北大、哈佛等NeurIPS新作：基于公理系统解释集成模型的决策过程

本文是NeurIPS 2020入选论文“Explainable Voting”的解读，该项研究由北京大学、普渡大学、哈佛大学联合完成。

论文地址：https://zixinzhou.com/pdf/explain.pdf

投票在许多的场景中都是非常重要的， 比如政治选举，聚合专家意见， 或者把多个机器学习模型整合到一起（即集成模型）等。 在之前的许多工作中，投票机制是自动决策系统中至关重要的一环， 因此一个可以解释的投票系统就毫无疑问是通向可解释AI的基础。

本文着重讨论了一个全新的投票机制解释模型，并给出了一套数学框架对其表现进行刻画。

具体来说，我们使用一些简单的公理来解释一个投票方法为什么对于一个给定的输入所产生的胜者会是某个候选人。以 Borda 这个性质非常好的投票方法为例，我们接下来要解释的投票输入有4个候选人，分别为 a, b, c, d。8个投票人，他们对这4个候选人的偏好分别是 (a, d, b, c); (b, a, c, d); (b, a, d, c); (b, d, c, a); (c, a, b, d); (c, a, d, b); (c, d, a, b); (d, a, c, b)。下图展示了我们的解释框架是如何进行的：

从这个例子出发，一般来说，我们的解释思路如下：

1. 将输入给分解成若干子输入。

2. 对于每个子输入，使用其于对称性和有效性的公理来得到相应的胜者。例如对于 (a, b, c); (b, a, c)，由于在这个输入中 a, b 的位置是对称的，且严格优于 c，因此可以得到这个子输入的胜者应该是 {a, b}。

3. 最后将所有子输入的胜者给合并起来，这里合并的途径是利用相容性公理。例如对于 (a, b, c) 和 (a, b, c); (b, a, c) 这两个子输入，由于前者的胜者是 {a}，后者的胜者是 {a, b}。我们可以得到 (a, b, c); (a, b, c); (b, a, c) 的胜者一定是 {a}（{a}和{a,b} 的交集）。

在这里提到的对称性、有效性公理和相容性公理是两个大类的公理。本文一大创新之处就是几类相似的公理给抽象出来。还是以 Borda 为例，我们使用了如下3个对称性、有效性公理：

和4个相容性公理：

共7个公理来解释 Borda。可以看到其中每个公理都是很符合直观的（否则也就不能称之为公理了）。当然能够解释一个投票机制的公理可能有非常多的选择，为了把相似的公理都刻画出来，本文创新地将投票方法和公理嵌入到线性空间中：

并提出了如下四个元公理（meta-axiom）：

之前提到的一些公理都是这4个元公理的特例。借助线性代数的工具，我们就可以描述一大类投票机制的公理解释了。

我们研究中遇到的一个挑战是： 仅仅知道这样的解释的存在性是远远不够的，在实际应用中，我们想 要的是越短越好的解释。 本文证明了，Borda 可以用之前提到的7个公理生成一个 长度的解释，其中 是候选人的个数。

我们知道了一些解释长度的上界之后，一个很自然的问题就是，这些解释的长度下界是什么样的。本文的主要结果是一个一般性的下界：如果一个投票方法能嵌入到 维空间，并且公理能被上述4个元公理所刻画，那么是不可能找到比 更短的解释的。 利用这个定理，我们得到了几个推论：

• Borda 不能在步数内被解释，结合上界，我们得到了 Borda 在7个公理下的解释长度为。                                             

• Plurality 不能在步数内被解释。

• Approval 不能在步数内被解释。

最后，值得一提的是我们下界不仅在最坏的情况下成立，它对于几乎所有的输入都成立。

总结

从一方面来说，我们希望我们的工作能够帮助投票机制的设计者更好地解释相应的机制，从另一方面来说，我们希望有关解释长度的探索能够指导未来实践中的投票方法和公理的选择—— 谁都不想看到一个投票结果需要很长很长的步数才能被解释。

我们的理论在不同的应用中也许会有不同的意义，例如在政治选举中，因为候选者的个数不多，所以一个 的解释步数是完全可以接受的，相反，在 ensemble learning 和 virtual d emocracy 的例子中，候选方法可能非常非常多，因此一个  的解释可能是无法接受的。 在这样的场景中，我们要下界就能帮助识别哪些是好的，可用的，哪些是不可用的投票与解释。

---

“CCF-NLP走进高校”是由中国计算机学会自然语言处理专业委员会（CCF-NLP）发起，联合AI研习社及各个知名高校开展的一系列高校NLP研究分享活动。

“CCF-NLP走进高校”第四期将走进“新疆大学”，一起聆听新疆大学NLP的前沿研究分享。本次活动邀请的嘉宾有哈尔滨工业大学（深圳）教授徐睿峰、清华大学计算机系长聘副教授黄民烈、天津大学教授熊德意、复旦大学教授黄萱菁、新疆大学教授汪烈军、西湖大学特聘研究员张岳。敬请期待！

点击阅读原文，直达直播页面