| |
Many applications involve repeatedly computing the optimal, maximum a
posteriori (MAP) configuration of a graphical model as the model
changes, often slowly or incrementally over time, e.g., due to input
from a user. Small changes to the model often require updating only a
small fraction of the MAP configuration, suggesting the possibility of
performing updates faster than recomputing from scratch. In this
paper we present an algorithm for efficiently performing such updates
under arbitrary changes to the model. Our algorithm is within a
logarithmic factor of the optimal and is asymptotically never slower
than re-computing from-scratch: if a modification to the model
requires $m$ updates to the MAP configuration of $n$ random variables,
then our algorithm requires O(mlog(n/m)) time; re-computing from
scratch requires O(n) time. We evaluate the practical effectiveness
of our algorithm by considering two problems in genomic signal
processing, CpG region segmentation and protein sidechain packing,
where a MAP configuration must be repeatedly updated. Our results
show significant speedups over recomputing from scratch.
|