大數(shù)據(jù)存儲(chǔ)與處理-大規(guī)模機(jī)器學(xué)習(xí)課件

大數(shù)據(jù)存儲(chǔ)與應(yīng)用

大規(guī)模機(jī)器學(xué)習(xí)課程主頁(yè)：http:///?page_id=397陳一帥chenyishuai@大數(shù)據(jù)存儲(chǔ)與應(yīng)用

大規(guī)模機(jī)器學(xué)習(xí)1介紹機(jī)器學(xué)習(xí)定義Perceptron（

感知機(jī)）SVM（support-vectormachines）支持向量機(jī)最近鄰（nearestneighbor）決策樹(shù)介紹機(jī)器學(xué)習(xí)定義2機(jī)器學(xué)習(xí)訓(xùn)練集

（X,y）X：featurevectory:label目的：找到一個(gè)函數(shù)：y=f(X)發(fā)現(xiàn)規(guī)律，預(yù)測(cè)未來(lái)y類型實(shí)數(shù)：Regression布爾值：二元分類有限取值：多元分類無(wú)限取值：句子機(jī)器學(xué)習(xí)訓(xùn)練集（X,y）3狗狗分類奇瓦瓦狗（體小，毛平滑）小獵兔狗臘腸犬X:高度，重量y:狗的種類狗狗分類奇瓦瓦狗（體小，毛平滑）小獵兔狗臘腸犬X:高度，4文本分類根據(jù)email的內(nèi)容，判斷是否垃圾郵件根據(jù)新聞內(nèi)容，判斷新聞?lì)愋蚐portPoliticsFeaturevector單詞向量（1，0）文本分類根據(jù)email的內(nèi)容，判斷是否垃圾郵件5常用方法無(wú)監(jiān)督學(xué)習(xí)聚類有監(jiān)督學(xué)習(xí)決策樹(shù)感知機(jī)：PerceptronsSVM支持向量機(jī)神經(jīng)元網(wǎng)絡(luò)無(wú)循環(huán)感知機(jī)網(wǎng)絡(luò)基于事例的學(xué)習(xí)Instance-basedlearningKNN常用方法無(wú)監(jiān)督學(xué)習(xí)6模型元素訓(xùn)練集測(cè)試集分類器問(wèn)題：Overfit模型元素7工作方式BatchlearningOnlinelearning象Stream來(lái)一個(gè)處理一個(gè)，更新分類器能夠處理大訓(xùn)練集工作方式Batchlearning8應(yīng)用快遞獲單預(yù)測(cè)X：出價(jià)，起點(diǎn)，終點(diǎn)y：接受/拒絕Online算法持續(xù)收集新數(shù)據(jù)，不斷更新模型應(yīng)用快遞獲單預(yù)測(cè)9感知機(jī)感知機(jī)10感知機(jī)神經(jīng)元刺激是輸入的加權(quán)和感知機(jī)神經(jīng)元11感知機(jī)輸入：實(shí)數(shù)向量輸出：1/-1例：垃圾郵件檢測(cè)Instance空間類型輸入：X輸出：y感知機(jī)輸入：實(shí)數(shù)向量Instance空間類型輸入：X輸出：12模型目標(biāo)：找到合適的使0模型目標(biāo)：013幾何描述W和X向量的點(diǎn)積（余弦距離）wx>0wx<0幾何描述W和X向量的點(diǎn)積（余弦距離）wx>0wx<14求W初始化為全0來(lái)一個(gè)x，算如果y=y’，W保持不變?nèi)绻鹹!=y，往yx的方向旋轉(zhuǎn)一點(diǎn)求W初始化為全015旋轉(zhuǎn)的效果y(x1)=1卻被判為了-1W往x1方向轉(zhuǎn)一點(diǎn)W+cyx1判斷平面逆時(shí)針旋轉(zhuǎn)一點(diǎn)試圖把x1包進(jìn)來(lái)旋轉(zhuǎn)的效果y(x1)=116收斂性只要是線性可分割的，就會(huì)收斂如果不是，最后會(huì)震蕩，無(wú)限循環(huán)收斂性只要是線性可分割的，就會(huì)收斂17震蕩時(shí)的停止算法震蕩時(shí)，如何停止算法？逐漸減小調(diào)整幅度觀察訓(xùn)練集上的誤差觀察一個(gè)小測(cè)試集上的誤差限制最大迭代次數(shù)震蕩時(shí)的停止算法震蕩時(shí)，如何停止算法？18非零判決平移非零判決平移19多類感知超過(guò)兩類分別訓(xùn)練三個(gè)分類器誰(shuí)的wx值最大，算誰(shuí)多類感知超過(guò)兩類誰(shuí)的wx值最大，算誰(shuí)20Winnow算法總會(huì)收斂x取值：0，1初始化w

全1，為x的長(zhǎng)度預(yù)測(cè)預(yù)測(cè)對(duì)，w不動(dòng)預(yù)測(cè)錯(cuò)：y真值是1，可，說(shuō)明w太小，看x中哪些值為1，把對(duì)應(yīng)的w加倍y真值是-1，可，說(shuō)明w太大，看x中哪些值為1，把對(duì)應(yīng)的w減半Winnow算法總會(huì)收斂21的調(diào)整把它加到w里，一起變?cè)试S對(duì)應(yīng)的x為-1，但調(diào)整方法反過(guò)來(lái)：預(yù)測(cè)錯(cuò)：y真值是1，，說(shuō)明

太大，減半y真值是-1，，說(shuō)明

太小，加倍的調(diào)整把它加到w里，一起變?cè)试S對(duì)應(yīng)的x為22擴(kuò)展平衡Winnow（BalancedWinnow）ThickSeparator界限（Margin）放松擴(kuò)展平衡Winnow（BalancedWinnow）23非線性邊界變換到線性上非線性邊界變換到線性上24Map-Reduce的實(shí)現(xiàn)每個(gè)機(jī)器處理部分xMap：如果出錯(cuò)，生成鍵值對(duì)（i,cyxi)表示要對(duì)wi進(jìn)行調(diào)整c為調(diào)整速度Reduce累積，實(shí)現(xiàn)對(duì)w的調(diào)整重復(fù)，直到收斂，或到達(dá)停止的條件Map-Reduce的實(shí)現(xiàn)每個(gè)機(jī)器處理部分x25感知機(jī)總結(jié)感知機(jī)加法更新w適合x(chóng)少，互相有相關(guān)性Winnonw乘法更新w適合x(chóng)多，互相無(wú)相關(guān)性感知機(jī)總結(jié)感知機(jī)26感知機(jī)總結(jié)是一種Online算法新(x,y)到達(dá)，更新w局限線性分割線性不可分的話，不收斂Feature多時(shí)，效果一般感知機(jī)總結(jié)是一種Online算法27問(wèn)題過(guò)擬合哪個(gè)最優(yōu)？問(wèn)題過(guò)擬合28問(wèn)題一旦找到邊界，就停止，不是最優(yōu)問(wèn)題一旦找到邊界，就停止，不是最優(yōu)29SVMSVM30問(wèn)題尋找最佳的線性分割問(wèn)題尋找最佳的線性分割31最大化MarginMargin到分割平面的距離，越寬越好最優(yōu)分割平面最大化MarginMargin32SVM改進(jìn)Perceptron的問(wèn)題：最大化MarginSVM改進(jìn)Perceptron的問(wèn)題：最大化Margin33Margin的數(shù)學(xué)描述A在B上的投影點(diǎn)積Margin的數(shù)學(xué)描述A在B上的投影點(diǎn)積34MarginAM在w上的投影M在L上MarginAM在w上的投影M在L上35最大化Margin即：最大化Margin即：36SVM求最佳分割平面最佳分割平面由支持向量決定d維X，一般有d+1個(gè)支持向量其他點(diǎn)可以忽略SVM求最佳分割平面最佳分割平面由支持向量決定37歸一化最佳分割平面w，b加倍，margin也加倍，不好找Max加約束

