20240329-1-SVM面试题

SVM面试题

1. SVM直观解释

SVM,Support Vector Machine,它是一种二分类模型,其基本模型定义为特征空间上的间隔最大的线性分类器,间隔最大使它有别于感知机;其还包括核技巧,这使它成为实质上的非线性分类器。其学习策略就是间隔最大化,可形式化为一个求解凸二次规划的问题。其学习算法就是求解凸二次规划的最优化算法。

这里涉及了几个概念,二分类模型线性分类器间隔最大化凸二次规划问题

  • 二分类模型:给定的各个样本数据分别属于两个类之一,而目标是确定新数据点将归属到哪个类中。
  • 线性分类器:分割样本点的分类器是一个超平面,这也就要求样本线性可分,这是hard-margin SVM的要求,对于后来的soft-margin SVM,放低为近似线性可分,再到后来的核技巧,要求映射到高维空间后要近似线性可分。
  • 线性可分: D 0 D0 D0 D 1 D1 D1 n n n维欧氏空间中的两个点集(点的集合)。如果存在 n n n维向量 w w w和实数 b b b,使得所有属于 D 0 D0 D0的点 xi 都有 w x i + b > 0 wx_i+b>0 wxi+b>0,而对于所有属于 D 1 D1 D1的点 x j x_j xj则有 w x j + b < 0 wx_j+b<0 wxj+b<0。则我们称 D 0 D0 D0 D 1 D1 D1线性可分。
  • 间隔最大化:首先要知道SVM中有函数间隔和几何间隔,函数间隔刻画样本点到超平面的相对距离,几何间隔刻画的是样本点到超平面的绝对距离,SVM的直观目的就是找到最小函数距离的样本点,然后最大化它的几何间隔。
  • 凸二次规划:目标函数是二次的,约束条件是线性的。

2. 核心公式

  • 线性可分训练集: T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x n , y n ) } T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{n}, y_{n}\right)\right\} T={(x1,y1),(x2,y2),,(xn,yn)}
  • 学习得到的超平面: w ∗ T x + b ∗ = 0 w^{* T} x+b^{*}=0 wTx+b=0
  • 相应的分类决策函数: f ( x ) = sign ⁡ ( w ∗ T x + b ∗ ) f(x)=\operatorname{sign}\left(w^{* T} x+b^{*}\right) f(x)=sign(wTx+b)
  • SVM基本思想:间隔最大化,不仅要讲正负类样本分开,而且对最难分的点(离超平面最近的点)也要有足够大的确信度将他们分开。

在这里插入图片描述在这里插入图片描述

函数间隔

给定一个超平面 ( w , b ) (w, b) w,b,定义该超平面关于样本点 ( x i , y i ) (x_i,y_i ) (xi,yi) 的函数间隔为: γ ^ i = y i ( w T x i + b ) \widehat{\gamma}_{i}=y_{i}\left(w^{T} x_{i}+b\right) γ i=yi(wTxi+b)
定义该超平面关于训练集 T T T的函数间隔为: γ ^ = min ⁡ i = 1 , 2 , … , N γ ^ i \widehat{\gamma}=\min _{i=1,2, \ldots, N} \widehat{\gamma}_{i} γ =mini=1,2,,Nγ i

几何间隔

给定一个超平面 ( w , b ) (w, b) w,b,定义该超平面关于样本点 ( x i , y i ) (x_i,y_i ) (xi,yi) 的几何间隔为: γ i = y i ( w T ∥ w ∥ x i + b ∥ w ∥ ) \gamma_{i}=y_{i}\left(\frac{w^{T}}{\|w\|} x_{i}+\frac{b}{\|w\|}\right) γi=yi(wwTxi+wb)
定义该超平面关于训练集 T T T的几何间隔为: γ = min ⁡ i = 1 , 2 , … , N γ i \gamma=\min _{i=1,2, \ldots, N} \gamma_{i} γ=mini=1,2,,Nγi

函数间隔与几何间隔的关系

γ i = γ ^ i ∥ w ∥ , i = 1 , 2 , … , N γ = γ ^ ∥ w ∥ \begin{array}{c}{\gamma_{i}=\frac{\hat{\gamma}_{i}}{\|w\|}, i=1,2, \ldots, N} \\ {\gamma=\frac{\hat{\gamma}}{\|w\|}}\end{array} γi=wγ^i,i=1,2,,Nγ=wγ^

间隔最大化

