Refinement as a Service: Algorithmic Predictor Refinement¶

会议: NeurIPS 2026
arXiv: 2610.11415
论文: https://arxiv.org/abs/2610.11415
领域: 其他
关键词: 预测精化, 校准预测器, 信号方案, 可观测线性空间, 极值射线分解

一句话总结¶

针对无需真实贝叶斯概率下的校准预测器聚合问题，本文将校准预测器抽象为信号方案并基于特征无关混淆定义信息优势，确立了确定性输出下双边多项式时间求解与多边NP-hard的算法分水岭，并提出了允许随机化输出时任意输入规模下的多项式时间极值射线分解精化算法。

研究背景与动机¶

预测聚合（Prediction Aggregation）旨在将多个异构预测器的信息在原则性框架下整合成一个更具信息量的综合预测，是集成学习、专家建议在线学习以及大模型专家混合（MoE）等技术背后的共同基础。在在线广告点击率（CTR）预测、医疗辅助诊断和气象预报等高敏感场景中，预测器的校准性（Calibration）至关重要，即在预测器发出某个预测信号的条件下，真实标签的期望必须严格等于该信号所对应的数值预测。然而在真实商业协作中，不同平台或专长代理往往掌握着互补的用户信息分布，各自拥有已校准的局部模型，但各方出于数据隐私和商业机密，既无法获知底层的真实后验贝叶斯概率，也不能直接共享底层训练数据，仅能通过协议交换模型在各特征上的预测行为。

此时面临的核心挑战是：在仅给定特征边际分布与各方校准预测器输出、而完全未知底层真实贝叶斯概率的现实约束下，能否利用其他参与者的信息对各参与方的预测器进行不可反向超越的“精化”（Refinement）？传统预测聚合文献多关注用加权平均等算子将多个数值汇总为一个数值，但这常常会抹平携带特征细分结构的有效信号；若仅按数值预测相等去合并信号，则会丢失信息论意义上的划分精细度。更关键的是，何时能够保证精化出的新预测器在所有输入特征上都弱占优、且依然维持严格的信号级校准性，此前缺乏严密的算法与计算复杂性刻画。

本文从信息结构与可观测代数约束切入，将校准预测器形式化为特征空间到抽象离散信号的随机核，通过特征无关信道（Garbling）定义严格的信息优势偏序，并将新预测器的可构造性精确等价为特征空间上的线性可观测信息。本文的核心 idea 是：将校准预测器的信息精化重构为可观测线性空间非负锥内的向量分解问题，证明确定性输出下双边可约化为二分图割点分支分解而在多边下归约自精确覆盖呈现 NP-hard，并进而证明允许随机化输出时，任意输入规模下的无损最大精化可在多项式时间内通过多面体锥的极值射线贪心分解与 LP 支撑集收缩精确求解。

方法详解¶

整体框架¶

本方法的目标是在输入特征分布 $\lambda \in \Delta(\mathcal{X})$ 与 $k$ 个信号级校准预测器 $(f_j)_{j\in[k]}$ 条件下，为每个 $f_j$ 寻找一个在其信息上达成严格帕累托改进的可构造预测器 $g_j$（即 $g_j \succ f_j$），且 $g_j$ 在所有可构造预测器族 $\mathcal{G}$ 中处于不可被进一步支配的极大状态（$g_j \in \mathcal{G}_{\succ}$）；若无法精化则保持原样。

整个精化服务分为三个主要阶段：首先将离散信号核转化为特征空间上的简约向量包（Reduced Bag-of-Vectors），构建信号-特征矩阵 $\mathbf{M}$ 并提取可观测行空间 $\text{Row}(\mathbf{M})$；随后根据系统约束选择确定性分支或随机化分支进行精化求解；最后基于观测到的边际标签质量 $\mathbf{b}$ 求解线性方程组，为精化后的每一个原子信号赋上严格校准的后验数值预测。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入: k个校准预测器与特征分布<br/>特征空间X与已知信号核"] --> B["向量包化与可观测线性空间表征<br/>构建M与行空间Row(M)"]
    B --> C{"输出预测器类型约束"}
    C -->|双边确定性 k=2| D["二分重叠图割点分支分解<br/>G-A连通分量投影提取极细划分"]
    C -->|多边确定性 k>=3| E["确定性精化NP-hard判定<br/>X3C3精确覆盖归约"]
    C -->|允许随机化 任意k| F["可构造非负锥极值射线分解<br/>LP支撑集极小化与逐行剥离"]
    D --> G["解线性系统计算校准预测值<br/>赋概率值p(v)=ξTb/λ(v)"]
    F --> G
    G --> H["输出各方最大化精化预测器<br/>完成Refinement-as-a-Service"]

