0%

统计学习方法(二)感知机

感知机,是二分类的线性分类模型。输入为实例的特征向量,输出为±1,旨在求出将训练数据进行线性划分的分离超平面,是神经网络与SVM的基础。

2.1 感知机模型

定义

其中w和b为感知机模型参数,w称为权值(向量),b称为偏置(bias)。

几何解释

线性方程

对应于特征空间中的一个超平面S,w表示超平面的法向量,b为超平面的截距。

2.2 感知机学习策略

数据集的线性可分性

给定一个数据集,如果存在超平面S,能够将数据集的正实例点和负实例点完全正确划分,则称数据及为线性可分数据集。

损失函数

损失函数的一个自然选择是误分类点的总数,但这样不是参数的连续可导函数,不易优化。

感知机选择的损失函数是误分类点到超平面S的总距离,输入空间任一点到超平面S的距离为

对于误分类的数据来说,始终有

所以距离为

假设误分类点集合为M,求和即得

不考虑系数,损失函数即为

误分类点越少,损失函数值越小,如果没有误分类点,损失函数值为0。

2.3 感知机学习算法

形式化

给定训练集

求参数w和b,使得损失函数极小化

学习算法是误分类驱动的,具体采用随机梯度下降法,首先任意选取一个超平面,之后用梯度下降法不断极小化目标函数。

损失函数的梯度为

随机选取一个误分类点,对参数进行更新

原始形式

  1. 选取参数初值

  2. 在训练集中选取数据

  3. 如果,则更新参数

  4. 转至2直至没有误分类点

收敛性

(Novikoff) 存在满足条件的超平面,且感知机算法的误分类次数k满足不等式

对偶形式

基本想法是,将w和b表示为实例x与标记y的线性组合,通过求解系数求得w和b。

最后学习到的w和b可表示为

训练过程

  1. 选取α和b为0,

  2. 在训练集中选取数据

  3. ,则更新参数

  1. 转至2直至没有误分类数据

Gram矩阵?

Scikit-learn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from sklearn.linear_model import Perceptron

clf = Perceptron(fit_intercept=True,
max_iter=1000,
shuffle=True)
clf.fit(X, y)

# Weights assigned to the features.
print(clf.coef_)

# Constants in decision function.
print(clf.intercept_)

y_ = -(clf.coef_[0][0]*x_ponits + clf.intercept_)/clf.coef_[0][1]
plt.plot(x_ponits, y_)
plt.plot(x_ponits, y_)