北京大学 wlw机器学习2022春季期末试题分析
- 前言
- 新的开始
- 第一题
- 第二题
- 第三题
前言
你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Markdown的基本语法知识。
新的开始
第一题
利用Lagrange Dueling，即可计算。
L
(
x
,
λ
1
,
λ
2
)
=
b
T
x
+
λ
1
T
(
c
−
A
x
)
−
λ
2
T
x
∂
L
∂
x
=
b
T
−
λ
1
T
A
−
λ
2
T
=
0
L(x,\lambda_1,\lambda_2)=b^Tx+\lambda_1^T(c-Ax)-\lambda^T_2 x\\\frac{\partial L}{\partial x}=b^T-\lambda_1^TA-\lambda_2^T=0
L(x,λ1,λ2)=bTx+λ1T(c−Ax)−λ2Tx∂x∂L=bT−λ1TA−λ2T=0
故最终对偶形式为：
m
a
x
λ
1
,
λ
2
−
λ
1
T
c
s
.
t
.
b
T
−
λ
1
T
A
−
λ
2
T
=
0
λ
1
T
≥
0
λ
2
T
≥
0
max_{\lambda_1,\lambda_2}-\lambda_1^Tc\\ s.t. \quad b^T-\lambda_1^TA-\lambda_2^T=0\\ \lambda_1^T\geq0\\ \lambda_2^T\geq0
maxλ1,λ2−λ1Tcs.t.bT−λ1TA−λ2T=0λ1T≥0λ2T≥0
第二题
这里我个人认为要利用定义，还有就是要注意，这里提到的
c
1
c_1
c1,
c
2
c_2
c2是存在，而不是任意。
L
e
t
M
d
(
X
,
ϵ
)
=
m
,
∃
x
1
,
x
2
,
.
.
.
,
x
m
∈
X
,
∀
i
,
j
∈
[
m
]
,
i
≠
j
,
d
(
x
i
,
x
j
)
≥
ϵ
G
e
t
x
m
+
1
∈
X
,
d
(
x
i
,
x
m
+
1
)
<
ϵ
S
o
c
2
≥
1
,
N
d
(
X
,
ϵ
/
c
2
)
=
M
d
(
X
,
ϵ
/
c
2
)
≥
M
d
(
X
,
ϵ
)
Let \quad\mathcal{M}_d(\mathcal{X}, \epsilon)=m,\\ \exist x_1,x_2,...,x_m\in\mathcal{X}, \forall i,j\in[m], i\neq j, d(x_i ,x_j)\geq \epsilon\\ Get\quad x_{m+1}\in\mathcal{X}, d(x_i,x_{m+1})<\epsilon\\ So \quad c_2\geq 1, \mathcal{N}_d(\mathcal{X},\epsilon/c_2)=\mathcal{M}_d(\mathcal{X},\epsilon/c_2)\geq \mathcal{M}_d(\mathcal{X},\epsilon)
LetMd(X,ϵ)=m,∃x1,x2,...,xm∈X,∀i,j∈[m],i=j,d(xi,xj)≥ϵGetxm+1∈X,d(xi,xm+1)<ϵSoc2≥1,Nd(X,ϵ/c2)=Md(X,ϵ/c2)≥Md(X,ϵ)
对左半部分证明同理。
第三题
（1）思路，根据题目描述，要想证明两个分类器不同，由于不知道算法A，故只能通过比较误差进行，题目中提到了弱学习性假设，故考虑证明加权误差：
R
^
t
+
1
(
h
t
)
=
∑
D
t
+
1
(
i
)
I
(
y
i
≠
h
t
(
x
i
)
)
=
∑
D
t
(
i
)
∗
e
x
p
(
−
y
i
α
t
h
t
(
x
i
)
)
Z
t
I
(
y
i
≠
h
t
(
x
i
)
)
=
∑
D
t
(
i
)
I
(
y
i
≠
h
t
(
x
i
)
)
e
x
p
(
−
y
i
α
t
h
t
(
x
i
)
)
Z
t
\hat{R}_{t+1}(h_t)=\sum D_{t+1}(i)I(y_i\neq h_t(x_i))\\ =\sum \frac{D_t(i)*exp(-y_i\alpha_t h_t(x_i))}{Z_t }I(y_i\neq h_t(x_i))\\ =\sum D_t(i)I(y_i\neq h_t(x_i))\frac{exp(-y_i\alpha_t h_t(x_i))}{Z_t }
R^t+1(ht)=∑Dt+1(i)I(yi=ht(xi))=∑ZtDt(i)∗exp(−yiαtht(xi))I(yi=ht(xi))=∑Dt(i)I(yi=ht(xi))Ztexp(−yiαtht(xi))
![Required request parameter ‘ids‘ for method parameter type List is not present]](https://img-blog.csdnimg.cn/direct/004d2160d08e4069b156d90ae525c0b9.png)
