Knowledge Representation
Motivation
Knowledge representation (KR) is the study of how to encode what a system knows so that it can reason: derive new facts, answer queries, and act on its conclusions (Russell and Norvig 2020). A neural network represents knowledge implicitly — distributed across millions of weights, accessible only through forward passes — while a knowledge representation makes the same knowledge explicit, structured, and inspectable.
Why bother, given that modern models work without explicit representations? Three reasons recur across the history of AI:
- Reasoning that does not appear in the training distribution. A model can memorize that Boston is in Massachusetts and that Massachusetts is in the United States; whether it reliably concludes that Boston is in the United States is a separate question. A KR with a transitivity rule does it once and forever.
- Verifiability. Symbolic facts and rules can be inspected, edited, and audited. A bug in a logical rule is localizable; a bug in a weight matrix is not.
- Compositionality. A small set of facts and rules generates a large set of consequences. The size of the representation grows with what is primitive, not with what is derivable.
The cost is that someone — or some pipeline — must produce the representation in the first place, and natural language does not come in this form. Most of the engineering question in modern KR is how to bridge that gap.
The Levels of Representation
KR formalisms differ in how much structure they impose. The classical levels, from least to most:
| Level | Atomic unit | Example |
|---|---|---|
| Propositional logic | Truth-valued atom | \(\text{Raining} \Rightarrow \text{WetGround}\) |
| First-order logic | Predicates with variables | \(\forall x.\, \text{Bird}(x) \Rightarrow \text{Animal}(x)\) |
| Description logics | Concepts and roles | \(\text{Mother} \equiv \text{Female} \sqcap \exists \text{hasChild}.\top\) |
| Knowledge graphs | Entity–relation triples | (Boston, locatedIn, Massachusetts) |
| Frames / objects | Slots with defaults | Bird = {flies: true (default), feathered: true} |
| Semantic networks | Labeled-edge graph | Sparrow –is-a→ Bird –is-a→ Animal |
These are not strictly ordered: a knowledge graph can be reinterpreted as a fragment of first-order logic, frames have description-logic encodings, and propositional logic is a degenerate case of all of them. What changes across the table is the trade-off between expressiveness (what you can say) and tractability (how fast you can reason about it).
What Counts as a Representation
A KR formalism specifies three things:
- Syntax. What symbols are allowed and how they combine into well-formed expressions.
- Semantics. What those expressions mean — typically given by an interpretation that assigns a value or a referent to each symbol, in the style of logical entailment.
- Proof theory. What inferences are allowed: which expressions can be derived from which others, by which rules.
A representation without semantics is just data; a representation without a proof theory is inert. The reasoning machinery from earlier in the course — resolution, forward chaining, backward chaining — supplies the proof theory for first-order representations.
Examples of Representations
Propositional knowledge base
Suppose we want to encode a fire alarm. The facts are atoms; the rules are implications.
Smoke ∧ Heat ⇒ Fire
Fire ⇒ Alarm
Smoke
HeatA propositional reasoner derives \(\text{Fire}\) then \(\text{Alarm}\). The representation is small and the reasoning is decidable, but every distinct alarm or sensor must be named with a distinct atom — there is no way to say “every smoke detector behaves this way.”
First-order knowledge base
Lifting to first-order logic introduces quantifiers and predicates:
\[\forall x.\, \text{Smoke}(x) \land \text{Heat}(x) \Rightarrow \text{Fire}(x).\]
One rule now covers every room \(x\). The cost is that first-order entailment is only semi-decidable: a complete prover can refute any false claim, but might not terminate on every true one.
Semantic network
A semantic network is a labeled graph whose nodes are concepts or individuals and whose edges are typed relations.
Sparrow ──is-a──▶ Bird ──is-a──▶ Animal
│ │
│ └──can──▶ Fly
└──has-color──▶ BrownSemantic networks were among the earliest AI representations. They make taxonomic reasoning visually obvious: a sparrow inherits “can fly” from Bird and “is an animal” from the transitive closure of is-a. The risk is that an unprincipled graph cannot say why a particular edge type behaves the way it does — a clean semantic-network formalism is, in modern terms, a description logic or a knowledge graph with explicit rules.
Frame
A frame represents a concept as a structured object with named slots, defaults, and constraints:
Frame: Bird
is-a: Animal
slots:
flies : Boolean default = true
has-feathers : Boolean default = true
diet : enum {seeds, insects, fish, ...}Subframes inherit slots and can override defaults — Frame: Penguin would set flies = false. Frames added two ideas that purely logical representations lacked: structured prototypes and default reasoning (assume the default unless the facts say otherwise).
Description logic concept
Description logics carve out a decidable fragment of first-order logic by trading away unrestricted quantification for object-centric expressions:
\[\text{Mother} \equiv \text{Female} \sqcap \exists \text{hasChild}.\text{Person}.\]
The class “Mother” is defined as “Female who has at least one Person as a child.” Description-logic reasoners can decide subsumption (is class \(A\) a subclass of class \(B\)?) and instance checking in polynomial or exponential time depending on the dialect. This is the formal underpinning of ontologies and the Web Ontology Language (OWL).
The Symbol Grounding Problem
Every representation eventually bottoms out at primitive symbols — Bird, Boston, hasChild — whose meaning is given by their connections to other symbols. But if all symbols are defined only in terms of other symbols, where does meaning come from? This is the symbol grounding problem: linking the formal tokens of a representation to the world they describe.
Classical KR mostly punted on this question, treating grounding as the responsibility of whoever connected the KR to sensors or natural-language input. Modern systems address it implicitly: a vision-language model learns embeddings that anchor textual symbols to perceptual features, and an LLM that reads documents learns connections that approximate the relational structure of the world. Whether these embeddings constitute genuine grounding remains debated.
The Frame Problem
Once you have rules, a different problem appears: what doesn’t change when an action happens? If I move a book from one shelf to another, the book’s title, color, and weight remain the same; so does the temperature of the room and the position of every other object in the world. Listing all the things that don’t change after every action — the frame problem (McCarthy and Hayes 1969) — exploded the size of early action representations.
Modern formalisms (situation calculus with successor-state axioms, STRIPS-style operators) address the frame problem by defaulting to no change and listing only what does change. The frame problem remains a useful diagnostic for any representation that has to support actions: how does it know what stays the same?
Expressiveness vs. Tractability
The central design tension is sharp:
- Propositional logic is decidable (SAT) but NP-complete in the worst case and inexpressive: no quantification.
- First-order logic is highly expressive but only semi-decidable.
- Description logics sit on a designed Pareto frontier: each dialect picks a decidable fragment with a known complexity (e.g., \(\mathcal{ALC}\) is ExpTime-complete; \(\mathcal{EL}\) is PTime).
- Datalog is first-order Horn logic without function symbols — Turing-incomplete by design, but PTime evaluable and used in modern deductive databases.
The history of KR can be read as a series of trades along this curve. Early systems aimed at “all of logic” and broke on undecidability; later systems retreated to designed fragments where reasoning is fast and consequences are bounded.
Where Modern Systems Sit
Contemporary AI is increasingly built from combinations of representations:
- Knowledge graphs scale the semantic-network idea to billions of triples, drawn from web-scale extraction pipelines and used to ground search and question answering.
- Ontologies add a description-logic layer over knowledge graphs, supplying class hierarchies and consistency constraints.
- Logical entailment provides the semantic standard against which any reasoning system — symbolic or neural — can be measured.
- Neurosymbolic AI combines learned embeddings with explicit representations, so that pattern recognition and structured reasoning operate on the same substrate.
- LLMs as interfaces to symbolic tools treat the symbolic system as an external oracle: the model decides when to call it, the tool does the reasoning.
- Neural proposal and symbolic verification lets the network generate candidate solutions cheaply and lets a sound symbolic checker keep only the ones that survive.
The thread connecting them is that no single representation does everything: explicit representations are precise but brittle, neural ones are flexible but opaque, and the engineering question is how to wire them together.