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

TadaoYamaokaの日記

山岡忠夫 Home で公開しているプログラムの開発ネタを中心に書いていきます。

将棋でディープラーニングする その23(バリューネットワークの実装)

前々回の日記に書いたバリューネットワークの実装を行った。

elmoで生成した教師データのフォーマットで教師データを読み込むようにした。

前々回の日記で書いたAlphaGoの手法を参考にして、ネットワーク構成は、SL policy networkの出力層に全結合層を繋げてtanhで勝率を表すスカラー値を出力するようにした。
AlphaGoの論文では入力に手番の色の加えているが、とりあえずSL policy networkと同じにした。
教師データは勝敗データ(-1, 1)、損失関数は平均2乗誤差とした。

教師データ

elmo_for_learnで100万局面を生成した。
(elmoの教師データの生成については以前の日記を参照)

学習結果

ミニバッチサイズを32として、SGDで1エポック学習させた結果は以下の通り。
f:id:TadaoYamaoka:20170524234930p:plain
1エポック後のテストデータ1万局面のtest lossは、0.9058882594108582となった。

train lossは順調に下がっているので、学習は成功している。

学習時間は、0:30:08かかった。
elmoと同じ50億局面学習すると、105日(3.5ヶ月)かかる。

バッチサイズを4倍の128にすると、学習時間は0:23:58になった。(1エポック後のtrain lossは0.898と少し悪化)
少し速くなっているが、4倍にはなっていない。
ミニバッチデータを作成する際のハフマン符号のデコードにCPU時間がかかっていると思われる。
この部分をマルチスレッドで処理するなど高速化の工夫が必要そうだ。

ネットワークのパラメータは初期値から学習したが、出力層以外はSL/RL policy networkと同一なため、転移学習が可能である。
転移学習した場合についても次回検証を行いたい。

GitHubにソースを公開しました。
github.com

将棋でディープラーニングする その22(評価値と勝率の関係)

前回の日記で書いたようにバリューネットワークの学習データとして、elmoの教師データを使用する予定である。

elmoの教師データは自己対戦の勝敗だけでなく、深さ6で探索した評価値も同時に出力される。
そこで、学習がうまくいっているかの検証用として、elmoの評価値から推測される勝率を使用したい。

シグモイド関数で近似

elmoは評価値から勝率への変換に、ロジスティック(シグモイド)関数を使用している。
その際、評価値を600で割ってスケーリングしている。
\displaystyle
\frac{1}{1 + \exp(\frac{-a}{600})}
グラフにすると以下のようになる。
f:id:TadaoYamaoka:20170524214751p:plain

教師データの生成に使用しているelmoの評価関数は、この式で最適化されているので、実際に生成されたデータも近い分布になるはずである。

そこで、10万局面を生成し、勝率をプロットしてみた。
その結果、以下のようになった。
f:id:TadaoYamaoka:20170524215115p:plain

評価値100ずつの範囲で勝敗の平均値をプロットしている。
緑の線は、回帰で近似したシグモイド曲線である。
回帰の結果、シグモイド関数のスケーリングのパラメータは、0.00132566 = 1/754.3となった。

elmoは損失関数に、浅い探索と深い探索の評価値の交差エントロピー正則化項として加えているので、元の600から差がでていると思われる。

双曲線関数で近似

AlphaGoの論文では、バリューネットワークの出力層は双曲線関数(tanh)が使われている。
tanhは、グラフの形はシグモイド関数と似ているが、値の範囲が-1~1となる関数である。
負けを-1、勝ちを1で表す場合に適している。
(elmoでは、負けを0、勝ちを1で表しているのでシグモイド関数が適している。)

elmoで生成したデータの勝敗を-1と1にして、tanhで近似した場合についても調べた。
その結果、以下のようになった。
f:id:TadaoYamaoka:20170524220123p:plain

緑の線は回帰で近似したtanh曲線である。
回帰の結果、スケーリングのパラメータは、0.00067492 = 1/1481.7となった。

このスケーリングのパラメータを使用して、バリューネットワークの出力の妥当性を検証したい。