||W||=1給b也加一個(gè)約束，支持向量xi在上面等于1/-1歸一化最佳分割平面w，b加倍，margin也加倍，不好找Ma38歸一化結(jié)果歸一化結(jié)果39最小化||W||優(yōu)化問(wèn)題轉(zhuǎn)化最小化||W||優(yōu)化問(wèn)題轉(zhuǎn)化40優(yōu)化最小化||W||SVMwith“hard”約束即：優(yōu)化最小化||W||41優(yōu)化訓(xùn)練集最優(yōu)解:優(yōu)化訓(xùn)練集最優(yōu)解:42不能線性分割引入懲罰：離邊界的距離優(yōu)化問(wèn)題轉(zhuǎn)化為不能線性分割引入懲罰：離邊界的距離43懲罰因子CC大：Care，懲罰大C=0:無(wú)所謂也叫懲罰因子CC大：Care，懲罰大44懲罰函數(shù)Z離邊界的距離懲罰函數(shù)Z離邊界的距離45優(yōu)化Matlab求解BigData時(shí)，求解困難最小化Convex函數(shù)GradientDescent（梯度下降）遞歸優(yōu)化Matlab求解46懲罰函數(shù)的導(dǎo)數(shù)如果y=1如果y=-1總結(jié)懲罰函數(shù)的導(dǎo)數(shù)如果y=147小結(jié)：梯度下降法目標(biāo)：求w，最小化梯度下降，調(diào)整w梯度小結(jié)：梯度下降法目標(biāo)：求w，最小化48SVMSVM49例C=0.1，b作為一個(gè)W，參與優(yōu)化，初始W=[0,1],b=-2b對(duì)應(yīng)的樣本值為1訓(xùn)練集例C=0.1，50獲得懲罰函數(shù)導(dǎo)數(shù)表代入訓(xùn)練集獲得懲罰函數(shù)導(dǎo)數(shù)表代入訓(xùn)練集51計(jì)算梯度代入初始w=[u,v,b]=[0,1,-2]，過(guò)一遍表，得到第二行不滿足獲得梯度計(jì)算梯度代入初始w=[u,v,b]=[0,1,-2]，過(guò)52更新w重復(fù)掃描懲罰函數(shù)表，計(jì)算梯度調(diào)整權(quán)重MapReducMap管不同的懲罰函數(shù)行Reduce加起來(lái)，獲得梯度更新w53問(wèn)題調(diào)整一次W，對(duì)所有樣本都過(guò)一遍StochasticGradientDescent翻過(guò)來(lái):對(duì)每個(gè)樣本（共n個(gè)），把各維更新一遍問(wèn)題調(diào)整一次W，對(duì)所有樣本都過(guò)一遍54性能評(píng)估LeonBottou文本分類ReutersRCV1文檔Trainset：n=781,000（文檔）Testset:23,000d=50,000features（單詞）移走禁用詞stop-words移走低頻詞性能評(píng)估LeonBottou55結(jié)果速度大大提高結(jié)果速度大大提高56準(zhǔn)確度合理的質(zhì)量情況下，時(shí)間大大縮短準(zhǔn)確度合理的質(zhì)量情況下，時(shí)間大大縮短57擴(kuò)展BatchConjugateGradient收斂更快SGD更簡(jiǎn)單多次SGD，比一次BCG好。擴(kuò)展BatchConjugateGradient58實(shí)際需要選擇和Leon建議選，使期望的初始更新和期望的權(quán)重可比選：挑少量樣本嘗試10,1,0.1,0.01,…選效果最好的實(shí)際需要選擇和59實(shí)際當(dāng)x稀疏時(shí)近似為兩步因?yàn)閤稀疏，所以，第一步中更新的Wi少兩種方案：W=SV，S為標(biāo)量，V為向量第二步頻率低一些，大一些實(shí)際當(dāng)x稀疏時(shí)60停止在測(cè)試集上檢驗(yàn)在訓(xùn)練集上檢驗(yàn)停止在測(cè)試集上檢驗(yàn)61多類方法1：類似感知機(jī)訓(xùn)練三個(gè)分類器選多類方法1：類似感知機(jī)62多類方法2：同時(shí)學(xué)習(xí)三類權(quán)重優(yōu)化問(wèn)題類似地解多類方法2：同時(shí)學(xué)習(xí)三類權(quán)重63最近鄰最近鄰64K-NearestNeighbor(KNN)Instancebasedlearning保存整個(gè)訓(xùn)練集{(x,y)}新查詢q尋找最近的樣例根據(jù)樣例，預(yù)測(cè)q的y回歸/分類例：Collaborativefiltering尋找K個(gè)最相似的用戶根據(jù)他們的評(píng)分，預(yù)測(cè)用戶的評(píng)分K-NearestNeighbor(KNN)Instan65四要素距離Metric：最近EuclideanK的選擇加權(quán)函數(shù)預(yù)測(cè)平均四要素距離Metric：最近66K=1K=9K=1K=967Kernel回歸K：所有已知樣本加權(quán)函數(shù)K=9Kernel回歸K：所有已知樣本K=968最近鄰尋找算法線性掃描基于樹(shù)的高維Index結(jié)構(gòu)Multidimensionalindexstructures主存Quadtreekd-tree第二存儲(chǔ)R-trees最近鄰尋找算法線性掃描69高維的挑戰(zhàn)curseofdimensionality維數(shù)詛咒兩種方法VAFiles兩級(jí)降維（SVD）到低維處理高維的挑戰(zhàn)curseofdimensionality70非歐式距離ManhattandistanceJaccarddistance用LSH近似相似非歐式距離Manhattandistance71決策樹(shù)DecisionTree決策樹(shù)DecisionTree72決策樹(shù)回歸分類決策樹(shù)回歸73構(gòu)造樹(shù)構(gòu)造樹(shù)741)FindBestSplit–分類最大化信息增益1)FindBestSplit–分類最大化信息增益751）FindBestSplit–回歸最大化對(duì)數(shù)值：Sort，然后依次檢查對(duì)類型：按子集1）FindBestSplit–回歸最大化762)StoppingCriteria很多啟發(fā)式方法方差足夠小元素足夠少2)StoppingCriteria很多啟發(fā)式方法773)FindPrediction回歸返回葉子中元素均值返回葉子中元素線性回歸分類返回葉子中元素類型3)FindPrediction回歸78MapReduce實(shí)現(xiàn)ParallelLearnerforAssemblingNumerousEnsembleTrees[Pandaetal.,VLDB‘09]一級(jí)一個(gè)Map-ReduceMapper考慮大量可能的SplitReduce綜合，決定最優(yōu)SplitMapReduce實(shí)現(xiàn)ParallelLearnerfo79裝袋Bagging采樣訓(xùn)練集學(xué)習(xí)多個(gè)樹(shù)組合其預(yù)測(cè)結(jié)果，得到更好的結(jié)果很實(shí)用的方法裝袋Bagging80SVMvs.DT比較SVMvs.DT比較81ReferB.Panda,J.S.Herbach,S.Basu,andR.J.Bayardo.PLANET:MassivelyparallellearningoftreeensembleswithMapReduce.VLDB2009.J.Ye,J.-H.Chow,J.Chen,Z.Zheng.StochasticGradientBoostedDistributedDecisionTrees.CIKM2009.ReferB.Panda,J.S.Herbach,82總結(jié)機(jī)器學(xué)習(xí)Perceptron（

感知機(jī)）SVM（support-vectormachines）支持向量機(jī)最近鄰（nearestneighbor）決策樹(shù)總結(jié)機(jī)器學(xué)習(xí)83大數(shù)據(jù)存儲(chǔ)與應(yīng)用

大規(guī)模機(jī)器學(xué)習(xí)課程主頁(yè)：http:///?page_id=397陳一帥chenyishuai@大數(shù)據(jù)存儲(chǔ)與應(yīng)用

大規(guī)模機(jī)器學(xué)習(xí)84介紹機(jī)器學(xué)習(xí)定義Perceptron（

感知機(jī)）SVM（support-vectormachines）支持向量機(jī)最近鄰（nearestneighbor）決策樹(shù)介紹機(jī)器學(xué)習(xí)定義85機(jī)器學(xué)習(xí)訓(xùn)練集

（X,y）X：featurevectory:label目的：找到一個(gè)函數(shù)：y=f(X)發(fā)現(xiàn)規(guī)律，預(yù)測(cè)未來(lái)y類型實(shí)數(shù)：Regression布爾值：二元分類有限取值：多元分類無(wú)限取值：句子機(jī)器學(xué)習(xí)訓(xùn)練集（X,y）86狗狗分類奇瓦瓦狗（體小，毛平滑）小獵兔狗臘腸犬X:高度，重量y:狗的種類狗狗分類奇瓦瓦狗（體小，毛平滑）小獵兔狗臘腸犬X:高度，87文本分類根據(jù)email的內(nèi)容，判斷是否垃圾郵件根據(jù)新聞內(nèi)容，判斷新聞?lì)愋蚐portPoliticsFeaturevector單詞向量（1，0）文本分類根據(jù)email的內(nèi)容，判斷是否垃圾郵件88常用方法無(wú)監(jiān)督學(xué)習(xí)聚類有監(jiān)督學(xué)習(xí)決策樹(shù)感知機(jī)：PerceptronsSVM支持向量機(jī)神經(jīng)元網(wǎng)絡(luò)無(wú)循環(huán)感知機(jī)網(wǎng)絡(luò)基于事例的學(xué)習(xí)Instance-basedlearningKNN常用方法無(wú)監(jiān)督學(xué)習(xí)89模型元素訓(xùn)練集測(cè)試集分類器問(wèn)題：Overfit模型元素90工作方式BatchlearningOnlinelearning象Stream來(lái)一個(gè)處理一個(gè)，更新分類器能夠處理大訓(xùn)練集工作方式Batchlearning91應(yīng)用快遞獲單預(yù)測(cè)X：出價(jià)，起點(diǎn)，終點(diǎn)y：接受/拒絕Online算法持續(xù)收集新數(shù)據(jù)，不斷更新模型應(yīng)用快遞獲單預(yù)測(cè)92感知機(jī)感知機(jī)93感知機(jī)神經(jīng)元刺激是輸入的加權(quán)和感知機(jī)神經(jīng)元94感知機(jī)輸入：實(shí)數(shù)向量輸出：1/-1例：垃圾郵件檢測(cè)Instance空間類型輸入：X輸出：y感知機(jī)輸入：實(shí)數(shù)向量Instance空間類型輸入：X輸出：95模型目標(biāo)：找到合適的使0模型目標(biāo)：096幾何描述W和X向量的點(diǎn)積（余弦距離）wx>0wx<0幾何描述W和X向量的點(diǎn)積（余弦距離）wx>0wx<97求W初始化為全0來(lái)一個(gè)x，算如果y=y’，W保持不變?nèi)绻鹹!=y，往yx的方向旋轉(zhuǎn)一點(diǎn)求W初始化為全098旋轉(zhuǎn)的效果y(x1)=1卻被判為了-1W往x1方向轉(zhuǎn)一點(diǎn)W+cyx1判斷平面逆時(shí)針旋轉(zhuǎn)一點(diǎn)試圖把x1包進(jìn)來(lái)旋轉(zhuǎn)的效果y(x1)=199收斂性只要是線性可分割的，就會(huì)收斂如果不是，最后會(huì)震蕩，無(wú)限循環(huán)收斂性只要是線性可分割的，就會(huì)收斂100震蕩時(shí)的停止算法震蕩時(shí)，如何停止算法？逐漸減小調(diào)整幅度觀察訓(xùn)練集上的誤差觀察一個(gè)小測(cè)試集上的誤差限制最大迭代次數(shù)震蕩時(shí)的停止算法震蕩時(shí)，如何停止算法？101非零判決平移非零判決平移102多類感知超過(guò)兩類分別訓(xùn)練三個(gè)分類器誰(shuí)的wx值最大，算誰(shuí)多類感知超過(guò)兩類誰(shuí)的wx值最大，算誰(shuí)103Winnow算法總會(huì)收斂x取值：0，1初始化w

全1，為x的長(zhǎng)度預(yù)測(cè)預(yù)測(cè)對(duì)，w不動(dòng)預(yù)測(cè)錯(cuò)：y真值是1，可，說(shuō)明w太小，看x中哪些值為1，把對(duì)應(yīng)的w加倍y真值是-1，可，說(shuō)明w太大，看x中哪些值為1，把對(duì)應(yīng)的w減半Winnow算法總會(huì)收斂104的調(diào)整把它加到w里，一起變?cè)试S對(duì)應(yīng)的x為-1，但調(diào)整方法反過(guò)來(lái)：預(yù)測(cè)錯(cuò)：y真值是1，，說(shuō)明

太大，減半y真值是-1，，說(shuō)明

太小，加倍的調(diào)整把它加到w里，一起變?cè)试S對(duì)應(yīng)的x為105擴(kuò)展平衡Winnow（BalancedWinnow）ThickSeparator界限（Margin）放松擴(kuò)展平衡Winnow（BalancedWinnow）106非線性邊界變換到線性上非線性邊界變換到線性上107Map-Reduce的實(shí)現(xiàn)每個(gè)機(jī)器處理部分xMap：如果出錯(cuò)，生成鍵值對(duì)（i,cyxi)表示要對(duì)wi進(jìn)行調(diào)整c為調(diào)整速度Reduce累積，實(shí)現(xiàn)對(duì)w的調(diào)整重復(fù)，直到收斂，或到達(dá)停止的條件Map-Reduce的實(shí)現(xiàn)每個(gè)機(jī)器處理部分x108感知機(jī)總結(jié)感知機(jī)加法更新w適合x(chóng)少，互相有相關(guān)性Winnonw乘法更新w適合x(chóng)多，互相無(wú)相關(guān)性感知機(jī)總結(jié)感知機(jī)109感知機(jī)總結(jié)是一種Online算法新(x,y)到達(dá)，更新w局限線性分割線性不可分的話，不收斂Feature多時(shí)，效果一般感知機(jī)總結(jié)是一種Online算法110問(wèn)題過(guò)擬合哪個(gè)最優(yōu)？問(wèn)題過(guò)擬合111問(wèn)題一旦找到邊界，就停止，不是最優(yōu)問(wèn)題一旦找到邊界，就停止，不是最優(yōu)112SVMSVM113問(wèn)題尋找最佳的線性分割問(wèn)題尋找最佳的線性分割114最大化MarginMargin到分割平面的距離，越寬越好最優(yōu)分割平面最大化MarginMargin115SVM改進(jìn)Perceptron的問(wèn)題：最大化MarginSVM改進(jìn)Perceptron的問(wèn)題：最大化Margin116Margin的數(shù)學(xué)描述A在B上的投影點(diǎn)積Margin的數(shù)學(xué)描述A在B上的投影點(diǎn)積117MarginAM在w上的投影M在L上MarginAM在w上的投影M在L上118最大化Margin即：最大化Margin即：119SVM求最佳分割平面最佳分割平面由支持向量決定d維X，一般有d+1個(gè)支持向量其他點(diǎn)可以忽略SVM求最佳分割平面最佳分割平面由支持向量決定120歸一化最佳分割平面w，b加倍，margin也加倍，不好找Max加約束

