Combining structures, skills and assessment

These operations implement finite definitions from Learning Spaces (Falmagne & Doignon, 2011), Chapters 4, 6, 7 and 13. They also provide targeted interoperability with kst, kstMatrix, CbKST and kstIO. Matching a reference package on examples is a compatibility check, not a proof of correctness or a claim of complete package parity.

Neighbourhoods and paths

from itertools import islice
from knowledgespaces import KnowledgeStructure

structure = KnowledgeStructure("abc", ["a", "ab"])
print(structure.neighbourhood("a", distance=2))
print(list(structure.iter_gradations(start="a", target="abc")))
first_ten = list(islice(structure.iter_learning_paths(), 10))

neighbourhood(K, distance=d) returns states at symmetric-difference distance 1 through d; K itself is excluded. This matches kst::knneighbourhood. It is not a graph-distance ball: on {∅, {a,b}}, the full state is a distance-two neighbour of ∅ even though no single-item path connects them.

A learning path is a maximal inclusion chain from ∅ to Q; a gradation adds exactly one item at every step (Definition 4.1.3). iter_learning_paths() and iter_gradations() distinguish these notions. Both accept nested state endpoints for an interval, use deterministic order, and yield tuples lazily. A full gradation can exist only in a discriminative structure; arbitrary structures can have learning paths with larger jumps.

The historical learning_paths(target, max_paths=100) still returns a bounded list of gradations for compatibility. Its name does not imply that it enumerates every maximal chain. Use the iterators for the explicit notions and islice for an explicit output limit. Enumeration may have factorially many results; the iterators do not remove this output cost.

Maximal mesh

left = KnowledgeStructure("ab", ["a"])
right = KnowledgeStructure("bc", ["b"])
assert left.compatible_with(right)
mesh = left.maximal_mesh(right, max_states=100_000)
assert mesh.projection(left.domain) == left
assert mesh.projection(right.domain) == right

Compatibility means equality of the two projections on the overlapping domain. The maximal mesh is exactly

\[\{K\subseteq Y\cup Z: K\cap Y\in\mathcal F, K\cap Z\in\mathcal G\}.\]

Implementation groups states by their overlap, then takes unions only within matching groups (Definition 7.4.1). The exact number of resulting states is checked before materialization. Incompatible structures raise ValueError. Disjoint domains are compatible. Even compatible learning spaces can have a mesh that is not well-graded (Example 7.4.4).

This intentionally differs from kstMatrix 3.0-0::kmmesh on some overlaps: that version can include unions whose traces fail to recover the inputs. For the example above Python returns ∅, {a}, {a,b}, {a,b,c}; the R reference also returns {b} and {b,c}, which violate the first projection. The small-domain tests check the defining projection equation independently.

Inverting a skill multimap

from knowledgespaces import SkillMultiMap
from knowledgespaces.derivation import minimal_competencies, compatible_competencies

skills = SkillMultiMap("ab", "xy", {"a": ["x", "y"], "b": ["x", "y"]})
exact = minimal_competencies("a", skills)              # empty family: impossible
sufficient = minimal_competencies("a", skills, exact=False)  # { {x}, {y} }
competences = KnowledgeStructure("xy", ["x", "y"])
all_compatible = compatible_competencies("ab", skills, competences)

For a performance state P, exact inversion requires p(C) = P. Setting exact=False requires only P ⊆ p(C): other items may also be solvable. CbKST::cbkst_perf2comp uses the latter positive-coverage computation in the inspected 0.1-1 source. It must not be interpreted as an exact inverse when nonmastered items also constrain the performance.

minimal_competencies returns all inclusion-minimal solutions, not just those of smallest cardinality. With competence_structure=..., minimality is evaluated among admissible states. Without it, every skill subset is admissible and the algorithm builds minimal unions of alternative competencies. The max_candidates guard bounds intermediate families; it raises instead of truncating the answer. Empty competencies and unused skills are supported. An empty solution family differs from a family containing the empty skill set.

These functions also accept conjunctive SkillMap. They make no probabilistic inference from noisy answers, and do not extend the conjunctive fringe/floor theorems of CompetenceModel to multimaps.

Multiplicative assessment

from knowledgespaces.assessment import MultiplicativePosterior, select_item_half_split

posterior = MultiplicativePosterior.uniform(mesh, zeta0=1.2, zeta1=2.1)
item = select_item_half_split(posterior).item
posterior = posterior.update(item, True)
print(posterior.most_likely_state)

For response r to item q, multiply the mass of every agreeing state by ζ(q,r)>1 and renormalize; other states receive factor 1 (Equations 13.9–13.10). zeta0 rewards agreement with incorrect responses and zeta1 with correct ones. Each accepts a scalar or a complete item mapping. Updates use logarithms to handle large finite factors, retain prior zero masses, and return a new object. is_converged and half-split selection support both Bayesian and multiplicative distributions.

The multiplicative weights are not themselves conditional response probabilities. With positive BLIM errors, the Bayesian equivalence is ζ(q,1)=(1−β(q))/η(q), ζ(q,0)=(1−η(q))/β(q) (Remark 13.4.5). Our EIG policy uses a specified BLIM response model, including its actual response probabilities. It is not an alias for kstMatrix’s mastery-weighted kmassessinformative heuristic. No automatic response model or EIG policy is attached to MultiplicativePosterior.

See I/O for repeated-item competency tables and KST/SRBT text formats. The executable cookbook/08_structures_assessment_io.py combines the operations above and checks its round trips.

References: Falmagne & Doignon (2011), Learning Spaces; versioned source comparisons with kst, kstMatrix, CbKST and kstIO.