調査に使用したソースコードGitHubに公開した。
github.com
winrate.pyが勝率調査用のコードである。
回帰にはChainerを使用した。

将棋でディープラーニングする その21(elmoの学習データ)

バリューネットワークを実装する前に、検証に使用する学習データの仕様を決めておきたい。

バリューネットワークの入力は、局面と勝敗のセットになる。

AlphaGoの論文ではRL policy networkで終局まで打った際の勝敗データを使用しているが、私の検証しているRL policy networkはまだ精度が悪いため、まともなデータが生成できない。
今年のコンピュータ将棋選手権で優勝したelmoは、教師データとして勝敗データを使用している。
そのため、バリューネットワークの入力データとして流用が可能である。
そこで、elmoを使用して教師データを生成することにする。

elmoで教師データ生成

elmoで教師データを生成するには、elmo_for_learnを使用する。
生成方法は、説明があるのでその通りに行えばできる。
Windowsでビルドするには、MSYS2を使用する。

教師データのフォーマット

elmoの教師データは、局面の情報がハフマン符号で圧縮されている。
ハフマン符号はelmoのソースコードのposition.cpp:33に記述されている。
デコードするにはハフマン符号の伸縮を行えばよい。

Pythonで読めるようにする

Pythonで使用したいため、elmoのC++のコードを参考に、ほぼそのままPythonに移植した。
github.com

elmoとpython-shogiでは将棋盤の座標系が異なるため注意が必要である。
どちらも座標を数値0~80で表しているが、対応する座標が異なる。

通常の将棋盤の座標系

f:id:TadaoYamaoka:20170523210704p:plain

座標と数値

f:id:TadaoYamaoka:20170523212436p:plain

elmoの座標系

f:id:TadaoYamaoka:20170523211203p:plain

python-shogiの座標系

f:id:TadaoYamaoka:20170523212953p:plain

ちょうどpython-shogiの座標系を左に90°回転するとelmoの座標系になる。

上記のpythonのコードでは座標系の変換も行っている。

教師データの活用方法

elmoの教師データには、

  • 局面情報
  • 評価値(depth=6)
  • 指し手
  • 勝敗

の情報が含まれている。

そのため、SL policy network、RL policy network、Value networkの学習データとして使用可能である。

SL policy networkの学習には、局面情報と指し手を使用する。
RL policy networkの学習には、局面情報、評価値、指し手、勝敗を使用する。
評価値は報酬のベースライン(以前の日記で書いたv(s_t^i))として使う。
Value networkの学習には、局面情報と勝敗を使用する。

elmoの教師データを使って、それぞれのモデルの精度を上げてからAlphaGoの手法で学習すると、さらに精度を上げることができそうだ。

将棋でディープラーニングする その20(バリューネットワーク)

週末は電王戦の第2局を観戦していました。
人間のプロとコンピュータの対局はこれで最後となりましたが、コンピュータ同士の電王戦は継続されるということで、今後も楽しみです。

検証しているディープラーニングによるコンピュータ将棋ですが、入力層のフィルターサイズについて見直しが必要と思っています。
飛車などの大駒に対して3×3のフィルターサイズは効果的でないので、駒ごとにフィルターサイズを分ける必要があると思っています。
フィルターサイズのバリエーションを自分で試して実験するのは時間がかかるので、Ponanza Chainerが情報公開を行う予定があるということなので、それを待っています。(まだかなぁー)

さて、今回からバリューネットワークの実装方法の確認を行います。

参考にするAlphaGoの手法は以下の通りです。

バリューネットワークの構成

バリューネットワークは、1から13層は方策ネットワークと同じで、出力層のsoftmaxに代わり、256ノードの全結合層の後に活性化関数がtanhの1ノードの全結合層にした構成となる。
出力は状態(局面)の価値(期待報酬)を表すスカラー値となる。

入力特徴

方策ネットワークの入力特徴に手番の色を追加している。

学習方法

損失関数には平均2乗誤差(MSE)を使用する。
RL policyで終局までプレイした結果(報酬)が教師データとなる。
よって、勾配は以下の式で表される。
\displaystyle
\Delta \theta = \frac{\alpha}{m} \sum_{k=1}^m (z^k - v_\theta(s^k)) \frac{\partial v_\theta(s^k)}{\partial \theta}

