およそひと月ぶりに，仲間内で行っている小さな勉強会で論文紹介をしてまいりました．ICML2013の予稿がちょっとづつ出てきているので，本日はその中から一本．

• “A Machine Learning Framework for Programming by Example” Aditya Menon et al, ICML 2013

機械学習を使って，Programming by Example(PbE)をしようという論文です．PbEというのは私も初耳だったのですが，ざっくり言うと，人間が「例」を与えることで，その例をうまく再現するようなプログラムを自動的に生成する，というタスクのようです．

それを部分的に実現している（らしい）のが，Excel2013に新しく搭載されたという“Flash Fill”という機能．ユーザーの意図を推測して，ルールにしたがったセルの補完なんかをしてくれるみたいです．百聞は一見にしかず，以下の動画をご覧ください．

Flash Fillは一行から一行（というよりは，セルからセル）への変換のみがターゲットでしたが，本論文では集計であるとか，重複の削除のように，複数の行にまたがった処理をうまく解く枠組みを提案しています．

具体的には以下の例が分かりやすいかもしれません．

「書き換え前」「書き換え後」の文字列を与えると，それらをうまく繋ぐようなプログラムを生成する，というイメージです．Perlいらず？

手法としてはさほど難しいことはしておらず，無理やり一言でまとめてしまうと，「書き換えプログラム」の生成モデルをPCFGでモデル化して，それぞれの生成ルールの確率をlog-linearで書き，そのパラメータをPCFGのn-best導出を延々と求めながら更新していく，というだけ．見方によっては，あまりICMLっぽくは無いかも．

もちろん，書き換えルールの元になるような基礎的な関数セット(最低限チューリング完全なものがあれば原理的には可能ですが，現実的には重複除去とかカウントとかを用意しておくみたいです)はあらかじめ定義しておかなければならないのですが，あとは探索時間さえ掛ければ任意の書き換えを行うプログラムが生成可能である，というのがポイントです．

ただ，現実的な時間で探索を行うためには探索に優先順位をつける必要があります．そこで，効率的に探索を行うために機械学習を用いて「書き換え」の集合をあつめたコーパスからPCFGのパラメータを学習しましょう，というのがこの論文の本旨のようです．実際，探索が難しいプログラムほど高速化が期待でき，brute forceな方法にくらべると40倍ほど速くなる場合もあるとのこと．

機械学習は「適応的なシステム」を作るのに使われる「重い」手法，というイメージがありますが，もともと原理的に解ける問題を「高速化」するために用いる，という意味で面白い視点を与える論文だと思いました．

ビッグデータ感もなければ，ディープラーニングでもなく，曼荼羅のようなグラフィカルモデルもなんとかダイバージェンスも出てこない論文ですが，なかなか面白かったです．実用に近そうなのもいい．

話は変わりまして，先日大学の同期とのプチ同窓会で10人ばかり集まったのですが，誰一人結婚してなくて笑．もちろん，ある種の集合バイアスもあるとは思いますが，おいおい俺らそろそろみそじやで．