• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Dynamic programming, tree-width and computation on graphical models.
【24h】

Dynamic programming, tree-width and computation on graphical models.

机译：在图形模型上进行动态编程，树宽和计算。

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

摘要

Computing on graphical models is a field of diverse interest today, due to the general applicability of these models. This thesis begins by giving background on the generalized Dynamic Programming (DP) method of performing inference computations (Chapter 1). We then (in Chapter 2) demonstrate explicity equivalences between different methods of computation and the importance of a parameter called tree-width. We go on to prove a novel method of bounding the tree-width of a graph by using maximum cardinality search. This gives a lower bound on the computational complexity of a graph with respect to standard methods. This bound can be quite weak or quite good. We provide experimental results demonstrating both cases. Chapter 3 is concerned with Coarse-to-Fine Dynamic Programming (CFDP), a method which can be faster than the standard methods, but requires special conditions. We prove theorems giving the complexity of CFDP for problems that meet certain criteria. These theoretical results are borne out with applications to specific problems.
机译：由于这些模型的普遍适用性，因此在图形模型上进行计算是当今引起人们广泛关注的领域。本文首先介绍执行推理计算的通用动态编程（DP）方法（第1章）。然后，我们（在第2章中）演示了不同计算方法与称为树宽的参数的重要性之间的显式等效性。我们继续证明通过使用最大基数搜索来限制图的树宽的新颖方法。相对于标准方法，这为图形的计算复杂度提供了一个下限。此界限可能非常弱或非常好。我们提供的实验结果证明了这两种情况。第3章讨论的是粗略到精巧的动态编程（CFDP），该方法可能比标准方法快，但需要特殊条件。我们证明了定理给出了满足某些条件的问题的CFDP的复杂性。这些理论结果在具体问题上的应用得到了证实。

著录项

  • 作者

    Lucena, Brian Oliveira.;

  • 作者单位

    Brown University.;

  • 授予单位 Brown University.;
  • 学科 Statistics.; Mathematics.
  • 学位 Ph.D.
  • 年度 2002
  • 页码 130 p.
  • 总页数 130
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 统计学;数学;
  • 关键词

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号