UTCS Colloquia/AI - Rob Holte/University of Alberta, "Improving Predictions of IDA's Performance by Ignoring Information", ACES 2.402

Contact Name: 
Jenna Whitney
Feb 22, 2011 11:00am - 12:00pm

There is a sign-up schedule for this event that can be found at



Type of Talk: UTCS Colloquia/AI

Speaker/Affiliation: Rob Ho

lte/University of Alberta

Talk Audience: UTCS Faculty, Grad Students

and Undergrads, and Outside Interested Parties

Date/Time: Tuesday, F

ebruary 22, 2011, 11:00 a.m.

Location: ACES 2.402

Host: Bruce P


Talk Title: Improving Predictions of IDA*''s Performance by Igno

ring Information

Talk Abstract:
In 1998 Korf and Reid launched a lin

e of research aimed at creating practical methods for predicting exactly ho

w many nodes the search algorithm IDA* would expand on an iteration with a

specific depth-bound given a particular heuristic function. Zahavi, Felner

, Burch, and Holte recently generalized the Korf and Reid work. The work

presented in this talk represents the next advance in this line of research

. Our main contribution is to identify a source of prediction error that ha

d hitherto been overlooked. We call it the "discretization effect". Our sec

ond contribution is to disprove the intuitively appealing idea, specifical

ly asserted to be true by Zahavi et al., that a "more informed" prediction
system cannot make worse predictions than a "less informed" system. The po

ssibility of this statement being false arises immediately from knowledge o

f the discretization effect, since a more informed system is likely to be

more susceptible to the discretization effect than a less informed system.

In many of our experiments, the more informed system makes poorer predicti

ons. Our final contribution is a method for counteracting the discretizatio

n effect, which we call "epsilon-truncation". One way to view "epsilon-tru

ncation is that it makes a prediction system less informed, in a carefully
chosen way, so as to improve its predictions by avoiding the discretizati

on effect. Experimental results show that epsilon-truncation substantially

improves prediction accuracy for a variety of domains and heuristics.

Speaker Bio:
Dr. Robert Holte is a professor in the Computing Science Dep

artment and Vice Dean of the Faculty of Science at the University of Albert

a. He is a well-known member of the international machine learning research
community, former editor-in-chief of a leading international journal in t

his field ("Machine Learning"), and past director of the Alberta Ingenuity
Centre for Machine Learning (AICML). His main scientific contributions are
his seminal works on the performance of very simple classification rules a

nd a technique ("cost curves") for cost-sensitive evaluation of classifiers

. In addition to machine learning he undertakes research in single-agent se

arch (pathfinding), in particular, the use of automatic abstraction techn

iques to speed up search.