学习高覆盖判别性简约规则集

# 学习高覆盖判别性简约规则集
来源：https://arxiv.org/html/2606.14156
11institutetext:印度科学理工学院，CV Raman路，班加罗尔，卡纳塔克邦56001222institutetext:Compass，班加罗尔，卡纳塔克邦560012###### 摘要

基于IF-THEN规则表示的学习系统易于提供可解释性，使其成为当代人工智能研究的关键焦点。这类规则集的一个关键目标是同时实现高判别力和可解释性。虽然现有的最先进算法隐式地优先考虑预测准确性，但它们在确保可解释性的一个或多个质量指标（如覆盖率和规则集的简约性）上常常表现不足。受此启发，本文提出开发CDPR，旨在为分类问题创建高准确性和高可解释性的规则集。据我们所知，这是首次尝试建立这样的方法。在本研究中，我们引入了两种基于子模最大化的算法，这些算法不仅提供可证明的覆盖率保证，而且生成的规则集既具有判别性又简约。我们通过实验证明，通过我们的方法学习的规则集在准确性和可解释性方面表现更优，并且与次优算法相比，平均覆盖率提高了2.5倍以上。

## 1 引言

当前，在医疗[18]、刑事司法[17]、金融[23]等关键领域，对可解释模型的需求日益增长。这一需求因欧洲议会批准的GDPR法律中规定的“解释权”而进一步加剧。该立法赋予个人获得模型自动推理解释的权利，并允许他们质疑和挑战相关建议，尤其是当这些模型决策对个人生活产生重大影响时[29,10]。以可解释性著称的基于规则的模型，使从业者和专家能够检查模型背后的逻辑，并验证或改进模型。虽然事后方法可以为黑箱模型提供解释，但它们并不总能保证这些模型解释的忠实性。

IF thalassemia = normal AND number of major vessels (0-3) colored by fluoroscopy = 0 AND resting blood pressure < 127 THEN No Heart Disease
IF chest pain type = asymptomatic AND age > 41 AND maximum heart rate achieved <= 159 THEN Heart Disease
...

图1：由心脏病数据集[6]中的属性组成的规则集，用于诊断心脏病
本文专注于开发规则集¹¹¹也称为DNF或AND-of-ORs[16,5,31,36,34,24,12]作为分类的可解释模型。规则集由独立的IF-THEN规则集合组成，如果样本满足规则的条件-值对，则将其分配给特定的类别标签。一项在多个数据集上进行的全面对比研究表明，虽然现有算法学习的规则集保持了高精度，但它们往往无法满足可解释性的期望标准。早期的基于顺序覆盖和关联分类的规则集算法存在规则数量过多的问题，这对可解释性产生了负面影响[16]。然而，最近用于学习规则集的算法面临不同的挑战：即使预测能力很高，覆盖率也很低。这个挑战被称为*高精度-低覆盖率问题*。

低覆盖率的规则集仅代表输入空间的一小部分。在大多数情况下，它无法基于从业者或专家验证的规则为个人提供决策。相反，决策是使用默认规则做出的，其逻辑对个人来说是未知的。因此，模型的决策缺乏透明度，并且无法提供解释，而这正是可解释模型所期望的。这一限制阻碍了规则集在透明度和忠实性至关重要的关键应用中的采用。虽然规则集准确性的重要性在文献中已广泛讨论，但据我们所知，开发覆盖整个输入空间的规则集的重要性尚未得到充分解决。

本文主要旨在解决现有算法的局限性，并生成*高质量*的规则，通过准确性和可解释性指标（如精度、覆盖率和简约性）来衡量。本文引入了学习高覆盖判别性简约规则集（CDPR）的问题，旨在学习满足特定质量指标的规则集。虽然子模方法已应用于各种问题，但在规则学习中很少使用。学习CDPR的问题可以表述为具有多个约束的子模最大化问题，其中一些约束是子模的。本文提出了一种新颖的图规则算法（GRA）来解决子模优化问题。此外，本文还引入了CDPR的一个变体，称为CDPRL-MO，并提出了一种贪心算法（GDY）来解决CDPRL-MO。

与该问题相关的主要贡献总结如下。

1. 现有的学习规则集的算法通常不会生成*高质量*的规则（通过准确性和可解释性指标如覆盖率、精度和简约性来衡量，如表4（在第6.2节）中所总结）。覆盖率受到最严重的影响（通常覆盖率低至不到10%），而精度却非常高，这导致了我们称之为*高精度-低覆盖率问题*。受此问题启发，我们引入了学习CDPR的问题。这是一个新问题，似乎尚未被研究。
2. 本文的主要贡献是引入了一种新颖的图规则算法（GRA）。GRA被证明具有\(1−(1−\frac{(1−\beta)}{\gamma(1+d\beta)})^\gamma\)的近似保证（定理5.1），其中\(\beta\)和\(\gamma\)分别是规则集中重叠率的最大阈值和规则数量，而\(d\)是添加到规则集中的规则的最小入度。用\(B_{\alpha,\delta}\)表示精度大于\(\alpha\)且宽度小于\(\delta\)的规则集，GRA的运行时间与\(|B_{\alpha,\delta}|\)成二次关系。
3. 为了开发运行时间更短的算法，我们引入了CDPR的一个松弛变体，名为CDPRL-MO，这是一个在大型集合\(B_{\alpha,\delta}\)上的子模问题。该问题可以使用贪心算法（GDY）近似到恒定因子（定理5.2）。GDY的运行时间几乎与\(|B_{\alpha,\delta}|\)成线性关系。
4. 使用十个公开可用的数据集进行了全面的实验。实验结果表明，与次优算法IDS相比，GRA和GDY的平均覆盖率提高了2.5倍以上。因此，GRA和GDY在实现比最先进基线更好的覆盖率的同时，在判别力和可解释性方面也保持竞争力。

