算法專家聚合

算法專家聚合

Algorithmic Expert Aggregation

https://arxiv.org/pdf/2607.08744

摘要

預測聚合旨在將多個貝葉斯專家預測中的信息合并為一個聚合預測。然而，在大部分此類文獻中，聚合預測是針對特定的損失或魯棒性標準進行優化的，其本身不必針對結果進行校準：所報告的預測不必等于在給定聚合預測本身條件下的結果條件概率。我們引入并研究專家聚合，其目標則是將貝葉斯專家聚合為一個新的專家，該新專家能夠繼續提供校準的預測。具體而言，我們考慮這樣一種設定：每個輸入專家報告校準的預測，聚合器可以觀察到狀態上的先驗分布以及輸入專家，但無法觀察到狀態潛在的貝葉斯概率。我們探討是否能夠：(i) 構建一個校準的輸出專家，該專家布萊克韋爾細化（Blackwell refines）了目標專家，且無法利用可用信息進一步進行布萊克韋爾改進；以及 (ii) 在指定了恰當損失（proper loss）的情況下，在所有此類細化中計算出一個近乎損失最優的專家。

我們將校準的專家表述為簡化型信息結構（reduced-form information structures），并通過所誘導預測分布的布萊克韋爾占優（Blackwell dominance）來衡量細化程度。我們通過可觀測線性信息來刻畫可構建的輸出專家：輸入專家生成一個線性系統，其行空間決定了哪些校準的輸出預測是可識別的，并且當且僅當一個新專家的預測位于相關的可觀測非負錐內時，該新專家才是可構建的。我們確立了一幅清晰的算法圖景。當允許使用隨機化輸出專家時，細化搜索問題 (i) 和恰當損失優化問題 (ii) 均存在高效算法。相比之下，確定性輸出專家在計算上是難以處理的：即使只有兩個輸入專家且目標專家為恒定基準率專家，判定是否存在確定性校準細化也是 NP 難的；并且除非 P = NP，否則確定性恰當損失優化不存在乘法多項式時間近似方案（multiplicative PTAS），即使對于布里爾損失（Brier loss）也是如此。

1 引言

決策者正在斟酌是否采取某項行動，該行動的收益取決于某一事件是否發生：為具體起見，若事件發生則收益為1，否則為-1。為提供協助，一個專家團隊對該事件發生的概率進行預測。出于專業性，這些專家總是報告其盡最大努力做出的預測，并綜合考慮了他們所掌握的所有信息。盡管如此，不同的專家專注于該事項的不同方面，導致從各自專家的視角來看，所有不同的預測都是誠實的。于是決策者面臨一個問題：如何將這些不同的預測聚合為一個能為決策提供最佳指導的單一預測？

這正是預測聚合（forecast aggregation）這一研究脈絡所探討的核心研究問題（參見，例如，[Sto61, BG69]）。在一個決策者擁有所有相關先驗知識的理想化世界中，上述問題可歸結為貝葉斯推斷：給定有關所關注事件及所有專家預測的聯合信息結構，（至少在原則上）可以推斷出以所有專家的預測為條件的該事件的后驗概率。另一方面，決策者往往無法獲取完整的信息結構（或無法以貝葉斯意義形成關于它的信念），在這種情況下，人們可以轉向魯棒預測聚合（robust forecast aggregation），其旨在針對信息結構的不確定性，在最壞情況下優化聚合預測[ABS18, LR22, KWW24, GHH+25, FMNW25]。在考慮實際情況時，這一直是預測聚合中占主導地位的方法。

