TL;DR
This paper introduces "linked decision forests," a novel representation that avoids redundant sub-structures in decision trees, leading to more efficient learning. They also present "Lumberjack," a supervised learning algorithm that builds these forests, demonstrating improved generalization accuracy on hierarchically decomposable concepts compared to standard decision trees.
What Problem Does This Paper Address?
Decision trees are powerful tools for concept representation, but they can become inefficient when a subconcept needs to be represented multiple times in different parts of the tree. This redundancy means that the same sub-structure must be learned repeatedly, potentially using only a subset of the available data for each instance. This is particularly problematic in domains like reinforcement learning, where these repeated structures can be viewed as subtasks or macros that are relearned unnecessarily. The paper aims to address this inefficiency by proposing a representation that can factor out and share these common sub-structures.
Methods
The core innovation is the linked decision forest representation. Unlike traditional decision trees, a linked forest is a collection of trees where inter-tree references are allowed. These references can be either "value references" (like a jump) or "attribute references" (like a function call). This allows a sub-concept to be represented once and then referenced from multiple locations, eliminating redundancy.
The paper also introduces the Lumberjack algorithm for learning these linked forests. Lumberjack builds upon the SEQUITUR algorithm's idea of detecting common subsequences. It works by iteratively adding decision nodes to a forest, while maintaining a hash table of "di-nodes" (pairs of parent-child internal nodes). When duplicate di-nodes are detected, they are extracted to form a new "attribute tree," and the original di-nodes are replaced with references to this new tree. This process effectively factors out repeated substructures. The algorithm uses the Minimum Description Length (MDL) principle to guide the learning process and determine when to stop growing the forest.
Datasets
The paper evaluates Lumberjack on two types of datasets:
- Boolean function ABC V DEF V GHI: This dataset was generated by sampling with replacement and introducing 10% noise. The testing dataset was clean.
- Robot Maze Problem: This dataset was derived from a reinforcement learning problem where a robot learns to navigate a maze. The problem was mapped to a supervised learning setting, and training datasets were generated by random sampling with replacement from a true dataset. The testing dataset was the full true dataset.
Key Insights and Ideas
- Shared Substructure is Key: The fundamental insight is that many decision trees contain significant structural redundancy. By explicitly representing and sharing these common sub-structures, we can achieve more efficient learning and better generalization.
- Linked Forests as a Solution: The linked decision forest provides a formal mechanism to represent these shared substructures, moving beyond simple decision trees. The distinction between "value references" and "attribute references" is crucial for managing control flow within the forest.
- Lumberjack's SEQUITUR Inspiration: The algorithm's ability to detect and factor out repeated structures is inspired by string-processing algorithms like SEQUITUR, adapted for tree structures. The use of di-nodes and a hash table is an elegant way to identify these commonalities.
- MDL for Guidance and Stopping: Employing the Minimum Description Length principle provides a principled way to select the best splits and determine when the learning process should terminate, balancing model complexity with data fit.
Key Results
The paper reports improved generalization accuracy for Lumberjack compared to a standard decision tree learner on both datasets.
- Boolean Function: Significant differences in error rate were observed for sample sizes between 1000 and 3000, favoring Lumberjack.
- Robot Maze Problem: Significant differences were found for sample sizes of 2000 or more, with Lumberjack outperforming the decision tree. The authors note that at larger sample sizes, the decision tree begins to converge as it gains enough data to learn the repeated structure.
Limitations and Future Work
- No Leaf Joining: A noted limitation is that Lumberjack currently only decomposes internal nodes and does not join leaves, even when this might be beneficial (as seen in some decision graph approaches).
- Attribute Trees Only: The current implementation only forms "attribute trees" (trees referenced by attribute references), not "value trees" (trees referenced by value references).
- Comparison with C4.5: The authors mention that their MDL-based system is always significantly worse than C4.5 (a popular decision tree algorithm) when using MDL coding. However, they state that C4.5 and Lumberjack perform similarly with 1000 or more data points, suggesting that Lumberjack's benefits become apparent with sufficient data.
Future work could explore incorporating leaf joining and the formation of value trees to further enhance the representation's power.
Summary updated