模式识别与机器学习-SVM（核方法）
SVM（核方法）
谨以此博客作为复习期间的记录
核方法
对解线性分类问题，线性分类支持向量机是一种非常有效的方法．但是，有时分类问题是非线性的，这时可以使用非线性支持向量机，核心思想是通过核方法将低维非线性可分数据转化为高维线性可分数据。
非线性问题往往不好求解，所以希望能用解线性分类问题的方法解决这个问题. 所采取的方法是进行一个非线性变换, 将非线性问题变换为线性问题, 通过解变换后的线性问题的方法求解原来的非线性问题. 对图 7.7 所示的例子，通过变换, 将左图中椭圆变换成右图中的直线, 将非线性分类问题变换为线性分类问题.
设原空间为
X
?
R
2
,
x
=
(
x
(
1
)
,
x
(
2
)
)
T
∈
X
\mathcal{X} \subset \mathbf{R}^2, x=\left(x^{(1)}, x^{(2)}\right)^{\mathrm{T}} \in \mathcal{X}
X?R2,x=(x(1),x(2))T∈X, 新空间为
Z
?
R
2
,
z
=
(
z
(
1
)
,
z
(
2
)
)
T
∈
Z
\mathcal{Z} \subset \mathbf{R}^2, z=\left(z^{(1)}, z^{(2)}\right)^{\mathrm{T}} \in \mathcal{Z}
Z?R2,z=(z(1),z(2))T∈Z,定义从原空间到新空间的变换 (映射):
z
=
?
(
x
)
=
(
(
x
(
1
)
)
2
,
(
x
(
2
)
)
2
)
T
z=\phi(x)=\left(\left(x^{(1)}\right)^2,\left(x^{(2)}\right)^2\right)^{\mathrm{T}}
z=?(x)=((x(1))2,(x(2))2)T
经过变换
z
=
?
(
x
)
z=\phi(x)
z=?(x), 原空间
X
?
R
2
\mathcal{X} \subset \mathbf{R}^2
X?R2 变换为新空间
Z
?
R
2
\mathcal{Z} \subset \mathbf{R}^2
Z?R2, 原空间中的点相应地变换为新空间中的点，原空间中的椭圆
w
1
(
x
(
1
)
)
2
+
w
2
(
x
(
2
)
)
2
+
b
=
0
w_1\left(x^{(1)}\right)^2+w_2\left(x^{(2)}\right)^2+b=0
w1?(x(1))2+w2?(x(2))2+b=0
变换成为新空间中的直线
w
1
z
(
1
)
+
w
2
z
(
2
)
+
b
=
0
w_1 z^{(1)}+w_2 z^{(2)}+b=0
w1?z(1)+w2?z(2)+b=0
在变换后的新空间里，直线 w 1 z ( 1 ) + w 2 z ( 2 ) + b = 0 w_1 z^{(1)}+w_2 z^{(2)}+b=0 w1?z(1)+w2?z(2)+b=0 可以将变换后的正负实例点正确分开. 这样, 原空间的非线性可分问题就变成了新空间的线性可分问题.
核技巧在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), \cdots,\left(x_N, y_N\right)\right\}
T={(x1?,y1?),(x2?,y2?),?,(xN?,yN?)}, 其中
x
i
∈
X
=
R
n
,
y
i
∈
x_i \in \mathcal{X}=\mathbf{R}^n, y_i \in
xi?∈X=Rn,yi?∈
Y
=
{
?
1
,
+
1
}
,
i
=
1
,
2
,
?
?
,
N
\mathcal{Y}=\{-1,+1\}, \quad i=1,2, \cdots, N
Y={?1,+1},i=1,2,?,N;
输出: 分类决策函数.
（1）选取适当的核函数
K
(
x
,
z
)
K(x, z)
K(x,z) 和适当的参数
C
C
C, 构造并求解最优化问题
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.?
∑
i
=
1
N
α
i
y
i
=
0
0
?
α
i
?
C
,
i
=
1
,
2
,
?
?
,
N
\begin{array}{ll} \min _\alpha & \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j K\left(x_i, x_j\right)-\sum_{i=1}^N \alpha_i \\ \text { s.t. } & \sum_{i=1}^N \alpha_i y_i=0 \\ & 0 \leqslant \alpha_i \leqslant C, \quad i=1,2, \cdots, N \end{array}
minα??s.t.??21?∑i=1N?∑j=1N?αi?αj?yi?yj?K(xi?,xj?)?∑i=1N?αi?∑i=1N?αi?yi?=00?αi??C,i=1,2,?,N?
求得最优解
α
?
=
(
α
1
?
,
α
2
?
,
?
?
,
α
N
?
)
T
\alpha^*=\left(\alpha_1^*, \alpha_2^*, \cdots, \alpha_N^*\right)^{\mathrm{T}}
α?=(α1??,α2??,?,αN??)T.
(2) 选择
α
?
\alpha^*
α? 的一个正分量
0
<
α
j
?
<
C
0<\alpha_j^*<C
0<αj??<C, 计算
b
?
=
y
j
?
∑
i
=
1
N
α
i
?
y
i
K
(
x
i
?
x
j
)
b^*=y_j-\sum_{i=1}^N \alpha_i^* y_i K\left(x_i \cdot x_j\right)
b?=yj??i=1∑N?αi??yi?K(xi??xj?)
（3）构造决策函数:
f
(
x
)
=
sign
?
(
∑
i
=
1
N
α
i
?
y
i
K
(
x
?
x
i
)
+
b
?
)
f(x)=\operatorname{sign}\left(\sum_{i=1}^N \alpha_i^* y_i K\left(x \cdot x_i\right)+b^*\right)
f(x)=sign(i=1∑N?αi??yi?K(x?xi?)+b?)
当 K ( x , z ) K(x, z) K(x,z) 是正定核函数时, 问题、 是凸二次规划问题, 解是存在的.
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！