机器学习基石笔记 感知机

损失函数

给定一个数据集 $T ={(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)}$ , 其中 $x = R^n , , y={+1,-1}$

若存在超平面S $w\cdot x + b = 0$ 能将所有的正负实例点分到两侧，则称数据集是线性可分的，否则称线性不可分。
任意一点$x_0$到超平面的距离为
$$\frac{1}{||w||}|w\cdot x_0 + b|$$
对于误分类数据$(x_i,y_i)$来说，
$-y_i(w\cdot x_i + b) > 0$

有误分类点到超平面距离
$$-\frac{1}{||w||}y_i|w\cdot x_0 + b|$$

则所有误分类点到超平面距离为
$$-\frac{1}{||w||}\sum_{x_i \in m }y_i|w\cdot x_0 + b|$$

所以感知机$sign(w\cdot x + b)$学习损失函数为
$$L(w,b) = -\sum_{x_i \in m }y_i|w\cdot x_0 + b|$$

学习算法

1. 选取初值$w_0,b_0$

2. 在训练集中选取数据$(x_i,y_i)$

3. 如果$y_i(w\cdot xi+ b) \leq 0$（分类错误）
   $$w \leftarrow w + x_iy_i$$

4. 转至2，直至没有误分类点。

收敛性

令$R=\max || x_i || $ ，
令$\rho = \min \frac{W_f}{||W_f||}x_iy_i$
则有修正次数
$$k \leq \frac{R^2}{\rho ^2}$$

下面给出证明。
由
$$W_k \cdot W_f = W_{k-1} W_f + x_i y_i \geq W_{k-1} + \rho \geq \cdots \geq k \rho$$

得
$$||w_k||^2=||w_{k-1} + x_i y_i||^2=||w_{k-1}||^2 + 2w_{k-1}x_iy_i+||x_iy_i||^2 \leq ||w_{k-1}||^2 +||x_iy_i||^2 \leq ||w_{k-1}||^2 + R^2$$

故
$$||w_k||^2\leq ||w_{k-1}||^2 + R^2 \leq \cdots \leq kR^2$$

故
$$k \rho \leq w_k\cdot w_f \leq ||w_k|| \cdot ||w_f|| \leq ||w_k|| \leq \sqrt k R$$

故 $k \rho \leq \sqrt k R$,易得$k \leq \frac{R^2}{\rho ^2}$，得证。

其他性质

1. 一般用加上速度后的修正式：$ w \leftarrow w + \eta \cdot x_iy_i$ 来修正直线。
2. 读入数据的次序是影响修正次数的。

示范代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

	import numpy as np

	def sign(x):
		if x < 0:
			return -1
		else:
			return 1

	w = np.array([0.,0.,0.,0.,0.])
	halts = 0
	speed = 1
	f = open('pla.dat')

	while True:
		data = f.readline()
		if data == '':
			break
		datas = data.split('\t')
		xi = np.array([float(i) for i in ('1 ' + datas[0]).split()])
		yi = float((datas[1].split())[0])
		if not abs(yi) == 1 :
			exit(1)
		if not sign(np.inner(w,xi)) == yi:
			w = w + speed * yi * xi
			print("W: " + str(w))
			halts += 1
		
	print('Halts :' + str(halts))