感知机（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中无误分类点

参考：

[1] 南开 - bilibili.com

[2] 算法——感知机详解（推导+证明） - Summer的文章 - 知乎

[3] 感知机收敛性(Novikoff定理证明)_herosunly的博客-CSDN博客_感知器收敛 wopt