TadaoYamaokaの開発日記

個人開発しているスマホアプリや将棋AIの開発ネタを中心に書いていきます。

仮説検定でプログラムが有意に強くなったか検証する

プログラムで自己対局したときに、その対局数と勝敗の数から何%勝ちなら強くなったといえるのか。
そのような問題に統計的に答える方法として、仮説検定という方法がある。

仮説検定

仮説検定は、帰無仮設と対立仮説を設定し、帰無仮説が定めた有意水準の範囲内かにより、棄却されるか採択されるか判定する。

詳しい説明は、統計の教科書に譲るとして、対局結果から強いかの検定には以下の式で計算する。

帰無仮説 H_0P=P_0(=0.5)
対立仮説 H_1P > P_0
と設定すると、
\displaystyle
u_0 = \frac{r-P_0}{\sqrt{P_0(1-P_0)/n}}
u_0が棄却域Rにあれば、帰無仮説H_0は棄却され、対立仮説H_1が採択される。

ここで、rは勝率、nは対局数で、棄却域Rは、有意水準\alpha=0.05とするとR > 1.644854となる。

棄却域の臨界値は、R言語を使って、

qnorm(0.05, lower.tail=FALSE)

で計算できる。

対局数がn=100の場合、勝率rが有意であるためには、
\displaystyle
\frac{r-0.5}{\sqrt{0.5(1-0.5)/100}}>1.644854
から、
\displaystyle
r>0.5822427
であれば有意に強いと言える。

対局数が1000回だと、
\displaystyle
r>0.5260074
となる。

前回の日記で、自己対局の結果、100回対局して勝率が54%で強くなっていると判断したが、統計的には有意とは言えない。
逆に、勝率54%を有意と言うには、
\displaystyle
\frac{0.54-0.5}{\sqrt{0.5(1-0.5)/n}}>1.644854
から
\displaystyle
n > 422.7414
の対局が必要になる。

勝率と必要対局数

勝率と必要対局数の関係は、以下のグラフのようになる。
f:id:TadaoYamaoka:20170615075043p:plain
※横軸は勝率で、縦軸は必要対局数(10の対数)

グラフはR言語の以下のスクリプトでplotした。

need_n <- function(r) {
  qnorm(0.05, lower.tail=FALSE)^2 * 0.5 * (1-0.5) / (r - 0.5)^2
}
need_n_log10 <- function(r) {
  log10(need_n(r))
}
plot(need_n_log10, 0.5, 1)

Pythonでグラフを描くには、以下のように実行する。

import matplotlib.pyplot as plt
import numpy as np
import scipy.stats

x = np.linspace(0.5, 1, 100)
plt.plot(x, scipy.stats.norm.ppf(0.95)**2 * 0.5 * (1 - 0.5) / (x - 0.5) ** 2)
plt.yscale("log")

将棋でディープラーニングする その34(強化学習【成功】)

以前にRL policy networkをelmoの自己対戦でデータを使ってREINFORCE algorithmで学習させたが、うまく学習できなかった。

昨日の日記でマルチタスク学習を実装したので、RL policy networkをバリューネットワークと同時に学習させることで、RL policy networkの学習がうまくいくか試してみた。

学習方法

RL policyの出力のバッチごと損失(交差エントロピー)に報酬を乗じた値を平均したものと、バリューネットワークの損失(交差エントロピー)の和を損失とした。
勝敗(0か1)をz、局面の価値(0から1)をvとしたとき、z-vを報酬として使用する。
勝敗はelmoの自己対局の結果、局面の価値はelmoの評価値をシグモイド関数で勝率に変換したものを使用する。

検証結果

1億局面から学習済みのモデルを使用して、elmo_for_learnで生成した1千万局面を学習させた。
f:id:TadaoYamaoka:20170608222709p:plain
バッチサイズ64で、10000イテレーション学習したところで、損失がnanになってしまった。

バリューネットワークを同時に学習してもうまくいかなかった。

policyのtest accuracyが0になっていることから、教師データの指し手を選ばないことが最も損失が小さくなるので、そのように学習してしまったためと思われる。
モデルの一致率が40%程度なので、勝ちのゲームで正しい指し手を選んで得られる場合が少なく、負けのゲームで指し手が一致しているとマイナスの報酬となるため、全ての手で指し手を選ばないことが最小の損失となってしまう。

追試1

ChainerRLのソースを眺めていると、GradientClippingを使用したので、GradientClippingを試してみた。
発散するまでのイテレーションが少し伸びたが結果は同じとなった。
WeightDecayも試したが同じだった。

対策

全て指し手と一致しない方が損失が小さくなるようではうまく学習できないと考えられるため、報酬の与え方を工夫する必要がある。

プラスの報酬が多くなるようにするには、勝ちの局面の割合を多くすればよい。
しかし、一致率が40%程度なので、勝ちの局面の割合を負けの局面の倍以上にする必要があり、教師データが有効に活用できなくなる。

別の方法として、報酬にベースラインを加えて、全体的にプラスの報酬を多くすることが考えられる。
そうすることで、勝ちの局面で負けたゲームの指し手にはマイナスの報酬となり、それ以外では少なくともプラスの報酬とすることができる。
重み付きの教師あり学習に近くなる。
負けの局面から勝ちのゲームとなった指し手は高い報酬となるので、効果的な手を重視して学習できる。

ベースラインに0.5を使用して、elmo_for_learnで生成した1千万局面を学習させたところ、以下のようになった。
f:id:TadaoYamaoka:20170608225502p:plain
バッチサイズ128で、1千万局面を学習できた。

train lossは下がり続けており、うまく学習できている。
policyのtest accuracyは上がっていないが、勝ちの局面で負けたゲームでは指し手が一致しない方が良いので、test accuracyが上がっていないことは必ずしも問題ではない。
value networkのtest accuracyは、上がり続けており、うまく学習できている。

効果測定

ベースラインを加えて学習したモデルと、学習前の1億局面を学習したSL policyのモデルで対局を行った。
100回対局した結果以下の通りとなった。

SL policy 勝ち48(49%)
RL policy(ベースラインあり) 勝ち49(50%)

あまり変わっていないが、少なくとも弱くはなっていない。
学習局面をさらに増やした場合や、他のソフトとの対局でも検証してみないとはっきり効果は分からない。

検証は時間がかかりそうなので、別途効果の検証を行う。

今回、elmo_for_learnの自己対戦データを使用して学習したが、AlphaGoのRL policy networkと同じように自己対戦でも、ベースラインを調整することでうまく学習できるようになると思われる。

検証には以下のコードを使用した。
https://github.com/TadaoYamaoka/DeepLearningShogi/blob/master/dlshogi/train_rl_policy_with_value_using_hcpe.pygithub.com

2017/6/9 追記

3千万局面、上記の方法で学習させたモデルと学習前のモデルで対局を行った結果、以下の通りとなった。

SL policy 勝ち43(45%)
RL policy(ベースラインあり) 勝ち51(54%)

学習に効果があることが確かめられた。

ただし、3千万局面以上学習させるとtest accuracyが急に下がる現象が起きて学習できなくなった。
f:id:TadaoYamaoka:20170609211139p:plain
この辺がこのモデルの限界かもしれない。

将棋でディープラーニングする その33(マルチタスク学習)

SL policy networkとValue networkは、12層までは同じ構成で、出力の数層のみが異なるため、12層まで同じネットワークでそこから2つの出力を行うようにして、SL policy networkとValue networkを同時に学習することを試してみた。

複数のタスクを同時に学習することを、マルチタスク学習といい、以下の論文では顔器官の座標と顔の角度を同時に学習することで精度が上がることが報告されている。
Facial Landmark Detection by Deep Multi-task Learning

マルチタスク学習を行うことで、SL policy networkとValue networkのネットワーク構成が一つになるため、指し手と価値の予測を同時に行えるようになり、対局時の処理時間も短縮できる効果がある。
精度も向上できれば、効果的な手法となる。

ネットワーク構成

SL policyとValue networkで12層目までを共有する。
SL policyは、12層の出力をそのまま出力とする。
Value networkは、13層目で全結合を行い、出力が1つの全結合層に接続する。

