2017-07-19

XGBoost fizzbuzz

XGBoostのFizzBuzzです　　

勾配ブースティングでもFizzBuzzできるという例を示します

やろうと思った動機

DeepLearningならばFizzBuzzの3の倍数と5の倍数と15の倍数の時に、特定の動作をするというルールを獲得することは容易なのですが、他の機械学習アルゴリズムはどうでしょうか

XGBoostはその決定木の性質と、勾配ブースティングの学習アルゴリズムを解析的に説明した論文の内容を見ると、特定のルールを獲得することは難しくないんじゃないかと思いました[1]

ただ、FizzBuzzを数値として扱ってしまうと、かなり厄介で、連続する値が大きい小さいなどで判別するのは容易ではありません

DeepLearning時と同じように、Character Levelで入力を扱います

具体的な数値データの取り扱い

数字を文字表現として皆して、各桁の数字を一つの特徴量として扱います

図1.　データの取り扱い

クラスの設定、目的関数の設定

クラスは"3の倍数の時のFizz",“5の倍数の時のBuzz”,“15の倍数の時のFizzBuzz”,“その他"の時の4つのクラスの分類問題にしました

softmaxではなくて、softprobを用いました

ドキュメントを読むと、各クラスの所属する確率として表現されるようです（クラスの数ぶん、sigmoidが配置されていると、同じ？）

学習データ

0〜99999までの数字の各FizzBuzzを利用します　　

この時、2割をランダムでテストデータに、8割を学習データに分割します　　

各種パラメータ

このようにしました、もっと最適な設定があるかもしれないので、教えていただけると幸いです

etaが大きいのは、極めてroundが多いので、これ以上小さくするとまともな時間に学習が完了しません　　

booster      = gbtree
objective    = multi:softprob
num_class    = 4
eta          = 1.0
gamma        = 1.0
min_child_weight = 1
max_depth   = 100
subsample   = 0.8
num_round   = 100000
save_period = 1000
colsample_bytree = 0.9
data        = "svm.fmt.train"
eval[test]  = "svm.fmt.test"
#eval_train = 1
test:data   = "svm.fmt.test"

プログラムの解説

githubにコードが置いてあります

データセットの準備

$ python3 createDataset.py --step1 # データセットの作成
$ python3 createDataset.py --step2 # 前処理
$ python3 createDataset.py --step3 # libsvmフォーマットを作成

学習

(xgboost.binはubuntu linux 16.04でコンパイルしたバイナリです。環境に合わせて適宜バイナリを用意してください)
(学習には、16コアのRyzen 1700Xで2時間程度かかります)

$ ./xgboost.bin fizzbuzz.train.conf

予想

(必要に応じて、使用するモデルを書き換えてください)

$ ./xgboost.bin fizzbuzz.predict.conf

精度の確認

$ python3 predCheck.py

精度

50000roundでテストデータで以下の精度が出ます

acc 0.9492

出力はこのようになります

    12518 predict class = 3 real class = 3
    42645 predict class = 2 real class = 0
    15296 predict class = 3 real class = 3
    47712 predict class = 3 real class = 1
     1073 predict class = 3 real class = 3
    66924 predict class = 1 real class = 1
    82852 predict class = 3 real class = 3
    26043 predict class = 1 real class = 1
    96556 predict class = 3 real class = 3
    81672 predict class = 1 real class = 1
    44018 predict class = 3 real class = 3
    16622 predict class = 3 real class = 3
    79924 predict class = 3 real class = 3
    15290 predict class = 2 real class = 2
    25276 predict class = 3 real class = 3

class 2は15の倍数なのですが、これの獲得が難しいようです

liblinear(support vector classification)との比較

一応、違う機械学習との比較ともやるべきでしょう

L2-regularized L2-loss support vector classificationで動作する、liblinearで比較しました　　

$ ./train -s 1 svm.fmt.train 
....*.*
optimization finished, #iter = 52
Objective value = -56679.234880
nSV = 64068
.....*
optimization finished, #iter = 51
Objective value = -56678.857821
nSV = 65083
....*.
optimization finished, #iter = 50
Objective value = -14306.576984
nSV = 17032
.....*
optimization finished, #iter = 51
Objective value = -14305.608585
nSV = 16957

