Exact Power Indices for Plurality-Voting Ensembles¶

会议: NeurIPS 2026
arXiv: 2610.17980
代码: https://github.com/iliesarpe/enpower
领域: 学习理论
关键词: 相对多数投票集成、合作博弈论、Banzhaf 指数、Shapley 值、普通生成函数

一句话总结¶

针对带均匀随机平局决胜的相对多数投票（Plurality-Voting）集成模型归因难题，本文提出了合作博弈论新框架 enpower，通过组合对称性与普通生成函数，首次在二分类实现线性时间、多分类实现低阶多项式时间的 Banzhaf 与 Shapley 权力指数精确计算。

研究背景与动机¶

相对多数投票（Plurality Voting，即预测得票最多的类别，平局时均匀随机抽取）是机器学习中广泛采用的模型聚合机制。然而，评估集成中单个基分类器的实际贡献（Attribution）却异常困难。基分类器的影响力绝不仅取决于其单体预测准确率或留一法（Leave-One-Out）精度，而是深刻依赖于它与集成中其他所有模型的相互作用。例如，某个弱分类器的投票可能恰好在关键平局时打破僵局，或者在强分类器形成压倒性多数时沦为冗余。在由 $n$ 个基分类器构成的庞大空间中，简单的启发式评估仅考查了全集成或空集成这两个极端子集，彻底忽视了指数级子集成中复杂的协同与互补关系。

合作博弈论中的权力指数（Power Indices）——尤其是公理化体系完备的 Banzhaf 指数与 Shapley 值——是量化博弈参与者真实贡献的黄金标准。但将其应用于机器学习集成时面临双重瓶颈：计算复杂度通常随玩家数量 $n$ 呈指数级爆炸 $\mathcal{O}(2^n)$；现有可高效计算的多项式时间方法仅适用于加权多数博弈（Weighted Majority Games, WMG），该类博弈预先设定固定配额（Quota）且属于单调的简单博弈（Simple Games），完全无法表达具有随机平局打破（Random Tie-Breaking）的相对多数投票，更无法向多分类场景直接推广（传统多分类二值约简计算代价极高且割裂了类别间竞合交互）。

本文切入问题的核心视角在于：相对多数投票的特征函数虽然既非超模、非超加，也非单调（非简单博弈），但分类器投票天然存在深刻的置换对称性——预测相同类别的基模型具有完全等价的边际收益。通过将模型贡献精细解构为引入平局与打破平局两类事件，二分类可推导出优美的封闭解；在多分类下，则可通过单变量与双变量普通生成函数（Ordinary Generating Functions, OGF）对联盟组合进行紧凑编码与动态规划提取。核心 idea：建立融合随机平局决胜的相对多数投票特征函数博弈，利用同预测投票对称性推导二分类闭式解，并构造以 OGF 系数编码候选类别得票状态的动态规划，实现基分类器 Banzhaf 与 Shapley 值的精确多项式时间求解。

方法详解¶

整体框架¶

本文针对二分类与多分类场景分别形式化了带随机平局打破的点级特征函数博弈 $G_z = (\mathcal{C}, v)$。对于单一样本 $z=(x, y)$ 与基分类器集合 $\mathcal{C}$ 中的任意非空联盟 $S \subseteq \mathcal{C}$，定义有效得票向量 $\bm{p}(x, S) \in \mathbb{Z}^\ell$ 及得票最多的标签集合 $\mathcal{M}(x, S)$。在二分类下，$v_{\mathsf{B}}(z, S)$ 分别在正确类占优、平局与错误类占优时取值 $1$、$1/2$、$0$；在多分类下，$v_{\mathsf{MC}}(z, S)$ 在正确类 $y \in \mathcal{M}(S)$ 时取值为 $1/|\mathcal{M}(S)|$（平局平分收益），否则为 $0$。全数据集的博弈则是所有测试点博弈的算术平均值 $v(\mathcal{D}, S) = \frac{1}{|\mathcal{D}|}\sum_{z\in\mathcal{D}} v(z, S)$。

整个 enpower 算法管线首先利用单点计算与线性公理，将全集归因拆解至单点独立处理；随后在单点中利用唯一投票轮廓（Unique Vote Profiles $U$）建立缓存与去重，二分类直接执行封闭组合公式求值，多分类则通过构造代数生成函数的多项式乘法与动态规划矩阵递推提取组合系数，最终实现高效精确的权力指数汇总。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：集成分类器集合 𝒞 与测试数据集 𝒟"] --> B["相对多数投票博弈建模<br/>定义单点特征函数与随机平局决胜机制"]
    B --> C["同投票对称性与唯一轮廓缓存<br/>聚合等价投票模型并提取唯一配置集合 U"]
    C --> D["二分类封闭组合解法<br/>引入/打破平局两类边际增益封闭求和"]
    C --> E["多分类普通生成函数代数求解<br/>单变量/双变量 OGF 动态规划递推"]
    D --> F["全集线性聚合输出<br/>精确 Banzhaf / Shapley 权力指数向量"]
    E --> F

关键设计¶

1. 相对多数投票博弈建模：刻画平局随机打破的非简单博弈特征函数 传统 WMG 博弈要求严格达到全局过半配额 $q = \lfloor n/2 \rfloor + 1$，直接抹杀了小规模联盟内部的得票博弈，且非 0 即 1 的收益无法反映随机仲裁。本文构建的博弈函数 $v_{\mathsf{MC}}(z, S)$ 对任意大小联盟 $S \neq \emptyset$ 均度量相对优势：只要真实标签 $y_1$ 并列第一（$y_1 \in \mathcal{M}(S)$），就赋予其平分概率的期望增益 $1/|\mathcal{M}(S)|$。理论证明该函数既非超模也非单调，取值集合落在 $\{0, 1/\ell, \dots, 1/2, 1\}$，彻底跳出了简单博弈的限制，完整刻画了集成模型在各种局部投票格局下的真实行为。

2. 二分类封闭组合解法：线性时间精准求解两类临界事件 在二分类样本 $z=(x, y)$ 上，令正确分类器数量为 $n_+$，错误分类器数量为 $n_-$。关键性质在于：向联盟子集 $S-i$ 中加入正确分类器 $i$，其边际增益 $v_{\mathsf{B}}(S) - v_{\mathsf{B}}(S-i)$ 非零的充要条件只有两类，且收益恒为 $1/2$：要么 $i$ 使得原本落后的正确类追平成平局（引入平局），要么 $i$ 使得原本持平的状态转变为正确类独占多数（打破平局）。借助这一二值结构与完全对称性，本文证明了 Banzhaf 指数与 Shapley 值的解析求和闭式：对于预测正确的分类器 $C_i(x)=y$： $$\beta_i(G_z) = \frac{1}{2^n}\left(\binom{n}{n_-} + 1\right), \quad \phi_i(G_z) = \frac{1}{n} + \frac{T_+}{2},$$ 对于预测错误的分类器 $C_i(x) \neq y$： $$\beta_i(G_z) = -\frac{1}{2^n}\left(\binom{n}{n_+} - 1\right), \quad \phi_i(G_z) = -\frac{T_-}{2},$$ 其中 $T_\sigma$ 由两部分组合项与阶乘权重构成。该设计消除了对 $2^n$ 种联盟的穷举，使二分类样本点上的两种指数计算复杂度骤降至 $\mathcal{O}(n)$，全数据集时间复杂度严格收敛于 $\mathcal{O}(|\mathcal{D}|n)$。

3. 多分类普通生成函数代数求解：将高维联盟状态坍缩为多项式系数 在多分类场景下（$\ell > 2$），错误类别多达 $\ell - 1$ 个，相互之间存在极度错综的竞争，无法直接排列组合。本文构造了度数至多为 $\ell - 1$ 的单变量生成函数 $P_h(t)$，用于高效求解 Banzhaf 指数： $$P_h(t) = \prod_{j=2}^\ell (A_j(h) + B_j(h)t), \quad A_j(h) = \sum_{q=0}^{h-1}\binom{n_j}{q}, \quad B_j(h) = \binom{n_j}{h}.$$ 此处多项式中 $t^k$ 的系数 $[t^k]P_h(t)$ 严丝合缝地对应于“恰好有 $k$ 个错误类别获得 $h$ 票，且其余错误类别得票均严格小于 $h$”的联盟数量 $|\mathcal{S}(k, h)|$。针对特定错误类 $j$，只需除以因子 $(A_j(h) + B_j(h)t)$ 即可消除自身干扰。对于 Shapley 值，由于权重依赖联盟总大小 $|S|$，进一步引入双变量生成函数 $P_h(t, u) = \prod_{j=2}^\ell (A_j(h, u) + B_j(h, u)t)$，用变量 $u$ 的指数追踪非正确模型的总数 $m$。借助动态规划矩阵 $P^{(j)}_h[k, m]$ 递推计算多项式系数，将原本指数级的多分类 Shapley 计算压制在 $\mathcal{O}(|U|n^3\ell + |\mathcal{D}|n)$ 多项式时间内，Banzhaf 指数则达到 $\mathcal{O}(|U|n\ell^2 + |\mathcal{D}|n)$。

损失函数 / 训练策略¶

