Mathematical Foundations

Basic definitions

Definition — Knowledge Structure

A knowledge structure on a finite domain \(Q\) is a pair \((Q, \mathcal{K})\) where \(\mathcal{K} \subseteq 2^Q\) is a family of subsets (called knowledge states) such that:

  1. \(\emptyset \in \mathcal{K}\) (the empty state)

  2. \(Q \in \mathcal{K}\) (the full domain)

The elements of \(Q\) are called items — problems or questions whose mastery is represented by membership in a state. In competence-based models, latent skills form a separate domain.

Special structures

Definition — Knowledge Space

A knowledge structure \((Q, \mathcal{K})\) is a knowledge space if \(\mathcal{K}\) is closed under set union:

\[K_1, K_2 \in \mathcal{K} \implies K_1 \cup K_2 \in \mathcal{K}\]

Definition — Learning Space

A knowledge space \((Q, \mathcal{K})\) is a learning space if it is well-graded: any two states \(K,L\) can be joined by a sequence of states that changes one item at each step and has exactly \(|K \triangle L|\) steps (Falmagne & Doignon, 2011, Definition 2.2.2).

Accessibility is the weaker condition that every nonempty state \(K\) has some \(q \in K\) with \(K \setminus \{q\} \in \mathcal{K}\). For a finite union-closed knowledge structure it is equivalent to well-gradedness (Theorem 2.2.4); for arbitrary structures it is not. A learning space allows every admissible state to be reached from \(\emptyset\) by adding one item at a time; it need not contain every subset of the domain.

Surmise relations

A surmise relation (or prerequisite relation) is a quasi-order (reflexive and transitive) \(\preceq\) on \(Q\). If \(a \preceq b\), then mastering \(a\) is a prerequisite for mastering \(b\). On a discriminative item domain — no two distinct items are mutually prerequisite — it is additionally antisymmetric, i.e. a partial order. Equivalent items can also occur in ordinary knowledge structures; they always occur together in the states.

The quasi-ordinal space generated by a surmise relation is the family of all downsets (downward-closed subsets):

\[\mathcal{K} = \{K \subseteq Q \mid \forall q \in K, \; \text{prereq}(q) \subseteq K\}\]

This is always closed under both union and intersection (a distributive lattice). It is ordinal precisely when it is also discriminative (Definition 3.8.1). The Python SurmiseRelation constructor stores generating pairs; transitive_closure() obtains the generated quasi-order, with reflexive membership implicit.

Surmise functions

A surmise function \(\sigma: Q \to 2^{2^Q}\) generalises the surmise relation. For each item \(q\), \(\sigma(q)\) is a family of clauses — alternative minimal foundations for mastering \(q\).

Four axioms define a surmise function (Def. 5.1.2):

  1. \(\sigma(q) \neq \emptyset\) — at least one clause per item

  2. \(q \in C\) for all \(C \in \sigma(q)\) — each clause contains its item

  3. If \(q' \in C \in \sigma(q)\), then \(\exists\, C' \in \sigma(q')\) with \(C' \subseteq C\) — refinement

  4. Clauses for the same item are incomparable under \(\subseteq\)

Theorem 5.2.5 (Learning Spaces): There is a one-to-one correspondence between granular knowledge spaces and surmise functions. The clauses of \(\sigma\) are exactly the atoms of \(\mathcal{K}\), and a set \(K\) is a state iff:

\[\forall q \in K, \; \exists\, C \in \sigma(q) : C \subseteq K\]

When each item has exactly one clause, \(\sigma\) reduces to a surmise relation (the quasi-ordinal case; ordinal if also discriminative).

Competence-Based KST

The CbKST framework separates skills from items:

  • \(S\): a set of skills

  • \(\mu: Q \to 2^S\): for each item, the skills required to solve it

  • A competence structure \(\mathcal{C}\) on \(S\); it may, in particular, consist of the downsets of a skill prerequisite quasi-order

The problem function maps a competence state \(C \subseteq S\) to the set of solvable items:

\[p(C) = \{q \in Q \mid \mu(q) \subseteq C\}\]

The knowledge structure is:

\[\mathcal{K} = \{p(C) \mid C \in \mathcal{C}\}\]

Item requirements must be nonempty so that \(p(\emptyset)=\emptyset\). CompetenceModel accepts an explicit competence structure for this conjunctive model. SkillMultiMap additionally supports alternative competencies for deriving performance structures; see the derivation guide for the distinct assumptions of effective-fringe methods.

References

  • Doignon, J.-P., & Falmagne, J.-C. (1999). Knowledge Spaces. Springer-Verlag.

  • Falmagne, J.-C., & Doignon, J.-P. (2011). Learning Spaces. Springer-Verlag.