Automatically Personalizing
User Interfaces
Daniel Weld
University of Washington
Acknowledgements

Corin Anderson
Oren Etzioni
Pedro Domingos
Krzysztof Gajos
Keith Golden
Cody Kwok
Tessa Lau
UW AI Group

NSF, ONR, NASA, DARPA, WRF







3-Oct-15
Daniel S. Weld / Univ. Washington
2
Two Interface Trends
Usage
4x
3-Oct-15
Variation
625x
Daniel S. Weld / Univ. Washington
3
“Steelcase-Inspired Software”
-- David Gelernter

One
Fits All Adaptivity
NeedSize
Increased
• Beyond inconsistent defaulting
Adapt
 Adapt
 Adapt
 Adapt


to
to
to
to
available devices, interaction modes
user location, tasks & goals
user calendar & current time
network connectivity, …
Need Increased Customization
• Beyond changing buttons on the toolbar
Overriding inappropriate adaptation
 High-level functionality
 Programming by demonstration

3-Oct-15
Daniel S. Weld / Univ. Washington
4
Adaptivity & Customization
 Consistent
Across Applications
 Adaptation
 Bridging
in every ‘dialog’
Applications
 Data
gathering
 Transformations
 Deep
3-Oct-15
Deployment ~ OS layer
Daniel S. Weld / Univ. Washington
5
Outline
High-level
Customization
 Motivation
 Deliberative
Software Agents
 Programming by Demonstration
 Adapting User Interfaces to
 Screen
Size
 User Behavior
Pure
Adaptation
3-Oct-15
Daniel S. Weld / Univ. Washington
6
Genesis: Internet Softbots

Interface Principles:
Goal-Oriented
 Integrated
 Balanced
 Safe

3-Oct-15
[Etzioni & Weld CACM 94]
User says what she wants
Single,
Agentexpressive
determines &how &
uniform
when interface
to achieve it
DT-lite: “Softbot must
E.g.,
printing
files
vs.
balance
the cost
of finding

planning-based
Asimov’s first law… softbots
FTPingon
them
information
its own with
Safety, tidiness &
the nuisance of asking the
thriftiness
user.”
constraints in planner
Daniel S. Weld / Univ. Washington
7
Softbot
UW Softbot
Project
Family
Observations
Tree

Rodney
Specifying goals is bottleneck


Logical spec. language ?!$@#!
Simon
Forms interface
• Limited to anticipated use
• Not scalable
Info Manifold

BargainFinder
MetaCrawler
Grouper Ahoy
Often easier to just do task!
ShopBot
• Except: data integration tasks
Occam
Wrapper Induction
Razor

Natural language interfaces


[Popescu et al; Yates et al 03]
…
LSD
Mulder
Tukwila
GLUE
Piazza
Programming by demonstration
3-Oct-15
ILA
Daniel S. Weld / Univ. Washington
KnowItAll
8
Outline
High-level
Customization
 Motivation
 Deliberative
Software Agents
 Programming by Demonstration
 Adapting User Interfaces to
 Screen
Size
 User Behavior
Pure
Adaptation
3-Oct-15
Daniel S. Weld / Univ. Washington
9
Programming by Demonstration
[Lau & Weld IUI-99]
[Wolfman et al. IUI-01]
[Lau et al. ICML-01]
If it’s too hard for users to specify goals
 Let’s watch them…

And try to help
 Like plan recognition


Initial domains:
Email
 Text editing
 Cross domain

3-Oct-15
Daniel S. Weld / Univ. Washington
10
Objectives
Macro Record On / Off
Straight Ln Brittle
VBasic Programing Turing Cplt
Robust
None
Varying
Lots
Previous PBD
Little
Varying
SmartEdit
SmartPython
On / Off
Loops,Cond Robust
3-Oct-15
None
Daniel S. Weld / Univ. Washington
Minimal
11
SmartEdit 1
[Lau et al. ICML-01]
3-Oct-15
Daniel S. Weld / Univ. Washington
12
2
3-Oct-15
Daniel S. Weld / Univ. Washington
13
3
3-Oct-15
Daniel S. Weld / Univ. Washington
14
4
3-Oct-15
Daniel S. Weld / Univ. Washington
15
5
3-Oct-15
Daniel S. Weld / Univ. Washington
16
6
3-Oct-15
Daniel S. Weld / Univ. Washington
17
PBD as a learning problem

Action is function : input state  output state


