"""
Knowledge structures, spaces, and learning spaces.
A knowledge structure on a domain Q is a family K of subsets of Q
(called knowledge states) that contains at least the empty set and Q itself.
Special cases:
- Knowledge space: closed under set union.
- Closure space: closed under set intersection.
- Learning space: a well-graded knowledge space (equivalently, an antimatroid).
References:
Doignon, J.-P., & Falmagne, J.-C. (1999).
Knowledge Spaces. Springer-Verlag.
Falmagne, J.-C., & Doignon, J.-P. (2011).
Learning Spaces. Springer-Verlag.
"""
from __future__ import annotations
from collections.abc import Collection, Iterator
from itertools import islice
from typing import TYPE_CHECKING
from knowledgespaces._limits import DEFAULT_MAX_N_ITEMS, check_domain_size
from knowledgespaces.structures.relations import SurmiseRelation
if TYPE_CHECKING:
from knowledgespaces.structures.set_family import SetFamily
from knowledgespaces.structures.surmise_function import SurmiseFunction
[docs]
class KnowledgeStructure:
"""A family of knowledge states over a domain of items.
Parameters
----------
domain : Collection[str]
The set of all items. Must be non-empty: the knowledge-structure
axioms (Falmagne & Doignon 2011, Def. 2.1.2) require a nonempty
domain Q, and every downstream algorithm in this package (BLIM
EM, QUERY, assessment) is undefined for ``|Q| = 0``. An empty
domain raises ``ValueError``.
states : Collection[Collection[str]]
The knowledge states (subsets of domain). The empty set and
the full domain are added automatically if missing.
"""
__slots__ = ("_domain", "_states")
def __init__(
self,
domain: Collection[str],
states: Collection[Collection[str]],
) -> None:
self._domain: frozenset[str] = frozenset(domain)
if len(self._domain) == 0:
raise ValueError(
"KnowledgeStructure requires a non-empty domain. "
"The axioms (Falmagne & Doignon 2011, Def. 2.1.2) are "
"defined on a nonempty set Q, and all downstream "
"algorithms (BLIM EM, QUERY, assessment) degenerate "
"silently on |Q|=0."
)
raw: set[frozenset[str]] = set()
for s in states:
fs = frozenset(s)
if not fs.issubset(self._domain):
extra = fs - self._domain
raise ValueError(f"State {set(fs)} contains items outside the domain: {set(extra)}")
raw.add(fs)
# Ensure ∅ and Q are present (axioms of a knowledge structure)
raw.add(frozenset())
raw.add(self._domain)
self._states: frozenset[frozenset[str]] = frozenset(raw)
# ------------------------------------------------------------------
# Properties
# ------------------------------------------------------------------
@property
def domain(self) -> frozenset[str]:
return self._domain
@property
def states(self) -> frozenset[frozenset[str]]:
return self._states
@property
def n_items(self) -> int:
return len(self._domain)
@property
def n_states(self) -> int:
return len(self._states)
# ------------------------------------------------------------------
# Structural properties
# ------------------------------------------------------------------
@property
def is_knowledge_space(self) -> bool:
"""True if closed under union."""
for s1 in self._states:
for s2 in self._states:
if (s1 | s2) not in self._states:
return False
return True
@property
def is_closure_space(self) -> bool:
"""True if closed under intersection."""
for s1 in self._states:
for s2 in self._states:
if (s1 & s2) not in self._states:
return False
return True
@property
def is_discriminative(self) -> bool:
"""True if no two items occur in exactly the same states (FD2011, 2.1)."""
return all(len(group) == 1 for group in self.item_equivalence_classes())
[docs]
def item_equivalence_classes(self) -> frozenset[frozenset[str]]:
"""Partition items by indistinguishability across knowledge states."""
groups: dict[frozenset[frozenset[str]], set[str]] = {}
for q in self._domain:
signature = frozenset(s for s in self._states if q in s)
groups.setdefault(signature, set()).add(q)
return frozenset(frozenset(group) for group in groups.values())
@property
def is_quasi_ordinal(self) -> bool:
"""True if closed under union and intersection (FD2011, Def. 3.8.1)."""
return self.is_knowledge_space and self.is_closure_space
@property
def is_ordinal(self) -> bool:
"""True if quasi-ordinal and discriminative (partial-order case)."""
return self.is_quasi_ordinal and self.is_discriminative
@property
def is_well_graded(self) -> bool:
"""True if every two states admit a tight path.
The path changes one item per step and has length equal to the
symmetric-difference distance (Falmagne & Doignon 2011,
Definition 2.2.2), including for non-union-closed structures.
For every ordered pair K, L, check that K has a neighbour one
step closer to L. Necessity follows from the first step of a
tight path. Sufficiency follows by repeatedly taking such a
step: the nonnegative integer distance decreases to zero.
Cost is ``O(|K|**2 * |Q|)`` set-membership checks in the worst case.
For the weaker predecessor condition use :attr:`is_accessible`.
"""
for state in self._states:
for target in self._states:
difference = state ^ target
if difference and not any(state ^ {q} in self._states for q in difference):
return False
return True
@property
def is_accessible(self) -> bool:
"""True if every state is reachable from the empty set.
Reachability means there exists a chain from ∅ to the state
where each step adds exactly one item.
"""
# On a finite family containing the empty state, the predecessor
# condition yields a chain to the empty state by induction on size.
return all(
not state or any(state - {q} in self._states for q in state) for state in self._states
)
@property
def is_learning_space(self) -> bool:
"""True if this is a well-graded knowledge space.
Equivalent to: knowledge space (union-closed) + well-graded.
Note that the absence of hanging states (accessibility) alone
does NOT characterize a learning space: union closure is also
required (Falmagne & Doignon 2011).
"""
# Antimatroid characterization (FD2011, Theorem 2.2.4).
return self.is_knowledge_space and self.is_accessible
# ------------------------------------------------------------------
# Fringe operations
# ------------------------------------------------------------------
[docs]
def inner_fringe(self, state: frozenset[str]) -> frozenset[str]:
"""Items whose removal yields another valid state.
A structural boundary, not a record of the individual's learning
history. Raises ValueError if the input is not a knowledge state.
"""
if state not in self._states:
raise ValueError("Fringes require a state in the knowledge structure.")
return frozenset(q for q in state if state - {q} in self._states)
[docs]
def outer_fringe(self, state: frozenset[str]) -> frozenset[str]:
"""Items whose addition yields another valid state.
These represent the 'next learnable' items from this state.
Raises ValueError if the input is not a knowledge state.
"""
if state not in self._states:
raise ValueError("Fringes require a state in the knowledge structure.")
return frozenset(q for q in self._domain - state if state | {q} in self._states)
[docs]
def hanging_states(self) -> list[frozenset[str]]:
"""Non-empty states with empty inner fringe.
A hanging state cannot be reached incrementally — it indicates
a structural problem in the learning space.
"""
return [s for s in self._states if s and not self.inner_fringe(s)]
# ------------------------------------------------------------------
# Analysis
# ------------------------------------------------------------------
[docs]
def atoms(self) -> dict[str, list[frozenset[str]]]:
"""Atoms of the knowledge structure.
An atom at item q is a **minimal** state containing q — i.e. a
state K such that q ∈ K and no proper subset of K that is also
a state contains q. An item can have **more than one** atom.
In a closure space (closed under intersection) each item has
exactly one atom (the intersection of all states containing it).
In a knowledge space (closed under union) the collection of all
atoms equals the base.
Returns
-------
dict[str, list[frozenset[str]]]
Mapping from each item to the list of its atoms (minimal
states containing that item), sorted by size then content.
References
----------
Doignon & Falmagne (1999), *Knowledge Spaces*, Def. 1.23.
Falmagne & Doignon (2011), *Learning Spaces*, Section 3.4.
"""
result: dict[str, list[frozenset[str]]] = {}
for q in self._domain:
states_with_q = [s for s in self._states if q in s]
if not states_with_q:
continue
# Keep only minimal states (no proper subset also contains q)
minimal: list[frozenset[str]] = []
for candidate in states_with_q:
if not any(other < candidate for other in states_with_q):
minimal.append(candidate)
result[q] = sorted(minimal, key=lambda s: (len(s), sorted(s)))
return result
@property
def item_heights(self) -> dict[str, int]:
"""Minimum cardinality of a state containing each item, minus one.
Equivalently, minimize over the atoms at that item. For knowledge
spaces this agrees with ``KnowledgeBase.item_heights`` and
``kstMatrix::kmheights``. It is not a Hasse level or the number of
individually necessary prerequisites. The presence of Q ensures
every item has a finite height, even outside union-closed spaces.
"""
return {q: min(len(s) for s in self._states if q in s) - 1 for q in sorted(self._domain)}
[docs]
def base(self) -> list[frozenset[str]]:
"""Minimal generating family under union.
The base B of a knowledge space K is the smallest family such
that K equals the closure of B under union (plus ∅).
A state K is in the base iff it cannot be expressed as the
union of states in K that are strictly contained in K.
Only meaningful for knowledge spaces (closed under union).
"""
result: list[frozenset[str]] = []
for state in self._states:
if not state:
continue
# Check if state = union of proper substates
proper_substates = [s for s in self._states if s < state]
union_of_substates: frozenset[str] = frozenset()
for s in proper_substates:
union_of_substates = union_of_substates | s
if union_of_substates != state:
result.append(state)
return sorted(result, key=lambda s: (len(s), sorted(s)))
[docs]
def states_by_size(self) -> dict[int, int]:
"""Distribution of states by cardinality."""
dist: dict[int, int] = {}
for state in self._states:
n = len(state)
dist[n] = dist.get(n, 0) + 1
return dict(sorted(dist.items()))
[docs]
def learning_paths(
self, target: frozenset[str] | None = None, max_paths: int = 100
) -> list[list[frozenset[str]]]:
"""Return at most ``max_paths`` gradations from ∅ to target.
Historical convenience name: this enumerates single-item additions.
A general learning path is a maximal chain and may have larger jumps
(Falmagne & Doignon 2011, §4.1). Use :meth:`iter_learning_paths`
for those chains, or :meth:`iter_gradations` for uncapped iteration.
Parameters
----------
target : frozenset[str] or None
Target state. Defaults to the full domain.
max_paths : int
Maximum number of paths to return (to avoid combinatorial explosion).
"""
if isinstance(max_paths, bool) or not isinstance(max_paths, int) or max_paths < 1:
raise ValueError("max_paths must be a positive integer.")
return [list(path) for path in islice(self.iter_gradations(target=target), max_paths)]
[docs]
def neighbourhood(
self, state: Collection[str], distance: int = 1, *, include: bool = False
) -> frozenset[frozenset[str]]:
"""States at symmetric-difference distance 1 through ``distance``.
The centre is excluded, as in ``kst::knneighbourhood``. This is a
set-distance neighbourhood, not a graph-distance ball: an intermediate
state need not exist. ``include=True`` also returns the centre,
including when the radius is zero.
"""
centre = frozenset(state)
if centre not in self._states:
raise ValueError("The centre must be a state in the structure.")
if isinstance(distance, bool) or not isinstance(distance, int) or distance < 0:
raise ValueError("distance must be a nonnegative integer.")
if not isinstance(include, bool):
raise ValueError("include must be a boolean.")
return frozenset(
s for s in self._states if (include or s != centre) and len(s ^ centre) <= distance
)
[docs]
def iter_gradations(
self,
start: Collection[str] | None = None,
target: Collection[str] | None = None,
*,
through: Collection[str] | None = None,
) -> Iterator[tuple[frozenset[str], ...]]:
"""Iterate all chains adding one item at a time between two states.
Defaults are ∅ and Q (gradations in Definition 4.1.3 of *Learning
Spaces*). Other endpoints give single-item chains in that interval;
they need not extend to a full gradation from ∅ to Q.
Endpoints must be states with ``start <= target``; disconnected
intervals yield no paths. Equal endpoints yield one singleton path.
``through`` restricts paths to those containing that state, including
an endpoint. A valid state outside the interval gives no paths.
Order is deterministic. Output can be factorial in the number of
items; use ``itertools.islice`` to limit consumption explicitly.
"""
yield from self._iter_chains(start, target, through=through, single_item=True)
[docs]
def iter_learning_paths(
self,
start: Collection[str] | None = None,
target: Collection[str] | None = None,
*,
through: Collection[str] | None = None,
) -> Iterator[tuple[frozenset[str], ...]]:
"""Iterate maximal inclusion chains in the specified interval.
With the default endpoints ∅ and Q these are learning paths (§4.1).
Consecutive states are inclusion covers, which may add several items.
Ordering, ``through`` filtering, endpoint validation and output-size
caveats are as for :meth:`iter_gradations`. No well-gradedness
assumption is made.
"""
yield from self._iter_chains(start, target, through=through, single_item=False)
def _iter_chains(
self,
start: Collection[str] | None,
target: Collection[str] | None,
*,
through: Collection[str] | None,
single_item: bool,
) -> Iterator[tuple[frozenset[str], ...]]:
first = frozenset() if start is None else frozenset(start)
last = self._domain if target is None else frozenset(target)
if first not in self._states or last not in self._states or not first <= last:
raise ValueError("Endpoints must be states with start <= target.")
middle = None if through is None else frozenset(through)
if middle is not None:
if middle not in self._states:
raise ValueError("through must be a state in the structure.")
if not first <= middle <= last:
return
# Iterative depth-first traversal avoids Python's recursion-depth limit.
stack: list[tuple[frozenset[str], ...]] = [(first,)]
while stack:
path = stack.pop()
current = path[-1]
if middle is not None and middle not in path and not current <= middle:
continue
if current == last:
yield path
continue
if single_item:
successors = [
current | {q} for q in sorted(last - current) if current | {q} in self._states
]
else:
above = [s for s in self._states if current < s <= last]
successors = sorted(
(s for s in above if not any(t < s for t in above)),
key=lambda s: (len(s), sorted(s)),
)
stack.extend((*path, s) for s in reversed(successors))
[docs]
def compatible_with(self, other: KnowledgeStructure) -> bool:
"""Whether both structures have the same traces on their overlap.
This is compatibility for meshing (2011, §7.3), including disjoint
domains. It does not assert compatibility of a skill map with a
competence space, which is a different concept.
"""
overlap = self._domain & other.domain
return {s & overlap for s in self._states} == {s & overlap for s in other.states}
[docs]
def maximal_mesh(
self, other: KnowledgeStructure, *, max_states: int = 100_000
) -> KnowledgeStructure:
"""Maximal mesh of compatible structures (2011, Definition 7.4.1).
States are exactly the unions of states agreeing on the overlap.
Thus projection onto either original domain recovers that structure.
Incompatible structures raise ``ValueError``. The exact output size
is checked against ``max_states`` before materializing the unions.
Even two learning spaces can have a mesh that is not well-graded.
"""
if isinstance(max_states, bool) or not isinstance(max_states, int) or max_states < 1:
raise ValueError("max_states must be a positive integer.")
overlap = self._domain & other.domain
groups: list[dict[frozenset[str], list[frozenset[str]]]] = [{}, {}]
for family, grouped in zip((self._states, other.states), groups, strict=True):
for state in family:
grouped.setdefault(state & overlap, []).append(state)
left, right = groups
if left.keys() != right.keys():
raise ValueError("Structures are incompatible on their shared domain.")
size = sum(len(states) * len(right[trace]) for trace, states in left.items())
if size > max_states:
raise ValueError(f"Mesh has {size} states, exceeding max_states={max_states}.")
states = {a | b for trace in left for a in left[trace] for b in right[trace]}
return KnowledgeStructure(self._domain | other.domain, states)
# ------------------------------------------------------------------
# Factories
# ------------------------------------------------------------------
[docs]
@classmethod
def from_surmise_relation(
cls,
relation: SurmiseRelation,
*,
max_items: int | None = None,
) -> KnowledgeStructure:
"""Build the quasi-ordinal knowledge space from a surmise relation.
A state is valid iff for every item in the state, all its
prerequisites are also in the state (downward closure).
The resulting structure is always closed under both union
and intersection (it is a distributive lattice).
The states are generated as the span (union closure) of the
principal downsets of the quasi order, so the cost scales with
the number of states rather than with ``2^|Q|``. The domain-size
preflight is unchanged because the number of states itself can
be exponential in ``|Q|``; `max_items` overrides the default
hard limit for advanced callers.
"""
closure = relation.transitive_closure()
items = sorted(closure.items)
check_domain_size(
len(items),
max_threshold=max_items if max_items is not None else DEFAULT_MAX_N_ITEMS,
context="from_surmise_relation",
)
# The downsets of a quasi order are exactly the unions of its
# principal downsets {q} | prerequisites(q): every union of
# downsets is a downset, and a downset D is the union of the
# principal downsets of its elements.
principal = [frozenset({item}) | closure.prerequisites_of(item) for item in items]
states: set[frozenset[str]] = {frozenset()}
for down in principal:
states.update([s | down for s in states])
return cls(items, states)
[docs]
@classmethod
def from_states(cls, states: Collection[Collection[str]]) -> KnowledgeStructure:
"""Build from an explicit collection of states.
The domain is inferred as the union of all states.
"""
all_items: set[str] = set()
for s in states:
all_items.update(s)
return cls(all_items, states)
# ------------------------------------------------------------------
# Set operations
# ------------------------------------------------------------------
[docs]
def dual(self) -> KnowledgeStructure:
"""The complementary family {Q - K : K in the structure} (FD2011, 2.2.2)."""
return KnowledgeStructure(self._domain, [self._domain - s for s in self._states])
[docs]
def union_closure(self, *, max_items: int | None = None) -> KnowledgeStructure:
"""Smallest knowledge space containing this structure.
Exact finite union closure. The result may have 2**|Q| states;
the standard domain-size guard applies before enumeration.
"""
check_domain_size(
self.n_items,
context="union_closure",
max_threshold=max_items if max_items is not None else DEFAULT_MAX_N_ITEMS,
)
closed: set[frozenset[str]] = {frozenset()}
for state in self._states:
closed.update([s | state for s in closed])
return KnowledgeStructure(self._domain, closed)
[docs]
def intersection_closure(self, *, max_items: int | None = None) -> KnowledgeStructure:
"""Smallest intersection-closed structure containing this structure.
Computed through complementation and union closure (De Morgan).
"""
return self.dual().union_closure(max_items=max_items).dual()
[docs]
def intersection_with(self, other: KnowledgeStructure) -> KnowledgeStructure:
"""Intersection of two structures: states present in both."""
if self._domain != other._domain:
raise ValueError("Domains must match for intersection.")
common = self._states & other._states
return KnowledgeStructure(self._domain, common)
[docs]
def as_family(self) -> SetFamily:
"""Expose the states as a family for operations without automatic axioms."""
from knowledgespaces.structures.set_family import SetFamily
return SetFamily(self._domain, self._states)
[docs]
def union_with(self, other: KnowledgeStructure) -> KnowledgeStructure:
"""Union of two state families on the same domain, without union closure."""
return self.as_family().union_with(other.as_family()).to_knowledge_structure()
[docs]
def quotient(self) -> tuple[KnowledgeStructure, dict[str, frozenset[str]]]:
"""Collapse equivalent items and retain the label-to-class mapping."""
family, classes = self.as_family().quotient()
return family.to_knowledge_structure(), classes
[docs]
def projection(self, sub_domain: Collection[str]) -> KnowledgeStructure:
"""Project (restrict) the structure to a subset of items.
For each state K, the projected state is K ∩ sub_domain.
Only items present in the original domain are retained.
Raises
------
ValueError
If sub_domain contains items not in the original domain.
"""
sub = frozenset(sub_domain)
extra = sub - self._domain
if extra:
raise ValueError(f"sub_domain contains items outside the domain: {set(extra)}")
projected = {s & sub for s in self._states}
return KnowledgeStructure(sub, projected)
# ------------------------------------------------------------------
# Surmise relation extraction
# ------------------------------------------------------------------
[docs]
def surmise_function(self) -> SurmiseFunction:
"""Derive the surmise function from this knowledge space.
For each item q, σ(q) is the set of atoms at q (minimal states
containing q). Requires a knowledge space (union-closed) where
every item has at least one atom (granularity).
Returns
-------
SurmiseFunction
Raises
------
ValueError
If the structure is not a granular knowledge space.
References
----------
Falmagne & Doignon (2011), Definition 5.2.1, Theorem 5.2.5.
"""
from knowledgespaces.structures.surmise_function import SurmiseFunction
return SurmiseFunction.from_knowledge_space(self)
[docs]
def surmise_relation(self) -> SurmiseRelation:
"""Extract the surmise relation implied by this structure.
Item a is a prerequisite of b iff every state containing b
also contains a.
"""
items = sorted(self._domain)
relations: set[tuple[str, str]] = set()
for a in items:
for b in items:
if a == b:
continue
if all(a in s for s in self._states if b in s):
relations.add((a, b))
return SurmiseRelation(items, relations)
# ------------------------------------------------------------------
# Dunder methods
# ------------------------------------------------------------------
def __contains__(self, state: Collection[str]) -> bool:
return frozenset(state) in self._states
def __len__(self) -> int:
return len(self._states)
def __iter__(self) -> Iterator[frozenset[str]]:
return iter(sorted(self._states, key=lambda s: (len(s), sorted(s))))
def __eq__(self, other: object) -> bool:
if not isinstance(other, KnowledgeStructure):
return NotImplemented
return self._domain == other._domain and self._states == other._states
def __repr__(self) -> str:
return f"KnowledgeStructure(items={self.n_items}, states={self.n_states})"