Compile the Hypothesis Space: Do it Once, Use it Often

• Autorzy: Fonseca N.A. , Camacho R. , Rocha R. , Costa V.S.
• Języki publikacji: EN

Abstrakty

EN

Inductive Logic Programming (ILP) is a powerful and well-developed abstraction for multi-relational data mining techniques. Despite the considerable success of ILP, deployed ILP systems still have efficiency problems when applied to complex problems. In this paper we propose a novel technique that avoids the procedure of deducing each example to evaluate each constructed clause. The technique is based on the Mode Directed Inverse Entailment approach to ILP, where a bottom clause is generated for each example and the generated clauses are subsets of the literals of such bottom clause. We propose to store in a prefix-tree all clauses that can be generated from all bottom clauses together with some extra information. We show that this information is sufficient to estimate the number of examples that can be deduced froma clause and present an ILP algorithmthat exploits this representation. We also present an extension of the algorithm where each prefix-tree is computed only once (compiled) per example. The evaluation of hypotheses requires only basic and efficient operations on trees. This proposal avoids re-computation of hypothesis’ value in theorylevel search, in cross-validation evaluation procedures and in parameter tuning. Both proposals are empirically evaluated on real applications and considerable speedups were observed.

Słowa kluczowe

EN

Mode Directed Inverse Entailment; efficiency; data structures; compilation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 89, nr 1
• Strony: 45--67
• Opis fizyczny: bibliogr. 48 poz., wykr.

Twórcy

autor

Fonseca N.A.

autor

Camacho R.

autor

Rocha R.

autor

Costa V.S.

• IBMC, AC Nuno Fonseca, Rua do Campo Alegre 823, 4150-180 Porto, Portugal,

Bibliografia

