Jan-Hendrik Lange (PhD Student)

MSc Jan-Hendrik Lange

Address
Max-Planck-Institut für Informatik
Saarland Informatics Campus
Campus E1 4
66123 Saarbrücken
Location
E1 4 - Room 629
Phone
+49 681 9325 2029
Fax
+49 681 9325 2099
Email
Get email via email

Personal Information

Research Interests:

  • Combinatorial Optimization
  • Applications of Mathematical Optimization in Machine Learning

Education:

  • Master of Science in Mathematics with Minor in Computer Science, Technische Universität Darmstadt, June 2016
  • Since June 2016: PhD Student at Max Planck Institute for Informatics

 

Publications

2017
Analysis and Optimization of Graph Decompositions by Lifted Multicuts
A. Horňáková, J.-H. Lange and B. Andres
Proceedings of the 34th International Conference on Machine Learning (ICML 2017), 2017
Decomposition of Trees and Paths via Correlation
J.-H. Lange and B. Andres
Technical Report, 2017
(arXiv: 1706.06822v2)
Abstract
We study the problem of decomposing (clustering) a tree with respect to costs attributed to pairs of nodes, so as to minimize the sum of costs for those pairs of nodes that are in the same component (cluster). For the general case and for the special case of the tree being a star, we show that the problem is NP-hard. For the special case of the tree being a path, this problem is known to be polynomial time solvable. We characterize several classes of facets of the combinatorial polytope associated with a formulation of this clustering problem in terms of lifted multicuts. In particular, our results yield a complete totally dual integral (TDI) description of the lifted multicut polytope for paths, which establishes a connection to the combinatorial properties of alternative formulations such as set partitioning.
Discrete-Continuous Splitting for Weakly Supervised Learning
E. Laude, J.-H. Lange, F. R. Schmidt, B. Andres and D. Cremers
Technical Report, 2017
(arXiv: 1705.05020)
Abstract
This paper introduces a novel algorithm for a class of weakly supervised learning tasks. The considered tasks are posed as joint optimization problems in the continuous model parameters and the (a-priori unknown) discrete label variables. In contrast to prior approaches such as convex relaxations, we decompose the nonconvex problem into purely discrete and purely continuous subproblems in a way that is amenable to distributed optimization by the Alternating Direction Method of Multipliers (ADMM). This approach preserves integrality of the discrete label variables and, for a reparameterized variant of the algorithm using kernels, guarantees global convergence to a critical point. The resulting method implicitly alternates between a discrete and a continuous variable update, however, it is inherently different from a discrete-continuous coordinate descent scheme (hard EM). In diverse experiments we show that our method can learn a classifier from weak supervision that takes the form of hard and soft constraints on the labeling and outperforms hard EM in this task.
Efficient Algorithms for Moral Lineage Tracing
M. Rempfler, J.-H. Lange, F. Jug, C. Blasse, E. W. Myers, B. H. Menze and B. Andres
Technical Report, 2017
(arXiv: 1702.04111)
Abstract
Lineage tracing, the joint segmentation and tracking of living cells as they move and divide in a sequence of light microscopy images, is a challenging task. Jug et al. have proposed a mathematical abstraction of this task, the moral lineage tracing problem (MLTP) whose feasible solutions define a segmentation of every image and a lineage forest of cells. Their branch-and-cut algorithm, however, is prone to many cuts and slow convergences for large instances. To address this problem, we make three contributions: Firstly, we improve the branch-and-cut algorithm by separating tighter cutting planes. Secondly, we define two primal feasible local search algorithms for the MLTP. Thirdly, we show in experiments that our algorithms decrease the runtime on the problem instances of Jug et al. considerably and find solutions on larger instances in reasonable time.
2016
Lifting of Multicuts
B. Andres, A. Fuksova and J.-H. Lange
Technical Report, 2016
(arXiv: 1503.03791)
Abstract
For every simple, undirected graph $G = (V, E)$, a one-to-one relation exists between the decompositions and the multicuts of $G$. A decomposition of $G$ is a partition $\Pi$ of $V$ such that, for every $U \in \Pi$, the subgraph of $G$ induced by $U$ is connected. A multicut of $G$ is an $M \subseteq E$ such that, for every (chordless) cycle $C \subseteq E$ of $G$, $|M \cap C| \neq 1$. The multicut related to a decomposition is the set of edges that straddle distinct components. The characteristic function $x \in \{0, 1\}^E$ of a multicut $M = x^{-1}(1)$ of $G$ makes explicit, for every pair $\{v,w\} \in E$ of neighboring nodes, whether $v$ and $w$ are in distinct components. In order to make explicit also for non-neighboring nodes, specifically, for all $\{v,w\} \in E'$ with $E \subseteq E' \subseteq {V \choose 2}$, whether $v$ and $w$ are in distinct components, we define a lifting of the multicuts of $G$ to multicuts of $G' = (V, E')$. We show that, if $G$ is connected, the convex hull of the characteristic functions of those multicuts of $G'$ that are lifted from $G$ is an $|E'|$-dimensional polytope in $\mathbb{R}^{E'}$. We establish properties of trivial facets of this polytope.