Coda

メモ FastXML: A Fast, Accurate and Stable Tree-classifier for eXtreme Multi-label Learning

August 24, 2019

表題にあるExtreme multi-label classificationの手法を紹介する。 Extreme multi-label classificationの目的は、大量のラベルの候補から与えられたデータに関連する複数のラベルを推定する学習器を構築することにある。 FastXMLは、弱学習器に決定木を使うアンサンブル学習であり、ノードの分割の評価関数にnDCGを採用することで、学習にかかる時間と予測精度の向上を意図している。

Extreme classificationの難しさは、言うまでもなくラベルの候補数が多いことにある。 Extreme classificationにおけるベースラインとして多クラス分類の1-vs-Allがあるが、1-vs-Allはラベルの数だけ学習器が必要であり、 ラベルの数が多くなるとそれだけ学習と予測に計算コストが線形に増えてしまう。

ラベル数に対する計算コストの増加に対して、木構造でコストを削減する手法が既に確立さている。 葉に近いノードほどラベルが少ない木構造にすることで、計算コストの増加を劣線形や対数にできる。 それでも、依然として計算コストは高く、ランダムフォレストをもちいるMLRFだと何千ものノードをつかうクラスタが必要になる。

本論文では、決定木のノードの分割の代表的な評価関数に、よく使われるジニ係数や交差エントロピーなどではなく、nDCGを使い、訓練にかかる時間と予測性能の向上を達成した。 計算コストについていえば、先述のMLRFだとクラスタが必要になるような学習データであっても、一台のデスクトップPCで一日かければ学習できるまで計算コストが下がっている。 提案したnDCGを用いた評価関数は、学習する重みについて連続ではなく勾配法では解けず、最適化が難しい。 そこで、本論文は、最適化のためのアルゴリズムを提案し、アルゴリズムが収束することを示している。 精度におけるnDCDGを採用した理由は、正のラベルは負のラベルよりも少量かつ重要になるという非対称性をランキングとして評価に含めることができることにある。


論文はこちらからダウンロードできます。