Cogprints
Login | Create Account

Low Size-Complexity Inductive Logic Programming: The East-West Challenge Considered as a Problem in Cost-Sensitive Classification

Turney, Peter (1995) Low Size-Complexity Inductive Logic Programming: The East-West Challenge Considered as a Problem in Cost-Sensitive Classification. [Conference Paper]

Full text available as:

[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
84Kb

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.

Item Type:Conference Paper
Subjects:Computer Science > Machine Learning
Computer Science > Artificial Intelligence
ID Code:2890
Deposited By:Turney, Peter
Deposited On:16 Apr 2003
Last Modified:12 Sep 2007 17:47

References in Article

Select the SEEK icon to attempt to find the referenced article. If it does not appear to be in cogprints you will be forwarded to the paracite service. Poorly formated references will probably not work.

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.

Metadata

Repository Staff Only: item control page

Cogprints is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.