$ ./predict svm.fmt.test svm.fmt.train.model output
Accuracy = 66.2298% (13240/19991)

精度が66%しか出ていません

やはり、XGBoostの精度で判別をすることはできないようです

まとめ

DeepLearningでは精度100%を達成できましたが、XGBoostでは95%程度の精度です

完全なルールの獲得は怪しいですが、それでもかなりいいところまで行っているようです　　

また、目的関数を複数ラベルを取れるようにするなど、うまく設計すれば、もっといけるでしょう（勾配ブースティングのマルチラベル分類、どうやるんだろう）　　

参考文献

[1] XGBoost: A Scalable Tree Boosting System

2017-07-17

Multi Agent Deep Q Network for Keras

Kerasでマルチエージェント DQN

マルチエージェントラーニングは、相互に影響を与え合うモデルが強調ないし、敵対して、目的となる報酬を最大化するシチュエーションのディープラーニングです[1][2]

強化学習の特殊系と捉えることができそです　　

Deep Mind社が提案したモデルの一部では非常に面白く、報酬の設定しだいでは各エージェントが協力したり敵対したりします。　　

Kerasで敵対的な簡単なマルチエージェントラーニングを21言っちゃダメゲームでスクラッチで、構築しました

(これはQiitaのはむこさんの記事を参考にさせていただきました、ありがとうございます[3])

(調べながらやったこともあり、理論的な間違いを見つけたら、ツイッターで指摘していただけると助かります)

強化学習の理論

強化学習は、人間が特に正しい悪いなどを指定せずとも、なんらかの報酬系から値を得ることで報酬を最大化するよう学習します　　

このとき、ある系列の状態をSとし、その時の行動をaとし、この組み合わせで得られる報酬関数をQとすします

　この関数で、最適な行動を得られた時に*をつけて表し、この時の行動sについて最大となるsをとると、以下のように最適な行動πを得ることができます

また報酬の割引率というものがあるのですが、今回は具体的に割引率を与えたり、求めるということをしていません

今回の例では、Q関数を具体的にDeepLearningによる関数としています

ϵ-greedy

全く意識していなかったのですが、どうやら行動の選択は初期値依存性がある程度あり、運が悪いと局所解に嵌ったなままなかなか更新してくれなくなります　　

適度にランダムに行動を選択することを入れないとダメっぽいです　　

ルール（問題設定）

先手、後手に別れて0から最小１、最大の３つ増やした数字を言い合います　　

数字を累積していって、21以上のになるように言った時点で負けです。相手に21以上を踏ませれば勝ちです

今回設計した、Q関数

Q関数は状態と行動を入力することで、報酬の値を得ます　　

報酬がもっとも多いと期待できる選択を選ぶことで、（この問題の場合）最短の手数で、勝ちに行くことができます

今回は、それぞれの行動と状態から、唯一に報酬が決まるとして、その和でQ関数が表現されるとしました（この問題設定がいつも適応できるわけではなさそうです）

このスモールq関数をディープラーニングで表現すると、このような任意のモデルで書くことができます

報酬の設定

一個一個の行動に報酬を設定するのは、困難なので、一連の行動の系の結果として勝ったか、負けたかを見ていきます　　

スモールq関数を求める問題に変更できたので、これを具体的に以下の値を最小化していきます（Nはゲーム終了までにかかった手数）　　

勝った時の報酬を+1, 負けた時の報酬を-1のReward関数とすると、以上の式を最小化すれば、勝った時はその選択をより強化して学習し、負けた時は選択を誤ったとして、別の可能性を探索する可能性が強くなります　

マルチエージェント

同じような報酬系をもつモデルを２つ以上用意して、対決させました

先に21以上を言った方が負けというルールで二つのモデルに対決させました

コード＆実行

githubにて管理しています　　

マルチエージェント学習

$ python3 21-icchadame-pure.py --reinforce

実際に対戦してみる

