This site has been permanently archived. This is a static copy provided by the University of Southampton.
--- 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. altloc: [] chapter: ~ commentary: ~ commref: ~ confdates: ~ conference: Fifth International Inductive Logic Programming Workshop confloc: 'Leuven, Belgium' contact_email: ~ creators_id: - 2175 creators_name: - family: Turney given: Peter honourific: '' lineage: '' date: 1995 date_type: published datestamp: 2003-04-16 department: ~ dir: disk0/00/00/28/90 edit_lock_since: ~ edit_lock_until: ~ edit_lock_user: ~ editors_id: [] editors_name: [] eprint_status: archive eprintid: 2890 fileinfo: /style/images/fileicons/application_pdf.png;/2890/1/NRC%2D39164.pdf full_text_status: public importid: ~ institution: ~ isbn: ~ ispublished: pub issn: ~ item_issues_comment: [] item_issues_count: 0 item_issues_description: [] item_issues_id: [] item_issues_reported_by: [] item_issues_resolved_by: [] item_issues_status: [] item_issues_timestamp: [] item_issues_type: [] keywords: ~ lastmod: 2011-03-11 08:55:15 latitude: ~ longitude: ~ metadata_visibility: show note: ~ number: ~ pagerange: 247-263 pubdom: FALSE publication: ~ publisher: ~ 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. relation_type: [] relation_uri: [] reportno: ~ rev_number: 12 series: ~ source: ~ status_changed: 2007-09-12 16:47:21 subjects: - comp-sci-mach-learn - comp-sci-art-intel succeeds: ~ suggestions: ~ sword_depositor: ~ sword_slug: ~ thesistype: ~ title: | Low Size-Complexity Inductive Logic Programming: The East-West Challenge Considered as a Problem in Cost-Sensitive Classification type: confpaper userid: 2175 volume: ~