Recommendation仕様の検討

[MatsuTaku]

Recommendationは各ユーザにとってある程度有用な難易度帯の問題をいい感じに表示する機能です。 Recommendationで表示された問題を解いていく方法で精進している人も多く、AtcoderProblemsで人気が高まっています。 ここでは、Recommendationをより良い機能にするための議論がここでできればと思います。

まず現状の仕様に依存する課題を整理します。

次に、ひとまず考えられる改善案を提案します。

現在のRecommendationの仕様

• 大きく3つの難易度で分類 ({Easy, Moderate, Difficult} = {0, 1, 2})
• 各難易度dごとに基準推定正解率Sdを設定し、|Sd-Pi| の小さい順にレコメンド。ここで、Piはユーザの問題iに対する正解率
  • {S0, S1, S2} = {0.8, 0.5, 0.2}
• 問題ごとに以下の情報を表示
  • 難易度
  • 推定正解率
  • 推定回答時間

問題点

• 現在のRecommendationが推薦する問題は局所に集中しています。 この仕様により、難易度区分の境目付近に該当する正解率の問題が現れにくい、推薦される問題を上から解いていった場合に基準推定正解率に近い問題から消化されて谷のようになってしまう、という現象が起こってしまいます。

• 問題の難易度に関する具体的な情報は、問題に対して先入観を与える可能性があります。 解こうとしている問題がどれくらいの難易度の問題か、という情報は問題の考察に影響を与える恐れがあり、それを知ってしまうことで本番で挑む場合よりも考察難易度が下がってしまう可能性があります。

提案

情報量

問題の詳細な難易度に関連する情報の表示は少なくともオプションにした方がよいと思います。

難易度区分

難易度ごとに推定正解率の範囲を設定します。 範囲を設定することで、次で提案する問題の選出方法の実装を容易にします。 範囲の決め方には、https://github.com/kenkoooo/AtCoderProblems/pull/681#issuecomment-660456902 の案が参考になると思います。

区間を分ける際の閾値ですが、 推定正解率p(x) は 問題の難易度とレートの差x のシグモイド関数になっていますので、xの次元で等分になるように計算するようにしました。 基準として、最も難しい（HARD）区分が(推定正解率 <= 0.1)となるように設定しました。 (画像は1-推定正解率のグラフ)

問題の選出方法

推定正解率の範囲内でランダムがよいと思われます。 ランダムであれば、表示される問題を順に消化していっても、消化される問題の推定正解率の分布が一様になります。 また、解こうとしている問題の難易度予測を曖昧にすることで、問題に対する先入観の強さを緩和します。

推定正解率に基づく問題の検索

現在のRecommendationの仕様を踏襲して、任意の推定正解率に基づいた問題の検索機能を別に提供してもよいかもしれません。

[MatsuTaku]

上記の提案を形にしたものをDraftに挙げました #787

既存のRecommendationタブの隣に以下のページを仮置きしました

• 問題の情報量はあえて減らしています ？ボタンをクリックすると詳細を確認できます

• 問題の並びはランダムです 現在は簡単な実装のため、ページをリフレッシュするたびにシャッフルされます 使い勝手が悪ければ、フィルタ設定ごとの問題リストのキャッシュ等を検討します

• 問題の推定正解率に基づいて問題を分類します 各難易度の分け方は以下の画像と対応します 推定正解率の下限は0.03としました（適当です） (y: Predicted solve probability, x: Meaning of problem difficulty) https://www.desmos.com/calculator/iuc0sjckze

[MatsuTaku]

推薦する問題の選び方について

このページを利用するユーザに以下のニーズを仮定しました

ユーザーは、実力の向上を目的としてこのページを利用する

