1.列舉常用的最優化方法

梯度下降法

牛頓法，

擬牛頓法

坐標下降法

梯度下降法的改進型如AdaDelta，AdaGrad，Adam，NAG等。

2.梯度下降法的關鍵點

梯度下降法沿著梯度的反方向進行搜索，利用了函數的一階導數信息。梯度下降法的迭代公式為： ? 根據函數的一階泰勒展開，在負梯度方向，函數值是下降的。只要學習率設置的足夠小，并且沒有到達梯度為0的點處，每次迭代時函數值一定會下降。需要設置學習率為一個非常小的正數的原因是要保證迭代之后的xk+1位于迭代之前的值xk的鄰域內，從而可以忽略泰勒展開中的高次項，保證迭代時函數值下降。 ? 梯度下降法只能保證找到梯度為0的點，不能保證找到極小值點。迭代終止的判定依據是梯度值充分接近于0，或者達到最大指定迭代次數。 ? 梯度下降法在機器學習中應用廣泛，尤其是在深度學習中。AdaDelta，AdaGrad，Adam，NAG等改進的梯度下降法都是用梯度構造更新項，區別在于更新項的構造方式不同。對梯度下降法更全面的介紹可以閱讀SIGAI之前的公眾號文章“理解梯度下降法”。 ?

3.牛頓法的關鍵點

牛頓法利用了函數的一階和二階導數信息，直接尋找梯度為0的點。牛頓法的迭代公式為： ? 其中H為Hessian矩陣，g為梯度向量。牛頓法不能保證每次迭代時函數值下降，也不能保證收斂到極小值點。在實現時，也需要設置學習率，原因和梯度下降法相同，是為了能夠忽略泰勒展開中的高階項。學習率的設置通常采用直線搜索（line search）技術。 ? 在實現時，一般不直接求Hessian矩陣的逆矩陣，而是求解下面的線性方程組： ? ? 其解d稱為牛頓方向。迭代終止的判定依據是梯度值充分接近于0，或者達到最大指定迭代次數。 ? 牛頓法比梯度下降法有更快的收斂速度，但每次迭代時需要計算Hessian矩陣，并求解一個線性方程組，運算量大。另外，如果Hessian矩陣不可逆，則這種方法失效。 ?

4.拉格朗日乘數法

拉格朗日乘數法是一個理論結果，用于求解帶有等式約束的函數極值。對于如下問題： 構造拉格朗日乘子函數： ? ? 在最優點處對x和乘子變量的導數都必須為0： ? ? 解這個方程即可得到最優解。對拉格朗日乘數法更詳細的講解可以閱讀任何一本高等數學教材。機器學習中用到拉格朗日乘數法的地方有： ?

主成分分析

線性判別分析

流形學習中的拉普拉斯特征映射

隱馬爾科夫模型

5.凸優化

數值優化算法面臨兩個方面的問題：局部極值，鞍點。前者是梯度為0的點，也是極值點，但不是全局極小值；后者連局部極值都不是，在鞍點處Hessian矩陣不定，即既非正定，也非負定。 凸優化通過對目標函數，優化變量的可行域進行限定，可以保證不會遇到上面兩個問題。凸優化是一類特殊的優化問題，它要求：

優化變量的可行域是一個凸集

目標函數是一個凸函數

凸優化最好的一個性質是：所有局部最優解一定是全局最優解。機器學習中典型的凸優化問題有：

線性回歸

嶺回歸

LASSO回歸

Logistic回歸

支持向量機

Softamx回歸

6.拉格朗日對偶

對偶是最優化方法里的一種方法，它將一個最優化問題轉換成另外一個問題，二者是等價的。拉格朗日對偶是其中的典型例子。對于如下帶等式約束和不等式約束的優化問題： ? 與拉格朗日乘數法類似，構造廣義拉格朗日函數： ? ? 必須滿足的約束。原問題為： ? ? 即先固定住x，調整拉格朗日乘子變量，讓函數L取極大值；然后控制變量x，讓目標函數取極小值。原問題與我們要優化的原始問題是等價的。 ? 對偶問題為： ? ? 和原問題相反，這里是先控制變量x，讓函數L取極小值；然后控制拉格朗日乘子變量，讓函數取極大值。 ? 一般情況下，原問題的最優解大于等于對偶問題的最優解，這稱為弱對偶。在某些情況下，原問題的最優解和對偶問題的最優解相等，這稱為強對偶。 ? 強對偶成立的一種條件是Slater條件：一個凸優化問題如果存在一個候選x使得所有不等式約束都是嚴格滿足的，即對于所有的i都有gi?(x)<0，不等式不取等號，則強對偶成立，原問題與對偶問題等價。注意，Slater條件是強對偶成立的充分條件而非必要條件。 ? 拉格朗日對偶在機器學習中的典型應用是支持向量機。 ?

7.KKT條件

KKT條件是拉格朗日乘數法的推廣，用于求解既帶有等式約束，又帶有不等式約束的函數極值。對于如下優化問題： ? 和拉格朗日對偶的做法類似，KKT條件構如下乘子函數： ? ? 和稱為KKT乘子。在最優解處應該滿足如下條件： 等式約束 和不等式約束 是本身應該滿足的約束，和之前的拉格朗日乘數法一樣。唯一多了關于gi?(x)的條件： KKT條件只是取得極值的必要條件而不是充分條件。 ? ?

8.特征值與特征向量

對于一個n階矩陣A，如果存在一個數和一個非0向量X，滿足： ? ? 則稱為矩陣A的特征值，X為該特征值對應的特征向量。根據上面的定義有下面線性方程組 成立： ? ? 上式左邊的多項式稱為矩陣的特征多項式。矩陣的跡定義為主對角線元素之和： ? 根據韋達定理，矩陣所有特征值的和為矩陣的跡： ? ? 同樣可以證明，矩陣所有特征值的積為矩陣的行列式： ? ? 利用特征值和特征向量，可以將矩陣對角化，即用正交變換將矩陣化為對角陣。實對稱矩陣一定可以對角化，半正定矩陣的特征值都大于等于0，在機器學習中，很多矩陣都滿足這些條件。特征值和特征向量在機器學習中的應用包括：正態貝葉斯分類器、主成分分析，流形學習，線性判別分析，譜聚類等。 ?

9.奇異值分解

矩陣對角化只適用于方陣，如果不是方陣也可以進行類似的分解，這就是奇異值分解，簡稱SVD。假設A是一個m x n的矩陣，則存在如下分解： ? 其中U為m x m的正交矩陣，其列稱為矩陣A的左奇異向量；為m x n的對角矩陣，除了主對角線以外，其他元素都是0；V為n x n的正交矩陣，其行稱為矩陣A的右奇異向量。U的列為AAT的特征向量，V的列為AT?A的特征向量。 ?

10.最大似然估計

有些應用中已知樣本服從的概率分布，但是要估計分布函數的參數，確定這些參數常用的一種方法是最大似然估計。 ? 最大似然估計構造一個似然函數，通過讓似然函數最大化，求解出。最大似然估計的直觀解釋是，尋求一組參數，使得給定的樣本集出現的概率最大。 ? 假設樣本服從的概率密度函數為，其中X為隨機變量，為要估計的參數。給定一組樣本xi,i?=1,...,l，它們都服從這種分布，并且相互獨立。最大似然估計構造如下似然函數： ? ? 其中xi是已知量，這是一個關于的函數，我們要讓該函數的值最大化，這樣做的依據是這組樣本發生了，因此應該最大化它們發生的概率，即似然函數。這就是求解如下最優化問題： ? ? 乘積求導不易處理，因此我們對該函數取對數，得到對數似然函數： ? 最后要求解的問題為： ? 最大似然估計在機器學習中的典型應用包括logistic回歸，貝葉斯分類器，隱馬爾科夫模型等。 ?

基本概念

1.有監督學習與無監督學習

根據樣本數據是否帶有標簽值，可以將機器學習算法分成有監督學習和無監督學習兩類。有監督學習的樣本數據帶有標簽值，它從訓練樣本中學習得到一個模型，然后用這個模型對新的樣本進行預測推斷。有監督學習的典型代表是分類問題和回歸問題。 無監督學習對沒有標簽的樣本進行分析，發現樣本集的結構或者分布規律。無監督學習的典型代表是聚類，表示學習，和數據降維，它們處理的樣本都不帶有標簽值。

2.分類問題與回歸問題

在有監督學習中，如果樣本的標簽是整數，則預測函數是一個向量到整數的映射，這稱為分類問題。如果標簽值是連續實數，則稱為回歸問題，此時預測函數是向量到實數的映射。

3.生成模型與判別模型

分類算法可以分成判別模型和生成模型。給定特征向量x與標簽值y，生成模型對聯合概率p(x,y)建模，判別模型對條件概率p(y|x)進行建模。另外，不使用概率模型的分類器也被歸類為判別模型，它直接得到預測函數而不關心樣本的概率分布： 判別模型直接得到預測函數f(x)，或者直接計算概率值p(y|x)，比如SVM和logistic回歸，softmax回歸，判別模型只關心決策面，而不管樣本的概率分布的密度。 ? 生成模型計算p(x, y)或者p(x|y) ，通俗來說，生成模型假設每個類的樣本服從某種概率分布，對這個概率分布進行建模。 ? 機器學習中常見的生成模型有貝葉斯分類器，高斯混合模型，隱馬爾可夫模型，受限玻爾茲曼機，生成對抗網絡等。典型的判別模型有決策樹，kNN算法，人工神經網絡，支持向量機，logistic回歸，AdaBoost算法等。 ?

4.交叉驗證

交叉驗證（cross validation）是一種統計準確率的技術。k折交叉驗證將樣本隨機、均勻的分成k份，輪流用其中的k-1份訓練模型，1份用于測試模型的準確率，用k個準確率的均值作為最終的準確率。

5.過擬合與欠擬合

欠擬合也稱為欠學習，直觀表現是訓練得到的模型在訓練集上表現差，沒有學到數據的規律。引起欠擬合的原因有模型本身過于簡單，例如數據本身是非線性的但使用了線性模型；特征數太少無法正確的建立映射關系。 過擬合也稱為過學習，直觀表現是在訓練集上表現好，但在測試集上表現不好，推廣泛化性能差。過擬合產生的根本原因是訓練數據包含抽樣誤差，在訓練時模型將抽樣誤差也進行了擬合。所謂抽樣誤差，是指抽樣得到的樣本集和整體數據集之間的偏差。引起過擬合的可能原因有： 模型本身過于復雜，擬合了訓練樣本集中的噪聲。此時需要選用更簡單的模型，或者對模型進行裁剪。訓練樣本太少或者缺乏代表性。此時需要增加樣本數，或者增加樣本的多樣性。訓練樣本噪聲的干擾，導致模型擬合了這些噪聲，這時需要剔除噪聲數據或者改用對噪聲不敏感的模型。

6.偏差與方差分解

模型的泛化誤差可以分解成偏差和方差。偏差是模型本身導致的誤差，即錯誤的模型假設所導致的誤差，它是模型的預測值的數學期望和真實值之間的差距。 方差是由于對訓練樣本集的小波動敏感而導致的誤差。它可以理解為模型預測值的變化范圍，即模型預測值的波動程度。 模型的總體誤差可以分解為偏差的平方與方差之和： 如果模型過于簡單，一般會有大的偏差和小的方差；反之如果模型復雜則會有大的方差但偏差很小。 ?

7.正則化

為了防止過擬合，可以為損失函數加上一個懲罰項，對復雜的模型進行懲罰，強制讓模型的參數值盡可能小以使得模型更簡單，加入懲罰項之后損失函數為： 正則化被廣泛應用于各種機器學習算法，如嶺回歸，LASSO回歸，logistic回歸，神經網絡等。除了直接加上正則化項之外，還有其他強制讓模型變簡單的方法，如決策樹的剪枝算法，神經網絡訓練中的dropout技術，提前終止技術等。 ?

8.維數災難

為了提高算法的精度，會使用越來越多的特征。當特征向量維數不高時，增加特征確實可以帶來精度上的提升；但是當特征向量的維數增加到一定值之后，繼續增加特征反而會導致精度的下降，這一問題稱為維數災難。

貝葉斯分類器

貝葉斯分類器將樣本判定為后驗概率最大的類，它直接用貝葉斯公式解決分類問題。假設樣本的特征向量為x，類別標簽為y，根據貝葉斯公式，樣本屬于每個類的條件概率（后驗概率）為： ? 分母p(x)對所有類都是相同的，分類的規則是將樣本歸到后驗概率最大的那個類，不需要計算準確的概率值，只需要知道屬于哪個類的概率最大即可，這樣可以忽略掉分母。分類器的判別函數為： ? 在實現貝葉斯分類器時，需要知道每個類的條件概率分布p(x|y)即先驗概率。一般假設樣本服從正態分布。訓練時確定先驗概率分布的參數，一般用最大似然估計，即最大化對數似然函數。 ? 如果假設特征向量的各個分量之間相互獨立，則稱為樸素貝葉斯分類器，此時的分類判別函數為： ? 實現時可以分為特征分量是離散變量和連續變量兩種情況。貝葉斯分分類器是一種生成模型，可以處理多分類問題，是一種非線性模型。 ?

決策樹

決策樹是一種基于規則的方法，它用一組嵌套的規則進行預測。在樹的每個決策節點處，根據判斷結果進入一個分支，反復執行這種操作直到到達葉子節點，得到預測結果。這些規則通過訓練得到，而不是人工制定的。 決策樹既可以用于分類問題，也可以用于回歸問題。分類樹的映射函數是多維空間的分段線性劃分，用平行于各坐標軸的超平面對空間進行切分；回歸樹的映射函數是分段常數函數。決策樹是分段線性函數而不是線性函數。只要劃分的足夠細，分段常數函數可以逼近閉區間上任意函數到任意指定精度，因此決策樹在理論上可以對任意復雜度的數據進行擬合。對于分類問題，如果決策樹深度夠大，它可以將訓練樣本集的所有樣本正確分類。 決策樹的訓練算法是一個遞歸的過程，首先創建根節點，然后遞歸的建立左子樹和右子樹。如果練樣本集為D，訓練算法的流程為：

1.用樣本集D建立根節點，找到一個判定規則，將樣本集分裂成D1和D2兩部分，同時為根節點設置判定規則。

2.用樣本集D1遞歸建立左子樹。

3.用樣本集D2遞歸建立右子樹。

4.如果不能再進行分裂，則把節點標記為葉子節點，同時為它賦值。

對于分類樹，如果采用Gini系數作為度量準則，決策樹在訓練時尋找最佳分裂的依據為讓Gini不純度最小化，這等價于讓下面的值最大化： 尋找最佳分裂時需要計算用每個閾值對樣本集進行分裂后的純度值，尋找該值最大時對應的分裂，它就是最佳分裂。如果是數值型特征，對于每個特征將l個訓練樣本按照該特征的值從小到大排序，假設排序后的值為： 接下來從x1開始，依次用每個xi作為閾值，將樣本分成左右兩部分，計算上面的純度值，該值最大的那個分裂閾值就是此特征的最佳分裂閾值。在計算出每個特征的最佳分裂閾值和上面的純度值后，比較所有這些分裂的純度值大小，該值最大的分裂為所有特征的最佳分裂。 ? 決策樹可以處理屬性缺失問題，采用的方法是使用替代分裂規則。為了防止過擬合，可以對樹進行剪枝，讓模型變得更簡單。如果想要更詳細的了解決策樹的原理，請閱讀SIGAI之前的公眾號文章“理解決策樹”，在SIGAI云端實驗室有決策樹訓練算法的原理實驗，此功能免費，網址為： www.sigai.cn ? 決策樹是一種判別模型，既支持分類問題，也支持回歸問題，是一種非線性模型，它支持多分類問題。 ?

隨機森林

隨機森林是一種集成學習算法，是Bagging算法的具體實現。集成學習是機器學習中的一種思想，而不是某一具體算法，它通過多個模型的組合形成一個精度更高的模型，參與組合的模型稱為弱學習器。在預測時使用這些弱學習器模型聯合進行預測，訓練時需要依次訓練出這些弱學習器。 隨機森林用有放回抽樣（Bootstrap抽樣）構成出的樣本集訓練多棵決策樹，訓練決策樹的每個節點時只使用了隨機抽樣的部分特征。預測時，對于分類問題，一個測試樣本會送到每一棵決策樹中進行預測，然后投票，得票最多的類為最終分類結果。對于回歸問題，隨機森林的預測輸出是所有決策樹輸出的均值。 假設有n個訓練樣本。訓練每一棵樹時，從樣本集中有放回的抽取n個樣本，每個樣本可能會被抽中多次，也可能一次都沒抽中。如果樣本量很大，在整個抽樣過程中每個樣本有0.368的概率不被抽中。由于樣本集中各個樣本是相互獨立的，在整個抽樣中所有樣本大約有36.8%沒有被抽中。這部分樣本稱為包外（Out Of Bag，簡稱OOB）數據。 用這個抽樣的樣本集訓練一棵決策樹，訓練時，每次尋找最佳分裂時，還要對特征向量的分量采樣，即只考慮部分特征分量。由于使用了隨機抽樣，隨機森林泛化性能一般比較好，可以有效的降低模型的方差。 如果想更詳細的了解隨機森林的原理，請閱讀SIGAI之前的公眾號文章“隨機森林概述”。隨機森林是一種判別模型，既支持分類問題，也支持回歸問題，并且支持多分類問題，這是一種非線性模型。

AdaBoost算法

AdaBoost算法也是一種集成學習算法，用于二分類問題，是Boosting算法的一種實現。它用多個弱分類器的線性組合來預測，訓練時重點關注錯分的樣本，準確率高的弱分類器權重大。AdaBoost算法的全稱是自適應，它用弱分類器的線性組合來構造強分類器。弱分類器的性能不用太好，僅比隨機猜測強，依靠它們可以構造出一個非常準確的強分類器。強分類器的計算公式為： 其中x是輸入向量，F(x)是強分類器，ft(x)是弱分類器，at是弱分類器的權重，T為弱分類器的數量，弱分類器的輸出值為+1或-1，分別對應正樣本和負樣本。分類時的判定規則為： 強分類器的輸出值也為+1或-1，同樣對應于正樣本和負樣本。 ? 訓練時，依次訓練每一個若分類器，并得到它們的權重值。訓練樣本帶有權重值，初始時所有樣本的權重相等，在訓練過程中，被前面的弱分類器錯分的樣本會加大權重，反之會減小權重，這樣接下來的弱分類器會更加關注這些難分的樣本。弱分類器的權重值根據它的準確率構造，精度越高的弱分類器權重越大。 ? 給定l個訓練樣本(xi,yi?)，其中xi是特征向量，yi為類別標簽，其值為+1或-1。訓練算法的流程為： 根據計算公式，錯誤率低的弱分類器權重大，它是準確率的增函數。AdaBoost算法在訓練樣本集上的錯誤率會隨著弱分類器數量的增加而指數級降低。它能有效的降低模型的偏差。 ? AdaBoost算法從廣義加法模型導出，訓練時求解的是指數損失函數的極小值： 求解時采用了分階段優化，先得到弱分類器，然后確定弱分類器的權重值，這就是弱分類器，弱分類器權重的來歷。除了離散型AdaBoost之外，從廣義加法模型還可以導出其他幾種AdaBoost算法，分別是實數型AdaBoost，Gentle型AdaBoost，Logit型AdaBoost，它們使用了不同的損失函數和最優化算法。 ? 標準的AdaBoost算法是一種判別模型，只能支持二分類問題。它的改進型可以處理多分類問題。 ?

主成分分析

主成分分析是一種數據降維和去除相關性的方法，它通過線性變換將向量投影到低維空間。對向量進行投影就是對向量左乘一個矩陣，得到結果向量： y = Wx 結果向量的維數小于原始向量的維數。降維要確保的是在低維空間中的投影能很好的近似表達原始向量，即重構誤差最小化： 其中e為投影后空間的基向量，是標準正交基；a為重構系數，也是投影到低維空間后的坐標。如果定義如下的散布矩陣： 其中m和為所有樣本的均值向量。則上面的重構誤差最小化等價于求解如下問題： 通過拉格朗日乘數法可以證明，使得該函數取最小值的ej為散度矩陣最大的d'個特征值對應的單位長度特征向量。矩陣W的列ej是我們要求解的基向量，由它們構成投影矩陣。計算時，先計算散布矩陣（或者協方差矩陣），再對該進行進行特征值分解，找到最大的一部分特征值和對應的特征向量，構成投影矩陣?？梢宰C明，協方差矩陣或散布矩陣是實對稱半正定矩陣，因此所有特征值非負。進行降維時，先將輸入向量減掉均值向量，然后左乘投影矩陣，即可得到投影后的向量。 ? 主成分分析一種無監督學習算法，也是一種線性方法。 ?

線性判別分析

線性判別分析向最大化類間差異、最小化類內差異的方向線性投影。其基本思想是通過線性投影來最小化同類樣本間的差異，最大化不同類樣本間的差異。具體做法是尋找一個向低維空間的投影矩陣W，樣本的特征向量x經過投影之后得到的新向量： y = Wx 同一類樣投影后的結果向量差異盡可能小，不同類的樣本差異盡可能大。簡單的說，就是經過這個投影之后同一類的樣本進來聚集在一起，不同類的樣本盡可能離得遠。這種最大化類間差異，最小化類內差異的做法，在機器學習的很多地方都有使用。 類內散布矩陣定義為： 它衡量的內類樣本的發散程度。其中mi為每個類的均值向量，m為所有樣本的均值向量。類間散布矩陣定義為： 它衡量的了各類樣本之間的差異。訓練時的優化目標是類間差異與類內差異的比值： 上面的問題帶有冗余，如果w是最優解，將其乘以一個不為0的系數之后還是最優解。為了消掉冗余，加上如下約束： 然后使用拉格朗日乘數法，最后歸結于求解矩陣的特征值與特征向量： LDA是有監督的學習算法，在計算過程中利用了樣本標簽值，是線性模型。LDA也不能直接用于分類和回歸問題，要對降維后的向量進行分類還需要借助其他算法。 ?

kNN算法

