Browsing by Subject "Graphical models"
Now showing 1 - 6 of 6
Results Per Page
Sort Options
Item Graph theoretic results on index coding, causal inference and learning graphical models(2016-08) Shanmugam, Karthikeyan; Dimakis, Alexandros G.; Sanghavi, Sujay; Shakkottai, Sanjay; Caramanis, Constantine; Zuckerman, DavidExploiting and learning graph structures is becoming ubiquitous in Network Information Theory and Machine Learning. The former deals with efficient communication schemes in a many-node network. In the latter, inferring graph structured relationships from high dimensional data is important. In this dissertation, some graph theoretic results in these two areas are presented. The first part deals with the problem of optimizing bandwidth resources for a shared broadcast link serving many users each having access to cached content. This problem and its variations are broadly called Index Coding. Index Coding is fundamental to understanding multi-terminal network problems and has applications in networks that deploy caches. The second part deals with the resources required for learning a network structure that encodes distributional and causal relationships among many variables in machine learning. The number of samples needed to learn graphical models that capture crucial distributional information is studied. For learning causal relationships, when passive data acquisition is not sufficient, the number of interventions required is investigated. In the first part, efficient algorithms for placing popular content in a network that deploys a distributed system of caches are provided. Then, the Index Coding problem is considered: every user has its own cache content that is given and transmissions on a shared link are to be optimized. All graph theoretic schemes for Index Coding, known prior to this work, are shown to perform within a constant factor from the one based on graph coloring. Then, `partial' flow-cut gap results for information flow in a multi-terminal network are obtained by leveraging Index Coding ideas. This provides a poly-logarithmic approximation for a known generalization of multi-cut. Finally, optimal cache design in Index Coding for an adversarial demand pattern is considered. Near-optimal algorithms for cache design and delivery within a broad class of schemes are presented. In the second part, sample complexity lower bounds considering average error for learning random Ising Graphical Models, sampled from Erdós-Rényi ensembles, are obtained. Then, the number of bounded interventions required to learn a network of causal relationships under the Pearls model is studied. Upper and lower bounds on the number of size bounded interventions required for various classes of graphs are obtained.Item Greedy structure learning of Markov Random Fields(2011-08) Johnson, Christopher Carroll; Ravikumar, Pradeep; Dhillon, InderjitProbabilistic graphical models are used in a variety of domains to capture and represent general dependencies in joint probability distributions. In this document we examine the problem of learning the structure of an undirected graphical model, also called a Markov Random Field (MRF), given a set of independent and identically distributed (i.i.d.) samples. Specifically, we introduce an adaptive forward-backward greedy algorithm for learning the structure of a discrete, pairwise MRF given a high dimensional set of i.i.d. samples. The algorithm works by greedily estimating the neighborhood of each node independently through a series of forward and backward steps. By imposing a restricted strong convexity condition on the structure of the learned graph we show that the structure can be fully learned with high probability given $n=\Omega(d\log (p))$ samples where $d$ is the dimension of the graph and $p$ is the number of nodes. This is a significant improvement over existing convex-optimization based algorithms that require a sample complexity of $n=\Omega(d^2\log(p))$ and a stronger irrepresentability condition. We further support these claims with an empirical comparison of the greedy algorithm to node-wise $\ell_1$-regularized logistic regression as well as provide a real data analysis of the greedy algorithm using the Audioscrobbler music listener dataset. The results of this document provide an additional representation of work submitted by A. Jalali, C. Johnson, and P. Ravikumar to NIPS 2011.Item High-dimensional statistics : model specification and elementary estimators(2014-12) Yang, Eunho; Ravikumar, PradeepModern statistics typically deals with complex data, in particular where the ambient dimension of the problem p may be of the same order as, or even substantially larger than, the sample size n. It has now become well understood that even in this type of high-dimensional scaling, statistically consistent estimators can be achieved provided one imposes structural constraints on the statistical models. In spite of great success over the last few decades, we are still experiencing bottlenecks of two distinct kinds: (I) in multivariate modeling, data modeling assumption is typically limited to instances such as Gaussian or Ising models, and hence handling varied types of random variables is still restricted, and (II) in terms of computation, learning or estimation process is not efficient especially when p is extremely large, since in the current paradigm for high-dimensional statistics, regularization terms induce non-differentiable optimization problems, which do not have closed-form solutions in general. The thesis addresses these two distinct but highly complementary problems: (I) statistical model specification beyond the standard Gaussian or Ising models for data of varied types, and (II) computationally efficient elementary estimators for high-dimensional statistical models.Item Multi-scale error-correcting codes and their decoding using belief propagation(2014-05) Yoo, Yong Seok; Fiete, Ila; Vishwanath, SriramThis work is motivated from error-correcting codes in the brain. To counteract the effect of representation noise, a large number of neurons participate in encoding even low-dimensional variables. In many brain areas, the mean firing rates of neurons as a function of represented variable, called the tuning curve, have unimodal shape centered at different values, defining a unary code. This dissertation focuses on a new type of neural code where neurons have periodic tuning curves, with a diversity of periods. Neurons that exhibit this tuning are grid cells of the entorhinal cortex, which represent self-location in two-dimensional space. First, we investigate mutual information between such multi-scale codes and the coded variable as a function of tuning curve width. For decoding, we consider maximum likelihood (ML) and plausible neural network (NN) based models. For unary neural codes, Fisher information increases with narrower tuning, regardless of the decoding method. By contrast, for the multi-scale neural code, the optimal tuning curve width depends on the decoding method. While narrow tuning is optimal for ML decoding, a finite width, matched to statistics of the noise, is optimal with a NN decoder. This finding may explain why actual neural tuning curves have relatively wide tuning. Next, motivated by the observation that multi-scale codes involve non-trivial decoding, we examine a decoding algorithm based on belief propagation (BP) because BP promises certain gains in decoding efficiency. The decoding problem is first formulated as a subset selection problem on a graph and then approximately solved by BP. Even though the graph has many cycles, BP converges to a fixed point after few iterations. The mean square error of BP approaches to that of ML at high signal-to-noise ratios. Finally, using the multi-scale code, we propose a joint source-channel coding scheme that allows separate senders to transmit complementary information over additive Gaussian noise channels without cooperation. The receiver decodes one sender's codeword using the other as side information and achieves a lower distortion using the same number of transmissions. The proposed scheme offers a new framework to design distributed joint source-channel codes for continuous variables.Item On a class of distributed algorithms over networks and graphs(2011-05) Lee, Sang Hyun, 1977-; Vishwanath, Sriram; Vikalo, Haris; Powers, Edward J.; Ghosh, Joydeep; Sanghavi, Sujay; Qiu, LiliDistributed iterative algorithms are of great importance, as they are known to provide low-complexity and approximate solutions to what are otherwise high-dimensional intractable optimization problems. The theory of message-passing based algorithms is fairly well developed in the coding, machine learning and statistical physics literatures. Even though several applications of message-passing algorithms have already been identified, this work aims at establishing that a plethora of other applications exist where it can be of great importance. In particular, the goal of this work is to develop and demonstrate applications of this class of algorithms in network communications and computational biology. In the domain of communications, message-passing based algorithms provide distributed ways of inferring the optimal solution without the aid of a central agent for various optimization problems that happen in the resource allocation of communication networks. Our main framework is Affinity Propagation (AP), originally developed for clustering problems. We reinterpret this framework to unify the development of distributed algorithms for discrete resource allocation problems. Also, we consider a network-coded communication network, where continuous rate allocation is studied. We formulate an optimization problem with a linear cost function, and then utilize a Belief Propagation (BP) approach to determine a decentralized rate allocation strategy. Next, we move to the domain of computational biology, where graphical representations and computational biology play a major role. First, we consider the motif finding problem with several DNA sequences. In effect, this is a sequence matching problem, which can be modeled using various graphical representations and also solved using low-complexity algorithms based on message-passing techniques. In addition, we address the application of message-passing algorithms for a DNA sequencing problem where the one dimensional structure of a single DNA sequence is identified. We reinterpret the problem as being equivalent to the decoding of a nonlinear code. Based on the iterative decoding framework, we develop an appropriate graphical model which enables us to derive a message-passing algorithm to improve the performance of the DNA sequencing problem. Although this work consists of disparate application domains of communications, networks and computational biology, graphical models and distributed message-passing algorithms form a common underlying theme.