最大熵模型
\(P(X, Y)\) 的经验分布
\[\tilde{P}(X=x, Y=y)=\frac{\nu(X=x, Y=y)}{N} \]
边缘分布 \(P(X)\)
\[\tilde{P}(X=x)=\frac{v(X=x)}{N} \]
\(P(X，Y)\) 的经验分布的期望值和关于模型 \(P(Y|X)\) 与 \(P(X)\) 的经验分布的期望值
\[\sum_{x, y} \tilde{P}(x) P(y | x) f(x, y)=\sum_{x, y} \tilde{P}(x, y) f(x, y) \]
定义在条件概率分布 \(P(Y|X)\) 上的条件熵为 \(H(P)=-\sum_{x, y} \tilde{P}(x) P(y | x) \log P(y | x)\)，则条件熵最大的模型称为最大熵模型。
求解最大熵模型
\[\begin{array}{cl}{\max _{P_{R C}}} & {H(P)=-\sum_{x, y} \tilde{P}(x) P(y | x) \log P(y | x)} \\ {\text { s.t.}} & {E_{P}\left(f_{i}\right)=E_{\tilde{p}}\left(f_{i}\right), \quad i=1,2, \cdots, n} \\ {} & {\sum_{y} P(y | x)=1}\end{array} \]
将求最大值问题改为等价的求最小值问题
\[\begin{array}{ll}{\min _{P \in \mathbf{C}}} & {-H(P)=\sum_{x, y} \tilde{P}(x) P(y | x) \log P(y | x)} \\ {\text { s.t.}} & {E_{P}\left(f_{i}\right)-E_{\tilde{F}}\left(f_{i}\right)=0, \quad i=1,2, \cdots, n} \\ {} & {\sum_{y} P(y | x)=1}\end{array} \]
引入拉格朗日乘子
\[\begin{aligned} L(P, w) \equiv &-H(P)+w_{0}\left(1-\sum_{y} P(y | x)\right)+\sum_{i=1}^{n} w_{i}\left(E_{\tilde{p}}\left(f_{i}\right)-E_{P}\left(f_{i}\right)\right) \\=& \sum_{x, y} \tilde{P}(x) P(y | x) \log P(y | x)+w_{0}\left(1-\sum_{y} P(y | x)\right) \\ &+\sum_{i=1}^{n} w_{i}\left(\sum_{x, y} \tilde{P}(x, y) f_{i}(x, y)-\sum_{x, y} \tilde{P}(x) P(y | x) f_{i}(x, y)\right) \end{aligned} \]
\[P_{w}(y | x)=\frac{1}{Z_{w}(x)} \exp \left(\sum_{i=1}^{n} w_{i} f_{i}(x, y)\right) \]
\[Z_{w}(x)=\sum_{y} \exp \left(\sum_{i=1}^{n} w_{i} f_{i}(x, y)\right) \]
算法
- 改进的迭代尺度法 (IIS)
- 拟牛顿法