This paper, presented at IJCAI 2015, introduces a new formal framework for AI agents to reason about not just what they believe, but why they believe it—even when that information is uncertain. By merging Justification Logic (which tracks evidence) with Possibilistic Logic (which handles degrees of certainty), the authors create Possibilistic Justification Logic (PJL).
TL;DR
The authors develop Possibilistic Justification Logic (PJL), a framework that allows AI systems to track the specific evidence behind uncertain beliefs. This logic enables agents to maintain "justified" degrees of certainty and provides a mathematical way to pinpoint the source of contradictions in a knowledge base.
What Problem Does This Paper Address?
In classical epistemic logic (the logic of knowledge), we usually say an agent knows something using a box symbol: $\Box \phi$ ("It is known that $\phi$"). However, this treats knowledge as a black box—it doesn't tell us the reason or evidence for that knowledge.
Justification Logic (JL) solved this by replacing the box with a "justification term" ($t : \phi$), meaning "term $t$ is the reason for believing $\phi$." But standard JL is binary: you either have a justification or you don't. In reality, beliefs are often uncertain. While "Graded Modal Logics" can handle degrees of certainty (e.g., "I am 80% sure $\phi$ is true"), they lose the "why."
The authors address this gap: How can an agent reason about evidence ($t$) while also accounting for the fact that the evidence might only provide a certain degree of confidence ($\alpha$)?
Methods
The authors introduce Possibilistic Justification Logic (PJL). The core of their method involves:
- Syntax Expansion: They introduce formulas like $t :_\alpha \phi$, which reads: "According to evidence $t$, $\phi$ is believed with a certainty of at least $\alpha$."
- Kripke-Fitting Models: They extend standard semantics to include a "fuzzy accessibility relation." In this setup, worlds aren't just "reachable" or "not reachable"; they have a degree of possibility. They combine this with an admissible evidence function that determines if a specific term $t$ is valid evidence for a claim $\phi$ in a given world.
- Axiomatization ($J^\Pi$): They provide a set of formal rules (axioms) for PJL. This includes "Application" (if you have evidence for $A \to B$ and evidence for $A$, you can combine them to get evidence for $B$) and "Sum" (combining two pieces of evidence for the same claim).
- Internalization: They prove that any logical derivation within the system can be tracked by a justification term—essentially, the logic can "commentate" on its own reasoning process.
Datasets
As a theoretical logic paper, no empirical datasets were used. The authors evaluate their logic using formal proofs of soundness and completeness. They also use a qualitative "toy example" involving a classic AI problem: reasoning about whether "Tweety" (a penguin) can fly, given conflicting rules about birds and penguins.
Key Insights and Ideas
- The "Why" of Uncertainty: PJL allows an agent to say, "I am uncertain about $X$, and here is the specific chain of evidence that led to that uncertainty."
- Inconsistency Tolerance: This is the "aha moment" of the paper. In standard logic, a single contradiction (like "Tweety can fly" and "Tweety cannot fly") ruins the entire system. In PJL, because every claim is tied to a justification term and a certainty level, the agent can "debug" the contradiction. It can look at the justification terms to see exactly which default rule or observation caused the clash and adjust the certainty of that specific "weak link" rather than discarding all information.
- Forgetful Projection: The authors show that if you "forget" the justification terms in PJL, you are left with Quantitative Modal Logic (QML). This proves that PJL is a mathematically sound "explicit" version of existing uncertainty logics.
Key Results
- Soundness and Completeness: The authors mathematically prove that their logic is consistent (it doesn't produce nonsense) and complete (everything that is true in the model can be proven by the rules).
- Realization Theorem: They prove a correspondence between PJL and QML, showing that any uncertain belief in QML can be "realized" with a specific justification term in PJL.
- Conservative Extension: They demonstrate that PJL is a faithful extension of standard Justification Logic; it adds uncertainty without breaking the original logic's properties.
Limitations and Future Work
- Computational Complexity: The paper does not discuss how "heavy" it is to compute these justifications. In a massive knowledge base, tracking every term could become computationally expensive.
- Introspection: The current version doesn't fully explore "knowing that you know" (positive/negative introspection) in the context of uncertainty.
- Multi-Agent Systems: The logic currently handles a single agent. The authors suggest extending this to scenarios where multiple agents share and justify uncertain beliefs to one another.
- Probabilistic Logic: PJL is based on possibility theory (which deals with "ease of attainment"). The authors note that a probabilistic version of justification logic would be a valuable but distinct future direction.
Summary updated