OpenRaiser/Intern-Atlas huggingface dataset:
Online discovery of similarity mappings
Authors: Alexander Rakhlin, Jacob D. Abernethy, Peter L. Bartlett
Venue: ICML
Year: 2007

We consider the problem of choosing, sequentially, a map which assigns elements of a set A to a few elements of a set B. On each round, the algorithm suffers some cost associated with the chosen assignment, and the goal is to minimize the cumulative loss of these choices relative to the best map on the entire sequence. Even though the offline problem of finding the best map is provably hard, we show that there is an equivalent online approximation algorithm, Randomized Map Prediction (RMP), that is efficient and performs nearly as well. While drawing upon results from the “Online Prediction with Expert Advice ” setting, we show how RMP can be utilized as an online approach to several standard batch problems. We apply RMP to online clustering as well as online feature selection and, surprisingly, RMP often outperforms the standard batch algorithms on these problems. 1.
Graph clustering with network structure indices
Authors: Matthew J. Rattigan, Marc E. Maier, David D. Jensen
Venue: ICML
Year: 2007

Graph clustering has become ubiquitous in the study of relational data sets. We examine two simple algorithms: a new graphical adaptation of the k-medoids algorithm and the Girvan-Newman method based on edge betweenness centrality. We show that they can be effective at discovering the latent groups or communities that are defined by the link structure of a graph. However, both approaches rely on prohibitively expensive computations, given the size of modern relational data sets. Network structure indices (NSIs) are a proven technique for indexing network structure and efficiently finding short paths. We show how incorporating NSIs into these graph clustering algorithms can overcome these complexity limitations. We also present promising quantitative and qualitative evaluations of the modified algorithms on synthetic and real data sets.
Restricted Boltzmann machines for collaborative filtering
Authors: Ruslan Salakhutdinov, Andriy Mnih, Geoffrey E. Hinton
Venue: ICML
Year: 2007

