感知机-Perceptron

感知机的直观感受

感知机是机器学习中的最基本也是最简单的一个算法。下图就是一个例子。

例如，我们有一个二维数据，横轴为$X_1$, 纵轴为$X_2$。图中有黄蓝红三条直线，都可以将两簇数据完美划分。其实，这三条直线就是感知机的分割线。如果数据是n维的，那就是分离超平面了。

并且我们需要注意到，感知机是没有一个确定解的。因为我们的目标只是将两个数据簇分开。如果想要确定一个唯一的超平面，那需要加限制条件，这将是SVM的内容。

感知机的数学视角

对于这样一个模型，我们怎么来找到一个超平面呢？

首先，如前面所说，感知机是依靠超平面来划分数据集的。数学上，我们定义超平面为$<w, x>+b$ ，其中$w$为超平面的法向量，$b$为超平面的偏置。同时，由于我们需要通过这个超平面来划分数据，而我们的数据的标志$y\in\{-1, +1\}$, 因此我们定义函数为$f(x)=sign(<w, x>+b)​$，其中

$$\begin{align*} sign(<w, x>+b)&=\left\{ \begin{array}{lr} 1, & <w, x> + b > 0 \newline -1, & <w, x> + b < 0 \end{array} \right. \end{align*}$$

现在，我们考虑如何来确定损失函数。我们的目标是将数据点正确的划分，因此我们可以考虑数据点到超平面的距离来度量。距离公式为

$$\frac{|<w,x_i>+b|}{\left\|w\right\|}$$

考虑所有误分类点的集合$M$, 对于在$M$中的数据点，如果$<w, x_i>+b<0$, 那么$y_i=1$。反过来，如果​$<w, x_i>+b>0$, 那么​$y_i=-1$. 因此我们可以通过乘以$y_i$来去掉距离中的绝对值，因为绝对值的存在会妨碍我们优化模型。现在定义距离为

$$\frac{-y_i(<w,x_i>+b)}{\left\|w\right\|}$$

所以，我们的损失函数为

$$Loss(w, b)= \frac{-\sum_{i\in M}y_i(<w,x_i>+b)}{\left\|w\right\|}$$

考虑到我们的数据是线性可分的，最终$Loss(w, b)=0​$。因此，为了是优化更加简单，我们定义损失函数为

$$Loss(w, b)= -\sum_{i\in M}y_i(<w,x_i>+b)$$

现在，考虑如何优化损失函数。我们采用随机梯度下降法(SGD)， 首先对损失函数求导

$$\begin{align*} &\nabla_w L(w,b)= - \sum_{i\in M} y_i x_i\\ &\nabla_b L(w,b)= - \sum_{i\in M} y_i\\ \end{align*}$$

随机选择一个$(x_i, y_i)$， 更新权重

$$w\leftarrow w+\eta y_ix_i\\ b\leftarrow b+\eta y_i$$

最后进行迭代直到损失函数为0。

感知机的对偶形式

对偶形式的思想就是用$x_i和y_i​$的线性组合来表示$w和b​$。考虑在初始化参数的时候，将$w和b​$设为0，由之前的迭代算法可知，

$$w\leftarrow w+\eta y_ix_i\\ b\leftarrow b+\eta y_i$$

设总共修改了$n​$次参数，对于样本点$(x_i, y_i)​$，$w和b​$的增量分别是$\alpha_iy_i x_i和\alpha_iy_i​$, 其中$\alpha_i=n_i\eta​$。

$$w=\sum_{i=1}^n\alpha_iy_ix_i\\ b=\sum_{i=1}^n\alpha_iy_i$$

如果我们假定$\eta=0​$, 则$\alpha_i=n_i​$，即$\alpha​$表示第$i​$个实例点由于误分总共迭代更新的次数。

从中，我们可以得出，如果某个实例点更新的次数越多，它里超平面的距离也就越近，也就越难正确分类，它对最后确定的超平面的影响也就越大。

$$f(x)=sign(\sum_{i=1}^n\alpha_iy_i<x_j, x>+b)$$

其中，$\alpha_i \leftarrow \alpha_i+\eta$, 加$\eta$的原因是因为$\alpha_i=n_i\eta$。误分一次，$\alpha_i$增加一个$\eta$。

同时，由于存在实例之间内积，可以先计算Gram矩阵，存储所有的实例的之间的内积。

Python实现

import numpy as np
import pandas as pd
import time
import matplotlib.pyplot as plt

class Perceptron(object):
    
    def __init__(self, eta=0.05, n_iter=50, random_state=1):
        self.eta = eta
        self.n_iter = n_iter
        self.random_state = random_state
        self.error = 0
        
    
    def fit(self, X, y):
        rgen = np.random.RandomState(self.random_state)
        self.w = rgen.normal(loc=0, scale=0.1, size=(X.shape[1]+1))

        for k in range(self.n_iter):
            for xi, yi in zip(X, y):
                pred = np.where(np.dot(xi, self.w[1:]) + self.w[0] >=0, 1, -1)
                if yi != pred:
                    self.w[1:] += self.eta*yi*xi
                    self.w[0] += self.eta*yi
        return self

        
    def predict(self, X, y):
        for i in range(X.shape[0]):
            xi = X[i, ]
            yi = y[i]
            result = np.where(np.dot(xi, self.w[1:]) + self.w[0] >=0, 1, -1)
            if result != yi:
                self.error += 1/X.shape[0]
        return self


if __name__ == "__main__":
    df = pd.read_csv('https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data', header=None)
    df.tail()
    y = df.iloc[0:150, 4].values
    y = np.where(y == 'Iris-setosa', -1, 1)
    y_train = y[0:100]
    y_test = y[100:]
    X = df.iloc[0:150, [0, 2]].values
    X_train = X[0:100, ]
    X_test = X[100:, ]
    ppn = Perceptron(eta=0.1, n_iter=50)
    ppn.fit(X_train, y_train)
    m =ppn.predict(X_test, y_test)
    n = ppn.fit(X_train, y_train)
    print(n.error)