求得一个几何间隔最大的分离超平面,可以表示为如下的最优化问题:
max ⁡ w , b γ s.t. y i ( w T ∥ w ∥ x i + b ∥ w ∥ ) ≥ γ , i = 1 , 2 , … , N \begin{array}{c}{\max _{w, b} \gamma} \\ {\text {s.t.} y_{i}\left(\frac{w^{T}}{\|w\|} x_{i}+\frac{b}{\|w\|}\right) \geq \gamma, i=1,2, \ldots, N}\end{array} maxw,bγs.t.yi(wwTxi+wb)γ,i=1,2,,N

考虑函数间隔与几何间隔的关系式,改写为:

max ⁡ w , b γ ^ ∥ w ∥ s.t.  y i ( w T x i + b ) ≥ γ ^ , i = 1 , 2 , … , N \begin{array}{c}{\max _{w, b} \frac{\hat{\gamma}}{\|w\|}} \\ {\text {s.t. } y_{i}\left(w^{T} x_{i}+b\right) \geq \hat{\gamma}, i=1,2, \ldots, N}\end{array} maxw,bwγ^s.t. yi(wTxi+b)γ^,i=1,2,,N

等价与下式

max ⁡ w , b 1 ∥ w ∥ s.t.  1 − y i ( w T x i + b ) ≤ 0 , i = 1 , 2 , … , N \begin{array}{c}{\max _{w, b} \frac{1}{\|w\|}} \\ {\text {s.t. } 1-y_{i}\left(w^{T} x_{i}+b\right) \leq 0, i=1,2, \ldots, N}\end{array} maxw,bw1s.t. 1yi(wTxi+b)0,i=1,2,,N

注意到最大化 1 ∥ w ∥ \frac{1}{\|w\|} w1 和最小化 1 2 ∥ w ∥ 2 \frac{1}{2}\|w\|^{2} 21w2是等价的,故最优化问题可转化为:

min ⁡ w , b 1 2 ∥ w ∥ 2 s.t.  1 − y i ( w T x i + b ) ≤ 0 , i = 1 , 2 , … , N \begin{array}{c}{\min _{w, b} \frac{1}{2}\|w\|^{2}} \\ {\text {s.t. } 1-y_{i}\left(w^{T} x_{i}+b\right) \leq 0, i=1,2, \ldots, N}\end{array} minw,b21w2s.t. 1yi(wTxi+b)0,i=1,2,,N

构造Lagrange函数:
L ( w , b , α ) = 1 2 ∥ w ∥ 2 + ∑ i = 1 N α i [ 1 − y i ( w T x i + b ) ] α i ≥ 0 , i = 1 , 2 , … , N \begin{aligned} L(w, b, \alpha)=& \frac{1}{2}\|w\|^{2}+\sum_{i=1}^{N} \alpha_{i}\left[1-y_{i}\left(w^{T} x_{i}+b\right)\right] \\ \alpha_{i} & \geq 0, i=1,2, \ldots, N \end{aligned} L(w,b,α)=αi21w2+i=1Nαi[1yi(wTxi+b)]0,i=1,2,,N

θ α ( w , b ) = max ⁡ α i ≥ 0 L ( w , b , α ) \theta_{\alpha}(w, b)=\max _{\alpha_{i} \geq 0} L(w, b, \alpha) θα(w,b)=maxαi0L(w,b,α)

