Lecture12 - Bayesian Theory

02-05

這講開始，我們來講講神秘的貝葉斯吧。

貝葉斯定理：

bayse定理是一個關於隨機變數A和隨機變數B的條件概率的一個準則，具體公式化為如下：

$p(A|B)= frac{p(B|A)p(A)}{sum_{i=1}^np(B|A_i)p(A_i)}$

等號右邊的分母對應了全概率公式，從這個公式，我們就可以很容易的得到 $p(A|B)和p(B|A)$ 之間的相互轉換關係。在具體的應用中，我們需要靈活的運用。

關於這個定理的應用，在後面的講解中，將向大家細細展開。

樸素貝葉斯：

樸素貝葉斯方法是基於貝葉斯定理和特徵條件獨立假設的分類方法。對於一個給定的training set來說，我們首先根據特徵條件獨立假設來學習輸入與輸出之間的聯合概率分布，然後基於這個學出來的 model，在給定的輸入x，利用貝葉斯定理求出後驗概率最大的輸出y

輸入空間為n維向量集合，那麼輸入的就是一個隨機變數
輸出空間為類別標記 $y=(c_1,c_2,...,c_k)$ ，輸出的就是一個類別的標記
X是定義在輸入空間上的隨機變數，Y是定義在輸出空間上的隨機變數
定義 $p(X,Y)$ 表示X和Y的聯合概率分布，訓練數據集為 $((x_1,y_1),(x_2,y_2),...,(x_n,y_n))$
那麼，naive貝葉斯的思想就是通過給定的訓練集來學 $p(X,Y)$
但是 $p(X,Y)$ 又不能直接學到，所以，我們藉助概率論中的乘法原理 $p(X,Y)=p(X|Y)p(Y)$
其中 $p(Y=c_k)，k=1,2,...,K$
那麼條件概率分布 $p(X=x|Y=c_k) = p(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_k),k=1,2,3,...,K$
但是，由於我們前面說過，樸素貝葉斯法其實是對條件概率的分布做了條件獨立的假設。所以說 $p(X=x|Y=c_k) = p(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_k),k=1,2,3,...,K$ 可以被改寫成為 $p(X=x|Y=c_k) = p(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_k) = prod_{j=1}^np(X^{(j)}=x^{(j)}|Y=c^{k}),k=1,2,3,...,K$
通過上面的分析，我們能夠看出來，樸素貝葉斯方法其實是通過對 $p(X,Y)$ 來進行建模的，所以說，它輸入生成模型的方法。
條件獨立性假設：是說用於分類的特徵在類確定的條件下，都是條件獨立的。

樸素貝葉斯法進行分類的時候，對於給定的輸入x，通過我們train的model計算後驗概率分布 $p(Y=c_k|X=x) = frac{p(X=x|Y=c_k)p(Y=c_k)}{p(X=x)}$

通過分析，我們知道 $p(X=x)$ 不會影響我們需要的後驗概率的大小，我們的目的是找到一個c_k，使得這個後驗概率儘可能的大，俗話說的「誰大就像誰」。

那麼，我們就得到了簡化形式下的：

$y=f(x)=argmax_{c_k}p(X=x|Y=c_k)p(Y=c_k)$

然後將上面做的條件概率獨立性假設得到的式子帶入，得到

$f(x)=argmax_{c_k}prod_{j=1}^np(X^{(j)}=x^{(j)}|Y=c_k)p(Y=c_k),k=1,2,3,...,K$

怎麼樣，應該不難吧，這就是我們通常所說的naive的貝葉斯，他能成立的一個非常重要的假設就是條件獨立性假設。

最大後驗概率：

最大後驗概率在前面講supervised learning的時候已經提到過了，其實就是MAP。我們再來想想，naive貝葉斯要做的就是將輸入的x判別到後驗概率最大的一類中，這就等價於期望風險最小化。假設我們現在的loss選擇為0-1損失。

$L(Y,f(X)) = 1, if ;Y=f(X) =0, ; Yne f(X)$

我們最終希望的是期望風險函數最小，那麼，得到的就是

$f(x) = argmin_{Y}sum_{k=1}^Kp(yne c_k|X=x)= argmin_{Y}(1-p(y=c_k|X=x))=argmax_Y(p(y=c_k|X=x))$

這樣一來，我們就得到了經驗風險最小化往往對應的就是最大後驗概率準則

極大似然估計：

極大似然估計就是我們前面講過的MLE。在最前面的幾講，都已經進行了詳細的學習，這裡就不在贅述了。

貝葉斯參數估計：

到現在來看，我們已經學習了頻率派統計的方法和基於估計單一值 $theta$ 的方法，基於該估計，就可以對unseen的data來做預測了。那麼接下來，我么就介紹一種，在預測的時候，會考慮 $theta$ 所有的可能取值的情況的估計，這種估計就是我們經常所說的貝葉斯參數估計

在進行MLE估計的過程中

我們假定 $theta$ 是固定的，並且是未知的。

那麼在做貝葉斯參數估計的過程中，

我們假定 $theta$ 是不固定的，並且也是未知的，這個時候 $theta$ 就變成了一個隨機變數，那麼隨機變數就會對應自己的分布，所以說，我們再次所做的估計就是一個全分布估計。

運用貝葉斯來估計參數和MLE有很大的不同，它通過利用概率來反映知識狀態的確定程度。在觀測數據前，我們將 $theta$ 的已知知識，表示成為其先驗分布的形式 $p(theta)$ 。關於這個分布的選取，我們一般會選擇一個非常寬泛的先驗分布，這就為了表明在我們觀測到任何數據前， $theta$ 具有的高度不確定性。例如，我們會在觀測數據前，假設 $theta$ 滿足均勻分布。

現在，假設，我們手上有一組樣本數據 $(x^1,x^2,...,x^m)$
通過貝葉斯公式，結合似然概率和先驗，我們得到 $p(theta|X) = frac{p(X|theta)p(theta)}{p(X)}$
由於我們一開始假設 $p(theta)$ 是一個高熵的分布，那麼每次由於觀測到了數據，都會使得這種不確定性下降，並最終將 $theta$ 集中在幾個可能性很大的值附近。
例如，現在觀測到了m個數據後，又來了第m+1個數據。那麼，我們得到 $p(x^{m+1}|X)=int p(x^{m+1}|theta)p(theta|X)dtheta$
通過這個公式，我們可以看出，等號的右邊包含了關於參數的後驗概率，並且以此概率作為一個權重的結果，加到了第m+1個新的觀測數據的前面。這就說明了，即使我們已經觀察到了m個數據，但是我們通過這m個數據依舊不能夠非常確定參數的值，那麼，為了達到精確的估計，我們就必須將這種不確定性一直的帶入到我們所做的任何估計中

其實，這就是貝葉斯參數估計。那麼講完了貝葉斯參數估計，以及前面學習過的MLE，我們對兩種估計方法做一個conclusion

MLE和貝葉斯估計都是參數估計
MLE和MAP都是對於參數進行點估計，而貝葉斯參數估計則是對參數進行全分布估計
由於在做貝葉斯參數估計的時候，要去給參數加一個先驗分布，這就使得這個先驗分布將會影響概率質量密度朝著參數空間中偏好先驗的區域移動。在具體的時間中，先驗的選取通常是偏好更簡單，更光滑的model。
當我們的training set有限的時候，MLE容易產生overfitting的問題，而貝葉斯參數估計卻能夠泛化的很好。但是當training set的數量很大的時候，就會帶來很大的計算代價。
從MLE到MAP再到貝葉斯估計，對參數的表示越來越精確，得到的參數估計結果也越來越接近我們希望的先驗概率，越來越能夠反映基於樣本的真實參數情況。

講完了MLE,MAP以及貝葉斯的參數估計，那麼接下來就講一個非常重要的演算法：EM演算法

EM演算法

EM演算法可以說是一個非常重要的演算法了，我們必須徹頭徹尾把這個概念理解了，因為在高斯混合模型(GMM)，K-means等很多演算法上面，都能夠看到EM的影子，而且EM演算法也是幫助我們求解一類優化問題的必備利器。

先給出EM演算法的基本概念：

EM演算法是一種迭代演算法，是用來求解那些含有隱含變數(hidden variable)的概率模型參數的極大似然估計。
說白了，EM演算法其實就是MLE的一種特例。因為MLE演算法不能求解帶有隱含變數的參數估計問題。而EM演算法剛剛好彌補了MLE演算法的不足
EM演算法的每次迭代由兩步組成：

E步：求期望(expection)
M步：求極大(maximization)
所以就叫做EM演算法了

我打算從兩個方面來講述EM演算法，

一個方面是從Jenson不等式
一個方面是從KL散度與log-likelihood的的下界優化

那麼，我們就開始吧！

Jensen『s inequality

現在有一個函數f，它的定義域和值域都是實數集合
回想大學學過的，如果一個函數f是凸函數，那麼這個函數的二階導數就大於等於0
如果f的input是向量的形式，那麼這個函數是凸函數的話，那麼這個函數的二階導數就對應海森矩陣H，H>=0

