2003 FeatExtrLangForPropositionalizedRelLearning

• (Cumby & Roth, 2003a) ⇒ Chad Cumby, and Dan Roth. (2003). “Feature Extraction Languages for Propositionalized Relational Learning.” In: IJCAI Workshop on Learning Statistical Models from Relational Data.

Subject Headings: Kernel Function, Relational Learning Task.

Quotes

Abstract

Kernel methods have gained a great deal of popularity in the machine learning community as a method to learn indirectly in high dimensional feature spaces. Those interested in relational learning have recently begun to cast learning from structured and relational data in terms of kernel operations.

We describe a general family of kernel functions built up from a description language of limited expressivity and use it to study the benefits and drawbacks of kernel learning in relational domains. Learning with kernels in this family directly models learning over an expanded feature space constructed using the same description language. This allows us to examine issues of time complexity in terms of learning with these and other relational kernels, and how these relate to generalization ability. The tradeoffs between using kernels in a very high dimensional implicit space versus a restricted feature space, is highlighted through two experiments, in bioinformatics and in natural language processing.

References

• [Borgida and Patel-Schneider, 1994] A. Borgida and P. F. Patel-Schneider. A semantics and complete algorithm for subsumption in the classic description logic. JAIR, 1:277–308, 1994.
• [Cohen, 1995a] W. Cohen. PAC-learning recursive logic programs: Efficient algorithms. JAIR, 2:501–539, 1995.
• [Cohen, 1995b] W. Cohen. PAC-learning recursive logic programs: Negative result. JAIR, 2:541–573, 1995.
• [Cook and Holder, 1994] D.J. Cook and L.B. Holder. Substructure discovery using minimum description length and background knowledge. JAIR, 1:231–255, 1994.
• [Cumby and Roth, 2000] C. Cumby and Dan Roth. Relational representations that facilitate learning. In: Proceedings of KR’2000, 2000.
• [Cumby and Roth, 2002] C. Cumby and Dan Roth. Learning with feature description logics. In: Proceedings of ILP’02, 2002.
• [Cumby and Roth, 2003a] C. Cumby and Dan Roth. Feature extraction languages for propositionalized relational learning. Technical Report UIUCDCS-R-2003-2346, UIUC Computer Science Department, May 2003.
• [Cumby and Roth, 2003b] C. Cumby and Dan Roth. On kernel methods for relational learning. In Submission, 2003.
• [Dzeroski et al., 1992] S. Dzeroski, S. Muggleton, and S. Russell. PAC-learnability of determinate logic programs. In: Proceedings of COLT, pages 128–135, 1992.
• [Friedman et al., 1999] Nir Friedman, Lise Getoor, Daphne Koller, and A. Pfeffer. Learning probabilistic relational models. In IJCAI’99, pages 1300–1309, 1999.
• [Geibel and Wysotzki, 1996] P. Geibel and F. Wysotzki. Relational learning with decision trees. In ECAI’96, pages 428–432, 1996.
• [Golding and Roth, 1999] A. R. Golding and Dan Roth. A Winnow based approach to context-sensitive spelling correction. Machine Learning, 34(1-3):107–130, 1999.
• [Gonzalez et al., 2002] J. Gonzalez, L.B. Holder, and D.J. Cook. Graph-based relational concept learning. In ICML’02, 2002.
• [Kersting and Raedt, 2000] K. Kersting and L. De Raedt. Bayesian logic programs. In: Proceedings of the ILP’2000 Work-in-Progress Track, pages 138–155, 2000.
• [Khardon et al., 1999] R. Khardon, Dan Roth, and L. G. Valiant. Relational learning for NLP using linear threshold elements. In: Proceedings of IJCAI, 1999.
• [Koller et al., 1997] Daphne Koller, A. Levy, and A. Pfeffer. P-classic: A tractable probabilistic description logic. In: Proceedings of NCAI’97, pages 360–397, 1997.
• [Kramer and Frank, 2000] S. Kramer and E. Frank. Bottom-up propositionalization. In: Proceedings of the ILP-2000 Work-In-Progress Track, 2000.
• [Kramer and Raedt, 2001] S. Kramer and L. De Raedt. Feature construction with version spaces for biochemical applications. In: Proceedings of ICML’01, 2001.
• [Kramer et al., 2001] S. Kramer, N. Lavrac, and P. Flach. Propositionalization approaches to relational data mining. In Relational Data Mining. Springer Verlag, 2001.
• [Lavrac et al., 1991] N. Lavrac, S. Dzeroski, and Marko Grobelnik. Learning nonrecursive definitions of relations with LINUS. In: Proceedings of the 5th European Working Session on Learning, pages 265–281, 1991.
• [Levesque and Brachman, 1985] Hector Levesque and Ronald J. Brachman. A fundamental tradeoff in knowledge representation and reasoning. In Ronald J. Brachman and Hector Levesque, editors, Readings in Knowledge Representation. Morgan Kaufman, 1985.
• [Littlestone, 1988] N. Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2:285–318, 1988.
• [Lloyd, 1987] J. W. Lloyd. Foundations of Logic Programming. Springer-verlag, 1987.
• [Muggleton and De Raedt, 1994] S. Muggleton and L. De Raedt. Inductive Logic Programming: Theory and methods. Journal of Logic Programming, 20:629–679, 1994.
• [Punyakanok and Roth, 2001] V. Punyakanok and Dan Roth. The use of classifiers in sequential inference. In NIPS’2000, pages 995–1001, 2001.
• [Roth and Yih, 2001] Dan Roth and W. Yih. Relational learning via propositional algorithms: An information extraction case study. In: Proceedings of IJCAI, pages 1257–1263, 2001.
• [Selman, 1990] B. Selman. Tractable Default Reasoning. PhD thesis, Dept. of Computer Science, Univ. of Toronto, 1990.
• [Valiant, 1999] L. G. Valiant. Robust logic. In: Proceedings,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2003 FeatExtrLangForPropositionalizedRelLearning	Chad Cumby			Feature Extraction Languages for Propositionalized Relational Learning			http://l2r.cs.uiuc.edu/~danr/Papers/CumbyRo03a.pdf