はじめに

以前に、AtCoderの問題難易度の推定を項目反応理論を用いて行いました。これは統計モデリングを使った方法だったのですが、同様のことを機械学習でできないこともないな、と思い今回は機械学習を用いて問題難易度の推定を行うことにしました。

手順としては、参加者のレーティングやコンテストの正答率などの特徴量を入力変数として各参加者の正解・不正解を判定する２値判別モデルを作成し、その作成したモデルを使って参加者のレートを変化させた場合の正答率の変化を確認するという方法をとります。

やっていることは少し違いますが、下記のような学習済みモデルを使って入力するパラメータの最適点を探すという逆問題の考え方を参考にしています。

予測モデルを使ったシミュレーションと最適解探索

実験

まずは正解・不正解の二値判別をするモデルを作成する必要があります。使用するデータは前回と同様にAtcoderのサイトから取得したAGC29、日経コン、みんなのプロコンの３つのコンテストの順位表のデータです。

モデルを作るためにはコンテストの特徴量を作成する必要があります。特徴量として問題毎の正答率と正答者の平均レートを作成し、学習可能なようデータ整形を行いました。前処理後のデータは以下のようにレーティング、目的変数となる参加者毎の正答・不正答、問題名、正答者の平均レート、問題に対する正答率のカラムをもつものになります。 f:id:rmizutaa:20190314084927p:plain

このデータをlightgbmで学習させモデルを作成します。

import lightgbm as lgb
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
params={
    'random_state' : 1,
    'objective': 'binary',
    'metric': 'binary_error',
    }
dtrain = lgb.Dataset(X_train, label=y_train)
dvalid = lgb.Dataset(X_test, label=y_test)
bst = lgb.train(params, dtrain, num_boost_round=1000,valid_sets=[dtrain,dvalid],early_stopping_rounds=50,verbose_eval=10)

f:id:rmizutaa:20190314084946p:plain

正答率は約93%。難しい判別ではないのでこれくらいは出ますね。

今回欲しいのは参加者のレーティングによって各問題に対して正答率がどのように変化するかなので、先ほど作成したモデルを利用し、入力レートの部分のみを変化させた場合の正答率を算出します。

probsets=df[["probname","mean_rating","mean_solve_rate"]].drop_duplicates()
rating=[i*10 for i in range(300)]
result=pd.DataFrame()
for index, row in probsets.iterrows():
    tmp=pd.DataFrame()
    tmp["rating"]=rating
    tmp["mean_rating"]=row["mean_rating"]
    tmp["mean_solve_rate"]=row["mean_solve_rate"]
    tmp["pred"]=bst.predict(tmp)
    tmp["name"]=row["probname"]
    result=pd.concat([result,tmp],axis=0)

こんな感じで各問題に対してレーティング10毎に予測値が入っているデータが作成できました。

f:id:rmizutaa:20190314084909p:plain

これで欲しいデータが揃いましたので、可視化していきます。左が今回の結果で、右が前回統計モデリングで出した結果になります。横軸が参加者のレーティング（コンテスト参加時）で、縦軸が正解率です。右の図では横軸のレーティングは1/1000になっています。

AGC29

全国統一プログラミング王決定戦予選

みんなのプロコン2019

横軸のレンジが異なるので少し見辛いですが、全体的な波形は機械学習を使った場合でも統計モデリングを使った場合でもほぼ同じになりました。

機械学習(木系のアルゴリズム)を使った場合の特徴としては、波形がギザギザになり、必ずしもレーティングが上がったからといって問題の正答率が上がるようにはならないことと、サンプルサイズが少ない部分（今回だと500以下と2500以上）は1サンプルあたりの影響力が大きくなるために値がブレやすいという点があると思います。

これだけみると統計モデリングの方がこういった場合には向いているのでは？と思うかもしれませんが、統計モデリングだとロジスティック関数の形に従うという前提を置いてしまっているので、例えば左右対称でなかったり、一定のレートの人はその周辺のレートの人よりも問題が解ける性質があるという特異点があった場合には対応することができなくなります。

機械学習を用いる場合はそのような前提を置いておらず、現在手元で取れている点のみを用いて推定しているので、今回のようにサンプルサイズがあまり多くない場合はあやしい形になることが多いですが、データがあればあるほど母集団の性質に近づいていくので、もし１億サンプルくらいデータがあるのであればほぼ真のモデルが作れるのではないかと思います。

まとめ

AtCoderの問題難易度推定を機械学習で行いました。機械学習でも問題難易度の推定を行うことができましたが、用いたサンプルが３コンテスト分とあまり多くないことから予測が少し歪な形になる部分がありました。サンプルサイズが増えればこの欠点は軽減されることが予測されるため、統計モデリングと機械学習は一定のサンプルサイズを基準に使い分けするのが良いのかな…という気持ちになっています。

今回使用したコードは以下になります。

github.com

rmizutaの日記

AtCoderの問題難易度を推定する（機械学習編）

はじめに

実験

まとめ