{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "在前面的例子中，我们假定样本空间是线性可分的，即存在一个超平面将不同类别完全划分开来。然而在现实的分类任务中，样本空间往往是线性不可分的，譬如下面这样：\n", "\n", "![](../images/svm-unseparable.png)\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) \\geq 1\n", "$$\n", "\n", "这个约束条件确保所有样本都被正确划分，这被称为 **硬间隔**（hard margin），我们把这个约束条件稍微放宽，允许某些样本不满足该条件，得到的就是 **软间隔**（soft margin），当然，我们希望不满足约束条件的样本越少越好。\n", "\n", "为此，我们对每个样本引入一个松弛变量 $\\xi_i \\geq 0$，约束条件变成：\n", "\n", "$$\n", "y_i(w^Tx_i + b) \\geq 1 - \\xi_i\n", "$$\n", "\n", "同时，对每一个松弛变量 $\\xi$，支付一个代价 C，所以优化目标就变成了：\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", "这里的 C 是一个超参数，决定了你有多重视异常点带来的损失。显然，当 C 为无穷大时，为了求优化目标的最小值，这里加上的松弛变量类似于惩罚项，要非常小甚至等于 0 才行，也就是 $\\xi_i = 0$，会迫使所有的样本都满足约束 $y_i(w^Tx_i + b) \\geq 1$，这就和硬间隔一样；当 C 为某一常数时，允许某些样本不满足约束，得到的就是软间隔。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 损失函数的其他形式\n", "\n", "上面通过在硬间隔的优化目标中引入松弛变量 $\\xi_i$ 得到了软间隔支持向量机的基本形式。实际上，我们还有很多其他的方式来推导软间隔的优化目标，最简单的想法是在优化目标中加入 **0/1损失函数**，硬间隔的优化目标为：\n", "\n", "$$\n", "\\mathop \\min_{w,b} \\frac{1}{2}\\|w\\|^2\n", "$$\n", "\n", "加入 0/1损失函数后，优化目标变成了：\n", "\n", "$$\n", "\\mathop \\min_{w,b} \\frac{1}{2}\\|w\\|^2 + C \\sum_{i=1}^m \\ell_{0/1}(y_i(w^Tx_i + b) - 1)\n", "$$\n", "\n", "其中，$\\ell_{0/1}$ 就是 0/1损失函数，当样本满足硬间隔的约束条件时，也就是 $y_i(w^Tx_i + b) \\geq 1$ 时，损失为 0，不满足时损失为 1：\n", "\n", "$$\n", "\\ell_{0/1}(z) =\n", "\\left\\{\n", "\\begin{align}\n", "0, z \\geq 0 \\\\\n", "1, z < 0 \\\\\n", "\\end{align}\n", "\\right.\n", "$$\n", "\n", "但是 0/1损失函数不连续，也不是凸函数，导致优化目标不易求解，通常用一些其他函数来替代 0/1损失函数，这被称为 **替代损失**（surrogate loss），替代损失一般具有良好的数学性质，通常是凸的连续函数并且是 0/1损失函数的上界。比如 **Hinge损失**：\n", "\n", "$$\n", "\\ell_{hinge}(z) = max(0, 1-z)\n", "$$\n", "\n", "Hinge损失，又叫 **合页损失** 或 **铰链损失**，它就像一个打开的合页形状：\n", "\n", "![](../images/hinge-loss.png)\n", "\n", "加入 Hinge损失函数后，优化目标变成了：\n", "\n", "$$\n", "\\mathop \\min_{w,b} \\frac{1}{2}\\|w\\|^2 + C \\sum_{i=1}^m \\max(0, 1 - y_i(w^Tx_i + b))\n", "$$\n", "\n", "其中，当样本满足硬间隔的约束条件时，也就是 $y_i(w^Tx_i + b) \\geq 1$ 时，这时 $1 - y_i(w^Tx_i + b) \\leq 0$，Hinge损失为 0；当样本不满足约束条件时损失为 $1 - y_i(w^Tx_i + b)$。\n", "\n", "令：\n", "\n", "$$\n", "\\xi_i = \\max(0, 1 - y_i(w^Tx_i + b))\n", "$$\n", "\n", "于是得到和上面一样的优化目标：\n", "\n", "$$\n", "\\mathop \\min_{w,b} \\frac{1}{2}\\|w\\|^2 + C \\sum_{i=1}^m \\xi_i\n", "$$\n", "\n", "很显然：\n", "\n", "$$\n", "\\left\\{\n", "\\begin{align}\n", "& \\xi_i = \\max(0, 1 - y_i(w^Tx_i + b)) \\geq 1 - y_i(w^Tx_i + b) \\\\\n", "& \\xi_i = \\max(0, 1 - y_i(w^Tx_i + b)) \\geq 0\n", "\\end{align}\n", "\\right .\n", "$$\n", "\n", "所以有约束条件：\n", "\n", "$$\n", "y_i(w^Tx_i + b) \\geq 1 - \\xi_i, \\xi_i \\geq 0\n", "$$\n", "\n", "除 Hinge损失之外，还有很多其他的替代损失，比如 **指数损失**（exponential loss）：\n", "\n", "$$\n", "\\ell_{exp}(z) = exp(-z)\n", "$$\n", "\n", "或者 **对率损失**（logistic loss）：\n", "\n", "$$\n", "\\ell_{log}(z) = log(1+exp(-z))\n", "$$\n", "\n", "他们的图像如下所示：\n", "\n", "![](../images/svm-3-loss.jpg)" ] } ], "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 }