感知器学习笔记

最近杨老师课上又学了一遍感知器。。唔，算做个总结吧。 时间仓促，难免有疏漏，望各位指正!(email: vast2stars@gmail.com)

基本

感知器函数定义：

$$f(x)=sign(w\cdot x+b)$$

其中$w$ 和$b$ 为感知器模型参数，分别为权值和阈值。在特征空间$R^n$ 中，$w$ 是感知器决策超平面的法向量（恒指向正类$^{[1]}$），$b$ 是超平面的截距。$f(x)$ 输出$+1,-1$ 。

记感知器学习策略的损失函数为$L(w,b)$。 该函数不能定义成误分类点的数量，因为此时$L$ 不是关于$w,b$ 的连续可到函数$^{[2]}$，不易优化。通常采用所有误分类点(集合M)到超平面的距离总和作为损失函数。推导过程如下：

任意点到超平面的距离为：

$$\begin{equation} \frac{|w\cdot x_i+b|}{||w||} \end{equation} \tag{1}$$

消除误分类点的符号差异性： 式(1)分子含有绝对值，不利于求微分进行优化。如果删去绝对值，那么假阴性(false negative, FN)样本的计算值为负，而假阳性(false positive, FP)为正，错误相互抵消而非累加。为了解决该问题，使用$-y_i(w\cdot x_i+b)/||w||$ 作为修正后的距离（不论FN还是FP，该函数值恒为正）。

删去$1/||w||$ $^{[3]}$ 并累积求和，得到最终的损失函数：

$$L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b)$$

对上式求微分，即可得到感知器的训练规则。此处略过。

三个不等式

记$\hat{w}=(w^T,b)^T$，$\hat{x}=(x^T,1)^T$,显然$\hat{w}\cdot \hat{x}=w\cdot x+b$。若训练数据集线性可分，则存在超平面可将数据集完全分开，取此超平面为$\hat{w_{opt}}\cdot \hat{x}=0$,且不妨令$||\hat{w}_{opt}||=1$.

取 $\gamma=min_i\{y_i(w_{opt}\cdot x_i+b_{opt})\}$ 。其实$\gamma$ 就是误分类样本点到超平面距离的最小值。

记$\hat{w}_k$是第$k$次迭代后的参数，学习过程：

$$\hat{w}_k=\hat{w}_{k-1}+\eta y_k\hat{x}_k \tag{2.1}$$

$||\hat{w}_k||$上界

由三角不等式及式(2.1)，有：$||\hat{w}_k||\le||\hat{w}_{k-1}||+||\eta y_k\hat{x}_k||=||\hat{w}_{k-1}||+\eta ||y_k||\cdot||\hat{x}_k||$

考虑到$y_k​$ 符号不确定，我们平方处理：

$$\begin{align*} \Vert\hat{w}_{k}\Vert^2&= \hat{w}_{k}\cdot \hat{w}_{k}\\ &=[\hat{w}_{k-1}+\eta y_k\hat{x}_k]\cdot[\hat{w}_{k-1}+\eta y_k\hat{x}_k]\\ &=\hat{w}_{k-1}\cdot[\hat{w}_{k-1}+\eta y_k\hat{x}_k]^T+\eta y_k\hat{x}_k\cdot[\hat{w}_{k-1}+\eta y_k\hat{x}_k]\\ &=\Vert\hat{w}_{k-1}\Vert^2+\hat{w}_{k-1}\cdot\eta y_k \hat{x}_k+\eta y_k\hat{x}_k\cdot\hat{w}_{k-1}+\eta y_k\Vert\hat{x}_k\Vert^2\\ &=\Vert\hat{w}_{k-1}\Vert^2+2\eta y_k\hat{w}_{k-1}\cdot \hat{x}_k+\eta^2 y_k^2\Vert\hat{x}_k\Vert^2\\ \end{align*}$$

考虑$y_k\hat{w}_{k-1}\cdot \hat{x}_k$， 由于第$k$个样本$\hat{x}_k$相对于参数$\hat{w}_{k-1}$是错误的，则$\hat{w}_{k-1}\cdot \hat{x}_k$ 一定与$y_k$异号（见上文消除误分类点的符号差异性 ），故$y_k\hat{w}_{k-1}\cdot \hat{x}_k\le0$。

所以我们有：

$$\Vert\hat{w}_k^2\Vert\le\Vert\hat{w}_{k-1}\Vert^2+\eta^2 \Vert\hat{x}_k\Vert^2 \tag{2.2}\le \eta^2\sum_{i=1}^{i=k}\Vert\hat{x}_i\Vert^2\le k\eta^2R^2\\ R=max\{\Vert\hat{x}_i\Vert\}$$

$||\hat{w}_k||$下界

