线性支持超平面分类器

考虑\(D=(x_i, y_i)_{i=1}^n, x_i \in R^p, y_i \in \{-1, 1\}\)的分类问题。我们想找一个超平面\(\langle w, x \rangle + b=0\)将两类\(x_i\)完全分开。若\(D\)是线性可分的，则可以做到。令\(f(x)=\langle w, x \rangle + b\),最小化 \[\min_{w,b} \frac{1}{2} \|w\|^2 \tag{1.1}\] \[s.t. y_i f(x_i) \geq 1, i=1,\cdots, n.\] 因为任意一点\(x_i\)到超平面的距离为\(f(x_i)/\|w\|\)，因为\(d(x, l_0)=\|x\| \cos(<x, l_0^\perp>)=\|x\| \|w\| \cos(<x, l^\perp>)/\|w\|=<x,w>/\|w\|=f(x_i)/\|w\|\)，其中\(l_0\)表示超平面，\(l_0^\perp\)表示超平面的法向量。 由于\(y_i \in \{1,-1\}\)，所有两类点之间的距离最小为\(2\|w\|^{-1}\)。\((1.1)\)是很简单的一个带有线性约束的二次规划问题，现有很多二次规划方法可以求解。

当数据线性不可分时，满足约束条件的可行解无法找到，因为它要求每个样本点都满足条件。此时，我们可以引入一个容忍度参数\(\xi_i\),最小化 \[\min_{w,b} \frac{1}{2} \|w\|^2 +C \sum_i \xi_i \tag{1.2}\] \[s.t. y_i f(x_i) \geq 1-\xi_i, \xi_i \geq 0, i=1,\cdots, n.\] 同时尽量让\(\xi_i\)接近0，表示违背\((1.1)\)约束的样本点尽量少。 这个带约束的二次规划问题等价于一个不带约束的判罚损失目标函数最小化的问题，如下 \[\min_{w,b} \sum_i l(f(x_i),y_i) + \frac{\lambda}{2} \|w\|^2,\tag{1.3} \] 其中\(l(f(x_i), y_i) = \max\{1-y_if(x_i), 0\}\)，这就是著名的Hinge Loss。

