Algorithm 版 (精华区)

发信人: Lerry (戒网·学习), 信区: Algorithm
标  题: 利用遗传算法实现词类标记集的优化
发信站: 哈工大紫丁香 (2001年11月20日21:25:35 星期二), 站内信件

利用遗传算法实现词类标记集的优化
孙宏林  陆勤*  俞士汶
*香港理工大学电子计算学系，香港，红墈
摘要：过去词类标记集的选择主要基于专家的经验知识，缺乏自动或半自动的方法来辅
助这一过程。本文提出了一种利用遗传算法来搜索优化的标记集的新方法。这种方法可
以在一个候选标记集集合中自动搜索一个最优或较优的标记集，并可根据应用的需求调
整参数以适应特定任务的需求。实验表明：遗传算法为标记集的选择提供了一种系统的
有效的辅助手段。
关键词：词性标注  词类  标记集  遗传算法
Using Genetic Algorithms for Optimizing Part-of-Speech Tagset
Sun Honglin  Lu Qin*  Yu Shiwen
*Department of Computing Hong Kong Polytechnic University
Abstract: POS tagset selection in the past was mainly done by experts using 
human knowledge manually, since there is no automatic or semi-automatic way 
to assist the selection process. This paper proposes a novel method to searc
h for an optimal POS tagset using genetic algorithms (GA). The experiment sh
ows that GA provides an efficient optimization of POS tagset and allows for 
the adjustment of parameters according to user requirement. It provides a sy
stematic way to help people in making an intelligent choice on the selection
 of a tagset.
Keywords: POS tagging, word class, POS tagset, genetic algorithm
一、        引言
任何自然语言的词汇都是一个很大的集合，一部中等规模的词典一般也有几万个词项。
这使得直接用词来描述语言的结构和建立语言模型十分困难，甚至难以实现。因而有必
要对词汇进行抽象，对词汇进行分类。分类的依据是词在句法、语义等属性上具有的共
性。至于到底归为多少类，并无一定之规，因为根据抽象程度的不同可以有各种不同的
结果。在过去十多年中，词性自动标注技术取得了很大的进展，统计方法的运用使得构
造一个高性能的自动词性标注系统变得相对容易，现在世界主要语言几乎都有不少这样
的标注系统可供使用。但是，所有的标注系统所使用的词类系统都是依靠人的知觉或经
验产生的（Halteren 1999）。由于对词类体系的合理性或合适性缺乏客观的评价，我们
在选择或定义一个词类标记集时就缺乏科学依据。同时，由于不同的应用系统对词性知
识有不同的需求，对于特定任务到底选择什么样的词类体系也是一个问题。这些问题都
属于词类标记集的评价和选择问题。我们曾讨论过词类标记集的评价问题(Sun et. al.
 1999)，这里我们将讨论词类标记集的选择问题。
