5. 予測/例示プログラミング

本日の話題

Programming by example

Programming by demonstration

自動プログラム生成

つぶやきProcessing

https://gyazo.com/e2059fe0c8d88fd75d58a566b892966e https://twitter.com/hashtag/つぶやきProcessing?src=hashtag_click

計算機操作の問題点

つまらない繰り返し操作が意外と多い

(例1) 連続する100行の字下げ

プログラム? マクロ? 特殊機能を探す?

(例2) パラメタを変えて再計算/コンパイル

プログラムを作るべき? Makefileを使うべき?

(例3) 図形レイアウト

ルーチンワークとあきらめる?

例1: 連続する字下げ

code:from.rb

def tarai(x,y,z,indent=0)

puts "#{' '*indent}tarai(#{x},#{y},#{z})"

if x <= y then

y

else

tarai(tarai(x-1,y,z),

tarai(y-1,z,x),

tarai(z-1,x,y),

indent+1)

end

end

code:to.rb

# def tarai(x,y,z,indent=0)

# puts "#{' '*indent}tarai(#{x},#{y},#{z})"

# if x <= y then

# y

# else

# tarai(tarai(x-1,y,z),

# tarai(y-1,z,x),

# tarai(z-1,x,y),

# indent+1)

# end

# end

連続する字下げ

プログラムを書く?

マクロを書く?

特殊な機能を探す?

例2: パラメタを変えて何度も再計算

code:cf.txt

10 × 9 / 5 + 32 =

20 × 9 / 5 + 32 =

30 × 9 / 5 + 32 =

...

手作業でやるべき?

プログラムを書くべき?

例3: 図形のレイアウト

https://gyazo.com/8f4889fa166f8100a3a108ad01d2e3a0

ルーチンワークを自動化したい

解決法

アプリの機能強化

アプリケーションが肥大

マクロ作成/使用

一般に面倒

プログラム作成

プログラミングは難しい

予測/例示システムによる解決

操作履歴から次の操作を予測

繰返し操作の検出

パラメタ予測

1, 2, 3 の後に 4 を予測

例示によるマクロ作成

例からのプログラミング

目標 = 例データからプログラムを自動的に作成

Programming by Example (PBE)

Programming by Demonstration (PBD)

PBEのメリット

コードを自分で書かなくてもプログラムができる

誰でもプログラミング

予測/例示インタフェース手法の利点

繰返し作業を楽にする

マクロを簡単に作成

複雑な機能を用意する必要がない

プログラミングが不要

プログラマででなくても使える

抽象的思考が不要

結果が目に見えてわかりやすい

エンドユーザプログラミングへの応用

テキストでプログラミングする必要がない

(例) メールの仕分けプログラムの作成

プログラムを書く場合

code:mail.pl

