逻辑斯蒂回归和最大熵¶

逻辑斯蒂回归¶

概述¶

逻辑斯蒂回归是一种广泛应用的分类算法。其核心思想是利用 Sigmoid 函数 (也称为 Logistic 函数) 将线性回归的输出结果映射到 (0, 1) 区间内，这个值可以被解释为样本属于某个类别的概率。

模型定义如下（假设标签为0/1,）：

\[ \begin{aligned} P(Y=1|x) &= \frac{\exp(w \cdot x + b)}{1 + \exp(w \cdot x + b)} && (6.3) \\ P(Y=0|x) &= \frac{1}{1 + \exp(w \cdot x + b)} && (6.4) \end{aligned} \]

如果我们将一个事件的几率（odds）理解为发生与不发生概率的比值，那么有：

\[ \log \frac{P(Y=1|x)}{1 - P(Y=1|x)} = w \cdot x \]

这就是说，在逻辑斯谛回归模型中，输出 $Y=1$ 的对数几率是输入 $x$ 的线性函数。

优化方法¶

以极大似然估计为目标，优化参数。一般采用梯度下降法。

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

（在逻辑斯蒂回归中，极大似然估计和交叉熵损失下的梯度一致）

多元分类¶

基本的逻辑斯谛回归模型是二项分类模型，可以将其推广为多项逻辑斯谛回归模型。

假设离散型随机变量 $Y$ 的取值集合是 $\{1, 2, \cdots, K\}$，那么多项逻辑斯谛回归模型是：

\[ \begin{aligned} P(Y=k|x) &= \frac{\exp(w_k \cdot x)}{1 + \sum_{k=1}^{K-1} \exp(w_k \cdot x)}, && k=1,2,\cdots,K-1 \\ P(Y=K|x) &= \frac{1}{1 + \sum_{k=1}^{K-1} \exp(w_k \cdot x)} \end{aligned} \]

最大熵¶

最大熵原理¶

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

这里蕴含了一个假设：在没有更多信息的情况下，那些不确定的部分都是“等可能的”。

而概率分布的熵定义如下： $$ H(P)=-\sum P(x)\log P(x) $$

最大熵模型¶

对于一组样本，我们能获取其经验分布$\tilde{P}$

使用$f$表示特征函数，描述输入和输出y之间的是否满足某一个事实，并取1或者0。

我们假设经验分布和真实分布下，特征函数的期望相同，有： $$ \sum_{x, y} \tilde{P}(x) P(y|x) f_i(x, y) = \sum_{x, y} \tilde{P}(x, y) f_i(x, y) $$

则最大熵模型的学习过程可以形式化为一个约束最优化问题，如下

\[ \begin{aligned} Maximize \; \;&H(P(Y|X)) = - \sum_{x} \tilde{P}(x) \sum_{y} P(y|x) \log P(y|x)\\ s.t. \;\;&\sum_{y} P(y|x) = 1\\ &\sum_{x, y} \tilde{P}(x) P(y|x) f_i(x, y) = \sum_{x, y} \tilde{P}(x, y) f_i(x, y) \end{aligned} \]

通过拉格朗日乘子法，可以求得最大熵模型的条件概率分布 $P(y|x)$ 具有如下形式：

\[ P_w(y|x) = \frac{1}{Z_w(x)} \exp \left( \sum_{i=1}^{k} w_i f_i(x, y) \right) \]

其中：

$w_i$ 是第 $i$ 个特征函数 $f_i$ 的权重参数（拉格朗日乘子）。
$Z_w(x)$ 是归一化因子

特别的，可以证明对以上最优化问题的求解，等价于对最大熵模型求极大似然估计。

而具体的$w_i$，需要采用梯度下降、拟牛顿法等。

与逻辑斯蒂回归的关系¶

逻辑斯蒂回归模型可以看作是最大熵模型在二分类问题上的一个特例。

