多类支持向量机损失（SVM）

假设给定一个特征空间上的训练数据集 $$ T={(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)} $$ 其中， $x_i\in\mathcal{X}=\mathbf{R}^n$ ， $y_i\in\mathcal{Y}={+1,-1},i=1,2,\cdots,N$ 。 $x_i$ 表示第 $i$ 个实例， $y_i$ 是 $x_i$ 的类标记。 当 $y=+1$ 时，称 $x_i$ 为正例；当 $y=-1$ 时，称 $x_i$ 为负例。 $(x_i,y_1)$ 称为样本点。 假设训练数据集是# 线性可分的。

我们的目标是在特征空间中找到一个分离超平面（Separating Hyperplane），能将实例分到不同的类。 分离超平面 $w\dot x+b=0$ ，由法向量 $w$ 和截距 $b$ 决定。

一般的，当训练数据集是线性可分时，存在无穷个分离超平面可将两类数据分离开。 线性可分支持向量机利用间隔最大化求最优分离超平面，这时的解是唯一的。

在上图中，有 $A,B,C$ 三个点，表示三个实例，均在分离超平面的正类一侧。 点 $A$ 距分离超平面较远，若预测该点为正类，就比较确定预测是正确的； 点 $C$ 距分离超平面较近，则预测该点确信为正类就不那么自信。

一般来说，一个点距离分离超平面的远近可以表示分类预测的确定程度。 在超平面 $w\cdot x+b=0$ 确定的情况下， $|w\cdot x+b|$ 能够相对的表示点 $x$ 距离超平面的远近。 而 $w\cdot x+b$ 的符号可以表示预测的准确性，因此我们使用 $y(w\cdot x+b)$ 来表示分类的 准确性和确信度。这就是函数间隔（Functional Margin）。

对于给定的训练数据集 $T$ 和超平面 $(w,b)$ ，定义超平面关于样本点 $(x_i,y_i)$ 的函数间隔为 $$ \hat{\gamma}_i=y_i(w\cdot x+b) $$

定义超平面 $(w,b)$ 关于训练数据集 $T$ 中的函数间隔为超平面关于 $T$ 中所有样本点的函数间隔的最小值，即 $$ \hat{\gamma} = \min_{i=1,\cdots,N}\hat{\gamma}_i $$

虽然函数间隔可以表示分类预测的正确性及确定度，但是选择分离超平面时，只有函数间隔还不够。 只要成比例的改变 $w$ 和 $b$ ，例如将他们改成 $2w$ 和 $2b$ ， 分离超平面没有发生变化，但它们的函数间隔却成了原来的两倍。 这个事实启示我们，如果对函数变量加以约束，使函数间隔变成确定的，这样就可以找到最佳的分离超平面。

可知， $w/||w||$ 是在 $w$ 方向上的单位向量。 假设 $A$ 表示 $x_i$ ， $\gamma_i$ 表示几何间隔，那么 $B$ 可以表示为 $x_i-\gamma_i\cdot w/||w||$ 。 $B$ 点在超平面上，满足超平面方程 $$ w^{T}(x_i-\gamma_i\frac{w}{||w||})+b=0 $$ 求解得： $$ \gamma_i=\frac{w}{||w||}\cdot x_i+\frac{b}{||w||} $$ 由于 $A$ 在超平面上方，所以其几何间隔为正，因此，更一般的， 当样本 $(x_i,y_i)$ 被正确分类时，点 $x_i$ 与超平面的几何距离为 $$ \gamma_i=y_i(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||}) $$

定义超平面 $(w,b)$ 关于训练数据集 $T$ 的几何间隔为超平面关于 $T$ 中所有样本点的几何间隔的最小值，即 $$ \gamma=\min_{i=1,\cdots,N}\gamma_i $$

从上面的分析可以看出，函数间隔和几何间隔之间的关系为： $$ \gamma_i=\frac{\hat{\gamma}_i}{||w||} $$

在线性可分的情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量（Support Vector）。

原始问题的拉格朗日函数是： $$ L(w,b,\xi,\alpha,\mu)=\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i-\sum_{i=1}^{N}\alpha_{i}(y_i(w\cdot x_i+b)-1+\xi_i)-\sum_{i=1}^{N}\mu_i\xi_i $$

