春告げ鳥

興味のあることをごちゃ混ぜで書いているので、.カテゴリー別に閲覧することをオススメします

競プロ問題推薦システムの話

​この記事はkstm Advent Calendar 5日目です。

qiita.com

目的

プログラミングやアルゴリズムを勉強しようと思って競プロのジャッジシステムを使う方は多いと思います。
しかし、競技プログラミングは問題が多種多様だったり、難易度を決めるのがとても難しいです。効率よく学習するために、その人に合わせたプログラミングの問題を推薦するシステムがあれば学習者の負担やモチベーションの低下を防ぐことが出来るのではないかと考えました。
そこで作ったのがAtCoder-Recommendationです。

http://sandbox.ugwis.net/recommend/

github.com

これは、AtCoder上で解いた問題傾向と近いユーザーを探し、自分に対して解いてない問題を推薦するサービスです。

協調フィルタリング

他のユーザーとの距離を計算し、推薦するアルゴリズムを強調フィルタリングと言います。 推薦アルゴリズムには二種類の分類があり、内容ベースとユーザーベースの物があります。 内容ベースはアイテムの属性を数値（またはベクトル）で表現し、アイテム間の距離を計算することで推薦する手法です。
一方、ユーザーベースの推薦システムはユーザー間の距離を計算し、その距離から似たような傾向のユーザを探すことができます。
強調フィルタリングはユーザベースの推薦アルゴリズムで、実際の推薦する内容に関わらず統計的なデータをもとに推薦します。

AtCoder-Recommendation

AtCoder-Recommendationでも協調フィルタリングを使用して推薦しています。
まず初めに推薦したいユーザに近いユーザを探すためにジャッカード指数という式を計算し、ユーザー間の距離を計算します。
　　 { \displaystyle J(A,B) = \frac{|A \cap B|}{|A \cup B|} }

推薦するユーザとその他のユーザとの距離を計算すると、自分に近いユーザが解いていて自分が解いていない問題が分かります。

ユーザ間の距離をコストとして問題に重みづけをしていって、コストが一番小さいものがそのユーザに対して推薦するべき問題であることが分かります。

実際にコードとして書いてみるとそこまで時間はかからず、計算もそこまで複雑ではありません。

課題

推薦精度

今回作成したAtCoder-Recommendationに関わらず協調フィルタリングは内容を一切考慮しないため、推薦の精度に関しては内容ベースのものには劣ります。今回の場合は、「自分に近い人が解いていて自分が解いていない問題は自分にとっては簡単な問題である」という仮定のもとに推薦しています。しかし、AtCoderは基本的にオンラインコンテストとして時間を決めて問題を出題しているため、例えばそのときはたまたまコンテストに出られなかったので解いていないという場合も考えられるため、推薦する対象として適切である　とは言えません。Aizu Online Judgeの方がまだ推薦する対象としては良いかもしれません。

推薦結果の扱い方

今回のシステムでは推薦結果をEasy ,Medium, Hardの三種類に分けて推薦しています。自分にとって簡単な問題と、中くらい、ちょっと難しめという難易度になればよいなと考えていますが、実際にはすこし意味合いの違う推薦結果が出ています。推薦している部分のソースコードを読めばわかりますが、Easyはコストが大きい問題、Mediumは一番コストが大きい問題の半分のコストの問題、Hardは四分の一のコストの問題を順番に表示しています。
しかし、問題のコストというのは問題の難しさではなく、自分に近い人が良く解いているかどうかしか現れていません。相関関係はあると思いますが、自分があまり解いていない問題が難しい問題かどうかはまた別問題です。 Easy, Medium, Hardというのはニュアンスとしては間違っていて、Challenge Problemという風に書いた方が伝わるかもしれません。

今後の期待

今回作った推薦システムはユーザベースであったため、内容を一切考慮せずに推薦しました。統計的な処理だけでもここまでの精度が出せるのはすごいことだと思いますが、実際に使うにはもう少しユーザに対して親切な推薦が出来ればもっと良くなると思います。 以下は競プロ問題推薦システムの改善アイデアです。

対話形式で推薦

少し昔にネットで流行ったAkinatorという質問の回答を元に回答者の想像している物（または人物）を推定するというサービスがあります。 競プロ問題推薦システムでも同じようなシステムを作ることが出来るかもしれません。今日はフローの問題を解いてみたい気分だとか、簡単な問題を解きたいとかそういうのが対話形式で見つけられるかもしれません。

問題グラフ

推薦システムではありませんが、それぞれの問題の位置関係を二次元平面状で表せると面白いなと思います。同じ傾向の問題を近い位置にするには問題をベクトル化する必要があります。ぱっと思いつくのがTF-IDFのような計算を用いてそれぞれの問題間の距離を推定し、空間にプロットすると同じ傾向の問題は近くに表示されるのではないかという推測です。プログラミング言語もある意味では言葉であるので自然言語処理で用いている方法と同じやり方で出来る事があるかもしれません。二次元平面状でプロットすることが出来るようになると、k-Means等のクラスタリングアルゴリズムを使用することが出来るようになるので、コンピュータが問題の分類をすることが出来るようになるかもしれません。