西瓜書習題試答-第14章-機率圖模型

時間 2020-09-26 標籤西瓜書習題試答第 14 章機率圖模型

試答系列：「西瓜書」-周志華《機器學習》習題試答
系列目錄
[第01章：緒論]
[第02章：模型評估與選擇]
[第03章：線性模型]
[第04章：決策樹]
[第05章：神經網絡]
[第06章：支持向量機]
第07章：貝葉斯分類器
 第08章：集成學習
 第09章：聚類
 第10章：降維與度量學習
 第11章：特徵選擇與稀疏學習
第12章：計算學習理論(暫缺)
第13章：半監督學習
 第14章：機率圖模型
(後續章節更新中...)html

14.1 試用盤式記法表示條件隨機場和樸素貝葉斯分類器.

答：見下圖。其中，對於樸素貝葉斯分類器的盤式記法是毫無懸念的。而對於通常的條件隨機場，狀況較複雜，難以統一表示，下面僅對鏈式條件隨機場進行盤式表示。然而，即使對於簡單的鏈式條件隨機場，也並不符合14.5.2節中所述：「...相互獨立的、由相同機制生成的多個變量...」的條件。這裏只是模仿其「對重複單元進行簡化表示」的精神。

網絡

14.2 試證實圖模型中的局部馬爾科夫性：給定某變量的鄰接變量，則該變量條件獨立於其餘變量.

答：參考教材正文14.2節，文中已經證實了「全局馬爾科夫性」：給定兩個變量子集的分離集，則這兩個變量子集條件獨立。由它能夠獲得兩個推論，也就是這裏習題14.2和14.3的結論。
對於14.2的局部馬爾科夫性，鄰接變量做爲分離集，將給定變量與其餘變量分離。
對於14.3的成對馬爾科夫性，其餘全部變量做爲分離集，將兩個非鄰接變量分離。機器學習

14.3 試證實圖模型中的成對馬爾科夫性：給定其餘全部變量，則兩個非鄰接變量條件獨立.

答：參見習題14.2。函數

14.4 試述馬爾科夫隨機場中爲什麼僅需對極大團定義勢函數。

答：這裏試圖從動機的角度來講明表示爲極大團勢函數的形式有什麼好處。
咱們已經有了關於「團」、「分離子集」、「馬爾科夫性(條件獨立)」的概念。如今，讓咱們對於如下幾點達成共識：學習

對於任意關於一組隨機變量\(x_1,x_2,\cdots x_N\)的機率分佈均可以表達爲\(P(x_1,x_2,\cdots x_N)\)，用機率圖模型能夠表示爲一個「全鏈接」的「團」，亦即任意兩個變量之間都有關聯。
可是，這樣的話，對於機率圖模型就毫無優點可言了。在一個具體的機率圖模型中，並不是一個全鏈接，一個具體的圖結構能夠體現出一些條件獨立性等信息，這樣能夠對機率分佈的表達式進行簡化。
若是一個圖結構存在可分離子集，根據馬爾科夫性，能夠將機率表達式進行「降維」、「分離變量」。
好比，對於下面的圖結構中，變量子集\(C=\{C_1,C_2\}\)將\(A=\{A_1,A_2,A_3,A_4\}\)和\(B=\{B_1,B_2,B_3\}\)分離。

因爲馬爾科夫性，聯合機率能夠表示爲：

\[\begin{aligned} P(A,B,C)&=P(C)P(A|C)P(B|C)\\ &=P(A,C)P(B,C)/P(C)\\ \end{aligned}\]

這樣，便將聯合機率函數進行了「分解」、「降維」、「分離變量」，從原先的3維函數(將ABC視同單個變量)變爲兩個2維和一個1維函數的乘積形式(除法也可視爲乘法)。
這個過程能夠繼續下去，好比，進一步對P(B,C)進行分解：
spa

\[\begin{aligned} P(C,B_1,B_2,B_3)&=P(B_1,B_3)P(C|B_1,B_3)P(B_2|B_1,B_3)\\ &=P(C,B_1,B_3)P(B_1,B_2,B_3)/P(B_1,B_3)\\ \end{aligned}\]

這樣便將原先的4維函數(將C視爲一個變量)分解爲兩個3維函數和一個2維函數的乘積形式。
這樣的分解一直到何時呢？直到分解以後的各部分因子爲團爲止。
3. 一個「團」具備全鏈接結構，其中不存在可分離變量子集，對團進行分解表示時，並不會降維和分離變量。
好比，對於僅兩個變量的團：
htm

\[\begin{aligned} P(A,B)&=P(A)P(B|A)\\ &=P(B)P(A|B) \end{aligned}\]

無論怎麼分解，原先爲2維函數，分解後的各部分中最高維數仍然是2維，沒法達到降維和分離變量的目的。所以，第2部分所說的對聯合機率的分解，一直分解到團爲止，便再也不繼續往下分解了。
舉個具體實例，對於下圖：
blog

\[\begin{aligned} P(ABCDE)&=\frac{P(ABCD)P(BCDE)}{P(BCD)}\\ &=\frac{P(ABC)P(BCD)}{P(BC)}\cdot\frac{P(BCD)P(BDE)}{P(BD)}\cdot \frac{1}{P(BCD)}\\ &=\frac{P(ABC)P(BCD)P(BDE)}{P(BC)P(BD)} \end{aligned}\]

其中第一行以{B,C,D}做爲A和E分離子集，第二行以{BC}做爲A和D的分離子集，以{B,D}做爲C和E的分離子集。
能夠發現一個規律：
將聯合機率按可分離狀況進行分解，一直到分解結果各項爲團的聯合機率爲止，所得結果表達式爲（各個極大團的聯合機率之積）除以（極大團之間相交結點子集所構成的(非極大)團的聯合機率之積）
好比，上面的，get

\[P(ABCDE)=\frac{P(ABC)P(BCD)P(BDE)}{P(BC)P(BD)} \]

關於全部變量的聯合機率能夠分解爲關於各個極大團函數的乘積的形式。
好比，對於上式，將分母上的子團與包含它的極大團的聯合機率函數進行合併：

\[\begin{aligned} P(ABCDE)&=\frac{P(ABC)P(BCD)P(BDE)}{P(BC)P(BD)}\\ &=\frac{P(ABC)}{\sqrt{P(BC)}}\cdot\frac{P(BCD)}{\sqrt{P(BC)P(BD)}}\cdot\frac{P(BDE)}{\sqrt{P(BD)}}\\ &=f(ABC)h(BCD)g(BDE) \end{aligned}\]

不妨稱這些關於極大團的函數爲極大團的勢函數。
這就是爲何只需對極大團定義勢函數的緣由，由於聯合機率恰好能夠分解爲極大團勢函數的形式。class

14.5 比較條件隨機場和對率迴歸，試析其異同。

答：

二者都是判別模型P(y|x)，在對率迴歸中，y僅一個變量，取值爲{1,0}或者{1,-1}，其擴展形式softmax模型中一樣只有一個y，可是取值能夠爲{1,2,...,N}。
從表達式形式上看，對率迴歸表達爲：

\[p(y|x)=\frac{e^{y(w^Tx+b)}}{\sum_{y=1,0}e^{y(w^Tx+b)}} \]

而softmax可表達爲：

\[p(y_i|x)=\frac{e^{(w_i^Tx+b_i)}}{\sum_{y_j}e^{y_j(w_j^Tx+b_j)}} \]

鏈式條件隨機場則表達爲：

\[P(y|x)=\frac{1}{Z}exp\left(\sum_j\sum_{i=1}^{n-1}\lambda_jt_j(y_{i+1},y_i,x,i)+\sum_k\sum_{i=1}^n\mu_ks_k(y_i,x,i)\right) \]

參考李航《統計學習方法》11.2.3節「條件隨機場的簡化形式」，將轉移特徵函數\(t_j\)和\(s_k\)統一視表示爲特徵函數\(f_k(y_{i+1},y_i,x,i)\)，而後對各個節點求和後記做\(f_k(y,x)\)，將權重\(\lambda_j\)和\(\mu_k\)統一表示爲權重\(w_k\)，則上式可轉化爲：

\[\begin{aligned} p(y|x)&=\frac{1}{Z}exp\sum_k w_k f_k(y,x)\\ &=\frac{e^{W^T F(y,x)} } {Z}\\ &=\frac{e^{W^T F(y,x)} } {\sum_y e^{W^T F(y,x)}}\\ \end{aligned}\]

它們的共同點在於，非歸一化的機率(也就是分子部分)都表示爲一個線性函數的指數函數形式，只不過在條件隨機場中須要先用\(f_k(y,x)\)的特徵函數將(y,x)轉換爲特徵，而後再進行線性計算。

14.6 試證實變量消去法的計算複雜度隨圖模型中極大團規模的增加而呈指數增加，但隨結點數的增加未必呈指數增加。

答：