随机森林决策可被形式化解释:编译成电路后,完整理由与最短翻转都能线性时间算出
核心概要
随机森林的多数投票决策现在可以编译成电路形式的类公式,再转成可处理的决策图,从而在决策图规模线性时间内算出完整理由与一般理由。此前把随机森林转成符号编码再交给 SAT 或 MAX-SAT 求解器,编码含大量辅助变量,不对应类公式,无法直接得到完整理由。在 UCI 与 Penn 机器学习基准的数据集上,编译出的 NNF 电路在多数数据集上小于已有 ADD 与 ORD 决策图,最大一次编译耗时 323.9 秒。
深度剖析
随机森林分类器可以被编译成一组电路,每个电路直接编码落在某一类中的实例,这为后续计算形式化解释提供了可操作的类公式。 此前把随机森林转成符号编码再查询 SAT 或 MAX-SAT 求解器的做法通常只针对单个解释,编码含大量辅助变量,不对应类公式,因而不能直接用来计算完整理由和一般理由。 在 UCI 与 Penn 机器学习基准的数据集上,生成的 NNF 电路在四个简单数据集上大于 ADD,其中三个是二分类数据集,而在其余所有数据集上都远小于 ADD,因而也小于 ORD 决策图;编译任一被考察分类器最多耗时 7.11 秒。
把类公式进一步表示成满足弱单次测试性质的决策图后,一次决策的完整理由和一般理由可以在决策图规模线性时间内算出。 已有把随机森林编译成决策图的方法可以从中提取电路形式的类公式,但提取出的电路不可处理,无法像这样在线性时间内计算完整理由和一般理由。 在相同特征数、类别数、测试实例数和最大深度的设置下,对每个数据集最多解释 100 个测试实例,19 个数据集中有 12 个能编译至少 50 棵树的分类器。
有了完整理由和一般理由,就能枚举一次决策的全部充分理由、必要理由和对比解释,并计算决策的鲁棒性以及所有最短翻转方式。 必要理由只保证至少存在一种违反会翻转决策,并不保证所有违反都会翻转,一般必要理由补上了这一更强的保证。 在所有测试数据集上平均鲁棒性很低,决策平均只需改动不到两个特征即可翻转;19 个数据集中有 17 个的每个决策最短一般必要理由少于 10 个。
启示与展望
演示范围是 UCI 机器学习库与 Penn 机器学习基准中的数据集,随机森林由 WEKA 学习,85% 实例作训练、15% 作测试,每个数据集最多解释 100 个测试实例;编译与解释枚举均在单机 Python 实现上完成。
多类随机森林中实例可能同时属于多个类,测试中发现这类实例比例低于 1%,处理时按得票最多且排名最高的类归属;把类公式转成可处理决策图的合取与析取算法目前没有有用的复杂度上界,只能靠实测评估。
