最大エントロピーモデル（対数線形モデル）について - 機械学習・自然言語処理の勉強メモ

最大エントロピー原理

概要は

確率変数 X について、 X が条件 I を満たす事だけが分かっており、それ以外に X に関して何1つ知らなかったとする。
X について条件 I 以外には何も知らないのだから、条件 I の下で X の「不確かさ」が最大（エントロピーが最大）になるような分布を選ぶのが適切だと思われる。
最大エントロピー原理は、「不確かさ」を図る尺度であるエントロピーを条件 I の下で最大にするよう分布を選ぶべきである、という原理である。

最大エントロピー原理 - Wikipedia
より引用

具体例による説明に関しては下記ブログが分かりやすい。
http://d.hatena.ne.jp/takeda25/20121105/1352385394

例題：
$P(a,b)$ の確率分布（クラス $a$ と文脈 $b$ の同時生起確率）を考える。
$a \in \{x,y\}$ , $b \in \{0,1\}$
制約条件は、 $P(x,0)+P(x,1)+P(y,0)+P(y,1)=1.0$

$P(a,b)$	0	1
$x$	?	?
$y$	?	?
$total$			1.0

この場合、エントロピーを最大化する確率分布は、

$P(a,b)$	0	1
$x$	0.25	0.25
$y$	0.25	0.25
$total$	0.5	0.5	1.0

となる。（全ての確率変数が等確率）

次に、 $P(x,0)+P(y,0)=0.6$ の制約条件が加わった場合、

$P(a,b)$	0	1
$x$	?	?
$y$	?	?
$total$	0.6		1.0

を考える。
この場合、エントロピーを最大化する確率分布は、

$P(a,b)$	0	1
$x$	0.3	0.2
$y$	0.3	0.2
$total$	0.6	0.4	1.0

制約条件以外に情報は無いので、 $P(x,0), P(y,0)$ の確率変数は等確率とする。
一般化すると、エントロピー
$\begin{eqnarray} H(P)=-\sum_{a \in \{x,y\}, b \in \{0,1\}}P(a,b)\log P(a,b) \end{eqnarray}$
が最大となる $P(a,b)$ を求める問題となる。

$H(P)$ を最大にする $P(a,b)$ は次のように導かれる。（導出は割愛）
$\begin{eqnarray} P(a,b)=\pi \prod_{j=1}^k w_j^{f_j(a,b)}\ldots (1) \end{eqnarray}$
例えば、
$P(x,1)=\pi \times w_0^{f_0(x,1)}\times w_1^{f_1(x,1)}$
となる。
$f$ を素性関数と呼び、
$f_0(a,b) =\begin{cases}1 & b = 0\\0 & otherwise\end{cases}$
$f_1(a,b) =\begin{cases}1 & b = 1\\0 & otherwise\end{cases}$
とすると、この式は、
$P(x,1)=\pi \times w_1$
となる。

$w_j$ が素性関数ごとの重みであり、これを解析的に求める。
※A Simple Introduction to Maximum Entropy Models for Natural Language Processing より引用

条件付き確率の導出

最大エントロピーモデルの場合、直接 $P(Y|X)$ をモデル化する。
（ $P(Y|X)$ のパラメータを最尤法により求める。）

まず、(1)から条件付き確率を求める。
$\pi$ は確率の総和を1とする規格係数なので、(1)は、
$\begin{eqnarray} P(a,b)=\frac{\prod_{j=1}^k w_j^{f_j(a,b)}}{\sum_{a \in \{x,y\}, b \in \{0,1\}}{ ( \prod_{j=1}^k w_j^{f_j(a,b)})}}\ldots (2) \end{eqnarray}$
と書き換えられる。
(2)を $P(a|b)$ とする場合、周辺化は $a$ に関してのみ行うので、
$\begin{eqnarray} P(a|b)=\frac{\prod_{j=1}^k w_j^{f_j(a,b)}}{\sum_{a \in \{x,y\}}{ ( \prod_{j=1}^k w_j^{f_j(a,b)})}}\ldots (3) \end{eqnarray}$
となる。
特に意味はないが、(3)の素性関数を $\phi$ に変える。
$\begin{eqnarray} P(a|b)=\frac{\prod_{j=1}^k w_j^{\phi_j(a,b)}}{\sum_{a \in \{x,y\}}{ ( \prod_{j=1}^k w_j^{\phi_j(a,b)})}}\ldots (4) \end{eqnarray}$
(4)の重み・素性関数をそれぞれ $j$ 次元のベクトルで表記すると、
$\begin{eqnarray} P(a|b)=\frac{w^{\phi(a,b)}}{\sum_{a \in \{x,y\}}{ (w^{\phi(a,b)})}}\ldots (5) \end{eqnarray}$
となる。
(5)は
$\begin{eqnarray} P(a|b)=\frac{\exp (\log w^{\phi(a,b)})}{\sum_{a \in \{x,y\}}{ \exp (\log w^{\phi(a,b)})}}\ldots (6) \end{eqnarray}$
と書き換えられる。
制約条件 $\phi(a,b)=\big\{0,1\big\}$ がある場合、(6)は、
$\begin{eqnarray} P(a|b)=\frac{\exp (\log w\cdot {\phi(a,b)})}{\sum_{a \in \{x,y\}}{ \exp (\log w\cdot {\phi(a,b)})}}\ldots (7) \end{eqnarray}$
と等価。
$W=\log w$ とおくと、(7)は、
$\begin{eqnarray} P(a|b)=\frac{\exp (W\cdot {\phi(a,b)})}{\sum_{a \in \{x,y\}}{ \exp (W\cdot {\phi(a,b)})}}\ldots (8) \end{eqnarray}$

