Understanding the role of noise in stochastic local search: analysis and experiments

DOI10.1016/j.artint.2007.09.010zbMath1183.68582MaRDI QIDQ2389642

Ole J. Mengshoel

Publication date: 17 July 2009

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2007.09.010

zbMATH Keywords

noise; Bayesian networks; convexity; polynomial approximation; rational functions; probabilistic reasoning; stochastic local search; Markov chain models; most probable explanation; expected hitting times; systematic experiments; noise response curves

Mathematics Subject Classification ID

68T37: Reasoning under uncertainty in the context of artificial intelligence

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

Understanding the scalability of Bayesian network inference using clique tree growth curves, Portfolios in stochastic local search: efficiently computing most probable explanations in Bayesian networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some nonlinear parameters of PP intervals of pulse main peaks
• Approximating MAPs for belief networks is NP-hard and other theorems
• Finding MAPs for belief networks is NP-hard
• Local search algorithms for SAT: an empirical evaluation
• Towards a characterisation of the behaviour of stochastic local search algorithms for SAT
• Portfolios in stochastic local search: efficiently computing most probable explanations in Bayesian networks
• Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering
• The computational complexity of probabilistic inference using Bayesian belief networks
• On the hardness of approximate reasoning
• Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
• A general scheme for automatic generation of search heuristics from specification \(dependencies^{*}\)
• Local search characteristics of incomplete SAT procedures