測試集調參和PAC可學習性

作者：由歐澤彬發表于體育時間：2021-10-03

在做標準化的機器學習任務時，任務形式、評價指標、資料切分等都已經做好，甚至標準模型都已經寫好了，我們在

git pull

後只需要跟隨前人的儀式，在訓練集上訓練引數，在開發集上選擇超參，用測試集報告結果，就能煉出一份好丹。但是一旦需要自己定義任務、設計評價、蒐集資料的時候，我們可能會產生如下疑問：

什麼確定了一個機器學習任務？

當我們在用資料去訓練、評價模型時，我們到底在做什麼？

怎麼根據機器學習的實驗結果給出科學結論？

為什麼要切分開發和測試集？資料量比較少的時候為什麼不直接在測試集上選超參？

回答以上問題涉及到對學習（learning）的理解

［1］

。歡迎大家批評指正。

1。學習和可學習性

機器學習的一個通用的定義來自 Tom Mitchell：

A computer program is said to learn from experience

with respect to some class of tasks

， and performance measure

， if its performance at tasks in

， as measured by

， improves with experience

。

我們引入額外的概念來解釋預測任務

，效能指標

，經驗

以及

的提升分別是什麼，從而給學習（learning）下一個更具體的定義。

預測任務

由某個例項域

$\mathcal{Z}$

及其上的分佈

$P_\mathcal{Z}(z)$

決定。在確定好關於例項

$z \in \mathcal{Z}$

的對映的形式（根據

的一部分預測另一部分）後，分佈

$P_\mathcal{Z}(z)$

決定了具體的對映規則：不符合對映規則的例項

的機率為 0 或很小。例如對於分類任務（classification），例項

$z \in \mathcal{Z}$

會拆為

$(x, y) \in \mathcal{X} \times \mathcal{Y}$

，我們需要根據輸入特徵

預測標籤

，具體的對映規則由

$P_{\mathcal{X} \times \mathcal{Y}}(x, y)$

決定，最後得到的對映規則是一個機率性對映（probabilistic mapping），即對於每個輸入

，輸出的是所有可能取值的分佈

$P_{\mathcal{X} \times \mathcal{Y}}(y|x)$

而不是一個具體的值

。

我們引入和任務

在例項

有相同對映形式的的預測器（predictor），稱之為對具體對映的一種假設（hypothesis）

。所有候選的

組成集合

$\mathcal{H}$

，稱為假設族（hypothesis class）。

損失函式（loss）

$l(h,z) \geq 0$

被用來評價

準確度，其在

$P_\mathcal{Z}(z)$

上的期望稱之為風險（risk）

$R(h) = \mathbb{E}_{P_\mathcal{Z}}[l(h,z)]$

，這便是效能指標

。

我們並不知道分佈

$P_\mathcal{Z}(z)$

的具體形式（否則就沒有機器學習什麼事了），但我們可以取樣

$z \sim P_\mathcal{Z}(z)$

得到

個例項樣本組成的資料集

，這便構成了經驗

。一般我們假設這些樣本

是獨立同分布的（independent and identically distributed， i。i。d。），所以資料集

服從分佈

$P^m_\mathcal{Z}(S) = \prod_{i=1}^m P_\mathcal{Z}(z_i)$

。每個

定義了經驗風險（empirical risk）

$R_S(h) = \frac{1}{m} \sum_{i=1}^m l(h, z_i)$

，作為風險

的統計估計。

的提升意味著風險

的下降。

所以學習（learning）意味著我們利用資料集

從假設族

$\mathcal{H}$

中選擇了風險

較低的預測對映

。如果這件事可以被保證實現我們便稱假設族

$\mathcal{H}$

是可學習的（learnable）。選擇

的過程由一個學習演算法（learning algorithm）

來實現。

理想上我們希望找出

$\mathcal{H}$

中最小化

的對映

$h^* = \arg \min_{h \in \mathcal{H}} R(h)$

，稱之為最優假設（optimal hypothesis）。因為經驗風險

是

的統計估計，我們可以用經驗風險最小化（Empirical Risk Minimization， ERM）作為學習演算法

的目標選出假設

$h_S = \arg \min_{h\in\mathcal{H}} R_S(h)$

。基於 ERM，學習理論（computational learning theory）進一步定義了 PAC 可學習性（Probably Approximately Correct learnability）：

Approximately Correct：根據資料集

用 ERM 選出的對映

與最優對映

之間的誤差是有界的：

$R(h_S) - R(h^*) < \epsilon$

Probably：取樣到的資料集

至少以機率

$1 - \delta$

滿足 approximately correct 條件。

Learnable：對任意

$\epsilon \in [0, +\infty]$

和

$\delta \in [0, 1]$

，存在

$m_\mathcal{H}(\epsilon, \delta)$

，當資料集

的樣本數量

滿足

$m > m_\mathcal{H}(\epsilon, \delta)$

的任意 i。i。d。樣本

總能成立。

1。1。為什麼要引入 Probably 和 Approximately Correct

Probably approximately correct 定義成功的學習（learning）意味著在

較小的失敗機率

下我們能找到

風險

和最優對映相近

的對映。任務

對於

的真實對映規則存在不確定性（uncertainty）。這種不確定性可能來自於我們對真實對映規則背後的機制的無知（認識不確定性，epistemic uncertainty），也可能來自於機制本身存在的隨機性（固有不確定性，aleatoric uncertainty）。所以我們用一個機率性函式去建模任務

的真實對映，並在此基礎上用機率語言定義可學習性：Probably 反應了認識不確定性，即取樣到的訓練集

可能不能代表真實分佈

$P_\mathcal{Z}(z)$

；而 Approximately Correct 則容許了認識不確定性帶來的統計推斷誤差，以及固有不確定性帶來的隨機誤差。

1。2。先驗知識和泛化

假設族

$\mathcal{H}$

、損失函式

、學習演算法

共同決定了我們對任務

的先驗知識（prior knowledge）：

$\mathcal{H}$

決定了可選假設的範圍，

定義了選擇偏好，

決定了搜尋順序。先驗是必要的，因為沒有了對可能對映的限制和偏好，我們無法根據已取樣到的資料推測未來取樣的資料。這裡構造一個零先驗的例子來說明這一點：假如假設族

$\mathcal{H}$

包含一個無窮例項域

$\mathcal{Z}$

上的所有對映，那麼總有一個無窮子集

$\mathcal{H}$

包含了在無窮集合

$\{z: z \notin S, z \sim P_\mathcal{Z}(z) \}$

上的任何對映，其中每一個

都滿足

，即在 ERM 視角下他們都是一樣的。所以在

上進行 ERM 相當於隨機從

$\mathcal{H}$

中選擇一個

，這並不能保證其風險

足夠小。

如果用 ERM 選取的

對應的

過大，我們便稱

過擬合了

，其以

體現的泛化（generalization）效能比較差。這裡的

通常用另一個不參與 ERM 的資料集

，即測試集來估計，這麼做的原因在第 2 節中會闡述。

1。3。回答問題 1 - 3

問題 1. 什麼確定了一個機器學習任務？

機器學習任務通常指例項

上的對映形式及刻畫某個未知規律的分佈

$P_{\mathcal{Z}}(z)$

共同確定的一個機率性對映。我們可能會混淆同一個分佈

$P_{\mathcal{Z}}(z)$

下的關於

不同對映形式，如預訓練語言模型中

對應語料中的一個句子，但是可以對

定義不同的 mask-predict 任務。我們也可能混淆關於

的同一個對映形式的不同分佈

$P_{\mathcal{Z}}(z)$

，比如在不同垂域下的翻譯任務。當然不同垂域的任務也可以認為是同一個分佈

$P_{\mathcal{Z}}(z)$

的不同有偏取樣。

問題 2. 當我們在用資料去訓練、評價模型時，我們到底在做什麼?

資料集

提供了對真實的評價指標

的統計估計

$R_{S}(h)$

，這是一個統計估計問題。從預先定義的假設族

$\mathcal{H}$

中選出風險

最低的假設

，這是一個最佳化問題。由於

未知我們用統計估計值

$R_{S}(h)$

