Propositional Kernels

Mirko Polato; Fabio Aiolli

doi:10.3390/e23081020

journal article Open Access Aug 07, 2021

Propositional Kernels

Mirko Polato

Fabio Aiolli

Entropy Vol. 23 No. 8 pp. 1020 · MDPI AG

View at Publisher Save 10.3390/e23081020

Abstract

The pervasive presence of artificial intelligence (AI) in our everyday life has nourished the pursuit of explainable AI. Since the dawn of AI, logic has been widely used to express, in a human-friendly fashion, the internal process that led an (intelligent) system to deliver a specific output. In this paper, we take a step forward in this direction by introducing a novel family of kernels, called Propositional kernels, that construct feature spaces that are easy to interpret. Specifically, Propositional Kernel functions compute the similarity between two binary vectors in a feature space composed of logical propositions of a fixed form. The Propositional kernel framework improves upon the recent Boolean kernel framework by providing more expressive kernels. In addition to the theoretical definitions, we also provide an algorithm (and the source code) to efficiently construct any propositional kernel. An extensive empirical evaluation shows the effectiveness of Propositional kernels on several artificial and benchmark categorical data sets.

Topics

No keywords indexed for this article. Browse by subject →

References

32

[1]

Došilović, F.K., Brčić, M., and Hlupić, N. (2018, January 21–25). Explainable artificial intelligence: A survey. Proceedings of the International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), Opatija, Croatia. 10.23919/mipro.2018.8400040

[2]

Hall, P., Gill, N., and Schmidt, N. (2019, January 8–14). Proposed Guidelines for the Responsible Use of Explainable Machine Learning. Proceedings of the NeurIPS 2019 Workshop on Robust AI in Financial Services: Data, Fairness, Explainability, Trustworthiness, and Privacy, Vancouver, Canada.

[3]

Jeyakumar, J.V., Noor, J., Cheng, Y.H., Garcia, L., and Srivastava, M. (2021, August 07). How Can I Explain This to You? An Empirical Study of Deep Neural Network Explanation Methods. Available online: https://www.semanticscholar.org/paper/How-Can-I-Explain-This-to-You-An-Empirical-Study-of-Jeyakumar-Noor/3f9474022c113b087cb0ccb65ddea05672e22745.

[4]

Shi, H., Fu, W., Li, B., Shao, K., and Yang, D. (2021). Intelligent Fault Identification for Rolling Bearings Fusing Average Refined Composite Multiscale Dispersion Entropy-Assisted Feature Extraction and SVM with Multi-Strategy Enhanced Swarm Optimization. Entropy, 23. 10.3390/e23050527

[5]

Massaroppe, L., and Baccalá, L.A. (2019). Kernel Methods for Nonlinear Connectivity Detection. Entropy, 21. 10.3390/e21060610

[6]

Martino, A., and Rizzi, A. (2020). (Hyper)graph Kernels over Simplicial Complexes. Entropy, 22. 10.3390/e22101155

[7]

Barakat "Rule extraction from support vector machines: A review" Neurocomputing (2010) 10.1016/j.neucom.2010.02.016

[8]

Polato, M., Lauriola, I., and Aiolli, F. (2018). A Novel Boolean Kernels Family for Categorical Data. Entropy, 20. 10.3390/e20060444

[9]

Polato "Boolean kernels for rule based interpretation of support vector machines" Neurocomputing (2019) 10.1016/j.neucom.2018.11.094

[10]

Polato, M. (2018). Definition and Learning of Logic-Based Kernels for Categorical Data, and Application to Collaborative Filtering. [Ph.D. Thesis, University of Padova].

[11]

Sadohara, K. (2001, January 25–28). Learning of Boolean Functions Using Support Vector Machines. Proceedings of the International Conference on Algorithmic Learning Theory (ALT), Washington DC, USA. 10.1007/3-540-45583-3_10

[12]

Kimeldorf "Some Results on Tchebycheffian Spline Functions" J. Math. Anal. Appl. (1971) 10.1016/0022-247x(71)90184-3

[13]

Kernel methods in machine learning

Thomas Hofmann, Bernhard Schölkopf, Alexander J. Smola

The Annals of Statistics 2008 10.1214/009053607000000677

[14]

Watkins, C. (1999). Kernels from Matching Operations, Royal Holloway, University of London. Technical Report.

[15]

Khardon, R., Roth, D., and Servedio, R. (2001). Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms, University of Illinois at Urbana-Champaign. Technical Report. 10.7551/mitpress/1120.003.0059

[16]

Sadohara, K. (2002, January 9–12). On a Capacity Control Using Boolean Kernels for the Learning of Boolean Functions. Proceedings of the International Conference on Data Mining (ICDM), Maebashi, Japan.

[17]

Zhang, Y., Li, Z., Kang, M., and Yan, J. (2003, January 15–18). Improving the classification performance of boolean kernels by applying Occam’s razor. Proceedings of the International Conference on Computational Intelligence, Robotics and Autonomous Systems (CIRAS), Singapore.

[18]

Shawe-Taylor, J., and Cristianini, N. (2004). Kernel Methods for Pattern Analysis, Cambridge University Press. 10.1017/cbo9780511809682

[19]

Kusunoki, Y., and Tanino, T. (2014, January 26–29). Boolean kernels and clustering with pairwise constraints. Proceedings of the International Conference on Granular Computing (GrC), Chongqing, China. 10.1109/grc.2014.6982823

[20]

Kowalczyk, A., Smola, A.J., and Williamson, R.C. (2021, August 07). Kernel Machines and Boolean Functions. Available online: https://www.semanticscholar.org/paper/Kernel-Machines-and-Boolean-Functions-Kowalczyk-Smola/ea1244e3a362ab880e9f04b9ec9b9946f387b8bd.

[21]

Khardon, R., and Servedio, R.A. (2021, August 07). Maximum Margin Algorithms with Boolean Kernels. Available online: https://www.jmlr.org/papers/volume6/khardon05a/khardon05a.pdf.

[22]

Cui, K., Han, F., and Wang, P. (2008, January 25–27). Research on Face Recognition Based on Boolean Kernel SVM. Proceedings of the International Conference on Natural Computation (ICNC), Jinan, China. 10.1109/icnc.2008.721

[23]

Cui, K., and Du, Y. (2009, January 25–26). Application of Boolean Kernel Function SVM in Face Recognition. Proceedings of the International Conference on Networks Security, Wireless Communications and Trusted Computing (NSWCTC), Wuhan, China. 10.1109/nswctc.2009.172

[24]

Liu "Applications of Support Vector Machine Based on Boolean Kernel to Spam Filtering" Mod. Appl. Sci. (2009) 10.5539/mas.v3n10p27

[25]

Cui, K., and Du, Y. (2009, January 25–26). Short-Term Load Forecasting Based on the BKF-SVM. Proceedings of the International Conference on Networks Security, Wireless Communications and Trusted Computing (NSWCTC), Wuhan, China. 10.1109/nswctc.2009.170

[26]

Polato "Boolean kernels for collaborative filtering in top-N item recommendation" Neurocomputing (2018) 10.1016/j.neucom.2018.01.057

[27]

Polato, M., and Aiolli, F. (2016, January 27–29). Kernel based collaborative filtering for very large scale top-N item recommendation. Proceedings of the European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN), Bruges, Belgium.

[28]

Ben-Ari, M. (2012). Mathematical Logic for Computer Science, Springer Publishing Company, Incorporated. [3rd ed.]. 10.1007/978-1-4471-4129-7

[29]

Chung, K.M., Kao, W.C., Sun, T., Wang, L.L., and Lin, C.J. (2002, January 18–22). Radius margin bounds for support vector machines with the RBF kernel. Proceedings of the International Conference on Neural Information Processing (ICONIP), Singapore.

[30]

Do, H., and Kalousis, A. (2013, January 16–21). Convex Formulations of Radius-Margin Based Support Vector Machines. Proceedings of the International Conference on Machine Learning (ICML), Atlanta, GA, USA.

[31]

Donini "Learning deep kernels in the space of dot product polynomials" Mach. Learn. (2017) 10.1007/s10994-016-5590-8

[32]

Lauriola, I., Polato, M., and Aiolli, F. (2021, August 07). Radius-Margin Ratio Optimization for Dot-Product Boolean Kernel Learning. Available online: https://www.researchgate.net/publication/318468451_Radius-Margin_Ratio_Optimization_for_Dot-Product_Boolean_Kernel_Learning.

Metrics

2

Citations

32

References

Details