概率图模型的学习算法研究

论文摘要

概率图模型结合概率论和图论,用紧凑的形式描述多元统计关系,目前广泛应用于不确定性知识表示和推理。在大数据时代的今天,如何加快网络模型学习的速度,使之能够在短时间内利用海量数据学习出复杂的网络模型,对充分利用数据的价值具有重要意义。概率图模型主要有贝叶斯网络和马尔可夫网络两种,本文主要关注于贝叶斯网络的学习问题。贝叶斯网络学习分为结构学习和参数学习,其中结构学习是研究重点。贝叶斯网络的结构学习是NP难问题,因此多使用启发式算法或随机方法来降低网络模型学习复杂度。本文提出了一种基于MCMC方法对序列进行抽样的算法来学习贝叶斯网络结构。相比于在图空间中进行抽样,对序列抽样显著减小了抽样空间。为进一步提高算法效率,本文引入了一种新的序列评分函数,减少了传统评分函数的复杂计算,提高了序列的评价速度,并使用新的整数与组合之间的映射算法,取代传统的哈希算法来计算局部评分的存储位置,加快局部评分的查找过程。此外使用了贝叶斯参数估计方法来学习网络模型的参数。然后,对改进后的学习算法进行了并行化设计,以便在CUDA平台上利用GPU来加速贝叶斯网络的学习。在改进算法中,预处理阶段计算局部评分表和MCMC迭代学习阶段对给定序列中每个节点的最佳局部评分都可以利用GPU线程来并行计算,而且这两个阶段也是整个算法的核心,因此能够显著降低贝叶斯网络模型学习的时间。同时,应用新的归约算法获取节点对应的最优父节点集合,降低了对显卡内存的要求。最后,在实验阶段,本文选取了四个不同规模的贝叶斯网络对改进算法mMCL和基于CUDA GPU的PmMCL并行学习算法进行性能测试,并与经典的MCL学习算法进行比较。实验结果表明,改进算法在保证了模型学习准确性的前提下,mMCL算法在一定程度上提高了贝叶斯网络模型的学习速度,PmMCL并行学习算法显著加快了贝叶斯网络的学习效率,且具有良好的可扩展性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
•   1.1 研究背景
•   1.2 国内外研究现状
•     1.2.1 概率图模型学习算法研究现状
•     1.2.2 概率图模型学习算法并行化研究现状
•   1.3 论文研究内容
•   1.4 论文组织结构
• 第二章 贝叶斯网络和GPU并行计算概述
•   2.1 贝叶斯网络模型的表示
•     2.1.1 条件独立性与链式法则
•     2.1.2 贝叶斯网络模型表示
•   2.2 贝叶斯网络参数学习
•     2.2.1 最大似然估计
•     2.2.2 贝叶斯估计
•   2.3 贝叶斯网络结构学习
•     2.3.1 评分函数
•     2.3.2 搜索算法
•     2.3.3 序列空间
•     2.3.4 MCMC抽样算法
•   2.4 图形处理器GPU
•     2.4.1 GPU简介
•     2.4.2 GPU通用计算
•     2.4.3 GPU与 CPU
•   2.5 CUDA架构
•     2.5.1 CUDA软件体系
•     2.5.2 CUDA线程结构
•     2.5.3 CUDA存储结构
•     2.5.4 CUDA编程模型
•   2.6 本章小结
• 第三章 贝叶斯网络学习算法研究
•   3.1 贝叶斯网络结构学习关键技术
•     3.1.1 序列评分函数
•     3.1.2 k-组合映射为整数
•     3.1.3 根据整数还原k-组合
•   3.2 贝叶斯网络结构学习算法
•     3.2.1 预处理
•     3.2.2 序列评分
•     3.2.3 拓扑序列生成及Metropolis-Hastings抽样
•     3.2.4 贝叶斯网络学习算法设计与实现
•   3.3 贝叶斯网络参数学习
•     3.3.1 贝叶斯参数估计方法
•     3.3.2 贝叶斯参数估计算法流程
•   3.4 本章小结
• 第四章 贝叶斯网络学习算法并行化研究
•   4.1 并行学习算法流程
•   4.2 预处理阶段并行化
•   4.3 并行序列评分
•   4.4 局部评分归约
•   4.5 本章小结
• 第五章 实验测试与分析
•   5.1 实验目的和方法
•   5.2 实验环境
•   5.3 实验数据
•   5.4 实验结果与分析
•     5.4.1 mMCL学习算法效率
•     5.4.2 PmMCL并行学习算法效率
•     5.4.3 PmMCL并行学习算法可扩展性
•     5.4.4 参数学习准确性
•   5.5 本章小结
• 第六章 总结与展望
•   6.1 总结
•   6.2 展望
• 致谢
• 参考文献
• 作者简介

文章来源

类型: 硕士论文

作者: 孟贺

导师: 姜浩,陈宇寒

关键词: 概率图模型,贝叶斯网络,结构学习,并行计算

来源: 东南大学

年度: 2019

分类: 基础科学

专业: 数学,数学

单位: 东南大学

分类号: O157.5;O211

DOI: 10.27014/d.cnki.gdnau.2019.002147

总页数: 65

文件大小: 4088K

下载量: 90