UTCS Colloquium/AI-Robert Holte/University of Alberta: "Using Machine Learning to Iteratively Improve a Search Heuristic," ACES 2.402, Friday, February 19, 2010, 11:00 a.m.

Contact Name: 
Jenna Whitney
Feb 19, 2010 11:00am - 12:00pm

There is a sign-up schedule for this event that can be found
at http://www.cs.utexas.edu/department/webeven


Type of Talk: UTCS Collo


Speaker/Affiliation: Robert Holte/University of Alberta

Date/Time: Friday, February 19, 2010, 11:00 a.m.


: ACES 2.402

Host: Bruce Porter

Talk Title: Using Machine

Learning to Iteratively Improve a Search Heuristic

Talk Abstract: <


This presentation describes a method for using machine learning to
create heuristics for search
algorithms such as IDA*. The idea is to

iteratively improve upon an initial weak heuristic H1.
The easy proble

ms that can be solved using H provide training examples for learning a new<

br />heuristic H2 that is expected to be stronger than H1. If H1 is so weak
that none of the given
instances can be solved with it a method is us

ed to create a sequence of successively more
difficult instances start

ing with ones that are guaranteed to be solvable using H1. The entire

process is then repeated using H2 in lieu of H1 to produce H3, and so on,
until a sufficiently
strong heuristic is produced. In our experimenta

l tests this method produces a heuristic that
allows IDA* to solve ran

domly generated problem instances extremely quickly with solutions very
close to optimal.

Speaker Bio:

Dr. Robert

Holte is a professor in the Computing Science Department and Vice Dean of t

Faculty of Science at the University of Alberta. He is a well-known
member of the international
machine learning research community, for

mer editor-in-chief of a leading international journal
in this field (

"Machine Learning"), and past director of the Alberta Ingenuit

y Centre for
Machine Learning (AICML). His main scientific contributio

ns are his seminal works on the
performance of very simple classificat

ion rules and a technique ("cost curves") for

ve evaluation of classifiers. In addition to machine learning he undertakes
in single-agent search (pathfinding), in particular, the u

se of automatic abstraction techniques
to speed up search.