論文翻訳: A Simple Introduction to Maximum Entropy Models for Natural Language Processing

Adwait Ratnaparkhi
Dept. of Computer and Information Science
University of Pennsylvania
adwait@unagi.cis.upenn.edu
May 13, 1997

Abstract

自然言語処理における多くの問題は、言語学的文脈を用いて言語学的クラスを予測する言語学的分類問題と考えることができる。最大エントロピーモデルは特定の言語学的コンテキストで発生する特定の言語学的クラスの確率を推定するために、様々な文脈的根拠を組み合わせるクリーンな方法を提供する。このレポートでは例問題で特定の最大エントロピーモデルを使用して、そのモデルに関するいくつかの関連する数学的事実を簡単かつアクセス可能な方法で証明する。またこのレポートでは特定のモデルのパラメータを推定する一般化反復スケーリング (Generalized Iterative Scaling) と呼ばれる既存の手順も記載している。このレポートの目的は [Ratnaparkhi, 1996, Reynar and Ratnaparkhi, 1997, Ratnaparkhi, 1997] に記載されている最大エントロピーモデルを再現するために十分な詳述を提供することであり、最大エントロピー形式論の簡単な説明も提供することである。

Table of Contents

1. Abstract
2. 1 Introduction
3. 2 Representing Evidence
4. 3 A Simple Example
5. 4 Preliminaries
6. 5 Maximum Entropy
7. 6 Maximum Likelihood
8. 7 Parameter Estimation
   1. 7.1 Computation
9. 8 Conclusion
10. References
11. 翻訳抄

1 Introduction

自然言語処理 (NLP) における多くの問題は統計的分類問題として再定式化することができ、そのタスクは "コンテキスト" \(b\) で "クラス" \(a\) が起きる確率 \(p(a, b)\) を推定することである。通常、NLP タスクのコンテキストには単語が含まれており、正確なコンテキストはタスクの性質に依存している。いくつかのタスクではコンテキスト \(b\) はただ一つの単語で構成され、他のコンテキストでは \(b\) はいくつかの単語とそれに関連する構文ラベルで構成される。通常ラージテキストコーパスは \(a\) と \(b\) の共起についての情報を含んでいるが、一般的に \(b\) の単語は疎であるため、可能なすべての \((a,b)\) ペアに対して \(p(a,b)\) を完全に指定することは決して十分ではない。問題は \(a\) と \(b\) についての疎エビデンス (sparse evidence) を用いて、確率モデル \(p(a,b)\) を確実に推定する方法を見つけることである。

Principle of Maximum Entropy [Jaynes, 1957, Good, 1963] について考える。これは真の分布 \(p(a,b)\) が "エビデンス"、つまり実験者が得ている観測値の観測条件下でエントロピーまたは "不確かさ" を最大にするものであると述べている。[Janyes, 1957] ではその利点について論議している:

...部分的な情報に基づいて推論を行う際には、既知のものに従属する最大エントロピーを持つ確率分布を使用しなければならない。これは我々が使うことのできる唯一の偏りのない割り当てである; 他のいかなるものも、我々が持ち合わせていない仮説の情報によって恣意的な仮定となりうる。

より明示的には、とりうるクラスの集合を \(\mathcal{A}\)、とりうるコンテキストの集合を \(\mathcal{B}\) とした場合、\(p\) はエントロピー \[ H(p) = - \sum_{x \in \mathcal{E}} p(x) \log p(x) \] を最大にならなければならない。ここで \(x = (a, b)\), \(a \in \mathcal{A}\), \(b \in \mathcal{B}\), \(\mathcal{E} = \mathcal{A} \times \mathcal{B}\) であり、エビデンスや "部分的な情報" と一貫していなければならない。以下に論じるエビデンスの表現は \(p\) の形を決定する。

2 Representing Evidence