Most of the existing approaches to collaborative filtering cannot handle very large data sets. In this paper we show how a class of two-layer undirected graphical models, called Restricted Boltzmann Machines (RBM's), can be used to model tabular data, such as user's ratings of movies. We present efficient learning and inference procedures for this class of models and demonstrate that RBM's can be successfully applied to the Netflix data set, containing over 100 million user/movie ratings. We also show that RBM's slightly outperform carefully-tuned SVD models. When the predictions of multiple RBM models and multiple SVD models are linearly combined, we achieve an error rate that is well over 6% better than the score of Netflix's own system.
Sparse eigen methods by D.C. programming
Authors: Bharath K. Sriperumbudur, David A. Torres, Gert R. G. Lanckriet
Venue: ICML
Year: 2007

Eigenvalue problems are rampant in machine learning and statistics and appear in the context of classification, dimensionality reduction, etc. In this paper, we consider a cardinality constrained variational formulation of generalized eigenvalue problem with sparse principal component analysis (PCA) as a special case. Using l1-norm approximation to the cardinality constraint, previous methods have proposed both convex and non-convex solutions to the sparse PCA problem. In contrast, we propose a tighter approximation that is related to the negative log-likelihood of a Student's t-distribution. The problem is then framed as a d.c. (difference of convex functions) program and is solved as a sequence of locally convex programs. We show that the proposed method not only explains more variance with sparse loadings on the principal directions but also has better scalability compared to other methods. We demonstrate these results on a collection of datasets of varying dimensionality, two of which are high-dimensional gene datasets where the goal is to find few relevant genes that explain as much variance as possible.
Learning to solve game trees
Authors: David H. Stern, Ralf Herbrich, Thore Graepel
Venue: ICML
Year: 2007

We apply probability theory to the task of proving whether a goal can be achieved by a player in an adversarial game. Such problems are solved by searching the game tree. We view this tree as a graphical model which yields a distribution over the (Boolean) outcome of the search before it terminates. Experiments show that a best-first search algorithm guided by this distribution explores a similar number of nodes as Proof-Number Search to solve Go problems. Knowledge is incorporated into search by using domain-specific models to provide prior distributions over the values of leaf nodes of the game tree. These are surrogate for the unexplored parts of the tree. The parameters of these models can be learned from previous search trees. Experiments on Go show that the speed of problem solving can be increased by orders of magnitude by this technique but care must be taken to avoid over-fitting.
Robust mixtures in the presence of measurement errors
Authors: Jianyong Sun, Ata Kabán, Somak Raychaudhury
Venue: ICML
Year: 2007

We develop a mixture-based approach to robust density modeling and outlier detection for experimental multivariate data that includes measurement error information. Our model is designed to infer atypical measurements that are not due to errors, aiming to retrieve potentially interesting peculiar objects. Since exact inference is not possible in this model, we develop a tree-structured variational EM solution. This compares favorably against a fully factorial approximation scheme, approaching the accuracy of a Markov-Chain-EM, while maintaining computational simplicity. We demonstrate the benefits of including measurement errors in the model, in terms of improved outlier detection rates in varying measurement uncertainty conditions. We then use this approach for detecting peculiar quasars from an astrophysical survey, given photometric measurements with errors.
Incremental Bayesian networks for structure prediction
Authors: Ivan Titov 0001, James Henderson 0001
Venue: ICML
Year: 2007

We propose a class of graphical models appropriate for structure prediction problems where the model structure is a function of the output structure. Incremental Sigmoid Belief Networks (ISBNs) avoid the need to sum over the possible model structures by using directed arcs and incrementally specifying the model structure. Exact inference in such directed models is not tractable, but we derive two efficient approximations based on mean field methods, which prove effective in artificial experiments. We then demonstrate their effectiveness on a benchmark natural language parsing task, where they achieve state-of-the-art accuracy. Also, the model which is a closer approximation to an ISBN has better parsing accuracy, suggesting that ISBNs are an appropriate abstract model of structure prediction tasks.
Learning from interpretations: a rooted kernel for ordered hypergraphs
Authors: Gabriel Wachman, Roni Khardon
Venue: ICML
Year: 2007

The paper presents a kernel for learning from ordered hypergraphs, a formalization that captures relational data as used in Inductive Logic Programming (ILP). The kernel generalizes previous approaches to graph kernels in calculating similarity based on walks in the hypergraph. Experiments on challenging chemical datasets demonstrate that the kernel outperforms existing ILP methods, and is competitive with state-of-the-art graph kernels. The experiments also demonstrate that the encoding of graph data can affect performance dramatically, a fact that can be useful beyond kernel methods.
Transductive regression piloted by inter-manifold relations
Authors: Huan Wang 0001, Shuicheng Yan, Thomas S. Huang, Jianzhuang Liu, Xiaoou Tang
Venue: ICML
Year: 2007

In this paper, we present a novel semisupervised regression algorithm working on multiclass data that may lie on multiple manifolds. Unlike conventional manifold regression algorithms that do not consider the class distinction of samples, our method introduces the class information to the regression process and tries to exploit the similar configurations shared by the label distribution of multi-class data. To utilize the correlations among data from different classes, we develop a cross-manifold label propagation process and employ labels from different classes to enhance the regression performance. The interclass relations are coded by a set of intermanifold graphs and a regularization item is introduced to impose inter-class smoothness on the possible solutions. In addition, the algorithm is further extended with the kernel trick for predicting labels of the out-of-sample data even without class information. Experiments on both synthesized data and real world problems validate the effectiveness of the proposed framework for semisupervised regression.
Dirichlet aggregation: unsupervised learning towards an optimal metric for proportional data
Authors: Hua-Yan Wang, Hongbin Zha, Hong Qin 0001
Venue: ICML
Year: 2007

Proportional data (normalized histograms) have been frequently occurring in various areas, and they could be mathematically abstracted as points residing in a geometric simplex. A proper distance metric on this simplex is of importance in many applications including classification and information retrieval. In this paper, we develop a novel framework to learn an optimal metric on the simplex. Major features of our approach include: 1) its flexibility to handle correlations among bins/dimensions; 2) widespread applicability without being limited to ad hoc backgrounds; and 3) a "real" global solution in contrast to existing traditional local approaches. The technical essence of our approach is to fit a parametric distribution to the observed empirical data in the simplex. The distribution is parameterized by affinities between simplex vertices, which is learned via maximizing likelihood of observed data. Then, these affinities induce a metric on the simplex, defined as the earth mover's distance equipped with ground distances derived from simplex vertex affinities.
Hybrid huberized support vector machines for microarray classification
Authors: Li Wang, Ji Zhu, Hui Zou
Venue: ICML
Year: 2007

