プログラムを自動生成する研究、とくに入出力例を用いたプログラム合成 (Programming by Example) に興味があるので、論文を読んでメモとして残してゆく。以下、水色のテキストは私の主観的なコメント。

タイトル

Web Data Extraction using Hybrid Program Synthesis: A Combination of Top-down and Bottom-up Inference

SIGMOD2020

Web data extraction using hybrid program synthesis: a combination of top-down and bottom-up inference - Microsoft Research

概要

ウェブページからデータを抽出するプログラムを、抽出すべきデータの (不完全な) 例から合成する手法。合成のアルゴリズムとして、入出力例を考慮したトップダウンなアプローチと、ドキュメントの構造のみを考慮したボトムアップなアプローチを組み合わせるのが特徴。本手法は Microsoft Power BI に搭載されている。

手法の入出力

手法の入力

Web ドキュメント $d$
抽出するデータの例 ]
- $t_i$ は文字列、 $n_i$ はノードの例。文字列は必須で、ノードはオプション。
- たとえば [(“Snow White and the Seven Dwarfs”, ), (“Fantasia”, )]
  - ここで $n_1$ や $n_2$ は null でもよい。

手法の出力

DSL 上のプログラム
- ただし、の実行結果が ] であるもの。ここで、すべての () に対して以下が成立する
  - $n'_{i}.\texttt{Text} = t_i$
  - $n'_i = n_i$ ( $n_i \neq$ null の場合)
- ここでのポイントは、抽出するデータの例が $k$ 個与えられるもとで、 $s$ ( $k \leq s$ ) 個のデータを抽出する、もっともらしいプログラム $P$ を求めるということ。仕様が不完全であるため、semi-supervised で hybrid なアプローチが有効である。

DSL の定義

プログラム合成手法では、DSL (Domain-Specific Language、ドメイン固有言語) をドメインごとに定義し、その上でプログラムを構築するアプローチが一般的である。本手法では、入力となる DOM ツリー inp からノードの集合を抽出するための DSL $\mathcal{L}$ を以下のように定義する。

f:id:t-keita:20200914022637p:plain:w400

各命令のセマンティクスは論文を参照。ただし、文法 $\mathcal{L}$ から点線下線と実線下線を除いた文法を、それぞれ $\mathcal{L}_t$ と $\mathcal{L}_b$ とする。文法 $\mathcal{L}_t$ , $\mathcal{L}_b$ はそれぞれ top-down, bottom-up な合成で構築される。

たとえば、"mydata" という ID を持つノードの配下にある DIV 要素の2番目の子でありクラス "c1" のノード集合を抽出したいとき、対応するプログラムは以下の通りである。

Filter(
   Conjunction(
      Class(“c1”), 
      NthChild(2)
   ),
   ChildrenOf(
      Filter(
         Tag(“DIV”), 
         DescendantsOf(
            Filter(
               AllNodes(), 
               Id(“mydata”)
)))))

Combination of top-down and bottom-up synthesis

一般に、DSL 上のプログラムを合成するアルゴリズムとして top-down なものと bottom-up なものが存在する。

top-down なアプローチでは、ユーザによって入出力例が与えられるケース (supervised program synthesis) で有効である。具体的には、構文木の根から葉の方向へプログラムを構築してゆく。その過程において、満たすべき入出力例の制約を、各命令からその引数 (構文木の) へと伝播させることで、探索空間を入出力例を満たしうる部分のみに限定する。これは deductive なアプローチといえる。

bottom-up なアプローチは、ユーザによって入出力例を与えられないケース (unsupervised program synthesis) で有効である。(入出力例の制約は関係なく) DSL 上のプログラムを列挙する。

本手法は、top-down と buttom-up なアプローチのどちらも使用するハイブリッドなアルゴリズムになっているのが特徴である。

Bottom-up synthesis

まずは Figure 5 にある bottom-up な合成から見てゆく。

f:id:t-keita:20200915024554p:plain:w400

EnumerateBottomUp(d)

与えられた入出力例とは関係なく、 $\mathcal{L}_b$ で表現されるプログラムをボトムアップに列挙してゆく。その結果は、得られたプログラム $P$ と、それをウェブドキュメント $d$ に適用した結果得られるノード集合 $N$ の2つ組 $(P, N)$ の集合 $\mathcal{E}$ として返される。本質的には、 $(P, N)$ でなくプログラム $P$ の集合を返すだけでよいが、ドキュメント $d$ に対する実行結果をキャッシュすることで計算にかかる時間を削減しているっぽい。

