机器学习：感知机

[TOC]

感知器的概念

感知器（perceptron)是人工神经网络的基础单元，感知器是以一个实数值向量作为输入，计算这些输入的线性组合，然后如果结果大于某个阈值，就输出1，否则输出-1.更精确的是，如果输入为$x_1$到$x_n$，那么感知器计算的输出为：
$$
o(x_1,…,x_n) = \begin{cases}
1, & \text{ $w_0+w_1x_1+…+w_nx_n $> 0}\
-1, & \text{otherwise }
\end{cases}
$$
perceptron
其中，每一个$w_i$是一个实数常量，或者叫做权值(weight),用来决定输入$x_i$对感知器输出的贡献率。
实数$w_0$是一个阈值(threshold)，它是为了使感知器输出1，输入的加权和 $w_0+w_1x_1+…+w_nx_n$必须超过的值。

感知机是一种线性分类模型(非线性的不能分)，属于判别模型，感知机模型的假设空间是定义在特征空间中的所有线性分类模型或线性分类器，即函数集合 $\lbrace f \mid f(x) = w \cdot x + b \rbrace$。
感知机有如下几何解释：线性方程
$$ w \cdot x +b = 0 $$
对应于特征空间$R^n$中的一个超平面S,其中w是超平面的法向量，b是超平面的截距。这个超平面将特征空间划分为2个部分，每一部分是一类。

公式是这样推导出来的：

$ h(x) = sign((\sum_{i=1}^dw_ixi$) - threashold)
= $sign((\sum{i=1}^dw_ixi$) + (-threashold) $\cdot$ (+1))
= sign(($\sum{i=1}^dw_ix_i$) + $w_0x_0$)
= sign($W^T$X)

感知机的历史

1943年，心理学家 Warren McCulloch 和数理逻辑学家 Walter Pitts 在合作的《A logical calculus of the ideas immanent in nervous activity》论文中提出并给出了人工神经网络的概念及人工神经元的数学模型，从而开创了人工神经网络研究的时代。1949年，心理学家唐纳德·赫布在《The Organization of Behavior》论文中描述了神经元学习法则。

人工神经网络更进一步被美国神经学家 Frank Rosenblatt 所发展。他提出了可以模拟人类感知能力的机器，并称之为『感知机』。1957年，在 Cornell 航空实验室中，他成功在IBM 704机上完成了感知机的仿真。两年后，他又成功实现了能够识别一些英文字母、基于感知机的神经计算机——Mark1，并于1960年6月23日，展示与众。

为了『教导』感知机识别图像，Rosenblatt，在 Hebb 学习法则的基础上，发展了一种迭代、试错、类似于人类学习过程的学习算法——感知机学习。除了能够识别出现较多次的字母，感知机也能对不同书写方式的字母图像进行概括和归纳。但是，由于本身的局限，感知机除了那些包含在训练集里的图像以外，不能对受干扰（半遮蔽、不同大小、平移、旋转）的字母图像进行可靠的识别。

首个有关感知机的成果，由 Rosenblatt 于1958年发表在《The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain》的文章里。1962年，他又出版了《Principles of Neurodynamics: Perceptrons and the theory of brain mechanisms》一书，向大众深入解释感知机的理论知识及背景假设。此书介绍了一些重要的概念及定理证明，例如感知机收敛定理。

虽然最初被认为有着良好的发展潜能，但感知机最终被证明不能处理诸多的模式识别问题。1969年，Marvin Minsky 和 Seymour Papert 在《Perceptrons》书中，仔细分析了以感知机为代表的单层神经网络系统的功能及局限，证明感知机不能解决简单的异或（XOR）等线性不可分问题，但 Rosenblatt 和 Minsky 及 Papert 等人在当时已经了解到多层神经网络能够解决线性不可分的问题。

由于 Rosenblatt 等人没能够及时推广感知机学习算法到多层神经网络上，又由于《Perceptrons》在研究领域中的巨大影响，及人们对书中论点的误解，造成了人工神经领域发展的长年停滞及低潮，直到人们认识到多层感知机没有单层感知机固有的缺陷及反向传播算法在80年代的提出，才有所恢复。1987年，书中的错误得到了校正，并更名再版为《Perceptrons - Expanded Edition》。

近年，在 Freund 及 Schapire (1998)使用核技巧改进感知机学习算法之后，愈来愈多的人对感知机学习算法产生兴趣。后来的研究表明除了二元分类，感知机也能应用在较复杂、被称为 structured learning 类型的任务上（Collins, 2002），又或使用在分布式计算环境中的大规模机器学习问题上（McDonald, Hall and Mann,2011）。

感知机学习策略

1. 数据集的线性可分性

给定一个数据集，如果存在某个超平面S, $w \cdot x+b$=0能够将数据集的正实例点和负实例点都正确的划分到超平面的两侧，即对所有$y_i=+1的实例i，有wx_i+b >０$，$y_i=－1$的实例i，有
$w \cdot x+b＜０$，就称该数据集是*线性可分的。

2. 感知机学习策略

感知机学习策略是：在假设空间中，选取使损失函数值最小的模型参数（权重w,偏置bias)，即感知机模型。

