在Introduction中，我们简单提到了Logistic回归模型，这是最简单也是最常见的分类模型。本节我们将从最基本的二项逻辑斯蒂回归开始，推广到多项逻辑斯蒂回归，然后和最大熵模型进行比较。

逻辑斯蒂回归模型

Logistic分布

  • 首先定义Logistic分布的分布函数与概率密度函数： F(x)=11+e−x−μsf(x)=e−x−μss(1+e−x−μs)2\begin{aligned} F(x)&=\frac{1}{1+e^{-\frac{x-\mu}{s}}}\\ f(x)&=\frac{e^{-\frac{x-\mu}{s}}}{s\left(1+e^{-\frac{x-\mu}{s}}\right)^2} \end{aligned} 其中μ∈R\mu\in\R为位置参数，s>0s>0为形状参数。分布图像如下：logistic distribution
    可以看到分布函数呈S形（Sigmoid函数就是μ=0,s=1\mu=0,s=1时的曲线），且关于(μ,12)\displaystyle\left(\mu,\frac{1}{2}\right)中心对称。

二项逻辑斯蒂回归

  • 二项逻辑斯蒂回归模型的输出是二分类，其条件概率分布为参数化的Logistic分布，即 P(y=1∣x)=11+e−(w⋅x+b)P(y=0∣x)=e−(w⋅x+b)1+e−(w⋅x+b)\begin{aligned} P(y=1|\mathbf{x})&=\frac{1}{1+e^{-(\mathbf{w}\cdot\mathbf{x}+b)}}\\ P(y=0|\mathbf{x})&=\frac{e^{-(\mathbf{w}\cdot\mathbf{x}+b)}}{1+e^{-(\mathbf{w}\cdot\mathbf{x}+b)}}\\ \end{aligned} 其中x\mathbf{x}为MM维特征向量，w\mathbf{w}为MM维权重向量，bb为偏置。模型就是根据两个条件概率的大小比较得到最终的输出。

    有时也将偏置项并入权重向量，即w=(w1,w2,⋯ ,wM,b)⊤,x=(x1,x2,⋯ ,xM,1)⊤\mathbf{w}=(w_1,w_2,\cdots,w_M,b)^\top,\mathbf{x}=(x_1,x_2,\cdots,x_M,1)^\top。

  • 这个模型也可以看作对输入进行仿射变换（线性变换+平移）后，再经过一次非线性（Sigmoid）变换。【其输出与前馈神经网络中神经元的变换等价】
  • 与线性模型的关系：考虑对数几率（logit函数） logit(P)=log⁡P1−P\text{logit}(P)=\log\frac{P}{1-P} 那么将上述两个概率代入得 log⁡P(y=1∣x)1−P(y=1∣x)=w⋅x+blog⁡P(y=0∣x)1−P(y=0∣x)=−(w⋅x+b)\begin{aligned} \log\frac{P(y=1|\mathbf{x})}{1-P(y=1|\mathbf{x})}&=\mathbf{w}\cdot\mathbf{x}+b\\ \log\frac{P(y=0|\mathbf{x})}{1-P(y=0|\mathbf{x})}&=-(\mathbf{w}\cdot\mathbf{x}+b) \end{aligned} 因此模型具有良好的解释性：每一维特征对应的权重表示该特征对分类的贡献（大小与方向）。
  • 二项逻辑斯蒂回归模型还有另一种形式——分类标签y={−1,+1}y=\{-1,+1\}。此时考虑负对数损失函数（分类模型的目标是正确输出条件概率尽量接近11），那么 −log⁡2P(y=+1∣x)=−log⁡211+e−(w⋅x+b)=log⁡2[1+e−yf(x)],−log⁡2P(y=−1∣x)=−log⁡2e−(w⋅x+b)1+e−(w⋅x+b)=log⁡2[1+e−yf(x)]\begin{aligned} -\log_2 P(y = +1 | \mathbf{x}) &= -\log_2 \frac{1}{1 + e^{-(\mathbf{w} \cdot \mathbf{x} + b)}}\\ &= \log_2 \left[1 + e^{-y f(\mathbf{x})}\right],\\[10pt] -\log_2 P(y = -1 | \mathbf{x}) &= -\log_2 \frac{e^{-(\mathbf{w}\cdot \mathbf{x} + b)}}{1 + e^{-(\mathbf{w} \cdot \mathbf{x} + b)}}\\ &= \log_2 \left[1 + e^{-y f(\mathbf{x})}\right] \end{aligned} 因此可以统一为对数损失或逻辑斯谛损失log⁡2[1+e−yf(x)]\log_2 \left[1 + e^{-y f(\mathbf{x})}\right]。

