×

On Shapley value interpretability in concept-based learning with formal concept analysis. (English) Zbl 1511.68272

Summary: We propose the usage of two power indices from cooperative game theory and public choice theory for ranking attributes of closed sets, namely intents of formal concepts (or closed itemsets). The introduced indices are related to extensional concept stability and are also based on counting of generators, especially of those that contain a selected attribute. The introduction of such indices is motivated by the so-called interpretable machine learning, which supposes that we do not only have the class membership decision of a trained model for a particular object, but also a set of attributes (in the form of JSM-hypotheses or other patterns) along with individual importance of their single attributes (or more complex constituent elements). We characterise computation of the Shapley and Banzhaf-Penrose values of a formal concept in terms of minimal generators and their order filters, provide the reader with their properties important for computation purposes, prove related #P-completeness results, and show experimental results with model and real datasets. We also show how this approach can be applied in both supervised (classification) and unsupervised (pattern mining) settings.

MSC:

68T30 Knowledge representation
68T05 Learning and adaptive systems in artificial intelligence

Software:

shap
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aleskerov, F.T., Habina, E.L., Swartz, D.A.: Binary Relations, Graphs, and Collective Decisions. Fizmatlit. https://id.hse.ru/books/25246294.html (2012) · Zbl 1277.91001
[2] Babin, M.A., Kuznetsov, S.O.: Approximating concept stability. In: Domenach, F, Ignatov, DI, Poelmans, J (eds.) Formal Concept Analysis - 10th International Conference, ICFCA 2012, Leuven, Belgium, May 7-10, 2012. Proceedings, Lecture Notes in Computer Science. doi:10.1007/978-3-642-29892-9_7, vol. 7278, pp 7-15. Springer (2012) · Zbl 1360.68798
[3] Banzhaf, JC, Weighted voting doesn’t work: a mathematical analysis, Rutgers Law Review, 19, 317-343 (1965)
[4] Borwein, PB, On the complexity of calculating factorials, J. Algo., 6, 3, 376-380 (1985) · Zbl 0576.68027 · doi:10.1016/0196-6774(85)90006-9
[5] Faigle, U.; Grabisch, M.; Jiménez-Losada, A.; Ordóñez, M., Games on concept lattices: Shapley value and core, Discrete Appl. Math, 198, 29-47 (2016) · Zbl 1334.91008 · doi:10.1016/j.dam.2015.08.004
[6] Fayyad, UM; Piatetsky-Shapiro, G.; Smyth, P., From data mining to knowledge discovery in databases, AI Mag., 17, 3, 37-54 (1996)
[7] Finn, V.: On Machine-oriented Formalization of Plausible Reasoning in F.Bacon-J.S.Mill Style. Semiotika i Informatika (20):35-101. (in Russian) (1983) · Zbl 0521.03012
[8] Ganter, B.; Obiedkov, SA, Conceptual Exploration (2016), Berlin: Springer, Berlin · Zbl 1357.68004 · doi:10.1007/978-3-662-49291-8
[9] Ganter, B.; Wille, R., Formal Concept Analysis - Mathematical Foundations (1999), Berlin: Springer, Berlin · Zbl 0909.06001 · doi:10.1007/978-3-642-59830-2
[10] Gionis, A.; Mannila, H.; Mielikäinen, T.; Tsaparas, P., Assessing data mining results via swap randomization, TKDD, 1, 3, 14 (2007) · Zbl 05463418 · doi:10.1145/1297332.1297338
[11] Ignatov, D.I., Kwuida, L.: Interpretable concept-based classification with shapley values. In: Alam, M., Braun, T., Yun, B. (eds.) Ontologies and Concepts in Mind and Machine - 25th International Conference on Conceptual Structures, ICCS 2020, Bolzano, Italy, September 18-20, 2020, Proceedings, Lecture Notes in Computer Science. doi:10.1007/978-3-030-57855-8_7, vol. 12277, pp 90-102. Springer (2020) · Zbl 1476.68231
[12] Ignatov, D.I., Kwuida, L.: Shapley and Banzhaf vectors of a formal concept. In: Valverde-Albacete, F.J., Trnecka, M. (eds.) Proceedings of the Fifthteenth International Conference on Concept Lattices and Their Applications, Tallinn, Estonia, June 29-July 1, 2020, CEUR Workshop Proceedings. http://ceur-ws.org/Vol-2668/paper20.pdf, vol. 2668, pp 259-271. CEUR-WS.org (2020)
[13] Ignatov, D.I., Nenova, E., Konstantinova, N., Konstantinov, A.V.: Boolean matrix factorisation for collaborative filtering: An FCA-based approach. In: Agre, G., Hitzler, P., Krisnadhi, A.A., Kuznetsov, S.O. (eds.) Artificial Intelligence: Methodology, Systems, and Applications - 16th International Conference, AIMSA 2014, Varna, Bulgaria, September 11-13, 2014. Proceedings, Lecture Notes in Computer Science. doi:10.1007/978-3-319-10554-3_5, vol. 8722, pp 47-58. Springer (2014)
[14] Kim, B., Koyejo, O., Khanna, R.: Examples are not enough, learn to criticize! Criticism for interpretability. In: Lee, D.D., Sugiyama, M., von Luxburg, U., Guyon, I., Garnett, R. (eds.) Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 2280-2288. http://papers.nips.cc/paper/6300-examples-are-not-enough-learn-to-criticize-criticism-for-interpretability (2016)
[15] Konecny, J.: On attribute reduction in concept lattices: Methods based on discernibility matrix are outperformed by basic clarification and reduction. Information Sciences 415-416, 199-212. doi:10.1016/j.ins.2017.06.013. http://www.sciencedirect.com/science/article/pii/S0020025516320291 (2017) · Zbl 1435.68321
[16] Kurz, S.: A note on limit results for the Penrose-Banzhaf index. Theor. Decis. 88(2), 191-203 (2020). (doi:10.1007/s11238-019-09726-3) · Zbl 1433.91010
[17] Kuznetsov, S.O.: JSM-Method as a machine learning method. Method. Itogi Nauki i Tekhniki, ser. Informatika (15),17-53. (in Russian) (1991)
[18] Kuznetsov, SO, Stability as an estimate of the degree of substantiation of hypotheses derived on the basis of operational similarity, Nauchn. Tekh. Inf. Ser., 2, 12, 217-29 (1991)
[19] Kuznetsov, SO, Mathematical aspects of concept analysis, J. Math. Sci., 80, 2, 1654-1698 (1996) · Zbl 0885.06001 · doi:10.1007/BF02362847
[20] Kuznetsov, S.O.: Machine learning and formal concept analysis. In: Concept Lattices, Second International Conference on Formal Concept Analysis, ICFCA 2004, Sydney, Australia, February 23-26, 2004, Proceedings, pp. 287-312. doi:10.1007/978-3-540-24651-0_25 (2004) · Zbl 1198.68194
[21] Kuznetsov, S.O.: Galois connections in data analysis: Contributions from the Soviet era and modern Russian research. In: Ganter, B., Stumme, G., Wille, R. (eds.) Formal Concept Analysis, Foundations and Applications, Lecture Notes in Computer Science. doi:10.1007/11528784_11, vol. 3626, pp 196-225. Springer (2005) · Zbl 1152.68628
[22] Kuznetsov, SO, On stability of a formal concept, Ann. Math. Artif. Intell., 49, 1-4, 101-115 (2007) · Zbl 1129.68086 · doi:10.1007/s10472-007-9053-6
[23] Kuznetsov, SO; Makhalova, TP, On interestingness measures of formal concepts, Inf. Sci., 442-443, 202-219 (2018) · Zbl 1440.68282 · doi:10.1016/j.ins.2018.02.032
[24] Kuznetsov, S.O., Obiedkov, S.A., Roth, C.: Reducing the representation complexity of lattice-based taxonomies. In: Priss, U., Polovina, S., Hill, R. (eds.) Conceptual Structures: Knowledge Architectures for Smart Applications, 15th International Conference on Conceptual Structures, ICCS 2007, Sheffield, UK, July 22-27, 2007, Proceedings, Lecture Notes in Computer Science. doi:10.1007/978-3-540-73681-3_18, vol. 4604, pp 241-254. Springer (2007)
[25] Kwuida, L., Ignatov, D.I., et al.: On Interpretability and Similarity in Concept-Based Machine Learning. In: van der Aalst, W.M.P. (ed.) Analysis of Images, Social Networks and Texts, pp 28-54. Springer International Publishing, Cham (2021)
[26] Lallich, S.; Teytaud, O.; Prudhomme, E., Association Rule Interestingness: Measure and Statistical Validation, 251-275 (2007), Berlin: Springer, Berlin
[27] Lipton, ZC, The mythos of model interpretability, Commun. ACM, 61, 10, 36-43 (2018) · doi:10.1145/3233231
[28] Lundberg, S.M., Lee, S.I.: A unified approach to interpreting model predictions. In: Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. (eds.) Advances in Neural Information Processing Systems. http://papers.nips.cc/paper/7062-a-unied-approach-to-interpreting-model-predictions.pdf, vol. 30, pp 4765-4774. Curran Associates Inc (2017)
[29] Maafa, K., Nourine, L., Radjef, M.S.: Algorithms for computing the Shapley value of cooperative games on lattices. Discret. Appl. Math. 249, 91-105 (2018). doi:10.1016/j.dam.2018.03.022. http://www.sciencedirect.com/science/article/pii/S0166218X18301136. Concept Lattices and Applications: Recent Advances and New Opportunities · Zbl 1417.91054
[30] Mill, J.S.: A system of logic, ratiocinative and inductive, being a connected view of the principles of evidence and the methods of scientific investigation. Longmans, Green, and Co. London (1843)
[31] Molnar, C.: Interpretable Machine Learning. https://christophm.github.io/interpretable-ml-book/ (2019)
[32] Penrose, LS, The elementary statistics of majority voting, J. R. Stat. Soc., 109, 1, 53-57 (1946) · doi:10.2307/2981392
[33] Roth, C., Obiedkov, S.A., Kourie, D.G.: Towards concise representation for taxonomies of epistemic communities. In: Yahia, S.B., Nguifo, E.M., Belohlávek, R. (eds.) Concept Lattices and Their Applications, Fourth International Conference, CLA 2006, Tunis, Tunisia, October 30 - November 1, 2006, Selected Papers, Lecture Notes in Computer Science. doi:10.1007/978-3-540-78921-5_17, vol. 4923, pp 240-255. Springer (2006) · Zbl 1133.68454
[34] Shapley, LS, A value for n-person games, Contributions to the Theory of Games, 2, 28, 307-317 (1953) · Zbl 0050.14404
[35] Strumbelj, E.; Kononenko, I., Explaining prediction models and individual predictions with feature contributions, Knowl. Inf. Syst., 41, 3, 647-665 (2014) · doi:10.1007/s10115-013-0679-x
[36] Tatti, N., Moerchen, F.: Finding Robust Itemsets under Subsampling. In: Cook, D.J., Pei, J., Wang, W., Zaïane, O.R., Wu, X. (eds.) 11th IEEE International Conference on Data Mining, ICDM 2011, Vancouver, BC, Canada, December 11-14, 2011. doi:10.1109/ICDM.2011.69, pp 705-714. IEEE Computer Society (2011)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.