Competence-Based KST (CbKST)

CbKST derives a knowledge structure from a skill map — the mapping from items to the skills required to solve them.

The model

Given:

  • A set of items \(Q\) (problems/questions)

  • A set of skills \(S\) (competencies)

  • A skill map \(\mu: Q \to 2^S\) (each item requires a set of skills)

  • A prerequisite relation on skills

The problem function maps a competence state \(C \subseteq S\) to the set of solvable items (an item is solvable iff all its required skills are mastered — the conjunctive model):

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

The knowledge structure is the image of all valid competence states:

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

Note. With a conjunctive skill map, \(\mathcal{K}\) is not guaranteed to be union-closed, so the result is a knowledge structure but not necessarily a knowledge space. Check with is_knowledge_space.

Skill multimaps: alternative competencies

A skill multimap assigns to each item one or more competencies — alternative skill sets, each sufficient on its own (Doignon & Falmagne 1999, Ch. 4): conjunctive within a competency, disjunctive across competencies. The problem function becomes

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

Use SkillMultiMap with derive_knowledge_structure, or the one-call structure_from_skill_multimap:

from knowledgespaces import structure_from_skill_multimap

# q2 is solvable with s1 alone OR with s2 and s3 together
ks = structure_from_skill_multimap(
    {"q1": [["s1"]], "q2": [["s1"], ["s2", "s3"]]},
)

The one-competency case coincides with structure_from_skill_map; the extended skill function that delineates the 13-state structure \(K_2\) of the accompanying article is a worked example in the replication material.

Usage

High-level API

import knowledgespaces as ks

structure = ks.structure_from_skill_map(
    skill_map={
        "q1": ["s_add"],
        "q2": ["s_add", "s_carry"],
        "q3": ["s_mul", "s_add"],
    },
    skill_prerequisites=[("s_add", "s_carry")],
)

Low-level API

from knowledgespaces import SkillMap, derive_knowledge_structure
from knowledgespaces.structures import SurmiseRelation

skill_map = SkillMap(
    items=["q1", "q2", "q3"],
    skills=["s_add", "s_carry", "s_mul"],
    mapping={
        "q1": {"s_add"},
        "q2": {"s_add", "s_carry"},
        "q3": {"s_mul", "s_add"},
    },
)

skill_rel = SurmiseRelation(
    ["s_add", "s_carry", "s_mul"],
    [("s_add", "s_carry")],
)

result = derive_knowledge_structure(skill_map, skill_rel)

print(result.competence_structure.n_states)
print(result.knowledge_structure.n_states)
print(result.knowledge_structure.is_knowledge_space)

# mapping: competence state -> induced knowledge state
for comp_state, know_state in result.mapping.items():
    print(set(comp_state), "->", set(know_state))

Skill-to-item conversion

You can also derive the item prerequisite relation from the skill map. Item \(p\) precedes \(q\) iff every skill required by \(p\) is either required by \(q\) or is a prerequisite of one:

\[\mathrm{covers}(q) = \mu(q) \,\cup\, \{s : \exists\, t \in \mu(q),\ (s, t) \in \mathord{\preceq}\} \qquad p \prec q \iff \mu(p) \subseteq \mathrm{covers}(q)\]
from knowledgespaces import skill_to_item_relation

item_rel = skill_to_item_relation(skill_map, skill_rel)
for a, b in item_rel:
    print(f"{a} → {b}")

Alternative: surmise functions

When an item can be solved through different alternative prerequisite sets (the disjunctive case), use a surmise function instead — see space_from_surmise_function in structures.

Deriving structures from data: IITA

Inductive item tree analysis (IITA) derives a surmise relation from binary response data. For each ordered item pair \((i, j)\) the counterexample count \(b_{ij}\) tallies the respondents who solve \(j\) and fail \(i\); small counts support the implication that mastery of \(j\) entails mastery of \(i\). Candidate quasi orders enter inductively by increasing counterexample count, and the candidate minimizing the diff measure (mean squared deviation between observed and expected counterexamples) is selected. Three classical variants are available: original (Schrepp, 2003), corrected, and minimized corrected (Sargin & Ünlü, 2009), the default.

import numpy as np
from knowledgespaces.derivation import iita
from knowledgespaces.estimation import ResponseMatrix

data = ResponseMatrix(
    items=["a", "b", "c"],
    patterns=np.array([[1, 1, 1], [1, 1, 0], [1, 0, 0], [0, 0, 0]]),
    counts=np.array([40.0, 30.0, 20.0, 10.0]),
)
result = iita(data)                    # version="minimized" by default
print(sorted(result.implications))     # [('a', 'b'), ('a', 'c'), ('b', 'c')]
print(result.error_rate)
print(result.diff)                     # fit of every candidate

# Convert the selected relation into a knowledge space:
from knowledgespaces import KnowledgeStructure
space = KnowledgeStructure.from_surmise_relation(
    result.relation.transitive_closure()
)

