{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T16:52:23Z","timestamp":1773939143832,"version":"3.50.1"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031436185","type":"print"},{"value":"9783031436192","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,24]],"date-time":"2023-09-24T00:00:00Z","timestamp":1695513600000},"content-version":"vor","delay-in-days":266,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate explainability via short Boolean formulas in the data model based on unary relations. As an explanation of length<jats:italic>k<\/jats:italic>, we take a Boolean formula of length<jats:italic>k<\/jats:italic>that minimizes the error with respect to the target attribute to be explained. We first provide novel quantitative bounds for the expected error in this scenario. We then also demonstrate how the setting works in practice by studying three concrete data sets. In each case, we calculate explanation formulas of different lengths using an encoding in Answer Set Programming. The most accurate formulas we obtain achieve errors similar to other methods on the same data sets. However, due to overfitting, these formulas are not necessarily ideal explanations, so we use cross validation to identify a suitable length for explanations. By limiting to shorter formulas, we obtain explanations that avoid overfitting but are still reasonably accurate and also, importantly, human interpretable.<\/jats:p>","DOI":"10.1007\/978-3-031-43619-2_7","type":"book-chapter","created":{"date-parts":[[2023,9,23]],"date-time":"2023-09-23T15:02:40Z","timestamp":1695481360000},"page":"90-105","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Short Boolean Formulas as\u00a0Explanations in\u00a0Practice"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4714-4637","authenticated-orcid":false,"given":"Reijo","family":"Jaakkola","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2029-7708","authenticated-orcid":false,"given":"Tomi","family":"Janhunen","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1356-8749","authenticated-orcid":false,"given":"Antti","family":"Kuusisto","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5660-3052","authenticated-orcid":false,"given":"Masood Feyzbakhsh","family":"Rankooh","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7301-939X","authenticated-orcid":false,"given":"Miikka","family":"Vilander","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,9,24]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Alviano, M., Dodaro, C., Leone, N., Ricca, F.: Advances in WASP. In: LPNMR 2015, pp. 40\u201354 (2015)","DOI":"10.1007\/978-3-319-23264-5_5"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Audemard, G., Bellart, S., Bounia, L., Koriche, F., Lagniez, J., Marquis, P.: On the computational intelligibility of Boolean classifiers. In: Bienvenu, M., Lakemeyer, G., Erdem, E. (eds.) Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, Online event, 3\u201312 November 2021, pp. 74\u201386 (2021)","DOI":"10.24963\/kr.2021\/8"},{"issue":"6","key":"7_CR3","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/0020-0190(87)90114-1","volume":"24","author":"A Blumer","year":"1987","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.K.: Occam\u2019s razor. Inf. Process. Lett. 24(6), 377\u2013380 (1987)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"7_CR4","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.K.: Learnability and the Vapnik-Chervonenkis dimension. J. ACM 36(4), 929\u2013965 (1989)","journal-title":"J. ACM"},{"issue":"1","key":"7_CR5","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0304-3975(92)90367-O","volume":"100","author":"RA Board","year":"1992","unstructured":"Board, R.A., Pitt, L.: On the necessity of Occam algorithms. Theor. Comput. Sci. 100(1), 157\u2013184 (1992)","journal-title":"Theor. Comput. Sci."},{"issue":"12","key":"7_CR6","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1145\/2043174.2043195","volume":"54","author":"G Brewka","year":"2011","unstructured":"Brewka, G., Eiter, T., Truszczynski, M.: Answer set programming at a glance. Commun. ACM 54(12), 92\u2013103 (2011)","journal-title":"Commun. ACM"},{"issue":"6804","key":"7_CR7","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1038\/35036586","volume":"407","author":"J Feldman","year":"2022","unstructured":"Feldman, J.: Minimization of Boolean complexity in human learning. Nature 407(6804), 630\u2013633 (2022)","journal-title":"Nature"},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Gebser, M., Kaminski, R., Kaufmann, B., Romero, J., Schaub, T.: Progress in clasp series 3. In: LPNMR 2015, pp. 368\u2013383 (2015)","DOI":"10.1007\/978-3-319-23264-5_31"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Answer Set Solving in Practice. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, Williston (2012)","DOI":"10.1007\/978-3-031-01561-8"},{"key":"7_CR10","doi-asserted-by":"publisher","unstructured":"Griffith, J., O\u2019Dea, P., O\u2019Riordan, C.: A neural net approach to data mining: classification of users to aid information management. In: Szczepaniak, P.S., Segovia, J., Kacprzyk, J., Zadeh, L.A. (eds.) Intelligent Exploration of the Web. Studies in Fuzziness and Soft Computing, vol. 111, pp. 389\u2013401. Physica, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-7908-1772-0_23","DOI":"10.1007\/978-3-7908-1772-0_23"},{"key":"7_CR11","unstructured":"Jaakkola, R., Janhunen, T., Kuusisto, A., Rankooh, M.F., Vilander, M.: Explainability via short formulas: the case of propositional logic with implementation. In: RCRA 2022. CEUR Workshop Proceedings, vol. 3281, pp. 64\u201377. CEUR-WS.org (2022)"},{"key":"7_CR12","unstructured":"Jaakkola, R., Janhunen, T., Kuusisto, A., Rankooh, M.F., Vilander, M.: Explainability via short formulas: the case of propositional logic with implementation. CoRR abs\/2209.01403 (2022)"},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Jaakkola, R., Janhunen, T., Kuusisto, A., Rankooh, M.F., Vilander, M.: Short boolean formulas as explanations in practice. CoRR abs\/2307.06971 (2023)","DOI":"10.1007\/978-3-031-43619-2_7"},{"issue":"3","key":"7_CR14","first-page":"13","volume":"37","author":"T Janhunen","year":"2016","unstructured":"Janhunen, T., Niemel\u00e4, I.: The answer set programming paradigm. AI Mag. 37(3), 13\u201324 (2016)","journal-title":"AI Mag."},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"Kearns, M.J., Vazirani, U.: An Introduction to Computational Learning Theory. The MIT Press, Cambridge (1994)","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"Kotz, S., Balakrishnan, N., Johnson, N.: Continuous Multivariate Distributions, Volume 1: Models and Applications. Continuous Multivariate Distributions, Wiley, Hoboken (2004)","DOI":"10.1002\/0471667196.ess5098"},{"issue":"2","key":"7_CR17","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0004-3702(82)90040-6","volume":"18","author":"TM Mitchell","year":"1982","unstructured":"Mitchell, T.M.: Generalization as search. Artif. Intell. 18(2), 203\u2013226 (1982)","journal-title":"Artif. Intell."},{"key":"7_CR18","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/j.spl.2016.08.016","volume":"119","author":"C Pelekis","year":"2016","unstructured":"Pelekis, C., Ramon, J.: A lower bound on the probability that a binomial random variable is exceeding its mean. Stat. Probab. Lett. 119, 305\u2013309 (2016)","journal-title":"Stat. Probab. Lett."},{"issue":"1","key":"7_CR19","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF00116251","volume":"1","author":"JR Quinlan","year":"1986","unstructured":"Quinlan, J.R.: Induction of decision trees. Mach. Learn. 1(1), 81\u2013106 (1986)","journal-title":"Mach. Learn."},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"Shih, A., Choi, A., Darwiche, A.: A symbolic approach to explaining Bayesian network classifiers. In: Lang, J. (ed.) IJCAI, pp. 5103\u20135111 (2018)","DOI":"10.24963\/ijcai.2018\/708"},{"key":"7_CR21","first-page":"262","volume":"10","author":"VG Sigillito","year":"1989","unstructured":"Sigillito, V.G., Wing, S.P., Hutton, L.V., Baker, K.B.: Classification of radar returns from the ionosphere using neural networks. J. Hopkins APL Tech. Dig. 10, 262\u2013266 (1989)","journal-title":"J. Hopkins APL Tech. Dig."},{"key":"7_CR22","unstructured":"\u0160ter, B., Dobnikar, A.: Neural networks in medical diagnosis: comparison with other methods. In: Proceedings of the International Conference on Engineering Applications of Neural Networks (1996)"},{"issue":"11","key":"7_CR23","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"LG Valiant","year":"1984","unstructured":"Valiant, L.G.: A theory of the learnable. Commun. ACM 27(11), 1134\u20131142 (1984)","journal-title":"Commun. ACM"},{"key":"7_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3264-1","volume-title":"The Nature of Statistical Learning Theory","author":"V Vapnik","year":"2013","unstructured":"Vapnik, V.: The Nature of Statistical Learning Theory. Springer, New York (2013). https:\/\/doi.org\/10.1007\/978-1-4757-3264-1"},{"key":"7_CR25","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1007\/3-540-44795-4_48","volume-title":"Machine Learning: ECML 2001","author":"Y Yang","year":"2001","unstructured":"Yang, Y., Webb, G.I.: Proportional k-interval discretization for Naive-Bayes classifiers. In: De Raedt, L., Flach, P. (eds.) ECML 2001. LNCS (LNAI), vol. 2167, pp. 564\u2013575. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44795-4_48"}],"container-title":["Lecture Notes in Computer Science","Logics in Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43619-2_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,22]],"date-time":"2023-12-22T12:56:50Z","timestamp":1703249810000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43619-2_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031436185","9783031436192"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43619-2_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"24 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"JELIA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Conference on Logics in Artificial Intelligence","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Dresden","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 September 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"jelia2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.jelia.eu\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"111","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"11","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"37% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3,6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}