# 2.感知机——入门的垫脚石

### 概述

每个算法都是为了解决一类问题，或者说解决之前的问题所创造出来的，而感知机，在解决一类问题的时候也暴露了很多问题，变相的推动了以后的算法的改进方向。

### 知识树

![1618031817787](assets/1618031817787.png)

> 苹果表示相对重要的



### 直观介绍

现在有一盘红豆和绿豆，怎么把红豆和绿豆分开来

![1618032628458](assets/1618032628458.png)

> 当红豆和绿豆放在一起时，它们却能自己分开来，为什么呢？

我们怎么区分呢，假设我们随意花如下的线

![1618032073968](assets/1618032073968.png)

> 这样是不是就完美的区分开来了，完美解决。
>
> 那么程序怎么知道x和y都大于0的豆是红豆呢？
>
> 或者说，它是怎么学会这个规则的？

那是不是只要一条直线不分错一个点，或者说尽可能的少分错点，那就是一条好的直线。

即：我们把所有分错的点和直线的距离的和（蓝色示例），求和的距离最小表示这条直线越好，因为这表示这条线分错的最少。

![1618032462253](assets/1618032462253.png)

> 如图中红色线的和的距离肯定比黑色或者黄色的线大。



### 总结

1. 一条直线不分错一个点，这就是好的直线。
2. 模型要尽可能找到好的直线。
3. 如果没有好的直线，在差的直线中找到好的直线。
4. 判断直线多差的方式：分错的点到直线的距离求和。



### 感知机模型

Perceptron

确定终究目标

f(x)

> 我们希望一个函数，如f(x)，进来一个豆，它告诉我们是红豆还是绿豆

f(x) = sign(w * x + b)

> sign如图：![1618034843122](assets/1618034843122.png)

把w * x + b 比作x，相当于给了一个“豆”进来，就只得到两个结果，也就是红豆（+1）或者绿豆（-1）。那么w * x + b 是什么？

w * x + b是超平面

![1618035195004](assets/1618035195004.png)

> 即那条黄色的分割线，且当豆在线的上面，就是红豆，在下面是绿豆。
>
> 超平面是n维欧氏空间中余维度等于一的线性子空间，也就是必须是(n-1)维度。即如果是2维，超平面就是1维，如果是3维，超平面就是2维。

w * x + b分别代表什么

> w是权重，x是特征的实际值，b是偏值
>
> 比如知道豆的直径，如x1表示某个豆的直径 = w1 * x1 + b1，大于1则是红豆，小于则是绿豆
>
> 有时候一个特征不一定能区分开来，可能还需要质量，(x1,x2)计算 = (w1, w2) * (x1, x2)
>
> 亦或者还有豆的光滑度，则有x1, x2, x3 ，这样就变成3维了。

**正式的说**

w * x + b 是一个n维空间中的超平面S，其中w是超平面的法向量，b是超平面的截距，这个超平面将特征空间划分成两部分，位于两部分的点分别被分为正负两类。所以，超平面S称为分离超平面。

特征空间也就是整个n维空间，样本的每个属性都叫一个特征，特征空间的意思是在这个空间中可以找到样本所有的属性的组合。



### 感知觉的学习策略

Learning policy

> 求空间中任意一个点X0到超平面S的距离

**函数间隔与几何间隔**

函数间距：![1618232951329](assets/1618232951329.png)

> 缺点：已知wx + b = 0，当不等于0时（比如1），那如果等比例放大缩小w和b是不是就更小，等同于1/2 (wx + b) = 1/2(wx) + 1/2(b) = 1/2，超平面是没有动的，但是结果却缩小了，那么模型就觉得它知道等比例缩小就能得到更小的结果。
>
> 这时候就引入几何间距

几何间距：![1618232969849](assets/1618232969849.png)



![1618232989614](assets/1618232989614.png)

> 加入了二范式，相当于有了一个度量的标准，即等比例缩小w时，外面的w也会等比例变化。

通俗来讲，函数间距是将你去吃饭的那段路本来要1000m，它改成1km，1就小于1000了，而几何间距就杜绝这种情况，只能都是m或者km



对于误分类数据而已，![1618233535293](assets/1618233535293.png)

> yi表示真实是+1还是-1
>
> w*xi+b表示预测的结果
>
> 绿豆预测成绿豆：预测结果w*xi+b < 0（绿豆），且真实为绿豆(-1)时，则- * -1(wxi + b) < 0。
>
> 绿豆预测成红豆：w*xi+b > 0，真实为绿豆-1，则- * -1 (wxi + b) > 0。
>
> 也就是说只要分错，那么数据一定是大于0

误分类点xi到超平面S的距离为：![1618233578508](assets/1618233578508.png)

因此，所有误分类点到超平面S的总距离为：![1618233886281](assets/1618233886281.png)

> M：误分类点的集合



### 感知觉的学习策略——原始形式

Learning policy

1. 任选一个超平面w0，b0

   > 随机初始化，如w0 = 1，可能有多个维度，如x0，x1，x2，那么w也会有w0，w1，w2的随机初始化

2. 采用梯度下降法极小化目标函数

   ![1618234010513](assets/1618234010513.png)

   > L：loss
   >
   > 这时候用的还是函数间隔，因为感知机的超平面的目标是不分错任何一个点。所以不存在说要某个点到超平面的距离无限的小。
   >
   > 也可以用几何间隔，但是会增加计算量，没有必要，但后面基本都是用几何间隔。
   >
   > 侧面反映了感知机只能在线性可分的数据集上使用，也就是线性模型。

3. 更新w，b

   ![1618234028471](assets/1618234028471.png)



### 例子

Example

训练数据中，正例（y=+1）点位x1 = (3,3)T，x2 = (4,3)T，负例（y=-1）为x3 =  (1, 1)T，求解感知机模型f(x) = sign(w*x + b)，其中w = (w1, w2)T，x = (x1, x2)T

解：

1. 构造损失函数

   ![1618234528190](assets/1618234528190.png)

2. 梯度下降求解w，b。设步长为1

   1. 取初值w0 = 0，b0 = 0
   2. 对于x1，y1(w0 * x1 + b0) = 0未被正确分类，更新w，b。w1 = w0 + x1y1 = (3,3)T，b1 = b0 + y1 = 1 => w1 * x + b1 = 3x + 3x + 1

3. 对x1，x2，显然yi(w1 * xi + b1) > 0，被正确分类，不做修改。对于x3，y3(w1 * x3 + b1) 应该小于0，结果是大于0被误分类，更新w，b。

   ![1618234885210](assets/1618234885210.png)

4. 以此往复，直到没有误分类点，损失函数达到极小。

   ![1618234973878](assets/1618234973878.png)

   

### 总结

Summarization

1. 感知机通过构造超平面的形式划分不同类的点。

2. 感知机属于线性判别模型，因为它的判别边界是线性的。

3. 函数间隔和几何间隔的区别

   > 大多时候是用的几何间隔，因为有“度量标准”，而感知机是误分类驱动，目标是不分错任何一个点，即结果为0，所以即使度量标准改变也没用。