共查询到17条相似文献,搜索用时 203 毫秒
1.
2.
收敛性是评价信息传播算法性能的重要指标,信息传播算法求解可满足性问题时,命题公式的结构特征影响算法的收敛性,具有复杂结构的命题公式,信息传播算法不总收敛。为了系统地对此现象给予理论解释,借助于结构熵的方法和技术,提出命题公式的结构熵模型及其度量方法,计算随机可满足性实例的结构熵。警示传播算法(WP)作为信息传播算法的基本模型,分析WP算法的收敛性对于研究其他信息传播算法的收敛性具有重要意义,分析了WP算法收敛性与结构熵之间的关系,给出WP算法收敛的判定条件。通过实验分析,该方法有效可行。 相似文献
3.
4.
信息传播算法求解随机3-SAT问题时非常有效,能使难解区域变窄.然而,对于因子图带有环的实例,信息传播算法并不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.警示传播(Warning Propagation,WP)算法是一种基础的信息传播算法,对WP算法的收敛性研究是其它信息传播算法收敛性研究的重要基础.将一个3-SAT问题转换为具有规则结构的(3,4)-SAT问题,(3,4)-SAT问题是NP-完全的.基于(3,4)-SAT问题的规则结构性质,分析WP算法的收敛性.选取了3组不同规模的实例进行实验模拟,结果表明:在这种规则结构的可满足性实例集上,WP算法的收敛性有较大提高. 相似文献
5.
信息传播算法在求解随机kSAT问题时有惊人的效果,难解区域变窄.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,为有效分析WP算法在随机kCNF公式上的收敛性,给出了随机kCNF公式因子图上圈存在的相变点.在随机kCNF公式产生模型G(n,k,p)中,取k=3,p=d/n2,因子图中圈存在的相变点为p=1/8n2.当d<1/8时,因子图中开始出现圈,且每个连通分支至多有一个圈,因子图中含圈的连通分支的数目以及圈的长度均与n无关.因此,因子图是由森林和一些含有唯一圈的连通分支构成.证明了WP算法在这些实例集上高概率收敛,并且给出了算法的迭代步数为O(logn+s),其中,s为连通分支的大小. 相似文献
6.
7.
针对以大数据为中心的信息开放共享平台,如何从嵌入大规模噪声结构的网络中解码出网络的真实结构,进一步在挖掘关联信息的过程中得到较为准确的挖掘结果的问题,提出基于结构熵的聚类方法实现对图中节点关联程度的划分.提出了计算二维结构信息的求解算法和基于熵减原则的模块划分算法,对图结构中节点划分得到对应的模块;利用K维结构信息算法... 相似文献
8.
9.
信息传播算法求解可满足问题时有惊人的效果,难解区域变窄.然而,因子图带有环的实例,信息传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,对WP算法的收敛性研究是其他信息传播算法收敛性研究的重要基础.在WP算法中,将警示信息的取值从{0,1}松弛为[0,1],利用压缩函数的性质,给出了WP算法收敛的一个充分条件.选取了两组不同规模的随机3-SAT实例进行实验模拟,结果表明:当子句与变元的比值α<1.8时,该判定条件有效. 相似文献
10.
基于警示传播与DPLL算法的启发式极性决策算法 总被引:1,自引:0,他引:1
警示传播(WP)算法是信息传播算法的重要基础,WP算法的本质是因子图上警示信息的迭代过程,在算法收敛时得到一组稳定的警示信息,并利用局部腔域得到公式变元的部分赋值。分析了警示传播算法的基本原理,给出了算法的改进。RB实例集上的实验证明,改进后的算法比原算法具有迭代次数和运行时间,提高了收敛速度。然而,在RB模型产生的大部分实例集上,警示传播算法不收敛,因而不能有效求解公式。警示传播算法与DPLL算法的组合使用使回溯计算次数大大降低,从而有效地弥补了WP算法的不足。通过在RI3实例集上的测试实验表明,该方法是有效的。 相似文献
11.
基于云模型和BP神经网络的入侵检测 总被引:1,自引:0,他引:1
云模型是进行定性定量转换的有效工具,正态云模型通过期望、熵和超熵构成特定结构发生器,这种特定结构使得正态云模型更具有普遍适用性,更简单、直接地完成了定性与定量之间的相互转换过程.结合 BP 网络局部精确搜索的特性,提出一种基于云模型与 BP 网络的入侵检测方法,将云模型和 BP算法有机结合.通过 KDD99 CUP 数... 相似文献
12.
13.
Correctness of belief propagation in Gaussian graphical models of arbitrary topology 总被引:1,自引:0,他引:1
Graphical models, such as Bayesian networks and Markov random fields, represent statistical dependencies of variables by a graph. Local "belief propagation" rules of the sort proposed by Pearl (1988) are guaranteed to converge to the correct posterior probabilities in singly connected graphs. Recently, good performance has been obtained by using these same rules on graphs with loops, a method we refer to as loopy belief propagation. Perhaps the most dramatic instance is the near Shannon-limit performance of "Turbo codes," whose decoding algorithm is equivalent to loopy propagation. Except for the case of graphs with a single loop, there has been little theoretical understanding of loopy propagation. Here we analyze belief propagation in networks with arbitrary topologies when the nodes in the graph describe jointly gaussian random variables. We give an analytical formula relating the true posterior probabilities with those calculated using loopy propagation. We give sufficient conditions for convergence and show that when belief propagation converges, it gives the correct posterior means for all graph topologies, not just networks with a single loop. These results motivate using the powerful belief propagation algorithm in a broader class of networks and help clarify the empirical performance results. 相似文献
14.
针对标准BP算法收敛速度慢的缺点,分析了其产生的主要原因,提出了一种改进BP算法。在传统BP算法基础上通过对其激励函数增加陡度因子并在误差反传权值修正时增加协调器,通过对网络灵敏度的分析将全反传式网络变成局部式反传网络,从而达到提高网络学习速率及精度的目的。改进的BP算法应用于导向钻井稳定平台系统的辨识,仿真结果表明该算法收敛速度快,精度高。 相似文献
15.
图卷积神经网络(Graph Convolutional Neural Network)能有效地提取非欧式距离数据中的特征信息。提出一种基于图卷积网络模型的无监督社区检测算法。选择图中某些节点添加人工标签来模拟在图上的信号输入,使其满足图卷积网络的传播特征的要求,通过修改后的图卷积网络传播规则将节点本身的标签传递至其相邻节点,通过对同一节点获得的不同标签进行比较后将节点归类,之后优化归类结果并输出社区划分矩阵。使用现实世界的数据集进行测试,并与一些其他社区检测算法进行对比评估。实验结果表明算法在不同类型的数据集中都能得到很好的社区划分效果。 相似文献
16.
针对传统BP神经网络的随机初始权值和阈值易导致网络学习速度慢、容易陷入局部解及运算精度低等缺陷,提出基于改进二进制萤火虫算法(IBGSO)的BP神经网络并行集成学习算法.首先构建以高斯变异函数作为概率映射函数的IBGSO,并从理论上分析算法的有效性.然后结合IBGSO与BP神经网络构建并行集成学习算法,并将算法应用于农业干旱灾害评估中.实验表明,相比传统算法,文中算法在计算速度及精度方面更优,可以提高旱情等级评估的准确性. 相似文献
17.
标签传播算法是高效且具代表性的社团检测算法,其中不包含必需调节适应的相关参数,是大型网络社团检测的首选算法。标签传播算法具有较低的时间复杂度,但其随机性较强,且在标签传播过程中存在不确定性因素,影响了社区检测的准确性和稳定性。针对上述问题,提出一种基于节点引力和鱼记忆标签存储策略的社区检测算法CDA-GM。通过融入节点信息熵的k-shell排序策略增强社区检测的准确性,利用节点间的引力更新标签,减小标签传播的随机性。在此基础上,引入鱼记忆节点标签存储策略,避免出现标签震荡,增强标签传播的稳定性。选择人工网络和真实世界网络数据集进行实验,结果表明,该算法能够显著提高社区检测质量,获得准确的社区结构,与COPRA、SLPA、DLPA和COPRAPC算法相比,其标准化互信息值平均提高0.01、0.18、0.12、0.02,社区模块度平均提高0.04、0.02、0.07、0.01。 相似文献