ML基石_2_LearnAnswer2

回归

上一篇，我们讲述了学习问题，其实质是

A takes D and H to get g which is approach to f.

这里写图片描述

本篇，将要探讨简单地二分类问题，即回答yes or no。

Perception假设集

感知器的数学模型

感知器的数学模型，简单来说就是

h(x)=sign((∑i=1nwixi)−threshold)

h(x) = sign((\sum_{i=1}^n w_i x_i)-threshold) 其中，xix_i是数据xx的第ii个分量，wiw_i是不同分量的权重。

上式，可简化为：

h(x)=sign(∑i=0nwixi)=sign(wx)

h(x)=sign(\sum_{i=0}^n w_i x_i)=sign(wx) 其中，w,xw,x表示对应的向量。具体来说，ww指定了超平面的唯一位置，不同的ww组成了假设集。

在下面的二维数据空间中： ww指c(w0,w1,w2)c(w_0,w_1,w_2)，xx指c(1,x1,x2)c(1,x_1,x_2)

感知器的图像意义

感知器，实际上是 linear(binary) classifiers，在二维空间中如图

这里写图片描述

PLA(感知器学习算法)

上文，知道了感知器的假设集H是由不同ww的值组成的。 问题随之而来，如何从H中选择合适的ww值，进而挑选出合适的g呢？

思路

思路是： 1. 在样本空间中，尽量满足g(xn)=f(xn)=yng(x_n)=f(x_n)=y_n的分类规则 2. 从w0w_0开始，根据D中分类错的数据不断对ww进行修正

修正规则

分类正确的依据

分类正确，等同于以下描述： 1. yn∗wxn>0y_n *w x_n >0 2. 当yn=1y_n=1时，w,xnw,x_n夹角小于90度；当yn=−1y_n=-1时，w,xnw,x_n夹角大于90度

所以，分类是否正确，关键是比较不同yny_n情况下，w,xnw,x_n相乘的符号，即两者的夹角是否大于90度。

分类错误的修正规则

上文所述的二维空间的数据集对应的w,xnw,x_n都是三维的，为了简化，本处使用二维的w,xnw,x_n来讨论。

首先，画图易知： 1. w+xnw+x_n靠近了xnx_n 2. w−xnw-x_n远离了xnx_n

因此，易得到对于分类错误的数据xnx_n，修正规则如下：

综上所述，修正规则可汇合为：

wt+1=wt+ynxn

w_{t+1}=w_t +y_n x_n

其中，xnx_n指代分类错的数据，即yn∗wtxn<0y_n *w_t x_n <0。

正如

A fault confessed is half redressed.

算法实施

算法遵循的原则为：

start from some w0 (say, 0), and ‘correct’ its mistakes on D

算法的伪代码如下：

while True:
    for i in range(n):
        if (y_n*w*x_n != 0):
            w = w + y_n*x_n  #在犯错误的点处更新权值
            break #跳出for循环，重新遍历各个点判断是否有错误
    #遍历完点还没有跳出，表示所有点都满足条件,得到答案
    w_result = w

可视化

这里写图片描述

可视化这里有一个问题，原来三维空间的w,xw,x为什么可以在二维空间来表示呢？ 答案：xx有一个分量为1，所以在二维空间平面上。ww可以分解为xx平面内的向量与垂直该平面的向量。其中，垂直向量对w,xw,x的内积正负并无影响，故只需考虑ww在xx平面中的投影与xx的角度关系。 但是，更新ww的时候还是应该按照三维的情况来处理。

PLA的实现保证

每次更新的性质

每次更新，并不能保证更新后的ww，使xnx_n分类正确，但能保证

ynwt+xxn>ynwtxn

y_n w_{t+x} x_n >y_n w_{t} x_n 即向着分类正确地方向移动

wtw_t越接近wfw_f

wtw_t与wfw_f的内积随着更新错误，越来越大

这里写图片描述

wtw_t的增长受到制约

wtw_t的增长受到最大xnx_n的制约

这里写图片描述

练习

这里写图片描述

小结

这里写图片描述

线性不可分的数据

这里写图片描述

这里写图片描述