感知机——《统计学习方法》笔记

感知机——《统计学习方法》笔记

1 模型定义

  假设输入空间为$X \subseteq \textbf {R}^n​$ ,输出空间为$Y = { +1, -1}​$ ，输入$x \in X​$为实例的特征向量，输出$y \in Y​$为实例的类别，则以下从输入到输出的函数成为感知机
$$
f(x) = sign(w \cdot x + b)
$$
  其中$w,b$为感知机的参数，$w \in \textbf {R}^n$一般称为权值(weight)，$b \in \textbf {R}$称为偏置(bias)。$w \cdot x$为$w$和$x$的内积，那么两个$n$维的向量的点积得到一个实数。sign为符号函数
$$
sign(x) =
\begin{cases}
+1 & x \geq 0 \\
-1 & x < 0
\end{cases}
$$
  感知机为线性分类模型，属于判别模型，感知机模型的假设空间为特征空间中所有的线性分类模型或者线性分类器的集合。

  感知机的几何解释为，线性方程
$$
w \cdot x + b = 0
$$
对应于特征空间中的一个超平面$S$，其中$w$和$b$分别为超平面的法向量和截距。若这个超平面就将特征空间分为两个部分，分别为正负两类，那么称这个超平面为分离超平面，如图所示

  感知机的学习为给定训练集
$$
T={ (x_1, y_1), (x_2,y_2),…(x_N,y_N)}
$$
其中$x_i \in X \subseteq \textbf{R}^n,y_i \in Y={+1,-1},i=1,2,…N$，求得模型参数$w,b$。而感知机的预测，可通过模型求得输入实例所对应的类别。

2 损失函数

  给定一个数据集，若存在某个分类超平面能够将数据集的正实例和负实例完全分正确地划分到超平面的两侧，则称数据集为线性可分数据集，否则称数据集为线性不可分。

  假设训练数据是线性可分的，那么我们的目标是找到一个分类超平面，将训练数据的正负实例分开，也就是要找到合适的$w,b$(通过$w,b$可以确定一个超平面)。因此感知机模型定义损失函数为误分类点到超平面$S$的总距离。其中任意一个点$x_0$到超平面的距离为
$$
\frac{1}{||w||}(w \cdot x + b)
$$
    其中$||w||$为$w$的二范数。对于误分类的数据$(x_i,y_i)$
$$
-y_i(w \cdot x_i + b) > 0
$$
成立，因为当误分类数据为$(x_i,y_i=-1)$时，即负类被分类成正类，那么$w \cdot x_i + b > 0$，成立；当误分类数据为$(x_i,y_i=1)$时，即正类被分类成负类，那么$w \cdot x_i + b < 0$，也成立。所以误分类点$x_i$到超平面的距离为
$$
-\frac{1}{||w||}y_i(w \cdot x_i + b)
$$
​ 如果不考虑$\frac{1}{||w||}$，则将几何间隔转化为函数间隔$y(w \cdot x + b)$，就可得到感知机学习的损失函数。那么给定数据集$T={ (x_1, y_1), (x_2,y_2),…(x_N,y_N)}$，感知机学习的损失函数为：
$$
L(w,b) = -\sum_{x_i \in M} y_i(w \cdot x_i + b)
$$
  其中$M$为误分类点的集合。

3 学习算法

3.1 算法原始形式

  定义最优化问题：给定一个训练数据集$T={ (x_1, y_1), (x_2,y_2),…(x_N,y_N)}$，求参数$w,b$，使其为以下损失函数极小化问题的解
$$
min_{w,b}L(w,b) = -\sum_{x_i \in M} y_i(w \cdot x_i + b)
$$
  感知机学习算法可以采用通过随机梯度下降。首先计算损失函数$L(w,b) $的梯度，对$w,b$求偏导，有

$$
\frac{\partial(L(w,b))}{\partial w} = -\sum_{x_i \in M}y_ix_i \\
\frac{\partial(L(w,b))}{\partial b} = -\sum_{x_i \in M}y_i\\
$$

  那么学习算法流程为：

  输入：训练数据集合$T={ (x_1, y_1), (x_2,y_2),…(x_N,y_N)}$，学习率$\eta(0<\eta \leq 1)$;

  输出：$w,b$;感知机模型$f(x)=sign(w\cdot x + b)$。

  （1）初始化$w_0,b_0$

  （2）在训练集上选择数据$(x_i,y_i)$

  （3）如果$y_i(w\cdot x_i + b) \leq 0$
$$
w \leftarrow w + \eta y_ix_i \\
b \leftarrow b + \eta y_i
$$
  （4）转至（2），知道全部分类正确。

  下面为以例2.1为例的代码实现。

正实例点为$x_1=(3,3)^T,x_2=(4,3)^T$,负实例点是$x_3=(1,1)^T$。

  首先先用numpy生成数据：

import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline

# 用于打印数据
def print_var(var, name='x'):
    print(name+':\n',var, '\nshape:', var.shape if hasattr(var, 'shape') else '')


# 例2.1 中的数据
x = np.array([[3, 3],[4, 3], [1, 1]]).T
print_var(x, 'x')
y = np.array([1, 1, -1])
print_var(y, 'y')
lr = 1
w, b = np.zeros([1,2]), 0
print_var(w, 'w')
print_var(b, 'b')

>>>
x:
 [[3 4 1]
 [3 3 1]] 
shape: (2, 3)
y:
 [ 1  1 -1] 
shape: (3,)
    
w:
 [[ 0.  0.]] 
shape: (1, 2)
b:
 0 
shape:

  定义$w \cdot x+b$

def wx_plus_b(x, w, b):
    pred = np.dot(w, x) + b
    return pred

  学习过程代码如下：

all_True = False
iter_num = 0

# 不断迭代，直到所有样本被正确分类为止
while not all_True:
    iter_num += 1
    for i in range(x.shape[1]):
        
        # 取第i个样本
        sample_x = x[:, i]
        sample_y = y[i]
        pred = wx_plus_b(sample_x, w, b)
        
        # 若样本被正确分类则跳过
        if sample_y * pred > 0:
            continue
        else:
            # 更新参数 w和b
            w = w + lr * sample_y * sample_x
            b = b + lr * sample_y
            print(iter_num, ' x_%s '%(i+1), ' (%d,%d) '%(w[0,0], w[0,1]), str(b).rjust(2), '分类超平面: %dx1+%dx2%+d'%(w[0,0], w[0,1], b))
            break
    else:
        # 若全部被分类
        all_True = True

>>>
1  x_1   (3,3)   1 分类超平面: 3x1+3x2+1
2  x_3   (2,2)   0 分类超平面: 2x1+2x2+0
3  x_3   (1,1)  -1 分类超平面: 1x1+1x2-1
4  x_3   (0,0)  -2 分类超平面: 0x1+0x2-2
5  x_1   (3,3)  -1 分类超平面: 3x1+3x2-1
6  x_3   (2,2)  -2 分类超平面: 2x1+2x2-2
7  x_3   (1,1)  -3 分类超平面: 1x1+1x2-3

3.2 算法对偶形式

  将参数$w,b$用实例的$x_i$和标记$y_i$的线性组合来表示，可得到算法的对偶形式。在算法3.1中，每次更新$w,b$都是通过找到误分类点$(x_i,y_i)$来更新，那么到了最后就可以将$w,b$ 可以表示为:
$$
w = \sum_{i=1}^N \alpha_iy_ix_i \\
b = \sum_{i=1}^N \alpha_iy_i
$$
  其中$\alpha=(\alpha_1,\alpha_2,…,\alpha_N)^T$,$N$为样本个数。

  那么就有$w\cdot x + b=\sum_{i=1}^N \alpha_iy_ix_i \cdot x + b$，学习算法流程为：

 学习算法流程为：

  输入：训练数据集合$T={ (x_1, y_1), (x_2,y_2),…(x_N,y_N)}$，学习率$\eta(0<\eta \leq 1)$;

  输出：$\alpha,b$;感知机模型$f(x)=sign(\sum_{j=1}^N \alpha_jy_jx_j \cdot x + b)$。

  （1）初始化$\alpha=(0,0, …,0)^T,b = 0$

  （2）在训练集上选择数据$(x_i,y_i)$

  （3）如果$y_i(\sum_{j=1}^N \alpha_jy_jx_j \cdot x + b) \leq 0$
