Coursera台大机器学习基础课程学习笔记

1、Coursera台大机器学习基础课程学习笔记1 -机器学习定义及PLA算法最近在跟台大的这个课程，觉得不错，想把学习笔记发出来跟大家分享下，有错误希望大家指正。一机器学习是什么?machine learnimg: improving some porformance imcasuife with experienee computed from datadataimpro'ved4 periorimancenr leasure感觉和Tom M. Mitchell的定义几乎一致,A compu ter p rogram is said to lear n from exp erie ne

2、e E with res pect to some class of tasks T and p erforma nee measure P, if its p erforma nee at tasks in T, as measured by P, im proves with exp erie nee E.简而言之，就是我们想要机器在某些方面有提高（如搜索排名的质量，即NDCG提高），就给机器一些数据（用户的点击数据等各种）然后让机器获得某些经验（Lear ning to rank 的种模型，也就是数学公式）。这里有点需要强调，那就是提高指标,必须要有某种指标可以量化这种提高，这点还是很关

3、键的，工业界做机器学习，首先关注data，其次就是有无成型的 measurement，可以使 Precision/Recall，也可以是 NDCG等。二什么时候可以用机器学习? exists sr-'nie。山门已匚刊站泊0 口引也口1小tr teanigH so p erformance measure can be imp roved but no programmable (easy) definitionso 'ML is needed其实就三要素:1.有规律可以学习;2.编程很难做到;3.有能够学习到规律的数据;编程很难做到可以有多种，大部分原因是系统太复杂，很难用R

4、ule-based的东西去解决，例 如搜索排名，现在影响排名的因素有超多几百种，不可能去想出这些因素的规则，因此，这 时候用机器学习就是恰到好处。特别是移动互联网的今天，用户更容易接触互联网，产生的 数据越来越多，那么要找到某些不容易实现的规律，用机器学习就是很好的了，这也是为啥 机器学习这么火，其实我学机器学习不仅仅是一种投资（肯定它未来的发展前途），我想做 的事情还有一点，就是通过它更深刻的理解人脑的学习过程，提高自己的学习效率和思维能 力。三具体如何用机器学习?Basic Notations输入是两个：1 data ; 2假设集合。Data如何使用？通过提取出feature vector

5、来使用，也就 是那个trai ning examp les ，假设集合是用来选取最终 f的。也就是说，输出就是f （或近似f）。四第一个机器学习算法：PLA （Perceptron Learning Algorithm） 课程讲述这个算法的总体思路如下（典型的提出问题，分析问题以及解决问题）1.通过信用卡问题引入 PLA ；2. 对问题用数学抽象，并得到目标函数;3. 详细解释PLA迭代（学习）过程;4. 证明PLA学习的过程可以收敛并会得到最优解;5. 分析PLA优缺点，并提出克服缺点的一些方法;这个算法本质上是线性分类器，针对给定的feature vector给出Yes或者No的回答F面是

6、用这个算法去解决信用卡问题的数学抽象: For X =（兀|-比.-Xd）维目自of ciiStO'miei compuite a weighted “scord andLdapprove credit it 打册抑 > thresholddeny credit ifEdWjXj < t hires hold y：湎）.一 1!J , 0 ignoredlinear formula ft ?/ arecalled P erce ptro” hypo thesis historically J/?（x） = sign州 X/ Ihreshotd这里的思想在于朴素的把从用户信息

7、抽出来的一些feature （年龄等）量化并组成 vector，然 后乘以一个权重向量，并设定一个阈值，大于这个阈值就表示好，小于表示不好，很明显这 个式子的未知变量有两个（实际只有一个）：1.权重向量 wi, 1<=i<=d;2.阈值，下面设为0做一点小小的变形使得式子更加紧凑,姻MET 一 threshold)signd 1WfXf + ("threshold) (+1)七 /7sign (力 WiXi f=0sign (wx each 'ta w rep rese nts a hypo thesis h & is multiplied with *t

8、air X一wiilli use tali versions to simplify notatton还有就是从这个模型可以知道，regression model也可以解决classification问题，转化的思 想。下面是这个算法的核心，定义了学习目标之后，如何学习？这里的学习是，如何得到最 终的直线去区分 data ？start from some wq (say, 0), and *cofrecf its mistakes on Dy=+1For f = CX1 .0 find a mistake of called (心，/n/)sign（W仏弄y=-iWf. 1 A Wf十y口和u

9、ntil no miore mistakes return last w called Wpla) as gThafs it!A fault confessed is half redressed. : feature vector，找至U错误这个算法的精髓之处在于如何做到"做错能改"，其循环是不断遍历 的点（Yn和当前Wt*Xn不符合），然后校正 Wt,那么为什么要这样校正？因为这样可以保证Wt越来越靠近perfect直线Wf （ps.暂时没想到正向思维是如何得到这个式子的）课程像 大多数课本一样，用逆向思维给予介绍，就是在给定这样能够做的情况下去证明，即证明为 什么这样

