极限多标签之FastXML

极限多标签之FastXML"/>

极限多标签之FastXML

《FastXML：A Fast, Accurate and Stable Tree-classifier for eXtreme Multi-label Learning》阅读笔记

References:
原文以及：
=1001.2014.3001.5502

核心创新点：

1. 直接优化 n D C G nDCG nDCG；
2. 该模型训练一个随机森林manner的分类器；时间复杂度低；并且能implicitly learns balanced partitions?.

Related works (由于不甚了解XC的问题，故给出一些前人研究工作):
如果假定训练一个线性01分类器的代价是 O ( N D ^ ) O(N\hat{D}) O(ND^)，那么1-vs-all基线分类器的训练代价为 O ( L N D ^ ) O(LN\hat{D}) O(LND^)，预测代价为 O ( L D ^ ) O(L\hat{D}) O(LD^)。
但是1-vs-all分类器infeasible，当 L , D ∼ 1 0 5 − 1 0 6 L, D \sim 10^5 - 10^6 L,D∼105−106。

嵌入式(Embedding)方法一般在计算复杂度方面优于一般的1-vs-all的分类器。不过该文说嵌入式方法并不优于1-vs-all方法（as to 2014），当 L ^ ≈ log ⁡ ( L ) \hat{L} \approx \log(L) L^≈log(L)。

在嵌入式方法由于标签非常稀疏，通常压缩标签数量为 L → L ^ L \rightarrow \hat{L} L→L^。
低维嵌入方法: y ^ = P y \hat{\mathbf{y}} = \mathbf{P}\mathbf{y} y^​=Py，其中 P P P是一个 L ^ × L \hat{L}\times L L^×L的投影矩阵。
如果在压缩后的标签上应用1-vs-all分类器，那么时间代价将降低至：training: O ( L ^ N D ^ ) O(\hat{L}N\hat{D}) O(L^ND^)；prediction: O ( L ^ D ^ ) O(\hat{L}\hat{D}) O(L^D^)。

嵌入式方法需要引入额外的开销 O ( L ^ L ) O(\hat{L}L) O(L^L)，以将压缩后的标签逆变换回 L L L。

另外一种嵌入式方法压缩特征 x ^ = R x ∈ R L ^ \hat{\mathbf{x}} = \mathbf{R}\mathbf{x} \in \mathbb{R}^{\hat{L}} x^=Rx∈RL^，类似于压缩标签那样。

本文比较的两个关键工作：
LPSR: 训练1-vs-all基线分类器，在此基础上，训练一个二叉树状的层次结构。样本将递归地pass down这个树。
MLRF:学习一个随机森林进行决策.

###本文工作

FastXML学习一个层次,并不是在label space上(一些传统multi-class会这样做),而是在feature space上.
Note: 原文是将样本空间进行了划分,实际上是将在特征空间上相近的样本有监督地划分到一个子空间.在特征空间上的相似是根据 w T x > 0 ? \mathbf{w}^\text{T}\mathbf{x}>0? wTx>0?来决定的. 所以说这里是feature space,大概是这个意思吧.

如Algorithm 1, FastXML训练一组randomized tree (like random forest), 从根节点开始(包含所有样本), 递归地对节点进行划分, 每次划分会将一部分样本划分到左子树,将另外一部分样本划分到右子树. 核心方法是SPLIT_NODE,它决定了如何划分样本,并学习当前节点的线性决策向量 n . w n.\mathbf{w} n.w.
当叶子节点的样本数 ∣ n . I d ∣ < MaxLeaf |n.Id| < \text{MaxLeaf} ∣n.Id∣<MaxLeaf,其中 MaxLeaf \text{MaxLeaf} MaxLeaf是一个超参数-叶子节点的最大样本数.

如Alogrithm 3, 在预测阶段, 给定一个样本 x \mathbf{x} x, 该样本将递归地按照决策边界 n . w T x n.\mathbf{w}^{\text{T}}\mathbf{x} n.wTx决定被分配到左子树还是右子树,直到达到leaf node.
最后获取当前样本在每颗树的叶子节点的top-k score (i.e., n . P n.\mathbf{P} n.P)取平均. 再求得 rank k \text{rank}_k rankk​,作为最终的预测.

Note: 这个top-k score就是叶子节点所包含的所有样本标签的均值的top-k.

核心工作

