CRF

PGM

我们首先讲讲概率图模型吧。作为建模的最主要的工具，不知道是不是不太好啊。个人观点是： Model based 学习方法才是更合理的，为什么这样说呢。首先呢，我们希望的是解释性，是对某些事物，某些现象做出合理的解释。那什么是解释性呢？这里我们可以说是一种因果关系，就是说一个属性和另一个属性，一个时间和另一个事件之间的因果关系。这种关系，我认为是一种基于人的认知的，也就是说机器不会有的。那 Model free 的学习方法在学习什么呢？我认为这种模型在学习一种相关性，也就是说，一个时间和另一个事件的相关性，是正相关还是负相关。我们都知道相关性不等于因果性。但是某种意义上，这两个关系也有很强的关系，使得很难区分。首先机器是没有办法区分的，因为因果性不是简简单单的相关性加上时间序，因果性需要更强的物理意义，物理意义有很难直接跨过认为建模来在机器中直接产生。所以我倾向于 Model based 学习方法。

PGM ，就是 probabilistic graphical models 的简称，中文翻译作概率图模型。这个基础理论由来已久了吧，经过人们的不断地完善，这个理论已经趋于成熟。我也是参看了 Daphne Kollar 的《概率图模型：原理和技术》（中译版），对概率图模型有了一个初步的认识。图模型，这个我们在离散数学中经常提到的概念，在这里变成了可以一种抽象工具。可以抽象一个事件的各个部件之间的关系，可以抽象一个问题的前因后果，甚至可以抽象整个世界的运转（说的有点夸张，不过确实是有很大用处）。我知道的一些大牛，例如 Micheal Jordan，Bishop 对这个领域都是做出了很大的贡献吧。在概率图模型中最重要的就是独立性假设，这个东西应该硕士贯穿始终的东西吧，之所以概率图模型能抽象简化问题，就是因为这个独立性假设，这些是人类知识，或者说是对事物观察的体现吧。下面，先简要介绍一下有向图网络，在介绍无向图网络，这个其中就有条件随机场。

贝叶斯网络

这里我们知识粗略的介绍一下关于贝叶斯网络的东西，给大家一个 intuitive inspection 就可以了，具体的还是要看国语概率图模型的教材。一个直观的感觉还是比较好说的，毕竟这个东西本来就是来对现实世界中发生的事件进行建模的，所以我们很容易直观的理解为什么这样建模。下面还是以一些教材上的例子来给我们以一个直观的感觉吧。

例子：一个学生的高考成绩，和课程老师的推荐信。而，课程老师的推荐信主要是以来该学生的课程成绩，上过那么多课的我们也应该知道，课程成绩，主要依赖课程的难易程度和学生的智力，而高考成绩我们一般只依赖智力。

这个例子我们可以看出，处处充满了假设和简化，很显然的就像课程成绩肯定还依赖我们的努力程度等等。但是我们是抽象模型，简化模型的，所以我们忽略这些次要因素（也不能说是次要因素，使我们不关心的因素），而里面的因果关系充满了我们对事物的认知。根据上面的假设，我们就可以建立一个贝叶斯网络了。

Bayes network for students finding jobs

这个图模型就很好的对例子中的描述进行了建模，我们可以很清楚的看到各个元素之间的独立性和因果性。既然事物之间的关系知道了，我们该怎么对这些关系量化呢？（这也是参数学习的本源吧）首先我们要明确的一个问题是，这个世界是概率的世界，一切事物的关系都是概率的，我们不能精确的量化之间的关系，我们只能用概率来描述这种关系的强弱。图中，我们可以看到没有父节点的节点，我们是要知道其先验概率的，这个问题中，我们要知道一个课程难易程度的概率，还有一个人智力高下的概率，这些都是统计上的。然后我们就要对剩下的因果关系进行建模了，在概率中，我们是使用条件概率来进行建模的。虽然在概率论中，条件概率并没有实际的因果性。但是这里我们赋予它因果性。下面我们给出这个例子的一些参数：

\begin{array}{|c|c|}
\hline
d^0 & d^1 \\
\hline
0.6 & 0.4 \\
\hline
\end{array}

$ p(d) $

\begin{array}{|c|c|}
\hline
i^0 & i^1 \\
\hline
0.7 & 0.3 \\
\hline
\end{array}

$p(i) $

\begin{array}{|c|c|c|}
\hline
& s^0 & s^1 \\
\hline
i^0 &0.95 & 0.05 \\
\hline
i^1 &0.2 & 0.8\\
\hline
\end{array}

$p(s|i) $

\begin{array}{|c|c|c|c|}
\hline
& g^1 & g^2 & g^3 \\
\hline
i^0,d^0 &0.3 & 0.4 & 0.3 \\
\hline
i^0,d^1 &0.05 & 0.25 & 0.7 \\
\hline
i^1,d^0 &0.9 & 0.08 & 0.02 \\
\hline
i^1,d^1 &0.5 & 0.3 & 0.2 \\
\hline
\end{array}

