没有合适的资源?快使用搜索试试~ 我知道了~
基于双尺度约束模型的BN结构自适应学习算法.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 53 浏览量
2023-02-23
20:19:40
上传
评论
收藏 673KB DOCX 举报
温馨提示
试读
26页
基于双尺度约束模型的BN结构自适应学习算法.docx
资源推荐
资源详情
资源评论
贝叶斯网络(Bayesian network, BN)理论为不确定性知识的表示, 节点间复杂关系的表
达和信息融合推理提供了有效的模型框架
[1-3]
. 然而, 与其他图形化模型学习方法类似, BN
也存在研究对象节点增加导致候选结构数量呈指数级增长的问题. 因此, 从大规模候选结构
集合中快速, 准确地获得一个与数据样本匹配程度最优的结构模型是 BN 结构学习亟待解
决的问题之一.
研究人员尝试利用条件独立性(Conditional independence, CI)测试度量节点间的依赖关
系, 然后构造满足这些依赖关系的模型结构
[4-6]
. 但该类型学习方法运算次数一般为节点个
数的指数次幂, 当面对节点数量较多的复杂网络时, CI 测试效率较低. 与此同时, 研究人员
将模型先验信息作为约束条件, 并与结构评分函数和搜索算法组合, 共同完成 BN 结构学习
[7-10]
. 但该类型方法在模型先验信息不准确或发生错误的情况下, 将导致结构学习结果精度
低或陷入局部最优. 为此, 文献[11]通过构建不确定先验信息的评分函数并设计先验搜索算
子, 提高对错误先验信息的适应能力. 但该方法并不能完全消除错误先验信息对 BN 结构学
习产生的负面影响. 此外, 研究人员将节点间依赖关系检验与结构优化学习方法相结合, 进
行无先验信息情况下的 BN 结构学习
[12-13]
. 在该思路下, 文献[14]提出了一种混合式 BN 结
构学习方法, 该方法通过计算互信息量(Mutual information, MI)构造基于支撑树权重矩阵的
节点序适应度函数, 利用改进遗传算法(Genetic algorithm, GA)获得节点排序, 最后将节点排
序作为 K2 算法的输入进行结构学习; Wong 等和 Ji 等分别将低阶 CI 测试引入进化算法和
蚁群优化算法, 利用 CI 测试辨识部分节点对的独立关系以缩小结构搜索空间, 在此基础上
利用评分函数和启发式搜索以获得 BN 结构
[15-16]
; Li 等则提出 I-GREEDY-E 算法
[17]
, 该算法
首先在空图上计算节点间的 MI 以确定无向边, 然后利用 CI 测试确定边的指向, 最后在等
价类模型空间中利用贪婪搜索算法获得 BN 结构. 上述学习方法在无先验信息的情况下实
现了对结构搜索空间的约束, 并在约束空间内利用搜索方法获得了模型结构, 一定程度上提
高了多节点复杂网络结构的学习效率. 然而, 在无先验信息的情况下, 以 CI 测试或 MI 检验
为约束条件构造的结构搜索空间尺度固定, 无法在结构学习过程中动态调整结构搜索空间
的规模大小, 易导致潜在最优解丢失.
针对上述问题, 提出基于双尺度约束模型的 BN 结构自适应学习算法(BN structure
adaptive learning algorithm based on dual-scale constraint model, DSC-AL). 该算法将最大互信
息(Maximum mutual information, MMI)和 CI 测试结合建立结构搜索空间的大尺度约束模型,
限制 BN 结构搜索空间的规模, 完成结构搜索空间的初始化. 借鉴 GA 迭代寻优过程完成
BN 结构学习. 在迭代寻优过程中建立小尺度约束模型完成搜索空间动态调整, 构建变异概
率的自适应调节函数, 提高 GA 全局搜索能力. 在实验仿真中, 选择了不同节点规模的标准
BN 模型和不同样本量对 DSC-AL 算法的有效性进行测试, 并通过与 Lee 等提出的基于双重
GA 编码的 BN 结构学习算法
[18]
和 Gheisari 等构建的基于粒子群优化的 BN 结构学习方法
[19]
,
以及经典的 K2 算法
[20]
进行性能对比, 验证 DSC-AL 算法的性能.
1. 问题描述
为达到大尺度约束模型完成结构搜索空间的初始化, 小尺度约束模型实现结构搜索空
间动态缩放的目的, 在观测样本驱动下, DSC-AL 算法将 MI 和 CI 测试相结合辨识节点间的
依赖或独立关系, 形成限制结构搜索空间的大尺度约束模型. 然而受 MI 和 CI 测试方法辨
识精度的影响, 可能导致结构搜索空间约束不合理, 将会出现以下两种情况, 即约束尺度过
大将最优结构排除在结构搜索空间之外, 或约束尺度较小导致结构搜索空间规模依然较大.
因此, 还需要建立小尺度约束模型完成结构搜索空间动态缩放. DSC-AL 算法框架如图 1 所
示.
图 1 DSC-AL 算法框架示意图
Fig. 1 The framework of DSC-AL algorithm
下载: 全尺寸图片 幻灯片
根据图 1 给出的算法框架, 大尺度约束模型作用于算法的初始阶段, 通过剔除不满足
约束条件的 BN 模型限制结构搜索空间, 而小尺度约束模型针对 GA 种群中的每一个个体,
在迭代寻优过程中, 通过删除不满足约束条件的连接边调整每个个体表示的 BN 结构. DSC-
AL 算法为实现结构搜索空间小尺度动态缩放, 降低 GA 结构寻优过程发生早熟收敛的概率,
需要解决以下三个关键问题:
1) 小尺度约束模型需要随 GA 学习进程不断调整, 达到动态缩放结构搜索空间的目
的;
2) GA 学习进程中若产生新个体, 需要反复检测无环性, 并使用修复算子对无效结构
进行无环修复, 这将导致算法的时间成本增加, 学习效率下降;
3) GA 学习进程需要保持种群多样性以及减少对优势基因的破坏, 以降低学习方法陷
入局部最优的可能性.
2. 双尺度约束模型
2.1 大尺度约束模型
包含 nn 个节点的 BN 可生成的结构个数如式(1)所示
[21]
:
f(n)=⎧⎩⎨1,∑i=1n(−1)i+1(ni)2i(n−i)f(n−i),n=0n>0f(n)={1,n=0∑i=1n(−1)i+1(ni)2i(n−i)f(n−i),n>0
(1)
由上式可知, BN 结构搜索空间规模随着节点个数的增加呈指数级增长. 为限制 BN 结
构搜索空间, 利用节点连接边存在性约束与节点连接边缺失性约束
[22]
构建大尺度约束模型.
1) 节点连接边存在性约束
BN 中的节点 xx 与节点 yy 之间的 MI 可以采用式(2)进行计算:
I(x;y)=∑i=1r∑j=1sp(ai,bj)log2p(ai,bj)p(ai)p(bj)I(x;y)=∑i=1r∑j=1sp(ai,bj)log2p(ai,bj)p(ai)p(bj)
(2)
式中: rr 和 ss 分别表示节点 xx 与节点 yy 的状态个数, aiai 是 xx 的第 ii 个可能状态
值, bjbj 是 yy 的第 jj 个可能状态值. 两个节点之间的 MI 越大, 两者之间的依赖性越强, 即
两个节点间可能存在一条连接边.
2) 节点连接边缺失性约束
CI 测试在给定观测样本和约束集 ZZ 的基础上, 采用卡方检验判定原假设
H0H0: I(x,y∣Z)I(x,y∣Z)是否成立. 式(3)中统计量 χ2χ2 服从自由度为
(r−1)×(s−1)×t(r−1)×(s−1)×t 的分布, 其中 tt 表示约束集 ZZ 的状态个数, 即
χ2=2∑a,b,cmabcxyZlog2mabcxyZmcZmacxZmbcyZχ2=2∑a,b,cmxyZabclog2mxyZabcmZcmxZacmyZbc
(3)
式中 mabcxyZmxyZabc 表示观测样本中满足节点 xx 与 yy 的状态值分别为 aa 和 bb,
且约束集 ZZ 的状态值为 cc 的观测样本个数. 给定显著性水平 αα (0<α<10<α<1), 当
χ2<χ2αχ2<χα2, 接受原假设, 即 I(x,y∣Z)I(x,y∣Z)成立, 这就表示在给定约束集 ZZ 的条件
下, 节点 xx 和 yy 独立. 此时, 对应的两节点之间不存在连接边.
根据节点连接边存在性约束与节点连接边缺失性约束, 主要通过以下 6 个步骤构建大
尺度约束模型:
a) 利用 MI 计算每个节点与其他节点之间的依赖程度大小;
b) 将 MI 的计算结果排序, 获取相应的 MMI, 找出与各节点依赖程度最高的相关节点.
由于 MI 的对称性, 即 I(x;y)=I(y;x)I(x;y)=I(y;x), 每个节点的 MMI 所对应的连接边是无向
的;
c) 随机给定连接边指向, 确定 BN 结构的节点顺序. 根据该节点序列, 剔除搜索空间
中不满足该约束条件的候选结构, 从而缩小结构搜索空间;
d) 根据 c)获得的节点序列建立相应的邻接矩阵, 该矩阵的行序对应节点序列. 由于节
点序列中需要满足父节点排在子节点的前面, 因此只需考虑上三角邻接矩阵. 将矩阵的上三
角部分中的所有元素设置为 1. 然后根据以下步骤中 CI 测试的结果, 修改满足条件独立的
节点对所对应的矩阵元素;
e) 考虑到高阶 CI 测试的不可靠性且较高的计算复杂度
[23]
, 采用一阶 CI 测试, 即
|Z|=1|Z|=1, 利用式(3)计算邻接矩阵中所有节点的卡方统计量, 储存每一个节点与其他节点
之间的 CI 测试结果中对应的最大 pp-值;
f) 将显著性水平 αα(初始值随机给定)作为判断条件独立性的阈值. 若最大 pp -值大于
αα, 则两节点之间无连接边存在, 因此将上三角邻接矩阵中的元素 1 修改为 0. 在此基础上
可对 c)中获得的结构搜索空间完成进一步缩放.
2.2 小尺度约束模型
根据构建大尺度约束模型的步骤 f), 发现利用 CI 测试辨识节点独立性关系的精度与其
显著性水平 αα 取值相关. 若 αα 取值过小, 易出现网络的部分连接边被永久删除, 极有可能
丢失潜在最优解; 若 αα 取值过大, 结构搜索空间规模依然巨大, 且候选结构中可能存在较
多错误连接边, 导致结构学习的效率和精度下降. 因此, 需要小尺度约束模型控制显著性水
平 αα 的更新, 实现对结构搜索空间的动态缩放.
显著性水平 αα 的更新主要依赖结构复杂度评估函数对 GA 产生的每一代新的 BN 结
构的复杂度评估. 根据评估结果产生更新后的 αnewαnew 完成结构搜索空间的进一步缩放,
更新后的结构搜索空间以及更新后的 αnewαnew 将作用于 GA 迭代搜索过程(相关内容将在
第 3 节进行介绍), 小尺度约束模型工作原理如图 2 所示.
图 2 小尺度约束模型工作原理
Fig. 2 The working principle of small-scale constraint model
下载: 全尺寸图片 幻灯片
图 2 中的结构复杂度评估函数是在 BIC 评分函数的基础上获得的. 考虑到 BIC 评分
函数是一种带惩罚函数的极大似然函数评分方法
[23]
, 评分函数中的第二项能够对 BN 结构
复杂度进行评估, 因此可利用 BIC 评分函数中的第二项对 αα 进行动态更新. BIC 评分函数
如式(4)所示, 即
scoreBIC=∑i=1n∑j=1qi∑k=1rimijklog2mijkmij∗−∑i=1nqi(ri−1)2log2mscoreBIC=∑i=1n∑j=1qi∑k=1rimijklog2mijkmij∗−∑i=1nqi(ri−1)2log2m
(4)
式中: nn 表示结构中的节点个数, qiqi 表示节点 xixi 的父节点集合的状态数, riri 表示节
点 xixi 的状态数, mijkmijk 是观测数据中满足节点 xixi 的父节点集合为第 jj 个状态且节点
xixi 为第 kk 个状态的样本个数, mij∗=∑rik=1mijkmij∗=∑k=1rimijk, mm 是观测数据样本总数.
BIC 评分的第二项是描述 BN 结构复杂度的惩罚函数, 结构复杂度越高, 相应的惩罚函数值
越大, 如式(5)所示:
penalty=∑i=1nqi(ri−1)2log2mpenalty=∑i=1nqi(ri−1)2log2m
(5)
根据小尺度约束模型的工作原理, 构建小尺度约束模型主要通过以下 3 个步骤实现:
a) 利用式(5)计算当代种群中每个个体的结构复杂度 penaltykpenaltyk;
b) 将上一步骤中计算得到的 penaltykpenaltyk 与历史最优个体的结构复杂度
penaltybestpenaltybest 比较; 若 penaltyk<penaltybestpenaltyk<penaltybest, 则选择输入口 1;
若 penaltyk>penaltybestpenaltyk>penaltybest, 则选择输入口 3; 若
penaltyk=penaltybestpenaltyk=penaltybest, 则选择输入口 2. 将更新后的 αnewαnew 作为种
群个体 CI 测试的新的显著性水平;
c) 利用更新后的显著性水平 αnewαnew 调整结构搜索空间.
需要说明的是, 步骤 b)中根据复杂度评估结果更新 αα, 即当种群个体的结构复杂度小
于历史最优个体的结构复杂度时, 需要增加该个体结构的连接边, 减少 CI 测试时满足条件
独立性关系的节点对的数量, 即提高显著性水平 αα, 因此在 αα 更新过程中选择输入口 1,
此时 αnew=α+Δααnew=α+Δα; 当种群个体的结构复杂度大于历史最优个体的结构复杂度时,
应该减少结构的连接边数量, 即降低显著性水平 αα, 因此在 αα 更新过程中选择输入口 3,
此时 αnew=α−Δααnew=α−Δα; 若种群个体和历史最优个体有相同的结构复杂度, 此时, αα
的取值保持不变, 因此在 αα 更新过程中选择输入口 2.
在 GA 迭代寻优过程中存在新个体适应度不及前代个体的情况. DSC-AL 算法通过联
赛选择算子和精英保留机制将前代最优个体直接选入下一代中进行迭代寻优, 当代种群中
的最优个体即为历史最优个体. 将当代种群中每一个个体与该最优个体的结构复杂度进行
比较, 更新显著性水平. 此外, BIC 评分函数的罚项用于复杂度评估具有节点可分解性
[8]
, 以
节点为单位将每个节点的结构复杂度用向量的方式保存. 在迭代寻优过程中通常只有少数
节点的结构产生变化, 因此每次迭代只需更新个体表示的 BN 结构中少数节点的结构复杂
度. 在动态调整显著性水平时直接利用结构复杂度向量中对应元素进行计算, 可以降低计算
复杂性.
3. 基于双尺度约束模型的 BN 结构自适应学习算法
3.1 BN 结构自适应学习过程
基于双尺度约束模型的 BN 结构自适应学习算法设计思路如下:
1) 设计种群个体的编码方案. 将节点顺序和 CI 测试的显著性水平 αα 引入种群编码.
其目的主要包含两个方面: 避免迭代寻优过程中对新个体无环性的反复检验或修复无效结
剩余25页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3577
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功