考虑训练集 D = {(x1, y1), · · · , (xm, ym)}, ym ∈ {−1, +1}, 参照《机器学习》第八章图 8.3 的变量定义，请证明数据分布$D_t$的调整过程满足: \begin{align*} \mathcal{D}_{t+1}(\x) = \frac{e^{-y_i \sum_{s=1}^t \alpha_s h_s(\x)}}{m \prod_{s=1}^t Z_s}, \quad \forall t \in [T]. \end{align*}

我们需要证明对于所有的 $t \in [T]$ 和 $\x \in \mathcal{X}$，都有:
$$\mathcal{D}_{t+1}(\x) = \frac{e^{-y_i \sum_{s=1}^t \alpha_s h_s(\x)}}{m \prod_{s=1}^t Z_s}$$

我们首先回顾 AdaBoost 算法中 $\mathcal{D}_t$ 的更新过程，即：
$$\mathcal{D}_t(i) = \frac{\mathcal{D}_{t-1}(i) e^{-\alpha_t y_i h_t(\x_i)}}{Z_t}$$
其中 $Z_t$ 是规范化因子，满足 $\sum_{i=1}^m \mathcal{D}_t(i) = 1$。

我们将上式中的 $i$ 换成 $\x$，并将 $\mathcal{D}_t(i)$ 换成 $\mathcal{D}_t(\x)$，则有：
$$\mathcal{D}_t(\x) = \frac{\sum_{i=1}^m \mathcal{D}_{t-1}(\x_i) e^{-\alpha_t y_i h_t(\x_i)} \mathbb{I}(\x=\x_i)}{Z_t}$$
其中 $\mathbb{I}(\cdot)$ 是指示函数，当 $\x=\x_i$ 时为 $1$，否则为 $0$。

我们将 $\mathcal{D}_{t-1}$ 带入上式，有：
$$\mathcal{D}_t(\x) = \frac{\sum_{i=1}^m \frac{e^{-y_i \sum_{s=1}^{t-1} \alpha_s h_s(\x_i)}}{m \prod_{s=1}^{t-1} Z_s} e^{-\alpha_t y_i h_t(\x_i)} \mathbb{I}(\x=\x_i)}{Z_t}$$
将 $Z_t$ 展开，有：
$$\begin{aligned} \mathcal{D}_t(\x) &= \frac{1}{m \prod_{s=1}^{t-1} Z_s} \sum_{i=1}^m e^{-y_i \sum_{s=1}^{t-1} \alpha_s h_s(\x_i)} e^{-\alpha_t y_i h_t(\x_i)} \mathbb{I}(\x=\x_i) \\ &= \frac{1}{m \prod_{s=1}^{t-1} Z_s} \sum_{i=1}^m e^{-y_i \sum_{s=1}^t \alpha_s h_s(\x_i)} \mathbb{I}(\x=\x_i) \\ &= \frac{1}{m \prod_{s=1}^{t} Z_s} \sum_{i=1}^m e^{-y_i \sum_{s=1}^t \alpha_s h_s(\x_i)} \mathbb{I}(\x=\x_i) \\ &= \frac{e^{-y_i \sum_{s=1}^t \alpha_s h_s(\x)}}{m \prod_{s=1}^t Z_s} \end{aligned}$$
其中第二个等号是因为 $\mathbb{I}(\x=\x_i)$ 只在 $\x=\x_i$ 时为 $1$，其他时候都为 $0$，所以可以将 $t$ 个指标的指数相加合并为一个指标的指数。第三个等号是因为 $Z_t = \sum_{i=1}^m e^{-y_i \sum_{s=1}^t \alpha_s h_s(\x_i)}$。

因此，我们证明了数据分布 $\mathcal{D}_t$ 的调整过程满足：
$$\mathcal{D}_{t+1}(\x) = \frac{e^{-y_i \sum_{s=1}^t \alpha_s h_s(\x)}}{m \prod_{s=1}^t Z_s}$$