公司网站开发详细流程,h5做的网站,房管局备案查询网站,吉安网页制作公司线性可分SVM摘记 0. 线性可分1. 训练样本到分类面的距离2. 函数间隔和几何间隔、(硬)间隔最大化3. 支持向量 \qquad 线性可分的支持向量机是一种二分类模型#xff0c;支持向量机通过核技巧可以成为非线性分类器。本文主要分析了线性可分的支持向量机模型#xff0c;主要取自… 线性可分SVM摘记 0. 线性可分1. 训练样本到分类面的距离2. 函数间隔和几何间隔、(硬)间隔最大化3. 支持向量 \qquad 线性可分的支持向量机是一种二分类模型支持向量机通过核技巧可以成为非线性分类器。本文主要分析了线性可分的支持向量机模型主要取自于李航《统计学习方法》第七章。 0. 线性可分 \qquad 如下图所示考虑训练数据“线性可分”的情况 \qquad \qquad 假设分类面 w T x b 0 \boldsymbol w^T\boldsymbol xb0 wTxb0 可以将两类数据完整分开任一训练样本 x \boldsymbol x x 的输出值目标值 y y y 满足 y sgn ( w T x b ) { 1 , w T x b 0 ( x ∈ ℓ 1 ) − 1 , w T x b 0 ( x ∈ ℓ 2 ) \qquad\qquad\qquad y\text{sgn}(\boldsymbol w^T\boldsymbol xb)\begin{cases}1,\quad\boldsymbol w^T\boldsymbol xb0\ (\boldsymbol x\in\ell_1)\\-1,\quad\boldsymbol w^T\boldsymbol xb0\ (\boldsymbol x\in\ell_2)\end{cases} ysgn(wTxb){1,wTxb0 (x∈ℓ1)−1,wTxb0 (x∈ℓ2) \qquad
1. 训练样本到分类面的距离 \qquad 任一样本 x \boldsymbol x x 到分类面的垂直距离为 r y ( w T x b ) ∥ w ∥ r\dfrac{y(\boldsymbol w^T\boldsymbol{x}b)}{\Vert\boldsymbol w\Vert} r∥w∥y(wTxb) ∙ \quad\bullet ∙ 正例 x i \boldsymbol x_i xi满足 w T x i b 0 , y i 1 \boldsymbol w^T\boldsymbol x_ib0,\ y_i1 wTxib0, yi1 \qquad\qquad \qquad 假设 x i \boldsymbol x_i xi 到分类面的距离为 r i r_i ri向量 x ˉ \bar{\boldsymbol x} xˉ 在分类面满足 w T x ˉ b 0 \boldsymbol{w}^T\bar{\boldsymbol{x}}b0 wTxˉb0显然 x i x ˉ r i w ∥ w ∥ \boldsymbol x_i\bar{\boldsymbol x}r_i\dfrac{\boldsymbol w}{\Vert\boldsymbol w\Vert} xixˉri∥w∥w \qquad 那么 w T x i b w T ( x ˉ r i w ∥ w ∥ ) b w T x ˉ b w T r i w ∥ w ∥ r i w T w ∥ w ∥ r i ∥ w ∥ \qquad\qquad\qquad\begin{aligned}\boldsymbol w^T\boldsymbol x_ib\boldsymbol w^T(\bar{\boldsymbol x}r_i\frac{\boldsymbol w}{\Vert\boldsymbol w\Vert})b\\ \boldsymbol w^T\bar{\boldsymbol x}b\boldsymbol w^Tr_i\frac{\boldsymbol w}{\Vert\boldsymbol w\Vert}\\ r_i\frac{\boldsymbol w^T\boldsymbol w}{\Vert\boldsymbol w\Vert}\\ r_i\Vert\boldsymbol w\Vert\end{aligned} wTxibwT(xˉri∥w∥w)bwTxˉbwTri∥w∥wri∥w∥wTwri∥w∥ \qquad 可得到正例 x i \boldsymbol x_i xi 到分类面的垂直距离 r i w T x i b ∥ w ∥ r_i\dfrac{\boldsymbol w^T\boldsymbol x_ib}{\Vert\boldsymbol w\Vert} ri∥w∥wTxib \qquad ∙ \quad\bullet ∙ 负例 x j \boldsymbol x_j xj满足 w T x j b 0 , y j − 1 \boldsymbol w^T\boldsymbol x_jb0,\ y_j-1 wTxjb0, yj−1 \qquad\qquad \qquad 假设 x j \boldsymbol x_j xj 到分类面的距离为 r j r_j rj向量 x ˉ \bar{\boldsymbol x} xˉ 在分类面满足 w T x ˉ b 0 \boldsymbol w^T\bar{\boldsymbol x}b0 wTxˉb0显然 x j x ˉ − r j w ∥ w ∥ \boldsymbol x_j\bar{\boldsymbol x}-r_j\dfrac{\boldsymbol w}{\Vert\boldsymbol w\Vert} xjxˉ−rj∥w∥w \qquad 那么 w T x j b w T ( x ˉ − r j w ∥ w ∥ ) b w T x ˉ b − w T r j w ∥ w ∥ − r j w T w ∥ w ∥ − r j ∥ w ∥ \qquad\qquad\qquad\begin{aligned}\boldsymbol w^T\boldsymbol x_jb\boldsymbol w^T(\bar{\boldsymbol x}-r_j\frac{\boldsymbol w}{\Vert\boldsymbol w\Vert})b\\ \boldsymbol w^T\bar{\boldsymbol x}b-\boldsymbol w^Tr_j\frac{\boldsymbol w}{\Vert\boldsymbol w\Vert}\\ -r_j\frac{\boldsymbol w^T\boldsymbol w}{\Vert\boldsymbol w\Vert}\\ -r_j\Vert\boldsymbol w\Vert\end{aligned} wTxjbwT(xˉ−rj∥w∥w)bwTxˉb−wTrj∥w∥w−rj∥w∥wTw−rj∥w∥ \qquad 可得到负例 x j \boldsymbol x_j xj 到分类面的垂直距离 r j − w T x j b ∥ w ∥ r_j-\dfrac{\boldsymbol w^T\boldsymbol x_jb}{\Vert\boldsymbol w\Vert} rj−∥w∥wTxjb \qquad
2. 函数间隔和几何间隔、(硬)间隔最大化 \qquad 由于任一训练样本 x i \boldsymbol x_i xi 的输出值 y y y 满足 y { 1 , w T x i b 0 ( ∀ x i ∈ ℓ 1 ) − 1 , w T x i b 0 ( ∀ x i ∈ ℓ 2 ) y\begin{cases}1,\quad\boldsymbol w^T\boldsymbol x_ib0\ \ (\forall\ \boldsymbol x_i\in\ell_1)\\-1,\quad\boldsymbol w^T\boldsymbol x_ib0\ \ (\forall\ \boldsymbol x_i\in\ell_2)\end{cases} y{1,wTxib0 (∀ xi∈ℓ1)−1,wTxib0 (∀ xi∈ℓ2)可定义两种间隔 ( margin ) (\text{margin}) (margin)来描述“训练样本 x i \boldsymbol x_i xi 到分类面的远近”。 \qquad ∙ \quad\bullet ∙ 函数间隔 ( functional margin ) (\text{functional margin}) (functional margin) γ ^ i y i ( w T x i b ) ∣ w T x i b ∣ \qquad\qquad\hat{\gamma}_iy_i(\boldsymbol w^T\boldsymbol x_ib)\vert\boldsymbol w^T\boldsymbol x_ib\vert γ^iyi(wTxib)∣wTxib∣ 函数间隔只能够相对地描述“训练样本 x i \boldsymbol x_i xi 到分类面的远近”。 例如 H 1 : w T x b 0 \mathcal H_1:\ \boldsymbol w^T\boldsymbol xb0 H1: wTxb0 与 H 2 : λ w T x λ b 0 \mathcal H_2:\ \lambda\boldsymbol w^T\boldsymbol x\lambda b0 H2: λwTxλb0 实际上是指同一个分类面假设 λ 0 \lambda0 λ0 对训练样本 x i \boldsymbol x_i xi 而言却有 { γ ^ 1 i ∣ w T x i b ∣ γ ^ 2 i λ ∣ w T x i b ∣ \begin{cases}\hat{\gamma}_{1i}\vert\boldsymbol w^T\boldsymbol x_ib\vert\\ \hat{\gamma}_{2i}\lambda\vert\boldsymbol w^T\boldsymbol x_ib\vert \end{cases} {γ^1i∣wTxib∣γ^2iλ∣wTxib∣函数间隔 γ ^ 2 i λ γ ^ 1 i \hat{\gamma}_{2i}\lambda\hat{\gamma}_{1i} γ^2iλγ^1i \qquad ∙ \quad\bullet ∙ 几何间隔 ( geometricl margin ) (\text{geometricl margin}) (geometricl margin) γ i y i r i y i ( w T x i b ) ∥ w ∥ ∣ w T x i b ∣ ∥ w ∥ \qquad\qquad \gamma_iy_ir_i\dfrac{y_i(\boldsymbol w^T\boldsymbol x_ib)}{\Vert\boldsymbol w\Vert}\dfrac{\vert\boldsymbol w^T\boldsymbol x_ib\vert}{\Vert\boldsymbol w\Vert} γiyiri∥w∥yi(wTxib)∥w∥∣wTxib∣ 几何间隔就是“训练样本 x i \boldsymbol x_i xi 到分类面的垂直距离”也就是“规范化的函数间隔”。 上例中 { γ 1 i γ ^ 1 i ∥ w ∥ ∣ w T x i b ∣ ∥ w ∥ γ 2 i γ ^ 2 i ∥ λ w ∥ λ ∣ w T x i b ∣ ∥ λ w ∥ ∣ w T x i b ∣ ∥ w ∥ \begin{cases}\gamma_{1i}\dfrac{\hat{\gamma}_{1i}}{\Vert\boldsymbol w\Vert}\dfrac{\vert\boldsymbol w^T\boldsymbol x_ib\vert}{\Vert\boldsymbol w\Vert} \\ \\\gamma_{2i}\dfrac{\hat{\gamma}_{2i}}{\Vert\lambda\boldsymbol w\Vert}\dfrac{\lambda\vert\boldsymbol w^T\boldsymbol x_ib\vert}{\Vert\lambda\boldsymbol w\Vert}\dfrac{\vert\boldsymbol w^T\boldsymbol x_ib\vert}{\Vert\boldsymbol w\Vert} \end{cases} ⎩ ⎨ ⎧γ1i∥w∥γ^1i∥w∥∣wTxib∣γ2i∥λw∥γ^2i∥λw∥λ∣wTxib∣∥w∥∣wTxib∣几何间隔 γ 1 i γ 2 i \gamma_{1i}\gamma_{2i} γ1iγ2i仍然相等。 \qquad 显然函数间隔和几何间隔之间的关系为 γ γ ^ ∥ w ∥ \qquad\qquad\textcolor{crimson}{\gamma\dfrac{\hat{\gamma}}{\Vert\boldsymbol w\Vert}} γ∥w∥γ^ \qquad ∙ \quad\bullet ∙ 以最大化训练样本的几何间隔为目标函数并定义约束最优化问题 \qquad 约束最优化问题1 max w , b γ s . t . y i ( w T x i b ) ∥ w ∥ ≥ γ , ∀ x i \qquad\qquad\qquad\textcolor{indigo}{\begin{aligned}\max_{\boldsymbol w,b}\ \gamma\\ \ s.t.\ \ \ \dfrac{y_i(\boldsymbol w^T\boldsymbol x_ib)}{\Vert\boldsymbol w\Vert}\ge \gamma,\quad \forall\ \boldsymbol x_i\end{aligned}} w,bmax γ s.t. ∥w∥yi(wTxib)≥γ,∀ xi 也就是在确保所有训练样本到分类面的垂直距离都大于 γ \gamma γ 的前提下尽可能让几何间隔最大。 \qquad 利用两种间隔之间的关系 γ γ ^ ∥ w ∥ \gamma\dfrac{\hat{\gamma}}{\Vert\boldsymbol w\Vert} γ∥w∥γ^在约束最优化问题1中使用函数间隔 γ ^ \hat{\gamma} γ^ 来描述几何间隔 γ \gamma γ也就是 \qquad 约束最优化问题2 max w , b γ ^ ∥ w ∥ s . t . y i ( w T x i b ) ≥ γ ^ , ∀ x i \qquad\qquad\qquad\textcolor{indigo}{\begin{aligned}\max_{\boldsymbol w,b}\ \dfrac{\hat{\gamma}}{\Vert\boldsymbol w\Vert}\\ \ s.t.\ \ \ y_i(\boldsymbol w^T\boldsymbol x_ib) \ge \hat{\gamma},\quad \forall\ \boldsymbol x_i\end{aligned}} w,bmax ∥w∥γ^ s.t. yi(wTxib)≥γ^,∀ xi \qquad \qquad 考虑满足约束最优化问题2的同一个分类面的两种表示 H 1 : ( w , b ) \mathcal H_1:(\boldsymbol w,b) H1:(w,b) 和 H 2 : ( λ w , λ b ) \mathcal H_2:(\lambda\boldsymbol w,\lambda b) H2:(λw,λb)对于任一训练样本 x i \boldsymbol x_i xi 而言 λ 0 \lambda0 λ0那么 \qquad ① H 1 : w T x b 0 \quad\textcolor{firebrick}{\mathcal H_1}:\ \boldsymbol w^T\boldsymbol xb0 H1: wTxb0 函数间隔为 γ ^ ∣ w T x i b ∣ \hat\gamma\vert\boldsymbol w^T\boldsymbol x_ib\vert γ^∣wTxib∣ ⟹ { 目标函数值 γ ^ ∥ w ∥ 约束函数 y i ( w T x i b ) ≥ γ ^ , ∀ x i \qquad\qquad\quad\Longrightarrow\quad\begin{cases}目标函数值\quad\dfrac{\hat\gamma}{\Vert\boldsymbol w\Vert}\\ 约束函数 \quad y_i(\boldsymbol w^T\boldsymbol x_ib) \ge \hat\gamma,\quad \forall\ \boldsymbol x_i\end{cases} ⟹⎩ ⎨ ⎧目标函数值∥w∥γ^约束函数 yi(wTxib)≥γ^,∀ xi \qquad ② H 2 : λ w T x λ b 0 \quad\textcolor{firebrick}{\mathcal H_2}:\ \lambda\boldsymbol w^T\boldsymbol x\lambda b0 H2: λwTxλb0 函数间隔为 λ γ ^ \lambda\hat\gamma λγ^ ⟹ { 目标函数值 λ γ ^ ∥ λ w ∥ 约束函数 y i λ ( w T x i b ) ≥ λ γ ^ , ∀ x i \qquad\qquad\quad\Longrightarrow\quad\begin{cases}目标函数值\quad\dfrac{\lambda\hat\gamma}{\Vert\lambda\boldsymbol w\Vert}\\ 约束函数 \quad y_i\lambda(\boldsymbol w^T\boldsymbol x_ib) \ge \lambda\hat\gamma,\quad \forall\ \boldsymbol x_i\end{cases} ⟹⎩ ⎨ ⎧目标函数值∥λw∥λγ^约束函数 yiλ(wTxib)≥λγ^,∀ xi \qquad \qquad 显然权值 ( w , b ) (\boldsymbol w,b) (w,b) 与其同比例的缩放值 ( λ w , λ b ) (\lambda\boldsymbol w,\lambda b) (λw,λb) 对于约束最优化问题2而言是没有影响的。 \qquad ∙ \quad\bullet ∙ 构造凸二次规划问题 \qquad 在约束最优化问题2中可以简单地取函数间隔 γ ^ 1 \hat\gamma1 γ^1。 假设待求解的权值为 ( w , b ) (\boldsymbol w,b) (w,b) 样本 x \boldsymbol x x 到 w T x b 0 \boldsymbol w^T\boldsymbol xb0 wTxb0 的几何间隔为 γ ^ ∥ w ∥ \dfrac{\hat\gamma}{\Vert\boldsymbol w\Vert} ∥w∥γ^ 函数间隔 γ ^ 1 \hat\gamma1 γ^1 时的几何间隔写为 1 ∥ λ ′ w ∥ \dfrac{1}{\Vert\lambda^{\prime}\boldsymbol w\Vert} ∥λ′w∥1也就是 ( w , b ) (\boldsymbol w,b) (w,b) 缩放为了 ( λ ′ w , λ ′ b ) , λ ′ 1 / γ (\lambda^{\prime}\boldsymbol w,\lambda^{\prime}b),\ \lambda^{\prime}1/\gamma (λ′w,λ′b), λ′1/γ 而 w T x b 0 \boldsymbol w^T\boldsymbol xb0 wTxb0 和 λ ′ w T x λ ′ b 0 \lambda^{\prime}\boldsymbol w^T\boldsymbol x\lambda^{\prime}b0 λ′wTxλ′b0 是同一个分类面 \qquad 那么约束最优化问题2就可以写为 max w , b γ ^ ∥ w ∥ s . t . y i ( w T x i b ) ≥ γ ^ , ∀ x i ⟹ γ ^ 1 max w , b 1 ∥ w ∥ s . t . y i ( w T x i b ) ≥ 1 , ∀ x i \qquad\qquad\textcolor{darkblue}{\begin{aligned}\max_{\boldsymbol w,b}\ \dfrac{\hat\gamma}{\Vert\boldsymbol w\Vert}\\ \ s.t.\ \ \ y_i(\boldsymbol w^T\boldsymbol x_ib) \ge \hat\gamma,\ \forall\ \boldsymbol x_i\end{aligned}}\quad\overset{\hat\gamma1}\Longrightarrow\qquad\textcolor{royalblue}{\begin{aligned}\max_{\boldsymbol w,b}\ \dfrac{1}{\Vert\boldsymbol w\Vert}\\ \ s.t.\ \ \ y_i(\boldsymbol w^T\boldsymbol x_ib) \ge 1,\ \forall\ \boldsymbol x_i\end{aligned}} w,bmax ∥w∥γ^ s.t. yi(wTxib)≥γ^, ∀ xi⟹γ^1w,bmax ∥w∥1 s.t. yi(wTxib)≥1, ∀ xi \qquad \qquad 又由于 max 1 ∥ w ∥ ⟺ min 1 2 ∥ w ∥ 2 \max\ \dfrac{1}{\Vert\boldsymbol w\Vert}\Longleftrightarrow\min\ \dfrac{1}{2}\Vert\boldsymbol w\Vert^2 max ∥w∥1⟺min 21∥w∥2因此可以构造出一个凸二次规划问题 \qquad 约束最优化问题3 min w , b 1 2 ∥ w ∥ 2 s . t . y i ( w T x i b ) ≥ 1 , ∀ x i \qquad\qquad\qquad\textcolor{indigo}{\begin{aligned}\min_{\boldsymbol w,b}\ \dfrac{1}{2}\Vert\boldsymbol w\Vert^2\\ \ s.t.\ \ \ y_i(\boldsymbol w^T\boldsymbol x_ib) \ge 1,\quad \forall\ \boldsymbol x_i\end{aligned}} w,bmin 21∥w∥2 s.t. yi(wTxib)≥1,∀ xi \qquad
3. 支持向量 \qquad 支持向量 ( support vector ) (\text{support\ vector}) (support vector) 是指距离分类面最近的训练样本红色 点两个红色点线超平面 w T x b 1 \boldsymbol w^T\boldsymbol xb1 wTxb1 和 w T x b − 1 \boldsymbol w^T\boldsymbol xb-1 wTxb−1 之间的距离称为间隔 ( margin ) (\text{margin}) (margin)。 \qquad \qquad 考察该凸二次规划最优化问题 min w , b 1 2 ∥ w ∥ 2 s . t . y i ( w T x i b ) ≥ 1 , ∀ x i \qquad\qquad\qquad\begin{aligned}\min_{\boldsymbol w,b}\ \dfrac{1}{2}\Vert\boldsymbol w\Vert^2\\ \ s.t.\ \ \ y_i(\boldsymbol w^T\boldsymbol x_ib) \ge 1,\quad \forall\ \boldsymbol x_i\end{aligned} w,bmin 21∥w∥2 s.t. yi(wTxib)≥1,∀ xi \qquad 支持向量也是使得约束条件的等式成立的点即 y ( w T x b ) 1 y(\boldsymbol w^T\boldsymbol xb)1 y(wTxb)1。在线性可分的情况下选择不同的点作为支持向量就可以确定不同的分离超平面 w T x b 0 \boldsymbol w^T\boldsymbol xb0 wTxb0。 正例的支持向量 x i , y i 1 : y i ( w T x i b ) 1 ⇒ H 1 : w T x i b 1 \boldsymbol x_i,y_i1:\ y_i(\boldsymbol w^T\boldsymbol x_ib)1 \qquad\Rightarrow\quad H_1:\boldsymbol w^T\boldsymbol x_ib1 xi,yi1: yi(wTxib)1⇒H1:wTxib1 其余的 正例的训练样本满足 w T x i b 1 \boldsymbol w^T\boldsymbol x_ib1 wTxib1负例的支持向量 x j , y j − 1 : y j ( w T x j b ) 1 ⇒ H 2 : w T x j b − 1 \boldsymbol x_j,y_j-1:y_j(\boldsymbol w^T\boldsymbol x_jb)1 \qquad\Rightarrow\quad H_2:\boldsymbol w^T\boldsymbol x_jb-1 xj,yj−1:yj(wTxjb)1⇒H2:wTxjb−1 其余的 负例的训练样本满足 w T x i b − 1 \boldsymbol w^T\boldsymbol x_ib-1 wTxib−1两个超平面 H 1 H_1 H1 与 H 2 H_2 H2 之间的间隔为 2 ∥ w ∥ \dfrac{2}{\Vert\boldsymbol w\Vert} ∥w∥2 \qquad \qquad 【写在最后】SVM的资料太多了越写越觉得没什么特别的内容值得去写。攒在草稿箱里太久发出来就当留个记录吧。