多项逻辑斯蒂回归

  • 将上述模型从二分类推广到多分类，就得到了多项逻辑斯蒂回归模型。其条件概率分布形式如下： P(y=ck∣x)=exp⁡(wk⋅x+bk)1+∑k=1K−1exp⁡(wk⋅x+bk),k=1,2,⋯ ,K−1P(y=cK∣x)=11+∑k=1K−1exp⁡(wk⋅x+bk)\begin{aligned} P(y = c_k \mid \mathbf{x}) &= \frac{\exp(\mathbf{w}_k \cdot \mathbf{x} + b_k)}{\displaystyle 1 + \sum_{k=1}^{K-1} \exp(\mathbf{w}_k \cdot \mathbf{x} + b_k)}, \quad k = 1, 2, \cdots, K-1 \\ P(y = c_K \mid \mathbf{x}) &= \frac{1}{\displaystyle 1 + \sum_{k=1}^{K-1} \exp(\mathbf{w}_k \cdot \mathbf{x} + b_k)} \end{aligned} 由此可知多项逻辑斯蒂回归模型（包含二项逻辑斯蒂回归模型）属于概率判别模型。在计算所有类别的条件概率后，模型选择最大概率对应的类别作为输出结果。
  • 与线性模型的关系：类似上面的推导，我们可以将一个类别（y=cKy=c_K）作为参照类，那么其他类别（y∈{c1,⋯ ,cK−1}y\in\{c_1,\cdots,c_{K-1}\}）与参照类的对数几率是关于特征向量x\mathbf{x}的线性函数。
  • 上面的条件概率分布中参数为K−1K-1类，而实际上模型也可以定义在KK类参数上： P(y=ck∣x)=exp⁡(wk⋅x+bk)∑k=1Kexp⁡(wk⋅x+bk),k=1,2,⋯ ,KP(y = c_k \mid \mathbf{x}) = \frac{\exp(\mathbf{w}_k \cdot \mathbf{x} + b_k)}{\displaystyle\sum_{k=1}^{K} \exp(\mathbf{w}_k \cdot \mathbf{x} + b_k)}, \quad k = 1, 2, \cdots, K 这与多分类前馈神经网络输出层形式等价。这个函数也被称为softmax函数。

最大熵模型（maxEnt）

最大熵原理

  • 最大熵原理由杰尼斯【贝叶斯学派代表人物】与1957年提出，其核心是：学习概率模型时，在所有可能的概率模型（分布）中，熵最大的模型是最好的模型。
  • 关于熵的概念已经在决策树章节中阐述。设x\mathbf{x}的概率分布为P(x)P(\mathbf{x})，那么它的熵为 H(P)=−∑x∈XP(x)log⁡P(x)H(P)=-\sum_{\mathbf{x}\in\mathcal{X}}P(\mathbf{x})\log P(\mathbf{x}) 那么可以证明H(P)H(P)在P(x)P(\mathbf{x})为均匀分布时取得最大值log⁡∣X∣\log|\mathcal{X}|（∣X∣|\mathcal{X}|表示X\mathcal{X}取值个数）。
    因此，利用最大熵原理估计概率就是在约束条件下尽量取等概率。

