Top

Published in:

2017 | OriginalPaper | Chapter

Entropic Trace Estimates for Log Determinants

Authors : Jack Fitzsimons, Diego Granziol, Kurt Cutajar, Michael Osborne, Maurizio Filippone, Stephen Roberts

Published in: Machine Learning and Knowledge Discovery in Databases

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The scalable calculation of matrix determinants has been a bottleneck to the widespread application of many machine learning methods such as determinantal point processes, Gaussian processes, generalised Markov random fields, graph models and many others. In this work, we estimate log determinants under the framework of maximum entropy, given information in the form of moment constraints from stochastic trace estimation. The estimates demonstrate a significant improvement on state-of-the-art alternative methods, as shown on a wide variety of matrices from the SparseSuite Matrix Collection. By taking the example of a general Markov random field, we also demonstrate how this approach can significantly accelerate inference in large-scale learning methods involving the log determinant.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Bayesian Nonlinear Support Vector Machines for Big Data

next chapter Fair Kernel Learning

Code for algorithms proposed in this paper are available at https://github.com/OxfordML/EntropicTraceEstimation.

Atallah, M.J., Grigorescu, E., Wu, Y.: A lower-variance randomized algorithm for approximate string matching. Inf. Process. Lett. 113(18), 690–692 (2013)MathSciNetCrossRefMATH

Aune, E., Simpson, D.P., Eidsvik, J.: Parameter estimation in high dimensional Gaussian distributions. Stat. Comput. 24(2), 247–263 (2014)MathSciNetCrossRefMATH

Avron, H.: Counting triangles in large graphs using randomized matrix trace estimation. In: Workshop on Large-Scale Data Mining: Theory and Applications, vol. 10, pp. 10–9 (2010)

Avron, H., Toledo, S.: Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. J. ACM (JACM) 58(2), 8:1–8:34 (2011)MathSciNetCrossRefMATH

Bai, Z., Golub, G.H.: Bounds for the trace of the inverse and the determinant of symmetric positive definite matrices. Ann. Numer. Math. 4, 29–38 (1997)MathSciNetMATH

Bandyopadhyay, K., Bhattacharya, A.K., Biswas, P., Drabold, D.: Maximum entropy and the problem of moments: a stable algorithm. Phys. Rev. E 71(5), 057701 (2005)CrossRef

Boutsidis, C., Drineas, P., Kambadur, P., Zouzias, A.: A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix. CoRR abs/1503.00374 (2015)

Buchen, P.W., Kelly, M.: The maximum entropy distribution of an asset inferred from option prices. J. Financ. Quant. Anal. 31(01), 143–159 (1996)CrossRef

Caticha, A.: Entropic Inference and the Foundations of Physics (monograph commissioned by the 11th Brazilian Meeting on Bayesian Statistics-EBEB-2012) (2012)

10.

Chen, J., Anitescu, M., Saad, Y.: Computing f(A)b via least squares polynomial approximations. SIAM J. Sci. Comput. 33(1), 195–222 (2011)MathSciNetCrossRefMATH

11.

Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. (TOMS) 38(1), 1 (2011)MathSciNetMATH

12.

Fitzsimons, J., Cutajar, K., Osborne, M., Roberts, S., Filippone, M.: Bayesian inference of log determinants (2017)

13.

Fitzsimons, J., Osborne, M., Roberts, S., Fitzsimons, J.: Improved stochastic trace estimation using mutually unbiased bases. arXiv preprint arXiv:1608.00117 (2016)

14.

Gershgorin, S.: Uber die Abgrenzung der Eigenwerte einer matrix. Izvestija Akademii Nauk SSSR Serija Matematika 7(3), 749–754 (1931)MATH

15.

Giffin, A., Cafaro, C., Ali, S.A.: Application of the maximum relative entropy method to the physics of ferromagnetic materials. Phys. A: Stat. Mech. Appl. 455, 11–26 (2016). http://www.sciencedirect.com/science/article/pii/S0378437116002478 MathSciNetCrossRef

16.

Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore (1996)MATH

17.

González, D., Davis, S., Gutiérrez, G.: Newtonian dynamics from the principle of maximum caliber. Found. Phys. 44(9), 923–931 (2014)MathSciNetCrossRefMATH

18.

Granziol, D., Roberts, S.: An information and field theoretic approach to the grand canonical ensemble (2017)

19.

Guinness, J., Ipsen, I.C.F.: Efficient computation of Gaussian likelihoods for stationary Markov random fields (2015)

20.

Han, I., Malioutov, D., Shin, J.: Large-scale log-determinant computation through stochastic Chebyshev expansions. In: Bach, F.R., Blei, D.M. (eds.) Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6–11 July 2015

21.

Hutchinson, M.: A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines. Commun. Stat. - Simul. Comput. 19(2), 433–450 (1990)MathSciNetCrossRefMATH

22.

Jaynes, E.T.: Information theory and statistical mechanics. Phys. Rev. 106, 620–630 (1957). http://link.aps.org/doi/10.1103/PhysRev.106.620 MathSciNetCrossRefMATH

23.

Lindgren, F., Rue, H., Lindström, J.: An explicit link between Gaussian fields and Gaussian Markov random fields: the stochastic partial differential equation approach. J. Roy. Stat. Soc.: Ser. B (Stat. Methodol.) 73(4), 423–498 (2011)MathSciNetCrossRefMATH

24.

Macchi, O.: The coincidence approach to stochastic point processes. Adv. Appl. Probab. 7, 83–122 (1975)MathSciNetCrossRefMATH

25.

Meurer, A., Smith, C.P., Paprocki, M., Čertík, O., Kirpichev, S.B., Rocklin, M., Kumar, A., Ivanov, S., Moore, J.K., Singh, S., Rathnayake, T., Vig, S., Granger, B.E., Muller, R.P., Bonazzi, F., Gupta, H., Vats, S., Johansson, F., Pedregosa, F., Curry, M.J., Terrel, A.R., Roučka, Š., Saboo, A., Fernando, I., Kulal, S., Cimrman, R., Scopatz, A.: SymPy: symbolic computing in Python. PeerJ Comput. Sci. 3, e103 (2017). https://doi.org/10.7717/peerj-cs.103 CrossRef

26.

Mohammad-Djafari, A.: A Matlab program to calculate the maximum entropy distributions. In: Smith, C.R., Erickson, G.J., Neudorfer, P.O. (eds.) Maximum Entropy and Bayesian Methods. FTPH, vol. 50, pp. 221–233. Springer, Dordrecht (1992). https://doi.org/10.1007/978-94-017-2219-3_16 CrossRef

27.

Neri, C., Schneider, L.: Maximum entropy distributions inferred from option portfolios on an asset. Finan. Stochast. 16(2), 293–318 (2012)MathSciNetCrossRefMATH

28.

Nielsen, M.A., Chuang, I.: Quantum computation and quantum information (2002)

29.

O’Hagan, A.: Bayes-Hermite quadrature. J. Stat. Plan. Infer. 29, 245–260 (1991)MathSciNetCrossRefMATH

30.

Pressé, S., Ghosh, K., Lee, J., Dill, K.A.: Principles of maximum entropy and maximum caliber in statistical physics. Rev. Mod. Phys. 85, 1115–1141 (2013). http://link.aps.org/doi/10.1103/RevModPhys.85.1115 CrossRef

31.

Rasmussen, C.E., Williams, C.: Gaussian Processes for Machine Learning. MIT Press, Cambridge (2006)MATH

32.

Rue, H., Held, L.: Gaussian Markov Random Fields: Theory and Applications, Monographs on Statistics and Applied Probability, vol. 104. Chapman & Hall, London (2005)MATH

33.

Saatçi, Y.: Scalable inference for structured Gaussian process models. Ph.D. thesis, University of Cambridge (2011)

34.

Shore, J., Johnson, R.: Axiomatic derivation of the principle of maximum entropy and the principle of minimum cross-entropy. IEEE Trans. Inf. Theory 26(1), 26–37 (1980)MathSciNetCrossRefMATH

35.

Ubaru, S., Chen, J., Saad, Y.: Fast estimation of tr(F(A)) via stochastic Lanczos quadrature (2016)

36.

Wainwright, M.J., Jordan, M.I.: Log-determinant relaxation for approximate inference in discrete Markov random fields. IEEE Trans. Signal Process. 54(6–1), 2099–2109 (2006)CrossRefMATH

37.

Wolfram Research Inc.: Mathematica. https://www.wolfram.com/mathematica/

Title: Entropic Trace Estimates for Log Determinants
Authors: Jack Fitzsimons
Diego Granziol
Kurt Cutajar
Michael Osborne
Maurizio Filippone
Stephen Roberts
Publisher: Springer International Publishing
Book: Machine Learning and Knowledge Discovery in Databases
Print ISBN: 978-3-319-71248-2

Electronic ISBN: 978-3-319-71249-9

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-71249-9_20

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner