2. 中国科学院大学, 北京 100049;
3. 新疆民族语音语言信息处理重点实验室, 乌鲁木齐 830011;
4. 新疆财经大学 计算机科学与工程学院, 乌鲁木齐 830012;
5. 中国科学院 计算技术研究所 智能信息重点实验室, 北京 100190
为维吾尔语和韩语形态分析建立了一种图状结构的判别式模型，该模型将语句的形态分析建模为形态成分的图状结构，通过灵活丰富的特征设计描述了词语内部形态成分之间以及分属相邻词语的形态成分之间的关联约束.相比传统的线性模型，图状模型更好地考虑了各形态成分之间的语言学关联，从而取得更高的整句分析性能.在维吾尔语和韩语上的实验结果表明，图状模型相比线性模型的性能有一定提升，形态分析词级准确率分别提升了4.4%和2.8%.
2. University of Chinese Academy of Sciences, Beijing 100049, China;
3. Xinjiang Key Laboratory of Minority Speech and Language Information Processing, Urumqi 830011, China;
4. College of Computer Science and Engineering, Xinjiang University of Finance and Economics, Urumqi 830012, China;
5. Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Science, Beijing 100190, China
A discriminant model of the graphic structure is established for the morphological analysis of Uighur and Korean language. The model builds the morphological analysis of the sentence into the graphic structure of morphological components, and describes the correlation between the morphological components of the words inside and the morphological components of the adjacent words through flexible and rich feature design. Compared with the traditional linear model, the pattern model is better to consider the linguistic association between the morphological components, and it is expected to achieve higher sentence analysis performance. The experimental results in Uighur and Korean indicate that the graphic model achieves certain performance improvement comparing with the linear model, and the word level accuracy of morphological analysis respectively increases by 4.4 and 2.8 percentage points.
形态分析是自然语言处理任务的基础.对于形态复杂的黏着语如东亚的韩语和中国的维吾尔语，其词语形态和构词规律比较复杂，目前形态分析准确率仍有较大的提升空间[1-4]，这类语言的词语通常由词干和若干起修饰作用的词缀两种形态成分构成，形态分析过程中通常会出现歧义切分问题，导致形态分析结果不准确.为解决此问题，研究者提出了两类模型：一类是基于统计的序列标注模型；另一类是基于有向图模型的形态分析模型.
基于统计的序列标注模型，将形态分析看做线性序列标注模型，常见的方法是借助于最大熵、条件随机场、感知机等模型对序列进行符号标注.典型的工作有Lee等[5]提出的运用最大似然概率的方法进行统计语料中出现的词干、词缀以及音节等，然后按照词素、音节等粒度进行韩语形态分析工作. Ablimit等[6-7]将形态切分看作序列标注，运用条件随机场进行有监督学习，设计特征来表述形态切分的规律.赵伟等[8]提出了基于条件随机场的蒙古语切分方法[8].
基于统计的有向图形态分析模型，在形态分析时建立词干与词干、词干与词缀相关联的词图，通过对词图的分析获得标注结果.典型的工作有麦热哈巴·艾力等[3]提出的维吾尔语词法分析有向图模型，该方法建立了词干决定词干，词干决定词缀的有向图模型，以求解最优的形态分析序列. Jiang等[9]提出一种基于词图中文分词和词性标注的重排序算法，对生成的词图进行粗剪枝，融入非局部特征进行解码获得分词和词性标注结果.华却才让[10]利用音节特征感知机模型进行藏文词语粗切分并生成词图, 然后在解码时利用基于词典的加权方法和最短路径算法, 选择最优有向路径，生成最优分词结果.赛迪亚古丽·艾尼瓦尔等[1]以N-gram模型为基本框架，根据维吾尔语的构词约束条件，提出了融合词性特征和上下文词干信息的维吾尔语词干提取模型.
总的来说，以上方法从词本身考虑，考虑的上下文信息有限.以句为单位将形态分析建模为字母的序列标注问题，虽较为直观，但这种方式只能考虑特定窗口内的上下文信息，无法刻画更大范围内形态元素之间的语言学关联.因此，笔者针对词干词缀间的连接特性，建立了更贴合黏着语构词规律的图状模型，是针对黏着语构词特性的崭新建模方式，具有一定的理论价值.
1 形态分析图状模型描述图状模型的结构，就要与传统的线性建模方法进行对比.图状建模的优点在于它可以刻画更大范围内形态元素之间的关联约束关系，比只考虑邻近元素的线性建模方法性能更好.在图状建模的基础上，如何进行有效地特征设计是关键.
1.1 图状建模最直观的建模方式是将句中词语的形态元素表示为一个线性序列，赵伟等[8]对蒙古语词语切分时，对单词内的每一个字母进行标注，只提取当前字母左右几个字母窗口范围内的特征.对于一个黏着语词语，词干前面或后面可能缀接一个或多个词缀，运用线性模型使得词干之间的距离变长，同一词内不相邻形态元素之间的关联无法进行直接有效地刻画，更不必说不同词之间相隔更远的形态元素了，在相当程度上弱化了统计模型的能力，如图 1所示.
|
图 1 形态切分线性建模 |
还有一种直观的方式是将之建模为树状结构，赛迪亚古丽·艾尼瓦尔[1]把词的形态切分视作一棵树, 树根表示词, 树叶分别表示词素.该建模方式的优点是拉近了相邻词词干的距离，使得词干之间的语言学关联，可以通过对词干元组设置参数或设计特征的方式进行有效地建模，如图 2所示.相比线性建模，树状建模更好地考虑了词干之间的联系.但事实上，对于大多数的黏着语，邻近词的词缀与词干之间以及词缀与词缀之间同样存在语言学关联.
|
图 2 形态切分树状建模 |
笔者提出了一种可以有效刻画邻近词中任意形态元素语言学关联的图状建模方式，如图 3所示.在图状模型中，节点代表形态元素包括词干和词缀，节点之间的边表示形态元素之间的关联关系.对于同一词内和相邻词间的任意一对形态元素，都存在直接的边进行关联.因此，图状建模可以视为前面提到的树状建模扩展，而树状建模又可以视为线性建模的扩展.借助图状建模，可以针对可能的形态元素间的关联关系，自由灵活地设计相应的参数(生成式方法)或特征模板(判别式方法).相比于生成式方法，更便于判别式方法通过丰富灵活的特征设计，充分挖掘黏着语的构词和构句规律；即以判别式方法进行形态分析图状模型的建模、训练和解码.
|
图 3 形态切分图状建模 |
给定待分析语句x，判别式图状模型的解码算法输出最可能的分析结果
| $ \begin{array}{l} \tilde y = {\rm{argma}}{{\rm{x}}_{y \in {\rm{GEN}}(x)}}S\left( {y|\mathit{\boldsymbol{a}}, \mathit{\Phi}, x} \right) = \\ \;\;\;\;\;\;\;\;\;\;\;{\rm{argma}}{{\rm{x}}_{y \in {\rm{GEN}}(x)}}f\left( {x, y} \right)\mathit{\boldsymbol{a}} \end{array} $ | (1) |
其中：a为模型的训练算法输出的权重向量，f(x, y)a为特征向量f(x, y)和权重向量a的内积.权重向量通过一定的训练算法习得，可采用如下感知机算法.
1 Input:训练实例(X, Y)
2 a←0
3 for t←1… T do ▷T轮迭代
4 for (x, y)∈(X, Y) do
5
6 if
7 a←a+Φ(x, y)－Φ(x,
8 end if
9 end for
10 end for
11 Output:权重向量a
感知机训练过程旨在学习一个从输入x∈X到输出y∈Y的判别式模型，其中X是训练语料的句子集合，Y是对应的标注结果集合.函数GEN(x)采用维特比算法得到当前输入语句x的候选标注结果，Φ(x, z)为输入句子的特征向量，然后计算Φ(x, z)a得分，选择最高的标注序列z，y表示正确的标注序列，函数f将训练实例(x, y)∈(X, Y)映射到对应的特征向量f(x, y)∈Rd，d是特征向量的维度.为获得更好的训练效果，在上述算法的基础上采用平均参数技术[11].其中，GEN(x)采用的维特比算法是一种动态规划方法，用于求解隐马尔科夫模型中状态序列的问题，算法遵循从左到右依次计算图中每一个可能的状态节点，同时保存下具有最大概率的节点，最后通过该节点进行依次回溯求出最优的状态序列标注, 维特比算法如下：
1 p(source_state)=1
2 for observation i from source to destination
3 for each possible state n of observation o
4 p(n)=0, previous_state(n)=Ø
5 for each edge e directed to n from n1
6 p1(n)=p(n1) * transition_prob(n1|n) * output_prob(o|n)
7 if p1(n)>p(n) then
8 p(n)=p1(n)
9 previous_state(n)=n1
10 endif
11 endfor
12 endfor
13 endfor
14 init best_tag_sequence is a empty array of states
15 state n is the destination state
16 repeat until n is the source state
17 push previous_state(n) to the head of best_tag_sequence
18 assign n=previous_state(n)
19 return best_tag_sequence
循环语句用来计算维特比图中每个节点的概率值.概率值有两部分：一部分是转移概率，即从上一个状态转移到当前状态的概率；另外一部分是输出概率，从当前状态到当前观察值的概率.其中每个观察值的状态值就是每个字母的标注集合，观察值就是字母本身.
1.2 特征设计相比于参数训练算法，特征设计通常是影响系统最终性能的关键因素.它能够正确反映句中形态元素之间的语言学关联约束，具有良好的描述能力和泛化能力的特征模板，正是特征设计所要解决的问题.基于之前描述的形态分析图状模型，图中的任意一个节点对应为一项一元特征，一条边及其连接的2个节点对应为一项二元特征.一元特征描述的是一个形态元素作为特定词句法角色的事件，二元特征则描述2个形态元素作为相应词句法角色事件之间的关联约束.采用的特征模板如表 1所示.
|
表 1 形态分析图状模型特征模板 |
表 1中，s0、s－1和s－2为由形态元素构成的向量，分别表示当前词及其前面2个词的候选分析结果，s*表示这3个向量顺序拼接而成的向量.函数P表示形态元素在分析结果向量中的相对位置.对于向量中的首尾元素，函数分别返回L(left)和R(right)，对于其他元素则返回M(middle).函数D返回形态切分结果向量中2个形态元素的距离，对于相邻的形态元素返回N(near)，对于不相邻的情形则返回F(far).
2 词语形态候选生成为待分析语句中的每个词语枚举出可能的形态分析候选，是形态分析图状模型的前序阶段.给定可能的词干和词缀集合，一个词的形态分析候选可以通过简单的递归枚举求得.但这带来了两方面的问题：对于形态切分歧义严重的词，可能会生成过多的不合理形态分析候选；而对于未登录词，则无法生成正确的形态分析候选.下面描述一种高效且具有泛化能力的形态拆分算法，该方法借鉴基于字符分类的汉语分词原理，将词语形态切分建模为词内字母的序列标注问题.
对于许多黏着语而言，音变现象广泛存在，即由形态成分构成词时发生诸如元音脱落等词形变化.因此，需要还原出各形态成分的原始形态，这一过程即音变还原.同样地，为摆脱对语言学规则设计的依赖，将音变还原也建模为字符分类问题.通过从标注语料中自动化地获取音变还原规律，并抽取相应的判别式分类实例，可以自动化地构建高效的音变还原模型.
形态拆分为上层的图状模型，提供语句中各词语的形态分析候选.对于存在音变现象的语言，则需在形态拆分之前先进行音变还原.下面介绍基于字符分类原理的形态拆分和音变还原.
2.1 形态拆分对于给定的待切分词语
| $ W = {C_{1:n}} = {c_1}{c_2} \ldots {c_n} $ |
其中ci(1≤i≤n)为W中的第i个字母，n为字母序列的长度.词干词缀切分即为字母序列的划分问题：
| $ {c_1}{c_2} \ldots {c_n} \to {c_{1:{e_1}}}{c_{{e_1} + 1:{e_2}}} \ldots {c_{{e_{m-1}} + 1:{e_m}}} $ |
其中：em=n，字母序列c1:n划分为m个子序列，每个子序列对应为一个形态元素.一般而言，第1个子序列c1:e1是词干，剩余的字母序列是词缀.
这是典型的序列划分问题，可以用序列标注的方式进行建模.将其与基于判别式字符分类的汉语分词进行类比，将每个字母ci分类为如下4种类别之一.
b：词干或词缀的开始字母
m：词干或词缀的中间字母
e：词干或词缀的结束字母
s：单字母作为词干或词缀
当对整个词的字母序列完成标注之后，标注为bm*e或者s的字母子序列即为词干或词缀，相应地得到一个候选的词干词缀切分结果.以维语为例, 单词之间加#，单词内的字母之间加空格，满足线性结构，对每一个字符提取上下文特征信息，用bmes标注成序列，然后切分为词干+词缀的形式，如图 4所示.
|
图 4 基于字符分类的维吾尔语形态拆分示意图 |
对字符分类所采用的特征，是以该字符为中心的特定长度窗口中的字符元组.所用的特征模板列见表 2.其中，c0表示当前考察的字母，c-i/ci表示c0左边/右边的第i个字母.借助这些特征模板，从训练语料中抽取字符分类实例，以此训练字符分类器.
|
|
表 2 形态拆分和音变还原特征模板 |
考虑到词干词缀切分的歧义性，为待分析语句中的每个词及其变形形态都生成N个最佳的切分方案.通过为N选择合适的值，可以在保证分析速度的同时取得较高的分析精度.
2.2 音变还原黏着语普遍存在音变现象，词干缀接词缀时，有些元音和辅音会弱化为另外一个音，或者出现丢失(脱落)和增加(增音)等情况.这些音变现象给黏着语的形态分析带来了较大困难，需要在形态拆分之前先进行音变还原.通过语言学规则的方式进行音变还原耗时耗力，而且需要相关语言专家知识的支撑.为实现更好的语言无关性，提出一种自动化的基于字符分类的音变还原方法.
基于字符分类的音变还原模型，将音变还原建模为对词中每个字母进行判别式分类的问题.黏着语词语可以看成它所包含字母的线性序列.假设音变现象会发生在每个字母上，每个字母既可以保持不变，即变为其自身，又可以变为其他形式(包括变为空的情形).一个字母在音变过程中变为何种形式，是可以由其上下文信息预测得知的.由此，音变还原问题建模为字符的判别式分类问题.
以字符分类模式求解音变还原，需要知道词中的每个字母在音变之后转换为何种字母串(它自身，空串或其他字符串).以维吾尔语为例，首先要确定音变还原前后词内字母的对应关系，如图 5所示.借鉴最短编辑距离算法的思想提出一种词内字母对齐算法，音变前的一个字母可以对应到音变后的0个或多个字母，如果对应到一个字母且恰好为该字母本身，则得分加1，否则得分为0.通过类似于求解最短编辑距离的动态规划算法，即可快速找到得分最高的匹配模式.在动态规划搜索过程中，不仅记录当前最高的匹配得分，还要记录此得分对应的匹配模式，以便搜索结束后回溯出最优路径对应的整个词的匹配模式.
|
图 5 音变还原前后词内字母对齐 |
在经过字母对齐的词语集合上，可以提取出用以判别式分类的训练实例.采用与基于字符分类的形态拆分模型同样的特征模板，并同样适用最大熵工具包训练分类器.为提高形态还原的召回率，使用类似于立方体剪枝的策略，为待分析词生成多个最佳形态还原候选.
3 实验以韩语和维吾尔语为例进行形态切分实验.韩语的形态切分语料来自网络和人工标注语料，共有54 358句，各随机抽取1%的句子作为开发集和测试集，剩余的全部作为训练集.维吾尔语语料来自新疆大学多语种重点实验室标注的维吾尔语百万词词法分析语料库，共有72 739句，类似地，各随机抽取1%的句子用作开发集和测试，剩余的语句用以训练.
关于形态切分的评价指标，有基于整词的评估模式，也有将词干和词缀分别对待的模式.笔者采取最严格的评测方式，即以整词为单位进行评估.对于一个黏着语词语，只有当其词干和词缀全部识别正确时才算是分析正确的.整词正确率Pw定义为分析正确的词占全部词语的比例.考虑到有些应用更关注词干识别精度，采用词干正确率Ps定义为正确识别出词干的词占全部词语的比例.
音变还原和形态拆分为上层的图状模型提供形态拆分候选，首先验证这两个模块的性能.对于音变还原和形态拆分抽取的训练实例，采用最大熵工具包MaxEnt[12]训练分类器.高斯先验设置为1.0，剪枝阈值设置为0，其余参数保持默认，进行200轮L-BFGS迭代训练.
图 6和图 7分别显示了音变还原和形态拆分分类器输出N-best时的Oracle(N-best列表包含正确答案的可能性)情况.当N取较小的值时，音变还原和形态拆分分类器的Oracle就已经非常高了；当N>3时，Oracle的值趋于平稳.因此，在后续图状模型的实验中，将这2个模块的N-best数量都设置为3，即针对每个词语，音变还原模块输出最多3个候选，随后的形态拆分模块为每个音变还原候选生成最多3种拆分方案.
|
图 6 音变还原分类器Oracle曲线 |
|
图 7 形态拆分分类器Oracle曲线 |
图状模型的性能如表 3所示.将音变还原模块和形态拆分模块串联起来，即为最直观和最常用的基于序列标注的形态切分模式，这可以作为图状建模策略的基线模型.相比基于字母序列标注的基线模型，基于形态元素的图状模型取得了一定精度的提升.在韩语上，形态分析词级准确率提升了2.8个百分点，从91.01%提升到93.79%；在维吾尔语上提升了4.4个百分点，从91.26%提升到95.67%，尤其超过了基于树状模型的维吾尔语形态切分性能.
|
|
表 3 形态分析图状模型性能 |
在维吾尔语形态分析过程中，论证了图状建模比树状建模性能更优，从表 3和麦热哈巴的树状建模实验[3]对比可以看出，赛迪亚古丽·艾尼瓦尔等[1]采用自己人工标注的10 025条维吾尔语句中9 025句作为训练语料，剩下的1 000句作为测试语料，使用N-gram模型+词性特征+上下文词干信息，词级准确率为96.6%，但实验所使用的语料库与本文不同，规模也较小，不具有可比性.因此，无论在使用相同语料库方面，还是在语言模型建模方面，麦热哈巴等[3]的实验较其他实验更具有可比性.
4 结束语针对黏着语的词句法特性，为形态分析任务建立了一种图状结构的判别式模型.该模型将黏着语语句的形态分析结果建模为以形态成分为节点的图状结构，并通过丰富的特征描述词语内部形态成分之间以及分属相邻词语的形态成分之间的关联约束.同时，将词语形态拆分和音变还原都建模为基于字符分类的序列标注问题，摆脱了对语言学规则的依赖，从语料库中自动学习到更具覆盖度和泛化性的形态切分和音变还原规律.在韩语和维吾尔语上的实验表明，图状建模的形态分析比线性建模方式取得了一定性能的提升.
| [1] |
赛迪亚古丽·艾尼瓦尔, 向露, 宗成庆, 等. 基于多策略的维吾尔语词干提取方法[J]. 中文信息学报, 2015, 29(5): 204–210.
Sediyegvl Enwer, Xiang Lu, Zong Chengqing, et al. A multi-strategy approach to uyghur stemming[J]. Journal of Chinese Information Processing, 2015, 29(5): 204–210. |
| [2] |
徐春, 杨勇, 蒋同海. 基于机器翻译的维吾尔语形态分析研究[J]. 计算机工程与应用, 2017, 53(14): 138–142.
Xu Chun, Yang Yong, Jiang Tonghai. Research on machine translation based uyghur morphological analysis[J]. Computer Engineering and Applications, 2017, 53(14): 138–142. doi: 10.3778/j.issn.1002-8331.1604-0119 |
| [3] |
麦热哈巴·艾力, 姜文斌, 王志洋, 等. 维吾尔语词法分析的有向图模型[J]. 软件学报, 2012, 23(12): 3115–3129.
Mairehaba·AILI, Jiang Wenbin, Wang Zhiyang. Directed graph model of uyghur morphological analysis[J]. Journal of Software, 2012, 23(12): 3115–3129. |
| [4] |
张海波, 蔡洽吾, 姜文斌, 等. 基于联合音变还原和形态切分的形态分析方法[J]. 中文信息学报, 2014, 28(6): 10–16.
Zhang Haibo, Cai Qiawu, Jiang Wenbin. Morphological segmentation model for morphological analysis[J]. Journal of Chinese Information Processing, 2014, 28(6): 10–16. |
| [5] | Lee D G, Rim H C. Probabilistic modeling of korean morphology[J]. IEEE Transactions on Audio, Speech, and Language Processing, 2009, 17(5): 945–955. doi: 10.1109/TASL.2009.2019922 |
| [6] | Ablimit M, Kawahara T, Pattar A, et al. Stem-affix based Uyghur morphological analyzer[J]. International Journal of Future Generation Communication and Networking, 2008, 9(2): 59–72. |
| [7] | Ruokolainen T, Kohonen O, Virpioja S et al. Supervised morphological segmentation in a low-resource learning setting using conditional random fields[C]//Proceeding of the Seventeenth Conference on Computational National Language Learning. Sofia: Association for Computational Linguistics, 2013: 8-9. |
| [8] |
赵伟, 侯宏旭, 丛伟, 等. 基于条件随机场的蒙古语词切分研究[J]. 中文信息学报, 2010, 24(5): 31–35.
Zhao Wei, Hou Hongxu, Cong Wei. Research on conditional random fields based mongolian word segmentation[J]. Journal of Chinese Information Processing, 2010, 24(5): 31–35. |
| [9] | Jiang W, Mi H, Liu Q. Word lattice reranking for Chinese word segmentation and part-of-speech tagging[C]//Proceedings of the 22nd International Conference on Computational Linguistics. Manchester: [s. n. ], 2008: 385-392. |
| [10] | 华却才让. 基于树到串藏语机器翻译若干关键技术研究[D]. 西安: 陕西师范大学, 2014. |
| [11] | Michael C. Discriminative training methods for hidden markov models: theory and experiments with perceptron algorithms[C]//Proceedings of EMNLP, 2002, Pennsylvania, USA, 410(21-23): 1-8. |
| [12] | Le Zhang. Maximum entropy modeling toolkit for python and C++[EB/OL]. (2011-09-09)[2017-05-06]. http://homepages.inf.ed.ac.uk/lzhang10/maxent_toolkit.html |