一、逻辑回归
1.1 什么是逻辑回归？
(1) 通俗版本：逻辑回归实际上就是在线性回归的基础上加了一个逻辑函数 (sigmoid)
(2) 学术版：逻辑回归是一种分类模型，由条件概率分布 $P(Y|X)$ 表示
1.2 逻辑回归的形式
按照李航老师的书中，应该介绍的是 logistic 分布。但是，我们先来一个简单的。
sigmoid 函数
其数学形式是：
$$g(x) = \frac{1}{1 + e ^ {-x}}$$
从上图可以看到 sigmoid 函数是一个 S形的曲线，它的取值在[0, 1]之间，在远离0的地方函数的值会很快接近0/1。
logistic 分布
设 $X$ 是连续随机变量， $X$ 服从 logistic 分布是指 $X$ 具有下列分布函数
$$F(x) = P(X \leqslant x) = \frac{1}{1 + e^{-(x-\mu) / \gamma}}$$
式中， $\mu$ 为位置参数， $\gamma > 0$ 为形状参数。
通俗点就是，曲线以点 $(\mu , \frac12)$ 为中心对称，且 $\gamma$ 的值越小，曲线在中心附近增长得越快。
所以，可以这样认为 sigmoid 函数其实就是满足 $\mu = 0 , \gamma = 1$ 的 logistic 分布
logistic 模型
这里，我们以二项逻辑斯蒂回归模型为例。
那么在给定随机变量 $X$ 和 随机变量 $Y$ 的情况下， 二项逻辑斯蒂回归模型是：
$$P(Y=1 | X) = \frac{1}{1 + e^{-\theta^T x}}$$
其中， $\theta$ 是我们需要求的模型的参数。
1.3 求解 logistic 回归模型
对于训练数据集，特征数据 $X = { x_1, x_2, … , x_n }$ 和对应的分类数据 $Y = { y_1, y_2, … , y_n }$ 我们采取极大似然估计的方法来估计模型参数即找到一组参数，使得在这组参数下，我们的数据的似然度（概率）可以达到最大。在逻辑回归模型中，似然度可表示为：
$$L(\theta) = P(Y|\theta) = \prod P(y|x;\theta) = \prod g(\theta^T x) ^ y (1-g(\theta^T x))^{1-y}$$
取对数可以得到对数似然度：
$$l(\theta) = \sum {y\log{g(\theta^T x)} + (1-y)\log{(1-g(\theta^T x))}}$$
另一方面，在机器学习领域，我们更经常遇到的是损失函数的概念，其衡量的是模型预测错误的程度。常用的损失函数有0-1损失，log损失，hinge损失等。其中log损失在单个数据点上的定义为
$$-y\log{p(y|x)}-(1-y)\log{1-p(y|x)}$$
如果取整个数据集上的平均log损失，我们可以得到
$$J(\theta) = -\frac{1}{N} l(\theta)$$
即在逻辑回归模型中，我们最大化似然函数和最小化log损失函数实际上是等价的。对于该优化问题，存在多种求解方法，这里以梯度下降的为例说明。梯度下降(Gradient Descent)又叫作最速梯度下降，是一种迭代求解的方法，通过在每一步选取使目标函数变化最快的一个方向调整参数的值来逼近最优值。基本步骤如下：
- 选择下降方向（梯度方向，$\nabla {J(\theta)}$）
- 选择步长，更新参数 $\theta^i = \theta^{i-1} - \alpha^i \nabla {J(\theta^{i-1})}$
- 重复以上两步直到满足终止条件
其中损失函数的梯度计算方法为：
$$\frac{\partial{J}}{\partial{\theta}} = -\frac{1}{n}\sum_i (y_i - y_i^*)x_i + \lambda \theta$$
沿梯度负方向选择一个较小的步长可以保证损失函数是减小的，另一方面，逻辑回归的损失函数是凸函数（加入正则项后是严格凸函数），可以保证我们找到的局部最优值同时是全局最优。
二、最大熵模型
2.1 最大熵原理
熵反应的是事物的无序程度，或者说随机变量分布的均匀程度。
用数学形式表示就是：
$$H(P) = -\sum_x P(x) log P(x)$$
熵满足以下不等式：
$$0 \leq H(P) \leq log(|x|)$$
其中 $|X|$ 为 $X$ 取值个数，仅当 $X$ 均匀分布时，右等号成立，熵最大。
我们知道了一个变量 $X$ 的熵的表达式，很容易推广到多个变量的熵，很显然随机变量 $X$ 和 $Y$ 的联合熵的表达式是
$$H(X, Y) = - \sum_{x, y}^n p(x, y) log p(x, y)$$
但是，在最大熵模型中，我们会使用的是条件熵， $H(Y|X)$ 表示在已知随机变量X的条件下随机变量Y的不确定性。它的推导过程如下所示：
$$H(Y|X) = \sum_{x \in X} p(x) H(Y|X = x) \
= -\sum_{x \in X} p(x) \sum_{y \in Y} p(y|x) log p(y|x) \
= -\sum_{x \in X} \sum_{y \in Y} p(x, y) log p(y|x)$$
直观地讲，最大熵原理认为，在所有可能的概率模型（分布）中，熵最大的模型是最好的模型。也就是说，在那些满足已有事实（或约束条件）的概率模型中，那些不确定的部分都是无序的、混乱的、等可能的、均匀分布的。这个“等可能、混乱”只是个感性的词语，需要一个量化的标准，这个标准就是熵。
用一个例子介绍最大熵原理：
1 | 例 1 随机变量 X 取值 {A,B,C,D,E} , 要估计各值的概率 P(A) ，P(B) ... |
2.2 最大熵模型的定义
将最大熵原理应用于分类就得到了最大熵模型。
假设分类模型是一个条件概率分布 $P(Y|X)$，$X \in \mathcal{X} \subseteq R^n$ 表示输入, $Y \in \mathcal{Y}$ 表示输出, $\mathcal{X}$ 和 $\mathcal{Y}$ 分别是输入、输出的集合，这个模型表示的是对于给定的输入 $\X$ ，以条件 $P(Y|X)$ 输出 $Y$.
给定一个训练数据集
$$T = { (x_1, y_1), (x_2, y_2) …, (x_n, y_n) }$$
学习的目标是使用最大熵原理选择最好的分类模型。
2.2.1 两个经验分布
因为，我们给定了训练数据集，所以，我们可以确定联合分布 $P(X, Y)$ 的经验分布和边缘分布 $P(X)$ 的经验分布。
我对于经验分布的理解就是：经验分布就是我们通过样本得到的概率分布，因为总体的分布，我们是未知的，所以我们需要通过样本来估计总体
这里，我们用 $\widetilde{P}(X, Y)$ 和 $\widetilde{P}(X)$ 表示 $P(X, Y)$ 的经验分布和 $P(X)$ 的经验分布。
所以，我们有：
$$\widetilde{P}(X = x, Y = y) = \frac{v(X = x, Y = y)}{N}
\ \widetilde{P}(X = x) = \frac{v(X = x)}{N}$$
其中， $v(X = x, Y = y)$ 表示训练数据中样本 $(x, y)$ 出现的频数， $v(X = x)$ 表示训练数据中输入 $x$ 出现的频数， N表示样本容量。
2.2.2 特征函数
我们用特征函数 $f(x, y)$ 描述输入 $x$ 和输出 $y$ 之间的某一个事实, 它是一个二值函数。其定义是
$$f(x,y)=\begin{cases}
1, & x, y 满足某一事实\
0, & 否则
\end{cases}$$
特征函数 $f(x, y)$ 关于经验分布 $\widetilde{P}(X, Y)$ 的期望值，用 $E_{\widetilde{P}}(f)$ 表示。
$$E_{\widetilde{P}}(f) = \sum_{x, y} \widetilde{P}(x, y) f(x, y)$$
特征函数 $f(x, y)$ 关于模型 $P(Y|X)$ 与经验分布 $\widetilde{P}(X)$ 的期望值，用 $E_{P}(f)$ 表示。
按道理来说，我们应该是想要获得 $P(X)$ 的分布，但是没办法，我们有的是样本，而不是总体，所以我们只能近似的认为经验分布 $\widetilde{P}(X)$ == 总体分布 $P(X)$
$$E_{P}(f) = \sum_{x, y} \widetilde{P}(x) P(y|x) f(x, y)$$
如果模型能够获取训练数据中的信息，那么久可以假设这两个期望值相等，也就是
$$E_P (f) = E_{\widetilde{P}}(f)$$
或
$$\sum_{x, y} \widetilde{P}(x) P(y|x) f(x, y) = \sum_{x, y} \widetilde{P}(x, y) f(x, y)$$
我们将上面的式子，作为模型学习的约束条件。 假如有 $n$ 个特征函数 $f_i (x, y), i=1, 2, 3, …, n$ 那么就有 $n$ 个约束条件。
2.2.3 最大熵模型
假设满足所有约束条件的模型集合为
$$\mathcal{C} \equiv { P \in \mathcal{P} | E_{\widetilde{P}}(f_i), i=1, 2, …, n }$$
定义在条件概率分布 $P(Y|X)$ 上的条件熵为
$$H(P) = - \sum_{x, y} \widetilde{P} (x) P(y|x) log P(y|x)$$
则模型集合 $\mathcal{C}$ 中条件熵 $H(P)$ 最大的模型称为最大熵模型。 式中的对数为自然对数。
上面的定义或许显得太枯燥了，那么我们就用一个例子来表示。
2.2.4 一个例子
例1： 假设我们需要判断 “打” 字是动词还是量词，已知的训练数据有
$(x_1, y_1)$ = (一打火柴， 量词) ,
$(x_2, y_2)$ = (三打啤酒， 量词) ,
$(x_3, y_3)$ = (五打塑料袋， 量词) ,
$(x_4, y_4)$ = (打电话， 动词) ,
$(x_5, y_5)$ = (打篮球， 动词) ,
通过观察，我们会发现 “打” 字前面为数字的时候，“打” 是量词， “打” 字后面是名词的时候， “打” 是动词。这是我们从训练数据中提取出来的两个特征，可以分别用特征函数 $f_1(x=“打”字前面为数字, y=量词)$ 和 $f_2(x=“打”字后面为名词, y=动词)$ 表示。
$$f_1(x,y)=\begin{cases}
1, & 若“打”字前面为数字；\
0, & 否则
\end{cases}$$
$$f_2(x,y)=\begin{cases}
1, & 若“打”字后面是名词；\
0, & 否则
\end{cases}$$
在有了特征函数之后，对于训练数据，我们有：
$$f_1(x_1, y_1) = f_1(x_2, y_2) = f_1(x_3, y_3) = 1; f_1(x_4, y_4) = f_1(x_5, y_5) = 0$$
$$f_2(x_1, y_1) = f_2(x_2, y_2) = f_2(x_3, y_3) = 0; f_2(x_4, y_4) = f_2(x_5, y_5) = 1$$
同时，对于特征函数 $f_1$ 来说，它的经验分布是:
$$\widetilde{P}(X = 若“打”字前面为数字, Y = 量词) = \frac{3}{5}
\ \widetilde{P}(X = 若“打”字前面为数字) = \frac{3}{5}$$
对于特征函数 $f_2$ 来说，它的经验分布是:
$$\widetilde{P}(X = 若“打”字后面是名词, Y = 动词) = \frac{2}{5}
\ \widetilde{P}(X = 若“打”字后面是名词) = \frac{2}{5}$$
所以，我们有两个约束条件
$$\sum_{x, y} \frac{3}{5} P(y=量词 | x = 若“打”字前面为数字) = \frac{9}{5}$$
$$\sum_{x, y} \frac{2}{5} P(y=动词 | x = 若“打”字后面是名词) = \frac{4}{5}$$
2.3 最大熵模型的学习
最大熵模型的学习过程就是求解最大熵模型的过程，最大熵模型的学习可以形式化为约束最优化的问题。
对于给定的训练数据集 $T = { (x_1, y_1), (x_2, y_2), …, (x_N, y_N) }$ 以及特征函数 $f_i(x, y), i=1, 2, …, n$， 最大熵模型的学习等价于约束最优化问题：
$$\max \limits_{P \in C} \ 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,…, n \
\sum_y P(y|x) = 1$$
我们通常习惯上求最小值问题，所以我们把这里的最大值问题改写为等价的求最小值问题
$$\min \limits_{P \in C} \ - H(P) = \sum_{x, y} \widetilde{P} (x) P(y|x) log P(y|x) \ \ (2.1) \
s.t. \ E_P (f_i) - E_{\widetilde{P}} (f_i) = 0, \ i=1,2,…, n \ \ (2.2) \
\sum_y P(y|x) = 1 \ \ (2.3)$$
一旦，我们求出了约束最优化问题 $(2.1) ~ (2.3)$ 的解，我们就得到了最大熵模型学习的解。
下面是详细的推导公式：
1、首先，我们先将约束最优化问题转换成无约束最优化的对偶问题 (todo: 写一篇关于拉格朗日对偶性的blog) . 通过求出对偶问题的解来求原始问题的解。
引入拉格朗日乘子 $w_0, w_1, w_2, …, w_n$，定义拉格朗日函数 $L(P, w)$ ：
$$L(P, w) \equiv -H(P) + w_0 \lgroup 1 - \sum_y P(y|x) \rgroup + \sum_{i=1}^n w_i (E_\widetilde{P} (f_i) - E_P (f_i)) \
= \sum_{x, y} \widetilde{P} (x) P(y|x) log P(y|x) + w_0 \lgroup 1 - \sum_y P(y|x) \rgroup + \
\sum_{i=1}^n w_i \lgroup \sum_{x, y} \widetilde{P} (x, y) f_i (x, y) - \sum_{x, y} \widetilde{P}(x) P(y|x) f_i {x, y} \rgroup \ \ (2.4)$$
最优化的原始问题是：
$$\min_{P \in C} \ \max_{w} L(P, w) \ \ (2.5)$$
对偶问题就是
$$\max_{w} \min_{P \in C} L(P, w) \ \ (2.6)$$
由于拉格朗日函数 $L(P, w)$ 是 $P$ 的凸函数，原始问题 $(2.5)$ 的解与对偶问题 $(2.6)$ 的解是等价的。这样，可以通过求解对偶问题 $(2.6)$ 来求解原始问题 $(2.5)$。
2、我们先求里面的极小化问题 $\min \limits_{P \in C} L(P, w)$， 因为 $\min \limits_{P \in C} L(P, w)$ 是 $w$ 的函数，我们将其记为：
$$\Psi (w) = \min_{P \in C} L(P, w) = L(P_w, w) \ \ (2.7)$$
$\Psi (w)$ 称为对偶函数。 同时，将其解记为：
$$P_w = arg \min \limits_{P \in C} L(P, w) = P_w(y|x) \ \ (2.8)$$
具体来说，我们可以求 $L(P, w)$ 对 $P(y|x)$ 的偏导数：
$$\frac{\partial L(P, w)}{\partial L(y|x)} = \sum_{x, y} \widetilde{P}(x) (log P(y|x) + 1) - \sum_y w_0 - \sum_{x,y} \lgroup \widetilde{P}(x) \sum_{i=1}^n w_i f_i(x, y) \rgroup \
= \sum_{x, y} \widetilde{P}(x) \lgroup log P(y|x) + 1 - w_0 - \sum_{i=1}^n w_i f_i (x,y) \rgroup \ \ (2.9)$$
令偏导数等于 0，在 $\widetilde{P}(x) > 0$ 的情况下，我们可以解出：
$$P(y|x) = exp (\sum_{i=1}^n w_i f_i (x,y) + w_0 - 1) = \frac{exp(\sum \limits_{i=1}^n w_i f_i (x,y))}{exp(1 - w_0)} \ \ (2.10)$$
由 $\sum \limits_y P(y|x) = 1$ 得：
$\sum \limits_y \frac{exp(\sum \limits_{i=1}^n w_i f_i (x,y))}{exp(1 - w_0)} = 1$ 可以推出 $exp(1 - w_0) = \sum \limits_y exp(\sum \limits_{i=1}^n w_i f_i (x,y))$
所以：
$$P_w (y|x) = \frac{exp(\sum \limits_{i=1}^n w_i f_i (x,y))}{\sum \limits_y exp(\sum \limits_{i=1}^n w_i f_i (x,y))} \ \ (2.11)$$
然后，我们再让
$$Z_w (x) = \sum \limits_y exp \lgroup \sum \limits_{i=1}^n w_i f_i (x,y) \rgroup \ \ (2.12)$$
这时候，我们称呼 $Z_w (x)$ 为规范化因子； $f_i (x, y)$ 是特征函数；$w_i$ 是特征的权值，由式 $(2.11)$ 和 $(2.12)$ 表示的模型 $P_w = P_w (y|x)$ 就是最大熵模型。这里， $w$ 是最大熵模型中的参数向量。
3、求解对偶问题外部的极大化问题。
$$\max_x \Psi (w) \ \ (2.13)$$
将其解记作 $w^*$，即：
$$w^* = arg \max_w \Psi (w)$$
也就是说，可以应用最优化算法求对偶函数 $\Psi (w)$ 的极大值，得到 $w^$，用来表示 $P^ \in C$. 这里， $P^ = P_{w^} =P_{w^*} (y|x)$ 是学习到的最优模型（最大熵模型）。也就是说，最大熵模型的学习归结为对偶函数 $\Psi (w)$ 的极大化。
2.4 一个关于最大熵模型的栗子
问题：假设随机变量 $X$ 有5个取值 ${ A,B,C,D,E }$ ，且 $P(A) + P(B) = \frac{3}{10}$， 问，我们如何估计取各个值的概率？
解：
为了方便，我们用 $y_1, y_2, y_3, y_4, y_5$ 表示 $A, B, C, D, E$ ，于是最大熵模型学习的最优化问题就是
$$min - H(P) = \sum_{i=1}^5 P(y_i) log P(y_i) \
s.t. \ \ P(y_1) + P(y_2) = \widetilde{P}(y_1) + \widetilde{P}(y_2) = \frac{3}{10} \
\sum_{i=1}^5 P(y_i) = \sum_{i=1}^5 \widetilde{P}(y_i) = 1$$
引进拉格朗日乘子 $w_0$, $w_1$，定义拉格朗日函数
$$L(P, w) = \sum_{i=1}^5 P(y_i) log P(y_i) + w_1 \lgroup P(y_1) + P(y_2) - \frac{3}{10} \rgroup + w_0 \lgroup \sum_{i=1}^5 P(y_i) - 1 \rgroup$$
根据拉格朗日对偶性，可以通过求解对偶最优化问题得到原始最优化问题的解，所以求解
$$\max \limits_w \min \limits_P L(P, w)$$
1、我们首先求解 $L(P, w)$ 关于 $P$ 的极小化问题，因此， $w_0, w_1$ 被我们看成常数，对 $y_i$ 求偏导，可以得到：
$$\frac{\partial L(P,w)}{\partial P(y_1)} = 1 + log P(y_1) + w_1 + w_0$$
$$\frac{\partial L(P,w)}{\partial P(y_2)} = 1 + log P(y_2) + w_1 + w_0$$
$$\frac{\partial L(P,w)}{\partial P(y_3)} = 1 + log P(y_3) + w_0$$
$$\frac{\partial L(P,w)}{\partial P(y_4)} = 1 + log P(y_4) + w_0$$
$$\frac{\partial L(P,w)}{\partial P(y_5)} = 1 + log P(y_5) + w_0$$
令各个偏导数等于0，解得
$$P(y_1) = P(y_2) = e^{-w_1 -w_0 - 1}$$
$$P(y_3) = P(y_4) = P(y_5) = e^{-w_0 - 1}$$
于是，
$$\min \limits_P L(P, w) = L(P_w, w) = -2 e^{-w_1 -w_0 - 1} - 3 e^{-w_0 - 1} - \frac{3}{10} w_1 - w_0$$
再求解 $L(P_w, w)$ 关于 $w$ 的极大化问题：
$$\max \limits_w L(P_w, w) = -2 e^{-w_1 -w_0 - 1} - 3 e^{-w_0 - 1} - \frac{3}{10} w_1 - w_0$$
同样的，对 $w_0, w_1$ 求导得到
$$2 e^{-w_1 -w_0 - 1} + 3 e^{-w_0 - 1} - 1 = 0$$
$$2 e^{-w_1 -w_0 - 1} + - \frac{3}{10} = 0$$
通过上面两个式子，我们可以得到
$$e^{-w_1 -w_0 - 1} = \frac{3}{20}$$
$$e^{-w_0 - 1} = \frac{7}{30}$$
于是，得到所要求的概率分布为：
$$P(y_1) = P(y_2) = \frac{3}{20}$$
$$P(y_3) = P(y_4) = P(y_5) = \frac{7}{30}$$