Day5~6 第二章感知机

1 感知机模型

定义 2.1 (感知机) 假设输入空间是 $\mathcal{X}\subseteq\mathbb{R}^n$ ，输出空间是 $\mathcal{Y}=\{+1,-1\}$ 。输入 $x\in\mathcal{X}$ 表示实例的特征向量，对应输出空间的的点；输出 $y\in\mathcal{Y}$ 表示实例的类别。由输入控件到输出空间的如下函数： $f(x)=\text{sgn}(\omega \cdot x+b)$ 称为感知机。其中， $\omega$ 和 $b$ 为感知机模型的参数， $\omega \in \mathbb{R}^n$ 叫做权值 (weight) 或权值向量 (weight vector)， $b\in\mathbb{R}^n$ 叫做偏置 (bias)， $\omega\cdot x$ 表示 $\omega$ 和 $x$ 的内积， $\text{sgn}$ 是符号函数。
感知机是一种线性分类模型，属于判别模型。感知机模型的假设空间是定义在特征空间中的所有线性分类模型，即函数集合 $\{f|f(x)=\omega\cdot x+b\}$ 。

2 感知机学习策略

2.1 数据集的线性可分性

定义 2.2 (数据集的线性可分性) 给定一个数据集 $T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\}$ 其中， $x_i\in\mathcal{X}=\mathbb{R}^n$ ， $y_i\in\mathcal{Y}=\{+1,-1\}$ ， $i=1,2,\dots ,N$ ，若存在某个超平面 $S$ 能够将数据集的正实例点与负实例点完全正确地划分到超平面的两侧，则称数据集 $T$ 为线性可分数据集 (linearly swparaable data set)；否则，称数据集 $T$ 线性不可分。
数据集是线性可分的是感知机学习最基本的假设之一。

2.2 感知机学习策略

感知机的学习目标是求得一个能够将训练集正实例点和负实例点完全正确分开的超平面。为此我们需要定义一个包含模型参数 $\omega$ 与 $b$ 的损失函数并将其极小化。
通常地，我们选择误分类点到超平面 $S$ 的总距离作为损失函数，这样得到的函数往往具有连续可导等良好性质，便于优化计算。
假设超平面 $S$ 的误分类点集合为 $M$ ，给定数据集 $T$ 同定义 2.2，那么所有误分类点到超平面 $S$ 的总距离为 $-\frac{1}{||\omega||}\sum\limits_{x_i\in M} y_i(\omega \cdot x_i+b)$ 其中， $||\omega||$ 表示 $\omega$ 的 $L_2$ 范数。

不难注意到 $1/||\omega||$ 恒为正数，将其舍去一方面不影响超平面对实例点的划分，另一方面可以避免大数除以小数以避免舍入误差。实际上 $y(\omega\cdot x+b)$ 称为样本点的函数间隔，是衡量点与平面间隔大小的重要指标之一。

这样就得到了感知机学习的损失函数： $L(\omega,b)=-\sum\limits_{x_i\in M} y_i(\omega \cdot x_i+b)$

3 感知机学习算法

3.1 感知机学习算法的原始形式

假设超平面 $S$ 的误分类点集合为 $M$ ，给定数据集 $T$ 同定义 2.2，根据 2.2 小节的分析，我们已经得到感知机学习策略等价于求解含参数 $\omega$ 与 $b$ 的如下最优化问题： $\min\limits_{\omega,b} L(\omega,b) = \min\limits_{\omega,b}\left\{- \sum\limits_{x_i\in M} y_i(\omega \cdot x_i+b)\right\}$ 感知机学习算法采用的是随机梯度下降法 (stochastic gradient descent)。

梯度下降法是沿着函数下降最快的方向即梯度方向进行迭代搜索，对于参数 $\omega$ 与 $b$ 的更新，所有的样本都有贡献： $\left( \begin{array}{l} \omega^T \\ b \end{array} \right) \leftarrow \left( \begin{array}{l} \omega^T \\ b \end{array} \right)- \eta\ \big(\text{grad}\ L(\omega ,b)\big)^T = \left( \begin{array}{l} \omega^T+\eta\sum\limits_{x_i\in M} y_ix_i^T \\ b+\eta\sum\limits_{x_i\in M} y_i\end{array} \right)$ 其中 $\eta(0<\eta\leqslant 1)$ 为步长，在统计学习中又称为学习率(learning rate)。
而随机梯度法是用样本中的一个例子来近似所有的样本： $\left( \begin{array}{l} \omega^T \\ b \end{array} \right) \leftarrow \left( \begin{array}{l} \omega^T \\ b \end{array} \right) +\eta\left( \begin{array}{l} y_ix_i^T \\ \ \ \ y_i \end{array} \right)$ 其中， $\eta(0<\eta\leqslant 1)$ 为步长。
随机梯度法相较于梯度下降法的优点是当样本量很大时，训练速度是非常快的（因为梯度下降算法每次迭代都要用到全部样本)，并且可以进行在线更新。但是随机梯度下降最大的缺点在于每次学习可能并不会按照正确的方向进行，因此可能带来优化波动(扰动)，并且容易陷入局部最优点。
另外，有一种折中的办法称为小批量梯度下降法 (mini-batch gradient descent)，算法使用了一些小样本来近似全部的样本。相对于随机梯度下降，其降低了收敛波动性，即降低了参数更新的方差，使得更新更加稳定。相对于全量梯度下降，其提高了每次学习的速度。这个方法在神经网络训练中是非常常用的。

