Browsing by Subject "Tensors"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Hypergraph Analytics: Modeling Higher-Order Structures And Probabilities
    (2020-05) Sharma, Ankit
    Data structured in the form of overlapping or non-overlapping sets are found in a variety of domains, sometimes explicitly but often subtly. For example, teams, which are of prime importance in industry and social science studies are “sets of individuals”; “item sets” in pattern mining of customer transactions are sets, and for various types of analysis in language studies a sentence can be considered as a “set or bag of words”. Although building models and inference algorithms for structured data has been an essential task in the fields of machine learning and statistics, research on “set-like” data remains less explored. Relationships between pairs of elements can be modeled as edges in a graph. However, for modeling relationships that involve all members of a set, hyperedges in a Hypergraph are more natural representations. Hypergraphs are less known graph-theoretic structure as compared to graphs. Because of this popularity graphs have been employed prolifically to model data of all kinds. Little attention is given to the fact that whether the data is naturally being generated as dyadic interactions or not. We think that much data is even deliberately converted to a graph for the sake of fitting it into a graph-based model and destroying the precious information present when it was originally generated. This thesis describes analyzing complex group structured data from domains like social networks, customer transaction data, and general categorical data, via the lens of Hypergraphs. To do so, we propose the Hypergraph Analytics Framework, under which we shall be interested in three higher-level questions pertaining to the hypergraph modeling. Firstly, how to model higher-order hypergraph information and what kind of lower-order approximations are available or sufficient depending upon the problem at hand. This question is addressed across the thesis as we employ different hypergraph models contingent upon the problem at hand. Secondly, we shall be interested in understanding what kind of inferences are possible over the hypergraph structure and what kind of probabilities can be learned. For this, we shall be dissecting the problem of hypergraph inference into various hyperedge prediction sub-problems and developing inference methods for each of them. We develop inference methods for both cross-sectional analysis: when we ignore the time information about group interactions into account, as well as longitudinal analysis: where we leverage temporal data. We also develop separate methods for conducting inference over observed and unobserved regions of the hypergraph structure. This variety of inference mechanisms on hypergraph structure together constitute the first part of the thesis, which we refer to as the \textit{Spatial Analysis} within our Hypergraph Analytics framework. Lastly, we are interested in learning what kinds of compression algorithms are possible for hypergraphs and how effective these techniques are. Here we develop techniques to compress the hypergraph topology to lower-dimensional latent space. We shall be chiefly considering hyperedge compression or hyperedge embeddings. We examine two different embedding approaches. First, is an algebraic approach which leverages leverage the relationship between hypergraphs and symmetric higher-order tensors. Symmetric tensor decomposition techniques are then developed to learn embeddings. Second, is a neural networks based solution which employs auto-encoders regularized by hypergraph structure. Together, both these approaches constitute the second part of the thesis, which we refer to as \textit{Spectral Analysis} within the proposed Hypergraph Analytics framework.
  • Thumbnail Image
    Item
    Leveraging sparsity for genetic and wireless cognitive networks
    (2013-08) Bazerque, Juan Andres
    Sparse graphical models can capture uncertainty of interconnected systems while promoting parsimony and simplicity - two attributes that can be utilized to identify the topology and control processes defined on networks. This thesis advocates such models in the context of learning the structure of gene-regulatory networks, for which it is argued that single nucleotide polymorphisms can be seen as perturbation data that are critical to identify edge directionality. Applied to the immune-related gene network, these models facilitate the discovery of new regulation pathways. Learning gene-regulating interactions is critical not only to understand how cells differentiate and behave, but also to decipher mechanisms triggering diseases with a genetic component. The impact here is on the development of a new generation of drugs designed to target specific genes. In particular, the genetic interactions of an uncharacterized chemical compound are identified by comparing its effect on the fitness of Saccharomyces cerevisiae (yeast) to that of double-deletion knockouts. As drug targeting is limited by expensive and time-involving laboratory tests, a judicious design of experiments is instrumental in order to reduce the required number of diagnostic mutant strains. During in-vitro experiments with 82 test-drugs, an orderly data reduction of 30% was shown possible without altering the identification of the primary chemical-genetic interactions. Sparsity in wireless cognitive networks emerges due to the geographical distribution of sources, and also due to the scarcity of the radio frequency spectrum used for transmission. In this context, sparsity is leveraged for mapping the interference temperature across space while identifying unoccupied frequency bands. This is achieved by a novel so-terms nonparametric basis pursuit (NBP) method, which entails a basis expansion model with coefficients belonging to a function space. The spatial awareness markedly impacts spectral efficiency, especially when cognitive radios collaborate to reach consensus in a decentralized manner. Tested in a simulated communication setting, NBP captures successfully both shadowing as well as path-loss effects. In additional tests with real-field RF measurements, the spectrum maps reveal the frequency bands utilized for transmission and also reveal the position of the sources. Finally, a blind NBP alternative is introduced to yield a Bayesian nuclear-norm regularization approach for matrix completion. In this context, it becomes possible to incorporate prior covariance information which enables smoothing and prediction. Blind NBP can be further applied to impute missing entries of third- or higher-order data arrays (tensors). These attracted features of blind NBP are illustrated for network flow prediction and imputation of missing entries in three-way ribonucleic-acid (RNA) sequencing arrays and magnetic-resonance-imaging (MRI) tensors.
  • Thumbnail Image
    Item
    Symmetries of tensors
    (2009-09) Berget, Andrew Schaffer
    This thesis studies the symmetries of a fixed tensors by looking at certain group representations this tensor generates. We are particularly interested in the case that the tensor can be written as v 1 ⊗ · · · ⊗ v n , where the v i are selected from a complex vector space. The general linear group representation generated by such a tensor contains subtle information about the matroid M ( v ) of the vector configuration v 1 , · · ·, v n . To begin, we prove the basic results about representations of this form. We give two useful ways of describing these representations, one in terms of symmetric group representations, the other in terms of degeneracy loci over Grassmannians. Some of these results are equivalent to results that have appeared in the literature. When this is the case, we have given new, short proofs of the known results. We will prove that the multiplicities of hook shaped irreducibles in the representation generated by v 1 ⊗ · · · ⊗ v n are determined by the no broken circuit complex of M ( v ). To do this, we prove a much stronger result about the structure of vector subspace of Sym V spanned by the products Π i∈S v i , where S ranges over all subsets of [ n ]. The result states that this vector space has a direct sum decomposition that determines the Tutte polynomial of M ( v ). We will use a combinatorial basis of the vector space generated the products of the linear forms to completely describe the representation generated by a decomposable tensor when its matroid M ( v ) has rank two. Next we consider a representation of the symmetric group associated to every matroid. It is universal in the sense that if v 1 , . . . , v n is a realization of the matroid then the representation for the matroid provides non-trivial restrictions on the decomposition of the representation generated by the tensor product of the vectors. A complete combinatorial characterization of this representation is proven for parallel extensions of Schubert matroids. We also describe the multiplicity of hook shapes in this representation for all matroids. The contents of this thesis will always be freely available online in the most current version. Simply search for my name and the title of the thesis. Please do not ever pay for this document.