Using Learning to Improve the Computational Performance of the Simulation of a Modeled Environment
W. McD. Armstrong · 2005
Decision trees are a common way to solve classification problems. Methods for learning such trees using information-theoretic heuristics are well known. However, existing learning methods do not consider the cost of evaluating the learned decision tree. This thesis describes a learning algorithm which incorporates a new decision procedure for selecting nodes in a decision tree. This procedure imbues established information-gain methods with an awareness of the consequences of their choices in the terms of evaluation speed of the learned tree. The new algorithm chooses attributes for the tree based on a measure of their bit-rate, or how fast they produce information. An empirical comparison was conducted between the new, speed-aware method, and a standard one based purely on information theory. It was found that significantly different trees are generated by the two methods. Evaluation of these trees was conducted in terms of two metrics: precision and speed. The new method produced trees which were significantly faster than those produced by the standard method the gain ranged between 3% and 24%, depending on the number of objects in the world being classified. Additionally, while the standard method could not outperform the baseline speed of the function it was approximating, the newmethod recorded such an improvement in speed that it was faster than executing the untutored function. These gains in speed did not result in a decrease in accuracy over the traditional method.