为什么引入损失函数呢？损失函数又是什么呢？

假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面（separating hyperplane),为了找出这样的超平面，即确定感知机模型参数w,b,需要确定一个学习策略，即定义经验损失函数并将损失函数极小化。

损失函数可以选择误分类点的总数，也可以选择误分类点到超平面的距离，由于我们要对这个损失函数进行极小化，极小化最好是连续可导的函数，所以就选择后者，因为误分类点的总数是一个离散的函数，不是连续的。

为此，我们先根据点到平面的距离公式写出输入空间$R^n$中任意一点$x_0$到超平面S的距离：
$$
\frac1{\left\lVert w\right\rVert}\left\lvert w \cdot x +b \right\rvert
$$
这里 $\left\lVert w \right\rVert$ 是 w 的norm范数。

其次，对于误分类的数据($x_i,y_i$)来说,
$$ -y_i(w \cdot x_i +b) \gt 0 $$成立。因为对于误分类的数据来说，$y_i和w \cdot x+b $ 永远异号，所以，误分类点到超平面的距离就是：
$$
-\frac1{\left\lVert w\right\rVert} yi \left( w \cdot x +b \right)
$$
这样，假设超平面S的误分类点集合为 M ,那么所有误分类点到超平面S的总距离为
$$
-\frac1{\left\lVert w\right\rVert} \sum{x_i \in M } yi \left( w \cdot x +b \right)
$$
不考虑 $\frac1{\left\lVert w\right\rVert}$（因为它对所有的训练数据样本都是一样的），就得到了感知机学习的损失函数
$$
L(w,b)=- \sum{x_i \in M }y_i \left( w \cdot x +b \right)
$$
其中 M 为 误分类点的集合。这个损失函数就是感知机学习的 经验风险函数。

显然，损失函数是非负的，如果没有误分类点，那么损失函数的值就是0，误分类点越少，误分类点离超平面越近，损失函数值就越小。针对一个特定的样本点的损失函数值，在分类正确的时候是0，在误分类的时候是参数w,b的线性函数，因此，损失函数 L(w,b) 是 w,b 的连续可导函数。这样，我们就能用数值积分的优化方法对这个函数进行最优化了。优化的过程就是学习的过程。

感知器学习算法

感知机学习算法的原始形式：
输入：　训练数据集T = {$(x_1,y_1),(x_2,y_2),…,(x_n,y_n)$},其中　$x_i \in X = R^n , y_i \in Y = {-1,+1},i=1,2,…,N$ ; 学习率$\eta$ ( 0 < $\eta \le 1$);

输出：　w,b; 感知机模型 $ f(x) = sign( w \cdot x + b) $ ;

选取初始值$ w_0,b_0$
在训练集中随机选取一个数据($ x_i , y_i $)
如果 $ y_i(w \cdot x_i + b) \le 0 $
$$w \leftarrow w + \eta y_ix_i\ b \leftarrow b + \eta y_i$$
转到2，直到训练集合中没有误分类点

这种学习算法直观上有如下解释：当一个实例点被误分类，即位于分离超平面的错误一侧时，则调整w,b的值，使得分离超平面向该误分类点的一侧移动，以减少该误分类点与超平面的距离，直至超平面越过该误分类点使其被正确分类。

感知机学习算法由于采用不同的初值或者选取不同的误分类点，解可以不同。

梯度下降

首先，对每一条数据进行计算　，求出符号
然后如果求出的符号和真实的符号不相等，就要修正错误
如何修正错误
- 看右上方y=+1的图，正确的是正的，却算出来负的，说明w 和 x的夹角太大，要把w转向x，因为此时y=+1所以w+yx是　w+x，相当于图中的中间那条向量；
- 再看y=-1的图，正确的是负的，但是算出来是正的，说明w和x的夹角太小了，要把w向远离x的方向转，此时w+yx=w-x，所以结果就转向远离x的方向了。

算法代码仿真

import os
# set the initial data
data_set = [[(3,3),1],[(4,3),1],[(1,1),-1]]
w = [i-i for i in range(len(data_set)-1)]
b = 0
rate = 1
# update parameters using stochastic gradient descent,define the cost function
def cost_function(item):
  global w,b
  y = item[1]
  x = item[0]
  # get the inner product of w and x
  inner_product = 0.0
  for i in range(len(w)-1):
    inner_product += w[i]*x[i]
  res = y*(inner_product+b)
  return res
# define the update strategy
def update(item):
  global w,b,rate
  y = item[1]
  x = item[0]
  for i in range(len(w)-1):
    w[i] = w[i] + rate*y*x[i]
  # b is the bias
  b = b + rate*y
# check if there is still mis-classified item
def check(data_set,exist_mis):
  for item in data_set:
    if cost_function(item) <= 0:
      update(item)
      exist_mis = True
    if exist_mis == False:
      print 'Result w : ',str(w),' b: ',str(b)
      os._exit(0)
def learn(data_set):
  global w,b
  for turn in range(1000): # iterator 1000 times
    exist_mis= False
    check(data_set,exist_mis)
    exist_mis = False
  print 'the dataset is no linear separatable'
if __name__=='__main__':
  learn(data_set)

Prev Home Next