共查询到20条相似文献,搜索用时 156 毫秒
1.
2.
3.
信息传播算法求解可满足问题时有惊人的效果,难解区域变窄.然而,因子图带有环的实例,信息传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,对WP算法的收敛性研究是其他信息传播算法收敛性研究的重要基础.在WP算法中,将警示信息的取值从{0,1}松弛为[0,1],利用压缩函数的性质,给出了WP算法收敛的一个充分条件.选取了两组不同规模的随机3-SAT实例进行实验模拟,结果表明:当子句与变元的比值α<1.8时,该判定条件有效. 相似文献
4.
5.
6.
为解决目前网络最大流问题求解效率低、数据溢出等问题,设计求解网络最大流问题的信念传播算法.根据网络最大流问题的特性,使最大流问题的线性规划方程与信念传播算法传递方程结合,得到描述函数,将带权随机有向图映射为对应的因子图模型;在此模型基础上,利用信念传播算法的信息迭代方程进行特征值收敛计算,提高寻优效率.选取若干随机有向图进行数值实验,实验结果表明,该算法在寻优速度上优于同类算法,验证了其可行性及有效性. 相似文献
7.
由于社会网络的日益复杂,具有线性时间复杂度的标签传播算法越来越被广泛的运用,然而在标签传播过程中存在随机性,致使社区划分不稳定.因此,对节点标签初始化、节点更新顺序和节点标签传播选择过程这三个方面改进,提出一种稳定性较高的标签传播算法.该方法引入LeaderRank算法计算节点影响力,在此基础上选取关键节点并为这些关键节点赋予标签,节点更新顺序依据于节点影响力由高到低更新,在标签传播过程中考虑节点之间的传播能力.采用真实网络数据进行实验,和传统算法相比,论文算法在相关质量指标上均有优势. 相似文献
8.
基于信度分配的并行集成CMAC及其在建模中的应用 总被引:1,自引:0,他引:1
Albus CMAC(cerebella model articulation controller) 神经网络是一种模拟人类小脑学习结构的小脑模型关节控制器, 它具有很强的记忆与输出泛化能力, 但对于在线学习来说, Albus CMAC仍难满足快速性的要求. 本文在常规CMAC神经网络的基础上, 针对其在学习精度与存储容量之间的矛盾, 引入信度分配概念, 提出了一种基于信度分配的并行集成CMAC. 它将大规模网络切割为多个子网络分别训练后再组合, 大大地提高了计算效率. 通过对复杂非线性函数建模的仿真研究表明, 该方案提高了系统建模的泛化能力和算法的收敛速度. 文章最后讨论了学习常数和泛化参数对该神经网络在线学习效果的影响. 相似文献
9.
资源调度中的资源信度模型和调度算法 总被引:10,自引:0,他引:10
提出了用于描述资源动态性和可用性的一种资源信度模型,在该模型下每个资源是一个信度实体.资源信度是对资源完成作业能力的一个综合评价,资源信度值越高,它越可能在较短的时间内完成交给它的作业.在此基础上提出了一种基于资源信度模型的资源调度算法.通过GridSim工具包与FIFO算法和Libra调度算法进行了模拟对比试验,试验结果表明,该算法是有效的. 相似文献
10.
11.
Efficient Belief Propagation for Early Vision 总被引:8,自引:0,他引:8
Pedro F. Felzenszwalb Daniel P. Huttenlocher 《International Journal of Computer Vision》2006,70(1):41-54
Markov random field models provide a robust and unified framework for early vision problems such as stereo and image restoration.
Inference algorithms based on graph cuts and belief propagation have been found to yield accurate results, but despite recent
advances are often too slow for practical use. In this paper we present some algorithmic techniques that substantially improve
the running time of the loopy belief propagation approach. One of the techniques reduces the complexity of the inference algorithm
to be linear rather than quadratic in the number of possible labels for each pixel, which is important for problems such as
image restoration that have a large label set. Another technique speeds up and reduces the memory requirements of belief propagation
on grid graphs. A third technique is a multi-grid method that makes it possible to obtain good results with a small fixed
number of message passing iterations, independent of the size of the input images. Taken together these techniques speed up
the standard algorithm by several orders of magnitude. In practice we obtain results that are as accurate as those of other
global methods (e.g., using the Middlebury stereo benchmark) while being nearly as fast as purely local methods. 相似文献
12.
13.
In this article, we study the belief propagation algorithms for solving the multiple probable configurations (MPC) problem over graphical models. Based on the loopy max-product methodology, we first develop an iterative belief propagation mechanism (IBPM), which aims to find the most probable configurations facing with the existence of multiple solutions. In applications ranging from low-density parity-check codes to combinatorial optimization one would like to find not just the best configurations but rather than the summary of all possible explanations. Not only can this problem be solved by our proposed loopy message-passing algorithm (LMPA), we also prove that, for tree factor graph models, this LMPA guarantees fast convergence. Moveover, we subsequently present a low-complexity approach to simplifying the message integration operation throughout the whole belief propagation circulation. Simulations built on various settings demonstrate that both IBPM and LMPA can accurately and rapidly approximate the MPC in acyclic graph with hundreds of variables. 相似文献
14.
基于置信传播算法的低密度校验码量化译码设计 总被引:2,自引:0,他引:2
介绍了二元输入连续输出无记忆AWGN信道下低密度校验 (LDPC)码的置信传播译码算法及其密度进化特性 .根据密度进化规律 ,分析了不同消息空间中的量化译码问题 .得出结论如下 :对于概率和概率差消息 ,只有高阶均匀量化才能获得满意的译码性能 ;似然比消息的适当对数量化可等价于对数似然比消息的均匀量化 ;对数似然比消息易于实现相对信道输入± 1的无偏对称量化 ,并有效利用消息的统计特性 .由非均匀量化在大消息区域分配的量化电平可以有效地促进算法收敛 .仿真结果表明 ,低阶非均匀量化优于均匀量化 相似文献
15.
Stereo Matching with Color-Weighted Correlation, Hierarchical Belief Propagation, and Occlusion Handling 总被引:1,自引:0,他引:1
Qingxiong Yang Liang Wang Ruigang Yang Stewenius H. Nister D. 《IEEE transactions on pattern analysis and machine intelligence》2009,31(3):492-504
In this paper, we formulate a stereo matching algorithm with careful handling of disparity, discontinuity, and occlusion. The algorithm works with a global matching stereo model based on an energy-minimization framework. The global energy contains two terms, the data term and the smoothness term. The data term is first approximated by a color-weighted correlation, then refined in occluded and low-texture areas in a repeated application of a hierarchical loopy belief propagation algorithm. The experimental results are evaluated on the Middlebury data sets, showing that our algorithm is the top performer among all the algorithms listed there. 相似文献
16.
基于信任度传播的体视算法 总被引:1,自引:0,他引:1
针对信任度传播算法计算量大及误匹配率高的问题,提出一种高效的计算稠密视差图的全局优化算法。首先,根据像素匹配代价的特点、视差不连续亮度变化的特征,定义具有适应性的数据约束和平滑约束,并对平滑约束进行分层调节后执行消息的传输。其次,讨论消息传输迭代过程中的冗余计算问题,通过检测消息的收敛性减少运行时间。最后,分析信任度传播算法中的误匹配问题,通过匹配的对称性检测遮挡,并提出重建数据项后,利用贪婪迭代法优化所得视差图,将图像中可靠像素的视差向不可靠像素扩散。实验结果表明,该算法能以较快的速度计算出更理想的视差图。 相似文献
17.
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. 相似文献
18.
为了提高立体匹配效率和克服处理区域的视差跳跃,提出了一种基于像元集的置信传递立体匹配方法。该方法首先以像素为基元,利用层次置信传递算法得到较为准确的初始视差;然后依次根据颜色和初始视差对参考图像进行分割,再利用分裂合并策略对分割后的像元集进行平面拟合,以消除颜色分割错误对匹配造成的影响;最后在拟合后的像元集空间,利用标准置信传递优化算法得到最终解。采用国际标准图像进行测试的实验结果表明,该方法的匹配效率和精度优于同类方法。 相似文献
19.
A novel algorithm based on the window construction method using local edge detection is presented. Firstly, in order to construct the adaptive window, a virtual closed edge is formed around each pixel via second order differential operator. Secondly, a novel rule called Dissimilar Intensity Support (DIS) technique is proposed. This rule is used to distinguish support pixels with dissimilar intensity from those with similar intensity for each centered pixel. So that the performance of window-based cost aggregation computation is improved. Thirdly, belief propagation (BP) optimization algorithm is used to obtain the disparity. The experimental results based on Middlebury stereo benchmark show that the proposed algorithm has good performances. 相似文献
20.
针对固定参数的点对马尔可夫随机场(Pairwise MRF)模型不能充分描述图像丰富的统计特征的问题,在研究 Pairwise MRF 模型的基础上,提出一种自适应分割算法.该算法首先建立一种空间自适应的局部区域 MRF 分割模型,并对局部区域的先验知识进行自适应估计;然后通过局部收敛的循环置信度传播(LBP)算法最大化自适应 MRF 模型的全局后验概率.实验结果表明所提出算法具有较好的分割结果. 相似文献