作成者別アーカイブ: threecourse

ライブラリのコードを理解するための環境整備

はてなブログに引っ越しましたので、そちらをご参照下さい
https://threecourse.hatenablog.com/entry/%3Fp%3D1186

=================

目的

xgboost等のPythonからC++を呼び出すライブラリの理解のため、printデバッグや改造をできるようにする

環境

Windowsなので、GCPでlinuxのインスタンスを立ち上げる。
CLion/Pycharmのリモート機能を利用する。(ローカルの方が楽だけどやむを得ない)

やること

1. コードを落とし、C++でコンパイルできることを確認する

git clone –recursive https://github.com/dmlc/xgboost
cd xgboost; make -j4

2. 読むべきPythonコード/C++コードのフォルダを確認する

xgboostの場合は以下のフォルダ。
Pythonコード: python-package
C++コード: src, include
どうやって読むべきフォルダを確認するか良く分からないのですが、Makefileを読む/雰囲気くらいか。

3. (pipなどでインストールしたものでない)対象のPythonライブラリを呼び出す

呼び出し元となるpythonスクリプトを作り、そこで
import sys
sys.path.insert(0, my_library_path)
とすると、対象のパスから優先的に読み込むことができる。

4. (pipなどでインストールしたものでない)対象のC++ライブラリを呼び出す

どのようにPythonからC++ライブラリを呼び出すかをまず確認する。
xgboostの場合は、python-package/xgboost/core.pyの_load_libメソッドでctypes.cdll.LoadLibraryにより呼び出している。
ここでライブラリのパスはpython-package/xgboost/libpath.pyのfind_lib_pathメソッドで取得している。
対象の相対パスは含まれているので、pipなどでインストールしたライブラリが読み込まれないよう、dll_path = dll_path[:-1]などとすれば良い。

5. 動作確認

確認対象のpythonモジュールが読み込まれているか、C++ライブラリが読み込まれているかをprintやstd::coutを差し込むことで確認する。


マラソンマッチの資料集

はてなブログに引っ越しましたので、そちらをご参照下さい

https://threecourse.hatenablog.com/entry/%3Fp%3D1164

============================

マラソンマッチ勉強会の予習ということで、少しまとめてみました。(2018/8/14 資料追加)
リンクはちょっと探した限りなので、他にもあったら教えて下さい。

全般

手法

他にもいろいろありそうですが、

  • いろんな探索(幅優先探索、深さ優先探索)、局所探索
  • 山登り、焼きなまし
  • 貪欲法
  • ビームサーチ
  • chokudaiサーチ

(参考)

ヴィジュアライザ

具体的にどのコンポーネントやフレームワークを使うのがいいのかな?

  • .NETのSystem.Drawingとかでぽちぽち書いていく
  • Siv3D
  • HTML + JavaScript

(参考)

過去問(と解法)

過去問とその解法をいっぱい持っておくことは役に立つと考える。

月刊: Kaggleは役に立たない

Kaggle Meetupのネタにでも、ふわっとした文章を書いてみる。
個人の意見です&ここ1-2年の状況変化は追えていないかも。

(追記:タイトルは「月刊競技プログラミングは役に立たない」という競プロ方面のネタから来ています)

どうでもいい技術、どうでもいくない技術

Kaggleで勝つための技術を書き連ねてみる:

  • Python, R, ライブラリの使い方
  • 特徴量の作成
  • データについての考察、EDA
  • モデルの使い方、パラメータチューニング
  • 評価指標についての考察
  • DiscussionやWinner’s interviewを読む英語力
  • 柔軟に作業や分析を回すためのクラス・ワークフロー・ログなどの実装
  • GCP, AWS, BigQueryといったサービスの運用
  • 論文を読んで手法を参考にしたり実装したりする力
  • 折れない心

改めてまとめてみると普通に学んで損のないものばかりな気がしてきた。

ただ、実際には、

  • 脳みそを空っぽにしていろんなモデルや特徴量を作ってアンサンブル
  • たくさんランを流してxgboostのscoreの流れをぼーっと眺める
  • 画像コンペでのトレーニングデータへのラベリング

とか、何やってんだろと思うこともあるのは確か。

Bestfitting氏のインタビュー

