Lec 8-1 噪聲和概率目標(biāo)

有噪聲的數(shù)據(jù)

回顧 learning flow亏镰，我們有一個(gè)target function，這個(gè)target function 會(huì)產(chǎn)生一堆的example 資料拯爽，除了從target function 得到資料的 y 以外索抓，它的 x 的部分是由某一個(gè)我們所不知道的distribution所產(chǎn)生的。未來(lái)在測(cè)試的時(shí)候，我們也會(huì)用一樣的distribution逼肯。我們的演算法A想辦法從這些資料還有一個(gè)hypothesis set 里面找出一個(gè)好的 hypothesis耸黑。

我們現(xiàn)在有一個(gè)觀念說(shuō)，好的hypothesis set 是 VC dimension 是 finite （有限）的篮幢；而好的hypothesis 是Ein 最低的大刊。經(jīng)過(guò)第第七章的推導(dǎo)，我們已經(jīng)證明三椿，在這樣的流程下是成立的缺菌。但我們之前也提到過(guò)，如果在這個(gè)圖里加上了noise 噪聲搜锰，對(duì)我們整個(gè)理論的推導(dǎo)會(huì)不會(huì)有影響呢伴郁？

，

有噪聲時(shí)的推導(dǎo)

我們之前講pocket演算法時(shí)講到過(guò)纽乱，我們的資料可能會(huì)有noise蛾绎，例如說(shuō)銀行發(fā)信用卡的例子，有一個(gè)顧客應(yīng)該要發(fā)信用卡給他鸦列，但資料里面因?yàn)橛涗涘e(cuò)誤或人為錯(cuò)誤或其他原因，我們沒(méi)有發(fā)信用卡給他鹏倘；還有可能有兩筆差不多條件的資料薯嗤，但一個(gè)人發(fā)了信用卡，另一個(gè)人沒(méi)發(fā)給他纤泵。對(duì)應(yīng)到2D的圖中就是骆姐，一個(gè)本來(lái)是?，但被劃分成了X捏题；以及兩個(gè)點(diǎn)疊在一起玻褪，但一個(gè)是?，一個(gè)是X公荧。另外带射，除了y可能有噪音，x也可能會(huì)有噪音循狰，即收集顧客資料時(shí)搜集得不精準(zhǔn)窟社。但在原來(lái)的流程里面，我們是沒(méi)有考慮這些的绪钥。

那么有了噪音灿里，我們推導(dǎo)出來(lái)的VC bound 是不是還能工作得很好？那么VC bound 的核心是什么? 回想一下程腹，我們?cè)谧C明VC bound 的時(shí)候匣吊，一開始的假設(shè)都是我們有一個(gè)罐子，我們不知道罐子里有多少橘色彈珠，如果我們抓一把出來(lái)的話色鸳，就可以估計(jì)橘色的彈珠是多少社痛。假設(shè)這些橘色的彈珠就是我們犯錯(cuò)誤的地方。

我們把每一個(gè)彈珠就看做一個(gè)一個(gè)的x缕碎，對(duì)應(yīng)到學(xué)習(xí)里面褥影，就是一個(gè)一個(gè)的輸入，然后我們從某一個(gè)幾率分布P咏雌，把它抽出來(lái)凡怎。再來(lái)呢，彈珠的顏色怎么決定的赊抖？我們就看看统倒，我們的hypothesis 的預(yù)測(cè)，我們的 h 就對(duì)應(yīng)到一個(gè)罐子氛雪，這個(gè)罐子 h 的預(yù)測(cè)跟我們目標(biāo)函數(shù) f 的預(yù)測(cè)到底是一樣還是不一樣房匆，不一樣就記成橘色，一樣就記成綠色报亩。這是我們之前推導(dǎo)VC bound 最核心的部分浴鸿。

