2008-08-14

Netflix Prize 外野席

"集合知プログラミング" という本が出たらしい. 私の積読には元本の "Programming Collective Intelligence" があって, 途中まで読んだまま放置していたら日本語訳が出てしまった. (オライリーのアンチパターンと命名.) 悔しいので本は処分. そのうち日本語版で続きを読もう....

興味を持っていたのは推薦エンジン(協調フィルタ)だった. 私の中では検索エンジンに匹敵するウェブのハイテクという位置付けなんだけど, 草の根には普及しておらず悲しい. 検索エンジンでの Hyper Estraier や senna に相当する協調フィルタの立ち位置は デッドヒートが予想される...とだいぶ前から思ってるんだけど, いまのところ閑古鳥気味. まったく, 出し抜くだけの実力があればなあ.

先の皇帝ペンギン本では, 一章にさっそく協調フィルタが登場する. 読んでみると, 簡潔な python のコードであっさりアルゴリズムが実装されている. 著者とリスト内包表記の力に目を見張る. 例題は del.icio.us を使った推薦エンジン. 私もさっそく ruby で del.icio.us 用エンジンを書いたけど, いまいちうまく動かなかった. del.icio.us は取得できるデータが制限されている上に, すぐ throttling されてしまう. 十分なデータが揃わないとレコメンダの旨味はでない. (私のコードにバグがあっただけかもしらんけど...)

そのあと少し真面目に作りなおそうと調べ物をしていたら, 海外では Netflix Prize という 推薦エンジンコンテストで盛り上っていたのを知った.

Netflix Prize

Netflix はアメリカにあるオンラインレンタルビデオ屋で, 日本でいうと ぽすれん みたいなものだろうか. 割と人気のあるサービスらしく, friendfeed でも対応している. でも日本はサービス外で, すっかり外野気分.

Netflix は Amazon ばりの協調フィルタを持っており, ユーザの試聴記録と評価の星から次に見るべきビデオを勧めてくれる. あるとき, この協調フィルタの性能に限界を感じた Netflix は思いきった行動に出る. アルゴリズムの一般公募を始めたのだ. そのコンテストが Netflix Prize というわけ.

コンテストは 2006 年に始まり, 2011 年(!)まで続く. 賞金は 100 万ドル. 年に一回 "Progress Prize" という途中経過の表彰もある. こちらは賞金 5 万ドル. 2007 年に最初の Progress Prize が贈られている.

参加者は匿名化された実データのサブセットをダウンロードし, 自分のアルゴリズムで計算した推薦データ投稿する. 運営システムはその投稿を秘密の実データと比較, 誤差を評価する. 誤差が小さいほど成績があがる. 現在のランキングは leaderboard で一覧できる. score が誤差, improvement が Netflix のシステム (Cinematch) からの改善分をあらわしている.

Prize が始まってしばらくは, 賞金目当ての猛者と外野が大層盛りあがっていたらしい. そんな祭りに乗りそびれたのは悔しいけれど, レースはまだ続いている. いまさら様子を眺めてみよう.

Try This at Home

コンテスト開始から数ヶ月後, 参加者のひとり Simon Funk が自身のアルゴリズムを ウェブで公開し波紋を呼んだ. Simon は行列ベースの協調フィルタ(皇帝ペンギン本で紹介されているようなの)では必須となる SVD の高速な実装を紹介している.

購買情報のように極めて疎な行列は推薦エンジンのアリゴリズムで扱いにくい. そこでより低い次数をもつ, 密度の高い行列に変換して扱うのが機械学習の定石となっている(らしい). SVD はこうした次元の縮退に用いるツールのひとつで, ふつうは計算に時間がかかる. Simon のアルゴリズムを使うと SVD の近似を高速に計算できるという. (計算そのものより結果の更新の速さが売りなんだけれど, まあそれは細かい話.) Prize 参加者に走った衝撃は, 当時の Forum のスレッド を見るとわかる. これ以降, アマチュア参加者がまずやるべきなのはこの Simon's SVD を実装することになったと言っていい. Netflix Prize 入門サイトでは必ず紹介されている.

