Name
Abstract | ||
|---|---|---|
Suppose that we are given n mutually exclusive hypotheses, m mutually exclusive possible observations, the conditional probabilities for each of these observations under each hypothesis, and a method to probe each hypothesis whether it is the true one. We consider the problem of efficient searching for the true (target) hypothesis given a particular observation. Our objective is to minimize the expected search cost for a large number of instances, and for the worst-case distribution of targets. More precisely, we wish to rank the hypotheses so that probing them in the chosen order is optimal in this sense. Costs grow monotonic with the number of probes. While it is straightforward to formulate this problem as a linear program, we can solve it in polynomial time only after a certain reformulation: We introduce mn^2 the so-called rank variables and arrive at another linear program whose solution can be translated afterwards into an optimal mixed strategy of low description complexity: For each observation, at most n rankings, i.e., permutations of hypotheses, appear with positive probabilities. Dimensionality arguments yield further combinatorial bounds. Possible applications of the optimization goal are discussed. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.dam.2007.12.006 | Discrete Applied Mathematics |
Keywords | Field | DocType |
probabilistic inference model,particular observation,linear programming,ranking hypothesis,polytopes,optimal mixed strategy,n ranking,mixed strategy,linear program,possible application,probabilistic inference,dimensionality argument,exclusive hypothesis,searching,search cost,ranking,so-called rank variable,exclusive possible observation,large number,conditional probability,polynomial time | Monotonic function,Combinatorics,Conditional probability,Ranking,Permutation,Probability distribution,Linear programming,Statistical model,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
157 | 6 | Discrete Applied Mathematics |
Citations | PageRank | References |
0 | 0.34 | 15 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Damaschke | 1 | 471 | 56.99 |