On Belief Change for Multi-Label Classifier Encodings

Sylvie Coste-Marquis, Pierre MarquisIJCAI 2021 · DOI

TL;DR

This paper introduces "rectification," a novel belief change operation designed to minimally modify multi-label classifier encodings (represented as Boolean circuits) to align with a more reliable background theory. This work bridges the gap between machine learning and symbolic reasoning by providing a principled way to integrate background knowledge into learned models, ensuring consistency without sacrificing the classifier's structure.

What Problem Does This Paper Address?

Integrating learning and reasoning is a major goal in AI, particularly in areas like neural-symbolic computation and statistical relational learning. A key challenge is leveraging existing background knowledge (T) to improve machine learning classifiers (C), making them more accurate and robust. While some methods use background knowledge during the learning phase, this paper focuses on a scenario where the classifier is already learned, and the training data is unavailable. In this situation, the classifier itself needs to be modified to comply with the background theory.

The authors note that recent advancements allow representing classifiers as Boolean circuits (Σ). This opens up the possibility of treating the problem of making a learned classifier Σ comply with a background theory T as a belief change problem. However, standard belief change operations like revision and update are not well-suited for this task because they don't preserve the crucial "XY-classification property" required for classifier encodings. This property ensures that for every input instance, the classifier produces a unique output classification. Therefore, a new, specialized belief change operation is needed.

Methods

The core contribution is the introduction of a new belief change operation called rectification. This operation aims to minimally modify a classifier's Boolean circuit representation (Σ) to comply with a background theory (T), which is assumed to be more reliable.

Key aspects of their approach include:

  • Logical Characterization of Classifiers: They define what it means for a propositional representation to be an "XY-classification circuit," which is a formal way to represent multi-label classifiers. This involves ensuring that for any input features (X), the circuit uniquely determines the output labels (Y).
  • Notions of Compliance: They propose several ways a classifier (Σ) can "comply" with a background theory (T):
  • Classification-compliant: Σ and T classify the same instances in the same way.
  • Knowledge-compliant: Σ's classification of an instance is consistent with what T implies about that instance's classification.
  • Fact-compliant: Σ's classification of an instance is consistent with the direct implications of T regarding that instance's class membership. Fact-compliance is the least stringent.
  • Rectification Operators: They define a family of rectification operators (denoted by ) that take a classifier circuit Σ and a background theory T and produce a rectified circuit ΣT. These operators must satisfy specific postulates:
  • (RE1) XY-classification Property Preservation: The output Σ*T must still be a valid classifier encoding.
  • (RE2) Minimal Change (Fact-Compliance): If Σ is already fact-compliant with T for an instance, its classification should not be changed.
  • (RE3) Primacy of T: For instances where Σ is not fact-compliant, Σ*T must align with T's implications (specifically, it must be fact-compliant with T).
  • (RE4) Inconsistent T: If T is inconsistent, Σ should remain unchanged.
  • (RE5) Syntax Independence: The operation should be independent of the specific representation of Σ and T.
  • (RE6) Variable Independence: The operation should only depend on variables relevant to classification (X and Y).
  • Specific Rectification Operators: They propose two concrete types of rectification operators:
  • Dalal Revision-based (*D): Uses a revision operator to adjust Σ's output for each instance based on T.
  • Selection Function-based (*s): Uses a selection function to choose a specific model of T's output for instances where Σ is not fact-compliant.

Datasets

Not discussed in the paper. The paper focuses on theoretical formalisms and algorithmic properties rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The Need for a New Belief Change Operation: Standard belief revision and update operators are insufficient because they don't guarantee the preservation of the XY-classification property, which is fundamental for a Boolean circuit to represent a classifier. Rectification is specifically designed to address this.
  • Hierarchy of Compliance: The paper establishes a clear hierarchy of compliance notions (classification > knowledge > fact). This allows for flexibility in how strictly the rectified classifier must adhere to the background theory.
  • Primacy of Background Theory: The rectification framework explicitly prioritizes the background theory (T) over the learned classifier (Σ), reflecting a common scenario where background knowledge is considered more reliable.
  • Computational Hardness and Tractable Subsets: While computing rectified classifications is generally NP-hard, the paper identifies specific propositional languages (like DNNF) that allow for tractable computation, making the approach practical in certain settings.
  • Disjointness from Standard Operators: Axiomatically, rectification operators are shown to be distinct from standard belief revision and update operators, highlighting its novelty.

Key Results

  • Axiomatic Characterization of Rectification: The paper defines a set of postulates (RE1-RE6) that characterize rectification operators and demonstrates that such operators exist.
  • Disjointness of Operator Families: Rectification operators are proven to be axiomatically distinct from KM revision and KM update operators.
  • Computational Complexity:
    • Computing rectified classifications is generally NP-hard and coNP-hard, even for simplified inputs.
  • However, for specific languages like DNNF that support certain knowledge compilation operations (CD, FO, CO), computing rectified classifications becomes polynomial-time tractable.
  • Evaluating the "knowledge compliance degree" of a classifier with a theory is #P-hard in general but becomes polynomial-time tractable under similar language assumptions.

Limitations and Future Work

  • Representation Size: The rectified representations (ΣT and ΣsT) can be exponentially large in the number of features, making their computation impractical in many cases. The authors suggest looking for more succinct representations.
  • Operator Strengths: The paper discusses stronger compliance notions (knowledge-compliance and classification-compliance) and suggests exploring operators that satisfy these stronger conditions.
  • Representation Theorems: The authors plan to derive representation theorems for rectification operators, providing constructive characterizations of their family.
  • Empirical Evaluation: While the paper focuses on theoretical foundations and computational complexity, future work would involve empirical evaluation on real-world datasets to demonstrate the practical benefits of rectification.

Summary updated

BibTeX
@inproceedings{costemarquis2021belief,
  author = {Sylvie Coste-Marquis and Pierre Marquis},
  title = {{On Belief Change for Multi-Label Classifier Encodings}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/252},
}
Figure