线性模型（线性回归、感知机和逻辑斯谛回归）

2018-12-30 本文已影响32人怀柔小龙虾

线性模型.png

线性模型

根据周志华老师的定义来说，线性模型是指其通过属性的线性组合来进行预测的函数，即
$f ( \boldsymbol { x } ) = w _ { 1 } x _ { 1 } + w _ { 2 } x _ { 2 } + \ldots + w _ { d } x _ { d } + b$
用一般向量形式，则写成
$f ( x ) = w ^ { \mathrm { T } } x + b$
其中， $\omega = \left( \omega _ { 1 } ; \omega _ { 2 } ; \cdots ; \omega _ { d } \right)$ ，并且 $w$ 和 $b$ 学到以后，模型也就确定了。因此，因此我们应该对线性模型有了一个初步的理解，那就是一定会用训练集去学习出一条线从而作为模型函数，而究竟这条线是用来拟合数据还是分类数据，那就要看模型是属性回归模型还是分类模型了

对于线性模型来说，它有很多种，比如回归模型中有线性回归，分类模型中有感知机、逻辑斯谛回归等，接下来我们主要展开讲解这三个模型

线性回归

线性回归是对给定的训练数据集进行线性拟合，从而找到一条能使得大多数样本点都尽可能被准确预测的拟合线，比如公式如下：
$\mathrm { f } \left( x _ { i } \right) = \omega ^ { T } x _ { i } + b，使得f \left( x _ { i } \right) \approx y _ { i }$

低维下的线性回归

当然，在高维的情况下肯定就不再是一条线了，比如在三维情况下这条线就将会是一个曲面，这里之所以称为线性回归，相信应该是诸多前辈们为了我们这些人能够直观地理解吧

高维下的线性回归

线性回归的学习策略

对于线性回归问题，我们最终的目的就是学习得到 $w$ 和 $b$ ，建立起这个模型公式，而目前最首要的问题就是：如何确定 $w$ 和 $b$ 是最优呢？

一般，对于线性回归问题，我们采用的是均方误差作为模型的性能度量，也就是我们会尽可能让均方误差最小化，而均方误差最小的时候，其参数w和b就是我们想要的最优参数了，即
$\begin{aligned} \left( w ^ { * } , b ^ { * } \right) & = \underset { ( w , b ) } { \operatorname { argmin } } \sum _ { i = 1 } ^ { m } \left( f \left( x _ { i } \right) - y _ { i } \right) ^ { 2 } \\ & = \underset { ( w , b ) } { \operatorname { argmin } } \sum _ { i = 1 } ^ { m } \left( y _ { i } - w x _ { i } - b \right) ^ { 2 } \end{aligned}$
说明：

均方误差的几何意义是对应的欧几里得距离；
基于均方误差最小化来进行模型求解的方法称为“最小二乘法”；
基于12，最小二乘法的几何意义也就是找到一条直线，使得所有样本到这条直线的欧氏距离之和最小
当然，也是可以用梯度下降法去做参数求解的，只是感知机部分会用到，这里就重复展开

我们现在知道，我们想要找到最好的拟合线需要用到最小二乘法求解代价函数最小时的 $w$ 和 $b$ ，然而最小二乘法是如何找到最佳参数的呢？这里我们不需要深究，只需要了解最小二乘法的代数法的求解过程是通过代价函数 $\sum _ { i = 1 } ^ { m } \left( f \left( x _ { i } \right) - y _ { i } \right)$ 对参数 $w$ 和 $b$ 进行求偏导，并令每个偏导值为0，进而求解整个方程组；其他的求解方法自然还有，比如矩阵法求解，具体内容可以参考文章后面的博客（最小二乘法小结）

为更多地理解最小二乘法的求解方式，我们这里引入周志华老师的单变量线性回归求解（代数法）和多变量线性回归（矩阵法）求解

单变量线性回归

