论文部分内容阅读
多示例学习是一种弱监督学习，有别于传统的有监督学习，多示例学习处理的是包（由示例组成的集合）的分类问题。在该学习问题中，并不是所有的示例标签是给出的。基于标准的多示例学习假设，一个包如果含有至少一个正示例，则该包则被看做正包;反之，则为负包。显然，在正包中每个示例对应的类别标签信息是未知的。近几年来，多示例学习领域得到了较为成熟的发展，产生了各种各样的多示例学习算法。同时，由于其能够处理示例标签的模糊性，多示例学习已经在模式识别和计算机视觉中得到了广泛的应用。 针对近年来的多示例学习研究领域中的两个关键问题——大规模多示例学习和多示例学习中的正示例识别，本文分别结合哈希学习技术和图挖掘技术对这两个问题进行研究，提出了针对两个问题的各自的新算法SALE和PIGMIL，并对这两个算法进行了详细全面的介绍与分析。进一步，我们在不同的数据集上把这两个算法分别和其它常见的、对应各自问题的多示例学习算法做了对比实验，而实验结果表明，两个算法分别在处理各自问题的时候，都具有优异的表现。另外，本文也对多示例学习进行了全面系统的总结，详细的介绍了多示例学习的各种基本假设、常见算法分析、重要算法拓展、主要应用、常见数据集和工具，为多示例学习研究领域的研究者提供了一份全面、细致、实用的中文参考资料。本文针对大规模多示例学习和多示例学习中的正示例识别这两个问题的研究与成果，具体描述如下所示。 (1)针对大规模多示例学习问题，我们提出了一个基于自适应局部敏感哈希(LSH)编码的多示例学习算法SALE。 SALE算法的核心思想是，基于LSH技术把包转化为新的特征表示，再基于这些新的特征表示训练分类器，同时实现高效的学习分类效果。具体而言，SALE算法首先利用LSH构造了原始的映射批次，用于把示例和包映射到新的空间。然后，这些原始映射批次基于自适应学习的过程被再次构造，从而提升映射的效能。接着，基于不完全编码方法，每个包能够被转化成一个随机超级直方图(RSH)。对于产生的RSH，我们用一个权重框架作用于RSH上，来强调突出关键示例。这样，每个包最终被转化成为了一个权重化的随机超级直方图(weighted RSH)。最后，我们根据这些weighted RSH进行学习训练得到一个分类模型。我们所提出的SALE算法主要的贡献可以总结如下: 1.基于LSH的特点，SALE算法具有高灵活性(high flexibility)和低复杂度(low computation cost)，可适用于规模较大的多示例学习问题; 2.SALE算法是第一个结合了哈希学习方法和适应性学习来处理多示例学习问题的方法，其算法模型涉及到的针对映射批次的自适应再造(self-adaptive reconstruction)使得映射更加的有效; 3.SALE算法利用了多示例学习问题中的一些关键信息来提高算法的表现性能，比如关键示例的信息、不同包的示例之间的一致信息。 (2)针对多示例学习中的正示例识别问题，我们提出了结合图更新的针对多示例学习的正示例识别算法PIGMIL。 PIGMIL算法的核心思想是，真正的正示例(TPI)之间具有全局相似度，以及具有针对于负示例的稳健区别度，而PIGMIL算法则从所有正包中寻找同时拥有很高全局相似度和稳健区别度的示例，如图4.2所示。具体而言，PIGMIL算法首先初始化工作集合(working sets(WSs))、工作包(working bags(WBs)）、正候选示例池(positive candidate pool，PCP)，从而降低计算成本和提高TPI识别的准确度。我们认为PCP中的示例是应该是最有可能为正的示例。然后，我们基于一个示例更新算法对PCP中的示例进行不断的更新。该示例更新算法的基本思想是，根据PCP中的示例建立连续相似度和区分度图，然后把一个随机游走的算法作用于该图上而实现计算其中每个顶点的排序值，紧接着，根据这些排序值以及各个顶点对应的工作包、工作集，确定被替换和用来替换的示例对应的顶点。当得到跟新后的PCP，我们就把更新后的PCP中的示例视为TPI。最后，包就会基于这些找到的TPI被转化新的特征表示，进而带入分类器中进行学习训练一个包水平的分类模型。PIGMIL算法的主要贡献可以总结如下: 1.正示例之间的全局相似度被挖掘。通过结合正示例之间的一般相似度similarity(S)和这些相似度对应的连续度consistency(C)，我们可以得到一个全局的相似度(global similarity)(S+C)，而且避免了由巧合模式带来的对于TPI识别的错误信息。 2.正负示例之间的稳健的区别度被挖掘。稳健的区别度discrimination(D)对于数据异常点具有稳健性，该性质的主要作用表现为当一个较远的负示例变得更远的时候，这个负示例所带来的的影响会被急剧减小，当一个较近的负示例变得更近的时候，我们放置更多的重要性在这个负示例上。 3.WS、WS和PCP被建立从而减小计算成本和提升算法搜索的精确度。PIGMIL算法进一步把识别TPI的目标转化为PCP的更新，然后通过迭代更新CSDG图来近似目标。