Incremental Learning of Linear Model Trees
Duncan Potts - University of New South Wales
A linear model tree is a decision tree with a linear functional model in each leaf. Previous model tree induction algorithms have operated on theentire training set, however there are many situations when an incrementallearner is advantageous. In this paper we demonstrate that model trees can beinduced incrementally using an algorithm that scales linearly with the numberof examples. An incremental node splitting rule is presented, together with incremental methods for stopping the growth of the tree and pruning. Empirical testing in three domains, wherethe emphasis is on learning a dynamic model of the environment, shows that thealgorithm can learn a more accurate approximation from fewer examples thanother incremental methods. In addition the induced models are smaller, and thelearner requires less prior knowledge about the domain.