Learning Boolean Functions in an Infinite Attribute Space

Avrim BlumMachine Learning 1992 · DOI

Introduction

In the early 1990s, computational learning theory was largely dominated by models that assumed a fixed, pre-defined vocabulary. In frameworks like Valiant’s Probably Approximately Correct (PAC) learning or Littlestone’s mistake-bound model, objects were typically represented as bit vectors of a fixed length $n$. This implied that the learner knew exactly which $n$ attributes existed in the universe from the outset.

In his 1992 paper, Avrim Blum challenged this "fixed-vocabulary" assumption, arguing that it is biologically and practically unrealistic. When a human learns a concept—such as what a "pencil" is—they do not process a list of every possible descriptor in the English language and mark most of them as "False." Instead, they focus on a small set of active attributes (e.g., wooden, yellow, writes). Blum’s work proposed a more realistic framework for learning in environments where the number of potential features is massive or even infinite, but each individual object is described by only a few.

The Infinite Attribute Model

Blum’s primary contribution is a theoretical model where an example is defined as a finite list of active attributes rather than a fixed-length vector. In this setting, the total number of possible attributes $A$ can be infinite.

This shift necessitates a fundamental change in how learning algorithms operate. In standard models, algorithms for learning disjunctions (OR-functions) often use an "elimination" strategy: they start with a hypothesis containing all $n$ possible attributes and delete those that contradict negative examples. In an infinite space, such an approach is impossible because the learner cannot enumerate the entire universe of attributes.

From Elimination to Growth

Blum proposes moving from elimination-based strategies to growth-based strategies. Rather than starting with a full hypothesis, the learner starts "empty." When it encounters positive examples, it adds attributes to its hypothesis. Negative examples are then used to prune or refine these attributes.

For more complex structures like $K$-CNF (conjunctions of clauses where each clause has at most $K$ literals), Blum introduced the "Seed" technique. The algorithm maintains small subsets of potential clauses, or "seeds." When the learner makes a mistake on a positive example, it "grows" these seeds by incorporating attributes found in that specific example, effectively discovering the relevant features of the concept on the fly.

Adapting the Winnow Algorithm

The paper also explores how to adapt Nick Littlestone’s Winnow algorithm—a linear threshold learner—to the infinite setting. Winnow is known for its ability to handle many irrelevant attributes in the standard model. Blum adapts this by using a "brute-force" discovery method: whenever the learner makes a mistake that cannot be explained by its current set of known attributes, it pulls in all attributes present in that example and initiates a weight-tuning process. This allows the learner to remain efficient even as it discovers new parts of the attribute space.

Key Results and Mistake Bounds

The strength of Blum's model lies in its mistake bounds—the maximum number of errors an algorithm will make before it perfectly learns a target concept. Crucially, these bounds scale with the complexity of the objects actually seen, rather than the size of the entire potential universe.

  • Monotone $K$-CNF: These are learnable with at most $(n+1)^K$ mistakes, where $n$ is the size of the largest example encountered.
  • General $K$-CNF: These can be learned with $O(rK \cdot n^K)$ mistakes, where $r$ is the number of clauses in the target function.
  • Efficient Disjunctions: By integrating the model with the Winnow algorithm, Blum demonstrated that a disjunction of $r$ literals can be learned with $O(r \log n)$ mistakes. This logarithmic dependence on the example size $n$ is a significant theoretical result, showing that learning can be highly efficient even in vast spaces.

Furthermore, Blum proved a general transformation: if a concept class is learnable in the standard model using membership queries (the ability to ask if a specific constructed object belongs to the concept), it can be adapted to the infinite attribute model with only a minor penalty in complexity.

Discussion and Philosophical Impact

Blum’s work represents a philosophical shift in how we treat "missing" attributes. In his model, an attribute not listed in an example is treated as "False" or simply "Unknown but irrelevant." This simplifies the logic required to navigate infinite spaces and more closely mirrors natural learning processes.

However, the paper also identifies several limitations that paved the way for future research:

  1. Decision Lists: While learnable in standard models, Blum identified Decision Lists (nested if-then-else logic) as a major open problem for the infinite attribute setting, as it was not immediately clear if they could be learned in polynomial time.
  2. Computational Constraints: While the "Halving Algorithm" proves that many concepts are theoretically learnable with enough computing power, the practical challenge remains finding computationally efficient versions for complex Boolean functions.
  3. Noise: The model assumes that attributes are reported perfectly. It does not account for the noise or sensor errors common in real-world infinite-dimensional data, such as web text or complex sensor arrays.

Conclusion

"Learning Boolean Functions in an Infinite Attribute Space" remains a foundational text in computational learning theory. By proving that we do not need to know the "size of the world" to learn effectively, Blum provided the mathematical justification for feature discovery and sparse representation, concepts that continue to underpin modern machine learning.

Summary updated

BibTeX
@article{blum1992learning,
  author = {Avrim Blum},
  title = {{Learning Boolean Functions in an Infinite Attribute Space}},
  journal = {Machine Learning},
  year = {1992},
  doi = {10.1007/bf00994112},
}
Figure