前言

如果你能找到这里，真是我的幸运~这里是蓝白绛的学习笔记，本集合主要针对《统计学习方法》这本书，主要是基本机器学习算法代码实现的解读。
本集合中的代码整理来自github：黄海广《统计学习方法》代码实现
本篇整理感知机实现，代码原作者github：wzyonggege《统计学习方法》笔记-基于Python算法实现

第二章感知机

1、模型定义

感知机模型： $f(x) = {\rm sign}(w*x + b),$
其中 $w*x+b$ 的值域是实数域 $R$ ， ${\rm sign}$ 是符号函数。
损失函数： $L(w, b) = -\sum_{x_i\in M}{y_{i}(w*x_{i} + b)},$
其中 $M$ 是误分类点集合，感知机学习算法是误分类点驱动的。这里的 $y_i$ 主要起取符号的作用，和式外面带上负号是因为误分类点与 $y_i$ 的乘积一定为负，而损失函数最好为正。

2、模型训练

学习算法原始形式：采用随机梯度下降法，假设误分类点集合 $M$ 是固定的，则损失函数 $L(w, b)$ 的梯度为 $\nabla_wL(w,b)=-\sum_{x_i\in M}y_ix_i$ $\nabla_bL(w,b)=-\sum_{x_i\in M}y_i$ 根据 $y_i(w\cdot x_i+b)\leq0$ 是否成立，随机选取误分类点 $(x_i,y_i)$ ，则 $w$ 和 $b$ 的更新公式为： $w\leftarrow w+\eta y_ix_i$ $b\leftarrow b+\eta y_i$ 其中 $\eta\in(0,1]$ 为学习率。
算法收敛性：对于线性可分数据集，感知机学习算法原始形式收敛，即经过有限次迭代可以得到一个将训练数据集完全正确划分的分离超平面及感知机模型。(书中31页有证明)
学习算法对偶形式：从 $w$ 和 $b$ 的更新公式中可看出， $w$ 和 $b$ 关于 $(x_i,y_i)$ 的增量分别是 $\alpha_iy_ix_i$ 和 $\alpha_iy_i$ ，即 $w$ 和 $b$ 可以分别表示为 $w=\sum_{i=1}^N\alpha_iy_ix_i$ $b=\sum_{i=1}^N\alpha_iy_i$ 其中 $\alpha_i\geq0$ ， $\alpha_i$ 等于 $\eta$ 乘以因点 $(x_i,y_i)$ 误分类而更新的次数。也就是说，每次点 $(x_i,y_i)$ 被误分类，则 $\alpha_i$ 增加一个 $\eta$ 。
根据 $y_i(\sum_{j=1}^N\alpha_jy_jx_j\cdot x_i+b)\leq0$ 是否成立，随机选取一个误分类点 $(x_i,y_i)$ ，则更新公式为： $\alpha_i\leftarrow\alpha_i+\eta$ $b\leftarrow b+\eta y_i$ 其中 $\eta\in(0,1]$ 为学习率。

注：这里为什么将 $w$ 替换成了 $\alpha_i$ ，而 $b$ 未替换，原因是 $b=\sum_{i=1}^N\alpha_iy_i$ ，也就是说 $b$ 能由 $\alpha$ 计算出来。既然能计算出来，为什么更新公式还要两个，原因是 $b$ 要及时更新，才能继续判断后面的点是否误分类。这里非常巧妙的是从 $b=\sum_{i=1}^N\alpha_iy_i$ 可看出，如果此时点 $(x_i,y_i)$ 误分类，那么只要将 $b$ 在原基础上增加 $\eta y_i$ 就行，而不是全部重新计算 $\sum_{i=1}^N\alpha_iy_i$ 。
并且，通常我们将 $b$ 也看成 $w_0$ ，将 $b$ 对应的 $x_0$ 的值令为1，更新了 $w$ 也就更新了 $b$ 。 $b$ 在原基础上增加 $\eta y_i$ ，也就是 $w_0$ 在原基础上增加了 $\eta y_i\cdot 1$ 。

对偶形式中，训练实例仅以内积的形式出现，可以预先将训练集实例间的内积计算出来并以矩阵的形式存储，这个矩阵就是Gram矩阵。 $G=[x_i\cdot x_j]_{N\times N}$

3、代码实现

这里只解读最关键的模型实现代码，完整的源代码由作者github：wzyonggege《统计学习方法》笔记-基于Python算法实现所编写，这里略去了iris数据准备等代码。该代码实现的是感知机学习算法的原始形式，我在原始代码的基础上进行了一定修改，测试通过。

class Model:
    def __init__(self):
        self.w = np.ones(len(data[0])-1, dtype=np.float32)# 初始化w参数为1
        self.b = 0
        self.l_rate = 0.1# 将学习率设置为0.1
        
    # sign函数主要用于后面判断点是否被误分类，不需要取符号，只计算w*x+b即可
    def sign(self, X):
        y = np.dot(X, self.w) + self.b
        return y
    
    # 原始代码中没有实现score方法，为实现score方法我添加了predict函数，在sign函数的基础上添加了取符号的过程
    def predict(self, X):
        y = np.dot(X, self.w) + self.b
        return 1 if y>0 else -1
    
    # 随机梯度下降法
    def fit(self, X_train, y_train):
        # 原始代码中这里本来是is_wrong = False，我觉得改成has_wrong = True比较好理解
        # 意为数据集中是否还有误分类的点，初始我们认为一定有误分类点，将has_wrong设置为True
        has_wrong = True
        while has_wrong:# 原始代码这里是while not is_wrong:，循环的主要功能是一直更新w和b，直到数据集中再没有误分类点
            wrong_count = 0# 每轮循环统计此次循环内的误分类点个数
            for d in range(len(X_train)):
                X = X_train[d]# 取一个点
                y = y_train[d]
                if y * self.sign(X) <= 0:# 如果该点是误分类点，则更新参数，并将wrong_count加一
                    self.w = self.w + self.l_rate*np.dot(y, X)# w <- w + learning_rate * np.dot(y_i * x_i)
                    self.b = self.b + self.l_rate*y# b <- b + learning_rate * y_i
                    wrong_count += 1
            if wrong_count == 0:# 直到该轮误分类点数为0，则将has_wrong设置为False，跳出循环
                has_wrong = False# 原始代码是is_wrong = True
            print('w =',self.w, 'b =',self.b)
        return 'Perceptron Model Done!'
        
    # 评价模型性能
    def score(self, X_test, y_test):
        count = 0# 用count来统计预测对的点的个数
        for d in range(len(X_test)):
            X = X_test[d]
            y = y_test[d]
            if y == self.predict(X):
                count += 1
        return count/len(X_test)

总的来说，fit()方法将整个数据集一次次进行遍历，每发现一个误分类点，则更新 $w$ 和 $b$ ，直到没有误分类点为止。

结尾

如果您发现我的文章有任何错误，或对我的文章有什么好的建议，请联系我！如果您喜欢我的文章，请点喜欢~*我是蓝白绛，感谢你的阅读！

机器学习｜感知机代码实现解读

机器学习｜感知机代码实现解读

前言

第二章感知机

1、模型定义

2、模型训练

3、代码实现

结尾

推荐阅读更多精彩内容

机器学习｜感知机代码实现解读

前言

第二章 感知机

1、模型定义

2、模型训练

3、代码实现

结尾

推荐阅读更多精彩内容

第二章感知机