$ python3 21-icchadame-pure.py --play

強さについて

この21言っちゃダメゲームは4の倍数を取りに行けば勝てることがわかっている問題なのですが、途中から4の倍数にはめ込もうとしようとしていることがわかります

例えば、次のような結果になります

なお、最適解は、初手で１を打って次に4を取らせることですが、初期値依存性があり、この状態に素早く収束させるのは結構難しいです

下記の例は、20000回のゲームをさせた例

例1.

コンピュータは3を選択しました
now position 3
数字（１−３）を入力してください
2
コンピュータは3を選択しました
now position 8
数字（１−３）を入力してください
1
コンピュータは3を選択しました
now position 12
数字（１−３）を入力してください
2
コンピュータは2を選択しました
now position 16
数字（１−３）を入力してください
1
コンピュータは3を選択しました
now position 20
数字（１−３）を入力してください
1
結果 あなたの負け

例2.

コンピュータは3を選択しました
now position 3
数字（１−３）を入力してください
3
コンピュータは2を選択しました
now position 8
数字（１−３）を入力してください
3
コンピュータは1を選択しました
now position 12
数字（１−３）を入力してください
3
コンピュータは1を選択しました
now position 16
数字（１−３）を入力してください
3
コンピュータは1を選択しました
now position 20
数字（１−３）を入力してください
3
結果 あなたの負け

実際やってみて

Reinforce Learning関しては教師あり学習、教師なし学習についで、最後にやろうと思っていたこともあり、あまり深く手をつけていませんでした

最初、理論をあまり勉強せず、とりあえず適当にコードを書いてみたのですが、収束はめっちゃ早いけど、すぐオーバーフィットしてしまうモデルになってしまいました。基礎理論を再度確認して、コードに落として行くという気持ちでやると、サクサクできます（反省）

マルチエージェントにすることで、コードがやばいことになるのかなと思ったのですが、意外とシンプルに構築することができました

今回は敵対的なゲームでしたが、時には協力し、時には裏切るモデルなど面白そうであります。学習させることも容易なので、様々な応用が利きそうで面白そうでした

参考文献

[1] Understanding Agent Cooperation
[2] Multi-agent Reinforcement Learning in Sequential Social Dilemmas
[3] 深層強化学習：「20言っちゃダメゲーム」の最適解を30分程度で自動的に編み出す（chainerRL）

2017-07-04

KerasのRNNでFizzBuzzを行う(+ Epochスケジューラの提案)

ディープラーニングをやるようになって半年程度経ちました
ある程度ならば、文章や画像判別モデルならば、過去の自分の資産をうまく活用することと、外部からState of the Artな手法を導入することで、様々なネットワークを組むことが可能になってまいりました
しかし、基礎の基礎であるはずの、Fizz Buzzをやるのを忘れていたのです
やるしかありません

先行研究

全結合のモデルでの、Fizz Buzzの評価のようです

提案

RNNでも、FizzBuzzは可能なのではないでしょうか
全結合層のモデルのみで、1000 ~ 5000程度のデータで学習させることが多いですが、20万件のデータセットで学習させることで、より大きな数字にも対応させることを目標とします

カリキュラム学習という学習法があり、簡単な問題設定から初めて、徐々に難しくしていくことで、早く安定的に学習できるそうです[1]

この時、人間がカリキュラムを意図して簡単な問題を用意して学習させるのではなく、学習のデータを最初のうちは限定したデータセットにて学習させ、限定したデータを覚えてきたらデータを拡大し、様々なケースを学習させて、汎化性能を獲得していくという学習方法をとります

具体的には、データセットとepochにスケジューラを組み込むことで実現します

モデル

‘1:Fizz, 2:Buzz, 3:Fizz Buzz, 4:そのまま(Path)'と４値の判別問題を全結合層２層でといている問題設定が多いが、 '1:Fizz, 2:Buzz, 3:Path'の３値のそれぞれの状態を求める問題設定とする

図1. 使用したモデル

コードはKerasを利用したモデルとスケジューラは、非常に小さく、わかりやすいですモデル

