"""
Inductive item tree analysis (IITA).
Derives a quasi order (surmise relation) from binary response data. The
three classical sample-level variants are implemented: original
(Schrepp, 1999, 2003), corrected, and minimized corrected (Sargin &
Ünlü, 2009). All three share the same inductive generation of candidate
quasi orders from the counterexample counts and differ in how the
expected counterexamples, and hence the *diff* fit measure, are
computed.
The implementation mirrors the sample-level algorithms of the R package
``DAKS`` (Ünlü & Sargin, 2010) and is numerically cross-validated
against it (see ``tests/test_iita.py``). Population quantities and
delta-method inference are available in ``derivation.iita_inference``,
with documented corrections and regularity restrictions.
References:
Schrepp, M. (2003). A method for the analysis of hierarchical
dependencies between items of a questionnaire. Methods of
Psychological Research Online, 8(1), 43-79.
Sargin, A., & Ünlü, A. (2009). Inductive item tree analysis:
Corrections, improvements, and comparisons. Mathematical Social
Sciences, 58(3), 376-392.
Ünlü, A., & Sargin, A. (2010). DAKS: An R package for data analysis
methods in knowledge space theory. Journal of Statistical Software,
37(2), 1-31.
"""
from __future__ import annotations
from collections.abc import Sequence
from dataclasses import dataclass
from typing import Literal
import numpy as np
from knowledgespaces.estimation.blim_em import ResponseMatrix
from knowledgespaces.structures.relations import SurmiseRelation
__all__ = ["IITAResult", "counterexamples", "iita", "inductive_generation"]
_Pair = tuple[int, int]
[docs]
def counterexamples(data: ResponseMatrix) -> np.ndarray:
"""Counterexample counts ``b[i, j]`` for each ordered item pair.
``b[i, j]`` counts the respondents who solve item ``j`` and fail
item ``i``. A small ``b[i, j]`` supports the implication that
mastery of ``j`` entails mastery of ``i``, that is, the pair
``(i, j)`` of the derived surmise relation. Pattern frequencies in
``data.counts`` are respected. The diagonal is zero.
"""
P = data.patterns.astype(np.float64)
w = data.effective_counts.astype(np.float64)
return ((1.0 - P) * w[:, np.newaxis]).T @ P
def _pairs(relation: SurmiseRelation, items: list[str]) -> frozenset[tuple[int, int]]:
if set(items) != relation.items or len(items) != len(set(items)):
raise ValueError("Item labels must match the relation's domain exactly once.")
if len(items) < 2:
raise ValueError("IITA needs at least two items.")
if relation.transitive_closure().relations != relation.relations:
raise ValueError(
"Supply a transitively closed relation; generators are not silently closed."
)
indices = {q: i for i, q in enumerate(items)}
pairs = frozenset((indices[a], indices[b]) for a, b in relation.relations)
if not pairs:
raise ValueError("IITA error rates require at least one nonreflexive implication.")
return pairs
def _inductive_generation(b: np.ndarray) -> list[frozenset[_Pair]]:
"""Inductively generate the selection set of candidate quasi orders.
Mirrors ``DAKS::ind_gen``: candidate pairs enter by increasing
counterexample count; at each threshold, entering pairs that would
break transitivity of the accumulated relation are discarded (and
reconsidered at later thresholds); duplicate and empty candidates
are dropped at the end.
"""
m = b.shape[0]
off_diag = [(i, j) for i in range(m) for j in range(m) if i != j]
level_1 = {(i, j) for (i, j) in off_diag if b[i, j] == b.min()}
candidates: list[set[_Pair]] = [set(level_1)]
a_prev: set[_Pair] = set(level_1)
thresholds = np.unique(b)
thresholds = thresholds[thresholds != 0]
for elem in thresholds:
entering = {(i, j) for (i, j) in off_diag if b[i, j] <= elem and (i, j) not in a_prev}
m_k = set(entering)
# Fixpoint: drop pairs whose addition breaks transitivity of
# a_prev | m_k; a dropped pair can free further drops, so the
# pass repeats until stable. Iteration order matches DAKS
# (lexicographic snapshot per pass, live membership checks).
while True:
changed = False
for x, y in sorted(m_k):
# Only the pair currently being processed is ever discarded
# below, so every (x, y) of the sorted snapshot is still a
# member when its turn comes — no liveness re-check needed.
for h in range(m):
if h in (x, y):
continue
if ((y, h) in a_prev or (y, h) in m_k) and not (
(x, h) in a_prev or (x, h) in m_k
):
m_k.discard((x, y))
changed = True
if ((h, x) in a_prev or (h, x) in m_k) and not (
(h, y) in a_prev or (h, y) in m_k
):
m_k.discard((x, y))
changed = True
if not changed:
break
a_prev = a_prev | m_k
candidates.append(set(a_prev))
result: list[frozenset[_Pair]] = []
seen: set[frozenset[_Pair]] = set()
for cand in candidates:
frozen = frozenset(cand)
if frozen and frozen not in seen:
seen.add(frozen)
result.append(frozen)
return result
[docs]
def inductive_generation(
counterexample_counts: np.ndarray, *, items: Sequence[str]
) -> tuple[SurmiseRelation, ...]:
"""Generate IITA candidates from a counterexample matrix (DAKS ind_gen).
b[i,j] counts failures on i paired with success on j; items follow the
rows and columns. Input must be finite, nonnegative, square with zero
diagonal and at least two distinct string labels. Zero-counterexample
implications must already be transitive, as they are for actual data.
These necessary conditions do not certify realizability of all counts
by a response matrix. Use counterexamples(data) for observed counts.
Candidates are nested, transitively closed, nonempty in strict pairs,
and deduplicated. No model fitting or state enumeration is performed.
"""
labels = list(items)
if (
len(labels) < 2
or any(not isinstance(q, str) for q in labels)
or len(labels) != len(set(labels))
):
raise ValueError("items must contain at least two distinct string labels.")
b = np.asarray(counterexample_counts, dtype=float)
if (
b.shape != (len(labels), len(labels))
or not np.isfinite(b).all()
or np.any(b < 0)
or np.any(np.diag(b) != 0)
):
raise ValueError(
"Counterexample matrix must be finite, nonnegative, square, with zero diagonal."
)
zero = SurmiseRelation(
labels,
[
(a, c)
for i, a in enumerate(labels)
for j, c in enumerate(labels)
if i != j and b[i, j] == 0
],
)
if zero.transitive_closure() != zero:
raise ValueError("Zero-counterexample implications must be transitive.")
return tuple(
SurmiseRelation(labels, [(labels[i], labels[j]) for i, j in pairs])
for pairs in _inductive_generation(b)
)
def _error_rate(b: np.ndarray, p: np.ndarray, relation: frozenset[_Pair]) -> float:
"""Average violation rate over the pairs of the candidate relation."""
return float(sum(b[i, j] / p[j] for (i, j) in relation) / len(relation))
def _error_rate_minimized(b: np.ndarray, p: np.ndarray, relation: frozenset[_Pair]) -> float:
"""Error rate minimizing the corrected diff in closed form."""
num = 0.0
den = 0.0
m = b.shape[0]
for i in range(m):
for j in range(m):
if i == j:
continue
if (i, j) in relation:
num += -2.0 * b[i, j] * p[j]
den += 2.0 * p[j] ** 2
elif (j, i) in relation:
num += -2.0 * b[i, j] * p[i] + 2.0 * p[i] * p[j] - 2.0 * p[i] ** 2
den += 2.0 * p[i] ** 2
return float(-num / den)
def _diff(
b: np.ndarray,
p: np.ndarray,
n: float,
relation: frozenset[_Pair],
gamma: float,
version: str,
) -> float:
"""The *diff* fit measure: mean squared deviation between observed
and expected counterexample counts over ordered item pairs."""
m = b.shape[0]
expected = np.zeros_like(b, dtype=np.float64)
for i in range(m):
for j in range(m):
if i == j:
continue
if (i, j) in relation:
expected[i, j] = gamma * p[j]
elif version == "original":
expected[i, j] = (1.0 - p[i] / n) * p[j] * (1.0 - gamma)
elif (j, i) in relation:
expected[i, j] = p[j] - p[i] + p[i] * gamma
else:
expected[i, j] = (1.0 - p[i] / n) * p[j]
return float(((b - expected) ** 2).sum() / (m**2 - m))
[docs]
@dataclass(frozen=True)
class IITAResult:
"""Result of an inductive item tree analysis.
Attributes
----------
implications : frozenset[tuple[str, str]]
The selected quasi order as pairs ``(q, q')`` read as ``q`` is a
prerequisite of ``q'``.
relation : SurmiseRelation
The selected quasi order as a :class:`SurmiseRelation`. Convert
to a knowledge space with
``KnowledgeStructure.from_surmise_relation(relation.transitive_closure())``.
diff : tuple[float, ...]
The *diff* fit measure of every candidate in the selection set;
the selected candidate minimizes it.
error_rate : float
IITA error rate gamma of the selected candidate, not a BLIM slip estimate.
error_rates : tuple[float, ...]
IITA error rates for every candidate, in selection_set order.
selected_index : int
Index of the selected candidate in ``selection_set``.
selection_set : tuple[frozenset[tuple[str, str]], ...]
The generated or explicitly supplied candidate quasi orders.
version : str
The variant used: ``"original"``, ``"corrected"``, or
``"minimized"``.
"""
implications: frozenset[tuple[str, str]]
relation: SurmiseRelation
diff: tuple[float, ...]
error_rate: float
selected_index: int
selection_set: tuple[frozenset[tuple[str, str]], ...]
version: str
error_rates: tuple[float, ...] = ()
[docs]
def iita(
data: ResponseMatrix,
*,
version: Literal["original", "corrected", "minimized"] = "minimized",
selection_set: Sequence[SurmiseRelation] | None = None,
) -> IITAResult:
"""Derive a surmise relation from response data by IITA.
Inductive item tree analysis generates a nested family of candidate
quasi orders from the pairwise counterexample counts of the data and
selects the candidate that minimizes the *diff* measure, the mean
squared deviation between observed and expected counterexample
counts (Schrepp, 2003; Sargin & Ünlü, 2009).
Parameters
----------
data : ResponseMatrix
Observed binary response patterns; pattern frequencies in
``data.counts`` are respected. Every item must be solved at
least once and the domain must contain at least two items.
version : {"original", "corrected", "minimized"}
The variant of the expected counterexample counts. The
corrected variant treats pairs whose reverse belongs to the
candidate consistently; the minimized corrected variant
(default) additionally chooses the error rate that minimizes
*diff* in closed form.
selection_set : Sequence[SurmiseRelation] or None
Optional prespecified candidates, corresponding to DAKS orig_iita,
corr_iita and mini_iita's A argument. Each must have the data's
domain, already be transitive, and contain a nonreflexive pair.
The supplied order and duplicates are retained; first wins ties.
None generates candidates inductively. Evaluating or selecting
candidates is descriptive; no post-selection inference is implied.
Returns
-------
IITAResult
The selected quasi order with the full selection set and fit
measures.
Raises
------
ValueError
If ``version`` is unknown, the domain has fewer than two items,
or some item is never solved.
Examples
--------
>>> import numpy as np
>>> from knowledgespaces.estimation import ResponseMatrix
>>> data = ResponseMatrix(
... items=["a", "b"],
... patterns=np.array([[1, 1], [1, 0], [0, 0]]),
... counts=np.array([50.0, 30.0, 20.0]),
... )
>>> sorted(iita(data).implications)
[('a', 'b')]
"""
if version not in ("original", "corrected", "minimized"):
raise ValueError(
f"version must be 'original', 'corrected', or 'minimized', got {version!r}."
)
if data.n_items < 2:
raise ValueError("IITA requires at least two items.")
b = counterexamples(data)
p = (data.patterns.astype(np.float64) * data.effective_counts[:, np.newaxis]).sum(axis=0)
n = data.n_respondents
never_solved = [data.items[j] for j in range(data.n_items) if p[j] == 0]
if never_solved:
raise ValueError(f"Every item must be solved at least once; never solved: {never_solved}.")
if selection_set is None:
selection = _inductive_generation(b)
else:
if not selection_set:
raise ValueError("selection_set must contain at least one relation.")
selection = [_pairs(relation, data.items) for relation in selection_set]
diffs: list[float] = []
gammas: list[float] = []
for cand in selection:
if version == "minimized":
gamma = _error_rate_minimized(b, p, cand)
else:
gamma = _error_rate(b, p, cand)
gammas.append(gamma)
diffs.append(_diff(b, p, n, cand, gamma, version))
best = int(np.argmin(diffs))
implications = frozenset((data.items[i], data.items[j]) for (i, j) in selection[best])
relation = SurmiseRelation(list(data.items), sorted(implications))
return IITAResult(
implications=implications,
relation=relation,
diff=tuple(diffs),
error_rate=gammas[best],
selected_index=best,
selection_set=tuple(
frozenset((data.items[i], data.items[j]) for (i, j) in cand) for cand in selection
),
version=version,
error_rates=tuple(gammas),
)