线性分类器-两类样本的单样本修正法

1.线性判别函数

设样本在n维空间中描述，比如2维空间对应点(x1,x2)( x_{1},x_{2})(x1​,x2​)，3维空间对应点(x1,x2,x3)( x_{1},x_{2},x_{3})(x1​,x2​,x3​)。。。，并且这里只考虑两类别问题，即这些样本只可以分为两类，那么只需要描述一个判别函数：

g(x)=wTx+w0g(x)=w^{T}x+w_{0}g(x)=wTx+w0​ ，2维空间下等价于 g(x)=w1x1+w2x2+w0g(x)=w_{1}x_{1}+w_{2}x_{2}+w_{0}g(x)=w1​x1​+w2​x2​+w0​ ，当g(x)=0时，该判别函数为一条直线，而在多维空间中就是一个超平面了。

写成齐次形式：g(x)=aTyg(x)=a^{T}yg(x)=aTy ，这里的a=[wTw0]，y=[x1]a= [wTw0]" role="presentation">[wTw0]$$\left[\begin{array}{c}{w}^T\\ w_0\end{array}\right]$$ ，y= [x1]" role="presentation">[x1]$$\left[\begin{array}{c}x\\ 1\end{array}\right]$$a=[wTw0​​]，y=[x1​]，其中y向量是齐次对齐的。

那么这个线性判别函数如何进行二分类问题呢？这里需要定义判别准则：

比如有如下样本点，红蓝对应了ω1ω2ω_{1}ω_{2}ω1​ω2​两类样本点，将某个(x1,x2)( x_{1},x_{2})(x1​,x2​)带入g(x)，如果>0则表示划为ω1ω_{1}ω1​类别（红色），反之是蓝色，这个g(x)即中间的一条直线。

如下图所示，这种无法用一条直线划分的，是不能进行线性分类的，属于非线性分类！

注意这里我们拿到的样本点是已知分类的，下面就是找这个判别函数的过程了，即计算w1w2w0w_{1}w_{2}w_{0}w1​w2​w0​系数。在这之前，一般会对样本进行规范化处理。

2. 样本规范化

因为我们拿到的样本是已知分类的，为了后面简化计算，一般首先会对样本进行规范化处理，处理过程很简单，即将某一类样本取反，比如样本1是(0,1)(0,2) ，样本2是 (1,0)(2,0) ，可以对样本2取反变为 (-1,0)(-2,0) ，这样我们只需要判断g(x)是否一直>0即可，无需在迭代中进行条件判定。

3.感知准则函数法

如何求解判别函数g(x)呢？这里使用的是Rosenblatt的感知准则函数法进行梯度下降求解。
首先定义感知准则函数：

这么一看有点懵逼，它是怎么来的呢？

如果某个样本yky_{k}yk​被错分，那么此时g(x)=aTyk<0g(x)=a^{T}y_{k}<0g(x)=aTyk​<0，加上负号，累加所有错分的样本(γkgamma^{k}γk)，即为该函数Jp(a)J_{p}(a)Jp​(a)。当a对应的w1w2w0w_{1}w_{2}w_{0}w1​w2​w0​求出的函数值为最小值(应该为0)时，无错分样本。

下面就可以通过梯度下降求该函数的最小值了。
未知量为a向量，按照梯度下降的理论，需要进行迭代a，即：
a(k+1)=a(k)−ρ▽Ja(k+1) = a(k) - ho riangledown Ja(k+1)=a(k)−ρ▽J （这里ρ hoρ为步长）
▽J=∂J/∂a=∑−yi riangledown J= partial J / partial a = sum_{}^{}-y_{i}▽J=∂J/∂a=∑​−yi​
最后 a(k+1)=a(k)+ρ∑yia(k+1) = a(k) + hosum_{}^{}y_{i}a(k+1)=a(k)+ρ∑​yi​ ，即每一步将错分的样本乘以某个系数加到权向量上。

4.单样本修正

通常，一次将所有错误样本进行修正不是效率最高的做法，更常用是每次只修正一个样本或一批样本的固定增量法。把样本集看做一个不断重复出现的序列而逐个加以考虑。对于任意权向量a(k)，如果他把某个样本分错了，则对a(k)做一次修正。这种方法称为单样本修正法。
那么上面的梯度下降可以简化为：
a(k+1)=a(k)+ρyia(k+1) = a(k) + ho y_{i}a(k+1)=a(k)+ρyi​ ，一般ρ hoρ取值1。
给a(k)a(k)a(k)一个初值，就可以进行迭代计算了。

5.直观的理解

通过向量的角度，可以直观的理解整个过程。
g(x)=aTyg(x)=a^{T}yg(x)=aTy 实际上是两个向量相乘，即向量的内积：

当内积>0时，两个向量夹角锐角；
当内积=0时，两个向量直角；
当内积<0时，两个向量钝角。
当我们拿到一个样本点向量yiy_{i}yi​(比如(0,1)），一个权重向量a(k)，相乘大于0才能符合要求，当某个样本点和权重向量相乘小于0时，我们对权重向量进行向量相加调整：a(k+1)=a(k)+yia(k+1) = a(k) + y_{i}a(k+1)=a(k)+yi​ ，向量相加是什么操作呢？初中就学过了：

实际上加完，a(k+1) 向量和yiy_{i}yi​之间的夹角更小了，更有可能变为锐角！也就是说整个梯度下降，是通过向量相加来一点点调整纠正中间的判别函数即直线的！符合的样本点不关心，不符合的样本点对判别函数直线施加一点自身的“力”，拉扯一下这根直线，是不是就生动了。

6.题目举例