首先，我们令 $E _ { ( w , b ) } = \sum _ { i = 1 } ^ { m } \left( y _ { i } - w x _ { i } - b \right) ^ { 2 }$
然后，分别对 $w$ 和 $b$ 进行求偏导，得
$\begin{aligned} \frac { \partial E _ { ( w , b ) } } { \partial w } & = 2 \left( w \sum _ { i = 1 } ^ { m } x _ { i } ^ { 2 } - \sum _ { i = 1 } ^ { m } \left( y _ { i } - b \right) x _ { i } \right) \\ \frac { \partial E _ { ( w , b ) } } { \partial b } & = 2 \left( m b - \sum _ { i = 1 } ^ { m } \left( y _ { i } - w x _ { i } \right) \right) \end{aligned}$
接着，令偏导式为0，解得
$\begin{array} { c } { w = \frac { \sum _ { i = 1 } ^ { m } y _ { i } \left( x _ { i } - \overline { x } \right) } { \sum _ { i = 1 } ^ { m } x _ { i } ^ { 2 } - \frac { 1 } { m } \left( \sum _ { i = 1 } ^ { m } x _ { i } \right) ^ { 2 } } } \\ { b = \frac { 1 } { m } \sum _ { i = 1 } ^ { m } \left( y _ { i } - w x _ { i } \right) } \end{array}$
注：单变量线性回归和多变量线性回归的区别仅在于样本点的特征数是一个还是多个，所以在单变量的时候， $w$ 的参数只有一个，公式是 $f \left( x _ { i } \right) = \omega x _ { i } + b$ ,在多变量的时候 $w$ 的参数就有多个，公式是 $f \left( x _ { i } \right) = \omega ^ { T } x _ { i } + b$

多变量线性回归

为方便起见，我们将 $w$ 和 $b$ 吸收入向量形式 $\widehat { \omega } = ( \omega ; b )$ ；这里的样本有 $d$ 个属性，把数据集 $D$ 表示为一个 $m*(d+1)$ 大小的矩阵 $X$ ，其中每行对应一个样本，该行的前 $d$ 个元素对应着样本的前 $d$ 个属性值，如下
$\mathbf { X } = \left( \begin{array} { c c c c c } { x _ { 11 } } & { x _ { 12 } } & { \dots } & { x _ { 1 d } } & { 1 } \\ { x _ { 21 } } & { x _ { 22 } } & { \dots } & { x _ { 2 d } } & { 1 } \\ { \vdots } & { \vdots } & { \ddots } & { \vdots } & { \vdots } \\ { x _ { m 1 } } & { x _ { m 2 } } & { \dots } & { x _ { m d } } & { 1 } \end{array} \right) = \left( \begin{array} { c c } { x _ { 1 } ^ { \mathrm { T } } } & { 1 } \\ { x _ { 2 } ^ { \mathrm { T } } } & { 1 } \\ { \vdots } & { \vdots } \\ { x _ { m } ^ { \mathrm { T } } } & { 1 } \end{array} \right)$
另外，把输出的标记也写成向量形式 $y = \left( y _ { 1 } ; y _ { 2 } ; \cdots ; y _ { m } \right)$ ，于是，我们得到目标式如下：
$\hat { \boldsymbol { w } } ^ { * } = \underset { \boldsymbol { \hat { w } } } { \arg \min } ( \boldsymbol { y } - \mathbf { X } \hat { \boldsymbol { w } } ) ^ { \mathbf { T } } ( \boldsymbol { y } - \mathbf { X } \hat { \boldsymbol { w } } )$

现在，我们先令 $E _ { \hat { \boldsymbol { w } } } = ( \boldsymbol { y } - \mathbf { X } \hat { \boldsymbol { w } } ) ^ { \mathrm { T } } ( \boldsymbol { y } - \mathbf { X } \hat { \boldsymbol { w } } )$

接着用 $E _ { \hat { \boldsymbol { w } } }$ 对 $\hat { \boldsymbol { w } }$ 求导，得到
$\frac { \partial E _ { \hat { \boldsymbol { w } } } } { \partial \hat { \boldsymbol { w } } } = 2 \mathbf { X } ^ { \mathrm { T } } ( \mathbf { X } \hat { \boldsymbol { w } } - \boldsymbol { y } )$

注：矩阵求导这部分大家应该都是一样在学校没有学过的，毕竟学矩阵的时候我们不学矩阵求导，学求导的时候我们还是不学矩阵求导，所以造成了似乎能看懂又看不太懂的情况，所以我把过程贴在下面，有需要更深入了解的同学可以到文章后面参考博客《机器学习中的矩阵求导的一点总结（三种方法求线性回归最佳参数）》
$\nabla _ { w } J ( w )$
$= \nabla _ { w } ( X w - Y ) ^ { T } ( X w - Y )$
$= \nabla _ { w } \left( w ^ { T } X ^ { T } X w - Y ^ { T } X w - w ^ { T } X ^ { T } Y + Y ^ { T } Y \right)$
$= \nabla _ { w } \left( w ^ { T } X ^ { T } X w \right) - \nabla _ { w } \left( Y ^ { T } X w \right) - \nabla _ { w } \left( w ^ { T } X ^ { T } Y \right)$
$= 2 * X ^ { T } X w - X ^ { T } Y - X ^ { T } Y$
$= 2 * X ^ { T } X w - 2 * X ^ { T } Y$

