7. 半定规划半监督学习

我们讨论了支持向量机（SVM）转导问题，这是一个在未标记样本数上具有指数计算复杂性的组合问题。对于这种组合问题，存在不同的方法，其中包括精确的整数规划方法（仅适用于非常小的样本量，如（Bennett和Demiriz，1999））和从适当选择的起始值开始的局部搜索启发式方法，如第6章“转导支持向量机”中所述的方法，以及引入于（Joachims，1999）（可扩展到大问题大小，但对局部优化很敏感）。

在本章中，我们讨论了（de bie和Cristianini，2004a）中引入的一种替代方法，该方法基于与支持向量机转导相关的优化问题的凸松弛。结果是一个半定规划（SDP）问题，可在多项式时间内进行优化，其解是最优标记的近似值，也是原转导目标函数真最优的边界。为了进一步降低计算的复杂性，我们提出了一种近似方法，可以解决多达1000个未标记样本的转导问题。

最后，我们将公式扩展到更一般的半监督学习环境中，其中一些样本的标签上给出了等价和不等价约束。

7.1 松弛 SVM 转导

在转导问题中，我们提供了一组标记的数据点（训练集），以及一组未标记的数据点（测试集）。我们的兴趣是为第二组找到合适的标签，而不是立即对稍后可能出现的尚未发现的数据点进行预测。SVM 转导问题的处理方法是找到那些测试集标签，在组合训练和测试集上训练SVM后，完整数据集上的裕度最大。这涉及到优化测试集的所有工作，一个具有指数成本的整数规划问题。

原始的让我们回顾一下原始的软边界支持向量机问题（参见（Cristianini和Shawe Taylor，2000年）和（Shawe Taylor和Cristianini，2004年），了解支持向量机和内核方法的介绍：

$min_{\xi_i,w} \ \ \ \frac{1}{2} w^Tw + C\sum_{i=1}^l \xi_i$

s.t. $y_iw^T\xi_i \geq 1-\xi_i$

$\xi_i \geq 0$

这里我们省略了偏置项，我们将在整个章节中这样做。如（Poggio等人，2001）所述，这不是一个问题。这个优化问题只涉及标记的数据点。然后，可将转导SVM写为

$min_{\xi_i,w,Y_u} \ \ \ \frac{1}{2} w^T\cdot w + C\sum_{i=1}^n \xi_i$

s.t. $y_iw^T\xi_i \geq 1- \xi_i$

$\xi_i \geq 0$

$Y_u \in \{ -1,+1 \},$ （7.1）

我们用符号 $Y_u=(y_{l+1},...,y_n)$ 对于测试集标签集，包含测试点标签的列向量，以及训练和测试点总数的n=l+u。正是由于组合约束7.1的存在，使得该优化问题难以精确求解。

双重的 通常，关注对偶问题更有趣，因为它允许我们使用核技巧进行非线性分类和非外部数据分类。标准软边界支持向量机问题由下式给出：

$max_{\alpha_l} \ \ 2\alpha_l^T-\alpha_l^T(K_l\odot Y_lY_l^T)\alpha_l$

s.t. $C\geq \alpha_i \geq 0,$

式中 $\alpha_l = (\alpha_1,...,\alpha_l)$ 是双变量αi的列向量，kl是训练集的核矩阵。有了⊙，元素矩阵产品就意味着。这个优化问题的最优值等于边际的平方反比（加上软边际公式中的附加成本项）。因此，由于我们希望最大限度地提高边际，因此可将转导支持向量机的双重公式写成

$min_Y \ max_{\alpha} \ \ 2\alpha^T1 - \alpha^T(K\odot YY^T)\alpha$

s.t. $C \geq \alpha_i \geq 0$

$Y=\bigg({Y_l \atop Y_u}\bigg)$

$Y_u \in \{-1,1 \}^u$

这里， $\alpha = (\alpha_1,...,\alpha_l,\alpha_{l+1},...,\alpha_n)$ 是包含训练和测试集的双变量的向量， $K$ 是完整的核矩阵， $Y$ 是完整的标签向量。在不失去一般性的情况下，我们假设 $Y$ 的前 $l$ 行和列对应于训练点，最后 $u$ 对应于测试点。同样，正是这种组合约束使得寻找一个精确的解对于合理大小的问题是不可行的。

在不影响解的情况下，我们通过引入矩阵变量 $\Gamma = YY^T$ （我们称之为标签矩阵）来稍微重新表述优化问题。然后，二元公式变成

$min_{\Gamma} \ max_{\alpha} \ \ 2\alpha^T1-\alpha^T(K\odot\Gamma)\alpha$

s.t. $C\geq \alpha_i \geq 0$

$\Gamma=YY^T=\bigg({Y_lY_l^T\atop Y_uY_l^T} \ \ {Y_lY_u^T\atop Y_uY_u^T}\bigg)$ （7.2）

$Y_u \in \{-1,1 \}^u$ （7.3）

所有约束现在都是线性（矩阵）不等式，目标在 $\Gamma$ 中是线性的，在 $\alpha$ 中是凹的。然而，由于约束7.3，问题仍然是一个整数规划，因此整体问题不是凸的。

7.1.1 SDP 问题的松弛

我们将用符号把标签矩阵 $\Gamma$ 写成一个块矩阵

$\Gamma=\bigg({\Gamma_{ll}\atop \Gamma_{ul}} \ \ {\Gamma_{lu}\atop \Gamma_{uu}}\bigg)=\bigg({Y_lY_l^T\atop Y_uY_l^T} \ \ {Y_lY_u^T\atop Y_uY_u^T}\bigg)$ 。

对称约束（ $\Gamma_{uu}=\Gamma_{uu}^T$ 和 $\Gamma_{lu}=\Gamma_{ul}^T$ ）是可以理解的，我们永远不会明确提及它们。现在，观察任何在对角线上有一个秩1的矩阵都可以写成一个向量的外积，其中这个向量只包含1和−1作为它的元素。因此，以下命题成立：

命题 7.1 我们可以通过等价的约束集重新表述约束（7.2）和（7.3）：

$diag(\Gamma)=1$

$rank(\Gamma)=1$

$\Gamma = \bigg({Y_lY_l^T \atop \Gamma_{ul}} \ \ {\Gamma_{lu} \atop \Gamma_{uu}} \bigg).$

这些约束在参数中是线性的，除了秩约束，它显然是非凸的（实际上，秩1的两个矩阵的凸组合通常是秩2）。针对这一问题，本章提出通过将可行域扩展到凸集来松弛约束集，从而在合理的计算时间内完成优化。为了保持良好的性能，它不应该比上面约束指定的非凸集大太多。

注意，约束意味着矩阵 $\Gamma$ 是半正定的（PSD）。因此，我们可以添加 $\Gamma \succeq 0$ 作为附加约束，而不修改问题。然后，松弛就是简单地去掉秩约束。由此产生的松弛优化问题是

$min_{\Gamma} \ max_{\alpha} \ \ \ 2\alpha^T1-\alpha^T(K\odot\Gamma)\alpha$

s.t. $C \geq \alpha_i \geq 0$

$diag(\Gamma)=1$

$T\succeq 0$

$\Gamma = \bigg({Y_lY_l^T \atop \Gamma_{ul}} \ \ {\Gamma_{lu} \atop \Gamma_{uu}} \bigg).$

当然，得到的最优矩阵 $\Gamma$ 的秩不一定再等于1，其元也不等于1和−1。但是，我们可以看到，的每个元仍然位于区间[-1，1]。事实上，由于PSD矩阵的所有主要子矩阵也必须是PSD，因此每个2×2的主要子矩阵都必须是PSD，对于包含对角线上的元素的矩阵，只能对[-1，1]中的非对角线元素实现PSD。此外：

定理 7.2 上述优化问题是凸的。更具体地说，这是一个SDP问题。

证明通过引入符号

$f(\Gamma)=max_{\alpha} \ \ \ 2 \alpha^T1-\alpha^T(K\odot \Gamma)\alpha$

s.t. $C \geq \alpha_i \geq 0,$

我们可以将优化问题重写为

$min_{\Gamma} \ \ \ f(\Gamma)$

s.t. $diag(\Gamma)=1$

$\Gamma \succeq 0$

$\Gamma = \bigg({Y_lY_l^T \atop \Gamma_{ul}} \ \ {\Gamma_{lu} \atop \Gamma_{uu}} \bigg).$

让我们先集中精力于 $f(\Gamma)$ 。对于给定的 $\Gamma \succeq 0$ ，目标是凹的，约束都是线性的，即我们有一个凸优化问题。我们可以很容易地验证斯莱特的约束条件（约束集合中存在严格可行的点，见（Anjos，2001）），表明强对偶性成立。现在我们用拉格朗日乘子 $2\mu \geq 0$ 和 $2\upsilon \geq 0$ 分别为不等式约束 $C \geq \alpha_i$ 和 $\alpha \geq 0$ （ $\mu$ 和 $\upsilon$ 前面的因子 $2$ 用于表示方便）来编写双优化问题。通过调用强对偶性，即双最优与原最优相等，我们现在可以将 $f(\Gamma)$ 写成

