[统计学习]第二章感知机

感知机（Perceptron），是线性分类模型，利用一个线性超平面对数据进行二分类。

1. 感知机模型

感知机的模型的假设是对于输入空间中的变量，经模型
$$
f(x)=\text{sign}(w\cdot x+b) \tag{1} \label{1}
$$
得到输入变量 $y\in \lbrace -1, +1 \rbrace$ 。对于模型中的 $\text{sign}$ 它是一个指示函数，用于筛选在某种条件下属于正例，反之属于负例。该模型是属于 $y=f(x)$ 的模型，即是一个判别模型。

2. 感知机学习策略

对于给定的数据集是线性可分的：即满足 $y_i=+1$ 的实例 $i$ 满足 $w\cdot x_i+b>0$，反之实例 $i$ 满足 $w\cdot x_i+b<0$ 的条件的情况下数据集才是线性可分的，否则数据集是线性不可分的。

确定感知机模型参数 $w$ 和 $b$ 是通过明确损失函数最小化的来明确。这个经验损失函数误分类数据到超平面的距离确认的：
$$
\begin{align}
L(w) & = -\frac{1}{\left| w\right|}\displaystyle{ \sum_{x_i\in X}y_i(w\cdot x_i+b)} \
\end{align}
$$
上面的公式中误分类点的确认是通过 $y_i \left(w\cdot x_i+b \right)$ 来判断，因为是误分类的情况 $y_i$ 和 $\left(w\cdot x_i +b \right)$ ^1的正负号不一致情况，结果一定是小于零；另外当 $x_i$ 在 $w\cdot x_1+b$ 的线上时 $w\cdot x_1+b=0$，损失函数结果为零 。其中 $\left |w \right|$ 是参数 $w$ 的二范数，数据值肯定是大于零。整个函数的最优化问题变为求解误分类点的。

在进行计算优化策略：没有误分类的点，损失函数的值为 $0$；误分类点的损失函数值为 $\left( w\cdot x+b\right)$。最终是从假设空间 $\eqref{1}$ 中选择损失函数最小的模型参数 $w$ 和 $b$。

3. 感知机算法

3.1 算法流程

感知机算法是一个误分类驱动的解决的问题，在计算过程中使用的随机梯度下降方法（Stochastic Gradient Descent）是其中一种方法，计算的方式就是就是利用下式计算出更新数据值：
$$
\begin{align}
\frac{\partial{L(w,b)}}{\partial w}&=-\displaystyle{\sum_{x_i\in X}y_i\times x_i} \
\frac{\partial{L(w,b)}}{\partial b}&=-\displaystyle{\sum_{x_i\in X}y_i} \
\end{align}
$$
参数^2每步更新的具体数据值需要通过学习率 $\eta$ 来确定“步长”，对于任意一个发生误分类(即满足 $y_i(w_i\cdot x_i+b)\le 0$)的数据点 $(x_i, y_i)$ 的权重更新如下：
$$
\begin{align}
w &\leftarrow w+\eta \times y_i\times x_i \
b & \leftarrow b + \eta \times y_i
\end{align}
$$

3.2 算法收敛性证明

感知机算法的收敛需要证明的是在数据集 $T=\lbrace (x_1,y_1),(x_2, y_2),\cdots, (x_N, y_N)\rbrace$ 满足线性可分的条件下，感知机随着参数更新，其误分类次数 $k$ 是有上界的。对 Novikoff 定理解读：

1. 存在满足条件的 $\vert \hat{w}{\text{opt}} \vert=1$ 的超平面 $\hat{w}{\text{opt}}\cdot \hat{x}=w_{\text{opt}}\cdot x+b_{\text{opt}}$ 经数据集正确分开，同时存在$\gamma \gt 0$ 对所有 $i=1,2,\cdots, N$ 满足 $y_i\times(\hat{w}{\text{opt}}\cdot \hat{x_i})=y_i\times (w{\text{opt}}\cdot x_i+b_{\text{opt}})\ge \gamma$

   解读： $|\hat{w}{\text{opt}}|=1$ 的意思是参数 $w{\text{opt}}$ 和 $b_{\text{opt}}$ 构造的超平面的法向量的长度为一，且这个超平面能够将数据正确分类——那么 $y_i \times f(x_i)$ 的结果肯定是非负数的

2. 假定 $R=\displaystyle{\max_{1\le i \le N}|\hat{x}_i|}$，那么感知机算法在数据集中误分类次数 $k$ 满足不等式 $k\le \left(\frac{R}{\gamma} \right)^2$

   解读： 这个条件是算法收敛的最终说明，理解该结果需要有一个完整的证明过程手写证明过程

3.3 感知机算法的对偶形式

对偶形式的思路是，以 $w$ 和 $b$ 作为数据实例 $x_i$ 和对应的标签 $y_i$ 的线性组合形式，求解系数就可以得到对应的参数。如果参数初始化的值为 $\vec{0}$，那么通过 $W\leftarrow W+\eta\times y_i\times x_i$ 更新参数的方式，最终参数更新的累计值是 $\displaystyle{\sum_{i=1}^N \alpha_i\times y_i\times x_i}$ ^3。

在步骤三中 $x_j\cdot x_i$ 是构建的 Gram 矩阵^4。迭代计算的步骤中，感知机算法的对偶形式和原始形式是对应的，同时结果也是存在多个解。

参考

Dot products and duality 中可以了解到点积 $\left( w\cdot x_i\right)$对应的几何变换是 $x_i$ 和 $w$ 之间的有“方向”的距离计算，添加上 $b$ 可以看作是在延着超平面截距移动。从下面的图中可以理解任意点 $x_i$ 到超平面的距离可以通过 $\frac{\left(w\cdot x_i \right)}{\left | w\right|}$ 方式得到（在不考虑截距移动的移动情况下）：

在使用 SGD 的过程中，首先会有一步初始化参数 $w$ 和 $b$ 的过程，因此在得到的结果上受初始化的值和误分类点不同，得到的结果也不同。梯度下降和 SGD 的差异在于，SGD 每一步计算的损失是不需要将所有的数据点都计算完，主要是存在大量数据的情况下 SGD 得到的损失是梯度下降损失的无偏估计。因此 SGD 能够保证计算结果，同时能够提高计算的效率

在算法中更新的参数是通过错误计数点来计算的，所以 $N$ 表示的是错误分类点，也就是 $\alpha_i=n_i\times \eta$ 中 $n_i$ 是在第 $i$ 次更新参数过程中有 $n_i$ 个错误分类点

Gram 矩阵是通过数据 $X\in \mathbb R^{N\times N}$ 的内积形式构建的：$\text{Gram Matrix}=[X_i\cdot X_j]_{N\times N}$，其重要的作用是确认数据特征之间的相关程度，所以其中的 $i$ 和 $j$ 都是表示的列索引。在应用上可以参见 A Neural Algorithm of Artistic Style 中应用 Gram 矩阵来分析图片的风格损失，这里的应用是通过 Gram 矩阵计算出图片的”风格“特征。

说明:

1. 封面图 “Perceptron” by fdecomite is licensed under CC BY 2.0
2. 缩略图来自 Flickr janeqjames