半监督学习中的几种协同训练算法

半监督学习中的几种协同训练算法高原(南京大学计算机科学与技术系,南京210093)ASurveyofSemi-SupervisedAlgorithmswithCo-TrainingParadigmYuanGao*(DepartmentofComputerScienceandTechnology,NanjingUniversity,Nanjing210093,China)Abstract:OnecansplittheMachineLearningintothreeimportantresearchareas,theyareSupervised,UnsupervisedandSemi-SupervisedLearning.AsamixtureofSupervisedandUnsupervisedmethod,SSLcantrainwithafewoflabeledandamountofunlabeledinstances.Here,wefocusourdiscussiononSemi-Supervisedclassification.Sinceitisproposedin1998byBlum&Mitchell,Co-Traininghasgrownintooneofthemostimportanttrainstyles[1].Itbuildstwoormoreclassifierswhichworktogetherduringthewholeprocessoftraining.Thispaperdiscussesvariousimportantapproachestosemi-supervisedlearningwithCo-TrainingparadigmsuchasCo-Training,Tri-Training,CoForestandCoTrade.Keywords:Semi-Supervised;Co-Training;classifier;labeled;unlabeled;Algorithms摘要:我们可以把机器学习划分为三个重要的研究领域：监督，无监督和半监督学习。作为监督和无监督学习的混合体，半监督学习能够利用少量标记数据和大量未标记数据进行训练。这里我们主要讨论的是的半监督学习的分类问题。自1998年Blum和Mitchell提出协同训练算法以来，协同训练风范已经成长为半监督学习中最重要的风范之一[1]。在整个训练过程中它建立起两个或两个以上的分类器并让他们协同工作。本文主要讨论了一些在半监督学习中具有协同训练风范的算法：Co-Training，Tri-Training，CoForest和CoTrade。关键词:半监督;协同训练;分类;标记;未标记;算法中图法分类号:TP301文献标识码:A1引言分类问题的核心是如何训练出一个分类器，它的输入是一个待分类示例的特征向量，对应的输出是一个合理的类别标记。贝叶斯公式P(𝐶𝑖|𝑥)=∑𝑃(𝑥|𝐶𝑖)𝑃(𝐶𝑖)𝑃(𝑥)表明我们可以将先验概率P(𝐶𝑖)转换为后验概率P(𝐶𝑖|𝑥)。P(𝐶𝑖|𝑥)代表在输入示例的特征向量x的条件下该示例类别属于𝐶𝑖的概率。据此我们可以得到一个𝐶𝑖关于x的似然函数，在其他条件都相等的情况下，使P(𝐶𝑖|𝑥)取最大值的𝐶𝑖更有可能是真实的类别[2]。显然，可以从大量的标记数中统计出先验概率P(𝐶𝑖)以及𝑃(𝑥|𝐶𝑖)这就意味着能够通过学习大量标记数据训练出一个强分类器，这种机器学习方法称为监督学习。事实上，获得大量的标记数据是一件极其耗时且代价高昂的事情。相反，无标记数据的获得就显得容易的多了。我们能够从标记数据中计算出𝑃(𝑥|𝐶𝑖)和𝑃(𝐶𝑖)，大量的无标记数据则有作者简介:2助于得到更接近于真值的p(x)。由贝叶斯公式可以看出p(x)能够影响到P(𝐶𝑖|𝑥)的值[3]，也就是说大量的无标记数据是有助于分类器学习的。半监督学习研究的主要内容就是如何高效的利用少量标记数据和大量的未标记数据来训练分类器。相比监督学习半监督学习能够得到更高的性价比，因此半监督学习在理论和实际在运用中均受到了广泛关注。最早在训练中运用未标记数据的想法（Self-Training）是[4]：首先利用标记数据集训练出初始分类器，使用该分类器对一些未标记数据进行标记，将可信度最高的一些标记新示例放入到标记数据集中再在新标记数据集上进行下一次训练直到满足截止条件为止（e.g.,Scudder(1965);Fralick(1967);Agrawala(1970)）。在这里未标记数据被用来修正和提高分类器的准确率。由于初始分类器总是一个弱分类器，self-training不断地利用上次迭代过程中训练得到的分类器来对未标记数据进行分类并将分类结果加入下次迭代的训练过程中的做法，将会导致self-training算法不断累积自身的分类错误最终造成分类器分类效率不高。在Self-Training的基础上Blum&Mitchell（1998）提出了由两个分类器协同训练的算法Co-Training。它利用两个分类器协同训练由单个分类器产生的新标记数据将会加入到另一分类器的下次迭代训练过程中作为新加入的标记数据。在此之后，很多学者在Co-Training的基础上进行了一系列的改进并提出了相应的算法（如：Tri-Training，CoFroest，CoTrade）。本文将详细介绍半监督学习中一些具有协同训练风范的一些算法。本文结构安排如下：第二章详细介绍具有协同训练风范的各种算法，在第三章对各个算法的实验结果进行分析比对，最后在第四章总结。2协同训练算法2.1Co-Training在网页分类[5]的问题中，网页拥有两个独立（distinct）的视图（view）即链接和网页内容。换言之，无论是链接还是网页内容都能独立完备的唯一确定一个网页。除此之外还有很多其属性可自然划分为两类的例子，如人的身份证号和面部特征。在具有这种特征的数据集的任何一个视图上均可以利用一定的机器学习算法训练出一个强分类器。基于上述情况Blum&Mitchell提出了Co-Training算法，该算法假设数据属性拥有两个充分冗余（sufficientandredundant）的视图[1]，称之为view1和view2。算法基本流程是：首先在标记数据集L的view1和view2分别上训练出两个分类器C1和C2；然后从未标记数据集U上随机的选取u个示例放入集合U’中；分别用C1和C2对U’中的所有元素进行标记；接着从两个分类器标记结果中各取可信度最高的p个正标记和n个负标记放入L中；最后从U中选取2p+2n个数据补充到U’中；重复上述过程直到满足截止条件。值得注意的是这两个视图应该是相互独立的。考虑一个极端的情况如果view1和view2是全相关的，那么由view1的到分类器和由view2训练得到的分类器对相同待标记示例的标记是完全一样的，这样以来Co-Training算法就退化成了self-training算法。2.2Tri-Training通常情况下，数据集很难满足拥有两个充分冗余视图的要求。许多研究者对Co-Training算法的条件进行了放松，提出了不需要充分冗余视图的协同训练算法[5]（Zhouetal.2007）。对于一个缺少充分冗余视图的数据集来讲，如何保证各分类器之间的差异性便成了协同算法的重要设计考虑之一。Zhou在其算法中采用了在同一数据集上使用不同的分类算法训练出有差异的分类器的方法。Z.-H.Zhou&Li（2005）提出了Tri-Training[6]算法，它既不需要充分冗余视图也不需要使用不同的分类算法[6]。Tri-Training通过在原始数据集上抽取出的有差异的数据子集上进行训练来保证分类器之间的差异性。数据子集由可放回随机采样算法bootstrap获得。Tri-Training采用了三个分类器，这样以来可信标记数据就可以由简单投票法则确定。详细情况是：对于未标记数据x，如果Ci和Cj对于x的标记是相同的，那么就把x及其标记y加入到Ck(k≠i,j)的标记训练数据集中。这里采用朴素贝叶斯算法作为分类算法。鉴于简单投票会给第三个分类器带入噪音[1]，Zhouetal.在Tri-Training算法中加入了在噪声环境下确保3分类错误率收敛的控制条件。考虑一个关于训练数据集容量m，学习器预测错误率ϵ与数据噪声率η的关系式：𝓂=𝐶𝜖2(1−2𝜂2)（Angluin&Laird，其中c是一个常数）。要保证𝜖𝑡𝜖𝑡−1（这里t表示第t次迭代），在训练过程中就必须满足：|𝐿∪𝐿𝑡|(1−2𝜂𝐿|𝐿|+𝑒̌1𝑡|𝐿𝑡||𝐿∪𝐿𝑡|)2|𝐿∪𝐿𝑡−1|(1−2𝜂𝐿|𝐿|+𝑒̌1𝑡−1|𝐿𝑡−1||𝐿∪𝐿𝑡−1|)2𝐿𝑡表示第t次迭代过程中获得前两个分类器肯定加入第三个分类器的标记数据；𝑒̌1𝑡为𝐿𝑡的标记错误率；𝜂𝐿则是L上的噪声数据率。显然|𝐿𝑡||𝐿𝑡−1|，进一步精炼得到的约束条件为：𝑒̌1𝑡|𝐿𝑡|𝑒̌1𝑡−1|𝐿𝑡−1|(1)，更简单的：𝑒̌1𝑡𝑒̌1𝑡−1且|𝐿𝑡||𝐿𝑡−1|为了确保（1）式成立有时我们需要抽取𝐿𝑡的子集作为新加入的标记集合。2.3Co-ForestZ.-H.Zhou&Li对Tri-Training进行了进一步的改进，提出了采用n个分类器的CoForest算法[7]。对于单个分类器hi,Hi称为它的协同分类集合。Hi是一个包含了除hi之外的所有分类器的集合。由Hi投票决定要加入hi下次迭代训练过程中的新标记示例。不同于Tri-Training，CoForest算法采用随机森林（RandomForest）来保证各分类器之间的差异性。随机森林是一个若干分类决策树的组合。它采用Bagging方法产生各异的训练集同时使用分类回归树作为元分类器。随机森林中单颗子树的生长过程可以概括为：首先可放回的从原标记数据集合中随机选取n个示例（采用Bagging算法获得）作为此单颗树的训练集并生成一颗分类树，然后CART随机地选择一组特征对内部节点进行属性分裂[8]。RF算法具有很好的鲁棒性。在确定第t次迭代的噪声率时，Zhouetal.引入了样本权值Wi,t从而有𝜂𝑖,𝑡=𝜂0𝑊0+𝑒𝑖𝑡𝑊𝑖,𝑡𝑊0+𝑊𝑖,𝑡，𝜂0和𝑊0分别代表了初始噪声率和初始标记数据权重。其中𝑊𝑖,𝑡=∑𝑗=0𝑚𝑖,𝑡𝑤𝑖,𝑡,𝑗，𝑤𝑖,𝑡,𝑗表示了除了第i个分类器之外的n-1个分类器对xj的预测可信度，显然𝑊0=∑𝑗=0𝑚01。类似于Tri-Training，Co-Forest最终求得的收敛约束条件为：𝑒𝑖,𝑡𝑒𝑖,𝑡−1且𝑊𝑖,𝑡𝑊𝑖,𝑡−1同样为了确保𝑒𝑖,𝑡𝑊𝑖,𝑡𝑒𝑖,𝑡−1𝑊𝑖,𝑡−1也需要对新标记集合𝐿𝑖,𝑡′进行再采样使得𝑊𝑖,𝑡𝑒𝑖,𝑡−1𝑊𝑖,𝑡−1𝑒𝑖,𝑡⁄。较Tri-training，Co-Forest算法更好的发挥了集成学习的作用[1]。2.4Co-TradeCo-Trade[9]沿袭了传统协同训练算法使用两个学习器的设定。这种二元协同算法无法用简单投票来决定标记可信度。S.Goldman和Y.Zhou在其二元协同算法中采用多次交叉十倍验证来测试标记的准确性。具体做法是：将数据集分成十份，轮流将其中9份作为训练数据，1份作为测试数据，进行试验，最终采用10次结果的正确率的平均值作为对算法精度的估计。显然，这种估计精度的做法具有高时间复杂度。在Co-Trade中Zhou&Zhang使用了一种基于切割边缘权重统计（cutedgeweighstatistic）的数据编辑（dataediting）技术来确定标记