学習方法

SL policyの出力のsoftmax_cross_entropyとValue networkの出力のsigmoid_cross_entroyの和を損失として、SGDで学習する。

test accuracyは、SL policy、Value networkのそれぞれの出力で評価する。

検証結果

100万局面を学習データに使い、初期値からSL policy単体、Value network単体、マルチタスク学習した場合を比較した。
f:id:TadaoYamaoka:20170607233357p:plain
※凡例にsl_valが付くものがマルチタスク学習の結果

1エポック後のテストデータ1万局面のtest accuracyは以下の通り。

SL policy単体 0.2819378972053528
マルチタスク学習(SL policy) 0.28547564148902893
Value network単体 0.6400353908538818
マルチタスク学習(Value network) 0.6896619200706482

tain lossはマルチタスク学習したものはSL policy単体より大きくなっているが、Value networkのlossが足されているので妥当である。
減少の傾向は同じであるため、うまく学習できていると思われる。

test accuracyは、SL policy単体とマルチタスク学習のSL policyの出力でわずかにマルチタスク学習の方が一致率が高い。
Value network単体とマルチタスク学習のValue networkの出力では、マルチタスク学習の方が良い一致率になっている。

以上の結果から、マルチタスク学習は精度においても効果的であることが分かった。


RL policy networkの学習がうまくいかず保留していたが、RL policy networkでもマルチタスク学習を行うことで、Value networkの学習がある種の正則化として働いてうまく学習できるようになるのではないかと予測している。
それについては、別途検証したい。


マルチタスク学習は以下のコードで検証した。
https://github.com/TadaoYamaoka/DeepLearningShogi/blob/master/dlshogi/train_sl_policy_with_value.pygithub.com

将棋でディープラーニングする その32(転移学習)

以前の日記で、バリューネットワークを学習した際、SL policy networkからバリューネットワークに転移学習が可能であることに言及した。

転移学習するには、12層まではネットワーク構造が同じであるため、SL policy networkからバリューネットワークにパラメータをそのままコピーすればよい。

モデルのコピー方法

Chainerでモデルを部分的にコピーするには、以下のようにする。

policy_model = PolicyNetwork()
value_model = ValueNetwork()

serializers.load_npz(args.policy_model, policy_model)

value_dict = {}
for path, param in value_model.namedparams():
    value_dict[path] = param

for path, param in policy_model.namedparams():
    value_dict[path].data = param.data

serializers.save_npz(args.value_model, value_model)

一旦モデルのインスタンスを作って、それぞれのモデルのnamedparams()でパラメータのパスとパラメータを取得して同じパスのパラメータの値をコピーすればよい。

転移学習の効果測定

1億局面から学習済みのSL policyのモデルをバリューネットワークにコピーして、elmo_for_learnで生成した100万局面でバリューネットワークを学習したところ以下のようになった。
f:id:TadaoYamaoka:20170607222435p:plain
※凡例のinitialが初期値から学習した場合
※transferが転移学習した場合

1エポック後のテストデータ1万局面のtest accuracyは以下の通りとなった。

初期値 0.6400353908538818
転移学習 0.7109866142272949

転移学習した方がtrain lossが35%小さくなり、test accuracyは11%大きくなっている。

以上の結果から、SL policy networkからバリューネットワークへの転移学習は効果があることが確かめられた。

なお、バリューネットワークの出力はAlphaGoではtanhだが、sigmoidに変更している。
理由は、後ほどSL policyとvalue networkのマルチタスク学習を試したいため、lossを交差エントロピーに揃えたいためである。
上記のtest accuracyは、binary_accuracyで求めている。

モデルのコピーには以下のコードを使用した。
https://github.com/TadaoYamaoka/DeepLearningShogi/blob/master/dlshogi/transfer_policy_to_value.pygithub.com

ChainerをC++から使う

ディープラーニングを使った将棋プログラムを試しているが、将棋プログラムは速度が必要なため、開発言語はC++が適している。
しかし、使用しているディープラーニングフレームワークのChainerはPythonにしか対応していない。

