Heavy-Tailed Analogues of the Covariance Matrix for ICA

Independent Component Analysis (ICA) is the problem of learning a square matrix A, given samples of X=AS, where S is a random vector with independent coordinates. Most existing algorithms are provably efficient only when each S_i has finite and moderately valued fourth moment. However, there are practical applications where this assumption need not be true, such as speech and finance. Algorithms have been proposed for heavy-tailed ICA, but they are not practical, using random walks and the full power of the ellipsoid algorithm multiple times. The main contributions of this paper are: (1) A practical algorithm for heavy-tailed ICA that we call HTICA. We provide theoretical guarantees and show that it outperforms other algorithms in some heavy-tailed regimes, both on real and synthetic data. Like the current state-of-the-art, the new algorithm is based on the centroid body (a first moment analogue of the covariance matrix). Unlike the state-of-the-art, our algorithm is practically efficient. To achieve this, we use explicit analytic representations of the centroid body, which bypasses the use of the ellipsoid method and random walks. (2) We study how heavy tails affect different ICA algorithms, including HTICA. Somewhat surprisingly, we show that some algorithms that use the covariance matrix or higher moments can successfully solve a range of ICA instances with infinite second moment. We study this theoretically and experimentally, with both synthetic and real-world heavy-tailed data.

Large-Scale Stochastic Learning using GPUs

In this work we propose an accelerated stochastic learning system for very large-scale applications. Acceleration is achieved by mapping the training algorithm onto massively parallel processors: we demonstrate a parallel, asynchronous GPU implementation of the widely used stochastic coordinate descent/ascent algorithm that can provide up to 35x speed-up over a sequential CPU implementation. In order to train on very large datasets that do not fit inside the memory of a single GPU, we then consider techniques for distributed stochastic learning. We propose a novel method for optimally aggregating model updates from worker nodes when the training data is distributed either by example or by feature. Using this technique, we demonstrate that one can scale out stochastic learning across up to 8 worker nodes without any significant loss of training time. Finally, we combine GPU acceleration with the optimized distributed method to train on a dataset consisting of 200 million training examples and 75 million features. We show by scaling out across 4 GPUs, one can attain a high degree of training accuracy in around 4 seconds: a 20x speed-up in training time compared to a multi-threaded, distributed implementation across 4 CPUs.

Detecting causal associations in large nonlinear time series datasets

Detecting causal associations in time series datasets is a key challenge for novel insights into complex dynamical systems such as the Earth system or the human brain. Interactions in high-dimensional dynamical systems often involve time-delays, nonlinearity, and strong autocorrelations. These present major challenges for causal discovery techniques such as Granger causality leading to low detection power, biases, and unreliable hypothesis tests. Here we introduce a reliable and fast method that outperforms current approaches in detection power and scales up to high-dimensional datasets. It overcomes detection biases, especially when strong autocorrelations are present, and allows ranking associations in large-scale analyses by their causal strength. We provide mathematical proofs, evaluate our method in extensive numerical experiments, and illustrate its capabilities in a large-scale analysis of the global surface-pressure system where we unravel spurious associations and find several potentially causal links that are difficult to detect with standard methods. The broadly applicable method promises to discover novel causal insights also in many other fields of science.

Feature Generation for Robust Semantic Role Labeling

Hand-engineered feature sets are a well understood method for creating robust NLP models, but they require a lot of expertise and effort to create. In this work we describe how to automatically generate rich feature sets from simple units called featlets, requiring less engineering. Using information gain to guide the generation process, we train models which rival the state of the art on two standard Semantic Role Labeling datasets with almost no task or linguistic insight.

Social Big Data Analytics of Consumer Choices: A Two Sided Online Platform Perspective

This dissertation examines three distinct big data analytics problems related to the social aspects of consumers’ choices. The main goal of this line of research is to help two sided platform firms to target their marketing policies given the great heterogeneity among their customers. In three essays, I combined structural modeling and machine learning approaches to first understand customers’ responses to intrinsic and extrinsic factors, using unique data sets I scraped from the web, and then explore methods to optimize two sided platforms’ firms’ reactions accordingly. The first essay examines ‘social learning’ in the mobile app store context, controlling for intrinsic value of hedonic and utilitarian mobile apps, price, advertising, and number of options available. The second essay investigates bidders’ anticipated winner and loser regret in the context of the eBay online auction platform. Using a large data set from eBay and empirical Bayesian estimation method, I quantify the bidders’ anticipation of regret in various product categories, and investigate the role of experience in explaining the bidders’ regret and learning behaviors. The third essay investigates the effects of Gamification incentive mechanisms in an online platform for user generated content. I use an ensemble method over LDA, mixed normal and k-mean clustering methods to segment users into competitors, collaborators, achievers, explorers and uninterested users. These findings help the Gamification platform to target its users. The simulation counterfactual analysis suggests that a two sided platform can increase the number of user contributions, by making earning badges more difficult.

