Solving M-Modes in Loopy Graphs Using Tree Decompositions
Solving M-Modes in Loopy Graphs Using Tree Decompositions
复制标题
DOI：
--
复制
发表时间：
2018-08
期刊：
影响因子：
--
通讯作者：
Cong Chen;Changhe Yuan;Ze Ye;Chao Chen
中科院分区：
文献类型：
--
作者：
Cong Chen;Changhe Yuan;Ze Ye;Chao Chen
M-Modes 是找到局部最优的图形模型的前 M 个标签的问题。最先进的 M-Modes 算法是一种启发式搜索方法，通过增量连接局部邻域中的 MAP 解决方案来查找全局模式。该搜索方法还依赖于启发式函数的指导来探索搜索空间中最有希望的部分。然而，由于一般循环图中协调模式搜索、启发式函数计算和局部MAP计算的困难，该方法仅在树或子模网格图等特殊图模型上实现和测试。本文提供了一种更通用的基于树分解的搜索方法的实现，适用于一般的循环图。树分解允许将一系列局部子图映射到一组横扫树分解的子树，从而实现模式搜索、启发式函数计算和局部 MAP 计算之间的平滑且高效的来回转换。我们使用随机数据集和真实数据集来评估树分解方法的有效性。此外，我们还展示了 M 模式在为手势识别任务进行多种不同结构化预测方面的实用价值。
M-Modes is the problem of finding the top M labelings of a graphical model that are locally optimal. The state-of-the-art M-Modes algorithm is a heuristic search method that finds global modes by incrementally concatenating MAP solutions in local neighborhoods. The search method also relies on the guidance of a heuristic function to explore the most promising parts of the search space. However, due to the difficulty of coordinating mode search, heuristic function calculation and local MAP computation in general loopy graphs, the method was only implemented and tested on special graphical models such as trees or submodular grid graphs. This paper provides a more general implementation of the search method based on tree decompositions that is applicable to general loopy graphs. A tree decomposition allows a sequence of local subgraphs to be mapped to a set of sub-trees sweeping through the tree decomposition, thus enabling a smooth and efficient transition back and forth between mode search, heuristic function calculation and local MAP calculations. We use both random and real datasets to evaluate the effectiveness of the tree-decomposition method. Furthermore, we demonstrate the practical value of M-Modes in making multiple diverse structured predictions for a gesture recognition task.