StanでAizu Online Judgeの難易度・習熟度を推定したい（１：モデル式）

シリーズ一覧

kujira16.hateblo.jp

はじめに

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

AIZU ONLINE JUDGE: Programming Challenge

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

得られる情報

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 Y[i,j]=\begin{cases}1 & \text{if $\mathit{try}[i,j]=1$ and $\mathit{pf}[i,j] \geq D[j]$} \\ 0 & \text{if $\mathit{try}[i,j]=0$ or $\mathit{pf}[i,j] < D[j]$}\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で有志によって人手で値が付与されています。