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

1、大數(shù)據(jù)存儲與應(yīng)用大數(shù)據(jù)存儲與應(yīng)用大規(guī)模機(jī)器學(xué)習(xí)大規(guī)模機(jī)器學(xué)習(xí)課程主頁：http:/ 機(jī)器學(xué)習(xí)定義 Perceptron （ 感知機(jī)） SVM（ support-vector machines）支持向量機(jī) 最近鄰（ nearest neighbor） 決策樹機(jī)器學(xué)習(xí) 訓(xùn)練集 （X, y） X：feature vector y: label 目的： 找到一個函數(shù)：y = f(X) 發(fā)現(xiàn)規(guī)律，預(yù)測未來 y類型 實數(shù)：Regression 布爾值：二元分類 有限取值：多元分類 無限取值：句子狗狗分類奇瓦瓦狗（體小，毛平滑）小獵兔狗臘腸犬X: 高度，重量y: 狗的種類文本分類 根據(jù)email的內(nèi)容，判斷

2、是否垃圾郵件 根據(jù)新聞內(nèi)容，判斷新聞類型 Sport Politics Feature vector 單詞向量（1，0）常用方法 無監(jiān)督學(xué)習(xí) 聚類 有監(jiān)督學(xué)習(xí) 決策樹 感知機(jī)：Perceptrons SVM 支持向量機(jī) 神經(jīng)元網(wǎng)絡(luò) 無循環(huán)感知機(jī)網(wǎng)絡(luò) 基于事例的學(xué)習(xí) Instance-based learning KNN模型 元素 訓(xùn)練集 測試集 分類器 問題：Overfit工作方式 Batch learning Online learning 象Stream 來一個處理一個，更新分類器 能夠處理大訓(xùn)練集應(yīng)用 快遞獲單預(yù)測 X：出價，起點(diǎn)，終點(diǎn) y：接受/拒絕 Online算法 持續(xù)收集新數(shù)據(jù)，

3、不斷更新模型感知機(jī)感知機(jī) 神經(jīng)元 刺激是輸入的加權(quán)和感知機(jī) 輸入：實數(shù)向量 輸出：1/-1 例：垃圾郵件檢測Instance 空間類型輸入：X輸出：y模型 目標(biāo)： 找到合適的 使0幾何描述 W和X向量的點(diǎn)積 （余弦距離）wx 0wx 0求W 初始化為全0 來一個x，算 如果y=y，W保持不變 如果y!=y，往yx的方向旋轉(zhuǎn)一點(diǎn)旋轉(zhuǎn)的效果 y(x1) = 1 卻被判為了-1 W往x1方向轉(zhuǎn)一點(diǎn) W + cyx1 判斷平面逆時針旋轉(zhuǎn)一點(diǎn) 試圖把x1包進(jìn)來收斂性 只要是線性可分割的，就會收斂 如果不是，最后會震蕩，無限循環(huán)震蕩時的停止算法 震蕩時，如何停止算法？ 逐漸減小調(diào)整幅度 觀察訓(xùn)練集上的誤差

4、 觀察一個小測試集上的誤差 限制最大迭代次數(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， ， 說明 太小，加倍擴(kuò)展 平衡Winnow （Balanced Winnow） Thick Separator 界限（Ma

5、rgin） 放松非線性邊界 變換到線性上Map-Reduce的實現(xiàn) 每個機(jī)器處理部分x Map： 如果出錯，生成鍵值對（i, cyxi) 表示要對wi進(jìn)行調(diào)整 c為調(diào)整速度 Reduce 累積，實現(xiàn)對w的調(diào)整 重復(fù)，直到收斂，或到達(dá)停止的條件感知機(jī)總結(jié)感知機(jī) 加法更新w 適合x少，互相有相關(guān)性Winnonw 乘法更新w 適合x多，互相無相關(guān)性感知機(jī)總結(jié)是一種Online算法 新(x,y)到達(dá)，更新w局限 線性分割 線性不可分的話，不收斂 Feature多時，效果一般問題 過擬合 哪個最優(yōu)？問題一旦找到邊界，就停止，不是最優(yōu)SVM問題 尋找最佳的線性分割最大化MarginMargin 到分割平面

6、的距離，越寬越好 最優(yōu)分割平面SVM 改進(jìn)Perceptron的問題：最大化MarginMargin的數(shù)學(xué)描述A在B上的投影點(diǎn)積MarginAM在w上的投影M在在L上上最大化Margin即：即：SVM求最佳分割平面最佳分割平面由支持向量決定d維X，一般有d+1個支持向量其他點(diǎn)可以忽略歸一化最佳分割平面 w，b加倍，margin也加倍，不好找Max 加約束 |W| = 1 給b也加一個約束，支持向量xi在上面等于1/-1歸一化結(jié)果最小化最小化|W|優(yōu)化問題轉(zhuǎn)化優(yōu)化最小化最小化|W|SVM with “hard” 約束即：優(yōu)化 訓(xùn)練集最優(yōu)解:不能線性分割 引入懲罰：離邊界的距離 優(yōu)化問題轉(zhuǎn)化為懲罰

