Attributions, families and operations on spaces¶
Attribution separates a general prerequisite description from a canonical
SurmiseFunction. SetFamily represents intermediate sets without adding
the empty/full states required of a KnowledgeStructure. Both are pure
Python objects and preserve their input meaning.
From an attribution to a surmise function¶
An attribution assigns a nonempty family of clauses to every item; an empty clause is permitted. A surmise function additionally requires self-inclusion, refinement and incomparable clauses (Falmagne & Doignon, 2011, Definition 5.1.2).
from knowledgespaces import Attribution
attribution = Attribution("abc", {"a": ["b"], "b": ["a"], "c": [""]})
assert not attribution.is_surmise_function
assert "ab" in attribution
assert "a" not in attribution
function = attribution.to_surmise_function()
assert function.clauses_for("a") == {frozenset("ab")}
space = function.to_knowledge_space()
Membership implements Equation (5.2): K is a state iff every item q in K
has some clause contained in K. The example describes exactly
∅, {c}, {a,b}, {a,b,c}. Cycles are legal here: equivalent items need not
be learnable one at a time, and a knowledge space need not be a learning space.
to_surmise_function() searches for all minimal states containing each
item. It adds prerequisites only when an included item lacks a satisfied
clause, explores alternatives, and discards supersets of completed minimal
states. It preserves the space defined by the attribution; it does not
simply take the union closure of incomplete clauses. max_candidates
bounds distinct candidate sets in each item-rooted search. Search may be
exponential, but a full state powerset is not an intermediate requirement.
Attribution.from_relation(domain, pairs) accepts any binary relation,
including nonreflexive generators, using (a,b) for “a required for b”.
Attribution.from_surmise_function(function) preserves canonical clauses.
expand(larger_domain) adds unrestricted items; canonicalizing afterwards
corresponds to expansion followed by closure. SurmiseFunction.expand
does the canonical expansion directly.
Families and closures¶
from knowledgespaces import SetFamily
family = SetFamily("abc", ["a", "b"])
assert "" not in family and "abc" not in family
closed = family.union_closure()
assert closed.sets == {frozenset(s) for s in ["", "a", "b", "ab"]}
The declared domain may contain unused items. Empty families and empty
domains are legal. minimal_sets and maximal_sets use inclusion, not
cardinality. union_with, intersection_with and difference operate
on members of families with the same domain; they do not close the result.
dual complements each member relative to the domain, and projection
restricts each member to a subdomain.
union_closure includes the empty union ∅; intersection_closure includes
the empty intersection Q. The latter closes only under intersection.
The kstMatrix::kmclosure(..., closure="intersection") option closes under
both union and intersection, so reproducing it requires both operations.
Use max_sets to limit output explicitly; an exceeded limit raises.
to_knowledge_structure() requires the nonempty domain and both endpoints
already in the family. to_knowledge_base() explicitly interprets members
as union generators, removes redundant rows and requires their union to
cover the domain. It does not enumerate their span.
Combining compact representations¶
from knowledgespaces import KnowledgeBase
left = KnowledgeBase("abc", ["a", "ab", "abc"])
right = KnowledgeBase("abc", ["b", "ab", "abc"])
join = left.join(right)
meet = left.intersection_with(right)
assert join.to_knowledge_space().n_states == 5
assert meet.to_knowledge_space().n_states == 3
KnowledgeBase and SurmiseFunction both provide:
Method |
Meaning in the inclusion order of knowledge spaces |
|---|---|
|
Smallest knowledge space containing both spaces |
|
States present in both spaces |
|
Nonempty projection, computed from generators |
|
Discriminative quotient and a representative-to-class mapping |
Joining merges/reduces bases. Intersection combines item clauses and
canonicalizes their conjunction. It is not the intersection of the two
base families. These methods avoid generating either full state span.
In contrast, KnowledgeStructure.union_with is the raw union of state
families; call union_closure explicitly when a space is required.
The names follow knowledge-space inclusion consistently. kstMatrix names
the corresponding surmise-function operations in the reversed representation
order (kmunion corresponds to our space intersection, kmintersection
to our join). Matching method names without matching that convention would
reverse the intended operation.
Quotient representatives use the lexicographically first original item in
each equivalence class. The returned mapping preserves the original labels.
SetFamily and KnowledgeStructure also expose quotient().
Refining equivalent items¶
family = SetFamily("abcd", ["a", "b", "abcd"])
refining_base = KnowledgeBase("cd", ["c", "cd"])
refined = family.refine(refining_base)
assert refined.sets == {frozenset(s) for s in ["a", "b", "abc", "abcd"]}
The refining domain D must lie within a single equivalence class: its items
co-occur in every original member. For every member containing D, replace D
in turn by each refining base set. Members disjoint from D stay unchanged.
This implements the family replacement described by kstMatrix kmrefine,
with explicit handling of multiple affected rows and subsets of a notion.
The replacement family need not contain Q or be union-closed.
KnowledgeBase.refine instead treats the replacement rows as generators
and returns their reduced base. This distinction is explicit; no structure
axioms are silently inserted. Refinement here is a user-specified structural
operation, not automatic empirical model selection or the assessment-driven
procedure in Chapter 15 of Learning Spaces.
The tests retain counterexamples to kstMatrix 3.0-0’s multiple-row reshaping and reversed subset check; they validate the declared replacement rule independently. They do not claim every kstMatrix option has been reproduced.
See I/O for general-clause CSV/JSON, family JSON and multimap JSON.
The executable cookbook/09_attribution_and_algebra.py combines these workflows.
Primary definitions: Falmagne & Doignon (2011), Learning Spaces, Chapters 3 and 5. Software comparison: kstMatrix 3.0-0 archived source and freshly executed functions.