TITLE: ``Learning Good Search Strategies''

ABSTRACT:

Many tasks, including derivation, diagnosis and planning, require searching through a network of probabilistic experiments, seeking a satisfying set of successful outcomes. A "search strategy" specifies the order in which to perform these experiments; we clearly prefer a strategy whose "expected cost" is minimal. This expected cost depends on the success probabilities of the experiments, which unfortunately are usually not known a priori. This work first describes statistical methods for estimating these probabilities, and then provides two methods that use these estimates to obtain good strategies: One returns a strategy whose expected cost is, with high probability, approximately optimal. As this process is not always tractable, we next present a more general method that efficiently hill-climbs to a strategy that is, with high probability, close to a local optimum. These techniques directly address the "utility problem" of explanation-based learning systems. We also demonstrate their generality by showing how they can be used to address other (non-search) tasks, including

• theory revision,
• the "multiple-extension" problem of non-monotonic reasoning,
• landmark selection for autonomous navigation, and
• the "tractability / completeness" problem from knowledge representation.

Everyone is welcome to attend.
Interested people can also anonymously FTP relevant material from ftp://scr.siemens.com/pub/learning/Papers/greiner/
Short (conference) papers: phc-applic.ps pao_kr91.ps useful-lms-aaai.ps
Longer (journal) papers: palo-aij.ps pao.ps useful-lms-smc.ps

Short Biography for Russell Greiner:

After receiving his PhD in Computer Science from Stanford, Russell Greiner worked at the University of Toronto (as a visiting professor) before moving to Siemens Corporate Research. He has over 60 publications, in topics including

• machine learning
  • analogical inference
  • explanation-based learning
  • formal PAC-learning
  • theory revision
  • dealing with missing information
• vision and robot navigation
• knowledge representation
  • efficient reasoning (optimal derivational strategies, caching/memoizing, finding effective abstractions)
  • diagnosis
  • plan verification
• databases
• operations research
• signal analysis
• systems and control theory.

The main foci of his current work are applying machine learning techniques to address specific knowledge representation tasks, effective theory revision, understanding "relevance", and robot navigation.

Web Accessibility