タイトル

BUSTLE: Bottom-up program-Synthesis Through Learning-guided Exploration

arXiv, Submitted on 28 Jul 2020

[2007.14381] BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration

手法の入出力

手法の入力

入出力例の集合
- 論文上では $\mathcal{I}$ と $\mathcal{O}$ の２つ組という雑な表現になっているが、実際は任意の $i \in \mathcal{I}$ に対してユニークに $o \in \mathcal{O}$ が定まるものとしている。

手法の出力

プログラム
- ただし、任意の $(i, o) \in (\mathcal{I}, \mathcal{O})$ に対して $P(i) = o$ を満たす。

DSL の定義

プログラム合成手法では、DSL (Domain-Specific Language、ドメイン固有言語) をドメインごとに定義し、その上でプログラムを構築するアプローチが一般的である。本手法では、文字列を操作するための DSL を独自に定義している。

f:id:t-keita:20200916013428p:plain

入出力例からのプログラム合成 (Programming by Example) の実用化の代表的である、Excel に搭載されている FlashFill で用いられる DSL よりも複雑な文法となっており、課題設定として難易度の高いものとなっている。

Property Signatures

property signatures は入出力例を特徴ベクトルに変換する手法である。機械学習をプログラム合成に適用する研究は近年盛んに行われているが、property signatures は ICLR2020 で発表されたばかりの手法である。

Learning to Represent Programs with Property Signatures | OpenReview

まず、property signatures を具体例を用いて説明する。以下の図 (Listing 1) の io_pairs は入出力例であり、p1, p2, p3 は入出力例を引数にとって Mixed, AllFalse, AllTrue のいずれかを返す関数である。たとえば p1 は「入力文字列が出力文字列に含まれているか」を返す関数である。p1, p2, p3 は入出力例 io_pairs を引数にとり、それぞれ Mixed, AllFalse, AllTrue を返す。この [Mixed, AllFalse, AllTrue] というリストが io_pairs の property signatures である。

f:id:t-keita:20200916013907p:plain

もう少し厳密に書くと、入力 $\mathcal{I}$ と出力 $\mathcal{O}$ の型をそれぞれ $\tau_\text{in}$ , $\tau_\text{out}$ とすると、 $(\tau_\text{in}, \tau_\text{out}) \rightarrow \texttt{Bool}$ という型をもつ関数を property とする。各入出力例に property を適用した結果を集約することで、入出力例に対して AllTrue（すべて True の場合）、AllFalse (すべて False の場合)、Mixed（それ以外）を出力する。この値を property signature とする。あらかじめ定められた $k$ 個の property から出力される $k$ 個の property signature のリストが property signatures である。

なお、property を定義するのは人間である。

Bottom-Up Synthesis with Learning

この手法のアルゴリズムの重要な部分は以下の Algorithm 1 で表現されている。

f:id:t-keita:20200916020953p:plain

青字で書かれた部分を無視すると一般的な bottom-up な合成アルゴリズムである。bottom-up なアルゴリズムでは、プログラムの大きさ（具体的には構文木のノード数）の小さいものから順番に列挙してゆくだけである。たとえば、大きさが 9 以下のプログラムをすべて列挙できているとき、次に列挙するのは大きさが 10 のものである。構文木のトップレベルに使用する命令 $op$ を固定したとき、 $op$ の引数の合計の大きさが 9 となるように引数を列挙する。たとえば、 $op$ が２つの引数を取るのであれば、第一引数と第二引数のプログラムの大きさとして (1,8), (2,7), ..., (8,1) の場合をそれぞれ列挙する。

青字で書かれた部分を考慮した場合、プログラムの大きさに加えて property signature を用いた重みづけを行うことで正解に至りそうなプログラムを優先的に列挙する。具体的には、16 行目でボトムアップに構築したプログラムの出力 $\mathcal{V}$ と出力 $\mathcal{O}$ における property signature を計算し、17 行目で重みの更新を行う。このとき、binary classifier $p(- \mid \mathcal{I}, \mathcal{V}, \mathcal{O})$ によって、現在のプログラムの出力 $\mathcal{V}$ が入力 $\mathcal{I}$ から出力 $\mathcal{O}$ へ至る中間結果としてどの程度もっともらしいのか確率を計算する。この確率が 1 に近いほど重みは小さく、0 に近いほど重みが大きくなるように重みの更新が行われる。

Model Architecture and Training

binary classifier $p(- \mid \mathcal{I}, \mathcal{V}, \mathcal{O})$ のためのニューラルネットワークはシンプルな構造をもつ。property signatures を使うことで人間の知見が表現されているので deep な構造を回避できているという。学習データセットは自動生成している。詳しくは論文参照。

Evaluation

論文参照。

所感

機械学習を用いたプログラム合成は近年 ML 系のコミュニティでよく発表されている。そっち系の論文10 本くらいは読んだが、ほとんどの機械学習手法が、入出力例が属するドメインからパターンを抽出することにフォーカスしている。そのため、手法に対してドメインをまたぐ汎用性は期待しないほうがよい印象。どの論文を見てもドメインに依存しない汎用的なアイデアを提案しているのだが、ドメインに依存せずに性能が出るとは言っていないので要注意。
関連研究にもあるが、"Write, execute, assess: Program synthesis with a REPL" (NeurIPS2019) とアイデアが似ていて、具体的な研究の貢献がよく分からない。手法のコアである bottom-up synthesis と property signatures はもちろん既存技術であるし、作りかけのプログラム (partial program) の実行結果と出力例を比較するというアイデアも execution-guided synthesis という名で知られている。ただし、本手法のアルゴリズムはかなりシンプルなので、先行研究と同じような性能が出るのであれば本手法のやり方を参考にするのはよいかもしれない。
作りかけのプログラムの実行結果と出力を比較する execution-guided synthesis は、結局のところ「出力の部分構造が、合成すべきプログラムの部分構造に対応する」という考えに基づいているような気がする。出力文字列の一部が常に大文字なら、プログラムとして大文字を返す命令を含むべき、みたいな。これはもちろん一般的な合成関数にはまったく当てはまらない。 $(g \circ f) (a)$ が $f(a)$ の名残をとどめていることが重要そう。
bottom-up なアプローチはどうしても入出力例の制約を活かしづらく、有益でないプログラムを無駄に探索してしまう印象がある。top-down な手法との比較結果を見てみたい。