github contest 日記 (おわり)

終わった。最終的に51%まであがった。
http://github.com/blog/481-about-the-github-contest:title=
http://contest.github.com/:title=

並びは3番目ですが、最後のほうで全員の結果を混ぜる人が続出したもののチートとして消されたり、上のほうにいたけど最後までソースコードが置かれなかったりで人が消えまくってるので3位とは言いがたいし、順位はマジでどうでもよくなった。
個人的にもできなかったことが多かったのであまり達成感はないのですが、いろいろ知らなかったことが分かったし、勘違いしていたことにも気づけたし、今後やっとくべきと思ったこともいくつかできたので、やってよかったですね。

知ったことの中から知っていて当然だろJK…なことをいくつか

疎なベクトルの類似度

リポジトリが15万件、ユーザが5万人いて、あるユーザに似ているユーザを抽出しましょーというタスクがある。このとき、リポジトリをwatchしてる|してないを1|0とする15万次元のベクトルを各ユーザに割り当てて、全ユーザとの距離なり類似度なり計算すればいいーと思うわけだけど、この計算はでかすぎて無理だろ…と思ってしまっていた。
ただ実際は、ほとんどの成分が0なので15万個の成分をすべて使う必要はないし、全ユーザについて比較する必要もない。例として内積を考えると、0*0=0なのと、1*1=1なことから、ユーザAがwatchしているリポジトリの集合とユーザBがwatchしているリポジトリの集合の積の要素数がの内積と一致しているので、計算にかかる時間は各ユーザがwatchしているリポジトリの平均数に関係している。またwatchしているリポジトリがひとつもかぶっていないユーザ同士は内積が0になることから、コサイン類似度など分子が内積の類似度は、watchしているリポジトリがひとつもかぶっていないと0になるし、ひとつでもかぶっていると0より大きくなる。なのでリポジトリごとにwatchしているユーザの転置インデックスを作っておけば、ユーザのwatchしているリポジトリの集合から類似度が0より大きくなるユーザだけを高速に抽出できるため、5万ユーザをすべて比較する必要もない。
などなど。

潜在意味解析は次元を削減するけど比較の計算にかかる時間は増える

潜在意味解析 - Wikipedia
文章分類やリコメンデーションでやる潜在意味解析という方法は、次元は削減するけれど、もともと疎だったベクトルを密にしてしまって、上で書いたような高速化テクニックが使えなくなるため、逆に遅くなる。なので名前のとおり、概念空間での比較とか、相関の高い成分をアレするのが目的ですよ（よく分かってない）。
CUR分解というでやれば、疎にできるらしい。

あとhttp://tedlab.mit.edu/~dr/svdlibc/:title=は使える

たくさん比較したわけではないけど、とりあえず使えた。入出力のファイルフォーマットで疎行列が扱えるのと、上位n個の特異値を求めたりできるので、メモリ使用量が少ないし速い。
15万x5万の行列のSVDが10秒くらいでできる。ちょっとソースコードをいじればWindowsでも動く。ちょっとソースコードをいじらないとLinuxでも動かなかったけど。