论文笔记: 极限多标签学习之 FastXML

摘要: 分享对论文的理解, 原文见 Yashoteja Prabhu and Manik Varma, FastXML: A Fast, Accurate and Stable Tree-classifier for eXtreme Multi-label Learning.

1. 论文贡献

• Fast, Accurate and Stable Tree-classifier
• 学习的过程中, 直接优化 nDCG
• 代码: http://research.microsoft.com/~manik/code/FastXML/download.html

2. 相关工作

2.1 1-vs-All 复杂度分析

使用线性分类器, 每个标签的训练复杂度为 $O(N\hat{D})$; 其中 $\hat{D}$ 看作正标签的数量.
所有标签的训练复杂度为 $O(LN\hat{D})$.
所有标签的预测复杂度为 $O(L\hat{D})$.
但这种 baseline 方案的效果并不差.

2.2 嵌入方法

由于数据矩阵与标签矩阵都是稀疏、低轶的, 使用矩阵, 将它们映射到低维空间.
使用 $D\times \hat{D}$ 矩阵映射数据矩阵; $L\times \hat{L}$ 矩阵映射标签矩阵.
对于标签矩阵而言, 预测后使用相同的矩阵进行逆映射即可.

2.3 基于树的方法

Label Partitioning by Sub-linear Ranking (LPSR) 训练一个基础分类器, 再构建一棵标签树.
Multi-label Random Forest (MLRF) 使用树的集成.

3. FastXML

3.1 总体方案

利用属性对样本进行聚类与分割.
Algorithm 1 只是一般性的对象划分, 以及叶节点的建立. 但它需要建立 $T$ 棵树, 有随机森林的感觉.

3.2 学习节点 (数据子集) 划分

• 直接优化 nDCG

前 $k$ 个标签的下标
$${\mathrm{rank}}_k(\mathbf{y})=[i_1^{\mathrm{desc}},\dots ,i_k^{\mathrm{desc}}{]}^{\mathsf{T}}\text{\hspace{1em}(1)}$$
给定一个排列 $\mathbf{r}$ (即预测的顺序), 相应的 DCG 值为
$${\mathcal{L}}_{DCG@k}(\mathbf{r},\mathbf{y})=\sum _{l=1}^k\frac{y_{r_l}}{\log (1+l)}$$
对于前 $k$ 个预测值, $y_{r_l}=1$ 表示预测正确, $y_{r_l}=0$ 表示预测错误,
nDCG 的讨论见 论文笔记: 极限多标签学习的基本理解

• 优化目标
  $$\min \Vert \mathbf{w}{\Vert }_1+\sum _i{C}_{\delta }({\delta }_i)\log (1+e^{-{\delta }_i{\mathbf{w}}^{\mathsf{T}{\mathbf{x}}_i}})-C_r\sum _i\frac{1}{2}(1+{\delta }_i){\mathcal{L}}_{{nDCG@}_L}({\mathbf{r}}^{+},{\mathbf{y}}_{\mathbf{i}})-C_r\sum _i\frac{1}{2}(1-{\delta }_i){\mathcal{L}}_{{nDCG@}_L}({\mathbf{r}}^{-},{\mathbf{y}}_{\mathbf{i}})\text{\hspace{1em}(5)}$$
  其中 $\mathbf{w}\in {\mathcal{R}}^D$, δ ∈ { − 1 , + 1 } L \mathbf{\delta} \in \{-1, +1\}^L δ∈{−1,+1}L, ${\mathbf{r}}^{+},{\mathbf{r}}^{-}\in \Pi (1,L)$ 为 $1$ 到 $L$ 的排列. $C_{\delta }$ 和 $C_r$ 是用户定义的重要度权值.
  各部分解释如下:
• 第一部分使用 $l_1$ 范数保证线性分类器权值的稀疏性;
• 第二部分是分类导致的损失项. 其中 ${\mathbf{w}}^{\mathsf{T}}{\mathbf{x}}_i$ 是线性分类器对 ${\mathbf{x}}_i$ 的预测. 在前面乘以 $-{\delta }_i$ 使得正确分类的函数值为负, 自然指数值更小, loss 也更小.
• 第三部分是对 nDCG 的评估, 该值越大损失函数值越小. 当 ${\delta }_i=-1$ 的时候对当前分类没有贡献, 相应值为 0. 这里考虑了所有的标签排序 ($L$ 个), 而不仅仅是 $k$ 个.
• 第四部分与第三部分同理.

另外需要注意:

• 使用 $L$ 个标签避免在根结点做太重要的决定, 导致大量信息丢失.
• 一个标签可能在正负簇里面同时出现.
• $\delta$ 和 $\mathbf{r}$ 独立写出来是为了易于高效地优化.

3.3 预测

$$\mathbf{r}(\mathbf{x})={\mathrm{rank}}_k\left(\frac{1}{T}\sum _{t=1}^T{\mathbf{P}}_t^{\mathrm{leaf}}(\mathbf{x})\right)\text{\hspace{1em}(6)}$$

4. 优化算法

与平常的梯度下降不同，设计了专门的优化算法:

• 初始化 $\mathbf{w}=0$, ${\delta }_i$ 根据均匀分布取 $\pm 1$ (即概率各为 $0.5$);
• 保持 $\mathbf{w}$ 和 $\delta$, 优化 ${\mathbf{r}}^{+}$ 和 ${\mathbf{r}}^{-}$, 以此来对相应簇的标签进行排序;
• 保持 $\mathbf{w}$ 和 ${\mathbf{r}}^{\pm }$, 优化 $\delta$;
• 保持 $\delta$ 和 ${\mathbf{r}}^{\pm }$, 优化 $\mathbf{w}$, 只有在前两步无法减小损失的时候做.

5. 小结

任重道远.