Tree-Structured Bias

Stuart J. RussellAAAI 1988

Abstract

Autonomous agents must be able to construct their own hypothesis spaces from raw data and background knowledge to achieve true independence. This paper proposes a method for deriving these spaces using background knowledge expressed as logical determinations. By demonstrating that these derivations naturally form tree structures, the author demonstrates that this "tree-structured bias" significantly reduces learning complexity from doubly-exponential to singly-exponential, enabling more efficient concept learning from fewer examples.

Introduction: The Challenge of Unbiased Learning

In traditional machine learning, human programmers typically design the hypothesis space—the set of all possible rules an agent can learn. However, for an agent to be truly autonomous, it must be able to construct this space itself. The fundamental challenge is that "unbiased" learning is computationally intractable; without constraints, the number of possible concepts for $n$ boolean features is $2^{2^n}$. For instance, with just 4 features, there are 65,536 possible concepts, making it impossible to learn from a small number of examples. This paper seeks a "strong but natural" bias that restricts this space without requiring hard-coded rules.

Methodology: Declarative and Tree-Structured Bias

The author introduces the concept of Declarative Bias, where the hypothesis space is derived from background knowledge using first-order logic. The approach relies on several key technical components:

  1. Determinations: Logical statements of the form $P \succ Q$ (read as "$P$ determines $Q$"), indicating that if two objects match on property $P$, they must match on property $Q$.
  2. Backward Chaining: The system starts with a goal concept and works backward through a chain of determinations to identify "operational" features.
  3. Tree-Structured Derivation: Because determinations are linked via an extended transitivity rule, the derivation process naturally forms a tree. Each internal node represents a functional combination of its children.
A tree-structured derivation where a goal concept $Q$ is determined by a hierarchy of operational features $P_i$.

Key Insights: The Power of Structure

The central insight of this work is that the structure of a logical proof serves as a powerful bias. When a concept is derived through a tree of intermediate steps, it limits the ways features can interact. Features in one branch of the tree can only interact with features in another branch through the function defined at their common ancestor node.

This structural constraint leads to a massive reduction in complexity. In a "flat" space of $n$ features, there are $2^{2^n}$ possible boolean functions. The paper proves that if the branching factor of the derivation tree is bounded by a constant $k$, the number of possible functions becomes exponential in $n$ (roughly $(2^{2^k})^{n-1}$), rather than doubly exponential.

Examples of tree structures with different branching factors, illustrating how the hypothesis space complexity depends on the tree's degree.

Key Results and Quantitative Impact

The mathematical core of the paper is Theorem 4, which states that for a tree-structured bias with a bounded degree of branching, the number of rules consistent with the bias is exponential in the number of leaf nodes.

To illustrate this, the author provides a concrete example: for a balanced, four-leaf binary tree, the number of possible rules is reduced from 65,536 in a flat bias to just 520. Furthermore, using the framework of PAC (Probably Approximately Correct) learning, the author shows that this reduction allows a concept to be learned with high probability from a linear number of examples, rather than an exponential one.

Limitations and Future Directions

While promising, several hurdles remain:

  • Observability: Internal nodes (intermediate concepts) are often not observable, requiring the learner to infer hidden functional relationships.
  • Computational Complexity: While polynomial-time algorithms exist for "monotone" functions, the general non-monotone case remains difficult.
  • Complex Derivations: The current theory assumes simple trees where each feature appears once; future work must address more complex graphs and overlapping features.
  • Integration: Further research is needed to understand how tree-structured bias interacts with other constraints, such as conjunctive biases or predicate hierarchies.

Summary updated

BibTeX
@inproceedings{russell1988tree,
  author = {Stuart J. Russell},
  title = {{Tree-Structured Bias}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}

Loading related content...

Figure