$ p(g \mid i,d) $

\begin{array}{|c|c|c|}
\hline
& l^0 & l^1 \\
\hline
g^1 & 0.1 & 0.9 \\
\hline
g^2 & 0.4 & 0.6 \\
\hline
g^3 & 0.99 & 0.01 \\
\hline
\end{array}

$p(i \mid g) $

根据独立性分解，我们可以得到因子图：

I-map

这样一分解，一切问题就变得简单了，本来47个变量现在一下变得很少了，而联合概率我们就可以写成：
\begin{equation}\label{1}
p(i,d,g,s,l)=p(i)p(d)p(g \mid i,d)p(s \mid i)p(l \mid g)
\end{equation}

马尔科夫网

之前说的是一些有向图，现在我们来讨论无向图。 PGM 这本书里说的主要是有些模型，我们无法使用有向图来，或者说我们无法确切的知道两个事件的因果关系。还有一个问题就是独立性条件有向图很难满足的。例如我们看图

Markov network

这个图很好的保证了 $p(a \perp c \mid b,d)$ 和 $p(b \perp d \mid a,c)$ ，但是有向图中就很难同时满足这两个条件。无向图和有向图同样十分重要的一个环节就是，因子图分解。在无向图中每一个完备子图（最大完全子图）就是一个因子图。如上图所示，我们可以看到虚线框起来的就是一个因子图。每一个因子和之前有向图的因子是非常相似的。然后联合概率就可以转化成：

\begin{equation}\label{mk}
p(a,b,c,d)=\frac{1}{\mathcal{Z}} \phi_1(D_1) \times \phi_2 (D_2) \times \cdots \cdots \times \phi_n (D_n)
\end{equation}

其中 $\mathcal{Z}$ 是划分函数：
\begin{equation}\label{pf}
\mathcal{Z}=\sum_{a,b,c,d}\phi_1(D_1) \times \phi_2 (D_2) \times \cdots \cdots \times \phi_n (D_n)
\end{equation}

这是一个很简单的例子，这里就不在深入的讲解了。我们所熟悉的，成对马尔科夫网（特别像四邻域或者八邻域的图像结构），伊辛模型和玻尔兹曼机，条件随机场等都是无向图模型里面的模板。这里只是作为了解，如果大家感兴趣可以看教材，还有很多论文。

Sequential data

我们这里关注的是 sequential data 一些问题，比如序列标注，分割等问题。这个问题初始来源于自然语言处理领域，后来图像领域作语义分割的人把这个迁移过来，效果非常好。而现在，作语义分割的基本都是使用条件随机场，这个已经成了必备的知识的，而先进的深度学习的技术只是作为这个框架的一部分来进行刻画的。好了既然这么重要，我们就从这个自然语言序列标注开始慢慢讲起吧！

HMM

一个隐马尔科夫模型是一个五元组 ${X,Y,\pi ,A,B}$ , $Y$ 表示的是隐含变量， $X$ 表示的是观测， $\pi$ 表示的是初始概率， $A$ 表示的是状态之间的转移矩阵， $B$ 表示的是状态和观测之间的关系，根据这个我们就可以定义一个隐马尔可夫模型了。隐马尔可夫模型其实是动态贝叶斯网络（ dynamic bayes network ）的的一个最简单的特例。

在序列标注领域，隐马尔科夫模型可以说是一个非常非常重要的角色。我们还是惯常使用一个经典的例子来解释这个问题（一个到处都能找到的例子）。

例子，一个人想知道另一个城市的天气，但是他不能直接观测到，他知道他朋友的每天的活动，怎么获取当地的天气？

下面我们假设，他知道几天前的某一天的天气的概率，而天气这里分为 *Y={sunny,cloudy rainy}*，朋友的活动有 *X={tennis,hiking,home}*，天气之间的变换是有一定的规律的，朋友的活动和天气也有很大的关系。

\begin{array}{|c|c|c|c|}
\hline
& sunny &cloudy &rainy \\ \hline
\pi & 0.5 &0.3 &0.2 \\
\hline
\end{array}

$\pi $

\begin{array}{|c|c|c|c|}
\hline
& sunny &cloudy &rainy \\ \hline
sunny & 0.6 &0.3 &0.1 \\ \hline
cloudy & 0.2 &0.3 &0.5 \\ \hline
rainy & 0.3 &0.4 &0.3 \\
\hline
\end{array}

$A$

\begin{array}{|c|c|c|c|}
\hline
& tennis &hiking &home \\ \hline
sunny & 0.2 &0.4 &0.4 \\ \hline
cloudy & 0.6 &0.3 &0.1 \\ \hline
rainy & 0.1 &0.2 &0.7 \\
\hline
\end{array}

$B$

这里需要注意的是每一行的概率，也就是条件概率的和为一。

根据这个我们可以得到一个状态转移图，也就是自动机。

automatic for HMM

但是我们关心的是时序上的关系，也就是说未来的通过一系列的过去的观测来推算过去的天气，这样把这个自动机变成一个时序上模型

HMM
根据这个时序模型，加上之前的一些知识，我们可以知道：
\begin{equation}\label{hme}
p(x,y\mid \theta)= p(y_1) \prod_{i} p(y_i \mid y_{i-1})p(x_i \mid y_i)
\end{equation}

这里的 $x_i,y_i$ 都是一个变量，也就是之前的 X,Y 在时序上的体现，他们的取值就是之前所表示的，之间的状态转移概率，和状态与观测之间的条件概率都是之前我们定义的。这个是什么意思呢。我们可以认为我们观测到了朋友这四天的活动情况， ${x_1,x_2,x_3,x_4}$ ，来计算这四天的天气状况$ {y_1,y_2,y_3,y_4} $。 当然，我们也可以换另外一个问题，已知这个模型，这四天朋友 ${x_1,x_2,x_3,x_4}$ 的概率是多少？ 这是两个完全不同的问题，一个是求在这个模型下，产生这个观测的最可能的状态是什么。一个是求这个模型对这个观测的适应程度。解决不同的问题，我们会有不同的算法。到这里我相信各位已经有了一个比较直观的了解了。下面我们看看对于不同的问题，我们应该使用什么算法。

前向算法

前向算法就是评估一个模型对已有观测的适应性的。什么意思呢？就是说，我给定一个模型的算有参数，现在来了观测，问这个模型产生这个观测的概率是多少呢？这个应该就是模型的适应性吧。用公式表示就是：
\begin{equation}\label{qian}
p(x \mid \theta)=\sum_y p(x,y \mid \theta)
\end{equation}

当然我们可以枚举算有的状态序列，这个规模是以状态个数为底，以时序长度没指数的大小，现在这个随着时序的增加会非常大，这个不是我们想要的结果，我们希望希望能快速的计算出这个结果，这就是前向算法了。前向算法有效地利用之前状态的的信息，可以看做是一种类似于动态规划的过程。下面我们展开这个 HMM 来看，在给定一个观测时，状态之间的关系如下图所示：

All pathes at this observation

这里面的每一条路径都可以产生我们的观测，我们这个问题就是求所有的路径的和，也就是所有的状态序列产生这个观测的和。最暴力的办法当然就是枚举每一个路径，然后求和就可以了。但是我们观察，这里是有子结构的：

sub-structure in the pathes

这个子结构可以使我们很有效的计算这个和。下面我们给出具体的计算公式：

（1）当 $t=1$ 时；

\begin{equation}\label{t1}
\alpha_t(i)=\pi(i) B(i,j)
\end{equation}

这里我们用到的就是初始概率了这里的 $\alpha_t(i)$ 表示在 $t$ 时刻，观测 $y_t=j$ 由状态 $x_t=i$ 产生的概率，这里是枚举了之前的算有的状态。

（2）当 $t =1,2,…n$ 时：

\begin{equation}\label{t2}
\alpha_t(i)=B(i,j)\sum_{k}\alpha_{t-1}(k) A(k,i)
\end{equation}

而我们想要求的 $p(x\mid \theta)$ 在这里就变成了：
\begin{equation}\label{qianx}
p(x\mid \theta)=\sum_{i}\alpha_n(i)
\end{equation}

这样我们看到之前的时间复杂度 $\mathcal{O}(N^T)$ 一下子就变成了 $\mathcal{O}(N^2 T)$ 。

维特比算法（Viterbi algorithm）

上面讲到了前向算法，但是平时我们使用最多的并不是衡量一个隐马尔可夫模型的适应性，而是在一个给定的马尔可夫模型中，找到一组观测对应的最可能的状态。这个可以看做是解码的过程。怎么快捷有效的解码这个才是我们最关心的。当然我们也可以像之前，我们所说的那样穷举状态空间来进行求解，显然我们并不像这么做。那怎么办呢？

之前我们发现了路径中的子结构，那这个问题是否也使用这个子结构呢？如果使用该怎么求解呢？

我们来看一下实例图：

The optimal path

如果所示，该路径是最优路径也就是说，这个路径的概率是最大的，如果这个路径的概率是最大的也就是 $\max_i v_n(i)$ ，那么如果这个最终的节点是最大的，在这条路上的每一个节点都应该是当前最大的。所以这个也可以使用之前的子结构，不过要作稍微的改动。

1）当 $t=1$ 时；

\begin{equation}\label{v1}
v_t(i)=\pi(i) B(i,j)
\end{equation}

这里的初始的节点的值是没有什么变化的。

（2）当 $t =1,2,…n$ 时：

