読者です 読者をやめる 読者になる 読者になる

いものやま。

雑多な知識の寄せ集め

強化学習について学んでみた。(その28)

技術 AI 強化学習

前回はSarsa( \lambda)法について説明した。

今日からは関数近似について説明していく。

これまでの方法の限界と関数近似

これまでの方法では、状態価値ベクトル \boldsymbol{V} \in \mathbb{R}^{\mathcal{S}}、行動価値ベクトル \boldsymbol{Q} \in \mathbb{R}^{\mathcal{S} \times \mathcal{A}(s)}の各要素を、メモリ上に(配列などで)そのまま保存し、参照、更新してきた。
このような方法をテーブル型と呼んだりする。

しかし、この方法では、状態や状態行動対の数が膨大になると、メモリ上に価値を保持するのが困難になる。
なので、現実的な大きなタスクに対しては、応用できない。
例えば、将棋や囲碁を考えてみると、すべての盤面に対する価値を保持しないといけないことになり、そんなのは無理だと分かる。

そこで、状態価値ベクトルや行動価値ベクトルを、一般化手法を用いて近似的に求める方法を考える。
このとき、一般化手法のことを関数近似と呼ぶ。

準備

さて、さっそく関数近似のことを、とも思うのだけど、その前にちょっと準備。
というのも、本だと記述が悪いこともあり、この章(第8章「一般化と関数近似」)はかなり分かりにくくなっているから。

まず、強化学習のことはちょっと忘れて、単純な一変数の一次関数による近似を考えてみる。

例えば、入力 x \in \mathbb{R}に対して、次のような出力 y \in \mathbb{R}が観測されたとする。

 x  y
1 2
3 4.5
4 5
6 6.5

この値のペアをそのままメモリに保存するのが、テーブル型の方法。
けど、当然 xの値はいろんな値をとるので、これをそのまま保存していくのだと限界が出てくる。
そこで、関数を使って近似を行う。

ここでは一次関数を使って近似を行うことを考えてみる。
すなわち、入力 xに対する出力 yを、一次関数

 y = f(x) = a x + b

で、近似的に表現することを考えてみる。
ここで、 a bは、この一次関数の具体的な形を決定するためのパラメータで、最初の段階では未知になっている。
このようなパラメータを表すときに、とくに

 y = f(x; a, b) = a x + b

のように、セミコロン(;)の後ろにパラメータを置いたりする。

なお、この a bに具体的な値が入ると、例えば

 \begin{align}
f(x; 2, -3) &= 2 x - 3 \\
f(x; -1, 4) &= - x + 4
\end{align}

のように、具体的な関数の形が定まることになる。

ところで、この a bの値は、どのような値であるべきか。

それは当然、観測された (x, y)の組との誤差が出来るだけ小さくなるような a bが望ましい。
そこで、次のような誤差関数 E(a, b)を考えてみる。
(本では平均二乗誤差(MSE)としている)

 {
\begin{align}
E(a, b) &= \sum_i \left( y_i - f(x_i; a, b) \right)^2 \\
&= \sum_i \left( x_i a + b - y_i \right)^2
\end{align}
}

気をつけたいのは、ここで (x_i, y_i)というのは観測された何かしらの値なので、変数ではないということ。
なので、この誤差関数は a bに関する関数となっている。

具体的に先程のテーブルの値を入れてみると、

{
\begin{align}
E(a, b) &= (a + b - 2)^2 \\
& \quad + (3a + b - 4.5)^2 \\
& \quad + (4a + b - 5)^2 \\
& \quad + (6a + b - 6.5)^2 \\
&= 62a^2 + 28ab + 4b^2 - 149a - 36b + 91.5
\end{align}
}

と、 a bに関する関数になることが分かる。

この E(a, b)を最小化したいので、 E(a, b)が最小値をとるならば \frac{\partial E}{\partial a} = 0, \frac{\partial E}{\partial b} = 0であることから、

{
\begin{array}{lll}
\frac{\partial E}{\partial a} &= 124a + 28b - 149 &= 0 \\
\frac{\partial E}{\partial b} &= 28a + 8b - 36 &= 0
\end{array}
}

