Data-Method-05Perceptron在我看来，学术生活中的普遍自由是其最重要的特征之一。长假非常有吸引力，工作时间的自由感也是如此。-ClaudeShannon数据系列：目录|配置|代码仓库|作为神经网络和支持向量机的基础，感知器可以说已经占据了人工智能领域数十年。虽然现在很多书上更多的是从神经网络的角度来解释感知器，并且把它放在神经网络的章节里面。但是作为一个单独就能快速开启一章的方法，我又怎么舍得放到其他内容中去呢？的线性分类模型是一种判别模型。感知器可以说是最简单的人工神经网络，只有一个神经元。输入：实例的特征向量$x$，输入空间为$\mathcal{X}\subseteq{\rmR}^n$输出：实例的类别$y$，输出空间为$\mathcal{Y}=\{+1,-1\}$任务：找出线性划分训练数据的分离超平面（separatinghyperplane），求出输入空间到输出空间的函数，$f(x)={\rmsign}(w\cdotx+b)$$w$：权重（weight），从神经元的角度看是突触$b$：偏差（bias），从神经元的角度看是相反的数量threshold（阈值）$f$：激活函数（activationfunction），从一个神经元的角度看就是细胞体${\rmsign}$function：符号函数，也可以写成${\rmsgn}$$${\rmsign(x)}=\begin{cases}+1,\quad&x\ge0\\-1,&x<0\end{cases}$$分离超平面图示（来自《统计学习方法》）：2.感知器学习【学习策略-损失函数】感知器学习目标：找到一个完全正确分离的分离超平面训练集的正负实例点。学习策略：定义（经验）损失函数并最小化损失函数。损失函数自然选择的是误分类点总数，但是由于这不是参数$w$和$b$的连续可导函数，不好优化，所以没得选。感知器学习策略实际选择的是误分类点到超平面$S$的总距离。任意点$x_0$到超平面的距离为：$\frac{1}{||w||}|w\cdotx_0+b|$，$||w||$表示L2范数误分类数据$(x_i,y_i)$有：$y_i(w\cdotx_i+b)<0$设误分类集为$M$，则总距离为：$-\frac{1}{||w||}y_i(w\cdotx_i+b)$不管$\frac{1}{||w||}$，感知机学习到的损失函数（经验风险函数）为：$L(w,b)=-\sum_{x_i\inM}y_i(w\cdotx_i+b)$为$w$，$b$的连续可导函数感知器学习在假设空间$\{f|f(x)=w\cdot在x+b\}$中，选择最小化损失函数$L(w,b)$的模型参数$w,b$，即求解损失函数的优化问题，采用的方法是stochastic梯度下降法（stochasticgradientdescent）。[学习算法-原始形式]感知器学习算法是误分类驱动、错误驱动，并使用随机梯度下降进行优化。简单点说，先随机选择一个超平面$w_0,b_0$，然后每次随机选择一个误分类的点，通过梯度下降法最小化目标函数。感知器学习算法的原始形式：输入：训练数据集$T=\{(x_1,y_1),(x_2,y_2)...,(x_N,y_N)\}$，其中$x_i\in\mathcal{X}\subseteq{\rmR}^n$,$y_i\in\mathcal{Y}=\{+1,-1\}$学习率（learningrate）/步长$\eta$($0<\eta\le1$)output:$w,b$,感知机模型$f(x)={\rmsign}(w\cdotx+b)$算法步骤：选择初始值$w_0,b_0$；在训练集中选择数据$(x_i,y_i)$；如果是误分类点，即$y_i(w\cdotx_i+b)\le0$,$$\begin{aligned}&w\leftarroww+\etay_ix_i\\&b\leftarrowb+\etay_i\end{对齐}$$到2步，直到没有误分类点。因为感知器学习算法采用不同的初始值或者选择不同的误分类点，所以解可以不同。【学习算法-对偶形式】对偶形式的基本思想是将$w$和$b$表示为实例$x_i$和标签$y_i$的线性组合形式，得到$w$和$通过求解其系数b$。对偶形式的构建：在原始形式下，将$w_0$和$b_0$的初始值设为0，对误分类点$(x_i,y_i)$进行随机梯度下降，逐步修改$w$和$b$；假设修改$n$，$w$和$b$在$(x_i,y_i)$上的增量分别为$\alpha_iy_ix_i$和$\alpha_iy_i$，即$\alpha_i=n_i\eta$；最后学习到的$w,b$可以表示为：$$\begin{aligned}&w=\sum^N_{i=1}\alpha_iy_ix_i\\&b=\sum^N_{i=1}\alpha_iy_i\end{aligned}$$感知器学习算法的对偶形式：输入：训练数据集$T=\{(x_1,y_1),(x_2,y_2)...,(x_N,y_N)\}$，其中$x_i\in\mathcal{X}\subseteq{\rmR}^n$,$y_i\in\mathcal{Y}=\{+1,-1\}$学习率（learningrate）/步长$\eta$($0<\eta\le1$)输出：$\alpha,b$,感知器模型$f(x)={\rmsign}(\sum^N_{j=1}\alpha_jy_jx_j\cdotx+b)$,其中$\alpha=(\alpha_1,\alpha_2,...,\alpha_N)^T$算法步骤：$\alpha\leftarrow0$,$b\leftarrow0$;在训练集中选择数据$(x_i,y_i)$；如果是误分类点，即$(\sum^N_{j=1}\alpha_jy_jx_j\cdotx_i+b)\le0$,$$\begin{aligned}&\alpha_i\leftarrow\alpha_i+\eta\\&b\leftarrowb+\etay_i\end{aligned}$$到2步，直到没有误分类点。在对偶形式中，训练样例只以内积$x_ix_j$的形式出现，所以可以提前得到内积，并以矩阵的形式存储。这个矩阵就是所谓的Gram矩阵：$\textbf{G}=[x_i\cdotx_j]_{N\timesN}$。与原始形式一样，感知器学习算法的对偶形式也有多个解。两种形式的计算示例请参考《统计学习方法》中的示例。3.感知器学习的评价【线性可分性和收敛性】对于一个数据集$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$，如果有一个超平面$S$：$w\cdotx+b=0$可以完全正确地将正负实例点划分到超平面的两边，即对于所有$y_i=+1$实例$i$，有$w\cdotx_i+b>0$；对于$y_i=-1$的所有实例$i$，有$w\cdotx_i+b<0$。则称数据集$T$为线性可分数据集（linearlyseparabledataset），否则称为线性不可分。当数据集线性可分时，感知器学习算法的原始形式和对偶形式迭代均收敛；而当训练集线性不可分时，感知机学习算法不收敛，迭代结果会出现波动（fluctuation）（推导过程在《统计学习方法》中给出，证明了对于线性可分的数据集，迭代次数感知器学习有一个上限）。【感知机与神经元】从神经网络的角度来看，感知机由两层神经元组成。详情请参考《机器学习》中神经网络部分，或后续博客。【感知机的扩展】感知机的扩展学习包括pocketalgorithm、votedperceptron、preceptronwithmargin等，现在看来感知机的方法很简单，在很多书里神经网络章节只是一小部分，但是它使用了一个连续可导的损失函数来进行梯度下降更新权重，对偶形式提升等，确实，看起来还是那么精致。