||W||=1給b也加一個(gè)約束，支持向量xi在上面等于1/-1歸一化最佳分割平面w，b加倍，margin也加倍，不好找Ma121歸一化結(jié)果歸一化結(jié)果122最小化||W||優(yōu)化問(wèn)題轉(zhuǎn)化最小化||W||優(yōu)化問(wèn)題轉(zhuǎn)化123優(yōu)化最小化||W||SVMwith“hard”約束即：優(yōu)化最小化||W||124優(yōu)化訓(xùn)練集最優(yōu)解:優(yōu)化訓(xùn)練集最優(yōu)解:125不能線性分割引入懲罰：離邊界的距離優(yōu)化問(wèn)題轉(zhuǎn)化為不能線性分割引入懲罰：離邊界的距離126懲罰因子CC大：Care，懲罰大C=0:無(wú)所謂也叫懲罰因子CC大：Care，懲罰大127懲罰函數(shù)Z離邊界的距離懲罰函數(shù)Z離邊界的距離128優(yōu)化Matlab求解BigData時(shí)，求解困難最小化Convex函數(shù)GradientDescent（梯度下降）遞歸優(yōu)化Matlab求解129懲罰函數(shù)的導(dǎo)數(shù)如果y=1如果y=-1總結(jié)懲罰函數(shù)的導(dǎo)數(shù)如果y=1130小結(jié)：梯度下降法目標(biāo)：求w，最小化梯度下降，調(diào)整w梯度小結(jié)：梯度下降法目標(biāo)：求w，最小化131SVMSVM132例C=0.1，b作為一個(gè)W，參與優(yōu)化，初始W=[0,1],b=-2b對(duì)應(yīng)的樣本值為1訓(xùn)練集例C=0.1，133獲得懲罰函數(shù)導(dǎo)數(shù)表代入訓(xùn)練集獲得懲罰函數(shù)導(dǎo)數(shù)表代入訓(xùn)練集134計(jì)算梯度代入初始w=[u,v,b]=[0,1,-2]，過(guò)一遍表，得到第二行不滿足獲得梯度計(jì)算梯度代入初始w=[u,v,b]=[0,1,-2]，過(guò)135更新w重復(fù)掃描懲罰函數(shù)表，計(jì)算梯度調(diào)整權(quán)重MapReducMap管不同的懲罰函數(shù)行Reduce加起來(lái)，獲得梯度更新w136問(wèn)題調(diào)整一次W，對(duì)所有樣本都過(guò)一遍StochasticGradientDescent翻過(guò)來(lái):對(duì)每個(gè)樣本（共n個(gè)），把各維更新一遍問(wèn)題調(diào)整一次W，對(duì)所有樣本都過(guò)一遍137性能評(píng)估LeonBottou文本分類ReutersRCV1文檔Trainset：n=781,000（文檔）Testset:23,000d=50,000features（單詞）移走禁用詞stop-words移走低頻詞性能評(píng)估LeonBottou138結(jié)果速度大大提高結(jié)果速度大大提高139準(zhǔn)確度合理的質(zhì)量情況下，時(shí)間大大縮短準(zhǔn)確度合理的質(zhì)量情況下，時(shí)間大大縮短140擴(kuò)展BatchConjugateGradient收斂更快SGD更簡(jiǎn)單多次SGD，比一次BCG好。擴(kuò)展BatchConjugateGradient141實(shí)際需要選擇和Leon建議選，使期望的初始更新和期望的權(quán)重可比選：挑少量樣本嘗試10,1,0.1,0.01,…選效果最好的實(shí)際需要選擇和142實(shí)際當(dāng)x稀疏時(shí)近似為兩步因?yàn)閤稀疏，所以，第一步中更新的Wi少兩種方案：W=SV，S為標(biāo)量，V為向量第二步頻率低一些，大一些實(shí)際當(dāng)x稀疏時(shí)143停止在測(cè)試集上檢驗(yàn)在訓(xùn)練集上檢驗(yàn)停止在測(cè)試集上檢驗(yàn)144多類方法1：類似感知機(jī)訓(xùn)練三個(gè)分類器選多類方法1：類似感知機(jī)145多類方法2：同時(shí)學(xué)習(xí)三類權(quán)重優(yōu)化問(wèn)題類似地解多類方法2：同時(shí)學(xué)習(xí)三類權(quán)重146最近鄰最近鄰147K-NearestNeighbor(KNN)Instancebasedlearning保存整個(gè)訓(xùn)練集{(x,y)}新查詢q尋找最近的樣例根據(jù)樣例，預(yù)測(cè)q的y回歸/分類例：Collaborativefiltering尋找K個(gè)最相似的用戶根據(jù)他們的評(píng)分，預(yù)測(cè)用戶的評(píng)分K-NearestNeighbor(KNN)Instan148四要素距離Metric：最近EuclideanK的選擇加權(quán)函數(shù)預(yù)測(cè)平均四要素距離Metric：最近149K=1K=9K=1K=9150Kernel回歸K：所有已知樣本加權(quán)函數(shù)K=9Kernel回歸K：所有已知樣本K=9151最近鄰尋找算法線性掃描基于樹(shù)的高維Index結(jié)構(gòu)Multidimensionalindexstructures主存Quadtreekd-tree第二存儲(chǔ)R-trees最近鄰尋找算法線性掃描152高維的挑戰(zhàn)curseofdimensionality維數(shù)詛