エビデンスを表現する方法の一つは有用な観測値を特徴としてエンコードし、それらの特徴の期待値に条件を課すことである。特徴は事象のバイナリ値関数: \(f_j: \mathcal{E} \to \{0,1\}\) (訳注: 事象が発生した/しなかった) である。\(k\) 個の特徴を与えたとき、条件は \[ \begin{equation} E_p f_j = E_{\tilde{p}} f_j \label{prob} \end{equation} \] の形をとる。ここで \(1 \leq j \leq k\) である。\(E_p f_j\) はモデル \(p\) の \(f_j\) の期待値であり: \[ E_p f_j = \sum_{x \in \mathcal{E}} p(x) f_j(x) \] 観測された期待値 \(E_{\tilde{p}} f_j\): \[ E_{\tilde{p}} f_j = \sum_{x \in \mathcal{E}} \tilde{p}(x) f_j(x) \] と一致するよう制約付けられている。ここで \(\tilde{p}\) はある訓練サンプル \(S\) において \(x\) に観測された確率である。このとき、モデル \(p\) は (\(\ref{prob}\)) で示された \(k\) 制約を満たす場合に限り観測されたエビデンスと一致する。The Principal of Maximum Entropy では一貫したモデル \(P\) のセットに対するエントロピーを最大にすることから \(p^*\) を使用することを推奨している \[ \begin{eqnarray*} P & = & \{p | E_p f_j = E_{\tilde{p}} f_j, \ j = \{1...k\}\} \\ p^* & = & \argmax_{p \in P} H(p) \end{eqnarray*} \] 5 章では \(p^*\) が以下の式とならなければならないことを示している: \[ \begin{equation} p^*(x) = \pi \prod_{j=1}^k \alpha_j^{f_j(x)}, \ \ 0 \lt \alpha_j \lt \infty \label{paster} \end{equation} \] ここで \(\pi\) は正規化定数、\(\alpha_j\) はモデルパラメータである。それぞれの \(\alpha_j\) パラメータはちょうど 1 つの \(f_j\) に対応し、その特徴の "重み" とみなすことができる。

3 A Simple Example

以下の例に非常に簡単な問題での最大エントロピーの使用を示す。確率分布 \(p(a,b)\) を推定することを考える。ここで \(a \in \{x,y\}\), \(b \in \{0,1\}\) とする。また、\(p\) に関して分かっている唯一の観測値として \(p(x,0) + p(y,0) = .6\) とする (条件 \(\sum_{a,b} p(a,b) = 1\) は \(p\) が確率分布であることから自明である)。Table 1 は "?" でラベル付けされた 4 つのセルで \(p(a,b)\) を表し、その値は条件と一致しなければならない。Table 1 のセルを満たす条件は明らかに (無限というほど) 数多く存在している。Table 2 はそのような方法の 1 つを示している。しかしながら、The Principal Maximum Entropy は Table 3 の割り当てを推奨する。これは \(p\) の条件を満たす確率の最も曖昧な (most non-committal) 割り当てである。

