Knowledge Structures and Relations¶

Surmise relations¶

A surmise relation (or prerequisite relation) is a partial order on items. 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. The transitive reduction (Hasse diagram) keeps only the direct edges.

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`
Well-graded	Every state has a predecessor	`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}\) — the most recently consolidated items.
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))  # most recently consolidated

A hanging state is a non-empty state with empty inner fringe — it cannot be reached by adding items one at a time, and usually signals a problem in the structure. 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())

Learning paths¶

A learning path is a sequence of states from \(\emptyset\) to \(Q\) where each step adds exactly one item:

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

Surmise functions¶

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 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 first mastering d, or by mastering both a and c, or by mastering both c and e.

Properties¶

Property	Meaning	Check
Ordinal	One clause per item (equivalent to surmise relation)	`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()