贝叶斯网络结构学习总结.pdf

贝叶斯网络结构学习总结贝叶斯网络结构学习总结 一 一 贝叶斯网络贝叶斯网络结构结构学习学习的原理的原理 从数据中学习贝叶斯网络结构就是对给定的数据集 找到一个与 数据集拟合最好的网络 首先定义一个随机变量 h S 表示网络结构的不确定性 并赋予先 验概率分布 h p S 然后计算后验概率分布 h p SD 根据 Bayesian 定 理有 hhhh p SDp SDp Dp Sp D Sp D 其中 p D是一个与结构无关的正规化常数 h p D S是边界似然 于是确定网络结构的后验分布只需要为每一个可能的结构计算数据 的边界似然 在无约束多项分布 参数独立 采用 Dirichlet 先验和数 据完整的前提下 数据的边界似然正好等于每一个 i j 对的边界 似然的乘积 即 111 ii qr n ijijkijkh ijk ijijijk N p D S N 二 二 贝叶斯网络完整数据集下结构学习方法贝叶斯网络完整数据集下结构学习方法 贝叶斯网络建模一般有三种方法 1 依靠专家建模 2 从数据 中学习 3 从知识库中创建 在实际建模过程中常常综合运用这些 方法 以专家知识为主导 以数据库和知识库为辅助手段 扬长避短 发挥各自优势 来保证建模的效率和准确性 但是 在不具备专家知 识或知识库的前提下 从数据中学习贝叶斯网络模型结构的研究显得 尤为重要 常用的结构学习方法主要有两类 分别是基于依赖性测试的学习 和基于搜索评分的学习 第一类方法是基于依赖性测试的方法 它是在给定数据集 D 中评 估变量之间的条件独立性关系 构建网络结构 基于条件独立测试方 法学习效率最好 典型的算法包括三阶段分析算法 TPDA 基于依 赖性测试的方法比较直观 贴近贝叶斯网络的语义 把条件独立性测 试和网络结构的搜索分离开 不足之处是对条件独立性测试产生的误 差非常敏感 且在某些情况下条件独立性测试的次数相对于变量的数 目成指数级增长 第二类方法是基于评分搜索的方法 其原理是在所有节点的结构 空间内按照一定的搜索策略及评分准则构建贝叶斯网络结构 这种算 法虽然能够搜索到精确的网络结构 但是由于结构空间很大 从所有 可能的网络结构空间搜索最佳的贝叶斯网络结构被证明为NP hard问 题 所以一般需要使用启发式算法 代表性算法有 K2 算法等 基于 搜索评分的方法是一种统计驱动的方法 试图在准确性 稀疏性 鲁 棒性等多个因素之间找个平衡点 但由于搜索方法的先天弱点 导致 用搜索评分的方法不一定能找到最好的结构 但是应用范围很广 当观察到的数据足够充分且计算次数足够多时 基于搜索评分的 方法和基于依赖性测试的方法都可以学到 正确 的网络结构 此外 有人结合上述两种方法 提出了一些混合算法 这类算法 首先利用独立性测试降低搜索空间的复杂度 然后执行评分搜索找到 最佳网络 如稀疏候选算法 sparse candidate 及 MMHC max min hill climbing 算法等 1 基于依赖性基于依赖性测测试试结构学习方法结构学习方法 基于依赖性测试的结构学习算法将贝叶斯网络看作是编码了变量 间独立性关系的图结构 它的核心思想是 通过样本集 D 验证条件独 立性 I Xi Xj C 是否成立 若成立 则在网络 S 中节点 Xi 和 Xj 被 C 有向分割 节点 Xi 和 Xj 之间不存在边 若不成立 变量 Xi 和 Xj 是依赖的 网络中节点 Xi 和 Xj 之间存在边 然后 利用节点集之间 的条件独立性 建造一个有向无环图 以尽可能多地覆盖这些条件独 立性 常用的独立性检验的方法有 2 检验和基于互信息的检验方法 基 于依赖性测试的学习方法学习效率较高 而且能够获得全局最优解 但存在以下问题 1 判断两个节点是否独立或条件独立是困难的 变 量间条件独立性检验的次数是随着变量的个数的增加指数级增长的 2 高阶的条件独立性检验的结果不够可靠 1993 年 Sprites 等提出的SGS 算法是典型的以条件独立性测试确 定拓扑结构的算法 该算法从无向完全图出发 如果相节点间存在无 向分割集 则删除它们间的边 然后通过统计测试来确定剩余边的方 向 2002 年 Cheng 将信息论与统计测试相结合 使用相互信息代替 了条件独立性测试 经过 Drafting Thickening Thinning 三个步骤 通过计算相互信息量来确定节点间的条件独立性 从而构造出多连接 有向图模型 2 基于评分搜索的结构学习方法 基于评分搜索的结构学习方法 贝叶斯网络基于评分搜索的结构学习方法主要包括两步 模型 选择和模型优化 模型选择部分要制定模型选择准则 即评分函数 目前较常用的几个 评分函数如下 最优参数对数似然函数 CH 评分 BIC 评分等 还有 MDL minimum description length AIC Akaike information criterion 评分函数 HVL holdout validation likelihood 评分 验证数据似然 度 CVL cross validation likelihood 评分 交叉验证 模型优化就是要根据模型选择准则 即评分函数 选择出评分最 高的网络结构 也就是搜索策略问题 从所有可能的网络结构空间搜 索最佳的贝叶斯网络结构被证明为 NP hard 问题 所以一般使用启发 式搜索算法 主要有 K2 hill climbing 算法 随机重复爬山法 random restart hill climbing 禁忌搜索 tabu search 模拟退火 simulated annealing 及遗传算法 genetic algorithm 等 常用的评分函数介绍如下 常用的评分函数介绍如下 最优参数对数似然函数 结构 与相应的参数集合 组成贝叶斯网络 相对于数据 最优的贝叶斯网 应该使对数似然函数达到最大 即 maxsup ll 在概念上寻找最优的贝叶斯网络的过程可以分为两步 第一步寻找最 优结构 第二步寻找最优参数 对任一网络结构 定义 sup ll 作为网络结构的函数 l 称为优参对数似然 函数 最优结构 应该使优参对数似然函数达到最大 即 max ll 这就是最大优参似然准则 家族 CH 评分 设定 S 1 B D n i i pscore i pa s B表示网络结构 D 表示一组 变量 12n XXX 的完整实例数据 其中 11 ii qr ijijkijk i jk ijijijk N score i pa N 其中 ijk N是 D 中满足 i X k i j 的样本个数 ir ij ijk k 1 NN ir ij ijk k 1 在使用 CH 评分之前 首先需要选定参数先验分布 s Bs p B 中超参数 ijk 通常这并非易事 因为理论上我们需要对每一个可能的结构都 提供参数先验分布 然而结构数目众多 无法一一罗列 在实际中 人们往往规定一个等价样本量 和一个先验贝叶斯旺 s B 利用下式得 到 s Bs p B 的超参数 ijk s Bii P Xk j ijk BIC 评分 即贝叶斯信息准则是在大样本前提下对边缘似然函数的一种近 似 它有明确直观的意义 而且使用方便 是实际中最常用的评分函 数 log log log 2 d PPm 这就是模型结构 的 BIC 评分 记为 BIC BIC 评分的第一项是模型 的优参对数似然度 它度量的是结构 与 数据 的拟合程度 第二项是一个关于模型复杂度的罚项 若仅仅依 据优参似然度来选择模型 会选到最复杂的完全贝叶斯网络 导致过 度拟合 由于附加了一个模型复杂度的罚项 BIC 有效地避免了过度 拟合 直观上 基于 BIC 评分选择模型就是要选择既与数据拟合 又 比较简单的模型 MDL 评分 它是最短描述长度 minimum description length 的简称 这个准则 的基本思想如下 数据分析的目的是要找出蕴含在数据中的规律 然 后可以利用它们对数据进行压缩 从而降低数据的编码 描述 长度 所以 用贝叶斯网分析数据是否成功可以用数据和模型的编码总长度 来度量 AIC 评分 它是 Akaike 信息准则的简称 他假设数据 是从一个概率分布 P X 中进行独立同分布抽样而得到的 AIC 评分的出发点是要找一个贝叶 斯网 B 使得 B PX与 P X 之间的 KL 距离最短 即 B B KL P PKL P PB 在一定光滑条件下做大样本近似 可得如下 结论 即 B的结构 应该满足 AICAIC 其中 log AICPd AIC 评分与 BIC 评分都是优参对数似然度加一个罚项 因此都称为罚 项似然度 MDL 也是罚项似然度 HVL 评分 罚项的作用是防止过度拟合 还有一种防止过度拟合的方法 它的基 本思想是把数据 随机地分成训练数据 t 和验证数据 v 对于一个模 型结构 首先基于训练数据对其参数进行估计 得到一个贝叶斯网 t 然后计算验证数据 v 对数似然度 log t vtv HVLP 这就是 HVL 评分函数 CVL 评分 即交叉验证 它的基本思想是多次计算模型的 HVL 评分 而每次都按照不同方式将 划分为 t 和 v 然后计算各次所得评分的平均值 并将其作为模型 的最后评分 CVL 评分比 HVL 评分更具鲁棒性 但其计算复杂度也高 出 HVL 评分数倍 在大样本情况下 HVL 准则 CVL 准则都与 AIC 准则等价 3 典型算法介绍 典型算法介绍 三阶段算法 三阶段算法 第一阶段 Drafting 计算每对节点间的互信息 建立完整的无向图 第二阶段 Thickening 如果节点对不是 d 分割的话 把这一点对加 入到边集中 第三阶段 Thinning 检察边集中的每个点对 如果两个节点是 d 分 割的 则移走这条边 K2K2 算法 算法 K2 算法用贪婪搜索处理模型选择问题 先定义一种评价网络结构优 劣的评分函数 再从一个网络开始 根据事先确定的最大父节点数目 和节点次序 选择分值最高的节点作为该节点的父节点 K2 算法使 用后验概率作为评分函数 1 n si i p D Bscore i pa 其中 11 ii qr ijijkijk i jk ijijijk N score i pa N K2 算法伪代码 2 kX 输入 12 n XX XX 一组变量 一个变量顺序 设它与变量下标一致 变量父亲节点个数的上界 一组完整的数据 输出 一个贝叶斯网 1 12n XXX 由节点 组成的无边图 2 for j 1 to n 3 j 4 oldjj VCH X 5 while true 6 ij jji 1 iV and 9 oldnew VV 10 jii X 11 在 中加边 ij XX 12 else 13 break 14 end if 15 end while 16 end for 17 估计 的参数 18 return K2 的出发点是一个包含所有节点 但却没有边的无向图 在搜索 过程中 K2 按顺序逐个考察 中的变量 确定其父亲节点 然后添加 相应的边 对某一变量 j X 假设 K2 已经找到了它的一些父亲节点 j 如果 j V 则把 i X添加为 j X的父节点 否则停止为 j X寻找父 亲节点 H Hillill climbing climbing 算法算法 爬山法的目标是要找出评分最高的模型 它从一个初始模型出发开始 搜索 初始模型一般设为无边模型 在搜索的每一步 它首先用搜索 算子对当前模型进行局部修改 得到一系列候选模型 然后计算每个 候选模型的评分 并将最优候选模型与当前模型进行比较 若最优候 选模型的评分大 则以它为下一个模型 继续搜索 否则 就停止搜 索 并返回当前模型 搜索算子有三个 加边 减边和转边 加边和减边算子的使用有个前 提 就是不能在网络中形成有向圈 爬山法可以使用任何评分函数 不同的评分函数有不同的要求 CH 评分要求关于先验参数分布的超参数 而 HVL 及 CVL 评分则要求 把数据分成训练数据和验证数据 因此 需要处理的算法细节也有所 不同 爬山算法的伪代码如下 LearnBN HC X 0f 输入 X 一组变量 一组关 于 X 的完整数据 f 一个罚项似然度评分函数 0 一个初始贝叶 斯网络结构 输出 一个贝叶斯网络 1 0 的参数的最大似然估计 2 oldScoref 3 while true 4 null null newScore 5 for 每个对 做一次加边 减边或转边而得到的模型结构 6 的参数的最大似然估计 7 tempScoref 8 if tempScore newScore 9 newScoretempScore 10 end if 11 end for 12 if newScore oldScore 13 oldScorenewScore 14 else 15 return 16 end if 17 end while 三 三 贝叶斯网贝叶斯网缺值数据缺值数据下下的结构学习的结构学习 贝叶斯网络缺值数据下的结构学习算法主要有 SEM structure EM learning algorithm 算法 它的基本思想是 从某初始模型结构 0 和参数 0 出发开始迭代 在进行了 t 次迭代得到了 tt 后 第 t 1 次迭代由