We study the problem of maximum marginal prediction (MMP) in probabilistic graphical models, a task that occurs, for example, as the Bayes optimal decision rule under a Hamming loss. MMP is typically performed as a two-stage procedure: one estimates each variable's marginal probability and then forms a prediction from the states of maximal probability. In this work we propose a simple yet effective technique for accelerating MMP when inference is sampling-based: instead of the above two-stage procedure we directly estimate the posterior probability of each decision variable. This allows us to identify the point of time when we are sufficiently certain about any individual decision. Whenever this is the case, we dynamically prune the variables we are confident about from the underlying factor graph. Consequently, at any time only samples of variables whose decision is still uncertain need to be created. Experiments in two prototypical scenarios, multi-label classification and image inpainting, show that adaptive sampling can drastically accelerate MMP without sacrificing prediction accuracy.
82 - 90
NIPS: Neural Information Processing Systems
Lake Tahoe, NV, United States
2012-12-03 – 2012-12-06
Lampert C. Dynamic pruning of factor graphs for maximum marginal prediction. In: Vol 1. Neural Information Processing Systems; 2012:82-90.
Lampert, C. (2012). Dynamic pruning of factor graphs for maximum marginal prediction (Vol. 1, pp. 82–90). Presented at the NIPS: Neural Information Processing Systems, Lake Tahoe, NV, United States: Neural Information Processing Systems.
Lampert, Christoph. “Dynamic Pruning of Factor Graphs for Maximum Marginal Prediction,” 1:82–90. Neural Information Processing Systems, 2012.
C. Lampert, “Dynamic pruning of factor graphs for maximum marginal prediction,” presented at the NIPS: Neural Information Processing Systems, Lake Tahoe, NV, United States, 2012, vol. 1, pp. 82–90.
Lampert C. 2012. Dynamic pruning of factor graphs for maximum marginal prediction. NIPS: Neural Information Processing Systems vol. 1, 82–90.
Lampert, Christoph. Dynamic Pruning of Factor Graphs for Maximum Marginal Prediction. Vol. 1, Neural Information Processing Systems, 2012, pp. 82–90.