Explainable Artificial Intelligence Using Expressive Boolean Formulas
We propose and implement an interpretable machine learning classification model for Explainable AI (XAI) based on expressive Boolean formulas. Potential applications include credit scoring and diagnosis of medical conditions. The Boolean formula defines a rule with tunable complexity (or interpretab...
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-11-01
|
| Series: | Machine Learning and Knowledge Extraction |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2504-4990/5/4/86 |
| _version_ | 1797380237335461888 |
|---|---|
| author | Gili Rosenberg John Kyle Brubaker Martin J. A. Schuetz Grant Salton Zhihuai Zhu Elton Yechao Zhu Serdar Kadıoğlu Sima E. Borujeni Helmut G. Katzgraber |
| author_facet | Gili Rosenberg John Kyle Brubaker Martin J. A. Schuetz Grant Salton Zhihuai Zhu Elton Yechao Zhu Serdar Kadıoğlu Sima E. Borujeni Helmut G. Katzgraber |
| author_sort | Gili Rosenberg |
| collection | DOAJ |
| description | We propose and implement an interpretable machine learning classification model for Explainable AI (XAI) based on expressive Boolean formulas. Potential applications include credit scoring and diagnosis of medical conditions. The Boolean formula defines a rule with tunable complexity (or interpretability) according to which input data are classified. Such a formula can include any operator that can be applied to one or more Boolean variables, thus providing higher expressivity compared to more rigid rule- and tree-based approaches. The classifier is trained using native local optimization techniques, efficiently searching the space of feasible formulas. Shallow rules can be determined by fast Integer Linear Programming (ILP) or Quadratic Unconstrained Binary Optimization (QUBO) solvers, potentially powered by special-purpose hardware or quantum devices. We combine the expressivity and efficiency of the native local optimizer with the fast operation of these devices by executing non-local moves that optimize over the subtrees of the full Boolean formula. We provide extensive numerical benchmarking results featuring several baselines on well-known public datasets. Based on the results, we find that the native local rule classifier is generally competitive with the other classifiers. The addition of non-local moves achieves similar results with fewer iterations. Therefore, using specialized or quantum hardware could lead to a significant speedup through the rapid proposal of non-local moves. |
| first_indexed | 2024-03-08T20:34:28Z |
| format | Article |
| id | doaj.art-0669b6bf00d5475b9e1ccf90ed56b4cf |
| institution | Directory Open Access Journal |
| issn | 2504-4990 |
| language | English |
| last_indexed | 2024-03-08T20:34:28Z |
| publishDate | 2023-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Machine Learning and Knowledge Extraction |
| spelling | doaj.art-0669b6bf00d5475b9e1ccf90ed56b4cf2023-12-22T14:22:12ZengMDPI AGMachine Learning and Knowledge Extraction2504-49902023-11-01541760179510.3390/make5040086Explainable Artificial Intelligence Using Expressive Boolean FormulasGili Rosenberg0John Kyle Brubaker1Martin J. A. Schuetz2Grant Salton3Zhihuai Zhu4Elton Yechao Zhu5Serdar Kadıoğlu6Sima E. Borujeni7Helmut G. Katzgraber8Amazon Quantum Solutions Lab, Seattle, WA 98170, USAAmazon Quantum Solutions Lab, Seattle, WA 98170, USAAmazon Quantum Solutions Lab, Seattle, WA 98170, USAAmazon Quantum Solutions Lab, Seattle, WA 98170, USAAmazon Quantum Solutions Lab, Seattle, WA 98170, USAFidelity Center for Applied Technology, FMR LLC, Boston, MA 02210, USAAI Center of Excellence, FMR LLC, Boston, MA 02210, USAFidelity Center for Applied Technology, FMR LLC, Boston, MA 02210, USAAmazon Quantum Solutions Lab, Seattle, WA 98170, USAWe propose and implement an interpretable machine learning classification model for Explainable AI (XAI) based on expressive Boolean formulas. Potential applications include credit scoring and diagnosis of medical conditions. The Boolean formula defines a rule with tunable complexity (or interpretability) according to which input data are classified. Such a formula can include any operator that can be applied to one or more Boolean variables, thus providing higher expressivity compared to more rigid rule- and tree-based approaches. The classifier is trained using native local optimization techniques, efficiently searching the space of feasible formulas. Shallow rules can be determined by fast Integer Linear Programming (ILP) or Quadratic Unconstrained Binary Optimization (QUBO) solvers, potentially powered by special-purpose hardware or quantum devices. We combine the expressivity and efficiency of the native local optimizer with the fast operation of these devices by executing non-local moves that optimize over the subtrees of the full Boolean formula. We provide extensive numerical benchmarking results featuring several baselines on well-known public datasets. Based on the results, we find that the native local rule classifier is generally competitive with the other classifiers. The addition of non-local moves achieves similar results with fewer iterations. Therefore, using specialized or quantum hardware could lead to a significant speedup through the rapid proposal of non-local moves.https://www.mdpi.com/2504-4990/5/4/86explainable AIinterpretable MLBoolean formulasstochastic local searchlarge neighborhood searchquantum computing |
| spellingShingle | Gili Rosenberg John Kyle Brubaker Martin J. A. Schuetz Grant Salton Zhihuai Zhu Elton Yechao Zhu Serdar Kadıoğlu Sima E. Borujeni Helmut G. Katzgraber Explainable Artificial Intelligence Using Expressive Boolean Formulas Machine Learning and Knowledge Extraction explainable AI interpretable ML Boolean formulas stochastic local search large neighborhood search quantum computing |
| title | Explainable Artificial Intelligence Using Expressive Boolean Formulas |
| title_full | Explainable Artificial Intelligence Using Expressive Boolean Formulas |
| title_fullStr | Explainable Artificial Intelligence Using Expressive Boolean Formulas |
| title_full_unstemmed | Explainable Artificial Intelligence Using Expressive Boolean Formulas |
| title_short | Explainable Artificial Intelligence Using Expressive Boolean Formulas |
| title_sort | explainable artificial intelligence using expressive boolean formulas |
| topic | explainable AI interpretable ML Boolean formulas stochastic local search large neighborhood search quantum computing |
| url | https://www.mdpi.com/2504-4990/5/4/86 |
| work_keys_str_mv | AT gilirosenberg explainableartificialintelligenceusingexpressivebooleanformulas AT johnkylebrubaker explainableartificialintelligenceusingexpressivebooleanformulas AT martinjaschuetz explainableartificialintelligenceusingexpressivebooleanformulas AT grantsalton explainableartificialintelligenceusingexpressivebooleanformulas AT zhihuaizhu explainableartificialintelligenceusingexpressivebooleanformulas AT eltonyechaozhu explainableartificialintelligenceusingexpressivebooleanformulas AT serdarkadıoglu explainableartificialintelligenceusingexpressivebooleanformulas AT simaeborujeni explainableartificialintelligenceusingexpressivebooleanformulas AT helmutgkatzgraber explainableartificialintelligenceusingexpressivebooleanformulas |