讀者背景知識：線性回歸、邏輯回歸、SVM、最大熵模型、拉格朗日乘子法

說在前面的廢話：

前面已經講清楚了最大似然估計(MLE)與EM演算法的關係，按照計劃，是要討論EM演算法求解優化問題的思想的

不過細想，優化目標求解問題其實就那麼幾種，而EM演算法只不過是其中某種大類求解策略下的一種具體實現而已，一個是道，一個是術，道的高度是大於術的，講清楚了道，則一通百通，術便不再是問題 所以，這一節，我就給大家理一理那些優化目標求解問題中的幾大求解策略

1. 兩種優化目標：有約束與無約束

首先，大家要知道，優化目標按照是否有額外的約束條件可以分為以下兩種情況：

  • 無約束的最優化問題

這種情況是最常見的，也是比較容易求解的優化問題

比如：

（1）線性回歸的損失函數最小化目標（又稱為最小二乘法）：

min_w frac 12 sum_{i=1}^m(h(x_i)-y_i)^2

如果再在原始最小二乘法損失函數的基礎上加上正則化項，又變成了新的優化目標：

min_w frac 12 sum_{i=1}^m(h(x_i)-y_i)^2+lambdasum_{j=1}^n|w_i|quad LASSO

min_w frac 12 sum_{i=1}^m(h(x_i)-y_i)^2+lambdasum_{j=1}^n|w_i|_2^2quad ext{嶺回歸}

其中， lambda 是正則化項的係數，用於權衡模型結構風險與經驗風險的比重，可以看到LASS回歸於嶺回歸的差別僅僅在於使用的正則化項而已，LASS使用的是L1正則化，嶺回歸使用的是L2正則化

（2）邏輯回歸的最大對數似然估計：

egin{aligned} &max_w logprod_{i=1}^m P(y_i mid x_i) \ &= logprod_{i=1}^m P(y_i=1 mid x_i)^{y_i}P(y_i=0 mid x_i)^{1-y_i} \ &= sum_{i=1}^m y_ilog P(y_i=1 mid x_i)+(1-y_i)log(1-P(y_i=1 mid x_i)) end{aligned}

其中，

h(x)=P(y=1mid x)=frac{1}{1+e^{wx}}\ P(y=0mid x)=1-P(y=1mid x)=frac{e^{wx}}{1+e^{wx}}

則，優化目標可以寫成：

max_w sum_{i=1}^m y_ilog h(x_i)+(1-y_i)log(1-h(x_i))

  • 有約束的最優化問題

這一類優化問題除了有目標函數項，還有其他約束項

比如：

（1）支持向量機的最大化幾何間隔 (max margin)

它的優化目標為最大化幾何間隔，即

max_w r=frac {hat r}{||W||}

其中， r 是樣本集合在樣本空間的幾何間隔（幾何間隔：樣本點到分界面的垂直距離）， hat r 是函數間隔，幾何間隔與函數間隔滿足 r=hat r/||W|| ， W 是分界超平面的係數向量，SVM的目標就是要讓上圖中的r最大化

但是，這個優化目標還要滿足額外的約束條件：

r^{(i)}ge r

其中， r^{(i)} 表示每個樣本各自的幾何間隔，很顯然幾何的幾何間隔肯定要大於等於每個樣本各自的幾何間隔

另外，根據幾何間隔的定義，可以把上面的約束條件寫成：

y_ifrac{W^Tx_i}{||W||}ge frac{hat r}{||W||}quad Rightarrow y_i(W^Tx_i)ge hat r

則，完整的優化目標可以寫成：

max_W frac{hat r}{||W||} \ s.t. quad y_i(W^Tx_i)ge hat r quad i=1,2,...,m

為了簡化優化目標，我們限定 hat r=1 ，則完整的優化目標可以寫成：

max_W frac{1}{||W||} \ s.t. quad y_i(W^Tx_i)ge 1 quad i=1,2,...,m

而我們習慣將優化目標寫成最小化形式，所以，可以進一步改寫成：

min_W frac 12 ||W|| \ s.t. quad 1-y_i(W^Tx_i)le 0 quad i=1,2,...,m

（2）最大熵模型的極大化模型的熵

對於給定的訓練集 T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)} 以及特徵函數 f_i(x,y),, i=1,2,...,n ，最大熵模型的學習等價於約束最優化問題：

max_{Pin C} H(P)=-sum_{x,y} hat P(x)P(ymid x)log P(y mid x) \ s.t. quad E_P(f_i)=E_{hat P}(f_i), , i=1,2,...,n \ sum_y P(y mid x)=1

其中， C 是滿足約束條件的模型空間， hat P(x) 是訓練樣本的邊際分布 P(x) 的經驗分布， E_{hat P}(f) 是經驗分布 hat P(X,Y) 的期望值， E_P(f) 是模型 P(y mid x) 與經驗分布 hat P(X,Y) 的期望值，即

E_{hat P}(f)=sum_{x,y} hat P(x,y)f(x,y)

E_P(f)=sum_{x,y} hat P(x)P(y mid x)f(x,y)

