1. 章節(jié)主要內(nèi)容
機(jī)器學(xué)習(xí)理論（computational learning theory）研究的是關(guān)于通過“計(jì)算”來進(jìn)行“學(xué)習(xí)”的理論摘仅，即關(guān)于機(jī)器學(xué)習(xí)的理論基礎(chǔ)，其目的是分析學(xué)習(xí)任務(wù)的困難本質(zhì)石蔗，為學(xué)習(xí)算法提供理論保證，并根據(jù)分析結(jié)果指導(dǎo)算法設(shè)計(jì)畅形。
這章內(nèi)容相對比較抽象养距，它關(guān)注的更多是算法能產(chǎn)生的數(shù)據(jù)與結(jié)果之間的映射與實(shí)際映射的貼近程度和穩(wěn)定程度，而不是具體的算法的優(yōu)劣日熬。這是一個(gè)在更高層面審視機(jī)器學(xué)習(xí)算法有效性的理論棍厌，所以在學(xué)習(xí)這章內(nèi)容之前，我們要設(shè)定好這樣的認(rèn)知竖席，那就是文章中提到的算法是各種算法的抽象耘纱，請用一個(gè)整體的概念去閱讀和理解這章的內(nèi)容。
1）概率近似正確（Probably Approximately Correct毕荐，簡稱PAC）學(xué)習(xí)理論
計(jì)算學(xué)習(xí)理論中最基本的是概率近似正確束析，在學(xué)習(xí)概率近似正確理論之前，我們先理解以下這些定義：
［1］“概念”（concept）：令 c 表示概念憎亚，它代表從樣本空間 X 到標(biāo)記空間 Y 的映射员寇。若對任何樣例（x, y）有 c(x) = y 成立，則稱 c 為目標(biāo)概念第美。所有目標(biāo)概念的集合稱為“概念類”（concept class）蝶锋，用符號(hào) C 表示。
［2］“假設(shè)空間”（hypothesis space）：給定學(xué)習(xí)算法 A斋日，它所考慮的所有可能概念的集合稱為假設(shè)空間牲览，用符號(hào) H 表示。對于假設(shè)空間中的任一概念恶守，我們用符號(hào) h 表示第献，由于并不能確定它是否真是目標(biāo)概念，因此稱為“假設(shè)”（hypothesis）兔港。
［3］“可分的”（separable）：由于學(xué)習(xí)算法事先并不知道概念類的真實(shí)存在庸毫，因此 H 和 C 通常是不同的。若目標(biāo)概念 c 屬于 H衫樊，則說明 H 中存在假設(shè)能將所有示例按于真實(shí)標(biāo)記一致的方式完全分開飒赃，我們稱該問題對學(xué)習(xí)算法 A 是“可分的”（separable），亦稱“一致的”（consistent）科侈；反之载佳，若 c 不屬于 H，則稱該問題對學(xué)習(xí)算法 A 是“不可分的”（non-separable）臀栈，亦稱“不一致的”（non-consistent）
給定訓(xùn)練集D蔫慧，我們訓(xùn)練機(jī)器學(xué)習(xí)模型的目的就是希望基于學(xué)習(xí)算法 A 學(xué)得的模型所對應(yīng)的假設(shè) h 盡可能的接近目標(biāo)概念 c。這種希望以較大概率學(xué)得誤差滿足預(yù)設(shè)上限的模型权薯，就是“概率”“近似正確”的含義姑躲。
在清楚了上邊的概念后睡扬，給定置信度 t，誤差參數(shù) e黍析，我們有如下定義：
［1］PAC辨識(shí)（PAC Identify）：對 0 < t, e < 1卖怜，所有 c 屬于 C 和分布D,若存在學(xué)習(xí)算法 A，其輸出假設(shè) h 使得泛化誤差 E(h) 小于 e 的概率大于置信空間 1 - t阐枣，那么我們說學(xué)習(xí)算法能從假設(shè)空間 H 中 PAC 辨識(shí)概念類 C
［2］PAC可學(xué)習(xí)（PAC Learnable）：令 m 是從分布D中獨(dú)立同分布采樣的樣例數(shù)目马靠，?0 < t, e < 1，所有 c 屬于 C 和分布D,若存在學(xué)習(xí)算法 A 和多項(xiàng)式函數(shù) poly(.,.,.,.)侮繁，使得對于任意 m >= poly(1/e, 1/t, size(X), size(c))虑粥，A能從假設(shè)空間 H 中 PAC辨識(shí)出概念類 C，則稱概念類 C 對假設(shè)空間 H 而言是PAC可學(xué)習(xí)的
［3］PAC學(xué)習(xí)算法（PAC Learning Algorithm）：若學(xué)習(xí)算法 A 使概念類 C 為PAC可學(xué)習(xí)宪哩，且 A 的運(yùn)行時(shí)間也是多項(xiàng)式函數(shù)??poly(1/e, 1/t, size(X), size(c)) 娩贷，則稱概念類 C 是高效 PAC可學(xué)習(xí)（efficiently PAC learnable）的，稱 A 為概念類 C 的PAC學(xué)習(xí)算法
假定學(xué)習(xí)算法對每個(gè)樣本的處理時(shí)間為常數(shù)锁孟，則算法的時(shí)間復(fù)雜度等同于樣本復(fù)雜度彬祖。于是我們對算法的時(shí)間復(fù)雜度的關(guān)心轉(zhuǎn)換為對樣本復(fù)雜度的關(guān)心
［4］樣本復(fù)雜度（Sample Complexity）：滿足PAC學(xué)習(xí)算法 A 所需的??m >= poly(1/e, 1/t, size(X), size(c)) 中最小的 m，稱為算法 A 的樣本復(fù)雜度
上邊的四個(gè)概念乍看下來有點(diǎn)繞口品抽，其實(shí)轉(zhuǎn)換為以下表述理解起來應(yīng)該就簡單一些了：
如果算法 A 足夠優(yōu)秀储笑，使得誤差大概率情況下（在置信空間 1-t范圍內(nèi)）足夠小（誤差小于誤差參數(shù) e）圆恤，那么目標(biāo)概念類 C 對于算法 A 來說是PAC可辨識(shí)的突倍；
如果采樣數(shù)目 m 大于一定值時(shí)（多項(xiàng)式函數(shù)poly），概念類 C 一定能被 A PAC辨識(shí)盆昙，那么概念類 C 對于算法 A 來說是PAC可學(xué)習(xí)的羽历；
如果此時(shí)算法 A 的時(shí)間復(fù)雜度也在一定范圍內(nèi)（多項(xiàng)式函數(shù) poly）時(shí)，算法A就是概念類 C 的PAC學(xué)習(xí)算法淡喜；
PAC學(xué)習(xí)算法 A 所需的最小樣本數(shù) m 被稱為算法 A 的樣本復(fù)雜度
顯然秕磷，PAC學(xué)習(xí)給出了一個(gè)抽象地刻畫機(jī)器學(xué)習(xí)能力的框架，基于這個(gè)框架能對很多重要的問題進(jìn)行理論探討炼团，例如研究某任務(wù)在什么樣的條件下可學(xué)得較好的模型澎嚣？某算法在怎樣的條件下可進(jìn)行有效的學(xué)習(xí)？需多少訓(xùn)練樣例才能獲得較好的模型瘟芝？
PAC學(xué)習(xí)中的一個(gè)關(guān)鍵因素是假設(shè)空間 H 的復(fù)雜度易桃，一般而言，H 越大其包含任意目標(biāo)概念的概率也越大锌俱，但從中找到某個(gè)具體的目標(biāo)概念的難度也越大颈抚。
下邊我們將根據(jù) |H| 是否有限來分別討論機(jī)器學(xué)習(xí)理論的具體研究過程。
2）有限假設(shè)空間的可學(xué)習(xí)性研究
［1］可分情況
可分情況意味著目標(biāo)概念 c 屬于假設(shè)空間 H 嚼鹉，那么給定 m 個(gè)樣本的訓(xùn)練集 D贩汉，一個(gè)簡單的學(xué)習(xí)策略是：既然 D 中的樣本標(biāo)記都是由 c 賦予的，并且 c 存在于假設(shè)空間 H 中锚赤，那么任何在 D 上出現(xiàn)標(biāo)記錯(cuò)誤的假設(shè)肯定不是目標(biāo)概念 c
于是我們只需要保留與 D 一致的假設(shè)即可匹舞，當(dāng) D 足夠大時(shí)，剩余的假設(shè)越來越少线脚，最終只會(huì)剩下目標(biāo)概念 c赐稽。但是通常情況下，D 的大小是有限的浑侥，而我們只需要找到目標(biāo)概念的有效近似姊舵，所以當(dāng)學(xué)習(xí)算法 A 能達(dá)到PAC可學(xué)習(xí)即可。
實(shí)際上寓落，有限假設(shè)空間 H 都是PAC可學(xué)習(xí)的括丁，所需樣例數(shù)目如下式所示，輸出假設(shè) h 的泛化誤差隨樣例數(shù)目的增加而收斂到 0伶选，收斂速度為O(1/m)
［2］不可分情況
對較為困難的學(xué)習(xí)問題史飞，目標(biāo)概念 c 往往不存在于假設(shè)空間 H 中。對于不可分的情況仰税，假設(shè)空間 H 的任意一個(gè)假設(shè) h 在訓(xùn)練樣本 D 上都可能會(huì)出現(xiàn)或多或少的錯(cuò)誤构资。
當(dāng) c 不屬于 H 時(shí)，學(xué)習(xí)算法 A 無法學(xué)得目標(biāo)概念 c 的 e 近似陨簇。但是當(dāng)假設(shè)空間 H 給定時(shí)吐绵，其中必定存在一個(gè)泛化誤差最小的假設(shè)，找出此假設(shè)的 e 近似也不失為一個(gè)較好的目標(biāo)河绽。
于是以此為目標(biāo)己单，可以將PAC學(xué)習(xí)推廣到不可分情況，這稱為“不可知PAC學(xué)習(xí)”（agnostic PAC learning）：令 m 是從分布D中獨(dú)立同分布采樣的樣例數(shù)目葵姥，?0 < t, e < 1荷鼠，對所有分布D，若存在學(xué)習(xí)算法 A 和多項(xiàng)式函數(shù)poly(.,.,.,.)榔幸，使得對于任意 m >= poly(1/e, 1/t, size(X), size(c))允乐，A能從假設(shè)空間 H 中找到假設(shè) h，使其泛化誤差 E(h) 與最小泛化誤差 E(h') 的差小于 e 的概率大于置信空間 (1 - t)削咆，則稱假設(shè)空間 H 是不可知PAC可學(xué)習(xí)的
3）無限假設(shè)空間的可學(xué)習(xí)性研究 － VC維
現(xiàn)實(shí)學(xué)習(xí)任務(wù)所面臨的常常是無限假設(shè)空間牍疏，比如 SVM、神級(jí)網(wǎng)絡(luò)等拨齐，前者的假設(shè)空間是 d 維空間上的所有線性超平面鳞陨，后者的假設(shè)空間可以是實(shí)數(shù)域中的所有區(qū)間。欲對這種情況的可學(xué)習(xí)性進(jìn)行研究，需度量假設(shè)空間的復(fù)雜度厦滤。最常見的方法是考慮假設(shè)空間的“VC維”（Vapnik-Chervonenkis Dimension）
介紹VC維之前援岩，我們再引入幾個(gè)概念：
［1］增長函數(shù)（growth function）：增長函數(shù)表示假設(shè)空間 H 對 m 個(gè)示例所能賦予標(biāo)記的最大可能結(jié)果數(shù) n 的映射關(guān)系。
對于二分類問題（結(jié)果只有0掏导、1兩個(gè)）享怀，若 m=2，有a趟咆，b兩個(gè)樣例添瓷，則賦予標(biāo)記的可能結(jié)果最大為4種：a=0,b=0; a=1,b=1; a=0,b=1; a=1,b=0。以此類推當(dāng) m=3 時(shí)值纱，則可能有8種鳞贷。但是，這只是最優(yōu)情況虐唠，很多時(shí)候假設(shè)空間所能賦予的最大可能結(jié)果數(shù)不是 2 的 m 次方搀愧。
顯然，H 對示例所能賦予的可能結(jié)果數(shù)越大凿滤，H 的表示能力越強(qiáng)妈橄，對學(xué)習(xí)任務(wù)的適應(yīng)能力也越強(qiáng)。因此翁脆，增長函數(shù)描述了假設(shè)空間 H 的表示能力眷蚓，由此反映出了假設(shè)空間的復(fù)雜度
［2］對分（dichotomy）：對于二分類問題來說，H 中的假設(shè)對 D 中示例賦予標(biāo)記的每種可能結(jié)果稱為對 D 的一種對分
［3］打散（shattering）：若假設(shè)空間 H 能實(shí)現(xiàn)示例集 D 上的所有對分反番，即對于 m 個(gè)示例的樣本集 D 的增長函數(shù)等于 2 的 m 次方沙热，則稱示例集 D 能被假設(shè)空間 H 打散
在清晰了以上概念后，我們可以正式定義VC維了：
假設(shè)空間 H 的VC維是能被 H 打散的最大示例集的大小罢缸，記作 VC( H )
VC( H ) = d 表明存在大小為 d 的示例集能被假設(shè)空間 H 打散篙贸，但是需注意：這并不代表所有大小為 d 的示例集都能被空間 H 打散。除此之外枫疆，VC維還有一個(gè)特點(diǎn)爵川，那就是它與數(shù)據(jù)分布D無關(guān)！因此數(shù)據(jù)分布未知時(shí)我們也可以算出假設(shè)空間 H 的VC維
舉個(gè)例子來加深理解一下息楔，對于二維平面的線性劃分學(xué)習(xí)任務(wù)寝贡，令假設(shè)空間 H 表示二維平面上所有的線性劃分所構(gòu)成的集合，輸入屬性 X 是二維平面的坐標(biāo)值依，輸出標(biāo)簽 Y 是根據(jù) X 坐標(biāo)相對應(yīng)假設(shè) h 的位置而定的圃泡，被線性劃分到一邊的被歸為一類，另一邊的被歸為另一類愿险。由下圖可知颇蜡，存在大小為 3 的示例集可被 H 打散，但不存在大小為 4 的示例集可被 H 打散。于是风秤，該假設(shè)空間 H 的 VC 維為 3
因?yàn)樵鲩L函數(shù)反映出假設(shè)空間的復(fù)雜度鳖目，我們可利用增長函數(shù)來估計(jì)經(jīng)驗(yàn)誤差與泛化誤差之間的關(guān)系（具體關(guān)系請參閱[Vapnik and Chervonenkis, 1971]），而通過VC維的定義我們知道VC維與增長函數(shù)有密切的關(guān)系唁情，確切的說我們可以根據(jù) VC 維的大小 d 來確定假設(shè)空間增長函數(shù)的上界疑苔。
于是乎我們可通過 VC 維來估計(jì)經(jīng)驗(yàn)誤差與泛化誤差之間的關(guān)系，具體關(guān)系如下圖定理12.3所示：
不用管那些復(fù)雜的嵌套關(guān)系甸鸟、平方根、指數(shù)函數(shù)兵迅、概率分布抢韭、置信值等內(nèi)容，從定理12.3我們只需要知道一個(gè)最重要的一點(diǎn)恍箭，那就是：泛化誤差界只與樣例數(shù)目 m 有關(guān)刻恭，與數(shù)據(jù)分布D和樣例集 D 無關(guān)。因此扯夭，基于 VC 維的泛化誤差界是分布無關(guān)（distribution-free）鳍贾、數(shù)據(jù)獨(dú)立（data-independent）的
在此基礎(chǔ)上，我們可得下邊這個(gè)重要的定理：
任何 VC 維有限的假設(shè)空間 H 都是（不可知）PAC可學(xué)習(xí)的
4）考慮數(shù)據(jù)分布情況下的無限假設(shè)空間可學(xué)習(xí)性研究 － Rademacher復(fù)雜度
基于 VC 維的泛化誤差界是分布無關(guān)交洗、數(shù)據(jù)獨(dú)立的骑科，也就是說對于任意的數(shù)據(jù)分布都成立。這使得基于 VC 維的可學(xué)習(xí)性分析結(jié)果具有一定的“普適性”构拳；但從另一方面來說咆爽，由于沒有考慮數(shù)據(jù)自身，基于 VC 維得到的泛化誤差界通常比較“松”置森，對那些與學(xué)習(xí)問題的典型情況相差甚遠(yuǎn)的較“壞”分布來說尤其如此
Rademacher復(fù)雜度是另一種刻畫假設(shè)空間復(fù)雜度的途徑斗埂，與 VC 維不同，它在一定程度上考慮了數(shù)據(jù)分布
在介紹Rademacher復(fù)雜度前凫海，我們先回顧一下機(jī)器學(xué)習(xí)的性能體現(xiàn)在哪里呛凶？機(jī)器學(xué)習(xí)算法的性能體現(xiàn)在其泛化誤差足夠小，但是現(xiàn)實(shí)中泛化誤差往往無法求行贪，所以我們只能用經(jīng)驗(yàn)誤差來進(jìn)行近似漾稀！
考慮現(xiàn)實(shí)情況中噪音可能對假設(shè)空間的性能影響，在訓(xùn)練集上表現(xiàn)最好的假設(shè)有時(shí)還不如已考慮了隨機(jī)噪音的假設(shè)瓮顽，所以Rademacher 復(fù)雜度計(jì)算直接引入了 Rademacher 隨機(jī)變量來代替訓(xùn)練樣本中的標(biāo)記县好，它以 0.5 的概率為 -1，0.5 的概率為 +1暖混。
在一個(gè)確定的訓(xùn)練集上缕贡，經(jīng)驗(yàn) Rademacher 復(fù)雜度其實(shí)計(jì)算的是假設(shè)空間 H 與隨機(jī)噪音相關(guān)性的期望，這個(gè)值越大，則說明假設(shè)空間與隨機(jī)噪音擬合地越好晾咪，也說明這個(gè)假設(shè)空間越復(fù)雜收擦。
假設(shè)訓(xùn)練集樣本采樣自分布D，則?Rademacher 復(fù)雜度是分布D上的經(jīng)驗(yàn) Rademacher 復(fù)雜度的期望
于是通過?Rademacher 復(fù)雜度谍倦，我們可以計(jì)算出基于Rademacher 復(fù)雜度的泛化誤差界
5）穩(wěn)定性（stability）
無論是基于 VC 維還是?Rademacher 復(fù)雜度來推導(dǎo)泛化誤差界塞赂，所得到的結(jié)果均與具體學(xué)習(xí)算法無關(guān)，對所有的學(xué)習(xí)算法都適用昼蛀。這使得人們能夠脫離具體的學(xué)習(xí)算法的設(shè)計(jì)來考慮學(xué)習(xí)問題本身的性質(zhì)宴猾，但在另一方面，若希望獲得與算法有關(guān)的分析結(jié)果叼旋，則需另辟蹊徑仇哆。穩(wěn)定性分析是這方面一個(gè)值得關(guān)注的方向
算法“穩(wěn)定性”考察的是算法在輸入發(fā)生變化時(shí)，輸出是否會(huì)隨之發(fā)生較大的變化夫植。令 AD 表示學(xué)習(xí)算法 A 在訓(xùn)練集 D 上學(xué)得的假設(shè)讹剔，L( AD, z ) 為損失函數(shù)，表示假設(shè) AD 對輸入 z = (x,y) 的映射 AD(x) 與真實(shí)的映射 y 之間的差值详民。
再次的延欠，要繼續(xù)理解穩(wěn)定性對于機(jī)器學(xué)習(xí)理論的作用，我們先了解一下下邊的定義與定理
［1］算法均勻穩(wěn)定性
假設(shè) AD 為學(xué)習(xí)算法 A?在訓(xùn)練集 D 上學(xué)得的假設(shè)沈跨，AD'??在訓(xùn)練集 D' 上學(xué)得的假設(shè)由捎，其中 D' 為從 D 中移除了一個(gè)樣本的新的訓(xùn)練集。若對于任意的 z = (x,y)谒出，| L( AD, z ) - L( AD', z ) | < B隅俘，則稱學(xué)習(xí)算法 A 關(guān)于損失函數(shù) L 滿足 B-均勻穩(wěn)定性
［2］若損失函數(shù)有界 M，則對于任意的 z = (x,y)笤喳，有 0 <=?L( AD, z ) <= M
［3］基于穩(wěn)定性分析的泛化誤差界
給定從分布 D 上獨(dú)立同分布采樣得到的大小為 m 的示例集为居，若學(xué)習(xí)算法 A 關(guān)于損失函數(shù) L 滿足 B-均勻穩(wěn)定性，且損失函數(shù)的上界為 M杀狡，則可以學(xué)得學(xué)習(xí)算法 A 的泛化誤差界
［4］經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化（Empirical Risk Minimization）原則
對損失函數(shù) L蒙畴，若學(xué)習(xí)算法 A 所輸出的假設(shè)的損失等于其所在假設(shè)空間的最小損失，則稱算法 A 是ERM的
綜上呜象，我們可以得到穩(wěn)定性與假設(shè)空間可學(xué)習(xí)性的關(guān)系：
若學(xué)習(xí)算法 A 是ERM且穩(wěn)定的膳凝，則假設(shè)空間 H 可學(xué)習(xí)
2. 基礎(chǔ)知識(shí)
1）獨(dú)立同分布（independent and identically distributed，簡稱 i.i.d. ）
在概率統(tǒng)計(jì)理論中恭陡，指隨機(jī)過程中蹬音，任何時(shí)刻的取值都為隨機(jī)變量，如果這些隨機(jī)變量服從同一分布休玩，并且互相獨(dú)立著淆，那么這些隨機(jī)變量是獨(dú)立同分布
2）上確界
上確界是一個(gè)集合的最小上界劫狠。具體到數(shù)學(xué)分析中。一個(gè)實(shí)數(shù)集合A永部，若有一個(gè)實(shí)數(shù)M独泞，使得A中任何數(shù)都不超過M，那么就稱M是A的一個(gè)上界苔埋。在所有那些上界中如果有一個(gè)最小的上界懦砂，就稱為A的上確界
3）多項(xiàng)式函數(shù) poly()
多項(xiàng)式函數(shù) poly() 返回的是一個(gè)多項(xiàng)式，假定輸入 n 個(gè)參數(shù)组橄，第 i 個(gè)參數(shù)的值代表變量的第( n - i )項(xiàng)式的倍數(shù)荞膘，比如 poly(2, -1, 3, 1) = 2x^3 - x^2 + 3x + 1
3. 總結(jié)
1）機(jī)器學(xué)習(xí)理論研究的是關(guān)于通過“計(jì)算”來進(jìn)行“學(xué)習(xí)”的理論，即關(guān)于機(jī)器學(xué)習(xí)的理論基礎(chǔ)晨炕，其目的是分析學(xué)習(xí)任務(wù)的困難本質(zhì)衫画，為學(xué)習(xí)算法提供理論保證，并根據(jù)分析結(jié)果指導(dǎo)算法設(shè)計(jì)
2）機(jī)器學(xué)習(xí)理論研究的一個(gè)關(guān)鍵是研究算法對應(yīng)的假設(shè)空間是否是可學(xué)習(xí)的
3）對于具體的假設(shè)空間瓮栗，其可學(xué)習(xí)性是指該假設(shè)空間是否滿足其泛化誤差小于誤差參數(shù)的概率在置信空間內(nèi)
3）通過分析不同情況下假設(shè)空間的泛化誤差界的范圍，可以了解該假設(shè)空間是否可學(xué)習(xí)
4）對于有限假設(shè)空間瞄勾，可以根據(jù) PAC 學(xué)習(xí)理論來分析假設(shè)空間的可學(xué)習(xí)性
5）對于無限假設(shè)空間费奸，我們通過 VC 維分析來度量假設(shè)空間的復(fù)雜度，并可知任何 VC 維有限的假設(shè)空間 H 都是（不可知）PAC可學(xué)習(xí)的
6）基于 VC 維的泛化誤差界是分布無關(guān)（distribution-free）进陡、數(shù)據(jù)獨(dú)立（data-independent）的
7）Rademacher復(fù)雜度在 VC 維的基礎(chǔ)上考慮了數(shù)據(jù)樣本分布D
8）在一個(gè)確定的訓(xùn)練集上愿阐，經(jīng)驗(yàn) Rademacher 復(fù)雜度其實(shí)計(jì)算的是假設(shè)空間 H 與隨機(jī)噪音相關(guān)性的期望，這個(gè)值越大趾疚，則說明假設(shè)空間與隨機(jī)噪音擬合地越好缨历，也說明這個(gè)假設(shè)空間越復(fù)雜
9）假設(shè)訓(xùn)練集樣本采樣自分布D，則?Rademacher 復(fù)雜度是分布D上的經(jīng)驗(yàn) Rademacher 復(fù)雜度的期望
10）穩(wěn)定性分析是希望基于具體學(xué)習(xí)算法的設(shè)計(jì)來考慮學(xué)習(xí)問題本身的性質(zhì)
11）算法“穩(wěn)定性”考察的是算法在輸入發(fā)生變化時(shí)糙麦，輸出是否會(huì)隨之發(fā)生較大的變化
12）若學(xué)習(xí)算法 A 是ERM且穩(wěn)定的辛孵，則假設(shè)空間 H 可學(xué)習(xí)
