概述
感知机（perceptron）是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别。
感知机对应于输入空间中将实例划分为正负两类的分离超平面，属于判别模型。
2.1 感知机模型
定义：
感知机是一种线性分类模型，属于判别模型。假设空间是定义在特征空间中所有线性分类模型，即函数集合
感知机的几何解释：
2.2 感知机学习策略
2.2.1 数据集的线性可分性
线性可分：存在某个超平面能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧。
2.2.2 感知机学习策略
学习目标：求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面S
损失函数：误分类点到超平面S的总距离
给定训练数据集
2.3 感知机学习算法
感知机学习问题转化为求解损失函数的最优化问题，最优化的方法是随机梯度下降法。
2.3.1 感知机学习算法的原始形式
感知机学习算法是误分类驱动的，具体采用随机梯度下降法。首先任一选取一个超平面
由此得到感知机算法的原始形式：
2.3.2 算法的收敛性
需要证明：对于线性可分数据集，感知机学习算法原始形式收敛，即经过有限次迭代可以得到一个将训练数据集完全正确划分的分离超平面及感知机模型。（Novikoff定理）
证明略过。
该定理表明，误分类的次数k是有上界的，经过有限次搜索可以找到将训练数据完全正确分开的分离超平面。并且该超平面不唯一，依赖于初值的选择和迭代过程中误分类点的选择顺序。若要找到唯一的超平面，需要对分离超平面增加约束条件（SVM)。
2.3.3 感知机学习算法的对偶形式
对偶形式的基本想法是：将和
表示为实例
和标记
的线性组合的形式，通过求解其系数而求得
和
。
由此得到感知机学习算法的对偶形式：
对偶形式中训练实例仅以内积的形式出现，为了方便，可以预先将训练集中实例间的内积计算出来并以矩阵的形式存储，这个矩阵就是所谓的Gram矩阵(Gram matrix)。
Gram矩阵
本章概要
1．感知机是根据输入实例的特征向量对其进行二类分类的线性分类模型：
感知机模型对应于输入空间（特征空间）中的分离超平面。
2．感知机学习的策略是极小化损失函数：
损失函数对应于误分类点到分离超平面的总距离。
3．感知机学习算法是基于随机梯度下降法的对损失函数的最优化算法，有原始形式和对偶形式。算法简单且易于实现。原始形式中，首先任意选取一个超平面，然后用梯度下降法不断极小化目标函数。在这个过程中一次随机选取一个误分类点使其梯度下降。
4．当训练数据集线性可分时，感知机学习算法是收敛的。感知机算法在训练数据集上的误分类次数满足不等式：
当训练数据集线性可分时，感知机学习算法存在无穷多个解，其解由于不同的初值或不同的迭代顺序而可能有所不同。
网友评论