...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Ranking hypotheses to minimize the search cost in probabilistic inference models
【24h】

Ranking hypotheses to minimize the search cost in probabilistic inference models

机译：对假设进行排序以最大程度地降低概率推理模型中的搜索成本

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Suppose that we are given n mutually exclusive hypotheses, in 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 11 rankings, i.e., permutations of hypotheses, appear with positive probabilities. Dimensionality arguments yield further combinatorial bounds. Possible applications of the optimization goal are discussed.
机译：假设在互斥可能的观察中，我们给了n个互斥假设，每个假设下每个观察的条件概率，以及一种探查每个假设是否为真的方法。考虑到特定的观察，我们考虑有效搜索真实（目标）假设的问题。我们的目标是将大量实例以及最坏情况下的目标分配的预期搜索成本降至最低。更准确地说，我们希望对假设进行排名，以便在这种意义上以选定的顺序进行探测是最佳的。成本随着探针数量的增加而单调增加。虽然将这个问题表达为线性程序很简单，但是只有在经过一定的重新格式化之后，我们才能在多项式时间内解决它：我们引入mn（2）所谓的秩变量，然后得出另一个线性程序，其解可以在之后进行转换。降低描述复杂度的最佳混合策略：对于每个观察，最多出现11个排名，即假设的排列，并具有正概率。维数参数产生进一步的组合边界。讨论了优化目标的可能应用。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号