First analytical coverage bounds of a fully specified nested sampling algorithm

技術要約：完全に特定されたネステッド・サンプリング・アルゴリズムにおける初の解析的カバレッジ境界

問題提起
ネステッド・サンプリングは、ベイズモデル比較および事後分布推定のために設計されたモンテカルロ・アルゴリズムである。その核心的なメカニズムは、事前分布からサンプリングされた$K$個の「ライブ・ポイント」の集団を維持することである。各反復において、最も尤度が低い点が破棄され、破棄された点の尤度を上回るように制限された事前分布から新たに抽出されたサンプルによって置き換えられる。このアルゴリズムの計算上のボトルネックは、尤度制限付き事前分布サンプル（LRPS）を効率的かつ確実に生成することである。理想化されたLRPS手順を仮定した場合にはネステッド・サンプリングの収束証明が存在するが、実用的な実装は、そのカバレッジやバイアスに関する解析的特性がほとんど解明されていない特定のアルゴリズム（MCMCや領域ベースの手法など）に依存している。具体的には、実用的な、完全に特定されたアルゴリズムが、尤度制限付き事前空間のどの程度の割合をカバーできない可能性があるかについて、厳密な解析的境界はこれまで存在しなかった。

手法
本研究は、低次元から中次元の問題に適した領域ベースのLRPSアルゴングリズムであるMLFriendsに焦点を当てる。著者らは、MLFriendsの自己完結的な数学的定式化を提供し、特定のモデリング仮定の下でその性能に関するヒューリスティックな境界を導出している。

1. 再パラメータ化： 事前空間は、一様分布を持つ単位超立方体に変換される。
2. 点過程モデル： $K$個のライブ・ポイントは、尤度制限付き事前体積（$\Omega_{r\pi}$）内に一様かつ独立に分布する、均質な二項点過程としてモデル化される。
3. アルゴリズムのメカニズム： MLFriendsは、ライブ・ポイントの近傍を集約することで提案領域（$\Omega_P$）を構築する。また、$m$回のラウンドにわたるブートストラップ集約（bagging）手順を採用する。各ラウンドでは、訓練セットとなるライブ・ポイントが重複を許してサンプリングされ、除外された検証ポイントをカバーする「安全な」半径（$r_{train}$）が決定される。最終的な提案半径（$r_{max}$）は、これら$m$個の独立したラウンドにおける半径の最大値である。
4. 解析的手法： 著者らはブートストラップ半径の$d$乗の期待値を導出し、次いで、提案領域によってカバーされない尤度制限付き事前空間内の点の確率（$P_{missed}$）を導出する。これには、ブートストラップ集合の挙動を近似するために、ベータ分布および第2種スターリング数の性質を利用する。

主な貢献と結果
本論文は、漸近的または理想化されたサンプリング仮定に依存することなく、完全に特定された、実用的に実装可能なネステッド・サンプリング・アルゴリズムの最初の解析的特性を提示している。

• カバレッジ境界の導出： 共通の訓練セットから検証ポイントへの最近傍距離が独立であるという仮定（ヒューリスティックな仮定）の下で、著者らは、提案領域によってカバーされない尤度制限付き事前空間の期待される割合の上限を導出した。
  • この境界は $( \frac{1}{3}Km )^{-3/2}$ として減衰する。
  • 実用的なパラメータ選択（例：$K=1000, m=20$）の場合、この未カバーの割合は無視できるほど小さい（例：$\approx 2 \times 10^{-7}$）。
• バイアス解析： 著者らは、この未カバー領域が周辺尤度推定値（$\hat{Z}$）および事後分布サンプルに与える影響を分析している。
  • 周辺尤度： $\hat{Z}$における分数的なバイアスは $N( \frac{1}{3}Km )^{-3/2}$ によって抑えられることを示している（ここで$N$は反復回数）。このバイアスは、中規模から大規模な$K$および$m$に対して、推定器固有の統計的標準偏差（$\sqrt{N/K}$）と比較して無視できることが示されている。
  • 事後分布サンプル： 未カバー領域の欠落は、未カバーの体積に比例した事後分布質量の損失をもたらす。未カバー領域の尤度が系統的に平均より高いわけではないという仮定（仮定2）の下では、事後分布近似におけるバイアスも同様に無視できる。
• 体積増分： この分析により、制限付き事前分布の一部を欠落させても、推定される事前体積増分（$\Delta V_i$）は増大せず、むしろ、欠落した領域における尤度重み付き質量がサンプリングされないことにより、エビデンス推定に下方バイアスが生れることが明確にされている。

意義と主張
著者らは、これらの結果が、理想的な（あるいは漸近的な）サンプリング手順を仮定しない、完全に特定された実用的なネステッド・サンプリング・アルゴリズムの最初の解析的特性を提供するものであると主張している。

• 本研究は、理論的な収束証明（完全なLRPSを仮定するもの）と、実用的な実装との間のギャップを埋めるものである。
• 導出された境界は、有限のリソースを持つコンピュータ実装に対して「実用的に有用な信頼性推定」を提供する。
• 本論文は、そのアプローチの限界を明示的に認めている。すなわち、最近傍距離間の独立性とブートストラップ・ラウンドの独立性の仮定に基づいているため、結果は「ヒューリスティック」とラベル付けられている。次元や幾何学の関数としての明示的な誤差境界を伴う完全な厳密な取り扱いは、将来の研究における未解決問題として特定されている。
• 分析は、尤度がプラトー（平坦な領域）を持たず、パラメータ空間が一様事前分布に再パラメータ化可能であることを仮定している。また、マルチモーダルなケースは、クラスター検出（付録に記載）を通じてヒューリスティックに処理されることが記されているが、メインの導出では解析的には扱われていない。

要約すると、本論文は、MLFriendsアルゴリズムが、実用的なパラメータ選択の下では、得られるネステッド・サンプリングの推定値におけるバイアスが、アルゴリズムによる提案領域の近似よりも、その固有の統計的分散によって支配されるほど高い確率で、尤度制限付き事前分布をカバーしていることを確立している。