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.
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 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.