$f(\Gamma)= min_{\mu,\upsilon} \ max_{\alpha} \ \ \ 2\alpha^T(1-\mu + \upsilon)-\alpha^T(K\odot\Gamma)\alpha+2C_{\mu}^T1$

s.t. $\mu \geq 0$

$\upsilon \geq 0.$

我们顺便注意到， $1-\mu + \upsilon$ 的最佳值将与 $K \odot \Gamma$ 的零空间正交，因为否则，通过沿该零空间增加的分量 $\alpha$ ，解可以增长到无穷大。现在，关于的最大化可以明确地实现： $\alpha =(K\odot \Gamma)^†(1-\mu + \upsilon)+\alpha_0$ 达到了最优，其中 $\alpha_0$ 是 $K\odot \Gamma$ 的零空间中的一个项。这里†用于表示摩尔-彭罗斯反比。把这个插进去

$f(\Gamma)=min_{\mu,\upsilon} \ \ (1-\mu+\upsilon)^T(K\odot \Gamma)^†(1-\mu+\upsilon)+2C_{\mu}^T1$

s.t. $\mu \geq 0$

$\upsilon \geq 0.$

注意 $\alpha_0$ 已经消失了。引入额外变量 t 之后，

$f(\Gamma)=min_{\mu,\upsilon,t} \ \ \ t$

s.t. $\mu \geq 0$

$\upsilon \geq 0$

$t \geq (1-\mu+\upsilon)^T(K\odot \Gamma)^†(1-\mu+\upsilon)+2C_{\mu}^T1$ .

使用扩展的舒尔补码引理（见附录），我们可以将后一个约束重写为

$\bigg({K\odot\Gamma \atop (1-\mu+\upsilon)^T} \ \ {(1-\mu+\upsilon) \atop t-2C_u^T1}\bigg) \succeq 0$

它是对一个矩阵的PSD约束，该矩阵是变量的线性函数。因此，我们可以将整个优化问题改写为线性（矩阵）不等式下的线性优化问题：

$min_{\Gamma,\mu,\upsilon,t} \ \ \ t$ （7.4）

s.t. $\mu \geq 0$

$\upsilon \geq 0$

$diag(\Gamma)=1$

$\Gamma \succeq 0$

$\bigg({K\odot\Gamma \atop (1-\mu+\upsilon)^T} \ \ {(1-\mu+\upsilon) \atop t-2C_u^T1}\bigg) \succeq 0$

$\Gamma = \bigg({Y_lY_l^T \atop \Gamma_{ul}} \ \ {\Gamma_{lu} \atop \Gamma_{uu}} \bigg).$ （7.5）

这是一个凸优化问题，可在多项式时间内解决（参见例如（Nesterov和Nemirovsky，1994；Vandenberghe和Boyd，1996））。

7.1.2 一些简化

我们可以使用以下两个命题来简化问题：

命题 7.3 $\Gamma$ 的最佳值的形式为

$\Gamma=\bigg({Y_lY_l^T\atop \gamma _uY_l^T} \ \ {Y_l\gamma _u^T\atop \Gamma_{uu}}\bigg)$

证明由扩展的舒尔补引理可知， $\Gamma_{lu}$ 的列空间应与 $Y_lY_l^T$ 的零空间正交。只有当某些向量 $\gamma_u$ 的 $\Gamma_{lu}=Y_l\gamma_u^T$ 时，这才可能发生。

命题 7.4 限制 $\Gamma \succeq 0$ 等价于 $\bigg({1 \atop \gamma_u } \ \ {\gamma_u^T \atop \Gamma_{uu} } \bigg) \succeq 0$ 。

证明我们使用的事实是，一个PSD矩阵的主子阵也是PSD（霍恩和约翰逊，1985年）。通过取一个 $\Gamma$ 的主子矩阵，其中正好包含一行和第一个 $l$ 中的对应列，以及最后所有的 $u$ 行和列，我们可以看到 $\Gamma \succeq 0$ 蕴涵 $\bigg({1 \atop \gamma_u } \ \ {\gamma_u^T \atop \Gamma_{uu} } \bigg) \succeq 0$ 。另一方面，从 $\bigg({1 \atop \gamma_u } \ \ {\gamma_u^T \atop \Gamma_{uu} } \bigg) \succeq 0$ 我们得到