在本文中，我們從另一個角度審視預測聚合，并研究其一種自然的變體，我們將其稱為專家聚合（expert aggregation）。在專家聚合中，我們不再處理一次性的預測，而是直接處理專家本身，將每位專家視為從可能的觀測到數值預測的一個可能隨機化的映射。其目標是將多個輸入專家聚合為一個單一的輸出專家，該輸出專家的優越性由布萊克韋爾信息量（Blackwell's informativeness）[Bla53]來量化，這是一個通過“整體有用性”對專家進行排序的經典概念。專家聚合的顯著特征，尤其是在魯棒預測聚合的背景下，是我們要求輸出專家做出校準的預測（calibrated forecasts），即專家做出的預測始終精確等于以該預測為條件的該事件的后驗概率。1從概念上講，專家聚合對應于這樣一些場景：我們旨在構建一個通用的專家系統，該系統并非針對特定的單次任務，而是為不特定的下游應用提供有用的建議。更具體地說，設想以下場景：一家醫院收集了多年醫療病例的檔案，其中特別包含了多位醫學專家關于每位患者患有某種潛在疾?。ㄈ鐏喤R床糖尿?。┑目赡苄缘呐袛唷Ｓ酶鼘I的術語來說，這些檔案精確地包含了以下信息：患者可觀測特征的總體分布，以及這些可觀測特征與每位專家關于該潛在疾病可能性的預測之間的相關結構。2請注意，后者等同于上文討論的輸入專家系統的形式，即從觀測到數值預測的映射。我們希望將這些檔案聚合為一個能夠輔助未來醫療決策的專家系統。重要的是，我們不希望將該專家系統過擬合于任何特定的治療方案，因為該潛在疾病會以不同的方式影響不同的潛在治療方案。正如我們稍后將討論的，我們的算法將輸入檔案聚合為一個具有以下理想特性的單一專家系統，這些特性本質上定義了專家聚合問題：

• 校準性（Calibration）：輸出專家始終做出校準的預測，這本質上是在缺乏對下游任務的具體知識時唯一合理的做法，同時也確保了預測的可解釋性。后者在某些應用領域（包括醫學）中至關重要。
• 最大信息性（Maximal informativeness）：就布萊克韋爾信息量（Blackwell informativeness）而言，輸出專家在所有可以基于輸入中包含的信息構建的專家中是（近似）不受支配的，或帕累托最優的。換句話說，輸出專家最大限度地利用了輸入信息。
• 模塊化（Modularity）：輸出專家可以用于任何下游任務，甚至可以以黑盒方式輸入到后續的聚合算法中。輸出專家的性能由校準性和最大信息性作為支撐，這兩者很大程度上與下游應用無關。此外，下游應用不需要訪問專家聚合的任何輸入專家。這提供了某種形式的隱私保證，這在醫學以及許多其他應用中也具有巨大價值。
• 針對性改進（Targeted refinement）：除上述要求外，我們可以選擇性地要求輸出專家改進一個指定的目標輸入專家，這意味著輸出專家的信息量永遠不會少于——并且在許多方面通常多于——目標輸入專家。這在我們希望保留某個輸入專家的完整領域專業知識，同時整合來自其他輸入專家的通用知識的應用中特別有用。

總結上述討論，我們對專家聚合的研究旨在回答兩個級聯的算法問題，這些問題將上述理想特性重組為更具技術意義的形式。首先：

改進（Refinement）：是否可以將輸入專家中包含的可觀測信息重組為一個新的專家，使其在布萊克韋爾意義上比一個（可能是平凡的）目標專家更具信息量？

如果這種改進是可能的，我們進一步追問可以將它推進到什么程度：

最優性（Optimality）：聚合器能否構建一個不受支配的專家，并且能否在所有支配目標的可行專家上進行優化？

1.1 我們的貢獻

我們針對這些問題提供了算法層面的解答。我們的結果揭示了隨機化專家聚合與確定性專家聚合之間尖銳的計算二分法：隨機化輸出專家允許高效的搜索與優化算法，而確定性輸出專家即使在高度受限的實例中也會導致計算上的不可處理性。

聚合為隨機化專家時的高效算法。我們首先研究當輸出專家被允許報告可能隨機化的預測時，聚合器問題的計算復雜度。我們表明，在這種自然的隨機化輸出模型下，SEARCH-AGGREGATION 和 OPT-AGGREGATION 均存在高效的算法解。

