Alexander Zeilmann

We introduce a novel algorithm for estimating optimal parameters of linearized assignment flows for image labeling. An exact formula is derived for the parameter gradient of any loss function that is constrained by the linear system of ODEs determining the linearized assignment flow. We show how to efficiently evaluate this formula using a Krylov subspace and a low-rank approximation. This enables us to perform parameter learning by Riemannian gradient descent in the parameter space, without the need to backpropagate errors or to solve an adjoint equation. Experiments demonstrate that our method performs as good as highly-tuned machine learning software using automatic differentiation. Unlike methods employing automatic differentiation, our approach yields a low-dimensional representation of internal parameters and their dynamics which helps to understand how assignment flows and more generally neural networks work and perform.

The assignment flow recently introduced in the J. Math. Imaging and Vision 58/2 (2017) constitutes a high-dimensional dynamical system that evolves on a statistical product manifold and performs contextual labeling (classification) of data given in a metric space. Vertices of an underlying corresponding graph index the data points and define a system of neighborhoods. These neighborhoods together with nonnegative weight parameters define the regularization of the evolution of label assignments to data points, through geometric averaging induced by the affine e-connection of information geometry. From the point of view of evolutionary game dynamics, the assignment flow may be characterized as a large system of replicator equations that are coupled by geometric averaging. This paper establishes conditions on the weight parameters that guarantee convergence of the continuous-time assignment flow to integral assignments (labelings), up to a negligible subset of situations that will not be encountered when working with real data in practice. Furthermore, we classify attractors of the flow and quantify corresponding basins of attraction. This provides convergence guarantees for the assignment flow which are extended to the discrete-time assignment flow that results from applying a Runge–Kutta–Munthe–Kaas scheme for the numerical geometric integration of the assignment flow. Several counter-examples illustrate that violating the conditions may entail unfavorable behavior of the assignment flow regarding contextual data classification.

Like many other types of cancer, colorectal cancer (CRC) develops through multiple pathways of carcinogenesis. This is also true for colorectal carcinogenesis in Lynch syndrome (LS), the most common inherited CRC syndrome. However, a comprehensive understanding of the distribution of these pathways of carcinogenesis, which allows for tailored clinical treatment and even prevention, is still lacking. We suggest a linear dynamical system modeling the evolution of different pathways of colorectal carcinogenesis based on the involved driver mutations. The model consists of different components accounting for independent and dependent mutational processes. We define the driver gene mutation graphs and combine them using the Cartesian graph product. This leads to matrix components built by the Kronecker sum and product of the adjacency matrices of the gene mutation graphs enabling a thorough mathematical analysis and medical interpretation. Using the Kronecker structure, we developed a mathematical model which we applied exemplarily to the three pathways of colorectal carcinogenesis in LS. Beside a pathogenic germline variant in one of the DNA mismatch repair (MMR) genes, driver mutations in APC, CTNNB1, KRAS and TP53 are considered. We exemplarily incorporate mutational dependencies, such as increased point mutation rates after MMR deficiency, and based on recent experimental data, biallelic somatic CTNNB1 mutations as common drivers of LS-associated CRCs. With the model and parameter choice, we obtained simulation results that are in concordance with clinical observations. These include the evolution of MMR-deficient crypts as early precursors in LS carcinogenesis and the influence of variants in MMR genes thereon. The proportions of MMR-deficient and MMR-proficient APC-inactivated crypts as first measure for the distribution among the pathways in LS-associated colorectal carcinogenesis are compatible with clinical observations. The approach provides a modular framework for modeling multiple pathways of carcinogenesis yielding promising results in concordance with clinical observations in LS CRCs.

Like many other tumors, colorectal cancers develop through multiple pathways containing different driver mutations. This is also true for colorectal carcinogenesis in Lynch syndrome, the most common inherited colorectal cancer syndrome. However, a comprehensive understanding of Lynch syndrome tumor evolution which allows for tailored clinical treatment and even prevention is still lacking. We suggest a linear autonomous dynamical system modeling the evolution of the different pathways. Starting with the gene mutation graphs of the driver genes, we formulate three key assumptions about how these different mutations might be combined. This approach leads to a dynamical system that is built by the Kronecker sum of the adjacency matrices of the gene mutation graphs. This Kronecker structure makes the dynamical system amenable to a thorough mathematical analysis and medical interpretation, even if the number of incorporated genes or possible mutation states is increased. For the case that some of the mathematical key assumptions are not satisfied, we explain possible extensions to our model. Additionally, improved bio-medical measurements or novel medical insights can be integrated into the model in a straightforward manner, as all parameters in the model have a biological interpretation. Modifications of the model are able to account for other forms of colorectal carcinogenesis, such as Lynch-like and familial adenomatous polyposis cases. Graphical From the Medical Hypothesis Over the Modeling Approach To the Mathematical Structure.: The medical hypothesis of multiple pathways in carcinogenesis is widely known for various types of cancer. Left: We present a model for this phenomenon at the example of Lynch syndrome, the most common inherited colorectal cancer syndrome, with specific key driver events in the MMR genes, CTNNB1 , APC , KRAS and TP53 . Middle: This current medical understanding of carcinogenesis is translated into a mathematical model using a specific dynamical system, which can be represented by a graph structure, where each vertex in the graph represents a genotypic state and the edges correspond to the transition probabilities between those states. Starting with all colonic crypts in the state of all genes being wild-type and a single MMR germline mutation due to Lynch syndrome, we are interested in the distribution of the crypts among the graph at different ages of the patient in order to obtain estimates for the number of crypts in specific states, e.g. adenomatous or cancerous states. Right: The underlying matrix of the dynamical system makes use of the Kronecker sum and product. It is a sparse upper triangular matrix accounting for the assumption that mutations cannot be reverted. This allows fast numerical solving by using the matrix exponential. Each nonzero entry of the matrix represents a connection between genotypic states in the graph.

The assignment flow is a smooth dynamical system that evolves on an elementary statistical manifold and performs contextual data labeling on a graph. We derive and introduce the linear assignment flow that evolves nonlinearly on the manifold, but is governed by a linear ODE on the tangent space. Various numerical schemes adapted to the mathematical structure of these two models are designed and studied, for the geometric numerical integration of both flows: embedded Runge–Kutta–Munthe–Kaas schemes for the nonlinear flow, adaptive Runge–Kutta schemes and exponential integrators for the linear flow. All algorithms are parameter free, except for setting a tolerance value that specifies adaptive step size selection by monitoring the local integration error, or fixing the dimension of the Krylov subspace approximation. These algorithms provide a basis for applying the assignment flow to machine learning scenarios beyond supervised labeling, including unsupervised labeling and learning from controlled assignment flows.

We introduce the linear assignment flow as an approximation of the full nonlinear assignment flow, which is a method for contextual data labeling on arbitrary graphs. The linear assignment flow is a dynamical system evolving on the tangent space of a statistical manifold. It is numerically determined using exponential integrators and Krylov subspace approximation, for which we provide error estimates. The approximation property of the linear assignment flow is illustrated by a numerical experiment. This work is supplemented by two papers on variational modeling and unsupervised labeling [1].

The assignment flow is a smooth dynamical system that evolves on an elementary statistical manifold and performs contextual data labeling on a graph. We derive and introduce the linear assignment flow that evolves nonlinearly on the manifold, but is governed by a linear ODE on the tangent space. Various numerical schemes adapted to the mathematical structure of these two models are designed and studied, for the geometric numerical integration of both flows: embedded Runge-Kutta-Munthe-Kaas schemes for the nonlinear flow, adaptive Runge-Kutta schemes and exponential integrators for the linear flow. All algorithms are parameter free, except for setting a tolerance value that specifies adaptive step size selection by monitoring the local integration error, or fixing the dimension of the Krylov subspace approximation. These algorithms provide a basis for applying the assignment flow to machine learning scenarios beyond supervised labeling, including unsupervised labeling and learning from controlled assignment flows.