关键设计¶

1. 向量包化与可观测线性空间表征：将离散信号语义化为高维空间向量

传统研究直接处理连续或离散的数值预测映射，容易在数值相同时混淆携带不同特征辨识能力的信号。为此，本文将每个预测器 $f$ 的离散信号 $\ell$ 在特征样本上的触发概率表示为非负向量 $\mathbf{v}_{f,\ell} \in \mathbb{R}_+^n$（其中 $\mathbf{v}_{f,\ell}(i) = T_f(\ell \mid x_i)$），所有信号向量之和恰为全 1 向量 $\mathbf{1}$。针对同方向射线上正比例向量仅相当于加入独立随机硬币分割的冗余，定义射线等价合并（Ray Reduction），得到唯一的简约向量包 $\mathcal{V}(f)$。进一步地，由于聚合者无法获知底层贝叶斯概率 $q_i = \mathbb{P}[Y=1 \mid X=x_i]$，仅能观测到各输入信号的校准预测值，将 $N$ 个输入信号向量堆叠为信号-特征矩阵 $\mathbf{M} \in \mathbb{R}_+^{N \times n}$，则观测到的标签质量向量 $\mathbf{b} = \mathbf{M}\mathbf{y}$，其中 $\mathbf{y}_i = \lambda_i q_i$。本文证明一个新信号向量 $\mathbf{v}$ 的条件标签均值能被唯一确定，当且仅当 $\mathbf{v} \in \text{Row}(\mathbf{M})$。由此，可构造预测器族 $\mathcal{G}$ 的每个信号向量均严格受限于可观测线性空间与非负象限的交集： $$ \mathcal{M} = \text{Row}(\mathbf{M}) \cap \mathbb{R}_+^n $$ 这一代数重构将复杂的信息论信道模拟问题转化为了精确的凸几何约束。

2. 二分重叠图割点分支分解：确定性双边精化的图论组合解法

