elmoのアピール文書を読む - TadaoYamaokaの開発日記

世界コンピュータ将棋選手権で優勝したelmoのアピール文書を読んでいますが、結構難しいです。

勝率が二項分布に従う場合、評価値はロジスティック分布に従う(※1)だろう、
ということでロジスティック回帰を適用しています(※2)。

この部分は、ある局面の勝敗は評価関数の値によって決まる確率分布に従うという仮定を置き、評価値が与えられた時の事後確率をロジスティック関数で表すということだと思います。
勝敗が評価値によって決まる確率に従うならば、ベルヌーイ試行に従うので勝率は二項分布になります。

ロジスティック関数は、以下の式で与えられる値の範囲が0～1の関数で、入力値が大きければ1に近づき、入力値が小さければ0に近づきます。

$\displaystyle \sigma(a) = \frac{1}{1+\exp(-a)}$
$\bf a$ は評価値で、3駒関係の重みを $\bf w$ 、学習データの3駒関係の入力ベクトルを $\bf x$ としたときの線形和 ${\bf w}^T{\bf x}$
※多くの将棋ソフトでは歩1枚の価値がだいたい100点になるように横軸をスケーリングしているようです。
f:id:TadaoYamaoka:20170506123454p:plain:w300

人間が評価値が1000を超えたあたりからほぼ勝ちだと判断する感覚とも一致するので、評価値による勝率がロジスティック関数に従うと仮定するのは納得がいきます。

局面の勝敗結果から、機械学習の最尤推定という手法で、損失関数（交差エントロピー誤差関数）を最小化するように学習することで、評価関数のパラメータを最適化できます。

交差エントロピー誤差関数は以下の式で表されます。
$\displaystyle L({\bf w}, {\bf X}, {\bf t}) = -\sum_{i=1}^{N}(t_i{\bf w}^T{\bf x_i} - \log(1+\exp({\bf w}^T{\bf x_i}))$
$\bf X$ は学習データの集合 $({\bf x_1}, {\bf x_2}, \cdots)$ 、 $\bf t$ は勝敗(0か1)の教師データです。
交差エントロピー誤差関数をパラメータ $\bf w$ について偏微分すると
$\displaystyle \frac{\partial L({\bf w}, {\bf X}, {\bf t})}{\partial {\bf w}} = \sum_{i=1}^{N}{\bf x_i}(\sigma({\bf w}^T{\bf x_i}) - t_i)$
となり、計算がしやすい式となります。

アピール文書では、これに正則化項を加えています。

単純に最尤推定のロジスティック回帰を適用するのではではなく、
正則化項として深い探索結果を浅い探索結果にフィードバックする手法(※3)を採用しています。

交差エントロピー誤差関数に、その局面の深い探索結果による評価値を加えることで、その評価値に近づける正則化を行っています。
$\displaystyle L'({\bf w}, {\bf X}, {\bf t}) = L({\bf w}, {\bf X}, {\bf t}) + \lambda R({\bf X})$
$\lambda$ は正則化係数、 $R({\bf x})$ が浅い探索による評価値と深い探索による評価値の誤差

さらに、正則化項に以下の変形を加えています。

正則化項には、第4回電王戦トーナメントの†白美神†さんが利用していた同様交差エントロピー(※4)を利用しています。
これは単にロジスティック回帰の損失項が交差エントロピーを使うのが普通なので
両項のオーダーを合わせる意味で利用しています。計算簡単で直感的に値が分かりやすい点も良いです。

つまり、以下の式になります。
$\displaystyle \begin{eqnarray*} L'({\bf w},{\bf X}, {\bf t}) &=& L({\bf w},{\bf X}, {\bf t}) + \lambda H({\bf p}, {\bf q}) \\ H(p, q) &=& - \sum_t p(t) \log q(t) \\ &=& -p \log q - (1 - p) \log(1-q) \end{eqnarray*}$
pは評価値からの勝率、qは深い探索の評価値からの勝率、H(p, q)は2確率変数の交差エントロピー

H(p, q)の偏微分は、
$\displaystyle \frac{\partial H(p, q)}{\partial {\bf w}} = {\bf x_i}(q - p)$
となる。
H(p, q)の微分の式の展開の詳細は、引用されている資料参照
ロジスティック関数の微分が $\sigma'(a)=\sigma(a)\sigma(1-a)$ であることを利用している。

学習データに使用するのは、ある局面からの浅い探索結果と深い探索結果の評価値と勝敗のデータになります。

1エポック分パラメータを更新した後、自己対戦により再度学習データを生成する必要があるので、何エポックも学習を回すのはかなり大変そうです。

elmoは、アピール文書では探索深さ6、50億局面弱で1回だけ最適化したということです。（対局時はもっと回していたかもしれません。）

2017/5/11 追記

elmoのソースコードが公開されました。
github.com

上記の説明と対応する箇所は以下の通りです。

src/usi.cpp (706～711行目)

const double eval_winrate = sigmoidWinningRate(eval);
const double teacher_winrate = sigmoidWinningRate(teacherEval);
const double t = ( (hcpe.isWin) ? 1.0 : 0.0 ); // tkzw: 勝っていれば1, 負けていれば0

const double LAMBDA = 0.5; // tkzw: 適当に変えてください。
const double dsig = (eval_winrate -t) + LAMBDA * (eval_winrate - teacher_winrate);