模型
定义
感知机是二分类的线性分类模型，感知机定义为
$$f(x)=\mathrm{sign}(w\cdot x+b)$$
$$\begin{equation}
\mathrm{sign}(x)=
\begin{cases}
+1, &x\geqslant 0\\
-1, &x<0
\end{cases}
\end{equation}$$
其中输入 \(x\in \mathbf{R}^n\) 表示实例的特征向量，输出 \(y\in \{+1,-1\}\)表示实例的类别。模型参数 \(w\) 称为权值，参数 \(b\) 称为偏置。
几何模型
若 \(x\in \mathbf{R}^2\),
$$\begin{align}
w\cdot x+b&=0\\
(w^{(1)},w^{(2)})^\mathrm{T}\cdot (x^{(1)},x^{(2)})^\mathrm{T}+b&=0\\
\end{align}$$
该形式满足平面中的直线方程：
$$\begin{align}
(i,j)^\mathrm{T}\cdot (x^{(1)},x^{(2)})^\mathrm{T}+b&=0\\
ix^{(1)}+jx^{(2)}+b&=0
\end{align}$$
其中 \(w=(i,j)^\mathrm{T}\) 为直线法向量。
类似地，当 \(x\in \mathbf{R}^3\) 时，感知机模型满足空间中的平面方程：
$$ix^{(1)}+jx^{(2)}+kx^{(3)}+b=0$$
且 \(w=(i,j,k)^\mathrm{T}\) 为平面法向量。
因此，感知机在模型本质上是在特征空间 \(\mathbf{R}^n\) 中的一个超平面 \(S\)，代表特征向量的点被超平面 \(S\) 分隔成两部分，其中参数 \(w\) 为超平面法向量。
超平面 \(S\) 也应符合 \(\mathbf{R}^n\) 空间中的几何关系，所以在 \(\mathbf{R}^n\) 空间中的任意一点 \(x_0\) 到超平面的距离为
$$d=\frac{1}{||w||}|w\cdot x_0+b|$$
\(||w||\) 是 \(w\) 的 \(L_2\) 范数：
$$||w||=\sqrt{\sum(w_i)^2}$$
即法向量长度。
点到超平面距离
以 \(x\in \mathbf{R}^2\) 为例，将超平面 \(S\) 方程转化为截距式：
$$\begin{align}
ix^{(1)}+jx^{(2)}+b&=0\\
\frac{x^{(1)}}{-\frac{b}{i}}+\frac{x^{(2)}}{-\frac{b}{j}}&=1
\end{align}$$
超平面 \(S\) 在 \(x^{(2)}\) 轴上的截距就为 \(-\frac{b}{j}\)。过点 \(x_0\) 作平行于 \(S\) 的超平面 \(S_0\)，同样得到截距式：
$$\frac{x^{(1)}}{-\frac{b_0}{i}}+\frac{x^{(2)}}{-\frac{b_0}{j}}=1$$
超平面 \(S_0\) 在 \(x^{(2)}\) 轴上的截距为 \(-\frac{b_0}{j}\)。
将 \(d\) 平移至蓝色三角形中，\(\boldsymbol{w}\) 是超平面的法向量，\(\boldsymbol{w}=w=(i,j)^\mathrm{T}\)，根据向量夹角余弦公式
$$\begin{align}
\cos\theta&=|\cos(\boldsymbol{w},\boldsymbol{j})|\\
&=\frac{|\boldsymbol{w}\cdot\boldsymbol{j}|}{|\boldsymbol{w}||\boldsymbol{j}|}
\end{align}$$
\(\boldsymbol{j}\) 为 \(x^{(2)}\) 方向的单位向量，因此有
$$\begin{align}
\cos\theta&=\frac{|(i,j)^\mathrm{T}\cdot(0,1)^\mathrm{T}|}{|\boldsymbol{w}|}\\
&=\frac{|j|}{|\boldsymbol{w}|}
\end{align}$$
在蓝色三角形中，
$$\begin{align}
d&=\left|\frac{b}{j}-\frac{b_0}{j}\right|\cos\theta\\
&=\frac{|b-b_0|}{|j|}\frac{|j|}{|\boldsymbol{w}|}\\
&=\frac{|b-b_0|}{|\boldsymbol{w}|}\\
\end{align}$$
由 \(w\cdot x_0+b_0=0\) 得到 \(b_0=-w\cdot x_0\)，代入就可以证得
$$d=\frac{|w\cdot x_0+b|}{||w||}$$
策略
感知机的分类情况可以归为以下几类：
- \(w\cdot x_i+b\geqslant0\),\(\ y_i=+1\)，分类正确；
- \(w\cdot x_i+b\geqslant0\),\(\ y_i=-1\)，分类错误；
- \(w\cdot x_i+b<0\),\(\ y_i=-1\)，分类正确；
- \(w\cdot x_i+b<0\),\(\ y_i=+1\)，分类错误。
因此分类错误的数据点 \((x_i,y_i)\) 满足
$$-y_i(w\cdot x_i+b)>0$$
若超平面 \(S\) 误分类的点的集合为 \(M\)，那么误分类点到超平面的距离之和为
$$\sum_{x_i\in M}\left[-\frac{1}{||w||}y_i(w\cdot x_i+b)\right]$$
略去 \(\frac{1}{||w||}\)（见第七章），得到经验风险函数：
$$L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b)$$
感知机的学习策略就是在假设空间中选取 \(L(w,b)\) 最小的模型参数 \(w\) 和 \(b\)。
算法
Code Here.
感知机的学习算法就是求解以下最优化问题的算法：
$$\min_{w,b}L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b)$$
随机梯度下降法
- 任意选取超平面 \(w_0\cdot x+b_0=0\);
- 随机选取误分类点使 \(L(w,b)\) 梯度下降；
- 不断更新 \(w\) 与 \(b\)，直至 \(L(w,b)=0\)。
二元函数 \(f(x,y)\) 在 \((x_0,y_0)\) 处的梯度定义为
$$\mathbf{grad}\ f(x_0,y_0)=\nabla f(x_0,y_0)=f_x(x_0,y_0)\boldsymbol{i}+f_y(x_0,y_0)\boldsymbol{j}$$
因此损失函数 \(L(w,b)\) 的梯度为
$$\nabla_wL(w,b)=\frac{\partial\left[-\sum_{x_i\in M}\color{orangered}{y_i}(w\cdot \color{orangered}{x_i}+b)\right]}{\partial w}=-\sum_{x_i\in M}\color{orangered}{y_ix_i}$$
$$\nabla_bL(w,b)=\frac{\partial\left[-\sum_{x_i\in M}\color{orangered}{y_i}(w\cdot x_i+b)\right]}{\partial b}=-\sum_{x_i\in M}\color{orangered}{y_i}$$
随机选择误分类点 \((x_i,y_i)\) 更新 \(w\) 与 \(b\)，使 \(L(w,b)\) 沿梯度方向下降：
$$w\leftarrow w+\eta y_ix_i$$
$$b\leftarrow b+\eta y_i$$
其中 \(\eta\ (0<\eta\leqslant1)\) 称为步长，不断迭代至 \(L(w,b)=0\)。
原始形式算法
算法2.1
输入：训练集 \(T\)，学习率 \(\eta\)
输出：\(w\) 与 \(b\) ，感知机模型 \(f(x)=\mathrm{sign}(w\cdot x+b)\)
- 设定步长 \(\eta\)，选取初值 \(w_0\) 与 \(b_0\)，一般为 \(w_0=0\)，\(b_0=0\)；
- 选取点 \((x_i,y_i)\)；
- 若 \(y_i(w\cdot x_i+b)\leqslant0\)，
$$w\leftarrow w+\eta y_ix_i$$
$$b\leftarrow b+\eta y_i$$
- 重复步骤（2），直至没有误分类点，即 \(L(w,b)=0\)。
对偶形式算法
经过数次以下迭代步骤：
$$w\leftarrow w+\eta y_ix_i$$
$$b\leftarrow b+\eta y_i$$
最终的 \(w\) 和 \(b\) 可以表示为
$$w=\sum_{i=1}^N \alpha_iy_ix_i$$
$$b=\sum_{i=1}^N\alpha_iy_i$$
其中 \(\alpha_i=n_i\eta\)，\(n_i\) 表示点 \((x_i,y_i)\) 被误分类的次数。也就是说，在迭代的每一次过程中，被误分类的点 \((x_i,y_i)\) 都不断向超平面靠近，直至位于超平面的另一侧。
最后得到的感知机模型应为
$$f(x)=\mathrm{sign}\left(\sum_{i=1}^N\alpha_iy_ix_i\cdot x+b\right)$$
为了与 \(x=x_i\) 代入后的模型相区别，表示为
$$f(x)=\mathrm{sign}\left(\sum_{j=1}^N\alpha_jy_jx_j\cdot x+b\right)$$
算法2.2
输入：训练集 \(T\)，学习率 \(\eta\)
输出：\(\alpha\) 与 \(b\) ，感知机模型 \(f(x)=\mathrm{sign}\left(\sum_{j=1}^N\alpha_iy_jx_j\cdot x+b\right)\)
- 设定步长 \(\eta\)，选取初值 \(\alpha\) 与 \(b_0\)，一般为 \(\alpha=(\alpha_1,\alpha_2,\cdots,\alpha_N)^\mathrm{T}=0\)，\(b_0=0\)；
- 选取点 \((x_i,y_i)\)；
- 若\(y_i\left(\sum_{j=1}^N\alpha_jy_jx_j\cdot x_i+b\right)\leqslant0\)，
$$\alpha_i\leftarrow\alpha_i+\eta$$
$$b\leftarrow b+\eta y_i$$
- 重复步骤 2，直至没有误分类点。
考虑迭代的判断条件
$$y_i\left(\sum_{j=1}^N\alpha_jy_j\vec{x_j}\cdot \vec{x_i}+b\right)\leqslant0$$
每次判断都需要计算
$$\sum_{j=1}^N\alpha_jy_j\color{orangered}{\vec{x_j}\cdot \vec{x_i}}=\alpha_1y_1\color{orangered}{\vec{x_1}\cdot\vec{x_i}}+\alpha_2y_2\color{orangered}{\vec{x_2}\cdot\vec{x_i}}+\cdots+\alpha_Ny_N\color{orangered}{\vec{x_N}\cdot\vec{x_i}}$$
因此可以将内积以矩阵形式存放，即 Gram 矩阵：
$$\boldsymbol{G}=[x_i\cdot x_j]_{N\times N}=\begin{bmatrix}
x_1\cdot x_1 &\cdots &x_1\cdot x_N\\
\vdots &\ddots &\vdots\\
x_N\cdot x_1 &\cdots &x_N\cdot x_N
\end{bmatrix}$$
由于内积的性质，Gram 矩阵实际上是一个对称矩阵。
References
