(画面左下にMathJaxのタイプセットステータスが表示されます。)
環境によっては表示が崩れているかもしれません。その際はブラウザーを変更してみてください。
モンテカルロ法その他
「モンテカルロ法」では数値積分の一手法としてモンテカルロ法を紹介し、連続確率からサンプリングを行っていましたが、実はモンテカルロ法は離散確率による総和計算にも適用可能です。
統計における推定量は、その特性により偏／不偏、一致／不一致推定量(関数)といった呼ばれ方をします。
ここでは離散確率に対する適用と、推定量の特性について解説します。
離散確率への適用
\begin{equation*}
S = \sum_{j = 1}^{M} f \Prta{x_j}
\end{equation*}
積分の場合と同様に、ここでは1次元の総和問題を考えます。ここで $ M $ は離散事象の数( $ \geq 1 $ )で、積分範囲に対応する概念と言えます。例えば、1年間のうち月々の売り上げを合計する問題を考える場合は $ M = 12 $ となります。そして各事象(ある月) $ x_j $ に対する数値(売り上げ)が $ f \Prta{x_j} $ に対応します。
このような離散事象では、必要な計算点数が明確に決まっているため、全ての点に関して計算を行えば問題を正確に解くことができます。しかし計算点数が増えるに従い、処理時間も相応に増加するため、正確に解くことよりも大体の値を知る事の需要も出てきます。そういった場合にモンテカルロ法が使用できます。上記の総和問題を次のようにして求めます。
\begin{eqnarray}
\Abk{S} &=& \frac{M}{N} \sum_{i = 1}^{N} f \Prta{x_{j_i}} \label{eq:MC_d_uniform}
\end{eqnarray}
ここで $ j_i $ は $ 1 \sim M $ 中で、等しい確率で分布するそれぞれ独立な離散確率変数、$ x_{j_i} $ はそれに対応する数値、$ N $ はそのサンプル数です。連続の場合に対応して、この式も総和が対象とする範囲内における平均値を推定し、それに事象数をかけていると解釈できます。また同様に $ \Abk{S} $ は確率的な推定量であるため期待値の概念を持ち、次のように計算されます。
\begin{eqnarray*}
\mathbb{E} \Brk{\Abk{S}} &=& \mathbb{E} \Brk{\frac{M}{N} \sum_{i = 1}^N f \Prta{x_{j_i}}}
= \frac{M}{N} \sum_{i = 1}^N \mathbb{E} \Brk{f \Prta{x_j}} \\
&=& M \cdot \mathbb{E} \Brk{f \Prta{x_j}}
= M \cdot \sum_{j = 1}^M f \Prta{x_j} P \Prta{x_j} \\
&=& M \cdot \sum_{j = 1}^M f \Prta{x_j} \frac{1}{M}
= S
\end{eqnarray*}
半分くらい連続確率の式からのコピペで済みました。期待値が真値に等しい事がこのように証明できます。そして次はお察しの通り、式\eqref{eq:MC_d_uniform}の一般化です。ここまでは $ x_{j_i} $ を一様な分布として来ましたが、任意の分布、確率質量関数(probability mass function, PMF)を使用することができます。この場合のモンテカルロ推定量は次のようになります。
\begin{eqnarray*}
\Abk{S} &=& \frac{1}{N} \sum_{i = 1}^{N} \frac{f \Prta{x_{j_i}}}{P \Prta{x_{j_i}}}
\end{eqnarray*}
この式の分散に関しては上記の期待値のように、連続関数とほぼ同様の手順で求められるため省略しますが、分散と標準偏差の収束がそれぞれ $ N $ と $ \sqrt{N} $ に反比例することになります。
多次元総和への拡張や、分散低減手法である重点的サンプリングや層化サンプリングの考え方も同様に機能します。
無限和への適用
\begin{eqnarray*}
S &=& \sum_{i = 1}^{\infty} C_i
\end{eqnarray*}
通常の総和問題へモンテカルロ法が適用できることがわかりましたが、無限級数のような総和には適用できるのでしょうか。前節のようにランダムに事象(項)を選ぼうにも項数が無限にあるため選択が難しく、選ぶ確率(PMF)も極限的にゼロになってしまいます。無限級数が発散してしまう場合にはどうやっても正確な値を求めることができない、というか正確かつ明確な値なんてないので無視するとして、級数が収束する場合には多くの場合、最初の方の項ほど結果に対して大きな寄与を持つことに着目します。
ある程度から後ろの項を切り捨てて考えるのもひとつの手ですが、それでは期待値が真値からずれてしまいせっかくのモンテカルロ法の利点が消えてしまいます。そこで、前の項から順に値を計算する際に、逐次それ以降の計算を続行するかどうかの確率を導入します。その場合の推定量は次のようになります。
\begin{eqnarray*}
\Abk{S} &=& \sum_{i = 1}^{\infty} \frac{C_i}{\prod_{j = 1}^i P_j}
\end{eqnarray*}
この式の最初の数項を例にして説明します。最初の3項までを書き表すと次のようになります。
\begin{eqnarray*}
\Abk{S} &=& \frac{1}{P_1} \Brc{C_1 + \frac{1}{P_2} \Brc{C_2 + \frac{1}{P_3} \Brc{C_3 + \vphantom{\left\{ \frac{1}{P_4} \right.} \cdots}}}
\end{eqnarray*}
この式の第一項目の計算は確率 $ P_1 $ で実行され、$ C_1 \:/\: P_1 $ が結果に加算されるため、この項の期待値は $ C_1 $ となります。続く第二項目は確率 $ P_1 \cdot P_2 $ で実行され、$ C_2 \:/\: \Prta{P_1 \cdot P_2} $ が加算されるため、この項の期待値は $ C_2 $ となります。続く項も同様にして期待値が真値に一致します。結果として全体の期待値は真値に一致します。(厳密には上記の式には確率的に演算を続行するという手続きが書かれていないため表記としては間違っているかもしれません。詳しい方教えてください。)モンテカルロ法によって総和処理を途中で打ち切りつつ、期待値は真値に一致させたままにできます。
CGのレンダリングでは例えば、無限回の反射回数を扱いつつも処理を有限回数で打ち切り、期待値を真値に一致させるためにこの考え方を用います。
推定量の特性
推定量と求めたい真値との間の振る舞いで、以下の2つの特性が考えられます。
不偏推定量(Unbiased Estimator)
\begin{eqnarray*}
\mathbb{E} \Brk{\Abk{I}} - I = \varepsilon
\end{eqnarray*}
推定量 $ \Abk{I} $ の期待値と真値 $ I $ とのずれ $ \varepsilon $ を、推定量の偏り(bias)と呼びます。この偏り $ \varepsilon $ がゼロ、つまり推定量の期待値が真値に完全に一致する場合は、不偏推定量(Unbiased Estimator)と呼ばれます。
モンテカルロ法による推定量は基本的に不偏推定量と言えますが、そもそもその推定量が扱っている関数が、本当の関数と異なっている場合は、求めたい真値に対して偏りのある推定量となります。ただし、偏りのある推定量は必ずしも不偏推定量に劣るというわけではなく、時には偏りを持つ推定量のほうが良い推定をもたらすこともあります。
一致推定量(Consistent Estimator)
\begin{eqnarray*} \lim_{N \to \infty} \Prtb{\Abk{I} - I} = 0 \end{eqnarray*} サンプル数を無限に増やしたときに、推定量が完全に真値に一致する場合、一致性(Consistency)を持つと言います。また、一致性を持つ推定量のことを一致推定量(Consistent Estimator)と呼びます。もちろん推定量が真値に一致するためには偏りも極限ではゼロにならなければなりません。逆に言えば極限で偏りがゼロになり、推定値も収束するのであれば、偏りを持っている推定量でも一致性を満たします。
偏／不偏、一致／不一致推定量の例
\begin{eqnarray*} I = \int_a^b f \Prta{x} \d x \end{eqnarray*} 上記のような極々簡単な積分問題を考えます。積分区間 $ \Brk{a, b} $ 内で一様乱数を $ N $ 個発生させ、それによってサンプリングした値から推定量を構築してみます。偏りの有無、一致性の有無の組み合わせから、例えば以下のような4つの推定量が考えられます。 \begin{eqnarray*} \mbox{不偏かつ一致性を持つ：}\Abk{I} &=& \frac{b - a}{N} \sum_{i = 1}^N f \Prta{x_i} \\ \mbox{不偏かつ、一致性を持たない：}\Abk{I} &=& \frac{b - a}{2} \Brcb{f \Prta{x_1} + f \Prta{x_N}} \\ \mbox{偏りを持ち、一致性を持つ：}\Abk{I} &=& \frac{b - a}{N} \Brcb{ \sum_{i = 1}^N f \Prta{x_i} + A} \\ \mbox{偏りを持ち、一致性を持たない：}\Abk{I} &=& \frac{b - a}{N} \sum_{i = 1}^N f \Prta{x_i} + A \end{eqnarray*} ここで、$ A $ は非ゼロの定数とします。実はモンテカルロ法自体は確率変数を使って数値計算を行う手法の総称なので、上のいずれもモンテカルロ推定量と呼べます。一般的にモンテカルロ積分と言えば一番上のもので、この場合は不偏性も一致性も持っています。2段目はある意味いくらサンプルを採ろうとも、サンプル数が2から増えないような状態です。少し強引と感じるかもしれませんが、この場合は不偏性は明らかに持っているものの、結果は真値に収束しません(定数関数ならば話は別ですが)。3段目は推定量の偏りとして、$ \Prta{b - a} \cdot A \:/\: N $ を持ちますが、サンプル数が無限大となればゼロに収束するため一致性を持ちます。そして最後の4段目はサンプル数によって消えきらない偏りを持っているため、一致性は持ちません。
これはほんの一例ですが、偏りと一致性は別の概念ということの説明でした。もう一度書いておくと、偏りを持つ推定量は必ずしも悪いものではありません。ただ、一致性を持たない推定量はまず良いものとは言えないでしょう。