得到偏导式后，一般来说我们令其为0即可得到 $\hat { \boldsymbol { w } }$ 的解；但是，由于计算过程涉及到了矩阵的求逆运算，所以我们必须分为两种情况进行讨论：

当 $X ^ { T } X$ 是满秩矩阵时，可以直接令偏导式为0，得到
$\hat { \boldsymbol { w } } ^ { * } = \left( \mathbf { X } ^ { \mathrm { T } } \mathbf { X } \right) ^ { - 1 } \mathbf { X } ^ { \mathrm { T } } \boldsymbol { y }$
当 $X ^ { T } X$ 不是满秩矩阵时，我们可能会得到多组解；例如矩阵X的列数多于行数，显然不是满秩矩阵，此时便会解除多个的值（用借用我们中学解线性方程组时，如果因变量的数目大于方程的数目，则必然会出现很多组解）；所以，面对多组解的情况，我们的做法是引入正则化项（似乎就是吴恩达视频里的正规化方程，可以帮助解决矩阵的行数小于列数的情况）

感知机学习算法（Percetron Learning Algorithm）

感知机是基于数据集线性可分的前提下的一种二分类线性模型，即把数据集中的所有实例用一个超平面进行分离，其超平面的一侧为正例（即+1），另一侧为负例（-1）。因此，这个模型就是相当于把整个特征空间进行二分化，然后对每一个测试样例进行分类进而得到测试样例的标签。比如，公式如下：
$f ( x ) = \operatorname { sign } ( w \cdot x + b )$
说明：

