機器學習理論基礎(chǔ)—支持向量機的推導(dǎo)

算法原理

SVM:從幾何角度，對于線性可分數(shù)據(jù)集，支持向量機就是找距離正負樣本都最遠的超平面，相比于感知機，其解是唯一的，且不偏不倚，泛化性能更好。

超平面

n維空間的超平面（wT X+ b= 0，其中w,x ∈ R）

• 超平面方程不唯—
• 法向量w和位移項b確定一個唯一超平面
• 法向量w垂直于超平面 （縮放w，b時，若縮放倍數(shù)為負數(shù)會改變法向量方向)
• 法向量w指向的那一半空間為正空間，另一半為負空間
• 任意點到超平面的距離公式為
  

點到超平面的距離公式

理論證明：提出假設(shè)條件

1.由于法向量W與x1x0向量平行，首先計算兩個向量點乘的模長：而下x1x0向量的模長就是要求的距離R

2.按照點乘的坐標形式來進行計算，最后令兩個式子相等即可以得到最終的結(jié)果。

兩個式子相等得到最終的結(jié)果：

幾何間隔

定義：M關(guān)于超平面的幾何間隔為：（樣本點的形式）

正確分類是指：正樣本都集中在正空間，負樣本都集中在負空間。

• 正確分類時r(i)>0,幾何間隔此時也等價于點到超平面的距離。
• 沒有正確分類時：r(i)<0

（數(shù)據(jù)集的定義形式 X為（x1,x2…）的數(shù)據(jù)集）：即是所有樣本點幾何間隔的最小值。

支持向量機

模型定義：給定線性可分數(shù)據(jù)集X，支持向量機模型希望求得數(shù)據(jù)集X關(guān)于超平面的幾何間隔達到最大的那個超平面，然后套上一個sign函數(shù)實現(xiàn)分類功能

其中與感知機模型的區(qū)別在于，參數(shù)的不同支持向量機中的參數(shù)為b而感知機中的參數(shù)為一個閾值。

幾何間隔最大的超平面一定是距離正負樣本最遠的超平面。

當超平面沒有正確劃分正負樣本時：幾何間隔最小的為誤分類點，因此r<0
當超平面正確劃分超平面時：r≥0，且越靠近中央越大。

支持向量機學習策略

策略：給定線性可分數(shù)據(jù)集X，設(shè)X中幾何間隔最小的樣本(xmin,ymin），那么支持向量機找超平面的過程可以轉(zhuǎn)化為以下帶約束條件的優(yōu)化問題。

根據(jù)幾何間隔的定義帶入進行求解，可以得到最終的結(jié)果式子與約束條件


化簡后的公式存在的問題：
假設(shè)該問題的最優(yōu)解為(w*,b*），那么(αw*，αb*），α ∈R+也是最優(yōu)解，且超平面也不變，因此還需要對w,b做一定限制才能使得上述優(yōu)化問題有可解的唯一解。不妨令

因為對于特定的(Xmin,Ymin)來說，使得該公式為1的α 的值只有一個
因此該公式和約束條件可以進一步優(yōu)化為：

為了便于計算在進一步進行化簡得到最終的學習策略結(jié)果（平方取反轉(zhuǎn)換為最小值問題）。

此優(yōu)化問題為含不等式約束的優(yōu)化問題，且為凸優(yōu)化問題，因此可以直接用很多專門求解凸優(yōu)化問題的方法求解該問題，在這里，支持向量機通常采用拉格朗日對偶來求解。

凸優(yōu)化問題

若目標函數(shù)f(x)是凸函數(shù)，約束集合是凸集，則稱上述優(yōu)化問題為凸優(yōu)化問題，特別地，g(x)是凸函數(shù)，h(x)是線性函數(shù)時，約束集合為凸集，該優(yōu)化問題為凸優(yōu)化問題。顯然，支持向量機的目標函數(shù)1/2||w||2是關(guān)于w的凸函數(shù)，不等式約束1 一y(wtx(i)十b)是也是關(guān)于w的凸函數(shù)，因此支持向量機是一個凸優(yōu)化問題。

拉格朗日對偶

用來處理一般的約束問題，對于上面的公式，使用拉格朗日函數(shù)進行構(gòu)造可得有

其中μ=（μ1,μ2，·,μm)T,入=（入1,入2，.,入n)T為拉格朗日乘子向量。
定義上述優(yōu)化問題的拉格朗日對偶函數(shù)T(μ,入）（注意其自變量不包含x）為L(x，μ，入)關(guān)于x的下確界，也即：

無論上述優(yōu)化問題是否是凸優(yōu)化問題，其對偶函數(shù)T(μ,入)恒為凹函數(shù) (證明參見《凸優(yōu)化》）當μ≥0時，(μ,入)構(gòu)成了上述優(yōu)化問題最優(yōu)值p*的下界，也即:
對上面的使用拉格朗日對偶函數(shù)求最優(yōu)值提供參考的證明步驟

定義在滿足μ≥ 0這個約束條件下求對偶函數(shù)最大值的優(yōu)化問題為拉格朗日對偶問題（原優(yōu)化問題稱為主問題）

設(shè)該優(yōu)化問題的最優(yōu)值為d*，顯然d≤ p，此時稱為“弱對偶性"成立，若d* = p*，則稱為“強對偶性"成立。找到了求p*的方法（上面有參考的證明過程）

無論主問題是否為凸優(yōu)化問題，對偶問題恒為凸優(yōu)化問題，因為對偶函數(shù)T(μ,入)恒為凹函數(shù)（加個負號即可轉(zhuǎn)為凸函數(shù)），約束條件μ≥0恒為凸集。

當主問題滿足某些充分條件時，強對偶性成立。常見的充分條件有Slater條件：“若主問題是凸優(yōu)化問題，且可行集D中存在一點能使得所有不等式約束的不等號成立，則強對偶性成立”（證明參見《凸優(yōu)化》）。顯然，支持向量機滿足Slater條件。

KKT條件（5個）

設(shè)f(x),g(x),h(x)一階偏導(dǎo)連續(xù)，x*，（μ*，入*)分別為主問題和對偶問題的最優(yōu)解，若強對偶性成立，則x*，μ*，入*一定滿足如下5個條件（證明參見《凸優(yōu)化》

得出了第一種推導(dǎo)形式

根據(jù)支持向量機的主問題直接引出拉格朗日函數(shù)=0并對其求一階偏導(dǎo)

若將w,b合并為=（w;b)，顯然上式是關(guān)于w的凸函數(shù)，直接求一階導(dǎo)令其等于0，然后帶回即可得到最小值，也即拉格朗日對偶函數(shù)。文章來源地址http://www.zghlxwxcb.cn/news/detail-861339.html

到了這里，關(guān)于機器學習理論基礎(chǔ)—支持向量機的推導(dǎo)（一）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！