CRF 可以看作是 logistics 回归的一个扩展

Modeling

Notions

• $\mathbf{X}$: 我们观测到的输入变量
• $\mathbf{Y}$: 我们待预测的输出变量
• $\sum_{\mathbf{y} \setminus y_s}$: 在$y_s$ 给定的情况下，y 中所有其他变量的可能的取值的遍历

G & D

Classification

Classification 是分类问题，通过给定的特征向量 $\mathbf{x}$ 我们来估计隐藏在这些数据后面的类别 $y$ 是什么，其中一个简单的方法是假设特征向量里面的变量都是相互独立的，这称为 _naive Bayes classifier_ 这是基于 x 的联合分布：

$$p(y|\mathbf{x}) = p(y) \prod_{k=1}^K p(x_k | y)$$

上面的公式也是可以写成因子图的表示形式的

另一个比较常见的模型就是 logistic regression：

$$p(y|\mathbf{x}) = \frac{1}{Z(\mathbf{x})} exp \left\{ \sum_{k=1}^K \theta_k f_k (y, \mathbf{x}) \right\}$$

Sequence Models

Classifier 只能对于单变量做预测，我们希望能对多变量做预测，为了引出这个模型，我们来讨论一个 NLP 的应用，称为 NER，NER 是用来定义一个词的类别的，比如，china，它的 NER 就是 location，更加具体一些，给定一个句子，我们确定哪些词是组合在一起的，同时对于这些词做一个区分。

一个直观的 NER 方法是对于单词做独立的区分，这种方法每个单词和它周围的单词是独立的，比如 new york 是一个地名，但是 new york times 它就是一个报纸了。。。一个方法就是把这些输出变量都串起来，形成一个链式的模型，称为 HMM，HMM 有两个独立性假设

• 每一个 state $y_t$ 只和前一个 state $y_{t-2}$ 相关
• 观测 $x_t$ 由 $y_t$ 导出

于是，state y 和 观测 x 的联合分布可以写成

$$p(\mathbf{y},\mathbf{x}) = p(y_1) \prod_{t=2}^ T p(y_t|y_{t-1}) p(x_t|y_t)$$

Comparision

Generative Model

• Naive Bayes
• HMM

Discriminative Model

• logistic regression

我们还回忆一下生成模型和判别模型的区别，生成模型中概率的一部分是分给 x 的，所以生成模型最后的联合分布的概率通常很小，就比如 naive bayes，对于判别模型，概率是 0-1 之间的条件，这就符合了逻辑回归呀，在条件概率中，x 只对 y 的概率有影响，但是完全不出现在概率中。之所以不对 $p(x)$ 建模，是因为输入的特征变量之间的相关性太高

Linear Chain CRFs

我们重写 HMM 模型到一个更加 general 的 case：

$$p(\mathbf{y}, \mathbf{x}) = \frac{1}{Z} \prod_{t=1}^T exp \left \{ \sum_{i,j \in S} 1_{\{y_t=i\}} 1_{\{y_{t-1}=j\}} + \sum_{i \in S} \sum_{o \in O} \mu_{oi} 1_{\{y_t = i\}} 1_{\{x_t = o\}} \right \}$$

当 $\theta_{ij} = log p(y^{\prime} = i | y = j)$ 时，$\mu_{oi} = log p(x=o|y=i)$ 时，就是 HMM 了，写成更一般的简洁一些的形式，即把指数的参数直接写成 feature function 为 $f_k(y_t,y_{t-1},x_t)$ 的形式：

$$p(\mathbf{y}, \mathbf{x}) = \frac{1}{Z} \prod_{t=1}^T exp \left\{ \sum_{k=1}^K \theta_k f_k (y_t, y_{t-1},x_t) \right\}$$

上面是生成模型，根据 bayes 定理我们把它写成条件概率的判别模型：

$$p(\mathbf{y}| \mathbf{x}) = \frac{p(\mathbf{y}, \mathbf{x})}{\sum_{\mathbf{y^{\prime}}}} = \frac{\prod_{t=1}^T exp \left\{ \sum_{k=1}^K \theta_k f_k(y_t,y_{t-1},x_t) \right\}}{\sum_{\mathbf{y^{\prime}}} \prod_{t=1}^T exp \left \{ \sum_{k=1}^K \theta_k f_k(y_t^{\prime}, y_{t-1}^{\prime},x_t) \right \} }$$

上面的条件概率就是 linear-chain CRF，

Definition：linear-chain CRF

$$p(\mathbf{y}| \mathbf{x}) = \frac{1}{Z(\mathbf{x})} \prod_{t=1}^T exp \left\{ \sum_{k=1}^K \theta_k f_k(y_t,y_{t-1},\mathbf{x}_t) \right\}$$

• $Y,X$ 是随机变量
• $\theta$ 是参数向量，总共有 K 个变量
• $f_k(y,y^{\prime},x_t)$ 是 feature function

General CRFs

把 linear-chain CRF 中的 linear-chain factor 用 more general 的 factor 表示就是 General CRFs

$$p(\mathbf{y}|\mathbf{x}) = \frac{1}{Z(\mathbf{x})} \prod_{\Psi_A \in G} exp \left\{ \sum_{k=1}^{K(A)} \theta_{ak} f_{ak}(\mathbf{y}_a,\mathbf{x}_a) \right\}$$

General form 的参数似乎更多，对于 linear-chain，相同的 weight 作用于每一个时间轴上的 $\Psi_t(y_t,y_{t-1},x_t)$，对于 General 的形式，我们将 G 的 factors 分成 $C= \{ C_1,C_2,…,C_p \}$ 每一个 clique $C_p$ 对应这一个 suffcient statistics $\{ f_{pk}(\mathbf{x}_p, \mathbf{y}_p) \}$ 以及参数 $\theta_p \in R^{K(p)}$，于是 CRF 可以写成：

$$p(\mathbf{y}|\mathbf{x}) = \frac{1}{Z(\mathbf{x})} \prod_{C_p\in C} \prod_{\Psi_c \in C_p} \Psi (\mathbf{x}_c,\mathbf{y}_c; \theta_p)$$ $$\Psi (\mathbf{x}_c,\mathbf{y}_c; \theta_p) = exp \left\{ \sum_{k=1}^{K(p)} \theta_{pk} f_{pk} (\mathbf{x}_c,\mathbf{y}_c) \right\}$$

Inference

。