Automatic Learning of Temporal Relations Under the Closed World Assumption

• Autorzy: Nicoletti M. C. , Lisboa F. O. S. S. , Hruschka Jr E. R.
• Języki publikacji: EN

Abstrakty

EN

Time plays an important role in the vast majority of problems and, as such, it is a vital issue to be considered when developing computer systems for solving problems. In the literature, one of the most influential formalisms for representing time is known as Allen's Temporal Algebra based on a set of 13 relations (basic and reversed) that may hold between two time intervals. In spite of having a few drawbacks and limitations, Allen's formalism is still a convenient representation due to its simplicity and implementability and also, due to the fact that it has been the basis of several extensions. This paper explores the automatic learning of Allen's temporal relations by the inductive logic programming system FOIL, taking into account two possible representations for a time interval: (i) as a primitive concept and (ii) as a concept defined by the primitive concept of time point. The goals of the experiments described in the paper are (1) to explore the viability of both representations for use in automatic learning; (2) compare the facility and interpretability of the results; (3) evaluate the impact of the given examples for inducing a proper representation of the relations and (4) experiment with both representations under the assumption of a closed world (CWA), which would ease continuous learning using FOIL. Experimental results are presented and discussed as evidence that the CWA can be a convenient strategy when learning Allen's temporal relations.

Słowa kluczowe

EN

Allen's temporal algebra; automatic learning of temporal relations; inductive logic programming; learning under closed world assumption; time intervals; time points; time representation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 124, nr 1/2
• Strony: 133--151
• Opis fizyczny: Bibliogr. 47 poz., wykr.

Twórcy

autor

Nicoletti M. C.

• DC, UFSCar, S. Carlos & FACCAMP, C. L. Paulista, SP, Brazil

autor

Lisboa F. O. S. S.

• IFSC, USP, S. Carlos, SP, Brazil

autor

Hruschka Jr E. R.

• DC, UFSCar, S. Carlos, SP, Brazil

Bibliografia

• [1] Adlassnig, K.-P., Combi, C., Das, A. K., Keravnou, E. T., Pozzi, G.: Temporal representation and reasoning in medicine: research directions and challenges, Artificial Intelligence in Medicine, vol. 38, 2006, 101-113.
• [2] Aiello, M., Monz, C., Todoran, L., Worring, M.: Document understanding for a broad class of documents, International Journal on Document Analysis and Recognition (IJDAR), vol. 5, no. 1, 2002, 1-16.
• [3] Allen, J. F.: An interval-based representation of temporal knowledge, in: Proc. of The 7th International Joint Conference on Artificial Intelligence (IJCAI81), Vancouver: Morgan Kaufmann, 1981, 221-226.
• [4] Allen, J. F.: Maintaining knowledge about temporal intervals, Communications of the ACM, vol. 26, no. 11, 1983, 832-843.
• [5] Allen, J. F.: Towards a general theory of action and time, Artificial Intelligence, vol. 23, 1984, 123-154.
• [6] Allen, J. F., Hayes, P. J.: A common-sense theory of time, in: Proc. of The 9th International Joint Conference on Artificial Intelligence, Los Angeles: Morgan Kaufmann, 1985, 528-531.
• [7] Allen, J. F., Hayes, P. J.: Moments and points in an interval-based temporal logic, Computational Intelligence, vol. 5, no. 3, 1989, 225-238.
• [8] Allen, J. F.: Time and time again: the many ways to represent time, International Journal of Intelligent Systems, vol. 6, no. 4, 1991, 341-355.
• [9] Allen, J.F., Ferguson, G.: Actions and events in interval temporal logic, Technical Report, The University of Rochester, 1994, 58 pgs.
• [10] Artale, A., Franconi, E.: A temporal description logic for reasoning about actions and plans, Journal of Artificial Intelligence Research, vol. 9, 1998, 463-506.
• [11] Bellazi, R., Larizza, C., Magni, P., Bellazi, R.: Temporal data mining for the quality assessment of hemodialysis services, Artificial Intelligence in Medicine, vol. 34, 2005, 25-39.
• [12] Bouzid, M., Combi, C., Fisher, M., Ligozat, G.: Guest editorial: temporal representation and reasoning, Annals of Mathematics and Artificial Intelligence, vol. 46, no. 3, 2006, 231-234.
• [13] Cameron-Jones, R. M., Quinlan, J. R.: Efficient top-down induction of logic programs, ACM SIGART Bulletin, vol. 5, no. 1, 1994, 33-42.
• [14] Carlson, A.: Coupled semi-supervised learning, PhD. Thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, USA, 2010.
• [15] Chittaro, L., Montanari,A.: Temporal representation and reasoning in artificial intelligence: issues and approaches, Annals of Mathematics and Artificial Intelligence, vol. 28, 2000, 47-106.
• [16] Freksa, C.: Temporal reasoning based on semi-intervals, Artificial Intelligence, vol. 54, nos. 1-2, 1992, 199227.
• [17] Furia, C., Mandrioli, D., Morzenti, A., Rossi, M.: Modeling time in computing: a taxonomy and a comparative survey, ACM Computing Surveys, vol. 42, no. 2, 2010, 1-59.
• [18] Galton, A.: A critical examination of Allen’s theory of action and time, Artificial Intelligence, vol. 42, nos. 2-3, 1990, 159-188.
• [19] Gamper, J., Nejdl, W.: Abstract temporal diagnosis in medical domains, Artificial Intelligence in Medicine, vol. 10, no. 3, 1997, 209-234.
• [20] Hayes, P. J., Allen, J. F.: Short time periods, in: Proc. of The 10th International Joint Conference on Artificial Intelligence (IJCAI87), Milan: Morgan Kaufmann, 1987, 981-983.
• [21] Kietz, J-U.: Some lower bounds for the computational complexity of inductive logic programming, Lecture Notes in Computer Science, vol. 667, P. B. Bradzil (ed.), Springer-Verlag, 1993, 115-123.
• [22] Kietz, J-U., Dzeroski, S.: Inductive logic programming and learnability, SIGARTBulletin, vol. 5, no. 1,1994, 22-32.
• [23] Knight, B., Ma, J.: Time representation: a taxonomy of temporal models, Artificial Intelligence Review, vol. 7, no. 6, 1993, 401-419.
• [24] Kowalski, R., Sergot, M.: A logic-based calculus of events, New Generation Computing, vol. 4, no. 1, 1986, 67-95.
• [25] Ma, J., Knight, B.: A general temporal theory, The Computer Journal, vol. 37, no. 2, 1994, 114-123.
• [26] Mani, I., Pustejovsky, J., Sundheim, B.: Introduction to the special issue on temporal information processing, vol. 3, no. 1, 2004, 1-10.
• [27] McCarthy, J., Hayes, P. J.: Some philosophical problems from the standpoint of artificial intelligence, Machine Intelligence, vol. 4, 1969, 463-502.
• [28] McDermott, D.: A temporal logic for reasoning about processes and plans, Cognitive Science, vol. 6, no. 2, 1982, 101-155.
• [29] Morchen, F.: Algorithms for time series knowledge mining, in: Proc. of The 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia:ACM Press, 2006, 668-673.
• [30] Morchen, F.: A better tool than Allen’s relations for expressing temporal knowledge in interval data, in: Proc. of The 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia: ACM Press, 2006, 25-34.
• [31] Muggleton, S., Feng, C.: Efficient induction of logic programs, in: Proc. of The First Conference on Algorithmic Learning Theory, Tokyo, Japan.
• [32] Nebel, B., Burckert, H. J.: Reasoning about temporal relations: a maximal tractable subclass of Allen’s interval algebra, Journal of the ACM, vol. 42, no. 1, 1995, 43-66.
• [33] Nicoletti, M. C.; Lisboa, F. O. S. S.; Hruschka, E. R.: Learning temporal interval relations using inductive logic programming, Communications in Computer and Information Science, vol. 165, 2011, 90-104.
• [34] Page, C. D., Frish, A. M.: Generalisation and learnability: a study in constrained atoms, in: S. H. Muggleton (ed.), Inductive Logic Programming, Academic Press, 1992, 29-61.
• [35] Plotkin,G. D.: Automatic Methods of Inductive Inference, Ph. D. thesis, Edinburgh University, 1971.
• [36] Quinlan, J. R.: Induction of decision trees, Machine Learning, vol. 1, 1986, 81-106.
• [37] Quinlan, J. R.: Learning from relational data, in: Proc. of The 4th Australian Joint Conference on Artificial Intelligence, World Scientific, 1990, 38-47.
• [38] Quinlan, J. R.: Learning logical definitions from relations, Machine Learning, vol. 5, 1990, 239-266.
• [39] Quinlan, J. R.; Cameron-Jones, R. M.: FOIL - an overview, FOIL Version 5.0, 1993.
• [40] Quinlan, J. R.; Cameron-Jones, R. M.: FOIL: A midterm report, in: Proc. of The European Conference on Machine Learning (ECML), Springer Verlag: Bled, Slovenia, vol. 667, 1993, 3-20.
• [41] Cameron-Jones, R. M., Quinlan, J. R.: Efficient top-down induction of logic programs, ACM SIGART Bulletin, vol. 5, no. 1, 1994, 33-42.
• [42] Robinson, J.: A machine-oriented logic based on the resolution principle, Journal of the ACM, vol. 12, no. 1, 1965, 23-41.
• [43] Roddick, J. F., Mooney, C. H.: Linear temporal sequences and their interpretation using midpoint relationships, IEEE Transactions on Knowledge and Data Engineering, vol. 17, no. 1, 2005, 133-135.
• [44] Sanampudi, S. K., Kumari, G. V.: Temporal reasoning in natural language processing: a survey, International Journal of Computer Applications, vol. 1, no. 4, 2010, 53-57.
• [45] Schockaert, S., De Cock, M., Kerre, E. E.: Fuzzifying Allen’s temporal interval relations, IEEE Transactions on Fuzzy Systems, vol. 16, no. 2, 2008, 517-533.
• [46] Vila, L.: A survey on temporal reasoning in artificial intelligence, AI Communications, vol. 7, 1994, 4-28.
• [47] Wrobel, S.: Higher-order concepts in a tractable knowledge representation, in: Proc. of The 11th German Workshop on Artificial Intelligence - GWAI-87, Informatik-Fachberichte no. 152, Springer-Verlag, 1987, 129-138.