inputs       = Input(shape=(10, 11))
encoded1     = Bi( GRU(256, activation='relu') )(inputs)
encoded1     = Dense(512, activation='relu')( encoded1 )
encoded1_1x  = Reshape((1,512,))(encoded1)
decoded      = Dense(3, activation='sigmoid')( Flatten()(encoded1_1x) )
fizzbuzz     = Model(inputs, decoded)
fizzbuzz.compile(optimizer=Adam(), loss='binary_crossentropy')

スケジューラ（初期のデータセットは、epochを多く学習し、後半になるにつれ一回のみにスケジューリングしている）

class CURRICULUM:
  EPOCH = [50, 30, 20, 10, 5, 1]
  @staticmethod
  def GET():
    if len(CURRICULUM.EPOCH) > 0:
      return CURRICULUM.EPOCH.pop(0)
    else:
      return 1
...
fizzbuzz.fit(Xs, Ys, epochs=CURRICULUM.GET(), callbacks=[batch_callback])
...

コードや日本語では伝えるのに私の貧困なコミュ力では難しかったので、画像を添付しますと、このような差があります

図 2. スケジューリングなし

図 3. スケジューリングあり

このように、学習初期に置いて、学習するデータを非対称にして、最初のデータは多めに繰り返し学習させます

実験

200,000件のFizz Buzzのデータセットを、スクリプトで作成し、5000件ずつ、データセットを分割し40個のデータセットを学習させる

この時、スケジューリングモデルAは、任意のデータセットをランダムで選択し、以下のepoch回、学習する

{ 1回目：50epoch, 2回目：30epoch, 3回目：20epoch, 4回目：10epoch, 5回目：5epoch }

このスケジューリングが完了した後は、残りのデータセットを1epochで学習する

スケジューリングモデルBは特にスケジューリングは行わず、全てのデータセットを平等に学習していく。なお、この方法は、全てのデータセットをメモリ上に乗せて順番に学習していく方法と変わらない

評価

スケジューリングモデルA（青）とモデルB（赤）で大きな差がでた

図4. trainデータのepochごとのlossの変化

ニューラルネットワークの初期値の依存性を考慮しても、この差は大きく、スケジューリングを行うことが、まともに収束するしないなどの差を担っているように思われる

モデルAはテストデータにおける精度100%であった
モデルBは68%であった

なお、出力はこのようになっている左から、入力値、人手による結果、予想値、正解だったかどうか、である（PATHとは、そのまま出力するという意味にしました）ほぼ100%あっていることが確認できた

    64170 original result = Fizz Buzz , predict result = Fizz Buzz , result = True
      9791 original result = Path , predict result = Path , result = True
     54665 original result = Buzz , predict result = Buzz , result = True
    118722 original result = Fizz , predict result = Fizz , result = True
     97502 original result = Path , predict result = Path , result = True
    186766 original result = Path , predict result = Path , result = True
    153331 original result = Path , predict result = Path , result = True
      7401 original result = Fizz , predict result = Fizz , result = True
    117939 original result = Fizz , predict result = Fizz , result = True
     22732 original result = Path , predict result = Path , result = True
     73516 original result = Path , predict result = Path , result = True
    144774 original result = Fizz , predict result = Fizz , result = True
     32783 original result = Path , predict result = Path , result = True
     67097 original result = Path , predict result = Path , result = True
    116715 original result = Fizz Buzz , predict result = Fizz Buzz , result = True
     21195 original result = Fizz Buzz , predict result = Fizz Buzz , result = True

コード

https://github.com/GINK03/keras-rnn-fizzbuzz-on-dev

テストデータを作成する

$ python3 data_utils.py --step1

学習する(全体の8割を学習します)

$ python3 fizzbuzz.py --train

予想する(テストデータから予想します)

$ python3 fizzbuzz.py --predict

感想

データによってはまともに収束してくれないものあり、RNNではその傾向が特に顕著です精確にロス率の違いなどを測ったことがなかったのですが、Epochをいじることによって、安定して学習させることができることがあるということでした

参考文献

[1] Deep Learningの技術と未来

