perceptron learning algorithm - linear separability

数学放下来太多年，machine learning教材又很少涉及数学方面的解析，学起来挺吃力。

这次给“感知器 - 线性可分"补充一些数学方面的笔记，防止过两天又忘了。

感知器是ML/神经网络的基础概念，反馈的是yes/no，或者1/-1，或者是/非。

x：一组输入变量

w：权重

每一个输入变量x(i)都对应一个权重w(i)

转化为向量表达如下图所示：

最终演化为向量w和向量x之间的”内积“（又称”点积“）

w^T：矩阵w的转置；h(x) = sign(w^T x) 是简化了的数学语言的表达。

内积（又称”点积“），举例来说：

向量a = [a1, a2, ... , an]；向量b = [b1, b2, ... , bn]

内积 a b = a1 b1 + a2 b2 + ... + an bn

向量的内积有两种定义方式：在欧几里得空间中引入笛卡儿坐标系，向量之间的点积既可以由向量坐标的代数运算获得，也可以通过引入两个向量的长度和角度等几何概念求解。

内积代数定义

设二维空间内有两个向量a = (x1, y1) 和 b = (x2, y2)，它们的数量积为以下实数：

a b = x1 * y1 + x2 * y2

更一般地，n维向量的内积定义如下：

向量内积的代数定义

内积几何定义

向量内积的几何定义

了解了向量内积的代数与几何定义后，就比较容易理解下面的胶片 —— 二维平面的线性分类器

二维平面上，(w0 + w1 x1 + w2 x2) 表示平面上的一条直线

x：特征向量，在二维空间里，x即平面上的点（向量）

y：标签，在感知器里为正、负

hypothesis：二维平面上的线，如果正标签（点）全部在某条线的一边，负标签（点）全部在该线的另一边，则感知器存在线性分类器

如何寻找这条”直线“（线性可分）呢，需要在Data（资料）的输入x（多维向量，二维空间的话即为平面上的点[集 set]）里循环，通过循环来不断修正权重向量w，使得所有内积的结果y(n)都与资料的输出Y符号吻合。

通过资料数据的循环来修正权重向量w

在循环过程中，遇到y(n,t)符号错误即修正w(t)，获得w(t+1)。

如果y为正，而y(n,t)计算得负，根据向量内积的几何定义，w(t)与x(n,t)的夹角过大（cos(夹角)为负）；因此需要修正w(t+1) = w(t) + x(n,t)

如果y为负，而y(n,t)计算得正，则说明w(t)与x(n,t)的夹角过小（cos(夹角)为正），因此需要修正w(t+1) = w(t) - x(n,t)

考虑到y(n,t)的符号，可以统一表达为w(t+1) = w(t) + y(n,t) x(n,t)，即如胶片所示。

用二维平面举例，如何在hyothesis（平面）中找到合适的g（直线），来对x进行分类：

第一步

初始条件：w0=0, x1=1，即没有直线，所有x（点）的分类都不对；

对于第一次更新，w(0+1) = w(0) + x(1)

第二步

根据内积的几何定义，w(t)的法向量（二维平面里为垂直于w(t)的直线）的一边，内积标量全部为正（夹角在0到90度之间，上图蓝色部分），而法向量的另一边，内积标量全部为负（夹角在90到180度之间，上图红色部分）。对x的分类方式即通过w(t)的法向量进行划分，获得不同的符号（正负）。

第三步

经过10次纠正后，所有点都分类正确

假如通过有限次迭代，存在一条直线，使得所有的点都可经过计算获得正确的符号（正负），则该数据集线性可分。

线性可分

胶片来自cousera，台大，林轩田，《机器学习基石》

数学部分大多来自百度百科