统计学习方法笔记之感知机
in 机器学习 with 0 comment

统计学习方法笔记之感知机

in 机器学习 with 0 comment

定义

假设输入空间是$\mathcal{X} \subseteq R^n$,输出空间是$\mathcal{Y} = \{+1, - 1\}$,由输入空间到输出空间的如下函数:

$$ f(x) = sign(w \centerdot x + b) $$

称为感知机。$w \in R^n$称作权值或权值向量,$b \in R$称作偏置,$w \centerdot x$是$w$和$x$的内积,sign是符号函数:

$$ sign(x) = \left\{ \begin{align} +1,x \geq 0 \\- 1, x < 0\end{align} \right. $$

感知机的假设空间是全体线性函数。

感知机学习策略

感知机的损失函数一个选择是误分类的点的个数,但是由于这样的损失函数不是参数$w$,$b$的连续可导函数,不易优化。损失函数的另外一个选择是误分类点到超平面$S$的总距离,这是感知机所采用的。我们知道,一个点$x_0$到一个平面的距离为:

$$ \frac{1}{||w||}|w \centerdot x_0 +b| $$

而且,对于误分类的数据$(x_i, y_i)$总有

$$ -y_i (w \centerdot x_i + b) > 0 $$

成立。这是因为如果点本来为正类,即$y_i = 1$,若误分类,则得到的$sign(w \centerdot x_i + b)=-1$,这样上式就大于0;反之,如果本来$y_i = -1$,误分类得到的结果$sign(w \centerdot x_i + b)=1$,上式结果仍大于0。因此,所有误分类的点(记集合为$M$)到超平面的距离就是

$$ - \frac{1}{||w||} \sum_{x_i \in M}y_i(w \centerdot x_i + b) $$

不考虑$\frac{1}{||w||}$,就得到了感知机的损失函数。

感知机学习算法

利用梯度下降法对感知机进行求解:

$$ \nabla_w L(w, b)= - \sum_{x_i \in M}y_i x_i \\ \nabla_b L(w, b) = -\sum_{x_i \in M}y_i $$

随机选择一个误分类点$(x_i, y_i)$,对$w,b$进行更新:

$$ w \gets w + \eta y_i x_i \\ b \gets b + \eta y_i $$

其中$\eta$称为步长,又称作学习率。通过迭代可以让$L(w, b)$不断减小,直至为0。

原始形式

假设输入线性可分的数据集为$\{ (x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}$,其中$x_i \in R^n$,$y \in \{+1, -1\}$,学习率$0 < \eta \leq 1$。则采用以下步骤进行求解:

(1)选取初值$w_0, b_0$;

(2)在训练集中选取数据$(x_i, y_i)$;

(3)如果$y_i(w \centerdot x_i) +b \leq 0$,

$$ w \gets w + \eta y_i x_i \\ b \gets b + \eta y_i $$

(4)回到步骤2,直至训练集中没有误分类点;

最终输出为$w,b$;感知机模型$f(x) = sign(w \centerdot x +b)$。

对偶形式

在每次迭代$w, b$的更新中:

$$ w \gets w + \eta y_i x_i \\ b \gets b + \eta y_i $$

设修改$n$次,则$w,b$关于$(x_i, y_i)$的增量分别是$\alpha_iy_ix_i$和$\alpha_iy_i$,这里$\alpha_i=n_i \eta$,那么最后的结果可以表示为:

$$ w = \sum^N_{i=1}\alpha_iy_ix_i \\ b = \sum^N_{i=1} \alpha_i y_i $$

因此我们就可以用对偶形式来叙述感知机算法:

假设输入线性可分的数据集为$\{ (x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}$,其中$x_i \in R^n$,$y \in \{+1, -1\}$,学习率$0 < \eta \leq 1$。则采用以下步骤进行求解:

(1)$\alpha = 0, b = 0$;

(2)在训练集中选取数据$(x_i, y_i)$;

(3)如果$\sum^N_{j=1}\alpha_j y_j x_j + b \leq 0$,则

$$ \alpha_i \gets \alpha_i+ \eta \\ b \gets b+\eta y_i $$

(4)回到步骤2,直至训练集中没有误分类点;

最终输出为$\alpha, b$,感知机模型$f(x) = sign(\sum^N_{j=1}\alpha_jy_jx_j \centerdot x + b)$,其中$\alpha = (\alpha_1, \alpha_2, \cdots, \alpha_N)^T$。

由于对偶形式中训练集仅以内积的形式出现。为了方便可以预先将训练集的内积计算出来并以矩阵的形式保存,这个矩阵称为Gram矩阵:

$$ G = \left[ \begin{matrix}x_1 \centerdot x_1 &x_1 \centerdot x_2 & \cdots & x_1 \centerdot x_N \\ x_2 \centerdot x_1 &x_2 \centerdot x_2 & \cdots & x_2 \centerdot x_N \\ \vdots & \vdots & \cdots & \vdots \\ x_N \centerdot x_1 &x_N \centerdot x_2 & \cdots & x_N \centerdot x_N \end{matrix}\right] $$

代码实现

下面是利用Python实现的感知机算法:

import numpy as np


def sign(w, x_i, b):
    """
    符号函数
    :param w: 权重矩阵,形如[1, 2, 3, 4, 5]
    :param x_i: 训练集的一个样本,列数(行数)和权重矩阵相同
    :param b: 偏置
    :return: +1,-1
    """
    if np.matmul(w.T, x_i) + b > 0:
        return 1
    else:
        return -1


def perceptron(w0, b0, eta, x, y):
    """
    感知机算法原始形式:
        1. 选取初值w0, b0;
        2. 在训练集中选取数据(xi, yi);
        3. 如果y_i(w * x_i) <= 0,更新w, b;
        4. 回到2,直到训练集中没有误分类点;
    :param w0: 初始w0,维数与x相同
    :param b0: 初始b0,常数
    :param eta: 步长
    :param x: 训练集
    :param y: 训练集标签
    :return: 包含w, b的元祖
    """
    m, n = x.shape
    w = w0
    b = b0
    iterations = 0
    while True:
        iterations = iterations + 1
        for i in range(m):
            if y[i] * sign(w, x[i], b) > 0:
                continue
            else:
                w = w + eta*y[i]*x[i]
                b = b + eta*y[i]
        corr_num = 0
        for j in range(m):
            if y[j] * sign(w, x[j], b) > 0:
                corr_num = corr_num + 1
        if corr_num == m:
            break
    print("经过了", iterations + 1, "次迭代算法收敛")
    return w, b


def perceptron_duality(eta, x, y):
    """
    感知机算法的对偶形式:
        1. 初始化alpha,b;
        2. 在训练集中选取(x_i, y_i);
        3. 如果 y_i * (\sum^N_{j=1}(\alpha_j y_j x_j * x_i) + b) <= 0,更新alpha,b;
        4. 转回2,直至没有误分类数据;
    :param eta: 步长
    :param x: 训练集
    :param y: 训练集的标签
    :return: w和b的二元元祖
    """
    m, n = x.shape
    alpha = np.zeros(m)
    b = 0
    # Gram矩阵
    gram = np.zeros((m, m))
    for i in range(m):
        for j in range(m):
            gram[i, j] = np.matmul(x[i].T, x[j])
    iterations = 0
    while True:
        iterations = iterations + 1
        for i in range(m):
            if y[i] * (sum(alpha[j]*y[j]*gram[j, i] for j in range(m)) + b) > 0:
                continue
            else:
                alpha[i] = alpha[i] + eta
                b = b + eta*y[i]
        corr_num = 0
        for i in range(m):
            if y[i] * (sum(alpha[j]*y[j]*gram[j, i] for j in range(m)) + b) > 0:
                corr_num = corr_num + 1
        if corr_num == m:
            break
    w = sum(alpha[i] * y[i] * x[i] for i in range(m))
    b = sum(alpha[i]*y[i] for i in range(m))
    print("经过", iterations+1, "次迭代后,算法收敛")
    return w, b

参考

李航《统计学习方法(第二版)》第二章

赞 (0)
Responses