Machine Learning-支持向量機(jī)（SVM）(上)

支持向量機(jī)（SVM）

簡(jiǎn)介

支持向量機(jī)（SVM）做為一種二分類算法斜姥，與其他分類算法相比，在小的數(shù)據(jù)集上沧竟，分類效果好铸敏，泛化能力強(qiáng)，且可以處理非線性的分類問題屯仗，支持向量回歸機(jī)(SVR)是支持向量機(jī)在回歸問題上的一種推廣搞坝。半監(jiān)督的支持向量機(jī)(S3VM)是支持向量機(jī)在半監(jiān)督學(xué)習(xí)上的一種推廣搔谴。

本文主要真對(duì)SVM魁袜，系統(tǒng)的在數(shù)學(xué)上進(jìn)行理論推導(dǎo)，要想在數(shù)學(xué)上推導(dǎo)SVM，首先要介紹三個(gè)內(nèi)容：凸二次規(guī)劃峰弹、拉格朗日乘數(shù)法和KKT店量、拉格朗日對(duì)偶問題。

凸二次規(guī)劃（convex quadratic programming）

凸二次規(guī)劃從名字上既可以理解鞠呈，什么是凸融师，其目標(biāo)函數(shù)二階導(dǎo)數(shù)大于等于零（既目標(biāo)函數(shù)為凸函數(shù)），且可行域是凸集蚁吝，什么是二次旱爆，其目標(biāo)函數(shù)最高是二次的，什么是規(guī)劃窘茁，其解決的問題是給定條件下求目標(biāo)函數(shù)的最值怀伦。為什么要單獨(dú)討論他，是因?yàn)楹芏鄶?shù)學(xué)模型都是凸二次規(guī)劃模型山林，如：投資組合中的馬科維茨模型房待。凸二次規(guī)劃具體的數(shù)學(xué)定義如下：

考慮如下優(yōu)化問題：
$\min_{x} \frac{1}{2}x^TQx+c^Tx$
$s.t. Ax\le b$

若其中A是有限維實(shí)矩陣，Q為半正定實(shí)矩陣驼抹。

上面給出的就是凸二次規(guī)劃的定義。

對(duì)于凸二次規(guī)劃給出幾點(diǎn)說明

1、約束條件等式問題

標(biāo)準(zhǔn)的二次規(guī)劃問題約束條件中并沒有等式約束丰包，但是當(dāng)約束條件中出現(xiàn)等式是担汤，可以將這個(gè)等式轉(zhuǎn)化為兩個(gè)不等式約束，如 $ax=b$ 可以轉(zhuǎn)化為 $ax \le b$ 和 $-ax \le -b$ 兩個(gè)不等式明也，所以約束條件中可以含有等式镣隶。

2、矩陣Q的問題

為什么Q是半正定矩陣問題就是凸問題诡右。只要證明 $f(x)= \frac{1}{2}x^TQx+c^Tx$ 是凸函數(shù)即可安岂，

對(duì)于任意的 $x_1,x_2$ ，有：
$\begin{align} f(\frac {x_1+x_2}{2})&= \frac{1}{2}(\frac{x_1+x_2}{2})^TQ(\frac{x_1+x_2}{2})+c^T(\frac{x_1+x_2}{2}) \\ &=\frac{1}{8}x_1^TQx_1+\frac{1}{2} c^Tx_1 +\frac{1}{8}x_2^TQx_2+\frac{1}{2} c^Tx_2 + \frac{1}{8}x_1^TQx_2+\frac{1}{8}x_2^TQx_1 \end{align}$

而：
$\begin{align} \frac {f(x_1)+f(x_2)}{2}=\frac{1}{4}x_1^TQx_1+\frac{1}{2} c^Tx_1 +\frac{1}{4}x_2^TQx_2+\frac{1}{2} c^Tx_2 \end{align}$

所以上面兩公式相減帆吻，得到域那。
$\begin{align} \frac {f(x_1)+f(x_2)}{2}- f(\frac {x_1+x_2}{2}) &=\frac{1}{8}x_1^TQx_1+\frac{1}{8}x_2^TQx_2 - \frac{1}{8}x_1^TQx_2-\frac{1}{8}x_2^TQx_1\\ &=\frac{1}{8}(x_1-x_2)^TQ(x_1-x_2)^T \end{align}$

若Q是半正定矩陣，則上式大于零猜煮，有：
$\frac {f(x_1)+f(x_2)}{2} \ge f(\frac {x_1+x_2}{2})$

所以問題是凸的次员。

3、矩陣Q到底是什么王带。

對(duì)于 $f(x)= \frac{1}{2}x^TQx+c^Tx$

對(duì)向量x的各個(gè)分量求二階導(dǎo)淑蔚，
$\frac{\partial^{2}f}{\partial x_i ^2}=q_{i,i}$
$\frac{\partial^{2}f}{\partial x_i \partial x_j}=q_{i,j}$

其中 $q_{i,j}$ 是Q的第i行第j列的元素。

所以其實(shí)Q是一個(gè)黑森矩陣愕撰，是描述這個(gè)超曲面的局部曲率刹衫。

上面就是凸二次規(guī)劃問題的介紹醋寝，求解這個(gè)凸二次規(guī)劃問題常用的方法為橢球法，內(nèi)點(diǎn)法和拉格朗日法带迟。下面詳細(xì)介紹拉格朗日乘數(shù)法音羞。

拉格朗日乘數(shù)法

其實(shí)每個(gè)模型的特點(diǎn)，都與其獨(dú)特的數(shù)學(xué)推導(dǎo)過程仓犬，息息相關(guān)嗅绰，在推導(dǎo)中用的方法一定程度上決定了最后模型的特點(diǎn)，如Adaboost只能用指數(shù)損失函數(shù)推導(dǎo)搀继，SVM也一樣窘面，其最后的特點(diǎn)完全是由推導(dǎo)過程中，使用了拉格朗日乘數(shù)法和KKT條件所決定的叽躯。

對(duì)于一般無約束的的函數(shù)優(yōu)化問題民镜，我們可以直接求導(dǎo)，令導(dǎo)數(shù)等于零险毁，找到極值點(diǎn)制圈，再驗(yàn)證最大值最小值。而對(duì)于有約束的函數(shù)優(yōu)化問題畔况，可以使用拉格朗日乘數(shù)法鲸鹦，將其轉(zhuǎn)化為無約束的函數(shù)最優(yōu)化問題。

但需要特別指出的是跷跪，轉(zhuǎn)化成的無約束的函數(shù)最優(yōu)化馋嗜，也只能求其極值，極值和最值還是有一定差別吵瞻，一定要理解這個(gè)差別葛菇，拉格朗日乘數(shù)法求得的是極值，并不是最值橡羞，還有其并不能確定極值一定存在眯停，即使轉(zhuǎn)化前的目標(biāo)函數(shù)是凸函數(shù)，由于存在約束條件卿泽，其也可能沒有極值莺债。轉(zhuǎn)化后的目標(biāo)函數(shù)如果是凸函數(shù)，由于沒有約束條件签夭，那必存在機(jī)值齐邦。以下討論在極值存在下討論。

其具體的推導(dǎo)如下：

先考慮只有等式約束的優(yōu)化問題第租；

$\min_{x} f(x)$
$s.t. g(x)=0$

其中x是一個(gè)n維向量措拇， $x=(x_1,x_2,...x_n)$ ,這里f(x)需滿足一個(gè)條件，即f(x)對(duì)向量x各個(gè)分量的偏導(dǎo)數(shù)連續(xù)慎宾。很明顯凸二次規(guī)劃的目標(biāo)函數(shù)滿足之一條件丐吓。

對(duì)于g(x)=0,是一個(gè)n維空間的超曲面浅悉，我們先討論g(x)=0這個(gè)超曲面的一些性質(zhì)。對(duì)于超曲面上的任意一個(gè)點(diǎn) $x=(x_1,x_2,...x_n)$ 汰蜘，這里討論的g(x)都是連續(xù)可導(dǎo)的，不連續(xù)之宿，不可導(dǎo)的g(x)不做討論族操。由于這個(gè)超曲面是連續(xù)可導(dǎo)，所以其上對(duì)于任意的點(diǎn) $x=(x_1,x_2,...x_n)$ 比被，都存在一個(gè)小的領(lǐng)域U色难，在鄰域U里面過點(diǎn) $x=(x_1,x_2,...x_n)$ 的任意曲線，都可以參數(shù)化表示等缀。

設(shè)過點(diǎn) $x=(x_1,x_2,...x_n)$ 的任意曲線的參數(shù)表達(dá)式為：
$r(t)=(x_1(t),x_2(t),...x_n(t))$

則該曲線在點(diǎn)x處的方向?qū)?shù)為：
$( \frac{\partial x_1}{\partial t }枷莉， \frac{\partial x_2}{\partial t }... \frac{\partial x_n}{\partial t } )| _{x}$

又點(diǎn)x在曲面g(x)=0上，所以有：
$g(x_1(t),x_2(t),...x_n(t))=0$

兩邊關(guān)于t求導(dǎo)得到：
$\frac{\partial g}{\partial x_1 } \frac{\partial x_1}{\partial t }+ \frac{\partial g}{\partial x_2 } \frac{\partial x_2}{\partial t }+...+ \frac{\partial g}{\partial x_n } \frac{\partial x_n}{\partial t }=0$

所以有：
$( \frac{\partial g}{\partial x_1 } , \frac{\partial g}{\partial x_2 } ,... \frac{\partial g}{\partial x_n })\left( \begin{array} {cccc} \frac{\partial x_1}{\partial t }\\ \frac{\partial x_2}{\partial t }\\ .\\ .\\ .\\ \frac{\partial x_n}{\partial t }\\ \end{array} \right)=0$

所以兩個(gè)向量是正交的尺迂，而向量 $( \frac{\partial g}{\partial x_1 } , \frac{\partial g}{\partial x_2 } ,... \frac{\partial g}{\partial x_n })$ 是函數(shù) $g(x_1,x_2,...x_3)$ 的梯度方向笤妙。但是很明顯這里g(x_1,x_2,...x_3)=0是一個(gè)超曲面，并不是一個(gè)函數(shù)噪裕。所以這里要區(qū)分開來蹲盘。而從這個(gè)公式，可以看出膳音，這個(gè)方向正交與過這一點(diǎn)的任意曲線在這一點(diǎn)上的方向向量召衔，所以這個(gè)方向是曲面的法向量方向。

所以我們?cè)诖说玫搅艘粋€(gè)結(jié)論：
結(jié)論一祭陷、超曲面g(x)=0的法向量是函數(shù)y=g(x)的梯度方向苍凛。

超曲面g(x)=0的性質(zhì)討論完了，我們?cè)賮砜茨繕?biāo)函數(shù)f(x)在最優(yōu)點(diǎn) $x^*$ 處的性質(zhì)兵志。

開始我們就假設(shè)了 $x^*$ 的存在醇蝴，不存在的情況不做討論,因?yàn)槔窭嗜粘藬?shù)法解決不了這一類問題。

結(jié)論二想罕、對(duì)于最優(yōu)點(diǎn) $x^*$ ,一定有f(x)在該點(diǎn)的梯度 $( \frac{\partial f}{\partial x^*_1 } , \frac{\partial f}{\partial x^*_2 } ,... \frac{\partial f}{\partial x^*_n })$ 垂直于約束曲面哑蔫。

對(duì)于上面的結(jié)論，使用反證法證明弧呐，

證明：假設(shè) $\nabla f(x_1^*,x_2^*,...x_n^*)=( \frac{\partial f}{\partial x^*_1 } , \frac{\partial f}{\partial x^*_2 } ,... \frac{\partial f}{\partial x^*_n })$ 不垂直于約束曲面闸迷，則根據(jù)垂直的定義，必然可以在曲面g（x）=0上俘枫，找到過最優(yōu)點(diǎn) $x^*$ 的一條曲線腥沽，使得 $( \frac{\partial f}{\partial x^*_1 } , \frac{\partial f}{\partial x^*_2 } ,... \frac{\partial f}{\partial x^*_n })$ 不垂直于這條曲線在 $x^*$ 點(diǎn)的方向向量，則 $( \frac{\partial f}{\partial x^*_1 } , \frac{\partial f}{\partial x^*_2 } ,... \frac{\partial f}{\partial x^*_n })$ 必在這條曲線的方向向量上有投影鸠蚪，

所以今阳，對(duì)于點(diǎn) $x^*$ ,因?yàn)樯厦娴那€是連續(xù)可導(dǎo)师溅，所以可以在曲線上可以找到點(diǎn) $(x_1^*,x_2^*,...x_n^*)-\varepsilon$ ，其中 $\varepsilon$ 為無窮小的方向向量盾舌。

觀察點(diǎn) $(x_1^*,x_2^*,...x_n^*)-\varepsilon$ 的f值墓臭，有：
$f((x_1^*,x_2^*,...x_n^*)-\varepsilon)=f(x_1^*,x_2^*,...x_n^*)-\nabla f(x_1^*,x_2^*,...x_n^*)\varepsilon+\varepsilon^TQ\varepsilon$

上面 $\nabla f(x_1^*,x_2^*,...x_n^*)\varepsilon$ 為兩個(gè)向量的內(nèi)積，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cnabla%20f(x_1%5E*%2Cx_2%5E*%2C...x_n%5E*)" alt="\nabla f(x_1^*,x_2^*,...x_n^*)" mathimg="1">與向量 $\varepsilon$ 不垂直妖谴，所以 $\nabla f(x_1^*,x_2^*,...x_n^*)\varepsilon$ 不為零窿锉，而Q是半正定矩陣，所以有：
$\varepsilon^TQ\varepsilon \ge 0$

取 $\varepsilon$ 時(shí)膝舅，如果取 $\nabla f(x_1^*,x_2^*,...x_n^*)$ 與向量 $\varepsilon$ 內(nèi)積為正的方向嗡载，對(duì)于固定的 $x^*$ ,在零附近，有以下公式：
$\nabla f(x_1^*,x_2^*,...x_n^*)\varepsilon \ge \varepsilon^TQ\varepsilon$

因?yàn)樯鲜胶竺媸?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cvarepsilon" alt="\varepsilon" mathimg="1">的二階仍稀，前面是一階洼滚，后面收斂比前面快。

由上面的不等式得到：
$0\ge-\nabla f(x_1^*,x_2^*,...x_n^*)\varepsilon + \varepsilon^TQ\varepsilon$

所以有：
$f((x_1^*,x_2^*,...x_n^*)-\varepsilon)\le f(x_1^*,x_2^*,...x_n^*)$

所以這與 $x^*$ 是f(x)的極小值點(diǎn)相矛盾技潘。所以假設(shè)不成立遥巴。

至此，我們得到了一下兩個(gè)結(jié)論：
1享幽、超曲面g(x)=0的法向量是函數(shù)y=g(x)的梯度方向挪哄。
2、對(duì)于最優(yōu)點(diǎn) $x^*$ ,一定有f(x)在該點(diǎn)的梯度 $( \frac{\partial f}{\partial x^*_1 } , \frac{\partial f}{\partial x^*_2 } ,... \frac{\partial f}{\partial x^*_n })$ 垂直于約束曲面琉闪。

由上面的兩個(gè)結(jié)論可以得到迹炼，在最優(yōu)點(diǎn) $x^*$ 處，曲面g(x)=0的法向 $\nabla g(x_1^*,x_2^*,...x_n^*)$ 與目標(biāo)函數(shù)f(x)在這一點(diǎn)的梯度 $\nabla f(x_1^*,x_2^*,...x_n^*)$ 是共線的颠毙。

所以斯入，對(duì)于目標(biāo)函數(shù)的極值點(diǎn)，一定滿足下面方程：
$\nabla g(x_1^*,x_2^*,...x_n^*)=\lambda \nabla f(x_1^*,x_2^*,...x_n^*)$

其中 $\lambda$ 為非零常數(shù)蛀蜜。

此時(shí)我們構(gòu)造一個(gè)函數(shù)：
$L(x,\lambda)=f(x)+\lambda g(x)$

這個(gè)函數(shù)就是拉格朗日函數(shù)刻两。

因?yàn)?br> $\frac{\partial L(x,\lambda) }{\partial x }=\nabla g(x_1^*,x_2^*,...x_n^*)+\lambda \nabla f(x_1^*,x_2^*,...x_n^*)$

$\frac{\partial L(x,\lambda) }{\partial \lambda }=g(x)$
所以,原帶約束的優(yōu)化問題的極值點(diǎn)，必然滿足

$\begin{cases} \frac{\partial L(x,\lambda) }{\partial x }=0 \\ \frac{\partial L(x,\lambda) }{\partial \lambda }=0 \end{cases}$

其中x是向量滴某， $\lambda$ 是標(biāo)量磅摹。

解上面的方程組，即可求得原問題的極值點(diǎn)霎奢。

至此户誓，我們就推出了約束條件為等式的情況。下面考慮約束條件為 $g(x)\le 0$ 的情況幕侠。

考慮不等式約束的優(yōu)化問題

$\min_{x} f(x)$
$s.t. g(x)\le 0$

其中x是一個(gè)n維向量帝美， $x=(x_1,x_2,...x_n)$ ,這里f(x)需滿足一個(gè)條件，即f(x)對(duì)向量x各個(gè)分量的偏導(dǎo)數(shù)連續(xù)晤硕。很明顯凸二次規(guī)劃的目標(biāo)函數(shù)滿足之一條件悼潭。

設(shè) $x^*$ 是f(x)的最優(yōu)點(diǎn)庇忌，此時(shí)分兩種情況進(jìn)行討論， $x^*$ 在g（x）=0上和 $x^*$ 在g(x)<0內(nèi)舰褪。

其一

當(dāng) $x^*$ 在g(x)=0上時(shí)皆疹，因?yàn)閒(x)在 $g(x) \le 0$ 上連續(xù)且可導(dǎo)，且由f(x)導(dǎo)函數(shù)也連續(xù)占拍，所以略就，當(dāng)極小值點(diǎn) $x^*$ 在g(x)=0上時(shí)，f(x)在 $g(x)<0$ 沒有極小值點(diǎn)刷喜，且f(x)在 $g(x)<0$ 上的值全部大于 $f(x^*)$ 残制。

有因?yàn)樘荻纫欢ㄊ呛瘮?shù)上升的方向立砸，所以 $\nabla f$ 的方向一定是指向 $g(x)\le0$ 的區(qū)域內(nèi)部掖疮。

而在g(x)=0上， $\nabla g$ 的方向也是函數(shù)g(x)增大的方向颗祝，所以 $\nabla g$ 的方向一定是指向 $g(x)\le0$ 的區(qū)域外部浊闪。

所以當(dāng) $x^*$ 在g(x)=0上時(shí)， $\nabla f= \lambda \nabla g$ ,其中 $\lambda >0$

所以只要求解 $L(x,\lambda)$ 關(guān)于自變量 $(x,\lambda)$ 的極值點(diǎn)螺戳，就可以求得原始問題的極值點(diǎn)搁宾。即解一下方程組：
$\begin{cases} \frac{\partial L(x,\lambda) }{\partial x }=0 \\ \frac{\partial L(x,\lambda) }{\partial \lambda }=0 \end{cases}$

其中 $\lambda >0$

其二

當(dāng) $x^*$ 在g(x)<0內(nèi)部時(shí)，其約束對(duì)目標(biāo)函數(shù)f(x)的極小值點(diǎn)不起作用倔幼，可直接 $\nabla f(x) =0$ ,求出的向量x盖腿，就是目標(biāo)函數(shù)的極小值點(diǎn)。

為和上面表達(dá)式統(tǒng)一损同，這種情況相當(dāng)于翩腐， $\lambda =0$

所以只要求解 $L(x,\lambda)$ 關(guān)于自變量 $(x,\lambda)$ 的極值點(diǎn)，就可以求得原始問題的極值點(diǎn)膏燃。即解一下方程組：
$\begin{cases} \frac{\partial L(x,\lambda) }{\partial x }=0 \\ \lambda=0 \end{cases}$

KKT 條件

通過以上其一茂卦，其二情況的分析，我們得到组哩，當(dāng) $\lambda=0$ 時(shí)等龙，必有 $g(x)\le 0$ ,當(dāng) $\lambda \ge 0$ 時(shí)，必有 $g(x)= 0$

所以伶贰， $\lambda$ 與g(x)必然有一個(gè)為零蛛砰，即， $\lambda g(x)=0$

所以此時(shí)有：
$\begin{cases} \lambda \ge 0\\ g(x) \le 0\\ \lambda g(x)=0 \end{cases}$

這個(gè)就是與原始問題中不等式約束對(duì)應(yīng)的拉格朗日的KKT條件黍衙。也就是說當(dāng)約束條件中有不等式約束時(shí)暴备，拉格朗日乘數(shù)法解出的解，必須滿足KKT條件们豌。

到此涯捻，我們得到了拉格朗日乘數(shù)法浅妆，詳細(xì)敘述如下：

拉格朗日乘數(shù)法詳細(xì)描述

對(duì)于如下帶約束的優(yōu)化問題
$\min_{x} f(x)$
$s.t. g(x)\le 0$
其中x是一個(gè)n維向量， $x=(x_1,x_2,...x_n)$ ,這里f(x)需滿足一個(gè)條件障癌，即f(x)對(duì)向量x各個(gè)分量的偏導(dǎo)數(shù)連續(xù)凌外。（很明顯凸二次規(guī)劃的目標(biāo)函數(shù)滿足之一條件。）

可以轉(zhuǎn)化成以下問題涛浙。
引入拉格朗日函數(shù)：
$L(x,\lambda)=f(x)+\lambda g(x)$
其中x為一個(gè)n維向量康辑。

求解以下方程組
$\begin{cases} \frac{\partial L(x,\lambda) }{\partial x }=0 \\ \frac{\partial L(x,\lambda) }{\partial \lambda }=0\\ \lambda \ge 0\\ g(x) \le 0\\ \lambda g(x)=0 \end{cases}$

以上方程組的解的x的部分，就是原問題的最優(yōu)解轿亮。其中以下條件稱為KKT條件疮薇。
$\begin{cases} \lambda \ge 0\\ g(x) \le 0\\ \lambda g(x)=0 \end{cases}$

多個(gè)約束的拉格朗日乘數(shù)法

對(duì)于多約束優(yōu)化問題如下：
$\min_{x} f(x)$
$s.t. h_i(x)= 0 　 (i=1,2....m)$
$s.t. g_j(x)\le 0　 (j=1,2....k)$

其中x為n維向量，f(x)有關(guān)于x各個(gè)分量的連續(xù)一階偏導(dǎo)函數(shù)我注。

以上優(yōu)化問題按咒，可以轉(zhuǎn)化為以下問題。

定義廣義拉格朗日函數(shù)：
$L(x,\lambda,\mu)=f(x)+\sum_i^m \lambda_i h_i(x) +\sum_j^k \mu_jg_j(x)$

其中但骨， $\lambda=(\lambda_1,\lambda_2,...\lambda_m)$ , $\mu=(\mu_1,\mu_2,...\mu_k)$ 為引入的拉格朗日乘數(shù)励七。

求解以下方程組，得到的解的x部分奔缠，就是原問題的最優(yōu)解。
$\begin{cases} \frac{\partial L(x,\lambda,\mu) }{\partial x }=0 \\ \frac{\partial L(x,\lambda,\mu) }{\partial \lambda_i }=0\\ \frac{\partial L(x,\lambda,\mu) }{\partial \mu_j }=0\\ \mu_j \ge 0\\ g_j(x) \le 0\\ \mu_j g_j(x)=0 \end{cases}$

與原始問題中不等式約束對(duì)應(yīng)的KKT條件為：
$\begin{cases} \mu_j \ge 0\\ g_j(x) \le 0\\ \mu_j g_j(x)=0 \end{cases}$

其中j=1,2,3...,k

自此拉格朗日乘數(shù)法推導(dǎo)完成。

拉格朗日對(duì)偶問題

首先要聲明的是，求解帶約束的規(guī)劃問題，上面給出可以轉(zhuǎn)換成拉格朗日函數(shù)贝攒，對(duì)未知數(shù)求導(dǎo)，令導(dǎo)數(shù)等于零弥奸，直接可以解出最優(yōu)解。也就是說，原始問題已經(jīng)得到解決招拙。那為什么還要在引入拉格朗日對(duì)偶問題呢诉稍？

其實(shí)在很多時(shí)候是用不到轉(zhuǎn)換成拉格朗日對(duì)偶問題的服爷，本文的SVM推導(dǎo)匾旭，其實(shí)不用引入拉格朗日對(duì)偶問題也可以解決女蜈，在周志華的書和很多教程中并未對(duì)此進(jìn)行說明，直接引入拉格朗日對(duì)偶問題，我認(rèn)為這種推導(dǎo)是本末倒置的伪窖，必須先論證出引入拉個(gè)朗日對(duì)偶問題的必要性逸寓。

下面先給出什么是拉格朗日對(duì)偶，然后再給出為什么使用拉格朗日對(duì)偶覆山。

什么是拉格朗日對(duì)偶

對(duì)于多約束優(yōu)化問題如下：
$\min_{x} f(x)$
$s.t. h_i(x)= 0 　 (i=1,2....m)$
$s.t. g_j(x)\le 0　 (j=1,2....k)$

其中x為n維向量竹伸，f(x)有關(guān)于x各個(gè)分量的連續(xù)一階偏導(dǎo)函數(shù)。

由上面的推導(dǎo)簇宽，可以得到拉格朗日函數(shù)：
$L(x,\lambda,\mu)=f(x)+\sum_i^m \lambda_i h_i(x) +\sum_j^k \mu_jg_j(x)$
其中勋篓， $\lambda=(\lambda_1,\lambda_2,...\lambda_m)$ , $\mu=(\mu_1,\mu_2,...\mu_k)$ 為引入的拉格朗日乘數(shù)。且向量 $\mu$ 的每個(gè)分量大于等于零

其拉格朗日對(duì)偶函數(shù)定義為：
$\Gamma( \lambda,\mu)=\inf_x L(x,\lambda,\mu)=\inf_x (f(x)+\sum_i^m \lambda_i h_i(x) +\sum_j^k \mu_jg_j(x))$
其中魏割， $\lambda=(\lambda_1,\lambda_2,...\lambda_m)$ , $\mu=(\mu_1,\mu_2,...\mu_k)$ 為引入的拉格朗日乘數(shù)譬嚣。且向量 $\mu$ 的每個(gè)分量大于等于零

上面定義了拉格朗日對(duì)偶函數(shù)，下面推出拉格朗日對(duì)偶問題钞它。

對(duì)拉格朗日對(duì)偶函數(shù) $\Gamma( \lambda,\mu)$ 進(jìn)行分析拜银。設(shè) $\widetilde{x}$ 是原始優(yōu)化問題可行域內(nèi)的一個(gè)點(diǎn)， $x^*$ 是原始問題的最優(yōu)解遭垛。

因?yàn)橄麓_界的定義有：
$\inf_x L(x,\lambda,\mu)\le L(\widetilde{x},\lambda,\mu)$

因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cwidetilde%7Bx%7D" alt="\widetilde{x}" mathimg="1">是原始優(yōu)化問題可行域內(nèi)的一個(gè)點(diǎn)尼桶，所以有：

$h_i(\widetilde{x}) =0$
$g_j(\widetilde{x})\le 0$
$\mu_j\ge 0$
所以有
$\sum_i^m \lambda_i h_i(\widetilde{x}) +\sum_j^k \mu_jg_j(\widetilde{x})\le 0$

所以有：
$L(\widetilde{x},\lambda,\mu) \le f(\widetilde{x})$

所以：
$\Gamma( \lambda,\mu)=\inf_x L(x,\lambda,\mu)\le L(\widetilde{x},\lambda,\mu) \le f(\widetilde{x})$

因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cwidetilde%7Bx%7D" alt="\widetilde{x}" mathimg="1"> 是可行域中任意一點(diǎn)，所以對(duì)于最優(yōu)解 $x^*$ 也必須滿足上面不等式锯仪，即：
$\Gamma( \lambda,\mu)\le f(x^*)$

所以泵督，拉格朗日對(duì)偶函數(shù)確定了原始問題最優(yōu)解的下界。

由于對(duì)于任意滿足條件( $\mu$ 的每個(gè)分量大于等于零)的 $\lambda,\mu$ ,上面不等式都成立卵酪，所以有：
$\sup_{\lambda,\mu}\Gamma( \lambda,\mu)\le f(x^*)$

試想如果上面的等號(hào)成立幌蚊，那么我們就可以把原始問題求f(x)的最小值谤碳，轉(zhuǎn)換成一下問題：
$\max_{\lambda,\mu}\Gamma( \lambda,\mu)$
$s.t. 向量\mu的每個(gè)分量大于等于零溃卡。$

如果能轉(zhuǎn)化成上面問題，可以看出原問題的下確界等于上面問題的上確界蜒简，所以上面這個(gè)問題稱作原問題的拉格朗日對(duì)偶問題瘸羡。

這樣我們就定義了什么是拉格朗日對(duì)偶問題。但是上面我們假設(shè)不等式中等式成立搓茬，也就是說在有些時(shí)候不等式中等式是不成立的犹赖，此時(shí)，什么時(shí)候等式成立成了關(guān)鍵問題卷仑，所以我們引入以下兩個(gè)概念峻村，強(qiáng)對(duì)偶和弱對(duì)偶。

強(qiáng)對(duì)偶和弱對(duì)偶

對(duì)于以下不等式
$\sup_{\lambda,\mu}\Gamma( \lambda,\mu)\le f(x^*)$
其中向量 $x^*$ 為原始約束優(yōu)化問題的最優(yōu)解锡凝。

我們定義如果 $\sup_{\lambda,\mu}\Gamma( \lambda,\mu)= f(x^*)$
那么原始約束的優(yōu)化問題和以下問題成強(qiáng)對(duì)偶關(guān)系粘昨。
$\max_{\lambda,\mu}\Gamma( \lambda,\mu)$
$s.t. 向量\mu的每個(gè)分量大于等于零。$

我們定義如果 $\sup_{\lambda,\mu}\Gamma( \lambda,\mu)< f(x^*)$
那么原始約束的優(yōu)化問題和以下問題成弱對(duì)偶關(guān)系。
$\max_{\lambda,\mu}\Gamma( \lambda,\mu)$
$s.t. 向量\mu的每個(gè)分量大于等于零张肾。$

所以如果兩者成強(qiáng)對(duì)偶關(guān)系芭析，那么我們可以將原問題轉(zhuǎn)化成對(duì)偶問題來求，至于為什么大費(fèi)周章的把原問題轉(zhuǎn)化成對(duì)偶問題來解吞瞪，在后面的文章詳細(xì)分析馁启。

現(xiàn)在又有一個(gè)新問題擺在我們的面前，就是什么時(shí)候是強(qiáng)對(duì)偶問題芍秆，什么時(shí)候是弱對(duì)偶問題惯疙。對(duì)于這個(gè)問題我們給出以下定理判斷。

在證明強(qiáng)弱對(duì)偶問題的定理時(shí)妖啥，需要用到一下引理螟碎，所以先給出以下引理，再給出判斷強(qiáng)弱對(duì)偶問題的定理迹栓。

引理（凸集分離定理）

設(shè)集合S1掉分，S2是 $R^n$ (n≥1)中的兩個(gè)不相交的非空凸集，則存在一個(gè)超平面分離S1,S2,既存在 $v∈R^n$ , $v≠0$ 以及b∈R 使得：
$v?x+b \ge 0, \forall x∈S1,(1)$ 且：
$v?x+b \le 0, \forall x∈S2.(2)$

證明：
定義集合 $S=S_1-S_2=\{x-y | x\in S_1 ,y\in S_2 \}$ 克伊。則對(duì)任意的 $z_1\in S ,z_2\in S$
必存在 $x_1,x_2\in S_1$ 酥郭， $y_1,y_2\in S_2$ 有下式成立。
$z_1=x_1-y_1\\ z_2=x_2-y_2\\$
所以對(duì)任意的 $t\in [0,1]$ 有
$(t)z_1+(1-t)z_2=(t)x_1-(t)y_1 +(1-t)x_2-(1-t)y_2=(t)x_1+(1-t)x_2-((t)y_1 +(1-t)y_2)\\$
因?yàn)榧蟂1愿吹，S2是 $R^n$ (n≥1)中的兩個(gè)不相交的非空凸集不从，

所以對(duì)任意的 $t\in [0,1]$ 有 $(t)z_1+(1-t)z_2\in S$
所以集合S也是非空凸集合。且向量0不屬于集合S犁跪。

對(duì)于以上不包含零向量的凸集合S椿息，構(gòu)造集合 $A=S\bigcup \partial S$
其中 $\partial S$ 表示S的邊界。所以對(duì)于集合A是 $R^n$ 的一個(gè)閉凸子集坷衍。
因?yàn)锳是閉凸集寝优，所以必然存在 $x^*\in A$ 使得：
$x^*=\inf_{y\in A}{||y||^2}$

可以證明對(duì) $\forall z∈A$ ,都有內(nèi)積 $(z,x^*)\ge0$

若 $x^*$ 為零向量，則結(jié)論顯然成立枫耳，以下在 $x^*\neq 0$ 的情況下討論乏矾。

用反證法證明以上結(jié)論，假設(shè)存在向量 $\beta\in A$ .有
$(\beta,x^*)<0$

所以由向量 $\beta,x^*$ 可以構(gòu)造構(gòu)造一個(gè)垂直于向量 $\beta-x^*$ 的向量 $\mu$ ,構(gòu)造方式如下：
$\mu=\beta-\frac{\beta-x^*}{||\beta-x^*||}\frac{(\beta,\beta-x^*)}{||\beta-x^*||} = \frac{(x^*,x^*)-(x^*,\beta)}{||\beta-x^*||^2}\beta-\frac{(\beta,\beta)-(\beta,x^*)}{||\beta-x^*||^2} x^*$

設(shè) $\lambda=\frac{(x^*,x^*)-(x^*,\beta)}{||\beta-x^*||^2}$ ,則 $1-\lambda=\frac{(\beta,\beta)-(\beta,x^*)}{||\beta-x^*||^2}$ ,

所以 $\mu=\lambda \beta+(1-\lambda )x^*$

由 $\lambda$ 的表達(dá)式得到迁杨， $\lambda \in (0,1)$

所以钻心，推導(dǎo)出向量 $\mu \in A$

又因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cmu-x%5E*%3D%5Clambda%20%5Cbeta-%5Clambda%20x%5E*%3D%5Clambda%20(%5Cbeta-%20x%5E*)" alt="\mu-x^*=\lambda \beta-\lambda x^*=\lambda (\beta- x^*)" mathimg="1">,所以 $\mu-x^*$ 與 $\beta- x^*$ 共線，所以 $\mu$ 也垂直于 $\mu-x^*$

所以：
$||\mu||^2=||\mu-x^*+x^*||^2=||\mu-x^*||^2+||x^*||^2 \le ||x^*||^2$

所以铅协，與 $x^*=\inf_{y\in A}{||y||^2}$ 相矛盾捷沸。所以假設(shè)不成立。

所以對(duì)于構(gòu)造的凸集合S,可以找到一個(gè)向量 $\nu$ ,對(duì) $\forall z \in S$ ,有
$(\nu, z)\ge 0$

而集合S中的元素可寫為z=x-y, $x\in S_1,y \in S_2$ .

所以有：
$(\nu,(x-y))\ge 0$

設(shè) $b=-\sup_{y\in S_2}\{(\nu, y)\}$

所以有：
$(v,x)+b \ge 0, \forall x∈S1,(1)$

而此時(shí)剛好：
$(\nu ,y)+b \le 0, \forall y∈S2.(2)$

所以引理得到證明狐史。

定理(強(qiáng)對(duì)偶充分條件定理)：

對(duì)于多約束優(yōu)化問題如下：
$\min_{x} f(x)$
$s.t. h_i(x)= 0 　 (i=1,2....m)$
$s.t. g_j(x)\le 0　 (j=1,2....k)$
其中x為n維向量痒给，f(x)有關(guān)于x各個(gè)分量的連續(xù)一階偏導(dǎo)函數(shù)坯钦。這里 $h_i(x)$ 已經(jīng)化簡(jiǎn)為行滿秩。

如果以上問題是一個(gè)凸優(yōu)化問題侈玄，函數(shù) $g_j(x)$ 是凸函數(shù)婉刀，函數(shù) $h_i(x)$ 是放射函數(shù)，且存在 $\widetilde{x}∈relintD(定義域的相對(duì)內(nèi)部)$ 使得： $g_j(\widetilde{x})<0$ , 對(duì)任意的j=1,2,...k, $h_i(\widetilde{x})= 0 　對(duì)任意的 (i=1,2....m)$ ,則原問題和對(duì)偶問題是強(qiáng)對(duì)偶的序仙。

證明：
首先我們定義集合：
$\cal{G}=\{(g_1(x),g_2(x)...g_k(x),h_1(x),h_2(x)...h_m(x),f(x)) \in R^k\times R^m\times R|x \in D \}$
其中集合D為拉格朗日函數(shù)的定義域突颊，注意這個(gè)地方不是原問題的可行域，因?yàn)檗D(zhuǎn)化成拉格朗日函數(shù)時(shí)潘悼，不存在可行域律秃。

接著我們引入上鏡圖的概念，定義集合
$\cal{A}=\{p+(u,0,t) \in R^k\times R^m\times R| p \in \cal{G},u\in R^k ,0\in R^m.t \in R ,u \succeq 0治唤，t \ge 0 \}$

由上鏡集的定義棒动，可以看出，上鏡集是集合 $\cal{G}$ 沿著前k個(gè)坐標(biāo)軸和最后一個(gè)坐標(biāo)軸的正向運(yùn)動(dòng)覆蓋的區(qū)域宾添。

因?yàn)楹瘮?shù)f(x)是凸函數(shù)船惨，函數(shù) $g_j(x)$ 是凸函數(shù)，函數(shù) $h_i(x)$ 是放射函數(shù)缕陕，所以集合 $\cal{G}$ 也是凸函數(shù)粱锐，所以其上鏡圖 $\cal{A}$ 也是個(gè)凸集。

我們令：
$\cal{B}=\{(u,0,t) \in R^k\times R^m\times R| p \in \cal{G},u\in R^k ,0\in R^m.t \in R ,u \preceq 0扛邑，t \le p^* \}$

其中 $p^*=inf\{ t|(\mu,\lambda,t )\in \cal{G}, \mu \preceq 0 ,\lambda=0 \}$

由 $p^*$ 的定義可以看出怜浅， $p^*$ 就是原問題的最小值 $f(x^*)$ .

可以根據(jù)凸集的定義，可以驗(yàn)證集合 $\cal{B}$ 也是凸集蔬崩。

由 $\cal{A}$ 恶座， $\cal{B}$ 定義，可以得到 $\cal{A}$ 沥阳， $\cal{B}$ 的交集為空跨琳。此時(shí)由凸集分離定理，可得到沪袭，存在一個(gè)非零向量 $( \mu_0,\lambda_0,t_0 ) \in R^k\times R^m\times R$ ,以及 $b \in R$ 使得：
$( \mu_0,\lambda_0,t_0)(g_1(x)+u_1,..g_k(x)+u_k,h_1(x),h_2(x)..h_m(x),f(x)+t)+b\ge 0 ,\forall (g_1(x)+u_1,..g_k(x)+u_k,h_1(x),h_2(x)..h_m(x),f(x)+t)∈ \cal{A}$
$( \mu_0,\lambda_0,t_0)(u,0,t)+b\le 0 ,\forall (u,0 , t)∈ \cal{B}$

其中 $\mu_0=(\mu_1,...\mu_k)$ , $\lambda_0=(\lambda_1,...\lambda_m)$

可化簡(jiǎn)為：
$\sum_j^k{\mu_j(g_j(x)+u_j)}+\sum_i^m\lambda_ih_i(x)+t_0(f(x)+t)+b\ge 0 ,\forall (g_1(x)+u_1,..g_k(x)+u_k,h_1(x),h_2(x)..h_m(x),f(x)+t)∈ \cal{A}$
再化簡(jiǎn)為
$\sum_j^k{\mu_jg_j(x) }+\sum_i^m\lambda_ih_i(x)+t_0 f(x) +b + \mu_0 u + t_0t \ge 0 ,\forall (g_1(x)+u_1,..g_k(x)+u_k,h_1(x),h_2(x)..h_m(x),f(x)+t)∈ \cal{A} 湾宙， (1)$
上式對(duì)所有的 $x \in D,u \succeq 0，t \ge 0$ 成立冈绊。

$\mu_0 u + t_0t +b\le 0 ,\forall (u,0 , t)∈ \cal{B} ,(2)$
上式對(duì)所有的 $x \in D,u \preceq 0，t \le p^*$ 成立埠啃。

由(1)式的任意性死宣，可得 $\mu_0\succeq0 ,t_0>0$ ，令u從右側(cè)趨近于0碴开，t從右側(cè)趨近于0毅该，可得到：
$\sum_j^k{\mu_jg_j(x) }+\sum_i^m\lambda_ih_i(x)+t_0 f(x) +b \ge 0$

由(2)式得博秫，u從左側(cè)趨近于0，t從左側(cè)趨近于 $p^*$ 眶掌，可得到:
$t_0p^*\le -b$

所以：
$\sum_j^k{\mu_jg_j(x) }+\sum_i^m\lambda_ih_i(x)+t_0 f(x) \ge t_0p^*$

因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=t_0%5Cge0" alt="t_0\ge0" mathimg="1"> 有兩種情形挡育，
第一種情況若 $t_0>0$ ，兩邊同時(shí)除以 $t_0$ ,得到 $L(x,\mu/t_0,\lambda_0/t_0) \ge p^*$ 朴爬，

所以
$\sup_{\lambda,\mu}\Gamma( \lambda,\mu)\ge p^*= f(x^*)$

又由于拉格朗日對(duì)偶本來
$\sup_{\lambda,\mu}\Gamma( \lambda,\mu)\le f(x^*)$

所以
$\sup_{\lambda,\mu}\Gamma( \lambda,\mu)= p^*= f(x^*)$

所以此時(shí)原問題和拉格朗日對(duì)偶問題是強(qiáng)對(duì)偶關(guān)系即寒。

第二種情況若 $t_0=0$ ，有

$\sum_j^k{\mu_jg_j(x) }+\sum_i^m\lambda_ih_i(x) \ge0$

此時(shí)因?yàn)槎ɡ淼臈l件中有召噩，存在 $\widetilde{x}∈relintD$ ,有 $g_j(\widetilde{x})<0,j=(1,2,...k)$

因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=g_i(x)" alt="g_i(x)" mathimg="1">是凸函數(shù)母赵，必有連續(xù)性，必然存在 $g_i(x)\le 0,i=(1,2,...k)$ 的解集的一個(gè)真閉子集U,使得 $\forall x \in U$ 有 $g_j(x)<0,j=(1,2,...k)$

而 $\mu_0\succeq0$ ,所以在U上
$\sum_j^k{\mu_jg_j(x) }\le0$

所以
$\sum_i^m\lambda_ih_i(x) \ge- \sum_j^k{\mu_jg_j(x) } \ge0$

在集合U上具滴，因?yàn)榉律浜瘮?shù) $\sum_i^m\lambda_ih_i(x) 必須恒等于零凹嘲，因?yàn)槿舨缓艿扔诹悖赨上必然不能有零點(diǎn)构韵，這與$ h_i(\widetilde{x})=0$矛盾周蹭。

所以， $\sum_i^m\lambda_ih_i(x)=0$

所以 $\lambda_0=0$ . $\mu_0=0$ ,所以向量 $(\mu_0,\lambda_0,t_0)=0$ ,這與凸集分離定理中(\mu_0,\lambda_0,t_0)非零矛盾疲恢，所以 $t_0$ 不能等于0.所以定理得到證明谷醉。

Slater條件

所以由這個(gè)定理可以輕松簡(jiǎn)單的判斷一個(gè)原問題和拉格朗日對(duì)偶問題是強(qiáng)對(duì)偶關(guān)系還是弱對(duì)偶關(guān)系。

只需要看是否滿足定理中的條件：
對(duì)于一個(gè)凸優(yōu)化問題冈闭，存在 $\widetilde{x}∈relintD(定義域的相對(duì)內(nèi)部)$ 使得： $g_j(\widetilde{x})<0$ , 對(duì)任意的j=1,2,...k成立, $h_i(\widetilde{x})= 0 　對(duì)任意的 (i=1,2....m)$ 成立俱尼。

這個(gè)條件也被稱為Slater條件。

自此萎攒，我們就引入了判斷朗格朗日對(duì)偶為強(qiáng)對(duì)偶的條件遇八。下面我們給出為什么使用拉格朗日對(duì)偶問題。

為什么使用拉格朗日對(duì)偶問題

如上面的分析耍休，我們對(duì)拉格朗日函數(shù)中的未知數(shù)進(jìn)行求導(dǎo)刃永，既可以得到原問題的最優(yōu)解，為何還有再引入拉格朗日對(duì)偶問題羊精，之所以多此一舉的使用拉格朗日對(duì)偶問題斯够，主要有以下兩點(diǎn)原因。

原因1

大大縮減了計(jì)算量喧锦，不論是直接解原問題读规，還是對(duì)拉格朗日函數(shù)求導(dǎo)，令導(dǎo)數(shù)等于零燃少，其計(jì)算量都和自變量x的維度有關(guān)束亏，如果x的維度很高時(shí)，這兩種方法求解時(shí)的計(jì)算量就會(huì)變大阵具，而不論x的維度多高碍遍，轉(zhuǎn)化成拉格朗日對(duì)偶問題，其未知數(shù) $\mu.\lambda$ 的數(shù)量和約束條件的多少有關(guān)怕敬。從而大大減少了計(jì)算量。

原因2

$\Gamma( \lambda,\mu)=\inf_x L(x,\lambda,\mu)=\inf_x (f(x)+\sum_i^m \lambda_i h_i(x) +\sum_j^k \mu_jg_j(x))$

對(duì)任意的滿足 $L(x,\lambda,\mu)$ 定義域的 $\lambda_1,\lambda_2$ ,有：

$\begin{align} \Gamma(\frac{ \lambda_1+\lambda_2}{2},\mu)&=\inf_x L(x,\frac{ \lambda_1+\lambda_2}{2},\mu)\\ &=\inf_x (f(x)+\sum_i^m \frac{ \lambda_1+\lambda_2}{2} h_i(x) +\sum_j^k \mu_jg_j(x))\\ &=\inf_x (\frac{f(x)}{2}+\frac{f(x)}{2}+\sum_i^m \frac{ \lambda_1+\lambda_2}{2} h_i(x) +\frac{\sum_j^k \mu_jg_j(x)}{2}+\frac{\sum_j^k \mu_jg_j(x)}{2} )\\ &=\inf_x(\frac{ L( x , \lambda_1 , \mu )}{2}+\frac{L( x , \lambda_2 , \mu )}{2})\\ &\ge \inf_x(\frac{ L( x , \lambda_1 , \mu )}{2})+\inf_x( \frac{ L( x , \lambda_2 , \mu )}{2}))\\ &=\frac{ \Gamma( \lambda_1 ,\mu)}{2}+ \frac{\Gamma( \lambda_2 ,\mu)}{2}\\ \end{align}$

所以 $\Gamma( \lambda,\mu)$ 一定為一個(gè)凹函數(shù)熬的。 $-\Gamma( \lambda,\mu)$ 一定是一個(gè)凸函數(shù)。

也就是說不論原問題是不是凸優(yōu)化問題，拉格朗日對(duì)偶問題一定是可以轉(zhuǎn)化為凸優(yōu)化問題崭闲。所以這就是有時(shí)引入拉格朗日對(duì)偶問題的必要性沙兰。

原因3

特別的在SVM中但荤，引入拉格朗日對(duì)偶問題烧颖，有一個(gè)至關(guān)重要的原因，是可以方便的引入核函數(shù)胞皱。這點(diǎn)在下面SVM的推導(dǎo)中說明反砌。

支持向量機(jī)(SVM)

和其他模型推導(dǎo)不一樣，支持向量機(jī)模型的推導(dǎo)并不是從損失函數(shù)出發(fā)萌朱，其推導(dǎo)過程只是在中途化簡(jiǎn)時(shí)用到損失函數(shù)宴树。

支持向量機(jī)模型其實(shí)是一個(gè)凸二次規(guī)劃問題，所以其推導(dǎo)從凸二次規(guī)劃出發(fā)晶疼。下面我們就具體的介紹怎么把支持向量機(jī)轉(zhuǎn)化成凸二次規(guī)劃問題酒贬。

設(shè)訓(xùn)練樣本集 $D=\{(x_1,y_1),(x_2,y_2) ,(x_3,y_3)...(x_m,y_m)\},y_i \in \{-1,+1 \}$ ,
其中 $x_i=(x_{i1},x_{i2},x_{i3},...x_{in})$ 代表第i個(gè)樣本點(diǎn)的n個(gè)屬性值, $y_i$ 是第i個(gè)樣本點(diǎn)的label又憨。
現(xiàn)在需要找一個(gè)超平面將樣本集中的正負(fù)樣本分開。首先考慮簡(jiǎn)單的形式锭吨，如果可以找到兩個(gè)凸集 $S_1,S_2$ ,使得正樣本集在凸集 $S_1$ 內(nèi)蠢莺，負(fù)樣本集在凸集 $S_2$ 內(nèi),那么由上面介紹的凸集分離定理，存在一個(gè)超平面零如，可以將正負(fù)樣本完美的分離躏将。如下圖所示：

圖1.PNG

由上圖可以看出，可以將訓(xùn)練樣本集D完美分開的超平面有很多個(gè)考蕾，現(xiàn)在我們要找到泛化能力最強(qiáng)的一個(gè)祸憋，也就是說當(dāng)樣本增加時(shí)，這個(gè)超平面還可以盡可能的將樣本完美分離肖卧。我下面試著找到這個(gè)超平面蚯窥。

和所有監(jiān)督模型一樣，訓(xùn)練樣本集的最后一個(gè)維度y是樣本的label,由上圖可以看出超平面所在的空間對(duì)應(yīng)的是樣本點(diǎn)的屬性空間喜命，這個(gè)空間與label所在的維度空間沒有關(guān)系沟沙，先不考慮這個(gè)維度，所以下面說的樣本點(diǎn)特指的是剔除了label的樣本點(diǎn)壁榕。

設(shè)這個(gè)完美的超平面方程為：

$\vec{w}^T\vec{x}+b=0$

第一步：首先求出樣本空間任意點(diǎn) $\vec{x_i}=(x_{i1},x_{i2}...x_{in})$ (其中n為樣本點(diǎn)的n個(gè)屬性)到這個(gè)超平面的距離矛紫。

由超平面的方程可以得到，超平面的法向量為 $\vec{w}$ ,則單位法向量為 $\frac{\vec{w}}{||\vec{w}||}$ 牌里。

設(shè)這個(gè)距離為d, 則 $\vec{x_i}\pm d\frac{\vec{w}}{||\vec{w}||}$ 是點(diǎn)x在超平面上的投影點(diǎn)（法向量指向 $\vec{x_i}$ 一側(cè)時(shí)是減颊咬，法向量不指向 $\vec{x_i}$ 一側(cè)時(shí)是加）。則有下面方程成立：
$\vec{w}^T(\vec{x_i}\pm d\frac{\vec{w}}{||\vec{w}||})+b=0$

所以：
$d=\frac{|\vec{w}^T\vec{x_i}+b|}{||w||}$

以上求出了樣本點(diǎn)到超平面的距離牡辽。

第二步：求陰性樣本到陽(yáng)性樣本之間的最小距離喳篇。
對(duì)于每個(gè)label等于1的樣本點(diǎn) $\vec{x_i}$ 有下面公式成立：
$\vec{w}^T\vec{x_i}+b>0$
對(duì)于每個(gè)label等于-1的樣本點(diǎn) $\vec{x_i}$ 有下面公式成立：
$\vec{w}^T\vec{x_i}+b<0$

所以存在 $\varepsilon_1>0$ , $\varepsilon_2<0$ ,使下是成立：
$\begin{cases} \vec{w}^T\vec{x_i}+b\ge \varepsilon_1 ,y_i=1\\ \vec{w}^T\vec{x_i}+b \le \varepsilon_2,y_i=-1 \end{cases}$

而且使上述等式成立的陽(yáng)性樣本和陰性樣本可以找到。

此時(shí)态辛，令 $b=b_1+\frac{\varepsilon_1+\varepsilon_2}{2}$

則有
$\begin{cases} \vec{w}^T\vec{x_i}+b_1 \ge \frac{\varepsilon_1-\varepsilon_2}{2}>0 ,y_i=1\\ \vec{w}^T\vec{x_i}+b_1 \le \frac{\varepsilon_2-\varepsilon_1}{2}<0,y_i=-1 \end{cases}$

