Goldszmidt & Pearl (1996): Qualitative Probabilities for Default Reasoning #
@cite{goldszmidt-pearl-1996}
This study demonstrates System Z — the constructive derivation of minimal ranking functions from a knowledge base of default rules. Where @cite{spohn-1988} defines ranking functions as primitive objects, G&P show how to compute the unique minimal admissible ranking κ^z from a set of defaults, using tolerance-based stratification.
Key demonstrations #
Tolerance stratification: Rules are partitioned by iteratively peeling off tolerated rules (Consistency-Test, Fig. 2). In the 3-rule subset of the Tweety scenario (r₁–r₃ from Example 17), "birds fly" is tolerated first (Z = 0), while "penguins are birds" and "penguins don't fly" are tolerated only after removing the first stratum (Z = 1).
κ^z ranking (Definition 12): The minimal admissible ranking assigns each world the lowest possible rank. Worlds verifying all rules get rank 0; worlds falsifying only low-priority rules get low ranks.
Specificity: More specific defaults automatically override general ones — penguinNoFly outranks penguinFlies because the penguin-specific rule has higher Z-priority.
Bridge to Veltman: The κ^z ranking derives the same specificity result that @cite{veltman-1996} obtains by stipulating orderings. We prove the agreement directly.
Scenario #
We formalize rules r₁–r₃ from Example 17 (the paper's full example has 5 rules including r₄: b→w and r₅: f→a, which would require extending TweetyWorld with wings/airborne features). The 3-rule subset is sufficient to demonstrate tolerance stratification, κ^z construction, admissibility, and specificity.
All Tweety worlds are birds.
Instances For
Equations
- Phenomena.DefaultReasoning.Studies.GoldszmidtPearl1996.isPenguinB Phenomena.DefaultReasoning.TweetyWorld.penguinFlies = true
- Phenomena.DefaultReasoning.Studies.GoldszmidtPearl1996.isPenguinB Phenomena.DefaultReasoning.TweetyWorld.penguinNoFly = true
- Phenomena.DefaultReasoning.Studies.GoldszmidtPearl1996.isPenguinB x✝ = false
Instances For
Equations
- Phenomena.DefaultReasoning.Studies.GoldszmidtPearl1996.fliesB Phenomena.DefaultReasoning.TweetyWorld.birdFlies = true
- Phenomena.DefaultReasoning.Studies.GoldszmidtPearl1996.fliesB Phenomena.DefaultReasoning.TweetyWorld.penguinFlies = true
- Phenomena.DefaultReasoning.Studies.GoldszmidtPearl1996.fliesB x✝ = false
Instances For
Bool predicates agree with the Prop predicates in TweetyNixon.
r₁: "Birds fly" (b → f).
Equations
- One or more equations did not get rendered due to their size.
Instances For
r₂: "Penguins are birds" (p → b). Strict: no world falsifies it in TweetyWorld since all penguins are birds by construction.
Equations
- One or more equations did not get rendered due to their size.
Instances For
r₃: "Penguins don't fly" (p → ¬f).
Equations
- One or more equations did not get rendered due to their size.
Instances For
The penguin-bird knowledge base Δ_pb (rules r₁–r₃).
Equations
- One or more equations did not get rendered due to their size.
Instances For
Stratum 0: r₁ is tolerated by Δ_pb (birdFlies verifies r₁ and all material counterparts). r₂ and r₃ are not tolerated (no world satisfies their antecedent + consequent while also satisfying b → f as a material conditional).
Stratum 1: After removing r₁, both r₂ and r₃ are tolerated
(penguinNoFly verifies both and satisfies the remaining material
counterparts).
Z-priorities: Z(r₁) = 0, Z(r₂) = 1, Z(r₃) = 1.
After removing stratum 0 (r₁), both r₂ and r₃ are tolerated.
Equations
Instances For
Z-prioritized rules: Z(r₁) = 0, Z(r₂) = 1, Z(r₃) = 1.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The minimal ranking κ^z for the Tweety knowledge base.
κ^z values (Definition 12):
- birdFlies: falsifies nothing → 0
- birdNoFly: falsifies r₁ (Z=0) → max(0)+1 = 1
- penguinFlies: falsifies r₃ (Z=1) → max(1)+1 = 2
- penguinNoFly: falsifies r₁ (Z=0) → max(0)+1 = 1
Equations
- One or more equations did not get rendered due to their size.
Instances For
r₁ (b → f) is admissible: every world falsifying it (birdNoFly, penguinNoFly, both rank 1) is outranked by birdFlies (rank 0).
r₃ (p → ¬f) is admissible: the only falsifying world is penguinFlies (rank 2), outranked by penguinNoFly (rank 1).
κ^z is admissible relative to the full knowledge base Δ_pb (Definition 2).
z-entailment queries on Δ_pb. These cover two of the five queries in Table 2 (the remaining three — red birds fly, birds airborne, penguins winged — require r₄/r₅ and a richer world type).
"Do penguin-birds fly?" → NO (z-entailment). penguinNoFly (rank 1) outranks penguinFlies (rank 2). The more specific default wins.
"Are birds typically penguins?" → NO (z-entailment). birdFlies (rank 0) is a non-penguin bird, outranking all penguin worlds.
"Do birds fly?" → YES (z-entailment). birdFlies (rank 0) is the most normal bird world and it flies.
The κ^z ranking makes penguinNoFly strictly more plausible than penguinFlies.
The κ^z ranking preserves the general default: among non-penguin birds, flying is more normal than not flying.
The induced plausibility ordering is connected (total), so Rational Monotonicity holds.
@cite{veltman-1996} manually stipulates subdomain orderings to
resolve the Tweety Triangle: birdOrd promotes flying,
penguinOrd promotes not-flying. The key result is
penguinFlies_not_normal_in_birds — penguinFlies fails the
normality test because the penguin subdomain ordering demotes it.
G&P's System Z *derives* the same specificity result from the
rules alone, without any stipulated orderings. The following
theorem makes this derivation-vs-stipulation relationship explicit
by combining both papers' conclusions.
What @cite{veltman-1996} stipulates about penguin normality, @cite{goldszmidt-pearl-1996}'s System Z derives:
- Veltman: penguinFlies is not normal among birds (via stipulated penguin subdomain ordering)
- G&P: penguinFlies has strictly higher κ^z rank than birdFlies (derived from tolerance stratification alone) Both reach the same conclusion: flying penguins are less normal than non-flying penguins in a bird context.
@cite{frank-goodman-2012}'s RSA framework uses softmax-based Bayesian inference with a finite rationality parameter α. @cite{goldszmidt-pearl-1996}'s System Z uses ranking functions for qualitative default reasoning.
The two frameworks are endpoints of the same continuum: as
α → ∞, softmax concentrates on the most normal (rank-0) worlds,
recovering ranking-based entailment from probabilistic inference.
We demonstrate this concretely: the softmax distribution with
scores derived from κ^z concentrates on birdFlies (the unique
rank-0 world) as α → ∞. This means RSA's pragmatic listener
with infinite rationality reasons exactly like System Z.
birdFlies is the unique rank-0 world under κ^z.
The softmax distribution softmax(-κ^z, α) concentrates on birdFlies as α → ∞. This is the core RSA–ranking bridge for the Tweety scenario: an RSA listener with infinite rationality assigns probability 1 to the most normal world.
Under κ^z, all minimum-rank bird-worlds fly. This connects
the ranking entailment birds_fly to the softmax limit:
as α → ∞, the softmax listener restricted to bird-worlds
assigns all probability to flying worlds.
Under κ^z, all minimum-rank penguin-worlds don't fly. The specificity result — penguins override the general bird default — is precisely the α → ∞ limit of RSA inference restricted to the penguin domain.
Conditional limit: "Do birds fly?" → probability 1. As α → ∞, the conditional probability P_α(flies|bird) → 1 under κ^z scores. This is the full conditional softmax limit theorem applied to the Tweety scenario.
Conditional limit: "Do penguin-birds fly?" → probability 0. As α → ∞, the conditional probability P_α(flies|penguin∧bird) → 0, because ranking entailment says penguin-birds don't fly. We prove this by showing P_α(¬flies|penguin∧bird) → 1.
The Consistency-Test (Fig. 2) computes the same Z-priorities as
our manually-verified prioritized list: Z(r₁)=0, Z(r₂)=1, Z(r₃)=1.
System Z⁺ augments each rule with a strength parameter δ, requiring a wider gap between verifying and falsifying worlds. The Z⁺-priority of a rule accounts for δ, giving stronger rules higher priority and thus wider separation in the ranking.
Strength-augmented rules: δ₁=1, δ₂=1, δ₃=2. "Penguins don't fly" (r₃) is strongest.
Equations
- Phenomena.DefaultReasoning.Studies.GoldszmidtPearl1996.sr₁ = { toDefaultRule := Phenomena.DefaultReasoning.Studies.GoldszmidtPearl1996.r₁, strength := 1 }
Instances For
Equations
- Phenomena.DefaultReasoning.Studies.GoldszmidtPearl1996.sr₂ = { toDefaultRule := Phenomena.DefaultReasoning.Studies.GoldszmidtPearl1996.r₂, strength := 1 }
Instances For
Equations
- Phenomena.DefaultReasoning.Studies.GoldszmidtPearl1996.sr₃ = { toDefaultRule := Phenomena.DefaultReasoning.Studies.GoldszmidtPearl1996.r₃, strength := 2 }
Instances For
Equations
- One or more equations did not get rendered due to their size.
Instances For
Z⁺ priorities computed via the Z⁺_order procedure (Fig. 4) to satisfy δ-admissibility constraints. z⁺(r₁) = 1, z⁺(r₂) = 3, z⁺(r₃) = 4.
The constraint for r₃ (δ=2) is κ(penguinNoFly) + 2 < κ(penguinFlies). Since penguinNoFly falsifies r₁ giving rank z⁺(r₁)+1 = 2, we need 2 + 2 < z⁺(r₃) + 1, so z⁺(r₃) ≥ 4.
Note: z⁺(r₂) = 3 because the verifying world for r₂ (penguinNoFly) has κ = z⁺(r₁) + 1 = 2, so z⁺(r₂) = 2 + δ₂ = 2 + 1 = 3. r₂ is never falsified in TweetyWorld, so its priority doesn't affect ranks.
Equations
- One or more equations did not get rendered due to their size.
Instances For
κ⁺: the Z⁺ ranking with wider gaps than κ^z.
- birdFlies: falsifies nothing → 0
- birdNoFly: falsifies r₁ (z⁺=1) → 2
- penguinFlies: falsifies r₃ (z⁺=4) → 5
- penguinNoFly: falsifies r₁ (z⁺=1) → 2
Equations
- One or more equations did not get rendered due to their size.
Instances For
κ⁺ is δ-admissible relative to the strength rules.
κ^z's gap for r₃ is too small for δ₃=2: 1 + 2 ≥ 2. This motivates Z⁺ — the minimal ranking κ^z doesn't provide enough separation for variable-strength defaults.