The implementation mirrors the sample-level algorithms of the R package DAKS (Ünlü & Sargin, 2010) and is cross-validated against it in the test suite. population_iita, iita_variance, population_iita_variance and iita_z_test also provide population quantities and delta-method inference. See IITA inference for their fixed-relation assumptions, paired comparisons and limits at nonregular zero-discrepancy nulls.

Effective fringes and observable learning

For an explicit competence structure and a conjunctive skill function, CompetenceModel implements the definitions of Stefanutti & de Chiusole (2017), Sections 3-6. The supplied competence structure need not be generated by a quasi-order.

from knowledgespaces import KnowledgeStructure, SurmiseRelation
from knowledgespaces.derivation import CompetenceModel, SkillMap

skills = ["s", "t", "u"]
C = KnowledgeStructure.from_surmise_relation(SurmiseRelation(skills, []))
mu = SkillMap(["a", "b", "c", "d"], skills,
              {"a": ["s"], "b": ["s", "t"],
               "c": ["s", "u"], "d": ["t", "u"]})
model = CompetenceModel(C, mu)
assert model.effective_outer_fringe(set()) == {"s"}
assert model.collective_outer_fringe(set()) == {"s"}

An effective outer fringe contains skills, each available from the current competence state and capable of increasing its delineated performance state. Acquiring one skill may unlock several items. It therefore differs from the outer fringe of an item-level knowledge state.

compatible_states(performance) returns all competence states that could delineate the supplied performance state. equivalence_class(C) returns the class of a given competence state. collective_outer_fringe takes a performance state and intersects the outer fringes of all compatible competence states. It identifies skills that are available and effective throughout that equivalence class, possibly a strict subset of an individual’s effective fringe.

floor(C) is the intersection of its class; it may lie outside the competence structure. is_floor_inclusive checks this condition for all classes. floor_fringe(C) requires floor-inclusiveness and computes the outer fringe of floor(C) in the family of floors. floors returns the exact family as a frozenset, without inserting unused skills.

Keep three quantities distinct: floor_fringe(C), effective_outer_fringe(floor(C)) in the original competence structure, and collective_outer_fringe(mu.problem_function(C)). Floor-inclusiveness and union closure imply equality of the latter two (Proposition 6), but are insufficient to identify them with the fringe in the family of floors. For example, this floor-inclusive learning space uses every declared skill:

C = KnowledgeStructure("abcd", ["", "b", "c", "bc", "ac", "ab", "abc", "abcd"])
mu = SkillMap("123", "abcd", {"1": "a", "2": "b", "3": "cd"})
model = CompetenceModel(C, mu)
assert C.is_learning_space and model.is_floor_inclusive
assert not model.is_compatible
assert model.floor_fringe("ac") == set()
assert model.effective_outer_fringe(model.floor("ac")) == {"b"}
assert model.collective_outer_fringe({"1"}) == {"b"}

Here adding b to ac is effective and admissible, but abc is not a floor: its class has floor ab. In particular, we do not apply the identification in Proposition 7 and Corollary 1 to an arbitrary restricted competence family solely on the basis of floor-inclusiveness.

A sufficient condition for equality of all three quantities is model.is_compatible: the competence structure is union-closed and each item’s conjunctive requirement set is an admissible state (Definition 5). To see why, put \(U(T)=\bigcup_{q\in p(T)}\mu(q)\). Compatibility makes \(U(T)\) admissible; it is contained in every state with performance \(p(T)\) and has that same performance. Hence \(U(T)=\operatorname{floor}(T)\). If adding skill \(s\) to a floor \(F\) is effective, then \(U(F\cup\{s\})\) contains all of \(F\) and the newly required skill \(s\), so it equals \(F\cup\{s\}\): the enlarged state is itself a floor. Conversely, two distinct admissible floors cannot have the same performance. Thus the floor-family fringe equals the effective fringe of the floor. Union closure then makes each such effective addition available throughout its equivalence class, giving the collective fringe. This is a sufficient condition, not a claim that compatibility is necessary.

mu.atomic_items() and mu.is_exclusive implement Definitions 3 and 4. The exclusiveness/well-graded-floor equivalence (Proposition 10) requires a competence space compatible with the skill function; use model.is_compatible to check that hypothesis. No corresponding theorem is asserted for general skill multimaps. Published Examples 1, 3, 5, 7, and 8 are reproduced in the test suite.

Delineating a KnowledgeStructure now rejects items with empty skill requirements: otherwise the empty performance state is unattainable and adding it would change the image of the problem function. Low-level skill maps still represent empty requirements for import and inspection.

ITA and IITA inference

The classical methods guide covers threshold ITA, population IITA and delta-method uncertainty for fixed relations, including paired comparisons and nonregular zero-discrepancy nulls.