《统计学习方法》-02感知机

# 感知机

感知机这个模型，其实很早就提出了，然而限于当时的技术条件（主要是计算机的计算能力），再加上某个人证明感知机无法解决逻辑运算问题，所以很多人都放弃了。但是，如今的所谓的神经网络，其实就是多层感知机……

事实上，一个感知机能做的事的确太有限，但是众多的感知机连接成网状，对不起，几乎什么函数都可以拟合了。

## 感知机模型

感知器要解决的问题是二分类（很简单），对于输入的实例，感知机要给出其正确的分类，而总的分类只有两个，正例和负例。

数学上来说，输入空间是$X\subseteq \bf{R}^n$，输出空间为$Y=\{+1,-1\}$。输入$x\in X$表示实例的特征向量，输出$y\in Y$表示实例的类别。这样的一个函数：
$$
f(x)={ \rm sign} (wx+b)
$$
这里的$\rm sign$函数是符号函数。

从解析的角度来说，感知机作为一个函数，以实例为自变量产生一个+1或者-1的结果，从而实现分类。

从几何上来理解，感知机就是输入空间中的一个超平面，之所以是“超”，因为输入空间常常是高维的。这个超平面把整个空间一分为二，从而对空间中的点（实例）进行分类。

由解析几何，超平面的方程是：
$$
wx+b=0
$$
这里，$w$是平面法向量，$b$是截距。

对于超平面上方的点，有：
$$
wx+b>0
$$
而对于超平面下方的点，有：
$$
wx+b<0
$$

## 感知机学习策略

我们需要一个损失函数来度量模型的好坏，或许可以使用误分类点的总数来作为损失函数，当损失函数值为零时，所有的点就都被正确分类了，但是，这个函数很显然不是关于$w,b$的可导函数，那么也就没办法用梯度下降函数来找到它的最小值了。

我们选择另外一种方式来定义损失函数。

我们选择从误分类点到超平面的总距离来度量。

在输入空间中，任何一点$x_0$到超平面的距离是：
$$
\frac{1}{||w||}|wx_0 +b|
$$
$||w||$就是向量$w$的模（或者叫长度、$L_2$范数）。对于误分类的点$(x_i,y_i)$来说：
$$
-y_i (wx_i +b)>0
$$
所以我们可以去掉距离表达式中的绝对值：
$$
-\frac{1}{||w||}y_i(wx_i+b)
$$
作为一个方向向量，$||w||$可以直接丢掉，我们得到损失函数的表达式：
$$
L(w,b)=-\sum_{x_i\in M}y_i(wx_i+b)
$$
其中$M$为误分类点的集合。

$L(w,b)$是关于$w,b$的连续可导函数，于是就可以使用梯度下降了。

##感知机学习算法

损失函数的梯度：
$$
\nabla_wL(w,b)=-\sum_{x_i\in M}y_ix_i\\
\nabla_bL(w,b)=-\sum_{x_i\in M}y_i
$$
那么，我们就得到一个可以直接写在代码中的赋值表达式，通过这个表达式来更新$w,b$的值，从而找到正确的分类超平面：
$$
w\leftarrow w+\eta y_ix_i\\
b\leftarrow b+\eta y_i
$$

$\eta$是学习率，用来调节梯度下降的步长。

最后，给出算法的描述：

>1. 选取初始值$w_0,b_0$
>
>2. 在训练集中选取数据$(x_i,y_i)$
>
>3. 如果$y_i(wx_i+b)\leq 0$
>   $$
>   w\leftarrow w+\eta y_ix_i\\
>   b\leftarrow b+\eta y_i
>   $$
>
>4. 转至第二步，循环直至训练集中没有误分类点
#笔记#