作為替代目標進行最佳化，即 ERM。保證 ERM 找出的解

的

足夠低便是機器學習要解決的泛化性（generalization）問題 —— 學習是一個統計 + 最佳化的複合問題。

問題 3. 怎麼根據機器學習的實驗結果給出科學結論？

首先

$P_{\mathcal{Z}}(z)$

是由某種物理機制決定的

現象

或者

行為

。

描述的是現象和行為上的一致而不是內在機制的一致，所以機器學習受限於行為主義（behaviorism）的侷限性：同一個現象或者行為可能由多個內在機制產生，所以現象或行為的一致不能推斷出內在機制的一致。典型的例子便是圖靈測試：透過圖靈測試的機器並不意味著擁有類似人類的智慧，它可能是在做一個巨大的表格查詢。

其次

只能用取樣得到的資料集進行統計估計，而估計必然存在誤差。除去理論上隨機性帶來的誤差外，資料的取樣過程也會帶來偏差，如有偏取樣或者非 i。i。d。取樣。

最後假設族

$\mathcal{H}$

、損失函式

、學習演算法

反映的先驗隱藏了我們的假設。如果需要用機器學習實驗區證明某個結論，這些假設必須仔細檢驗，否則會出現用結論證明結論的邏輯迴環。另外注意

和分佈

$P_{\mathcal{Z}}(z)$

共同決定的

只表達了現象或行為在

某個維度上

和分佈

$P_{\mathcal{Z}}(z)$

的相似性。

1。4。擬人化的論述在說啥

機器學習文獻裡面存在大量的擬人化論述。作為直覺理解各種方法無可厚非，但是以此來做科學論述可能會存在問題。筆者曾經遇到過一些類似的論述，聽起來總覺得不能充分理解。這裡舉兩個遇到過的例子。

神經網路可以在隨機標籤訓練集上達到

，一個解釋是神經網路擁有完全記住（memorize）整個資料集的能力。所以似乎可以把訓練集的準確率

當做是模型“記住”訓練集所有“知識”的證據。作為擬人化的推論，既然記住了整個訓練集，那模型就擁有了訓練集的所有資訊。假設這些資訊被某個下游任務所需要，那麼下游任務的準確率差便可以作為模型並不能“回憶”記住的“知識”的證據。這裡的謬誤在於

刻畫的是

某個維度上

和

取樣到的訓練集

的相似性，它並不能作為

記住

整個訓練集資訊的依據。

分析性的工作如通常會聲稱神經網路擁有或者缺乏某種知識（knowledge），比如語義知識和常識等。首先這些論述其實隱藏了擬人假設：神經網路學到的知識必須和我們已經形成的概念以及知識體系相對應，我們才能理解它們、用相關的語言去表達它們。所以當我們在說神經網路擁有或者缺乏某種知識的時候，我們其實是在說它們擁有或者缺乏

人類總結過的

知識。其次，由於機器學習繼承了行為主義的侷限性，知識只能體現為某個任務上的效能，並不存在單獨、孤立開來的知識。我們在討論機器學習中知識與知識間的關係時，其實是在討論任務和任務間的關係。

2。最佳化對統計估計誤差的影響

最佳化和統計估計本身是兩個正交的概念。但是如果既把資料集

用來執行 ERM 選出

$h_S = \arg\min_{h \in \mathcal{H}} R_S(h)$

，又報告

作為

的近似，統計估計的準確度就會受最佳化相關的因素影響。這種做法在機器學習中廣泛被採用：我們使用測試、開發和訓練集在不同假設族

$\mathcal{H}_{\mathrm{te}}$

，

$\mathcal{H}_{\mathrm{dev}}$

和

$\mathcal{H}_{\mathrm{tr}}$

中選擇

並報告

。分析背後的機制可以幫助我們回答

問題 4

。

理想上

$\mathcal{H}_{\mathrm{te}}$

是一個單成員集合，所以不涉及到 ERM；

$\mathcal{H}_{\mathrm{dev}}$

是一個有限集合，其成員對應不同超參取值；而

$\mathcal{H}_{\mathrm{tr}}$

