FastXML: A Fast, Accurate and Stable Tree-classifier for eXtreme Multi-label Learning(2014)
August 24, 2019Extreme multi-label classificationの手法である。 Extreme multi-label classificationは、大量のラベルの候補からデータに関連する複数のラベルを推定するタスクである。 FastXMLは、決定木を弱学習器にしたアンサンブル学習であり、ノードを分割するための評価関数にnDCGを採用することで、学習時間を短縮し、予測精度を向上させた。
Extreme classificationの難しさは、言うまでもなくラベルの候補数が多いことにある。 Extreme classificationにおけるベースラインに多クラス分類の1-vs-Allがあるが、1-vs-Allはラベルの数だけ学習器が必要であり、 ラベルの数が多くなるとそれだけ学習と予測に計算コストが線形に増えてしまう。
ラベル数に対する計算コストの増加に対して、木構造でコストを削減する手法はすでにあるが、依然として計算コストは高い。 葉に近いノードほどラベルが少ない木構造にすることで、計算コストの増加を劣線形や対数にできる。 それでも、依然として計算コストは高く、ランダムフォレストをもちいるMLRFだと何千ものノードをつかうクラスタが必要になる。
FastXMLでは、決定木のノードの分割の代表的な評価関数に、よく使われるジニ係数や交差エントロピーなどではなく、nDCGを使い、訓練にかかる時間と予測性能の向上を達成した。 計算コストについていえば、先述のMLRFだとクラスタが必要になるような学習データであっても、一台のデスクトップPCで一日かければ学習できるまで計算コストが下がっている。 提案したnDCGを用いた評価関数は、学習する重みについて連続ではなく勾配法では解けず、最適化が難しい。 そこで、本論文は、最適化のためのアルゴリズムを提案し、アルゴリズムが収束することを示している。 精度におけるnDCDGを採用した理由は、正のラベルは負のラベルよりも少量かつ重要になるという非対称性をランキングとして評価に含めることができることにある。
論文はこちらからダウンロードできます。
雑記
DCGを損失関数に使うアプローチは、ランキング学習のLambdaRankでも採用されている。