mtybilly/Instruct2DS huggingface dataset:
A Structural SVM Based Approach for Optimizing Partial AUC
Authors: Narasimhan, Harikrishna and Agarwal, Shivani
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The area under the ROC curve (AUC) is a widely used performance measure in machine learning. Increasingly, however, in several applications, ranging from ranking and biometric screening to medical diagnosis, performance is measured not in terms of the full area under the ROC curve, but instead, in terms of the partial area under the ROC curve between two specified false positive rates. In this paper, we develop a structural SVM framework for directly optimizing the partial AUC between any two false positive rates. Our approach makes use of a cutting plane solver along the lines of the structural SVM based approach for optimizing the full AUC developed by Joachims (2005). Unlike the full AUC, where the combinatorial optimization problem needed to find the most violated constraint in the cutting plane solver can be decomposed easily to yield an efficient algorithm, the corresponding optimization problem in the case of partial AUC is harder to decompose. One of our key technical contributions is an efficient algorithm for solving this combinatorial optimization problem that has the same computational complexity as Joachims’ algorithm for optimizing the usual AUC. This allows us to efficiently optimize the partial AUC in any desired false positive range. We demonstrate the approach on a variety of real-world tasks.
Loss-Proportional Subsampling for Subsequent ERM
Authors: Mineiro, Paul and Karampatziakis, Nikos
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We propose a sampling scheme suitable for reducing a data set prior to  selecting a hypothesis with minimum empirical risk.  The sampling only  considers a subset of the ultimate (unknown) hypothesis set, but can  nonetheless guarantee that the final excess risk will compare favorably  with utilizing the entire original data set. We demonstrate the practical  benefits of our approach on a large dataset which we subsample and  subsequently fit with boosted trees.
Convex Relaxations for Learning Bounded-Treewidth Decomposable Graphs
Authors: Kumar, K. S. Sesh and Bach, Francis
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider the problem of learning the structure of undirected graphical models with bounded treewidth, within the maximum likelihood framework. This is an NP-hard problem and most approaches consider local search techniques. In this paper, we pose it as a combinatorial optimization problem, which is then relaxed to a convex optimization problem that involves searching over the forest and hyperforest polytopes with special structures. A supergradient method is used to solve the dual problem, with a run-time complexity of O(k^3 n^k+2 łog n) for each iteration, where n is the number of variables and k is a bound on the treewidth. We compare our approach to state-of-the-art methods on synthetic datasets and classical benchmarks, showing the gains of the novel convex approach.
Scalable Simple Random Sampling and Stratified Sampling
Authors: Meng, Xiangrui
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Analyzing data sets of billions of records has now become a regular task in    many companies and institutions.    In the statistical analysis of those massive data sets, sampling generally    plays a very important role.    In this work, we describe a scalable simple random sampling algorithm, named    ScaSRS, which uses probabilistic thresholds to decide on the fly whether to    accept, reject, or wait-list an item independently of others.    We prove, with high probability, it succeeds and needs only O(\sqrtk)    storage, where k is the sample size.    ScaSRS extends naturally to a scalable stratified sampling algorithm, which is    favorable for heterogeneous data sets.    The proposed algorithms, when implemented in MapReduce, can effectively reduce    the size of intermediate output and greatly improve load balancing.    Empirical evaluation on large-scale data sets clearly demonstrates their    superiority.
Adaptive Task Assignment for Crowdsourced Classification
Authors: Ho, Chien-Ju and Jabbari, Shahin and Vaughan, Jennifer Wortman
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Crowdsourcing markets have gained popularity as a tool for inexpensively collecting data from diverse populations of workers. Classification tasks, in which workers provide labels (such as “offensive” or “not offensive”) for instances (such as websites), are among the most common tasks posted, but due to a mix of human error and the overwhelming prevalence of spam, the labels collected are often noisy. This problem is typically addressed by collecting labels for each instance from multiple workers and combining them in a clever way. However, the question of how to choose which tasks to assign to each worker is often overlooked. We investigate the problem of task assignment and label inference for heterogeneous classification tasks. By applying online primal-dual techniques, we derive a provably near-optimal adaptive assignment algorithm. We show that adaptively assigning workers to tasks can lead to more accurate predictions at a lower cost when the available workers are diverse.
Riemannian Similarity Learning
Authors: Cheng, Li
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider a similarity-score based paradigm to address scenarios where either the class labels are only partially revealed during learning, or the training and testing data are drawn from heterogeneous sources. The learning problem is subsequently formulated as optimization over a bilinear form of fixed rank. Our paradigm bears similarity to metric learning, where the major difference lies in its aim of learning a rectangular similarity matrix, instead of a proper metric. We tackle this problem in a Riemannian optimization framework. In particular, we consider its applications in pairwise-based action recognition, and cross-domain image-based object recognition. In both applications, the proposed algorithm produces competitive performance on respective benchmark datasets.
Optimal Regret Bounds for  Selecting the State Representation in Reinforcement Learning
Authors: Maillard, Odalric-Ambrym and Nguyen, Phuong and Ortner, Ronald and Ryabko, Daniil
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider an agent interacting with an environment in a single stream of actions, observations, and rewards, with no reset. This process is not assumed to be a Markov Decision Process (MDP). Rather, the agent has several representations (mapping histories of past interactions to a discrete state space) of the environment with unknown dynamics, only some of which result in an MDP. The goal is to minimize the average regret criterion against an agent who knows   an MDP representation giving the highest optimal reward, and acts optimally in it. Recent regret bounds for this setting are of order O(T^2/3) with an additive term constant yet exponential in some characteristics of the optimal MDP.  We propose an algorithm whose regret after T time steps is O(\sqrtT),  with all constants reasonably small.  This is optimal in T since O(\sqrtT) is the optimal regret in the setting of learning in a (single discrete) MDP.
On Compact Codes for Spatially Pooled Features
Authors: Jia, Yangqing and Vinyals, Oriol and Darrell, Trevor
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Feature encoding with an overcomplete dictionary has demonstrated good performance in many applications, especially computer vision. In this paper we analyze the classification accuracy with respect to dictionary size by linking the encoding stage to kernel methods and \nystrom sampling, and obtain useful bounds on accuracy as a function of size. The \nystrom method also inspires us to revisit dictionary learning from local patches, and we propose to learn the dictionary in an end-to-end fashion taking into account pooling, a common computational layer in vision. We validate our contribution by showing how the derived bounds are able to explain the observed behavior of multiple datasets, and show that the pooling aware method efficiently reduces the dictionary size by a factor of two for a given accuracy.
Better Mixing via Deep Representations
Authors: Bengio, Yoshua and Mesnil, Gregoire and Dauphin, Yann and Rifai, Salah
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: It has been hypothesized, and supported with experimental evidence, that deeper representations, when well trained, tend to do a better job at disentangling the underlying factors of variation.  We study the following related conjecture: better representations, in the sense of better disentangling, can be exploited to produce Markov chains that mix faster between modes. Consequently, mixing between modes would be more efficient at higher levels of representation.  To better understand this, we propose a secondary conjecture: the higher-level samples fill more uniformly the space they occupy and the high-density manifolds tend to unfold when represented at higher levels.  The paper discusses these hypotheses and tests them experimentally through visualization and measurements of mixing between modes and interpolating between samples.
Dynamic Covariance Models for Multivariate Financial Time Series
Authors: Wu, Yue and Miguel Hernandez-Lobato, Jose and Zoubin, Ghahramani
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The accurate prediction of time-changing covariances is an important problem in the modeling of multivariate financial data. However, some of the most popular models suffer from a) overfitting problems and multiple local optima, b) failure to capture shifts in market conditions and c) large computational costs. To address these problems we introduce a novel dynamic model for time-changing covariances. Over-fitting and local optima are avoided by following a Bayesian approach instead of computing point estimates. Changes in market conditions are captured by assuming a diffusion process in parameter values, and finally computationally efficient and scalable inference is performed using particle filters. Experiments with financial data show excellent performance of the proposed method with respect to current standard models.
Online Latent Dirichlet Allocation with Infinite Vocabulary
Authors: Zhai, Ke and Boyd-Graber, Jordan
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Topic models based on latent Dirichlet allocation (LDA) assume a predefined vocabulary a priori. This is reasonable in batch settings, but it is not reasonable when data are revealed over time, as is the case with streaming / online algorithms. To address this lacuna, we extend LDA by drawing topics from a Dirichlet process whose base distribution is a distribution over all strings rather than from a finite Dirichlet. We develop inference using online variational inference and because we only can consider a finite number of words for each truncated topic propose heuristics to dynamically organize, expand, and contract the set of words we consider in our vocabulary truncation. We show our model can successfully incorporate new words as it encounters new terms and that it performs better than online LDA in evaluations of topic quality and classification performance.
Revisiting the Nystrom method for improved large-scale machine learning
Authors: Gittens, Alex and Mahoney, Michael
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We reconsider randomized algorithms for the low-rank approximation of SPSD matrices such as Laplacian and kernel matrices that arise in data analysis and machine learning applications.    Our main results consist of an empirical evaluation of the performance quality and running time of sampling and projection methods on a diverse suite of SPSD matrices. Our results highlight complementary aspects of sampling versus projection methods, and they point to differences between uniform and nonuniform sampling methods based on leverage scores.    We complement our empirical results with a suite of worst-case theoretical bounds for both random sampling and random projection methods. These bounds are qualitatively superior to existing bounds— e.g., improved additive-error bounds for spectral and Frobenius norm error and relative-error bounds for trace norm error.
Characterizing the Representer Theorem
Authors: Yu, Yaoliang and Cheng, Hao and Schuurmans, Dale and Szepesvari, Csaba
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The representer theorem assures that kernel methods retain optimality under penalized empirical risk minimization. While a sufficient condition on the form of the regularizer guaranteeing the representer theorem has been known since the initial development of kernel methods, necessary conditions have only been investigated recently. In this paper we completely characterize the necessary and sufficient conditions on the regularizer that ensure the representer theorem holds. The results are surprisingly simple yet broaden the conditions where the representer theorem is known to hold. Extension to the matrix domain is also addressed.
Infinite Positive Semidefinite Tensor Factorization for Source Separation of Mixture Signals
Authors: Yoshii, Kazuyoshi and Tomioka, Ryota and Mochihashi, Daichi and Goto, Masataka
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: This paper presents a new class of tensor factorization called positive semidefinite tensor factorization (PSDTF) that decomposes a set of positive semidefinite (PSD) matrices into the convex combinations of fewer PSD basis matrices. PSDTF can be viewed as a natural extension of nonnegative matrix factorization. One of the main problems of PSDTF is that an appropriate number of bases should be given in advance. To solve this problem, we propose a nonparametric Bayesian model based on a gamma process that can instantiate only a limited number of necessary bases from the infinitely many bases assumed to exist. We derive a variational Bayesian algorithm for closed-form posterior inference and a multiplicative update rule for maximum-likelihood estimation. We evaluated PSDTF on both synthetic data and real music recordings to show its superiority.
Dynamical Models and tracking regret in online convex programming
Authors: Hall, Eric and Willett, Rebecca
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: This paper describes a new online convex optimization method which incorporates a family of candidate dynamical models and establishes novel tracking regret bounds that scale with comparator’s deviation from the best dynamical model in this family. Previous online optimization methods are designed to have a total accumulated loss comparable to that of the best comparator sequence, and existing tracking or shifting regret bounds scale with the overall variation of the comparator sequence. In many practical scenarios, however, the environment is nonstationary and comparator sequences with small variation are quite weak, resulting in large losses. The proposed dynamic mirror descent method, in contrast, can yield low regret relative to highly variable comparator sequences by both tracking the best dynamical model and forming predictions based on that model. This concept is demonstrated empirically in the context of sequential compressive observations of a dynamic scene and tracking a dynamic social network.
A Unified Robust Regression Model for Lasso-like Algorithms
Authors: Yang, Wenzhuo and Xu, Huan
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We develop a unified robust linear regression model and show that it is equivalent to a general regularization framework to encourage sparse-like structure that contains group Lasso and fused Lasso as specific examples. This provides a robustness interpretation of these widely applied Lasso-like algorithms, and allows us to construct novel generalizations of Lasso-like algorithms by considering different uncertainty sets. Using this robustness interpretation, we present new sparsity results, and establish the statistical consistency of the proposed regularized linear regression. This work extends a classical result from Xu et al. (2010) that relates standard Lasso with robust linear regression to learning problems with more general sparse-like structures, and provides new robustness-based tools to to understand learning problems with sparse-like structures.
Large-Scale Bandit Problems and KWIK Learning
Authors: Abernethy, Jacob and Amin, Kareem and Kearns, Michael and Draief, Moez
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We show that parametric multi-armed bandit (MAB) problems with large state and action spaces can be algorithmically reduced to the supervised learning model known as Knows What It Knows or KWIK learning. We give matching impossibility results showing that the KWIK learnability requirement cannot be replaced by weaker supervised learning assumptions. We provide such results in both the standard parametric MAB setting, as well as for a new model in which the action space is finite but growing with time.
Quickly Boosting Decision Trees -- Pruning Underachieving Features Early
Authors: Appel, Ron and Fuchs, Thomas and Dollar, Piotr and Perona, Pietro
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Boosted decision trees are one of the most popular and successful learning techniques used today.  While exhibiting fast speeds at test time, relatively slow training makes them impractical for applications with real-time learning requirements. We propose a principled approach to overcome this drawback. We prove a bound on the error of a decision stump given its preliminary error on a subset of the training data; the bound may be used to prune unpromising features early on in the training process. We propose a fast training algorithm that exploits this bound, yielding speedups of an order of magnitude at no cost in the final performance of the classifier. Our method is not a new variant of Boosting; rather, it may be used in conjunction with existing Boosting algorithms and other sampling heuristics to achieve even greater speedups.
Vanishing Component Analysis
Authors: Livni, Roi and Lehavi, David and Schein, Sagi and Nachliely, Hila and Shalev-Shwartz, Shai and Globerson, Amir
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The vanishing ideal of a set of n points S, is the set of all polynomials that attain the value of zero on all the points in S. Such ideals can be compactly represented using a small set of polynomials known as generators of the ideal. Here we describe and analyze an efficient procedure that constructs a set of generators of a vanishing ideal. Our procedure is numerically stable, and can be used to find approximately vanishing polynomials.  The resulting polynomials capture nonlinear structure in data, and can for example be used within supervised learning. Empirical comparison with kernel methods show that our method constructs more compact classifiers with comparable accuracy.
On the Statistical Consistency of Algorithms for Binary Classification under Class Imbalance
Authors: Menon, Aditya and Narasimhan, Harikrishna and Agarwal, Shivani and Chawla, Sanjay
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Class imbalance situations, where one class is rare compared to the other, arise frequently in machine learning applications. It is well known that the usual misclassification error is ill-suited for measuring performance in such settings. A wide range of performance measures have been proposed for this problem, in machine learning as well as in data mining, artificial intelligence, and various applied fields. However, despite the large number of studies on this problem, little is understood about the statistical consistency of the algorithms proposed with respect to the performance measures of interest. In this paper, we study consistency with respect to one such performance measure, namely the arithmetic mean of the true positive and true negative rates (AM), and establish that some simple methods that have been used in practice, such as applying an empirically determined threshold to a suitable class probability estimate or performing an empirically balanced form of risk minimization, are in fact consistent with respect to the AM (under mild conditions on the underlying distribution). Our results employ balanced losses that have been used recently in analyses of ranking problems (Kotlowski et al., 2011) and build on recent results on consistent surrogates for cost-sensitive losses (Scott, 2012). Experimental results confirm our consistency theorems.
Learning an Internal Dynamics Model from Control Demonstration
Authors: Golub, Matthew and Chase, Steven and Yu, Byron
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Much work in optimal control and inverse control has assumed that the controller has perfect knowledge of plant dynamics.  However, if the controller is a human or animal subject, the subject’s internal dynamics model may differ from the true plant dynamics.  Here, we consider the problem of learning the subject’s internal model from demonstrations of control and knowledge of task goals.  Due to sensory feedback delay, the subject uses an internal model to generate an internal prediction of the current plant state, which may differ from the actual plant state.  We develop a probabilistic framework and exact EM algorithm to jointly estimate the internal model, internal state trajectories, and feedback delay. We applied this framework to demonstrations by a nonhuman primate of brain-machine interface (BMI) control. We discovered that the subject’s internal model deviated from the true BMI plant dynamics and provided significantly better explanation of the recorded neural control signals than did the true plant dynamics.
Topic Model Diagnostics: Assessing Domain Relevance via Topical Alignment
Authors: Chuang, Jason and Gupta, Sonal and Manning, Christopher and Heer, Jeffrey
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The use of topic models to analyze domain-specific texts often requires manual validation of the latent topics to ensure they are meaningful. We introduce a framework to support large-scale assessment of topical relevance. We measure the correspondence between a set of latent topics and a set of reference concepts to quantify four types of topical misalignment: junk, fused, missing, and repeated topics. Our analysis compares 10,000 topic model variants to 200 expert-provided domain concepts, and demonstrates how our framework can inform choices of model parameters, inference algorithms, and intrinsic measures of topical quality.
Robust Structural Metric Learning
Authors: Lim, Daryl and Lanckriet, Gert and McFee, Brian
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Metric learning algorithms produce a linear transformation of data which is optimized for a prediction task, such as nearest-neighbor classification or ranking.  However, when the input data contains a large portion of non-informative features, existing methods fail to identify the relevant features, and performance degrades accordingly. In this paper, we present an efficient and robust structural metric learning algorithm which enforces group sparsity on the learned transformation, while optimizing for structured ranking output prediction.  Experiments on synthetic and real datasets demonstrate that the proposed method outperforms previous methods in both high- and low-noise settings.
Online Kernel Learning with a Near Optimal Sparsity Bound
Authors: Zhang, Lijun and Yi, Jinfeng and Jin, Rong and Lin, Ming and He, Xiaofei
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this work, we focus on Online Sparse Kernel Learning that aims to online learn a kernel classifier with a bounded number of support vectors. Although many online learning algorithms have been proposed to learn a sparse kernel classifier, most of them fail to bound the number of support vectors used by the final solution which is the average of the intermediate kernel classifiers generated by online algorithms. The key idea of the proposed algorithm is to measure the difficulty in correctly classifying a training example by the derivative of a smooth loss function, and give a more chance to a difficult example to be a support vector than an easy one via a sampling scheme. Our analysis shows that when the loss function is smooth, the proposed algorithm yields similar performance guarantee as the standard online learning algorithm but with a near optimal number of support vectors (up to a poly(lnT) factor). Our empirical study shows promising performance of the proposed algorithm compared to the state-of-the-art algorithms for online sparse kernel learning.
Constrained fractional set programs and their  application in local clustering and community detection
Authors: Bühler, Thomas and Rangapuram, Shyam Sundar and Setzer, Simon and Hein, Matthias
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The (constrained) minimization of a ratio of set functions is a problem frequently occurring in clustering and community detection. As these optimization problems are typically NP-hard, one uses convex or spectral relaxations in practice. While these relaxations can be solved globally optimally, they are often too loose and thus lead to results far away from the optimum. In this paper we show that every constrained minimization problem of a ratio of non-negative set functions allows a tight relaxation into an unconstrained continuous optimization problem. This result leads to a flexible framework for solving constrained problems in network analysis. While a globally optimal solution for the resulting non-convex problem cannot be guaranteed, we outperform the loose convex or spectral relaxations by a large margin on constrained local clustering problems.
Spectral Learning of Hidden Markov Models from Dynamic and Static Data
Authors: Huang, Tzu-Kuo and Schneider, Jeff
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We develop spectral learning algorithms for Hidden Markov Models  that learn not only from time series, or dynamic data but also  static data drawn independently from the HMM’s stationary distribution.  This is motivated by the fact that static, orderless snapshots are usually easier to obtain than time series in quite a few dynamic modeling tasks. Building on existing spectral learning algorithms, our methods solve convex optimization problems minimizing squared loss on the dynamic data plus a regularization term on the static data. Experiments on synthetic and  real human activities data demonstrate better prediction by the proposed method than existing spectral algorithms.
Efficient Semi-supervised and Active Learning of Disjunctions
Authors: Balcan, Nina and Berlind, Christopher and Ehrlich, Steven and Liang, Yingyu
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We provide efficient algorithms for learning disjunctions in the semi-supervised setting under a natural regularity assumption introduced by (Balcan & Blum, 2005). We prove bounds on the sample complexity of our algorithms under a mild restriction on the data distribution. We also give an active learning algorithm with improved sample complexity and extend all our algorithms to the random classification noise setting.
Analogy-preserving Semantic Embedding for Visual Object Categorization
Authors: Ju Hwang, Sung and Grauman, Kristen and Sha, Fei
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In multi-class categorization tasks, knowledge about the classes’ semantic relationships can provide valuable information beyond the class labels themselves.  However, existing techniques focus on preserving the semantic distances between classes (e.g., according to a given object taxonomy for visual recognition), limiting the influence to pairwise structures.  We propose to model \emphanalogies that reflect the relationships between multiple pairs of classes simultaneously, in the form “p is to q, as r is to s"".  We translate semantic analogies into higher-order geometric constraints called \emphanalogical parallelograms, and use them in a novel convex regularizer for a discriminatively learned label embedding.   Furthermore, we show how to discover analogies from attribute-based class descriptions, and how to prioritize those likely to reduce inter-class confusion.  Evaluating our Analogy-preserving Semantic Embedding (ASE) on two visual recognition datasets, we demonstrate clear improvements over existing approaches, both in terms of recognition accuracy and analogy completion.
Convex Adversarial Collective Classification
Authors: Torkamani, MohamadAli and Lowd, Daniel
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper, we present a novel method for robustly  performing collective classification in the presence of a malicious  adversary that can modify up to a fixed number of binary-valued  attributes.  Our method is formulated as a convex quadratic program  that guarantees optimal weights against a worst-case adversary in  polynomial time.  In addition to increased robustness against active  adversaries, this kind of adversarial regularization can also lead to  improved generalization even when no adversary is present.  In  experiments on real and simulated data, our method consistently  outperforms both non-adversarial and non-relational baselines.
Algebraic classifiers: a generic approach to fast cross-validation, online training, and parallel training
Authors: Izbicki, Michael
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We use abstract algebra to derive new algorithms for fast cross-validation, online learning, and parallel learning.  To use these algorithms on a classification model, we must show that the model has appropriate algebraic structure.  It is easy to give algebraic structure to some models, and we do this explicitly for Bayesian classifiers and a novel variation of decision stumps called HomStumps.  But not all classifiers have an obvious structure, so we introduce the Free HomTrainer.  This can be used to give a “generic” algebraic structure to any classifier.  We use the Free HomTrainer to give algebraic structure to bagging and boosting.  In so doing, we derive novel online and parallel algorithms, and present the first fast cross-validation schemes for these classifiers.
Rounding Methods for Discrete Linear Classification
Authors: Chevaleyre, Yann and Koriche, Frédéerick and Zucker, Jean-daniel
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Learning discrete linear functions is a notoriously difficult challenge. In this paper, the learning task is cast as combinatorial optimization problem: given a set of positive and negative feature vectors in the Euclidean space, the goal is to find a discrete linear function that minimizes the cumulative hinge loss of this training set. Since this problem is NP-hard, we propose two simple rounding algorithms that discretize the fractional solution of the problem. Generalization bounds are derived for two important classes of binary-weighted linear functions, by establishing the Rademacher complexity of these classes and proving approximation bounds for rounding methods. These methods are compared on both synthetic and real-world data.
Factorial Multi-Task Learning : A Bayesian Nonparametric Approach
Authors: Gupta, Sunil and Phung, Dinh and Venkatesh, Svetha
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Multi-task learning is a paradigm shown to improve the performance of related tasks through their joint learning. However, for real-world data, it is usually difficult to assess the task relatedness and joint learning with unrelated tasks may lead to serious performance degradations. To this end, we propose a framework that groups the tasks based on their relatedness in a low dimensional subspace and allows a varying degree of relatedness among tasks by sharing the subspace bases across the groups. This provides the flexibility of no sharing when two sets of tasks are unrelated and partial/total sharing when the tasks are related. Importantly, the number of task-groups and the subspace dimensionality are automatically inferred from the data. This feature keeps the model beyond a specific set of parameters. To realize our framework, we present a novel Bayesian nonparametric prior that extends the traditional hierarchical beta process prior using a Dirichlet process to permit potentially infinite number of child beta processes. We apply our model for multi-task regression and classification applications. Experimental results using several synthetic and real-world datasets show the superiority of our model to other recent state-of-the-art multi-task learning methods.
Modeling Information Propagation with Survival Theory
Authors: Gomez-Rodriguez, Manuel and Leskovec, Jure and Schölkopf, Bernhard
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Networks provide a ‘skeleton’ for the spread of contagions, like, information, ideas, behaviors and diseases. Many times networks over which contagions diffuse are unobserved and need to be inferred. Here we apply survival theory to develop general additive and multiplicative risk models under which the network inference problems can be solved efficiently by exploiting their convexity. Our additive risk model generalizes several existing network inference models. We show all these models are particular cases of our more general model. Our multiplicative model allows for modeling scenarios in which a node can either increase or decrease the risk of activation of another node, in contrast with previous approaches, which consider only positive risk increments. We evaluate the performance of our network inference algorithms on large synthetic and real cascade datasets, and show that our models are able to predict the length and duration of cascades in real data.
Better Rates for Any Adversarial Deterministic MDP
Authors: Dekel, Ofer and Hazan, Elad
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider regret minimization in adversarial deterministic Markov  Decision Processes (ADMDPs) with bandit feedback. We devise a new  algorithm that pushes the state-of-the-art forward in two ways: First,  it attains a regret of O(T^2/3) with respect to the best fixed  policy in hindsight, whereas the previous best regret bound was  O(T^3/4). Second, the algorithm and its analysis are compatible  with any feasible ADMDP graph topology, while all previous approaches  required additional restrictions on the graph topology.
ABC Reinforcement Learning
Authors: Dimitrakakis, Christos and Tziortziotis, Nikolaos
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We introduce a simple, general framework for likelihood-free Bayesian reinforcement learning, through Approximate Bayesian Computation (ABC). The advantage is that we only require a prior distribution on a class of simulators. This is useful when a probabilistic model of the underlying process is too complex to formulate, but where detailed simulation models are available. ABC-RL allows  the use of any Bayesian reinforcement learning technique in this case. It can be seen as an extension of simulation methods to both planning and inference.  We experimentally demonstrate the potential of this approach in a comparison with LSPI. Finally, we introduce a theorem showing that ABC is sound.
Sharp Generalization Error Bounds for Randomly-projected Classifiers
Authors: Durrant, Robert and Kaban, Ata
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We derive sharp bounds on the generalization error of a generic linear classifier trained by   empirical risk minimization on randomly-projected data. We make no restrictive assumptions   (such as sparsity or separability) on the data: Instead we use the fact that, in a classification setting, the question of interest is really ‘what is the effect of random projection on the predicted class labels?’ and we therefore derive the exact probability of ‘label flipping’ under Gaussian random projection in order to quantify this effect precisely in our bounds.
On learning parametric-output HMMs
Authors: Kontorovich, Aryeh and Nadler, Boaz and Weiss, Roi
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We present a novel approach to learning an HMM whose outputs are distributed according to a parametric family. This is done by \em decoupling the learning task into two steps: first estimating the output parameters, and then estimating the hidden states transition probabilities. The first step is accomplished by fitting a mixture model to the output stationary distribution. Given the parameters of this mixture model, the second step is formulated as the solution of an easily solvable convex quadratic program. We provide an error analysis for the estimated transition probabilities and show they are robust to small perturbations in the estimates of the mixture parameters. Finally, we support our analysis with some encouraging empirical results.
LDA Topic Model with Soft Assignment of Descriptors to Words
Authors: Weinshall, Daphna and Levi, Gal and Hanukaev, Dmitri
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The LDA topic model is being used to model corpora of documents that can be represented by bags of words. Here we extend the LDA model to deal with documents that are represented more naturally by bags of continuous descriptors. Given a finite dictionary of words which are generative models of descriptors, our extended LDA model allows for the soft assignment of descriptors to (many) dictionary words. We derive variational inference and parameter estimation procedures for the extended model, which closely resemble those obtained for the original model, with two important differences: First, the histogram of word counts is replaced by a histogram of pseudo word counts, or sums of responsibilities over all descriptors. Second, parameter estimation now depends on the average covariance matrix between these pseudo-counts, reflecting the fact that with soft assignment words are not independent.    We use this approach to address novelty detection, where we seek to identify video events with low posterior probability. Video events are described by a generative dynamic texture model, from which we naturally derive a dictionary of generative words.  Using a benchmark dataset for novelty detection, we show a very significant improvement in the detection of novel events when using our extended LDA model with soft assignment to words as against hard assignment (the original model), achieving state of the art novelty detection results.
On autoencoder scoring
Authors: Kamyshanska, Hanna and Memisevic, Roland
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Autoencoders are popular feature learning models because they are conceptually simple, easy to train and allow for efficient inference and training. Recent work has shown how certain autoencoders can assign an unnormalized “score” to data which measures how well the autoencoder can represent the data. Scores are commonly computed by using training criteria that relate the autoencoder to a probabilistic model, such as the Restricted Boltzmann Machine. In this paper we show how an autoencoder can assign meaningful scores to data independently of training procedure and without reference to any probabilistic model, by interpreting it as a dynamical system. We discuss how, and under which conditions, running the dynamical system can be viewed as performing gradient descent in an energy function, which in turn allows us to derive a score via integration. We also show how one can combine multiple, unnormalized scores into a generative classifier.
Infinite Markov-Switching Maximum Entropy Discrimination Machines
Authors: Chatzis, Sotirios
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper, we present a method that combines the merits of Bayesian  nonparametrics, specifically stick-breaking priors, and large-margin  kernel machines in the context of sequential data classification.  The proposed model postulates a set of (theoretically) infinite interdependent  large-margin classifiers as model components, that robustly capture  local nonlinearity of complex data. The postulated large-margin classifiers  are connected in the context of a Markov-switching construction that  allows for capturing complex temporal dynamics in the modeled datasets.  Appropriate stick-breaking priors are imposed over the component switching  mechanism of our model to allow for data-driven determination of the  optimal number of component large-margin classifiers, under a standard  nonparametric Bayesian inference scheme. Efficient model training  is performed under the maximum entropy discrimination (MED) framework,  which integrates the large-margin principle with Bayesian posterior  inference. We evaluate our method using several real-world datasets,  and compare it to state-of-the-art alternatives.
A PAC-Bayesian Approach for Domain Adaptation with Specialization to Linear Classifiers
Authors: Germain, Pascal and Habrard, Amaury and Laviolette, François and Morvant, Emilie
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We provide a first PAC-Bayesian analysis for domain adaptation (DA) which arises when the learning and test distributions differ. It relies on a novel distribution pseudodistance based on a disagreement averaging. Using this measure, we derive a PAC-Bayesian DA bound for the stochastic Gibbs classifier. This bound has the advantage of being directly optimizable for any hypothesis space. We specialize it to linear classifiers, and design a learning algorithm which shows interesting results on a synthetic problem and on a popular sentiment annotation task. This opens the door to tackling DA tasks by making use of all the PAC-Bayesian tools.
Sparse PCA through Low-rank Approximations
Authors: Papailiopoulos, Dimitris and Dimakis, Alexandros and Korokythakis, Stavros
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We introduce a novel algorithm that computes the k-sparse principal component of a positive semidefinite matrix A.  Our algorithm is combinatorial and operates by examining a discrete set of special vectors lying in a low-dimensional eigen-subspace of A.  We obtain provable approximation guarantees that depend on the spectral profile of the matrix: the faster the eigenvalue decay, the better the quality of our approximation.  For example, if the eigenvalues of A follow a power-law decay, we obtain a polynomial-time approximation   algorithm for any desired accuracy.   We implement our algorithm and test it on multiple artificial and real data sets. Due to   a feature elimination step, it is possible to perform sparse PCA on data sets consisting of millions of entries in a few minutes.   Our experimental evaluation shows that our scheme is nearly optimal   while finding very sparse vectors.  We compare to the prior state of the art and show that our scheme matches or outperforms previous algorithms   in all tested data sets.
Computation-Risk Tradeoffs for Covariance-Thresholded Regression
Authors: Shender, Dinah and Lafferty, John
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We present a family of linear regression estimators that provides a fine-grained tradeoff between statistical accuracy and computational efficiency.  The estimators are based on hard thresholding of the sample covariance matrix entries together with l2-regularizion(ridge regression).  We analyze the predictive risk of this family of estimators as a function of the threshold and regularization parameter.  With appropriate parameter choices, the estimate is the solution to a sparse, diagonally dominant linear system, solvable in near-linear time.  Our analysis shows how the risk varies with the sparsity and regularization level, thus establishing a statistical estimation setting for which there is an explicit, smooth tradeoff between risk and computation.  Simulations are provided to support the theoretical analyses.
Exact Rule Learning via Boolean Compressed Sensing
Authors: Malioutov, Dmitry and Varshney, Kush
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We propose an interpretable rule-based classification system based on ideas from Boolean compressed sensing. We represent the problem of learning individual conjunctive clauses or individual disjunctive clauses as a Boolean group testing problem, and apply a novel linear programming relaxation to find solutions. We derive results for exact rule recovery which parallel the conditions for exact recovery of sparse signals in the compressed sensing literature: although the general rule recovery problem is NP-hard, under some conditions on the Boolean ‘sensing’ matrix, the rule can be recovered exactly. This is an exciting development in rule learning where most prior work focused on heuristic solutions. Furthermore we construct rule sets from these learned clauses using set covering and boosting.  We show competitive classification accuracy using the proposed approach.