基于隐马尔科夫模型的中文输入法SEGInput的设计与实现

SEGInput：基于隐马尔科夫模型的中文输入法设计与实现李永超，蔡增科，刘春能，戎挺南京大学，计算机科学与技术系摘要：我们基于前一个版本的输入法做了如下改进：1）实现了词组和句子的输入功能；2）实现了运行在Windows环境中的可用的输入法程序。我们提出了基于隐马尔科夫模型的拼音串到汉字串的转换算法，以支持词组和句子的输入。通过对大量文本进行统计学习，建立了汉字的隐马尔科夫转换模型库，将拼音串作为观察变量，通过建立的隐马尔科夫转换模型计算出作为隐式状态的汉字串的概率，按照这些字串出现的概率的排序呈现给用户进行选择。我们基于所提出的算法实现了SEGInput拼音输入法。输入法程序的实现是基于Windows提供的IMM-IME框架，使得用户可以像使用智能ABC等输入法一样使用我们的输入法。关键词：隐马尔科夫转换模型；IMM-IME。1引言上一个版本中，我们对拼音输入法的实现方法进行了调研，并实现了一个具有最基本的单字输入功能的输入法程序模型。随后我们展开了对于具有词组和句子输入功能的输入法的实现的调研。我们设计了基于隐马尔科夫模型的拼音串到汉字串的转换算法。算法将拼音串看做隐马尔科夫模型中的观察值，将汉字看成隐含状态，算法的目标是在已知拼音串的情况下，计算出该拼音串是由某汉字串产生的概率。每当用户的拼音串发生改变，算法便执行一次，给出最有可能的汉字串。本文余下部分安排如下：第2节简单介绍隐马尔科夫模型；第3节重点介绍我们提出的算法；第4节介绍SEGInput输入法的实现原理；第5节总结。2隐马尔科夫模型简介隐马尔可夫模型（HiddenMarkovmodels，HMM）是马尔可夫链的一种，它的状态不能直接观察到，但能通过观测向量序列观察到，每个观测向量都是通过某些概率密度分布表现为各种状态，每一个观测向量是由一个具有相应概率密度分布的状态序列产生。所以，隐马尔可夫模型是一个双重随机过程，具有一定状态数的隐马尔可夫链和显示随机函数集。其中马尔科夫链描述了状态的转移,一般用转移概率矩阵描述；而一般随机过程描述状态和观测序列间的关系，用观察概率矩阵描述。隐马尔可夫模型是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析，例如模式识别。在正常的马尔可夫模型中，状态对于观察者来说是直接可见的。这样状态的转换概率便是全部的参数。而在隐马尔可夫模型中,状态并不是直接可见的，但受状态影响的某些变量则是可见的。每一个状态在可能输出的符号上都有一概率分布。因此输出符号的序列能够透露出状态序列的一些信息。上图是隐马尔科夫模型状态变迁的一个例子，x表示隐含状态，y表示可观察的输出，a表示转换概率，b表示输出概率。有时，明确的表示出模型的演化也是有用的,我们用x（t1）与x（t2）来表达不同时刻t1和t2的状态。在下图中，每个时间快（x(t),y(t)）都可以向前或向后延伸。通常，时间的起点被设置为t=0或t=1。隐马尔可夫模型可以用五个元素来描述：1.N，模型的隐状态数目。虽然这些状态是隐含的，但在许多实际应用中，模型的状态通常有具体的物理意义。2.M，每个状态的不同观测值的数目。3.A，状态转移概率矩阵。描述了HMM模型中各个状态之间的转移概率。其中A_{IJ}=P(A_{T+1}=S_{J}|Q_{T}=S_{I}),1≤I,J≤N.(1)式（1）表示在T时刻、状态为SI的条件下，在T+1时刻状态是SJ的概率。4.B，观测概率矩阵。其中BJ(K)=P[VK(T)|QT=SJ];1≤J≤N,1≤K≤M。表示在T时刻、状态是SJ条件下，观察符号为VK(T)的概率。5.π初始状态概率矩阵π={π_{J}|π_{J}=P[Q_{1}=S_{J}];1≤J≤N。表示在初始T=1时刻状态为SJ的概率。一般的，可以用λ=(A,B,π)来简洁的表示一个隐马尔可夫模型。给定了N,M,A,B,π后，隐马尔可夫模型可以产生一个观测序列O=O1O2O3…OT。隐马尔科夫模型有三个典型问题：1.评估问题：已知模型参数，计算某一特定输出序列的概率。通常使用forward算法解决。2.解码问题：已知模型参数，寻找最可能的能产生某一特定输出序列的隐含状态的序列。通常用Viterbi算法解决。3.学习问题：已知输出序列，寻找最可能的状态转移以及输出概率。通常使用Baum-Welch算法以及ReversedViterbi算法解决。另外,最近的一些方法使用Junctiontree算法来解决这三个问题。下面举个例子来更好地阐释隐马尔科夫模型。假设你有一个住得很远的朋友,他每天跟你打电话告诉你他那天做了什么。你的朋友仅仅对三种活动感兴趣:公园散步,购物以及清理房间。他选择做什么事情只凭天气。你对于他所住的地方的天气情况并不了解,但是你知道总的趋势。在他告诉你每天所做的事情基础上,你想要猜测他所在地的天气情况。你认为天气的运行就像一个马尔可夫链。其有两个状态雨和晴,但是你无法直接观察它们,也就是说,它们对于你是隐藏的。每天,你的朋友有一定的概率进行下列活动:散步,购物,或清理。因为你朋友告诉你他的活动,所以这些活动就是你的观察数据。这整个系统就是一个隐马尔可夫模型。你知道这个地区的总的天气趋势,并且平时知道你朋友会做的事情。也就是说这个隐马尔可夫模型的参数是已知的。你可以用程序语言(Python)写下来:states=('Rainy','Sunny')observations=('walk','shop','clean')start_probability={'Rainy':0.6,'Sunny':0.4}transition_probability={'Rainy':{'Rainy':0.7,'Sunny':0.3},'Sunny':{'Rainy':0.4,'Sunny':0.6},}emission_probability={'Rainy':{'walk':0.1,'shop':0.4,'clean':0.5},'Sunny':{'walk':0.6,'shop':0.3,'clean':0.1},}在上述代码中,start_probability代表了你对于你朋友第一次给你打电话时的天气情况的不确定性(你知道的只是那个地方平均起来下雨多些)。在这里,这个特定的概率分布并非平衡的,平衡概率应该接近（在给定变迁概率的情况下）{'Rainy':0.571,'Sunny':0.429}。transition_probability表示基于马尔可夫链模型的天气变迁,在这个例子中,如果今天下雨,那么明天天晴的概率只有30%。代码emission_probability表示了你朋友每天做某件事的概率。如果下雨,有50%的概率他在清理房间;如果天晴,则有60%的概率他在外头散步。隐马尔可夫模型最初是在20世纪60年代后半期LeonardE.Baum和其它一些作者在一系列的统计学论文中描述的。HMM最初的应用之一是开始于20世纪70年代中期的语音识别。在1980年代后半期，HMM开始应用到生物序列尤其是DNA的分析中。从那时开始，在生物信息学领域它们已经变得无处不在。3基于隐马尔科夫模型的拼音到汉字转换算法3.1拼音输入法简介我们知道输入法几乎是我们每一个中国人使用电脑时都会用到的软件。在电脑普及的过程中，有很多的输入法陪伴过用户撰写文档、冲浪、聊天。随着网络时代的来临，每天都有大量的新词、新人名涌现出来，例如：“八荣八耻”，“胡戈”，“李宇春”，“劲舞团”，“超女”等。输入法有单字拼音输入方法和多字输入法也即全拼输入，输入要打的字的全拼中所有字母当用户输入汉字拼音时，然后需要给出候选汉字。如：中国：zhongguo，输入法需给出候选词中国、中过、种过等等。3.2拼音输入法问题拼音输入法最基本的两个问题是：1、词库：如何建立最新最全的词库，特别是互联网上特有的、刚刚出现的新词；2、词频：如何提高对于同音词的词频统计和排序准确性。我们的输入法由于客观因素的限制，暂时忽略第一个问题，我们主要集中的解决如何提高对于同音词的词频统计和排序准确性。我们是通过大量的语料来解决并且统计这些词汇的出现频率。基于这些的数据，输入法的关键性问题词频——得到了突破性的解决。3.3拼音输入法隐马尔科夫模型以上简介可见，拼音输入法就是怎么将用户输入的拼音准确的转换成候选汉字，我们对比隐马尔科夫模型，可知这种问题，可以用隐马尔科夫模型去实现。拼音输入法隐马尔科夫模型定义),,,,(BAVS，其中S是状态集，也即所有的汉字，V是观测值也即拼音，还有观察序列ToooO...21可见，A是状态转移概率分布][ijaA，B是观察值生成概率分布)]([kjvbB，这里的1)|()(itktkjsqvoPob因为给定汉字我们有拼音是唯一的（多音字当单字处理）。初始状态值概率分布)(],[1iiisqP，这里i根据汉字拼音个数可以计算得。模型解码，给定模型和一个拼音序列，寻求一个产生这个拼音序列的可能性最大的汉字序列，也即给定拼音序列T（可见的拼音序列），寻求产生这个拼音序列的最可能的汉字序列TSSS...21（隐藏的状态序列）。通过语料库进行模型学习，只需要学习A，学习方法：有指导的学习－最大似然估计。数所有汉字总数出现词组ijiijijsssssPa)|(然后利用Viterbi算法的寻求产生这个拼音序列的最可能的汉字序列TSSS...21（隐藏的状态序列）初始化：NiwsPosPiiii1,),(max)(11迭代：)]([max)]...,,...(maxmax[)...,,...(max)(2112111i迭代结束：))((maxiTi回溯记录最优路径给出汉字结果。3.4隐马尔科夫模型代码实现3.4.1模型参数学习上文提到实现用隐马尔科夫模型实现音字的转换需要的参数π（初始化概率）和A（转换概率矩阵）。我们小组先以人民日报作为语料，训练出这两个参数。模型训练实际是一个统计过程，以单个汉字为单位，遍历语料库，用数组occurrenceList记录每个汉出现的次数；用矩阵convert[i][j]记录汉字j在汉字i后出现的次数。然后可利用下面的公式算得π和A：（其中h为某个汉字，hi表示与该汉字同音的所有汉字）由于模型训练时间很长，需用离线模式，所以得到模型参数以后用文件保存。考虑到程序运行时需要读文件进行参数初始化，为了不影响性能，要尽可能高效的存储。矩阵A是汉字到汉字的转换概率，大概为一个6000*6000的矩阵，如果直接存储是必对系统时间和空间都是一个挑战。不难发现该矩阵为一稀疏矩阵，因此我们将矩阵分行存储，而每行记录下标和概率值。在系统运行时用mapstring,mapstring,double这样的数据结构读入内存。3.4.2veterbi算法实现在得到了模型参数以后，就可用于音字转换。转换算法的基本描述如下：4SEGInput——基于隐马尔科夫模型的中文输入法的实现关于Windows的IMM-IME框架的介绍请参照上一版本文档《基于IMM-IME框架的中文输入法实现研究》第3节中的内容。本部分将主要介绍如何基于IMM-IME框架实现SEGInput输入法。供用户使用的输入法程序属于IME应用程序，IMM是系统的输入法管理器，它调用IME应用程序中实现的接口，在IME应用程序和输入窗口之间传递消息，并且维护进行输入和转换所需的数据结构。要使一个IME应用程序可以顺利的在系统中运行，必须实现IMM需要调用的19个函数，虽然不是所有的函数都要给出定义，但哪怕是提供一个空函数体，也必须使其存在于IME程序中。4.1主要数据结构输入和转换的实现，必须依赖两个数据结构：写作字串和候选列表（Compositionstring和Candidatelist）。前