误分类点

设一个点 $\vec x$ 被误分类了 $n$ 次，则由于 $\nabla L=<\vec xy,y>$，更新了 $n$ 次后的 $\vec w$ 为：

$\begin{aligned}\vec w&=\alpha n\vec xy\end{aligned}$

对所有的点来说：

$\begin{aligned}\vec w&=\sum\alpha n_i\vec x_iy_i\end{aligned}$

所以当 $(\sum\alpha n_i\vec x_iy_i\vec x_j+b)y_j<0$ 时，$\vec x_j$ 就是误分类点。

为了简化计算，我们可以将 $\vec x_i\vec x_j$ 预先取出，形成一个矩阵，这样可以免去重复的计算。

更新权重项与偏置项

由于 $n$ 代表一个点被误分类的次数，所以每次找到误分类点后，只需要 $n+1$ 即相当于更新了权重项。或者简化一下，设 $a=\alpha n$ 则每次更新时只需要：

$\begin{aligned}a&+=\alpha\\b&+=\alpha y_i\end{aligned}$

模板：

import numpy as np

X_train = np.array([[1, 1], [1, 0], [0, 1], [0, 0]])
Y_train = np.array([1, 1, 1, -1])

class perceptron:
    def __init__(self, X, Y, Alpha = 0.01):
        self.alpha = Alpha
        self.X_trn = np.array(X)
        self.Y_trn = np.array(Y)
        self.B = np.random.rand()
        self.lenth = len(self.X_trn)
        self.a = np.zeros(self.lenth)
        
        self.mat = np.zeros((self.lenth, self.lenth))
        for i in range(self.lenth):
            for j in range(self.lenth):
                self.mat[i, j] = np.dot(self.X_trn[i], self.X_trn[j])

    def check(self, j):
        Sum = np.dot(self.a * self.Y_trn, self.mat[j]) + self.B
        if (Sum * self.Y_trn[j] >= 0):
            return True
        else:
            return False

    def Loss_func(self, j):
        self.a[j] += self.alpha
        self.B += self.alpha * self.Y_trn[j]

    def train(self):
        Error = True
        k = 0
        while (Error):
            Error = False
            for i in range(self.lenth):
                if (self.check(i) == False):
                    self.Loss_func(i)
                    Error = True
        print(self.a)
        print("W: ", np.dot(self.a * self.Y_trn, self.X_trn), " B: ", self.B)

per = perceptron(X_train, Y_train, 0.01)
per.train()