Lec 4：Feasibility of Learning
上一章中我們介紹了各種各樣的機(jī)器學(xué)習(xí)，本門課的著重點(diǎn)是binary classification or regression from a batch of supervised data with concrete features.
這一章（實(shí)際還要加上接下來(lái)的Lec6和7）介紹機(jī)器學(xué)習(xí)是不是可行的筋量？湖苞！這是個(gè)有趣的問(wèn)題（＾_＾）機(jī)器學(xué)習(xí)當(dāng)前如此熱門拯欧，答案當(dāng)然是可行的，但你不一定知道它為什么可行２乒恰镐作？個(gè)人認(rèn)為藏姐，機(jī)器學(xué)習(xí)的可行性問(wèn)題，或者說(shuō)是理論保障该贾，是設(shè)計(jì)機(jī)器學(xué)習(xí)算法以及techniques的根本出發(fā)點(diǎn)羔杨！
Tips：符號(hào)含義請(qǐng)參照Lec1
1，Learning is impossible杨蛋？
第一節(jié)的幾個(gè)小栗子告訴我們兜材，我們從已知的data（D）中學(xué)到的完美的g很可能會(huì)不適用于未知的data（outside D），而預(yù)測(cè)未來(lái)的data又是機(jī)器學(xué)習(xí)的目的逞力。那么機(jī)器學(xué)習(xí)是不是不可行呢护姆？
2注祖、Inferring something unknown & 霍夫丁不等式
我們可以想一想有沒(méi)有推測(cè)未知事情的場(chǎng)景熊泵？袖外！學(xué)過(guò)概率論的一定都接觸過(guò)忿等。舉一個(gè)具體的例子：有一個(gè)裝了很多很多橘色和綠色彈珠的罐子舔涎，我們知道橘色占的比例嗎褒墨？不知道敬肚。但是我們可以推測(cè)（infer）橘色占的比例嗎菜循？可以捅膘！這類問(wèn)題在統(tǒng)計(jì)學(xué)中很常見(jiàn)添祸。如何infer？
假設(shè)橘色罐子中的實(shí)際比例是?μ寻仗。?獨(dú)立隨機(jī)抽取樣本sample刃泌，在sample中橘色比例是v，則綠色比例是1-v署尤。統(tǒng)計(jì)學(xué)中耙替，in-sample 的v跟out-of-sample的μ大部分時(shí)候是接近的。抽取sample的大小用N表示曹体。
這件事情在數(shù)學(xué)中的描述是：
這個(gè)不等式的含義是俗扇，當(dāng)N很大時(shí)，v和μ相差ε（誤差范圍）的概率很小箕别，這就是著名的“霍夫丁不等式”Hoeffding‘s Inequality铜幽。我們說(shuō)“v = μ”這個(gè)式子是probably approximately correct（PAC），大概差不多是對(duì)的串稀。
關(guān)于霍夫丁不等式：
1）對(duì)任意N和ε都成立除抛；
2）不需要知道 μ；
3）當(dāng)N larger母截、looser gap ε（較大的容忍度）到忽，那么 v ≈ μ的概率會(huì)higher；
因此微酬，如果sample夠大的話绘趋，我們可以通過(guò)v infer μ（概率論知識(shí)）颤陶。
這個(gè)不等式十分重要～個(gè)人認(rèn)為它是機(jī)器學(xué)習(xí)最基本的理論保障～
3、Connection to learning
上一節(jié)中關(guān)于彈珠和概率等等的介紹和機(jī)器學(xué)習(xí)有什么關(guān)系呢陷遮？
針對(duì)一個(gè)h滓走，可以把抽到橘色情況看作是wrong，即h（x）≠ f（x）帽馋，對(duì)應(yīng)地綠色代表right搅方，即h（x）= f（x）。那么 μ 就是Eout（h）绽族，v就是Ein（h）姨涡。這樣我們可以通過(guò)已知的Ein推測(cè)未知的 Eout “陕霍夫丁不等式可以寫作
與前面類似涛漂，“Ein（h）= Eout（h）”是PAC。如果Ein（h）≈ Eout（h）并且Ein較小检诗，就能推出Eout（h）較小匈仗，從而推出h≈f，我們可以依據(jù)Ein的大小verify某個(gè)h逢慌。至此悠轩，這些理論只能用來(lái)判斷某個(gè)h的好壞，真正的機(jī)器學(xué)習(xí)還需要用算法A從H中選出一個(gè)“good”h作為g.
4攻泼、Multiple h
上一小節(jié)中對(duì)一個(gè)h進(jìn)行討論得出verify h的準(zhǔn)則火架，這節(jié)考慮一下在很多個(gè)h中做選擇的情況，霍夫丁不等式會(huì)是什么作用忙菠？
抽樣存在很多情況何鸡，難免出現(xiàn)Bad sample（Ein和Eout相差很大的sample）≈桓椋霍夫丁不等式說(shuō)明針對(duì)一個(gè)h出現(xiàn)bad sample的幾率很小音比。但是當(dāng)有很多個(gè)h時(shí)，bad data就很可能出現(xiàn)（如課件中拋硬幣的例子）氢惋，當(dāng)bad sample的Ein又很小時(shí)，我們作出選擇時(shí)就會(huì)worse情況稽犁。Bad sample也就是Bad Data焰望。
霍夫丁不等式是針對(duì)某個(gè)h成立，它表示對(duì)于一個(gè)h來(lái)說(shuō)已亥，bad data出現(xiàn)的幾率small熊赖。
當(dāng)有很多h時(shí)，出現(xiàn)bad data的概率上限可以使用“聯(lián)級(jí)上限”union bound獲得虑椎。M=|H|震鹉，即hypothesis set的size（在下一章Lec5中我們將看到這個(gè)上限實(shí)際上很loose）俱笛。
由上式可以知道：
1）當(dāng)M有限大時(shí)，如果N足夠大传趾，A選出的任意g都會(huì)有Eout（g）≈ Ein（g）迎膜，如果Ein（g）≈ 0，Eout（g）≈ 0是PAC的浆兰，學(xué)習(xí)有效磕仅，learning is feasible！
2）But當(dāng)M無(wú)限大時(shí)簸呈，boom榕订！如Perceptrons（注意：這里不是PLA，是Perceptrons蜕便。PLA是算法劫恒，Perceptrons才是H）。接下來(lái)將需要Lec5～Lec7三章內(nèi)容揭秘類似Perceptrons情況的可行性問(wèn)題轿腺。歡迎繼續(xù)學(xué)習(xí)两嘴！
