什么是感知机？
1) 感知机的定义是什么？感知机(perceptron)是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别。
2) 感知机的取值是什么？
取+1和-1二值。
3) 感知机对应于输入空间(特征空间)中的什么？
感知机对应于输入空间中将实例划分为正负两类的分离超平面，属于判别模型。
4) 感知机学习的目的是什么？
感知机学习旨在求出将训练数据进行线性划分的分离超平面，为此，导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。
5) 感知机学习算法有什么特点？
感知机学习算法具有简单，并且易于实现的特点，分为原始形式和对偶形式。
6) 什么是感知机预测？
感知机预测是用学习得到的感知机模型对新的输入实例进行分类。它是神经网络与支持向量机的基础。
2.1感知机模型
1) 感知机模型的数学定义是什么？
定义 2.1(感知机) 假设输入空间(特征空间)是https://www.zhihu.com/equation?tex=+X+%5Csubseteq+R%5En+ ，输出空间是 y={+1, -1}。输入 https://www.zhihu.com/equation?tex=x+%5Cin+X 表示实例的特征向量，对应于输入空间(特征空间)的点；输出 https://www.zhihu.com/equation?tex=y+%5Cin+Y 表示实例的类别。由输入空间到输出空间的如下函数：
https://www.zhihu.com/equation?tex=f%28x%29+%3D+sign%28w%5Cbullet+x+%2B+b%29+%5Cspace%5Cspace%5Cspace%5Cspace%5Cspace%5Cspace%5Cspace%282.1%29
称为感知机。其中w和b为感知机模型参数， https://www.zhihu.com/equation?tex=w+%5Cin+R%5En 叫做权值(weight)或权值向量(weight vector)， https://www.zhihu.com/equation?tex=b+%5Cin+R 叫作偏置(bias)， https://www.zhihu.com/equation?tex=w%5Cbullet+x 表示w 和 x的内积。sign是符号函数，即：
https://www.zhihu.com/equation?tex=sign%28x%29+%3D+%5Cbigg+%5C%7B_%7B-1%2C+%5Cspace+x%3C0%7D%5E%7B%2B1%2C+%5Cspace+x+%5Cgeq+0%7D+%5Cspace%5Cspace%5Cspace%5Cspace%5Cspace%5Cspace%5Cspace%5Cspace%5Cspace+%282.2%29
2) 感知机是什么类型的模型？
感知机是一种线性分类模型，属于判别模型。
3) 感知机的几何解释？
感知机的几何解释是线性方程：
https://www.zhihu.com/equation?tex=w%5Cbullet+x+%2B+b+%3D+0+%5Cspace+%5Cspace%5Cspace%5Cspace%5Cspace+%282.3%29
对应于特征空间中的一个超平面S，其中w是从超平面的法向量，b是超平面的截距。
这个超平面将特征空间划分为两个部分。位于两部分的点(特征向量)分别被分为正、负两类。
因此，超平面S成为分离超平面(separating hyperplane),如图2.1所示。
感知机学习，由训练数据集(实例的特征向量及类别)
其中 ，求得感知机模型(2.1)，即求得模型参数w, b。感知机预测， 通过学习得到的感知机模型， 对于新的输入实例给出其对应的输出类别。
2.2 感知机的学习策略
2.2.1 数据集的线性可分性
1) 什么是感知机的线性可分性？
定义2.2 (数据集的线性可分性) 给定一个数据集
，
其中，如果存在某个超平面S
https://www.zhihu.com/equation?tex=w+%5Cbullet+x+%2B+b+%3D+0
能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，即对所有的 https://www.zhihu.com/equation?tex=y_i+%3D+%2B1 的实例i，有对所有的实例 i，有，则称数据集T为线性可分数据集(linearly separable data set)； 否则，成数据集T线性不可分。
2.2.2 感知机学习策略
1) 感知机的目的是什么？
假设训练数据集是线性可分的，感知机学习的目的是求得一个能够将训练集整实例点和负实例点完全正确分开的分离超平面。
为了找出这样的超平面，即确定感知机模型参数w 和 b, 需要确定一个学习策略，即定义(经验)损失函数并将损失函数极小化。
2) 损失函数的选择依据是什么？
损失函数的一个自然选择是误分类点的总数，但是这样损失函数不是参数w和b的连续可到函数，不易优化。
损失函数的另一个选择是误分类点到超平面S的总距离，这是感知机所采用的。为此，首先写出输入空间中任一点 https://www.zhihu.com/equation?tex=x_0 到超平面S的距离：
https://www.zhihu.com/equation?tex=%5Cfrac%7B1%7D%7B%7C%7Cw%7C%7C%7D%7Cw+%5Cbullet+x_0+%2B+b%7C
这里， https://www.zhihu.com/equation?tex=%7C%7Cw%7C%7C 是w的 https://www.zhihu.com/equation?tex=L_2 范数。
其次，对于误分类的数据来说， https://www.zhihu.com/equation?tex=-y_i%28w+%5Cbullet+x_i+%2B+b%29+%3E+0 成立。因为当时，，而当时， https://www.zhihu.com/equation?tex=y_i+%3D+%5Cunderline%2B+1 。因此，误分类点 https://www.zhihu.com/equation?tex=x_i 到超平面S的距离是 https://www.zhihu.com/equation?tex=%5Cfrac%7B1%7D%7B%7C%7Cw%7C%7C%7D+y_i%28w+%5Cbullet+x_i+%2B+b%29
这样，假设超平面S的误分类点集合为M，那么所有误分类点到超平面S的总距离为 https://www.zhihu.com/equation?tex=%5Cfrac%7B1%7D%7B%7C%7Cw%7C%7C%7D+%5Csum_%7Bx_i+%5Cin+M%7D+y_i+%28w+%5Cbullet+x_i+%2B+b%29
不考虑 https://www.zhihu.com/equation?tex=%5Cfrac%7B1%7D%7B%7C%7Cw%7C%7C%7D ,就得到感知机学习的损失函数。
3) 感知机学习的损失函数如何定义的？和经验风险函数有什么关系？
给定训练数据集 https://www.zhihu.com/equation?tex=T+%3D+%5C%7B%28x_1%2C+y_1%29%2C%28x_2%2C+y_2%29%2C...%2C%28x_N%2C+y_N%29+%5C%7D
其中， https://www.zhihu.com/equation?tex=x_i+%5Cin+X+%3D+R%5E%7Bn%7D , https://www.zhihu.com/equation?tex=y_i+%5Cin+Y+%3D+%7B%2B1%2C+-1%7D%2C+i+%3D+1%2C+2%2C...%2C+N 。感知机 https://www.zhihu.com/equation?tex=sign%28w+%5Cbullet+x+%2B+b%29 学习的损失函数定义为
https://www.zhihu.com/equation?tex=L%28w%2C+b%29+%3D+-+%5Csum_%7Bx_i+%5Cin+M%7D+y_i%28w+%5Cbullet+x_i+%2B+b%29+%5Cspace%5Cspace%5Cspace%5Cspace%5Cspace%282.4%29
其中M为误分类点的集合。这个损失函数就是感知机学习的经验风险函数。
4) 损失函数可以取到负值么？
显然，损失函数是非负的。
如果没有误分类点，损失函数值是0；
误分类点越少，误分类点距离超平面越近，损失函数值越小;
一个特定的样本点的损失函数，在误分类时是参数w, b的线性函数，在正确分类时是0。
因此，给定训练数据集T， 损失函数L(w, b)是w, b的连续可导函数。
感知机学习的策略是在假设空间中选取使损失函数式(2.4)最小的模型参数w, b,即感知机模型。
2.3 感知机学习算法
感知机的学习问题转化为求解损失函数式(2.4)的最优化问题，最优化的方法是随机梯度下降法。
2.3.1 感知机学习算法的原始形式
感知机学习算法是对一下最优化问题的算法，给定一个训练数据集
https://www.zhihu.com/equation?tex=T+%3D+%5C%7B%28x_1%2C+y_1%29%2C+%28x_2%2C+y_2%29%2C...%2C%28x_N%2C+y_N%29+%5C%7D
其中， https://www.zhihu.com/equation?tex=x_i+%5Cin+X+%3D+R%5E%7Bn%7D%2C+%5Cspace+y_i+%5Cin+Y+%3D+%5C%7B-1%2C+1%5C%7D%2C+%5Cspace+i+%3D+1%2C2%2C...%2CN ,求参数w 和 b，使其为一下损失函数极小化问题的解：
https://www.zhihu.com/equation?tex=%5Cmin_%7Bw%2C+b%7D+L%28w%2C+b%29+%3D+-+%5Csum_%7Bxi+%5Cin+M%7D+y_i%28w+%5Cbullet+x_i+%2B+b%29+%5Cspace%5Cspace%5Cspace%5Cspace%5Cspace+%282.5%29
其中M为误分类点的集合。
1) 感知机学习算法是正确分类驱动的么？
不是。感知机学习算法是误分类驱动的。具体采用随机梯度下降法。
首先，任意选取一个超平面，然后用梯度下降法不断地极小化目标函数(2.5)。极小化过程中不是一次使M中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。
2) 损失函数的梯度怎么取？
假设误分类点集合M是固定的，那么损失函数L(w, b)的梯度由
https://www.zhihu.com/equation?tex=%5Cspace%5Cspace%5Cspace%5Cspace%5Cspace+%5Cbigtriangledown_w+L%28w%2C+b%29+%3D+-+%5Csum_%7Bx_i+%5Cin+M%7D+y_i+x_i
https://www.zhihu.com/equation?tex=%5Cspace%5Cspace%5Cspace%5Cspace%5Cspace+%5Cbigtriangledown_b+L%28w%2C+b%29+%3D+-+%5Csum_%7Bx_i+%5Cin+M%7D+y_i
给出。
随机选取一个误分类点 https://www.zhihu.com/equation?tex=%28x_i+%2C+y_i%29 ，对w, b进行更新：
https://www.zhihu.com/equation?tex=%5Cspace%5Cspace%5Cspace%5Cspace%5Cspace+w+%3C-+w+%2B+%5Ceta+y_i+x_i+%5Cspace%5Cspace%5Cspace%5Cspace%5Cspace%282.6%29
https://www.zhihu.com/equation?tex=%5Cspace%5Cspace%5Cspace%5Cspace%5Cspace+b+%3C-+b+%2B+%5Ceta+y_i+%5Cspace%5Cspace%5Cspace%5Cspace%5Cspace+%282.7%29
式中是步长，在统计学习中又称为学习率(learning rate)。这样，通过迭代可以期待损失函数L(w, b)不断减小，直到为0。
3) 梯度下降算法的原始形式是什么？
算法 2.1 (感知机学习算法的原始形式)
输入： 训练数据集 https://www.zhihu.com/equation?tex=T+%3D+%5C%7B%28x_1%2C+y_1%29%2C+%28x_2%2C+y_2%29%2C...%2C%28x_N%2C+y_N%29+%5C%7D%2C%E5%85%B6%E4%B8%ADx_i+%5Cin+X+%3D+R%5E%7Bn%7D%2C+y_i+%5Cin+Y+%3D+%7B-1%2C+%2B1%7D%2C+%5Cspace+i+%3D+1%2C+2%2C...%2C+N%3B%5Cspace+%E5%AD%A6%E4%B9%A0%E7%8E%87+%5Ceta+%280+%3C+%5Ceta+%5Cleq+1%29%3B
输出： w, b; 感知机模型 https://www.zhihu.com/equation?tex=f%28x%29+%3D+sign%28w+%5Cbullet+x+%2B+b%29
(1) 选取初值
(2) 在训练集中选取数据
(3) 如果 https://www.zhihu.com/equation?tex=y_i+%28w+%5Cbullet+x_i+%2B+b%29+%5Cleq+0
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+w+%3C-+w+%2B+%5Ceta+y_i+x_i+
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+b+%3C-+b+%2B+%5Ceta+y_i
(4) 转至(2),直至训练集中没有误分类点。
这种学习算法直观上有如下解释： 当一个实例点被误分类，及位于分离超平面的错误一侧时，则调整w, b的值，使分离超平面向该误分类点的一侧移动，以减少该误分类点与超平面的距离，直至超平面越过该误分类点使其被正确分类。
算法2.1 是感知机学习的基本算法，对应于后面的对偶形式，成为原始形式，感知机学习算法简单且易于实现。
4) 例举一个感知机算法的例子
例2.1 如图2.2所示的训练数据集，其正实例点是 https://www.zhihu.com/equation?tex=x_1+%3D+%283%2C+3%29%5E+T%2C+%5Cspace+x_2+%3D+%284%2C+3%29%5ET%2C 负实例点是 https://www.zhihu.com/equation?tex=x_3+%3D+%281%2C+1%29%5ET%2C 试用感知机学习算法的原始形式求感知机模型 https://www.zhihu.com/equation?tex=f%28x%29+%3D+sign%28w+%5Cbullet+x+%2B+b%29. 这里， https://www.zhihu.com/equation?tex=w+%3D+%28w%5E%7B%281%29%7D%2C+w%5E%7B%282%29%7D%29%5ET%2C+%5Cspace+x+%3D+%28x%5E%7B%281%29%7D%2C+x%5E%7B%282%29%7D%29%5ET.
解构建最优化问题：
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cmin_%7Bw%2C+b%7D+L%28w%2C+b%29+%3D+-+%5Csum_%7Bx_i+%5Cin+M%7D+y_i%28w+%5Cbullet+x+%2B+b%29
按照算法2.1求解w, b ,.
(1) 取初值 https://www.zhihu.com/equation?tex=w_0+%3D+0%2C+%5Cquad+b_0+%3D+0+
(2) 对 https://www.zhihu.com/equation?tex=x_1+%3D+%283%2C+3%29%5ET%2C+%5Cspace+y_1%28w_0+%5Cbullet+x_1+%2B+b_0%29+%3D+0%2C 未能被正确分类，更新w, b
https://www.zhihu.com/equation?tex=%5Cqquad+w_1+%3D+w_0+%2B+y_1x_1+%3D+%283%2C+3%29%5ET%2C%5Cspace+b_1+%3D+b_0+%2B+y_1+%3D+1
得到线性模型
https://www.zhihu.com/equation?tex=%5Cqquad+w_1+%5Cbullet+x+%2B+b_1+%3D+3x%5E%7B%281%29%7D+%2B+3x%5E%7B%282%29%7D+%2B+1
(3) 对于 https://www.zhihu.com/equation?tex=x_1%2C+x_2%EF%BC%8C 显然， https://www.zhihu.com/equation?tex=y_1%28w_1+%5Cbullet+x_1+%2B+b_1%29+%3E+0%2C 被正确分类，不修改w, b;
对 https://www.zhihu.com/equation?tex=x_3+%3D+%281%2C+1%29%5ET%2C+y_3%28w_1+%5Cbullet+x_3+%2B+b_1%29+%3C+0%2C%E8%A2%AB%E8%AF%AF%E5%88%86%E7%B1%BB%EF%BC%8C%E6%9B%B4%E6%96%B0w%2C+b .
https://www.zhihu.com/equation?tex=%5Cqquad+w_2+%3D+w_1+%2B+y_3x_3+%3D+%282%2C+2%29%5ET%2C+%5Cspace+b_2+%3D+b_1+%2B+y_3+%3D+0
得到线性模型
https://www.zhihu.com/equation?tex=%5Cqquad+w_2+%5Cbullet+x+%2B+b_2+%3D+2x%5E%7B%281%29%7D+%2B+2x%5E%7B%282%29%7D
如此继续下去，直到
https://www.zhihu.com/equation?tex=%5Cqquad+w_7%3D%281%2C+1%29%5ET%2C+%5Cspace+b_7+%3D+-3+
https://www.zhihu.com/equation?tex=%5Cqquad+w_7+%5Cbullet+x+%2B+b_7+%3D+x%5E%7B%281%29%7D+%2B+x%5E%7B%282%29%7D+-3
对所有数据点 https://www.zhihu.com/equation?tex=y_i%28w_7+%5Cbullet+x_i+%2B+b_7%29+%3E+0%2C 没有误分类点，损失函数达到极小。
分离超平面为 https://www.zhihu.com/equation?tex=x%5E%7B%281%29%7D+%2B+x%5E%7B%282%29%7D+-3+%3D+0
感知机模型为 https://www.zhihu.com/equation?tex=f%28x%29+%3D+sign%28x%5E%7B%281%29%7D+%2B+x%5E%7B%282%29%7D+-3%29
迭代过程见表2.1
这是在计算中误分类点先后取 https://www.zhihu.com/equation?tex=x_1%2C+x_3%2C+x_3%2C+x_3%2C+x_1%2C+x_3%2C+x_3 得到的分离超平面和感知机模型。如果在计算中误分类点依次取 https://www.zhihu.com/equation?tex=x_1%2C+x_3%2C+x_3%2C+x_3%2C+x_2%2C+x_3%2C+x_3%2C+x_3%2C+x_1%2C+x_3%2C+x_3%2C 那么得到的分离超平面是 https://www.zhihu.com/equation?tex=2x%5E%7B%281%29%7D+%2B+x%5E%7B%282%29%7D+-5+%3D0 。
5) 感知机学习算法的初值和解有什么规律？
感知机学习算法由于采用不同的初值或选取不同的误分类点，解可以不同。
2.3.2 算法的收敛性
1) 感知机算法原始形式收敛么？
对于线性可分数据集，感知机学习算法原始形式收敛，即经过有限次迭代可以得到一个将训练数据集完全正确划分的分离超平面及感知机模型。
2) 证明感知机原始形式的收敛性
为了便于叙述 与推到，将偏置b并入权重向量w，记作 https://www.zhihu.com/equation?tex=%5Chat+w+%3D+%28w%5ET%2C+b%29%5ET ，同样也将输入向量加以扩充，加进常数1，记作 https://www.zhihu.com/equation?tex=%5Chat+x+%3D+%28x%5ET%2C+1%29%5ET. 这样， https://www.zhihu.com/equation?tex=%5Chat+x+%5Cin+R%5E%7B%28n%2B1%29%7D%2C+%5Cspace+%5Chat+w+%5Cin+R%5E%7B%28n%2B1%29%7D ,显然， https://www.zhihu.com/equation?tex=%5Chat+w+%5Cbullet+%5Chat+x+%3D+w+%5Cbullet+x+%2B+b.
定理 2.1(Novikoff)设训练数据集 https://www.zhihu.com/equation?tex=T+%3D%5C%7B+%28x_1%2C+y_1%29%2C+%28x_2%2C+y_2%29%2C...%2C+%28x_N%2C+y_N%29+%5C%7D%E6%98%AF%E7%BA%BF%E6%80%A7%E5%8F%AF%E5%88%86%E7%9A%84%EF%BC%8C+%E5%85%B6%E4%B8%ADx_i+%5Cin+X+%3D+R%5E%7Bn%7D%2C+y_i+%5Cin+Y+%3D+%7B-1%2C+%2B1%7D%2C+%5Cspace+i+%3D+1%2C+2%2C...%2CN%2C
则
(1) 存在满足条件 https://www.zhihu.com/equation?tex=%7C%7C%5Chat+w_%7Bopt%7D%7C%7C+%3D+1 的超平面 https://www.zhihu.com/equation?tex=%5Chat+w_%7Bopt%7D+%5Cbullet+%5Chat+x+%3D+w_%7Bopt%7D+%5Cbullet+x+%2B+b_%7Bopt%7D+%3D+0 将训练数据集完全分开；且存在 https://www.zhihu.com/equation?tex=%5Cgamma+%3E0%2C%E5%AF%B9%E6%89%80%E6%9C%89i+%3D+1%2C+2%2C...%2C+N
https://www.zhihu.com/equation?tex=%5Cqquad+y_i%28%5Chat+w_%7Bopt%7D+%5Cbullet+%5Chat+x_i%29+%3D+y_i%28w_%7Bopt%7D+%5Cbullet+x_i+%2B+b_%7Bopt%7D+%29+%5Cgeq+%5Cgamma+%5Cqquad+%282.8%29
(2) 令 https://www.zhihu.com/equation?tex=R+%3D+%5Cmax_%7B1+%5Cleq+i+%5Cleq+N%7D+%7C%7C%5Chat+x_i%7C%7C%2C 则感知机算法2.1在训训练数据集上的误分类次数k 满足不等式
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+%5Cqquad+k+%5Cleq+%5Cbigg%28+%5Cfrac%7BR%7D%7B%5Cgamma%7D+%5Cbigg%29%5E2+%5Cqquad%282.9%29
证明 (1) 由于训练数据集是线性可分的，按照定义2.2存在超平面将训练数据集完全正确分开，取次超平面为 https://www.zhihu.com/equation?tex=%5Chat+w_%7Bopt%7D+%5Cbullet+%5Chat+x+%3D+w_%7Bopt%7D+%5Cbullet+x+%2B+b_%7Bopt%7D+%3D+0%2C%E4%BD%BF%7C%7C%5Chat+w_%7Bopt%7D%7C%7C+%3D+1。由于对有限的 https://www.zhihu.com/equation?tex=i+%3D+1%2C2%2C...N%2C 均有
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+y_i%28%5Chat+w_%7Bopt%7D+%5Cbullet+%5Chat+x_i%29+%3D+y_i%28w_%7Bopt%7D+%5Cbullet+x_i+%2B+b_%7Bopt%7D%29+%3E+0
所以存在
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+%5Cgamma+%3D+%5Cmin_i+%5C%7By_i+%28w_%7Bopt%7D+%5Cbullet+x_i+%2B+b_%7Bopt%7D%29%5C%7D
使
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+y_i%28%5Chat+w_%7Bopt%7D+%5Cbullet+%5Chat+x_i%29+%3D+y_i%28w_%7Bopt%7D+%5Cbullet+x_i+%2B+b_%7Bopt%7D%29+%5Cgeq+%5Cgamma
(2) 感知机算法从 https://www.zhihu.com/equation?tex=%5Chat+w_0+%3D+0 开始，如果实例被误分类，则更新权重。令 https://www.zhihu.com/equation?tex=%5Chat+w_%7Bk-1%7D 是第k个误分类实例之前的扩充权重向量，即
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+%5Chat+w_%7Bk-1%7D+%3D+%28w_%7Bk-1%7D%5ET%2C+b_%7Bk-1%7D%29%5ET+
则第k个误分类实例的条件是
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+y_i%28%5Chat+w_%7Bk-1%7D%2C+%5Chat+x_i%29+%3D+y_i%28w_%7Bk-1%7D+%5Cbullet+x_i+%2B+b_%7Bk-1%7D%29+%5Cleq+0+%5Cqquad+%282.10%29
若 https://www.zhihu.com/equation?tex=%28x_i%2C+y_i%29%E6%98%AF%E8%A2%AB%5Chat+w_%7Bk-1%7D+%3D+%28w_%7Bk-1%7D%5ET%2C+b_%7Bk-1%7D%29%5ET 误分类的数据，则w 和b的更新是
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+w_k+%5Cleftarrow+%5Cspace+w_%7Bk-1%7D+%2B+%5Ceta+y_i+x_i
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+b_k+%5Cleftarrow+%5Cspace+b_%7Bk-1%7D+%2B+%5Ceta+y_i
即
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+%5Chat+w_%7Bk%7D+%3D+%5Chat+w_%7Bk-1%7D+%2B+%5Ceta+y_i+%5Chat+x_i+%5Cqquad+%282.11%29
下面推导两个不等式：
(1) https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+%5Chat+w_k+%5Cbullet+%5Chat+w_%7Bopt%7D+%5Cgeq+k+%5Ceta+%5Cgamma+%5Cqquad+%282.12%29
由式(2.11)及式(2.8)得
https://www.zhihu.com/equation?tex=%5Chat+w_k+%5Cbullet+%5Chat+w_%7Bopt%7D+%3D+%5Chat+w_%7Bk-1%7D+%5Cbullet+%5Chat+w_%7Bopt%7D+%2B+%5Ceta+y_i+%5Chat+w_%7Bopt%7D+%5Cbullet+%5Chat+x_i+%5Cgeq+%5Chat+w_%7Bk-1%7D+%5Cbullet+%5Chat+w_%7Bopt%7D+%2B+%5Ceta%5Cgamma
由此递推即得不等式(2.12)
https://www.zhihu.com/equation?tex=%5Chat+w_k+%5Cbullet+%5Chat+w_%7Bopt%7D+%5Cgeq+%5Chat+w_%7Bk-1%7D+%5Cbullet+%5Chat+w_%7Bopt%7D+%2B+%5Ceta%5Cgamma+%5Cgeq+%5Chat+w_%7Bk-2%7D+%5Cbullet+%5Chat+w_%7Bopt%7D+%2B+2%5Ceta%5Cgamma+%5Cgeq+...+%5Cgeq+k%5Ceta%5Cgamma
(2)
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+%7C%7C%5Chat+w_k%7C%7C%5E2+%5Cleq+k+%5Ceta%5E2+R%5E2+%5Cqquad%5Cqquad+%282.13%29
由式(2.11)及(2.10)得
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+%7C%7C%5Chat+w_k%7C%7C%5E2+%3D+%7C%7C%5Chat+w_%7Bk-1%7D%7C%7C%5E2+%2B+2%5Ceta+y_i+%5Chat+w_%7Bk-1%7D+%5Cbullet+%5Chat+x_i+%2B+%5Ceta%5E2+%7C%7C%5Chat+x_i%7C%7C%5E2+
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+%5Cqquad+%5Cleq+%7C%7C%5Chat+w_%7Bk-1%7D%7C%7C%5E2+%2B+%5Ceta%5E2+%7C%7C%5Chat+x_i%7C%7C%5E2
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+%5Cqquad+%5Cleq+%7C%7C%5Chat+w_%7Bk-1%7D%7C%7C%5E2+%2B+%5Ceta%5E2+R%5E2
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+%5Cqquad+%5Cleq+%7C%7C%5Chat+w_%7Bk-2%7D%7C%7C%5E2+%2B+2%5Ceta%5E2R%5E2+%5Cleq+...
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+%5Cqquad+%5Cleq+k+%5Ceta%5E2+R%5E2
结合不等式(2.12)及式(2.13)即得
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+k%5Ceta%5Cgamma+%5Cleq+%5Chat+w_k+%5Cbullet+%5Chat+w_%7Bopt%7D+%5Cleq+%7C%7C%5Chat+w_k%7C%7C%5Cspace%7C%7C%5Chat+w_%7Bopt%7D%7C%7C+%5Cleq+%5Csqrt+k+%5Ceta+R
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+k%5E2+%5Cgamma%5E2+%5Cleq+k+R%5E2
于是 https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+%5Cqquad+k+%5Cleq+%5Cbigg+%28%5Cfrac%7BR%7D%7B%5Cgamma%7D+%5Cbigg+%29%5E2
定理表明，误分类的次数k是有上界的，经过有限次搜索可以找到将训练数据完全分开的分离超平面，也就是说，当训练数据集线性可分时，感知机学习算法原始形式迭代是收敛的。
不过例2.1说明，感知机学习算法存在很多解，而为了得到唯一的超平面，需要对分离超平面增加约束条件，这就是之后会讲解的线性支持向量机的想法，当训练集线性不可分时，感知机学习算法不收敛，迭代结果会发生震荡。
2.3.3 感知机学习算法的对偶形式
1) 什么是感知机学习算法的对偶形式？
对偶形式的基本想法是，将w 和 b表示为实例 https://www.zhihu.com/equation?tex=x_i%E5%92%8C%E6%A0%87%E8%AE%B0y_i 的线性组合的形式，通过求解其系数而求得 w 和 b 。
在算法2.1中可假设初始值均为0，对误分类点通过
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+%5Cqquad+w+%5Cleftarrow+w+%2B+%5Ceta+y_i+x_i
逐步修改w 和 b，设修改n 次，则w , b 关于的增量分别是 https://www.zhihu.com/equation?tex=%5Calpha_i+y_i+x_i%E5%92%8C%5Calpha_i+y_i ，这里 https://www.zhihu.com/equation?tex=%5Calpha_i+%3D+n_i+%5Ceta 。这样，从学习过程不难看出，最后学习到的w , b 可以分别表示为
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+%5Cqquad+w+%3D+%5Csum_%7Bi%3D1%7D%5E%7BN%7D+%5Calpha+y_i+x_i+%5Cqquad+%5Cqquad+%282.14%29
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+%5Cqquad+b+%3D+%5Csum_%7Bi%3D1%7D%5E%7BN%7D+%5Calpha_i+y_i+%5Cqquad+%5Cqquad+%282.15%29+
这里， https://www.zhihu.com/equation?tex=%5Calpha_i+%5Cgeq+0%2C%5Cspace+i+%3D+1%2C2%2C...%2CN%2C 当时，表示第 https://www.zhihu.com/equation?tex=i 个实例点由于误分而进行更新的次数，实例点更新次数越多，意味着它距离分离超平面越近，也就越难正确分类。换句话说，这样的实例对学习结果影响最大。
2) 请对照原始形式来叙述对偶形式
算法 2.2 (感知机学习算法的对偶形式)
输入：线性可分的数据集 https://www.zhihu.com/equation?tex=T+%3D+%5C%7B+%28x_1%2C+y_1%29%2C+%28x_2%2C+y_2%29%2C...%2C%28x_N%2C+y_N%29%5C%7D%2C+%E5%85%B6%E4%B8%ADx_i+%5Cin+R%2C%5Cspace+y_i+%5Cin+%5C%7B-1%2C+%2B1%5C%7D%2C+%5Cspace+i+%3D+1%2C2%2C...%2CN%3B 学习率;
输出： https://www.zhihu.com/equation?tex=%5Calpha%2C+b%3B 感知机模型 https://www.zhihu.com/equation?tex=f%28x%29+%3D+sign%5Cbigg%28%5Csum_%7Bj+%3D+1%7D%5E%7BN%7D+%5Calpha_j+y_j+x_j+%5Cbullet+x+%2B+b%5Cbigg%29
其中 https://www.zhihu.com/equation?tex=%5Calpha+%3D+%28%5Calpha_1%2C+%5Calpha_2%2C...%2C%5Calpha_N%29%5ET.
(1) https://www.zhihu.com/equation?tex=%5Calpha+%5Cleftarrow+0%2C+b+%5Cleftarrow+0
(2) 在训练集中选取数据
(3) 如果 https://www.zhihu.com/equation?tex=y_i+%5Cbigg%28%5Csum_%7Bj%3D1%7D%5E%7BN%7D+%5Calpha_j+y_j+x_j+%5Cbullet+x_i+%2B+b+%5Cbigg%29+%5Cleq+0
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+%5Cqquad+%5Calpha_i+%5Cleftarrow+%5Calpha_i+%2B+%5Ceta
(4) 转至(2)直到没有误分类数据。
对偶形式中训练实例仅以内积的形式出现，为了方便，可以预先将训练集中实例间的内积计算出来并以矩阵形式存储，这个矩阵就是所谓的Gram矩阵(Gram matrix)
https://www.zhihu.com/equation?tex=%5Cqquad+%5Cqquad+%5Cqquad+G+%3D+%5Bx_i+%5Cbullet+x_j%5D_%7BM+%5Ctimes+N%7D emmmmmm简单总结+copy了一下统计学习方法的内容 对偶形式的基本想法是，将w 和 b表示为实例的线性组合的形式。此处我个人理解成w=Axi+Byi这种形式，但下文中w=alpha×yi×xi，求解答！ 此处损失函数，最好加上个max(0, -yi(w*xi+b))，不然当选择到一个样本，将其正确分类后，原有的损失函数会小于0 的确是这样 2333 你好，想问下loss函数为什么将1/||w||拿掉 损失函数存在的作用对象是误分类的点。有了1/||w||、没有1/||w||，只要数据集线性可分（前提条件），那么loss的值最终都会收敛到0，因此拿掉也没关系。此外，重要的一点是感知机没有要求最终得到的线性模型唯一，只要最终loss为0即可。如果要求唯一的话，参考SVM的间隔最大化思想。 谢谢了[微笑] 站在李航老师的肩膀上，更加简洁清晰
[欢呼] 请问，这个上界与学习率无关了，难道学习率再小学习次数也不会超过此上界吗，怎么理解这一点？
页:
[1]
2