text:
@inproceedings{10.1145/1553374.1553375,
author = {Adams, Ryan Prescott and Ghahramani, Zoubin},
title = {Archipelago: Nonparametric Bayesian Semi-Supervised Learning},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553375},
doi = {10.1145/1553374.1553375},
abstract = {Semi-supervised learning (SSL), is classification where additional unlabeled data can be used to improve accuracy. Generative approaches are appealing in this situation, as a model of the data's probability density can assist in identifying clusters. Nonparametric Bayesian methods, while ideal in theory due to their principled motivations, have been difficult to apply to SSL in practice. We present a nonparametric Bayesian method that uses Gaussian processes for the generative model, avoiding many of the problems associated with Dirichlet process mixture models. Our model is fully generative and we take advantage of recent advances in Markov chain Monte Carlo algorithms to provide a practical inference method. Our method compares favorably to competing approaches on synthetic and real-world multi-class data.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {1–8},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553376,
author = {Adams, Ryan Prescott and Murray, Iain and MacKay, David J. C.},
title = {Tractable Nonparametric Bayesian Inference in Poisson Processes with Gaussian Process Intensities},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553376},
doi = {10.1145/1553374.1553376},
abstract = {The inhomogeneous Poisson process is a point process that has varying intensity across its domain (usually time or space). For nonparametric Bayesian modeling, the Gaussian process is a useful way to place a prior distribution on this intensity. The combination of a Poisson process and GP is known as a Gaussian Cox process, or doubly-stochastic Poisson process. Likelihood-based inference in these models requires an intractable integral over an infinite-dimensional random function. In this paper we present the first approach to Gaussian Cox processes in which it is possible to perform inference without introducing approximations or finitedimensional proxy distributions. We call our method the Sigmoidal Gaussian Cox Process, which uses a generative model for Poisson data to enable tractable inference via Markov chain Monte Carlo. We compare our methods to competing methods on synthetic data and apply it to several real-world data sets.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {9–16},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553377,
author = {Aiolli, Fabio and Da San Martino, Giovanni and Sperduti, Alessandro},
title = {Route Kernels for Trees},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553377},
doi = {10.1145/1553374.1553377},
abstract = {Almost all tree kernels proposed in the literature match substructures without taking into account their relative positioning with respect to one another. In this paper, we propose a novel family of kernels which explicitly focus on this type of information. Specifically, after defining a family of tree kernels based on routes between nodes, we present an efficient implementation for a member of this family. Experimental results on four different datasets show that our method is able to reach state of the art performances, obtaining in some cases performances better than computationally more demanding tree kernels.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {17–24},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553378,
author = {Andrzejewski, David and Zhu, Xiaojin and Craven, Mark},
title = {Incorporating Domain Knowledge into Topic Modeling via Dirichlet Forest Priors},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553378},
doi = {10.1145/1553374.1553378},
abstract = {Users of topic modeling methods often have knowledge about the composition of words that should have high or low probability in various topics. We incorporate such domain knowledge using a novel Dirichlet Forest prior in a Latent Dirichlet Allocation framework. The prior is a mixture of Dirichlet tree distributions with special structures. We present its construction, and inference via collapsed Gibbs sampling. Experiments on synthetic and real datasets demonstrate our model's ability to follow and generalize beyond user-specified domain knowledge.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {25–32},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553379,
author = {Bailly, Rapha\"{e}l and Denis, Fran\c{c}ois and Ralaivola, Liva},
title = {Grammatical Inference as a Principal Component Analysis Problem},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553379},
doi = {10.1145/1553374.1553379},
abstract = {One of the main problems in probabilistic grammatical inference consists in inferring a stochastic language, i.e. a probability distribution, in some class of probabilistic models, from a sample of strings independently drawn according to a fixed unknown target distribution p. Here, we consider the class of rational stochastic languages composed of stochastic languages that can be computed by multiplicity automata, which can be viewed as a generalization of probabilistic automata. Rational stochastic languages p have a useful algebraic characterization: all the mappings up: v → p(uv) lie in a finite dimensional vector subspace Vp* of the vector space ℝ 〈〈Σ〉〉 composed of all real-valued functions defined over Σ*. Hence, a first step in the grammatical inference process can consist in identifying the subspace Vp*. In this paper, we study the possibility of using Principal Component Analysis to achieve this task. We provide an inference algorithm which computes an estimate of this space and then build a multiplicity automaton which computes an estimate of the target distribution. We prove some theoretical properties of this algorithm and we provide results from numerical simulations that confirm the relevance of our approach.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {33–40},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553380,
author = {Bengio, Yoshua and Louradour, J\'{e}r\^{o}me and Collobert, Ronan and Weston, Jason},
title = {Curriculum Learning},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553380},
doi = {10.1145/1553374.1553380},
abstract = {Humans and animals learn much better when the examples are not randomly presented but organized in a meaningful order which illustrates gradually more concepts, and gradually more complex ones. Here, we formalize such training strategies in the context of machine learning, and call them "curriculum learning". In the context of recent research studying the difficulty of training in the presence of non-convex training criteria (for deep deterministic and stochastic neural networks), we explore curriculum learning in various set-ups. The experiments show that significant improvements in generalization can be achieved. We hypothesize that curriculum learning has both an effect on the speed of convergence of the training process to a minimum and, in the case of non-convex criteria, on the quality of the local minima obtained: curriculum learning can be seen as a particular form of continuation method (a general strategy for global optimization of non-convex functions).},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {41–48},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inbook{10.1145/1553374.1553381,
author = {Beygelzimer, Alina and Dasgupta, Sanjoy and Langford, John},
title = {Importance Weighted Active Learning},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553381},
abstract = {We present a practical and statistically consistent scheme for actively learning binary classifiers under general loss functions. Our algorithm uses importance weighting to correct sampling bias, and by controlling the variance, we are able to give rigorous label complexity bounds for the learning process.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {49–56},
numpages = {8}
}

@inproceedings{10.1145/1553374.1553382,
author = {Bouchard, Guillaume and Zoeter, Onno},
title = {Split Variational Inference},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553382},
doi = {10.1145/1553374.1553382},
abstract = {We propose a deterministic method to evaluate the integral of a positive function based on soft-binning functions that smoothly cut the integral into smaller integrals that are easier to approximate. In combination with mean-field approximations for each individual sub-part this leads to a tractable algorithm that alternates between the optimization of the bins and the approximation of the local integrals. We introduce suitable choices for the binning functions such that a standard mean field approximation can be extended to a split mean field approximation without the need for extra derivations. The method can be seen as a revival of the ideas underlying the mixture mean field approach. The latter can be obtained as a special case by taking soft-max functions for the binning.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {57–64},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553383,
author = {Boularias, Abdeslam and Chaib-draa, Brahim},
title = {Predictive Representations for Policy Gradient in POMDPs},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553383},
doi = {10.1145/1553374.1553383},
abstract = {We consider the problem of estimating the policy gradient in Partially Observable Markov Decision Processes (POMDPs) with a special class of policies that are based on Predictive State Representations (PSRs). We compare PSR policies to Finite-State Controllers (FSCs), which are considered as a standard model for policy gradient methods in POMDPs. We present a general Actor-Critic algorithm for learning both FSCs and PSR policies. The critic part computes a value function that has as variables the parameters of the policy. These latter parameters are gradually updated to maximize the value function. We show that the value function is polynomial for both FSCs and PSR policies, with a potentially smaller degree in the case of PSR policies. Therefore, the value function of a PSR policy can have less local optima than the equivalent FSC, and consequently, the gradient algorithm is more likely to converge to a global optimal solution.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {65–72},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553384,
author = {Boutilier, Craig and Regan, Kevin and Viappiani, Paolo},
title = {Online Feature Elicitation in Interactive Optimization},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553384},
doi = {10.1145/1553374.1553384},
abstract = {Most models of utility elicitation in decision support and interactive optimization assume a predefined set of "catalog" features over which user preferences are expressed. However, users may differ in the features over which they are most comfortable expressing their preferences. In this work we consider the problem of feature elicitation: a user's utility function is expressed using features whose definitions (in terms of "catalog" features) are unknown. We cast this as a problem of concept learning, but whose goal is to identify only enough about the concept to enable a good decision to be recommended. We describe computational procedures for identifying optimal alternatives w.r.t. minimax regret in the presence of concept uncertainty; and describe several heuristic query strategies that focus on reduction of relevant concept uncertainty.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {73–80},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inbook{10.1145/1553374.1553385,
author = {B\"{u}hler, Thomas and Hein, Matthias},
title = {Spectral Clustering Based on the Graph <i>p</i>-Laplacian},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553385},
abstract = {We present a generalized version of spectral clustering using the graph p-Laplacian, a nonlinear generalization of the standard graph Laplacian. We show that the second eigenvector of the graph p-Laplacian interpolates between a relaxation of the normalized and the Cheeger cut. Moreover, we prove that in the limit as p → 1 the cut found by thresholding the second eigenvector of the graph p-Laplacian converges to the optimal Cheeger cut. Furthermore, we provide an efficient numerical scheme to compute the second eigenvector of the graph p-Laplacian. The experiments show that the clustering found by p-spectral clustering is at least as good as normal spectral clustering, but often leads to significantly better results.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {81–88},
numpages = {8}
}

@inproceedings{10.1145/1553374.1553386,
author = {Burl, Michael C. and Wang, Esther},
title = {Active Learning for Directed Exploration of Complex Systems},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553386},
doi = {10.1145/1553374.1553386},
abstract = {Physics-based simulation codes are widely used in science and engineering to model complex systems that would be infeasible to study otherwise. Such codes provide the highest-fidelity representation of system behavior, but are often so slow to run that insight into the system is limited. For example, conducting an exhaustive sweep over a d-dimensional input parameter space with k-steps along each dimension requires kd simulation trials (translating into kd CPU-days for one of our current simulations). An alternative is directed exploration in which the next simulation trials are cleverly chosen at each step. Given the results of previous trials, supervised learning techniques (SVM, KDE, GP) are applied to build up simplified predictive models of system behavior. These models are then used within an active learning framework to identify the most valuable trials to run next. Several active learning strategies are examined including a recently-proposed information-theoretic approach. Performance is evaluated on a set of thirteen synthetic oracles, which serve as surrogates for the more expensive simulations and enable the experiments to be replicated by other researchers.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {89–96},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553387,
author = {Busetto, Alberto Giovanni and Ong, Cheng Soon and Buhmann, Joachim M.},
title = {Optimized Expected Information Gain for Nonlinear Dynamical Systems},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553387},
doi = {10.1145/1553374.1553387},
abstract = {This paper addresses the problem of active model selection for nonlinear dynamical systems. We propose a novel learning approach that selects the most informative subset of time-dependent variables for the purpose of Bayesian model inference. The model selection criterion maximizes the expected Kullback-Leibler divergence between the prior and the posterior probabilities over the models. The proposed strategy generalizes the standard D-optimal design, which is obtained from a uniform prior with Gaussian noise. In addition, our approach allows us to determine an information halting criterion for model identification. We illustrate the benefits of our approach by differentiating between 18 published biochemical models of the TOR signaling pathway, a model selection problem in systems biology. By generating pivotal selection experiments, our strategy outperforms the standard Aoptimal, D-optimal and E-optimal sequential design techniques.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {97–104},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553388,
author = {Cai, Deng and Wang, Xuanhui and He, Xiaofei},
title = {Probabilistic Dyadic Data Analysis with Local and Global Consistency},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553388},
doi = {10.1145/1553374.1553388},
abstract = {Dyadic data arises in many real world applications such as social network analysis and information retrieval. In order to discover the underlying or hidden structure in the dyadic data, many topic modeling techniques were proposed. The typical algorithms include Probabilistic Latent Semantic Analysis (PLSA) and Latent Dirichlet Allocation (LDA). The probability density functions obtained by both of these two algorithms are supported on the Euclidean space. However, many previous studies have shown naturally occurring data may reside on or close to an underlying submanifold. We introduce a probabilistic framework for modeling both the topical and geometrical structure of the dyadic data that explicitly takes into account the local manifold structure. Specifically, the local manifold structure is modeled by a graph. The graph Laplacian, analogous to the Laplace-Beltrami operator on manifolds, is applied to smooth the probability density functions. As a result, the obtained probabilistic distributions are concentrated around the data manifold. Experimental results on real data sets demonstrate the effectiveness of the proposed approach.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {105–112},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553389,
author = {de Campos, Cassio P. and Zeng, Zhi and Ji, Qiang},
title = {Structure Learning of Bayesian Networks Using Constraints},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553389},
doi = {10.1145/1553374.1553389},
abstract = {This paper addresses exact learning of Bayesian network structure from data and expert's knowledge based on score functions that are decomposable. First, it describes useful properties that strongly reduce the time and memory costs of many known methods such as hill-climbing, dynamic programming and sampling variable orderings. Secondly, a branch and bound algorithm is presented that integrates parameter and structural constraints with data in a way to guarantee global optimality with respect to the score function. It is an any-time procedure because, if stopped, it provides the best current solution and an estimation about how far it is from the global solution. We show empirically the advantages of the properties and the constraints, and the applicability of the algorithm to large data sets (up to one hundred variables) that cannot be handled by other current methods (limited to around 30 variables).},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {113–120},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553390,
author = {Cesa-Bianchi, Nicol\`{o} and Gentile, Claudio and Orabona, Francesco},
title = {Robust Bounds for Classification via Selective Sampling},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553390},
doi = {10.1145/1553374.1553390},
abstract = {We introduce a new algorithm for binary classification in the selective sampling protocol. Our algorithm uses Regularized Least Squares (RLS) as base classifier, and for this reason it can be efficiently run in any RKHS. Unlike previous margin-based semi-supervised algorithms, our sampling condition hinges on a simultaneous upper bound on bias and variance of the RLS estimate under a simple linear label noise model. This fact allows us to prove performance bounds that hold for an arbitrary sequence of instances. In particular, we show that our sampling strategy approximates the margin of the Bayes optimal classifier to any desired accuracy ε by asking \~{O} (d/ε2) queries (in the RKHS case d is replaced by a suitable spectral quantity). While these are the standard rates in the fully supervised i.i.d. case, the best previously known result in our harder setting was \~{O} (d3/ε4). Preliminary experiments show that some of our algorithms also exhibit a good practical performance.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {121–128},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553391,
author = {Chaudhuri, Kamalika and Kakade, Sham M. and Livescu, Karen and Sridharan, Karthik},
title = {Multi-View Clustering via Canonical Correlation Analysis},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553391},
doi = {10.1145/1553374.1553391},
abstract = {Clustering data in high dimensions is believed to be a hard problem in general. A number of efficient clustering algorithms developed in recent years address this problem by projecting the data into a lower-dimensional subspace, e.g. via Principal Components Analysis (PCA) or random projections, before clustering. Here, we consider constructing such projections using multiple views of the data, via Canonical Correlation Analysis (CCA).Under the assumption that the views are un-correlated given the cluster label, we show that the separation conditions required for the algorithm to be successful are significantly weaker than prior results in the literature. We provide results for mixtures of Gaussians and mixtures of log concave distributions. We also provide empirical support from audio-visual speaker clustering (where we desire the clusters to correspond to speaker ID) and from hierarchical Wikipedia document clustering (where one view is the words in the document and the other is the link structure).},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {129–136},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inbook{10.1145/1553374.1553392,
author = {Chen, Jianhui and Tang, Lei and Liu, Jun and Ye, Jieping},
title = {A Convex Formulation for Learning Shared Structures from Multiple Tasks},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553392},
abstract = {Multi-task learning (MTL) aims to improve generalization performance by learning multiple related tasks simultaneously. In this paper, we consider the problem of learning shared structures from multiple related tasks. We present an improved formulation (iASO) for multi-task learning based on the non-convex alternating structure optimization (ASO) algorithm, in which all tasks are related by a shared feature representation. We convert iASO, a non-convex formulation, into a relaxed convex one, which is, however, not scalable to large data sets due to its complex constraints. We propose an alternating optimization (cASO) algorithm which solves the convex relaxation efficiently, and further show that cASO converges to a global optimum. In addition, we present a theoretical condition, under which cASO can find a globally optimal solution to iASO. Experiments on several benchmark data sets confirm our theoretical analysis.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {137–144},
numpages = {8}
}

@inbook{10.1145/1553374.1553393,
author = {Chen, Yihua and Gupta, Maya R. and Recht, Benjamin},
title = {Learning Kernels from Indefinite Similarities},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553393},
abstract = {Similarity measures in many real applications generate indefinite similarity matrices. In this paper, we consider the problem of classification based on such indefinite similarities. These indefinite kernels can be problematic for standard kernel-based algorithms as the optimization problems become non-convex and the underlying theory is invalidated. In order to adapt kernel methods for similarity-based learning, we introduce a method that aims to simultaneously find a reproducing kernel Hilbert space based on the given similarities and train a classifier with good generalization in that space. The method is formulated as a convex optimization problem. We propose a simplified version that can reduce overfitting and whose associated convex conic program can be solved efficiently. We compare the proposed simplified version with six other methods on a collection of real data sets.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {145–152},
numpages = {8}
}

@inproceedings{10.1145/1553374.1553394,
author = {Cheng, Chih-Chieh and Sha, Fei and Saul, Lawrence K.},
title = {Matrix Updates for Perceptron Training of Continuous Density Hidden Markov Models},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553394},
doi = {10.1145/1553374.1553394},
abstract = {In this paper, we investigate a simple, mistake-driven learning algorithm for discriminative training of continuous density hidden Markov models (CD-HMMs). Most CD-HMMs for automatic speech recognition use multivariate Gaussian emission densities (or mixtures thereof) parameterized in terms of their means and covariance matrices. For discriminative training of CD-HMMs, we reparameterize these Gaussian distributions in terms of positive semidefinite matrices that jointly encode their mean and covariance statistics. We show how to explore the resulting parameter space in CDHMMs with perceptron-style updates that minimize the distance between Viterbi decodings and target transcriptions. We experiment with several forms of updates, systematically comparing the effects of different matrix factorizations, initializations, and averaging schemes on phone accuracies and convergence rates. We present experimental results for context-independent CD-HMMs trained in this way on the TIMIT speech corpus. Our results show that certain types of perceptron training yield consistently significant and rapid reductions in phone error rates.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {153–160},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inbook{10.1145/1553374.1553395,
author = {Cheng, Weiwei and H\"{u}hn, Jens and H\"{u}llermeier, Eyke},
title = {Decision Tree and Instance-Based Learning for Label Ranking},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553395},
abstract = {The label ranking problem consists of learning a model that maps instances to total orders over a finite set of predefined labels. This paper introduces new methods for label ranking that complement and improve upon existing approaches. More specifically, we propose extensions of two methods that have been used extensively for classification and regression so far, namely instance-based learning and decision tree induction. The unifying element of the two methods is a procedure for locally estimating predictive probability models for label rankings.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {161–168},
numpages = {8}
}

@inproceedings{10.1145/1553374.1553396,
author = {Cho, Youngmin and Saul, Lawrence K.},
title = {Learning Dictionaries of Stable Autoregressive Models for Audio Scene Analysis},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553396},
doi = {10.1145/1553374.1553396},
abstract = {In this paper, we explore an application of basis pursuit to audio scene analysis. The goal of our work is to detect when certain sounds are present in a mixed audio signal. We focus on the regime where out of a large number of possible sources, a small but unknown number combine and overlap to yield the observed signal. To infer which sounds are present, we decompose the observed signal as a linear combination of a small number of active sources. We cast the inference as a regularized form of linear regression whose sparse solutions yield decompositions with few active sources. We characterize the acoustic variability of individual sources by autoregressive models of their time domain waveforms. When we do not have prior knowledge of the individual sources, the coefficients of these autoregressive models must be learned from audio examples. We analyze the dynamical stability of these models and show how to estimate stable models by substituting a simple convex optimization for a difficult eigenvalue problem. We demonstrate our approach by learning dictionaries of musical notes and using these dictionaries to analyze polyphonic recordings of piano, cello, and violin.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {169–176},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553397,
author = {Choi, Myung Jin and Chandrasekaran, Venkat and Willsky, Alan S.},
title = {Exploiting Sparse Markov <i>and</i> Covariance Structure in Multiresolution Models},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553397},
doi = {10.1145/1553374.1553397},
abstract = {We consider Gaussian multiresolution (MR) models in which coarser, hidden variables serve to capture statistical dependencies among the finest scale variables. Tree-structured MR models have limited modeling capabilities, as variables at one scale are forced to be uncorrelated with each other conditioned on other scales. We propose a new class of Gaussian MR models that capture the residual correlations within each scale using sparse covariance structure. Our goal is to learn a tree-structured graphical model connecting variables across different scales, while at the same time learning sparse structure for the conditional covariance within each scale conditioned on other scales. This model leads to an efficient, new inference algorithm that is similar to multipole methods in computational physics.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {177–184},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553398,
author = {Cl\'{e}men\c{c}on, St\'{e}phan and Vayatis, Nicolas},
title = {Nonparametric Estimation of the Precision-Recall Curve},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553398},
doi = {10.1145/1553374.1553398},
abstract = {The Precision-Recall (PR) curve is a widely used visual tool to evaluate the performance of scoring functions in regards to their capacities to discriminate between two populations. The purpose of this paper is to examine both theoretical and practical issues related to the statistical estimation of PR curves based on classification data. Consistency and asymptotic normality of the empirical counterpart of the PR curve in sup norm are rigorously established. Eventually, the issue of building confidence bands in the PR space is considered and a specific resampling procedure based on a smoothed and truncated version of the empirical distribution of the data is promoted. Arguments of theoretical and computational nature are presented to explain why such a bootstrap is preferable to a "naive" bootstrap in this setup.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {185–192},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553399,
author = {Dai, Wenyuan and Jin, Ou and Xue, Gui-Rong and Yang, Qiang and Yu, Yong},
title = {EigenTransfer: A Unified Framework for Transfer Learning},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553399},
doi = {10.1145/1553374.1553399},
abstract = {This paper proposes a general framework, called EigenTransfer, to tackle a variety of transfer learning problems, e.g. cross-domain learning, self-taught learning, etc. Our basic idea is to construct a graph to represent the target transfer learning task. By learning the spectra of a graph which represents a learning task, we obtain a set of eigenvectors that reflect the intrinsic structure of the task graph. These eigenvectors can be used as the new features which transfer the knowledge from auxiliary data to help classify target data. Given an arbitrary non-transfer learner (e.g. SVM) and a particular transfer learning task, EigenTransfer can produce a transfer learner accordingly for the target transfer learning task. We apply EigenTransfer on three different transfer learning tasks, cross-domain learning, cross-category learning and self-taught learning, to demonstrate its unifying ability, and show through experiments that EigenTransfer can greatly outperform several representative non-transfer learners.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {193–200},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inbook{10.1145/1553374.1553400,
author = {Daitch, Samuel I. and Kelner, Jonathan A. and Spielman, Daniel A.},
title = {Fitting a Graph to Vector Data},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553400},
abstract = {We introduce a measure of how well a combinatorial graph fits a collection of vectors. The optimal graphs under this measure may be computed by solving convex quadratic programs and have many interesting properties. For vectors in d dimensional space, the graphs always have average degree at most 2(d + 1), and for vectors in 2 dimensions they are always planar. We compute these graphs for many standard data sets and show that they can be used to obtain good solutions to classification, regression and clustering problems.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {201–208},
numpages = {8}
}

@inbook{10.1145/1553374.1553401,
author = {Daum\'{e}, Hal},
title = {Unsupervised Search-Based Structured Prediction},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553401},
abstract = {We describe an adaptation and application of a search-based structured prediction algorithm "Searn" to unsupervised learning problems. We show that it is possible to reduce unsupervised learning to supervised learning and demonstrate a high-quality un-supervised shift-reduce parsing model. We additionally show a close connection between unsupervised Searn and expectation maximization. Finally, we demonstrate the efficacy of a semi-supervised extension. The key idea that enables this is an application of the predict-self idea for unsupervised learning.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {209–216},
numpages = {8}
}

@inproceedings{10.1145/1553374.1553402,
author = {Davis, Jesse and Domingos, Pedro},
title = {Deep Transfer via Second-Order Markov Logic},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553402},
doi = {10.1145/1553374.1553402},
abstract = {Standard inductive learning requires that training and test instances come from the same distribution. Transfer learning seeks to remove this restriction. In shallow transfer, test instances are from the same domain, but have a different distribution. In deep transfer, test instances are from a different domain entirely (i.e., described by different predicates). Humans routinely perform deep transfer, but few learning systems, if any, are capable of it. In this paper we propose an approach based on a form of second-order Markov logic. Our algorithm discovers structural regularities in the source domain in the form of Markov logic formulas with predicate variables, and instantiates these formulas with predicates from the target domain. Using this approach, we have successfully transferred learned knowledge among molecular biology, social network and Web domains. The discovered patterns include broadly useful properties of predicates, like symmetry and transitivity, and relations among predicates, such as various forms of homophily.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {217–224},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553403,
author = {Deisenroth, Marc Peter and Huber, Marco F. and Hanebeck, Uwe D.},
title = {Analytic Moment-Based Gaussian Process Filtering},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553403},
doi = {10.1145/1553374.1553403},
abstract = {We propose an analytic moment-based filter for nonlinear stochastic dynamic systems modeled by Gaussian processes. Exact expressions for the expected value and the covariance matrix are provided for both the prediction step and the filter step, where an additional Gaussian assumption is exploited in the latter case. Our filter does not require further approximations. In particular, it avoids finite-sample approximations. We compare the filter to a variety of Gaussian filters, that is, the EKF, the UKF, and the recent GP-UKF proposed by Ko et al. (2007).},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {225–232},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553404,
author = {Dekel, Ofer and Shamir, Ohad},
title = {Good Learners for Evil Teachers},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553404},
doi = {10.1145/1553374.1553404},
abstract = {We consider a supervised machine learning scenario where labels are provided by a heterogeneous set of teachers, some of which are mediocre, incompetent, or perhaps even malicious. We present an algorithm, built on the SVM framework, that explicitly attempts to cope with low-quality and malicious teachers by decreasing their influence on the learning process. Our algorithm does not receive any prior information on the teachers, nor does it resort to repeated labeling (where each example is labeled by multiple teachers). We provide a theoretical analysis of our algorithm and demonstrate its merits empirically. Finally, we present a second algorithm with promising empirical results but without a formal analysis.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {233–240},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553405,
author = {Deodhar, Meghana and Gupta, Gunjan and Ghosh, Joydeep and Cho, Hyuk and Dhillon, Inderjit},
title = {A Scalable Framework for Discovering Coherent Co-Clusters in Noisy Data},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553405},
doi = {10.1145/1553374.1553405},
abstract = {Clustering problems often involve datasets where only a part of the data is relevant to the problem, e.g., in microarray data analysis only a subset of the genes show cohesive expressions within a subset of the conditions/features. The existence of a large number of non-informative data points and features makes it challenging to hunt for coherent and meaningful clusters from such datasets. Additionally, since clusters could exist in different subspaces of the feature space, a co-clustering algorithm that simultaneously clusters objects and features is often more suitable as compared to one that is restricted to traditional "one-sided" clustering. We propose Robust Overlapping Co-Clustering (ROCC), a scalable and very versatile framework that addresses the problem of efficiently mining dense, arbitrarily positioned, possibly overlapping co-clusters from large, noisy datasets. ROCC has several desirable properties that make it extremely well suited to a number of real life applications.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {241–248},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553406,
author = {Diuk, Carlos and Li, Lihong and Leffler, Bethany R.},
title = {The Adaptive <i>k</i>-Meteorologists Problem and Its Application to Structure Learning and Feature Selection in Reinforcement Learning},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553406},
doi = {10.1145/1553374.1553406},
abstract = {The purpose of this paper is three-fold. First, we formalize and study a problem of learning probabilistic concepts in the recently proposed KWIK framework. We give details of an algorithm, known as the Adaptive k-Meteorologists Algorithm, analyze its sample-complexity upper bound, and give a matching lower bound. Second, this algorithm is used to create a new reinforcement-learning algorithm for factored-state problems that enjoys significant improvement over the previous state-of-the-art algorithm. Finally, we apply the Adaptive k-Meteorologists Algorithm to remove a limiting assumption in an existing reinforcement-learning algorithm. The effectiveness of our approaches is demonstrated empirically in a couple benchmark domains as well as a robotics navigation problem.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {249–256},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553407,
author = {Do, Chuong B. and Le, Quoc V. and Foo, Chuan-Sheng},
title = {Proximal Regularization for Online and Batch Learning},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553407},
doi = {10.1145/1553374.1553407},
abstract = {Many learning algorithms rely on the curvature (in particular, strong convexity) of regularized objective functions to provide good theoretical performance guarantees. In practice, the choice of regularization penalty that gives the best testing set performance may result in objective functions with little or even no curvature. In these cases, algorithms designed specifically for regularized objectives often either fail completely or require some modification that involves a substantial compromise in performance.We present new online and batch algorithms for training a variety of supervised learning models (such as SVMs, logistic regression, structured prediction models, and CRFs) under conditions where the optimal choice of regularization parameter results in functions with low curvature. We employ a technique called proximal regularization, in which we solve the original learning problem via a sequence of modified optimization tasks whose objectives are chosen to have greater curvature than the original problem. Theoretically, our algorithms achieve low regret bounds in the online setting and fast convergence in the batch setting. Experimentally, our algorithms improve upon state-of-the-art techniques, including Pegasos and bundle methods, on medium and large-scale SVM and structured learning tasks.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {257–264},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553408,
author = {Do, Trinh-Minh-Tri and Arti\`{e}res, Thierry},
title = {Large Margin Training for Hidden Markov Models with Partially Observed States},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553408},
doi = {10.1145/1553374.1553408},
abstract = {Large margin learning of Continuous Density HMMs with a partially labeled dataset has been extensively studied in the speech and handwriting recognition fields. Yet due to the non-convexity of the optimization problem, previous works usually rely on severe approximations so that it is still an open problem. We propose a new learning algorithm that relies on non-convex optimization and bundle methods and allows tackling the original optimization problem as is. It is proved to converge to a solution with accuracy ε with a rate O (1/ε). We provide experimental results gained on speech and handwriting recognition that demonstrate the potential of the method.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {265–272},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553409,
author = {Doshi-Velez, Finale and Ghahramani, Zoubin},
title = {Accelerated Sampling for the Indian Buffet Process},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553409},
doi = {10.1145/1553374.1553409},
abstract = {We often seek to identify co-occurring hidden features in a set of observations. The Indian Buffet Process (IBP) provides a non-parametric prior on the features present in each observation, but current inference techniques for the IBP often scale poorly. The collapsed Gibbs sampler for the IBP has a running time cubic in the number of observations, and the uncollapsed Gibbs sampler, while linear, is often slow to mix. We present a new linear-time collapsed Gibbs sampler for conjugate likelihood models and demonstrate its efficacy on large real-world datasets.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {273–280},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553410,
author = {Doyle, Gabriel and Elkan, Charles},
title = {Accounting for Burstiness in Topic Models},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553410},
doi = {10.1145/1553374.1553410},
abstract = {Many different topic models have been used successfully for a variety of applications. However, even state-of-the-art topic models suffer from the important flaw that they do not capture the tendency of words to appear in bursts; it is a fundamental property of language that if a word is used once in a document, it is more likely to be used again. We introduce a topic model that uses Dirichlet compound multinomial (DCM) distributions to model this burstiness phenomenon. On both text and non-text datasets, the new model achieves better held-out likelihood than standard latent Dirichlet allocation (LDA). It is straightforward to incorporate the DCM extension into topic models that are more complex than LDA.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {281–288},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553411,
author = {Duan, Lixin and Tsang, Ivor W. and Xu, Dong and Chua, Tat-Seng},
title = {Domain Adaptation from Multiple Sources via Auxiliary Classifiers},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553411},
doi = {10.1145/1553374.1553411},
abstract = {We propose a multiple source domain adaptation method, referred to as Domain Adaptation Machine (DAM), to learn a robust decision function (referred to as target classifier) for label prediction of patterns from the target domain by leveraging a set of pre-computed classifiers (referred to as auxiliary/source classifiers) independently learned with the labeled patterns from multiple source domains. We introduce a new data-dependent regularizer based on smoothness assumption into Least-Squares SVM (LS-SVM), which enforces that the target classifier shares similar decision values with the auxiliary classifiers from relevant source domains on the unlabeled patterns of the target domain. In addition, we employ a sparsity regularizer to learn a sparse target classifier. Comprehensive experiments on the challenging TRECVID 2005 corpus demonstrate that DAM outperforms the existing multiple source domain adaptation methods for video concept detection in terms of effectiveness and efficiency.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {289–296},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553412,
author = {Duchi, John and Singer, Yoram},
title = {Boosting with Structural Sparsity},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553412},
doi = {10.1145/1553374.1553412},
abstract = {We derive generalizations of AdaBoost and related gradient-based coordinate descent methods that incorporate sparsity-promoting penalties for the norm of the predictor that is being learned. The end result is a family of coordinate descent algorithms that integrate forward feature induction and back-pruning through regularization and give an automatic stopping criterion for feature induction. We study penalties based on the l1, l2, and l∞ norms of the predictor and introduce mixed-norm penalties that build upon the initial penalties. The mixed-norm regularizers facilitate structural sparsity in parameter space, which is a useful property in multiclass prediction and other related tasks. We report empirical results that demonstrate the power of our approach in building accurate and structurally sparse models.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {297–304},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553413,
author = {Farhangfar, Alireza and Greiner, Russell and Szepesv\'{a}ri, Csaba},
title = {Learning to Segment from a Few Well-Selected Training Images},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553413},
doi = {10.1145/1553374.1553413},
abstract = {We address the task of actively learning a segmentation system: given a large number of unsegmented images, and access to an oracle that can segment a given image, decide which images to provide, to quickly produce a segmenter (here, a discriminative random field) that is accurate over this distribution of images. We extend the standard models for active learner to define a system for this task that first selects the image whose expected label will reduce the uncertainty of the other unlabeled images the most, and then after greedily selects, from the pool of unsegmented images, the most informative image. The results of our experiments, over two real-world datasets (segmenting brain tumors within magnetic resonance images; and segmenting the sky in real images) show that training on very few informative images (here, as few as 2) can produce a segmenter that is as good as training on the entire dataset.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {305–312},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553414,
author = {Flores, M. Julia and G\'{a}mez, Jos\'{e} A. and Mart\'{\i}nez, Ana M. and Puerta, Jos\'{e} M.},
title = {GAODE and HAODE: Two Proposals Based on AODE to Deal with Continuous Variables},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553414},
doi = {10.1145/1553374.1553414},
abstract = {AODE (Aggregating One-Dependence Estimators) is considered one of the most interesting representatives of the Bayesian classifiers, taking into account not only the low error rate it provides but also its efficiency. Until now, all the attributes in a dataset have had to be nominal to build an AODE classifier or they have had to be previously discretized. In this paper, we propose two different approaches in order to deal directly with numeric attributes. One of them uses conditional Gaussian networks to model a dataset exclusively with numeric attributes; and the other one keeps the superparent on each model discrete and uses univariate Gaussians to estimate the probabilities for the numeric attributes and multinomial distributions for the categorical ones, it also being able to model hybrid datasets. Both of them obtain competitive results compared to AODE, the latter in particular being a very attractive alternative to AODE in numeric datasets.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {313–320},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553415,
author = {Foo, Chuan-Sheng and Do, Chuong B. and Ng, Andrew Y.},
title = {A Majorization-Minimization Algorithm for (Multiple) Hyperparameter Learning},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553415},
doi = {10.1145/1553374.1553415},
abstract = {We present a general Bayesian framework for hyperparameter tuning in L2-regularized supervised learning models. Paradoxically, our algorithm works by first analytically integrating out the hyperparameters from the model. We find a local optimum of the resulting non-convex optimization problem efficiently using a majorization-minimization (MM) algorithm, in which the non-convex problem is reduced to a series of convex L2-regularized parameter estimation tasks. The principal appeal of our method is its simplicity: the updates for choosing the L2-regularized subproblems in each step are trivial to implement (or even perform by hand), and each subproblem can be efficiently solved by adapting existing solvers. Empirical results on a variety of supervised learning models show that our algorithm is competitive with both grid-search and gradient-based algorithms, but is more efficient and far easier to implement.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {321–328},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553416,
author = {Fu, Wenjie and Song, Le and Xing, Eric P.},
title = {Dynamic Mixed Membership Blockmodel for Evolving Networks},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553416},
doi = {10.1145/1553374.1553416},
abstract = {In a dynamic social or biological environment, interactions between the underlying actors can undergo large and systematic changes. Each actor can assume multiple roles and their degrees of affiliation to these roles can also exhibit rich temporal phenomena. We propose a state space mixed membership stochastic blockmodel which can track across time the evolving roles of the actors. We also derive an efficient variational inference procedure for our model, and apply it to the Enron email networks, and rewiring gene regulatory networks of yeast. In both cases, our model reveals interesting dynamical roles of the actors.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {329–336},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553417,
author = {Garg, Rahul and Khandekar, Rohit},
title = {Gradient Descent with Sparsification: An Iterative Algorithm for Sparse Recovery with Restricted Isometry Property},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553417},
doi = {10.1145/1553374.1553417},
abstract = {We present an algorithm for finding an s-sparse vector x that minimizes the square-error ∥y -- Φx∥2 where Φ satisfies the restricted isometry property (RIP), with isometric constant δ2s < 1/3. Our algorithm, called GraDeS (Gradient Descent with Sparsification) iteratively updates x as: [EQUATION]where γ > 1 and Hs sets all but s largest magnitude coordinates to zero. GraDeS converges to the correct solution in constant number of iterations. The condition δ2s < 1/3 is most general for which a near-linear time algorithm is known. In comparison, the best condition under which a polynomial-time algorithm is known, is δ2s < √2 -- 1.Our Matlab implementation of GraDeS outperforms previously proposed algorithms like Subspace Pursuit, StOMP, OMP, and Lasso by an order of magnitude. Curiously, our experiments also uncovered cases where L1-regularized regression (Lasso) fails but GraDeS finds the correct solution.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {337–344},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553418,
author = {Garnett, Roman and Osborne, Michael A. and Roberts, Stephen J.},
title = {Sequential Bayesian Prediction in the Presence of Changepoints},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553418},
doi = {10.1145/1553374.1553418},
abstract = {We introduce a new sequential algorithm for making robust predictions in the presence of changepoints. Unlike previous approaches, which focus on the problem of detecting and locating changepoints, our algorithm focuses on the problem of making predictions even when such changes might be present. We introduce nonstationary covariance functions to be used in Gaussian process prediction that model such changes, then proceed to demonstrate how to effectively manage the hyperparameters associated with those covariance functions. By using Bayesian quadrature, we can integrate out the hyperparameters, allowing us to calculate the marginal predictive distribution. Furthermore, if desired, the posterior distribution over putative changepoint locations can be calculated as a natural byproduct of our prediction algorithm.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {345–352},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553419,
author = {Germain, Pascal and Lacasse, Alexandre and Laviolette, Fran\c{c}ois and Marchand, Mario},
title = {PAC-Bayesian Learning of Linear Classifiers},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553419},
doi = {10.1145/1553374.1553419},
abstract = {We present a general PAC-Bayes theorem from which all known PAC-Bayes risk bounds are obtained as particular cases. We also propose different learning algorithms for finding linear classifiers that minimize these bounds. These learning algorithms are generally competitive with both AdaBoost and the SVM.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {353–360},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553421,
author = {Gieseke, Fabian and Pahikkala, Tapio and Kramer, Oliver},
title = {Fast Evolutionary Maximum Margin Clustering},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553421},
doi = {10.1145/1553374.1553421},
abstract = {The maximum margin clustering approach is a recently proposed extension of the concept of support vector machines to the clustering problem. Briefly stated, it aims at finding an optimal partition of the data into two classes such that the margin induced by a subsequent application of a support vector machine is maximal. We propose a method based on stochastic search to address this hard optimization problem. While a direct implementation would be infeasible for large data sets, we present an efficient computational shortcut for assessing the "quality" of intermediate solutions. Experimental results show that our approach outperforms existing methods in terms of clustering accuracy.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {361–368},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inbook{10.1145/1553374.1553422,
author = {Rodrigues Gomes, Eduardo and Kowalczyk, Ryszard},
title = {Dynamic Analysis of Multiagent <i>Q</i>-Learning with ε-Greedy Exploration},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553422},
abstract = {The development of mechanisms to understand and model the expected behaviour of multiagent learners is becoming increasingly important as the area rapidly find application in a variety of domains. In this paper we present a framework to model the behaviour of Q-learning agents using the ε-greedy exploration mechanism. For this, we analyse a continuous-time version of the Q-learning update rule and study how the presence of other agents and the ε-greedy mechanism affect it. We then model the problem as a system of difference equations which is used to theoretically analyse the expected behaviour of the agents. The applicability of the framework is tested through experiments in typical games selected from the literature.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {369–376},
numpages = {8}
}

@inproceedings{10.1145/1553374.1553423,
author = {Guiver, John and Snelson, Edward},
title = {Bayesian Inference for Plackett-Luce Ranking Models},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553423},
doi = {10.1145/1553374.1553423},
abstract = {This paper gives an efficient Bayesian method for inferring the parameters of a Plackett-Luce ranking model. Such models are parameterised distributions over rankings of a finite set of objects, and have typically been studied and applied within the psychometric, sociometric and econometric literature. The inference scheme is an application of Power EP (expectation propagation). The scheme is robust and can be readily applied to large scale data sets. The inference algorithm extends to variations of the basic Plackett-Luce model, including partial rankings. We show a number of advantages of the EP approach over the traditional maximum likelihood method. We apply the method to aggregate rankings of NASCAR racing drivers over the 2002 season, and also to rankings of movie genres.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {377–384},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553424,
author = {Haider, Peter and Scheffer, Tobias},
title = {Bayesian Clustering for Email Campaign Detection},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553424},
doi = {10.1145/1553374.1553424},
abstract = {We discuss the problem of clustering elements according to the sources that have generated them. For elements that are characterized by independent binary attributes, a closed-form Bayesian solution exists. We derive a solution for the case of dependent attributes that is based on a transformation of the instances into a space of independent feature functions. We derive an optimization problem that produces a mapping into a space of independent binary feature vectors; the features can reflect arbitrary dependencies in the input space. This problem setting is motivated by the application of spam filtering for email service providers. Spam traps deliver a real-time stream of messages known to be spam. If elements of the same campaign can be recognized reliably, entire spam and phishing campaigns can be contained. We present a case study that evaluates Bayesian clustering for this application.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {385–392},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inbook{10.1145/1553374.1553425,
author = {Hazan, Elad and Seshadhri, C.},
title = {Efficient Learning Algorithms for Changing Environments},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553425},
abstract = {We study online learning in an oblivious changing environment. The standard measure of regret bounds the difference between the cost of the online learner and the best decision in hindsight. Hence, regret minimizing algorithms tend to converge to the static best optimum, clearly a suboptimal behavior in changing environments. On the other hand, various metrics proposed to strengthen regret and allow for more dynamic algorithms produce inefficient algorithms.We propose a different performance metric which strengthens the standard metric of regret and measures performance with respect to a changing comparator. We then describe a series of data-streaming-based reductions which transform algorithms for minimizing (standard) regret into adaptive algorithms albeit incurring only poly-logarithmic computational overhead.Using this reduction, we obtain efficient low adaptive-regret algorithms for the problem of online convex optimization. This can be applied to various learning scenarios, i.e. online portfolio selection, for which we describe experimental results showing the advantage of adaptivity.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {393–400},
numpages = {8}
}

@inproceedings{10.1145/1553374.1553426,
author = {Heidrich-Meisner, Verena and Igel, Christian},
title = {Hoeffding and Bernstein Races for Selecting Policies in Evolutionary Direct Policy Search},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553426},
doi = {10.1145/1553374.1553426},
abstract = {Uncertainty arises in reinforcement learning from various sources, and therefore it is necessary to consider statistics based on several roll-outs for evaluating behavioral policies. We add an adaptive uncertainty handling based on Hoeffding and empirical Bernstein races to the CMA-ES, a variable metric evolution strategy proposed for direct policy search. The uncertainty handling adjusts individually the number of episodes considered for the evaluation of a policy. The performance estimation is kept just accurate enough for a sufficiently good ranking of candidate policies, which is in turn sufficient for the CMA-ES to find better solutions. This increases the learning speed as well as the robustness of the algorithm.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {401–408},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inbook{10.1145/1553374.1553427,
author = {Helleputte, Thibault and Dupont, Pierre},
title = {Partially Supervised Feature Selection with Regularized Linear Models},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553427},
abstract = {This paper addresses feature selection techniques for classification of high dimensional data, such as those produced by microarray experiments. Some prior knowledge may be available in this context to bias the selection towards some dimensions (genes) a priori assumed to be more relevant. We propose a feature selection method making use of this partial supervision. It extends previous works on embedded feature selection with linear models including regularization to enforce sparsity. A practical approximation of this technique reduces to standard SVM learning with iterative rescaling of the inputs. The scaling factors depend here on the prior knowledge but the final selection may depart from it. Practical results on several microarray data sets show the benefits of the proposed approach in terms of the stability of the selected gene lists with improved classification performances.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {409–416},
numpages = {8}
}

@inproceedings{10.1145/1553374.1553429,
author = {Huang, Junzhou and Zhang, Tong and Metaxas, Dimitris},
title = {Learning with Structured Sparsity},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553429},
doi = {10.1145/1553374.1553429},
abstract = {This paper investigates a new learning formulation called structured sparsity, which is a natural extension of the standard sparsity concept in statistical learning and compressive sensing. By allowing arbitrary structures on the feature set, this concept generalizes the group sparsity idea. A general theory is developed for learning with structured sparsity, based on the notion of coding complexity associated with the structure. Moreover, a structured greedy algorithm is proposed to efficiently solve the structured sparsity problem. Experiments demonstrate the advantage of structured sparsity over standard sparsity.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {417–424},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553430,
author = {Huang, Tzu-Kuo and Schneider, Jeff},
title = {Learning Linear Dynamical Systems without Sequence Information},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553430},
doi = {10.1145/1553374.1553430},
abstract = {Virtually all methods of learning dynamic systems from data start from the same basic assumption: that the learning algorithm will be provided with a sequence, or trajectory, of data generated from the dynamic system. In this paper we consider the case where the data is not sequenced. The learning algorithm is presented a set of data points from the system's operation but with no temporal ordering. The data are simply drawn as individual disconnected points.While making this assumption may seem absurd at first glance, we observe that many scientific modeling tasks have exactly this property. In this paper we restrict our attention to learning linear, discrete time models. We propose several algorithms for learning these models based on optimizing approximate likelihood functions and test the methods on several synthetic data sets.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {425–432},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553431,
author = {Jacob, Laurent and Obozinski, Guillaume and Vert, Jean-Philippe},
title = {Group Lasso with Overlap and Graph Lasso},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553431},
doi = {10.1145/1553374.1553431},
abstract = {We propose a new penalty function which, when used as regularization for empirical risk minimization procedures, leads to sparse estimators. The support of the sparse vector is typically a union of potentially overlapping groups of co-variates defined a priori, or a set of covariates which tend to be connected to each other when a graph of covariates is given. We study theoretical properties of the estimator, and illustrate its behavior on simulated and breast cancer gene expression data.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {433–440},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553432,
author = {Jebara, Tony and Wang, Jun and Chang, Shih-Fu},
title = {Graph Construction and <i>b</i>-Matching for Semi-Supervised Learning},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553432},
doi = {10.1145/1553374.1553432},
abstract = {Graph based semi-supervised learning (SSL) methods play an increasingly important role in practical machine learning systems. A crucial step in graph based SSL methods is the conversion of data into a weighted graph. However, most of the SSL literature focuses on developing label inference algorithms without extensively studying the graph building method and its effect on performance. This article provides an empirical study of leading semi-supervised methods under a wide range of graph construction algorithms. These SSL inference algorithms include the Local and Global Consistency (LGC) method, the Gaussian Random Field (GRF) method, the Graph Transduction via Alternating Minimization (GTAM) method as well as other techniques. Several approaches for graph construction, sparsification and weighting are explored including the popular k-nearest neighbors method (kNN) and the b-matching method. As opposed to the greedily constructed kNN graph, the b-matched graph ensures each node in the graph has the same number of edges and produces a balanced or regular graph. Experimental results on both artificial data and real benchmark datasets indicate that b-matching produces more robust graphs and therefore provides significantly better prediction accuracy without any significant change in computation time.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {441–448},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inbook{10.1145/1553374.1553433,
author = {Jetchev, Nikolay and Toussaint, Marc},
title = {Trajectory Prediction: Learning to Map Situations to Robot Trajectories},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553433},
abstract = {Trajectory planning and optimization is a fundamental problem in articulated robotics. Algorithms used typically for this problem compute optimal trajectories from scratch in a new situation. In effect, extensive data is accumulated containing situations together with the respective optimized trajectories - but this data is in practice hardly exploited. The aim of this paper is to learn from this data. Given a new situation we want to predict a suitable trajectory which only needs minor refinement by a conventional optimizer. Our approach has two essential ingredients. First, to generalize from previous situations to new ones we need an appropriate situation descriptor - we propose a sparse feature selection approach to find such well-generalizing features of situations. Second, the transfer of previously optimized trajectories to a new situation should not be made in joint angle space - we propose a more efficient task space transfer of old trajectories to new situations. Experiments on a simulated humanoid reaching problem show that we can predict reasonable motion prototypes in new situations for which the refinement is much faster than an optimization from scratch.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {449–456},
numpages = {8}
}

@inproceedings{10.1145/1553374.1553434,
author = {Ji, Shuiwang and Ye, Jieping},
title = {An Accelerated Gradient Method for Trace Norm Minimization},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553434},
doi = {10.1145/1553374.1553434},
abstract = {We consider the minimization of a smooth loss function regularized by the trace norm of the matrix variable. Such formulation finds applications in many machine learning tasks including multi-task learning, matrix classification, and matrix completion. The standard semidefinite programming formulation for this problem is computationally expensive. In addition, due to the non-smooth nature of the trace norm, the optimal first-order black-box method for solving such class of problems converges as O(1/√k), where k is the iteration counter. In this paper, we exploit the special structure of the trace norm, based on which we propose an extended gradient algorithm that converges as O(1/k). We further propose an accelerated gradient algorithm, which achieves the optimal convergence rate of O(1/k2) for smooth problems. Experiments on multi-task learning problems demonstrate the efficiency of the proposed algorithms.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {457–464},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553435,
author = {Jin, Wei and Ho, Hung Hay},
title = {A Novel Lexicalized HMM-Based Learning Framework for Web Opinion Mining},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553435},
doi = {10.1145/1553374.1553435},
abstract = {NOTE FROM ACM: A Joint ACM Conference Committee has determined that the authors of this article violated ACM's publication policy on simultaneous submissions. Therefore ACM has shut off access to this paper.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {465–472},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553436,
author = {Johnson, Jason K. and Chernyak, Vladimir Y. and Chertkov, Michael},
title = {Orbit-Product Representation and Correction of Gaussian Belief Propagation},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553436},
doi = {10.1145/1553374.1553436},
abstract = {We present a new view of Gaussian belief propagation (GaBP) based on a representation of the determinant as a product over orbits of a graph. We show that the GaBP determinant estimate captures totally backtracking orbits of the graph and consider how to correct this estimate. We show that the missing orbits may be grouped into equivalence classes corresponding to backtrackless orbits and the contribution of each equivalence class is easily determined from the GaBP solution. Furthermore, we demonstrate that this multiplicative correction factor can be interpreted as the determinant of a backtrackless adjacency matrix of the graph with edge weights based on GaBP. Finally, an efficient method is proposed to compute a truncated correction factor including all backtrackless orbits up to a specified length.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {473–480},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553437,
author = {Kamisetty, Hetunandan and Langmead, Christopher J.},
title = {A Bayesian Approach to Protein Model Quality Assessment},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553437},
doi = {10.1145/1553374.1553437},
abstract = {Given multiple possible models b1, b2, ... bn for a protein structure, a common sub-task in in-silico Protein Structure Prediction is ranking these models according to their quality. Extant approaches use MLE estimates of parameters ri to obtain point estimates of the Model Quality. We describe a Bayesian alternative to assessing the quality of these models that builds an MRF over the parameters of each model and performs approximate inference to integrate over them. Hyperparameters w are learnt by optimizing a list-wise loss function over training data. Our results indicate that our Bayesian approach can significantly outperform MLE estimates and that optimizing the hyper-parameters can further improve results.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {481–488},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553438,
author = {Karampatziakis, Nikos and Kozen, Dexter},
title = {Learning Prediction Suffix Trees with Winnow},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553438},
doi = {10.1145/1553374.1553438},
abstract = {Prediction suffix trees (PSTs) are a popular tool for modeling sequences and have been successfully applied in many domains such as compression and language modeling. In this work we adapt the well studied Winnow algorithm to the task of learning PSTs. The proposed algorithm automatically grows the tree, so that it provably remains competitive with any fixed PST determined in hindsight. At the same time we prove that the depth of the tree grows only logarithmically with the number of mistakes made by the algorithm. Finally, we empirically demonstrate its effectiveness in two different tasks.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {489–496},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553439,
author = {K\'{e}gl, Bal\'{a}zs and Busa-Fekete, R\'{o}bert},
title = {Boosting Products of Base Classifiers},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553439},
doi = {10.1145/1553374.1553439},
abstract = {In this paper we show how to boost products of simple base learners. Similarly to trees, we call the base learner as a subroutine but in an iterative rather than recursive fashion. The main advantage of the proposed method is its simplicity and computational efficiency. On benchmark datasets, our boosted products of decision stumps clearly outperform boosted trees, and on the MNIST dataset the algorithm achieves the second best result among no-domain-knowledge algorithms after deep belief nets. As a second contribution, we present an improved base learner for nominal features and show that boosting the product of two of these new subset indicator base learners solves the maximum margin matrix factorization problem used to formalize the collaborative filtering task. On a small benchmark dataset, we get experimental results comparable to the semi-definite-programming-based solution but at a much lower computational cost.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {497–504},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553440,
author = {Kok, Stanley and Domingos, Pedro},
title = {Learning Markov Logic Network Structure via Hypergraph Lifting},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553440},
doi = {10.1145/1553374.1553440},
abstract = {Markov logic networks (MLNs) combine logic and probability by attaching weights to first-order clauses, and viewing these as templates for features of Markov networks. Learning MLN structure from a relational database involves learning the clauses and weights. The state-of-the-art MLN structure learners all involve some element of greedily generating candidate clauses, and are susceptible to local optima. To address this problem, we present an approach that directly utilizes the data in constructing candidates. A relational database can be viewed as a hypergraph with constants as nodes and relations as hyperedges. We find paths of true ground atoms in the hypergraph that are connected via their arguments. To make this tractable (there are exponentially many paths in the hypergraph), we lift the hypergraph by jointly clustering the constants to form higherlevel concepts, and find paths in it. We variabilize the ground atoms in each path, and use them to form clauses, which are evaluated using a pseudo-likelihood measure. In our experiments on three real-world datasets, we find that our algorithm outperforms the state-of-the-art approaches.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {505–512},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553441,
author = {Kolter, J. Zico and Ng, Andrew Y.},
title = {Near-Bayesian Exploration in Polynomial Time},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553441},
doi = {10.1145/1553374.1553441},
abstract = {We consider the exploration/exploitation problem in reinforcement learning (RL). The Bayesian approach to model-based RL offers an elegant solution to this problem, by considering a distribution over possible models and acting to maximize expected reward; unfortunately, the Bayesian solution is intractable for all but very restricted cases. In this paper we present a simple algorithm, and prove that with high probability it is able to perform ε-close to the true (intractable) optimal Bayesian policy after some small (polynomial in quantities describing the system) number of time steps. The algorithm and analysis are motivated by the so-called PAC-MDP approach, and extend such results into the setting of Bayesian RL. In this setting, we show that we can achieve lower sample complexity bounds than existing algorithms, while using an exploration strategy that is much greedier than the (extremely cautious) exploration of PAC-MDP algorithms.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {513–520},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inbook{10.1145/1553374.1553442,
author = {Kolter, J. Zico and Ng, Andrew Y.},
title = {Regularization and Feature Selection in Least-Squares Temporal Difference Learning},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553442},
abstract = {We consider the task of reinforcement learning with linear value function approximation. Temporal difference algorithms, and in particular the Least-Squares Temporal Difference (LSTD) algorithm, provide a method for learning the parameters of the value function, but when the number of features is large this algorithm can over-fit to the data and is computationally expensive. In this paper, we propose a regularization framework for the LSTD algorithm that overcomes these difficulties. In particular, we focus on the case of l1 regularization, which is robust to irrelevant features and also serves as a method for feature selection. Although the l1 regularized LSTD solution cannot be expressed as a convex optimization problem, we present an algorithm similar to the Least Angle Regression (LARS) algorithm that can efficiently compute the optimal solution. Finally, we demonstrate the performance of the algorithm experimentally.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {521–528},
numpages = {8}
}

@inbook{10.1145/1553374.1553443,
author = {Kondor, Risi and Shervashidze, Nino and Borgwardt, Karsten M.},
title = {The Graphlet Spectrum},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553443},
abstract = {Current graph kernels suffer from two limitations: graph kernels based on counting particular types of subgraphs ignore the relative position of these subgraphs to each other, while graph kernels based on algebraic methods are limited to graphs without node labels. In this paper we present the graphlet spectrum, a system of graph invariants derived by means of group representation theory that capture information about the number as well as the position of labeled subgraphs in a given graph. In our experimental evaluation the graphlet spectrum outperforms state-of-the-art graph kernels.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {529–536},
numpages = {8}
}

@inbook{10.1145/1553374.1553444,
author = {Kot\l{}owski, Wojciech and S\l{}owi\'{n}ski, Roman},
title = {Rule Learning with Monotonicity Constraints},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553444},
abstract = {In classification with monotonicity constraints, it is assumed that the class label should increase with increasing values on the attributes. In this paper we aim at formalizing the approach to learning with monotonicity constraints from statistical point of view. Motivated by the statistical analysis, we present an algorithm for learning rule ensembles. The algorithm first "monotonizes" the data using a nonparametric classification procedure and then generates a rule ensemble consistent with the training set. The procedure is justified by a theoretical analysis and verified in a computational experiment.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {537–544},
numpages = {8}
}

@inproceedings{10.1145/1553374.1553445,
author = {Kowalski, Matthieu and Szafranski, Marie and Ralaivola, Liva},
title = {Multiple Indefinite Kernel Learning with Mixed Norm Regularization},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553445},
doi = {10.1145/1553374.1553445},
abstract = {We address the problem of learning classifiers using several kernel functions. On the contrary to many contributions in the field of learning from different sources of information using kernels, we here do not assume that the kernels used are positive definite. The learning problem that we are interested in involves a misclassification loss term and a regularization term that is expressed by means of a mixed norm. The use of a mixed norm allows us to enforce some sparsity structure, a particular case of which is, for instance, the Group Lasso. We solve the convex problem by employing proximal minimization algorithms, which can be viewed as refined versions of gradient descent procedures capable of naturally dealing with nondifferentiability. A numerical simulation on a Uci dataset shows the modularity of our approach.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {545–552},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553446,
author = {Kumar, Sanjiv and Mohri, Mehryar and Talwalkar, Ameet},
title = {On Sampling-Based Approximate Spectral Decomposition},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553446},
doi = {10.1145/1553374.1553446},
abstract = {This paper addresses the problem of approximate singular value decomposition of large dense matrices that arises naturally in many machine learning applications. We discuss two recently introduced sampling-based spectral decomposition techniques: the Nystr\"{o}m and the Column-sampling methods. We present a theoretical comparison between the two methods and provide novel insights regarding their suitability for various applications. We then provide experimental results motivated by this theory. Finally, we propose an efficient adaptive sampling technique to select informative columns from the original matrix. This novel technique outperforms standard sampling methods on a variety of datasets.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {553–560},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inbook{10.1145/1553374.1553447,
author = {Kunegis, J\'{e}r\^{o}me and Lommatzsch, Andreas},
title = {Learning Spectral Graph Transformations for Link Prediction},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553447},
abstract = {We present a unified framework for learning link prediction and edge weight prediction functions in large networks, based on the transformation of a graph's algebraic spectrum. Our approach generalizes several graph kernels and dimensionality reduction methods and provides a method to estimate their parameters efficiently. We show how the parameters of these prediction functions can be learned by reducing the problem to a one-dimensional regression problem whose runtime only depends on the method's reduced rank and that can be inspected visually. We derive variants that apply to undirected, weighted, unweighted, unipartite and bipartite graphs. We evaluate our method experimentally using examples from social networks, collaborative filtering, trust networks, citation networks, authorship graphs and hyperlink networks.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {561–568},
numpages = {8}
}

@inproceedings{10.1145/1553374.1553448,
author = {Ku\v{z}elka, Ond\v{r}ej and \v{z}elezn\'{y}, Filip},
title = {Block-Wise Construction of Acyclic Relational Features with Monotone Irreducibility and Relevancy Properties},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553448},
doi = {10.1145/1553374.1553448},
abstract = {We describe an algorithm for constructing a set of acyclic conjunctive relational features by combining smaller conjunctive blocks. Unlike traditional level-wise approaches which preserve the monotonicity of frequency, our block-wise approach preserves a form of monotonicity of the irreducibility and relevancy feature properties, which are important in propositionalization employed in the context of classification learning. With pruning based on these properties, our block-wise approach efficiently scales to features including tens of first-order literals, far beyond the reach of state-of-the art propositionalization or inductive logic programming systems.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {569–576},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inbook{10.1145/1553374.1553449,
author = {Lan, Yanyan and Liu, Tie-Yan and Ma, Zhiming and Li, Hang},
title = {Generalization Analysis of Listwise Learning-to-Rank Algorithms},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553449},
abstract = {This paper presents a theoretical framework for ranking, and demonstrates how to perform generalization analysis of listwise ranking algorithms using the framework. Many learning-to-rank algorithms have been proposed in recent years. Among them, the listwise approach has shown higher empirical ranking performance when compared to the other approaches. However, there is no theoretical study on the listwise approach as far as we know. In this paper, we propose a theoretical framework for ranking, which can naturally describe various listwise learning-to-rank algorithms. With this framework, we prove a theorem which gives a generalization bound of a listwise ranking algorithm, on the basis of Rademacher Average of the class of compound functions. The compound functions take listwise loss functions as outer functions and ranking models as inner functions. We then compute the Rademacher Averages for existing listwise algorithms of ListMLE, ListNet, and RankCosine. We also discuss the tightness of the bounds in different situations with regard to the list length and transformation function.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {577–584},
numpages = {8}
}

@inproceedings{10.1145/1553374.1553450,
author = {Lang, Tobias and Toussaint, Marc},
title = {Approximate Inference for Planning in Stochastic Relational Worlds},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553450},
doi = {10.1145/1553374.1553450},
abstract = {Relational world models that can be learned from experience in stochastic domains have received significant attention recently. However, efficient planning using these models remains a major issue. We propose to convert learned noisy probabilistic relational rules into a structured dynamic Bayesian network representation. Predicting the effects of action sequences using approximate inference allows for planning in complex worlds. We evaluate the effectiveness of our approach for online planning in a 3D simulated blocksworld with an articulated manipulator and realistic physics. Empirical results show that our method can solve problems where existing methods fail.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {585–592},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553451,
author = {Langford, John and Salakhutdinov, Ruslan and Zhang, Tong},
title = {Learning Nonlinear Dynamic Models},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553451},
doi = {10.1145/1553374.1553451},
abstract = {We present a novel approach for learning nonlinear dynamic models, which leads to a new set of tools capable of solving problems that are otherwise difficult. We provide theory showing this new approach is consistent for models with long range structure, and apply the approach to motion capture and high-dimensional video data, yielding results superior to standard alternatives.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {593–600},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553452,
author = {Lawrence, Neil D. and Urtasun, Raquel},
title = {Non-Linear Matrix Factorization with Gaussian Processes},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553452},
doi = {10.1145/1553374.1553452},
abstract = {A popular approach to collaborative filtering is matrix factorization. In this paper we develop a non-linear probabilistic matrix factorization using Gaussian process latent variable models. We use stochastic gradient descent (SGD) to optimize the model. SGD allows us to apply Gaussian processes to data sets with millions of observations without approximate methods. We apply our approach to benchmark movie recommender data sets. The results show better than previous state-of-the-art performance.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {601–608},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inbook{10.1145/1553374.1553453,
author = {Lee, Honglak and Grosse, Roger and Ranganath, Rajesh and Ng, Andrew Y.},
title = {Convolutional Deep Belief Networks for Scalable Unsupervised Learning of Hierarchical Representations},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553453},
abstract = {There has been much interest in unsupervised learning of hierarchical generative models such as deep belief networks. Scaling such models to full-sized, high-dimensional images remains a difficult problem. To address this problem, we present the convolutional deep belief network, a hierarchical generative model which scales to realistic image sizes. This model is translation-invariant and supports efficient bottom-up and top-down probabilistic inference. Key to our approach is probabilistic max-pooling, a novel technique which shrinks the representations of higher layers in a probabilistically sound way. Our experiments show that the algorithm learns useful high-level visual features, such as object parts, from unlabeled images of objects and natural scenes. We demonstrate excellent performance on several visual recognition tasks and show that our model can perform hierarchical (bottom-up and top-down) inference over full-sized images.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {609–616},
numpages = {8}
}

@inproceedings{10.1145/1553374.1553454,
author = {Li, Bin and Yang, Qiang and Xue, Xiangyang},
title = {Transfer Learning for Collaborative Filtering via a Rating-Matrix Generative Model},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553454},
doi = {10.1145/1553374.1553454},
abstract = {Cross-domain collaborative filtering solves the sparsity problem by transferring rating knowledge across multiple domains. In this paper, we propose a rating-matrix generative model (RMGM) for effective cross-domain collaborative filtering. We first show that the relatedness across multiple rating matrices can be established by finding a shared implicit cluster-level rating matrix, which is next extended to a cluster-level rating model. Consequently, a rating matrix of any related task can be viewed as drawing a set of users and items from a user-item joint mixture model as well as drawing the corresponding ratings from the cluster-level rating model. The combination of these two models gives the RMGM, which can be used to fill the missing ratings for both existing and new users. A major advantage of RMGM is that it can share the knowledge by pooling the rating data from multiple tasks even when the users and items of these tasks do not overlap. We evaluate the RMGM empirically on three real-world collaborative filtering data sets to show that RMGM can outperform the individual models trained separately.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {617–624},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553455,
author = {Li, Ping},
title = {ABC-Boost: Adaptive Base Class Boost for Multi-Class Classification},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553455},
doi = {10.1145/1553374.1553455},
abstract = {We propose abc-boost (adaptive base class boost) for multi-class classification and present abc-mart, an implementation of abc-boost, based on the multinomial logit model. The key idea is that, at each boosting iteration, we adaptively and greedily choose a base class. Our experiments on public datasets demonstrate the improvement of abc-mart over the original mart algorithm.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {625–632},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553456,
author = {Li, Yu-Feng and Kwok, James T. and Zhou, Zhi-Hua},
title = {Semi-Supervised Learning Using Label Mean},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553456},
doi = {10.1145/1553374.1553456},
abstract = {Semi-Supervised Support Vector Machines (S3VMs) typically directly estimate the label assignments for the unlabeled instances. This is often inefficient even with recent advances in the efficient training of the (supervised) SVM. In this paper, we show that S3VMs, with knowledge of the means of the class labels of the unlabeled data, is closely related to the supervised SVM with known labels on all the unlabeled data. This motivates us to first estimate the label means of the unlabeled data. Two versions of the meanS3VM, which work by maximizing the margin between the label means, are proposed. The first one is based on multiple kernel learning, while the second one is based on alternating optimization. Experiments show that both of the proposed algorithms achieve highly competitive and sometimes even the best performance as compared to the state-of-the-art semi-supervised learners. Moreover, they are more efficient than existing S3VMs.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {633–640},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553457,
author = {Liang, Percy and Jordan, Michael I. and Klein, Dan},
title = {Learning from Measurements in Exponential Families},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553457},
doi = {10.1145/1553374.1553457},
abstract = {Given a model family and a set of unlabeled examples, one could either label specific examples or state general constraints---both provide information about the desired model. In general, what is the most cost-effective way to learn? To address this question, we introduce measurements, a general class of mechanisms for providing information about a target model. We present a Bayesian decision-theoretic framework, which allows us to both integrate diverse measurements and choose new measurements to make. We use a variational inference algorithm, which exploits exponential family duality. The merits of our approach are demonstrated on two sequence labeling tasks.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {641–648},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553458,
author = {Liu, Han and Palatucci, Mark and Zhang, Jian},
title = {Blockwise Coordinate Descent Procedures for the Multi-Task Lasso, with Applications to Neural Semantic Basis Discovery},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553458},
doi = {10.1145/1553374.1553458},
abstract = {We develop a cyclical blockwise coordinate descent algorithm for the multi-task Lasso that efficiently solves problems with thousands of features and tasks. The main result shows that a closed-form Winsorization operator can be obtained for the sup-norm penalized least squares regression. This allows the algorithm to find solutions to very large-scale problems far more efficiently than existing methods. This result complements the pioneering work of Friedman, et al. (2007) for the single-task Lasso. As a case study, we use the multi-task Lasso as a variable selector to discover a semantic basis for predicting human neural activation. The learned solution outperforms the standard basis for this task on the majority of test participants, while requiring far fewer assumptions about cognitive neuroscience. We demonstrate how this learned basis can yield insights into how the brain represents the meanings of words.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {649–656},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553459,
author = {Liu, Jun and Ye, Jieping},
title = {Efficient Euclidean Projections in Linear Time},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553459},
doi = {10.1145/1553374.1553459},
abstract = {We consider the problem of computing the Euclidean projection of a vector of length n onto a closed convex set including the l1 ball and the specialized polyhedra employed in (Shalev-Shwartz & Singer, 2006). These problems have played building block roles in solving several l1-norm based sparse learning problems. Existing methods have a worst-case time complexity of O(n log n). In this paper, we propose to cast both Euclidean projections as root finding problems associated with specific auxiliary functions, which can be solved in linear time via bisection. We further make use of the special structure of the auxiliary functions, and propose an improved bisection algorithm. Empirical studies demonstrate that the proposed algorithms are much more efficient than the competing ones for computing the projections.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {657–664},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553460,
author = {Liu, Yan and Niculescu-Mizil, Alexandru and Gryc, Wojciech},
title = {Topic-Link LDA: Joint Models of Topic and Author Community},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553460},
doi = {10.1145/1553374.1553460},
abstract = {Given a large-scale linked document collection, such as a collection of blog posts or a research literature archive, there are two fundamental problems that have generated a lot of interest in the research community. One is to identify a set of high-level topics covered by the documents in the collection; the other is to uncover and analyze the social network of the authors of the documents. So far these problems have been viewed as separate problems and considered independently from each other. In this paper we argue that these two problems are in fact inter-dependent and should be addressed together. We develop a Bayesian hierarchical approach that performs topic modeling and author community discovery in one unified framework. The effectiveness of our model is demonstrated on two blog data sets in different domains and one research paper citation data from CiteSeer.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {665–672},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.1553461,
author = {Lu, Zhengdong and Jain, Prateek and Dhillon, Inderjit S.},
title = {Geometry-Aware Metric Learning},
year = {2009},
isbn = {9781605585161},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1553374.1553461},
doi = {10.1145/1553374.1553461},
abstract = {In this paper, we introduce a generic framework for semi-supervised kernel learning. Given pair-wise (dis-)similarity constraints, we learn a kernel matrix over the data that respects the provided side-information as well as the local geometry of the data. Our framework is based on metric learning methods, where we jointly model the metric/kernel over the data along with the underlying manifold. Furthermore, we show that for some important parameterized forms of the underlying manifold model, we can estimate the model parameters and the kernel matrix efficiently. Our resulting algorithm is able to incorporate local geometry into the metric learning task; at the same time it can handle a wide class of constraints. Finally, our algorithm is fast and scalable -- unlike most of the existing methods, it is able to exploit the low dimensional manifold structure and does not require semi-definite programming. We demonstrate wide applicability and effectiveness of our framework by applying to various machine learning tasks such as semi-supervised classification, colored dimensionality reduction, manifold alignment etc. On each of the tasks our method performs competitively or better than the respective state-of-the-art method.},
booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning},
pages = {673–680},
numpages = {8},
location = {Montreal, Quebec, Canada},
series = {ICML '09}
}

@inproceedings{10.1145/1553374.155

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr