习题11.1
由题，根据公式 \(P(Y) = \frac{1}{\sum \limits_Y \prod \limits_C \Psi_C(Y_C)} \prod \limits_C \Psi_C(Y_C)\)
概率无向图模型的因子分解为将概率无向图模型的联合概率分布表示为其最大团上的随机变量的函数的乘积形式的操作
图11.3 的最大团为 \(\{Y_1, Y_2, Y_3\}\) 和 \(\{Y_2, Y_3, Y_4\}\)
所以 ，\(P(Y) = \frac{\Psi_{(1,2,3)} (Y_{(1,2,3)}) * \Psi_{(2,3,4)} (Y_{(2,3,4)})}{\sum \limits_Y[\Psi_{(1,2,3)} (Y_{(1,2,3)}) * \Psi_{(2,3,4)} (Y_{(2,3,4)})]}\)
习题11.2
第1步，证明 \(Z(x) = \alpha^T_n(x)*1\)
根据条件随机场的矩阵形式， \((M_{n+1}(x))_{i,j} = \begin{cases} 1, j=stop \\ 0, otherwise\end{cases}\)
根据前向向量的定义 ，\(\alpha_0(y_0|x) = \begin{cases} 1, y_0=start \\ 0, otherwise \end{cases}\)
所以，\(Z_n(x) = (M_1(x) M_2(x) ... M_{n+1} (x))_{stop, end} \\ = \alpha_0^T(x)M_1(x)M_2(x)...M_n(x)*1 \\ = \alpha_n^T(x)*1\)
第二步，证明 \(Z(x) = 1^T*\beta^T_1(x)\)
根据后向向量的定义，\(\beta_{n+1}(y_{n+1 | x}) = \begin{cases} 1,y_{n+1} = stop \\ 0,otherwise\end{cases}\)
所以，\(Z_n(x) = (M_1(x) M_2(x) ... M_{n+1} (x))_{stop, end} \\ = (M_1(x)M_2(x)...M_n(x)\beta_{n+1}(x))_{start} \\ = (\beta_1(x))_{start} = 1^T * \beta_1(x)\)
综上所述，\(Z(x) = \alpha^T_n(x)*1 = 1^T*\beta^T_1(x)\)
习题11.3
条件随机场的极大似然函数为 \(L(w)=\sum \limits ^N_{j=1} \sum \limits^K_{k=1} w_k f_k(y_j,x_j)-\sum \limits ^N_{j=1} \log{Z_w(x_j)}\)
极大化似然函数就是极小化损失函数，所以 \(f(w) = -L(w)\)
损失函数的梯度为 \(g(w) = \nabla f(w) =(\frac{\partial f(w)}{\partial w_i} ...)\)
其中， \(\frac{\partial f(w)}{\partial w_i} = -\sum \limits^N_{j=1} w_i f_i(y_j,x_j) + \sum \limits ^N_{j=1} \frac{1}{Z_w(x_j)} \cdot \frac{\partial{Z_w(x_j)}}{\partial{w_i}} \\ = -\sum \limits ^N_{j=1}w_if_i(y_j,x_j)+\sum \limits ^N_{j=1}\frac{1}{Z_w(x_j)}\sum_y(\exp{\sum^K_{k=1}w_kf_k(y,x_j))}w_if_i(y,x_j)\)
后面就可以用梯度下降法进行求解
习题11.4
以\(start=2\)为起点，\(stop=2\)为终点的所有路径的状态序列\(y\)的概率为：
路径为：2->1->2->1->2 概率为：0.21
路径为：2->2->1->1->2 概率为：0.175
路径为：2->2->1->2->2 概率为：0.175
路径为：2->1->2->2->2 概率为：0.14
路径为：2->2->2->1->2 概率为：0.09
路径为：2->1->1->1->2 概率为：0.075
路径为：2->1->1->2->2 概率为：0.075
路径为：2->2->2->2->2 概率为：0.06
概率最大的状态序列为2->1->2->1->2