TopAlignmentGroups( $\mathcal{E}$ )

前手順で列挙したプログラムの実行結果は、ドキュメント $d$ において親子関係を持つ可能性がある。そこで、親子関係にあるノードを生み出すプログラムの集合を $(P_1, \dots, P_n)$ としてグルーピングする。さらに、グループの中で根に近いノードを実行結果にもつプログラム $P_a$ をグループの代表とする。つまり、 $(P_a, (P_1, \dots, P_n))$ を求める。たとえば、Figure 3 の motivating example の例では $P_a$ が .list_item であり、 $P_i$ が .year_type や .item_desc SPAN である。

Top-down synthesis

Figure 7 の top-down なプログラムの合成を見てゆく。

f:id:t-keita:20200915024725p:plain:w400

SynthTopDown( $d$ , $N_e$ , $N_a$ )

$\mathcal{L}_t$ で表現されるプログラムを top-down に列挙してゆく。このとき、満たすべき出力例 $N_e$ が与えられるが、これを使用する DSL の命令 (ChildrenOf, Filter) の引数を合成するにあたっての新たな制約として伝播させるのがポイント。ここの仕組みが厳密に理解できていない。Figure 8 の line 2 で $N_e$ の親になり得るノード集合 $N_p$ を求め、line 3 で再帰的に SynthTopDown( $d$ , $N_p$ , $N_a$ ) を呼び出している。親方向のノード集合を再帰的に求めることになるので、やがて $N_p$ は根のシングルトンとなり、その後に空集合となるはず。 $N_e$ が空集合であれば $N_p$ も空集合となるので、再帰が停止しないように思う。

SynthPredicate( $d$ , $N_s$ , $N_e$ , $N_a$ )

実行結果としてノードの列 $N_e$ をプレフィックスに持つような Filter の条件式を合成する。このとき、overfitting を避けるため、できる限りシンプルな条件式を合成したい。そこで minimal set cover として定式化して解く。具体的には、atomic な述語と、それによって取得できるノード集合 ( $\subseteq N_e$ ) を求めておき、 $N_e$ をカバーできる最小数の述語の組み合わせ (conjunction) を求める。

Hybrid synthesis

Figure 8 の hybrid なプログラム合成を見てゆく。なお、top-down な合成が成功した場合、解となるプログラムをより洗練させる形で hybrid synthesis を実行する。

f:id:t-keita:20200915024851p:plain:w400

SyntheHybrid( $d$ , $N$ , $\mathcal{G}$ , $P_t$ )

ここで $\mathcal{G}$ は bottom-up に発見されたノードのグループ、 $P_t$ は top-down に求められたプログラムである。この２つの情報を組み合わせているので hybrid といえる。 $\mathcal{G}$ は入出力の例とは独立に、ドキュメント $d$ のみから構築されたグループであるため、ドキュメントの構成要素を "自然な" まとまりとして集めたノード集合である。それに対し、入出力の例を考慮して top-down に作られたプログラム $P_t$ が $\mathcal{G}$ に対して整合性があるかをチェックする。整合性がなければ制約を $N_a$ として追加して top-down な合成を再実行する。

たとえば、bottom-up に集めた映画のレコードが 100 件あったとして、そこから映画のタイトルを抽出したいとする。ただし、100 件中 1 件だけディレクターについての項目が欠落しており、タグ構造が特殊なレコードがあるとする。このとき、抽出するデータの例として先頭２件が与えらえたとする。この 2 件を満たすように top-down に合成したプログラム $P$ が 100 件中 99 件のタイトルしか抽出していないとき、合成結果を $P$ とするのは怪しい。そこで、100 件を結果として含むように制約を加えて合成を再実行する。その結果、100 件すべてから正しく映画タイトルを抽出するプログラムを合成できる。

Evaluation

論文参照。

所感

Web ページのスクレイピングを自動的に行う手法。抽出するデータの形式がレコードである場合 wrapper induction と呼ばれるらしい。ここで wrapper は HTML などで表現されたページの構造からレコード集合への写像。
- Wrapper (data mining) - Wikipedia
与えられる出力例が、期待する出力の一部のみが与えられる不完全なものであるため、完全な出力例を推測する必要がある。そのための heuristics が bottom-up な合成として表現されているように思えた。
bottom-up にプログラムを列挙するアルゴリズムとして lifting functions を用いている。これは [34] に詳細が書かれているのでちゃんと見てみたい。