2017-09-04

Socherの自然文の問合せをSQLに変換する論文を読む

AI論文自然言語解析

テニス２時間　英語できず

(1) Socherの自然言語の問合せをSQLに変換する論文を読む

「Seq2SQL: Generating Structured Queries from Natural Language using Reinforcement Learning」

https://einstein.ai/static/images/layouts/research/seq2sql/seq2sql.pdf

現在SNSで話題になっている自然言語の問合せをSQLに変換するモデルです。

翻訳モデルとしてseq2seqが有名でしたが、これはRNNで適当に人間が解釈できる言葉に変換していたに過ぎません。しかし本モデルは計算機を動かすSQL文の生成モデルなので曖昧性が許されません。

(1.1) 手法

そこで曖昧性を排除するために２つのモデルと知識ベースを導入して達成しています。

・Augment Pointer Network

　曖昧性の除去のため、どの様なDataBaseを対象にしているかを反映した次の様なベクトルを作って学習させています。

　[検索対象になるテーブルのカラム、SQL文、自然言語の問合せ文」

この様な学習用のベクトルが必要なため、膨大な知識ベースを構築しています。

例えば次の様なQuestionには学習用のベクトルは次となります。

[<col>pick,CFL Team,Player,Position,Collage;<sql>SELECT COUN..;<quesiton> How many CFL teams are from College]　

f:id:mabonki0725:20170904072531p:plain

　学習用ベクトルから分る様に完全な教師付モデルになっています。

　この学習用ベクトルを入力として

　　Encode(BiLSTM 2層) → Decode(LSTM 2層)

　で学習用ベクトルにあるSQL文を教師データとして下記のseq2SQLでネットワークの重みを学習させています。

・seq2SQL

　これは上記のAugment Point Nettworkの学習結果を次の種類別に最適なSQL語を選択しています。

　　集約種類(Aggregation)　数　最大　最小　検索の種類の判断

　　カラム選択(Select)　テーブルのカラム名の選択

　　条件(where)　検索条件文の作成

f:id:mabonki0725:20170904073435p:plain

　ここで注意すべきは、集約種類とカラム選択は完全な教師付モデルとして

　入力文とSQL語との相互情報量が低減する様にencoder-decoderの重みを調整しています。

　しかし条件は入力文とSQL語の対応関係では律し得ない表現があるので、検索後の結果の一致度合いを報酬として強化学習も導入しています。

f:id:mabonki0725:20170904074225p:plain

・知識ベースWikiSQL

　学習用のベクトルを作成するため、膨大な学習用の知識ベースを作成していることがわかります。

　問合せ文は、空白があるテンプレートを用意して空白は計算機が埋める方法で大量に生成させています。これが自然文になっているかは人手で検査しています。

f:id:mabonki0725:20170904075601p:plain

(1.2) 結果

　普通のseq2seqによるSQL文の生成結果比較です。

ここで

　　 $Acc_{if}$ は検索結果が一致

　　 $Acc_{ex}$ は生成文が正しい

　　Devはパラーメータ・調整後の試験を示す

f:id:mabonki0725:20170904075418p:plain

　(1.3) 感想

　・複雑な自然言語の問合せ成功例が記述されていないので、どれだけ柔軟な問合せが

　　可能か明瞭でない。

　・大規模な学習用データWikiSQLを構築して初めて成功した。

　　今までNLP→SQLモデルが成功しなかったのは、大規模な学習用データを

構築できなかったからと考えられる。

　　この点wikiSQLはクラウド・フアンディングで資金を調達して構築している。

　・これだけの知識ベースを使っても成功率は50％程度しか達成していない。

　　この辺の理由が明確でない。

2017-09-03

部分観測型の強化学習の文献を読む

ロボテックス確率・統計

ランニング30分英語:Toeic

(1) 部分観測型の強化学習の文献を読む

　「確率ロボット　16章 POMDPの近似手法」※POMDP(Partially Observable Marcov Decision Process)

　この文献は下記のThrunの「Probabilistic Robotic」を千葉工大の上田隆一先生が訳したもので非常に名訳です。先生は[RaspPai Mouse]の製作者としても有名です。

https://www.google.co.jp/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0ahUKEwix2orZx4fWAhUBk5QKHdOzB84QFgg3MAE&url=https%3A%2F%2Fdocs.ufpr.br%2F~danielsantos%2FProbabilisticRobotics.pdf&usg=AFQjCNGyMwb645fqeJ0EKKwcfscTuGp0Bw

f:id:mabonki0725:20170428075234p:plain

(1.1) 手法

　現実のロボットは環境より部分的にしか観測できません。この部分観測データを拠所にして目的を達成する強化学習のモデルの説明です。

　ここでは拡張MDP(Augmented Marcov Decision)の近似モデルで説明しています。

一般に強化学習のBellman方程式は次式になりますが、

$v_t (x) = \gamma \ max_u [r(x,u) + \int v_{t-1}(x') p(x'|u,x) dx' ]$

　部分観察される場合のBellman方程式は次に変更となります。

　　 $v_t(b) = \gamma \ max_u [r(b,u) + \int v_{t-1}(b') p(b'|a,b)db']$

ここで

　　 $x$ は状態

$v_t$ は $t$ 時点の価値関数

$b$ は信念

$u$ は行動

　　 $r$ は報酬

　　 $\gamma$ は割引率

　部分観測しかできないのでロボットには信念(belief) $b(x)$ という確率分布を与えます。部分観測によってこの信念を精緻化するのが目的です。

近似モデルなので、ここでは信念の確率分布を次の２変数の十分統計量で表現できると仮定します。（正規分布の場合は平均と分散が十分統計量です）

　 $\bar{b} = f(b) = (argmax_x b(x) , H_b(x))$

$H_b(x)$ はエントロピー $H_b(x) = - \int b(x) \log b(x) dx$

問題によってはもっと多数の変数で十分統計量を表す必要があります。

信念確率の十分統計量を区分表 $\mathcal{\hat{P}}$ にします。部分観察から得た情報で縦と横の区分内に入る個数で、信念の十分統計量の表を更新で精緻化しています。

また信念と行動 $u$ の報酬の区分表 $\mathcal{\hat{R}}$ も得られた報酬で更新しています。

f:id:mabonki0725:20170903113657p:plain

この様な区分表はルックアップ・テーブルと云いSuttonは各セルの値を特徴量の重みとして強化学習を解いています。DQNでは深層学習で特徴量を抽出して、その重みをQ-Learningで解いていることになります。

(1.2) 結果

　左図の(a) (c) は普通のロボットの移動で、右図の(b)(c)は本手法AMDPによるロボットの移動です。右図では自分の位置をロストしない様に物体に沿って移動しています。

f:id:mabonki0725:20170903085055p:plain

(1.3) 感想

　下図もAMDPの結果です。これは監視ロボット(○）が進入者（●）の居る場所の信念を濃く表現しています。この場合は信念の十分統計量は6変数使っています。

侵入者がロボットとすると、監視ロボットと侵入ロボットとが敵対的に互いを出し抜く様な環境が考えられます。これを繰返すと両ロボットは知見を更新し能力を高める可能性があります。

敵対的なモデルは早期に自己能力を高める手法であることが分かります。

f:id:mabonki0725:20170903090807p:plain

2017-09-02

非深層型の進化戦略の強化学習の論文を読む

AI論文ロボテックス

ランニング30分　英語できず

(1) 非深層強化学習の進化戦略の論文を読む

「Evolution Strategies as a Scalable Alternative to Reinforcement Learning」

https://arxiv.org/abs/1703.03864

公開ソース https://github.com/MorvanZhou/Evolutionary-Algorithm

この論文は昨日記事にした深層強化学習のサーベイ論文で著者が高く評価したモデルである。

最近の強化学習や逆強化学習が全て深層モデルで構築されているが、本論の手法は深層学習を使わず、パラメータに摂動を入れ、大規模な並列処理で高速化とロバストな強化学習を達成するものである。

(1.1)方法

方策 $\pi(\theta)$ はパラメータ $\theta$ の関数とする。また確率 $p$ は $\psi$ で決まるとする時

$\theta \sim p_\psi$ でサンプリングされとする。

方策 $\pi(\theta)$ で行動した場合の得られた報酬を $F(\theta)$ とすると、

$\psi$ に関して以下の期待値を最大にする最適化モデルが定義できる。

　 $\eta(\psi) = E_{\theta \sim p_\psi}(F(\theta))$

この最適な $\psi$ を見つけるため以下の微分を考える。

　 $\nabla_\psi \eta(\psi) = E_{\theta \sim p_\psi}(F(\theta) \nabla_\psi \log p_\psi(\theta))$

ここで $p_\psi$ は偏差が $\sigma$ の正規分布であるとの仮定を置くと上式は次の簡単な式となる。

　 $\nabla_\psi \eta(\psi) = E_{\epsilon \sim N(0,I)} (F(\theta+\sigma \epsilon) \epsilon)$

この最適化モデルの $\psi$ の微分が得られたのでSDGにより

報酬 $F(\theta)$ を最大にする $\psi$ は以下アルゴリズムで求めることができる。

f:id:mabonki0725:20170902194706p:plain

進化戦略モデルは多数並列化することで局所解の解消や高速化を図っている。

このアルゴリズムは以下となる。

f:id:mabonki0725:20170902201509p:plain

さらに以下の工夫をしている。

・ $p_\psi$ が正規分布する仮定は安直過ぎないか→しかし旨くいく

・方策 $\pi(\theta)$ による報酬は実際にはm期先(パラメータ化）迄としている

・方策 $\pi(\theta)$ によって選択される行動 $a$ は選択子なので $\theta$ の近傍で微分できない。

　→ $\theta+\epsilon$ として摂動 $\epsilon$ を与え分布として微分可能にしている。

(1.2) 結果

　強化学習のベンチマークとして有名なMuJoCoでの深層強化学習のTRPOとの計算時間の比較である。大体半分程度で達成しているが、複雑の動きをするHopperやWalkerは6～8倍近くかかっている。

　ES(Evolutional Strategie)の並列化は1440　

　下表のEnviromentは強化学習の達成率

　TRPOの100%達成は500万ステップで学習

f:id:mabonki0725:20170902203313p:plain

f:id:mabonki0725:20170819120717p:plain

(1.1) 評価

　この大胆な方法は深層学習に比べ、かなり簡単なロジックと多数の並列処理によりロバストと高速化を達成しており、簡単な課題であれば早期に学習している。今後はこのモデルの採用が増えると考えられる。

2017-09-01

深層強化学習のサーベイ論文を読む

AI論文ロボテックス

ランニングできず　英語できず

深層強化学習のサーベイ論文を読む

「DeepLearning for Video Game Playing」https://arxiv.org/abs/1708.07902

最近までのPCゲームやテレビゲームを深層学習で解くAI技術について網羅的に解説した論文である。従って深層学習を使っても碁や将棋の様なボードゲームは対象外となっている。

下図の様な殆ど全ての深層強化学習を系統別かつ目的別に解説してあり大変な労作である。もし注目するモデルがあれば、この論文で検索すると以下のことが分る様になっている。

・モデルの概要

・モデルを発表した論文

・考案した動機や対象としたゲーム

・モデル開発が可能なプラットホーム

・継承したモデルと発展先のモデル

下図の様に深層学習としては2013年の偉大なDQNから全てが始まっている。しかしこのDQN前にはSuttonのSarsaモデルやこれを１段のニューロで解いた強化学習があったから出現できたのである。

f:id:mabonki0725:20170901200747p:plain

上図の重要な点は色分けの区分である。これはDQNが解けなかった分野を示しており、DQNに様々な工夫を加えた系統図になっている。（同心円は年代を示す）

色分け分野の説明を以下に記す（中括弧は開発プラットホーム名）

・茶色：Atariゲーム(報酬が直ぐ得られるゲーム） {ALE}

・橙色：Montezuma's Revenge (報酬が得にくいゲーム）

・黄色：Racingゲーム（運転ゲーム)　{TORCS}

・青色：Doom（シューテイングゲーム) {VizDoom}

・緑色：MineCraft (探検・探索ゲーム）{Minecraft}

・紫色：StarCraft(集団対戦型ゲーム）{StarCraftⅡ}

・膿灰：２DBillard (物理シュミレーションモデル）

・薄灰：Tex-baseGame（自然言語で指示を与えるゲーム）

f:id:mabonki0725:20170901214713p:plain

下表では上記の分野毎に対象ゲームとその解法モデル名とそのネットワーク構成及び価値関数の算出方法が示されている。（緑枠は本論文での論文参照番号）

f:id:mabonki0725:20170901220319p:plain

自分なりの印象を下記に示す。

・敵対的（Adversarial)モデルが存在しないことが不思議

　Agentが知識を獲得していくには、対戦相手との競争の中で互いを上まわる戦略を

　練ることで知識を拡大していくのが合理的と考えられるが、これだけのサーベイ論文でも

　存在しないのは奇異である。

・最近発表されたEvolutional Approachが、かなり有望視されている。

　これは確率勾配法ではなくノイズを分析して学習する方法の様である。

「Evolution Strategies as a Scalable Alternative to Reinforcement Learning」

https://arxiv.org/abs/1703.03864

・特徴量選択の検討が少ない

　やはりこの中で最も優秀なモデルはUNREALとしている様である。

　確かにこのモデルには次の様々な深層学習が統合されている。

　・並列処理(A3C)

　・仮想出現回数(Pseud Count)

　・経験メモリー (Reuse Memory)

　・外部記憶 (External Memory)

　しかし状態を端的に表す特徴量の把握手法がもっと研究されてもよいと考えられる。

・倉庫問題の様な長期計画問題に対するモデル記述が殆どない。

　これはこの問題が直近になって発表される様になったためと考える。

2017-08-31

DeepMindの強化学習での歪んだ報酬の対処の論文を読む

AI論文ロボテックス

テニススクール90分　英語できず

DeepMindの強化学習での歪んだ報酬の対処の論文を読む

[1705.08417] Reinforcement Learning with a Corrupted Reward Channel

この論文は報酬が誤解釈や観測失敗やノイズがある場合の対処を論じたもので、かなり長文で数学よりの話である。数学的な理解は何れ行いたいが、ここでは自分なりの要約を述べたい。

次の動画は有名なボートレースゲームで誤った報酬を観測した例である。よく見ると一隻だけ異常な短絡ループで走行している。この船は下図の左端の報酬関数を掴んでおり、こここから逃れられない状態にある。

CoastRunners 7 - YouTube

f:id:mabonki0725:20170831120253p:plain

まず歪んだ報酬のマルコフ決定過程CRMDP（Corrupted Reward Marcov Dicision Process)を数学t的に定義している。

そしてCRMDPではNo-Free-Lunch定理を用いて強化学習には一般解が無い事を証明し、対象問題別にモデルを構築する必要を説いている。

そこで歪んだ報酬でも適正化できる２つの方法を提案している。

・ $decoupled RL$ ：様々な状態の報酬を観察して、多面的に解く方法

・ $Quantilisation$ ：粒子化

(1) $decoupled RL$ では下記のモデルでは様々な状態からデータが取得でき比較することができる。

・IRL(Inverse RL)：熟練者の行動データからの逆強化学習モデル

・LVFS(Learning Value Fron Stories)：人間の行動を真似るモデル

・SSRL(Sub-Supervised RL)：一部だけをAgentに教えるモデル

理論としては下図の様に状態の相違と報酬の相違を考慮してベイズで解けば真値が判明するというものである。

f:id:mabonki0725:20170831122547p:plain

(2) $Quantilisation$ は粒子化によって高い報酬を探すものである。

下図では $\delta$ 以上について細かくサンプリングして穴を見つけている。

f:id:mabonki0725:20170831201618p:plain

感想

$decoupled RL$ は、部分観察マルコフ決定過程POMDP(Partial Observed Marcov Process)で確立されている理論の応用である。自動車運転の例でみると様々な場所から部分的に観測された位置情報でも、観測にノイズがあり自動車の走行距離や移動方向にノイズがあっても正しく把握できる理論である。

また $Quantilisation$ 粒子化は、粒子フィルターとして自動運転に使われている。

しかも複合観測と粒子化は統合されてSLAMとして既に実用化されている。

今回の歪んだ報酬による強化学習の適性化は、自動運転技術を参考にした様に思える。

2017-08-30

Abbeelの計画問題の強化学習の論文を読む

AI論文ロボテックス

ランニング30分　英語できず

Abbeelの計画問題の強化学習の論文を読む

「Learning Generalized Reactive Plicies using Deep Neural Network」

https://arxiv.org/abs/1708.07280v1

ロボット学の第一人者USCバークレイのPieter Abbeelが参加している倉庫ゲームを扱った強化学習の論文である。下記はこの論文の成果動画である。

youtu.be

learn2plan

DeepMindも下記で同じように倉庫問題にチャレンジしていている。こちらは長期戦略の深層RL(model-based)と画面による深層RL(model-free)の合せ技で計画問題を解いている。

mabonki0725.hatenablog.com

こちらは経験的な知識(Heuristic)を逆強化学習として計画問題として解いている。この様にDeepMindと違うのは、DeepMindは計算機が自分自身で考える所謂シンギュラリティを目指しており、一方Abbeel達はロボットの実用化を目指していて汎用的な解法には拘っていないためと思われる。

・手法

　知らなかったがA*(Astar)の様に計画問題を専門に解くシステムがある様で、このシステムを使ったログデータを熟達者のデータとして用い逆強化学習で強化学習の方策問題を解いている。計画問題のシステムとしてASP2000で優勝したFast-Forward(FF)モデルの結果をログデータとして採用している。

http://www.cs.toronto.edu/~sheila/2542/w06/readings/ffplan01.pdf

ここでは逆強化学習をGRP（Generlized reactive plolicy)と称しCNN型の深層学習で解いている。

このネットワークは以下の特徴を持つ

・GPRでは現在とゴールの２画面を指定すると、ログデータより多数の経路をboostrap法でサンプリングしている。

　深層ネットワークはこのサンプリング経路を基に行動予測の訓練をしていると思われる。

・途中で枝分かれして、行動の予測とゴールまでの必要な手数の予測をしている

・枝分かれした層には直接観察データのデータも混ぜてCNN処理をしている。

f:id:mabonki0725:20170830114442p:plain