【理解機器學習（一）】理解極大似然估計和EM演算法（中）盤一盤優化目標求解的那些小九九
讀者背景知識：線性回歸、邏輯回歸、SVM、最大熵模型、拉格朗日乘子法
說在前面的廢話：
前面已經講清楚了最大似然估計(MLE)與EM演算法的關係，按照計劃，是要討論EM演算法求解優化問題的思想的
不過細想，優化目標求解問題其實就那麼幾種，而EM演算法只不過是其中某種大類求解策略下的一種具體實現而已，一個是道，一個是術，道的高度是大於術的，講清楚了道，則一通百通，術便不再是問題 所以，這一節，我就給大家理一理那些優化目標求解問題中的幾大求解策略
1. 兩種優化目標：有約束與無約束
首先，大家要知道，優化目標按照是否有額外的約束條件可以分為以下兩種情況：
- 無約束的最優化問題
這種情況是最常見的，也是比較容易求解的優化問題
比如：（1）線性回歸的損失函數最小化目標（又稱為最小二乘法）：
如果再在原始最小二乘法損失函數的基礎上加上正則化項，又變成了新的優化目標：
其中，
其中，
則，優化目標可以寫成：
- 有約束的最優化問題
這一類優化問題除了有目標函數項，還有其他約束項
比如：
（1）支持向量機的最大化幾何間隔 (max margin)
它的優化目標為最大化幾何間隔，即但是，這個優化目標還要滿足額外的約束條件：
另外，根據幾何間隔的定義，可以把上面的約束條件寫成：
則，完整的優化目標可以寫成：
為了簡化優化目標，我們限定
而我們習慣將優化目標寫成最小化形式，所以，可以進一步改寫成：
（2）最大熵模型的極大化模型的熵
對於給定的訓練集
其中，
對於上面談到的兩類優化目標，第一類無約束優化目標，它可以之間使用我們常用的最優化問題的求解方法（具體內容在後面展開）進行解決，而第二類，即有約束優化目標，則不能進行直接求解，需要先將它轉化為無約束優化目標，然後再用求解無約束優化目標的方法進行求解
那麼，如何將有約束優化目標轉化為無約束優化目標呢？
需要使用拉格朗日乘子法
對於以下一般形式的帶約束的優化問題（即有等式約束，又有不等式約束）
引入拉格朗日乘子 ，定義拉格朗日函數 ： 則，在引入拉格朗日乘子法後，原先有約束優化問題就轉化成了下面的無約束優化問題： 至於為什麼
會等於 ，由於文章篇幅有限，這裡就不展開證明了
2. 兩種求解策略
讀者知識背景：線性代數
下面來討論一下怎麼求解優化問題
其實，任它優化問題千變萬化，求解起來無非就是兩種策略：
（1）標準方程法 (Normal equation method)
（2）迭代法 (iteration)
- 標準方程法
它的基本思想其實非常簡單，即假設目標函數是一個凸函數，那麼它在定義域上的最優解一般來說，是在其極值點取到，那麼我們就可以對目標函數求偏導數，且令各個偏導數的值為0，從而找出極值點，也就獲得了最優解
比如，對於線性回歸問題，其優化目標（不進行正則化）為：
即
記
為了方便後面的推導，用向量化形式來表示：
其中，
則對模型參數的每一項求偏導數，得到
而
因此
所以，
上面的推導過程，涉及到比較深的線性代數的知識，尤其是關於矩陣的跡相關的知識，看不懂沒有關係，上面講這麼多只是想說明，可以通過對目標函數求導並讓導數為0來得到解
- 迭代法
像我們最熟悉的梯度下降法以及牛頓法或擬牛頓法都屬於迭代求解的方法，包括我們下一節要進一步討論的EM演算法也屬於迭代法
它們的基本思想為：
與標準方程法一步到位獲得最優解的策略不同，迭代法先找一個隨機解做為起始的當前解，然後對當前解進行迭代更新，保證每一次迭代後得到的新解朝著最優化的方向前進，即
若最優化目標為：
則找到一種解的更新方法，實現 ，保證 不斷迭代，直到目標函數不再朝著優化目標改變為止，即解已經收斂了，此時的解W即為最優解不過迭代法不能保證收斂到的解是全局最優，它很可能落到局部最優位置
區別具體的迭代法的，是它們各自所採用的參數更新的方法
比如梯度下降法的參數更新的方法為：
參考資料：
(1) 周志華《機器學習》
(2) 李航《統計學習方法》
(3) 吳軍《數學之美》
(4) 蘭艷艷《SVM演算法》，國科大《模式識別與機器學習》課程
(5) 吳恩達《斯坦福大學·機器學習》公開課
(6) 機械工業出版社《機器學習實戰：基於Scikit-Learn和TensorFlow》
推薦閱讀：