机器学习算法03-logistics和最大熵模型

本文将复习并记录的最大熵&logistics模型的推导和思想。

本文将要介绍的内容如下图所示：

1. Logistic 函数的历史起源

Logistic 函数的思想最早可以追溯到 1838 年由比利时数学家Verhulst提出。Verhulst 当时面临的问题是如何修正 Malthus 人口增长模型的局限性。Malthus 模型假设人口呈几何级数增长，即 $P(t) = P_0 e^{rt}$ ，但这一模型忽略了环境承载能力有限的事实，就像现发达国家的年人口增长规模远低于指数函数做预测的那样。Verhulst 引入了人口承载上限的概念，认为人口增长速度会随着人口规模逼近环境上限而逐渐衰减。

于是乎，Verhulst 建立了著名的 logistic 微分方程。设 $N(t)$ 为时刻 $t$ 的人口数量，$K$ 为环境承载容量，$r$ 为种群增长潜力指数，则增长率可表示为：

$$r_{t} = \frac{dN}{dt} = rN \left(1 - \frac{N}{K}\right)$$

令 $x(t) = \frac{N}{K}$, 简化得：

$$\begin{aligned} \frac{dx}{dt} &= rx(1-x) \\ \frac{dx}{x(1-x)} &= r\ dt \\ \end{aligned}$$

积分：

$$\begin{aligned} \ln(x) - \ln(1-x) &= rt + c \\ \frac{x}{1-x} &= e^{rt+c} \end{aligned}$$

解得，常数的正负号无所谓：

$$\begin{aligned} x = \frac{N}{K} = \frac{1}{1 + e^{-rt+c}} \end{aligned}$$

如图函数的曲线为s型，值域仅在 [0,1] 之间。

2. logistics 回归模型

从人口增长模型到分类模型，logistics模型是如何完成这一转变的？首先其形式保证了概率分布的输出值落在 $(0, 1)$ 区间内,分布和密度函数可写作:

$$\begin{aligned} F(x)=P(X \leqslant x)=\frac{1}{1+\mathrm{e}^{-(x-\mu) / \gamma}} \\ f(x)=F^{\prime}(x)=\frac{\mathrm{e}^{-(x-\mu) / \gamma}}{\gamma\left(1+\mathrm{e}^{-(x-\mu) / \gamma}\right)^{2}} \end{aligned}$$

将二分类任务引入，对于类别$Y=\{0,1\}$,：

$$\begin{aligned} P(Y=1 \mid x)=\frac{\exp (w \cdot x+b)}{1+\exp (w \cdot x+b)} \\ P(Y=0 \mid x)=\frac{1}{1+\exp (w \cdot x+b)} \end{aligned}$$

将两者相比，得到几率的角度来理解。几率定义为发生概率与不发生概率之比，取对数后得到 logit 函数：

$$\log \frac{P(Y=1|\mathbf{x})}{1-P(Y=1|\mathbf{x})} = w\cdot x + b$$

注意我这里的向量大小无论 $w,x$ 均为 n 维向量，有些书上将$b$写入了向量中所以为 n+1维。

通过这个回归式就可将线性函数$wx+b$赋予概率上的意义——每个特征$x_{i}$ 对几率的贡献是可加的。对于 $w$ 的参数估计采用极大似然估计方法，将对数似然函数写作：

