文章名称

【Arxiv-2021】【University of Technology Sydney】Prototype-based Counterfactual Explanation for Causal Classification

核心要点

文章旨在解决现有（针对离散特征的）反事实解释方法存在的，1）丢失特征间因果关系，导致反事实样本不合理；2）生成反事实样本速度慢，需调节大量参数，融合多种损失两方面问题，提出了利用因果结构模型来保留反事实特征背后的因果关系，同时设计了一种基于多目标遗传算法的新型无梯度优化算法为连续和分类数据的混合类型生成反事实解释。

问题引入

反事实解释是可解释机器学习的一个分支，通过产生扰动样本使得模型改变原来决策，以扰动样本作为对模型决策依据的解释。现有的反事实解释方法大多是基于梯度的方法，只能优化连续变量。虽然有许多方法被提出，来对分类变量进行反事实解释的生成，但存在两点不足

• 在生成反事实时通常会忽略特征之间的因果关系，导致得到的反事实解释是不合理的（比如提升学历，但年龄不变），不能帮助决策者采取行动[Ustun et al., 2019, Poyiadzi et al., 2020]。
• 生成反事实样本的速度非常慢，需要调节大量参数，并且要组合多种损失函数[Mahajan et al., 2019, Mothilal et al., 2020]。

具体做法

为了解决上述问题，作者提出了ProCE方法，其特点包括，

• 该方法是一种与模型无关的方法，能够对混合特征空间中的分类决策给出解释。
• 该方法结合因果结果模型和因果损失函数，可以在生成反事实样本时保持特征间因果约束。
• 利用自动编码器模型，结合所谓的“类原型”来指导反事实样本生成的搜索过程，并加快搜索速度。
• ProCE利用多目标优化平衡生成的反事实样本的最优性和合理性。

首先，对一些后续用到的变量进行一下形式化定义，

• 决策模型h: mathcal{X } rightarrow mathcal{Y }，mathcal{X } subseteq R^D， mathcal{Y } in { 0, 1 }分别表示特征和标签空间，x in mathcal{X }表示某一个具体样本的特征。
• 为了区别观测事实和反事实，把观测样本特征和标签记作x_0, y_0。
• 反事实样本生成的目的是，基于x_0, y_0，生成反事实样本x_{cf}, 使得样本的预测结果y_{cf}变为目标标签。该生成过程一般通过解决如下图所示的优化问题得到。其中，f表示 x_0和 x_{cf}之间的距离度量函数。一般为了产生合理的反事实解释，要求反事实样本与原始样本在特征空间中的距离要小。

❞

Prototype-based Causal Model

ProCE在反事实样本，要求模型遵循一些约束来，以此保证样本取值的合理性，加速反事实样本生成速度。包括，

• 目标标签约束。分类器对发说说样本的预测距离和期望反事实结果要一致。在分类任务中，可以利用cross-entropy来度量这个差异，其损失如下图所示。

• 原型约束。巨大的搜索空间，导致反事实样本生成运算过程很慢。作者受到[Van Looveren and Klaise, 2019]启发，利用“类原型”的概念指导模型在特征空间中搜索，并得到合理的反事实样本。具体做法是一个意向量空间中寻找x_0的KNN，并以这些KNN的算数中心（各节点的平均）。可以通过投影函数Q_phi: mathcal{X } rightarrow mathcal{Z }把原始样本特征x_0投影到原型空间。在原型空间中利用欧式距离，找到KNN，最终某一个类型i的原型proto_i的定义如下图所示。

基于此，原型损失定义如下图所示。

其中，类别j是在原型空间中，距离原始样本x_0最近的类原型的标号，其公式如下图所示。

• 相近约束。反事实样本应尽可能接近原始观测样本，以便用户理解（跨度太大的样本之间很难做对比）。然而，样本同时具有离散和连续特征时，很难构造有效的损失函数进行反事实样本生成，并度量相近性。一般会利用指示变量表明反事实样本和观测样本的某个离散特征是否一致[Sharma et al., 2020]。但是这种标识符不能够反映距离的远近，无法优化。作者利用原型约束中的嵌入函数，把离散特征变成稠密向量来度量距离的远近，具体公式表示如下图所示。

值得注意的是，采用嵌入函数的好处是能够捕获每个分类值之间的潜在关系，不需要通过特征工程为每个类别分配权重。

• 因果关系保留约束。上述约束都不能保持特征之间的因果关系。因此，作者基于结构因果模型（SEM）[Pearl, 2009]，构建了因果损失函数来保持生成样本中特征的因果关系。作者假设「可以得到与反事实生成业务相关的因果结构模型」。对于每一个内生变量v（v是因果图的节点，表示某一个特征），其值由因果结构方程v = {g}({v}^{}_{p1}, {v}^{}_{p2}, ldots, {v}^{}_{pk})确定。其中，({v}^{}_{p1}, {v}^{}_{p2}, ldots, {v}^{}_{pk})表示v的所有父节点。回到反事实生成场景，特征{x}^{v}_{}的proximity Loss的计算公式如下图所示。

