牛頓方法

之前我們在最大化對數(shù)似然函數(shù)l(θ)時用到了梯度上升法夷磕，現(xiàn)在我們介紹另一種方法。

我們先來看下如何用牛頓方法(Newton's Method)求解θ使得f(θ)=0爬虱。如下圖所示米碰，首先我們選取一個初始點，比如說令θ=4.5漫萄，然后作出f(θ)在該點的切線腾窝，這條切線與x軸相交的點θ=2.8作為下一次迭代的點缀踪。下右圖又一次重復了一輪迭代，f(θ)在θ=2.8處的切線與x軸相交于θ=1.8處虹脯，然后再次迭代到θ=1.3處辜贵。

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

牛頓方法可以找到θ使得f(θ)=0归形，那么如何把它應用到最大化l(θ)上呢托慨？當l(θ)達到最大點時，其導數(shù)為0暇榴，因此問題轉(zhuǎn)化為找到θ使得l'(θ)=0厚棵。所以，令f(θ)=l'(θ)蔼紧，我們推導出迭代規(guī)則：

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

其中?_θl(θ)是指l(θ)的梯度奸例，H是一個n * n的矩陣彬犯，被稱為海森矩陣(Hessian Matrix)向楼。

和梯度下降法相比，牛頓方法收斂的速度更快谐区，迭代的次數(shù)也更少湖蜕。但是牛頓方法每次迭代的計算量更大，因為每次都要計算一個n階矩陣的逆宋列≌咽悖總體而言，當n不是很大時牛頓方法計算的速度更快炼杖。當牛頓方法用來求解最大化對數(shù)似然函數(shù)l(θ)時灭返，這個方法也被稱為Fisher Scoring。

指數(shù)分布族

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

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

其中η被稱為分布的自然參數(shù)(natural parameter)导饲，或者是標準參數(shù)(canonical parameter)捞高；T(y)是充分統(tǒng)計量(sufficient statistic)，通常T(y)=y渣锦；a(η)是對數(shù)分割函數(shù)(log partition function)硝岗。e^-a(η)通常起著歸一化的作用，使得整個分布的總和/積分為1袋毙。

如果固定參數(shù)T, a, b型檀，就定義了一個以η為參數(shù)的函數(shù)族。當η取不同的值听盖，我們就得到一個不同的分布函數(shù)胀溺。

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

對于伯努利分布B(φ)皆看，其y值為0或1仓坞，因而有p(y=1;φ)=φ; p(y=0;φ)=1-φ 。所以可推導p(y;φ)如下：

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

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

接下來我們繼續(xù)來看高斯分布N(μ,σ²)虽缕。回憶下之前推導線性回歸的時候蒲稳，σ²的值與θ和h_θ(x)無關氮趋，因此為了簡化證明，我們令σ²=1江耀，所以可推導p(y;μ)如下：

對比指數(shù)分布族的定義剩胁，進而可得：

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

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

廣義線性模型

介紹完指數(shù)分布族后，我們開始正式介紹廣義線性模型(GLM)舌稀。對回歸或者分類問題來說啊犬，我們都可以借助于廣義線性模型進行預測。廣義線性模型基于如下三個假設：

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

依據(jù)這三個假設语御，我們可以推導出一個非常優(yōu)雅的學習算法，也就是GLM席怪。接下來我們分別看幾個通過GLM推導出來的算法应闯。

最小二乘法

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

上式中第一個等號來自假設2挂捻，第二個等號是高斯分布的特性碉纺，第三個等號
來自上一節(jié)中我們已經(jīng)證明了η=μ，第四個等號來自假設3刻撒。

邏輯回歸

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

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

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

Softmax回歸

接下來我們來看一個更復雜的模型狮荔。在分類問題上，我們不止預測0和1兩個值介粘，假設我們預測的值有k個殖氏，即y∈{1,2,…,k}。那么我們就不能再使用伯努利分布了姻采，我們考慮用多項式分布(Multinomial distribution)建模雅采。

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

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

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

接下來我們引入指示函數(shù)(indicator function)：1{·}。如果參數(shù)表達式為真碍舍，則指示函數(shù)取值為1柠座；表達式為假，指示函數(shù)取值為0片橡，即1{True} = 1, 1{False} = 0妈经。基于上述定義锻全，我們可以得到：(T(y))_i = 1{y = i}，進一步可得：

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

由η的表達式鳄厌，我們可以得到η和φ的對應關系：

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

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

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

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

總結

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

參考資料

• 斯坦福大學機器學習課CS229講義 pdf
• 網(wǎng)易公開課：機器學習課程 雙語字幕視頻