Dependency Bagging

Yuan Jiang, Jinjiang Ling, Gang Li, Honghua Dai, Zhi-Hua Zhou

TL;DR

This paper introduces "Dependency Bagging" (DepenBag), a novel ensemble learning algorithm that enhances traditional Bagging by incorporating causal discovery. By building dependency models (Directed Acyclic Graphs) from bootstrap samples, DepenBag identifies and removes attributes irrelevant to the class label within each sample, leading to more accurate and diverse component classifiers, particularly for k-nearest neighbor (k-NN) models.

What Problem Does This Paper Address?

Ensemble learning methods, which combine multiple models to improve predictive performance, have seen significant success. Bagging, a popular ensemble technique, generates multiple training sets through bootstrap sampling and trains a separate learner on each. While effective for "unstable" base learners like decision trees, Bagging struggles with "stable" learners such as k-NN classifiers. This is problematic because k-NN is widely used in real-world applications. The challenge is to adapt Bagging to effectively improve the performance of stable learners like k-NN. The paper aims to address this by introducing a mechanism to increase the diversity and accuracy of component k-NN classifiers within a Bagging framework.

Methods

The core innovation of DepenBag lies in its use of causal discovery to refine the training data for each component learner. The process is as follows:

  1. Bootstrap Sampling: Similar to standard Bagging, multiple bootstrap samples (Di) are drawn from the original dataset (D).
  2. Causal Discovery: For each bootstrap sample (Di), a causal discovery algorithm is employed to induce a dependency model, represented as a Directed Acyclic Graph (DAG). This DAG illustrates the probabilistic relationships between attributes.
  3. Irrelevant Attribute Removal: Within each DAG, attributes that have no direct or indirect connection to the class attribute are identified. These are considered "irrelevant" for predicting the class label within that specific bootstrap sample.
  4. Component Learner Training: The identified irrelevant attributes are removed from the corresponding bootstrap sample (Di). A base learner (e.g., k-NN) is then trained on this reduced sample.
  5. Ensemble Combination: The predictions from all trained component learners are combined, typically using majority voting.

The key novelty is the per-sample attribute removal based on causal dependency, which aims to create more focused and potentially more diverse learners compared to standard Bagging or methods that perform feature selection once on the entire dataset.

Datasets

The paper evaluates DepenBag on ten datasets from the UCI Machine Learning Repository. These datasets vary in size, number of categorical attributes, and number of continuous attributes. The specific datasets used are: wpbc, sonar, liver, ionosphere, vote, credit, diabetes, tic, german, and sick. All datasets have binary classes.

Key Insights and Ideas

  • Bagging's Struggle with Stable Learners: The paper highlights that standard Bagging doesn't always improve performance for stable learners like k-NN, a known limitation.
  • Diversity and Accuracy Trade-off: The core principle of ensemble learning is that both accuracy and diversity of component learners contribute to overall performance. DepenBag aims to enhance both.
  • Sample-Specific Feature Relevance: The crucial insight is that attribute relevance to the class label can vary across different bootstrap samples due to their unique data distributions. DepenBag exploits this by performing feature selection independently for each sample.
  • Causal Discovery as a Perturbation Tool: Causal discovery is used not just to find causal relationships but as a mechanism to perturb the input data by removing attributes that are statistically irrelevant in that specific sample, thereby increasing diversity.
  • Shared Irrelevant Attributes: Only attributes that are irrelevant across all bootstrap samples are considered truly useless and removed. This conservative approach prevents the removal of attributes that might be useful in other samples.

Key Results

The empirical study compares DepenBag with single k-NN classifiers and two other ensemble methods: Bagging and ReliefF-Bag (a Bagging variant with ReliefF feature selection).

  • Generalization Error: DepenBag consistently outperforms standard Bagging for k-NN classifiers, often showing significant improvements. It also generally outperforms ReliefF-Bag, suggesting that causal discovery-based feature selection is more effective than the ReliefF algorithm in this context. DepenBag is shown to be effective in building ensembles of k-NN classifiers.
  • Error-Ambiguity Decomposition: Analysis reveals that DepenBag achieves its performance gains by either decreasing the generalization error (E) or increasing the ambiguity (A) of component learners, or both. This indicates that DepenBag successfully generates more accurate and/or more diverse component classifiers.

Limitations and Future Work

  • Computational Cost: A significant limitation acknowledged is the increased computational cost due to the causal discovery process performed on each bootstrap sample. However, the authors suggest this cost might be acceptable for applications where a stronger ensemble is desired, especially if the causal discovery can be done offline.
  • Attribute Removal Strategy: The current attribute removal is conservative (only removing attributes irrelevant to all samples). Future work could explore removing attributes irrelevant to a subset of samples or based on a single sample's dependency model.
  • Applicability to Other Learners: While effective for k-NN, the paper suggests investigating DepenBag's performance with other stable learners (e.g., Naive Bayes) and even unstable learners (e.g., decision trees, neural networks).
  • Alternative Perturbation Schemes: The causal discovery approach is one way to perturb input attributes for diversity. Exploring other efficient and effective perturbation schemes for Bagging is a promising avenue for future research.

Summary updated

Abstract

In this paper, a new variant of Bagging named DepenBag is proposed. This algorithm obtains bootstrap samples at first. Then, it employs a causal discoverer to induce from each sample a dependency model expressed as a Directed Acyclic Graph (DAG). The attributes without connections to the class attribute in all the DAGs are then removed. Finally, a component learner is trained from each of the resulted samples to constitute the ensemble. Empirical study shows that DepenBag is effective in building ensembles of nearest neighbor classifiers.
BibTeX
@inproceedings{jiang2005dependency,
  author = {Yuan Jiang and Jinjiang Ling and Gang Li and Honghua Dai and Zhi-Hua Zhou},
  title = {{Dependency Bagging}},
  booktitle = {RSFDGrC},
  year = {2005},
  doi = {10.1007/11548669\_51},
}
Figure