支持向量机

1. 历史背景

支持向量机的发明可以追溯到 20 世纪中叶一系列事件。

1950 年，Aronszajn 发表了 “Theory of Reproducing Kernels”。

1957 年，Frank Rosenblatt 采用上述思想，发明了感知机，一种简单的线性分类器。

1963 年，Vapnik 和 Lerner 发表了 “Generalized Portrait Algorithm”，这是支持向量机的灵感来源。

1992 年，Vladimir Vapnik 和同事 Bernhard Boser、Isabelle Guyon 在 AT&T 贝尔实验室开发出支持向量机算法。

1995 年，Vladimir Vapnik 和 Cortes 开发出软边距（soft margin）分类器。

1998 年，Shawe、Taylor 等人，对硬间隔（hard margin）支持向量机的泛化做出了重大贡献。

2001 年，Vladimir Vapnik 和 Hava Siegelmann 开发出支持向量聚类（Support Vector Clustering，SVC），可以用于未标记的数据。

2. 基础预备

2.1 拉格朗日乘数法^[3]

假设 $f(x,y)$ 与 $g(x,y)$ 都具有连续的一阶导数，即在 $\R^n$ 上是连续可微函数，考虑最优化问题

$${\min f(x,y)} \\ {\displaystyle s.t \quad g(x,y)=0}$$

如果 $f(x,y)$ 与 $g(x,y)$ 在 $(x_0,y_0)$ 处取极值，它们必定相切，因此梯度平行

$$\triangledown f(x,y)=\lambda\triangledown g(x,y)$$

同时必定满足

$$g(x,y)=0$$

将它们联立起来即可求解出 $(x_0,y_0)$ 的取值。

拉格朗日乘数法将上述优化问题构造为一个新的函数称作拉格朗日函数

$${\displaystyle {\mathcal {L}}(x,y,\lambda )=f(x,y)-\lambda g(x,y)}$$

然后直接求解拉格朗日函数的极值点，即

$${\displaystyle { \begin{cases} \triangledown_x{\mathcal {L}}(x,y,\lambda )=0\\ \triangledown_y{\mathcal {L}}(x,y,\lambda )=0\\ \triangledown_\lambda{\mathcal {L}}(x,y,\lambda )=0 \end{cases} } }$$

事实上，这与下式是完全一样的。

$${\displaystyle { \begin{cases} \triangledown f(x,y)=\lambda\triangledown g(x,y)\\ \;\\ g(x,y)=0\\ \end{cases} } }$$

因此拉格朗日乘数法只是一种构造方法，本质是极值点处的两个曲线相切。

2.2 广义拉格朗日乘数法

Harold W. Kuhn 和 Albert W. Tucker 将拉格朗日乘数法进行了推广，在满足 Karush-Kuhn-Tucker (KKT) 条件的情况下，允许不等式约束。

2.2.1 原始问题

考虑如下最优化问题，$f,g,h$ 都具有连续的一阶导数，即在 $\R^n$ 上是连续可微函数

$$\begin{aligned} &\min_{\mathbf x} f(\mathbf x) \\ \displaystyle s.t \quad &g_i(\mathbf x)\le 0 & i=1,2,\dots,k\\ &h_j(\mathbf x) =0 & j=1,2,\dots,l\\ \end{aligned}$$

构造如下拉格朗日函数

$${\displaystyle L(\mathbf x,\mu ,\lambda )=f(\mathbf x)+\sum _{i=1}^{k}\mu _{i}g_{i}(\mathbf x)+\sum _{j=1}^{l }\lambda _{j}h_{j}(\mathbf x)}$$

其中，$\mu_i,\lambda_j$ 是拉格朗日乘子。考虑如下目标函数

$$\theta_{\mathcal P}(\mathbf x)=\max_{\mu,\lambda:\mu_i\ge 0}L(\mathbf x,\mu ,\lambda )$$

