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

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

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

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

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

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

在有些情況下，我們知道目標(biāo)函數(shù)的表達(dá)形式，但因?yàn)槟繕?biāo)函數(shù)形式復(fù)雜不方便對(duì)變量直接求導(dǎo)。這個(gè)時(shí)候可以嘗試找到目標(biāo)函數(shù)的一個(gè)下界函數(shù)，通過對(duì)下界函數(shù)的優(yōu)化，來逐步的優(yōu)化目標(biāo)函數(shù)。

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

EM算法

改進(jìn)迭代算法

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

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

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

重復(fù)步驟2，直到收斂。

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

小結(jié)

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