Digital Reactor
モンテカルロ法

モンテカルロ法における次元の呪いの緩和方法：重点サンプリングによる効率化

モンテカルロ法における次元の呪いの緩和方法：重点サンプリングによる効率化

はじめに

積分を数値的に求めるとき、格子状に評価点を並べる方法は次元が上がった途端に破綻します。各次元にたった10点ずつ取るだけでも、10次元では評価点が 101010^{10} 個に達するからです。そこで乱数によるサンプリングで数値積分や期待値を近似するモンテカルロ法の出番になりますが、こちらも次元の増加と無縁ではありません。次元が上がると、同じ精度に必要なサンプル数が指数関数的に膨らみます。「次元の呪い（Curse of Dimensionality）」と呼ばれる現象です。この記事では緩和手法を一覧で比べたうえで、重点サンプリング（Importance Sampling）を実装し、次元数を変えて効果を確かめます。

対象読者:

  • モンテカルロ法を学び始めたばかりの初心者
  • 高次元の数値計算に関心のあるエンジニア、研究者
  • 確率モデルやシミュレーションに携わる方

記事のポイント:

  • 次元の呪いとその影響を具体的に理解できる
  • 重点サンプリングの原理と実装方法を学べる
  • 他の緩和手法と比べたときの重点サンプリングの位置づけがわかる
  • Pythonコードによる実装例で、実際に試せる

次元の呪いの緩和手法比較

次元の呪いへの対策は一つではありません。主な緩和手法を表にまとめます。

手法概要
重点サンプリング（Importance Sampling）被積分関数が大きな値を取る領域に多くのサンプルを配置します。目的の関数の形に近い提案分布からサンプルを生成し、分布の違いは重みで補正します。分散を大きく削減でき理論的な収束保証もありますが、効果は提案分布をうまく設計できるかどうかに左右されます。
層化サンプリング（Stratified Sampling）積分領域を複数の小領域（層）に分割し、各層から所定の数のサンプルを取ります。層ごとの重要度に応じてサンプル数を配分すれば分散を確実に減らせて、実装も比較的容易です。ただし次元が高くなると層の数が急増し、分割の設計も難しくなります。
準モンテカルロ法（Quasi-Monte Carlo Method）乱数の代わりに、空間を均一に埋めるよう設計された決定論的な数列（低不一致列）を使います。Halton列やSobol列が代表的です。収束が速く再現性もありますが、乱数の独立性が失われ、高次元では数列の生成コストが増えます。
適応的サンプリング（Adaptive Sampling）サンプリングの途中で得た情報をもとに、次にどこを調べるかを動的に更新します。事前知識なしで自動的に効率化できる一方、計算コストが高く、収束判定が難しくなります。
マルチレベル法（Multilevel Method）粗い近似と詳細な計算を階層的に組み合わせ、重要な領域だけを詳細に計算します。計算コストを大きく削減でき並列化も容易ですが、実装が複雑で、問題ごとの設計が要ります。
ラテン超格子サンプリング（Latin Hypercube Sampling）各次元を均等に分割し、どの次元でも各区間から1点ずつ取るようにサンプル点を配置します。空間を均一に覆いつつ次元間の相関も考慮できますが、高次元では配置の最適化が難しく、非直交領域では効率が落ちます。
MCMC法（Markov Chain Monte Carlo）マルコフ連鎖で現在の点から次の点へ確率的に移動しながらサンプルを集めます。メトロポリス法は提案分布から生成した候補点の採否を受容確率で決め、ギブスサンプリングは各方向を順番に更新します。複雑な分布にも使え理論的保証もありますが、収束に時間がかかり、サンプル間に相関が残ります。
次元削減（Dimensionality Reduction）主成分分析（PCA）などで問題の本質的な低次元構造を取り出してから計算します。計算量を大幅に減らせて解釈もしやすくなりますが、情報を落とす可能性があり、非線形な構造は捉えにくくなります。
スパースグリッド法（Sparse Grid Method）格子点を疎に配置し、重要な領域だけ格子を細かくします。少ない点で空間を覆え、精度も適応的に上げられますが、実装が複雑で、滑らかでない関数では性能が落ちます。
ガウス過程回帰（Gaussian Process Regression）少数の評価点から確率的な補間モデルを作り、不確実性も含めて全体を推定します。不確実性を定量化でき滑らかな補間もできますが、計算コストが高く、カーネル関数の選択が結果を左右します。

重点サンプリングの実装