这里，$\mathcal P$ 代表原始（primal）问题，相对的是对偶（dual）问题 $\mathcal D$。

假设给定 $\mathbf x$，如果 $\mathbf x$ 不满足任一约束条件，即存在 $g_i(\mathbf x)> 0$ 或者 $h_j(\mathbf x)\ne0$，会导致

$$\theta_{\mathcal P}(\mathbf x)=\max_{\mu,\lambda:\mu_i\ge 0}L(\mathbf x,\mu ,\lambda )=+\infty$$

因为，当 $g_i(\mathbf x)> 0$ 时，$\theta_{\mathcal P}(\mathbf x)$ 随 $\mu_i$ 的增大而增大，最终趋于正无穷；当 $h_j(\mathbf x)\ne0$ 时，如果 $h_j(\mathbf x)>0$，$\theta_{\mathcal P}(\mathbf x)$ 随 $\lambda_j$ 的增大而增大，反之随 $\lambda_j$ 的减小而增大，最终都趋于正无穷。

如果 $\mathbf x$ 满足约束条件，可以得到 $\theta_{\mathcal P}(\mathbf x)=f(\mathbf x)$。因此

$${\displaystyle \theta_{\mathcal P}(\mathbf x)={ \begin{cases} f(\mathbf x)&\text{if }\mathbf x \text{ satisfies primal constraints}\\ +\infty&\text{otherwise} \end{cases} } }$$

所以，对于满足原始约束的 $\mathbf{x}$ 的所有值，$\theta_{\mathcal P}(\mathbf x)$ 与最优化问题中的目标值相同，如果不满足原始约束，则值为正无穷大。因此，如果考虑最小化问题

$$\min_{\mathbf x}\theta_{\mathcal P}(\mathbf x)=\min_{\mathbf x}\max_{\mu,\lambda:\mu_i\ge 0}L(\mathbf x,\mu ,\lambda )$$

它与原始最优化问题是等价的，即具有相同的解。定义原始最优问题的最优解为

$$p^*=\min_{\mathbf{x}}\theta_{\mathcal P}(\mathbf x)$$

2.2.2 对偶问题

定义对偶问题

$$\theta_{\mathcal D}(\mu,\lambda)=\min_{\mathbf{x}}L(\mathbf x,\mu ,\lambda )$$

再将上式极大化

$$\max_{\mu,\lambda:\mu_i\ge 0}\theta_{\mathcal D}(\mu,\lambda)=\max_{\mu,\lambda:\mu_i\ge 0}\min_{\mathbf x}L(\mathbf x,\mu ,\lambda )$$

定义对偶问题的最优值

$$d^*=\max_{\mu,\lambda:\mu_i\ge 0}\theta_{\mathcal D}(\mu,\lambda)$$

用函数值集合理解对偶问题^[7]。

将问题简单化，只考虑一个不等式约束，假设 $f,g$ 映射后的值为 $a,b$，那拉格朗日函数即为 $a+\lambda b$，其中 $b\le 0$。原始问题中是先对于不同的 $\mathbf{x}$，即每一组 $a,b$ 都求最大化的 $a+\lambda b$，由于 $b\le 0$，因此 $\lambda=0$ 时，$a+\lambda b$ 值最大，因此然后只需要再最小化 $a$ 即 $f(\mathbf{x})$ 即可。

反之，在对偶问题中，则是对于每一个斜率 $\lambda$，都求得一个最小化的 $a+\lambda b$，最后再在所有 $\lambda$ 中选一个能使 $a+\lambda b$ 最大化的即可，而 $a+\lambda b$ 实际上是该直线的截距。

2.2.3 原始问题与对偶问题关系

定理1. （弱对偶性） 若原始问题和对偶问题都有最优值，则

$$d^*=\max_{\mu,\lambda:\mu_i\ge 0}\min_{\mathbf x}L(\mathbf x,\mu ,\lambda )\le \min_{\mathbf x}\max_{\mu,\lambda:\mu_i\ge 0}L(\mathbf x,\mu ,\lambda )=p^*$$

