雷鋒網(wǎng) AI 科技評論按，本文作者張皓，目前為南京大學(xué)計(jì)算機(jī)系機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘所（LAMDA）碩士生，研究方向?yàn)橛?jì)算機(jī)視覺和機(jī)器學(xué)習(xí)，特別是視覺識別和深度學(xué)習(xí)。

個人主頁：http://lamda.nju.edu.cn/zhangh/。該文為其對雷鋒網(wǎng) AI 科技評論的獨(dú)家供稿，未經(jīng)許可禁止轉(zhuǎn)載。

摘要

本文介紹機(jī)器學(xué)習(xí)算法中的概率方法。概率方法會對數(shù)據(jù)的分布進(jìn)行假設(shè)，對概率密度函數(shù)進(jìn)行估計(jì)，并使用這個概率密度函數(shù)進(jìn)行決策。本文介紹四種最常用的概率方法：線性回歸 (用于回歸任務(wù))、對數(shù)幾率回歸 (用于二分類任務(wù))、Softmax 回歸 (用于多分類任務(wù)) 和樸素貝葉斯分類器 (用于多分類任務(wù))。* 前三
種方法屬于判別式模型，而樸素貝葉斯分類器屬于生成式模型。（*嚴(yán)格來說，前三者兼有多種解釋，既可以看做是概率方法，又可以看做是非概率方法。）

本系列文章有以下特點(diǎn): (a). 為了減輕讀者的負(fù)擔(dān)并能使盡可能多的讀者從中收益，本文試圖盡可能少地使用數(shù)學(xué)知識，只要求讀者有基本的微積分、線性代數(shù)和概率論基礎(chǔ)，并在第一節(jié)對關(guān)鍵的數(shù)學(xué)知識進(jìn)行回顧和介紹。(b). 本文不省略任何推導(dǎo)步驟，適時(shí)補(bǔ)充背景知識，力圖使本節(jié)內(nèi)容是自足的，使機(jī)器學(xué)習(xí)的初學(xué)者也能理解本文內(nèi)容。(c). 機(jī)器學(xué)習(xí)近年來發(fā)展極其迅速，已成為一個非常廣袤的領(lǐng)域。本文無法涵蓋機(jī)器學(xué)習(xí)領(lǐng)域的方方面面，僅就一些關(guān)鍵的機(jī)器學(xué)習(xí)流派的方法進(jìn)行介紹。(d). 為了幫助讀者鞏固本文內(nèi)容，或引導(dǎo)讀者擴(kuò)展相關(guān)知識，文中穿插了許多問題，并在最后一節(jié)進(jìn)行問題的“快問快答”。

1 準(zhǔn)備知識

本節(jié)給出概率方法的基本流程，后續(xù)要介紹的不同的概率方法都遵循這一基本流程。

1.1 概率方法的建模流程

(1). 對 p(y | x; θ) 進(jìn)行概率假設(shè)。我們假定 p(y| x; θ)具有某種確定的概率分布形式，其形式被參數(shù)向量
θ 唯一地確定。

(2). 對參數(shù) θ 進(jìn)行最大后驗(yàn)估計(jì)。基于訓(xùn)練樣例對概率分布的參數(shù) θ 進(jìn)行最大后驗(yàn)估計(jì) (maximum a posteriori, MAP)，得到需要優(yōu)化的損失函數(shù)。

最大后驗(yàn)估計(jì)是指

其在最大化時(shí)考慮如下兩項(xiàng)：

? 參數(shù)的先驗(yàn)分布 p(θ)。最大后驗(yàn)估計(jì)認(rèn)為參數(shù) θ 未知并且是一個隨機(jī)變量，其本身服從一個先驗(yàn)分布 p(θ)。這個先驗(yàn)分布蘊(yùn)含了我們關(guān)于參數(shù)的領(lǐng)域知識。

? 基于觀測數(shù)據(jù)得到的似然 (likelihood) p(D | θ)。最大化似然是在 θ 的所有可能的取值中，找到一個能使樣本屬于其真實(shí)標(biāo)記的概率最大的值。

最大后驗(yàn)估計(jì)是在考慮先驗(yàn)分布 p(θ) 時(shí)最大化基于觀測數(shù)據(jù)得到的似然 (likelihood) p(D | θ)。

參數(shù)估計(jì)的兩個不同學(xué)派的基本觀點(diǎn)是什么? 這實(shí)際上是參數(shù)估計(jì) (parameter estimation) 過程，統(tǒng)計(jì)學(xué)中的頻率主義學(xué)派 (frequentist) 和貝葉斯學(xué)派(Bayesian) 提供了不同的解決方案 [3, 9] 。頻率主義學(xué)派認(rèn)為參數(shù)雖然未知，但卻是客觀存在的固定值，因此通常使用極大似然估計(jì)來確定參數(shù)值。貝葉斯學(xué)派則認(rèn)為參數(shù)是未觀察到的隨機(jī)變量，其本身也可有分布，因此，可假定參數(shù)服從一個先驗(yàn)分布，然后基于觀察到的數(shù)據(jù)來計(jì)算參數(shù)的后驗(yàn)分布。

定理 1. 最大后驗(yàn)估計(jì)的結(jié)果是優(yōu)化如下形式的損失函數(shù)

Proof. 利用樣例的獨(dú)立同分布假設(shè)，

經(jīng)驗(yàn)風(fēng)險(xiǎn)和結(jié)構(gòu)風(fēng)險(xiǎn)的含義? L(θ) 的第一項(xiàng)稱為經(jīng)驗(yàn)風(fēng)險(xiǎn) (empirical risk)，用于描述模型與訓(xùn)練數(shù)據(jù)的契合程度。第二項(xiàng)稱為結(jié)構(gòu)風(fēng)險(xiǎn) (structural risk) 或正則化項(xiàng) (regularization term)，源于模型的先驗(yàn)概率，表述了我們希望獲得何種性質(zhì)的模型 (例如希望獲得復(fù)雜度較小的模型)。λ 稱為正則化常數(shù)，對兩者進(jìn)行折中。

結(jié)構(gòu)風(fēng)險(xiǎn)的作用? (1). 為引入領(lǐng)域知識和用戶意圖提供了途徑。(2). 有助于削減假設(shè)空間，從而降低了最小化訓(xùn)練誤差的過擬合風(fēng)險(xiǎn)。這也可理解為一種 “罰函數(shù)法”，即對不希望得到的結(jié)果施以懲罰，從而使得優(yōu)化過程趨向于希望目標(biāo)。?p 范數(shù)是常用的正則化項(xiàng)。

其中先驗(yàn)分布 的參數(shù)  轉(zhuǎn)化為正則化常數(shù) λ。

為什么最常假設(shè)參數(shù)的先驗(yàn)分布是高斯分布 (或最常使用  正則化)? 這是因?yàn)楦咚狗植?N (μ; Σ) 是所有均值和熵存在且協(xié)方差矩陣是 Σ 的分布中熵最大的分布。最大熵分布是在特定約束下具有最大不確定性的分布。在沒有更多信息的情況下，那些不確定的部分都是 “等可能的”。在設(shè)計(jì)先驗(yàn)分布 p(θ) 時(shí)，除了我們對參數(shù)的認(rèn)知 (例如均值和值域) 外，我們不想引入任何其余的偏見 (bias)。因此最大熵先驗(yàn) (對應(yīng)正則化) 常被使用。除高斯先驗(yàn)外，還可以使用不提供信息的先驗(yàn)(uninformative prior)，其在一定范圍內(nèi)均勻分布，對應(yīng)的損失函數(shù)中沒有結(jié)構(gòu)風(fēng)險(xiǎn)這一項(xiàng)。

(3). 對損失函數(shù) L(θ) 進(jìn)行梯度下降優(yōu)化。

梯度下降的細(xì)節(jié)留在下一節(jié)介紹。

概率方法的優(yōu)缺點(diǎn)各是什么? 優(yōu)點(diǎn): 這種參數(shù)化的概率方法使參數(shù)估計(jì)變得相對簡單。缺點(diǎn): 參數(shù)估計(jì)結(jié)果的準(zhǔn)確性嚴(yán)重依賴于所假設(shè)的概率分布形式是否符合潛在的真實(shí)數(shù)據(jù)分布。在現(xiàn)實(shí)應(yīng)用中，欲做出能較好地接近潛在真實(shí)分布的假設(shè)，往往需在一定程度利用關(guān)于應(yīng)用任務(wù)本身的經(jīng)驗(yàn)知識，否則僅憑 “猜測”來假設(shè)概率分布形式，很可能產(chǎn)生誤導(dǎo)性的結(jié)果。我們不一定非要概率式地解釋這個世界，在不考慮概率的情況下，直接找到分類邊界，也被稱為判別函數(shù) (discriminant function)，有時(shí)甚至能比判別式模型產(chǎn)生更好的結(jié)果。

1.2 梯度下降

我們的目標(biāo)是求解下列無約束的優(yōu)化問題。

其中 L(θ) 是連續(xù)可微函數(shù)。梯度下降是一種一階 (frstorder) 優(yōu)化方法，是求解無約束優(yōu)化問題最簡單、最經(jīng)典的求解方法之一。

梯度下降的基本思路? 梯度下降貪心地迭代式地最小化 L(θ)。梯度下降希望找到一個方向 (單位向量) v 使得 L 在這個方向下降最快，并在這個方向前進(jìn) α 的距離

定理 3. 梯度下降的更新規(guī)則是公式 5。重復(fù)這個過程，可收斂到局部極小點(diǎn)。

Proof. 我們需要找到下降最快的方向 v 和前進(jìn)的距離α。

(1). 下降最快的方向 v。利用泰勒展開

的一階近似，

即下降最快的方向是損失函數(shù)的負(fù)梯度方向。

(2). 前進(jìn)的距離 α。我們希望在開始的時(shí)候前進(jìn)距離大一些以使得收斂比較快，而在接近最小值時(shí)前進(jìn)距離小一些以不錯過最小值點(diǎn)。因此，我們設(shè)前進(jìn)距離為損失函數(shù)梯度的一個倍數(shù)

其中 η 被稱為學(xué)習(xí)率 (learning rate)。

向公式 7 代入最優(yōu)的和后即得。

則稱 f 為區(qū)間 [a,b] 上的凸函數(shù) (convex function)。當(dāng) < 成立時(shí)，稱為嚴(yán)格凸函數(shù) (strict convex function)。U形曲線的函數(shù)如通常是凸函數(shù)。

2 線性回歸

2.1 建模流程

線性回歸 (linear regression) 回歸問題。其建模方法包括如下三步 (參見第 1.1 節(jié))。

(1). 對 p(y | x; θ) 進(jìn)行概率假設(shè)。

我們假設(shè)

被稱為誤差項(xiàng)，捕獲了 (a)。特征向量 x 中沒有包含的因素.

(b). 隨機(jī)噪聲。對不同的樣本是獨(dú)立同分布地從中進(jìn)行采樣得到的。

線性回歸的假設(shè)函數(shù)是

為了書寫方便，我們記

那么公式 12 等價(jià)于

在本文其余部分我們將沿用這一簡化記號。因此，

(2). 對參數(shù) θ 進(jìn)行最大后驗(yàn)估計(jì)。

定理 7. 假設(shè)參數(shù) θ 服從高斯先驗(yàn)，對參數(shù) θ 進(jìn)行最大后驗(yàn)估計(jì)等價(jià)于最小化如下?lián)p失函數(shù)

其中

被稱為平方損失 (square loss)。在線性回歸中，平方損失就是試圖找到一個超平面，使所有樣本到該超平面的歐式距離 (Euclidean distance) 之和最小。

Proof

其中，最后一行只是為了數(shù)學(xué)計(jì)算上方便，下文推導(dǎo)對數(shù)幾率回歸和 Softmax 回歸時(shí)的最后一步亦然。

(3). 對損失函數(shù) L(θ) 進(jìn)行梯度下降優(yōu)化。

可以容易地得到損失函數(shù)對參數(shù)的偏導(dǎo)數(shù)

2.2 線性回歸的閉式解

線性回歸對應(yīng)的平方損失的函數(shù)形式比較簡單，可以通過求直接得到最優(yōu)解。

定理 8. 線性回歸的閉式解為

Proof. L(θ) 可等價(jià)地寫作

令

那么

求解

即得。

不可逆的情況及解決方案? (1). 屬性數(shù) d+1 多于樣例數(shù) m。(2). 屬性之間線性相關(guān)。通過正則化項(xiàng)

mλI，即使不可逆， + mλI 仍是可逆的。

2.3 其他正則化回歸模型

事實(shí)上，上文介紹的線性回歸模型是嶺回歸 (ridge regression)。根據(jù)正則化項(xiàng)的不同，有三種常用的線性回歸模型，見表 1。

基于 ?0、?1 和 ?2 范數(shù)正則化的效果? ?2 范數(shù)傾向于 w 的分量取值盡量均衡，即非零分量個數(shù)盡量稠密。而 ?0“范數(shù)”和 ?1 范數(shù)則傾向于 w 的分量盡量稀疏，即非零分量個數(shù)盡量少，優(yōu)化結(jié)果得到了僅采用一部分屬性的模型。也就是說，基于 ?0“范數(shù)”和 ?1 范數(shù)正則化的學(xué)習(xí)方法是一種嵌入式 (embedding) 特征選擇方法，其特征選擇過程和學(xué)習(xí)器訓(xùn)練過程融為一體，兩者在同一個優(yōu)化過程中完成。事實(shí)上，對 w 施加稀疏約束最自然的是使用 ?0“范數(shù)”。但 ?0“范數(shù)”不連續(xù)，難以優(yōu)化求解。因此常采用 ?1 范數(shù)來近似。

為什么 ?1 正則化比 ?2 正則化更易于獲得稀疏解？假設(shè)，則。我們繪制出平方損失項(xiàng)、?1 范數(shù)和 ?2 范數(shù)的等值線 (取值相同的點(diǎn)的連線)，如圖 1 所示。LASSO 的解要在平方損失項(xiàng)和正則化項(xiàng)之間折中，即出現(xiàn)在圖中平方誤差項(xiàng)等值線和正則化項(xiàng)等值線的相交處。從圖中可以看出，采用 ?1 正則化時(shí)交點(diǎn)常出現(xiàn)在坐標(biāo)軸上 (w₂ = 0), 而采用 ?2 正則化時(shí)交點(diǎn)常出現(xiàn)在某個象限中 (w₁，w₂ 均不為 0)。

Figure 1: ?1 正則化 (紅色) 比 ?2 正則化 (黑色) 更易于獲得稀疏解。本圖源于 [17]。

考慮一般的帶有 ?1 正則化的優(yōu)化目標(biāo)

若 ?(θ) 滿足 L-Lipschitz 條件，即

優(yōu)化通常使用近端梯度下降 (proximal gradient descent, PGD) [1]。PGD 也是一種貪心地迭代式地最小化策略，能快速地求解基于 ?1 范數(shù)最小化的方法。

定理 9. 假設(shè)當(dāng)前參數(shù)是，PGD 的更新準(zhǔn)則是

其中

Proof. 在 附近將 ?(θ) 進(jìn)行二階泰勒展開近似

由于 θ 各維互不影響 (不存在交叉項(xiàng))，因此可以獨(dú)立求解各維。

在 LASSO 的基礎(chǔ)上進(jìn)一步發(fā)展出考慮特征分組結(jié)構(gòu)的 Group LASSO [14] 、考慮特征序結(jié)構(gòu)的 Fused LASSO [11] 等變體。由于凸性不嚴(yán)格，LASSO 類方法可能產(chǎn)生多個解，該問題通過彈性網(wǎng)(elastic net)得以解決 [16] .

2.4 存在異常點(diǎn)數(shù)據(jù)的線性回歸

一旦數(shù)據(jù)中存在異常點(diǎn) (outlier)，由于平方損失計(jì)算的是樣本點(diǎn)到超平面距離的平方，遠(yuǎn)離超平面的點(diǎn)會對回歸結(jié)果產(chǎn)生更大的影響，如圖 2 所示。平方損失對應(yīng)于假設(shè)噪聲服從高斯分布，一種應(yīng)對異常點(diǎn)的方法是取代高斯分布為其他更加重尾 (heavy tail) 的分布，使其對異常點(diǎn)的容忍能力更強(qiáng)，例如使用拉普拉斯分布，如圖 3 所示。

Figure 2：存在異常點(diǎn) (圖下方的三個點(diǎn)) 時(shí)普通線性回歸 (紅色) 和穩(wěn)健線性回歸 (藍(lán)色)。本圖源于 [7]。

Figure 3: 高斯分布 N (0,1) (紅色) 和拉普拉斯分布Lap(0,1) (藍(lán)色)。本圖源于：https://www.epixanalytics.com/modelassist/AtRisk/images/15/image632.gif

定 義 2 (拉 普 拉 斯 分 布 (Laplace distribution) Lap(μ,b))，又稱為雙邊指數(shù)分布 (double sided exponential distribution)，具有如下的概率密度函數(shù)

該分布均值為 μ，方差為 

定理 10. 假設(shè)參數(shù)服從高斯先驗(yàn)，

對參數(shù) θ 進(jìn)行最大后驗(yàn)估計(jì)等價(jià)于最小化如下?lián)p失函數(shù)

Proof

由于絕對值函數(shù)不光滑，不便基于梯度下降對公式 33 進(jìn)行優(yōu)化。通過分離變量技巧，可將其轉(zhuǎn)化為二次規(guī)劃 (quadratic programming) 問題，隨后調(diào)用現(xiàn)有的軟件包進(jìn)行求解。我們在下一章形式化 SVR 時(shí)還會再使用這個技巧。

定理 11. 最小化公式 33 等價(jià)于如下二次規(guī)劃問題，其包含 d + 1 + 2m 個變量，3m 個約束：

此外，為了結(jié)合高斯分布 (對應(yīng)平凡損失) 容易優(yōu)化和拉普拉斯分布 (對應(yīng) ?1 損失) 可以應(yīng)對異常值的優(yōu)點(diǎn)，Huber 損失[5]在誤差接近 0 時(shí)為平方損失，在誤差比較大時(shí)接近 ?1 損失，如圖 4 所示。

Huber 損失處處可微，使用基于梯度的方法對 Huber 損失進(jìn)行優(yōu)化會比使用拉普拉斯分布更快。

Figure 4: ?2 損失 (紅色)、?1 損失 (藍(lán)色) 和 Huber 損失 (綠色)。本圖源于 [7]。

2.5 廣義線性模型

線性回歸利用屬性的線性組合進(jìn)行預(yù)測。除了直接利用逼近 y 外，還可以使模型的預(yù)測值逼近 y 的衍生物?？紤]單調(diào)可微函數(shù) g，令

這樣得到的模型稱為廣義線性模型 (generalized linear model)，其中函數(shù) g 被稱為聯(lián)系函數(shù) (link function)。本文介紹的線性回歸、對數(shù)幾率回歸和 Softmax 回歸都屬于廣義線性模型，如表 2 所示。

廣義線性模型的優(yōu)點(diǎn)? (1). 形式簡單、易于建模。(2). 很好的可解釋性。直觀表達(dá)了各屬性在預(yù)測中的重要性。

如何利用廣義線性模型解決非線性問題? (1). 引入層級結(jié)構(gòu)。例如深度學(xué)習(xí)是對樣本 x 進(jìn)行逐層加工，將初始的低層表示轉(zhuǎn)化為高層特征表示后使用線性分類器。(2). 高維映射。例如核方法將 x 映射到一個高維空間 ?(x) 后使用線性分類器。

3 對數(shù)幾率回歸

3.1 建模流程

對數(shù)幾率回歸 (logistic regression) 應(yīng)對二分類問題。其建模方法包括如下三步 (參見第 1.1 節(jié))。

(1). 對 p(y | x, θ) 進(jìn)行概率假設(shè)。

對二分類任務(wù)，標(biāo)記 ，而產(chǎn)生的是實(shí)數(shù)值，于是，我們需要找到一個單調(diào)可微函數(shù) g 將轉(zhuǎn)化為。最理想的是用單位階躍函數(shù)

當(dāng)大于 0 時(shí)輸出 1，小于 0 時(shí)輸出 0。但是，單位階躍函數(shù)不連續(xù)不可微，無法利用梯度下降方法進(jìn)行優(yōu)化。因此，我們希望找到一個能在一定程度上近似單位階躍函數(shù)并單調(diào)可微的替代函數(shù) (surrogate function)。

Figure 5: 單位階躍函數(shù) (紅色) 與對數(shù)幾率函數(shù) (黑色)。本圖源于 [17]。

如圖 5 所示，對數(shù)幾率函數(shù) (sigmoid function) 正是這樣一個常用的替代函數(shù)

我們將其視為后驗(yàn)概率估計(jì)，即

那么

兩者可以合并寫作

也就是說，y | x,θ 服從伯努利分布 Ber(sigm)。

(2). 對參數(shù) θ 進(jìn)行最大后驗(yàn)估計(jì)。

定理 12. 假設(shè)參數(shù) θ 服從高斯先驗(yàn)，對參數(shù) θ 進(jìn)行最大后驗(yàn)估計(jì)等價(jià)于最小化如下?lián)p失函數(shù)

其中

稱為對數(shù)幾率損失 (logistic loss)。

Proof

注意到

因此

(3). 對損失函數(shù) L(θ) 進(jìn)行梯度下降優(yōu)化。

3.2 與廣義線性模型的關(guān)系

對數(shù)幾率回歸的假設(shè)函數(shù)等價(jià)于，其中被稱為幾率 (odds)，反映 x 作為正例的相對可能性。被稱為對數(shù)幾率 (log odds, logit)，公式 50 實(shí)際上在用線性回歸模型的預(yù)測結(jié)果逼近真實(shí)標(biāo)記的對數(shù)幾率，這是對數(shù)幾率回歸名稱的由來。

對數(shù)幾率回歸的優(yōu)點(diǎn)? (1). 直接對分類的可能性進(jìn)行建模 (假設(shè) p(y | x, θ) 服從伯努利分布)，無需事先假設(shè)樣本 x 的分布，這樣避免了假設(shè)分布不準(zhǔn)確所帶來的問題。(2). 不僅能預(yù)測出類別，還可以得到近似概率預(yù)測，對許多需要概率輔助決策的任務(wù)很有用。(3). 對數(shù)幾率的目標(biāo)函數(shù)是凸函數(shù)，有很好的數(shù)學(xué)性質(zhì)。

引理 13. 對數(shù)幾率損失函數(shù)是凸函數(shù)。

Proof. 在的基礎(chǔ)上，進(jìn)一步可求得是一個半正定矩陣。

3.3  的對數(shù)幾率回歸

為了概率假設(shè)方便，我們令二分類問題的標(biāo)記。有時(shí)，我們需要處理形式的分類問題。對數(shù)幾率損失函數(shù)需要進(jìn)行相應(yīng)的改動。

(1). 對 p(y | x, θ) 進(jìn)行概率假設(shè)。

我們假設(shè)

那么

兩者可以合并寫作

(2). 對參數(shù) θ 進(jìn)行最大后驗(yàn)估計(jì)。

定理 14. 假設(shè)參數(shù) θ 服從高斯先驗(yàn)，對參數(shù) θ 進(jìn)行最大后驗(yàn)估計(jì)等價(jià)于最小化如下?lián)p失函數(shù)

其中

稱為對數(shù)幾率損失 (logistic loss)。

Proof

(3). 對損失函數(shù) L(θ) 進(jìn)行梯度下降優(yōu)化。

4 Softmax 回歸

4.1 建模流程

Softmax 回歸應(yīng)對多分類問題，它是對數(shù)幾率回歸向多分類問題的推廣。其建模方法包括如下三步 (參見
第 1.1 節(jié))。

(1). 對 p(y | x, θ) 進(jìn)行概率假設(shè)。

對數(shù)幾率回歸假設(shè) p(y | x, θ) 服從伯努利分布，Softmax 回歸假設(shè) p(y | x, θ) 服從如下分布

令

假設(shè)函數(shù)可以寫成矩陣的形式

(2). 對參數(shù) θ 進(jìn)行最大后驗(yàn)估計(jì)。

定理 15. 假設(shè)參數(shù) θ 服從高斯先驗(yàn)，對參數(shù) θ 進(jìn)行最大后驗(yàn)估計(jì)等價(jià)于最小化如下?lián)p失函數(shù)

其中

稱為交叉熵?fù)p失 (cross-entropy loss)。

Proof

(3). 對損失函數(shù) L(θ) 進(jìn)行梯度下降優(yōu)化。

損失函數(shù)對應(yīng)于類別 k 的參數(shù)的導(dǎo)數(shù)是

寫成矩陣的形式是

其中的第 k 個元素是 1，其余元素均為 0。對比公式 20 、49 和 67 ，損失函數(shù)的梯度有相同
的數(shù)學(xué)形式

區(qū)別在于假設(shè)函數(shù)的形式不同。事實(shí)上，所有的廣義線性模型都有類似于公式 68 的更新準(zhǔn)則。

4.2 交叉熵

定義由訓(xùn)練集觀察得到的分布，稱為經(jīng)驗(yàn)分布 (empirical distribution)。經(jīng)驗(yàn)分布對應(yīng)于第 i 個樣例，定義。另一方面，是由模型估計(jì)出的概率。

定理 16. 交叉熵?fù)p失旨在最小化經(jīng)驗(yàn)分布和學(xué)得分布之間的交叉熵。這等價(jià)于最小化和之間的 KL 散度，迫使估計(jì)的分布近似目標(biāo)分布。

Proof

5 樸素貝葉斯分類器

樸素貝葉斯分類器 (naive Bayes classifer) 也是一種概率方法，但它是一種生成式模型。在本節(jié)，我們首先回顧生成式模型，之后介紹樸素貝葉斯分類器的建模流程。

5.1 生成式模型

判別式模型和生成式模型各是什么? 判別式模型(discriminant model) 直接對 p(y | x) 進(jìn)行建模，生成式模型 (generative model) 先對聯(lián)合分布 p(x, y) = p(x | y)p(y) 進(jìn)行建模，然后再得到

其中，p(y) 是類先驗(yàn) (prior) 概率，表達(dá)了樣本空間中各類樣本所占的比例。p(x | y) 稱為似然 (likelihood)。p(x) 是用于歸一化的證據(jù) (evidence)。由于其和類標(biāo)記無關(guān)，該項(xiàng)不影響 p(y | x) 的估計(jì)

如何對類先驗(yàn)概率和似然進(jìn)行估計(jì)? 根據(jù)大數(shù)定律，當(dāng)訓(xùn)練集包含充足的獨(dú)立同分布樣本時(shí)，p(y) 可通過各類樣本出現(xiàn)的頻率來進(jìn)行估計(jì)

而對似然 p(x | y)，由于其涉及 x 所有屬性的聯(lián)合概率，如果基于有限訓(xùn)練樣本直接估計(jì)聯(lián)合概率，(1). 在計(jì)算上將會遭遇組合爆炸問題。(2). 在數(shù)據(jù)上將會遭遇樣本稀疏問題，很多樣本取值在訓(xùn)練集中根本沒有出現(xiàn)，而“未被觀測到”與“出現(xiàn)概率為零”通常是不同的。直接按樣本出現(xiàn)的頻率來估計(jì)會有嚴(yán)重的困難，屬性數(shù)越多，困難越嚴(yán)重。

判別式模型和生成式模型的優(yōu)缺點(diǎn)? 優(yōu)缺點(diǎn)對比如表 3 所示。

5.2 建模流程

(1). 對 p(x | y, θ) 進(jìn)行概率假設(shè)。

生成式模型的主要困難在于, 類條件概率 p(x | y)是所有屬性的聯(lián)合概率，難以從有限的訓(xùn)練樣本直接估計(jì)而得。為避開這個障礙，樸素貝葉斯分類器采用了屬性條件獨(dú)立性假設(shè)：對已知類別，假設(shè)所有屬性相互獨(dú)立。也就是說，假設(shè)每個屬性獨(dú)立地對分類結(jié)果發(fā)生影響

此外，對連續(xù)屬性，進(jìn)一步假設(shè)

因此，樸素貝葉斯分類器的假設(shè)函數(shù)是

(2). 對參數(shù) θ 進(jìn)行最大后驗(yàn)估計(jì)。參數(shù) θ 包括了第 c 類樣本在第 j 個屬性上的高斯分布的均值和
方差。

定理 17. 假設(shè)參數(shù) θ 服從不提供信息的先驗(yàn)，對參數(shù) θ 進(jìn)行最大后驗(yàn)估計(jì)的結(jié)果是

Proof. 代入公式 76

5.3 離散屬性的參數(shù)估計(jì)

樸素貝葉斯分類器可以很容易地處理離散屬性。可估計(jì)為

然而，若某個屬性值在訓(xùn)練集中沒有與某個類同時(shí)出現(xiàn)過，則根據(jù)公式 82 估計(jì)得到 0。代入公式 75 得到 -1。因此，無論該樣本的其他屬性是什么，分類結(jié)果都不會是 y = c，這顯然不太合理。

為了避免其他屬性攜帶的信息被訓(xùn)練集中未出現(xiàn)的屬性值“抹去”，在估計(jì)概率值時(shí)通常要進(jìn)行平滑(smoothing)，常用拉普拉斯修正 (Laplacian correction)。具體的說，令 K 表示訓(xùn)練集 D 中可能的類別數(shù)，n_j 表示第 j 個屬性可能的取值數(shù)，則概率估計(jì)修正為

拉普拉斯修正實(shí)際上假設(shè)了屬性值與類別均勻分布，這是在樸素貝葉斯學(xué)習(xí)中額外引入的關(guān)于數(shù)據(jù)的先驗(yàn)。在訓(xùn)練集變大時(shí)，修正過程所引入的先驗(yàn)的影響也會逐漸變得可忽略，使得估值漸趨向于實(shí)際概率值。

在現(xiàn)實(shí)任務(wù)中樸素貝葉斯有多種實(shí)現(xiàn)方式。例如，若任務(wù)對預(yù)測速度要求較高，則對給定訓(xùn)練集，可將樸素貝葉斯分類器涉及的所有概率估值事先計(jì)算好存儲起來，這樣在進(jìn)行預(yù)測時(shí)只需查表即可進(jìn)行判別。若任務(wù)數(shù)據(jù)更替頻繁，則可采用懶惰學(xué)習(xí)方式，先不進(jìn)行任何訓(xùn)練，待收到預(yù)測請求時(shí)再根據(jù)當(dāng)前數(shù)據(jù)集進(jìn)行概率估值。若數(shù)據(jù)不斷增加，則可在現(xiàn)有估值基礎(chǔ)上，僅對新增樣本的屬性值所涉及的概率估值進(jìn)行計(jì)數(shù)修正即可實(shí)現(xiàn)增量學(xué)習(xí)。

