Document Open Access Logo

Cumulative Scoring-Based Induction of Default Theories

Authors Farhad Shakerin , Gopal Gupta

PDF
Thumbnail PDF

File

OASIcs.ICLP.2018.2.pdf
  • Filesize: 477 kB
  • 15 pages

Document Identifiers

Author Details

Farhad Shakerin
  • The University of Texas at Dallas, Texas, USA
Gopal Gupta
  • The University of Texas at Dallas, Texas, USA

Funding

Authors are partially supported by NSF Grant IIS 171894

Cite As Get BibTex

Farhad Shakerin and Gopal Gupta. Cumulative Scoring-Based Induction of Default Theories. In Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018). Open Access Series in Informatics (OASIcs), Volume 64, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/OASIcs.ICLP.2018.2

Abstract

Significant research has been conducted in recent years to extend Inductive Logic Programming (ILP) methods to induce a more expressive class of logic programs such as answer set programs. The methods proposed perform an exhaustive search for the correct hypothesis. Thus, they are sound but not scalable to real-life datasets. Lack of scalability and inability to deal with noisy data in real-life datasets restricts their applicability. In contrast, top-down ILP algorithms such as FOIL, can easily guide the search using heuristics and tolerate noise. They also scale up very well, due to the greedy nature of search for best hypothesis. However, in some cases despite having ample positive and negative examples, heuristics fail to direct the search in the correct direction. In this paper, we introduce the FOLD 2.0 algorithm - an enhanced version of our recently developed algorithm called FOLD. Our original FOLD algorithm automates the inductive learning of default theories. The enhancements presented here preserve the greedy nature of hypothesis search during clause specialization. These enhancements also avoid being stuck in local optima - a major pitfall of FOIL-like algorithms. Experiments that we report in this paper, suggest a significant improvement in terms of accuracy and expressiveness of the class of induced hypotheses. To the best of our knowledge, our FOLD 2.0 algorithm is the first heuristic based, scalable, and noise-resilient ILP system to induce answer set programs.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Inductive logic learning
Keywords
  • Inductive Logic Programming
  • Negation As Failure
  • Answer Set Programming
  • Default reasoning
  • Machine learning

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Domenico Corapi, Alessandra Russo, and Emil Lupu. Inductive Logic Programming in Answer Set Programming. In Stephen Muggleton, Alireza Tamaddoni-Nezhad, and Francesca A. Lisi, editors, Inductive Logic Programming - 21st International Conference, ILP 2011, Windsor Great Park, UK, July 31 - August 3, 2011, Revised Selected Papers, volume 7207 of Lecture Notes in Computer Science, pages 91-97. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-31951-8_12.
  2. Johannes Fürnkranz. FOSSIL: A robust relational learner. In Francesco Bergadano and Luc De Raedt, editors, Machine Learning: ECML-94, pages 122-137, Berlin, Heidelberg, 1994. Springer Berlin Heidelberg. Google Scholar
  3. Michael Gelfond and Vladimir Lifschitz. The Stable Model Semantics for Logic Programming. In Robert A. Kowalski and Kenneth A. Bowen, editors, Logic Programming, Proceedings of the Fifth International Conference and Symposium, Seattle, Washington, August 15-19, 1988 (2 Volumes), pages 1070-1080. MIT Press, 1988. Google Scholar
  4. Mark Law, Alessandra Russo, and Krysia Broda. Inductive Learning of Answer Set Programs. In Eduardo Fermé and João Leite, editors, Logics in Artificial Intelligence - 14th European Conference, JELIA 2014, Funchal, Madeira, Portugal, September 24-26, 2014. Proceedings, volume 8761 of LNCS, pages 311-325. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-11558-0_22.
  5. M. Lichman. UCI machine learning repository, 2013. URL: http://archive.ics.uci.edu/ml.
  6. Marco Lippi, Manfred Jaeger, Paolo Frasconi, and Andrea Passerini. Relational information gain. Machine Learning, 83(2):219-239, May 2011. URL: http://dx.doi.org/10.1007/s10994-010-5194-7.
  7. John Mingers. An Empirical Comparison of Selection Measures for Decision-Tree Induction. Machine Learning, 3:319-342, 1989. Google Scholar
  8. Thomas M. Mitchell. Machine Learning. McGraw-Hill, Inc., New York, NY, USA, 1 edition, 1997. Google Scholar
  9. Stephen Muggleton. Inductive Logic Programming. New Generation Comput., 8(4):295-318, 1991. URL: http://dx.doi.org/10.1007/BF03037089.
  10. Stephen Muggleton. Inverse Entailment and Progol. New Generation Comput., 13(3&4):245-286, 1995. URL: http://dx.doi.org/10.1007/BF03037227.
  11. G. D. Plotkin. A further note on inductive generalization, In machine Intelligence, volume 6, pages 101-124, 1971. Google Scholar
  12. J. R. Quinlan. Determinate Literals in Inductive Logic Programming. In Proceedings of the 12th International Joint Conference on Artificial Intelligence - Volume 2, IJCAI'91, pages 746-750, San Francisco, CA, USA, 1991. Morgan Kaufmann Publishers Inc. URL: http://dl.acm.org/citation.cfm?id=1631552.1631572.
  13. J. Ross Quinlan. Learning Logical Definitions from Relations. Machine Learning, 5:239-266, 1990. URL: http://dx.doi.org/10.1007/BF00117105.
  14. Oliver Ray. Nonmonotonic abductive inductive learning. Journal of Applied Logic, 7(3):329-340, 2009. Special Issue: Abduction and Induction in Artificial Intelligence. URL: http://dx.doi.org/10.1016/j.jal.2008.10.007.
  15. Raymond Reiter. A Logic for Default Reasoning. Artif. Intell., 13(1-2):81-132, 1980. URL: http://dx.doi.org/10.1016/0004-3702(80)90014-4.
  16. Chiaki Sakama. Induction from answer sets in nonmonotonic logic programs. ACM Trans. Comput. Log., 6(2):203-231, 2005. URL: http://dx.doi.org/10.1145/1055686.1055687.
  17. Chiaki Sakama and Katsumi Inoue. Brave induction: a logical framework for learning from incomplete information. Machine Learning, 76(1):3-35, 2009. URL: http://dx.doi.org/10.1007/s10994-009-5113-y.
  18. Mathieu Serrurier and Henri Prade. Introducing possibilistic logic in ILP for dealing with exceptions. Artificial Intelligence, 171:939-950, 2007. Google Scholar
  19. Farhad Shakerin and Gopal Gupta. Technical Report, Heuristic Based Induction of Answer Set Programs: From Default theories to combinatorial problems, http://arxiv.org/abs/1802.06462, 2018.
  20. Farhad Shakerin, Elmer Salazar, and Gopal Gupta. A new algorithm to automate inductive learning of default theories. TPLP, 17(5-6):1010-1026, 2017. URL: http://dx.doi.org/10.1017/S1471068417000333.
  21. Ashwin Srinivasan, Stephen Muggleton, and Michael Bain. Distinguishing Exceptions from Noise in Non-Monotonic Learning,In S. Muggleton and K. Furukawa, editors, Second International Inductive Logic Programming Workshop (ILP92), 1996. Google Scholar
  22. James Wogulis. Revising Relational Domain Theories. In Lawrence Birnbaum and Gregg Collins, editors, Proceedings of the Eighth International Workshop (ML91), Northwestern University, Evanston, Illinois, USA, pages 462-466. Morgan Kaufmann, 1991. Google Scholar
  23. Qiang Zeng, Jignesh M. Patel, and David Page. QuickFOIL: Scalable Inductive Logic Programming. Proc. VLDB Endow., 8(3):197-208, November 2014. URL: http://dx.doi.org/10.14778/2735508.2735510.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact