Combinatorial Optimization in Machine Learning and Computer Vision

Dr. Bogdan Savchynskyy, Prof. Dr. Carsten Rother, WiSe 2018/19

Announcements

On 17.10, as an exception, the seminar will take place in SR 4, INF 327, EG !

Summary

Machine learning techniques are tightly coupled with optimization methods. Many techniques become practical only if there exists a supporting optimization tool.

In the seminar we will discuss a number of recent articles on combinatorial optimization with applications in computer vision and machine learning.

Topics

Papers for presentation and discussion are in general pre-selected and grouped by subtopics. A short introduction will be given at the first seminar session on 17 October 2018. The paper assignment will also take place during this seminar.

All papers can be found here grouped by topics.

CRFs

  • [Introduction to CRFs] Bogdan Savchynskyy. Chapter 1: Introduction to Inference for Graphical Models. In Discrete Graphical Models. Optimization Perspective.
  • [Introduction to Graph Cuts] Yuri Boykov, Olga Veksler, Ramin Zabih. Fast Approximate Energy Minimization via Graph Cuts. In PAMI 2001.
  • Hunter Lang, David Sontag, Aravindan Vijayaraghavan. Alpha-expansion is Exact on Stable Instances. arXiv preprint arXiv:1711.02195 (2017).
  • Lena Gorelick, Olga Veksler, Yuri Boykov, Claudia Nieuwenhuis. Convexity Shape Prior for Binary Segmentation. In PAMI 2017.
  • E. Laude, J.-H. Lange, J. Schüpfer, C. Domokos, L. Leal-Taixé, F. R. Schmidt, B. Andres, D. Cremers. Discrete-Continuous ADMM for Transductive Inference in Higher-Order MRFs. In CVPR 2018.
  • Hossam Isack, Yuri Boykov. Energy-based Geometric Multi-Model Fitting. In IJCV 2010.
  • Andrew Delong, Anton Osokin, Hossam Isack, Yuri Boykov. Fast Approximate Energy Minimization with Label Costs. In IJCV 2010.
  • Rustem Takhanov, Vladimir Kolmogorov. Inference algorithms for pattern-based CRFs on sequence data. arXiv preprint arXiv:1210.0508v5 (2012).
  • Lena Gorelick, Yuri Boykov, Olga Veksler, Ismail Ben Ayed, Andrew Delong. Local Submodularization for Binary Pairwise Energies. In PAMI 2017.
  • Paul Swoboda, Vladimir Kolmogorov. MAP inference via Block-Coordinate Frank-Wolfe Algorithm. arXiv preprint arXiv:1806.05049 (2018).

Dense CRFs

  • Philipp Krähenbühl, Vladlen Koltun. Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials. In NIPS 2011.
  • Olga Veksler. Efficient Graph Cut Optimization for Full CRFs with Quantized Edges. arXiv preprint arXiv:1809.04995 (2018).
  • Thalaiyasingam Ajanthan, Alban Desmaison, Rudy Bunel, Mathieu Salzmann, Philip H.S. Torr, M. Pawan Kumar. Efficient Linear Programming for Dense CRFs. In CVPR 2017.

M-Solutions CRFs

  • Alexander Kirillov, Bogdan Savchynskyy, Dmitrij Schlesinger, Dmitry Vetrov, Carsten Rother. Inferring M-Best Diverse Labelings in a Single One. In ICCV 2015.
  • Chao Chen, Vladimir Kolmogorov, Yan Zhu, Dimitris Metaxas, Christoph H. Lampert. Computing the M Most Probable Modes of a Graphical Model. In AISTATS 2013.
  • Cong Chen, Changhe Yuan, Ze Ye, Chao Chen. Solving M-Modes in Loopy Graphs Using Tree Decompositions. In PGM 2018.

