Transcript Automated changes of problem representation

Automated Changes of
Problem Representation
Eugene Fink
LTI Retreat 2007
Outline
• Research interests and projects
• Concept of representation
• Representation-changing system
• Future research challenges
Research interests and projects
1992–1998 Ph.D. Student
1999–2003 Assistant Professor
2004–2007 Systems Scientist
Research interests
• Artificial intelligence
Major
• Machine learning
• Algorithm theory
Minor
• Computational geometry
Main projects
• Artificial intelligence
• Machine learning
• Algorithm theory
Representation changes
in AI search (Prodigy)
Indexing of massive approximate data (Argus/Rapid)
Optimization and elicitation
under uncertainty (Radar)
Exchange markets for
complex commodities
Medical expert systems
• Computational geometry
Indexing of time series
Generalized convexity
Research themes
Automated improvement of representations
Efficient reasoning
under uncertainty
Collaboration with
the human user
Heuristic search
in indexing trees
Representation changes
in AI search (Prodigy)
Indexing of massive approximate data (Argus/Rapid)
Optimization and elicitation
under uncertainty (Radar)
Exchange markets for
complex commodities
Medical expert systems
Indexing of time series
Generalized convexity
Research themes
Automated improvement of representations
Efficient reasoning
under uncertainty
Collaboration with
the human user
Heuristic search
in indexing trees
Representation changes
in AI search (Prodigy)
Indexing of massive approximate data (Argus/Rapid)
Optimization and elicitation
under uncertainty (Radar)
Exchange markets for
complex commodities
Medical expert systems
Indexing of time series
Generalized convexity
Outline
• Research interests and projects
• Concept of representation
• Representation-changing system
• Future research challenges
Concept of representation
Informally, a representation is a
specific approach to solving a
problem or class of problems.
Psychologists and computer
scientists have accumulated
evidence on the importance of
appropriate representations for
both human problem solvers
and software systems.
Examples:
• Efficient indexing structures vs. linear search
• Java vs. assembly language
• Well written vs. poorly written papers
Motivation
When humans works on a
complex problem, they may
need to search for the right
approach to the problem.
The related AI challenge is
to automated the search for
the right approach.
Aha!
Definition of representation
A representation consists of three parts:
• Problem or class of problems
• Data structures for representing them
• Algorithms operating on these structures
A representation-changing system should select
or construct appropriate data structures and
algorithms for each given class of problems.
problems
data structures
algorithms
Outline
• Research interests and projects
• Concept of representation
• Representation-changing system
• Future research challenges
Representation-changing system
Automated representation improvements in
the Prodigy problem-solving architecture.
Three main parts:
• Library of search modules
• Library of learning modules
• Top-level control mechanism
Architecture
Architecture
Automatic
control
Manual
control
Control center
Given a new problem:
• Select appropriate modules
• Apply them to solve the problem
• Repeat if necessary
Top-level control
Solve the problem or learn additional knowledge?
Which learner to apply?
Which past results to use?
Solve or skip the problem?
With which search module?
Which learned data to use?
Invoke the selected
learning module
Invoke the selected
search module
Wait for the next problem
Performance example
Solving a series of 50 problems, and
improving the related representation.
order of solving problems
Performance example
Solving a series of 50 problems, and
improving the related representation.
order of solving problems
Performance example
Solving a series of 500 problems, and
improving the related representation.
order of solving problems
Related publications
• Eugene Fink. Changes of problem
representation. Springer-Verlag, 2003.
• Eugene Fink. Automatic evaluation and
selection of problem solving methods.
JETAI journal, 16(2), 2004.
• Eugene Fink. Evaluation of representations.
IEEE SMC conference, under review.
Applications
• Exchange markets for complex commodities:
Automated selection of indexing structures,
depending on the type and number of orders
• Elicitation under uncertainty (Radar):
Automated selection among elicitation
algorithms and related heuristics
Outline
• Research interests and projects
• Concept of representation
• Representation-changing system
• Future research challenges
Future research challenges
• Evaluation of representations
• Automated selections among
data structures and algorithms
• Automated construction
of new data structures
• Integrated AI systems
• Applications
Evaluation of representations
• Standard methods for the evaluation and
comparison of alternative representations
• Theory of representation efficiency, which
should account for the search time, solution
quality, and percentage of solved problems
• Inherent complexity of AI problems,
complexity classes, and AI-completeness
Automated selection among
data structures and algorithms
• Combining exploration with exploitation
• Analysis of similarities among problems
and among representations
• Generation and use of small test problems
Automated construction
of new data structures
• Automated selection among
alternative data structures
• Self-adjusting data structures
• Automated construction of complex
structures from basic blocks
Integrated AI systems
• General architecture for integrating
search and learning algorithms
• Large library of standard AI algorithms
and tools for their synergetic use
The grand challenge is to develop an architecture
that integrates thousands of AI engines and problem
domains, in the same way as an operating system
integrates file-processing programs.
Applications
The automated improvement of
representations should be applicable
to most areas of computer science.