ちなみに Simon 自身は既にコンテストから身を引いたのか, ランキングにそれらしい名前はない. 2007 年のインタビュー(PDF) を読んだ範囲でもやる気はなさそう. なんとなくかっこいい.

いまでは Simon Funk 以外にもいくつかのチームが自らのアルゴリズムを解説している. そうした解説は leaderboard からリンクされている各チームのページで見ることができる. (ワークショップもあった らしい...)

When Gravity and Dinosaurs Unite

2007 年の冬, 参加者の一群は Progress Prize に向けて凌ぎを削っていた. トップを走るのは "KorBell". AT&T の研究者 Yehuda Koren と Bob Bell のチームだ. (プロかよ...) そして後を追う "Team Gravity" と "Team Dinosaur Planet". どちらも学生(当時)がやっている. 締切も差し迫ったころ, KorBell を追うこの 2 チームが手を組み, "When Gravity and Dinosaurs Unite" を結成する. そしてお互いの出力をブレンドし, 結果を改善したのだ. トップに躍り出る重力の恐竜! (画像は上のページから拝借)

しかし KorBell も黙ってはいない. すかさず新しい結果を投稿し, 彼らを抜き返したのだ. 結局そのまま KorBell が逃げきり, 第一回の Progress Prize を手中に収めた. 終盤の白熱した様子は Berkeley science review の取材が詳しく伝えている.

その夜, 僕とチームメイトはほとんど眠らなかったから, 頭の中は新しいテクニックやどうやってそれを混ぜるかで一杯だった. コードを仕立てて何個か新しい方法を試した, 結果はよくなった. けれど決着がついてみると BellKor がトップだったのさ.

それにしても <出力をブレンドする> なんてことができるんだろうか? これを可能にするのが, ensemble learningboosting と呼ばれる一連のアルゴリズムだ(と Wikipedia に書いてあった. 私はよくしらない...). トップの KorBell も, 実は 100 以上のアルゴリズムを合成したと解説記事で明らかにしている. やりすぎだろ... KorBell はブレンドにも工夫をしている: テストデータを性質に応じて 15 に分割し, 個々の部分集合(bin)ごとに別々の重みを与えているのだ. こうすることで, データの性質による得手不得手をある程度補い合えるという.

KorBell の後継である BellKor は今も leaderboad でトップの座を守り続けている. Team Gravity はレコメンダ屋を 起業 した. もう一つのトップ常連である BigChaos起業 している. みんながんばってね.

心理学者の追撃

上位の膠着状態が続くなか新星が現れた. その新星, "Just a guy in a garage" は しばらく所在を明らかにせず, 利用しているアルゴリズムについてもまったく知られていなかったが, 今年 2 月の WIRED の記事 が彼の正体を明らかにした.

記事によると Just a guy... の作者は Gavin Potter というイギリス在住の心理学者で, もともとは IBM でコンサルをしていたらしい. 機械学習でも勉強するかと会社をやめた傍ら手をつけた Netflix Prize で, 目を見張る成果を上げることになる. Gavin Potter はアルゴリズムの詳細を明らかにしていないが, 先の記事では "アンカリング" など 行動経済学の知見をとりこんだと謳っている. 自身の blog でも, 他の参加者は "ignore the fact that there are humans actually making the ratings." と指摘し, そこに勝機を見ているようだ. また 他のエントリ では "シリーズもの同士の相関" というように, コンテンツの中身に踏みこんだ調査もしている. たしかに評価データを行列やベクトルとみなす数学者的アプローチとは少し違う視点を持っているのかもしれない.

WIRED の記事は多くの関心を集めたようだ. マンネリ化が始まったかに見えた leaderboard にも新風を吹きこんだ. 記事を読んで興味をもったという PragmaticTheory チームは, 早くも第 3 位に食い込んでいる.

Wikinomics blog も今年に入ってから この Prize に言及するなど, 開始から 2 年近くがたった Netflix Prize は今なお何か面白いことが起きそうな予感を孕んでいる.

データセットにまつわる話