则有 θ α ( w , b ) = { 1 2 ∥ w ∥ 2 , 当全部约束满足 + ∞ ,当存在约束不满足 \theta_{\alpha}(w, b)=\left\{\begin{array}{c}{\frac{1}{2}\|w\|^{2},当全部约束满足} \\ {+\infty,当存在约束不满足}\end{array}\right. θα(w,b)={21w2,当全部约束满足+,当存在约束不满足

故原问题等价于
min ⁡ w , b θ α ( w , b ) = min ⁡ w , b max ⁡ α i ≥ 0 L ( w , b , α ) \min _{w, b} \theta_{\alpha}(w, b)=\min _{w, b} \max _{\alpha_{i} \geq 0} L(w, b, \alpha) minw,bθα(w,b)=minw,bmaxαi0L(w,b,α)

对偶算法

根据拉格朗日对偶性,上式的对偶问题为:
min ⁡ w , b θ α ( w , b ) = max ⁡ α i ≥ 0 min ⁡ w , b L ( w , b , α ) \min _{w, b} \theta_{\alpha}(w, b)= \max _{\alpha_{i} \geq 0}\min _{w, b} L(w, b, \alpha) minw,bθα(w,b)=maxαi0minw,bL(w,b,α)

(1)求 min ⁡ w , b L ( w , b , α ) \min _{w, b} L(w, b, \alpha) minw,bL(w,b,α)

∇ w L ( w , b , α ) = w − ∑ i = 1 N α i y i x i = 0 \nabla_{w} L(w, b, \alpha)=w-\sum_{i=1}^{N} \alpha_{i} y_{i} x_{i}=0 wL(w,b,α)=wi=1Nαiyixi=0

∇ b L ( w , b , α ) = − ∑ i = 1 N α i y i = 0 \nabla_{b} L(w, b, \alpha)=-\sum_{i=1}^{N} \alpha_{i} y_{i}=0 bL(w,b,α)=i=1Nαiyi=0

w = ∑ i = 1 N α i y i x i w=\sum_{i=1}^{N} \alpha_{i} y_{i} x_{i} w=i=1Nαiyixi

∑ i = 1 N α i y i = 0 \sum_{i=1}^{N} \alpha_{i} y_{i}=0 i=1Nαiyi=0

将以上两式代入拉格朗日函数中消去,得
L ( w , b , α ) = − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ⟨ x i , x j ⟩ + ∑ i = 1 N α i \begin{aligned} L(w, b, \alpha) &=-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left\langle x_{i}, x_{j}\right\rangle+\sum_{i=1}^{\mathrm{N}} \alpha_{i} \end{aligned} L(w,b,α)=21i=1Nj=1Nαiαjyiyjxi,xj+i=1Nαi

(2)求 min ⁡ w , b L ( w , b , α ) \min _{w, b} L(w, b, \alpha) minw,bL(w,b,α)求对 α \alpha α的极大,即是对偶问题

max ⁡ α − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ⟨ x i , x j ⟩ + ∑ i = 1 N α i s.t. ∑ i = 1 N α i y i = 0 α i ≥ 0 , i = 1 , 2 , … , N \begin{aligned} \max _{\alpha} &-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left\langle x_{i}, x_{j}\right\rangle+\sum_{i=1}^{\mathrm{N}} \alpha_{i} \\ \text {s.t.} & \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \\ \alpha_{i} & \geq 0, i=1,2, \ldots, N \end{aligned} αmaxs.t.αi21i=1Nj=1Nαiαjyiyjxi,xj+i=1Nαii=1Nαiyi=00,i=1,2,,N

将极大改为极小,得

min ⁡ α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ⟨ x i , x j ⟩ − ∑ i = 1 N α i {\min _{\alpha} \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left\langle x_{i}, x_{j}\right\rangle-\sum_{i=1}^{\mathrm{N}} \alpha_{i}} minα21i=1Nj=1Nαiαjyiyjxi,xji=1Nαi

∑ i = 1 N α i y i = 0 \sum_{i=1}^{N} \alpha_{i} y_{i}=0 i=1Nαiyi=0

α i ≥ 0 , i = 1 , 2 , … , N \alpha_{i} \geq 0, i=1,2, \ldots, N αi0,i=1,2,,N

原问题的对偶问题:
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. ∑ i = 1 N α i y i = 0 α i ≥ 0 , i = 1 , 2 , … , N \begin{aligned} \min _{\alpha} & \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left\langle x_{i}, x_{j}\right\rangle-\sum_{i=1}^{\mathrm{N}} \alpha_{i} \\ \text {s.t.} & \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \\ & \alpha_{i} \geq 0, i=1,2, \ldots, N \end{aligned} αmins.t.21i=1Nj=1Nαiαjyiyjxi,xji=1Nαii=1Nαiyi=0αi0,i=1,2,,N

求解方法:
(1)由于该问题为凸优化问题,故可直接求解。
(2)由于该问题与其原问题等价,其原问题满足Slater定理,故该问题的解与KKT条件为充分必要的关系,故只需找到一组解满足KKT条件,即找到了问题的解(充分性)。

关于对偶问题的解 α ∗ = ( α 1 ∗ , α 2 ∗ , … , α N ∗ ) \alpha^{*}=\left(\alpha_{1}^{*}, \alpha_{2}^{*}, \ldots, \alpha_{N}^{*}\right) α=(α1,α2,,αN),是由SMO算法解出来的,这个结合加入松弛变量的情况再讲。

解出对偶问题的解 α ∗ = ( α 1 ∗ , α 2 ∗ , … , α N ∗ ) \alpha^{*}=\left(\alpha_{1}^{*}, \alpha_{2}^{*}, \ldots, \alpha_{N}^{*}\right) α=(α1,α2,,αN)后,怎么求原问题的解 w ∗ , b ∗ w^{*}, b^{*} w,b

由KKT条件可知,原问题和对偶问题均取到最优值的解 ( w ∗ , b ∗ , α ∗ ) \left(w^{*}, b^{*}, \alpha^{*}\right) (w,b,α)需满足以下四个要求:

  1. 对原始变量梯度为0:
    ∇ w L ( w ∗ , b ∗ , α ∗ ) = w ∗ − ∑ i = 1 N α i ∗ y i x i = 0 \nabla_{w} L\left(w^{*}, b^{*}, \alpha^{*}\right)=w^{*}-\sum_{i=1}^{N} \alpha_{i}^{*} y_{i} x_{i}=0 wL(w,b,α)=wi=1Nαiyixi=0
    ∇ b L ( w ∗ , b ∗ , α ∗ ) = − ∑ i = 1 N α i ∗ y i = 0 \nabla_{b} L\left(w^{*}, b^{*}, \alpha^{*}\right)=-\sum_{i=1}^{N} \alpha_{i}^{*} y_{i}=0 bL(w,b,α)=i=1Nαiyi=0
  2. 原问题可行:
    1 − y i ( w ∗ T x i + b ∗ ) ≤ 0 , i = 1 , 2 , … , N 1-y_{i}\left(w^{* T} x_{i}+b^{*}\right) \leq 0, i=1,2, \ldots, N 1yi(wTxi+b)0,i=1,2,,N
  3. 不等式约束乘子非负:
    α i ∗ ≥ 0 , i = 1 , 2 , … , N \alpha_{i}^{*} \geq 0, i=1,2, \ldots, N αi0,i=1,2,,N
  4. 对偶互补松弛:
    α i ∗ [ 1 − y i ( w ∗ T x i + b ∗ ) ] = 0 , i = 1 , 2 , … , N \alpha_{i}^{*}\left[1-y_{i}\left(w^{* T} x_{i}+b^{*}\right)\right]=0, i=1,2, \dots, N αi[1yi(wTxi+b)]=0,i=1,2,,N

由于1中
∇ w L ( w ∗ , b ∗ , α ∗ ) = w ∗ − ∑ i = 1 N α i ∗ y i x i = 0 \nabla_{w} L\left(w^{*}, b^{*}, \alpha^{*}\right)=w^{*}-\sum_{i=1}^{N} \alpha_{i}^{*} y_{i} x_{i}=0 wL(w,b,α)=wi=1Nαiyixi=0

得到
w ∗ = ∑ i = 1 N α i ∗ y i x i w^{*}=\sum_{i=1}^{N} \alpha_{i}^{*} y_{i} x_{i} w=i=1Nαiyixi
这样 w ∗ w^{*} w就求出来了

用反证法我们可以得到至少有一个 α i ∗ > 0 \alpha_{i}^{*}>0 αi>0,假设所有的 α i ∗ = 0 \alpha_{i}^{*}=0 αi=0,由 w ∗ − ∑ i = 1 N α i ∗ y i x i = 0 w^{*}-\sum_{i=1}^{N} \alpha_{i}^{*} y_{i} x_{i}=0 wi=1Nαiyixi=0知道, w ∗ = 0 w^{*}=0 w=0,而 w ∗ = 0 w^{*}=0 w=0显然不是原问题的解,我们要零解一点意义都没有。

接下来,求 b ∗ b^{*} b
α i ∗ \alpha_{i}^{*} αi 的一个分量满足 α i ∗ > 0 \alpha_{i}^{*}>0 αi>0 ,则有对应的由4中的 α i ∗ [ 1 − y i ( w ∗ T x i + b ∗ ) ] = 0 , i = 1 , 2 , … , N \alpha_{i}^{*}\left[1-y_{i}\left(w^{* T} x_{i}+b^{*}\right)\right]=0, i=1,2, \dots, N αi[1yi(wTxi+b)]=0,i=1,2,,N,有 1 − y j ( w ∗ T x j + b ∗ ) = 0 1-y_{j}\left(w^{* T} x_{j}+b^{*}\right)=0 1yj(wTxj+b)=0

代入 w ∗ w^{*} w和样本点 ( x j , y j ) (x_j,y_j) (xj,yj),求出
b ∗ = y j − ∑ i = 1 N α i ∗ y i ⟨ x i , x j ⟩ b^{*}=y_{j}-\sum_{i=1}^{N} \alpha_{i}^{*} y_{i}\left\langle x_{i}, x_{j}\right\rangle b=yji=1Nαiyixi,xj

这样超平面的两个参数 ( w ∗ , b ∗ ) (w^{*},b^{*}) (w,b)就都求出来了
w ∗ = ∑ i = 1 N α i ∗ y i x i w^{*}=\sum_{i=1}^{N} \alpha_{i}^{*} y_{i} x_{i} w=i=1Nαiyixi
b ∗ = y j − ∑ i = 1 N α i ∗ y i ⟨ x i , x j ⟩ b^{*}=y_{j}-\sum_{i=1}^{N} \alpha_{i}^{*} y_{i}\left\langle x_{i}, x_{j}\right\rangle b=yji=1Nαiyixi,xj

至于为什么SVM叫支持向量机,因为我们发现只有 α i ∗ > 0 \alpha_{i}^{*}>0 αi>0时,对应的样本 ( x i , y i ) (x_i,y_i) (xi,yi)才会对最终超平面的结果产生影响,此时 1 − y i ( w ∗ T x i + b ∗ ) = 0 1-y_{i}\left(w^{* T} x_{i}+b^{*}\right)=0 1yi(wTxi+b)=0, 也就是函数间隔为1,我们称这类样本为支持向量,所以这个模型被叫做支持向量机。支持向量的个数一般很少,所以支持向量机只有很少的“重要的”训练样本决定。

核技巧

基本思想:找一个映射Φ(一般为高维映射),将样本点特征x映射到新的特征空间Φ(x),使其在新的特征空间中线性可分(或近似线性可分),然后利用之前的SVM算法在新的特征空间中对样本进行分类。
在这里插入图片描述
流程:
输入训练集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x n , y n ) } T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{n}, y_{n}\right)\right\} T={(x1,y1),(x2,y2),,(xn,yn)}其中 x i ∈ R n , y i ∈ { − 1 , + 1 } x_{i} \in R^{n}, y_{i} \in\{-1,+1\} xiRn,yi{1,+1}
(1)选择合适的映射函数Φ,将训练集??映射为
T = { ( Φ ( x 1 ) , y 1 ) , ( Φ ( x 2 ) , y 2 ) , … , ( Φ ( x n ) , y n ) } T=\left\{\left(\Phi\left(x_{1}\right), y_{1}\right),\left(\Phi\left(x_{2}\right), y_{2}\right), \ldots,\left(\Phi\left(x_{n}\right), y_{n}\right)\right\} T={(Φ(x1),y1),(Φ(x2),y2),,(Φ(xn),yn)}
(2)选择惩罚参数C,构造并求解约束最优化问题(原问题的对偶问题)
min ⁡ α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ⟨ Φ ( x i ) , Φ ( x j ) ⟩ − ∑ i = 1 N α i \min_{\alpha} \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left\langle\Phi\left(x_{i}\right), \Phi\left(x_{j}\right)\right\rangle-\sum_{i=1}^{\mathrm{N}} \alpha_{i} minα21i=1Nj=1NαiαjyiyjΦ(xi),Φ(xj)i=1Nαi
s.t.  ∑ i = 1 N α i y i = 0 0 ≤ α i ≤ C , i = 1 , 2 , … , N \begin{aligned} \text { s.t. } & \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \\ & 0 \leq \alpha_{i} \leq C, i=1,2, \ldots, N \end{aligned}  s.t. i=1Nαiyi=00αiC,i=1,2,,N
求得最优解 α ∗ = ( α 1 ∗ , α 2 ∗ , … , α N ∗ ) T \alpha^{*}=\left(\alpha_{1}^{*}, \alpha_{2}^{*}, \ldots, \alpha_{N}^{*}\right)^{T} α=(α1,α2,,αN)T
(3)计算 W ∗ , b ∗ W^{*}, b^{*} W,b:
w ∗ = ∑ i = 1 N α i ∗ y i Φ ( x i ) w^{*}=\sum_{i=1}^{N} \alpha_{i}^{*} y_{i} \Phi\left(x_{i}\right) w=i=1NαiyiΦ(xi)
选择 a ∗ a^{*} a的一个分量满足 0 < α i ∗ < C 0<\alpha_{i}^{*}<C 0<αi<C,计算
b ∗ = y j − ∑ i = 1 N α i ∗ y i ⟨ Φ ( x i ) , Φ ( x j ) ⟩ b^{*}=y_{j}-\sum_{i=1}^{N} \alpha_{i}^{*} y_{i}\left\langle\Phi\left(x_{i}\right), \Phi\left(x_{j}\right)\right\rangle b=yji=1NαiyiΦ(xi),Φ(xj)
(4)求得分离超平面和分类决策函数:
w ∗ T Φ ( x ) + b ∗ = 0 w^{* T} \Phi(x)+b^{*}=0 wTΦ(x)+b=0
f ( x ) = sign ⁡ ( w ∗ T Φ ( x ) + b ∗ ) = sign ⁡ ( ∑ i = 1 N α i ∗ y i ⟨ Φ ( x ) , Φ ( x i ) ⟩ + b ∗ ) f(x)=\operatorname{sign}\left(w^{* T} \Phi(x)+b^{*}\right)=\operatorname{sign}\left(\sum_{i=1}^{N} \alpha_{i}^{*} y_{i}\left\langle\Phi(x), \Phi\left(x_{i}\right)\right\rangle+ b^{*}\right) f(x)=sign(wTΦ(x)+b)=sign(i=1NαiyiΦ(x),Φ(xi)+b)

该算法的问题:
(1)合适的映射函数??太难找,几乎找不到
(2)假设找到了映射函数??,由于将数据映射到高维,在高维空间中做运算,计算量太大(维数灾难)

改进:
考虑到算法中如果不需写出分离超平面,即不需写出 w ? w^{?} w?,而是直接用 f ( x ) = sign ⁡ ( w ∗ T Φ ( x ) + b ∗ ) = sign ⁡ ( α i ∗ y i ⟨ Φ ( x ) , Φ ( x j ) ⟩ + b ∗ ) f(x)=\operatorname{sign}\left(w^{* T} \Phi(x)+b^{*}\right)=\operatorname{sign}\left(\alpha_{i}^{*} y_{i}\left\langle\Phi(x), \Phi\left(x_{j}\right)\right\rangle+ b^{*}\right) f(x)=sign(wTΦ(x)+b)=sign(αiyiΦ(x),Φ(xj)+b)来做预测,同样可以给出分类边界以及达到预测目的。这样的话,算法中需要用到样本的地方全部以内积形式出现,如果我们能够找到一种函数,能够在低维空间中直接算出高维内积,并且该函数对应着某个映射,即解决了以上两个问题。

核函数的本质:用相似度函数重新定义内积运算。

什么样的函数可以作为核函数?
核函数对应的Gram矩阵为半正定矩阵。

