Querying Experts

The QUERY algorithm (Koppen & Doignon, 1990) derives a knowledge structure by asking an expert prerequisite questions.

How it works

The algorithm asks questions of the form:

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

It proceeds in phases:

  1. Block 1: Pair queries (\(|A| = 1\)) to discover the surmise relation.

  2. Block 2+: Group queries (\(|A| \geq 2\)) to refine the structure into a learning space.

Two inference mechanisms reduce the number of questions:

  • Negative monotonicity: If \(q\) is minimal, no set implies \(q\).

  • Positive monotonicity: If a subset of \(A\) already implies \(q\), so does \(A\).

A positive answer removes the states that contradict it. When that removal would break well-gradedness (Falmagne & Doignon 2011, Theorem 16.1.6), the answer is not discarded: it is buffered with pending status and re-tested after every later removal, until the structure stabilizes (the pending-table mechanism of Section 16.1). At full elicitation depth this carries the recovery guarantee of Theorem 16.1.16: an error-free expert whose latent structure is a learning space is recovered exactly. Positives still pending at the end are reported in result.pending_unapplied.

Basic usage

from knowledgespaces import run_query
from knowledgespaces.query import CallbackExpert

def my_expert(antecedent, consequent):
    # Your logic: human input, LLM call, database lookup, etc.
    known = {("add", "sub"), ("sub", "mul"), ("mul", "div")}
    return any((a, consequent) in known for a in antecedent)

expert = CallbackExpert(my_expert)
result = run_query(["add", "sub", "mul", "div"], expert)

print(result.is_learning_space)
print(result.total_expert_queries)

Controlling the algorithm

# Without Qmax minimality test (fewer group queries, more pair queries)
result = run_query(items, expert, use_qmax=False)

# With Block 3 (group queries of size 3)
result = run_query(items, expert, max_antecedent_size=3)

# Full procedure: antecedents up to |Q| - 1 (recovery guarantee,
# Falmagne & Doignon 2011, Thm 16.1.16). Any smaller depth emits a
# TruncatedQueryWarning, because the result is then a depth-limited
# approximation of the latent structure.
result = run_query(items, expert, max_antecedent_size=len(items) - 1)

# Legacy one-pass scheme (Algorithm 16.1.10): blocked positives are
# recorded as structural negatives without consulting the expert and
# never revisited. Kept for comparison; it can return a strict
# superset of the latent space even at full depth.
result = run_query(items, expert, algorithm="one_pass")

The interactive CLI (ks query) additionally defaults to --no-qmax: the Qmax opening asks group queries with maximal antecedents, which are the most demanding for human experts (Falmagne & Doignon 2011, §15.4); use_qmax=True remains the API default, aimed at simulated experts.

Inspecting results

# The derived structure
for state in result.structure:
    print(set(state))

# Block 1 details
print(result.block1.relation)       # direct prerequisites found
print(result.block1.minimal_global)  # items certified minimal by Qmax
print(result.block1.stats)           # query counts

# Full query log
for entry in result.block1.log:
    print(f"{entry.query} → {entry.answer} ({entry.source.name})")