Combinatorial Optimization in Machine Learning and Computer Vision

Dr. Bogdan Savchynskyy, Prof. Dr. Carsten Rother, SoSe 2019

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.

General Information

• Seminar: Wed, 14:00 – 16: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

Schedule

5 June 2019

14:00 - M. Schäfers. The Auction Algorithm and Variants Thereof.

19 June 2019

14:00 - M. Tabachnik. The Sinkhorn Algorithm and its Analysis.

26 June 2019

15:00 - D. Fieberg. Convergence and Correctness of Belief Propagation for Min-Cost Network Flow.

10 July 2019

14:00 - H. Tian. Motion Trajectory Segmentation.

17 July 2019

14:00 - T. Darr. Weighted Correlation Clustering.
15:00 - L. Kuppel. Combinatorial Persistency Criteria.

24 July 2019

14:00 - M. Tabachnik. TBA.

Registration

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

Topics

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

Cell-Tracking

• Moral Lineage Tracing
  Jug et al.: Moral Lineage Tracing
  Rempfler et al.: Efficient Algorithms for Moral Lineage Tracing

• Graphical Models for Joint Segmentation and Tracking
  Kausler et al.: A Discrete Chain Graph Model for 3d+t Cell Tracking with High Misdetection Robustness
  Schiegg et al.: Graphical Model for Joint Segmentation and Tracking of Multiple Dividing Cell

• Cell Tracking using Integer Programming
  Tueretken et al.: Globally Optimal Cell Tracking using Integer Programming

• Escherichia Coli in the Mother Machine
  Jug et al.: Optimal Joint Segmentation and Tracking of Escherichia Coli in the Mother Machine

• Conservation Tracking
  Schiegg et al.: Conservation Tracking

• Linking of Cell Tracks using the Viterbi Algorithm
  Magnusson et al.: Global Linking of Cell Tracks using the Viterbi Algorithm

Min-Cost-Flow

• The Auction Algorithm and Variants Thereof
  Bertsekas: Network Optimization: Continuous and Discrete Models

• The Sinkhorn Algorithm and its analysis
  Sinkhorn, Knopp: Concerning Nonnegative Matrices and Doubly Stochastic Matrices

• Loopy Belief Propagation
  Sanghavi et al.: Linear Programming Analysis of Loopy Belief Propagation for Weighted Matching

• Belief Propagation Min-Sum Algorithm for Min-Cost Network Flow
  Riazanov et al.: Belief Propagation Min-Sum Algorithm for Generalized Min-Cost Network Flow

• Convergence and Correctness of Belief Propagation for Min-Cost Network Flow
  Gamarnik, Shah, Wei: Belief Propagation for Min-Cost Network Flow: Convergence and Correctness

Multicut

• Decomposition of Image and Mesh Graphs by Lifted Multicut
  Keuper et al.: Efficient Decomposition of Image and Mesh Graphs by Lifted Multicuts

• Motion Trajectory Segmentation
  Keuper et al.: Motion Trajectory Segmentation via Minimum Cost Multicuts

• Weighted Correlation Clustering
  Lange et al.: Partial Optimality and Fast Lower Bounds for Weighted Correlation Clustering

• Message Passing for Minimum Cost Multicut
  Swoboda, Andres: A Message Passing Algorithm for the Minimum Cost Multicut Problem

• Combinatorial Persistency Criteria
  Lange, Andres, Swoboda: Combinatorial Persistency Criteria for Multicut and Max-Cut

You can find all papers in the HeiBOX. The password will be announced during the introduction.

Contact

Lisa Kruse
Dr. Bogdan Savchynskyy