作为后验归因与博弈估值框架，enpower 无需修改基模型的训练目标或损失函数，对模型黑盒推理输出即插即用。但在数值实现上存在两项严密的数值稳定性与性能优化策略： 1. 二项式比值与对数域计算：在二分类 Banzhaf 计算中，组合数与 $2^n$ 的直接计算易导致溢出，算法利用 $\binom{n}{n_-}/2^n$ 等价于二项分布 $\mathrm{Bin}(n, 1/2)$ 在点 $n_-$ 处的概率质量这一性质，调用数值稳定的专用库求解；Shapley 的组合系数在对数域进行预计算以规避大阶乘溢出。 2. 唯一轮廓缓存与动态规划修剪：算法按测试点实际产生的排序得票向量 $\bm{p}(x, \mathcal{C}) = (n_1, n_2, \dots, n_\ell)$ 建立全局哈希字典 $J_{\text{unique}}$。对于准确率较高的模型集成，大量样本展现出完全一致的投票轮廓（$|U| \ll |\mathcal{D}|$），使得高代价的多项式 DP 仅在首次遇到该配置时触发一次，随后实现 $\mathcal{O}(1)$ 缓存命中。

实验关键数据¶

主实验¶

论文在 UCI 仓库的 6 个标准数据集（BTSC、CR、C9、TT、BM、CT）及 3 种主流集成架构上展开测试：随机森林（RF, $n=50$）、AdaBoost（AB, $n=150$）与异质集成（HET, $n=30$）。基线对比涵盖图博弈方法 ISCG、截断方法 Tr-MLE 与 Tr-PS、加权多数博弈 WMG，以及蒙特卡洛抽样基线 MC。下表展示在 Covertype（CT，大样本规模）与 CNAE-9（C9，多分类）上的多分类运行耗时与典型二分类运行耗时对比：

数据集 / 场景	集成配置与指标	enpower-β	enpower-ϕ	WMG-β / WMG-ϕ	Tr-MLE / Tr-PS
CT (多分类, 7类)	AB ($n=150$) 运行耗时 (s)	1.9 ± 0.4	265 ± 50 (优化版 77s)	不支持多分类	不适用直接多分类
CT (多分类, 7类)	RF ($n=50$) 运行耗时 (s)	0.10 ± 0.01	2.6 ± 0.2 (优化版 0.48s)	不支持多分类	不适用直接多分类
C9 (多分类, 9类)	RF ($n=50$) 运行耗时 (s)	0.0037 ± 0.0004	0.14 ± 0.02	不支持多分类	不适用直接多分类
二分类大样本 (BM)	AB ($n=150$) 运行耗时 (s)	< 0.01	< 0.01	~10 - 100	> 100

在 CLIP 视觉大模型 Prompt 集成（22 个通用 Prompt 模板，在 CIFAR-100、ImageNet-A 和 Pets 上进行多分类零样本推理）实验中，通过 enpower 评估 Prompt 贡献并筛选 Top-$k$ 子集进行集成的表现如下表所示（测试集分类精度 Accuracy）：

评测数据集	评估排序依据	最优 Top-k 精度 (best acc)	达到最优的子集大小 k	全集成 baseline (k=22)
CIFAR-100 (100类)	enpower-β	0.649 ± 0.004	k = 10	0.645 ± 0.004
CIFAR-100 (100类)	enpower-ϕ	0.649 ± 0.004	k = 8	0.645 ± 0.004
CIFAR-100 (100类)	原始 Accuracy (Acc)	0.648 ± 0.005	k = 14	0.645 ± 0.004
CIFAR-100 (100类)	Tr-PS / Tr-MLE	0.647 / 0.648	k = 15 / 14	0.645 ± 0.004
ImageNet-A (200类)	enpower-ϕ	0.308 ± 0.003	k = 5	0.300 ± 0.004
ImageNet-A (200类)	Tr-PS	0.298 ± 0.006	k = 13	0.295 ± 0.004

消融实验¶

论文设计了与蒙特卡洛抽样（MC，样本量设定为 $s = n^2$）的估计精度与排序偏差消融对比，验证解析算法在消除随机误差上的必要性；同时对唯一轮廓数量 $|U|$ 带来的提速优势进行了消融分析。

数据集与集成	指标配置	蒙特卡洛最大绝对误差 ε_abs	蒙特卡洛最大相对误差 ε_rel	Kendall's τ (vs. enpower)
BTSC (RF, n=50)	Shapley (ϕ)	0.0045 ± 0.0007	0.42 ± 0.15	0.720 ± 0.036
BTSC (RF, n=50)	Banzhaf (β)	0.0003 ± 0.0000	3.34 ± 4.51	0.967 ± 0.004
CR (AB, n=150)	Shapley (ϕ)	0.0010 ± 0.0002	0.28 ± 0.20	0.882 ± 0.014
C9 (RF, n=50)	Shapley (ϕ)	0.0063 ± 0.0009	0.31 ± 0.04	0.288 ± 0.089
C9 (HET, n=30)	Shapley (ϕ)	0.0148 ± 0.0029	0.42 ± 0.09	0.457 ± 0.139

