Programming by Example
Henry Lieberman
Media Laboratory
Massachusetts Institute of Technology
Cambridge, MA, USA
[email protected]
http://www.media.mit.edu/~lieber
PBE Web site: http://www.media.mit.edu/~lieber
/PBE/
Henry Lieberman • MIT Media Lab
Your Wish is My Command:
Programming by Example
Morgan Kaufmann, 2001
Henry Lieberman • MIT Media Lab
Programming should be like teaching
User plays the role of a teacher
Computer plays the role of a student
Henry Lieberman • MIT Media Lab
Programming by Example
(Also called "Programming by Demonstration")
Agent "watches what you do" in an interactive
interface
Records sequence of operations, data
Generalizes program so that you can use an
analogous procedure in new examples
"Macros on Steroids"
Henry Lieberman • MIT Media Lab
Programming in the User Interface
The same interface used by end-users can be
used for programming
Empowers end-users to do programming
No switching between user and programmer
interfaces
Empowers "visual thinkers"
Henry Lieberman • MIT Media Lab
PBE and the "Intelligent Agent"
movement
There's been a recent movement toward
"intelligent agents" -- proactive, assistive,
(possibly anthropomorphic) interfaces
PBE can be used to make agents instructible
Agent personalities:
Butler/Servant/Secretary
Teacher/Student, Master/Apprentice
Henry Lieberman • MIT Media Lab
Issues in
Programming by Example
The Generalization Problem (= Data Description)
How do I describe actions and data?
How similar do the actions/data have to be next
time?
Feedback
How does the system show the user what it's
learned?
Advice
How can the user influence or modify what the
Henry Lieberman • MIT Media Lab
system learns?
Issues in
Programming by Example
How should we record the user's actions?
At what granularity should things be recorded?
Can the user interact with the agent during
recording? If so, how?
Do we represent the agent directly in the
interface?
Do we anthropomorphize the agent?
Can users give advice during recording?
Turning recording on and off
Henry Lieberman • MIT Media Lab
Issues in
Programming by Example
How should the recorded program be
represented?
Should the user see the recorded program?
What should it look like?
Should the user interact directly with the recorded
program? If so, how?
How to represent examples?
How to represent generalizations?
Henry Lieberman • MIT Media Lab
Issues in
Programming by Example
How should the user edit an already-recorded
program?
How do we keep the representations consistent
during editing?
Can the user edit previous generalizations?
How can users debug programs?
Can users step/trace/break programs?
Henry Lieberman • MIT Media Lab
Machine learning in
Programming by Example
Lots of work in machine learning
Careful: Watch for hidden assumptions
Few examples, learns fast, explainable
• Explanation-based Generalization
• Case Based reasoning
Lots of examples, slow but more robust
• Neural networks, PAC learning, data-mining
Henry Lieberman • MIT Media Lab
Users of the world, unite!
You have nothing to lose but your error messages!
Almost "political" message of empowerment of
users
Users should not be at the mercy of software
providers
User procedures and data should not be held
hostage by software companies
Henry Lieberman • MIT Media Lab
"Poor man's"
Programming by Example
Macro recorders in applications, AppleScript
Emacs keyboard macros
Interface builders / Scripting languages
Quickeys / OneClick …
Henry Lieberman • MIT Media Lab
Hooking PBE systems to
conventional applications
PBE systems would like to use conventional
interfaces as tools rather than re-implement
apps
Conventional interfaces aren't set up to be
operated by an external program
Issues: Access to application data, sharing the
interface, parallelism
Article: Lieberman, IUI 98 "Attaching Interface
Agents to Conventional Applications"
Henry Lieberman • MIT Media Lab
Watch What I Do
Allen Cypher, ed. MIT Press 1993
Henry Lieberman • MIT Media Lab
A Small Matter of Programming
Bonnie Nardi, MIT Press, 1994.
End-User Programming
Scripting languages
Application-specific languages
"Gardeners"
Henry Lieberman • MIT Media Lab
Eager - Allen Cypher
Programming by example for Hypercard
Notices patterns in user actions
Anticipation highlighting of predicted actions
Anthropomorphization of learning agent
Example: Collect subject lines from messages
Henry Lieberman • MIT Media Lab
Eager
Henry Lieberman • MIT Media Lab
Mondrian:
An Instructible Graphical Editor
Mondrian =
• An object-oriented
graphical editor +
• An agent that records
user interface actions
+
• Learning and
generalization
heuristics
Henry Lieberman • MIT Media Lab
Mondrian:
An Instructible Graphical Editor
Henry Lieberman • MIT Media Lab
Wizard of Oz Experiment
Human simulates agent
What kinds of communication between human and
agent are plausible?
What kind of knowledge does the agent need to
know to perform the task?
Henry Lieberman • MIT Media Lab
Wizard of Oz experiment task
Reformat a Bibliography
• Lieberman, H., The One True Path to
Intelligent Agents, International Conference
on Buzzwords and Hype, Tahiti, 1996.
• [Lieberman 96] The One True Path to
Intelligent Agents, Int. Conf. on Buzzwords
and Hype, Tahiti, (1996).
• Oz, Wizard Of, Pay No Attention to the Man
Behind the Curtain, Journal of Smoke and
Mirrors, August 1942, Emerald City, Oz.
Henry Lieberman • MIT Media Lab
Wizard of Oz results
Users can make mistakes
Information can be incomplete
Agents can ask the user if they encounter an error
situation
Agent could ask the user to supply missing
information
Agent could ask the user to edit the example
Skip steps that don't work
Henry Lieberman • MIT Media Lab
Wizard of Oz experiment method
User performs task once
• “Thinking aloud”: goals and methods
Agent (secretly) constructs description of actions
• In terms of simple “implementable” operations
Agent offers help
Agent performs help according to action description
Agent gives user feedback
Agent accepts advice from user
Henry Lieberman • MIT Media Lab
Survey of "Your Wish" systems
Astonishingly wide variety of application domains:
Kids, Games, CAD, GIS, Text editing, Graphical
editing, Web browsing, Animation, Databases,
etc.
Illustrates variety of design decisions in PBE
systems
Different reps for programs, agents, etc.
How much inference, generalization, initiative?
Henry Lieberman • MIT Media Lab
Stagecast Creator
- Smith, Cypher
Programming for kids, grid game world
If you see this pattern of squares, replace it with that pattern
of squares
Viz rep of rules, editor/stepper
Generalization on object types, introduce variables
Commercially available, success with thousands of users
Henry Lieberman • MIT Media Lab
A Stagecast Creator Rule
Henry Lieberman • MIT Media Lab
A Stagecast Creator Game
Henry Lieberman • MIT Media Lab
Toontalk - Ken Kahn
Programming language is a video game
Most radical programming model
Concurrent logic programming
Abstraction by removing detail
Commercially available, success with kids in
schools
Henry Lieberman • MIT Media Lab
Toontalk's Visual Language
Henry Lieberman • MIT Media Lab
Generalizing by Removing Detail
Henry Lieberman • MIT Media Lab
Toontalk Sort program
Henry Lieberman • MIT Media Lab
How much intelligence?
- Brad Myers, Rich McDaniel
CMU group one of most active and consistent in
PBE
Multitude of systems, "gems" of PBE
Peridot, Lapidary, Jade, Gilt, Tourmaline, C32,
Pursuit, Gold, Marquise, Katie, Turquoise, Topaz,
Gamut
Experience with range of conservative to radical
PBE systems
"Spectrum of Instructibility"
Tradeoff between conveience Henry
andLieberman
control
• MIT Media Lab
Pursuit's Visual Language
Henry Lieberman • MIT Media Lab
Selecting Generalizations in
Marquise
Henry Lieberman • MIT Media Lab
Internet Scrapbook - Sugiura
Everybody's favorite application area - the Web!
Automates Browse & Cut & Paste applications
How do you describe a Web page selection?
Partial matching, Web design heuristics
Commercially available - preloaded on NEC PCs
Henry Lieberman • MIT Media Lab
Internet Scrapbook
Henry Lieberman • MIT Media Lab
TriAS - Bauer, Meyer, Dengler, Paul
Automating Browse & Copy & Paste, like
Scrapbook
Collaborative, mixed-initiative dialog
At any time, agent or user can propose
selections, generalizations
What Next? Can I Stop?
Integrates wrapper description language HyQL,
InfoBeans dynamic Web sources
Henry Lieberman • MIT Media Lab
Collaborative Wrapper Definition
Henry Lieberman • MIT Media Lab
PBE for GIS: CSprl
- Traynor, Williams
Study of how end users use Geographical
Information Systems
"Gardeners", "Surrogate Users"
Comic-strip PBE language
Henry Lieberman • MIT Media Lab
A Geographical Info Systems
PBE Program
Henry Lieberman • MIT Media Lab
Visual Language for Geographic
Information Systems
Henry Lieberman • MIT Media Lab
PBE for Computer Aided Design Girard, Pierra
True "Industrial Strength" PBE, probably the
champ
CAD users are sophisticated in application
domain, willing to specify a lot
Provides complete editing and debugging
Key issues: Naming, Ambiguity in spec/solutions,
general control structures: conditionals, loops
Henry Lieberman • MIT Media Lab
Example-Based Programming in
Computer-Aided Design
Henry Lieberman • MIT Media Lab
Demonstrating "Hidden
Features" - McDaniel, Myers
PBE for animated computer games
WYSIWYG - "What you get is all you have"
Demonstrate "hidden features" by reifying them
Guides, e.g. Arrows for directions
Sophisticated heuristics, lots of inference
Stop This!
Do Something!
Henry Lieberman • MIT Media Lab
Demonstrating Hidden Features
Henry Lieberman • MIT Media Lab
Report Generation - Masuishi
Mundane, but hey, could save a lot of time
Format generalization
Application-specific iteration
Distributed to wide user community
Henry Lieberman • MIT Media Lab
Report Generation by Example
Henry Lieberman • MIT Media Lab
Dynamic Macro - Masui
Notices loops in text editing commands
Simple, automatic: No start/stop recording
Wide community of users
Also: POBox predictive input for PDAs, phones,
etc.
Henry Lieberman • MIT Media Lab
Dynamic Macro
Henry Lieberman • MIT Media Lab
SmartEdit - Lau, Domingos,
Wolfman, Weld
Automates repetitive text-editing procedures
Predictive, anticipatory, loop detection
Uses version-space learning
Henry Lieberman • MIT Media Lab
SmartEdit Version Space
Henry Lieberman • MIT Media Lab
SmartEdit Screens
Henry Lieberman • MIT Media Lab
Grammex: "Grammars by Example"
- Lieberman, Nardi, Wright
Pick out "needles" of structured information in
"haystack" of unstructured information
First direct-manipulation user interface to
powerful grammar and parsing technology
Show example strings, explain components
recursively
Iterative: System parses, you explain
Henry Lieberman • MIT Media Lab
Defining Recursive Grammars
Henry Lieberman • MIT Media Lab
Visual representation of regular
expressions - Blackwell
SWYN: "See what you need"
Representation of positive and negative examples
Anticipation of selections updated dynamically
Representation of grammars as Finite-State
machines
User study of understandability of representations
Henry Lieberman • MIT Media Lab
Visual representation of
Regular Expressions
Henry Lieberman • MIT Media Lab
APE: PBE for Programming
Environments - Ruvini, Dony
Combining predictive interfaces with PBE
Conventional programming environment:
Smalltalk
Automates coding, debugging procedures
What-set, When-set use different learning
algorithms
C4.5, new algorithm IDHYS can learn nonconsecutive patterns
Henry Lieberman • MIT Media Lab
Repetitive code in protocols
Henry Lieberman • MIT Media Lab
Familiar - PBE across
applications - Paynter
PBE for Applescript
Application-independent, no mods to applications,
uses commercial OS scripting language
Limited by shortcomings of Applescript and
application implementations
Henry Lieberman • MIT Media Lab
Familiar arranging files
Henry Lieberman • MIT Media Lab
Tatlin - Gaxiola, Lieberman
Examinability: Some applications will let you look
at their data even if you can't record them or use
API
PBE by comparing states and inducing
transformations rather than recording and
generalizing actions
Henry Lieberman • MIT Media Lab
Tatlin - PBE via Examinability
Henry Lieberman • MIT Media Lab
Demonstrating What vs. When
- Wolber, Myers
Saying "when" you want something to happen
Stimulus-Response PBE
Pavlov: Animation scripting system like
Macromind Director
Henry Lieberman • MIT Media Lab
Pavlov driving game
Henry Lieberman • MIT Media Lab
Programming by Analogous
Examples - Repenning, Perrone
Agentsheets - Grid world like Stagecast Creator
If-then rules by example
Make generalizations by analogy to
generalizations of previous examples
Henry Lieberman • MIT Media Lab
Programming by
Analogous Examples
Henry Lieberman • MIT Media Lab
Visual Generalization - St. Amant,
Zettlemoyer, Lieberman, Potter
Actually parse the screen!
Simulate human user's visual system
Finesses data access problem, hooking to
applications
Fragile - if viz rep changes, you're screwed
Permits unique visual generalizations not possible
by accessing data
Henry Lieberman • MIT Media Lab
Triggers - "Just the pixels, ma'am"
S te p 1 - Se le ct U R L tex t fi eld:
S te p 2 - Start m ou se d rag t o selec t deepe st d ire ctory :
S te p 3 - Fin is h m ous e d rag :
S te p 4 - Press backsp a ce to de lete t he selec tion :
Henry Lieberman • MIT Media Lab
Solitaire by "Parsing the screen"
Henry Lieberman • MIT Media Lab
“Short order programming”
exercise
Task: Add similarity-based learning to an actionbased learning system
Ingredients: Graphical editor, action recording,
relation inference
Henry Lieberman • MIT Media Lab
Things to think about
How could we integrate the paradigms of
Mondrian and Eager?
What sort of information do we need to get from
the graphical editor?
What should the learning algorithm learn?
How should the result of learning affect the
interface?
Henry Lieberman • MIT Media Lab
Descargar

Programming by Example Tutorial