Problem functions on arbitrary competence families

ProblemFunction evaluates a SkillMap or SkillMultiMap on a supplied family of competence states. It returns the exact performance image, a table retaining the original rows, equivalence classes, and inverse reports. It complements CompetenceModel, whose effective and collective fringe methods retain their conjunctive-model assumptions.

For a skill multimap, an item is solvable when at least one of its alternative competencies is contained in the competence state. All skills within that alternative are required:

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

These are deterministic finite-set operations. They do not infer latent skills from noisy responses and do not require a learning space, an ordinal competence structure, or either endpoint in the supplied family.

Keep rows, column order and identities

from knowledgespaces import SetFamily, SkillMultiMap
from knowledgespaces.derivation import ProblemFunction

multimap = SkillMultiMap(
    items=["42", "10"],
    skills=["x", "y", "z"],
    mapping={"42": [{"x"}, {"y"}], "10": [{"y", "z"}]},
)
problem = ProblemFunction(
    multimap,
    [{"y", "z"}, set(), {"x"}, {"y", "z"}, {"z"}],
    skills=["z", "y", "x"],
    competence_ids=["u3", "u1", "u9", "u7", "u0"],
)
table = problem.to_matrix()
assert table.tolist() == [
    [1, 1, 0, 1, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 1, 1, 0],
    [1, 1, 0, 1, 1],
    [1, 0, 0, 0, 0],
]
competence_matrix = table[:, :len(problem.skills)]
performance_matrix = table[:, len(problem.skills):]
assert problem.items == ("42", "10")
assert problem.equivalence_classes[0].competence_ids == ("u3", "u7")
assert problem.equivalence_classes[0].row_indices == (0, 3)

The column labels are problem.skills + problem.items: separate skill and item blocks, even when their labels overlap. Numeric item identifiers should be supplied as strings; they are retained rather than renumbered. The performance matrix keeps all five input rows, including duplicate competence states and duplicate performance images. Its corresponding row IDs are problem.competence_ids. Equivalence classes partition these rows by equal performance; they are ordered by first occurrence.

In contrast, problem.image is a SetFamily: a mathematical family contains each distinct performance state once. problem.competence_family similarly deduplicates the input states without inserting any others. Supplying a SetFamily, KnowledgeStructure, set or frozenset orders its members by cardinality and then lexicographically. Supply a sequence to preserve an existing row order. Unique row IDs default to C1, C2, and so on.

Exact preimages and positive coverage

from knowledgespaces import SkillMap

same_requirement = SkillMap(["a", "b"], ["x", "y"], {"a": {"x"}, "b": {"x"}})
mapped = ProblemFunction(same_requirement, [{"x", "y"}, {"x"}, {"x"}, set()])
exact = mapped.inverse([{"a"}, {"a", "b"}], performance_ids=["only-a", "both"])
assert exact.rows[0].competence_states == ()  # {a} is unattainable
assert exact.rows[1].row_indices == (0, 1, 2)
assert exact.rows[1].minimal_states == (frozenset({"x"}),)

positive = mapped.inverse([{"a"}], exact=False)
assert positive.rows[0].minimal_states == (frozenset({"x"}),)

The default exact=True requests all admissible competence rows with p(C) == K. With exact=False, it requests K <= p(C), so solving additional items is allowed. This is the positive-mastery interpretation used by CbKST’s cbkst_perf2comp and cbkst_simple_perf2comp.

Each report row includes the requested performance and ID, matching competence row indices/IDs/states, and their distinct inclusion-minimal states. Minimal does not mean smallest cardinality. Minima are taken within the supplied admissible family. An empty tuple means no compatible state; a tuple containing frozenset() is a valid empty-skill solution.

report.compatible_family collects all compatible states across report rows. report.minimal_family collects the minima of each row; it does not minimize the aggregate a second time. Requested order, duplicate patterns, and unattainable performances remain visible in report.rows.

Explicit endpoints and CbKST correspondence

from knowledgespaces import KnowledgeStructure

free_item = SkillMultiMap(["a", "b"], ["x", "y"], {"a": [set()], "b": [{"x"}]})
restricted = ProblemFunction(free_item, SetFamily(["x", "y"], [{"y"}]))
assert restricted.image == SetFamily(["a", "b"], [{"a"}])
# p(empty) contains a; neither empty nor {a,b} is an attained image here.

multi = SkillMultiMap(["a", "b"], ["x", "y"], {"a": [{"x"}], "b": [{"x"}, {"y"}]})
report = ProblemFunction(multi).inverse(exact=False)
# CbKST::cbkst_competencestructure constructs this positive-minimum family
# and adds the empty and full skill sets as structure endpoints:
cbkst_structure = KnowledgeStructure(report.skills, report.minimal_family.sets)
assert cbkst_structure.states == {
    frozenset(), frozenset({"x"}), frozenset({"y"}), frozenset({"x", "y"})
}

image.to_knowledge_structure() validates that the exact image already has both endpoints and a nonempty item domain. It raises otherwise. By contrast, the explicit KnowledgeStructure(domain, states) constructor adds the endpoints. The latter is appropriate for the displayed CbKST construction, but its output must not be described as an exact image or as all preimages.

CbKST 0.1-1’s cbkst_performancestructure can insert unattained endpoint states. ProblemFunction.image deliberately preserves the exact image. Native comparisons cover ordinary maps, alternative competencies, repeated rows, numeric string IDs, empty competencies, and restricted families; they distinguish this endpoint difference rather than treating it as numerical equality. MATLAB’s skillmap correspondence is the row-preserving competence/performance matrices with explicit item identities; MATLAB was not executed for this comparison.

For one inverse query without a precomputed problem-function table, compatible_competencies and minimal_competencies also accept a SetFamily as competence_structure. Without that argument, minimal_competencies constructs minimal unions of competencies and can avoid a full powerset.

Enumeration limits

Omitting competence_states enumerates all skill subsets; passing an empty sequence supplies no competence states. Similarly, inverse() with no performance family enumerates all item subsets, whereas inverse([]) has no requested rows. Both operations use max_states=100_000 by default and raise before enumerating a larger powerset. Supply explicit families when the full domain is too large. These guards never return partial results.

The cost of evaluating a supplied family scales with the rows and competency alternatives. Inverse reports additionally scan those rows for every requested performance and compare compatible states to find their minima. These methods are intended for finite explicit families; they do not claim polynomial scaling in the size of an implicitly represented powerset.

References: Falmagne and Doignon (2011), Learning Spaces, Chapter 6; the manuals and sources of CbKST 0.1-1 for cbkst_problemfunction, cbkst_performancestructure, cbkst_competencestructure and cbkst_perf2comp; KST-toolbox MATLAB, skillmap, revision 8b53ecd18f57ec5b8788522d8ebaa12019082330.