Multi-Instance Learning by Treating Instances As Non-I.I.D. Samples_jvdm

Multi-Instance Learning by Treating Instances As Non-I.I.D. Samples

miGraph(2009)

时间：2023/0709

0. Abstract

存在问题：以往的多实例学习研究通常将袋中的实例视为独立、同分布的。然而，在实际任务中，包中的实例很少是独立的。忽略了实例之间的关系传递重要的结构信息这一事实。

解决思路：利用实例之间关系，如果在Non-I.I.D.中处理实例，则可以期望获得更好的性能。

解决方法：

1. 第一种：我们显式地将每个袋映射到一个无向图上，并设计一个图核来区分正负袋。

2. 第二种：通过推导亲和矩阵来隐式构造图，并提出一个考虑团信息的高效图核。

1. Introduction

多实例学习的一个突出优点主要在于许多真实对象都有其固有的结构，通过采用多实例表示，我们能够比简单地使用扁平的单实例表示更自然地表示这些对象并捕获更多的信息。

如果划分是有意义的(例如，每个部分对应一个显著区域)，多实例表示捕获的附加信息可能有助于使学习任务更容易处理。

并非所有的时候都能使用多示例，因为如果单实例表示就足够了，那么使用多实例表示只是画蛇添足。即使在对象具有固有结构的任务中，我们也应该记住，多实例表示的力量存在于它捕获一些结构信息的能力中。

基本思想：将每个包视为一个实体，作为一个整体进行处理，并将实例视为实体的相互关联的组成部分。

2. The Proposed Methods

2.1. 问题分析：

如图所示，若用方块表示一个示例，相同颜色的表示同一类示例。若不考虑包中示例之间的关联，只考虑示例的数量，则三个包都是相似的。但显然不是这样。若我们考虑示例之间的联系，如图3，很明显，由于第一个包和第二个包的示例间结构相似，所以和第三个包相比，前两个包会更相似一点。

2.2. MIGraph

第一步是为每个包构造一个图。在这里作者采用$ϵ-graph$建立，因为受到文章A global geometric framework for nonlinear dimensionality reduction的启发，这种结构更能发现数据的底层流形结构。具体而言：

• 如果$x_{iu}$和$x_{iv}$之间的距离小于预先设定的阈值，则在这两个节点之间建立一条边，其中边的权重表示两个节点的亲和力(在实验中我们使用非零距离的归一化倒数作为亲和力值)。

• 可以使用许多距离度量来计算距离。根据流形的性质，即一个小的局部区域近似为欧几里得空间，我们用欧几里得距离建立$ϵ-graph$。

• 当涉及到分类属性categorical（离散属性/标称属性）时，我们使用VDM (Value Difference Metric)作为补充。例如对于实例的前j 个属性是categorical，余下的(d− j)个是归一化为 [0,1]的连续值：

$$(\sum _{h=1}^{j}VDM(x_{1,h},x_{2,h})+\sum _{h=j+1}^d|x_{1,h}-x_{2,h}{|}^2{)}^{\frac{1}{2}}$$

• 而VDM则定义为：

$$VDM(z_1,z_2)=\sum _{c=1}^C|\frac{N_{Z,z_1,c}}{N_{Z,z_1}}-\frac{N_{Z,z_2,c}}{N_{Z,z_2}}{|}^2$$

而$N_{Z,z}$表示在属性$Z$上取值为$z$的样本数量，$N_{Z,z,c}$表示在第c个类别中在属性$Z$上取值为$z$的样本数量，C表示类别数。

分类器的构建方法：

• 可以构建一个k近邻分类器，利用图编辑距离。
• 可以设计一个图核来捕捉图之间的相似性，然后通过核机(如SVM)来解决分类问题。

MIGraph方法采用第二种方法，图核的思想如图所示。使用节点核(即$K_{node}$)来合并节点传递的信息，使用边缘核(即$K_{edge}$)来合并边传递的信息，并将它们聚合得到最终的图核(即$K_G$)

对于图表示 G h = ( { x h u } u = 1 n h , { e h v } v = 1 m h ) G_h=(\{x_{hu}\}_{u=1}^{n_h},\{e_{hv}\}_{v=1}^{m_h}) Gh​=({xhu​}u=1nh​​,{ehv​}v=1mh​​)，图核$K_G$的定义如下：

$$K_G(B_i,B_j)=\sum _{a=1}^{n_i}\sum _{b=1}^{n_j}{K}_{node}(x_{ia},x_{ib})+\sum _{a=1}^{m_i}\sum _{b=1}^{m_j}{K}_{edge}(e_{ia},e_{ib})$$

其中，$K_{node}$和$K_{edge}$是半正定核。

为避免数值问题，对图核进行归一化处理：

$$K_G(B_i,B_j)=\frac{K_G(B_i,B_j)}{{\sqrt{K}}_G(B_i,B_i){\sqrt{K}}_G(B_j,B_j)}$$

对于半正定核的选取，有很多选择，这里文章中选择高斯核来作为结点核和边核：

$$K_{node}(x_{ia},x_{jb})=exp(-\gamma ||x_{ia}-x_{jb}|{|}^2)$$

边核同样如此。

现在的问题是如何定义边的描述向量？

在文章中，作者定义边的向量为$[d_u,p_u,d_v,p_v{]}^{{}^{\prime }}$其中$d_u,d_v$分别是结点$x_u$和结点$x_v$的度。而$p_u$则表示为$p_u=w_{uv}/\sum w_u$，传递了边$e_{uv}$对于结点$x_u$的重要性，$p_v$同理。

$K_G$显然是一个正定核，所以可以适用于任意类型的图，同时也满足图核定义应该考虑的所有四个主要属性。但不足之处在于时间复杂度为$O(n_i{n}_j+m_i{m}_j)$，和边的数量有关，当包中实例数过多时，时间开销可能很大。

2.2. miGraph

思路：对于一个包$B_i$，可以计算器实例距离以及结合阈值$\delta$推导一个亲和力矩阵（affinity matrix）$W^i$。例如，若$x_a$和$x_u$的距离小于阈值则对应亲和矩阵位置$W_{au}^i$设置为1，否则设置为0。

修改后的图核定义如下：

$$K_g(B_i,B_j)=\frac{{\sum }_{a=1}^{n_i}{\sum }_{b=1}^{n_j}{W}_{ia}{W}_{jb}k(x_{ia},x_{jb})}{{\sum }_{a=1}^{n_i}{W}_{ia}{\sum }_{b=1}^{n_j}{W}_{jb}}$$

其中$W_{ia}=1/{\sum }_{u=1}^{n_i}{w}_{au}^i$，$W_{jb}=1/{\sum }_{v=1}^{n_j}{w}_{bv}^j$，而依然采用高斯核计算实例的距离。

一个团中的实例可以被视为属于一个概念，这是有帮助的。对于大型图来说，寻找团通常是昂贵的，而$K_g$可以看作是基于团的图核的一个有效的软版本，它显然满足以下原则:

1. 当$W^i=I$时，即每两个实例不属于同一概念时，应平等对待一个包中的所有实例，即$W^i=$。

2. 当$W^i=E$时，即矩阵元素全为1的矩阵。所有实例属于同一概念时，每个bag可视为一个实例，且每个实例贡献相同，$W_{ia}=1/n_i$

3. 当$W^i$是分块矩阵时，即实例被聚为属于一个概念的团，$W_{i}a=1/n_{ia}$。此时$K_g$为一个基于团的图核。

4. 此外，当$W_{ab}^i$增加时，$W_{ia}和W_{ib}$应该减少，因为他们之间变得更加相似了。而其他项则不受影响。

则$K_g$的时间复杂度为$O(n_i{n}_j)$

3. Experiments

实验数据集：Benchmark（5）,1000-Image ,2000-Image ,text categorization(20),Multi-Instance Regression