机器学习 | 感知机理论知识（二）

今天，我们一起对感知机剩下的部分进行学习。

上周我们学习了感知机算法的原始形式，这周我们将对原始形式算法收敛性进行说明，然后再讲解感知机算法的对偶形式。

算法的收敛性

收敛性即意味着经过有限次迭代可以得到一个将训练数据集完全正确划分的分离超平面及感知机模型。

为了便于说明，做出一些规定：

①将偏置b并入权重向量w，记作\(\hat{w} = (w^T , b^T)^T\)。

②将输入向量进行扩充，加入常数1，记作\(\hat{x}=(x^T , 1)^T\)。

这样，\(\hat{x}\)∈Rⁿ⁺¹，\(\hat{w}\)∈Rⁿ⁺¹，有\(\hat{w} · \hat{x} = w · x + b\)。

先来说定理：

设训练数据集T = {(x₁, y₁), (x₂, y₂), ..., (x_N, y_N)}是线性可分的，其中x_i∈X = Rⁿ，y_i∈Y = {-1, +1}，i = 1, 2, ..., N，则有：

①存在满足条件\(||\hat{w}_{opt}||=1\)的超平面\(\hat{w}_{opt}·\hat{x}=w_{opt} ·x+b_{opt}=0\)将训练集完全正确分开；且存在\(\gamma\) > 0，对所有i = 1, 2, ..., N，有以下式子： \[ y_i(\hat{w}_{opt}·\hat{x}_i)=y_i(w_{opt}·x_i + b_{opt})\geq \gamma \]

\[ (1)式 \]

②令\(R = max||\hat{x}_i||\)，则感知机算法在训练集上的误分类次数k满足不等式： \[ k \leq (\frac{R}{\gamma})^2 \]

\[ (2)式 \]

下面来证明：

取可以将数据集完全正确分开的超平面为\(\hat{w}_{opt}·\hat{x}=w_{opt} ·x+b_{opt}=0\)，使\(||\hat{w}_{opt}||=1\)。由于对有限的i = 1, 2, ... , N，均有： \[ y_i(\hat{w}_{opt}·\hat{x}_i)=y_i(w_{opt}·x_i + b_{opt})\geq0 \] 所以有 \[ \gamma = min\lbrace y_i(w_{opt}·x_i + b_{opt})\rbrace \] 使得 \[ y_i(\hat{w}_{opt}·\hat{x}_i)=y_i(w_{opt}·x_i + b_{opt})\geq \gamma \] 由此可以得到（1）式。

接下来证明（2）式：

对于感知机来说，出现了误分类点就会更新权重。规定用\(\hat{w}_{k-1}\)表示第k个误分类点之前的扩充权重向量，即 \[ \hat{w}_{k-1} = (w^T_{k-1}, b_{k-1})^T \] 则第k个误分类点的条件是： \[ y_i(\hat{w}_{k-1}·\hat{x}_i) = y_i(w_{k-1}·x_i + b_{k-1})\leq0 \]

\[ (3)式 \]

若\((x_i, y_i)\)是被\(\hat{w}_{k-1} = (w^T_{k-1}, b_{k-1})^T\)误分类的数据，则w和b的更新是 \[ w_k\leftarrow w_{k-1}+\eta y_ix_i \]

\[ b_k\leftarrow b_{k-1}+\eta y_i \]

即 \[ \hat{w}_k = \hat{w}_{k-1}+\eta y_i\hat{x}_i \]

\[ (4)式 \]

下面推导两个不等式：

<1> \[ \hat{w}_k · \hat{w}_{opt} \geq k\eta\gamma \]

\[ (5)式 \]

由(1)式和(3)式可得： \[ \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 \] 由此可以推得(4)式： \[ \hat{w}_k · \hat{w}_{opt} \geq \hat{w}_{k-1} · \hat{w}_{opt}+\eta \gamma \geq \hat{w}_{k-2} · \hat{w}_{opt}+2\eta \gamma \geq...\geq k\eta\gamma \] <2>
\[ ||\hat{w}_k||^2 \leq k\eta^2R^2 \]

\[ (6)式 \]

由(3)式和(4)式可证明(6)式： \[ ||\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^2R^2\\ \leq||\hat{w}_{k-2}||^2 + 2\eta^2R^2 \leq ...\\ \leq k\eta^2R^2 \]

结合上面证明的(5)式和(6)式可以得知(2)式： \[ k \eta\gamma \leq \hat{w}_k ·\hat{w}_{opt} \leq ||\hat{w}_k||||\hat{w}_{opt}|| \leq \sqrt{k} \eta R \] 即可得到(2)式。

由以上证明可知，误分类次数k是有上界的，经过有限次搜索可以找到完全正确分开线性可分数据集的分离超平面，即可证明感知机的原始算法是收敛的。

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

对偶形式的基本想法是：将w和b表示成实例\(x_i\)和标记\(y_i\)的线性组合的形式，通过求解其系数而求得w和b。按照原始算法中w和b的更新方式，假设修改n次，则w和b关于\((x_i,y_i)\)的增量分别是\(\alpha_iy_ix_i\)和\(\alpha_iy_i\)，这里\(\alpha_i = n_i\eta\)。这样，从学习过程可以看出，最后学习到的w和b为： \[ w = \sum_{i = 1}^N \alpha_iy_ix_i\\b = \sum_{i = 1}^N \alpha_iy_i \] 这里，\(\alpha_i \geq 0\)，i = 1, 2, ... , N，当\(\eta\) = 1时，表示第i个实例点由于误分类点而进行更新的次数。

感知机算法的对偶形式中，感知机模型为： \[ f(x) = sign(\sum_{j=1}^N \alpha_jy_jx_j·x + b) \] 输入为训练集，输出为\(\alpha\)和b，其中\(\alpha = (\alpha_1, \alpha_2,...,\alpha_N)^T\)。

首先初始化\(\alpha\)和b都为0，两者遇到误分类点\((x_i,y_i)\)后按照如下规则更新： \[ \alpha_i \leftarrow \alpha_i + \eta\\b \leftarrow b + \eta y_i \] 直到没有误分类点。

对偶形式中训练实例仅以内积的形式出现。为了方便，可以预先将训练实例间的内积计算出来并以矩阵的形式存储，这个矩阵就是Gram矩阵： \[ G = [x_i·x_j]_{N×N} \]

下面用一个例子来说明：

正样本点是\(x_1 = (3, 3)^T\)，\(x_2 = (4,3)^T\)，负样本点是\(x_3 = (1,1)^T\)，下面用对偶形式来求感知机模型。

首先设置初值：取\(\alpha_i = 0\)，i = 1, 2, 3，b = 0，\(\eta = 1\)。

然后计算Gram矩阵便于后续运算： \[ G = \left[\begin{array}{ccc} 18 & 21 & 6\\ 21 & 25 & 7\\ 6 & 7 & 2 \end{array}\right] \] 之后便是参数更新过程（具体过程不再展示，大家可以自己尝试计算一下，下面给出计算表格，大家计算后可以对照表格看看自己是否正确）：

k	0	1	2	3	4	5	6	7
		\(x_1\)	\(x_3\)	\(x_3\)	\(x_3\)	\(x_1\)	\(x_3\)	\(x_3\)
\(\alpha_1\)	0	1	1	1	1	2	2	2
\(\alpha_2\)	0	0	0	0	0	0	0	0
\(\alpha_3\)	0	0	1	2	3	3	4	5
b	0	1	0	-1	-2	-1	-2	-3

感知机的内容就到此结束啦！谢谢大家的观看！