z^k RL policyで自己対戦した結果(報酬(-1,1))
v_\theta(s^k) 局面s^kの価値を表す関数(バリューネットワーク)
\alpha 学習率
m ミニバッチサイズ

学習局面のデータセットは、SL policyによる自己対戦によって、1手から450手までランダムに選んだ手数だけプレイした局面から1手ランダムに打った局面が使われる。

ミニバッチサイズm=32として、5千万ミニバッチを学習する。(局面数は1億6千万)


学習データがあれば、学習は普通の回帰問題であり、Chainerなどのフレームワークを使えば損失関数をmean_squared_errorとするだけでよく、実装は易しい。

学習データの生成は、GPUを使えば複数ゲームを並列で進行できるので、探索ベースのプログラムよりは早く生成できそうだが、それでも非常に時間がかかりそうである。

次回はバリューネットワークの実装を行う予定。

将棋でディープラーニングする その19(報酬に応じた勾配 その2)

前回の日記でChainerでミニバッチの要素を1件ずつ処理することで報酬に応じた勾配の計算を実装したが、softmax_cross_entropyのbackwardの処理で、誤差逆の後続に伝えるデルタの値に重みを掛けることで実装できることがわかった。

Chainerのリポジトリからsoftmax_cross_entropy.pyをコピーして、softmax_cross_entropy_with_weight.pyとしてプロジェクトに追加し、以下の通り編集する。

--- chainer/chainer/functions/loss/softmax_cross_entropy.py
+++ softmax_cross_entropy_with_weight.py
@@ -15,14 +15,15 @@
     return numpy.broadcast_arrays(array, dummy)[0]
 
 
-class SoftmaxCrossEntropy(function.Function):
+class SoftmaxCrossEntropyWithWeight(function.Function):
 
     """Softmax activation followed by a cross entropy loss."""
 
     normalize = True
 