$$\begin{aligned} L(w) & =\sum_{i=1}^{N}\left[y_{i} \log \pi\left(x_{i}\right)+\left(1-y_{i}\right) \log \left(1-\pi\left(x_{i}\right)\right)\right] \\ & =\sum_{i=1}^{N}\left[y_{i} \log \frac{\pi\left(x_{i}\right)}{1-\pi\left(x_{i}\right)}+\log \left(1-\pi\left(x_{i}\right)\right)\right] \\ & =\sum_{i=1}^{N}\left[y_{i}\left(w \cdot x_{i}+b\right)-\log \left(1+\exp \left(w \cdot x_{i}+b\right)\right]\right. \end{aligned}$$

求$L(w)$的最大值，也就是一系列的 $\frac{\partial L}{\partial x_i} = 0$ 方程求解，得到参数。

对于多类分类问题，逻辑斯谛回归可以推广为多项逻辑斯谛回归，采用 softmax 函数进行归一化，归根到底 softmax 就是 logistics 函数在多维的推广，继承了 logistics 函数的映射特点，让它在很多领域中大方光彩，比如神经网络嘻嘻：

$$P(Y=k|\mathbf{x}) = \frac{\exp(\mathbf{w}_k^\top\mathbf{x})}{1 + \sum_{j=1}^{K-1}\exp(\mathbf{w}_j^\top\mathbf{x})}, \quad k=1,\dots,K-1$$

确保各类别概率之和为 1，那么 $P(Y=K|\mathbf{x})$ 的分子就必须唯一参考二分类的第二个式子。

3. 最大熵模型

3.1. 信息熵的基本概念

在已知部分信息的前提下，应当选择熵最大的概率分布，即在满足已知约束的条件下保持最大的不确定性，这就是最大熵原理。我认为把信息定义为不确定性是一个很好的理解方式，在这里简要的介绍一下可能需要用到的概念，在信息论中衡量有多少信息，也就是多少不确定性的信息熵定义为：

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

用于度量概率分布的不确定性，注意了千万别和$S(x) = \int \frac{\delta Q}{T} dT$混了，this is 热力学中的熵。

互信息是两个随机变量之间相互依赖性的信息量，换句话说就是 知道了X之后的Y的信息熵减少的量，互信息永远非负，写作：

$$I(X ; Y)=\sum_{x, y} p(x, y) \log \frac{p(x, y)}{p(x) p(y)}$$

从概率和期望的角度可以把熵理解为 $-log P(\cdots)$ 的期望
.条件熵可以写为，衡量的在$X$已知后的$Y$剩余的不确定性是：

$$H(Y|X) = -\sum_x\sum_y P(x,y) \log P(y|x) = H(Y) - I(X;Y)$$

证明：

$$\begin{aligned} I(X ; Y) & =\sum_{x, y} p(x, y) \log \frac{p(x, y)}{p(x) p(y)} \\ & =\sum_{x, y} p(x, y) \log \frac{p(y \mid x) p(x)}{p(x) p(y)} \\ & =\sum_{x, y} p(x, y) \log \frac{p(y \mid x)}{p(y)} \\ & =\sum_{x, y} p(x, y) \log p(y \mid x)-\sum_{x, y} p(x, y) \log p(y) \\ & =-H(Y \mid X)-\sum_{y}\left(\sum_{x} p(x, y)\right) \log p(y) \\ & =-H(Y \mid X)-\sum_{y} p(y) \log p(y) \\ & =-H(Y \mid X)+H(Y) \end{aligned}$$

3.2. 最大熵模型的基本形式

最大熵原理认为要选择的概率模型首先必须满足已有的事实，即约束条件。在没有更多信息的情况下，那些不确定的部分都是＂等可能的＂。最大熵原理通过熵的最大化来表示等可能性；换句话说最大熵原理认为最好的概率模型是熵最大的，即不确定性最大最富有 information 的。

从上面定义的条件熵开始，我们可以展开前面的概率密度分布$P(x,y) = P(x)\cdot P(y|x)$，那么条件熵的形式就可以写作为$H(Y|X)= -\sum_x\sum_y P(x)\cdot P(y|x)\cdot \log P(y|x)$。面对分类任务，我们希望这个模型可以起到输入一连串的“特征变量($X$)”输出“这个类别的概率( $P(y = 0 \ or\ 1\ |\ x)$ )”。

但首先我们模型必须满足的是任务中提供的必要条件，使用特征函数 $f(x, y)$进行描述。特征函数 $f(x, y)$ 通常取值为 0 或 1，若输入输出之间满足某一特定事实则为1，不满足则为0。说起来简单，但这里最重要的问题是如何让模型可以通过数据来学习呢？简单的想法是通过学习数据上的比较宏观的指标—期望，来模仿这种规律。

对于数据端而言，归纳出的经验分布写作$\bar P(x,y)$，期望则为：$E_{\hat P} = \sum_{x,y} \bar P(x,y) \cdot f(x,y)$

对于模型端而言，x，y经验分布写作$P(x,y)$，期望则为：$E_{P} = \sum_{x,y} P(x,y) \cdot f(x,y) = \sum_{x,y} P(x) \cdot P(y|x) \cdot f(x,y)$。根据大数定理，在样本足够多的情况下，$\bar P(x) \rightarrow P(x)$，期望改写为：$E_{P} = \sum_{x,y} \bar P(x) \cdot P(y|x) \cdot f(x,y)$。

概括地来说，最大熵模型学习目标找到一个条件概率分布 $P(y|x)$，使其熵最大，同时满足模型期望等于经验期望的约束条件，因而可以把优化问题写为

$$\begin{aligned} &\max_{P \in C} \ H(P) =-\sum_{x, y} \bar P(x) P(y \mid x) \log P(y \mid x) \\ & s.t. \quad \bar E_{P}(f_{i}(x,y)) = E_{P}(f_{i}(x,y)) \qquad i = 1,2,\dots,n \qquad (\text{特征函数约束})\\ & \qquad \sum _{y} P(y|x)= 1 \qquad (\text{概率归一化})\end{aligned}$$

小小调整一下变成最小化问题：

$$\begin{aligned} &\min_{P \in C} \ H(P) =-\sum_{x, y} \bar P(x) P(y \mid x) \log P(y \mid x) \\ & s.t. \quad \bar E_{P}(f_{i}(x,y)) - E_{P}(f_{i}(x,y)) =0\qquad i = 1,2,\dots,n \qquad (\text{特征函数约束})\\ & \qquad \sum _{y} P(y|x)= 1 \qquad (\text{概率归一化})\end{aligned}$$

3.3. 优化问题转化

通过引入广义拉格朗日乘子法求解这一带约束的优化问题：

$$\begin{aligned} L\left(P, \mathbf{w}\right)=-H(P)+\sum_{i=1}^{n} w_{i}\left(E_{\bar{P}}\left(f_{i}\right)-E_{P}\left(f_{i}\right)\right)+w_{0}\left(1-\sum_{y} P(y \mid x)\right) \\ = -H(P)+\sum_{i=1}^{n} w_{i}(\sum_{x,y} \bar P(x,y) \cdot f(x,y)+ \sum_{x,y} \bar P(x) \cdot P(y|x) \cdot f(x,y)) \\ +w_{0}\left(1-\sum_{y} P(y \mid x)\right) \end{aligned}$$

将原始问题转换成对偶问题，因为该拉格朗日函数是凸函数且满足KKT条件，两问题等价：

$$\min _{P \in \mathbf{C}} \max _{ \mathbf{w}} L(P, \mathbf{w}) \Longleftrightarrow \max _{ \mathbf{w}} \min _{P \in \mathbf{C}} L(P, \mathbf{w})$$

$\min _{P \in \mathbf{C}} L(P, \mathbf{w})$ 是一个关于 $\mathbf{w}$ 的函数，记作 $\Psi(\mathbf{w})$ ，而 $L(P, \mathbf{w})$ 是一个关于 $P(x|y)$ 的函数对其求偏导：

$$\begin{aligned} \frac{\partial L\left(P, \mathbf{w}\right)}{\partial P(x|y)} = \sum_{x,y} \bar P(x) (log P(y|x)+1)- \sum^{n}_{i=1}\sum_{x,y} \bar P(x) w_{i} f_{i}(x,y) -\sum_{y} w_{0} \\ = \sum_{x,y} \bar P(x) (log P(y|x)+1)- \sum^{n}_{i=1}\sum_{x,y} \bar P(x) w_{i} f_{i}(x,y) -\sum_{x,y} w_{0} \bar P(x) \\ =\sum_{x,y} \bar P(x) (log P(y|x)+1-\sum^{n}_{i=1}w_{i} f_{i}(x,y) -w_{0}） = 0 \end{aligned}$$

分布恒为正，因而第二项为0：

$$\begin{aligned} log P(y|x)=\sum^{n}_{i=1}w_{i} f_{i}(x,y) +w_{0}-1 \\ P(y|x) = \frac{e^{\sum^{n}_{i=1}w_{i} f_{i}(x,y) }}{e^{w_{0}-1}}\\ \text{带入概率的的归一性质：} \sum_{y} P(y|x)= 1 \\ \sum_{y} e^{\sum_{i=1}^n w_i f_i(x,y) } = e^{w_{0}-1} \\ \text{P(x|y)改写为：} P(x|y) = \frac{e^{\sum_{i=1}^n w_i f_i(x,y) }}{\sum_{y} e^{\sum_{i=1}^n w_i f_i(x,y) } } = \frac{e^{\sum_{i=1}^n w_i f_i(x,y) }}{Z_w(x)} \end{aligned}$$

其中 $Z_w(x) = \sum_y \exp\left(\sum_{i=1}^n w_i f_i(x,y)\right)$ 为归一化因子。当特征函数选择适当时，最大熵模型与逻辑斯谛回归模型是等价的，居然通过不同的优化路径（最大熵原理 vs. 极大似然估计）到达了相同的解。

4. 模型学习的优化算法

逻辑斯谛回归和最大熵模型的参数学习本质上都是对数似然函数的最大化问题。对于逻辑斯谛回归，常用的优化方法包括梯度下降法、牛顿法和拟牛顿法（如 BFGS）。拟牛顿法通过近似 Hessian 矩阵的逆矩阵，在保持较快收敛速度的同时避免了直接计算 Hessian 矩阵的高昂代价，特别适合大规模问题。优化目标可写为：

$$\min_{\mathbf{w}} -\ell(\mathbf{w})$$

最大熵模型的传统学习算法是改进的迭代尺度法（Improved Iterative Scaling, IIS）。该算法的核心思想是每次迭代只更新一个参数，通过求解一个单变量方程来确定参数的增量：

$$\sum_{x,y} \tilde{P}(x)P_w(y|x)f_i(x,y)\exp(\delta_i f^*(x,y)) = \mathbb{E}_{\tilde{P}}[f_i]$$

其中 $f^{*}(x,y) = \sum_i f_i(x,y)$。IIS 算法的优点是每次迭代都能保证对数似然函数增加，但收敛速度相对较慢。在实际应用中，拟牛顿法往往比 IIS 更为高效。

5. 模型的局限性&对比

逻辑斯谛回归虽然简单有效，但也存在一些固有的局限性。

首先，它只能产生线性决策边界，对于非线性可分的问题需要人工构造非线性特征。其次，模型对特征之间的多重共线性较为敏感，高度相关的特征会导致参数估计不稳定。此外，在类别不平衡的场景下，模型对少数类的预测效果往往较差。

从建模方式来看，逻辑斯谛回归属于判别式模型，直接对条件概率 $P(Y|X)$ 进行建模；而朴素贝叶斯属于生成式模型，对联合概率 $P(X, Y) = P(X|Y)P(Y)$ 进行建模。判别式模型假设较弱，通常需要更多训练数据，但渐近误差更低；生成式模型假设较强（如特征条件独立性），在小数据场景下表现更好，但渐近误差相对较高。两种模型各有优劣，应根据具体任务和数据特点进行选择。