Abstract
In incremental concept learning, identifying the most informative experiment to refine a version space is a computationally intensive task, often scaling exponentially with the complexity of the concept language. This paper introduces Factorization, a technique that exploits independence between attributes (such as color and shape) to decompose a massive hypothesis space into smaller, manageable factors. This approach transforms an NP-hard search problem into a linear one, significantly accelerating the learning process.
Introduction: The Challenge of Experiment Generation
A central problem in machine learning is "discrimination-experiment generation." Given a set of hypotheses consistent with observed data (the version space), the system must select a test instance to present to a teacher. Ideally, this instance should be "optimal"—one that, regardless of the teacher's label, eliminates roughly half of the remaining hypotheses.
As the number of features and their possible values grow, the size of the version space explodes. Searching for the optimal instance becomes practically infeasible for complex domains. The authors address this bottleneck by leveraging structural independence within the concept language.
Methodology: Cartesian Factorization
The core innovation is the use of Cartesian Factorization. If a concept can be represented as a conjunction of independent parts—for example, a "red wedge" being defined by its color ("red") and its shape ("wedge")—the version space can be treated as a Cartesian product of smaller sub-spaces.
Structural Decomposition
The version space is represented as a Directed Acyclic Graph (DAG). By applying graph theory algorithms, the system can automatically identify "prime factors" of these DAGs. This allows the learner to treat the search for an experiment as a set of parallel searches in smaller dimensions.
Credit Assignment Strategies
When a teacher provides feedback, the learner must update its version space. The paper discusses two main strategies:
- Independent Credit Assignment (ICA): If the teacher specifies why an instance failed (e.g., "wrong color"), the learner updates only the relevant factor.
- Non-ICA Strategy: If the teacher only provides a binary "yes/no," the learner uses a "near-miss" strategy. It generates a composite instance from the best candidates of each factor and then uses follow-up questions to isolate the cause of any negative feedback.
Evaluation and Results
The authors evaluated their approach using the Blocks World domain, specifically focusing on the classic "Winston’s Arch" problem. The vocabulary included attributes like color (red, green) and shape (cube, brick, wedge, pyramid).
Complexity and Efficiency
The primary result is a dramatic reduction in time complexity. Instead of $O(|VS| \cdot |I|)$, where $|VS|$ is the size of the version space, the factored approach operates in $O(k \cdot n \cdot m)$, where $k$ is the number of factors. This represents a shift from exponential to linear scaling relative to the number of independent features.
In the Arch problem, an unfactored version space contained nearly 20,000 hypotheses ($3^9$). By factoring it into three sub-spaces of size 27, the system successfully converged on the correct concept using only 9 experiments. The table in Figure 5 illustrates how the "Best" instance is calculated by evaluating the expected information gain ($E$) across these factors.
Key Insights
- Independence is Power: Domain-independent knowledge about attribute independence (e.g., shape doesn't affect color) transforms a problem of size $n^k$ into $k$ problems of size $n$.
- Semantic Independence: The authors demonstrate that the syntactic operation of graph factoring corresponds directly to logical independence in the concept language.
- The Cost of Credit: While factoring simplifies experiment generation, it may increase the number of questions needed if the teacher does not provide specific reasons for failure. The paper provides a formal cost-benefit analysis for this trade-off.
Limitations and Future Directions
The current framework assumes that all hypotheses are initially equally likely, an assumption that may not hold in real-world scenarios. Additionally, while the system handles "clean" Cartesian products well, many domains exhibit "partial independence" where factors share variables. Extending the logic to handle these overlaps and more complex disjunctive concepts (A OR B) remains a subject for future research.
Summary updated