\def\vector#1{\boldsymbol{#1}}

\newcommand{\argmax}{\mathop{\rm arg~max}\limits}

最大エントロピー法

2018年5月10日 #NLP #MaximumEntropy

概要

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

例えば「A さんと B さんのどちらが柔道経験者か」という問いに対して、どちらの人物の情報も与えられていないのに「A は 80%、B は 20%」と判断することは不自然だし「A も B も 50% (どちらとも言えない)」の判断の方がより妥当に感じるだろう。情報理論の観点では明確な偏りがあることはエントロピーが低いことから、この考えは条件の中で最もエントロピーの高い選択肢 (余計なバイアスを含まない選択肢) が採用されるべきという原理に従っていることがわかる。

例 : 赤、青、緑の 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*}$ つまり、何の条件も与えられず $n$ 個の選択肢が与えられただけあれば、(最大エントロピーモデルに従えば) 全ての $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) ということになる。

参照

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

最大エントロピー法

概要

​​次元事象系での最大エントロピー

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

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

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

参照

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