。

最大熵原理认为#xff0c;学习概率模型时#xff0c;在所有可能的概率模型#xff08;分布#xff09;中#xff0c;熵最大的模型时最好…最大熵模型maximum

entropy

最大熵原理是概率模型学习的一个准则。

最大熵原理认为学习概率模型时在所有可能的概率模型分布中熵最大的模型时最好的模型。

通常用约束条件来确定概率模型的集合所以最大熵原理也可以表述为在满足约束条件的模型集合中选取熵最大的模型。

假设离散随机变量

L(P,λ)−i1∑n​pi​logpi​−λ(i1∑n​pi​−1)

log

\left\{\left(\mathbf{x}_1,y_1\right),\cdots,\left(\mathbf{x}_N,y_N\right)\right\}

P\left(X,Y\right)

\tilde{P}\left(X\mathbf{x},Yy\right)\frac{v\left(X\mathbf{x},Yy\right)}{N}\\

\tilde{P}\left(X\mathbf{x}\right)

\frac{v\left(X

P~(Xx,Yy)Nv(Xx,Yy)​P~(Xx)Nv(Xx)​

v\left(X\mathbf{x},Y

E_{\tilde{P}}\left(f\right)\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)f\left(\mathbf{x},y\right)

特征函数

\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P\left(y|\mathbf{x}\right)f\left(\mathbf{x},y\right)

如果模型能够获取训练数据中的信息那么就可以假设这两个期望值相等即

E_P\left(f\right)E_{\tilde{P}}\left(f\right)

EP​(f)EP~​(f)

\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P\left(y|\mathbf{x}\right)f\left(\mathbf{x},y\right)\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)f\left(\mathbf{x},y\right)

x,y∑​P~(x)P(y∣x)f(x,y)x,y∑​P~(x,y)f(x,y)

假设有

\mathcal{C}\equiv\left\{P\in\mathcal{P}|E_p\left(f_i\right)

E_{\tilde{P}}\left(f_i\right),\quad

1,2,\cdots,

C≡{P∈P∣Ep​(fi​)EP~​(fi​),i1,2,⋯,n}

定义在条件概率分布

-\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P\left(y|\mathbf{x}\right)\log

则模型集合

最大熵模型的学习过程就是求解最大熵模型的过程。

最大熵模型的学习可以形式化为约束最大化问题

T\left\{\left(\mathbf{x}_1,y_1\right),

\cdots,

-\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P\left(y|\mathbf{x}\right)\log

s.t.

E_{\tilde{P}}\left(f_i\right),\quad

1,2,\cdots,

\sum_{y}P\left(y|\mathbf{x}\right)

\end{aligned}

P∈Cmax​s.t.​H(P)−x,y∑​P~(x)P(y∣x)logP(y∣x)EP​(fi​)EP~​(fi​),i1,2,⋯,ny∑​P(y∣x)1​

改成最小化

\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P\left(y|\mathbf{x}\right)\log

s.t.

E_{\tilde{P}}\left(f_i\right),\quad

1,2,\cdots,

\sum_{y}P\left(y|\mathbf{x}\right)

\end{aligned}

P∈Cmin​s.t.​−H(P)x,y∑​P~(x)P(y∣x)logP(y∣x)EP​(fi​)EP~​(fi​),i1,2,⋯,ny∑​P(y∣x)1​

拉格朗日函数

\sum_{y}P\left(y|\mathbf{x}\right)\right)\sum_{i1}^{n}w_i\left(E_{\tilde{P}}\left(f_i\right)

\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P\left(y|\mathbf{x}\right)\log

P\left(y|\mathbf{x}\right)w_0\left(1

\sum_{y}P\left(y|\mathbf{x}\right)\right)\\

\quad

\sum_{i1}^{n}w_i\left(\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)f\left(\mathbf{x},y\right)

\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P\left(y|\mathbf{x}\right)f\left(\mathbf{x},y\right)\right)

\end{aligned}

L(P,w)​−H(P)w0​(1−y∑​P(y∣x))i1∑n​wi​(EP~​(fi​)−EP​(fi​))x,y∑​P~(x)P(y∣x)logP(y∣x)w0​(1−y∑​P(y∣x))i1∑n​wi​(x,y∑​P~(x,y)f(x,y)−x,y∑​P~(x)P(y∣x)f(x,y))​

原始问题

目标函数是凸的约束条件是等式约束于是满足广义Slater条件,

min

L\left(P,\mathbf{w}\right)L\left(P_\mathbf{w},\mathbf{w}\right)

arg

P_{\mathbf{w}}\arg\min_{P\in\mathcal{C}}

P_{\mathbf{w}}\left(y|\mathbf{x}\right)

log

\tilde{P}\left(\mathbf{x}\right)\left(\log

1\right)-\sum_{y}w_0-\sum_{\mathbf{x},y}\left(\tilde{P}\left(\mathbf{x}\right)\sum_{i1}^{n}w_if_i\left(\mathbf{x},y\right)\right)\\

\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)\left(\log

1-w_0-\sum_{i1}^{n}w_if_i\left(\mathbf{x},y\right)\right)\\

\end{aligned}

∂P(y∣x)∂L​​x,y∑​P~(x)(logP(y∣x)1)−y∑​w0​−x,y∑​(P~(x)i1∑n​wi​fi​(x,y))x,y∑​P~(x)(logP(y∣x)1−w0​−i1∑n​wi​fi​(x,y))0​

\tilde{P}\left(\mathbf{x}\right)0

exp\left(\sum_{i1}^{n}w_if_i\left(\mathbf{x},y\right)

w_0

1\right)\frac{exp\left(\sum_{i1}^{n}w_if_i\left(\mathbf{x},y\right)\right)}{exp\left(1-w_0\right)}

P(y∣x)exp(i1∑n​wi​fi​(x,y)w0​−1)exp(1−w0​)exp(∑i1n​wi​fi​(x,y))​

\sum_{y}

P_{\mathbf{w}}\left(y|\mathbf{x}\right)

\frac{1}{Z_{\mathbf{w}}\left(\mathbf{x}\right)}exp\left(\sum_{i1}^{n}w_if_i\left(\mathbf{x},y\right)\right)

Pw​(y∣x)Zw​(x)1​exp(i1∑n​wi​fi​(x,y))

Z_{\mathbf{w}}\left(\mathbf{x}\right)

\sum_{y}exp\left(\sum_{i1}^{n}w_if_i\left(\mathbf{x},y\right)\right)

Z_{\mathbf{w}}\left(\mathbf{x}\right)

Zw​(x)称为规范化因子

P_{\mathbf{w}}P_{\mathbf{w}}\left(y|\mathbf{x}\right)

\mathbf{w}

\max\psi\left(\mathbf{w}\right)

maxψ(w)

\arg\max_{\mathbf{w}}\psi\left(\mathbf{w}\right)

w∗argwmax​ψ(w)

\pi_{\mathbf{x},y}P\left(y|\mathbf{x}\right)^{\tilde{P}\left(\mathbf{x},y\right)}

\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)