ここで、AtCoderのレート表記は、99.9%の確率でそのレート以上の実力があることを保証する数字になるように設定されています( AtCoderのレート計算式 - レートとパフォーマンス , https://twitter.com/chokudai/status/829601624502919168 )

したがって、ユーザの実力向上に寄与する問題の難易度は、実際のレートに対する評価よりも難しい側（上の画像で言う中心より右側）にある可能性が高いです

このような思考の元、推薦する問題の範囲をユーザのレートに対する推定正解率が低い範囲に対してリッチな情報量になるように設定しました

この設計に関しては主観が強く反映されていますので、ご意見いただけると幸いです

[kenkoooo]

情報量が多いので、問題の選び方と問題の見せ方の2つに分けたほうが良いと思います。

[kenkoooo]

ご自身で使ってみた感想をお聞きしたいです。

僕の個人的な体験としては Recommendation の Moderate は、たしかに 50% くらいの確率で解ける感覚はありますが、ギリギリ解けた、あるいはギリギリ解けなかった、という手応えであり、易しい問題だと感じることはありません。なので、個人的な感覚ではありますが Easy=易しい問題、Moderate=難しい問題、Hard=無理、と感じていて、難しい側が充実しても、僕はそんなに嬉しくないです。

[amylase]

AtCoderのレート表記は、99.9%の確率でそのレート以上の実力があることを保証する数字

というのは、コンテストによるパフォーマンス測定にはばらつきがあるという前提のもとで、たくさんコンテストに出てないうちはレーティングの推定量には大きなばらつきがあるのでそのばらつきのぶんだけ割り引こうという話で、実はこれはいわゆるリセマラ排除補正のことです。これを取り除くには単に内部レーティングを使用すればよく、Recommendationではすでにそのようにしているので、この点だけを持ってより難しい問題に寄せたほうがいいという結論にはなりません。

でも、例えば練習で問題を解いているときはコンテスト中よりも長い時間をかけられるのが一般的ですから、そのぶんだけより難しい問題に挑戦できるという考え方はありえます。他にもいろいろな要素が本番と練習では異なるので50％という具体的な値にはあまり意味がないようにも思え、実際に使ってみた感覚に頼る必要があるのかもしれません。

個人的には50%だと程よい手応えの問題が出てくるのですが20％はとても手が出ない問題が多く、kenkooooさんの感覚に近い印象を持っています。

[MatsuTaku]

情報量が多いので、問題の選び方と問題の見せ方の2つに分けたほうが良いと思います。

その通りですね。まず選び方から話を進めようと思います。

AtCoderのレート表記は、99.9%の確率でそのレート以上の実力があることを保証する数字

というのは、コンテストによるパフォーマンス測定にはばらつきがあるという前提のもとで、たくさんコンテストに出てないうちはレーティングの推定量には大きなばらつきがあるのでそのばらつきのぶんだけ割り引こうという話で、実はこれはいわゆるリセマラ排除補正のことです。これを取り除くには単に内部レーティングを使用すればよく、Recommendationではすでにそのようにしているので、この点だけを持ってより難しい問題に寄せたほうがいいという結論にはなりません。

ご指摘ありがとうございます。仮説の不備に納得しました。

個人的な推定正解率に対する印象

• 90%以上: 確実に解ける
• 80%付近: レート維持のために確実に解けるようになりたい
• 50%付近: ここは解釈が広いが、丁寧に考えれば解ける
• 20%付近: コンテスト中に解けることもある。私の精進のホットスポットはここ
• 10ー3%: 稀に手足が届く
• 以下: ほぼ不可能

10-3%は、解ける可能性もあり、解説を読んで理解するだけでも学びがある難易度帯だと感じていて、Recommendationの範囲に含めておきたいなと感じます。 実力のポテンシャルに本番のパフォーマンスが追いついていない人は、この辺りがちょうど良くなっていると思います。

80%付近も、レートを安定させるために練習しておきたいというニーズはありそうだと感じました。 (この難易度帯については、”Easy”ではなく”Stable”等と表記したほうがいいかもしれません。Easyが解けないと辛いのと、精進用にも選ばれにくそうなので。)

個人差がかなり大きそうというのは分かりました。 レート帯によっても印象は違っていそうですね。

[MatsuTaku]

選び方には、ユーザに必要十分な選択肢を与えることが重要かなと思いますので、どの範囲と分類数が必要十分かで議論したいです。 名前の付け方も肝になってくると思います。

以下のような分け方ではどうでしょうか。

1. 右寄り4区間 https://github.com/kenkoooo/AtCoderProblems/compare/master...MatsuTaku:classify-idea1

2. 右寄り3区間 https://github.com/kenkoooo/AtCoderProblems/compare/master...MatsuTaku:classify-idea2

3. 中央3区間 https://github.com/kenkoooo/AtCoderProblems/compare/master...MatsuTaku:classify-idea3