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

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

大規(guī)模機器學(xué)習(xí)課程主頁：httppage_id=397陳一帥介紹機器學(xué)習(xí)定義Perceptron（

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

（X,y）X：featurevectory:label目的：找到一個函數(shù)：y=f(X)發(fā)現(xiàn)規(guī)律，預(yù)測未來y類型實數(shù)：Regression布爾值：二元分類有限取值：多元分類無限取值：句子狗狗分類奇瓦瓦狗（體小，毛平滑）小獵兔狗臘腸犬X:高度，重量y:狗的種類文本分類根據(jù)email的內(nèi)容，判斷是否垃圾郵件根據(jù)新聞內(nèi)容，判斷新聞類型SportPoliticsFeaturevector單詞向量（1，0）常用方法無監(jiān)督學(xué)習(xí)聚類有監(jiān)督學(xué)習(xí)決策樹感知機：PerceptronsSVM支持向量機神經(jīng)元網(wǎng)絡(luò)無循環(huán)感知機網(wǎng)絡(luò)基于事例的學(xué)習(xí)Instance-basedlearningKNN模型元素訓(xùn)練集測試集分類器問題：Overfit工作方式BatchlearningOnlinelearning象Stream來一個處理一個，更新分類器能夠處理大訓(xùn)練集應(yīng)用快遞獲單預(yù)測X：出價，起點，終點y：接受/拒絕Online算法持續(xù)收集新數(shù)據(jù)，不斷更新模型感知機感知機神經(jīng)元刺激是輸入入的加權(quán)和和感知機輸入：實數(shù)數(shù)向量輸出：1/-1例：垃圾郵郵件檢測Instance空間類型輸入：X輸出：y模型目標：找到合適的的使0幾何描述W和X向量的點積積（余弦弦距離）wx>0wx<0求W初始化為全全0來一個x，算如果y=y’，W保持不變?nèi)绻鹹!=y，往yx的方向旋轉(zhuǎn)轉(zhuǎn)一點旋轉(zhuǎn)的效果果y(x1)=1卻被判為了了-1W往x1方向轉(zhuǎn)一點W+cyx1判斷平面逆時針旋轉(zhuǎn)轉(zhuǎn)一點試圖把x1包進來收斂性只要是線性性可分割的的，就會收收斂如果不是，，最后會震震蕩，無限限循環(huán)震蕩時的停停止算法震蕩時，如如何停止算算法？逐漸減小調(diào)調(diào)整幅度觀察訓(xùn)練集集上的誤差差觀察一個小小測試集上上的誤差限制最大迭迭代次數(shù)非零判決平移多類感知超過兩類分別訓(xùn)練三三個分類器器誰的wx值最大，算誰Winnow算法總會收斂x取值：0，1初始化w全1，為為x的長度預(yù)測預(yù)測對，w不動預(yù)測錯：y真值是1，可，，說說明w太小，看x中哪些值為為1，把對應(yīng)的的w加倍y真值是-1，可，，說明w太大，看x中哪些值為為1，把對應(yīng)的的w減半的調(diào)整把它加到w里，一起變變允許對對應(yīng)的x為-1，但調(diào)整方方法反過來來：預(yù)測錯：y真值是1，，，說明太大，減半y真值是-1，，說說明太小，加倍擴展平衡Winnow（BalancedWinnow）ThickSeparator界限（Margin）放松非線性邊界界變換到線性性上Map-Reduce的實現(xiàn)每個機器處處理部分xMap：如果出錯，，生成鍵值值對（i,cyxi)表示要對wi進行調(diào)整c為調(diào)整速度度Reduce累積，實現(xiàn)現(xiàn)對w的調(diào)整重復(fù)，直到收斂斂，或到達達停止的條條件感知機總結(jié)結(jié)感知機加法更新w適合x少，互相有有相關(guān)性Winnonw乘法更新w適合x多，互相無無相關(guān)性感知機總結(jié)結(jié)是一種Online算法新(x,y)到達，更新新w局限線性分割線性不可分分的話，不不收斂Feature多時，效果果一般問題過擬合哪個最優(yōu)？？問題一旦找到邊邊界，就停停止，不是是最優(yōu)SVM問題尋找最佳的的線性分割割最大化MarginMargin到分割平面面的距離，越寬寬越好最優(yōu)分割平平面SVM改進Perceptron的問題：最最大化MarginMargin的數(shù)學(xué)描述述A在B上的投影點積MarginAM在w上的投影M在L上最大化Margin即：SVM求最佳分割割平面最佳分割平平面由支持向量決定d維X，一般有d+1個支持向量量其他點可以以忽略歸一化最佳佳分割平面面w，b加倍，margin也加倍，不不好找Max加約束||W||=1給b也加一個約約束，支持持向量xi在上面等于于1/-1歸一化結(jié)果最小化||W||優(yōu)化問題轉(zhuǎn)轉(zhuǎn)化優(yōu)化最小化||W||SVMwith““hard”約束即：優(yōu)化訓(xùn)練集最優(yōu)解:不能線性分割引入懲罰：：離邊界的的距離優(yōu)化問題轉(zhuǎn)轉(zhuǎn)化為懲罰因子CC大：Care，懲罰大C=0:無所謂也叫懲罰函數(shù)Z離邊界的距距離優(yōu)化Matlab求解BigData時，求解困困難最小化Convex函數(shù)GradientDescent（梯度下降降）遞歸懲罰函數(shù)的的導(dǎo)數(shù)如果y=1如果y=-1總結(jié)小結(jié)：梯度度下降法目標：求w，最小化梯度下降，，調(diào)整w梯度SVM例C=0.1，b作為一個W，參與優(yōu)化化，初始W=[0,1],b=-2b對應(yīng)的樣本本值為1訓(xùn)練集獲得得懲懲罰罰函函數(shù)數(shù)導(dǎo)數(shù)數(shù)表代入入訓(xùn)練練集集計算算梯梯度度代入入初初始始w=[u,v,b]=[0,1,-2]，過過一一遍遍表表，，得得到到第二二行行不不滿滿足足獲得得梯梯度度更新新w重復(fù)復(fù)掃描描懲懲罰罰函函數(shù)數(shù)表表，，計算算梯梯度度調(diào)整整權(quán)權(quán)重重MapReducMap管不不同同的的懲懲罰罰函函數(shù)數(shù)行行Reduce加起起來來，，獲獲得得梯梯度度問題題調(diào)整整一一次次W，對對所所有有樣樣本本都都過過一一遍遍StochasticGradientDescent翻過過來來:對每個樣樣本（共共n個），把把各維更更新一遍遍性能評估LeonBottou文本分類類ReutersRCV1文檔Trainset：n=781,000（文檔））Testset:23,000d=50,000features（單詞））移走禁用用詞stop-words移走低頻頻詞結(jié)果速度大大大提高準確度合理的質(zhì)質(zhì)量情況況下，時時間大大大縮短擴展BatchConjugateGradient收斂更快快SGD更簡單多次SGD，比一次次BCG好。實際需要選擇擇和和Leon建議選，，使使期望的的初始更更新和期期望的權(quán)權(quán)重可比比選：：挑少量樣樣本嘗試10,1,0.1,0.01,……選效果最最好的實際當x稀疏時近似為兩兩步因為x稀疏，所所以，第第一步中中更新的的Wi少兩種方案案：W=SV，S為標量，，V為向量第二步頻頻率低一一些，大大一些停止在測試集集上檢驗驗在訓(xùn)練集集上檢驗驗多類方法1：類似感感知機訓(xùn)練三個個分類器器選多類方法2：同時學(xué)學(xué)習(xí)三類類權(quán)重優(yōu)化問題題類似地解解最近鄰K-NearestNeighbor(KNN)Instancebasedlearning保存整個個訓(xùn)練集集{(x,y)}新查詢q尋找最近近的樣例例根據(jù)樣例例，預(yù)測測q的y回歸/分類例：Collaborativefiltering尋找K個最相似似的用戶戶根據(jù)他們們的評分分，預(yù)測測用戶的的評分四要素距離Metric：最近EuclideanK的選擇加權(quán)函數(shù)數(shù)預(yù)測平均K=1K=9Kernel回歸K：所有已已知樣本本加權(quán)函數(shù)數(shù)K=9最近鄰尋尋找算法線性掃描描基于樹的高維維Index結(jié)構(gòu)Multidimensionalindexstructures主存Quadtreekd-tree第二存儲儲R-trees高維的挑挑戰(zhàn)curseofdimensionality維數(shù)詛咒咒兩種方法法VAFiles兩級降維（SVD）到低維處處理非歐式距距離ManhattandistanceJaccarddistance用LSH近似相似似決策樹DecisionTree決策樹回歸分類構(gòu)造樹1)FindBestSplit–分類最大化信信息增益益1）FindBestSplit–回歸最大化對數(shù)值：：Sort，然后依依次檢查查對類型：：按子集集2)StoppingCriteria很多啟發(fā)發(fā)式方法法方差足夠夠小元素足夠夠少3)FindPrediction回歸返回葉子中元元素均值值返回葉子中元素線性性回歸分類返回葉子中元素類型型MapReduce實現(xiàn)ParallelLearnerforAssemblingNumerousEnsembleTrees[Pandaetal.,VLDB‘09]一級一個個Map-ReduceMapper考慮大量量可能的的SplitReduce綜合，決決定最優(yōu)優(yōu)Split裝袋Bagging采樣訓(xùn)練練集學(xué)習(xí)多個個樹組合其預(yù)預(yù)測結(jié)果果，得到到更好的的結(jié)果很實用的的方法SVMvs.DT比較ReferB.Panda,J.S.Herbach,S.Basu,andR.J.Bayardo.PLANET:Massivelyparallellearningoftree