\log

LP~​(Pw​)logπx,y​P(y∣x)P~(x,y)x,y∑​P~(x,y)logP(y∣x)

log

L_{\tilde{P}}\left(P_{\mathbf{w}}\right)

\sum_{\mathbf{x},y}

\tilde{P}\left(\mathbf{x},y\right)

\log

\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)\sum_{i1}^{n}w_i

\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)\log

Z_{\mathbf{w}}\left(\mathbf{x}\right)\\

\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)\sum_{i1}^{n}w_i

\sum_{\mathbf{x}}\tilde{P}\left(\mathbf{x}\right)\log

Z_{\mathbf{w}}\left(\mathbf{x}\right)

\end{aligned}

LP~​(Pw​)​x,y∑​P~(x,y)logP(y∣x)x,y∑​P~(x,y)i1∑n​wi​fi​(x,y)−x,y∑​P~(x,y)logZw​(x)x,y∑​P~(x,y)i1∑n​wi​fi​(x,y)−x∑​P~(x)logZw​(x)​

log

\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P_{\mathbf{w}}\left(y,\mathbf{x}\right)\log

P_{\mathbf{w}}\left(y|\mathbf{x}\right)

\quad

w_i\left(\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)f_i\left(\mathbf{x},y\right)

\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P_{\mathbf{w}}\left(y|\mathbf{x}\right)f_i\left(\mathbf{x},y\right)\right)\\

\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)\sum_{i1}^{n}w_i

\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)

P_{\mathbf{w}}\left(y|\mathbf{x}\right)\left(\log

P_{\mathbf{w}}\left(y|\mathbf{x}\right)

\sum_{i1}^{n}w_if_i\left(\mathbf{x},y\right)\right)\\

\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)\sum_{i1}^{n}w_i

f_i\left(\mathbf{x},y\right)-\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)P_{\mathbf{w}}\left(y|\mathbf{x}\right)\log

Z_{\mathbf{w}}\left(\mathbf{x}\right)\\

\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x},y\right)\sum_{i1}^{n}w_i

f_i\left(\mathbf{x},y\right)-\sum_{\mathbf{x},y}\tilde{P}\left(\mathbf{x}\right)\log

Z_{\mathbf{w}}\left(\mathbf{x}\right)\\

\end{aligned}

ψ(w)​x,y∑​P~(x)Pw​(y,x)logPw​(y∣x)i1∑n​wi​(x,y∑​P~(x,y)fi​(x,y)−x,y∑​P~(x)Pw​(y∣x)fi​(x,y))x,y∑​P~(x,y)i1∑n​wi​fi​(x,y)x,y∑​P~(x)Pw​(y∣x)(logPw​(y∣x)−i1∑n​wi​fi​(x,y))x,y∑​P~(x,y)i1∑n​wi​fi​(x,y)−x,y∑​P~(x)Pw​(y∣x)logZw​(x)x,y∑​P~(x,y)i1∑n​wi​fi​(x,y)−x,y∑​P~(x)logZw​(x)​

这样最大熵模型的学习问题就转化为具体求解对数似然函数极大化或对偶函数极大化的问题

\frac{1}{Z_{\mathbf{w}}\left(\mathbf{x}\right)}exp\left(\sum_{i1}^{n}w_i

f_i\left(\mathbf{x},y\right)\right)

Z_{\mathbf{w}}\left(\mathbf{x}\right)\sum_{y}exp\left(\sum_{i1}^{n}w_i

f_i\left(\mathbf{x},y\right)\right)

x∈Rn为输入