令 r a n k k ( y ) = [ i 1 d e s c , … , i k d e s c ] T \mathbf{rank}_k(\mathbf{y}) = [i_1^{desc},\dots, i_k^{desc}]^{\text{T}} rankk​(y)=[i1desc​,…,ikdesc​]T, 令 Π ( 1 , L ) \Pi(1, L) Π(1,L)为 { 1 , … , L } \{1,\dots, L\} {1,…,L}的所有排列组合构成的集合, 令 r ∈ Π ( 1 , L ) \mathbf{r} \in \Pi(1, L) r∈Π(1,L).
定义
L DCG@ k ( r , y ) = ∑ l = 1 k y r l log ⁡ ( 1 + l ) \mathcal{L}_{\text{DCG@}k}(\mathbf{r}, \mathbf{y}) = \sum_{l=1}^k \frac{y_{r_l}}{\log (1 + l)} LDCG@k​(r,y)=l=1∑k​log(1+l)yrl​​​
L nDCG@ k ( r , y ) = I k ( y ) ∑ l = 1 k y r l log ⁡ ( 1 + l ) \mathcal{L}_{\text{nDCG@}k}(\mathbf{r}, \mathbf{y}) = I_k(\mathbf{y}) \sum_{l=1}^k \frac{y_{r_l}}{\log (1 + l)} LnDCG@k​(r,y)=Ik​(y)l=1∑k​log(1+l)yrl​​​
其中 I k ( y ) = 1 ∑ l = 1 min ⁡ ( k , 1 T y ) 1 log ⁡ ( 1 + l ) I_k(\mathbf{y}) = \frac{1}{\sum_{l = 1}^{\min(k, \mathbf{1}^\text{T}\mathbf{y})} \frac{1}{\log(1 + l)}} Ik​(y)=∑l=1min(k,1Ty)​log(1+l)1​1​.

FastXML为每一个节点定义优化目标(核心目标):
min ⁡ ∣ ∣ w ∣ ∣ 1 + ∑ i C δ ( δ i ) log ⁡ ( 1 + exp ⁡ ( − δ i w T x i ) ) − C r ∑ i 1 2 ( 1 + δ i ) L nDCG@ L ( r + , y i ) − C r ∑ i 1 2 ( 1 − δ i ) L nDCG@ L ( r − , y i ) \begin{aligned} \min ||\mathbf{w}||_1 & + \sum_i C_\delta(\delta_i) \log(1 + \exp(-\delta_i\mathbf{w}^\text{T}\mathbf{x}_i)) \\ & - C_r \sum_i \frac{1}{2}(1 + \delta_i) \mathcal{L}_{\text{nDCG@}L}(\mathbf{r}^+, \mathbf{y}_i) \\ & - C_r \sum_i \frac{1}{2}(1 - \delta_i) \mathcal{L}_{\text{nDCG@}L}(\mathbf{r}^-, \mathbf{y}_i) \end{aligned} min∣∣w∣∣1​​+i∑​Cδ​(δi​)log(1+exp(−δi​wTxi​))−Cr​i∑​21​(1+δi​)LnDCG@L​(r+,yi​)−Cr​i∑​21​(1−δi​)LnDCG@L​(r−,yi​)​

其中 w ∈ R D , δ i ∈ { − 1 , 1 } w \in \mathbb{R}^D, \delta_i \in \{-1, 1\} w∈RD,δi​∈{−1,1} (原文写错了), r + , r − ∈ Π ( 1 , L ) \mathbf{r}^+, \mathbf{r}^- \in \Pi(1, L) r+,r−∈Π(1,L).
C δ , C r C_\delta, C_r Cδ​,Cr​为代价(user defined).

之所以将优化目标定义成这样,有几点原因:

1. 剥离 δ , r ± \delta, \mathbf{r}^{\plusmn} δ,r±是为了更高效地优化. (并未将这两个参数表征为 w \mathbf {w} w的函数)
2. Dr. Min认为使用 nDCG @ L \text{nDCG}@L nDCG@L而不是 k k k是为了避免在根节点做太重要的决定,从而导致大量信息丢失?
   实际上 nDCG @ p \text{nDCG}@p nDCG@p这里的 p p p对所有的根和内部节点都是相同的.
   原文说明了根据所有标签进行优化是为了保证局部优化不短视.
   原文进一步说明: 采用 L L L而不是 k k k是有好处的,尽管最后预测的时候仍然采用 k < < L k << L k<<L.
   例如，在维基百科数据集的根节点上对k=5的nDCG进行优化，就相当于找到一个分离器，使所有分配给正面分区的几十万维基百科文章都能准确地被贴上正面分区中出现频率最高的五个维基百科类别的标签，对于负面分区也是如此。似乎如此做会导致travial solution?
