【论文阅读】Multi-instance Learning with Discriminative Bag Mapping

本文主要是介绍【论文阅读】Multi-instance Learning with Discriminative Bag Mapping，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

基本信息

· 题目：Multi-instance Learning with Discriminative Bag Mapping

· 会议：IEEE

摘要

目前，通过选择一个实例将一个包转化为一个新空间中的单个实例，主要是基于原始空间。但是基于原始空间的映射有一些缺陷，如：难以保证所选实例的识别能力。因此，允许一组实例共享一个标签，是解决学习中标签歧义问题的有效工具。本文提出了一种用于多示例学习的判别映射方法，旨在识别最佳实例，从而直接区分新映射空间中的包。

介绍

在有监督学习中，每一个训练样本都是一个带有类标签的实例；与有监督学习相比，多示例学习中的每一个训练样本则是一个含有多个实例的包，每个包都带有类标签。标签是分配给包的而不是给实例的。
若一个包是负包，那么该负包中的所有实例都是负的；但对于正包来说，包中至少有一个实例时正的。
现有的MIL方案主要分为两类：①改进传统的学习算法来解决标签歧义问题；②开发专门用于多示例学习的学习范式。但以上两种方案无法在包中含有大量实例的情况下呈现出优越的性能。
因此，本文提出一种用于多示例学习的直接判别映射方法，旨在识别那些能够使包在新的映射空间中能够被明显区分的实例。
在这里插入图片描述

符合与算法框架

本文符号表如下：

符号	含义
$B$	训练集
$n$	包数量
$B_{i}$	第 $i$ 个包
$y_{i}∈Y=\left \{ -1,+1 \right \}$	标签
$X$	实例集
$x_{i,j}$	第 $i$ 个包中的第 $j$ 个实例
$p$	实例空间大小
$P\subseteq X$	判别实例池（Discriminative Instance Pool, DIP）
$m$	DIP大小
$B_{i}^{\phi}=[s(B_{i},x_{1}^{\phi})，···，s(B_{i},x_{m}^{\phi})]$	包映射
$s(B_{i},x_{k}^{\phi})$	包 $B_{i}$ 与映射后的实例 $x_{k}^{\phi}$ 的相似度

一个包 $B_{i}$ 包含许多实例，实例 $x_{i,j}$ 表示在第 $i$ 个包中的第 $j$ 个实例。用 $y_{i}=Y,Y=\left \{ -1,+1\right \}$ 来表示包 $B_{i}$ 的标签。
在训练的过程中，所有的包 $B_{i}$ 都通过discriminative instance pool（DIP）转换称为一个新的特征空间中的一个单实例 $B_{i}^{\phi }$ 。我们将DIP通过 $P$ 来表示。
在测试过程中，先通过DIP将每一个包映射为特征空间中新的实例，然后利用训练好的分类器来预测最终的类标签。该过程中最关键的一部分就是找到最优的用于包映射的DIP（discriminative instance pool）。

DIP(discriminative instance pool) Optimization

DIP优化目标为：使用一个实例选择矩阵 $I_{p}$ （一种对角矩阵， $diag(I_{p})=d(p)$ ）来找到一个子集 $P \in X$ 。而 $d (p)$ 是一个启示向量。若 $x_{i}∈P$ ，那么 $d(P)_{i}=1$ ，否则 $d(P)_{i}=0$ 。
我们定义 $J (P)$ 作为实例评估函数，用于评价子集 $P$ 的质量。表达式如下：
$P_{*}=\arg\max J(P)\ \ s.t.|P|=m\tag{1}$
其中， $\ ·\ |$ 表示实例集的基数，而 $m$ 为从实例集 $X$ 中选出的实例数量。

DIP评价标准

为了能够得到具有一定鉴别实例能力的DIP，引入以下两个规则：
①bag mapping must-link：由于每一个包 $B_{i}$ 都带有一个正或负类标签，因此DIP必须确保在另一个映射空间中的包 $B_{i}^{\phi }$ 标签与包 $B_{i}$ 标签一致；
②bag mapping cannot-link：在映射空间中带有不同类别标签的包应该代表它们之间的差异；
DIP评价标准可以表示为：
$J(P)=\frac{1}{2} {\textstyle \sum_{i,j}^{}}K_{P}(B_{i},B_{j})Q_{i,j}\tag{2}$
其中， $K_{P}(B_{i},B_{j})$ 表示通过DIP得到的新的映射空间中包 $B_{i}$ 与包 $B_{j}$ 之间的距离。 $J (P)$ 表示映射空间的区别程度。 $K_{P}(B_{i},B_{j})$ 能够表示为：
$K_{P}(B_{i},B_{j})=||I_{P}B_{i}^{\phi_{x}} -I_{P}B_{j}^{\phi_{x}} ||^{2}\tag{3}$
其中， $B_{i}^{\phi_{x}}$ 与 $B_{i}^{\phi}$ 一样都使用了所有实例作为映射实例池。将标签嵌入矩阵 $Q$ 定义为：
$Q_{i,j}= \begin{cases} -1/|A|,y_{i}y_{j}=1\\ 1/|B|, y_{i}y_{j}=-1 \end{cases} \tag{4}$
其中， $A=\left \{ (i,j)|y_{i}y_{j}=1 \right \}$ 表示bag mapping must-link的包集； $B=\left \{ (i,j)|y_{i}y_{j}=-1 \right \}$ 表示bag mapping cannot-link的包集。
$J (P)$ 的推导过程如下：
在这里插入图片描述

其中， $t r (\cdot)$ 表示矩阵迹算子， $\chi_{\phi }=[B_{1}^{\phi _{x}},···,B_{n}^{\phi _{x}}]=[\phi _{1},···,\phi _{p}]^{\tau }∈\left \{ ℝ \right \}^{p\times n}$ ， $n$ 代表包的大小。 $D$ 是对角矩阵，它由矩阵 $Q$ 产生。 $L$ 是拉普拉斯（Laplacian）矩阵，由矩阵 $Q$ 产生， $L$ 可以表示为 $L=[L_{i,j}]^{n×n}=D-Q$ 。通过函数 $f(x_{k}^{\phi},L)$ 来表示 $\phi_{k}^{\tau }L\phi_{k}$ 。
最开始的优化问题可以转化为求使函数 $f(x_{k}^{\phi},L)$ 得到最大和的实例映射集合 $P$ ：
$max_{P\subseteq\chi } {\textstyle \sum_{x_{k}^{\phi}\subseteq P}^{}} f(x_{k}^{\phi },L)\ \ \ \ s.t.|P|=m\tag{6}$
DIP算法流程如图所示：
在这里插入图片描述
算法以一个空实例集 $P = \emptyset$ 以及最小分数 $\tau=0$ 开展。首先计算标签嵌入矩阵 $Q$ 以及与之相关联的拉普拉斯矩阵 $L$ 。然后通过实例 $x_{k}$ 与拉普拉斯矩阵 $L$ 计算函数 $f(x_{k},L)$ 的值。若函数 $f(x_{k},L)$ 的值比最小识别分数值更大，那么实例 $x_{k}$ 则被选为实例集 $P$ 中的一员。否则，倘若实例集 $P$ 溢出，那么在实例集 $P$ 中识别分数值最小的那个实例会从 $P$ 中移出。循环持续推荐直到产生最终的最佳识别实例池 $P$ 。

通过DIP实现包映射

一旦使用选择好的实例构建DIP，每个包都需要映射到新空间中的单个实例。给定一个DIP判别实例池 $P$ ，该DIP中有 $m$ 个实例，包 $B_{i}$ 能够映射为一个实例 $B_{i}^{\phi}=[s(B_{i},x_{1}^{\phi})，···，s(B_{i},x_{m}^{\phi})]$ ，而 $s(B_{i},x_{k}^{\phi})$ 代表包 $B_{i}$ 与示例 $x_{k}^{\phi}$ 之间的相似度，表示为：
$s(B_{i},x_{k}^{\phi})=max_{x_{i,j}∈B_{i}}\ \exp (-||x_{i,j}-x_{k}^{\phi}||^{2}/\sigma ^{2})\tag{7}$
其中， $x_{i,j}$ 代表在第 $i$ 个包 $B_{i}$ 中的第 $j$ 个实例， $\sigma$ 为预设的比例因子。通过优化的DIP，每一个包 $B_{i}∈B$ 都映射为 $B_{i}^{\phi}$ 。
映射算法又分为两类：①Global DiscriminativeBag Mapping；②Local Discriminative Bag Mapping