数式にもちょっと慣れよう
前回のコードを作り始めるところまで戻り、概念や用語を学んでいきます。
ゲーム部分を書き換えて良かったの？
前回は人間用のゲームを若干書き換えて機械学習用のゲームとしました。
ゲーム部分を書き換えてしまったら、人間用のゲームを学習したことにならないんじゃないか？
もしくは、どれくらいまでならコードを変更してよいのか？
という素朴な疑問が生じるかもしれません。
この時に満たしておくべきなのが、マルコフ決定過程（MDP）的に同等という条件です。
$$P(X_{t+1}=x_{t+1}\mid X_t=x_t, X_{t-1}=x_{t-1}, \dots, X_0=x_0)=P(X_{t+1}=x_{t+1}\mid X_t=x_t)$$
式にするとこのようになりますが、現時点では記号の意味すらわからない...という状態でも大丈夫です。これをわかるように説明していくのが今回の記事になります。
（逆にわかる人は今回の記事は飛ばしてOKです）
そもそもマルコフ〜とは？
マルコフ連鎖とかマルコフ性など、マルコフ〜という用語を機械学習ではよく見かけます。
考えたのはロシアの数学者アンドレイ・マルコフさんです。
何かがおこる確率について、
- 将来がどうなるかは 「現在の状態」と「行動」 で決まる
- 過去どうだったかは関係ないとする
と思いっきり割り切る考え方です。
（念の為ですが「現在の状態」に未来予測に必要な情報が十分に入っているという条件は前提とします。）
マルコフは詩人プーシキンの文学作品を使い、
母音の後に母音が来る確率
子音の後に母音が来る確率
などを分析したことでも有名です。
マルコフはこの研究から、過去の履歴を加味した場合と、直前しか見なかった場合で、次にくるものの確率は統計的には同じである、という理論を実証しました。
P( 次 ∣ 直前, さらに過去 ) = P( 次 ∣ 直前 )
この式は、確率Pが、「|」の右側に書かれた条件の時に「|」の左側になる確率、ということを示したものです。つまり、過去の条件は次の確率には関係ないということです。この条件に合致する場合をマルコフ性を満たすと言います。
これを数学的に書くと下記のようになります。
確率過程 ${X_t}$ が マルコフ性 を満たすとは、任意の $t$ と任意の状態列 $x_0,\dots,x_{t+1}$ に対して
$$P(X_{t+1}=x_{t+1}\mid X_t=x_t, X_{t-1}=x_{t-1}, \dots, X_0=x_0)=P(X_{t+1}=x_{t+1}\mid X_t=x_t)$$
が成り立つことをいう。
冒頭に出てきた式がもう読めるようになりました。
直前の情報だけの時と、情報に履歴を含めた時と、予想結果は一緒だぜ！...ということにしようぜ！ ということを表す式です。
マルコフ決定過程（MDP）
さて、「マルコフ性」はなんとなくわかってきました。
では マルコフ決定過程（Markov Decision Process, MDP） とは何でしょうか？
「マルコフ性を満たす世界で、行動を選びながら報酬を最大化する枠組み」
これがMDPです。
もうすこし詳しく見ていきます。
MDPを構成する要素
MDPは次の5つ（実質4つ＋割引率）で定義されます。
( $S$, $A$, $P$, $R$, $γ$ )
それぞれ意味があります。
-
状態空間 $S$
ゲームの「今の状況」です。
ラケットの位置、ボールの位置、得点など、
未来を決めるのに必要な情報がすべて含まれている状態の集合です。
「空間」という言葉が聞きなれないという方がいるかもしれませんが、下図のように各種パラメータを軸とした多次元空間をイメージすればしっくり来るのではないでしょうか。
-
行動空間 $A$
プレイヤー（エージェント）が取れる行動の集合です。
左右に動く、何もしない、など。 -
状態遷移確率 $𝑃$ ( $𝑠$′ ∣ $𝑠$ , $𝑎$ )
状態 $s$ で行動 $a$ を取ったとき、次の状態 $s$' に遷移する確率です。
ここが「マルコフ性」に対応しています。
次の状態は「今の状態」と「今の行動」だけで決まり、過去の履歴は見ないということです。 -
報酬関数 $𝑅$ ( $𝑠$ , $𝑎$ )
状態 $s$ で行動 $a$ を取ったときに得られる報酬です。
ボールを打ち返す → +10
ボールを落とす → -100
何もしない → 0
などです。 -
割引率 $\gamma$
将来の報酬をどれくらい重視するかを決める係数です。
$\gamma = 0$ → 今だけ見る
$\gamma = 1$ → 将来も同じ重み
通常は 0.99 などを使うそうです。
1以上に設定すると収束しない可能性があるためです。これは別の機会に説明します。
(あとでやる理由のメモ：無限和の発散・ベルマン方程式の収束・有効ホライズン)
問題のないゲームの書き換え方
ここが今回の本題です。
ゲームを機械学習用に書き換えたとき、
描画を消す、入力を自動化する、内部状態を取得できるようにする
といった変更を加えました。
この時、
状態の定義、行動の意味、状態遷移の確率、報酬の与え方、が変わらないのであれば、
マルコフ決定過程（MDP）的に同等 という条件を満たすということになります。
逆に、状態に必要な情報が欠けるとマルコフ性が壊れて、同じ問題ではなくなります。
つまり、コードの見た目が違っても、
( $S$, $A$, $P$, $R$, $γ$ )
が完全に同じであれば、同じ問題を解いていることになるわけです。
今日はここまで！
次回
実際のコードを読み進め、ニューラルの概念に触れていきます。
前回記事