Fall 2016

  • 09/16/2016
    • Speaker: Natali Ruchansky
    • Title: Learn to query and query to learn.
    • Abstract:  
      • Working with data has never been easy: Sharing economy platforms wish to make product recommendations to users, but their data is incomplete. Biologists have large interesting protein-protein interaction networks, but they don't know how to extract useful insight from them. The above examples can be viewed as the interplay between two components: the data and the inference process. In the case of Netflix the latter is known and algorithms are needed to infer the missing data; I will call this Learning to Query. In the biology example the data is readily available and an algorithm is needed to query the graph for discoveries; I will call this Querying to Learn. In my work I addressed these two converse problems and proposed simple, but effective algorithms to solve them. In this talk 
      • I will first present my work on the Learning to Query problem through the lens of matrix completion. I will discuss the new problem of Active Matrix Completion which asks to first analyzes the quality of the available data, such as movie ratings on Netflix, then perform the completion and inference, or movie recommendation.  I will then present a new algorithm called Order&Extend that tackles the Active Completion problem.  By framing the problem in terms of linear systems, Order&Extend identifies which portions of the data do or do not have enough information, suggests how the data can be augmented, and finally produces a completion. 
      • In the second half of my talk I will present my work on the Querying to Learn through the lens of graph mining. Here there is a data set available, and in particular there are some query-nodes of interest;  the biologists have a protein-protein-interaction network and wish to study the interactions between three particular proteins.  I will present the new notion of a Wiener-Connector that isolates interesting connections among the query-nodes by utilizing the simple relationship of shortest paths.  I will then discuss the algorithm for finding the Wiener-Connector along with its applicability and utility, for example, in identifying possible protein-disease associations and providing outputs that are easy to interpret and visualize, making it useful across different domains.
  • 09/30/2016
    • We will not have machine learning lunch this week due to the ML retreat on Friday.
  • 10/14/2016
    • Speaker: Xinran He
    • Title: Learning Influence Functions from Incomplete Observations.
    • Abstract:  We study the problem of learning influence functions under incomplete observations of node activations. Incomplete observations are a major concern as most (online and real-world) social networks are not fully observable. We establish both proper and improper PAC learnability of influence functions under uniformly randomly missing observations. Proper PAC learnability under the Discrete-Time Linear Threshold (DLT) and Discrete-Time Independent Cascade (DIC) models is established by essentially reducing incomplete observations to complete observations in a modified graph. Our improper PAC learnability result applies for the DLT and DIC models as well as the Continuous-Time Independent Cascade (CIC) model. It is based on a parametrization in terms of reachability features, and also gives rise to an efficient and practical heuristic. Experiments on synthetic and real-world datasets demonstrate the ability of our method to compensate even for fairly large loss rates.
  • 10/28/2016
    • Speaker: Dehua Cheng
    • Title: SPALS: Fast Alternating Least Squares via Implicit Leverage Scores Sampling.
    • Abstract:  Tensor CANDECOMP/PARAFAC (CP) decomposition is a powerful but computationally challenging tool in modern data analytics. In this talk, I will present the sparse alternating least squares (SPALS) method. It samples intermediate steps of alternating minimization algorithms for computing low rank tensor CP decompositions. Specifically, we sample the Khatri-Rao product, which arises as an intermediate object during the iterations of alternating least squares. This product captures the interactions between different tensor modes, and form the main computational bottleneck for solving many tensor related tasks. By exploiting the spectral structures of the matrix Khatri-Rao product, we provide efficient access to its statistical leverage scores. When applied to the tensor CP decomposition, our method leads to the first algorithm that runs in sublinear time per-iteration and approximates the output of deterministic alternating least squares algorithms. Empirical evaluations of this approach show significant speedups over existing randomized and deterministic routines for performing CP decomposition. This is joint work with Richard Peng (Gatech), Ioakeim Perros (Gatech), and Yan Liu.
  • 11/11/2016
    • Speaker: Chao-Kai Chiang
    • Title: Multi-armed bandit problems and its variants.
    • Abstract:  We will review the basic definition of multi-armed bandits. Variants of the MAB and recent progress will be covered as well.
  • 12/02/2016
    • Speaker: Shuyang Gao
    • Title: Mutual information estimation and its application on feature selection.
    • Abstract:  Mutual information is a fundamental measure of dependence between random variables. We demonstrate that a popular class of nonparametric mutual information estimators perform very poorly for strongly dependent variables and have sample complexity that scales exponentially with the true mutual information. This undesired behavior is due to their implicit reliance on local uniformity of the underlying joint distribution. We introduce new mutual information estimators to solve this problem and show that our methods have superior performance compared to several baselines. In the second part of the talk, we focus on the feature selection problem. An extensive body of work on feature selection exists which is based on maximizing mutual information between subsets of features and class labels. But owing to the difficulty of estimating mutual information in high dimensions, most of these methods are based on lower-order approximations which are heuristic in nature. We introduce a novel feature selection method based on variational mutual information lower bound.  With proper choice of tractable variational distributions, we demonstrate our method is optimal under tree graphical models and show the proposed method outperforms state-of-the-art mutual information feature selection methods across a variety of datasets. This is joint work with Greg Ver Steeg (USC/ISI) and Aram Galstyan (USC/ISI).
Comments