logistic回归和最大熵模型

1. logistic回归模型

  logistic回归是一种广义线性回归（generalized linear model），因此与多重线性回归分析有很多相同之处。它们的模型形式基本上相同，都具有wx+b，其中w和b是待求参数，其区别在于他们的因变量不同，多重线性回归直接将wx+b作为因变量，即y =wx+b，而logistic回归则通过函数g(wx+b)让其对应一个隐状态p，p =g(wx+b),然后根据p 与1-p的比值大小（几率）决定因变量的值。如果g是logistic函数，就是logistic回归，如果g是多项式函数就是多项式回归。

  logistic回归的因变量可以是二分类的，也可以是多分类的，但是二分类的更为常用，也更加容易解释，多类可以使用softmax方法进行处理。实际中最为常用的就是二分类的logistic回归。

1.1 logistic分布

  设X是连续随机变量，X服从的logistic分布具有如下分布函数

$$F(x) = P(X \leqslant x) = \frac {1} {1+exp(\frac {-(x-\mu)} {\gamma})}$$

其中，$\mu$ 为位置参数，$\gamma > 0$为形状参数。

  我们最常用的是$\mu =0,\gamma =1 $的标准logistic分布，即sigmoid函数

$$\sigma(x) = \frac {1} {1+e^{-x}}$$

其图像如下

1.2 二项logistic回归模型

  二项logistic回归模型是一种分类模型，以往都是将分类和回归作为两个类别的，为什么logistic回归是一种分类模型呢？原因在于logistic回归计算两个类别的条件概率的大小，再将其比值作为输出，将类别划分为比值大的那一类。所以它的输出是连续值，只是用来分类而已。

  logistic回归由条件概率$P(Y|X)$的形式表示，其中，随便变量X取值为实数，随机变量Y取值为1或0。二项logistic回归模型是如下的条件概率分布：

$$\begin{aligned} P(Y=1|x) =& \frac {1}{1+exp(-(w^T\cdot x+b))}\\ P(Y=0|x) =& 1-P(Y=1|x)\\ =& \frac {1}{1+exp(w^T\cdot x +b)} \end{aligned}$$

  计算出上式两个概率值后，它们的比值就是logistic回归模型的输出，最后将输入实例x分类到比值大的那一类。

  若不关心logistic函数作为随机变量的分布函数，该模型计算的就是普通的二项分布，而使用logistic函数使得该二项分布具有一个很好的特性。logistic回归模型计算概率的比值$\frac {p}{1-p}$，这个比值叫做事件发生的几率。取对数后叫做对数几率。因此logistic回归也有人叫做对数几率回归。当分布函数是sigmoid时

$$log\frac {p}{1-p} = log \frac {P(Y=1|x)}{P(Y=0|x)}=w^T\cdot x +b$$

  这个式子表明，logistic回归模型取对数后是一个线性模型，即它是一个对数线性模型。普通的线性模型$w\cdot x +b$的取值范围可能会非常大，而logistic模型将其值约束在$0\sim 1$之间，从根本上解决了因变量不是连续变量的问题。

1.3 模型参数估计

  对logistic回归模型学习用的损失函数是根据极大似然估计推导而来，X服从二项logistic分布，对于有N组数据的训练集，其似然函数为

$$\prod_{i=1}^N [\pi(x_i)]^{y_i}[1-\pi(x_i)]^{1-y_i}$$

对数似然函数为

