{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**支持向量机**（Support Vector Machine，简称 SVM）和逻辑回归、朴素贝叶斯一样，也是一种有监督分类算法，它的目标是通过最大化训练数据集的间隔找到一个最优划分超平面。\n",
    "\n",
    "那么什么是支持向量？什么是间隔？什么是最优划分超平面呢？\n",
    "\n",
    "给定如下图所示的训练样本，很显然这是二维平面上的一个二分类问题，一个最基本的分类想法是能不能找一条直线把两个样本类别划分成两个部分？这条直线有点像我们之前在逻辑回归中介绍的 **决策边界**，而在支持向量机中，我们称之为 **划分超平面**。但是能将样本分开的划分超平面可能会有多个，就像下图这样，到底哪个才是最好的呢？\n",
    "\n",
    "![](../images/svm-1.jpg)\n",
    "\n",
    "直观上看，我们应该去找位于这个类别正中间的划分超平面，尽可能的远离所有类别的数据点，这样它对训练样本的噪声影响最小，容忍性最好，也就是说，基于这个划分超平面所产生的分类结果是最鲁棒的，泛化能力最强。这个超平面叫做 **最优划分超平面**。\n",
    "\n",
    "那么如何去找最优划分超平面呢？这就要引出间隔的概念。我们知道平面可以用线性方程来表示，所以划分超平面可以写成：\n",
    "\n",
    "$$\n",
    "w^Tx + b = 0\n",
    "$$\n",
    "\n",
    "样本空间中的任意点到划分超平面的距离为：\n",
    "\n",
    "$$\n",
    "r = \\frac{|w^Tx + b|}{\\|w\\|}\n",
    "$$\n",
    "\n",
    "假设 $w^Tx + b \\ge +1$ 时为正例，$w^Tx + b \\le -1$ 时为负例，如下图所示：\n",
    "\n",
    "![](../images/svm-2.jpg)\n",
    "\n",
    "从图中可以看出，距离划分超平面最近的正例样本位于直线 $w^Tx + b = 1$ 上，而距离划分超平面最近的负例样本位于直线 $w^Tx + b = -1$ 上，这两条直线上的样本被称为 **支持向量**（support vector），这两条直线之间的距离被称为 **间隔**（margin），很显然，间隔的值为：\n",
    "\n",
    "$$\n",
    "\\gamma = \\frac{2}{\\|w\\|}\n",
    "$$\n",
    "\n",
    "要找到最优划分超平面，也就是让间隔最大化，所以问题可以转换为求优化问题的解：\n",
    "\n",
    "$$\n",
    "\\mathop \\max_{w,b} \\frac{2}{\\|w\\|}\n",
    "$$\n",
    "\n",
    "当然这个优化问题有一个约束条件：\n",
    "\n",
    "$$\n",
    "\\left\\{\n",
    "\\begin{align}\n",
    "w^Tx_i + b \\ge +1, y_i = +1 \\\\\n",
    "w^Tx_i + b \\le -1, y_i = -1\n",
    "\\end{align}\n",
    "\\right.\n",
    "$$\n",
    "\n",
    "约束条件也可以简写成：\n",
    "\n",
    "$$\n",
    "y_i(w^Tx_i + b) \\ge 1\n",
    "$$\n",
    "\n",
    "上面这个有约束条件的最优化问题就是支持向量机的基本形式，一般写成：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "&\\mathop \\max_{w,b} \\frac{2}{\\|w\\|} \\\\\n",
    "&s.t. y_i(w^Tx_i + b) \\ge 1, i = 1,2,\\dots,n\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "其中，$s.t.$ 是 subject to 的缩写，表示受限于，是前面优化目标的约束条件。稍作转换，支持向量机还能写成最小化的形式：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "&\\mathop \\min_{w,b} \\frac{1}{2}\\|w\\|^2 \\\\\n",
    "&s.t. y_i(w^Tx_i + b) \\ge 1, i = 1,2,\\dots,n\n",
    "\\end{align}\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
}