基于团分划改进的IPS算法

发布时间：2017-06-26 14:08

  本文关键词：基于团分划改进的IPS算法，由笔耕文化传播整理发布。

【摘要】：图模型用图直观地、清晰地表达变量间的结构关系,并将复杂的大型全局问题分解为相对简单局部问题,这样不仅极大地减少推理计算时的计算量,而且也将提高推理的功效。在图模型的各种推理计算中,参数估计和模型选择是最核心的两个问题。本文将研究完全数据时的极大似然估计和不完全数据情形下的模型选择。图模型的极大似然估计一般采用迭代比例拟合(IPS)算法。由于IPS算法的稳定性和易于执行性,自从Deming and Stephan首次提出之后,陆续有许多学者从几何解释、收敛性、空间复杂度、时间复杂度等许多方面进行了深入研究和改进。然而,许多实际问题往往结构复杂、涉及的变量众多,此时IPS算法复杂度较高。本文从计算局部化的角度对IPS算法作了进一步研究。受Xu等人发表在JCGS的关于高斯图模型中利用团分划进行局部计算的启发,我们给出了在多项分布图模型中基于团分划进行局部计算的理论。由构成该理论的2个定理知,基于团分划的局部计算没有利用变量间的条件独立关系,这样即使图结构非常复杂,团分划策略仍然有效,这是前辈学者的诸多算法所不具备的优点。进一步,提出了基于团分划进行局部计算的算法,即IPSP算法。在该算法中,先将团集分划为几个非重叠和非空的块,然后在每个块中局部地、逐次地调整团边缘。找到使IPSP算法胜过IPS算法的团分划不难,但是整体最优的分划是很难确定地找到。本文采用模拟退火(SA)算法来寻找到一个近似最优分划。此外,我们还证明了n元圈图模型的最优分划为连续二等分划。由于团分划的策略没有利用图的结构和模型的条件独立关系,而Teh and Welling提出的UPS-JT算法中利用连接树进行局部计算的策略不具备此特性,因此团分划能提高UPS-JT算法中的拟合步的计算速度,进而提高UPS-JT算法的整体计算效率,本文称之为UPSP-JT算法。然后,本文模拟比较了IPS、IPSP、UPS-JT、UPSP-JT这几种算法的算法效率,我们发现使用连接树的UPS-JT算法和UPSP-JT算法优于没使用连接树的IPS算法和IPSP算法,并且IPSP算法和UPSP-JT算法运行的分别比IPS算法和UPS-JT算法更快,所以基于团分划的局部计算能有效地提高计算效率。含不完全数据的模型选择问题,传统的方法是先在备选模型下求极大似然估计,而后采用信息准则(例如BIC等)选择模型。但Jiang等人的JASA论文指出,传统的方法可能不会收敛,甚至可能选错模型,并提出了在一定条件下具有收敛性的E-MS算法。本文将利用Jiang等人提出的E-MS算法,考虑不完全数据情形下图模型的模型选择问题。但由于E-MS其嵌套计算的特性,计算量随变量个数的增加迅速的增大,因而本文在最大化Q函数中将采用IPSP算法提高计算速度,同时进行了模拟研究。本文结构安排如下。第一章中,简要介绍了研究背景和IPS算法发展的历史和现状,以及本文的组织结构安排。第二章中,简要介绍了一些预备知识,即图模型的一些定义、概念和记号。第三章中,首先简介了属性数据的列联表和经典的IPS算法。其次给出了基于团分划进行局部计算的理论结果和算法(IPSP算法),以及利用模拟退火算法求团集的近似最优分划中进行MH抽样的算法(MHDP算法),并证明了图模型的一种基础结构n元圈的最优分划为连续二等分划。然后利用团分划策略改进了UPS-JT算法,并通过模拟实验比较了IPS、IPSP、UPS-JT和UPSP-JT这四种算法的计算效率。第四章中,简介了不完全数据情形下模型选择的较新理论成果,即E-MS算法,并分析了其复杂度,同时还进行了不完全数据情形下图模型的模型选择的模拟研究。第五章中,给出了全文总结,并且展望了在贝叶斯估计中,IPS算法基于局部计算策略的改进。
【关键词】：图模型 IPS算法 局部计算 团分划 E-MS算法
【学位授予单位】：长春工业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O212.1;F224
【目录】：

• 摘要3-5
• Abstract5-8
• 第一章 绪论8-12
• 1.1 研究背景8
• 1.2 图模型的分类及研究方向8-9
• 1.3 IPS算法发展的历史和现状9-10
• 1.4 本文的一些工作10
• 1.5 文章的组织结构10-12
• 第二章 预备知识及记号12-15
• 2.1 图的相关概念及图分解12-13
• 2.2 马尔科夫性及图模型13-15
• 第三章 基于团分划改进IPS算法15-26
• 3.1 多项分布图模型及IPS算法简介15-17
• 3.1.1 列联表15-16
• 3.1.2 极大似然估计的IPS算法16-17
• 3.2 基于团分划改进的IPS算法17-20
• 3.2.1 基于团分划的局部计算的理论17-18
• 3.2.2 基于团分划的IPSP算法18-20
• 3.3 团集的近似最优分划20-22
• 3.4 n元圈图模型的最优分划22-23
• 3.5 基于团分划改进UPS-JT算法及模拟比较23-26
• 3.5.1 UPS-JT算法简介及基于团分划的改进23-24
• 3.5.2 算法效率的模拟比较24-26
• 第四章E-MS算法在不完全数据图模型选择中的模拟研究26-29
• 4.1 E-MS算法及复杂度分析26-27
• 4.2 模拟研究27-29
• 第五章 结论29-31
• 致谢31-32
• 参考文献32-35
• 作者简介35
• 攻读硕士学位期间研究成果35

【相似文献】

中国硕士学位论文全文数据库 前1条

1 孙聚波;基于团分划改进的IPS算法[D];长春工业大学;2016年

  本文关键词：基于团分划改进的IPS算法，，由笔耕文化传播整理发布。

本文编号：486397