## 2 相关工作

基于规则的模型多年来在各个领域得到广泛研究， notable works include by [30,2,8,14,27,13,28]。在顺序覆盖技术（如RIPPER [4]和CN2 [3]）中，每个阶段从未覆盖的样本中使用启发式方法生成规则，然后移除新覆盖的样本。在关联分类技术[21,20,35]中，首先通过关联规则挖掘生成大量规则。然后，根据特定的兴趣度指标对规则进行排序，随后进行启发式修剪以消除冗余规则，从而构建规则集。然而，这些技术普遍存在规则集中规则数量过多的问题，这会对可解释性产生不利影响。

最初用于学习可解释规则集的算法主要强调具有较低模型复杂度的规则集，通过较少的条件来衡量以提高可解释性。例如，Bayesian Rule Sets (BRS)（由[31]提出）提供了一种概率方法，通过模拟退火过程从预挖掘的规则集中学习规则集。或者，在另一种方法中，学习规则集的问题被框架化为群组测试问题，如[22]所述。该问题可以使用源自压缩感知领域的线性规划（LP）松弛技术有效解决。

许多近期的工作将可解释性定义为具有较小的规则规模或较少的规则。例如，LIBRE [24]使用布尔函数合成从数据中学习规则。另一种方法 DefragTrees（由[12]提出）利用概率模型表示来合并输入空间中的相邻区域，从而减少区域的总体数量。然而，DefragTrees的一个显著限制是合并不同区域以创建更少规则的过程通常会导致更复杂的规则，难以解释。相比之下，[5,36]中讨论的线性规划算法通过整数规划生成规则集，无需对规则进行预挖掘。然而，基于LP的方法在处理大型数据集时面临计算不可行性的挑战，通常仅适用于具有二值化特征值和二值化标签的数据集。

DRS [12] 将可解释性定义为具有最小重叠的简约规则集的存在。与我们的方法类似，DRS也专注于学习高质量规则。DRS在每次迭代中使用规则发现过程，仅从未覆盖的记录池中采样候选规则，类似于顺序覆盖方法。值得注意的是，DRS假设所有特征和类别标签都是二元的。相比之下，IDS（由[16]提出）优化一个全局目标，从预挖掘的规则集中学习规则集。他们的方法在构建规则集时寻求准确性和可解释性之间的平衡。

## 3 关于最先进规则学习算法生成规则质量的比较研究

为了理解当前最先进算法生成的规则质量，我们进行了一项实验研究。在本节中，我们展示了研究结果。

### 3.1 正式设置与定义

考虑一个数据集 \(D = \{(X_i, y_i) | i \in 1, \dots, N\}\)，包含 \(N\) 个样本，其中 \(X_i\) 和 \(y_i\) 分别表示数据实例 \(i\) 的输入特征和类别标签。令 \(A\) 为规则的全体集合，其中每个规则 \(r \in A\) 是一个对 \((s, c)\)，\(s\) 是条件-值对的合取，\(c\) 表示类别标签。在我们的调查中，我们从决策树集成（第6.1节）中获得 \(A\)。我们回顾以下标准定义[16]。

*   **覆盖率**。规则 \(r = (s, c)\) 的覆盖（cover）是数据集中满足 \(s\) 中条件-值对的点集。规则集 \(S\) 的覆盖率是 \(f(S) = coverage(S) = |\bigcup_{r \in S} cover(r)|\)。
*   **规则规模**。规则规模（Rule-size）是 \(S\) 中规则 \(r \in S\) 的数量。
*   **规则宽度**。规则宽度（Rule-width）表示规则中条件-值对的数量。例如，规则 \(r\) = IF (cond1 ≤ value1) AND (cond2 ≤ value2) THEN label1 具有 \(rule-width(r) = 2\)。
*   **重叠率**。两个规则 \(r_i, r_j\) 之间的重叠（Overlap）定义为 \(r_i = (s_i, c_i)\) 且 \(r_j = (s_j, c_j)\) 时，其属性同时满足 \(s_i\) 和 \(s_j\) 的数据点数量。\(overlap(r_i, r_j) = |cover(r_i) \bigcap cover(r_j)|\)。\(overlap-rate(r_i, r_j) = \frac{overlap(r_i, r_j)}{|cover(r_i)|}\)。
*   **精度**。规则 \(r = (s, c)\) 的正确覆盖（correct-cover）是数据集中同时满足 \(s\) 和 \(c\) 的点集。规则 \(r = (s, c)\) 的错误覆盖（incorrect-cover）是数据集中满足 \(s\) 但不满足 \(c\) 的点集。规则的精度定义为 \(accuracy(r) = \frac{|correct-cover(r)|}{|cover(r)|}\)。

以下指标用于衡量规则集的质量：

*   **规则集精度 (RSA)**。RSA 是整个规则集的精度。它表示规则集正确分类的测试数据集中样本的比例。
*   **覆盖率 (Coverage-rate)**。该指标衡量规则集中所有规则相对于总数据点数的覆盖率。\(coverage-rate(S) = \frac{|\cup_{r \in S} cover(r)|}{N}\)。我们希望覆盖率尽可能大。
*   **最大规则宽度**。这指的是规则集中所有规则的最大宽度。\(Max.width(S) = \max_{r \in S} width(r)\)。该指标值较小表示规则集中的规则更有意义。

### 3.2 现有基准算法的比较

我们进行了全面的实验，使用来自UCI机器学习库[6]的十个真实世界数据集以及来自NACC统一数据集[33,1,32]的... (翻译继续)