AI_ML_DL’s diary

人工知能、機械学習、ディープラーニングの日記

Program Synthesis(ARCに挑戦!)

Program Synthesis

Program synthesis

S GulwaniO PolozovR Singh - Foundations and Trends® in …, 2017 - nowpublishers.com
 
4月26日~修正・追記
 
ARCに挑戦!
あと1か月:
The Measure of Intelligenceを読みながら進む。
 
ステップ00
taskは、1対のgridからなるdemonstration exampleによって暗示される。
1対のgridとは、1組のinput gridとoutput gridのことである。
通常、1対のgridではtaskが確定しないので、1組のgrid対が示される。
input gridとoutput gridを比較することによって、taskを決め、solverを構築する。
<taskを決め、solverを構築するプログラムの構築>
Measure of intelligenceの53ページに示されているARC solver作成手順では、
最初に、(800セットの)すべての訓練データに対応できるプログラム(taskとsolverがセットになったもの)を作成する。
(「学習する」「考える」プログラムではなく、ヒトが課題毎に作成したプログラム)
Core Knoledge priors : Objectness priors, Goal-directedness prior, Numbers and Counting priors, Basic Geometry and Topology priors
プログラムが、期待通りのグリッドを出力したとき、ヒトは、コンピュータがこれらのpriorを持っていて、それらをベースに、reasoningやabstractionを適切に適用することによって、正しいグリッドを出力することができたのだと感じるかもしれない。
そのようなプログラムは、まだ、存在しないだけでなく、その萌芽すら認められないといえるかもしれない。
<作りたいプログラム>
幼児はARCに対応できない。園児になると、input gridとoutput gridの違いを認識して、どこが違うかを指し示すことができるようになる。小学生になると、理解できる課題が増えていくだろう。ヒトは成長するにしたがって、core knowledge priorsを段階的に獲得していくだろう。
人工知能を目指すプログラムの開発においては、core knowledge priorsをプログラムに組み込むのではなく、プログラムがcore knowledge priorsを獲得できるようにしなければならない。
ヒトはどのようにしてcore knowledge priorsを獲得しているのだろうか。
具体的に考えてみよう。
 
 
 
 
test gridを含む訓練グリッドに対して、用意しておいたtaskとsolverの中から、最も類似したtaskとsolverを探し出す。
探し出したtaskとsolverは、そのままでは使えず、変更が必要になる。
input gridとoutput gridを入力したら、taskとsolverが出力されるプログラムが必要である。
input gridとoutput gridからtaskを推定して分類するプログラムが必要である。
ヒトはinput gridとoutput gridを一瞥するだけで、taskの概略を把握することができる。一瞥でもじっくり眺めるのでもよいのだが、そのときヒトは何をどのように見ているのだろうか。
ヒトは、グリッドの形状と色と分布を見ている。
プログラムで同じことをできるようにするためには、入力された1つの行列を見るだけではなく、カラー別の行列、まとまった形状を把握できる行列(3x3のグリッドパターンや、結合して特定の形状をしているものなど)などを用意する必要がある。
いわゆる特徴量を複数見つけ出して記憶させる必要がある。 
 
ステップ0
準備:
2次元配列において、同一の数字がつくる構造体を、特徴量として把握する。
入力画像から把握した構造体を特徴量、I1,I2,I3,・・・とし、訓練出力画像から把握した構造体を特徴量O1,O2,O3,・・・とする。
カラー画像を3原色の強度で表現しているように、ARCパターンを、10原色の0,1強度で表現してみようか。
色別に10チャンネル設定することによるメリット、デメリット:
 単位構造が単色の場合、特段のメリットはなさそう
 構造体の移動がある場合、静止した構造と移動した構造を見分けやすい
 ノイズの判定がしやすくなるかもしれない
 点と点を線状に結ぶ場合、変化が見やすくなる
 繰り返し構造を構築する場合、作業が容易になるかもしれない
 灰色による分離帯の識別が容易になりそう
 新規に形成された構造体が分かりやすい
最終的な出力画像を得るための演算方法 
命令を作る:
 上下左右の定義
 移動の定義
 追加の定義
 削除の定義
 パターン生成の定義 
  1点ごとの移動の定義
 構造体の移動の定義
 構造体の回転:回転中心と回転角
 構造体の反転:上下反転、左右反転
 構造体の鏡像作成、鏡像追加