理論上是一個無限集合（引數通常是實數向量），其成員對應所有可能的引數，但由於浮點數是有限可列舉的，所以實際上

$\mathcal{H}_{\mathrm{tr}}$

也是有限的（這裡用了所謂的 discretization trick）。

給定誤差上界

$\epsilon$

、資料集大小

以及一個有限假設族

$\mathcal{H}$

，在這一節我們推導對任意

$h \in \mathcal{H}$

，取樣到的資料集

對應的最大估計誤差超過上界

$\epsilon$

的機率

$P(\{S: \max_{h \in \mathcal{H}}|R_S(h) - R(h)| > \epsilon \})$

。我們會看到這個機率存在一個上界

$\rho$

，它和 ERM 對應的假設族大小

$|\mathcal{H}|$

線性相關。有了

$\rho$

的表示式後便可以分析固定

$\rho$

後不同因子間的關係。

2。1。違反估計誤差上界的機率

重新整理違反估計誤差上界的資料集

的集合：

$\begin{align} \mathcal{V} &=\{S: \max_h|R_S(h) - R(h)| > \epsilon \} \\ &=_1\{S: \exists h \in \mathcal{H}, |R_S(h) - R(h)| > \epsilon\} \\ &=_2\cup_{h \in \mathcal{H}} \{S: |R_S(h) - R(h)| > \epsilon\} \end{align}$

其中

是因為最大化

的

必然滿足存在條件，

則是將資料集樣本

根據

重新分組（允許

重複出現在不同組中），然後再用並集去掉重複的

。進而

$\begin{align} P(\mathcal{V}) &= P_\mathcal{Z}^m(\cup_{h \in \mathcal{H}} \{S: |R_S(h) - R(h)| > \epsilon\}) \\ &\leq_1 \sum_{h \in \mathcal{H}} P_\mathcal{Z}^m(\{S: |R_S(h) - R(h)| > \epsilon\}) \\ &\leq_2 \sum_{h\in \mathcal{H}} 2 \exp(-2m \epsilon^2) \\ & = 2|\mathcal{H}|\exp(-2m \epsilon^2) = \rho \end{align}$

其中

$P_\mathcal{Z}^m(S)$

是關於資料集

的分佈；

$\leq_1$

基於機率論的 union bound

$P(A \cup B) \leq P(A) + P(B)$

；

$\leq_2$

則是使用了 Hoeffding 不等式。

2.2.1. Hoeffding 不等式的使用

對於期望為

$\mu$

的 i。i。d。的隨機變數

$\theta_1, ..., \theta_m$

，如果

$P(a\leq \theta_i \leq b) = 1$

，Hoeffding 不等式為

$P(|\frac{1}{m} \sum_{i=1}^m \theta_i - \mu| > \epsilon) \leq 2 \exp(-2m \epsilon^2 /(b-a)^2)$

由於

$R_S(h) = \frac{1}{m} \sum_{i=1}^{m} l(h, z_i)$

是期望

$R(h) = \mathbb{E}_{P_\mathcal{Z}}[l(h,z)]$

的統計估計，再令

$l(h, z) \in [0, 1]$

（有界的

總能被縮放到

區間），套用這個不等式得到

$P_\mathcal{Z}^m(\{S: |R_S(h) - R(h)| > \epsilon\}) \leq 2 \exp(-2m \epsilon^2)$

2。2。根據推導結果回答問題 4

我們最終得到

$P(\mathcal{V}) \leq \rho = 2|\mathcal{H}|\exp(-2m \epsilon^2)$

。

固定

$\rho$

以及

後有

$\epsilon = \sqrt{\frac{1}{2m}\log\frac{2|\mathcal{H}|}{\rho}}$

固定

$\rho$

以及

$\epsilon$

後有

$m = \frac{1}{2\epsilon^2} \log \frac{2|\mathcal{H}|}{\rho}$

令

$\rho = 0.01$

，

$m(|\mathcal{H}|) - m(1)$

和

$\epsilon(|\mathcal{H}|) - \epsilon(1)$

在不同

$|\mathcal{H}|$

的取值取值見下表。注意

$R_S(h) \in [0, 1]$

。