词类标记集选择的一个直接的简单方法是：对几个候选的词类标记集，用同一标注系统
分别进行训练和标注实验，根据实验的结果从中选择一个可以一个最好的体系。但这种
方法的缺点是：候选标记集只能是有限的若干个，而可能的标记集几乎是无限的。而且
对每一个标记集都需要经过语料标注、训练、标注评测的过程，其中都需要人介入，工
作量很大。
本文针对这一问题，提出了一种基于遗传算法的词类标记集优选方法，该方法可以在一
个候选标记集集合中自动搜索一个最优或较优的标记集。该方法的基本思想是：首先定
义一个包含一个最大标记集和最小标记集的词类层级体系，然后选择一个语料库，用最
大标记集进行标注，然后对介于最大标记集和最小标记集之间的可能的标记集用一个评
价函数进行度量，利用遗传算法从中选择最优或较优的标记集。标记集的评价函数综合
考虑两个因素：（1）标记集的歧义度，用语料库中每个词例（token）的可能的标记数
数的均值来表示；（2）标记集的信息量，用标记集的熵（entropy）来表示。这一方法
的目的是帮助人们确定哪些标记应该包括在标记集中，标记应该排除在外。
本文第二节简单介绍遗传算法的基本思想，第三节给出问题的表示，第四节详细讨论标
记集评价函数，第五节给出实验结果，最后是全文总结。
二、遗传算法
遗传算法是根据自然进化中“适者生存”的原则提出的一种概率型优化方法（Holland 
1975）。这种方法适合于具有很大搜索空间的优化问题，下面简要介绍遗传算法的主要
思想，详细情况可参考（Goldberg 1989）和（Mitchell 1996）。
在遗传算法中，有一个包含个体xi的群体P = < x1 , ? , xn >，个体xi代表问题的一个
解，群体就是问题的一些解的集合。某一评价函数F(xi)被用来对这些候选解进行评价，
目标是优化该评价函数（搜索该函数的最大值或最小值）以解决给定的问题。这些候选
解通常用位串（bit string）的形式表示，借用生物学的术语称之为染色体(chromosom
e)。把解表示表示为位串的过程称为编码，编码后的每个位串就表示一个个体，即问题
的一个解。评价函数用以评价群体中每个个体的适应度(fitness)。在算法的每次迭代（
借用生物学术语称作一代）中，评价函数按照优化标准对每个个体xi进行度量，计算其
适应度fi ，适应度最高的个体被选择允许再生，以产生新的一代。下面是算法的形式化
描述：
{
      gen = 0;    //代号初始化
      initialize();  //初始化第一个群体
      evaluate(P(gen));  //P(gen) 是 第gen代的群体
      do {
         gen = gen+1;
         generate new population P(gen) from P(gen-1) through select, crosso
ver, and mutation; //通过选择、交叉和变异从P(gen-1)生成新的群体 P(gen)
         evaluate(P(gen));  // 评价P(gen)
      } while (gen <= maxgen)
    }
图1  遗传算法概貌
遗传算法中的再生过程主要包括三个遗传算子：（1）选择；（2）交叉；（3）变异。在
选择过程中，适应度高的个体被直接复制到下一代群体中。适应度越高的串，产生后代
的概率就越高。在交叉过程中，两个串的部分位（称为基因）进行交换从而产生一个新
串作为下一代的个体。变异用来随机地改变染色体的部分基因。交叉和变异的使用都有
一定的概率，分别称为交叉概率和变异概率。
三、问题的表示
词汇的分类可以用图2所示的树型结构来表示。树中的一个结点对应于一个词类标记，树
中若干个结点构成一个标记集。在遗传算法中，我们用一个位串来表示一个标记集。分
类树中除根结点以外的所有结点可以用一个位来编码，每一位有两种可能的值：1 表示
该结点在分类树中存在，0表示该结点在分类树中不存在。如果最大结点数为n，即最大
标记集M中有n个标记，那么，n个标记构成的所有可能的标记集构成M的幂集，其数量是
2n。我们的目的是在一个如此大的空间中搜索一个最优或较优的标记集，即找到适应度
最高的位串或染色体。
                      n        o    a ?           v
                  np  ng  nt  ns  nf   va  vi  vf  vt  vv  vw
                   ng0   ngl         vtz  vtb  vtp  vtx
图2  词分类树
由于分类树是树型结构，因此位串中各个位的的值并不是相互独立的。如果一个结点的
值为0，那么它的下位结点必为0。所以，在样本产生过程中违反以下限制的染色体将被
删除：
如果任一子结点非空，则父结点不能为空。
例如，附录中的标记集有107个标记，分为三个层级（根结点为空），如图2所示。在第
一层上有15个结点，第二、三层上分别有41和51个结点。整个标记集可以用图3所示的位
串来表示，该位串的长度为107。
np
 ng
 ?
 il
 npx
 ?
 utg
 n
 ?
 i
