Name
Abstract | ||
|---|---|---|
We consider an optimization problem in probabilistic inference: Given n hypotheses Hj, m possible observations Ok, their conditional probabilities pkj, and a particular Ok, select a possibly small subset of hypotheses excluding the true target only with some error probability ε. After specifying the optimization goal we show that this problem can be solved through a linear program in mn variables that indicate the probabilities to discard a hypothesis given an observation. Moreover, we can compute optimal strategies where only O(m+n) of these variables get fractional values. The manageable size of the linear programs and the mostly deterministic shape of optimal strategies makes the method practicable. We interpret the dual variables as worst-case distributions of hypotheses, and we point out some counterintuitive nonmonotonic behaviour of the variables as a function of the error bound ε. One of the open problems is the existence of a purely combinatorial algorithm that is faster than generic linear programming. |
Year | Venue | Keywords |
|---|---|---|
2006 | Journal of Machine Learning Research | linear programs,open problem,error probability,cycle-free graphs,particular ok,generic linear programming,optimization goal,optimal strategy,hypotheses selection,n hypotheses hj,conditional probabilities pkj,linear program,net- work flows,probabilistic inference models,linear progr amming,optimization problem,probabilistic inference,conditional probability,chemical shifts,natural sciences,automatic control,flow,control engineering,network flows,linear programming,theoretical computer science,computer and information science,computer science |
Field | DocType | Volume |
Flow network,Probabilistic inference,Counterintuitive,Conditional probability,Automatic control,Linear programming,Artificial intelligence,Optimization problem,Mathematics,Machine learning,Information and Computer Science | Journal | 7, |
ISSN | Citations | PageRank |
1532-4435 | 2 | 0.39 |
References | Authors | |
3 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anders Bergkvist | 1 | 9 | 0.91 |
| Peter Damaschke | 2 | 471 | 56.99 |
| Marcel Lüthi | 3 | 131 | 11.01 |