Editor state: text buffer, cursor position, etc.
Actions: move, select, delete, insert, cut, paste,…
Move
to next
<!-
Given a state sequence, infer actions


Delete
to next
-->
Many actions may be consistent with one example
Challenge: Weak bias + low sample complexity
3-Oct-15
Daniel S. Weld / Univ. Washington
18
Version Space Algebra


Version space = set of complex functions
Define version space hierarchically

Algebraic operators for combing VSs
• Union  : analogous to set union
• Join
: cross-product with consistency predicate
• Transform: convert functions to different types

Can factor a version space
3-Oct-15
Daniel S. Weld / Univ. Washington
19
SMARTedit's version space
…
3-Oct-15
…
…
…
Daniel S. Weld / Univ. Washington
20
Fast Consistency


Test consistency of example against
entire version space
Quickly prune subtrees
Action
Move
Paste
Insert
Select

Copy
Delete
Cut
Innovations:

Independent join allows BSR representation
3-Oct-15
Daniel S. Weld / Univ. Washington
21
Preliminary User Study




6 undergrad CS majors
7 repetitive tasks with & later w/out SMARTedit
Tasks: 4 to 27 iterations, 1-5 min to complete
Evaluation metrics:



Time saved completing task with SMARTedit's help
% user actions (keyboard + mouse) saved
User feedback
3-Oct-15
Daniel S. Weld / Univ. Washington
22
Time saved using SMARTedit
300
Cost
Time (sec)
T im e s av ingsSaved
(s ec )
250
200
150
100
A
B
50
C
D
0
X
X
E
- 50
Six
Users
F
- 100
- 150
- 200
1
2
3
4
5
6
T as k
Task Number
3-Oct-15
Daniel S. Weld / Univ. Washington
23
Action Savings with SMARTedit
100
Cost
P e rc e nt s a v ings
Saved
Percent of Actions
80
60
40
A
B
20
C
D
0
E
X
- 20
X
XXXX
Six
Users
F
- 40
- 60
1
2
3
4
5
6
Task Number
Ta s k
3-Oct-15
Daniel S. Weld / Univ. Washington
24
Observations from PBD

Overhead of macro recorder UI is high
Most repetitive tasks short
 How many shell scripts do you write / day?


Should focus on pure adaptivity

E.g., automatic segmentation
3-Oct-15
Daniel S. Weld / Univ. Washington
25
Outline
High-level
Customization
 Motivation
 Deliberative
Software Agents
 Programming by Demonstration
 Adapting User Interfaces to
 Screen
Size
 User Behavior
Pure
Adaptation
3-Oct-15
Daniel S. Weld / Univ. Washington
26
Early Adaptation: Mitchell,Maes



Predict:
Principle 1:
Principle 2:
3-Oct-15
Email message priorities
Meeting locations, durations
Defaults minimize cost of errors
Allow users to adjust thresholds
Daniel S. Weld / Univ. Washington
27
Adaptation in Lookout: Horvitz
3-Oct-15
Daniel S. Weld / Univ. Washington Adapted from Horvitz
28
Resulting Principles
[Horvitz CHI-99]

Decision-Theoretic Framework
Graceful degradation of service precision
 Use dialogs to disambiguate

(Considering cost of user time, attention)
3-Oct-15
Daniel S. Weld / Univ. Washington Adapted from Horvitz
29
Principles About Invocation
Allow efficient invocation & dismissal
 Timeouts minimize
cost of prediction
errors

3-Oct-15
Daniel S. Weld / Univ. Washington
30
Adapting to Device Characteristics
Func
Interface
Spec
+
Hierarchy of
State vars +
Methods
Device
Model
Custom
Interface
Rendering
Screen size
AvailableApproaches:
widgets
Interaction
modes
•Templates
•Expert System
•Optimization
3-Oct-15
Daniel S. Weld / Univ. Washington
31
Optimize Widgets & Layout
Available widgets = F(type(state-var))
 E.g. for an integer


For hierarchy

Tabs, adjacent panes, …
3-Oct-15
Daniel S. Weld / Univ. Washington
32
SUPPLE

Optimization methods
[Gajos & Weld, draft 2003]
Branch & bound vs. local search
 CSP: MRV, FC


Cost function = minimize user effort
Navigation + manipulation
 Component importance ( trace data)

3-Oct-15
Daniel S. Weld / Univ. Washington
33
SUPPLE Output
3-Oct-15
Daniel S. Weld / Univ. Washington
34
SUPPLE Output
3-Oct-15
Daniel S. Weld / Univ. Washington
35
SUPPLE Output
260,000,000 possibilities
 Simulated annealing fastest
 Can improve with bin-packing methods

