模式识别系列（一）感知器算法（PLA）

  本系列博客主要是对我大三这一年学到的知识整理，参考课程的ppt和林轩田老师的机器学习基石，侵删

  感知器算法主要用于线性可分特征向量的二分类问题。算法的核心是两个要点，一是线性可分，二是二分类（可以1vN或者1v1拓展至多类，暂且不讨论）。

  要说线性可分，首先需要明确什么是特征向量。特征向量就是原始数据经过特征提取算法之后生成的一个高维的向量，你可以认为它的每一个维度表示了目标的一个属性。例如：

输入是一个图像，而输出是一个d维的向量，中间是不同的特征提取算法（像素，主成分分析，词袋等等）。而线性可分指的就是有一条高维的直线（超平面），可以让两类数据分别置于超平面的两侧。而既然分类面是一个超平面，那么分类的结果只能是平面的一侧和另一侧中的一个，也就是一个二分类。我们假设特征向量是一个二维的特征向量，线性可分和不可分的例子如下： 上图的x轴和y轴分别是特征向量的两个维度，而黑色的线就是分界面。可以很直观地感到第一张图是线性可分，而二是线性不可分，三的分界面是一个曲线，因此也是线性不可分。

  由此，我们可以定义分界面的函数。从最简单的二维说起，我们知道一条二维直线可以表示为 a x + b y + c = 0 ax + by + c = 0 ax+by+c=0,那么，我们就可以定义评估函数 g ( x ) = w 1 x 1 + w 2 x 2 + w 0 g(x) = w_1x_1 + w_2x_2 + w_0 g(x)=w1​x1​+w2​x2​+w0​ 这个评估函数就代表了了上面的那条直线，当 g ( x ) > 0 g(x) > 0 g(x)>0,可以说特征向量位于分界面的正侧，当 g ( x ) < 0 g(x) 0 y_nw_f^Tx_n >0 yn​wfT​xn​>0对任意( x n , y n x_n,y_n xn​,yn​)都成立，即 y n w f T x n ⩾ min ⁡ n ( y n w f T x n ) > 0 y_nw_f^Tx_n \geqslant\underset{n}{ \operatorname{min}}(y_nw_f^Tx_n)>0 yn​wfT​xn​⩾nmin​(yn​wfT​xn​)>0 在一次迭代后: w f T ⋅ w t + 1 = w f T ⋅ w t + w f T y n x n ⩾ w f T ⋅ w t + min ⁡ n ( y n w f T x n ) > w f T ⋅ w t \begin{aligned} w_{f}^{T} \cdot w_{t+1} &= w_f^T\cdot w_{t} + w_f^Ty_nx_n \\ &\geqslant w_f^T \cdot w_{t} +\underset{n}{\min}(y_nw_f^Tx_n) \\ & >w_f^T\cdot w_{t} \end{aligned} wfT​⋅wt+1​​=wfT​⋅wt​+wfT​yn​xn​⩾wfT​⋅wt​+nmin​(yn​wfT​xn​)>wfT​⋅wt​​ 因此 w f T ⋅ w t w_f^T \cdot w_t wfT​⋅wt​的值是在不断变大的，说明这两个向量在不断接近。 另一方面，由于只更新错分的样本,因此对于错误样本 ( x n , y n ) (x_n, y_n) (xn​,yn​), y n w t T x n ≤ 0 y_{n} w_{t}^{T} x_{n} \leq 0 yn​wtT​xn​≤0 ∥ w t + 1 ∥ 2 = ∥ w t + y n x n ∥ 2 = ∥ w t ∥ 2 + 2 y n w t T x n + ∥ y n x n ∥ 2 ≤ ∥ w t ∥ 2 + 0 + ∥ y n x n ∥ 2 ≤ ∥ w t ∥ 2 + max ⁡ n ∥ x n ∥ 2 \begin{aligned} \left\|w_{t+1}\right\|^{2} &=\left\|w_{t}+y_{n} x_{n}\right\|^{2} \\ &=\left\|w_{t}\right\|^{2}+2 y_{n} w_{t}^{T}x_{n}+\left\|y_{n} x_{n}\right\|^{2} \\ & \leq\left\|w_{t}\right\|^{2}+0+\left\|y_{n}x_{n}\right\|^{2} \\ & \leq\left\|w_{t}\right\|^{2}+\max _{n}\left\| x_{n}\right\|^{2} \end{aligned} ∥wt+1​∥2​=∥wt​+yn​xn​∥2=∥wt​∥2+2yn​wtT​xn​+∥yn​xn​∥2≤∥wt​∥2+0+∥yn​xn​∥2≤∥wt​∥2+nmax​∥xn​∥2​ 假设从w=0开始迭代，结合上面两个式子，则有 w f T ∥ w f ∥ w T ∥ w T ∥ ≥ T ⋅ min ⁡ n ( y n w f T x n ) ∥ w f ∥ ⋅ T ⋅ max ⁡ n ∥ x n ∥ 2 = T ⋅  constant  \frac{w_{f}^{T}}{\left\|w_{f}\right\|} \frac{w_{T}}{\left\|w_{T}\right\|} \geq \frac{T \cdot \underset{n}{\min}(y_nw_f^Tx_n) }{\left\|w_{f}\right\| \cdot \sqrt{T} \cdot \underset{n}{\max}\left\| x_{n}\right\|^{2}} = \sqrt{T} \cdot \text { constant } ∥wf​∥wfT​​∥wT​∥wT​​≥∥wf​∥⋅T ​⋅nmax​∥xn​∥2T⋅nmin​(yn​wfT​xn​)​=T ​⋅ constant  可以证明迭代次数 T T T有上确界

  实际得到样本的时候，是否线性可分往往是未知的，PLA有可能并不收敛。对于这种情况，自然而然就想到一些近似地办法。比如试探法，尝试更新一次权重，如果正确分类的样本增多，就替换权重，否则保留最佳。再比如采用不同的步长，进行试探等等。或者采用别的方法，比如梯度下降，核向量机等等，这都是后话了。