(8)を
$\begin{eqnarray}Z=\sum_{a \in \{x,y\}}{\exp ( W\cdot \phi(a,b))}\end{eqnarray}$
で変形すると、
$\begin{eqnarray} P(a|b)=\frac{1}{Z}\exp (W\cdot \phi(a,b))\ldots (9) \end{eqnarray}$
が導かれる。

このように同時確率からベイズの定理を用いて条件付き確率が導出される。
最終的にモデルが対数の形をとることから「対数線形モデル」とも呼ばれる。
導出の一部はここを参照した。

パラメータ推定（学習）

計算を簡単にするため、(9)の対数を取った値
$L(w)=logP(a|b)=(W \cdot \phi (a,b))-\log Z$
の最大化問題を解くこととする。
これは解析的には求めることが出来ないので、最急勾配法などの数値解法を用いる。すなわち、
$w^{new}=w^{old}+\epsilon \nabla _wL(w^{old})$
の更新式を収束するまで繰り返す。
$\nabla _wL(w)=(\phi (a,b)-\frac{Z '}{Z})$
※第二項は合成関数の微分
$\hspace{39pt} =\begin{eqnarray}(\phi (a,b)-\frac{\sum_{b}\exp (W \cdot \phi(a,b) )'}{Z})\end{eqnarray}$
※第二項は更に合成関数の微分
$\hspace{39pt} =\begin{eqnarray}(\phi (a,b)-\frac{\sum_{b}\exp (W \cdot \phi(a,b) )' \cdot (W \cdot \phi(a,b))'}{Z})\end{eqnarray}$
それぞれ微分して
$\hspace{39pt} =\begin{eqnarray}(\phi (a,b)-\frac{\sum_{b}\exp (W \cdot \phi(a,b) ) \cdot \phi(a,b)}{Z})\end{eqnarray}$
$\hspace{39pt} =\begin{eqnarray}(\phi (a,b)-\frac{\sum_{b}\exp (W \cdot \phi(a,b) ) \cdot \phi(a,b)}{\sum_{b}\exp (W \cdot \phi(a,b) )})\end{eqnarray}$
$\hspace{39pt} =\begin{eqnarray}(\phi (a,b)- \sum_{b}P(b|a) \cdot \phi(a,b))\end{eqnarray}$
となる。
これを計算して重みを更新していく。
※実際の計算では、損失関数に正則化項（ $-(C/2)|w|^2$ ）を加える。

書いてみた。

上記で紹介した書籍（通称、高村本）p.135の例題を解いてみた。

# maximum entropy model
import numpy as np


class MEM(object):
    def __init__(self, eta, c, stop_num):
        self.eta = eta
        self.c = c
        self.stop_num = stop_num
        self.L = -999

    def updateW(self):
        sum_f = np.zeros(self.fm.shape[2])
        for i, (sent, label) in enumerate(zip(self.docs, self.labels)):
            sum_f = sum_f + self.fm[i][label] - np.dot(self.prob[i], self.fm[i])
        return sum_f - self.c * np.sum(self.w)

    def negative_log_likelihood(self):
        return np.sum(np.log(self.prob[np.arange(len(self.labels)), self.labels])) \
               - (self.c / 2) * np.linalg.norm(self.w)

    def fit(self, docs, labels):
        self.docs = docs
        self.labels = labels
        self.classes = set(labels)
        # build feature
        self.features = [f for f in self.build_feature()]
        # docs to feature vector
        self.fm = np.array([fm for fm in self.doc2fv(docs)])
        self.w = np.zeros(self.fm.shape[2])
        dif_ = 1
        while self.stop_num < dif_:
            self.prob = self.calc_prob(self.fm)
            w_ = self.updateW()
            self.w = self.w + self.eta * w_
            current_L = self.negative_log_likelihood()
            dif_ = current_L - self.L
            self.L = current_L

    def predict(self, docs):
        # docs to feature vector
        fm = np.array([fm for fm in self.doc2fv(docs)])
        prob = self.calc_prob(fm)
        return np.argmax(prob, axis=0)

    def calc_prob(self, fm):
        dot_ = np.dot(fm, self.w)
        return self.softmax(dot_)

    def softmax(self, f):
        e = np.exp(f)
        return e / np.sum(e, axis=1, keepdims=True)

    def build_feature(self):
        words = set([word for sent in self.docs for word in sent.split()])
        added = set()
        for word in words:
            for label in self.labels:
                if word + str(label) in added:
                    pass
                else:
                    added.add(word + str(label))
                    yield [word, label]

    def doc2fv(self, docs):
        for i, doc in enumerate(docs):
            label_list = []
            for label in self.classes:
                feature_list = []
                for feature in self.features:
                    if feature[0] in doc.split() and feature[1] == label:
                        feature_list.append(1)
                    else:
                        feature_list.append(0)
                label_list.append(feature_list)
            yield label_list


docs = ['good bad good good',
        'exciting exciting',
        'bad boring boring boring',
        'bad exciting bad']
labels = [0, 0, 1, 1]

mem = MEM(eta=0.1, c=0.1, stop_num=1.0e-5)
mem.fit(docs, labels)
print mem.predict(['bad exciting good', 'bad boring'])
>> [0 1]

bad exciting goodを与えると0(Positive)、
bad boringを与えると1(Negative)を返す。