基于下界函數(shù)的最優(yōu)化這樣一種優(yōu)化思路

導讀：生活中我們處處面臨最優(yōu)化的問題，比如，怎么樣一個月減掉的體重最高？怎么樣學習效率最高？怎么樣可以最大化實現(xiàn)個人價值？

顯然，每一個目標都受很多因素的影響，我們稱之為目標函數(shù)的最優(yōu)化。

優(yōu)化的思路有很多種，比如基于梯度的梯度下降，基于二階梯度的牛頓法，基于近似的二階梯度的擬牛頓法，基于下界函數(shù)的最優(yōu)化，貪婪算法，坐標下降法，將約束條件轉移到目標函數(shù)的拉格朗日乘子法等等。

本文我們討論一下基于下界函數(shù)的最優(yōu)化，且將討論的范圍限定為無約束條件的凸優(yōu)化。

基于下界函數(shù)的優(yōu)化

在有些情況下，我們知道目標函數(shù)的表達形式，但因為目標函數(shù)形式復雜不方便對變量直接求導。這個時候可以嘗試找到目標函數(shù)的一個下界函數(shù)，通過對下界函數(shù)的優(yōu)化，來逐步的優(yōu)化目標函數(shù)。

上面的描述性推導很是抽象，下面我們來看兩個具體的例子，EM算法和改進的迭代尺度法。限于篇幅，我們重點推導EM算法，改進的迭代尺度法只是提及一下。

EM算法

改進迭代算法

概率模型中最大熵模型的訓練，最早用的是通用迭代法GIS(Generalized Iterative Scaling)。GIS的原理很簡單，大致包括以下步驟：

假定初始模型（第0次迭代）為等概率的均勻分布。

用第k次迭代的模型來估算每種信息特征在訓練數(shù)據(jù)中的分布，如果超過了實際的，就把相應的模型參數(shù)變小；反之，將參數(shù)變大。

重復步驟2，直到收斂。

GIS算法，本質上就是一種EM算法，原理簡單步驟清晰，但問題是收斂太慢了。Della Pietra兄弟在1996年對GIS進行了改進，提出了IIS(Improved Iterative Scaling)算法。IIS利用log函數(shù)的性質，以及指數(shù)函數(shù)的凸性，對目標函數(shù)進行了兩次縮放，來求解下界函數(shù)。詳情可參閱李航的《統(tǒng)計學習方法》一書。

小結

本文討論了一下基于下界函數(shù)的最優(yōu)化這樣一種優(yōu)化思路，希望對大家有所幫助。同時也一如既往地歡迎批評指正，以及大神拍磚。