1、Coursera 臺(tái)大機(jī)器學(xué)習(xí)基礎(chǔ)課程學(xué)習(xí)筆記1 -機(jī)器學(xué)習(xí)定義及 PLA 算法最近在跟臺(tái)大的這個(gè)課程，覺(jué)得不錯(cuò)，想把學(xué)習(xí)筆記發(fā)出來(lái)跟大家分享下，有錯(cuò)誤希望大家 指正。一機(jī)器學(xué)習(xí)是什么？machinelearning: improving some performance measure withexperience computed from dataimproveddata- ML- performancemeasure感覺(jué)和 Tom M. Mitchell 的定義幾乎一致，A computer program is said to lear n from experie nee E wi

2、th respect to some class of tasks T andperforma nee measure P, if its performa nee at tasks in T, as measured by P, improves withexperie nee E.簡(jiǎn)而言之，就是我們想要機(jī)器在某些方面有提高（如搜索排名的質(zhì)量，即NDCG 提高），就給機(jī)器一些數(shù)據(jù)（用戶的點(diǎn)擊數(shù)據(jù)等各種）然后讓機(jī)器獲得某些經(jīng)驗(yàn)（ Learni ng to rank 的一 種模型，也就是數(shù)學(xué)公式）。這里有點(diǎn)需要強(qiáng)調(diào)，那就是提高指標(biāo)，必須要有某種指標(biāo)可以 量化這種提高，這點(diǎn)還是很關(guān)鍵的，工業(yè)界做機(jī)

3、器學(xué)習(xí)，首先關(guān)注data，其次就是有無(wú)成型的 measurement，可以使 Precision/Recall，也可以是 NDCG 等。二什么時(shí)候可以用機(jī)器學(xué)習(xí)?O exists some Inderlying pattern* to be learned soBperformance measure can be improvedbut no programmable (easy) definition一soCML is neededsomehow there is data about the pattern so ML has some Inputs tolearn from其實(shí)就三要素

4、：1.有規(guī)律可以學(xué)習(xí)；2.編程很難做到；3.有能夠?qū)W習(xí)到規(guī)律的數(shù)據(jù)；編程很難做到可以有多種，大部分原因是系統(tǒng)太復(fù)雜， 很難用 Rule-based 的東西去解決，例如搜索排名，現(xiàn)在影響排名的因素有超多幾百種，不可能去想出這些因素的規(guī)則，因此，這 時(shí)候用機(jī)器學(xué)習(xí)就是恰到好處。特別是移動(dòng)互聯(lián)網(wǎng)的今天，用戶更容易接觸互聯(lián)網(wǎng)，產(chǎn)生的 數(shù)據(jù)越來(lái)越多，那么要找到某些不容易實(shí)現(xiàn)的規(guī)律，用機(jī)器學(xué)習(xí)就是很好的了，這也是為啥 機(jī)器學(xué)習(xí)這么火，其實(shí)我學(xué)機(jī)器學(xué)習(xí)不僅僅是一種投資（肯定它未來(lái)的發(fā)展前途），我想做 的事情還有一點(diǎn)，就是通過(guò)它更深刻的理解人腦的學(xué)習(xí)過(guò)程，提高自己的學(xué)習(xí)效率和思維能 力。三具體如何用機(jī)器學(xué)習(xí)?

5、Basic Notations in put: x 尢(customer application) output: y ey (good/bad after appro ving credit card) unknown pattern to be learned o target function:X (ideal credit approval formula) data o training examples: T =(x2.y2) thresholddeny credit ifWjXj threshold,0 ignoreci一linear formula ft arecalled p

6、erceptron1hypothesis historically這里的思想在于樸素的把從用戶信息抽出來(lái)的一些feature （年齡等）量化并組成 vector，然后乘以一個(gè)權(quán)重向量，并設(shè)定一個(gè)閾值，大于這個(gè)閾值就表示好，小于表示不好，很明顯這 個(gè)式子的未知變量有兩個(gè)（實(shí)際只有一個(gè)）：1.權(quán)重向量 wi, 1=i=d;2.閾值，下面設(shè)為 0做一點(diǎn)小小的變形使得式子更加緊湊,itures of customer1, compute athresholdh(x) = signWjXj/Xisign(dT wtx, j -threshold i=i)signd牙WfXj| 十(一threshold)

7、(+1)二、-*-7WoXocfE吩sign (wrx)sign each talf w represents a hypothesis h & is multiplied withtall1x will use tall versions to simplify notation還有就是從這個(gè)模型可以知道，regression model 也可以解決 classification 問(wèn)題，轉(zhuǎn)化的思想。下面是這個(gè)算法的核心，定義了學(xué)習(xí)目標(biāo)之后，如何學(xué)習(xí)？這里的學(xué)習(xí)是，如何得到最終的直線去區(qū)分 data ？start from some wg (say, 0), and correct its m

8、istakes on DJFor f = 0. h y=+1”0 find a mistake of W/ called(心弘)sign w/xn(f)弄 /(try to) correct the mistake by o exists perfect such that yn= sign(wjx W/ perfect hence every xncorrectly away from line:辦抵嗆)n 叫n%wjx門 0 w；W/1 by updating with any (x(小)wjwr+i =(叫 +yn(oMn)w；Wf + min ynwxn+ 0.W/ appears m

9、ore aligned with Wf after update(really?)W/ changed only when mistakeo sign(W%)豐yn(to yn(txn(0 0 mistake limits* |Wf|2growth, even when updating with longest1xnI冋+i=|wf+ yn(0 xn(0|2=|wf|2+ 2%(r)wJ xn(r)+ |yn(oxn(o|2l|Wf|2+ 0 + |yn(f)xn(0|2 VT - constant這兩頁(yè) PPT 比較復(fù)雜，其實(shí)就是在利用條件證明，下面重新組織下給出思路，因?yàn)橹形牟惶?，就?/p>

10、英文了：Latex 用Given 3 conditions1 u)f perfectly fitting those data means: 叫嚴(yán)?/nwJrn()(1)2wtchanged only when making mistakes means:signg -Cn(O)/嘰Q Vn(t)t ()(2)3 we make corrections by:勁 =wf_i+如巧(3)We want to prov after t mistake corrections starting from 0r, thus thealgorithm will stop at some time;2 t

11、he left purt the above equation indans the angle of uy and u” and thir angle is decreasing, in other wordswt is approaching少八thus we are on the right way to get the solutionHere is the prove:the priinarv principle is to replace all t.lie variables which in above equations are u)t and |u?| for wtweha

12、ve:砂=砂_i+：!/“(i)巧(一i)using (3)WjWt_i + min ynWfXnusing (1)u?o十T min ywjxnapplying T timesTTT min /nuyfor |wr| we have:lldl =using (3)|1呦-1+()+ |%(using (2)llf-ill2+ rnax |xn|2nlloII + T 刃心hull2= T-”心 |如斥iMil IIrCons五 PLA 的優(yōu)缺點(diǎn)applying above 2 conclusions to the left patt of the equation we finally ge

13、t:Because the ；：； 1, wefinally have:simple to implement, fast, works in any dimension d為了應(yīng)對(duì) Noisy，我們不可能得到完美的直線，那么怎么衡量當(dāng)前得到的直線能夠滿足要求呢？憑直覺(jué)，我們知道如果當(dāng)前直線犯錯(cuò)越少越好（對(duì)所有data），于是有了下面的改進(jìn)算法，Pocket PLA，本質(zhì)上就是在改錯(cuò)的時(shí)候多做一步-判斷當(dāng)前改正犯的錯(cuò)是否比之前更小,也就是貪心選擇wj -|wt|/T minYi- = y/T constant卜nuLT |min：2jrnr r ；升Hj.*max|血|卩屮世 assumes9

14、linear separable V to haltproperty unknowri in advance (no need tor PLA if we know w/) not fully sure how long halting takes (p depends on wr)though practically fast|wj| - x/T max |H|Pocket Algorithmmodify PLA algorithm (black lines) by keeping best weights in pocketO find a (random) mistake of called(*伽加。 )(try lo) correct the mistake bywf+i i wr + y仃x叩)if Wj+i makes fewer mistakes than w?replace w by w-. until enoughttergtionsreturn w (called