1. 对偶问题应用之支持向量机SVM

1.1 SVM

设给定数据集： { ( s i , y i ) : y i ∈ { 1 , − 1 } , i = 1 , ⋯   , m } \{(\mathbf{s}^i,y^i):y^i\in\{1,-1\},i=1,\cdots,m\} {(si,yi):yi∈{1,−1},i=1,⋯,m}，我们想要找到一个决策超平面（decision hyperplane），用方程表示为 ${\mathbf{x}}^T\mathbf{s}+b=0$，使两个类别的样本尽量分开，如图：

SVM的目标就是最大化分类间隔（margin），所以找到 margin 的数学表达式至关重要。

1.1.1 【推导】：分类间隔的数学表达

因为等比例放缩 $\mathbf{x},b$ 不会改变平面位置，也就是说 ${\mathbf{x}}^T\mathbf{s}+b=0$ 和 $c({\mathbf{x}}^T\mathbf{s}+b)=0$ 表示同一个超平面！

设此时的决策超平面是 ${{\mathbf{x}}_0}^T\mathbf{s}+b_0=0$ ，决策上界为 ${{\mathbf{x}}_0}^T\mathbf{s}+b_0=k_0$，因为等比例缩放不改变平面位置，所以决策上界可以重写为 $\frac{1}{k_0}({{\mathbf{x}}_0}^T\mathbf{s}+b_0)=1$，对应的，决策超平面为 $\frac{1}{k_0}({{\mathbf{x}}_0}^T\mathbf{s}+b_0)=0\iff {{\mathbf{x}}_0}^T\mathbf{s}+b_0=0$。

所以无论如何我们都能找到一组 $\mathbf{x},b$ 使得 ${\mathbf{x}}^T{\mathbf{s}}^{+}+b\ge 1$，${\mathbf{x}}^T{\mathbf{s}}^{-}+b\le -1$

我们可以通过缩放 $\mathbf{x},b$ 让正例和负例中距离决策超平面最近的两个点分别落在超平面 $H_1:{\mathbf{x}}^T\mathbf{s}+b=1$ 和 $H_2:{\mathbf{x}}^T\mathbf{s}+b=-1$ 上。

不难推出 $H_1$ 和 $H_2$ 之间的距离，即分类间隔（margin）等于 $\frac{2}{||\mathbf{x}|{|}_2}$

1.1.2 【SVM】约束优化形式

SVM的原优化问题定义：
$$\begin{gathered} \underset{\mathbf{x},b}{\max }\frac{2}{||\mathbf{x}||} \\ \text{s.t. }{y}^i({\mathbf{x}}^T{\mathbf{s}}^i+b)\ge 1 \end{gathered}$$
写成约束优化标准形式：
$$\begin{gathered} \underset{\mathbf{x},b}{\min }\frac{||\mathbf{x}|{|}^2}{2} \\ \text{s.t. }1-y^i({\mathbf{x}}^T{\mathbf{s}}^i+b)\le 0 \end{gathered}$$

1.1.3 【推导】求解

• 将上述约束优化式子转换成拉格朗日函数：

$$L(\mathbf{x},b,\lambda )=\frac{1}{2}||\mathbf{x}|{|}^2+\sum _{i=1}^m{\lambda }_i(1-y^i({\mathbf{x}}^T{\mathbf{s}}^i+b))$$

• 根据KKT条件，有如下推断

KaTeX parse error: Undefined control sequence: \part at position 8: \frac{\̲p̲a̲r̲t̲ ̲L}{\part\mathbf…

KaTeX parse error: Undefined control sequence: \part at position 8: \frac{\̲p̲a̲r̲t̲ ̲L}{\part b}=0\R…

• 由公式(1)我们得到：

$$||\mathbf{x}|{|}^2=||\sum _{i=1}^m{\lambda }_i{y}^i{\mathbf{s}}^i|{|}^2=\sum _{i=1}^m\sum _{j=1}^m{\lambda }_i{\lambda }_j{y}^i{y}^j({\mathbf{s}}^i{)}^T{\mathbf{s}}^i$$

• 于是，拉格朗日函数可以化简为：

$$\begin{gathered} L(\mathbf{x},b,\lambda )=\frac{1}{2}||\mathbf{x}|{|}^2+\sum _{i=1}^m{\lambda }_i-\sum _{i=1}^m{\lambda }_i{y}^i({\mathbf{s}}^i{)}^T\mathbf{x}=\sum _{i=1}^m{\lambda }_i-\frac{1}{2}||\mathbf{x}|{|}^2 \\ \Rightarrow q(\lambda )=\sum _{i=1}^m{\lambda }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\lambda }_i{\lambda }_j{y}^i{y}^j({\mathbf{s}}^i{)}^T{\mathbf{s}}^i \end{gathered}$$

• 上述的分析可以推出下面对偶问题：

max ⁡ λ ∑ i = 1 m λ i − 1 2 ∑ i = 1 m ∑ j = 1 m λ i λ j y i y j ( s i ) T s i s.t.  ∑ i = 1 m λ i y i = 0 , λ i ≥ 0 , i ∈ { 1 , ⋯   , m } . \max\limits_{\lambda}\sum_{i=1}^m\lambda_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\lambda_i\lambda_jy^iy^j(\mathbf{s}^i)^T\mathbf{s}^i\\ \text{s.t. } \sum_{i=1}^m\lambda_iy^i=0,\lambda_i\geq0,i\in\{1,\cdots,m\}. λmax​i=1∑m​λi​−21​i=1∑m​j=1∑m​λi​λj​yiyj(si)Tsis.t. i=1∑m​λi​yi=0,λi​≥0,i∈{1,⋯,m}.

• 不难发现，对偶问题的目标函数是一个二次型目标函数，且约束都为线性约束。一旦我们找到了对偶问题的最优解 ${\lambda }_i^{\ast }$，我们就能得到 $\mathbf{x}={\sum }_{i=1}^m{\lambda }_i^{\ast }{y}^i{\mathbf{s}}^i$。
• 我们称 ${\mathbf{s}}^i$ 为一个支持向量，如果 $y^i({\mathbf{x}}^T{\mathbf{s}}^i+b)=1$，如果 ${\mathbf{s}}^i$ 不是支持向量，根据互补松弛条件，${\lambda }_i=0$，于是 $\mathbf{x}$ 可以被支持向量表示为：$\mathbf{x}=\sum _{i:{\lambda }_i>0}{\lambda }_i{y}^i{\mathbf{s}}^i$