\begin{equation}\label{v2}
v_t(i)=\max_k B(i,j)v_{t-1}(k) A(k,i)
\end{equation}
这里每一步都求之前的最大值，但是我们要知道这个最大值是来自哪一个节点，所以得定义一个结构来记录每一步指向的父节点：
\begin{equation}\label{v3}
p_t(i)=\arg \max_k B(i,j)v_{t-1}(k) A(k,i)
\end{equation}

而我们想要求的 $\max p(x\mid y, \theta)$ 在这里就变成了：
\begin{equation}\label{vetbi}
\max p(x\mid y,\theta)=max_{i} v_n(i)
\end{equation}

然后我们可以回溯的 $p_t$ 这个表来获取，我们求得的最大概率的状态序列。

前向后向算法

但是事实情况是这样的，我们大部分情况是很难知道模型的参数。就是初始概率，转移概率还有条件概率，我们是很难知道的。一般情况，我们知道的都是经过一段时间的观测，得到状态和观测对。我们需要通过学习来获得整个模型的参数。那问题就来了，这个模型我该怎么训练呢？怎么回去这一大对概率呢？

总是有牛人提出一些有效地办法来解决问题，这就是大名鼎鼎的前向- 后向算法，之前我们已经大致知道了前向算法，下面我们来介绍一下后向算法吧。

后向算法

后向算法和前向算法是很相似的，但是后向算法是从后面向前计算的。前向算法就是计算某一个状态确定，之前的所有状态能产生对应的观测对的概率，而后向算法正好相反，计算的是一个状态固定，之后的所有状态产生对应的观测的概率。具体的计算过程就是：

（1）当 $t=n$ 时，

\begin{equation}\label{ba}
\beta_t(i)=1
\end{equation}

（2）当 $t=n-1,….1$ 时：
\begin{equation}\label{bb}
\beta_t(i)=B(i,j) \sum_k A(i,k) \beta_{t+1}(k)
\end{equation}

这里的观测是 $y_t=j$ ，这样我们就可以递归的计算整个时序图的后向结果了。

下面我们还是简单提一下，其实这个前向-后向算法可以说是大名鼎鼎的 EM 算法的一个特例。这话可不是我说的，是发明 EM 算法的人说的，虽然这个前向后向算法的提出是要比 EM 算法早的，但是 Dempster 在它的论文里就是这样么说的，后来还有大牛 Jelinek 说就是这样的。那我们就信了吧。 EM 算法就不多说了，我们大致知道了这是一个的待求解的过程就可以了。下面我们来看看这个算法的具体流程吧。

之前我们已经通过前向算法，后向算法，获得了相应的 $\alpha,\beta $，我们先来定义一个概率来表示某一时刻是由某个特定的状态产生其对应观测：
\begin{equation}\label{gamma}
\gamma_t(i)=p(y_t=i \mid x,\theta)=\frac{p(y_t=i,x \mid \theta)}{p(x \mid \theta)}
\end{equation}

然后联想到之前的定义，我们可以很容易的得到：

\begin{equation}\label{gamma1}
\gamma_t(i)=\frac{\alpha_t(i) \beta_t(i)}{\sum_i \alpha_t(i) \beta_t(i)}
\end{equation}

现在我们知道某一个时刻的状态的概率了，那我们肯定还要知道两个时刻之间状态转移的概率，这个概率有那么点抽象，我们来看看一个形象的解释吧。

Forward-Backward algorithm

看到上图，我们大致就可以定义一个在某一时刻，某一状态转移到另一状态的概率：

\begin{equation}\label{xi}
\xi_t(i,j)=p(y_t=i,y_(t=1)=j \mid x,\theta)=\frac{p(y_t=i,y_{t+1}=j,x \mid \theta)}{p(x \mid \theta)}
\end{equation}

根据上图，我们就可以得出：
\begin{equation}\label{xi2}
\xi_t(i,j)=\frac{\alpha_t(i) A(i,j) B(j,x_{t+1}) \beta_{t+1}(j)}{\sum_i \sum_j \alpha_t(i) A(i,j) B(j,x_{t+1}) \beta_{t+1}(j)}
\end{equation}

上面这两个参数是有关系的：
\begin{equation}\label{gux}
\gamma_t(i)=\sum_j \xi_t(i,j)
\end{equation}

我们求了这么几个参数，但是这些参数到底是什么意思呢？下面我们解释一下：
$\sum_t \gamma_t(i)$ 表示状态 $i$ 的所有转出数，
$\sum_t \xi_t(i,j)$ 表示状态 $i$ 转移到状态 $j$ 的数目。

既然知道了这个，我们就可以得到，我们更新后的 $\pi,A,B$ 了。
\begin{equation}\label{pi}
\pi(i)=\gamma_1(i)
\end{equation}

\begin{equation}\label{a}
A(i,j)=\frac{\sum_t \xi_t(i,j)}{\sum_t \gamma_t(i)}
\end{equation}

\begin{equation}\label{b}
B(i,v_k)\frac{\sum_{t \ S.t. x=v_k } \gamma_t(i)}{\sum_t \gamma_t(i)}
\end{equation}

然后我们就可以迭代求解了，因为之前我们求解 $\alpha,\beta$ 都用到了 $\pi,A,B$ 。这样就可以求得局部最优解了。

到这里 HMM 就告一段落了，对于 HMM 一些应用，我们基本上都知道例如。

最大熵原理马尔科夫模型

这里的模型主要是：

Max entropy hidden markov network

这里就是最大熵原理加上隐马模型。这里主要关注的是最大熵原理的对偶问题和最大熵模型的极大似然解是一样。这里用到了改进的迭代尺度法，都为条件随机场建立了良好的基础。

条件随机场

条件随机场，是 Laffety 在2001年提出的，这个可以说是在序列标注领域是一个很大的进步。 Laffety 分析了之前模型面临的问题：（1）最重要的问题就是之前的模型都是产生式模型，也就是说之前的算法都是对联合概率分布进行建模的，也就是说之前的算法要对所有的观测进行建模，显然这个是很困难的，因为这个是基本不太可能的。（2）还有一个问题就是，标记偏置问题，因为不同的状态的出度的是不一致的，然后因为局部归一化导致这个标记偏置了。

然后作者说了一大堆别的模型的缺点提出了条件随机场，首先确定的是条件随机场是一个判别式模型，他是在给定一组输入变量，输出变量构成马尔科夫随机场的这么一个模型。 Laffety 最先提出来的是链式条件随机场，那我们就从链式条件随机场讲起吧。

定义:条件随机场
设 $X$ 和 $Y$ 是随机变量， $p(Y \mid X)$ 是在给定 $X$ 的条件下 $Y $ 的条件概率分布，若随机变量 $Y$ 构成一个无向图 $G={V,E}$ 表示的马尔科夫随机场，即
$$P(Y_v \mid X,Y_w,w \neq v)=p(Y_v \mid X,Y_w,w \sim v) $$
对任意的节点成立，则称条件概率分布 $p(Y \mid X)$ 为条件对机场。

需要注意的是这里的 $Y_v,Y_w$ 表示的是节点 $v,w$ 对应的随机变量。 $w \sim v$ 表示这两个节点右有边链接。

根据这个，我们给出线性链式条件随机场：

定义：线性链式条件随机场
设 $X=(X_1,X_2,…,X_n),Y=(Y_1,Y_2,…,Y_n)$ 均是线性链表示的随机变量序列，若在给定 $X$ 的条件下 $Y$ 的条件概率分布 $p(Y \mid X)$ 构成的条件随机场满足：

$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})$

则称 $P(Y \mid X)$ 是线性链式条件随机场。

下面我们来看一下这个用图怎么表示：

Chain conditional random field
这个跟之前的隐马尔可夫模型和最大熵马尔可夫模型都有了很到的区别，首先就是这是一个判别式模型，是在最大化特定的观测下的状态序列概率，也就是条件概率，而且状态之间变成了马尔科夫随机场，也不再是之前的动态贝叶斯网络。这些都符合作者对问题的分析，和改正。观测序列的结构这里没有给出，因为这个是和数据有很大关系的，可以说是基于应用的，不同的数据可能会有不同的结构。

下面我们着重来看一下这个模型是怎么参数化的。

条件随机场的参数化

我们有了之前的定义，加上我们对马尔科夫网的了解，我们大致知道，怎么去因子化一个马尔科夫网，然后怎么用吉布斯能量去表示一个一个网络的能量。下面我们给出一个条件随机场的因子化的定理：

定理：线性链式条件随机场的参数化
设 $P(Y \mid X)$ 为线性链式条件随机场，则在随机变量 $X$ 取值为 $x$ 的条件下。随机变量 $Y$ 取值为 $y$ 的条件规律具体如下：
$$p(y \mid x)=\frac{1}{\mathcal{Z}(x)} \exp \left(\sum_{i,k} \lambda_k t_k (y_{i-1},y_i,x,i)+\sum_{i,l} \mu_l s_l(y_i,x,i)\right)$$
其中：
$$\mathcal{Z}(x)=\sum_y \exp \left(\sum_{i,k} \lambda_k t_k (y_{i-1},y_i,x,i)+\sum_{i,l} \mu_l s_l(y_i,x,i)\right)$$

这个公式里面 $t_k,s_l$ 是特征函数， $\lambda_k,\mu_l$ 是对应的权值， $\mathcal{Z}(x)$ 是归一化因子，求和是在所有的输出序列上进行的，这个可能就是避免标签偏置的过程，不在是局部归一化，而采用全局的归一化。

-

但是这个参数化之后，看着还是满复杂的，我们想把那两个项简化成一个同一的表达形式，以便于后面的理解。我们这里首先来同一符号，之前的特征函数我们这里都是用 $f_k$ 表示，那么这里的特征函数的个数就是之前的和 $K=K_1+K_2$ ：