Profiling Top Kagglers: Bestfitting, Currently #1 in the World

現在のKaggle User Ranking 第1位のBestfittingのインタビュー。
ちゃんと自分を律しているなぁという印象。
人によって興味深いポイントはそれぞれだが、個人的にはコンペを始める前に類似のコンペのSolution(にとどまらず論文まで)をおさえることをきっちりやっているのは偉いと思った。
(どうやってその時間を捻出するのだろう…)

競プロとの違い

以下のTweetが本質を突いているのかなと思った。

私としては、

競プロ(特にアルゴリズム)

  • 「純粋」な印象。範囲が定められているが、深度が要求される。
  • 強い人には絶対かなわない感がある(逆に競プロが強い人がKaggleにアジャストすると楽に勝てるイメージ)

Kaggle

  • 「複線的」でいろんな方向から攻めなくてはいけない印象。
  • 実世界への適用が意識されている
  • 実力差があっても、攻め方や頑張りや運でワンチャンある感じ。

Kagglerは仕事ができる説

「Kagglerは仕事ができる」とか吹いても良いんじゃないかと思った。

  • 複線的でいろんな技術が要求される
  • どのモデルやどの特徴量から作るか、手元のCVスコアとPublic LeaderBoardのスコアが合わないときに何を疑うか、手を動かすのか情報収集をするのか、優先順位をつけて攻めていく必要がある
  • 計算時間やメモリ使用量だけでなく、睡眠時間や現実でのお仕事の状況を含めたリソース管理が要求される

楽しみ方はいろいろ

“ガチ勢”はgold medalを基本目指していると思いますが、他にもいろいろと楽しみ方はある。

金メダルを目指す

競技者としては、ここがベースになりそう。
ほぼ金メダル=Kaggle Masterであり、対外的にもなんか強そうな印象を与えられる。
hard workを積み重ねないとgold medalには届かないのはメルカリのceremonyでも共通意見だったか。
(たまにラッキーパンチが入るという噂もある)

銀メダルを目指す

そこまでガチではなく、単純に学びたいとか、データ分析と違う業種にいるけど実力を示したいとか、という場合には銀メダルを目指すのが良いと思う。
実力証明としては、銀メダル(できたら複数)で十分価値はありそう。
学びの場としても、ここに至るまでが一番費用対効果が高そう。

beat the benchmarkを自力で超えられる力をつける

銅メダルは入るための基準がコンペによってまちまちな印象があるので、これを目指すというのはあまりお勧めしないかも。
どのコンペでも大体誰か優しい人がbeat the benchmark(以下btb)と言われる、基本的なモデリングを行ったSolutionをKaggle Kernelに上げてくれるのですが、
銅メダルを目指すよりは、btbを自力で超えられる力をつけるということを目指して結果として銅メダルなどがついてくる方が良さそう。

上の順位を目指さない

こんな感じで、興味や軸をずらして参加してみるのもあり。

  • 可視化、EDAに絞ってkernelを眺めてみたりまとめてみる
  • 特定のモデル・ライブラリについて深く追う
  • Winners’ Interviewで人間ドラマを追う
  • Datasets AwardやKernels Awardを目指してみる

AOJ本の基本問題集

最近はatcoderの黄色を目指すべく、競プロの問題を解いています。
atcoderの過去問なども解いていますが、基本問題を整理しておきたいと思ったので、プログラミングコンテスト攻略のためのアルゴリズムとデータ構造をやっていました。

AOJ本の例題には、競プロには直接役に立ちづらいもの(stackの実装とか)もあるので、競プロに役立ちそうな基本問題をまとめてみます。