入力と出力の配列は0から9の数値で埋め尽くされる。
途中の演算は、チャンネルごとに行う
途中の演算は、チャンネル間で行う
ステップ1
入力画像と訓練出力画像を入力する。
ステップ2
入力画像のサイズと訓練出力画像のサイズ比から、作業内容を推測する。
画像のサイズ比(1、1以上、1以下)から、作業内容を絞り込む。
入力画像の形状から、作業内容を絞り込む。
入力画像と訓練出力画像の差異(形状変化)から、作業内容を絞り込む。
入力画像と訓練出力画像の差異(色変化)から、作業内容を絞り込む。
入力画像と訓練出力画像の差異(形状変化と色変化)から、作業内容を絞り込む
ステップ3
入力画像と推定作業内容から出力画像を作成し、訓練出力画像と比較する。
出力画像と訓練出力画像の違いから、作業内容を修正する。
入力画像と修正作業内容から出力画像を作成し、訓練出力画像と比較する。
 
自動プログラムには、いくつかのパターンが考えられる。
1.自動で、訓練データを解析して、1からプログラムを作る方法
2.自動で、訓練データを解析して、あらかじめ作成しておいたサブルーチンを呼び出してプログラムを作る方法
3.自動で、訓練データを解析して、あらかじめ作成しておいたあらゆる訓練データに対応できるプログラムから適切なプログラムを選ぶ方法
 
*3.は、邪道かと思ってしまうが、そうではない。これが出来ることが、プログラム合成において最も重要なことである。最終目的を達成するためには、これをクリヤしておかなければならない。
*プログラム合成は、あらゆるタスクに対応できることが、大前提となる。
*あらゆるタスクに対応するには、ドメインの特定が必要である。
ドメインの特定だけでは不足で、ドメイン内のタスクの範囲の制限も必要になるかもしれない。
*始めのうちは、ドメインもタスクも、プログラム合成が実現しやすい状態、すなわち、ドメインもタスクも最小単位から始めるのが良いかもしれない。
*たとえば、ARCのタスクでいえば、グリッドサイズの変化も、パターンの位置、パターンの形状の変化はなく、パターンの色が初期のグレーから赤に変化するタスクに制限し、グリッドサイズは9x9、パターンサイズは3x3くらいから始める。ドメインもタスクも、自動プログラムを作ることができるところまで縮小して検討してみることから始めるしかないだろう。
*簡単なものから複雑なものへ。
 
この論文、Google Scholarでは、概要と序文約10ページくらいしか出てこないが、program synthesisでGoogleで検索すると、この論文がトップに現れ、microsoftのサイトからダウンロードして、全文を読むことができる。
 
1 Introduction 3
1.1 Program Synthesis . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Dimensions in Program Synthesis . . . . . . . . . . . . . . 7
1.4 Roadmap . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Applications 15
2.1 Data Wrangling . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Graphics . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Code Repair . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4 Code Suggestions . . . . . . . . . . . . . . . . . . . . . . 30
2.5 Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.6 Superoptimization . . . . . . . . . . . . . . . . . . . . . . 32
2.7 Concurrent Programming . . . . . . . . . . . . . . . . . . 34
3 General Principles 37
3.1 Second-Order Problem Reduction . . . . . . . . . . . . . . 37
3.2 Oracle-Guided Synthesis . . . . . . . . . . . . . . . . . . . 39
3.3 Syntactic Bias . . . . . . . . . . . . . . . . . . . . . . . . 45
3.4 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . 53
4 Enumerative Search 57
4.1 Enumerative Search . . . . . . . . . . . . . . . . . . . . . 57
4.2 Bidirectional Enumerative Search . . . . . . . . . . . . . . 62
4.3 Offline Exhaustive Enumeration and Composition . . . . . 63
5 Constraint Solving 65
5.1 Component-Based Synthesis . . . . . . . . . . . . . . . . 67
5.2 Solver-Aided Programming . . . . . . . . . . . . . . . . . 71
5.3 Inductive Logic Programming . . . . . . . . . . . . . . . . 75
6 Stochastic Search 77
6.1 Metropolis-Hastings Algorithm for Sampling Expressions . 77
6.2 Genetic Programming . . . . . . . . . . . . . . . . . . . . 80
6.3 Machine Learning . . . . . . . . . . . . . . . . . . . . . . 84
6.4 Neural Program Synthesis . . . . . . . . . . . . . . . . . . 85
7 Programming by Examples 91
7.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . 91
7.2 Version Space Algebra . . . . . . . . . . . . . . . . . . . . 93
7.3 Deduction-Based Techniques . . . . . . . . . . . . . . . . 95
7.4 Ambiguity Resolution . . . . . . . . . . . . . . . . . . . . 100
8 Future Work 107
Acknowledgements 111
References 113
 
 

f:id:AI_ML_DL:20200317091349p:plain

style=116 iteration=1

f:id:AI_ML_DL:20200317091439p:plain

style=116 iteration=20

f:id:AI_ML_DL:20200317091758p:plain

style=116 iteration=500