数式的に、最大エントロピーフレームワークの下で、観測値: \[ p(x,0) + p(y,0) = .6 \] はモデル \(p\) の特徴 \(f\) の期待値の制約として実装される: \[ \begin{equation} E_p f = .6 \label{prob6} \end{equation} \] ここで \[ E_p f = \sum_{a \in \{x,y\}, b \in \{0,1\}} p(a,b) f(a,b) \] であり、ここで \(f\) は以下のように定義される: \[ f(a, b) = \left\{ \begin{array}{ll} 1 & \mbox{ if } b = 0 \\ 0 & \mbox{otherwise} \end{array} \right. \] \(f\) の観測期待値、または \(E_{\tilde{p}} f\) は .6 である。目的は制約 (\(\ref{prob6}\)) を条件に \[ H(p) = - \sum_{a \in \{x,y\}, b \in \{0,1\}} p(a,b) \log p(a,b) \] を最大化することである。

特徴 \(f\) が常に事象 \((a,b)\) を 0 または 1 にマップすると仮定すると、特徴の期待値に対する制約は事象空間を表す表内の特定のセルの合計に対する制約に過ぎない。上記のような制約付き最大エントロピー問題は (インスペクションによって) 努力を要することなく解くことができるが、複数の制約が閉じた数式の解を禁止する方法を重複する可能性があるため、通常はより大きな問題には反復手続きが必要となる。

一般的に特徴は言語的文脈における何かと特定の予測の間の共起関係を表している。例えば [Ratnaparkhi, 1996] は、\(a\) を取りうる品詞タグ、\(b\) をタグ付けされる単語を含む (他のものの中でも) ようなモデル \(p(a,b)\) を推定している。有用な特徴は以下のようになるだろう。\[ f_j(a,b) = \left\{ \begin{array}{ll} 1 & \mbox{if } a = {\tt DETERMINER} \mbox{ and } {\it currentword}(b) = \mbox{"that"} \\ 0 & \mbox{otherwise} \end{array} \right. \] この特徴の観測期待値 \(E_{\tilde{p}} f_j\) は、学習サンプルの数に渡って正規化された、学習サンプル中の \({\tt DETERMINER}\) というタグで "that" という単語を検出することが予想される回数である。

最大エントロピーフレームワークの利点は、実験者はどのような特徴を使用するかを決めることに集中するだけでよく、使用方法に焦点を合わせる必要がないということである。各特徴 \(f_j\) が \(p(a,b)\)、つまりその "重み" \(\alpha_j\) に寄与する程度は、Generalized Iterative Scaling アルゴリズムに寄って自動的に決定される。さらに、[Ratnaparkhi, 1996] のモデルではタグ bigram と単語接頭辞だけでなく単一の文言を検査するように、あらゆる種類の文脈的特徴をこのモデルで使用することができる。

4 章は予備定義を議論し、5 章は数式 (\(\ref{paster}\)) のモデルの最大エントロピー特性を議論し、6 章は最尤推定との関係を論じ、7 章は Generalized Iterative Scaling アルゴリズムを述べる。

4 Preliminaries

定義 1 と 2 は相対エントロピーとある関連する表記法を導入する。補題 1 と 2 は相対エントロピー指標の特性を詳述する。

Definition 1 (Relative Entropy, or Kullback-Liebler Distance).

\[ D(p, q) = \sum_{x \in \mathcal{E}} p(x) \log \frac{p(x)}{q(x)} \]

Definition 2

\[ \begin{eqnarray*} \mathcal{A} & = & \mbox{set of possible classes} \\ \mathcal{B} & = & \mbox{set of possible contexts} \\ \mathcal{E} & = & \mathcal{A} \times \mathcal{B} \\ \mathcal{S} & = & \mbox{finite training sample of events} \\ \tilde{p}(x) & = & \mbox{observed probability of }x\mbox{ in }S \\ p(x) & = & \mbox{the model }p\mbox{'s probability of }x \\ f_j & = & \mbox{a function of type }\mathcal{E} \to \{0,1\} \\ E_p f_j & = & \sum_{x \in \mathcal{E}} p(x) f_j(x) \\ E_{\tilde{p}} f_j & = & \sum_{x \in \mathcal{E}} \tilde{p}(x) f_j(x) \\ P & = & \{ p | E_p f_j = E_{\tilde{p}} f_j, \ j = \{1...k\}\} \\ Q & = & \{ p | p(x) = \pi \prod_{j=1}^k \alpha_j^{f_j(x)}, \ 0 \lt \alpha_j \lt \infty \} \\ H(p) & = & \sum_{x \in \mathcal{E}} p(x) \log p(x) \\ L(p) & = & \sum_{x \in \mathcal{E}} \tilde{p}(x) \log p(x) \end{eqnarray*} \]

ここで \(\mathcal{E}\) は事象空間、\(p\) は常に \(\mathcal{E}\) 上で定義される確率分布を示す。\(P\) は制約 (\(\ref{prob}\)) に従う確率分布のセット、\(Q\) は式 (\(\ref{paster}\)) の確率分布のセット、\(H(p)\) は \(p\) のエントロピー、\(L(p)\) は分布 \(p\) に従うサンプル \(\mathcal{S}\) の対数尤度に比例する。

Lemma 1

どのような 2 つの確率分布 \(p\) と \(q\) に対しても \(D(p,q) \geq 0\) であり、\(p = q\) の場合にのみ \(D(p,q)=0\) となる。

証明: [Cover and Thomas, 1991] 参照。

Lemma 2 (Pythagorean Property).

定義 2 に置いて与えられた \(P\) と \(Q\) について、\(p \in P\), \(q \in Q\), \(p^* \in P \cap Q\) としたとき \[ D(p,q) = D(p,p^*) + D(p^*,q) \]

この観測値は [Csiszar, 1975] およびより最近の [Della Pietra et al., 1995] で論議されている。用語 "Pythagorean" は、\(p\), \(p^*\) および \(q\) が直角三角形の頂点であり、\(D\) が二乗距離関数である場合に、この特性がジオメトリにおけるピタゴラス定理と同等である事実を反映している。

証明: 全ての \(r, s \in P\), \(t \in Q\) において: \[ \begin{eqnarray*} \sum_{x \in \mathcal{E}} r(x) \log t(x) & = & \\ \sum_x r(x) \left[\log \pi + \sum_j f_j(x) \log \alpha_j \right] & = & \\ \log \pi \left[ \sum_x r(x) \right] + \left[ \sum_j \log \alpha_j \sum_x r(x) f_j(x) \right] & = & \\ \log \pi \left[ \sum_x s(x) \right] + \left[ \sum_j \log \alpha_j \sum_x s(x) f_j(x) \right] & = & \\ \sum_x s(x) \left[ \log \pi + \sum_j f_j(x) \log \alpha_j \right] & = & \\ & = & \sum_x s(x) \log t(x) \end{eqnarray*} \] 上記の代入と \(p \in P\), \(q \in Q\) および \(p^* \in P \cap Q\) を使用し: \[ \begin{eqnarray*} D(p, p^*) + D(p^*, q) & = & \\ \sum_x p(x) \log p(x) - \sum_x p(x) \log p^*(x) + \sum_x p^*(x) \log p^*(x) - \sum_x p~*(x) \log q(x) & = & \\ \sum_x p(x) \log p(x) - \sum_x p(x) \log p^*(x) + \sum_x p(x) \log p^*(x) - \sum_x p(x) \log q(x) & = & \\ \sum_x p(x) \log p(x) - \sum_x p(x) \log q(x) & = & D(p, q) \\ \end{eqnarray*} \] ∎

5 Maximum Entropy

補題 1 と 2 は制約 (\(\ref{prob}\)) を満たす式 (\(\ref{paster}\)) のモデルの最大エントロピー特性を導く:

Theorem 1. \(p^* \in P \cap Q\) のとき \(p^* = \argmax_{p \in P} H(p)\) が成り立つ。また \(p^*\) は一意である。

Proof. \(p \in P\), \(p^* \in P \cap Q\) とする。\(u \in Q\) を一様分布とすると \(\forall x \in \mathcal{E}\), \(u(x) = \frac{1}{|\mathcal{E}|}\) である。

• \(H(p) \leq H(p^*)\) を示す:
  補題 2 より \[ D(p, u) = D(p, p^*) + D(p^*, u) \] また補題 1 より \[ \begin{eqnarray*} D(p, u) & \geq & D(p^*, u) \\ -H(p)-\log \frac{1}{|\mathcal{E}|} & \geq & -H(p^*) - \log \frac{1}{|\mathcal{E}|} \\ H(p) & \leq & H(p^*) \end{eqnarray*} \]
• \(p^*\) が一意となることを示す: \[ H(p) = H(p^*) \Longrightarrow D(p,u) = D(p^*,u) \Longrightarrow D(p,p^*) = 0 \Longrightarrow p = p^* \]

6 Maximum Likelihood

次に、(\(\ref{prob}\)) を満たす式 (\(\ref{paster}\)) のモデルは最尤推定フレームワークの下で代替的な説明を持つ:

Theorem 2. \(p^* \in P \cap Q\) ならば \(p^* = \argmax_{q \in Q} L(q)\) である。

Proof. \(\tilde{p}\) をサンプル \(\mathcal{S}\) における \(x\), \(\forall x \in \mathcal{E}\) の観測された分布とする。\(\tilde{p} \in P\) は自明。\(q \in Q\), \(p^* \in P \cap Q\) と置く。

• \(L(q) \leq L(p^*)\) であることを示す:
  補題 2 より \[ D(\tilde{p}, p^*) = D(\tilde{p}, p^*) + D(p^*, q) \] また補題 1 より \[ \begin{eqnarray*} D(\tilde{p}, q) & \geq & D(\tilde{p}, p^*) \\ -H(\tilde{p}) - L(q) & \geq & -H(\tilde{p}) - L(p^*) \\ L(q) & \leq & L(p^*) \end{eqnarray*} \]
• \(p^*\) が一意であることを示す: \[ L(q) = L(p^*) \Longrightarrow D(\tilde{p},q) = D(\tilde{p},p^*) \Longrightarrow D(p^*,q) = 0 \Longrightarrow p^* = q \]

定理 1 と 2 では \(p^* \in P \cap Q\) ならば \(p^* = \argmax_{p \in P} H(p) = \argmax_{q \in Q} L(q)\) であり、\(p^*\) は一意に決まると述べている。従って、\(p^*\) は最大エントロピーフレームワークと同時に最尤フレームワークとも見ることができる。最大エントロピーモデルとしての \(p^*\) は制約 (\(\ref{prob}\)) を超える観測値を仮定しないが、最大尤度モデルとしての \(p^*\) は可能な限りデータに近似するためこの二重性は魅力的である。

7 Parameter Estimation

Generalized Iterative Scaling [Darroch and Ratcliff, 1972]、または GIS は一意の分布 \(p^* \in P \cap Q\) のパラメータ \(\{\alpha_1 ... \alpha_k\}\) を発見するための手続きである。GIS 手続きは制約 \[ \forall x \in \mathcal{E} \sum_{j=1}^k f_j(x) = C \] を必要とする。ここで \(C\) はある定数である。これが当てはまらない場合 \(C\) は \[ C = \max_{x \in \mathcal{E}} \sum_{j=1}^k f_j(x) \] として選択し、"訂正" 特徴 \(f_l\) を加える。ここで \[ \forall x \in \mathcal{E} f_l(x) = C - \sum_{j=1}^k f_j(x) \] のように \(l=k+1\) である。既存の特徴と異なり \(f_l(x)\) は 0 から \(C\) までの値を取ることに注意。ここで \(C\) は 1 よりも大きい値を取りうる。

さらに GIS 手続きは、すべての事象が最低一つのアクティブな特徴を持つと仮定する。\[ \forall x \in \mathcal{E} \exists f_j f_j(x) = 1 \]

定理 3. 以下の手続きは \(p^* \in P \cap Q\) に収束する。\[ \begin{eqnarray} \alpha_j^{(0)} & = & 1 \nonumber \\ \alpha_j^{(n+1)} & = & \alpha_j^{(n)} \left[ \frac{\tilde{E}f_j}{E^{(n)}f_j} \right]^{\frac{1}{C}} \label{theorem3} \end{eqnarray} \] ここで \[ \begin{eqnarray*} E^{(n)} f_j & = & \sum_{x \in \mathcal{E}} p^{(n)}(x) f_j(x) \\ p^{(n)}(x) & = & \pi \prod_{j=1}^l \left( \alpha_j^{(n)}\right)^{f_j^{(x)}} \end{eqnarray*} \]

収束の証明は [Darroch and Ratcliff, 1972] 参照。また [Darroch and Ratcliff, 1972] は尤度は減少しない、すなはち \(D(\tilde{p},p^{(n+1)}) \leq D(\tilde{p},p^{(n)})\) であり、\(L(p^{(n+1)}) \geq L(p^{(n)})\) となることを示している。Improved Iterative Scaling の詳細と証明については [Della Pietra et al., 1995] を参照。これは "訂正" 特徴を使用せずに \(p^*\) のパラメータを発見する。GIS の幾何学的解釈については [Csiszar, 1989] 参照。

7.1 Computation

GIS 手続きのそれぞれの反復は \(E_{\tilde{p}}f_j\) と \(E_p f_j\) の量を必要とする。\(E_{\tilde{p}} f_j\) の計算は単に \(f_j\) の正規化されたカウントであるため、訓練サンプル \(\mathcal{S}=\{(a_1,b_1),\ldots,(a_N,b_N)\}\) が与えられれば簡単である: \[ E_{\tilde{p}} f_j = \sum_{i=1}^N \tilde{p}(a_i,b_i) f_j(a_i,b_i) = \frac{1}{N} \sum_{i=1}^N f_j(a_i,b_i) \] ここで \(N\) はサンプル \(\mathcal{S}\) における事象トークン (タイプと対照となる) の数である。

しかしながら、\(\mathcal{E}\) が \(2^k\) の識別可能な事象からなる可能性があるため、\(k\) (重複する) 特徴を有するモデルにおいてモデルの特徴期待値 \[ E^{(n)} f_j = \sum_{a,b \in \mathcal{E}} p^{(n)}(a,b) f_j(a,b) \] の計算は困難である。従って我々は元々 [Lau et al., 1993] で説明されていた近似: \[ \begin{equation} E^{(n)} f_j \approx \sum_{i=1}^N \tilde{p}(b_i) \sum_{a \in \mathcal{A}} p^{(n)} (a|b_i) f_j(a,b_i) \label{e5} \end{equation} \] を使用する。これは \(\mathcal{E}\) ではなく \(\mathcal{S}\) 内の文脈上でのみ合計し計算を扱いやすくする。

この手続は一定の反復回数 (例えば 100) の後、または対数尤度の変化が極僅かである場合に終了すべきである。

各反復の実行時間 \(O(NPA)\) は (\(\ref{e5}\)) によって支配される。ここで \(N\) は訓練セットサイズ、\(P\) は予測数、\(A\) は与えられた事象 \((a,b)\) に対するアクティブな特徴の平均数である。

8 Conclusion

このレポートは簡単な方法で最大エントロピーモデルに関連する数学的特性を示し、[Ratnaparkhi, 1996, Reynar and Ratnaparkhi, 1997, Ratnaparkhi, 1997] で説明されているモデルを再実装するための十分な情報を含んでいる。コンテキスト特性を無限に使用でき、原則的にそれらを組み合わせるだけであるため、このモデルは自然言語処理において便利である。さらに、実験者はその一般性によって異なる問題に対して再利用することができ、高度にカスタマイズされた問題固有の推定方法を開発する必要がなくなるだろう。

References

原文参照。

翻訳抄

最大エントロピーモデル (Maximum Entropy; EM) の自然言語処理への応用に関する 1997 年の論文。

• 原文: A Simple Introduction to Maximum Entropy Models for Natural Language Processing
• 自動要約 (MOXBOX)