$\bigg({Y_l \atop 0 } \ \ {0 \atop I } \bigg)\bigg({1 \atop \gamma_u } \ \ {\gamma_u^T \atop \Gamma_{uu} } \bigg) \bigg({Y_l \atop 0 } \ \ {0 \atop I } \bigg)^T =\bigg({Y_lY_l^T\atop \gamma _uY_l^T} \ \ {Y_l\gamma _u^T\atop \Gamma_{uu}}\bigg)=\Gamma \succeq 0$

因此，松弛的SVM转导问题的最终公式由下式给出：

$min_{\Gamma_{uu},\gamma_u,\mu,\upsilon,t} \ \ t$

s.t. $\mu \geq 0$

$\upsilon \geq 0$

$diag(\Gamma_{uu})=1$

$\bigg({1 \atop \gamma_u } \ \ {\gamma_u^T \atop \Gamma_{uu} } \bigg) \succeq 0$

$\bigg({K\odot\bigg({Y_lY_l^T\atop \gamma _uY_l^T} \ \ {Y_l\gamma _u^T\atop \Gamma_{uu}}\bigg)\atop (1-\mu+\upsilon)^T} \ \ {(1-\mu+\upsilon) \atop t-2C_u^T1}\bigg) \succeq 0$ 。

这里我们要指出的是，对角线上的等式约束也可以转化为不影响解的不等式约束： $diag(\Gamma_{uu} )\leq 1$ 。实际上，如果对角线小于1，我们可以简单地增加它，而不影响约束或增加目标值。我们将在本章后面使用这个事实。

计算复杂度 变量的总数为 $O(l+u^2)$ ,线性不等式约束的数量是 $O(l+u)$ ，我们有一个大小为 $O(l+u)$ 和一个大小为 $O(u)$ 的 SDP 约束。这就推出一个最糟的计算复杂度 $O((l+u^2)^2(l+u)^{2.5})$ （（参见（Vandenberghe和Boyd，1996）了解SDP问题的计算研究）。

7.1.3 标签向量的估计

如前所述， $\Gamma$ 的最佳值的秩可能不为 1 。因此，它不能为标签向量 $Y_u$ 提供直接的估计。然而，前一节给了我们一个合适的估计值的提示：它只由一列 $\Gamma$ 对应于一个正标记的训练点给出。换言之，我们建议将（阈值）向量 $\gamma_u$ 作为最佳测试标签向量的估计。

其他的方法也可以，比如采用 $\Gamma$ 的显性特征向量，或者采用随机方法。有关此类方法的更多信息，请参阅（Helmberg，2000年）。

7.1.4 转导支持向量机的性能约束

松弛最小化问题的最小值总是小于非松弛问题的最小值。因此，我们的方法立即提供平方反比利润的下限（加上软利润公式的成本项），从而可以实现（软）利润的上限。另一方面，对带有估计测试标签的训练和测试集进行训练的支持向量机的（软）裕度为我们提供了一个下限。如果两个边界都很接近，我们可以确信已经找到了全局最优。

7.2 加速的近似值

在大多数实际情况下，这种松弛的计算复杂性仍然很高。在这一节中，我们提出了一种近似技术，它将以合理的性能损失为代价，大大加快该方法的速度。值得注意的是，这种方法可能具有更广泛的适用性，以加速组合问题的凸松弛，例如最大割问题（参见例如（Helmberg，2000））。

7.2.1 子空间技巧

让我们假设我们可以得到一个包含最优标签向量 $Y$ 的 $R^n$ 的D-维子空间。我们用矩阵 $V \in R^{n \times d}$ 的列来表示这个子空间，这是它的基础。然后，最优标签矩阵 $\Gamma = YY^T$ 表示为 $\Gamma = VMV^T$ ，用 $M\in R^{d\times d}$ 表示一个秩为1的对称矩阵。我们将秩约束松弛到 $SDP$ 约束，然后将其转化为 $M$ 上的类似松弛。通过简单地将所有出现的 $\Gamma$ 替换为式 7.4 和 7.5 中的 $VMV^T$ ，可以得到最终的优化问题，并优化 $M$ 而不是优化 $\Gamma$ ：

$min_{M,\mu,\upsilon,t} \ \ \ t$

s.t. $\mu \geq 0$

$\upsilon \geq 0$

$diag(VMV^T) = 1$

$\bigg({K\odot (VMV^T)\atop (1-\mu+\upsilon)^T} \ \ {(1-\mu+\upsilon) \atop t-2C_u^T1}\bigg) \succeq 0$ 。

7.2.2 查找标签向量附近的子空间

