感知机

分类 有监督学习

---

主要思想

在机器学习中，感知机（perceptron）是二分类的线性分类模型，属于监督学习算法。输入为实例的特征向量，输出为实例的类别（取+1和-1）。感知机对应于输入空间中将实例划分为两类的分离超平面。感知机旨在求出该超平面，为求得超平面导入了基于误分类的损失函数，利用随机梯度下降法 对损失函数进行最优化。感知机的学习算法具有简单而易于实现的优点，分为原始形式和对偶形式。感知机预测是用学习得到的感知机模型对新的实例进行预测的，因此属于判别模型。

产生背景

感知器（英语：Perceptron）是Frank Rosenblatt在1957年就职于Cornell航空实验室（Cornell Aeronautical Laboratory）时所发明的一种人工神经网络。它可以被视为一种最简单形式的前馈神经网络，是一种二元线性分类器。

应用场景

• 二分类
• 无法解决抑或问题

核心理解

使用一个超平面将特征空间化为两部分。

主要推导

M为误分点的集合，感知机的优化目标是求解如下函数：

$$L(w,b) = \sum\limits_{{x_i} \in M}^{} { - {y_i}(w{x_i} + b)}$$
损失函数对应误分点到分离超平面的总距离。

求梯度

$$\eqalign{ & {{\partial L(w,b)} \over {\partial w}} = \sum\limits_{{x_i} \in M}^{} { - {y_i}{x_i}} \cr & {{\partial L(w,b)} \over {\partial b}} = \sum\limits_{{x_i} \in M}^{} { - {y_i}} \cr}$$
使用随机梯度下降每次选一个样本点做更新
$$\eqalign{ & w \leftarrow w + \eta {y_i}{x_i} \cr & b \leftarrow b + \eta {y_i} \cr}$$

求解算法

线性可分:随机梯度下降，每次选取一个错误用例修改
线性不可分:使用pocket算法，考虑所有数据

伪代码

这里假设数据线性可分
输入:数据集D(N个样本)
过程:
随机初始化w,b
do
随机选取一个样本点
if(这个样本点被误分)
    使用上文推导中的公式更新w和b
until 所有样本被正确分类    
输出:训练好的sign(wx+b)感知机函数

复杂度分析

时间复杂度：如果数据线型可分，一定会在有限次收敛，如果线性不可分，会出现震荡

大数据下改进

to be done...

评价

• 优点

  • 简单

• 缺点

  • 不能解决抑或问题
  • 精度不高

算法改进

• SVM
• 神经网络

参考资料

1. wiki

2. 机器学习常见算法个人总结