统计学习方法（二）：感知机

学习目标：

1.掌握感知机的模型形式、损失函数及对应的优化问题。

损失函数推导过程：


最终优化函数：

                min L(w,b)

2.掌握随机梯度下降算法原理。

推导过程：

3.理解感知机模型中随机梯度算法的收敛性。

习题：

1.思考感知机模型假设空间是什么？模型复杂度体现在哪？

假设空间 {f|f=wx+b}，即特征空间中的所有线性分类器。模型的复杂度主要体现在实例特征向量的维度d上或者特征数量上。

2.已知训练数据集D，其正实例点是x1=(3,3)T,x2=(4,3)T，负实例点是x3=(1,1)T:

(1) 用python 自编程实现感知机模型，对训练数据集进行分类，并对比误分类点选择次序不同对最终结果的影响。可采用函数式编程或面向对象的编程。

import numpy as np
class Perceptron:
    def __init__(self, x, y, n, eta):
        self.x = x  # 实例点
        self.y = y  # 实例点的分类
        self.n = n  # 实例点个数
        self.eta = eta  # 学习率

    # 随机梯度下降法
    def SGD(self):
        # 对w,b取初值
        w = np.array([0, 0])
        b = 0
        # 记录一次迭代是否有误分类点
        flag = 1
        while flag == 1:
            flag = 0
            for i in range(n):
                # 如果有误分类点
                if self.y[i] * (w.dot(self.x[i]) + b) <= 0:
                    # 更新w,b，设置flag为1
                    w = w + self.eta * self.y[i] * self.x[i]
                    b = b + self.eta * self.y[i]
                    flag = 1
        return w, b
if __name__ == "__main__":
    x = np.array([[3, 3], [4, 3], [1, 1]])
    y = np.array([1, 1, -1])
    n = 3
    eta = 1

    perceptron = Perceptron(x, y, n, eta)
    w, b = perceptron.SGD()
    print("模型参数w:", w, "b:", b)

模型参数w: [1 1] b: -3

(2)试调用sklearn.linear_model 的Perceptron模块，对训练数据集进行分类，并对比不同学习率h对模型学习速度及结果的影响。

from sklearn.linear_model import Perceptron
import numpy as np

X = np.array([[3, 3], [4, 3], [1, 1]])
Y = np.array([1, 1, -1])

perceptron = Perceptron()
# fit用于训练数据集
perceptron.fit(X, Y)
# coef_:权重w,intercept_:b,n_iter:迭代次数
print("w:", perceptron.coef_, "\n", "b:", perceptron.intercept_, "\n", "n_iter:", perceptron.n_iter)

# score用来评价训练效果
res = perceptron.score(X, Y)
print("correct rate:{}".format(res))

w: [[1. 0.]] 
 b: [-2.] 
 n_iter: None
correct rate:1.0

(3)附加题：对比传统感知机算法及其对偶形式的运行速度。

样本数	N
特征维度	d

原始形式的复杂度：O(d)
对偶形式的复杂度：O(N)
故，样本量较大时使用原始形式；特征维度较大时，使用对偶形式。