实际上，似乎不可能精确地提出这样的子空间 V 。但是，有几种方法可以近似它，这是基于快速特征值问题（de Bie等人，2004；Kamvar等人，2003；Joachims，2003）。这里，我们选择使用（de bie等人，2004）中提出的方法，该方法基于归一化图切割成本函数的光谱松弛（参见（de bie等人，2005），了解模式识别中的光谱聚类和其他特征值问题）。首先，让我们简要回顾一下基本的光谱聚类方法（没有标签约束）。随后，我们将展示如何约束结果以满足培训标签信息。

基本谱聚类问题由以下广义特征值问题解决：

$(diag(K1)-K)v = \lambda diag(K1)v$

属于小特征值的广义特征向量捕获了数据中的聚类结构（这意味着与数据的良好聚类相对应的标签向量很可能接近这些广义特征向量所跨越的空间）。

为了确保该解决方案尊重给定的训练标签信息，应在 v 上施加额外的约束。这可以通过使用我们称之为标签约束矩阵 $L$ ，定义为

$L=\begin{pmatrix} 1_{l+} & 1_{l+} & 0 \\ 1_{l-} & -1_{l-} & 0 \\ 1_u & 0 &I \end{pmatrix}$ ，

其中 $1_{l+}$ 和 $1_{l-}$ 是包含正的和标记为负的训练点的矢量， $1_u$ 包含 $u$ 点。使用 $L$ ，我们可以根据训练标签信息通过参数化 $v=Lz$ 来约束 $v$ 。然后要解决的广义特征值问题是

