12.5数值解
文档摘要
12.5 数值解 我们通过探讨如何根据第7章介绍的概念来表达本章中推导的问题，来结束对支持向量机（SVMs）的讨论。我们考虑两种不同的方法来找到SVM的最优解。首先，我们考虑SVM的损失视角（8.2.2节），并将其表达为一个无约束优化问题。然后，我们将原始和对偶SVM的约束版本表达为标准形式的二次规划（7.3.2节）。 考虑SVM的损失函数视角（12.31）。这是一个凸无约束优化问题，但合页损失（12.28）不可微。因此，我们采用次梯度方法来解决它。然而，合页损失几乎在所有地方都是可微的，除了合页$t=1$处的单点。在这一点上，梯度是一个介于0和-1之间的可能值集。
12.5 数值解
我们通过探讨如何根据第7章介绍的概念来表达本章中推导的问题，来结束对支持向量机（SVMs）的讨论。我们考虑两种不同的方法来找到SVM的最优解。首先，我们考虑SVM的损失视角（8.2.2节），并将其表达为一个无约束优化问题。然后，我们将原始和对偶SVM的约束版本表达为标准形式的二次规划（7.3.2节）。
考虑SVM的损失函数视角（12.31）。这是一个凸无约束优化问题，但合页损失（12.28）不可微。因此，我们采用次梯度方法来解决它。然而，合页损失几乎在所有地方都是可微的，除了合页t=1处的单点。在这一点上，梯度是一个介于0和-1之间的可能值集。因此，合页损失的次梯度g由下式给出：
(12.54)
使用这个次梯度，我们可以应用第7.1节中介绍的优化方法。
原始和对偶SVM都导致了凸二次规划问题（约束优化）。请注意，原始SVM（12.26a）中的优化变量具有输入示例维度D的大小。对偶SVM（12.41）中的优化变量具有示例数量N的大小。
为了将原始SVM表达为二次规划的标准形式（7.45），我们假设使用点积（3.5）作为内积。我们重新排列原始SVM的方程（12.26a），使得优化变量都在右侧，并且约束的不等式与标准形式相匹配。这产生了以下优化问题：
(12.55)
n=1,\ldots,N。通过将变量w,b,\boldsymbol{x}_n连接成一个单独的向量，并仔细收集项，我们得到软间隔SVM的以下矩阵形式：
在前面的优化问题中，最小化是针对参数[\boldsymbol w^{\top},b,\boldsymbol{\xi}^{\top}]^{\top}\in\mathbb{R}^{D+1+N}进行的，我们使用的符号包括：I_m表示大小为m\times m的单位矩阵，\boldsymbol{0}_{m,n}表示大小为m\times n的零矩阵，\boldsymbol{1}_{m,n}表示大小为m\times n的全1矩阵。此外，y是标签向量[y_1,\cdots,y_N]^\top，\boldsymbol{Y}=\text{diag}(\boldsymbol y)是一个N\times N的对角矩阵，其对角线元素来自y，且X\in\mathbb{R}^{N\times D}是通过连接所有示例获得的矩阵。
我们同样可以对支持向量机（SVM）的对偶版本（12.41）中的项进行一系列收集。为了将对偶SVM表达为标准形式，我们首先需要表示核矩阵K，使得其每个元素为K_{ij} = k(\boldsymbol{x}_i,\boldsymbol{x}_j)。如果我们有明确的特征表示x_i，则我们定义K_{ij} = \langle x_i,x_j \rangle。为了方便表示，我们引入一个矩阵，其所有元素均为零，除了对角线上存储标签的位置，即Y = \operatorname{diag}(\boldsymbol{y})。对偶SVM可以表示为
(12.57)
备注。在7.3.1和7.3.2节中，我们介绍了约束的标准形式为不等式约束。我们将对偶SVM的等式约束表示为两个不等式约束，即
(12.58)
凸优化方法的特定软件实现可能提供了表达等式约束的能力。
\diamondsuit
由于SVM有许多不同的可能视角，因此解决由此产生的优化问题也有许多方法。这里介绍的方法，即将SVM问题表达为标准凸优化形式，在实践中并不常用。SVM求解器的两个主要实现是Chang和Lin（2011）（开源）以及Joachims（1999）。由于SVM具有清晰且定义良好的优化问题，因此可以应用许多基于数值优化技术（Nocedal和Wright，2006）的方法（Shawe-Taylor和Sun，2011）。