机器学习基石

机器学习 感知机

---

1. 基本符号定义
   
2. 学习模型
   
3. 推导
   数据集的线性可分性
   给定一个数据集$T=\{(x_1,y_1), (x_2, y_2), ... (x_N, y_N)\}$, 其中$x_i \in R^{n}, y_i \in \{+1, -1\}, i=1,2,...N$, 如果存在某个超平面S，存在$w * x + b = 0$ 将数据集的正实例点和负实例点完全分开，则称该数据集线性可分。
   符号定义
   损失函数$L(w,b)=-\sum_{x_i \in M}y_i(w*x_i+b)$
   使用梯度下降法进行求解
   $$\bigtriangledown_wL(w,b)=-\sum_{x_i \in M}y_i*x_i$$
   $$\bigtriangledown_bL(w,b)=-\sum_{x_i \in M}y_i$$
   则$w, b$的更新公式为
   $$w \gets w + \eta y_ix_i$$
   $$b \gets b + \eta y_i$$
   其中$\eta$为学习率learning rate
   证明该算法是收敛的，即通过有限步N的迭代，能找到$w,b$将数据集正负实例分开
   证明：
   
   • 存在满足条件的$||\hat{w}_{opt}||=1$的超平面$\hat{w}_{opt} * \hat{x} = w_{opt} * x + b_{opt} = 0$将数据正确分开：且存在$\gamma>0$, 对所有$i=1,2,...N$
     $$y_i(\hat{w}_{opt} * \hat{x}_i) = y_i(w_{opt} * x_i + b_{opt}) \geq \gamma$$
     可知对于任意$i=1,2,...N$, $y_i(\hat{y}_{opt} * \hat{x}_i) = y_i(w_{opt} * x_i + b_{opt}) > 0$
     则存在$\gamma = \min_i\{y_i(w_{opt} * x_i + b_{opt})\} > 0$
     即$y_i(\hat{y}_{opt} * \hat{x}_i) = y_i(w_{opt} * x_i + b_{opt}) \geq \gamma$
   • 令$R = \max_{(1 \leq i \leq N)}||\hat{x_i}||$, 则训练集上的误分类次数满足
     $$k \leq {(\frac{R}{\gamma})}^2$$
     对于第K个误分类的实例，存在
     $$y_i(\hat{w}_{k-1}*\hat{x}_i) = y_i(w_{k-1}*x_i+b_{k-1}) \leq 0$$
     则w针对该错误的分类实例的更新为
     $$w_k \gets w_{k-1} + \eta y_i x_i$$
     $$b_k \gets b_{k-1} + \eta y_i$$
     $$\hat{w}_k = \hat{w}_{k-1} + \eta y_i \hat{x}_i$$

则公式<1>

$$\hat{w}_i * \hat{w}_{opt} = \hat{w}_{k-1} * \hat{w}_{opt} + \eta y_i \hat{w}_{opt} * \hat{x}_{i} \geq \hat{w}_{k-1} * \hat{w}_{opt} + \eta \gamma$$
可得 $$\hat{w}_k * \hat{w}_{opt} \geq k \eta \gamma$$

又可得公式<2>

$${||\hat{w}_{k}||}^2 = {||\hat{w}_{k-1}||}^2 + 2 \eta y_i \hat{w}_{k-1} * \hat{x}_{i} + {\eta}^2 {||\hat{x}_i||}^2 \leq {||\hat{w}_{k-1}||}^2 + {\eta}^2R^2 \leq k {\eta}^2 R^2$$

由<1><2>可得

$$k^2 {\eta}^2 {\gamma}^2 \leq k {\eta}^2 R^2$$
$$k \leq {(\frac{R}{\gamma})}^2$$
4. 代码实现

#!/usr/bin/python
# coding: utf-8
import numpy as np
DATA_PATH = r"C:\Users\Administrator\PycharmProjects\learn_machine_learning\perceptron\dataset\data.dat"
def init():
    data = np.loadtxt(DATA_PATH)
    X = data[:,0:-1]
    y = data[:,-1]
    return X, y
class Perceptron(object):
    def __init__(self, w_shape, learning_rate=0.01):
        self.w = np.random.rand(w_shape[1], w_shape[0])
        self.b = np.random.rand(1)
        self.learning_rate = learning_rate
    def fit(self, X, y):
        while True:
            w, b = np.copy(self.w), np.copy(self.b)
            count = 0
            for i in range(len(X)):
                if y[i] * ((np.dot(w, X[i])) + b) < 0:
                    count += 1
                    self.w += self.learning_rate * y[i] * X[i]
                    self.b += self.learning_rate * y[i]
            if count == 0: break
    def predict(self, x):
        return 1 if self.w * x + self.b > 0 else -1
def main():
    X, y = init()
    perceptron = Perceptron((X.shape[1], 1))
    perceptron.fit(X, y)
    print(perceptron.w, perceptron.b)
if __name__ == "__main__":
    main()

参考资料：
1. 统计学习方法-李航
2. 机器学习基石课程-林轩田