证明：对于任意的 $\mu ,\lambda$

$$\theta_{\mathcal D}(\mu,\lambda)=\min_{\mathbf{x}}L(\mathbf x,\mu ,\lambda )\le L(\mathbf x,\mu ,\lambda )$$

对于任意的 $\mathbf x$，有

$$\theta_{\mathcal P}(\mathbf x)=\max_{\mu,\lambda:\mu_i\ge 0}L(\mathbf x,\mu ,\lambda )\ge L(\mathbf x,\mu ,\lambda )$$

因此

$$\theta_{\mathcal D}(\mu,\lambda)\le \theta_{\mathcal P}(\mathbf x)$$

已知原始问题和对偶问题均有最优值，因此

$$\max_{\mu,\lambda:\mu_i\ge 0}\theta_{\mathcal D}(\mu,\lambda)\le \min_{\mathbf x}\theta_{\mathcal P}(\mathbf x)$$

即

$$d^*=\max_{\mu,\lambda:\mu_i\ge 0}\min_{\mathbf x}L(\mathbf x,\mu ,\lambda )\le \min_{\mathbf x}\max_{\mu,\lambda:\mu_i\ge 0}L(\mathbf x,\mu ,\lambda )=p^*$$

定理2. （强对偶性的充分条件） 如果函数 $f,g_i$ 是凸函数，$h_j$ 是仿射函数，并且不等式约束 $g$ 是严格执行的，即存在 $\mathbf{x}$ 对所有 $i$ 有 $g_i(\mathbf{x})<0$，则存在 $\mathbf{x}^,\mu^,\lambda^$，使 $\mathbf{x}^$ 是原始问题的解，$\mu^,\lambda^$ 是对偶问题的解，并且

$$p^*=d^*=L(\mathbf{x}^*,\mu^*,\lambda^*)$$

定理3. （强对偶性的充要条件） 如果函数 $f,g_i$ 是凸函数，$h_j$ 是仿射函数，并且不等式约束 $g$ 是严格执行的，则存 $\mathbf{x}^$ 和 $\mu^,\lambda^$ 分别是原始问题和对偶问题的解的充要条件是 $\mathbf{x}^,\mu^,\lambda^$ 满足如下 Karush-Kuhn-Tucker (KKT) 条件

$$\triangledown_{\mathbf{x}}L(\mathbf{x}^*,\mu^*,\lambda^*)=0$$ $$\mu_ig_i(\mathbf{x}^*)=0,\quad i=1,2,\cdots,k$$ $$g_i(\mathbf{x}^*)\le0,\quad i=1,2,\cdots,k$$ $$\mu_i^*\ge0,\quad i=1,2,\cdots,k$$ $$h_j(\mathbf{x}^*)=0,\quad j=1,2,\cdots,l$$

后面三个关系式其实就是约束条件。第二个关系式是对偶互补条件，类似于线性规划中互补松弛性，当影子价格 $\mu_i^>0$，则 $g_i(\mathbf{x}^)=0$，如果 $g_i(\mathbf{x}^)<0$，则 $\mu_i^=0$。

3. 基本概念

假设训练数据集：

$$T=\{(\mathbf x_1,y_1),(\mathbf x_2,y_2),...,(\mathbf x_N,y_N)\}$$

其中，${\displaystyle \mathbf x_i\in \mathcal{X}\subseteq R^n}$ 表示实例的特征向量，$y\in \mathcal{Y}=\{+1,-1\}$ 表示实例的类别。

在感知机中，通过超平面对线性可分的数据进行分类，超平面为

$${\displaystyle f(\mathbf x)=\mathbf w\cdot \mathbf x+b}$$

超平面将特征空间分为两部分，法向量指向的一侧为正类，另一侧为负类，即 $\mathbf w\cdot \mathbf x+b > 0$ 时为正，反之为负。

