Probably Approximately Optimal Derivation Strategies
Full Text:
pao_kr91.pdf 
An inference graph can have many 'derivation strategies', each a particular ordering of the steps involved in reducing a given query to a sequence of database retrievals. An 'optimal strategy' for a given distribution of queries is a complete strategy whose'expected cost' is minimal, where the expected cost depends on the conditionalprobabilities that each requested retrieval succeeds, given that a member ofthis class of queries is posed. This paper describes the PAO algorithm thatfirst uses a set of training examples to approximate these probability values,and then uses these estimates to produce a 'probably approximately optimal' strategy - i.e., given any ε, δ > 0, PAO produces a strategy whose cost is
within ε of the
cost of the optimal strategy, with probability greater than 1- δ.
This paper also shows how to obtain these strategies in time polynomial in
1/ε, 1/δ and the size of the inference graph, for many
important classes of graphs, including all and-or trees.
Citation
R. Greiner,
P. Orponen.
"Probably Approximately Optimal Derivation Strategies".
Knowledge Representation and Reasoning (KR), Boston, April 1991.
| Keywords: |
PAO, efficient search, PAC learning |
| Category: |
In Conference |
BibTeX
@incollection{Greiner+Orponen:KR91,
author = {Russ Greiner and Pekka Orponen},
title = {Probably Approximately Optimal Derivation Strategies},
booktitle = {Knowledge Representation and Reasoning (KR)},
year = 1991,
}Last Updated: August 13, 2007
Submitted by Russ Greiner 