10、做可以不断接近目标，以及最终一定会停止?F面道出了 PLA终止的条件: i! PLA halts (ie no mor© mistakes),(归讥Q三三刊cd L ik'i 11 0 allows some w Io make no mistakeassume linear separabledoes PLA always !,i3h?这个是比较容易想到的，如果不能用直线去区分data （线性不可分），肯定是解决不了的,所以必须要满足线性可分，其实问题的关键在于如何方便的知道某些数据是否线性可分？这 个在课程中目前没有涉及，一种简单的解决方法是画出来，直观的去看，这个我觉得

11、不是好 方法。linear separable Q 0 exists perfect Wf such that y* = sign(wjxj j Wf perfect hence every Xn correctly away from line:办wxf) >minynwfxn > 0 w；Wf t by updating with any (x小 y口)wJwf+1 = W； (Wf + “Xf)> wJWz - rnin Xn> w；Wf + 0.W/ app ears more aligned with Wf after up date(really?)W/ c

12、hanged only when mistakeo sign (wjx)丰弘 o 齐wjx曲)< 0 mistake limits' |Wr| growth, even when updating with longest|Wr + yn(f)Xn(olPIM 川 2 + 2yn(f)WXn(r)+ II 齐 Xw)|2 MfiF + o + i% 他)11 |wJ| + max|yrXn| nstart from w。= 0, after T mistake corrections,IlWrII IlwrilWf Wt > 歼-constantLatex 用这两页PPT比

13、较复杂，其实就是在利用条件证明，下面重新组织下给出思路，因为中文不太爽，就用英文了:Gi¥fn 3 conditionsI Wf perfectly fitting those data ineaiis:"讹$)7"：叭(f) > m和 i/wj<rn > 02 wy clianged only when making mistake inasuis：-(-1sEgH(g Xn(O)丰 yn(i Q Si5 盧別U) < ()3 we make corrections by:wt = S-i + 如 5f)We want to prove

14、after t mistake corrections starting from 0, we will get:TT 71n > vT - coiiHtan: 冋II llsHit means 2 things:1 Clause the above equatiou is less equal tb»n 1, we also prove the T will have upper boundary, thus the algorithm will jop at some time;2 tlie left purt the above equation iiivaub the

15、angle of uy and w£ and their angle is decreasing, in other words wt is approaching i”/, thus we are on the right way to get the solutionHere is the provtrthe priinary priiicipic is to r巳卩lace all the varinbltjs which in above equationx are it> ami | u；f| for Wf we have:iisilig (3) using (1)a

16、pplying T times+呗-1)呗-1)Wj逊_1 + rimr如匕升wa 十 T min、T ininfor II蚀 II we have:using 2 2+()+ II如(一 12)1)11using (2)+ max llj-tjpn|叭| 4 T 心|H=Tf心II如nri2lying above '1 co ack is Ions to the left p art of the oquFiticn we finally get:T T片" Wlf昭llglF 皿 ijf宜科' 疔-MH IM-nilr*Trat张仪;心mil/T fin/T co

17、nstantBee皿芒die命盘I < 1小电mmy have:I协；II irvir lln II - 1"2上III如|趴|址7 匸丄j/Krr i 丁”2 丿五PLA的优缺点simple to implement, fast, works in any dimmension dCons nss. m,es'' linear separable 门 to haltpoperty unknown In advance (no need for PLA if we know w/) not fully sure卄 b up niAltiog 仙kgs Q>

18、depend$ on wj though practically fast为了应对Noisy，我们不可能得到完美的直线，那么怎么衡量当前得到的直线能够满足要求呢？凭直觉，我们知道如果当前直线犯错越少越好（对所有data），于是有了下面的改进算法，Pocket PLA，本质上就是在改错的时候多做-判断当前改正犯的错是否比之前更小,也就是贪心选择Pocket Algorithmmodify PLA algorithm (bllack lines) by keepang best wei；,gh£s op pocfe引“d讪川和i匚'卸神*蓟h隠.嘶For f = 0-1 -O find a (random) mistake of Wf called (*和(小卩斤) (Iry to) correct the mistake by"旨，产自r即卅三广 自三e昱:han 帆 rs