學習理論：代理損失函數(shù)的泛化界與Rademacher復(fù)雜度

在之前的博客中我們提到過，設(shè)l為在標簽Y上定義的0-1多分類棄權(quán)損失的代理損失，則我們可以在此基礎(chǔ)上進一步定義棄權(quán)代理損失L。在這篇博客中，讓我們把注意力轉(zhuǎn)移一個新的方向——代理損失函數(shù)的泛化誤差界（generalization error gap）。差值R_L(hat{h}) - widehat{R}_L(hat{h})被稱為泛化差距（generalization gap），刻畫了學習算法輸出假設(shè)的泛化能力。證明學習算法的泛化界（generalization bound）即為證明其泛化差距被某個大致形如epsilon = O(C(H)/m)的項給界定，其中C(H)為假設(shè)空間H的模型復(fù)雜度，m為樣本個數(shù)。按照經(jīng)典統(tǒng)計學習理論，一般假設(shè)空間H的模型復(fù)雜度越低，樣本個數(shù)m越多，學習算法的泛化性能越好。證明泛化界的問題可以轉(zhuǎn)化為證明經(jīng)驗過程有界。

3月份以來的科研基本圍繞推導代理損失函數(shù)的一致界展開，證明現(xiàn)已基本完工（關(guān)于代理損失函數(shù)的一致界的介紹可參見之前的博客《學習理論：預(yù)測器-拒絕器多分類棄權(quán)學習》）。導師建議我可以的話把泛化界也一起證了╰(￣▽￣)╭。由于認識有搞過泛化的朋友，許多東西盡管沒有親自上手做但早已“耳濡目染”了，比如集中不等式這些。這篇博客旨在就代理損失函數(shù)的泛化界證明流程進行初步的介紹，并穿插介紹一些學習理論、高維概率中常用的概念。

1 導引

首先，回顧一下多分類棄權(quán)學習的基本設(shè)置。假設(shè)帶標簽樣本集$S=((x_1, y_1), \cdots, (x_m, y_m))$中的每個樣本$(x_i, y_i)$都獨立同分布地采自$\mathcal{D}$，記$S\sim \mathcal{D}^m$，且有$(x_i, y_i)\in \mathcal{X}\times \mathcal{Y}$（標簽$\mathcal{Y} = \{1, \cdots, n\}$（$n\geqslant 2$））。

針對多分類問題的預(yù)測器-拒絕器棄權(quán)損失^[1]$L_{\text{abst}}$定義如下（這里默認采用單階段的訓練設(shè)置）：

\[L_{\text{abst}}(h, r, x, y) = \underbrace{\mathbb{I}_{\text{h}(x) \neq y}\mathbb{I}_{r(x) > 0}}_{\text{不棄權(quán)}} + \underbrace{c \mathbb{I}_{r(x)\leqslant 0}}_{\text{棄權(quán)}} \]

其中$(h, r)\in \mathcal{H}\times\mathcal{R}$為預(yù)測器-拒絕器對（$\mathcal{H}$和$\mathcal{R}$為兩個從$\mathcal{X}$到$\mathbb{R}$的函數(shù)構(gòu)成的函數(shù)族），$\text{h}(x) = \underset{y\in \mathcal{Y}}{\text{arg max}}\space {h(x)}_y$直接輸出實例$x$的預(yù)測標簽。假設(shè)$c\in (0, 1)$為一個常數(shù)。

在之前的博客中我們提到過，設(shè)$\mathcal{l}$為在標簽$\mathcal{Y}$上定義的0-1多分類損失的代理損失，則我們可以在此基礎(chǔ)上進一步定義棄權(quán)代理損失$L$：

\[L(h, r, x, y) = \mathcal{l}(h, x, y)\phi(-\alpha r(x)) + c \phi(\beta r(x)) \]

不過這里為了進一步簡化分析，我們規(guī)定這里的拒絕器$r$不再是學出來的，而是直接根據(jù)下列公式計算而得^[2]：

\[r(x) = \max_{y\in \mathcal{Y}} \left[\Psi^{-1}(h(x))\right]_y - (1 - c) \]

這里$\Psi: [0, 1]^n\rightarrow \mathbb{R^n}$定義為將數(shù)據(jù)的條件概率分布向量$\left(\begin{matrix} p(Y=1\mid x)\\ \vdots\\ p(Y=n\mid x) \end{matrix}\right)\in [0, 1]^n$映射到最優(yōu)預(yù)測器輸出向量$\left(\begin{matrix} h(x)_1\\ \vdots\\ h(x)_n \end{matrix}\right)\in \mathbb{R}^n$的函數(shù)。那么$\Psi^{-1}$就反之，根據(jù)最優(yōu)預(yù)測器輸出向量給出數(shù)據(jù)條件概率分布向量的預(yù)測值。將$r(x)$與貝葉斯最優(yōu)拒絕器$r^*(x) = \max_{y\in \mathcal{Y}}p(y\mid x) - (1 - c)$的公式進行對比可以更好地對其進行理解）。