常用的核函数:

  1. 线性核函数(linear kernel) K ( x , z ) = x T z K(x, z)=x^{T} z K(x,z)=xTz
  2. 多项式核函数(polynomial kernel function) K ( x , z ) = ( γ x T z + r ) p K(x, z)=\left(\gamma x^{T} z+r\right)^{p} K(x,z)=(γxTz+r)p
  3. 高斯核函数( Gaussian kernel function ) K ( x , z ) = exp ⁡ ( − γ ∥ x − z ∥ 2 ) K(x, z)=\exp \left(-\gamma\|x-z\|^{2}\right) K(x,z)=exp(γxz2)

3. SVM 为什么采用间隔最大化

当训练数据线性可分时,存在无穷个分离超平面可以将两类数据正确分开。感知机利用误分类最小策略,求得分离超平面,不过此时的解有无穷多个。线性可分支持向量机利用间隔最大化求得最优分离超平面,这时,解是唯一的。另一方面,此时的分隔超平面所产生的分类结果是最鲁棒的,对未知实例的泛化能力最强。可以借此机会阐述一下几何间隔以及函数间隔的关系。

4. 为什么要将求解 SVM 的原始问题转换为其对偶问题

  • 对偶问题往往更易求解,当我们寻找约束存在时的最优点的时候,约束的存在虽然减小了需要搜寻的范围,但是却使问题变得更加复杂。为了使问题变得易于处理,我们的方法是把目标函数和约束全部融入一个新的函数,即拉格朗日函数,再通过这个函数来寻找最优点。

  • 可以自然引入核函数,进而推广到非线性分类问题。

