Multi-Instance Multi-Label Learning with Application to Scene Classification – Zhi-Hua Zhou, Min-Ling Zhang, NIPS 2006#
- Multi-instance: 一个example包含多个instance, example只对应1个label; Multi-label: 一个example对应多个label.
- 以Multi-instance或Multi-label为桥梁, 将multi-instance multi-label learning ($f_{MIML}: 2^{\mathcal{X}}\rightarrow 2^{\mathcal{Y}}$) 转化为传统机器学习任务.
- 方法一 (通过Multi-instance): 先转化为$f_{MIL}:2^{\mathcal{X}}\times \mathcal{Y}\rightarrow {-1. +1}$, 再转化为$f_{SISL}: \mathcal{X}\times\mathcal{Y}\rightarrow{-1, +1}$, $f_{MIL}(X_i, y) = sign[\sum_{i=1}^{n_i}f_{SISL}(x_{j}^{(i)}, y)]$
- 方法二 (通过Multi-label): 先转化为$f_{MLL}:\mathcal{Z}\rightarrow 2^{\mathcal{Y}}$, 对于任意$z_i\in \mathcal{Z}, f_{MLL}(z_i) = f_{MIML}(X_i)$ if $z_i\in\phi(X_i), \phi: 2^{\mathcal{X}}\rightarrow\mathcal{Z}$, 再转化为$f_{SISL}:\mathcal{Z}\times\mathcal{Y}\rightarrow{-1, +1}$, $f_{MLL}(z_i) = {y|\arg_{y\in\mathcal{Y}}[f_{SISL}(z_i,y)=+1}$
- MINIBOOST (在每轮boosting中试图将$\mathcal{F}(B)$扩展为$\mathcal{F}(B)+cf(B)$)
- 将每个MIML样本 $(X_u, Y_u)$ 转化为 $|\mathcal{Y}|$ 个multi-instance bags ${[(X_u,y_1), \Psi(X_u,y_1)],…,[(X_u,y_{|\mathcal{Y}|}), \Psi(X_u,y_{|\mathcal{Y}|})]}$
- 初始化每个bag的权重$W^{(i)} = \dfrac{1}{m\times |\mathcal{Y}|}$
- 对于迭代次数$t=1,2,…,m\times |\mathcal{Y}|$:
- 令$W_j^{(i)} = W^{(i)}/n_i$, 将bag 的label $\Psi(X^{(i)},y^{(i)})$赋给其中的instance $(x_j^{(i)}, y^{(i)})$， 训练一个 instance-level的学习器 $h_t[(x_j^{(i)}, y^{(i)})]$.
- 对第 $i$个bag, 计算其错误率, $e^{(i)} = \dfrac{\sum_{i=1}^{n_i}\llbracket{h_t[(x_j^{(i)}, y^{(i)})]\neq\Psi(X^{(i)},y^{(i)})}\rrbracket}{n_i}$
- 若 $e^{(i)} < 0.5$ 对所有 $i\in [1,2,…,m\times|\mathcal{Y}| ]$, 则跳出循环
- 计算$c_t=\argmin_{c_t}\sum_{i=1}^{m\times|\mathcal{Y}}W^{(i)}\exp[(2e^{(i)}-1)c_t]$
- 如果$c_t < 0$, 则跳出循环
- 令 $W^{(i)} = W^{(i)}\exp[(2e^{(i)}-1)c_t]$, 重新正则化使得 $0\leq W^{(i)}\leq 1$且$\sum_{i=1}^{m\times|\mathcal{Y}| }W^{(i)} = 1$
- 返回 $Y^* = {y|\arg_{y\in\mathcal{Y}}sign(\sum_j\sum_tc_th_t[(x_j^,Y)])=+1}$ ($x_j^$是$X^*$的instance)
- P.S. 损失函数为:
$$\begin{aligned}
E_{\mathcal{B}}E_{\mathcal{G}|\mathcal{B}}[\exp(-g\mathcal{F}(B)+c(-g\mathcal{F}(B)))] &= \sum_i W^{(i)}\exp[c\left(-\dfrac{g^{(i)}\sum_jh(\mathbf{b}_j^{(i)})}{n_i}\right)]\
&= \sum_iW^{(i)}\exp[(2e^{(i)}-1)c]
\end{aligned}$$
- MINISVM
- 对MIML样本 $(X_u, Y_u), \Gamma = {X_u|u=1,2,…,m}$
- 从$\Gamma$中随即选择$k$个元素初始化$M_t$, 重复以下直到$M_t$不再变化:
- $\Gamma_t = {M_t}$ (t=1,2,…,k)
- 对于每一个 $X_u\in (\Gamma-{M_t|t=1,2,…,k})$:
- $index = \argmin_{t\in{1,…,k}}d_H(X_u, M_t), \Gamma_{index} = \Gamma_{index} \cup {X_u}$
- $M_t = \argmin_{A\in\Gamma_t}\sum_{B\in\Gamma_t}d_H(A, B)$ (t=1,2,…,k)
- 将 $(X_u, Y_u)$ 转化为 multi-instance 样本 $(z_u, Y_u), z_u = (z_{u1}, z_{u2}, …, z_{uk}) = (d_H(X_u, M1), d_H(X_u, M_2),…,d_H(X_u,M_k))$
- 对于每个$y\in\mathcal{Y}$, 生成一个数据集 $\mathcal{D} = {(z_u,\Phi(z_u,y))|u=1,2,…,m}$, 然后训练一个SVM $h_y = SVMTrain(\mathcal{D}_y)$
- 返回 $Y^* = {\argmax_{y\in\mathcal{Y}}h_y(z^)}\cup{y|h_y(z^) \geq 0, y\in\mathcal{Y}}$
- P.S. Hausdorff distance: $d_H(A,B) = \max{\max_{a\in A}\min_{b\in B}|\mathbf{a} - \mathbf{b}|, \max_{b\in B}\min_{a\in A}|\mathbf{b} - \mathbf{a}|}$
On Multi-Class Cost-Sensitive Learning – Zhihua Zhou, Xuying Liu, AAAI 2006#
- rescale classes 针对二分类问题有很好的效果, 但是针对多分类代价敏感问题效果不好. 原理: rescale让代价不敏感的算法变得代价敏感, 对于二分类问题, $p = P(class=1|\mathbf{x})$, 作出最优选择的阈值$p^$满足
$$p^\times\epsilon_{11}+(1-p^)\times\epsilon_{21} = p^\times\epsilon_{12}+(1-p^*)\times\epsilon_{22}$$
- Elkan Theorem: 对应原先的概率阈值$p_0$设置新的阈值$p^$, 则第二类的个数应乘以$\dfrac{p^}{1-p^*}\dfrac{1-p_0}{p_0}$. 推广到多分类, rescale时$i$类相比于$j$的比例是$\tau_{opt}(i,j)=\dfrac{\epsilon_{ij}}{\epsilon_{ji}}, \epsilon_i = \sum_{j=1}^c\epsilon_{ij}, w_i = \dfrac{(n\times\epsilon_i)}{\sum_{k=1}^cn_k\times\epsilon_k}, w_i$是赋给每个类样本个数的权重.
- 传统rescale方法赋的比例$\tau(i,j) = \dfrac{w_i}{w_j} = \dfrac{\epsilon_i}{\epsilon_j}$, 和上一条相比只在$c=2$时一样, 其余情况不等, 因此传统rescale方法针对多分类情况会不适用.
- The $RESCALE_{new}$ Approach
$$\begin{aligned}
\dfrac{w_1}{w_2} = \dfrac{\epsilon_{12}}{\epsilon_{21}}, \dfrac{w_1}{w_3} = \dfrac{\epsilon_{13}}{\epsilon_{31}}, …, \dfrac{w_1}{w_c} &= \dfrac{\epsilon_{1c}}{\epsilon_{c1}}\
\dfrac{w_2}{w_3} = \dfrac{\epsilon_{23}}{\epsilon_{32}}, …, \dfrac{w_2}{w_c} &= \dfrac{\epsilon_{2c}}{\epsilon_{c2}}\
…\ \ \ \ \ \ \ \ …\ \ \ \ \ \ \ &\ …\
\dfrac{w_{c-1}}{w_c} &= \dfrac{\epsilon_{c-1,c}}{\epsilon_{c,c-1}}
\end{aligned}$$
可以构造出一个$c$元一次方程组.
Where am I: Place instance and category recognition using spatial $\tt{PACT}$ – Jianxin Wu, James M.Rehg, 2008, CVPR#
- “Where am I” 问题: 经典的机器人问题, recognize instances and categories of places or scenes. 在视觉中常被处理为场景识别问题 (场景的类别而不是具体位置)
- PACT: Principal component Analysis of Census Transform histograms.
- CT: 一个没有参数的局部转换方法, 可以建立局部的相关性. 将图片转换成灰度图, 每九个像素($3\times 3$), 将中间的像素灰度和周围8个比较(比较结果用0/1)表示, 构成一个8位的二进制数, 转换成十进制数后作为CT代替原来的像素.
- CT的传递性保证了相距很远的像素对应的CT也有相关性.
- 再构造直方图统计不同CT值的数量
- 最后使用PCA计算对应特征值最大的特征向量, 对应主成分, 即图片中最主要的形状.
- Spatial PACT: 将图片分成小份, 在区域中其中计算相关性. 构造 “spatial pyramid”, 0,1,2-level对应不同的划分方式.
Semi-Supervised Learning with Very Few Labeled Training Examples#
- 传统半监督学习算法需要先通过少量标注数据训练一个初始弱学习器$h$, 再利用$h$和无标注数据. 但是在现实中很多任务能获得的标注数据很少, 比如基于内容的图像检索(搜索相似图片)或在线网页推荐(只拥有一个用户感兴趣的页面)
- OLTV (learning with One Labeled example and Two Views):
- CCV (Canonical correlation analysis): 定义两个视角间的相关投影. $X=(x_0,x_1,…,x_{l-1}), Y=(y_0,y_1,…,y_{l-1})$, 寻找两个基向量集合, 以最大化两个视角向量分别在基向量$w_x,w_y$上投影的相关性:
$$\mathop{\arg\min}\limits_{w_x,w_y} \left(\dfrac{w^T_xC_{xy}w^T_y}{\sqrt{w^T_xC_{xx}w^T_x\cdot w^T_yC_{yy}w^T_y}}\right)\
w^T_xC_{xx}w^T_x=1, w^T_yC_{yy}w^T_y=1$$
最终可以得到一个线性关系$C_{xy}C_{yy}^{-1}C){yx}w_x=\lambda^2C_{xx}w_x$. 也可用核函数映射到高维, 目标函数变为
$$\mathop{\arg\min}\limits_{\alpha, \beta}\dfrac{\alpha^TS_xS_x^TS_yS_y^T\beta}{\sqrt{\alpha^TS_xS_x^TS_xS_x^T\alpha\cdot\beta^TS_yS_y^TS_yS_y^T\beta}}$$
两个核矩阵为$K_x=S_xS_x^T, K_y=S_yS_y^T$, $\alpha, \beta$可以由$(K_x+\kappa I)^{-1}K_y(K_y+\kappa I)^{-1}K_x\alpha = \lambda^2\alpha, \beta = \dfrac{1}{\lambda}(K_y+\kappa I)^{-1}K_x\alpha$算出.
因此对于所有的$(x^,y^)$, 投影可以利用$\alpha, \beta$算出. 继而算出新样本和旧样本的投影的相似度, 将最像的作为新的正例, 最不像的作为负例.