機械学習で音ゲープレーヤーの地力と得手不得手を解析する

はじめに


この記事は映画サイトの推薦システム有名なMatrix Factorizationという手法を,音ゲーのプレーデータに応用してみよう.という趣旨の記事になります.有名な論文
学習のため,機械学習フレームワークとかを使うんじゃなくて自力でやろうねというところに重きをおいてやっていきます.

次のようなことを目的にしています.
  • プレーヤーと曲が持つ潜在的な「苦手パラメータ」を発見する.
  • 苦手・得意を考慮したその人の地力を決定する.(「○○が苦手」とのたまうプレーヤーが本当に苦手なのかただ地力がないだけなのかがわかる.)
  • プレーヤーにスコアが伸びそうな曲やランプがつきそうな曲をおすすめする.
プレーヤーや曲の代表ベクトルから,「このプレーヤーは(高速曲/トリル/縦連譜面)が苦手」ということだったり,「この曲は縦連属性が強いからタグ付けできるな」等の情報が獲得できれば面白いなと思ってます.

またこの記事では,BMSクライアントLR2のランキングサイトであるLR2IRに登録されているプレーヤーと楽曲のうち,
  • 発狂BMSのスコア登録数が125曲以上のプレーヤー
  • 発狂難易度表またはOverjoy難易度表に登録されている楽曲

に対して学習を行います.


準備:Matrix Factorizationによる学習


Matrix Factorizaionは行列分解手法の一つです.説明はこちらにざっくり説明されていますので.

最初は音ゲーマー$i$が曲$j$をプレーした時のスコア$S_{ij}$が次の式で表されると過程して実装していきます.
$$S_{ij} = u_i + m_i + P_iQ_j$$
ここで.
\begin{eqnarray*}
u&:&音ゲーマーの地力\\
m&:&曲の難易度(高いほうが簡単)\\
P&:&音ゲーマーの苦手パラメータ(P\in R^{|u|\times k})\\
Q&:&曲の苦手パラメータ(Q\in R^{k\times |m|})
\end{eqnarray*}
この$S_{ij}$と実際の値$R_{ij}$との誤差を小さくするように機械学習していきます.
ここで曲の難易度とは実際に決められている難易度ではなく,学習によって求める値になります.
このような変数を学習によって求めることで,音ゲーマーの地力値や,その人がどれだけ個人差に弱いかを知ることができるわけです.

$k$は苦手パラメータの数で,ハイパーパラメータの一つになります.
苦手パラメータがBPM,縦連の量,ソフラン具合などを露骨に表すような値になると第一の目的は成功でいいかなと思います.

これらの$u,m,P,Q$を,$S_{ij}$と実際の値$R_{ij}$との誤差$e_{ij}=R_{ij}-S_{ij}$をもとに勾配降下法(Wikipedia)で学習していきます.

学習の目的関数は次のようになります
$$\min \frac{1}{2}\left( \sum_{i,j(S_{ij}\neq 0)}e_{ij}^2 + \lambda (||p_i||^2+||p_j||^2) \right)$$
ここで$\lambda$は各変数が大きくなるのをどの程度許すかというパラメータになります.
この値が大きすぎるとロクに学習できないことになりますし,小さすぎると過学習を起こして未プレイの場所に怪しいスコアが入ることになります.
$u,m$に対して正規化を行っていないのはそこに地力が入ってほしいからです.

上記の目的関数を各変数で微分し,勾配を求めると更新式は次のようになります.
\begin{eqnarray*}
u_i&\leftarrow &u_i + \alpha (e_{ij})\\
m_j&\leftarrow &m_j + \alpha (e_{ij})\\
p_i&\leftarrow &p_i + \alpha (e_{ij}\cdot q_j-\lambda p_i)\\
q_j&\leftarrow &q_j + \alpha (e_{ij}\cdot p_i-\lambda q_j)
\end{eqnarray*}
この更新を繰り返していくとこで学習が進みます.


機械学習モデルの実装


せっかくなのでやってみようということで,ライブラリなどを使わずにとりあえず動くものを素Pythonで実装します.本当は機械学習のフレームワーク使えば一瞬でできるらしい.

最急降下法

こちらは全データに対して勾配を計算した後にまとめて全てのパラメータを変更するという方針になります.


テストのために作ったデータは列が曲で行がプレーヤーに対応するスコアレートデータのつもりです.
上のプレーヤーの方がうまいプレーヤーで右の曲の方が難しい曲のつもりです.
スコアレート0は未プレイになります.

上記のコードでの学習結果がこちら(丸めています)


理論値超えてるところが一箇所ありますが,未プレイのところにもそれっぽい値が入っています.よしよし.
プレーヤーの地力も一応序列はしっかり上の人が高い値になっています.

学習の様子です.とりあえず局所解に落ち着いています.


RMSEっていうのはRooted Mean Square Errorです
ここからいろいろ試します.

確率的勾配降下法

先程のコードが全部の勾配を求めてから一気に変数を更新していましたが,それでは変数を1つ変更するのに大きい計算をしないといけません.慎重すぎるというわけですね.
確率的勾配降下法では$e_{ij}$をひとつ求めたら早速パラメータを更新してしまいます.
1回の更新に大きく変数を変化させることもあり,計算量も少ないため早い収束が期待できます.
収束するギリギリまで$\alpha$を大きくした結果がこちら


やっぱり早かった.かなり揺れているのがわかります.

モーメンタム(慣性)の導入

学習が早くなるように$t-1$回目はどれぐらい動かしたかを記憶して,$t-1$回目に大きく動かした変数を$t$回目にブーストしてより大きく動かし,早く収束させるという方法です.
変数の更新式は次のようになります.
\begin{eqnarray*}
u_i^t&\leftarrow &u_i^t + \alpha (e_{ij}) +\beta \Delta u_i^{t-1}\\
m_j^t&\leftarrow &m_j^t + \alpha (e_{ij})+\beta \Delta m_j^{t-1}\\
p_i^t&\leftarrow &p_i^t + \alpha (e_{ij}\cdot q_j^t-\lambda p_i^t)+\beta \Delta p_i^{t-1}\\
q_j^t&\leftarrow &q_j^t + \alpha (e_{ij}\cdot p_i^t-\lambda q_j^t)+\beta \Delta q_j^{t-1}
\end{eqnarray*}
$\beta=0.9$にしてギリギリまで$\alpha$を大きくした結果がこちら


はやい.けどかなり振れが激しいです.

指数的に学習率が減衰するようにしてみた

毎エポックごとに$\alpha$を$1.0001$乗する…という感じで減衰させていきます.


ブレなくなった.


目的関数に和の正則化を追加


これはどういうことかというと,このままでは$p_iやq_j$の中に,全部が正だったり全部が負だったりするものが出てきてしまいます.
これではプレーヤーの地力や曲の難しさが正確に出せません.ということで目的関数に$p_iやq_j$の和がゼロになるように正則化項を追加します.

とはいえそんなもの微分できないので適当に$pとq$の制約式を次のようにしてみます.
\begin{eqnarray*}
p_i^t&\leftarrow &p_i^t + \alpha (e_{ij}\cdot q_j^t-\lambda p_i^t)+\beta \Delta p_i^{t-1} -\gamma \sum_i p_i^t \\
q_j^t&\leftarrow &q_j^t + \alpha (e_{ij}\cdot p_i^t-\lambda q_j^t)+\beta \Delta q_j^{t-1}-\gamma \sum_j q_j^t
\end{eqnarray*}
適当に$\gamma$に$0.01$ぐらいの値を入れて回してみたら無事$pとq$の和が0になりました.


サックリ解決しました.

ということで改良したこのモデルをLR2IRデータに適用してみましょう.





LR2IRデータへの適用



これで得られた苦手ベクトルで色々できる.

苦手ベクトルの類似度が高いプレーヤー同士は同じ曲が苦手なはずなので談義が捗るはずで,Stairwayにある「似ているプレーヤー」のより似ているやつを推薦できるはず.
また苦手ベクトルとの内積を取ることで苦手な曲・得意な曲が発見できるようになる.
苦手意識があっても実は相性が良かったりという曲が見つかるかもしれない.

今回はまた今回はスコアしか見ていませんが,これをクリアランプでやれば苦手や得意が考慮されたリコメンドを行うことができるはず.そうなると捗る.

プレーヤーの地力ベクトル$u$が大体正規分布に従う感じだったので全プレーヤーの偏差値を出してみました.
ちなみにぼく(発狂六段)は$48.3$だった



段位が高い人のほうがうまいですね(それはそう)

取れたデータの一部がこちらになります.







0 件のコメント: