Toward Question-Asking Machines: The Logic of Questions and the Inquiry Calculus

Kevin H. KnuthAISTATS 2005

Introduction

For over a century, mathematical logic has focused almost exclusively on the logic of statements—the formalization of facts and their implications. While this has powered the digital revolution, it leaves a significant gap in artificial intelligence: the logic of questions. Current AI systems excel at processing provided data but often lack the "active learning" capabilities required to identify missing information and formulate the most efficient queries to fill those gaps. This paper introduces the "Inquiry Calculus," a mathematical framework that treats questions as formal objects within a lattice structure, providing a rigorous foundation for how machines can decide what they need to ask.

Defining the Question Space

The core innovation of this work is the formal definition of a question. Drawing on the work of Richard Cox, the author defines a question as the set of all logical statements that answer it. For example, the question "Is it raining?" is defined by the set of statements { "It is raining", "It is not raining" }.

By organizing these sets, we can construct a hierarchy based on the relation of "answering." If the set of answers for question A is a subset of the answers for question B, then A is said to answer B. This ordering relation allows for the construction of a lattice.

Lattice Construction

While statements typically form a Boolean lattice (where every statement has a negation), the space of questions forms a free distributive lattice. This distinction is crucial: in the logic of questions, there is no natural "negation" (there is no such thing as a "NOT-Question").

The free distributive lattice Q3 representing the space of questions generated by three elementary statements.

As shown in the lattice $\mathcal{Q}_3$, the structure becomes significantly more complex than the statement lattices from which they are derived. This complexity reflects the myriad ways information can be partitioned and combined to resolve uncertainty.

The Inquiry Calculus

To move from a static structure to a functional calculus, the author derives a measure called relevance, denoted as $d(I|Q)$. This measure quantifies the degree to which a question $Q$ resolves a central issue $I$.

To ensure this measure is objective and consistent, it must obey the algebraic properties of the lattice, such as associativity, commutativity, and distributivity. By solving the functional equations arising from these constraints, the author derives the "Sum Rule" and "Product Rule" for questions, mirroring the foundations of probability theory.

The algebraic properties and operations that form the consistent basis for the Inquiry Calculus.

These rules lead to a "Bayes’ Theorem Analogue" for questions: $$d(Y | X \wedge Q) = \frac{d(Y|Q)d(X | Y \wedge Q)}{d(X|Q)}$$ This formula allows an agent to calculate the relevance of a new question $Y$ given that it has already asked (or intends to ask) question $X$.

Information Theory as a Logical Consequence

One of the paper's most significant results is the derivation of Information Theory from first principles. The author proves that Shannon Entropy and Hartley Entropy are not merely useful heuristics; they are the unique measures of relevance that satisfy the consistency requirements of the Inquiry Calculus. This suggests that mutual information and joint entropy are natural consequences of the disjunction and conjunction of questions within the lattice, providing a unified framework for inference and inquiry.

Limitations and Future Directions

While the Inquiry Calculus provides a powerful theoretical tool, practical implementation faces challenges. The size of a free distributive lattice grows at an enormous rate (governed by Dedekind numbers), which may lead to computational bottlenecks in large hypothesis spaces. Future work will focus on integrating this calculus into standard Bayesian Networks and exploring how these formal questions can be mapped to real-time robotic decision-making and collaborative human-robot interaction.

Summary updated

BibTeX
@inproceedings{knuth2005toward,
  author = {Kevin H. Knuth},
  title = {{Toward Question-Asking Machines: The Logic of Questions and the Inquiry Calculus}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2005},
}
Figure