在感知机算法中，满足条件的超平面有多个，而支持向量机就是寻找最优的一个。至于哪一个是最优的，直观的想法就是距离正负实例都尽可能的远，可能最终影响到超平面位置的只有两个实例，距离超平面最近的一正一负两实例。

实例到超平面的距离还有另一种解释，就是分类的确信程度，距离越远表示分类的确信度越大，距离越近表示确信度越小。为了衡量实例到超平面的距离，引入函数间隔和几何间隔。

对于分离超平面 $\mathbf w\cdot \mathbf x+b=0$，定义样本点 $(\mathbf x_i,y_i)$ 函数间隔 $\hat{\gamma}_i$ 为

$$\hat{\gamma}_i = y_i(\mathbf w\cdot \mathbf x_i+b)$$

样本集 $T$ 关于超平面的函数间隔则为每个样本点函数间隔的最小值

$$\hat{\gamma}=\min_i \hat{\gamma}_i$$

可以发现，当超平面分类正确时，$w\cdot \mathbf x+b$ 与 $y_i$ 同号，函数间隔为正，当分类错误时，函数间隔为负。

在感知机中使用的损失函数就是函数间隔，而函数间隔的问题在于并没有正常反映样本点到超平面的距离，例如 $\mathbf w,b$ 同时扩大 $2$ 倍，超平面并没有改变，但同一样本点的函数距离也扩大了 $2$ 倍。因此，在感知机中其实只用到了 $y_i(\mathbf w\cdot \mathbf x_i+b)$ 的符号，当所有样本正确分类则结束算法，在支持向量机中想要考虑距离因素则必须引入几何间隔。

定义几何间隔

$$\gamma_i=\frac{y_i(\mathbf w\cdot \mathbf x_i+b)}{\left\|\mathbf w\right\|}$$

同理，样本集 $T$ 关于超平面的几何间隔为每个样本点几何间隔的最小值

$${\gamma}=\min_i {\gamma}_i$$

几何间隔与函数间隔存在如下关系

$$\gamma=\frac{\hat{\gamma}}{\left\|\mathbf w\right\|}$$

如果可以保证 ${\left|\mathbf w\right|}=1$，则几何间隔与函数间隔相等，简化计算。

4. 线性可分：硬间隔支持向量机

支持向量机的核心思想就是在满足正确分类的情况下，同时希望超平面的几何间隔尽可能大，这就是一个条件约束问题。

$$\begin{aligned} \max\quad &\gamma \\ \displaystyle s.t \quad &\frac{y_i(\mathbf w\cdot \mathbf x_i+b)}{\left\|\mathbf w\right\|}\ge \gamma \quad i=1,2,\dots,N \end{aligned}$$

根据几何间隔与函数间隔的关系，上式替换为

$$\begin{aligned} \max\quad &\frac{\hat{\gamma}}{\left\|\mathbf w\right\|} \\ \displaystyle s.t \quad &y_i(\mathbf w\cdot \mathbf x_i+b)\ge \hat{\gamma}\quad i=1,2,\dots,N \end{aligned}$$

上面的约束问题中，$\hat{\gamma}$ 的取值实际上不影响解的结果，$\mathbf w,b$ 同时扩大 $\lambda$ 倍，$\hat{\gamma}$ 则变为 $\lambda\hat{\gamma}$，对于目标函数来说并没有改变。因此，取 $\hat{\gamma}=1$，同时将最大化 $\displaystyle \frac{1}{\left|\mathbf w\right|}$ 转换为最小化 $\displaystyle\frac{1}{2}\left|\mathbf w\right|^2$，因此最终线性可分支持向量机的最优化问题为

$$\begin{aligned} \min\quad &\frac{1}{2}\left\|\mathbf w\right\|^2 \\ \displaystyle s.t \quad &y_i(\mathbf w\cdot \mathbf x_i+b)-1\ge 0\quad i=1,2,\dots,N \end{aligned}$$