$$\begin{aligned} L(w) = & \sum_{i=1}^N[y_ilog\pi(x_i)+(1-y_i)log(1-\pi(x_i))]\\ = & \sum_{i=1}^N \left [ y_ilog\frac {\pi(x_i)}{1-\pi(x_i)}+log(1-\pi(x_i)) \right ]\\ = & \sum_{i=1}^N [y_i(w^T\cdot x_i)-log(1+exp(w^T\cdot x_i)] \end{aligned}$$

估计

$$\widehat w = arg\underset w {max} L(w)$$

得到参数$w$的估计值

  $L(w)$的最大化是一个无约束的最优化问题，求解这类问题的经典方法是梯度下降和牛顿法。这里求极大化应该用梯度上升，不过原理都是一样的，下面以梯度上升为例，正常的梯度上升求解所有样本$n$的梯度平均值，而梯度前会有学习率调整学习速度，因此前面的$\frac 1 n$并不是必须的。先对$L(w)$关于$w$求偏导，$w$是向量，这里分步对其求导得到$w$每个维度的迭代公式

$$\begin{aligned} \frac {\partial L(w)}{\partial w_k} = &\frac 1 n \sum_i^n\left[ x_{ik}y_i -\frac {exp(w^T\cdot x_i)}{1+exp(w^T\cdot x_i)} x_{ik} \right]\\ =&\frac 1 n \sum_i^n [y_i - \sigma( x_i)]\cdot x_{ik} \end{aligned}$$

其中，$x_{ik}$表示第$i$ 个样本向量的第$k$ 维数据。

  那么，迭代方程为

$$\widetilde w_k = w_k + \alpha \sum_i^n[y_i- \sigma(x_i)] \cdot x_{ik}$$

其中，$\alpha$为学习率。

• 迭代过程向量化

  在$NumPy$中，对矩阵和向量的运算做了优化，其运行效率远远高于使用$Python$的for循环计算。因此对于经常有较大矩阵与向量计算的机器学习算法，将计算公式向量化（矩阵化）是非常有必要的。

  假设默认的向量都是列向量，观察原迭代方程。有两个需要使用for循环的地方，一是对$n$个样本求梯度均值，二是求$w$系数的所有维度。对于一，将$n$个样本以列向量组合在一起，计算内积即可。对于二，数据以向量形式组合后，可以直接计算返回一个列向量得到$w$的所有维度。其中，

$$y = [y_1,y_2,\cdots,y_n]^T$$

以$X$表示样本组合成的矩阵

$$X= \begin{bmatrix} x_1^T\\ x_2^T\\ \vdots\\ x_n^T\end{bmatrix}$$

则，向量化后的迭代方程为

$$\widetilde w = w+\alpha [y-\delta(X)]\cdot X^T$$

2. 最大熵模型

2.1 最大熵原理

  最大熵模型根据最大熵原理而来，而最大熵原理是概率模型学习中的一个准则。即在满足已有的事实（约束条件）的情况下，若没有其他更多的信息，那么剩下的一些不能确定的部分都应当作“等可能的”，也就是一个模型如果是等可能的，它的不确定性就很大。熵就是用于表示这种不确定性，因此在学习中，应尽量满足熵最大化的原则。这就是最大熵原理。

  假设离散随机变量X的概率分布是$P(X)$，其熵的定义如下

$$H(P) = - \sum_x P(x)log P(x)$$

它满足不等式：

$$0 \leqslant H(P) \leqslant log | num(X) |$$

当且仅当$X$是均匀分布的时候右边取等号，即均匀分布时的熵最大。此时

$$H(P)=-\sum_n\frac 1 n log\frac 1 n = logn$$

  关于熵的理解在另一篇笔记中《熵、交叉熵、极大似然》。总的来说，熵表示了模型内部的混乱度，或者说信息量的大小和不确定性的大小。

2.2 最大熵模型

  依据最大熵原理，在没有获取充足的模型约束情况下。一个好的方法便是在满足已有约束的条件下，对未知情况的抉择使用均匀分布去代替，也就是选择一个熵最大（信息量最大，不确定性最大，最混乱）的模型。这就是最大熵模型的思想，可以分解为两步。一、根据已有约束条件，得出所有满足约束的概率模型。二、在得到的模型中选择一个熵最大的模型作为最优模型。

  假设一个分类模型是一个条件概率分布$P(Y|X)$，表示对于给定输入$X$，模型给出一个分类结果$Y$。已知训练集后，我们能够得到该训练集中$X,Y$的联合分布$P(X,Y)$和边缘分布$P(X)$的经验分布，分别由$\widetilde P(X,Y),\widetilde P(X)$表示。

  为了添加一些约束条件，最大熵模型引入了特征函数来表达$x$与$y$之间满足的一些约束

$$f(x,y) = \begin{cases} 1, &x与y满足某约束\\ 0，&否则 \end{cases}$$

  如何表达该模型满足特征函数的约束条件呢？前面我们由训练数据集可以得出$X,Y$的联合分布与$X$的边缘分布的经验分布，那么首先，模型$P(Y|X)$应满足的条件便是

$$\widetilde P(X) \cdot P(Y|X) = \widetilde P(X,Y)$$

如果该模型$P(Y|X)$同时满足特征函数的约束，那么特征函数关于上式两端的期望都应该相同，特征函数$f(x,y)$关于$\widetilde P(X,Y)$的期望为

$$E_{\widetilde P} (f) = \sum_{x,y} \widetilde P(x,y) f(x,y)$$

关于$P(Y|X)$与$\widetilde P(X)$的期望为

$$E_p(f) = \sum_{x,y} \widetilde P(X) P(Y|X) f(x,y)$$

  得到关于特征函数的约束为

$$E_{\widetilde P} (f)= E_P(f)$$

• 最大熵模型定义

  假设满足所有特征函数的模型集合为

$$C \equiv \{ P\in \mathbb{P}|E_{\widetilde P} (f_i)= E_P(f_i) \}$$

  在得到满足特征函数约束的模型集合后，计算其熵的大小，选择其中熵最大的模型即是最优模型，$P(Y|X)$的条件熵为

$$H(P) = -\sum_{x,y} \widetilde P(x)P(y|x) log P(y|x)$$

则，最大熵模型$p^*$为

$$P^* = arg\underset {P\in C} {max} H(P)$$

2.3 最大熵模型的学习

  得到最大熵模型的定义后，便可对该模型进行学习，而最大熵模型学习的过程实际上就是其求解过程，因为通过学习选择的模型就是最大熵模型。最大熵模型的定义分为两部分，首先是提出约束条件，再选择最优模型。因此最大熵模型的学习可以形式化为约束最优化问题。

  形式化为如下最优化问题：

$$\begin{aligned} \underset {P\in C} {max} \;\;\; &H(P) = -\sum_{x,y} \widetilde P(x)P(y|x) log P(y|x) \\ s.t. \;\;\;\; &E_P(f_i) = E_{\widetilde P}(f_i), \;\;\;\;i=1,2,\cdots, n \\ &\sum_yP(y|x) =1 \end{aligned}$$

  依据凸优化，我们常常喜欢处理凸函数，所以将原问题转化为等价的最小化问题：

$$\begin{aligned} \underset {P\in C} {min} \;\;\; &-H(P) = \sum_{x,y} \widetilde P(x)P(y|x) log P(y|x) \\ s.t. \;\;\;\; &E_P(f_i) = E_{\widetilde P}(f_i), \;\;\;\;i=1,2,\cdots, n \\ &\sum_yP(y|x) =1 \end{aligned}$$

  这是一个典型的线性规划问题，求解这种带约束的线性规划问题，通常的做法都是将其转化为无约束的最优化问题，而求解这个无约束的最优化问题用的方法又常常是求解其对偶问题。带约束问题转化为无约束问题的方法就是我们常用的拉格朗日乘数法：

$$\begin{aligned} L(P,w) =& -H(P) +w_0(1-\sum_yP(y|x))+\sum_{i=1}^nw_i(E_p(f_i) - E_{\widetilde P}(f_i))\\ =& \sum_{x,y}\widetilde P(x) P(y|x) log P(Y|x) +w_0(1-\sum_yP(y|x))\\ + &\sum_{i=1}^n w_i \left ( \sum_{x,y} \widetilde P(x,y) logP(y|x) + \sum_{x,y} \widetilde P(x) P(y|x) log P(y|x) \right ) \end{aligned}$$

  得到无约束的广义拉格朗日函数后，如果按照普通的拉格朗日乘数法求极值的步骤，现在就应该对$P,w$求偏导了，然后解一大堆方程组。但是在这个问题中，对$w$求偏导的难度较大。其实对$w$求偏导后的结果就是原问题中的约束条件，里面各种$P$，并且需要求出$P$满足的各种约束，复杂度很高。

  因此继续将这个问题拆解为两个问题：先求$\underset w {max}\;\;\;L(P,w)$，再计算

$$\underset {P\in C} {min} \;\underset w {max}\;\;\;L(P,w)$$

  这个函数称为广义拉格朗日函数的极小极大问题，也叫原始问题。这个函数与原拉格朗日函数是等价的，因为在求对关于$w$的极大化时，若该问题中的约束条件不满足，则$w$系数后面的内容就不为0，那么极大化这个函数使得$w$会往正无穷或负无穷变化，最终使得函数极大化结果为正无穷。若满足约束条件的话，这个函数始终等于$-H(P)$。于是这两步分解，使得函数满足了约束条件，同时也将对$P,w$的处理分解开来，让我们有机会处理这个问题。具体的分析写在单独的对偶性分析里，这里不再赘述。关于对偶性可以参数李航老师书后面的附录，和Convex Optimization Overview (cnt’d) 及相关凸优化书籍。

  前面说了，对$w$求偏导的结果十分复杂，若直接求解极小极大问题对优化工作量没有帮助。根据凸优化理论，$L(P,w)$是凸函数，因此我们可以求解其对偶问题来减少工作量，且对偶问题的解与原始问题的解是等价的——满足KKT条件。

其对偶问题是

$$\underset w {max}\; \underset {P\in C} {min} \; L(P,w)$$

如此，我们可以先对$P$求导，对它求导的结果看起来会舒服很多，其中极小化得到的函数是关于$w$的函数，它就是对偶函数，记为

$$\Psi(w) = \underset {P\in C} {min} \; L(P,w) = L(P_w,w)$$

它的解自然是一个关于$w$的概率模型$P$，记作

$$P_w = arg \underset {P\in C} {min} \; L(P,w) = P_w(y|x)$$

再用外部的极大化确定$w$的参数取值，带入$P_w$即得到最大熵模型。

  具体过程如下：

1. 求解内部极小问题

  对$P$求偏导

$$\begin{aligned} \frac {\partial L(P,x)} {\partial P(y|x)} = & \sum_y \widetilde P(x) (logP(y|x)+1)-\sum_y w_0 -\sum_{x,y} \left ( \widetilde P(x) \sum_{i=1} ^n w_i f_i(x,y) \right)\\ =& \sum_{x,y} \widetilde P(x) \left ( logP(y|x) + 1 -\sum_x \widetilde P(x)\sum_y w_0 -\sum_{i=1}^n w_if_i(x,y) \right)\\ =& \sum_{x,y} \widetilde P(x) \left ( logP(y|x) + 1 - w_0 -\sum_{i=1}^n w_if_i(x,y) \right)\\ \end {aligned}$$

令该式为0，$\widetilde P(x) > 0$解得

$$P(y|x) = exp \left ( \sum_{i=1}^n w_i f_i(x,y) + w_0 -1 \right)= \frac {exp \left ( \sum_{i=1}^n w_i f_i(x,y) \right)} {exp(1-w_0)}$$

  得到的这个$P(y|x)$可能并不是一个真正的概率，因为求解过程中消去了一些变量，比如$\widetilde P(x)$。因此，它应该只是表达了所有可能取值之间的一个比值关系，是一个非规范化概率，所有对其规范化，由于

$$\sum_yP(y|x) = 1$$

得到规范化因子

$$Z_w(x) = \sum_y exp\left (\sum_{i=1} {n} w_i f_i (x,y)\right)$$

ps: $exp(1-w_0)$是常数会被约去

   最终得到

$$P_w(y|x) = \frac 1 {Z_w(x)} exp\left (\sum_{i=1} {n} w_i f_i (x,y)\right)$$

1. 最大化对偶函数$\Psi(w)$

  将得到的结果带入$\Psi(w) = L(P_w,w)$，接着求解对偶函数$\Psi(w)$的极大化问题

$$\underset w {max} \Psi(w)$$

其解为

$$w^* = arg \underset w {max} \; \Psi(w)$$

求解方法同样是对$w$求偏导令为0即可。

  得到参数$w^*$后带入$P_w(y|x)$即得最大熵模型。

3. 极大似然估计

  下面证明最大熵模型的极大似然估计等价与上面用到的对偶函数的极大化。最大熵的极大似然函数使用的是对数似然函数，关于这个似然函数在我的另一篇笔记《熵、交叉熵、极大似然》)中有提到和推导。下面直接给出其形式

