Local Rules for Global MAP: When Do They Work ?
We consider the question of computing Maximum A Posteriori (MAP) assignment in an arbitrary pair-wise Markov Random Field (MRF). We present a randomized iterative algorithm based on simple local updates. The algorithm, starting with an arbitrary initial assignment, updates it in each iteration by first, picking a random node, then selecting an (appropriately chosen) random local neighborhood and optimizing over this local neighborhood. Somewhat surprisingly, we show that this algorithm finds a near optimal assignment within $2n\ln n$ iterations on average and with high probability for {\em any} $n$ node pair-wise MRF with {\em geometry} (i.e. MRF graph with polynomial growth) with the approximation error depending on (in a reasonable manner) the geometric growth rate of the graph and the average radius of the local neighborhood -- this allows for a graceful tradeoff between the complexity of the algorithm and the approximation error. Through extensive simulations, we show that our algorithm finds extremely good approximate solutions for various kinds of MRFs with geometry.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Evolving-to-Learn Reinforcement Learning Tasks with Spiking Neural Networks
Inspired by the natural nervous system, synaptic plasticity rules are applied to train spiking neural networks with local information, making them suitable for online learning on neuromorphic hardware. However, when such…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Byzantine-Robust Gossip: Insights from a Dual Approach
Distributed approaches have many computational benefits, but they are vulnerable to attacks from a subset of devices transmitting incorrect information. This paper investigates Byzantine-resilient algorithms in a decentr…
Interacting Behavior and Emerging Complexity
Can we quantify the change of complexity throughout evolutionary processes? We attempt to address this question through an empirical approach. In very general terms, we simulate two simple organisms on a computer that co…
Financial Models with Defaultable Num\'eraires
Financial models are studied where each asset may potentially lose value relative to any other. Conditioning on non-devaluation, each asset can serve as proper num\'eraire and classical valuation rules can be formulated.…
Internal Pluralism and the Limits of Pairwise Comparisons
Local pairwise comparisons are a standard tool for learning how people want decision rules to work, e.g., in participatory design or alignment. However, their use builds in two strong assumptions: that local comparisons …