定理 1.1（非正式）。對于任意數量 k k 的輸入專家和任意目標專家，存在一個求解 SEARCH-AGGREGATION 的多項式時間算法。此外，對于任意數量 k k 的輸入專家和任意目標專家，針對每一個正則恰當損失（regular proper loss），存在一個求解 OPT-AGGREGATION 的加法 FPTAS（全多項式時間近似方案），即該算法輸出一個布萊克韋爾占優目標專家的可構建專家，且其期望恰當損失在期望的加法誤差范圍內接近最優值。

定理的第一部分表明，對于搜索問題，只要存在這樣的改進，隨機化聚合就能高效地找到目標專家的一個最大信息量的后驗一致性改進。第二部分表明，這種可處理性同樣延伸到了優化問題：在所有布萊克韋爾占優目標專家的可構建專家中，對于任何給定的恰當損失，人們可以高效地找到一個期望恰當損失近乎最優的專家。從概念上講，結果的第二部分解決了一個定義更明確的問題，在該問題中我們仍然旨在構建一個校準的專家系統，該系統可以在下游任務中提供持久的幫助，但我們確實知道在這些任務中起作用的損失函數。重要的是，在這兩個問題中，算法都不需要訪問潛在的貝葉斯概率。它們僅使用先驗分布和輸入專家，且輸出專家保持完全可構建和完全校準。

確定性聚合的困難性。接著我們轉向確定性輸出專家。確定性專家在那些每個狀態、特征檔案或患者檔案應該接收到一個穩定預測的應用中是很自然的。然而，我們的結果表明，確定性聚合在計算上比隨機化聚合難得多。

定理 1.2（非正式）。問題 SEARCH-AGGREGATION 的確定性輸出是 NP 難的，即使只有兩個輸入專家、一個均勻先驗分布，且兩個輸入專家之一是報告基準率并作為目標專家的常數專家。此外，除非 P = NP，問題 OPT-AGGREGATION 的確定性輸出不存在乘法 PTAS（多項式時間近似方案），即使對于布里爾損失（Brier loss）也是如此，即使只有兩個輸入專家、一個均勻先驗分布和一個常數目標專家。

這一結果表明，SEARCH-AGGREGATION 的可處理性本質上依賴于允許隨機化輸出專家。這種困難性并非由大量專家、復雜的先驗分布或豐富的目標專家所驅動：它僅憑兩個輸入專家就已經出現，其中一個是可能的最簡單的專家：一個常數基準率專家。因此，即使是判定這樣一個常數專家是否能被一個確定性可構建專家嚴格改進，在計算上也是困難的。優化困難性進一步表明，確定性聚合不僅對搜索問題困難，而且對損失最小化 OPT-AGGREGATION 也困難。即使是對于標準的布里爾損失，除非 P = NP，否則不存在高效的乘法近似方案。

1.2 我們的技術

我們的第一步是利用恰當損失的結構。恰當損失的貝葉斯風險函數是凹的，并且對于正則恰當損失類，它允許一個多項式規模的分段線性上界近似（piecewise-linear upper approximation）。用這個上界近似替換貝葉斯風險函數，將每個預測的非線性損失貢獻轉化為一個線性表達式。這給出了一個線性目標，該目標給出了真實期望恰當損失的上界，且僅帶有加法近似誤差。第二步是通過源標記分解（source-labelled decomposition）來編碼布萊克韋爾占優。與其直接在任意輸出專家上進行優化，不如我們根據目標專家分裂出的預測分量來標記每個輸出預測。對于每個目標預測值，源標記的預測必須同時保持其概率質量和后驗均值。這兩個約束精確地表達了從目標專家的預測分布到輸出專家的預測分布的鞅耦合（martingale coupling）。根據布萊克韋爾占優的鞅刻畫，這保證了輸出專家弱布萊克韋爾占優目標專家。

