层次化的隐马尔可夫模型

在自然语言处理等应用中，由于处理序列具有递归特性，尤其当序列长度比较大时，HMM的复杂度将会急剧增大，因此层次化隐马尔可夫模型（HHMM）被提出了。

我们知道HMM是由两个随机过程构成的，而HHMM是由多层随机过程构成的。在HHMM中每个状态就是一个独立的HHMM，因此一个HHMM的状态就产生一个观察序列，而不是一个观察符号。HHMM通过状态递归地产生观察序列，一个状态可以激活下层状态中的某个状态，而被激活的状态又可以再激活下层的状态，直至到达某个特定的状态，这一递归过程结果。该特定状态成为生产状态，只有生产状态才能通过常规的HMM机制，即根据输出符号的概率分布产生可观察的输出符号。不直接产生可观察符号的隐藏状态称作内部状态，不同层次之间的状态转移叫垂直转移，同一层次上状态之间的转移叫做水平转移。特殊的终止状态负责控制转移过程返回到激活该层状态转移的上层状态。

这一递归过程将形成一个生产状态序列，而每个生产状态生成一个观察输出符号，因此生产状态序列将为顶层状态生成一个观察输出序列，HHMM的树状结构如图所示：

HHMM的树状结构

最上面的q1就是一个能产生一个观察序列的HHMM状态，而q1产生的这个结构也是一个独立了HHMM，图中画双圈的就是终止状态，用于控制转移过程返回到激活该层状态的上层状态。其它状态为内部状态。终止状态与生产状态不同，图中并没有画出生产状态。

为了避免误解，我特意找了另一张HHMM的图对比着来看：

HHMM

图中画双圈的是终止状态，能够输出符号的是生产状态，不能输出符号且不是终止状态的被叫做内部状态。

像HMM一样，HHMM中也有三个基本问题，第一个就是快速地计算观察序列的概率，第二个就是求解模型最有可能的状态序列，第三个就是在给定一个HHMM的结构和一个或多个观察序列的条件下，估计模型的最优参数。

马尔可夫网络（马尔可夫随机场）

前面其实是讲过马尔可夫模型的，马尔可夫网络不同于马尔可夫模型，我们来回顾一下前面的图：

常见的概率图模型

我们知道马尔可夫模型和隐马尔科夫模型HMM都是有向图模型，而马尔可夫网络是无向图模型。

马尔可夫网络和贝叶斯网络有类似之处，也可用于表示变量之间的依赖关系，但它又与贝叶斯网络有所不同。一方面它可以表示贝叶斯网络无法表示的一些依赖关系，如循环依赖；另一方面，它不能表示贝叶斯网络能够表示的某些关系，如推导关系。

一个简单的无向图

马尔可夫网络是一组有马尔可夫性质的随机变量的联合概率分布模型，由一个无向图G（如上图）和定义在G上的势函数组成。

无向图的每个顶底表示一个随机变量，每条边表示两个随机变量之间的依赖关系。

首先简单说一下什么是子图，假设有两个图，如果第二个图的顶点都是第一个图的顶点，第二个图的边也都是第一个图的边，那么第二个图就是第一个图的子图。

如果一个子图任意两个顶点都有边相连，那么这个子图就是一个完全子图，一个完全子图又称为一个团，一个团的完全子图叫子团。

因为图是无向的，所以我们不能用条件概率对模型进行参数化，而是使用团势能函数或简称势函数进行参数化，每个团都对应一个势函数，表示团的一个状态。

我们的目的是什么？是对无向图进行参数化，得到概率分布，进而描述出整个马尔科夫网络。拿上面的那个简单的无向图举例，这个图可以拆成两个团，一个是XC1 = {x1, x2}，另一个是XC2 = {x1, x3, x4}，这个马尔可夫网络H的分布概率PΦ(x1, x2, x3, x4)可以由这两个团的团势能函数Φ(XC)进行因子化，PΦ(x1, x2, x3, x4)可以看做是这个马尔可夫网络H的一个吉布斯分布：

Z是归一化常量，称为划分函数，不重要。

那然后我们只需要确定每个团的团势能函数Φ(XC)了。我们一般将团势能函数Φ(XC)定义为：Φ(XC) = exp{-E(XC)}，其中-E(XC)叫做团XC的能量函数。

这样我们就得到了整个图模型的吉布斯分布。而且因为式子里是连乘，我们可以通过取对数，将因子化的乘积运算转变为加法运算：

最大熵模型

前面讲熵的时候我们就提到过最大熵模型，它的基本原理是：在只掌握关于未知分布的部分信息的情况下，符合已知知识的概率分布可能有多个，但使熵值最大的概率分布最真实的反映了事件的分布情况，因为熵定义了随机变量的不确定性，当熵最大时，随机变量最不确定，最难准确地预测其行为。也就是说，在已知部分信息的前提下，关于未知分布最合理的推断应该是符合已知信息最不确定或最大随机的推断。

最大熵模型的推导比较复杂，这里尽量不列公式，而是侧重于把原理讲清楚。

这里我们先引入特征的概念，简单的说，就是一个待消歧问题可能的候选结果与上下文信息的一个对应关系。就是在怎样的上下文条件下，这个待消歧问题的结果是什么。

最大熵模型说，在已知部分信息的前提下，关于未知分布最合理的推断应该是符合已知信息最不确定或最大随机的推断，实际上就是下面这个式子：

首先式子左侧的是条件概率，a就是『待消歧问题的结果』，b就是『上下文条件』，这个条件概率就是最大熵模型所要描述的概率分布，即知道在特定上下文条件下，某待消歧问题的结果。

然后式子的右侧就是所谓的『最不确定或最大随机的推断』了，我们选择所建模型中所有与已知样本中的概率分布相吻合的概率分布中熵最大的推断作为最终的结果，P就是这些符合条件的模型的集合。

我们建的模型中p(b)的概率分布必须符合已知训练样本中的概率分布，所以我们直接代入已知训练样本中的概率分布，也即式子中带了估计符号的p(b)。

其实上面那个式子就是我们需要求最大值的目标函数，接下来的问题就是如何确定所建模型中所有与已知样本中的概率分布相吻合的概率分布的集合P。

最大熵模型也说，在已知部分信息的前提下，关于未知分布最合理的推断应该是符合已知信息最不确定或最大随机的推断，那什么叫做『符合已知信息』？

符合已知信息也即，所建立模型的概率分布应该与已知样本中的概率分布相吻合（这里用的是联合概率分布），而我们通过所建立模型中『特征』的期望值和已知样本中『特征』的期望值作比较。如果特征对于模型是有用的，那这两个期望值应当是相等的。

而且我们往往选择不止一个特征，比如，我们选取k种在建模过程中对输出有影响的特征，分别表示出这k种特征下所建立模型中『特征』的期望值和已知样本中『特征』的期望值，
令其相等，那么也就相应的产生了k个约束条件，符合k条已知信息。

这样，问题就变成了在满足k个约束条件下求解目标函数的最优解的问题，而拉格朗日乘子法可以用于解决这一问题。也即如下式：

接下来是最大熵模型的训练，最大熵模型训练的任务就是选取有效的特征f以及权重λ。由于可以利用歧义点所在的上下文信息（如词形、词性、窗口大小等）作为特征条件，而歧义候选往往也有多个，因此各种特征条件和歧义候选可以组合成很多特征函数，必须对其进行筛选。

比如从候选特征集中选择那些训练数据中出现频次超过一定阈值的特征，或者利用互信息作为评价尺度从候选特征集中选择满足一定互信息要求的特征等等。

而对于权重参数λ，最开始的训练方法是通用迭代算法（Generalized Iterative Scaling，GIS），GIS实际上是一个典型的期望最大化算法（EM），简单的说，就是在第零次迭代时，在遵循限制条件的前提下任意的初始化参数λ，然后用第N次迭代的模型来估算训练数据中的分布。如果超过了实际的，就把相应的参数减小，否则，将他们变大。重复这个过程直到收敛。

GIS算法每次的迭代时间都很长，需要迭代很多次才能收敛，而且不太稳定，所以在实际应用中很少有人使用。改进迭代算法IIS（Improved Iterative Scaling）等，在GIS的基础上进行了优化，不过计算量仍然非常巨大。

最大熵马尔可夫模型

最大熵马尔可夫模型（maximum-entropy Markov model，MEMM）又称条件马尔可夫模型（conditional Markov model，CMM）。它结合了隐马尔可夫模型和最大熵模型的共同特点，被广泛应用于处理序列标注问题。

McCallum认为，在HMM模型中存在两个问题，一个是，在很多序列标注任务中，尤其是不能枚举观察输出时，需要用大量的特征来刻画观察序列。比如识别一个公司名的时候，除了通过单词，还要考虑到大写字母、结尾词、词性、格式、在文本中的位置等。也就是说，我们需要用特征对观察序列输出进行参数化。

然后是，在很多自然语言处理任务中，需要解决的问题是在已知观察序列的情况下求解状态序列，HMM采用生成式的联合概率模型P(ST,OT)来求解这种概率问题，这种方法不适合处理用很多特征描述观察序列的情况。为此，MEMM直接采用条件概率模型P(ST|OT)（所以MEMM不是一种生成式模型），从而使观察输出可以用特征表示，借助最大熵模型进行特征选取。

下图展示了HMM和MEMM的区别：

HMM与MEMM依存图对照

在上一篇我们说过HMM有三个假设：

• 有限历史性假设：也即一阶马尔可夫模型，认定t时刻出现的状态只与t-1时刻的状态有关
• 齐次性假设：假定P(s(i+1)|si)=P(s(j+1),sj)
• 输出独立性假设：假定输出仅与当前状态有关

其中包括输出独立性假设，认为当前时刻的观察输出只取决于当前状态，而在MEMM中，当前时刻的观察输出还可能取决于前一时刻的状态，MEMM解决了HMM输出独立性假设的问题。实际上，MEMM也舍弃了齐次性假设，不再用生成式的联合概率模型P(ST,OT)来求解，而是直接采用条件概率模型P(ST|OT)。

假设已知观察序列O1O2...OT，要求解状态序列S1S2...ST，并使条件概率P(S1S2...ST|O1O2...OT)最大。在MEMM中，将这一概率因子化为马尔可夫转移概率，从上面的图中也可以看出，在MEMM中，当前时刻的状态St取决于前一时刻的状态S(t-1)和当前时刻的观察输出Ot，所以：

这样，MEMM中的MM有了，接下来是ME，我们还记得上一篇讲最大熵模型的时候，讲到，最大熵模型解决的是给定上下文条件下，获得待消歧问题结果的问题，那么在现在情况下，前一时刻的状态S(t-1)和当前时刻的观察输出Ot就是上下文，而当前时刻的状态St就是待消歧问题，所以我们依照这个思想通过最大熵分类器建模：

前面讲过最大熵模型可以通过GIS来进行求解，GIS是一种EM算法，HMM中用于参数估计的前后向算法也是一种EM算法，在这里，前向后向算法修改后可用于MEMM的状态转移概率估计，这里具体的计算方法较为复杂，还用到了维特比算法的思想，这里不再深入讲解。

MEMM是有向图和无向图的混合模型，其主体还是有向图框架，与HMM相比，MEMM最大的优点在于它允许使用任意特征刻画观察序列，因为在MEMM里，处理观察序列的实际上是最大熵模型的套路，最大熵模型在推导时就考虑了处理多种特征的情况。

MEMM的缺点在于存在标记偏置问题（label bias problem），MEMM解决了HMM输出独立性假设的问题，但是只解决了观察值独立的问题，而状态之间的假设--有限历史性假设，则是标注偏置问题产生的根源。

什么是标注偏置问题？比如这样的状态转换概率分布：

路径1-1-1-1的概率：0.40.450.5=0.09
路径2-2-2-2的概率：0.018
路径1-2-1-2的概率：0.06
路径1-1-2-2的概率：0.066

由此看来，最优的路径是1-1-1-1，但是实际上，状态1偏向于转移到状态2，而状态2总倾向于停留在状态2，这就是所谓的标注偏置问题，由于分支数不同，概率的分布不均衡，导致状态的转移存在不公平的情况。条件随机场CRF则解决了标注偏置问题，是进一步优化。

这里给出HMM、MEMM、CRF的对比图：

HMM

可以清晰的看到HMM的有限历史性假设（认为Yt只取决于Y(t-1)）和输出独立性假设（认为Xt只取决于Yt）。

MEMM

MEMM克服了HMM的输出独立性假设，不再认为Xt只取决于Yt。但是仍然存在有限历史性假设，认为Yt只取决于Y(t-1)。

CRF

CRF模型解决了标注偏置问题，去除了HMM中两个不合理的假设（有限历史性假设、输出独立性假设），当然，模型相应得也变复杂了。

条件随机场

条件随机场（conditional random fields）由J.Lafferty提出，是一种典型的判别模型，就是对于给定的输出标识序列Y和观测序列X；条件随机场通过定义条件概率P(Y|X)，而不是联合概率分布P(X,Y)来描述模型。CRF也可以看做一个马尔可夫随机场（无向图模型、马尔可夫网络）。

我们先给出一张更清晰的CRF的链式结构图：

CRF的链式结构图

如果以观察序列X为条件，条件随机场中，每一个随机变量Yv都满足以下马尔可夫特性：

其中，w~v表示两个结点在图中是临近节点。也即，就像前面所提到的，在条件随机场中，有限历史性假设也被舍弃了，Yt不再只取决于前一时刻的临近节点Y(t-1)，CRF统计了全局概率，在做归一化时，考虑了数据在全局的分布，而不是仅仅在局部归一化，是全局最优的解，这样就解决了MEMM中的标记偏置的问题。

参考了标注偏置问题(Label Bias Problem)和HMM、MEMM、CRF模型比较，举一个例子，对于一个标注任务『我爱北京天安门』：假设标注为" s c b e b c e"。

对于HMM的话，其判断这个标注成立的概率为：
P= P(s转移到c)*P('我'表现为s)* P(c转移到b)*P('爱'表现为c)* ...
训练时，要统计状态转移概率矩阵和符号发射概率矩阵。

对于MEMM的话，其判断这个标注成立的概率为：
P= P(s转移到c|'我'表现为s)*P('我'表现为s)* P(c转移到b|'爱'表现为c)*P('爱'表现为c)*...
训练时，要统计条件状态转移概率矩阵和符号发射概率矩阵。

前面也给出了这个图：

HMM与MEMM依存图对照

MEMM中，除了t-1时刻的状态，当前时刻的观察输出也是当前时刻状态的决定条件。

对于CRF的话，其判断这个标注成立的概率为：
P= F(s转移到s,'我'表现为s...)
F为一个函数，是在全局范围统计归一化的概率而不是像MEMM在局部统计归一化的概率。

条件随机场的条件概率公式较为复杂，这里不再给出推导过程。

条件随机场也需要解决三个基本问题：特征的选取、解码和参数训练。

前面提到了条件随机场就是一个马尔可夫随机场，这里简要介绍一下马尔可夫随机场与条件随机场的关系，参考了随机场。

马尔可夫一般是马尔可夫性质的简称，它指的是一个随机变量序列按时间先后关系依次排开的时候，第N+1时刻的分布特性，与N时刻以前的随机变量的取值无关。

随机场包含两个要素：位置（site），相空间（phase space）。当给每一个位置中按照某种分布随机赋予相空间的一个值之后，其全体就叫做随机场。我们不妨拿种地来打个比方。『位置』好比是一亩亩农田；『相空间』好比是种的各种庄稼。我们可以给不同的地种上不同的庄稼，这就好比给随机场的每个『位置』，赋予『相空间』里不同的值。所以，俗气点说，随机场就是在哪块地里种什么庄稼的事情。

然后类比马尔可夫随机场，还是拿种地打比方，如果任何一块地里种的庄稼的种类仅仅与它邻近的地里种的庄稼的种类有关，与其它地方的庄稼的种类无关，那么这些地里种的庄稼的集合，就是一个马尔可夫随机场。

其实通过上文也能发现，CRF和MRF（马尔可夫随机场）的关键区别就在马尔可夫性质上，CRF是在给定需要标记的观察序列的条件下，计算整个标记序列的联合概率分布，而不是在给定当前状态条件下，定义下一个状态的状态分布。

个人理解，马尔可夫性质就是前面提到的有限历史性假设，CRF舍弃掉了有限历史性假设，这也就是CRF与MRF（马尔可夫随机场）的最大区别。

上面的讲法可能还会有误解，看下面这张图：

朴素贝叶斯序列化得到HMM，Logistic回归序列化得到链式CRF，HMM与链式CRF的区别就类似于朴素贝叶斯算法与Logistic回归的区别。CRF舍弃掉了HMM的有限历史性假设、输出独立性假设，由生成模型转变为判别模型，由概率图转变为函数拟合（这句是解释力最强的，如果你真的理解朴素贝叶斯算法和Logistic回归算法的区别）。就像Logistic回归，它不再像朴素贝叶斯算法那样计算各种先验条件概率，由贝叶斯公式得到计算结果，而是整体的去做函数拟合，表示出训练集整体的联合分布概率，并对其做期望最大化，这与CRF之于HMM是相同的。

自动分词、命名实体识别与词性标注

由于词是最小的能够独立运用的语言单位，而汉语的词与词之间没有任何空格之类的显式标志指示词的边界，因此，自动分词问题就成了处理汉语文本时面临的首要基础性问题。

汉语自动分词中的基本问题

简单地讲，汉语自动分词就是让计算机系统在汉语文本的词与词之间自动加上空格或其他边界标记。汉语自动分词的主要困难来自如下三个方面：分词规范、歧义切分和未登录词的识别。

首先是汉语分词规范，『词是什么』、『什么是词』这两个基本问题飘忽不定，迄今拿不出一个公认的、权威的词表来。单字词与词素之间的划界、词与短语（词组）的划界，都是很难解决的问题。不同的人、普通人和语言学家之间的分词标准都有很大的差异。

然后是歧义切分问题，梁南元定义了两种基本的切分歧义类型，一个是交集型切分歧义，另一个是组合型切分歧义。

先说交集型切分歧义，汉字串AJB称作交集型切分歧义，如果满足AJ、JB同时为词。此时汉字串J称作交集串。比如『从小学起』可以切为『从小|学起』、『从|小学|起』。

一个交集型切分歧义所拥有的交集串的集合称为交集串链，它的个数称为链长。比如『结合成分子』，『结合』、『合成』、『成分』、『分子』均成词，交集串的集合为『合、成、分』，因此链长为3。

接下来是组合型切分歧义，汉字串AB称为多义组合型切分歧义，如果满足A、B、AB同时成词。比如『起身』，『他站|起|身|来』和『他|明天|起身|去北京』。还有别的例子，比如『才能』、『学生会』。而且严格定义的话，需要补充一个条件，文本中至少存在一个上下文语境C，在C的约束下，将AB切开成A、B，在语法和语义上都成立。

有人还将交集型切分歧义成为偶发歧义，多义组合型切分歧义称为固有歧义。

对于一些较为复杂的文本，还可能会出现交集型歧义内包含组合型歧义的情况，有人称其为混合型切分歧义。

第三个是未登录词问题。未登录词又称生词（unknown word），未登录词可以有两种解释，一种是已有的词表中没有收录的词，另一个种是已有的训练语料中未曾出现过的词。由于目前的汉语自动分词系统多采用基于大规模训练语料的统计方法，所以这两种解释通常可以不用区分。

未登录词可能是：

• 新出现的普通词，比如一些最先流行在互联网上的词
• 命名实体，比如人名、地名（包括城市名、省名、国家名等）、组织机构名、时间和数字表达
• 专业名词和研究领域名称，比如三聚氰胺、堰塞湖
• 其他专用名词，比如新出现的产品、电影、书籍名等等

而且，在汉语分词中对命名实体词汇的识别不是只识别整个实体的左右边界，而是将命名实体中可独立成词的切分单位正确地识别出来。比如『2017年3月27日』，这是一个命名实体，但在分词时不能将其整个的作为一个实体识别出来，而是要分出『2017|年|3|月|27|日』。比如人名也要把姓和名分开。

汉语分词方法

汉语自动分词问题被提出来之后，上世纪80年代及之前，人们提出过很多分词方法，比如正向最大匹配法、逆向最大匹配法、双向扫描法、逐词遍历法等。这些方法大多数都是基于词表进行的，因此，一般统称为基于词表的分词方法。

随着统计方法的迅速发展，人们又提出了若干基于统计模型（比如HMM和n元文法模型）的分词方法，以及规则方法与统计方法相结合的分词技术。

N-最短路径方法

我们先来介绍N-最短路径方法，考虑到汉语自动分词中存在切分歧义消除和未登录词识别两个主要问题，有人提出将分词过程分为两个阶段：首先采用切分算法对句子词语进行初步切分，得到一个相对最好的粗分结果，然后，再进行歧义排除和未登录词识别。

粗切分结果的准确性与包容性（即必须涵盖正确结果）直接影响后续的歧义排除和未登录词识别模块的效果，并最终影响整个分词系统的正确率和召回率。

N-最短路径方法就是一个汉语词语粗分模型，基本思想是，先根据词典找到字串中所有可能的词，构造一个词语切分的有向无环图，每个词对应一条有边长（权值）的边，然后我们找出由起点到终点的所有路径中，拥有N个最小长度值的路径结果，所以得到的路径数量可能大于N。简单的来说，就是整体上尽可能多的用上词典里的词，而不是让词处于未处理的状态，因为词的边长要比组成词的字的总边长要短。

因为涉及到图的边长，N-最短路径方法还可以分为非统计粗分模型和统计粗分模型，所谓非统计粗分模型就是假定切分有向无环图中所有词的权重都是相等的，即每个词对应的边长为1。

既然是求最短路径，就要考虑Dijkstra算法了，Dijkstra算法的过程这里不讲，下面是求『他说的确实在理』的3-最短路径的示例：

『他说的确实在理』的求解过程（N=3）

最终起点0到终点7有两条长度为5的路径，一条长度为6的路径，一条长度为7的路径，从Table表中就可以看出。前驱(i,j)中的i表示到达当前节点的前一个节点，而j表示对应到前一个节点i编号为j的路径上。这样根据这个表就能回溯出所有的路径。

非统计模型给每个词对应边的长度赋值为1，随着字串长度n和最短路径数N的增大，长度相同的路径数会急剧增加，同时粗切分结果数量必然上升，这对于后期处理和整个分词系统的性能很不利。接下来我们介绍基于统计的N-最短路径方法。

假定一个词串W经过信道传送，由于噪声干扰而丢失了词界的切分标志，到输出端便成了汉字串C。N-最短路径方法词语粗分模型可以相应地改进为：求N个候选切分W，使概率P(W|C)为前N个最大值。

