Learning Terminological Naive Bayesian Classifiers under Different Assumptions on Missing Knowledge

Pasquale Minervini, Claudia d'Amato, Nicola FanizziURSW 2011 · OpenReview

TL;DR

This paper introduces a novel machine learning approach for building "terminological naive Bayesian classifiers" that can effectively handle missing knowledge in Semantic Web data. By explicitly modeling different types of missingness (MCAR, MAR, NMAR), their method provides more robust and accurate predictions than existing approaches.

What Problem Does This Paper Address?

The Semantic Web (SW) aims to represent knowledge in a way that machines can understand and process. However, real-world data is often incomplete. This incompleteness is exacerbated by the "Open World Assumption" (OWA) inherent in many SW standards like OWL, which means that if something isn't explicitly stated as true, it's not necessarily false. This leads to a significant challenge: how to build predictive models when crucial information might be missing. Existing machine learning methods often struggle with this, either assuming data is "Missing at Random" (MAR) or ignoring the nuances of missingness, leading to potentially inaccurate results. This paper tackles the problem of learning predictive models (specifically, Bayesian classifiers) from SW data that explicitly accounts for the different ways knowledge can be missing due to the OWA.

Methods

The core contribution is a Statistical Relational Learning (SRL) system designed to learn "terminological naive Bayesian classifiers." These classifiers are essentially naive Bayesian networks where the "features" are Description Logic (DL) concepts, and the "class" is a target concept. The key innovation lies in how they handle missing knowledge:

  • Terminological Naive Bayesian Classifiers: They define a classifier as a naive Bayesian network structure where nodes represent DL concepts (features) and a target concept. The network models the conditional dependencies between these concepts.
  • Handling Different Ignorance Models: The paper categorizes missing knowledge into three types:
  • MCAR (Missing Completely at Random): Missingness is independent of any available knowledge.
  • MAR (Missing at Random): Missingness depends on observed knowledge.
  • NMAR (Not Missing at Random / Informatively Missing): Missingness depends on the missing knowledge itself.
  • Learning Algorithms:
    • For MCAR, they use an "available case analysis" approach, building an unbiased estimator based only on available data and calculating the log-likelihood.
  • For MAR, they employ the Expectation-Maximization (EM) algorithm. This involves an "Expectation step" to estimate the distribution of missing values and a "Maximization step" to update network parameters based on these estimates.
  • For NMAR, they propose two strategies: either extending the model to treat observability as an additional variable (making it MAR) or using Robust Bayesian Estimation (RBE) to learn probability intervals instead of single values, reflecting the uncertainty.
  • Structure Learning: The system uses a greedy search algorithm (Alg. 1) that incrementally adds DL complex concepts as features to the classifier, aiming to maximize a scoring function.

Datasets

The paper does not explicitly mention specific benchmark datasets used for training or evaluation. Instead, it describes the learning problem in terms of a generic DL Knowledge Base (KB) K = (T, A) and sets of positive, negative, and neutral training individuals. The examples provided are illustrative, using simple DL concepts like Female, HasChild, and Father.

Key Insights and Ideas

  • The OWA is a double-edged sword: While enabling flexibility, it fundamentally introduces uncertainty about missing knowledge, which standard ML models often overlook.
  • Not all missing data is created equal: Differentiating between MCAR, MAR, and NMAR is crucial for building accurate models. Treating NMAR data as MAR can lead to significant errors.
  • SRL is a natural fit for SW: Combining logic (DL concepts) with probabilistic reasoning (Bayesian networks) is a powerful way to model complex, relational SW data.
  • Probability intervals for NMAR: For the most challenging type of missingness (NMAR), learning probability intervals (as in Robust Bayesian Estimation) is a more principled approach than trying to force point estimates.

Key Results

The paper focuses on the methodology and algorithms rather than presenting extensive quantitative results on specific datasets. However, it outlines how their algorithms (EM for MAR, RBE for NMAR) are designed to provide more robust classifications by accounting for different missingness assumptions. The effectiveness is demonstrated through illustrative examples, showing how the probability of an individual belonging to a target concept can be inferred even with incomplete information.

Limitations and Future Work

  • Structure Learning: While the paper describes a greedy search for feature concepts, it notes that a method for searching for structures other than naive Bayesian networks has not yet been implemented.
  • Computational Complexity: Exhaustively searching for optimal network structures can be computationally prohibitive.
  • Future Work: The authors aim to:
  • Computationally estimate the ignorance model for each feature.
  • Develop new methods to exploit the information contained in missingness.
  • Evaluate their methods' effectiveness on real-world ontologies.

Summary updated

BibTeX
@inproceedings{minervini2011learning,
  author = {Pasquale Minervini and Claudia d'Amato and Nicola Fanizzi},
  title = {{Learning Terminological Naive Bayesian Classifiers under Different Assumptions on Missing Knowledge}},
  booktitle = {URSW},
  year = {2011},
  url = {https://openreview.net/forum?id=S-5in5Hu_nZ},
}
Figure