3. Dr. Min认为相同的标签可能在正负簇同时出现, 这是正常的. 一个簇里面更可能包含的是相似的标签,不同簇里面更可能包含的是不相似的标签. 并不能保证在不同簇里就一定没有相同的标签.
4. 原文作者认为,起作用的是少量特征(不同的节点这些特征大概不同),因此采用 ℓ 1 \ell_1 ℓ1​范数保证稀疏性(相比于 ℓ 2 \ell_2 ℓ2​)和易优化(相比于 ℓ 0 \ell_0 ℓ0​).
5. 为什么采用 nDCG \text{nDCG} nDCG而不是 DCG \text{DCG} DCG-尺度问题.

####优化过程

问题的限制: 肯定不能使用SGD,也不能使用次梯度下降. (次梯度下降可用于不可微凸问题的优化,这个问题不是凸问题).

本文采用了交替优化算法(作者居然证明了,厉害):
先优化 r ± \mathbf{r}^{\plusmn} r±,再优化 δ i \delta_i δi​,最后优化 w \mathbf{w} w,之所以是这样的优化顺序,是因为优化目标的各个项的影响顺序是 r ± → δ i → w \mathbf{r}^{\plusmn} \rightarrow \delta_i \rightarrow \mathbf{w} r±→δi​→w.
本文并非完全采用三者交替优化的方法，这是因为针对 w \mathbf{w} w的优化过程很慢，本文采用了一种策略是先完全优化 r \mathbf{r} r和 δ \delta δ，当这两者中的 δ \delta δ不变的时候，再优化 w \mathbf{w} w。

优化 r ± \mathbf{r}^{\plusmn} r±

固定 w \mathbf{w} w和 δ \delta δ, 优化 r ± \mathbf{r}^{\plusmn} r±, 显然问题可转化为:
max ⁡ r ± ∈ Π ( 1 , L ) ∑ i ( 1 + δ i ) L nDCG@ L ( r + , y i ) + ∑ i ( 1 − δ i ) L nDCG@ L ( r − , y i ) \max_{\mathbf{r}^{\plusmn} \in \Pi(1, L)} \sum_{i} (1 + \delta_i) \mathcal{L}_{\text{nDCG@}L}(\mathbf{r}^+, \mathbf{y}_i) + \sum_{i}(1 - \delta_i) \mathcal{L}_{\text{nDCG@}L}(\mathbf{r}^-, \mathbf{y}_i) r±∈Π(1,L)max​i∑​(1+δi​)LnDCG@L​(r+,yi​)+i∑​(1−δi​)LnDCG@L​(r−,yi​)

如何优化呢?结合 L nDCG@ L \mathcal{L}_{\text{nDCG@}L} LnDCG@L​的公式可以得到:
max ⁡ r ± ∈ Π ( 1 , L ) ∑ i ( 1 + δ i ) I L ( y i ) ∑ l = 1 L y i r l + log ⁡ ( 1 + l ) + ∑ i ( 1 − δ i ) I L ( y i ) ∑ l = 1 L y i r l − log ⁡ ( 1 + l ) \max_{\mathbf{r}^{\plusmn} \in \Pi(1, L)} \sum_{i} (1 + \delta_i) I_L(\mathbf{y}_i) \sum_{l=1}^L \frac{y_{ir_l^{+}}}{\log (1 + l)} + \sum_{i}(1 - \delta_i) I_L(\mathbf{y}_i) \sum_{l=1}^L \frac{y_{ir_l^{-}}}{\log (1 + l)} r±∈Π(1,L)max​i∑​(1+δi​)IL​(yi​)l=1∑L​log(1+l)yirl+​​​+i∑​(1−δi​)IL​(yi​)l=1∑L​log(1+l)yirl−​​​
两个独立的问题(因为本身 r + \mathbf{r}^{+} r+和 r − \mathbf{r}^- r−是独立的):
max ⁡ r + ∈ Π ( 1 , L ) ∑ i : δ i = 1 I L ( y i ) ∑ l = 1 L y i r l + log ⁡ ( 1 + l ) \max_{\mathbf{r}^{+} \in \Pi(1, L)} \sum_{i: \delta_i = 1} I_L(\mathbf{y}_i) \sum_{l=1}^L \frac{y_{ir_l^{+}}}{\log (1 + l)} r+∈Π(1,L)max​i:δi​=1∑​IL​(yi​)l=1∑L​log(1+l)yirl+​​​
max ⁡ r − ∈ Π ( 1 , L ) ∑ i : δ i = − 1 I L ( y i ) ∑ l = 1 L y i r l − log ⁡ ( 1 + l ) \max_{\mathbf{r}^{-} \in \Pi(1, L)} \sum_{i: \delta_i = -1} I_L(\mathbf{y}_i) \sum_{l=1}^L \frac{y_{ir_l^{-}}}{\log (1 + l)} r−∈Π(1,L)max​i:δi​=−1∑​IL​(yi​)l=1∑L​log(1+l)yirl−​​​

