考慮一個(gè)二分類問題。假設(shè)輸入空間與特征空間為兩個(gè)不同的空間。輸入空間為歐氏空間或離散集合，特征空間為歐式空間或希爾伯特空間。線性可分支持向量機(jī)、線性支持向量機(jī)假設(shè)這兩個(gè)空間的元素一一對應(yīng)，并將輸入空間中的輸入映射為特征空間中的特征向量。非線性支持向量機(jī)利用一個(gè)從輸入空間到特征空間的非線性映射將輸入映射為特征向量（核技巧）。支持向量機(jī)的學(xué)習(xí)是在特征空間進(jìn)行的。

輸入空間：輸入空間是輸入的所有可能取值的集合。

特征空間：特征空間是所有特征向量存在的空間，特征向量的每一維代表一個(gè)特征，通常與輸入空間一一對應(yīng)，但也可以通過映射函數(shù)從輸入空間映射得到特征空間。

歐氏空間：內(nèi)積空間+完備性+有限維。

希爾伯特空間：內(nèi)積空間+完備性，可以看做歐式空間在無限維的情形。

線性可分支持向量機(jī)、線性支持向量機(jī)處理的樣本在輸入空間上就通過線性劃分，所以輸入空間和特征空間一一對應(yīng)。非線性支持向量機(jī)處理的樣本在輸入空間上不可以線性劃分，所以需要通過映射函數(shù)從輸入空間映射到特征空間使其在特征空間上可以線性劃分，最終轉(zhuǎn)化成線性可分支持向量機(jī)、線性支持向量機(jī)的形式。

問題

假設(shè)給定一個(gè)特征空間上的訓(xùn)練數(shù)據(jù)集
$T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N) \}$
其中， $x_i\in\mathcal X=\textbf R^n$ ， $y_i\in\mathcal Y=\{+1,-1 \}$ ， $i=1,2,\cdots,N$ ， $x_i$ 為第 $i$ 個(gè)特征向量，也稱為實(shí)例， $y_i$ 為 $x_i$ 的類標(biāo)記，當(dāng) $y_i=+1$ 時(shí)，稱 $x_i$ 為正例；當(dāng) $y_i=-1$ 時(shí)，稱 $x_i$ 為負(fù)例， $(x_i,y_i)$ 稱為樣本點(diǎn)。再假設(shè)訓(xùn)練數(shù)據(jù)集是線性可分的。

線性可分：用一個(gè)超平面可以將正負(fù)例完全正確的劃分在超平面兩側(cè)。

學(xué)習(xí)的目的是找到一個(gè)超平面：
$w^*\cdot x+b^*=0$
對于一個(gè)新的輸入 $x$ 的分類決策函數(shù)為：
$f(x)=\mathrm{sign}(w^*\cdot x+b^*)$
滿足條件的這樣的超平面可能有很多個(gè)，但是支持向量機(jī)通過幾何間隔在超平面的選擇上加上了約束，即最大化幾何間隔，使最后得到的超平面是唯一的。

函數(shù)間隔和幾何間隔

函數(shù)間隔

一般來說，一個(gè)樣本點(diǎn)到超平面的距離代表了支持向量機(jī)對這個(gè)樣本分類的確信程度。由于當(dāng)超平面確定，點(diǎn)到平面的距離公式
$\frac {|w\cdot x+b|}{||w||}$
的分母為一個(gè)常量，所以確信程度的大小由分子 $|w\cdot x+b|$ 決定。于是定義樣本點(diǎn) $(x_i,y_i)$ 的函數(shù)間隔：
$\hat \gamma_i=y_i(w\cdot x_i+b)\tag1$
對于 $T$ 中所有樣本的函數(shù)間隔：
$\hat \gamma=\min_{i=1,\cdots N}\hat\gamma_i\tag2$
當(dāng)超平面能夠完全分類正確時(shí) $y_i(w\cdot x_i+b)\geq0$ ，所以函數(shù)間隔代表確信程度最小樣本的確信程度，最大化函數(shù)間隔就等于最大化支持向量機(jī)對樣本分類的確信程度。在線性可分支持向量機(jī)中，這也稱為硬間隔最大化。

幾何間隔

由于對參數(shù) $w$ 和 $b$ 成比例縮放，就可以改變函數(shù)間隔 $\hat\gamma$ 的大小，但這仍然表示同一個(gè)超平面。所以提出幾何間隔 $\gamma$ 對 $w$ 規(guī)范化：
$\gamma_i=\frac{\hat \gamma_i}{||w||}\tag3$

$\gamma=\frac{\hat \gamma}{||w||}\tag4$

$||w||$ 代表 $w$ 的 $L2$ 范數(shù)。

重新定義問題

學(xué)習(xí)一個(gè)超平面：
$w\cdot x+b=0$
超平面的參數(shù) $w$ 和 $b$ 需要滿足條件
$\max_{w,b}\gamma\tag5$

$\mathrm{s.t.}\ \ y_i(\frac{w}{||w||}\cdot x_i+\frac{||w||})\geq\gamma,\ \ i=1,2,\cdots,N\tag6$

根據(jù)公式(4)將(5)-(6)轉(zhuǎn)化為關(guān)于函數(shù)間隔 $\hat\gamma$ 的表述方式：

$\max_{w,b}\frac{\hat\gamma}{||w||}\tag7$

$\mathrm{s.t.}\ \ y_i(w\cdot x_i+b)\geq\hat\gamma,\ \ i=1,2,\cdots,N\tag8$

由于函數(shù)間隔 $\hat\gamma$ 的取值不會影響最優(yōu)化問題的解（參數(shù) $w$ 和 $b$ 成比例縮放），所以取 $\hat\gamma=1$ 。而最大化 $\frac{1}{||w||}$ 等價(jià)于最小化 $\frac12||w||^2$ ，所以支持向量機(jī)最終可以表示成最優(yōu)化問題：
$\min_{w,b}\ \ \frac12||w||^2\tag9$

$\mathrm{s.t.}\ \ 1-y_i(w\cdot x_i+b)\leq0,\ \ i=1,2,\cdots,N\tag{10}$

這是一個(gè)凸二次規(guī)劃問題，即目標(biāo)函數(shù) $f(w)=\frac12||w||^2$ 是二次函數(shù)，且約束函數(shù) $g_i(w)=1-y_i(w\cdot x_i+b)$ 是仿射函數(shù)。

線性可分支持向量機(jī)學(xué)習(xí)算法--最大間隔法

輸入：線性可分訓(xùn)練數(shù)據(jù)集 $T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N) \}$ ，其中 $x_i\in\mathcal X=\textbf R^n$ ， $y_i\in\mathcal Y=\{+1,-1 \}$ ， $i=1,2,\cdots,N$ ；

輸出：最大間隔分離超平面和分類決策函數(shù)。

（1）構(gòu)造并求解約束最優(yōu)化問題：
$\min_{w,b}\ \ \frac12||w||^2$

$\mathrm{s.t.}\ \ 1-y_i(w\cdot x_i+b)\leq0,\ \ i=1,2,\cdots,N$

求得最優(yōu)解 $w^*$ ， $b^*$ 。

（2）由此得到分離超平面：
$w^*\cdot x+b^*=0$
分類決策函數(shù)：
$f(x)=\mathrm{sign}(w^*\cdot x+b^*)$
這樣的超平面存在且唯一，證明略。

支持向量和間隔邊界

支持向量是使約束條件公式(10)等號成立的點(diǎn)，即
$w\cdot x_i+b=y_i$
對于正例 $y_i=+1$ ，支持向量在超平面
$H_1:w\cdot x+b=1$
對于負(fù)例 $y_i=-1$ ，支持向量在超平面
$H_2:w\cdot x+b=-1$
如圖所示

間隔邊界

落在 $H_1$ 和 $H_2$ 上的實(shí)例點(diǎn)稱為支持向量， $H_1$ 和 $H_2$ 之間的距離稱為間隔， $H_1$ 和 $H_2$ 稱為間隔邊界。在決定超平面時(shí)，只有支持向量起作用，所以這種模型叫做支持向量機(jī)。

