对数几率回归(逻辑斯蒂回归)

@(机器学习经典算法总结)

逻辑回归基本是我们所有人学习的第一个分类器，分类器从概率意义上理解，代表的是什么意思，以最简单的二分类来举例吧，假设样本数据

D = (x^{(i)}, y^{(i)}), i f o r 1, 2, 3, . . . y^{(i)} \in (- 1, + 1)

那么我们对于新的数据

x^{(j)}

肯定是要得到

P (y = - 1 | x^{(j)}) 以 及 P (y = + 1 | x^{(j)})

哪个概率大，那么我们就采用该类别。
分类器所得到也即是

P (c | x)

生成式模型和判别式模型

目前分类模型根绝获取 $P (c | x)$ 的方式不同，分为生成时模型（generative models）和判别式模型（discriminative models）
从CMU的教材来看
对数几率回归(逻辑斯蒂回归)
从上图可看出，当使用生成式分类器时，我们依靠所有的点来学习生成模型。当使用判别式分类器时，我们主要关心决策边界。
那么这两种模型从概率角度怎么解释呢？
- 判别式模型：给定 $x$ ，通过直接建模 $P (c | x)$ 来预测 $c$ ，常见模型为决策树，BP神经网络，SVM，当然还包括本节的LR；
- 生成式模型：通过联合概率求解 $P (c | x) = \frac{P (x, c)}{P (x)}$ ，通过贝叶斯定理，可知 $P (c | x) = \frac{P (c) P (x | c)}{P (x)}$ ，目前我了解的经典算法中，只有朴素贝叶斯；

LR模型表达式和损失函数

那至此，我们也明确了，既然LR是判别式模型，就需要定义决策边界了。
经常把线性回归和逻辑回归关联到一起，虽然一个是回归模型，一个是分类模型，但是二者却有着千丝万缕的联系。
我们定义决策边界，可以考虑利用一个超平面，将正负样本分隔开，超平面我们可以使用线性模型去拟合。
那么此时，我们所要求的条件概率就是 $P (c | x, ω), ω 表示线性回归的参数。$
如图所示对数几率回归(逻辑斯蒂回归)
分离面的方程为 $\vec{ω} * \vec{x} = 0$

{\begin{cases} ω * x > 0, y = 1 \\ ω * x < 0, y = 0 \end{cases}

使用sigmoid函数将线性回归>0的标记为正类，反之则负类。
那么

P (Y = 1 | x, ω) = \frac{1}{1 + e x p (- ω * x)} = \frac{e x p (ω * x)}{1 + e x p (ω * x)} P (Y = 0 | x, ω) = \frac{1}{1 + e x p (ω * x)}

令

h_{ω} (x) = P (Y = 1 | x, ω)

我们定义几率为正类的概率/负类的概率:

\frac{P (Y = 1 | x, ω)}{P (Y = 0 | x, ω)} = e x p (ω * x)

则对数几率即为

l o g (\frac{P (Y = 1 | x, ω)}{P (Y = 0 | x, ω)}) = ω * x

这也就是逻辑回归的由来，本质是对数几率回归。
则同线性回归一致，我们仍然使用最大似然估计去估计模型的参数

ω

最大似然估计的原始形式为

L (ω) = \prod_{i = 1}^{n} (\frac{e x p (ω * x^{(i)})}{1 + e x p (ω * x^{(i)})})^{y^{(i)}} (\frac{1}{1 + e x p (ω * x^{(i)})})^{1 - y^{(i)}}

取对数似然

\begin{aligned} L L (ω) & = \sum_{i = 1}^{n} (y^{(i)} * l o g (\frac{e x p (ω * x^{(i)})}{1 + e x p (ω * x^{(i)})}) + (1 - y^{(i)}) * l o g (\frac{1}{1 + e x p (ω * x^{(i)})})) \\ = \sum_{i} (y^{(i)} ω x^{(i)} + l o g (1 + e x p (ω x^{(i)}))) \end{aligned}

\frac{\partial L L (ω)}{ω_{j}} = \sum_{i} (x_{j}^{(i)} (y^{(i)} - \frac{e x p (ω x^{(i)})}{1 + e x p (ω x^{(i)})})) = \sum_{i} (x_{j}^{(i)} (y^{(i)} - h_{ω} (x^{(i)})))

可看出直接对偏导数置为0，无法求解

ω

逻辑回归的最大似然函数对于参数

ω

来说是个凹函数，对似然函数取极大值，可以使用梯度上升来估计极大值。
而且，从最大似然函数出发可以得到逻辑回归的损失函数，即在似然函数前面加个-1/m。

\begin{aligned} J (ω) & = - \frac{1}{m} \sum_{i} (y^{(i)} * l o g (h_{ω} (x^{(i)})) + (1 - y^{(i)}) * l o g (1 - h_{ω} (x^{(i)}))) \\ \frac{\partial J (ω)}{ω_{j}} & = - \frac{1}{m} \sum_{i} (x_{j}^{(i)} (y^{(i)} - h_{ω} (x^{(i)}))) \end{aligned}

我们需要求损失函数的最小值，相应的需要使用梯度下降法求解。

梯度法和牛顿法——求解无约束最优化问题

数学回顾笔记（一）——方向导数和梯度回顾了方向导数和梯度的概念，明确了，梯度方向为函数增长最快的方向，负梯度方向为函数减小最快的方向。
梯度下降法和牛顿法都是求解无约束最优化问题的常用方法，基于泰勒展开式推出的，

f (x) = f (x_{0}) + (x - x_{0}) f (x_{0})^{(1)} + \frac{(x - x_{0})^{2}}{2!} f (x_{0})^{(2)} + . . . + \frac{(x - x_{0})^{n}}{n!} f (x_{0})^{(n)} + o (n)

根据泰勒展开式可以无限逼近原表达式。
则，来看梯度下降法。
梯度下降法使用的是一阶泰勒展开式

f (x) = f (x_{0}) + (x - x_{0}) f (x_{0})^{(1)}

但是这里的自变量是向量，则把自变量x变为向量

\vec{x}

，将一阶偏微分变为梯度，转换为下式：

f (\vec{x^{k}} + α \vec{d}) = f (\vec{x^{k}}) + α g_{k}^{T} \vec{d} g_{k}^{T} = g (x^{(k)}) = \nabla f (x^{(k)}) 表 示 f (x) 在 x^{(k)} 的 梯 度 ， 是 个 向 量

我们的目的是使得上式去最小，则向量

g_{k}^{T} 和 \vec{d}

的方向应相反，即

\vec{x^{(k + 1)}}

应该是

\vec{x^{k}}

沿着负梯度方向，更新的大小为

α

.
将梯度下降法应用于逻辑回归
则

ω_{j} :\leftarrow ω_{j} - \frac{1}{m} \sum_{i} (x_{j}^{(i)} (y^{(i)} - h_{ω} (x^{(i)})))

可以看出，梯度下降法每次都会使用全部的训练数据来更新

ω

，得到的是一个全局最优解，但是当训练数据非常多的时候，迭代的速度会非常慢。这种方法称为批梯度下降法，与之对应的是随机梯度下降法。

ω_{j} :\leftarrow ω_{j} - x_{j}^{(i)} (y^{(i)} - h_{ω} (x^{(i)}))

随机梯度下降法每次只是用一个训练样本

x^{(i)}

迭代更新

ω

，所以随机梯度下降法的迭代速度非常快，但是相对应的随机梯度下降法噪声比较多，每次迭代不一定都是朝着整体最大优化方向。

批梯度下降法——最小化所有训练样本的损失函数，使得最终求解的是全局最优解，即求解的参数使得风险函数最小。
随机梯度下降——最小化每条样本的损失函数，虽然每次迭代得到的损失函数都向着全局最优方向，但是整体的方向是向全局最优解的，最终的结果往往在全局最优解附近。牺牲了一部分精度来换取时间

而牛顿法使用的是二阶泰勒展开式

f (x) = f (x_{0}) + (x - x_{0}) f (x_{0})^{(1)} + \frac{(x - x_{0})^{2}}{2!} f (x_{0})^{(2)}

极值点处一阶导数为0，求出了

x = x_{0} - \frac{f (x_{0})^{(2)}}{f (x_{0})^{(1)}}

对应的矩阵形式为

x^{(k + 1)} = x (k) - H_{k}^{(- 1)} g_{k}

H_{k} (海 赛 矩 阵) 是 f (x) 在 x^{(k)} 处 的 二 阶 导 数 矩 阵 ， g_{k} 是 f (x) 的 梯 度 向 量 在 点 x^{(k)} 的 值

牛顿法收敛速度快，但是每次迭代都需要计算海赛矩阵

H_{k}

的逆矩阵，计算量非常大。

正则化

正则化在很多算法都有涉及，是机器学习中十分常用的一个思想。
使用正则化的原因是防止模型过拟合，模型过拟合的因素主要是
- 数据数据太少
- 模型参数过于复杂（参数过多或过大）

整理插播介绍一下三个风险——经验风险、结构风险和期望风险

在选择了合适的模型之后，使用极大似然估计模型的参数可以导出模型的损失函数，通过损失函数对所有样本点求和就得到了经验风险。
也可以看出，经验风险其实表示的是模型对训练数据的拟合程度，经验风险越小，对训练数据拟合程度越好，而我们希望的是对测试集或者说全局样本的拟合程度都比较好，这就是期望风险，但期望风险函数往往不可得到。所以折中考虑了一种结构风险，即在经验风险后面加一个惩罚项即正则化项。

最大熵模型

对于最大熵模型，自己对于模型的细节理解的还不是很清晰，即使写出来怕也是会误导读者。但这个文章是我自己对于逻辑回归相关内容的总结，还是记录相关内容链接吧，后续秋招时候会把这个模型补充完整。
Logistic Regression 的前世今生（理论篇）
关于最大熵模型的严重困惑：为什么没有解析解？
最大熵模型

广义线性模型

机器学习笔记五：广义线性模型（GLM）
cs229 slide
知乎这个链接解释了由于指数分布簇的性质，似然函数求导为0的解即为极大值
 广义线性模型（Generalized Linear Model）

对数几率回归(逻辑斯蒂回归)