• [1] Anthony, S., Frisch, A. M.: Cautious Induction: An Alternative to Clause-at-a-time Induction in Inductive Logic Programming, New Generation Computing, 17(1), January 1999, 25-52.
• [2] Bachmair, L., Chen, T., Ramakrishnan, I. V.: Associative-Commutative Discrimination Nets, Proceedings of the 4th International Joint Conference on Theory and Practice of Software Development, number 668 in Lecture Notes in Computer Science, Springer-Verlag, Orsay, France, 1993.
• [3] Badea, L., Stanciu, M.: Refinement Operators Can Be (Weakly) Perfect, Inductive Logic Programming, 9th International Workshop, ILP-99, Bled, Slovenia, June 24-27, 1999, Proceedings (S. Dzeroski, P. A. Flach, Eds.), 1634, Springer, 1999, ISBN 3-540-66109-3.
• [4] Blockeel, H., Dehaspe, L., Demoen, B., Janssens, G., Ramon, J., Vandecasteele, H.: Improving the Efficiency of Inductive Logic Programming through the Use of Query Packs, Journal of Machine Learning Research, 16, 2002, 135-166.
• [5] Blockeel, H., Raedt, L. D., Jacobs, N., Demoen, B.: Scaling Up Inductive Logic Programming by Learning from Interpretations, Data Mining and Knowledge Discovery, 3(1), 1999, 59-93.
• [6] Camacho, R.: Inducing Models of Human Control Skills using Machine Learning Algorithms, Ph.D. Thesis, Department of Electrical Engineering and Computation, Universidade do Porto, 2000.
• [7] Camacho, R.: Improving the efficiency of ILP systems using an Incremental Language Level Search, Annual Machine Learning Conference of Belgium and the Netherlands, 2002.
• 8] Camacho, R., Fonseca, N. A., Rocha, R., Costa, V. S.: ILP :- Just Trie It. Proceedings of the 17th International Conference on Inductive Logic Programming (ILP 2007) (H. Blockeel et al., Eds.), 4894, Springer-Verlag, 2008.
• [9] Cussens, J.: Part-of-SpeechDisambiguationUsing ILP, Technical Report PRG-TR-25-96, Oxford University Computing Laboratory, 1996.
• [10] Dehaspe, L., Toironen, H.: Relational Data Mining, chapter Discovery of relational association rules, Springer-Verlag, Berlin, 2000, 189-208.
• [11] Deransart, P., Ed-Dbali, A., Cervoni, L., Ed-Ball, A. A.: Prolog, The Standard : Reference Manual, Springer Verlag, 1996.
• [12] Di Mauro, N., Basile, T., Ferilli, S., Esposito, F., Fanizzi, N.: An Exhaustive Matching Procedure for the Improvement of Learning Efficiency, Inductive Logic Programming: 13th International Conference (ILP03) (T. Horváth, A. Yamamoto, Eds.), 2835, Springer-Verlag, 2003.
• [13] Džeroski, S., Lavrač, N.: Inductive Logic Programming: Techniques and Applications, Ellis Horwood, 1994.
• [14] Džeroski, S., Lavrač, N., Eds.: Relational Data Mining, Springer-Verlag New York, Inc., 2000.
• [15] Fisher, B., Cussens, J.: Inductive Mercury Programming, Inductive Logic Programming, 16th International, Conference, ILP 2006 (S.Muggleton, R. P. Otero, A. Tamaddoni-Nezhad, Eds.), 4455, Springer, 2007, ISBN 978-3-540-73846-6.
• [16] Fonseca, N. A., Camacho, R., Costa, V. S., Rocha, R.: k-RNN: k-Relational Nearest Neighbour Algorithm, Proceedings of 2008 ACM Symposium on Applied Computing (SAC 2008), ACM, March 2008.
• [17] Fonseca, N. A., Rocha, R., Camacho, R., Silva, F.: Efficient Data Structures for Inductive Logic Programming, Proceedings of the 13th International Conference on Inductive Logic Programming (T. Horváth, A. Yamamoto, Eds.), 2835, Springer-Verlag, Szeged, Hungary, 2003.
• [18] Fonseca, N. A., Silva, F., Camacho, R.: Strategies to Parallelize ILP Systems, Proceedings of the 15th International Conference on Inductive Logic Programming (ILP 2005) (S. Kramer, B. Pfahringer, Eds.), 3625, Springer-Verlag, Bonn, Germany, August 2005.
• [19] Fonseca, N. A., Silva, F., Camacho, R.: April - An Inductive Logic Programming System, Proceedings of the 10th European Conference on Logics in Artificial Intelligence (JELIA06), 4160, Springer-Verlag, Liverpool, September 2006.
• [20] Fredkin, E.: Trie Memory, Communications of the ACM, 3, 1962, 490-499.
• [21] Graf, P.: Term Indexing, Number 1053 in Lecture Notes in Artificial Intelligence, Springer-Verlag, 1996.
• [22] Han, J., Kimber, M.: Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2007.
• [23] Idestam-Almquist, P.: Generalization of Clauses under Implication, Journal of Artificial Intelligence Research, 3, 1995, 467-489.
• [24] ILP Applications, http://www-ai.ijs.si/ ilpnet2/apps/index.html, 2002.
• [25] Van der Laag, P.: An analysis of refinement operators in inductive logic programming, Ph.D. Thesis, Erasmus Universiteit, Rotterdam, the Netherlands, 1995.
• [26] Landwehr, N., Passerini, A., Raedt, L. D., Frasconi, P.: kFOIL: Learning Simple Relational Kernels., Proceedings of the National Conference on Artificial Intelligence, 2006.
• [27] Lavrač, N., Flach, P., Zupan, B.: Rule Evaluation Measures: A Unifying View, Proceedings of the 9th International Workshop on Inductive Logic Programming (S. Džeroski, P. Flach, Eds.), 1634, Springer-Verlag, Berlin, June 1999.
• [28] Lloyd, J. W.: Foundations of Logic Programming, 2nd edition, Springer-Verlag, Berlin, 1997.
• [29] Maloberti, J., Sebag, M.: Fast Theta-Subsumption with Constraint Satisfaction Algorithms, Machine Learning, 55(2), 2004, 137-174, ISSN 0885-6125.
• [30] Michalski, R. S., Larson, J. B.: Selection of Most Representative Training Examples and Incremental Generation of VL918 Hypotheses: The UnderlyingMehtodology and the Description of Programs ESEL and AQ11, Technical Report 867, Department of Computer Science, University of Illinois at Urbana-Champaign, 1978.
• [31] Muggleton, S.: Inductive logic programming, Proceedings of the 1st Conference on Algorithmic Learning Theory, Ohmsma, Tokyo, Japan, 1990.
• [32] Muggleton, S.: Inverse Entailment and Progol, New Generation Computing, Special issue on Inductive Logic Programming, 13(3-4), 1995, 245-286.
• [33] Muggleton, S., Feng, C.: Efficient induction of logic programs, Proceedings of the First Conference on Algorithmic Learning Theory, Ohmsha, Tokyo, 1990.
• [34] Muggleton, S., Raedt, L. D.: Inductive Logic Programming: Theory and Methods, Journal of Logic Programming, 19,20, 1994, 629-679.
• [35] Muggleton, S. H.: Inductive Logic Programming, New Generation Computing, 8(4), 1991, 295-317.
• [36] N´edellec, C., Rouveirol, C., Ad´e, H., Bergadano, F., Tausend, B.: Declarative Bias in ILP, in: Advances in Inductive Logic Programming (L. De Raedt, Ed.), IOS Press, 1996, 82-103.
• [37] Nienhuys-Cheng, S.-H., de Wolf, R.: Foundations of Inductive Logic Programming, vol. 1228 of Lecture Notes in Artificial Intelligence, Springer-Verlag, 1997, ISBN 3-540-62927-0.
• [38] Nijssen, S., Kok, J. N.: Faster Association Rules for Multiple Relations., Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001, Seattle, Washington, USA, August 4-10, 2001, 2001.
• [39] Ong, I. M., Dutra, I. d. C., Page, C. D., Santos Costa, V.: Mode Directed Path Finding, Proceedings of the 16th European Conference on Machine Learning, 3720, 2005.
• [40] Page, D.: ILP: Just Do It, Proceedings of the 10th International Conference on Inductive Logic Programming (J. Cussens, A. Frisch, Eds.), 1866, Springer-Verlag, 2000.
• [41] Ramakrishnan, I. V., Rao, P., Sagonas, K., Swift, T., Warren, D. S.: Efficient Access Mechanisms for Tabled Logic Programs, Journal of Logic Programming, 38(1), 1999, 31-54.
• [42] Rocha, R., Fonseca, N. A., Costa, V. S.: On Applying Tabling to Inductive Logic Programming, Proceedings of the 16th European Conference on Machine Learning, ECML-05, Porto, Portugal, October 2005, 3720, Springer-Verlag, Berlin, 2005.
• [43] Santos Costa, V., Srinivasan, A., Camacho, R., Blockeel, H., Demoen, B., Janssens, G., Struyf, J., Vandecasteele, H., Laer, W. V.: Query Transformations for Improving the Efficiency of ILP Systems, Journal of Machine Learning Research, 4, 2003, 465-491.
• [44] Sebag, M., Rouveirol, C.: Tractable induction and classification in first-order logic via stochastic matching, Proceedings of the 15th International Joint Conference on Artificial Intelligence,Morgan Kaufmann, 1997.
• [45] Srinivasan, A.: A study of two sampling methods for analysing large datasets with ILP, Data Mining and Knowledge Discovery, 3(1), 1999, 95-123.
• [46] Srinivasan, A.: The Aleph Manual, University of Oxford, 2004, http://www.comlab.ox.ac.uk/oucl/ research/areas/machlearn/Aleph/.
• [47] Tronc¸on, R., Janssens, G., Vandecasteele, H.: Fast Query Evaluation with (Lazy) Control Flow Compilation, Logic Programming, 20th International Conference, ICLP 2004, Saint-Malo, France, September 6-10, 2004, Proceedings (B. Demoen, V. Lifschitz, Eds.), 3132, Springer, 2004, ISBN 3-540-22671-0.
• [48] Yamamoto, A.: Which Hypotheses Can Be Found with Inverse Entailment?, Proceedings of the 7th International Workshop on Inductive Logic Programming (N. Lavrač, S. Džeroski, Eds.), 1297, Springer-Verlag, 1997.