これまでの研究業績と今後の抱負

浅井政太郎東京大学総合文化研究科 学振DC2

発表要旨

背景

　Fully Automated Cyclic Planning for Large-Scale Manufacturing Domains※1. ICAPS14.

　Solving Large-Scale Planning Problems by Decomposition and Macro Generation※1. ICAPS15.

　Tiebreaking Strategies for A* Search: How to Explore the Final Frontier※1. AAAI16. (JSAI 学生奨励賞)

　Tie-Breaking Strategies for Cost-Optimal Best First Search※1. JAIR 58 (2017): 67-121.

　Exploration Among and Within Plateaus in Greedy Best-First Search※1. ICAPS17.

　Efficient Optimal Search under Expensive Edge Cost Computation※2. IJCAI17.

　Classical Planning in Deep Latent Space: From Unlabeled Images to PDDL (and back)※1. KEPS17.

今後の研究計画

※1 Masataro Asai, Alex Fukunaga

※2 Masataro Asai, Akihiro Kishimoto, Adi Botea, Radu Marinescu, Elizabeth Daly M, and Spyros Kotoulas

1 背景 – 自律機械とは?

1.1 誰?

1.1.1 誰?

1.1.2 誰?

1.1.3 誰?

1.1.4 誰?

1.1.5 誰?

1.2 なぜ自律機械? 社会的意義 — 例えば、操縦士が足りない!

そのままでは役に立たない!

1.2.1 「人」は簡単に増やせない – Human Resource and Training

✘ 時間がかかる: 訓練に＞100時間, 必要な時だけ増やす のは不可能
✘ ￥￥￥￥ がかかる: 訓練官、訓練場所、訓練用具
✘ 技術は 維持が重要: 定期的な再訓練、長期的コスト
✘ 平時は無駄な技術: 普段は意味がない – 無駄な費用!

1.3 自律機械のための自動プランナ (≠ モータ制御)

1.4 自律機械のための自動プランナ (≠ モータ制御)

1.5 自律機械のための自動プランナ (≠ モータ制御)

1.6 古典プランニング問題 (決定的,完全情報) – Blocksworld

非古典的なさまざまな拡張

(並列アクション,POMDP,HTN… どのAIの教科書にものっている)

1.6.1 アクション = 条件付き状態遷移

アクション (move ?X ?Y)

?X, ?Y : 変数。値 BLOCK-A, BLOCK-B などを適用して使う

条件と効果で構成される

条件 : 実行に必要な条件を表す命題

　(clear ?X) : 積み木 ?X の上が空

　(clear ?Y) : 積み木 ?Y の上に空

効果 : 前後の状態の差分を表す命題

　(on ?X ?Y) を追加 : ?Y の上は ?X

　(clear ?Y) を削除

モデリング言語 PDDL で記述

(:action move
 :parameters (?X ?Y)
 :preconditions
   (and (clear ?X)   ; (1)
        (clear ?Y))  ; (2)
 :effect
   (and (on ?X ?Y)   ; (3)
        (not         ; (4)
         (clear ?Y))))

1.6.2 プランニング = グラフ探索

ノード : 状態 = 命題の集合 ⇒ (on A B), (clear A) など

辺 : アクション ⇒ (move A B) 等

*1 [Helmert, 2006] [Richter, 2010]

1.7 Xerox PARC Printer: Hypermoduler Systems

Crawford, Lara S., et al. "On-Line Reconfigurable Machines." AI Magazine 34.3 (2013): 73-88.

1.8 プランニング(自動行動計画)分野の位置づけ

2 査読論文実績 (抜粋)

AAAI, IJCAI: AI一般の1st-tier, ICAPS: プランニング専門の1st-tier, JAIR: トップジャーナル

ICAPS14 (採択率33%) (IHI共同研究) Fully Automated Cyclic Planning for …

ICAPS15 (採択率33%) Solving Large-Scale Planning Problems by Decomposition …

AAAI16 (採択率26%) (JSAI 学生奨励賞) Tiebreaking Strategies for A* Search: …

JAIR17 (採択率12%) Tie-Breaking Strategies for Cost-Optimal Best First Search.

