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

シリーズ一覧

kujira16.hateblo.jp

kujira16.hateblo.jp

はじめに

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
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で有志によって人手で値が付与されています。

続き

kujira16.hateblo.jp

参考文献

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

*1:私のことです

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

Indeed Machine Learning CodeSprint 2017

www.hackerrank.com

問題

求人の文面が与えられるので,以下のタグを付けるべきかどうかそれぞれのタグについて二値分類してください。

  • アルバイト
  • フルタイム
  • 時給制
  • 月給制
  • 短大卒対象
  • 大卒対象
  • 修士または博士対象
  • 免許が必要
  • 1年の経験が必要
  • 2〜4年の経験が必要
  • 5年以上の経験が必要
  • 管理職

評価

それぞれのタグの真陽性,真陰性,偽陽性偽陰性の数を合計してSTP, STN, SFP, SFNとします。

\displaystyle
\begin{align}
\mathit{STP}&=\sum_{i=1}^{12}\mathit{TP}_i \\
\mathit{STN}&=\sum_{i=1}^{12}\mathit{TN}_i \\
\mathit{SFP}&=\sum_{i=1}^{12}\mathit{FP}_i \\
\mathit{SFN}&=\sum_{i=1}^{12}\mathit{FN}_i \\
\end{align}

STP, STN, SFP, SFNを使ってF値を計算したものが評価指標となります。

\displaystyle
\begin{align}
P&=\frac{\mathit{STP}}{\mathit{STP}+\mathit{SFP}} \\
R&=\frac{\mathit{STP}}{\mathit{STP}+\mathit{SFN}}
\end{align}
\displaystyle
F_1=\frac{2PR}{P+R}

方針

コンテスト終了まで残り12時間しかないタイミングで始めたので,テキスト分類でベースライン的に使われている手法だけ試しました。

それぞれのタグについて二値分類問題を解いてもいいわけですが,アルバイトとフルタイムや時給制と月給制は排他的なはずなので,「アルバイト or フルタイム or それ以外」や「時給制 or 月給制 or それ以外」で多値分類問題を解くというアプローチも考えられます。ただし今回は評価指標がかなり独特で,それぞれのタグについて二値分類問題として解いたほうが最終的な評価値は高くなりそうな気がしたのでそのアプローチを試しました。

前処理

Unicodeにはスペースっぽい文字,ハイフンっぽい文字,整形のための制御コードなどが多数収録されています。テキスト分類の問題ではそのあたりの文字は消したり正規化したりしたほうが都合が良いので,最初にどんな文字種が含まれているか調べました。ASCIIコード範囲内で表示可能文字以外の文字を列挙するには以下のような処理を実行します。

chrs = set()
for desc in descs:
    for c in desc:
        if ord(c) <= 0x19 or ord(c) >= 0x7f:
            chrs.add(c)
chrs = sorted(list(chrs))
for c in chrs:
    print(repr(c), hex(ord(c)))

実行してみたところ,極少数ですが日本語,ポルトガル語スペイン語などで書かれた求人の文面もあることが分かりました。あまりリソースを避けそうにないので英語のみに対象を絞ろうと思い,漢字やひらがな,カタカナは消すことにしました。

あとはU+2010のハイフンは半角ハイフンに置換したり,書字方向指定コードやゼロ幅スペースなど(具体的には0xAD, U+200B, U+202A, U+202C, U+FEFF, U+FFFC, U+FFFD)を消しました。

あとはユニコード範囲外にある無効なコードポイントを消したりしました。これは以下のように書いたのですが,もっと良い方法があるはずです。

t = ''
for c in s:
    try:
        unicodedata.name(c)
        t += c
    except ValueError:
        pass

単語分割・レンマ化

英語の単語分割はスペースで区切るだけだと思うかもしれませんが,実際には例外処理がいくつかあるので専用のトークナイザを使ったほうが良いです。専用のツールとしては Stanford Tokenizer などがあります。

テキスト分類でやったほうが良い処理として,語のステミング(語幹以外の部分の除去)やレンマ化(見出し語化)などがあります。ステミングのアルゴリズムはPorter stemmerとSnowball stemmerというものが有名で,どちらもNLTKで使えます。レンマ化の処理はNLTKやStanford POS Taggerに収録されています。本来であればどの処理が最も適切であるか全部試すべきなのですが,あまり時間がなかったのでStanford POS Taggerのレンマ化のみ試しました。

特徴ベクトルの作成

TFとBM25だけ試しました。作り方は以下のページを見てください。

kujira16.hateblo.jp

kujira16.hateblo.jp

分類

時間がなかったので最初にNaive BayesとPassive Aggressiveを試しましたが全く性能が出ませんでした。

データを眺めてみたのですが,例えばpart-timeというタグを付けるべきかどうかは “part” か “time” か “part-time” が入っているかどうかだけで決まっているなど,全体の極性でタグが決まるというよりは極少数の単語の有無のみでタグが決まっているようでした。そのため,意外と決定木が強いのではないかと思い試してみるとなかなかよい性能が出ました。max_depth をグリッドサーチしていると締め切りが来てしまったので,これで提出しました。

結果

順位表は以下のURLにあります。

https://www.hackerrank.com/contests/indeed-ml-codesprint-2017/challenges/tagging-raw-job-descriptions/leaderboard

テストデータに対する解答を送信すると,テストデータ全体の2922件のうち約半数の1446件のデータについての解答のみが評価され,その結果が仮スコアとして順位表に掲載されます。最終的な順位はコンテスト終了後にテストデータ全体に対する解答が評価されます。これはデータ分析コンペにおいて参加者にフィードバックを与えつつもモデルの過学習を防ぐための工夫です。

まだ最終テストが行われていないので最終的な順位分かりませんが,仮スコアは628.80で52位でした。オーバーフィッティングする要素をそんなに入れていないので最終テストが行われてもそんなに悪くならないと嬉しいですね…

ソースコードは以下のリポジトリに置いています。

github.com

その後

一般にこの手のコンペでは決定木よりもRandom Forestのほうが性能が出ることが多いようなのですが,後日試してみるとやっぱりそうなりました。今回のタスクでは特定の単語の有無のみで結果がほとんど決まってしまうので,特徴量のサンプリングは行わずに学習データのサンプリングのみを行うように設定すると良い性能が得られました。