The QUERY Algorithm

The QUERY algorithm (Koppen & Doignon, 1990) constructs a learning space by systematically querying an expert.

Query format

Each query has the form:

If a student fails all items in \(A\), will they also fail item \(q\)?

A positive answer means: mastering \(q\) requires mastering at least one item in \(A\).

Block 1: Surmise relation discovery

Block 1 uses pair queries (\(|A| = 1\)) to discover the prerequisite relation.

Phase 0: Qmax minimality test

For each item \(q\), ask: \(Q \setminus \{q\} \to q\)?

If NO, by negative monotonicity, no subset of \(Q \setminus \{q\}\) can imply \(q\). Therefore \(q\) is minimal and all pair queries \((r, q)\) can be skipped.

Cost: \(|Q|\) group queries to potentially save \(O(|Q|^2)\) pair queries.

Phases 1–3: Pair queries with pruning

For each non-minimal \(q\), ask pair queries \((r, q)\) with three optimizations:

  • Transitivity: if \((r, q)\) is already in the transitive closure, skip.

  • Antisymmetry: if \((q, r)\) is in the closure, then \((r, q)\) is impossible.

  • Bottom-up construction: start from minimal items and build outward.

Block 2+: Learning space refinement

Block \(n\) tests group queries with \(|A| = n\) to refine the ordinal space \(L_1\) into a learning space.

Inference mechanisms

For each candidate query \((A, q)\):

  1. Negative monotonicity: if \(q\) is globally minimal (from Qmax), then \((A, q) = \text{NO}\) for any \(A\) not containing \(q\).

  2. Positive monotonicity: if there exists a proper subset \(B \subset A\) such that \((B, q) = \text{YES}\) (from a previous block), then \((A, q) = \text{YES}\).

Queries settled by neither rule are posed to the expert.

State removal and the admissibility test

A positive answer \((A, q) = \text{YES}\) calls for removing \(D_{\mathcal{L}}(A, q) = \{K \in \mathcal{L} \mid q \in K,\, A \cap K = \emptyset\}\) — the states that contain \(q\) but are disjoint from \(A\), violating the discovered prerequisite. The removal always preserves union closure, but it leaves a learning space only when no almost-hanging state relies on a removed state (Falmagne & Doignon 2011, Theorem 16.1.6); such a removal is admissible.

The pending table

An inadmissible removal is not discarded and not negated: the positive answer keeps pending status and is re-tested after every later successful removal — a removal elsewhere can make it admissible — until the collection of states stabilizes (Falmagne & Doignon 2011, Section 16.1, Example 16.1.13). With queries of every antecedent size and an error-free expert whose latent structure is a learning space, the stabilized result is exactly the latent space (Theorem 16.1.16); pending entries then always drain. Under depth truncation, entries still pending at the end are reported (pending_unapplied): the returned structure is a learning space consistent with the applied answers but not with the pending ones.

The legacy algorithm="one_pass" reproduces the naive Algorithm 16.1.10 instead: an inadmissible positive is recorded as a structural negative without consulting the expert and never revisited. Example 16.1.12(a) of the book shows how this can suppress a truthful answer permanently, so the one-pass result can strictly contain the latent space and depend on the item order.

Generalization

Block \(n\) for any \(n \geq 2\) follows the same pattern. The library supports arbitrary antecedent sizes via max_antecedent_size.

References

  • Koppen, M., & Doignon, J.-P. (1990). How to build a knowledge space by querying an expert. Journal of Mathematical Psychology, 34, 311–331.

  • Falmagne, J.-C., & Doignon, J.-P. (2011). Learning Spaces, Chs. 15–16.