Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-24T09:59:51.876Z Has data issue: false hasContentIssue false
  • English
  • Français

Continuous-domain assignment flows

Part of: Game theory Inference from stochastic processes Miscellaneous topics - Partial differential equations Existence theories

Published online by Cambridge University Press:  01 September 2020

F. SAVARINO Open the ORCID record for F. SAVARINO [Opens in a new window]  and
C. SCHNÖRR
F. SAVARINO
Affiliation:
Image and Pattern Analysis Group, Heidelberg University, Heidelberg, Germany emails: [email protected]; [email protected], URL: https://ipa.math.uni-heidelberg.de
C. SCHNÖRR
Affiliation:
Image and Pattern Analysis Group, Heidelberg University, Heidelberg, Germany emails: [email protected]; [email protected], URL: https://ipa.math.uni-heidelberg.de
Get access Rights & Permissions [Opens in a new window]

Abstract

Assignment flows denote a class of dynamical models for contextual data labelling (classification) on graphs. We derive a novel parametrisation of assignment flows that reveals how the underlying information geometry induces two processes for assignment regularisation and for gradually enforcing unambiguous decisions, respectively, that seamlessly interact when solving for the flow. Our result enables to characterise the dominant part of the assignment flow as a Riemannian gradient flow with respect to the underlying information geometry. We consider a continuous-domain formulation of the corresponding potential and develop a novel algorithm in terms of solving a sequence of linear elliptic partial differential equations (PDEs) subject to a simple convex constraint. Our result provides a basis for addressing learning problems by controlling such PDEs in future work.

Keywords

Image labellingimage segmentationinformation geometryreplicator equationevolutionary dynamicsassignment flow

MSC classification