所以為了保證

的估計誤差

$\epsilon$

恆定，資料集的大小

需滿足

$m \propto \log|\mathcal{H}|$

。由於在訓練集中 ERM 中涉及的假設族

$\mathcal{H}$

非常大，所以訓練集的大小應遠大於開發集和測試集。

最後我們回答問題 4 ：

問題 4. 為什麼要切分開發和測試集？資料量比較少的時候為什麼不直接在測試集上選超參？

固定資料集，ERM 涉及的假設族

$\mathcal{H}$

越大，

的估計誤差

$\epsilon$

越大，為了證明一個假設

的優越性需要的效能

的相對提升就越大。所以在測試集上調超參的操作並不可取 —— 測試集是有“使用壽命”的，過分在測試集上最佳化只會令其對真實分佈的估計越不準。

對一些充分最佳化的測試集，我們需要謹慎地根據微小的效能提升下結論。

3。有限假設族是 PAC 可學習的

上一小節的推導修改一下後就可以證明有限假設族

$\mathcal{H}$

是 PAC 可學習的，所以順帶提一下。

集合

$\mathcal{V} = \{S: \exists h \in \mathcal{H}, |R_S(h) - R(h)| > \epsilon\}$

的補集為

$\bar{\mathcal{V}} = \{S: \forall h \in \mathcal{H}, |R_S(h) - R(h)| \leq \epsilon\}$

。滿足

$\forall h \in \mathcal{H}, |R_S(h) - R(h)| \leq \epsilon$

的資料集

被稱為是

$\epsilon$

-representative 的。由於對任意

$h \in \mathcal{H}$

：

$R(h_S) \leq_1 R_S(h_S) + \epsilon \leq_2 R_S(h) + \epsilon\leq_3 R(h) + 2\epsilon$

所以

$\epsilon$

-representative 可以推出 approximately correct。上式中

$\leq_1$

是因為

可能低估了

，

$\leq_2$

是由於

$R_S(h_S) = \min_{h \in \mathcal{H}} R_S(h)$

，

$\leq_3$

是因為

可能高估了

。由於上式對任意

成立，自然也對最優假設

成立。

如果將 PAC 可學習性中的 approximately correct 條件，即任何對樣本

都有

$R(h_S) - R(h^*) < \epsilon$

，換成任何樣本

都滿足

$\epsilon$

-representative，即

$\forall h \in \mathcal{H}, |R_S(h) - R_D(h)| \leq \epsilon$

，那麼 PAC 可學習性就變成了 uniform convergence。所以我們只需要證明假設族

$\mathcal{H}$

滿足 uniform convergence，就證明了

$\mathcal{H}$

是 PAC 可學習的。

根據 uniform convergence 的定義，

$P(\bar{\mathcal{V}})$

需滿足

$P(\bar{\mathcal{V}}) \geq 1 - \delta$

，即

$P(\mathcal{V}) \leq \delta$

。我們已經得到

$P(\mathcal{V}) \leq 2|\mathcal{H}|\exp(-2m \epsilon^2)$

，只需令

$\delta \geq 2|\mathcal{H}|\exp(-2m \epsilon^2)$

，即

$m \geq \frac{\log2|\mathcal{H}|/\delta}{2\epsilon^2} = m_\mathcal{H}(\epsilon, \delta)$

，就能使

$P(\bar{\mathcal{V}}) \geq 1 - \delta$

。所以

$m_\mathcal{H}(\epsilon, \delta)$

存在，從而有限假設族

$\mathcal{H}$

滿足 uniform convergence，進而是 PAC 可學習的。

參考

Understanding Machine Learning： From Theory to Algorithms， Shai Shalev-Shwartz and Shai Ben-David， 2014

標簽：對映學習假設 ERM 我們

上一篇:脾胃氣虛怎麼調理？

下一篇：小龍蝦蝦尾可以帶皮吃嗎

測試集調參和PAC可學習性

猜你喜歡

大家覺得零基礎學習大資料方面的怎麼樣？

計算機都要學程式設計嗎？

圓周率是固定的數嗎？

如何科學設計和評估一次AB測試

構思你的故事線