多示例学习是机器学习中一个重要的研究方向[1-2], 其训练集的基本组成元素不是单个示例, 而是由若干示例组成的包, 且只有包的类别标记是给出的。若一个包中至少含有一个正示例, 则该包为正包, 反之则为负包。多示例学习被公认为是一种新的学习框架[3], 其显著特点是正包中可同时含有正、负两类示例, 而负包中只含有负示例。面向多示例学习问题, 国内外学者进行大量研究工作, 提出很多代表性算法并取得良好的试验结果, 例如:多样性密度算法[4]、期望最大-多样性密度算法[5]、引用-K近邻(citation-K nearest neighbors, citation-KNN)算法[6]、多示例支持向量机算法[7]、多示例核算法[8]、多示例图算法[9]、多示例去歧义算法[10]、多示例维数约减算法[11]、多示例最大间隔子空间算法[12]。
在上述算法中, Citation-KNN基于最小或最大Hausdorff距离来搜索近邻包, 是一种基于近邻准则的多示例学习算法, 在多个公用数据集上均取得不错的试验结果[6, 13-14]。但是, Citation-KNN没有分析最小和最大Hausdorff距离的各自特点, 也没指明在某些特定情形下采用哪个距离更加合理。本研究分别针对这两种Hausdorff距离的特点展开分析, 指出它们均有缺陷且缺陷具有互补性, 然后提出混合Hausdorff距离将它们加以融合, 以减弱任意单一Hausdorff距离给多示例学习带来的不利影响。权系数是混合Hausdorff距离中的未知参数, 不同的权系数对应着不同的混合Hausdorff距离, 需要基于某种模型来优化权系数找到在该模型意义下最优的混合Hausdorff距离。本研究采用能够表示概率意义上分类精度的近邻分量分析(neighborhood component analysis, NCA)模型[15]来优化权系数。
1 混合Hausdorff距离 1.1 最小和最大Hausdorff距离的各自缺陷令A和B表示任意两个包, nA和nB分别表示包A和B中的示例数目, ar∈RD(r∈{1, …, nA})和bs∈RD(s∈{1, …, nB})分别表示包A中第r个示例和包B中第s个示例, 其中每个示例均为一个D维向量。令‖‖2表示l2范数, 则包A和包B之间的最小、最大Hausdorff距离可分别表示为
| $ {d_{\min {\rm{H}}}}\left( {A,B} \right) - \min {{\kern 1pt} _r}\min {{\kern 1pt} _s}\sum\limits_{r = 1}^{{n_A}} {\sum\limits_{s = 1}^{{n_B}} {{{\left\| {{\mathit{\boldsymbol{a}}_r} - {\mathit{\boldsymbol{b}}_s}} \right\|}_2}} } , $ | (1) |
| $ {d_{\max {\rm{H}}}}(A,B) = \max \left\{ {d(A,B),{\rm{ }}d(B,A)} \right\}, $ | (2) |
其中: dminH和dmaxH分别表示最小和最大Hausdorff距离。式(2)中的d(A, B)和d(B, A)均为距离, 可分别表示为
| $ d(A,B) = \min {{\kern 1pt} _r}\min {{\kern 1pt} _s}\sum\limits_{r = 1}^{{n_A}} {\sum\limits_{s = 1}^{{n_B}} {{{\left\| {{\mathit{\boldsymbol{a}}_r} - {\mathit{\boldsymbol{b}}_s}} \right\|}_2}} } , $ | (3) |
| $ (B,A) = \min {{\kern 1pt} _s}\min {{\kern 1pt} _r}\sum\limits_{s = 1}^{{n_B}} {\sum\limits_{r = 1}^{{n_A}} {{{\left\| {{\mathit{\boldsymbol{b}}_s}\mathit{\boldsymbol{ - }}{\mathit{\boldsymbol{a}}_r}} \right\|}_2}} } 。 $ | (4) |
最大Hausdorff距离对异常示例非常敏感, 甚至仅一个异常样本就能明显影响最大Hausdorff距离的取值。下面通过一个例子对此加以说明。为简单起见, 首先假设每个示例均为标量, 即D=1。然后, 假设包A由{-1, -2, -3}这3个示例构成, 包B由{1, 2, 50}这3个示例构成, 其中包B中的50为异常示例。根据式(3)、(4)可知d(A, B)=max{2, 3, 4}=4, d(B, A)=max{2, 3, 51}=51, 然后根据式(2)可知dmaxH (A, B)=max{4, 51}=51。显而易见, 异常示例50会影响最大Hausdorff距离的取值。根据式(1)可知, 包A和B之间的最小Hausdorff距离为dminH (A, B)=2, 该距离没有受到异常示例50的影响, 可见最小Hausdorff距离对异常示例并不敏感。
给定一个正包A+, 两个负包B-和C-, 假设知道B-的类别标记为负, 此外还知道A+和C-的类别标记为一正一负, 但谁正谁负未知, 需要根据它们与负包B-的关系来判断。由于包A+可同时包含正、负两类示例, 包B-仅包含负示例, 根据式(1)可知dminH (A+, B-)既可能等于某个正示例和某个负示例之间的距离(情形1), 也可能等于某两个负示例之间的距离(情形2)。假设通常情况下同类示例之间的距离小于异类示例之间的距离, 那么情形2的出现概率更大, 即dminH (A+, B-)等于某两个负示例之间的距离。由于dminH (C-, B-)同样为某两个负示例之间的距离, 因此dminH (A+, B-)和dminH (C-, B-)的大小关系将具有随机性, 若出现dminH (A+, B-) < dminH (C-, B-), 则A+将被误判为负包, C-将被误判为正包。若采用的是最大Hausdorff距离, 出现误判的概率将大大降低。因为根据式(3)、(4)可知, 无论是d(A+, B-)还是d(B-, A+)均为max-min距离, 那么在上述假设下(同类示例之间的距离小于异类示例之间的距离), max-min距离中的max部分将使d(A+, B-)和d(B-, A+)均等于某个正示例和某个负示例之间的距离, 而根据式(2)可知dmaxH (A+, B-)也将等于某个正示例和某个负示例之间的距离。因此会有dmaxH (C-, B-) < dmaxH (A+, B-), 从而不会对A+和C-的类别标记作出误判。
1.2 混合Hausdorff距离及其权系数的优化通过上述分析, 可知最小、最大Hausdorff距离均存在各自缺陷, 且它们的缺陷具有一定的互补性。基于此, 提出混合Hausdorff距离将最小和最大Hausdorff距离融合在一起, 希望该混合距离能够减弱任意单一距离因其自身缺陷给识别带来的不利影响, 更加适用于多示例学习分类器的设计工作。包A和包B之间的混合Hausdorff (integrated Hausdorff, intH)距离可表示为
| $ {d_{{\rm{intH}}}}(A,B) = \alpha {d_{\min {\rm{H}}}}(A,B) + (1 - \alpha ){d_{\max {\rm{H}}}}(A,B), $ | (5) |
其中dintH表示混合Hausdorff距离。0≤α≤1和0≤1-α≤1分别表示最小和最大Hausdorff距离的权系数。
从式(5)可以看出, 不同的权系数α对应着不同的混合Hausdorff距离。需要选择某种意义下最优的混合Hausdorff距离:即通过将混合Hausdorff距离嵌入某种算法模型, 然后采用该模型针对α进行寻优,即可得到在该模型意义下最优的混合Hausdorff距离。NCA模型能够表示概率意义下基于留一法(leave-one-out)评估准则的分类精度[15], 计算较为简单且具有良好的泛化性能, 故采用该模型来优化α。假设共有l个包, Xi∈RD和yi∈{0, 1} (∀i∈{1, …, l})分别表示第i个包以及该包的类别标记, 其中0为负包标记, 1为正包标记。令pij表示Xi选择Xj作为它的近邻且继承Xj的类别标记的概率。根据NCA模型, pij可定义为Xi与Xj的相似程度相对于Xi与所有包的相似程度之和的比值。若采用混合Hausdorff距离的负指数形式来描述任意两个包之间的相似程度, 则pij可表述为
| $ {p_{ij}} = \left\{ \begin{array}{l} \frac{{\exp \left[ {\frac{{ - {d_{{\rm{intH}}}}({X_i},{X_j})}}{\sigma }} \right]}}{{\left\{ {\sum\limits_{k \ne i} {\exp \left[ {\frac{{ - {d_{{\rm{intH}}}}({X_i},{X_k})}}{\sigma }} \right]} } \right\}}}{\rm{,if }}i \ne j,\\ 0,{\rm{ if }}i = j, \end{array} \right. $ | (6) |
其中σ表示高斯核的带宽。
在定义pij的基础上, 能够被正确分类的包的数目的期望值可以表述为
| $ f(\alpha ) = \sum\limits_i {{p_i}} = \sum\limits_{{y_j} = {y_i}} {{p_{ij}}} , $ | (7) |
其中
通过最大化上述期望值来获取最优的α, 即可得到基于混合Hausdorff距离的NCA模型
| $ \mathop {\arg \max }\limits_\alpha f(\alpha )。 $ | (8) |
需要注意, 在上述NCA模型中引入一个新的未知参数σ。该参数与混合Hausdorff距离中的参数α不同:α为待优化变量, 希望通过NCA模型来找到最优的α (即最优的混合Hausdorff距离); 而σ为自由变量, 不同的σ对应着不同的NCA模型, 即一旦σ固定, NCA模型也就固定, 就可以找到与该NCA模型对应的最优α。在仿真试验中, 通过交叉验证技术来选择σ。
当将σ固定(即将NCA模型固定)来针对α进行寻优时, 由于α是一个标量, 可采用黄金分割搜索法(golden section search, GSS)[16]来优化α。GSS法是一种非常成熟且得到广泛应用的一维搜索技术, 其名字中含有“黄金分割”是因为它在优化过程中需要不停地记录3个点的函数值, 其中距离最远的两个点构成搜索区间, 中间点将该区间一分为二, 且分割后的2个子区间的长度的比值符合黄金分割比例。该方法可以逐步缩小搜索区间, 若搜索区间足够小(小于某个阈值), 该区间的中点即为待优化变量α的解。关于GSS法的具体实现细节, 可参见文献[16]的第10.2节。
2 试验通过多组公用数据集分别对基于最小、最大和混合Hausdorff距离的多示例学习近邻分类器进行性能评估。试验中采用的公用数据集共包括3类, 分别是关于药物活性预测问题的数据集Musk1和Musk2, 关于图像标注问题的数据集Elephant、Fox和Tiger, 以及关于Web目录页面推荐问题的数据集MILWEB。下面分别介绍这3类典型的多示例学习应用问题及相应数据集。
2.1 Musk1和Musk2数据集多示例学习技术可应用于药物活性预测[2]。大多数药物都是一些分子, 它们通过与较大的蛋白质分子例如酶等绑定来发挥作用, 药效则由绑定程度来决定。对适合制药的分子来说, 它的某个低能形状和期望的绑定区域将耦合得很紧密; 对不适合制药的分子来说, 则耦合得不够紧密。一个分子可能有上百种低能形状, 这么多形状中只要有一种是合适的(即该分子的某种低能形状和期望的绑定区域耦合得足够紧密), 这个分子就适于制药。因此, 若把每个分子看作一个包, 把该分子的每种低能形状看作包中的一个示例, 把和期望的绑定区域耦合得足够紧密的低能形状看作正示例, 耦合得不够紧密的低能形状看作负示例, 则药物活性预测将是一个典型的多示例学习问题。Musk1和Musk2是关于药物活性预测的2组数据集, 对它们的说明见表 1。
|
表 1 对Musk1等5组数据集的说明 Table 1 Introduction of Musk1 and other four datasets |
多示例学习技术可应用于图像标注[7]。在图像标注中, 每幅图像都被赋予一个标注来表示该图像的主题, 例如一幅关于“Elephant”的图像, “Elephant”就是对该图像主题的标注。每幅图像将被分割为若干片段, 其中每个片段对应着原来图像中的某个区域。若把每幅图像看作一个包, 把分割后的每个片段看作包中的一个示例, 把能够体现图像主题的片段看作正示例, 无法体现图像主题的片段看作负示例, 那么图像标注将是一个典型的多示例学习问题。Elephant、Fox和Tiger是关于图像标注的3组数据集, 对它们的说明见表 1。
2.3 MILWEB数据集多示例学习技术可应用于Web目录页面推荐[14]。用户在浏览Internet上的信息时经常会遇到目录页面, 这些页面仅提供标题或摘要, 而把具体的内容放在其链接到的下级页面中。例如各大门户网站都包含大量的目录页面。由于目录页面包含大量的链接, 很难要求用户花费大量的时间来指出其感兴趣的每个具体链接, 只能请用户反馈该目录页面中是否包含其感兴趣的链接内容。因此, 若将某目录页面及其全部链接内容组成的整体看作一个包, 将具体的链接内容看作包中的示例, 如果链接中有用户感兴趣的内容, 则该包为正包, 反之则为负包, 那么Web目录页面推荐将是一个典型的多示例学习问题。MILWEB是关于Web目录页面推荐的数据集, 由9组子数据集构成, 对它们的说明见表 2。由于每组子数据集均已被划分为训练集和测试集, 因此分别针对每组子数据集的训练集和测试集进行说明。
|
|
表 2 对9组MILWEB子数据集的说明 Table 2 Introduction of nine MILWEB sub-datasets |
试验中采用两种基于近邻准则的多示例学习分类器: Citation-KNN和K近邻(K Nearest Nei-ghbors, KNN)。Citation-KNN与KNN的不同之处在于前者利用citers和references两种信息来统计近邻样本的数目, 而后者仅利用references信息来统计近邻样本的数目, 因此KNN可看作是Citation-KNN的简化版。
令dminH、dmaxH、dintH分别表示最小、最大和混合Hausdorff距离。此外, 文献[17]提出一种平均Hausdorff (average Hausdorff)距离daveH, 文献[18]提出一种自适应Hausdorff (adapted Hausdorff)距离dadaH, 它们均能用来设计多示例学习分类器。将Citation-KNN、KNN这2种分类器分别与dminH、dmaxH、dintH、daveH和dadaH这5种Hausdorff距离相结合, 一共可以得到10种不同的多示例学习算法, 分别为Citation-KNN+dminH、Citation-KNN+dmaxH、Citation-KNN+dintH、Citation-KNN+daveH、Citation-KNN+dadaH、KNN+dminH、KNN+dmaxH、KNN+dintH、KNN+daveH、KNN+dadaH。试验部分将基于多组数据集(或子数据集)分别对这10种多示例学习算法的分类性能进行对比。需要指出的是, 为了公平地比较不同Hausdorff距离的多示例学习性能, 本研究没有采用文献[17-18]中的分类器, 而是通过Citation-KNN和KNN这2种简单分类器来分别测试不同Hausdorff距离的学习性能。由于采用NCA模型, Citation-KNN+dintH中含有2个自由变量:references (citers的设定方法则按照文献[6]中采取的策略, 即令citers=references+2)和σ; KNN+dintH中也含有2个自由变量:近邻样本数目和σ。对这两种算法, 均通过在训练集上进行5重交叉验证来选取最优的自由变量组合。Citation-KNN+dminH和Citation-KNN+dmaxH中仅含有references自由变量, 而KNN+dminH和KNN+dmaxH中仅含有近邻样本数目自由变量, 对这4种算法, 均通过在训练集上进行5重交叉验证来选取最优的单自由变量。由于Citation-KNN中references起的作用与KNN中近邻样本数目起的作用相同, 令references和近邻样本数目的候选集相同且均等于{1, 3, 5, 7}, 令σ的候选集等于{0.1, 0.2, 0.5, 1, 2, 5, 10, 20, 50, 100}。
对于Musk1、Musk2、Elephant、Fox和Tiger这5组数据集, 均采用10重交叉验证法来测试不同算法的分类性能。表 3给出了10种多示例学习算法在这5组数据集上的分类结果。由于MILWEB的9组子数据集均事先划分好了训练集和测试集, 因此可直接测试算法的分类性能(不需要采用10重交叉验证法), 表 4给出了上述10种多示例学习算法在这9组子数据集上的分类结果。在表 3和表 4中, 每组数据集(或子数据集)上能够获取的最优试验结果都用黑体表示。
|
|
表 3 对比算法在Musk1等5组数据集上的分类精度 Table 3 Classification accuracies of competing algorithms on Musk1 and other four datasets |
|
|
表 4 对比算法在9组MILWEB子数据集上的分类精度 Table 4 Classification accuracies of competing algorithms on nine MILWEB sub-datasets |
从表 3和表 4可以看出, 不管分类器采用的是Citation-KNN还是KNN, 在最小、最大、混合这3种Hausdorff距离中, 混合Hausdorff距离总能获得最高的分类精度。此外, 在Musk1、Musk2、Elephant、Fox和Tiger这5组数据集上, 无论采用Citation-KNN分类器还是KNN分类器, 混合Hausdorff距离的分类精度总是高于平均Hausdorff距离和自适应Hausdorff距离的分类精度。在9组MILWEB子数据集上, 就整体而言, 混合Hausdorff距离的分类性能略优于平均Hausdorff距离的分类性能(当采用Citation-KNN分类器时, 混合Hausdorff距离在4组子数据集上取得最优结果, 平均Hausdorff距离在3组子数据集上取得最优结果; 当采用KNN分类器时, 混合Hausdorff距离在4组子数据集上取得最优结果, 平均Hausdorff距离在2组子数据集上取得最优结果), 而自适应Hausdorff距离的分类性能则明显地不如混合Hausdorff距离和平均Hausdorff距离。
为分析自由变量对试验结果的影响, 图 1~2分别给出在Citation-KNN+dintH中不同references、不同σ所对应的分类精度(图中references用r表示), 图 3~4分别给出在KNN+dintH中不同近邻样本数目、不同σ所对应的分类精度。整体而言, references (近邻样本数目)和σ的变化对Citation-KNN+dintH和KNN+dintH的分类精度的影响, 在Musk1、Musk2、Elephant、Fox、Tiger这5组数据集上比在9组MILWEB子数据集上要小。造成这种差异的原因如下:在Musk1等5组数据集上, 给出的是采用10重交叉验证法进行测试得到的平均分类精度, 对10次分类精度进行平均将对最终的试验结果起到某种程度的平滑作用; 而对于9组MILWEB子数据集, 由于其训练集和测试集已经固定, 其分类精度仅仅是一次试验的结果, 因此自由变量的变化对试验结果的影响要大一些。
|
图 1 Citation-KNN+dintH中不同r所对应的分类精度 Figure 1 Classification accuracies of Citation-KNN+dintH for different r |
|
图 2 Citation-KNN+dintH中不同σ所对应的分类精度 Figure 2 Classification accuracies of Citation-KNN+dintH for different σ |
|
图 3 KNN+dintH中不同近邻样本数目所对应的分类精度 Figure 3 Classification accuracies of KNN+dintH for different numbers of neighbors |
|
图 4 KNN+dintH中不同σ所对应的分类精度 Figure 4 Classification accuracies of KNN+dintH for different σ |
本研究从多示例学习的角度出发, 在对最小、最大Hausdorff距离的各自缺陷进行分析的基础上, 提出混合Hausdorff距离来融合上述两种单一Hausdorff距离以弥补任意单一距离的缺陷, 并将其应用于多示例学习近邻分类器的设计工作。混合Hausdorff距离含有权系数α这一未知变量, 基于NCA模型、采用黄金分割搜索法可以快速方便地对α进行寻优。基于多个公用数据集的试验结果证明混合Hausdorff距离能够有效提高多示例学习算法的分类精度。
由于混合Hausdorff距离比最小、最大Hausdorff距离更加适用于多示例学习, 若采用它来设计相应的特征提取和特征选择算法, 则有望提取出(或选择出)能够有效区分正包和负包的判别分量(或特征子集), 从而进一步提高分类精度。如何基于混合Hausdorff距离来设计多示例学习特征提取和特征选择算法将是今后工作中的一个研究方向。
| [1] | 周志华.多示例学习[M].知识科学中的基本问题研究.北京:清华大学出版社, 2006:322-336. |
| [2] | DIETTERICH T G, LATHROP R H, LOZANO-PEREZ T. Solving the multiple-instance problem with axis-parallel rectangles[J]. Artificial Intelligence, 1997, 89 (1-2) : 31-71 DOI:10.1016/S0004-3702(96)00034-3 |
| [3] | MARON O. Learning from ambiguity[D]. Boston: Massachusetts Institute of Technology, 1998. |
| [4] | MARON O, LOZANO-PEREZ T. A framework for multiple-instance learning[C]//Advances in Neural Information Processing Systems 10. Denver, USA: MIT Press, 1998:570-576. |
| [5] | ZHANG Q, GOLDMAN S A. EM-DD: an improved multiple-instance learning technique[C]//Advances in Neural Information Processing Systems 14. Vancouver, Canada: MIT Press, 2002:1073-1080. |
| [6] | WANG J, ZUCKER J D. Solving the multiple-instance problem: a lazy learning approach[C]//Proceedings of the 17th International Conference on Machine Learning. Stanford, USA: Morgan Kaufmann Press, 2000:1119-1125. http://cogprints.org/2124 |
| [7] | ANDREWS S, TSOCHANTARIDIS I, HOFMANN T. Support vector machines for multiple-instance learning[C]//Advances in Neural Information Processing Systems. Vancouver, Canada: MIT Press, 2003:561-568. |
| [8] | GARTER T, FLACH P A, KOWALCZYK A, et al. Multi-instance kernels[C]//Proceedings of the 19th International Conference on Machine Learning. Sydney, Australia: Morgan Kaufmann Press, 2002:179-186. |
| [9] | ZHOU Zhihua, SUN Yuyin, LI Yufeng. Multi-instance learning by treating instances as non-I.I.D. samples[C]//Proceedings of the 26th International Conference on Machine Learning. Montreal, Canada: ACM Press, 2009:1249-1256. http://dl.acm.org/citation.cfm?id=1553534 |
| [10] | LI W J, YEUNG D T. MILD: multiple-instance learning via disambiguation[J]. IEEE Transactions on Knowledge and Data Engineering, 2010, 22 (1) : 76-89 DOI:10.1109/TKDE.2009.58 |
| [11] | SUN Y Y, NG M K, ZHOU Z H. Multi-instance dimensionality reduction[C]//Proceedings of the 24th AAAI Conference on Artificial Intelligence. Atlanta, USA: AAAI Press, 2010: 587-592. |
| [12] | PING Wei, XU Ye, REN Kexin, et al. Non-i.i.d. multi-instance dimensionality reduction by learning a maximum bag margin subspace[C]//Proceedings of the 24th AAAI Conference on Artificial Intelligence Atlanta. USA: AAAI Press, 2010: 551-556. |
| [13] | AMAR R A, DOOLY D R, GOLDMAN S A, et al. Multiple-instance learning of real-valued data[C]//Proceedings of the 18th International Conference on Machine Learning. Williamstown, USA: Morgan Kaufmann Press, 2001: 3-10. |
| [14] |
薛晓冰, 韩洁凌, 姜远, 等. 基于多示例学习技术的Web目录页面链接推荐[J].
计算机研究与发展, 2007, 44 (3) : 406-411 XUE Xiaobing, HAN Jieling, JIANG Yuan, et al. Link recommendation in web index page based on multi-instance learning techniques[J]. Journal of Computer Research and Development, 2007, 44 (3) : 406-411 DOI:10.1360/crad20070306 |
| [15] | ROWEIS S, HINTON G, SALAKHUTDINOV R. Neighbourhood component analysis[C]//Advances in Neural Information Processing Systems. Vancouver, Canada: MIT Press, 2005:513-520. |
| [16] | PRESS W H, TEUKOLSKY S A, VETTERLING W T, et al. Numerical recipes: the art of scientific computing[M]. New York: Cambridge University Press, 2007 . |
| [17] | ZHANG Minling, ZHOU Zhihua. Multi-instance clustering with applications to multi-instance prediction[J]. Applied Intelligence, 2009, 31 (1) : 47-68 DOI:10.1007/s10489-007-0111-x |
| [18] | ZAFRA A, PECHENIZKIY M, VENTURA S. ReliefF-MI: an extension of ReliefF to multiple instance learning[J]. Neurocomputing, 2012, 75 (1) : 210-218 DOI:10.1016/j.neucom.2011.03.052 |