《统计学习方法》读书笔记一：感知机

感知机模型

感知机是一种线性分类模型。假设输入空间是$X subseteq mathbb{R}^n (，输出空间是)Y = {-1, 1}(，定义从)X(到)Y(的如下函数 [ f(x) = mbox{sign}(w^Tx + b) ] 其中)x in X$, (w in mathbb{R}^n)，(b in mathbb{R})，sign是符号函数。

感知机的几何意义是，由线性方程(w^Tx + b =0)定义的超平面将输入空间划为两个部分，位于两个部分的点分别为正、负两类。其中(w)是超平面的法向，这个超平面称为分离超平面（separating hyperplane）。

感知机学习

在训练集(T = {(x_1, y_1) dots, (x_N,y_N)})上学习得到感知机模型，并对于新的输入得到其输出类别，用于分类。

感知机学习的损失函数

一种自然的定义是所有误分类点到分离超平面的总距离，输入空间中任意一点(x_0)到超平面(w^Tx+b=0)的距离定义为
[
frac{1}{|w|_2} |w^Tx_0 + b|
]
但这里需要用到不可导的绝对值函数

注意到对于误分类的数据((x_i, y_i))有
[
y_i(w^Tx_i + b ) < 0
]
并且(|y_i| = 1)，于是(|w^Tx_i + b|)可以被(-y_i(w^Tx_i + b ))替换掉，得到
[
-frac{1}{|w|_2}y_i(w^Tx_i + b)
]

忽略(frac{1}{|w|})，得到感知机学习的损失函数
[
L(w,b) = -sum_{x_i in M} y_i(w^Tx_i + b)
]
其中(M)是误分类点的集合，此函数关于(w),(b)连续可导。

于是感知机学习问题求转化为优化问题
[
min_{w,b} L(w,b) = -sum_{x_i in M} y_i(w^Tx_i + b)
]

感知机学习算法

对损失函数求得梯度
egin{align}
& partial_w L(w,b) = sum_{x_i in M} y_i x_i \
& partial_b L(w,b) = sum_{x_i in M} y_i
end{align}
用随机梯度下降法求解，得到更新为
egin{align}
& w = w + eta y_i x_i \
& b = b + eta y_i
end{align}
其中(eta)是learning rate。

于是得到感知机学习算法：

1. 选取初值(w_0, b_0)
2. 在训练集中选取数据((x_i,y_i))
3. 如果(y_i(w^Tx_i + b) leq 0)，即((x_i,y_i) in M)，则更新(w,b)
   egin{align}
   & w = w + eta y_i x_i \
   & b = b + eta y_i
   end{align}
4. 转置（2），直至训练集中没有误分类点。

注意，其实优化问题
[
min_{w,b} L(w,b) = -sum_{x_i in M} y_i(w^Tx_i + b)
]
在无约束时是有问题的。因为去掉了(frac{1}{|w|})，(w=0,b=0)是它的最优解。此外如果假设(w_star eq 0, b_star eq 0)是它的最优解，那么(L(frac{1}{2}w_star, frac{1}{2}b_star) < L(w_star,b_star))与假设矛盾，因此(w=0,b=0)是优化问题唯一的最优解，这显然是错的。

但为什么用感知机的学习算法又能求得问题的解呢？因为在感知机学习算法中，加了一个迭代停止的判定条件：第一次达到没有误分点时迭代停止。而不是通常我们用的损失函数不再下降作为停止条件。所以当(w=0,b=0)不能构成分离超平面时，(w=0,b=0)不是一组解。如果(w_star eq 0, b_star eq 0)是一组解，那么(cw_star eq 0, cb_star eq 0)这组解目前为止没有在迭代过程中出现过，否则迭代在它出现是就停止了。因此(w_star eq 0, b_star eq 0)是能构成分离超平面的第一组解。也就是我们要求的。

感知机学习算法的收敛性

设训练集(T = {(x_1, y_1) dots, (x_N,y_N)})线性可分，则有

1. 存在满足条件(| ilde{w_star}|=1)的超平面( ilde{w_star}^Tx = w_star^Tx + b_star = 0)，将数据集完全分开，且存在(gamma > 0)满足
   [
   forall i, quad y_i( ilde{w_star}^Tx_i) geq gamma
   ]
2. 记(R = max_{1 leq i leq N} | ilde{x_i}|)，感知机学习算法在训练集上误分类的次数(k)满足(k leq (frac{R}{gamma})^2)

证明思路：(forall k) (frac{ ilde{w_star}^T ilde{w(k)}}{| ilde{w_star}|| ilde{w(k)}|} leq 1)，且有( ilde{w_star}^T ilde{w(k)} geq ilde{w_star}^T ilde{w(k-1)} + eta gamma)，(| ilde{w(k)}| leq | ilde{w(k-1)}| + eta^2 R^2)

感知机算法的对偶形式

由于上面收敛性的证明是不依赖初值的，所以可以取初值为(w_0 = 0, b = 0)，于是有
egin{align}
& w = sum_{i=1}^N alpha_i y_i x_i \
& b = sum_{i=1}^N alpha_i y_i
end{align}
其中(alpha_i = n_i eta)，(n_i)表示第(i)个点由于误分而进行更新的次数。

于是我们可以假设感知机模型是(f(x) = mbox(sign)left( sum_{j = 1}^N alpha_j y_j x_j^x + b ight))，则损失函数变为
[
L(alpha, b) = -sum_{x_i in M} y_ileft( sum_{j = 1}^N alpha_j y_j x_j^x + b ight)
]
优化问题变为
[
min_{alpha,b} L(alpha, b)
]
求梯度得
egin{align}
& partial_{alpha_j} L = -sum_{x_i in M} y_i y_j x_i^T x_j \
& partial_b L = -sum_{x_i in M} y_i
end{align}