通过上述分析，得到如下算法：
算法2.1（感知机学习算法的原始形式）
输入：训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\}$ ，其中 $x_i\in\mathcal{X}=\mathbb{R}^n$ ， $y_i\in\mathcal{Y}=\{+1,-1\}$ ， $i=1,2,\dots,N$ ；学习率 $\eta(0<\eta\leqslant 1)$ ；
输出： $\omega ,b$ ；感知机模型 $f(x)=\text{sgn}(\omega\cdot x+b)$ ；
(1) 选取初值 $\omega_0,b_0$ ;
(2) 在训练集中选取数据 $x_i,y_i$ ；
(3) 若 $y_i(\omega\cdot x_i +b)\leqslant 0$ ，则 $\omega\leftarrow\omega+\eta\ y_ix_i$ $b\leftarrow b+\eta\ y_i$ (4) 转至 (2)，直至训练集中没有误分类点。

注：不难发现，若数据集不可分则该算法将会一直迭代下去。

3.2 感知机学习算法的对偶形式

对偶形式的基本想法是，将 $w$ 和 $b$ 表示为实例 $x_i$ 和标记 $y_i$ 的组合形式，通过求解其系数来求解 $w$ 和 $b$ 。不失一般性，假设算法 2.1 中 $w$ 和 $b$ 初始值都为 0。逐步对参数 $\omega$ 与 $b$ 进行迭代，迭代 $n$ 次后，参数 $\omega$ 与 $b$ 可表示为： $\omega=\sum_{i=1}^N\alpha_i y_ix_i,\quad b=\sum_{i=1}^N\alpha_i y_i$ 其中 $\alpha_i=n_i \eta$ ， $\sum\limits_{i=1}^N n_i = n$ ， $n_i$ 表示第 $i$ 个实例点由于误分而进入迭代的次数。 $n_i$ 越大，表明该实例点被选用的次数越多，也就是越接近超平面，从而越容易被分错。
通过上述分析，得到如下算法：
算法2.2（感知机学习算法的对偶形式）
输入：训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\}$ ，其中 $x_i\in\mathcal{X}=\mathbb{R}^n$ ， $y_i\in\mathcal{Y}=\{+1,-1\}$ ， $i=1,2,\dots,N$ ；学习率 $\eta(0<\eta\leqslant 1)$ ；
输出： $\omega ,b$ ；感知机模型 $f(x)=\text{sgn}(\sum\limits_{j=1}^N \alpha_j y_j x_j \cdot x+b)$ ；
(1) 选取初值 $\alpha_0=,b_0=0$ ;
(2) 在训练集中选取数据 $x_i,y_i$ ；
(3) 若 $y_i\left(\sum\limits_{j=1}^N \alpha_j y_j x_j \cdot x_i +b\right)\leqslant 0$ ，则 $\alpha\leftarrow\alpha+\eta$ $b\leftarrow b+\eta\ y_i$ (4) 转至 (2)，直至训练集中没有误分类点。

对偶形式只用计算 $x_i$ 与 $x_j$ 的内积，而避免了在迭代过程中 $\omega$ 与 $x_i$ 的内积计算。可以预先将训练集中的实例间的内积计算出来并以矩阵的形式储存，即 Gram 矩阵，这样能够减少在迭代学习过程中的计算，加快学习速率。

4 习题

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

