mtybilly/Instruct2DS huggingface dataset:
Structured Generative Models of Natural Source Code
Authors: Maddison, Chris and Tarlow, Daniel
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We study the problem of building generative models of natural source code (NSC); that is, source code written and understood by humans. Our primary contribution is to describe a family of generative models for NSC that have two key properties: First, they incorporate both sequential and hierarchical structure. Second, they are capable of integrating closely with a compiler, which allows leveraging compiler logic and abstractions when building structure into the model. We also develop an extension that includes more complex structure, refining how the model generates identifier tokens based on what variables are currently in scope.  Our models can be learned efficiently, and we show empirically that including appropriate structure greatly improves the probability of generating test programs.
Making the Most of Bag of Words: Sentence Regularization with Alternating Direction Method of Multipliers
Authors: Yogatama, Dani and Smith, Noah
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In many high-dimensional learning problems, only some parts of an observation are important to the prediction task; for example, the cues to correctly categorizing a document may lie in a handful of its sentences. We introduce a learning algorithm that exploits this intuition by encoding it in a regularizer.  Specifically, we apply the sparse overlapping group lasso with one group for every bundle of features occurring together in a training-data sentence, leading to thousands to millions of overlapping groups. We show how to efficiently solve the resulting optimization challenge using the alternating directions method of multipliers.  We find that the resulting method significantly outperforms competitive baselines (standard ridge, lasso, and elastic net regularizers) on a suite of real-world text categorization problems.
A Single-Pass Algorithm for Efficiently Recovering Sparse Cluster Centers of High-dimensional Data
Authors: Yi, Jinfeng and Zhang, Lijun and Wang, Jun and Jin, Rong and Jain, Anil
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Learning a statistical model for high-dimensional data is an important topic in machine learning. Although this problem has been well studied in the supervised setting, little is known about its unsupervised counterpart. In this work, we focus on the problem of clustering high-dimensional data with sparse centers.  In particular, we address the following open question in unsupervised learning: “is it possible to reliably cluster high-dimensional data when the number of samples is smaller than the data dimensionality?" We develop an efficient clustering algorithm that is able to estimate sparse cluster centers with a single pass over the data. Our theoretical analysis shows that the proposed algorithm is able to accurately recover cluster centers with only O(słog d) number of samples (data points), provided all the cluster centers are s-sparse vectors in a d dimensional space. Experimental results verify both the effectiveness and efficiency of the proposed clustering algorithm compared to the state-of-the-art algorithms on several benchmark datasets.
Narrowing the Gap: Random Forests In Theory and In Practice
Authors: Denil, Misha and Matheson, David and De Freitas, Nando
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Despite widespread interest and practical use, the theoretical properties of random forests are still not well understood. In this paper we contribute to this understanding in two ways. We present a new theoreti- cally tractable variant of random regression forests and prove that our algorithm is con- sistent. We also provide an empirical eval- uation, comparing our algorithm and other theoretically tractable random forest models to the random forest algorithm used in prac- tice. Our experiments provide insight into the relative importance of different simplifi- cations that theoreticians have made to ob- tain tractable models for analysis.
Statistical analysis of stochastic gradient methods for generalized linear models
Authors: Toulis, Panagiotis and Airoldi, Edoardo and Rennie, Jason
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We study the statistical properties of stochastic gradient descent (SGD) using   explicit and implicit updates for fitting generalized linear models (GLMs).  Initially, we develop a computationally   efficient algorithm to implement implicit SGD learning of GLMs.  Next, we obtain exact formulas for the bias and variance  of both updates which leads to two important observations on their   comparative statistical properties.  First, in small samples, the estimates from the implicit procedure   are more biased than the estimates from the explicit one,   but their empirical variance is smaller and they are more robust to   learning rate misspecification.   Second, the two procedures are statistically identical in the limit:   they are both unbiased, converge at the same rate and have the   same asymptotic variance. Our set of experiments confirm our theory and   more broadly suggest that the implicit procedure can be a competitive choice   for fitting large-scale  models, especially when robustness is a concern.
Coherent Matrix Completion
Authors: Chen, Yudong and Bhojanapalli, Srinadh and Sanghavi, Sujay and Ward, Rachel
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Matrix completion concerns the recovery of a low-rank matrix from a subset of its revealed entries, and nuclear norm minimization has emerged as an effective surrogate for this combinatorial problem.  Here, we show that nuclear norm minimization can recover an arbitrary n \times n matrix of rank r from O(nr log^2(n)) revealed entries, provided that revealed entries are drawn proportionally to the local row and column coherences (closely related to leverage scores) of the underlying matrix.  Our results are order-optimal up to logarithmic factors, and extend existing results for nuclear norm minimization which require strong incoherence conditions on the types of matrices that can be recovered, due to assumed uniformly distributed revealed entries.  We further provide extensive numerical evidence that a proposed two-phase sampling algorithm can perform nearly as well as local-coherence sampling and without requiring a priori knowledge of the matrix coherence structure.  Finally, we apply our results to quantify how weighted nuclear norm minimization can improve on unweighted minimization given an arbitrary set of sampled entries.
Coding for Random Projections
Authors: Li, Ping and Mitzenmacher, Michael and Shrivastava, Anshumali
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: The method of random projections has become  popular for large-scale applications in statistical learning, information retrieval, bio-informatics  and other applications.  Using a well-designed \textbfcoding scheme for the projected data, which determines the number of bits needed for each projected value and how to allocate these bits, can significantly improve the effectiveness of the algorithm, in storage cost as well as computational speed.   In this paper, we study a number of simple coding schemes, focusing on the task of similarity estimation and on an application to training linear classifiers. We demonstrate that \textbfuniform quantization outperforms the standard and influential method i̧teProc:Datar_SCG04, which used a \em window-and-random offset scheme. Indeed, we argue that in many cases coding with just a small number of bits suffices.  Furthermore, we also  develop a \textbfnon-uniform 2-bit coding scheme that generally performs well in practice, as confirmed by our experiments on training linear support vector machines (SVM). Proofs and additional experiments  are available at \em arXiv:1308.2218.      In the context of using coded random projections for \textbfapproximate near neighbor search by building hash tables (\em arXiv:1403.8144) \ţeReport:RPCodeLSH2014, we show that the step of random offset in \cȩProc:Datar_SCG04 is  again not needed  and may hurt the performance. Furthermore, we show that, unless the target similarity level is high, it usually suffices to use only 1 or 2 bits to code each hashed value for this task. Section e̊fsec_LSH presents some experimental results for LSH.
Admixture of Poisson MRFs: A Topic Model with Word Dependencies
Authors: Inouye, David and Ravikumar, Pradeep and Dhillon, Inderjit
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: This paper introduces a new topic model based on an admixture of Poisson Markov Random Fields (APM), which can model dependencies between words as opposed to previous independent topic models such as PLSA (Hofmann, 1999), LDA (Blei et al., 2003) or SAM (Reisinger et al., 2010). We propose a class of admixture models that generalizes previous topic models and show an equivalence between the conditional distribution of LDA and independent Poissons—suggesting that APM subsumes the modeling power of LDA. We present a tractable method for estimating the parameters of an APM based on the pseudo log-likelihood and demonstrate the benefits of APM over previous models by preliminary qualitative and quantitative experiments.
Fast Computation of Wasserstein Barycenters
Authors: Cuturi, Marco and Doucet, Arnaud
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We present new algorithms to compute the mean of a set of $N$ empirical probability measures under the optimal transport metric. This mean, known as the Wasserstein barycenter (Agueh and Carlier, 2011; Rabin et al, 2012), is the measure that minimizes the sum of its Wasserstein distances to each element in that set. We argue through a simple example that Wasserstein barycenters have appealing properties that differentiate them from other barycenters proposed recently, which all build on kernel smoothing and/or Bregman divergences. Two original algorithms are proposed that require the repeated computation of primal and dual optimal solutions of transport problems. However direct implementation of these algorithms is too costly as optimal transports are notoriously computationally expensive. Extending the work of Cuturi (2013), we smooth both the primal and dual of the optimal transport problem to recover fast approximations of the primal and dual optimal solutions. We apply these algorithms to the visualization of perturbed images and to a clustering problem.
True Online TD(lambda)
Authors: Seijen, Harm and Sutton, Rich
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: TD(lambda) is a core algorithm of modern reinforcement learning. Its appeal comes from its equivalence to a clear and conceptually simple forward view, and the fact that it can be implemented online in an inexpensive manner. However, the equivalence between TD(lambda) and the forward view is exact only for the off-line version of the algorithm (in which updates are made only at the end of each episode). In the online version of TD(lambda) (in which updates are made at each step, which generally performs better and is always used in applications) the match to the forward view is only approximate. In a sense this is unavoidable for the conventional forward view, as it itself presumes that the estimates are unchanging during an episode. In this paper we introduce a new forward view that takes into account the possibility of changing estimates and a new variant of TD(lambda) that exactly achieves it. Our algorithm uses a new form of eligibility trace similar to but different from conventional accumulating and replacing traces. The overall computational complexity is the same as TD(lambda), even when using function approximation. In our empirical comparisons, our algorithm outperformed TD(lambda) in all of its variations. It seems, by adhering more truly to the original goal of TD(lambda)—matching an intuitively clear forward view even in the online case—that we have found a new algorithm that simply improves on classical TD(lambda).
Global graph kernels using geometric embeddings
Authors: Johansson, Fredrik and Jethava, Vinay and Dubhashi, Devdatt and Bhattacharyya, Chiranjib
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Applications of machine learning methods increasingly deal with graph structured data through kernels. Most existing graph kernels compare graphs in terms of features defined on small subgraphs such as walks, paths or graphlets, adopting an inherently local perspective. However, several interesting properties such as girth or chromatic number are global properties of the graph, and are not captured in local substructures. This paper presents two graph kernels defined on unlabeled graphs which capture global properties of graphs using the celebrated Lovász number and its associated orthonormal representation. We make progress towards theoretical results aiding kernel choice, proving a result about the separation margin of our kernel for classes of graphs. We give empirical results on classification of synthesized graphs with important global properties as well as established benchmark graph datasets, showing that the accuracy of our kernels is better than or competitive to existing graph kernels.
Memory Efficient Kernel Approximation
Authors: Si, Si and Hsieh, Cho-Jui and Dhillon, Inderjit
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: The scalability of kernel machines is a big challenge when facing millions of samples due to storage and computation issues for large kernel matrices, that are usually dense. Recently, many papers have suggested tackling this problem by using a low rank approximation of the kernel matrix. In this paper, we first make the observation that the structure of shift-invariant kernels changes from low-rank to block-diagonal (without any low-rank structure) when varying the scale parameter. Based on this observation, we propose a new kernel approximation algorithm – Memory Efficient Kernel Approximation (MEKA), which considers both low-rank and clustering structure of the kernel matrix. We show that the resulting algorithm outperforms state-of-the-art low-rank kernel approximation methods in terms of speed, approximation error, and memory usage. As an example, on the MNIST2M dataset with two-million samples, our method takes 550 seconds on a single machine using less than 500 MBytes memory to achieve 0.2313 test RMSE for kernel ridge regression, while standard Nyström approximation takes more than 2700 seconds and uses more than 2 GBytes memory on the same problem to achieve 0.2318 test RMSE.
Topic Modeling using Topics from Many Domains, Lifelong Learning and Big Data
Authors: Chen, Zhiyuan and Liu, Bing
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Topic modeling has been commonly used to discover topics from document collections. However, unsupervised models can generate many incoherent topics. To address this problem, several knowledge-based topic models have been proposed to incorporate prior domain knowledge from the user. This work advances this research much further and shows that without any user input, we can mine the prior knowledge automatically and dynamically from topics already found from a large number of domains. This paper first proposes a novel method to mine such prior knowledge dynamically in the modeling process, and then a new topic model to use the knowledge to guide the model inference. What is also interesting is that this approach offers a novel lifelong learning algorithm for topic discovery, which exploits the big (past) data and knowledge gained from such data for subsequent modeling. Our experimental results using product reviews from 50 domains demonstrate the effectiveness of the proposed approach.
Learning Sum-Product Networks with Direct and Indirect Variable Interactions
Authors: Rooshenas, Amirmohammad and Lowd, Daniel
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Sum-product networks (SPNs) are a deep probabilistic representation that allows for efficient, exact inference.  SPNs generalize many other tractable models, including thin junction trees, latent tree models, and many types of mixtures.  Previous work on learning SPN structure has mainly focused on using top-down or bottom-up clustering to find mixtures, which capture variable interactions indirectly through implicit latent variables.  In contrast, most work on learning graphical models, thin junction trees, and arithmetic circuits has focused on finding direct interactions among variables.  In this paper, we present ID-SPN, a new algorithm for learning SPN structure that unifies the two approaches. In experiments on 20 benchmark datasets, we find that the combination of direct and indirect interactions leads to significantly better accuracy than several state-of-the-art algorithms for learning SPNs and other tractable models.
K-means recovers ICA filters when independent components are sparse
Authors: Vinnikov, Alon and Shalev-Shwartz, Shai
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Unsupervised feature learning is the task of using unlabeled examples  for building a representation of objects as vectors. This task has  been extensively studied in recent years, mainly in the context of  unsupervised pre-training of neural networks. Recently, (Coates et al., 2011)  conducted extensive experiments, comparing the accuracy of a linear  classifier that has been trained using features learnt by several  unsupervised feature learning methods.  Surprisingly, the best  performing method was the simplest feature learning approach that was  based on applying the K-means clustering algorithm after a whitening  of the data. The goal of this work is to shed light on the success of  K-means with whitening for the task of unsupervised feature learning.  Our main result is a close connection between K-means and ICA  (Independent Component Analysis).  Specifically, we show that K-means  and similar clustering algorithms can be used to recover the ICA  mixing matrix or its inverse, the ICA filters. It is well known that  the independent components found by ICA form useful features for  classification (Le et al., 2012; 2011; 2010), hence the connection between K-mean and ICA explains  the empirical success of K-means as a feature learner. Moreover, our  analysis underscores the significance of the whitening operation, as was also  observed in the experiments reported in (Coates et al., 2011).  Finally, our  analysis leads to a better initialization of K-means for the task of feature learning.
Hamiltonian Monte Carlo Without Detailed Balance
Authors: Sohl-Dickstein, Jascha and Mudigonda, Mayur and DeWeese, Michael
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We present a method for performing Hamiltonian Monte Carlo that largely eliminates sample rejection.  In situations that would normally lead to rejection, instead a longer trajectory is computed until a new state is reached that can be accepted.  This is achieved using Markov chain transitions that satisfy the fixed point equation, but do not satisfy detailed balance.  The resulting algorithm significantly suppresses the random walk behavior and wasted function evaluations that are typically the consequence of update rejection.  We demonstrate a greater than factor of two improvement in mixing time on three test problems.  We release the source code as Python and MATLAB packages.
Learning Mixtures of Linear Classifiers
Authors: Sun, Yuekai and Ioannidis, Stratis and Montanari, Andrea
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We consider a discriminative learning (regression) problem, whereby the regression function is a convex combination of k linear classifiers. Existing approaches are based on the EM algorithm, or similar techniques, without provable guarantees. We develop a simple method based on spectral techniques and a ‘mirroring’ trick, that discovers the subspace spanned by the classifiers’ parameter vectors. Under a probabilistic assumption on the  feature vector distribution, we prove that this approach has nearly optimal statistical efficiency.
Filtering with Abstract Particles
Authors: Steinhardt, Jacob and Liang, Percy
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Using particles, beam search and sequential Monte Carlo can approximate distributions in an extremely flexible manner. However, they can suffer from sparsity and inadequate coverage on large state spaces. We present a new filtering method that addresses this issue  by using “abstract particles” that each represent an entire region of the state space. These abstract particles are combined into a hierarchical decomposition, yielding a  representation that is both compact and flexible. Empirically, our method outperforms beam search and sequential Monte Carlo on both a text reconstruction task and a multiple object tracking task.
The Falling Factorial Basis and Its Statistical Applications
Authors: Wang, Yu-Xiang and Smola, Alex and Tibshirani, Ryan
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We study a novel spline-like basis, which we name the   ıt falling factorial basis, bearing many similarities to the  classic truncated power basis.  The advantage of the falling factorial  basis is that it enables rapid, linear-time computations in basis  matrix multiplication and basis matrix inversion.  The falling  factorial functions are not actually splines, but are close enough  to splines that they provably retain some of the favorable properties  of the latter functions.  We examine their application in two  problems: trend filtering over arbitrary input points, and a  higher-order variant of the two-sample Kolmogorov-Smirnov test.
Stochastic Dual Coordinate Ascent with Alternating Direction Method of Multipliers
Authors: Suzuki, Taiji
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We propose a new stochastic dual coordinate ascent technique  that can be applied to a wide range of regularized learning problems. Our method is based on  alternating direction method of multipliers (ADMM) to deal with complex regularization functions such as structured regularizations. Although the original ADMM is a batch method,  the proposed method offers a stochastic update rule where each iteration requires only one or few sample observations. Moreover, our method can naturally afford mini-batch update and it gives speed up of convergence. We show that, under mild assumptions, our method converges exponentially. The numerical experiments show that our method actually performs efficiently.
Nonmyopic $ε$-Bayes-Optimal Active Learning of Gaussian Processes
Authors: Hoang, Trong Nghia and Low, Bryan Kian Hsiang and Jaillet, Patrick and Kankanhalli, Mohan
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: A fundamental issue in active learning of Gaussian processes is that of the exploration-exploitation trade-off. This paper presents a novel nonmyopic ε-Bayes-optimal active learning (ε-BAL) approach that jointly and naturally optimizes the trade-off.   In contrast, existing works have primarily developed myopic/greedy algorithms or performed exploration and exploitation separately. To perform active learning in real time, we then propose an anytime algorithm based on ε-BAL with performance guarantee and empirically demonstrate using synthetic and real-world datasets that, with limited budget, it outperforms the state-of-the-art algorithms.
Deep Supervised and Convolutional Generative Stochastic Network for Protein Secondary Structure Prediction
Authors: Zhou, Jian and Troyanskaya, Olga
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Predicting protein secondary structure is a fundamental problem in protein structure prediction. Here we present a new supervised generative stochastic network (GSN) based method to predict local secondary structure with deep hierarchical representations. GSN is a recently proposed deep learning technique (Bengio & Thibodeau-Laufer, 2013) to globally train deep generative model. We present the supervised extension of GSN, which learns a Markov chain to sample from a conditional distribution, and applied it to protein structure prediction. To scale the model to full-sized, high-dimensional data, like protein sequences with hundreds of amino-acids, we introduce a convolutional architecture, which allows efficient learning across multiple layers of hierarchical representations. Our architecture uniquely focuses on predicting structured low-level labels informed with both low and high-level representations learned by the model. In our application this corresponds to labeling the secondary structure state of each amino-acid residue. We trained and tested the model on separate sets of non-homologous proteins sharing less than 30% sequence identity. Our model achieves 66.4% Q8 accuracy on the CB513 dataset, better than the previously reported best performance 64.9% (Wang et al., 2011) for this challenging secondary structure prediction problem.
A Unifying View of Representer Theorems
Authors: Argyriou, Andreas and Dinuzzo, Francesco
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: It is known that the solution of regularization and interpolation problems with Hilbertian penalties can be expressed as a linear combination of the data. This very useful property, called the representer theorem, has been widely studied and applied to machine learning problems. Analogous optimality conditions have appeared in other contexts, notably in matrix regularization.  In this paper we propose a unified view, which generalizes the concept of representer theorems and extends necessary and sufficient conditions for such theorems to hold. Our main result shows a close connection between representer theorems and certain classes of regularization penalties, which we call orthomonotone functions.  This result not only subsumes previous representer theorems as  special cases but also yields a new class of optimality conditions, which goes beyond the classical linear combination of the data.  Moreover, orthomonotonicity   provides a useful criterion for testing whether a representer theorem  holds for a specific regularization problem.
An Efficient Approach for Assessing Hyperparameter Importance
Authors: Hutter, Frank and Hoos, Holger and Leyton-Brown, Kevin
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: The performance of many machine learning methods depends critically on hyperparameter settings. Sophisticated Bayesian optimization methods have recently achieved considerable successes in optimizing these hyperparameters, in several cases surpassing the performance of human experts. However, blind reliance on such methods can leave end users without insight into the relative importance of different hyperparameters and their interactions. This paper describes efficient methods that can be used to gain such insight, leveraging random forest models fit on the data already gathered by Bayesian optimization. We first introduce a novel, linear-time algorithm for computing marginals of random forest predictions and then show how to leverage these predictions within a functional ANOVA framework, to quantify the importance of both single hyperparameters and of interactions between hyperparameters. We conducted experiments with prominent machine learning frameworks and state-of-the-art solvers for combinatorial problems. We show that our methods provide insight into the relationship between hyperparameter settings and performance, and demonstrate that—even in very high-dimensional cases—most performance variation is attributable to just a few hyperparameters.
Online Clustering of Bandits
Authors: Gentile, Claudio and Li, Shuai and Zappella, Giovanni
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We introduce a novel algorithmic approach to content recommendation based on adaptive clustering of exploration-exploitation (“bandit") strategies. We provide a sharp regret analysis of this algorithm in a standard stochastic noise setting, demonstrate its scalability properties, and prove its effectiveness on a number of artificial and real-world datasets. Our experiments show a significant increase in prediction performance over state-of-the-art methods for bandit problems.
Cold-start Active Learning with Robust Ordinal Matrix Factorization
Authors: Houlsby, Neil and Hernandez-Lobato, Jose Miguel and Ghahramani, Zoubin
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We present a new matrix factorization model for rating data and a corresponding active learning strategy to address the cold-start problem. Cold-start is one of the most challenging tasks for recommender systems: what to recommend with new users or items for which one has little or no data. An approach is to use active learning to collect the most useful initial ratings. However, the performance of active learning depends strongly upon having accurate estimates of i) the uncertainty in model parameters and ii) the intrinsic noisiness of the data. To achieve these estimates we propose a heteroskedastic Bayesian model for ordinal matrix factorization. We also present a computationally efficient framework for Bayesian active learning with this type of complex probabilistic model. This algorithm successfully distinguishes between informative and noisy data points. Our model yields state-of-the-art predictive performance and, coupled with our active learning strategy, enables us to gain useful information in the cold-start setting from the very first active sample.
Multivariate Maximal Correlation Analysis
Authors: Nguyen, Hoang Vu and Müller, Emmanuel and Vreeken, Jilles and Efros, Pavel and Böhm, Klemens
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Correlation analysis is one of the key elements of statistics, and has various applications in data analysis. Whereas most existing measures can only detect pairwise correlations between two dimensions, modern analysis aims at detecting correlations in multi-dimensional spaces.    We propose MAC, a novel multivariate correlation measure designed for discovering multi-dimensional patterns. It belongs to the powerful class of maximal correlation analysis, for which we propose a generalization to multivariate domains. We highlight the limitations of current methods in this class, and address these with MAC. Our experiments show that MAC outperforms existing solutions, is robust to noise, and discovers interesting and useful patterns.
Efficient Label Propagation
Authors: Fujiwara, Yasuhiro and Irie, Go
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Label propagation is a popular graph-based semi-supervised learning framework.   So as to obtain the optimal labeling scores, the label propagation algorithm requires an inverse matrix which incurs the high computational cost of O(n^3+cn^2), where n and c are the numbers of data points and labels, respectively.   This paper proposes an efficient label propagation algorithm that guarantees exactly the same labeling results as those yielded by optimal labeling scores.   The key to our approach is to iteratively compute lower and upper bounds of labeling scores to prune unnecessary score computations.   This idea significantly reduces the computational cost to O(cnt) where t is the average number of iterations for each label and t << n in practice.   Experiments demonstrate the significant superiority of our algorithm over existing label propagation methods.
Estimating Diffusion Network Structures: Recovery Conditions, Sample Complexity & Soft-thresholding Algorithm
Authors: Daneshmand, Hadi and Gomez-Rodriguez, Manuel and Song, Le and Schoelkopf, Bernhard
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Information spreads across social and technological networks, but often the network structures are hidden from us and we only observe the traces left by the diffusion processes, called cascades. Can we recover the hidden network structures from these observed cascades? What kind of cascades and how many cascades do we need? Are there some network structures which are more difficult than others to recover? Can we design efficient inference algorithms with provable guarantees?    Despite the increasing availability of cascade data and methods for inferring networks from these data, a thorough theoretical understanding of the above questions remains largely unexplored in the literature. In this paper, we investigate the network structure inference problem for a general family of continuous-time diffusion models using an l1-regularized likelihood maximization framework. We show that, as long as the cascade sampling process satisfies a natural incoherence condition, our framework can recover the correct network structure with high probability if we observe O(d^3 log N) cascades, where d is the maximum number of parents of a node and N is the total number of nodes. Moreover, we develop a simple and efficient soft-thresholding inference algorithm, which we use to illustrate the consequences of our theoretical results, and show that our framework outperforms other alternatives in practice.
Coupled Group Lasso for Web-Scale CTR Prediction in Display Advertising
Authors: Yan, Ling and Li, Wu-Jun and Xue, Gui-Rong and Han, Dingyi
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In display advertising, click through rate(CTR) prediction is the problem of estimating the probability  that an advertisement (ad) is clicked when displayed to a user in a specific context. Due to its easy implementation and promising performance, logistic regression(LR) model has been widely used for CTR prediction, especially in industrial systems. However, it is not easy for LR to capture the nonlinear information, such as the conjunction information, from user features and ad features. In this paper, we propose a novel model, called coupled group lasso(CGL), for CTR prediction in display advertising. CGL can seamlessly integrate the conjunction information from user features and ad features for modeling. Furthermore, CGL can automatically eliminate useless features for both users and ads, which may facilitate fast online prediction. Scalability of CGL is ensured through feature hashing and distributed implementation. Experimental results on real-world data sets show that our CGL model can achieve state-of-the-art performance on web-scale CTR prediction tasks.
Putting MRFs on a Tensor Train
Authors: Novikov, Alexander and Rodomanov, Anton and Osokin, Anton and Vetrov, Dmitry
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: In the paper we present a new framework for dealing with probabilistic graphical models. Our approach relies on the recently proposed Tensor Train format (TT-format) of a tensor that while being  compact allows for efficient application of linear algebra operations. We present a way to convert the energy of a Markov random field to the TT-format and show how one can exploit the properties of the TT-format to attack the tasks of the partition function estimation and the MAP-inference. We provide theoretical guarantees on the accuracy of the proposed algorithm for estimating the partition function and compare our methods against several state-of-the-art algorithms.
Efficient Algorithms for Robust One-bit Compressive Sensing
Authors: Zhang, Lijun and Yi, Jinfeng and Jin, Rong
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: While the conventional compressive sensing assumes measurements of infinite precision, one-bit compressive sensing considers an extreme setting where each measurement is quantized to just a single bit. In this paper, we study the vector recovery problem from noisy one-bit measurements, and develop two novel algorithms with formal theoretical guarantees. First, we propose a passive algorithm, which is very efficient in the sense it only needs to solve a convex optimization problem that has a closed-form solution. Despite the apparent simplicity, our theoretical analysis reveals that the proposed algorithm can recover both the exactly sparse and the approximately sparse vectors. In particular, for a sparse vector with s nonzero elements, the sample complexity is O(s łog n/ε^2), where n is the dimensionality and εis the recovery error. This result improves significantly over the previously best known sample complexity in the noisy setting, which is O(s łog n/ε^4). Second, in the case that the noise model is known, we develop an adaptive algorithm based on the principle of active learning. The key idea is to solicit the sign information only when it cannot be inferred from the current estimator. Compared with the passive algorithm, the adaptive one has a lower sample complexity if a high-precision solution is desired.
Learning Complex Neural Network Policies with Trajectory Optimization
Authors: Levine, Sergey and Koltun, Vladlen
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: Direct policy search methods offer the promise of automatically learning controllers for complex, high-dimensional tasks. However, prior applications of policy search often required specialized, low-dimensional policy classes, limiting their generality. In this work, we introduce a policy search algorithm that can directly learn high-dimensional, general-purpose policies, represented by neural networks. We formulate the policy search problem as an optimization over trajectory distributions, alternating between optimizing the policy to match the trajectories, and optimizing the trajectories to match the policy and minimize expected cost. Our method can learn policies for complex tasks such as bipedal push recovery and walking on uneven terrain, while outperforming prior methods.
Composite Quantization for Approximate Nearest Neighbor Search
Authors: Zhang, Ting and Du, Chao and Wang, Jingdong
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: This paper presents a novel compact coding approach, composite quantization, for approximate nearest neighbor search. The idea is to use the composition of several elements selected from the dictionaries to accurately approximate a vector and to represent the vector by a short code composed of the indices of the selected elements. To efficiently compute the approximate distance of a query to a database vector using the short code, we introduce an extra constraint, constant inter-dictionary-element-product, resulting in that  approximating the distance only using the distance of the query to each selected element is enough for nearest neighbor search. Experimental comparison with state-of-the-art algorithms over several benchmark datasets demonstrates the efficacy of the proposed approach.
Local Ordinal Embedding
Authors: Terada, Yoshikazu and Luxburg, Ulrike
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We study the problem of ordinal embedding: given a set of ordinal constraints of the form distance(i,j) < distance(k,l) for some_quadruples (i,j,k,l) of indices, the goal is to construct a point configuration \hat\bmx_1, ..., \hat\bmx_n in \R^p that preserves these constraints as well as possible. Our first contribution is to suggest a simple new algorithm for this problem, Soft Ordinal Embedding. The key feature of the algorithm is that it recovers not only the ordinal constraints, but even the density structure of the underlying data set. As our second contribution we prove that in the large sample limit it is enough to know “local ordinal information” in order to perfectly reconstruct a given point configuration. This leads to our Local Ordinal Embedding algorithm, which can also be used for graph drawing.
Reducing Dueling Bandits to Cardinal Bandits
Authors: Ailon, Nir and Karnin, Zohar and Joachims, Thorsten
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We present algorithms for reducing the Dueling Bandits problem to the conventional (stochastic) Multi-Armed Bandits problem. The Dueling Bandits problem is an online model of learning with ordinal feedback of the form “A is preferred to B” (as opposed to cardinal feedback like “A has value 2.5”), giving it wide applicability in learning from implicit user feedback and revealed and stated preferences. In contrast to existing algorithms for the Dueling Bandits problem, our reductions – named \Doubler, \MultiSbm and \DoubleSbm – provide a generic schema for translating the extensive body of known results about conventional Multi-Armed Bandit algorithms to the Dueling Bandits setting.     For \Doubler and \MultiSbm we prove regret upper bounds in both finite and infinite settings, and conjecture about the performance of \DoubleSbm which empirically outperforms the other two as well as previous algorithms in our experiments.  In addition, we provide the first almost optimal regret bound in terms of second order terms, such as the differences between the values of the arms.
Large-margin  Weakly Supervised Dimensionality Reduction
Authors: Xu, Chang and Tao, Dacheng and Xu, Chao and Rui, Yong
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: This paper  studies dimensionality reduction in a weakly supervised setting, in which the preference relationship between examples is indicated by weak cues. A novel framework is proposed that integrates two aspects of the large margin principle (angle and distance), which simultaneously encourage angle consistency between preference pairs and maximize the distance between examples in preference pairs. Two specific algorithms are developed: an alternating direction method to learn a linear transformation matrix and a gradient boosting technique to optimize a non-linear transformation directly in the function space. Theoretical analysis demonstrates that the proposed large margin optimization criteria can strengthen and improve the robustness and generalization performance of preference learning algorithms on the obtained low-dimensional subspace. Experimental results on real-world datasets demonstrate the significance of studying dimensionality reduction in the weakly supervised setting and the effectiveness of the proposed framework.
Joint Inference of Multiple Label Types in Large Networks
Authors: Chakrabarti, Deepayan and Funiak, Stanislav and Chang, Jonathan and Macskassy, Sofus
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We tackle the problem of inferring node labels in a partially labeled  graph where each node in the graph has multiple label types and  each label type has a large number of possible labels.  Our primary  example, and the focus of this paper, is the joint inference of label  types such as hometown, current city, and employers, for users  connected by a social network.  Standard label propagation fails to  consider the properties of the label types and the interactions  between them.  Our proposed method, called EdgeExplain, explicitly  models these, while still enabling scalable inference under a  distributed message-passing architecture.  On a billion-node subset of the Facebook social network,  EdgeExplain significantly outperforms label propagation for several  label types, with lifts of up to 120% for recall@1 and 60% for  recall@3.
Hard-Margin Active Linear Regression
Authors: Hazan, Elad and Karnin, Zohar
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We consider the fundamental problem of linear regression in which the designer can actively choose observations.   This model naturally captures various experiment design settings in medical experiments, ad placement problems and more. Whereas previous literature addresses the soft-margin or mean-square-error variants of the problem, we consider a natural machine learning hard-margin criterion. In this setting, we show that active learning admits significantly better sample complexity bounds than the passive learning counterpart, and give  efficient algorithms that attain near-optimal  bounds.
Maximum Margin Multiclass Nearest Neighbors
Authors: Kontorovich, Aryeh and Weiss, Roi
Published in: Proceedings of the 31st International Conference on Machine Learning (Main Conference Track), 2014

Abstract: We develop a general framework for margin-based multicategory classification in metric spaces. The basic work-horse is a margin-regularized version of the nearest-neighbor classifier. We prove generalization bounds that match the state of the art in sample size n and significantly improve the dependence on the number of classes k. Our point of departure is a nearly Bayes-optimal finite-sample risk bound independent of k. Although k-free, this bound is unregularized and non-adaptive, which motivates our main result: Rademacher and scale-sensitive margin bounds with a logarithmic dependence on k. As the best previous risk estimates  in this setting were of order \sqrt k, our bound is exponentially sharper. From the algorithmic standpoint, in doubling metric spaces our classifier may be trained on n examples in  O(n^2łog n) time and evaluated on new points in O(łog n) time.