この中から重点サンプリングを取り上げます。被積分関数がどこに集中しているか見当のつく問題では効果が大きく、実装も短く済むからです。重点サンプリングでは、被積分関数が大きな値を取る領域に集まるような確率分布（提案分布、proposal distribution）からサンプルを生成し、目的の分布と提案分布の密度の比を重みとして掛けて補正します。効果を確かめる題材として、次の多次元積分を使います。

I=∫[0,1]dexp⁡(−∑i=1dxi2)dxI = \int_{[0,1]^d} \exp(-\sum_{i=1}^d x_i^2) dx

被積分関数は原点付近で大きな値を取り、外側に向かって急速に減衰します。一様にサンプルを打つと、値がほとんどゼロの領域に大半のサンプルを費やすことになり、次元 dd が大きいほどこの無駄が積み重なって効率が落ちます。

原点に集中する被積分関数

2次元の場合の被積分関数の形状は次のとおりです。

同じ関数を等高線で描くと、値の偏りがはっきり見えます。

値は原点付近に集中しています。この形なら、原点付近に多くのサンプルを置く提案分布が有効に働くはずです。

サンプル点の配置がどう変わるか

通常のモンテカルロ法と重点サンプリングで、サンプル点の分布がどう変わるかを比較します。

左図は通常のモンテカルロ法による一様サンプリング、右図は重点サンプリングによる切断正規分布からのサンプリングです。重点サンプリングでは、被積分関数の値が大きい原点付近にサンプル点が寄っています。

実装は次のとおりです。

import numpy as np

def standard_mc(d, n_samples):
    """通常のモンテカルロ法による多次元積分"""
    samples = np.random.uniform(0, 1, (n_samples, d))
    values = np.exp(-np.sum(samples**2, axis=1))
    return np.mean(values), np.std(values) / np.sqrt(n_samples)

def importance_sampling(d, n_samples):
    """重点サンプリングによる多次元積分
    提案分布として切断正規分布を使用"""
    # 切断正規分布からサンプリング
    samples = np.abs(np.random.normal(0, 0.5, (n_samples, d))) % 1

    # 重みの計算
    # p(x): 目的の関数 exp(-sum(x_i^2))
    # q(x): 提案分布（切断正規分布）の確率密度
    p = np.exp(-np.sum(samples**2, axis=1))
    q = np.prod(np.exp(-(samples - 0)**2 / (2 * 0.5**2)) /
               (0.5 * np.sqrt(2 * np.pi)), axis=1)

    weights = p / q
    return np.mean(weights), np.std(weights) / np.sqrt(n_samples)

standard_mc は一様分布から各次元の座標をサンプリングし、サンプル点での関数値の平均と標準誤差を返します。importance_sampling は平均0、標準偏差0.5の正規分布からサンプリングし、絶対値を取って1の剰余を計算することで積分領域の [0,1][0,1] に収めます。そのうえで重み p(x)/q(x)p(x)/q(x)（pp は目的の関数、qq は提案分布の確率密度）を求め、重み付き平均と標準誤差を返します。標準偏差の0.5は被積分関数の減衰の速さに合わせた値で、大きくしすぎると一様サンプリングに近づいて利点が消え、小さくしすぎると裾のサンプルが不足して重みが不安定になります。

次元が上がるほど差が開く

次元数dd = 2, 5, 10について、サンプル数を変えながら通常のモンテカルロ法と重点サンプリングの精度を比較しました。

次元数が増えるほど、通常のモンテカルロ法の精度は急速に落ちます。次元の呪いの典型的な現れです。重点サンプリングの改善幅は高次元（dd=10）でとくに大きく、同じ精度を得るために必要なサンプル数は通常のモンテカルロ法の1/5から1/10程度で済んでいます。低次元（dd=2）では両手法の差は小さくなります。一様サンプリングでも領域を十分に探索できるためです。

まとめ

高次元の積分で通常のモンテカルロ法の精度が頭打ちになったら、まず被積分関数がどこに集中しているかを確かめる価値があります。今回の題材のように集中する場所が分かっている問題なら、その形に合わせた提案分布を用意するだけで、必要なサンプル数を1桁近く減らせます。裏を返せば、重点サンプリングの効果は提案分布の質で決まります。集中する場所の見当がつかない問題では、層化サンプリングや準モンテカルロ法のように、関数の形への依存が小さい手法から試すほうが無理がありません。手元の問題を次元数と被積分関数の形で整理し、比較表のどの手法が合うかを当てはめるところから始めてみてください。

関連記事

← 技術ブログ一覧へ