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

下面先看這張圖：

（關注公眾號SIGAICN，回復“算法地圖”，即可獲得高清原圖鏈接）

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

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

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

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

有監督學習（supervised learning）的樣本數據帶有標簽值，它從訓練樣本中學習得到一個模型，然后用這個模型對新的樣本進行預測推斷。它的樣本由輸入值x與標簽值y組成：

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

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

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

無監督學習（unsupervised learning）對沒有標簽的樣本進行分析，發現樣本集的結構或者分布規律。無監督學習的典型代表是聚類和數據降維。

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

在有監督學習算法中，我們列出了5個分支：

（關注公眾號SIGAICN，回復“算法地圖”，即可獲得高清原圖鏈接）

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

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

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

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

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

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

接下來說無監督學習，它可以分為數據降維算法和聚類算法兩大類。演變關系如下圖所示：

（關注公眾號SIGAICN，回復“算法地圖”，即可獲得高清原圖鏈接）

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

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

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

（關注公眾號SIGAICN，回復“算法地圖”，即可獲得高清原圖鏈接）

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

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

有監督學習

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

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

貝葉斯分類器

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

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

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

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

決策樹家族

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

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

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

下圖是決策樹進行空間劃分的一個例子。在這里有紅色和藍色兩類訓練樣本，用下面兩條平行于坐標軸的直線可以將這兩類樣本分開（來自SIGAI云端實驗室）：

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

對于分類與回歸樹，訓練每個節點時的目標是要讓Gini不純度最小化，這等價于讓下面的值最大化：

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

kNN算法

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

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

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

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

線性模型家族

線性模型的預測函數是線性函數，既可以用于分類問題，也可以用于回歸問題，這是機器學習算法中的一個龐大家族。從線性模型中衍生出了多種機器學習算法，對于回歸問題問題，有嶺回歸，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回歸是一種判別模型，也是線性模型，它支持多分類問題。

支持向量機

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

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

預測函數為：

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

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

神經網絡

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

將這個函數記為：

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

如果采用歐氏距離，訓練時的優化目標為：

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

對于隱含層：

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

然后用梯度下降法更新。神經網絡是一個判別模型，并且是非線性模型，它既支持分類問題，也支持回歸問題，并且支持多分類問題。下圖是用神經網絡對異或問題的分類結果（來自SIGAI云端實驗室）：

深度神經網絡家族

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

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

訓練時的做法是先經過編碼器得到編碼后的向量，然后再通過解碼器得到解碼后的向量，用解碼后的向量和原始輸入向量計算誤差。如果編碼器的映射函數為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。這樣要優化的目標函數定義為：

在這里判別模型和生成模型是目標函數的自變量，它們的參數是要優化的變量。求解時采用了交替優化的策略，先固定住生成網絡，訓練判別網絡；然后固定住判別網絡，訓練生成網絡。每個網絡的訓練都采用梯度下降法和反向傳播算法。

集成學習家族

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

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

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

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

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

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

強分類器的計算公式為：

分類時的判定規則為：

訓練目標是最小化指數損失函數：

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

樣本權重的更新公式為：

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

AdaBoost算法是一個判別模型，也是非線性模型，它只支持二分類問題。下圖是用AdaBoost算法對異或問題的分類結果（來自SIGAI云端實驗室）：

無監督學習

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

聚類算法家族

聚類屬于無監督學習問題，其目標是將樣本集劃分成多個類，保證同一類的樣本之間盡量相似，不同類的樣本之間盡量不同。這些類被稱為簇（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）算基于核密度估計技術，是一種尋找概率密度函數極值點的算法。在用于聚類任務時，它尋找概率密度函數的極大值點，即樣本分別最密集的位置，以此得到簇。

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

數據降維

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

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

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

圖7.1 主分量投影示意圖

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

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

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

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

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

主成分分析是一種線性降維技術，對于高度非線性的數據具有局限性，而在實際應用中很多時候數據是非線性的。此時可以采用非線性降維技術，流形學習（manifold learning）是非線性降維技術的典型代表。

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

假設有一個N維空間中的流形M，即：

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

其中n<

局部線性嵌入（簡稱LLE）將高維數據投影到低維空間中，并保持數據點之間的局部線性關系。其核心思想是每個點都可以由與它相近的多個點的線性組合來近似，投影到低維空間之后要保持這種線性重構關系，并且有相同的重構系數。

每個數據點和它的鄰居位于或者接近于流形的一個局部線性片段上，即可以用它鄰居點的線性組合來重構，組合系數刻畫了這些局部面片的幾何特性：

權重系數通最小化下面的重構誤差確定：

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

這里的權重和上一個優化問題的值相同，在前面已經得到。下圖為用LLE算法將手寫數字圖像投影到3維空間后的結果（來自SIGAI云端實驗室）：

等距映射（Isomap）使用了微分幾何中測地線的思想，它希望數據在向低維空間映射之后能夠保持流形上的測地線距離。

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

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

這個目標函數的意義是向量降維之后任意兩點之間的距離要盡量的接近在原始空間中這兩點之間的最短路徑長度，因此可以認為降維盡量保留了數據點之間的測地距離信息。下圖是等距映射對手寫數字圖像降維后的結果（來自SIGAI云端實驗室）：

強化學習

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

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

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

強化學習要解決的問題可以抽象成馬爾可夫決策過程（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）。網絡的輸入為經過處理后游戲圖像畫面，原始的畫面是210x160的彩色圖像，每個像素的值為[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函數，而策略梯度算法是通過最大化回報而逼近最優策略。