6. 支持向量機(jī)

6.1. 間隔與支持向量

分類學(xué)習(xí)最基本的想法就是基于訓(xùn)練集 $D$ 在樣本空間中找到一個(gè)劃分超平面，將不同類別的樣本分開。

支持向量機(jī)找到的劃分超平面所產(chǎn)生的分類結(jié)果是最魯棒的，對(duì)未見示例的泛化能力最強(qiáng).

超平面

$n$ 維空間的超平面定義：
$\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b=0$

超平面方程不唯一；
法向量 $\omega$ 和位移項(xiàng) $b$ 確定唯一的超平面；
法向量 $\omega$ 為法向量，垂直于超平面，決定了平面方向， $b$ 為位移項(xiàng)，確定超平面與原點(diǎn)之間的距離；
法向量 $\omega$ 指向的一半空間為正空間（代入定義方程是 > 0 的），另一半為負(fù)空間（代入定義方程是 < 0 的）；
任意點(diǎn)到超平面的距離為：
$r=\frac{\left|\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b\right|}{\|\boldsymbol{w}\|}$

幾何間隔

數(shù)據(jù)集的幾何間隔：數(shù)據(jù)集中所有樣本點(diǎn)的幾何間隔的最小值。

支持向量機(jī)

給定線性可分?jǐn)?shù)據(jù)集 $X$ ，支持向量機(jī)希望求得數(shù)據(jù)集 $X$ 關(guān)于超平面的幾何間隔 $\gamma$ 達(dá)到最大的那個(gè)超平面，再加上階躍函數(shù)實(shí)現(xiàn)分類功能。
$y=\operatorname{sign}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b\right)=\left\{\begin{array}{rr} 1, & \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b>0 \\ -1, & \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b<0 \end{array}\right.$

當(dāng)超平面未正確劃分樣本時(shí)，幾何間隔最小的為誤分類點(diǎn)， $\gamma < 0$ ；
當(dāng)超平面正確劃分時(shí)， $\gamma \geq 0$ ，且越靠近中央位置， $\gamma$ 越大，進(jìn)而達(dá)到幾何間隔最大。

給定線性可分?jǐn)?shù)據(jù)集 $X$ ，設(shè) $X$ 中幾何間隔最小的樣本為 $(x_{min},y_{min})$ ，則支持向量機(jī)尋找超平面的過程，可轉(zhuǎn)換為帶約束的優(yōu)化問題。

做出一定的限制，使得該優(yōu)化問題有可解的唯一解，在 SVM 中，通常令幾何間隔為 1.

為方便計(jì)算，將最大化問題轉(zhuǎn)化為最小化問題。

6.2. 對(duì)偶問題

支持向量機(jī)是約束優(yōu)化問題。

拉格朗日對(duì)偶的基礎(chǔ)知識(shí)

對(duì)一般的約束優(yōu)化問題，有 $m$ 個(gè)不等式約束，有 $n$ 個(gè)等式約束。
$\begin{array}{ll} \min & f(\boldsymbol{x}) \\ \text { s.t. } & g_{i}(\boldsymbol{x}) \leqslant 0 \quad i=1,2, \ldots, m \\ & h_{j}(\boldsymbol{x})=0 \quad j=1,2, \ldots, n \end{array}$
定義域?yàn)椋?img class="math-inline" src="https://math.jianshu.com/math?formula=D%3D%5Coperatorname%7Bdom%7D%20f%20%5Ccap%20%5Cbigcap_%7Bi%3D1%7D%5E%7Bm%7D%20%5Coperatorname%7Bdom%7D%20g_%7Bi%7D%20%5Ccap%20%5Cbigcap_%7Bj%3D1%7D%5E%7Bn%7D%20%5Coperatorname%7Bdom%7D%20h_%7Bj%7D" alt="D=\operatorname{dom} f \cap \bigcap_{i=1}^{m} \operatorname{dom} g_{i} \cap \bigcap_{j=1}^{n} \operatorname{dom} h_{j}" mathimg="1">
可行集為： $\tilde{D}=\left\{\boldsymbol{x} \mid \boldsymbol{x} \in D, g_{i}(\boldsymbol{x}) \leqslant 0, h_{j}(\boldsymbol{x})=0\right\}$ ，可行集是定義域的子集
最優(yōu)值為： $p^{*} = \min \{f(\tilde{\boldsymbol{x}})\}$

根據(jù)拉格朗日函數(shù)的定義，優(yōu)化問題的拉格朗日函數(shù)為：
$L(\boldsymbol{x}, \boldsymbol{\mu}, \boldsymbol{\lambda})=f(\boldsymbol{x})+\sum_{i=1}^{m} \mu_{i} g_{i}(\boldsymbol{x})+\sum_{j=1}^{n} \lambda_{j} h_{j}(\boldsymbol{x})$
其中， $\boldsymbol{\mu}=\left(\mu_{1}, \mu_{2}, \ldots, \mu_{m}\right)^{T}, \boldsymbol{\lambda}=\left(\lambda_{1}, \lambda_{2}, \ldots, \lambda_{n}\right)^{T}$ 為拉格朗日乘子向量。

定義拉格朗日對(duì)偶函數(shù)，是關(guān)于拉格朗日乘子 $\mu$ 和 $\lambda$ 的函數(shù)，與 $x$ 無關(guān)。
拉格朗日對(duì)偶函數(shù) $\Gamma(\boldsymbol{\mu}, \boldsymbol{\lambda})$ 是拉格朗日函數(shù) $L(\boldsymbol{x}, \boldsymbol{\mu}, \boldsymbol{\lambda})$ 關(guān)于 $x$ 的下確界。
$\Gamma(\boldsymbol{\mu}, \boldsymbol{\lambda})=\inf _{\boldsymbol{x} \in D} L(\boldsymbol{x}, \boldsymbol{\mu}, \boldsymbol{\lambda})=\inf _{\boldsymbol{x} \in D}\left(f(\boldsymbol{x})+\sum_{i=1}^{m} \mu_{i} g_{i}(\boldsymbol{x})+\sum_{j=1}^{n} \lambda_{j} h_{j}(\boldsymbol{x})\right)$

不管優(yōu)化問題是否是凸優(yōu)化問題，其對(duì)偶函數(shù)恒為凹問題。
當(dāng)不等式拉格朗日乘子 $\mu \geq 0$ 時(shí)， $\Gamma(\boldsymbol{\mu}, \boldsymbol{\lambda})$ 構(gòu)成了上述優(yōu)化問題最優(yōu)值 $p^{*}$ 的下界。
$\Gamma(\boldsymbol{\mu}, \boldsymbol{\lambda}) \leq p^{*}$

將上述約束優(yōu)化問題轉(zhuǎn)換為對(duì)偶問題
$\begin{array}{ll} \max \ \Gamma(\boldsymbol{\mu}, \boldsymbol{\lambda}) \\ \text { s.t. } \quad \boldsymbol{\mu} \succeq 0 \end{array}$
主問題不好求解時(shí)，使用對(duì)偶問題來求解。
設(shè)該優(yōu)化問題的最優(yōu)值為 $d^{*}$ ，顯然 $d^{*} \leq p^{*}$ ，稱為“弱對(duì)偶性”成立，若 $d^{*} = p^{*}$ ，稱為”強(qiáng)對(duì)偶性”成立，此時(shí)找到了求 $p^{*}$ 的方法。

KKT 條件

支持向量機(jī)的主問題和對(duì)偶問題

6.3. 核函數(shù)

將樣本從原始空間映射到一個(gè)更高維的特征空間，使得樣本在這個(gè)特征空間內(nèi)線性可分.

如果原始空間是有限維，即屬性數(shù)有限，那么一定存在一個(gè)高維特征空間使樣本可分。

令 $\phi(x)$ 是 $x$ 映射后的特征向量，在特征空間中劃分超平面所對(duì)應(yīng)的模型為：
$f(\boldsymbol{x})=\boldsymbol{w}^{\mathrm{T}} \phi(\boldsymbol{x})+b$
給出對(duì)應(yīng)的優(yōu)化問題：
$\begin{aligned} \min _{\boldsymbol{w}, b} & \frac{1}{2}\|\boldsymbol{w}\|^{2} \\ \text { s.t. } & y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \phi\left(\boldsymbol{x}_{i}\right)+b\right) \geqslant 1, \quad i=1,2, \ldots, m . \end{aligned}$
及對(duì)應(yīng)的對(duì)偶問題：
$\max_{\alpha} \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \phi\left(\boldsymbol{x}_{i}\right)^{\mathrm{T}} \phi\left(\boldsymbol{x}_{j}\right) \text{ } s.t. \sum_{i=1}^{m} \alpha_{i} y_{i}=0,\alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m .$

設(shè)計(jì)到計(jì)算 $\phi\left(\boldsymbol{x}_{i}\right)^{\mathrm{T}} \phi\left(\boldsymbol{x}_{j}\right)$ ，這是兩個(gè)樣本映射到特征空間之后的內(nèi)積，特征空間的維數(shù)可能很高。

設(shè)想一個(gè)函數(shù)，有 $\kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\left\langle\phi\left(\boldsymbol{x}_{i}\right), \phi\left(\boldsymbol{x}_{j}\right)\right\rangle=\phi\left(\boldsymbol{x}_{i}\right)^{\mathrm{T}} \phi\left(\boldsymbol{x}_{j}\right)$ ，即 $x_{i}$ 與 $x_{j}$ 在特征空間的內(nèi)積等于它們?cè)谠紭颖究臻g中通過函數(shù) $\kappa\left (\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)$ 計(jì)算結(jié)果。推導(dǎo)后，有，
$f(x)=\sum_{i=1}^{m} \alpha_{i} y_{i} \kappa\left(\boldsymbol{x}, \boldsymbol{x}_{i}\right)+b$
函數(shù) $\kappa\left (\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)$ 為核函數(shù)。

什么樣的函數(shù)可以做核函數(shù)？

常用核函數(shù)

還可以通過組合得到，

線性組合
$\gamma_{1} \kappa_{1}+\gamma_{2} \kappa_{2}$
直積
$\kappa_{1} \otimes \kappa_{2}(\boldsymbol{x}, \boldsymbol{z})=\kappa_{1}(\boldsymbol{x}, \boldsymbol{z}) \kappa_{2}(\boldsymbol{x}, \boldsymbol{z})$
對(duì)任意函數(shù)的運(yùn)算
$\kappa(\boldsymbol{x}, \boldsymbol{z})=g(\boldsymbol{x}) \kappa_{1}(\boldsymbol{x}, \boldsymbol{z}) g(\boldsymbol{z})$

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

吃瓜教程_Task_5_西瓜書+南瓜書_Chapter6

吃瓜教程_Task_5_西瓜書+南瓜書_Chapter6

6. 支持向量機(jī)

6.1. 間隔與支持向量

超平面