感知机
学习笔记
-
感知机是二类分类的线性模型,属于判别模型
-
感知机学习旨在求出将训练数据进行线性划分的分离超平面.是神经网络和支持向量机的基础
-
损失函数选择
- 损失函数的一个自然选择是误分类点的总数,但是,这样的损失函数不是参数w,b的连续可导函数,不易优化
- 损失函数的另一个选择是误分类点到超平面S的总距离,这正是感知机所采用的
-
感知机学习的经验风险函数(损失函数)
L(w,b)=−xi∈M∑yi(w⋅xi+b)
其中M是误分类点的集合,给定训练数据集T,损失函数L(w,b)是w和b的连续可导函数
原始形式算法
输入:训练数据集T={(x1,y1),(x2,y2),…,(xN,yN)},xi∈Rn,yi∈{+1,−1},i=1,2,3,…,N;学习率0<η⩽1
输出:w,b;感知机模型f(x)=sign(w⋅x+b)
-
选取初值w0,b0
-
训练集中选取数据(xi,yi)
-
如果yi(w⋅xi+b)⩽0
w←w+ηyixib←b+ηyi
-
转至(2),直至训练集中没有误分类点
- 这个是原始形式中的迭代公式,可以对x补1,将w和b合并在一起,合在一起的这个叫做扩充权重向量
对偶形式算法
- 对偶形式的基本思想是将w和b表示为实例xi和标记yi的线性组合的形式,通过求解其系数而求得w和b。
输入:T={(x1,y1),(x2,y2),…,(xN,yN)},xi∈Rn,yi∈{+1,−1},i=1,2,3,…,N;学习率0<η⩽1
输出:
α,b;感知机模型f(x)=sign(∑j=1Nαjyjxj⋅x+b),α=(α1,α2,⋯,αN)T
-
α←0,b←0
-
训练集中选取数据(xi,yi)
-
如果yi(∑j=1Nαjyjxj⋅x+b)⩽0
αi←αi+ηb←b+ηyi
-
转至(2),直至训练集中没有误分类点
习题解答
- 2.1 Minsky 与 Papert 指出:感知机因为是线性模型,所以不能表示复杂的函数,如异或 (XOR)。验证感知机为什么不能表示异或。
- 我们显然无法使用一条直线将两类样本划分,异或问题是线性不可分的。
- 可以借助下面动图理解
- 2.2 模仿例题 2.1,构建从训练数据求解感知机模型的例子。
- 感知机的训练过程如上所述,取与原例题相同的数据,计算出不同的结果
- x = [3 3; 4 3; 1 1];
y = [1; 1; -1];
- 根据程序运行可得:
- eg1:
误分类点为: [3 3] 此时的w和b为: [[0.][0.]] 0
误分类点为: [1 1] 此时的w和b为: [[3.][3.]] 1
误分类点为: [1 1] 此时的w和b为: [[2.][2.]] 0
误分类点为: [1 1] 此时的w和b为: [[1.][1.]] -1
误分类点为: [3 3] 此时的w和b为: [[0.][0.]] -2
误分类点为: [1 1] 此时的w和b为: [[3.][3.]] -1
误分类点为: [1 1] 此时的w和b为: [[2. [2.]] -2
最终训练得到的w和b为: [[1.] [1.]] -3
即f(x)=sign(x(1)+x(2)−3)
- eg2:
误分类点为: [1 1] 此时的w和b为: [[0.] [0.]] 0
误分类点为: [4 3] 此时的w和b为: [[-1.] [-1.]] -1
误分类点为: [1 1] 此时的w和b为: [[3.] [2.]] 0
误分类点为: [1 1] 此时的w和b为: [[2.] [1.]] -1
最终训练得到的w和b为: [[1.] [0.]] -2
即f(x)=sign(x(1)−2)
感知机中的损失函数中的分母为什么可以不考虑?
-
感知机处理线性可分数据集,是二分类,所以涉及到的乘以yi的操作实际贡献的是符号;
-
损失函数 L(w,b)=−∑xi∈Myi(w⋅xi+b),其中 M 是错分的点集合,线性可分的数据集肯定能找到超平面 S, 所以这个损失函数最值是0。
-
如果正确分类, yi(w⋅xi+b)=∣w⋅xi+b∣ ,错误分类的话,为了保证正数就加个负号,这就是损失函数里面那个负号,这个就是函数间隔;
-
∣∣w∣∣1 用来归一化超平面法向量,得到几何间隔,也就是点到超平面的距离, 函数间隔和几何间隔的差异在于同一个超平面 (w,b) 参数等比例放大成 (kw,kb) 之后,虽然表示的同一个超平面,但是点到超平面的函数间隔也放大了,但是几何间隔是不变的;
-
具体算法实现的时候, w要初始化,然后每次迭代针对错分点进行调整,既然要初始化,那如果初始化个 ∣∣w∣∣=1 的情况也就不用纠结了,和不考虑 ∣∣w∣∣1 是一样的了;
Python实现感知机
用python实现例2.1的感知机模型学习