那現(xiàn)在呢，如果有噪聲會(huì)怎么樣弦追？噪聲的意思是什么岳链，噪聲是說(shuō)，也許我有一個(gè)真實(shí)的 x 在那邊劲件，但是呢掸哑，今天我拿到的 y 并不一定是f(x) 。我們想象一種特別的彈珠零远，它的顏色會(huì)不斷地變化苗分，每一個(gè)時(shí)間點(diǎn)，它就有可能從橘色變綠色牵辣，或者綠色變橘色摔癣，它的顏色不是固定的，而是有時(shí)候是橘色服猪，有時(shí)候是綠色供填。如果從時(shí)間的比例來(lái)切割的話，我們想象每一顆彈珠罢猪，它60%的時(shí)候是橘色近她，40%的時(shí)候是綠色。這樣膳帕，每一顆彈珠都是一個(gè)變色龍粘捎，但從整體來(lái)看薇缅，整個(gè)罐子還是有一個(gè)橘色和綠色的比例的。那我們要怎樣知道攒磨，整個(gè)罐子里面泳桦，橘色和綠色的比例到底是多少？同樣娩缰，我可以從中抽樣灸撰，并且趕快記錄抽出來(lái)的瞬間那些彈珠的顏色，同樣可以估計(jì)說(shuō)那個(gè)時(shí)刻罐子里橘色彈珠的比例拼坎，盡管彈珠的顏色是變來(lái)變?nèi)サ母√海驗(yàn)樗w還是有分布規(guī)律的，所以仍然可以抽樣估計(jì)泰鸡。

我們也可以把整個(gè)VC 的證明重新寫一次债蓝，用會(huì)變色的彈珠寫一次，也就是我們現(xiàn)在要想象說(shuō)盛龄，我們的 y ,也就是label 并不是來(lái)自 f(x)饰迹，而是來(lái)自取樣的過(guò)程，來(lái)自 P(y|x)余舶，也就是已經(jīng)是這些彈珠的狀況下啊鸭，到底它的顏色會(huì)怎么樣變來(lái)變?nèi)ィ@是由 P(y|x) 決定的匿值。那我們現(xiàn)在有了x 和 y 的分布莉掂，只要把VC 的復(fù)雜證明再重新寫一次，VC bound 還是可以work千扔。

我們可以把這兩個(gè)部分整合起來(lái)，這實(shí)際上告訴我們說(shuō)库正，只要我們的每一個(gè)example 的（x, y） y 來(lái)自某一個(gè) joint distribution? ?P(x, y)曲楚，在訓(xùn)練時(shí)是這樣，在測(cè)試時(shí)也是這樣褥符，那么整個(gè)VC 的大架構(gòu)都還是能夠用得上來(lái)龙誊。

，

P( y | x) 我們一般把它叫做 target 的 distribution, 也就是說(shuō)不是一個(gè)目標(biāo)函數(shù)喷楣，而是一個(gè)目標(biāo)分布趟大，因?yàn)閷?duì)每一個(gè)彈珠來(lái)說(shuō)，把它的預(yù)測(cè)稱為mini-target铣焊，對(duì)這個(gè)x 可以做一個(gè)預(yù)測(cè)逊朽，mini-target 對(duì)這個(gè) x 上面，到底最理想的預(yù)測(cè)是什么曲伊。什么意思呢叽讳？這個(gè)distribution告訴我們說(shuō)，最理想是什么，然后其他不理想部分是什么岛蚤，哪些是噪聲邑狸。

例如說(shuō)：我今天有個(gè)P，這個(gè)P長(zhǎng)這樣子涤妒，如果我拿一顆彈珠单雾，它是?的幾率是0.7， 它是X 的幾率是0.3她紫，那么請(qǐng)問(wèn)你要猜?還是X硅堆？那么大家都更愿意猜?，這樣錯(cuò)誤率只有30%犁苏。雖然?是比較好的選擇硬萍，但還是有30%的幾率是錯(cuò)誤的，那么這30%就可以想象是在這個(gè)最好的選擇上的噪聲围详。所以這個(gè)目標(biāo)分布可以告訴我們朴乖，最好的選擇是什么，然后噪聲是多少助赞，這是一種對(duì)target distribution的看法买羞。

那或者呢，我們把之前一直所適用的deterministic target function 雹食，也就是固定的目標(biāo)函數(shù)畜普，也可以看作target distribution的一個(gè)特殊的例子：如果今天，我的 y 跟我的 f (x) 是一樣群叶，完全沒(méi)有噪聲吃挑，是最好的預(yù)測(cè)。適用target distribution的時(shí)候跟以前使用target function 的時(shí)候基本上沒(méi)有什么不一樣街立。

所以現(xiàn)在我們learning 的目標(biāo)就有兩個(gè)部分了：

① 一個(gè)是 p (x), 它告訴我們哪些點(diǎn)是重要的舶衬，如果某些點(diǎn)的p(x) 很大，它常常會(huì)被sample 到赎离，在Ein里面常常會(huì)被采到逛犹，在Eout的時(shí)候它也會(huì)比較重要一點(diǎn)。

②這些常常被sample到的點(diǎn)梁剔，我們要預(yù)測(cè)得盡量接近 mini-target, 這個(gè)mini-target 是從 P(y|x) 來(lái)的虽画，它告訴我們說(shuō)最理想的mini-target是什么。

在常見(jiàn)的事情上做得好荣病，這就是learning要做的事情码撰。

所以加上噪聲以后，現(xiàn)在左上角不再是一個(gè)target function了众雷，而是一個(gè)target distribution p(y|x)灸拍，它所產(chǎn)生的 y 會(huì)給trainning的部分做祝，并且我們用同樣的distribution來(lái)產(chǎn)生這些 y 來(lái)做測(cè)試看 g 到底跟 f 一樣還是不一樣。

對(duì)于pocket算法鸡岗，在A那邊混槐，我們盡量想辦法去讓Ein越小越好，那這個(gè)Ein越小轩性，后面真的會(huì)變成Eout 越猩恰？會(huì)揣苏，因?yàn)樵谟衝oise 的情況下悯嗓，只要我們想象說(shuō)，這個(gè)noise卸察，是由這個(gè)target distribution來(lái)做描述的話脯厨，我們還是可以把事情學(xué)得很好。

Lec 8-2 錯(cuò)誤估計(jì)

講完了噪聲坑质，現(xiàn)在來(lái)看看合武，在整個(gè)learning flow 里面，我們一直有這個(gè)最后一步：想要知道 g 跟 f 到底一不一樣涡扼。我們整個(gè)的推導(dǎo)都在想辦法說(shuō)服人家稼跳，我們的g 跟 f 是很像的。我們前面使用的是Eout來(lái)衡量 g 跟 f sample出來(lái)的點(diǎn)是否一樣等等吃沪。更一般地來(lái)說(shuō)汤善，實(shí)際上要回答這個(gè)問(wèn)題，我們心里要有個(gè)想好的說(shuō)到底要怎么打分?jǐn)?shù)票彪，人家給了你一個(gè) g红淡，你心里有個(gè)你想要的 f ，你總要有個(gè)打分?jǐn)?shù)的方式來(lái)告訴人家好或不好降铸。

那我們之前使用的這個(gè) g 呢锉屈，有三個(gè)特性：

① out-of-sample：我們看的事情是未來(lái)抽樣出來(lái)的這些 x 。

② pointwise ：可以在每一個(gè) x 上個(gè)別衡量垮耳，而不是說(shuō)一定要抽10個(gè) x 然后有一個(gè)綜合的衡量，只用看一個(gè) x 好不好遂黍，然后最后做抽樣的平均就可以了终佛。

③ classification：我們之前討論的是二元分類，就看對(duì)或不對(duì)就行了雾家。classification的錯(cuò)誤通常又被叫做 0/1 錯(cuò)誤铃彰。

好，以上是錯(cuò)誤的衡量芯咧，很多時(shí)候牙捉，我們所碰到的錯(cuò)誤衡量竹揍，都可以像之前做的一樣，只考慮每個(gè)點(diǎn)上邪铲，到底有多少錯(cuò)誤芬位，然后再把它加起來(lái)或者做平均的方式。這種方式就把他叫做pointwise带到，每個(gè)點(diǎn)上的error measure昧碉，用 err 來(lái)表示，有了這個(gè) err 之后揽惹，我們就可以看看說(shuō)我們的Ein和 Eout 會(huì)長(zhǎng)什么樣子被饿？

這些 f(xn) 在比較有noise 的情況下，其實(shí)就是 y(n)搪搏。

那么歸納一下狭握，有哪些衡量錯(cuò)誤的方式：

① 0/1 錯(cuò)誤：通常用在分類；

② squared error 平方錯(cuò)誤: 通常用在預(yù)測(cè)疯溺，實(shí)數(shù)的回歸论颅，用來(lái)衡量y~ 和 y 到底有多接近，離得越遠(yuǎn)喝检，平方的錯(cuò)誤越大嗅辣，而不是像0/1錯(cuò)誤一樣，對(duì)就是對(duì)挠说，錯(cuò)就是錯(cuò)澡谭。

我們未來(lái)會(huì)講更多不同的錯(cuò)誤的衡量，這兩個(gè)基本的先有個(gè)概念损俭，想跟大家說(shuō)蛙奖，我們對(duì)錯(cuò)誤的衡量會(huì)影響到，到底杆兵，我們剛才講過(guò)說(shuō)雁仲，在 p（y | x）的時(shí)候，我們有那個(gè)最理想的mini-target琐脏，迷你的目標(biāo)攒砖，這個(gè)迷你的目標(biāo)跟錯(cuò)誤有關(guān)，也跟 p（y | x）有關(guān)日裙。什么意思呢吹艇？好，我們來(lái)看看到底錯(cuò)誤的衡量昂拂，同一個(gè)?p（y | x）受神， 這邊舉了個(gè)例子說(shuō)：

我有三個(gè)可能的輸出，y=1 的幾率是0.2格侯；y=2的幾率是0.7鼻听； y=3 的幾率是0.1财著，加起來(lái)就是1了。那我們來(lái)看看說(shuō)撑碴，在這個(gè)狀況下撑教，最理想的mini-target 長(zhǎng)什么樣子。

假如你想象的錯(cuò)誤是 0/1 錯(cuò)誤灰羽，當(dāng)你的hypothesis說(shuō)是 1 時(shí)驮履，可能的錯(cuò)誤率是0.8，如果你的hypothesis 說(shuō)是2呢廉嚼？那么可能的錯(cuò)誤率是0.3玫镐， 如果說(shuō)是3的話，可能的錯(cuò)誤率是0.9怠噪；當(dāng)然這個(gè)hypothesis 不可能說(shuō)是1.9恐似，因?yàn)檫@是個(gè)分類問(wèn)題。所以在這個(gè)例子里傍念，最好的答案是猜2矫夷，這樣你只有0.3的幾率犯錯(cuò)誤。

如果我們今天的錯(cuò)誤衡量是squared 呢憋槐？平方的錯(cuò)誤双藕。你的hypothesis 說(shuō)是 1，有0.2的機(jī)會(huì)它沒(méi)有犯錯(cuò)阳仔，有0.7的機(jī)會(huì)它犯錯(cuò) （2-1）^2 = 1, 有0.1 的機(jī)會(huì)它犯錯(cuò)（3-1）^2 = 4, 加權(quán)后為0.7*1 + 0.1 * 4 = 1.1忧陪。依次算出hypothesis 預(yù)測(cè)是其他各個(gè)值時(shí)的錯(cuò)誤率，最低的為推測(cè)1.9時(shí)近范，為0.29嘶摊。你看，在0/1錯(cuò)誤時(shí)不可能出現(xiàn)的1.9评矩，在平方錯(cuò)誤時(shí)叶堆，反而是犯錯(cuò)幾率最小的推測(cè)。

