Knowledge Structures and Relations¶

Surmise relations¶

A surmise relation (or prerequisite relation) is a quasi-order (reflexive and transitive) on items — a partial order when the item domain is discriminative. If \((a, b)\) is in the relation, then mastering \(a\) is a prerequisite for mastering \(b\).

from knowledgespaces import SurmiseRelation

rel = SurmiseRelation(
    items=["a", "b", "c", "d"],
    relations=[("a", "b"), ("a", "c"), ("b", "d"), ("c", "d")],
)

Transitive closure and Hasse diagram¶

closure = rel.transitive_closure()   # all implied relations
hasse = closure.transitive_reduction()  # minimal representation

print(closure.levels())  # {'a': 0, 'b': 1, 'c': 1, 'd': 2}
print(hasse.minimal_items())  # {'a'}

The transitive closure adds all transitively implied edges. For a partial order, the transitive reduction keeps only cover edges. With equivalent items, distinguish the quasi-order from the partial order on its equivalence classes.

Knowledge structures¶

A knowledge structure \(\mathcal{K}\) on a domain \(Q\) is a family of subsets of \(Q\) (called knowledge states) that contains \(\emptyset\) and \(Q\).

from knowledgespaces import KnowledgeStructure

ks = KnowledgeStructure.from_surmise_relation(closure)
print(ks.n_states)  # number of valid states

Structural properties¶

Property	Meaning	Check
Knowledge space	Closed under \(\cup\)	`ks.is_knowledge_space`
Closure space	Closed under \(\cap\)	`ks.is_closure_space`
Accessible	Every nonempty state has a single-item predecessor	`ks.is_accessible`
Well-graded	Every pair of states admits a path of symmetric-difference length	`ks.is_well_graded`
Learning space	Knowledge space + well-graded	`ks.is_learning_space`

Fringes¶

For a state \(K\):

Inner fringe: items \(q \in K\) such that \(K \setminus \{q\} \in \mathcal{K}\) — possible last additions on a compatible path.
Outer fringe: items \(q \notin K\) such that \(K \cup \{q\} \in \mathcal{K}\) — what the student is ready to learn.

state = frozenset({"a", "b"})
print(ks.outer_fringe(state))  # next learnable items
print(ks.inner_fringe(state))  # removable items that leave a state

A hanging state is a non-empty state with empty inner fringe — it cannot be reached by adding items one at a time. It is allowed in a general knowledge structure but excludes a learning space. Use ks.hanging_states() to list them.

Base of the space¶

The base is the minimal generating family under union. Every state in the space can be expressed as a union of base elements.

print(ks.base())

KnowledgeBase stores a compact base without enumerating its span:

from knowledgespaces import KnowledgeBase

base = KnowledgeBase({"a", "b", "c"}, [{"a"}, {"a", "b"}, {"a", "c"}])
assert {"a", "b"} in base
assert base.outer_fringe({"a"}) == {"b", "c"}
assert base.inner_fringe({"a", "b"}) == {"b"}
assert base.to_knowledge_space().n_states == 5

A state equals the union of its contained base sets. For a state \(K\), \(q\) belongs to the outer fringe exactly when a base set \(B\) satisfies \(B\setminus K=\{q\}\). These finite union-span consequences (Falmagne & Doignon 2011, Chapter 3) support membership and fringes without expansion. Inner fringes test single-item deletions. to_knowledge_space() expands the span and may be expensive; from_structure() rejects non-union-closed input. BLIM fitting still uses an explicit KnowledgeStructure.

Learning paths¶

A learning path is a maximal inclusion chain from \(\emptyset\) to \(Q\). A gradation is a path where each step adds exactly one item:

for path in ks.iter_gradations():
    print([set(s) for s in path])

Use iter_learning_paths() for maximal chains, including larger jumps. The historical learning_paths() returns at most 100 gradations by default. See combining structures for interval endpoints, neighbourhoods, maximal meshing and computational limits.

Surmise functions¶

