引入

  论文地址：https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8242668&tag=1
  已有工作：

1. 非包映射： 使用一个实例或者所有实例的统计信息表示包，这将丢失大量信息。
2. 传统包映射： 基于实例选取进行映射，但是不能使得包在新的映射空间有效区分。
     论文作者提出判别包映射：选取更具代表性的实例，以此构建判别实例池，使得包可以在映射空间得以有效区分。
   
     说明：所有图片源自原论文，无意侵权。

1 判别包映射

1.1 总体框架

  本文符号表如下：

符号	含义
$\mathcal{B}$B	训练集
$n$n	包数量
$B_i$Bi​	包
$y_i \in \mathcal{Y} = \{ -1, +1 \}$yi​∈Y={−1,+1}	包标签
$\mathcal{X}$X	实例空间
$p$p	实例空间大小
$x_{i, j}$xi,j​	包中实例
$\mathcal{P} \subseteq \mathcal{X}$P⊆X	判别实例池 (Discriminative Instance Pool, DIP)
$m$m	$\mathcal{P}$P大小
$B_i^{\phi} = [ s(B_i, x_1^{\phi}), \cdots, s(B_i, x_m^{\phi})], {\rm where} x_k^{\phi} \in \mathcal{P}$Biϕ​=[s(Bi​,x1ϕ​),⋯,s(Bi​,xmϕ​)],wherexkϕ​∈P	包映射
$s(B_i, x_k^{\phi})$s(Bi​,xkϕ​)	包与实例$x_k^{\phi}$xkϕ​的相似度

  算法大致步骤如下：

1. 基于传统有监督分类算法于训练集获取DIP；
2. 基于DIP将每一个包映射到新的特征空间并完成预测。

1.2 DIP优化

  给定大小为$n$n的数据集$\mathcal{B}$B，汇聚$\mathcal{B}$B中的所有实例构建大小为$p$p的实例空间$\mathcal{X}$X。优化目标为：使用对角矩阵$\mathcal{I}_{\mathcal{P}}$IP​找到$\mathcal{P} \subseteq \mathcal{X}$P⊆X，其中$diag (\mathcal{I}_{\mathcal{P}}) = \mathbf{d} (\mathcal{P})$diag(IP​)=d(P)，并且：