BigVAR: Tools for Modeling Sparse High-Dimensional Multivariate Time Series

The R package BigVAR allows for the simultaneous estimation of high-dimensional time series by applying structured penalties to the conventional vector autoregression (VAR) and vector autoregression with exogenous variables (VARX) frameworks. Our methods can be utilized in many forecasting applications that make use of time-dependent data such as macroeconomics, finance, and internet traffic. Our package extends solution algorithms from the machine learning and signal processing literatures to a time dependent setting: selecting the regularization parameter by sequential cross validation and provides substantial improvements in forecasting performance over conventional methods. We offer a user-friendly interface that utilizes R’s s4 object class structure which makes our methodology easily accessible to practicioners. In this paper, we present an overview of our notation, the models that comprise BigVAR, and the functionality of our package with a detailed example using publicly available macroeconomic data. In addition, we present a simulation study comparing the performance of several procedures that refit the support selected by a BigVAR procedure according to several variants of least squares and conclude that refitting generally degrades forecast performance.

Automatic Representation for Lifetime Value Recommender Systems

Many modern commercial sites employ recommender systems to propose relevant content to users. While most systems are focused on maximizing the immediate gain (clicks, purchases or ratings), a better notion of success would be the lifetime value (LTV) of the user-system interaction. The LTV approach considers the future implications of the item recommendation, and seeks to maximize the cumulative gain over time. The Reinforcement Learning (RL) framework is the standard formulation for optimizing cumulative successes over time. However, RL is rarely used in practice due to its associated representation, optimization and validation techniques which can be complex. In this paper we propose a new architecture for combining RL with recommendation systems which obviates the need for hand-tuned features, thus automating the state-space representation construction process. We analyze the practical difficulties in this formulation and test our solutions on batch off-line real-world recommendation data.

Stability of Topic Modeling via Matrix Factorization

Topic models can provide us with an insight into the underlying latent structure of a large corpus of documents. A range of methods have been proposed in the literature, including probabilistic topic models and techniques based on matrix factorization. However, in both cases, standard implementations rely on stochastic elements in their initialization phase, which can potentially lead to different results being generated on the same corpus when using the same parameter values. This corresponds to the concept of ‘instability’ which has previously been studied in the context of k-means clustering. In many applications of topic modeling, this problem of instability is not considered and topic models are treated as being definitive, even though the results may change considerably if the initialization process is altered. In this paper we demonstrate the inherent instability of popular topic modeling approaches, using a number of new measures to assess stability. To address this issue in the context of matrix factorization for topic modeling, we propose the use of ensemble learning strategies. Based on experiments performed on annotated text corpora, we show that a K-Fold ensemble strategy, combining both ensembles and structured initialization, can significantly reduce instability, while simultaneously yielding more accurate topic models.

Spectral Clustering using PCKID – A Probabilistic Cluster Kernel for Incomplete Data

In this paper, we propose PCKID, a novel, robust, kernel function for spectral clustering, specifically designed to handle incomplete data. By combining posterior distributions of Gaussian Mixture Models for incomplete data on different scales, we are able to learn a kernel for incomplete data that does not depend on any critical hyperparameters, unlike the commonly used RBF kernel. To evaluate our method, we perform experiments on two real datasets. PCKID outperforms the baseline methods for all fractions of missing values and in some cases outperforms the baseline methods with up to 25 percentage points.

Ontologies in System Engineering: a Field Report

In recent years ontologies enjoyed a growing popularity outside specialized AI communities. System engineering is no exception to this trend, with ontologies being proposed as a basis for several tasks in complex industrial implements, including system design, monitoring and diagnosis. In this paper, we consider four different contributions to system engineering wherein ontologies are instrumental to provide enhancements over traditional ad-hoc techniques. For each application, we briefly report the methodologies, the tools and the results obtained with the goal to provide an assessment of merits and limits of ontologies in such domains.

Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm

Learning rates for regularized least-squares algorithms are in most cases expressed with respect to the excess risk, or equivalently, the L_2-norm. For some applications, however, guarantees with respect to stronger norms such as the L_\infty-norm, are desirable. We address this problem by establishing learning rates for a continuous scale of norms between the L_2– and the RKHS norm. As a byproduct we derive L_\infty-norm learning rates, and in the case of Sobolev RKHSs we actually obtain Sobolev norm learning rates, which may also imply L_\infty-norm rates for some derivatives. In all cases, we do not need to assume the target function to be contained in the used RKHS. Finally, we show that in many cases the derived rates are minimax optimal.

Online Multiclass Boosting

Recent work has extended the theoretical analysis of boosting algorithms to multiclass problems and online settings. However, the multiclass extension is in the batch setting and the online extensions only consider binary classification. To the best of our knowledge, there exists no framework to analyze online boosting algorithms for multiclass classification. We fill this gap in the literature by defining, and justifying, a weak learning condition for online multiclass boosting. We also provide an algorithm called online multiclass boost-by-majority to optimally combine weak learners in our setting.

Approximating Unique Games Using Low Diameter Graph Decomposition

A Realistic Dataset for the Smart Home Device Scheduling Problem for DCOPs

Online Ranking with Constraints: A Primal-Dual Algorithm and Applications to Web Traffic-Shaping

Approximations of the Restless Bandit Problem

Lollipop and lariat symmetric functions

High dimensional deformed rectangle matrices with applications in matrix denoising

On Polynomial Time Methods for Exact Low Rank Tensor Completion

Rank conditional coverage and confidence intervals in high dimensional problems

Generalized Pareto Processes and Liquidity

Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness

Pretty good state transfer in graphs with an involution

Theoretical and Experimental Analysis of the Canadian Traveler Problem

Breaking the Bonds of Submodularity: Empirical Estimation of Approximation Ratios for Monotone Non-Submodular Greedy Maximization

Synthesising Dynamic Textures using Convolutional Neural Networks

The Impact of Confounder Selection in Propensity Scores for Rare Events Data – with Applications to Birth Defects

N-body localization for the Anderson model with strongly mixing correlated random potentials

Learning Hawkes Processes from Short Doubly-Censored Event Sequences

Unsupervised Learning of Morphological Forests

CT Image Denoising with Perceptive Deep Neural Networks

One Size Fits Many: Column Bundle for Multi-X Learning

Existence of Noise Induced Order, a Computer Aided Proof

Increasing Deep Learning Melanoma Classification by Classical And Expert Knowledge Based Image Transforms

Moments of 2D Parabolic Anderson Model

Nonparametric Inference via Bootstrapping the Debiased Estimator

On the ability of neural nets to express distributions

Proactive Resource Management in LTE-U Systems: A Deep Learning Perspective

On the Complexity of Bundle-Pricing and Simple Mechanisms

Modulo Orientations with Bounded Out-Degrees and Modulo Factors with Bounded Degrees

QRT maps and related Laurent systems

Learning Chained Deep Features and Classifiers for Cascade in Object Detection

Almost Sure Invariance Principle for non-autonomous holomorphic dynamics in $\Bbb{P}^k$

Conic divisorial ideals of Hibi rings and their applications to non-commutative crepant resolutions

Robust and fully automated segmentation of mandible from CT scans

Stochastic complex Ginzburg-Landau equation with space-time white noise

Learning Model Predictive Control for Iterative Tasks: A Computationally Efficient Approach for Linear System

A Unified Parallel Algorithm for Regularized Group PLS Scalable to Big Data

The Sprague-Grundy function for some nearly disjunctive sums of Nim and Silver Dollar games

Pronunciation recognition of English phonemes /\textipa{@}/, /æ/, /\textipa{A}:/ and /\textipa{2}/ using Formants and Mel Frequency Cepstral Coefficients

DyAdHyTM: A Low Overhead Dynamically Adaptive Hybrid Transactional Memory on Big Data Graphs

Distributions and Statistical Power of Optimal Signal-Detection Methods In Finite Cases

Scalable Inference for Nested Chinese Restaurant Process Topic Models

A Nonparametric Bayesian Approach to Copula Estimation

A Neural Attention Model for Categorizing Patient Safety Events

Sparse Solutions of an Undetermined Linear System

Bidirectional Backpropagation: Towards Biologically Plausible Error Signal Transmission in Neural Networks

Matrix product ensembles of Hermite-type

Discriminating Traces with Time

More efficient formulas for efficiency correction of cumulants and effect of using averaged efficiency

Multiuser Millimeter Wave Beamforming Strategies with Quantized and Statistical CSIT

Design of a Cognitive VLC Network with Illumination and Handover Requirements

LTSG: Latent Topical Skip-Gram for Mutually Learning Topic Model and Vector Representations

Warped metrics for location-scale models

Joint Planning of PEV Fast-Charging Network and Distributed PV Generation

Consistent On-Line Off-Policy Evaluation

The Facets of the Bases Polytope of a Matroid and Two Consequences

Diverse Weighted Bipartite b-Matching

Imprecise Continuous-Time Markov Chains: Efficient Computational Methods with Guaranteed Error Bounds

On measures of edge-uncolorability of cubic graphs: A brief survey and some new results

Space-Time Channel Modulation

Dimers, crystals and quantum Kostka numbers

A DIKW Paradigm to Cognitive Engineering

Robust Hedging of Options on a Leveraged Exchange Traded Fund

Tight Bounds for Online Coloring of Basic Graph Classes

Discretisation and Duality of Optimal Skorokhod Embedding Problems

The method of weighted words revisited

Inductive tools for connected ribbon graphs, delta-matroids and multimatroids

Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good

Massive MIMO 5G Cellular Networks: mm-wave vs. μ-wave Frequencies

Stationary patterns in star networks of bistable units: Theory and application to chemical reactions

Analyzing Learned Convnet Features with Dirichlet Process Gaussian Mixture Models

ViP-CNN: A Visual Phrase Reasoning Convolutional Neural Network for Visual Relationship Detection

First Experiences Optimizing Smith-Waterman on Intel’s Knights Landing Processor

Preconditioning ideas for the Augmented Lagrangian method

Convergence acceleration of alternating series

Utilizing Lexical Similarity for pivot translation involving resource-poor, related languages

Massive MIMO Pilot Decontamination and Channel Interpolation via Wideband Sparse Channel Estimation

A minimax and asymptotically optimal algorithm for stochastic bandits

Synchronizability of Communicating Finite State Machines is not Decidable

Slow to fast infinitely extended reservoirs for the symmetric exclusion process with long jumps

Duality functions and stationary product measures

Generalizations of Capparelli’s identity

Non-commutative rational function in strongly convergent random variables

Mixed Cages

Tempered fractional Brownian and stable motions of second kind

Exit problems for general draw-down times of spectrally negative Lévy processes

A Novel Index Coding Scheme and its Application to Coded Caching

Particle Filters for Partially-Observed Boolean Dynamical Systems

Controllability and optimal control of the transport equation with a localized vector field

Rotting Bandits

A Probabilistic Framework for Location Inference from Social Media

Non-penalized variable selection in high-dimensional linear model settings via generalized fiducial inference

Are Emojis Predictable?

Network Construction with Ordered Constraints

Self-similar solutions of fragmentation equations revisited

How to Optimally Allocate Resources for Coded Distributed Computing?

Two-Moment Inequalities for Rényi Entropy and Mutual Information

Conflict diagnostics for evidence synthesis in a multiple testing framework

Causal Discovery Using Proxy Variables

Simple groups, product actions, and generalised quadrangles

Bounding the inefficiency of compromise

ERA: A Framework for Economic Resource Allocation for the Cloud

Minimal length maximal green sequences

Koszul binomial edge ideals of pairs of graphs

Learning to Draw Dynamic Agent Goals with Generative Adversarial Networks

On the convex infimum convolution inequality with optimal cost function

Rigid stationary determinantal processes in non-Archimedean fields

Inherent Biases of Recurrent Neural Networks for Phonological Assimilation and Dissimilation

Achieving rental harmony with a secretive roommate

Time-Series Adaptive Estimation of Vaccination Uptake Using Web Search Queries

k-Means Clustering and Ensemble of Regressions: An Algorithm for the ISIC 2017 Skin Lesion Segmentation Challenge

Light Microscopy at Maximal Precision

A Converse to Banach’s Fixed Point Theorem and its CLS Completeness

On the inducibility of cycles