Netflix Prize の公開したテストデータは画期的なものだった. それ以前に世の中で公開されていた最大のデータセットは Movie Lens のもの で, これは 1,000,000 件のデータを含んでいた. 対する Netflix のデータはおよそ 100,000,000 件のデータを含む. 二桁多い. この巨大なデータがアカデミアの興味を引いたのは間違いない. かつて Amazon でレコメンダを開発していた Greg Linden もこの点を評価している. ある新しいアリゴリズムが現実のデータセットで使えるだけスケールするのか, 研究者は検証のしようがなかった. 洗練されたアルゴリズムよりデータの量がものをいう 世界でこれは困ってしまう. Prize のデータセットはそんな状況を改善した. (Netflix は 一日 200万件のペースで評価データが増える というから, この 1 億件もたかだか二ヶ月分なんだけどね...)

リアルで巨大なデータセットは思わぬ問題に繋がる. ある研究者が, Netflix Prize のデータセットから匿名性を暴く研究を公表した. この研究では, あるユーザについて 7-8 件の評価(と評価日)情報がわかれば, そのユーザを Prize のデータセットから特定できるとしている. 雑談のつもりで映画の善し悪しをを話したら, 他の(人には言えないような)ビデオの閲覧情報が明らかになってしまうわけ. ちょっと気味が悪い. この研究に限らず, データセットや推薦結果のプライバシは昨今の協調フィルタの分野では割とよく研究されているようす. 面倒だけど仕方ないのかもしらん.

オープンソースの推薦エンジン

色々読み物を眺めているうちに, 実際のコードをみたくなってきた. 探してみるとオープンソースの実装がいくつかあった. PHP 向けの Vogoo と Java 製の Taste は, そこそこ開発が続いているように見える. Vogoo のサイトにはいくつか採用実績が載っている. 日本では 映画生活 が採用しており, ウノウラボにも紹介記事 があった. Taste のサイトにはそうした記述は見当らないが, その割にはちゃんと作ってあるんだよな. 開発者自身が使っているのかもしれない. (...と思ったけど開発者の Sean Owen は Google のプログラマなので, 仕事じゃ使えなそうだなあ. やっぱり単なる趣味かもね.)

PHP はしんどいので Java で書かれた Taste のコードをみると, Netflix Prize に出てくるような高等なアルゴリズムは使っていない. ただデータの入出力やアルゴリズムを pluggable にするなど好感の持てる作りではある. Prize データを読み込むモジュールもあった.

その Taste が少し前に Apache の Mahout プロジェクトへ 統合されたのは興味深い. Mahout は Apache Hadoop の上に機械学習のライブラリを揃えようという野心的なプロジェクトで, Taste もそうしたライブラリに組込もうとしているのだろう. レポジトリをみたところ, Taste 用の Job (Mapper や Reducer) の実装が始まっている. Mahout で実装している SparseMatrix や SparseVector を使う様子はなく, 自身のデータ構造を使って Hadoop の上に実装を進めている. これまでの Taste は計算に使うデータをオンメモリに持つつくりになっており, 規模拡大に不安があった. Hadoop にあわせてうまくデータを分割できれば, こうした制限を押し広げることができるだろう.

Mahout も今のところ多くの機能が未実装で使えるかんじじゃないけれど, 熱心に開発が続いている. 二年もすれば実用になる並列計算のライブラリになっているんじゃなかろうか. 追いかけがいのあるプロジェクトだとおもう.

まとめ

さて, 勢いに任せて Netflix Prize の周辺をとりとめもなく眺めてみました. ウェブみてる暇があったらコード書けという話もあるけど, そこは夏休みということでお許しを. 暑くてね...

日本語で読める推薦エンジンの解説記事には, "推薦システム-情報過多時代をのりきる" などがある. 同じ著者によるもう少し詳しい入門記事として, 人工知能学会誌 の 2007/11 から三号続けて連載があった. 学生のひとは学校の図書館で読めるんじゃないでしょうか. 夏休みの暇潰しに Netflix Prize にのりこむのも面白そう. 一山あたったら宴会には呼んでね:D