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

資料

参考情報いろいろ

Twitter

FlashFill

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

計算機操作の問題点

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

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

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

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

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

(例3) 図形レイアウト

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

解決法

機能強化

アプリケーションが肥大

マクロ作成/使用

一般に面倒

プログラム作成

プログラミングは難しい

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

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

繰返し操作の検出

パラメタ予測

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

例示によるマクロ作成

例からのプログラミング

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

Programming by Example (PBE)

Programming by Demonstration (PBD)

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

繰返し作業を楽にする

マクロを簡単に作成

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

プログラミングが不要

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

抽象的思考が不要

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

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

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

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

プログラムを書く場合

code:mail.pl

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

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

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

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

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

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

e.g. GUI設計システム

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

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

http://hondana.org/%E5%A2%97%E4%BA%95/0262032139 http://gyazo.com/faf7afca309669b6fcf4ca7c56784459.png

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

http://hondana.org/%E5%A2%97%E4%BA%95/1558606882 http://gyazo.com/7023e93cdd3569ba57f6b38ecad9b60f.png

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

http://hondana.org/%E5%A2%97%E4%BA%95/012381541X http://gyazo.com/ff1f4d2e9b739ca809c6aa710d47afe7.png

Allen Cypher

予測一筋20年?

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

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

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

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

単純/複雑

単純なもの

操作記憶/再実行

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

統計情報などからの予測

繰返しパタンの検出

複雑なもの

自動適応

機械学習

帰納的推論

帰納的推論

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

一般化 / 知識形成

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

予測に使用されるデータ

無意識的なもの

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

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

別のテキスト

辞書 (他人による例示)

明示的に指定するもの

プログラミングに近い

両者の組み合わせ

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

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

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

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

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

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

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

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

ブラウザ履歴

UNIXシェル

Reactive Keyboard

操作予測電卓

Dynamic Macro

POBox

Eager

SnappingEditor

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

http://gyazo.com/d10af2afca10df05c52cbea83ab93e8f.png

UNIXシェル、Emacs

省略形による再実行

% !!

% !c

補完(completion)

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

Dynamic abbreviation

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

Demo: Unixシェル

Demo: Emacsの補完、dabbrev

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

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

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

テキスト圧縮に有効

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

e.g. `abracadabraに続く文字の予測

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

テキスト圧縮

辞書式 (LZ系)

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

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

予測 + 符号化

PPM法

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

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

出現確率が不明の場合

各文字に2ビット必要

aを0, bを10, cを100, dを101と符号化

1*0.5 + 2 * 0.25 + 2 * 3 * 0.125 = 平均1.75ビット/文字

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

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

PPM法利用

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

(例) x * exp(1-x) の計算

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

Emacs上での操作の再実行

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

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

マクロ登録が不要

Demo: Dynamic Macro

ブラウザ上のDynamic Macro

Firefoxの拡張機能

Dynamic Macroの動作

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

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

Dynamic Macroの動作 (Cont'd)

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

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

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

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

e.g. 仮名漢字変換

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

Flash Fill

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

https://gyazo.com/f4a42294244a13bc370bf36808d5492a.png

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

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

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

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

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

POBoxの具体的手法

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

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

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

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

POBox搭載製品

http://gyazo.com/1822ff6c32df6b726808bf0c3b447408.png

http://gyazo.com/59bb09888b26a2942ada1804c7de555a.png

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

http://gyazo.com/f2c255399d4b1fbc8ab7dbac48b2f088.png

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

Demo: POBox

Chaim (for ChromeBook)

Slime (for Android)

Gyaim (for Mac)

Eager (Cypher)

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

Eager

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

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

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

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

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

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

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

Aza Raskin

Raskinジュニア

https://gyazo.com/22cd113e2f93c5b13867c4520cb7e1b3

Video: Eager

http://masui.org.s3.amazonaws.com/1/5/154a9f7e08985a4d4f66604c78f22d6a.mp4

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

HyperSnapping (増井)

スナッピングを活用した図形編集システム

Dynamic Macroと同様の予測動作

Demo: HyperSnapping

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 前の表示

後退キー 32 最後に入力されたパラメタが表示される

後退キー 5 続けて後退キーを押すとその前のパラメタが表示される

後退キー 9

後退キー 10 最初に入力したパラメタの表示

20 20 新しいパラメタ(20℃)を入力

＝ 68 20℃に対して華氏の計算が再実行される

30 30 さらに別のパラメタ(30℃)を入力

＝ 86 30℃に対する再計算結果

...

再計算の状態遷移

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

例示インタフェース

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

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

Editing by Example

TELS

SmallStar

Triggers

Metamouse

Chimera

Mondrian

Layout by Example

KidSIM

Stagecast

Viscuit

CoScripter

Sicri

Editing by Example (Nix)

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

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

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

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

TELS (Mo)

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

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

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

空白文字の後の数字222-3456の選択、空白文字の後の数字234-5555の選択

↓

空白文字の後の数字2**-**5*の選択の繰り返し というプログラム生成

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

編集前/後のテキスト

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

SmallStar (Halbert)

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

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

http://gyazo.com/dca4a743d9c8da3dbc0132fe656ca9c5.png

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

Triggers (Potter)

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

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

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

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

マイナス記号&#147;-&#148;を示すビットマップパタンを指定してそのパタンの近辺に印をつける操作を例示により定義

http://gyazo.com/cd25caa5d14b850f9a1d9da2d6beb0c9.png

Video: Triggers

http://masui.org.s3.amazonaws.com/7/2/72aa1ce0f26d8af8a3b4c25b7b1e2a79.mp4

Metamouse (Maulsby)

http://gyazo.com/b2c205758a98d4041a4cd24c400a4f64.png

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

Metamouse

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

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

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

ループも表現可能

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

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

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

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

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

Chimera (Kurlander)

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

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

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

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

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

http://gyazo.com/ab3b00b63c4a6b9ac5fba9fd58d93f90.png

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

Mondrian (Lieberman)

図形の編集操作履歴をマクロとして登録

操作前と操作後の状態を示すアイコンの組(Domino)で表現

音声/自然言語利用

http://gyazo.com/d3075719620024ff5e57260c5571f0cc.png

Layout By Example (Hudson)

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

図形が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

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

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

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

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

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

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

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

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

最適な結果を生成

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

例を与えるだけで最適なものが出来るば楽だ!

遺伝的プログラミングによるグラフ配置 (増井)

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

配置の好みをユーザが指定することにより、ユーザと同じ判断を行なう評価関数を遺伝的プログラミングで自動生成

確率的手法

配置のよしあしを反映する評価関数を最適化することにより徐々に良い解を求める

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

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

代表的なアルゴリズム

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

焼きなまし法 (SA)

確率的手法の例

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

http://gyazo.com/d552207ae20dbed910c518d59e48e1ea.png

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

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

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/8fffe45a962630375cf74f6e0898c1fc

進化結果

https://gyazo.com/79e87ba56cfe998929ea40cfbe4e3065

NTT Intercommunication Center(初台オペラシティ)に展示された

9個の進化例の中から好みのものを選ぶことを繰り返す

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

進化した「生物」例

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

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

sbart (畝見)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Brooksによる批判

「予測/例示インタフェースシステムには、

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

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

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

推論に高いコストがかる

といった欠点がある」

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

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

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

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

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

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

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

プログラミング

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

例にもとづく判断

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

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

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

まとめ

単純なPBEは徐々に普及中

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

機械学習の進化で状況は変わるかも