统计学习(2)--感知机
摘要
感知机
1.感知机的定义
对于一个输入空间，如果存在一个超平面将实例分为正负两类，那么可以认为输入空间的输出空间可以通过如下函数实现。
\[ f(x)=\operatorname{sign}(w^T \cdot x+b) \]
该模型被称为感知机模型，其中\(w^T\)和\(b\)是感知机模型参数，线性方程
\[ w^T \cdot x+b \]
是在特征空间中的一个超平面，其中\(w\)是超平面的法向量，b是超平面的截距。
\(\operatorname{sign}\)是符号函数
\[ \operatorname{sign}(x)=\left\{\begin{array}{ll} +1, & x \geqslant 0 \\ -1, & x<0 \end{array}\right. \]
2.感知机学习策略
2.1 损失函数
感知机损失函数的一个自然选择是误分类点的总数，但这样损失函数不是参数\(w\)、\(b\)连续可导函数，不容易优化。
另一个选择是点到超平面S的总距离。
记空间中点为\(X^{(i)}\)，超平面为 \(w^T \cdot X+b\) ，空间中的任意一点到平面的距离 = 该点到平面任意一点的向量在平面的法向量上的投影。
\[ \begin{array}{l} D=\left|\frac{w}{\|w\|_{2}} \cdot\left(X^{(i)}-X^{(0)}\right)\right| \\ =\left|\frac{1}{\|w\|_{2}} \cdot\left(w^{T} \cdot X^{(i)}-w^{T} \cdot X^{(0)}\right)\right| \\ =\left|\frac{1}{\|w\|_{2}} \cdot\left(w^{T} \cdot X^{(i)}+b\right)\right| \end{array} \]
其中\(X^{(0)}\)是超平面上的点。
对于误分类数据\(\left(x_{i}, y_{i}\right)\)来说，
\[ -y_{i}\left(w^T \cdot x_{i}+b\right)>0 \]
假设误分类点集合为\(M\),那么所有误分类点到超平面的总距离为
\[ -\frac{1}{\|w\|} \sum_{x_{i} \in M} y_{i}\left(w^T \cdot x_{i}+b\right) \]
不考虑常数\(\frac{1}{\|w\|}\),即可得到感知机学习的损失函数。这里省略转置，下同。
\[ L(w, b)=-\sum_{x_{i} \in M} y_{i}\left(w \cdot x_{i}+b\right) \]
该损失函数就是感知机的经验风险函数。
2.2 随机梯度下降
对于感知机模型来说最优化方法是随机梯度下降法，损失函数如下
\[ \min _{w, b} L(w, b)=-\sum_{x_{i} \in M} y_{i}\left(w \cdot x_{i}+b\right) \]
梯度计算如下
\[ \nabla_{w} L(w, b)=-\sum_{x_{j} \in M} y_{i} x_{i} \\ \]
\[ \nabla_{b} L(w, b)=-\sum_{x_{i} \in M} y_{i} \]
为此选取更新策略为
\[ \begin{array}{c} w \leftarrow w+\eta y_{i} x_{i} \\ b \leftarrow b+\eta y_{i} \end{array} \]
3.收敛性证明
将超平面简记为\(\hat{w}\cdot\hat{x}\)
设训练集线性可分，则存在一个超平面\(\hat{w}_{opt}\cdot\hat{x}\)使得训练集完全正确分开，令\(\|\hat{w}_{opt}\|=1\), 那么对有限的\(i=1,2,...,N\)均有
\[ y_{i}\left(\hat{w}_{\text {opt }} \cdot \hat{x}_{i}\right)=y_{i}\left(w_{\text {opt }} \cdot x_{i}+b_{\text {opt }}\right) \geqslant \gamma \tag{式1} \]
其中
\[ \gamma=\min _{i}\left\{y_{i}\left(w_{\mathrm{opt}} \cdot x_{i}+b_{\mathrm{opt}}\right)\right\} \]
根据更新公式
\[ \begin{array}{l} w_{k} \leftarrow w_{k-1}+\eta y_{i} x_{i} \\ b_{k} \leftarrow b_{k-1}+\eta y_{i} \end{array} \]
可得
\[ \hat{w}_{k}=\hat{w}_{k-1}+\eta y_{i} \hat{x}_{i} \]
假设初始值为\(\hat{w}_0 = 0\)时,需要k次迭代达到最优值，有
\[ \begin{aligned} \hat{w}_k\cdot\hat{w}_{\text{opt}} & = (\hat{w}_{k-1}+\eta y_{i} \hat{x}_{i})\cdot\hat{w}_{\text{opt}} \\ & = \hat{w}_{k-1} \cdot \hat{w}_{\mathrm{opt}}+\eta y_{i} \hat{w}_{\mathrm{opt}} \cdot \hat{x}_{i} \\ & \geqslant \hat{w}_{k-1} \cdot \hat{w}_{\mathrm{opt}}+ \eta \gamma \\ & \geqslant \cdots \\ & \geqslant \hat{w}_{0} \cdot \hat{w}_{\mathrm{opt}}+ k\eta \gamma \\ & = k\eta \gamma \end{aligned} \]
另外有
\[ \begin{aligned} \left\|\hat{w}_{k}\right\|^{2} &=\left\|\hat{w}_{k-1}\right\|^{2}+2 \eta y_{i} \hat{w}_{k-1} \cdot \hat{x}_{i}+\eta^{2}\left\|\hat{x}_{i}\right\|^{2} \\ & \leqslant\left\|\hat{w}_{k-1}\right\|^{2}+\eta^{2}\left\|\hat{x}_{i}\right\|^{2} \\ & \leqslant\left\|\hat{w}_{k-1}\right\|^{2}+\eta^{2} R^{2} \\ & \leqslant\left\|\hat{w}_{k-2}\right\|^{2}+2 \eta^{2} R^{2} \\ & \leqslant \cdots \\ & \leqslant k \eta^{2} R^{2} \end{aligned} \]
结合上述两式可得不等式
\[ k \eta \gamma \leqslant \hat{w}_{k} \cdot \hat{w}_{\mathrm{opt}} \leqslant\left\|\hat{w}_{k}\right\|\left\|\hat{w}_{\mathrm{opt}}\right\| \leqslant \sqrt{k} \eta R \]
即对于k有
\[ k \leqslant\left(\frac{R}{\gamma}\right)^{2} \]
该不等式的意义指出如果空间线性可分，迭代次数是有上界的。
4.感知机学习算法的对偶形式
在初始值为0的时候，对于N次迭代后参数\(w\)、\(b\)分别为
\[ w=\sum_{i=1}^{N} \alpha_{i} y_{i} x_{i} \tag{式2} \]
\[ b=\sum_{i=1}^{N} \alpha_{i} y_{i} \]
其中\(\alpha_{i} =\mathrm{n}_{\mathrm{i}} \eta\)，\(\eta\)为学习率，当\(\eta=1\)时，\(\alpha_{i}\)就代表了第\(i\)个实例由于误分而进行更新的次数。通常这个点会越接近分离超平面，因为这些点比较难被分类，它们对学习结果的影响最大。
使用(式2)代替损失函数的\(w\)值，可得对偶形式的训练条件为
当
\[ y_{i}\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \cdot x_{i}+b\right) \leqslant 0\tag{式3} \]
则
\[ \alpha_{i} \leftarrow \alpha_{i}+\eta \]
\[ b \leftarrow b+\eta y_{i} \]
由于(式3)中出现了大量内积形式的训练实例，可以预先将训练集的实例计算出来并储存为Gram矩阵
Gram矩阵的定义是
\[ G=A^{T} A=\left[\begin{array}{c} \mathbf{a}_{1}^{T} \\ \mathbf{a}_{2}^{T} \\ \vdots \\ \mathbf{a}_{n}^{T} \end{array}\right]\left[\begin{array}{llll} \mathbf{a}_{1} & \mathbf{a}_{2} & \cdots & \mathbf{a}_{n} \end{array}\right]\\=\left[\begin{array}{cccc} \mathbf{a}_{1}^{T} \mathbf{a}_{1} & \mathbf{a}_{1}^{T} \mathbf{a}_{2} & \cdots & \mathbf{a}_{1}^{T} \mathbf{a}_{n} \\ \mathbf{a}_{2}^{T} \mathbf{a}_{1} & \mathbf{a}_{2}^{T} \mathbf{a}_{2} & \cdots & \mathbf{a}_{2}^{T} \mathbf{a}_{n} \\ \mathbf{a}_{n}^{T} \mathbf{a}_{1} & \mathbf{a}_{n}^{T} \mathbf{a}_{2} & \cdots & \mathbf{a}_{n}^{T} \mathbf{a}_{n} \end{array}\right] \]