【E資格】AlphaGo数式編【AI】

こんにちは
E資格合格を目指すサラリーマンのゆゆです。

前回「最強囲碁AI アルファ碁 解体新書 増補改訂版」を読んで、私なりにAlphaGoについてnoteにまとめました。

100％自信を持ってAlphaGoを理解したとは言えないのですが、黒本の問題文で問われていることは理解できるようになったかなと思います。
（なんで黒本がモチベーションになっているんだ・・・）

で、肝心の「問題に正解する」に関してはまだまだダメだったので、書籍のAppendixも読み、黒本に解答できるよう「AlphaGo数式編」として今回自分なりにまとめてみました。

ちなみに書籍を書かれた「大槻 知史さん」が作ったプレゼン資料（↓）がネットにありましたので、書籍を買うまでではないんだけどAlphaGoを勉強したいという方は読まれるといいかもしれません。

http://home.q00.itscom.net/otsuki/20160415AlphaGopublic.pdf

◆黒本で問われる数式

黒本で問われていますが、実際E資格でAlphaGoについて数式関連で問われるとしたら、

＜学習時＞

SLポリシーネットワークのパラメータ更新
RLポリシーネットワークのパラメータ更新
バリューネットワークのパラメータ更新

＜実戦（対局）時＞

勝率Q(s,a)
バイアスu(s,a)

なのではないかと勝手に思っております。

AlphaGo関係なく、
学習時：ディープラーニングや強化学習（方策勾配法）の更新について
実戦時：強化学習のUCB1について
の理解をAlphaGoを通じて問われている感じですかね。

数式以外だと、さすがにCNNのチャンネル数やAlphaGoと対戦した人を問われることはないと思いますが、何の学習はGPUで何日かかったとかはあるかもしれませんね。

Googleのバケモノリソースで何日ってどうせそんな事できる企業なんて限られているんだから、問わないで欲しいですけど。

ちなみにAlphaGo Zeroは3日間で学習できたらしいですけど、普通のPC（CPUだけ）だと20000年かかるらしいです。

◆AlphaGo学習時の数式

表記文字（$${w}$$とか）や数式は基本「最強囲碁AI アルファ碁 解体新書 増補改訂版」に合わせております。
（黒本と数式が若干異なりますが本質的なところは同じです）

＜SLポリシーネットワークのパラメータ更新＞

SLポリシーネットワークはCNNなのでAlphaGoだからと言って構えることなく従来の交差エントロピー誤差で考えればいいです。

CNNで猫の画像を与えて猫を出力させるときと同じで、最終的にはsoftmaxに入れて、各クラスに対する確率を算出します。

出力クラス数は囲碁は普通19×19路盤を用いるので、19×19=361個です。

損失関数$${L_w}$$は、

$${L_w=-\sum_{k=1}^{M}\sum_{a=1}^{A}t_a^k\log{y_a^k}}$$

M：学習データ数
A：出力クラス数（＝361）
t：教師データ
y：AIの出力値（推論値）
　→ある局面においてある手を選択する予測確率

となります。

学習データに対する正解は1手なので、教師データは361次元のワンホットベクトル（0か1）になります。

ですので、$${\sum_{a=1}^{A}t_a^k}$$ は正解データ1を掛ける部分だけ残り、

$${L_w=-\sum_{k=1}^{M}\log{y^k_{a^k}}}$$

となります。

確率的勾配降下法（SGD）を用いる場合、$${w}$$を重みパラメータ、$${α}$$を学習率とすると、

$${w←w+αΔw}$$,       $${Δw=-\frac{∂L_w}{∂w}}$$

と、いつもの見慣れた式が出てきて、

$${Δw=-\frac{∂L_w}{∂w}=\sum_{k=1}^{M}\frac{∂\log{y^k_{a^k}}}{∂w}}$$

$${=\sum_{k=1}^{M}\frac{∂\log{p_w(a^k|s^k)}}{∂w}}$$

となります。

最後$${y^k_{a^k}=p_w(a^k|s^k)}$$として条件付き確率の表現に変えております。

黒本では$${L_w}$$の式にデータ数$${M}$$で割ってデータ一つあたりにしていますが、そういった細かいところを除けば本式で解答できるかと思います。

