Abstract
FOLD-R is an automated inductive learning algorithm for learning default rules for mixed (numerical and categorical) data. It generates an (explainable) normal logic program (NLP) rule set for classification tasks. We present an improved FOLD-R algorithm, called FOLD-R++, that significantly increases the efficiency and scalability of FOLD-R by orders of magnitude. FOLD-R++ improves upon FOLD-R without compromising or losing information in the input training data during the encoding or feature selection phase. The FOLD-R++ algorithm is competitive in performance with the widely-used XGBoost algorithm, however, unlike XGBoost, the FOLD-R++ algorithm produces an explainable model. FOLD-R++ is also competitive in performance with the RIPPER system, however, on large datasets FOLD-R++ outperforms RIPPER. We also create a powerful tool-set by combining FOLD-R++ with s(CASP)—a goal-directed answer set programming (ASP) execution engine—to make predictions on new data samples using the normal logic program generated by FOLD-R++. The s(CASP) system also produces a justification for the prediction. Experiments presented in this paper show that our improved FOLD-R++ algorithm is a significant improvement over the original design and that the s(CASP) system can make predictions in an efficient manner as well.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The s(CASP) system is freely available at https://gitlab.software.imdea.org/ciao-lang/sCASP.
- 2.
The FOLD-R++ system is available at https://github.com/hwd404/FOLD-R-PP.
References
Arias, J., Carro, M., Chen, Z., Gupta, G.: Justifications for goal-directed constraint answer set programming. In: Proceedings 36th International Conference on Logic Programming (Technical Communications). EPTCS, vol. 325, pp. 59–72 (2020)
Arias, J., Carro, M., Salazar, E., Marple, K., Gupta, G.: Constraint answer set programming without grounding. Theory Pract. Logic Program. 18(3–4), 337–354 (2018)
Chen, T., Guestrin, C.: XGBoost: a scalable tree boosting system. In: Proceedings of the 22nd ACM SIGKDD, KDD 2016, pp. 785–794 (2016)
Cohen, W.W.: Fast effective rule induction. In: Proceedings of the 12th ICML, ICML 1995, pp. 115–123. Morgan Kaufmann Publishers Inc., San Francisco (1995). http://dl.acm.org/citation.cfm?id=3091622.3091637
Craven, M.W., Shavlik, J.W.: Extracting tree-structured representations of trained networks. In: Proceedings of the 8th International Conference on Neural Information Processing Systems, NIPS 1995, pp. 24–30. MIT Press, Cambridge (1995)
Friedman, J.H., Popescu, B.E., et al.: Predictive learning via rule ensembles. Ann. Appl. Stat. 2(3), 916–954 (2008)
Gelfond, M., Kahl, Y.: Knowledge Representation, Reasoning, and the Design of Intelligent Agents: The Answer-Set Programming Approach. Cambridge University Press (2014)
Gunning, D.: Explainable Artificial Intelligence (XAI) (2015). https://www.darpa.mil/program/explainable-artificial-intelligence
Landwehr, N., Kersting, K., Raedt, L.D.: nFOIL: integrating Naïve Bayes and FOIL. In: Proceedings of the Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, Pittsburgh, Pennsylvania, USA, 9–13 July 2005, pp. 795–800 (2005)
Landwehr, N., Passerini, A., Raedt, L.D., Frasconi, P.: kFOIL: learning simple relational kernels. In: Proceedings of the Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, MA, USA, 16–20 July 2006, pp. 389–394 (2006)
Law, M.: Inductive learning of answer set programs. Ph.D. thesis, Imperial College London, UK (2018)
Lichman, M.: UCI, Machine Learning Repository (2013). http://archive.ics.uci.edu/ml
Lloyd, J.: Foundations of Logic Programming, 2nd Ext. edn. Springer, Heidelberg (1987)
Muggleton, S.: Inductive logic programming. New Gen. Comput. 8(4) (1991)
Muggleton, S., Lodhi, H., Amini, A., Sternberg, M.J.E.: Support vector inductive logic programming. In: Hoffmann, A., Motoda, H., Scheffer, T. (eds.) DS 2005. LNCS (LNAI), vol. 3735, pp. 163–175. Springer, Heidelberg (2005). https://doi.org/10.1007/11563983_15
Muggleton, S., et al.: ILP turns 20. Mach. Learn. 86(1), 3–23 (2011). https://doi.org/10.1007/s10994-011-5259-2
Núñez, H., Angulo, C., Catalá, A.: Rule extraction from support vector machines. In: Proceedings of European Symposium on Artificial Neural Networks, pp. 107–112 (2002)
Plotkin, G.D.: A further note on inductive generalization. Mach. Intell. 6, 101–124 (1971)
Quinlan, J.R.: Learning logical definitions from relations. Mach. Learn. 5, 239–266 (1990)
Quinlan, J.R.: C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers Inc., San Francisco (1993)
Reiter, R.: A logic for default reasoning. Artif. Intell. 13(1–2), 81–132 (1980)
Sakama, C.: Induction from answer sets in nonmonotonic logic programs. ACM Trans. Comput. Log. 6(2), 203–231 (2005)
Shakerin, F.: Logic programming-based approaches in explainable AI and natural language processing. Ph.D. thesis, Department of Computer Science, The University of Texas at Dallas (2020)
Shakerin, F., Salazar, E., Gupta, G.: A new algorithm to automate inductive learning of default theories. TPLP 17(5–6), 1010–1026 (2017)
Srinivasan, A.: The Aleph Manual (2001). https://www.cs.ox.ac.uk/activities/programinduction/Aleph/aleph.html
Takemura, A., Inoue, K.: Generating explainable rule sets from tree-ensemble learning methods by answer set programming. Electron. Proc. Theor. Comput. Sci. 345, 127–140 (2021)
Wikipedia contributors: Prefix sum Wikipedia, the free encyclopedia (2021). https://en.wikipedia.org/wiki/Prefix_sum. Accessed 5 Oct 2021
Zeng, Q., Patel, J.M., Page, D.: QuickFOIL: scalable inductive logic programming. Proc. VLDB Endow. 8(3), 197–208 (2014)
Acknowledgement
Authors gratefully acknowledge support from NSF grants IIS 1718945, IIS 1910131, IIP 1916206, and from Amazon Corp, Atos Corp and US DoD. We are grateful to Joaquin Arias and the s(CASP) team for their work on providing facilities for generating the justification tree and English encoding of rules in s(CASP).
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Wang, H., Gupta, G. (2022). FOLD-R++: A Scalable Toolset for Automated Inductive Learning of Default Theories from Mixed Data. In: Hanus, M., Igarashi, A. (eds) Functional and Logic Programming. FLOPS 2022. Lecture Notes in Computer Science, vol 13215. Springer, Cham. https://doi.org/10.1007/978-3-030-99461-7_13
Download citation
DOI: https://doi.org/10.1007/978-3-030-99461-7_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-99460-0
Online ISBN: 978-3-030-99461-7
eBook Packages: Computer ScienceComputer Science (R0)