黑人猛操久久,久久久久久久免费播,AV老司机午夜福利

SVM（Support Vector Machine，支持向量機）是最經(jīng)典的分類算法，本文主要整理（為了應(yīng)付考試）SVM的推導(dǎo)方式，不包含SMO算法求解最后的約束。

借鑒博客：
https://cuijiahua.com/blog/2017/11/ml_8_svm_1.html

https://www.cnblogs.com/90zeng/p/Lagrange_duality.html

一般的，SVM就是一個分類器，只是相對于傳統(tǒng)的線性分類器，它添加了一個支持向量的概念。這樣相對于傳統(tǒng)分類器可能存在的多個解，SVM由于約束的存在一般只有單解，并且表現(xiàn)更好。

從圖片上解釋，對于一組數(shù)據(jù)，傳統(tǒng)的線性分類器使用一條直線將數(shù)據(jù)分類，而SVM在使用直線的同時要求數(shù)據(jù)點距離這條直線的最小距離最大，也就是說分類器和數(shù)據(jù)之間要有足夠大的“間隔”。這樣做的好處是很明顯的，越大的“間隔”代表了更大的轉(zhuǎn)圜空間，在得到新的數(shù)據(jù)之后更容易將其正確分類。

而SVM的工作就是求解這個最大間隔，也就是最優(yōu)化問題。對于線性可分的數(shù)據(jù)，可以直接套用線性規(guī)劃的知識進(jìn)行推導(dǎo)，但如果數(shù)據(jù)線性不可分，就需要核函數(shù)進(jìn)行數(shù)據(jù)升維，進(jìn)行超平面分類。

二分類問題的數(shù)據(jù)點

傳統(tǒng)的線性分類器

SVM的分類方式，要求“間隔”最大

下面是具體的建模推導(dǎo)過程：

一·決策面方程

我們現(xiàn)在二維場景下考慮分類方程，所以決策面也就是決策線。

考慮在二維場景下，我們描述一條直線的方法是：

$y=ax+b$

簡單替換，將 $y$ 替換為 $x_2$ ，將 $x$ 替換為 $x_1$ ，簡單獲得以下公式：

$x_2=ax_1+b$

=> $ax_1-x_2+b=0$

將上述公式轉(zhuǎn)換為向量形式：

$[a,-1][\begin{array}{c} x_1 \\ x_2\end{array}] +b=0$

也就是 $\omega ^Tx+\gamma =0, 其中，\omega=[a,-1]^T,x=[x_1,x_2]^T$

這個式子的幾何意義是原式子的法向量。而如果我們將上述式子推廣到高維空間，就是我們需要的決策面方程。也就是：

$\omega ^Tx+\gamma =0, 其中，\omega=[\omega_1, \dots, \omega_n]^T,x=[x_1,\dots,x_n]^T$

二·分類間隔方程

在獲取決策面方程之后，我們需要獲知決策面方程中的 $\omega$ 和 $\gamma$ 的具體值，而求解這個值的核心就是靠分類間隔方程所施加的約束條件。

首先我們需要副系以下間隔的含義，在SVM中，“間隔”指的是分類器距離樣本點的最小距離，我們需要找一個使這個最小距離最大的分類器作為我們的最優(yōu)解。因此我們的約束條件是很好想到的，高中學(xué)過的距離公式：