于是，棄權(quán)代理損失函數(shù)可以直接等價于在標簽$\mathcal{Y}$上定義的0-1多分類損失的代理損失$\mathcal{l}$，下面我們以一對多（one-versus-all, OVA） 損失為例進行分析：

\[L(h, x, y) = \mathcal{l}(h, x, y) = \phi(h(x)_y) + \sum_{y^{\prime}\neq y}\phi(-h(x)_{y^{\prime}}) \]

其中$\phi(\cdot)$為間隔損失（margin loss）（做為$z \mapsto \mathbb{I}_{z \leqslant 0}$的上界），可以設(shè)置為$\phi(z) = \exp(-z)$、$\phi(z) = \log(1 + \exp(-z))$等等。對于一對多損失而言，$\Psi^{-1}$的計算公式為$\left[\Psi^{-1}(h(x))\right]_y = \frac{\phi^{\prime}(-h(x))_y}{\phi^{\prime}(-h(x))_y + \phi^{\prime}(h(x))_y}$。

對于目標損失$L_{\text{abst}}$和代理損失$L$而言，可分別定義$L_{\text{abst}}$-期望棄權(quán)損失$R_{L_{\text{abst}}}(h, r)$（也即目標損失函數(shù)的泛化誤差）和$L$-期望棄權(quán)代理損失$R_{L}(h, r)$（也即代理損失函數(shù)的泛化誤差）如下：

\[R_{L_{\text{abst}}}(h, r) = \mathbb{E}_{(x, y)\sim \mathcal{D}}\left[L_{\text{abst}}(h, r, x, y)\right], \quad R_{L}(h) = \mathbb{E}_{(x, y)\sim \mathcal{D}}\left[L(h, x, y)\right] \]

$R_{L_{\text{abst}}}(h, r)$和$R_{L}(h, r)$在所有可測函數(shù)構(gòu)成的集合上取得的下確界分別記為：

\[R^*_{L_\text{abst}} = \inf_{h, r}R_{L_{\text{abst}}}(h, r), \quad R_{L}^* = \inf_{h}R_{L}(h) \]

這被稱為貝葉斯最優(yōu)誤差（Bayes-optimal error），記$h^* = \text{arg min}_{h}R_{L}(h)$。

貝葉斯一致性（Bayes-consistency） ^[3][4]定義這樣一種損失函數(shù)，這種損失函數(shù)能夠確保風險最小化的預(yù)測器能夠成為貝葉斯最優(yōu)分類器。進一步地，代理損失函數(shù)的貝葉斯一致性是指隨著訓練數(shù)據(jù)規(guī)模$m\rightarrow \infty$，基于訓練樣本學到的一系列輸出函數(shù)$\hat{h}_1, \hat{h}_2, \cdots, \hat{h}_m$滿足下列關(guān)系：

\[R_L(\hat{h}_m) \xrightarrow{m\rightarrow \infty} R_L^{*} \quad \Longrightarrow \quad R_{L_{\text{abst}}}(\hat{h}, r) \xrightarrow{m\rightarrow \infty} R_{L_{\text{abst}}}^{*} \]

從上式中可以看到，想要刻畫代理損失函數(shù)的貝葉斯一致性，就需要界定$R_L(\hat{h}) - R_L^{*}$，而這項差距可以進一步做如下分解^[5]：

\[R_L(\hat{h}) - R_L^{*} = \underbrace{\left(R_L(\hat{h}) - R_L^*(\mathcal{H})\right)}_{\text{excess error}\geqslant 0} + \underbrace{\left(R_L^*(\mathcal{H}) - R_L^{*}\right)}_{\text{approximation error}\geqslant 0} \]

其中$R_L^*(\mathcal{H}) = \inf_{\mathcal{h\in H}}R_L(h)$為假設(shè)類最優(yōu)（best-in-class）誤差，對應(yīng)的假設(shè)類最優(yōu)假設(shè)記為$h^{\circ}$，假設(shè)類最優(yōu)誤差也可以記為$R_L(h^{\circ})$

第一項差值被稱為超額誤差（excess error），它衡量了一個模型和假設(shè)類最優(yōu)的模型之間的差距。
第二項差值是逼近誤差（approximation error），代表了假設(shè)類$\mathcal{H}$在多大程度上涵蓋了貝葉斯最優(yōu)分類器$h^*$，刻畫了模型的表達能力。

注當定義超額誤差時，往往需要定義是超過什么的誤差。這里默認超額誤差以假設(shè)類的最優(yōu)誤差為基準，即$R_L(\hat{h}) - \inf_{\mathcal{h\in H}}R_L(h)$；也有論文定義的超額誤差以貝葉斯最優(yōu)誤差為基準，即$R_L(\hat{h}) - R_L^*$，然后將我們上面所定義的超額誤差稱為估計誤差（estimation error） ^[2][6]。

