Scalable inference for Gaussian hierarchical models

Abstract

Hierarchical modeling is a practical approach with proven results in modeling real world data. This paper studies Gaussian hierarchical models and methods which exploit the sparse conditional independence structure of such models to conduct scalable and efficient inference using sparse linear algebra methods. The efficiency of such methods is highly dependent on the row and column ordering of the precision matrix to be factorized. The key finding in this paper is that a depth-first permutation guarantees an optimal permutation of the precision matrix for Gaussian hierarchical models such that the fill-in ratio is optimal. This makes the use of permutation algorithms such as AMD or MMD unnecessary once it is known that the model used is a Gaussian hierarchical model, saving on computational efficiency. It was also found that the returned fill-in ratio is also optimal with a lexicographical ordering.Els models jeràrquics són una aproximació pràctica amb resultats provats en modelatge de dades del món real. Aquest article estudia els models i mètodes jeràrquics gaussians que estudien l’estructura d’independència dispersa condicional d’aquests models per a dur a terme inferència escalable i eficient utilitzant mètodes d’àlgebra linear dispersa. L’eficiència d’aquests mètodes és altament dependent de l’ordenament de files i columnes de la matriu de precisió a factoritzar. La troballa clau d’aquest article és que una permutació de primer grau garanteix tal permutació òptima de la matriu de precisió per a models jeràrquics gaussians que la ràtio d’emplenament és òptima. Això fa innecessari l’ús d’algoritmes de permutació com AMD o MMD, un cop és conegut que el model utilitzat és un model jeràrquic gaussià, estalviant en eficiència computacional. També s’ha trobat que la ràtio d’emplenament és també òptima amb ordenació lexicogràfica.