然后根据贝叶斯公式P(W|C)=P(W)P(W|C)/P(C)，P(C)是常数，P(W|C)为1，所以我们只需考虑P(W)即可，粗分的目标就是确定P(W)最大的N种切分结果。

然后我们采用一元文法模型，假定词的出现相互独立，以W=w1w2...wm作为一种切分结果，那切分W的概率为：

因为是连乘，为了处理方面，对其取对数，即变成了对数值的累加，那每一个对数值就可以看做是对应的词在有向无环图中的边长，当然我们可能还需要做适当的数据平滑处理。

这样对边长进行修改后，直接代入之前非统计粗分模型的求解算法即可。

基于词的n元语法模型的分词方法

基于词的n元语法模型是一个典型的生成式模型，早期很多统计分词方法均以它为基本模型，然后配合其它未登录词识别模块进行拓展。

基于词的生成式模型的二元文法切分词图

其基本思想是：首先根据词典对句子进行简单匹配，找出所有可能的词典词，然后，将它们和所有的单个字作为结点构造n元的切分词图。图中的结点表示可能的词候选，边表示路径，边上的n元概率表示代价，最后利用相关算法（如维特比算法）从图中找到代价最小的路径作为最后的分词结果。

由于未登录词的识别是汉语分词过程中的关键问题之一，因此，很多专家认为未登录词的识别与歧义切分应该是一体化处理的过程，而不是相互分离的。所以这种基于改进的信道信源模型的分词方法被提出了。

为了给自动分词任务一个明确的定义，J.Gao等人（2003）对文本中的词给出了一个可操作的定义，把汉语词定义成下列4类：

• 待切分文本中能与分词词表中任意一个词相匹配的字段为一个词
• 文本中任意一个经词法派生出来的词或短语为一个词
• 文本中被明确定义的任意一个实体名词（如：日期、时间、货币、百分数、温度、长度、面积、体积、重量、地址、电话号码、传真号码、电子邮件地址等）是一个词。
• 文本中任意一个专有名词（人名、地名、机构名）是一个词。

假设随机变量S为一个汉字序列，W是S上所有可能的词序列结果，所以经过贝叶斯公式转化，我们求的就是：

为了把4类词纳入同一个统计语言模型框架，一般把人名（PN）、地名（LN）、机构名（ON）各作为一类，实体名词中的日期、时间、百分数、货币作为一类处理，简称实体名，词法派生词（MW）个词表词（LW）每个词单独作为一类。那么词序列W可以被我们转换成一个词类序列C：

P(C)就是我们熟悉的语言模型，P(S|C)我们可以称之为基于词的生成式模型。

对P(C)我们采用三元文法模型：

而对于P(S|C)，我们认为其满足独立性假设，总概率为各个概率的乘积，而对每个词类的处理参考下表：

一些数据平滑操作也是需要的。

模型的训练过程一般如下：

• 在词表的基础上，先根据正向最大匹配法切分训练语料，专有名词特殊标注，实体名词用规则和有限状态自动机标注，得到一份带类别标记的初始语料
• 根据语料，采用最大似然估计法估计模型的概率参数
• 采用得到的语言模型对训练语料进行重新切分和标注
• 重复上两步直到系统性能不再有明显提高

对于交集型歧义字段（OAS），该方法首先通过最大匹配检测出这些字段，然后用一个特定的类<GAP>取代全体OAS，以此来训练语言模型P(C)。类<GAP>通过消歧规则或机器学习方法来估计。

对于组合型歧义字段（CAS），该方法通过对训练语料的统计，选出最高频、且分布比较均匀的70条CAS，用机器学习方法为每一条CAS训练一个二值分类器，这些分类器用于训练语料中消解这些CAS的歧义。

由字构词的汉语分词方法

由字构词的汉语分词方法将分词看做字的分类问题，是一种基于字的判别式模型，在以往的分词方法中，无论是基于规则的方法还是基于统计的方法，一般都依赖于一个事先编制的词表，自动分词过程就是通过查词表作出词语切分的决策。与此相反，由字构词的分词方法认为每个字在构造一个特定的词语时都占据着一个确定的构词位置，比如词首（B）、词中（M）、词尾（E）、单独成词（S）。

