机器学习 - 感知机

作者: tx_6df3 | 来源:发表于2018-11-06 23:12 被阅读0次

1.感知机模型

1.1感知机定义

假设输入空间（特征空间）是 $X\subseteq R^n$ ,输出空间是 $y\in\lbrace +1,-1 \rbrace$ ,输入 $x \in X$ 表示实例的特征向量，对应于输入空间特征空间）的点，输出 $y \in Y$ 表示实例的类别。由输入空间到输出空间的如下函数：
$f(x) = sign(w \cdot x+b)$
称为感知机，其中 $w$ 和 $b$ 称为感知机模型参数， $w \in R^n$ 叫做权值（weights）或权值向量(weight vector）， $b \in R$ 叫做偏置， $w \cdot x$ 表示 $w$ 和 $x$ 。
感知机有如下几何解释，线性方程：
$w \cdot x + b = 0$
对应于特征空间 $R^n$ 的一个超平面 $S$ ,其中 $w$ 是超平面的法向量， $b$ 是超平面的截距。这个超平面将特征空间划分为两个部分，位于两部分的点就被划分为正、负两类，即：
（1）若 $w \cdot x + b > 0$ ，则 $x$ 为正例, $f(x)=sign(w \cdot x + b)=1$
（2）若 $w \cdot x + b < 0$ ，则 $x$ 为负例, $f(x)=sign(w \cdot x + b) = -1$

2.感知机学习策略

2.1 数据集的线性可分性

给定一个数据集 $T=\lbrace (x_1,y_1),(x_2,y_2),...,(x_N,y_N) \rbrace$ ,其中 $x_i \in X = R^n$ , $y \in Y = \lbrace +1, -1 \rbrace$ , $i=1,2,..,N$ ，如果存在某个超平面 $S$ :
$w \cdot x + b = 0$
能够将数据集的正实例点和负实例点完全正确的划分到超平面的两侧，即对所有的 $y_i = +1$ 的实例 $i$ ,有 $w \cdot x + b > 0$ ,对所有的 $y_i = -1$ 的实例 $i$ ，有 $w \cdot x + b < 0$ ,则称数据集 $T$ 为线性可分数据集（linearly separable data set),否则称为不可分数据集。

2.2感知机的学习策略

损失函数的一个自然选择是误分类点的总数，但是这样的损失函数不是 $w , b$ 的连续可导函数，不容易优化。损失函数的另一个选择是误分类点到平面 $S$ 的总距离。
输入空间 $R^n$ 中一个点 $x_0$ 到超平面 $S$ 的距离是：
$|w \cdot x + b |\over ||w||$
若某个点被误分类，即：
（1） $x$ 为正例，但 $w \cdot x + b < 0$ , $f(x)=sign(w \cdot x + b)=-1, y = 1$
（2） $x$ 为负例,但 $w \cdot x + b > 0$ ， $f(x)=sign(w \cdot x + b) = 1, y = -1$
综合考虑，即：
$-y_i (w \cdot x + b ) > 0$
因此，每个误分类点 $x_i$ 到超平面 $S$ 的距离：
$- y_i(w \cdot x + b) \over ||w||$

假设超平面 $S$ 的误分类点的集合为 $M$ ，那么所有的误分类点到超平面 $S$ 的总距离为：
$- \sum_{x_i \in M} y_i (w \cdot x + b) \over ||w||$
由于 $1\over ||w||$ 是常量，不考虑该常量，就可以得到感知机的损失函数：
$L(w,b)= - \sum_{x_i \in M} y_i(w \cdot x + b)$

2.3 感知机学习算法

2.3.1 感知机学习算法的原始形式

目标函数：
$min L(w,b) = - \sum_{x_i \in M} y_i(w \cdot x + b)$

求解：梯度下降算法
感知机学习算法是误分类驱动的，具体采用梯度下降算法（stochastic gradient descent).首先，任选一个超平面 $w_0,b_0$ ，然后用梯度下降法不断的极小化目标函数。极小化的过程不是一次性使用 $M$ 中所有的点，而是每次只使用一个误分类点进行梯度下降，当没有误分类点时，即找到想要的超平面 $S$ .

假设误分类点的集合 $M$ 是固定的，那么损失函数 $L(w,b)$ 的梯度：
$\nabla_w L(w,b) = -\sum_{x_i \in M}y_i(w \cdot x + b)$
$\nabla_b L(w,b) = -\sum_{x_i \in M}y_i$
当前正遍历到误分类点 $(x_i,y_i)$ ,对 $w,b$ 进行更新，过程如下：
$w \leftarrow w + \eta y_i x_i$
$b \leftarrow b + \eta y_i$

其中 $\eta (0<\eta \leq 1)$ 是步长，在统计学习中又称为学习率。这样，通过迭代可以期待损失函数 $L(w,b)$ 不断减小，直到为0.

算法2.1（感知机学习算法的原始形式）###

输入：数据集 $T=\lbrace (x_1,y_1),(x_2,y_2),...,(x_N,y_N) \rbrace$ ,其中 $x_i \in X = R^n$ , $y \in Y = \lbrace +1, -1 \rbrace$ , $i=1,2,..,N$ ，学习率 $\eta(0<\eta\leq1)$
输出： $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 +b) \leq 0$ :
$w \leftarrow w + \eta y_i x_i$
$b \leftarrow b + \eta y_i$
(4)转至(2)，直到训练集中，没有误分类点。

实例（《统计学习方法》例2.1）：
代码如下：

import numpy as np

