Probabilistic Reasoning with Inconsistent Beliefs Using Inconsistency Measures

Nico Potyka, Matthias ThimmIJCAI 2015

Introduction

Classical probabilistic logic, such as Nilsson’s framework, operates under a strict requirement of consistency. In real-world scenarios, however, information is often contradictory. For instance, expert opinions may conflict, or rules within a knowledge base may overlap in incompatible ways. When faced with such inconsistencies, classical systems collapse, failing to provide meaningful answers. This paper proposes a "generalized entailment" framework that leverages inconsistency measures to find probability distributions that minimally violate a knowledge base, enabling robust reasoning in the presence of contradictions.

Methodology: Reasoning via Minimal Violation

The authors bridge the gap between logic and optimization by treating inconsistency as a distance problem. Instead of searching for a probability function that perfectly satisfies every rule, the framework identifies functions that minimize the "violation" of the rules.

Inconsistency Measures and p-norms

The degree of violation is quantified using $p$-norms ($L_1, L_2, L_\infty$):

  • $L_1$ norm: Acts like a median, considering all violations equally.
  • $L_2$ norm: Penalizes larger violations more heavily, often leading to unique "average" solutions.
  • $L_\infty$ norm: Focuses solely on the single largest violation, ignoring smaller ones.

Integrity Constraints (IC)

To maintain logical grounding, the system distinguishes between "negotiable" beliefs and "non-negotiable" facts, termed Integrity Constraints. While the system may compromise on beliefs to resolve inconsistency, it strictly adheres to these constraints.

Key Insights

The framework is built upon several core principles that ensure its practical and theoretical utility.

Rationality and the "Best Fit" Philosophy

The authors define rationality postulates—Consistency, Integrity, and Independence—proving that their method behaves like classical logic when data is consistent while remaining resilient to noise. By shifting from "absolute truth" to "minimal violation," logic begins to behave more like statistical regression, finding the most plausible model given conflicting evidence.

Computational Efficiency

A significant finding is that reasoning with inconsistent beliefs is asymptotically no more difficult than reasoning with consistent ones. Both tasks involve solving optimization problems of comparable complexity.

Computational complexity comparison of various probabilistic reasoning problems.

As illustrated in the table above, the number of variables ($\bar{n}$) and constraints ($\bar{m}$) for generalized entailment (GENT) and inconsistency-tolerant inference ($\mathcal{I}^p_{IC}$) remain within the same order of magnitude as standard probabilistic satisfiability (PSAT).

Results and Paradox Resolution

The framework was evaluated using classic logical benchmarks like the Nixon Diamond and Kyburg’s Lottery Paradox. In the Lottery Paradox—where one believes every ticket will lose but knows one must win—the generalized model correctly identifies a uniform distribution, assigning each ticket an equal, minimal probability of winning.

Norm Sensitivity

The choice of $p$-norm significantly influences the reasoner's output.

Query results under different p-norms ($L_1, L_2, L_\infty$).

As shown in the query results above, the $L_1$ norm typically yields more conservative, wider probability intervals. In contrast, $L_2$ and $L_\infty$ norms tend to converge toward specific point probabilities, reflecting different strategies for reconciling expert disagreement.

Limitations and Future Work

While robust, the framework faces challenges regarding continuity; small input changes can occasionally cause jumps in output. Additionally, the state-space of possible worlds grows exponentially with the number of variables. Future work may involve implementing "column generation" techniques to scale the optimization process for larger, real-world datasets.

Summary updated

BibTeX
@inproceedings{potyka2015probabilistic,
  author = {Nico Potyka and Matthias Thimm},
  title = {{Probabilistic Reasoning with Inconsistent Beliefs Using Inconsistency Measures}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure