作者 | 小小挖掘機

來源 | SIGAI

主成分分析

主成分分析是一種數據降維和去除相關性的方法，它通過線性變換將向量投影到低維空間。對向量進行投影就是對向量左乘一個矩陣，得到結果向量：

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為激活函數。正向傳播時反復用上上對每一層的輸出值進行計算，得到最終的輸出。使用激活函數是為了保證非線性，萬能逼近定理保證了神經網絡可以比較閉區間上任意一個連續函數。

權重和偏置通過訓練得到，采用的是反向傳播算法。反向傳播算法從復合函數求導的鏈式法則導出，用于計算損失函數對權重，偏置的梯度值。算法從最外層的導數值算起，依次遞推的計算更內層的導數值，這對應于從神經網絡的輸出層算起，反向計算每個隱含層參數的導數值。其核心是誤差項的定義，定義誤差項為損失函數對臨時變量u的梯度：

其中，nl是神經網絡的層數。最后一個層的誤差項可以直接求出，其他層的誤差項根據上面的遞推公式進行計算。根據誤差項，可以計算出損失函數對每一層權重矩陣的梯度值：

以及對偏置向量的梯度值：

然后用梯度下降法對它們的值進行更新。參數初始化一般采用隨機數，而不是簡單的初始化為0。為了加快收斂速度，還可以使用動量項，它積累了之前的梯度信息。

神經網絡訓練時的損失函數不是凸函數，因此有陷入局部極值，鞍點的風險。另外，隨著層數的增加，會導致梯度消失問題，這是因為每次計算誤差項時都需要乘以激活函數的導數值，如果其絕對值小于1，多次連乘之后導致誤差項趨向于0，從而使得計算出來的參數梯度值接近于0，參數無法有效的更新。

復合函數求導 + 梯度下降法

標準的神經網絡是一種有監督的學習算法，它是一種非線性模型，它既可以用于分類問題，也可以用于回歸問題，并且支持多分類問題。

支持向量機

支持向量機的核心思想是最大化分類間隔。簡單的支持向量機就是讓分類間隔最大化的線性分類器，找到多維空間中的一個超平面。它在訓練是求解的問題為：

這從點到超平面的距離方程導出，通過增加一個約束條件消掉了優化變量的冗余?？梢宰C明，這個問題是凸優化問題，并且滿足Slater條件。這個問題帶有太多的不等式約束，不易求解，因此通過拉格朗日對偶轉換為對偶問題求解：

同樣的，這個問題也是凸優化問題。此時支持向量機并不能解決非線性分類問題，通過使用核函數，將向量變換到高維空間，使它們更可能是線性可分的。而對向量先進行映射再做內積，等價于先做內積再做映射，因此核函數并不用顯式的對向量進行映射，而是對兩個向量的內積進行映射，這是核函數的精髓。

加入核函數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是一個線性模型，如果使用非線性核，則是非線性模型，這可以從上面的預測函數看出。

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池化，則為：

注意，池化層沒有需要訓練得到的參數。

卷積神經網絡具有遷移學習的能力，我們可以把這個網絡的參數作為訓練的初始值，在新的任務上繼續訓練，這種做法稱為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算法是一種迭代法，其目標是求解似然函數或后驗概率的極值，而樣本中具有無法觀測的隱含變量。因為隱變量的存在，我們無法直接通過最大化似然函數來確定參數的值?？梢圆捎靡环N策略，構造出對數似然函數的一個下界函數，這個函數不含有隱變量，然后優化這個下界。不斷的提高這個下界，使原問題達到最優解，這就是EM算法所采用的思路。算法的構造依賴于Jensen不等式。

算法在實現時首先隨機初始化參數θ的值，接下來循環迭代，每次迭代時分為兩步：

E步，基于當前的參數估計值

，計算在給定x時對z的條件概率的數學期望：

M步，求解如下極值問題，更新θ的值：

實現Qi 時可以按照下面的公式計算：

迭代終止的判定規則是相鄰兩次函數值之差小于指定閾值。需要注意的是，EM算法只能保證收斂到局部極小值。