2017-06-11

教師なし画像のベクトル化と、ベクトルからタグを予想したり類似度を計算したりする

はじめに

ISAI2017でPCAnetと呼ばれる、教師なし画像の特徴量の抽出方法が紹介されていました
味深い実装になっており、CNNをバックプロパゲーションで結合の太さを学習していくのではなく、予めフィルタを組み込んでおき、使うことで、高い精度を達成しているようです[1]

これを見ていて、AutoEncoderでも同等のことができるのではないかと思いました
AutoEncoderでは、ディープラーニング学習する必要がありますが、やはり、教師データは必要ないです。画像だけあれば良いです。

AutoEncoder

図1. Auto Encoderの図

GANに似ています。GANはこの、図のDecoderを入力との直接の誤差の最小化ではなく、判別機を騙すことで達成しますが、今回はもとの情報が近い方が良いと思ったので、AutoEncodeを利用しました

画像の特徴量をVAEで取り出す方法もあり、僅かにヒントを与えることと出力を工夫することで、より高精度ので分布が取り出せる方法も各種提案されています[2]
余談ですが、単純な、画像生成という視点では、GANに比べて彩度や繊細さがダメっぽくて、画像生成としては色々工夫が必要だなと思いました。

Encoderから特徴量を取り出す

Encoderから任意の次元に圧縮した特徴量を取り出すことができる

図2. Encoderによる特徴量の取り出し

このベクトルは200次元（配列の長さだと、v.size == 200程度）であり、これからディープラーニングは元の画像に近い画像を復旧できたということは、何らか画像を説明する、重要な特徴量がつまっていると考えられます。

このベクトルをVとすると、なんらかのディープラーニング以前のSVMなどのアルゴリズムで機械学習ができそうではあります
また、XGBoostの登場と、DeepLearningの流行りが同時期であったので、これらが得意とする分野が重ならず、併用する文化があまりなかったので、DeepLearningとXGBoostのコンビネーションをやってみようと思いました。

ディープラーニングの現実的な制約とその解決

画像から、属性を予想するプログラムは過去、何回か書かせていただきました。

最初からわかる問題としては、DeepLearning単体ではタグ情報が固定長までしか対応する事ができず、ネットワークを巨大にしても4000次元の出力で、オンライン学習が難しい（新たにタグが発生したときに学習が難しい）などのデメリットがあります
これらを解決する手段としてAutoEncoder, Variable AutoEncoderなどが使える次第です
画像そのもの情報がベクトル化されるので、これらの情報からXGBoostなどに繋げば、新しいタグが発生した祭などに、容易に学習ができます

AutoEncoderのモデル

学習用のコードはgithubにあります
Kerasで書きました。わかりやすいことは一つの正義ではあります。もちろん微細な制御ができるChainerなども正義です用途と目的によって使い分ければいいかなって思います

input_img = Input(shape=(28*BY, 28*BY, 3))  # adapt this if using `channels_first` image data format
x         = Conv2D(64, (3, 3), activation='relu', padding='same')(input_img)
x         = Conv2D(64, (3, 3), activation='relu', padding='same')(x)
x         = MaxPooling2D((2, 2), padding='same')(x)
x         = Conv2D(128, (3, 3), activation='relu', padding='same')(x)
x         = Conv2D(128, (3, 3), activation='relu', padding='same')(x)
x         = MaxPooling2D((2, 2), padding='same')(x)
x         = Conv2D(256, (3, 3), activation='relu' , padding='same')(x)
x         = Conv2D(256, (3, 3), activation='relu' , padding='same')(x)
x         = BN()(x)
x         = MaxPooling2D((2, 2), padding='same')(x)
x         = Conv2D(512, (3, 3), activation='relu' , padding='same')(x)
x         = Conv2D(512, (3, 3), activation='relu' , padding='same')(x)
x         = Conv2D(512, (3, 3), activation='relu' , padding='same')(x)
x         = BN()(x)
x         = MaxPooling2D((2, 2), padding='same')(x)
x         = Flatten()(x)
z_mean    = Dense(196)(x)
encoder = Model(input_img, z_mean)
""" dec network """
dec_0  = Reshape((7,7,4))
dec_1  = Conv2D(32, (3, 3), padding='same')
dec_2  = LeakyReLU(0.2, name="leaky_d1")
dec_3  = UpSampling2D((2, 2))
dec_4  = Conv2D(64, (3, 3), padding='same')
dec_5  = LeakyReLU(0.2)
dec_6  = UpSampling2D((2, 2))
dec_7  = Conv2D(128, (3, 3), padding='same')
dec_8 = LeakyReLU(0.2)
dec_9 = UpSampling2D((2, 2))
dec_10 = Conv2D(128, (2, 2), padding='same')
dec_11 = BN()
dec_12 = LeakyReLU(0.2, name="leaky_d5")
dec_13 = UpSampling2D((2, 2))
dec_14 = Conv2D(3, (2, 2), padding='same')
dec_15 = LeakyReLU(0.2, name="leaky_d6")

