Marginal MAP inference involves making MAP predictions in systems defined with latent variables or missing information. It is significantly more difficult than pure marginalization and MAP tasks, for which a large class of efficient and convergent variational algorithms, such as dual decomposition, exist. In this work, we generalize dual decomposition to a generic power sum inference task, which includes marginal MAP, along with pure marginalization and MAP, as special cases. Our method is based on a block coordinate descent algorithm on a new convex decomposition bound, that is guaranteed to converge monotonically, and can be parallelized efficiently. We demonstrate our approach on marginal MAP queries defined on real-world problems from the UAI approximate inference challenge, showing that our framework is faster and more reliable than previous methods.
Thus, most algorithms do not satisfy all the desirable properties listed in the introduction. For example, many works have developed convergent message-passing algorithms for convex free energies [e.g.,][] hazan08, hazan10 . However, by optimizing the dual they do not provide a bound until convergence, and the representation and constraints on the counting numbers do not facilitate optimizing the bound over these parameters. To optimize counting numbers, @cite_14 adopt a more restrictive free energy form requiring positive counting numbers on the entropies; but this cannot represent marginal MAP, whose free energy involves conditional entropies (equivalent to the difference between two entropy terms).
@cite_14
2103498186 1801773550 2173032108 165387623
We introduce a new technique that can reduce any higher-order Markov random field with binary labels into a first-order one that has the same minima as the original. Moreover, we combine the reduction with the fusion-move and QPBO algorithms to optimize higher-order multi-label problems. While many vision problems today are formulated as energy minimization problems, they have mostly been limited to using first-order energies, which consist of unary and pairwise clique potentials, with a few exceptions that consider triples. This is because of the lack of efficient algorithms to optimize energies with higher-order interactions. Our algorithm challenges this restriction that limits the representational power of the models, so that higher-order energies can be used to capture the rich statistics of natural scenes. To demonstrate the algorithm, we minimize a third-order energy, which allows clique potentials with up to four pixels, in an image restoration problem. The problem uses the fields of experts model, a learned spatial prior of natural images that has been used to test two belief propagation algorithms capable of optimizing higher-order energies. The results show that the algorithm exceeds the BP algorithms in both optimization performance and speed. We consider computation of the permanent of a positive (N × N) non-negative matrix, P = (Pji|i, j = 1, ..., N), or equivalently the problem of weighted counting of the perfect matchings over the complete bipartite graph KN, N. The problem is known to be of likely exponential complexity. Stated as the partition function Z of a graphical model, the problem allows for exact loop calculus representation (Chertkov M and Chernyak V 2006 Phys. Rev. E 72 065102) in terms of an interior minimum of the Bethe free energy functional over non-integer doubly stochastic matrix of marginal beliefs, β = (βji|i, j = 1, ..., N), also correspondent to a fixed point of the iterative message-passing algorithm of the belief propagation (BP) type. Our main result is an explicit expression of the exact partition function (permanent) in terms of the matrix of BP marginals, β, as Z = Perm(P) = ZBP Perm(βji(1 − βji)) ∏i, j(1 − βji), where ZBP is the BP expression for the permanent stated explicitly in terms of β. We give two derivations of the formula, a direct one based on the Bethe free energy and an alternative one combining the Ihara graph-ζ function and the loop calculus approaches. Assuming that the matrix β of the BP marginals is calculated, we provide two lower bounds and one upper bound to estimate the multiplicative term. Two complementary lower bounds are based on the Gurvits–van der Waerden theorem and on a relation between the modified permanent and determinant, respectively. We study an energy conservation problem where a variable-speed processor is equipped with a sleep state. Executing jobs at high speeds and then setting the processor asleep is an approach that can lead to further energy savings compared to standard dynamic speed scaling. We consider classical deadline-based scheduling, i.e. each job is specified by a release time, a deadline and a processing volume. For general convex power functions, [12] devised an offline 2-approximation algorithm. Roughly speaking, the algorithm schedules jobs at a critical speed Scrit that yields the smallest energy consumption while jobs are processed. For power functions P(s) = sα + γ, where s is the processor speed, [11] gave an (αα + 2)-competitive online algorithm. We investigate the offline setting of speed scaling with a sleep state. First we prove NP-hardness of the optimization problem. Additionally, we develop lower bounds, for general convex power functions: No algorithm that constructs Scrit-schedules, which execute jobs at speeds of at least scrit, can achieve an approximation factor smaller than 2. Furthermore, no algorithm that minimizes the energy expended for processing jobs can attain an approximation ratio smaller than 2. We then present an algorithmic framework for designing good approximation algorithms. For general convex power functions, we derive an approximation factor of 4 3. For power functions P(s) = βsα + γ, we obtain an approximation of 137 117 < 1.171. We finally show that our framework yields the best approximation guarantees for the class of Scrit-schedules. For general convex power functions, we give another 2-approximation algorithm. For functions P(s) = βsα + γ, we present tight upper and lower bounds on the best possible approximation factor. The ratio is exactly eW−1(−e−1−1 e) (eW−1(−e−1−1 e) + 1) < 1.211, where W--1 is the lower branch of the Lambert W function. We propose a general dual-fitting technique for analyzing online scheduling algorithms in the unrelated machines setting where the objective function involves weighted flow-time, and we allow the machines of the on-line algorithm to have (1 + e)-extra speed than the offline optimum (the so-called speed augmentation model). Typically, such algorithms are analyzed using non-trivial potential functions which yield little insight into the proof technique. We propose that one can often analyze such algorithms by looking at the dual (or Lagrangian dual) of the linear (or convex) program for the corresponding scheduling problem, and finding a feasible dual solution as the on-line algorithm proceeds. As representative cases, we get the following results: • For the problem of minimizing weighted flow-time, we give an O (1 e)-competitive greedy algorithm. This is an improvement by a factor of 1 e on the competitive ratio of the greedy algorithm of Chadha-Garg-Kumar-Muralidhara. • For the problem of minimizing weighted lk norm of flow-time, we show that a greedy algorithm gives an O (1 e)-competitive ratio. This marginally improves the result of Im and Moseley. • For the problem of minimizing weighted flow-time plus energy, and when the energy function f(s) is equal to sγ, γ > 1, we show that a natural greedy algorithm is O(γ2)-competitive. Prior to our work, such a result was known for the related machines setting only (Gupta-Krishnaswamy-Pruhs).