Supervised Learning and Data Mining

Supervised learning from examples involves learning a function y = f(x) from training examples of the form (x, f(x)). A wide range of algorithms have been developed for this task including decision trees, neural networks, association rules, belief networks, and the nearest neighbor rule. Despite the mature state of this field, there are many important open problems. Many of these result from the recent interest in applying machine learning algorithms to analyze large amounts of corporate and scientific data--"data mining".

Divide-and-Conquer Problems. Many current and anticipated machine learning applications involve x and y values that are very complex. For example, each x might be an image, and each y might be a partition of that image into segments and an assignment of labels to each segment. Another common example is speech recognition, where each x is a lengthy speech signal and each y is a string of words. Such problems are typically solved by dividing the x into small pieces (possibly overlapping), applying a classifier to classify each piece, and then merging or combining those pieces to produce the y value.
However, with the exception of speech recognition systems, the methods that have been applied have generally been ad hoc. The learning algorithms used to train the "base classifier" (i.e., the classifier applied to the individual pieces) are not designed for the divide-and-conquer setting, and the "merge" methods are typically not trained at all.
A goal of our research is to develop learning algorithms for the "base classifier" and "merge" steps that can be applied to a wide variety of divide-and-conquer learning algorithms. We wish to develop a language for specifying divide-and-conquer problems and a toolbox for constructing divide-and-conquer solutions. Our analysis of this problem is described in Machine Learning for Sequential Data: A Review.
Cost-Sensitive Learning. Standard learning algorithms assume that all classification errors are equally serious. However, in many applications (including divide-and-conquer problems), some errors are more serious than others. Cost-sensitive learning methods are needed to address this problem. We are currently exploring several different approaches to constructing cost-sensitive algorithms. In addition, we have developed new statistical tests for evaluating the performance of cost-sensitive algorithms (Margineantu and Dietterich, 2000).
Algorithms for learning stochastic models. Stochastic models--expressed as belief networks--are a new and very promising way of expressing prior knowledge and incorporating it into the learning process. We recently developed an application to VLSI wafer testing in collaboration with Hewlett Packard Corporation (Fountain, Dietterich, and Sudyka, 2000).
Ensemble Methods. Our error-correcting output coding technique is one instance of a general class of learning algorithms in which several classifiers are constructed and then combined to make classification decisions. These methods are very effective, but debate continues concerning why. We are conducting experiments to understand why Adaboost tends to avoid overfitting, even when it is applied to very flexible classifiers such as decision trees and neural networks.
Learning with many classes. Our group originated the method of error-correcting output coding--which gives improved accuracy on learning problems involving multiple classes and which promises to scale well to problems with thousands of classes. A topic that we would like to explore is the combination of error-correcting codes with large-margin classifiers such as support-vector machines and boosted ensembles.

Publications

