OpenRaiser/Intern-Atlas huggingface dataset:
Locally adaptive classification piloted by uncertainty
Authors: Juan Dai, Shuicheng Yan, Xiaoou Tang, James T. Kwok
Venue: ICML
Year: 2006

Locally adaptive classifiers are usually superior to the use of a single global classifier. However, there are two major problems in designing locally adaptive classifiers. First, how to place the local classifiers, and, second, how to combine them together. In this paper, instead of placing the classifiers based on the data distribution only, we propose a responsibility mixture model that uses the uncertainty associated with the classification at each training sample. Using this model, the local classifiers are placed near the decision boundary where they are most effective. A set of local classifiers are then learned to form a global classifier by maximizing an estimate of the probability that the samples will be correctly classified with a nearest neighbor classifier. Experimental results on both artificial and real-world data sets demonstrate its superiority over traditional algorithms.
Collaborative prediction using ensembles of Maximum Margin Matrix Factorizations
Authors: Dennis DeCoste
Venue: ICML
Year: 2006

Fast gradient-based methods for Maximum Margin Matrix Factorization (MMMF) were recently shown to have great promise (Rennie & Srebro, 2005), including significantly outperforming the previous state-of-the-art methods on some standard collaborative prediction benchmarks (including MovieLens). In this paper, we investigate ways to further improve the performance of MMMF, by casting it within an ensemble approach. We explore and evaluate a variety of alternative ways to define such ensembles. We show that our resulting ensembles can perform significantly better than a single MMMF model, along multiple evaluation metrics. In fact, we find that ensembles of partially trained MMMF models can sometimes even give better predictions in total training time comparable to a single MMMF model.
Efficient learning of Naive Bayes classifiers under class-conditional classification noise
Authors: François Denis, Christophe Nicolas Magnan, Liva Ralaivola
Venue: ICML
Year: 2006

We address the problem of efficiently learning Naive Bayes classifiers under class-conditional classification noise (CCCN). Naive Bayes classifiers rely on the hypothesis that the distributions associated to each class are product distributions. When data is subject to CCC-noise, these conditional distributions are themselves mixtures of product distributions. We give analytical formulas which makes it possible to identify them from data subject to CCCN. Then, we design a learning algorithm based on these formulas able to learn Naive Bayes classifiers under CCCN. We present results on artificial datasets and datasets extracted from the UCI repository database. These results show that CCCN can be efficiently and successfully handled.
R1-PCA: rotational invariant L1-norm principal component analysis for robust subspace factorization
Authors: Chris H. Q. Ding, Ding Zhou, Xiaofeng He, Hongyuan Zha
Venue: ICML
Year: 2006

Principal component analysis (PCA) minimizes the sum of squared errors (L2-norm) and is sensitive to the presence of outliers. We propose a rotational invariant L1-norm PCA (R1-PCA). R1-PCA is similar to PCA in that (1) it has a unique global solution, (2) the solution are principal eigenvectors of a robust covariance matrix (re-weighted to soften the effects of outliers), (3) the solution is rotational invariant. These properties are not shared by the L1-norm PCA. A new subspace iteration algorithm is given to compute R1-PCA efficiently. Experiments on several real-life datasets show R1-PCA can effectively handle outliers. We extend R1-norm to K-means clustering and show that L1-norm K-means leads to poor results while R1-K-means outperforms standard K-means.
A graphical model for predicting protein molecular function
Authors: Barbara E. Engelhardt, Michael I. Jordan, Steven E. Brenner
Venue: ICML
Year: 2006

We present a simple statistical model of molecular function evolution to predict protein function. The model description encodes general knowledge of how molecular function evolves within a phylogenetic tree based on the proteins' sequence. Inputs are a phylogeny for a set of evolutionarily related protein sequences and any available function characterizations for those proteins. Posterior probabilities for each protein are used to predict the molecular function of that protein. We present results from applying our model to three protein families, and compare our prediction results on the extant proteins to other available protein function prediction methods. For the deaminase family, our method achieves 93.9% where related methods BLAST achieves 72.7%, GOtcha achieves 87.9%, and Orthostrapper achieves 72.7% in prediction accuracy.
A note on mixtures of experts for multiclass responses: approximation rate and Consistent Bayesian Inference
Authors: Yang Ge, Wenxin Jiang 0003
Venue: ICML
Year: 2006

We report that mixtures of m multinomial logistic regression can be used to approximate a class of 'smooth' probability models for multiclass responses. With bounded second derivatives of log-odds, the approximation rate is O(m-2/s) in Hellinger distance or O(m-4/s) in Kullback-Leibler divergence. Here s = dim(x) is the dimension of the input space (or the number of predictors). With the availability of training data of size n, we also show that 'consistency' in multiclass regression and classification can be achieved, simultaneously for all classes, when posterior based inference is performed in a Bayesian framework. Loosely speaking, such 'consistency' refers to performance being often close to the best possible for large n. Consistency can be achieved either by taking m = mn, or by taking m to be uniformly distributed among {1, ...,mn} according to the prior, where 1 ≺ mn ≺ na in order as n grows, for some a ∈ (0, 1).
Fast transpose methods for kernel learning on sparse data
Authors: Patrick Haffner
Venue: ICML
Year: 2006

Kernel-based learning algorithms, such as Support Vector Machines (SVMs) or Perceptron, often rely on sequential optimization where a few examples are added at each iteration. Updating the kernel matrix usually requires matrix-vector multiplications. We propose a new method based on transposition to speedup this computation on sparse data. Instead of dot-products over sparse feature vectors, our computation incrementally merges lists of training examples and minimizes access to the data. Caching and shrinking are also optimized for sparsity. On very large natural language tasks (tagging, translation, text classification) with sparse feature representations, a 20 to 80-fold speedup over LIBSVM is observed using the same SMO algorithm. Theory and experiments explain what type of sparsity structure is needed for this approach to work, and why its adaptation to Maxent sequential optimization is inefficient.
Learning a kernel function for classification with small training samples
Authors: Tomer Hertz, Aharon Bar-Hillel, Daphna Weinshall
Venue: ICML
Year: 2006

When given a small sample, we show that classification with SVM can be considerably enhanced by using a kernel function learned from the training data prior to discrimination. This kernel is also shown to enhance retrieval based on data similarity. Specifically, we describe KernelBoost - a boosting algorithm which computes a kernel function as a combination of 'weak' space partitions. The kernel learning method naturally incorporates domain knowledge in the form of unlabeled data (i.e. in a semi-supervised or transductive settings), and also in the form of labeled samples from relevant related problems (i.e. in a learning-to-learn scenario). The latter goal is accomplished by learning a single kernel function for all classes. We show comparative evaluations of our method on datasets from the UCI repository. We demonstrate performance enhancement on two challenging tasks: digit classification with kernel SVM, and facial image retrieval based on image similarity as measured by the learnt kernel.
Batch mode active learning and its application to medical image classification
Authors: Steven C. H. Hoi, Rong Jin 0001, Jianke Zhu, Michael R. Lyu
Venue: ICML
Year: 2006

The goal of active learning is to select the most informative examples for manual labeling. Most of the previous studies in active learning have focused on selecting a single unlabeled example in each iteration. This could be inefficient since the classification model has to be retrained for every labeled example. In this paper, we present a framework for "batch mode active learning" that applies the Fisher information matrix to select a number of informative examples simultaneously. The key computational challenge is how to efficiently identify the subset of unlabeled examples that can result in the largest reduction in the Fisher information. To resolve this challenge, we propose an efficient greedy algorithm that is based on the property of submodular functions. Our empirical studies with five UCI datasets and one real-world medical image classification show that the proposed batch mode active learning algorithm is more effective than the state-of-the-art algorithms for active learning.
Ranking individuals by group comparisons
Authors: Tzu-Kuo Huang, Chih-Jen Lin, Ruby C. Weng
Venue: ICML
Year: 2006

