机器学习03-继续线性分类（硬分类）---感知器模型

从上一讲我们可以看到，线性分类其实是打破了线性回归全局线性的特点。具体的分类类型这边不再阐述，上一篇讲了应用比较广的LR，这一篇会说一下剩下的线性分类器。篇幅受限，这一篇我们主要讲硬分类模型中的感知器模型。

感知机模型

感知机模型是二分类的线性分类模型，其思想是错误驱动，其前提是数据线性可分。

首先是数据集， $D = \{{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)}\}$ ， $x_i\in R^p$ , $y = \{+1, -1\}$

定义如下模型： $f(x) = sign(w^Tx)$ ，截距项可以放进w里面，只要把x增加一维1即可。

其中sign是符号函数，当 $w^Tx$ 大于等于0时， sign(x) = 1, 否则 -1，从而起到分类的作用。

接下来第二步，定义损失函数，首先意识到一点，如果数据点被分类正确，则一定有 $y_iw^Tx_i > 0$

很直接的想法是，我们去统计被错误分类的个数 $L(w) = \sum_{i=1}^n1\{y_iw^Tx_i < 0\}$

上式中的 $1$ 是指示函数，当括号满足时候，值为1，不满足时为0，所以上式表示了错误分类的个数。

但是这个损失函数有一个问题，我们改变 $w$ ，使得 $w_{new} = w + \Delta w$ ，然后 $L(w)$ 发生了变化，但是并没有办法去求导，没有办法去最小化损失函数，因此需要对损失函数做一些变化，引出新的损失函数，所有误分类点到超平面的距离之和（严格意义上而言，距离应该加上 $\frac{1}{||w||^2}$ ）。

$L(w) = \sum_{x_i\subset D} -y_iw^Tx_i$ , $D$ 是分类错误的样本集合

这里不考虑 $\frac{1}{||w||^2}$ ，我个人的理解是，首先不影响误分类点的判断，因为不会影响 $y_iw^Tx_i$ 的正负情况，其次是感知机只适用于线性可分的情况，因此损失函数最终应该是0，即所有点都被分类正确。所以有没有这一项没有关系。

接下来就是统计机器学习第三步，使用算法求解优化问题，这边可以采用随机梯度下降法（SGD）来求解，本质也是求梯度，沿着负梯度方向前进，使得损失函数变小。 $\nabla_wL(w) = \sum_{x_i\subset D} -y_ix_i$ ，采用SGD，不需要用所有误分类点，每次随机选择一个误分类点即可，新的参数 $w^{t+1} = w^{t} +\eta y_ix_i$

这边有一个问题，就是为什么这个方法是可以收敛的，因为学习的过程只考虑了被分类错误的点，很有可能某一步学习，使得之前被分类错误的点分类正确了，而之前正确的却被新的模型分错了。

感知器模型对于线性可分问题一定收敛的证明如下：

放大缩小w，并不会影响平面位置，因此不失一般性的情况下，设 $||w_{opt}|| = 1$

假设第k步得到的w是 $w_k$ ,且存在一个 $x_i$ 使得 $y_iw_k^Tx_i < 0$ ,根据感知器算法，可以得到 $w_{k+1} = w_k +\eta y_ix_i$

$w_{k+1} - w_{opt} = w_k + \eta y_ix_i - w_{opt}$ , 取模，得到 $||w_{k+1} - a*w_{opt}||^2 = ||w_k - a*w_{opt}+ \eta y_ix_i||^2 = ||w_k - a*w_{opt}||^2 +||\eta y_ix_i||^2 +2\eta y_iw_k^Tix_i -2a\eta y_iw_{opt}^Tx_i$

第二项， $||\eta y_ix_i||^2 = \eta ^2||x_i||^2$ , 第三项 $2\eta y_iw_k^Tx_i$ 是小于0的，因为是分错的点，第四项 $2a\eta y_iw_{opt}^Tx_i$ 是大于0的，因为最终都是分类正确的，由此可以看出，只要选的a足够大，可以使得 $||w_{k+1} - a*w_{opt}||^2 < ||w_{k} - a*w_{opt}||^2$

现在先定义 $\beta = max\{||x_i||\}$ , $\gamma = min(y_iw_{opt}^Tx_i)$ , 取 $a = \frac{\beta ^2+1}{2\gamma}$ ,

最后一项 $2a\eta y_iw_{opt}^Tx_i = \frac{\beta ^2+1}{\gamma}\eta y_iw_{opt}^Tx_i > \eta(||x_i||^2 +1)$ , 第二项 $\eta ^2||x_i||^2$ ，第三项是小于0的。

当 $0 < \eta \leq 1时$ ，可推出 $||w_{k+1} - a*w_{opt}||^2 < ||w_{k} - a*w_{opt}||^2 - \eta$

所以一定可以收敛。

感知器模型是神经网络的基础，神经网络的具体内容会放到以后的篇章，毕竟路要一步一步走嘛，还有就是现在还在讲线性分类，就先把线性分类讲完，等大家看到神经网络的时候，对感知器模型还有印象就可以了。这里先做一个简单的解释，对于线性不可分的情况，感知器模型是不可能做到完全分类正确的。这时候，可以增加感知器的层数，这也就是神经网络的来源——MLP（multiple Layers Perceptron）。如果没有非线性处理，例如感知器里的sign函数，不管多少层的线性模型，都相当于一层的线性模型，增加层数并没有作用，这也是非线性处理的意义。但是对于更新参数，直接用上面的算法是没办法再这样做了，因此引入了BP（back-propagation）算法，利用求导的链式法则，把损失函数往回传，更新每一层的参数。但是，sign函数是一个分段函数，不具备处处可导的性质，因此sign函数会被替换成其它激活函数，例如sigmoid，Relu等。

转载请注明，谢谢