Optimal counterfactual explanations for random forests with MaxSAT

Thumbnail Image

Files

master_Raevskaya_Alesya_2025.pdf (415.79 KB)

URL

Journal Title

Journal ISSN

Volume Title

School of Science | Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2025-04-28

Department

Major/Subject

Computer Science

Mcode

Degree programme

Master's Programme in Computer, Communication and Information Sciences

Language

en

Pages

54

Series

Abstract

Machine learning approaches are predictive models based on historical data that are widely used in high-stakes areas. However, their inherent opacity led to concerns about fairness and accountability, which highlighted the need for explainability. In this work, we focus on finding optimal counterfactual explanations which answer the question "What is the easiest way to change a non-favourable decision?". In particular, we target Random Forests, commonly used well-performing classifiers. Our algorithm is guaranteed to provide a valid, feasible, and optimal explanation for every sample by formulating the problem as the maximum satisfiability (MaxSAT) task. The optimality of the explanation saves users from making unnecessary and costly changes. We achieve this by providing a Boolean encoding of features, a Random Forest structure, and a highly customisable distance function to accurately represent the needs of the user. Through experimental evaluation, we have shown that our algorithm outperforms existing approaches in most cases, showing the best performance on predominantly categorical datasets.

Description

Supervisor

Rintanen, Jussi

Thesis advisor

Lehtonen, Tuomo

Keywords

machine learning, satisfiability (SAT), random forests, explainable AI, maximal satisfiability (MaxSAT), explainability

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202505203879

Collections

[dipl] Perustieteiden korkeakoulu / SCI