跳到主要内容
返回时间线

拒识也要说清理由:MINABRO 给带拒识选项的线性模型算出最小规模溯因解释

核心概要

带拒识选项的线性分类器在证据不足时会弃权,但此前缺少既能保证忠实、又能保证解释最小的算法。MINABRO 对已分类样本沿用贪心排序,在特征有界域上以 O(n log n) 时间得到最小规模溯因解释;对拒识样本则把它写成 0–1 整数线性规划求解。十个公开数据集上,它的运行时间低于采样式的 Anchors 和线性规划式的 AbLinRO,即使求解拒识这一 NP-hard 形式也更快。

AI-generated editorial illustration: Concisely Explaining the Doubt: Minimum-Size Abductive Explanations for Linear Models with a Reject Option

深度剖析

带拒识选项的线性分类器现在能对弃权样本给出可证明最小规模的溯因解释,而不只是给出某个不可再删的特征子集。 此前的逻辑解释方法只覆盖不含拒识的线性模型,或对含拒识的线性模型给出不保证最小规模的解释。 在十个来自 UCI 与 OpenML 的公开二分类数据集上,MINABRO 与 Anchors、AbLinRO 两种参照方法对比,MINABRO 与 AbLinRO 都保证对模型的忠实性,而只有 MINABRO 保证解释规模最小。

已分类样本的解释靠一次排序完成:每个特征按固定它能把最坏情况得分抬高多少来排序,依次加入直到越过拒识阈值。 不含拒识的线性模型已有对数线性时间的贪心算法,但那里的判据是标准决策边界 0,而不是正类拒识阈值。 该贪心过程先花 O(n) 计算各特征的增益,再排序花 O(n log n),最后扫描取最短可行前缀,整体复杂度为 O(n log n)。

拒识样本的解释被写成一个 0–1 整数线性规划:用二元变量表示某特征是否被固定,目标是最小化被固定特征数。 拒识要求得分同时落在下阈值之上和上阈值之下,因此需要同时约束最坏情况的最大得分与最小得分。 该形式在理论上属于 NP-hard,但实验中 MINABRO 在拒识样本上仍比需要逐特征多次调用线性规划求解器的 AbLinRO 更快。

启示与展望

演示范围限于带拒识选项的线性分类器,特征取值被缩放到 [0,1] 并视为有界域,实验使用逻辑回归和十个公开二分类数据集;作者把多分类、膨胀式溯因解释以及用带拒识的局部线性替代模型解释深度网络列为后续工作。

拒识样本的解释在多数数据集上平均大于已分类样本的解释,因为要同时满足得分上下两个约束;拒识形式在理论上仍是 NP-hard,实际效率来自实验观察而非复杂度保证。