Tips：未進(jìn)行說(shuō)明的符號(hào)主要參照Lec 1 ，部分參照其他Lec.
上一節(jié)介紹了ML中非常重要的工具VC Dimension纫版，說(shuō)明了learning發(fā)生的理論保障和一些條件：當(dāng)dvc有限、N足夠大碗短、Ein較低時(shí)魁衙，learning 可行。
這節(jié)將從data出發(fā)巫俺，介紹存在noise和error時(shí)會(huì)是怎樣的情況认烁？之前的理論是否可以放寬到這種情況？
Lec 8：Noise and Error
1、Noise and Probabilistic Target
之前Pocket里面有提到noise却嗡，noise來(lái)源有三點(diǎn)：1）來(lái)自錯(cuò)誤標(biāo)記y舶沛；2）同一個(gè)x有兩個(gè)不同的y；3）x不正確稽穆；?
存在Noise的時(shí)候冠王，VC Bound是否還有效呢？?
回顧一下小球問(wèn)題舌镶，小球x～P（x）柱彻，抽出小球的顏色是確定的，橘色代表 f（x）≠ h（x）餐胀；綠色代表 f（x）= h（x）哟楷；
現(xiàn)在有noise是怎么樣的？小球x～P（x）否灾，不同的是當(dāng)抽出小球時(shí)卖擅，小球的顏色并不是確定的，但顏色也會(huì)存在一種分布distribution墨技，如何獲得惩阶？sample！表示為 y～P（y|x）扣汪；
在x～P（x）断楷，y～P（y|x）的情況下重新證明VC Bound，任然會(huì)是成立的崭别，不給出證明冬筒。
實(shí)際上，只要訓(xùn)練&測(cè)試的（x茅主，y）來(lái)自同一個(gè)P舞痰，則VC Bound可以work.
現(xiàn)在學(xué)習(xí)的目標(biāo)不是target function，而是target distribution P（y|x）诀姚，可以看做是 ideal mini-target + noise. 例如：結(jié)果給出P（1 | x）= 0.7响牛，P（0 | x） = 0.3，自然會(huì)選擇0.7那個(gè)結(jié)果学搜，而0.3就可以看做是Noise的level.
到這里就可以看出娃善，之前學(xué)習(xí) f 的情況是學(xué)習(xí)target distribution的特例。
（注："predict ideal mini-target （w.r.t. P(y|x)）on often-seen inputs(w.r.t. P(x))" 這個(gè)結(jié)論感覺(jué)自己還沒(méi)有理解好瑞佩，所以也不知道怎么解釋好聚磺，希望可以得到大家的指點(diǎn) ）
2、Error Measure
我們的學(xué)習(xí)目標(biāo)是得到一個(gè)接近f的g炬丸，g≈f. 之前也多數(shù)在圍繞這個(gè)目標(biāo)討論瘫寝，什么樣是接近的蜒蕾？前面是用Eout（g）來(lái)衡量，Eout（g）越小越好焕阿。
Eout這個(gè)衡量標(biāo)準(zhǔn)有3個(gè)注意點(diǎn)：out-of-sample咪啡，對(duì)未來(lái)的預(yù)測(cè)；pointwise暮屡，可以在單個(gè)data上衡量撤摸；二元分類，“對(duì)”or“錯(cuò)”褒纲，又叫 0/1 error.
更一般的衡量標(biāo)準(zhǔn)可以用 E（g准夷，f）表示，在一個(gè)點(diǎn)上判斷對(duì)錯(cuò)再對(duì)多個(gè)點(diǎn)平均莺掠， E(g衫嵌，f) = averaged err（g（x），f（x））彻秆，err叫做 “Pointwise Error Measure”. ?所以可以表示Ein（g）和Eout（g）為：
之后的課程中主要使用 pointwise err 作為衡量楔绞，當(dāng)然實(shí)際中也存在更復(fù)雜的衡量。
Pointwise Error Measure主要有兩種：0/1 err 和 squared err
類別型：0/1 err 是判斷對(duì)錯(cuò)唇兑，主要用在分類酒朵，選擇對(duì)應(yīng)的錯(cuò)誤概率最低的y作為結(jié)果；
數(shù)值型：squared err 是判斷“距離”扎附，主要用在回歸（后續(xù)會(huì)有介紹）耻讽，y是加權(quán)平均值（可以證明得到），如下圖：
到這里帕棉，對(duì)learning的理解已經(jīng)深入一些了，這里再附一張更詳細(xì)的learning flow的圖饼记，可以和Lec 1的比較一下：
直接給出拓展：vc theory / philosophy 對(duì)大部分H和err都可以成立香伴！
3、Error Measure in Algorithm
結(jié)合實(shí)際應(yīng)用具则，err存在兩種錯(cuò)誤情形：false reject 和 false accept即纲，比如設(shè)備的指紋識(shí)別，錯(cuò)誤的拒絕了用戶 和 錯(cuò)誤的接受了攻擊者博肋。
在 0/1 err中對(duì)這兩種情形的penalty（懲罰）是同等的低斋，但是在實(shí)際中，對(duì)于不同的應(yīng)用場(chǎng)景匪凡、不同的使用者等來(lái)說(shuō)膊畴，err兩種錯(cuò)誤情形的懲罰標(biāo)準(zhǔn)應(yīng)該不同。比如 超市顧客認(rèn)證系統(tǒng) 和 CIA認(rèn)證系統(tǒng)病游，不同錯(cuò)誤產(chǎn)生的后果差異巨大唇跨。所以稠通，在設(shè)計(jì)學(xué)習(xí)算法的時(shí)候，應(yīng)該考慮這一點(diǎn)买猖，但是……但是……通常很難確定懲罰標(biāo)準(zhǔn)改橘，1000？5000玉控？or飞主？不好說(shuō)懲罰多少。通常會(huì)選擇一種err的 替代品 或 容易最佳化的&合理的 err^.設(shè)計(jì)合適的err^是學(xué)習(xí)算法設(shè)計(jì)中的核心部分高诺！
后面的章節(jié)會(huì)看到碌识，不同的學(xué)習(xí)算法A的err^設(shè)計(jì)各異，各有千秋懒叛，自然可以理解這里說(shuō)的意思丸冕，嘿嘿。選擇一個(gè)right的err^非常重要薛窥！最后就會(huì)發(fā)現(xiàn)胖烛，大部分學(xué)習(xí)算法就是對(duì)err^的最佳化，最后都是數(shù)學(xué)問(wèn)題诅迷。 個(gè)人覺(jué)得佩番，理解了算法的err^設(shè)計(jì)，就差不多理解了算法的 philosophy.
4罢杉、Weighted Classification
給二元分類的err加上權(quán)重的分類稱為weighted classification.
給出一個(gè)名詞：cost或error或 loss matrix趟畏，表示不同錯(cuò)誤情景的代價(jià)。下圖展示了對(duì)應(yīng)超市和CIA認(rèn)證的cost matrix.
此時(shí)Ein和Eout形式為：
VC理論對(duì)于這種理論還是適用的滩租，那么希望Ein越小越好赋秀，帶weight的Ein如何解？
1）對(duì)于PLA來(lái)說(shuō)律想，Ein = 0猎莲，weight不影響什么；
2）對(duì)于pocket來(lái)說(shuō)技即，需要modify一下著洼。很簡(jiǎn)單，只需在比較Wt+1和Wt時(shí)而叼，比較加權(quán)錯(cuò)誤的大猩眢浴？葵陵！真的這么簡(jiǎn)單嗎笔链？可是考慮一下抓韩，pocket的理論保障是對(duì)于 0/1 err，這樣簡(jiǎn)單的修改也許會(huì)破壞之前的理論保障橘券？保持懷疑。
其實(shí)有一種巧妙方法可以把 weighted Ein 變換成 0/1 Ein：把y = -1 的data 復(fù)制1000倍！嗯哼~這時(shí)error matrix就和0/1 error matrix一樣，可以使用 pocket 了，但其實(shí)應(yīng)該modify兩點(diǎn)（更嚴(yán)謹(jǐn)响迂，也很巧妙）：
1）其實(shí)實(shí)現(xiàn)copy的時(shí)候，并不需要真的復(fù)制1000倍并存儲(chǔ)下來(lái)细疚，稱為“virtual copy”蔗彤。所以應(yīng)該頻繁地（1000倍）check y = -1 的data；
2）比較Wt+1和Wt時(shí)疯兼，比較加權(quán)錯(cuò)誤的大腥欢簟；
這個(gè)轉(zhuǎn)化思路可以應(yīng)用在很多其他的algorithms上吧彪，叫做 “reduction”待侵。
Fun Time 值得提一下：
這個(gè)題目體現(xiàn)了data的unbalanced的情況，properly設(shè)置weight可以避免這種情況姨裸。
至此why部分結(jié)束秧倾，下面將主要進(jìn)行各種Algorithm的介紹～
