1. 基本概念

1.1 数据要求

数据线性可分，其中，输入：特征向量；输出：类别。

是一種判別模型。

1.2 基本形式

$$f(x)=sign(\mathbf{w}\cdot \mathbf{x}+b)\text{\hspace{1em}(1.1)}$$ 其中： $$sign(x)=\{\begin{array}{cc}+1& ,x\ge 0\\ -1& ,x<0\end{array}\text{\hspace{1em}(1.2)}$$

1.3 几何意义

首先，根据向量的本质可知，$\mathbf{x}$的集合$\chi$所张成了一个空间，而线性方程$\mathbf{w}\cdot \mathbf{x}+b=0$相当于在这个空间中切一刀，希望能够将不同种类的数据最大限度的分开。其中，$\mathbf{w}$是超平面的法向量，$b$是超平面的截距。

---

2. 学习策略

2.1 目标

希望能够将不同种类的数据区分开。

2.2 损失函数

使分类点到超平面的距离之和最小。

回忆一下二维坐标中点到直线的距离公式。 $$d=\left|\frac{A{X}_0+B{Y}_0+C}{\sqrt{A^2+B^2}}\right|\text{\hspace{1em}(2.1)}$$

2.2.1 思路如下：

那么，在$\mathbf{x}$的集合所张成的空间中，任意一点到该平面的距离为$-\frac{|wx+b|}{||w||}$。 图中，$-\frac{b}{||w||}$指的是点A（原点）到线性方程的距离。

在分类正确的情况下，$y_i=1$时，一定有$(\mathbf{w}\cdot {\mathbf{x}}_{\mathbf{i}}+b)>0$，或者是$y_i=-1$时：$(\mathbf{w}\cdot {\mathbf{x}}_{\mathbf{i}}+b)<0$。

但是假设第$i$个点$({\mathbf{x}}_{\mathbf{i}},y_i)$分类错误了，则有$-y_i(\mathbf{w}\cdot {\mathbf{x}}_{\mathbf{i}}+b)>0$，则误分类点到超平面的距离为$-\frac{y_i(wx+b)}{||w||}$，则$m$个分类错误的点到该超平面的距离为：$-\frac{{\sum }_{i=1}^m{y}_i(wx+b)}{||w||}$

因此，损失函数即为： $$-\sum _{i=1}^m{y}_i(wx+b)\text{\hspace{1em}(2.2)}$$

强调一点：从直观上应该使用误分类点数目最少作为其目标函数,但是由于该表达式不可导,不利于优化参数$w$和$b$,因此选取其误分类点到分离超平面的距离作为其目标函数. 根据公式可知,当误分类点越多,则损失函数值越大,误分类点越少,损失函数值越小.

---

3. 学习算法（基本形式）

3.1 基本概念

随机梯度下降算法，不是一次使$n$个误分类点梯度下降，而是一次选取一个误分类点梯度下降。 存在两个问题：往哪走与走多远的情况。

往哪走？梯度告诉你走的方向，损失函数对$w$和$b$的求导计算结果为： $$▽w_{L(w,b)}=-\sum _{x_i\in M}{y}_i{x}_i\text{\hspace{1em}(3.1)}$$ $$▽b_{L(w,b)}=-\sum _{x_i\in M}{y}_i\text{\hspace{1em}(3.2)}$$

注意:公式$(3.1)$和公式$(3.2)$中参数的更新也只是说明了该往哪个方向走

走多远？没人知道，设定一次走多远$\eta$，剩下的那就只能一小步一小步的走吧。

对于计算机来说,由于计算是串行化的,不能够像人一样一次性从中找出所有的误分类点,只能一个点一个点的去修正(每次根据一个错误点调整参数,直到没有误分类点为止). 所以,记$w_i$为第$i$次调整的结果,寻找的参数表达式在计算机中实际上是这样的: $$mi{n}_{w,b}{L}_i(w,b)=mi{n}_{w,b}{L}_{1,2,...,i-1}(w_{i-1},b_{i-1})+y_i(w_i{x}_i+b)$$

于是乎，权重与偏差的更新： $$w\leftarrow w+\eta y_i{x}_i\text{\hspace{1em}(3.3)}$$ $$b\leftarrow b+\eta y_i\text{\hspace{1em}(3.4)}$$ $\eta$为步长

3.2 小结

在基本模式中，没有什么难以理解，通俗的说就是来一个值，根据计算结果调整一下权重和偏差，如此直到线性可分的数据集中没有错误的分类选项。

---

4. 学习算法（对偶模式）

有的人嫌一小步一小步的走太麻烦，想换一个方法：你告诉我沿一个方向走多远，我一次性走完，然后再换其他的。（说白了就是一次一次的更新太麻烦，我先攒着，看看你需要更新多少次，我一口气给你全部更新完【分期付款和全款的区别】） 于是乎，对偶模式诞生了。与基本形式类似，也是通过不断调整权重和偏差来实现对数据集的分类，但是，还是有原来的两个问题：往哪走，走多远？

往哪走？这个问题没有其他的解决方式，还是和基本形式一样，梯度告诉你。走多远？在基本模式中，是站在局部视角走，现在，切换到上帝视角看一看。 The God says： 例如：有$x_1,x_2,x_3,x_4,x_5$ 5条数据，如果这5条数据仅使用一次，那是不合理的，所以你要将这5条数据进行反复的抽取，每一条数据就可以被多次使用，第$i$条数据被抽取的次数记为$n_i$。那么，从初始权重到最终训练好之后，权重经过$N$次更新后，最后会变成这个样子： $$w=\sum _{j=1}^N\eta \cdot n_j\cdot y_j\cdot x_j$$ $$b=\sum _{j=1}^N\eta \cdot n_j\cdot y_j$$ 嗯，从上面可以看出每个方向走多少步（$n_i$说明了一切：第$i$个实例点因为误分类而进行更新的次数）

因此，你需要做如下改变：

4.1 判定表达式的改变

原先$w$代表第i次更新后的结果，现在站在上帝视角可以看出，$w={\sum }_{j=1}^N\eta \cdot n_j\cdot y_j\cdot x_j$，所以，感知机模型就变成了$$f(x)=sign(\sum _{j=1}^N\eta n_j{y}_j{x}_j\cdot x+b)$$

4.2 对偶模式的权重更新方式

在基本形式中，每一次权重是这么更新的： $$w_{i+1}\leftarrow w_i+\eta \cdot y_i\cdot x_i,i\in N$$

然而，在对偶模式中，权重按照每条数据被学习的次数进行更新。对偶模式的权重更新就变成了这个样子了： $$\eta \cdot n_{j+1}\leftarrow \eta \cdot n_j+\eta =(n_j+1)\cdot \eta$$ $$b_{j+1}\leftarrow b_j+\eta \cdot y_j$$

---

4.3 Gram 矩阵

---

5. 参考文献

1.《统计学习方法》 2.理解感知机对偶形式及Gram矩阵作用 3.感知机中的对偶形式理解

---

6. python代码实现

6.1 基本模式

class Perception(object): def __init__(self, input_vecs, labels, activation, lr=0.1): ''' 感知机模型权重以及偏置项的初始化 :param input_shape: <tuple>需要输入层维度信息 :param activation: <funciton>激活函数 :param lr: <float>学习率 ''' self.input_vecs = input_vecs self.n_features = input_vecs.shape[1] self.n_nums = input_vecs.shape[0] self.activation = activation self.weight = np.zeros((1, self.n_features)) self.bias = np.zeros((1, 1)) self.lr = lr def predict(self, input_vec): ''' 输入感知机运算结果 :param input_vecs: <np.ndarray>训练数据 :return:对ndarray中的逐元素应用激活函数 ''' output = np.dot(input_vec, self.weight.T) + self.bias return np.apply_along_axis(self.activation, axis=1, arr=output) def _update_weight(self, index_nums, delta): ''' 更新权重 delta_weights = lr * (t - y) * x_i w是与x_i输入对应的权重项, t是训练样本的实际值, y是感知器的输出值，lr是学习速率 ------ :param input_vecs: <np.ndarray>训练数据 :param delta: <np.ndarray>误差项 :return: ''' delta = np.tile(delta, (self.n_features, 1)) delta_weight = np.dot(self.input_vecs[index_nums].T, delta) self.weight += delta_weight def _update_bias(self, delta): ''' 更新偏差 delta_bias = lr * (t - y) :param delta: <np.ndarray>误差项 :return: ''' self.bias += delta def forward(self, nums, labels): ''' 前向计算感知机的输出值 :param nums: 训练样例的数量 :param input_vecs: 训练样本的特征值 :param labels: 训练样本的真实值 :return: ''' for k in range(nums): print('%d th iterations' % k) for inums in range(self.n_nums): output = self.predict(input_vecs[inums]) delta = self.lr * (labels[inums] - output) self._update_weight(inums, delta) self._update_bias(delta) # print('weights;', self.weight) # print('bias;', self.bias) print('output:', self.predict(input_vecs))

6.2 对偶模式

class PerceptionDualModel(object): def __init__(self, input_vecs, labels, activation, lr=1): ''' 感知机模型权重以及偏置项的初始化 :param input_vecs: <np.ndarray>输入层的特征值 :param labels: <np.ndarray>输入层对应的标签 :param activation: <funciton>激活函数 :param lr: <float>学习率 ''' self.input_vecs = input_vecs self.labels = labels self.activation = activation # 训练集特征的数量 self.n_features = input_vecs.shape[1] # 训练集的数量 self.n_nums = input_vecs.shape[0] self.lr = lr # n_i代表第i类数据使用的次数 self.n = np.zeros((self.n_nums, 1)) self.bias = 0 # 计算Gram矩阵，为权重训练做准备 self.Gram_metrix = self.calculate_Gram() def calculate_weights(self): ''' 根据公式计算权重 weights = \sum_{i=1}^{N} n_i * lr * xi * yi :return: ''' tmp = np.multiply(self.lr * self.n, self.labels) self.weight = (np.dot(tmp.T, self.input_vecs)).T def calculate_bias(self): ''' 计算偏差 bias = \sum_{i=1}^{N} n_i * lr * yi :return: ''' self.bias = np.dot(self.lr * self.n.T, self.labels) def calculate_Gram(self): return np.dot(self.input_vecs, self.input_vecs.T) def train(self, num_index): ''' 对感知机的权重进行驯良 :param num_index: <int>输入数据的行标签，同时也意味着第几类数据 :return:对ndarray中的逐元素应用激活函数 ''' output = np.dot( self.Gram_metrix[num_index], np.multiply(self.lr * self.n, self.labels) ) + self.bias return self.activation(output) def _update_weight(self, delta, num_index): ''' 更新权重 n_i * lr = n_i * lr * + lr w是与x_i输入对应的权重项, t是训练样本的实际值, y是感知器的输出值，lr是学习速率 ------ :param delta: <np.ndarray>误差项 :param num_index: <int>输入数据的行标签，同时也意味着第几类数据 :return: ''' # if delta == 0: # print(num_index, ':分类正确') # else: # print(num_index, ':分类错误') self.n[num_index] += delta def _update_bias(self, delta): ''' 更新偏差 delta_bias = lr * y_i :param delta: <np.ndarray>误差项 :return: ''' self.bias += delta * self.lr def _predict(self, input_vec): ''' 根据特征值计算分类标签 :param input_vec: 输入特征值 :return: ''' self.calculate_weights() # print('weights;', self.weight) # print('bias;', self.bias) predict = np.dot(input_vec, self.weight) + self.bias return np.apply_along_axis(self.activation, axis=1, arr=predict) def forward(self, nums): ''' 前向计算感知机的输出值 :param nums: 训练样例的数量 :param input_vecs: 训练样本的特征值 :param labels: 训练样本的真实值 :return: ''' for k in range(nums): print('%d th iterations' % k) for num_index in range(self.n_nums): output = self.train(num_index) delta = self.labels[num_index] - output self._update_weight(delta, num_index) self._update_bias(delta) print(self._predict(input_vecs))

6.3 激活函数与训练数据获取

def activation(x): ''' 对x中的所有元素逐元素的进行操作 :param x: :return: ''' return 1 if x > 0 else 0 def getTrainData(): ''' 得到输入数据和输出数据 :return: input_vecs<ndarray>：输入数据 labels<ndarray>：标签 ''' # 构建训练数据 # 输入向量列表 # input_vecs = np.array([[1, 1], [0, 0], [1, 0], [0, 1]]) # and # labels = np.array([1, 0, 0, 0]) # or # labels = np.array([1, 0, 1, 1]) input_vecs = np.array([[3, 3], [4, 3], [1, 1]]) labels = np.array([[1], [1], [0]]) return input_vecs, labels

6.4 函数调用

if __name__ == '__main__': input_vecs, labels = getTrainData() # ================ 基本模式 ================# P = Perception(input_vecs, labels, activation, lr=1) P.forward(10, labels) print(P.predict(np.array([[8, 6]]))) # ================ 对偶模式 ================# P = PerceptionDualModel(input_vecs, labels, activation) P.forward(10) print(P._predict(np.array([[8, 6]])))

---

7. 参考文献

《西瓜书》《统计学习方法》