機(jī)器學(xué)習(xí)：計(jì)算學(xué)習(xí)理論(編輯修改稿)
2025-08-28 15:04 本頁面
【文章內(nèi)容簡介】 上的邊界，我們必須考慮這 |H|個(gè)假設(shè)中任一個(gè)有較大錯(cuò)誤率的概率 22])()(Pr [ ?? mSD ehe rro rhe rro r ????? ?? ?? ? 22||)()(Pr ?? mSD eHhe r r o rhe r r o rHh ?????? 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 23 不可知學(xué)習(xí)和不一致假設(shè)（ 3） ? 將上式左邊概率稱為 ?，問多少個(gè)訓(xùn)練樣例 m才足以使 ?維持在一定值內(nèi)，求解得到 ? 式 ，適用于當(dāng)最佳假設(shè)可能有非零訓(xùn)練錯(cuò)誤率時(shí)，學(xué)習(xí)器仍能選擇到最佳假設(shè) h?H的情形。 ? ?)/1ln (||ln2 1 2 ?? ?? Hm 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 24 布爾文字的合取是 PAC可學(xué)習(xí)的 ? 我們已經(jīng)有了一個(gè)訓(xùn)練樣例數(shù)目的邊界，表示樣本數(shù)目為多少時(shí)才足以可能近似學(xué)習(xí)到目標(biāo)概念，現(xiàn)在用它來確定某些特定概念類別的樣本復(fù)雜度和 PAC可學(xué)習(xí)性 ? 考慮目標(biāo)概念類 C，它由布爾文字的合取表示。布爾文字是任意的布爾變量，或它的否定。問題： C是可 PAC學(xué)習(xí)的嗎？ ? 若假設(shè)空間 H定義為 n個(gè)布爾文字的合取，則假設(shè)空間 |H|的大小為 3n，得到關(guān)于 n布爾文字合取學(xué)習(xí)問題的樣本復(fù)雜度 ? ? ? ? 140)( 1)/1l n (3ln1 ????? ?? nm 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 25 布爾文字的合取是 PAC可學(xué)習(xí)的（ 2） ? 定理 ：布爾合取式的 PAC可學(xué)習(xí)性 –布爾文字合取的類 C是用 FindS算法 PAC可學(xué)習(xí)的 ? 證明： –式 n、 1/?和 1/?的多項(xiàng)式級，而且獨(dú)立于 size(c)。為增量地處理每個(gè)訓(xùn)練樣例， FindS算法要求的運(yùn)算量根據(jù) n線性增長，并獨(dú)立于 1/?、 1/?和 size(c)。因此這一概念類別是 FindS算法 PAC可學(xué)習(xí)的。 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 26 其他概念類別的 PAC可學(xué)習(xí)性 ? 無偏學(xué)習(xí)器（無歸納偏置） –考慮一無偏概念類 C，它包含與 X相關(guān)的所有可教授概念， X中的實(shí)例定義為 n個(gè)布爾值特征，則有 –無偏的目標(biāo)概念類在 PAC模型下有指數(shù)級的樣本復(fù)雜度 nXCH 2|| 22|||| ???? ?)/1ln (2ln21 ?? ?? nm 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 27 其他概念類別的 PAC可學(xué)習(xí)性（ 2） ? K項(xiàng) DNF和 KCNF概念 – 某概念類有多項(xiàng)式級的樣本復(fù)雜度，但不能夠在多項(xiàng)式時(shí)間內(nèi)被學(xué)習(xí)到 – 概念類 C為 k項(xiàng)析取范式（ k項(xiàng) DNF）的形式 – k項(xiàng) DNF： T1?...?Tk，其中每一個(gè) Ti為 n個(gè)布爾屬性和它們的否定的合取 – 假定 H=C，則 |H|最多為 3nk，代入式 ，得到 – 因此， k項(xiàng) DNF的樣本復(fù)雜度為 1/?、 1/?、 n和 k的多項(xiàng)式級 – 但是計(jì)算復(fù)雜度不是多項(xiàng)式級，該問題是 NP完全問題（等效于其他已知的不能在多項(xiàng)式時(shí)間內(nèi)解決的問題） – 因此，雖然 k項(xiàng) DNF有多項(xiàng)式級的樣本復(fù)雜度，它對于使用H=C的學(xué)習(xí)器沒有多項(xiàng)式級的計(jì)算復(fù)雜度 ? ?)/1ln (3ln1 ?? ?? nkm 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 28 其他概念類別的 PAC可學(xué)習(xí)性（ 3） – 令人吃驚的是，雖然 k項(xiàng) DNF不是 PAC可學(xué)習(xí)的，但存在一個(gè)更大的概念類是 PAC可學(xué)習(xí)的 – 這個(gè)更大的概念類是 KCNF，它有每樣例的多項(xiàng)式級時(shí)間復(fù)雜度，又有多項(xiàng)式級的樣本復(fù)雜度 – KCNF：任意長度的合取式 T1?...?Tj，其中每個(gè) Ti為最多 k個(gè)布爾變量的析取 – 容易證明 KCNF包含了 K項(xiàng) DNF，因此概念類 k項(xiàng)DNF是使用 H=KCNF的一個(gè)有效算法可 PAC學(xué)習(xí)的 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 29 無限假設(shè)空間的樣本復(fù)雜度 ? 式子 |H|刻畫樣本復(fù)雜度有兩個(gè)缺點(diǎn)： – 可能導(dǎo)致非常弱的邊界 – 對于無限假設(shè)空間的情形，無法應(yīng)用 ? 本節(jié)考慮 H的復(fù)雜度的另一種度量，稱為 H的VapnikChervonenkis維度（簡稱 VC維或 VC(H)） ? 使用 VC維代替 |H|也可以得到樣本復(fù)雜度的邊界，基于 VC維的樣本復(fù)雜度比 |H|更緊湊，另外還可以刻畫無限假設(shè)空間的樣本復(fù)雜度 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 30 打散一個(gè)實(shí)例集合 ? VC維衡量假設(shè)空間復(fù)雜度的方法不是用不同假設(shè)的數(shù)量 |H|，而是用 X中能被 H徹底區(qū)分的不同實(shí)例的數(shù)量 ? S是一個(gè)實(shí)例集， H中每個(gè) h導(dǎo)致 S的一個(gè)劃分，即 h將 S分割為兩個(gè)子集 {x?S|h(x)=1}和 {x?S|h(x)=0} ? 定義：一實(shí)例集 S被假設(shè)空間 H打散，當(dāng)且僅當(dāng)對 S的每個(gè)劃分，存在 H中的某假設(shè)與此劃分一致 ? 如果一實(shí)例集合沒有被假設(shè)空間打散，那么必然存在某概念可被定義在實(shí)例集之上，但不能由假設(shè)空間表示 ? H的這種打散實(shí)例集合的能力是其表示這些實(shí)例上定義的目標(biāo)概念的能力的度量 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 31 VapnikChervonenkis維度 ? 打散一實(shí)例集合的能力與假設(shè)空間的歸納偏置緊密相關(guān) ? 無偏的假設(shè)空間能夠打散所有實(shí)例組成的集合 X ? 直觀上，被打散的 X的子集越大， H的表示能力越強(qiáng) ? 定義：定義在實(shí)例空間 X上的假設(shè)空間 H的 VapnikChervonenkis維，是可被 H打散的 X的最大有限子集的大小 ? 如果 X的任意有限大的子集可被 H打散，則 VC(H)=? 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 32 VapnikChervonenkis維度（ 2） ? 對于任意有限的 H， VC(H)=log2|H| ? VC維舉例 – 假定實(shí)例空間 X為實(shí)數(shù)集合，而且 H為實(shí)數(shù)軸上的區(qū)間的集合，問 VC(H)是多少？ ? 只要找到能被 H打散的 X的最大子集，首先包含 2個(gè)實(shí)例的集合能夠被 H打散，其次包含 3個(gè)實(shí)例的集合不能被 H打散，因此 VC(H)=2 – 實(shí)例集合 S對應(yīng) x、 y平面上的點(diǎn)，令 H為此平面內(nèi)所有線性決策面的集合，問 H的 VC維是多少？ ? 能夠找到 3個(gè)點(diǎn)組成的集合，被 H打散，但無法找到能夠被H打散的 4個(gè)點(diǎn)組成的集合，因此 VC(H)=3 ? 更一般地，在 r維空間中，線性決策面的 VC維為 r+1 機(jī)器學(xué)習(xí) 計(jì)算學(xué)習(xí)理論 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 33 VapnikChervonenkis維度（ 3） – 假定 X上每個(gè)實(shí)例由恰好 3個(gè)布爾文字的合
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1