定義 3 (懶惰學(xué)習(xí) (lazy learning))。這類學(xué)習(xí)技術(shù)在訓(xùn)練階段僅僅是把樣本保存起來，訓(xùn)練時(shí)間開銷是 0，待收到測試樣本后再進(jìn)行處理。相應(yīng)的，那些在訓(xùn)練階段就對樣本進(jìn)行學(xué)習(xí)處理的方法稱為急切學(xué)習(xí)(eager learning)。

定義 4 (增量學(xué)習(xí) (incremental learning))。在學(xué)得模型后，再接收到訓(xùn)練樣例時(shí)，僅需根據(jù)新樣例對模型進(jìn)行更新，不必重新訓(xùn)練整個模型，并且先前學(xué)得的有效信息不會被“沖掉”。

5.4 樸素貝葉斯分類器的推廣

樸素貝葉斯分類器采用了屬性條件獨(dú)立性假設(shè)，但在現(xiàn)實(shí)任務(wù)中這個假設(shè)往往很難成立。于是，人們嘗試對屬性條件獨(dú)立性假設(shè)進(jìn)行一定程度的放松，適當(dāng)考慮一部分屬性間的相互依賴關(guān)系，這樣既不需要進(jìn)行完全聯(lián)合概率計(jì)算，又不至于徹底忽略了比較強(qiáng)的屬性依賴關(guān)系，由此產(chǎn)生一類半樸素貝葉斯分類器 (semi-naive Bayes classifers) 的學(xué)習(xí)方法。

獨(dú)依賴估計(jì) (one-dependent estimator, ODE) 是最常用的一種策略，其假設(shè)每個屬性在類別之外最多依賴于一個其他屬性 (稱為父屬性)。問題的關(guān)鍵在于如何確定每個屬性的父屬性。SPODE (super-parent ODE) 假設(shè)所有屬性都依賴于同一個屬性，稱為超父 (superparent)。TAN (tree augmented naive Bayes) [4] 以屬性節(jié)點(diǎn)構(gòu)建完全圖，任意兩結(jié)點(diǎn)之間邊的權(quán)重設(shè)為這兩個屬性之間的條件互信息。之后構(gòu)建此圖的最大帶權(quán)生成樹，挑選根變量，將邊置為有向，以將屬性間依賴關(guān)系約簡為樹形結(jié)構(gòu)。最后加入類別結(jié)點(diǎn) y，增加從 y 到每個屬性的有向邊。TAN 通過條件互信息刻畫兩屬性的條件相關(guān)性，最終保留了強(qiáng)相關(guān)屬性之間的依賴性。AODE (averaged ODE) [13] 嘗試將每個屬性作為超父來構(gòu)建 SPODE，之后將那些具有足夠訓(xùn)練數(shù)據(jù)支撐的 SPODE 集成作為最終結(jié)果。AODE 的訓(xùn)練過程也是“計(jì)數(shù)”，因此具有樸素貝葉斯分類器無需模型選擇、可預(yù)計(jì)算節(jié)省預(yù)測時(shí)間、也能懶惰學(xué)習(xí)、并且易于實(shí)現(xiàn)增量學(xué)習(xí)。

能否通過考慮屬性間高階依賴進(jìn)一步提升泛化性能? 相比 ODE, kDE 考慮最多 k 個父屬性。隨著依賴的屬性個數(shù) k 的增加，準(zhǔn)確進(jìn)行概率估計(jì)所需的訓(xùn)練樣本數(shù)量將以指數(shù)級增加。因此，若訓(xùn)練數(shù)據(jù)非常充分，泛化性能有可能提升。但在有限樣本條件下，則又陷入高階聯(lián)合概率的泥沼。

更進(jìn)一步，貝葉斯網(wǎng) (Bayesian network)，也稱為信念網(wǎng) (belief network)，能表示任意屬性間的依賴性。貝葉斯網(wǎng)是一種概率圖模型，借助有向無環(huán)圖刻畫屬性間的依賴關(guān)系。

事實(shí)上，雖然樸素貝葉斯的屬性條件獨(dú)立假設(shè)在現(xiàn)實(shí)應(yīng)用中往往很難成立，但在很多情形下都能獲得相當(dāng)好的性能 [2, 8]。一種解釋是對分類任務(wù)來說，只需各類別的條件概率排序正確，無須精準(zhǔn)概率值即可導(dǎo)致正確分類結(jié)果 [2]。另一種解釋是，若屬性間依賴對所有類別影響相同，或依賴關(guān)系能相互抵消，則屬性條件獨(dú)立性假設(shè)在降低計(jì)算開銷的同時(shí)不會對性能產(chǎn)生負(fù)面影響 [15]。樸素貝葉斯分類器在信息檢索領(lǐng)域尤為常用 [6]。

6 快問快答

隨機(jī)梯度下降和標(biāo)準(zhǔn)梯度下降的優(yōu)缺點(diǎn)各是什么?

? 參數(shù)更新速度。標(biāo)準(zhǔn)梯度下降需要遍歷整個訓(xùn)練集才能計(jì)算出梯度，更新較慢。隨機(jī)梯度下降只需要一個訓(xùn)練樣例即可計(jì)算出梯度，更新較快。

? 冗余計(jì)算。當(dāng)訓(xùn)練集樣本存在冗余時(shí)，隨機(jī)梯度下降能避免在相似樣例上計(jì)算梯度的冗余。

