mtybilly/Instruct2DS huggingface dataset:
Learning Multiple Behaviors from Unlabeled Demonstrations in a Latent Controller Space
Authors: Javier Almingol, Lui Montesano, Manuel Lopes
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper we introduce a method to learn multiple behaviors in the form of motor primitives from an unlabeled dataset. One of the difficulties of this problem is that in the measurement space, behaviors can be very mixed, despite existing a latent representation where they can be easily separated.  We propose a mixture model based on Dirichlet Process (DP) to simultaneously cluster the observed time-series and recover a sparse representation of the behaviors using a Laplacian prior as the base measure of the DP. We show that for linear models, e.g potential functions generated by linear combinations of a large number of features, it is possible to compute analytically the marginal of the observations and derive an efficient sampler. The method is evaluated using robot behaviors and real data from human motion and compared to other techniques.
Precision-recall space to correct external indices for biclustering
Authors: Blaise Hanczar, Mohamed Nadif
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Biclustering is a major tool of data mining in many domains and many algorithms have emerged in recent years. All these algorithms aim to obtain coherent biclusters and it is crucial to have a reliable procedure for their validation. We point out the problem of size bias in biclustering evaluation and show how it can lead to wrong conclusions in a comparative study. We present the theoretical corrections for all of the most popular measures in order to remove this bias. We introduce the corrected precision-recall space that combines the advantages of corrected measures, the ease of interpretation and visualization of uncorrected measures. Numerical experiments demonstrate the interest of our approach.
Learning Hash Functions Using Column Generation
Authors: Xi Li, Guosheng Lin, Chunhua Shen, Anton Hengel, Anthony Dick
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Fast nearest neighbor searching is becoming  an increasingly important tool in solving many  large-scale problems. Recently a number of approaches  to learning data-dependent hash functions  have been developed. In this work,  we propose a column generation based method  for learning data-dependent hash functions on  the basis of proximity comparison information.  Given a set of triplets that encode the pairwise  proximity comparison information, our method  learns hash functions that preserve the relative  comparison relationships in the data as well as  possible within the large-margin learning framework.  The learning procedure is implemented  using column generation and hence is named  CGHash. At each iteration of the column generation  procedure, the best hash function is selected.  Unlike most other hashing methods, our  method generalizes to new data points naturally;  and has a training objective which is convex, thus  ensuring that the global optimum can be identified.  Experiments demonstrate that the proposed  method learns compact binary codes and that its  retrieval performance compares favorably with  state-of-the-art methods when tested on a few  benchmark datasets.
Inference algorithms for pattern-based CRFs on sequence data
Authors: Rustem Takhanov, Vladimir Kolmogorov
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider \em Conditional Random Fields (CRFs) with pattern-based potentials  defined on a chain. In this model the energy of a string (labeling) x_1łdots x_n  is the sum of terms over intervals [i,j] where each term is non-zero only if the substring x_iłdots x_j  equals a prespecified pattern α. Such CRFs can be naturally applied to many sequence tagging problems. We present efficient algorithms for the three standard inference tasks in a CRF, namely  computing (i) the partition function, (ii) marginals, and (iii) computing the MAP.  Their complexities are respectively  O(n L), O(n L \ell_\max) and  O(n L \min|D|,łog (\ell_\max + 1))  where L is the combined length of input patterns, \ell_\max is the maximum length of a pattern,  and D is the input alphabet.  This improves on the previous algorithms of i̧teYe:NIPS09 whose complexities are respectively O(n L |D|),  Ołeft(n |Γ| L^2 \ell_\max^2i̊ght) and O(n L |D|),  where |Γ| is the number of input patterns. In addition, we give an efficient algorithm for sampling,  and revisit the case of MAP with non-positive weights. Finally, we apply pattern-based CRFs to the problem of the protein dihedral angles prediction.
Monochromatic Bi-Clustering
Authors: Sharon Wulff, Ruth Urner, Shai Ben-David
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We propose a natural cost function for the bi-clustering task, the monochromatic cost.  This cost function is suitable for detecting meaningful homogeneous bi-clusters based on categorical valued input matrices. Such tasks arise in many applications, such as the analysis of social networks and in systems-biology where researchers try to infer functional grouping of biological agents based on their pairwise interactions. We analyze the computational complexity of the resulting optimization problem. We present a polynomial time approximation algorithm for this bi-clustering task and complement this result by showing that finding (exact) optimal solutions is NP-hard. As far as we know, these are the first positive approximation guarantees  and formal NP-hardness results  for any bi-clustering optimization problem.  In addition, we show that our optimization problem can be efficiently  solved by deterministic annealing,  yielding a promising heuristic for large problem instances.
Combinatorial Multi-Armed Bandit: General Framework and Applications
Authors: Wei Chen, Yajun Wang, Yang Yuan
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We define a general framework for a large class of combinatorial multi-armed bandit (CMAB) problems, where simple arms with unknown istributions  form \em super arms. In each round, a super arm is played and the outcomes of its related simple arms are observed, which helps the selection of super arms in future rounds. The reward of the super arm depends on the outcomes of played arms, and it only needs to satisfy two mild assumptions, which allow a large class of nonlinear reward instances. We assume the availability of an (α,β)-approximation oracle that takes the  means of the distributions of arms and outputs a super arm that with probability βgenerates  an αfraction of the optimal expected reward. The objective of a CMAB algorithm is to minimize \em (α,β)-approximation regret, which is the difference in total expected reward between the αβfraction of expected reward when always playing the optimal super arm, and the expected reward of playing super arms according to the algorithm. We provide CUCB algorithm that achieves O(łog n) regret, where n is the number of rounds played, and we further provide distribution-independent bounds for a large class of reward functions. Our regret analysis is tight in that it matches the bound for classical MAB problem up to a constant factor, and it significantly improves the regret bound in a recent paper on combinatorial bandits with linear rewards. We apply our CMAB framework to two new applications, probabilistic maximum coverage (PMC) for online advertising and social influence maximization for viral marketing, both having nonlinear reward structures.
One-Bit Compressed Sensing: Provable Support and Vector Recovery
Authors: Sivakant Gopi, Praneeth Netrapalli, Prateek Jain, Aditya Nori
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper, we study the problem of one-bit compressed sensing (1-bit CS), where the goal is to design a measurement matrix A and a recovery algorithm s.t. a k-sparse vector \x^* can be efficiently recovered back from signed linear measurements, i.e., b=\sign(A\x^*). This is an important problem in the signal acquisition area and has several learning applications as well, e.g., multi-label classification i̧teHsuKLZ10. We study this problem in two settings: a) support recovery: recover \supp(\x^*), b) approximate vector recovery: recover a unit vector \hx s.t. || \hatx-\x^*/||\x^*|| ||_2≤ε. For support recovery, we propose two novel and efficient solutions based on two combinatorial structures: union free family of sets and expanders. In contrast to  existing methods for  support recovery, our methods are universal i.e. a single measurement matrix A can recover almost all the signals. For approximate recovery, we propose the first  method to recover sparse vector using a near optimal number of measurements.  We also empirically demonstrate  effectiveness of our algorithms; we show that our algorithms are able to recover signals with smaller number of measurements than several existing methods.
Gated Autoencoders with Tied Input Weights
Authors: Droniou Alain, Sigaud Olivier
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The semantic interpretation of images is one of the core applications of deep learning. Several techniques have been recently proposed to model the relation between two images, with application to pose estimation, action recognition or invariant object recognition. Among these techniques, higher-order Boltzmann machines or relational autoencoders consider projections of the images on different subspaces and intermediate layers act as transformation specific detectors. In this work, we extend the mathematical study of (Memisevic, 2012b) to show that it is possible to use a unique projection for both images in a way that turns intermediate layers as spectrum encoders of transformations. We show that this results in networks that are easier to tune and have greater generalization capabilities.
Near-optimal Batch Mode Active Learning and Adaptive Submodular Optimization
Authors: Yuxin Chen, Andreas Krause
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Active learning can lead to a dramatic reduction in labeling effort. However, in many practical implementations (such as crowdsourcing,  surveys, high-throughput experimental design), it is preferable to query labels for batches of examples to be labelled in parallel. While several heuristics have been proposed for batch-mode active learning, little is known about their theoretical performance.    We consider batch mode active learning and more general information-parallel stochastic optimization problems that exhibit adaptive submodularity, a natural diminishing returns condition. We prove that for such problems, a simple greedy strategy is competitive with the optimal batch-mode policy. In some cases, surprisingly, the use of batches incurs competitively low cost, even when compared to a fully sequential strategy. We demonstrate the effectiveness of our approach on batch-mode active learning tasks, where it outperforms the state of the art, as well as the novel problem of multi-stage influence maximization in social networks.
Tensor Analyzers
Authors: Yichuan Tang, Ruslan Salakhutdinov, Geoffrey Hinton
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Factor Analysis is a statistical method that seeks to explain linear variations in data by using unobserved latent variables. Due to its additive nature, it is not suitable for modeling data that is generated by multiple groups of latent factors which interact multiplicatively. In this paper, we introduce Tensor Analyzers which are a multilinear generalization of Factor Analyzers. We describe an efficient way of sampling from the posterior distribution over factor values and we demonstrate that these samples can be used in the EM algorithm for learning interesting mixture models of natural image patches. Tensor Analyzers can also accurately recognize a face under significant pose and illumination variations when given only one previous image of that face. We also show that Tensor Analyzers can be trained in an unsupervised, semi-supervised, or fully supervised settings.
Strict Monotonicity of Sum of Squares Error  and Normalized Cut in the Lattice of Clusterings
Authors: Nicola Rebagliati
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Sum of Squares Error and Normalized Cut are two widely used clustering functional. It is known their minimum values are monotone with respect to the input number of clusters and this monotonicity does not allow for a simple automatic selection of a correct number of clusters. Here we study monotonicity not just on the minimizers but on the entire clustering lattice. We show the value of Sum of Squares Error is strictly monotone under the strict refinement relation of clusterings and we obtain data-dependent bounds on the difference between the value of a clustering and one of its refinements. Using analogous techniques we show the value of Normalized Cut is strictly anti-monotone. These results imply that even if we restrict our solutions to form a chain of clustering, like the one we get from hierarchical algorithms, we cannot rely on the functional values in order to choose the number of clusters. By using these results we get some data-dependent bounds on the difference of the values of any two clusterings.
Convex formulations of radius-margin based Support Vector Machines
Authors: Huyen Do, Alexandros Kalousis
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider Support Vector Machines (SVMs) learned together with linear transformations of the feature spaces on which they are applied. Under this scenario the radius of the smallest data enclosing sphere is no longer fixed. Therefore optimizing the SVM error bound by considering both the radius and the margin has the potential to deliver a tighter error bound.  In this paper we present two novel algorithms: R-SVM_μ^+—a SVM radius-margin based feature selection algorithm, and R-SVM^+ —  a metric learning-based SVM. We derive our algorithms by exploiting a new tighter approximation of the radius and a metric learning interpretation of SVM. Both optimize directly the radius-margin error bound using linear transformations. Unlike almost all existing radius-margin based SVM algorithms which are either non-convex or combinatorial, our algorithms are standard quadratic convex optimization problems with linear or quadratic constraints. We perform a number of experiments on benchmark datasets.   R-SVM_μ^+ exhibits excellent feature selection performance compared to the state-of-the-art feature selection methods, such as L_1-norm and elastic-net based methods.  R-SVM^+ achieves a significantly better classification performance compared to SVM and its other state-of-the-art variants. From the results it is clear that the incorporation of the radius, as a means to control the data spread, in the cost function has strong beneficial effects.
Learning Sparse Penalties for Change-point Detection using Max Margin Interval Regression
Authors: Toby Hocking, Guillem Rigaill, Jean-Philippe Vert, Francis Bach
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In segmentation models, the number of change-points is typically    chosen using a penalized cost function.  In this work, we propose to    learn the penalty and its constants in databases of signals with    weak change-point annotations. We propose a convex relaxation for    the resulting interval regression problem, and solve it using    accelerated proximal gradient methods. We show that this method    achieves state-of-the-art change-point detection in a database of    annotated DNA copy number profiles from neuroblastoma tumors.
Transition Matrix Estimation in High Dimensional Time Series
Authors: Fang Han, Han Liu
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper, we propose a new method in estimating transition matrices of high dimensional vector autoregressive (VAR) models. Here the data are assumed to come from a stationary Gaussian VAR time series. By formulating the problem as a linear program, we provide a new approach to conduct inference on such models. In theory, under a doubly asymptotic framework in which both the sample size T and dimensionality d of the time series can increase, we provide explicit rates of convergence between the estimator and the population transition matrix under different matrix norms. Our results show that the spectral norm of the transition matrix plays a pivotal role in determining the final rates of convergence. This is the first work analyzing the estimation of transition matrices under a high dimensional doubly asymptotic framework. Experiments are conducted on both synthetic and real-world stock data to demonstrate the effectiveness of the proposed method compared with the existing methods. The results of this paper have broad impact on different applications, including finance, genomics, and brain imaging.
Modelling Sparse Dynamical Systems with Compressed Predictive State Representations
Authors: William L. Hamilton, Mahdi Milani Fard, Joelle Pineau
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Efficiently learning accurate models of dynamical systems is of central importance for developing rational agents that can succeed in a wide range of challenging domains. The difficulty of this learning problem is particularly acute in settings with large observation spaces and partial observability. We present a new algorithm, called Compressed Predictive State Representation (CPSR), for learning models of high-dimensional partially observable uncontrolled dynamical systems from small sample sets. The algorithm, which extends previous work on Predictive State Representations, exploits a particular sparse structure present in many domains. This sparse structure is used to compress information during learning, allowing for an increase in both the efficiency and predictive power. The compression technique also relieves the burden of domain specific feature selection and allows for domains with extremely large discrete observation spaces to be efficiently modelled. We present empirical results showing that the algorithm is able to build accurate models more efficiently than its uncompressed counterparts, and provide theoretical results on the accuracy of the learned compressed model.
Learning from Human-Generated Lists
Authors: Kwang-Sung Jun, Jerry Zhu, Burr Settles, Timothy Rogers
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Human-generated lists are a form of non-iid data with important applications in machine learning and cognitive psychology. We propose a generative model - sampling with reduced replacement (SWIRL) - for such lists. We discuss SWIRL’s relation to standard sampling paradigms, provide the maximum likelihood estimate for learning, and demonstrate its value with two real-world applications: (i) In a ""feature volunteering"" task where non-experts spontaneously generate feature=>label pairs for text classification, SWIRL improves the accuracy of state-of-the-art feature-learning frameworks. (ii) In a ""verbal fluency"" task where brain-damaged patients generate word lists when prompted with a category, SWIRL parameters align well with existing psychological theories, and our model can classify healthy people vs. patients from the lists they generate.
Label Partitioning For Sublinear Ranking
Authors: Jason Weston, Ameesh Makadia, Hector Yee
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: We consider the case of ranking a very large set of labels, items, or documents, which is common to information retrieval, recommendation, and large-scale annotation tasks. We present a general approach for converting an algorithm which has linear time in the size of the set to a sublinear one via label partitioning. Our method consists of learning an input partition and a label assignment  to each partition of the space such that precision at k is optimized, which is the loss function of interest in this setting. Experiments on large-scale ranking and recommendation tasks show that our method not only makes the original linear time algorithm computationally tractable, but can also improve its performance.
A Machine Learning Framework for Programming by Example
Authors: Aditya Menon, Omer Tamuz, Sumit Gulwani, Butler Lampson, Adam Kalai
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Learning programs is a timely and interesting challenge. In Programming by Example (PBE), a system attempts to infer a program from input and output examples alone, by searching for a composition of some set of base functions. We show how machine learning can be used to speed up this seemingly hopeless search problem, by learning weights that relate textual features describing the provided input-output examples to plausible sub-components of a program. This generic learning framework lets us address problems beyond the scope of earlier PBE systems. Experiments on a prototype implementation show that learning improves search and ranking on a variety of text processing tasks found on help forums.
A Fast and Exact Energy Minimization Algorithm for Cycle MRFs
Authors: Huayan Wang, Koller Daphne
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The presence of cycles gives rise to the difficulty in performing inference for MRFs. Handling cycles efficiently would greatly enhance our ability to tackle general MRFs. In particular, for dual decomposition of energy minimization (MAP inference), using cycle subproblems leads   to a much tighter relaxation than using trees, but solving the cycle subproblems turns out to be the bottleneck.  In this paper, we present a fast and exact algorithm for energy minimization in cycle MRFs, which can be used as a subroutine in tackling general MRFs. Our method builds on junction-tree message passing, with a large portion of the message entries pruned for efficiency. The pruning conditions fully exploit the structure of a cycle. Experimental results show that our algorithm is more than an order of magnitude faster than other state-of-the-art fast inference methods, and it performs consistently well in several different real problems.
Subproblem-Tree Calibration: A Unified Approach to Max-Product Message Passing
Authors: Huayan Wang, Koller Daphne
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Max-product (max-sum) message passing algorithms are widely used for MAP inference in MRFs. It has many variants sharing a common flavor of passing "messages" over some graph-object. Recent advances revealed that its convergent versions (such as MPLP, MSD, TRW-S) can be viewed as performing block coordinate descent (BCD) in a dual objective. That is, each BCD step achieves dual-optimal w.r.t. a block of dual variables (messages), thereby decreases the dual objective monotonically. However, most existing algorithms are limited to updating blocks selected in rather restricted ways. In this paper, we show a "unified" message passing algorithm that: (a) subsumes MPLP, MSD, and TRW-S as special cases when applied to their respective choices of dual objective and blocks, and (b) is able to perform BCD under much more flexible choices of blocks (including very large blocks) as well as the dual objective itself (that arise from an arbitrary dual decomposition).
Discriminatively Activated Sparselets
Authors: Ross Girshick, Hyun Oh Song, Trevor Darrell
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Shared representations are highly appealing due to their potential  for gains in computational and statistical efficiency.  Compressing  a shared representation leads to greater computational savings, but  at the same time can severely decrease performance on a target task.  Recently, sparselets (Song et al., 2012) were introduced as a new  shared intermediate representation for multiclass object detection  with deformable part models (Felzenszwalb et al., 2010a), showing  significant speedup factors, but with a large decrease in task  performance.  In this paper we describe a new training framework  that learns which sparselets to activate in order to optimize a  discriminative objective, leading to larger speedup factors with  no decrease in task performance.  We first reformulate sparselets  in a general structured output prediction framework, then analyze  when sparselets lead to computational efficiency gains, and lastly  show experimental results on object detection and image classification  tasks.  Our experimental results demonstrate that discriminative  activation substantially outperforms the previous reconstructive  approach which, together with our structured output prediction  formulation, make sparselets broadly applicable and significantly  more effective.
Stochastic k-Neighborhood Selection for Supervised and Unsupervised Learning
Authors: Daniel Tarlow, Kevin Swersky, Laurent Charlin, Ilya Sutskever, Rich Zemel
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Neighborhood Components Analysis (NCA) is a popular method for  learning a distance metric to be used within a k-nearest neighbors  (kNN) classifier.    A key assumption built into the model is that each point  stochastically selects a single neighbor, which  makes the model well-justified only for kNN with k=1.  However, kNN classifiers with k>1 are more robust and usually   preferred in practice.     Here we present kNCA, which generalizes NCA by  learning distance metrics that are appropriate for  kNN with arbitrary k.  The main technical contribution is showing  how to efficiently compute and optimize the expected  accuracy of a kNN classifier.  We apply similar ideas in an unsupervised  setting to yield kSNE and ktSNE, generalizations of  Stochastic Neighbor Embedding (SNE, tSNE) that operate on  neighborhoods of size k, which provide an axis of control over  embeddings that allow for more homogeneous and interpretable regions.  Empirically, we show that kNCA often improves classification accuracy over  state of the art methods, produces qualitative  differences in the embeddings as k is varied, and is more robust with  respect to label noise.
Collaborative hyperparameter tuning
Authors: Rémi Bardenet, Mátyás Brendel, Balázs Kégl, Michèle Sebag
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Hyperparameter learning has traditionally been a manual task because of the limited number of trials. Today’s computing infrastructures allow bigger evaluation budgets, thus opening the way for algorithmic approaches. Recently, surrogate-based optimization was successfully applied to hyperparameter learning for deep belief networks and to WEKA classifiers. The methods combined brute force computational power with model building about the behavior of the error function in the hyperparameter space, and they could significantly improve on manual hyperparameter tuning. What may make experienced practitioners even better at hyperparameter optimization is their ability to generalize across similar learning problems. In this paper, we propose a generic method to incorporate knowledge from previous experiments when simultaneously tuning a learning algorithm on new problems at hand. To this end, we combine surrogate-based ranking and optimization techniques for surrogate-based collaborative tuning (SCoT). We demonstrate SCoT in two experiments where it outperforms standard tuning techniques and single-problem surrogate-based optimization.
The Pairwise Piecewise-Linear Embedding for Efficient Non-Linear Classification
Authors: Ofir Pele, Ben Taskar, Amir Globerson, Michael Werman
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Linear classiffers are much faster to learn and test than non-linear ones. On the other hand, non-linear kernels offer improved performance, albeit at the increased cost of training kernel classiffers. To use non-linear mappings with efficient linear learning algorithms, explicit embeddings that approximate popular kernels have recently been proposed. However, the embedding process itself is often costly and the results are usually less accurate than kernel methods. In this work we propose a non-linear feature map that is both very efficient, but at the same time highly expressive. The method is based on discretization and interpolation of individual features values and feature pairs. The discretization allows us to model different regions of the feature space separately, while the interpolation preserves the original continuous values. Using this embedding is strictly more general than a linear model and as efficient as the second-order polynomial explicit feature map. An extensive empirical evaluation shows that our method consistently signiffcantly outperforms other methods, including a wide range of kernels. This is in contrast to other proposed embeddings that were faster than kernel methods, but with lower accuracy.
An Efficient Posterior Regularized Latent Variable Model for Interactive Sound Source Separation
Authors: Nicholas Bryan, Gautham Mysore
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In applications such as audio denoising, music transcription, music remixing, and audio-based forensics, it is desirable to decompose a single-channel recording into its respective sources.  One of the current most effective class of methods to do so is based on non-negative matrix factorization and related latent variable models.  Such techniques, however, typically perform poorly when no isolated training data is given and do not allow user feedback to correct for poor results. To overcome these issues, we allow a user to interactively constrain a latent variable model by painting on a time-frequency display of sound to guide the learning process.  The annotations are used within the framework of posterior regularization to impose linear grouping constraints that would otherwise be difficult to achieve via standard priors.  For the constraints considered, an efficient expectation-maximization algorithm is derived with closed-form multiplicative updates, drawing connections to non-negative matrix factorization methods, and allowing for high-quality interactive-rate separation without explicit training data.
SADA: A General Framework to Support Robust Causation Discovery
Authors: Ruichu Cai, Zhenjie Zhang, Zhifeng Hao
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Causality discovery without manipulation is considered a crucial problem to a variety of applications, such as genetic therapy. The state-of-the-art solutions, e.g. LiNGAM, return accurate results when the number of labeled samples is larger than the number of variables. These approaches are thus applicable only when large numbers of samples are available or the problem domain is sufficiently small. Motivated by the observations of the local sparsity properties on causal structures, we propose a general Split-and-Merge strategy, named SADA, to enhance the scalability of a wide class of causality discovery algorithms. SADA is able to accurately identify the causal variables, even when the sample size is significantly smaller than the number of variables. In SADA, the variables are partitioned into subsets, by finding cuts on the sparse probabilistic graphical model over the variables. By running mainstream causation discovery algorithms, e.g. LiNGAM, on the subproblems, complete causality can be reconstructed by combining all the partial results. SADA benefits from the recursive division technique, since each small subproblem generates more accurate result under the same number of samples. We theoretically prove that SADA always reduces the scale of problems without significant sacrifice on result accuracy, depending only on the local sparsity condition over the variables. Experiments on real-world datasets verify the improvements on scalability and accuracy by applying SADA on top of existing causation algorithms.
Fixed-Point Model For Structured Labeling
Authors: Quannan Li, Jingdong Wang, David Wipf, Zhuowen Tu
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper, we propose a simple but effective  solution to the structured labeling problem:  a fixed-point model. Recently, layered  models with sequential classifiers/regressors  have gained an increasing amount of interests  for structural prediction. Here, we design an  algorithm with a new perspective on layered  models; we aim to find a fixed-point function  with the structured labels being both the  output and the input. Our approach alleviates  the burden in learning multiple/different  classifiers in different layers. We devise a  training strategy for our method and provide  justifications for the fixed-point function  to be a contraction mapping. The learned  function captures rich contextual information  and is easy to train and test. On several  widely used benchmark datasets, the proposed  method observes significant improvement  in both performance and efficiency over  many state-of-the-art algorithms.
Estimating Unknown Sparsity in Compressed Sensing
Authors: Miles Lopes
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In the theory of compressed sensing (CS), the sparsity \|x\|_0 of the unknown signal x∈\R^p is commonly assumed to be a known parameter. However, it is typically unknown in practice. Due to the fact that many aspects of  CS depend on knowing \|x\|_0, it is important to estimate this parameter in a data-driven way. A second practical concern is that \|x\|_0 is a highly unstable function of x. In particular, for real signals with entries not exactly equal to 0, the value \|x\|_0=p is not a useful description of the effective number of coordinates. In this paper, we propose to estimate a stable measure of sparsity s(x)≔\|x\|_1^2/\|x\|_2^2, which is a sharp lower bound on \|x\|_0. Our estimation procedure uses only a small number of linear measurements, does not rely on any sparsity assumptions, and requires very little computation. A confidence interval for s(x) is  provided, and its width is shown to have no dependence on the signal dimension p. Moreover, this result extends naturally to the matrix recovery setting, where a soft version of matrix rank can be estimated with analogous guarantees. Finally, we show that the use of randomized measurements is essential to estimating s(x). This is accomplished by proving that the minimax risk for estimating s(x) with deterministic measurements is large when n≪p.
Learning and Selecting Features Jointly with Point-wise Gated Boltzmann Machines
Authors: Kihyuk Sohn, Guanyu Zhou, Chansoo Lee, Honglak Lee
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Unsupervised feature learning has emerged as a promising tool in learning representations from unlabeled data. However, it is still challenging to learn useful high-level features when the data contains a significant amount of irrelevant patterns. Although feature selection can be used for such complex data, it may fail when we have to build a learning system from scratch (i.e., starting from the lack of useful raw features). To address this problem, we propose a point-wise gated Boltzmann machine, a unified generative model that combines feature learning and feature selection. Our model performs not only feature selection on learned high-level features (i.e., hidden units), but also dynamic feature selection on raw features (i.e., visible units) through a gating mechanism. For each example, the model can adaptively focus on a variable subset of visible nodes corresponding to the task-relevant patterns, while ignoring the visible units corresponding to the task-irrelevant patterns. In experiments, our method achieves improved performance over state-of-the-art in several visual recognition benchmarks.
Connecting the Dots with Landmarks:  Discriminatively Learning Domain-Invariant Features for Unsupervised Domain Adaptation
Authors: Boqing Gong, Kristen Grauman, Fei Sha
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Learning domain-invariant features is of vital importance to unsupervised domain adaptation, where classifiers trained on the source domain need to be adapted to a different target domain for which no labeled examples are available. In this paper, we propose a novel approach for learning such features. The central idea is to exploit the existence of landmarks, which are a subset of labeled data instances in the source domain that are distributed most similarly to the target domain. Our approach automatically discovers the landmarks and use them to bridge the source to the target by constructing provably easier auxiliary domain adaptation tasks. The solutions of those auxiliary tasks form the basis to compose invariant features for the original task. We show how this composition can be optimized discriminatively without requiring labels from the target domain. We validate the method on standard benchmark datasets for visual object recognition and sentiment analysis of text. Empirical results show the proposed method outperforms the state-of-the-art significantly.
MAD-Bayes: MAP-based Asymptotic Derivations from Bayes
Authors: Tamara Broderick, Brian Kulis, Michael Jordan
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The classical mixture of Gaussians model is related to K-means via small-variance asymptotics: as the covariances of the Gaussians tend to zero, the negative log-likelihood of the mixture of Gaussians model approaches the K-means objective, and the EM algorithm approaches the K-means algorithm. Kulis & Jordan (2012) used this observation to obtain a novel K-means-like algorithm from a Gibbs sampler for the Dirichlet process (DP) mixture. We instead consider applying small-variance asymptotics directly to the posterior in Bayesian nonparametric models. This framework is independent of any specific Bayesian inference algorithm, and it has the major advantage that it generalizes immediately to a range of models beyond the DP mixture. To illustrate, we apply our framework to the feature learning setting, where the beta process and Indian buffet process provide an appropriate Bayesian nonparametric prior. We obtain a novel objective function that goes beyond clustering to learn (and penalize new) groupings for which we relax the mutual exclusivity and exhaustivity assumptions of clustering. We demonstrate several other algorithms, all of which are scalable and simple to implement. Empirical results demonstrate the benefits of the new framework.
Sequential Bayesian Search
Authors: Zheng Wen, Branislav Kveton, Brian Eriksson, Sandilya Bhamidipati
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Millions of people search daily for movies, music, and books on the Internet. Unfortunately, non-personalized exploration of items can result in an infeasible number of costly interaction steps. We study the problem of efficient, repeated interactive search. In this problem, the user is navigated to the items of interest through a series of options and our objective is to learn a better search policy from past interactions with the user. We propose an efficient learning algorithm for solving the problem, sequential Bayesian search (SBS), and prove that it is Bayesian optimal. We also analyze the algorithm from the frequentist point of view and show that its regret is sublinear in the number of searches. Finally, we evaluate our method on a real-world movie discovery problem and show that it performs nearly optimally as the number of searches increases.
Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization
Authors: Abhishek Kumar, Vikas Sindhwani, Prabhanjan Kambadur
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The separability assumption (Arora et al., 2012; Donoho & Stodden, 2003) turns non-negative matrix factorization (NMF) into a tractable problem. Recently, a new class of provably-correct NMF algorithms have emerged under this assumption. In this paper, we reformulate the separable NMF problem as that of finding the extreme rays of the conical hull of a finite set of vectors. From this geometric perspective, we derive new separable NMF algorithms that are highly scalable and empirically noise robust, and have several favorable properties in relation to existing methods. A parallel implementation of our algorithm scales excellently on shared and distributed-memory machines.
The Most Generative Maximum Margin Bayesian Networks
Authors: Robert Peharz, Sebastian Tschiatschek, Franz Pernkopf
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Although discriminative learning in graphical models generally improves classification results, the generative semantics of the model are compromised.  In this paper, we introduce a novel approach of hybrid generative-discriminative learning for Bayesian networks.  We use an SVM-type large margin formulation for discriminative training, introducing a likelihood-weighted \ell^1-norm for the SVM-norm-penalization.  This simultaneously optimizes the data likelihood and therefore partly maintains the generative character of the model.  For many network structures, our method can be formulated as a convex problem, guaranteeing a globally optimal solution.  In terms of classification, the resulting models outperform state-of-the art generative and discriminative learning methods for Bayesian networks, and are comparable with linear and kernelized SVMs.  Furthermore, the models achieve likelihoods close to the maximum likelihood solution and show robust behavior in classification experiments with missing features.
Sparse projections onto the simplex
Authors: Anastasios Kyrillidis, Stephen Becker, Volkan Cevher, Christoph Koch
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Most learning methods with rank or sparsity constraints use convex relaxations, which lead to optimization with the nuclear norm or the \ell_1-norm. However, several important learning applications cannot benefit from this approach as they feature these convex norms as constraints in addition to the non-convex rank and sparsity constraints. In this setting, we derive efficient sparse projections onto the simplex and its extension, and illustrate how to use them to solve high-dimensional learning problems in quantum tomography, sparse density estimation and portfolio selection with non-convex constraints.
Principal Component Analysis on non-Gaussian Dependent Data
Authors: Fang Han, Han Liu
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: In this paper, we analyze the performance of a semiparametric principal component analysis named Copula Component Analysis (COCA) (Han & Liu, 2012) when the data are dependent. The semiparametric model assumes that, after unspecified marginally monotone transformations, the distributions are multivariate Gaussian. We study the scenario where the observations are drawn from non-i.i.d. processes ($m$-dependency or a more general $ϕ$-mixing case). We show that COCA can allow weak dependence. In particular, we provide the generalization bounds of convergence for both support recovery and parameter estimation of COCA for the dependent data. We provide explicit sufficient conditions on the degree of dependence, under which the parametric rate can be maintained. To our knowledge, this is the first work analyzing the theoretical performance of PCA for the dependent data in high dimensional settings. Our results strictly generalize the analysis in Han & Liu (2012) and the techniques we used have the separate interest for analyzing a variety of other multivariate statistical methods.
Fastfood - Computing Hilbert Space Expansions in loglinear time
Authors: Quoc Le, Tamas Sarlos, Alexander Smola
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: Fast nonlinear function classes are crucial for nonparametric estimation, such as in kernel methods. This paper proposes an improvement to random kitchen sinks that offers significantly faster computation in log-linear time without sacrificing accuracy. Furthermore, we show how one may adjust the regularization properties of the kernel simply by changing the spectral distribution of the projection matrix. We provide experimental results which show that even for for moderately small problems we already achieve two orders of magnitude faster computation and three orders of magnitude lower memory footprint.
Modeling Musical Influence with Topic Models
Authors: Uri Shalit, Daphna Weinshall, Gal Chechik
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: The role of musical influence has long been debated by scholars  and critics in the humanities, but never in a data-driven way.  In this work we approach the question of influence by applying topic-modeling tools (Blei & Lafferty, 2006; Gerrish & Blei, 2010) to a dataset of 24941 songs by 9222 artists, from the years 1922 to 2010. We find the models to be significantly correlated with a human-curated influence measure, and to clearly outperform a baseline method. Further using the learned model to study properties of influence, we find that musical influence and musical innovation are not monotonically correlated. However, we do find that the most influential songs were more innovative during two time periods: the early 1970’s and the mid 1990’s.
Learning Linear Bayesian Networks with Latent Variables
Authors: Animashree Anandkumar, Daniel Hsu, Adel Javanmard, Sham Kakade
Published in: Proceedings of the 30th International Conference on Machine Learning (Main Conference Track), 2013

Abstract: This work considers the problem of learning linear Bayesian networks when  some of the variables are unobserved.  Identifiability and efficient recovery from low-order observable moments  are established under a novel graphical constraint.  The constraint concerns the expansion properties of the underlying directed  acyclic graph (DAG) between observed and unobserved variables in the  network, and it is satisfied by many natural families of DAGs that include  multi-level DAGs, DAGs with effective depth one, as well as certain  families of polytrees.