ICAPS17 (採択率33%) Exploration Among and Within Plateaus in Greedy Best-First Search.

IJCAI17 (採択率25%) (IBM Research 応用研究) Efficient Optimal Search under …

KEPS17 (採択率60%) Classical Planning in Deep Latent Space: From Unlabeled Images …

応用研究、基礎研究共に経験あり

2.1 業績1: 査読付き国際学会 ICAPS14 (採択率33%) (IHI共同研究)

2.2 業績2: 査読付き国際学会 ICAPS15 (採択率33%)

2.3 業績3: 査読付き国際学会 AAAI16 (採択率26%)

2.4 業績4: 査読付き論文誌 JAIR (採択率12%)

2.5 業績5: 査読付き国際学会 ICAPS17 (採択率33%)

2.6 業績6: 査読付き国際学会 IJCAI17 (採択率25%) (IBM共同研究)

3 産業技術総合研究所で行いたい研究 (短期目標)

Neural-Symbolic複合システム

による

次世代AIシステム

の研究

3.1 深層学習

3.2 Q. 深層学習と記号的AI はどう違う?

A. レイヤが違う

機械学習・Neural Networks == 関数近似

for 認識・反射

入力は Subsymbolic (連続値)

画像、音声、非構造化テキスト:
感覚的知能:

　 反応, 直後の行動の決定

パブロフの犬 : 餌を認知→よだれ

自動運転 : 赤信号,人 → 止まる.

翻訳 : 文章 → 文章

囲碁局面の評価関数 : 局面 → 勝率

☺ 効率よく 1-to-1 mapping

☹ 単純作業

推論・探索

for プランニング・ゲーム・定理証明

入出力は Symbolic

論理オブジェクトルール
論理・推論による知能:

　 未来に渡る 戦略の決定

　 (戦略 = 行動の 列や木)

レスキューロボ : ゴール = 被災者生存

証明器 : ゴール = QED

コンパイラ : 命令列の生成

囲碁,将棋 : ゴール = 勝利

☺ 順序制約+複雑な作業

AlphaGo = Subsymbolic (DLNNによる評価関数) + Symbolic (MCTSによる探索)

3.3 記号的AIによる論理推論の重要性

3.4 業績7: 査読付きワークショップ KEPS (採択率60%)

3.4.1 業績7: 査読付きワークショップ KEPS (採択率60%)

3.4.2 業績7: 査読付きワークショップ KEPS (採択率60%)

3.5 短期目標: このシステムを様々に拡張

3.6 長期目標: パラダイムシフト

3.7 産業応用: 深層学習+記号的推論 = ブレークスルー

人工無能以上の対話ボット

人工無能 : 従来型対話ボットの総称
- 反射的応答 = 論理を持たない
- Apple Siri (人の書いた返答データベース)
- Microsoft りんな (学習した返答ルール)
テキスト → 論理表現 → 記号的推論 → 返答
- 論理に基づき 思考する ボットへ

4 めざす研究者像

分野の創始者 / 1000以上のcitationをもつ重要な発見の著者

10年後に AIMA (AIの超有名な教科書) に乗る内容
いま興味・関心がある分野とは限らない
- やりたいことはいくらでもある (進化計算/学習/知識表現/HCI)
今の自分は小粒研究者 → 産総研の一流ビッグネームへ。

5 まとめ