Multicut

  • [Introduction to Multicut] Jörg Hendrik Kappes, Markus Speth, Bjoern Andres, Gerhard Reinelt, Christoph Schnörr. Globally Optimal Image Partitioning by Multicuts. In EMMCVPR 2011.
  • Loic A. Royer, David L. Richmond, Carsten Rother, Bjoern Andres, Dagmar Kainmüller. Convexity Shape Constraints for Image Segmentation. In CVPR 2016.
  • M. Keuper, E. Levinkov, N. Bonneel, G. Lavoué, T. Brox, B. Andres. Efficient Decomposition of Image and Mesh Graphs by Lifted Multicuts. In ICCV 2015.
  • Margret Keuper, Bjoern Andres, Thomas Brox. Motion Trajectory Segmentation via Minimum Cost Multicuts. In ICCV 2015.
  • Jan-Hendrik Lange, Andreas Karrenbauer, Bjoern Andres. Partial Optimality and Fast Lower Bounds for Weighted Correlation Clustering. In ICML 2018.
  • Leonid Pishchulin, Eldar Insafutdinov, Siyu Tang, Bjoern Andres, Mykhaylo Andriluka, Peter Gehler, Bernt Schiele. Deep Cut: Joint Subset Partition and Labeling for Multi Person Pose Estimation. In CVPR 2016.

Moral Lineage Trees

  • Florian Jug, Evgeny Levinkov, Corinna Blasse, Eugene W. Myers, Bjoern Andres. Moral Lineage Tracing. In CVPR 2016.
  • Markus Rempfler, Jan-Hendrik Lange, Florian Jug, Corinna Blasse, Eugene W. Myers, Bjoern H. Menze, Bjoern Andres. Efficient Algorithms for Moral Lineage Tracing. In ICCV 2017.

Learning Combinatorics

  • Dmitrii Marin, Meng Tang, Ismail Ben Ayed, Yuri Boykov. ADM for grid CRF loss in CNN segmentation. arXiv preprint arXiv:1809.02322 (2018).
  • Andrei Zanfir, Cristian Sminchisescu. Deep Learning of Graph Matching. In CVPR 2018.
  • Samuel Schulter, Paul Vernaza, Wongun Choi, Manmohan Chandraker. Deep Network Flow for Multi-Object Tracking. In CVPR 2017.
  • Hanjun Dai, Zornitsa Kozareva, Bo Dai, Alexander J. Smola, Le Song. Learning Steady-States of Iterative Algorithms over Graphs. In ICML 2018.
  • Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, Ellen Vitercik. Learning to Branch. arXiv preprint arXiv:1803.10150 (2018).
  • Pritish Mohapatra, C. V. Jawahar, M. Pawan Kumar. Learning to Round for Discrete Labeling Problems. In AISTATS 2018.

Schedule

28 November 2018

16:00 - Introduction to Energy Minimization via Graph Cuts.
16:45 - L. Lenz. Fast Approximate Energy Minimization with Label Costs.

12 December 2018

16:00 - T. Darr. Convexity Shape Prior for Binary Segmentation.
16:45 - I. Dehner. Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials.

19 December 2018

16:00 - Y. Venichenko. Efficient Algorithms for Moral Lineage Tracing.

9 January 2019

16:00 - J. Schnell. Globally Optimal Image Partitioning by Multicuts.
17:00 - P. Hilt. Convexity Shape Constraints for Image Segmentation.

16 January 2019

16:00 - A. Zulfiqar. Partial Optimality and Fast Lower Bounds for Weighted Correlation Clustering.
16:45 - S. Muller. Deep Cut: Joint Subset Partition and Labeling for Multi Person Pose Estimation.

23 January 2019

16:00 - O. Mautschke. Deep Learning of Graph Matching.
16:45 - S. Dubey. Deep Network Flow for Multi-Object Tracking.

30 January 2019

16:00 - E. F. Sanmartin. ADM for grid CRF loss in CNN segmentation.

Information

Important: On 17.10, as an exception, the seminar will take place in SR 4, INF 327, EG !

  • Seminar: Wed, 16:00 – 18:00, Raum: Mathematikon B (Berliner Str. 43), SR B128
    Ring the door bell labelled "HCI am IWR" to be let in. The seminar room is in the 3rd floor.
  • Credits: 2 / 4 / 6 CP depending on course of study

The presentations will be scheduled at the first meeting on 17 October 2018.

Registration

Please register for the seminar in Müsli. If you have trouble registering there drop an email to lisa.kruse@iwr.uni-heidelberg.de.

Contact

Lisa Kruse
Dr. Bogdan Savchynskyy