{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**感知机**（perceptron）是一种非常简单的用于二分类的线性模型，对于线性可分的样本，它对应于输入空间中将样本划分为正负两类的划分超平面，感知机模型在 1957 年由 Rosenblatt 提出，是神经网络和支持向量机的基础。\n",
    "\n",
    "### 感知机模型\n",
    "\n",
    "在支持向量机的学习中，我们知道，对于一个线性可分的输入空间，存在多个划分超平面可以将训练样本分开，如下图所示：\n",
    "\n",
    "![](../images/svm-1.jpg)\n",
    "\n",
    "这样的划分超平面可以写成线性方程的形式：\n",
    "\n",
    "$$\n",
    "w^Tx + b = 0\n",
    "$$\n",
    "\n",
    "一旦将空间划分成两个部分之后，就可以通过 $w^Tx + b$ 的符号来进行分类：\n",
    "\n",
    "$$\n",
    "f(x) = sign(w^Tx + b)\n",
    "$$\n",
    "\n",
    "其中，sign 是符号函数，当 $w^Tx + b \\geq 0$ 时，将其归为正类，当 $w^Tx + b < 0$ 时，将其归为负类。这里的 $f(x)$ 函数被称为 **感知机**（perceptron）模型。\n",
    "\n",
    "### 感知机的损失函数\n",
    "\n",
    "输入空间中的某个点到划分超平面的距离可以写成：\n",
    "\n",
    "$$\n",
    "r = \\frac{|w^Tx + b|}{\\|w\\|}\n",
    "$$\n",
    "\n",
    "如果某个点 $(x_i, y_i)$ 被误分类，也就是说当 $w^Tx_i + b \\geq 0$ 时，将其归为负类（$y_i = -1$），当 $w^Tx_i + b < 0$ 时，将其归为正类（$y_i = 1$），这时我们有：\n",
    "\n",
    "$$\n",
    "-y_i(w^Tx_i + b) \\geq 0\n",
    "$$\n",
    "\n",
    "所以对于误分类的点，它到划分超平面的距离可以写成：\n",
    "\n",
    "$$\n",
    "r = \\frac{|w^Tx + b|}{\\|w\\|} = \\frac{-y_i(w^Tx_i + b)}{\\|w\\|}\n",
    "$$\n",
    "\n",
    "我们将所有误分类的点到划分超平面的距离累加，得到感知机的损失函数：\n",
    "\n",
    "$$\n",
    "loss = -\\sum_{x_i \\in M} y_i(w^Tx_i + b)\n",
    "$$\n",
    "\n",
    "这里我们把 $\\frac{1}{\\|w\\|}$ 省略了，它不影响损失函数的结果，其中 $M$ 表示误分类点的集合，很显然，当没有点被误分类时，损失函数等于 0，感知机算法就是求损失函数最小时的 w、b 参数。\n",
    "\n",
    "### 使用随机梯度下降训练感知机\n",
    "\n",
    "要使感知机的损失函数最小化，通常使用 **随机梯度下降法**（stochastic gradient descent），首先选取一个超平面 $w_0, b_0$，然后用梯度下降法不断的极小化损失函数，在极小化过程中每次随机选取一个误分类点使其梯度下降。\n",
    "\n",
    "损失函数的梯度如下：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\nabla_w loss &= -\\sum_{x_i \\in M} y_i x_i \\\\\n",
    "\\nabla_b loss &= -\\sum_{x_i \\in M} y_i\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "随机选取一个误分类点 $(x_i, y_i)$，对 w, b 的更新公式为：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "w &:= w + \\eta y_i x_i \\\\\n",
    "b &:= b + \\eta y_i\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "式中 $\\eta$ 是步长，又叫学习率。通过不断的迭代，损失函数不断减小，直到为 0 。\n",
    "\n",
    "### 感知机算法的收敛性\n",
    "\n",
    "对于一个线性可分的数据集，感知机学习算法是不是一定收敛呢？这就需要引出 **Novikoff 定理** 了。\n",
    "\n",
    "根据 **Novikoff 定理**，感知机算法在训练集上的误分类次数 k 满足不等式：\n",
    "\n",
    "$$\n",
    "k \\leq (\\frac{R}{\\gamma})^2\n",
    "$$\n",
    "\n",
    "也就是说，误分类次数是有上界的，经过有限次迭代肯定可以找到将训练数据完全正确分开的超平面。\n",
    "\n",
    "### 感知机算法的对偶形式\n",
    "\n",
    "$$\n",
    "f(x) = sign(\\sum_{j=1}^N \\alpha_j y_j x_j \\cdot x + b)\n",
    "$$\n",
    "\n",
    "参考《统计学习方法》中的实例。\n",
    "\n",
    "### 感知机算法存在的问题\n",
    "\n",
    "感知机学习算法存在多个解，采用不同的初始值或者在迭代过程中改变选取误分类点的顺序，求得的解都会不同。为了得到唯一的超平面，需要对超平面增加约束条件，这就是线性支持向量机的想法。\n",
    "\n",
    "当训练样本不是线性可分的时候，感知机算法不收敛，迭代结果会发生震荡。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}