Bottom-Up Induction of Oblivious Read-Once Decision Graphs: Strengths and Limitations

Ron KohaviAAAI 1994

Abstract

This paper investigates improvements to HOODG, an algorithm for the bottom-up induction of Oblivious Read-Once Decision Graphs (OODGs). By allowing paths to reconverge, OODGs overcome the "replication problem" and "fragmentation problem" that limit standard decision trees. We demonstrate that HOODG is exceptionally effective at learning complex logical concepts, such as parity and symmetric functions, while remaining competitive on real-world classification tasks.

Introduction

Standard decision tree induction algorithms like ID3 and C4.5 are foundational to machine learning but possess inherent structural flaws. The replication problem occurs when a tree must duplicate subtrees to represent certain logical concepts (e.g., $A \land B \lor C \land D$), leading to bloated models. The fragmentation problem arises when high-arity attributes split data into small subsets, reducing the statistical significance of decisions at lower nodes.

Oblivious Read-Once Decision Graphs (OODGs) offer a solution. As Directed Acyclic Graphs (DAGs), OODGs allow paths to merge. They are "oblivious" because every node at a given level tests the same variable, and "read-once" because each variable is tested at most once on any path.

Methods: Bottom-Up Induction

The paper focuses on HOODG, a greedy hill-climbing algorithm that constructs OODGs from the bottom up. Unlike top-down splitting, HOODG starts with the final category labels and works backward to the root, grouping instances into sets that correspond to nodes at the preceding level.

Example of an OODG structure showing node reconvergence and level-based variable testing.

Key components of the method include:

  • Greedy Variable Ordering: The algorithm selects variables that minimize the "width" (number of nodes) of the next level. Although finding the absolute minimal width is NP-complete, this greedy approach is locally optimal for fully specified functions.
  • Least Commitment Heuristic: To handle incomplete real-world data, HOODG uses a heuristic to assign missing values in a way that keeps the graph as slim as possible.

Experimental Evaluation

The algorithm was evaluated on synthetic logical benchmarks (Monk’s Problems, Parity, Multiplexer 6) and real-world datasets (U.S. House votes, Wisconsin breast cancer).

Key Results

HOODG demonstrated significant advantages in specific domains:

  • Logical Dominance: On the Monk 1 and Parity datasets, HOODG achieved 100% accuracy, vastly outperforming ID3 and C4.5, which struggle with subtree replication.
  • Real-World Versatility: Performance on the Vote and Breast Cancer datasets was comparable to C4.5, indicating that the OODG inductive bias is applicable beyond pure logic.
Comparison of HOODG against ID3, C4.5, and DGRAPH across various datasets.

Discussion and Limitations

OODGs excel at representing symmetric functions in polynomial size, whereas decision trees often require exponential size. However, HOODG has limitations:

  1. Noise Sensitivity: The current implementation assumes clean data; future work must incorporate pruning techniques.
  2. Variable Ordering: Greedy selection can fall into global sub-optimals; deeper lookahead strategies may be required.
  3. Continuous Features: The framework currently handles only discrete variables.

In conclusion, HOODG provides a powerful alternative to decision trees for problems characterized by level-decomposable structures, offering superior generalization for complex logical concepts.

Summary updated

BibTeX
@inproceedings{kohavi1994bottom,
  author = {Ron Kohavi},
  title = {{Bottom-Up Induction of Oblivious Read-Once Decision Graphs: Strengths and Limitations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure