Timezone: »
The Probabilistic Watershed is a semi-supervised learning algorithm applied on undirected graphs. Given a set of labeled nodes (seeds), it defines a Gibbs probability distribution over all possible spanning forests disconnecting the seeds. It calculates, for every node, the probability of sampling a forest connecting a certain seed with the considered node. We propose the "Directed Probabilistic Watershed", an extension of the Probabilistic Watershed algorithm to directed graphs. Building on the Probabilistic Watershed, we apply the Matrix Tree Theorem for directed graphs and define a Gibbs probability distribution over all incoming directed forests rooted at the seeds. Similar to the undirected case, this turns out to be equivalent to the Directed Random Walker. Furthermore, we show that in the limit case in which the Gibbs distribution has infinitely low temperature, the labeling of the Directed Probabilistic Watershed is equal to the one induced by the incoming directed forest of minimum cost. Finally, for illustration, we compare the empirical performance of the proposed method with other semi-supervised segmentation methods for directed graphs.
Author Information
Enrique Fita Sanmartin (Heidelberg University)
Sebastian Damrich (Heidelberg University)
Fred Hamprecht (Heidelberg University)
More from the Same Authors
-
2022 Poster: Theory and Approximate Solvers for Branched Optimal Transport with Multiple Sources »
Peter Lippmann · Enrique Fita SanmartĂn · Fred Hamprecht -
2021 Poster: On UMAP's True Loss Function »
Sebastian Damrich · Fred Hamprecht -
2019 Poster: Probabilistic Watershed: Sampling all spanning forests for seeded segmentation and semi-supervised learning »
Enrique Fita Sanmartin · Sebastian Damrich · Fred Hamprecht -
2019 Spotlight: Probabilistic Watershed: Sampling all spanning forests for seeded segmentation and semi-supervised learning »
Enrique Fita Sanmartin · Sebastian Damrich · Fred Hamprecht -
2017 Poster: Sparse convolutional coding for neuronal assembly detection »
Sven Peter · Elke Kirschbaum · Martin Both · Lee Campbell · Brandon Harvey · Conor Heins · Daniel Durstewitz · Ferran Diego · Fred Hamprecht -
2017 Poster: Cost efficient gradient boosting »
Sven Peter · Ferran Diego · Fred Hamprecht · Boaz Nadler -
2016 : Fred Hamprecht : Motif Discovery in Functional Brain Data »
Fred Hamprecht -
2014 Poster: Sparse Space-Time Deconvolution for Calcium Image Analysis »
Ferran Diego Andilla · Fred Hamprecht -
2014 Spotlight: Sparse Space-Time Deconvolution for Calcium Image Analysis »
Ferran Diego Andilla · Fred Hamprecht -
2013 Poster: Learning Multi-level Sparse Representations »
Ferran Diego Andilla · Fred Hamprecht -
2011 Poster: Structured Learning for Cell Tracking »
Xinghua Lou · Fred Hamprecht