牛頓方法

之前我們?cè)谧畲蠡瘜?duì)數(shù)似然函數(shù)l(θ)時(shí)用到了梯度上升法，現(xiàn)在我們介紹另一種方法。

我們先來(lái)看下如何用牛頓方法(Newton's Method)求解θ使得f(θ)=0。如下圖所示，首先我們選取一個(gè)初始點(diǎn)，比如說(shuō)令θ=4.5，然后作出f(θ)在該點(diǎn)的切線，這條切線與x軸相交的點(diǎn)θ=2.8作為下一次迭代的點(diǎn)。下右圖又一次重復(fù)了一輪迭代，f(θ)在θ=2.8處的切線與x軸相交于θ=1.8處，然后再次迭代到θ=1.3處。

以此類推，我們得到迭代規(guī)則如下：

牛頓方法可以找到θ使得f(θ)=0，那么如何把它應(yīng)用到最大化l(θ)上呢？當(dāng)l(θ)達(dá)到最大點(diǎn)時(shí)，其導(dǎo)數(shù)為0，因此問(wèn)題轉(zhuǎn)化為找到θ使得l'(θ)=0。所以，令f(θ)=l'(θ)，我們推導(dǎo)出迭代規(guī)則：

上式中的θ是參數(shù)為實(shí)數(shù)的情況，當(dāng)θ為向量時(shí)，我們可以推導(dǎo)出更通用的公式：

其中?_θl(θ)是指l(θ)的梯度，H是一個(gè)n * n的矩陣，被稱為海森矩陣(Hessian Matrix)。

和梯度下降法相比，牛頓方法收斂的速度更快，迭代的次數(shù)也更少。但是牛頓方法每次迭代的計(jì)算量更大，因?yàn)槊看味家?jì)算一個(gè)n階矩陣的逆?？傮w而言，當(dāng)n不是很大時(shí)牛頓方法計(jì)算的速度更快。當(dāng)牛頓方法用來(lái)求解最大化對(duì)數(shù)似然函數(shù)l(θ)時(shí)，這個(gè)方法也被稱為Fisher Scoring。

指數(shù)分布族

到目前為止，我們分別學(xué)習(xí)了分類(classification)和回歸(regression)兩類問(wèn)題。在回歸問(wèn)題里，我們假設(shè)p(y|x;θ)服從高斯分布N(0,σ²)；在分類問(wèn)題里，我們假設(shè)p(y|x;θ)服從伯努利分布B(φ)。后面我們會(huì)看到，這兩類問(wèn)題可以被統(tǒng)一到一個(gè)更通用的模型，這個(gè)模型被稱為廣義線性模型(Generalized Linear Models, GLM)。在介紹GLM前，我們先引入一個(gè)概念：指數(shù)分布族(exponential family)。

指數(shù)分布族是指一類可以被表示為如下形式的概率分布：

其中η被稱為分布的自然參數(shù)(natural parameter)，或者是標(biāo)準(zhǔn)參數(shù)(canonical parameter)；T(y)是充分統(tǒng)計(jì)量(sufficient statistic)，通常T(y)=y；a(η)是對(duì)數(shù)分割函數(shù)(log partition function)。e^-a(η)通常起著歸一化的作用，使得整個(gè)分布的總和/積分為1。

如果固定參數(shù)T, a, b，就定義了一個(gè)以η為參數(shù)的函數(shù)族。當(dāng)η取不同的值，我們就得到一個(gè)不同的分布函數(shù)。

現(xiàn)在我們來(lái)證明高斯分布(Gaussian distribution)和伯努利分布(Bernoulli distribution)都屬于指數(shù)分布族。

對(duì)于伯努利分布B(φ)，其y值為0或1，因而有p(y=1;φ)=φ; p(y=0;φ)=1-φ 。所以可推導(dǎo)p(y;φ)如下：

對(duì)比指數(shù)分布族的定義，可得η=log(φ/(1-φ))，進(jìn)而可得φ=1/(1+e^-η)，而這正是sigmoid函數(shù)的定義。同樣對(duì)比其他參數(shù)，可得：

綜上可得，伯努利分布屬于指數(shù)分布族，且φ的形式與sigmoid函數(shù)一致。

接下來(lái)我們繼續(xù)來(lái)看高斯分布N(μ,σ²)?；貞浵轮巴茖?dǎo)線性回歸的時(shí)候，σ²的值與θ和h_θ(x)無(wú)關(guān)，因此為了簡(jiǎn)化證明，我們令σ²=1，所以可推導(dǎo)p(y;μ)如下：

對(duì)比指數(shù)分布族的定義，進(jìn)而可得：

因而我們證明了高斯分布也屬于指數(shù)分布族。事實(shí)上，大多數(shù)概率分布都屬于指數(shù)分布族，我們列舉一些如下：

• 多項(xiàng)式分布(Multinomial distribution)：對(duì)有k個(gè)離散結(jié)果的事件建模
• 泊松分布(Poisson distribution)：描述單位時(shí)間內(nèi)獨(dú)立事件發(fā)生次數(shù)的概率
• 伽馬分布(Gamma distribution)與指數(shù)分布(Exponential distribution)：描述獨(dú)立事件的時(shí)間間隔的概率
• β分布(Beta distribution)：在(0,1)區(qū)間的連續(xù)概率分布
• Dirichlet分布(Dirichlet distribution)：分布的分布(for distributions over probabilities)

廣義線性模型

介紹完指數(shù)分布族后，我們開始正式介紹廣義線性模型(GLM)。對(duì)回歸或者分類問(wèn)題來(lái)說(shuō)，我們都可以借助于廣義線性模型進(jìn)行預(yù)測(cè)。廣義線性模型基于如下三個(gè)假設(shè)：

• 假設(shè)1: p(y|x;θ) 服從以η為參數(shù)的指數(shù)分布族中的某個(gè)分布
• 假設(shè)2: 給定x，我們的目標(biāo)是預(yù)測(cè)T(y)的期望值，大多數(shù)情況下T(y)=y，所以假設(shè)函數(shù)可以寫為h(x)=E[T(y)|x]
• 假設(shè)3: η與x是線性相關(guān)的，即η=θ^Tx

依據(jù)這三個(gè)假設(shè)，我們可以推導(dǎo)出一個(gè)非常優(yōu)雅的學(xué)習(xí)算法，也就是GLM。接下來(lái)我們分別看幾個(gè)通過(guò)GLM推導(dǎo)出來(lái)的算法。

最小二乘法

假設(shè)p(y|x;θ)服從高斯分布N(μ,σ²)，我們可以推導(dǎo)如下：

上式中第一個(gè)等號(hào)來(lái)自假設(shè)2，第二個(gè)等號(hào)是高斯分布的特性，第三個(gè)等號(hào)
來(lái)自上一節(jié)中我們已經(jīng)證明了η=μ，第四個(gè)等號(hào)來(lái)自假設(shè)3。

邏輯回歸

假設(shè)p(y|x;θ)服從伯努利分布B(φ)，我們可以推導(dǎo)如下：

上式中第一個(gè)等號(hào)來(lái)自假設(shè)2，第二個(gè)等號(hào)是伯努利分布的特性，第三個(gè)等號(hào)
來(lái)自上一節(jié)中我們已經(jīng)證明了φ=1/(1+e^-η)，第四個(gè)等號(hào)來(lái)自假設(shè)3。

這里多介紹一些術(shù)語(yǔ)：將η與原始概率分布中的參數(shù)聯(lián)系起來(lái)的函數(shù)g(即g(η)=E[T(y);η])稱為標(biāo)準(zhǔn)響應(yīng)函數(shù)(canonical response function)，它的逆函數(shù)g^-1稱為標(biāo)準(zhǔn)關(guān)聯(lián)函數(shù)(canonical link function)。

Softmax回歸

接下來(lái)我們來(lái)看一個(gè)更復(fù)雜的模型。在分類問(wèn)題上，我們不止預(yù)測(cè)0和1兩個(gè)值，假設(shè)我們預(yù)測(cè)的值有k個(gè)，即y∈{1,2,…,k}。那么我們就不能再使用伯努利分布了，我們考慮用多項(xiàng)式分布(Multinomial distribution)建模。

我們用φ₁, φ₂, ... ,φ_k表示每個(gè)結(jié)果出現(xiàn)的概率，即P(y=k)=φ_k。由于所有結(jié)果概率之和為1，所以實(shí)際上k個(gè)參數(shù)中有1個(gè)是多余的，即：

為了使多項(xiàng)式分布能表示成指數(shù)分布族的形式，我們定義T(y)如下：

和我們之前的例子不一樣，T(y)這次不等于y，而是一個(gè)k-1維的向量。我們用(T(y))_i表示T(y)的第i個(gè)元素。

接下來(lái)我們引入指示函數(shù)(indicator function)：1{·}。如果參數(shù)表達(dá)式為真，則指示函數(shù)取值為1；表達(dá)式為假，指示函數(shù)取值為0，即1{True} = 1, 1{False} = 0?；谏鲜龆x，我們可以得到：(T(y))_i = 1{y = i}，進(jìn)一步可得：

現(xiàn)在我們可以證明多項(xiàng)式分布也屬于指數(shù)分布族，證明如下：

由η的表達(dá)式，我們可以得到η和φ的對(duì)應(yīng)關(guān)系：

這個(gè)從η和φ的映射函數(shù)被稱為softmax函數(shù)(softmax function)。有了softmax函數(shù)并結(jié)合假設(shè)3，我們可以求出p(y|x;θ)為：

這個(gè)k分類問(wèn)題的算法被稱為softmax回歸(softmax regression)，它是邏輯回歸更一般化的形式。

最后我們可以求出假設(shè)函數(shù)：

如果要求解參數(shù)θ，我們可以先求出它的對(duì)數(shù)似然函數(shù)l(θ)，然后用梯度上升或牛頓方法進(jìn)行迭代。

總結(jié)

• 梯度上升和牛頓方法都能用于求解最大化l(θ)的問(wèn)題，區(qū)別是牛頓方法收斂速度更快，但是它每次迭代的計(jì)算量也更大，當(dāng)數(shù)據(jù)規(guī)模不大時(shí)總體上性能更優(yōu)
• 指數(shù)分布族描述了一大類我們常見(jiàn)的概率分布，高斯分布、伯努利分布、多項(xiàng)式分布等都屬于指數(shù)分布族
• 廣義線性模型(GLM)描述了一種更通用的學(xué)習(xí)模型，最小二乘法和邏輯回歸都可以從GLM推導(dǎo)出來(lái)
• k分類問(wèn)題可以用softmax回歸建模，邏輯回歸可以看作是softmax回歸的特例(k=2)

參考資料

• 斯坦福大學(xué)機(jī)器學(xué)習(xí)課CS229講義 pdf
• 網(wǎng)易公開課：機(jī)器學(xué)習(xí)課程 雙語(yǔ)字幕視頻