nips nips2007 nips2007-27 nips2007-27-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Saher Esmeir, Shaul Markovitch
Abstract: Machine learning techniques are increasingly being used to produce a wide-range of classifiers for complex real-world applications that involve nonuniform testing costs and misclassification costs. As the complexity of these applications grows, the management of resources during the learning and classification processes becomes a challenging task. In this work we introduce ACT (Anytime Cost-sensitive Trees), a novel framework for operating in such environments. ACT is an anytime algorithm that allows trading computation time for lower classification costs. It builds a tree top-down and exploits additional time resources to obtain better estimations for the utility of the different candidate splits. Using sampling techniques ACT approximates for each candidate split the cost of the subtree under it and favors the one with a minimal cost. Due to its stochastic nature ACT is expected to be able to escape local minima, into which greedy methods may be trapped. Experiments with a variety of datasets were conducted to compare the performance of ACT to that of the state of the art cost-sensitive tree learners. The results show that for most domains ACT produces trees of significantly lower costs. ACT is also shown to exhibit good anytime behavior with diminishing returns.
[1] N. Abe, B. Zadrozny, and J. Langford. An iterative method for multi-class cost-sensitive learning. In KDD, 2004.
[2] V. Bayer-Zubek and Dietterich. Integrating learning from examples into the search for diagnostic policies. Artificial Intelligence, 24:263–303, 2005.
[3] C. L. Blake and C. J. Merz. UCI repository of machine learning databases, 1998.
[4] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Occam’s Razor. Information Processing Letters, 24(6):377–380, 1987.
[5] M. Boddy and T. L. Dean. Deliberation scheduling for problem solving in time constrained environments. Artificial Intelligence, 67(2):245–285, 1994.
[6] J. Bradford, C. Kunz, R. Kohavi, C. Brunk, and C. Brodley. Pruning decision trees with misclassification costs. In ECML, 1998.
[7] L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth and Brooks, Monterey, CA, 1984.
[8] J. Demsar. Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research, 7:1–30, 2006.
[9] P. Domingos. Metacost: A general method for making classifiers cost-sensitive. In KDD, 1999.
[10] C. Elkan. The foundations of cost-sensitive learning. In IJCAI, 2001.
[11] S. Esmeir and S. Markovitch. Anytime learning of decision trees. Journal of Machine Learning Research, 8, 2007.
[12] R. Greiner, A. J. Grove, and D. Roth. Learning cost-sensitive active classifiers. Artificial Intelligence, 139(2):137–174, 2002.
[13] T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. New York: Springer-Verlag, 2001.
[14] D. Margineantu. Active cost-sensitive learning. In IJCAI, 2005.
[15] P. Melville, M. Saar-Tsechansky, F. Provost, and R. J. Mooney. Active feature acquisition for classifier induction. In ICDM, 2004.
[16] S. W. Norton. Generating better decision trees. In IJCAI, 1989.
[17] M. Nunez. The use of background knowledge in decision tree induction. Machine Learning, 6:231–250, 1991.
[18] F. Provost and B. Buchanan. Inductive policy: The pragmatics of bias selection. Machine Learning, 20(1-2):35–61, 1995.
[19] Z. Qin, S. Zhang, and C. Zhang. Cost-sensitive decision trees with multiple cost scales. Lecture Notes in Computer Science, AI, Volume 3339/2004:380–390, 2004.
[20] J. R. Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, 1993.
[21] S. Sheng, C. X. Ling, A. Ni, and S. Zhang. Cost-sensitive test strategies. In AAAI, 2006.
[22] M. Tan and J. C. Schlimmer. Cost-sensitive concept learning of sensor use in approach and recognition. In Proceedings of the 6th international workshop on Machine Learning, 1989.
[23] P. Turney. Types of cost in inductive concept learning. In Workshop on Cost-Sensitive Learning at ICML, 2000.
[24] P. D. Turney. Cost-sensitive classification: Empirical evaluation of a hybrid genetic decision tree induction algorithm. Journal of Artificial Intelligence Research, 2:369–409, 1995. 8