最大熵模型定义

  • 给定训练数据集，考虑联合分布P(x,y)P(\mathbf{x},y)的经验分布和P(x)P(\mathbf{x})的经验分布，分别用P~(x,y)\tilde{P}(\mathbf{x},y)和P~(x)\tilde{P}(\mathbf{x})表示。那么它们的表达式为： P~(x,y)=N(x,y)N,P~(x)=N(x)N.\tilde{P}(\mathbf{x},y)=\frac{N(\mathbf{x},y)}{N},\quad \tilde{P}(\mathbf{x})=\frac{N(\mathbf{x})}{N}. 其中N(x,y),N(x)N(\mathbf{x},y),N(\mathbf{x})和NN分别表示训练样本中x\mathbf{x}和yy同时出现的频数，x\mathbf{x}出现的频数和总训练样本量。
  • 然后定义特征函数f(x,y)f(\mathbf{x},y)，其类似于示性函数，即x\mathbf{x}与yy满足某种条件时值为11，否则值为00。
  • 接着考虑特征函数关于联合经验分布的期望 EP~(f)=∑x,yP~(x,y)f(x,y)\mathbb{E}_{\tilde{P}}(f)=\sum_{\mathbf{x},y}\tilde{P}(\mathbf{x},y)f(\mathbf{x},y) 以及关于模型与先验分布P~(x)\tilde{P}(\mathbf{x})的期望 EP(f)=∑x,yP~(x)P(y∣x)f(x,y)\mathbb{E}_{P}(f)=\sum_{\mathbf{x},y}\tilde{P}(\mathbf{x})P(y|\mathbf{x})f(\mathbf{x},y) 对此，我们假设两个期望相等，即EP~(f)=EP(f)\mathbb{E}_{\tilde{P}}(f)=\mathbb{E}_P(f)，这样就得到了模型的约束条件。如果总共MM个特征函数fj(x,y),j=1,2,⋯ ,Mf_j(\mathbf{x},y),j=1,2,\cdots,M，那么就总共MM个约束条件。
  • 综上，我们得到最大熵模型的定义：假设满足所有约束条件的模型集合为 C≡{P∈P∣EP(fj)=EP~(fj),j=1,2,⋯ ,M}\mathcal{C} \equiv \left\{ P \in \mathcal{P} \mid \mathbb{E}_P(f_j) = \mathbb{E}_{\tilde{P}}(f_j), \quad j = 1, 2, \cdots, M \right\} 定义在条件概率分布P(y∣x)P(y|\mathbf{x})上的条件熵为 H(P)=−∑x,yP~(x)P(y∣x)log⁡P(y∣x)H(P) = - \sum_{\mathbf{x},y} \tilde{P}(\mathbf{x}) P(y|\mathbf{x}) \log P(y|\mathbf{x}) 则模型集合C\mathcal{C}中条件熵H(P)H(P)最大的模型称为最大熵模型。

    关于条件熵表达式如何得到：

    H(P)=∑i=1∣X∣P~(xi)H(y∣x=xi)=∑i=1∣X∣P~(xi)⋅∑j=1∣Y∣−P(yi∣xi)log⁡P(yi∣xi)=−∑i=1∣X∣∑j=1∣Y∣P~(xi)⋅P(yi∣xi)log⁡P(yi∣xi)=−∑x,yP~(x)P(y∣x)log⁡P(y∣x).\begin{aligned} H(P)&=\sum_{i=1}^{|\mathcal{X}|}\tilde{P}(x_i)H(y|\mathbf{x}=x_i)\\ &=\sum_{i=1}^{|\mathcal{X}|}\tilde{P}(x_i)\cdot\sum_{j=1}^{|\mathcal{Y}|}-P(y_i|x_i)\log P(y_i|x_i)\\ &=-\sum_{i=1}^{|\mathcal{X}|}\sum_{j=1}^{|\mathcal{Y}|}\tilde{P}(x_i)\cdot P(y_i|x_i)\log P(y_i|x_i)\\ &=- \sum_{\mathbf{x},y} \tilde{P}(\mathbf{x}) P(y|\mathbf{x}) \log P(y|\mathbf{x}). \end{aligned}

最大熵模型的学习

  • 通过定义，我们可以发现最大熵模型的学习过程实际就是一个带约束的最优化过程： max⁡P∈CH(P)=−∑x,yP~(x)P(y∣x)log⁡P(y∣x)s.t.EP(fj)=EP~(fj),j=1,2,⋯ ,M∑yP(y∣x)=1\begin{aligned} \max_{P \in \mathcal{C}} \quad & H(P) = -\sum_{\mathbf{x},y} \tilde{P}(\mathbf{x}) P(y|\mathbf{x}) \log P(y|\mathbf{x}) \\[10pt] \text{s.t.} \quad & \mathbb{E}_P(f_j) = \mathbb{E}_{\tilde{P}}(f_j), \quad j = 1, 2, \cdots, M \\[5pt] & \sum_y P(y|\mathbf{x}) = 1 \end{aligned}
  • 具体优化推导如下（原理可参考CS 127）：