所以有：
$\begin{cases} \vec{w^*}^T\vec{x_i}+b^*\ge 1,y_i=1\\ \vec{w^*}^T\vec{x_i}+b^* \le -1,y_i=-1 \end{cases}$

這個(gè)公式可以看出麸澜，通過調(diào)整初始的w,b得到的 $w^*，b^*$ 只差統(tǒng)一的一個(gè)倍數(shù)或者統(tǒng)一的一個(gè)平移奏黑。

所以求出 $w^*炊邦，b^*$ 即是求出w，b熟史，所以這里為了后面表述方便馁害，令w，b代替以上公式中的 $w^*蹂匹，b^*$ .所以有：

$\begin{cases} \vec{w}^T\vec{x_i}+b\ge 1,y_i=1\\ \vec{w}^T\vec{x_i}+b \le -1,y_i=-1 \end{cases}$

所以此時(shí)陽(yáng)性樣本到陰性樣本之間的最小距離為：
$min_{x_i,x_j} r= min_{x_i,x_j}\{ \frac{|\vec{w}^T\vec{x_i}+b|}{||w||}+\frac{|\vec{w}^T\vec{x_j}+b|}{||w||}\}$

其中 $x_i為陽(yáng)性樣本點(diǎn)碘菜，x_j為陰性樣本點(diǎn)$

因?yàn)?br> $\begin{cases} \vec{w}^T\vec{x_i}+b\ge 1,y_i=1\\ \vec{w}^T\vec{x_j}+b \le -1,y_j=-1 \end{cases}$
所以：
$|\vec{w}^T\vec{x}+b|\ge 1 ,\forall x \in D$

取使得上述不等式中等號(hào)成立的陽(yáng)性樣本點(diǎn)和陰性樣本點(diǎn)，則這個(gè)最小距離可求出如下：

$min_{x_i,x_j} r= \frac{2}{||w||}$

所以對(duì)于訓(xùn)練樣本集D，陽(yáng)性樣本點(diǎn)和陰性樣本點(diǎn)的最小距離為：
$\frac{2}{||w||}$

要使得模型泛化性能好忍啸，支持向量機(jī)的做法是仰坦，最大化這個(gè)距離。這就是支持向量機(jī)的本質(zhì)吊骤。

在上述過程中缎岗，滿足不等式中等號(hào)的樣本點(diǎn)稱為支持向量静尼。因?yàn)樽詈笸茖?dǎo)的這個(gè)距離和其他的點(diǎn)（向量）沒有任何關(guān)系白粉，只與這些點(diǎn)有關(guān)，所以者些被稱為支持向量逼庞。

第三步：最大化上述距離趁窃。

我們得到了陰性樣本和陽(yáng)性樣本之間的最小距離：
$\frac{2}{||w||}$
現(xiàn)在要尋找w,b使得這個(gè)距離最大化馅巷。

既轉(zhuǎn)化為以下問題：
$\max_{w,b} \frac{2}{||w||}$
$s.t.y_i(\vec{w}^T\vec{x_i}+b)\ge 1 ,(i=1,2...m)$

以上問題右等價(jià)于以下問題：
$\min_{w,b} \frac{1}{2} ||w||^2$
$s.t.y_i(\vec{w}^T\vec{x_i}+b)\ge 1 ,(i=1,2...m)$

這個(gè)優(yōu)化問題就是支持向量機(jī)（SVM）的常見形式。

注意上述問題中w鹃祖，b是自變量，約束條件都是仿射函數(shù)普舆，所以上述優(yōu)化問題是一個(gè)凸優(yōu)化恬口。且是一個(gè)凸二次規(guī)劃問題。

對(duì)于這個(gè)凸二次規(guī)劃問題沼侣，由上文的分析祖能，我們引入拉格朗日函數(shù)：

$L(\vec{w},b,\vec{\alpha})=\frac{1}{2}||w||^2+\sum_{i=1}^m\alpha_i(1-y_i(\vec{w}^T\vec{x_i}+b))$

因?yàn)榇藭r(shí)自變量的維度是n+m+1維，解起來還是比較麻煩蛾洛，所以轉(zhuǎn)化為拉格朗日對(duì)偶問題解決养铸。

由于上面的是凸二次規(guī)劃，滿足slater條件轧膘，所以其拉格朗日對(duì)偶問題是強(qiáng)對(duì)偶钞螟，其對(duì)偶問題的最優(yōu)值就是原問題的最優(yōu)值。

第四步：下面導(dǎo)出拉格朗日對(duì)偶問題：

上面的拉格朗日函數(shù)對(duì)各個(gè)維度求偏導(dǎo)得到：
$\frac{\partial L(\vec{w},b,\vec{\alpha}) }{\partial \vec{w}}= \vec{w}-\sum_{i=1}^m\alpha_iy_i \vec{x_i}=0$
$\frac{\partial L(\vec{w},b,\vec{\alpha}) }{\partial b}=\sum_{i=1}^m\alpha_iy_i=0$

所以：
$\vec{w}-\sum_{i=1}^m\alpha_iy_i \vec{x_i}=0$
$\sum_{i=1}^m\alpha_iy_i=0$

所以原拉格朗日函數(shù)可以消掉 $w,b$ ,得到以下函數(shù)：
$L(\vec{\alpha})= \sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_jy_iy_j\vec{x_i}^T\vec{x_j}$

所以拉格朗日對(duì)偶問題為：
$\max_{\vec{\alpha}}(\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_jy_iy_j\vec{x_i}^T\vec{x_j})$
$s.t.\alpha_i\ge 0, \sum_{i=1}^m\alpha_iy_i=0$

由上面拉格朗日對(duì)偶問題的分析谎碍，這個(gè)也是一個(gè)凸優(yōu)化鳞滨，且這個(gè)優(yōu)化問題的自變量的維度只有m維，比原問題減小了n+1維蟆淀，所以大大減小了計(jì)算量拯啦。

但是在m很大是求解這個(gè)問題還是很麻煩，未解決這個(gè)問題引入順序最小化（SMO）算法扳碍，大大縮短計(jì)算時(shí)間提岔，SMO算法在下面介紹，這里為了SVM的推導(dǎo)接著進(jìn)行笋敞。

對(duì)于上面拉格朗日對(duì)偶問題碱蒙，我們用SMO算法解出 $\vec{\alpha}$ ,帶入到以下等式：
$\vec{w}-\sum_{i=1}^m\alpha_iy_i \vec{x_i}=0$

可求得 $w$ ,由于原始的帶約束的凸二次規(guī)劃中，約束條件中是不等式約束，所以轉(zhuǎn)化為拉格朗日函數(shù)求解時(shí)赛惩，會(huì)伴隨KKT條件：
$\begin{cases} \alpha_i \ge 0\\ 1-y_i(\vec{w}^T\vec{x_i}+b)\le 0\\ \alpha_j (1-y_i(\vec{w}^T\vec{x_i}+b))=0 \end{cases}$

所以此時(shí)可以得到哀墓，解出的 $\alpha_i$ 要么大于零，要么等于零喷兼。當(dāng) $\alpha_i$ 大于零時(shí)篮绰，其 $1-y_i(\vec{w}^T\vec{x_i}+b)=0$ ,此時(shí)可反解出b。

這樣我們就求出了一開始需要的超平面
$\vec{w}^t\vec{x}+b=0$

需要注意的是季惯，由 $\vec{w}=\sum_{i=1}^m\alpha_iy_i \vec{x_i} 0$
得到吠各，在求的 $\alpha_i$ 后，求解 $\vec{w}$ 時(shí)勉抓， $\alpha_i=0$ 對(duì)應(yīng)的樣本點(diǎn)是沒有起作用的贾漏，求 $\vec{w}$ 時(shí)，解起作用的是 $\alpha_i>0$ 的點(diǎn)藕筋，當(dāng) $\alpha_i>0$ 時(shí)纵散，由KKT條件，得到 $1-y_i(\vec{w}^T\vec{x_i}+b)=0$ 隐圾，這些點(diǎn)被稱為支持向量伍掀。

也就是說最終模型求解出來后，僅僅與支持向量有關(guān)暇藏，與其他點(diǎn)沒關(guān)系蜜笤。

至此，我們推導(dǎo)出了SVM的基本款叨咖。為什么說是基本款瘩例，因?yàn)橐陨夏Ｐ椭恢С肿詈?jiǎn)單的數(shù)據(jù)集是線性可分的問題。所以要對(duì)其擴(kuò)展甸各，擴(kuò)展方向有兩個(gè)垛贤，一個(gè)是數(shù)據(jù)集非線性可分，一個(gè)是數(shù)據(jù)集不可分趣倾。對(duì)于解決非線性的問題聘惦，我們引入核函數(shù)。對(duì)于不可分的問題儒恋，我們引入松弛變量善绎。下面分別介紹。

再生核希爾伯特空間诫尽、核函數(shù)與核技巧

在上面的推導(dǎo)過程中禀酱，訓(xùn)練數(shù)據(jù)集是線性可分的，如果上面的數(shù)據(jù)集D如下圖分布牧嫉，我們是不可能找到一個(gè)平面將其陰性樣本和陽(yáng)性樣本分開的剂跟。

非線性數(shù)據(jù)集圖1.PNG

此時(shí)我們要想使用SVM减途，必須做一個(gè)變換。

如上圖所示數(shù)據(jù)集曹洽，可以第i個(gè)樣本點(diǎn) $\vec{x_i}=(x_{i1},x_{i2})$ 的極坐標(biāo)變換為
$\begin{cases} x_{i1} =r_i·cos\theta_i \\ x_{i2} =r_i·sin\theta_i \end{cases}$

可以反解出 $r_i,\theta_i$ 為：
$\begin{cases} r_i =\sqrt{x_{i1}^2+x_{i2}^2} \\ \theta_i= \arctan {\frac{x_{i2}}{x_{i1}}} \end{cases}$

把上面的映射關(guān)系設(shè)為： $(r_i,\theta_i)=\phi( (x_{i1},x_{i2}) )=\phi( \vec{x_i} )$

所以原數(shù)據(jù)集的分布圖可以轉(zhuǎn)化為下圖：

非線性數(shù)據(jù)集圖2.PNG

此時(shí)若用 $(r,\theta)$ 當(dāng)成新的直角坐標(biāo)鳍置，數(shù)據(jù)集是線性可分的，是可以使用上面推導(dǎo)的SVM的送淆。

此時(shí)SVM求解時(shí)的拉格朗日對(duì)偶問題如下：
$\max_{\vec{\alpha}}(\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_jy_iy_j (r_i,\theta_i) ^T(r_j,\theta_j))$
$s.t.\alpha_i\ge 0, \sum_{i=1}^m\alpha_iy_i=0$

對(duì)于上述公式中的 $(r_i,\theta_i) ^T(r_j,\theta_j)$ ,有：

$(r_i,\theta_i)^T(r_j,\theta_j)= ((r_i,\theta_i), (r_j,\theta_j) ) = (\phi( \vec{x_i} ),\phi( \vec{x_j} ))=\phi( \vec{x_i} )^T\phi( \vec{x_j} )$

此時(shí)SVM求解時(shí)的拉格朗日對(duì)偶問題如下：
$\max_{\vec{\alpha}}(\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_jy_iy_j \phi( \vec{x_i} )^T\phi( \vec{x_j} ))$
$s.t.\alpha_i\ge 0, \sum_{i=1}^m\alpha_iy_i=0$

可以看到税产，這個(gè)問題并沒有變量 $r,\theta$ ,所以我們只要通過樣本點(diǎn) $\vec{x_i}和\vec{x_j}$ 能直接求得 $\phi( \vec{x_i} )^T\phi( \vec{x_j} )$ ,那么問題就大大的簡(jiǎn)單了，

我們?cè)O(shè)：
$\kappa ( \vec{x_i},\vec{x_j})=\phi( \vec{x_i} )^T\phi( \vec{x_j} )$

如果能找到函數(shù) $\kappa$ ,我們根本不需要知道 $\phi$ 的具體表達(dá)式偷崩，直接求解以下問題即可：
$\max_{\vec{\alpha}}(\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_jy_iy_j \kappa ( \vec{x_i},\vec{x_j}))$
$s.t.\alpha_i\ge 0, \sum_{i=1}^m\alpha_iy_i=0$

所以問題的關(guān)鍵就轉(zhuǎn)化成了兩個(gè)問題辟拷，其一、對(duì)于任意的數(shù)據(jù)集环凿， $\phi$ 是否存在梧兼，如果 $\phi$ 根本不存在，這就行不通智听。其二、 $\phi$ 如果存在渡紫，那么怎么求得 $\kappa$ .

Cover定理

對(duì)于一個(gè)復(fù)雜的模式分類問題到推，若該分類問題的樣本空間不是稠密的，則將其分類問題非線性地投射到高維空間將比投射到低維空間更可能是線性可分的惕澎。

根據(jù)cover定理莉测，若原問題線性不可分，則將其映射到比原空間更高的維度空間上唧喉，其更容易線性可分捣卤，但是也可能線性不可分的，定理中只說了更容易線性可分八孝。但是如果樣本空間中維度是有限維的董朝，我們下面還可以證明，一定存在一個(gè)映射 $\phi$ 干跛，將其映射到更高維上時(shí)子姜，問題線性可分。

最后編輯于：2020.07.21 15:53:31

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末楼入，一起剝皮案震驚了整個(gè)濱河市哥捕，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌嘉熊，老刑警劉巖遥赚，帶你破解...
沈念sama閱讀 217,406評(píng)論 6贊 503
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異阐肤，居然都是意外死亡凫佛，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,732評(píng)論 3贊 393
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來御蒲，“玉大人衣赶，你說我怎么就攤上這事『衤” “怎么了府瞄？”我有些...
開封第一講書人閱讀 163,711評(píng)論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)碘箍。經(jīng)常有香客問我遵馆，道長(zhǎng)，這世上最難降的妖魔是什么丰榴？我笑而不...
開封第一講書人閱讀 58,380評(píng)論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任货邓，我火速辦了婚禮，結(jié)果婚禮上四濒，老公的妹妹穿的比我還像新娘换况。我一直安慰自己，他們只是感情好盗蟆，可當(dāng)我...
茶點(diǎn)故事閱讀 67,432評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布戈二。她就那樣靜靜地躺著，像睡著了一般喳资。火紅的嫁衣襯著肌膚如雪觉吭。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,301評(píng)論 1贊 301
城市分裂傳說
那天仆邓，我揣著相機(jī)與錄音鲜滩，去河邊找鬼。笑死节值，一個(gè)胖子當(dāng)著我的面吹牛徙硅，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播察署，決...
沈念sama閱讀 40,145評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼闷游，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來了贴汪？” 一聲冷哼從身側(cè)響起脐往，我...
開封第一講書人閱讀 39,008評(píng)論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎扳埂，沒想到半個(gè)月后业簿，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,443評(píng)論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡阳懂，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,649評(píng)論 3贊 334
?白月光啟示錄
正文我和宋清朗相戀三年梅尤，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了柜思。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 39,795評(píng)論 1贊 347
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡巷燥，死狀恐怖赡盘，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情缰揪，我是刑警寧澤陨享，帶...
沈念sama閱讀 35,501評(píng)論 5贊 345
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站钝腺，受9級(jí)特大地震影響抛姑，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜艳狐，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,119評(píng)論 3贊 328
男人毒藥：我在死后第九天來索命
文/蒙蒙一定硝、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧毫目，春花似錦蔬啡、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,731評(píng)論 0贊 22
一樁弒父案星爪，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至粉私，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間近零，已是汗流浹背诺核。一陣腳步聲響...
開封第一講書人閱讀 32,865評(píng)論 1贊 269
情欲美人皮
我被黑心中介騙來泰國(guó)打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留久信，地道東北人窖杀。一個(gè)月前我還...
沈念sama閱讀 47,899評(píng)論 2贊 370
代替公主和親
正文我出身青樓，卻偏偏與公主長(zhǎng)得像裙士，于是被迫代替她去往敵國(guó)和親入客。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,724評(píng)論 2贊 354

Machine Learning-支持向量機(jī)（SVM）(上)

Machine Learning-支持向量機(jī)（SVM）(上)

支持向量機(jī)（SVM）

目錄

·簡(jiǎn)介

·凸二次規(guī)劃

·拉格朗日乘數(shù)法與KKT條件

·拉格朗日對(duì)偶問題

·支持向量機(jī)(SVM)

·再生核希爾伯特空間览芳、核函數(shù)與核技巧

·軟間隔（softmargin）與正則化

·SVM與邏輯回歸

·SVM與神經(jīng)網(wǎng)絡(luò)

·支持向量回歸機(jī)(SVR)

·SVR與多項(xiàng)式回歸

·順序最小化算法（SMO）

·半監(jiān)督SVM

簡(jiǎn)介

凸二次規(guī)劃（convex quadratic programming）

拉格朗日乘數(shù)法

先考慮只有等式約束的優(yōu)化問題第租；

考慮不等式約束的優(yōu)化問題

其一

其二

KKT 條件

拉格朗日乘數(shù)法詳細(xì)描述

多個(gè)約束的拉格朗日乘數(shù)法

拉格朗日對(duì)偶問題

什么是拉格朗日對(duì)偶

強(qiáng)對(duì)偶和弱對(duì)偶

引理（凸集分離定理）

定理(強(qiáng)對(duì)偶充分條件定理)：

Slater條件

為什么使用拉格朗日對(duì)偶問題

原因1

原因2

原因3

支持向量機(jī)(SVM)

再生核希爾伯特空間诫尽、核函數(shù)與核技巧

Cover定理