该优化问题是具有凸二次目标函数，同时只有线性约束的优化问题。

求解该凸二次优化问题，需要用到拉格朗日乘子法，并转换为对偶问题求解，优点在于对偶问题更容易求解，且自然引入核函数的概念。

首先构建拉格朗日函数

$$L(\mathbf w,b,\alpha)=\frac{1}{2}\left\|\mathbf w\right\|^2-\sum_{i=1}^N\alpha_{i}\left[y_{i}(\mathbf{w}\cdot \mathbf{x}_{i}+b)-1\right]$$

原始问题转变为

$$\min_{\mathbf w,b}\max_{\alpha\ge 0}L(\mathbf w,b,\alpha)$$

对偶问题即为

$$\max_{\alpha\ge 0}\min_{\mathbf w,b}L(\mathbf w,b,\alpha)$$

第一步先求 $\displaystyle \min_{\mathbf w,b}L(\mathbf w,b,\alpha)$，分别对 $\mathbf w,b$ 求偏导数并令其等于 $0$。

$$\triangledown_{\mathbf w}L(\mathbf w,b,\alpha)=\mathbf w-\sum_{i=1}^N \alpha_{i}y_i\mathbf{x}_{i}=0$$ $$\triangledown_{b}L(\mathbf w,b,\alpha)=-\sum_{i=1}^N \alpha_{i}y_i=0$$

得到

$$\mathbf w=\sum_{i=1}^N \alpha_{i}y_i\mathbf{x}_{i}$$ $$\sum_{i=1}^N \alpha_{i}y_i=0$$

将 $\mathbf{w}$ 的表达式带入拉格朗日函数

$$\begin{aligned} L(\mathbf w,b,\alpha)&=\frac{1}{2}(\sum_{i=1}^N \alpha_{i}y_i\mathbf{x}_{i})^2-\sum_{i=1}^N\alpha_{i}\left[y_{i}(\sum_{j=1}^N \alpha_{j}y_j\mathbf{x}_{j}\cdot \mathbf{x}_{i}+b)-1\right]\\ &=-\frac{1}{2}(\sum_{i=1}^N \alpha_{i}y_i\mathbf{x}_{i})\cdot(\sum_{j=1}^N \alpha_{j}y_j\mathbf{x}_{j})+\sum_{j=1}^N \alpha_i \end{aligned}$$

第二步再求 $\displaystyle\max_{\alpha\ge 0}\min_{\mathbf w,b}L(\mathbf w,b,\alpha)$，优化对偶问题为

$$\begin{aligned} \max_{\alpha} &-\frac{1}{2}(\sum_{i=1}^N \alpha_{i}y_i\mathbf{x}_{i})\cdot(\sum_{j=1}^N \alpha_{j}y_j\mathbf{x}_{j})+\sum_{j=1}^N \alpha_i \\ \displaystyle s.t \quad &\sum_{i=1}^N \alpha_{i}y_i=0 \\ &\alpha_i\ge 0,\qquad i=1,2,\cdots,N \\ \end{aligned}$$

对目标函数进行变换，改变正负号，由求最大改为最小，得到等价对偶优化问题

$$\begin{aligned} \min_{\alpha}\quad &\frac{1}{2}(\sum_{i=1}^N \alpha_{i}y_i\mathbf{x}_{i})\cdot(\sum_{j=1}^N \alpha_{j}y_j\mathbf{x}_{j})-\sum_{j=1}^N \alpha_i \\ \displaystyle s.t \quad &\sum_{i=1}^N \alpha_{i}y_i=0 \\ &\alpha_i\ge 0,\qquad i=1,2,\cdots,N \\ \end{aligned}$$

假设求得对偶最优化问题的解为 $\alpha^*$，根据 KKT 条件有