0       1     ?     40      41    ?      91    92     ?     106
图3  标记集的表示
例如，在图3中，第0位是“np”(专有名词)，如果第0位的值为0则表示标记集中没有此
标记，否则表示有此标记。
四、评价函数
对群体中的每一个个体， 要计算其适应度值作为在从前一代“进化”到下一代的过程中
选择的标准。在标记集优选问题中，需要考虑两个参数：（1）标记集对词性标注系统准
确率的影响；（2）标记集为下一步处理所提供的信息的丰富程度。词性标注追求的目标
是：词性标记包含的信息越丰富越好，同时，自动标注的准确率越高越好。显然，这两
个目标是有矛盾的：一方面，词类分得越粗，自动标注的准确率就越高，但词类标记提
供的信息量就越少；另一方面，词类分得越细，给高一级处理提供的信息也就越丰富，
但自动标注的准确率就越低。因此，我们需要在词类标记的信息量与自动标注的准确率
之间找到一个最佳的平衡点。以下将分别讨论这两个参数，并在此基础上提出一个综合
这两个参数的对词类标记集的评价函数。
4.1 标记集对标注准确率的影响
为了度量标记集对标注程序准确率的影响，我们可以使用直接的方法，即用不同的标记
集分别进行语料的标注、标注系统的训练和标注评测。如前所述，这种方法的缺陷是：
考察的标记集数量有限，而且费时费力。所以我们应该寻找间接的方法。我们曾经通过
实验证明，词类标记集的动态歧义指数（语料库中每个词可能的标记数）与标注系统的
准确率成正比例关系（Sun, et.al. 1999）。这一点也是比较容易理解的，因为词性标
注系统的主要工作就是进行词性的消歧，语料中每个词例的歧义指数越高，那么标注系
统面临的消歧困难也就越大，因而标注准确率也就越低。标记集TS的动态歧义指数（dy
namic ambiguity index，DAI）可以通过下面的公式从标注好的语料库中很容易统计得
到：
                   (1)
这里，N 是语料库中词型（word type）的数目，f(Wi) 是词Wi在语料库中的出现次数，
AMB(Wi)表示Wi可能的标记数。
在计算一个标记集的DAI之前，必须有用该标记集标注好的语料库。在遗传算法的进化过
程中，需要对大量的标记集进行评价，不可能为每一个标记集准备一个标注版本。但是
，如果语料库事先用最大标记集进行了标注，就可以利用最大标记集到其子集的多对一
（有些标记是一对一）的映射关系自动得到用新标记集标注的语料库版本。
4.2 标记集的信息量
词的分类可粗可细。分类越粗，得到的类就越少，同时给后一步处理提供的信息也就越
少。以名词的分类为例，我们分别考虑以下三种情形：
    （1）对名词不作进一步分类；
    （2）把名词分成两类：普通名词和专有名词；
    （3）在(2)的基础上，进一步把专有名词分成四个子类:人名、地名、机构名和其他
专名。
对于命名实体任务（Chinchor 1998）来说，很显然以上第三种情形可以提供更多的信息
，因而使命名实体任务变得容易得多。
    但要想准确地估计一个标记集所包含的信息量却并非易事，一个标记所包含的信息
在下一步的处理到底起什么作用，跟整个系统的理论体系有关，很难给出一致的度量。
我们这里所说的信息量跟标记的具体属性含义无关，它只是一个一般性的定量的度量，
而非定性的描述。
标记集所包含的标记数目可以作为一个度量标准，但它是静态的，不能反映每个标记对
系统的实际贡献，因为不同的标记在文本中出现的概率不同。因此必须考虑标记的实际
出现概率。从这个角度来说，熵(entropy)是对标记集信息量的一个合适的度量。
    从信息论的观点看，文本中的词性标记序列可以看成一个随机过程，标记集是一个
随机变量，标记序列中的特定标记就是这个随机变量的值。熵是随机变量平均不确定性
的度量，不确定性越高，熵值就越大。标记的可能的取值越少，我们在猜测序列中标记
的出现时得到的信息就越少；相反，标记可能的取值越多，那么我们得到的信息就越多
。标记集TS的熵可以通过下面的公式来计算：
                  (2)
这里，t是标记集TS中的一个标记，P(t)是t的出现概率，对数以2为基。
4.3 评价函数
在进化过程中，对每一个标记集都需要给出一个适应度的度量以指导再生过程。优化的
过程就是搜索最大或最小评价值的过程。
       正如在第一节中所讨论的，两个相关的参数（准确率和信息量）成反比关系。事
实上，我们通常要根据特定任务的需求在这二者之间找到一个平衡点。不同的任务对词
性标注有不同的要求，在某些情况下，准确率是优先考虑的因素，而在有些情况下标记
的信息量则更重要。所以，应该给这两个参数赋以不同的权值，而且权值可以根据应用
的要求进行调整。
       我们把标记集优选的过程看成一个适应度值最大化的过程。DAI和适应度值成反
