歡迎光臨
每天分享高質量文章

機器學習演算法地圖

導讀:很多同學在學機器學習和深度學習的時候都有一個感受:所學的知識零散、不系統,缺乏整體感,這是普遍存在的一個問題。在這裡,SIGAI對常用的機器學習和深度學習演算法進行了總結,整理出它們之間的關係,以及每種演算法的核心點,各種演算法之間的比較。由此形成了一張演算法地圖,以幫助大家更好的理解和記憶這些演算法。

如果你對這張圖感興趣,可在公眾號後臺回覆演算法地圖,得到下載地址,用作電腦桌面是非常不錯的,絕對有逼格!

本文轉載自機器學習原創文章分享平臺SigAI(ID:SIGAICN

下麵先看這張圖:

▲圖片來自於SIGAICN

圖的左半部分列出了常用的機器學習演算法與它們之間的演化關係,分為有監督學習,無監督學習,強化學習3大類。右半部分列出了典型演算法的總結比較,包括演算法的核心點如型別,預測函式,求解的標的函式,求解演算法。

理解和記憶這張圖,對你系統化的掌握機器學習與深度學習會非常有幫助!

我們知道,整個機器學習演算法可以分為有監督學習,無監督學習,強化學習3大類。除此之外還有半監督學習,但我們可以把它歸到有監督學習中。演算法的演變與發展大多在各個類的內部進行,但也可能會出現大類間的交叉,如深度強化學習就是深度神經網絡與強化學習技術的結合。

根據樣本資料是否帶有標簽值(label),可以將機器學習演算法分成有監督學習和無監督學習兩類。如果要識別26個英文字母圖像,我們要將每張圖像和它是哪個字符即其所屬的型別對應起來,這個型別就是標簽值。

有監督學習(supervised learning)的樣本資料帶有標簽值,它從訓練樣本中學習得到一個模型,然後用這個模型對新的樣本進行預測推斷。它的樣本由輸入值x與標簽值y組成:

其中x為樣本的特征向量,是模型的輸入值;y為標簽值,是模型的輸出值。標簽值可以是整數也可以是實數,還可以是向量。有監督學習的標的是給定訓練樣本集,根據它確定映射函式:

確定這個函式的依據是函式能夠很好的解釋訓練樣本,讓函式輸出值f(x)與樣本真實標簽值y之間的誤差最小化,或者讓訓練樣本集的對數似然函式最大化。這裡的訓練樣本數是有限的,而樣本所有可能的取值集合在很多情況下是一個無限集,因此只能從中選取一部分樣本參與訓練。

日常生活中的很多機器學習應用,如垃圾郵件分類,手寫文字識別,人臉識別,語音識別等都是有監督學習。這類問題需要先收集訓練樣本,對樣本進行進行標註,用標註好的訓練樣本訓模型,然後根據模型對新的樣本進行預測。

無監督學習(unsupervised learning)對沒有標簽的樣本進行分析,發現樣本集的結構或者分佈規律。無監督學習的典型代表是聚類和資料降維。

強化學習是一類特殊的機器學習演算法,它根據輸入資料確定要執行的動作,在這裡。輸入資料是環境引數。和有監督學習演算法類似,這裡也有訓練過程中。在訓練時,對於正確的動作做出獎勵,對錯誤的動作做出懲罰,訓練完成之後就用得到的模型進行預測。

在有監督學習演算法中,我們列出了5個分支:

分別是決策樹,貝葉斯,線性模型,kNN,LDA(線性判別分析),集成學習。LDA也可以歸類到線性模型中,但因為它是一種有監督的投影技術,我們單獨列出。

決策樹是一種基於規則的方法,它的規則是通過訓練樣本學習得到的,典型的代表是ID3,C4.5,以及分類與回歸樹。

集成學習是機器學習中一類重要的演算法,它通過將多個簡單的模型進行集成,得到一個更強大的模型,簡單的模型稱為弱學習器。決策樹與集成學習演算法相結合,誕生了隨機森林,Boosting這兩類演算法(事實上,Boosting演算法的弱學習器不僅可以用決策樹,還可以用其他演算法)。

線性模型是最大的一個分支,從它最後衍生除了一些複雜的非線性模型。如果用於分類問題,最簡單的線性模型是線性回歸,加上L2和L1正則化項之後,分別得到嶺回歸和LASSO回歸。對於分類問題,最簡單的是感知器模型,從它衍生出了支持向量機,logistic回歸,神經網絡3大分支。而神經網絡又衍生出了各種不同的結構。包括自動編碼器,受限玻爾茲曼機,捲積神經網絡,迴圈神經網絡,生成對抗網絡等。當然,還有其他一些型別的神經網絡,因為使用很少,所以在這裡不列出。

kNN演算法基於模板匹配的思想,是最簡單的一種機器學習演算法,它依賴於距離定義,而距離同樣可以由機器學習而得到,這就是距離度量學習。

貝葉斯也是有監督學習演算法中的一個大分支,最簡單的是貝葉斯分類器,更複雜的有貝葉斯網絡。而貝葉斯分類器又有朴素貝葉斯和正態貝葉斯兩種實現。

接下來說無監督學習,它可以分為資料降維演算法和聚類演算法兩大類。演變關係如下圖所示:

無監督的降維演算法可以分為線性降維和非線性降維兩大類。前者的典型代表是主成分分析(PCA),通過使用核技術,可以把它擴展為非線性的版本。流形學習是非線性降維技術的典型實現,代表性的演算法有區域性線性嵌入(LLE),拉普拉斯特征映射,等距映射,區域性保持投影,它們都基於流形假設。流形假設不僅在降維演算法中有用,在半監督學習、聚類演算法中同樣有使用。

聚類演算法可以分為層次距離,基於質心的聚類,基於概率分佈的距離,基於密度的聚類,基於圖的聚類這幾種型別。它們從不同的角度定義簇(cluster)。基於質心的聚類典型代表是k均值演算法。基於概率分佈的聚類典型代表是EM演算法。基於密度的聚類典型代表是DBSCAN演算法,OPTICS演算法,Mean shift演算法。基於圖的聚類典型代表是譜聚類演算法。

強化學習是機器學習中的一個特殊分支,用於決策、控制問題。這類演算法的演變關係如下圖所示:

整個強化學習的理論模型可以抽象成馬爾可夫決策過程。核心任務是求解使得回報最大的策略。如果直接用動態規劃求解,則有策略迭代和價值迭代兩類演算法。他們都要求有精確的環境模型,即狀態轉移概率和獎勵函式。如果做不到這一點,只能採用隨機演算法,典型的代表是蒙特卡羅演算法和時序差分演算法。強化學習與深度學習相結合,誕生了深度強化學習演算法,典型代表是深度Q網絡(DQN)以及策略梯度演算法(策略梯度演算法不僅可用神經網絡作為策略函式的近似,還可以用其他函式)。

下麵我們來分別介紹每種演算法的核心知識點以及它們之間的關係。

01 有監督學習

先看有監督學習演算法,它是當前實際應用中使用最廣的機器學習演算法。進一步可以分為分類問題與回歸問題兩大類。前面說過,有監督學習演算法的預測函式為:

即根據輸入資料x預測出輸出資料y。如果y是整數的類別編號,則稱為分類問題;如果y是實數值,則為回歸問題。

1. 貝葉斯分類器

分類問題中樣本的特征向量取值x與樣本所屬型別y具有因果關係。因為樣本屬於型別y,所以具有特征值x。分類器要做的則相反,是在已知樣本的特征向量為x的條件下反推樣本所屬的類別y。根據貝葉斯公式有:

只要知道特征向量的概率分佈p(x),每一類出現的概率p(y),以及每一類樣本的條件概率p(x|y),就可以計算出樣本屬於每一類的概率p(y|x)。如果只要確定類別,比較樣本屬於每一類的概率的大小,找出該值最大的那一類即可。因此可以忽略p(x),因為它對所有類都是一樣的。簡化後分類器的判別函式為:

訓練時的標的是確定p(x|y)的引數,一般使用最大似然估計。如果假設樣本特征向量的各個分量之間相互獨立,則稱為朴素貝葉斯分類器。如果假設特征向量x服從多維正態分佈,則稱為正態貝葉斯分類器。正態貝葉斯分類器的預測函式為:

貝葉斯分類器是一種生成模型,是非線性模型,它天然的支持多分類問題。下圖是正態貝葉斯分類器對異或問題的分類結果(來自SIGAI雲端實驗室):

2. 決策樹家族

決策樹是基於規則的方法,它用一組嵌套的規則進行預測,在樹的每個決策節點處,根據判斷結果進入一個分支,反覆執行這種操作直到到達葉子節點,得到決策結果。決策樹的這些規則通過訓練得到,而不是人工制定的。下圖是決策樹的一個例子:

決策樹是一種判別模型,也是非線性模型,天然支持多類分類問題。它既可以用於分類問題,也可以用於回歸問題,具有很好的解釋性,符合人類的思維習慣。常用的決策樹有ID3,C4.5,分類與回歸樹(CART)等。

分類樹對應的映射函式是多維空間的分段線性劃分,即用平行於各個坐標軸的超平面對空間進行切分;回歸樹的映射函式是一個分段常數函式。決策樹是分段線性函式但不是線性函式,它具有非線性建模的能力。只要劃分的足夠細,分段常數函式可以逼近閉區間上任意函式到任意指定精度,因此決策樹在理論上可以對任意複雜度的資料進行分類或者回歸。

下圖是決策樹進行空間劃分的一個例子。在這裡有紅色和藍色兩類訓練樣本,用下麵兩條平行於坐標軸的直線可以將這兩類樣本分開(來自SIGAI雲端實驗室):

這個劃分方案對應的決策樹如下圖所示:

對於分類與回歸樹,訓練每個節點時的標的是要讓Gini不純度最小化,這等價於讓下麵的值最大化:

決策樹訓練求解時採用了列舉搜索和貪婪法的思想,找到的不一定是結構最優的樹。如果想要瞭解決策樹的原理,請閱讀SIGAI之前的公眾號文章“理解決策樹”。

3. kNN演算法

kNN演算法基於以下思想:要確定一個樣本的類別,可以計算它與所有訓練樣本的距離,然後找出和該樣本最接近的k個樣本,統計這些樣本的類別進行投票,票數最多的那個類就是分類結果。因為直接比較樣本和訓練樣本的距離,kNN演算法也被稱為基於實體的演算法,這實際上是一種模板匹配的思想。

下圖是使用k近鄰思想進行分類的一個例子:

在上圖中有紅色和綠色兩類樣本。對於待分類樣本即圖中的黑色點,我們尋找離該樣本最近的一部分訓練樣本,在圖中是以這個矩形樣本為圓心的某一圓範圍內的所有樣本。然後統計這些樣本所屬的類別,在這裡紅色點有12個,圓形有2個,因此把這個樣本判定為紅色這一類。上面的例子是二分類的情況,我們可以推廣到多類,k近鄰演算法天然支持多類分類問題,它是一種判別模型,也是非線性模型。下圖是kNN演算法對異或問題的分類結果(來自SIGAI雲端實驗室):

kNN演算法依賴於樣本距離值,常用的距離有歐氏距離,Mahalanobis距離等。這些距離定義中的引數可以通過學習得到,如Mahalanobis距離中的矩陣S,這稱為距離度量學習。

4. 線性模型家族

線性模型的預測函式是線性函式,既可以用於分類問題,也可以用於回歸問題,這是機器學習演算法中的一個龐大家族。從線性模型中衍生出了多種機器學習演算法,對於回歸問題問題,有嶺回歸,LASSO回歸;對於分類問題,有支持向量機,logistic回歸,softmax回歸,人工神經網絡(多層感知器模型),以及後續的各種深度神經網絡。

對於分類問題,線性模型的預測函式為:

其中sgn是符號函式。最簡單的線性分類器是感知器演算法,它甚至無法解決經典的異或問題,不具有太多的實用價值。

對於回歸問題,線性模型的預測函式為:

訓練時的標的是最小化均方誤差:

可以證明,這是一個凸優化問題,可以得到全域性極小值。求解時可以採用梯度下降法或者牛頓法。

嶺回歸是線性回歸的L2正則化版本,訓練時求解的問題為:

如果繫數,這個問題是一個嚴格凸優化問題,可用用梯度下降法,牛頓法求解。

LASSO回歸是線性回歸的L1正則化版本,訓練時求解的問題為:

同樣的,這是一個凸優化問題,可以用梯度下降法和牛頓法求解。

線性判別分析(LDA)是一種有監督的線性投影技術,它尋找向低維空間的投影矩陣W,樣本的特征向量x經過投影之後得到的新向量y:

投影的標的是同一類樣投影后的結果向量差異盡可能小,不同類的樣本差異盡可能大。直觀來看,就是經過這個投影之後同一類的樣本進來聚集在一起,不同類的樣本盡可能離得遠。下圖是這種投影的示意圖:

訓練時的求解標的是最大化類間差異與類內差異的比值:

最後歸結為求解矩陣的特征值和特征向量:

如果我們要將向量投影到c-1維,則挑選出最大的c-1個特征值以及它們對應的特征向量,組成矩陣W。線性判別分析不能直接用於分類問題,它只是完成投影,投影之後還需要用其他演算法進行分類,如kNN。下圖是LDA降維之後用最小距離分類器分類的結果:

從這張圖可以看出,決策面是直線。LDA是一種線性模型,也是判別模型,只能用於分類問題。

logistic回歸即對數幾率回歸,它的名字雖然叫“回歸”,但卻是一種用於二分類問題的分類演算法,它用sigmoid函式估計出樣本屬於某一類的概率。這種演算法可以看做是對線性分類器的改進。

預測函式為:

其中為線性映射權向量,由訓練演算法確定。訓練時的優化標的是最大化對數似然函式:

這是一個凸優化問題,可以得到全域性最優解,求解時可以採用梯度下降法或者牛頓法。分類時的判斷規則為:

logistic回歸是一種判別模型,也是線性模型,它只支持二分類問題。下圖是用logistic回歸進行分類的結果(來自SIGAI雲端實驗室):

從上圖可以看到,分界面是一條直線,這也說明瞭它是一個線性模型。

logistic回歸只能用於二分類問題,將它進行推廣可以得到處理多類分類問題的softmax回歸。softmax回歸按照下麵的公式估計一個樣本屬於每一類的概率:

模型的輸出為一個k維向量,其元素之和為1,每一個分量為樣本屬於該類的概率。訓練時的損失函式定義為:

上式是對logistic回歸損失函式的推廣。這個損失函式是凸函式,可以採用梯度下降法求解。Softmax回歸是一種判別模型,也是線性模型,它支持多分類問題。

5. 支持向量機

支持向量機是對線性分類器的改進,加上了最大化分類間隔的約束,另外還使用了核技術,通過非線性核解決非線性問題。一般情況下,給定一組訓練樣本可以得到不止一個可行的線性分類器,下圖就是一個例子:

在上圖中兩條直線都可以將兩類樣本分開。問題是:在多個可行的線性分類器中,什麼樣的分類器是好的?為了得到好的泛化性能,分類平面應該不偏向於任何一類,並且離兩個類的樣本都盡可能的遠。這種最大化分類間隔的標的就是支持向量機的基本思想。支持向量機在訓練時優化的標的是讓訓練樣本儘量分類正確,而且決策面離兩類樣本盡可能遠。原問題帶有太多的不等式約束,一般轉化為對偶問題求解,使用拉格朗日對偶,加上核函式之後,優化的對偶問題為:

預測函式為:

這是一個凸優化問題,可以得到全域性最優解,求解時一般採用SMO演算法,這是一種分治法,每次挑選出兩個變數進行優化,對這兩個變數的優化問題求公式解。優化變數的選擇使用了KKT條件。

支持向量機是一種判別模型,既支持分類問題,也支持回歸問題,如果使用非線性核,則是一種非線性模型,這從它的預測函式也可以看出來。標準的支持向量機只能解決二分類問題,通過多個二分類器組合,可以解決多分類問題,另外一種思路是直接構造多類的損失函式來解決多分類問題。下圖是用支持向量機對異或問題進行分類的結果(來自SIGAI雲端實驗室):

6. 神經網絡

人工神經網絡是一種仿生方法,受啟發於人腦的神經網絡。從數學上看,它本質上是一個多層複合函式。如果使用sigmoid作為激活函式,它的單個神經元就是logistic回歸。假設神經網絡的輸入是n維向量x,輸出是m維向量y,它實現瞭如向量到向量的映射:

將這個函式記為:

神經網絡第層的變換寫成矩陣和向量形式為:

如果採用歐氏距離,訓練時的優化標的為:

這不是一個凸優化問題,因此不能保證得到全域性極小值。可以採用梯度下降法求解,因為是一個複合函式,需要對各層的權重與偏置求導,採用了反向傳播演算法,它從多元函式求導的鏈式法則匯出。誤差項的計算公式為,對於輸出層:

對於隱含層:

根據誤差項可以得到權重和偏置的梯度值:

然後用梯度下降法更新。神經網絡是一個判別模型,並且是非線性模型,它既支持分類問題,也支持回歸問題,並且支持多分類問題。下圖是用神經網絡對異或問題的分類結果(來自SIGAI雲端實驗室):

7. 深度神經網絡家族

深度神經網絡是對多層感知器模型的進一步發展,它可以完成自動的特征提取,端到端的訓練,是深度學習的核心技術。可以分為自動編碼器,受限玻爾茲曼機,捲積神經網絡,迴圈神經網絡,生成對抗網絡這幾種型別。

自動編碼器用一個單層或者多層神經網絡對輸入資料進行映射,得到輸出向量,作為從輸入資料提取出的特征。在這種框架中,神經網絡的前半部分稱為編碼器,用於從原始輸入資料中提取特征;後半部分稱為解碼器,訓練時根據提取的特征重構原始資料,它只用於訓練階段。

訓練時的做法是先經過編碼器得到編碼後的向量,然後再通過解碼器得到解碼後的向量,用解碼後的向量和原始輸入向量計算誤差。如果編碼器的映射函式為h,解碼器的映射函式為g,訓練時優化的標的函式為:

在這裡同樣採用梯度下降法和反向傳播演算法。自動編碼器的改進型有去噪自動編碼器,收縮自動編碼器,變分自動編碼器,稀疏編碼等。

單個自動編碼器只能進行一層特征提取,可以將多個自動編碼器組合起來使用,得到一種稱為層疊編碼器的結構。層疊自動編編碼器由多個自動動編碼器串聯組成,能夠逐層提取輸入資料的特征,在此過程中逐層降低輸入資料的維度,將高維的輸入資料轉化成低維的特征。

受限玻爾茲曼機由Hinton等人提出,是一種生成式隨機神經網絡,這是一種概率模型。在這種模型中,神經元的狀態值是以隨機的方式確定的,而不像之前介紹的神經網絡那樣是確定性的。

受限玻爾茲曼機的資料分為可見變數和隱變數兩種型別,並定義了它們之間的概率關係。可見變數是神經網絡的輸入資料,如圖像;隱變數是從輸入資料中提取的特征。在受限玻爾茲曼機中,可見變數和隱藏變數都是二元變數,即其取值只能為0或1,整個神經網絡是一個二部圖。

可見節點用向量表示為v,隱藏節點用向量表示為h。任意可見節點和隱藏節點之間都有邊連接。(v, h)的聯合概率服從玻爾茲曼分佈,聯合概率定義為:

訓練時迭代更新權重引數直至網絡收斂,這種方法稱為Contrastive Divergence。

和自動編碼器類似,可以將多個受限玻爾茲曼機層疊加起來使用,在種結構稱為深度玻爾茲曼機(Deep Boltzmann Machine),簡稱DBM。通過多層的受限玻爾茲曼機,可以完成資料在不同層次上的特征提取和抽象。

在DBM中,所有層的節點之間的連接關係是無向的,如果我們限制某些層之間的連接關係為有向的,就得到了另外一種結構,稱為深信度網絡(Deep Belief Network),簡稱DBN。在DBN中,靠近輸入層的各個層之間的連接關係是有向的,是貝葉斯置信網;靠近輸出層的各個層之間的連接關係是無向的,是受限玻爾茲曼機。

在所有深度學習框架中,捲積神經網絡應用最為廣泛,在機器視覺等具有空間結構的資料問題上取得了成功。標準的捲積神經網絡由捲積層,池化層,全連接層構成。可以看做是權重共享的全連接神經網絡。

訓練時同樣採用梯度下降法和反向傳播演算法。對於捲積層,根據誤差項計算捲積核梯度的計算公式為:

捲層誤差項的遞推公式為:

也可以用矩陣乘法來實現捲積,這種做法更容易理解,可以方便的計算出對捲積核的梯度值。

迴圈神經網絡是僅次於捲積神經網絡的第二大深度神經網絡結構,在語音識別、自然語言處理等問題上取得了成功。迴圈神經網絡具有記憶功能,用於時間序列資料預測。迴圈層實現的映射為:

輸出層實現的映射為:

對單個樣本,訓練時的損失函式為各個時刻的損失函式之和:

這裡的反向傳播演算法稱為BPTT(Back Propagation Through Time),在時間軸上進行反向傳播。誤差項的遞推計算公式為:

根據誤差項計算權重和偏置的公式為:

生成對抗網絡(Generative Adversarial Network,簡稱GAN)是用機器學習的方法來解決資料生成問題的一種框架,它的標的是生成服從某種隨機分佈的資料,由Goodfellow在2014年提出。 這種模型能夠找出樣本資料內部的概率分佈規律,並根據這種規律產生出新的資料。

整個框架由一個生成模型和一個判別模型組成。生成模型用於學習真實資料的概率分佈,並生成符合這種分佈的資料;判別模型的任務是判斷一個輸入資料是來自於真實資料集還是由生成模型生成的。在訓練時,通過兩個模型之間不斷的競爭,從而分別提高這兩個模型的生成能力和判別能力。

生成模型的輸入是隨機噪聲z,輸出是產生的資料G(z)。判別模型的輸入是真實樣本,或者生成網絡生成的資料,得到的是它們的分類結果D(x)。

訓練的標的是讓判別模型能夠最大程度的正確區分真實樣本和生成模型生成的樣本;同時要讓生成模型使生成的樣本盡可能的和真實樣本相似。即:判別模型要盡可能將真實樣本判定為真實樣本,將生成模型產生的樣本判定為生成樣本;生成模型要儘量讓判別模型將自己生成的樣本判定為真實樣本。基於以上3個要求,對於生成模型生成的樣本,要最小化如下標的函式:

這意味著如果生成模型生成的樣本和真實樣本越接近,被判別模型判斷為真實樣本的概率就越大,即D(G(z))的值越接近於1,標的函式的值越小。另外還要考慮真實的樣本,對真實樣本要儘量將它判別成1。這樣要優化的標的函式定義為:

在這裡判別模型和生成模型是標的函式的自變數,它們的引數是要優化的變數。求解時採用了交替優化的策略,先固定住生成網絡,訓練判別網絡;然後固定住判別網絡,訓練生成網絡。每個網絡的訓練都採用梯度下降法和反向傳播演算法。

8. 集成學習家族

集成學習(ensemble learning)是一類機器學習演算法,它通過多個模型的組合形成一個精度更高的模型,參與組合的模型稱為弱學習器(weak learner)。在預測時使用這些弱學習器模型聯合進行預測;訓練時需要用訓練樣本集依次訓練出這些弱學習器。隨機森林和AdaBoost演算法是這類演算法的典型代表。

隨機森林由多棵決策樹組成。用多棵決策樹聯合預測可以提高模型的精度,這些決策樹用對訓練樣本集隨機抽樣構造出樣本集訓練得到。由於訓練樣本集由隨機抽樣構造,因此稱為隨機森林。隨機森林不僅對訓練樣本進行抽樣,還對特征向量的分量隨機抽樣,在訓練決策樹時,每次分裂時只使用一部分抽樣的特征分量作為候選特征進行分裂。下圖是隨機森林對異或問題的分類結果(來自SIGAI雲端實驗室):

對應的隨機森林如下圖所示:

隨機森林是一種判別模型,也是一種非線性模型,它既支持分類問題,也支持回歸問題,並且支持多分類問題,有很好的解釋性。

Boosting演算法也是一種集成學習演算法。它的分類器由多個弱分類器組成,預測時用每個弱分類器分別進行預測,然後投票得到結果;訓練時依次訓練每個弱分類器,在這裡和隨機森林採用了不同的策略,不是對樣本進行隨機抽樣構造訓練集,而是重點關註被前面的弱分類器錯分的樣本。弱分類器是很簡單的分類器,它計算量小且精度不用太高。

AdaBoost演算法由Freund等人提出,是Boosting演算法的一種實現版本。在最早的版本中,這種方法的弱分類器帶有權重,分類器的預測結果為弱分類器預測結果的加權和。訓練時訓練樣本具有權重,並且會在訓練過程中動態調整,被前面的弱分類器錯分的樣本會加大權重,因此演算法會關註難分的樣本。

強分類器的計算公式為:

分類時的判定規則為:

訓練標的是最小化指數損失函式:

求解時採用了分階段優化的策略,先把弱分類器的權重當做常數,優化弱分類器。得到弱分類器之後,再優化它的權重。弱分類器的權重計算公式為:

樣本權重的更新公式為:

AdaBoost演算法的原則是關註之前被錯分的樣本,準確率高的弱分類器有更大的權重。

AdaBoost演算法是一個判別模型,也是非線性模型,它只支持二分類問題。下圖是用AdaBoost演算法對異或問題的分類結果(來自SIGAI雲端實驗室):

02 無監督學習

相對於有監督學習,無監督學習的研究進展更為緩慢,演算法也相對較少。無監督學習可以分為聚類和降維兩大類,下麵分別介紹。

1. 聚類演算法

聚類屬於無監督學習問題,其標的是將樣本集劃分成多個類,保證同一類的樣本之間儘量相似,不同類的樣本之間儘量不同。這些類被稱為簇(cluster)。與有監督的分類演算法不同,聚類演算法沒有訓練過程,直接完成對一組樣本的劃分從而確定每個樣本的類別歸屬。我們一般將距離演算法分為層次距離,基於質心的聚類,基於密度的聚類,基於概率分佈的聚類,基於圖的聚類這幾種型別,它們從不同的角度定義簇。

k均值演算法是一種被廣為用於實際問題的聚類演算法。它將樣本劃分成k個類,引數k由人工設定。演算法將每個樣本分配到離它最近的那個類中心所屬的類,而類中心的確定又依賴於樣本的分配方案。假設樣本集有l個樣本,給定引數k的值,演算法將這些樣本劃分成k個集合:

最優分配方案是如下最優化問題的解:

其中為類中心向量。這個問題是NP難問題,不易求得全域性最優解,只能近似求解。實現時採用迭代法近似求解,只能保證收斂的區域性最優解處。每次迭代時,首先計算所有樣本離各個類中心的距離,然後將其分配到最近的那個類;接下來再根據這種分配方案更新類中心向量。下圖為k均值演算法的聚類結果(來自SIGAI雲端實驗室):

基於概率分佈的演算法假設每一個簇的樣本服從相同的概率分佈,這是一種生成模型。經常使用的是多維正態分佈,如果服從這種分佈,則為高斯混合模型,在求解時一般採用EM演算法。

EM演算法是一種迭代法,其標的是求解似然函式或後驗概率的極值,而樣本中具有無法觀測的隱含變數z。例如有一批樣本分屬於3個類,每個類的樣本都服從正態分佈,均值和協方差未知,並且每個樣本屬於哪個類也是未知的,需要在這種情況下估計出每個正態分佈的均值和協方差。演算法在實現時分為兩步:

E步,基於當前的引數估計值,計算在給定x時對z的條件概率的數學期望:

M步,求解如下極值問題,更新的值:

實現時可以按照下麵的公式計算:

迭代終止的判定規則是相鄰兩次函式值之差小於指定閾值。

DBSCAN演算法是一種基於密度的演算法,對噪聲魯棒。它將簇定義為樣本密集的區域,演算法從一個種子樣本開始,反覆向密集的區域生長,直至到達邊界。

演算法首先找出核心點,即周圍樣本非常密集的那些樣本點。然後從某一核心點出發,不斷向密度可達的區域擴張,得到一個包含核心點和邊界點的最大區域,這個區域中任意兩點密度相連。下圖是DBSCAN演算法的聚類結果(來自SIGAI雲端實驗室):

OPTICS演算法是對DBSCAN演算法的改進,對引數更不敏感。它不直接生成簇,而是對本進行排序,這種排序包含了聚類信息。

均值漂移(Mean Shift)算基於核密度估計技術,是一種尋找概率密度函式極值點的演算法。在用於聚類任務時,它尋找概率密度函式的極大值點,即樣本分別最密集的位置,以此得到簇。

基於圖的演算法把樣本資料看成圖的頂點,通過資料點之間的距離構造邊,形成帶權圖。通過圖的切割實現聚類,即將圖切分成多個子圖,這些子圖就是對應的簇。基於圖的聚類演算法典型的代表是譜聚類演算法。譜聚類演算法首先構造資料的鄰接圖,得到圖的拉普拉斯矩陣。接下來對矩陣進行特征值分解,通過特征值和特征向量構造出簇。

2. 資料降維

在有些應用中,向量的維數非常高。以圖像資料為例,對於高度和寬度分別為100像素的圖像,如果將所有像素值拼接起來形成一個向量,這個向量的維數是10000。另外向量的各個分量之間可能存在相關性。直接將向量送入機器學習演算法中處理效率會很低,也影響演算法的精度。為了可視化顯示資料,我們也需要把向量變換到低維空間中。

主成分分析(principal component analysis,簡稱PCA)是一種資料降維和去除相關性的方法,它通過線性變換將向量投影到低維空間。對向量進行投影就是讓向量左乘一個矩陣得到結果向量,這也是線性代數中講述的線性變換:

降維要確保的是在低維空間中的投影能很好的近似表達原始向量,即重構誤差最小化。下圖是主分量投影示意圖:

▲主分量投影示意圖

在上圖中樣本用紅色的點表示,傾斜的直線是它們的主要變化方向。將資料投影到這條直線上即完成資料的降維,把資料從2維降為1維。

尋找投影矩陣時要優化的標的是使得重構誤差最小化:

使得該函式取最小值的為散度矩陣最大的個特征值對應的單位長度特征向量。即求解下麵的優化問題:

矩陣W的列是我們要求解的基向量。散度矩陣是實對稱矩陣,因此屬於不同特征值的特征向量是正交的。下圖是主成分分析對手寫數字圖像的降維結果(來自SIGAI雲端實驗室):

雖然都是線性投影演算法,但主成分分析和線性判別分析有本質的不同,前者是無監督的,後者是有監督的,計算過程中使用了類別標簽信息。

主成分分析是一種線性降維技術,對於高度非線性的資料具有局限性,而在實際應用中很多時候資料是非線性的。此時可以採用非線性降維技術,流形學習(manifold learning)是非線性降維技術的典型代表。

流形是微分幾何中的一個概念,它是高維空間中的幾何結構,即空間中的點構成的集合,可以簡單的理解成二維空間的曲線,三維空間的曲面在更高維空間的推廣。下圖是三維空間中的一個流形,這是一個卷曲的曲面:

假設有一個N維空間中的流形M,即:

流形學習降維要實現的是如下映射:

其中n<

區域性線性嵌入(簡稱LLE)將高維資料投影到低維空間中,並保持資料點之間的區域性線性關係。其核心思想是每個點都可以由與它相近的多個點的線性組合來近似,投影到低維空間之後要保持這種線性重構關係,並且有相同的重構繫數。

每個資料點和它的鄰居位於或者接近於流形的一個區域性線性片段上,即可以用它鄰居點的線性組合來重構,組合繫數刻畫了這些區域性面片的幾何特性:

權重繫數通最小化下麵的重構誤差確定:

假設非線性映射將向量從D維空間的x映射為d維空間的y。每個點在d維空間中的坐標由下麵的最優化問題確定:

這裡的權重和上一個優化問題的值相同,在前面已經得到。下圖為用LLE演算法將手寫數字圖像投影到3維空間後的結果(來自SIGAI雲端實驗室):

等距映射(Isomap)使用了微分幾何中測地線的思想,它希望資料在向低維空間映射之後能夠保持流形上的測地線距離。

測地線源自於大地測量學,是指地球上任意兩點之間在球面上的最短路徑。在三維空間中兩點之間的最短距離是它們之間線段的長度,但如果要沿著地球錶面走,最短距離就是測地線的長度,因為我們不可能從地球內部穿過去。演算法計算任意兩個樣本之間的測地距離,然後根據這個距離構造距離矩陣。最後通過距離矩陣求解優化問題完成資料的降維,降維之後的資料保留了原始資料點之間的距離信息。

降維過求解如下最優化問題實現:

這個標的函式的意義是向量降維之後任意兩點之間的距離要儘量的接近在原始空間中這兩點之間的最短路徑長度,因此可以認為降維儘量保留了資料點之間的測地距離信息。下圖是等距映射對手寫數字圖像降維後的結果(來自SIGAI雲端實驗室):

3. 強化學習

強化學習是一類特殊的機器學習演算法,如果說有監督學習和無監督學習是要根據預測函式來確定輸出標簽信息或者聚類類別、降維後的向量,則強化學習演算法是要根據當前的狀態確定要執行的動作。

強化學習與有監督學習和無監督學習的標的不同,它借鑒於行為主義心理學。演算法要解決的問題是智慧體在環境中怎樣執行動作以獲得最大的累計獎勵。對於自動行駛的汽車,強化學習演算法控制汽車的動作,保證安全行駛。智慧體指強化學習演算法,環境是類似車輛當前狀態與路況這樣的由若干引數構成的系統,獎勵是我們期望得到的結果,如汽車正確的在路面上行駛而不發生事故。

很多控制、決策問題都可以抽象成這種模型。和有監督學習不同,這裡沒有標簽值作為監督信號,系統只會給演算法執行的動作一個評分反饋,這種反饋一般還具有延遲性,當前的動作所產生的後果在未來才會完全得到,另外未來還具有隨機性。

強化學習要解決的問題可以抽象成馬爾可夫決策過程(Markov Decision Process,簡稱MDP)。馬爾可夫過程的特點是系統下一個時刻的狀態由當前時刻的狀態決定,與更早的時刻無關。與馬爾可夫過程不同的是,在MDP中系智慧體可以執行動作,從而改變自己和環境的狀態,並且得到懲罰或獎勵。

馬爾可夫決策過程可以表示成一個五元組:

其中S和A分別為狀態和動作的集合。假設t時刻狀態為st,智慧體執行動作a,下一時刻進入狀態st+1。下一時刻的狀態由當前狀態以及當前採取的動作決定,是一個隨機性變數,這一狀態轉移的概率為:

這是當前狀態為s時行動作a,下一時刻進入狀態的條件概率。這個公式表明下一時刻的狀態與更早時刻的狀態和動作無關,狀態轉換具有馬爾可夫性。有一種特殊的狀態叫做終止狀態(也稱為吸收狀態),到達該狀態之後不會再進入其他後續狀態。對於圍棋,終止狀態是一局的結束。

執行動作之後,智慧體會收到一個立即回報:

立即回報和當前狀態、當前採取的動作以及下一時刻進入的狀態有關。在每個時刻t,智慧體選擇一個動作at執行,之後進入下一狀態st+1,環境給出回報值。智慧體從某一初始狀態開始,每個時刻選擇一個動作執行,然後進入下一個狀態,得到一個回報,如此反覆:

問題的核心是執行動作的策略,它可以抽象成一個函式,定義了在每種狀態時要選擇執行的動作。這個函式在狀態s所選擇的動作為:

這是確定性策略。對於確定性策略,在每種狀態下智慧體要執行的動作是唯一的。另外還有隨機性策略,智慧體在一種狀態下可以執行的動作有多種,策略函式給出的是執行每種動作的概率:

即按概率從各種動作中選擇一種執行。策略只與當前所處的狀態有關,於歷史時間無關,在不同時刻對於同一個狀態所執行的策略是相同的。

強化學習的標的是要達到我們的某種預期,當前執行動作的結果會影響系統後續的狀態,因此需要確定動作在未來是否能夠得到好的回報,這種回報具有延遲性。對於圍棋,當前走的一步棋一般不會馬上結束,但會影響後續的棋局,需要使得未來贏的概率最大化,而未來又具有隨機性,這為確定一個正確的決策帶來了困難。

選擇策略的標的是按照這個策略執行後,在各個時刻的累計回報值最大化,即未來的預期回報。按照某一策略執行的累計回報定義為:

這裡假設狀態轉移概率以及每個時刻的回報是已知的,演算法要尋找最佳策略來最大化上面的累計回報。

如果每次執行一個動作進入的下一個狀態是確定的,則可以直接用上面的累計回報計算公式。如果執行完動作後進入的下一個狀態是隨機的,則需要計算各種情況的數學期望。為此定義狀態價值函式的概念,它是在某個狀態s下,按照策略執行動作,累計回報的數學期望。狀態價值函式的計算公式為:

動作價值函式是智慧體按照策略執行,在狀態s時執行具體的動作a後的預期回報,計算公式為:

除了指定初始狀態與策略之外,還指定了在狀態s時執行的動作a。這個函式衡量的是給定某一策略,在某一狀態時執行各種動作的價值。

給定一個策略,可以用動態規劃演算法計算它的狀態價值函式,即策略評估(Policy Evaluation)。在每種狀態下執行的動作有多種可能,需要對各個動作計算數學期望。按照定義,狀態價值函式的計算公式為:

求解時使用迭代法,首先為所有狀態的價值函式設置初始值,然後用公式更新所有狀態的價值函式,第k次迭代時的更新公式為:

演算法最後會收斂到真實的價值函式值。

策略評估的目的是為了得到更好的策略,即策略改進。策略改進通過按照某種規則對當前策略進行調整,得到更好的策略。

策略迭代是策略評估和策略改進的結合。從一個初始策略開始,不斷的改進這個策略達到最優解。每次迭代時首先用策略估計一個策略的狀態價值函式,然後根據策略改進方案調整該策略,再計算新策略的狀態價值函式,如此反覆直到收斂。這一過程如下圖所示:

在策略迭代演算法中,策略評估的計算量很大,需要多次掃描所有狀態並不斷的更新狀態價值函式。實際上不需要知道狀態價值函式的精確值也能迭代到最優策略,值迭代就是其中的一種方法。

根據貝爾曼最優化原理,如果一個策略是最優策略,整體最優的解區域性一定也最優,因此最優策略可以被分解成兩部分:從狀態s到採用了最優動作,在狀態是採用的策略也是最優的。根據這一原理,每次選擇當前回報和未來回報之和最大的動作,價值迭代的更新公式為:

策略迭代演算法和價值迭代演算法雖然都可以得到理論上的最優解,但是它們的計算過程依賴於狀態轉移概率以及回報函式。對於很多應用場景,我們無法得到準確的狀態模型和回報函式。因此前面介紹的這兩種演算法在實際問題中使用價值有限。

對於無法建立精確的環境模型的問題,我們只能根據一些狀態、動作、回報值序列樣本進行計算,估計出價值函式和最優策略。基本思想是按照某種策略嘗試執行不同的動作,觀察得到的回報,然後進行改進。

蒙特卡洛演算法和時序差分演算法是解決這這類問題的兩種方法。蒙特卡洛演算法是一種隨機數值演算法,它通過使用隨機數來近似解決某些難以直接求解的問題。在強化學習中,蒙特卡洛演算法可以根據樣本得到狀態價值函式以及動作價值函式的估計值,用於近似數學期望值。

在上面的例子中,樣本是一些隨機的點,在用於計算強化學習的價值函式時,樣本是一些片段。在這裡先定義片段(episode)的概念,它是從某一狀態開始,執行一些動作,直到終止狀態為止的一個完整的狀態和動作序列,這類似於迴圈神經網絡中的時間序列樣本。蒙特卡洛演算法從這些片段樣本中學習,估算出狀態價值函式和動作價值函式。實現時的做法非常簡單:

按照一個策略執行,得到一個狀態和回報序列,即片段。多次執行,得到多個片段。接下來根據這些片段樣本估計出價值函式。

蒙特卡洛演算法需要使用完整的片段進行計算,這在有些問題中是不現實的,尤其是對於沒有終止狀態的問題。時序差分演算法(Temporal Difference learning,簡稱TD學習)在執行一個動作之後就進行價值函式估計,無需使用包括終止狀態的完整片段,它結合了蒙特卡洛演算法與動態規劃演算法的思想。與蒙特卡洛演算法一樣,TD演算法無需依賴狀態轉移概率,直接採樣計算。TD演算法用貝爾曼方程估計價值函式的值,然後構造更新項。迭代更新公式為:

演算法用當前動作的立即回報值與下一狀態當前的狀態價值函式估計值之和構造更新項,更新本狀態的價值函式:

在上式中沒有使用狀態轉移概率,而是和蒙特卡洛演算法一樣隨機產生一些樣本來進行計算,因此稱為無模型的演算法。用於估計狀態價值函式時,演算法的輸入為策略,輸出為該策略的狀態值函式。

Sarsa演算法用於估計給定策略下的動作價值函式,同樣是每次執行一個動作之後就進行更新。它的迭代更新公式為:

由於更新值的構造使用了這5個變數,因此被命名為Sarsa演算法。根據所有狀態-動作對的價值函式可以得到最優策略。

Q學習演算法估計每個動作價值函式的最大值,通過迭代可以直接找到價值函式的極值,從而確定最優策略,類似於價值迭代演算法的思想。

實現時需要根據當前的動作價值函式的估計值為每個狀態選擇一個動作來執行,這裡有兩種方案。第一種方案是隨機選擇一個動作,這稱為探索(exploration)。第二種方案是根據當前的動作函式值選擇一個價值最大的動作執行:

這稱為利用(exploitation)。第三種方案是二前兩者的結合,即貪心策略。執行完動作之後,進入狀態,然後尋找狀態下所有動作的價值函式的極大值,構造更新項。演算法最終會收斂到動作價值函式的最優值。用於預測時,在每個狀態下選擇函式值最大的動作執行,這就是最優策略,具體實現時同樣可以採用貪心策略。

前面介紹的演算法只能用於狀態和動作的集合是有限的離散基且狀態和動作數量較少的情況,狀態和動作需要人工預先設計。實際應用中的場景可能會很複雜,很難定義出離散的狀態;即使能夠定義,數量也非常大,無法用陣列儲存。用一個函式來逼近價值函式或策略函式成為解決這個問題的一種思路,函式的輸入是原始的狀態資料,函式的輸出是價值函式值或策略函式值。

在有監督學習中,我們用神經網絡來實現分類或回歸函式,同樣的,也可以用神經網絡可來擬合強化學習中的價值函式和策略函式,這就是深度強化學習的基本思想。在這裡,神經網絡被用於從原始資料如圖像中直接預測出函式值。

在Q學習中用表格儲存動作價值函式的值,如果狀態和動作太多這個表將非常大,在某些應用中也無法列舉出所有的狀態形成有限的狀態集合。解決這個問題的方法是用一個函式來近似價值函式,深度Q學習用神經網絡來近似動作價值函式。網絡的輸入是狀態,輸出是各種動作的價值函式值。下麵用一個例子進行說明。演算法要實現自動駕駛,將當前場景的圖像作為狀態,神經網絡的輸入是這種圖像,輸出是每個動作對應的Q函式值,這裡的動作是左轉,右轉,剎車,加油門等。顯然,神經網絡輸出層的尺寸與動作數相等。

DeepMind提出了一種用深度Q解決Atari游戲的方法,使用捲積神經網絡擬合Q函式,稱為深度Q網絡(簡稱DQN)。網絡的輸入為經過處理後游戲圖像畫面,原始的畫面是210×160的彩色圖像,每個像素的值為[0, 255]之間的整數,所有可能的狀態數為:

這個規模的矩陣無法直接用表格儲存。網絡的輸出值是在輸入狀態下執行每個動作的Q函式值,在這裡有18個值,代表游戲中的18種動作。神經網絡用於近似最優Q函式:

其中是網絡的引數。網絡結構如下圖所示:

關鍵問題是訓練樣本標簽值的與損失函式的設計。這裡的標的是逼近最優策略的Q函式值,因此可以採用Q學習的做法。損失函式用神經網絡的輸出值與Q學習每次迭代時的更新值構造,定義為:

在這裡採用了歐氏距離損失,是神經網絡的輸出值與Q函式估計值之間的誤差,與Q學習中的更新項相同。另一個問題是如何得到訓練樣本,和Q學習類似,可以通過執行動作來生成樣本。實現時,用當前的神經網絡進行預測,得到所有動作的價值函式,然後按照策略選擇一個動作執行,得到下一個狀態以及回報值,以此作為訓練樣本。

這裡還使用了經驗回放(Experience Replay)技術。神經網絡要求訓練樣本之間獨立同分佈,而Atari游戲的訓練樣本是一個時間序列,前後具有相關性。解決這個問題的做法是經驗池,將樣本儲存在一個集合中,然後從中隨機採樣得到每次迭代所用的訓練樣本。

深度Q學習基於動作價值函式,它用神經網絡擬合Q函式的最優值,通過函式值間接得到最優策略。如果動作集合是連續的或維數很高,這種方法將面臨問題。例如演算法要控制機器人在和方向上移動,每個方向上的移動距離是[-1.-, +1.0]之間的實數,移動距離無法窮舉出來離散化成動作集合,因此無法使用基於價值函式的方法。此時可以讓神經網絡根據輸入的狀態直接輸出和方向的移動距離,從而解決連續性動作問題。

策略梯度(Policy Gradient)演算法是這種思想的典型代表,策略函式網絡的輸入是圖像之類的原始資料。策略函式根據這個輸入狀態直接預測出要執行的動作:

其中是神經網絡的引數。對於隨機性策略,神經網絡的輸出是執行每種動作的概率值:

這是一種更為端到端的方法,神經網絡的映射定義了在給定狀態的條件下執行每種動作的概率,根據這些概率值進行採樣可以得到要執行的動作。對於離散的動作,神經網絡的輸出層神經元數量等於動作數,輸出值為執行每個動作的概率。對於連續型動作,神經網絡的輸出值為高斯分佈的均值和方差,動作服從此分佈。

這裡的關鍵問題是構造訓練樣本和優化標的函式,在這兩個問題解決之後剩下的就是標準的神經網絡訓練過程。在樣本生成問題上,策略梯度演算法採用的做法和DQN類似,用神經網絡當前的引數對輸入狀態進行預測,根據網絡的輸出結果確定出要執行的動作,接下來執行這個動作,得到訓練樣本,並根據反饋結果調整網絡的引數。如果最後導致負面的回報,則更新網絡的引數使得在面臨這種輸入時執行此動作的概率降低;否則加大這個動作的執行概率。策略梯度演算法在優化標的上和深度Q學習不同,深度Q學習是逼近最優策略的Q函式,而策略梯度演算法是通過最大化回報而逼近最優策略。

公眾號後臺對話框回覆演算法地圖可獲取完整版下載鏈接。

更多精彩


在公眾號後臺對話框輸入以下關鍵詞

查看更多優質內容!


PPT | 報告 | 讀書 | 書單 | 乾貨

Python | 機器學習 | 深度學習 | 神經網絡

區塊鏈 | 揭秘 | 高考 | 福利

猜你想看

Q: 這些演算法你掌握了多少

歡迎留言與大家分享

覺得不錯,請把這篇文章分享給你的朋友

轉載 / 投稿請聯繫:[email protected]

更多精彩,請在後臺點擊“歷史文章”查看

赞(0)

分享創造快樂