$$\triangledown_{\mathbf{w}}L(\mathbf w^*,b^*,\alpha^*)=\mathbf w^*-\sum_{i=1}^N \alpha^*_{i}y_i\mathbf{x}_{i}=0$$ $$\triangledown_{b}L(\mathbf w^*,b^*,\alpha^*)=-\sum_{i=1}^N \alpha^*_{i}y_i=0$$ $$\alpha^*_i[y_i(\mathbf w^*\cdot \mathbf x_i+b^*)-1]=0,\quad i=1,2,\cdots,N$$ $$y_i(\mathbf w^*\cdot \mathbf x_i+b^*)-1\ge0,\quad i=1,2,\cdots,N$$ $$\alpha_i^*\ge0,\quad i=1,2,\cdots,N$$

根据第一个公式可以得到

$$\mathbf w^*=\sum_{i=1}^N \alpha^*_{i}y_i\mathbf{x}_{i}$$

利用反证法可以知道一定存在一个 $\alpha_j^*>0$，因此根据第三个公式也就是互补性可知

$$y_j(\mathbf w^*\cdot \mathbf x_j+b^*)-1=0$$

联立两个式子可以得到

$$b^*=y_j-\sum_{i=1}^N \alpha^*_{i}y_i\mathbf{x}_{i}\cdot \mathbf x_j$$

分离超平面

$$\begin{aligned} f(\mathbf x)&=\mathbf w^*\cdot \mathbf x+b^*\\ &=\sum_{i=1}^N \alpha^*_{i}y_i\mathbf{x}_{i}\cdot \mathbf x+y_j-\sum_{i=1}^N \alpha^*_{i}y_i\mathbf{x}_{i}\cdot \mathbf x_j\\ &=\sum_{i=1}^N \alpha^*_{i}y_i\mathbf{x}_{i}\cdot (\mathbf x-\mathbf x_j) + y_i \end{aligned}$$

由以上可知，$\mathbf w^$ 和 $b^$ 只依赖于训练数据中对应 $\alpha_j^*>0$ 的样本点 $(\mathbf{x}_i,y_i)$，而其他样本点则没有影响，这个样本点就称为支持向量。

与线性规划相类比，其实这个实例点就是起到桎梏作用的点，如同工厂生产中最紧缺的材料，再增加减少其它材料都不会影响最优解，只有增减该种材料才会影响结果，在支持向量机图中就是移动距离超平面最近的点，自然会影响到超平面的位置。

5. 线性近似可分：软间隔支持向量机

在上述硬间隔支持向量机中，所有的约束都是硬约束，如果没有满足所有约束条件的可行解的话就求不出结果。所以，对应于线性近似可分的数据集，如果只有少数异常点无法通过分离超平面区分出来，那么可以给这些不满足的约束条件一个惩罚，最终求出一个近似最优解。其实，这就是线性规划中的目标规划，将原本的硬约束条件改为软约束条件即可。

根据上述思想，软间隔支持向量机原始问题为

$$\begin{aligned} \min\quad &\frac{1}{2}\left\|\mathbf w\right\|^2 + C\sum_{i=1}^N\xi_i \\ \displaystyle s.t \quad &y_i(\mathbf w\cdot \mathbf x_i+b)\ge 1-\xi_i\quad i=1,2,\dots,N \\ &\xi_i\ge0\quad i=1,2,\dots,N \end{aligned}$$

拉格朗日函数为

$$L(\mathbf w,b,\xi,\alpha,\mu)=\frac{1}{2}\left\|\mathbf w\right\|^2+ C\sum_{i=1}^N\xi_i -\sum_{i=1}^N\alpha_{i}\left[y_{i}(\mathbf{w}\cdot \mathbf{x}_{i}+b)-1+\xi_i\right]-\sum_{i=1}^N \mu_i\xi_i$$

原始问题转换为

$$\min_{\mathbf w,b,\xi}\max_{\alpha\ge 0,\mu\ge 0}L(\mathbf w,b,\xi,\alpha,\mu)$$