5. 为什么 SVM 要引入核函数

当样本在原始空间线性不可分时,可将样本从原始空间映射到一个更高维的特征空间,使得样本在这个特征空间内线性可分。而引入这样的映射后,所要求解的对偶问题的求解中,无需求解真正的映射函数,而只需要知道其核函数。核函数的定义: K ( x , y ) = < ϕ ( x ) , ϕ ( y ) > K(x,y)=<ϕ(x),ϕ(y)> K(x,y)=<ϕ(x),ϕ(y)>,即在特征空间的内积等于它们在原始样本空间中通过核函数 $K $计算的结果。一方面数据变成了高维空间中线性可分的数据,另一方面不需要求解具体的映射函数,只需要给定具体的核函数即可,这样使得求解的难度大大降低。

6. 为什么SVM对缺失数据敏感

  • SVM 没有处理缺失值的策略
  • SVM的效果和支持向量点有关,缺失值可能影响支持向量点的分布

7. SVM 核函数之间的区别

SVM 核函数一般选择线性核高斯核(RBF 核)

线性核:主要用于线性可分的情形,参数少,速度快,对于一般数据,分类效果已经很理想了。

RBF 核:主要用于线性不可分的情形,参数多,分类结果非常依赖于参数。

如果 Feature 的数量很大,跟样本数量差不多,这时候选用线性核的 SVM。