分词结果表示成字标注形式之后，分词问题就变成了序列标注问题。

因为我们需要根据上下文来判断待消歧问题的结果，所以通常情况下，使用基于字的判别模型时需要在当前字的上下文中开一个w字的窗口（一般取w=5，也就是前后各两个字），在这个窗口里抽取分词相关的特征，常用的特征模板如下：

• c(k)（k＝-2，-1,0,1,2）
• c(k)c(k+1)（k＝-2，-1,0,1）
• c(-1)c(1)
• T(c(-2))T(c(-1))T(c(0))T(c(1))T(c(2))

c指k位置上的字，T指字的类型。

有了这些特征以后，我们就可以利用常见的判别模型，比如最大熵模型、条件随机场、SVM和感知机等进行参数训练了。

由字构词的重要优势在于，它能够平衡地看待词表词和未登录词的识别问题，文本中的词表词和未登录都是用统一的字标注过程来实现的，分词过程就成了字重组的简单过程。

基于词感知机算法的汉语分词方法

基于词感知机算法的汉语分词方法是一种基于词的判别式模型，不同于前面基于词的生成模型和基于字的判别模型。该模型采用平均感知机作为学习算法，直接使用词而不是字的相关特征。

基于感知机算法的汉语自动分词方法的基本思路是，对于任意给定一个输入句子，解码器每次读一个字，生成所有的候选词。生成候选词的方式有两种，第一个是，作为上一个候选词的末尾，与上一个候选词组合成一个新的候选词；或者是，作为下一个候选词的开始。这种方式可以保证在解码过程中穷尽所有分词候选。

在解码的过程中，解码器维持两个列表，源列表和目标列表。开始时，两个列表都为空。解码器每读入一个字，就与源列表中的候选组合，按上一段说的两种方法，生成两个新的候选词放入目标列表。当源列表中的候选都处理完成之后，将目标列表中的所有候选词复制到源列表中，并清空目标列表。然后读入下一个字，如此循环往复直到句子结束。

这种算法类似于全切分算法，理论上生成切分结果的数量会随句长指数增长，为了提升速度，可以对目标列表的条目数进行限制，每次只保留B个得分最高的候选。可以用平均感知机算法对目标列表中的切分候选进行打分和排序。

平均感知机算法也是套用一些特征模板，使用一些规则，进行打分和排序，这里不再细说。

基于字的生成式模型和判别式模型相结合的汉语分词方法

前面讲的，基于词的n元语法模型（生成式模型）和基于字的序列标注模型（判别式模型）是两大主流方法。

其中，基于词的生成式模型在处理词典词时可以获得较好的表现，而基于字的判别式模型则想法，对未登录词的处理要更好一些。

而且实验发现，两个处于词边界的字之间的依赖关系和两个处于词内部的字的依赖关系是不一样的。基于词的生成式模型实际上隐含的考虑了这种处于不同位置的字的依赖关系，而基于字的判别式模型却无法考虑这种依赖关系。但是判别式模型能够充分利用上下文特征信息，拥有较大的灵活性和鲁棒性，所以基于字的n元语法模型，并将生成式模型与判别式模型相结合的汉语分词方法被提出。

我们将基于词的生成式模型中的词替换为相应的字即得到了基于字的生成式模型。

基于字的生成式模型仍然以字作为基本单位，但考虑了字与字之间的依赖关系，与基于字的判别式模型相比，处理词典词的能力有了大幅改观。但是该模型并不能像基于字的判别模型那样考虑整个窗口，也即当前字后面的上下文。因此，基于字的生成式模型在处理未登录词的能力仍然若于基于字的判别式模型。

为了同时利用生成式模型和判别式模型的优点，利用线性插值法将这两个模型进行整合，就提出了集成式分词模型。