Transcript mikaelS - Mälardalens högskola

Mikael Sollenborn, CSL, Eyescream AB
Artificial Intelligence and
Case-Based Reasoning
Computer Science and Engineering
Mälardalen University
Västerås, Sweden
@mdh.se
What is Case-Based
Reasoning
• A model of human problem solving and
reasoning
• A method for building ”intelligent”
computer systems
CBR as a model of
human reasoning
• Most of the problems a decision maker
has to deal with aren’t unique
• When solving new problems, we tend to
reuse solutions to similar problems
• People generally prefer examples to
rules (and besides, rules are generally
not available)
CBR as a method of
building ”intelligent”
systems
• stores previous experience in a case-library
• solves new problems by:
1) retrieving similar cases from the case library
2) reusing full or part of the cases in the context of the new
problem
3) adapting the solution to match current problem
4) storing new case. i.e. new problem and solution in case library
General architecture of a CBR system
Problem
Learning from past
cases, building up
experience, improving
performance and
adapting to changing
environment.
RETRIEVE
Problem
Solution
R
E
U
S
E
RETAIN
Case Library
REVISE
Confirmed
Solution
Proposed
Solution
CBR Essential works
• R. Schank (1982): Dynamic memory: a theory of
learning in computers and people
• C.K. Riesbeck, R. Schank (1989): Inside Case-Based
Reasoning
• J. Kolodner (1993): Case-Based Reasoning
• I. Watson (1995): Progress in Case-Based
Reasoning
Personalisation
• Personalisation prototype developed for
Eyescream AB for Masters Thesis
• How to create applications/web pages
whose behaviour changes dynamically
according to user preferences
– Information filtering (handling the
information overload problem)
– User Modelling (what we know about the
user, and how to utilise this knowledge)
What is Information
Filtering
• From a large amount of data/items,
extract the interesting parts
• Used in Recommender Systems,
typically using
– Content-based filtering
– Collaborative filtering
Recommender (hybrid)
systems
1. Record the behaviour of a large
number of people
2. Select a number of users whose past
behaviour is similar to the current user
3. Make recommendations based on the
similar users preferences and the user’s
own preferences
Content-based filtering
(CBR)
• Items are cases
• Category belonging and other metadata is the problem-description of a
case
• Compare current user preferences with
items, selecting the closest matching
”solutions”
Automated collaborative
filtering (ACF)
• Based on ”peer reviews”
• Similar users recommend items
(unknowingly) to each other
Essential works
• Collaborative filtering
– U. Shardanand, P. Maes(1995): Social information filtering:
algorithms for automating ’word of mouth’
– Hill et.al(1995): Recommending and evaluating choices in a virtual
community of use
• Content-based filtering
– K. Lang(1995): Newsweeder: learning to filter netnews
– Pazzani et.al(1996): Syskill & Webert: Identifying interesting web
sites
• Recommender systems
– H. Kautz(editor)(1998): Recommender systems. Papers from 1998
workshop
– I. Soboroff et.al(editors)(1999): ACM SIGIR’99 Workshop on
Recommender Systems: Algorithms and Evaluation
Problems with
recommender systems
• Response time (all reasoning done
online)
• Poor performance in domains where
items are often added and removed
• Crude recommendations, using only two
dimensions (users, items)
Handling response time
• Precalculating similarity metrics
– with 100 000 users, it may still not be good
enough
• Collective models, created offline using
clustering techniques
– faster retrieval
– will loose accuracy in the process?
Handling dynamic
domains
• Identify fine-grained item categories
– Categorise each new item by one or more
categories, possibly using text extraction
techniques
– When new items arrive, systems knows
current user or similar users attitude
towards the item categories
Adding rating
dimensions
• R: Users x Items  Rating
• Rmovies(John, Nosferatu 5)  10
• Multi-dimensional: users, items, time of
day, time of year etc.
– R: D1xD2x…....Dn  Rating
• Rmovies(John, Nosferatu 5, 15.00, 24 Dec)  1
• …which leads us to...
User Modelling
• How to gather information about a user
or users, his/her/their preferences etc.
• How to use the gathered information to
help satisfy the users needs
User Modelling essential
works
• A.J. Kok, 91: A review and synthesis of
user modelling in intelligent systems
• A. Kobsa, 93: User Modeling, recent
work, prospects and hazards
Acquiring user models:
asking the user
• Invasive
• Rich information, but
– users could be giving incorrect answers
– users are easily annoyed
• How do we ask the right questions?
Acquiring user models:
tracking the user
• Non-invasive
• Observe user behaviour
– What is clicked
– How long is the information viewed
– In what context are decisions made
–…
• Hard to evaluate, noisy information
User Modelling for
WWW
• Invasive
– Explicit rating
– Personal questions
• Non-Invasive
– Clicks
– Click context
– Time read
– Following mouse movements
– Personal info through ordering forms
User modelling for
learning systems
• Users are generally more positive
towards invasive techniques (if they
attain positive changes)
• Users will stay longer and will be
generally more interested in the
information content
Summary & Conclusions
Methods and techniques from Artificial Intelligence
have already proven to be useful in many
application areas and have still much to offer.
Case-Based Reasoning and User Modelling is a
promising combination, especially in
internet/intranet applications.