如果 Feature 的数量比较小,样本数量一般,不算大也不算小,选用高斯核的 SVM。

8. LR和SVM的联系与区别

  • 联系:

    • LR和SVM都可以处理分类问题,且一般都用于处理线性二分类问题
    • 两个方法都可以增加不同的正则化项,如l1、l2等等。所以在很多实验中,两种算法的结果是很接近的。
  • 区别:

    • LR是参数模型,SVM是非参数模型。
    • 从目标函数来看,区别在于逻辑回归采用的是交叉熵损失函数,SVM采用的是合页损失函数,这两个损失函数的目的都是增加对分类影响较大的数据点的权重,减少与分类关系较小的数据点的权重。
    • SVM的处理方法是只考虑支持向量点,也就是和分类最相关的少数点,去学习分类器。而逻辑回归通过非线性映射,大大减小了离分类平面较远的点的权重,相对提升了与分类最相关的数据点的权重。
    • 逻辑回归相对来说模型更简单,好理解,特别是大规模线性分类时比较方便。而SVM的理解和优化相对来说复杂一些,SVM转化为对偶问题后,分类只需要计算与少数几个支持向量的距离,这个在进行复杂核函数计算时优势很明显,能够大大简化模型和计算。

9. SVM的原理是什么?

SVM是一种二类分类模型,其主要思想为找到空间中的一个更够将所有数据样本划开的超平面,并且使得数据集中所有数据到这个超平面的距离最短。它的基本模型是在特征空间中寻找间隔最大化的分离超平面的线性分类器。(间隔最大使它有别于感知机)。需要求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对于线性可分的数据集来说,这样的超平面有无穷多个(即感知机),但是几何间隔最大的分离超平面却是唯一的。

10. SVM如何处理多分类问题?

一对多:就是对每个类都训练出一个分类器,设定为目标类为一类,其余类为另外一类。这样针对k个类可以训练出k个分类器,当有一个新的样本来的时候,用这k个分类器来测试,那个分类器的概率高,那么这个样本就属于哪一类。
一对一:任意两个类训练出一个分类器,如果有k类,一共训练出 C ( 2 , k ) C(2,k) C(2,k) 个分类器,这样当有一个新的样本要来的时候,用这$C(2,k) $个分类器来测试,每当被判定属于某一类的时候,该类就加一,最后票数最多的类别被认定为该样本的类。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/312843.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vue+element作用域插槽

作用域插槽的样式由父组件决定&#xff0c;内容却由子组件控制。 在el-table使用作用域插槽 <el-table><el-table-column slot-scope" { row, column, $index }"></el-table-column> </el-table>在el-tree使用作用域插槽 <el-tree>…

redis-plus-plus的安装与使用

文章目录 一、安装第一步&#xff1a;安装hiredis第二步&#xff1a;安装redis-plus-plus第三步&#xff1a;将编译后的可执行文件移动到/usr/local对应目录第四步&#xff1a;更新动态库 二、使用第一步&#xff1a;编写示例代码第二步&#xff1a;编译运行 本文参考自 redis-…

JVM垃圾回收与算法

1. 如何确定垃圾 1.1 引用计数法 在 Java 中&#xff0c;引用和对象是有关联的。如果要操作对象则必须用引用进行。因此&#xff0c;很显然一个简单 的办法是通过引用计数来判断一个对象是否可以回收。简单说&#xff0c;即一个对象如果没有任何与之关 联的引用&#xff0c;即…

ENSP防火墙配置策略路由及ip-link探测

拓扑 配置目标 1.A区域走ISP1&#xff0c;B区域走ISP2 2. isp线路故障时及时切换到另一条线路 配置接口及安全区域 配置安全策略 配置nat 配置默认路由 配置ip-link 配置策略路由 cl-1 cl-2 验证配置成功 策略路由 A走ISP1 B走ISP2 验证线路故障 isp1 in g0/0/0 shoutdow…

基于Python的机器学习的文本分类系统

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…

VIT论文阅读

论文地址&#xff1a;https://arxiv.org/pdf/2010.11929.pdf VIT论文阅读 摘要INTRODUCTION结论RELATEDWORKMETHOD1.VISIONTRANSFORMER(VIT)整体流程消融实验HEAD TYPE AND CLASSTOKENpoisitional embedding 整体过程公式Inductive biasHybrid Architecture 2.FINE-TUNINGANDH…

LeetCode236:二叉树的最近公共祖先

题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点 p、q&#xff0c;最近公共祖先表示为一个节点 x&#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大&#xff08;一个节点也可以是…

