### 一.CRF的定义¶

$$P(Y_v\mid X,Y_w,w\neq v)=P(Y_v\mid X,Y_w,w\sim v)$$

### 二.线性链CRF的定义¶

$$P(Y_i\mid X,Y_1,Y_2,...,Y_{i-1},Y_{i+1},...,Y-n)=P(Y_i\mid X,Y_{i-1},Y_{i+1}),i=1,2,..,n(在i=1或n时，只考虑单边)$$

### 三.CRF的参数化形式¶

$$P(y\mid x)=\frac{1}{Z(x)}exp(\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,x,i)+\sum_{i,l}\mu_ls_l(y_i,x,i))$$

$$Z(x)=\sum_yexp(\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,x,i)+\sum_{i,l}\mu_ls_l(y_i,x,i))$$

#### 简化形式¶

$$\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,x,i)+\sum_{i,l}\mu_ls_l(y_i,x,i)\\ =\sum_{k=1}^{K_1}\lambda_k[\sum_it_k(y_{i-1},y_i,x,i)]+\sum_{l=1}^{K_2}\mu_l[\sum_is_l(y_i,x,i)]\\ =[\lambda_1,..,\lambda_{K_1},\mu_1,..,\mu_{K_2}][\sum_it_1(y_{i-1},y_i,x,i),...,\sum_it_{K_1}(y_{i-1},y_i,x,i),\sum_is_1(y_i,x,i),...,\sum_is_{K_2}(y_i,x,i)]^T\\ =[w_1,..,w_K][f_1(y,x),...,f_K(y,x)]^T\\ =w^TF(y,x)$$

$$w_k=\left\{\begin{matrix} \lambda_k & k=1,2,...,K_1\\ \mu_l & k=K_1+l,l=1,2,...,K_2 \end{matrix}\right.\\ w=(w_1,w_2,...,w_K)^T$$

$$f_k(y,x)=\left\{\begin{matrix} \sum_it_k(y_{i-1},y_i,x,i) & k=1,2,...,K_1\\ \sum_is_l(y_i,x,i) & k=K_1+l,l=1,2,...,K_2 \end{matrix}\right.\\ F(y,x)=(f_1(y,x),f_2(y,x),...,f_K(y,x))^T$$

$$P(y\mid x)=\frac{1}{Z(x)}exp\sum_{k=1}^Kw_kf_k(y,x)\\ Z(x)=\sum_yexp\sum_{k=1}^Kw_kf_k(y,x)$$

#### 矩阵形式¶

$$Z_w(x)=\sum_{y_1=q_1}^{q_m}\sum_{y_2=q_1}^{q_m}\cdots\sum_{y_n=q_1}^{q_m}exp(w^TF(y,x))$$

$$w^TF(y,x)=\sum_{k=1}^Kw_kf_k(y,x)\\ =\sum_{k=1}^Kw_k\sum_{i=1}^nf_k(y_{i-1},y_i,x,i)\\ =\sum_{i=1}^n\sum_{k=1}^Kw_kf_k(y_{i-1},y_i,x,i)\\ =\sum_{i=1}^nW_i(y_{i-1},y_i\mid x)$$

$$Z_w(x)=\sum_{y_1=q_1}^{q_m}\sum_{y_2=q_1}^{q_m}\cdots\sum_{y_n=q_1}^{q_m}exp(\sum_{i=1}^n W_i(y_{i-1},y_i\mid x))\\ =\sum_{y_1=q_1}^{q_m}\sum_{y_2=q_1}^{q_m}\cdots\sum_{y_n=q_1}^{q_m}exp(W_1(y_0,y_1\mid x))exp(W_2(y_1,y_2\mid x))\cdots exp(W_n(y_{n-1},y_n\mid x))$$

（1）假设$y_i,i=1,2,..,n$共有$m$种取值$y_i\in \{q_1,q_2,...,q_{m}\}$，为了计算方便，我们为$y$引进特殊的起点和终点状态标记$y_0=start$和$y_{n+1}=stop$，不妨假设$start$和$stop$对应的状态为$q_0$和$q_{m+1}$，所以，现在$y_i$的取值状态多了2种，即$m+2$种

（2）对$i=1,2,3,...,n+1$，每一个位置构建一个$m+2$阶的矩阵：
$$M_i(x)=[M_i(q_o,q_t\mid x)]_{(m+2)\times(m+2)}\\ o,t=0,1,2,...,m,m+1$$ 这里，$[M_i(x)]_{o,t}=M_i(q_o,q_t\mid x)=exp(\sum_{k=1}^Kw_kf_k(q_o,q_t,x,i))$

（3）所以，通过DP，我们可以求得：

$$P_w(y\mid x)=\frac{1}{Z_w(x)}\prod_{i=1}^{n+1}M_i(y_{i-1},y_i\mid x)\\ Z_w(x)=[M_1(x)M_2(x)\cdots M_{n+1}(x)]_{0,m+1}$$

In [ ]: