图 书 馆
组合空间上的变分推理Variational Inference over Combinatorial Spaces |
|
| 课程网址: | http://videolectures.net/nips2010_bouchard_cote_vic/ |
| 主讲教师: | Alexandre Bouchard-Côté |
| 开课单位: | 不列颠哥伦比亚大学 |
| 开课时间: | 2010-03-25 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Since the discovery of sophisticated fully polynomial randomized algorithms for a range of #P problems (Karzanov et al., 1991; Jerrum et al., 2001; Wilson, 2004), theoretical work on approximate inference in combinatorial spaces has focused on Markov chain Monte Carlo methods. Despite their strong theoretical guarantees, the slow running time of many of these randomized algorithms and the restrictive assumptions on the potentials have hindered the applicability of these algorithms to machine learning. Because of this, in applications to combinatorial spaces simple exact models are often preferred to more complex models that require approximate inference (Siepel et al., 2004). Variational inference would appear to provide an appealing alternative, given the success of variational methods for graphical models (Wainwright et al., 2008); unfortunately, however, it is not obvious how to develop variational approximations for combinatorial objects such as matchings, partial orders, plane partitions and sequence alignments. We propose a new framework that extends variational inference to a wide range of combinatorial spaces. Our method is based on a simple assumption: the existence of a tractable measure factorization, which we show holds in many examples.Simulations on a range of matching models show that the algorithm is more general and empirically faster than a popular fully polynomial randomized algorithm. We also apply the framework to the problem of multiple alignment of protein sequences, obtaining state-of-the-art results on the BAliBASE dataset (Thompson et al., 1999). |
| 关 键 词: | 统计; 数学; 组合 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2020-06-01：wuyq |
| 阅读次数: | 44 |