原文整合到一块了:
max ⁡ r ± ∈ Π ( 1 , L ) ∑ i : δ i = ± 1 I L ( y i ) ∑ l = 1 L y i r l ± log ⁡ ( 1 + l ) ≡ max ⁡ r ± ∈ Π ( 1 , L ) ∑ l = 1 L ∑ i : δ i = ± 1 I L ( y i ) y i l log ⁡ ( 1 + r l ± ) ≡ max ⁡ r ± ∈ Π ( 1 , L ) ( ∑ i : δ i = ± 1 I L ( y i ) y i ) T d ± \begin{aligned} & \max_{\mathbf{r}^{\plusmn} \in \Pi(1, L)} \sum_{i: \delta_i = \plusmn1} I_L(\mathbf{y}_i) \sum_{l=1}^L \frac{y_{ir_l^{\plusmn}}}{\log (1 + l)} \\ \equiv & \max_{\mathbf{r}^{\plusmn} \in \Pi(1, L)} \sum_{l=1}^L \sum_{i: \delta_i = \plusmn 1} \frac{I_L(\mathbf{y}_i)y_{il}}{\log (1 + r_l^{\plusmn})} \\ \equiv & \max_{\mathbf{r}^{\plusmn} \in \Pi(1, L)} (\sum_{i: \delta_i = \plusmn 1} I_L(\mathbf{y}_i) \mathbf{y}_i)^{\text{T}}\mathbf{d}^{\plusmn} \end{aligned} ≡≡​r±∈Π(1,L)max​i:δi​=±1∑​IL​(yi​)l=1∑L​log(1+l)yirl±​​​r±∈Π(1,L)max​l=1∑L​i:δi​=±1∑​log(1+rl±​)IL​(yi​)yil​​r±∈Π(1,L)max​(i:δi​=±1∑​IL​(yi​)yi​)Td±​
其中 d ± = [ 1 log ⁡ ( 1 + r l ± ) ] l = 1 L \mathbf{d}^{\plusmn} = [\frac{1}{\log(1 + r_l^{\plusmn})}]_{l=1}^L d±=[log(1+rl±​)1​]l=1L​.
第二步容易理解,第三步里面 d ± \mathbf{d}^{\plusmn} d±独立于 i i i,因此可以拆解出来表示为两个向量的内积.
为了取极大:
r ± ∗ = rank L ( ∑ i : δ i = ± 1 I L ( y i ) y i ) \mathbf{r}^{\plusmn *} = \text{rank}_L(\sum_{i: \delta_i = \plusmn 1} I_L(\mathbf{y}_i) \mathbf{y}_i) r±∗=rankL​(i:δi​=±1∑​IL​(yi​)yi​)
容易理解. 比如两个向量 A ∈ R n A \in \mathbb{R}^n A∈Rn和 B ∈ Π ( 1 , n ) B \in \Pi(1, n) B∈Π(1,n),A和B的内积要最大,那么必然可排序A向量使得最小的分量对应1,次小的分量对应2,…,最大的分量对应n.

优化 δ \delta δ

