Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

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 Loaded(s)\mathit{Loaded}(s) hold or fail in situations, and do(a,s)do(a,s) is the situation after action aa. 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 ∣A∣⋅∣F∣|A|\cdot|F| 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).

DerivationSuccessor-state axioms (Reiter, 1991)
  1. γF+(a,s)⇒F(do(a,s)),γF−(a,s)⇒¬F(do(a,s))\gamma_F^+(a,s)\Rightarrow F(do(a,s)),\qquad\gamma_F^-(a,s)\Rightarrow\neg F(do(a,s))

    Collect all the ways a fluent FF can become true, and all the ways it can become false, into two conditions on the action:

  2. ¬F(s)∧F(do(a,s))⇒γF+(a,s),F(s)∧¬F(do(a,s))⇒γF−(a,s)\neg F(s)\wedge F(do(a,s))\Rightarrow\gamma_F^+(a,s),\qquad F(s)\wedge\neg F(do(a,s))\Rightarrow\gamma_F^-(a,s)

    Assume causal completeness: these are the only ways in which FF can change (explanation closure):

  3. F(do(a,s))  ⟺  γF+(a,s)∨(F(s)∧¬γF−(a,s))F(do(a,s))\iff\gamma_F^+(a,s)\vee\big(F(s)\wedge\neg\gamma_F^-(a,s)\big)

    If no action makes FF both true and false, and actions have unique names, the four axioms are equivalent to a single biconditional per fluent:

  4. Loaded(do(a,s))  ⟺  a=load∨(Loaded(s)∧a≠shoot)Alive(do(a,s))  ⟺  Alive(s)∧¬(a=shoot∧Loaded(s))\begin{aligned}\mathit{Loaded}(do(a,s))&\iff a=\mathit{load}\vee\big(\mathit{Loaded}(s)\wedge a\neq\mathit{shoot}\big)\\ \mathit{Alive}(do(a,s))&\iff\mathit{Alive}(s)\wedge\neg\big(a=\mathit{shoot}\wedge\mathit{Loaded}(s)\big)\end{aligned}

    For the shooting world:

  5. ≈∣A∣⋅∣F∣ frame axioms⟶∣F∣ successor-state axioms\approx|A|\cdot|F|\ \text{frame axioms}\quad\longrightarrow\quad|F|\ \text{successor-state axioms}

    One axiom per fluent, of total size proportional to the number of effect axioms, replaces about ∣A∣⋅∣F∣|A|\cdot|F| 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 W={Bird(t)}W=\{\mathit{Bird}(t)\} and the normal default Bird(x):Flies(x)Flies(x)\frac{\mathit{Bird}(x):\mathit{Flies}(x)}{\mathit{Flies}(x)}, the only extension contains Flies(t)\mathit{Flies}(t). Add Penguin(t)\mathit{Penguin}(t) and ∀x (Penguin(x)⇒¬Flies(x))\forall x\,(\mathit{Penguin}(x)\Rightarrow\neg\mathit{Flies}(x)) to WW, and the default is blocked: the only extension now contains ¬Flies(t)\neg\mathit{Flies}(t). Conflicting defaults produce several extensions. Credulous reasoning accepts what holds in some extension, skeptical reasoning only what holds in all of them.

DerivationProof sketch (finite D, consistent W)
  1. Ei+1=Ei∪{γ}  if Ei⊨α and Ei∪{γ} is consistent;E=Th⁡(Ek)E_{i+1}=E_i\cup\{\gamma\}\ \ \text{if }E_i\models\alpha\text{ and }E_i\cup\{\gamma\}\text{ is consistent};\qquad E=\operatorname{Th}(E_k)

    Build EE greedily. Start from E0=WE_0=W. At each step, apply an unused normal default α:γγ\frac{\alpha:\gamma}{\gamma} whose prerequisite follows and whose consequent is consistent with what has been built; stop when none is left:

  2. γ∈E  and  E consistent ⟹ ¬γ∉E\gamma\in E\ \text{ and }\ E\text{ consistent}\ \Longrightarrow\ \neg\gamma\notin E

    EE is consistent, since every step preserves consistency. So every applied default remains justified with respect to the final EE: its justification γ\gamma is in EE, hence ¬γ\neg\gamma is not.

  3. Ei⊆Γ(E) ⟹ Ei+1⊆Γ(E)E_i\subseteq\Gamma(E)\ \Longrightarrow\ E_{i+1}\subseteq\Gamma(E)

    E⊆Γ(E)E\subseteq\Gamma(E), by induction on ii: each applied default has its prerequisite in Th⁡(Ei)⊆Γ(E)\operatorname{Th}(E_i)\subseteq\Gamma(E) and a justification consistent with EE, so its consequent lies in Γ(E)\Gamma(E).

  4. Γ(E)⊆E⟹E=Γ(E)\Gamma(E)\subseteq E\quad\Longrightarrow\quad E=\Gamma(E)

    Γ(E)⊆E\Gamma(E)\subseteq E: the set EE contains WW, is deductively closed, and contains the consequent of every default whose prerequisite is in EE and whose justification is consistent with EE, or the construction would not have stopped. Γ(E)\Gamma(E) is the smallest set with these properties.

