Encoding formulas with partially constrained weights in a possibilistic-like many-sorted propositional logic

Salem Benferhat, Henri PradeIJCAI 2005

Introduction

In the field of automated reasoning, managing uncertainty is a fundamental challenge. Classical possibilistic logic provides a robust framework for this by assigning weights—typically numerical values between 0 and 1—to formulas to represent their certainty or priority. However, this approach relies on the assumption of a "total ordering," where every piece of information can be strictly ranked against every other piece. In real-world scenarios, particularly when merging data from heterogeneous sources, we often possess only partial knowledge of these priorities. This paper introduces a novel "two-sorted" propositional logic that treats uncertainty weights as symbolic variables, allowing for the formal representation and processing of partially constrained information.

The Problem: Beyond Total Ordering

Standard possibilistic logic struggles when confronted with qualitative or incomplete constraints. For instance, we might know that "Source A is more reliable than Source B," but have no information regarding how either compares to "Source C." Forcing these relationships into a numerical scale often requires inventing arbitrary values, which can lead to unjustified conclusions. The authors address this gap by proposing a framework that avoids numerical assignments in favor of symbolic weights and qualitative constraints (e.g., $a \ge b$), maintaining the integrity of the original partial information.

Methodology: A Two-Sorted Approach

The proposed framework utilizes a many-sorted propositional logic to bridge the gap between factual assertions and their associated certainties. The methodology is built upon several key pillars:

1. Dual Variable Sets

The logic employs two distinct sets of variables:

  • Fact Variables ($V$): Representing the actual propositions (e.g., "the sensor is active").
  • Weight Variables ($S$): Representing symbolic weights or "abnormality" conditions associated with those propositions.

2. Logical Encoding of Uncertainty

An uncertain formula $(p, a)$, which denotes that proposition $p$ is certain at least at level $a$, is translated into the logical clause $p \vee A$. In this context, the literal $A$ represents an "abnormal" state. The intuition is straightforward: either the proposition $p$ is true, or we are in an exceptional state where the information does not hold.

3. Constraint Mapping

Relationships between weights are translated into material implications. For example, the constraint $a \ge b$ is encoded as $A \to B$ (or $\neg A \vee B$). Furthermore, mathematical operations common in possibilistic logic are mapped to logical connectives: the max operation becomes logical conjunction ($\wedge$) and min becomes logical disjunction ($\vee$).

4. Inference via Variable Forgetting

To determine if a conclusion is plausible given a set of constraints, the system utilizes the concept of "forgetting" variables. By marginalizing out the factual variables ($V$) and focusing on the weight variables ($S$), the framework can ascertain whether the available constraints logically entail the desired conclusion.

Computational Efficiency and Knowledge Compilation

To ensure the framework is computationally feasible, the authors suggest leveraging knowledge compilation techniques. By compiling knowledge bases into Disjunctive Normal Form (DNF) or deterministic Decomposable Negation Normal Form (d-DNNF), the "forgetting" operation—which is generally hard—can be performed in polynomial time relative to the size of the compiled base. This moves the theoretical framework toward practical utility in automated reasoning tools.

Key Insights and Results

One of the most significant contributions of this work is the "abnormality link," where a certainty weight is treated as a literal representing an abnormal state. This allows for a unified framework where, if a total ordering of weights is provided, the system behaves exactly like traditional possibilistic logic, proving that the symbolic approach is a true generalization.

Theoretical Foundations

  • Soundness and Completeness: The authors provide a formal inference relation and demonstrate its soundness and completeness with respect to preferential model semantics.
  • Inconsistency Levels: The paper successfully defines a logical counterpart to the "inconsistency level" ($Inc(\Sigma)$), a crucial metric for identifying which conclusions remain reliable in the presence of conflicting data.
  • The Drowning Problem: The symbolic approach offers a potential solution to the "drowning problem," where a single high-priority contradiction in classical logic can cause the system to ignore multiple valid, lower-priority facts.

Limitations and Future Directions

While the theoretical groundwork is extensive, the authors acknowledge certain hurdles to practical implementation. The initial process of compiling a knowledge base into DNF or d-DNNF can be exponentially difficult for complex systems. Additionally, while the logic is sound, the paper does not provide empirical benchmarks or data on how the system scales to real-world expert systems containing thousands of variables. Future research is expected to focus on developing specialized tools for compiling standard possibilistic knowledge bases into this new many-sorted format and testing them against large-scale datasets.

Summary updated

BibTeX
@inproceedings{benferhat2005encoding,
  author = {Salem Benferhat and Henri Prade},
  title = {{Encoding formulas with partially constrained weights in a possibilistic-like many-sorted propositional logic}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
}
Figure