Likelihood, Probability, and Knowledge

Joseph Y. Halpern, David A. McAllesterAAAI 1984 · OpenReview

Abstract

The modal logic LL was introduced by Halpern and Rabin as a means of doing qualitative reasoning about likelihood. Here the relationship between LL and probability theory is examined. It is shown that there is a way of translating probability assertions into LL in a sound manner, so that LL in some sense can capture the probabilistic interpretation of likelihood. However, the translation is subtle; several more obvious attempts are shown to lead to inconsistencies. We also extend LL by adding modal operators for knowledge. This allows us to reason about the interaction between knowledge and likelihood. The propositional version of the resulting logic LLK is shown to have a complete axiomatization and to be decidable in exponential time, provably the best possible.

Introduction

In the development of artificial intelligence, a persistent tension exists between the precision of probability theory and the qualitative nature of human reasoning. While probability provides a robust mathematical framework for uncertainty, it often requires exact numerical values—such as "the probability is 0.73"—which are frequently unavailable or "epistemologically inadequate" for general reasoning. As McCarthy and Hayes (1969) argued, humans typically reason with qualitative convictions rather than precise numbers.

This paper addresses this gap by investigating the Logic of Likelihood (LL). The goal is to create a formal system that allows for qualitative reasoning about "likelihood" while maintaining mathematical consistency with the underlying laws of probability.

The Logic of Likelihood (LL)

The foundation of this work is LL, a modal logic that introduces an operator $L$ to represent "likely." In this framework, $L\phi$ is interpreted as "$\phi$ is reasonably likely."

Semantics and Structure

The semantics of LL are defined using Kripke structures, which represent possible worlds and the relationships between them. In these models, a state corresponds to a set of hypotheses, and transitions represent shifts to "reasonably likely" alternative sets.

Figure 1: A visual representation of overlapping sets of possible worlds or propositions within the Kripke semantics of LL.

As shown in Figure 1, propositions ($P_1, P_2, \dots$) are represented as sets of states. The logic reasons about the intersections and inclusions of these sets to determine the validity of likelihood assertions. For instance, if $P_3$ is a subset of $P_2$, then the necessity of $P_3$ implies the necessity of $P_2$, which influences how likelihood propagates through the model.

Bridging Probability and Logic: The Subtle Translation

The core technical challenge is translating quantitative probabilistic statements (e.g., "The probability of $C$ given $D$ is at least $\alpha$") into qualitative LL formulas. A naive translation often leads to paradoxes.

The Coin Toss Paradox

Consider tossing a fair coin twice. It is likely that the result is either HH or TT (combined probability of 0.5). However, in standard modal logic, the distribution axiom $L(P \lor Q) \implies (LP \lor LQ)$ would imply that it is either likely to get HH or likely to get TT—both of which are false individually. To resolve this, the authors propose a "subtle" translation where "likely $P$" is interpreted as $LGP$ (it is likely that $P$ is necessarily true).

The Role of Caveats

To ensure soundness, the translation incorporates "caveats" to handle conflicting information. A statement like "Given $P$, $Q$ is likely" is translated to include a mechanism that filters out potential negative impacts, effectively stating: "In the absence of information suggesting otherwise, $Q$ follows from $P$ with likelihood." This mechanism accounts for the non-monotonic nature of human reasoning, where new knowledge can force the retraction of previous likelihood assessments.

Extending to Knowledge: LLK

The authors extend LL by adding a knowledge operator $K_i$, representing "Agent $i$ knows..." The resulting logic, LLK, allows for formal reasoning about the interaction between an agent's information state and their likelihood estimates. This is crucial for modeling "heuristic knowledge," where an agent may not know a specific fact (e.g., Mary's exact height) but can adjust likelihoods based on partial information (e.g., knowing Mary is on a basketball team).

Results and Complexity

The paper establishes two primary results:

  1. Soundness: The proposed translation is sound. Any conclusion derived in LL from translated probabilistic assertions is guaranteed to be true in the probabilistic sense.
  2. Computational Efficiency: The logic LLK is shown to be decidable in exponential time (EXPTIME). While computationally intensive, the authors prove this is the theoretical lower bound for such a logic, making LLK as efficient as possible for its expressive power.

Conclusion

By formalizing the relationship between likelihood and probability, this work provides a rigorous foundation for qualitative reasoning under uncertainty. While LL is not a complete replacement for probability—some probabilistic truths remain uncapturable—it offers a powerful tool for AI systems that must reason with incomplete, non-numerical information. Future research directions include comparing LLK with other frameworks like fuzzy logic or Dempster-Shafer theory to further refine our understanding of formal uncertainty.

Summary updated

Abstract

The modal logic LL was introduced by Halpern and Rabin as a means of doing qualitative reasoning about likelihood. Here the relationship between LL and probability theory is examined. It is shown that there is a way of translating probability assertions into LL in a sound manner, so that LL in some sense can capture the probabilistic interpretation of likelihood. However, the translation is subtle; several more obvious attempts are shown to lead to inconsistencies. We also extend LL by adding modal operators for knowledge. This allows us to reason about the interaction between knowledge and likelihood. The propositional version of the resulting logic LLK is shown to have a complete axiomatization and to be decidable in exponential time, provably the best possible. La logique modale LL a ete proposee par Halpern et Rabin comme moyen de proceder a un raisonnement qualitatif a propos de la vraisemblance. Dans cet article, la relation entre la logique modale LL et la theorie des probabilites est examinee. Les auteurs demontrent qu'il existe une facon de bien traduire des assertions probabilistiques en logique modale LL de facon a ce que cette derniere puisse saisir l'interpretation probabilistique de la vraisemblance. Cependant, cette traduction est subtile; plusieurs tentatives plus evidentes ont entraine des incoherences. Des operateurs modaux ont ete ajoutes a la logique modale LL afin de permettre un raisonnement sur l'interaction de la connaissance et de la vraisemblance. On a constate que la version propositionnelle de la logique resultante possedait une axiomatisation complete et s'averait un facteur decisif en temps exponentiel.
BibTeX
@inproceedings{halpern1984likelihood,
  author = {Joseph Y. Halpern and David A. McAllester},
  title = {{Likelihood, Probability, and Knowledge}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1984},
  url = {https://openreview.net/forum?id=HkEt3Al_bH},
}
Figure