Abstract
We propose a novel way of approximating energy-based models by randomizing the parameters of assignment flows, a class of smooth dynamical data labeling systems. Our approach builds on averaging flow limit points within the combinatorially large simplex of joint distributions. In an initial learning stage, the distribution of flow parameters is selected to match a given energy-based model. This entails the difficult problem of estimating model entropy which we address by differentiable approximation of a bias-corrected estimator. The model subsequently allows to perform probabilistic inference by computationally efficient draws of structured integer samples which are approximately governed by the energy-based target Gibbs measure in the low-temperature regime. We conduct a rigorous quantitative assessment by approximating a small two-dimensional Ising model and find close approximation of the combinatorial solution in terms of relative entropy which outperforms a mean-field approximation baseline.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
All experiments were run on a single NVIDIA RTX 2080ti graphics card.
References
Åström, F., Petra, S., Schmitzer, B., Schnörr, C.: Image labeling by assignment. J. Math. Imaging Vis. 58(2), 211–238 (2017). https://doi.org/10.1007/s10851-016-0702-4
Baxter, R.: Exactly Solved Models in Statistical Mechanics. Academic Press (1982)
Blei, D.M., Kucukelbir, A., McAuliffe, J.D.: Variational inference: a review for statisticians. J. Am. Stat. Assoc. 112(518), 859–877 (2017)
Boll, B., Schwarz, J., Schnörr, C.: On the correspondence between replicator dynamics and assignment flows. In: Elmoataz, A., Fadili, J., Quéau, Y., Rabin, J., Simon, L. (eds.) SSVM 2021. LNCS, vol. 12679, pp. 373–384. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-75549-2_30
Boll, B., Zeilmann, A., Petra, S., Schnörr, C.: Self-certifying classification by linearized deep assignment. preprint arXiv:2201.11162 (2022)
Brèmaud, P.: Discrete Probability Models and Methods. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-43476-6
Catoni, O.: PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning. Institute of Mathematical Statistics (2007)
Dynkin, E.B.: Sufficient statistics and extreme points. Ann. Probab. 6(5), 705–730 (1978)
Geman, S., Geman, D.: Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intell. 6(6), 721–741 (1984)
Gidas, B.: A renormalization group approach to image processing problems. IEEE Trans. Pattern Anal. Mach. Intell. 11(11), 164–180 (1989)
Heskes, T.: Convexity arguments for efficient minimization of the Bethe and Kikuchi free energies. J. Artif. Intell. Res. 26, 153–190 (2006)
Jiao, J., Venkat, K., Han, Y., Weissman, T.: Minimax estimation of functionals of discrete distributions. IEEE Trans. Inf. Theory 61(5), 2835–2885 (2015)
Kappes, J., et al.: A comparative study of modern inference techniques for structured discrete energy minimization problems. Int. J. Comput. Vis. 115(2), 155–184 (2015). https://doi.org/10.1007/s11263-015-0809-x
Kingma, D.P., Ba, J.: Adam: a method for stochastic optimization. preprint arXiv:1412.6980 (2014)
Kingma, D.P., Welling, M.: Auto-encoding variational bayes. preprint arXiv:1312.6114 (2013)
Kobyzev, I., Prince, S.D., Brubaker, M.A.: Normalizing flows: an introduction and review of current methods. IEEE Trans. Pattern Anal. Mach. Intell. 43(11), 3964–3979 (2021)
Mézard, M., Montanari, A.: Information, Physics, and Computation. Oxford University Press, Oxford (2009)
Miller, G.: Note on the Bias of Information Estimates. Information Theory in Psychology: Problems and Methods (1955)
Montgomery-Smith, S., Schürmann, T.: Unbiased estimators for entropy and class number. arXiv preprint arXiv:1410.5002 (2014)
Pakzad, P., Anantharam, V.: Estimation and marginalization using Kikuchi approximation methods. Neural Comput. 17(8), 1836–1873 (2005)
Paninski, L.: Estimation of entropy and mutual information. Neural Comput. 15(6), 1191–1253 (2003)
Paszke, A., et al.: Pytorch: an imperative style, high-performance deep learning library. In: NIPS (2019)
Pathria, R.K., Beale, P.D.: Statistical Mechanics, 3rd edn. Academic Press (2011)
Ramesh, A., Dhariwal, P., Nichol, A., Chu, C., Chen, M.: Hierarchical text-conditional image generation with CLIP latents (2022)
Rizzo, T., Wemmenhove, B., Kappen, H.J.: Cavity approximation for graphical models. Phys. Rev. E 76(1), 011102 (2007)
Ruthotto, L., Haber, E.: An introduction to deep generative modeling. GAMM Mitt. 44(2), 24 (2021)
Savarino, F., Schnörr, C.: Continuous-domain assignment flows. Eur. J. Appl. Math. 32(3), 570–597 (2021)
Schnörr, C.: Assignment flows. In: Grohs, P., Holler, M., Weinmann, A. (eds.) Handbook of Variational Methods for Nonlinear Geometric Data, pp. 235–260. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-31351-7_8
Valiant, G., Valiant, P.: Estimating the unseen: an n/log (n)-sample estimator for entropy and support size, shown optimal via new CLTs. In: Proceedings of the 43th ACM Symposium on Theory of Computing, pp. 685–694 (2011)
Valiant, G., Valiant, P.: Estimating the unseen: improved estimators for entropy and other properties. J. ACM 64(6), 1–41 (2017)
Wainwright, M.J., Jaakola, T.S., Willsky, A.S.: Tree-based reparameterization framework for analysis of sum-product and related algorithms. IEEE Trans. Inf. Theory 49(5), 1120–1146 (2003)
Wainwright, M., Jordan, M.: Graphical models, exponential families, and variational inference. Found. Trends Mach. Learn. 1(1–2), 1–305 (2008)
Wu, Y., Yang, P.: Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Trans. Inf. Theory 62(6), 3702–3720 (2016)
Zeilmann, A., Savarino, F., Petra, S., Schnörr, C.: Geometric numerical integration of the assignment flow. Inverse Probl. 36(3), 034004 (33pp) (2020)
Zern, A., Zeilmann, A., Schnörr, C.: Assignment flows for data labeling on graphs: convergence and stability. Inf. Geom. 5, 355–404 (2022). https://doi.org/10.1007/s41884-021-00060-8
Acknowledgements
This work is funded by the Deutsche Forschungsgemeinschaft (DFG), grant SCHN 457/17-1, within the priority programme SPP 2298: “Theoretical Foundations of Deep Learning”. This work is funded by the Deutsche Forschungsgemeinschaft (DFG) under Germany’s Excellence Strategy EXC-2181/1 - 390900948 (the Heidelberg STRUCTURES Excellence Cluster).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Boll, B., Schwarz, J., Gonzalez-Alvarado, D., Sitenko, D., Petra, S., Schnörr, C. (2023). Modeling Large-Scale Joint Distributions and Inference by Randomized Assignment. In: Calatroni, L., Donatelli, M., Morigi, S., Prato, M., Santacesaria, M. (eds) Scale Space and Variational Methods in Computer Vision. SSVM 2023. Lecture Notes in Computer Science, vol 14009. Springer, Cham. https://doi.org/10.1007/978-3-031-31975-4_56
Download citation
DOI: https://doi.org/10.1007/978-3-031-31975-4_56
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-31974-7
Online ISBN: 978-3-031-31975-4
eBook Packages: Computer ScienceComputer Science (R0)