习题7.1
题目：
比较感知机的对偶形式与线性可分支持向量机的对偶形式.
解答：
感知机：
原始形式
min
w
,
b
L
(
w
,
b
)
=
∑
i
=
1
N
[
−
y
i
(
w
⋅
x
i
+
b
)
]
+
\min _{w, b} L(w, b)=\sum_{i=1}^{N}\left[-y_{i}\left(w \cdot x_{i}+b\right)\right]_{+}
min
w
,
b
L
(
w
,
b
)
=
∑
i
=
1
N
[
−
y
i
(
w
⋅
x
i
+
b
)
]
+
对偶形式
min
w
,
b
L
(
w
,
b
)
=
min
α
i
L
(
α
i
)
=
∑
i
=
1
N
(
−
y
i
(
∑
j
=
1
N
α
j
y
j
x
j
⋅
x
i
+
∑
j
=
1
N
α
j
y
j
)
)
\min _{w, b} L(w, b)=\min _{\alpha_{i}} L\left(\alpha_{i}\right)=\sum_{i=1}^{N}\left(-y_{i}\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \cdot x_{i}+\sum_{j=1}^{N} \alpha_{j} y_{j}\right)\right)
min
w
,
b
L
(
w
,
b
)
=
min
α
i
L
(
α
i
)
=
∑
i
=
1
N
(
−
y
i
(
∑
j
=
1
N
α
j
y
j
x
j
⋅
x
i
+
∑
j
=
1
N
α
j
y
j
)
)
由对偶形式可以求到
w
,
b
w,b
w
,
b
w
=
∑
i
=
1
N
α
i
y
i
x
i
,
b
=
∑
i
=
1
N
α
i
y
i
w=\sum_{i=1}^{N} \alpha_{i} y_{i} x_{i,} \\b=\sum_{i=1}^{N} \alpha_{i} y_{i}
w
=
∑
i
=
1
N
α
i
y
i
x
i
,
b
=
∑
i
=
1
N
α
i
y
i
线性可分支持向量机：
原始形式：
min
w
,
b
1
2
∥
w
∥
2
s.t.
y
i
(
w
⋅
x
i
+
b
)
−
1
⩾
0
,
i
=
1
,
2
,
⋯
,
N
\begin{array}{ll}\min _{w, b} & \frac{1}{2}\|w\|^{2} \\ \text { s.t. } & y_{i}\left(w \cdot x_{i}+b\right)-1 \geqslant 0, \quad i=1,2, \cdots, N\end{array}
min
w
,
b
s.t.
2
1
∥
w
∥
2
y
i
(
w
⋅
x
i
+
b
)
−
1
⩾
0
,
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{array}{cl}\min _{\alpha} & \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)-\sum_{i=1}^{N} \alpha_{i} \\ \text { s.t. } & \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \\ & \alpha_{i} \geqslant 0, \quad i=1,2, \cdots, N\end{array}
min
α
s.t.
2
1
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
y
i
y
j
(
x
i
⋅
x
j
)
−
∑
i
=
1
N
α
i
∑
i
=
1
N
α
i
y
i
=
0
α
i
⩾
0
,
i
=
1
,
2
,
⋯
,
N
由对偶形式可以求到
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
=
1
N
α
i
∗
y
i
x
i
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(x_{i} \cdot x_{j}\right)
b
∗
=
y
j
−
∑
i
=
1
N
α
i
∗
y
i
(
x
i
⋅
x
j
)
习题7.2
题目：
已知正例点
x
1
=
(
1
,
2
)
T
,
x
2
=
(
2
,
3
)
T
,
x
3
=
(
3
,
3
)
T
x_1=(1,2)^{T}, x_2=(2,3)^{T}, x_3=(3,3)^{T}
x
1
=
(
1
,
2
)
T
,
x
2
=
(
2
,
3
)
T
,
x
3
=
(
3
,
3
)
T
，负例点
x
4
=
(
2
,
1
)
T
,
x
5
=
(
3
,
2
)
T
x_4=(2,1)^{T}, x_5=(3,2)^{T}
x
4
=
(
2
,
1
)
T
,
x
5
=
(
3
,
2
)
T
，试求最大间隔分离超平面和分类决策函数，并在图上画出分离超平面、间隔边界及支持向量.
解答：
原始形式
min
1
2
∥
w
1
2
+
w
2
2
∥
\min \frac{1}{2}\left\|w_{1}^{2}+w_{2}^{2}\right\|
min
2
1
∥
∥
w
1
2
+
w
2
2
∥
∥
s.t.
w
1
+
2
w
2
+
b
≥
1…
(
1
)
\quad w_{1}+2 w_{2}+b \geq 1…(1)
w
1
+
2
w
2
+
b
≥
1
.
.
.
(
1
)
2
w
1
+
3
w
2
+
b
≥
1…
(
2
)
2 w_{1}+3 w_{2}+b \geq 1…(2)
2
w
1
+
3
w
2
+
b
≥
1
.
.
.
(
2
)
3
w
1
+
3
w
2
+
b
≥
1…
(
3
)
3 w_{1}+3 w_{2}+b \geq 1…(3)
3
w
1
+
3
w
2
+
b
≥
1
.
.
.
(
3
)
−
2
w
1
−
w
2
−
b
≥
1…
(
4
)
-2 w_{1}-w_{2}-b \geq 1…(4)
−
2
w
1
−
w
2
−
b
≥
1
.
.
.
(
4
)
−
3
w
1
−
2
w
2
−
b
≥
1…
(
5
)
-3 w_{1}-2 w_{2}-b \geq 1…(5)
−
3
w
1
−
2
w
2
−
b
≥
1
.
.
.
(
5
)
化简一下有
(
1
)
+
(
4
)
:
−
w
1
+
w
2
≥
2
(1)+(4): -w_{1}+w_{2} \geq 2
(
1
)
+
(
4
)
:
−
w
1
+
w
2
≥
2
(
1
)
+
(
5
)
:
−
2
w
1
≥
2
(1)+(5): -2w_{1} \geq 2
(
1
)
+
(
5
)
:
−
2
w
1
≥
2
(
2
)
+
(
4
)
:
2
w
2
≥
2
(2)+(4): 2w_{2}\geq 2
(
2
)
+
(
4
)
:
2
w
2
≥
2
(
3
)
+
(
4
)
:
w
1
+
2
w
2
≥
2
(3)+(4): w_{1}+2w_{2} \geq 2
(
3
)
+
(
4
)
:
w
1
+
2
w
2
≥
2
(
3
)
+
(
5
)
:
w
2
≥
2
(3)+(5): w_{2} \geq 2
(
3
)
+
(
5
)
:
w
2
≥
2
得到的5个方程，使用高中知识数学规划，画一下关于
w
1
,
w
2
w_{1},w_{2}
w
1
,
w
2
坐标系，发现
w
1
2
+
w
2
2
w_{1}^{2}+w_{2}^{2}
w
1
2
+
w
2
2
最小是在
w
1
=
−
1
,
w
2
=
2
w_{1}=-1, w_{2} = 2
w
1
=
−
1
,
w
2
=
2
将这个值带入原来的（1）-（5）方程，可以得到
b
=
−
2
b = -2
b
=
−
2
（图就不画了(✺ω✺)）
习题7.3
题目：
线性支持向量机还可以定义为以下形式：
min
w
,
b
,
ξ
1
2
∥
w
∥
2
+
C
∑
i
=
1
N
ξ
i
2
s.t.
y
i
(
w
⋅
x
i
+
b
)
⩾
1
−
ξ
i
,
i
=
1
,
2
,
⋯
,
N
ξ
i
⩾
0
,
i
=
1
,
2
,
⋯
,
N
\begin{array}{ll}\min _{w, b, \xi} & \frac{1}{2}\|w\|^{2}+C \sum_{i=1}^{N} \xi_{i}^{2} \\ \text { s.t. } & y_{i}\left(w \cdot x_{i}+b\right) \geqslant 1-\xi_{i}, \quad i=1,2, \cdots, N \\ & \xi_{i} \geqslant 0, \quad i=1,2, \cdots, N\end{array}
min
w
,
b
,
ξ
s.t.
2
1
∥
w
∥
2
+
C
∑
i
=
1
N
ξ
i
2
y
i
(
w
⋅
x
i
+
b
)
⩾
1
−
ξ
i
,
i
=
1
,
2
,
⋯
,
N
ξ
i
⩾
0
,
i
=
1
,
2
,
⋯
,
N
试求其对偶形式.
解答：
与课本110页的推导类似
这个形式的拉格朗日函数为
L
(
w
,
b
,
ξ
,
α
,
μ
)
≡
1
2
∥
w
∥
2
+
C
∑
i
=
1
N
ξ
i
2
−
∑
i
=
1
N
α
i
(
y
i
(
w
⋅
x
i
+
b
)
−
1
+
ξ
i
)
−
∑
i
=
1
N
μ
i
ξ
i
L(w, b, \xi, \alpha, \mu) \equiv \frac{1}{2}\|w\|^{2}+C \sum_{i=1}^{N} \xi_{i}^2-\sum_{i=1}^{N} \alpha_{i}\left(y_{i}\left(w \cdot x_{i}+b\right)-1+\xi_{i}\right)-\sum_{i=1}^{N} \mu_{i} \xi_{i}
L
(
w
,
b
,
ξ
,
α
,
μ
)
≡
2
1
∥
w
∥
2
+
C
∑
i
=
1
N
ξ
i
2
−
∑
i
=
1
N
α
i
(
y
i
(
w
⋅
x
i
+
b
)
−
1
+
ξ
i
)
−
∑
i
=
1
N
μ
i
ξ
i
其中
α
i
⩾
0
,
μ
i
⩾
0
\alpha_{i} \geqslant 0, \mu_{i} \geqslant 0
α
i
⩾
0
,
μ
i
⩾
0
首先求
L
(
w
,
b
,
ξ
,
α
,
μ
)
L(w, b, \xi, \alpha, \mu)
L
(
w
,
b
,
ξ
,
α
,
μ
)
对
w
,
b
,
ξ
w, b, \xi
w
,
b
,
ξ
的极小
∇
w
L
(
w
,
b
,
ξ
,
α
,
μ
)
=
w
−
∑
i
=
1
N
α
i
y
i
x
i
=
0
\nabla_{w} L(w, b, \xi, \alpha, \mu)=w-\sum_{i=1}^{N} \alpha_{i} y_{i} x_{i}=0
∇
w
L
(
w
,
b
,
ξ
,
α
,
μ
)
=
w
−
∑
i
=
1
N
α
i
y
i
x
i
=
0
∇
b
L
(
w
,
b
,
ξ
,
α
,
μ
)
=
−
∑
i
=
1
N
α
i
y
i
=
0
\nabla_{b} L(w, b, \xi, \alpha, \mu)=-\sum_{i=1}^{N} \alpha_{i} y_{i}=0
∇
b
L
(
w
,
b
,
ξ
,
α
,
μ
)
=
−
∑
i
=
1
N
α
i
y
i
=
0
∇
ξ
i
L
(
w
,
b
,
ξ
,
α
,
μ
)
=
2
C
ξ
i
−
α
i
−
μ
i
=
0
\nabla_{\xi_{i}} L(w, b, \xi, \alpha, \mu)=2C\xi_{i}-\alpha_{i}-\mu_{i}=0
∇
ξ
i
L
(
w
,
b
,
ξ
,
α
,
μ
)
=
2
C
ξ
i
−
α
i
−
μ
i
=
0
得到：
w
=
∑
i
=
1
N
α
i
y
i
x
i
w=\sum_{i=1}^{N} \alpha_{i} y_{i} x_{i}
w
=
∑
i
=
1
N
α
i
y
i
x
i
∑
i
=
1
N
α
i
y
i
=
0
\sum_{i=1}^{N} \alpha_{i} y_{i}=0
∑
i
=
1
N
α
i
y
i
=
0
2
C
ξ
i
−
α
i
−
μ
i
=
0
2C\xi_{i}-\alpha_{i}-\mu_{i}=0
2
C
ξ
i
−
α
i
−
μ
i
=
0
带入原式
min
w
,
b
,
ξ
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
−
C
∑
i
=
1
N
ξ
i
2
=
−
1
2
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
y
i
y
j
(
x
i
⋅
x
j
)
+
∑
i
=
1
N
α
i
−
C
∑
i
=
1
N
(
α
i
+
μ
i
2
C
)
2
=
−
1
2
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
y
i
y
j
(
x
i
⋅
x
j
)
+
∑
i
=
1
N
α
i
−
1
4
C
∑
i
=
1
N
(
α
i
+
μ
i
)
2
\min _{w, b, \xi} L(w, b, \xi, \alpha, \mu)\\=-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)+\sum_{i=1}^{N} \alpha_{i}-C \sum_{i=1}^{N} \xi_{i}^2\\=-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)+\sum_{i=1}^{N} \alpha_{i}-C \sum_{i=1}^{N} (\frac{\alpha_i+\mu_i}{2C})^2\\=-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)+\sum_{i=1}^{N} \alpha_{i}-\frac{1}{4C}\sum_{i=1}^{N} (\alpha_i+\mu_i)^2
min
w
,
b
,
ξ
L
(
w
,
b
,
ξ
,
α
,
μ
)
=
−
2
1
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
y
i
y
j
(
x
i
⋅
x
j
)
+
∑
i
=
1
N
α
i
−
C
∑
i
=
1
N
ξ
i
2
=
−
2
1
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
y
i
y
j
(
x
i
⋅
x
j
)
+
∑
i
=
1
N
α
i
−
C
∑
i
=
1
N
(
2
C
α
i
+
μ
i
)
2
=
−
2
1
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
y
i
y
j
(
x
i
⋅
x
j
)
+
∑
i
=
1
N
α
i
−
4
C
1
∑
i
=
1
N
(
α
i
+
μ
i
)
2
再对
min
w
,
b
,
ξ
L
(
w
,
b
,
ξ
,
α
,
μ
)
\min _{w, b, \xi} L(w, b, \xi, \alpha, \mu)
min
w
,
b
,
ξ
L
(
w
,
b
,
ξ
,
α
,
μ
)
求
α
\alpha
α
的极大，得对偶问题
m
a
x
α
−
1
2
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
y
i
y
j
(
x
i
⋅
x
j
)
+
∑
i
=
1
N
α
i
−
1
4
C
∑
i
=
1
N
(
α
i
+
μ
i
)
2
max_\alpha \quad -\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)+\sum_{i=1}^{N} \alpha_{i}-\frac{1}{4C}\sum_{i=1}^{N} (\alpha_i+\mu_i)^2
m
a
x
α
−
2
1
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
y
i
y
j
(
x
i
⋅
x
j
)
+
∑
i
=
1
N
α
i
−
4
C
1
∑
i
=
1
N
(
α
i
+
μ
i
)
2
s
.
t
∑
i
=
1
N
α
i
y
i
=
0
s.t\sum_{i=1}^{N} \alpha_{i} y_{i}=0
s
.
t
∑
i
=
1
N
α
i
y
i
=
0
α
i
,
μ
i
>
0
i
=
1
,
2…
N
\alpha_{i}, \mu_{i} > 0\qquad i=1,2…N
α
i
,
μ
i
>
0
i
=
1
,
2
.
.
.
N
习题7.4
题目：
证明内积的正整数幂函数：
K
(
x
,
z
)
=
(
x
⋅
z
)
p
K(x, z)=(x \cdot z)^{p}
K
(
x
,
z
)
=
(
x
⋅
z
)
p
是正定核函数，这里
p
p
p
是正整数，
x
,
z
ϵ
R
n
x,z\epsilon R_{n}
x
,
z
ϵ
R
n
解答：
要证明
K
(
x
,
z
)
K(x,z)
K
(
x
,
z
)
为正定核，有两种想法，一种是证明根据公式（7.26），证明
K
(
x
,
z
)
K(x,z)
K
(
x
,
z
)
满足
K
(
x
,
z
)
=
ϕ
(
x
)
⋅
ϕ
(
z
)
K(x,z)=\phi(x)\cdot \phi(z)
K
(
x
,
z
)
=
ϕ
(
x
)
⋅
ϕ
(
z
)
一种是根据定理7.5，证明对任意
x
i
ϵ
X
,
i
=
1
,
2…
m
,
K
(
x
,
z
)
x_i\epsilon X, i=1,2…m, K(x,z)
x
i
ϵ
X
,
i
=
1
,
2
.
.
.
m
,
K
(
x
,
z
)
对应的
G
r
a
m
Gram
G
r
a
m
矩阵
K
=
[
K
(
x
i
,
x
j
)
]
m
∗
m
K = [K(x_i, x_j)]_{m*m}
K
=
[
K
(
x
i
,
x
j
)
]
m
∗
m
为半正定矩阵。
我用数学归纳法证明
K
(
x
,
z
)
=
ϕ
(
x
)
⋅
ϕ
(
z
)
K(x,z)=\phi(x)\cdot \phi(z)
K
(
x
,
z
)
=
ϕ
(
x
)
⋅
ϕ
(
z
)
（1）
p
=
1
p=1
p
=
1
时
K
(
x
,
z
)
=
x
⋅
z
K(x,z)=x\cdot z
K
(
x
,
z
)
=
x
⋅
z
，取
ϕ
1
(
x
)
=
x
\phi_1(x)=x
ϕ
1
(
x
)
=
x
，满足条件
（2）假设
p
=
k
p=k
p
=
k
时，
K
(
x
,
z
)
K(x,z)
K
(
x
,
z
)
为正定核，即有
K
(
x
,
z
)
=
ϕ
k
(
x
)
⋅
ϕ
k
(
z
)
K(x,z)=\phi_k(x)\cdot \phi_k(z)
K
(
x
,
z
)
=
ϕ
k
(
x
)
⋅
ϕ
k
(
z
)
（3）那么当
p
=
k
+
1
p=k+1
p
=
k
+
1
时
K
(
x
,
z
)
=
(
x
⋅
z
)
k
(
x
⋅
z
)
=
ϕ
k
(
x
)
⋅
ϕ
k
(
z
)
(
x
⋅
z
)
K(x,z) \\= (x\cdot z)^{k}(x\cdot z)\\=\phi_k(x)\cdot \phi_k(z)(x\cdot z)
K
(
x
,
z
)
=
(
x
⋅
z
)
k
(
x
⋅
z
)
=
ϕ
k
(
x
)
⋅
ϕ
k
(
z
)
(
x
⋅
z
)
现在假设
ϕ
k
(
x
)
=
(
f
1
(
x
)
,
f
2
(
x
)
.
.
.
,
f
m
(
x
)
)
T
,
x
=
(
x
1
,
x
2
.
.
.
x
n
)
,
z
=
(
z
1
,
z
2
.
.
.
z
n
)
T
\phi_k(x)=(f_1(x),f_2(x)…,f_m(x))^T,x=(x_1,x_2…x_n),z=(z_1,z_2…z_n)^T
ϕ
k
(
x
)
=
(
f
1
(
x
)
,
f
2
(
x
)
.
.
.
,
f
m
(
x
)
)
T
,
x
=
(
x
1
,
x
2
.
.
.
x
n
)
,
z
=
(
z
1
,
z
2
.
.
.
z
n
)
T
则有
K
(
x
,
z
)
=
(
f
1
(
x
)
f
1
(
z
)
+
f
2
(
x
)
f
2
(
z
)
+
.
.
.
+
f
m
(
x
)
f
m
(
z
)
)
(
x
1
z
1
+
x
2
z
2
+
.
.
.
+
x
n
z
n
)
=
f
1
(
x
)
f
1
(
z
)
(
x
1
z
1
+
x
2
z
2
+
.
.
.
+
x
n
z
n
)
+
f
2
(
x
)
f
2
(
z
)
(
x
1
z
1
+
x
2
z
2
+
.
.
.
+
x
n
z
n
)
+
.
.
.
+
f
m
(
x
)
f
m
(
z
)
(
x
1
z
1
+
x
2
z
2
+
.
.
.
+
x
n
z
n
)
K(x,z)\\=(f_1(x)f_1(z)+f_2(x)f_2(z)+…+f_m(x)f_m(z))(x_1z_1+x_2z_2+…+x_nz_n)\\=f_1(x)f_1(z)(x_1z_1+x_2z_2+…+x_nz_n)+f_2(x)f_2(z)(x_1z_1+x_2z_2+…+x_nz_n)+…+f_m(x)f_m(z)(x_1z_1+x_2z_2+…+x_nz_n)
K
(
x
,
z
)
=
(
f
1
(
x
)
f
1
(
z
)
+
f
2
(
x
)
f
2
(
z
)
+
.
.
.
+
f
m
(
x
)
f
m
(
z
)
)
(
x
1
z
1
+
x
2
z
2
+
.
.
.
+
x
n
z
n
)
=
f
1
(
x
)
f
1
(
z
)
(
x
1
z
1
+
x
2
z
2
+
.
.
.
+
x
n
z
n
)
+
f
2
(
x
)
f
2
(
z
)
(
x
1
z
1
+
x
2
z
2
+
.
.
.
+
x
n
z
n
)
+
.
.
.
+
f
m
(
x
)
f
m
(
z
)
(
x
1
z
1
+
x
2
z
2
+
.
.
.
+
x
n
z
n
)
那么我们就可以取
ϕ
k
+
1
(
x
)
=
(
f
1
(
x
)
x
1
,
f
1
(
x
)
x
2
.
.
.
f
1
(
x
)
x
n
,
f
2
(
x
)
x
1
,
f
2
(
x
)
x
2
,
.
.
.
,
f
2
(
x
)
x
n
,
.
.
.
.
.
.
f
m
(
x
)
x
1
,
f
m
(
x
)
x
2
,
.
.
.
f
m
(
x
)
x
n
)
T
\phi_{k+1}(x)=(f_1(x)x_1, f_1(x)x_2…f_1(x)x_n,f_2(x)x_1,f_2(x)x_2,…,f_2(x)x_n,……f_m(x)x_1,f_m(x)x_2,…f_m(x)x_n)^T
ϕ
k
+
1
(
x
)
=
(
f
1
(
x
)
x
1
,
f
1
(
x
)
x
2
.
.
.
f
1
(
x
)
x
n
,
f
2
(
x
)
x
1
,
f
2
(
x
)
x
2
,
.
.
.
,
f
2
(
x
)
x
n
,
.
.
.
.
.
.
f
m
(
x
)
x
1
,
f
m
(
x
)
x
2
,
.
.
.
f
m
(
x
)
x
n
)
T
有
K
(
x
,
z
)
=
(
x
⋅
z
)
k
+
1
=
ϕ
k
+
1
(
x
)
⋅
ϕ
k
+
1
(
z
)
K(x,z) = (x\cdot z)^{k+1}=\phi_{k+1}(x)\cdot \phi_{k+1}(z)
K
(
x
,
z
)
=
(
x
⋅
z
)
k
+
1
=
ϕ
k
+
1
(
x
)
⋅
ϕ
k
+
1
(
z
)
得证
贴一个先前用半正定矩阵证明的方法，不过这个解法有点问题（关于用证明矩阵半正定的证明方法，有读者有好的想法可以在评论区一起讨论）
根据定理7.5，正定核函数的充要条件是对任意
x
i
ϵ
X
,
i
=
1
,
2…
m
,
K
(
x
,
z
)
x_i\epsilon X, i=1,2…m, K(x,z)
x
i
ϵ
X
,
i
=
1
,
2
.
.
.
m
,
K
(
x
,
z
)
对应的
G
r
a
m
Gram
G
r
a
m
矩阵
K
=
[
K
(
x
i
,
x
j
)
]
m
∗
m
K = [K(x_i, x_j)]_{m*m}
K
=
[
K
(
x
i
,
x
j
)
]
m
∗
m
为半正定矩阵
对任意
c
1
,
c
2
,
.
.
.
,
c
m
ϵ
R
c_1,c_2,…,c_m\epsilon R
c
1
,
c
2
,
.
.
.
,
c
m
ϵ
R
∑
i
,
j
=
1
m
c
i
c
j
K
(
x
i
,
x
j
)
=
∑
i
,
j
=
1
m
c
i
c
j
(
x
i
⋅
x
j
)
p
=
∑
i
=
1
m
(
c
i
x
i
⋅
c
j
x
j
)
(
x
i
⋅
x
j
)
p
−
1
\sum^m_{i,j=1}c_{i}c_jK(x_{i},x_j)\\=\sum^m_{i,j=1}c_{i}c_j(x_i\cdot x_j)^p\\=\sum^m_{i=1}(c_ix_i\cdot c_jx_j)(x_{i}\cdot x_{j})^{p-1}
∑
i
,
j
=
1
m
c
i
c
j
K
(
x
i
,
x
j
)
=
∑
i
,
j
=
1
m
c
i
c
j
(
x
i
⋅
x
j
)
p
=
∑
i
=
1
m
(
c
i
x
i
⋅
c
j
x
j
)
(
x
i
⋅
x
j
)
p
−
1
先来看前面一部分
(
c
i
x
i
⋅
c
j
x
j
)
(c_ix_i\cdot c_jx_j)
(
c
i
x
i
⋅
c
j
x
j
)
∑
i
=
1
m
(
c
i
x
i
⋅
c
j
x
j
)
=
(
∑
i
=
1
m
c
i
x
i
)
⋅
(
∑
j
=
1
m
c
j
x
j
)
=
∣
∣
∑
i
=
1
m
c
i
x
i
∣
∣
2
≥
0
\sum^m_{i=1}(c_ix_i\cdot c_jx_j)\\=(\sum^m_{i=1}c_ix_i)\cdot (\sum^m_{j=1}c_jx_j)\\=||\sum^m_{i=1}c_ix_i||^2\geq 0
∑
i
=
1
m
(
c
i
x
i
⋅
c
j
x
j
)
=
(
∑
i
=
1
m
c
i
x
i
)
⋅
(
∑
j
=
1
m
c
j
x
j
)
=
∣
∣
∑
i
=
1
m
c
i
x
i
∣
∣
2
≥
0
再看后面一部分
(
x
i
⋅
x
j
)
p
−
1
p
≥
0
(x_{i}\cdot x_{j})^{p-1}\quad p\geq 0
(
x
i
⋅
x
j
)
p
−
1
p
≥
0
对于
∑
i
=
1
m
(
x
i
⋅
x
j
)
=
(
∑
i
=
1
m
x
i
)
⋅
(
∑
i
=
1
m
x
i
)
=
∣
∣
∑
i
=
1
m
x
i
∣
∣
2
≥
0
\sum^m_{i=1}(x_{i}\cdot x_{j})\\=(\sum^m_{i=1}x_{i})\cdot (\sum^m_{i=1}x_{i})\\=||\sum^m_{i=1}x_{i}||^2\quad \geq 0
∑
i
=
1
m
(
x
i
⋅
x
j
)
=
(
∑
i
=
1
m
x
i
)
⋅
(
∑
i
=
1
m
x
i
)
=
∣
∣
∑
i
=
1
m
x
i
∣
∣
2
≥
0
而对于
∑
i
=
1
m
a
i
b
i
s
.
t
∑
i
=
1
m
a
i
,
∑
i
=
1
m
b
i
≥
0
\sum_{i=1}^ma_ib_i\\s.t\sum^m_{i=1}a_i,\sum^m_{i=1}b_i\quad \geq0
∑
i
=
1
m
a
i
b
i
s
.
t
∑
i
=
1
m
a
i
,
∑
i
=
1
m
b
i
≥
0
一定有
∑
i
=
1
m
a
i
b
i
≥
0
\sum_{i=1}^ma_ib_i\geq0
∑
i
=
1
m
a
i
b
i
≥
0
所以有
∑
i
=
1
m
(
c
i
x
i
⋅
c
j
x
j
)
(
x
i
⋅
x
j
)
p
−
1
≥
0
\sum^m_{i=1}(c_ix_i\cdot c_jx_j)(x_{i}\cdot x_{j})^{p-1}\geq0
∑
i
=
1
m
(
c
i
x
i
⋅
c
j
x
j
)
(
x
i
⋅
x
j
)
p
−
1
≥
0