等价于极小化
min ⁡ δ i ∈ { − 1 , 1 } C δ ( δ i ) log ⁡ ( 1 + exp ⁡ ( − δ i w T x i ) ) − C r 1 2 ( 1 + δ i ) L nDCG@ L ( r + , y i ) − C r 1 2 ( 1 − δ i ) L nDCG@ L ( r − , y i ) \begin{aligned} \min_{\delta_i \in \{-1, 1\}}& C_\delta(\delta_i) \log(1 + \exp(-\delta_i\mathbf{w}^\text{T}\mathbf{x}_i)) \\ & - C_r \frac{1}{2}(1 + \delta_i) \mathcal{L}_{\text{nDCG@}L}(\mathbf{r}^+, \mathbf{y}_i) \\ & - C_r \frac{1}{2}(1 - \delta_i) \mathcal{L}_{\text{nDCG@}L}(\mathbf{r}^-, \mathbf{y}_i) \end{aligned} δi​∈{−1,1}min​​Cδ​(δi​)log(1+exp(−δi​wTxi​))−Cr​21​(1+δi​)LnDCG@L​(r+,yi​)−Cr​21​(1−δi​)LnDCG@L​(r−,yi​)​
由于 δ i ∈ { − 1 , 1 } \delta_i \in \{-1, 1\} δi​∈{−1,1},因此对每个 x i \mathbf{x}_i xi​, 取两个的极小就可以了. 导出
δ i ∗ = sign ( v i − − v i + ) , v i ± = C δ ( ± 1 ) log ⁡ ( 1 + exp ⁡ ( ∓ w T x i ) ) − C r I L ( y i ) ∑ l = 1 L y i r l ± log ⁡ ( 1 + l ) \begin{aligned} & \delta_i^* = \text{sign}(v_i^- - v_i^+), \\ & v_i^{\pm} = C_\delta(\plusmn1)\log(1 + \exp(\mp \mathbf{w}^\text{T}\mathbf{x}_i)) - C_r I_L(\mathbf{y}_i)\sum_{l=1}^L\frac{y_{ir_l^\pm}}{\log(1 + l)} \end{aligned} ​δi∗​=sign(vi−​−vi+​),vi±​=Cδ​(±1)log(1+exp(∓wTxi​))−Cr​IL​(yi​)l=1∑L​log(1+l)yirl±​​​​

优化 w \mathbf{w} w

等价于
min ⁡ w ∈ R D ∣ ∣ w ∣ ∣ 1 + ∑ i C δ ( δ i ) log ⁡ ( 1 + exp ⁡ ( − δ i w T x i ) ) \min_{\mathbf{w}\in \mathbb{R}^D} ||\mathbf{w}||_1 + \sum_i C_\delta(\delta_i) \log(1 + \exp(-\delta_i\mathbf{w}^\text{T}\mathbf{x}_i)) w∈RDmin​∣∣w∣∣1​+i∑​Cδ​(δi​)log(1+exp(−δi​wTxi​))
通过newGLM-Net算法进行优化, newGLM-Net专门解决 ℓ 1 \ell_1 ℓ1​正则的Logistic regression(不懂).

作者给出了优化算法的伪代码,也就是节点划分方法:

总结

1. 本文提出了一个解决XMC的算法,训练阶段:(1) 建立randomized trees; (2) 每棵树递归地生成节点(top-down); (3)样本划分基于每个阶段训练出的决策边界 n . w n.\mathbf{w} n.w; (4) n . w n.\mathbf{w} n.w由一个优化目标给出; (5)该优化目标直接针对 nDCG \text{nDCG} nDCG.
   预测阶段: 给定一个新样本 x \mathbf{x} x,在每颗树上,按照 n . w T x n.\mathbf{w}^\text{T}\mathbf{x} n.wTx是否大于0被划分到左子树/右子树,直到叶子节点. 通过每颗树达到的叶子节点的top-k scores平均, 就预测出了样本的 rank k \text{rank}_k rankk​标签.

2. 内涵: 将特征空间上相近的样本划分到相同的簇, 相近是根据 w T x > 0 ? \mathbf{w}^\text{T}\mathbf{x}>0? wTx>0?决定的(监督学习).

3. 优缺点分析: 优点:不需要训练1-vs-all分类器,训练性能高(样本空间划分 --> 特征空间划分), Bagging降低了variance, 创新性强. 缺点(强行说): 没有对标签空间和特征空间进行降维, 如果降维,计算复杂度有可能进一步降低,但降维可能带来信息损失; Bagging通常不鼓励使用,因为任何机器学习算法都可以从模型平均中大幅获益; 实现比较复杂; 不一定全局最优.