TL;DR
This paper introduces the first method for generating counterfactual explanations for concept descriptions in the Description Logic $\mathcal{ELH}$. By adapting counterfactual reasoning from tabular data to knowledge bases, they provide short, actionable explanations that tell users how to change their situation to achieve a different classification, and a user study validates their approach.
What Problem Does This Paper Address?
Knowledge bases (KBs) are increasingly used in critical applications like web search, medical diagnostics, and credit scoring. When AI systems make decisions based on these KBs, users affected by these decisions need to understand why a decision was made and verify its fairness. While Description Logics (DLs) offer transparent models for classification, the learned concepts can become extremely long and complex, making them difficult for non-experts to understand. Furthermore, these long concepts don't offer a clear path for action. Counterfactual explanations, which answer "What needs to change for a different outcome?", have shown promise for tabular data, but this approach hasn't been applied to the structured world of KBs and DLs. This paper bridges that gap by developing a method to generate counterfactual explanations for concept descriptions in the $\mathcal{ELH}$ DL.
Methods
The core of the paper is the development of an algorithm to generate counterfactual explanations (CEs) for individuals within an $\mathcal{ELH}$ knowledge base. The process involves:
- Generating Counterfactual Candidates: Given a KB, a concept $C$, and an individual $x$ for which $C(x)$ holds (or doesn't hold), the algorithm generates candidate KBs ($K'$) where the classification of $x$ with respect to $C$ is flipped. This is achieved by making minimal changes to the ABox (assertions about individuals) of the original KB.
- Minimizing Feature Changes: To ensure explanations are concise and actionable, the algorithm prioritizes candidates that require the fewest changes (edit distance) to the ABox. This aligns with the idea of "minimal feature changes" from tabular data CEs.
- Ranking by Likeliness: When multiple counterfactual candidates have the same minimal edit distance, the paper introduces two heuristic measures, $I_{min}$ and $I_{mean}$, to rank them based on the "likeliness" of the feature combinations. This aims to present the most plausible counterfactuals to the user.
- Algorithm for "Removal" Requests: Algorithm 1 is presented for generating counterfactuals when the goal is to remove a concept assertion (e.g., "how to not be classified as a mother"). This involves recursively identifying and removing assertions that contribute to the concept's entailment.
- Algorithm for "Addition" Requests: Algorithm 3 handles counterfactuals for adding a concept assertion (e.g., "how to be classified as a mother"). This is simpler and involves adding necessary assertions, potentially including fresh individuals.
Datasets
The evaluation of the proposed method utilized modified versions of two existing ontologies:
- Family Ontology: This ontology deals with familial relationships.
- Animals Ontology: This ontology describes animal species.
These ontologies were chosen for their familiarity and understandability to lay users. The ABoxes were materialized, and concepts were learned using the DL concept learner ELTL. No new benchmarks were introduced; rather, existing ontologies were adapted for the study.
Key Insights and Ideas
- Counterfactuals for Structured Data: The paper successfully extends the concept of counterfactual explanations, previously popular for tabular data, to the structured domain of Description Logics and knowledge bases. This opens up new avenues for explaining AI decisions in knowledge-intensive applications.
- Actionability through Minimal Changes: By focusing on minimal ABox modifications, the generated counterfactuals provide a direct and actionable path for users to understand how to alter their situation to achieve a different outcome.
- Likeliness as a Ranking Heuristic: The introduction of $I_{min}$ and $I_{mean}$ as likeliness measures addresses the challenge of multiple minimal counterfactuals, aiming to present the most plausible ones to users, which is crucial for practical explanation.
- User Preferences Matter: The user study highlights that users prefer explanations that refer to more specific or characteristic features (like familial roles) over very common ones (like gender), suggesting that "likeliness" in explanations should go beyond mere statistical frequency.
Key Results
- Successful Generation of CEs: The proposed algorithm successfully generates counterfactual candidates for $\mathcal{ELH}$ concept descriptions.
- User Preference for Algorithmic CEs: A user survey indicated that participants generally preferred the counterfactual explanations generated by the algorithm, especially when they referred to specific familial roles.
- Alignment with User Ratings: The study found a reasonable alignment between the algorithm's preferred counterfactuals (based on likeliness) and user ratings of explanation helpfulness, though room for improvement was noted. For the Family ontology, the algorithm's decisions aligned perfectly with user ratings (F1-Score of 1.0). For the Animals ontology, the F1-scores were 0.33 and 0.37 for the $I_{min}$ and $I_{mean}$ measures, respectively, indicating room for refinement.
Limitations and Future Work
- Limited DL Expressivity: The current approach is limited to the $\mathcal{ELH}$ Description Logic. Future work aims to extend the method to more expressive DLs like $\mathcal{ALC}$, which involves handling negation and disjunctions, posing significant challenges.
- Actionability Nuances: While the approach aims for actionability, the paper acknowledges that not all features can be changed in the real world (e.g., gender). Future work will focus more on ensuring the practical actionability of counterfactuals.
- Improving Likeliness Measures: The user study suggests that the current likeliness measures could be improved. Future work may involve developing "learning to rank" algorithms to automatically learn better likeliness functions.
- Ontology Structure Impact: The structure of ontologies can influence the effectiveness of likeliness measurements. Future research will explore how different ontology structures affect CE generation and evaluation.
- Chatbot Integration: A long-term goal is to integrate these counterfactual explanations into a chatbot that can provide natural language explanations of learned concepts for various applications.
Summary updated