机器学习：感知机模型(perceptron)

简介

感知机是二类分类问题的线性分类模型，输入为实例的特征向量，输出为实例的类别，取+1和-1值

定义

假设输入空间（特征空间）是$X\in R^n$，输出空间是 Y = { − 1 , + 1 } Y = \{-1, +1\} Y={−1,+1}，输入$x\in X$表示实例的特征向量，对应与输入空间（特征空间）的点；输出$y\in Y$表示实例的类别，则由输入空间倒输出空间的如下函数:
$$f(x)=sign(w\ast x+b)$$，称为感知机

几何解释

线性方程$w\ast x+b=0$对应于特征空间$R^n$的一个超平面S（关于超平面），这个平面将特征空间分为了两个部分，将处于特征空间中的点分为了正，负两类。其中$w$是这个超平面的“斜率”，$b$是“截距”（尽管$w$和$b$都可能用向量来表示）

感知机学习策略

损失函数：$L(w,b)=-{\sum }_{x_i\in M}{y}_i(w\ast x_i+b)$，这个损失函数就是感知机学习的经验风险函数，直观上看，当一个点$x_i$是负分类的，那么$y_i(w\ast x_i+b)<0$，因为误分类点的$w\ast x_i+b$和$y_i$的符号一定是相反的。因此损失函数是非负的，误分类点越少，损失函数的值便越小。感知机的学习策略便是在训练过程中使用随机梯度下降法不断更新$w$和$b$的值，使得损失函数最小

感知机学习算法

原始形式

整个学习过程是对以下最优化问题（极小化问题）的求解：
$mi{n}_{w,b}L(w,b)=mi{n}_{w,b}{\sum }_{x_i\in M}{y}_i(w\ast x_i+b)$
先求损失函数的梯度： (倒三角的markdown代码是\nabla)
$$\begin{gathered} {\nabla }_{w}L(w,b)=-\sum _{x_i\in M}{y}_i{x}_i \\ {\nabla }_{b}L(w,b)=-\sum _{x_i\in M}{y}_i \end{gathered}$$
则整个学习的步骤是：

• 选取初值$w_0,b_0$
• 在训练集中选取误分类点$(x_i,y_i)$（判断条件$y_i(w\ast x_i+b)<=0$）
• 跟新参数$w,b$:
  $$\begin{gathered} w\leftarrow w+\eta y_i{x}_i \\ b\leftarrow b+\eta y_i \end{gathered}$$
  其中$\eta$称为学习率(learning rate)，决定学习的快慢/精确与否。
• 直到训练集中没有误分类点（不是所有情况都满足，算法提升在支持向量机）

对偶形式

在原始形式中，我们假设初始参数为$w_0=0,b_0=0$，然后通过：
$$\begin{gathered} w\leftarrow w+\eta y_i{x}_i \\ b\leftarrow +\eta y_i \end{gathered}$$
逐步修改$w,b$，假设修改了n次，则最后学习到的$w,b$ 可以分别表示为：
$$w=\sum _{i=1}^N{\alpha }_i{y}_i{x}_{i}b=\sum _{i=1}^N{\alpha }_i{y}_i$$
则对偶形式的感知机模型可以表示为：
$$f(x)=sign(\sum _{j=1}^N{\alpha }_j{y}_j{x}_j\ast x+b)$$
则判断分类错误的条件变为：
$$y_i(\sum _{j=1}^N{\alpha }_j{y}_j{x}_j\ast x_i+b)<=0$$
更新参数的方法变为：
$${\alpha }_i\leftarrow {\alpha }_i+\eta$$
$$b\leftarrow b+\eta y_i$$
这里预先将$x$的内积$x_j{x}_i$计算出来，用一个矩阵（Gram矩阵）表示，便可以加速训练过程，不用每次判断误分类的时候都计算一次内积。这里也是对偶形式的算法比原始形式更加优化的地方。
$$G_{i,j}=x_i\ast x_j$$

代码实现

github

核心代码perceptron.py

• 原始形式

import numpy as np
import pandas as pd

class Perceptron:
	def __init__(self, dimension):
		self.w = np.zeros((1, dimension))
		self.b = 0
		self.step = 0.5

	def model(self, x):
		# t_x = np.transpose(x)
		# print(t_x)
		return 1 if np.dot(self.w, x) + self.b >= 0 else -1

	def classify_fault(self, node):
		# t_x = np.transpose(node[0:2])
		return (np.dot(self.w, node[0:2]) + self.b) * node[2] <= 0

	def update(self, x, y):
		self.w = self.w + self.step * y * x
		self.b = self.b + self.step * y

	

	def learn(self, data_set):
		fault_nodes = []
		while True:
			for node in fault_nodes:
				self.update(node[0:2], node[2])
			fault_nodes[:] = []
			for node in data_set:
				if self.classify_fault(node):
					fault_nodes.append(node)
			if not fault_nodes:
				break;
	def get_parameter(self):
		return self.w[0], self.b

• 对偶形式

class Perceptron_antithesis:
	def __init__(self, data_set):
		self.b = 0
		self.step = 0.5
		self.data_set = data_set
		self.nums = data_set.shape[0]
		self.alpha = np.zeros(self.nums)
		self.G = np.zeros((self.nums, self.nums))
		for i in range(self.nums):
			x_i = self.data_set[i][0:2]
			for j in range(self.nums):
				x_j = self.data_set[j][0:2]
				self.G[i][j] = np.dot(x_i, x_j)
		self.x = self.data_set[:, 0:2]
		self.y = self.data_set[:, 2]


	def modle(self, x):
		l = [np.dot(self.x[i], x)*self.y[i]*self.alpha[i] for i in range(self.nums)]
		f_x = np.sum(l) + self.b
		return 1 if f_x >= 0 else -1

	def classify_fault(self, i):
		l = [self.alpha[j]*self.y[j]*self.G[j, i] for j in range(self.nums)]
		f_x = np.sum(l) + self.b
		return self.y[i] * f_x <= 0

	def update(self, i):
		self.alpha[i] = self.alpha[i] + self.step
		self.b = self.b + self.step*self.y[i]

	def learn(self):
		fault_nodes = []
		while True:
			for i in fault_nodes:
				self.update(i)
			fault_nodes[:] = []
			for i in range(self.nums):
				if self.classify_fault(i):
					fault_nodes.append(i)
			if not fault_nodes:
				break;
				
	def get_parameter(self):
		l_w = [self.alpha[i]*self.y[i]*self.x[i] for i in range(self.nums)]
		w = np.sum(l_w, axis=0)
		return w, self.b

数据可视化`data_view.py

import matplotlib.pyplot as plt

def draw(data_set, parameter):
	x_1 = data_set[:, 0]
	x_2 = data_set[:, 1]
	color = data_set[:, 2]
	fig = plt.figure()
	plt.scatter(x_1, x_2, c=color)

	w, b = parameter[0], parameter[1]

	#draw a classifying line
	#x_1 = 0
	t_x_2 = (-b) / w[1]
	#x_2 = 0
	t_x_1 = (-b) / w[0]

	plt.plot([0, t_x_1], [t_x_2, 0])
	plt.show()

实验效果

由于对测试的数据由限制，分类效果还算不错，生成数据的代码如下：

def get_data_set_random(num_node):
	data_set = np.random.random((num_node, 3)) * 10
	for i in range(num_node):
		data_set[i,2] = 1 if data_set[i, 0] ** 2 + data_set[i, 1] ** 2 <= 50 else -1
	return data_set

实验效果图：

MD搞了一晚上，最后发现是图画错了…