となり、この連立方程式を解いて、 E(a, b)が最小値をとるならば a = \frac{23}{26} \fallingdotseq 0.88, b = \frac{73}{52} \fallingdotseq 1.40となることが分かる。
(これはあくまで必要条件で、本当は十分性も成り立つことを示さないといけないんだけど、省略。直感的には、 a^2の係数も b^2の係数も正なので、下に凸となっているから、必要性を満たしていれば十分性も満たす)

ところで、上記では連立方程式を直接解いて a bの値を求めたけど、誤差関数 E(a, b)の勾配 \nabla E = (\frac{\partial E}{\partial a}, \frac{\partial E}{\partial b})^{\mathrm{T}}を用いて、反復的に極小値を求める方法も考えられる。

具体的には、

{
\left( \begin{array}{c}
a^{(t+1)} \\
b^{(t+1)}
\end{array} \right)
=
\left( \begin{array}{c}
a^{(t)} \\
b^{(t)}
\end{array} \right)
- \alpha \left( \begin{array}{c}
\frac{\partial E}{\partial a} (a^{(t)}, b^{(t)}) \\
\frac{\partial E}{\partial b} (a^{(t)}, b^{(t)}
\end{array} \right)
}

というふうに、勾配の逆方向に少しだけ進むことで、誤差関数の値を小さくする。
この方法を、最急降下法と呼ぶ。

試しに、 a^{(0)} = 0, b^{(0)} = 0, \alpha = 0.01としてやってみると、

{
\begin{array}{lll}
a^{(1)} &= 0 - 0.01 \times (124 \times 0 + 28 \times 0 - 149) &= 1.49 \\
b^{(1)} &= 0 - 0.01 \times (28 \times 0 + 8 \times 0 - 36) &= 0.36 \\
a^{(2)} &= 1.49 - 0.01 \times (124 \times 1.49 + 28 \times 0.36 - 149) &= 1.03 \\
b^{(2)} &= 0.36 - 0.01 \times (28 \times 1.49 + 8 \times 0.36 - 36) &= 0.27 \\
a^{(3)} &= 1.03 - 0.01 \times (124 \times 1.03 + 28 \times 0.27 - 149) &= 1.17 \\
b^{(3)} &= 0.27 - 0.01 \times (28 \times 1.03 + 8 \times 0.27 - 36) &= 0.32 \\
a^{(4)} &= 1.17 - 0.01 \times (124 \times 1.17 + 28 \times 0.32 - 149) &= 1.12 \\
b^{(4)} &= 0.32 - 0.01 \times (28 \times 1.17 + 8 \times 0.32 - 36) &= 0.33 \\
& \vdots & \\
a^{(299)} &= 0.89 - 0.01 \times (124 \times 0.89 + 28 \times 1.39 -149) &= 0.89 \\
b^{(299)} &= 1.39 - 0.01 \times (28 \times 0.89 + 8 \times 1.39 - 36) &= 1.39
\end{array}
}

というふうに、約300回反復すると、 a \fallingdotseq 0.89, b\fallingdotseq 1.39という結果が得られる。


ここまでの内容をまとめると、

  • 観測された値をテーブルですべて保存するのではなく、何かしらの関数を使って近似的に表現することを、関数近似と呼ぶ。
  • 関数が入力とは別にパラメータを持つ場合、そのパラメータはセミコロン(;)の後ろに書かれる。
  • 観測された値とパラメータを持つ関数との誤差は、パラメータに関する誤差関数で表される。
  • 誤差関数を小さくする方法として、誤差関数の勾配の逆方向に少しずつ進むことを繰り返す、最急降下法という方法がある。

これらの知識を使って、明日は関数近似が強化学習とどのように組合されるのかを見ていく。

今日はここまで!

強化学習

強化学習

  • 作者: Richard S.Sutton,Andrew G.Barto,三上貞芳,皆川雅章
  • 出版社/メーカー: 森北出版
  • 発売日: 2000/12/01
  • メディア: 単行本(ソフトカバー)
  • 購入: 5人 クリック: 76回
  • この商品を含むブログ (29件) を見る