＜バリューネットワークのパラメータ更新＞

バリューネットワークは順序的にはRLポリシーネットワークを学習させてから学習させるのですが、SLポリシーネットワークと同じCNNなので、CNN続きとして先にこちらを説明します。

まずバリューネットワークって何を出力するかなんですが、「次の一手」ではなく「ある局面における勝率予測値」を出力します。

なんでそんなことをするのかは前回のnoteを御覧いただきたいのですが、簡単にいうと最終的に選ぶ一手の精度向上に一役買うからです。

超理想的なことを言うと、このバリューネットワークの精度が100％で、しかも200〜300手くらいの色んな手に対して計算する余裕があればバリューネットワークさえあればいいような気がします。
（◯×ゲームで見ただけで勝ち負け分かるあの感覚です）

実際はそうならないので、他のネットワークなどの合せ技で使われるという感じです。

さてバリューネットワークの損失関数ですが、出力が勝率だからsigmoid関数にかませて、交差エントロピー誤差でしょって思いきや、まさかの回帰問題で二乗誤差でした。

出力は「0~1」ではなく、「-1~1」とのことなのですが、「0~1」で交差エントロピー誤差を使えばいいと思うのは私だけでしょうか・・・

確か教師データってSLポリシーネットワークとRLポリシーネットワークで作って、勝ちと負けをはっきりさせるんじゃなかったでしたっけ？
（教師データが勝率0.7とかであればわかりますが）

前置き長くなりましたが、バリューネットワークの損失関数は

$${L_θ=\sum_{k=1}^M(z^k-y^k)^2}$$

です。

回帰の損失関数そのものですね。

$${y^k=v_θ(s^k)}$$

とすると、

$${Δθ=-\frac{∂L}{∂θ}=\sum_{k=1}^M2(z^k-v_θ(s^k))\frac{∂v_θ(s^k)}{∂θ}}$$

となります。

係数に関わるところがやはり黒本と異なりますが、解答することはできるかと思います。

＜RLポリシーネットワークのパラメータ更新＞

RLポリシーネットワークを理解する上のキーワード的なものを挙げると、

・方策勾配法
・REINFORCEアルゴリズム
・ベースライン

となります。

RLポリシーネットワークは上記キーワードを数式展開含めしっかり理解していれば何も難しくないんだと思いますが、方策勾配法の数式を選択肢から選ぶ能力しかない私にとっては厳しいものがあります。

もちろんnoteを書く前に方策勾配法の証明をしているサイトを見てはいるのですが、噛み砕いて私なりの表現で説明することはできません。

以下に数式を並べておりますが、本当に申し訳ないのですが、こういうものだとしてお読みください。
（黒本にも方策勾配法の数式は暗記しましょうって書いてあったし笑）

書籍としては、今回出てくる更新パラメータは$${ρ}$$ですが、黒本表記の$${J(θ)}$$で書かせて頂きたいと思います。

$${∇_θJ(θ)=\sum_sd^{π_θ}(s) \sum_a ∇_θπ_θ(a|s,θ)Q^{π_θ}(s,a)}$$

$${=\mathbb{E}[∇_θ\log{π_θ(a|s,θ)Q^{π_θ}(s,a)}]}$$

この2式はE資格の問題で出てきそうなやつですね！（暗記せねば！）

どうも$${∇_θJ(θ)}$$は解析的には解けないので、モンテカルロ法を使ってサンプリング結果を用いて求めないといけないみたいです。

したがって近似式としては、

$${∇_θJ(θ)≈\frac{1}{N}\sum_{n=1}^{N} \frac{1}{T} \sum_a^T ∇_θ \logπ_θ(a^n|s^n,θ)Q^{π_θ}(s^n_t,a^n_t)}$$

となりますが、$${Q^{π_θ}(s^n_t,a^n_t)}$$は依然未知であるため、報酬や収益で近似します。
（REINFORCEアルゴリズムってやつですね）

報酬を$${z^i_t}$$とすると、

$${∇_θJ(θ)≈\frac{1}{N}\sum_{i=1}^{N} \frac{1}{T} \sum_a^T ∇_θ \logπ_θ(a^i|s^i,θ)z^i_t}$$

となります。