通過上面的圖，我們也可以定義，如果一個函數是凸的，那麼函數上任意兩點構成的弦一定在這個曲線的上方
對於任意 $0<=lambda<=1$ ，我們有 $f(lambda a+(1-lambda)b)<=lambda f(a)+(1- lambda)f(b)$
那麼將a,b擴展到任意x，得到 $f(sum_{i=1}^Mlambda x_i)<= sum_{i=1}^Mlambda f(x_i)$
將上述不等式推廣到更一般的形式就是 $E[f(X)]>=f[EX]$
那等號什麼時候成立呢？可以看出來當 $E[X]=X$ 到時候，等號成立，也即X為常數

好了，有了上面這些概念，你肯定就可以看懂EM演算法的推到了。我們先來說依靠jensen不等式推出來的EM演算法吧

假設，我們現在有一個參數估計問題，我們有一個觀測數據集 $(x^1,x^2,...,x^m)$ 包含了m個相互獨立的樣本。
我們想要去找到一個使得 $p(x,z)$ 這個model最合適的參數，先寫出這個問題的log-likelihood： $l(theta) = sum_{i=1}^m logp(x;theta)=sum_{i=1}^mlogsum_zp(x,z;theta)$
那麼，看看這個likelihood函數，和我們先前在學MLE時候見到的好像不太一樣啊。這個式子是先有求和，又求log，log裡面又有求和。如果還是使用MLE中的先求導，然後令其為0做，是做不出來的，也就是說，這個問題不存在closed-from形式的解。
那麼，這個時候，我們就要藉助EM演算法來幫我們求解上述式子的最大值了。我們先講講具體的思路：

首先通過E步construct一個下界
然後通過M步optimize這個下界，使得它儘可能的能夠逼近需要求解的log-likelihood函數的極大值

這個時候，我們在引入一個 $Q(z)$ ，這個 $Q(z)$ 是z的分布，並且滿足 $sum_zQ(z)=1,Q(z)>=0$
那麼上述的式子就能變成這樣
$begin{eqnarray*} sum_xlogsum_zp(x,z;theta) & = & sum_xlogsum_zQ(z;theta)frac{p(x,z;theta)}{Q(z;theta)} & >= & sum_xsum_zQ(z;theta)logfrac{p(x,z;theta)}{Q(z;theta)} end{eqnarray*}$
這是通過剛剛講的jensen不等式得到，因為這裡的log函數是一個凹函數，所以，我們需要將剛剛那個性質的符號變一下： $E[f(X)]<=f[EX]$
有了這個結論後，我們找到了log-likelihood的下界： $sum_xsum_zQ(z;theta)logfrac{p(x,z;theta)}{Q(z;theta)}$
由於為了上述不等式取等號，那麼，我們就讓 $frac{p(x,z;theta)}{Q(z;theta)}=c$
那麼 $begin{eqnarray*} Q(z;theta) & =& frac{p(x,z;theta)}{c} & = & frac{p(x,z;theta)}{csum_zQ(z;theta)} & = & frac{p(x,z;theta)}{sum_zcQ(z;theta)} & = & frac{p(x,z;theta)}{sum_z p(x,z;theta)} & = & frac{p(x,z;theta)}{p(x;theta)} & = & p(z|x;theta) end{eqnarray*}$
那麼，我們只要求Q為給搞定X下，Z的後驗概率就行了，然後把這個Q帶入到上面求出的下界中，然後優化這個下界，讓這個下界最大就OK了

那麼，EM演算法的框架就可以整理成為：

E步： $Q(Z) = p(Z|X;theta)$
M步: $theta :=argmax_{theta}sum_xsum_zQ(z)logfrac{p(X,Z;theta)}{Q(z)}$
重複E步和M步，直到收斂為止。
E步概括為：給定一個初試的 $theta$ ，那麼，我們就能通過 $theta$ 得到一個觀測Z，也即Q(Z)
M步概況為：根據這個Q(Z)，我們去尋找新的 $theta$ ，使得上述下界公式最大

那麼上面的演算法一定就會收斂么？我們只要證明了 $l(theta^t)<=l(theta^{t+1})$ ，那麼就能說明EM演算法總能夠使log-likelihood單調增加，那麼，我們就一定能找到一 $theta$ 使得上述M步成立

令 $l(theta^t) = sum_xsum_zQ(z;theta^t)logfrac{p(x,z;theta^t)}{Q(z;theta^{theta})}$

那麼 $begin{eqnarray*} l(theta^{t+1}) & >= & sum_xsum_zQ(z;theta^{t+1})logfrac{p(x,z;theta^{t+1})}{Q(z;theta^{t+1})} & >= &sum_xsum_zQ(z;theta^t)logfrac{p(x,z;theta^{t})}{Q(z;theta^{t})} & = & l(theta^t) end{eqnarray*}$

得到 $l(theta^{t+1})>=l(theta^t)$

如果我們定義：

$J(Q,theta) = sum_xsum_zQ(z)logfrac{p(X,Z;theta)}{Q(z)}$

通過，前面的推導，我們知道 $l(theta) >=J(Q,theta)$ ，結合前面在講SVM中介紹的SMO演算法中用到的坐標上升法，我們就能夠得到在E步中，相當於固定了 $theta$ 去優化Q。在M步中，相當於固定了Q去優化 $theta$ 。

從KL散度+log-likelihood下界優化：

首先介紹下KL散度的概念，KL散度是用來衡量兩個分布之間差異的，如果兩個分布越相近，那麼KL散度就越小，如果兩個分布差異越大，那麼KL散度就越大

假設p(Z)和q(Z)是兩個概率分布，那麼
$KL(q||p) = -sum_zq(z)lnp(z)-(-sum_zq(z)lnq(z))=-sum_zq(z)lnfrac{p(z)}{q(z)}$
注意 $KL(p||q) ne KL(q||p)$
$KL(p||q)>=0$

好了，如果知道了KL散度的概念，那麼我們後面的很多事情都可以迎刃而解了

那麼我們的log-likelihood就可以寫成：

$begin{eqnarray*} lnp(X|theta) & = & sum_Zq(Z)lnp(X|theta) & = & sum_Zq(Z) lnfrac{p(X,Z|theta)}{p(Z|X,theta)} & = & sum_Z q(Z)lnfrac{p(X,Z|theta)}{q(Z)}frac{q(Z)}{p(Z|X,theta)} & = & sum_Zq(Z)ln frac{p(X,Z|theta)}{q(Z)}-sum_Zq(Z)lnfrac{q(Z)}{p(Z|X,theta)} & = & L(q,theta)+KL(q||p) end{eqnarray*}$

如下圖所示，

那麼，我們通過上述式子，得到 $L(q,theta) = lnp(X|theta)-KL(q||p)$

那麼要想讓下界最大，那麼就需要讓KL散度越小越好

$KL(q||p)=-sum_Zq(Z)lnfrac{q(Z)}{p(Z|X,theta)}>=0$

上圖為當KL散度為0時候的下界值。

還是回到剛剛用Jensen公式推導EM的過程中。

E步：對應 $Q(Z) = p(Z|X;theta^{old})$
M步：對應 $L(q,theta)$ 最大

對於E步求出來的 $q(Z) = p(Z|X;theta^{old})$

那麼，我們就是要去尋找新的 $theta$ ，使得 $L(q,theta)$ 達到最大值

$begin{eqnarray*} L(q,theta)&=& sum_Zq(Z)ln frac{p(X,Z|theta)}{q(Z)} & = & sum_Zp(Z|X,theta^{old})lnp(X,Z| theta)+const end{eqnarray*}$

那麼M步對應的就是求出 $theta^{new} = argmax_{theta}sum_Zp(Z|X,theta^{old})lnp(X,Z| theta)$

更新過程如上圖所示。

同樣，我們也可以證明上述演算法是收斂的

$begin{eqnarray*} lnp(X|theta^{t+1}) & = & sum_Zq(Z)lnp(X|theta^{t+1}) & = & L(q,theta^{t+1})+KL(q||p) & >= & sum_Zp(Z|X,theta^t)lnfrac{p(X,Z|theta^{t+1})}{p(Z|X,theta^t)} & >= & sum_Zp(Z|X,theta^t)lnfrac{p(X,Z|theta^{t})}{p(Z|X,theta^t)} & = & lnp(X|theta^t) end{eqnarray*}$

另外一種觀點：

$begin{eqnarray*} lnp(X|theta) & = & lnsum_Zp(X,Z|theta) & = & lnsum_Zq(Z)frac{p(X,Z|theta)}{q(Z)} &>=&sum_Zq(Z)lnfrac{p(X,Z|theta)}{q(Z)} & = & L(q,theta) end{eqnarray*}$

其實有對應到了我們前面用Jensen不等式的推到了。

有關EM的演算法就講完了。大家學會了嗎？