支持向量机/04. 软间隔支持向量机的对偶问题.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上一节我们得到了软间隔支持向量机的基本形式：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "&\\mathop \\min_{w,b} \\frac{1}{2}\\|w\\|^2 + C\\sum_{i=1}^n\\xi_i \\\\\n",
    "&s.t. y_i(w^Tx_i + b) \\geq 1 - \\xi_i, \\xi_i \\geq 0, i = 1,2,\\dots,n\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "为了求解这个问题，我们也使用 **拉格郎日乘子法** 将其转换为对偶形式。我们给每一个约束条件加上 **拉格朗日乘子**，得到 **拉格郎日函数**：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "L(w,b,\\xi,\\alpha,\\beta) = \n",
    "& \\frac{1}{2}\\|w\\|^2 + C\\sum_{i=1}^n\\xi_i \\\\\n",
    "& + \\sum_{i=1}^n \\alpha_i (1-\\xi_i-y_i(w^Tx_i+b)) - \\sum_{i=1}^n \\beta_i\\xi_i\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "其中 $\\alpha \\geq 0, \\beta \\geq 0$ 是拉格郎日乘子。\n",
    "\n",
    "和硬间隔支持向量机的优化目标一样：\n",
    "\n",
    "$$\n",
    "\\mathop \\min_{w,b,\\xi} \\mathop \\max_{\\alpha,\\beta} L(w,b,\\xi,\\alpha,\\beta)\n",
    "$$\n",
    "\n",
    "转换为对偶问题：\n",
    "\n",
    "$$\n",
    "\\mathop \\max_{\\alpha,\\beta} \\mathop \\min_{w,b,\\xi} L(w,b,\\xi,\\alpha,\\beta)\n",
    "$$\n",
    "\n",
    "所以，我们对 $w, b, \\xi$ 分别求偏导：\n",
    "\n",
    "$$\n",
    "\\left\\{\n",
    "\\begin{align}\n",
    "\\frac{\\partial L(w,b,\\xi,\\alpha,\\beta)}{\\partial w} &= w - \\sum_{i=1}^n\\alpha_iy_ix_i \\\\\n",
    "\\frac{\\partial L(w,b,\\xi,\\alpha,\\beta)}{\\partial b} &= -\\sum_{i=1}^n \\alpha_iy_i \\\\\n",
    "\\frac{\\partial L(w,b,\\xi,\\alpha,\\beta)}{\\partial \\xi_i} &= C - (\\alpha_i + \\beta_i)\n",
    "\\end{align}\n",
    "\\right .\n",
    "$$\n",
    "\n",
    "分别令其为零，得到：\n",
    "\n",
    "$$\n",
    "\\left\\{\n",
    "\\begin{align}\n",
    "w &= \\sum_{i=1}^n\\alpha_iy_ix_i \\\\\n",
    "0 &= \\sum_{i=1}^n \\alpha_iy_i \\\\\n",
    "C &= (\\alpha_i + \\beta_i) \\\\\n",
    "\\end{align}\n",
    "\\right .\n",
    "$$\n",
    "\n",
    "将这三个式子带入 $L(w,b,\\xi,\\alpha,\\beta)$ 有：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "L(w,b,\\xi,\\alpha,\\beta) \n",
    "&= \\frac{1}{2}\\|w\\|^2 + C\\sum_{i=1}^n\\xi_i + \\sum_{i=1}^n \\alpha_i (1-\\xi_i-y_i(w^Tx_i+b)) - \\sum_{i=1}^n \\beta_i\\xi_i \\\\\n",
    "&= \\frac{1}{2}w^Tw + \\sum_{i=1}^n(\\alpha_i+\\beta_i)\\xi_i + \\sum_{i=1}^n(\\alpha_i-\\alpha_i\\xi_i-\\alpha_iy_iw^Tx_i-\\alpha_iy_ib-\\beta_i\\xi_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",
    "可以看到，参数 $\\beta$ 被消掉了，得到的结果和硬间隔支持向量机是一样的，问题转换为求：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\mathop \\max_{\\alpha,\\beta} \\mathop \\min_{w,b} L(w,b,\\xi,\\alpha,\\beta) &= \\mathop \\max_{\\alpha,\\beta} \\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 \\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",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "只是约束条件相比硬间隔支持向量机来说，多了 $\\alpha_i \\leq C$，所以有：\n",
    "\n",
    "$$\n",
    "s.t. \\sum_{i=1}^n \\alpha_i y_i = 0, 0 \\leq \\alpha_i \\leq C, i = 1,2,\\dots,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
}