SVM/支持向量机（SVMs）.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# SVM"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Linear Support Vector Machine\n",
    "- Dual Support Vector Machine\n",
    "- Kernel Support Vector Machine\n",
    "- Soft-Margin Support Vector Machine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Linear Support Vector Mahine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "对于一个线性分类器，怎么的线性分类器才是最好的呢？\n",
    "\n",
    "- 保证它的强壮性(就是可以容忍更多的噪声),就是让离这个分类器最近的点到这个分类器的距离间隔最大，这就是我们接下来要做的事情"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- 首先我们要找到一个分类器可以分割开数据，并且使这个分类器最胖，专业一点表示如下\n",
    "\n",
    "$\\max\\limits_w$     $fatness(w)$    \n",
    "目标是： $w$分类器使每个($X_n,y_n$)都正确，fatness($w$) = $\\min\\limits_{n=1,...N}$ distance($x_n$,$w$)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$\\max\\limits_w$     $margin(w)$    \n",
    "目标是： 每个$y_nW^Tx_n>0$，margin($w$) = $\\min\\limits_{n=1,...N}$ distance($x_n$,$w$)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- **  加上常数项 **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$\\max\\limits_{b,w}$     $margin(b,w)$    \n",
    "目标是： 每个$y_n(W^Tx_n+b)>0$，margin($b,w$) = $\\min\\limits_{n=1,...N} \\frac{1}{||w||}y_n(w^Tx_n+b)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- ** 当$\\min\\limits_{n=1,...N} y_n(w^Tx_n+b)=1$时候 $margin($b,w$)= \\frac{1}{||w||}$**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$\\max\\limits_{b,w} \\frac{1}{||w||}$    \n",
    "\n",
    "目标是： 每个$y_n(W^Tx_n+b)>0$   ， $\\min\\limits_{n=1,...N} y_n(w^Tx_n+b)=1$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- ** 最后的变形,这就是SVM的最初形式**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$\\min\\limits_{b,w} \\frac{1}{2}w^Tw$    \n",
    "\n",
    "目标是： 每个$y_n(W^Tx_n+b)>1$ 对所有的n成立"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- 这是一个关于$(b,w)$二次目标函数\n",
    "- 约束条件线性\n",
    "- 所以可以使用二次规划QP很容易的解决最优化问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "![](QP.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 如果不是线性的 **\n",
    "\n",
    "- 可以通过特征转换: $z_n = \\Phi(x_n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** SVM和正则化的区别 **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "||minimize|constraint|\n",
    "|:----:|:-----:|:----:|\n",
    "|regularization|$E_in$|$w^Tw <= C$|\n",
    "|SVM|$w^Tw$|$E_in=0$[any more]|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Dual Support Vector Machine\n",
    "\n",
    "- 非线性支持向量机"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 非线性支持向量机 **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$\\min\\limits_{b,w} \\frac{1}{2}w^Tw$    \n",
    "\n",
    "目标是： 每个$y_n(W^Tz_n+b)\\ge1$ 对所有的n成立"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- 在解决非线性问题时，二次规划问题有$\\widetilde{d} + 1$个变量和N个条件  \n",
    "- 如果$\\widetilde{d}$很大，或者无限怎么办？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 首先我们用拉格朗日函数去掉限制 **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$\\mathcal{L}(b,w,\\alpha) = \\frac{1}{2}w^Tw + \\sum\\limits_{n=1}^N\\alpha_n(1-y_n(w^Tz_n+b))$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$SVM \\equiv\\min\\limits_{b,w}(\\max\\limits_{all  \\alpha_n\\ge0} \\mathcal{L}(b,w,\\alpha)) = \\min\\limits_{b,w}$($\\infty $if violate; $\\frac{1}{2} $if feasible)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**经过一系列证明，得出强对偶关系**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$\\min\\limits_{b,w}(\\max\\limits_{all  \\alpha_n\\ge0} \\mathcal{L}(b,w,\\alpha)) = \\max\\limits_{all  \\alpha_n\\ge0}(\\min\\limits_{b,w}\\mathcal{L}(b,w,\\alpha))$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$\\max\\limits_{all  \\alpha_n\\ge0} (\\min\\limits_{b,w} \\frac{1}{2}w^Tw + \\sum\\limits_{n=1}^N\\alpha_n(1-y_n(w^Tz_n+b)))$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**去掉$b,w$**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$\\max\\limits_{all  \\alpha_n\\ge0, \\sum y_n\\alpha_n=0,w=\\sum\\alpha_ny_nz_n}-\\frac{1}{2}||\\sum\\limits_{n=1}^N\\alpha_ny_nz_n||^2 + \\sum\\limits_{n=1}\\alpha_n$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 使用KKT条件从最优的$\\alpha$得出$(b,w)$**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "primal feasible:$y_n(W^Tz_n+b)\\ge1$   \n",
    "dual feasible:$\\alpha_n\\ge0$   \n",
    "dual-inner optimal:$\\sum y_n\\alpha_n=0,w=\\sum\\alpha_ny_nz_n$   \n",
    "primal-inner optimal:$\\alpha_n(1-y_n(w^Tz_n+b))=0$  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 变成标准的对偶形式 **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$\\min\\limits_\\alpha \\frac{1}{2}\\sum\\limits_{n=1}^N\\sum\\limits_{m=1}^N\\alpha_n\\alpha_m y_ny_mZ_n^Tz_m - \\sum\\limits_{n=1}^N\\alpha_n$\n",
    "\n",
    "$\\sum\\limits_{n=1}^Ny_n\\alpha_n = 0;$     \n",
    "$\\alpha_n \\ge 0$,对于n=1，2，....N"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**这看起来像是N个变量，N+1个条件**    \n",
    "**使用QP解决 **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "![](QP2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 这时如果N过大的化，也很难解 **  \n",
    "** 需要特殊的求解器 **   \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 想到KKT条件$\\alpha_n(1-y_n(w^Tz_n+b))=0$ **\n",
    "\n",
    "如果$\\alpha_n \\ge0$则$b=y_n-w^Tz_n$    \n",
    "刚好$\\alpha_n > 0$时，就是在边界上的点(SV)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "所以只需要用边界上的点计算w:$w=\\sum\\limits_{n=1}^N\\alpha_ny_nz_n = \\sum\\limits_{SV}\\alpha_ny_nz_n$    \n",
    "只需要用边界上的点计算b:$b=y_n-w^Tz_n$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 原始SVM和对偶SVM比较 **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "![](svm.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "变量从$\\widetilde{d} + 1$到N，使用所有的点    \n",
    "限制条件从N到N+1，仅使用边界上的点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 但这时候并没有与$\\widetilde{d}$完全脱离关系**   \n",
    "** $q_{n,m}$$=y_ny_mz_n^Tz_m$ 仍然是 $\\widetilde{d}$维中计算内积 **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Kernel Support Vector Machine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** $q_{n,m}$$=y_ny_mz_n^Tz_m$    $\\widetilde{d}$维中计算内积 **   \n",
    "** $z_n^Tz_m=\\phi(x_n)^T\\phi(x_m)$ **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "用二次多项式作为例子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$\\phi_2(x) = (1,x_1,..,x_d,x_1^2,...x_1x_d,x_2x_1,x_2^2....,x_2x_d,...,x_d^2)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$\\phi_2(x)^T\\phi_2(x^{'})\\\\= 1 + \\sum\\limits_{i=1}^d x_ix_i^{'} + \\sum\\limits_{i=1}^d\\sum\\limits_{j=1}^d x_ix_i^{'}x_jx_j^{'}\\\\=1 + \\sum\\limits_{i=1}^d x_ix_i^{'} + \\sum\\limits_{i=1}^dx_ix_i^{'}\\sum\\limits_{j=1}^d x_jx_j^{'}\\\\=1+x^Tx^{'} +(x^Tx^{'})(x^Tx^{'}) $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 通过转换可以把复杂度降低$O(d^2)$到$O(d)$ **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 这就是核函数 **\n",
    "\n",
    "$K_\\phi(x,x^{'})=\\phi(x)^T\\phi(x^{'})$   \n",
    "$K_{\\phi_2}(x,x^{'})=1+x^Tx^{'} +(x^Tx^{'})(x^Tx^{'})$   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$q_{n,m}$$=y_ny_mz_n^Tz_m=y_ny_mK(x_n,x_m)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 这时候的b,用SV$（x_s,y_s)$**   \n",
    "$b=y_s-w^Tz_s=y_s-(\\sum\\limits_{n=1}^N\\alpha_ny_nz_n)^T=y_s-\\sum\\limits_{n=1}^N\\alpha_ny_nK(x_n,x_s)$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** optimal hypothesis $g_{SVM}$:  test input：x**\n",
    "\n",
    "$g_{SVM}=sign(w^T\\phi(x) + b) = sign(\\sum\\limits_{n=1}^N\\alpha_ny_nK(x_n,x)+b)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 这时候就与$\\widetilde{d}$完全无关了 **   \n",
    "** 时间复杂度为$O(N^2)$ **   \n",
    "** 仅仅使用SV进行预测 **  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 转换成一般的二项式核函数 **\n",
    "\n",
    "$k_2(x,x^{'})=(1+\\gamma x^Tx^{'})^2  \\\\\\gamma>0$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 一般的多项式核函数 **   \n",
    "$k_Q(x,x^{'})=(\\zeta+\\gamma x^Tx^{'})^Q  \\\\\\gamma>0\\\\\\zeta\\ge0$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 高斯核函数（RBF） **    \n",
    "$k(x,x^{'})=exp(-\\gamma||x-x^{'}||^2)  \\\\\\gamma>0$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "> $\\gamma$太大，也会过拟合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 线性核的优点和缺点 **\n",
    "\n",
    "$K(x,x^{'})=x^Tx^{'}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "优点：\n",
    "- 做什么问题都要从最简单的线性开始\n",
    "- 解起来比较快\n",
    "- 用W和SVs可以解释所有\n",
    "\n",
    "缺点\n",
    "- 不能解决线性不可分的点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 多项式核的优点和 缺点 **\n",
    "\n",
    "$k_Q(x,x^{'})=(\\zeta+\\gamma x^Tx^{'})^Q$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "优点：\n",
    "- 比线性的限制少 \n",
    "\n",
    "缺点：\n",
    "- 当Q大的时候不容易解\n",
    "- 参数多，不宜选择"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 高斯核优点和缺点 **    \n",
    "$k(x,x^{'})=exp(-\\gamma||x-x^{'}||^2)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "优点：\n",
    "- 比线性和多项式核更有力度\n",
    "- 边界点数量少\n",
    "- 一个参数，容易选择\n",
    "\n",
    "缺点：\n",
    "- 容易过拟合\n",
    "- 比线性核慢"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 怎么样避免高斯核和其他核的过拟合？**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Soft-Margin Support Vector Machine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "之前的方法都是Hard-Margin SVM，即所有的样本都正确分类才行，这往往需要更多更复杂的特征转换，甚至造成过拟合。\n",
    "\n",
    "本节课将介绍一种Soft-Margin SVM，目的是让分类错误的点越少越好，而不是必须将所有点分类正确，也就是允许有noise存在。这种做法很大程度上不会使模型过于复杂，不会造成过拟合，而且分类效果是令人满意的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "把SVM转换成如下形式：\n",
    "\n",
    "$$\\min_{b,w} \\frac{1}{2}w^Tw + C\\cdot \\sum_{n=1}^{N}[\\![y_n \\ne sign(w^Tz_n + b)]\\!]$$    \n",
    "对于正确的点 $$ y_n(w^Tz_n + b) \\ge 1$$\n",
    "对于错误的点 $$ y_n(w^Tz_n + b) \\ge -\\infty$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "两式合并：\n",
    "$$\\min_{b,w} \\frac{1}{2}w^Tw + C\\cdot \\sum_{n=1}^{N}[\\![y_n \\ne sign(w^Tz_n + b)]\\!]$$    \n",
    "条件：\n",
    "$$ y_n(w^Tz_n + b) \\ge 1 - \\infty \\cdot [\\![y_n \\ne sign(w^Tz_n + b)]\\!]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "上面的式子只是说点是否犯错误，但有的点犯得错误小有的大，上式中并没有区分，通过引入一个$\\xi_n$来表示每个点犯错误的程度值。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$$\\min_{b,w} \\frac{1}{2}w^Tw + C\\cdot \\sum_{n=1}^{N}\\xi_n$$    \n",
    "条件：\n",
    "$$ y_n(w^Tz_n + b) \\ge 1 - \\xi_n, \\xi_n \\ge 0$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "> 参数C表示尽可能选择宽边界和尽可能不要犯错两者之间的权衡，因为边界宽了，往往犯错误的点会增加。large C表示希望得到更少的分类错误，即不惜选择窄边界也要尽可能把更多点正确分类；small C表示希望得到更宽的边界，即不惜增加错误点个数也要选择更宽的分类边界。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "与之对应的QP问题中，由于新的参数 $\\xi_n$ 的引入，总共参数个数为 $\\hat d+1+N $，限制条件添加了 $\\xi_n\\geq0$ ，则总条件个数为2N。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** 对偶问题 **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "拉格朗日函数表示为：\n",
    "\n",
    "$$\\mathcal{L}(b,w,\\xi,\\alpha,\\beta) = \\frac{1}{2}w^Tw + C\\cdot \\sum_{n=1}^{N}\\xi_n + \\sum_{n=1}^{N}\\alpha_n(1-\\xi_n-y_n(w^Tz_n + b)) + \\sum_{n=1}^{N}\\beta_n(-\\xi_n)$$   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "转换成对偶的形式：\n",
    "\n",
    "$$\\max_{\\alpha_n\\ge 0,\\beta_n\\ge 0} ( \\min_{b,w,\\xi} \\frac{1}{2}w^Tw + C\\cdot \\sum_{n=1}^{N}\\xi_n + \\sum_{n=1}^{N}\\alpha_n(1-\\xi_n-y_n(w^Tz_n + b)) + \\sum_{n=1}^{N}\\beta_n(-\\xi_n) ) $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "** SVM算法经典实例 **\n",
    "\n",
    "[SVM算法经典实例](SVM算法经典实例.ipynb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}