\begin{equation}\label{fddtd}
f_k(y_{i-1},y_i,x,i)=
\begin{cases}
t_k(y_{i-1},y_i,x,i),&k=1,2,…,K_1 \\
s_l(y_i,x,i), & k=K_1+l;l=1,2…,K_2
\end{cases}
\end{equation}

之前我们也看到，参数只和特征函数函数的个数有关，和参数的个数是没有关系的，而且我们关心的也是求和之后的结果，所以我们可以先对特征函数求和：
\begin{equation}\label{f}
f_k(y,x)=\sum_{i=1}^nf_k(y_{i-1},y_i,x,i),k=1,2,…,K
\end{equation}

这样这个特征函数就可以写成一个列向量的形式了，参数同样也可以写成列向量的形式：

\begin{equation}\label{wttk}
w_k=
\begin{cases}
\lambda_k, &k=1,2,…,K_1 \\
\mu_l, &k=K_1+l;l=1,2…,K_2
\end{cases}
\end{equation}

然后我们用列向量来表示特征值和参数：
$$w=(w_1,w_2,…,w_K)^T$$
$$F(y,x)=(f_1(y,x),f_2(y,x),…,f_K(y,x))$$

写成了向量的形式，计算起来就很简单了，下面我们给出之前的公式一个向量形式的表示：
\begin{equation}\label{fw}
p_w(y \mid x)=\frac{1}{\mathcal{Z}_w(x)} \exp (w \cdot F(y,x))
\end{equation}

\begin{equation}\label{ftw}
\mathcal{Z}_w(x)=\sum_y \exp (w \cdot F(y,x))
\end{equation}

-

下面还有一种我们比较喜欢，另一种形式的简化，之前的都是对节点进行求和，然和写成列向量的形式，现在我们对特征函数求和，这样每个求和之后的结果都是一个 $\mid y \mid * \mid y \mid$ 的矩阵，这样使用起来是非常简单的。之前我们对 $y$ 求和，但是显示中，我们关注的是时序数据，也就是安，我们之前 HMM 中提出那样，每一个时序片之间，我们也可以枚举 $y$ 的状态，形成一个链路图。

Time spread form

我们想知道每一堆联通节点之间，所有状态取值之间的链接权值，以便我们在解码的时候找到最大概率的路径，即在给定观测下的最优状态序列。既然了解了这个大致是什么原理，那我们来看一下，具体是怎么定义的吧。

我们来定义一个矩阵形式的 $M_i(x)$ 表示在时序 $i$ 时， $i-1$ 所有状态取值到该时刻所有状态取值的一个转移概率矩阵（这个类似我们之前在 $HMM$ 中定义的转移矩阵 $A \bigodot (1_{1*3} \bigotimes B(i,x_i)$ ，不过这里的转移矩阵是可以随时序变化的）。
\begin{equation}\label{tm}
M_i(x)=[M_i(y_{i-1},y_i \mid x)]_{\mid y \mid * \mid y \mid}
\end{equation}

\begin{equation}\label{mi}
M_i(y_{i-1},y_i \mid x)=\exp \left(\sum_k w_k f_k(y_{i-1},y_i,x,i)\right)
\end{equation}

这里之前的概率，我们就可以写成：
\begin{equation}\label{pw2}
p_w(y \mid x)=\frac{1}{\mathcal{Z}_w(x)} \prod_i M_i(y_{i-1},y_i \mid x)
\end{equation}

这里的归一化因子就是：
\begin{equation}\label{guiyi}
\mathcal{Z}_w(x) =\sum \bigotimes_i M_i(x)
\end{equation}

说了这么多，我们都没有谈到概率，都没有谈到在给定观测，某一状态取特定值的概率是多少？两个特定状态之间的转移概率是多少？这些到这里，我们都没有给出，在条件随机场中，我们并没有刻意的去生命某个概率到底是什么，但是，应不应该有和隐马尔可夫模型相似的参数。下面我们来看到底会不会有呢？

概率的计算

这里的概率计算并不是可以直接得到概率，但是我们引入和隐马一样的计算方式，来计算在给定观测下的概率参数。

前向-后向算法

这里还是沿用之前的符号 $\alpha_i(x)$ 表示在 $i$ 时刻的前向结果， $\beta_i(x)$ 表示 $i$ 时刻的后向结果。

这里需要注意的是 $\alpha_0(x)$ 的取值，因为这个是我们认为加入的节点，所以，这个并没有什么意义，但是这个也要是向量形式，只是这里的向量是在某一个节点为1就可以了，之后的递推关系是;
\begin{equation}\label{alpha}
\alpha_i^T(x)=\alpha_{i-1}^T M_i(x)
\end{equation}

同样的 $\beta_0(x)$ 也是需要注意一下，因为这里她也是没什么意思的，只要是在每一停止位置为1就可以了，其他的都为零，其递推关系如下：
\begin{equation}\label{beta}
\beta_i(x)=M_{i+1}(x) \beta_{i+1}(x)
\end{equation}

这里同样有之前，我们定义的那个关系：
\begin{equation}\label{gx}
\mathcal{Z}(x)=\alpha_n^T \cdot \mathbf{1}=\mathbf{1}^T \cdot \beta_1^T(x)
\end{equation}

下面我们进入到正题，就真个模型的该理财的计算，包括一些统计量的获取。

\begin{equation}\label{pypx}
p(Y_i=y_i \mid x)=\frac{\alpha_i^T(y_i\mid x) \beta_i(y_i \mid x)}{\mathcal{Z}(x)}
\end{equation}

\begin{equation}\label{pyx}
p(Y_{i-1}=y_{i-1},Y_i=y_i \mid x)=\frac{\alpha_{i-1}^T(y_{i-1}\mid x) M_i(y_{i-1},Y_i\mid x) \beta_i(y_i \mid x)}{\mathcal{Z}(x)}
\end{equation}

这里面 $\alpha_i^T(y_i\mid x)$ 代表之前定意的 $\alpha_i^T(x)$ 这个向量的一个取值，以此类推，后向的结果也是这个样子的。

这里需要注意的是，这个归一化是全局的，之前隐马尔科夫模型中这个地方的归一化是局部的。

这里我们还要引入特征函数 $f_k$ 关于条件概率的期望的计算：
\begin{equation}\label{wfjjk}
\begin{split}
\mathbb{E}_{p(y \mid x)}[f_k] & =\sum_y p(y \mid x) f_k(y,x) \\
& = \sum_i \sum_{y_{i-1},y_i} f_k(y_{i-1},y_i,x,i) \frac{\alpha_{i-1}^T(y_{i-1}\mid x) M_i(y_{i-1},Y_i\mid x) \beta_i(y_i \mid x)}{\mathcal{Z}(x)}
\end{split}
\end{equation}

如果引入经验分布 $\widetilde{p}(x)$ ，那关于联合概率的期望：

\begin{equation}\label{wfk}
\begin{split}
\mathbb{E}_{p(y ,x)}[f_k] & =\sum_{x,y} p(y , x) f_k(y,x) \\
& =\sum_x \widetilde{p}(x) \sum_i \sum_{y_{i-1},y_i} f_k(y_{i-1},y_i,x,i) \frac{\alpha_{i-1}^T(y_{i-1}\mid x) M_i(y_{i-1},Y_i\mid x) \beta_i(y_i \mid x)}{\mathcal{Z}(x)}
\end{split}
\end{equation}

到这我们大概就知道怎么计算概率，期望什么的了。具体过程就是，来个一个观测，我们前向扫描一遍计算出 $\alpha_i(x)$ ，然后在通过一个后向扫描计算出 $\beta_i(x)$ ，然后根据上面的公式，我们就可以计算出我们想要的概率，和期望了。

学习算法

我们比较关注的还是，怎么学习一个模型的参数，也就是说，给定一系列的状态观测序列，我们希望找到最合适的模型来对这个进行建模，这里主要涉及的参数就是每一个特征函数对应的 $w_k$ 。既然知道了目的，那我们需要重要有个损失函数吧。

这里是根据和最大熵原理一样定义一个对数似然函数，通过极大化对数似然函数来获得我们参数。
\begin{equation}\label{lw9}
\mathcal{L}(w)=\mathcal{L}_{\widetilde{p}}(p_w)= \log \prod_{x,y} p_w(y \mid x)^{\widetilde{p}(x,y)}=\sum_{x,y} \widetilde{p}(x,y) \log p_w(y \mid x)
\end{equation}

根据之前的定义，我们可以把这个函数化解为：

\begin{equation}\label{ljw}
\begin{split}
\mathcal{L}(w) & =\sum_{x,y} \widetilde{p}(x,y) \log p_w(y \mid x) \\
& =\sum_{x,y}\left[ \widetilde{p}(x,y)\sum_k w_k f_k(y,x) -\widetilde{p}(x,y) \log \mathcal{Z}_w(x) \right]\\
& = \sum_{x,y} \sum_k w_k f_k(y,x) - \sum_x \log \mathcal{Z}_w(x)
\end{split}
\end{equation}

这里推导的过程在最大熵原理中都有介绍，我在这里就不赘述了。我们要学习的是 $w_k$ ，我们使用的都是梯度上升的办法，这里给出\textcolor{red}{改进的迭代尺度法}中，每一个参数 $w_k$ 的变化率 $\delta_k$ 的计算方式：

（1） $k \in [1,K_1]$
\begin{equation}\label{tp}
\begin{split}
\mathbb{E}_{\widetilde{p}}[t_k] & =\sum_{x,y} \widetilde{p}(x,y)\sum_i t_k(y_{i-1},y_i,x,i) \
& =\sum_{x,y}\widetilde{p}(x) p(y \mid x) \sum_i t_k(y_{i-1},y_i,x,i) \exp (\delta_k T(x,y))
\end{split}
\end{equation}

（1） $k=K_1+l \in [K_1 +1,K]$
\begin{equation}\label{tp1}
\begin{split}
\mathbb{E}_{\widetilde{p}}[s_l] & =\sum_{x,y} \widetilde{p}(x,y)\sum_i s_l(y_{i-1},y_i,x,i) \
& =\sum_{x,y}\widetilde{p}(x) p(y \mid x) \sum_i s_l(y_{i-1},y_i,x,i) \exp (\delta_k T(x,y))
\end{split}
\end{equation}

这里的 $T(x,y)$ 就是所有的特征总和：
\begin{equation}\label{tr}
T(x,y)=\sum_k f_k(x,y)=\sum_k \sum_i f_k(y_{i-1},y_i,x,i)
\end{equation}

根据上面的两个公式，我们可以求得所有的 $\delta_k$ ，然后根据梯度上升的办法：
\begin{equation}\label{tidu}
w_k =w_k+\delta_k
\end{equation}
直到收敛。

之前的算法的 $T(x,y)$ 用一个常数代替，只要在保证
\begin{equation}\label{s}
\forall(x,y) S-T(x,y) \geq 0
\end{equation}

这里的改进使用的是 $\max_y T(x,y)$ 。

到这里，我们就大致知道，怎么参数学习的了，但是问题还有一个就是我们在这里只给出了 $\delta_k$ 的求解方程，并没有给怎么求解，一些求解的细节这里也没有。因为求解的算法比较多，这里就不在一一赘述了，主要有拟牛顿法（BFGS）等，这里就不说了，详情请看李航老师的《统计学习方法》。

学习算法，我们已经给出了，下面我们来看看条件随机场是怎么预测的吧。

条件随机场的预测

预测就是在给定观测的情况下，获得割爱率最大化时的状态序列，形式化的表示就是：
\begin{equation}\label{yuce}
\begin{split}
y* & =\arg \max_y p_w(y \mid x) \
& =\arg \max_y \frac{\exp (w \cdot F(y,x))}{\mathcal{Z}_w(x)} \
& =\arg \max_y (w \cdot F(x,y))
\end{split}
\end{equation}

这里我们可以参考，之前的一个简化方式 $M_i(x)$ 来进行计算，但是这里直接计算指数上的结果，所有这里没有直接使用,而是使用类似的办法。当然这里的核心还是 Viterbi 算法。

上面的公式我们可以改写一下，因为上面的公式中没有涉及到实训问题，这样我们就没办法使用维特比算法了，我们要把上面的目标返程改写为，具有时序的形式；
\begin{equation}\label{shixu}
\max_y \sum_i w \cdot F_i(y_{i-1},y_i,x)
\end{equation}
这里的 $F_i(y_{i-1},y_i,x)$ 表示的是：
\begin{equation}\label{fs}
F_i(y_{i-1},y_i,x)=(f_1(y_{i-1},y_i,x,i),f_2(y_{i-1},y_i,x,i),…,f_K(y_{i-1},y_i,x,i))^T
\end{equation}

然后我们就可以使用维特比算法了，我们还是沿用之前的记号 $v_i(j)$ 表示在 i 时刻的状态取值是 $j$ 的值， $p_i(j)$ 来记录之后递归时的路径。

（1）当 $i=1$ ：

\begin{equation}\label{v001}
v_i(j)=w \cdot F_1(y_0=start,y_i=j,x)
\end{equation}

（2）当 $i=2,..,n$ 时：

\begin{equation}\label{v8}
v_i(j)=\max_{1 \leq l \leq \mid y \mid }[v_{i-1}(l) + w \cdot F_1(y_{i-1}=l,y_i=j,x)]
\end{equation}

\begin{equation}\label{v200}
p_i(j)=\arg \max_{1 \leq l \leq \mid y \mid }[v_{i-1}(l) + w \cdot F_1(y_{i-1}=l,y_i=j,x)]
\end{equation}

这样我们就可以求出最终的结果了：
\begin{equation}\label{vf}
\max_y \sum_i w \cdot F_i(y_{i-1},y_i,x)=\max_{1 \leq l \leq \mid y \mid } v_n(l)
\end{equation}

相应的状态序列，就可以直接回溯 $p_n$ 就可以了。

整个条件随机场就告一段落了。有一个网站是这方面很全的，crf这上面有很多资料，可以关注。还有就是李航老师的《统计学习方法》，还有[hmm]](http://www.52nlp.cn/hmm-learn-best-practices-one-introduction)，还有就是 Lafferty 的原始论文。图像这边最早的是 Xuming He 的”Multiscale Conditional Random Fields for Image Labeling”，还有 Plath的”Multi-class image segmentation using Conditional Random Fields and Global Classfication” 。这个之后要好好看看，看看这个东西是怎么应用的。