(cache) Robust Extreme Multi-Label Learning (KDD2016)を読んだ

マルチラベル分類を少し勉強しているので読んだ．もう一つ読んだので，近々もう一本マルチラベル関連で読んだので投稿するかも．．．（自分の研究があまり進んでないのでしないかも

今回はラベル行列の次元縮約（行列分解）をすることでマルチラベル分類の精度を上げる手法（去年，私がIBISに投稿しようとして諦めたのと同じ部類に属する手法ラベル行列をRobust PCAのような形で，Outlier行列を設けて分解する．ただそれだけ．そうすると，従来のPCAを用いた手法やSamplingによる行列分解と比べてよい結果になるらしい．それと，列毎に分解するんで超大規模にも対応しているということで，この題名．

モチベーション

大規模なマルチラベル分類（一つのサンプルが1つ以上のラベルを持つ）を解きたい．
そこでマルチラベル手法では近年，ラベル行列を分解して小さくして解くという手法が提案されている．ここでLabel Space Dimension Reduction(LSDR)と呼ぶことにする．マルチクラス分類と異なり，サンプルがラベルを持つか持たないかのベクトルでラベル情報を表現するためにラベルの表現が行列になる $Y \in \{0,1\}^{N \times L}$ ．ここでは訓練サンプル数，そしてはラベル数とする．しかし，ラベル行列が大規模になるのと，実際のラベル行列が行列分解するための仮定である，低ランク構造を持つということが成り立たなくなる．
そこで，提案法は，Outlier termを設けて何とかしましょうという話．(最適化の制約として，cardinality をつかってるという点では多分GoDecとかそっちの類になるはずただ outlierも行列の積にして書いているという点で少し違うっぽい．

前準備 LSDRとは

実際にLSDRは以下のように分類を行うものである

$\begin{equation} Y\simeq WH, \end{equation}$

ここで $W \in \mathbb{R}^{N \times K}$ と $H \in \mathbb{R}^{K \times L}$ であり， $K \ll N,L$ である．要は小さな行列に分解するということである．基準は適していれば何でもいい．

そうすると分解して得られたは0-1ではないものの，小さなで擬似的なラベルが振られたと解釈できる．そこでこれに対して，Regressionを用いて適当に

$\begin{equation} W \simeq XV, \end{equation}$

というように重み $V \in \mathbb{R}^{F \times K}$ 行列を学習してやる．は特徴の次元で，行列 $X \in \mathbb{R}^{N\times F}$ である．これを前の式に代入することで元のラベルへの分類ができるようになる．

$\begin{equation} Y \simeq XVH, \end{equation}$

これの目的はまず学習する重みのパラメータ数が $F \times L$ から $F \times K$ に減少しているということ次に低ランク構造からラベル間の関係である(label-dependency)がモデルにくみこまれているということ仮にそのままRegressionすると個に対して独立に求めることになっている．

コントリビューション

Outlier項を追加した手法の提案これは超大規模データセットではほんの数回しか出現しないラベルなどがものすごい数存在するため，普通の行列分解ではノイズとなり無視されてしまうため．別の項に退避させて評価してあげようということ
Divide and Conquer手法による高速化の提案
手法のTheoreticalな分析数式だらけになるから紹介しないけど，幾つかのErrorのboundが示されてるのと，divide and conquerの妥当性についても幾つか

提案法

2つの低ランク構造を持つ行列で近似することを考える

$\begin{equation} Y \simeq \hat{Y} +\hat{Z}, \end{equation}$ そして制約として，

$\begin{equation} rank(\hat{Y}) \leq K, \ \ card(\hat{Z}) \leq s \end{equation}$ を設けて分解を行う．

どちらもLSDRに流れで学習するので，そのままを込みで学習するような形をとると

$\begin{equation} Y \simeq \hat{Y} +\hat{Z}=Y \simeq XUV +XH, \end{equation}$ となる．

先の制約は面倒なので，制約を以下のように緩和してやって最適化を解く．これでお終い

$\begin{equation} rank(\hat{Y}) \rightarrow \beta (||U||^2_F +||V ||^{2}_F) \end{equation}$

$\begin{equation} card(\hat{Z})\rightarrow \alpha ||H||^2_F + \gamma ||XH||_1 \end{equation}$

まとめると

$\begin{equation} \min_{U,V,H} || Y- XUV -XH ||^2_F +\alpha ||H||^2_F +\beta (||U||^2_F +||V ||^2_F) + \gamma ||XH|| \end{equation}$

最適化はもうどれもこれも一発でOK．逆行列をつかってOK，ただしはADMMなどを使って最適化．交互最適化で収束するまで，実装も楽そうだから近々実装しとく

提案法 (Divide-and-Conquer)

ラベル毎にサンプリングして別々にを学習して，最後は最初に得られたの列空間へprojectionする．ここら辺は，短くて詳しく書かれていないけども，[Mackey+ NIPS11]をそのまま用いている模様．

実験結果

[Bhatia+ NIPS15]で提案されたSLEECという手法が鬼強いんだけども，あるデータセットでは勝っている．（それでも比較したデータセットが少なすぎる）正直なところ驚き，SLEECはLSDRの枠組みじゃなくて非常に強くてLSDR手法では勝てないと思っていたから．そういう点では，しっかりと手法を考察して研究していくということが大事なんだなと反省．
Divide-and-Conquerは分解する数を増やすと精度がすごい勢いで下がっていく．10個に分割するとおおよそ10% Top-1 precisionが下がる．提案法はSLEECに2%程差をつけて勝っているが，2個に問題を分割したとたん負ける模様．論文では，自由にユーザーのご希望で高速化と精度の欲しいところをとれという主張．(計算量の比較と計算時間の比較がない，supplementaryにあるのかも．．．ただ全然Extremeじゃない模様)

所感

Divide-and-Conquerには無理があるという印象．結局分割数1でとかないと従来法には勝てない．ただLSDR手法と比較すると10個に分割しても勝てているっぽいので，いい手法なんだろうなと思う．計算量については分割してもサンプル数が大きくなると計算できなくなる(サンプル数は分割されない）ので，もう少し工夫が必要になりそう．同時にKDD2016の[Jain+ KDD2016]も読んでいるけど，最近（今年のKDDにおける手法)の流行は極端に出現回数が少ないラベルをどう扱うかがテーマになっているっぽい．そのためにoutlier項を扱って処理するというのは理にかなっている気がする．

北の大地から

北大でひっそりと研究

Robust Extreme Multi-Label Learning (KDD2016)を読んだ

モチベーション

前準備 LSDRとは

コントリビューション

提案法

提案法 (Divide-and-Conquer)

実験結果

所感