當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

机器学习理论-PAC learning

發(fā)布時(shí)間：2024/3/12 编程问答 32 豆豆

生活随笔收集整理的這篇文章主要介紹了机器学习理论-PAC learning 小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

對于一個機(jī)器學(xué)習(xí)任務(wù)，通常需要考慮它是不是可學(xué)的 (learnable)
PAC學(xué)習(xí)給出了一個抽象的刻畫機(jī)器學(xué)習(xí)能力的框架，基于這個框架，有很多重要問題可以探討，例如: 某任務(wù)在什么樣的條件下可學(xué)得較好的模型? 某算法在什么條件下可以進(jìn)行有效的學(xué)習(xí)？需要多少訓(xùn)練樣本才能獲得較好的模型？

基本概念

給定樣本集 $D={(x1,y1),(x2,y2),...(xm,ym)}D=\{ (\pmb{x_1}, y_1), (\pmb{x_2}, y_2), ...(\pmb{x_m}, y_m)\}$ , $yi∈{?1,+1}=Yy_i \in \{-1, +1\} = \mathcal{Y}$ , $xi∈Xx_i \in \mathcal{X}$ , $D$ 中所有的樣本都是獨(dú)立同分布從 $D\mathcal{D}$ 采樣而得。
令 $h$ 為從 $X\mathcal{X}$ 到 $Y\mathcal{Y}$ 的一個映射, 其泛化誤差(generalization error)為:
$\mathcal{D}) = P_{(x, y) \sim \mathcal{D}}(h(x) \neq y) = E_{(x,y) \sim \mathcal{D}}[I[h(x) \neq y]]$
$h$ 在 $D$ 上的經(jīng)驗(yàn)誤差(empirical error)為：
$E^(h;D)=1m∑1mI(h(xi)≠yi)\hat{E}(h;D)=\frac{1}{m}\sum_1^mI(h(x_i)\neq y_i)$

由于 $D$ 是 $D\mathcal{D}$ 的獨(dú)立同分布采樣，所以 $h$ 經(jīng)驗(yàn)誤差的期望等于泛化誤差。令 $?\epsilon$ 為 $E (h)$ 的上限，即 $\leq \epsilon$ 。通常用 $?\epsilon$ 表示模型應(yīng)滿足的誤差要求，稱為誤差參數(shù).
令 $c$ 表示概念, 它是從樣本空間 $X\mathcal{X}$ 到標(biāo)記空間 $Y\mathcal{Y}$ 的映射。若任何樣本 $(x, y)$ , 有 $c (x) = y$ , 則稱 $c$ 為目標(biāo)概念。所有目標(biāo)概念所組成的集合稱為概念類 $C\mathcal{C}$

給定學(xué)習(xí)算法 $L\mathcal{L}$ ，它考慮所有可能的假設(shè)空間 $H\mathcal{H}$ . 假設(shè)空間是對于學(xué)習(xí)算法最大能力的整體刻畫。假設(shè)空間給定了算法所有可能的映射函數(shù)。若目標(biāo)概念 $\in \mathcal{H}$ , 則 $H\mathcal{H}$ 存在假設(shè)能將所有樣本正確分開，稱該學(xué)習(xí)問題對假設(shè)空間是可分的（separable）；若 $\notin \mathcal{H}$ , 則稱假設(shè)空間不存在任何假設(shè)能將所有樣本完全正確分開，稱該學(xué)習(xí)問題對假設(shè)空間是不可分的 (non-separable)

PAC learning

PAC learning(Probably Approximately Correct)是關(guān)于機(jī)器學(xué)習(xí)可學(xué)性的完整的理論。解釋一下這個名字的由來：

Appromately Correct （近似正確），指的是學(xué)出的模型誤差比較小，因?yàn)閷?shí)現(xiàn)零誤差 (Absolutely Correct)是很困難且通常是沒有必要的，所以考慮的是 Approximately Correct

其次，由于數(shù)據(jù)隨機(jī)性的存在，也只能從概率上保證Approximately Correct的可能性是很大的 (存在一個概率的下界)

