30分でボナンザメソッドの収束が5倍速くなる方法を話します!

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

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

かず@なのはさんは、「ぼくは、お小遣い制なので、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倍速く収束させる方法でした。

30分でボナンザメソッドの収束が5倍速くなる方法を話します!」への14件のフィードバック

  1. 専門外でバカなことを言っていると思いますが…(汗

    ちょっと違う「オンライン学習」で、yane@homeみたいなクライアントを作って分散処理は難しいのでしょうか。解説記事を読むと、局面ごとの学習は、少なくともその部分は並列性が高そうに見えます。もしできれば、微力ながら協力できます。←学習にいくらお金があっても足りない点

    P.S.
    64局面相当のFV_PENALTYは、元のFV_PENALTY次第ですが、単純にポアソン分布で下側累積確率を0.95とか0.99にとる手法だと0回近くになりそうなのでいっそのこと削除がいいみたいですね。

    • > もしできれば、微力ながら協力できます。

      おお、ありがとうございます!私のほうは、1PCでも1週間ぐらいで収束しそうなのでいまのところ大丈夫です…が、棋譜の数を増やすとそうでもなくなってくるので何かの際には協力をお願いするかも、です。学習部をクラスター化するのは、ボナンザメソッド(バッチ学習)では容易なのですが、いまどきの手法(SGD以降)は、色々問題があって、すこぶる難しいです。分散SGDの機械学習の論文が大量にあるのが、その難しさを物語っているように思います。

  2. >このとき、1回の学習に使う棋譜は64局分ぐらいを用いるのがお勧めです。あ、このとき棋譜は毎回シャッフルされるものとします。

    毎回シャッフルされるものとします、、、ということの内容は具体的には「数万局ある棋譜データベースから毎回64局相当のデータをランダムに選び出す」、、、という理解でよいのでしょうか?

    • はい、そうです。毎回64局取り出すと、前回の64局に含まれている棋譜が今回の64局に含まれていたりすると気分が悪いので、それはないようにしたほうがいいかも知れませんが。

      • ご返事ありがとうございます。
        この話のポイントは棋譜データの母集団(数万個)からそれをうまく代表できる64個の棋譜データをどうやったら毎回うまくサンプリングできるか、、、という所にありそうですね。

        それから、多変量解析をやるときに、元データの直交性(独立性ともいえますが、、、)がいいと、少ないデータ数で確実な結果が得られます。
        そこから類推するに、選び出された64セットの棋譜データの直交性が高ければ、収束はより速くなりそうな気がします。
        でも、「棋譜データの直交性」をどうやって計算したらいいのか、皆目見当がつきません、、、。

        • > 棋譜データの直交性
          とりあえず、差し手(人)や先手後手の戦法、どちらが勝利したか、終局までの手数がばらけると良いかもしれませんね。

          あとは、legacy なテクニックですが、「ステップ幅」をだんだん小さくして更新していく…手に似せて「大雑把に近い値まで収束」を早めにする手はあるかもしれません(的外れだったらすみません)。

          あとは、学習の評価ですが、自己対戦ではなくて、n-fold cross validation の感覚で「未知の局面について、勝利側の方が評価関数の値が高いか」どうかを指標としてやると、時短になりそうですね(もしかして、これ、めっちゃいいアイデア?)。

          • > 「未知の局面について、勝利側の方が評価関数の値が高いか」どうかを指標としてやる

            将棋は結構、逆転が多いゲームなので(特に人間の対局棋譜は)、勝ったほうの指し手が正例とは限らないのがアレなところですね。勝ったほうの序盤の評価値がプラスとも限らなくて…。

            強化学習とかで勝ったほうの棋譜から学習しようとする試みが、ことごとく失敗する(そういうソフトがレーティング上位に来ない)のはそのへんが理由としてあるような。

        • > そこから類推するに、選び出された64セットの棋譜データの直交性が高ければ

          同一局面を省く(Aperyなんかはやってますね)以上のことはなかなか難しいのでは…。

  3. ちょっと思ったんですけど、ローカルな極値に陥るみたいな話がない・・・(例えば焼きなまし法で回避するような問題)・・・のが不思議なんですが、将棋の評価関数の最適化問題では出てこないんですかね?

    • 将棋には直接関係ありませんが不適切だと思ったら消してください

      ———————————
      Googleは、脳の活動を模したニューラルネットワークによって学習を実現する「ディープラーニング」をサポートした機械学習ライブラリ「TensorFlow」をオープンソースで公開しました。ライセンスはApache 2.0オープンソースラインセンスです。

      • TensorFlowですけど、機械学習って結局、たいていは入力ベクトルxと出力yが与えられて、y=AxなるA(ベクトル or 行列 or …)を求めるだけの問題なのでライブラリとして提供してもらっても私としては何も嬉しくはないですね。

        ライブラリとして提供してもらってありがたいのは機械学習の内容をほとんど理解していないユーザーがpython等からお手軽に入力と出力与えて学習させて機械学習の面白さを体験できるというのはあるのかも知れませんが。

    • 焼きなまし法のreheating、そんなに意識しなくてもそう簡単に局所解には落ちないですね。なにせパラメーター数が多いので自動的に何らかのパラメーターは振動し続けるので…。本家のボナメソでは勾配が0の要素にも乱数を加算することで一種のreheatingをやっているように見えますけども。

りちゃぼう へ返信する コメントをキャンセル

メールアドレスが公開されることはありません。 が付いている欄は必須項目です