Nested sampling algorithm

Nested sampling algorithmとは、ベイズ統計におけるモデル比較、及び事後分布からのサンプル生成のための計算手法である。 2004年に物理学者のジョン・スキリング（John Skilling）によって開発された。 
背景.
ベイズの定理によれば、同時に真となることはない二つのモデルの組 formula_1に対し、データ formula_2 を観測した時のモデル formula_3 の事後確率は次のように計算できる：
ここで formula_3 と formula_6 に対する事前確率は既知であるとする。事後確率を求めるには残りのベイズ因子 formula_7 を求める必要があるが、一般にNuisance paramterを周辺化（積分）する必要があるため、評価はそれほど簡単ではない。一般にモデル formula_8 がパラメータ formula_9 （多次元であってもよく、モデルにより異なっても良い）を持つとき、 formula_10 の周辺化は次のようになる：
この積分はしばしば解析的に扱いにくいものであり、数値アルゴリズムを用い近似値を求める必要があります。Nested sampling algorithmは、特にこういった周縁化積分の近似計算のためにJohn Skillingによって開発され、積分計算と同時に事後分布 formula_12 からのサンプルが生成できるという追加の利点がある 。これはベイズ推定の観点からはブリッジサンプリングや防御的重要度サンプリングなどの方法に代わるものである。
Nested sampling algorithmの単純なバージョンは次のようになる。周辺確率密度 formula_13 は以下のように計算される：
 Start with formula_14 points formula_15 sampled from prior. 
 for formula_16 to formula_17 do  % The number of iterations j is chosen by guesswork.
 formula_18current likelihood values of the pointsformula_19; 
 formula_20 
 formula_21
 formula_22 
 Save the point with least likelihood as a sample point with weight formula_23.
 Update the point with least likelihood with some Markov chain Monte Carlo steps according to the prior, accepting only steps that 
 keep the likelihood above formula_24. 
 end 
 return formula_25;
各繰り返しステップにおいてformula_26は、 formula_27 における値より大きい尤度をもつようなパラメータ空間の体積の推定値である。重み formula_23 は2つの超曲面 formula_29 及び formula_30 の間の体積の推定値である。更新手順formula_31により、formula_32のformula_33による合計を計算することで、以下の積分を数値的に近似する：
formula_35 の極限でこの推定量にはformula_36の正のバイアスがあるが 、formula_37の代わりにformula_38を上記のアルゴリズムで用いることでこの誤差を取り除くことができる。
この計算手法の発想は、formula_39 の範囲を細分化し、各間隔 formula_40 ごとに、ランダムに選択された点 formula_9 がこの区間内に存在する確率を推定する、ということである。これはルベーグ積分を数値的に実装するベイズ流の方法と考えることができる。 
実装.
Nested sampling algorhithmの各プログラミング言語ごとの公開済み実装例は以下の通り。
応用.
Nested sampling algorithm は2004年に提案されて以来、天文学の分野の多くの側面で使用されており、宇宙論的モデルの選択と物体検出にも使用された。これは、「精度、一般的な適用性、および計算の実現可能性を併せ持っている」ためである。 多峰性事後確率を処理するためのアルゴリズムの改良が、現存するデータセット内の天体を検出する手段として提案されている。 Nested sampling algorithmの他の応用は、アルゴリズムを使用して最適な有限要素モデルを選択する有限要素更新の分野にあり、これは構造ダイナミクスに適用された。 このサンプリング方法は、材料モデリングの分野でも使用されている。統計力学から分配関数を学習し、熱力学的特性を導き出すためにも使用できる。 
動的 Nested sampling.
動的 Nested samplingは、Nested sampling algorithmの一般化であり、計算の精度が最大になるようにパラメータ空間のさまざまな領域で取得されるサンプルの数が動的に調整される。 これにより、サンプルの割り当てを変更できず、計算精度にほとんど影響を与えない領域で多くのサンプルが取得される、元のNested sampling algorithm と比較して、精度と計算効率が大幅に向上する場合がある。
公開されている動的Nested samplingのソフトウェアパッケージには、次のものがある。
動的Nested samplingは色々な科学分野で使用され、重力波検出、空間内の距離のマッピング 、太陽系外惑星の検出など、さまざまな科学的問題に適用されてきた。