這里想說(shuō)明斥杜，你要用什么樣的錯(cuò)誤衡量虱颗，配合上說(shuō) P 長(zhǎng)什么樣子，會(huì)告訴我們蔗喂，最理想化的目標(biāo)函數(shù)到底是長(zhǎng)什么樣子上枕。

一般來(lái)說(shuō)，在0/1 錯(cuò)誤里面弱恒，一般來(lái)說(shuō)，選P最大的那個(gè)就對(duì)了棋恼；而在squared 錯(cuò)誤里面返弹，則需要選的是平均值锈玉，也就是最中間的那個(gè)，它的加權(quán)平均值最小义起。

現(xiàn)在我們有了錯(cuò)誤衡量的觀念拉背，錯(cuò)誤衡量會(huì)影響到 f 到底長(zhǎng)什么樣子。我們的learning flow里面默终，不能夠只有我們不知道的p 和 f 在那邊椅棺，實(shí)際上必須要告訴我們的演算法說(shuō)，我們要用什么樣的錯(cuò)誤衡量齐蔽。然后两疚，另外呢，我們也希望含滴，用這樣錯(cuò)誤衡量最后真的來(lái)衡量說(shuō)我最后學(xué)到的 g 到底好還是不好诱渤。這個(gè)錯(cuò)誤衡量最好要告訴演算法，如果不告訴演算法怎么去找好的g谈况，可能它自己覺(jué)得它把0/1 做得很好勺美，結(jié)果我們要算的是squared error，結(jié)果可能就天差地別了碑韵，所以錯(cuò)誤衡量是很重要的一部分赡茸。

VC 的整個(gè)推導(dǎo)還有整個(gè)精神，對(duì)于很多不同的hypothesis set 祝闻，還有很多不同的錯(cuò)誤衡量來(lái)說(shuō)占卧，都會(huì)work。也就是說(shuō)治筒，如果我要做得不是classification屉栓，不是分類，而是做回歸分析耸袜，要輸入實(shí)數(shù)的那個(gè)回歸分析友多，把VC 的一些推導(dǎo)做一些定義上的修改，例如我要定義說(shuō)堤框，我今天是實(shí)數(shù)輸出的VC dimension是怎么算的域滥，做完這些修改之后，我是可以用得到幾乎一樣蜈抓，非常類似的VC bound启绰，也會(huì)起到作用。

Lec 8-3 算法的錯(cuò)誤衡量

案例：指紋辨識(shí)

你的分類器可能會(huì)犯兩種錯(cuò)誤：

① false accept：本應(yīng)被拒絕沟使，而通過(guò)了驗(yàn)證

② false reject：本應(yīng)該通過(guò)驗(yàn)證委可，而拒絕通過(guò)

對(duì)于我們之前的 0/1 錯(cuò)誤分類問(wèn)題，對(duì)兩種類型錯(cuò)誤的懲罰力度是一樣的。但實(shí)際的應(yīng)用中着倾，有可能更側(cè)重于其中的某一類拾酝。

① 超市給常客打折：

? ? false accept 雖然不應(yīng)該給折扣卡者，但錯(cuò)誤地給了蒿囤，影響并不大，無(wú)非是少賺一點(diǎn)錢崇决。

? ???false reject 錯(cuò)誤地拒絕了客戶材诽，客戶得不到應(yīng)有的折扣，客戶會(huì)非常生氣恒傻，以后可能再也不來(lái)了脸侥，對(duì)于超市來(lái)說(shuō)可能是很大的損失。

所以對(duì)超市來(lái)說(shuō)碌冶，false accept 錯(cuò)誤沒(méi)那么糟糕湿痢，但false reject 錯(cuò)誤影響很大。所以超市心里應(yīng)該有一個(gè)犯錯(cuò)的成本表：

f 為 +1 打折而 g 判定 為-1 不打折時(shí)扑庞，成本為10譬重，比f(wàn)alse accept 大10倍。

② CIA 美國(guó)中情局系統(tǒng)身份認(rèn)證：

? ? false accept：錯(cuò)誤地接受登入系統(tǒng)罐氨，可能導(dǎo)致數(shù)據(jù)泄露臀规，產(chǎn)生嚴(yán)重錯(cuò)誤

? ? false reject：錯(cuò)誤地拒絕登入系統(tǒng)，員工可能會(huì)不開心栅隐，但對(duì)CIA整體的目標(biāo)來(lái)說(shuō)塔嬉，沒(méi)有那么重要。

所以對(duì)CIA來(lái)說(shuō)的錯(cuò)誤成本表可能是：

f 為-1不接受登入租悄，但g推測(cè)說(shuō)可以登入谨究，false accept 的錯(cuò)誤成本是1000，為false reject 的1000倍泣棋。

所以不同的應(yīng)用會(huì)想要不同的錯(cuò)誤衡量胶哲，二元分類不是只搜集二元錯(cuò)誤就能搞定，超市打折和CIA登錄的案例是不同的兩種情形潭辈，你想要的分類器是長(zhǎng)得不一樣的鸯屿。所以在我們?cè)O(shè)計(jì)演算法的時(shí)候就要想辦法把這些錯(cuò)誤的衡量考慮進(jìn)去。最理想的情況是你想怎么衡量把敢，就直接告訴演算法具體值寄摆，錯(cuò)誤的成本是多少，但實(shí)際上你不可能跑去問(wèn)CIA修赞，他們就會(huì)告訴你用1000還是5000來(lái)做成本懲罰婶恼，所以，要生出真正的錯(cuò)誤衡量很困難，要把心里想的東西數(shù)字化勾邦，數(shù)學(xué)化是很困難的联逻。在設(shè)計(jì)演算法時(shí)，常常會(huì)采用替代的方式检痰，通常有兩種替代方式：

① 找一些有意義的錯(cuò)誤衡量：

? ? pocket 中的 0/1 錯(cuò)誤：如果分不對(duì)，想象一定是有翻轉(zhuǎn)噪聲（+1 變 -1锨推， -1 變 +1）铅歼，并且量很小。如果量很小的話换可，如果我們想辦法去讓 0/1 錯(cuò)誤很小椎椰，是一個(gè)好的方法。所以我們找一些理由說(shuō)服我們就對(duì)了沾鳄。

????平方錯(cuò)誤為什么要用平方慨飘？如果你噪聲跟我原來(lái)的偏離是高斯分布的，你想象高斯分布里面那個(gè)平方項(xiàng)會(huì)在期望里面出現(xiàn)译荞，如果我們把這個(gè)平方項(xiàng)減小瓤的，有點(diǎn)像說(shuō)，我們就是在找出最小的高斯噪聲在哪里吞歼。

????這是說(shuō)服我們自己的方式圈膏。我們把它叫做err~，代表它跟使用的真的有興趣的錯(cuò)誤衡量不見(jiàn)得完全一樣篙骡，不過(guò)如果使用者也說(shuō)不出個(gè)所以然來(lái)的話稽坤，這看起來(lái)是我們?cè)谘菟惴ɡ锩婵梢宰龅囊粋€(gè)方式。

不過(guò)回頭來(lái)看糯俗，我們?cè)谥v0/1的時(shí)候尿褪，如果我們要算一堆線，要找出Ein最小的那個(gè)的話非常地困難—— NP-hard 問(wèn)題得湘。

② friendly 方式：

????所以設(shè)計(jì)演算法有時(shí)非常地困難杖玲，不好設(shè)計(jì)演算法，所以我們常常還會(huì)采用另外一種叫做friendly 忽刽。friendly的意思是說(shuō)天揖，很友善，我們比較好設(shè)計(jì)演算法跪帝。我們知道今膊，演算法我們是在尋求，Ein越小越好伞剑，我們可能會(huì)用一些替代品斑唬，讓我們更容易地找到，到底哪一些是Ein更小的。例如說(shuō)：

? ? 如果我今天列出來(lái)的式子恕刘，可以都很容易地就求到closed-form solution缤谎，我有一個(gè)演算法，你照著這個(gè)算下去褐着，馬上就算出解來(lái)饺蚊，這是一種。

????然后演熟，或者是帮哈，在最佳化里面，有所謂的convex optimization馅扣， 也就是說(shuō)今天是一個(gè)凸的斟赚，所以你在做最小化的時(shí)候，只要像一個(gè)球從山上面滾下來(lái)差油，滾到山谷里面就好拗军，那這通常也是好的方式。這個(gè)我們之后會(huì)提到蓄喇。

我們最需要的是使用者告訴我們他想要什么发侵，不過(guò)如果使用者不告訴我們想要什么，我們?cè)谠O(shè)計(jì)演算法的時(shí)候公罕，我們可能可以采用器紧，1. 能說(shuō)服我們自己的方式，我們叫plausible楼眷；2.對(duì)我們演算法設(shè)計(jì)容易一點(diǎn)的方式铲汪，叫friendly。我們未來(lái)會(huì)講到更多相關(guān)的東西罐柳。這個(gè)err~對(duì)于演算法設(shè)計(jì)是非常重要的掌腰。

所以有了這個(gè)err~的概念之后，我們可以把learning flow 再做一個(gè)更新：

我們真的有興趣的是那個(gè)err张吉，不過(guò)我們?cè)谶@個(gè)地方說(shuō)齿梁，我們的演算法里面，有一個(gè)小小的部分肮蛹，它實(shí)際上是用到了某個(gè)err~來(lái)做的勺择，試圖讓我們的演算法好過(guò)一點(diǎn)，這是很多演算法核心的部分伦忠。

如果你今天是CIA的話省核，我們之前有講到說(shuō)，你要的 Ein 昆码，不再是原來(lái)的 0/1 錯(cuò)誤气忠，而是錯(cuò)誤成本加權(quán)后的Ein邻储，那你要的Ein到底長(zhǎng)什么樣子？ 答案選②旧噪，y = -1, g(x) = +1 是 false accept吨娜，錯(cuò)誤成本為1000。

Lec 8-4 加權(quán)分類

講機(jī)器學(xué)習(xí)中另一個(gè)問(wèn)題淘钟，之前講二元分類宦赠，現(xiàn)在呢，錯(cuò)誤在不同的情形下有著不同的重要性米母，我們把它叫做weighted classification袱瓮。它的懲罰成本我們把它叫做 cost Matrix，或者Error Matrix爱咬， Loss Matrix：

基于cost Matrix，計(jì)算Error時(shí)就會(huì)根據(jù)錯(cuò)誤的不同情況進(jìn)行加權(quán)：

所以現(xiàn)在我們的 Ein 就變成了有權(quán)重的Ein w绊起，我們要怎樣才能讓Ein w 最小化精拟？

Systematic route（reduction）

回想我們已經(jīng)學(xué)過(guò)的算法：

PLA ： PLA假設(shè)線性可分，跑完后Ein是0虱歪， Ein w 當(dāng)然也是0蜂绎，PLA根本不用管權(quán)重；不過(guò)大部分時(shí)候不是這樣笋鄙，如果資料不是線性可分的师枣，PLA停不下來(lái)，怎么辦萧落？

