A study on structure recovery and the broadcasting problem

Abstract

The thesis contains a study of two problems of combinatorial statistics. The first one is structure learning for partial correlation graphs and the second one is the broadcasting problem on certain families of random recursive trees. In a precise language, the structure recovery problem that we study is the following: given access to individual entries of a covariance matrix S, learn the support of the inverse of S (let us denote this matrix by K) using only a small fraction of S. We call this problem ‘structure recovery’ since the zero-entries of K define the adjacency matrix of a graph (called partial correlation graph). As an example of why this is an important graph to learn, consider that S corresponds to a Gaussian random vector (X1, ..., Xn). Then an entry sij is zero if and only if Xi and Xj are independent given the rest of the random variables. A series of algorithms is proposed to address the aforementioned question, assuming that our graphs satisfy certain sparsity conditions. The sparsity that is assumed is related to how much our graph resembles a tree; in particular we deal with trees, graphs of small 2 connected components, and graphs of small treewidth. The proposed algorithms can also be used to estimate K and not only learn the partial correlation graph. Moreover, they can be used to invert any symmetric positive definite matrix since the analysis can be detached from its statistical connection and impact.The motivation for the use of covariance entries is that S might be too large to even store, as it often happens in statistical settings. In fact, our goal is to learn the partial correlation graph using sub-quadratic number of queries, since quadratic time is needed just to write down and store the covariance matrix – this is the starting point for a big part of the literature. The desired complexity bounds are achieved through our analysis. Moving to the second problem under study, we consider a broadcasting process on a graph to be the propagation of a message (let us say a bit value in {0, 1}) from one node to all the rest, possibly corrupted. Our goal is to guess the initial message. We consider that our graph is a tree and is created dynamically in times 0, 1..., n, in a way that at time i the i-th vertex enters the system and attaches with an edge to an existing vertex j (we then write i ~ j). We are interested in the case where i attaches uniformly at random to an existing vertex (uniform attachment) or where i attaches to a vertex with probability proportional to the outdegree of an existing vertex, plus some parameter ß > 0. The broadcasting process we consider is one where vertex 0 (the root) has a bit value that is propagated correctly to its neighbours with probability 1 - q and incorrectly with probability q. The broadcasting problem under study can be formulated in this way: given access to a random tree produced by either uniform attachment or preferential attachment and the bit values of the vertices, but without observing the time labels of the vertices, recover the bit of vertex zero. In a more difficult variant, we answer the same question given only the bits of vertices with outdegree zero (the leaves). In both variants of the problem in both models, we characterize the values of q for which the optimal reconstruction method has a probability of error bounded away from 1/2. We also show that the probability of error is bounded by a constant times q. Two simple reconstruction rules are analyzed in detail. One of them is the simple majority vote, the other is the bit value of the centroid of the tree (or the closest leaf to the centroid). We also analyze a third reconstruction rule which is more complex but works for all q where reconstruction is theoretically possible.

Aquesta tesi estudia dos problemes d'estadística combinatòria: l'aprenentatge d'estructura per a grafs de correlació parcial, i el problema de difusió en famílies d'arbres recursius aleatoris. En el primer cas, el problema de recuperació de l'estructura que estudiem és el següent: donat l'accés a les entrades individuals d'una matriu de covariància A, aprenem el suport de la inversa de S. (denotem aquesta matriu per K) utilitzant només una petita fracció de la matriu S. Anomenem aquest problema «de recuperació d'estructures», ja que les entrades nul·les de K defineixen la matriu d'adjacència d'un graf (anomenat graf de correlació parcial). Com a exemple del perquè aquest és un graf rellevant, considereu que S s'associa a un vector aleatori gaussià (X1, ..., Xn). Llavors una entrada sij és zero si i només si Xi i Xj són independents. Proposem una sèrie d'algorismes per estudiar la pregunta esmentada, assumint que els nostres grafs satisfan certes condicions de densitat. La densitat que s'assumeix està relacionada amb quant s'assembla el nostre graf a un arbre; en particular, tractem amb arbres, grafs amb components connexes suficientment petites, i grafs de petita amplada d'arbre. Els algorismes proposats també es poden utilitzar per estimar S i no només per aprendre el graf de correlació parcial. Finalment, les tècniques també es poden utilitzar per invertir qualsevol matriu simètrica definida positiva, ja que l'estudi es pot separar de la seva connexió estadística. La motivació per a l'ús d'entrades de covariància és que S pot ser massa gran per emmagatzemar-la, com passa sovint en configuracions estadístiques. De fet, el nostre objectiu és aprendre el graf de correlació parcial utilitzant el nombre subquadràtic de consultes, ja que el temps quadràtic és necessari només per a escriure i emmagatzemar la matriu de covariància: aquest és el punt de partida per a una gran part de la literatura. Els límits de complexitat desitjats s'aconsegueixen a través de la nostra anàlisi. En quant al segon problema, considerem que un procés de radiodifusió sobre un graf és la propagació d'un missatge (diguem un valor de bit a {0,1}) d'un node a tota la resta, possiblement corromput. El nostre objectiu és esbrinar el missatge inicial. Considerem que el nostre graf és un arbre i es crea dinàmicament en temps 0, 1, ..., n, de tal forma que en el temps i el vèrtex i-èssim entra al sistema i s'uneix amb una aresta a un vèrtex j existent (escrivim i~j). Estem interessats en el cas en què i s'adhereixi uniformement a l'atzar a un vèrtex existent (adjunt uniforme) o on s'hi connecti a un vèrtex amb probabilitat proporcional al grau de sortida d'un vèrtex existent, més algun paràmetre ß > 0. El procés de radiodifusió que considerem és un en què el vèrtex 0 (l'arrel) té un valor de bits que es propaga correctament als seus veïns amb probabilitat 1-q i incorrectament amb probabilitat q. El problema de la radiodifusió es pot formular d'aquesta manera: donat l'accés a un arbre aleatori produït per un adjunció uniforme, o per adjunció preferencial i els valors de bits dels vèrtexs, però sense observar les etiquetes de temps dels vèrtexs, recupereu el bit del vèrtex zero. En una variant més difícil, també es pretén estudiar-lo donat només els bits dels vèrtexs amb grau de sobre zero (les fulles). En les dues variants del problema, caracteritzem els valors de q per als quals el mètode de reconstrucció òptim té una probabilitat d'error limitat a 1/2. També demostrem que la probabilitat d'error està limitada per un múltiple constant de q. S'analitzen detalladament dues regles de reconstrucció senzilles: una d'elles és el vot per majoria simple, l'altre és el valor de bit del centroide de l'arbre (o la fulla més propera al centroide). També analitzem una tercera regla de reconstrucció que és més complexa, però funciona en casos més generals de la tria de q.