在研究分词的这段时间里,接触了隐马尔科夫模型(Hidden Markov Model,HMM),刚开始看的时候一头雾水,花了两天时间静下心来研究了一下,在此做个总结。

一、介绍

我们通常都习惯寻找一个事物在一段时间里的变化模式(规律)。这些模式发生在很多领域,比如计算机中的指令序列,句子中的词语顺序和口语单词中的音素序列等等,事实上任何领域中的一系列事件都有可能产生有用的模式。
考虑一个简单的例子,有人试图通过一片海藻推断天气——民间传说告诉我们‘湿透的’海藻意味着潮湿阴雨,而‘干燥的’海藻则意味着阳光灿烂。如果它处于一个中间状态(‘有湿气’),我们就无法确定天气如何。然而,天气的状态并没有受限于海藻的状态,所以我们可以在观察的基础上预测天气是雨天或晴天的可能性。另一个有用的线索是前一天的天气状态(或者,至少是它的可能状态)——通过综合昨天的天气及相应观察到的海藻状态,我们有可能更好的预测今天的天气。
首先,我们将介绍产生概率模式的系统,如晴天及雨天间的天气波动。
然后,我们将会看到这样一个系统,我们希望预测的状态并不是观察到的——其底层系统是隐藏的。在上面的例子中,观察到的序列将是海藻而隐藏的系统将是实际的天气。
最后,我们会利用已经建立的模型解决一些实际的问题。对于上述例子,我们想知道:

  • 给出一个星期每天的海藻观察状态,之后的天气将会是什么?
  • 给定一个海藻的观察状态序列,预测一下此时是冬季还是夏季?直观地,如果一段时间内海藻都是干燥的,那么这段时间很可能是夏季,反之,如果一段时间内海藻都是潮湿的,那么这段时间可能是冬季。
    Read more »

(一)、人名的自动识别

中国人名识别的主要困难有:

  1. 人名构成的多样性
    如:姓名,有名无姓,有姓无名,姓+前后缀,港澳台已婚妇女姓名
  2. 人名内部相互成词
    如:王国维,高峰,汪洋,张朝阳
  3. 人名与其上下文组成合成词
    如:“这里有关天陪的壮烈事迹”
  4. 歧义理解
    如:“周鹏和同学”存在“周鹏”、“周鹏和”的歧义

针对这个问题目前存在的主要解决方案有:规则方法,统计方法以及规则和统计相结合的方法。规则方法主要利用了姓氏分类和名字组成的限制性,如名字的组成一般不会超过四个字。但是由于它需要“单点激发”,即它需要扫描到姓氏、职衔、称呼后才开始识别,所以往往无法识别不具有明显特征的人名,例如“有名无姓”的情况。统计方法主要是针对姓名语料库来训练某个字作为姓名组成部分的概率,并利用它们来计算某个字段作为姓名的概率值,其中概率值大于某一阈值的字段识别为中国人名。统计方法对语料库的规模要求很高。所以,在这种情况下,提出了基于角色标注的中文人名自动识别算法。该方法的大致思路是用隐马尔科夫模型(HMM)在分词结果上标注人名构成的角色,然后在标注出的角色序列基础上根据各个不同的角色,进行最长模式匹配,最终识别出人名。下面分别来说明这几个步骤:

Read more »

在上篇文章中,我们已经了解了1-最短路径的计算方式,接下来,我们来看看N-最短路径的求法。

N-最短路径的原理与1-最短路径的相同,只不过求解过程要稍微复杂一点。让我们仍然以上篇文章中的实例来看看如何求解N-最短路径。

一、数据表示

我们沿用上篇文章中的例子,各权重已经标出:

(图一)

根据有向图可以建立如下所示的二维表:

(图二)

Read more »