[DLHacks]Classical Planning in Deep Latent Space: Bridging the Subsymbolic-Symbolic Boundary
249 Views
June 12, 18
スライド概要
2018/06/12
Deep Learning JP:
http://deeplearning.jp/hacks/
DL輪読会資料
関連スライド
各ページのテキスト
Classical Planning in Deep Latent Space: Bridging the Subsymbolic-Symbolic Boundary PSI B3 近藤生也 1
書誌情報 ● Classical Planning in Deep Latent Space: Bridging the Subsymbolic-Symbolic Boundary ○ ● Asai, M.; Fukunaga, A ○ ● Accepted in AAAI-2018 ○ ● ポイント ○ 「深層学習手法 ×グラフ理論」で環境内で実行可能な Actionを自ら見つけ出し、かつ長期的なプラン ニングを可能とするモデル『 LatPlan』を提案 ○ ● 選定理由 ○ 1/22にあったJSAIの基調講演で興味を持った（けどそのときは理解できなかった）から 2
アジェンダ ● ● ● ● ● ● ● LatPlanとは 古典的プランニングの欠点 深層学習手法とプランニング LatPlanの仕組み 実装解説 実験結果 所感 3
LatPlanとは（8パズル） 初期状態 目標状態 4
LatPlanとは（8パズル） 初期状態 目標状態 5
LatPlanとは（ハノイの塔、Lights-Out） 6
LatPlanの特長 ● 必要なのは画像だけ ○ ○ 3x3のパズルそのものの画像 ×数万データ 3x3のパズルに対して、 「何かしら のアクション」を行った時の 前と後の画像 のペア×数万データ ○ ● 世界を人間がモデル化する必要がない ○ ○ ○ ● 8puzzle.pyみたいなのは不要。 実世界の8puzzleの写真を使うことを想定。 前 後 見たことがないActionがあってもプランニ ング可能。見たことがないActionを生み出 すことも可能。 7
古典的プランニング https://ja.wikipedia.org/wiki/自動計画 8
古典的プランニング ● アクション a ∈A a = <param, pre, e+, e-, c> （パラメータ, 前提条件, 追加効 果, 削除効果） True/False のバイナリデータ https://ja.wikipedia.org/wiki/自動計画 9
古典的プランニング
;; ロボットアームでテーブルの上に載っているブロック?x
a = <param, pre, e+, e-, c> を掴むアクション.
(:action pick-up
の例
:parameters (?x)
;; 前提条件の一覧.
:precondition (and (clear ?x)
(ontable ?x) (handempty))
;; アクション実行後に生成する述語.
:effect (and (not (ontable ?x))
(not (clear ?x)) (not (handempty))
(holding ?x)))
http://d.hatena.ne.jp/hanecci/20100220/1266681999 10
古典的プランニング ● ● 初期状態とゴール状態をバイナリデータに変換 すべての行動を01の変化で記述 ○ ○ ● a a 遷移図を書いて総当りなりA*なり、あるいは グラフ 理論の賢い方法を使ってプランニング ここをNNでやってしまおう ここも一部NNでやってしま おう 11
LatPlanとは ● AMA1 ○ ● SAE + Fast Downward（古典的ソルバの SOTA） AMA2 ○ SAE + AAE + AD + A* 12
アーキテクチャ 13
AMA1 SAE（State AutoEncoder） ● ● エンコード先のZをバイナリデータにしたVAE。 ただ単にencoderの出力に if (z>0.5) { z=1 } else { z=0 } のようにすると誤差逆伝 播ができないので、Gumbel-Softmaxという活性化関数を使う 14
Gumbel-Softmax ● Gumbel-SoftMax [2017] z= ○ ● 右のように変える ○ ● ● 普通のAEの出力をπ log(π)のsoftmax（結局ほ とんどπに戻る）に、 ノイ ズgを足す π= ただし http://musyoku.github.io/2016/11/12/Categorical-Repar ameterization-with-Gumbel-Softmax/ 15
Gumbel-Softmax ● ● ● τは温度 τ==1→100 τが小さいとバイナ リに近くなり,τが大 きいとのっぺらぼ うになる z= π= ただし http://musyoku.github.io/2016/11/12/Categorical-Repar ameterization-with-Gumbel-Softmax/ 16
Gumbel-Softmax ● Gumbel-SoftMax [2017] π= ● ● もともとの分布がしっかり01に近くない と結構ぶれてしまう。 →もとの分布がしっかり狙ったところが 1になるように学習が進む。 z= ○ http://musyoku.github.io/2016/11/12/Categorical-Repar ameterization-with-Gumbel-Softmax/ 17
VAE ● Zが正規分布に従うという仮定をおき、 Encoderは平均と分散を出力 ○ ● Encoderが出した平均と出力をもとに空間 Zから一点をサンプリング ○ ● 密な潜在空間を生成できるので、表現力 が高まる。 https://qiita.com/kenmatsu4/items/b029d697e9995d93aa24 18
Fast Downward Fast Downward [Helmert, 2006] https://arxiv.org/abs/1109.6051 ● ● 入力：すべての状態、すべての行動、初期状態、目標状態 出力：最短の行動プラン （今回調査しきれませんでした…） 19
精度 ● ● 100%（ノイズなし。ノイ ズありは書いてなかっ た） 8パズルで最も長い解 をもつインスタンスでも 問題なかった 20
AMA2 ● SAE + AAE（Action AutoEncoder）+ AD（Action Discriminator） ○ ● AAEでとりあえず遷移させた状態を作って、ありえないものはADで消し てもらう 21
Action AutoEncoder ● ● ● ● データ：ある遷移前のz∈Zとある遷移後のz∈Zのセット（s,tと置く） 入力：s, t 出力：t 中間：7bitの配列 ○ （アクション記号が 128個あると大きめに見積もってある） 22
Action AutoEncoder ● 中間：128次元の01データ これをアクションラベルとみなす ポイント ● すべての層にsをconcatする ○ ● もとがsであることを自明にする。 デコーダーを使うと、aとsからtを予測できる。 23
Action AutoEncoder ● ● 結局、128通りのactionを学習する。 当然ありえないactionが含まれているのでDiscriminateする必要がある。 24
Action Discriminator ● ● 入力：遷移前のz, AAEで生成した遷移後のz 出力：0or1（可能な遷移か否か） ○ ● ● 可能な遷移は観測できるが、不可能な遷移は観測できない。 →PU Learning 25
Action Discriminator PU Learning：観測された正例データから、未観測データを正例負例に分類。 まず観測 済みか否かで分類→未観測を複製して重み付け→正例と負例に分類 https://colab.research.google.com/drive/1spUTt9ckhVLu4lh7krsmALKbvoPzu_81 26
Action Discriminator PU Learning ● ● ● ↓正例と負例 ↓未観測が灰色 負例データを見たことがない状 態で分類すると左下のように全 部同じクラスになる。 未観測データが与えられたらま ず未観測か否かで分類し、 下のように重み付け 正しく分類が行えた ↑ 27
A* ● ● ● ● ● ● グラフ探索アルゴリズムの一つ。 最良優先探索を拡張したZ*に、 「現時点までの距離」gと 「ゴールまでの推定値」hの 和を採用したもの。 h は ヒューリスティック関数と呼ばれる。 https://ja.wikipedia.org/wiki/A* 28
A* ● ● ● ● ● 各マス目にスコアを設ける。 スコア＝実コストg＋推定コストh（小さい方が良い） g：スタートからの距離 h：ゴールまでの距離（障害物は考えない） ここではどちらもマンハッタン距離を考える。 スコアの低いマスから順 に周りのマス目を計算対 象にしていく（ Openにす る）。 周りにOpenできるマス がなくなったら Closedに する。 https://qiita.com/2dgames_jp/items/f29e915357c1decbc4b7 29
A* ● ● 距離←SAEでエンコードした時のゴールと異なるbit数 Fast Downwardと違って最適解が得られる保証はない https://qiita.com/2dgames_jp/items/f29e915357c1decbc4b7 30
精度 ● ADが正しく負 例と識別 した 遷移。 type2の!error A:7回ランダム操作, B:14回ランダム操作 ○ ● std:ノイズなし, G:ガウス, s/p:ごま塩 ○ ● ● AD.type1:AAEで生成された正しい遷移のう ち、ADが間違えて否定した割合 AD.type2:本当に可能な遷移を除いて遷移の 負例データを大量に作る。そのうちADが間違え て正例と判定した割合 AAE ←type2のerror 本当に可能な 遷移（type2の 対象外） 31
精度 ADが正しく負 例と識別 した 遷移。 type2の!error ● AAE ←type2のerror 本当に可能な 遷移（type2の 対象外） 32
実装 https://github.com/guicho271828/latplan GumbelSoftmax ● Kerasのレイヤーとして定義されている 33
実装 https://github.com/guicho271828/latplan SAE ● Denoisingしている 34
実装 https://github.com/guicho271828/latplan ActionAE（36+36 => 128） ● 基本的に全結合だけでいける 35
実装 https://github.com/guicho271828/latplan ActionAE（36+36 => 128） 36
実装 https://github.com/guicho271828/latplan ActionAE（128 => 36） 37
実装 https://github.com/guicho271828/latplan ActionAE（128 => 36） 38
実装 https://github.com/guicho271828/latplan AD 39
結果 ● Z(6x6) SAE（ランダムなZ） 40
結果 ● SAE（上がうまく行ってて下が失敗） 41
所感 ● ● ● パズルってもともと状態が離散的だからグラフにしやすい 連続的な環境をうまく離散化して01に落とし込めたら他のプランニングにも広く使え る ただ長期のプランニングはやはり難しいそう（行けそうな気がしたけど…） ○ ● カーナビと同じ要領なんじゃないのかな … SAEでエンコードしたものが近いからと言ってaction的に近いわけではない説 42