全程高能！因为数学表达式的推导和证明实在太多了，然后文章篇幅也比较长。导致我的markdown编辑器渲染公式无敌无敌卡，严重影响书写，所以后半篇基本以手写推导为主。（尽力在排版了TAT）之后的文章可能也会有很多的手写推导，具体排版形式我再斟酌斟酌。
0. 感知机的缺陷
我们在介绍过感知机，知道感知机的由输入空间到输出空间的映射函数为 $f(x)=sign(wx+b)$，可以绘制出图像
从图中我们可以发现，在图像 $x=0$ 处图像连续不可微（跳跃间断点），因此我们在梯度下降选择的是 $wx+b$ 而非 $sign(wx+b)$。
此外，感知机还存在一个巨大的缺陷：
在图中，用咖啡色线条框出的一个绿色实例和一个红色实例，紧邻感知机对应的超平面。由于感知机的划分，一个属于红色一个属于绿色，但这两者真的有天壤之别的差距吗？如果是在一个多分类的问题，两者甚至很有可能属于同一类别。
因此我们希望有新的模型可以解决以下两个问题：
- 怎么解决极小距离带来的 $+1$ 和 $-1$ 的天壤之别？
- 怎么让最终的预测式连续可微？
1. 逻辑斯谛回归模型
此处我们介绍二项逻辑斯谛回归模型。
二项逻辑斯谛回归模型满足如下条件概率分布：$P(Y=1|x)=\frac{exp(wx)}{1+exp(wx)}$ 和 $P(Y=0|x)=\frac{1}{1+exp(wx)}$
此处 $w=(w^{(1)},w^{(2)},..,w^{(n)},b)^T$，$x=(x^{(1)},w^{(2)},…,w^{(n)},1)^T$
我们容易发现：
- 整个函数连续可微
- $\begin{cases} P(Y=1|x) \in (0,1) \\P(Y=0|x) \in (0,1) \\P(Y=0|x)+P(Y=1|x)=1 \end{cases}$所以，逻辑斯谛回归模型输出的是概率。
此外，逻辑斯谛回归模型中，一个事件发生的几率是该事件发生的概率和不发生的概率的比值。
如果事件发生的概率为 $p$，那么事件发生的几率为 $\frac{p}{1-p}$。该事件的对数几率为 $logit(p)=log \frac{p}{1-p}$。
结合上述可以得到 $logit(P(Y=1|x))=log\frac{P(Y=1|x)}{1-P(Y=1|x)}=wx$，也就是说在逻辑斯谛回归中，输出 $Y=1$ 的对数几率是输入 $x$ 的线性函数。
2. 逻辑斯谛模型参数估计
设 $P(Y=1|x)=\pi(x)$，$P(Y=0|x)=1-\pi(x)$，
采用极大似然的方法估计模型参数，得到似然函数为 $\prod_{i=1}^{N}[\pi(x_i)]^{y_i}[1-\pi(x_i)]^{1-y_i}$
- 我们对似然函数取对数，将连乘转变为连加 $\sum_{i=1}^N log{[\pi(x_i)]^{y_i}[1-\pi(x_i)]^{1-y_i}}$
- 继续拆开乘法：$\sum_{i=1}^N {log[\pi(x_i)]^{y_i}+log[1-\pi(x_i)]^{1-y_i}}$
- 利用 $log a^b=b\ log\ a$ 进行化简：$\sum_{i=1}^N {y_ilog\ \pi(x_i)+(1-y_i)log[1-\pi(x_i)]$
我们将上式最后一步称为对数似然函数，可对其进行进一步变形：
- 将对数似然函数展开：$\sum_{i=1}^N {y_ilog\ \pi(x_i)+log[1-\pi(x_i)]-y_ilog[1-\pi(x_i)]}$
- 根据 $log\ a-log\ b=log\frac{a}{b}$，将第一第三项合并得到：$\sum_{i=1}^N {y_ilog\frac{\pi(x_i)}{1-\pi(x_i)}+log[1-\pi(x_i)]}$
其中 $\frac{\pi(x_i)}{1-\pi(x_i)}$ 通过第一步的假设可以写为 $\frac{P(Y=1|x_i)}{P(Y=0|x_i)}$，进而可以表示为 $\frac{exp(wx_i)}{1+exp(wx_i)}*\frac{1+exp(wx_i)}{1}=exp(wx_i)$；
同时 $1-\pi(x_i)$ 可以表示为 $P(Y=1|x_i)$ 进而表示为 $\frac{1}{1+exp(wx_i)}$
因此，将变形的上述两项带入对数似然函数：
- $=\sum_{i=1}^N {y_ilog(exp(wx_i))+log\frac{1}{1+exp(wx_i)}}$
- $=\sum_{i=1}^N {y_i*wx_i)-log(1+exp(wx_i))}$
至此，对 $L(w)=\sum_{i=1}^N {y_i*wx_i)-log(1+exp(wx_i))}$ 求极大值，就可以得到 $w$ 的估计值。
我们将 $L(w)$ 对 $w$ 求偏导，得到 $\frac{\partial L(w)}{\partial w}=\sum_{i=1}^N {y_ix_i - \frac{1}{1+exp(wx_i)}exp(wx)x_i}=\sum_{i=1}^N {y_ix_i - \frac{x_iexp(wx)}{1+exp(wx_i)}}$
于是可以轻松得到 $w$ 的极大似然估计 $\breve w$。
3. 最大熵模型
我们此前在决策树的部分提过： 当均匀分布时，熵最大。这是“最大熵原理”的一个推广。
最大熵原理认为：学习概率模型时，在所有可能的概率模型分布中，熵最大的模型时最好的模型。
因此，最大熵原理也可以表述为在满足约束条件的模型集合中选取熵最大的模型。
我们知道假设离散型随机变量 $X$ 的概率分布为 $P(X)$，则其熵为 $H(P)=-\sum_x P(x)log(P(x))$
因为我们的预测目标为 $P(Y|x)$，所以将 $P(Y|x)$ 带入熵的表达式：
得到条件熵 $H(P)=H(Y|x)=-\sum_x \breve P(x)P(Y|x)log(P(Y|x))$，其中 $\breve P(x)$ 代表经验分布
对于经验分布，我们有如下两个表达式，其中 $v(x)$ 表示满足条件 $x$ 的样本数目：
$\breve P(X=x,Y=y)=\frac{v(X=x,Y=y)}{N}$
$\breve P(x=x)=\frac{v(X=x)}{N}$
用特征函数 $f(x,y)$ 描述输入 $x$ 和输出 $y$ 之间的某一事实，其定义为 $f(x,y)=\begin{cases} 1, &\text{x 与 y 满足某一事实} \\ 0, &\text{否则} \end{cases}$
特征函数 $f(x,y)$ 关于经验分布 $\breve P(X,Y)$ 的期望值，用 $E_{\breve p}(f)=\sum_{x,y} \breve P(x,y)f(x,y)$ 表示，此处特征函数用于消除噪声干扰，因为不满足规律的分布将会乘以特征 0 再累加。
将 $E_{\breve p}(f)$ 再做变形，$E_{\breve p}(f)=\sum_{x,y} \breve P(x,y)f(x,y)=\sum_{x,y} \breve P(x) \breve P(y|x)f(x,y)$
特征函数 $f(x,y)$ 关于模型 $P(Y|X)$ 与经验分布 $\breve P(X)$ 的期望值用 $E_p(f)$ 表示：
- $E_p(f)=\sum_{x,y}P(x,y)f(x,y)$
- 由于我们的预测目标是 $P(Y|x)$，所以我们将 $P(x,y)$ 展开，得到 $E_p(f)=\sum_{x,y}P(x)P(Y|x)f(x,y)$
- 因为我们不可能得知 $P(x)$，只能通过经验数据得到 $\breve P(x)$，所以用 $\breve P(x)$ 替换 $P(x)$ 得到 $E_p(f)=\sum_{x,y} \breve P(x)P(Y|x)f(x,y)$
至此，我们整理上述表达式，可以得到最大熵模型。
定义（最大熵模型）：假设满足所有约束条件的模型集合为 $C \equiv {P \in PP|E_p(f_i)=E_\breve p(f_i),\ i=1,2,…,n }$
定义在条件概率分布 $P(Y|X)$ 上的条件熵为 $H(P)=-\sum_{x,y}\breve P(x)P(y|x)log(P(y|x))$
则模型集合 $C$ 中条件熵 $H(P)$ 最大的模型称为最大熵模型。
4. 最大熵模型的学习
最大熵模型的学习过程就是求解最大熵模型的过程，最大熵模型的学习可以形式化为约束最优化问题。
对于给定了训练集 $T={(x_1,y_),(x_2,y_2),…,(x_N,y_N)}$ 以及特征函数 $f_i(x,y)$，$i=1,2,…,n$，最大熵模型的学习等价于一个最优化问题：
$max_{P \in C} H(P) = -\sum_{x,y} \breve P(x) P(y|x) log(P(y|x))$
使得 $E_p(f_i)=E_{\breve p}(f_i)$，$i=1,2,…,n$；$\sum_y P(y|x)=1$
一般我们更加习惯求解最小值问题，因此对上述最大值问题进行改写：
$\begin{cases} min_{P \in C} (-H(P))=\sum_{x,y} \breve P(x) P(y|x)log(P(y|x)) \\使得\ E_p(f_i)- E_{\breve p}(f_i)=0，i=1,2,…,n\ 且\ \sum_y P(y|x)=1 \end{cases}$
我们使用拉格朗日乘子法，定义拉格朗日函数 $L(P,w)$
$L(P,w) \equiv -H(P) + w_0(1-\sum_yP(y|x))+\sum_{i=1}^nw_i(E_{\breve p}(f_i)-E_P(f_i))$
将 $H(P)$ 以最大熵模型带入，将 $E_{\breve p}(f_i)$ 和 $E_P(f_i))$ 带入得到：
$=\sum_{x,y} \breve P(x) P(y|x) log P(y|x) + w_0(1-\sum_yP(y|x))+\sum_{i=1}^nw_i(\sum_{x,y}\breve P(x,y)f_i(x,y)-\sum_{x,y}\breve P(x)P(y|x)f_i(x,y))$
因此最优化的原始问题为 $min_{p \in C}\ (max_w\ L(P,w))$
这里对 $min_{p \in C}\ (max_w\ L(P,w))$ 的由来进行一下解释：
- KKT 条件：
如果求解 $min_x f(x)$，约束条件为 $h_i(x)=0$ 和 $g_j(x) \leq 0$
先写出拉格朗日函数 $L(x, \alpha, \beta)=f(x)+\sum_{i=1}^m\alpha_ih_i(x)+\sum_{j=1}^n\beta_jg_j(x)$
在拉格朗日函数中，$h_i(x)=0$，$g_j(x) \leq 0$，因此 $L(x, \alpha, \beta)=f(x)+\sum_{i=1}^m\alpha_ih_i(x)+\sum_{j=1}^n\beta_jg_j(x) \geq f(x)$ （将 $\alpha$ 和 $\beta$ 视为变量）
因此求原函数 $f(x)$ 的最小值等价于求解 $L(x, \alpha, \beta)$ 关于 $\alpha$ 和 $\beta$ 最大值的最小值
即 $min_x[max_{\alpha,\beta}L(x,\alpha,\beta)]$
在本文的例子里， $E_p(f_i)-E_{\breve p}(f_i)=0$，$1-\sum_y P(y|x)=0$ 可以看作是 KKT 条件 $g_j(x) \leq 0$ 取等号的一个特例
根据“一般成立，特殊也成立”，所以本文的例子也可以由 KKT 的结论得到 $min_{p \in C}\ (max_w\ L(P,w))$
因为拉格朗日函数 $L(P,w)$ 为凸函数，所以亦可等价为 $max_w\ (min_{P \in C}\ L(P,w))$ 【强调！非凸函数不可采取这样的变换】
一、首先我们先求解 $min_{P \in C}L(P,w)$，因为是 $w$ 的函数，所以我们也记为 $\Phi(w)=min_{P \in C}L(P,w)=L(P_w,w)$，
同时将其解记为 $P_w=arg\ min_{p \in C}L(P,w)=P_w(y|x)$
具体地，就是求 $L(P,w)$ 对 $P(y|x)$ 的偏导数 $\frac{\partial L(P,w)}{\partial P(y|x)}$
$L(P,w)=\sum_{x,y} \breve P(x) P(y|x) log P(y|x) + w_0(1-\sum_yP(y|x))+\sum_{i=1}^nw_i(\sum_{x,y}\breve P(x,y)f_i(x,y)-\sum_{x,y}\breve P(x)P(y|x)f_i(x,y))$
使 $L(P,w)$ 对 $P(y|x)$ 求偏导：
令偏导数为 0：
由于 $\sum_y P(y|x)=1$，
将上式带入 $P(y|x)$ 的表达式：
简写得到得：
- $P_w(y|x)=\frac{1}{Z_w(x)}exp(\sum_{i=1}^nw_if_i(x,y))$
- 其中 $Z_w(x)=\sum_y exp(\sum_{i=1}^nw_if_i(x,y))$（$Z_w(x)$ 称为规范因子）
二、之后求解问题的外部极大化问题 $max_w \Phi(w)$ 将其解记为 $w^*$，即 $w^*=arg\ max_w \Phi(w)$
至此，我们解出了 $w^*$，于是 $P^*=P_{w^*}=P_{w^*}(y|x)$ 就是学习到的最大熵模型。
5. 最大熵模型的极大似然估计
由最大熵模型学习中可以看出，最大熵模型是：$P_w(y|x)=\frac{1}{Z_w(x)}exp(\sum_{i=1}^nw_if_i(x,y))$，其中 $Z_w(x)=\sum_y exp(\sum_{i=1}^nw_if_i(x,y))$
下面证明对偶函数的极大化等价于最大熵模型的极大似然估计。
已知训练数据的经验概率分布 $\breve P(X,Y)$，条件概率分布 $P(Y|X)$ 的对数似然函数为
- $L_{\breve P}(P_w)=log \prod_{x,y}P(y|x)^{\breve P(x,y)}$
- 将对数连乘转换为连加：$=\sum_{x,y}\breve P(x,y) logP(y|x)$
当条件概率分布是最大熵模型时，对数似然函数 $L_{\breve P}(P_w)$ 为：
- $L_{\breve P}(P_w)=\sum_{x,y}\breve P(x,y)logP(y|x)$
- $=\sum_{x,y}\breve P(x,y)log(\frac{1}{Z_w(x)}exp(\sum_{i=1}^nw_if_i(x,y)))$
- 将对数除法转换为减法：$=\sum_{x,y}\breve P(x,y)\sum_{i=1}^nw_if_i(x,y)-\sum_{x,y}\breve P(x,y)logZ_w(x)$
- $=\sum_{x,y}\breve P(x,y)\sum_{i=1}^nw_if_i(x,y)-\sum_x \breve P(x)logZ_w(x)$
再来看对偶函数：
- $\Phi(w)=\sum_{x,y}\breve P(x)P_w(y|x)logP_w(y|x)+\sum_{i=1}^nw_i(\sum_{x,y}\breve P(x,y)f_i(x,y)-\sum_{x,y}\breve P(x)P_w)(y|x)f_i(x,y)$
- $=\sum_{x,y}\breve P(x,y)\sum_{i=1}^nw_if_i(x,y)+\sum_{x,y}\breve P(x)P_w(y|x)(logP_w(y|x)-\sum_{i=1}^nw_if_i(x,y))$
- $=\sum_{x,y}\breve P(x,y)\sum_{i=1}^nw_if_i(x,y)-\sum_{x,y}\breve P(x)P_w(y|x)logZ_w(x)$
- 因为 $\sum_y P(y|x)=1$，$=\sum_{x,y} \breve P(x,y) \sum_{i=1}^nw_if_i(x,y)-\sum_x \breve P(x)log Z_w(x)$
结合对数似然函数和对偶函数得到 $\Phi(w)=L_{\breve P}(P_w)$
至此，我们证明了最大熵模型学习中的对偶函数极大化等价于最大熵模型的极大似然估计。
6. 改进的迭代尺度法
改进的迭代尺度法（improved iterative scaling, IIS）是一种最大熵模型学习的最优化算法。
此前我们知道最大熵模型的对数似然函数为 $L(w)=\sum_{x,y}\breve P(x,y)\sum_{i=1}^nw_if_i(x,y)-\sum_x\breve P(x)logZ_w(x)$
而 IIS 的想法是：每次增加一个增量 $\delta$，使得 $L(w+\delta)>L(w)$，从此不断地提高 $L$ 的值直到达到极大值。
因此我们对 $L(w+\delta)$ 和 $L(w)$ 做差值：
我们希望对差值进行放缩找到一个下界，利用不等式 $-log\ a \geq 1-a \ (a>0)$
然后从 $\frac{Z_{w+\delta}(x)}{Z_w(x)}$ 入手：
将结果代回差值表达式：
就此，我们得到了差值的一个下界，并将其记作为 $A(\delta|w)$。我们可以通过不断迭代找到合适的 $\delta$ 使得下界 $A(\delta|w)$ 提高，从而提升对数似然函数 $L(w)$。但是，$\delta$ 是一个 n 维向量，含有 n 个变量，难以同时优化。IIS 试图一次只优化其中一个变量 $\delta_i$，而固定其他变量 $\delta_j$。
为了达到这个目的，IIS 进一步降低下界 $A(\delta|w)$。
引入 $f^#(x,y)=\sum_if_i(x,y)$，因为 $f_i$ 是二值函数，故 $f^#(x,y)$ 表示所有特征在 $(x,y)$ 出现的次数。将 $A(\delta|w)$ 进行进一步改写：
因此，我们得到了一个更低的下界，记作 $B(\delta|w)$，即 $A(\delta|w) \geq B(\delta|w)$。我们希望尽可能得到更大的 $B(\delta|w)$，从而得到更大的 $A(\delta|w)$ ，从而得到更大的对数似然函数。
因此我们对 $B(\delta|w)$ 求 $\delta_i$ 的偏导数，并令偏导数为 0，解出 $\delta$：
总结一下改进的迭代尺度算法 IIS：
输入：特征函数 $f_1$，$f_2$，…，$f_n$；经验分布 $\breve P(X,Y)$，模型 $P_w(y|x)$
输出：最优参数值 $w_i^*$，最优模型 $P_{w^*}$
- 对所有 $i \in {1, 2, …,n}$，取初值 $w_i=0$
- 对每一 $i \in{1,2..,n}$
- 令 $\delta_i$ 是方程
$\sum_{x,y}\breve P(x)P(y|x)f_i(x,y)exp(\delta_i,f^#(x,y))=E_{\breve P}(f_i)$ 的解（$B(\delta|w)$ 对 $\delta_i$ 的偏导数为 0）- 更新 $w_i$ 值：$w_i \leftarrow w_i +\delta_i$
- 如果不是所有 $w_i$ 都收敛，重复步骤 2
7. 最大熵模型学习的其他方法
最大熵模型学习还可以应用牛顿法或者拟牛顿法。
【这里先挖一个坑，之后再填（因为这篇文章已经太长了）】
8. 总结
我们引入了逻辑斯谛回归解决了感知机存在的问题：
- 超平面两侧极小距离将会带来带来 $+1$ 和 $-1$ 的天壤之别。
- 最终的预测式不是连续可微（在 $x=0$ 处）
逻辑斯谛回归（二项）：$P(Y=1|x)=\frac{exp(wx)}{1+exp(wx)}$ 和 $P(Y=0|x)=\frac{1}{1+exp(wx)}$ 的好处不仅在于解决了感知机的缺点，而且：
- $P(Y=1|x)$ 和 $P(Y=0|x)$ 的返回值具有概率意义
- 在逻辑斯谛回归中，输出 $Y=1$ 的对数几率是输入 $x$ 的线性函数。
然后我们推导了如何应用极大似然估计法估计逻辑斯谛模型参数（见第二章），其中有一个参数估计常用的技巧就是通过取对数得到对数似然函数的方式，将复杂难以处理的连乘转换为易于处理的连加。
之后我们介绍了最大熵模型，最大熵模型认为熵最大的模型是最好的概率模型（比如均匀分布就是熵最大的模型）。一般我们要求的都是条件熵 $H(Y|x)$，因此将条件概率带入熵的表达式并进行变换，得到 $H(P)=-\sum_{x,y}\breve P(x)P(y|x)log(P(y|x))$
- 推导的过程中我们引入了特征函数 $f(x,y)=\begin{cases} 1, &\text{x 与 y 满足某一事实} \\ 0, &\text{否则} \end{cases}$，用于消除噪声干扰
- 化简过程中，因为我们不可能得知 $P(x)$，只能通过经验数据得到 $\breve P(x)$，所以用 $\breve P(x)$ 近似替换了 $P(x)$
然后我们介绍了最大熵模型的学习过程，核心是解决一个最优化问题：
$\begin{cases} min_{P \in C} (-H(P))=\sum_{x,y} \breve P(x) P(y|x)log(P(y|x)) \\使得\ E_p(f_i)- E_{\breve p}(f_i)=0，i=1,2,…,n\ 且\ \sum_y P(y|x)=1 \end{cases}$
使用拉格朗日乘子法和 KKT 条件将问题简化为 $max_w\ (min_{P \in C}\ L(P,w))$ 通过对似然函数求条件概率的偏导等操作得到最优参数 $w^*$
之后我们证明了最大熵模型学习中的对偶函数极大化等价于最大熵模型的极大似然估计。
介绍了改进的迭代尺度法 IIS（每次增加一个增量 $\delta$，使得 $L(w+\delta)>L(w)$，从此不断地提高 $L$ 的值直到达到极大值）并进行了推到与证明。
当然，虽然逻辑斯谛回归比感知机优秀太多了。但是逻辑斯谛回归就是一个完美的存在吗？显然不是，他也存在一些局限：
- 找到的超平面是一个表现良好的，而不是最优的
- 限定超平面是线性的，因此要求数据集也必须是线性的
之后我们也会介绍更优秀的分类模型比如 SVM 等。