$\mathbf{d} (\mathcal{P})_i = \begin{cases} 1, \qquad x_i \in \mathcal{P},\\ 0, \qquad \mathrm{otherwise}. \end{cases} \tag{1*}$d(P)i​={1,xi​∈P,0,otherwise.​(1*)

  令$\mathcal{J} (\mathcal{P})$J(P)表示一个实例评价函数，则对$\mathcal{P}$P的评估如下：
$\mathcal{P}_* = \arg \max_{\mathcal{P} \subseteq \mathcal{X}} \mathcal{J} (\mathcal{P}) \qquad s.t. \mid \mathcal{P} \mid = m. \tag{1}$P∗​=argP⊆Xmax​J(P)s.t.∣P∣=m.(1)式1指出，所选择的时候应该在新的映射空间具有最大的判别力。

1.3 DIP评价函数

  为了使得DIP具有最大的判别力，首先提出DIP优化的两大准则：

1. bag mapping must-link：标签相同的包在映射空间应该更相近。
2. bag mapping cannot-link：标签不同的包在映射空间能够体现出差异。

  因此，DIP评价函数如下：
$\mathcal{J}(\mathcal{P})=\frac{1}{2} \sum_{i, j} K_{\mathcal{P}}\left(B_{i}, B_{j}\right) Q_{i, j}, \tag{2}$J(P)=21​i,j∑​KP​(Bi​,Bj​)Qi,j​,(2)其中
$K_{\mathcal{P}}\left(B_{i}, B_{j}\right)=\left\|\mathcal{I}_{\mathcal{P}} B_{i}^{\phi_{x}}-\mathcal{I}_{\mathcal{P}} B_{j}^{\phi_{x}}\right\|^{2}, \tag{3}$KP​(Bi​,Bj​)=∥∥∥​IP​Biϕx​​−IP​Bjϕx​​∥∥∥​2,(3)其中$B_{i}^{\phi_{x}}$Biϕx​​与$B_{i}^{\phi}$Biϕ​类似，不同在于使用所有实例作为DIP；$Q$Q矩阵的元素定义如下：

$Q_{i, j} = \begin{cases} -1 / \mid A \mid, y_i y_j = 1;\\ 1 / \mid B \mid, y_i y_j = -1, \end{cases} \tag{4}$Qi,j​={−1/∣A∣,yi​yj​=1;1/∣B∣,yi​yj​=−1,​(4)其中$A = \{ (i, j) \mid y_i y_j = 1 \}$A={(i,j)∣yi​yj​=1}表示满足第一准则的成对约束集；$B = \{ (i, j) \mid y_i y_j = -1 \}$B={(i,j)∣yi​yj​=−1}与此类似。根据式3、4，将式2重写为 (具体推导看原文)：
$\mathcal{J} (\mathcal{P}) = \sum_{x_k^{\phi} \in \mathcal{P}} \phi_k^{\rm T} L \phi_k, \tag{5}$J(P)=xkϕ​∈P∑​ϕkT​Lϕk​,(5)其中$\phi_k = B_k^{\phi_x}$ϕk​=Bkϕx​​；$L$L是一个源自$Q$Q的拉普拉斯矩阵，满足$L = [L_{i, j}]^{n \times n} = D - Q$L=[Li,j​]n×n=D−Q；$D$D是一个对角矩阵，且$D_{i, i} = \sum_j Q_{i, j}$Di,i​=∑j​Qi,j​。
  令$f (x_k^{\phi}, L) = \phi_k^{\rm T} L \phi_k$f(xkϕ​,L)=ϕkT​Lϕk​，则式1可以转变为：
$\mathcal{P}_* = \max_{\mathcal{P} \subseteq \mathcal{X}} \sum_{x_k^{\phi} \in \mathcal{P}} f (x_k^{\phi}, L)\qquad s.t. \mid \mathcal{P} \mid = m. \tag{6}$P∗​=P⊆Xmax​xkϕ​∈P∑​f(xkϕ​,L)s.t.∣P∣=m.(6)为了找到最优的$\mathcal{P}_*$P∗​，可以计算所有的$f (x_k^{\phi}, L)$f(xkϕ​,L)，再取得前$m$m个作为DIP即可。

  具体的DIP优化过程如下：

  算法1: DIP优化算法
  输入:
    训练集$\mathcal{B}$B、实例空间$\mathcal{X}$X、DIP池大小$m$m；
  输出：
    $\mathcal{P} = \{ p_1, \cdots, p_m \}$P={p1​,⋯,pm​}；
   1：$\mathcal{P} = \emptyset, \tau = 0$P=∅,τ=0
   2：使用所有包标签、式4获取矩阵$Q$Q
   3：获取矩阵$L$L
   4：for $x_k \in \mathcal{X}$xk​∈X do
   5：  计算分数$f (x_k, L)$f(xk​,L)
   6：  if $\mid \mathcal{P} \leq m$∣P≤m or $f (x_k, L) > \tau$f(xk​,L)>τ, then
   7：    $\mathcal{P} \leftarrow \mathcal{P} \cup x_k$P←P∪xk​;
   8：  if $\mid \mathcal{P} > m$∣P>m, then
   9：    $\mathcal{P} \leftarrow \mathcal{P} / \arg \min_{x_k \in \mathcal{P}} f(x_k, L)$P←P/argminxk​∈P​f(xk​,L);
  10：  $\tau = \min_{x_k \in \mathcal{P}} f(x_k, L)$τ=minxk​∈P​f(xk​,L);
  11：end for
  12：return $\mathcal{P}$P;

  如上，DIP优化的关键步骤为计算矩阵$L$L以及每一个实例的得分$f (x_k, L)$f(xk​,L)，并找出得分最高的$m$m个实例。当然，计算得分需要知道$\phi_k = B_k^{\phi_x} = [ s(B_k, x_1^{\phi_x}), \cdots, s(B_k, x_m^{\phi_x})]$ϕk​=Bkϕx​​=[s(Bk​,x1ϕx​​),⋯,s(Bk​,xmϕx​​)]，具体的，需要知道如何计算$s(B_k, x_1^{\phi_x})$s(Bk​,x1ϕx​​)。

1.4 使用DIP映射包

  映射的关键在于计算$s(B_k, x_1^{\phi_x})$s(Bk​,x1ϕx​​)，文中的定义如下：

$s\left(B_{i}, x_{k}^{\phi}\right)=\max _{x_{i, j} \in B_{i}} \exp \left(-\left\|x_{i, j}-x_{k}^{\phi}\right\|^{2} / \sigma^{2}\right)$s(Bi​,xkϕ​)=xi,j​∈Bi​max​exp(−∥∥∥​xi,j​−xkϕ​∥∥∥​2/σ2)其中$x_{i, j}$xi,j​是包$B_i$Bi​中的第$j$j个实例，$\sigma$σ是一个预设参数。映射结束之后，可以使用任意的分类算法进行学习。以下描述了两种判别包映射方法。

1.4.1 全局判别包映射 (Global Discriminative Bag Mapping)

  所有的实例均计算分数，并选取$m$m个高分实例。

• aMILGDM：使用所有的训练实例。
• pMILGDM：仅使用训练集种的正包。

1.4.2 局部判别包映射 (Local Discriminative Bag Mapping)

  对每个包种的实例计算分数，并计算最高判别得分的一个实例加入DIP。

• aMILLDM：从每个包选取一个最高得分实例。
• pMILLDM：从每个正包选取一个最高得分实例。

2 实验

  实验数据集如下：