AtCoder Problems の難易度推定について
https://adventar.org/calendars/3865
Competitive Programming Advent Calendar 2019 の12月5日分です。この記事を書いた2019年12月時点でのAtCoder Problemsの難易度推定について、思いつく限りの話題を書きます。
あなたは誰？
AtCoder Problems に難易度推定をつけた人です。AtCoder社の人の次くらいにレーティングシステムに詳しいと思います。
AtCoder Problems の Difficulty ってなんですか？
現在の内部レーティング*1がこの値の人がコンテストでその問題を見たら50%の確率で解けると考えられる値です。過去のコンテストの結果から推定しています。
DifficultyがX色という表現をたまに見ますが、これは AtCoder Problems 上でそれぞれの問題が難易度に対応するレーティングカラーで表示されていることによります。
推定難易度の横に試験管の絵文字（🧪）がついている問題があります。これは公式のレーティングシステムが導入される以前の問題に対して、やや強引な手法で難易度を推定したものです。様々な理由で絵文字がない問題よりも推定の信頼度が低いと考えられます。
Twitterで見かける反応へのお返事 (Q&A)
Recommendation で絶妙な難易度の問題が出てきて便利、すごい、シンギュラリティ！
いえーい、ありがとうございます。
古い問題の推定難易度が高すぎない？（= 見た目の値よりも簡単に解ける）
公式レーティングを使った推定難易度とそれ以前の難易度 *2は、推定のもとになっているレーティングに連続性がないのでたぶん絶対的な水準がずれています。でもどう補正したらいいか見当がつかないので放置されています。
2020-03-15 追記: Experimental の推定に使っているレーティングの計算を見直して、どの問題も400くらい下がりました。なんとなくよくなった気がします。
参加者の少ないオンサイト決勝などで推定が変なことになってるよ
データが少なかったり全員がACしてるとおかしなことになります。こういう単純な場合は機械的なチェックで弾いてますが、それ以外にもどう見てもおかしいだろというのがあれば @pepsin_amylase までお知らせください。
X色になるにはX色の問題が毎回解けないとだめなの？ / X色の問題がコンテスト中に解けたらX色パフォが出るってこと？
X色タッチを目指す人にとってX色の問題はかなり難しいと思います。というのもX色の問題はX色の人が取り組んでだいたい正解率50%だからです。したがって、X色の問題が解けた回は平均的X色よりもよい成績だったと考えられますから、X+1色くらいのパフォーマンスが出ていても不思議ではありません。
2020-03-15: X色の問題を安定して特にはX+1色くらいの腕前が必要なようです。
AtCoder ProblemsのDifficulty（=50%の確率で解けるレート）と90%の確率で解けるレートを比較したら、だいたいレート400くらいの差があるっぽい pic.twitter.com/SdDqdtUCDT
— not (@not_522) 2020年3月6日
Difficulty がより低い問題の Solve Probability が高いとは限らないのはどうして？
正解率推定モデルのパラメータには difficulty（難易度）のほかに discrimination（判別力）というものがあり、これはレーティングと難易度の差が正解率にどれだけ影響するかの指標です。難易度が非常に低くても判別力も低ければ正解率はそれほど高くなりませんし、同じくらいの難易度で判別力が高ければ正解率はそれより高くなります。
音ゲーの難易度推定っぽい
世の中の音ゲーの難易度推定やレコメンドと同じ手法（項目応答理論）を使っているからだと思います。*3
以上がユーザー向けの情報です。以下はいわゆる開発者向け情報で、具体的なモデルと未解決問題の話になります。
モデルについて
公式のレーティングシステムが導入された後の問題は、コンテスト本番の (ユーザー, 問題) の対を1つのデータ点として内部レーティングを説明変数、その問題に正解したかを被説明変数とするロジスティック回帰によって正解予測モデルを作っています。このモデルで正解率が50%になる内部レーティングを difficulty としています。
公式レーティング以前については、AtCoderサービス開始時点から現在と同じ仕組みのレーティングシステムがあると仮定して仮想のレーティングを計算し、その値を用いて同様に難易度を決定しています。この仮想レーティングは間違いなく公式レーティングとズレがあるのですが（ないと考える理由がないので）、どうズレてるか計算する方法がわからないので Experimental Estimate と称してそのまま公開しました（カス）
正当化
Elo レーティング
相対的な強弱を測る統計的手法として広く用いられている Elo レーティングというものがあります。勝率はプレイヤー間のレーティング差のシグモイド関数で決まるという仮定（Elo仮定）から導き出されるモデルです。
ところで、Elo仮定を用いると AtCoder のパフォーマンスレートとはその順位となるような確率を最大化するレーティング、すなわち最尤推定であることがわかります。したがって、AtCoder のレーティングはある種の Elo レーティングと解釈できるわけです。
項目応答理論との整合性
実は、レーティングをロジスティック回帰に放り込むと結構うまくいくことは前々から知られていました。
これらの先行研究ではどちらも項目応答理論 (IRT) を利用したと説明しています。項目応答理論のうちのロジスティックモデルは、さきほどの Elo レーティングとの対比を意識した言い方をすれば、受験者のある問題の正解確率はレーティング差のシグモイド関数で決まるという仮定（IRT仮定）を用いて問題と受験者のレーティングを決定する方法というふうになります。
本来のIRTであれば受験者の能力も難易度と同時に推定しなければならないはずですが、どちらの事例でも能力値をレーティングで置き換え、それでとてもうまく行っています。これはなぜか。
それはIRT仮定（+α）からElo仮定を導けるからです。コンテスタントA, Bが問題Pのみのコンテストで勝敗を決することを考えます。ペナルティのタイブレークはなしで、両方の正解数が同じ時は別の問題を選んで決着がつくまで繰り返すとします*4。このとき、勝率は選んだ問題に関係なくAとBのレーティング差のシグモイド関数になります。これはElo仮定にほかなりません。
IRTはEloの矛盾しない拡張だったので、Eloで決まったレーティングを用いて難易度を推定してもうまく行ったというわけでした。
蛇足: 「レーティングは強さの対数」
物理量でいう次元のようなものが崩壊してます。レートは強さの対数とったものなので、exp(レート) と他の値をかけましょう。
— rng_58 (@rng_58) 2019年9月28日
これは統計的にはどういうことかというと、強さの比較モデルとしてBradley-Terry Modelを採用しているという意味になります。つまり、（人間・問題間/人間・人間間）勝率が exp(レート) の相対的な割合とするとIRTもEloもそこから導かれます。
AtCoder以外の事例
Codeforces はほぼ同様の手法で難易度を推定していると考えられます。
Codeforces: Problem Difficulties - Codeforces
正解確率のモデルがレーティング差のシグモイド関数なので、変なことをしてなければ推定手法もほぼ同じだと思います。
paiza は最近 Glicko ベース*5の手法を導入しました。
プログラミング問題を解けばエンジニアの戦闘力がわかる！？レーティング機能公開 - paiza開発日誌
勝ち負け（ユーザー同士なら順位、ユーザーと問題の間なら解けるかどうか）がレーティングのシグモイドで決まるというのは Glicko でも同じですので、これもだいたい同じですね。paiza の場合はユーザーが好きなときに問題を解けるという性質があるので、対戦ゲームなどで使われるオンラインなレーティング更新法を採用しているようです。エンジニア戦闘力は Bradley-Terry Model での強さそのものです。
未解決問題
具体的な解法がわかってるやつは issue にしてあります。興味があればぜひ！
Issues · kenkoooo/AtCoderProblems · GitHub
この先はかなり謎で、脳内研究ノートたれ流し状態です。謎度が低い順に行きます。
時間の経過によるレーティングの水準変化
Eloレーティングとその派生シリーズの有名な弱点として、過去と現在のレーティングを比較できないというものがあります。これはレーティングがプレイヤー間の相対評価で決まっていて、プレイヤーの実力とその分布は時間の経過とともに変化していると考えるのが自然だからです。
これがチェスのような対戦ゲームの場合は打つ手なしですが、競技プログラミングや項目応答理論が想定する問題・解答者のペアの場合は問題が時間に対して不変ですので、これを基準に使えます。*6 具体的には、基準となる問題に対して複数の時点での結果データがあれば、その時点間で共通の難易度軸が得られるので、これに合うように各時点のレーティングを補正します。
この基準となる問題をどうするか。難易度推定をやり始めた2019年8月頃だと2つくらいアイデアがあって、1つ目は AtCoder Virtual Contest の結果を利用するもの、2つ目はAtCoder公式さんサイドに復習コンテストと称して過去のコンテストをそのまま再放送してもらうものを考えていました……
が、つい最近こんな機能が公式に実装されました。
さすがに目立つのでもう気付いてる方もいますが、バーチャル機能ができました。 #AtCoder pic.twitter.com/rj9XUtm3Gz
— ꑄ꒖ꐇꌅꏂ🐈 (@snuke_) 2019年11月28日
というわけですので、公式バチャのデータが十分集まったら直せるかもしれないから気長に待ってください。もしかしたらこれで仮想レーティングの補正もできるかもしれません。
問題を解くことによるレーティングへの介入効果
今のところ Moderate Recommendations は正解率が50%に近い問題を推薦しています。
50%の確率で解ける問題そのものがほしい場合は別にこれでいいのですが、多くの場合、本当にほしいのは学習効果、もっと直接言えばレーティングのはずです。それなら、ある問題をある人が解いたときのレーティング変化を予測して、それが最大になる問題を推薦すればいいことになります。
正直なところ、正解率50%の問題で精進しても最適な場合に比べて大幅に損しているとは思わないのですが、練習にふさわしい良問がこの研究で明らかになると面白そうです。
競プロ精進データセットで人間の学習を研究
問題演習の学習効果について先行研究がないか適当に調べてたのですが思いの外見当たらず、原因について考えてみたところそもそもデータセットがないのではないかという疑念を抱きました。つまり、
- 定期的に学力試験を繰り返していて
- その結果が公開されていて
- 問題演習の履歴もある
データセットって競技プログラミング以外にあるんですかね、これ実は教育学の研究ネタになったりしませんかね（超適当）？ 先行研究を教えてくれるのも大歓迎なので人間の学習に詳しい方を切実に募集しています。こういうのって心理学の守備範囲？
謝辞
使ってくださる方全員に感謝しています。Twitter でエゴサしまくって感想読みまくってます。フィードバックや怪しい推定値があったときもためらわずに教えて下さい。
kenkoooo さんにも感謝します。彼は作ったモデルを使ってもらう場を提供し、その維持費も払ってくれる聖人です。莫大な金銭を得たら余った1億円ほど寄付します。
