Optimally-Weighted Herding is Bayesian Quadrature

問題提起
統計的機械学習における根本的な課題は、確率分布に対する関数の期待値 $Z_{f,p} = \int f(x)p(x)dx$ を計算することである。モンテカルロ法はランダムサンプリングを通じてこれを近似するが、収束率は $O(1/\sqrt{N})$ であり、確率的な分散の問題を抱えている。一方で、準モンテカルロ法（Quasi-Monte Carlo methods）は、擬似サンプルを生成することで、サンプルの経験的分布とターゲット分布 $p(x)$ の間のディスクレパンシー（不一致）を最小化する決定論的な代替案を提供する。代表的な2つの決定論的手法として、最大平均偏差（MMD）を最小化するようにサンプルを選択するカーネルハーディング（Kernel Herding）と、被積分関数 $f$ に対して事後分布を推論するベイズ量子化（Bayesian Quadrature: BQ）がある。本論文では、これら2つの手法間の理論的な関連性を解明し、重み付きのサンプル選択アプローチが標準的なハーディングを凌駕し得るかどうかを調査する。

手法
著者らは、各手法が最小化する目的関数を分析することで、カーネルハーディングとベイズ量子化の間の理論的な結びつきを確立している。

1. 基準の等価性： 本論文では、カーネルハーディングで最小化される基準（MMD）が、関数 $f$ にガウス過程（GP）事前分布を仮定した場合の、ベイズ量子化における積分推定値の事後分散と数学的に等価であることを示している。具体的には、BQにおける期待誤差は、ターゲット分布 $p$ と、サンプルおよびその重みによって定義される離散分布との間のMMDに対応する。
2. 逐次ベイズ量子化（Sequential Bayesian Quadrature: SBQ）： 標準的なハーディングがサンプルに一様重み（$1/N$）を割り当てるのに対し、BQはGP事後分布から導出された最適な重みを割り当てる。著者らは、事後分散を最小化（これは最適な重みを用いたMMDの最小化に相当する）するようにサンプル位置を選択する強欲（greedy）アルゴリズムである、逐次ベイズ量子化（SBQ）を提案する。
3. 重みの分析： 本論文ではBQの重みの特性を分析しており、それらが必ずしも正ではなく、合計が1になるとは限らないことを指摘している。これらの重みは、定義された再生核ヒルベルト空間（RKHS）において、ミニマックスの意味で最適であることが示されている。
4. 劣モジュラ性： 著者らは、SBQの収束特性を、スパースな辞書選択問題に関連付けることで調査している。彼らは、目的関数が「近似的に劣モジュラ（approximately submodular）」であることを証明しており、これにより、厳密な劣モジュラ関数に対するものよりは弱いものの、強欲な選択戦略の性能に関する理論的な境界を確立している。

主な貢献

1. 理論的統一： 本論文は、カーネルハーディングによって最小化される損失が、ベイズ量子化における期待誤差（事後分散）と同一であることを証明している。その結果、BQは、与えられたRKHSに対して最適な重みを持つ、重み付きのカーネルハーディングとして位置付けられる。
2. 重みの最適性： BQから導出される重みが、一様重みのハーディングやその他の非最適に重み付けされたハーディング手法よりも、収束率の観点で優れていることを示している。
3. アルゴリズム的接続： 本研究は、BQにおけるサンプルの強欲な選択を、スパースな辞書選択問題へと結びつけ、その目的関数が近似的に劣モジュラであることを確立している。
4. 実証的検証： 著者らは、SBQが最大平均偏差および積分推定誤差の両方において、$O(1/N)$ よりも速い収束率を達成することを示す実証的な証拠を提示している。

結果

• 収束率： 2次元混合ガウス分布を用いた実験において、SBQは、有限次元空間におけるハーディングに典型的な $O(1/N)$ の収束率を上回る収束率を示した。SBQの無限次元空間における正確な理論的収束率は未知であるが、実験結果は $O(1/N)$ よりも高速であることを示唆している。
• サンプル効率： 本論文は、少数のSBKサンプル（例：8個）と最適重みを用いることで、より多くのハーディングサンプル（例：20個）と一様重みを用いる場合と同等の推定誤差を達成できることを示している。
• 堅牢性： 仮定されたRKHSの外側にある関数を用いた実験では、理論的な保証は関数がRKHSに属していることに依存するものの、手法間の相対的な性能順位（SBQ > Herding > i.i.d.）は、「モデル外」の関数に対しても一貫していることが示された。
• 誤差境界： MMDは、BQ推定値の経験的誤差に対する証明可能な上界を提供し、それがサンプル数の増加とともに急速に減少することが示された。

意義と主張
本論文は、逐次ベイズ量子化が、サンプル選択プロセスに最適な重み付けを統合することにより、カーネルハーディングに対して重要な進歩をもたらすと主張している。BQを「最適に重み付けされたハーディング手法」と捉えることで、著者らは、BQの優れた性能を説明する統一的な理論的枠組みを提供している。本研究は、BQが重みの計算において $O(N^3)$ の計算コストを要する（ハーディングの $O(N^2)$ に対して）一方で、その速い収束率により、関数の評価が高コストなシナリオにおいてより効率的になる可能性があることを強調している。著者らは、経験的誤差の上界を確立し、$O(1/N)$ より速い収束を実証したものの、無限次元空間におけるSBQの理論的に最適な収束率は、将来の研究における未解決の課題であると控えめに述べている。結論として、手法の選択は、計算コストと被積分関数 $f$ の評価コストの間のトレードオフに依存すると述べている。