机器学习之感知机模型（Perceptron）

前言： 学习笔记，记录下对于一些问题的记录和理解，复习和加深记忆用，挖坑补坑用。

参考：李航 《统计学习方法》

0. 基本内容

感知机(perceptron)是用于二分类的一种线性分类器，是支持向量机(support vector machines, SVM)和神经网络(neural network, NN)的基础。

1. 问题及理解

• 判别模型与生成模型

  • 挖坑

• 超平面

  • 严格定义是从n维空间到n-1维空间的一个映射子空间。子空间具体定义可参考线性代数，子空间有一个性质为必经过原点，因为根据定义子空间具有减法封闭性，所以一个向量减去本身也应属于子空间。

    所以，感知机中所说的超平面实际上是仿射超平面，由超平面通过一定平移得到。形如 $w·x + b = 0$w⋅x+b=0 。一般w和x会表示为列向量，所以一般会将上述w写作转置形式 $w^T$wT。

    通过定义可以知道，超平面其实就是得到一个降维的线性空间，可将原空间分割成两部分。即 $w·x + b >0$w⋅x+b>0 部分和 $w·x + b < 0$w⋅x+b<0 部分。具体可参考对于三维空间，超平面（其实此时就是平面）就是一个平面，形如 $a_1x_1 + a_2x_2 + b = 0$a1​x1​+a2​x2​+b=0，就是我们常见的平面方程。二维空间就对应于线，一维空间就对应于点。

• 超平面 $w·x + b = 0$w⋅x+b=0 的法向量为w，截距为b

  • 法向量为w比较好理解和证明。可以参考三维空间的平面，对于一个平面 $w = [a_1,a_2]$w=[a1​,a2​](为保持一致，也未用转置形式)，线性方程为a_1x_1 + a_2x_2 + b = 0，法向量就是 $[a_1,a_2]$[a1​,a2​]。

    对于截距为b，不知是否因为有专门定义。对于我们常见的二维或者三维空间中，截距一般都会附加比如x轴截距，y轴截距等。事实上，对于超平面而言，其与轴的截距一般都不为b，其值为 b与对应轴系数除法的相反数。另一方面，考虑原点到超平面的距离，其实也不为b，其值为 $-\frac{b}{||w||}$−∣∣w∣∣b​。如果对系数进行平方和归一化，此时为b。

• 误分类点到超平面的总距离为 $-\frac{1}{||w||}\sum_{x_i\in M}y_i(w·x_i + b)$−∣∣w∣∣1​∑xi​∈M​yi​(w⋅xi​+b)，而损失 函数省略掉了 $\frac{1}{||w||}$∣∣w∣∣1​ 的合理性

  • 对于感知机模型来说，记总距离D(w,b) = $-\frac{1}{||w||}\sum_{x_i\in M}y_i(w·x_i + b)$−∣∣w∣∣1​∑xi​∈M​yi​(w⋅xi​+b)，则总有D>=0，我们优化该模型的方法就是 min(D)，也即是通过调整w和b，使得 D=0。

    而对于省略掉 $\frac{1}{||w||}$∣∣w∣∣1​ 的 L(w,b) = $-\sum_{x_i\in M}y_i(w·x_i + b)$−∑xi​∈M​yi​(w⋅xi​+b)，同样L >=0，如果min(L)，事实上，也是通过调整w和b值，使得 L=0。此时L=0，也就等价于D=0，即也完成了上述D的优化，因此两者是等价的。忽略掉 $\frac{1}{||w||}$∣∣w∣∣1​ 对结果没有影响。

• 损失函数$L(w,b) = - \sum_{x_i\in M}y_i(w·x + b)$L(w,b)=−∑xi​∈M​yi​(w⋅x+b)从直观上讲，随着w,b变化，误分类点会逐渐减少，即损失函数会经历从考虑某点到忽略某点过程，有一个“突变”过程，但实际上 $L(w,b)$L(w,b) 是w,b的连续可导函数。

  • 从直观上来看，对于一个点从考虑到不考虑，反映到函数变化上，似乎是有一个“突变过程”。但实际上，对于误分类点的考虑到不考虑过程也是一个循序渐进的过程。对于损失函数 L(w,b)，考虑随着w,b的变化，对于一点 p（x_1, x_2）从误分类到正确分类的过程（即从考虑到不考虑）。L(w,b)之所以没有阶跃式的跳跃，在于随着w，b的变化，L(w,b)中关于点p的项，即点p到超平面的距离是慢慢减为0的，当较少到0时，也即实现了p点从考虑到不考虑的转化。该过程是连续的。因此 $L(w,b)$L(w,b) 是w,b的连续可导函数。