概要 問題番号
5 二分探索 ALDS1_4_B
6 DFS(組み合わせ列挙) ALDS1_5_A
11 DP(フィボナッチ) ALDS1_10_A
11 DP(連鎖行列積) ALDS1_10_B
11 DP(最長共通部分列) ALDS1_10_C
12 グラフDFS ALDS1_11_B
12 グラフBFS ALDS1_11_C
13 単一始点最短経路-ダイクストラ ALDS1_12_C
14 UnionFind DSL_1_A
15 全点対間最短距離-ワーシャルフロイド GRL_1_C
15 最小全域木-クラスカル法もしくはプリム法 GRL_2_A
15 単一始点最短経路-ベルマンフォード GRL_1_B
16 幾何 CGL_1_A, CGL_1_B, CGL_1_C
16 幾何 CGL_2_A, CGL_2_B , CGL_2_C, CGL_2_D
17 DP(コイン) DPL_1_A
17 DP(ナップサック) DPL_1_B
17 DP(最長部分増加列) DPL_1_D
17 DP(最大正方形) DPL_3_A
18 最大公約数 ALDS1_1_B
18 エストステネスの篩 ALDS1_1_C
18 繰り返し2乗法 NTL_1_B
19 ヒューリスティクス(8クイーン) ALDS1_13_A
19 ヒューリスティクス (8パズル) ALDS1_13_B

ユニクロコン 実装編

