\( \def\vector#1{\boldsymbol{#1}} \) \( \newcommand{\argmax}{\mathop{\rm arg~max}\limits} \)

最大エントロピー法

Takami Torao #NLP #MaximumEntropy
  • このエントリーをはてなブックマークに追加

概要

最大エントロピー法 (maximum entropy model) は前提条件だけで明確な確率分布を導き出せない事象に対して、全体のエントロピーが最大化する方向に確率分布を割り当てる方法。条件が設定されていないのであれば、条件外の余計な偏りを含まない最も不確かなモデルが採用されるべきという考え方に基づく。

: 赤、青、緑の 3 種のボールがそれぞれたくさん入った袋から一つ取り出して戻す実験について考える。ただし、取り出した時に確認できるのはボールが赤か赤でないかだけである。1000 回の試行で赤いボールが 500 回の出たとき、袋の中に入っている赤、青、緑それぞれのボールの割合をどう想定すればよいだろうか?

観測結果から分かっている条件は赤の確率が 0.5 であること (そして確率の合計が 1.0 であること) だけである。青、緑のボールについては何の言及もないため可能な確率の組み合わせは無限に想定することができる。例えば青 0.3, 緑 0.2 や青 0.1, 緑 0.4 は可能な割り当ての例である。

ここで、青と緑のボールに何の前提も存在ないのだから青 0.25, 緑 0.25 と均等に割り当てることが妥当であろうという直感的な発想は、想定にない偏りを排除した最も不確かなモデル (全体のエントロピーが最も大きいモデル) を割り当てすることと一致する。

\(n\)次元事象系での最大エントロピー

\(n\) 個の事象のいずれかが発生する確率について考える (このような確率はカテゴリカル分布に従う; 前述のカラーボール取り出し例は \(n=3\) であり、6面サイコロは \(n=6\) である)。それぞれの事象の出現確率を \(p_i\) とした場合、エントロピーは以下のように表される。\[ H = - \sum_{i=1}^n p_i \log p_i \] エントロピー \(H\) の最大値を求めるにはラグランジュの未定乗数法を使用することができる。\[ \begin{eqnarray*} L & = & - \sum_{i=1}^n p_i \log p_i + \lambda \left( 1 - \sum_{i=1}^n p_i \right) \\ \frac{\partial L}{\partial p_i} & = & - \log p_i + 1 - \lambda = 0 \\ p_i & = & e^{1-\lambda} \end{eqnarray*} \] より、全ての \(p_i\) は同じ定数を取ることが導かれる。また、\[ \begin{eqnarray*} \frac{\partial L}{\partial \lambda} & = & 1 - \sum_{i=1}^n p_i = 0 \\ \sum_{i=1}^n p_i & = & 1 \end{eqnarray*} \] より、\(p_1 = p_2 = \ldots = p_n = \frac{1}{n}\) の場合にエントロピーが最大値となることが分かる。

\(p_i\) に観測によって分かっている確率が含まれている場合、残りの確率を均等に割り当てた結果となることに注意。

例1: 偏りのない6面サイコロ

サイコロの各面を \(i\) としたとき: \[ \begin{eqnarray*} L & = & - \sum_{i=1}^6 p_i \log p_i + \lambda (1 - \sum_{i=1}^6 p_i) \\ \frac{\partial L}{\partial p_i} & = & - \log p_i + 1 - \lambda = 0, \ \ \therefore p_i = C \\ \frac{\partial L}{\partial \lambda} & = & 1 - \sum_{i=0}^n p_i = 1 - 6 C = 0, \ \ \therefore C = \frac{1}{6} \end{eqnarray*} \] より、全ての確率が \(p_i = \frac{1}{6}\) の時に全体のエントロピーが最大値となる。

例2: 赤、青、緑のボール取り出し

赤=1、青=2、緑=3 とし \(p_1=0.5\) の条件の下でエントロピーが最大となる \(p_i\) は: \[ \begin{eqnarray*} L & = & - 0.5 \log 0.5 - \sum_{i=2}^3 p_i \log p_i + \lambda (1 - 0.5 - \sum_{i=2}^3 p_i) \\ \frac{\partial L}{\partial p_i} & = & - \log p_i + 1 - \lambda = 0, \ \ \therefore p_2 = p_3 = C \\ \frac{\partial L}{\partial \lambda} & = & 0.5 - p_2 - p_3 = 0.5 - 2C = 0, \ \ \therefore C = \frac{0.5}{2} \end{eqnarray*} \] よって \(p_2 = p_3 = 0.25\) の時にエントロピーが最大値となることがわかる。

例3: 確率分布が既知のエントロピー算出

\(n=3\) の確率がそれぞれ \((0.5, 0.2, 0.3)\) と分かっている場合のエントロピーは: \[ H = - 0.5 \log 0.5 - 0.2 \log 0.2 - 0.3 \log 0.3 = 0.4472 \] である。また \(p_1 = 1\) で他が 0 の場合: \[ H = - 1 \times \log 1 - 0 \times \log 0 - 0 \times \log 0 = 0 \] 試行の結果は赤のみとなるためエントロピーは 0 (つまり不確かさは 0) ということになる。

参照

  1. 最大エントロピー原理
  2. Ratnaparkhi (1997), A Simple Introduction to Maximum Entropy Models for Natural Language Processing (日本語訳)