難関国際会議ICAPS14(33%) Fully Automated Cyclic Planning for Large-Scale Manufacturing Domains.
1. 任意の問題から1種類の繰り返し構造を自動で検出
2. 工場での製造スケジューリング (x1000 高速化, 探索空間 10⁶ → 10²⁷⁴)
難関国際会議ICAPS15(33%) Solving Large-Scale Planning Problems by Decomposition and Macro Generation.
1. 複数の繰り返し構造をより柔軟・汎用に組み合わせる手法
2. ベンチマークセット全体で高速化 (x3-4 高速化, 探索空間 10⁷ → 10²⁸)
難関国際会議AAAI16(26%) Tiebreaking Strategies for A* Search: How to Explore the Final Frontier.
1. コストゼロの辺がグラフ探索に引き起こす問題を解決 (探索空間 10⁶ → 10⁸⁸) (JSAI 学生奨励賞)
難関論文誌JAIR(12%) Tie-Breaking Strategies for Cost-Optimal Best First Search.
1. (3.) に加えタイブレーキングと非最適コスト探索の関連性を指摘, さらに性能向上
難関国際会議ICAPS17(33%) Exploration Among and Within Plateaus in Greedy Best-First Search.
1. プラトー内均一化とプラトー間均一化の直交性 : 統一的フレームワーク
2. 非最適コスト探索をフラクタルを用いて 性能向上
難関国際会議IJCAI17(25%) Efficient Optimal Search under Expensive Edge Cost Computation.
1. 辺コストの動的計算が必要な問題に対して高速な最適アルゴリズムDEA*
国際会議付属ワークショップ(60%) Classical Planning in Deep Latent Space: From Unlabeled Images to PDDL (and back). (Knowledge Engineering for Planning and Scheduling (KEPS) Workshop)
1. 画像から命題を自動生成 して記号的AIで組合せ最適化問題を解き、画像で出力するシステム

6 付録

6.1. 既存研究について
6.2. AIの倫理について
6.3. ベンチャー?
6.4. ライフワーク: 人はより自由に創作/研究できるべきである
6.5. LatPlan 関連

6.1 既存研究について

6.1.1 その研究は…

	評価	オリジナリティ	過去のインパクト	未来のインパクト	動機
ICAPS14	難関学会	ループの自動検出	超大規模問題に初めてタックル	産業応用	人間プログラマでは追いつかない
ICAPS15	難関学会	問題分割統合手法	より汎用	産業応用	より一般化したい
AAAI16	査読者2/3 人に絶賛	タイブレークで性能改善	70年代からの定説を覆す	コスト0は実応用によく使われる	下界関数以外で改善したい
	(+ JSAI学生奨励賞)
JAIR17	トップジャーナル	タイブレーク=非最適探索		最適+非最適探索の融合	タイブレークを理解したい
IJCAI17	難関学会	問題設定(辺コストが未知)		医療福祉での実問題	全ての辺を計算できない
ICAPS17	難関学会	フラクタル	均一化手法の整理	高速化	理解したい/性能向上
KEPS17	査読者「重要な方向性」	画像から自動で命題を生成	シンボルグラウンディング	ニューラル・記号複合システム	記号システムの適用範囲の拡大

6.1.2 古典プランニングを研究する意義は?

6.1.3 Explicit Graph と Implicit Graph との違い

カーナビ、ソーシャルグラフなど : Explicit Graph

グラフ全体がメモリ(〜数ペタバイト)または二次記憶(〜数ゼタバイト)に収まる

参考: 2012年の全世界のデジタルデータ: 数ZB (1ZB = 10²¹ バイト)

AI and Web, social graph

プランニングにおける探索グラフ : Implicit Graph

地球上の全計算資源を集めても二次記憶に入らない

グラフのノード数は状態変数に対して 指数的に増加

動的メモリ確保+優れた枝刈りをしないと問題が解けない

探索空間サイズの例:

3x3x3のルービックキューブ: 4.32 x 10¹⁹ = 4 EB

4x4x4のルービックキューブ: 7.40 x 10⁴⁵ ＞ 10²⁴ ZB

5x5x5のルービックキューブ: 2.83 x 10⁷⁴

Gantz et al. "The digital universe in 2020: Big data, bigger digital shadows, and biggest growth in the far east." IDC iView: IDC Analyze the Future 2007 (2012): 1-16.

6.1.4 第五世代コンピュータとの違いは?

第五世代コンピュータ : 並列推論機械(Prologベース,ハードウェア,OS)

ハードの問題ではなく、根本的なソフトウェア技術、 探索技術 が未発達だった

第五世代	現在
後方全探索 +バックトラック	前方ヒューリスティック探索
問題ごとに手書きのcutで枝刈り	汎用下界関数
Prologベース	C/C++で高度に最適化されたプログラム
	State packing, 決定木, mutex…

今はベンチマーク問題 1104問 のうち 5分で 800問 前後解ける

仮に 当時のソフトウェア を 現在のハードウェア で動かしたとしても、 100問も解けない

