mtybilly/Instruct2DS huggingface dataset:
Methods of Moments for Learning Stochastic Languages: Unified Presentation and Empirical Comparison
Authors: Borja Balle, William Hamilton, Joelle Pineau
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Probabilistic latent-variable models are a powerful tool for modelling structured data.  However, traditional expectation-maximization methods of learning such models are both computationally expensive and prone to local-minima. In contrast to these traditional methods, recently developed learning algorithms based upon the method of moments are both computationally efficient and provide strong statistical guarantees.  In this work, we provide a unified presentation and empirical comparison of three general moment-based methods in the context of modelling stochastic languages. By rephrasing these methods upon a common theoretical ground, introducing novel theoretical results where necessary, we provide a clear comparison, making explicit the statistical assumptions upon which each method relies. With this theoretical grounding, we then provide an in-depth empirical analysis of the methods on both real and synthetic data with the goal of elucidating performance trends and highlighting important implementation details.
Effective Bayesian Modeling of Groups of Related Count Time Series
Authors: Nicolas Chapados
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Time series of counts arise in a variety of forecasting applications, for which traditional models are generally inappropriate. This paper introduces a hierarchical Bayesian formulation applicable to count time series that can easily account for explanatory variables and share statistical strength across groups of related time series. We derive an efficient approximate inference technique, and illustrate its performance on a number of datasets from supply chain planning.
Variational Inference for Sequential Distance Dependent Chinese Restaurant Process
Authors: Sergey Bartunov, Dmitry Vetrov
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Recently proposed distance dependent Chinese Restaurant Process (ddCRP) generalizes extensively used Chinese Restaurant Process (CRP) by accounting for dependencies between data points. Its posterior is intractable and so far only MCMC methods were used for inference. Because of very different nature of ddCRP no prior developments in variational methods for Bayesian nonparametrics are appliable. In this paper we propose novel variational inference for important sequential case of ddCRP (seqddCRP) by revealing its connection with Laplacian of random graph constructed by the process. We develop efficient algorithm for optimizing variational lower bound and demonstrate its efficiency comparing to Gibbs sampler. We also apply our variational approximation to CRP-equivalent seqddCRP-mixture model, where it could be considered as alternative to one based on truncated stick-breaking representation. This allowed us to achieve significantly better variational lower bound than variational approximation based on truncated stick breaking for Dirichlet process.
Discovering Latent Network Structure in Point Process Data
Authors: Scott Linderman, Ryan Adams
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Networks play a central role in modern data analysis, enabling us to reason about systems by studying the relationships between their parts.  Most often in network analysis, the edges are given.  However, in many systems it is difficult or impossible to measure the network directly.  Examples of latent networks include economic interactions linking financial instruments and patterns of reciprocity in gang violence.  In these cases, we are limited to noisy observations of events associated with each node.  To enable analysis of these implicit networks, we develop a probabilistic model that combines mutually-exciting point processes with random graph models.  We show how the Poisson superposition principle enables an elegant auxiliary variable formulation and a fully-Bayesian, parallel inference algorithm.  We evaluate this new model empirically on several datasets.
A Kernel Independence Test for Random Processes
Authors: Kacper Chwialkowski, Arthur Gretton
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: A non-parametric approach to the problem of testing the independence of two random processes is developed.  The test statistic is the Hilbert-Schmidt Independence Criterion (HSIC), which was used previously in testing independence for i.i.d. pairs of variables. The asymptotic behaviour of HSIC is established when computed from samples drawn from random processes. It is shown that earlier bootstrap procedures which worked in the i.i.d. case will fail for random processes, and an alternative consistent estimate of the p-values is proposed. Tests on artificial data and real-world forex data indicate that the new test procedure discovers dependence which is missed by linear approaches, while the earlier bootstrap procedure returns an elevated number of false positives.
Learning to Disentangle Factors of Variation with Manifold Interaction
Authors: Scott Reed, Kihyuk Sohn, Yuting Zhang, Honglak Lee
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Many latent factors of variation interact to generate sensory data; for example pose, morphology and expression in face images. We propose to learn manifold coordinates for the relevant factors of variation and to model their joint interaction. Most existing feature learning algorithms focus on a single task and extract features that are sensitive to the task-relevant factors and invariant to all others. However, models that just extract a single set of invariant features do not exploit the relationships among the latent factors. To address this we propose a higher-order Boltzmann machine that incorporates multiplicative interactions among groups of hidden units that each learn to encode a factor of variation. Furthermore, we propose a manifold-based training strategy that allows effective disentangling, meaning that units in each group encode a distinct type of variation. Our model achieves state-of-the-art emotion recognition and face verification performance on the Toronto Face Database, and we also demonstrate disentangled features learned on the CMU Multi-PIE dataset.
Learning Modular Structures from Network Data and Node Variables
Authors: Elham Azizi, Edoardo Airoldi, James Galagan
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: A standard technique for understanding underlying dependency structures among a set of variables posits a shared conditional probability distribution for the variables measured on individuals within a group. This approach is often referred to as module networks, where individuals are represented by nodes in a network, groups are termed modules, and the focus is on estimating the network structure among modules. However, estimation solely from node-specific variables can lead to spurious dependencies, and unverifiable structural assumptions are often used for regularization.  Here, we propose an extended model that leverages direct observations about the network in addition to node-specific variables. By integrating complementary data types, we avoid the need for structural assumptions. We illustrate theoretical and practical significance of the model and develop a reversible-jump MCMC learning procedure for learning modules and model parameters. We demonstrate the method accuracy in predicting modular structures from synthetic data and capability to learn regulatory modules in the  Mycobacterium tuberculosis gene regulatory network.
Probabilistic Partial Canonical Correlation Analysis
Authors: Yusuke Mukuta,  Harada
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Partial canonical correlation analysis (partial CCA) is a statistical method that estimates a pair of linear projections onto a low dimensional space, where the correlation between two multidimensional variables is maximized after eliminating the influence of a third variable. Partial CCA is known to be closely related to a causality measure between two time series. However, partial CCA requires the inverses of covariance matrices, so the calculation is not stable. This is particularly the case for high-dimensional data or small sample sizes. Additionally, we cannot estimate the optimal dimension of the subspace in the model. In this paper, we have addressed these problems by proposing a probabilistic interpretation of partial CCA and deriving a Bayesian estimation method based on the probabilistic model. Our numerical experiments demonstrated that our methods can stably estimate the model parameters, even in high dimensions or when there are a small number of samples.
Skip Context Tree Switching
Authors: Marc Bellemare, Joel Veness, Erik Talvitie
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Context Tree Weighting (CTW) is a powerful probabilistic sequence prediction technique that efficiently performs Bayesian model averaging over the class of all prediction suffix trees of bounded depth. In this paper we show how to generalize this technique to the class of K-skip prediction suffix trees. Contrary to regular prediction suffix trees, K-skip prediction suffix trees are permitted to ignore up to K contiguous portions of the context. This allows for significant improvements in predictive accuracy when irrelevant variables are present, a case which often occurs within record-aligned data and images. We provide a regret-based analysis of our approach, and empirically evaluate it on the Calgary corpus and a set of Atari 2600 screen prediction tasks.
Lower Bounds for the Gibbs Sampler over Mixtures of Gaussians
Authors: Christopher Tosh, Sanjoy Dasgupta
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: The mixing time of a Markov chain is the minimum time t necessary for the total variation distance between the distribution of the Markov chain’s current state X_t and its stationary distribution to fall below some ε> 0. In this paper, we present lower bounds for the mixing time of the Gibbs sampler over Gaussian mixture models with Dirichlet priors.
Marginalized Denoising Auto-encoders for Nonlinear Representations
Authors: Minmin Chen, Kilian Weinberger, Fei Sha, Yoshua Bengio
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Denoising auto-encoders (DAEs) have been successfully  used to learn new representations for a  wide range of machine learning tasks. During  training, DAEs make many passes over the training  dataset and reconstruct it from partial corruption  generated from a pre-specified corrupting  distribution. This process learns robust representation,  though at the expense of requiring many  training epochs, in which the data is explicitly  corrupted. In this paper we present the marginalized  Denoising Auto-encoder (mDAE), which  (approximately) marginalizes out the corruption  during training. Effectively, the mDAE takes  into account infinitely many corrupted copies of  the training data in every epoch, and therefore is  able to match or outperform the DAE with much  fewer training epochs. We analyze our proposed  algorithm and show that it can be understood as  a classic auto-encoder with a special form of regularization.  In empirical evaluations we show  that it attains 1-2 order-of-magnitude speedup in  training time over other competing approaches.
Gaussian Processes for Bayesian Estimation in Ordinary Differential Equations
Authors: David Barber, Yali Wang
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Bayesian parameter estimation in coupled ordinary differential equations (ODEs) is challenging due to the high computational cost of numerical integration. In gradient matching a separate data model is introduced with the property that its gradient can be calculated easily. Parameter estimation is achieved by requiring consistency between the gradients computed from the data model and those specified by the ODE. We propose a Gaussian process model that directly links state derivative information with system observations, simplifying previous approaches and providing a natural generative model.
Fast Multi-stage Submodular Maximization
Authors: Kai Wei, Rishabh Iyer, Jeff Bilmes
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We introduce a new multi-stage algorithmic framework for submodular maximization. We are motivated by extremely large scale machine learning problems, where both storing the whole data for function evaluation and running the standard accelerated greedy algorithm are prohibitive. We propose a multi-stage framework (called MultGreed), where at each stage we apply an approximate greedy procedure to maximize surrogate submodular functions. The surrogates serve as proxies for a target submodular function but require less memory and are easy to evaluate. We theoretically analyze the performance guarantee of the multi-stage framework, and give examples on how to design instances of MultGreed for a broad range of natural submodular functions. We show that MultGreed  performs very close to the standard greedy algorithm, given appropriate surrogate functions, and argue how our framework can easily be integrated with distributive algorithms for optimization. We complement our theory by empirically evaluating on several real world problems, including data subset selection on millions of speech samples, where MultGreed yields at least a thousand times speedup and superior results over the state-of-the-art selection methods.
Programming by Feedback
Authors: Marc Schoenauer, Riad Akrour, Michele Sebag, Jean-Christophe Souplet
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: This paper advocates a new ML-based programming framework, called Programming by Feedback (PF), which involves a sequence of interactions between the active computer and the user. The latter only provides preference judgments on pairs of solutions supplied by the active computer. The active computer involves two components: the learning component estimates the user’s utility function and accounts for the user’s  (possibly limited) competence; the optimization component explores the search space and returns the most appropriate candidate solution. A proof of principle of the approach is proposed, showing that PF requires a handful of interactions in order to solve some discrete and continuous benchmark problems.
Probabilistic Matrix Factorization with Non-random Missing Data
Authors: Jose Miguel Hernandez-Lobato, Neil Houlsby, Zoubin Ghahramani
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We propose a probabilistic matrix factorization model for collaborative  filtering that learns from data that is missing not at random(MNAR). Matrix factorization models exhibit state-of-the-art predictive performance in collaborative filtering. However, these models usually assume that the data is missing at random (MAR), and this is rarely the case. For example, the data is not MAR if users rate items they like more than ones they dislike. When the MAR assumption is incorrect, inferences are biased and predictive performance can suffer. Therefore, we model both the generative process for the data and the missing data mechanism. By learning these two models jointly we obtain improved performance over state-of-the-art methods when predicting the ratings and when modeling the data observation process. We present the first viable MF model for MNAR data. Our results are promising and we expect that further research on NMAR models will yield large gains in collaborative  filtering.
Pursuit-Evasion Without Regret, with an Application to Trading
Authors: Lili Dworkin, Michael Kearns, Yuriy Nevmyvaka
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We propose a state-based variant of the classical online learning problem of tracking the best expert. In our setting, the actions of the algorithm and experts correspond to local moves through a continuous and bounded state space. At each step, Nature chooses payoffs as a function of each player’s current position and action. Our model therefore integrates the problem of prediction with expert advice with the stateful formalisms of reinforcement learning. Traditional no-regret learning approaches no longer apply, but we propose a simple algorithm that provably achieves no-regret when the state space is any convex Euclidean region. Our algorithm combines techniques from online learning with results from the literature on pursuit-evasion games. We describe a quantitative trading application in which the convex region captures inventory risk constraints, and local moves limit market impact. Using historical market data, we show experimentally that our algorithm has a strong advantage over classic no-regret approaches.
The f-Adjusted Graph Laplacian: a Diagonal Modification with a Geometric Interpretation
Authors: Sven Kurras, Ulrike Luxburg, Gilles Blanchard
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Consider a neighborhood graph, for example a k-nearest neighbor graph, that is constructed on sample points drawn according to some density p. Our goal is to re-weight the graph’s edges such that all cuts and volumes behave as if the graph was built on a different sample drawn from an alternative density q. We introduce the f-adjusted graph and prove that it provides the correct cuts and volumes as the sample size tends to infinity. From an algebraic perspective, we show that its normalized Laplacian, denoted as the f-adjusted Laplacian, represents a natural family of diagonal perturbations of the original normalized Laplacian. Our technique allows to apply any cut and volume based algorithm to the f-adjusted graph, for example spectral clustering, in order to study the given graph as if it were built on an unaccessible sample from a different density. We point out applications in sample bias correction, data uniformization, and multi-scale analysis of graphs.
Riemannian Pursuit for Big Matrix Recovery
Authors: Mingkui Tan, Ivor W. Tsang, Li Wang, Bart Vandereycken, Sinno Jialin Pan
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Low rank matrix recovery is a fundamental task in many real-world  applications. The performance of existing methods, however,   deteriorates significantly when applied to ill-conditioned or large-scale matrices.  In this paper, we therefore propose an efficient method, called  Riemannian Pursuit (RP), that aims to address these two problems  simultaneously. Our method consists of a sequence of fixed-rank  optimization problems. Each subproblem, solved by a nonlinear  Riemannian conjugate gradient method, aims to correct the solution  in the most important subspace of increasing size.   Theoretically, RP converges linearly under mild conditions and  experimental results show that it substantially outperforms existing  methods when applied to   large-scale and ill-conditioned matrices.
Dynamic Programming Boosting for Discriminative Macro-Action Discovery
Authors: Leonidas Lefakis, Francois Fleuret
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We consider the problem of automatic macro-action discovery in imitation learning, which we cast as one of change-point detection. Unlike prior work in change-point detection, the present work leverages discriminative learning algorithms. Our main contribution is a novel supervised learning algorithm which extends the classical Boosting framework by combining it with dynamic programming. The resulting process alternatively improves the performance of individual strong predictors and the estimated change-points in the training sequence. Empirical evaluation is presented for the proposed method on tasks where change-points arise naturally as part of a classification problem. Finally we show the applicability of the algorithm to macro-action discovery in imitation learning and demonstrate it allows us to solve complex image-based goal-planning problems with thousands of features.
Online Stochastic Optimization  under Correlated Bandit Feedback
Authors: Mohammad Gheshlaghi azar, Alessandro Lazaric, Emma Brunskill
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In this paper we consider the problem of online stochastic optimization of a locally smooth function under bandit feedback. We introduce the high-confidence tree (HCT) algorithm, a novel anytime \mathcal X-armed bandit algorithm, and derive regret bounds matching the performance of state-of-the-art algorithms in terms of the dependency on number of steps and the near-optimality dimension. The main advantage of HCT is that it handles the challenging case of correlated bandit feedback (reward), whereas existing methods require rewards to be conditionally independent. HCT also improves on the state-of-the-art in terms of the memory requirement, as well as requiring a weaker smoothness assumption on the mean-reward function in comparison with the existing anytime algorithms. Finally, we discuss how HCT can be applied to the problem of policy search in reinforcement learning and we report preliminary empirical results.
Weighted Graph Clustering with Non-Uniform Uncertainties
Authors: Yudong Chen, Shiau Hong Lim, Huan Xu
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We study the graph clustering problem where each observation (edge or no-edge between a pair of nodes) may have a different level of confidence/uncertainty. We propose a clustering algorithm that is based on optimizing an appropriate weighted objective, where larger weights are given to observations with lower uncertainty. Our approach leads to a convex optimization problem that is efficiently solvable. We analyze our approach under a natural generative model, and establish theoretical guarantees for recovering the underlying clusters. Our main result is a general theorem that applies to any given weight and distribution for the uncertainty. By optimizing over the weights, we derive a provably optimal weighting scheme, which matches the information theoretic lower bound up to logarithmic factors and leads to strong performance bounds in several specific settings. By optimizing over the uncertainty distribution, we show that non-uniform uncertainties can actually help. In particular, if the graph is built by spending a limited amount of resource to take measurement on each node pair, then it is beneficial to allocate the resource in a non-uniform fashion to obtain accurate measurements on a few pairs of nodes, rather than obtaining inaccurate measurements on many pairs. We provide simulation results that validate our theoretical findings.
GeNGA: A Generalization of Natural Gradient Ascent with Positive and Negative Convergence Results
Authors: Philip Thomas
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Natural gradient ascent (NGA) is a popular optimization method that uses a positive definite metric tensor. In many applications the metric tensor is only guaranteed to be positive semidefinite (e.g., when using the Fisher information matrix as the metric tensor), in which case NGA is not applicable. In our first contribution, we derive generalized natural gradient ascent (GeNGA), a generalization of NGA which allows for positive semidefinite non-smooth metric tensors. In our second contribution we show that, in standard settings, GeNGA and NGA can both be divergent. We then establish sufficient conditions to ensure that both achieve various forms of convergence. In our third contribution we show how several reinforcement learning methods that use NGA without positive definite metric tensors can be adapted to properly use GeNGA.
A Bayesian Framework for Online Classifier Ensemble
Authors: Qinxun Bai, Henry Lam, Stan Sclaroff
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We propose a Bayesian framework for recursively estimating the classifier weights in online learning of a classifier ensemble. In contrast with past methods, such as stochastic gradient descent or online boosting, our framework estimates the weights in terms of evolving posterior distributions. For a specified class of loss functions, we show that it is possible to formulate a suitably defined likelihood function and hence use the posterior distribution as an approximation to the global empirical loss minimizer. If the stream of training data is sampled from a stationary process, we can also show that our framework admits a superior rate of convergence to the expected loss minimizer than is possible with standard stochastic gradient descent. In experiments with real-world datasets, our formulation often performs better than online boosting algorithms.
Adaptivity and Optimism: An Improved Exponentiated Gradient Algorithm
Authors: Jacob Steinhardt, Percy Liang
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We present an adaptive variant of the exponentiated gradient algorithm. Leveraging the optimistic learning framework of Rakhlin & Sridharan (2012), we obtain regret bounds that in the learning from experts setting depend on the variance and path length of the best expert, improving on results by Hazan & Kale (2008) and Chiang et al. (2012), and resolving an open problem posed by Kale (2012). Our techniques naturally extend to matrix-valued loss functions, where we present an adaptive matrix exponentiated gradient algorithm. To obtain the optimal regret bound in the matrix case, we generalize the Follow-the-Regularized-Leader algorithm to vector-valued payoffs, which may be of independent interest.
Gaussian Approximation of Collective Graphical Models
Authors: Liping Liu, Daniel Sheldon, Thomas Dietterich
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: The Collective Graphical Model (CGM) models a population of  independent and identically distributed individuals when only  collective statistics (i.e., counts of individuals) are   observed. Exact inference in CGMs is intractable, and previous work  has explored Markov Chain Monte Carlo (MCMC) and MAP approximations  for learning and inference. This paper studies Gaussian approximations  to the CGM. As the population grows large, we show that the CGM   distribution converges to a multivariate Gaussian distribution (GCGM)  that maintains the conditional independence properties of the original  CGM.  If the observations are exact marginals of the CGM or marginals  that are corrupted by Gaussian noise, inference in the GCGM  approximation can be computed efficiently in closed form. If the   observations follow a different noise model (e.g., Poisson), then  expectation propagation provides efficient and accurate approximate  inference. The accuracy and speed of GCGM inference is compared to the   MCMC and MAP methods on a simulated bird migration problem. The GCGM  matches or exceeds the accuracy of the MAP method while being significantly  faster.
On learning to localize objects with minimal supervision
Authors: Hyun Oh Song, Ross Girshick, Stefanie Jegelka, Julien Mairal, Zaid Harchaoui, Trevor Darrell
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Learning to localize objects with minimal supervision is an important problem in computer vision, since large fully annotated datasets are extremely costly to obtain. In this paper, we propose a new method that achieves this goal with only image-level labels of whether the objects are present or not. Our approach combines a discriminative submodular cover problem for automatically discovering a set of positive object windows with a smoothed latent SVM formulation. The latter allows us to leverage efficient quasi-Newton optimization techniques. Our experiments demonstrate that the proposed approach provides a 50% relative improvement in mean average precision over the current state-of-the-art on PASCAL VOC 2007 detection.
Multiresolution Matrix Factorization
Authors: Risi Kondor, Nedelina Teneva, Vikas Garg
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: The types of large matrices that appear in modern Machine Learning problems often have complex hierarchical structures that go beyond what can be found by traditional linear algebra tools, such as eigendecompositions. Inspired by ideas from multiresolution analysis,   this paper introduces a new notion of matrix factorization that can capture structure in matrices at multiple different scales. The resulting Multiresolution Matrix Factorizations (MMFs) not only provide a wavelet basis for sparse approximation, but can also be used for matrix compression (similar to Nystrom approximations) and as a prior for matrix completion.
Learnability of the Superset Label Learning Problem
Authors: Liping Liu, Thomas Dietterich
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In the Superset Label Learning (SLL) problem, weak supervision is  provided in the form of a ıt superset of labels that contains the  true label.  If the classifier predicts a label outside of the  superset, it commits a ıt superset error.  Most existing SLL  algorithms learn a multiclass classifier by minimizing the superset  error. However, only limited theoretical analysis has been dedicated  to this approach. In this paper, we analyze Empirical Risk Minimizing  learners that use the superset error as the empirical risk measure.  SLL data can arise either in the form of independent instances or as  multiple-instance bags. For both scenarios, we give the conditions for  ERM learnability and sample complexity for the realizable case.
Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
Authors: Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, Robert Schapire
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We present a new algorithm for the contextual bandit learning problem,  where the learner repeatedly takes one of K \emphactions in response to the  observed \emphcontext, and observes the \emphreward only for that  action. Our method assumes access to an oracle for solving fully  supervised cost-sensitive classification problems and achieves the  statistically optimal regret guarantee with only øtil(\sqrtKT)  oracle calls across all T rounds. By doing so, we obtain the most  practical contextual bandit learning algorithm amongst approaches that  work for general policy classes.  We conduct a  proof-of-concept experiment which demonstrates the excellent  computational and statistical performance of (an online variant of) our  algorithm relative to several strong baselines.
Structured Recurrent Temporal Restricted Boltzmann Machines
Authors: Roni Mittelman, Benjamin Kuipers, Silvio Savarese, Honglak Lee
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: The Recurrent temporal restricted Boltzmann machine (RTRBM) is a probabilistic model for temporal data, that has been shown to effectively capture both short and long-term dependencies in time-series. The topology of the RTRBM graphical model, however, assumes full connectivity between all the pairs of visible and hidden units, therefore ignoring the dependency structure between the different observations. Learning this structure has the potential to not only improve the prediction performance, but it can also reveal important patterns in the data. For example, given an econometric dataset, we could identify interesting dependencies between different market sectors; given a meteorological dataset, we could identify regional weather patterns. In this work we propose a new class of RTRBM, which explicitly uses a dependency graph to model the structure in the problem and to define the energy function. We refer to the new model as the structured RTRBM (SRTRBM). Our technique is related to methods such as graphical lasso, which are used to learn the topology of Gaussian graphical models. We also develop a spike-and-slab version of the RTRBM, and combine it with our method to learn structure in datasets with real valued observations. Our experimental results using synthetic and real datasets, demonstrate that the SRTRBM can improve the prediction performance of the RTRBM, particularly when the number of visible units is large and the size of the training set is small. It also reveals the structure underlying our benchmark datasets.
Scalable and Robust Bayesian Inference via the Median Posterior
Authors: Stanislav Minsker, Sanvesh Srivastava, Lizhen Lin, David Dunson
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Many Bayesian learning methods for massive data benefit from working with small subsets of observations.  In particular, significant progress has been made in scalable Bayesian learning via stochastic approximation.  However, Bayesian learning methods in distributed computing environments are often problem- or distribution-specific and use ad hoc techniques.   We propose a novel general approach to Bayesian inference that is scalable and robust to corruption in the data.  Our technique is based on the idea of splitting the data into several non-overlapping subgroups, evaluating the posterior distribution given each independent subgroup, and then combining the results.  The main novelty is the proposed aggregation step which is based on finding the geometric median of posterior distributions.    We present both theoretical and numerical results illustrating the advantages of our approach.
Kernel Adaptive Metropolis-Hastings
Authors: Dino Sejdinovic, Heiko Strathmann, Maria Lomeli Garcia, Christophe Andrieu, Arthur Gretton
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: A Kernel Adaptive Metropolis-Hastings algorithm is introduced, for the purpose of sampling from a target distribution with strongly nonlinear support. The algorithm embeds the trajectory of the Markov chain into a reproducing kernel Hilbert space (RKHS), such that the feature space covariance of the samples informs the choice of proposal. The procedure is computationally efficient and straightforward to implement, since the RKHS moves can be integrated out analytically: our proposal distribution in the original space is a normal distribution whose mean and covariance depend on where the current sample lies in the support of the target distribution, and adapts to its local covariance structure. Furthermore, the procedure requires neither gradients nor any other higher order information about the target, making it particularly attractive for contexts such as Pseudo-Marginal MCMC. Kernel Adaptive Metropolis-Hastings outperforms competing fixed and adaptive samplers on multivariate, highly nonlinear target distributions, arising in both real-world and synthetic examples.
Input Warping for Bayesian Optimization of Non-Stationary Functions
Authors: Jasper Snoek, Kevin Swersky, Rich Zemel, Ryan Adams
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Bayesian optimization has proven to be a highly effective methodology for the global optimization of unknown, expensive and multimodal functions.  The ability to accurately model distributions over functions is critical to the effectiveness of Bayesian optimization.  Although Gaussian processes provide a flexible prior over functions, there are various classes of functions that remain difficult to model.  One of the most frequently occurring of these is the class of non-stationary functions.  The optimization of the hyperparameters of machine learning algorithms is a problem domain in which parameters are often manually transformed a priori, for example by optimizing in "log-space", to mitigate the effects of spatially-varying length scale.  We develop a methodology for automatically learning a wide family of bijective transformations or warpings of the input space using the Beta cumulative distribution function.  We further extend the warping framework to multi-task Bayesian optimization so that multiple tasks can be warped into a jointly stationary space. On a set of challenging benchmark optimization tasks, we observe that the inclusion of warping greatly improves on the state-of-the-art, producing better results faster and more reliably.
Stochastic Gradient Hamiltonian Monte Carlo
Authors: Tianqi Chen, Emily Fox, Carlos Guestrin
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Hamiltonian Monte Carlo (HMC) sampling methods provide a mechanism for defining distant proposals with high acceptance probabilities in a Metropolis-Hastings framework, enabling more efficient exploration of the state space than standard random-walk proposals.  The popularity of such methods has grown significantly in recent years.  However, a limitation of HMC methods is the required gradient computation for simulation of the Hamiltonian dynamical system-such computation is infeasible in problems involving a large sample size or streaming data. Instead, we must rely on a noisy gradient estimate computed from a subset of the data.  In this paper, we explore the properties of such a stochastic gradient HMC approach. Surprisingly, the natural implementation of the stochastic approximation can be arbitrarily bad.  To address this problem we introduce a variant that uses second-order Langevin dynamics with a friction term that counteracts the effects of the noisy gradient, maintaining the desired target distribution as the invariant distribution.  Results on simulated data validate our theory.  We also provide an application of our methods to a classification task using neural networks and to online Bayesian matrix factorization.
A Deep Semi-NMF Model for Learning Hidden Representations
Authors: George Trigeorgis, Konstantinos Bousmalis, Stefanos Zafeiriou, Bjoern Schuller
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Semi-NMF is a matrix factorization technique that learns a low-dimensional representation of a dataset that lends itself to a clustering interpretation. It is possible that the mapping between this new representation and our original features contains rather complex hierarchical information with implicit lower-level hidden attributes, that classical one level clustering methodologies can not interpret. In this work we propose a novel model, Deep Semi-NMF, that is able to learn such hidden representations that allow themselves to an interpretation of clustering  according to different, unknown attributes of a given dataset. We show that by doing so, our model is able to learn low-dimensional representations that are better suited for clustering, outperforming Semi-NMF, but also other NMF variants.
Asynchronous Distributed ADMM for Consensus Optimization
Authors: Ruiliang Zhang, James Kwok
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Distributed optimization algorithms are highly attractive for solving big data problems. In particular, many machine learning problems can be formulated as the global consensus optimization problem, which can then be solved in a distributed manner by the alternating direction method of multipliers (ADMM) algorithm. However, this suffers from the straggler problem as its updates have to be synchronized. In this paper, we propose an asynchronous ADMM algorithm by using two conditions to control the asynchrony: partial barrier and bounded delay. The proposed algorithm has a simple structure and good convergence guarantees (its convergence rate can be reduced to that of its synchronous counterpart). Experiments on different distributed ADMM applications show that asynchrony reduces the time on network waiting, and achieves faster convergence than its synchronous counterpart in terms of the wall clock time.
Spectral Regularization for Max-Margin Sequence Tagging
Authors: Ariadna Quattoni, Borja Balle, Xavier Carreras, Amir Globerson
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We frame max-margin learning of latent variable structured prediction models as a convex optimization problem, making use of scoring functions computed by input-output observable operator models. This learning problem can be expressed as an optimization involving a low-rank Hankel matrix that represents the input-output operator model. The direct outcome of our work is a new spectral regularization method for max-margin structured prediction.  Our experiments confirm that our proposed regularization framework leads to an effective way of controlling the capacity of structured prediction models.
Learning by Stretching Deep Networks
Authors: Gaurav Pandey, Ambedkar Dukkipati
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In recent years, deep architectures have gained a lot of prominence for learning complex AI tasks  because of their capability to incorporate complex variations in data within the model. However, these models often need to be trained for a long time in order to obtain good results. In this paper, we propose a technique, called ‘stretching’, that allows the same models to perform considerably better with very little training.  We show that learning can be done tractably, even when the weight matrix is stretched to infinity, for some specific models. We also study tractable algorithms for implementing stretching in deep convolutional architectures in an iterative manner and derive bounds for its convergence. Our experimental results suggest that the proposed stretched deep convolutional networks are capable of achieving good performance for many object recognition tasks. More importantly, for a fixed network architecture, one can achieve much better accuracy using stretching rather than learning the weights using backpropagation.
Nonnegative Sparse PCA with Provable Guarantees
Authors: Megasthenis Asteris, Dimitris Papailiopoulos, Alexandros Dimakis
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We introduce a novel algorithm to compute nonnegative sparse principal components of positive semidefinite (PSD) matrices. Our algorithm comes with approximation guarantees   contingent on the spectral profile of the input matrix A:  the sharper the eigenvalue decay, the better the approximation quality.    If the eigenvalues decay like any asymptotically vanishing function, we can approximate nonnegative sparse PCA within any accuracy εin time polynomial in the matrix size n and desired sparsity k, but not in 1/ε. Further, we obtain a data-dependent bound that is computed by executing an algorithm on a given data set. This bound is significantly tighter than a-priori bounds and can be used to show that for all tested datasets our algorithm is provably within 40%-90% from the unknown optimum.     Our algorithm is combinatorial and explores a subspace defined by the leading eigenvectors of A. We test our scheme on several data sets, showing that it matches or outperforms the previous state of the art.
Active Learning of Parameterized Skills
Authors: Bruno Da Silva, George Konidaris, Andrew Barto
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We introduce a method for actively learning parameterized skills. Parameterized skills are flexible behaviors that can solve any task drawn from a distribution of parameterized reinforcement learning problems. Approaches to learning such skills have been proposed, but limited attention has been given to identifying which training tasks allow for rapid skill acquisition. We construct a non-parametric Bayesian model of skill performance and derive analytical expressions for a novel acquisition criterion capable of identifying tasks that maximize expected improvement in skill performance. We also introduce a spatiotemporal kernel tailored for non-stationary skill performance models. The proposed method is agnostic to policy and skill representation and scales independently of task dimensionality. We evaluate it on a non-linear simulated catapult control problem over arbitrarily mountainous terrains.
Learning Ordered Representations with Nested Dropout
Authors: Oren Rippel, Michael Gelbart, Ryan Adams
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In this paper, we present results on ordered representations of data in which different dimensions have different degrees of importance. To learn these representations we introduce nested dropout, a procedure for stochastically removing coherent nested sets of hidden units in a neural network. We first present a sequence of theoretical results in the simple case of a semi-linear autoencoder.  We rigorously show that the application of nested dropout enforces identifiability of the units, which leads to an exact equivalence with PCA.  We then extend the algorithm to deep models and demonstrate the relevance of ordered representations to a number of applications.  Specifically, we use the ordered property of the learned codes to construct hash-based data structures that permit very fast retrieval, achieving retrieval in time logarithmic in the database size and independent of the dimensionality of the representation. This allows the use of codes that are hundreds of times longer than currently feasible for retrieval.  We therefore avoid the diminished quality associated with short codes, while still performing retrieval that is competitive in speed with existing methods.  We also show that ordered representations are a promising way to learn adaptive compression for efficient online data reconstruction.
Learning the Irreducible Representations of Commutative Lie Groups
Authors: Taco Cohen, Max Welling
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We present a new probabilistic model of compact commutative Lie groups that produces invariant-equivariant and disentangled representations of data. To define the notion of disentangling, we borrow a fundamental principle from physics that is used to derive the elementary particles of a system from its symmetries. Our model employs a newfound Bayesian conjugacy relation that enables fully tractable probabilistic inference over compact commutative Lie groups – a class that includes the groups that describe the rotation and cyclic translation of images. We train the model on pairs of transformed image patches, and show that the learned invariant representation is highly effective for classification.