Learning with Many Irrelevant Features

Hussein Almuallim, Thomas G. DietterichAAAI 1991

Introduction

In machine learning, the presence of irrelevant features often degrades the performance of standard algorithms. This classic 1991 paper by Hussein Almuallim and Thomas G. Dietterich addresses this fundamental challenge by formalizing the MIN-FEATURES bias. The authors demonstrate that while popular algorithms like ID3 are easily "distracted" by irrelevant data, an algorithm explicitly designed to minimize the number of features can learn effectively even in high-dimensional noise.

The MIN-FEATURES Bias and the FOCUS Algorithm

The core contribution of the paper is the definition of the MIN-FEATURES bias: given multiple hypotheses that explain the training data, the learner should prefer the one defined over the fewest possible input features. This is a semantic bias toward variable simplicity, distinct from the syntactic bias toward small tree structures found in algorithms like ID3.

To implement this bias, the authors introduced the FOCUS algorithm. FOCUS operates in two stages:

  1. Feature Selection: It exhaustively searches for the smallest subset of features $A$ such that no two training examples have identical values for $A$ but different labels.
  2. Hypothesis Construction: Once the minimal set is identified, it builds a consistent hypothesis using only those features.

Theoretical Foundations

Using the Probably Approximately Correct (PAC) learning framework, the authors derived bounds for sample complexity. A key theoretical insight is that the number of training examples $m$ required to learn a concept with $p$ relevant features out of $n$ total features is:

$$m = O\left(\frac{1}{\epsilon} \ln \frac{1}{\delta} + \frac{1}{\epsilon} [2^p + p \ln n]\right)$$

Crucially, the total number of features $n$ appears within a logarithm. This implies that irrelevant features only impose a logarithmic cost on sample complexity, meaning we do not need exponentially more data to handle "junk" features.

Empirical Evaluation

The authors compared FOCUS against ID3 and FRINGE using synthetic Boolean concepts. The experiments highlighted a significant "distraction" effect in traditional algorithms as the feature space grows.

Accuracy vs. Number of total attributes, showing FOCUS's robustness to irrelevant features compared to ID3 and FRINGE.

As shown in the figure above, as the number of irrelevant features increases, the accuracy of ID3 and FRINGE drops significantly (from ~90% to ~65%). In contrast, FOCUS maintains near-perfect accuracy, demonstrating its ability to successfully isolate the relevant feature subset regardless of the noise.

Furthermore, the efficiency gap in terms of required training data is stark. As the number of features grows, ID3 requires orders of magnitude more examples to achieve the same confidence as FOCUS.

Table showing the number of examples required to reach a target confidence level as the number of features increases.

For instance, to learn a concept with 12 total features, ID3 required 2,236 examples, whereas FOCUS achieved the same result with only 42. This highlights the practical power of the MIN-FEATURES bias in sample-constrained environments.

Conclusion and Limitations

While FOCUS is highly sample-efficient, it faces a computational cost challenge. The exhaustive search for the minimal feature set is $O(n^p)$, making it "quasi-polynomial" and potentially impractical if the number of relevant features ($p$) is large. Additionally, the original algorithm assumes noise-free data. Despite these limitations, the paper established that irrelevant features are theoretically manageable and that explicit feature selection is a powerful tool for robust learning.

Summary updated

BibTeX
@inproceedings{almuallim1991learning,
  author = {Hussein Almuallim and Thomas G. Dietterich},
  title = {{Learning with Many Irrelevant Features}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure