【感知机】感知机(perceptron)学习算法的对偶形式

感知机( perceptron )是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1 和-1二值。感知机对应输入空间(特征空间)中将实例划分为正负两类的分离超平面，是一种判别模型。感知机是神经网络与支持向量机的基础

感知机学习旨在求出将训练数据进行线性划分的分离超平面。

感知机学习思路：

1.导入基于误分类的损失函数

2.利用梯度下降法对损失函数进行极小化

3.代入参数得到感知机模型。

感知机学习算法分类：

原始形式、对偶形式。

感知机学习算法的对偶形式

感知机学习算法的原始形式和对偶形式与支特向量机学习算法的原始形式和对偶形式相对应

输入：训练数据集 $T=\left \{ (x_1,y_1),(x_2,y_2),...,(x_N,y_N)\right \}$ ,其中 $x_i\in\mathbb{R}^{n}$ , $y_i\in\left \{ +1,-1 \right \}$ ,学习率 $\eta \left ( 0<\eta \leq 1 \right )$

1. $\alpha \leftarrow 0,b\leftarrow 0$ 其中 $\alpha =(\alpha _1,\alpha _2,...,\alpha _n)^{T}$

2.任意顺序遍历 $i$ ，计算 $y_i (\sum_{j=1}^{N} \alpha _jy_jx_j\cdot x+ b)$ ，当 $y_i (\sum_{j=1}^{N} \alpha _jy_jx_j\cdot x+ b)\leq 0$ ，转到步骤3；若对任意 $i$ ， $y_i (w\cdot x_i+b )> 0$ ，转到输出

3. $\alpha_i\leftarrow \alpha_i+\eta$ , $b\leftarrow b+\eta y_i$ ，转到步骤2

输出： $\alpha ,b$ ；感知机 $f(x)=sign(\sum_{j=1}^{N} \alpha _jy_jx_j\cdot x+ b)$

对偶形式的基本想法：将 $w$ 和 $b$ 表示为实例 $x_i$ 和标记 $y_i$ 的线性组合的形式，通过求解其系数来求解 $w$ 和 $b$

基于原始形式，可设 $w_0=0,b_0=0$ ，则迭代n次后，设第 $I$ 个实例点由于误分而更新的次数为 $n_i$ ，令 $\alpha_i=n_i\eta$ ,有 $w=\sum_{i=1}^{N}\alpha_iy_ix_i$ , $b=\sum_{i=1}^{N}\alpha_iy_i$ 。

注意：实例点更新次数越多，意味着它离分离超平面越近，意味着越难分类。这样的实例点对于学习结果的影响最大。