Penalty Logic and its Link with Dempster-Shafer Theory

Florence Dupin de Saint-Cyr, Jérôme Lang, Thomas Schiex

TL;DR

This paper introduces "penalty logic" as a novel way to handle inconsistencies in knowledge bases by assigning a "cost" to violating each piece of information. It establishes a formal link between this penalty logic and Dempster-Shafer theory, showing how penalties can be seen as a form of uncertainty measure and how they can be used for non-monotonic reasoning and solving optimization problems.

What Problem Does This Paper Address?

In artificial intelligence, knowledge bases (collections of facts and rules) can sometimes be contradictory or inconsistent. When this happens, standard logical reasoning breaks down. A common approach to deal with this is to select "preferred" subsets of the knowledge base that are consistent. These preferences are often based on notions of "priority" or "uncertainty." However, existing priority-based methods are often "non-compensatory," meaning a violation at a high priority level cannot be offset by multiple violations at lower levels. This paper addresses this by proposing "penalty logic," where each formula has an associated cost (penalty) for its violation. This allows for "compensatory" reasoning, where the overall cost of inconsistency is the sum of individual penalties, reflecting a more utilitarian approach. The paper also aims to formally connect this penalty-based approach to established theories of uncertainty, specifically Dempster-Shafer theory.

Methods

The paper formalizes "penalty logic" by defining a "penalty knowledge base" (PK) as a finite multiset of pairs $( \phi_i, \alpha_i )$, where $ \phi_i $ is a propositional formula and $ \alpha_i $ is its associated penalty (a non-negative real number, possibly infinite).

Key methodological contributions include:

  • Cost of an Interpretation: The cost of an interpretation $ \omega $ with respect to a PK is defined as the sum of penalties of formulas violated by $ \omega $. This leads to the concept of "PK-preferred interpretations" which minimize this cost.
  • Cost of Consistency of a Formula: The paper defines the cost of making a formula $ \phi $ consistent with the PK as the minimum cost of an interpretation satisfying $ \phi $. This is shown to be related to the minimum cost of a $ \phi $-consistent sub-theory of PK.
  • Cost of a Sub-theory: The cost of a sub-theory $ A $ of PK is the sum of penalties of formulas in PK but not in $ A $. This allows for defining "PK-preferred sub-theories."
  • Non-monotonic Inference Relation: A non-monotonic inference relation is defined based on PK-preferred sub-theories, allowing conclusions to be drawn even from inconsistent knowledge bases.
  • Link to Dempster-Shafer Theory: The paper establishes a formal connection by showing that the cost function of an interpretation in penalty logic is equivalent to a "contour function" (a restriction of the plausibility function to singletons) in Dempster-Shafer theory, up to a logarithmic transformation. Furthermore, it links formula costs to an infinitesimal version of Dempster-Shafer theory.
  • Application to Optimization: Penalty logic is demonstrated as a tool for representing discrete optimization problems, specifically the maximum clique problem in graphs, where minimum cost interpretations correspond to optimal solutions.

Datasets

Not discussed in the paper. The paper focuses on theoretical formalization and does not present empirical evaluations on specific datasets.

Key Insights and Ideas

  • Penalties as Compensatory Uncertainty: Unlike rigid priorities, penalties allow for trade-offs. A high penalty for one formula can be compensated by accepting violations of multiple lower-penalty formulas. This offers a more nuanced way to handle inconsistency.
  • Logarithmic Equivalence to Dempster-Shafer: The core insight is that the cost function in penalty logic is directly related to the plausibility function in Dempster-Shafer theory via a logarithmic transformation. This bridges two distinct formalisms for reasoning under uncertainty.
  • Penalty Logic for Optimization: The paper shows that penalty logic can elegantly encode discrete optimization problems. By assigning penalties to constraints and costs to potential solutions (interpretations), finding the minimum cost interpretation directly yields the optimal solution.
  • Syntax-Based Reasoning: The approach is "syntax-based," meaning the behavior of the system depends on the specific formulation of the knowledge base, which can be both a strength (fine-grained control) and a potential weakness (sensitivity to representation).

Key Results

  • Formal definitions and properties of penalty logic, including cost functions for interpretations, formulas, and sub-theories.
  • A non-monotonic inference relation is derived from penalty logic, satisfying standard comparative inference properties.
  • A formal equivalence is established between the cost of an interpretation in penalty logic and the contour function derived from Dempster's combination of simple support functions.
  • Formula costs are shown to be related to plausibility measures in an infinitesimal version of Dempster-Shafer theory.
  • An example demonstrates how penalty logic can represent and solve the maximum clique problem.

Limitations and Future Work

  • Complexity: While the paper mentions that penalty non-monotonic deduction is among the simpler non-monotonic inference problems, practical applications might still require more efficient methods. The paper suggests exploring randomized search algorithms (like GSAT) or ATMS for candidate generation, though these may not guarantee optimality.
  • Gradual Inference: For practical applications, a gradual inference relation (rather than a strict binary one) might be more desirable, and the paper suggests this as a future direction.
  • Extensions: The authors propose extending penalty logic to handle multiple, unrelated penalties for a single formula (using penalty vectors) and to incorporate "profits" for satisfactions (using negative penalties).
  • Syntax Dependence: The syntax-based nature of the approach means that equivalent knowledge bases might behave differently, which is a common challenge in non-monotonic reasoning.

Summary updated

Abstract

Penalty logic, introduced by Pinkas, associates to each formula of a knowledge base the price to pay if this formula is violated. Penalties may be used as a criterion for selecting preferred consistent subsets in an inconsistent knowledge base, thus inducing a non-monotonic inference relation. A precise formalization and the main properties of penalty logic and of its associated non-monotonic inference relation are given in the first part. We also show that penalty logic and Dempster-Shafer theory are related, especially in the infinitesimal case.
BibTeX
@inproceedings{saintcyr1994penalty,
  author = {Florence Dupin de Saint-Cyr and Jérôme Lang and Thomas Schiex},
  title = {{Penalty Logic and its Link with Dempster-Shafer Theory}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1994},
  url = {https://openreview.net/forum?id=E5YDlv6S0S},
}

Loading related content...

Figure