pocket：pocket 演算法有什么步驟跟原來(lái)的0/1 的Ein有關(guān)的践美？如果新找到的 w 比口袋里的好的話，就把口袋里的換掉找岖，那么我們就看看這一步就好了：那么現(xiàn)在這個(gè) w 和口袋里的比的話陨倡，不是在比有幾個(gè)錯(cuò)誤，而是比誰(shuí)的加權(quán)錯(cuò)誤更小许布。

但我們?cè)瓉?lái)只是說(shuō)pocket 有一些理論上的保證兴革，能讓Ein 在0/1 錯(cuò)誤的時(shí)候越來(lái)越小，那對(duì)Ein w有多少的保證蜜唾？接下來(lái)講怎樣修改一下演算法杂曲，讓pocket有和原來(lái)一樣的保證。

在原來(lái)的資料里面袁余，+1的不變擎勘，如果是-1的，就把它復(fù)制一千倍泌霍，這樣的話货抄，假如有一個(gè)h述召，在這份資料上犯了false accept （-1 判為 +1）的錯(cuò)誤，因?yàn)槲覀円呀?jīng)把這個(gè)點(diǎn)復(fù)制了一千次蟹地，那么它只要在這個(gè)點(diǎn)上犯錯(cuò)誤积暖，就相當(dāng)于在1000個(gè)點(diǎn)上犯了錯(cuò)誤，我們會(huì)收他1000倍的錯(cuò)誤成本怪与。在+1 上犯錯(cuò)誤和原來(lái)一樣夺刑，因?yàn)?1的點(diǎn)沒(méi)有變。所以在這份新的資料上分别，不管是+1 還是 -1 的從錯(cuò)誤遍愿，我們每個(gè)都收它一塊錢，就跟在舊的資料上 -1 犯錯(cuò)誤收1000塊錢是一樣的結(jié)果耘斩。所以在右邊和原來(lái)一樣的0/1錯(cuò)誤上的pocket 演算法沼填，跟左邊這樣專門設(shè)計(jì)一個(gè)支持加權(quán)成本的pocket演算法，實(shí)際上是對(duì)等的括授。

但因?yàn)閺?fù)制的動(dòng)作一般會(huì)增加計(jì)算成本坞笙、硬件成本、時(shí)間成本荚虚，所以一般不會(huì)真的做復(fù)制的動(dòng)作薛夜，而是在設(shè)計(jì)演算法時(shí)，我們腦袋里想著我們有復(fù)制的動(dòng)作版述。

如果有這個(gè)復(fù)制的動(dòng)作的話梯澜，那么，配合原來(lái)的pocket算法渴析，就能得到新的演算法晚伙，這個(gè)新的演算法會(huì)有什么改變呢：

① 首先這個(gè)pocket里面會(huì)不會(huì)被替換掉，原來(lái)是由Ein決定俭茧，現(xiàn)在要由Ein w來(lái)決定撬腾；

② 在pocket里面還有一步跟復(fù)制有關(guān)，就是我們到底要有多頻繁地拜訪每一個(gè)點(diǎn)恢恼，因?yàn)镻ocket下面有個(gè)PLA民傻，拜訪點(diǎn)的時(shí)候是隨機(jī)的，假設(shè)我復(fù)制了一千次场斑，所以我在拜訪點(diǎn)的時(shí)候漓踢，這些被我復(fù)制了一千次的點(diǎn)，應(yīng)該要有一千倍的幾率來(lái)被拜訪到漏隐，也就是我要常常檢查-1有沒(méi)有錯(cuò)誤喧半，少一些檢查+1有沒(méi)有錯(cuò)誤。

這樣做的好處是青责，如果今天權(quán)重不是整數(shù)倍挺据，而是比如10.26倍取具，你不能復(fù)制出9.26個(gè)數(shù)據(jù)，但你能把拜訪的幾率調(diào)到10.26倍扁耐。