CaffeやCNTK、TensorFlowなどC++で実行可能なフレームワークもあるが、個人的にはChainerが使いやすいので、できればC++からChainerを使用したい。

以前に、ChainerのモデルをC++で読み込んでcuDNNで実行することを試したが、今回はBatchNormalizationやDropoutも使用しているので、スクラッチで作成するには少々無理がある。

ということで、C++からPythonランタイムを呼び出して、PythonでChainerを使うことを考える。
Pythonの呼び出しにはオーバーヘッドがあるので、その影響も考慮する。

実装方法

C++からPythonの呼び出しは、Boost.Pythonを使うことで比較的簡単に実装できる。
(Boost.Pythonのセットアップ方法は以前の日記参照)

#include <boost/python.hpp>

namespace py = boost::python;

py::object module_ns = py::import("module").attr("__dict__");
py::object module_func = module_ns["func"];

module_func();

のようにして、Pythonに定義した関数を実行できる。

Chainerを使用する場合、データの入出力にNumpyを使用する。
NumpyもBoost.Numpyを使うとC++側から簡単に利用できる。

float features[BATCHSIZE][FEATURENUM][H][W];

np::ndarray ndfeatures = np::from_data(
	features,
	np::dtype::get_builtin<float>(),
	py::make_tuple(BATCHSIZE, FEATURENUM, H, W),
	py::make_tuple(sizeof(float)*FEATURENUM*H*W, sizeof(float)*H*W, sizeof(float)*W, sizeof(float)),
	py::object());

auto result_object = predict(features);
np::ndarray result = py::extract<np::ndarray>(result_object);

のようにして4次元Tensorを作成して、Pythonの関数の引数に渡し、結果をndarrayで受け取れる。

計測

上記の実装方法で、Chainerで実装した将棋の指し手を予測する方策ネットワークを呼び出すプログラムを作成し、処理時間を計測してみた。

predict call 1000 times
8480[msec]
8.48[msec per each call]
117.925[nps]

昨日Pythonで計測したときは、140npsだったので、スループット(nps)が落ちている。
C++からPython呼び出しのオーバーヘッドが発生している。

オーバーヘッド計測

オーバーヘッドを計測するため中身のない処理をC++から呼び出した場合の、処理時間を計測した。

dummy call 100000 times
7[msec]
7e-05[msec per each call]

無視できる程度の時間しかかかっていない。
引数、戻り値が一切ない処理の場合は、ほとんどオーバーヘッドはないようだ。

次に、引数と戻り値を方策ネットワークと同じにして、処理をなくしたもので計測してみた。

dummy2 call 1000 times
15[msec]
0.015[msec per each call]

今度は、1000回の呼び出しで15msec、1回あたり0.015msecかかっている。
言語間の変数のバインディングにオーバーヘッドがあるようだ。

ただし、方策ネットワークの実行時間が1回あたり8.48msecなので、それほど気にする必要はなさそうだ。


処理時間の計測には、以下のコードを使用した。
github.com

将棋でディープラーニングする その31(DNNのスループット)

方策ネットワークを対局中に用いた場合のスループットを計測した。

PUCTアルゴリズムで並列で探索をする場合、複数スレッドからGPUを使用するため、複数スレッドから使用する場合を考慮する。

まず、それぞれのスレッドからDNNを実行した場合について計測した。

測定条件

測定条件は以下の通り。

  • 12層、フィルターサイズ3×3、フィルター192枚、入力85枚、出力8181クラスのDNN(Wide ResNet)
  • バッチサイズ 1
  • 1000回ループして処理した時間を計測
  • 3回測定して平均をとる

測定結果

測定結果は以下の通りとなった。
f:id:TadaoYamaoka:20170605111559p:plain

複数スレッドから実行するとスレッドが増えるほどスループットが落ちている。
GPUは同時には利用されず、どこかで排他制御されていると思われる。
複数スレッドからの要求をキューにためておいて、1スレッドから利用した方がよいと言える。

バッチサイズを増やした場合

次に、1スレッドから利用して、バッチサイズを増やした場合について計測した。
f:id:TadaoYamaoka:20170605111855p:plain

