机器学习复习笔记之感知机

2019-04-01 约 1908 字预计阅读 4 分钟次阅读

感知机可以说是最古老的分类方法之一了，在1957年就已经提出。今天看来它的分类模型在大多数时候泛化能力不强，但是它的原理却值得好好研究。因为研究透了感知机模型，学习支持向量机的话会降低不少难度。同时如果研究透了感知机模型，再学习神经网络，深度学习，也是一个很好的起点。因此，本文作为复习笔记，记录感知机的理论知识。

感知机模型

感知机的思想很简单，对于二元分类问题，感知机的模型就是尝试找到一条直线，能够把两个分类隔离开。放到三维空间或者更高维的空间，感知机的模型就是尝试找到一个超平面，能够把所有的二元类别隔离开。如果能够找到分界线或者是分界面，那么称数据是线性可分的，如果找不到分界面或者分界线，那么称数据是线性不可分的。也就意味着感知机模型不适合你的数据的分类。使用感知机一个最大的前提，就是数据是线性可分的，这严重限制了感知机的使用场景。它的分类竞争对手在面对不可分的情况时，比如支持向量机可以通过核技巧来让数据在高维可分，神经网络可以通过激活函数和增加隐藏层来让数据可分。

用数学公式来表达，假设我们有m个样本，每个样本都是n维，这些样本属于二元分类：

$$(x_1^{(0)}, x_2^{(0)}, …x_n^{(0)}, y_0), (x_1^{(1)}, x_2^{(1)}, …x_n^{(1)},y_1), … (x_1^{(m)}, x_2^{(m)}, …x_n^{(m)}, y_m) \tag{1}$$

我们的目标是学习一个映射函数（模型）：

$$f(x) = sign(w \cdot x +b) \tag{2}$$

这个函数就叫做感知机，其中，w和b是感知机模型的参数，w叫做权重，b叫做偏置。w·x 表示权重与样本特征的内积，sign是符号函数：$$sign(x)= \begin{cases} -1& {x<0}\ 1& {x\geq 0} \end{cases}$$

损失函数

上面已经定义好了感知机模型，只要确定好了模型的参数w和b,那么模型也就确定了，确定模型参数w和b，需要确定一个学习策略，即定义损失函数并且根据优化方法来最小化损失函数。

损失函数的一个自然选择是误分类点的总数，但是，这样的损失函数，对于参数w和b而言，不是连续可导的函数，不易优化，因此，损失函数的另一个选择是误分类点到分界面的总距离：

$$L(w,b) = -\frac{1}{||w||} \sum_{i = 1} ^ny_i(w\cdot x_i+b) = \sum_{i = 1} ^ny_i(w\cdot x_i+b) \tag{3}$$

分子和分母都含有w，当分子的w扩大N倍时，分母的L2范数也会扩大N倍。也就是说，分子和分母有固定的倍数关系。那么我们可以固定分子或者分母为1，然后求另一个即分子自己或者分母的倒数的最小化作为损失函数，这样可以简化我们的损失函数。在感知机模型中，我们采用的是保留分子，忽略分母。

优化方法

损失函数的优化方法有很多，比如：牛顿法、拟牛顿法、梯度下降法等等。感知机模型损失函数的优化方法采用的是梯度下降法。但是用普通的基于所有样本的梯度和的均值的批量梯度下降法（BGD）是行不通的，原因在于我们的损失函数里面有限定，只有误分类的M集合里面的样本才能参与损失函数的优化。所以我们不能用最普通的批量梯度下降,只能采用随机梯度下降（SGD）或者小批量梯度下降（MBGD）。

损失函数对于w向量的的偏导数为：\frac{\partial}{\partial w}J(w) = - \sum\limits_{x_i \in M}y^{(i)}x^{(i)}

损失函数对于w向量的梯度更新公式为：w = w + \alpha\sum\limits_{x_i \in M}y^{(i)}x^{(i)}

由于我们采用随机梯度下降，所以每次仅仅采用一个误分类的样本来计算梯度，假设采用第i个样本来更新梯度，则简化后的w向量的梯度下降迭代公式为：$w = w + \alpha y^{(i)} x^{(i)}$

其中α为步长也可以称之为学习率，$y^{(i)}$为样本输出1或者-1，$x^{(i)}$为(n+1)x1的向量。

算法流程

假设我们有如下的m个样本，$$(x_1^{(0)}, x_2^{(0)}, …x_n^{(0)}, y_0), (x_1^{(1)}, x_2^{(1)}, …x_n^{(1)},y_1), … (x_1^{(m)}, x_2^{(m)}, …x_n^{(m)}, y_m)$$

每个样本有n个特征，每个样本对应的输出值为：-1或1.

算法的执行步骤如下：

定义所有$x_0$为1。选择θ向量的初值和步长α的初值。可以将θ向量置为0向量，步长设置为1。要注意的是，由于感知机的解不唯一，使用的这两个初值会影响θ向量的最终迭代结果。

在训练集里面选择一个误分类的点$(x_1^{(i)}, x_2^{(i)}, …x_n^{(i)}, y_i)$, 用向量表示即$(x^{(i)}, y^{(i)})$,这个点应该满足：$y^{(i)}\theta \bullet x^{(i)} \leq 0$

对θ向量进行一次随机梯度下降的迭代：$w = w + \alpha y^{(i)} x^{(i)}$

检查训练集里是否还有误分类的点，如果没有，算法结束，此时的θ向量即为最终结果。如果有，继续第2步。

算法对偶形式

参考知乎

算法实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


# 数据线性可分，二分类数据
# 此处为一元一次线性方程
class myModel:
    def __init__(self,lr = 0.001):
        self.lr = lr
        
    def sign(self, x, w, b):
        y = np.dot(x, w) + b
        return y
        # 随机梯度下降法
    def fit(self, X_train, y_train):
        X_train = np.mat(X_train)
        m,n = np.shape(X_train)
        self.w = np.ones((n,1))
        self.b = np.zeros(1)
        is_wrong = False
        while not is_wrong:
            wrong_count = 0
            for d in range(m):
                X = X_train[d]
                y = y_train[d]
                if y * self.sign(X, self.w, self.b) <= 0:
                    # 注意shape要匹配
                    self.w = self.w + self.lr * np.dot(X.T,y)
                    self.b = self.b + self.lr*y
                    wrong_count += 1
            if wrong_count == 0:
                is_wrong = True
        return 'Perceptron Model!'
    
    def predict(self):
        pass
    def score(self):
        pass
      
      
perceptron = myModel(0.01)
perceptron.fit(X, y)
perceptron.w,perceptron.b
# (matrix([[ 0.237],
#         [-0.249]]), array([-0.26]))

算法小结

感知机算法是一个简单易懂的算法，自己编程实现也不太难。它是很多算法的鼻祖，比如支持向量机算法，神经网络与深度学习。

目录