假設(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ù)集不是線性可分的枝恋。通常情況是创倔，訓(xùn)練數(shù)據(jù)中有一些特異點(diǎn)，將這些特異點(diǎn)除去后焚碌，剩下大部分的樣本點(diǎn)組成的集合是線性可分的畦攘。

線性不可分意味著某些樣本點(diǎn) $(x_i,y_i)$ 不能滿足函數(shù)間隔大于等于1的約束條件。為了解決這個(gè)問題十电，可以對每個(gè)樣本點(diǎn) $(x_i,y_i)$ 引進(jìn)一個(gè)松弛變量 $\xi_i\geq0$ 知押，使函數(shù)間隔加上松弛變量大于等于1。這樣鹃骂，約束條件變?yōu)?br> $1-\xi_i-y_i(w\cdot x_i+b)\leq0$
目標(biāo)函數(shù)由原來的最小化 $\frac12||w||^2$ 變成最小化
$\frac12||w||^2+C\sum_{i=1}^N\xi_i$
$C$ 是對誤分類的懲罰台盯， $C$ 越大，對誤分類懲罰越大畏线。相對于線性可分支持向量機(jī)的硬間隔最大化静盅，這叫做軟間隔最大化。

于是線性不可分支持向量機(jī)的學(xué)習(xí)的原始問題為凸二次規(guī)劃問題：
$\min_{w,b,\xi}\frac12||w||^2+C\sum_{i=1}^N\xi_i\tag1$

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

$-\xi_i\leq0,\ \ i=1,2,\cdots,N\tag3$

可以證明 $w$ 的解是唯一的寝殴，但 $b$ 的解可能不唯一蒿叠，而是存在于一個(gè)區(qū)間。證明略杯矩。

假如 $w^*$ 栈虚， $b^*$ 是最優(yōu)化問題(1)-(3)的解，則得到的超平面為
$w^*\cdot x+b^*=0\tag4$
分類決策函數(shù)為
$f(x)=\mathrm{sign}(w^*\cdot x+b^*)\tag5$
稱為線性支持向量機(jī)史隆。

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

由原始問題(1)-(3)魂务，首先構(gòu)建拉格朗日函數(shù)
$L(w,b,\xi,\alpha,\mu)=\frac12||w||^2+C\sum_{i=1}^N\xi_i+\sum_{i=1}^N\alpha_i(1-\xi_i-y_i(w\cdot x_i+b))-\sum_{i=1}^N\mu_i\xi_i\tag6$
其中 $\alpha_i\geq0$ ， $\mu_i\geq0$ 泌射，于是原始問題可以寫成
$\min_{w,b,\xi}\max_{\alpha,\mu}L(w,b,\xi,\alpha,\mu)$
則對偶問題為
$\max_{\alpha,\mu}\min_{w,b,\xi}L(w,b,\xi,\alpha,\mu)$
首先求解內(nèi)部極小化問題粘姜，求 $L(w,b,\xi,\alpha,\mu)$ 對 $w$ ， $b$ 熔酷， $\xi$ 的偏導(dǎo)并使其等于0：
$\nabla_wL(w,b,\xi,\alpha,\mu)=w-\sum_{i=1}^N\alpha_iy_ix_i=0$

$\nabla_bL(w,b,\xi,\alpha,\mu)=-\sum_{i=1}^N\alpha_iy_i=0$

$\nabla_{\xi_i}=C-\alpha_i-\mu_i=0$

得
$w=\sum_{i=1}^N\alpha_iy_ix_i\tag7$

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

$C-\alpha_i-\mu_i=0\tag9$

將公式(7)-(9)代入(6)得到
$L(w,b,\xi,\alpha,\mu)=-\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$
于是原始的問題(1)-(3)的對偶問題可以寫成
$\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{10}$

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

$C-\alpha_i-\mu_i=0\tag{12}$

$\alpha_i\geq0\tag{13}$

$\mu_i\geq0,\ \ i=1,2,\cdots,N\tag{14}$

對其進(jìn)一步改寫孤紧，由公式(12)得
$\mu_i=C-\alpha_i$
代入公式(14)得
$\alpha_i\leq C$
所以公式(12)-(14)可以簡寫為
$0\leq\alpha_i\leq C,\ \ i=1,2,\cdots,N$
再對目標(biāo)函數(shù)取相反數(shù)染突，得到對偶問題
$\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\tag{16}$

$0\leq\alpha_i\leq C,\ \ i=1,2,\cdots,N\tag{17}$

定理

設(shè) $\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)$ 是對偶問題(15)-(17)的一個(gè)解知给，若存在 $\alpha^*$ 的一個(gè)分量 $\alpha_j^*$ 双霍， $0\lt\alpha_j^*\lt C$ 鹦倚，則原始問題(1)-(3)的解 $w^*$ , $b^*$ 可按下式得到：
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i\tag{18}$

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

證明略。

于是分離超平面可以寫成
$\sum_{i=1}^N\alpha_i^*y_i(x\cdot x_i)+b^*=0$
分類決策函數(shù)
$f(x)=\mathrm{sign}\bigg(\sum_{i=1}^N\alpha_i^*y(x\cdot x_i)+b^*\bigg)$

線性支持向量機(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）選擇懲罰參數(shù) $C\gt0$ 雳刺，構(gòu)造并求解凸二次規(guī)劃問題
$\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$

$0\leq\alpha_i\leq C,\ \ i=1,2,\cdots,N$

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

（2）計(jì)算 $w^*=\sum_{i=1}^N\alpha_iy_ix_i$

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

支持向量

由公式
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$
得知 $\alpha_i^*\neq0$ 的樣本點(diǎn) $x_i$ 能夠影響支持向量機(jī)的參數(shù)掖桦。而 $0\leq\alpha_i^*\leq C$ 本昏，所以支持向量為 $0\lt\alpha_i^*\leq C$ 的樣本點(diǎn) $x_i$ 。這些支持向量分布在間隔邊界上滞详、間隔邊界與分離超平面之間或者在分離超平面誤分一側(cè)凛俱。若 $\alpha_i^*\lt C$ ，則 $\xi_i=0$ （由 $KKT$ 條件可以推出料饥，由于 $\xi^*$ 的結(jié)果不影響分離超平面蒲犬，所以一般也不去算，其計(jì)算過程略）岸啡，支持向量恰好落在間隔邊界上原叮；若 $\alpha_i^*=C$ ， $0\lt\xi_i\lt1$ 巡蘸，則分類正確奋隶，支持向量在間隔邊界與分離超平面之間；若 $\alpha_i^*=C$ 悦荒， $\xi_i=1$ 唯欣，則 $x_i$ 在分離超平面上；若 $\alpha_i^*=C$ 搬味， $\xi_i\gt1$ 境氢，則 $x_i$ 在分離超平面誤分一側(cè)。

合頁損失函數(shù)

線性支持向量機(jī)的學(xué)習(xí)還等價(jià)于最小化以下目標(biāo)函數(shù)：
$\min_{w,b}\sum_{i=1}^N[1-y_i(w\cdot x_i+b)]_++\lambda||w||^2\tag{20}$
證明過程略碰纬。其中目標(biāo)函數(shù)的第一項(xiàng)是經(jīng)驗(yàn)損失或經(jīng)驗(yàn)風(fēng)險(xiǎn)萍聊，第二項(xiàng)是正則化項(xiàng)。函數(shù)
$L(y(w\cdot x+b))=[1-y(w\cdot x+b)]_+$
稱為合頁損失函數(shù)悦析。下標(biāo)"+"表示 $ReLU$ 函數(shù)寿桨，由于函數(shù)形狀像一個(gè)合頁，故名合頁損失函數(shù)强戴。合頁損失函數(shù)相比感知機(jī)的0-1損失亭螟，不僅要求分類正確挡鞍，還要求確信度足夠高時(shí)（函數(shù)間隔大于等于1）損失才是0，所以支持向量機(jī)的學(xué)習(xí)比感知機(jī)有更高的要求媒佣。

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

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

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

定理

線性支持向量機(jī)學(xué)習(xí)算法

支持向量

合頁損失函數(shù)