小菜君的SVM笔记之核方法与核函数
前面对非线性支持向量机进行了简单的介绍。例如moons数据集,为其增加一个维度,即可很容易地构造一个平面对两类样本进行分割。然而,若映射至3维空间无法较好分割则需要映射到更高维空间,尤其是当原始数据维度较高时,可能需要将其映射到无穷维空间,这根本无法计算。
首先,给出核函数的定义。
定义:设
X
\mathcal{X}
X是输入空间,为欧氏空间
R
n
\mathbb{R}^n
Rn及其子空间或离散的几何,又设
H
\mathcal{H}
H为特征空间,为希尔伯特空间,若存在一个从
X
\mathcal{X}
X到
H
\mathcal{H}
H的映射
ϕ
(
x
)
:
X
→
H
\phi(\boldsymbol{x}):\ \mathcal{X} \rightarrow \mathcal{H}
ϕ(x): X→H使得对所有的
x
,
z
∈
X
\boldsymbol{x},\boldsymbol{z}\in \mathcal{X}
x,z∈X函数
K
(
x
,
z
)
K(\boldsymbol{x},\boldsymbol{z})
K(x,z)满足条件
K
(
x
,
z
)
=
ϕ
(
x
)
⋅
ϕ
(
z
)
K(\boldsymbol{x},\boldsymbol{z}) = \phi(\boldsymbol{x})\cdot \phi(\boldsymbol{z})
K(x,z)=ϕ(x)⋅ϕ(z)则称
K
(
x
,
z
)
K(\boldsymbol{x},\boldsymbol{z})
K(x,z)为核函数,
ϕ
(
x
)
\phi(\boldsymbol{x})
ϕ(x)为映射函数,而
ϕ
(
x
)
⋅
ϕ
(
z
)
\phi(\boldsymbol{x})\cdot \phi(\boldsymbol{z})
ϕ(x)⋅ϕ(z)称为
ϕ
(
x
)
\phi(\boldsymbol{x})
ϕ(x)和
ϕ
(
z
)
\phi(\boldsymbol{z})
ϕ(z)的内积。
正如之前在对偶问题的求解和SMO算法中,将 x ⊤ x \boldsymbol{x^\top}\boldsymbol{x} x⊤x写成内积的形式,即用核函数进行代替。通过核函数,我们并不需要显式地定义原始空间到特征空间的映射,仅通过定义核函数就可以在原始空间中进行计算,再通过内积体现在高维的特征空间当中,避免了在高维空间中进行复杂的计算。
然而,一个函数是否是核函数是有条件的,我们往往要求其是正定核函数(因为此时才能够保证特征空间的存在)。我们需要去找正定核函数的充要条件。
定理:设
K
:
X
×
X
→
R
K: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}
K:X×X→R是对称函数,则
K
(
x
,
z
)
K(\boldsymbol{x}, \boldsymbol{z})
K(x,z)是正定核函数的充要条件是对任意
x
i
∈
X
,
i
∈
[
m
]
\boldsymbol{x_i} \in \mathcal{X}, i \in [m]
xi∈X,i∈[m],
K
(
x
,
z
)
K(\boldsymbol{x}, \boldsymbol{z})
K(x,z)对应的Gram矩阵
K
=
[
K
(
x
i
,
x
j
)
]
m
×
m
K = \left[ K(\boldsymbol{x_i},\boldsymbol{x_j})\right]_{m \times m}
K=[K(xi,xj)]m×m是半正定矩阵。
在此不做证明,可参考李航老师《统计学习方法》中的证明。实际应用中我们往往是直接应用已有的函数。下面对常见的核函数进行介绍。
-
线性核函数
K ( x , z ) = x ⋅ z \begin{aligned} K(\boldsymbol{x},\boldsymbol{z}) = \boldsymbol{x} \cdot \boldsymbol{z} \end{aligned} K(x,z)=x⋅z - 多项式核函数
K ( x , z ) = ( γ x ⋅ z + r ) p \begin{aligned} K(\boldsymbol{x},\boldsymbol{z}) = (\gamma\boldsymbol{x} \cdot \boldsymbol{z}+r)^p \end{aligned} K(x,z)=(γx⋅z+r)p - 高斯核函数
K ( x , z ) = e − γ ∥ x − z ∥ 2 \begin{aligned} K(\boldsymbol{x},\boldsymbol{z}) = e^{-\gamma\Vert \boldsymbol{x} -\boldsymbol{z}\Vert^2} \end{aligned} K(x,z)=e−γ∥x−z∥2 - Sigmoid核函数
K ( x , z ) = t a n h ( γ x ⋅ z + r ) \begin{aligned} K(\boldsymbol{x},\boldsymbol{z}) = tanh(\gamma\boldsymbol{x} \cdot \boldsymbol{z}+r) \end{aligned} K(x,z)=tanh(γx⋅z+r)