$$
\alpha_i \leftarrow \alpha_i + \eta \\
b \leftarrow b + \eta y_i
$$
  （4）转至（2），知道全部分类正确。

  因为在对偶形式中训练实例都是以内积形式出现，所以预先计算所有的实例点之间的内积保存以来，可以大量减少计算时间，这个实例点内积的矩阵结果成为Gram矩阵
$$
G = [x_i \cdot x_j]_{N*N}
$$
  下面为以例2.1为例的对偶形式的代码实现。

  首先先生成数据

# 例2.1 中的数据
x = np.array([[3, 3],[4, 3], [1, 1]]).T
y = np.array([1, 1, -1])
lr = 1

alpha = np.zeros(x.shape[1])
print_var(alpha, 'alpha')
b = 0

>>> 
alpha:
 [ 0.  0.  0.] 
shape: (3,)

  计算Gram矩阵

# 首先先计算 Gram 矩阵，可由x点乘x的转置矩阵得到
Gram = np.dot(x.T, x)
print_var(Gram, 'Gram')

>>>
Gram:
 [[18 21  6]
 [21 25  7]
 [ 6  7  2]] 
shape: (3, 3)

  定义$\sum_{j=1}^N \alpha_jy_jx_j \cdot x + b$

# 对偶形式的计算方法
def calc_dual(x_i_idx, alphas_j, ys_j, b):
    """
    x_i_idx: 传入的样本的index
    alphas_j: 所有alpha的值
    ys_j: 所有y的值
    """
    pred = 0
    for j, (y_j, alpha_j) in enumerate(zip(ys_j, alphas_j)):
        # 从Gram矩阵中取出 x_j_i，并按照公式计算
        x_j_i = Gram[x_i_idx, j]
        pred += alpha_j * y_j * x_j_i
    pred = pred + b
    return pred

  学习过程代码如下：

all_True = False
iter_num = 0
while not all_True:
    iter_num += 1
    for i in range(x.shape[1]):
        sample_y = y[i]
        pred = calc_dual(i, alpha, y, b)
        if sample_y * pred > 0:
            continue
        else:
            # 更新参数alpha和b
            alpha[i] += lr
            b += lr * sample_y
            
            # 根据alpha和x,y计算w
            w = (np.multiply(x, y) * alpha).sum(1)
            S = ' 分类超平面: %dx1+%dx2%+d=0'%(w[0], w[1], b)
            
            print('k:%2d '%iter_num, ' x_%s '%(i+1), 'a1:%2d  a2:%2d  a3:%2d  b:%+d'%(*alpha, b), S)
            
            break
    else:
        all_True = True

>>>
k: 1   x_1  a1: 1  a2: 0  a3: 0  b:+1  分类超平面: 3x1+3x2+1=0
k: 2   x_3  a1: 1  a2: 0  a3: 1  b:+0  分类超平面: 2x1+2x2+0=0
k: 3   x_3  a1: 1  a2: 0  a3: 2  b:-1  分类超平面: 1x1+1x2-1=0
k: 4   x_3  a1: 1  a2: 0  a3: 3  b:-2  分类超平面: 0x1+0x2-2=0
k: 5   x_1  a1: 2  a2: 0  a3: 3  b:-1  分类超平面: 3x1+3x2-1=0
k: 6   x_3  a1: 2  a2: 0  a3: 4  b:-2  分类超平面: 2x1+2x2-2=0
k: 7   x_3  a1: 2  a2: 0  a3: 5  b:-3  分类超平面: 1x1+1x2-3=0

4 瞎谈

  嗯，就这样，完整代码地址见github，尽管文章里面的代码已经是全的了。
  接下来会陆续写完统计学习方法的笔记和上传实验代码。