• 感知机学习算法的对偶形式以及对偶形式为何比普通形式计算起来效率高

  • 此对偶形式和拉格朗日对偶不是同一概念。

    考虑原始形式下的整个w的变化过程，$w \leftarrow w + \eta x_i y_i$w←w+ηxi​yi​，如果初始w=0， 那么经过数次迭代后，最终的w可以写成 $w = \sum_{i=1}^{N} n_i \eta_i x_i y_i$w=∑i=1N​ni​ηi​xi​yi​的形式，理论上，式子中i取值仅为误分类点的i取值，但我们可以考虑全部点，只需要将正确分类的点的$n_i$ni​ 考虑为0即可，也即该点参与迭代了 $n_i=0$ni​=0 次，同时因为 $\eta$η 为定值，令 $\alpha_i = n_i \eta$αi​=ni​η 这样就可以把w写作为 $w = \sum_{i=1}^{N} \alpha_i y_i x_i$w=∑i=1N​αi​yi​xi​，只需调整 $\alpha_i$αi​ 即可。同理可知 $b = \sum_{i=1}^{N} \alpha_i y_i$b=∑i=1N​αi​yi​。

    对于计算效率高的问题，明显的一点是体现在对于误分类点的判别。对于原始形式，感知机模型 $f(x) = sign(w·x + b)$f(x)=sign(w⋅x+b); 对于对偶形式，感知机模型 $f(x) = sign(\sum_{j=1}^{N} \alpha_j y_j x_j ·x + b)$f(x)=sign(∑j=1N​αj​yj​xj​⋅x+b)。原始形式下，每次都要计算向量相乘 w·x值，而对于对偶形式，展开式中x_i·x_j 可以预先保存，从而不必要每次都进行重新计算。

• 感知机不能表示异或：因为异或是线性不可分的。

• 感知机学习算法的收敛性

  • 挖坑

2. 具体实例和算法实现

• 具体实例

正样本点：(3,3), (4,3), (5,2), (1.1,1.1), (4,4)
负样本点：(1,1), (-1,0)
用感知机学习算法求解感知机模型。

• 代码实现

import numpy as np
import matplotlib.pyplot as plt

class perceptron:
	def __init__(self, x, y, r):
		self.x = np.array(x)
		self.y = np.array(y)
		self.w = np.zeros(shape = (1, self.x.shape[-1]))
		self.b = 0
		self.r = r

	def fit(self):
		sig = 1
		while(sig):
			for i,x_data in enumerate(self.x):
				if(self.y[i] * (np.dot(self.w, x_data.T) + self.b) <=0):
					self.w = self.w + self.r * self.y[i] * x_data
					self.b = self.b + self.r * self.y[i]
					break
				elif( i == len(self.x)-1):
					sig = 0

	def model(self):
		# print("w:", self.w)
		# print("b:", self.b)
		return self.w,self.b

def main():
	x_data = [[3,3], [4,3], [5,2], [1,1], [1.1, 1.1], [-1,0], [4,4]]
	y_label = [1, 1, 1, -1, 1, -1, 1]
	learning_rate = 1
	
	fig = plt.figure()
	plt.plot(np.array(x_data)[:, 0], np.array(x_data)[:, 1], 'o')
	#plt.show()

	p = perceptron(x_data, y_label, learning_rate)
	p.fit()
	w,b = p.model()
	print("w:",w)
	print("b:",b)

	x = np.arange(5)
	y = -w[0][0]/float(w[0][1]) * x - b/float(w[0][1])
	plt.plot(x, y)
	plt.show()

if __name__ == '__main__':
	main()

结果展示：