比例关系，熵和适应度值成正比例关系，所以，标记集TS 的适应度可以定义如下：
       (3)
这里，DT 和HT 分别表示TS 的DAI和熵，Dmax和Dmin分别是最大标记集和最小标记集的
DAI，Hmax和Hmin 分别是最大标记集和最小标记集的熵值。这里，Dmax > Dmin ，Hmax
 > Hmin.。λ1和λ2 是两个参数的权值，λ1 + λ2 = 1。当优先考虑标注系统的准确
率时，可以给λ1赋一个大于0.5的值，如果优先考虑标记集的信息量，则可以给λ2赋一
个大于0.5的值。当λ1 = λ2 = 0.5时，两个参数的优先级相等。实际的取值可以在实
验中调试。显然，λ1越大，结果的标记集就越小，λ2越大，结果的标记集就越大。
五、实验结果
5.1 实现
实验中所用的标记集是一个汉语语料库所用的标记集（孙宏林等，1996）。该分类系统
是一个层级体系，分类树中共有107个结点，我们把这107个结点构成的标记集定义为最
大标记集。其第一级包含15个标记，我们把它定义为最小标记集，这15个标记包含在进
化过程中生成的任一标记集中。因此，共有92个变量。我们用长度为92的位串来表示这
92个结点，变异率为1/92，遵循这样的原则：染色体中的每一位有1/L的变异概率(L为染
色体中位的数量)（B?ck 1993）。交叉率为0.8，交叉采用了简单的单点交叉。
       为了评价每一个标记集，我们使用了以上语料库中的一个子集作为测试语料，其
中包含157篇选自《人民日报》的文章，共有203,499个词例。这些语料用以上的最大标
记集进行了标注，并经过细致的人工校对。因为最大标记集和生成的标记集之间有多对
一的对应关系，该语料库可以自动地转化为用其他标记集标注的版本，所以在程序运行
过程中不需要人的介入。
表1  部分标记集的适应度
Tagset
 DAI H Fitness(%)
 标记集说明
1
 2.42
 4.54
 50
 最大标记集，107个标记
2
 1.49
 2.83
 50
 最小标记集，15个标记
3
 1.74
 3.87
 61.83
 所有的第二集结点都不为空，所有的第三季结点皆为空
4
 1.62
 3.64
 63.43
 vt* and vw* 为空，其余结点皆不为空
    在评价函数中，选择λ1 = λ2 = 0.5，给标注的准确率和标记集的信息量以相同的
权值。表1给出了几个标记集的适应度，我们可以发现，在运用公式（3）中，Dmax和Dm
in 的值分别是2.42和1.49, Hmax 和Hmin的值分别是4.54和2.83。表1中的Tagset 1是最
大标记集，它包含107个标记，在所有的候选标记集中DAI 值和H值最大。对于最大标记
集，因为DT = Dmax 且HT = Hmax ，所以其适应度值等于λ2。 Tagset 2是最小标记集
，它在所有候选标记集中DAI 值和H 值最小。因为DT = Dmin 且HT = Hmin ，所以其适
应度值等于λ1。
5.2 实验结果
实验共生成了100代，表2给出了其中部分结果。在表2中，第一栏是代号，第二栏是群体
中最小的适应度，第三栏是群体中最大的适应度，第四栏是群体中所有标记集适应度的
均值，第五栏是已获得的最佳适应度，最后一栏是具有最佳适应度的标记集的位串表示
（用16进制表示）。标记按照附录中的序号编码，第0号标记对应于位串中的第0位，第
1号标记对应于位串中的第1位，其余依此类推。附录中序号为92-106的15
个标记是分类树中的一级标记，如前所述，我们规定这些包括在生成的任一标记集中，
所以不在位串中编码，因此位串的长度为92。
图4  进化过程中适应度的变化情况
图4显示了在前50代中适应度的变化情况，横轴上的11个点分别对应于代号1, 5, 10, 1
5, ? , 50。图中，横轴表示代号，纵轴表示适应度。上面的一条曲线表示最佳适应度的
变化情况，下面一条曲线表示平均适应度的变化情况。
从图4中我们可以发现，在进化过程中所生成的群体的最大适应度和平均适应度都随着代
号的增加而单调增加，而且在第23代基本达到收敛。
表2  部分实验结果
代
 最小适应度 (%)
 最大适应度(%)
 平均适应度 (%)
 最大适应度(%)
 标记集的位串表示 (hex)
