Exact Relaxation-Based Inference in Graphical Models (ERBI)
Final Report Abstract
The goals of the project are scalable, exact and accurate approximate solvers for extensions of discrete graphical models. These extensions include, but are not limited, to tracking and matching problems so far usually formulated and solved as integer liner programs (ILP) with off-the-shelf software like Gurobi. Due to NP-hardness of these problems the off-the-shelf ILP software does not scale well: Although it is fast for small-sized problem instances, it slows down dramatically as the problem size surpasses a certain threshold. Within this project we: • Contributed to the scalable exact optimization methods for discrete graphical models. The exact methods are important on the modeling stage, when a modeling error must be distinguished from an optimization error, and in cases when highest precision of the solutions is required, like in biological applications. To this end we extended the shrinking method (also known as CombiLP), the state-of-the-art technique for obtaining exact solutions for large-scale discrete graphical models. Our extension allows to efficiently apply the method to densely-connected and higher order discrete graphical models. • Contributed to approximate optimization methods for discrete graphical models. The goal of these methods is to obtain an accurate, but not necessarily optimal solution within a given time budget. To this end we have analyzed existing efficient dual block-coordinate ascent-based algorithms for discrete graphical models and generalized them so that they can be used for a broad class of combinatorial problems. We complemented our new dual algorithms with specifically customized primal heuristics profiting from the dual optimization. These led to accurate approximate solutions already in the first algorithm iterations. • Tested our new methods on two applications in bio-informatics. The first one is cell-tracking, where for mid- and large-scaled problem instances our solver is able to obtain good approximate solutions an order of magnitude faster than Gurobi. The second application is related to the C. elegans worm, a popular model organism in bio-informatics. The applied problem consists of matching cells between a pair of microscopic images (worm-to-worm matching) or between a microscopic image and the reference atlas of the organism (atlas-to-worm matching). For the atlas-to-worm matching we were often able to obtain exact solutions faster than the competing methods the approximate ones. For atlas-to-worm as well as for the worm-to-worm matchings our approximate technique turned out to be more accurate and an order of magnitude faster than the best of alternative methods. • Wrote a monograph on optimization techniques for discrete graphical models. The monograph is structured in a way to be useful for undergraduate and graduate students studying optimization or graphical models, as well as for experts in optimization who want to have a look into graphical models. The obtained results open a way to • a wider use of large-scale optimization-based models, in particular, for tracking and matching problems in bio-imaging. This, in its turn, allows to e.g. estimate lineage trees of organisms on later stages of their development, when the number of cells significantly grows; • estimate the costs of combinatorial problems by leveraging neural networks, based on training data. In the training loop the optimization routine has to be exectuted in each iteration, whenever the learning parameters are updated. This implies that optimization should take less than a fraction of a second. Faster optimization algorithms allow to train costs for larger problems.
Publications
- A dual ascent framework for Lagrangean decomposition of combinatorial problems. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2017
P. Swoboda, J. Kuske, and B. Savchynskyy
(See online at https://doi.org/10.1109/CVPR.2017.526) - Study of Lagrangean decomposition and dual ascent solvers for graph matching. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2017
P. Swoboda, C. Rother, H. Abu Alhaija, D. Kainmueller, and B. Savchynskyy
(See online at https://doi.org/10.1109/CVPR.2017.747) - Exact map-inference by confining combinatorial search with LP relaxation. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018
Stefan Haller, Paul Swoboda, and Bogdan Savchynskyy
(See online at https://doi.org/10.48550/arXiv.2004.06370) - Discrete graphical models — an optimization perspective. Foundations and Trends in Computer Graphics and Vision, 11(3-4):160–429, 2019
Bogdan Savchynskyy
(See online at https://doi.org/10.1561/0600000084) - A primal-dual solver for large-scale tracking-by-assignment. In Proceedings of the Conference on Artifical Intelligence and Statistics, 2020
Stefan Haller, Mangal Prakash, Lisa Hutschenreiter, Tobias Pietzsch, Carsten Rother, Florian Jug, Paul Swoboda, and Bogdan Savchynskyy
(See online at https://doi.org/10.48550/arXiv.2004.06375) - Taxonomy of dual block-coordinate ascent methods for discrete energy minimization. In Proceedings of the Conference on Artifical Intelligence and Statistics, 2020
Siddharth Tourani, Alexander Shekhovtsov, Carsten Rother, and Bogdan Savchynskyy
(See online at https://doi.org/10.48550/arXiv.2004.07715) - Fusion moves for graph matching
Lisa Hutschenreiter, Stefan Haller, Dagmar Kainmüller, and Bogdan Savchynskyy
(See online at https://doi.org/10.48550/arXiv.2101.12085)