数据集线性可分是指：对于给定的一个数据集 $T = \left\{ \left( x _ { 1 } , y _ { 1 } \right) , \left( x _ { 2 } , y _ { 2 } \right) , \cdots , \left( x _ { N } , y _ { N } \right) \right\}$ ，其中 $x _ { i } \in \mathcal { X } = R ^ { n }$ ， $y _ { i } \in y = \{ + 1 , - 1 \}$ ， $\mathrm { i } = 1,2 , \cdots , \mathrm { N }$ ，如果存在一个超平面S可以使得正实例点和负实例点完全正确地划分到超平面的两侧，则称数据集T为线性可分数据集
sign是符号函数，即
$\operatorname { sign } ( x ) = \left\{ \begin{array} { l l } { + 1 , } & { x \geqslant 0 } \\ { - 1 , } & { x < 0 } \end{array} \right.$
感知机模型属于判别模型；
感知机的几何解释：
- 线性方程 $wx+b$ 对应于特征空间 $R^n$ 中的一个超平面 $S$ ， $S$ 被称为分离超平面
- $w$ 是超平面的法向量
- $b$ 是超平面的截距
- 图示如下：
  
  感知机

感知机的学习策略

因为感知机算法的本身就是要通过训练集去找到一个分离超平面，而想要找到这样的超平面就需要确定参数 $w$ 和 $b$ ，和线性回归的问题一样，我们怎样才能确定参数 $w$ 和 $b$ 呢？因此，大佬们制定了策略，即定义一个损失函数，我们的目标就是让损失函数极小化，从而在极小化的基础上找到参数 $w$ 和 $b$ ，所以，我们现在分两步走，第一步是找到我们需要的损失函数，第二步就是我们如何让这个损失函数最小化

第一步：如何找到损失函数？

根据《统计学习方法》的说法，感知机的损失函数是选择误分类点到超平面 $S$ 的总距离，而不是误分类点的总数。为此，我们根据公式（可联系点到平面的公式）得到任意一点到 $x_{i}$ 超平面 $S$ 的距离为：
$\frac { 1 } { \| w \| } \left| w \cdot x _ { 0 } + b \right|$
注意，这里的是的范式；因此，我们也能得到所有误分类点到超平面S的距离：
- 说明：
  1. $M$ 是误分类点的集合
  2. 为什么去掉了绝对值后多了个 $-y_{i}$ ？这是因为我们为了去掉绝对值，考虑了两种情况
    - 当 $\omega x _ { i } + b > 0$ 时， $y _ { i } = - 1$ ，此时 $- y _ { i } \left( \omega x _ { i } + b \right) > 0$
    - 当 $\omega x _ { i } + b < 0$ 时， $y _ { i } = + 1$ ，此时 $- y _ { i } \left( \omega x _ { i } + b \right) > 0$
    所以，基于上面两种情况，我们才把绝对值去掉后的公式形式写成了 $- y _ { i } \left( \omega x _ { i } + b \right)$
更进一步，我们将分母忽略，于是就得到了我们感知机的损失函数，如下：
- 说明：
  - 这里我们引用某个博主的解答，如下:
    1. $\frac { 1 } { \| w\| }$ 不影响 $- y _ { i } \left( \omega x _ { i } + b \right)$ 正负的判断，即不影响学习算法的中间过程。因为感知机学习算法是误分类驱动的，这里需要注意的是所谓的“误分类驱动”指的是我们只需要判断 $- y _ { i } \left( \omega x _ { i } + b \right)$ 的正负来判断分类的正确与否，而 $\frac { 1 } { \| w\| }$ 并不影响正负值的判断。所以 $\frac { 1 } { \| w\| }$ 对感知机学习算法的中间过程可有可无；
    2. $\frac { 1 } { \| w\| }$ 不影响感知机学习算法的最终结果。因为感知机学习算法最终的终止条件是所有的输入都被正确分类，即不存在误分类的点。则此时损失函数为0，对应于 $- y _ { i } \left( \omega x _ { i } + b \right) / \| w\|$ ，即分母为0。则可以看出， $\frac { 1 } { \| w\| }$ 对最终结果也没有影响。
    3. 综上所述，我们可以从上面看出，忽略 $\frac { 1 } { \| w\| }$ 对感知机学习算法的执行过程不会产生任何影响，反而还可以简化运算，提高算法执行效

第二步：如何让损失函数最小化？

根据《统计学习方法》中介绍，感知机学习算法是误分类驱动的，具体采用的方法是：随机梯度下降（Stochastic Gradient Descent）；也就是先任意选取一个超平面和 ,然后利用梯度下降方法不断地极小化目标函数；其中，极小化过程不是一次使中的所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降这是随机梯度下降和标准的梯度下降之间的区别
- 说明：
  1. 随机梯度下降和标准的梯度下降及批量梯度下降之间的区别？
    - 标准梯度下降：
      1. 标准梯度是使用全部样本计算梯度的，其计算代价比较高，但是在理论上，其下降速度是三种里面最快的，因为标准梯度是基于所有样本，所以对于步长 $η$ 的取值，标准梯度下降的步长 $η$ 往往比随机梯度和批量梯度下降的大。
      2. 因为标准梯度是最小化所有训练样本的损失函数，所以它的每一步都是全局最优的下降方向，最终求解的是全局的最优解，即求解的参数是使得风险函数最小。
    - 随机梯度下降：
      1. 随机梯度使用单个样本计算，计算代价比较低，由于下降方向弯弯绕绕，所以有一定可能性避开局部最优，但是下降速度也比较慢，会迭代更多次。除此之外，如果误差曲面有多个局部最小值（即 $w$ 有多个极小值），随机梯度下降可能避免陷入这些局部最小值，原因还是在于随机梯度下降采用单个样本的误差梯度来引导搜索，也就是说，它有一定可能避开局部最优，也有一定可能陷入局部最优，究竟如何，还得等用代码实现了才能知道；
      2. 另外，因为标准梯度下降的是使用准确的梯度，它可以理直气壮地走，随机梯度下降使用的是近似的梯度，就得小心翼翼地走，怕一不小心误入歧途南辕北辙了；
      3. 虽然随机梯度下降不是每次迭代得到的损失函数都向着全局最优方向，但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近。
    - 批量梯度下降：
      1. 批量梯度介于两者之间，每次使用部分样本计算梯度。也就是说，批量的梯度下降就是一种折中的方法，他用了部分小样本来近似全部的样本。即：每次更新 $w$ 使用一批样本。
      2. 步长 $η$ 太小，收敛速度太慢；步长 $η$ 太大，会在最佳收敛点附近徘徊
      3. 不同问题的batch是不一样的，nlp的paper训练部分batch一般就设置为10000，那么为什么是10000呢，我觉得这就和每一个问题中神经网络需要设置多少层，没有一个人能够准确答出，只能通过实验结果来进行超参数的调整。（这一段摘自文章后面的博客）
  2. 最小二乘法与梯度下降法的异同：
    - 实现实现不同：最小二乘法是直接对参数求导找出全局最小，是非迭代法。而梯度下降法是一种迭代法，先给定一个 $β$ ，然后向参数下降最快的方向调整 $β$ ，在若干次迭代之后找到局部最小。
    - 梯度下降法的缺点：到最小点的时候收敛速度变慢，并且对初始点的选择极为敏感，其改进大多是在这两方面下功夫。
目前我们已经知道了方法，现在，我们先假设误分类点集合M是固定的，那么整天的损失函数 $L(w,b)$ 的梯度是：
$\begin{aligned} \nabla _ { w } L ( w , b ) & = - \sum _ { x _ { i } \in M } y _ { i } x _ { i } \\ \nabla _ { b } L ( w , b ) & = - \sum _ { x _ { i } \in M } y _ { i } \end{aligned}$
我们随机选取一个误分类点，对 $w$ , $b$ 进行更新：
$\begin{aligned} w &\leftarrow w + \eta y _ { i } x _ { i } \\ b &\leftarrow b + \eta y _ { i } \end{aligned}$
因为整个感知机学习算法是收敛的，最终我们会得到一个最优的参数 $w$ 和 $b$ ，而收敛的证明过程在《统计学习方法》中也有具体的证明过程，这里不做收敛证明的展开，至此，第二步完结。

感知机学习算法的两种形式

接下来我们讲解的感知机学习算法一共有两种，即原始形式和对偶形式

原始形式的算法：

输入：训练数据集 $\mathrm { T } = \left\{ \left( x _ { 1 } , y _ { 1 } \right) , \left( x _ { 2 } , y _ { 2 } \right) , \dots , \left( x _ { N } , y _ { N } \right) \right\}$ ，其中 $x _ { i } \in \mathcal { X } = R ^ { n }$ ， $y _ { i } \in y = \{ + 1 , - 1 \}$ ， $\mathrm { i } = 1,2 , \cdots , \mathrm { N }$ ；学习率 $\eta$ （ $0<\eta<1$ ）；
输出： $w$ ， $b$ ；感知机模型 $f ( x ) = \operatorname { sign } ( \omega x + b )$
学习过程：
1. 选取初值 $w_{0}$ ， $b_{0}$
2. 在训练集中选取数据 $(x_{i},y_{i})$
3. 如果 $y _ { i } \left( \omega x _ { i } + b \right) \leq 0$ ，则
  $\begin{aligned} w &\leftarrow w + \eta y _ { i } x _ { i } \\ b &\leftarrow b + \eta y _ { i } \end{aligned}$
4. 转至（2），直至训练集中没有误分类点

对偶形式的引入

原始形式写完，我们再来从几个问题中着手展开讲解感知机的对偶形式！

什么是对偶形式呢？
- 根据前面所讲，我们知道单个误分类点的是通过下面的两个公式
  $\begin{aligned} w &\leftarrow w + \eta y _ { i } x _ { i } \\ b &\leftarrow b + \eta y _ { i } \end{aligned}$ 来更新参数w和b的；同时我们还知道，我们更新的方法是随机梯度下降，也就是每次更新都是从误分类点中随机抽取一个来对参数进行更新；因此我们可以想象，在算法收敛找到最优的参数w和b的这个参数更新的过程中，每个误分类点都可能经历了很多次被抽取用来更新参数 $w$ 和 $b$ 的过程，此时我们添加一个新的概念 $\eta_{i}$ ，其是用来指代误分类样本点 $x _ { i } y _ { i }$ 在参数更新过程中被抽取的次数
- 现在，我们了解了新的概念后，我们再来看一下经历了全部的更新后所找到的最优参数公式：
  
  此时，我们再引入一个新的概念；
  - 说明：
    1. 这里的 $\alpha _ { i }$ 是《统计学习方法》中的写法，我想李航老师的意思应该是想简化参数
    2. 整个算法的步长 $\eta$ 是固定的，而我之前在博客中有看过别的博主观点是说步长是计算机根据需要选取的，并不是固定值，所以我自己对这里也不是很明白，希望以后能在代码实现的过程中理解
- 此时，我们根据新概念 $\alpha _ { i }$ 对我们之前的最终参数公式进行调整，如下：
  $\begin{aligned}w &= \sum _ { i = 1 } ^ { N } \alpha _ { i } y _ { i } x _ { i }\\b &= \sum _ { i = 1 } ^ { N } \alpha _ { i } y _ { i }\end{aligned}$
为什么感知机要有对偶形式呢？
- 先给出一个结论：对偶形式是从不同的角度解答原问题的相似问题，也就是说对偶其实就是在原问题的基础上进行的变形；
- 感知机使用对偶形式可以加快计算速度：因为在对偶形式里，样本点的特征向量是以内积的形式存在于训练算法中的，因此，如果我们事先算好训练集中实例间的内积并储存在矩阵里，也就是Gram矩阵，就可以在训练时大大快快算法的学习速度
- Gram矩阵：
  - $\mathrm { G } = \left[ x _ { i } \cdot x _ { j } \right] _ { N \times N }$
  - eg：我们有三个实例点 $x_{1},x_{2},x_{3}$ ，则Gram矩阵为：
    $\left[ \begin{array} { l l l } { x _ { 1 } \cdot x _ { 1 } } & { x _ { 1 } \cdot x _ { 2 } } & { x _ { 1 } \cdot x _ { 3 } } \\ { x _ { 2 } \cdot x _ { 1 } } & { x _ { 2 } \cdot x _ { 2 } } & { x _ { 2 } \cdot x _ { 3 } } \\ { x _ { 3 } \cdot x _ { 1 } } & { x _ { 3 } \cdot x _ { 2 } } & { x _ { 3 } \cdot x _ { 3 } } \end{array} \right]$

对偶形式的算法：

输入：训练数据集 $\mathrm { T } = \left\{ \left( x _ { 1 } , y _ { 1 } \right) , \left( x _ { 2 } , y _ { 2 } \right) , \dots , \left( x _ { N } , y _ { N } \right) \right\}$ ，其中 $x _ { i } \in \mathcal { X } = R ^ { n }$ ， $y _ { i } \in y = \{ + 1 , - 1 \}$ ， $\mathrm { i } = 1,2 , \cdots , \mathrm { N }$ ；学习率 $\eta$ （ $0<\eta<1$ ）；
输出： $\alpha$ ， $b$ ；感知机模型 $f ( x ) = \operatorname { sign } \left( \sum _ { j = 1 } ^ { N } a _ { j } y _ { j } x _ { j } \cdot x + b \right)$ ，其中 $\alpha = \left( \alpha _ { 1 } , \alpha _ { 2 } , \cdots , \alpha _ { N } \right) ^ { T }$
学习过程：
1. 选取初值 $\alpha \leftarrow 0 , b \leftarrow 0$
2. 在训练集中选取数据 $(x_{i},y_{i})$
3. 如果 $y _ { i } \left( \sum _ { j = 1 } ^ { N } a _ { j } y _ { j } x _ { j } \cdot x _ { i } + b \right) \leq 0$ ，则
  $\begin{aligned}\begin{array} { c } { \alpha _ { i } \leftarrow \alpha _ { i } + \eta } \\ { b \leftarrow b + \eta y _ { i } } \end{array} \end{aligned}$
4. 转至（2），直至训练集中没有误分类点
说明：
- 判定误分类的条件 $y _ { i } \left( \sum _ { j = 1 } ^ { N } a _ { j } y _ { j } x _ { j } \cdot x _ { i } + b \right) \leq 0$ ，对照原始形式 $y _ { i } \left( \omega x _ { i } + b \right) \leq 0$ ，可能会很困惑为什么差别这么大，如果参考上面引入 $\alpha_{i}$ 的部分可以更进一步发现，其中 $\sum _ { j = 1 } ^ { N } a _ { j } y _ { j } x _ { j }$ 不应该是最终更新得到的参数 $w$ 吗？没错，的确是，因为整个学习算法选用的是随机梯度下降的方法，所以在进行选取误分类点 $(x _ { j },y _ { j })$ 的过程中我们必须用当前最终的参数 $w$ 来进行判断，所以才会有这样的一个判定条件
- 看到 $\alpha _ { i } \leftarrow \alpha _ { i } + \eta , b \leftarrow b + \eta y _ { i }$ 的更新方式肯定也很奇怪，为什么是这样的更新形式？这是因为，我们的新参数 $\eta_{i}$ 被李航老师用 $\alpha _ { i } = n _ { i } \eta$ 的方式蕴含到了 $\alpha _ { i }$ 里，从而我们没能看到能代表更新式子的本质是 $\eta_{i}$ ，其实我们只要想一下 $\eta_{i}$ 表示的是误分类样本点 $(x _ { j },y _ { j })$ 在参数更新过程中被抽取的次数，我们就可以明白，每次我们选取一个误分类点 $(x _ { j },y _ { j })$ 的时候，因为误分类点的判定条件的符合，这个 $(x _ { j },y _ { j })$ 又需要再用来对参数进行一次更新，所以更新式应该是 $n _ { i } = n _ { i } + 1$ ，也因此，更新式被蕴含在 $\alpha _ { i } \leftarrow \alpha _ { i } + \eta = \left( n _ { i } + 1 \right) \eta$ 式子里

感知机的问题

根据我们先前的定义可以知道，感知机是基于数据集线性可分的前提下的可以寻找到一个超平面对数据进行分类的模型，如下图所示：

线性可分的情况

但是，我们可以想一下，如果数据不可分怎么办呢？

根据这个问题，我们首先来看如果发生线性不可分究竟是什么样的一种情况：

答：这个超平面会一直震荡来震荡去，从而在达到迭代上限的时候停下

线性不可分的情况

现在，我们知道这个问题引发的结果是什么了，我们就需要考虑另一个问题，怎么解决？

答：Pocket算法
1. 这是根据在网上的博客了解到的，台大的林轩田老师在讲感知机算法时讲解了一个Pocket改进算法，这是类似一种贪心选择的算法，下面我们借用网上的一个博客内容对这个改进算法做一个简单的直观理解
  - Pocket PLA（他们似乎把感知机学习算法称为Naive PLA），怎么理解呢？就好像我们在搜寻最佳分类直线的时候，随机选择错误点修正，修正后的直线放在口袋里，暂时作为最佳分类线。然后如果还有错误点，继续随机选择某个错误点修正，修正后的直线与口袋里的分类线比较，把分类错误点较少的分类线放入口袋。一直到迭代次数结束，这时候放在口袋里的一定是最佳分类线，虽然可能还有错误点存在，但已经是最少的了。
2. Pocket PLA缺点：
  - 如果数据一开始就是完全线性可分的，那么用这个算法所找出的解未必是最好的，并且时间花费也可能比较大。
  - 由于data是随机选取的，迭代的次数也是人定的，很可能迭代完后所找到的解并不是最好的。

逻辑斯谛回归（Logistics Regression）

逻辑斯谛回归是一个二分类的模型，简称LR，它是在线性回归的基础上使用了sigmoid函数，将线性模型 $\omega ^ { T } x + b$ 的结果压缩到了[0,1]之间，从而实现了将回归问题转化为了分类问题。

线性回归和逻辑斯谛回归

下面我们先借用吴恩达视频中的一个例子来讲解一下线性回归解决不了的分类问题

例：下图是一个乳腺癌分类的问题，其中横轴是肿瘤的大小，纵轴是我们的预测值。现在我们用线性回归去拟合数据，其中预测函数的阈值设置为0.5，即大于等于0.5的预测为1，表示是恶性肿瘤，小于0.5的预测为0，表示良性肿瘤。我们很幸运的可以发现，这条直线拟合的很好，刚好所有的样本点都能够分类正确

线性回归1
接下来，我们再进一步，假设现在训练集中突然来了一个尺寸非常大的恶性肿瘤，这个样本点将使得我们原先拟合的直线发生变化，如下

线性回归2
现在，我们发现阈值0.5对应的结点发生了变化，从原先的酒红色的结点向右移动到了蓝色结点，此时我们可以发现，这条直线的预测并不像原先那么好了，它让两个原先预测为1的样本点突然被预测为了0，就是上面4个红叉的左边两个

逻辑斯谛回归模型

鉴于上面的例子，我们可以发现，线性回归对于分类问题是具有很差的预测效果的，因此，我们在原先的线性回归的问题上引入sigmoid函数，也就是将原先的预测值 $\omega ^ { T } x + b$ 作为自变量填充到了sigmoid函数在，如下图黑色曲线：

单位阶跃函数与对数几率函数
说明：

图源自周志华老师的《机器学习》，其中红色线部分是单位阶跃函数，公式是图上红色字体部分，黑色曲线是sigmoid函数，借用这个图的原因是想说明我们不选用单位阶跃函数的原因是因为其不连续，相对的sigmoid函数是极好的，连续可导的
我们刚才说LR模型是在线性回归的基础上加了sigmoid函数，也就是将原先的预测值 $\omega ^ { T } x + b$ 作为自变量 $z$ 填充到了sigmoid函数里，所以我们得到了如下公式
$y = \frac { 1 } { 1 + e ^ { - \left( \boldsymbol { w } ^ { \mathrm { T } } \boldsymbol { x } + b \right) } }$

此时，我们需要引入一些新的概念：我们把一个事件的几率（odds）指代为该事件发生的概率与该事件不发生的概率比值；如果事件发生的概率是 $p$ ，那么该事件的几率是 $\frac { p } { 1 - p }$ ，该事件的对数几率（log odds）是
$\operatorname { logit } ( p ) = \log \frac { p } { 1 - p }$

注：对数几率也可以成为是logit函数，对此，其实我们可以不用被它怪异的名称吓到，它就是某事件发生概率与不发生概率比值的对数形式而已

为了建立起上面两个式子的联系，我们将 $y$ 视为样本 $x$ 作为正例的可能性，也就是 $p$ ， $1-y$ 视为样本 $x$ 作为反例的可能性，也就是 $1-p$ ，所以我们可以通过 $y = \frac { 1 } { 1 + e ^ { - \left( \omega ^ { T } x + b \right) } }$ 变化为如下形式：
$\ln \frac { y } { 1 - y } = w ^ { \mathrm { T } } x + b$
此时，为了方便，我们再把权值向量 $w$ 和输入向量 $x$ 进行扩充，即 $\widehat { \omega } = \left( \omega _ { 1 } ; \omega _ { 2 } ; \cdots ; \omega _ { n } ; b \right) ^ { T }$ ， $X=\left( x _ { 1 } ; x _ { 2 } ; \cdots ; x _ { d } ; 1 \right) ^ { T }$ ，这时，上式又可以变化为如下形式
$\log \frac { y } { 1 - y } = \widehat { w } \cdot X$

接下来，我们 $y$ 视为后验概率估计 $p ( y = 1 | x )$ ，则得到
$\log \frac { P ( y = 1 | x ) } { 1 - P ( y = 1 | x ) } = \widehat { w } \cdot X$

由上式，再加上 $\mathrm { p } ( y = 1 | x ) + \mathrm { p } ( y = 0 | x ) = 1$ ，我们终于可以得到逻辑斯谛回归模型的公式了，即：
$\begin{aligned} P ( y = 1 | x ) & = \frac { e ^ { ( \hat { w } \cdot X ) } } { 1 + e ^ { ( \hat { w } \cdot X ) } } \\ P ( y = 0 | x ) & = \frac { 1 } { 1 + e ^ { ( \hat { w } \cdot X ) } } \end{aligned}$

参数估计

对于逻辑斯谛回归模型，我们一般采用极大似然估计去对参数进行估计，接下来，我们开始进行极大似然估计对我们的参数进行估计

根据极大似然估计的常规步骤，我们需要写出似然函数，因此，我们先设
$P ( Y = 1 | x ) = \pi ( x ) , \quad P ( Y = 0 | x ) = 1 - \pi ( x )$

则，似然函数为
$\prod _ { i = 1 } ^ { N } \left[ \pi \left( x _ { i } \right) \right] ^ { y _ { i } } \left[ 1 - \pi \left( x _ { i } \right) \right] ^ { 1 - y _ { i } }$
进而，其对数似然函数为
$\begin{aligned} L ( \widehat { 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( \widehat { w } \cdot x _ { i } \right) - \log \left( 1 + e ^ { \left( \widehat { w } \cdot x _ { i } \right) } \right] \right. \end{aligned}$
最后，我们令 $L ( \widehat { w } )$ 为0，求极大值，进而就可以得到 $\widehat { w }$ 的估计值

说明：

可能我们对似然函数感觉很奇怪，但学过《概率论与数理统计》的同学应该都是了解的，而需要指出的是，这个似然函数就是我们的损失函数
当然，对于LR模型的参数估计并非只有极大似然估计一种方法，在吴恩达的视频中就是用梯度下降的方法去对似然函数进行参数估计的，但鉴于感知机部分里梯度下降已经讲了许多，我们这里不再过多展开。

我们假设极大似然估计得到的估计值是 $\widehat { \omega } ^ { * }$ ，则学习到的逻辑斯谛回归模型为
$\begin{aligned}P ( y = 1 | x ) = \frac { \exp \left( \hat { w } ^ { * } \cdot x \right) } { 1 + \exp \left( \hat { w } ^ { * } \cdot x \right) }\\P ( y = 0 | x ) = \frac { 1 } { 1 + \exp \left( \hat { w } ^ { * } \cdot x \right) }\end{aligned}$

逻辑斯谛回归这部分总体来说总结得还是太过简单，主要目前是在不想花太多精力在这个模型上面，毕竟时间和精力都是有限的，所以希望自己以后在第二个阶段模型实现的过程中能够为这些坑慢慢填上吧！

参考资料：
[1]：最小二乘法小结
[2]：机器学习中的矩阵求导的一点总结（三种方法求线性回归最佳参数）
[3]：感知机中损失函数1/||w||为什么可以不考虑（或直接忽略）？
[4]：梯度下降的三种形式BGD、SGD以及MBGD
[5]：随机梯度下降（Stochastic gradient descent）和批量梯度下降（Batch gradient descent ）的公式对比、实现对比
[6]：PLA算法（感知机）
[7]：《机器学习》周志华
[8]：《统计学习方法》李航
[9]：《机器学习》（视频）吴恩达