其中 $\alpha_i\geq0,\mu_i\geq0$ 。

其对偶问题是拉格朗日函数的极大极小问题。

1. 求 $\min_{w,b,\xi}L$

   分别对 $w,b,\xi$ 求导：

   \begin{aligned} \nabla_{w}L(w,b,\xi,\alpha,\mu)&=w-\sum_{i=1}^{N}\alpha_{i}y_{i}x_{i}=0 \\ \nabla_{b}L(w,b,\xi,\alpha,\mu)&=-\sum_{i=1}^{N}\alpha_{i}y_{i}=0 \\ \nabla_{\xi_i}L(w,b,\xi,\alpha,\mu)&=C-\alpha_i-\mu_i=0 \\ \end{aligned}

   得：

   \begin{aligned} w=\sum_{i=1}^{N}\alpha_iy_ix_i \\ \sum_{i=1}^{N}\alpha_iy_i=0 \\ C-\alpha_i-\mu_i=0 \end{aligned}

   将上式代回原拉格朗日函数得： $$ \min_{w,b,\xi}L(w,b,\xi,\alpha,\mu)=\sum_{i=1}^{N}\alpha_i-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) $$

2. 求 $\max_{\alpha,\mu}\min_{w,b,\xi}L$

   我们的优化问题变成了：

   \begin{aligned} \max_{\alpha} \quad &\sum_{i=1}^{N}\alpha_i-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) \\ s.t. \quad &\sum_{i=1}^{N}\alpha_iy_i=0 \\ &C - \alpha_i - \mu_i = 0 \\ & \alpha_i \geq 0 \\ & \mu_i \geq 0, \quad i=1,2,\cdots,N \end{aligned}

   将 $\mu_i$ 用 $\alpha_i$ 表示之后，可以将约束条件简化为 $$ 0 \leq \alpha_i \leq C,i=1,2,\cdots,N $$

   设 $\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)^T$ 是对偶问题的一个解， 若存在 $\alpha^*$ 的一个分量 $\alpha_j^*$ ， $0<\alpha_j^*<C$ ，则原始问题的解为

   \begin{aligned} w^*=\sum_{i=1}^{N}\alpha_i^*y_ix_i \\ b^*=y_j-\sum_{i=1}^{N}y_i\alpha_i^*(x_i\cdot x_j) \end{aligned}

   证明方法可以参考之前线性可分支持向量机学习算法。

软间隔的支持向量 $x_i$ 或者在间隔边界上，或者在间隔边界与分离超平面之间， 或者在分离超平面误分一侧。

• 若 $\alpha_i^* < C$ ，则 $\xi_i = 0$ ，支持向量恰好落在间隔边界上；
• 若 $\alpha_i^* = C,0<\xi_i<1$ ，则分类正确，在间隔边界和分离超平面之间；
• 若 $\alpha_i^* = C,\xi_i=1$ ，则 $x_i$ 正好在分离超平面上；
• 若 $\alpha_i^* = C,\xi_i>1$ ，则 $x_i$ 被分离超平面误分。

线性支持向量机原始最优化问题等价于

$$ \min_{w,b}\sum_{i=0}^{N}\left[1-y_{i}(w\cdot x_i+b)\right]_{+}+\lambda||w||^2 $$

证明： 合页损失函数（hinge loss function）为： $ [z]₊=≤ft\{ \begin{array}{rcl} z,\;&z>0
0,\;&z≤0

\end{array} \right. $

令 $[1-y_i(w\cdot x_i+b)]_{+}=\xi_i$ ，可知 $\xi_i\geq 0$ 。 当 $1-y_i(w\cdot x_i+b)>0$ ， $y_i(w\cdot x_i+b)=1-\xi_i$ ； 当 $1-y_i(w\cdot x_i+b)\leq0$ ， $\xi_i=0$ ，即 $y_i(w\cdot x_i+b)\geq 1-\xi_i$

因此，约束条件成立。

最优化问题可以写成： $$ \min_{w,b}=\sum_{i=1}^{N}\xi_i+\lambda||w||^2 $$

与线性支持向量机的原始最优化问题等价。