基于改进Tri-training算法投票机制的中文问句分类

王 雷,孙中全

(滁州职业技术学院,安徽 滁州 239000)

0 引言

问答系统由问句分类、信息检索、答案抽取三大部分组成,问句分类作为问答系统的初始环节,其能否正确地对问句进行分类会直接影响到后续的答案抽取环节[1],从而直接影响问答系统的性能。目前,问句分类的方法主要有两大类[2-3]:(1)基于人工规则的方法;(2)基于机器学习的方法。其中,基于机器学习的方法是目前问句分类的主流。机器学习方法[4]包括监督学习、无监督学习和半监督学习。在问句分类方面,监督学习的方法主要利用已标记样本,忽略未标记样本对于问句分类的意义,分类正确率难以提升,且分类灵活性较低。半监督学习是一种综合利用已标记样本和未标记样本进行学习的方法,能获得较好的学习泛化能力和学习效果。目前该类方法开始应用于问句分类中,在英文问句分类方面,AFRA等[5]采用基于机器学习的方法,使得孟加拉问题分类取得了很好的效果;SAEEDEH[6]将无监督潜在狄利克雷分配方法用于问题分类;FAIZ等[7]利用问题分类和答案抽取方式,搭建了烹饪问答系统;SEYHUMS等[8]基于Word2vec特征的深度学习方法用于问题分类研究。在中文问句分类方面,YU等[9]利用半监督学习中的Co-training算法将中文问句进行分类,张志满[10]利用深度学习算法将健康领域的中文问句进行分类。在半监督学习的诸多分类算法中Tri-training算法[11]不仅在其他知识领域得到了很好的应用,而且在自然语言处理领域有良好的分类效果。其中,任正雄等[12]提出了一种基于Tri-training的制冷系统半监督故障诊断方法,改善了制冷系统故障诊断性能;董昊旻等[13]利用半监督学习下的Tri-training算法,有效地提高了驾驶风格分类的准确率;高嘉伟等[14]提出一种基于Tri-training的半监督多标记学习文档分类算法,在文档分类中取得了良好的效果;李帅克等[15]基于Tri-training算法来保证自动标注数据的质量,进而提升跨领域依存句法分析性能。因此本文将Tri-training算法应用于中文问句分类。

原始Tri-training算法在三个分类器均给出了不相同的分类结果时,会默认第一个分类器给出的结果为分类器模型的最终结果,则会出现以点代全的问题。针对此问题,本文通过对Tri-training算法[16]的理论分析,受于重重等[17]提出的DSCC(semi-supervised collaboration classification algorithm with enhanced difference)算法的启发,提出一种基于平时优秀的投票机制的Tri-training算法。

1 Tri-training分类算法投票机制的改进

1.1 算法描述

在三个分类器均给出了不同的结果时,原始的Tri-training算法默认第一个分类器给出的结果为分类器模型最终结果,本文基于统计学思想,提出一种改进的投票机制算法,通过找出平时优秀的分类器给出的结果,作为分类器模型的最终分类结果。基本流程如图1所示。

图1 改进的Tri-training算法流程

该算法的核心思想是对于完成迭代训练得到的最新训练集样本,在给出分类结果以后,对每个分类器进行一个正确分类数的统计,记为Ci。所谓的正确分类数,即分类模型在迭代训练和测试分类的过程中,每个分类器分类正确的中文问句数。哪个分类器分类正确的中文问句数越多,就称这个分类器最好或者最优秀,即为平时优秀的投票机制。改进Tri-training算法的投票机制详细步骤如下:

输入:有标记样本集L,未标记样本集U,测试集T,分类器H

输出:测试集T通过分类模型分类之后的分类精度

1)根据L训练分类器

2)利用分类采样方法将L分为3份,形成3个有标记样本集Li(i=1,2,3)

3)用Li(i=1,2,3)分别去训练3个分类器Hi(i=1,2,3)

即Hi(i=1,2,3)←Learn(Li)

4)设定分类器初始分类错误率ei←0.5

5)对未标记样本集进行预测分类。对于一个分类器而言,如果另外两个分类器对未标记样本预测分类结果一致,即将此样本加入到该分类器的有标记样本集中,并且对该分类器进行迭代训练

6)重复3) ～ 5) 步骤,直至分类错误率ei不再发生变化,即分类器迭代训练结束

7)设定分类器正确分类数Ci(i=1,2,3),将正确数最大的分类器记为最优秀分类器

8)用迭代训练好的分类器将测试集中样本分类,测算分类器的分类正确率

9)算法结束

1.2 算法分析

1.2.1 改进投票机制的Tri-training算法原理

