搜索
书书书第３８卷 第８期２０１５年８月计 算 机 学 报ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＶｏｌ．３８Ｎｏ．８Ａｕｇ．２０１５ 收稿日期：２０１３０８１２；最终修改稿收到日期：２０１４０８２８．本课题得到国家“九七三”重点基础研究发展规划项目基金（２０１２ＣＢ７２０５００）、国家自然科学基金（２１００６１２７）、中国石油大学（北京）基础学科研究基金项目（ＪＣＸＫ２０１１０７）资助．刘建伟，男，１９６６年生，博士，副研究员，主要研究方向为智能信息处理、复杂非线性系统分析、预测与控制、算法分析与设计．Ｅｍａｉｌ：ｌｉｕｊｗ＠ｃｕｐ．ｅｄｕ．ｃｎ．刘 媛，女，１９８９年生，硕士研究生，主要研究方向为机器学习、数字图像处理．罗雄麟，男，１９６３年生，博士，教授，主要研究领域为智能控制、复杂非线性系统分析、预测与控制．半监督学习方法刘建伟 刘 媛 罗雄麟（中国石油大学（北京）自动化研究所 北京 １０２２４９）摘 要 半监督学习研究如何同时利用有类标签的样本和无类标签的样例改进学习性能，成为近年来机器学习领域的研究热点．鉴于半监督学习的理论意义和实际应用价值，系统综述了半监督学习方法．首先概述了半监督学习的相关概念，包括半监督学习的定义、半监督学习研究的发展历程、半监督学习方法依赖的假设以及半监督学习的分类，然后分别从分类、回归、聚类和降维这４个方面详述了半监督学习方法，接着从理论上对半监督学习进行了分析并给出半监督学习的误差界和样本复杂度，最后探讨了半监督学习领域未来的研究方向．关键词 半监督学习；有类标签的样本；无类标签的样例；类标签；成对约束中图法分类号ＴＰ１８１ 犇犗犐号１０．１１８９７／ＳＰ．Ｊ．１０１６．２０１５．０１５９２犛犲犿犻犛狌狆犲狉狏犻狊犲犱犔犲犪狉狀犻狀犵犕犲狋犺狅犱狊ＬＩＵＪｉａｎＷｅｉ ＬＩＵＹｕａｎ ＬＵＯＸｉｏｎｇＬｉｎ（犚犲狊犲犪狉犮犺犐狀狊狋犻狋狌狋犲狅犳犃狌狋狅犿犪狋犻狅狀，犆犺犻狀犪犝狀犻狏犲狉狊犻狋狔狅犳犘犲狋狉狅犾犲狌犿，犅犲犻犼犻狀犵 １０２２４９）犃犫狊狋狉犪犮狋 Ｓｅｍｉｓｕｐｅｒｖｉｓｅｄｌｅａｒｎｉｎｇｉｓｕｓｅｄｔｏｓｔｕｄｙｈｏｗｔｏｉｍｐｒｏｖｅｐｅｒｆｏｒｍａｎｃｅｉｎｔｈｅｐｒｅｓｅｎｃｅｏｆｂｏｔｈｅｘａｍｐｌｅｓａｎｄｉｎｓｔａｎｃｅｓ，ａｎｄｉｔｈａｓｂｅｃｏｍｅａｈｏｔａｒｅａｏｆｍａｃｈｉｎｅｌｅａｒｎｉｎｇｆｉｅｌｄ．Ｉｎｖｉｅｗｏｆｔｈｅｔｈｅｏｒｅｔｉｃａｌｓｉｇｎｉｆｉｃａｎｃｅａｎｄｐｒａｃｔｉｃａｌｖａｌｕｅｏｆｓｅｍｉｓｕｐｅｒｖｉｓｅｄｌｅａｒｎｉｎｇ，ｓｅｍｉｓｕｐｅｒｖｉｓｅｄｌｅａｒｎｉｎｇｍｅｔｈｏｄｓｗｅｒｅｒｅｖｉｅｗｅｄｉｎｔｈｉｓｐａｐｅｒｓｙｓｔｅｍａｔｉｃａｌｌｙ．Ｆｉｒｓｔｌｙ，ｓｏｍｅｃｏｎｃｅｐｔｓａｂｏｕｔｓｅｍｉｓｕｐｅｒｖｉｓｅｄｌｅａｒｎｉｎｇｗｅｒｅｓｕｍｍａｒｉｚｅｄ，ｉｎｃｌｕｄｉｎｇｄｅｆｉｎｉｔｉｏｎｏｆｓｅｍｉｓｕｐｅｒｖｉｓｅｄｌｅａｒｎｉｎｇ，ｄｅｖｅｌｏｐｍｅｎｔｏｆｒｅｓｅａｒｃｈ，ａｓｓｕｍｐｔｉｏｎｓｒｅｌｉｅｄｏｎｓｅｍｉｓｕｐｅｒｖｉｓｅｄｌｅａｒｎｉｎｇｍｅｔｈｏｄｓａｎｄｃｌａｓｓｉｆｉｃａｔｉｏｎｏｆｓｅｍｉｓｕｐｅｒｖｉｓｅｄｌｅａｒｎｉｎｇ．Ｓｅｃｏｎｄｌｙ，ｓｅｍｉｓｕｐｅｒｖｉｓｅｄｌｅａｒｎｉｎｇｍｅｔｈｏｄｓｗｅｒｅｄｅｔａｉｌｅｄｆｒｏｍｆｏｕｒａｓｐｅｃｔｓ，ｉｎｃｌｕｄｉｎｇｃｌａｓｓｉｆｉｃａｔｉｏｎ，ｒｅｇｒｅｓｓｉｏｎ，ｃｌｕｓｔｅｒｉｎｇ，ａｎｄｄｉｍｅｎｓｉｏｎｒｅｄｕｃｔｉｏｎ．Ｔｈｉｒｄｌｙ，ｔｈｅｏｒｅｔｉｃａｌａｎａｌｙｓｉｓｏｎｓｅｍｉｓｕｐｅｒｖｉｓｅｄｌｅａｒｎｉｎｇｗａｓｓｔｕｄｉｅｄ，ａｎｄｅｒｒｏｒｂｏｕｎｄｓａｎｄｓａｍｐｌｅｃｏｍｐｌｅｘｉｔｙｗｅｒｅｇｉｖｅｎ．Ｆｉｎａｌｌｙ，ｔｈｅｆｕｔｕｒｅｒｅｓｅａｒｃｈｏｎｓｅｍｉｓｕｐｅｒｖｉｓｅｄｌｅａｒｎｉｎｇｗａｓｄｉｓｃｕｓｓｅｄ．犓犲狔狑狅狉犱狊 ｓｅｍｉｓｕｐｅｒｖｉｓｅｄｌｅａｒｎｉｎｇ；ｌａｂｅｌｅｄｅｘａｍｐｌｅｓ；ｕｎｌａｂｅｌｅｄｉｎｓｔａｎｃｅｓ；ｌａｂｅｌ；ｐａｉｒｗｉｓｅｃｏｎｓｔｒａｉｎｔｓ１ 引 言半监督学习（ＳｅｍｉＳｕｐｅｒｖｉｓｅｄＬｅａｒｎｉｎｇ，ＳＳＬ）是机器学习（ＭａｃｈｉｎｅＬｅａｒｎｉｎｇ，ＭＬ）领域中的研究热点，已经被应用于解决实际问题，尤其是自然语言处理问题．ＳＳＬ被研究了几十年，国内外涌现出大量关于该领域的研究工作，研究人员在这个问题上已经取得了显著的进步，目前已经有多个文献对ＳＳＬ领域进行了综述，例如文献［１］综述了早期ＳＳＬ的一些进展，文献［２］对ＳＳＬ进行了比较全面的综述，文献［３］对基于不一致的ＳＳＬ方法进行了综述，文献［４］详细综述了协同训练风范．由于ＳＳＬ研究的发展非常迅速，因此需要有更新的综述来对近几年ＳＳＬ研究的相关情况进行总结．鉴于ＳＳＬ的理论意义和实际应用价值，本文系统综述ＳＳＬ方法的研究进展，为进一步深入研究ＳＳＬ理论和拓展其应用领域奠定一定的基础．本文第２节概述ＳＳＬ的基本概念、研究历程、依赖的假设及分类；第３节到第６节分别介绍用于分类、回归、聚类、降维问题的ＳＳＬ方法；第７节对ＳＳＬ进行理论分析，综述ＳＳＬ的抽样复杂性和误差界；第８节展望未来的研究方向；第９节对全文进行总结．２ 半监督学习概述ＭＬ有两种基本类型的学习任务：（１）监督学习（ＳｕｐｅｒｖｉｓｅｄＬｅａｒｎｉｎｇ，ＳＬ）根据输入输出样本对犔＝｛（狓１，狔１），…，（狓犾，狔犾）｝学习输入到输出的映射犳：犡→犢，来预测测试样例的输出值．ＳＬ包括分类（Ｃｌａｓｓｉｆｉｃａｔｉｏｎ）和回归（Ｒｅｇｒｅｓｓｉｏｎ）两类任务，分类中的样例狓犻∈犚犿，类标签狔犻∈｛犮１，犮２，…，犮犆｝，犮犼∈Ν；回归中的输入狓犻∈犚犿，输出狔犻∈犚．具有代表性的ＳＬ方法有线性判别分析（ＬｉｎｅａｒＤｉｓｃｒｉｍｉｎａｔｉｖｅＡｎａｌｙｓｉｓ，ＬＤＡ）、偏最小二乘（ＰａｒｔｉａｌＬｅａｓｔＳｑｕａｒｅ，ＰＬＳ）、支持向量机（ＳｕｐｐｏｒｔＶｅｃｔｏｒＭａｃｈｉｎｅ，ＳＶＭ）、犓近邻（犓ＮｅａｒｅｓｔＮｅｉｇｈｂｏｒ，犓ＮＮ）、朴素贝叶斯（ＮａｉｖｅＢａｙｅｓ）、逻辑斯蒂回归（ＬｏｇｉｓｔｉｃＲｅｇｒｅｓｓｉｏｎ）、决策树（ＤｅｃｉｓｉｏｎＴｒｅｅ）和神经网络等．（２）无监督学习（ＵｎｓｕｐｅｒｖｉｓｅｄＬｅａｒｎｉｎｇ，ＵＬ）利用无类标签的样例犝＝｛狓１，…，狓狀｝所包含的信息学习其对应的类标签犢＾狌＝［狔＾１…狔＾狀］Ｔ，由学习到的类标签信息把样例划分到不同的簇（Ｃｌｕｓｔｅｒ）或找到高维输入数据的低维结构．ＵＬ包括聚类（Ｃｌｕｓｔｅｒｉｎｇ）和降维（ＤｉｍｅｎｓｉｏｎａｌｉｔｙＲｅｄｕｃｔｉｏｎ）两类任务．具有代表性的ＵＬ方法有犓均值（犓Ｍｅａｎｓ）、层次聚类（ＨｉｅｒａｒｃｈｉｃａｌＣｌｕｓｔｅｒｉｎｇ）、主成分分析（ＰｒｉｎｃｉｐａｌＣｏｍｐｏｎｅｎｔＡｎａｌｙｓｉｓ，ＰＣＡ）、典型相关分析法（ＣａｎｏｎｉｃａｌＣｏｒｒｅｌａｔｉｏｎＡｎａｌｙｓｉｓ，ＣＣＡ）、等距特征映射（ＩｓｏｍｅｔｒｉｃＦｅａｔｕｒｅＭａｐｐｉｎｇ，ＩＳＯＭＡＰ）、局部线性嵌入（ＬｏｃａｌｌｙＬｉｎｅａｒＥｍｂｅｄｄｉｎｇ，ＬＬＥ）和局部保持投影（ＬｏｃａｌｉｔｙＰｒｅｓｅｒｖｉｎｇＰｒｏｊｅｃｔｉｏｎｓ，ＬＰＰ）等．在许多ＭＬ的实际应用中，如网页分类、文本分类、基因序列比对、蛋白质功能预测、语音识别、自然语言处理、计算机视觉和基因生物学，很容易找到海量的无类标签的样例，但需要使用特殊设备或经过昂贵且用时非常长的实验过程进行人工标记才能得到有类标签的样本，由此产生了极少量的有类标签的样本和过剩的无类标签的样例［５］．因此，人们尝试将大量的无类标签的样例加入到有限的有类标签的样本中一起训练来进行学习，期望能对学习性能起到改进的作用，由此产生了ＳＳＬ［１２］，如图１所示．ＳＳＬ避免了数据和资源的浪费，同时解决了ＳＬ的模型泛化能力不强和ＵＬ的模型不精确等问题．图１ 半监督学习示意２１ 半监督学习研究的发展历程ＳＳＬ的研究历史可以追溯到２０世纪７０年代，这一时期，出现了自训练（ＳｅｌｆＴｒａｉｎｉｎｇ）、直推学习（ＴｒａｎｓｄｕｃｔｉｖｅＬｅａｒｎｉｎｇ）、生成式模型（ＧｅｎｅｒａｔｉｖｅＭｏｄｅｌ）等学习方法．Ｓｃｕｄｄｅｒ［６］、Ｆｒａｌｉｃｋ［７］和Ａｇｒａｗａｌａ［８］提出的自训练方法是最早将无类标签的样例用于ＳＬ的方法．该方法是打包算法，在每一轮的训练过程中反复运用ＳＬ方法，将上一轮标记结果最优的样例和它的类标签一起加入到当前训练样本集中，用自己产生的结果再次训练自己．这种方法的优点是简单，缺点是学习性能依赖于其内部使用的ＳＬ方法，可能会导致错误的累积．直推学习的概念最先由Ｖａｐｎｉｋ于１９７４年提出［１］．与归纳学习（ＩｎｄｕｃｔｉｖｅＬｅａｒｎｉｎｇ）不同，直推学习只预测当前训练数据和测试数据中无类标签的样例的类标签，而不推断整个样本空间的广义决策规则．Ｃｏｏｐｅｒ等人提出的生成式模型假设生成数据的概率密度函数为多项式分布模型，用有类标签的样本和无类标签的样例估计该模型中的参数［１］．后来，Ｓｈａｈｓｈａｈａｎｉ和Ｌａｎｄｇｒｅｂｅ将这种每类单组分的场景拓展到每类多组分，Ｍｉｌｌｅｒ和Ｕｙａｒ进一步将其推广［１］．这一时期，ＭｃＬａｃｈｌａｎ等人研究用无类标签的样例估计费希尔线性判别（ＦｉｓｈｅｒＬｉｎｅａｒＤｉｓｃｒｉｍｉｎａｔｉｖｅ，ＦＬＤ）规则的问题［１］．对ＳＳＬ的研究到了２０世纪９０年代变得更加狂热，新的理论的出现，以及自然语言处理、文本分类和计算机视觉中的新应用的发展，促进了ＳＳＬ的发展，出现了协同训练（ＣｏＴｒａｉｎｉｎｇ）和转导支持向量机（ＴｒａｎｓｄｕｃｔｉｖｅＳｕｐｐｏｒｔＶｅｃｔｏｒＭａｃｈｉｎｅ，ＴＳＶＭ）等３９５１８期刘建伟等：半监督学习方法新方法．Ｍｅｒｚ等人［９］在１９９２年提出了ＳＳＬ这个术语，并首次将ＳＳＬ用于分类问题．接着Ｓｈａｈｓｈａｈａｎｉ和Ｌａｎｄｇｒｅｂｅ［１０］展开了对ＳＳＬ的研究．协同训练方法由Ｂｌｕｍ和Ｍｉｔｃｈｅｌｌ［１１］提出，基于不同的视图训练出两个不同的学习机，提高了训练样本的置信度．Ｖａｐｎｉｋ和Ｓｔｅｒｉｎ［１２］提出了ＴＳＶＭ，用于估计类标签的线性预测函数．为了求解ＴＳＶＭ，Ｊｏａｃｈｉｍｓ［１３］提出了ＳＶＭｌｉｇｈｔ方法，ＤｅＢｉｅ和Ｃｒｉｓｔｉａｎｉｎｉ［１４］将ＴＳＶＭ放松为半定规划问题从而进行求解．许多研究学者研究将期望最大算法（ＥｘｐｅｃｔａｔｉｏｎＭａｘｉｍｕｍ，ＥＭ）与高斯混合模型（ＧａｕｓｓｉａｎＭｉｘｔｕｒｅＭｏｄｅｌ，ＧＭＭ）相结合的生成式ＳＳＬ方法［１５１６］．Ｂｌｕｍ等人［１７］提出了最小割法（Ｍｉｎｃｕｔ），首次将图论应用于解决ＳＳＬ问题．Ｚｈｕ等人［１８］提出的调和函数法（ＨａｒｍｏｎｉｃＦｕｎｃｔｉｏｎ）将预测函数从离散形式扩展到连续形式．由Ｂｅｌｋｉｎ等人［１９］提出的流形正则化法（ＭａｎｉｆｏｌｄＲｅｇｕｌａｒｉｚａｔｉｏｎ）将流形学习的思想用于ＳＳＬ场景．Ｋｌｅｉｎ等人［２０］提出首个用于聚类的半监督距离度量学习方法，学习一种距离度量．研究人员通过理论研究和实验对ＳＳＬ的学习性能进行了分析．Ｃａｓｔｅｌｌｉ和Ｃｏｖｅｒ［２１］在服从高斯混合分布的无类标签的样例集中引入了一个新的有类标签的样本，通过理论分析证明了在无类标签的样例数量无限的情况下，可识别的混合模型的分类误差率以指数形式快速收敛到贝叶斯风险．Ｓｉｎｈａ和Ｂｅｌｋｉｎ［２２］从理论上研究了当模型不完善时使用无类标签的样例对学习性能产生的影响．Ｂａｌｃａｎ和Ｂｌｕｍ［２３］以及Ｓｉｎｇｈ等人［２４］用概率近似正确（ＰｒｏｂａｂｌｙＡｐｐｒｏｘｉｍａｔｅｌｙＣｏｒｒｅｃｔ，ＰＡＣ）理论和大偏差界理论分析了基于判别方法的ＳＳＬ方法的