This paper proposes new approaches to rank individuals from their group competition results. Many real-world problems are of this type. For example, ranking players from team games is important in some sports. We propose an exponential model to solve such problems. To estimate individual rankings through the proposed model we introduce two convex minimization formulas with easy and efficient solution procedures. Experiments on real bridge records and multi-class classification demonstrate the viability of the proposed model.
Hidden process models
Authors: Rebecca A. Hutchinson, Tom M. Mitchell, Indrayana Rustandi
Venue: ICML
Year: 2006

We introduce Hidden Process Models (HPMs), a class of probabilistic models for multivariate time series data. The design of HPMs has been motivated by the challenges of modeling hidden cognitive processes in the brain, given functional Magnetic Resonance Imaging (fMRI) data. fMRI data is sparse, high-dimensional, non-Markovian, and often involves prior knowledge of the form "hidden event A occurs n times within the interval [t,t′]." HPMs provide a generalization of the widely used General Linear Model approaches to fMRI analysis, and HPMs can also be viewed as a subclass of Dynamic Bayes Networks.
Pareto optimal linear classification
Authors: Seung-Jean Kim, Alessandro Magnani, Sikandar Samar, Stephen P. Boyd, Johan Lim
Venue: ICML
Year: 2006

We consider the problem of choosing a linear classifier that minimizes misclassification probabilities in two-class classification, which is a bi-criterion problem, involving a trade-off between two objectives. We assume that the class-conditional distributions are Gaussian. This assumption makes it computationally tractable to find Pareto optimal linear classifiers whose classification capabilities are inferior to no other linear ones. The main purpose of this paper is to establish several robustness properties of those classifiers with respect to variations and uncertainties in the distributions. We also extend the results to kernel-based classification. Finally, we show how to carry out trade-off analysis empirically with a finite number of given labeled data.
Autonomous shaping: knowledge transfer in reinforcement learning
Authors: George Dimitri Konidaris, Andrew G. Barto
Venue: ICML
Year: 2006

We introduce the use of learned shaping rewards in reinforcement learning tasks, where an agent uses prior experience on a sequence of tasks to learn a portable predictor that estimates intermediate rewards, resulting in accelerated learning in later tasks that are related but distinct. Such agents can be trained on a sequence of relatively easy tasks in order to develop a more informative measure of reward that can be transferred to improve performance on more difficult tasks without requiring a hand coded shaping function. We use a rod positioning task to show that this significantly improves performance even after a very brief training period.
Learning low-rank kernel matrices
Authors: Brian Kulis, Mátyás A. Sustik, Inderjit S. Dhillon
Venue: ICML
Year: 2006

Kernel learning plays an important role in many machine learning tasks. However, algorithms for learning a kernel matrix often scale poorly, with running times that are cubic in the number of data points. In this paper, we propose efficient algorithms for learning lowrank kernel matrices; our algorithms scale linearly in the number of data points and quadratically in the rank of the kernel. We introduce and employ Bregman matrix divergences for rank-deficient matrices—these divergences are natural for our problem since they preserve the rank as well as positive semi-definiteness of the kernel matrix. Special cases of our framework yield faster algorithms for various existing kernel learning problems. Experimental results demonstrate the effectiveness of our algorithms in learning both low-rank and full-rank kernels. 1.
Using query-specific variance estimates to combine Bayesian classifiers
Authors: Chi-Hoon Lee, Russell Greiner, Shaojun Wang
Venue: ICML
Year: 2006

Many of today's best classification results are obtained by combining the responses of a set of base classifiers to produce an answer for the query. This paper explores a novel "query specific" combination rule: After learning a set of simple belief network classifiers, we produce an answer to each query by combining their individual responses, using weights based inversely on their respective variances around their responses. These variances are based on the uncertainty of the network parameters, which in turn depend on the training datasample. In essence, this variance quantifies the base classifier's confidence of its response to this query. Our experimental results show that these "mixture-using-variance belief net classifiers" MUVS work effectively, especially when the base classifiers are learned using balanced bootstrap samples and when their results are combined using James-Stein shrinkage. We also found that our variance-based combination rule performed better than both bagging and AdaBoost, even on the set of base classifiers produced by AdaBoost itself. Finally, this framework is extremely efficient, as both the learning and the classification components require only straight-line code.
A probabilistic model for text kernels
Authors: Alain D. Lehmann, John Shawe-Taylor
Venue: ICML
Year: 2006