if(/From: masui.*/){ ...

例示インタフェースの場合

実際の仕分け操作から推論

GUIプログラミングへの応用

実際のGUI操作からGUIプログラムを生成

画面の表示やふるまいとプログラムのギャップを解消

e.g. GUI設計システム

画面表示とプログラムのギャップを解消

予測/例示インタフェース本

http://gyazo.com/faf7afca309669b6fcf4ca7c56784459.png

予測/例示インタフェース本

http://gyazo.com/7023e93cdd3569ba57f6b38ecad9b60f.png

予測/例示インタフェース本

http://gyazo.com/ff1f4d2e9b739ca809c6aa710d47afe7.png

Allen Cypher

予測一筋20+年

http://acypher.com/ http://gyazo.com/28aae39177a8bb0a5db71e11aa8cbace.png

Apple ⇒ IBM ⇒ Microsoft

予測/例示インタフェースの分類

知的処理を行なうかどうか

プログラムの作成を支援するかどうか

単純/複雑

単純なもの

操作記憶/再実行

アプリケーション知識からの予測

統計情報などからの予測

繰返しパタンの検出

複雑なもの

自動適応

機械学習

帰納的推論

帰納的推論

いくつかの例から普遍的法則を導く

一般化 / 知識形成

事例獲得→仮説形成→検証

予測に使用されるデータ

無意識的なもの

操作履歴 (計算トレース)

予測実行時のコンテクスト

別のテキスト

辞書 (他人による例示)

明示的に指定するもの

プログラミングに近い

両者の組み合わせ

自動適応 + 意識的に例を与えて「教育」

例示インタフェースでよく使われる手法

操作履歴, コンテクスト, 辞書の利用

アプリケーション依存のアドホックな知識の利用

ユーザの介入による推論誤りの修正

例示データの生成の自動化

ユーザ操作やプログラムのビジュアルな表現

単純な予測インタフェースの実例

ブラウザ履歴

UNIXシェル

dabbrev

Flash Fill

Reactive Keyboard

操作予測電卓

Dynamic Macro

Eager

Smart Make

履歴利用電卓

Snap Editor

Smart Make

履歴利用電卓

ブラウザの履歴を使った補完

UNIX shell, Emacs

Use shortcut keys

% !!

% !c

補完

ファイル名などの一部分のみ指定

Dynamic abbreviation

既出の文字列を静的/動的辞書として利用

Use M-/ key

Flash Fill (Excel)

https://www.youtube.com/watch?v=tBC9CuoCISY

https://www.youtube.com/watch?v=1KimYFzET1w

シェルのキーストローク列の頻度情報から次の入力文字列を予測

打鍵が非常に遅い場合に有効

PPM (Prediction by Partial Match)法

文字出現頻度情報から次の出現文字を予測

テキスト圧縮に有効

予測が正しいほど高圧縮率

PPM法

出現頻度の荷重和をとって次の文字の予想出現確率を計算

テキスト圧縮アルゴリズム

辞書式 (LZ系)

出現した文字列を辞書に格納

再び出現した文字列は辞書へのポインタで表現

予測 + 符号化

PPM法

ハフマン符号化 / 算術符号化

ハフマン符号化によるテキスト圧縮

出現確率が不明の場合

各文字に2ビット必要

算術符号化 = ハフマン符号化の拡張

http://gyazo.com/8f3f344d62b29641a47fc6195eed5004.png

操作予測電卓 (Witten)

PPM法利用

1 + 2 = , 1 + 3 = , ... といった操作列から "1 + ", "=" などの共通部分を予測

.1 mc m+= +/- + 1 = exp * mr =

履歴をもとに次の操作を予測

Emacs上での操作の再実行

操作履歴から繰返しパタンを抽出

あらゆる繰返し操作に対して有効

マクロ登録が不要

デモ: Dynamic Macro

次の数字も予測する

ブラウザ上のDynamic Macro

Firefoxの拡張機能

Dynamic Macroの動作

2回続けて全く同じ操作列が実行された後で繰り返し実行キーが入力されるとその1回分を繰り返す

そのようなパタンが複数存在するときは最長の繰り返しパタンを選択

Dynamic Macroの動作 (Cont'd)

直前の操作列と全く同じ操作列が以前の操作列中に存在するとき、それらの間の処理を実行する

もう一度繰り返し実行キーが押されると繰り返しパタンを実行する

http://gyazo.com/ac2b347a7042f920edd576ee07c4b7f4.png

予測型テキスト入力システム

「直接入力」でなく「検索で得られた侯補からの選択」による

なるべく少ない操作で検索条件を与える

検索結果を動的に表示し選択の対象とする

曖昧パタンマッチを活用する

POBoxの具体的手法

ソフトキーボードで読み/綴りの一部を指定

条件にマッチする単語を使用頻度の高い順に侯補として表示

例文辞書を使用し、前の単語から次の単語を予測

マッチする単語が無い場合は曖昧検索実行

POBox搭載商品

デモ: POBox

HyperSnapping (増井)

https://gyazo.com/ae10f0e13797c754c8ed896eb73a2749

デモ: HyperSnapping

Eager (Cypher)

http://gyazo.com/6137905efa632ac7386ffdc7647a9891.png

Eager

HyperCard上の繰り返し操作から次の操作を予測

システムは常にユーザ操作を監視

次の操作を先取りしてユーザに提示

提示された操作と同じ操作をユーザが実行した場合は推論の肯定とみなす

推論を無視して操作を続けた場合は否定とみなす

正しい予測を行なっているとユーザが確信した場合は残りを自動実行可能

Video: Eager

https://s3-ap-northeast-1.amazonaws.com/masui.org/1/5/154a9f7e08985a4d4f66604c78f22d6a.mp4

https://www.youtube.com/watch?v=X6ZL4BXOfbk

HyperCard

Macintosh上のハイパーテキストシステム

https://www.youtube.com/watch?v=FquNpWdf9vg

https://gyazo.com/fe55c33b8fb3b13b1ab681eddfbbf506

https://archive.org/details/mac_MacOS_7.0.1_compilation https://archive.org/serve/mac_MacOS_7.0.1_compilation/_screenshot.gif

Bill Atkinson と Jef Raskin

https://gyazo.com/09b337d875a1bd118cbf016eb9e71dab

Smart Make (増井)

シェル上のコマンド履歴からファイル/コマンド間の依存関係を抽出しMakefileを生成

コマンド操作 = 暗黙的な依存関係の例示

依存関係の抽出法

コマンドの字面からだけではわからない

ファイルの生成/アクセス時間から判断

Smart Make

code:smartmake:txt

101% grep a /etc/passwd > passwd.a

102% grep b /etc/passwd > passwd.b

103% tar cvf passwd.tar passwd.a passwd.b

a passwd.a 2 blocks

a passwd.b 3 blocks

104% compress < passwd.tar > passwd.tar.Z

105% uuencode passwd.tar.Z passwd.tar.Z > passwd.UU

106% ls

passwd.UU passwd.a passwd.b passwd.tar passwd.tar.Z

107% mm

passwd.tar.Z: passwd.tar

compress < passwd.tar > passwd.tar.Z

passwd.tar: passwd.a passwd.b

tar cvf passwd.tar passwd.a passwd.b

passwd.b:

grep b /etc/passwd > passwd.b

passwd.a:

grep a /etc/passwd > passwd.a

履歴利用電卓 (増井)

Undo操作を活用

値を変えて再計算

例: 華氏の計算

10 10

× 10

9 9

／ 90

5 5

＋ 18

32 32

＝ 50

値を変えて再計算

後退キーをUndoに使

- 50 previous result

BS 32 last parameter displayed

BS 5 parameter displayed

BS 9

BS 10 first parameter

20 20 enter new parameter

＝ 68 new F calculated

30 30 enter new parameter

＝ 86 new F calculated

...

再計算の状態遷移

http://gyazo.com/641016c4ecdf0940427df5b27bf8175b.png

例示インタフェース

システムに対して明示的に例データを与え、ユーザの意図や好みを推論させる

例示インタフェースの実例

Editing by Example

TELS

SmallStar

Triggers

Metamouse

Chimera

Mondrian

Layout by Example

KidSIM

Stagecast

Viscuit

CoScripter

Sikuli

編集前のテキストと編集後のテキストの組の例をシステムに提示

ユーザの実際の操作は考慮しない

正規表現による文字列置換のサブセットを使用

システムが変換規則を推論し、残りのテキストに適用

テキストエディタ上でのGUI操作の繰り返しを検出/プログラム生成

挿入/削除/移動/選択の4種類の編集操作のみ

各操作の前後でのコンテキストの汎化によりループを検出

↓

正規表現による文字列置換のサブセットを使用

編集前/後のテキスト

code:before.txt

John Bix, 2416 22 St., N.W., Calgary, T2M 3Y7. 284-4983

Tom Bryce, Suite 1, 2741 Banff Blvd., N.W., Calgary, T2L 1J4. 229-4567

Brent Little, 2429 Cherokee Dr., N.W., Calgary, T2L 2J6. 289-5678

Mike Hermann, 3604 Centre Street, N.W., Calgary, T2M 3X7. 234-0001

code:after.txt

John Bix,

2416 22 St., N.W.,

Calgary,

T2M 3Y7.

Tom Bryce,

Suite 1,

2741 Banff Blvd., N.W.,

Calgary,

T2L 1J4.

Brent Little,

2429 Cherokee Dr., N.W.,

Calgary,

T2L 2J6.

Mike Hermann,

3604 Centre Street, N.W.,

Calgary,

T2M 3X7.

プログラム生成

https://gyazo.com/88c6657deef4e8e62aa694e7d321a0ed

プログラム生成 (Cont'd)

https://gyazo.com/32b050371399acb749a7d3812af4f50b

StarのGUI操作マクロを例示により生成

操作を行なった後で、操作列をエディタで編集

http://gyazo.com/dca4a743d9c8da3dbc0132fe656ca9c5.png

http://gyazo.com/595a5a4cf92cadbf60b4c8309bdce796.png

ビットマップ画面上のパタンマッチングにより操作の自動実行

e.g. 「OK」が表示されたらクリックする

定義したビットマップパタンが表示されたとき定義された操作を自動実行させる

(例) 表計算ソフトの全ての負の数値データに印をつける

http://gyazo.com/cd25caa5d14b850f9a1d9da2d6beb0c9.png

Video: Triggers

https://s3-ap-northeast-1.amazonaws.com/masui.org/7/2/72aa1ce0f26d8af8a3b4c25b7b1e2a79.mp4

あらゆるGUI操作をビットマップパタンマッチングで実行

http://www.youtube.com/watch?v=FxDOlhysFcM

Metamouse (Maulsby)

http://gyazo.com/b2c205758a98d4041a4cd24c400a4f64.png

http://gyazo.com/3c6533eb47820cefa1a288b31d82f0e3.png

Metamouse

図形の編集操作から編集プログラムを自動生成

プログラムをプロダクションルールの集合として表現

e.g. 「上に移動させた直線が矩形に接したとき直線の長さだけ矩形を移動させる」

ループも表現可能

「接する」「交わる」といった幾何的条件を重視

システムの推論誤りを修正しながら正しいプログラムを作成

単一の例からでも変数や制約を抽出したプログラムを生成

似たようだがちょっと違う例があるときは、より詳細な条件をもつruleが生成され、条件分岐のように働く

ユーザが以前の操作と完全に同じ操作を始めたときは、すぐに次の行動を予測して提示

図形編集操作の履歴をプログラムとして後で編集/定義

GUI操作列を紙芝居(Storyboard)風に表現

重要な部分だけアイコンとして表示

細かい一連の操作はまとめてひとつのアイコンとする

グラフィカルな形で表現したまま編集可能

http://gyazo.com/ab3b00b63c4a6b9ac5fba9fd58d93f90.png

http://gyazo.com/5761803ec7e69458997cc4b71189d7ae.png

図形配置規則を例示により推論

図形が2個の場合の配置例，3個の場合の配置例... をユーザが与える

システムは配置アルゴリズムを推論

http://gyazo.com/8b337e894e2863996edb20c7306b790b.png

KidSIM (Cypher)

http://gyazo.com/e3811d24bde71596f7aedef782f60d90.png

KidSIM

例示によるアニメーション生成システム

処理前後の状態の絵の組で規則を表現

Graphical Rewrite Rule (GRR) の草分け

パタンにマッチする規則があればそれに従って盤面が変化

KidSIMを商品化したもの

http://gyazo.com/ac046dc993ee300f647599f3ba9e988f.png

https://www.youtube.com/watch?v=6Hm6R6INb30

子供用のプログラミング

GRRを利用

http://gyazo.com/66a451fefd3be1832a7418b017065fd9.png

http://www.youtube.com/watch?v=0N8cpLHZ41I

https://www.youtube.com/watch?v=kxeaeCajuFc

https://www.youtube.com/watch?v=L0Gg76f60ao

https://www.youtube.com/watch?v=8q-Pbg8sCV0

GRRを利用

操作とそのテキスト表現のギャップを「類推」で埋める

http://gyazo.com/42c5d4b68b126fe6e6eb496167208781.png

GUI操作とそのテキスト表現のギャップ

http://gyazo.com/da5488a47c80c9fea0bccebc43a50f8e.png

Agentsheetsの類推

http://gyazo.com/3492b4d80cf3b72b3b3af4186c5d2bb5.png

Firefoxでの操作を記録/再生

人間が読みやすいいい加減な記述を許す

作成したマクロがWikiで共有される

https://www.youtube.com/watch?v=TyQPwPgbRZQ

CoScripter

https://www.youtube.com/watch?v=nyUM_dyd8fE

インタラクティブ進化的計算

遺伝的アルゴリズムに対話性を導入

自動生成された例から適当なものを選ぶことを繰り返す

最適な結果を生成

最適なアルゴリズムを生成

確率的手法(GA, SAなど)を用いた図形配置システムでは評価関数の選択が重要

配置の好みをユーザが指定することにより、ユーザと同じ判断を行なう評価関数\\

を遺伝的プログラミングで自動生成

確率的手法

配置のよしあしを反映する評価関数を利用して徐々に良い解を求める

前の解をもとに次の解を計算する

手続きを用いずに良い解を得ることが可能

代表的なアルゴリズム

遺伝的アルゴリズム (GA)

焼きなまし法 (SA)

確率的手法の例

GA(GASP)とSA(TimberWolf)によるVLSI配置

確率的手法のグラフ描画への適用

美しさの基準を示す評価関数を最適化する

http://gyazo.com/8a28ce95b25c9fe78d8f583114577fc6.png

確率的手法の問題点

遅い

最適に近い解が得られるとは限らない

評価関数がはっきりしているとは限らない

配置制約と評価関数の関係が自明でない

例: 三角形の中の適当な位置に別の点を配置

なんらかの評価関数の最適化によりその点の位置が定まるようにしたい

https://gyazo.com/340109116a80ef84b0a7e370be9cc736

http://gyazo.com/d03154eeb529d6cbddf7862010e7fc8a.png

http://gyazo.com/bf06f4b7382f172adc55fea9f02350ef.png

例示によるアプローチ

例示により評価関数を作成する

ユーザはシステムに好みを伝えるだけ

遺伝的プログラミングによりユーザの与えた例から評価関数を自動生成

手法

良い配置例と悪い配置例の組をシステムに与える

遺伝的プログラミングにより配置の良否を決定する評価関数を抽出

与えた例における評価基準にもとづいて良い配置を生成することが可能

システムに与える配置例

http://gyazo.com/c203269a8abf8cd58ea730b9c119fe4f.png

得られた評価関数

(ADD (SUB (ADD (MUL (MUL (MUL (ADD (ADD (ADD SUM(diry) SUM(minangle)) (ADD 44.00 69.00)) (MUL 43.00 MIN(diry))) 5.00) (ADD (ABS MAX(minangle) MIN(dist)) (ADD (ABS 74.00 MIN(dirx)) (ABS 15.00 SUM(locx))))) SUM(minangle)) (MUL 12.00 (CMP (DIV 57.00 MIN(locx)) (CMP 94.00 MIN(intersec))))) (DIV (ABS (MUL (SUB SUM(locy) 27.00) (CMP 28.00 65.00)) 62.00) SUM(dirx))) (CMP (ABS (DIV 67.00 SUM(locy)) (CMP (ABS (ABS 73.00 (CMP 67.00 SUM(dist))) MIN(intersec)) (ABS MIN(dist) MIN(diry)))) MIN(diry)))

得られた評価関数を使って得られた配置

http://gyazo.com/bb72e5ebf630d30e1ddc8fff69b13a74.png

進化的アート作品生成

システムに作品をいくつか自動生成させ、良いと思われるものを選択することに\\

より進化させる

Biomorph (Richard Dawkins)

Galapagos (Karl Sims)

sbart (畝見)

Biomorph

「利己的な遺伝子」「Blind Watchmaker」のRichard Dawkinsの作品

「遺伝子」をもつ「虫」を進化させる

ランダムに遺伝子を交配させて作った子孫の中から最も気に入ったものを選ぶという行為を繰り返す

Biomorphの進化過程

https://gyazo.com/189863961ab4de620dab6d570ac8dfd9

https://gyazo.com/8fffe45a962630375cf74f6e0898c1fc

進化結果

Galapagos (Sims)

Presented at NTT ICC

Select one from 9 examples

http://gyazo.com/922ac4cc0136595f718209c81e6d4874.png

進化した「生物」例

http://gyazo.com/3ffc4dfce6ee255512e690f4939d3306.png

http://gyazo.com/356252a15a0243c5915b83662c2047a0.png

sbart (Unemi)

http://gyazo.com/06cb5d773b1add3e24775950e0fa5ab3.png

予測/例示インタフェースの現状

本当に役にたつシステムは少ない

普通にプログラミング/マクロ定義した方が楽なことが多い

少ない例からの推論/汎化が難しい

ヒューリスティクスの多用

ユーザからのフィードバックによる修正

システムの推論方式をよく知らないと使えない

予測/例示インタフェースの要件

予測を使わない場合に比べて全く不都合がないこと

予測による効果が余分な労力に見合うだけ大きいこと

予測がユーザの期待に一致する確率が高いこと

不安感がつきまとわないこと

予測機能を使わないユーザの邪魔にならないこと

誤った予測を実行したときの被害が小さいこと

突然の予測実行/挙動変化に驚かされないこと

複雑な仕事には使えない

プログラムウを書いた方が良い

終了条件や条件分岐を示すことができない

操作が間違いを多く含んでいる場合に困る

推論エラーを修正できない

推論に高いコストがかる

予測/例示インタフェースの展望

実世界指向インタフェースにおける応用

検索インタフェースとの融合

テキスト入力/描画エディタへの応用

実世界指向インタフェースにおける応用

実世界の状況を例データとして活用

(例) 夜の品川駅で電源を入れたときは時刻表を表示するPDA

プログラミング

センサから得られた位置情報/電界強度/時刻などの数値から条件分岐

例にもとづく判断

一度夜の品川駅で時刻表を使ったことがあるという以前の事例を検索

実世界でのプログラミング

「夜の鎌倉駅では時刻表を見る」のような例からプログラムを作成

検索インタフェースとの融合

既存データを例として使用 + ユーザによる例データ追加

e.g. 仮名漢字変換

システム辞書とユーザ辞書が同じ

まとめ

PBEは徐々に普及中

Flashfill、Sikuliなど

グラフィカルなもの、実世界のものは有望