For general clauses before canonicalization, operations on arbitrary families, compact joins/intersections, quotients and refinement, see attributions and algebra.

A surmise function \(\sigma\) generalises the surmise relation by allowing multiple alternative clauses per item. Each clause represents a possible minimal foundation for mastering an item.

When each item has exactly one clause, the surmise function reduces to a surmise relation (the quasi-ordinal case).

from knowledgespaces import SurmiseFunction

sf = SurmiseFunction(
    domain={"a", "b", "c", "d", "e"},
    clauses={
        "a": [{"a"}],
        "b": [{"b", "d"}, {"a", "b", "c"}, {"b", "c", "e"}],
        "c": [{"a", "b", "c"}, {"b", "c", "e"}],
        "d": [{"b", "d"}],
        "e": [{"b", "c", "e"}],
    },
)

Here item b has three alternative foundations: you can master b by belonging to a state containing b,d, or a,b,c, or b,c,e. Clauses express minimal supporting states, not a temporal order: this example includes equivalent items and is not a learning space.

Properties¶

Property	Meaning	Check
Quasi-ordinal	One clause per item (equivalent to a surmise relation)	`sf.is_quasi_ordinal`
Ordinal	Quasi-ordinal and discriminative	`sf.is_ordinal`
Discriminative	Distinct items have distinct clause families	`sf.is_discriminative`
Acyclic	No cycles in the prerequisite graph \(R_\sigma\)	`sf.is_acyclic`

Deriving a knowledge space¶

A surmise function uniquely defines a (granular) knowledge space (Theorem 5.2.5, Learning Spaces). A set \(K\) is a state iff every item in \(K\) has at least one clause contained in \(K\):

ks = sf.to_knowledge_space()
print(ks.n_states)       # 10
print(ks.is_knowledge_space)  # True

Extracting a surmise function from a knowledge space¶

Conversely, the surmise function of a knowledge space is derived from its atoms — the clause for each item is the set of atoms at that item:

sf2 = ks.surmise_function()
assert sf2 == sf  # roundtrip identity

High-level API¶

import knowledgespaces as ks

structure = ks.space_from_surmise_function({
    "a": [["a"]],
    "b": [["b", "d"], ["a", "b", "c"], ["b", "c", "e"]],
    "c": [["a", "b", "c"], ["b", "c", "e"]],
    "d": [["b", "d"]],
    "e": [["b", "c", "e"]],
})

Converting to/from surmise relations¶

from knowledgespaces import SurmiseRelation

# Surmise relation → ordinal surmise function
rel = SurmiseRelation(["a", "b", "c"], [("a", "b"), ("b", "c")])
sf_ordinal = SurmiseFunction.from_surmise_relation(rel)
assert sf_ordinal.is_ordinal

# Back to surmise relation (only if ordinal)
rel2 = sf_ordinal.to_surmise_relation()

Exact property checks and closures¶

is_accessible tests single-item predecessors. is_well_graded tests tight paths between every pair of states, including incomparable states and structures that are not union-closed. The learning-space check uses the equivalent finite antimatroid condition: accessibility and union closure (Falmagne & Doignon 2011, Definition 2.2.2, Theorem 2.2.4).

is_quasi_ordinal requires both union and intersection closure. is_ordinal additionally requires discriminativity. Use item_equivalence_classes() to inspect items that cannot be distinguished by any state, and is_discriminative to test whether all classes are singletons. The same distinction is available on a SurmiseFunction: is_quasi_ordinal means one clause per item; is_ordinal also requires distinct clause families.

dual() complements every state. union_closure() and intersection_closure() return the smallest containing family closed under the respective operation. They preserve the domain and can grow exponentially; the standard max_items guard is available.

SurmiseRelation preserves supplied generating pairs. These need not be transitively closed or Hasse covers. Use transitive_closure() for the mathematical quasi-order and transitive_reduction() for a Hasse diagram when its closure is antisymmetric. Minimal/maximal elements include all items in minimal/maximal equivalence classes of a quasi-order.