これでも学習は進むらしいのですが、ここからREINFORCEアルゴリズムを改善するベースラインという考えを導入します。

式的には$${z^i_t}$$を$${z^i_t-v(s^i_t)}$$に変えるだけです。

最終的に、

$${∇_θJ(θ)≈\frac{1}{N}\sum_{i=1}^{N} \frac{1}{T} \sum_a^T ∇_θ \logπ_θ(a^i|s^i,θ)(z^i_t-v(s^i_t))}$$

がRLポリシーネットワークの更新式となります。

「最強囲碁AI アルファ碁 解体新書 増補改訂版」にはベースラインを導入した理由が記載されているのですが、ベースラインを導入すると勝敗の予測が難しい場面や勝敗が逆転するような場面をうまく学習させることができるようです。

◆AlphaGo実戦（対局）時の数式

黒本に載っている数式は$${Q(s,a)}$$と$${u(s,a)}$$なので、この2点に絞って説明したいと思います。

＜暫定勝率＞

これは私が勝手に言っている用語なので、黒本にも「最強囲碁AI アルファ碁 解体新書 増補改訂版」にも出てきません。

意味としては、$${Q(s,a)}$$と$${u(s,a)}$$を足したものを指したいのですが、用語として見つからずそう呼んでいます。

UCB1の考えのもとにできているので、暫定勝率ではなくUCB1って言うのかもしれませんが、それはそれで違うような気がしたので私のnoteでは「暫定勝率」と書かせていただきます。

で、この暫定勝率は勝率とバイアスを足し合わせたものですが、（記載していいかわからないけど）数式として書くと、

暫定勝率 $${=Q(s,a)+u(s,a)}$$

となり、

$${Q(s,a)}$$が勝率、$${u(s,a)}$$がバイアスを表します。

前回のnoteに書いたのですが、実戦ではこの暫定勝率が大きい手に対してより深堀りをしていき最終的に暫定勝率の高い（正確には訪問回数の多い）手を選びます。

暫定勝率がどう計算されるかは置いといて、どうしてバイアスなるものがあるかというと、確率の高い手を探して深堀りする際に、その確率が正しくないかもしれないので下駄（バイアス）を履かせています。

例えばa手とb手を評価するときに、
真の確率がa手は勝率90％で、b手は30％であったとしても、シミュレーションの初期ではたまたま確率のゆらぎでa手を50%、b手を60%と評価し、b手の方がいいと判断してb手の深堀りをしてしまうかもしれません。

そうならないようにシミュレーションの回数（その手の訪問回数）に応じて下駄を履かせるようにします。

ですので、シミュレーション回数が増えれば下駄（バイアス）は下がっていき、無限回のシミュレーションができれば0になります。

それでは勝率、バイアスがどのような数式になるか見ていきたいと思います。

＜勝率Q(s,a)＞

文章で書くと、「バリューネットワークが出力する勝率とプレイアウトの結果の勝率を統合させたもの」です。

式は以下の通りです。

細かいことは置いといて、勝率なので「勝った数÷対局数」を計算しているだけと思えばいいのかなと思います。

$${W}$$は正確には負けたら+0ではなく、-1で更新されるのですが。

バリューネットワークによる直感（勝率）を入れているところがAlphaGoのすごいところみたいです。

＜バイアスu(s,a)＞

式は以下の通りです。

こちらも細かい数式は置いといて眺めますと、訪問回数$${N_r}$$が小さい時はバイアスが大きくなり、訪問回数が多くなればバイアスは小さくなるのがわかります。

数式にはSL ポリシーネットワークの事前確率$${P(s,a)}$$が掛けられているのですが、直感でこの手はないなと思われる手はいくら訪問回数が少なくともバイアスを大きくしないようにしている一種の工夫だと思われます。

◆最後に

書籍の読解およびnoteの更新で何日か取られてしまいAlphaGoの勉強時間にそんなに費やしていいのか不安になってきたのですが、黒本の17章だけ毎回鉛筆コロコロなのがどうしても許せず思い切って勉強時間を取りました。

記号が何を表しているのかなどすっ飛ばしたひどい記事になってしまいましたが、AlphaGoを勉強していてつまずいた方が少しでも得るものがあったのであれば幸いです。