jmlr jmlr2007 jmlr2007-47 jmlr2007-47-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Marta Arias, Roni Khardon, Jérôme Maloberti
Abstract: The paper introduces L OG A N -H —a system for learning first-order function-free Horn expressions from interpretations. The system is based on an algorithm that learns by asking questions and that was proved correct in previous work. The current paper shows how the algorithm can be implemented in a practical system, and introduces a new algorithm based on it that avoids interaction and learns from examples only. The L OG A N -H system implements these algorithms and adds several facilities and optimizations that allow efficient applications in a wide range of problems. As one of the important ingredients, the system includes several fast procedures for solving the subsumption problem, an NP-complete problem that needs to be solved many times during the learning process. We describe qualitative and quantitative experiments in several domains. The experiments demonstrate that the system can deal with varied problems, large amounts of data, and that it achieves good classification accuracy. Keywords: inductive logic programming, subsumption, bottom-up learning, learning with queries
D. Angluin. Queries and concept learning. Machine Learning, 2(4):319–342, 1988. D. Angluin, M. Frazier, and L. Pitt. Learning conjunctions of Horn clauses. Machine Learning, 9: 147–164, 1992. M. Arias and R. Khardon. Bottom-up ILP using large refinement steps. In Proceeding of the International conference on Inductive Logic Programming, pages 26–43. Springer, 2004. LNAI 3194. M. Arias and R. Khardon. Learning closed Horn expressions. Information and Computation, 178: 214–240, 2002. H. Arimura. Learning acyclic first-order Horn sentences from entailment. In Proceedings of the International Conference on Algorithmic Learning Theory, pages 432–445. Springer, 1997. LNAI 1316. Jacques Al` s Bianchetti, C´ line Rouveirol, and Mich` le Sebag. Constraint-based learning of long e e e relational concepts. In Proceedings of the International Conference on Machine Learning, pages 35–42. Morgan Kaufmann, 2002. 584 L EARNING H ORN E XPRESSIONS WITH L OG A N -H H. Blockeel and L. De Raedt. Lookahead and discretization in ILP. In Proceedings of the 7th International Workshop on Inductive Logic Programming, pages 77–84. Springer, 1997. LNAI 1297. H. Blockeel and L. De Raedt. Top down induction of first order logical decision trees. Artificial Intelligence, 101:285–297, 1998. H Blockeel, L. De Raedt, N. Jacobs, and B. Demoen. Scaling up inductive logic programming by learning from interpretations. Data Mining and Knowledge Discovery, 3(1):59–93, 1999. H. Blockeel, L. Dehaspe, B. Demoen, G. Janssens, J. Ramon, and H. Vandecasteele. Executing query packs in ILP. In Proc. Tenth International Conference on Inductive Logic Programming, LNAI 1866, pages 60–77. Springer-Verlag, Berlin, 2000. H. Blockeel, L. Dehaspe, B. Demoen, G. Janssens, J. Ramon, and H. Vandecasteele. Improving the efficiency of inductive logic programming through the use of query packs. Journal of Artificial Intelligence Research, 16:135–166, 2002. A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Occam’s razor. Information Processing Letters, 24:377–380, April 1987. I. Bratko. Refining complete hypotheses in ILP. In International Workshop on Inductive Logic Programming, pages 44–55. Springer, 1999. LNAI 1634. I. Bratko and S. Muggleton. Applications of inductive logic programming. Communications of the ACM, 38(11):65–70, November 1995. C. Chang and J. Keisler. Model Theory. Elsevier, Amsterdam, Holland, 1990. X. Chen. A Theoretical Comparison of Selected CSP Solving and Modeling Techniques. PhD thesis, University of Alberta, Canada, 2000. L. De Raedt. Logical settings for concept learning. Artificial Intelligence, 95(1):187–201, 1997. See also relevant Errata (forthcoming). L. De Raedt and S. Dzeroski. First order jk-clausal theories are PAC-learnable. Artificial Intelligence, 70:375–392, 1994. L. De Raedt and W. Van Laer. Inductive constraint logic. In Proceedings of the 6th Conference on Algorithmic Learning Theory. Springer, 1995. LNAI 997. R. Dechter and J. Pearl. Structure identification in relational data. Artificial Intelligence, 58:237– 270, 1992. N. Di Mauro, T.M.A. Basile, S. Ferilli, F. Esposito, and N. Fanizzi. An exhaustive matching procedure for the improvement of learning efficiency. In Proceedings of the 13th International Conference on Inductive Logic Programming, pages 112–129. Springer, 2003. LNAI 2835. J. Dougherty, R. Kohavi, and M. Sahami. Supervised and unsupervised discretization of continuous features. In Proceedings of the International Conference on Machine Learning, pages 194–202, 1995. 585 A RIAS , K HARDON AND M ALOBERTI U.M. Fayyad and K. B. Irani. Multi-interval discretization of continuous-valued attributes for classification learning. In Proceedings of the International Conference on Machine Learning, pages 1022–1027, 1993. I.P. Gent, E. MacIntyre, P. Prosser, and T. Walsh. The constrainedness of search. In Proceedings of the National Conference on Artificial Intelligence, pages 246–252, 1996. A. Giordana and L. Saitta. Phase transitions in relational learning. Machine Learning, 2:217–251, 2000. A. Giordana, L. Saitta, M. Sebag, and M. Botta. Relational learning as search in a critical region. Journal of Machine Learning Research, 4:431–463, 2003. H. Kautz, M. Kearns, and B. Selman. Horn approximations of empirical data. Artificial Intelligence, 74:129–145, 1995. R. Khardon. Learning horn expressions with LogAn-H. In Proceedings of the International Conference on Machine Learning, pages 471–478. Morgan Kaufmann, 2000. R. Khardon. Learning range-restricted Horn expressions. In Proceedings of the Fourth European Conference on Computational Learning Theory, pages 111–125. Springer, 1999a. LNAI 1572. R. Khardon. Learning function free Horn expressions. Machine Learning, 37(3):249–275, 1999b. R. D. King, K. Whelam, F. Jones, P. Reiser, C. Bryant, S. Muggleton, D. Kell, and S. Oliver. Functional genomic hypothesis generation and experimentation by a robot scientist. Nature, 427: 247–252, 2004. M. Krishna Rao and A. Sattar. Learning from entailment of logic programs with local variables. In Proceedings of the International Conference on Algorithmic Learning Theory. Springer, 1998. LNAI 1501. W. Van Laer, H. Blockeel, and L. De Raedt. Inductive constraint logic and the mutagenesis problem. In Proceedings of the Eighth Dutch Conference on Artificial Intelligence, pages 265–276, November 1996. J.W. Lloyd. Foundations of Logic Programming. Springer Verlag, 1987. Second Edition. A.K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8(1):99–118, 1977. J. Maloberti and M. Sebag. Fast theta-subsumption with constraint satisfaction algorithms. Machine Learning, 55(2):137–174, 2004. J. Maloberti and E. Suzuki. An efficient algorithm for reducing clauses based on constraint satisfaction techniques. In Proceedings of the 14th International Conference on Inductive Logic Programming, pages 234–251. Springer Verlag LNAI 3194, 2004. T. Mitchell. Machine Learning. McGraw-Hill, 1997. S. Muggleton. Inverse entailment and Progol. New Generation Computing, Special issue on Inductive Logic Programming, 13(3-4):245–286, 1995. 586 L EARNING H ORN E XPRESSIONS WITH L OG A N -H S. Muggleton and W. Buntine. Machine invention of first order predicates by inverting resolution. In S. Muggleton, editor, Inductive Logic Programming. Academic Press, 1992. S. Muggleton and L. DeRaedt. Inductive logic programming: Theory and methods. The Journal of Logic Programming, 19 & 20:629–680, May 1994. S. Muggleton and C. Feng. Efficient induction of logic programs. In S. Muggleton, editor, Inductive Logic Programming, pages 281–298. Academic Press, 1992. S. H. Muggleton, M. Bain, J. Hayes-Michie, and D. Michie. An experimental comparison of human and machine learning formalisms. In Proc. Sixth International Workshop on Machine Learning, pages 113–118. Morgan Kaufmann, 1989. F. Pereira and S. Shieber. Prolog and natural-language analysis. Stanford : Center for the Study of Language and Information, 1987. G. D. Plotkin. A note on inductive generalization. Machine Intelligence, 5:153–163, 1970. G. D. Plotkin. A further note on inductive generalization. Machine Intelligence, 6:101–124, 1971. J. R. Quinlan. Learning logical definitions from relations. Machine Learning, 5:239–266, 1990. J. R. Quinlan. C4.5: Programs for machine learning. Morgan Kaufmann, 1993. C. Reddy and P. Tadepalli. Learning first order acyclic Horn programs from entailment. In International Conference on Inductive Logic Programming, pages 23–37. Springer, 1998. LNAI 1446. V. Santos Costa, A. Srinivasan, R. Camacho, H. Blockeel, B. Demoen, G. Janssens, J. Struyf, H. Vandecasteele, and W. Van Laer. Query transformations for improving the efficiency of ILP systems. Journal of Machine Learning Research, 4:465–491, 2003. M. Sebag and C. Rouveirol. Resource-bounded relational reasoning: Induction and deduction through stochastic matching. Machine Learning, 38:41–62, 2000. A. Srinivasan, S. H. Muggleton, R. D. King, and M. J. E. Sternberg. Mutagenesis: ILP experiments in a non-determinate biological domain. In S. Wrobel, editor, Proc. 4th Int. Workshop on Inductive Logic Programming, pages 217–232, September 1994. A. Srinivasan, S. Muggleton, and R.D. King. Comparing the use of background knowledge by inductive logic programming systems. In Proceedings of the 5th International Workshop on Inductive Logic Programming, pages 199–230, 1995. C. Stolle, A. Karwath, and L. De Raedt. CLASSIC’CL: An integrated ILP system. In Discovery Science, pages 354–362, 2005. E. Tsang. Foundations of Constraint Satisfaction. Academic Press, London, 1993. 587