Extensions are expensive. For propositional default theories, deciding whether a formula belongs to some extension is Σ2p\Sigma_2^p-complete, and whether it belongs to every extension is Π2p\Pi_2^p-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.

Check your understanding

W={Quaker(n), Republican(n)}W=\{\mathit{Quaker}(n),\ \mathit{Republican}(n)\}, with the defaults Quaker(x):Pacifist(x)Pacifist(x)\frac{\mathit{Quaker}(x):\mathit{Pacifist}(x)}{\mathit{Pacifist}(x)} and Republican(x):¬Pacifist(x)¬Pacifist(x)\frac{\mathit{Republican}(x):\neg\mathit{Pacifist}(x)}{\neg\mathit{Pacifist}(x)}. Which statement is true?

  1. There is no extension, because the defaults conflict
  2. There is one extension, containing both Pacifist(n)\mathit{Pacifist}(n) and ¬Pacifist(n)\neg\mathit{Pacifist}(n)
  3. There are two extensions, so Pacifist(n)\mathit{Pacifist}(n) follows credulously but not skeptically
  4. The more specific default wins, so ¬Pacifist(n)\neg\mathit{Pacifist}(n) is in every extension
Show the answer

C. There are two extensions, so Pacifist(n)\mathit{Pacifist}(n) 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 Pacifist(n)\mathit{Pacifist}(n) and one containing ¬Pacifist(n)\neg\mathit{Pacifist}(n). 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:

ResourceBeganContent and representationStrengths and limits
Cyc (Lenat)1984, at MCC; Cycorp from the mid-1990sMillions 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 coexistPrecise and inferentially rich; enormously costly to build, mostly proprietary, and its coverage gaps are hard to see from outside
WordNet (Miller)1985, PrincetonSets of synonyms (synsets) linked by lexical relations such as hypernymy, meronymy and antonymyUbiquitous in NLP; lexical rather than inferential knowledge
ConceptNet1999, from MIT's Open Mind Common Sense project; version 5.5 in 2017A multilingual graph of natural-language terms joined by a few dozen relations such as UsedFor, CapableOf, AtLocation and Causes, from crowdsourcing and other resourcesBroad and easy to embed; loose semantics (edges link phrases, not defined concepts) and noise
ATOMIC (Sap et al.)2019Crowdsourced if-then knowledge about everyday events (the intents, reactions, effects and preconditions of people's actions) as free-text triplesSocial and causal inference; COMET (Bosselut et al., 2019) trains a transformer on it to generate new entries
From formal and hand-built to crowdsourced and textual: precision falls as coverage grows.

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.

Predict before you look

The original collection has 273 two-way problems. A coin-flipping system scores 50% on average, with a standard deviation of 0.25/273≈3\sqrt{0.25/273}\approx3 percentage points. Roughly what accuracy, in percent, must a system exceed to be two standard deviations above chance?

Show the answer

56 %

50+2×3.0≈56%50+2\times3.0\approx56\%. 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 ∣A∣⋅∣F∣|A|\cdot|F| frame axioms into one axiom per fluent; the qualification and ramification problems remain hard.
  • Default logic formalizes "typically": extensions are fixed points E=Γ(E)E=\Gamma(E), normal theories always have one, credulous reasoning is Σ2p\Sigma_2^p-complete and skeptical reasoning Π2p\Pi_2^p-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.

Question 1

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?

  1. About 150 frame axioms versus 50 successor-state axioms
  2. About 10,000 frame axioms versus 200 successor-state axioms
  3. About 10,000 of each
  4. 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 50×200−150≈10,00050\times200-150\approx10{,}000, or twice that if persistence of truth and of falsity are stated separately. Successor-state axioms need one per fluent: 200.

Question 2

Which default theory has no extension?

  1. W={Bird}W=\{\mathit{Bird}\} and D={Bird:FliesFlies}D=\{\frac{\mathit{Bird}:\mathit{Flies}}{\mathit{Flies}}\}
  2. The Nixon diamond
  3. W={p}W=\{p\} and D={p:qq}D=\{\frac{p:q}{q}\}
  4. W=∅W=\varnothing and D={⊤:¬pp}D=\{\frac{\top:\neg p}{p}\}
Show the answer

D. W=∅W=\varnothing and D={⊤:¬pp}D=\{\frac{\top:\neg p}{p}\}

If p∉Ep\notin E, the justification ¬p\neg p is consistent with EE, so the default fires and puts pp into Γ(E)\Gamma(E). If p∈Ep\in E, the justification fails and Γ(E)\Gamma(E) does not contain pp. Either way E≠Γ(E)E\neq\Gamma(E). The default is not normal, so Reiter's theorem does not apply.

Question 3

Why was the 2019–2020 "defeat" of the Winograd schema challenge by language models widely seen as inconclusive about commonsense reasoning?

  1. 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
  2. The models were evaluated on their own training problems
  3. Human annotators scored below chance on the test
  4. 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.

Question 4

Which contrast between Cyc and ConceptNet is accurate?

  1. Cyc was crowdsourced, while ConceptNet was hand-built by trained ontologists
  2. Both were learned automatically from text by neural networks
  3. Cyc uses a formal logic language (CycL) with microtheories, while ConceptNet links natural-language terms with loosely defined relations
  4. 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.