對於上面談到的兩類優化目標，第一類無約束優化目標，它可以之間使用我們常用的最優化問題的求解方法（具體內容在後面展開）進行解決，而第二類，即有約束優化目標，則不能進行直接求解，需要先將它轉化為無約束優化目標，然後再用求解無約束優化目標的方法進行求解

那麼，如何將有約束優化目標轉化為無約束優化目標呢？

需要使用拉格朗日乘子法

對於以下一般形式的帶約束的優化問題（即有等式約束，又有不等式約束）

min_w f(w) \ s.t. quad g_i(w) le 0, , i=1,2,...,k \ h_i(w)=0, , i=1,2,...,l 引入拉格朗日乘子 alpha_1,alpha_2,...,alpha_k,eta_1,eta_2,...,eta_l ，定義拉格朗日函數 L(w,alpha,eta) ： L(w,alpha,eta)=f(w)+sum_{i=1}^k alpha_i g_i(w) + sum_{i=1}^l eta_i h_i(w) 則，在引入拉格朗日乘子法後，原先有約束優化問題就轉化成了下面的無約束優化問題：

min_w max_{alpha>0,eta} L(w,alpha,eta)

至於為什麼 f(w) 會等於 max_{alpha>0,eta} L(w,alpha,eta) ，由於文章篇幅有限，這裡就不展開證明了

2. 兩種求解策略

讀者知識背景：線性代數

下面來討論一下怎麼求解優化問題

其實，任它優化問題千變萬化，求解起來無非就是兩種策略：

（1）標準方程法 (Normal equation method)

（2）迭代法 (iteration)
  • 標準方程法

它的基本思想其實非常簡單，即假設目標函數是一個凸函數，那麼它在定義域上的最優解一般來說，是在其極值點取到，那麼我們就可以對目標函數求偏導數，且令各個偏導數的值為0，從而找出極值點，也就獲得了最優解

比如，對於線性回歸問題，其優化目標（不進行正則化）為：

min_w frac 12 sum_{i=1}^m(h(x_i)-y_i)^2

即

min_w frac 12 sum_{i=1}^m(W^Tx_i-y_i)^2

記

f(W)=frac 12 sum_{i=1}^m(W^Tx_i-y_i)^2

為了方便後面的推導，用向量化形式來表示：

f(W)=frac 12 [XW-Y]^T[XW-Y]

其中，

W=(w_0,w_1,...,w_n)^T

X= egin{bmatrix} -x_1- \ -x_2- \ ... \ -x_m- end{bmatrix}

Y=(y_1,y_2,...,y_m)^T

則對模型參數的每一項求偏導數，得到

egin{aligned} Delta_W f(W) &= frac 12 Delta_W [XW-Y]^T[XW-Y] \ &= frac 12 Delta_W (W^TX^TXW - W^TX^TY - Y^TXW+Y^TY) \ &= frac 12 Delta_W tr(W^TX^TXW - W^TX^TY - Y^TXW+Y^TY) \ &= frac 12 Delta_W tr(WW^TX^TX - Y^TWX - Y^TXW) end{aligned}

而

Delta_W tr(WW^TX^TX)=X^TXWI + X^TXWI \ Delta_W tr(Y^TXW)=X^TY

因此

Delta_W f(W)=frac 12 [X^TXW + X^TXW - X^TY- X^TY]=X^TXW-X^TY

所以，

X^TXW=X^TY Rightarrow W=(X^TX)^{-1}Y

上面的推導過程，涉及到比較深的線性代數的知識，尤其是關於矩陣的跡相關的知識，看不懂沒有關係，上面講這麼多只是想說明，可以通過對目標函數求導並讓導數為0來得到解

  • 迭代法

像我們最熟悉的梯度下降法以及牛頓法或擬牛頓法都屬於迭代求解的方法，包括我們下一節要進一步討論的EM演算法也屬於迭代法

它們的基本思想為：

與標準方程法一步到位獲得最優解的策略不同，迭代法先找一個隨機解做為起始的當前解，然後對當前解進行迭代更新，保證每一次迭代後得到的新解朝著最優化的方向前進，即

若最優化目標為：

min_W f(W) 則找到一種解的更新方法，實現 W o W+delta ，保證 f(W_{i+1})le f(W_i) 不斷迭代，直到目標函數不再朝著優化目標改變為止，即解已經收斂了，此時的解W即為最優解不過迭代法不能保證收斂到的解是全局最優，它很可能落到局部最優位置

區別具體的迭代法的，是它們各自所採用的參數更新的方法

比如梯度下降法的參數更新的方法為：

W o W - alpha Delta f(W)

參考資料：

(1) 周志華《機器學習》

(2) 李航《統計學習方法》

(3) 吳軍《數學之美》

(4) 蘭艷艷《SVM演算法》，國科大《模式識別與機器學習》課程

(5) 吳恩達《斯坦福大學·機器學習》公開課

(6) 機械工業出版社《機器學習實戰：基於Scikit-Learn和TensorFlow》


推薦閱讀：
相关文章