$L^\prime ((diag(K1)-K)Lz=\lambda L^\prime diag(K1)Lz.$ （7.6）

相应的约束解为 $v=Lz$ 。关于这种方法的更多细节，我们鼓励读者参考（De Bie等人，2004年）。

标签向量可能接近的一个好的子空间由向量 $v_i = Lz_i$ 构成， $z_i$ 是（7.6）的广义特征向量，对应于 $d$ 个最小特征值（等于零的特征值除外）。因此，我们可以通过将这些 $v_i$ 彼此叠加来构造一个好的矩阵 $V$ 。

我们感兴趣的是解决方案 $\Gamma = VMV^T$ ，在标签矩阵 $\Gamma$ 中，相反标记的训练点 $x_i$ 和 $x_j$ 具有元 $\Gamma(i,j)=\Gamma(j,i)=-\Gamma(i,i)=-\Gamma(j,j)$ 。这可以通过对优化问题施加额外的约束来确保。然而，很容易看出，也可以通过忽略 $L$ 到 $v_i$ 中常数列的贡献，即 $V$ 的第 $i$ 列（即，在计算 $v_i$ 为 $v_i=Lz_i$ 之前，将 $z_i$ 的第一个元设为 $0$ ）来构造性地确保。

使用子空间技巧时，对角 $diag(\Gamma)=1$ 上的约束通常不可行。但是，如上所述，我们可以将它转换为一个不等式约束 $diag(\Gamma) \leq 1$ ，而不需要从根本上改变问题。实际上，如果 $V$ 的维数 $d$ （即列数）等于 $u$ ，无论是否采用子空间近似，得到的最优解之间都没有差别，因为 $\Gamma$ 的整个可行域是相同的。即使只指定了不等式约束，对角线也将等于1。

计算复杂度 约束的数量与非近似优化问题中的约束数量大致相同。然而，我们可能会从自由变量的数量上获得很多，现在是 $O(d^2 +n)$ 。因此，对于固定的 $d$ ，最坏情况下的计算复杂性是 $O(n^{4.5})$ 。 $d$ 的实际值可以选择为可用计算资源可以处理的最大值。

7.3 一般半监督学习设置

到目前为止，我们已经讨论了转导设置，它只是第1章中描述的半监督学习任务之一。不过，我们将简要地指出，如何将本章中的技术直接扩展到处理更一般的设置。

7.3.1 等价与不等价标签约束

如（de bie et al.，2004）和本书第5章所述，我们能够处理更一般的半监督学习设置（另见（de bie et al.，2003）和（shental et al.，2004），在这些设置中，利用相似的约束分别进行维数约减和计算高斯混合模型。想象一下这样一种情况，我们得到了一组指定了标签向量 $Y_i$ 的点。如果我们允许这样的分组只包含一个数据点，那么我们可以假定每个点只属于一个分组，而不会失去一般性。标签向量 $Y_i$ 指示分组中的哪些点被指定为同一类（等价约束），即那些在 $Y_i$ 中具有相同条目1或−1的点，以及哪些点被指定为属于相反的类（当它们在 $Y_i$ 中的条目不同时，一个不等价约束）。在不同的组之间不提供任何信息。这意味着这样一个分组标签向量 $Y_i$ 的整体符号是任意的。

然后，使用上面使用的类似技术，我们可以证明标签矩阵 $\Gamma$ 应该是一个块矩阵，对角块等于 $Y_iY_i^T$ ，非对角块 $(i,j)$ 等于 $\gamma_{i,j}Y_jY_i^T$ ：

$\Gamma = \begin{pmatrix} Y_1Y_1^T & \gamma_{1,2}Y_1Y_2^T & \cdots & \gamma_{1,k}Y_1Y_k^T \\ \gamma_{2,1}Y_2Y_1^T & Y_2Y_2^T & \cdots & \gamma_{2,k}Y_2Y_k^T \\ \vdots & \vdots & \ddots & \vdots \\ \gamma_{k,1}Y_kY_1^T & \gamma_{k,2}Y_kY_2^T & \cdots & Y_kY_k^T \end{pmatrix}$ 。

其中 $\gamma_{i,j}=\gamma_{j,i}$ 是我们必须优化的变量。显然，本章开头解释的转导方案中的标签矩阵是一个特例。现在我们也可以看到标签向量 $Y_i$ 的符号是不相关的：当改变 $Y_i$ 的符号时，最优解只会相应地改变所有 $j$ 的 $\gamma_{i,j}$ 和 $\gamma_{j,i}$ 的符号。

我们要指出的是，这种方法使得用层次的方法来处理转导支持向量机问题成为可能。首先，可以将数据点粗略地集群到许多尊重训练数据的小分组（grouplet）中。然后，在第二阶段，可以使用上面概述的半监督SVM方法。这可以大大降低整个算法的计算成本。

7.3.2 子空间技巧

在这里，子空间技巧也可以以非常类似的方式应用。同样，我们可以依赖（de Bie等人，2004）中描述的方法，该方法也能够处理等价和不等价约束。

7.4 经验结果

对于所有的实现，我们都使用了SeDuMi，一个用于Matlab的通用原始双内点求解器（sturm，1999）。我们只使用硬边支持向量机版本，这是从软边公式得到的 $\mu$ 到0。报告了与 $SVM^{light}$ （Joachims，1999）的比较，并使用默认参数设置。

7.4.1 基础 SDP 松弛

在本小节的所有实验中使用的内核都是径向基函数（RBF）内核，宽度设置为距离最近邻居的所有数据点的平均值。图7.1显示了通过转导SVM的基本SDP松弛解决的转导问题的人工构建示例。只标记了两个数据点，两个类各一个。显然，在这种极端情况下，标准的感应SVM会失效。

此外，由于换流优化与归纳优化的距离太远，使得贪婪策略（如 $SVM^{light}$ ）必然陷入局部最优。实际上，由SDP松弛得到的最优标记处的SVM权重向量的范数为5.7，而对于SVM轻局部最优，则为7.3。因此，由SDP松弛发现的标记获得了更大的裕度。2此外，值得注意的是，松弛优化问题的最优值为35.318608，而（归纳的）SVM最优值在使用未标记数据点的预测标记时仅稍大：35.318613。这表明已经找到了最有可能的最佳标记，因为SVM最优的最佳标记必须位于这些值之间（见第7.1.4节）。

在图7.2中，我们展示了另一个人工示例，其中数据似乎由五个集群组成。我们标记了六个样本，每个集群中至少有一个。SDP松弛和 $SVM^{light}$ 显然成功地为同一簇内的所有数据点分配了相同的标签，并且与该集群中的培训标签一致。图7.3显示了具有不同训练点标签的相同数据集。SDP弛豫发现的转导最佳值略有不平衡：一类38个数据点，另一类42个数据点。因此， $SVM^{light}$ 似乎对两个数据点进行了不同的分类，因为在默认情况下，它试图找到一个解决方案，该解决方案的正负标记测试点比例与培训集中的相同。由SDP松弛得到的最优标记的SVM权重向量范数等于5.92，略小于 $SVM^{light}$ 的权重向量范数5.96。因此，在这里，SDP方法实现了更大的利润。

同样，在这两种情况下，由SDP弛豫的最佳值提供的下限支持已找到最佳标记的结论。对于第一个问题，SDP松弛的最优值为35.338，而预测标签的SVM最优值为35.341。对于第二个问题，最优值分别为32.3934和32.3937。

图 7.1 基本SDP松弛（左）和

SVM^{light}

（右）对人工构建的转导问题的结果。“O”和“X”符号表示负面和正面标记的培训点。其他数据点由算法标记。根据转导算法确定的一组完整的数据点，为支持向量机绘制轮廓线。SDP松弛得到了期望的结果，而

SVM^{light}

显然陷入了局部最优。

7.4.2 子空间近似

我们对中使用的宪法数据集进行了一些实验（De Bie和Cristianini，2004c）。这个数据集包含780篇文章，德语、法语、意大利语和英语等号，它们是相互翻译的。此外，文章以所谓的标题组织。在我们的实验中，我们解决了两个不同的问题：一个是英语+法语文本与意大利语+英语文本的分类，另一个是最大标题（大约包含所有文章的一半）与较小标题的分类。我们测试了不同训练集大小下的SDP松弛和 $SVM^{light}$ 问题，并将结果绘制在图7.4中。使用的内核是规范化的单词包核， $d=0$ 。

显然，在根据文章的标题对文章进行分类的困难问题上， $SVM^{light}$ 优于近似的SDP松弛。这很可能是由于四维子空间太小，无法捕获由于标题不同而产生的精细聚类结构。只有子空间维数 $d$ 大于 $4$ 才能解决这个问题。然而，即使计算成本是D中的多项式，这很快就成为计算上的要求。

另一方面，对于更容易的问题，近似的SDP弛豫优于已经很好的 $SVM^{light}$ 性能，这表明光谱转导方法在这里找到了一个足够接近正确标签向量的子空间。

图 7.2 人工构建的转导问题（左）的基本SDP松弛结果和

SVM^{light}

（右）的结果。在这里，我们将数据点组织在几个小聚类中。在每个聚类中，都会标记一个或两个样本（总共有六个培训点）。对于这两种方法，训练标签决定了集群中所有数据点的测试标签，这在大多数应用程序中都是可取的。

图 7.3 SDP转导（左）和

SVM^{light}

（右）应用于图7.2中的相同数据集，现在使用不同的训练点标签。如果我们根据它们（视觉上）所属的簇中的标记点来标记数据点，这个转导问题就稍微不平衡了：一类是38个点，另一类是42个点。由于

SVM^{light}

将正标记和负标记数据点的分数固定到训练集中的分数（默认情况下），因此将两个数据点从上面留下的集群中分离出来以满足此约束。

图 7.4 受试者操作特征（ROC）评分根据两个分类问题的训练集大小对测试集进行评估。粗线表示容易分类的问题，模糊线表示难分类的问题，根据文章的“标题”对文章进行分类。近似SDP松弛的性能以实线表示，

SVM^{light}

以虚线表示。条形图表示三次随机化的标准差。

7.5 总结与展望

在本章中，我们提出了一种将转导支持向量机作为组合问题的替代方法，而早期的转导方法是基于学习一个合适的度量（Cristianini等人，2002b，a），以及其他使用精确整数规划方法解决这个问题的方法（Bennett和Demiriz，1999）（非常有限可伸缩性）或者使用局部搜索启发式（Joachims，1999），我们的方法包括将组合问题松弛为凸优化问题。更具体地说，由此产生的优化问题是一个SDP，它可以在最坏的多项式时间内解决。SDP和其他凸优化技术的应用似乎是当前机器学习领域的一个非常有前途的研究方向（也可参见（Lanckriet等人，2004b，a））。

虽然松弛的经验结果通常比 $SVM^{light}$ 更好，但不幸的是，可伸缩性仍然有限。为了解决这个问题，我们引入了一种适用于组合问题松弛的近似技术。这种近似的性能很大程度上取决于近似的质量，并报告了与 $SVM^{light}$ 相比的混合经验结果。

未来的工作包括研究是否可以利用问题结构来加速优化问题。一个尚未解决的重要理论问题是，松弛是否允许找到一个边界在未松弛最优的固定常数因子内的解。正如我们指出的，松弛确实为我们提供了一个区间，在这个区间内，真正的最优解必须存在。然而，这个区间的大小并不是先验的，例如最大割问题的松弛（见例如（Helmberg，2000））。最后，从理论上研究子空间近似对最优解的影响是很有意义的。

附录：扩展的舒尔补码引理

我们在没有证明的情况下陈述了舒尔补引理（参见例如（Helmberg，2000））：

引理 7.5 （Schur 补码引理）对对称矩阵 $A\succ 0$ 和 $C \succeq 0$ ：

$C\succeq B^TA^{-1}B \Leftrightarrow \begin{pmatrix} A & B \\ B^T & C \end{pmatrix} \succeq 0$

当矩阵A可能是秩亏时，应使用下列扩展的舒尔补引理。它是标准舒尔补引理的推广，我们在这里提供了一个证明：

引理 7.6 （扩展 Schur 补码引理）对对称矩阵 $A\succ 0$ 和 $C \succeq 0$ ：

${The \ column \ space \ of \ B⊥ \ the \ null \ space \ of \ A \atop C\succeq B^TA^†B }\Bigg \}\Leftrightarrow \begin{pmatrix} A & B \\ B^T & C \end{pmatrix} \succeq 0$ 。