因此对偶问题为

$$\max_{\alpha\ge 0,\mu\ge 0}\min_{\mathbf w,b,\xi}L(\mathbf w,b,\xi,\alpha,\mu)$$

先求 $\displaystyle\min_{\mathbf w,b,\xi}L(\mathbf w,b,\xi,\alpha,\mu)$，对三个变量 $\mathbf w,b,\xi$ 分别求偏导并令其等于 $0$

$$\triangledown_{\mathbf w}L(\mathbf w,b,\xi,\alpha,\mu)=\mathbf w-\sum_{i=1}^N \alpha_{i}y_i\mathbf{x}_{i}=0$$ $$\triangledown_{b}L(\mathbf w,b,\xi,\alpha,\mu)=-\sum_{i=1}^N \alpha_{i}y_i=0$$ $$\triangledown_{\xi_i}L(\mathbf w,b,\xi,\alpha,\mu)=C-\alpha_i-\mu_i=0$$

将结果带入 $L$ 得

$$\begin{aligned} L(\alpha,\mu)&=\frac{1}{2}(\sum_{i=1}^N \alpha_{i}y_i\mathbf{x}_{i})^2-\sum_{i=1}^N\alpha_{i}\left[y_{i}(\sum_{j=1}^N \alpha_{j}y_j\mathbf{x}_{j}\cdot \mathbf{x}_{i}+b)-1\right]+\sum_{i=1}^N(C-\alpha_i-\mu_i)\xi_i\\ &=-\frac{1}{2}(\sum_{i=1}^N \alpha_{i}y_i\mathbf{x}_{i})\cdot(\sum_{j=1}^N \alpha_{j}y_j\mathbf{x}_{j})+\sum_{j=1}^N \alpha_i \end{aligned}$$

再求 $\displaystyle\max_{\alpha\ge 0,\mu\ge 0}L(\alpha,\mu)$，优化对偶问题为

$$\begin{aligned} \max_{\alpha,\mu} &-\frac{1}{2}(\sum_{i=1}^N \alpha_{i}y_i\mathbf{x}_{i})\cdot(\sum_{j=1}^N \alpha_{j}y_j\mathbf{x}_{j})+\sum_{j=1}^N \alpha_i \\ \displaystyle s.t \quad &\sum_{i=1}^N \alpha_{i}y_i=0 \\ &C-\alpha_i-\mu_i=0\\ &\alpha_i\ge 0\\ &\mu_i\ge 0,\qquad i=1,2,\cdots,N \\ \end{aligned}$$

将目标函数极大转为极小，同时将 $\mu_i$ 的关系式带入消去 $\mu_i$，得到等价优化问题

$$\begin{aligned} \min_{\alpha}\quad &\frac{1}{2}(\sum_{i=1}^N \alpha_{i}y_i\mathbf{x}_{i})\cdot(\sum_{j=1}^N \alpha_{j}y_j\mathbf{x}_{j})-\sum_{j=1}^N \alpha_i \\ \displaystyle s.t \quad &\sum_{i=1}^N \alpha_{i}y_i=0 \\ &0\le\alpha_i\le C,\qquad i=1,2,\cdots,N \\ \end{aligned}$$

假设求得的最优解为 $\mathbf w^,b^,\xi^,\alpha^,\mu^*$

参考

1. Support Vector Machine History
2. 构造拉格朗日函数有何意义？-zhihu
3. 如何理解拉格朗日乘子法？-zhihu
4. Lagrange multiplier - Wikipedia
5. Karush–Kuhn–Tucker conditions - Wikipedia
6. 为什么我们要考虑线性规划的对偶问题？-zhihu
7. 如何通俗地讲解对偶问题，尤其是拉格朗日对偶 lagrangian duality？-zhihu

8. Logistic function - Wikipedia
9. 逻辑回归原理小结 - 刘建平

---

Machine Learning

2022-03-17