Applications of information theory to pattern recognition and the design of decision trees and trellises
Robert M. Gray, Philip A. Chou · 1988
An information-theoretic approach to pattern recognition is derived and used to develop new or improved algorithms for designing decision trees for pattern classification. Pattern classification is treated as data compression in a distortion-rate framework, by equating the distortion of a pattern classifier to its probability of error, and by equating the rate of a pattern classifier to its average number of discriminant function evaluations. Sequential pattern classifiers are interpreted as decision trees, which in turn are interpreted as variable length encoder/decoder pairs. Distortion-rate bounds and other insights from the theory and practice of data compression are applied to decision trees and more generally to pattern classifiers. In particular, algorithms are developed for growing decision trees in the distortion-rate plane, optimal pruning of decision trees in the distortion-rate plane, and optimal merging of decision trees to form decision trellises. The growing algorithm, which is a simple extension of the prevalent decision tree design algorithm, permits whole series of trees at different performance levels to be designed simultaneously. The optimal pruning algorithm, which is a generalization of an algorithm by Breiman, Friedman, Olshen, and Stone, chooses a sequence of pruned subtrees that traces the convex hull of the operational distortion-rate function. The optimal merging algorithm, which is an iterative descent algorithm formally equivalent to the generalized Lloyd algorithm for designing vector quantizers, finds a partition of feature space that retains the maximum amount of mutual information about the unknown class. The latter two algorithms rely on generalizations of theorems by Brieman et al., of interest in their own right. All of the algorithms are inspired by information theoretic ideas. The algorithms are experimentally supported throughout the thesis by applications to speech recognition, text-to-speech, and synthetic problems.