机器学习方法都是由3个要素构成的:
- 模型:包含输入空间,输出空间和假设空间(包含所有可能的决策函数)
- 策略:按照什么样的准则选择最优的模型(损失函数)
- 算法:如何找到最优模型(最优化问题)
感知机模型
输入空间:
(n维实数)
输出空间:
假设空间:
注意:
都是向量,
也就是向量的内积,比如在二维空间中:
就是要找一个直线
将点分成两类(这条直线更一般的名称叫做超平面);另外感知机模型对数据的假设是:数据是线性可分的;比如下图所示的数据所对应的就不是一个线性可分的输入空间
学习策略
感知机的损失函数为:误分类点到超平面S的总距离,通过最小化这个距离得到最优的超平面(超平面的参数就是w和b)
首先我们需要一些基础知识:
超平面的法向量
对于一个超平面S (
),其法向量为
:
设超平面S上有两个点:A点
和B点
有:
因为
是超平面S上的一个向量,两个向量的乘积为0,所以
垂直于S,即
为超平面S的法向量
点到超平面的距离
输入空间中任一点
到超平面S (
)的距离d为:
设点
在S上投影为
,则
;由于向量
与S的法向量
平行,所以:
对于
又有(假设
和
都是N维的向量,上面的图只是一个3维的例子):
因此由上面两个式子,可以得出:
回到感知机模型中,因为误分类点
和类标签的符号是相反的(当
大于0时,误分类的类标签是-1;当
小于0时,误分类的类标签是+1),所以误分类点到超平面S的距离也可以表示为:
误分类点的总距离为:
所以感知机的损失函数为:
学习算法
可以使用梯度下降或者随机梯度下降的方法来求解使损失函数最小化时的参数
损失函数
的梯度为:
所以按照梯度下降法,对每个误分类点更新w,b:
是学习率;在实际应用中一般选择使用随机梯度下降:
感知机的学习算法(随机梯度下降法)的步骤为:
,按照上式对参数进行更新
算法收敛性
证明如下的定理:
设训练数据集
是线性可分的:
- 存在满足条件
=1的超平面
将数据集完全正确分开,且存在
,对所有的
有:
- 令
,则感知机在训练集上的误分类次数k满足不等式:
首先为了方便,将b放进了w和x中,也就是:
先证明1:
由于数据集是线性可分的,肯定存在一个超平面将数据集完全分开,即对
,都有:
因此只需要r为
的最小值,就会有:
再来看2:
也就是说误分类的次数是有上界的,经过有限次搜索肯定是可以找到将训练集完全分开的超平面
Sci-kit learn
scikit learn 中的Perceptron类和SGDClassifier类都可以进行感知机模型的计算:
from sklearn.datasets import load_digits
from sklearn.linear_model import Perceptron
X, y = load_digits(return_X_y=True)
clf = Perceptron(random_state=0)
##也可以使用SGDClassifier(loss="perceptron", eta0=1, learning_rate="constant", penalty=None)
clf.fit(X, y)
clf.score(X, y)
参考:李航《机器学习》