当特征函数只依赖于输入 $x$ (或者说 $f_i(x,y)$ 对于某个 $y_0$ 是 $f_i(x)$，对于其他 $y \neq y_0$ 是 0)，并且类别 $y$ 只有两个时，最大熵模型就退化为逻辑斯蒂回归的形式。

此时有特征函数 $$ f_i(x,y)=x_j \cdot 1_{y=1} $$

改进的迭代尺度法¶

对于最大熵，我们有对数似然函数：

\[ \begin{aligned} L(w) = \sum_{x,y} \tilde{P}(x,y) \sum_{i=1}^{n} w_i f_i(x,y) - \sum_{x} \tilde{P}(x) \log Z_w(x) \end{aligned} \]

又原权重向量$w$，迭代后的权重向量$w+\delta$

\[ \begin{aligned} L(w+\delta) - L(w) &= \sum_{x,y} \tilde{P}(x,y) \log P_{w+\delta}(y|x) - \sum_{x,y} \tilde{P}(x,y) \log P_w(y|x) \\ &= \sum_{x,y} \tilde{P}(x,y) \sum_{i=1}^{n} \delta_i f_i(x,y) - \sum_{x} \tilde{P}(x) \log \frac{Z_{w+\delta}(x)}{Z_w(x)} \end{aligned} \]

利用不等式

\[ -\log \alpha \ge 1-\alpha, \quad \alpha > 0 \]

建立对数似然函数改变量的下界：

\[ \begin{aligned} L(w+\delta) - L(w) &\ge \sum_{x,y} \tilde{P}(x,y) \sum_{i=1}^{n} \delta_i f_i(x,y) + 1 - \sum_{x} \tilde{P}(x) \frac{Z_{w+\delta}(x)}{Z_w(x)} \\ &= \sum_{x,y} \tilde{P}(x,y) \sum_{i=1}^{n} \delta_i f_i(x,y) + 1 - \sum_{x} \tilde{P}(x) \sum_{y} P_w(y|x) \exp \left( \sum_{i=1}^{n} \delta_i f_i(x,y) \right) \end{aligned} \]

记该下界为$A(\delta|w)$，则我们可以通过选取合适的$\delta$来提高下限，以此提高对数似然函数

我们进一步寻找$A(\delta|w)$的下限，记$f^{\#}(x,y)=\sum f_i(x,y)$

利用指数函数的凸性以及对任意 $i$，有 $\frac{f_i(x,y)}{f^{\#}(x,y)} \ge 0$ 且 $\sum_{i=1}^{n} \frac{f_i(x,y)}{f^{\#}(x,y)} = 1$ 这一事实，根据 Jensen 不等式，得到

\[ \begin{aligned} \exp \left( \sum_{i=1}^{n} \frac{f_i(x,y)}{f^{\#}(x,y)} \delta_i f^{\#}(x,y) \right) \le \sum_{i=1}^{n} \frac{f_i(x,y)}{f^{\#}(x,y)} \exp(\delta_i f^{\#}(x,y)) \end{aligned} \]

于是式 (6.30) 可改写为

\[ \begin{aligned} A(\delta|w) \ge &\sum_{x,y} \tilde{P}(x,y) \sum_{i=1}^{n} \delta_i f_i(x,y) + 1 - \\ &\sum_{x} \tilde{P}(x) \sum_{y} P_w(y|x) \sum_{i=1}^{n} \frac{f_i(x,y)}{f^{\#}(x,y)} \exp(\delta_i f^{\#}(x,y)) \end{aligned} \]

这是一个更松弛的下界，记为$B(\delta|w)$，对其求偏导

\[ \frac{\partial B(\delta|w)}{\partial \delta_i} = \sum_{x,y} \tilde{P}(x,y) f_i(x,y) - \sum_{x} \tilde{P}(x) \sum_{y} P_w(y|x) f_i(x,y) \exp(\delta_i f^{\#}(x,y)) \]

则每次可以通过解上述的零方程来获得新的$\delta$，并更新$w^{t+1} \leftarrow w^t+\delta$