Dietterich, T. G. (2002). Machine Learning for Sequential Data: A Review. In T. Caelli (Ed.) Lecture Notes in Computer Science. Springer-Verlag. Postscript preprint. PDF preprint.
Dietterich, T. G. (to appear). Ensemble Learning. In The Handbook of Brain Theory and Neural Networks, Second edition, (M.A. Arbib, Ed.), Cambridge, MA: The MIT Press, 2002. Postscript Preprint.
Fountain, T., Dietterich, T., and Sudyka, B. (2002). Data mining for manufacturing control: An application in optimizing IC test. In B. Nebel and G. Lakemeyer (Eds.) Exploring Artificial Intelligence in the New Millenium. Morgan-Kaufmann. Postscript preprint.
Zubek, V. B., Dietterich, T. G. (2002). Pruning Improves Heuristic Search for Cost-Sensitive Learning. In Proceedings of the International Conference on Machine Learning. (pages 27-34) Postscript Preprint. PDF Preprint.
Margineantu, D., Dietterich, T. G. (2002). Improved Class Probability Estimates from Decision Tree Models. To appear in Lecture Notes in Statistics, © Springer-Verlag. Postscript Preprint. Postscript Preprint.
Margineantu, D. and Dietterich, T. G. (2001). Lazy Class Probability Estimators. In 33rd Symposium on the Interface of Computing Science and Statistics, Costa Mesa, California.
Dietterich, T. G. (2000). Ensemble Methods in Machine Learning. To appear in F. Roli (Ed.) First International Workshop on Multiple Classifier Systems, Lecture Notes in Computer Science, New York: Springer Verlag. Postscript preprint © Springer-Verlag.
Fountain, T., Dietterich, T. G., Sudyka, B. (2000). Mining IC Test Data to Optimize VLSI Testing. To appear in Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM Press. PDF preprint. Winner of Award for Best Application Paper. (Winner of Best Industrial Paper Award.)
Margineantu, D. D., Dietterich, T. G. (2000). Bootstrap Methods for the Cost-Sensitive Evaluation of Classifiers . In International Conference on Machine Learning, ICML-2000 (pp. 582-590). Postscript preprint
Dietterich, T. G., (2000). An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, boosting, and randomization. Machine Learning, 40 (2) 139-158. Postscript preprint.
Bakiri, G., Dietterich, T. G. (In press). Achieving high-accuracy text-to-speech with machine learning. To appear in B. Damper (Ed.) Data mining in speech synthesis. Chapman and Hall. Postscript preprint.
Margineantu, D., Dietterich, T. G. (1999). Learning Decision Trees for Loss Minimization in Multi-Class Problems. Technical report 99-30-03. Department of Computer Science, Oregon State University Postscript file.
Kong, E. G., and Dietterich, T. G. (1997). Probability estimation using error-correcting output coding. IASTED International Conference: Artificial Intelligence and Soft Computing, Banff, Canada. Postscript preprint.
Margineantu, D., Dietterich, T. G. (1997). Pruning Adaptive Boosting. Fourteenth International Conference on Machine Learning. Morgan Kaufmann, San Francisco. 211--218. Postscript preprint.
Dietterich, T. G., (1996). Editorial Machine Learning 24 (2), 1--3. Postscript preprint.
Dietterich, T. G., Kearns, M., Mansour, Y., (1996). Applying the weak learning framework to understand and improve C4.5. Proceedings of the Thirteenth International Conference on Machine Learning, 96-104. Postscript preprint.
Dietterich, T. G., Kong, E. B., (1995). Machine Learning Bias, Statistical Bias, and Statistical Variance of Decision Tree Algorithms. Poscript technical report.
Kong, E. B., Dietterich, T. G., (1995). Error-Correcting Output Coding Corrects Bias and Variance. In Proceedings of the 12th International Conference on Machine Learning (pp. 313-321). Tahoe City, CA. San Francisco: Morgan Kaufmann. Poscript preprint.
Dietterich, T. G., Bakiri, G. (1995) Solving Multiclass Learning Problems via Error-Correcting Output Codes. Journal of Artificial Intelligence Research 2: 263-286. Postscript file.
Almuallim, H., Dietterich, T. G. (1994) Learning boolean concepts in the presence of many irrelevant features. Artificial Intelligence, 69(1-2): 279-306. Postscript preprint.
Wettschereck, D., Dietterich, T. G. (1994). Locally adaptive nearest neighbor algorithms. Advances in Neural Information Processing Systems, 6. San Mateo, CA: Morgan Kaufmann. 184-191. Postscript preprint.
Bakiri, G., Dietterich, T. G. (1993). Performance comparison between human engineered and machine learned letter-to-sound rules for English: A machine learning success story. 18th International Conference on the Applications of Computers and Statistics to Science and Society. Cairo, Egypt. Postscript preprint.
Almuallim, H., Dietterich, T. G. (1992). Efficient algorithms for identifying relevant features. Proceedings of the Ninth Canadian Conference on Artificial Intelligence (pp. 38-45). Vancouver, BC: Morgan Kaufmann. May 11-15. Postscript preprint.
Almuallim, H., Dietterich, T. G. (1992). On learning more concepts. In Proceedings of the Ninth International Conference on Machine Learning, (pp. 11-19), Aberdeen, Scotland: Morgan-Kaufmann. Postscript preprint.
Wettschereck, D., Dietterich, T. G. (1992) Improving the performance of radial basis function networks by learning center locations. In Moody, J. E., Hanson, S. J., and Lippmann, R. P. (Eds.) Advances in Neural Information Processing Systems, 4. (pp. 1133-1140) San Mateo, CA: Morgan Kaufmann. Postscript preprint.
Almuallim, H., Dietterich, T. G. (1991) Learning with many irrelevant features. Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI-91) (pp. 547-552). Anaheim, CA: AAAI Press. Postscript preprint.
Dietterich, T. G. (1991). Do Hidden Units Implement Error-Correcting Codes? Technical Report. Postscript file
Dietterich, T. G., Bakiri, G. (1991) Error-correcting output codes: A general method for improving multiclass inductive learning programs. Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI-91) (pp. 572-577). Anaheim, CA: AAAI Press. Postscript preprint.
Dietterich, T. G., Hild, H., Bakiri, G. (1990) A comparative study of ID3 and backpropagation for English text-to-speech mapping. Proceedings of the 1990 Machine Learning Conference, Austin, TX. 24-31. Postscript preprint.