Commonsense Reasoning
Why the obvious is the hardest thing to encode.
Nobody tells you that a cup left on a table is still there after you leave the room, that you can't be in two places at once, or that a trophy too big for a suitcase won't fit in it. Writing such knowledge down for a machine has defeated every attempt to make it complete, and it has produced some of the deepest results in knowledge representation.
What you’ll learn
- State the frame, qualification and ramification problems, and derive Reiter's successor-state axioms.
- Define default logic and its extensions, prove that normal default theories always have an extension, and state the complexity of default reasoning.
- Compare the major commonsense resources: Cyc, WordNet, ConceptNet and ATOMIC.
- Explain the Winograd schema challenge, how it was "defeated", and what that does and does not show about commonsense in language models.
The frame problem and its cousins
McCarthy and Hayes (1969) introduced the situation calculus: fluents such as hold or fail in situations, and is the situation after action . Effect axioms say what an action changes. To prove anything about what it does not change, you need frame axioms, roughly one for every pair of an action and a fluent that it leaves alone: on the order of axioms. That is the representational frame problem.
It has two cousins. The qualification problem (McCarthy, 1980): no finite list of preconditions guarantees that an action succeeds (the car starts, unless there is a potato in the tailpipe). The ramification problem: actions have indirect effects (moving a box moves everything inside it).
Collect all the ways a fluent can become true, and all the ways it can become false, into two conditions on the action:
Assume causal completeness: these are the only ways in which can change (explanation closure):
If no action makes both true and false, and actions have unique names, the four axioms are equivalent to a single biconditional per fluent:
For the shooting world:
One axiom per fluent, of total size proportional to the number of effect axioms, replaces about frame axioms. This solves the representational frame problem for deterministic actions without ramifications. STRIPS builds the same idea into its semantics: whatever is outside an action's add and delete lists persists.
Defaults, extensions and their complexity
With and the normal default , the only extension contains . Add and to , and the default is blocked: the only extension now contains . Conflicting defaults produce several extensions. Credulous reasoning accepts what holds in some extension, skeptical reasoning only what holds in all of them.
Build greedily. Start from . At each step, apply an unused normal default whose prerequisite follows and whose consequent is consistent with what has been built; stop when none is left:
is consistent, since every step preserves consistency. So every applied default remains justified with respect to the final : its justification is in , hence is not.
, by induction on : each applied default has its prerequisite in and a justification consistent with , so its consequent lies in .
: the set contains , is deductively closed, and contains the consequent of every default whose prerequisite is in and whose justification is consistent with , or the construction would not have stopped. is the smallest set with these properties.
Extensions are expensive. For propositional default theories, deciding whether a formula belongs to some extension is -complete, and whether it belongs to every extension is -complete (Gottlob, 1992): one level above classical propositional reasoning in the polynomial hierarchy, because verifying a guessed extension already requires propositional entailment tests. In practice, nonmonotonic reasoning today mostly means answer set programming (Gelfond & Lifschitz, 1988), a rule language with default negation and efficient solvers.
, with the defaults and . Which statement is true?
- There is no extension, because the defaults conflict
- There is one extension, containing both and
- There are two extensions, so follows credulously but not skeptically
- The more specific default wins, so is in every extension
Show the answer
C. There are two extensions, so follows credulously but not skeptically
Applying either default blocks the other, because its consequent contradicts the other's justification. Each choice yields an extension, one containing and one containing . Default logic has no built-in notion of specificity.
Commonsense knowledge at scale
If the logic is hard, the knowledge is harder. Four resources span the design space:
| Resource | Began | Content and representation | Strengths and limits |
|---|---|---|---|
| Cyc (Lenat) | 1984, at MCC; Cycorp from the mid-1990s | Millions of hand-entered assertions in CycL, a higher-order logic language, organized into microtheories (contexts) so that mutually inconsistent assumptions, such as fiction and fact or different eras, can coexist | Precise and inferentially rich; enormously costly to build, mostly proprietary, and its coverage gaps are hard to see from outside |
| WordNet (Miller) | 1985, Princeton | Sets of synonyms (synsets) linked by lexical relations such as hypernymy, meronymy and antonymy | Ubiquitous in NLP; lexical rather than inferential knowledge |
| ConceptNet | 1999, from MIT's Open Mind Common Sense project; version 5.5 in 2017 | A multilingual graph of natural-language terms joined by a few dozen relations such as UsedFor, CapableOf, AtLocation and Causes, from crowdsourcing and other resources | Broad and easy to embed; loose semantics (edges link phrases, not defined concepts) and noise |
| ATOMIC (Sap et al.) | 2019 | Crowdsourced if-then knowledge about everyday events (the intents, reactions, effects and preconditions of people's actions) as free-text triples | Social and causal inference; COMET (Bosselut et al., 2019) trains a transformer on it to generate new entries |
The Winograd schema challenge, and after
Levesque, Davis and Morgenstern (2012) proposed Winograd schemas as a test of common sense that is harder to game than open conversation. Each is a pair of sentences that differ in one or two words, the special word, which flips the referent of a pronoun. The answer should be obvious to people and not recoverable from word co-occurrence or selectional restrictions. The name honors Terry Winograd's (1972) example: "The city councilmen refused the demonstrators a permit because they feared / advocated violence."
At the first challenge, held at IJCAI in 2016, no system came close to the 90% accuracy needed to advance. Then pretrained transformers changed the picture. Fine-tuned on WinoGrande, a crowdsourced set of about 44,000 Winograd-style problems filtered to remove easy statistical cues (Sakaguchi et al., 2020), language models exceeded 90% on the original collection of 273 problems. Kocijan, Davis, Lukasiewicz, Marcus and Morgenstern (2023) called this "the defeat of the Winograd schema challenge", and drew a lesson about surrogate tests: they can be passed without demonstrating the general commonsense reasoning they were designed to detect.
The original collection has 273 two-way problems. A coin-flipping system scores 50% on average, with a standard deviation of percentage points. Roughly what accuracy, in percent, must a system exceed to be two standard deviations above chance?
Show the answer
56 %
. Small benchmarks have wide error bars: on 273 items, a 3-point gain is one standard deviation of pure luck, and because schemas come in correlated pairs, the effective sample is smaller still. Claims of progress on small test sets need confidence intervals.
Key takeaways
- The frame problem: effects are easy to state, persistence is not. Successor-state axioms compress about frame axioms into one axiom per fluent; the qualification and ramification problems remain hard.
- Default logic formalizes "typically": extensions are fixed points , normal theories always have one, credulous reasoning is -complete and skeptical reasoning -complete.
- Commonsense resources trade precision for coverage: Cyc is formal and hand-built, WordNet lexical, ConceptNet and ATOMIC crowdsourced with loose semantics. Knowledge mined from text inherits reporting bias.
- The Winograd schema challenge was beaten by large language models around 2019–2020, largely through scale and fine-tuning on similar data. How much commonsense reasoning such models have remains contested, and small benchmarks need error bars.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
A situation-calculus domain has 50 actions and 200 fluents, and each action affects at most 3 fluents. Roughly how many classical frame axioms does it need, compared with successor-state axioms?
- About 150 frame axioms versus 50 successor-state axioms
- About 10,000 frame axioms versus 200 successor-state axioms
- About 10,000 of each
- About 200 frame axioms versus 10,000 successor-state axioms
Show the answer
B. About 10,000 frame axioms versus 200 successor-state axioms
Frame axioms are needed for every action–fluent pair that the action leaves unchanged: about , or twice that if persistence of truth and of falsity are stated separately. Successor-state axioms need one per fluent: 200.
Which default theory has no extension?
- and
- The Nixon diamond
- and
- and
Show the answer
D. and
If , the justification is consistent with , so the default fires and puts into . If , the justification fails and does not contain . Either way . The default is not normal, so Reiter's theorem does not apply.
Why was the 2019–2020 "defeat" of the Winograd schema challenge by language models widely seen as inconclusive about commonsense reasoning?
- High accuracy came from large models fine-tuned on Winograd-style data that could exploit statistical regularities, so it did not clearly show the intended reasoning
- The models were evaluated on their own training problems
- Human annotators scored below chance on the test
- The challenge was quietly changed to a multiple-choice format
Show the answer
A. High accuracy came from large models fine-tuned on Winograd-style data that could exploit statistical regularities, so it did not clearly show the intended reasoning
Large pretrained models fine-tuned on tens of thousands of similar problems crossed 90% on the original collection. Analyses found that some schemas could be solved through word associations, and passing the test turned out to be possible without demonstrating the general reasoning it was designed to require.
Which contrast between Cyc and ConceptNet is accurate?
- Cyc was crowdsourced, while ConceptNet was hand-built by trained ontologists
- Both were learned automatically from text by neural networks
- Cyc uses a formal logic language (CycL) with microtheories, while ConceptNet links natural-language terms with loosely defined relations
- ConceptNet supports full first-order inference, while Cyc stores only word associations
Show the answer
C. Cyc uses a formal logic language (CycL) with microtheories, while ConceptNet links natural-language terms with loosely defined relations
Cyc's ontologists encode assertions in CycL and reason within contexts. ConceptNet's edges connect phrases such as "knife" and "cut" through relations such as UsedFor, which makes it broad but semantically loose.
Further reading
- J. McCarthy & P. J. Hayes, "Some philosophical problems from the standpoint of artificial intelligence," Machine Intelligence 4 (1969), 463–502.
- R. Reiter, "A logic for default reasoning," Artificial Intelligence 13(1–2) (1980), 81–132.
- H. J. Levesque, E. Davis & L. Morgenstern, "The Winograd schema challenge," Proceedings of KR (2012).
- V. Kocijan, E. Davis, T. Lukasiewicz, G. Marcus & L. Morgenstern, "The defeat of the Winograd Schema Challenge," Artificial Intelligence 325 (2023).
- E. Davis & G. Marcus, "Commonsense reasoning and commonsense knowledge in artificial intelligence," Communications of the ACM 58(9) (2015), 92–103.