mtybilly/Instruct2DS huggingface dataset:
Max-Margin Multiple-Instance Dictionary Learning
Authors: Xinggang Wang, Baoyuan Wang, Xiang Bai, Wenyu Liu, Zhuowen Tu
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Dictionary learning has became an increasingly important task in machine learning, as it is fundamental to the representation problem. A number of emerging techniques specifically include a codebook learning step, in which a critical knowledge abstraction process is carried out. Existing approaches in dictionary (codebook) learning are either generative (unsupervised e.g. k-means) or discriminative (supervised e.g. extremely randomized forests). In this paper, we propose a multiple instance learning (MIL) strategy (along the line of weakly supervised learning) for dictionary learning. Each code is represented by a classifier, such as a linear SVM, which naturally performs metric fusion for multi-channel features. We design a formulation to simultaneously learn mixtures of codes by maximizing classification margins in MIL.  State-of-the-art results are observed in image classification benchmarks based on the learned codebooks, which observe both compactness and effectiveness.
Fast Semidifferential-based Submodular Function Optimization
Authors: Rishabh Iyer, Stefanie Jegelka, Jeff Bilmes
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We present a practical and powerful new framework for both unconstrained and constrained submodular function optimization based on discrete semidifferentials (sub- and super-differentials). The resulting algorithms, which repeatedly compute and then efficiently optimize submodular semigradients, offer new and generalize many old methods for submodular optimization.  Our approach, moreover, takes steps towards providing a unifying paradigm applicable to both submodular minimization and maximization, problems that historically have been treated quite distinctly. The practicality of our algorithms is important since interest in submodularity, owing to its natural and wide applicability, has recently been in ascendance within machine learning.  We analyze theoretical properties of our algorithms for minimization and maximization, and show that many state-of-the-art maximization algorithms are special cases. Lastly, we complement our theoretical analyses with supporting empirical experiments.
Kernelized Bayesian Matrix Factorization
Authors: Mehmet Gönen, Suleiman Khan, Samuel Kaski
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We extend kernelized matrix factorization with a fully Bayesian treatment and with an ability to work with multiple side information sources expressed as different kernels. Kernel functions have been introduced to matrix factorization to integrate side information about the rows and columns (e.g., objects and users in recommender systems), which is necessary for making out-of-matrix (i.e., cold start) predictions. We discuss specifically bipartite graph inference, where the output matrix is binary, but extensions to more general matrices are straightforward. We extend the state of the art in two key aspects: (i) A fully conjugate probabilistic formulation of the kernelized matrix factorization problem enables an efficient variational approximation, whereas fully Bayesian treatments are not computationally feasible in the earlier approaches. (ii) Multiple side information sources are included, treated as different kernels in multiple kernel learning that additionally reveals which side information sources are informative. Our method outperforms alternatives in predicting drug-protein interactions on two data sets. We then show that our framework can also be used for solving multilabel learning problems by considering samples and labels as the two domains where matrix factorization operates on. Our algorithm obtains the lowest Hamming loss values on 10 out of 14 multilabel classification data sets compared to five state-of-the-art multilabel learning algorithms.
Learning the Structure of Sum-Product Networks
Authors: Robert Gens, Domingos Pedro
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Sum-product networks (SPNs) are a new class of deep probabilistic models. SPNs can have unbounded treewidth but inference in them is always tractable. An SPN is either a univariate distribution, a product of SPNs over disjoint variables, or a weighted sum of SPNs over the same variables. We propose the first algorithm for learning the structure of SPNs that takes full advantage of their expressiveness. At each step, the algorithm attempts to divide the current variables into approximately independent subsets. If successful, it returns the product of recursive calls on the subsets; otherwise it returns the sum of recursive calls on subsets of similar instances from the current training set. A comprehensive empirical study shows that the learned SPNs are typically comparable to graphical models in likelihood but superior in inference speed and accuracy.
Quantile Regression for Large-scale Applications
Authors: Jiyan Yang, Xiangrui Meng, Michael Mahoney
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Quantile regression is a method to estimate the quantiles of the   conditional distribution of a response variable, and as such it permits a   much more accurate portrayal of the relationship between the response variable   and observed covariates than methods such as Least-squares or   Least Absolute Deviations regression.  It can be expressed as a linear program,   and   interior-point methods can be used to find a solution for  moderately large problems.  Dealing with very large problems, \emphe.g., involving data up to and   beyond the terabyte regime, remains a challenge.  Here, we present a randomized algorithm that runs in time that is nearly   linear in the size of the input and that, with constant probability,   computes a (1+ε) approximate solution to an arbitrary quantile   regression problem.  Our algorithm computes a low-distortion subspace-preserving  embedding with respect to the loss function of quantile regression.  Our empirical evaluation illustrates that our algorithm is competitive with   the best previous work on small to medium-sized problems, and that   it can be implemented in MapReduce-like environments and    applied to terabyte-sized problems.
Robust Regression on MapReduce
Authors: Xiangrui Meng, Michael Mahoney
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Although the MapReduce framework is now the \emphde facto standard for   analyzing massive data sets, many algorithms (in particular, many   iterative algorithms popular in machine learning, optimization, and linear   algebra) are hard to fit into MapReduce.   Consider, \emphe.g., the \ell_p regression problem: given a matrix   A ∈\mathbbR^m \times n and a vector b ∈\mathbbR^m, find a   vector x^* ∈\mathbbR^n that minimizes f(x) = \|A x - b\|_p.   The widely-used \ell_2 regression, \emphi.e., linear least-squares, is   known to be highly sensitive to outliers; and choosing p ∈[1, 2) can   help improve robustness.  In this work, we propose an efficient algorithm for solving strongly   over-determined (m ≫n) robust \ell_p regression problems to moderate precision on   MapReduce.  Our empirical results on data up to the terabyte scale demonstrate   that our algorithm is a significant improvement over traditional iterative algorithms on MapReduce   for \ell_1 regression, even for a fairly small number   of iterations.   In addition, our proposed interior-point cutting-plane method can also be   extended to solving more general convex problems on MapReduce.
Infinitesimal Annealing for Training Semi-Supervised Support Vector Machines
Authors: Kohei Ogawa, Motoki Imamura, Ichiro Takeuchi, Masashi Sugiyama
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The semi-supervised support vector machine (S3VM) is a maximum-margin classification algorithm based on both labeled and unlabeled data. Training S3VM involves either a combinatorial or non-convex optimization problem and thus finding the global optimal solution is intractable in practice. It has been demonstrated that a key to successfully find a good (local) solution of S3VM is to gradually increase the effect of unlabeled data, a la annealing. However, existing algorithms suffer from the trade-off between the resolution of annealing steps and the computation cost. In this paper, we go beyond this trade-off by proposing a novel training algorithm that efficiently performs annealing with an infinitesimal resolution. Through experiments, we demonstrate that the proposed infinitesimal annealing algorithm tends to produce better solutions with less computation time than existing approaches.
One-Pass AUC Optimization
Authors: Wei Gao, Rong Jin, Shenghuo Zhu, Zhi-Hua Zhou
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: AUC is an important performance measure and many algorithms have been devoted to AUC optimization, mostly by minimizing a surrogate convex loss on a training data set. In this work, we focus on one-pass AUC optimization that requires only going through the training data once without storing the entire training dataset, where conventional online learning algorithms cannot be applied directly because AUC is measured by a sum of losses defined over pairs of instances from different classes. We develop a regression-based algorithm which only needs to maintain the first and second order statistics of training data in memory, resulting a storage requirement independent from the size of training data. To efficiently handle high dimensional data, we develop a randomized algorithm that approximates the covariance matrices by low rank matrices. We verify, both theoretically and empirically, the effectiveness of the proposed algorithm.
Learning Convex QP Relaxations for Structured Prediction
Authors: Jeremy Jancsary, Sebastian Nowozin, Carsten Rother
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We introduce a new large margin approach to discriminative training of intractable discrete graphical models. Our approach builds on a convex quadratic programming relaxation of the MAP inference problem. The model parameters are trained directly within this restricted class of energy functions so as to optimize the predictions on the training data. We address the issue of how to parameterize the resulting model and point out its relation to existing approaches. The primary motivation behind our use of the QP relaxation is its computational efficiency; yet, empirically, its predictive accuracy compares favorably to more expensive approaches. This makes it an appealing choice for many practical tasks.
Concurrent Reinforcement Learning from Customer Interactions
Authors: David Silver, Leonard Newnham, David Barker, Suzanne Weller, Jason McFall
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper, we explore applications in which a company interacts concurrently with many customers. The company has an objective function, such as maximising revenue, customer satisfaction, or customer loyalty, which depends primarily on the sequence of interactions between company and customer. A key aspect of this setting is that interactions with different customers occur in parallel. As a result, it is imperative to learn online from partial interaction sequences, so that information acquired from one customer is efficiently assimilated and applied in subsequent interactions with other customers. We present the first framework for concurrent reinforcement learning, using a variant of temporal-difference learning to learn efficiently from partial interaction sequences.   We evaluate our algorithms in two large-scale test-beds for online and email interaction respectively, generated from a database of 300,000 customer records.
Saving Evaluation Time for the Decision Function in Boosting: Representation and Reordering Base Learner
Authors: Peng Sun, Jie Zhou
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: For a well trained Boosting classifier, we are interested in how to save the testing time, i.e., to make the decision without evaluating all the base learners. To address this problem, in previous work the base learners are sequentially calculated and early stopping is allowed if the decision function has been confident enough to output its value. In such a chain structure, the order of base learners is critical: better order can lead to less evaluation time.    In this paper, we present a novel method for ordering. We base our discussion on the data structure representing Boosting’s decision function. Viewing the decision function a boolean expression, we propose a Binary Valued Tree for its representation. As a secondary contribution, such a representation unifies the work by previous researchers and helps devise new representation. Also, its connection to Binary Decision Diagram(BDD) is discussed.
Stability and Hypothesis Transfer Learning
Authors: Ilja Kuzborskij, Francesco Orabona
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider the transfer learning scenario, where the learner does not have access to the source domain directly, but rather operates on the basis of hypotheses induced from it – the Hypothesis Transfer Learning (HTL) problem. Particularly, we conduct a theoretical analysis of HTL by considering the algorithmic stability of a class of HTL algorithms based on Regularized Least Squares with biased regularization. We show that the relatedness of source and target domains accelerates the convergence of the Leave-One-Out error to the generalization error, thus enabling the use of the Leave-One-Out error to find the optimal transfer parameters, even in the presence of a small training set. In case of unrelated domains we also suggest a theoretically principled way to prevent negative transfer, so that in the limit we recover the performance of the algorithm not using any knowledge from the source domain.
Fast Dual Variational Inference for Non-Conjugate Latent Gaussian Models
Authors: Mohammad Emtiyaz Khan, Aleksandr Aravkin, Michael Friedlander, Matthias Seeger
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Latent Gaussian models (LGMs) are widely used in statistics and machine learning.  Bayesian inference in non-conjugate LGM is difficult due to intractable integrals involving the Gaussian prior and non-conjugate likelihoods.  Algorithms based on Variational Gaussian (VG) approximations are widely employed since they strike a favorable balance between accuracy, generality, speed, and ease of use.  However, the structure of optimization problems associated with them    remains poorly understood, and standard solvers take too long to converge.  In this paper, we derive a novel dual variational inference approach, which exploits the convexity property of the VG approximations.   The implications of our approach is that we obtain an algorithm that solves a convex optimization problem, reduces the number of variational parameters, and converges much faster than previous methods.  Using real world data, we demonstrate these advantages on a variety of LGMs including Gaussian process classification and latent Gaussian Markov random fields.
Modeling Temporal Evolution and Multiscale Structure in Networks
Authors: Tue Herlau, Morten Mørup, Mikkel Schmidt
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Many real-world networks exhibit both temporal evolution and multiscale structure.  We propose a model for temporally correlated multifurcating hierarchies in complex networks which jointly capture both effects. We use the Gibbs fragmentation tree as prior over multifurcating trees and a change-point model to account for the temporal evolution of each vertex.  We demonstrate that our model is able to infer time-varying multiscale structure in synthetic as well as three real world time-evolving complex networks.  Our modeling of the temporal evolution of hierarchies brings new insights into the changing roles and position of entities and possibilities for better understanding these dynamic complex systems.
Dependent Normalized Random Measures
Authors: Changyou Chen, Vinayak Rao, Wray Buntine, Yee Whye Teh
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper we propose two constructions of dependent normalized random measures, a class of nonparametric priors over dependent probability measures. Our constructions, which we call mixed normalized random measures (MNRM) and thinned normalized random measures (TNRM), involve (respectively) weighting and thinning parts of a shared underlying Poisson process before combining them together. We show that both MNRM and TNRM are marginally normalized random measures, resulting in well understood theoretical properties. We develop marginal and slice samplers for both models, the latter necessary for inference in TNRM. In time-varying topic modelling experiments, both models exhibit superior performance over related dependent models such as the hierarchical Dirichlet process and the spatial normalized Gamma process.
Fast Max-Margin Matrix Factorization with Data Augmentation
Authors: Minjie Xu, Jun Zhu, Bo Zhang
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Existing max-margin matrix factorization (M3F) methods either are computationally inefficient or need a model selection procedure to determine the number of latent factors. In this paper we present a probabilistic M3F model that admits a highly efficient Gibbs sampling algorithm through data augmentation. We further extend our approach to incorporate Bayesian nonparametrics and build accordingly a truncation-free nonparametric M3F model where the number of latent factors is literally unbounded and inferred from data. Empirical studies on two large real-world data sets verify the efficacy of our proposed methods.
Natural Image Bases to Represent Neuroimaging Data
Authors: Ashish Gupta, Murat Ayhan, Anthony Maida
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Visual inspection of neuroimagery is susceptible to human eye limitations.  Computerized methods have been shown to be equally or more effective   than human clinicians in diagnosing dementia from neuroimages. Nevertheless,   much of the work involves the use of domain expertise to extract hand-crafted features. The key technique in this paper is the use of cross-domain features to represent MRI data.  We used a sparse autoencoder to learn a set of bases from natural images and   then applied convolution to extract features from the Alzheimer’s Disease Neuroimaging Initiative (ADNI) dataset.Using this new representation, we classify MRI instances into three categories: Alzheimer’s Disease (AD), Mild Cognitive Impairment (MCI) and Healthy Control (HC).Our approach, in spite of being very simple, achieved high classification performance,   which is competitive with or better than other approaches.
Breaking the Small Cluster Barrier of Graph Clustering
Authors: Nir Ailon, Yudong Chen, Huan Xu
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: This paper investigates graph clustering in the planted cluster model in the   presence of  \em small clusters. Traditional results dictate that for an   algorithm to provably correctly recover the clusters, \em all clusters must be   sufficiently large (in particular, \tildeΩ(\sqrtn) where n is the number   of nodes of the graph). We show that this is not really a restriction: by a more refined   analysis of the trace-norm based matrix recovery approach proposed in (Jalali et al. 2011) and (Chen et al. 2012), we prove that small clusters, under certain mild assuptions, do not hinder recovery of large ones.  Based on this result, we further devise an iterative algorithm   to recover \em almost all clusters via a “peeling strategy”, i.e., recover large clusters   first, leading to a reduced problem, and repeat this procedure.   These results are extended to the    \em partial observation setting, in which only a (chosen) part of the graph is observed.  The peeling strategy gives rise to an active learning algorithm, in which   edges adjacent to smaller clusters are queried more often as large clusters are learned  (and removed).  Our findings are supported by experiments.    From a high level, this paper sheds novel insights on high-dimesional statistics and   learning structured data, by presenting a structured matrix learning problem for which  a one shot convex relaxation approach necessarily fails, but a carefully constructed sequence of convex relaxations  does the job.
Approximate Inference in Collective Graphical Models
Authors: Daniel Sheldon, Tao Sun, Akshat Kumar, Tom Dietterich
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We study the problem of approximate inference in collective graphical models (CGMs), which were recently introduced to model the problem of learning and inference with noisy aggregate observations. We first analyze the complexity of inference in CGMs: unlike inference in conventional graphical models, exact inference in CGMs is NP-hard even for tree-structured models. We then develop a tractable convex approximation to the NP-hard MAP inference problem in CGMs, and show how to use MAP inference for approximate marginal inference within the EM framework. We demonstrate empirically that these approximation techniques can reduce the computational cost of inference by two orders of magnitude and the cost of learning by at least an order of magnitude while providing solutions of equal or better quality.
Scaling the Indian Buffet Process via Submodular Maximization
Authors: Colorado Reed, Ghahramani Zoubin
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Inference for latent feature models is inherently difficult as the inference space grows exponentially with the size of the input data and number of latent features. In this work, we use Kurihara & Wellings (2008)’s maximization-expectation framework to perform approximate MAP inference for linear-Gaussian latent feature models with an Indian Buffet Process (IBP) prior. This formulation yields a submodular function of the features that corresponds to a lower bound on the model evidence. By adding a constant to this function, we obtain a nonnegative submodular function that can be maximized via a greedy algorithm that obtains at least a 1/3-approximation to the optimal solution. Our inference method scales linearly with the size of the input data, and we show the efficacy of our method on the largest datasets currently analyzed using an IBP model.
Mini-Batch Primal and Dual Methods for SVMs
Authors: Martin Takac, Avleen Bijral, Peter Richtarik, Nati Srebro
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We address the issue of using mini-batches in stochastic  optimization of SVMs. We show that the same quantity, the  spectral norm of the data, controls the parallelization  speedup obtained for both primal stochastic subgradient descent(SGD) and stochastic dual coordinate ascent (SCDA) methods and use it to derive novel variants of mini-batched SDCA. Our guarantees for both methods are expressed in terms of the original nonsmooth primal problem based on the hinge-loss.
The lasso, persistence, and cross-validation
Authors: Darren Homrighausen, Daniel McDonald
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: During the last fifteen years, the lasso procedure has been the target of a substantial amount of theoretical and applied research. Correspondingly, many results are known about its behavior for a fixed or optimally chosen smoothing parameter (given up to unknown constants). Much less, however, is known about the lasso’s behavior when the smoothing parameter is chosen in a data dependent way. To this end, we give the first result about the risk consistency of lasso when the smoothing parameter is chosen via cross-validation. We consider the high-dimensional setting wherein the number of predictors p=n^α, α>0 grows with the number of observations.
Spectral Experts for Estimating Mixtures of Linear Regressions
Authors: Arun Tejasvi Chaganty, Percy Liang
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Discriminative latent-variable models are typically learned using EM or gradient-based optimization, which suffer from local optima.  In this paper, we develop a new computationally efficient and provably consistent estimator for the mixture of linear regressions, a simple instance of discriminative latent-variable models.  Our approach relies on a low-rank linear regression to recover a symmetric tensor, which can be factorized into the parameters using the tensor power method.  We prove rates of convergence for our estimator and provide an empirical evaluation illustrating its strengths relative to local optimization (EM).
Distribution to Distribution Regression
Authors: Junier Oliva, Barnabas Poczos, Jeff Schneider
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We analyze ’Distribution to Distribution regression’ where one is regressing a mapping where both the covariate (inputs) and response (outputs) are distributions. No parameters on the input or output distributions are assumed, nor are any strong assumptions made on the measure from which input distributions are drawn from. We develop an estimator and derive an upper bound for the L2 risk; also, we show that when the effective dimension is small enough (as measured by the doubling dimension), then the risk converges to zero with a polynomial rate.
Regularization of Neural Networks using DropConnect
Authors: Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, Rob Fergus
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We introduce DropConnect, a generalization of DropOut, for regularizing large fully-connected layers within neural networks. When training with Dropout, a randomly selected subset of activations are set to zero within each layer. DropConnect instead sets a randomly selected subset of weights within the network to zero. Each unit thus receives input from a random subset of units in the previous layer. We derive a bound on the generalization performance of both Dropout and DropConnect. We then evaluate DropConnect on a range of datasets, comparing to Dropout, and show state-of-the-art results on several image recoginition benchmarks can be obtained by aggregating multiple DropConnect-trained models.
Gaussian Process Kernels for Pattern Discovery and Extrapolation
Authors: Andrew Wilson, Ryan Adams
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Gaussian processes are rich distributions over functions, which provide a Bayesian nonparametric approach to smoothing and interpolation.  We introduce simple closed form kernels that can be used with Gaussian processes to discover patterns and enable extrapolation.  These kernels are derived by modelling a spectral density – the Fourier transform of a kernel – with a Gaussian mixture.  The proposed kernels support a broad class of stationary covariances, but Gaussian process inference remains simple and analytic.  We demonstrate the proposed kernels by discovering patterns and performing long range extrapolation on synthetic examples, as well as atmospheric CO2 trends and airline passenger data.  We also show that it is possible to reconstruct several popular standard covariances within our framework.
Anytime Representation Learning
Authors: Zhixiang Xu, Matt Kusner, Gao Huang, Kilian Weinberger
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Evaluation cost during test-time is becoming increasingly important as many real-world applications need fast evaluation (e.g. web search engines, email spam filtering) or use expensive features (e.g. medical diagnosis). We introduce Anytime Feature Representations (AFR), a novel algorithm that explicitly addresses this trade-off in the data representation rather than in the classifier. This enables us to turn conventional classifiers, in particular Support Vector Machines, into test-time cost sensitive <i>anytime classifiers</i> - combining the advantages of anytime learning and large-margin classification.
Algorithms for Direct 0--1 Loss Optimization in Binary Classification
Authors: Tan Nguyen, Scott Sanner
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: While convex losses for binary classification are attractive due to the existence of numerous (provably) efficient methods for finding their global optima, they are sensitive to outliers.  On the other hand, while the non-convex 0–1 loss is robust to outliers, it is NP-hard to optimize and thus rarely directly optimized in practice.  In this paper, however, we do just that: we explore a variety of practical methods for direct (approximate) optimization of the 0–1 loss based on branch and bound search, combinatorial search, and coordinate descent on smooth, differentiable relaxations of 0–1 loss. Empirically, we compare our proposed algorithms to logistic regression, SVM, and the Bayes point machine showing that the proposed 0–1 loss optimization algorithms perform at least as well and offer a clear advantage in the presence of outliers.  To this end, we believe this work reiterates the importance of 0–1 loss and its robustness properties while challenging the notion that it is difficult to directly optimize.
Top-k Selection based on Adaptive Sampling of Noisy Preferences
Authors: Robert Busa-Fekete, Balazs Szorenyi, Weiwei Cheng, Paul Weng, Eyke Huellermeier
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider the problem of reliably selecting an optimal subset of fixed size from a given set of choice alternatives, based on noisy information about the quality of these alternatives. Problems of similar kind have been tackled by means of adaptive sampling schemes called racing algorithms. However, in contrast to existing approaches, we do not assume that each alternative is characterized by a real-valued random variable, and that samples are taken from the corresponding distributions. Instead, we only assume that alternatives can be compared in terms of pairwise preferences. We propose and formally analyze a general preference-based racing algorithm that we instantiate with three specific ranking procedures and corresponding sampling schemes. Experiments with real and synthetic data are presented to show the efficiency of our approach.
The Extended Parameter Filter
Authors: Yusuf Bugra Erol, Lei Li, Bharath Ramsundar, Russell Stuart
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The parameters of temporal models, such as dynamic Bayesian networks, may be modelled in a Bayesian context as static or atemporal variables that influence transition probabilities at every time step. Particle filters fail for models that include such variables, while methods that use Gibbs sampling of parameter variables may incur a per-sample cost that grows linearly with the length of the observation sequence. Storvik devised a method for incremental computation of exact sufficient statistics that, for some cases, reduces the per-sample cost to a constant.  In this paper, we demonstrate a connection between Storvik’s filter and a Kalman filter in parameter space and establish more general conditions under which Storvik’s filter works. Drawing on an analogy to the extended Kalman filter, we develop and analyze, both theoretically and experimentally, a Taylor approximation to the parameter posterior that allows Storvik’s method to be applied to a broader class of models. Our experiments on both synthetic examples and real applications show improvement over existing methods.
Exploiting Ontology Structures and Unlabeled Data for Learning
Authors: Nina Balcan, Avrim Blum, Yishay Mansour
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We present and analyze a theoretical model designed to understand and  explain the effectiveness of ontologies for learning multiple related  tasks from primarily unlabeled data.  We present both  information-theoretic results as well as efficient algorithms.    We show in this model that an ontology, which specifies the  relationships between multiple outputs, in some cases is sufficient  to completely learn a classification using a large unlabeled data  source.
O(logT) Projections for Stochastic Optimization of Smooth and Strongly Convex Functions
Authors: Lijun Zhang, Tianbao Yang, Rong Jin, Xiaofei He
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Traditional algorithms for stochastic optimization require projecting the solution at each iteration into a given domain to ensure its feasibility. When facing complex domains, such as the positive semidefinite cone, the projection operation can be expensive, leading to a high computational cost per iteration. In this paper, we present a novel algorithm that aims to reduce the number of projections for stochastic optimization. The proposed algorithm combines the strength of several recent developments in stochastic optimization, including mini-batches, extra-gradient, and epoch gradient descent, in order to effectively explore the smoothness and strong convexity. We show, both in expectation and with a high probability, that when the objective function is both smooth and strongly convex, the proposed algorithm achieves the optimal O(1/T) rate of convergence with only O(logT) projections. Our empirical study verifies the theoretical result.
Optimizing the F-Measure in Multi-Label Classification: Plug-in Rule Approach versus Structured Loss Minimization
Authors: Krzysztof Dembczynski, Arkadiusz Jachnik, Wojciech Kotlowski, Willem Waegeman, Eyke Huellermeier
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We compare the plug-in rule approach for optimizing the F-measure in multi-label classification with an approach based on structured loss minimization, such as the structured support vector machine (SSVM). Whereas the former derives an optimal prediction from a probabilistic model in a separate inference step, the latter seeks to optimize the F-measure directly during the training phase. We introduce a novel plug-in rule algorithm that estimates all parameters required for a Bayes-optimal prediction via a set of multinomial regression models, and we compare this algorithm with SSVMs in terms of computational complexity and statistical consistency. As a main theoretical result, we show that our plug-in rule algorithm is consistent, whereas the SSVM approaches are not. Finally, we present results of a large experimental study showing the benefits of the introduced algorithm.
On the importance of initialization and momentum in deep learning
Authors: Ilya Sutskever, James Martens, George Dahl, Geoffrey Hinton
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Deep and recurrent neural networks (DNNs and RNNs respectively) are powerful models that were considered to be almost impossible to train using stochastic gradient descent with momentum. In this paper, we show that when stochastic gradient descent with momentum uses a well-designed random initialization and a particular type of slowly increasing schedule for the momentum parameter, it can train both DNNs and RNNs (on datasets with long-term dependencies) to levels of performance that were previously achievable only with Hessian-Free optimization. We find that both the initialization and the momentum are crucial since poorly initialized networks cannot be trained with momentum and well-initialized networks perform markedly worse when the momentum is absent or poorly tuned.     Our success training these models suggests that previous attempts to train deep and recurrent neural networks from random initializations have likely failed due to poor initialization schemes. Furthermore, carefully tuned momentum methods suffice for dealing with the curvature issues in deep and recurrent network training objectives without the need for sophisticated second-order methods.
A non-IID Framework for Collaborative Filtering with Restricted Boltzmann Machines
Authors: Kostadin Georgiev, Preslav Nakov
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We propose a framework for collaborative filtering based on Restricted Boltzmann Machines (RBM), which extends previous RBM-based approaches in several important directions. First, while previous RBM research has focused on modeling the correlation between item ratings, we model both user-user and item-item correlations in a unified hybrid non-IID framework. We further use real values in the visible layer as opposed to multinomial variables, thus taking advantage of the natural order between user-item ratings. Finally, we explore the potential of combining the original training data with data generated by the RBM-based model itself in a bootstrapping fashion. The evaluation on two MovieLens datasets (with 100K and 1M user-item ratings, respectively), shows that our RBM model rivals the best previously-proposed approaches.
Intersecting singularities for multi-structured estimation
Authors: Emile Richard, Francis BACH, Jean-Philippe Vert
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We address the problem of designing a convex nonsmooth regularizer encouraging multiple structural effects simultaneously. Focusing on the inference of sparse and low-rank matrices we suggest a new complexity index and a convex penalty approximating it. The new penalty term can be written as the trace norm of a linear function of the matrix. By analyzing theoretical properties of this family of regularizers  we come up with oracle inequalities and compressed sensing results ensuring the quality of our regularized estimator. We also provide algorithms and supporting numerical experiments.
Structure Discovery in Nonparametric Regression through Compositional Kernel Search
Authors: David Duvenaud, James Lloyd, Roger Grosse, Joshua Tenenbaum, Ghahramani Zoubin
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Despite its importance, choosing the structural form of the kernel in nonparametric regression remains a black art. We define a space of kernel structures which are built compositionally by adding and multiplying a small number of base kernels. We present a method for searching over this space of structures which mirrors the scientific discovery process. The learned structures can often decompose functions into interpretable components and enable long-range extrapolation on time-series datasets. Our structure search method outperforms many widely used kernels and kernel combination methods on a variety of prediction tasks.
Copy or Coincidence? A Model for Detecting Social Influence and Duplication Events
Authors: Lisa Friedland, David Jensen, Michael Lavine
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper, we analyze the task of inferring rare links between pairs of entities that seem too similar to have occurred by chance. Variations of this task appear in such diverse areas as social network analysis, security, fraud detection, and entity resolution. To address the task in a general form, we propose a simple, flexible mixture model in which most entities are generated independently from a distribution but a small number of pairs are constrained to be similar. We predict the true pairs using a likelihood ratio that trades off the entities’ similarity with their rarity. This method always outperforms using only similarity; however, with certain parameter settings, similarity turns out to be surprisingly competitive. Using real data, we apply the model to detect twins given their birth weights and to re-identify cell phone users based on distinctive usage patterns.
Smooth Operators
Authors: Steffen Grunewalder, Gretton Arthur, John Shawe-Taylor
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We develop a generic approach to form smooth versions of basic mathematical operations like multiplication, composition, change of measure, and conditional expectation, among others.   Operations which result in functions outside the reproducing kernel Hilbert space (such as the product of two RKHS functions) are approximated via a natural cost function, such that the solution is guaranteed to be in the targeted RKHS. This approximation problem is reduced to a regression problem using an adjoint trick, and solved in a vector-valued RKHS, consisting of continuous, linear, smooth operators which map from an input, real-valued RKHS to the desired target RKHS. Important constraints, such as an almost everywhere positive density, can be enforced or approximated naturally in this framework, using convex constraints on the operators. Finally, smooth operators can be composed to accomplish more complex machine learning tasks, such as the sum rule and kernelized approximate Bayesian inference, where state-of-the-art convergence rates are obtained.
The Cross-Entropy Method Optimizes for Quantiles
Authors: Sergiu Goschin, Ari Weinstein, Michael Littman
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Cross-entropy optimization (CE) has proven to be a powerful tool for search in control environments. In the basic scheme, a distribution over proposed solutions is repeatedly adapted by evaluating a sample of solutions and refocusing the distribution on a percentage of those with the highest scores.  We show that, in the kind of noisy evaluation environments that are common in decision-making domains, this percentage-based refocusing does not optimize the expected utility of solutions, but instead a quantile metric. We provide a variant of CE (Proportional CE) that effectively optimizes the expected value. We show using variants of established noisy environments that Proportional CE can be used in place of CE and can improve solution quality.
Topic Discovery through Data Dependent and Random Projections
Authors: Weicong Ding, Mohammad Hossein Rohban, Prakash Ishwar, Venkatesh Saligrama
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We present algorithms for topic modeling based on the geometry of cross-document word-frequency patterns. This perspective gains significance under the so called separability condition. This is a condition on existence of novel-words that are unique to each topic. We present a suite of highly efficient algorithms with provable guarantees based on data-dependent and random projections to identify novel words and associated topics. Our key insight here is that the maximum and minimum values of cross-document frequency patterns projected along any direction are associated with novel words. While our sample complexity bounds for topic recovery are similar to the state-of-art, the computational complexity of our random projection scheme scales linearly with the number of documents and the number of words per document. We present several experiments on synthetic and realworld datasets to demonstrate qualitative and quantitative merits of our scheme.
Bayesian Learning of Recursively Factored Environments
Authors: Marc Bellemare, Joel Veness, Michael Bowling
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Model-based reinforcement learning techniques have historically encountered a number of difficulties scaling up to large observation spaces. One promising approach has been to decompose the model learning task into a number of smaller, more manageable sub-problems by factoring the observation space. Typically, many different factorizations are possible, which can make it difficult to select an appropriate factorization without extensive testing. In this paper we introduce the class of recursively decomposable factorizations, and show how exact Bayesian inference can be used to efficiently guarantee predictive performance close to the best factorization in this class. We demonstrate the strength of this approach by presenting a collection of empirical results for 20 different Atari 2600 games.
Selective sampling algorithms for cost-sensitive multiclass prediction
Authors: Alekh Agarwal
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper, we study the problem of active learning for cost-sensitive multiclass classification. We propose selective  sampling algorithms, which process the data in a streaming fashion,  querying only a subset of the labels. For these algorithms, we analyze the regret and label complexity when the labels are generated according to a generalized linear model. We establish that the gains of active learning over passive learning can range from none to exponentially large, based on a natural notion of margin. We also  present a safety guarantee to guard against model mismatch. Numerical  simulations show that our algorithms indeed obtain a low regret with a  small number of queries.
The Bigraphical Lasso
Authors: Alfredo Kalaitzis, John Lafferty, Neil D. Lawrence, Shuheng Zhou
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The i.i.d. assumption in machine learning is endemic, but often flawed. Complex data sets exhibit partial correlations between both instances and features. A model specifying both types of correlation can have a number of parameters that scales quadratically with the number of features and data points. We introduce the bigraphical lasso, an estimator for precision matrices of matrix-normals based on the Cartesian product of graphs. A prominent product in spectral graph theory, this structure has appealing properties for regression, enhanced sparsity and interpretability. To deal with the parameter explosion we introduce L1 penalties and fit the model through a flip-flop algorithm that results in a linear number of lasso regressions.