感知机能够说是最古老的分类方法之一了，在1957年就已经提出。今天看来它的分类模型在大多数时候泛化能力不强，可是它的原理却值得好好研究。由于研究透了感知机模型，学习支持向量机的话会下降很多难度。同时若是研究透了感知机模型，再学习神经网络，深度学习，也是一个很好的起点。这里对感知机的原理作一个小结。html
感知机的思想很简单，好比咱们在一个平台上有不少的男孩女孩，感知机的模型就是尝试找到一条直线，可以把全部的男孩和女孩隔离开。放到三维空间或者更高维的空间，感知机的模型就是尝试找到一个超平面，可以把全部的二元类别隔离开。固然你会问，若是咱们找不到这么一条直线的话怎么办？找不到的话那就意味着类别线性不可分，也就意味着感知机模型不适合你的数据的分类。使用感知机一个最大的前提，就是数据是线性可分的。这严重限制了感知机的使用场景。它的分类竞争对手在面对不可分的状况时，好比支持向量机能够经过核技巧来让数据在高维可分，神经网络能够经过激活函数和增长隐藏层来让数据可分。算法
用数学的语言来讲，若是咱们有m个样本，每一个样本对应于n维特征和一个二元类别输出，以下：编程
\((x_1^{(0)}, x_2^{(0)}, ...x_n^{(0)}, y_0), (x_1^{(1)}, x_2^{(1)}, ...x_n^{(1)},y_1), ... (x_1^{(m)}, x_2^{(m)}, ...x_n^{(m)}, y_m)\)网络
咱们的目标是找到这样一个超平面，即：函数
\(\theta_0 + \theta_{1}x_1 + ... + \theta_{n}x_{n} = 0\) post
让其中一种类别的样本都知足\(\theta_0 + \theta_{1}x_1 + ... + \theta_{n}x_{n} > 0\) ，让另外一种类别的样本都知足\(\theta_0 + \theta_{1}x_1 + ... + \theta_{n}x_{n} < 0\) ，从而获得线性可分。若是数据线性可分，这样的超平面通常都不是惟一的，也就是说感知机模型能够有多个解。学习
为了简化这个超平面的写法，咱们增长一个特征\(x_0 = 1 \) ，这样超平面为\( \sum\limits_{i=0}^{n}\theta_{i}x_{i} = 0\)。进一步用向量来表示为： \(\theta \bullet x = 0\),其中\(\theta \)为(n+1)x1的向量，x为(n+1)x1的向量, \(\bullet \)为内积，后面咱们都用向量来表示超平面。优化
而感知机的模型能够定义为：\( y = sign(\theta \bullet x)\) 其中：htm
$$sign(x)=
\begin{cases}
-1& {x<0}\\
1& {x\geq 0}
\end{cases}$$blog
为了后面便于定义损失函数，咱们将知足\(\theta \bullet x > 0\)的样本类别输出值取为1，知足\(\theta \bullet x < 0\)的样本类别输出值取为-1， 这样取y的值有一个好处，就是方便定义损失函数。由于正确分类的样本知足 \(y\theta \bullet x > 0\)，而错误分类的样本知足 \(y\theta \bullet x < 0\)。咱们损失函数的优化目标，就是指望使误分类的全部样本，到超平面的距离之和最小。
因为\(y\theta \bullet x < 0\)，因此对于每个误分类的样本\(i \) ，到超平面的距离是
\(- y^{(i)}\theta \bullet x^{(i)}\big / ||\theta||_2\),
其中\(||\theta||_2\)为L2范数。
咱们假设全部误分类的点的集合为M，则全部误分类的样本到超平面的距离之和为：
\(- \sum\limits_{x_i \in M}y^{(i)}\theta \bullet x^{(i)}\big / ||\theta||_2\),
这样咱们就获得了初步的感知机模型的损失函数。
咱们研究能够发现，分子和分母都含有\(\theta\),当分子的\(\theta\)扩大N倍时，分母的L2范数也会扩大N倍。也就是说，分子和分母有固定的倍数关系。那么咱们能够固定分子或者分母为1，而后求另外一个即分子本身或者分母的倒数的最小化做为损失函数，这样能够简化咱们的损失函数。在感知机模型中，咱们采用的是保留分子，即最终感知机模型的损失函数简化为：
\( J(\theta) = - \sum\limits_{x_i \in M}y^{(i)}\theta \bullet x^{(i)}\)
题外话，若是你们了解过支持向量机，就发现支持向量机采用的是固定分子为1，而后求\(1/ ||\theta||_2\)的最大化。采用不一样的损失函数主要与它的后面的优化算法有关系。
上一节咱们讲到了感知机的损失函数：\( J(\theta) = - \sum\limits_{x_i \in M}y^{(i)}\theta \bullet x^{(i)}\)，其中M是全部误分类的点的集合。这个损失函数能够用梯度降低法或者拟牛顿法来解决，经常使用的是梯度降低法。
可是用普通的基于全部样本的梯度和的均值的批量梯度降低法（BGD）是行不通的，缘由在于咱们的损失函数里面有限定，只有误分类的M集合里面的样本才能参与损失函数的优化。因此咱们不能用最普通的批量梯度降低,只能采用随机梯度降低（SGD）或者小批量梯度降低（MBGD）。若是对这几种梯度降低法的区别不了解，能够参考个人另外一篇文章梯度降低（Gradient Descent）小结。
感知机模型选择的是采用随机梯度降低，这意味着咱们每次仅仅须要使用一个误分类的点来更新梯度。
损失函数基于\(\theta\)向量的的偏导数为：
\( \frac{\partial}{\partial \theta}J(\theta) = - \sum\limits_{x_i \in M}y^{(i)}x^{(i)}\)
\(\theta\)的梯度降低迭代公式应该为：
\(\theta = \theta + \alpha\sum\limits_{x_i \in M}y^{(i)}x^{(i)} \)
因为咱们采用随机梯度降低，因此每次仅仅采用一个误分类的样原本计算梯度，假设采用第i个样原本更新梯度，则简化后的\(\theta\)向量的梯度降低迭代公式为：
\(\theta = \theta + \alpha y^{(i)}x^{(i)} \)
其中\(\alpha\)为步长，\(y^{(i)}\)为样本输出1或者-1，\(x^{(i)}\)为(n+1)x1的向量。
前两节咱们谈到了感知机模型，对应的损失函数和优化方法。这里咱们就对感知机模型基于随机梯度降低来求\(\theta\)向量的算法作一个总结。
算法的输入为m个样本，每一个样本对应于n维特征和一个二元类别输出1或者-1，以下：
\((x_1^{(0)}, x_2^{(0)}, ...x_n^{(0)}, y_0), (x_1^{(1)}, x_2^{(1)}, ...x_n^{(1)},y_1), ... (x_1^{(m)}, x_2^{(m)}, ...x_n^{(m)}, y_m)\)
输出为分离超平面的模型系数\(\theta\)向量
算法的执行步骤以下：
1) 定义全部\(x_0\)为1。选择\(\theta\)向量的初值和 步长\(\alpha\)的初值。能够将\(\theta\)向量置为0向量，步长设置为1。要注意的是，因为感知机的解不惟一，使用的这两个初值会影响\(\theta\)向量的最终迭代结果。
2) 在训练集里面选择一个误分类的点\((x_1^{(i)}, x_2^{(i)}, ...x_n^{(i)}, y_i)\), 用向量表示即\((x^{(i)}, y^{(i)})\)，这个点应该知足：\(y^{(i)}\theta \bullet x^{(i)} \leq 0\)
3) 对\(\theta\)向量进行一次随机梯度降低的迭代：\(\theta = \theta + \alpha y^{(i)}x^{(i)} \)
4）检查训练集里是否还有误分类的点，若是没有，算法结束，此时的\(\theta\)向量即为最终结果。若是有，继续第2步。
上一节的感知机模型的算法形式咱们通常称为感知机模型的算法原始形式。对偶形式是对算法执行速度的优化。具体是怎么优化的呢？
经过上一节感知机模型的算法原始形式\(\theta = \theta + \alpha y^{(i)}x^{(i)}\)能够看出，咱们每次梯度的迭代都是选择的一个样原本更新\(\theta\)向量。最终通过若干次的迭代获得最终的结果。对于历来都没有误分类过的样本，他被选择参与\(\theta\)迭代的次数是0，对于被屡次误分类而更新的样本j，它参与\(\theta\)迭代的次数咱们设置为\(m_j\)。若是令\(\theta\)向量初始值为0向量， 这样咱们的\(\theta\)向量的表达式能够写为：
\(\theta = \alpha \sum\limits_{j=1}^{m}m_jy^{(j)}x^{(j)} \)
其中\(m_j\)为样本\((x^{(j)}, y^{(j)})\)在随机梯度降低到当前的这一步以前因误分类而更新的次数。
每个样本\((x^{(j)}, y^{(j)})\)的\(m_j\)的初始值为0，每当此样本在某一次梯度降低迭代中因误分类而更新时，\(m_j\)的值加1。
因为步长\(\alpha\)为常量，咱们令\(\beta_j = \alpha m_j\),这样\(\theta\)向量的表达式为:
\(\theta = \sum\limits_{j=1}^{m}\beta_j y^{(j)}x^{(j)} \)
在每一步判断误分类条件的地方，咱们用 \(y^{(i)}\theta \bullet x^{(i)} < 0\) 的变种 \(y^{(i)}\sum\limits_{j=1}^{m}\beta_j y^{(j)}x^{(j)}\bullet x^{(i)} < 0\) 来判断误分类。注意到这个判断误分类的形式里面是计算两个样本\(x^{(i)}和x^{(j)}\)的内积，并且这个内积计算的结果在下面的迭代次数中能够重用。若是咱们事先用矩阵运算计算出全部的样本之间的内积，那么在算法运行时， 仅仅一次的矩阵内积运算比屡次的循环计算省时。 计算量最大的判断误分类这儿就省下了不少的时间，，这也是对偶形式的感知机模型比原始形式优的缘由。
样本的内积矩阵称为Gram矩阵，它是一个对称矩阵，记为 \( G = [x^{(i)} \bullet x^{(j)} ]\)
这里给出感知机模型的算法对偶形式的内容。
算法的输入为m个样本，每一个样本对应于n维特征和一个二元类别输出1或者-1，以下：
\((x_1^{(0)}, x_2^{(0)}, ...x_n^{(0)}, y_0), (x_1^{(1)}, x_2^{(1)}, ...x_n^{(1)},y_1), ... (x_1^{(m)}, x_2^{(m)}, ...x_n^{(m)}, y_m)\)
输出为分离超平面的模型系数\(\theta\)向量
算法的执行步骤以下：
1) 定义全部\(x_0\)为1，步长\(\alpha\)初值，设置\(\beta\)的初值0。能够将\(\alpha\)设置为1。要注意的是，因为感知机的解不惟一，使用的步长初值会影响\(\theta\)向量的最终迭代结果。
2) 计算全部样本内积造成的Gram矩阵G。
2) 在训练集里面选择一个误分类的点\((x^{(i)}, y^{(i)})\)，这个点应该知足： \(y^{(i)}\sum\limits_{j=1}^{m}\beta_j y^{(j)}x^{(j)}\bullet x^{(i)} \leq 0\)， 在检查是否知足时能够经过查询Gram矩阵的\(g_{ij}\) 的值来快速计算是否小于0。
3) 对\(\beta\)向量的第i个份量进行一次更新：\(\beta_i= \beta_i+ \alpha \)
4）检查训练集里是否还有误分类的点，若是没有，算法结束，此时的\(\theta\)向量最终结果为下式。若是有，继续第2步。
\(\theta = \sum\limits_{j=1}^{m}\beta_j y^{(j)}x^{(j)} \)
其中\(\beta_j \) 为\(\beta\)向量的第j个份量。
感知机算法是一个简单易懂的算法，本身编程实现也不太难。前面提到它是不少算法的鼻祖，好比支持向量机算法，神经网络与深度学习。所以虽然它如今已经不是一个在实践中普遍运用的算法，仍是值得好好的去研究一下。感知机算法对偶形式为何在实际运用中比原始形式快，也值得好好去体会。
（欢迎转载，转载请注明出处。欢迎沟通交流： liujianping-ok@163.com）