证明我们把 $A$ 的奇异值分解（SVD）写成

$A = (V \ \ V_0) \begin{pmatrix} \land & 0 \\ 0 & 0 \end{pmatrix} (V \ \ V_0)^T = V\land V^T$ ，

式中， $V_0$ 表示 $A,V$ 的零空间的奇异向量，其他奇异向量， $\land$ 是包含 $A$ 的非零奇异值的对角矩阵，即 $\land \succ 0$ 。假定块是兼容的。同样，我们将 $C$ 的 $SVD$ 编写为

$C=(W \ \ W_0) \begin{pmatrix} \Delta & 0 \\ 0 & 0 \end{pmatrix} (W \ \ W_0) ^T = W\Delta W^T$ 。

（ $\Rightarrow$ ）如果 $B$ 的列空间 $\bot$ $V_0$ ，对某些矩阵 $B_v$ 我们可以将 $B$ 写为 $B= VB_v$ 。然后同样的 $B^TA^†B = B^T_v \land ^{-1} B_v$ 。因此，从 $C \succeq B^TA^†B = B^T_v \land ^{-1} B_v$ 和从 $\land \succ 0$ 和 $C\succeq 0$ ，根据 Schur 补码引理得到 $\begin{pmatrix} A & B_v \\ B^T_v & C \end{pmatrix} \succeq 0$ 。在不等式两边同时左乘 $\begin{pmatrix} V & 0 \\ 0 & I \end{pmatrix}$ 和右乘其转置矩阵，得到 $\begin{pmatrix} A & B \\ B^T & C \end{pmatrix} \succeq 0$ 。（ $\Leftarrow$ ）我们将用矛盾的方法证明 $B$ 的列空间与 $A$ 的空空间的正交性。因此，假设 $B$ 的列空间与 $A$ 的零空间 $V_0$ 不正交。则，在 $V_0$ 的扩展空间中存在一个向量 $v_0$ ，使得 $B^Tv_0 = b \neq 0$ 。现在，我们有 $\begin{pmatrix} A & B \\ B^T & C \end{pmatrix} = \begin{pmatrix} V \land V & B \\ B^T & C \end{pmatrix} \succeq 0$ 。因此，对任何向量 $w$ ，分别右乘、左乘矩阵 $\begin{pmatrix} v_0 \\ w \end{pmatrix}$ 和其转置必然结果为一个非负数字： $2b^Tw+w^TVw \geq 0$ 。然而，插入 $w= -C^†b-W_0W^T_0b$ 得到 $2b^Tw+w^TCw = -2b^TW_0W_0^T-b^TC^†b < 0,$ 于是我们就产生了矛盾。因此，我们确定了 $B$ 的列空间与 $V_0$ 的跨度是正交的。

这意味着对某些特定 $B_v$ 我们可以将 $B$ 写为 $B=VB_v$ ，而且

$\begin{pmatrix} A & B \\ B^T & C \end{pmatrix} = \begin{pmatrix} V \land V^T & VB_v \\ B_v^TV^T & C \end{pmatrix} = \begin{pmatrix} V & 0 \\ 0 & I \end{pmatrix} \begin{pmatrix} \land & B_v \\ B_v^T & C \end{pmatrix} \begin{pmatrix} V & 0 \\ 0 & I \end{pmatrix}^T ,$

因此：

$\begin{pmatrix} A & B \\ B^T & C \end{pmatrix} \succeq 0 \Rightarrow \begin{pmatrix} \land & B_v \\ B_v^T & C \end{pmatrix} \succeq 0$ .

因为 $\land \succ 0$ 和 $C \succeq 0$ 我们可以调用舒尔补引理，得出 $C\succeq B_v^T\land^{-1}B_v \succeq 0$ 。然而，从奇异向量的正态性来看 $V^TV =I$ ，因而 $B_v^T\land^{-1}B_v = B_v^TV^TV \land^{-1}V^TVB_v=B^TA^†B$ ，意味着 $B^TA^†B \succeq 0$ 。