基于感知器算法的维吾尔语词性标注研究

帕提古力·依马木，买合木提·买买提，吐尔根·依布拉音，卡哈尔江·阿比的热西提

(新疆大学 信息科学与工程学院，新疆 乌鲁木齐 830046)

1 引言

目前基于统计的词性标注方法得到了广泛的应用并取得了良好的效果。在基于统计方法的词性标注中，对兼类词和未登录词的处理是需要解决的问题。对兼类词和未登录词，可以根据词的上下文信息来确定词在句子中的词性。

维吾尔语属黏着语, 其形态变化比较丰富。名词有数、格、人称等语法范畴; 动词有数、人称、时态、语态的变化; 形容词有级的范畴。形态变化一方面提供了一些深层语法信息, 为词法分析、词性标注带来极大的方便, 另一方面也增加了自动标注的复杂性。维吾尔语同其他语言一样也存在词性歧义现象(词兼类现象)。在维吾尔语中兼类词数量较多，且使用频率较高，这给维吾尔语词性标注带来了很大的困难。兼类现象是词性标注中的一个不可回避的重点和难点，词性是词的重要的语法信息，假如一个词的词性无法确定，对后续句法分析造成直接的影响，句法分析就无法进行。如果一个词赋予错误的词性，将导致严重的句法分析错误，所以，维吾尔语词性标注在自然语言处理中有至关重要的意义。本文使用感知器算法进行维吾尔语的词性标注。目前基于感知器算法的模型在各个领域都表现出很好的性能，本文主要利用感知器算法的优点，在进行词性标注时利用词的上下文信息作为特征，在维吾尔语词性标注中取得了好的效果。

2 相关工作

目前词性标注方法可分为3类： 基于规则的词性标注方法、基于转换的错误驱动词性标注方法以及基于统计的词性标注方法。

1) 基于规则的词性标注方法

基于规则的词性标注方法首先由语言学家制定相应的规则，在规则中使用大量的上下文信息来对词性进行判断。词性标注的性能与规则制定者的语言学知识具有很大的关系。其次要构造一套对语言的各方面特性都覆盖的规则是一个艰难耗时的工作，而且随着规则数量的增加，各规则之间往往会产生冲突。最具有代表性的基于规则的词性标注系统是 1971 年开发的 TAGGIT 标注系统[1]。对于维吾尔语来说，基于规则的词性标注有吐尔根等开发的基于词典的维吾尔语词性标注系统[2]。

2) 基于转换的错误驱动词性标注方法

为了克服手工制定规则带来的问题，1995 年 Eric Brill 提出了基于转换的错误驱动的词性标注方法[3]。该方法最初用于英语的词性标注，基本处理步骤是: 首先为每个句子赋以初始词性序列，然后通过将这些句子与正确词性标注的句子相比较，自动学习一些结构转换规则，最后将这些规则作用于新的被赋以同样初始词性序列的句子上，就可以得到正确的词性标注。重复以上的过程直到不再获取新的转换规则，这样就可以构建一个词性标注规则集[4]。该方法的优势在于能有效地利用语言的词和语法的规则以及一定的上下文信息。实验结果显示，此方法可以用较小的训练集达到较高的分析准确度。

3) 基于统计的词性标注方法

基于统计的方法是目前应用最广泛的词性标注方法。基于统计的词性标注方法将词性标注看作是一个序列标注问题，为每一个词语赋予一个正确的候选词性。基于统计的词性标注有基于隐马尔科夫模型的词性标注方法、基于最大熵的词性标注方法、基于支持向量机的词性标注方法、基于条件随机场的词性标注方法等。在基于统计的维吾尔语词性标注方面，文献[5]提出基于N元模型的维吾尔词性自动标注方法,使用N元语法模型和动态规划的方法进行维吾尔语的词性标注，在测试中把训练语料库和测试语料库的比例设置为19∶1，并分析了二元,三元模型对维吾尔语词性标注的效率。训练和测试语料库的规模差距较大，该测试基本上接近于封闭测试。根据文献[6]的错误分析，模型性能下降的主要原因是未登录词较多。实际上，大多数未登录词在训练库里已有词干形式，只是因为词干附加了词缀发生形态变化导致模型与训练库的匹配失败。文献[7]中提出基于条件随机场的词性标注方法,有效地利用了所有可用的信息，并选择不同的模板进行试验。最后选用模板C建立基于条件随机场的维吾尔语词性标记标注模型。文献[7]还提出基于混合策略的维吾尔语词性标注并取得了良好的结果。常见的基于统计的方法还有神经元网络、决策树、线性分离网络标注模型等等。

