感知器算法

  平面上有颜色不同的两类点,我们希望找到一条直线,将这两类点尽可能地隔开,这就是机器学习中最简单的分类问题.

平面上的一些点

  为了找到这条直线,我们先以原点为起点,任取待分类的一点为终点,得到一个向量$\,\bm w_1\,$,再以$\,\bm w_1\,$为法向量作一条过原点的直线.

第一次找到的直线

显然,这样的一条直线是很粗糙的,我们应该想办法去修正它.为了便于描述,我们把蓝色的点标记为$\,1$,而黄色的点标记为$\,-1$,这些点记为$\,\bm x_{i}$,他们对应的标记为$\,y_i$.那么,如果$$\sgn(\bm w_1\cdot\bm x_i)=y_i,$$就说明这个点已经被正确分类.如果$\,\bm x_i\,$还没有被正确分类,我们就专门为$\,\bm x_i\,$去调整直线的法向量:$$\bm w_2=\bm w_1+y_i\bm x_i.$$

调整得到的新法向量

这样,再以$\,\bm w_2\,$为法向量,作一条过原点的直线,就能把之前分类错误的点正确分类了.

调整后的直线

不过目前还是没有将全部的点分类正确,但是相比前一条直线已经好很多了,所以我们可以继续重复前面的调整步骤.

  可以证明,当真的存在一条“完美”的分隔直线时,这样的算法是收敛的.因为,如果存在一条“完美”直线,我们可以设它的法向量为$\,\bm w$,并且是一个单位向量.用$\,\bm w_t\,$表示第$\,t\,$个法向量,用$\,\bm x_{i,t}\,$表示第$\,t\,$次发现的错误点.那么有$$y_i\bm w\cdot\bm x_{i}\geqslant\min_iy_i\bm w\cdot\bm x_{i}>0,$$从而\begin{align}
\bm w\cdot\bm w_{t+1}&=\bm w\cdot(\bm w_t+y_i\bm x_{i,t})\notag\\
&\geqslant \bm w\cdot\bm w_t+\min_iy_i\bm w\cdot\bm x_{i}\label{eq10021}\\
&>\bm w\cdot\bm w_t\notag.
\end{align}另一方面,注意到只有遇到错误的点时才会对$\,\bm w_t\,$进行调整,所以\begin{align}
\bm w_{t+1}^2&=(\bm w_t+y_i\bm x_{i,t})^2\notag\\
&=\bm w_t^2+2y_i\bm w_t\bm x_{i,t}+\bm x_{i,t}^2\notag\\
&<\bm w_t^2+\bm x_{i,t}^2\notag\\
&\leqslant\bm w_t^2+\max_i\bm x_{i}^2.\label{eq10022}
\end{align}如果记$$R^2=\max_i\bm x_i^2,\rho=\min_iy_i\bm w\cdot\bm x_i,\bm w_0=\bm 0,$$那么由\eqref{eq10021}式有$$\bm w\cdot\bm w_t\geqslant t\cdot\min_iy_i\bm w\cdot\bm x_{i}=t\rho,$$由\eqref{eq10022}式有$$\bm w_t^2\leqslant t\cdot\max_i\bm x_{i}^2=tR^2.$$进而$$1\geqslant\bm w\cdot\frac{\bm w_t}{|\bm w_t|}\geqslant\sqrt t\cdot\dfrac{\rho}{R},$$因此,经过不超过$\,\dfrac{R^2}{\rho^2}\,$次的调整,就能得到一条“完美”的分隔直线.

完整的调整过程

  对于这种可以找到一条直线将其完美分隔的数据集,我们称它为线性可分的,像下图中的点就不是线性可分的,此时感知器算法不再适用.

线性不可分的数据


   文本的Wolfram Notebook文件在这里,里面包含完整的算法.

  参考资料 台湾大学《机器学习基石》

您的支持将鼓励我继续创作!