本文是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)。下图展示了我们的解释框架是如何进行的：从这个例子出发，一般来说，我们的解释思路如下：将输入给分解成若干子输入。
对于每个子输入，使用其于对称性和有效性的公理来得到相应的胜者。例如对于 (a, b, c); (b, a, c)，由于在这个输入中 a, b 的位置是对称的，且严格优于 c，因此可以得到这个子输入的胜者应该是 {a, b}。
最后将所有子输入的胜者给合并起来，这里合并的途径是利用相容性公理。例如对于 (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 不能在步数内被解释，结合上界，我们得到了 Borda 在7个公理下的解释长度为。
Plurality 不能在步数内被解释。
Approval 不能在步数内被解释。
最后，值得一提的是我们下界不仅在最坏的情况下成立，它对于几乎所有的输入都成立。
总结从一方面来说，我们希望我们的工作能够帮助投票机制的设计者更好地解释相应的机制，从另一方面来说，我们希望有关解释长度的探索能够指导未来实践中的投票方法和公理的选择——谁都不想看到一个投票结果需要很长很长的步数才能被解释。我们的理论在不同的应用中也许会有不同的意义，例如在政治选举中，因为候选者的个数不多，所以一个的解释步数是完全可以接受的，相反，在 ensemble learning 和 virtual democracy 的例子中，候选方法可能非常非常多，因此一个 的解释可能是无法接受的。在这样的场景中，我们要下界就能帮助识别哪些是好的，可用的，哪些是不可用的投票与解释。“CCF-NLP走进高校”是由中国计算机学会自然语言处理专业委员会（CCF-NLP）发起，联合AI研习社及各个知名高校开展的一系列高校NLP研究分享活动。
“CCF-NLP走进高校”第四期将走进“新疆大学”，一起聆听新疆大学NLP的前沿研究分享。本次活动邀请的嘉宾有哈尔滨工业大学（深圳）教授徐睿峰、清华大学计算机系长聘副教授黄民烈、天津大学教授熊德意、复旦大学教授黄萱菁、新疆大学教授汪烈军、西湖大学特聘研究员张岳。敬请期待！
点击阅读原文，直达直播页面