バッチサイズが増えるほど線形にスループットが伸びている。
これは、GPU内で並列化が行われ、バッチサイズによらず実行時間が同じになるためと思われる。

NPSについての考察

バッチサイズを4にしても、NPSは560程度であり、将棋プログラムのNPSに比べて圧倒的に少ない。
i7 6700K(4コア4GHzのCPU)でやねうら王2017 Early(SSE42)を動かすと、NPSは3,564,673出ている。

Ponanza Chainerが行っていたように、DNNの実行と並列で従来プログラムで探索を行う方が効果的かもしれない。

PUCTアルゴリズムと従来のプログラムを組み合わせるには、以下のような方式が考えられる。

  • 方策ネットワークの出力がでるまでは、評価関数の値を事前確率として使用する
  • バリューネットワークの出力が出るまでは、評価値の値を使用する
  • 方策ネットワークの出力がでたら、評価関数の値と平均をとる
  • バリューネットワークの出力がでたら、評価値の値と平均をとる

実装が大変そうなのと、期待外れ度を知るのも意味があるので、まずDNNのみを用いてPUCTの実装を試したい。


スループットの計測には以下のコードを使用した。
https://github.com/TadaoYamaoka/DeepLearningShogi/blob/master/utils/throughput.pygithub.com

Ray+Rnのソースを調べる

将棋プログラムでPUCTアルゴリズムを試すため、囲碁プログラムのRayを元にCNTKを使って、ディープラーニングに対応させたRnのソースを調べています。
RnはPUCTアルゴリズムを実装しているので、参考になります。

以下、Windowsでビルドして、ソースをステップ実行するまでの手順です。

ビルド環境

  • Windows Home 64bit
  • Visual Stuido 2015 Community

CNTKダウンロード

以下のサイトからCNTK2.0をダウンロードする。
Releases · microsoft/CNTK · GitHub
Windows→CNTK for Windows v.2.0 GPU
のリンクからダウンロードする。

ダウンロードした「CNTK-2-0-Windows-64bit-GPU.zip」を任意のフォルダに解凍する。

環境変数PATHに
(CNTKを解凍したフォルダ)\cntk
を追加する。

Rnのソースをgit clone

Rnのソースをgit cloneする。

git clone -b nn https://github.com/zakki/Ray

プロジェクトのパス修正

Ray\win\ray\ray.vcxprojをテキストエディタで開く。
「C:\programs\CNTK-2-0-beta12-0-Windows-64bit-GPU」をCNTKを解凍したフォルダに置換する。

「EvalDll.lib」を「Cntk.Eval-2.0.lib」に置換する。

ビルド

Ray\win\ray.slnをVisual Studio 2015で開く。

デバッグビルドだとCNTKが動かなかったため、Releaseビルドにする。
Releaseビルドでは最適化されているため、ステップ実行が行いにくい。
そこで、プロジェクトの構成をコピーして、Release_NoOptを作成し、プロジェクトの設定で、C/C++→最適化を無効(/Od)に設定する。

プロジェクトの構成をRelease_NoOpt/x64にする。

ソリューションをビルドする。

Ray\win\x64\Release_NoOpt\ray.exeを
Rya\直下にコピーする。

GoGuiで実行

GoGuiをダウンロードしてインストールする。
GoGuiを実行し、ray.exeをプログラムに登録する。

プログラムを起動する。

プロセスにアタッチしてデバッグ

Visual Studioで、デバッグ→プロセスにアタッチを選択し、ray.exeにアタッチする。

ソースを調べたい箇所にブレークポイントを設定する。

UCTで探索を行っている箇所は、UctSearch.cppのParallelUctSearchあたりとなる。

CNTKで方策ネットワークを実行しているのは、UctSearch.cppのEvalPolicyあたりとなる。

PUCTのUCB値を計算しているのは、UctSearch.cppのSelectMaxUcbChildあたりとなる。

対局を開始する。
ブレークポイントで止まるので、ステップ実行してソースを調べる。

それぞれ別スレッドで動いているので、デバッグ→表示→並列スタックで、各スレッドのスタックトレースを見るとよい。
f:id:TadaoYamaoka:20170604155838p:plain