# 计算y值
def cacl_y(w, x, b):
    # print(w)
    # print(w.shape)
    # print(x)
    # print(x.shape)
    return np.sign(np.matmul(np.transpose(w), x) + b)

# 感知机计算过程
def perceptron(data_coord, data_label):
    # 0. 初始化参数:w,b, learning_rate
    learning_rate = 1
    w_star = np.zeros(shape=data_coord[0].shape) #zeros
    b_star = 0

    #1.开启更新w，b的循环:
    # 假设没有不可分的数据，当全部数据分类正确时，停止循环
    while True:
        count = 0;
        for i in range(len(data_coord)):
            # 2.1 对每个数据，查看分类是否错误
            x = data_coord[i]
            y_ = data_label[i]
            y = cacl_y(w_star, x, b_star)
            print("y_ = ", y_)
            print("y = ", y)
            print("\n\n")
            # 2.2 若分类错误(不大于0)，更新w，b
            if y * y_ <= 0:  # update w,b
                w_star += learning_rate * y_ * x
                b_star += learning_rate * y_
                print("w_star = ",w_star)
                print("b_star = ",b_star)

            # 2.2 分类正确，对分类正确的数据个数 计数
            else:
                print("count = ", count)
                count += 1
            print("One Circle Again!")
        print("After going through all data, count = ", count)

        # 3.1 对所有数据分类正确，stop circle
        if count == len(data_label):
            print("\n\n")
            break;
        # 3.2 否则，重启 遍历数据过程
        else:
            count = 0;
    # 4.结束：输出 w b
    print("w_star = ", w_star)
    print("b_star = ", b_star)

# 准备3组测试数据，2个正例， 1个负例
data_coord = np.asarray(((3, 3), (4, 3), (1, 1)))
data_label = np.asarray((1, 1, -1))
# start perceptron
perceptron(data_coord, data_label)

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

对偶形式的基本思想是，将 $w$ 和 $b$ 表示在实例 $x_i$ 和标记 $y_i$ 的线性组合的形式，通过求解其系数求得 $w$ 和 $b$ .不失一般性，在上一个算法中，将 $w_0$ 和 $b_0$ 设置为0，对于误分类点 $(x_i,y_i)$ ,通过：
$w \leftarrow w + \eta y_i x_i$
$b \leftarrow b + \eta y_i$
逐步修改 $w$ 和 $b$ ,设修改 $n$ 次，则 $w$ 和 $b$ a关于 $(x_i,y_i)$ 的增量分别是 $\alpha_i y_i x_i$ 和 $\alpha_i y_i$ ,其中 $\alpha_i = n_i \eta$ ,这样，经过学习之后，最终学习到的 $w$ 和 $b$ 可以表示如下：
$w = \sum_{i=1}^{n} \alpha_i y_i x_i$
$b = \sum_{i=1}^{n} \alpha_i y_i$
其中， $\alpha_i \geq 0, i=1,2,...,N$

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

输入：数据集 $T=\lbrace (x_1,y_1),(x_2,y_2),...,(x_N,y_N) \rbrace$ ,其中 $x_i \in X = R^n$ , $y \in Y = \lbrace +1, -1 \rbrace$ , $i=1,2,..,N$ ，学习率 $\eta(0<\eta\leq1)$
输出： $w,b$ ,感知机模型 $f(x)=sign(\sum_{j=1}^{N} \alpha_j y_j x_j \cdot x + b)$
(1) $\alpha \leftarrow 0, b \leftarrow 0$
(2)训练集中选取数据 $(x_i,y_i)$
(3)如果： $y_i( \sum_{j=1}^{N} \alpha_j y_j x_j \cdot x + b ) \leq 0$
$\alpha_i \leftarrow \alpha_i + \eta$
$b \leftarrow b + \eta y_i$
(4)转至(2)，直到没有误分类的数据。

案例2.2：

import numpy as np

def perceptron_dual(x_input,y_input,gram):
    alpha_star = np.zeros(y_input.shape[0]) # alpha矩阵,x_input为n行矩阵
    b_star     = 0
    learning_rate = 1
    classification_right_count = 0 # 正确分类计数
    while True:
        for i in range(x_input.shape[0]):
            y = y_input[i]
            # 判断是否满足条件
            value = (np.sum(gram[i]*(alpha_star*y_input)) + b_star)
            if y*value <= 0:
                alpha_star[i] += learning_rate
                b_star += y
                print("update , alpha =", alpha_star)
                print("update , b_star = ",b_star)
            else:
                classification_right_count += 1
        # 若都已经分类正确，则退出
        if classification_right_count >= y_input.shape[0]: # y_input,行
            print("end, alpha = ",alpha_star)
            print("end, b_star = " , b_star)
            break
        # 否则，继续循环
        else:
            classification_right_count = 0

# 1.准备数据
data_coord = np.asarray(((3, 3), (4, 3), (1, 1)))
data_label = np.asarray((1, 1, -1))
# 2.计算gram矩阵
x = np.asarray([data_coord[0],data_coord[1],data_coord[2]])
gram = np.matmul(x,x.T)
print("gram = ",gram)
# 3.感知机 对偶形式求解
perceptron_dual(data_coord,data_label,gram)

参考与致谢：
[1]《统计学习方法》
[2]感知机算法原理与实现
[3]WenDesi/lihang_book_algorithm

机器学习 - 感知机

1.感知机模型

1.1感知机定义

2.感知机学习策略

2.1 数据集的线性可分性

2.2感知机的学习策略

2.3 感知机学习算法

2.3.1 感知机学习算法的原始形式

算法2.1（感知机学习算法的原始形式）###

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

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

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

机器学习