Large Scale Learning to Rankを読んだ

論文紹介

　本当は三が日中にまともなエントリを1本ぐらいは書く予定だったのだが、ちょっと無理だった。というわけで、実質的に新年一本目のエントリです。Large Scale Learning to Rank (D. Sculley, NIPS Workshop on Advances in Ranking, 2009) (pdf) を読んだので、1本目のエントリとしてこの論文を紹介したい。
　では早速本題に入ろう。順位学習において、Pairwise Learningを単純に行うと、n^2の学習コストがかかる。これは計算時間としては厳しい部類に入る。そもそも順位学習ってなに、という人は、WWW2009のチュートリアル(pdf)とかを参照してください。
　Bottouらは、SGDの一般化能力はデータセットのサイズに依らず、どれだけのstochastic stepを実行したかで決まると言う事を示した。そこで、Sculleyは、データサンプルの全てのペアではなく、ランダムにペアをサンプリングすることで、劇的に学習を高速化した。
　この論文の一番の貢献は、ランダムサンプリングしても精度が落ちない、と言うところであると思うのだが、そこにたどり着くまでの論理展開がよくわからなかった。まず、Bottouらが「SGDの一般化能力はデータセットのサイズに依らず、どれだけのstochastic stepを実行したかで決まる」というような事を書いている文章が見つけられなかった。参照されている論文ではSGDの収束について議論されており、これは確かにデータセットのサイズというパラメータには依存していないのだが、Bottouらが文章でここまでの主張をした文章は見つけられなかった。また、一般化能力がデータセットのサイズによらないということと、じゃあデータサンプルからサンプリングを行うといいんじゃないの、という所のつながりもよくわからない。
　ともかく、Sculleyはランダムサンプリングによる順位学習の高速化をSPDと名付け、Pegasos, SGD-SVM, SGD-PA (Passive Aggressive) などを実装し、それがRankingSVMと同程度の精度を達成できる事を示した。RankingSVMとSPD化した手法では、大きなデータセットになると圧倒的な学習時間の差がついたが、これはアルゴリズムのオーダーを無理やり下げているので当たり前の話で、それよりもむしろ、10万ステップ、2.8GHzのCPUで0.2秒程度の学習時間で学習が終わっている点が特筆すべきところだろう。
　Pairwise Learningのコストは確かに単純に実装するとn^2なのだが、一方で、Pairwise Learningのメリットとして、学習データが作りやすいという点が挙げられる。つまり、文書A〜Eまであった時に正しい順番に並べるというのはむずかしいけれど、文書Aと文書Bのどちらのスコアを高くするべきか、という質問であれば前者の並べ替えよりは簡単だ。最初から人間がペアに対して正解をつける場合、n^2というのは膨大すぎるので、そもそも最初からランダムにサンプルされたデータに対して正解をつけるというタスクになるだろう。そういう意味では、この論文がやっていることは、Pairwise Learning（の一部）でこれまでやってきた事を提案しているにすぎない。
　そう考えるとむしろ、この論文の貢献は、すべてのペアに対してアノテーションせずとも、ある程度のデータ量に対して正解データをつければ、ランダムにサンプリングしたペアでも同等の精度を達成できるということを示した、という点にあるのではないかと考えられる。（もっとも、Pairwise Learningでこのような事が行われてきたと書いてある論文は、今ちょっと探した限りでは見当たらなかった。そういう意味では、これまでやってきた事を提案しているにすぎない、という評価は不当に低いかもしれない。）
　いずれにせよ、ランダムにサンプリングを行うという手法がアカデミックな世界に明示的には提案されていないという事を把握し、サンプリングでも同等の精度が達成できるということを示したという点は見事であり、素晴らしい論文であると言える。
　その他、気になる点としては、0.2秒とかの世界になってくると、どんな方法でランダムにサンプリングを行うかで実行時間が変わってくるというレベルであり、その点についても論文では言及している。
　今回はPairwiseアプローチの速度向上であったわけだが、Listwiseアプローチとの比較も気になるところだ。こちらはICML 2009に "Generalization Analysis of Listwise Learning-to-Rank Algorithms" (Y. Lan et al.) という論文が通っており、いくつかのListwiseアルゴリズムのgeneralization abilityに対する理論的な性能比較が行われている。理論的なPairwise, Listwiseの比較も気になるし、もちろん、Listwiseのアプローチが似たように手抜きしつつ現在と同程度の性能を達成できるのか、というところも気になる。まぁ、競争の激しい分野ですから、1年後には研究はだいぶ進んでることでしょう。
　ちなみに、D. Sculleyの現在の所属はGoogleである。今回の論文のソースコードについてもgoogle codeで公開されている。