6.1.5 似たような研究は誰がやっているか

ICAPS, SoCS : 例年200人-300人の参加者を集めており大変盛況,

AAAI, IJCAI : プランニングに関する論文は例年数十本採択 Proceedingsの一つの章

JAIR, AIJ (トップジャーナル) : 同様に多い (JAIR Volume 54: 12本中 2本がプランニング)

主な研究室:

MIT CSAIL (Brian Williams), Carnegie-Mellon,

NASA (NASA Ames および NASA/Caltech JPL のそれぞれに20名以上の研究者)

欧州宇宙機関(ESA)

King's College London, U. Freiburg, U. Bazel, U. Toronto, U. Ben-Gurion

指導教員は NASA JPL AI Lab の元メンバー

6.1.6 国内で誰が似たようなことをやっているか

この専門分野をやっている人はほぼいない

石田亨先生 (京都大学) — 以前は日本のA*系の探索手法の代表者, R. E. Korf と共著

R.E. Korf — Alex Fukunaga — 浅井政太郎

岸本先生 (探索) (東工大 → IBM Research Ireland)

少し離れているが似ている研究というと

SATソルバ, ASP(解集合)ソルバ, CPソルバ系, 推論系 – logic and reasoning : 田中哲朗先生 (総合文化研究科), 鍋島英知先生 (山梨大), 田村直之先生, 平山勝利先生 (神戸大), 田沼先生 (東工大)
井上克己先生 (NII) — Lemma Reusing for SAT based Planning and Scheduling (ICAPS10)
AAMAS マルチエージェント, CSP : 横尾誠先生 (九大)
ERATO グラフ探索(explicit graph)系, 大規模知識処理系 : 河原林健一先生 (NII), 秋葉先生, 湊先生(北海道)
ゲーム系金子先生 (総合文化研究科)

6.1.7 汎用性を失わずに解く?

No Free Lunch 定理: 最適化アルゴリズムの性能は 全問題の平均を取れば 全て同じ

Q. NFL定理のもとで「汎用性を失わずに高速に解く」というのは不可能?

A. NFL定理は確かにそのように主張するが、プランニング分野の意味する「汎用性」は

実問題(人間にとって有意義な問題の集合) における汎用性である。

全プランニング問題の集合 ⊇ 人間にとって有意義な問題の集合

従って、 全問題の平均を取れば という前提が成り立たない。

6.2 AIの倫理について

研究内容は漠然とした「AI」のうち グラフ探索 の研究
AIの目的はプランナのゴールで定義される
- AI自体は善悪の判断を行わない
- 人が与えるゴールについての倫理的問題 (→ 兵器使用)
価値判断は与えられる入力の中にある = 使用者の価値観/データのバイアスを反映
悪用の問題はある。しかし、自分としては、災害救助ロボットなど、人道的な応用を目指している

6.3 ベンチャー?

ベンチャーで大切なのは顧客速さ アイディア

何を やらない か:

研究目的のベンチャー if all you have is a hammer, everything looks like a nail
請け負い / スモールビジネス (国内ベンチャーの多く)
多目的の複雑な製品 / 過剰サービス ()

おそらく生活に密接した自動エージェント

6.4 ライフワーク: 人はより自由に創作/研究できるべきである

上記の目標を達成したらの話

人/機械は、 ひとつの課題でキャッシュを有効利用 すると 最大パフォーマンス
今でさえ distraction が多すぎる (プレゼン準備, 事務書類, 論文締め切り)
プレゼン、論文は 知の伝播/蓄積 のために必要だが、 研究の本質 ではない
プレゼン、論文の形式記述化と自動生成
- 主張を適切な順序で並べるプランニング問題
- 現代の研究活動で最も「時給単価が高い人間の手作業」を要する分野

6.5 LatPlan 関連

6.5.1 AIプランニングの Killer App

人が高価or不可能な作業

原発, 宇宙空間, 火星, 深海

正しさと最適性の理論保証が必要なミッションクリティカルシステム

製造システム、運送 (時間=お金)

人工衛星 (燃料使いきれば運用終了)

間違った解は許されない

思考過程を説明可能なシステム

レスキュー・宇宙船 (人間の安全がかかっている)

