MIML多示例多标记学习

MIML：多示例多标记学习* 周 志 华 1 张 敏 灵 1,2 1南京大学计算机软件新技术国家重点实验室，南京 210093 2河海大学计算机及信息工程学院，南京 210098 1. 引言 在利用机器学习技术解决实际问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 时，常见的做法是先对真实对象进行特征提取，用一个特征 向量来描述这个对象，这样就得到了一个示例（instance），然后把示例与该对象所对应的类别标记 （label）关联起来，就得到了一个例子（example）。在拥有了一个较大的例子集合之后，就可以利 用某种学习算法来学得示例空间与标记空间之间的一个映射，该映射可以预测未见示例（unseen instance）的标记。假设每个对象只有一个类别标记，那么形式化地来说，令 为示例空间、 为标 记空间，则学习任务是从数据集 中学得 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 ，其中 为一个示例而 为示例 所属的类别标记。在待学习对象具有明确的、单一的语义时， 上面的学习 框架 财政支出绩效评价指标框架幼儿园园本课程框架学校德育工作框架世界古代史知识框架质量保证体系框架图 已经取得了巨大的成功。 然而，真实世界的对象往往并不只具有唯一的语义，而是可能具有多义性的。例如，图 1(a)中 的这幅图像，既可认为它属于“大象”这个类别，也可认为它属于“狮子”、“草地”甚至“热带”、 “非洲”；图 1(b)中的这个网页，既可认为它属于“体育”这个类别，也可因为贝克汉姆娱乐明星味 十足而认为它属于“娱乐”类，甚至可以因为皇家马德里足球队出访的旅游、赚钱性质远大于比赛 性质而认为它属于“旅游”类、“经济”类。由于这样的多义性对象不再只具有唯一的语义，这就使 得前述的只考虑明确的、单一的语义的学习框架难以取得好的效果。 值得注意的是，对多义性对象进行学习是一个非常重要的问题。目前实际应用中遇到的很多难 题都是由对象的多义性所造成的。例如在基于内容的图像检索中，众所周知的难题是“语义鸿沟”， 即从图像的低层特征到高层语义之间存在难以逾越的障碍。笔者认为，这一语义鸿沟存在的本质原 因之一，就是因为图像是一种多义性对象：同样的特征描述、不同的语义。试想，如果一幅图像只 具有唯一的语义，那么哪里还会有什么语义鸿沟呢？笔者认为，要解决多义性造成的问题，首先需 要从某个任务所涉及的众多“可能语义”中把某个具体的多义性对象所能具有的“合适语义”找出 来，然后再根据具体的上下文从这些“合适语义”中确定当前的“语境语义”。而其中第一步，实际 *本文得到国家自然科学基金（60635030）、江苏省自然科学基金（BK2008018）和江苏省 333高层次人才培养工程 基金的资助 1 (a) 一幅图像 (b) 一个网页 图 1 多义性对象的两个例子 上就是要为对象赋予合适的类别标记子集，而不再是唯一的类别标记。针对这个目的，笔者提出了 MIML—— 即“多示例多标记学习”（Multi-Instance Multi-Label learning）这一学习框架[1][2]。本章 将对这方面的研究进展做一个简介，主要内容及更详细的介绍可参见[2]。 2. MIML 框架 提出MIML的基本考虑，是多义性对象往往具有复杂的内涵，只用一个示例（即一个特征向量） 来进行表示是一种过度简化，在表示阶段就丢失了有用的信息，后续的学习阶段将面临极大的困难。 事实上，一个多义性对象往往可以用多个示例来描述。例如对图像来说，如果使用某种技术将图像 划分为若干个区域，那么每个区域都可以用一个示例来描述，这样，一幅图像就可表示成多个示例 组成的一个集合；对文档来说，如果使用某种技术将其划分为若干部分，例如不同的章节段落，那 么每个部分都可以用一个示例来描述，这样，一个文档就可表示成多个示例的集合。考虑到多义性 对象具有多个语义，我们所要学习的实际上就是从示例集合到类别标记集合上的一个映射。形式化 地来说，令 表示示例空间， 表示类别标记空间，则 多示例多标记学习：给定数据集 ， ，目标是学得 。 其中， 为一组示例 ，而 为 的一组 合适类别标记 。 为 中所含示例的个数， 为 中所 含标记的个数。 对多义性对象的学习，机器学习界在多标记学习（multi-label learning）[3] 这一框架（framework） 下已经有一些研究。在这一框架下，每个对象由一个示例描述，该示例具有多个类别标记，学习的 2 目的是将所有合适的类别标记赋予未见示例。形式化地来说， 多标记学习：给定数据集 ， ，目标是学得 。其中 为一个示例， 为 的一组合适类别标记 。 为 中所含类别标记的个数。 利用一个示例集合来描述一个对象，这一技术在多示例学习（multi-instance learning）[4] 框架下 已有很多研究。在多示例学习框架下，每个对象由一组示例（即一个“示例包”）描述，该示例具有 一个类别标记，学习的目的是预测未见示例包的类别标记。形式化地来说， 多示例学习：给定数据集 ， ，目标是学得 。其中， 为一组示例 ， 为与 的类别标记。 为 中所含示例的个数。 如果再考虑本章开头时所提到的传统监督学习（单示例、单标记）框架，那么我们就有了四种 学习框架。图 2给出了一个直观的对比。 object instance label object … … … … instance instance instance label (a) 传统监督学习（单示例、单标记） (b) 多示例学习（多示例、单标记） … … object label label instance … … label … … object … … … … label label instance instance instance … … label (c) 多标记学习（单示例、多标记） (d) 多示例多标记学习 图 2 四种机器学习框架 [1][2] 既然已经有了好几个学习框架，为什么我们还需要MIML呢？ 首先，从表示能力上来看，传统监督学习框架可视为多示例学习框架或者多标记学习框架的特 例，而传统监督学习框架、多示例学习框架以及多标记学习框架均可视为MIML的特例。换句话说， 3 其他三种框架下所覆盖的情形，MIML框架也覆盖了；而MIML所覆盖的一些情形，其他三种框架 未必能够覆盖。在对真实世界学习问题求解时，好的表示往往至关重要，在一定程度上甚至直接决 定了学习的成败。采用了合适的表示，有可能更好地捕获学习对象所含的信息，从而使得学习任务 变得容易完成；采用不合适的表示，有可能已经丢失了重要信息，从而使得学习任务变得极其困难。 使用MIML来对多义性对象进行表示，有助于明示示例与类别标记之间的联系，从而有助于学习任 务的解决。 实际上，多标记学习框架所面临的困难，很大程度上是因其用一个示例来描述多义性对象所造 成的。如前所述，在多标记学习框架下，学习目标是 ，从图 2(c)可以看出，这是一个一 对多映射（从一个示例到多个类别标记），而一对多映射并不是一个合式函数。与多标记学习框架相 比，MIML 框架更加合理一些，虽然多对多映射看起来比一对多映射复杂，但是多对多映射毕竟是 一个合式函数，具有很多一对多映射所不具备的数学性质，这就使得学习任务可能得以较好地完成。 值得一提的是，与简单地对合适标记进行预测相比，了解一个对象为什么具有某个类别标记可 能在某些场合具有更重要的意义，而 MIML为此提供了一种可能。如图 3所示，与图 3(a)中难以了 解类别标记的原因不同，在图 3(b)中，我们可能可以知道，对象具有 的原因是因为其含有 ，具有 的原因是因为其含有 ，而该对象同时包含 与 则使得 其具有 。 … … object label1 labell instance labelj … … … … object… … … … label1 labell instancei instancen labelj instance1 … … (a) 一个具有 l个类别标记的对象 (b) 示例与类别标记之间的关系 图 3 MIML为理解示例与标记之间的关系提供了可能[2] 除了多标记学习问题，MIML还有助于涉及复杂概念的单标记学习问题的解决。如图 4(a)所示， 对于“非洲”这个语义内涵丰富的概念，与之对应的图像在表现形式上具有很大的差异性。因此， 对于图 4(a)左上角所示的图片，将其正确地分类为“非洲”是一个困难的问题。然而如图 4(b)所示， 如果我们能够充分利用该图片包含的树木、狮子、大象、草地等“子概念”，由于这些子概念相对而 言更加明确且易于学习，因此我们先利用MIML学习出子概念，然后再利用这些子概念导出“非洲” 这一高层概念，这可能比直接对“非洲”进行学习要容易很多。 4 (a) “非洲”是一个复杂、难以学习的高层概念 b) 利用MIML学习“子概念”，再由“子概念”导出复杂高层概念 图 4 MIML有助于学习复杂高层概念[2] 为了发挥 MIML 框架的能力，就需要 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 出有效的算法。为此，我们基于退化策略提出了 MIMLBOOST算法和MIMLSVM算法[1][2]，基于正则化（regularization）机制提出了 D-MIMLSVM算法 [2]和M3MIML算法 [5]。本章第 3节将对这些工作进行简介。 如果能够直接接触原始数据对象，那么我们可以利用MIML进行建模而获取更多的有用信息， 但在不少应用中，尤其是数据挖掘应用中，我们往往只能得到第二手数据，这些数据已由他人进行 了特征提取并将一个对象表示为一个特征向量。在这种情况下，虽然不能利用MIML表示的效力， 但是MIML学习仍然能发挥重要的作用。我们提出了 INSDIF算法[2][6] ，将单示例多标记样本转化为 MIML样本进行学习以获得更好的性能。本章第 4节将对此进行简介。 5 如前所述，MIML 框架还有助于对复杂高层概念的学习，为此我们提出了 SUBCOD算法[2]，通 过发现目标概念的子概念来将单标记样本转化为多标记样本，从而利用MIML的帮助提高学习性能。 本章第 5节将对此进行简介。 3. MIML 学习算法 3.1 基于退化策略的 MIML 学习算法 如第 2 节所述，传统监督学习是多示例学习或者多标记学习的特例，而传统监督学习、多示例 学习以及多标记学习均是多示例多标记学习的特例。因此，一种简单的MIML求解策略是以多示例 学习或者多标记学习为桥梁，将MIML问题退化为传统监督学习问题进行求解。 z 策略 1 - 以多示例学习为桥梁：多示例多标记学习的目标是学得 ，该目标可以 简化为一个多示例学习问题，即学习相应的目标函数 。此时，对于 任意的 ， 当且仅当 否则 。基于此，给定新样本 ，与之对应的类别标记集合为 。该多示例学习问题还可 进一步转化为传统监督学习问题，其目标是学得 并指定如何由 的取值确定 的取值。此时，对于任意的 ， 当且仅当 否则 。特别地，我们采用文献[7]中的方 法将多示例学习问题转化为传统监督学习问题，即 。 值得注意的是，上述转化过程也可采用其他方法实现。 z 策略 2 - 以多标记学习为桥梁：多示例多标记学习的目标是学得 ，该目标可以 简化为一个多标记学习问题，即学习相应的目标函数 。此时，对于任意的 ， 当且仅当 。基于此，给定新样本 ，与之对应的类 别标记集合为 。该多标记学习问题还可进一步转化为传统监督学习问题， 其目标是学得 。此时，对于任意的 ， 当且仅 当 否则 。基于此， 。本文采用文献 [8]中的“构造性聚类(constructive clustering)”方法实现所需的映射函数 。值得注意的是，上述 转化过程也可采用其他方法实现。 基于策略 1，我们设计了多示例多标记学习算法MIMLBOOST [1][2]。该算法以多示例学习为桥梁， 将 MIML 问题退化为传统监督学习问题求解。首先，MIMLBOOST 算法将每个多示例多标记样本 转化为 个多示例单标记样本 。其中， 包含 个示例 ，每个示例由 所含示例与类别标记 拼接而来。此外， 当且 仅当 ，否则 。上述转化过程完成后，MIMLBOOST 算法利用文献 [7]中的 MIBOOSTING算法对转化得到的多示例学习问题进行求解。MIBOOSTING算法假设包中每个示例对包 的类别标记具有独立且同等的影响，将多示例学习问题进一步退化为传统监督学习问题求解。需要 6 说明的是，基于策略 1还可以设计出其它类型的MIML学习算法。 基于策略 2，我们设计了另一种多示例多标记学习算法MIMLSVM [1][2]。该算法以多标记学习为 桥梁，将多示例多标记学习问题退化为传统监督学习问题求解。首先，MIMLSVM算法将每个多示例 多标记样本 转化为一个单示例多标记样本 。其中，函数 基于构造性聚类[8]将每个 包 转化为一个示例 。该聚类过程将集合 中的每个包看作一个原子对象，基于 Hausdorff距离度量包之间的距离并利用 k-medoids算法将集合 划分为若干个聚类。此时， 的每一 维即为包 与各聚类中心之间的距离。上述转化过程完成后，MIMLSVM 算法利用文献[9]中的 MLSVM算法对转化得到的多标记学习问题进行求解。该算法针对每个可能的类别标记构造一个二类 学习问题，从而将多标记学习问题进一步退化为传统监督学习问题求解。需要说明的是，基于策略 2还可以设计出其它类型的MIML学习算法。 为了考察 MIMLBOOST 与 MIMLSVM 算法的性能，我们在场景分类以及文本分类问题上进行了 实验。结果表明[1][2]，在 MIML 框架下对这些学习问题进行建模和学习，可以取得比使用多标记学 习框架和多示例学习框架更好的结果。MIMLBOOST算法与MIMLSVM算法的具体细节请参见[1][2]。 3.2 基于正则化的 MIML 学习算法 基于正则化机制以及最大化间隔（margin）策略，我们提出了两种多示例多标记学习算法，即 D-MIMLSVM [2]以及M3MIML [5]。本小节将首先介绍 D-MIMLSVM算法，然后介绍M3MIML算法。 3.2.1 D-MIMLSVM 算法 假设类别标记集合 中共含有 个不同的类别标记，即 。此外，假设分类系统由 个函 数 构成。其中，每个函数是一个由示例集合到实值空间的映射，即 。此时，给定新样本 ，分类系统预测与之对应的类别标记集合为 ，其中 用于判断 中第 个类别标记是否属于 。值得注意的是， 如果我们将包 中的每个示例 看作一个仅含一个示例的包 ，那么我们就可以用 表示分 类系统在示例 上的输出(即 )。 给定多示例多标记训练集 ，我们首先从两个方面来考察分类系统 的 性质。一方面，我们要求 在每个包 上预测的类别标记集合与其真实类别标记集合 保持一致。 另一方面，我们还考察 在包 上的输出与 在 所含示例上的输出之间的关系。具体来说，我们按 如下方式定义分类系统在训练集上的损失函数 ： 7 (1) 由上可见，函数 包含两个由正则化参数 进行平衡的损失项。具体来说，第一个损失项基于 hinge loss 考察包 的真实标记集合(即 )与系统输出 之间的差异。其中， 当且仅当 否则 ，且函数 。 中第二个损失项用于度量 在包 上输出与其在 所含示例上的输出之间的差异。基于多示例学习中常见的假设，我们将 在 的各个示例上的最大 输出，即 ，看作 在 上的最终输出。此外，用于度量 与 之间 差异的函数 可以有多种实现方式，例如采用 损失函数： 。 设 为某种定义在包空间 (即 )上的核函数，如 set kernel [10]。假设 中的每个成员函数 都是 一个线性函数，即 。其中， 是由核函数 导出的属性映射，而 是由核函数 导 出的再生核希尔伯特空间(RKHS) 所具有的点积运算。进一步地，记 为各线性函 数对应的平均权值向量。为了考察每个包所含各个类别标记之间的关系，受文献[11]中工作的启发， 我们通过同时最小化 以及 的方式来实现该目标。然而，考虑到 ，同时最小化 以及 可以简化为 同时最小化 以及 。结合上述考虑以及式(1)，我们定义如下的MIML学习正则化框 架： (2) 其中，正则化参数 用于平衡系统的模型复杂性和经验误差，而正则化参数 用于平衡系统在各 个类别上输出的差别和共性。直观上看，参数 的取值越大，则系统更关注在各个类上输出的共性， 反之则更关注在各个类上输出的差异。 基于上述设置，我们可以证明下述的表示定理：对于式(2)中的优化问题而言，其最优解 必定 具有如下的表示形式： (3) 其中， 。 假设采用 损失函数度量 ，则式(2)中的优化问题可以重写为： (4) 8 其中， 是与每个训练包在各个概念类上的误差对应的松弛变量， 而 与 分别代表全零和全 1向量。 不失一般性，假设我们按照 的顺序将所有训 练包以及训练包中的示例进行排列。此时，每个对象(包或者示例)可以用如下的函数 进行索引： 利用上述排序，我们可以得到定义在所有对象 (所有训练包及其包中示例 )上的大小为 的核矩阵 。设 表示核矩阵 的第 列，基于式 (3)所示的表示定理可得 且 。其中， 是与每个概念类对应的偏置(bias)而 。 基于上述描述，优化问题式(4)可以重写为： (5) 其中， 且 。 由于优化问题式(5)中含有非凸约束条件，因此该优化问题并不是常见的凸优化问题。然而另一 方面，考虑到优化问题式(5)中的非凸约束条件是由两个凸函数的差所构成的，对于这种形式的优化 问题我们可以利用 CCCP (Constrained Concave-Convex Procedure) [12][13]这一成熟的迭代优化策略对其 求解。已有的研究结果表明，CCCP方法可以保证收敛到相应优化问题的局部最优解 [14]，有时甚至 可以收敛到全局最优解 [15]。 此外，考虑到对于每一个可能的概念类，属于该概念的样本数通常远少于不属于该概念的样本 9 数，我们还在 D-MIMLSVM 算法中引入了相应的机制来处理类别不平衡问题。另一方面，为了提高 基于 CCCP策略求解式(5)的优化问题时每一步迭代过程的效率，我们还使用割平面（cutting plane） 算法提高效率。具体细节请参见[2]。 3.2.2 M3MIML 算法 给定多示例多标记样本 ，我们用 表示相应的类别向量。其中，当 时，其第 维 取值为 否则取值为 。M3MIML 算法假设分类系统包含 个线性模型 ，每个线性 模型对应于一个可能的概念类。其中， 与 分别为与第 类对应的权值向量和偏置。 M3MIML 算法假设样本在第 类上的输出由其所含示例在对应模型 上的最大输出决定 [16][17]。因此，给定新样本 ，对应的类别标记集合为 。 基于样本在每一个类上的输出，M3MIML算法定义 在第 类上的间隔为： (6) 其中， 用于计算向量之间的点积。M3MIML 算法进一步假设模型在 上的间隔由各个类上 间隔的最小值确定，并且模型在整个训练集上的间隔(记为 )由所有样本间隔的最小值确定。在理想 情况下，假设模型可以对训练集中的所有样本正确分类。则 ，存在模型 使得下式成立： (7) 并且对于任意的 ，最少存在一个 使得式(7)取等号。由此， 即为： (8) 理想情况下，M3MIML算法求解的最大化间隔问题为： (9) s.t.: such that 10 其中， 表示 在 中的补集。式(7)所示的不等式按照 取值为 或 两种不同的情况在式 (9)中对应于不同的约束条件。而最大化式(8)所示的间隔 相当于最小化 ，对应于 式(9)中的优化目标。 式(9)在优化目标和约束条件中均涉及 函数，难以使用优化技术直接寻优。为此，我们利用 如下所示的不等式在一定程度上放宽优化目标和约束条件： (10) 与此同时，引入松弛变量以反映真实世界中训练集不可完全正确分类的情况，M3MIML 算法对应的 优化问题即转化为： (11) 其 中 是 具 有 标 记 的 样 本 对 应 的 索 引 集 合 。 相 应 地 ， 为不具有标记 的样本对应的索引集合。 为所有权 值向量构成的参数矩阵而 为所有偏置构成的参数向量。 和 为相应的松弛变量集合。此外，目标函数中的参数 用 于平衡系统在训练集上的经验误差和间隔。 优化问题式(11)是一个具有凸目标函数和线性约束条件的二次规划问题，但仅仅假设了线性模型 用于样本分类。为了使得系统具有非线性分类能力，我们将式(11)在其对偶形式下利用核技巧求解， 相应的优化问题变为： (12) 11 其中，集合 ， ， 以及 分别为与优化问题式(11)中约束 条件相对应的对偶变量。此外，优化问题(式 12)中的目标函数为： 式(12)的对偶优化问题仍是一个具有凸目标函数和线性约束条件的二次规划问题。值得注意的 是，该二次规划问题的约束条件仅含有区间形式的不等式约束以及线性的等式约束，由此我们可以 利用文献[18]中的方法对其进行快速优化。该方法的基本思想是将二次规划问题分解为一系列相对简 单的线性规划问题求解。在完成式(12)的优化过程后，我们可以利用 KKT 条件来获得模型参数 。这样，给定新样本 ，与之对应的类别标记集合可按如下方式确定： (13) M3MIML算法的具体细节请参见[5]。 4. 利用 MIML 学习单示例样本 如前所述，如果能够直接接触原始数据对象，那么我们可以利用MIML进行建模而获取更多的 有用信息，但在不少应用中，我们只能得到他人进行特征提取后的数据，一个对象由一个特征向量 表示。事实上，对于采用单示例表示的对象，此时该对象多个类别标记所蕴含的多样性信息仅仅内 嵌于单一的示例中。如果能将对象单一示例的表示形式合适地转化为包（一组示例）的表示形式， 使得包中的每个示例能从特定方面反映对象所包含的某种信息，那么将有助于学习问题的解决。 12 基于上述考虑，我们设计了 INSDIF (INStance DIFferentiation)方法[2][6]。该方法将单示例多标记 样本转化为多示例多标记样本，从而利用MIML框架获得更好的学习结果。总的来看，INSDIF采用 了基于“示例区分”策略的两阶段学习算法。在算法的第一阶段，INSDIF将每个样本转化为包的表 示形式从而在输入空间中显式地描述对象歧义性。在算法的第二阶段，INSDIF利用多示例多标记学 习器对转化后的数据集进行学习。 令 为训练集。其中， 为一个示例，而 为与 对应的 一组类别标记。此外，设每个示例都是一个 维的特征向量。在算法的第一阶段，INSDIF 为每个可 能的概念类 计算一个原型向量 ，该向量为具有类别 的所有训练样本对应的均值向量： (14) INSDIF基于上述原型向量将对象转化为包的表示形式。具体来说，在求得每一类的原型向量后， INSDIF将每个样本 转化为一组示例构成的包 ，包中的每个示例对应于样本 与某个原型向量之 间的差值： (15) 基于式(15)，每个样本由单一示例的表示形式 转化为包的表示形式 ，且包的大小等于所有 可能的概念类别数。特别地，包中的每个示例(即 )考察了给定样本与类别 之间的空间关系， 从而蕴含了该样本与此类别相关的某种信息。实际上，除了利用上述方式实现单示例表示向多示例 表示的转化，还可采用其它策略来实现该目标。 在 算 法 的 第 二 阶 段 ， INSDIF 采 用 MIML 学 习 算 法 对 转 化 后 的 数 据 集 进行学习。在提出该算法时[6]，我们使用了一种类似于 RBF 神经网 络的两层分类结构来实现该目标，但其他的MIML学习算法，例如本章第 3节中所述的算法都可用 于此处。 具体地说，该结构的输入为一个包含 个示例的包 ，包中的每个示例 为 一个 d 维的属性向量 。该结构的输出包含了 个实值 ，其中每个 实值输出 与标记 相对应。该结构的第一层由 个包 组成，其中每个包 对应于 簇 的 中 心 且 将 训 练 集 划 分 为 个 互 不 相 交 的 子 集 ， 即 且 。该结构的第二层对应于权值矩阵 ， 其中 为连接包 与输出 的权值。 我们将每个包看作一个原子对象，基于 Hausdorff距离度量包之间的距离并利用 k-medoids算法 13 将集合 划分为 个不相交的簇 。这样，每个子集 对应的中心 即为： (16) 其中， 用于计算包 与包 之间的 Hausdorff距离。 由于聚类过程有助于发现数据集的内在结构信息，因此基于上式求得的子集中心可能蕴含了不 同包的分布信息。由此，每个包 可以转化为一个 维的属性向量 ，其 中 。INSDIF算法所需的第二层权值矩阵 可通过最小化如下的误差 平方和函数得到： (17) 其中， 为分类结构相对于包 在第 类上的实际输出。此外， 为算法相对 于包 在第 类上的期望输出，当 时 取值为 否则取值为 。将上式相对于变量 求导并设 导数值为 ，则最小化上述误差平方和函数等价于求解如下的方程组： (18) 其中，矩阵 且含有元素 ，矩阵 且含有元素 。这里， 我们使用奇异值分解来对上式求解。 在 INSDIF 算法的两阶段训练过程完成后，给定新样本 ，与之对应的类别标记集合为 。其中， 为与 对应的包的表 示形式。 INSDIF算法的具体细节请参见[2][6]。 5. 利用 MIML 学习复杂高层概念 如前所述，MIML框架还有助于对复杂高层概念的学习，为此我们提出了 SUBCOD (sub-concept discovery) 算法[2]，通过发现目标概念的子概念来将单标记样本转化为多标记样本，从而利用MIML 的帮助提高学习性能。 SUBCOD 采用了基于“子概念发现”策略的两阶段学习算法。在算法的第一阶段，SUBCOD 基 于训练包中的所有示例进行聚类分析。由此，算法发现与高层概念对应的一组低层子概念，并将多 示例单标记样本转化为多示例多标记样本。在算法的第二阶段，SUBCOD 利用监督学习器获得低层 子概念与高层概念之间的映射关系。由此，基于MIML学习器对转化后的数据集进行学习，并利用 14 监督学习器所得的映射关系对新样本的类别标记进行预测。 令 为训练集。其中， 为一组示例构成的包，而 为与 对应的类别标记。在算法的第一阶段， SUBCOD 将所有训练包中的示例构成数据集 。为了方便起见，我们将 中所有示例重新索引并记为 。其中， 。 我们利用具有 个混合成分的混合高斯模型对数据集 进行建模，并将所得模型中的每个混合 成分作为相应的低层子概念。我们基于 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的 EM 算法对高斯混合模型中的参数进行学习。简要地 说，我们首先随机初始化各个高斯混合成分的均值向量 ，协方差矩阵 以及混合系数 。在 EM算法迭代的每一轮中，我们首先求得 中每个样本隶属于各混合成分 的概率： (19) 然后，基于所得数值对模型参数进行更新： (20) (21) (22) 在上述 EM 过程收敛或迭代达到指定轮数后，我们通过如下方式确定 中每个样本 对应的低 层子概念： (23) 基于上述结果，我们为每个训练包 赋予一个 维的二值类别向量 以表达其隶属的一组低层 子概念。其中， 代表 具有第 个高斯混合成分所代表的子概念，否则 。特别地， 基于式(23)， 当且仅当 ，否则 。值得注意的是，对于两个具有 相同高层概念的包而言，由于它们所含的示例不同，其对应的低层子概念有可能不同。 由于上述确定子概念的过程基于非监督聚类的方式实现，因此并未考虑每个包所含的高层概念。 为此，我们通过考察子概念与 的高层概念(即 )之间的关系对二值类别向量 做进一步的修正。具 体来说，我们采用最大化间隔策略来实现该目标。设 为用于子类别标记修正的 维实值向量，向 量的每一维 位于 区间之内。其中， 代表标记 的取值应保持 15 不 变 而 则 代 表 应 翻 转 标 记 的 取 值 。 此 外 ， 设 向 量 ， 其 中 。另设 中至少有 个标记不能被翻转。基于上述表示， SUBCOD算法将求解如下的优化问题： (24) 其中， 。 通过优化上述问题，我们可以得到最大化间隔意义下的修正值 。我们迭代地求解式(24)。在迭 代过程开始前，我们将 的每一个元素初始化为 1。在迭代优化的每一轮中，我们首先固定 的取值 来优化变量 与 (二次规划问题)；然后，我们固定变量 与 的取值来优化修正值 (线性规划问题)。 上述迭代过程不断重复直至收敛或达到指定迭代轮数。 此后，我们利用修正值 将每个训练包 对应的二值类别向量 修正为 。其中， 当且 仅当 ，否则 。上述修正过程完成后，初始的多示例单标记训练集 即 可 转 化 为 相 应 的 多 示 例 多 标 记 数 据 集 。基于转化后的数据集 ，我们可以学习得到一个 MIML 学习器 。 在算法的第二阶段，为了将测试样本在 上的多标记输出映射到所需的单标记，SUBCOD使用一 个监督学习算法从 中学习得到一个分类器 。在 SUBCOD算法的两 阶段训练过程完成后，给定新样本 ，与之对应的类别标记即为 。 SUBCOD算法的具体细节请参见[2]。 6. 结束语 MIML 是一个有潜力的面向多义性对象的学习框架，本章对这方面的一些初步工作[1][2][5][6]进行 了介绍。最近，在基于MIML的图像标注[19]、MIML的距离度量学习[20]以及生物信息学应用[21]方面 又有一些新进展。作为一个新框架，MIML 还有很多内容需要进一步探索。我们相信，在今后的几 年中，在MIML的学习理论、高效算法、新型应用等方面都会有新成果出现。 16 参 考 文 献 [1] Zhou Z-H, Zhang M-L. Multi-instance multi-label learning with application to scene classification. In: Schölkopf B, Platt J, Hofmann T, eds. Advances in Neural Information Processing Systems 19 (NIPS’06), Cambridge, MA: MIT Press, 2007, 1609-1616. [2] Zhou Z-H, Zhang M-L, Huang S-J, Li Y-F. MIML: A framework for learning with ambiguous objects. CORR abs/0808.3231, 2008. [3] Tsoumakas G, Katakis I. Multi-label classification: An overview. International Journal of Data Warehousing and Mining, 2007, 3(3):1-13. [4] 周志华. 多示例学习. 见: 刘大有 主编, 知识科学中的基本问题研究, 北京: 清华大学出版社, 2006, 322-336. [5] Zhang M-L, Zhou Z-H. M3MIML: A maximum margin method for multi-instance multi-label learning. In: Proceedings of the 8th IEEE International Conference on Data Mining (ICDM’08), Pisa, Italy, 2008, 688-697. [6] Zhang M-L, Zhou Z-H. Multi-label learning by instance differentiation. In: Proceedings of the 22nd Conference on Artificial Intelligence (AAAI’07), Vancouver, Canada, 2007, 669-674. [7] Xu X, Frank E. Logistic regression and boosting for labeled bags of instances. In: Proceedings of the 8th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD'04), Sydney, Australia, LNAI 3056, 2004, 272-281. [8] Zhou Z-H, Zhang M-L. Solving multi-instance problems with classifier ensemble based on constructive clustering. Knowledge and Information Systems, 2007, 11(2): 155-170. [9] Boutell M R, Luo J, Shen X, Brown C M. Learning multi-label scene classification. Pattern Recognition, 2004, 37(9): 1757-1771. [10] Gärtner T, Flach P A, Kowalczyk A, Smola A J. Multi-instance kernels. In: Proceedings of the 19th International Conference on Machine Learning (ICML’02), Sydney, Australia, 2002, 179-186. [11] Evgeniou T, Micchelli C A, Pontil M. Learning multiple tasks with kernel methods. Journal of Machine Learning Research, 2005, 6: 615-637. [12] Cheung P M, Kwok J T. A regularization framework for multiple-instance learning. In: Proceedings of the 23rd International Conference on Machine Learning (ICML’06), Pittsburgh, PE, 2006, 193-200. [13] Smola A J, Vishwanathan S V N, Hofmann T. Kernel methods for missing variables. In: Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics (AISTATS’05), Barbados, 2005, 325-332. [14] Yuille A L, Rangarajan A. The concave-convex procedure. Neural Computation, 2003, 15(4): 915-936. [15] Pham Dinh T, Le Thi H A. A D. C. optimization algorithm for solving the trust-region subproblem. SIAM Journal on Optimization, 1998, 8(2): 476-505. [16] Maron O, Lozano-Pérez T. A framework for multiple-instance learning. In: Jordan M I, Kearns M J, Solla S A, eds. Advances in Neural Information Processing Systems 10 (NIPS’07), Cambridge, MA: MIT Press, 1998, 570-576. [17] Ray S, Page D. Multiple instance regression. In: Proceedings of the 18th International Conference on Machine Learning (ICML’01), Williamstown, MA, 2001, 425-432. [18] Franke M, Wolfe P. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 1956, 3: 95-110. [19] Zha Z-J, Hua X-S, Mei T, Wang J, Qi G-J, Wang Z. Joint multi-label multi-instance learning for image classification. In: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’08), Anchorage, AK, 2008. 17 18 [20] Jin R, Wang S, Zhou Z-H. Learn a distance metric from multi-instance multi-label data. In: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'09), Miami, FL, 2009. [21] Li Y-X, Ji S, Ye J, Kumar S, Zhou Z-H. Drosophila gene expression pattern annotation through multi-instance multi-label learning. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI'09), Pasadena, CA, 2009.