kNN算法將樣本分到離它最相似的樣本所屬的類。算法本質上使用了模板匹配的思想。要確定一個樣本的類別，可以計算它與所有訓練樣本的距離，然后找出和該樣本最接近的k個樣本，統計這些樣本的類別進行投票，票數最多的那個類就是分類結果。 由于需要計算樣本間的距離，因此需要依賴距離定義，常用的有歐氏距離，Mahalanobis距離，Bhattacharyya距離。另外，還可以通過學習得到距離函數，這就是距離度量學習。 kNN算法是一種判別模型，即支持分類問題，也支持回歸問題，是一種非線性模型。它天然的支持多分類問題。kNN算法沒有訓練過程，是一種基于實例的算法。

人工神經網絡

人工神經網絡是一種仿生的方法，參考了動物的神經元結構。從本質上看，它是一個多層復合函數。對于多層前饋型神經網絡，即權連接網絡，每一層實現的變換為： 其中W為權重矩陣，b為偏置向量，f為激活函數。正向傳播時反復用上上對每一層的輸出值進行計算，得到最終的輸出。使用激活函數是為了保證非線性，對于激活函數更深入全面的介紹請參考SIGAI之前的公眾號文章“理解神經網絡的激活函數”，“神經網絡的激活函數總結”。萬能逼近定理保證了神經網絡可以比較閉區間上任意一個連續函數。 ? 權重和偏置通過訓練得到，采用的是反向傳播算法。反向傳播算法從復合函數求導的鏈式法則導出，用于計算損失函數對權重，偏置的梯度值。算法從最外層的導數值算起，依次遞推的計算更內層的導數值，這對應于從神經網絡的輸出層算起，反向計算每個隱含層參數的導數值。其核心是誤差項的定義，定義誤差項為損失函數對臨時變量u的梯度： 其中，nl是神經網絡的層數。最后一個層的誤差項可以直接求出，其他層的誤差項根據上面的遞推公式進行計算。根據誤差項，可以計算出損失函數對每一層權重矩陣的梯度值： 以及對偏置向量的梯度值： 然后用梯度下降法對它們的值進行更新。參數初始化一般采用隨機數，而不是簡單的初始化為0。為了加快收斂速度，還可以使用動量項，它積累了之前的梯度信息。 ? 神經網絡訓練時的損失函數不是凸函數，因此有陷入局部極值，鞍點的風險。另外，隨著層數的增加，會導致梯度消失問題，這是因為每次計算誤差項時都需要乘以激活函數的導數值，如果其絕對值小于1，多次連乘之后導致誤差項趨向于0，從而使得計算出來的參數梯度值接近于0，參數無法有效的更新。 ? 如果對反傳播算法的推導細節感興趣，可以閱讀SIGAI之前的公眾號文章“反向傳播算法推導-全連接神經網絡”。神經網絡的訓練算法可以總結為： 復合函數求導?+?梯度下降法 ? 標準的神經網絡是一種有監督的學習算法，它是一種非線性模型，它既可以用于分類問題，也可以用于回歸問題，并且支持多分類問題。 ?

支持向量機

支持向量機的核心思想是最大化分類間隔。簡單的支持向量機就是讓分類間隔最大化的線性分類器，找到多維空間中的一個超平面。它在訓練是求解的問題為： 這從點到超平面的距離方程導出，通過增加一個約束條件消掉了優化變量的冗余。可以證明，這個問題是凸優化問題，并且滿足Slater條件。這個問題帶有太多的不等式約束，不易求解，因此通過拉格朗日對偶轉換為對偶問題求解： 同樣的，這個問題也是凸優化問題。此時支持向量機并不能解決非線性分類問題，通過使用核函數，將向量變換到高維空間，使它們更可能是線性可分的。而對向量先進行映射再做內積，等價于先做內積再做映射，因此核函數并不用顯式的對向量進行映射，而是對兩個向量的內積進行映射，這是核函數的精髓。要理解核函數，可以閱讀SIGAI之前的公眾號文章“【實驗】理解SVM的核函數和參數”。 ? 加入核函數K之后的對偶問題變為： 預測函數為： 其中b通過KKT條件求出。如果使用正定核，這個問題也是凸優化問題。求解采用了SMO算法，這是一種分治法，每次挑選出兩個變量進行優化，其他變量保持不動。選擇優化變量的依據是KKT條件，對這兩個變量的優化是一個帶等式和不等式約束的二次函數極值問題，可以直接得到公式解。另外，這個子問題同樣是一個凸優化問題。 ? 標準的支持向量機只能解決二分類問題。對于多分類問題，可以用這種二分類器的組合來解決，有以下幾種方案： ? 1對剩余方案。對于有k個類的分類問題，訓練k個二分類器。訓練時第i個分類器的正樣本是第i類樣本，負樣本是除第i類之外其他類型的樣本，這個分類器的作用是判斷樣本是否屬于第i類。在進行分類時，對于待預測樣本，用每個分類器計算輸出值，取輸出值最大那個作為預測結果。 ? 1對1方案。如果有k個類，訓練Ck2個二分類器，即這些類兩兩組合。訓練時將第i類作為正樣本，其他各個類依次作為負樣本，總共有k?(k???1)?/ 2種組合。每個分類器的作用是判斷樣本是屬于第i類還是第j類。對樣本進行分類時采用投票的方法，依次用每個二分類器進行預測，如果判定為第m類，則m類的投票數加1，得票最多的那個類作為最終的判定結果。 ? 除了通過二分類器的組合來構造多類分類器之外，還可以通過直接優化多類分類的目標函數得到多分類器。 ? SVM是一種判別模型。它既可以用于分類問題，也可以用于回歸問題。標準的SVM只能支持二分類問題，使用多個分類器的組合，可以解決多分類問題。如果不使用核函數，SVM是一個線性模型，如果使用非線性核，則是非線性模型，這可以從上面的預測函數看出。如果想更詳細的了解支持向量機，可以閱讀SIGAI之前的公眾號文章“用一張圖理解SVM的脈絡”。 ?

logistic回歸

logistic回歸是一種二分類算法，直接為樣本估計出它屬于正負樣本的概率。先將向量進行線性加權，然后計算logistic函數，可以得到[0,1]之間的概率值，它表示樣本x屬于正樣本的概率： 正樣本標簽值為1，負樣本為0。使用logistic函數的原因是它單調增，并且值域在(0, 1)之間，剛好符合概率的要求。訓練時采用最大似然估計，求解對數似然函數的極值： 可以證明這是一個凸優化問題，求解時可以用梯度下降法，也可以用牛頓法。如果正負樣本的標簽為+1和-1，則可以采用另外一種寫法： 訓練時的目標同樣是最大化對數似然函數： 同樣的，這也是一個凸優化問題。預測時并不需要計算logistic函數，而是直接計算： Logistic回歸是一種二分類算法，雖然使用了概率，但它是一種判別模型！另外要注意的是，logistic回歸是一種線性模型，這從它的預測函數就可以看出。它本身不能支持多分類問題，它的擴展版本softmax回歸可以解決多分類問題。 ?

K均值算法

K均值算法是一種聚類算法，把樣本分配到離它最近的類中心所屬的類，類中心由屬于這個類的所有樣本確定。 k均值算法是一種無監督的聚類算法。算法將每個樣本分配到離它最近的那個類中心所代表的類，而類中心的確定又依賴于樣本的分配方案。 在實現時，先隨機初始化每個類的類中心，然后計算樣本與每個類的中心的距離，將其分配到最近的那個類，然后根據這種分配方案重新計算每個類的中心。這也是一種分階段優化的策略。 與k近鄰算法一樣，這里也依賴于樣本之間的距離，因此需要定義距離的計算方式，最常用的是歐氏距離，也可以采用其他距離定義。算法在實現時要考慮下面幾個問題： 1.類中心向量的初始化。一般采用隨機初始化。最簡單的是Forgy算法，它從樣本集中隨機選擇k個樣本作為初始類中心。第二種方案是隨機劃分，它將所有樣本隨機的分配給k個類中的一個，然后按照這種分配方案計算各個類的類中心向量。 2.參數k的設定?？梢愿鶕闰炛R人工指定一個值，或者由算法自己確定。 3.迭代終止的判定規則。一般做法是計算本次迭代后的類中心和上一次迭代時的類中心之間的距離，如果小于指定閾值，則算法終止。

卷積神經網絡

