Loading...
Please wait, while we are loading the content...
Probably Approximately Optimal Derivation Strategies (1991)
| Content Provider | CiteSeerX |
|---|---|
| Author | Greiner, Russell Orponen, Pekka |
| Description | 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 conditional probabilities that each requested retrieval succeeds, given that a member of this class of queries is posed. This paper describes the PAO algorithm that first 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 ffl; ffi ? 0, PAO produces a strategy whose cost is within ffl of the cost of the optimal strategy, with probability greater than 1 \Gamma ffi . This paper also shows how to obtain these strategies in time polynomial in 1=ffl, 1=ffi and the size of the inference graph, for many important classes of graphs, including all and... In Proc, KR-91 |
| File Format | |
| Language | English |
| Publisher | Morgan Kaufmann |
| Publisher Date | 1991-01-01 |
| Access Restriction | Open |
| Subject Keyword | Conditional Probability Complete Strategy Inference Graph Time Polynomial Gamma Ffi Optimal Strategy Particular Ordering Many Important Class Pao Algorithm Optimal Derivation Strategy Probability Value Training Example Many Derivation Strategy Database Retrieval |
| Content Type | Text |
| Resource Type | Article |