03攻防世界-unserialize3

根据题目可以看出&#xff0c;这是个反序列化的题目 打开网址观察题目可以看到这里是php的代码&#xff0c;那么也就是php的反序列化 本题需要利用反序列化字符串来进行解题&#xff0c;根据源码提示我们需要构造code。 序列化的意思是&#xff1a;是将变量转换为可保存或传输…

向量数据库与图数据库:理解它们的区别

作者&#xff1a;Elastic Platform Team 大数据管理不仅仅是尽可能存储更多的数据。它关乎能够识别有意义的见解、发现隐藏的模式&#xff0c;并做出明智的决策。这种对高级分析的追求一直是数据建模和存储解决方案创新的驱动力&#xff0c;远远超出了传统关系数据库。 这些创…

计算机网络 2.2数据传输方式

第二节 数据传输方式 一、数据通信系统模型 添加图片注释&#xff0c;不超过 140 字&#xff08;可选&#xff09; 1.数据终端设备&#xff08;DTE&#xff09; 作用&#xff1a;用于处理用户数据的设备&#xff0c;是数据通信系统的信源和信宿。 设备&#xff1a;便携计算机…

通过调用Vcenter-Api获取Vcenter中服务器信息

通过调用Vcenter-Api获取Vcenter中服务器信息 文章目录 通过调用Vcenter-Api获取Vcenter中服务器信息1. 获取Vmware API帮助文档2. 获取访问凭证3. 获取服务器清单4. 获取服务器更多信息5. 获取虚机更多信息6. 获取磁盘信息7. 获取操作系统相关 1. 获取Vmware API帮助文档 htt…

Chrome修改主题颜色

注意&#xff1a;自定义Chrome按钮只在搜索引擎为Google的时候出现。

抖店每天稳定出单300+,但是不挣钱,你图什么?

我是王路飞。 如果你的抖店已经可以稳定出单了&#xff0c;且每天可以保证稳定出单300。 那么&#xff0c;你有没有算过你到底有没有赚到马内&#xff1f;是小赚还是大赚&#xff1f; 如果这些单量没有给你带来一个比较满意的【利润回报】&#xff0c; 那么请问&#xff0c…

【数据分析】AHP层次分析法

博主总结&#xff1a;根据每个方案x各准则因素权重累加结果 对比来选择目标。数据主观性强 简介 AHP层次分析法是一种解决多目标复杂问题的定性和定量相结合进行计算决策权重的研究方法。该方法将定量分析与定性分析结合起来&#xff0c;用决策者的经验判断各衡量目标之间能…

第十五届蓝桥杯复盘python大学A组——试题B 召唤数学精灵

按照正常思路解决&#xff0c;由于累乘消耗大量时间&#xff0c;因此这不是一个明智的解决方案。 这段代码执行速度非常慢的原因在于它试图计算非常大的数的阶乘&#xff08;累乘&#xff09;&#xff0c;并且对于每一个i的值都执行这个计算。阶乘的增长是极其迅速的&#xff…

考研数学|「基础」和「强化」阶段分别怎么做?

从目前考研数学的趋势来看&#xff0c;更加注重数学基础的理解和计算量。也就是基础知识和计算&#xff0c;如何锻炼这两种能力就显得尤为重要。希望我的复习经验可以给到读者一些启发。 数学规划 从备考过程来看&#xff0c;数学的复习可以分为三个阶段&#xff1a;1、基础阶…

.net框架和c#程序设计第三次测试

目录 一、测试要求 二、实现效果 三、实现代码 一、测试要求 二、实现效果 数据库中的内容&#xff1a; 使用数据库中的账号登录&#xff1a; 若不是数据库中的内容&#xff1a; 三、实现代码 login.aspx文件&#xff1a; <% Page Language"C#" AutoEventW…

Pytest测试用例中的mark用法(包含代码示例与使用场景详解)

在软件开发中&#xff0c;测试是确保代码质量和功能稳定性的重要环节。Python作为一门流行的编程语言&#xff0c;拥有丰富的测试工具和框架&#xff0c;其中pytest是其中之一。pytest提供了丰富的功能来简化测试用例的编写&#xff0c;其中的mark功能允许我们对测试用例进行标…

程序设计|C语言教学——C语言基础1:C语言的引入和入门

一、程序的执行 1.定义 解释&#xff1a;借助一个程序&#xff0c;那个程序能够试图理解你的程序&#xff0c;然后按照你的要求执行。下次执行的时候还需要从零开始解释。 编译&#xff1a;借助一个程序&#xff0c;能够像翻译官一样&#xff0c;把你的程序翻译成机器语言&a…