This paper explores several kernels in the context of text classification. A novel view of how documents might have been created is introduced and kernels are derived from this framework. The relations between these kernels as well as to the Gaussian kernel are discussed. Moreover, the popular tf-idf weighting scheme will be derived as a natural consequence. Finally, the kernels have been evaluated on the Requiers Corpus Volume I newswire database to assess their quality in a topic classification application.
Efficient MAP approximation for dense energy functions
Authors: Marius Leordeanu, Martial Hebert
Venue: ICML
Year: 2006

We present an efficient method for maximizing energy functions with first and second order potentials, suitable for MAP labeling estimation problems that arise in undirected graphical models. Our approach is to relax the integer constraints on the solution in two steps. First we efficiently obtain the relaxed global optimum following a procedure similar to the iterative power method for finding the largest eigenvector of a matrix. Next, we map the relaxed optimum on a simplex and show that the new energy obtained has a certain optimal bound. Starting from this energy we follow an efficient coordinate ascent procedure that is guaranteed to increase the energy at every step and converge to a solution that obeys the initial integral constraints. We also present a sufficient condition for ascent procedures that guarantees the increase in energy at every step.
Region-based value iteration for partially observable Markov decision processes
Authors: Hui Li 0068, Xuejun Liao, Lawrence Carin
Venue: ICML
Year: 2006

An approximate region-based value iteration (RBVI) algorithm is proposed to find the optimal policy for a partially observable Markov decision process (POMDP). The proposed RBVI approximates the true polyhedral partition of the belief simplex with an ellipsoidal partition, such that the optimal value function is linear in each of the ellipsoidal regions. The position and shape of each region, as well as the gradient (alpha-vector) of the optimal value function in the region, are parameterized explicitly, and are estimated via efficient expectation maximization (EM) and variational Bayesian EM (VBEM), based on a set of selected sample belief points. The RBVI maintains a much smaller number of alpha-vectors than point-based methods and yields a more parsimonious representation that approximates the true value function in the maximum likelihood (ML) sense. The results on benchmark problems show that the proposed RBVI is comparable in performance to state-of-the-art algorithms, despite of the small number of alpha-vectors that are used.
Combined central and subspace clustering for computer vision applications
Authors: Le Lu 0001, René Vidal
Venue: ICML
Year: 2006

Central and subspace clustering methods are at the core of many segmentation problems in computer vision. However, both methods fail to give the correct segmentation in many practical scenarios, e.g., when data points are close to the intersection of two subspaces or when two cluster centers in different subspaces are spatially close. In this paper, we address these challenges by considering the problem of clustering a set of points lying in a union of subspaces and distributed around multiple cluster centers inside each subspace. We propose a generalization of Kmeans and Ksubspaces that clusters the data by minimizing a cost function that combines both central and subspace distances. Experiments on synthetic data compare our algorithm favorably against four other clustering methods. We also test our algorithm on computer vision problems such as face clustering with varying illumination and video shot segmentation of dynamic scenes.
Learning high-order MRF priors of color images
Authors: Julian J. McAuley, Tibério S. Caetano, Alexander J. Smola, Matthias O. Franz
Venue: ICML
Year: 2006

In this paper, we use large neighborhood Markov random fields to learn rich prior models of color images. Our approach extends the monochromatic Fields of Experts model (Roth & Black, 2005a) to color images. In the Fields of Experts model, the curse of dimensionality due to very large clique sizes is circumvented by parameterizing the potential functions according to a product of experts. We introduce simplifications to the original approach by Roth and Black which allow us to cope with the increased clique size (typically 3x3x3 or 5x5x3 pixels) of color images. Experimental results are presented for image denoising which evidence improvements over state-of-the-art monochromatic image priors.
Learning to impersonate
Authors: Moni Naor, Guy N. Rothblum
Venue: ICML
Year: 2006

