深層強化学習によるリバーシAI

はじめに

いわゆるAI（人工知能、artificial intelligence） というものは実はかなり定義があいまいです。比較的しっかりした説明をしそうなWikipediaでさえ、「～ともされる」「～もこう呼ばれることがある」と、なんとも歯切れの悪い説明をしています。要約して説明するなら、「『コンピューターで人間の知能を再現してみよう』という分野（またはそれの研究対象）のこと」といったところでしょうか。『AIがこれからの社会で～』『我々の仕事はAIが～』といった言葉はよく聞きますが、多くの人はぼんやりとしたイメージしか持っていないと思います。注目されていると言われている「AI」とはどういった仕組みで、何ができて、何ができないのでしょうか。そういった疑問から自分の手で実際に簡易的なものを作ってみて理解を深めたいと思い、この記事を書きました。この記事を読んでそういったことが伝われば幸いです。

この記事は自分で理解を深め、知識を確かめるために書いたものでもあるので、何も知らない状態では理解しづらい文、数式が多く含まれると思われます。また、内容に誤りも含まれるかもしれませんので、ご了承ください。

強化学習とは

概要

強化学習（reinforcement learning） はAIが学習をして知識を獲得する機械学習（machine learning） の手法の1つです。強化学習の特徴はその学習方法にあります。別の機械学習の手法であり、画像認識などで用いられる教師あり学習（supervised learning） と比べてみましょう。教師あり学習では、前もって用意された問題（入力）とそれに対する解答（出力）をセットにした教師データを使って学習を進めます。人間が何かを学ぶ時のように、自分の出した答えと解答を見比べて、誤差を修正して学習するわけです。しかし実際の場合には、学習すべき問題が多すぎる、もとになるデータベースがない、そもそもこれといった圧倒的な正解がない、といった理由で十分に教師データを用意できない場合があります。このような場合に対応しやすいのが先ほどの強化学習という手法です。強化学習では教師データをまったく必要としません。代わりに学習をする対象である環境（environment） に対してランダムな行動を繰り返すなどして試行錯誤を重ねます。すると環境から良い行動には報酬（reward） が、悪い行動にはマイナスの報酬である罰（punishment） が与えられて、それをもとに教師データの代わりとなる知識を自ら作り出すことができます。なので、なにかのスコアといった数値的な報酬に変換しやすい要素を最大化させるなどの行動を学習したいときに有効であると言えます。また、ランダムに試した行動がうまくいったかを学習するため、人間が思ってもみなかった答えを編み出すこともあります。今回はその強化学習の手法のうち問題解決のためにどういった行動パターンをとればよいか学習をするQ学習（Q-learning） というものについて考えてみます。

Q学習の仕組み

