基于线性规划松弛的概率图模型MAP推理方法研究

《基于线性规划松弛的概率图模型MAP推理方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、~~i-:~10699~~%TP391.4J&:~~*c~""5"2010100543~~¥T~~/11~.9l:R:Ij*'~5tP,B~*RJC$1Il1~~MAPft!ljj5!~Jf~~#,~~rr.m#~~tt*t~~tt!ltP*f(g?~tt'it~1ftEJm20171:p6YJ4B,-II'll'-..............--,.....,I......<#,U'......"wi........wi""""r"".",I""'"I...........西北工业大学博士学位论文题目:基于线性规划松弛的概率图模型MAP推理方法研究作者：张臻学科专业：计算机科学与

2、技术指导教师：张艳宁教授2017年6月4日LinearProgrammingRelaxationbasedMAPInferenceForGraphicalModelsByZhenZhangUndertheSupervisionofProfessorProf.YanningZhangADissertationSubmittedtoNorthwesternPolytechnicalUniversityInpartialfulfillmentoftherequirementForthedegreeofDoctorofComputerScienceandTechnologyXi’anP.R.C

3、hinaJune4,2017摘要摘要概率图模型是计算机视觉、模式识别、自然语言处理和生物信息等领域中极为重要的结构化数据建模处理工具，MAP推理是概率图模型中最为关键的瓶颈问题之一，也是概率图模型中的研究热点问题。由于概率图模型MAP推理通常是NP难问题，需要进行松弛求解。在众多松弛方法中，线性规划松弛通常相对其他松弛方法具有更高的精度。本文基于线性规划松弛模型，对概率图模型MAP推理中的模型和方法进行了较为深入的研究，完成的主要成果与创新工作概括如下。(1)现有高阶概率图模型线性规划松弛模型和消息传递框架中，通常存在较多的冗余约束算和冗余运算。针对这两个问题本文：a)在分析比较现有线

4、性规划松弛模型的基础上，针对高阶概率图模型提出一种新的线性规划松弛模型，并基于该模型提出一种冗余约束消除方法，能够有效消除冗余约束；b)基于提出的线性规划松弛模型提出一种新的消息传递框架，该框架通过直接更新重整参数而非消息变量减少了冗余运算。将冗余约束消除方法和消息传递框架相结合，可以提出一系列消息传递方法。在生物信息、图像分割、图像匹配等领域的实验表明，这些方法相对现有方法具有速度较快。(2)图像重建、M-最优求解、二次背包问题等实际问题中需要对作用于随机变量的全局约束条件进行建模，而传统概率图推理模型和方法难以对全局约束条件进行建模。针对这一问题，本文首先建立了一种约束下的概率图模

5、型推理模型，利用该模型可以对机器学习、计算机视觉和组合优化中很多重要的问题进行建模；其次针对该推理模型提出一种约束下的线性规划松弛模型，并利用复杂性理论和对偶优化理论分析得出了该模型在一些特定情形下的误差界。(3)针对通用软件——如CPLEX等对约束下概率图模型求解效率低，求解速度慢的问题，基于对偶分解框架和对偶优化理论提出一种扩展消息传递方法，将复杂的约束下组合优化推理问题分解为简单的消息变量更新问题和约束变量更新子问题，并对消息变量和约束变量进行交替更新，逼近原问题的最优解。在人工随机生成的数据和前景检测、图像重建、M-最优问题和二次背包问题等领域的真实数据验证了方法的有效性，实验

6、表明，所提出方法常常在精度和速度均优于传统方法和CPLEX商业求解软件。（4）特征匹配问题是计算机视觉和机器学习中极为重要的基础性问题，而传统高精度求解方法如基于凹凸松弛过程的因子化图匹配方法以及基于概率图模型的对偶分解方法等求解速度较慢。针对这一问题，提出一种新的二阶特征匹配问题对偶分解框架，I西北⼯业⼤学博⼠学位论⽂将复杂的二阶图匹配问题分解为容易求解的二部图匹配子问题和消息传递子问题，并提出一种“匈牙利-消息传递”方法，利用匈牙利算法和消息传递方法对这两个子问题进行交替优化求解，实现对二阶特征匹配问题的高精度近似求解。理论分析表明：该方法相对传统方法具有更好的时间复杂度，且在一定

7、条件下能够给出图匹配问题的精确解；实验结果表明：该方法相对目前公布的高精度求解方法具有更高的精度和更快的速度。（5）超图匹配相对二阶特征匹配方法能够对更为复杂几何结构进行建模，是计算机视觉中对复杂非刚性形变物体进行匹配的重要方法。传统方法的求解精度通常较低，利用高阶概率图模型可以对超图匹配问题进行较高精度的求解，但求解速度慢，难以满足大规模超图匹配问题的应用需求。针对这一问题，本文提出一种动态规划——二部匹配消息传递方法，将复杂的高阶匹配问题分