感知机（Perceptron）
一. 概念
1. 模型
感知机是二分类的线性分类模型，旨在求出将输入实例划分为两类的分离超平面，是神经网络与支持向量机的基础。
2. 组成
ω为法向量，b为截距，超平面分离两类
(1) 输入x：实例的特征向量（树突信号）
(2) 权重ω：在模拟训练期间计算的值，[ω1,...,ωn]
(3) 偏置b：偏执神经元允许分类器可移动决策边界，更快更好训练模型
(4) 输出y：实例的类别，y={+1,-1}
二. 学习策略
1. 原理
为求超平面S的参数ω、b，定义基于误分类的损失函数，用梯度下降法对损失函数进行优化。
(1) 误分类点：
①误分类点到超平面的距离之和：
②误分类点：
③误分类点距离：
④误分类点总距离： （min趋近于0）
(2) 损失函数： （n为误分类点个数）
关于
的省略：对正负判定无影响，若不忽略，每次都需要进行复杂的求导
(3)求解最优化问题： min Loss(ω,b)
随机梯度下降法：在每次迭代过程中，随机选取一个超平面，不断极小化目标函数Loss（参考拉格朗日乘子法）
① 对ω、b求偏导：
② 选取误分类点更新：
，η∈(0,1]为学习率，下降步长
2. 算法
(1) 输入：训练数据集 T={} ，学习率η∈(0,1]
输出：ω、b，得到感知机模型
(2) 流程：
① 初始化 ω、b
② 随机选取数据点
③ 若出现误分类点，即
则更新误分类点 ，
④ 转至②，直至训练集T中无误分类点
3.收敛性分析
(1) 定理一：经过有限次迭代，存在一个将线性可分的数据集划分的分离超平面。
(2) 定理二：对线性可分的数据，感知机算法迭代的次数（误分类数据点次数）有一个上界。
Novikoff定理证明：
表明：算法不稳定（存在多个平面），既依赖初值，也依赖迭代中对误分类点的选择顺序。
4. 对偶形式
(1) 将 ，
带入感知机原问题
(2) 对偶感知模型：
(3) 流程：
① 初始化 α、b
② 随机选取数据点
③ 若出现误分类点，即 （核函数，Gram矩阵）
则更新误分类点 、
③ 转至②，直至训练集T中无误分类点
参考：
