基于特征选择的嵌入空间多示例学习算法研究

摘要

多示例学习与传统的监督学习类似，每个训练样本具有一个与之关联的类别标签，学习系统的任务是尽可能正确地预测未知样本的类别标签。但二者又存在较大区别，在监督学习中，每个样本仅包含一个示例，而在多示例学习中，样本被称之为包，每个包包含一个或多个示例，包具有类别标签，而其中示例不被赋予任何类别信息。标准多示例假设认为：如果一个包至少包含一个正示例，那么该包被标记为正；否则，该包被标记为反。
　　在标准多示例假设下，正包中至少存在一个正示例，然而，许多多示例问题并不满足这一假设。比如，在基于区域的图像分类问题中，仅当多个局部目标对象同时出现在一幅图片中时，该图片才被认定为属于某一类别。为解决类似图像分类等问题，研究者们提出了广义多示例假设并设计了若个嵌入空间多示例学习算法。这类算法的基本思想是：首先，将训练包映射到由训练集中所有示例形成的嵌入空间中，以构造其相应的包级特征；然后，利用新的包级特征向量训练一个标准的监督学习分类器（比如，支持向量机）。利用包级特征映射，嵌入空间算法已将多示例学习转化为传统的监督学习。
　　嵌入空间算法的典型做法是利用训练集中的所有示例来构造嵌入空间，而在一般的多示例问题中，大多数训练包均由多个示例所组成，这样，即使对于中等规模的数据集，嵌入空间的维度也会远高于训练包的数量，而二者间的不均衡很容易导致学习过程的过拟合，因此特征选择便成为嵌入空间算法的必然选择。由于每一维包级特征均由一个示例原型所定义，因而在嵌入空间算法中特征选择本质上也是示例选择。本文以特征选择为视角围绕嵌入空间算法所涉及的两个关键问题（特征映射和特征选择）对这类算法进行深入研究，具体内容如下：
　　（1）提出一种基于距离特征非线性支持向量机映射方式的MILES算法。如何选择包级特征与支持向量机组合方式是MILES等嵌入空间算法的一个基本问题。针对这一问题，深入剖析现有两种组合方式的本质目的，并在此基础上改进MILES算法。目前存在两种组合方式，即距离特征与非线性支持向量机组合和相似性特征与线性支持向量机组合，前者利用非线性支持向量机实现了对距离特征的非线性映射，而后者基于指数函数实现了相应映射。通过对比分析这两种映射方式的优劣，归纳出距离特征与非线性支持向量机组合更适合于嵌入空间算法，进而利用这一较优组合替换MILES算法的原始组合实现对其的改进。实验结果表明，改进算法不仅在分类性能与执行效率上优于原始算法，在算法健壮性上也强于它。
　　（2）给出一种嵌入空间算法的分类方案。针对目前缺乏对这类算法的分类研究，以特征选择为视角对现有算法进行分类，将它们划分为基于“过滤”型和“嵌入”型特征选择的算法。此外，由于以往算法基于整个数据集进行参数调节，相应实验结果不能体现算法的真实性能，因此还利用交叉验证实验方法重新测试这些算法，即保证参数调节仅发生于训练包上，绝不涉及任何测试包。进行这部分实验的另一好处是能够帮助分析不同类型特征选择方法对嵌入空间算法的影响。
　　（3）提出三种基于贪心获取特征子集的嵌入空间算法。如何获取最优特征子集是嵌入空间算法的又一基本问题，简单的统计策略忽视了多示例学习本身的特点，致使特征子集中仍存在大量冗余特征，最终导致算法的执行效率很低。为解决这一问题，结合多示例学习的特点，提出一种贪心的特征子集获取方法——按某一特征选择标准在包级特征中挑选与每个训练包中得分最高的示例所对应的的特征，以及三种基于贪心方法的嵌入空间算法。实验结果表明，基于贪心方法的算法能够在保持原始算法分类性能的前提下大幅度提高其执行效率，即能够在性能和效率间保持均衡。
　　（4）提出一种示例选择方法泛化能力增强的MILD算法。MILD将示例对训练包的分类能力作为其示例选择依据，然而该算法未考察一个候选示例原型对未知包的分类能力，即忽视了其示例选择方法的泛化能力，此外，该算法还未考虑选择来自于反训练包的反示例原型。为克服MILD的以上缺点，将经典的交叉验证技术应用于其示例选择过程，提出一种其示例选择方法的泛化能力得到增强的改进算法。改进算法与原始算法的最大区别是将候选示例原型对验证集的分类能力作为示例选择的依据并将反示例原型的选取纳入其中。实验结果表明，改进算法能够大大提高原始算法的分类准确率。
　　（5）提出一种基于包内成对示例相似性的嵌入空间算法。由于包内最相似的一对示例可能蕴含着存在于其内的目标概念，因此还考虑利用成对示例相似性概念进行示例选择。在多个分类任务中，所提算法均表现出了十分出色的分类能力和执行效率。另外，由于该算法就示例选择而言仅关心包的内部结构并不考虑其所属类别，它在噪声敏感性测试中表现出了很强的健壮性。

目录

封面

中文摘要

英文摘要

目录

第1章 绪论

1.1 课题研究的背景和意义

1.2 多示例学习的研究现状

1.3 课题拟解决的主要问题

1.4 论文的研究内容和组织结构

第2章 嵌入空间算法特征映射方式的对比研究及改进的MILES算法

2.1 引言

2.2 包级特征与支持向量机组合的本质目的

2.3 采用距离特征非线性支持向量机映射方式的MILES算法

2.4 实验数据和设置

2.5 实验结果及分析

2.6 本章小结

第3章 嵌入空间算法特征选择方法的对比研究

3.1 引言

3.2 嵌入空间算法的分类与对比分析

3.3 实验结果及分析

3.4 本章小结

第4章 基于贪心获取特征子集的嵌入空间算法

4.1 引言

4.2 贪心的特征子集获取方法

4.3 贪心获取特征子集的嵌入空间算法

4.4 实验结果及分析

4.5 本章小结

第5章 示例选择方法泛化能力增强的MILD算法

5.1 引言

5.2 原始算法

5.3 基于交叉验证示例选择的MILD算法

5.4 实验结果及分析

5.5 本章小结

第6章 基于包内成对示例相似性的嵌入空间算法

6.1 利用相似性进行选择示例的动机

6.2 基于成对相似性的嵌入空间算法

6.3 实验结果及分析

6.4 本章小结

结论

参考文献

攻读博士学位期间发表的论文及其他成果

声明

致谢

个人简历