当限制输出必须为确定性预测器（即每个特征以概率 1 映射到确定信号单元）且输入预测器数量 $k=2$ 时，两预测器的信号单元分别构成特征空间的两组划分 $\Pi_{f_1}$ 与 $\Pi_{f_2}$。本文构建二分重叠图 $G = (\Pi_{f_1} \sqcup \Pi_{f_2}, E)$，其中边表示两单元在特征空间有非空交集。为了找出包含在某个单元 $A \in \Pi_{f_1}$ 内的所有可观测子集，算法移除顶点 $A$ 并分析导出图 $G - A$ 的连通分支 $K$。对于每个连通分支 $K$，定义其在 $A$ 上的投影分支块： $$ A_K = A \cap \left( \bigcup_{A' \in \mathcal{I}(K) \cap \Pi_{f_2}} A' \right) $$ 本文证明非空的 $A_K$ 构成了单元 $A$ 的严格划分，且其指示向量满足线性代数差分关系： $$ \mathbf{1}{A_K} = \sum}(K) \cap \Pi_{f_2}} \mathbf{1{A'} - \sum) $$ 这意味着每个分支块 }(K) \cap \Pi_{f_1}} \mathbf{1}_{A^\dagger} \in \text{Row}(\mathbf{M$A_K$ 均天然位于可观测行空间中，其实际标签质量可通过已知单元的代数加减精确解析求出。对所有输入单元完成分支分解后，算法构造出不可再细分的最细规范划分 $\widehat{\Pi}_j$；若 $\widehat{\Pi}_j \neq \Pi_{f_j}$，则成功实现帕累托信息占优精化；反之则证明原预测器在此信息下已处于不可精化状态。全流程复杂度仅为 $\mathcal{O}(n^2)$。

3. 多边确定性精化的精确覆盖 NP-Hard 归约：划定计算复杂度下界

当预测器数量 $k \ge 3$ 时，确定性精化面临指数级组合爆炸。本文通过将三元精确三覆盖问题（X3C3，即每个元素恰好出现在 3 个三元子集中的 Exact 3-Cover）归约至确定性精化判定问题 ifRefinable，确立了其 NP 难性。在构造中，将特征空间分为两部分 $\mathcal{X}_1 = \{v_1, \dots, v_d\}$ 与 $\mathcal{X}_2 = \{w_1, \dots, w_m\}$，基准预测器 $f_1$ 划分整个特征空间为 $\{\mathcal{X}_1, \mathcal{X}_2\}$，其余 $d$ 个预测器分别编码子集 $C_j$ 的关联关系。本文证明 $\mathcal{X}_2$ 内不存在任何非平凡的可观测子集，而 $\mathcal{X}_1$ 内存在非平凡可观测子集 $\mathbf{1}_S \in \text{Row}(\mathbf{M})$ 当且仅当其指示向量 $\mathbf{z}$ 满足关联矩阵方程 $\mathbf{X}\mathbf{z} = \beta \mathbf{1}_m$。由于 $\mathbf{X}$ 每行恰有 3 个 1，标量 $\beta$ 只能取值 0、1、2、3。排除平凡情况后，$\beta=1$ 或 $\beta=2$ 恰好分别对应于 X3C3 的原解或补集精确覆盖解。这证明了在多方确定性规则下判断是否存在可构造精化预测器是 NP-hard 的。

4. 可构造非负锥极值射线分解：支持任意多输入的随机化多项式算法

若放宽限制允许输出预测器为随机化预测器，问题迎来颠覆性突破。此时，任意可构造信号向量均落入多面体锥 $\mathcal{M} = \text{Row}(\mathbf{M}) \cap \mathbb{R}_+^n$。根据锥几何理论，多面体锥中的极值射线（Extreme Ray）具有不可再分的原子性，且本文严格证明：非零向量 $\mathbf{v} \in \mathcal{M}$ 处于极值射线上，当且仅当其在 $\mathcal{M}$ 内具有极小支撑集（Minimal Support），即不存在非零向量 $\mathbf{u} \in \mathcal{M}$ 使得 $\text{supp}(\mathbf{u}) \subsetneq \text{supp}(\mathbf{v})$。

基于此性质，算法设计了两层极小化与剥离循环：首先通过求解线性规划可行性问题 Feasible(S)（检查是否存在支撑于子集 $S$ 内且坐标和为 1 的行空间非负向量），逐一尝试移除索引，在最多 $n$ 次 LP 求解内锁定一个极小支撑的极值射线向量 $\mathbf{u}$；随后计算残差步长 $\beta = \min_{i \in \text{supp}(\mathbf{u})} \mathbf{r}_i / \mathbf{u}_i$，将当前向量 $\mathbf{r}$ 分解为 $\beta \mathbf{u}$ 与残余向量 $\mathbf{r} - \beta \mathbf{u}$。由于每次剥离至少使残余向量的非零支撑集维度减少 1，整个分解过程在最多 $n$ 步内必定终止于零向量。对所有输入信号完成该分解并合并同向射线后，得到的预测器每个信号向量均处于极值射线，保证了其在信息论支配意义下处于 $\mathcal{G}_{\succ}$。对于精化后的每个信号 $\mathbf{v}$，通过解线性方程 $\mathbf{M}^\top \xi = \mathbf{v}$ 并代入已知标签质量 $\mathbf{b}$，可唯一计算出严格校准的后验数值预测： $$ p(\mathbf{v}) = \frac{\xi^\top \mathbf{b}}{\lambda(\mathbf{v})} $$ 整体算法仅需调用 $\mathcal{O}(N n^2)$ 次有理线性规划，完全在强多项式时间内运行。

一个完整示例¶

以 3 类用户特征 $\mathcal{X} = \{x_1, x_2, x_3\}$（均等概率 $\lambda_i = 1/3$）为例，设有两个输入校准预测器： - $f_1$ 具有信号单元 $A_1 = \{x_1, x_2\}$（预测 0.30）和 $A_2 = \{x_3\}$（预测 0.70）； - $f_2$ 具有信号单元 $B_1 = \{x_1\}$（预测 0.10）和 $B_2 = \{x_2, x_3\}$（预测 0.60）。

算法构建重叠图 $G$，顶点为 $\{A_1, A_2, B_1, B_2\}$，边为 $(A_1, B_1)$、$(A_1, B_2)$ 与 $(A_2, B_2)$。对于 $A_1$，移除它后图 $G - A_1$ 裂解为两个连通分支 $K_1 = \{B_1\}$ 与 $K_2 = \{A_2, B_2\}$。由分支公式计算投影： - $A_1^{K_1} = A_1 \cap B_1 = \{x_1\}$； - $A_1^{K_2} = A_1 \cap B_2 = \{x_2\}$。

单元 $A_1$ 成功裂解为两个细分信号 $\{x_1\}$ 与 $\{x_2\}$。利用代数差分计算 $x_2$ 处的预测质量：$L(\{x_2\}) = L(A_1) + L(B_2) - L(A_2) - L(B_1)$，带入数值解得 $x_2$ 的校准预测为 0.50。最终输出精化预测器 $g$ 能够完全辨别 $\{x_1\}$ (0.10)、$\{x_2\}$ (0.50) 与 $\{x_3\}$ (0.70)，在零隐私泄露和无真实贝叶斯概率先验的前提下，实现了对两输入预测器的最大帕累托精化。

实验关键数据¶

算法复杂度与理论收敛性对比¶

本文属于纯理论计算机科学与机器学习基础理论工作（Accepted to NeurIPS 2026），其主要贡献通过严格的定理与渐近复杂度界限定量呈现。下表系统对比了不同设置下精化问题的算法判定、计算复杂度与极值性质：

设定分支	允许输出类型	输入预测器数 $k$	复杂度 / 求解状态	核心算法机制	理论保证与极值性质
双边确定性	确定性（Deterministic）	$k = 2$	$\mathcal{O}(n^2)$ 强多项式时间	二分重叠图割点连通分支分解	产物为最细唯一规范划分 $\widehat{\Pi}$，证明严格帕累托优势
多边确定性	确定性（Deterministic）	$k \ge 3$（任意）	$\mathsf{NP}$-Hard	X3C3 精确三覆盖多项式归约	证明确定性条件下多方精化判定的计算下界不可逾越
多边随机化	随机化（Randomized）	任意 $k \in \mathbb{N}$	多项式时间（$\mathcal{O}(N n^2)$ 次 LP）	支撑集逐点缩减与极值射线贪心剥离	全局信息极大（$g \in \mathcal{G}_{\succ}$），输出规模 $\le m_j n$
数值型聚合基线	仅数值（Blackwell序）	任意 $k \in \mathbb{N}$	凸优化 / 连续松弛	边际分布保序重采样	仅保证标签后验排序，无法保留特征区分性信道结构

关键组件消融与性质分析¶

下表对精化算法中的关键几何与代数设计组件进行了系统性消融与失效机理分析：

模块 / 机制设计	作用配置与状态	变体状态与退化机制	理论退化分析与后果
向量包射线归一化（Ray Reduction）	完整机制	仅使用原始向量包 $\mathcal{V}^{\text{raw}}(f)$	包含同射线正倍数冗余信号，导致信号空间膨胀且无法唯一判定极值性
极小支撑集搜索（Minimal Support）	贪心 LP 缩减	任意选取可行基（Arbitrary LP Basic Sol）	分解出的非零分量可能仍处于锥内部面，残差支撑集不单调缩减，算法可能死循环
信号级校准假定（Signal-level Calib.）	完整假定	降级为常规预测级校准（Prediction-level）	同数值预测信号被强制混合，矩阵方程退化，可观测线性空间维度缩水，丢失细粒度特征划分
特征无关混淆信道（Garbling Kernel）	严格单向模拟	允许依赖特征的随机信道（Feature-dependent）	退化为普通泛化重训练，违反不可获知先验/特征机密的隐私协作协议

关键发现¶

算法复杂度存在明显的“确定性 vs. 随机化”对偶反转：确定性多边精化受限于组合子集覆盖约束呈现 NP 难，而一旦引入连续随机化核，离散子集覆盖即被松弛为凸锥上的极值射线几何，从而使问题在任意输入规模下重获多项式时间可解性。
精化信号的数值可计算性完全解耦于真实贝叶斯概率：通过转置矩阵方程 $\mathbf{M}^\top \xi = \mathbf{v}$，所有可构造信号的后验概率计算被转化为线性可观测系统，计算精度仅取决于浮点或有理数编码位长，不存在参数估计误差。
信号级校准与信息支配具有严格的不可逆性：合并相同数值预测的信号无法逆向恢复特征划分，在模型作为服务（MaaS）调用时，保留离散信号核结构能提供远优于纯数值输出的信息冗余度。

亮点与洞察¶

将预测聚合的经典统计学问题升华为凸几何与信息论交织的组合优化问题：巧妙将校准预测器映射为特征指示空间的向量包，用可观测行空间 $\text{Row}(\mathbf{M})$ 严格界定了外部聚合者在零先验条件下的“认识论边界”。
提出了“Refinement-as-a-Service”（精化即服务）这一具有商业落地前景的新范式：允许拥有海量全域特征的平台方与拥有垂直领域高质量预测器的代理方，在不泄露底层数据和特征的前提下，通过算法协议互相“注入”信息，输出帕累托支配的更优预测器。
极值射线与极小支撑集等价性的算法落地极其精炼：巧妙利用不超过 $n$ 次 LP 的坐标剔除法求解极小支撑向量，避免了通用的指数级多面体顶点枚举算法，构造了高度实用化的多项式求解器。

局限与展望¶

特征空间离散有限基底假设：当前理论建立在有限特征空间 $\mathcal{X}$（$|\mathcal{X}| = n$）与已知精确特征边际分布 $\lambda$ 的前提下；在连续高维特征空间或仅有经验经验采样分布时，矩阵 $\mathbf{M}$ 与线性系统的泛化界与样本复杂度仍待解决。
标签维度的二元限制：当前推导聚焦于二元分类标签 $\mathcal{Y} = \{0, 1\}$，尽管论文指出可自然推广，但对于高维多分类或连续回归任务下的校准性与可观测空间张量结构，仍需更复杂的张量代数刻画。
策略性参与者的博弈论激励机制：当前设定各参与方诚实提交预测器，若参与者存在策略性操纵（如故意提交过拟合或恶意变形的信号核以探查对手信息），如何设计防欺诈的机制化精化协议是极具潜力的后续方向。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次从信息论支配和可观测线性空间视角刻画校准预测器精化问题，提出了极富启发性的理论抽象。
理论深度: ⭐⭐⭐⭐⭐ 建立了双边确定性多项式、多边确定性NP-hard与多边随机化多项式的完整理论画卷，证明严谨自洽。
写作质量: ⭐⭐⭐⭐⭐ 概念铺垫通俗易懂，开篇CTR广告实例生动具象，算法伪代码与数学定义条理分明。
价值: ⭐⭐⭐⭐☆ 为多模型协作、联邦预测聚合以及预测即服务（Prediction APIs）提供了坚实的算法与信息论基石。

设定分支	允许输出类型	输入预测器数 \(k\)	复杂度 / 求解状态	核心算法机制	理论保证与极值性质
双边确定性	确定性（Deterministic）	\(k = 2\)	\(\mathcal{O}(n^2)\) 强多项式时间	二分重叠图割点连通分支分解	产物为最细唯一规范划分 \(\widehat{\Pi}\)，证明严格帕累托优势
多边确定性	确定性（Deterministic）	\(k \ge 3\)（任意）	\(\mathsf{NP}\)-Hard	X3C3 精确三覆盖多项式归约	证明确定性条件下多方精化判定的计算下界不可逾越
多边随机化	随机化（Randomized）	任意 \(k \in \mathbb{N}\)	多项式时间（\(\mathcal{O}(N n^2)\) 次 LP）	支撑集逐点缩减与极值射线贪心剥离	全局信息极大（\(g \in \mathcal{G}_{\succ}\)），输出规模 \(\le m_j n\)
数值型聚合基线	仅数值（Blackwell序）	任意 \(k \in \mathbb{N}\)	凸优化 / 连续松弛	边际分布保序重采样	仅保证标签后验排序，无法保留特征区分性信道结构

模块 / 机制设计	作用配置与状态	变体状态与退化机制	理论退化分析与后果
向量包射线归一化（Ray Reduction）	完整机制	仅使用原始向量包 \(\mathcal{V}^{\text{raw}}(f)\)	包含同射线正倍数冗余信号，导致信号空间膨胀且无法唯一判定极值性
极小支撑集搜索（Minimal Support）	贪心 LP 缩减	任意选取可行基（Arbitrary LP Basic Sol）	分解出的非零分量可能仍处于锥内部面，残差支撑集不单调缩减，算法可能死循环
信号级校准假定（Signal-level Calib.）	完整假定	降级为常规预测级校准（Prediction-level）	同数值预测信号被强制混合，矩阵方程退化，可观测线性空间维度缩水，丢失细粒度特征划分
特征无关混淆信道（Garbling Kernel）	严格单向模拟	允许依赖特征的随机信道（Feature-dependent）	退化为普通泛化重训练，违反不可获知先验/特征机密的隐私协作协议