? 梯度中的隨機(jī)因素/噪聲。標(biāo)準(zhǔn)梯度下降計(jì)算得到的梯度沒有隨機(jī)因素，一旦陷入局部極小將無法跳出。隨機(jī)梯度下降計(jì)算得到的梯度有隨機(jī)因素，有機(jī)會跳出局部極小繼續(xù)優(yōu)化。

實(shí)際應(yīng)用時(shí)，常采用隨機(jī)梯度下降和標(biāo)準(zhǔn)梯度下降的折中，即使用一部分樣例進(jìn)行小批量梯度下降。此外，相比隨機(jī)梯度下降，小批量梯度下降還可以更好利用矩陣的向量化計(jì)算的優(yōu)勢。

梯度下降和牛頓法的優(yōu)缺點(diǎn)各是什么?

? 導(dǎo)數(shù)階數(shù)。梯度下降只需要計(jì)算一階導(dǎo)數(shù)，而牛頓法需要計(jì)算二階導(dǎo)數(shù)。一階導(dǎo)數(shù)提供了方向信息(下降最快的方向)，二階導(dǎo)數(shù)還提供了函數(shù)的形狀信息。

? 計(jì)算和存儲開銷。牛頓法在參數(shù)更新時(shí)需要計(jì)算 Hessian 矩陣的逆，計(jì)算和存儲開銷比梯度下降更高。

? 學(xué)習(xí)率。梯度下降對學(xué)習(xí)率很敏感，而標(biāo)準(zhǔn)的牛頓法不需要設(shè)置學(xué)習(xí)率。

? 收斂速度。牛頓法的收斂速度比梯度下降更快。

? 牛頓法不適合小批量或隨機(jī)樣本。

實(shí)際應(yīng)用時(shí)，有許多擬牛頓法旨在以較低的計(jì)算和存儲開銷近似 Hessian 矩陣。

線性回歸的損失函數(shù)及梯度推導(dǎo)。

答案見上文。

為什么要使用正則化，?1 和 ?2 正則化各自對應(yīng)什么分布，各有什么作用?

答案見上文。

對數(shù)幾率回歸的損失函數(shù)及梯度推導(dǎo)。

答案見上文。

線性分類器如何擴(kuò)展為非線性分類器?

答案見上文。

判別式模型和生成式模型各是什么，各自優(yōu)缺點(diǎn)是什么，常見算法中哪些是判別式模型，哪些是生成式模型?

答案見上文。

貝葉斯定理各項(xiàng)的含義?

答案見上文。

樸素貝葉斯為什么叫“樸素”貝葉斯?

為了避開從有限的訓(xùn)練樣本直接估計(jì) p(x | y) 的障礙，樸素貝葉斯做出了屬性條件獨(dú)立假設(shè)，該假設(shè)在現(xiàn)實(shí)應(yīng)用中往往很難成立。

References

[1] P. L. Combettes and V. R. Wajs. Signal recovery by proximal forward-backward splitting. Multiscale Modeling & Simulation, 4(4):1168–1200, 2005. 5

[2] P. M. Domingos and M. J. Pazzani. On the optimality of the simple bayesian classifer under zero-one loss. Machine Learning, 29(2-3):103–130, 1997. 12

[3] B. Efron. Bayesians, frequentists, and scientists. Journal of the American Statistical Association, 100(469):1–5, 2005. 1

[4] N. Friedman, D. Geiger, and M. Goldszmidt. Bayesian network classifers. Machine Learning, 29(2-3):131–163,1997. 12

[5] P. J. Huber. Robust estimation of a location parameter. Annals of Statistics, 53(1):492–518, 1964. 6

[6] D. D. Lewis. Naive (bayes) at forty: The independence assumption in information retrieval. In Proceedings of the 10th European Conference on Machine Learning(ECML), pages 4–15, 1998. 13

[7] K. P. Murphy. Machine Learning: A Probabilistic Perspective. MIT Press, 2012. 5, 6

[8] A. Y. Ng and M. I. Jordan. On discriminative vs. generative classifers: A comparison of logistic regression and naive bayes. In Advances in Neural Information Processing Systems 14 (NIPS), pages 841–848, 2001.12

[9] F. J. Samaniegos. A Comparison of the Bayesian and Frequentist Approaches to Estimation. Springer Science & Business Media, 2010. 1

[10] R. Tibshirani. Regression shrinkage and selection via the LASSO. Journal of the Royal Statistical Society. Series B (Methodological), pages 267–288, 1996. 4

[11] R. Tibshirani, M. Saunders, S. Rosset, J. Zhu, and K. Knight. Sparsity and smoothness via the fused lasso. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67(1):91–108, 2005. 5

[12] A. N. Tikhonov and V. I. Arsenin. Solutions of Ill-posed Problems. Winston, 1977. 4

[13] G. I. Webb, J. R. Boughton, and Z. Wang. Not so naive bayes: Aggregating one-dependence estimators. Machine Learning, 58(1):5–24, 2005. 12

[14] M. Yuan and Y. Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 68(1):49–67, 2006. 5

[15] H. Zhang. The optimality of naive bayes. In Proceedings of the Seventeenth International Florida Artifcial Intelligence Research Society Conference (FLAIRS), pages 562–567, 2004. 13

[16] H. Zou and T. Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67(2):301–320, 2005. 5

[17] 周志華. 機(jī)器學(xué)習(xí). 清華大學(xué)出版社, 2016. 5, 7, 12

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。