7、因子C C大：Care，懲罰大 C = 0: 無所謂 也叫懲罰函數(shù)Z離邊界的距離優(yōu)化 Matlab求解 Big Data時，求解困難 最小化 Convex函數(shù) Gradient Descent （梯度下降） 遞歸懲罰函數(shù)的導(dǎo)數(shù) 如果y = 1 如果y = -1 總結(jié)小結(jié)：梯度下降法 目標(biāo)：求w，最小化 梯度下降，調(diào)整w 梯度SVM例 C= 0.1， b作為一個W，參與優(yōu)化， 初始 W = 0,1, b = -2 b對應(yīng)的樣本值為1 訓(xùn)練集獲得懲罰函數(shù)導(dǎo)數(shù)表代入代入訓(xùn)練集訓(xùn)練集計算梯度 代入初始w=u,v,b = 0,1,-2，過一遍表，得到 第二行不滿足 獲得梯度更新w 重復(fù) 掃描懲罰函數(shù)表，

8、 計算梯度 調(diào)整權(quán)重 MapReduc Map管不同的懲罰函數(shù)行 Reduce加起來，獲得梯度問題調(diào)整一次W，對所有樣本都過一遍Stochastic Gradient Descent 翻過來:對每個樣本（共n個），把各維更新一遍性能評估 Leon Bottou 文本分類 Reuters RCV1文檔 Train set： n = 781,000 （文檔） Test set: 23,000 d = 50,000 features （單詞） 移走禁用詞 stop-words 移走低頻詞結(jié)果 速度大大提高準(zhǔn)確度 合理的質(zhì)量情況下，時間大大縮短擴(kuò)展Batch Conjugate Gradient 收斂

9、更快SGD 更簡單多次SGD，比一次BCG好。實際 需要選擇 和 Leon建議 選 ，使期望的初始更新和期望的權(quán)重可比 選 ： 挑少量樣本 嘗試10, 1, 0.1, 0.01, 選效果最好的實際 當(dāng)x稀疏時 近似為兩步 因為x稀疏，所以，第一步中更新的Wi少 兩種方案：1. W = SV，S為標(biāo)量，V為向量2. 第二步頻率低一些， 大一些停止 在測試集上檢驗 在訓(xùn)練集上檢驗多類 方法1：類似感知機(jī) 訓(xùn)練三個分類器 選多類 方法2：同時學(xué)習(xí)三類權(quán)重 優(yōu)化問題 類似地解最近鄰K-Nearest Neighbor (KNN) Instance based learning 保存整個訓(xùn)練集 (x,y

10、) 新查詢q 尋找最近的樣例 根據(jù)樣例，預(yù)測q的y 回歸/分類 例：Collaborative filtering 尋找K個最相似的用戶 根據(jù)他們的評分，預(yù)測用戶的評分四要素 距離Metric：最近 Euclidean K的選擇 加權(quán)函數(shù) 預(yù)測 平均K=1K=9Kernel回歸 K：所有已知樣本 加權(quán)函數(shù)K=9最近鄰尋找算法線性掃描基于樹的高維Index結(jié)構(gòu) Multidimensional index structures主存 Quadtree kd-tree第二存儲 R-trees高維的挑戰(zhàn)curse of dimensionality 維數(shù)詛咒兩種方法 VA Files 兩級 降維（SV

11、D） 到低維處理非歐式距離Manhattan distanceJaccard distance 用LSH 近似相似決策樹Decision Tree決策樹回歸分類構(gòu)造樹1) FindBestSplit 分類 最大化信息增益1）FindBestSplit 回歸 最大化 對數(shù)值：Sort，然后依次檢查 對類型：按子集2) StoppingCriteria 很多啟發(fā)式方法 方差足夠小 元素足夠少3) FindPrediction 回歸 返回葉子中元素均值 返回葉子中元素線性回歸 分類 返回葉子中元素類型MapReduce實現(xiàn) Parallel Learner for Assembling Numerous Ensemble Trees Panda et al., VLDB 09 一級一個Map-Reduce Mapper考慮大量可能的Split Reduce綜合，決定最優(yōu)Split裝袋 Bagging 采樣訓(xùn)練集 學(xué)習(xí)多個樹 組合其預(yù)測結(jié)果，得到更好的結(jié)果 很實用的方法SVM vs. DT 比較Refer B. Panda, J. S. Herbach, S. Basu, and R. J. Bayardo. PLANET: Massively parallel learning of tree ensembles with MapReduce. VLDB 2009. J.