手机网站建站公司有哪些,十九冶成都建设网站,中企动力服务怎么样,电商推广绩效5. 支持向量机(线性SVM) 文章目录 5.4 非线性可分SVM5.4.1 非线性可分问题处理思路核技巧核函数特点 核函数作用于SVM 5.4.2 正定核函数由 K ( x , z ) K(x,z) K(x,z) 构造 H \mathcal{H} H 空间步骤 常用核函数 5.5 SVM参数求解算法5.6 SVM与线性模型关系 5.4 非线性可分SVM …5. 支持向量机(线性SVM) 文章目录 5.4 非线性可分SVM5.4.1 非线性可分问题处理思路核技巧核函数特点 核函数作用于SVM 5.4.2 正定核函数由 K ( x , z ) K(x,z) K(x,z) 构造 H \mathcal{H} H 空间步骤 常用核函数 5.5 SVM参数求解算法5.6 SVM与线性模型关系 5.4 非线性可分SVM
5.4.1 非线性可分问题
原始空间不存在能够正确划分的超平面 在二维平面直角坐标系中如果按照与原点之间的距离对数据点进行分类的话分类模型就成为一个圆也就是超平面
处理思路 如果能将样本从原始空间映射到高维特征空间上在新的特征空间是上样本就可能是线性可分的
若样本的属性数优先则一定存在一个高维特征空间使样本可分
核技巧
通过一个非线性映射将原始低维空间上的非线性问题转化为新的高维空间上的线性问题这就是核技巧的基本思想。
使在原始空间 R n R^n Rn 中的超平面模型映射为特征空间的超平面模型
在学习和预测中只定义核函数而不显式定义映射函数利用线性分类方法与核函数解决非线性问题
核函数
假设原始空间是 低维欧几里得空间 X \mathcal{X} X 新空间为 **高维希尔伯特空间 H \mathcal{H} H ** 从 X \mathcal{X} X 到 H \mathcal{H} H 的映射可以用函数 ϕ ( x ) : X → H \phi(x):\mathcal{X}\rightarrow \mathcal{H} ϕ(x):X→H 表示。核函数可以表示为映射函数内积形式 K ( x , z ) ϕ ( x ) ⋅ ϕ ( z ) K(x,z)\phi(x)\cdot\phi(z) K(x,z)ϕ(x)⋅ϕ(z)
eg
原空间 X \mathcal{X} X 中的两个点进行内积运算 ( x i , x j ) (x_i,x_j) (xi,xj) 若先进行映射再在 H \mathcal{H} H 中内积运算则有 z i ϕ ( x i ) , z j ϕ ( x j ) , 则 ( z i , z j ) ϕ ( x i ) ⋅ ϕ ( x j ) z_i\phi(x_i),z_j\phi(x_j),则(z_i,z_j)\phi(x_i)\cdot \phi(x_j) ziϕ(xi),zjϕ(xj),则(zi,zj)ϕ(xi)⋅ϕ(xj) 若使用核函数则可直接计算 K ( x i , x j ) K(x_i,x_j) K(xi,xj)
特点
对于确定的核函数 计算过程在低维空间上完成避免了高维空间中的复杂计算 对于给定核函数高维空间 H \mathcal{H} H 和映射函数 ϕ \phi ϕ 的取法不唯一 可映射到不同的特征空间 z i z_i zi 维度可以不同和 可通过不同映射函数映射到同一特征空间
核函数作用于SVM
输入线性不可分的数据 D { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯ , ( x N , y N ) } ∈ X ∈ R n , y i ∈ Y ∈ { 1 , − 1 } , i 1 , ⋯ , N D\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}\in \mathcal{X}\in R^n,y_i\in \mathcal{Y}\in \{1,-1\},i1,\cdots,N D{(x1,y1),(x2,y2),⋯,(xN,yN)}∈X∈Rn,yi∈Y∈{1,−1},i1,⋯,N 输出分离超平面和决策函数
算法
1. 选择合适的参数 C C C 和核函数 K ( x , z ) K(x,z) K(x,z) 构造最优化问题
线性SVM { min α 1 2 ∑ i 1 N ∑ j 1 N α i α j y i y j x i ⋅ x j − ∑ i 1 N α i s . t . 0 ≤ α i ≤ 0 ∑ i 1 N α i y i 0 \begin{cases} \min\limits_{\alpha}\frac{1}{2}\sum\limits_{i1}^N\sum\limits_{j1}^N\alpha_i\alpha_jy_iy_jx_i\cdot x_j-\sum\limits_{i1}^N\alpha_i\\ s.t. \quad 0\le \alpha_i\le 0\\ \qquad \sum\limits_{i1}^N\alpha_iy_i0\\ \end{cases} ⎩ ⎨ ⎧αmin21i1∑Nj1∑Nαiαjyiyjxi⋅xj−i1∑Nαis.t.0≤αi≤0i1∑Nαiyi0 对于 ( x i , x j ) (x_i,x_j) (xi,xj) 可以通过核技巧映射到线性可分空间 ϕ ( x i ) ⋅ ϕ ( x j ) z i ⋅ z j K ( x i , x j ) \phi(x_i)\cdot \phi(x_j)z_i\cdot z_jK(x_i,x_j) ϕ(xi)⋅ϕ(xj)zi⋅zjK(xi,xj) 在 H \mathcal{H} H 空间中的SVM问题为 { min α 1 2 ∑ i 1 N ∑ j 1 N α i α j y i y j K ( x i , x j ) − ∑ i 1 N α i s . t . 0 ≤ α i ≤ 0 ∑ i 1 N α i y i 0 \begin{cases} \min\limits_{\alpha}\frac{1}{2}\sum\limits_{i1}^N\sum\limits_{j1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum\limits_{i1}^N\alpha_i\\ s.t. \quad 0\le \alpha_i\le 0\\ \qquad \sum\limits_{i1}^N\alpha_iy_i0\\ \end{cases} ⎩ ⎨ ⎧αmin21i1∑Nj1∑NαiαjyiyjK(xi,xj)−i1∑Nαis.t.0≤αi≤0i1∑Nαiyi0 求得最优解 α ∗ ( α 1 ∗ , α 2 ∗ , ⋯ , α N ∗ ) \alpha^*(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*) α∗(α1∗,α2∗,⋯,αN∗)
2. 选一个 0 α j ∗ C 0\alpha_j^*C 0αj∗C 的分量对应的样本点 ( x j , y j ) (x_j,y_j) (xj,yj) ——支持向量计算模型参数 ω ∗ , b ∗ \omega^*,b^* ω∗,b∗
有 ω ∗ ∑ i 1 N α i ∗ y i K ( ⋅ , x i ) \omega^*\sum\limits_{i1}^N\alpha_i^*y_i K(\cdot,x_i) ω∗i1∑Nαi∗yiK(⋅,xi) b ∗ y j − ∑ i 1 N α i ∗ y i K ( x i , x j ) b^*y_j-\sum\limits_{i1}^N\alpha_i^*y_iK(x_i,x_j) b∗yj−i1∑Nαi∗yiK(xi,xj)
模型 { ∑ i 1 N α i ∗ y i K ( x i , x ) ( y j − ∑ i 1 N α i ∗ y i K ( x i , x j ) ) 0 决策函数 f ( x ) s i g n [ ∑ i 1 N α i ∗ y i K ( x i , x ) ( y j − ∑ i 1 N α i ∗ y i K ( x i , x j ) ) ] \begin{cases} \sum\limits_{i1}^N\alpha_i^*y_i K(x_i,x)\left(y_j-\sum\limits_{i1}^N\alpha_i^*y_iK(x_i,x_j)\right)0\\ 决策函数f(x)sign\left[\sum\limits_{i1}^N\alpha_i^*y_iK(x_i,x)\left(y_j-\sum\limits_{i1}^N\alpha_i^*y_iK(x_i,x_j)\right)\right] \end{cases} ⎩ ⎨ ⎧i1∑Nαi∗yiK(xi,x)(yj−i1∑Nαi∗yiK(xi,xj))0决策函数f(x)sign[i1∑Nαi∗yiK(xi,x)(yj−i1∑Nαi∗yiK(xi,xj))] 所以问题的关键为 如何确定核函数 K ( x i , x j ) K(x_i,x_j) K(xi,xj)
5.4.2 正定核函数
对于内积运算 ( x , x ) 0 当 x 0 时 ——正定性 ( x i , x j ) ( x j , x i ) ——非负性 } ⇒ 正定核 \left. \begin{aligned} (x,x)0当x0时——正定性\\ (x_i,x_j)(x_j,x_i)——非负性 \end{aligned} \right\}\Rightarrow 正定核 (x,x)0当x0时(xi,xj)(xj,xi)——正定性——非负性}⇒正定核 故正定核函数应满足 对称性 K ( x , z ) K ( z , x ) K(x,z)K(z,x) K(x,z)K(z,x) 正定性 ∀ x 1 , x 2 ⋯ , x N ∈ R n \forall x_1,x_2\cdots,x_N\in R^n ∀x1,x2⋯,xN∈Rn K ( x i , x j ) K(x_i,x_j) K(xi,xj) 的Gram阵是半正定的 Gram阵 原 [ ( x 1 , x 1 ) ⋯ ( x 1 , x N ) ⋮ ⋱ ⋮ ( x N , x 1 ) ⋯ ( x N , x N ) ] 新 [ K ( x 1 , x 1 ) ⋯ K ( x 1 , x N ) ⋮ ⋱ ⋮ K ( x N , x 1 ) ⋯ K ( x N , x N ) ] 原\left[ \begin{matrix} (x_1,x_1)\cdots(x_1,x_N)\\ \vdots\ddots\vdots\\ (x_N,x_1)\cdots(x_N,x_N) \end{matrix} \right]\qquad 新\left[ \begin{matrix} K(x_1,x_1)\cdotsK(x_1,x_N)\\ \vdots\ddots\vdots\\ K(x_N,x_1)\cdotsK(x_N,x_N) \end{matrix} \right] 原 (x1,x1)⋮(xN,x1)⋯⋱⋯(x1,xN)⋮(xN,xN) 新 K(x1,x1)⋮K(xN,x1)⋯⋱⋯K(x1,xN)⋮K(xN,xN) 半正定 对于A ∀ x ≠ 0 \forall x\neq 0 ∀x0 有 x T A x ≥ 0 x^TAx\ge 0 xTAx≥0 则有A为半正定阵 半正定判定 { x T A x y T D y —— D 为对角阵 全部特根 λ ≥ 0 所有主子行列式 ≥ 0 \begin{cases} x^TAxy^TDy——D为对角阵\\ 全部特根\lambda\ge 0\\ 所有主子行列式\ge 0 \end{cases} ⎩ ⎨ ⎧xTAxyTDy——D为对角阵全部特根λ≥0所有主子行列式≥0
由 K ( x , z ) K(x,z) K(x,z) 构造 H \mathcal{H} H 空间
任何一个核函数都隐式定义了一个成为 再生核希尔伯特空间 的特征空间 欧式空间 { 空间 ( 集合 ) → 元素是向量 向量空间 ⊆ 线性空间 ( 元素 数乘 ∈ 空间 ) → 内积 内积空间 { 表示向量间关系 用夹角表示用 ( a , b ) 度量夹角大小 → 范数 赋范线性空间——表示向量大小、长度 数列存在极限且 ∈ 空间任一柯西列都是收敛列 { x 1 ⋯ , x N } { x 1 x 2 ⋯ x N 且 x 1 − x 2 x 2 − x 3 ⋯ x N − 1 − x N ( 柯西列 ) → 0 ↓ 巴拿赫空间 \begin{aligned} 欧式空间\begin{cases} 空间(集合)\xrightarrow{元素是向量}向量空间\subseteq 线性空间(元素数乘\in 空间)\\ \xrightarrow{内积}内积空间\begin{cases} 表示向量间关系\\ 用夹角表示用(a,b)度量夹角大小 \end{cases}\\ \xrightarrow{范数}赋范线性空间——表示向量大小、长度 \end{cases}\\ 数列存在极限且\in 空间任一柯西列都是收敛列\{x_1\cdots,x_N\}\\ \begin{cases} x_1x_2\cdotsx_N\\ 且x_1-x_2x_2-x_3\cdotsx_{N-1}-x_N(柯西列)\rightarrow 0\ \end{cases}\\ \downarrow\\ 巴拿赫空间 \end{aligned} 欧式空间↓巴拿赫空间⎩ ⎨ ⎧空间(集合)元素是向量 向量空间⊆线性空间(元素数乘∈空间)内积 内积空间{表示向量间关系用夹角表示用(a,b)度量夹角大小范数 赋范线性空间——表示向量大小、长度数列存在极限且∈空间任一柯西列都是收敛列{x1⋯,xN}{x1x2⋯xN且x1−x2x2−x3⋯xN−1−xN(柯西列)→0 对于非欧氏空间上的完备空间称为希尔伯特空间 H \mathcal{H} H
步骤
1. 定义映射 ϕ : x → K ( ⋅ , x ) \phi:x\rightarrow K(\cdot,x) ϕ:x→K(⋅,x) ⋅ \cdot ⋅ 表示任一位置元素 ϕ ( ⋅ ) ⋅ ϕ ( x ) K ( ⋅ , x ) \phi(\cdot)\cdot \phi(x)K(\cdot,x) ϕ(⋅)⋅ϕ(x)K(⋅,x) 表示 ϕ ( x ) \phi(x) ϕ(x) 与任一个元素的内积为 K ( ⋅ , x ) K(\cdot,x) K(⋅,x)
表示这个映射受核函数约束
线性组合 f ( ⋅ ) ∑ i 1 m α i K ( ⋅ , x i ) f(\cdot)\sum\limits_{i1}^m\alpha_iK(\cdot,x_i) f(⋅)i1∑mαiK(⋅,xi) ——向量 S { f ( ⋅ ) } ——向量空间 S\{f(\cdot)\}——向量空间 S{f(⋅)}——向量空间 2. S → 内积 内积空间 S\xrightarrow{内积}内积空间 S内积 内积空间 f ( ⋅ ) ∑ i 1 m α i K ( ⋅ , x i ) g ( ⋅ ) ∑ j 1 l β j ( ⋅ , z j ) } ⇒ f ⋅ g ∑ i 1 m ∑ j 1 l α i β j K ( x i , z j ) \left.\begin{aligned} f(\cdot)\sum\limits_{i1}^m\alpha_iK(\cdot,x_i)\\ g(\cdot)\sum\limits_{j1}^l\beta_j(\cdot,z_j)\\ \end{aligned} \right\}\Rightarrow f\cdot g\sum\limits_{i1}^m\sum\limits_{j1}^l\alpha_i\beta_jK(x_i,z_j) f(⋅)i1∑mαiK(⋅,xi)g(⋅)j1∑lβj(⋅,zj)⎭ ⎬ ⎫⇒f⋅gi1∑mj1∑lαiβjK(xi,zj) 证明 f ⋅ f ≥ 0 f ⋅ f ∑ i 1 m ∑ j 1 m α i α j K ( x i , x j ) ≥ 0 令 x ( α 1 , ⋯ , α m ) T , G [ K ( x 1 , x 1 ) ⋯ K ( x 1 , x m ) ⋮ ⋱ ⋮ K ( x m , x 1 ) ⋯ K ( x m , x m ) ] x T G x ( α 1 , ⋯ , α m ) G ( α 1 , ⋯ , α m ) T [ α 1 K ( x 1 , x 1 ) α 2 K ( x 2 , x 1 ) ⋯ α m K ( x m , x 1 ) ⋮ α 1 K ( x 1 , x m ) α 2 K ( x 2 , x m ) ⋯ α m K ( x m , x m ) ] ( α 1 , ⋯ , α m ) T ∑ i 1 m ∑ j 1 m α i α j K ( x i , x j ) ≥ 0 \begin{aligned} f\cdot f\ge 0\\ f\cdot f\sum\limits_{i1}^m\sum\limits_{j1}^m\alpha_i\alpha_jK(x_i,x_j)\ge 0\\ 令x(\alpha_1,\cdots,\alpha_m)^T,G\left[ \begin{matrix} K(x_1,x_1)\cdotsK(x_1,x_m)\\ \vdots\ddots\vdots\\ K(x_m,x_1)\cdotsK(x_m,x_m) \end{matrix} \right]\\ \begin{aligned} x^TGx(\alpha_1,\cdots,\alpha_m)G(\alpha_1,\cdots,\alpha_m)^T\\ \left[ \begin{matrix} \alpha_1K(x_1,x_1)\alpha_2K(x_2,x_1)\cdots\alpha_mK(x_m,x_1)\\ \vdots\\ \alpha_1K(x_1,x_m)\alpha_2K(x_2,x_m)\cdots\alpha_mK(x_m,x_m)\\ \end{matrix} \right](\alpha_1,\cdots,\alpha_m)^T\\ \sum\limits_{i1}^m\sum\limits_{j1}^m\alpha_i\alpha_jK(x_i,x_j)\ge 0 \end{aligned} \end{aligned} f⋅f≥0f⋅fi1∑mj1∑mαiαjK(xi,xj)≥0令x(α1,⋯,αm)T,G K(x1,x1)⋮K(xm,x1)⋯⋱⋯K(x1,xm)⋮K(xm,xm) xTGx(α1,⋯,αm)G(α1,⋯,αm)T α1K(x1,x1)α2K(x2,x1)⋯αmK(xm,x1)⋮α1K(x1,xm)α2K(x2,xm)⋯αmK(xm,xm) (α1,⋯,αm)Ti1∑mj1∑mαiαjK(xi,xj)≥0 3. S → 范数 赋范空间 → 完备化 H S\xrightarrow{范数}赋范空间\xrightarrow{完备化}\mathcal{H} S范数 赋范空间完备化 H
再生性 K ( ⋅ , x ) ⋅ K ( ⋅ , z ) K ( x , z ) f ( ⋅ ) ∑ i α i K ( ⋅ , x i ) K ( ⋅ , x ) f ( ⋅ ) ∑ i α i K ( x , x i ) f ( x ) K(\cdot,x)\cdot K(\cdot,z)K(x,z)\\ f(\cdot)\sum\limits_{i}\alpha_iK(\cdot,x_i)\\ K(\cdot,x)f(\cdot)\sum\limits_{i}\alpha_i K(x,x_i)f(x) K(⋅,x)⋅K(⋅,z)K(x,z)f(⋅)i∑αiK(⋅,xi)K(⋅,x)f(⋅)i∑αiK(x,xi)f(x)
常用核函数
在支持向量机中核函数的选择是一个核心问题常用核函数有
线性核 K ( X , Y ) X T Y K(X,Y)X^TY K(X,Y)XTY
多项式核 K ( X , Y ) ( X T Y c ) d K(X,Y)(X^TYc)^d K(X,Y)(XTYc)d c c c 为常数 d ≥ 1 d\ge 1 d≥1 为多项式次数
高斯核 K ( X , Y ) e − ∥ X − Y ∥ 2 2 σ 2 K(X,Y)e^{-\frac{\Vert X-Y\Vert^2}{2\sigma^2}} K(X,Y)e−2σ2∥X−Y∥2 σ 0 \sigma0 σ0 为高斯核带宽
拉普拉斯核 K ( X , Y ) e − ∥ X − Y ∥ σ K(X,Y)e^{-\frac{\Vert X-Y\Vert}{\sigma}} K(X,Y)e−σ∥X−Y∥
sigmod核 K ( X , Y ) t a n h ( β X T Y θ ) K(X,Y)tanh(\beta X^TY\theta) K(X,Y)tanh(βXTYθ) β 0 \beta 0 β0 θ 0 \theta 0 θ0
5.5 SVM参数求解算法
将支持向量机的最优化作为原始问题应用最优化理论中的拉格朗日对偶性可以通过求解其对偶问题得到原始问题的最优解
SVM关键是如何根据支持向量构建解算法的复杂度也主要取决于支持向量的数目
在算法实现过程中支持向量机会遇到大量训练样本下全局最优解难以求得的情况——SMO算法序列最小最优化
支持向量机的学习问题可以形式化为凸二次规划问题的求解SMO算法的特点是不断将原始的二次规划问题分解为只有两个变量的二次规划子问题并求解子问题的解析解直到所有变量满足条件为止
5.6 SVM与线性模型关系
逻辑斯蒂模型损失函数 J ( ω ) − 1 n [ ∑ i 1 n ∑ k 1 2 I ( y i k ) ln P ( y i k ∣ x i , ω ) ] − 1 n [ ∑ i 1 n y i ln P ( y i 1 ∣ x i , ω ) ( 1 − y i ) ln P ( y i 0 ∣ x i , ω ) ] \begin{aligned} J(\omega)-\frac{1}{n}\left[\sum\limits_{i1}^n\sum\limits_{k1}^2I(y_ik)\ln P(y_ik\vert x_i,\omega)\right]\\ -\frac{1}{n}\left[\sum\limits_{i1}^ny_i\ln P(y_i1\vert x_i,\omega)(1-y_i)\ln P(y_i0\vert x_i,\omega)\right] \end{aligned} J(ω)−n1[i1∑nk1∑2I(yik)lnP(yik∣xi,ω)]−n1[i1∑nyilnP(yi1∣xi,ω)(1−yi)lnP(yi0∣xi,ω)] 正则化 J ( ω ) λ 2 n ∥ ω ∥ 2 2 J(\omega)\frac{\lambda}{2n}\Vert \omega\Vert_2^2 J(ω)2nλ∥ω∥22 即逻辑斯蒂模型先有损失函数再做正则化 SVM将损失函数作为约束先求出参数再以损失函数为约束