$$L_{\widetilde P}(P) = log \prod_{x,y}P(y|x)^{\widetilde P(x,y)} = \sum_{x,y} \widetilde P(x,y) log P(y|x)$$

将$P_w(y|x)$带入

$$\begin{aligned} L_{\widetilde P}(P_w) =& \sum_{x,y} \widetilde P(x,y) \sum_{i=1} ^n w_i f_i(x,y) -\sum_{x,y} \widetilde P(x,y) log Z_w(x)\\ =& \sum_{x,y} \widetilde P(x,y) \sum_{i=1} ^n w_i f_i(x,y) -\sum_x\widetilde P(x) log Z_w(x) \end{aligned}$$

  对于对偶函数

$$\begin{aligned} \Psi(w) =& \sum_{x,y} \widetilde P(x) P_w(y|x)log P_w(y|x) + \sum_{i=1} ^n w_i \left ( \sum_{x,y} \widetilde P(x,y) f_i(x,y) - \sum_{x,y} \widetilde P(x) P_w(y|x)f_i(x,y) \right)\\ =&\sum_{x,y} \widetilde P(x,y) \sum_{i=1}^n w_i f_i(x,y) +\sum_{x,y} \widetilde P(x) P_w(y|x) \left ( logP_w(y|x) - \sum_{i=1}^n w_i f_i (x,y) \right)\\ =& \sum_{x,y} \widetilde P(x,y) \sum_{i=1} ^n w_i f_i(x,y) -\sum_{x,y} \widetilde P(x,y) log Z_w(x)\\ =& \sum_{x,y} \widetilde P(x,y) \sum_{i=1} ^n w_i f_i(x,y) -\sum_x\widetilde P(x) log Z_w(x) \end{aligned}$$

