图 书 馆
最大乘积不动点质量的最坏情况界Worst-case bounds on the quality of max-product fixed-points |
|
| 课程网址: | http://videolectures.net/nips2010_vinyals_wcb/ |
| 主讲教师: | Meritxell Vinyals |
| 开课单位: | 人工智能研究所 |
| 开课时间: | 2011-03-25 |
| 课程语种: | 英语 |
| 中文简介: |  我们研究了马尔可夫随机场（MRF）的最大乘积算法的任何定点分配质量的最坏情况下的界限。我们开始证明一个与MRF结构和参数无关的界线。之后，我们展示了如何针对具有特定结构（例如二部图或网格）的MRF改善此边界。我们的结果为max产品的行为提供了有趣的见解。例如，我们证明在具有较大可变不相交循环的MRF（所有循环均可变不相交的MRF，即它们不共享任何边且每个边均互不相交的MRF）上，最大乘积提供了非常好的结果（至少是最优值的90％）。周期至少包含20个变量。 |
| 课程简介: | We study worst-case bounds on the quality of any fixed point assignment of the max-product algorithm for Markov Random Fields (MRF). We start proving a bound independent of the MRF structure and parameters. Afterwards, we show how this bound can be improved for MRFs with particular structures such as bipartite graphs or grids. Our results provide interesting insight into the behavior of max-product. For example, we prove that max-product provides very good results (at least 90% of the optimal) on MRFs with large variable-disjoint cycles (MRFs in which all cycles are variable-disjoint, namely that they do not share any edge and in which each cycle contains at least 20 variables). |
| 关 键 词: | 乘积算法; 乘积变量 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2021-04-14：zyk |
| 最后编审: | 2021-05-07：yumf |
| 阅读次数: | 63 |