最大熵模型

1. logistic回归模型

1.1 Logsitic分布

设X是服从logistic分布的连续随即变量，则X的分布函数和密度函数如下：

　　　　　　( F(x)=P(x le x)=displaystylefrac{1}{1+e^{-(x-mu)/gamma}} )

　　　　　　( f(x)=F'(x) = displaystylefrac{e^{-(x-mu)/gamma}}{gamma(1+e^{-(x-mu)/gamma})^2} )

分布函数属于Logistic函数，是一条S型曲线

1.2 logistic回归模型

二项logistic回归模型是一种分类模型，有条件概率分布( P(Y|X) )表示，形式为参数化的logistic分布。这里X取值为实数，Y取值为1或0.通过监督学习的方法来估计模型参数。

二项logistic回归模型的条件概率分布：

　　　　　　( P(Y=1|x)=displaystylefrac{exp(w cdot x +b)}{1+exp(w cdot x + b)} )

　　　　　　( P(Y=1|x)=displaystylefrac{1}{1+exp(w cdot x + b)} )

这里，( x in R^n )是输入，( Y in {0,1} )是输出，( w in R^n )和( b in R )是参数，w成为权值向量，b成为偏置。

对于给定的输入x，按照如上公式分别求得( P(Y=1|x) )和( P(Y=0|x) )，比较里两个条件概率值的大小，将X分到概率值比较大的那个类。属于判别模型。

1.3 模型参数估计

logistic回归模型学习时，对于给定的训练数据集( T={ (x_1,y_1), (x_2, y_2),...,(x_N,y_N)} )，其中( x_i in R^n, y_i in {0,1} )，可以使用极大斯然估计法估计模型参数，从而得到logistic模型。

假设 ( displaystyle P(Y=1|x) = pi(x) , p(Y=0|x) = 1- pi(x))

似然函数

　　　　　　( displaystyleprod_{i=1}^{N} [pi(x_i)]^{y_i}[1-/pi(x_i)]^{1-y_i} )

对数似然函数

　　　　　　( displaystyle L(w)=sum_{i=1}^{N}[y_i logpi(x_i) + (1-y_i)log(1-pi(x_i))] )

　　　　　　　　　( displaystyle=sum_{i=1}^{N}iggl[y_i logfrac{pi(x_i)}{1-pi(x_i)} + log(1-pi(x_i))iggr] )

　　　　　　　　　( displaystyle=sum_{i=1}^{N}[y_i(w cdot x_i) - log(1+exp(w cdot x_i))] )

对( L(w) )求极大值，得到( w )的估计值。这样，问题就变成了以对数似然函数为目标的最优化问题。logistic回归学总通常采用的方法是梯度下降法和拟牛顿法。

假设( w )极大似然估计为( hat w )，那么学到logistic的回归模型为

　　　　　　( P(Y=1|x)=displaystylefrac{exp(hat w cdot x)}{1 + exp(hat w cdot x)} )

　　　　　　( P(Y=1|x)=displaystylefrac{1}{1+exp(hat w cdot x)} )

2. 最大熵模型

2.1 最大熵原理

设随机变量X的概率分布为P(X)，则其熵为

　　　　　　( H(P)=displaystyle-sum_{x}P(x)logP(x) )

( 0 le H(P) le log|X| )，( |X| )为X的取值个数，当且仅当X的分布式均匀分布时右边的等号成立。也就是说X均匀分布时，熵最大。

直观上，最大熵原理认为要选择的概率模型搜西安必须满足已有的事实，及约束条件。在没有更多信息的条件下，那些不确定的部分都是”等可能的“。最大熵原理通过熵的最大化来表示等可能性。

2.2 最大熵模型

假设所有满足约束条件的模型集合为

　　　　　　(displaystyle mathcal{C} equiv { p in mathcal{p}|E_p(f_i)=E_{ ilde{p}}(f_i), i=1,2,...,n } )

定义在条件概率分布P(Y|X)上的条件熵为

　　　　　　(displaystyle H(P)=-sum_{x,y} ilde{P}(x)P(y|x)logP(y|x) )

则模型集合( mathcal{C} )中条件熵( H(P) )最大的模型成为最大熵模型。式中的对数为自然对数。( f_i)为特征还函数

( E_{ ilde{p}}(f) )表示特征函数( f(x,y) )关于经验分布的期望

　　　　　　(displaystyle E_{ ilde{P}}(f)=sum_{x,y} ilde{P}(x,y)f(x,y) )

( E_P(f) )表示特征函数( f(x,y) )关于模型( P(Y|X) )与经验分布( ilde{P}(X) )的期望

　　　　　　(displaystyle E_P(f)=sum_{x,y} ilde{P}(x)P(y|x)f(x,y) )

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

　　　　　　(displaystyle E_P(f)=E_{ ilde{P}}(f))

或

　　　　　　(displaystyle sum_{x,y} ilde{P}(x,y)f(x,y)=sum_{x,y} ilde{P}(x)P(y|x)f(x,y) )

这就是模型学习的约束条件，如果有n个特征函数( f_i(x,y) ,i=1,2,...,n )，那么就有n个约束条件。

2.3 最大熵模型的学习

最大熵模型的学习过程就是求解最大熵模型的过程，最大熵模型的学习可以形式化为约束最优化问题。

对于给定的训练数据集( displaystyle T={(x_1,y_1),(x_2,y_2),...,(x_N, y_N)} )，及特征函数( displaystyle f_i(x,y),i=1,2,...,n )，最大熵模型的学习问题等价于约束最优化问题：

　　　　　　( displaystyle max_{p in C} quad H(P)=-sum_{x,y} ilde{P}(x)P(y|x)log P(y|x) )

　　　　　　(displaystyle s.t. quad E_P(f_i)=E_{ ilde{P}}(f_i), i=1,2,...,n )

　　　　　　　　　　(sum_yP(y|x)=1 )

改写成最小化问题

　　　　　　(displaystyle min_{p in C} quad -H(P)=sum_{x,y} ilde{P}P(x,y)log P(y|x) )

　　　　　　(displaystyle s.t. quad E_P(f_i)-E_{ ilde{P}}(f_i)=0,i=1,2,...,n)

　　　　　　(displaystyle sum_{y}P(y|x)=1 )

看到这种形式，想到引入拉格朗日乘子( displaystyle w_0,w_1,w_2,...,w_n )，定义拉格朗日函数( L(P,w) )

　　　　　　(displaystyle L(P,w) equiv -H(P)+w_0 iggl(1-sum_yP(y|x) iggr) + sum_{i=1}^{n}w_i (E_{ ilde{P}}(f_i)- E_P(f_i)) )

　　　　　　　　　　(displaystyle =sum_{x,y} ilde{P}(x)P(y|x)log P(y|x) + w_0 iggl(1-sum_y P(y|x) iggr) + sum_{i=1}^{n}w_i iggl(sum_{x,y} ilde{P}(x,y)f_i(x,y)-sum_{x,y} ilde{P}(x)P(y|x)f_i(x,y) iggr) )

最优化的原始问题是

　　　　　　(displaystyle min_{P in C} quad max_{w} L(P,w) quad quad (*))

对偶问题是

　　　　　　(displaystyle max_{w} min_{p in C} L(P,w) quad quad (**))

由于拉格朗日函数(displaystyle L(P,w) )是P的凸函数，原始问题的解与对偶问题的解是等价的.

首先求解对偶问题**内部的极小化问题 (displaystyle min_{P in C}L(P,w))，他是w的函数，记做

　　　　　　(displaystyle Psi(w) = min_{P in C}L(P,w)=L(P_w,w) )

则

　　　　　　(displaystyle P_w=arg min_{P in C}L(P,w)=P_w(y|x) )

具体的，求(displaystyle L(P,w) )对(displaystyle P(y|x) )的偏导

　　　　　　(displaystyle frac{eth L(P,w)}{eth P(y|x)}=sum_{x,y} ilde P(x)(log P(y|x)+1)-sum_y w_0 -sum_{x,y} iggl( ilde P(x)sum_{i=1}^{n}w_if_i(x,y) iggr) )

　　　　　　(displaystyle =sum_{x,y} ilde P(x) iggl(log P(y|x)+1-w_0-sum_{i=1}^{n}w_if_i(x,y) iggr) )

令其等0，在(displaystyle ilde P(x) >0 )的情况下，解得

　　　　　　(displaystyle P(y|x)=exp iggl( sum_{i=1}^{n}w_i f_i (x,y) + w_0 -1 iggr) =frac{exp igl( sum_{i=1}^{n}w_i f_i (x,y) igr)}{exp (1-w_0)})

由于

　　　　　　(displaystyle sum_y P(y|x)=1 )

得

　　　　　　(displaystyle P_w(y|x)=frac{1}{Z_w(x)}exp igl( sum_{i=1}^n w_i f_i (x,y) ig) )

其中

　　　　　　(displaystyle Z_w(x)=sum_y igl( sum_{i=1}^n w_i f_i (x,y)igr) )

(displaystyle Z_w(x) )称为规范化因子；(displaystyle f_i(x,y) )是特征函数；(displaystyle w_i )是特征权值。(displaystyle P_w=P_w(y|x))就是最大熵模型。

然后，求解对偶问题外部的极大化问题

　　　　　　(displaystyle max_w Psi(w) quad quad (1))

将其解记为(displaystyle w^*)，即

　　　　　　(displaystyle w^*=arg max_w Psi(w) quad quad (2))

这就是说，可以应用最优化算法求对偶函数(displaystyle Psi(w))的极大化，得到(displaystyle w^*)，用来表示(displaystyle P^* in C)。这里(displaystyle P^*=P_{w^*}=P_{w^*}(y|x))就是学习到的最有模型（最大熵模型）。也就是说，最大熵模型的学习归结为对偶函数(displaystyle Psi(w))的极大化。

2.4 极大似然估计

下面证明对偶函数的极大化等价于最大熵模型的极大似然估计。

已知训练数据的经验概率分布(displaystyle ilde P(X,Y))，条件概率分布(displaystyle P(Y|X) )的对数似然函数为

　　　　　　(displaystyle L_{ ilde P}(P_W) = log prod_{x,y} P(y|x)^{ ilde P(x,)}=sum_{x,y} ilde P(x,y)log P(y|x))

当条件概率分布(displaystyle P(y|x))是最大熵模型（1）和（2）时，对数似然函数(displaystyle L_{ ilde P}(P_W) )为

　　　　　　(displaystyle L_{ ilde P}(P_W) = sum_{x,y} ilde P(x,y) log P(x,y))

　　　　　　(displaystyle =sum_{x,y} ilde P(x,y) sum_{i=1}^n w_i f_i (x,y) - sum_{x,y} ilde P(x,y)log Z_W(x))

　　　　　　(displaystyle =sum_{x,y} ilde P(x,y) sum_{i=1}^n w_i f_i (x,y) - sum_{x} ilde P(x)log Z_W(x))