考虑训练集 D = {(x1, y1), · · · , (xm, ym)}, ym ∈ {−1, +1}, 参照《机器学习》第八章图 8.3 的变量定义, 我们将证明如下定理: AdaBoost 迭代 T 轮后返回的分类器 f , 经验误差满足 ˆRD (f ) = 1 m m∑ i=1 1yi f (xi )≤0 ≤ exp [ −2 T∑ t=1 ( 1 2 − εt )2] . 进一步地, 若对于任意的 t ∈ [T ], γ ≤ ( 1 2 − εt), 那么有 ˆRD (f ) ≤ exp(−2γ2T ). (1) [5pts] 请证明数据分布 Dt 的调整过程满足: Dt+1(x) = e−yi ∑t s=1 αs hs (x) m ∏t s=1 Zs , ∀t ∈ [T ]. (2) [5pts] 请证明规范化因子 Zt 与基学习器误差 εt 的关系: Zt = 2√εt(1 − εt), ∀t ∈ [T ]. (3) [5pts] 利用前两问的结论, 完成题给定理的证明. (提示: 使用不等式 I(u ≤ 0) ≤ exp (−u), ∀u ∈ R)

(1) 我们需要证明对于任意样本 xi ，有 Dt+1(xi) = e^-yi(f(xi)) / Zt ，其中 f 是第 T 轮迭代后的分类器，即 f(x) = sign(∑t αt ht(x)) 。

首先，我们可以将 Dt+1(x) 的式子展开：

Dt+1(xi) = (1/Zt) * e^(-yi * f(xi)) * ∏t=1^T Zt

接下来，我们需要证明 e^(-yi * f(xi)) = ∏t=1^T (Zt ^ (-αt * y * ht(xi))) 。

我们对 T 进行归纳。当 t = 1 时，由于初始时 Dt(x) = 1/m ，所以 Z1 = 2 * sqrt(ε1 * (1 - ε1)) = 2 * sqrt((1/2) * (1 - (1/2))) = 1 ，因此：

e^(-y1 * f(x1)) = e^(-y1 * α1 * h1(x1))
= e^(α1) (若 y1 = h1(x1))
= e^(-α1) (若 y1 ≠ h1(x1))

而 Z1 ^ (-α1 * y1 * h1(x1)) = 1 ^ (-α1 * y1 * h1(x1)) = 1 ，因此上式成立。

假设对于 t = 1, 2, ..., T-1，上式成立。考虑 t = T 时，我们有：

e^(-yi * f(xi)) = e^(-yi * ∑t=1^T αt * ht(xi))
= e^(-yi * αT * hT(xi)) * e^(-yi * ∑t=1^(T-1) αt * ht(xi))

由于 e^(-yi * ∑t=1^(T-1) αt * ht(xi)) 可以通过归纳假设表示为 ∏t=1^(T-1) (Zt ^ (-αt * y * ht(xi))) ，因此我们只需要考虑 e^(-yi * αT * hT(xi)) 。

当 yT * hT(xi) = 1 时，我们有：

e^(-yi * αT * hT(xi)) = e^(-αT) = ZT ^ (-αT * yT * hT(xi))

当 yT * hT(xi) = -1 时，我们有：

e^(-yi * αT * hT(xi)) = e^(αT) = ZT ^ (-αT * yT * hT(xi))

因此，无论 yT * hT(xi) 的取值如何，我们都有：

e^(-yi * f(xi)) = e^(-yi * αT * hT(xi)) * ∏t=1^(T-1) (Zt ^ (-αt * y * ht(xi)))

接下来，我们只需要将上式代回 Dt+1(x) 的式子，即可得到：

Dt+1(xi) = e^-yi(f(xi)) / Zt

证毕。

(2) 我们需要证明 Zt = 2√εt(1 − εt) 。

根据定义，我们有：

Zt = ∑i=1^m Dt(xi) * exp(-αt * yi * ht(xi))

我们将正负样本分开考虑。对于正样本 xi ，有 yi = 1 ，因此：

Zt(+) = ∑i:yi=1 Dt(xi) * exp(-αt * ht(xi))
= ∑i:yi=1 (Dt(xi) * exp(-αt)) (若 ht(xi) = -1)
(Dt(xi) * exp(αt)) (若 ht(xi) = 1)
= exp(-αt) * εt + exp(αt) * (1-εt)
= 2 * sqrt(εt * (1-εt))

对于负样本 xi ，有 yi = -1 ，因此：

Zt(-) = ∑i:yi=-1 Dt(xi) * exp(αt * ht(xi))
= ∑i:yi=-1 (Dt(xi) * exp(-αt)) (若 ht(xi) = -1)
(Dt(xi) * exp(αt)) (若 ht(xi) = 1)
= exp(-αt) * (1-εt) + exp(αt) * εt
= 2 * sqrt(εt * (1-εt))

因此，我们得到 Zt = Zt(+) + Zt(-) = 2 * sqrt(εt * (1-εt)) 。

证毕。

(3) 我们需要证明 ˆRD (f) = 1/m ∑i=1^m 1yi f(xi) ≤ 0 ≤ exp[-2 * ∑t=1^T (1/2 - εt)^2] 。

根据定义，我们有：

1/m ∑i=1^m 1yi f(xi) = 1/m ∑i=1^m 1yi ∑t=1^T αt ht(xi)

= ∑t=1^T αt * (1/m ∑i=1^m 1yi ht(xi))

= ∑t=1^T αt * εt

= εt

因此，我们只需要证明 εt ≤ exp[-2 * ∑t=1^T (1/2 - εt)^2] 。

考虑函数 f(x) = exp[-2 * (1/2 - x)^2] ，我们需要证明 εt ≤ f(εt) 对于所有 t 成立。

首先，我们有 f'(x) = -4 * x + 2 ，因此当 x = 1/2 时，f'(x) = 0 ，f(x) 取得最大值。同时，当 x = 0 或 x = 1 时，f(x) = 0 。因此，f(x) 是一个开口向下的单峰函数，其最大值为 f(1/2) = 1 。

又因为 εt ∈ [0, 1/2] ，因此我们有：

εt ≤ f(εt) = exp[-2 * (1/2 - εt)^2]

因此，我们得到：

εt ≤ exp[-2 * (1/2 - εt)^2] ≤ 1

证毕。