Stack Overflowのアルゴリズム: Top Questions編

http://blog.stackoverflow.com/2010/11/stack-overflow-homepage-changes/

1 comment | 0 points | by WazanovaNews 2年以上前 edited


Jshiike 2年以上前 edited | ▲upvoteする | link

サイトが成長していくとすると、ユーザに表示すべきリストのアルゴリズムもそれに伴い調整しないと違和感がでてきます。事例として、Stack Overflowにアクセスすると表示されるTop Questionsリストの時系列での変化をまとめてみました。


1) 当初のアルゴリズム

最新のactivity date(activityの定義は、新しい質問、回答もしくは修正)順にソート

2) 2010年11月

問題点

質問数の急増により回答のペースが追いつかず、50%の質問が未回答の状態になり、Top Questionsリストも未回答が占める状態になる。

実験

calculateWeightファンクションでソートのアルゴリズムの各パラメータをユーザがフロント側で設定/保存できる機能を実験的に提供 [1] し、本件に関心の強いユーザからのフィードバックを募集。(実験を完了した後の最終的なアルゴリズムの反映はサーバ側)

変更後のアルゴリズム [2]

ユーザごとにカスタマイズされた表示をするために、直近のactive質問3000件に対し、

  • Ignoreタグ(興味がない項目をタグで明示できる仕組み)を含む質問を排除。
  • クローズされた質問を再オープンにする評判スコアが足りないユーザに対しては、クローズされた質問を排除。

そして、残った各質問に対して下記の内容で設定したソートのスコアを適用。

  • Interestingタグ(興味がある項目をタグで明示できる仕組み): タグ当たり+1,500、最大で合計+2,000
  • そのユーザのタグ上位40件(Ignore/Interestingで設定したタグではなく、各質問にはタグが最大5個設定されていて、対応したユーザにタグごとのスコアが貯まる仕組み。): タグ当たり最大+1,000(スコアに合わせて調整)、合計で最大+2,000
  • 質問スコア: +200 x スコア、合計で最大+1,000
  • 回答スコア計: -200 x スコア、合計で最大-1,000
  • 回答数: -200 x 回答数、合計で最大-1,000
  • 閲覧数: -15 x 閲覧数、合計で最大-1,000
  • 直近のactivity date: -1 x (秒数/15)

上位90件が採用されるが、更にその3,000件の中からログインユーザに対しては10%、非ログインユーザに対しては20%をランダムに混ぜてから表示する。


3) 2013年5月 [3]

問題点

ユーザとして直感的に感じるのは、利用したタグは全て同じロジックで評価されるべきだとは限らない。利用の動機は様々。また、特定のタグの利用は、それ単体だけでなく他のタグとも絡んだ文脈で使われるケースもある。

本当に知りたいのは未来のこと。既にある情報ではなく、この先どのような質問に回答したいのか。その二つは確実に関連しているが、必ずしも同じものではない。具体的に言うと、ユーザとサイト上でのそれまでのactivityの情報があれば、各タグに対して、そのユーザの将来の回答の何%がそのタグ含む質問になるのかを知りたかった。この場合少し事情を複雑にするのは、各質問に最大5個のタグが設定できるので、パーセントを合計しても意味はない。

検証結果

ユーザが将来回答する質問に付与されているタグを予想するのに、変更前のページと変更後のページに対して、それぞれA/Bテストで検証した結果わかったのは、

  • サイト上で40回以上使われるまでは、そのタグは考慮に入れるにあたいしない。
  • 3回以上回答するまでは、そのユーザの回答はタグの意味合いを把握するロジックの参考にできない。(たまたま出くわした質問に回答しただけで、興味とは関係ないかもしれない。)
  • テクノロジーがこれほどのスピードで変化していても、直近の履歴からサイト全体の平均を計算するよりも、今までの全ての履歴から計算した方が結果の精度が高かった。
  • サイト全体の平均が世の中のプログラマーの回答行動を示す指標になるので、まずサイト平均のタグを抽出し、それにユーザごとのactivityを反映させるのがよい。但し、あるタグが9回以上そのユーザの回答に該当すれば、サイト平均よりもそのユーザの履歴を反映させるほうがよい。3回から9回の間はリニアに変化していくとするのがよい。
  • 新しいユーザは、既存の似たようなユーザと同じ傾向の回答分野を選択するようになるという仮説のもと、既存のユーザの最初のn件の回答を参考し、新しいユーザがどのクラスタにあてはまるようになるか予想。ユークリッド空間の最小距離を計測すると、最初の60個のタグ(= ほぼ回答30件)で440のグループに分けることができた。
  • 「htmlとcss」「javascriptとjquery」「iosとobjective-c」のように、相関関係の強いタグの存在はある。一定量のデータがないと証明できないが、Stack Overflow上では12,000タグが該当した。基本の予想アルゴリズムによるデータを、主成分分析を使って相関関係を計算した結果で少しだけ調整するのがよいとわかった。

Stack OveflowのエンジニアであるKevin Montrose曰く [3] 、

モデリングのプロセスで大きく占めるのは、何のデータを見るのか。網を広く掛けすぎると、検証ボリュームは膨大になる。狭過ぎると、成果を逃すリスクがあがる。

全てお任せの機械学習を盲目的に使った鵜呑みにしないこと。何にでも適用できる手法が可能なケースももちろんありえるが、調査するドメインをよく理解したうえでの自分の感覚を活かしたほうが効果は大きい。

仮説をたてて検証することで、事実を確認するとともに、誤った思い込みを排除するプロセスは本当に重要ですが、闇雲に仮説を立てると、終わりのない果てしない、かつ光の見えない辛く苦しい戦いになります。深く考えて仮説をたてる。つまり、自分なりに落ち着いて考えて、確かそうだと強く思える仮説かどうか、というのが大切ですね。やる人によって、センスの差もでてくるスキルだと思います。


[1] http://meta.stackexchange.com/questions/69571/help-us-choose-a-sort-order-for-the-stack-overflow-homepage

[2] http://blog.stackoverflow.com/2010/11/stack-overflow-homepage-changes/

[3] http://kevinmontrose.com/2013/05/22/your-future-on-stack-overflow/


2014 Topアクセスランキング


Back