今回の事の発端は、これです。

将棋の評価関数のパラメーターを1回収束させるためにボナメソではAWSのc3.8xlargeを半月借りる必要があるのだが、その額、10数万円。1回収束させるのに10数万円。ソシャゲで言えば1ガチャが10数万円だぞ？こんなんSRとかSSR引こうと思ったら、いくらお金あっても足りんわ…

— やねうら王 (@yaneuraou) November 3, 2015

「いまどきボナメソなんか誰も使ってねーよ！ｗ ばーか、ばーか！」というツッコミが来るかと思いきや、そうでもなかったようで、かず＠なのはさんは、こんなことを言っています。

そんなにかかるのか！ うちのPCだと進行遅いなぁ、とは思ってたんだけど、これは詰んだ＼(^O^)／ https://t.co/wBPZcDrsBw

— かず@なのは (@kazu_nanoha) November 3, 2015

@kazu_nanoha スポットインスタンス使えばそんなかからないですよ。

— 平岡 拓也@Ponanza倒したい (@HiraokaTakuya) November 3, 2015

かず＠なのはさんは、「ぼくは、お小遣い制なので、AWSに持っていくお金なんかないから、家のPCで学習させるけど、AWSの32コア(16物理コア)でそれだけ時間がかかるなら、家のPCだと電王トーナメントに間に合わない。そんなに(時間が)かかるのか！これは詰んだ＼(^O^)／」と言っているのに対して、平岡さんが「スポットインスタンス使えばそんなに(お金は)かからないですよ。」とか返信してて、全く話が噛み合っていないのがなんともシュールです。

ちなみにAWSはスポットインスタンスでもWindowsですと、1.5$/h以上かかって、1日4500円近くかかります。半月で6.5万円ぐらいかかります。何故、AWSはWindowsだけあんなに高いのか、わけがわかりません。いまどきLinuxが使えないプログラマーは死ねとでも言うのでしょうか。Linuxが使いやすいかどうかの問題ではなく、すっかり老害のわたくしめとしましては、いまさら大変貴重な脳内リソースを費やしてLinuxなんか覚えたくないのですよ！

みたいな話をしていると、30分では終わらないので(すでに5分経過)、話を進めます。

ボナメソの要点としては、棋譜の指し手でdepth手だけ進めたときのleaf(末端の局面)と、棋譜の指し手以外で進めたときのleafと比較します。前者をA、後者をBとします。Aは1つですが、Bはたくさんあります。あまりのAとBの評価値がかけ離れていると参考にならないので、それらは無視するとします。それでも10個ぐらいはあります。もっとあるかも知れませんね。

つぎに、
1. Aに出ていて、Bに出ていない特徴因子には加点したい
2. Aに出ていなくて、Bに出ている特徴因子には減点したい
3. Aにも出ていてBにも出ている特徴因子には加点も減点もしたくない
ですね。

1. 2.でどれだけ加点するかという問題はありますが、そこはさほど重要ではなくて、大切なのは3.です。3.は確実にやらないと発散します。だって、その特徴因子は良くも悪くもないわけですから、値をいじりたくないのに、その値を動かしたらおかしいっしょ？

また、AとBとの差分は取りたくないです。プログラムが複雑になるので。

ではどうすればいいでしょうか。
・Aに出現した特徴因子すべてに+1点加点
・Bに出現した特徴因子すべてに-1点減点
これでどうかと最初思うわけです。確かに上記の1. , 2. の条件は満たします。

ところが、3.の条件を満たさない。Aのleafは一つですが、Bのleafは10個ぐらいあるからです。仮に10個あるとしたら、AとBの両方に出現した特徴因子は、+1 + (-1)×10 = -9 と大きく値が減ってしまう。これでは何をやっているかわからない。これで収束するはずがない。そういうわけです。

そこで
・Aに出現した特徴因子すべてに+1点加点
をやめて、+1点加点ではなく、Bのleafの数(いま仮に10)だけ、加点するように変更してやるわけです。

これがボナメソです。実際のソースコードでは、Bに出現した因子にdT減点して、Aに出現した因子には、この合計である、Σ dTを加算します。

「いやいや、そんなことをするとBのleafがたくさんある局面ほど、その重みが大きくなってしまうので、Bのleafの数をmとして、次のようにしたほうが良いのでは？」
・Aに出現した特徴因子すべてに+1点加点
・Bに出現した特徴因子すべてに-1/m点減点
と言われるかも知れません。これは激指のオンライン学習ですね。

どちらが優れているかの議論はここではしません。

次に、Bonanzaでは、この+1点加点と言っても、実際はすぐには加点/減点していません。実際に値を動かすのは次の関数です。

dvの符号によってistep分動かすというわけですね。いま、話を簡単にするためistep == 1と考えましょう。また、出現しなかった特徴はdv==0ですから、vがゼロ方向に移動するようにistep(==1)だけ引っ張られるということもわかりますね。こうして、集合全体をsparse(値が0である要素が多い集合)にしているわけです。dvが微小でFV_PENALTY以下のときもvはゼロ方向に引っ張られます。

また、「せこいこと言わずにdv × 係数分ぐらい1回に動かせばいいじゃん！」という話もあります。激指をはじめとするオンライン学習では大抵そうします。「Bonanzaは、目的関数はデコボコ(かも知れない)ので、そんなにいっぺんにたくさん動かしてはいかん！傾きの方向にちょっとずつ動かすのぢゃ！」という思想の元に作られています。まあ、当時、この目的関数の実際の姿(?)がどういうものかは知られていなかったわけで、安全方向に倒したわけですね。

そんなわけで、話はそろそろ見えてきたかと思いますが、激指風に変えてしまうのが一つの方法です。しかし、オンライン学習はBonanzaのようなバッチ型の学習と比べると収束性に不安があります。

そこで、まずはバッチ型学習は維持したまま、大雑把に近い値まで収束させることをお勧めします。このとき、1回の学習に使う棋譜は64局分ぐらいを用いるのがお勧めです。あ、このとき棋譜は毎回シャッフルされるものとします。この条件では、mini batch SGD(ミニバッチ確率的勾配降下法)にかなり近くなってきます。

ところが、BonanzaのソースコードのままですとFV_PENALTYの処理があってしばらく出現しないとすぐにゼロ方向に行ってしまうわけです。

本来4万局に対して出現しない特徴を少しゼロ方向に引っ張ろうという程度のものなので、64局見て出現しないごとにゼロ方向に引っ張っていたとしたら、それは引っ張りすぎです。

「なら、dv==0のときは引っ張る量(step)を、64/4万ぐらいにすればいいのか？」
と言われるかも知れませんが、FV_PENALTYの値も、4万局に対して、FV_PENALTY未満しか動いていなければゼロにひっぱっちゃえ！みたいな値なので、この値も4万局ではなく64局に相当する値に変更する必要があります。(確率計算して調整してくだされ…。)

あるいは、どうせ最終的には元のボナメソ通りに学習させるということであれば、このペナルティの処理を削除してしまうかです。

つまり、
if (dv == 0) return ; // 勾配がゼロのときは動かさない
とするわけですね。

名づけてノンペナボナンザメソッドです。

64局ごとぐらいにノンペナボナンザメソッドで1stepずつ回して、500回ほどiterationを回します。(500×64局 = 32000局) これで、そこそこの値に収束しているので、そこから64局を1000とか5000とかに徐々に増やしながら、最終的に元のボナンザのバッチ学習で学習させれば数回〜10回程度のiterationでそこそこの値に収束します。

以上、Bonanzaより5倍速く収束させる方法でした。