证明：
设集合 $S\subset \mathbb{R}^n$ 由 $k$ 个点组成： $S = \{x_1,\dots,x_k\}$ 。那么根据定义 $S$ 的凸壳 $\text{conv(S)}$ 为 $\text{conv}(S)=\left\{x=\sum\limits_{i=1}^k \lambda_i x_i \bigg|\sum\limits_{i=1}^k \lambda_i=1, \lambda_i\geqslant 0, i=1,2,\dots ,k \right\}$ 设正实例点集为 $S^+$ ，其构成的凸壳为 $\text{conv}(S^+)$ ；设负实例点集为 $S^-$ ，其构成的凸壳为 $\text{conv}(S^-)$ 。
不失一般性，设 $x_1,\dots,x_{m} \in S^+，x_{m+1},\dots,x_{k} \in S^-$ 。
（1）必要性
必要性的直接证明比较复杂，我的想法是由于凸壳是一个凸集，再参考最优化理论里的凸集分离定理即可得证。证明凸壳是凸集是简单的，这里以证明 $\text{conv}(S^+)$ 是凸集为例：
$\forall v_1 ,v_2 \in \text{conv}(S^+), \exists \lambda_1,\dots,\lambda_m,\eta_1,\dots,\eta_m\geqslant 0$ , 满足 $\Sigma\lambda_i=\Sigma\eta_i=1$ . 且 $v_1=\sum\limits_{i=1}^m\lambda_ix_i, \quad v_2=\sum\limits_{i=1}^m\eta_ix_i$ 于是 $\forall \xi\in[0,1]$ 有
$\begin{align} \xi v_1+(1-\xi )v_2 = & \,\, \xi\sum\limits_{i=1}^m\lambda_ix_i+(1-\xi)\sum\limits_{i=1}^m\eta_ix_i\\ = & \,\sum\limits_{i=1}^m \big(\xi\lambda_i+(1-\xi)\eta_i\big)x_i\\ \end{align}$ 令 $\tau_i=\xi\lambda_i+(1-\xi)\eta_i$ ，由于 $\xi\in[0,1]$ ，故有 $\tau_i\geqslant 0$ ， $i=1,2,\dots m$ ，并且
$\begin{align} \sum\limits_{i=1}^m\tau_i = & \,\sum\limits_{i=1}^m \big(\xi\lambda_i+(1-\xi)\eta_i\big)\\ = & \,\, \xi\sum\limits_{i=1}^m\lambda_i+(1-\xi)\sum\limits_{i=1}^m\eta_i\\ = & \,\, \xi+(1-\xi)=1\\ \end{align}$ 因此 $\forall \xi\in[0,1]$ 有 $\xi v_1+(1-\xi)v_2\in \text{conv}(S^+)$ 。即集合内任意两点之间的连线都仍然在集合内，故 $\text{conv}(S^+)$ 是凸集。根据凸集分离定理即可得证。凸集分离定理的证明这里就不再重复了，可参考开头给出的参考资料。
直接的证明方法可参考统计学习方法习题解答第2章感知机。

（2）充分性
根据线性可分的定义，必然存在 $\omega$ 与 $b$ ，使得 $\forall x_i\in S$ 以及对应的 $y_i$ 满足 $y_i(\omega\cdot x_i+b)>0,\ i=1,2,\dots k$ 反证法。假设正实例点集所构成的凸壳与负实例点集所构成的凸壳相交。则 $\exists x^*\in S$ 满足 $x^*\in \text{conv}(S^+)$ ，且 $x^*\in \text{conv}(S^-)$ 。
①一方面由于 $x^*\in \text{conv}(S^+)$ ，可得 $x^*=\sum\limits_{i=1}^m\eta_ix_i$ 满足 $\sum\limits_{i=1}^m \eta_i=1, \eta_i\geqslant 0, i=1,\dots ,m$ ，从而 $\begin{align} \omega \cdot x^*+b= & \,\, \omega \cdot \sum\limits_{i=1}^m\eta_ix_i+b\\ = & \,\,\omega \cdot \sum\limits_{i=1}^m\eta_ix_i+\sum\limits_{i=1}^m\eta_i b\\ = & \,\, \sum\limits_{i=1}^m\eta_i(\omega \cdot x_i+ b)\\ \end{align}$ 由于 $\forall x_i\in S^+$ 有 $y_i=1$ 。结合线性可分 $y_i(\omega\cdot x_i+b)>0$ ，从而 $\omega\cdot x_i+b>0$ 。再结合 $\eta_i\geqslant 0$ ，于是 $\omega \cdot x^*+b=\sum\limits_{x_i\in S^+}\eta_i(\omega \cdot x_i+ b)>0$ 故 $x^*$ 位于超平面 $\omega\cdot x + b$ 的上方。
②另一方面由于 $x^*\in \text{conv}(S^-)$ ，可得 $x^*=\sum\limits_{i=m+1}^k\eta_ix_i$ 满足 $\sum\limits_{i=m+1}^k \eta_i=1, \eta_i\geqslant 0, i=1,\dots ,m$ ，从而 $\begin{align} \omega \cdot x^*+b= & \,\, \omega \cdot \sum\limits_{i=m+1}^k\eta_ix_i+b\\ = & \,\, \omega \cdot \sum\limits_{i=m+1}^k\eta_ix_i+\sum\limits_{i=m+1}^k\eta_i b\\ = & \sum\limits_{i=m+1}^k\eta_i(\omega \cdot x_i+ b)\\ \end{align}$ 由于 $\forall x_i\in S^-$ 有 $y_i=-1$ 。结合线性可分 $y_i(\omega\cdot x_i+b)>0$ ，于是 $\omega\cdot x_i+b<0$ 。再结合 $\eta_i\geqslant 0$ ，从而 $\omega \cdot x^*+b=\sum\limits_{x_i\in S^-}\eta_i(\omega \cdot x_i+ b)<0$ 故 $x^*$ 位于超平面 $\omega\cdot x + b$ 的下方。
显然 $x^*$ 不能同时位于一个超平面的上方与下方，故假设不成立。因此正实例点集所构成的凸壳与负实例点集所构成的凸壳互不相交。充分性得证。