该投票机制的核心思想是对于完成迭代训练得到的最新训练集样本,在给出分类结果以后,对每个分类器进行一个正确分类数的统计,记为Ci。所谓的正确分类数,即为分类模型在迭代训练和测试分类的过程中,每个分类器分类正确的中文问句数。哪个分类器分类正确的中文问句数越多,就称这个分类器最好或者最优秀。那么在分类模型中,三个分类器给出不同的分类结果时,就可以根据这个正确分类数,选出最优秀的分类器给出的结果作为分类结果,而不是默认第一个分类器的结果作为分类结果。

关于Tri-training算法投票机制的改进方面,于重重等[17]研究了改进的投票机制方法,提出了一种基于分类准确率的投票法。这种投票机制是在分类结果各不相同时,用分类器模型中每一个分类器分别对最初始的样本训练集进行分类测试,将每个分类器分类结果的错误率记为ei,最后将错误率最低的那个分类器的结果作为分类器模型的预测结果。本文将对原始投票机制、基于分类准确率的投票机制和基于平时优秀思想的投票机制这三类方法进行实验验证,在分类结果数据对比下验证方法有效性。

1.2.2 改进投票机制的Tri-training算法有效性分析

针对改进投票机制的Tri-training算法,本文针对以下两方面的进行有效性分析。

1.2.2.1 不会出现“以点代全”的情况

由前文可知,原始Tri-training算法的分类器模型中的投票机制已描述得很清楚。在三个分类器给出的结果中,有相同的分类结果出现时,毫无疑问,这个相同的分类结果就是原始Tri-training算法分类器模型的给出的最终分类结果。若在三个分类器均给出了不相同的结果,原始的Tri-training算法会默认第一个分类器给出的结果为分类器模型的最终结果。那么,这种情况属于以点代全的情况。在正常情况下,第一个分类器给出的结果不可能每次都是正确的,而且其分类精度也不一定比另外两个分类器的分类精度高。这就很可能在一定程度上降低分类器模型的分类精度。这一点也是本文改进原始Tri-training算法中投票机制的最终出发点。基于统计学的原理,在分类器模型进行迭代训练和测试分类的过程中,对每个分类器进行一个分类正确数的统计,记为Ci。即在程序中添加一个计数器,此计数器用来在三个分类器给出不相同的结果时,选出最优秀的分类器,用其给出的结果作为分类器模型的分类结果,这就避免了上面所述的以点代全的现象。

1.2.2.2 对分类结果的选择和程序时间复杂度的控制

于重重等[17]提出的基于分类准确率的投票机制是在三个分类器给出不相同的结果时,用分类器模型中每一个分类器分别对初始样本训练集进行分类测试,将每个分类器分类结果的错误率记为ei,最后将错误率最低的那个分类器的结果作为分类器模型的分类结果。这种投票机制虽然避免了以点代全的情况,但并不是最可取的方法,而且这种投票机制因需让每个分类器分别对初始的样本训练集进行分类测试,这同时就会增加算法的复杂度和时间开销。本文提出的改进的投票机制方法,只需在程序中增加一个计数器,用来记录每个分类器分类出的正确问句数,根据分类正确数可以选出平时最优秀的分类器。因此,相对于基于分类准确率的投票方法,其算法的复杂度和时间的开销都会相对小一点。

本文的投票机制可以处理原始投票机制和基于分类准确率投票机制存在的一些不足之处,比原始投票机制和基于分类准确率投票机制具有更合理的选择性,同时比基于分类准确率投票机制有更佳的判断、更高的效率及更低的时间开销。

2 基于改进Tri-training算法的中文问句分类

基于改进Tri-training算法建立半监督分类模型。模型主要包括原始数据导入、数据预处理、协同训练和分类结果输出四个部分,其流程如图2所示。

2.1 数据预处理

一般来说,中文问句集不是分类算法中所用分类器需要的数据格式。对于中文来说,中文问句包含词袋、词性、命名实体和依存关系等基本特征。数据预处理部分主要是将中文问句中的基本特征提取出来,并选择合适的基本特征将中文问句中所包含的属性进行量化,形成分类器所需的数据格式。本文利用程序实现数据预处理,在建立的中文问句分类模型中,选用中文问句的词袋这一基本特征,旨在验证改进Tri-training算法对于中文问句分类的有效性。对于中文问句中不同的基本特征组合,不再一一验证。

2.2 协同训练

协同训练部分利用数据预处理得到的中文问句集,对分类器进行训练、测试。本文在基于类别分类采样的Tri-training算法基础上,运用三个分类器协同训练。基于类别分类采样方法将有标记样本集中的每一类中文问句提取出来,然后分别对提取出来的每类问句进行随机采样,形成三个有标记的样本集。用形成的三个有标记样本集分别去训练三个分类器,再利用训练得到的三个分类器协同对未标记样本集中的样本进行标记。对于一个分类器而言,如果另外两个分类器对这些没有标记的样本标记了相同的分类结果,这些样本则被当作已标记样本,加入到该分类器有标记样本集中参加对该分类器进行迭代训练。对每个分类器而言,均如此进行迭代训练,直至分类器不再更新,则迭代训练结束。

3 实验结果及分析

3.1 实验数据

本文实验数据主体来自哈尔滨工业大学的中文问句集[18]。该问句集分为六大类,共包含6 266个已标记好问句类别的问句。在该问句集的基础上,又利用网络资源通过人工方式将每类问句数量进行扩展,扩展的总问句数为4 000个。将扩展的中文问句加入到哈尔滨工业大学的中文问句集中,形成新的中文问句集。

3.2 实验设置

3.2.1 样本集分配

针对哈尔滨工业大学的中文问句集,选用其中25%的数据作为测试样本集,剩余75%的数据作为训练集,其中,训练样本集中未标记样本的比率r依次选用20%、40%、60%、80%。将本文扩展的问句集加入到哈尔滨工业大学的中文问句集,形成一个新的问句集,再将此问句集按照哈工大中文问句集的样本分配比例进行实验数据分配。

3.2.2 分类器选择

本实验选用了三个SVM分类器,旨在验证基于问句类别的分类采样方法对问句分类的影响。对于其他不同分类器的组合用法对分类实验的效果影响,李心磊等[19]已经通过实验验证。

3.2.3 评价指标

本实验共有如下两个评价指标。

(1)对分类结果进行测试时,采用分类正确率A作为评价标准,其定义如下:

其中,N为测试集中正确分类的问句数,M为测试集中总的问句数。

(2)对几个分类算法运行时间进行比较时,该实验的评价标准为算法的运行时间T(单位为s)。

3.3 问句分类实验及结果分析

3.3.1 在中文问句集中不同分类算法的比较

采用图2所示的分类模型,利用中文问句集进行实验。分别得出在四种不同的未标记比率下,原始投票机制的Tri-training算法、基于分类准确率投票机制的Tri-training算法以及基于平时优秀投票机制的Tri-training算法在此问句集上的分类精度(表1)。其中T1代表原始投票机制的Tri-training算法,T2代表基于分类准确率投票机制的Tri-training算法,T3代表平时优秀投票机制的Tri-training算法。

表1 三种算法在四种不同未标记比率下的分类精度

3.3.2 在中文问句集中不同分类算法所需时间开销的比较

在前文建立分类模型的基础上,本文在算法的程序代码中添加一个程序运行计时器,用来记录三种算法分类完成所需的时间开销。在三种算法分类完成时,分别记录三种算法在分类时所需的时间开销。实验结果如表2所示。

表2 三种算法在四种不同未标记比率下分类时所需时间开销

根据表1试验结果可以看出,基于分类准确率的投票机制算法和基于平时优秀的投票机制算法的分类精度,均高于原始的投票机制算法的分类精度,当r=80%时,分别高出0.13%和0.15%。虽然改进的投票机制算法比原始的投票机制算法的分类精度没有明显提高,但其也可以避免以点代全的情况。从实验数据也可以看出,基于分类准确率投票机制的Tri-training算法和平时优秀投票机制的Tri-training算法的分类精度相差不大。出现以上这两种情况,也是不难理解的。本文分析可能有两种原因:一是最优秀的分类器恰好就是第一个分类器;二是中文问句集的规模还不够大。

根据表2实验结果可以看出,原始的投票机制算法的运行时间开销最小。基于平时优秀投票机制的Tri-training算法相对于基于分类准确率投票机制的Tri-training算法的运行时间开销明显要少一点,其平均少了7 s。虽然基于平时优秀投票机制的Tri-training算法花了一点运行开销时间,但是也避免了以点代全的情况。总而言之,该算法的提出还是有价值的。

因此,改进原始的投票机制算法对于中文问句分类而言,其分类精度能够得到一定程度的提高。基于平时优秀投票机制的Tri-training算法与基于分类准确率投票机制的Tri-training算法相比较而言,虽然两种算法的分类精度相差不大,但前者相比后者的时间开销少一点。所以基于平时优秀投票机制的Tri-training算法还是具有一定优势的。

4 结语

本文提出了基于平时优秀投票机制的Tri-training算法,建立了半监督协同分类模型,利用人工扩展的问句集进行分类实验。实验结果表明,基于平时优秀投票机制的Tri-training算法和基于分类准确率投票机制的Tri-training算法,较原始Tri-training算法的分类精度,当r=80%时,分别提高了0.15%和0.13%;且基于平时优秀投票机制的Tri-training算法,相对于基于分类准确率投票机制的Tri-training算法的运行时间开销平均少了7 s。本文算法的分类实验主要是在哈尔滨工业大学的中文问句集基础上展开的,对于更大规模的中文问句集而言,算法是否有效,还有待验证。希望本文算法能够为其他分类领域研究提供参考。