PAC Identify (PAC 辨識)：對于 $?>0,δ<1\epsilon > 0, \delta<1$ , 所有 $c∈Cc\in \mathcal{C}$ 和分布 $D\mathcal{D}$ , 若存在學(xué)習(xí)算法 $L\mathcal{L}$ , 其輸出假設(shè) $h∈Hh\in \mathcal{H}$ 滿足：
$\leq \epsilon) \geq 1-\delta$
則稱學(xué)習(xí)算法 $L\mathcal{L}$ 能從假設(shè)空間中PAC辨識概念類 $C\mathcal{C}$

PAC learnable (PAC 可學(xué)): 令 $m$ 表示從分布 $D\mathcal{D}$ 獨(dú)立同分布采樣得到樣本的數(shù)， $?>0,δ<1\epsilon > 0, \delta<1$ ，對所有分布 $D\mathcal{D}$ ，若存在學(xué)習(xí)算法 $L\mathcal{L}$ 和多項(xiàng)式函數(shù) $p o l y ()$ ，使得對于任何 $poly(1/\epsilon, 1/\delta, size(x), size(c))$ ， $L\mathcal{L}$ 能從假設(shè)空間 $H\mathcal{H}$ 中PAC identify 概念類 $C\mathcal{C}$ , 就稱概念類 $C\mathcal{C}$ 是PAC可學(xué)的

Agnostic PAC Learnable (不可知PAC可學(xué))：令 $m$ 表示從分布 $D\mathcal{D}$ 獨(dú)立同分布采樣得到樣本的數(shù)， $?>0,δ<1\epsilon > 0, \delta<1$ ，對所有分布 $D\mathcal{D}$ ，若存在學(xué)習(xí)算法 $L\mathcal{L}$ 和多項(xiàng)式函數(shù) $p o l y ()$ ，使得對于任何 $poly(1/\epsilon, 1/\delta, size(x), size(c))$ ， $L\mathcal{L}$ 能從假設(shè)空間中輸出滿足如下的假設(shè) $h$ ：
$\underset{h'\in\mathcal{H}}{min} E(h') \leq \epsilon) >= 1 - \delta$

PAC Learning Algorithm(PAC學(xué)習(xí)算法): 若學(xué)習(xí)算法 $L\mathcal{L}$ 使概念類 $C\mathcal{C}$ 為PAC可學(xué)，且 $L\mathcal{L}$ 的時(shí)間復(fù)雜度也是多項(xiàng)式函數(shù) $poly(1/?,1/δ,size(x),size(c))poly(1/\epsilon, 1/\delta, size(x), size(c))$ , 則稱概念類 $C$ 是高效PAC可學(xué)的， $L\mathcal{L}$ 稱概念類 $C$ 的PAC學(xué)習(xí)算法

(Sample Complexity)樣本復(fù)雜度: 滿足PAC學(xué)習(xí)算法 $L\mathcal{L}$ 所需的最小樣本數(shù)量 $poly(1/\epsilon, 1/\delta, size(x), size(c))$ ， $L\mathcal{L}$ 稱為學(xué)習(xí)算法 $L\mathcal{L}$ 的樣本復(fù)雜度

對于較為困難的學(xué)習(xí)問題，目標(biāo)概念 $c$ 往往不存在于假設(shè)空間 $H\mathcal{H}$ 中，也就是對于任何 $h∈H，E^(h)≠0h \in \mathcal{H}， \hat{E}(h) \neq 0$ , 也就是 $H\mathcal{H}$ 任意一個假設(shè)都會在訓(xùn)練集出現(xiàn)或多或少的錯誤。
先給出Hoeffding不等式: 給定 $m$ 個取值為 $[0, 1]$ 的獨(dú)立的隨機(jī)變量 $x_1, x_2,...,x_m$ ，對任意 $?>0\epsilon>0$ ，有如下等式成立：
$P(∣1m∑i=1mxi?1m∑i=1mE(xi)∣≥?)≤exp(?2m?2))P(|\frac{1}{m}\sum_{i=1}^mx_i-\frac{1}{m}\sum_{i=1}^mE(x_i)| \geq \epsilon ) \leq exp(-2m \epsilon^2))$

