Assignment flows for data labeling on graphs: convergence and stability

Information Geometry - 2022
Artjom Zern1, Alexander Zeilmann1, Christoph Schnörr1
1Image and Pattern Analysis Group, Heidelberg University, Heidelberg, Germany

Tóm tắt

AbstractThe 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.

Từ khóa


Tài liệu tham khảo

Amari, S.I., Nagaoka, H.: Methods of Information Geometry. Oxford Univ. Press, Oxford (2000)

Åström, F., Petra, S., Schmitzer, B., Schnörr, C.: Image labeling by assignment. J. Math. Imag. Vision 58(2), 211–238 (2017)

Ay, N., Jost, J., Lê, H.V., Schwachhöfer, L.: Information Geometry, Ergebnisse Der Mathematik Und Ihrer Grenzgebiete 34, vol. 64. Springer, Cham (2017)

Belitskii, G., Rayskin, V.: On the Grobman–Hartman theorem in $$\alpha $$-Hölder class for Banach spaces. preprint (2009)

Bergmann, R., Fitschen, J.H., Persch, J., Steidl, G.: Iterative multiplicative filters for data labeling. Int. J. Comput. Vision 123(3), 435–453 (2017)

Bomze, I.M.: Regularity versus degeneracy in dynamics, games, and optimization: a unified approach to different aspects. SIAM Rev. 44(3), 394–414 (2002)

Chan, T.F., Esedoglu, S., Nikolova, M.: Algorithms for finding global minimizers of image segmentation and denoising models. SIAM J. Appl. Math. 66(5), 1632–1648 (2006)

Cordts, M., Omran, M., Ramos, S., Refeld, T., Enzweiler, M., Beneson, R., Franke, U., Roth, S., Schiele, B.: The cityscapes dataset for semantic urban scene understanding. In: Proc. CVPR (2016)

Elad, M.: Deep, deep trouble: deep learning’s impact on image processing, mathematics, and humanity. SIAM News 50(4) (2017)

Fenichel, N.: Geometric singular perturbation theory for ordinary differential equations. J. Differ. Equ. 31(1), 53–98 (1979)

Finlayson, S., Bowers, J., Ito, J., Zittrain, J., Beam, A., Kohane, I.: Adversarial attacks on medical machine learning: emerging vulnerabilities demand new conversations. Science 363(6433), 1287–1289 (2019)

Galla, T., Farmer, J.: Complex dynamics in learning complicated games. PNAS 110(4), 1232–1236 (2013)

Goodfellow, I., Bengio, Y., Courville, A.: Deep Learning. MIT Press, New York (2016)

Heaven, D.: Deep trouble for deep learning. Nature 574 (2019)

Hofbauer, J., Sigmund, K.: Evolutionary game dynamics. Bull. Am. Math. Soc. 40(4), 479–519 (2003)

Hühnerbein, R., Savarino, F., Petra, S., Schnörr, C.: Learning adaptive regularization for image labeling using geometric assignment. J. Math. Imaging Vis. 63, 186–215 (2021)

Kappes, J., Andres, B., Hamprecht, F., Schnörr, C., Nowozin, S., Batra, D., Kim, S., Kausler, B., Kröger, T., Lellmann, J., Komodakis, N., Savchynskyy, B., Rother, C.: A comparative study of modern inference techniques for structured discrete energy minimization problems. Int. J. Comput. Vis. 115(2), 155–184 (2015)

Kelley, A.: The stable, center-stable, center, center-unstable, unstable manifolds. J. Differ. Equ. (1966)

Losert, V., Akin, E.: Dynamics of games and genes: discrete versus continuous time. J. Math. Biol. 17(2), 241–251 (1983)

Nock, R., Nielsen, F.: Statistical region merging. IEEE Trans. Pattern. Anal. Mach. Intell. 26(11), 1452–1458 (2004)

Perko, L.: Differential Equations and Dynamical Systems, vol. 7. Springer, Berlin (2001)

Sandholm, W.H.: Population Games and Evolutionary Dynamics. MIT Press, Chicago (2010)

Savarino, F., Schnörr, C.: Continuous-domain assignment flows. Eur. J. Appl. Math. 32(3), 570–597 (2021)

Schaeffer, D.G., Cain, J.W.: Ordinary Differential Equations: Basics and Beyond. Springer, Berlin (2016)

Schecter, S., Gintis, H.: Game Theory in Action: An Introduction to Classical and Evolutionary Models. Princeton University Press, Princeton (2016)

Schnörr, C.: Assignment Flows. In: Grohs, P., Holler, M., Weinmann, A. (eds.) Variational Methods for Nonlinear Geometric Data and Applications, pp. 235–260. Springer, Berlin (2020)

Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Trans. Pattern. Anal. Mach. Intell. 22, 888–905 (2000)

Sitenko, D., Boll, B., Schnörr, C.: Assignment flow for order-constrained OCT segmentation. Int. J. Comput. Vis. 129, 3088–3118 (2021).

Teschl, G.: Ordinary Differential Equations and Dynamical Systems. Grad. Studies Math, vol. 140. Amer. Math. Soc, London (2012)

Van Loan, C.F.: The ubiquitous Kronecker product. J. Comput. Appl. Math. 123, 85–100 (2000)

Zeilmann, A., Petra, S., Schnörr, C.: Learning Linear Assignment Flows for Image Labeling via Exponential Integration. In: Elmoataz, A., Fadili, J., Quéau, Y., Rabin, J., Simon, L. (eds.) Scale Space and Variational Methods in Computer Vision (SSVM), LNCS, vol. 12679, pp. 385–397 (2021)

Zeilmann, A., Petra, S., Schnörr, C.: Learning Linearized Assignment Flows for Image Labeling. arXiv:2108.02571 (2021)

Zeilmann, A., Savarino, F., Petra, S., Schnörr, C.: Geometric numerical integration of the assignment flow. Inverse Prob. 36, 034004 (33pp) (2020)

Zern, A., Zisler, M., Petra, S., Schnörr, C.: Unsupervised assignment flow: label learning on feature manifolds by spatially regularized geometric assignment. J. Math. Image. Vis. 62(6–7), 982–1006 (2020)

Zisler, M., Zern, A., Petra, S., Schnörr, C.: Self-assignment flows for unsupervised data labeling on graphs. SIAM J. Image. Sci. 13(3), 1113–1156 (2020)

Thông tin
Thông tin xuất bản

Information Geometry

Thông tin tác giả