The large number of genes and the relatively small number of samples are typical characteristics for microarray data. These characteristics pose challenges for both sample classification and relevant gene selection. The support vector machine (SVM) is a widely used classification technique, and previous studies have demonstrated its superior classification performance in microarray analysis. However, a major limitation is that the SVM can not perform automatic gene selection. To overcome this limitation, we propose the hybrid huberized support vector machine (HHSVM). The HHSVM uses the huberized hinge loss function and the elastic-net penalty. It has two major benefits: 1. automatic gene selection; 2. the grouping effect, where highly correlated genes tend to be selected/removed together. We also develop an efficient algorithm that computes the entire regularized solution path for HHSVM. We have applied our method to real microarray data and achieved promising results. 1.
Winnowing subspaces
Authors: Manfred K. Warmuth
Venue: ICML
Year: 2007

We generalize the Winnow algorithm for learning disjunctions to learning subspaces of low rank. Subspaces are represented by symmetric projection matrices. The online algorithm maintains its uncertainty about the hidden low rank projection matrix as a symmetric positive definite matrix. This matrix is updated using a version of the Matrix Exponentiated Gradient algorithm that is based on matrix exponentials and matrix logarithms. As in the case of the Winnow algorithm, the bounds are logarithmic in the dimension n of the problem, but linear in the rank r of the hidden subspace. We show that the algorithm can be adapted to handle arbitrary matrices of any dimension via a reduction.
Multi-task reinforcement learning: a hierarchical Bayesian approach
Authors: Aaron Wilson, Alan Fern, Soumya Ray, Prasad Tadepalli
Venue: ICML
Year: 2007

We consider the problem of multi-task reinforcement learning, where the agent needs to solve a sequence of Markov Decision Processes (MDPs) chosen randomly from a fixed but unknown distribution. We model the distribution over MDPs using a hierarchical Bayesian infinite mixture model. For each novel MDP, we use the previously learned distribution as an informed prior for modelbased Bayesian reinforcement learning. The hierarchical Bayesian framework provides a strong prior that allows us to rapidly infer the characteristics of new environments based on previous environments, while the use of a nonparametric model allows us to quickly adapt to environments we have not encountered before. In addition, the use of infinite mixtures allows for the model to automatically learn the number of underlying MDP components. We evaluate our approach and show that it leads to significant speedups in convergence to an optimal policy after observing only a small number of tasks.
Beamforming using the relevance vector machine
Authors: David P. Wipf, Srikantan S. Nagarajan
Venue: ICML
Year: 2007

Beamformers are spatial filters that pass source signals in particular focused locations while suppressing interference from elsewhere. The widely-used minimum variance adaptive beamformer (MVAB) creates such filters using a sample covariance estimate; however, the quality of this estimate deteriorates when the sources are correlated or the number of samples n is small. Herein, a modified beamformer is derived that replaces this problematic sample covariance with a robust maximum likelihood estimate obtained using the relevance vector machine (RVM), a Bayesian method for learning sparse models from possibly overcomplete feature sets. We prove that this substitution has the natural ability to remove the undesirable effects of correlations or limited data. When n becomes large and assuming uncorrelated sources, this method reduces to the exact MVAB. Simulations using direction-of-arrival data support these conclusions. Additionally, RVMs can potentially enhance a variety of traditional signal processing methods that rely on robust sample covariance estimates.
Learning to combine distances for complex representations
Authors: Adam Woznica, Alexandros Kalousis, Melanie Hilario
Venue: ICML
Year: 2007

The k-Nearest Neighbors algorithm can be easily adapted to classify complex objects (e.g. sets, graphs) as long as a proper dissimilarity function is given over an input space. Both the representation of the learning instances and the dissimilarity employed on that representation should be determined on the basis of domain knowledge. However, even in the presence of domain knowledge, it can be far from obvious which complex representation should be used or which dissimilarity should be applied on the chosen representation. In this paper we present a framework that allows to combine different complex representations of a given learning problem and/or different dissimilarities defined on these representations. We build on ideas developed previously on metric learning for vectorial data. We demonstrate the utility of our method in domains in which the learning instances are represented as sets of vectors by learning how to combine different set distance measures.
Least squares linear discriminant analysis
Authors: Jieping Ye
Venue: ICML
Year: 2007

Linear Discriminant Analysis (LDA) is a well-known method for dimensionality reduction and classification. LDA in the binaryclass case has been shown to be equivalent to linear regression with the class label as the output. This implies that LDA for binary-class classifications can be formulated as a least squares problem. Previous studies have shown certain relationship between multivariate linear regression and LDA for the multi-class case. Many of these studies show that multivariate linear regression with a specific class indicator matrix as the output can be applied as a preprocessing step for LDA. However, directly casting LDA as a least squares problem is challenging for the multi-class case. In this paper, a novel formulation for multivariate linear regression is proposed. The equivalence relationship between the proposed least squares formulation and LDA for multi-class classifications is rigorously established under a mild condition, which is shown empirically to hold in many applications involving high-dimensional data. Several LDA extensions based on the equivalence relationship are discussed.
Discriminant kernel and regularization parameter learning via semidefinite programming
Authors: Jieping Ye, Jianhui Chen, Shuiwang Ji
Venue: ICML
Year: 2007

Regularized Kernel Discriminant Analysis (RKDA) performs linear discriminant analysis in the feature space via the kernel trick. The performance of RKDA depends on the selection of kernels. In this paper, we consider the problem of learning an optimal kernel over a convex set of kernels. We show that the kernel learning problem can be formulated as a semidefinite program (SDP) in the binary-class case. We further extend the SDP formulation to the multi-class case. It is based on a key result established in this paper, that is, the multi-class kernel learning problem can be decomposed into a set of binary-class kernel learning problems. In addition, we propose an approximation scheme to reduce the computational complexity of the multi-class SDP formulation. The performance of RKDA also depends on the value of the regularization parameter. We show that this value can be learned automatically in the framework. Experimental results on benchmark data sets demonstrate the efficacy of the proposed SDP formulations.
Robust multi-task learning with t-processes
Authors: Shipeng Yu, Volker Tresp, Kai Yu 0001
Venue: ICML
Year: 2007

Most current multi-task learning frameworks ignore the robustness issue, which means that the presence of "outlier" tasks may greatly reduce overall system performance. We introduce a robust framework for Bayesian multitask learning, t-processes (TP), which are a generalization of Gaussian processes (GP) for multi-task learning. TP allows the system to effectively distinguish good tasks from noisy or outlier tasks. Experiments show that TP not only improves overall system performance, but can also serve as an indicator for the "informativeness" of different tasks.
Conditional random fields for multi-agent reinforcement learning
Authors: Xinhua Zhang, Douglas Aberdeen, S. V. N. Vishwanathan
Venue: ICML
Year: 2007

Conditional random fields (CRFs) are graph-ical models for modeling the probability of labels given the observations. They have tra-ditionally been trained with using a set of observation and label pairs. Underlying all CRFs is the assumption that, conditioned on the training data, the labels are independent and identically distributed (iid). In this pa-per we explore the use of CRFs in a class of temporal learning algorithms, namely policy-gradient reinforcement learning (RL). Now the labels are no longer iid. They are ac-tions that update the environment and affect the next observation. From an RL point of view, CRFs provide a natural way to model joint actions in a decentralized Markov de-cision process. They define how agents can communicate with each other to choose the optimal joint action. Our experiments in-clude a synthetic network alignment problem, a distributed sensor network, and road traffic control; clearly outperforming RL methods which do not model the proper joint policy. 1.
Nonlinear independent component analysis with minimal nonlinear distortion
Authors: Kun Zhang 0001, Laiwan Chan
Venue: ICML
Year: 2007

Nonlinear ICA may not result in nonlinear blind source separation, since solutions to nonlinear ICA are highly non-unique. In practice, the nonlinearity in the data generation procedure is usually not strong. Thus it is reasonable to select the solution with the mixing procedure close to linear. In this paper we propose to solve nonlinear ICA with the "minimal nonlinear distortion" principle. This is achieved by incorporating a regularization term to minimize the mean square error between the mixing mapping and the best-fitting linear one. As an application, the proposed method helps to identify linear, non-Gaussian, and acyclic causal models when mild nonlinearity exists in the data generation procedure. Using this method to separate daily returns of a set of stocks, we successfully identify their linear causal relations. The resulting causal relations give some interesting insights into the stock market.
Maximum margin clustering made practical
Authors: Kai Zhang 0001, Ivor W. Tsang, James T. Kwok
Venue: ICML
Year: 2007

Maximum margin clustering (MMC) is a recent large margin unsupervised learning approach that has often outperformed conventional clustering methods. Computationally, it involves non-convex optimization and has to be relaxed to different semidefinite programs (SDP). However, SDP solvers are computationally very expensive and only small data sets can be handled by MMC so far. To make MMC more practical, we avoid SDP relaxations and propose in this paper an efficient approach that performs alternating optimization directly on the original non-convex problem. A key step to avoid premature convergence is on the use of SVR with the Laplacian loss, instead of SVM with the hinge loss, in the inner optimization subproblem. Experiments on a number of synthetic and real-world data sets demonstrate that the proposed approach is often more accurate, much faster and can handle much larger data sets.
Optimal dimensionality of metric space for classification
Authors: Wei Zhang 0016, Xiangyang Xue 0001, Zichen Sun, Yue-Fei Guo, Hong Lu 0001
Venue: ICML
Year: 2007

In many real-world applications, Euclidean distance in the original space is not good due to the curse of dimensionality. In this paper, we propose a new method, called Discriminant Neighborhood Embedding (DNE), to learn an appropriate metric space for classification given finite training samples. We define a discriminant adjacent matrix in favor of classification task, i.e., neighboring samples in the same class are squeezed but those in different classes are separated as far as possible. The optimal dimensionality of the metric space can be estimated by spectral analysis in the proposed method, which is of great significance for high-dimensional patterns. Experiments with various datasets demonstrate the effectiveness of our method.
On the value of pairwise constraints in classification and consistency
Authors: Jian Zhang 0003, Rong Yan
Venue: ICML
Year: 2007

In this paper we consider the problem of classification in the presence of pairwise constraints, which consist of pairs of examples as well as a binary variable indicating whether they belong to the same class or not. We propose a method which can effectively utilize pairwise constraints to construct an estimator of the decision boundary, and we show that the resulting estimator is sign-insensitive consistent with respect to the optimal linear decision boundary. We also study the asymptotic variance of the estimator and extend the method to handle both labeled and pairwise examples in a natural way. Several experiments on simulated datasets and real world classification datasets are conducted. The results not only verify the theoretical properties of the proposed method but also demonstrate its practical value in applications. 1.