學(xué)習(xí)的對偶算法

對于最優(yōu)化問題(9)-(10)：
$\min_{w,b}\ \ \frac12||w||^2$

$\mathrm{s.t.}\ \ 1-y_i(w\cdot x_i+b)\leq0,\ \ i=1,2,\cdots,N$

首先構(gòu)建拉格朗日函數(shù)：
$L(w,b,a)=\frac12||w||^2-\sum_{i=1}^N\alpha_iy_i(w\cdot x_i+b)+\sum_{i=1}^N\alpha_i\tag{11}$
其中 $\alpha_i\geq0$ ，則原始問題為極小極大問題：
$\min_{w,b}\max_\alpha L(w,b,a)$
由拉格朗日對偶性改為求解原始問題的對偶問題：
$\max_\alpha\min_{w,b}L(w,b,a)$
首先求解對偶問題的內(nèi)部極小問題：
$\min_{w,b}L(w,b,a)$
將拉格朗日函數(shù)分別對 $w$ ， $b$ 求偏導(dǎo)并令其等于0：
$\nabla_wL(w,b,\alpha)=w-\sum_{i=1}^N\alpha_iy_ix_i=0$

$\sum_{i=1}^N\alpha_iy_i=0$

得到：
$w=\sum_{i=1}^N\alpha_iy_ix_i\tag{12}$

$\sum_{i=1}^N\alpha_iy_i=0\tag{13}$

將其代入(11)得到：
$\begin{align} L(w,b,\alpha)&=\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_iy_i\Bigg(\bigg(\sum_{j=1}^N\alpha_jy_jx_j\bigg)\cdot x_i+b\Bigg)+\sum_{i=1}^N\alpha_i\\ &=\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-b\sum_{i=1}^N\alpha_iy_i+\sum_{i=1}^N\alpha_i\\ &=-\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i \end{align}$
于是對偶問題為：
$\max_\alpha-\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i\tag{14}$

$\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0$

$\alpha_i\geq0,\ \ i=1,2,\cdots,N$

對(14)的目標(biāo)函數(shù)取相反數(shù)轉(zhuǎn)化為極小問題：
$\min_\alpha\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i\tag{15}$

$\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0$

$\alpha_i\geq0,\ \ i=1,2,\cdots,N$

定理

設(shè) $\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)$ 是對偶問題最優(yōu)化問題
$\min_\alpha\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i$

$\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0$

$\alpha_i\geq0,\ \ i=1,2,\cdots,N$

的解，則存在下標(biāo) $j$ ，使得 $\alpha_j^*\gt0$ ，并按下式求得原始最優(yōu)化問題
$\min_{w,b}\ \ \frac12||w||^2$

$\mathrm{s.t.}\ \ 1-y_i(w\cdot x_i+b)\leq0,\ \ i=1,2,\cdots,N$

的解 $w^*$ ， $b^*$
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i\tag{16}$

$b^*=y_j-\sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)\tag{17}$

證明

由于目標(biāo)函數(shù) $f(w)=\frac12||w||^2$ 和約束函數(shù) $g_i(w)=1-y_i(w\cdot x_i+b)$ 是凸函數(shù)，且假設(shè)不等式約束 $g_i(w)$ 是嚴(yán)格可行的，則 $w^*$ ， $b^*$ ， $\alpha^*$ 分別原始問題和對偶問題的解的充分必要條件是 $w^*$ ， $b^*$ ， $\alpha^*$ 滿足 $KKT$ 條件：
$\nabla_wL(w^*,b^*,\alpha^*)=w^*-\sum_{i=1}^N\alpha_i^*y_ix_i=0\tag{18}$

$\nabla_bL(w^*,b^*,\alpha^*)=-\sum_{i=1}^N\alpha_i^*y_i=0\tag{19}$

$\alpha_i^*g_i(w^*)=\alpha_i^*(1-y_i(w^*\cdot x_i+b^*))=0\tag{20}$