-    def __init__(self, use_cudnn=True, normalize=True, cache_score=True,
+    def __init__(self, weight, use_cudnn=True, normalize=True, cache_score=True,
                  class_weight=None, ignore_label=-1, reduce='mean'):
+        self.weight = weight
         self.use_cudnn = use_cudnn
         self.normalize = normalize
         self.cache_score = cache_score
@@ -172,10 +173,13 @@
                 gx *= _broadcast_to(c, gx.shape)
             gx *= (t != self.ignore_label).reshape((len(t), 1, -1))
             gx = gx.reshape(y.shape)
+
         if self.reduce == 'mean':
             gx *= gloss * self._coeff
         else:
             gx *= gloss[:, None]
+        # weight
+        gx *= self.weight.reshape((len(y), 1))
         return gx, None
 
     def backward_gpu(self, inputs, grad_outputs):
@@ -195,33 +199,33 @@
 
         if self.class_weight is None:
             gx = cuda.elementwise(
-                'T y, S t, T coeff, S n_channel, S n_unit, S ignore_label',
+                'T y, T weight, S t, T coeff, S n_channel, S n_unit, S ignore_label',
                 'T gx',
                 '''
                     const int c = (i / n_unit % n_channel);
-                    gx = t == ignore_label ? 0 : coeff * (y - (c == t));
+                    gx = t == ignore_label ? 0 : coeff * (y - (c == t)) * weight;
                 ''',
                 'softmax_crossent_bwd')(
-                    y, cupy.expand_dims(t, 1), coeff, x.shape[1],
+                    y, self.weight.reshape((len(y), 1)), cupy.expand_dims(t, 1), coeff, x.shape[1],
                     n_unit, self.ignore_label)
         else:
             gx = cuda.elementwise(
-                'T y, raw T w, S t, T coeff, S n_channel, S n_unit, '
+                'T y, T weight, raw T w, S t, T coeff, S n_channel, S n_unit, '
                 'S ignore_label',
                 'T gx',
                 '''
                     const int c = (i / n_unit % n_channel);
-                    gx = t == ignore_label ? 0 : coeff * (y - (c == t)) * w[t];
+                    gx = t == ignore_label ? 0 : coeff * (y - (c == t)) * w[t] * weight;
                 ''',
                 'softmax_crossent_weight_bwd')(
-                    y, self.class_weight, cupy.expand_dims(t, 1), coeff,
+                    y, self.weight.reshape((len(y), 1)), self.class_weight, cupy.expand_dims(t, 1), coeff,
                     x.shape[1], n_unit, self.ignore_label)
 
         return gx, None
 
 
-def softmax_cross_entropy(
-        x, t, use_cudnn=True, normalize=True, cache_score=True,
+def softmax_cross_entropy_with_weight(
+        x, t, weight, use_cudnn=True, normalize=True, cache_score=True,
         class_weight=None, ignore_label=-1, reduce='mean'):
     """Computes cross entropy loss for pre-softmax activations.
 
@@ -271,6 +275,6 @@
 
     """
 
-    return SoftmaxCrossEntropy(
-        use_cudnn, normalize, cache_score, class_weight, ignore_label, reduce)(
+    return SoftmaxCrossEntropyWithWeight(
+        weight, use_cudnn, normalize, cache_score, class_weight, ignore_label, reduce)(
             x, t)

softmax_cross_entropyの引数にweightを増やして、backward_cpuおよびbackward_gpuのgxの計算でweightの値をミニバッチの各要素に掛けるようにしている。
こうすることで逆伝播の後続処理でも勾配に重みが掛けられる。

3層パーセプトロンに適用すると以下のようになる。

import numpy as np
from chainer import Chain, Function, Variable
from chainer import optimizers
import chainer.functions as F
import chainer.links as L
from softmax_cross_entropy_with_weight import *

W1 = [[ 1.21082544, -0.42751756],
      [ 1.35623264, -0.1971387 ],
      [-0.77883673,  0.28367677]]
W2 = [[ 0.08621028, -0.19540818,  0.78203094],
      [ 0.30133799,  1.3698988 , -0.01031571]]

class MyChain(Chain):
    def __init__(self):
        super(MyChain, self).__init__(
            l1=L.Linear(2, 3, initialW=np.array(W1)),
            l2=L.Linear(3, 2, initialW=np.array(W2)),
        )

    def __call__(self, x):
        h = F.relu(self.l1(x))
        return self.l2(h)

model = MyChain()
model.to_gpu()

optimizer = optimizers.SGD()
optimizer.setup(model)

# print param data
for path, param in model.namedparams():
    print(path)
    print(param.data)
print()

x_data = [[0.1, 0.4],
          [0.2, 0.5],
          [0.3, 0.6]]
t_data = [1, 0, 0]
z_data = [1.0, 0.5, 0.5]

x = Variable(cuda.to_gpu(np.array(x_data, dtype=np.float32)))
t = Variable(cuda.to_gpu(np.array(t_data, dtype=np.int32)))
z = cuda.to_gpu(np.array(z_data, dtype=np.float32))

y = model(x)

model.cleargrads()
loss = softmax_cross_entropy_with_weight(y, t, z)
loss.backward()

optimizer.update()

# print param data and grad
for path, param in model.namedparams():
    print(path)
    print(cuda.to_cpu(param.data))
    print(cuda.to_cpu(param.grad))

z_dataでミニバッチ単位の重みを設定している。
前回の方法に比べミニバッチ単位に計算でき、GPUで効率的に計算できる。

softmax_cross_entropy_with_weight.pyを含むテスト用のプロジェクトをGitHubに公開しました。
github.com

将棋でディープラーニングする その18(報酬に応じた勾配)

前回の日記で、RL policy networkの勾配\Delta \rhoを求める際に、対数尤度の偏微分に報酬に応じた重み(勝敗の報酬z_t^iから状態価値v(s_t^i)を引いた値)を掛ける計算の実装が、Chainerでは難しいということを書いた。

Chainerでは損失関数のbackwardを行うと、ミニバッチで1つの勾配が計算されるため、ミニバッチの要素(局面)単位の勾配に(z_t^i - v(s_t^i))を掛ける計算が実装できない。

そこで、ミニバッチの要素1件ずつ、順伝播と逆伝播を行い、計算された勾配を保存しておき、ミニバッチのすべての要素の勾配を計算できたら、保存しておいた勾配に、報酬に応じた重みを掛け合わせて、それらの平均をとることでミニバッチの勾配とする。
最後に、モデルのupdateを行い、パラメータを更新する。

この方法で、報酬に応じた勾配が実装できる。

しかし、ミニバッチの単位で順伝播、逆伝播の計算ができないため、1件ずつ計算すると時間がかかってしまう。
この部分を効率化するにはChainerの内部で行っている勾配計算に手を入れるか、TensorFlowなどでより低レベルな実装を行う必要がある。

また、勾配の計算はGPUからCPUに値を移して計算する必要があるため、メモリ転送で時間のロスが発生する。

実行時間を気にしなければ、以下のように記述することで実装できる。
下記の例は、3層パーセプトロンで、ミニバッチの要素ごとに勾配に重みを掛けている。

import numpy as np
from chainer import cuda, Chain, Function, Variable
from chainer import optimizers
import chainer.functions as F
import chainer.links as L

W1 = [[ 1.21082544, -0.42751756],
      [ 1.35623264, -0.1971387 ],
      [-0.77883673,  0.28367677]]
W2 = [[ 0.08621028, -0.19540818,  0.78203094],
      [ 0.30133799,  1.3698988 , -0.01031571]]

class MyChain(Chain):
    def __init__(self):
        super(MyChain, self).__init__(
            l1=L.Linear(2, 3, initialW=np.array(W1)),
            l2=L.Linear(3, 2, initialW=np.array(W2)),
        )

    def __call__(self, x):
        h = self.l1(x)
        return self.l2(h)

model = MyChain()
model.to_gpu()

optimizer = optimizers.SGD()
optimizer.setup(model)

# print param data
for path, param in model.namedparams():
    print(path)
    print(param.data)
print()

x_data = [[1, 2],
          [3, 4]]
t_data = [0, 1]

# init grads
dic_grads = {}
for path, param in model.namedparams():
    dic_grads[path] = []

for x_elem, t_elem in zip(x_data, t_data):
    x = Variable(cuda.to_gpu(np.array([x_elem], dtype=np.float32)))
    t = Variable(cuda.to_gpu(np.array([t_elem], dtype=np.int32)))

    y = model(x)

    model.cleargrads()
    loss = F.softmax_cross_entropy(y, t)
    loss.backward()

    # save grad
    for path, param in model.namedparams():
        dic_grads[path].append(cuda.to_cpu(param.grad))

# manipulate grad
z_data = [1.0, 0.5]
z = np.array(z_data, dtype=np.float32)
for path, param in model.namedparams():
    grads = np.array(dic_grads[path], dtype=np.float32)
    grad = np.tensordot(z, grads, axes=1)
    grad /= len(z_data)
    param.grad = cuda.to_gpu(grad)

optimizer.update()

# print param data and grad
for path, param in model.namedparams():
    print(path)
    print(cuda.to_cpu(param.data))
    print(cuda.to_cpu(param.grad))

zがミニバッチの要素(要素数2)ごとの重みとなっている。

z_data = [1.0, 1.0]

とすると、Chainerの勾配計算と同じになる。

上記の方法ではGPUを活かしきれず非効率であるため、Chainerの内部処理をもう少し理解して、効率化を検討する予定。
softmax_cross_entropyのbackwardに手を入れることで実現できないか調べている。

将棋でディープラーニングする その17(強化学習の実装)

前回の日記に書いたように方策ネットワークを使って自己対戦できるようになったので、AlphaGoの手法(RL policy network)で強化学習の実装を行った。

教師ありで十分に訓練できていないので、今の時点で強化学習を行っても効果はでないと思われるが、実装方法の確認を目的にとりあえず実装を先に行った。

AlphaGoの論文に書かれている強化学習の手法は以前の日記に書いた通り、REINFORCE algorithmが使われている。

以下の式で表される勾配で方策ネットワークのパラメータを更新する。
\displaystyle
\Delta \rho = \frac{\alpha}{n} \sum_{i=1}^n \sum_{t=1}^{T^i} \frac{\partial \log p_\rho (a_t^i \mid s_t^i)}{\partial \rho} (z_t^i - v(s_t^i))

v(s_t^i)は、状態価値関数の値で、局面ごとに値が異なるため、Chainerで実装するには、サンプルごとの異なる値を勾配に掛ける必要があり、コアな処理に手を入れないとと実装できそうにない。(TensorFlowの方が低レベルの計算ができるので向いているかもしれない。)
ただし、v(s_t^i)は、バリューネットワークができる前は、常に0で学習するため、v(s_t^i)を使用しない場合について実装した。

勾配計算の実装

上記の式は対数尤度(交差エントロピー誤差)に勝敗による報酬z_t^iを掛けたものであるため、学習率に勝敗の報酬を掛けて、損失をsoftmax_cross_entropyとして実装した。

方策ネットワークによる対局

自己対戦部分は、方策ネットワークにより指し手を確率に応じて選択し、勝敗の判定にUSIエンジンを補助的に使用した。
ほぼ勝敗がはっきりした局面で指し手を進めても学習に悪影響があるため、USIエンジンが探索で求めた評価値で勝敗がはっきりした時点(勝率0.85以上)で、その時点の評価値から算出した勝率を報酬の値とした。
評価値から勝率の予測は、elmoなどで採用されている以下の式で計算した。
\displaystyle
\frac{1}{1 + \exp(\frac{-a}{600})}
これを勝率0.5の報酬が0になるようにして平行移動とスケーリングして使用した。

方策ネットワークで指し手を確率で選ぶ際には、AlphaGoの論文に書かれているように、下記の式で表されるBolzmann分布を使用した。
\displaystyle
\frac{\exp(Q_t(a)/\tau)}{\sum_{b=1}^n \exp(Q_t(b)/\tau)}
\tauは、温度(softmax tempature)と呼ばれる正定数で、温度が高い場合すべての行動が同程度に起こり、低い場合は選択確率の差がより大きくなる。
適切な値が分かっていないので、ひとまずAlpahGoの論文と同じ値0.67を使用した。

Chainerでは、softmax_cross_entropyの入力は、出力層の活性化関数に入力する値を入力とするので、入力はlogスケールの確率になっている。
そのため、通常はsoftmaxを使用する代わりに、上記式のQ_t(a)にその値を入力して計算する。

自己対戦の実装

方策ネットワークは、GPUを使用して同時計算が可能であるため、対局はミニバッチ単位で行い、各対局を同時に1手ずつ進める。
ミニバッチは、半分を先手番と半分を後手番とする。

USIエンジンで局面を評価して終局判定を行い、終局した対局をミニバッチから取り除く。
ミニバッチの全対局が終了したら、対局ごとをバッチの単位として、その対局のすべての局面を入力、選択した手を教師データとして、損失をsoftmax_cross_entropyとして誤差逆伝播を行いパラメータを更新する。
その際、学習率は定数に勝敗の報酬を掛けた値を使用する。
負けた対局の場合は、学習率は負の値になるので、損失が増える方向に学習される。

対局相手は、以前に更新したパラメータからランダムに選んだパラメータを使用する。

自己対戦の実装はこちらのAlphaGoのクローンの実装を大いに参考にした。

実行結果

以上を実装して、以前に教師ありで学習したパラメータを初期値として、強化学習を実行した。

方策ネットワークによる対局は並列で行えるが、USIエンジンによる評価値の算出はシーケンシャルな処理になるため、1手0.1秒に設定しても、非常に時間がかかる。
16ゲームをミニバッチとした場合、1イテレーション(16ゲームの対局)に1分半もかかった。

初期値から40イテレーションを学習してみたが、勝率が上がる傾向は見られなかった。
f:id:TadaoYamaoka:20170520193049p:plain

なお、学習率の定数は小さい値(0.001)にしていないと値が発散してうまく学習できなかった。

初期値の教師ありで学習したパラメータの質が良くないので、これ以上は学習を試すのは保留する。

次回はバリューネットワークの実装を試す予定。

GitHubにソースを公開しました。
github.com