$$\begin{align*} \hat{w}_k\cdot \hat{w}_{opt} &= \hat{w}_{k-1}\cdot \hat{w_{opt}}+\eta y_i\hat{x_i}\cdot\hat{w_{opt}}\\ &\ge \hat{w}_{k-1}\cdot \hat{w_{opt}}+\eta\gamma\\ &\ge \hat{w_{k-2}}\cdot \hat{w_{opt}}+2\eta\gamma\\ &\cdots\\ &\ge k\eta\gamma \tag{2.3} \end{align*}$$

所以就$\hat{w}_k\ge\frac {k\eta\gamma} {\hat{w}_{opt}}$ ？大错特错。2个向量之间不能比较大小。况且点乘【 $\cdot$ 】 不是实数的乘法。

考虑$k\eta\gamma\le\hat{w}_k\cdot\hat{w}_{opt}\le||\hat{w}_k||\times||\hat{w}_{opt}||$ ,所以我们有:

$$||\hat{w}_k||\ge\frac{k\eta\gamma}{||\hat{w}_{opt}||}$$

$k$上界

结合(2.2)和(2.3)，且$||\hat{w}_{opt}||=1$，我们有：

$$k\eta\gamma\le||\hat{w}_k||\times||\hat{w}_{opt}||\le\sqrt{k}\eta R$$

即$k^2\gamma^2\le kR^2$ ,得:

$$k\le\frac{R^2}{\gamma^2}$$

变形

假设感知器的函数输出函数sign() 以及样本类标$y_i$类标为0和+1，那么如何进行以上证明？

首先考虑到以上所有推导证明都不涉及感知器的输出函数sign ，而公式里大多都和$y_i$ 有关。下面从$y_i$ 角度考虑。

同样，到超平面的距离仍然是式(1)。但是在消除误分类点的符号差异性时，有两种方法：

1. 取$y^{new}_i=2\times (y_i-0.5)$, 这样就把$\{0,+1\}$ 映射到$\{-1,+1\}$ ，所有后面的证明都相同。
2. 上课说的，取 $y^{new}_i=y_i-\hat{w}\cdot\hat{x} $, 若是FP，$\hat{w}\cdot\hat{x}>0$ , $y_i^{new}<0$ ;="" 若是fn,="" 同理$y_i^{new}="">0$ 映射到$(-\infty,0)\cup(0,\infty)$ 。当然这个变换缺陷是关于FP和FN是不对称的，且输出值不是固定值，不如方法1方便。优点是对所有样本都可以进行该变换，如果是分类正确的样本，$y_i^{new}=0$ ，在计算$L(w,b)$ 时就可以直接对全体样本代入计算，不用判断是否为误分类样本。

补充证明

1 法向量恒指向正样本

证明： 假设$x_0$ 恰好位于决策超平面上，即$w\cdot x_0+b=0$ ,那么从该点引出法向量指向$x_1$，即$x_1=x_0+\alpha w$ 。不失一般性，设$\alpha=1$ 。那么

$$\begin{align*} f(x) &= f(x_1)\\ &=sign(w\ x_1+b) \\ &=sign(w(x_0+w)+b)\\ &=sign(w\cdot x_0+b+w^2)\\ &=sign(w^2)=1 \end{align*}$$

2 不连续

在$L$ 定义成误分类点的个数时，$L$ 很难(几乎不可能？)写成关于$w,b$ 的解析形式。就算有，那么也是包含数量巨大的脉冲函数（难以求微分）。在这种情况下要求得极小值，相当于一个超高维且分布规律弱的离散优化问题。

3 不考虑$||w||$

显然$w$ 和$b$ 同时按比例放大缩小时，对决策超平面没有任何影响，而感知器学习目标是改进决策超平面的位置。且分子分母同时带有$w$ 不易于函数优化（尤其分母还是欧氏距离函数）。

4 额外证明

题目出自《统计学习方法》 P36：设集合$S\subset R^n$ 是由$R^n$中的$k$个点所组成的集合，即$S=\{x_1,x_2,\cdots,x_k\}$，定义$S$的凸壳$conv(S)$为：

$$conv(S)=\{x=\sum_{i=1}^{k}\lambda_ix_i \Bigg | \sum_{i=1}^k\lambda_i=1,\lambda_i\ge0,i=1,2,\cdots,k \}$$

证明以下定理：样本集线性可分的充分必要条件是正实例点集所构成的凸壳与负实例点集所构成的凸壳互不相交。

证明过程见：https://vast-stars.com/2018/03/18/线性可分与凸壳/

参考

[1] 李航. 统计学习方法[M]. 清华大学出版社, 2012.

[2] 杨老师的PPT

[3] http://blog.csdn.net/y954877035/article/details/52210734