Approximate MMAP by Marginal Search

• URL: http://arxiv.org/abs/2002.04827v1
• Date: Wed, 12 Feb 2020 07:41:13 GMT
• Title: Approximate MMAP by Marginal Search
• Authors: Alessandro Antonucci and Thomas Tiotto
• Abstract summary: We present a strategy for marginal MAP queries in graphical models. The proposed confidence measure is properly detecting instances for which the algorithm is accurate. For sufficiently high confidence levels, the algorithm gives the exact solution or an approximation whose Hamming distance from the exact one is small.
• Score: 78.50747042819503
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a heuristic strategy for marginal MAP (MMAP) queries in graphical models. The algorithm is based on a reduction of the task to a polynomial number of marginal inference computations. Given an input evidence, the marginals mass functions of the variables to be explained are computed. Marginal information gain is used to decide the variables to be explained first, and their most probable marginal states are consequently moved to the evidence. The sequential iteration of this procedure leads to a MMAP explanation and the minimum information gain obtained during the process can be regarded as a confidence measure for the explanation. Preliminary experiments show that the proposed confidence measure is properly detecting instances for which the algorithm is accurate and, for sufficiently high confidence levels, the algorithm gives the exact solution or an approximation whose Hamming distance from the exact one is small.

Related papers

• Probabilistic Inference in Reinforcement Learning Done Right [37.31057328219418]
  A popular perspective in Reinforcement learning casts the problem as probabilistic inference on a graphical model of the Markov decision process (MDP) Previous approaches to approximate this quantity can be arbitrarily poor, leading to algorithms that do not implement genuine statistical inference. We first reveal that this quantity can indeed be used to generate a policy that explores efficiently, as measured by regret.
  arXiv  Detail & Related papers  (2023-11-22T10:23:14Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  We study matrix estimation problems arising in reinforcement learning (RL) with low-rank structure. In low-rank bandits, the matrix to be recovered specifies the expected arm rewards, and for low-rank Markov Decision Processes (MDPs), it may for example characterize the transition kernel of the MDP. We show that simple spectral-based matrix estimation approaches efficiently recover the singular subspaces of the matrix and exhibit nearly-minimal entry-wise error.
  arXiv  Detail & Related papers  (2023-10-10T17:06:41Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  We consider the problem of learning the optimal policy for infinite-horizon Markov decision processes (MDPs) Some variant of Mirror Descent is proposed for convex programming problems with Lipschitz-continuous functionals. We analyze this algorithm in a general case and obtain an estimate of the convergence rate that does not accumulate errors during the operation of the method.
  arXiv  Detail & Related papers  (2021-02-27T19:28:39Z)
• Non-approximate Inference for Collective Graphical Models on Path Graphs via Discrete Difference of Convex Algorithm [19.987509826212115]
  This paper proposes a new method for MAP inference for Collective Graphical Model (CGM) on path graphs. First we show that the MAP inference problem can be formulated as a (non-linear) minimum cost flow problem. In our algorithm, important subroutines in DCA can be efficiently calculated by minimum convex cost flow algorithms.
  arXiv  Detail & Related papers  (2021-02-18T07:28:18Z)
• Optimal quantisation of probability measures using maximum mean discrepancy [10.29438865750845]
  Several researchers have proposed minimisation of maximum mean discrepancy (MMD) as a method to quantise probability measures. We consider sequential algorithms that greedily minimise MMD over a discrete candidate set. We investigate a variant that applies this technique to a mini-batch of the candidate set at each iteration.
  arXiv  Detail & Related papers  (2020-10-14T13:09:48Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Revisiting Co-Occurring Directions: Sharper Analysis and Efficient Algorithm for Sparse Matrices [23.22254890452548]
  We study the streaming model for approximate matrix multiplication (AMM) We are interested in the scenario that the algorithm can only take one pass over the data with limited memory. The state-of-the-art deterministic sketching algorithm for streaming AMM is the co-occurring directions (COD)
  arXiv  Detail & Related papers  (2020-09-05T15:35:59Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• A Robust Functional EM Algorithm for Incomplete Panel Count Data [66.07942227228014]
  We propose a functional EM algorithm to estimate the counting process mean function under a missing completely at random assumption (MCAR) The proposed algorithm wraps several popular panel count inference methods, seamlessly deals with incomplete counts and is robust to misspecification of the Poisson process assumption. We illustrate the utility of the proposed algorithm through numerical experiments and an analysis of smoking cessation data.
  arXiv  Detail & Related papers  (2020-03-02T20:04:38Z)
• Statistical Outlier Identification in Multi-robot Visual SLAM using Expectation Maximization [18.259478519717426]
  This paper introduces a novel and distributed method for detecting inter-map loop closure outliers in simultaneous localization and mapping (SLAM) The proposed algorithm does not rely on a good initialization and can handle more than two maps at a time.
  arXiv  Detail & Related papers  (2020-02-07T06:34:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.