论文阅读 (十六)：Image Annotation By Multiple-Instance Learning With Discriminative Feature Mapping (MILFM)
文章目录
引入
题目：Image Annotation By Multiple-Instance Learning With Discriminative Feature Mapping and Selection
缩写：MILFM
年份：2014
目标：解决–>以往的特征映射方法将忽略辨别性
领域：图像标注、特征选择、多示例
地址：https://ieeexplore.ieee.org/document/6542696
1 MILFM
1.1 特征映射：动机及方法
1.1.1 MIL范式
首先简要回顾三种用于图像标注的MIL范式。
1.1.1.1 传统MIL
如果一个包至少包含一个属于概念
c
c
c的实例，则该包为正包
[
1
]
^{[1]}
[1]。具体的，给定来自概念空间的一个概念
c
c
c，传统MIL可以表示为如下函数
v
v
v：
v
(
B
i
,
c
)
=
1
⇔
Δ
(
B
i
,
c
)
≥
1
,
(1)
v (\boldsymbol{B}_i, c) = 1 \Leftrightarrow \Delta (\boldsymbol{B}_i, c) \geq 1, \tag{1}
v(Bi,c)=1⇔Δ(Bi,c)≥1,(1)其中
B
i
\boldsymbol{B}_i
Bi表示一个包；
Δ
\Delta
Δ表示一个计数函数，即一个包中属于给定概念
c
c
c的成员个数。
1.1.1.2 Weidmann’s presence-based MIL
给定来自概念空间的概念集合
C
\mathcal{C}
C，该范式可以表示为
[
2
]
^{[2]}
[2]：
v
P
B
(
B
i
,
C
)
=
1
⇔
∀
c
∈
C
:
Δ
(
B
i
,
c
)
≥
1.
(2)
v_{PB} (\boldsymbol{B}_i, \mathcal{C}) = 1 \Leftrightarrow \forall_c \in \mathcal{C}: \Delta (\boldsymbol{B_i}, c) \geq 1. \tag{2}
vPB(Bi,C)=1⇔∀c∈C:Δ(Bi,c)≥1.(2)
1.1.1.3 Concurrent MIL
并发概念可以增强一个包为正的可能性
[
3
]
^{[3]}
[3]，然而该方法只考虑了正概念的相关性，这对图像标注而言是不充分的。
对此，本文在式 (2)的基础上，且引入负概念的相关性：给定正概念集合
C
1
\mathcal{C}_1
C1和负相关概念结合
C
2
\mathcal{C_2}
C2，定义
v
E
B
v_{EB}
vEB：
v
E
B
(
B
i
,
C
1
,
C
2
)
=
1
⇔
∀
c
1
∈
C
1
,
∀
c
2
∈
C
2
:
Δ
(
B
i
,
c
1
)
≥
1
,
δ
(
B
i
,
c
2
)
=
0.
(3)
v_{EB} (\boldsymbol{B_i}, \mathcal{C}_1, \mathcal{C}_2) = 1 \Leftrightarrow \forall_{c_1} \in \mathcal{C}_1, \forall_{c_2} \in \mathcal{C}_2: \Delta (\boldsymbol{B}_i, c_1) \geq 1, \delta (\boldsymbol{B}_i, c_2) = 0. \tag{3}
vEB(Bi,C1,C2)=1⇔∀c1∈C1,∀c2∈C2:Δ(Bi,c1)≥1,δ(Bi,c2)=0.(3)
1.1.2 实例原型
本文将基于实例原型将包映射为特征向量，这里实例原型是指能够隐含指示正负概念相关性的实例。
基于范式
v
E
B
v_{EB}
vEB，这里有两种类型的实例原型：
1）正实例原型：代表正相关概念；
2）负实例原型：代表负相关概念。
显然，正实例原型应该全来自正包，负实例原型则应全来自负包。这里，我们使用所有正包中的实例作为正实例原型，定义为
p
t
(
t
=
1
,
2
,
⋯
,
m
)
p_t (t = 1, 2, \cdots, m)
pt(t=1,2,⋯,m)。
在图像标注中，训练集通常是类不平衡的，即负包可能远多于正包。因此，不能像选取实例原型那样选取负实例原型。
本文中，将使用所有负包中实例聚类后的中心作为负实例原型：
1）对于所有负包中的实例，重复
n
n
n次
k
k
kMeans算法 (聚类中心数设置为正包数量)；
2）获得总计
c
c
c个聚类中心，表示为
n
t
(
t
=
1
,
2
,
⋯
,
c
)
n_t (t = 1, 2, \cdots, c)
nt(t=1,2,⋯,c)。
1.1.3 距离函数
令
B
i
\boldsymbol{B}_i
Bi表示第
i
i
i个包，
B
i
j
\boldsymbol{B}_{ij}
Bij表示包中第
j
j
j个实例。定义
X
\mathcal{X}
X和
F
\mathcal{F}
F分别为实例级别的特征空间和包映射级别的特征空间。
定义包与实例原型的距离函数如下：
d
(
p
t
,
B
i
)
=
min
j
d
(
p
t
,
B
i
j
)
;
d
(
n
t
,
B
i
)
=
min
j
d
(
n
t
,
B
i
j
)
,
B
i
j
∈
B
i
.
(4)
\begin{aligned} & d (p_t, \boldsymbol{B}_i) = \min_j d (p_t, \boldsymbol{B}_{ij});\\ & d (n_t, \boldsymbol{B}_i) = \min_j d (n_t, \boldsymbol{B}_{ij}), \boldsymbol{B}_{ij} \in \boldsymbol{B}_i.\\ \end{aligned} \tag{4}
d(pt,Bi)=jmind(pt,Bij);d(nt,Bi)=jmind(nt,Bij),Bij∈Bi.(4) 实例之间的距离函数在本文中指定为如下：
d
(
p
t
,
B
i
j
)
=
exp
(
−
∥
p
t
−
B
i
j
∥
2
σ
2
)
;
d
(
n
t
,
B
i
j
)
=
exp
(
−
∥
n
t
−
B
i
j
∥
2
σ
2
)
.
(5)
\begin{aligned} & d (p_t, \boldsymbol{B}_{ij}) = \exp (- \frac{{\| p_t - \boldsymbol{B}_{ij} \|}^2}{\sigma^2});\\ & d (n_t, \boldsymbol{B}_{ij}) = \exp (- \frac{{\| n_t - \boldsymbol{B}_{ij} \|}^2}{\sigma^2}).\\ \end{aligned} \tag{5}
d(pt,Bij)=exp(−σ2∥pt−Bij∥2);d(nt,Bij)=exp(−σ2∥nt−Bij∥2).(5)
1.1.4 包映射
给定任意包
B
i
\boldsymbol{B}_i
Bi，都可以将其映射为
F
\mathcal{F}
F上的
m
+
c
m + c
m+c为特征向量，即：
B
i
⟶
Feature Mapping
[
d
(
p
1
,
B
i
)
,
…
,
d
(
p
m
,
B
i
)
,
d
(
n
1
,
B
i
)
,
…
,
d
(
n
c
,
B
i
)
]
.
(6)
\begin{array}{r} \boldsymbol{B}_{i} \stackrel{\text { Feature Mapping }} \longrightarrow {\left[d\left(p_{1}, \boldsymbol{B}_{i}\right), \ldots, d\left(p_{m}, \boldsymbol{B}_{i}\right),\right.} \\ \left.d\left(n_{1}, \boldsymbol{B}_{i}\right), \ldots, d\left(n_{c}, \boldsymbol{B}_{i}\right)\right] . \end{array} \tag{6}
Bi⟶ Feature Mapping [d(p1,Bi),…,d(pm,Bi),d(n1,Bi),…,d(nc,Bi)].(6)
一种直观理解特征映射过程的方式如下图 (图片源自原论文)：
1）如果一个实例原型
p
t
p_t
pt近似于
X
\mathcal{X}
X中的正概念，值
d
(
p
t
;
B
i
)
d (p_t; \boldsymbol{B}_i)
d(pt;Bi)就应该相对于
B
+
i
\boldsymbol{B}_{+i}
B+i小，相对于
B
−
i
\boldsymbol{B}_{-i}
B−i大，即有利于辨别正包和负包；
2）实例原型
n
t
n_t
nt与此类似。
然而，基于MIL设置，正包中仅仅只有一小部分实例是真正的正实例 (更接近于正相关概念)；同理，仅有一小部分负实例能够指示负相关概念。
因此，我们需要一个特征选择过程，即从
m
+
c
m + c
m+c的特征向量中选出有用的子集
[
4
]
^{[4]}
[4]。本文中，将使用基于线性弱分类的AdaBoost算法完成此工作。
1.2 AdaBoost特征选择及分类学习
映射结束后的特征向量带有大量噪声，本文使用AdaBoost算法来进行特征选择并构建最终的分类器。
1.2.1 AdaBoost弱分类器选择
弱分类器的选取有两点主要考量：
1）如果映射后特征向量的一个确定维度是相关的，则该维度能够更有效地辨别正包和负包；
2）弱分类应该尽量简单。
最终，弱分类器的学习过程如下：
算法1：弱分类器学习
输入：
( x 1 , y 1 ) , ⋯ , ( x m , y m ) (x_1, y_1), \cdots, (x_m, y_m) (x1,y1),⋯,(xm,ym)，其中 x i , i = 1 , 2 , ⋯ , m x_i, i = 1, 2, \cdots, m xi,i=1,2,⋯,m表示特征向量； y i = 0 y_i = 0 yi=0、 y i = 1 y_i = 1 yi=1分别表示负样本和正样本
训练样本权重 w ( x i ) w (x_i) w(xi)
算法 ：
1）划分特征为 n n n个子空间 X 1 , X 2 , ⋯ , X n X_1, X_2, \cdots, X_n X1,X2,⋯,Xn
2）给定训练样本权重 w ( x i ) w (x_i) w(xi)，计算 W l j W_l^j Wlj，其中 l = 0 , 1 l = 0, 1 l=0,1， j = 1 , 2 , ⋯ , n j = 1, 2, \cdots, n j=1,2,⋯,n：
W l j = P ( x i ∈ X j , y i = l ) = ∑ i : x i ∈ X j , y i = l w ( x i ) . W_l^j = P (x_i \in X_j, y_i = l) = \sum_{i: x_i \in X_j, y_i = l} w (x_i). Wlj=P(xi∈Xj,yi=l)=i:xi∈Xj,yi=l∑w(xi).
基于权重 w ( x i ) w (x_i) w(xi)的弱学习器的输入如下：
h ( x ) = 1 2 log ( W 1 j + ε W 0 j + ε ) , j = 1 , ⋯ , n , , ∀ x ∈ X j h (x) = \frac{1}{2} \log (\frac{W_1^j + \varepsilon}{W_0^j + \varepsilon}), \qquad j = 1, \cdots, n, \qquad, \forall x \in X_j h(x)=21log(W0j+εW1j+ε),j=1,⋯,n,,∀x∈Xj其中 ε \varepsilon ε是一个很小的正常量。
4）相应的训练误差如下：
e r r = ∑ h ( x i ) ≥ 0 , y i = 0 w ( x i ) + ∑ h ( x i ) < 0 , y i = 1 w ( x i ) . err = \sum_{h (x_i) \geq 0, y_i = 0} w (x_i) + \sum_{h (x_i) < 0, y_i = 1} w (x_i). err=h(xi)≥0,yi=0∑w(xi)+h(xi)<0,yi=1∑w(xi).
1.2.2 AdaBoost特征选择
具体过程如下：
算法2：AdaBoost特征选择和分类器建造
输入：
比算法1少了个权重
算法：
1）初始化权重为：
w ( x i ) = { 1 2 n , y i = 0 ; 1 2 p , y i = 1 , w (x_i) = \begin{cases} \frac{1}{2n}, \qquad y_i = 0;\\ \frac{1}{2p}, \qquad y_i = 1,\\ \end{cases} w(xi)={2n1,yi=0;2p1,yi=1, 其中 n n n、 p p p分别为正样本和负样本的个数。
2）For t = 1 , ⋯ , T t = 1, \cdots, T t=1,⋯,T
a）基于算法1为每一个特征 j j j训练一个弱分类器 h j ( x ) ∈ R h_j (x) \in R hj(x)∈R，并获取相应的 e r r j err_j errj
b）选取具有最低分类误差的弱分类器，并保存 h t ( x ) = h j ( x ) h_t (x) = h_j (x) ht(x)=hj(x)，且设置 e r r t = e r r j err_t = err_j errt=errj
c）权重更新：
w t + 1 ( x i ) = { w t ( x i ) Z t p × e − y i h t ( x ) , y i = 1 ; w t ( x i ) Z t n × e − y i h t ( x ) , y i = 0 , w_{t+1} (x_i) = \begin{cases} \frac{w_t (x_i)}{Z_{tp}} \times e^{-y_i h_t (x)}, \qquad y_i = 1;\\ \frac{w_t (x_i)}{Z_{tn}} \times e^{-y_i h_t (x)}, \qquad y_i = 0,\\ \end{cases} wt+1(xi)={Ztpwt(xi)×e−yiht(x),yi=1;Ztnwt(xi)×e−yiht(x),yi=0, 其中 Z t p Z_{tp} Ztp和 Z t n Z_{tn} Ztn是用以确保正负样本权重之和等于 1 / 2 1 / 2 1/2的归一化因子。
输出：
最终假设：
H ( x ) = s i g n ( ∑ t = 1 T w t ( x ) h t ( x ) ) . H (x) = \mathrm{sign} (\sum_{t = 1}^T w_t (x) h_t (x)). H(x)=sign(t=1∑Twt(x)ht(x)).
本文中，正负样本呆呆权重之和始终等于 1 / 2 1 / 2 1/2，这有助于处理类别不平衡问题； T T T设置为比训练集中正样本的个数稍大。
1.3 包级别特征空间中低级别的特征选择
[1] O. Maron and A. Ratan, “Multiple-instance learning for natural scene classification,” in Proc. 15th Int. Conf. Mach. Learn., Jul. 1998, pp. 341–349.
[2] N. Weidmann, E. Frank, and B. Pfahringer, “A two-level learning method for generalized multi-instance problem,” in Machine Learning, vol. 2837. Berlin, Germany: Springer, 2003, pp. 468–479.
[3] G.-J. Qi, X.-S. Hua, Y. Rui, T. Mei, J.-H. Tang, and H.-J. Zhang, “Concurrent multiple-instance learning for image categorization,” in Proc. IEEE Int. Conf. Comput. Vis. Pattern Recognit., Jun. 2007, pp. 1–8.
[4] X. Yuan, M. Wang, and Y. Song, “Concept-dependent image annotation via existence-based multiple-instance learning,” in Proc. IEEE Int. Conf. Syst., Man, Cybern., Oct. 2009, pp. 4112–4117.