creators_name: Turney, Peter creators_id: 2175 type: confpaper datestamp: 2003-04-16 lastmod: 2011-03-11 08:55:15 metadata_visibility: show title: Low Size-Complexity Inductive Logic Programming: The East-West Challenge Considered as a Problem in Cost-Sensitive Classification ispublished: pub subjects: comp-sci-mach-learn subjects: comp-sci-art-intel full_text_status: public abstract: The Inductive Logic Programming community has considered proof-complexity and model-complexity, but, until recently, size-complexity has received little attention. Recently a challenge was issued "to the international computing community" to discover low size-complexity Prolog programs for classifying trains. The challenge was based on a problem first proposed by Ryszard Michalski, 20 years ago. We interpreted the challenge as a problem in cost-sensitive classification and we applied a recently developed cost-sensitive classifier to the competition. Our algorithm was relatively successful (we won a prize). This paper presents our algorithm and analyzes the results of the competition. date: 1995 date_type: published pagerange: 247-263 refereed: TRUE referencetext: Cestnik, B., Kononenko, I., & Bratko, I. (1987). ASSISTANT 86: A knowledge elicitation tool for sophisticated users. In I. Bratko and N. Lavrac, editors, Progress in Machine Learning, pp. 31-45. Wilmslow, UK: Sigma Press. Clark, P., & Boswell, R. (1991). Rule induction with CN2: Some recent improvements. In Proceedings of the Fifth European Working Session on Learning, EWSL-91, pp. 151-163. Berlin: Springer Verlag. Conklin, D., & Witten, I.H. (1994). Complexity-based induction. Machine Learning, 16, 203-225. Grefenstette, J.J. (1986). Optimization of control parameters for genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics, 16, 122-128. Lavrac, N., & Dzeroski, S. (1994). Inductive Logic Programming: Techniques and Applications. New York: Ellis Horwood. Michalski, R.S., & Larson, J.B. (1977). Inductive inference of VL decision rules. Paper presented at Workshop in Pattern-Directed Inference Systems, Hawaii, 1977. SIGART Newsletter, ACM, 63, 38-44. Michie, D., Muggleton, S., Page, D., & Srinivasan, A. (1994). To the international computing community: A new East-West challenge. Oxford University Computing Laboratory, Oxford, UK. Mozetic, I. (1985). NEWGEM: Program for learning from examples, technical documentation and user’s guide. Reports of Intelligent Systems Group, UIUCDCS-F- 85-949, Department of Computer Science, University of Illinois, Urbana Champaign, Illinois. Muggleton, S., & Buntine, W. (1988). Machine invention of first-order predicates by inverting resolution. Proceedings of the Fifth International Conference on Machine Learning, ML-88, pp. 339-352. California: Morgan Kaufmann. Muggleton, S., & Feng, C. (1990). Efficient induction of logic programs. Proceedings of the First Conference on Algorithmic Learning Theory, pp. 368-381. Ohmsha, Tokyo. Muggleton, S., Srinivasan, A., & Bain, M. (1992). Compression, significance and accuracy. In D. Sleeman and P. Edwards, editors, Machine Learning: Proceedings of the Ninth International Conference (ML92), pp. 338-347. California: Morgan Kaufmann. Norton, S.W. (1989). Generating better decision trees. Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, IJCAI-89, pp. 800-805. Detroit, Michigan. Núñez, M. (1988). Economic induction: A case study. Proceedings of the Third European Working Session on Learning, EWSL-88, pp. 139-145. California: Morgan Kaufmann. Núñez, M. (1991). The use of background knowledge in decision tree induction. Machine Learning, 6, 231-250. Quinlan, J.R. (1990). Learning logical definitions from relations. Machine Learning, 5, 239-266. Quinlan, J.R. (1991). Determinate literals in inductive logic programming. Proceedings of the Eighth International Workshop on Machine Learning, ML-91, pp. 442-446. California: Morgan Kaufmann. Quinlan, J.R. (1993). C4.5: Programs for machine learning. California: Morgan Kaufmann. Shapiro, E. (1983). Algorithmic Program Debugging. Massachusetts: MIT Press. Tan, M., & Schlimmer, J. (1989). Cost-sensitive concept learning of sensor use in approach and recognition. Proceedings of the Sixth International Workshop on Machine Learning, ML-89, pp. 392-395. Ithaca, New York. Tan, M., & Schlimmer, J. (1990). CSL: A cost-sensitive learning system for sensing and grasping objects. IEEE International Conference on Robotics and Automation. Cincinnati, Ohio. Tan, M. (1993). Cost-sensitive learning of classification knowledge and its applications in robotics. Machine Learning, 13, 7-33. Turney, P. (1995). Cost-sensitive classification: Empirical evaluation of a hybrid genetic decision tree induction algorithm. Journal of Artificial Intelligence Research, 2, 369-409. [Available on the Internet at URL http://www.cs.washington.edu/ research/jair/home.html.] Wong, M.L., & Leung, K.S. (1994). Inductive logic programming using genetic algorithms. Advances in Artificial Intelligence -- Theory and Application II, Volume II of the Proceedings of the 7th International Conference on Systems Research, Informatics and Cybernetics, Baden-Baden, Germany, pp. 119-124. citation: Turney, Peter (1995) Low Size-Complexity Inductive Logic Programming: The East-West Challenge Considered as a Problem in Cost-Sensitive Classification. [Conference Paper] document_url: http://cogprints.org/2890/1/NRC-39164.pdf