通過可觀測二元向量的困難性。我們接下來解釋我們的確定性困難性結果背后的主要思想。關鍵的觀察結果是，確定性輸出專家施加了一個在隨機化模型中不存在的整數約束（integrality constraint）。一個確定性專家將狀態空間劃分為預測單元（prediction cells）。如果這樣的專家是可構建的，那么該劃分的每個單元必須是可觀測的：其二元指示向量必須位于由輸入專家生成的可觀測線性空間中。因此，確定性聚合等價于詢問可觀測線性空間是否包含有用的非平凡二元向量。

我們的困難性構造將這一二元向量要求歸約自子集和問題（SubsetSum problem）。從一個受限的子集和實例出發，我們構建一個僅有兩個輸入專家的聚合實例：一個專家是常數基準率專家，它也作為目標專家；另一個專家是精心設計的隨機化輔助專家。這兩個專家共同生成一個具有以下性質的可觀測線性空間：每個可觀測二元向量必須在兩個放大的狀態塊（amplified blocks）上是常數，并且一旦這兩個塊上的值被固定，剩余的可行性條件就精確地變成了一個子集和方程。

這一構造建立了一個直接的等價關系。當且僅當可觀測線性空間包含一個非平凡二元向量時，子集和解才存在。這樣的二元向量定義了一個非常數的確定性可構建專家。由于目標專家是常數基準率專家，任何具有相同均值的非常數校準專家都嚴格布萊克韋爾占優它。因此，判定常數目標專家是否允許確定性可構建改進已經是 NP 難的，即使只有兩個輸入專家和一個均勻先驗。

對于優化困難性，我們使用相同的構造，但利用放大的塊來創建一個常數布里爾損失差距（Brier-loss gap）。在 NO 實例中，可觀測線性空間不包含非平凡二元向量，因此每個確定性可構建專家必須是常數，并且具有等于基準率損失的布里爾損失。在 YES 實例中，子集和證書產生了一個雙單元確定性專家，其預測與基準率分離，并且放大的塊保證了嚴格更小的布里爾損失。該差距足夠大，以至于任何針對確定性OPT-AGGREGATION的乘法 PTAS 都能區分 YES 實例和 NO 實例，這意味著 P = NP。因此，確定性聚合不僅對搜索問題困難，而且對損失最小化也困難，即使是對于布里爾損失，即使是在高度受限的雙專家實例中也是如此。

1.3 更多相關工作

預測與信息聚合。預測聚合及其密切相關的公式已在多個學術社區中被研究，包括機器學習、統計學、經濟學和理論計算機科學。早期的基礎工作包括意見池（opinion pooling）和預測組合（forecast combination）[Sto61, BG69]，以及預測組合的經典綜述 [Cle89]。此后，更廣泛的文獻沿著不同的方法論方向發展。

在機器學習中，聚合通常通過集成方法（ensemble methods）進行研究，即結合多個預測器/分類器以提高預測性能。經典的例子包括堆疊（stacking）、裝袋（bagging）、提升（boosting）和隨機森林（random forests）[Wol92, Bre96, Sch90, Fre95, FS97, FHT00, Bre01, Die00]。一個相關的在線學習視角研究了帶有專家建議的預測（prediction with expert advice），其中乘權重類（multiplicative-weights-type）算法在結合專家預測的同時，相對于最佳固定專家實現低遺憾（low regret）[LW94, CBL06]。

在統計學中，預測聚合已從公理化和概率論兩個角度進行研究。公理化文獻對聚合規則施加了期望特性，如一致同意保持（unanimity preservation）和獨立性的變體，并在相應的假設下刻畫了線性或外部貝葉斯池化（externally Bayesian pooling）等規則 [AW80, Gen84, DL16]。概率論和貝葉斯文獻則建模預測如何從底層信號生成，然后通過貝葉斯更新或參數估計推導聚合規則；參見，例如，[SBF+14, FCK15, EPSU16, SPU16, RG10]。

這些文獻的一個共同特征是，報告的預測被解釋為由預測者信息誘導的概率信念（probabilistic beliefs）[Bor82, GBR07, SPU16, ABS18, GHH+25]。在這種解釋下，預測相對于預測者的信號是校準的：它代表在預測者可用信息條件下目標的后驗均值。在我們的設定中，我們也要求構建的預測是校準的，這也與這種標準的信念更新觀點相一致。

