统计学习方法 - 第 2 章感知机 - ⎝⎛CodingNote.cc ⎞⎠

统计学习方法 – 第 2 章感知机

2021 年 8 月 16 日
筆記

第 2 章感知机

感知机Perceptron是1957年，由Rosenblatt提出会，是神经网络和支持向量机的基础。

要求：数据集线性可分(linearly separable data set)

模型：
$$f(x) = sign(w.x + b)$$
其中$x,w \in \mathbb{R}^n ,b \in \mathbb{R}$,$w$叫作权值（weight）或权值向量（weight vector），$b$叫作偏置（bias），sign是符号函数
$$sign(x) = \begin{cases}
+1 & x \geq 0 \
-1 & x<0
\end{cases}$$

感知机是一种线性分类模型，属于判别模型。感知机模型的假设空间是定义在特征空间中的所有线性分类模型（linear classification model）或线性分类器(linear classifier)，即函数集合${f|f(x)＝w·x+b}$

超平面S：$w.x+b = 0$,其中$w$是S的法向量，$b$是S的截距，超平面S称为分离超平面（separating hyperplane）

策略：
$$L(w,b) = -\sum_{x_i \in M}{y_i(w.x_i + b)}$$
其中$M$为误分类点的集合。误分类数据$M = { (x_i,y_i)|-y_i(w.x_i +b) > 0}$

函数间隔：$y(w.x + b)$
几何间隔：$\frac{1}{||w||}|w.x + b|$ (在上面的loss function中没有考虑$\frac{1}{||w||}$)

算法：
$$\min_{w,b} L(w,b) = -\sum_{x_i \in M}{y_i(w.x_i + b)}$$
使用随机梯度下降法（stochastic gradient）:

初始化参数(随机法)：$w_0,b_0$
选取数据$(x_i,y_i)$
如果$(x_i,y_i)$是误分类点，也就是$y_i(w.x_i + b) \leq 0$，则对$w,b$进行更新
$$在(x_i,y_i)点处梯度为：\ \nabla_wL(w,b) = -y_ix_i \ \nabla_bL(w,b) = -y_i\ 更新w：w_{k+1} \gets w_{k}+\eta y_ix_i \ 更新b：b_{k+1} \gets b_{k}+\eta y_i \其中学习率\eta \in (0,1]$$
循环2-3，直到训练集中没有误分类点。

上述算法的收敛性：

Novikoff定理：
设训练集$T = {(x_1,y_1),…,(x_N,y_N)}$是线性可分的，

设完美超平面$\hat{w}{opt}.\hat{x} = 0 , ||\hat{w}{opt}||=1$ 将训练集完全正确分开（简化起见 $\hat{w}{opt}.\hat{x} = w{opt}.x +b$），存在$\gamma >0$ ,对所有点有$y_i(\hat{w}_{opt}.\hat{x_i}) \geq \gamma$；
令$R = \max_{1\leq i\leq N}||\hat{x_i}||$,则算法会在有限步k满足不等式$k \leq (\frac{R}{\gamma})^2$

证明(注意：带hat的表示扩充向量)：

因为数据线性可分，对于所有点$y_i(\hat{w}{opt}.\hat{x_i}) > 0$,所以存在
$$\gamma = \min_i{y_i(\hat{w}{opt}.\hat{x_i})} \leq {y_i(\hat{w}_{opt}.\hat{x_i})} \label{2-1}\tag{2-1}$$
所以这里的$\gamma$代表了所有点离完美超平面的最小距离；
为了方便计算设扩充向量$\hat{w} = (w^T,b)T$，有
$$\hat{w}{k} = \hat{w}{k-1}+\eta y_i\hat{x_i} \label{2-2}\tag{2-2}$$
推导不等式
$$\hat{w}{k}.\hat{w}{opt} \geq k\eta\gamma \label{2-3}\tag{2-3}$$

由$\eqref{2-1}$和$\eqref{2-2}$
$$\hat{w}{k}.\hat{w}{opt} = \hat{w}{k-1}.\hat{w}{opt} + \eta{y_i}\hat{w}{opt}.\hat{x_i} \ \geq \hat{w}{k-1}.\hat{w}{opt} + \eta\gamma \ \geq \hat{w}{k-2}.\hat{w}_{opt} + 2\eta\gamma \ \geq k\eta\gamma$$

推导不等式
$$||\hat{w}{k}||^2 \leq k\eta^2R2 \label{2-4}\tag{2-4}$$
由$\eqref{2-2}$
$$||\hat{w}{k}||^2=||\hat{w}{k-1}+\eta y_i\hat{x_i}||^2 = ||\hat{w}{k-1}||^2 + 2\eta{y_i}\hat{w}{k-1}.\hat{x}{i} + \eta^{2||\hat{x}_{i}||}2$$
假设k次完全分完，那么k-1次有误分类点，则${y_i}\hat{w}{k-1}.\hat{x}{i} \leq 0$
所以
$$||\hat{w}{k}||^2 =||\hat{w}{k-1}||^2 + 2\eta{y_i}\hat{w}{k-1}.\hat{x}{i} + \eta^{2||\hat{x}_{i}||}2 \ \leq ||\hat{w}{k-1}||^2 + \eta^{2||\hat{x}_{i}||}2 \ \leq ||\hat{w}{k-1}||^2 + \eta^2R2 \ \leq ||\hat{w}_{k-2}||^2 + 2\eta^2R2 \leq … \ \leq k\eta^2R2$$
由$\eqref{2-3}$和$\eqref{2-4}$

$$k\eta\gamma \leq \underbrace{\hat{w}{k}.\hat{w}{opt} \leq ||\hat{w}{k}||.\underbrace{||\hat{w}{opt}||}{=1} }{\text{柯西-施瓦茨 (Cauchy–Schwarz) 不等式}} \leq \sqrt{k} \eta R \ ; \ \Rightarrow k^2\gamma2 \leq kR^2 \ \Rightarrow k \leq (\frac{R}{\gamma})^2$$

也就是k是有上界的。