{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T15:57:12Z","timestamp":1786636632305,"version":"build-2736575974"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:p>Sophisticated machine models are increasingly used for high-stakes decisions in everyday life. There is an urgent need to develop effective explanation techniques for such automated decisions. Rule-Based Explanations have been proposed for high-stake decisions like loan applications, because they increase the users' trust in the decision. However, rule-based explanations are very inefficient to compute, and existing systems sacrifice their quality in order to achieve reasonable performance. We propose a novel approach to compute rule-based explanations, by using a different type of explanation, Counterfactual Explanations, for which several efficient systems have already been developed. We prove a Duality Theorem, showing that rule-based and counterfactual-based explanations are dual to each other, then use this observation to develop an efficient algorithm for computing rule-based explanations, which uses the counterfactual-based explanation as an oracle. We conduct extensive experiments showing that our system computes rule-based explanations of higher quality, and with the same or better performance, than two previous systems, MinSetCover and Anchor.<\/jats:p>","DOI":"10.14778\/3570690.3570693","type":"journal-article","created":{"date-parts":[[2023,1,23]],"date-time":"2023-01-23T17:29:55Z","timestamp":1674494995000},"page":"420-432","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Computing Rule-Based Explanations by Leveraging Counterfactuals"],"prefix":"10.14778","volume":"16","author":[{"given":"Zixuan","family":"Geng","sequence":"first","affiliation":[{"name":"University of Washington"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maximilian","family":"Schleich","sequence":"additional","affiliation":[{"name":"Relational AI"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,1,23]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Javier Antoran Umang Bhatt Tameem Adel Adrian Weller and Jos\u00e9 Miguel Hern\u00e1ndez-Lobato. 2021. Getting a {CLUE}: A Method for Explaining Uncertainty Estimates. https:\/\/openreview.net\/forum?id=XSLF1XFq5h  Javier Antoran Umang Bhatt Tameem Adel Adrian Weller and Jos\u00e9 Miguel Hern\u00e1ndez-Lobato. 2021. Getting a {CLUE}: A Method for Explaining Uncertainty Estimates. https:\/\/openreview.net\/forum?id=XSLF1XFq5h"},{"key":"e_1_2_1_2_1","volume-title":"How to Explain Individual Classification Decisions. J. Mach. Learn. Res. 11 (aug","author":"Baehrens David","year":"2010","unstructured":"David Baehrens , Timon Schroeter , Stefan Harmeling , Motoaki Kawanabe , Katja Hansen , and Klaus-Robert M\u00fcller . 2010. How to Explain Individual Classification Decisions. J. Mach. Learn. Res. 11 (aug 2010 ), 1803--1831. David Baehrens, Timon Schroeter, Stefan Harmeling, Motoaki Kawanabe, Katja Hansen, and Klaus-Robert M\u00fcller. 2010. How to Explain Individual Classification Decisions. J. Mach. Learn. Res. 11 (aug 2010), 1803--1831."},{"key":"e_1_2_1_3_1","unstructured":"Chaofan Chen Kangcheng Lin Cynthia Rudin Yaron Shaposhnik Sijia Wang and Tong Wang. 2018. An Interpretable Model with Globally Consistent Explanations for Credit Risk. arXiv:1811.12615.  Chaofan Chen Kangcheng Lin Cynthia Rudin Yaron Shaposhnik Sijia Wang and Tong Wang. 2018. An Interpretable Model with Globally Consistent Explanations for Credit Risk. arXiv:1811.12615."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 32nd International Conference on Neural Information Processing Systems","author":"Dhurandhar Amit","year":"2018","unstructured":"Amit Dhurandhar , Pin-Yu Chen , Ronny Luss , Chun-Chen Tu , Paishun Ting , Karthikeyan Shanmugam , and Payel Das . 2018 . Explanations Based on the Missing: Towards Contrastive Explanations with Pertinent Negatives . In Proceedings of the 32nd International Conference on Neural Information Processing Systems ( Montr\u00e9al, Canada) (NIPS'18). Curran Associates Inc., Red Hook, NY, USA, 590--601. Amit Dhurandhar, Pin-Yu Chen, Ronny Luss, Chun-Chen Tu, Paishun Ting, Karthikeyan Shanmugam, and Payel Das. 2018. Explanations Based on the Missing: Towards Contrastive Explanations with Pertinent Negatives. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (Montr\u00e9al, Canada) (NIPS'18). Curran Associates Inc., Red Hook, NY, USA, 590--601."},{"key":"e_1_2_1_5_1","unstructured":"Dheeru Dua and Casey Graf. 2017. UCI Machine Learning Repository. UC Irvine. http:\/\/archive.ics.uci.edu\/ml\/index.php  Dheeru Dua and Casey Graf. 2017. UCI Machine Learning Repository. UC Irvine. http:\/\/archive.ics.uci.edu\/ml\/index.php"},{"key":"e_1_2_1_6_1","unstructured":"FICO. 2019. Explainable machine learning challenge. FICO. https:\/\/community.fico.com\/s\/explainable-machine-learning-challenge  FICO. 2019. Explainable machine learning challenge. FICO. https:\/\/community.fico.com\/s\/explainable-machine-learning-challenge"},{"key":"e_1_2_1_7_1","unstructured":"Shalmali Joshi Oluwasanmi Koyejo Warut Vijitbenjaronk Been Kim and Joydeep Ghosh. 2019. Towards Realistic Individual Recourse and Actionable Explanations in Black-Box Decision Making Systems. arXiv:1907.09615 http:\/\/arxiv.org\/abs\/1907.09615  Shalmali Joshi Oluwasanmi Koyejo Warut Vijitbenjaronk Been Kim and Joydeep Ghosh. 2019. Towards Realistic Individual Recourse and Actionable Explanations in Black-Box Decision Making Systems. arXiv:1907.09615 http:\/\/arxiv.org\/abs\/1907.09615"},{"key":"e_1_2_1_8_1","unstructured":"Amir-Hossein Karimi Gilles Barthe Borja Balle and Isabel Valera. 2020. Model-agnostic counterfactual explanations for consequential decisions. In AISTATS. 895--905.  Amir-Hossein Karimi Gilles Barthe Borja Balle and Isabel Valera. 2020. Model-agnostic counterfactual explanations for consequential decisions. In AISTATS. 895--905."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3001460.3001502"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939874"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91473-2_9"},{"key":"e_1_2_1_12_1","unstructured":"Ana Lucic Harrie Oosterhuis Hinda Haned and M. de Rijke. 2019. Actionable Interpretability through Optimizable Counterfactual Explanations for Tree Ensembles.  Ana Lucic Harrie Oosterhuis Hinda Haned and M. de Rijke. 2019. Actionable Interpretability through Optimizable Counterfactual Explanations for Tree Ensembles."},{"key":"e_1_2_1_13_1","volume-title":"Lundberg and Su-In Lee","author":"Scott","year":"2017","unstructured":"Scott M. Lundberg and Su-In Lee . 2017 . A Unified Approach to Interpreting Model Predictions. In Advances in neural information processing systems (NIPS) . 4765--4774. Scott M. Lundberg and Su-In Lee. 2017. A Unified Approach to Interpreting Model Predictions. In Advances in neural information processing systems (NIPS). 4765--4774."},{"key":"e_1_2_1_14_1","unstructured":"Christoph Molnar. 2022. Interpretable Machine Learning (2 ed.). https:\/\/christophm.github.io\/interpretable-ml-book  Christoph Molnar. 2022. Interpretable Machine Learning (2 ed.). https:\/\/christophm.github.io\/interpretable-ml-book"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3351095.3372850"},{"key":"e_1_2_1_16_1","unstructured":"Martin Pawelczyk Sascha Bielawski Johannes van den Heuvel Tobias Richter and Gjergji Kasneci. 2021. Carla: a python library to benchmark algorithmic recourse and counterfactual explanation algorithms. arXiv:2108.00783.  Martin Pawelczyk Sascha Bielawski Johannes van den Heuvel Tobias Richter and Gjergji Kasneci. 2021. Carla: a python library to benchmark algorithmic recourse and counterfactual explanation algorithms. arXiv:2108.00783."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Martin Pawelczyk Klaus Broelemann and Gjergji Kasneci. 2020. Learning Model-Agnostic Counterfactual Explanations for Tabular Data.  Martin Pawelczyk Klaus Broelemann and Gjergji Kasneci. 2020. Learning Model-Agnostic Counterfactual Explanations for Tabular Data.","DOI":"10.1145\/3366423.3380087"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380087"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375627.3375850"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939778"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11491"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Cynthia Rudin and Yaron Shaposhnik. 2019. Globally-consistent rule-based summary-explanations for machine learning models: Application to credit-risk evaluation. SSRN. https:\/\/ssrn.com\/abstract=3395422  Cynthia Rudin and Yaron Shaposhnik. 2019. Globally-consistent rule-based summary-explanations for machine learning models: Application to credit-risk evaluation. SSRN. https:\/\/ssrn.com\/abstract=3395422","DOI":"10.2139\/ssrn.3395422"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461555"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098039"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3287560.3287566"},{"key":"e_1_2_1_26_1","first-page":"841","article-title":"Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR","volume":"31","author":"Wachter Sandra","year":"2017","unstructured":"Sandra Wachter , Brent D. Mittelstadt , and Chris Russell . 2017 . Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR . Harv. JL & Tech. 31 (2017), 841 . arXiv:1711.00399 http:\/\/arxiv.org\/abs\/1711.00399 Sandra Wachter, Brent D. Mittelstadt, and Chris Russell. 2017. Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR. Harv. JL & Tech. 31 (2017), 841. arXiv:1711.00399 http:\/\/arxiv.org\/abs\/1711.00399","journal-title":"Harv. JL & Tech."},{"key":"e_1_2_1_27_1","first-page":"1","article-title":"A Bayesian Framework for Learning Rule Sets for Interpretable Classification","volume":"18","author":"Wang Tong","year":"2017","unstructured":"Tong Wang , Cynthia Rudin , Finale Doshi-Velez , Yimin Liu , Erica Klampfl , and Perry MacNeille . 2017 . A Bayesian Framework for Learning Rule Sets for Interpretable Classification . J. Mach. Learn. Res. 18 , 1 (jan 2017), 2357--2393. Tong Wang, Cynthia Rudin, Finale Doshi-Velez, Yimin Liu, Erica Klampfl, and Perry MacNeille. 2017. A Bayesian Framework for Learning Rule Sets for Interpretable Classification. J. Mach. Learn. Res. 18, 1 (jan 2017), 2357--2393.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2007.12.020"},{"key":"e_1_2_1_29_1","unstructured":"Yelp. 2017. Yelp Dataset Challenge. Yelp. https:\/\/www.yelp.com\/dataset\/challenge\/  Yelp. 2017. Yelp Dataset Challenge. Yelp. https:\/\/www.yelp.com\/dataset\/challenge\/"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3570690.3570693","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,23]],"date-time":"2023-01-23T17:37:03Z","timestamp":1674495423000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3570690.3570693"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["10.14778\/3570690.3570693"],"URL":"https:\/\/doi.org\/10.14778\/3570690.3570693","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,11]]},"assertion":[{"value":"2023-01-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}