3-Oct-15
Daniel S. Weld / Univ. Washington
36
Web Pages on Small Screens
3-Oct-15
Daniel S. Weld / Univ. Washington
37
Web Site Adaptation in Proteus
[Anderson et al. WWW-01]
Visitor

Proteus
Web server
Personalizing in two steps:
1. Learn model of visitor from access logs
2. Transform content per learned model

Hill-climbing thru space of websites


Transforms: shortcuts & elision
Expected utility of candidate site =
• Sum of utility of each screen of each page
• Discounted by access difficulty (#links, scrolling)
3-Oct-15
Daniel S. Weld / Univ. Washington
38
Analysis of Proteus
Why Proteus worked well
Suggested useful shortcuts
Elided mostly unnecessary content
Why Proteus worked poorly
Links followed
Sometimes elided useful content
Users didn’t find shortcut, tho it existed
Flaws with implementation, not concept
3-Oct-15
Personalized
Unmodified
Daniel S. Weld / Univ. Washington
39
Principles
Eliminating features is dangerous
Accurate prediction is crucial
Saliency of new UI operations is crucial
How name shortcuts?
Must partition dynamicity
Maintain separate dynamic & static “areas”
Always allow previous navigational methods
Duplicate functionality if necessary
3-Oct-15
Daniel S. Weld / Univ. Washington
40
Partitioned Dynamism
3-Oct-15
Daniel S. Weld / Univ. Washington
41
Partitioned Dynamism
3-Oct-15
Daniel S. Weld / Univ. Washington
42
Partitioning Failure
3-Oct-15
Daniel S. Weld / Univ. Washington
43
Principles
Must partition dynamicity
Accurate prediction also crucial
3-Oct-15
Daniel S. Weld / Univ. Washington
44
Predicting User Behavior
[Anderson et al. IJCAI-01]

Model as Sequential Process

Markov Models
P(sd) =
# times sd was followed
Total # visits to s
Mixtures of Markov Models
 Second-Order…
 Conditioning on Position in Trace
 Etc.

3-Oct-15
Daniel S. Weld / Univ. Washington
45
Weakness of Markov Models

Each state is trained independently



Abundant training data at one state cannot
improve prediction at another state
Large state models  vast training data
Problem: Web trace data is sparse
A single visitor views ~0% of any site
 New & dynamic content not in training data

3-Oct-15
Daniel S. Weld / Univ. Washington
46
Reasoning about Uncertainty
DPRM
PRM
DBN
Structure
Bayes Net
RMM
Sequence
3-Oct-15
Sanghai et al.
Thurs 12:10
Cholula 3
Markov Model
Daniel S. Weld / Univ. Washington
47
Relational Markov Models
[Anderson et al. KDD02]

Domains often contain relational
structure

Each state is a tuple in relational DB sense
ProductPage
ProductName
Apple_iMac
Palm_m505
StockLevel
in_stock
backorder
Structure enables state generalization
 Which allows learning from sparse data

3-Oct-15
Daniel S. Weld / Univ. Washington
48
Defn: Relational Markov Model
 Q: set of states
Pages in a web site
 Each state ~ a relation

ProductPage(Apple_iMac, in_stock)
 p: init prob distribution
 A: transition probability matrix
 D: a set of hierarchical domains
 R: a set of relations
3-Oct-15
Daniel S. Weld / Univ. Washington
49
Domain Hierarchies
Instance of relation
with leaf values is a
state, e.g.
ProductName
AllProducts
…
AllComputers
AllPDAs
…
ProductPage(iMac, in_stock)
AllDesktops
…
AppleDesktops …
…
3-Oct-15
iMac
…
Daniel S. Weld / Univ. Washington
50
Domain Hierarchies
Instance of relation with
non-leaf values is a set of
states: an abstraction, eg
ProductName
AllProducts
…
AllComputers
…
ProductPage(AllComputers, in_stock)
AllPDAs
AllDesktops
…
AppleDesktops …
…
3-Oct-15
iMac
…
Daniel S. Weld / Univ. Washington
51
E-commerce Site: Markov
RMMVer.
MainEntryPage()
ProductPage(AllProducts,
AllStockLevels)
CheckoutPage()
…
ProductPage(AllProducts,
backorder)
main.html
m505_backorder.html
checkout.html
…
ProductPage(AllProducts,
instock)
iMac_instock.html
dell4100_instock.html
3-Oct-15
Daniel S. Weld / Univ. Washington
52
RMM generalization

Want to estimate P(s


d) … but no data!
Use shrinkage
s
3-Oct-15
d
Daniel S. Weld / Univ. Washington
53
RMM generalization

Want to estimate P(s



d) … but no data!
Use shrinkage
Can do this with abstractions of d and s

Let  be an abstraction of s and  of d

3-Oct-15
s
d

Daniel S. Weld / Univ. Washington
54
RMM generalization

Want to estimate P(s



d) … but no data!
Use shrinkage
Can do this with abstractions of d and s

Let  be an abstraction of s and  of d
P( | s) P(   ) P(d |  )
s
s
3-Oct-15
dd


Daniel S. Weld / Univ. Washington
55
RMM generalization

Want to estimate P(s



d) … but no data!
Use shrinkage
Can do this with abstractions of d and s

Let  be an abstraction of s and  of d
P( s  d )  
  P( | s) P(   ) P(d |  )
  Abs( s )  Abs( d )
s
3-Oct-15
d
Daniel S. Weld / Univ. Washington
56
Calculating Shrinkage Weights
Intuitively, the  should be large when
Abstractions are more specific
Training data is abundant
Three methods for assigning weights
Uniform
Heuristic (Based on lattice depth, # of examples)
EM
(Data intensive)
3-Oct-15
Daniel S. Weld / Univ. Washington
57
Gazelle
A vg erag e n eg ative lo g likelih o o d
8 .5
R M M -u n ifo rm
8 .0
R M M -ra n k
7 .5
R M M -P E T
PMM
7 .0
6 .5
6 .0
5 .5
5 .0
4 .5
4 .0
3 .5
10
3-Oct-15
100
1000
10000
N u m b e r tra in in g e x a m p le s
Daniel S. Weld / Univ. Washington
100000
1000000
58
The Google Generation

Most WWW traces very short


Can’t beat |trace| = 2
Not true in desktop / mobile apps
Adapt to user behavior
 Adapt to device characteristics

3-Oct-15
Daniel S. Weld / Univ. Washington
59
Striving for Duplex
3-Oct-15
Daniel S. Weld / Univ. Washington
60
Still Striving for Duplex
3-Oct-15
Daniel S. Weld / Univ. Washington
61
Finally!
3-Oct-15
Daniel S. Weld / Univ. Washington
62
Confirm (Twice!)
3-Oct-15
Daniel S. Weld / Univ. Washington
63
State machine (partial)
main
ok,
cancel
^P
printer,
range,
copies,
frames,
links
ok,
cancel
features
properties
print
setup
color
ok,
cancel
ok,
cancel
services
ok,
cancel
Six clicks required!
3-Oct-15
Daniel S. Weld / Univ. Washington
64
Remember: Partitioned Dynamicity
Proteus: Users didn’t find shortcuts!
Saliency of new UI operations is crucial
Must partition dynamicity
Maintain separate dynamic & static “areas”
Duplicate functionality
3-Oct-15
Daniel S. Weld / Univ. Washington
65
With Controlled Adaptation
Maintain
Stable
Navigation
Optimize
For
User
Behavior
3-Oct-15
Daniel S. Weld / Univ. Washington
66
Or Rather…
Curry to Boolean
3-Oct-15
Daniel S. Weld / Univ. Washington
67
Challenges for AI
 Formalizing
 Pebbles,
interface descriptions
iCrafter, XIML, …
 Customization
 Rec
start/stop; shortcut; make default
 Datamining
 Improved
 Interface
 Complex
3-Oct-15
languages
the clickstream
prediction;  dim +  data
transformation algorithms
constraint satisfaction
Daniel S. Weld / Univ. Washington
68
Conclusion




Goal-oriented softbots
Programming by demonstration
Adaptive interfaces / websites

Pure
Adaptation
Principles

High-level
Customization
Partitioned Dynamicity
Techniques


3-Oct-15
Version-Space Algebra
Relational Markov Models
Daniel S. Weld / Univ. Washington
69
The End
3-Oct-15
Daniel S. Weld / Univ. Washington
70
Abstract

3-Oct-15
Today’s computer interfaces are one size fits all. Users with little
programming experience have very limited opportunities to
customize an interface to their task and work habits.
Furthermore, the overhead induced by generic interfaces will be
proportionately greater on small form-factor PDAs, embedded
applications and wearable devices. Searching for a solution,
researchers argue that productivity can be greatly enhanced if
interfaces anticipated their users, adapted to their preferences,
and reacted to high-level customization requests. But realizing
these benefits is tricky, because there is an inherent tension
between the dynamism implied by automatic interface adaptation
and the stability required in order for the user to predict the
computer’s behavior and maintain control. This talk will list
challenges for the field, describe principles governing effective
adaptation, and present new algorithms for data mining user
action traces and dynamically transforming interfaces.
Daniel S. Weld / Univ. Washington
71
Gentle-Slope Systems
C
Click’nCreate
VBasic
Hypercard
Hypertalk
Basic
Difficulty
of use
C
C Plugins
kCmds
MFC
(Multimedia Fusion)
Ideal
Sophistication of what can be created
3-Oct-15
Daniel S. Weld / Univ. Washington Adapted from Myers et al.72
Learning programs from traces

Illustrated VS algebra with SMARTedit

Grand vision: cross-domain PBD



Learn an abstract programming language
SMARTpython: learn Python programs
Lau PhD thesis

Loops, conditionals, …
3-Oct-15
Daniel S. Weld / Univ. Washington
73
Req’s for Interface Representation

Same as Pebbles Project?




3-Oct-15
State variables
Typing
Commands
Hierarchical organization
Daniel S. Weld / Univ. Washington
74
Adaptation in Pebbles
See next talk…
3-Oct-15
Daniel S. Weld / Univ. Washington
75
State abstractions form lattice
ProductPage(AllProducts, AllStockLevels)
ProductPage(AllProducts, in_stock)
ProductPage(AllComputers, AllStockLevels)
ProductPage(AllComputers, in_stock)
ProductPage(AllDesktops, AllStockLevels)
ProductPage(AllDesktops, in_stock)
ProductPage(AppleDesktops, AllStockLevels)
ProductPage(AppleDesktops, in_stock)
ProductPage(iMac, AllStockLevels)
ProductPage(iMac, in_stock)
3-Oct-15
Daniel S. Weld / Univ. Washington
76
Guiding the Search
Expected utility based on model of visitor
Model learned by mining server access logs
Sum value of each screen
of each page
Discount by difficulty of
reaching screen from p
=p
Depends on how many
links followed and how
much scrolling required
3-Oct-15
Daniel S. Weld / Univ. Washington
77
Specifics of Screen Evaluation
Expected
utility of sij
E[U ( sij )] 
Similarity to
past content
Frequency of
past visits
Intrinsic
utility
 simsim ( sij )   freq freq( sij ) 
P(scroll ) ( E[U ( si , j 1 )]
[ P( L )
k
  (scroll )) 
( E[U ( Lk .dest )]   ( Lk ))]
Extrinsic
utility
links
Lk
Probability
action taken
3-Oct-15
Expected utility
Cost of
of destination taking action
Daniel S. Weld / Univ. Washington
78
Proteus Empirical Study
Observe real users on the desktop

Info-seeking goals drawn from random
distribution
Personalize based on observations
Measure performance on mobile device
Number of links and scrolls, amount of time
 Compare unmodified and personalized sites

•
3-Oct-15
Half users did unmodified first, others vice versa
Daniel S. Weld / Univ. Washington
79
Average number links followed
5
U n m o d ifie d
A v e ra g e n u m b e r o f lin k s fo llo w e d
P e rs o n a liz e d
4
3
2
1
0
c s .w a s h in g to n .e d u
3-Oct-15
fin a n c e .ya h o o .c o m
e b a y.c o m
Daniel S. Weld / Univ. Washington
c n n .c o m
c n e t.c o m
80
RMM generalization

Want to estimate P(s



d)
Use shrinkage
Can do this with abstractions of d and s

Let  be an abstraction of s and  of d
P( s  d )  
 
P( | s) P(   ) P(d |  )
  Abs( s )  Abs( d )

s
d




P(   )    P(i |  )  P(i  j )
i 
j

3-Oct-15
Daniel S. Weld / Univ. Washington
81
Backup

Want to estimate P(s



d) … but no data!
Use shrinkage
Can do this with abstractions of d and s

Let  be an abstraction of s and  of d
P( s  d )  
  P( | s) P(   ) P(d |  )
  Abs( s )  Abs( d )
s
s
3-Oct-15
dd


Daniel S. Weld / Univ. Washington
82
Descargar

Print Dialog #1 - University of Washington