支持向量机/07. 非线性支持向量机和核函数.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在前面的学习中，我们假设训练样本是线性可分的，也就是存在一个划分超平面能将训练样本正确分类，那么如果训练样本是非线性的，不存在这样的划分超平面时，该如何解决呢？\n",
    "\n",
    "譬如下面的异或问题就不是线性可分的：\n",
    "\n",
    "<img src=\"../images/xor-nonlinear.png\" width=\"600px\" />\n",
    "\n",
    "我们在学习非线性回归的时候也遇到过类似这种问题，可以将样本从原始空间映射到一个更高维的特征空间，比如上图中我们将其映射到三维空间，这时就能找到合适的划分超平面。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "令 $\\phi(x)$ 表示 $x$ 映射后的特征向量，于是划分超平面可以表示为：\n",
    "\n",
    "$$\n",
    "f(x) = w^T\\phi(x) + b\n",
    "$$\n",
    "\n",
    "优化目标可以写为：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "&\\mathop \\min_{w,b} \\frac{1}{2}\\|w\\|^2 \\\\\n",
    "&s.t. y_i(w^T\\phi(x_i) + b) \\geq 1, i = 1,2,\\dots,n\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "其对偶问题为：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "&\\mathop \\min_{\\alpha} \\frac{1}{2} \\sum_{i=1}^n \\sum_{j=1}^n \\alpha_i \\alpha_j y_i y_j \\phi(x_i)^T \\phi(x_j) - \\sum_{i=1}^n \\alpha_i \\\\\n",
    "&s.t. \\sum_{i=1}^n \\alpha_i y_i = 0, \\alpha_i \\geq 0, i = 1,2,\\dots,n\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "上式中，$\\phi(x_i)^T \\phi(x_j)$ 表示样本 $x_i$ 和 $x_j$ 映射到特征空间之后的内积，由于特征空间维数可能很高，直接计算通常比较困难，可以设想这样一个函数：\n",
    "\n",
    "$$\n",
    "\\kappa(x_i, x_j) = \\langle \\phi(x_i), \\phi(x_j) \\rangle = \\phi(x_i)^T \\phi(x_j)\n",
    "$$\n",
    "\n",
    "也就是 $x_i$ 和 $x_j$ 在特征空间的内积等于它们在原始样本空间中通过函数 $\\kappa(\\centerdot, \\centerdot)$ 计算的结果，这个函数就是 **核函数**（kernel function）。\n",
    "\n",
    "通过引入核函数，非线性支持向量机的优化目标就可以写成下面这种形式：\n",
    "\n",
    "$$\n",
    "\\mathop \\min_{\\alpha} \\frac{1}{2} \\sum_{i=1}^n \\sum_{j=1}^n \\alpha_i \\alpha_j y_i y_j \\kappa(x_i, x_j) - \\sum_{i=1}^n \\alpha_i\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "那么这样的核函数是否存在呢？如果已知映射函数 $\\phi(x)$，那么显然核函数可以通过映射函数的内积计算得到，如果不知道 $\\phi(x)$ 的具体形式，核函数是否存在？什么样的函数可以当作核函数？\n",
    "\n",
    "这里引入核函数定理，如果函数 $\\kappa$ 是对称的，并且对任意的输入数据它对应的 **核矩阵**（kernel matrix）$K$ 总是 **半正定** 的，那么 $\\kappa$ 就是一个核函数。核矩阵是由核函数构成的一个矩阵：\n",
    "\n",
    "$$\n",
    "K = \n",
    "\\left [\n",
    "\\begin{array}{ccc}\n",
    "\\kappa(x_1, x_1) & \\kappa(x_1, x_2) & \\dots & \\kappa(x_1, x_n) \\\\\n",
    "\\vdots & \\vdots & \\vdots & \\vdots \\\\\n",
    "\\kappa(x_n, x_1) & \\kappa(x_n, x_2) & \\dots & \\kappa(x_n, x_n)\n",
    "\\end{array} \n",
    "\\right ]\n",
    "$$\n",
    "\n",
    "这个定理也叫 **Mercer定理**，也就是说，对于任何一个半正定的核矩阵，总能找到一个与之对应的映射 $\\phi$，对于任何一个核函数，都隐式的对应一个特征空间，这个特征空间被称为 **再生核希尔伯特空间**（Reproducing Kernel Hilbert Space，简称 RKHS 空间）。\n",
    "\n",
    "关于核函数的概念，涉及很多泛函分析的概念，包括各种函数空间的概念，可以参考：[说一说核方法（一）——核方法与核函数简介](http://sakigami-yang.me/2017/08/13/about-kernel-01/)、[说一说核方法（二）——数学角度简介](http://sakigami-yang.me/2017/08/13/about-kernel-02/)。\n",
    "\n",
    "下面是一些常用的核函数：\n",
    "\n",
    "![](../images/kernel-functions.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看出使用核函数解决非线性分类问题的基本思想，是通过一个非线性变换将输入空间（欧式空间 $R^n$ 或离散集合）对应于一个特征空间（希尔伯特空间 $\\mathcal{H}$），使得在输入空间中的超曲面模型对应特征空间中的超平面模型，这样，分类问题的学习任务通过在特征空间中求解线性支持向量机就可以完成。\n",
    "\n",
    "实际上这样的技巧可以用在更广泛的地方，对于满足某些条件的优化问题，其最优解都可以表示成核函数的线性组合，这被称为 **表示定理**（representer theorem）：\n",
    "\n",
    "> 对于下面的优化问题：\n",
    "> $$ \\mathop \\min_{w} \\frac{\\lambda}{2} \\|w\\|^2 + \\frac{1}{m} \\sum_{i=1}^m \\ell(w^T\\phi(x_i), y_i) $$\n",
    "> 它的解 $w$ 可以表示成样本的线性组合：\n",
    "> $$ w = \\sum_{i=1}^m \\alpha_i \\phi(x_i) $$\n",
    "\n",
    "通过核函数，我们可以将线性模型扩展成非线性模型，这启发了一系列基于核函数的学习方法，被统称为 **核方法**（kernel methods）或 **核技巧**（kernel trick）。譬如在 **线性判别分析**（LDA）中引入核方法对其进行非线性扩展，就得到了 **核线性判别分别**（KLDA）。"
   ]
  }
 ],
 "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
}