关键发现¶

抽样法在小幅度边际贡献上存在严重失真：消融表清晰显示，在 C9 等数据集上，基于 $s=n^2$ 的蒙特卡洛采样方法与精确 Shapley 排序的相关性甚至骤降至 0.288；由于真实边际增益数值极小，抽样波动会产生高达 3.34 倍甚至 13.72 倍的相对误差，这凸显了解析精确算法的不可替代性。
唯一得票轮廓显著收缩运算空间：实际数据中高精度分类器导致有效投票分布高度集中。在 CIFAR-100 上，5,000 个验证集样本中平均仅出现 675 个唯一投票轮廓；在 Pets 数据集上更是仅有 123 个，使动态规划计算量削减了 80%~93%。
冗余弱模型会毒化集成决策：在 CLIP 提示词集成剪枝实验中，所有数据集的最优子集成规模均远小于全量 22 个提示词（如 ImageNet-A 仅需 5 个，CIFAR-100 仅需 8-10 个）。个别单体准确率虚高的提示词（如“带有水印的照片”）在权力指数下因频发干扰投票而呈现负值，剪除后显著提升了集成泛化性能。

亮点与洞察¶

将博弈权力指数从纯理论象牙塔带入实用工业级集成：以往由于 $\mathcal{O}(2^n)$ 复杂度，模型归因通常依赖大幅度妥协的启发式。enpower 巧妙利用投票标签置换不变性，将组合爆炸问题优雅规约为普通生成函数的多项式乘法，实现了多项式时间内的解析解。
发现“高单体准确率”与“高集成系统价值”之间的反直觉背离：实验揭示了一个极具启发性的现象：部分单体准确率排名靠前的 Prompt（如带有局部裁剪的视图）在集成系统中往往具有很强的误导重合性；反而是单体精度略逊但在冷门类目上提供互补判决的 Prompt 获得了极高的 Shapley 值，彻底印证了多样性协同的系统学规律。
即插即用的多模态模型选择与提示工程范式：不仅能用于传统随机森林与提升树的集成剪枝（Ensemble Pruning），还可直接无缝迁移到 VLM / LLM 的多提示词选择与混合专家系统（MoE）专家权重量化评估中。

局限与展望¶

局限于硬分类离散投票设定：当前特征函数与组合求和体系完全建立在类别硬投票（Hard Voting）的基础上，无法直接兼容各分类器输出连续概率分布的软投票（Soft Voting）与加权投票（Weighted Plurality Voting）。
高阶多项式时间在大集成下的算力开销：多分类 Shapley 计算的时间复杂度为 $\mathcal{O}(|U|n^3\ell)$，当基分类器数目 $n$ 膨胀至数千且类别数 $\ell$ 达到上千时，即使引入 FFT 与 DP 缩减，多项式阶数仍会带来显著的计算延迟。
未来方向：作者指出可将该权力指数进一步拓展到数据清洗与验证（Data Valuation）、子集成贪心动态选拔机制，以及探索支持连续后验概率的广义平局决胜博弈框架。

评分¶

新颖性: ⭐⭐⭐⭐⭐ [首次突破相对多数投票与随机平局决胜的非简单博弈权力指数精确计算壁垒]
实验充分度: ⭐⭐⭐⭐⭐ [覆盖经典表格集成剪枝与前沿视觉大模型 Prompt 归因，对比深入详实]
写作质量: ⭐⭐⭐⭐⭐ [理论推导严密精妙，生成函数建模与算法复杂度证明一气呵成]
价值: ⭐⭐⭐⭐⭐ [为模型集成剪枝、可解释性 AI 与大模型提示工程提供了坚实精确的博弈论工具]

数据集 / 场景	集成配置与指标	enpower-β	enpower-ϕ	WMG-β / WMG-ϕ	Tr-MLE / Tr-PS
CT (多分类, 7类)	AB (\(n=150\)) 运行耗时 (s)	1.9 ± 0.4	265 ± 50 (优化版 77s)	不支持多分类	不适用直接多分类
CT (多分类, 7类)	RF (\(n=50\)) 运行耗时 (s)	0.10 ± 0.01	2.6 ± 0.2 (优化版 0.48s)	不支持多分类	不适用直接多分类
C9 (多分类, 9类)	RF (\(n=50\)) 运行耗时 (s)	0.0037 ± 0.0004	0.14 ± 0.02	不支持多分类	不适用直接多分类
二分类大样本 (BM)	AB (\(n=150\)) 运行耗时 (s)	< 0.01	< 0.01	~10 - 100	> 100