两个过程的最后一步都用到$\sum_yP(y|x) = 1$。

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

4. 最大熵与logistic回归的关系

  在本章中，logistic回归和最大熵模型放在一起，那么它们有什么关系呢。实际上，最大熵模型可以退化为logistic回归模型。

  首先限定y是一个二元变量，不失一般性，假设取值为0,1.即$y\in \{ 0,1\}$，再定义关于x，y的特征函数为

$$f(x,y) = \begin{cases} g(x) & y=1\\ 0&y=0 \end{cases}$$

它与最大熵模型特征函数的区别在于，最大熵模型特征函数是限定了$x,y$之间的关系，而这里显然没有。将其带入最大熵模型

$$\begin{aligned} P(y=1|x) = &\frac {exp(w\cdot f(x,1))} {exp(w\cdot f(x,0))+exp(w\cdot f(x,1))}\\ =& \frac {exp(w\cdot g(x)} {exp(0)+exp(w\cdot g(x))}\\ =& \frac 1 {exp(-w\cdot g(x))+1}\\ \end{aligned}$$

当$g(x)$为sigmoid函数时，这就是logistic回归模型。

同理可计算$P(y=0|x)$。

关于模型的最优化算法单独写一篇。

5. 总结

  logistic回归是一个对数线性模型，它与线性模型相比有更好的特性，可以处理范围波动较大的数据。其学习通过极大似然估计，且其似然函数形如伯努利分布的似然函数。

  最大熵模型中用到了熵的概念和最大熵原理，熵描述一个模型内部的混乱程度或不确定性的大小。最大熵原理表明，当我们没有更多的信息来确定一个模型的时候，信息量最大（不确定性最大）的模型是理想的选择。熵似乎与极大似然有着异曲同工的关系，在另一篇笔记《熵、交叉熵、极大似然》)中也说明了交叉熵与极大似然在广义伯努利分布下的等价的。

  最大熵模型的学习用到了拉格朗日的对偶性，这是因为将条件线性规划表达为无约束优化问题后，原始问题仍较难计算，于是根据凸优化理论，计算原始问题的对偶问题，只要满足KKT条件，原始问题与对偶问题的解就是等价的。

  最大熵模型与logistic的关系可通过特征函数联系起来，特征函数相当于人为的帮助模型排除一些不合理的情况。最大熵模型是一个判别模型，在计算上可以使用最优化算法。后面学到的条件随机场也是一个判别模型，因此在计算上二者有很多类似的地方，应考虑它们计算上的共通点。不过其思想还是基于概率图模型的，因此在理论思想方面应与隐马尔可夫模型对比。

6. Reference

[1] 统计学习方法

[2] 如何理解最大熵中的特征函数

[3] Convex Optimization Overview (cnt’d)

[4] PRML

[5] 最小化交叉熵与极大似然函数