卷積神經網絡是對全連接神經網絡的發展，它使用卷積層，池化層自動學習各個尺度上的特征。卷積運算為： 在這里需要注意多通道卷積的實現，它的輸入圖像，卷積核都有多個通道，分別用各個通道的卷積核對輸入圖像的各個通道進行卷積，然后再累加。這里也使用了激活函數，原因和全連接神經網絡相同。池化運算最常見的有均值池化，max池化，分別用均值和最大值代替圖像的一塊矩形區域。使用池化的原因是為了降維，減小圖像的尺寸，另外，它還帶來了一定程度的平移和旋轉的不變性。Max池化是非線性操作，現在用的更多。 ? 對于經典的網絡結構，包括LeNet-5網絡，AlexNet，VGG網絡，GoogLeNet，殘差網絡等經典的網絡結構，創新點，要熟記于心。 ? 自Alex網絡出現之后，各種改進的卷積網絡不斷被提出。這些改進主要在以下幾個方面進行：卷積層，池化層，激活函數，損失函數，網絡結構。對于這些典型的改進，也要深刻理解。 ? 由于引入了卷積層和池化層，因此反向傳播算法需要為這兩種層進行考慮。卷積層誤差項的反向傳播的公式為 根據誤差項計算卷積核梯度值的公式為： 如果采用均值池化，池化層的誤差項反向傳播計算公式為： 如果使用max池化，則為： 注意，池化層沒有需要訓練得到的參數。如果對卷積神經網絡反向傳播算法的推導感興趣，可以閱讀SIGAI之前的公眾號文章“反向傳播算法推導-卷積神經網絡”。 ? 卷積神經網絡具有遷移學習的能力，我們可以把這個網絡的參數作為訓練的初始值，在新的任務上繼續訓練，這種做法稱為fine-tune，即網絡微調。大量的實驗結果和應用結果證明，這種微調是有效的。這說明卷積神經網絡在一定程度上具有遷移學習的能力，卷積層學習到的特征具有通用性。VGG網絡在ImageNet數據集上的訓練結果在進行微調之后，被廣泛應用于目標檢測、圖像分割等任務。 ? 和全連接神經網絡一樣，卷積神經網絡是一個判別模型，它既可以用于分類問題，也可以用用于回歸問題，并且支持多分類問題。 ?

循環神經網絡

循環神經網絡是一種具有記憶功能的神經網絡，每次計算時，利用了上一個時刻的記憶值，特別適合序列數據分析。網絡接受的是一個序列數據，即一組向量，依次把它們輸入網絡，計算每個時刻的輸出值。記憶功能通過循環神層實現： 它同時利用了本時刻的輸入值和上一個時刻的記憶值。輸出層的變換為： 這和普通神經網絡沒什么區別。由于引入了循環層，因此反向傳播算法有所不同，稱為BPTT，即時間軸上的反向傳播算法。算法從最后一個時刻算起，沿著時間軸往前推。誤差項的遞推公式為： 遞推的終點為最后一個時刻。 根據誤差項計算對權重和偏置的梯度值的公式為： 循環神經網絡同樣存在梯度消失問題，因此出現了LSTM，GRU等結構。 ? 以循環神經網絡為基礎，構造出了兩類通用的框架，分別是連接主義時序分類（CTC），以及序列到序列學習（seq2seq）。用于解決語音識別，自然語言處理中的問題。其中，seq2seq采用了編碼器-解碼器結構，用兩個循環神經網絡組合起來完成計算，一個充當編碼器，一個充當解碼器。 ? 和其他類型的神經網絡一樣，循環神經網絡是一個判別模型，既支持分類問題，也支持回歸問題，并且支持多分類問題。 ?

高斯混合模型

高斯混合模型通過多個正態分布的加權和來描述一個隨機變量的概率分布，概率密度函數定義為： 其中x為隨機向量，k為高斯分布的個數，wi為權重，為高斯分布的均值向量，為協方差矩陣。所有權重之和為1，即： 任意一個樣本可以看作是先從k個高斯分布中選擇出一個，選擇第i個高斯分布的概率為wi，再由第i個高斯分布產生出這個樣本數據x。高斯混合模型可以逼近任何一個連續的概率分布，因此它可以看做是連續性概率分布的萬能逼近器。之所有要保證權重的和為1，是因為概率密度函數必須滿足在內的積分值為1。 ? 指定高斯分布的個數，給定一組訓練樣本，可以通過期望最大化EM算法確定高斯混合模型的參數。每次迭代時，在E步計算期望值，在M步最大化期望值，如此循環交替。 ?

EM算法

EM算法是一種迭代法，其目標是求解似然函數或后驗概率的極值，而樣本中具有無法觀測的隱含變量。因為隱變量的存在，我們無法直接通過最大化似然函數來確定參數的值。可以采用一種策略，構造出對數似然函數的一個下界函數，這個函數不含有隱變量，然后優化這個下界。不斷的提高這個下界，使原問題達到最優解，這就是EM算法所采用的思路。算法的構造依賴于Jensen不等式。 算法在實現時首先隨機初始化參數的值，接下來循環迭代，每次迭代時分為兩步： ? E步，基于當前的參數估計值，計算在給定x時對z的條件概率的數學期望： M步，求解如下極值問題，更新的值： 實現Qi?時可以按照下面的公式計算： 迭代終止的判定規則是相鄰兩次函數值之差小于指定閾值。需要注意的是，EM算法只能保證收斂到局部極小值。