Q学習ではある状態（situation） における行動（action） の評価値となるQ値（Q-Value）（統計学の用語）というものを学習します。学習を通して、ある状態でのある行動が良いかどうかを正確に判断できるようになれば、すなわち評価値であるQ値を適当に出力できるようになれば学習成功ということになります。良い行動かどうかというのは、環境から与えられる報酬（マイナス値の報酬である罰を含む）のみによって判断できるので状態\(s\)における行動\(a\)のQ値を\(Q(s,a)\)と表すと、環境から与えられる報酬\(r\)を用いて以下のように\(Q(s,a)\)を更新すればよさそうです。 \[Q(s,a)=Q(s,a)+r\] しかし実際にすべての行動に報酬や罰を与えられることは少ないです（もし与えられるなら教師あり学習のほうが良いかもしれません）。サッカーやバスケットボールなどの球技を環境の例として考えてみましょう。これらのスポーツでは「シュートを成功させる」という行為には点（＝報酬）が与えられます。しかし、「ゴールの近くでパスを受け取る」という行動はそれ自体に対して点は与えられません。ですが、一連の流れで見ると「ゴールの近くでパスを受け取る」という行為は点に強く結びつく行動であり、高い評価を与えられるべき行動だと考えられます。なのでこういった行動を「ほぼ点が入ったようなもの」とみなして時刻\(t\)におけるQ値を次のように更新してみることにします。 \[ Q(s_{t},a)=Q(s_{t},a)+(r+maxQ(s_{t+1},a')-Q(s_{t},a)) \] なにやらごちゃごちゃと式が増えましたが、やっていることはそこまで複雑ではありません。\(maxQ(s_{t+1},a')\)というのは時刻\(t\)に状態\(s\)で行動\(a\)をとった後に、時刻\(t+1\)においてとれる行動のQ値の最大値を表します。つまりこれまでの報酬に加えて、「高いQ値のある状態に移行すること」そのものを報酬として与えるようにしています。しかしそういった状態に移行しても必ずしもその高いQ値の行動をとれるとは限りませんし、何よりたくさん更新を繰り返していくとQ値が発散してしまうので、割引率\(\gamma (0<\gamma< 1)\)を用いて更新式を次のように変更します。 \[ Q(s_{t},a)=Q(s_{t},a)+(r+\gamma maxQ(s_{t+1},a')-Q(s_{t},a)) \] 割引率\(\gamma\)は時系列的なつながりの強い場合には1に近く、弱い場合には0に近く設定されます。これによってその後の行動との関係性の強さを設定できます。また、実際に学習を進める場合にはすべてのQ値をランダムな値で初期化してから、「もっともQ値の高い行動をとる」などのように設定し、偶発的な報酬や罰に左右されないように何回も更新を繰り返して少しずつQ値を修正します。なので1回の更新が与える影響を減らすために学習係数\(α\)を用いて更新式を次のように変更します。 \[ Q(s_{t},a)=Q(s_{t},a)+\alpha(r+\gamma maxQ(s_{t+1},a')-Q(s_{t},a)) \] これで一般的に用いられている更新式の完成です。上記の内容を大雑把にまとめます。

環境によって報酬や罰が与えられる場合はその行動のQ値がそのまま決まる
そうでない場合は移行先の最高Q値を割り引いた値を、その行動のQ値にする
学習開始時はすべてのQ値はランダムに初期化され、だんだんと修正をして学習をする

深層学習とは

概要

昨今のAIブームは第三次と言われていますが、その火種となったのが深層学習（ディープラーニング、deep learning） という技術です。これは主にもともとあったニューラルネットワーク（神経網、neural network） のパーセプトロン（Perceptron） という手法を発展させたものを指します。ニューラルネットワークは人間の脳にある神経細胞のネットワークをコンピューター上で数学的に再現を試みる、というものです。ニューラルネットワークは特定の入力に対して特定の出力をするという条件を複数同時に満たすことのできる関数を作成できたりします。なのでニューラルネットワークは知能が関数で表現できることを前提にした上で、その知能を神経細胞を模した関数の集合によって再現してみるという試みとも考えられると思います。もし実在する複雑な問題に対しても関数化が完全に可能になれば、いろいろなことができるようになると考えられます。最近になってから注目を浴びているような印象がありますが、実はニューラルネットワークの歴史自体はとても長く、人工知能研究の歴史の中でも比較的初期段階から研究されていた手法です。しかし近年のコンピューター技術の発展によりニューロン（神経細胞、neuron） の数を容易に増やすことができるようになり、より複雑なネットワークを形成することができるようになったため、ニューラルネットワークの発展的な分野である深層学習等の研究が加速したといえるでしょう。ニューロンの数を増やすだけでなく、そのネットワークの形を工夫する畳み込みニューラルネット（convolutional neural network） などの研究も進んでおり、その最たる例であるGoogleなどの画像認識等の技術には目を見張ります。

ニューラルネットワークの構造

ニューラルネットワークはニューロンが集合して形成するものなので、まずはニューロンとは何かというところから説明します。ニューロンはそれぞれの入力に対応する重み（weight） という係数と、しきい値（threshold） という係数をもち、複数の入力に対して計算をした結果を伝達関数（活性化関数、transfer function） に代入して主に単一の出力をします。これを数学的に表すと、 \[o=f(\sum_{i}x_{i}w_{i}-v)\] \[（o:出力　x:入力　w:重み　v:しきい値　f:伝達関数）\] となります。すこし分かりにくいですが強化学習の式よりもやっていることは単純です。それぞれの入力の値がどれほど出力に影響されるべきかを決定する重みと入力を掛け合わせたものが\(xw\)です。なので\(\sum_{i}x_{i}w_{i}\)というのは入力に重みをかけたものをすべて足し合わせるということなので、入力から取得できる情報を、何が重要か判断して取捨選択するという側面があります。その合計値からしきい値を引き、伝達関数に代入したものが出力となります。しきい値には誤差などの比較的小さな情報を無視するようにする効果があります。伝達関数にはいろいろな関数が使用され、それぞれで効果は違いますが、極端に小さな値や極端に大きな値の影響を小さくするといった効果のものがあります。また、誤差逆伝播法（後述）に、この伝達関数の微分が深く関わっているため学習の精度や速度に直結する部分であると言えます。一般的には \[y= \frac {1}{1+e^{-x}}（シグモイド関数）\] \[y=\left\{\begin{array}{ll}x & (0 \lt x) \\0 & (x \leq 0)\end{array}\right.（ReLU関数）\] などが用いられることが多いです。こうして計算を行う複数個のニューロンを層状に構成し、それぞれのニューロンの出力結果を次の層のニューロンの入力にするというものが一般的にニューラルネットワークと呼ばれるものです。深層学習では、入力を受ける入力層、情報を伝える中間層、出力をする出力層などの層が3～4以上組み合わさったものを使った学習がもっとも多く見られます。また、入力層や出力層のニューロンを増やすことで、複数の入力に対して複数の出力をすることも可能です。

最急降下法

ニューロンの組み合わせで任意の関数を再現するには最急降下法（steepest descent）と誤差逆伝播法（backpropagation） によってそれぞれのニューロンの重みとしきい値を正しく修正することが必要です。詳しくやろうとすると必要な数学的知識が多く、少しややこしいので今回は簡単に説明しようと思います。まず、\(x\)についての関数\(f(x)\)で、出力結果をある値に近づける方法について考えてみます。調整する前の値として\(x=n\)を代入して、出力結果を近づけたい値を\(t\)とおきます。「\(f(n)\)が\(t\)に近づくように\(n\)を変更する」ということは「\(f(n)-t\)が\(0\)に近づくように\(n\)を変更する」ということと同じなので、\[E(x)=\frac {1}{2}{\{f(x)-t\}^2}\]とおいて、ここで目標を「\(E(n)\)が\(0\)に近づくように\(n\)を変更する」に置き換えてみます。ここで\(n\)の変更具合を決定するのに使うのが微分です。\(y=E(x)\)のグラフが以下のようになっている場合を例に考えてみます。

\(x=n\)が①である場合、\(E(n)\)の減る方向に変更すればよいので\(n\)を増やせばいいことがわかります。これは\(x=n\)で傾きが負であるからです。逆に②の場合は傾きが正であるので\(n\)は減らせばいいとわかります。傾きは \[\frac {\mathrm{d}E}{\mathrm{d}x}=\frac {\mathrm{d}E}{\mathrm{d}f}\frac {\mathrm{d}f}{\mathrm{d}x}=\{f(x)-t\}f'(x)\] で求められるので定数\(\alpha(0<\alpha)\)を用いて \[n'=n-\alpha \{f(n)-t\}f'(n)\] とすればよさそうです。この更新を何回も繰り返していくというのが最急降下法の方法です。ちなみに、この式に含まれる定数\(α\)は学習速度、精度ともに深く関わっている定数です。もし小さすぎれば、変化量が少なすぎて何回も調整し直さなければなりません。

また、先ほどの範囲で最小であった\(n=-0.9\)付近は局所的なもので、全体でみると\(n=1.3\)あたりが最小である、という 局所解（local solution） についての問題も変化量が小さい場合には発生しやすくなります。逆に、定数が大きすぎる場合には変化量が大きすぎて最適解を通り過ぎてしまい収束が遅くなります。これは\(\alpha>1\)の場合に何が起こるか、単純な\(y=x^2\)で考えるとわかりやすいです。

誤差逆伝播法

前項で説明した最急降下法を、関数であるニューロンが複数個組み合わさったニューラルネットワークに組み込むのが誤差逆伝播法です。説明の前に少しニューロンの式を以下のように変形してみます。 \[o=f(\sum_{i}x_{i}w_{i})\] \[（o:出力　x:入力　w:重み　f:伝達関数）\] 3-3の式からしきい値がなくなりました。これはしきい値もある一定の入力（定数）に重みをかけたものとみなすことができるからです。重みひとつだけを変数とみなしたとき、ニューロンは\(o=f(\sum_{i}x_{i}w_{i})\)で表され、入力\(x_{i}\)やほかの重み付き入力は定数とみなせるので（偏微分）さきほどの例に当てはめることができます。伝達関数をシグモイド関数にした場合の伝達関数の\(f(x)\)の微分は \[f'(x)=(\frac {1}{1+e^{-x}})'=- \frac {(1+e^{-x})'}{(1+e^{-x})^2}=\frac {e^{-x}}{(1+e^{-x})^2}\] \[=e^{-x}(\frac {1}{1+e^{-x}})^2=e^{-x}f(x)^2=\{\frac{1}{f(x)}-1\}f(x)^2=f(x)\{1-f(x)\}\] となるので出力層の重みの更新式は、伝達関数の微分などを3-3の式に当てはめ、重みの係数である\(x_{i}\)を考慮して、 \[w_{i}'=w_{i}-\alpha (o-t)o(1-o)x_{i}\] と考えられます。これが出力層のニューロンの最急降下法です。ここから出力層のひとつ前の中間層のニューロンの重みを調整することを考えます。出力層とは違い、ニューロンの出力が直接誤差の式に組み込まれていないので、少し追加する必要があります。しかし基本的な考え方は先ほどとまったく同じです。誤差である\(E\)を0に近づければよいのでまずは\(E\)を中間層の重み\(w_{a}\)で偏微分してみます。 \[\frac{\partial E}{\partial w_{a}}=\frac{\partial E}{\partial o_{b}}\frac{\partial o_{b}}{\partial o_{a}}\frac{\partial o_{a}}{\partial w_{a}}=(y-t)(1-o_{b})o_{b}w_{b}(1-o_{a})o_{a}x_{a}\] \[(x_{a},w_{a},o_{a}:中間層の入力、重み、出力　x_{b},w_{b},o_{a}:出力層の入力、重み、出力\] \[E:出力層の誤差　t：目標値 )\] なので中間層の重みの更新式は次のようにすればいいとわかります。 \[w_{a}'=w_{a}-\alpha (y-t)(1-o_{b})o_{b}w_{b}(1-o_{a})o_{a}x_{a}\] また、さらに層が重なっていく場合にはさらにそれぞれの微分を加えればよいです。こういった式がまさに誤差逆伝播法の中身であり、この方法では、微分によって出力層の誤差がそれぞれのニューロンに逆行して伝搬されていると言えます。

深層強化学習とは

強化学習の課題

強化学習はさまざまな課題に対処できる手法ではありますが、実際の問題にすんなりと適応できるかというとそうではありません。大きな課題のうちの1つに「多すぎる状態を保存しきれない」というものがあります。Q学習において、すべてのQ値は状態と行動を対応させた状態で保存されます。単純な問題であれば、保存すべき状態も行動の選択肢も少ないために簡単に保存できます。しかしボードゲームなどの比較的単純な問題でさえ、数手進めるだけで何億通りもの盤面があり、現在のメモリでは保存しきることができません。（将来的に技術が進歩すれば解決できる問題というわけでもありません）実際の問題だったらなおさらです。Q値の保存ができなければもちろんQ学習を進めることはできません。この問題を解決するのに役立つのがニューラルネットワークです。

ニューラルネットワークによる解決

ニューラルネットワークは複数の入力に対して特定の出力をするように学習でき、これは複数の変数をもつ任意の関数の疑似的な模倣ができるといいかえられます。なので先ほどの問題は、状態を複数の変数で表現し、Q値を出力する関数をニューラルネットワークによって学習することで解決できると考えられます。具体的な例で考えてみましょう。先ほどと同じようにサッカーやバスケットボールといったスポーツで一プレーヤーについての行動を例にしてみましょう。こういった球技で変数として表すのがよさそうな要素をリストアップしてみます。

自分の位置、速度
味方と敵の位置、速度
ボールの位置、速度
残り時間

これらは数値で表現可能な情報なので変数として扱うことができます。これらの入力に対して、「前に進む」などについての評価値を算出し、それに基づき行動を行います。そして行動をとってから報酬や罰によってQ値を修正します。この場合、Q値はニューラルネットワークによって構成されるひとつの関数の計算結果として表現されるので、さきほどのニューロンの重みを修正することによって任意の出力に修正できます。つまり、知識をニューロンの重みとして蓄積することができるということです。

深層強化学習によるゲームAI

リバーシについて

リバーシは白と黒が一面ずつある石と、8×8マスに区切られている盤を使って2人でプレイされる完全情報ゲームです。とても有名ですが主なルールを明文化しておきます。

プレイヤーは基本的に交互に1つずつ石を置いていく
自分の番に置く石は、置いてある自分の石と相手の石を直線的に挟めるマスにのみ置くことができる
置いた石と自分の石で挟まれた相手の石はすべて自分の石になり、裏返る
おける場所がない場合にはパスとなる
おける場所がある場合には必ず石をおかなくてはならない
相手も自分もおける場所がない場合にはゲーム終了となる
ゲーム終了時に石の多いプレイヤーが勝利する
ゲーム開始時には中央4マスにそれぞれの石が2個ずつ互い違いに置かれる

今回リバーシを学習対象に選んだ理由は以下の通りです。

8×8マスなので入力となる情報が単純すぎず複雑すぎない
手順通りに進めれば毎回同じ結果になる
ルールが単純で広く知られているゲームである
ほかにも人工知能でやってる方がいる
実際にすぐに対戦できるので強さがわかりやすい
ゲームの実装が複雑でない

学習方法について

もちろん学習方法は多層パーセプトロンによる深層学習を採用しました。詳細は以下の通りです。

第1層～第3層からなりそれぞれの層は128、64、64個のパーセプトロンから構成される
練習相手となる簡易的なコンピュータープレイヤーの強さが適切になるように、そのふるまいを直近100試合の勝率を用いて以下のように設定

勝率(0～1)の確率でランダムに石の置き場所を決定する
そうでない場合は半分の確率で、2手先の時点で相手の石より自分の石がなるべく多くなるようなマスに置く
そうでない場合は同様に3手先の時点で多くなるようなマスに置く

入力はそれぞれのマスに白が置いてあるか、黒が置いてあるか、空白であるかという状態をそれぞれ0と1で表したものに設定。つまり0または1で表される64×3=192個の要素から構成される
出力層はそれぞれのマスに置くことのQ値（0≦Q≦1）に設定。つまり0～1で表されるそれぞれのマスの評価値が計64個出力される
ニューロンとQ学習に関連する定数等は以下のように設定

Q学習の学習係数	\(\alpha=0.1\)
割引率	\(\gamma=0.9\)
ニューロンの学習定数	\(\alpha=0.05\)
出力の誤差の許容値	\(T=19.2(0.1×192)\)
伝達関数	シグモイド関数
学習対象となる試合数	500

また、Pythonのモジュール等で手軽に実装することは可能でしたが、理解を深めるため、今回は何もない状態からC++でコーディングしました。

結果

ある程度の客観的な指標になると思い、石を置ける場所からランダムに選択するコンピュータープレイヤーとの1000試合の結果をここに示しておきます。

試行	勝ち	引き分け	負け
1回目	937	7	56
2回目	812	4	184
3回目	847	25	128
平均	865.3	12	122.7

結果、ランダムな手に対しての勝率は9割ぐらいを予想してましたが約8割5分でした。

ちなみに人間との対戦結果は、人間がたまに負けるくらいの印象でした。

おわりに

今回の制作を通して、その仕組みがわかり今まで朦朧としてた印象が固まりました。また、大企業などの膨大なデータベースを用いたAIの強力さを強く実感しました。次はより複雑な問題や実生活に密接な問題などに挑戦したいと思います。

参考文献

小高知宏、『強化学習と深層学習　-C言語によるシミュレーション-』、オーム社、2017
『誤差逆伝播法を宇宙一わかりやすく解説してみる』、ロボット・IT雑食日記、2018/6/14、閲覧日2021/9/30https://www.yukisako.xyz/entry/backpropagation