1
 48.67
 56.24
 52.74
 56.24
 acfbc04b5f2881000574574
2
 48.92
 67.91
 55.83
 67.91
 e5e3fa974ad7880005b90dc
6
 53.44
 70.67
 67.52
 70.67
 e1e3ea974ad7000005790dc
16
 53.44
 70.67
 70.21
 70.67
 e1e3ea974ad7000005790dc
23
 54.40
 71.22
 70.28
 71.22
 b1e3ead75af4000001a9014
50
 54.66
 71.22
 70.95
 71.22
 b1e3ead75af4000001a9014
100
 54.66
 71.22
 70.89
 71.22
 b1e3ead75af4000001a9014
具有最高适应度的位串是b1e3ead75af4000001a9014，在第23代就得到。与该位串对应的
标记集所包括的标记在附录中的序号后加了星号。该标记集包含51个标记，在第一、二
、三级上分别有15、25和11个标记。下面以名词为例对得到的标记集进行简单的讨论。

在最大标记集中，在第一级上的名词在第二级上分为两类：普通名词和专有名词。专有
名词在第三级上进一步分为五类，普通名词在第三级上又分为两类：普通名词合理和名
词。其中离合名词是指一些动宾式复合词中间插入别的词语之后，原来在复合词内部只
作一个构词成分的语素不得不独立成为一个词的情形，如：
            如何 使 种植业 与 市场 接 上 轨
…… 向 老师们 敬 一 个 礼 ， 然后 他 深深 鞠 了 一 躬
“接轨”、“敬礼”和“鞠躬”本来都是一个复合词，由于中间插入了别的成分，使得
“轨”、“礼”和“躬”都变成了独立的词。但这些词和前面的动词显然有很强的依赖
关系，有的离了前面的动词之后根本就不可能存在，如“躬”。这些词和一般的名词显
然不同，如果把这些词单独加上标记，对下一步的句法和语义分析显然是有益的，但这
样会增加更多的兼类现象，如上例中的“礼”在上面的语境中它是一个离合名词，但在
别的情况下它也可以是一般的名词。是不是需要这一类要根据任务的要求综合考虑准确
率和信息量两个因素来作决定。在上面的实验中，我们设λ1 = λ2 = 0.5，即给予两个
参数相同的权重时离合名词就没有被选中，在另外的改变参数权重的实验中，我们发现
，当λ2大于0.7时，离合名词就总是被选中。而当λ2小于或等于0.7时，离合名词总是
不被选中。
在上面的结果标记集中，我们发现，原来的专有名词分为五个小类，在结果标记集中保
留了其中的四个。这主要是因为专名跟其他类兼类的现象比较少，因此尽管专名分得这
样细，但引起的词性歧义并不多。不过，这并不说明专名的归类就很容易了。事实上，
专名的细分类并不是一种语法分类，而是语义分类。专名的归类更多的要依靠词性标注
以外的技术来解决。
显然，所得到的标记集并不能直接应用，因为它在某些方面缺乏系统性。比如，在词缀
中，它选择了名词前缀（kh）、动词后缀（kv）和可能中缀（kp）,但没有选择名词后缀
（kn）。从词缀的系统性考虑，这显然是不合理的，所以有必要对得到的标记集进行适
当的微调。
六、结论
本文提出了一种利用遗传算法优选词类标记集的方法。该方法的目的是帮助人们根据任
务的需求选择一个最优或较优的标记集。该方法自动生成可能的标记集，并对对每一个
标记集给出一个评价函数值，在一个很大的标记集候选集中搜索评价函数值最大的标记
集。该评价函数考虑了两个参数：标记集的动态歧义指数和熵。参数的权值可以根据应
用进行调整。
本文给出了一个应用遗传算法进行标记集优选的实用方法。首先，在一个树型的分类体
系中定义一个最大标记集和最小标记集。然后选择一个语料库，用最大标记集进行标注
，并经过人工校对。在进化过程中，当一个新的标记集生成时，该语料库自动转化为用
新标记集标注的版本。我们的实验表明：该方法对词类标记集的优选提供了一种有价值
的辅助手段。

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]