Primary: 35R02: Partial differential equations on graphs and networks (ramified or polygonal spaces) 62M45: Neural nets and related approaches 68U10: Image processing
Secondary: 49J40: Variational methods including variational inequalities 91A22: Evolutionary games
Type
Papers
Information
European Journal of Applied Mathematics , Volume 32 , Special Issue 3: Connections between Deep learning and Partial Differential Equations , June 2021 , pp. 570 - 597
Check for updates
Copyright
© The Author(s), 2020. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Attouch, H., Buttazzo, G. & Michaille, G. (2014) Variational Analysis in Sovolev and BV Spaces: Applications to PDEs and Optimization, 2nd ed., SIAM, Philadelphia, PA.CrossRefGoogle Scholar
Amari, S.-I. & Nagaoka, H. (2000) Methods of Information Geometry, American Mathematical Society and Oxford University Press, Providence, Rhode Island.Google Scholar
Ambrosio, L., Fornasier, M., Morandotti, M. & Savaré, G. (2018) Spatially Inhomogeneous Evolutionary Games, CoRR abs/1805.04027.Google Scholar
Ambrosio, L. & Tortorelli, V. M. (1990) Approximation of functional depending on jumps by elliptic functional via $$\Gamma $$ -convergence. Comm. Pure Appl. Math. 43(8), 999–1036.CrossRefGoogle Scholar
Antun, V., Renna, F., Poon, C., Adcock, B. & Hansen, A. C. (2019) On Instabilities of Deep Learning in Image Reconstruction - Does AI Come at a Cost?, CoRR abs/1902.05300.Google Scholar
Åström, F., Petra, S., Schmitzer, B. & Schnörr, C. (2017) Image labeling by assignment. J. Math. Imaging Vis. 58(2), 211–238.CrossRefGoogle Scholar
Beck, A. & Teboulle, M. (2003) Mirror descent and nonlinear projected subgradient methods for convex optimization. Operat. Res. Lett. 31(3), 167–175.CrossRefGoogle Scholar
Bolte, J., Sabach, S. & Teboulle, M. (2014) Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Progr. Ser. A 146(1–2), 459–494.CrossRefGoogle Scholar
Bratus, A. S., Posvyanskii, V. P. & Novozhilov, A. S. (2014) Replicator equations and space. Math. Model. Nat. Phenomena 9(3), 47–67.CrossRefGoogle Scholar
Chambolle, A., Cremers, D. & Pock, T. (2012) A convex approach to minimal partitions. SIAM J. Imag. Sci. 5(4), 1113–1158.CrossRefGoogle Scholar
Coveney, P. V., Dougherty, E. R. & Highfield, R. R. (2016) Big data need big theory too. Phil. Trans. R. Soc. Lond. A 374, 20160153.Google ScholarPubMed
Cristoferi, R. & Thorpe, M. (2020) Large data limit for a phase transition model with the p-Laplacian on point clouds. Europ. J. Appl. Math. 31(2), 185–231.CrossRefGoogle Scholar
deForest, R. & Belmonte, A. (2013) Spatial pattern dynamics due to the fitness gradient flux in evolutionary games. Phys. Rev. E 87(6), 062138.CrossRefGoogle ScholarPubMed
Elad, M. (2017) Deep, deep trouble: deep learning’s impact on image processing, mathematics, and humanity, SIAM News 50(4).Google Scholar
Haber, E. & Ruthotto, L. (2017) Stable architectures for deep neural networks. Inverse Prob. 34(1), 014004.CrossRefGoogle Scholar
He, K., Zhang, X., Ren, S. & Sun, J. (2016) Deep residual learning for image recognition. In: Proceedings of CVPR.CrossRefGoogle Scholar
Hofbauer, J. & Siegmund, K. (2003) Evolutionary game dynamics. Bull. Amer. Math. Soc. 40(4), 479–519.CrossRefGoogle Scholar
Hühnerbein, R., Savarino, F., Petra, S. & Schnörr, C. (2019) Learning adaptive regularization for image labeling using geometric assignment. In: Proceedings of SSVM, Springer.CrossRefGoogle Scholar
Jost, J. (2017) Riemannian Geometry and Geometric Analysis, 7th ed., Springer-Verlag, Berlin, Heidelberg.CrossRefGoogle Scholar
Kimmel, R., Malladi, R. & Sochen, N. (2000) Images as embedded maps and minimal surfaces: movies, color, texture, and volumetric images. Int. J. Comp. Vis. 39(2), 111–129.CrossRefGoogle Scholar
Lellmann, J. & Schnörr, C. (2011) Continuous multiclass labeling approaches and algorithms. SIAM J. Imag. Sci. 4(4), 1049–1096.CrossRefGoogle Scholar
Liu, G.-H. & Theodorou, E. A. (2019) Deep Learning Theory Review: An Optimal Control and Dynamical Systems Perspective, CoRR abs/1908.10920.Google Scholar
Mumford, D. & Shah, J. (1989) Optimal approximations by piecewise smooth functions and associated variational problems. Comm. Pure Appl. Math. 42, 577–685.CrossRefGoogle Scholar
Novozhilov, A., PosvNovozh, V. P. & Bratus, A. S. (2011) On the reaction–diffusion replicator systems: spatial patterns and asymptotic behaviour. Russ. J. Numer. Anal. Math. Modell. 26(6), 555–564.Google Scholar
Rockafellar, R. T. & Wets, R. J.-B. (2009) Variational Analysis, Vol. 317, Springer Science & Business Media, Berlin and Heidelberg, Germany.Google Scholar
Sandholm, W. H. (2010) Population Games and Evolutionary Dynamics, MIT Press, Cambridge, Massachusetts.Google Scholar
Schnörr, C. (in press) Assignment flows. In: Grohs, P., Holler, M. & Weinmann, A. (editors), Variational Methods for Nonlinear Geometric Data and Applications, Springer, Cham, Switzerland.Google Scholar
Sternberg, P. (1991) Vector-valued local minimizers of nonconvex variational problems. Rocky-Mountain J. Math. 21(2), 799–807.CrossRefGoogle Scholar
Traulsen, A. & Claussen, J. C. (2004) Similarity-based cooperation and spatial segregation. Phys. Rev. E 70(4), 046128.CrossRefGoogle ScholarPubMed
Weinan, E. (2017) A proposal on machine learning via dynamical systems. Comm. Math. Stat. 5(1), 1–11.Google Scholar
Weinan, E., Han, J. & Li, Q. (2019) A mean-field optimal control formulation of deep learning. Res. Math. Sci. 6(10), 41 p.Google Scholar
Zeidler, E. (1985) Nonlinear Functional Analysis and its Applications, Vol. 3, Springer, New York, United States.CrossRefGoogle Scholar
Zern, A., Zeilmann, A. & Schnörr, C. (2020) Assignment Flows for Data Labeling on Graphs: Convergence and Stability, CoRR abs/2002.11571.Google Scholar
Zern, A., Zisler, M., Petra, S. & Schnörr, C. (in press) Unsupervised assignment flow: Label learning on feature manifolds by spatially regularized geometric assignment. J. Math. Imaging Vis. https://doi.org/10.1007/s10851-019-00935-7.CrossRefGoogle Scholar
Zeilmann, A., Savarino, F., Petra, S. & Schnörr, C. (2020) Geometric numerical integration of the assignment flow. Inverse Prob. 36(3), 034004 (33pp).CrossRefGoogle Scholar
Ziemer, W. P. (1989) Weakly Differentiable Functions, Springer, New York, United States.CrossRefGoogle Scholar
Zisler, M., Zern, A., Petra, S. & Schnörr, C. (2019) Unsupervised labeling by geometric and spatially regularized self-assignment. In: Proceedings of SSVM, Springer.CrossRefGoogle Scholar