若假設(shè)假設(shè)類和拒絕函數(shù)類為所有可測函數(shù)構(gòu)成的集合，即$\mathcal{H} = \mathcal{H}_{\text{all}}, \mathcal{R} = \mathcal{R}_{\text{all}}$，則上式中第二項逼近誤差等于0，于是若證明以下代理損失函數(shù)的超額誤差界（excess error bound） 成立，則可以直接通過取極限操作得到貝葉斯一致性：

\[\underbrace{R_{L_{\text{abst}}}(h, r) - R_{L_{\text{abst}}}^*(\mathcal{H}_{\text{all}}, \mathcal{R}_{\text{all}})}_{\text{target excess error}} \leqslant \Gamma \underbrace{\left(R_L(h) - R_L^*(\mathcal{H}_{\text{all}})\right)}_{\text{surrogate excess error}} \]

其中$R_L^*(\mathcal{H}_{\text{all}}) = \inf_{\mathcal{h}}R_L(h) = R_L^{*}$。$\Gamma: \mathbb{R}_{+}\rightarrow \mathbb{R}_{+}$為滿足屬性$\lim_{t\rightarrow 0^{+}}\Gamma (t) = 0$的非遞減函數(shù)。這也是我們在博客《學習理論：預(yù)測器-拒絕器多分類棄權(quán)學習》）中提到過的內(nèi)容。在這篇博客中，讓我們把注意力轉(zhuǎn)移一個新的方向——代理損失函數(shù)的泛化誤差界（generalization error gap）。

2 泛化誤差界

機器學習理論的一大目標就是最小化超額誤差$R_L(\hat{h}) - R_L^{*}(\mathcal{H})$，然而$\hat{h}$做為$h^*$的估計值，是最小化如下所示的經(jīng)驗誤差（泛化誤差的近似）^[7]來獲得的：

\[\widehat{R}_L(h) = \mathbb{E}_{(x, y)\sim S}\left[L(h, x, y)\right] = \frac{1}{m}\sum_{i=1}^m L(h, x_i, y_i) \]

其中$(x, y)\sim S$表示$(x, y)$采自樣本集$S$定義的經(jīng)驗分布。這也就是說$\hat{h} = \inf_{h\in \mathcal{H}}\widehat{R}_{L}(h)$。這也就意味著$\hat{h}$并不能保證最小化泛化誤差$R_L(\hat{h})$，自然也就無法保證最小化超額誤差了。

于是，考慮對超額誤差進行進一步的分解^[5]：

\[\begin{aligned} & R_L(\hat{h}) - R_L^{*}(\mathcal{H}) \\ &= R_L(\hat{h}) - R_L(h^{\circ}) \quad (h^{\circ} = \text{arg min}_{\mathcal{h\in H}}R_L(h))\\ &= \underbrace{\left(R_L(\hat{h}) - \widehat{R}_L(\hat{h})\right)}_{\text{generalization gap}\geqslant 0} + \underbrace{\left(\widehat{R}_L(\hat{h}) - \widehat{R}_L(h^{\circ})\right)}_{\text{training error} \leqslant 0 \text{ or } \geqslant 0} + \underbrace{\left(\widehat{R}_L(h^{\circ}) - R_L(h^{\circ})\right)}_{\text{small term} \geqslant 0} \end{aligned} \]

第一項差值$R_L(\hat{h}) - \widehat{R}_L(\hat{h})$被稱為泛化差距（generalization gap），刻畫了學習算法輸出假設(shè)的泛化能力。證明學習算法的泛化界（generalization bound） 即為證明對任意$h\in \mathcal{H}$，$R_L(h) - \widehat{R}_L(h)$依概率被某個大致形如$\epsilon = \mathcal{O}(\frac{\mathcal{C}(\mathcal{H})}{m})$的項給界定，其中$\mathcal{C}(\mathcal{H})$為假設(shè)空間$\mathcal{H}$的模型復(fù)雜度，$m$為樣本個數(shù)。按照經(jīng)典統(tǒng)計學習理論，一般假設(shè)空間$\mathcal{H}$的模型復(fù)雜度越低，樣本個數(shù)$m$越多，學習算法的泛化性能越好。

注上述理論在深度學習中不一定適用。在深度學習理論中會出現(xiàn)所謂的雙下降（double descent），過參數(shù)化模型的泛化性能也可能很好，感興趣的同學可以查看B站南大大佬的視頻JOJO想：深度學習中的泛化理論（9）良性過擬合^[8]。
第二項差值$\underbrace{\widehat{R}_L(\hat{h}) - \widehat{R}_L(h^{\circ})}_{\leqslant 0} \leqslant \underbrace{\widehat{R}_L(\hat{h}) - \inf_{h}\widehat{R}_L(h)}_{\geqslant 0}$和模型的訓練誤差有關(guān)，刻畫了訓練算法的優(yōu)化能力。當$\hat{h}$能夠最小化訓練誤差，也即$\widehat{R}_L(\hat{h}) = \inf_{h}\widehat{R}_L(h)$時，這一項一定$\leqslant 0$。
第三項差值$\widehat{R}(h^{\circ}) - R(h^{\circ})$一般是一個很小的項，我們稱之為“小項”，也可以被界定。

觀察上述分解，可以發(fā)現(xiàn)泛化差距$R_L(\hat{h}) - \widehat{R}_L(\hat{h})$和“小項”$\widehat{R}(h^{\circ}) - R(h^{\circ})$具有相似的形式，都可以寫成$R_L(\cdot)$和$\widehat{R}(\cdot)$之間關(guān)于某個假設(shè)$h$的差值。而這個差值可以被界定如下（以泛化差距為例，“小項”同理）：

\[\begin{aligned} R_L(\hat{h}) - \widehat{R}_L(\hat{h}) \leqslant \sup_{h\in \mathcal{H}}\lvert \widehat{R}_L(h) - R_L(h)\lvert \end{aligned} \]

若能證明當$n\rightarrow \infty$時，$\sup_{h\in \mathcal{H}}\lvert \widehat{R}(h) - R_L(h)\rvert\rightarrow 0$（比如該上確界被某個大致形如$\epsilon = \mathcal{O}(\frac{\mathcal{C}(\mathcal{H})}{\sqrt{m}})$或$\mathcal{O}(\frac{\mathcal{C}(\mathcal{H})}{m})$的項給控制），則我們稱假設(shè)類$\mathcal{H}$是一致收斂（uniform convergence） 的^[9][10]。

注注意這里一致收斂的“一致”對應(yīng)的英文是“uniform”，而我們之前提到過的損失函數(shù)一致性的“一致性”對應(yīng)的英文是“consistency”。

$\sup_{h\in \mathcal{H}}\lvert \widehat{R}_L(h) - R_L(h)\lvert$可以視為假設(shè)$h\in \mathcal{H}$做為下標索引的隨機過程的量綱（magnitude），這種隨機過程稱為經(jīng)驗過程^[11]。

定義 1 （經(jīng)驗過程）假設(shè)類$\mathcal{H}$上的經(jīng)驗過程（empirical process）$\left(X_h\right)_{h\in \mathcal{H}}$定義為：

\[X_{h} := \widehat{R}_L(h) - R_L(h) \]

證明泛化界的問題可轉(zhuǎn)化為證明經(jīng)驗過程有界（比如$\sup_{h\in \mathcal{H}}\lvert \widehat{R}_L(h) - R_L(h)\lvert < \epsilon = \mathcal{O}(\frac{\mathcal{C}(\mathcal{H})}{\sqrt{m}})$）的問題。

3 經(jīng)驗過程的Rademacher復(fù)雜度上界

對于一對多代理損失$L(h, x, y) = \phi\left(h(x)_y\right) + \sum_{y^{\prime}\neq y}\phi\left(-h(x)_{y^{\prime}}\right)$，以及定義在其上的經(jīng)驗過程$X_{h} := \widehat{R}_L(h) - R_L(h), h\in \mathcal{H}$，我們有下列定理^[2]成立：

定理 1 對任意$\delta > 0$，至少以$1 - \delta$的概率有

\[\sup_{h\in \mathcal{H}}\lvert \widehat{R}_L(h) - R_L(h)\lvert \leqslant 4 n C_{\phi} \mathfrak{R}_S(\mathcal{\Pi_1(H)}) + M_{\phi} \sqrt{\frac{8\log \frac{2}{\delta}}{m}} \]

其中$n$為標簽類別數(shù)，$C_{\phi}$為函數(shù)$\phi(\cdot)$的Lipschitz常數(shù)（假設(shè)$\phi(\cdot)$滿足Lipschitz連續(xù)），$\mathfrak{R}(\mathcal{H}\circ \mathcal{S})$為定義在樣本集$S$上的假設(shè)類$\Pi_1(\mathcal{H}) = \left\{x \mapsto h(x)_y \mid y\in \mathcal{Y}, h\in \mathcal{H}\right\}$的Rademacher復(fù)雜度，$M_{\phi} = \sup_{x\in \mathcal{X}, h\in \mathcal{H}}\left|\phi(h(x))\right|$。下面先介紹Rademacher復(fù)雜度的定義。

定義 2 （Rademacher復(fù)雜度）設(shè)樣本集$S = (z_1, z_2, \cdots, z_m)$中的每個樣本都獨立同分布地采自分布$\mathcal{D}$，$\mathcal{F}=\{f: \mathcal{Z}\rightarrow \mathbb{R}\}$為可測函數(shù)類。則$\mathcal{F}$關(guān)于樣本集$S$的Rademacher復(fù)雜度^[3]定義為

\[\mathfrak{R}_S(\mathcal{H}) = \mathbb{E}_{S}\mathbb{E}_{\sigma\sim \{\pm 1\}^m}\left[\sup_{f\in \mathcal{F}}\frac{1}{m}\sum_{i=1}^m \sigma_i f(z_i)\right] \]

其中$\sigma = (\sigma_1, \cdots, \sigma_m)\in \{\pm 1\}^m$為隨機向量，其中每個元素都獨立同分布地采自$\{-1, +1\}$。

為了證明定理 1，我們會先展示一個引理，該引理關(guān)聯(lián)了假設(shè)類$\mathcal{H}$和代理損失函數(shù)類$\mathcal{L}$的Rademacher復(fù)雜度。現(xiàn)定義代理損失函數(shù)類$\mathcal{L}$為

\[\mathcal{L} = \left\{(x, y)\rightarrow L(h, x, y)\mid h\in \mathcal{H}\right\} \]

則有下列引理^[2]成立：

引理 1 設(shè)$\mathfrak{R}_S(\mathcal{L})$為$\mathcal{L}$關(guān)于樣本集$S$的Rademacher復(fù)雜度，$\mathfrak{R}_S(\mathcal{H})$為$\mathcal{H}$關(guān)于樣本集$S$的Rademacher復(fù)雜度，則我們有$\mathfrak{R}_S(\mathcal{L})\leqslant 2 n C_{\phi} \mathfrak{R}_S(\Pi_1(\mathcal{H}))$。

引理 1的證明 按照定義，可以將$\mathfrak{R}_S(\mathcal{L})$界定如下：

\[\begin{aligned} \mathfrak{R}_S(\mathcal{L}) &= \mathbb{E}_S\mathbb{E}_{\sigma}\left[\sup_{L\in \mathcal{L}}\frac{1}{m}\sum_{i=1}^m \sigma_i L(x_i, y_i, h)\right] \\ &= \mathbb{E}_S\mathbb{E}_{\sigma}\left[\sup_{h\in \mathcal{H}}\frac{1}{m}\sum_{i=1}^m \sigma_i \left(\phi\left(h(x_i)_{y_i}\right) + \sum_{y^{\prime}\neq y_i}\phi\left(-h(x_i)_{y^{\prime}}\right)\right)\right]\\ &= \mathbb{E}_S\mathbb{E}_{\sigma}\left[\sup_{h\in \mathcal{H}}\left(\frac{1}{m}\sum_{i=1}^m \sigma_i \phi\left(h(x_i)_{y_i}\right) + \frac{1}{m}\sum_{i=1}^m \sigma_i \sum_{y^{\prime}\neq y_i}\phi\left(-h(x_i)_{y^{\prime}}\right)\right)\right]\\ &\leqslant \underbrace{\mathbb{E}_S\mathbb{E}_{\sigma}\left[\sup_{h\in \mathcal{H}}\frac{1}{m}\sum_{i=1}^m \sigma_i \phi\left(h(x_i)_{y_i}\right)\right]}_{(A)} + \underbrace{\mathbb{E}_S\mathbb{E}_{\sigma} \left[\sup_{h\in \mathcal{H}}\frac{1}{m}\sum_{i=1}^m \sigma_i \sum_{y^{\prime}\neq y_i}\phi\left(-h(x_i)_{y^{\prime}}\right)\right]}_{(B)} \end{aligned} \]

其中最后一行不等式我們使用了$\sup(\cdot)$函數(shù)的次可加性（sub-additivity）^[12]：$\sup(U + V)\leqslant \sup(U) + \sup(V)$。接下來我們嘗試界定上述兩項。設(shè)$\alpha_i = 2\mathbb{I}_{y = y_i} - 1$，可以將第一項$(A)$界定如下：

\[\begin{aligned} (A) &= \mathbb{E}_S\mathbb{E}_{\sigma}\left[\sup_{h\in \mathcal{H}}\frac{1}{m}\sum_{i=1}^m \sigma_i \phi\left(h(x_i)_{y_i}\right)\right]\\ &= \mathbb{E}_S\mathbb{E}_{\sigma}\left[\sup_{h\in \mathcal{H}}\frac{1}{2m}\sum_{i=1}^m \sigma_i \sum_y \phi\left(h(x_i)_{y}\right) (\alpha_i + 1)\right] \\ &\leqslant \mathbb{E}_S\mathbb{E}_{\sigma}\left[\sup_{h\in \mathcal{H}}\frac{1}{2m}\sum_{i=1}^m \sigma_i \sum_y \phi\left(h(x_i)_{y}\right)\alpha_i \right] + \mathbb{E}_S\mathbb{E}_{\sigma}\left[\sup_{h\in \mathcal{H}}\frac{1}{2m}\sum_{i=1}^m \sigma_i \sum_y \phi\left(h(x_i)_{y}\right) \right] \\ &\quad (\text{sub-additivity of} \sup(\cdot))\\ &= \mathbb{E}_S\mathbb{E}_{\sigma}\left[\sup_{h\in \mathcal{H}}\frac{1}{2m}\sum_{i=1}^m \sum_y \phi\left(h(x_i)_{y}\right)\alpha_i\sigma_i \right] + \mathbb{E}_S\mathbb{E}_{\sigma}\left[\sup_{h\in \mathcal{H}}\frac{1}{2m}\sum_{i=1}^m \sigma_i \sum_y \phi\left(h(x_i)_{y}\right) \right] \\ &= \mathbb{E}_S\mathbb{E}_{\sigma}\left[\sup_{h\in \mathcal{H}}\frac{1}{2m}\sum_{i=1}^m \sum_y \phi\left(h(x_i)_{y}\right)\sigma_i \right] + \mathbb{E}_S\mathbb{E}_{\sigma}\left[\sup_{h\in \mathcal{H}}\frac{1}{2m}\sum_{i=1}^m \sigma_i \sum_y \phi\left(h(x_i)_{y}\right) \right] \\ & (\alpha_i\sigma_i \text{ has the same distribution as } \sigma_i)\\ &= \mathbb{E}_S\mathbb{E}_{\sigma}\left[\sup_{h\in \mathcal{H}}\frac{1}{m}\sum_{i=1}^m \sigma_i \sum_y \phi\left(h(x_i)_{y}\right) \right]\\ &\leqslant \sum_y \mathbb{E}_S\mathbb{E}_{\sigma}\left[\sup_{h\in \mathcal{H}}\frac{1}{m}\sum_{i=1}^m \sigma_i \phi\left(h(x_i)_{y}\right) \right] (\text{sub-additivity of} \sup(\cdot))\\ &= n \mathfrak{R}_S(\phi\circ \Pi_1(\mathcal{H})) \end{aligned} \]

其中$n$是類別個數(shù)。與$(A)$項類似，$(B)$項也可以被$ \mathfrak{R}_S(\phi\circ \Pi_1(\mathcal{H}))$界定。

于是，我們可以將$\mathcal{L}$關(guān)于樣本集$S$的Rademacher復(fù)雜度界定如下：

\[\mathfrak{R}_S(\mathcal{L}) \leqslant \underbrace{2 n \mathfrak{R}_S(\phi \circ \Pi_1(\mathcal{H})) \leqslant 2 n C_{\phi} \mathfrak{R}_S(\Pi_1(\mathcal{H}))}_{\text{Talagrand contraction principle}} \]

最后一個不等式根據(jù)如下的Talagrand壓縮原理^[13]得到：

引理 2 (Talagrand壓縮原理) 設(shè)$\phi: \mathbb{R}\rightarrow \mathbb{R}$為$C_{\phi}$-Lipschitz函數(shù)，則

\[ \mathfrak{R}_S(\phi\circ\mathcal{H}) \leqslant C_{\phi}\mathfrak{R}_S(\mathcal{H}) \]

其中$\phi\circ \mathcal{H} = \{z\mapsto \phi(h(z)): h\in \mathcal{H}\}$。

其次，我們介紹一個經(jīng)驗過程的單側(cè)上界關(guān)于訓練樣本$S$的期望的重要結(jié)論^[9]，該結(jié)論將經(jīng)驗過程的單側(cè)上界與Rademacher復(fù)雜度聯(lián)系了起來。

引理 3

\[\mathbb{E}_{S}\left[\sup_{h\in \mathcal{H}} \left(\widehat{R}_L(h) - R_L(h)\right)\right] \leqslant 2\mathfrak{R}_S(\mathcal{L}) \]

這個引理的證明會用到一種稱之為對稱化（symmetrization） 的技術(shù)，大致為引入輔助樣本集$S^{\prime}$并以此將泛化誤差$R_L(h)$限制到$S^{\prime}$上（類似測試集），并利用$S$和$S^{\prime}$樣本集的對稱性來在保持期望不變的前提下完成$\sigma(\cdot)$函數(shù)的引入（這也是為何不等式左邊有個期望$\mathbb{E}_S[\cdot]$），詳細證明可參考《Understanding machine learning: From theory to algorithms》Ch.26 ^[9]。

有了這些引理，我們可以接下來可以開始正式證明定理 1了。

注下面再將定理 1再貼一遍：對任意$\delta > 0$，至少以$1 - \delta$的概率有

\[\sup_{h\in \mathcal{H}}\lvert \widehat{R}_L(h) - R_L(h)\lvert \leqslant 4 n C_{\phi} \mathfrak{R}_S(\Pi_1(\mathcal{H})) + M_{\phi} \sqrt{\frac{8\log \frac{2}{\delta}}{m}} \]

定理 1的證明 上述不等式是經(jīng)驗過程的雙側(cè)界，只需討論與$\sup_{h\in \mathcal{H}}\left(\widehat{R}_L(h) - R_L(h)\right)$相關(guān)的單側(cè)界至少以概率$1 - \frac{\delta}{2}$成立即可。