推导过程
  • 引入拉格朗日乘子，定义拉格朗日函数L(P,w)L(P,\mathbf{w})： L(P,w)≜−H(P)+w0(1−∑yP(y∣x))+∑j=1Mwj(EP~(fj)−EP(fj))=∑x,yP~(x)P(y∣x)log⁡P(y∣x)+w0(1−∑yP(y∣x))+∑j=1Mwj(∑x,yP~(x,y)fj(x,y)−∑x,yP~(x)P(y∣x)fj(x,y))\begin{aligned} L(P,\mathbf{w})&\triangleq -H(P)+w_0\left(1-\sum_y P(y|\mathbf{x})\right)+\sum_{j=1}^Mw_j(\mathbb{E}_{\tilde{P}}(f_j)-\mathbb{E}_P(f_j))\\ = &\sum_{\mathbf{x},y} \tilde{P}(\mathbf{x})P(y|\mathbf{x})\log P(y|\mathbf{x}) + w_0\left(1-\sum_y P(y|\mathbf{x})\right) \\ &+ \sum_{j=1}^M w_j \left( \sum_{\mathbf{x},y} \tilde{P}(\mathbf{x},y)f_j(\mathbf{x},y) - \sum_{\mathbf{x},y} \tilde{P}(\mathbf{x})P(y|\mathbf{x})f_j(\mathbf{x},y) \right) \end{aligned} 于是原始问题变为min⁡P∈Cmax⁡wL(P,w)\displaystyle\min_{P\in\mathcal{C}}\max_{\mathbf{w}}L(P,\mathbf{w})【这里PP表示条件概率P(y∣x)P(y|\mathbf{x})】，由此得到对偶问题为max⁡wmin⁡P∈CL(P,w)\displaystyle\max_{\mathbf{w}}\min_{P\in\mathcal{C}}L(P,\mathbf{w})，且二者得到的解等价。
  • 对于对偶问题，先固定w\mathbf{w}，求min⁡P∈CL(P,w)\displaystyle\min_{P\in\mathcal{C}}L(P,\mathbf{w})。计算L(P,w)L(P,\mathbf{w})对PP的偏导： ∂L(P,w)∂P(y∣x)=∑x,yP~(x)(log⁡P(y∣x)+1)−∑yw0−∑x,y(P~(x)∑j=1Mwjfj(x,y))=∑x,yP~(x)(log⁡P(y∣x)+1−w0−∑j=1Mwjfj(x,y))\begin{aligned} \frac{\partial L(P, w)}{\partial P(y|\mathbf{x})}=&\sum_{\mathbf{x},y} \tilde{P}(\mathbf{x}) \left( \log P(y|\mathbf{x}) + 1 \right) - \sum_y w_0 - \sum_{\mathbf{x},y} \left( \tilde{P}(\mathbf{x}) \sum_{j=1}^M w_j f_j(\mathbf{x}, y) \right)\\ =&\sum_{\mathbf{x},y} \tilde{P}(\mathbf{x}) \left( \log P(y|\mathbf{x}) + 1 - w_0 - \sum_{j=1}^M w_j f_j(\mathbf{x}, y) \right) \end{aligned} 当偏导数为00时 Pw(y∣x)=exp⁡(∑j=1Mwjfj(x,y)+w0−1)=exp⁡(∑j=1Mwjfj(x,y))exp⁡(1−w0)P_w(y|\mathbf{x})=\exp\left(\sum_{j=1}^M w_j f_j(\mathbf{x}, y) + w_0 - 1\right) = \frac{\displaystyle\exp\left(\sum_{j=1}^M w_j f_j(\mathbf{x}, y)\right)}{\exp(1 - w_0)} 再根据条件∑yP(y∣x)=1\displaystyle \sum_y P(y|\mathbf{x}) = 1确定权重w0w_0，得到 Pw(y∣x)=exp⁡(∑j=1Mwjfj(x,y))∑yexp⁡(∑j=1Mwjfj(x,y)).P_w(y|\mathbf{x})=\frac{\displaystyle\exp\left(\sum_{j=1}^M w_j f_j(\mathbf{x}, y)\right)}{\displaystyle\sum_{y}\exp\left(\sum_{j=1}^M w_j f_j(\mathbf{x}, y)\right)}. 最后将Pw(y∣x)P_w(y|\mathbf{x})代入L(P,w)L(P,\mathbf{w})，对w\mathbf{w}取最大值即可。
  • 可以证明最大熵模型学习中的对偶函数最大化等价于最大熵模型的极大似然估计。【过程略】
  • 另一方面，由上述推导可知，最大熵模型与逻辑斯谛回归模型有类似的形式，它们都是对数线性模型。可以认为逻辑斯谛回归模型是最大熵模型的特殊情况。（特征函数包括输入函数）
  • 最大熵原理与指数分布族也有密切的关系。在不同的约束条件下，应用最大熵原理可以得到指数分布族的不同分布。

学习算法

从最优化的观点看，逻辑斯蒂回归模型和最大熵模型的目标函数都是光滑的凸函数，保证能找到全局最优解。常用的学习方法有梯度下降法、牛顿法或拟牛顿法。【具体略，或许在CS 127中会有涉及】