3 训练算法和特征选择

本文主要用感知器算法进行训练并根据维吾尔语的特点选择特征。以下详细介绍感知器算法和选择的特征。

3.1 感知器算法

目前基于统计的方法是词性标注、文本识别等方面的主流方法。在基于统计的方法中，问题被描述为统一的序列标注问题，即给定一个观测序列X=(x1,x2,…,xn)，需要求解最优的标记序列Y=(y1,y2,…,yn)。 其中一类方法从概率的角度来估计X和Y的概率分布，这类方法常用的统计模型有最大熵模型(Maximum Entropy Model，ME)[8]，隐马尔科夫模型(Hidden Markov Model，HMM)[9]以及条件随机场模型(Condition Random Fields Model，CRF)[10]等。在另一类序列标注算法中，定义观测序列X=(x1,x2,…,xn)对应状态序列Y=(y1,y2,yn)的分数(score)为式(1)所示。

(1)

其中fn(X,Y)为特征函数，wn为第n个特征对应的权重。

当特征函数取特定值时，则该模板被实例化，得到具体的特征。特征值一般可以定义为下面的一个二值函数形式：

给定观测序列X=(x1,x2,…,xn)，最好的状态序列Y为score最大的状态序列，即式(2)所示。

Y=argmaxY′score(X,Y′)

(2)

当通过训练得到每个特征对应的权重后，我们可以使用动态规划算法快速得到score最大的状态序列。

在线算法[11]是一种常用的训练算法，在在线算法中，每次仅仅使用一个实例对参数进行更新，而不像梯度下降之类的批处理训练算法，每次更新参数都需要用到所有的训练语料，导致对资源的巨大消耗。感知器算法[12]是一种典型的在线算法。感知器算法每次使用一个训练实例对模型参数进行更新，在更新参数时每次将需要更新的参数重加 1 或者减 1。感知器算法的代码如下所示：

Input:Trainingexamples(xi,yi)

Algorithm:Fort=1 ..T,i=1..n

zi=F(xi),

为了防止模型对数据的过拟合，常对参数进行平均化操作，即Average Perceptron 算法。

算法的表达形式如图1所示。

图1 算法的表达形式

(3)

用简单的例子描述感知器算法在维吾尔语词性标注的过程:

gold-standard: NB MI AO NB VN ∅(x,y)

Yiraqtin bir qara at k⊇liwatatti

current output : NB MI AO VN VN ∅(X,Z)

Yiraktin bir qara at k⊇liwatatti

上述例子假设有以下的特征:

词性 ti-1ti;词/词性组合Wi/ti 根据上面的算法，对参数进行更新。

weights ++: (AO, NB)( NB→at)

weights --: (AO, VN)( VN→at)

通过感知器训练算法得到每个特征对应的权重后，我们可以使用动态规划算法快速得到最优的状态序列。

3.2 特征选择

特征选择是指针对特定的任务，为模型选取特征集合。词性的正确判断依赖于可靠的特征信息。维吾尔语词性自动标注模型的关键是利用对词性歧义消除的特征构建特征模块，尽量减少冲突的特征。根据维吾尔语的语言知识，维吾尔语词的结构，形态等特征信息与词性的关系以及维吾尔语的语法特点，本文中主要使用的基本特征如表1所示。

表1 基本特征表

4 解码算法

本文中使用Viterbi算法快速地得到最优的状态序列。Viterbi算法是基于动态规划(Dynamic Programming)的思想，找“正确”的状态序列--词性。具体的就是先解决最基本的子问题，然后再寻找整个问题即最优解。对已知词序列w1,w2…wm，词性标记序列t1t2…tm，寻找该词序列上可能性最优的词性序列c1c2…cm。

Viterbi 算法有三个步骤： (1)初始化； (2)推导； (3)终止和读取路径(最优解)。下面给出标准的Viterbi算法：

定义一个局部概率θm(i)，它表示的是时刻t到达状态Ci的所有序列概率中最大的概率。再定义一个反向指针μm(i)，它用来表示的是时刻t到达最佳状态ci的路径。

(1) 初始化：t=1，表示所处状态ci的初始概率

(2) 推导阶段

递归计算通向词wm的词性标记ci的最佳路径

(3) 终止和读取路径(最优解)

终止，即到达最后一个词wm时的最佳词性标注

P=max[θt(i)]cm=argmax[θt(i)] 1≤i,j≤N

从最后一个词wm开始，回退求取每个词的最佳状态序列：

cm=θm+1(cm+1)m=M-1M-2, ………1

这样可以得到最优词性标序列c1c2…cm

5 实验与分析

维吾尔语中有名词、形容词、数词、代词、副词、量词、连词、语气词、叹词、后置词、动词等12个词类。新疆大学多语种信息技术实验室自然语言处理组对维吾尔语规则进行深入研究，结合实际文本制定了现代维吾尔语词性标注集(共计137个一级标注，71个二级标注，51个三级标注)，该标注集主要用于新疆大学多语种信息技术实验室将要研究的维吾尔语词法分析器、句法分析器、机器翻译等领域。本实验主要使用新疆大学自然语言处理实验室构建的维吾尔语语料库，此语料库已进行人工标注。为了更好地评价维吾尔文词性自动标注的结构，采用计算正确率。表达式如下：

词性自动标注正确率=(标注结果正确词数/语料的总词数)×100%

为了说明不同方法的优劣，所以选择了其他方法的实验结果与之比较。

实验结果如表2所示。

表2 维吾尔语词性自动标注算法比较结果

从上面的例子和表2可以看出，感知器算法对维吾尔语词性标注有更大的贡献。

6 总结

本文使用基于感知器算法的序列标注方法进行词性标注。本方法具有在线算法的优点，它可以充分利用多个任意的特征并每次使用一个训练实例对模型参数进行更新，在更新参数时每次将需要更新的参数重加1或者减1。这个优点对维吾尔语词性标注尤其是标注中处理词性歧义(兼类现象)有很大的贡献。目前根据维吾尔语的特点，选择考虑词的上下文信息的特征，使维吾尔语词性标注方法能够取得很好的标注效果。虽然标注效果好，但还是需要加其他的特征并用别的训练测试比例进行实验。因此今后将进一步扩充语料库规模，同时加入更多的特征信息进行研究。

[1] 吐尔根·依不拉音，阿里甫·库尔班.基于词典的现代维吾尔语词性自动标注系统的研究[A].中文输入技术发展历程及输入方案汇编(论文集)[C]，2006.11.

[2] Màrquez, Lluís, LluisPadro et al. A Machine Learning Approach to POS Tagging. Machine Learning 2000，39(1)： 59-91.

[3] Brill Eric. Transformation-based Error-driven Learning and Natural Language Processing: A Case Study in Part-of-speech Tagging. Computational linguistics.1995,21(4): 543-565.

[4] 周明, 吴进, 黄昌宁. 用于词性标注的一种快速学习算法对Brill 的基于变换算法的一项改进[J]. 计算机学报,1998 (4) : 357-366

[5] 买合木提·买买提，吐尔根·依布拉音.基于n‐gram 的维吾尔语词性标注研究[C]//第二届中国少数民族青年自然语言处理学术研讨会.2008 年10 月，中国安徽合肥.2008： 185-189.

[6] 艾斯卡尔·亚克甫,肖克来提,玉素甫·艾白都拉.维吾尔语词频统计子系统的体系结构[J].新疆师范大学学报 (自然科学版)2006,25(2): 16-20

[7] 艾山·吾买尔·维吾尔语词法句法分析关键技术的研究[D].博士论文，新疆大学，2010年.

[8] Ratnaparkhi A. A Maximum Entropy Model for Part-of-speech Tagging[C]//Proceedings of the Conference on Empirical Methods in Natural Language Processing. 1996, 1: 133-142.

[9] Dobrushin R L. Central Limit Theorem for Nonstationary Markov Chains[J]. Theory of Probability & Its Applications, 1956, 1(1): 65-80.

[10] Lafferty John, Andrew McCallum, Fernando CN Pereira. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. ICML 18(2001): 45-54.

[11] Manshadi V H, Gharan S O, Saberi A. Online Stochastic Matching: Online Actions Based on Offline Statistics[J]. Mathematics of Operations Research, 2012, 37(4): 559-573.

[12] Freund Y, Schapire R E. Large Margin Classification Using the Perceptron Algorithm [J]. Machine Learning, 1999, 37(3): 277-296.