根據(jù)Hoeffding不等式，有如下引理：若訓(xùn)練集 $D$ 中包含 $m$ 個從分布 $D\mathcal{D}$ 上獨(dú)立同分布采樣而得到的樣本， $\epsilon <1$ ，則對于任意 $\in \mathcal{H}$ 有：

$P(E^(h)?E(h)≥?)≤exp(?2m?2)P(\hat{E}(h) - E(h) \geq \epsilon) \leq exp(-2m \epsilon^2)$ $P(E(h)?E^(h)≥?)≤exp(?2m?2)P(E(h) - \hat{E}(h) \geq \epsilon) \leq exp(-2m \epsilon^2)$ $P(∣E^(h)?E(h)∣≥?)≤2exp(?2m?2)P(|\hat{E}(h) - E(h)| \geq \epsilon) \leq 2exp(-2m \epsilon^2)$

同樣的，可以證明:若訓(xùn)練集 $D$ 中包含 $m$ 個從分布 $D\mathcal{D}$ 上獨(dú)立同分布采樣而得到的樣本，則對于任意 $\in \mathcal{H}$ , 下式至少以 $\delta$ 成立. (只需要令 $δ=2exp(?2m?2)\delta = 2exp(-2m\epsilon^2)$ 即可證明)

$E^(h)?12mln2δ<E(h)<E^(h)+12mln2δ\hat{E}(h) - \sqrt{\frac{1}{2m}ln\frac{2}{\delta}} < E(h) < \hat{E}(h) + \sqrt{\frac{1}{2m}ln\frac{2}{\delta}}$

該引理表面，當(dāng)樣本數(shù)目 $m$ 較大時(shí)， $h$ 的經(jīng)驗(yàn)誤差可以看成其泛化誤差很好的近似

需要指出的是， PAC是一種分布無關(guān)的理論模型，因?yàn)樗鼘Ψ植?span id="ze8trgl8bvbq" class="katex--inline"> $D\mathcal{D}$ 沒有任何假設(shè)， $D\mathcal{D}$ 可以是任何分布，但是訓(xùn)練集和測試集必須來自同一個分布。另外PAC考慮的是針對某個概念類 $C\mathcal{C}$ 而不是特定概念的可學(xué)性，目標(biāo)概念 $\in C$ 對于學(xué)習(xí)算法是未知的。

PAC學(xué)習(xí)中一個關(guān)鍵因素是假設(shè)空間 $H\mathcal{H}$ 的復(fù)雜度。 $H\mathcal{H}$ 越大，包含目標(biāo)概念的可能性越大，但找到某個具體目標(biāo)概念的難度也越大。 $H\mathcal{H}$ 有限時(shí)，稱 $H\mathcal{H}$ 為有限假設(shè)空間；否則為無限假設(shè)空間。有限假設(shè)空間可以用概念個數(shù)來衡量其復(fù)雜度；無限假設(shè)空間的復(fù)雜度需要一些特別的技術(shù) (VC維)。

PAC可學(xué)考慮的是學(xué)習(xí)算法 $L\mathcal{L}$ 輸出假設(shè)的泛化誤差與最優(yōu)假設(shè)泛化誤差之間的差別，由于其真實(shí)分布未知，通常無法計(jì)算。不過由于經(jīng)驗(yàn)誤差和泛化誤差有密切聯(lián)系，可以借助經(jīng)驗(yàn)誤差進(jìn)行比較。

泛化界

對于一個學(xué)習(xí)算法來說，判斷其性能好壞的依據(jù)是泛化誤差，即學(xué)習(xí)算法在未知數(shù)據(jù)上的預(yù)測能力。對于假設(shè)空間 $H\mathcal{H}$ ，可以分為有限假設(shè)空和無限假設(shè)空間，根據(jù)目標(biāo)概念 $c\mathcal{c}$ 是否在 $H\mathcal{H}$ 中可以分為 可分情形 和 不可分情形
我們來分別討論一下。

泛化誤差上界

有限假設(shè)空間

可分情形