证明: 最小化的\(\xi_i\)其实就是定义的关于\((f(x_i),y_i)\)的一个损失度量，\(\xi_i\)越小越好。于是，我们可以根据条件约束定义一个损失函数： \[\xi_i = l(y_i, f(x_i))=\left\{ \begin{aligned} 0 &, & 1- y_i f(x_i) \leq 0, \\ 1-y_i f(x_i) & , & 1- y_i f(x_i) > 0. \end{aligned} \right.\] 因为\(\xi_i \geq 1 - y_i f(x_i)\)，当\(1- y_i f(x_i) > 0\),\(\xi_i\)最小值为\(1-y_i f(x_i)\)。将\(\xi_i\)代入\((1.2)\)，我们得到： \[\min_{w,b} \frac{1}{2} \|w\|^2 +C \sum_i l(f(x_i), y_i) \tag{1.4},\] 最后目标函数同时除以\(C\)，将判罚参数转到第一项上，于是得证。 &club;

\((1.3)\)式的好处是帮助我们建立\(f\)估计的理论性质，因为它有一个明确的目标函数，方便从统计角度研究它的理论性质，比如估计相合性和收敛速度。

虽然\((1.2)\)式利用二次规划的方法很好求解，但是当变量维度\(p>n\)时，计算是无效率的。于是，我们将它转化为对偶问题来求解。为了求它的对偶问题，我们需要用到拉格朗日方法，首先需要不等式约束转化为\(\leq\)约束, \[\min_{w,b} \frac{1}{2} \|w\|^2 +C \sum_i \xi_i \tag{1.5}\] \[s.t. 1-\xi_i-y_i f(x_i)\leq 0, -\xi_i \leq 0, i=1,\cdots, n.\] 于是，我们得到拉格朗日函数为 \[L(w,b,\xi, \alpha, \eta) = 1/2 \|w\|^2 + C \sum_i \xi_i + \sum_i \alpha_i(1-\xi_i-y_if(x_i)) - \sum_i \eta_i \xi_i,\] 其中\(\forall i, \alpha_i,\eta_i \geq 0\). 关于原始变量求导，得 \[\partial L_w = w - \sum_i \alpha_i y_i x_i = 0,\] \[\partial L_b = -\sum_i \alpha_i y_i = 0,\] \[\partial L_{\xi_i} = C - \alpha_i - \eta_i=0,\] 把原始变量表示成对偶变量\(\alpha_i\)和\(\eta_i\)的形式。故得\(w = \sum_i \alpha_i y_i x_i\),代入拉格朗日函数得到对偶问题, \[\min_\alpha 1/2 \alpha^T Q \alpha - \alpha^T 1 \tag{1.6}\] \[s.t. \alpha^Ty=0, \alpha_i \in [0, C],\forall i \in [n].\] 其中\(Q_{ij} = y_i y_j \langle x_i, x_j \rangle\). 这个二次规划就更加简单，只用解\(n\)个参数，而不是像\((1.2)\)需要解\(p+n\)个参数。KKT条件要求\(\alpha_i (y_i f(x_i) - 1) = 0\)，于是对于\(y_i f(x_i) -1 \geq 0\)的那些样本\(\xi_i = 0\)，且\(\alpha_i = 0\)，这样的\(x_i\)称为内部点；而对于\(y_i f(x_i) -1 =0\)的那些样本\(\alpha_i>0\)，这样的\(x_i\)被称为支持向量。所以该分类器被称为线性支持超平面分类器。

问题：为什么KKT条件要求$\alpha_i (y_i f(x_i) - 1) = 0$？

支持向量机

根据\((1.6)\)式，我们很容易将它推广到特征映射和再生核。只需\(K_{ij}=y_i y_j \langle \Phi(x_i), \Phi(x_j) \rangle\)，这样推广后的支持超平面分类器被称为支持向量机。

由于\(l(y_i, f(x_i)) \leq \xi_i\)，所以\(\sum_i \xi_i\)是经验风险的上界。将\(y_if(x_i) \geq 1\)变成\(y_if(x_i) \geq \rho\)，我们可以推广到所谓的\(\nu\)-SV 分类器： \[\min_{w,b} \frac{1}{2} \|w\|^2 +C \sum_i \xi_i -n \nu \rho \tag{1.7}\] \[s.t. y_i f(x_i) \geq \rho-\xi_i, \xi_i \geq 0, i=1,\cdots, n.\] 它的对偶问题为: \[\min_\alpha 1/2 \alpha^T Q \alpha \tag{1.8}\] \[s.t. \alpha^Ty=0, \alpha^T 1= n \nu, \alpha_i \in [0, 1],\forall i \in [n].\] \(\nu\)是支持向量所占比例的一个下界，即\(\nu \leq \frac{\|\alpha\|_0}{n}\)。由于\(\alpha_i \leq 0\)，所以\(\|\alpha\|_1 = n\nu\),再加上\(\|\alpha\|_1 \leq \|\alpha\|_0\)得证。

支持向量回归

假设我们要找一个函数\(f(x) = \langle w, x \rangle + b\)来拟合一个回归问题，最小化 \[\min_{w,b} \frac{1}{2} \|w\|^2 + C \sum_i \xi_i \tag{3.1}\] \[s.t. |y_i - f(x_i)| \leq \epsilon + \xi_i, \xi_i \geq 0.\] 这个问题，我们也可以转化成判罚损失函数的形式。同样这里\(\xi_i\)可以视为\(y_i\)与\(f(x_i)\)之间的一个损失度量，\(\xi_i\)越小越好。于是，我们可以根据条件约束定义一个损失函数： \[\xi_i = l(y_i, f(x_i))=\left\{ \begin{aligned} 0 &, & |y_i - f(x_i)| - \epsilon \leq 0, \\ |y_i - f(x_i)| - \epsilon & , & |y_i - f(x_i)| - \epsilon > 0. \end{aligned} \right.\] 因为\(\xi_i \geq |y_i - f(x_i)| - \epsilon\)，当\(|y_i - f(x_i)| - \epsilon > 0\),\(\xi_i\)最小值为\(|y_i - f(x_i)| - \epsilon\)。将\(\xi_i\)代入\((3.1)\)，我们得到： \[\min_{w,b} \frac{1}{2} \|w\|^2 +C \sum_i l(f(x_i), y_i) ,\] 其中\(l(f(x_i), y_i) = \max(0, |f(x_i) - y_i|-\epsilon)\)，这个损失函数也有一个著名的名字，它叫\(\epsilon\)-不敏感损失函数（只有超过\(\epsilon\)后才会产生损失，真实名副其实）。最后目标函数同时除以\(C\)，将判罚参数转到第一项上，于是得到 \[\min_{w,b} \sum_i l(f(x_i), y_i) + \frac{\lambda}{2} \|w\|^2 \tag{3.2}.\]

到了这里，我应该相信我题目中所说的“无所不能的支持向量机”，它的思想既可
以处理回归问题，又可以分类问题，后面还会看到它还可处理无监督学习的问题。

根据\((3.2)\)，我们可以把损失换成其他损失函数，就会得到不同的方法。同样\((3.1)\)也可以转化为对偶问题求解，优化一个二次规划问题。利用二次规划目标函数，可以直接推广到再生核空间上面。

多分类支持向量机

假设\(y_i \in \mathcal{Y}\)，它是一个离散的分类标签空间，元素个数可以超过2。多分类的目标是找一个函数\(f(x,y)\)，它是一个分类得分函数，\(f(x,y)\)越大表示\(x\)属于\(y\)的可能性越大。所以 \[\hat y(x) = \arg\max_{y \in \mathcal{Y}} f(x,y).\]

我们定义一个损失函数\(\Delta(y,y')\)表示把\(y\)错分为\(y'\)带来的损失，特别地，它可以是0-1损失函数，也可以是其他更一般的损失函数，只要满足如下性质： \(\Delta(y,y)=0,\Delta(y,y')\geq 0\)。下面的引理可以帮助我们构造支持向量思想中的所需要的约束条件。

引理：假设\(\xi \geq 0\)满足对\(\forall y \in \mathcal{Y}\)有 \[f(x,y) - f(x,y') \geq \Delta(y,y') - \xi \tag{5.1}\] 成立，则\(\Delta(y, \arg\max_{y'\in Y} f(x, y')) \leq \xi\)。

该引理表示只要满足约束条件\((5.1)\)，则错判的损失都可以被\(\xi\)给控制住。于是假设\(f(x,y) = \langle \Phi(x,y), w \rangle\)，对应的核函数为\(k(x,y,x',y')=\langle \Phi(x,y), \Phi(x',y') \rangle\)。我们最小化如下目标函数 \[\min_{w,b} \frac{1}{2} \|w\|^2 + C \sum_i \xi_i \tag{5.2}\] \[s.t. f(x_i,y_i) - f(x_i, y) \geq \Delta(y_i,y) - \xi_i, \xi_i \geq 0, y \in Y.\] 对于二分类，令\(\Phi(x,y)=y\Phi(x), \Delta(y,y') = 1- \delta_{yy'}\)，则约束退化成\(2y_i\langle \Phi(x_i), w \rangle \leq 1 - \xi_i\)，这就是二分类的支持向量机。 同样地，目标函数\((5.2)\)也可以转化为对偶问题，求解一个二次规划问题。