実験に用いるデータセット

Pixiv社のデータを利用させていただきました
400万件を取得し、そのうち、200万件をAutoEncoderの学習に用いました。残り200万件をAutoEncoderのEncoderに通すことで、タイトルとベクトルとその画像のタグ状を取得します
データ構造的には以下のようになります

title1 -> ([v1, v2, ...], [Tag1, Tag2, ...]),
title2 -> ([v1, v2, ...], [Tag1, Tag2, ...]),
...

XGBoostの設定

何のタグが付くかの確率値を出したいという思惑があるので、binary, logisticを使いますその他の詳細な設定は、以下の通りです

param     = {'max_depth':1000, 'eta':0.025, 'silent':1, 'objective':'binary:logistic' }
num_round = 300

これを、すべてのタグに対して予想しますタグの種類は30000を超えており、つまり、タグ一つに対して一つモデルを作るので、30000個ものモデルができますこのようにいくらでもスケールできることが強みになますね

実験

AutoEncoderのチューニングにはGTX1080にギリギリ入るモデルが必要でした（やはりでかいモデルのほうが性能がいい）比べて、後半のタスクであるXGBoostでの学習は、CPUです。Ryzen16コアを2つ持っているのですが、持ってなかったら死んでた…

Pixivのイメージ200万枚を112x112にリサイズして、AutoEncoderで学習
Encoderのみを取り出し、200万枚をベクトル化
タグをXGBoostで学習
任意の入力の画像に対して、適切にタグが付与されるか

結果

学習に用いてないデータでの検証を行いました予想できるタグは30000種類を超えており、多様性の視点では既存のDeepLearningを超えているかと思います

図3. 入力画像と予想出力値(下のタグの画像が真)

図4. 入力画像と予想出力値(下のタグの画像が真)

図5. 入力画像と予想出力値(下のタグの画像が真, 人物は間違った)

ある程度予想していたのですが、やはり、キャラクターの特定は、Pixiv社のタグの数の個数制限があり、なかなか難しかったです
そのかわり強いなって思ったのが、夜空・星空・下絵・海・ハートなど、全体の世界観などモヤッとしたものをつかむがうまかったです

Appendix.類似度

なお、このAutoEncoderの情報をうまく使えば、画像の類似度検索にも用いることができます 200次元程度なので、ある程度、意味のある類似度検索をすることができ、cosine類似度や、ユークリッド距離を図ったりしていたがどちらも、同等のパフォーマンスで、ランキングに大きな変動がなかったため、計算が早いユークリッドを用いました

図6. 一番上が検索クエリで、2,3番めが検索結果

illustration2vecと同様に、画像自体を検索クエリとすることができます高速なマッチングも幾つか考案しましたが、余裕があるときにまたご紹介したいと思います

コード

AE. VAEは基礎的な特徴の研究から初めて、なんとか、いろいろ引き上げて使えるようにした感じです
keras-tiny-vaeがオートエンコーダ系で、特にこのPixivのタスクに限定したものではないコードですが、AE, VAEで特徴量を取り出します
PixivTagPredictorがタグを学習・予想するXGBoostのプログラムです