$g_i(w^*)=1-y_i(w^*\cdot x_i+b^*)\leq0\tag{21}$

$\alpha_i^*\geq0,\ \ i=1,2,\cdots,N\tag{22}$

由(18)得
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$
由反證法，假設(shè)不存在下標(biāo) $j$ ，使得 $\alpha_j^*\gt0$ ，根據(jù)(22)，則 $\alpha^*=0$ ，代入(18)得到 $w^*=0$ ，超平面不存在，假設(shè)不成立。于是存在下標(biāo) $j$ ，使得 $\alpha_j^*\gt0$ ，根據(jù)(20)得到
$1-y_j(w^*\cdot x_j+b^*)=0$
根據(jù) $y_j^2=1$ 得
$y_j(w^*\cdot x_j+b^*)=y_j^2$
解得
$b^*=y_j-w^*\cdot x_j$
將
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$
代入得到
$b^*=y_j-\sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)$
證明完成。

線性可分支持向量機(jī)的對偶學(xué)習(xí)算法

輸入：線性可分訓(xùn)練數(shù)據(jù)集 $T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N) \}$ 其中 $x_i\in\mathcal X=\textbf R^n$ ， $y_i\in\mathcal Y=\{+1,-1 \}$ ， $i=1,2,\cdots,N$ ；

輸出：最大間隔分離超平面和分類決策函數(shù)。

（1）構(gòu)造并求解約束最優(yōu)化問題
$\min_\alpha\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i\tag{15}$

$\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0$

$\alpha_i\geq0,\ \ i=1,2,\cdots,N$

求得最優(yōu)解 $\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)$ 。

（2）計(jì)算
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$
并選擇 $\alpha^*$ 的一個(gè)正分量 $\alpha_j^*\gt0$ ，計(jì)算
$b^*=y_j-\sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)$
（3）求得分離超平面
$w^*\cdot x+b^*=0$
分類決策函數(shù)：
$f(x)=\mathrm{sign}(w^*\cdot x+b^*)$

支持向量

根據(jù)公式
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$
可以知道對 $w^*$ 的結(jié)果有影響的樣本點(diǎn) $(x_i,y_i)$ ，其 $\alpha_i^*\neq0$ ，又因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Calpha_i%5E*%5Cgeq0" alt="\alpha_i^*\geq0" mathimg="1">，所以 $\alpha_i^*\gt0$ ，根據(jù) $KKT$ 條件：
$\alpha_i^*g_i(w^*)=\alpha_i^*(1-y_i(w^*\cdot x_i+b^*))=0$
所以
$1-y_i(w^*\cdot x_i+b^*)=0$
這樣的樣本點(diǎn)落在間隔邊界上
$w^*\cdot x_i+b^*=\pm1$
與前面的描述相同。

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

統(tǒng)計(jì)機(jī)器學(xué)習(xí)-線性可分支持向量機(jī)與硬間隔最大化

統(tǒng)計(jì)機(jī)器學(xué)習(xí)-線性可分支持向量機(jī)與硬間隔最大化

問題

函數(shù)間隔和幾何間隔

函數(shù)間隔

幾何間隔

重新定義問題

線性可分支持向量機(jī)學(xué)習(xí)算法--最大間隔法

支持向量和間隔邊界

學(xué)習(xí)的對偶算法

定理

證明

線性可分支持向量機(jī)的對偶學(xué)習(xí)算法

支持向量

友情鏈接更多精彩內(nèi)容

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

統(tǒng)計(jì)機(jī)器學(xué)習(xí)-線性可分支持向量機(jī)與硬間隔最大化

問題

函數(shù)間隔和幾何間隔

函數(shù)間隔

幾何間隔

重新定義問題

線性可分支持向量機(jī)學(xué)習(xí)算法--最大間隔法

支持向量和間隔邊界

學(xué)習(xí)的對偶算法

定理

證明

線性可分支持向量機(jī)的對偶學(xué)習(xí)算法

支持向量

友情鏈接更多精彩內(nèi)容

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