對于可分的有限假設(shè)空間 $H\mathcal{H}$ ，目標(biāo)概念 $\in \mathcal{H}$ ，任何在訓(xùn)練集上犯錯的假設(shè)都不是要找的目標(biāo)概念，因此可以提出這些在訓(xùn)練集上出錯的假設(shè)，留下與訓(xùn)練集一致的假設(shè)。如果訓(xùn)練集足夠大，最終剩下的假設(shè)一定會很少，從而能以較大的概率找到目標(biāo)概念的近似。實(shí)際中訓(xùn)練集往往是有限的，所有會剩下不止一個與訓(xùn)練集一致的假設(shè)。在PAC學(xué)習(xí)理論中，只要訓(xùn)練集 $D$ 的大小能使學(xué)習(xí)算法 $L\mathcal{L}$ 至少以 $\delta$ 的概率找到目標(biāo)近似即可。當(dāng) $H\mathcal{H}$ 為可分的有限假設(shè)空間時(shí)，有下面的不等式成立

令 $H\mathcal{H}$ 為可分的有限假設(shè)空間， $D$ 為從 $D\mathcal{D}$ 獨(dú)立同分布采樣得到的大小為 $m$ 的訓(xùn)練集，學(xué)習(xí)算法 $L\mathcal{L}$ 基于訓(xùn)練集 $D$ 輸出與訓(xùn)練集一致的假設(shè) $\in \mathcal{H}$ , 對于 $?>0,δ<1\epsilon > 0, \delta < 1$ ，若 $\geq \frac{1}{\epsilon}(ln|\mathcal{H}| + ln\frac{1}{\delta})$ , 有
$\leq \epsilon) \geq 1 - \delta$
這表明 $H\mathcal{H}$ 為可分的有限假設(shè)空間時(shí)，學(xué)習(xí)算法輸出的泛化誤差依賴于假設(shè)空間的大小 $∣H∣|\mathcal{H}|$ 和訓(xùn)練集的大小 $m$ 。隨著訓(xùn)練集的樣本數(shù)目逐漸增加，泛化誤差的上界逐漸趨近于0, 收斂率為 $O(1m)O(\frac{1}{m})$

不可分情形

不可分情形中，目標(biāo)概念不在假設(shè)空間中，即假設(shè)空間中的每個假設(shè)都會或多或少的出現(xiàn)分類錯誤，我們的目標(biāo)則是希望找到假設(shè)空間中泛化誤差最小假設(shè)的 $?\epsilon$ 近似。對于學(xué)習(xí)算法的輸出假設(shè) $h$ 來說，泛化誤差是在未見數(shù)據(jù)上的預(yù)測能力，但是在訓(xùn)練集上的經(jīng)驗(yàn)誤差是直接可以觀察到的。當(dāng)訓(xùn)練集中樣本數(shù)目較大時(shí)， $h$ 的經(jīng)驗(yàn)誤差時(shí)泛化誤差的較好近似。

令 $H\mathcal{H}$ 為可分的有限假設(shè)空間， $D$ 為從 $D\mathcal{D}$ 獨(dú)立同分布采樣得到的大小為 $m$ 的訓(xùn)練集， $\in \mathcal{H}$ , 對于 $?>0,0<δ<1\epsilon > 0, 0<\delta < 1$ ，有
$P(∣E(h)?E^(h)∣≤ln∣H∣+ln(2/δ)2m)≥1?δP(|E(h) - \hat{E}(h)| \leq \sqrt{\frac{ln|\mathcal{H}| + ln(2/\delta)}{2m}}) \geq 1 - \delta$
這表明 $H\mathcal{H}$ 為不可分的有限假設(shè)空間時(shí)，學(xué)習(xí)算法輸出的泛化誤差依賴于假設(shè)空間的大小 $∣H∣|\mathcal{H}|$ 和訓(xùn)練集的大小 $m$ 。隨著訓(xùn)練集的樣本數(shù)目逐漸增加，收斂率為 $O(1m)O(\frac{1}{\sqrt m})$

無限假設(shè)空間

對于無限假設(shè)空間，需要從VC維和Rademacher復(fù)雜度的角度來分析泛化誤差界

有限VC維假設(shè)空間的泛化誤差

對于有限VC維的假設(shè)空間，泛化誤差的收斂率與VC維的大小有關(guān)，VC維越大，假設(shè)空間越復(fù)雜，泛化誤差收斂率越慢.

基于Rademacher復(fù)雜度的泛化誤差界

泛化誤差下界