支持向量机/02. 支持向量机的对偶问题.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上一节我们学习了支持向量机的优化目标为：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "&\\mathop \\min_{w,b} \\frac{1}{2}\\|w\\|^2 \\\\\n",
    "&s.t. y_i(w^Tx_i + b) \\geq 1, i = 1,2,\\dots,n\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "这是一个 **凸二次规划**（convex quadratic programming） 问题，可以用现成的 QP 优化包来求解。（TODO）\n",
    "\n",
    "另外，还可以通过 **拉格朗日乘子法** 将其转换为解法更高效的对偶形式，其主要思想是将约束条件函数与原函数联系到一起，使之配成与变量数量相等的等式方程，从而求出原函数极值的各个变量的解。转换的方法简单来说就是对每一个约束条件加上一个 **拉格朗日乘子**（Lagrange multiplier），定义出 **拉格朗日函数** 如下：\n",
    "\n",
    "$$\n",
    "L(w,b,\\alpha) = \\frac{1}{2}\\|w\\|^2 - \\sum_{i=1}^n \\alpha_i (y_i(w^Tx_i + b) - 1)\n",
    "$$\n",
    "\n",
    "其中，引入了一个新的变量 $\\alpha$，这个变量就是 **拉格朗日乘子**。所以支持向量机的优化目标可以写成：\n",
    "\n",
    "$$\n",
    "\\mathop \\min_{w,b} \\mathop \\max_{\\alpha} L(w,b,\\alpha)\n",
    "$$\n",
    "\n",
    "根据 **拉格郎日对偶性**，可以得到该优化目标的 **对偶问题**（dual problem）：\n",
    "\n",
    "$$\n",
    "\\mathop \\max_{\\alpha} \\mathop \\min_{w,b} L(w,b,\\alpha)\n",
    "$$\n",
    "\n",
    "为了求解这个问题，我们可以先求 $\\mathop \\min_{w,b} L(w,b,\\alpha)$，很显然，这是一个最小值问题，直接使用求导的方法，我们对 $w$ 和 $b$ 分别求偏导：\n",
    "\n",
    "$$\n",
    "\\frac{\\partial L(w,b,\\alpha)}{\\partial w} = w - \\sum_{i=1}^n \\alpha_i y_i x_i\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial L(w,b,\\alpha)}{\\partial b} = \\sum_{i=1}^n \\alpha_i y_i\n",
    "$$\n",
    "\n",
    "令偏导等于 0，可以得到：\n",
    "\n",
    "$$\n",
    "w = \\sum_{i=1}^n \\alpha_i y_i x_i\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\sum_{i=1}^n \\alpha_i y_i = 0\n",
    "$$\n",
    "\n",
    "将这两个结果带入 $L(w,b,\\alpha)$ 有：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "L(w,b,\\alpha) &= \\frac{1}{2}\\|w\\|^2 - \\sum_{i=1}^n \\alpha_i (y_i(w^Tx_i + b) - 1) \\\\\n",
    "&= \\frac{1}{2}w^Tw - w^T \\sum_{i=1}^n \\alpha_i y_i x_i - b \\sum_{i=1}^n \\alpha_i y_i + \\sum_{i=1}^n \\alpha_i \\\\\n",
    "&= \\frac{1}{2}w^Tw - w^Tw - b 0 + \\sum_{i=1}^n \\alpha_i \\\\\n",
    "&= \\sum_{i=1}^n \\alpha_i - \\frac{1}{2}w^Tw \\\\\n",
    "&= \\sum_{i=1}^n \\alpha_i - \\frac{1}{2} \\sum_{i=1}^n \\sum_{j=1}^n \\alpha_i \\alpha_j y_i y_j x_i x_j \\\\\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "所以问题转换为求：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\mathop \\max_{\\alpha} \\mathop \\min_{w,b} L(w,b,\\alpha) &= \\mathop \\max_{\\alpha} \\sum_{i=1}^n \\alpha_i - \\frac{1}{2} \\sum_{i=1}^n \\sum_{j=1}^n \\alpha_i \\alpha_j y_i y_j x_i x_j \\\\\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",
    "转换符号变成求最小值：\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 x_i 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",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解出 $\\alpha$ 后，从而得到划分超平面：\n",
    "\n",
    "$$\n",
    "f(x) = w^Tx+b = \\sum_{i=1}^n \\alpha_i y_i x_i^T x + b\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
}