記$A(z_1, \cdots, z_m) = \sup_{h\in \mathcal{H}}\left(\widehat{R}_L(h) - R_L(h)\right)$，通過引理 3，我們已經(jīng)知道$ \mathbb{E}_{S}\left[A(z_1, \cdots, z_m)\right] \leqslant 2\mathfrak{R}_S(\mathcal{L}) $成立。現(xiàn)在我們需要考慮$A(z_1, \cdots, z_m)$的界，那么如果我們可以證明有界變差條件^[6][7]$\left|A(z_1, \cdots, z_m) - A(z_1, \cdots, z_i^{'}, \cdots, z_m)\right|\leqslant c$（也即將參數(shù)中的任意一項$z_i = (x_i, y_i)$被與訓練集獨立同分布的$z_i^{\prime} = (x^{\prime}_i, y_i^{\prime})$替換后，函數(shù)值的變化量被常數(shù)$c$界定），那么就可以考慮應(yīng)用McDiarmid不等式得到

\[ A(z_1, \cdots, z_m) \leqslant \mathbb{E}_{S}\left[A(z_1, \cdots, z_m)\right] + c\sqrt{\frac{m}{2}\log (\frac{1}{\delta}))} \]

以$1 - \delta$概率成立。

那么我們先嘗試界定單側(cè)變差：

\[\begin{aligned} &A(z_1, \cdots, z_m) - A(z_1, \cdots, z_i^{'}, \cdots, z_m)\\ &= \sup_{h\in \mathcal{H}}\left[\frac{1}{m}\sum_{j=1}^mL(h, x_j, y_j) - \mathbb{E}_{\mathcal{D}}\left[L(h, x, y)\right]\right]\\ &\quad \space - \sup_{h^{\prime}\in \mathcal{H}}\left[\frac{1}{m}L(h^{\prime}, x_i^{\prime}, y_i^{\prime}) + \frac{1}{m}\sum_{j\in [m]\backslash\{i\}}L(h^{\prime}, x_j, y_j) - \mathbb{E}_{\mathcal{D}}\left[L(h^{\prime}, x, y)\right]\right]\\ &= \sup_{h\in \mathcal{H}}\inf_{h^{\prime}\in \mathcal{H}}\left[\frac{1}{m}\sum_{j=1}^mL(h, x_j, y_j) - \mathbb{E}_{\mathcal{D}}\left[L(h, x, y)\right]\right.\\ &\quad \space \left.- \frac{1}{m}L(h^{\prime}, x_i^{\prime}, y_i^{\prime}) - \frac{1}{m}\sum_{j\in [m]\backslash\{i\}}L(h^{\prime}, x_j, y_j) + \mathbb{E}_{\mathcal{D}}\left[L(h^{\prime}, x, y)\right]\right]\\ &\leqslant \sup_{h\in \mathcal{H}}\left[\frac{1}{m}\sum_{j=1}^mL(h, x_j, y_j) - \mathbb{E}_{\mathcal{D}}\left[L(h, x, y)\right]\right.\\ &\quad \space \left.- \frac{1}{m}L(h, x_i^{\prime}, y_i^{\prime}) - \frac{1}{m}\sum_{j\in [m]\backslash\{i\}}L(h, x_j, y_j) + \mathbb{E}_{\mathcal{D}}\left[L(h, x, y)\right]\right]\\ &= \sup_{h\in \mathcal{H}}\left[\frac{1}{m}L(h, x_i, y_i) - \frac{1}{m}L(h, x^{\prime}_i, y^{\prime}_i)\right]\\ &= \frac{1}{m}\sup_{h\in \mathcal{H}}\left[\phi\left(h(x_i)_{y_i}\right) + \sum_{y^{\prime}\neq y_i}\phi\left(-h(x_i)_{y^{\prime}}\right) - \phi\left(h(x_i^{\prime})_{y^{\prime}_i}\right) - \sum_{y^{\prime\prime}\neq y_i^{\prime}}\phi\left(-h(x_i^{\prime})_{y^{\prime\prime}}\right)\right]\\ &= \frac{1}{m}\sup_{h\in \mathcal{H}}\left[\phi\left(h(x_i)_{y_i}\right) + \phi\left(-h(x_i)_{y_i^{\prime}}\right) - \phi\left(h(x_i^{\prime})_{y_i^{\prime}}\right) - \phi\left(-h(x_i^{\prime})_{y_i}\right)\right]\\ &\leqslant \frac{4M_{\phi}}{m} \end{aligned} \]

同理可得$A(z_1, \cdots, z_i^{'}, \cdots, z_m) - A(z_1, \cdots, z_m)\geqslant -\frac{4M_{\phi}}{m}$。于是$\left|A(z_1, \cdots, z_m) - A(z_1, \cdots, z_i^{'}, \cdots, z_m)\right| \leqslant c = \frac{4M_{\phi}}{m}$。接著，應(yīng)用McDiarmid不等式并結(jié)合引理 3、引理 1可知

\[\begin{aligned} \sup_{h\in \mathcal{H}}\left(\widehat{R}_L(h) - R_L(h)\right) &\leqslant \mathbb{E}_{S}\left[\sup_{h\in \mathcal{H}}\left(\widehat{R}_L(h) - R_L(h)\right)\right] + c\sqrt{\frac{m}{2}\log (\frac{1}{\delta}))}\\ & \quad (\text{McDiarmid inequality})\\ &\leqslant \mathbb{E}_{S}\left[\sup_{h\in \mathcal{H}}\left(\widehat{R}_L(h) - R_L(h)\right)\right] + M_{\phi}\sqrt{\frac{8\log (\frac{1}{\delta})}{m}} \quad (c = \frac{4M_{\phi}}{m})\\ &\leqslant 2\mathfrak{R}_S(\mathcal{L}) + M_{\phi}\sqrt{\frac{8\log (\frac{1}{\delta})}{m}} \quad (\text{Lemma } 3)\\ &\leqslant 4 n C_{\phi} \mathfrak{R}_S(\Pi_1(\mathcal{H}))+ M_{\phi}\sqrt{\frac{8\log (\frac{1}{\delta})}{m}} \quad (\text{Lemma } 1) \end{aligned} \]

對任意$\delta > 0$，至少以$1 - \delta$的概率成立。用$\frac{\delta}{2}$直接變量替換掉$\delta$有：$\sup_{h\in \mathcal{H}}\left(\widehat{R}_L(h) - R_L(h)\right)\leqslant 4 n C_{\phi} \mathfrak{R}_S(\Pi_1(\mathcal{H}))+ M_{\phi}\sqrt{\frac{8\log (\frac{2}{\delta})}{m}}$至少以$1 - \frac{\delta}{2}$的概率成立。于是對于雙側(cè)界，我們有：

\[\sup_{h\in \mathcal{H}}\lvert \widehat{R}_L(h) - R_L(h)\lvert \leqslant 4 n C_{\phi} \mathfrak{R}_S(\Pi(\mathcal{H})) + M_{\phi} \sqrt{\frac{8\log \frac{2}{\delta}}{m}} \]

對任意$\delta > 0$，至少以$1 - \delta$的概率成立。定理得證。

于是，我們在第2部分提到的泛化差距$R_L(\hat{h}) - \widehat{R}_L(\hat{h})$和“小項”$\widehat{R}(h^{\circ}) - R(h^{\circ})$都可以被界定了。而對任意$h\in \mathcal{H}$，有泛化界

\[R_L(h)\leqslant \widehat{R}_L(h) + 4 n C_{\phi} \mathfrak{R}_S(\Pi_1(\mathcal{H}))+ M_{\phi}\sqrt{\frac{8\log (\frac{1}{\delta})}{m}} \]

對任意$\delta > 0$，至少以$1 - \delta$的概率成立。至此，代理損失函數(shù)的泛化界得證。

參考

[1] Mao A, Mohri M, Zhong Y. Predictor-rejector multi-class abstention: Theoretical analysis and algorithms[C]//International Conference on Algorithmic Learning Theory. PMLR, 2024: 822-867.
[2] Ni C, Charoenphakdee N, Honda J, et al. On the calibration of multiclass classification with rejection[J]. Advances in Neural Information Processing Systems, 2019, 32.
[3] 周志華, 王魏, 高尉, 張利軍. 機器學習理論導引[M]. 機械工業(yè)出版社, 2020.
[4] Han Bao: Learning Theory Bridges Loss Functions
[5] 滕佳燁、王伯元、張臻: 機器學習理論簡明手冊
[6] Bartlett P L, Jordan M I, McAuliffe J D. Convexity, classification, and risk bounds[J]. Journal of the American Statistical Association, 2006, 101(473): 138-156.
[7] Cortes C, DeSalvo G, Mohri M. Boosting with abstention[J]. Advances in neural information processing systems, 2016, 29.
[8] JOJO想：深度學習中的泛化理論（9）良性過擬
[9] Shalev-Shwartz S, Ben-David S. Understanding machine learning: From theory to algorithms[M]. Cambridge university press, 2014.
[10] Wellner J A: Empirical processes: Theory and applications
[11] Vershynin R. High-dimensional probability: An introduction with applications in data science[M]. Cambridge university press, 2018.
[12] Mohri M, Rostamizadeh A, Talwalkar A. Foundations of machine learning[M]. MIT press, 2018.
[13] Stanford CS229T/STATS231: Statistical Learning Theory - Lecture #6

posted @ 2025-08-04 17:36 orion-orion 閱讀(220) 評論(0) 收藏舉報

刷新頁面返回頂部

Orion's Blog

學習理論、在線優(yōu)化、數(shù)據(jù)挖掘

學習理論：代理損失函數(shù)的泛化界與Rademacher復(fù)雜度

1 導引

2 泛化誤差界

3 經(jīng)驗過程的Rademacher復(fù)雜度上界

參考

公告