Consider Alice and Bob, who have some shared secret which helps Alice to identify Bob-impersonators, and Eve, who does not know their secret. Eve wants to impersonate Bob and "fool" Alice. If Eve is computationally unbounded, how long does she need to observe Bob before she can impersonate him? What is a good strategy for Eve? If (cryptographic) one-way functions exist, an efficient Eve cannot impersonate even very simple Bobs, but if they do not exist, can Eve learn to impersonate any efficient Bob?We formalize these questions in a new computational learning model, which we believe captures a wide variety of natural learning tasks, and tightly bound the number of observations Eve makes in terms of the secret's entropy. We then show that if one-way functions do not exist, then an efficient Eve can learn to impersonate any efficient Bob nearly as well as an unbounded Eve.For the full version of this work see (Naor & Rothblum, 2006).
Learning hierarchical task networks by observation
Authors: Negin Nejati, Pat Langley, Tolga Könik
Venue: ICML
Year: 2006

Knowledge-based planning methods offer benefits over classical techniques, but they are time consuming and costly to construct. There has been research on learning plan knowledge from search, but this can take substantial computer time and may even fail to find solutions on complex tasks. Here we describe another approach that observes sequences of operators taken from expert solutions to problems and learns hierarchical task networks from them. The method has similarities to previous algorithms for explanation-based learning, but differs in its ability to acquire hierarchical structures and in the generality of learned conditions. These increase the method's capability to transfer learned knowledge to other problems and supports the acquisition of recursive procedures. After presenting the learning algorithm, we report experiments that compare its abilities to other techniques on two planning domains. In closing, we review related work and directions for future research.
Reinforcement learning for optimized trade execution
Authors: Yuriy Nevmyvaka, Yi Feng, Michael J. Kearns
Venue: ICML
Year: 2006

We present the first large-scale empirical application of reinforcement learning to the important problem of optimized trade execution in modern financial markets. Our experiments are based on 1.5 years of millisecond time-scale limit order data from NASDAQ, and demonstrate the promise of reinforcement learning methods to market microstructure problems. Our learning algorithm introduces and exploits a natural &amp;quot;low-impact &amp;quot; factorization of the state space. 1.
Concept boundary detection for speeding up SVMs
Authors: Navneet Panda, Edward Y. Chang, Gang Wu 0005
Venue: ICML
Year: 2006

Support Vector Machines (SVMs) suffer from an O(n2) training cost, where n denotes the number of training instances. In this paper, we propose an algorithm to select boundary instances as training data to substantially reduce n. Our proposed algorithm is motivated by the result of (Burges, 1999) that, removing non-support vectors from the training set does not change SVM training results. Our algorithm eliminates instances that are likely to be non-support vectors. In the concept-independent preprocessing step of our algorithm, we prepare nearest-neighbor lists for training instances. In the concept-specific sampling step, we can then effectively select useful training data for each target concept. Empirical studies show our algorithm to be effective in reducing n, outperforming other competing downsampling algorithms without significantly compromising testing accuracy.
CN = CPCN
Authors: Liva Ralaivola, François Denis, Christophe Nicolas Magnan
Venue: ICML
Year: 2006

We address the issue of the learnability of concept classes under three classification noise models in the probably approximately correct framework. After introducing the Class-Conditional Classification Noise (CCCN) model, we investigate the problem of the learnability of concept classes under this particular setting and we show that concept classes that are learnable under the well-known uniform classification noise (CN) setting are also CCCN-learnable, which gives CN = CCCN. We then use this result to prove the equality between the set of concept classes that are CN-learnable and the set of concept classes that are learnable in the Constant Partition Classification Noise (CPCN) setting, or, in other words, we show that CN = CPCN.