概要
表題の通り、コンテスト中に(このまま椅子を温め続けた時の)最終順位を推定したいです。私はac-predictorってやつを作ってるんですが、それにコンテスト中の最終順位の推定機能を組み込めたら更に便利になるなってのがモチベーションです。
ただ、問題を詰めていくに従ってどん詰まりになってきたので頭の整理のためにでも書いてます。もし何らかの解決策を少しでもご存知であれば、是非教えて頂けると幸いです……。本稿で使用したnotebookはGistに上げておきました。
この記事でレートと言った場合、明示しない場合は内部レート(APerf(average perf), パフォーマンスの単純な加重平均)のことを指すことにします。
要件
リアルタイムに推定を出したい。できるならばすべての処理をクライアント(=JS)側に任せたいが、流石にブラウザ上でやるには厳しい計算が出てきた場合はサーバサイドでの計算もやむを得ないかも。(その場合はバッチ処理のような形を取る)
現段階での考えている手法
とりあえず、(このまま椅子を温め続けた時の)最終順位を予測するためには何が必要かを考える。最終順位=今の順位+自分を抜いた人の順位であるため、全ての人について自分を抜く確率がどれくらいあるのかを計算したい気持ちになる。
そのためには、それぞれの人が問題を一定の時間以内に解く確率を計算したくなる。
AtCoder の問題に取り掛かってから AC するまでにかかる時間の対数の平均値は、レーティングの1次式で表現できると考えられます。
とあるため、これは問題のDifficultyと分散を求めると良さそうである。
よって、各問題のDifficultyと分散を求めることとする。
ここで、Diffは「コンテスト中に50%の人が解けるレート」として計算されているため、「コンテスト終了時に50%の人が解けているレート帯」をそのままDiffとして考えることにする。
コンテスト本番の (ユーザー, 問題) の対を1つのデータ点として内部レーティングを説明変数、その問題に正解したかを被説明変数とするロジスティック回帰によって正解予測モデルを作っています。このモデルで正解率が50%になる内部レーティングを difficulty としています。
ここまでをまとめると、
各問題について:
- コンテスト中の順位表よりDifficulty(=終了時に半分の人が解けているレート帯)を推定
- そのDifficultyより各人が自分を抜く確率を推定
- そこから最終順位を予測
というプロセスで推定を行うということになる。
Difficultyを推定する
追記(2020/7/31)
本項でいくつか記事を参考にさせていただき、またAtCoder ProblemsのDiff推定部分の担当もしていらっしゃるid:pepsin-amylaseさんより「最近それをやった論文がある」と教えていただいたため、それを読んだ。それを用いた場合C問題程度まではきれいな推定ができるが、それ以降ではまだきれいな推定ができなかった。
Diff推定実装したけどDEFのブレがやっべえ(Cの精度がかなり良いので全部うまく行ったらかなり組み込めそうという気持ち) pic.twitter.com/cjYjayzb1m
— keymoon (@keymoon_) 2020年7月28日
その後も手法を改善する努力などは行っているため、何か進展があればここに追記する。
(追記:記事を書きました。未だに上手くはいっていません…)
(追記終わり)
Difficultyを推定するに当たって、終了時に半分の人が解けているレート帯を求めることをしたい。
まず、観察として「全ての問題について、各レート帯の何割の人がどの程度の時間で解けているか」をプロットすることとした。
その結果が以下である。
縦軸のaperfは内部レート、横軸は時間の対数である。
赤の点はがそのレート帯の人の50パーセンタイルが解けたときの時間、黄色が40/60,青が30/70… といったことを示している。
これを見てもわかるように、それぞれのパーセンタイル毎の値は微妙な曲線になっている。
また、各レート帯毎の解ける時間については対数正規分布になっているように感じる。
これらの観測を基に、コンテスト中の順位表から終了時に5割の人が解けているレート帯(すなわち終了時刻に赤点線が当たる場所)を求めたいという気持ちになる。
開始10分時点での情報をプロットしたもの
そのためには、「各レート帯での解けるまでの時間の中央値を推定」→「その中央値を基にDiffを推定」というステップを踏むべきであると考えた。
課題
ここまで考えたのは良いものの、その推定をどのように行ってよいかが分かっていない。
ここから、行ったことと考察を書く。
中央値を推定するフェーズ
対数正規分布になりそうだという観測を基に、その時点での結果について正規分布のフィッティングを行うこととした。
どうにも打ち切りモデルというものによる推定になりそうだが、このような高度なモデルを使用することなくcurbe_fittingを行ってみることとした。
その結果、20分程度まではある程度まともなデータが得られたが、それ以降では頓珍漢な結果が出てしまう結果となった。
どこかで分散を求めてしまって、それを基に全てを推定とかのほうが楽なのかもしれない……?
Diffを推定するフェーズ
一度対数を適用してもまだ対数っぽい見た目をしていたのでもう一度適用すると良いかもしれないと思い、適用してみる。
結果としては、まだ対数っぽさが残っている気がする。
最初の方に解けた上位陣を無視して、最後の方の傾きだけを基に推定すれば良いかとも思ったが、できるならば最初の方から推定できていてほしさがあるため、上位陣込みのデータを基に推定可能な汎用的なモデルを構築したい。
あと、中央値となる点の「確実性」の重みは、推定がどの程度の点の量で行われたかによって変化すると考えた。そのため、それを加味した上でフィッティングは行うべきな気がする。
終わりに
数学的な議論を踏まずに観察でモデルを構築しようとしているのが良くないのかもしれないですね……。
これらの推定やモデル案について、少しの提案や意見でもあればお待ちしています。宜しくおねがいします。
