我们知道，分类问题可以分为硬分类和软分类两种，其中硬分类有 SVM，PLA，LDA 等。软分类问题大体上可以分为概率生成和概率判别模型，其中较为有名的概率判别模型有 Logistic 回归，生成模型有朴素贝叶斯模型。Logistic 回归模型的损失函数为交叉熵，这类模型也叫对数线性模型，一般地，又叫做最大熵模型，这类模型和指数族分布的概率假设是一致的。对朴素贝叶斯假设，如果将其中的单元素的条件独立性做推广到一系列的隐变量，那么，由此得到的模型又被称为动态模型，比较有代表性的如 HMM，从概率意义上，HMM也可以看成是 GMM 在时序上面的推广。
我们看到，一般地，如果将最大熵模型和 HMM相结合，那么这种模型叫做最大熵 Markov 模型（MEMM）：
graph LR;
x4((x4))-->y4
x2((x2))-->y2
x1((x1))-->y1
x3((x3))-->y3
y1-->y2;
y2-->y3;
y3-->y4;
这个图就是将 HMM 的图中观测变量和隐变量的边方向反向，应用在分类中，隐变量就是输出的分类，这样 HMM 中的两个假设就不成立了，特别是观测之间不是完全独立的了。
HMM 是一种生成式模型，其建模对象为
在 MEMM 中，建模对象是
MEMM 的缺陷是其必须满足局域的概率归一化（Label Bias Problem），我们看到，在上面的概率图中，$p(y_t|y_{t-1},x_t)$， 这个概率，如果
对于这个问题，我们将
graph LR;
x4((x4))-->y4
x2((x2))-->y2
x1((x1))-->y1
x3((x3))-->y3
y1---y2;
y2---y3;
y3---y4;
线性链的 CRF 的 PDF 为
对于这个
我们可以设计一个表达式将其参数化：
$$
\begin{align}
\Delta_{y_t,y_{t-1},X}&=\sum\limits_{k=1}^K\lambda_kf_k(y_{t-1},y_t,X)\
\Delta_{y_{t},X}&=\sum\limits_{l=1}^L\eta_lg_l(y_t,X)
\end{align}
$$
其中 $g,f $ 叫做特征函数，对于
代入概率密度函数中：
$$
p(Y|X)=\frac{1}{Z}\exp\sum\limits_{t=1}^T[\sum\limits_{k=1}^K\lambda_kf_k(y_{t-1},y_t,X)+\sum\limits_{l=1}^L\eta_lg_l(y_t,X)]
$$
对于单个样本，将其写成向量的形式。定义
CRF 需要解决下面几个问题：
-
Learning：参数估计问题，对
$N$ 个$T$ 维样本，$\hat{\theta}=\mathop{argmax}\limits_{\theta}\prod\limits_{i=1}^Np(y^i|x^i)$，这里用上标表示样本的编号。 -
Inference：
- 边缘概率： $$ p(y_t|x) $$
-
条件概率：一般在生成模型中较为关注，CRF 中不关注
-
MAP 推断： $$ \hat{y}=\mathop{argmax}p(y|x) $$
边缘概率这个问题描述为，根据学习任务得到的参数，给定了
首先，将两个求和分为：
$$
\begin{align}&p(y_t=i|x)=\frac{1}{Z}\Delta_l\Delta_r\
&\Delta_l=\sum\limits_{y_{1:t-1}}\phi_{1}(y_0,y_1,x)\phi_2(y_1,y_2,x)\cdots\phi_{t-1}(y_{t-2},y_{t-1},x)\phi_t(y_{t-1},y_t=i,x)\
&\Delta_r=\sum\limits_{y_{t+1:T}}\phi_{t+1}(y_t=i,y_{t+1},x)\phi_{t+2}(y_{t+1},y_{t+2},x)\cdots\phi_T(y_{T-1},y_T,x)
\end{align}
$$
对于
类似地，$\Delta_r=\beta_t(i)=\sum\limits_{j\in S}\phi_{t+1}(y_t=i,y_{t+1}=j,x)\beta_{t+1}(j)$。这个方法和 HMM 中的前向后向算法类似，就是概率图模型中精确推断的变量消除算法（信念传播）。
在进行各种类型的推断之前，还需要对参数进行学习：
$$
\begin{align}\hat{\theta}&=\mathop{argmax}{\theta}\prod\limits{i=1}^Np(y^i|x^i)\
&=\mathop{argmax}\theta\sum\limits{i=1}^N\log p(y^i|x^i)\
&=\mathop{argmax}\theta\sum\limits{i=1}^N[-\log Z(x^i,\lambda,\eta)+\sum\limits_{t=1}^T[\lambda^Tf(y_{t-1},y_t,x)+\eta^Tg(y_t,x)]]
\end{align}
$$
上面的式子中，第一项是对数配分函数，根据指数族分布的结论：
$$
\nabla_\lambda(\log Z(x^i,\lambda,\eta))=\mathbb{E}{p(y^i|x^i)}[\sum\limits{t=1}^Tf(y_{t-1},y_t,x^i)]
$$
其中，和
于是：
$$
\nabla_\lambda L=\sum\limits_{i=1}^N\sum\limits_{t=1}^T[f(y_{t-1},y_t,x^i)-\sum\limits_{y_{t-1}}\sum\limits_{y_t}p(y_{t-1},y_t|x^i)f(y_{t-1},y_t,x^i)]
$$
利用梯度上升算法可以求解。对于
译码问题和 HMM 中的 Viterbi 算法类似，同样采样动态规划的思想一层一层求解最大值。