因此，所有特征的causality-preserving loss如下图所示。其中，U, u分别表示所有外生节点和单个外生节点（特征）。

❞

最终，作者将所有损失汇集在一起形成如下图所示的多目标，并直接采用改进的NSGA-II[Deb et al., 2000]求解，而绕开了费时费力的目标权重调节（时间花在了求解运算上）。

作者改进的NSGA-II的具体细节参见代码实现部分的伪代码。作者首先找到与原始实例x_0最接近的类原型，用来计算后续的原型损失。随后，通过高斯分布初始化一个随机的候选种群，为每个候选解计算上述损失，f_{pred},f_{proto}, f_{final_dist}。再按照非支配解[Deb et al., 2002]排序方法，为每一个候选解分配Pareto Front[Ngatchou et al., 2005]。从分配后的候选集中选择候选解。重复该过程，直到所有解决方案都分配到一个Pareto Front（具体细节和定义可以参考原文）。

到此为止，我们得到一个候选解种群。对每一个候选解计算crowding distance [Raquel and Naval Jr, 2005]「来保证多样性」。只有排名靠前的一半候选解被保留并进行cross-over和mutation操作。最终，最优的反事实样本被作为最终解返回。

代码实现

文章的伪代码如下图所示。

心得体会

反事实约束

作者的优化思路是先把反事实样本需要遵循的约束（或者说目标）罗列清楚，通过优化这些目标，得到期望的反事实样本。其中，prototype，相当于给反事实样本生成打锚点，让反事实样本生成逐渐找到方向，而不是不知道该往哪走（因为有可以瞄准任何一个具有目标标签的样本去搜索或者改变特征值）。

也许在原型选取，也就是KNN中K的设置过程上，优先使用大的K，最终逐渐缩小K，类似引路的感觉。

特征因果关系保留

作者计算proximity loss的时候引入SEM来强调因果性，是该方法的一大亮点，不过也需要更多的领域知识，并且应该是需要全部的因果图。在因果可解释综述中介绍过，假设全部因果图已知是不太现实的。因此，该方法可能比较难实际应用。

反事实生成与多样性

作者采用crowding distance保证多样性，其实是利用了样本点的密度，高密度的点更容易被生成出来，因此低密度的则更可能是多样的。有一个地方可以稍作调整，来保证其他特性，例如哪些特征不能变化，特征的取值范围再什么范围内等。

文章引用

[Ustun et al., 2019] Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Proceedings of the Conference on Fairness, Accountabil- ity, and Transparency, pages 10–19, 2019.

[Poyiadzi et al., 2020] Rafael Poyiadzi, Kacper Sokol, Raul Santos-Rodriguez, Tijl De Bie, and Peter Flach. Face: fea- sible and actionable counterfactual explanations. In Pro- ceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pages 344–350, 2020.

[Mahajan et al., 2019] Divyat Mahajan, Chenhao Tan, and Amit Sharma. Preserving causal constraints in counterfactual explanations for machine learning classifiers. arXiv preprint arXiv:1912.03277, 2019.

[Mothilal et al., 2020] Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pages 607–617, 2020.

[Van Looveren and Klaise, 2019] Arnaud Van Looveren and Janis Klaise. Interpretable counterfactual explanations guided by prototypes. arXiv preprint arXiv:1907.02584, 2019.

[Sharma et al., 2020] Shubham Sharma, Jette Henderson, and Joydeep Ghosh. Certifai: A common framework to provide explanations and analyse the fairness and ro- bustness of black-box models. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pages 166–172, 2020.

[Pearl, 2009] Judea Pearl. Causal inference in statistics: An overview. Statistics Surveys, 3:96–146, 01 2009.

[Deb et al., 2000] Kalyanmoy Deb, Samir Agrawal, Am- rit Pratap, and Tanaka Meyarivan. A fast elitist non- dominated sorting genetic algorithm for multi-objective optimization: Nsga-ii. In International conference on parallel problem solving from nature, pages 849–858. Springer, 2000.

[Deb et al., 2002] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. A fast and elitist mul- tiobjective genetic algorithm: Nsga-ii. IEEE transactions on evolutionary computation, 6(2):182–197, 2002.

[Ngatchou et al., 2005] Patrick Ngatchou, Anahita Zarei, and A El-Sharkawi. Pareto multi objective optimization. In Proceedings of the 13th International Conference on, Intelligent Systems Application to Power Systems, pages 84–91. IEEE, 2005.

[Raquel and Naval Jr, 2005] Carlo R Raquel and Prospero C Naval Jr. An effective use of crowding distance in mul- tiobjective particle swarm optimization. In Proceedings of the 7th annual conference on Genetic and evolutionary computation, pages 257–264, 2005.