$\begin{equation} \left\{ \begin{array}{**lr**} d=\frac{Ax_0+By_0+C}{\sqrt{A^2+B^2} } , & \\點(x_0,y_0),直線Ax+By+C=0\end{array} \right. \end{equation}$

而在超平面上，只需要簡單的推廣以上公式，結(jié)合我們之前獲得的決策面方程，

$\omega ^Tx+\gamma =0, 其中，\omega=[\omega_1, \dots, \omega_n]^T,x=[x_1,\dots,x_n]^T$

我們不難得到，在我們所得到的直線（超平面上），某個樣本與其的距離是：

$d=\frac{|\omega^Tx+\gamma|}{||\omega||}$ ?

分母是指 $\omega$ 的二范數(shù)，也就是平方和求導(dǎo)。這樣我們的問題就轉(zhuǎn)化為，求最大的 $W$ ，其中 $W=2d$ ，也就是求 $\max \limits_{}d$ 。

三·約束條件

獲取了上述分類間隔方程，但是這個方程只是來評判我們的分類器是否是好的，我們并不能確定

（1）分類器是否能正確分類

（2）如何選擇正確的支持向量點

這兩個問題是限制我們隨意計算 $d$ 的限制條件，在SVM中，以下列方式處理這些限制條件。

首先仍然只考慮線性可分的二分類情況，在這種情況下只有兩類數(shù)據(jù)，我們對這兩類數(shù)據(jù)分別賦值為1和-1，也就是：

$y=\begin{equation} \left\{ \begin{array}{**lr**} 1 , 數(shù)據(jù)屬于第一類& \\-1.數(shù)據(jù)屬于第二類\end{array} \right. \end{equation}$

分類還是很直觀的，事實上我們在有監(jiān)督學(xué)習(xí)里面基本也這么賦值。這樣賦值之后，假設(shè)我們所得到的分類器可以正確分類兩類數(shù)據(jù)，那么我們的分類器可以得出什么結(jié)果？不難得到以下形式：

$y=\begin{equation} \left\{ \begin{array}{**lr**} \omega^T+\gamma>0, y_i=1& \\\omega^T+\gamma<0, y_i=-1\end{array} \right. \end{equation}$

如果我們嚴(yán)格一點（或者說運氣很好），我們得到的分類器是SVM的最優(yōu)解，那么根據(jù)上面的距離公式，我們可以簡化得到：

$\begin{equation} \left\{ \begin{array}{**lr**} \frac{|\omega^Tx+\gamma|}{||\omega||}\ge d, y_i=1& \\\frac{|\omega^Tx+\gamma|}{||\omega||}\le -d, y_i=-1\end{array} \right. \end{equation}$

$\Rightarrow \begin{equation} \left\{ \begin{array}{**lr**} \omega_d^Tx+\gamma_d\ge 1, y_i=1& \\\omega_d^Tx+\gamma_d\le 1, y_i=-1\end{array} \right. \end{equation}$

其中：

$\omega_d^T=\frac{\omega}{||\omega||d}$ ? ?? $\gamma_d=\frac{\gamma}{||\omega||d}$

分母都是標(biāo)量，所以除以 $d$ 并不影響原式子的幾何含義，也就是法向量。那么我們事實上拿掉這個 $d$

也不會影響最后的結(jié)果。最后對以上式子進(jìn)行整理，即可獲得一個不等式：

$y_i(\omega^Tx+\gamma)\ge 1, \forall x_i$

這里的 $\omega$ 與上文中的 $\omega$ 在數(shù)值上不同，但是在幾何意義上是一樣的。

四·優(yōu)化問題描述

在三中，我們考慮了如果我們的分類器可以正確分類，我們的公式要如何進(jìn)行約束，那么現(xiàn)在我們需要解決第二個問題了，如果選取支持向量點？

這個問題比較好考慮，支持向量點有一個特征，那就是對于一個支持向量點 $x_i$ ,必然有

$|\omega^Tx_i+\gamma| = 1$

那么在我們預(yù)先定義好的距離公式 $d=\frac{|\omega^Tx+\gamma|}{||\omega||}$ 中，我們發(fā)現(xiàn)帶入上式子的結(jié)果，有

$d=\frac{1}{||\omega||}$

那么我們對 $d$ 的最大值約束就變化為對 $\omega$ 的最小值約束，也就是求解 $min\frac{1}{2}||\omega||^2,其中y_i(\omega^Tx_i+b)\ge 1,i=1,2,\dots,n$

五·求解準(zhǔn)備

在得到上述式子之后，我們發(fā)現(xiàn)這是一個帶有不等式約束的規(guī)劃問題，為了解決這種問題，我們一般采用構(gòu)造拉格朗日函數(shù)的方法，使用對偶性解決問題。

5.1·拉格朗日函數(shù)

首先，我們先要從宏觀的視野上了解一下拉格朗日對偶問題出現(xiàn)的原因和背景。

我們知道我們要求解的是最小化問題，所以一個直觀的想法是如果我能夠構(gòu)造一個函數(shù)，使得該函數(shù)在可行解區(qū)域內(nèi)與原目標(biāo)函數(shù)完全一致，而在可行解區(qū)域外的數(shù)值非常大，甚至是無窮大，那么這個沒有約束條件的新目標(biāo)函數(shù)的優(yōu)化問題就與原來有約束條件的原始目標(biāo)函數(shù)的優(yōu)化問題是等價的問題。

這就是使用拉格朗日方程的目的，它將約束條件放到目標(biāo)函數(shù)中，從而將有約束優(yōu)化問題轉(zhuǎn)換為無約束優(yōu)化問題。

隨后，人們又發(fā)現(xiàn)，使用拉格朗日獲得的函數(shù)，使用求導(dǎo)的方法求解依然困難。進(jìn)而，需要對問題再進(jìn)行一次轉(zhuǎn)換，即使用一個數(shù)學(xué)技巧：拉格朗日對偶。

所以，顯而易見的是，我們在拉格朗日優(yōu)化我們的問題這個道路上，需要進(jìn)行下面二個步驟：

將有約束的原始目標(biāo)函數(shù)轉(zhuǎn)換為無約束的新構(gòu)造的拉格朗日目標(biāo)函數(shù)

使用拉格朗日對偶性，將不易求解的優(yōu)化問題轉(zhuǎn)化為易求解的優(yōu)化

下面，進(jìn)行第一步：將有約束的原始目標(biāo)函數(shù)轉(zhuǎn)換為無約束的新構(gòu)造的拉格朗日目標(biāo)函數(shù)

先寫下原始式子：

$min\frac{1}{2}||\omega||^2,其中y_i(\omega^Tx_i+b)\ge 1,i=1,2,\dots,n$

我們首先將其變形，將其變?yōu)槿缦赂袷剑?/p>

$L(\omega,b,\alpha)=\frac{1}{2}||\omega||^2-\sum_{i=1}^n \alpha_i[y_i(\omega^Tx_i+b)-1]$

其中 $\alpha_i \ge 0$ 被稱為拉格朗日乘子，當(dāng)然雖然名字很嚇唬人，事實上它是我們隨意引入的一個參數(shù)。這個參數(shù)是用來構(gòu)造等價問題的。

我們令 $\theta(\omega,b)=\max \limits_ {\alpha_i \ge 0}\ L(\omega,b,\alpha)$ 。

也就是當(dāng)前這個方程和 $\alpha_i$ 無關(guān)，當(dāng)某個點 $x_i$ 不在可行解區(qū)域中，也就是 $y_i(\omega^Tx_i+b) < 1$ ,我們將 $\alpha_i$ 設(shè)置為無窮大，顯然此時 $\theta(\omega,b)$ 也是無窮大的。而當(dāng)該點在可行域區(qū)域內(nèi)， $y_i(\omega^Tx_i+b) \ge 1$ ，那么 $\max \limits_ {\alpha_i \ge 0}\ L(\omega,b,\alpha)$ 的結(jié)果顯然是 $\frac{1}{2}||\omega||^2$ （因為后半部分必然大于等于0，那么為了保證最大，當(dāng)然是等于0）。這樣， $\theta(\omega,b)$ 就可以轉(zhuǎn)化為：

$\theta(\omega,b)=\begin{equation} \left\{ \begin{array}{**lr**} \frac{1}{2}||\omega||^2, x_i在可行域\\+\infty，x_i不在可行域\end{array} \right. \end{equation}$

顯然在可行域內(nèi)， $\theta$ 是一個凸函數(shù)，是必然有極小值的，因此問題被轉(zhuǎn)化為求此函數(shù)的最小值，也就是：

$\min \limits_{\omega,b}\theta(\omega,b)=\min \limits_{\omega,b}\max\limits_{\alpha_i\ge0}L(\omega,b,\alpha)=p^*$

這個式子事實上也不好求，因為內(nèi)層的 $max$ 仍然帶有不等式的限制條件，因此我們要使用拉格朗日對偶方法將其轉(zhuǎn)化為易求的對偶形式。

5.2 拉格朗日對偶及其證明

拉格朗日對偶的定義如下：

以我們剛剛獲得的式子 $\min \limits_{\omega,b}\theta(\omega,b)=\min \limits_{\omega,b}\max\limits_{\alpha_i\ge0}L(\omega,b,\alpha)=p^*$ 為例，我們先針對 $\alpha$ 作為未知數(shù)構(gòu)造一個函數(shù)：

$\theta(\alpha)=\min \limits_{\omega,b}L(\omega,b,\alpha)$

考慮其極大化，也就是 $\max\limits_{\alpha;\alpha_i\ge0}\theta(\alpha)=\max\limits_{\alpha;\alpha_i\ge0}\min \limits_{\omega,b}L(\omega,b,\alpha)$

這個問題就是原始問題的對偶問題了。假設(shè)我們使 $\max\limits_{\alpha;\alpha_i\ge0}\theta(\alpha)=\max\limits_{\alpha;\alpha_i\ge0}\min \limits_{\omega,b}L(\omega,b,\alpha)=d^*$

則可以證明 $d^*\le p^*$

證明方式：對于任意的 $\alpha,\omega和b$ ，有 $\theta_d(\alpha)=\min\limits_{\omega,b}L(\omega,b,\alpha)\le L(\omega,b,\alpha)\le \max\limits_{\alpha\ge 0}L(\omega,b,\alpha)\le \theta_p(\omega,b)$

不難推論，當(dāng) $d^*=p^*$ 時，此時 $\omega^*,b^*,\alpha^*$ 均為最優(yōu)解。

那么如何使得上述相等情況成立呢？這就需要滿足KKT條件。

5.3·KKT條件

KKT條件的全稱是Karush-Kuhn-Tucker條件，KKT條件是說最優(yōu)值條件必須滿足以下條件：

條件一：經(jīng)過拉格朗日函數(shù)處理之后的新目標(biāo)函數(shù)L(w,b,α)對x求導(dǎo)為零：

條件二：h(x) = 0；

條件三：α*g(x) = 0；

我們的式子已經(jīng)滿足此條件，具體的嘛……反正我也不懂，先記下來以后補= =

六·最終結(jié)果

已知 $\max\limits_{\alpha;\alpha_i\ge0}\theta(\alpha)=\max\limits_{\alpha;\alpha_i\ge0}\min \limits_{\omega,b}L(\omega,b,\alpha)=d^*$

$L(\omega,b,\alpha)=\frac{1}{2}||\omega||^2-\sum_{i=1}^n \alpha_i[y_i(\omega^Tx_i+b)-1]$

首先固定 $\alpha$ ,針對內(nèi)層最小化求導(dǎo)，可以得到：

$\frac{\alpha L}{\alpha \omega}=0 \Rightarrow \omega=\sum_{i=1}^n \alpha_iy_ix_i$

$\frac{\alpha L}{\alpha b}=0 \Rightarrow \sum_{i=1}^n \alpha_iy_i=0$

帶入原式：

$\begin{equation}\begin{aligned}L(\omega,b,\alpha)&=\frac{1}{2}||\omega||^2-\sum_{i=1}^n \alpha_i[y_i(\omega^Tx_i+b-1) ] \\&=\frac{1}{2}\omega^T\omega-\omega^T\sum_{i=1}^n\alpha_iy_ix_i-b\sum_{i=1}^n\alpha_iy_i+ \sum_{i=1}^n\alpha_i \\&=\frac{1}{2}\omega^T\sum_{i=1}^n\alpha_iy_ix_i-\omega^T\sum_{i=1}^n\alpha_ix_iy_i-b*0+\sum_{i=1}^n\alpha_i\\&=\sum_{i=1}^n\alpha_i-\frac{1}{2}(\sum_{i=1}^n\alpha_iy_ix_i)^T\sum_{i=1}^n\alpha_iy_ix_i\\&=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j\end{aligned}\end{equation}$

此時只有一個參數(shù)， $\alpha_i$

然后我們計算外層的最大化，

$\max\limits_{\alpha}\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j\\s.t.\ \alpha_i \ge0, \ \ i =1,2,\dots,n\\\sum_{i=1}^n\alpha_iy_i=0$

現(xiàn)在我們的優(yōu)化問題變成了如上的形式。對于這個問題，我們有更高效的優(yōu)化算法，即序列最小優(yōu)化（SMO）算法。我們通過這個優(yōu)化算法能得到α，再根據(jù)α，我們就可以求解出w和b，進(jìn)而求得我們最初的目的：找到超平面，即"決策平面"。

七·非線性與核函數(shù)

前面六個部分都是建立在數(shù)據(jù)線性可分的情況之下，而當(dāng)數(shù)據(jù)不可分時，我們需要使用一些方法將其升維，使其在高維空間成為可分的。

總體而言，經(jīng)過SMO計算出 $\alpha$ 之后，可以得到最后的方程：

$f(x) = \sum_{i=1}^n\alpha_iy_ix_i^Tx + b$

使用內(nèi)積表示它：

$f(x) = \sum_{i=1}^n\alpha_iy_i<x_i,x> + b$

如果數(shù)據(jù)是不可分的，我們使用一個非線性映射（不管這個映射是什么樣的，事實上往往不知道這是什么映射，映射獲得的結(jié)果也可能無法計算）將數(shù)據(jù)映射到高維空間，使其在高維空間可分，則上式可以改寫為：

$f(x) = \sum_{i=1}^n\alpha_iy_i<\phi (x_i),\phi(x)> + b$

其中 $\phi(x)$ 是一個映射，它表示輸入空間到特征空間的映射。

這種映射結(jié)果，牽扯到高維空間的內(nèi)積運算，而高維空間維度越高我們需要的計算量就越大，有時候甚至是無限維的，導(dǎo)致不能直接計算。因此我們定義了一個核函數(shù)(kernel function)，其本質(zhì)是在輸入空間的一個函數(shù) $\kappa$ ，我們?nèi)绻梢允沟?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Ckappa(x_i%2C%20x)%3D%3C%5Cphi(x_i)%2C%5Cphi(x)%3E" alt="\kappa(x_i, x)=<\phi(x_i),\phi(x)>" mathimg="1">，那么計算就可以局限在輸入空間的低緯度，減少計算資源的消耗。

所以直接就給出一個定義：核是一個函數(shù)k，對所有x,z∈X，滿足k(x,z)=<?(xi),?(x)>，這里?(·)是從原始輸入空間X到內(nèi)積空間F的映射。

在實際使用中，有多種比較常見的核函數(shù)形式（所以核函數(shù)實際上都是一種近似）：

常用的核函數(shù)

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

SVM推導(dǎo)步驟

SVM推導(dǎo)步驟

一·決策面方程

二·分類間隔方程

三·約束條件

四·優(yōu)化問題描述