另一條相關路線研究基于共識的信息聚合（agreement-based information aggregation）：交換信念或預測并達成共識的代理人是否聚合了各代理人之間持有的信息，以及在什么條件下達成的共識與基于匯集信息的后驗信念一致或近似 [Aum76, Aar05, KS23, FNW23]。最近的工作還研究了計算上易于處理的共識和協作預測協議，其中代理人或模型迭代地交換預測或反饋以提高準確性，同時保持其底層信息私密 [CGGR25, CGHG+26]。我們的工作與之互補。我們沒有建模代理人之間的交互式信念交換或預測交換過程，而是將校準的專家及其報告規則作為輸入，并詢問哪些后驗一致的輸出專家可以僅使用這些輸入中包含的可觀測信息來構建和優化。

魯棒預測聚合。我們的工作涉及信息聚合問題。最近的一條文獻線在 [ABS18] 中首次引入，采取魯棒視角，要求在可能信息結構的大類中表現良好的聚合器，特別是當專家信號之間的相關結構未知或錯誤指定時。最近的工作研究了這種魯棒信息聚合問題的各種擴展和變體 [DOIL21, LR22, NR22, KWW24, GHH+25, GK25, FMNW25, CPT26]?；パa的一條路線利用二階或更高階信息（如代理人對他人答案的信念）來改善有限群體中的聚合 [Pre04, PSM17, PS19, WLC21, WMH22, PCK24, APSL+25]。

我們的工作在目標和信息約束上都與這些路線不同。我們不是設計一個將幾個報告的預測映射到單個聚合預測的規則，或者在損失或遺憾標準下評估這樣的規則，而是研究何時以及如何僅使用輸入專家預測中包含的可觀測信息來改進預測，而無法訪問底層的貝葉斯概率。另一個重要的區別是，魯棒聚合規則的輸出預測本身不必是貝葉斯后驗信念。相比之下，我們框架中構建的每個預測都要求是后驗一致的：每個報告的預測在每一個與輸入預測一致的潛在貝葉斯概率向量下都是有效的貝葉斯信念。這導致了一個獨特的可構建性問題：目標是從預測聚合轉向信息聚合，并在布萊克韋爾占優關系下刻畫和計算最大信息量的可構建輸出專家。我們在備注 3.4 中更詳細地討論了這些聯系。

信息結構上的優化。我們的工作也與信息設計和貝葉斯勸說（Bayesian persuasion）相關，其中設計者選擇信息結構以在貝葉斯合理性約束（Bayes plausibility constraint）下優化目標 [KG11, DX16, BM19]。越來越多的算法文獻研究了勸說及相關問題中信息結構優化的計算方面。與這些文獻類似，我們將預測視為信息結構，并在可行的后驗分布上進行優化。然而，我們問題中的約束本質上是貝葉斯合理性的反向類比：我們不是在所有貝葉斯合理的信息結構上進行優化，而是從觀察到的預測出發，詢問哪些更具信息量的預測可以僅從它們的可觀測線性信息中構建出來。

在概念上，我們的工作也與最近關于信息結構比較和交互的研究相關。[CW16] 研究了信息替代品和互補品，重點關注一個信號的邊際價值如何取決于其他信號的可用性，而 [BFK22, BFK24] 研究了信息層次結構或信號比較在決策環境和輔助信息中何時在魯棒意義上有效。這些工作比較給定的信息源或刻畫它們之間的魯棒排序；相比之下，我們的問題是建設性的：給定幾個觀察到的預測，我們詢問哪些更具信息量的預測可以僅使用它們的可觀測含義來生成和認證。最近關于校準優化（calibeating）的工作 [CHJL26] 也研究了如何后處理外部預測以獲得校準、信息量和恰當損失保證，但這是在在線學習設定中。

原文鏈接：https://arxiv.org/pdf/2607.08744https://arxiv.org/pdf/2607.08744