Assignment flows for data labeling on graphs: convergence and stability
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 correspon...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
2022
|
| In: |
Information geometry
Year: 2022, Volume: 5, Issue: 2, Pages: 355-404 |
| ISSN: | 2511-249X |
| DOI: | 10.1007/s41884-021-00060-8 |
| Online Access: | Verlag, kostenfrei, Volltext: https://doi.org/10.1007/s41884-021-00060-8
|
| Author Notes: | Artjom Zern, Alexander Zeilmann, Christoph Schnörr |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1818209993 | ||
| 003 | DE-627 | ||
| 005 | 20240417193751.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 221007s2022 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1007/s41884-021-00060-8 |2 doi | |
| 035 | |a (DE-627)1818209993 | ||
| 035 | |a (DE-599)KXP1818209993 | ||
| 035 | |a (OCoLC)1361695974 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 27 |2 sdnb | ||
| 100 | 1 | |a Zern, Artjom |d 1987- |e VerfasserIn |0 (DE-588)1216462747 |0 (DE-627)1727696050 |4 aut | |
| 245 | 1 | 0 | |a Assignment flows for data labeling on graphs |b convergence and stability |c Artjom Zern, Alexander Zeilmann, Christoph Schnörr |
| 264 | 1 | |c 2022 | |
| 300 | |a 50 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Published online: 18 November 2021 | ||
| 500 | |a Gesehen am 21.12.2022 | ||
| 520 | |a 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. | ||
| 650 | 4 | |a 34B45 | |
| 650 | 4 | |a 34C40 | |
| 650 | 4 | |a 62H35 | |
| 650 | 4 | |a 68U10 | |
| 650 | 4 | |a 91A22 | |
| 650 | 4 | |a Assignment flow | |
| 650 | 4 | |a Evolutionary game dynamics | |
| 650 | 4 | |a Image and data labeling | |
| 650 | 4 | |a Information geometry | |
| 650 | 4 | |a Replicator equation | |
| 700 | 1 | |a Zeilmann, Alexander |e VerfasserIn |0 (DE-588)1225318092 |0 (DE-627)1744906696 |4 aut | |
| 700 | 1 | |a Schnörr, Christoph |e VerfasserIn |0 (DE-588)1023033348 |0 (DE-627)717351017 |0 (DE-576)168404540 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Information geometry |d Singapore : Springer Singapore, 2018 |g 5(2022), 2, Seite 355-404 |h Online-Ressource |w (DE-627)875634176 |w (DE-600)2878750-X |w (DE-576)48123912X |x 2511-249X |7 nnas |a Assignment flows for data labeling on graphs convergence and stability |
| 773 | 1 | 8 | |g volume:5 |g year:2022 |g number:2 |g pages:355-404 |g extent:50 |a Assignment flows for data labeling on graphs convergence and stability |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s41884-021-00060-8 |x Verlag |x Resolving-System |z kostenfrei |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20221007 | ||
| 993 | |a Article | ||
| 994 | |a 2022 | ||
| 998 | |g 1023033348 |a Schnörr, Christoph |m 1023033348:Schnörr, Christoph |d 110000 |d 110200 |d 110000 |d 110400 |d 700000 |d 728500 |e 110000PS1023033348 |e 110200PS1023033348 |e 110000PS1023033348 |e 110400PS1023033348 |e 700000PS1023033348 |e 728500PS1023033348 |k 0/110000/ |k 1/110000/110200/ |k 0/110000/ |k 1/110000/110400/ |k 0/700000/ |k 1/700000/728500/ |p 3 |y j | ||
| 998 | |g 1225318092 |a Zeilmann, Alexander |m 1225318092:Zeilmann, Alexander |d 110000 |d 110200 |d 110000 |d 110400 |d 700000 |d 728500 |e 110000PZ1225318092 |e 110200PZ1225318092 |e 110000PZ1225318092 |e 110400PZ1225318092 |e 700000PZ1225318092 |e 728500PZ1225318092 |k 0/110000/ |k 1/110000/110200/ |k 0/110000/ |k 1/110000/110400/ |k 0/700000/ |k 1/700000/728500/ |p 2 | ||
| 998 | |g 1216462747 |a Zern, Artjom |m 1216462747:Zern, Artjom |p 1 |x j | ||
| 999 | |a KXP-PPN1818209993 |e 4195038790 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"type":{"bibl":"article-journal","media":"Online-Ressource"},"note":["Published online: 18 November 2021","Gesehen am 21.12.2022"],"recId":"1818209993","language":["eng"],"title":[{"subtitle":"convergence and stability","title":"Assignment flows for data labeling on graphs","title_sort":"Assignment flows for data labeling on graphs"}],"person":[{"given":"Artjom","family":"Zern","role":"aut","display":"Zern, Artjom","roleDisplay":"VerfasserIn"},{"family":"Zeilmann","given":"Alexander","display":"Zeilmann, Alexander","roleDisplay":"VerfasserIn","role":"aut"},{"given":"Christoph","family":"Schnörr","role":"aut","display":"Schnörr, Christoph","roleDisplay":"VerfasserIn"}],"physDesc":[{"extent":"50 S."}],"relHost":[{"recId":"875634176","language":["eng"],"note":["Gesehen am 29. Mai 2018"],"type":{"bibl":"periodical","media":"Online-Ressource"},"disp":"Assignment flows for data labeling on graphs convergence and stabilityInformation geometry","part":{"issue":"2","pages":"355-404","year":"2022","extent":"50","text":"5(2022), 2, Seite 355-404","volume":"5"},"pubHistory":["2018-"],"title":[{"title":"Information geometry","title_sort":"Information geometry"}],"physDesc":[{"extent":"Online-Ressource"}],"id":{"issn":["2511-249X"],"zdb":["2878750-X"],"eki":["875634176"]},"origin":[{"publisher":"Springer Singapore","dateIssuedDisp":"[2018]-","publisherPlace":"Singapore"}]}],"origin":[{"dateIssuedKey":"2022","dateIssuedDisp":"2022"}],"id":{"eki":["1818209993"],"doi":["10.1007/s41884-021-00060-8"]},"name":{"displayForm":["Artjom Zern, Alexander Zeilmann, Christoph Schnörr"]}} | ||
| SRT | |a ZERNARTJOMASSIGNMENT2022 | ||