オプトのユニクロコンペ(https://deepanalytics.jp/compe/36?tab=compedetail)について、もう少し実装のマニアックな話をしてみます。
コードはhttps://github.com/threecourse/opt-uniqlo-publicに上げています。

コードのインターフェイス

データ分析コンペ用のモデル構築用のクラスをどう作るかは長年の課題だったのですが、少しずつ固まってきました。

いろいろ考えた末、ベースとなるクラスはModel, Runnerに2つに分けた。

  • Modelはsklearnの各モデルをwrapするイメージ
  • Runnerは訓練や予測やクロスバリデーションなど一連の計算のもろもろ
  • 結構良い感じで、わりとモデル追加、クラスの拡張の際にストレス無くできた。
  • sklearnのインターフェイスがあまりしっくりこないのと、hyperoptに合わせたいこともあり、sklearnのベースクラスの継承はしていない。
  • データの読み込みをRunnerに持たせているが、微妙かもしれない。Modelに密接に結びついているので、そちらに定義させた方が良いかもしれない。
  • どう頑張っても時にはダーティーにやらなくてはいけないことがあるので、その時は諦める。
  • 型ヒントが効くようにちゃんとdocstring書いた方が良いかもしれない。

Model

  • Modelクラスはmodel.pyに定義。
  • 入力は、モデル名(とfold名)・データ・パラメータなど。
  • 責務は、訓練・予測・モデルの保存・モデルの読み込みなど。
  • 各foldごとに1つモデルのインスタンスが作成される。
  • baggingなどもこの中で処理することができる。

主なメソッドは以下のとおり。

シグネチャ 概要
__init__(run_fold_name) モデル名(とfold名)がないと不便。
train(prms, x_tr, y_tr, x_te, y_te) パラメータとtrainのx, yとvallidationのx, yを入力とし、モデルの訓練を行う。
train_without_validation(prms, x_tr, y_tr) パラメータとtrainのx, yを入力とし、モデルの訓練を行う。trainの全データで訓練したいとき用。
save_model() モデルを保存する。
load_model() モデルを読み込む。
predict(x_te) testやvalidationのxを入力とし、訓練されたモデルから予測値を返す。

Runner

  • Runnerクラスもmodel.pyに定義。
  • 入力は、モデル名・入力データのリスト・パラメータなど。
  • 責務は、データの読み込み、インデックスの読み込み、クロスバリデーションでの訓練(精度の出力も含む)、訓練されたモデルを使ってのテストデータの予測、hyperopt用の精度の出力など。
  • データの読み込みは単にファイル名の指定だけでなく細かく修正することが多いので、Runnerでそこだけ調整できるのは便利。
  • インデックスは複数に対応するようにしておかないと、後で面倒。
  • ログとクロスバリデーションの精度を標準出力とファイルに出力。
  • 動作確認用に少ないデータで流せるよう設計しておけば楽なのだが、対応が面倒なのであまり出来ていない。

主なメソッドは以下のとおり。
各Runnerで定義が必要なのはbuild_model, load_x_train, load_x_test。
ランなどで外部から使用する必要があるのはrun_train, run_test, run_hoptあたり。

シグネチャ 概要
__init__(run_name, flist, prms) モデル名、特徴量名(list)、パラメータ(dict)のセット。
build_model(run_fold_name) 使用するModelの定義。
load_x_train() trainのxの読み込み。
load_x_test() testのxの読み込み。
load_y_train() trainのyの読み込み。
load_w_train() trainのweightの読み込み。weightを変えて訓練したい場合に。
load_index_fold(i_fold) cv用インデックスの読み込み。(trainのidx, validationのidx)を返す。5foldの場合、基本はi_foldに0-4が入る。違うcv用インデックスで計算したい場合、”a0″や”a4″のように指定する。
load_x_fold(i_fold) foldを指定したxの読み込み。(trainのx, validationのx)を返す。
load_y_fold(i_fold) foldを指定したyの読み込み。(trainのy, validationのy)を返す。
load_w_fold(i_fold) foldを指定したweightの読み込み。(trainのweight, validationのweight)を返す。
train_fold(i_fold) 指定したfoldでの訓練を行い、訓練されたモデルを返す。
run_hopt(i_fold = “a0”) hyperopt用。指定したfoldでの訓練を行った後に、loss(と訓練されたモデル)を返す。
run_train() クロスバリデーションでの訓練を行う。とりあえず5cv固定。各foldのモデルの保存、精度のログ出力についても行う。
run_test() クロスバリデーションで訓練した各foldのモデルの平均により、testのyの予測を行う。
run_train_alltrain() trainの全データで訓練し、そのモデルを保存する。
run_test_alltrain() trainの全データで訓練したモデルにより、testのyの予測を行う。

パラメータチューニング

パラメータチューニングはhyperoptを用いて、5cvのうちの1foldのみで行い、メインの計算とは別のcv用インデックスで行った。
また、fit_generatorにより1epochを3000枚程度に小さくし、patience=3のearlystoppingで行った。
なお、訓練時はhyperoptの結果を元にepochを固定した。

  • コードはhopt/hopt_resnet.pyなどを参照。
  • 計算時間に余裕があり、精度のばらつきが激しい場合は5cvなどで評価した方が良いが、neural netだと計算時間はさすがにきつい。
  • 同じインデックスだと、hyperoptに使ったfoldだけoverfitすることがあるので、stackingを行う場合にちょっと気になる。気にし過ぎかもしれない。
  • epochをそのままだと、patience=3だとかなり行き過ぎてしまう感じ。
  • epochを固定するのではなく、early_stoppingでsave_best_onlyを使う方法もあるかもしれない。

kerasのジェネレータ、data augmemtation

頑張った。kerasのImageDataGeneratorは、場合によっては少し手を加えないと使いづらい。

  • コードはmodel_keras_util.py, model_keras_util_augmentation.pyなどを参照。
  • 汎用のジェネレータがサポートされていないようだったので、keras.preprocessing.imageのIteratorなどを参考に作成。
  • data augmentationも、ImageDataGeneratorを元に切り貼りして作成。

ログ

  • コードはutil_log.pyを参照。出力はlogフォルダを参照。
  • ログを標準出力とファイルの両方に出力するようにする。
  • 時間の情報を付加することにより、なんとなく時間のかかっている処理がわかる。
  • 一般的な情報とクロスバリデーションの精度の情報の2つに分ける。
  • クロスバリデーションの精度の情報はltsv形式で出力しておく。時々util_result.pyをランすることでモデルごとにまとめる。

ヴィジュアリゼーション、分析

  • コードはanalyzeフォルダを参照
  • 背景領域を0, それ以外を1としてベクトル化し、kmeansクラスタリングを行った。画像が整えられているので、単純だが結構きれいに商品カテゴリごとに分けられる。
  • 巡回サラリーマン問題を解いてカテゴリ間の距離が最小になるように並べた。近いカテゴリが近くにくるので見やすい。
  • カテゴリごとに画像・正解ラベルを並べたpdfを作った。(運営からの許可が出てないのでpdfはアップロードしてません)
  • どうもipython notebookは自分に合わなく、pdfを生成することが多い。

ユニクロコン 手法編

オプトのユニクロコンペ(https://deepanalytics.jp/compe/36?tab=comperank)に出ていました。
public 4th -> private 4thという結果で、運次第では賞金圏内もあったと思うので切ないですね。

0. 概要

基本データ

  • ユニクロの商品の色(24クラス)を判別する課題
  • Train:12399, Test:9801
  • 背景はちゃんと切り抜いてくれているので、わざわざwatershedなどで背景抽出をする必要が無い

課題

  • 色の判別はやや単純すぎる課題で、本来はCNNを使うのはオーバーキルな感じもある。
    ただ、後述のラベリングの微妙さも相まってコンペとしてはある意味おもしろい。
  • ラベリングが微妙。もはやどっちが正しいのかわからないの多数。特に3連靴下はなんだこれ。
  • 分析すると、女性物は同じような色でもオフホワイトになりやすかったり、ラベリングは服の種類に影響を受けていることがわかる
  • このコンペは色を判別するコンペではなく、人間がどのように色コードを設定するかを判別するコンペといえる。
  • train/testはrandom splitではなく、商品ラインごとのsplitをしている様子。
    なので、やりすぎるとtrainデータへのoverfitの危険もある

評価指標

  • balanced accuracyであることがポイント。比率の少ないものを間違えるとペナルティが大きい。
    完全に正しい確率を予測できているとするならば、確率÷正解ラベルの比率が最大となるものを予測するのが適切。
  • trainingデータのweightを変える方法も試したが、通常のweightで分類し上記の調整を行う方が精度が高かった。
  • balanced accuracyは安定しない、accuracyが良くても2番手以降の評価がいまいちだとスコアが出ないので、loglossを下げることに注力。

1. 特徴量抽出、分析

クラスタリングを少し試したが、結局モデリングには適用していない。

  • シルエットによるクラスタリング
    背景領域を0, それ以外を1としてベクトル化し、kmeansクラスタリング。
    画像が整えられているので、単純だが結構きれいに商品カテゴリごとに分けられる。

  • 分析、ヴィジュアライゼーション
    カテゴリ間の距離が最小になるように並べる(巡回サラリーマン問題を解く)と、近いカテゴリが近くなるので見やすい。
    カテゴリごとに画像を並べたPDFを作ったり、カテゴリごとの色の分布・正答率を見たりした。

  • 接続領域での分離
    繋がっている領域が何個あるかを求める(DFS)。3連靴下とかを綺麗にわけることができる。

  • その他
    SIFT、カラーヒストグラム、pretrained modelで予測したimagenetのカテゴリとか考えたが、結局使っていない。

2-1. モデリング

  • ニューラルネットのライブラリはkeras
  • ファインチューニングとスクラッチからのCNNの両方を行った。
  • テストデータには、5cvの平均を適用するようにした。
    ニューラルネットだと、trainの全データを使うとvalidation scoreが見れないので怖い。
  • パラメータ調整はhyperopt。ネットワーク構成、learning rate、optimizerの選択に大変役に立った。
  • 単発だとかなりぶれるので、10-20回回した平均をとった。
  • オプティマイザは、ファインチューニングはmomentum sgdで良さそうですが、スクラッチではadamが有効だった。
  • スクラッチから作る場合は、序盤に1*1フィルタを適用するモデルの精度が良かった。
  • 1epochで10000枚回すとearly stoppingの際に行き過ぎてしまうので、generatorを使うことで1 epochの枚数を制御した。
  • data augmentation, test-time augmentationを行った。
    左右反転・少し回転・少し拡大縮小させた。
    kerasのImageGeneratorは専用実装になっており、取り入れにくかったので、適宜コードをつぎはぎした。

2-2. 作成したモデル

ファインチューニング

  • vgg16
  • vgg16, augmentationあり
  • resnet
  • resnet, augmentationあり

スクラッチからのCNN

  • cnn1-5 : 序盤に1*1フィルタを適用したCNN(5種類)、augmentationあり
  • cnn0 : 1*1フィルタのみでピクセルの場所の情報を全く使用しないCNN

ネットワーク構造は以下のような感じ。怪しい。
Conv2d(filter=1 * 1) -> Conv2d(filter=1 * 1,stride=2) -> BN -> Maxpooling(2 * 2) ->
Conv2d(filter=2 * 2) -> Conv2d(filter=2 * 2,stride=2) -> BN -> MaxPooling(2 * 2) ->
Dense -> BN -> Prediction

各モデルのローカルのスコア(10-20個混ぜている)は以下のとおり。

model logloss balanced acc accuracy
vgg16 0.6876 0.7004 0.7695
vgg16_aug 0.6969 0.6910 0.7685
resnet 0.6687 0.6975 0.7747
resnet_aug 0.6462 0.7005 0.7809
cnn1-5 0.6548-0.6743 0.6993-0.7116 0.7672-0.7732
cnn0 0.7396 0.6624 0.7443

3. Ensemble、調整

  • 各モデルの加重平均をとる。
    加重平均を取る際には、loglossが最小になるような係数を探し、適用する。
  • スタッキングを行う。クラスが多いためか、スタッキングをしたモデル自体の精度はあまり良くない。
    スタッキングをしたモデルとの加重平均をとることで少し精度が上がる。
  • 最後の仕上げでloglossが最小になるように確率をn乗したり、色の比率のn乗を乗じた。
    この辺はいろいろやり方がありそう。

各モデルのローカルのスコアは以下のとおり。

model logloss balanced acc accuracy
加重平均 0.6154 0.7199 0.7880
スタッキング 0.6311 0.7154 0.7815
上2つの加重平均 0.6120 0.7213 0.7882
調整後 0.6069 0.7217 0.7874

機械学習系コンペの意義

参加者にとっての意義

  • 機械学習のスキルアップ
    特徴量作成、モデリング、可視化など
  • エンジニアリング技術のスキルアップ
    コードの構造化、awsの利用など
  • スキルの客観的評価
  • 賞金
    モチベーションや質を担保する要因の一つだが、賞金自体は割に合わないでしょう
  • 楽しさ
    価値があるから楽しい、楽しいから高いレベルの人が集まって価値がある、の循環

参加者のつらみ

  • かなりの体力と精神力を費やすことになる(週8時間で良い順位をとるのは厳しい)
  • 精度が出ない、順位が上がらない
  • 頑張ってもkaggle master連合軍や500 model stackingに負けるとつらい
  • leakなど、あまり意味のないソリューションを頑張んなきゃいけないことがある

スポンサーにとっての意義

  • リクルーティング
  • 宣伝効果
  • 良い知見やソリューションの獲得
    • モデリング
    • データに関する知見、良い特徴量
    • 可視化手法

良い知見やソリューションを獲得できるかは分の良くない賭けである気がする(後述)

そのほかの意義

  • 効果的でわかりやすいツールや手法を広める役割
    xgboost, stacking, keras, t-sne など

データセットとソリューション

  • 機械学習系コンペは問題設定が難しいように思う
  • 理想は実務に役立つ、知られざる知見を得ることだが、そんなものが都合よくあるとは限らない
  • 印象に残っているソリューションはTaxi Trajectory PredictionNOAA Right Whale Recognition。これらは実際に役に立ちそう。
  • 一方で入賞者のソリューションが何の役にも立たなそうなコンペもある
  • 純粋に技術を競うのなら、人工的なデータセットを作ってそれの”謎を解く”方がよいのかもしれない。ただ、それでは機械学習の実世界との関わり感が失われてしまう

train/test split、データ量

  • trainとtestが均一なsplitでデータ量が十分にある場合、評価指標にもよるが、多数のモデルによるstacking競争になる可能性がある。ただ、ひたすらcross validation scoreを高めることに注力できるので、スキルアップには良い。
  • trainとtestが均一でない場合(時系列データやtrain/test splitが何らかのグループで分かれている場合)は、stacking競争になりにくいが、train/testの違いを考察したり、LBに投げてみて良いスコアを探すなどが必要なケースがある。下手すると運ゲーになることもある。

どんなコンペがやりたいか?

個人的に一番楽しそうなのは強化学習を用いたAIの対戦ゲーム。
codingameはローカルで流せないようなのと、UIがちょっと見た目重視過ぎる気がするのがいまいち。
code vsが求められている?

CartPoleをやってみる

openAI gymのCartPoleを強化学習で解いてみました。
https://gist.github.com/threecourse/3b428c70c8fad43472affc6ede0b4e9f

  • 以下の記事を元に、まずはcartpoleから始めて見ました。理論的な解説はそちらをご参照下さい。
    https://elix-tech.github.io/ja/2016/06/29/dqn-ja.html
  • 理解しようと思ってリファクタリングした。TensorFlowの書き方が良くわからなかったので結局全部kerasで書いた(書けた)
  • kerasのactionごとのq_valueを統合するところで苦労した。2次元だとmerge(mode=”dot”)が効かないらしく、merge(mode=”mul”)からのsumでどうにかした。
  • CartPoleといえども適当にやると上手くいかない。
  • いろいろ間違ってるかもしれません。

AlphaGoのお勉強

http://www.slideshare.net/yuk1yoshida/alphago-61311712
は大変分かりやすいスライドなのですが、AlphaGoがなぜそういう設計になっているのかわからなかったので原文を読んでみました。
(スライド中のvk.comから取っていいのかな・・?)
以下は自分の解釈ですが、上記スライドをかなり参考にしています。

学習しておく関数

a. ポリシー関数

P(a|s) = 盤面sにおいて手aを打つべき確率

a-1. rollout policy(p-pai)

  • 線形softmax、高速
  • 人間による8M盤面より学習
  • rollout時の確率として使用

a-2. tree policy(p-tau)

  • 線形softmax、高速
  • rollout policyより特徴量が多い
  • 人間による8M盤面より学習(?)
  • 木の展開時にpolicy networkが計算されるまでの仮値として使用

a-3. policy network(p-sigma)

  • neural network、高精度
  • 人間による28.4M盤面より学習
  • 木の展開時の事前確率として使用(探索時の優先順位に影響)

b. バリュー関数

V(s) = 盤面sの評価値(-1~1)

b-1. value network(v-theta)

  • neural network
  • 盤面の評価値
  • 生成された30M盤面より学習

memo

  • なぜrollout policyとtree policyを分けるのかは良くわからない。
  • 強化学習においてp-rhoを学習するが、それはvalue networkの学習に用いるだけで対戦には使用しない。
    p-paiの方が多様性が高くモンテカルロ探索には良いとのこと。
  • value networkの学習では、同じ局から盤面をとってきてしまうとover fittingしてしまうので、それぞれ別の局から盤面をとってきている。

MCTS(Monte Carlo tree search) のアルゴリズム

ルートノードおよび合法手をエッジとする木から開始する

  • エッジは事前確率・value network計算回数・rollout計算回数・value newwork評価値の積算・rollout結果の積算を保持する
  • 事前確率はpolicy networkをセットする

各スレッドは以下のように探索する

  • 1 ルートノードからQ+uの大きいものを選び木を下ってリーフ(エッジがまだ展開されていないノード)まで到達する
    • Qはvalue networkの値とrollout結果の平均
    • uは事前確率と探索回数による、探索を広く行うための項
  • 2-1 リーフ到達時に、まだ評価されていない場合はvalue networkの評価を依頼する
    • value network終了時に評価を伝播させる
  • 2-2 リーフ到達時に、ロールアウトを行う
    • ロールアウト終了時に評価を伝播させる
    • rollout中は一時的に評価を下げておき、他のスレッドから探索されづらくする
  • 3 あるエッジのrollout回数が閾値(=40)を超えた場合、その直下のリーフを展開する
    • 事前確率はtree policyを仮にセットし、policy networkの計算が終わったら置き換える
    • policy networkの値をsoftmax temperatureで調整し、メリハリを強くしている

最終的に、rollout回数の最も多い手を選択する

  • 評価値の最も高い手より外れ値に頑強

memo

  • CPUのスレッドの他、value network用のGPUのキュー、policy network用のGPUのキューがあり(?) 、非同期に評価が行われる
  • value networkの評価の順序は良くわかりませんが、きっとうまく評価の高そうな順に行うようになっているのでしょう。
  • policy networkの評価が追いつくように、リーフ展開の閾値を動的に調整する
  • 評価の伝播は単純に勝敗・評価値・探索回数をルートノードまでさかのぼって加える。
    探索確率はpolicy network/Value Network/rollout結果によるため、評価値はそれなりに良い手の加重平均となる。
    評価値のmaxをとるわけではないのが面白いところで、囲碁を確率論的なものとしてとらえているように思える。
  • 評価が非同期に更新されていくので、良い感じに探索するパスが分散される

感想

  • neural networkや強化学習が重要な役割を果たしているのは確かだが、
    特徴量からの線形softmaxやモンテカルロ木も同じくらい重要そう。
  • 論文を元に実装しようとしているgithubもあるようです。
    https://github.com/Rochester-NRT/RocAlphaGo