The 2009 GitHub Contest

参加しています。
http://contest.github.com/:title=
内容は、簡単にいうとリコメンデーションエンジンのコンテスト。8/30までやっているので、まだまだ参加できます。
あんまり参加している人がいないようなのと、海外のブログとかだと戦略を説明している人がいたりするので、僕も簡単な紹介と僕が参加しようと思った理由、僕が今行っている方法について説明を書いておこうと思います。
僕は自然言語処理とかリコメンデーションとかあまり詳しくないのですが、昨日の時点では8番目に入っている(現在下降中…)ので、そんなにひどく間違ってはいないだろうということと、完全に同じ方法でも8位どまりでネタバレ的要素としても薄いので、説明してもそんなに害はないだろうということで。

内容

(詳細は、配布されているデータセット.zipのreadme.txtをみてください。)
データセットとして次のファイルが与えられます。

repos.txt
『リポジトリID:オーナー/リポジトリ名,作成日またはfork日,fork元リポジトリID(あれば)』を行としてリポジトリの情報が入っているファイル。約12万のリポジトリ情報が入っている。
lang.txt
『リポジトリID:言語1;行数1,言語2;行数2,,,言語N;行数N』を行として各リポジトリの使用言語が入っているファイル。約7.3万行しかないので、すべてのリポジトリの情報があるわけではない。
data.txt
『ユーザID:リポジトリID』を行として、ユーザがwatchしているリポジトリの情報が入っているファイル。1ユーザが複数のリポジトリをwatchしていることがあるので、ユーザIDのカラムはユニークではない。約5.6万ユーザの情報が入っている。ただしwatchしているリポジトリの情報がすべて入っているわけではない(一部欠けている)。
test.txt
『ユーザID』を行とした問題ファイル。4788行ある。

test.txtに入っているユーザIDの人はいくつかのwatchしているリポジトリがdata.txtに入っていないので、それがどのリポジトリであるかを当てるのが問題です。
回答方法としては、test.txtの各ユーザの欠けているリポジトリIDの候補を10個ずつを指定したファイル(results.txt)を作成してコンテストに登録しているリポジトリにcommitします。そうするとサーバ側でテストが行われ、その正解率がスコアになります。
意味的には、欠けているリポジトリはこれからwatchに追加する予定のリポジトリで、オススメを10個だした結果、実際にはどれだけwatchされたか、ということを評価の基準にしたいのだと思う。
ブログをみると、シンプルでオープンソースなリコメンデーションエンジンがほしいね、みたいな感じっぽい。

賞品

やろうと思った理由

もともとgithub入門をしたついでにちょっとだけやろうかと思って、よくありそうな『同じリポジトリを多くwatchしているユーザと同じリポジトリをwatchしている確率が高い』みたいなものを1時間程度で作って、そのときの上位組が正解率40%後半くらいだったので、まあこれで42%はいっただろうワロスなどと思いながらコミットしたところ13%だったでござる。
このときに、

  • なんでこんなに低いんだ？
  • 上位のやつらはなにをしているんだ？

というのが分からなかったので、これはやる意味があるよね、と思って丸一日くらい試行錯誤してたら、42%(12位くらい)までいって、大体コツが分かったのと同時にこれは完全データがない時点で現実を反映していないしコンテストのための問題とかクソであるので時間をかける意味はない、と思ってやめようと思ったんだけど、上のほうにデータマイニングを専攻している学生とかRuby Cookbookの著者とかいて、そのあたりの人には真面目にやっても勝てないんだろうなーなどと考えていたら悲しくなったので、せめてちゃんとやろうと思って、別リポジトリを作って参加することにした。

僕の今の方法

ソースコードは全部githubにあります。

今は、それぞれ別の特徴に基づいたリコメンデーションシステムを複数作って、それぞれの結果を確信度合いで重み付けて投票して最終的な予測を出す、という方法でやっています。
現在の正解率は48.14%です。1位が54.78%。
以下、簡単に説明。

forkbase_recommender.pl

ユーザがwatchしているリポジトリがforkしている場合、fork元のリポジトリをwatchしている可能性が高い、という考えに基づいてオススメを生成するもの。単体での正解率は23.76%。ただし、回答を8%しか埋めれていない(watchしているリポジトリがforkしてないと回答できない)ので、かなり正解率は高い。

author_recommender.pl

ユーザがwatchしているリポジトリの著者の別のリポジトリをwatchしている可能性が高い、という考えに基づいてオススメを生成するもの。単体での正解率は16.37%。

co_occurrence_recommender.pl

共起性うんぬんをやりたいんだけど、あんまりうまくできてない。今は、ユーザの類似度を一致しているwatchリポジトリの頻度の逆数で重み付けて計算して、その基準でユーザの近傍80人を抽出した後、それらのユーザがwatchしているリポジトリのランキングをユーザ間の類似度で重み付けて作って上位10をオススメにしている。単体での正解率は24.54%。頻度の逆数を使うのは、個性というのは大勢とは違う部分なので個性的な部分が似てるユーザはより似ているという基準。
ここは文章分類とかで研究されていると思うので、そのへんの成果を使おうと思って、潜在意味解析でリポジトリを軸にしたベクトルを次元削減して、そこでのコサイン類似度で似たユーザを抽出する、とかやってみているんだけど、上の方法より正解率悪かったので、何か悪いんだろうなどと悩んでます。(たぶん削減しすぎだ)
こいつの正解率がランクアップの鍵になると思ってる。

popular_recommender.pl

もともとは人気のあるリポジトリを適当にオススメしましょうというもの。現在は、ユーザがwatchしているリポジトリで使われている言語からユーザの使用言語を設定して、その中でマイナーな言語のリポジトリをwatchする可能性が高いという謎の基準で人気ランキングを再計算してる。単体での正解率は、6.57%。
これ以外のシステムは、回答を全部埋めることができないので、このシステムが出すオススメ情報は必ず使われる。なので、こいつの正解率は重要。

bagging_recommender.pl

上記4つのシステムが出した予測を各システムの正解率に基づいて重み付けて、最終的なオススメ情報を生成するもの。
「正解率に基づいて」と言いながら、重みは手動で適当に設定しているので、このパラメーターを自動で最適化すればもう少し全体の正解率が上がるんじゃないかと思ってる。
正解率は、48.14%。

個人的におもしろいはなし


全員がソースコードをgithubに全部置けば上位10までのソースコードを丸ごと持ってきて各システムが出した結果を統合する、とかもルール内でできますよね。
上位の中でも個性の強いシステムを選択すれば(あれば)正解率は上がると思っているんですが。ただ上位になるほど、完全なソースコードがない場合が多い。