6.5.2 知的機械を作る上で深層学習の果たす役割

6.5.2.1 知的機械を作る上で深層学習の果たす役割

6.5.2.2 知的機械を作る上で深層学習の果たす役割

6.5.2.3 目的達成型機械

反射的に動くロボットでは 複雑なゴールを設定できない

瓦礫に埋もれた 骨折・出血 している被災者を なるべく早く 病院に運ぶ。

救急車 を先に呼んでおき、 患者を傷つけない ように, 素早く , 瓦礫を 崩れないよう に どけて, 止血し, 当て木 し, 担架に乗せ て, ちょうどきた 救急車 に 隊員と協力 して運び入れる。

→ 目的達成/熟慮型の知能が必要

熟慮: deliberation の訳

6.5.2.4 知的機械を作る上で深層学習の果たす役割

6.5.2.5 知的機械を作る上で深層学習の果たす役割

深層学習でカバーできない部分には記号的AI(プランニング)が必要

6.5.3 業績7: 査読付きワークショップ KEPS (採択率60%)

6.5.4 業績7: 査読付きワークショップ KEPS (採択率60%)

6.5.5 既存の有名システム

AlphaGo = Subsymbolic (NNによる評価関数) + Symbolic (MCTSによる探索)

ただし ドメイン依存 – 囲碁に特化, "マス目"や"石"といった概念をハードコード
膨大な棋譜が必要 — 運用データがない環境(e.g.火星)には適用不能
人って模範解答がないと行動できませんか? 真の自律機械は前例無しでも行動可能

DQN = Subsymbolic (DLNN) + 強化学習 (DLNN)

様々な Atari Game につかえる汎用フレームワーク (Invader, Packman…) だが

RLのActing: 学習したpolicyに従ってgreedyに行動
Atariゲームは 脊髄反射で生き残ることが可能 → 複雑な論理思考はいらない!

6.5.6 既存システムとの違い (追加)

NNで直接問題を解くシステム

TSP [Hopfield and Tank, 1985], NeuroSolver [Bieszczad and Pagurek, 1998], Neural Turing Machine [Graves et. al., 2014]
- NNで解くが、入力はシンボリック (ニューロンが人の与えた状態変数に対応)
- 完全性、最適性などの保証なし

NNを認識でなく探索中の枝刈り用に使うシステム

AlphaGo [Sievers 16], Rubik Cube [Arfaee et al., 2011], Planning [Satzger and Kramer, 2013]
- LatPlan は NNを探索の外で使う

6.5.7 Learning from Observation との違い

主にロボットの経路探索 (ローレベル制御) [Argall et al., 2009]

ボードゲームの学習だが「マス目」など強い仮定 [Barbu et al., 2010; Kaiser, 2012; Kirk and Laird, 2016]

Action Segmentation problem がある

「映像の観察」を中心とするので、いつアクションが始まる/終わるのか解らない
LatPlan には関係なし

6.5.8 Gumbel-Softmax

6.5.8.1 Gumbel-Softmax

6.5.8.2 Gumbel-Softmax: Differential Approximation of Gumbel-Max

It uses annealing to approximate discrete vectors

Gumbel-Max: Method for drawing one-hot vector sample ($z$) from category probability ($x$)

E.g.: $x=[0.1, 0.1, 0.8] \rightarrow z = [1,0,0] \text{or} [0,1,0] \text{or} [0,0,1]$
$z = \text{ GumbelMax}(x) = [ i == \arg \max_j (\text{ Gumbel}(0,1)+\log x_j) \; ? \; 1 : 0 ]$
argmax is non-differentiable → softmax approximation (differentiable)
$z = \text{ GumbelSoftmax}_\tau (x) = \text{ Softmax}( [\text{ Gumbel}(0,1)+\log x_j]/\tau )$
Temparature $\tau \rightarrow 0$, $z\rightarrow \text{one-hot vector}$

Maddison et. al., 2014

6.5.9 LatPlan実装

詳しくは論文を

Keras + TensorFlow

1764(42x42)

[→FC(4000,ReLu)→Batchnorm→Dropout(0.4)] × 2

→FC(49,GumbelSoftmax) (variational loss)