読者です 読者をやめる 読者になる 読者になる

StanでAizu Online Judgeの難易度・習熟度を推定したい(1:モデル式)

はじめに

Aizu Online Judge (AOJ) という競技プログラミングの練習サイトがあります。

AIZU ONLINE JUDGE: Programming Challenge

解けるか解けないかくらいのちょうど良い難易度の問題に取り組むことが一番成長につながるはずなので,それぞれ問題の難易度や,それぞれのユーザの習熟度を定量的に評価して推薦システムを作りたい気分になります。AOJの 各ユーザのページ にはこれまでの正答数やレーティングが表示されていますが,この2つの値はユーザの習熟度とは必ずしも一致しません。簡単な問題ばかり解いていれば正答数は伸ばせますし*1レーティング*2は回答者が少なくて簡単な問題を中心に解いていればかなり大きく伸びるためです。そのため,問題の難易度やそれぞれのユーザの習熟度を計算する気の利いた方法が必要です。

関連研究

sucrose.hatenablog.com

topcoder.g.hatena.ne.jp

得られる情報

AOJのAPIを利用することで,誰がどの問題に正答したかという情報を得ることができます。

問題の難易度の情報はAOJでは提供されていませんが,AOJ-ICPC というサイトで有志によって一部の問題に対して人手で難易度が付与されています。

難しいところ

正答していない問題は,取り組んだけれども実力不足で解けなかったのか,そもそも取り組んでいなかったのかを区別することができません。そのため,あるユーザが問題に取り組むかどうかを表す確率をモデルに組み込むことにしました。

モデル式

考えたモデルは以下のとおりです。

 \displaystyle
q[i] \sim \mathrm{Beta}(a_0,b_0)
 \displaystyle
\mathit{try}[i,j] \sim \mathrm{Bernoulli}(q[i])
 \displaystyle
\mathit{pf}[i,j] \sim \mathrm{Normal}(\mu_\mathit{pf}[i], \sigma_\mathit{pf})
 \displaystyle
\begin{cases}\mathit{try}[i,j]=1 \text{ and } \mathit{pf}[i,j] \geq D[j] & \text{ if } Y[i,j]=1 \\ \mathit{try}[i,j]=0 \text{ or } \mathit{pf}[i,j] < D[j] & \text{otherwise} \end{cases}

q[i] は人 i が個々の問題の取り組む確率です。事前分布としてベータ分布 \mathrm{Beta}(a_0,b_0) を設定します。a_0, b_0 はデータから推定します。

\mathit{try}[i,j] は人 i が問題 j に取り組むときに1,取り組まないときに0をとります。

\mathit{pf}[i,j] は 人 i が問題 j に取り組むときに発揮されるパフォーマンスです。人 i が持っている平均的なパフォーマンス \mu_\mathit{pf}[i]標準偏差 \sigma_\mathit{pf} のばらつきが乗ったものとしました。パフォーマンスのばらつき \sigma_\mathit{pf} には個人差はないものとしています。

Y[i,j] は 人 i が問題 j に正答したかどうかを表す観測可能な変数です。問題に取り組む気分になり,かつ問題に取り組んだときにユーザが発揮したパフォーマンス \mathit{pf}[i,j] が 問題の難易度 D[j] を上回った場合に1になります。問題に取り組む気分にならなかったり,ユーザが発揮したパフォーマンスが問題の難易度を下回ったりした場合には0になります。問題の難易度 D[j] は一部の問題についてはAOJ-ICPCで有志によって人手で値が付与されています。

続き

kujira16.hateblo.jp

参考文献

Stanを使った統計モデリングチュートリアルです。大学1年生の教科書レベルの確率統計が理解できれば1人で読み進められます。

StanとRでベイズ統計モデリング (Wonderful R)

StanとRでベイズ統計モデリング (Wonderful R)

*1:私のことです

*2:計算式はこちら http://judge.u-aizu.ac.jp/onlinejudge/rating_note.jsp