OpenRaiser/Intern-Atlas huggingface dataset:
Generalized low rank approximations of matrices
Authors: Jieping Ye
Venue: ICML
Year: 2004

We consider the problem of computing low rank approximations of matrices. The novelty of our approach is that the low rank approximations are on a sequence of matrices. Unlike the problem of low rank approximations of a single matrix, which was well studied in the past, the proposed algorithm in this paper does not admit a closed form solution in general. We did extensive experiments on face image data to evaluate the effectiveness of the proposed algorithm and compare the computed low rank approximations with those obtained from traditional Singular Value Decomposition based method.
Feature extraction via generalized uncorrelated linear discriminant analysis
Authors: Jieping Ye, Ravi Janardan, Qi Li 0001, Haesun Park
Venue: ICML
Year: 2004

Feature extraction is important in many applications, such as text and image retrieval, because of high dimensionality. Uncorrelated Linear Discriminant Analysis (ULDA) was recently proposed for feature extraction. The extracted features via ULDA were shown to be statistically uncorrelated, which is desirable for many applications. In this paper, we will first propose the ULDA/QR algorithm to simplify the previous implementation of ULDA. Then we propose the ULDA/GSVD algorithm, based on a novel optimization criterion, to address the singularity problem. It is applicable for undersampled problem, where the data dimension is much larger than the data size, such as text and image retrieval. The novel criterion used in ULDA/GSVD is the perturbed version of the one from ULDA/QR, while surprisingly, the solution to ULDA/GSVD is shown to be independent of the amount of perturbation applied. We did extensive experiments on text and face image data to show the effectiveness of ULDA/GSVD and compare with other popular feature extraction algorithms.
Learning and evaluating classifiers under sample selection bias
Authors: Bianca Zadrozny
Venue: ICML
Year: 2004

Classifier learning methods commonly assume that the training data consist of randomly drawn examples from the same distribution as the test examples about which the learned model is expected to make predictions. In many practical situations, however, this assumption is violated, in a problem known in econometrics as sample selection bias. In this paper, we formalize the sample selection bias problem in machine learning terms and study analytically and experimentally how a number of well-known classifier learning methods are affected by it. We also present a bias correction method that is particularly useful for classifier evaluation under sample selection bias.
Active learning for Hidden Markov Models: objective functions and algorithms
Authors: Brigham S. Anderson, Andrew Moore
Venue: ICML
Year: 2005

Hidden Markov Models (HMMs) model sequential data in many fields such as text/speech processing and biosignal analysis. Active learning algorithms learn faster and/or better by closing the data-gathering loop, i.e., they choose the examples most informative with respect to their learning objectives. We introduce a framework and objective functions for active learning in three fundamental HMM problems: model learning, state estimation, and path estimation. In addition, we describe a new set of algorithms for efficiently finding optimal greedy queries using these objective functions. The algorithms are fast, i.e., linear in the number of time steps to select the optimal query and we present empirical results showing that these algorithms can significantly reduce the need for labelled training data.
Error limiting reductions between classification tasks
Authors: Alina Beygelzimer, Varsha Dani, Thomas P. Hayes, John Langford 0001, Bianca Zadrozny
Venue: ICML
Year: 2005

We introduce a reduction-based model for analyzing supervised learning tasks. We use this model to devise a new reduction from multi-class cost-sensitive classification to binary classification with the following guarantee: If the learned binary classifier has error rate at most ε then the cost-sensitive classifier has cost at most 2ε times the expected sum of costs of all possible lables. Since cost-sensitive classification can embed any bounded loss finite choice supervised learning task, this result shows that any such task can be solved using a binary classification oracle. Finally, we present experimental results showing that our new reduction outperforms existing algorithms for multi-class cost-sensitive learning.
Reducing overfitting in process model induction
Authors: Will Bridewell, Narges Bani Asadi, Pat Langley, Ljupco Todorovski
Venue: ICML
Year: 2005

In this paper, we review the paradigm of inductive process modeling, which uses background knowledge about possible component processes to construct quantitative models of dynamical systems. We note that previous methods for this task tend to overfit the training data, which suggests ensemble learning as a likely response. However, such techniques combine models in ways that reduce comprehensibility, making their output much less accessible to domain scientists. As an alternative, we introduce a new approach that induces a set of process models from di#erent samples of the training data and uses them to guide a final search through the space of model structures. Experiments with synthetic and natural data suggest this method reduces error and decreases the chance of including unnecessary processes in the model.
Learning class-discriminative dynamic Bayesian networks
Authors: John Burge, Terran Lane
Venue: ICML
Year: 2005

In many domains, a Bayesian network's topological structure is not known a priori and must be inferred from data. This requires a scoring function to measure how well a proposed network topology describes a set of data. Many commonly used scores such as BD, BDE, BDEU, etc., are not well suited for class discrimination. Instead, scores such as the class-conditional likelihood (CCL) should be employed. Unfortunately, CCL does not decompose and its application to large domains is not feasible. We introduce a decomposable score, approximate conditional likelihood (ACL) that is capable of identifying class discriminative structures. We show that dynamic Bayesian networks (DBNs) trained with ACL have classification efficacies competitive to those trained with CCL on a set of simulated data experiments. We also show that ACL-trained DBNs outperform BDE-trained DBNs, Gaussian naive Bayes networks and support vector machines within a neuroscience domain too large for CCL.
Learning to rank using gradient descent
Authors: Christopher J. C. Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, Gregory N. Hullender
Venue: ICML
Year: 2005

We investigate using gradient descent methods for learning ranking functions; we propose a simple probabilistic cost function, and we introduce RankNet, an implementation of these ideas using a neural network to model the underlying ranking function. We present test results on toy data and on data from a commercial internet search engine. 1.
Hedged learning: regret-minimization with learning experts
Authors: Yu-Han Chang, Leslie Pack Kaelbling
Venue: ICML
Year: 2005

In non-cooperative multi-agent situations, there cannot exist a globally optimal, yet opponent-independent learning algorithm. Regret-minimization over a set of strategies optimized for potential opponent models is proposed as a good framework for deciding how to behave in such situations. Using longer playing horizons and experts that learn as they play, the regret-minimization framework can be extended to overcome several shortcomings of earlier approaches to the problem of multi-agent learning.
Variational Bayesian image modelling
Authors: Li Cheng 0001, Feng Jiao, Dale Schuurmans, Shaojun Wang
Venue: ICML
Year: 2005

We present a variational Bayesian framework for performing inference, density estimation and model selection in a special class of graphical models---Hidden Markov Random Fields (HMRFs). HMRFs are particularly well suited to image modelling and in this paper, we apply them to the problem of image segmentation. Unfortunately, HMRFs are notoriously hard to train and use because the exact inference problems they create are intractable. Our main contribution is to introduce an efficient variational approach for performing approximate inference of the Bayesian formulation of HMRFs, which we can then apply to the density estimation and model selection problems that arise when learning image models from data. With this variational approach, we can conveniently tackle the problem of image segmentation. We present experimental results which show that our technique outperforms recent HMRF-based segmentation methods on real world images.
Preference learning with Gaussian processes
Authors: Wei Chu, Zoubin Ghahramani
Venue: ICML
Year: 2005

In this paper, we propose a probabilistic kernel approach to preference learning based on Gaussian processes. A new likelihood function is proposed to capture the preference relations in the Bayesian framework. The generalized formulation is also applicable to tackle many multiclass problems. The overall approach has the advantages of Bayesian methods for model selection and probabilistic prediction. Experimental results compared against the constraint classification approach on several benchmark datasets verify the usefulness of this algorithm.
Learning to compete, compromise, and cooperate in repeated general-sum games
Authors: Jacob W. Crandall, Michael A. Goodrich
Venue: ICML
Year: 2005

Learning algorithms often obtain relatively low average payoffs in repeated general-sum games between other learning agents due to a focus on myopic best-response and one-shot Nash equilibrium (NE) strategies. A less myopic approach places focus on NEs of the repeated game, which suggests that (at the least) a learning agent should possess two properties. First, an agent should never learn to play a strategy that produces average payoffs less than the minimax value of the game. Second, an agent should learn to cooperate/compromise when beneficial. No learning algorithm from the literature is known to possess both of these properties. We present a reinforcement learning algorithm (M-Qubed) that provably satisfies the first property and empirically displays (in self play) the second property in a wide range of games.
Learning as search optimization: approximate large margin methods for structured prediction
Authors: Hal Daumé III, Daniel Marcu
Venue: ICML
Year: 2005

Mappings to structured output spaces (strings, trees, partitions, etc.) are typically learned using extensions of classification algorithms to simple graphical structures (eg., linear chains) in which search and parameter estimation can be performed exactly. Unfortunately, in many complex problems, it is rare that exact search or parameter estimation is tractable. Instead of learning exact models and searching via heuristic means, we embrace this difficulty and treat the structured output problem in terms of approximate search. We present a framework for learning as search optimization, and two parameter updates with convergence the-orems and bounds. Empirical evidence shows that our integrated approach to learning and decoding can outperform exact models at smaller computational cost.
A practical generalization of Fourier-based learning
Authors: Adam Drake, Dan Ventura
Venue: ICML
Year: 2005

This paper presents a search algorithm for finding functions that are highly correlated with an arbitrary set of data. The functions found by the search can be used to approximate the unknown function that generated the data. A special case of this approach is a method for learning Fourier representations. Empirical results demonstrate that on typical real-world problems the most highly correlated functions can be found very quickly, while combinations of these functions provide good approximations of the unknown function.
Combining model-based and instance-based learning for first order regression
Authors: Kurt Driessens, Saso Dzeroski
Venue: ICML
Year: 2005

The introduction of relational reinforcement learning and the RRL algorithm gave rise to the development of several first order regression algorithms. So far, these algorithms have employed either a model-based approach or an instance-based approach. As a consequence, they suffer from the typical drawbacks of model-based learning such as coarse function approximation or those of lazy learning such as high computational intensity.In this paper we develop a new regression algorithm that combines the strong points of both approaches and tries to avoid the normally inherent draw-backs. By combining model-based and instance-based learning, we produce an incremental first order regression algorithm that is both computationally efficient and produces better predictions earlier in the learning experiment.
Reinforcement learning with Gaussian processes
Authors: Yaakov Engel, Shie Mannor, Ron Meir
Venue: ICML
Year: 2005

Gaussian Process Temporal Difference (GPTD) learning offers a Bayesian solution to the policy evaluation problem of reinforcement learning. In this paper we extend the GPTD framework by addressing two pressing issues, which were not adequately treated in the original GPTD paper (Engel et al., 2003). The first is the issue of stochasticity in the state transitions, and the second is concerned with action selection and policy improvement. We present a new generative model for the value function, deduced from its relation with the discounted return. We derive a corresponding on-line algorithm for learning the posterior moments of the value Gaussian process. We also present a SARSA based extension of GPTD, termed GPSARSA, that allows the selection of actions and the gradual improvement of policies without requiring a world-model.
Experimental comparison between bagging and Monte Carlo ensemble classification
Authors: Roberto Esposito, Lorenza Saitta
Venue: ICML
Year: 2005

Properties of ensemble classification can be studied using the framework of Monte Carlo stochastic algorithms. Within this framework it is also possible to define a new ensemble classifier, whose accuracy probability distribution can be computed exactly. This paper has two goals: first, an experimental comparison between the theoretical predictions and experimental results; second, a systematic comparison between bagging and Monte Carlo ensemble classification.
Supervised clustering with support vector machines
Authors: Thomas Finley, Thorsten Joachims
Venue: ICML
Year: 2005

Supervised clustering is the problem of training a clustering algorithm to produce desirable clusterings: given sets of items and complete clusterings over these sets, we learn how to cluster future sets of items. Example applications include noun-phrase coreference clustering, and clustering news articles by whether they refer to the same topic. In this paper we present an SVM algorithm that trains a clustering algorithm by adapting the item-pair similarity measure. The algorithm may optimize a variety of different clustering functions to a variety of clustering performance measures. We empirically evaluate the algorithm for noun-phrase and news article clustering.
Online feature selection for pixel classification
Authors: Karen A. Glocer, Damian Eads, James Theiler
Venue: ICML
Year: 2005

Online feature selection (OFS) provides an efficient way to sort through a large space of features, particularly in a scenario where the feature space is large and features take a significant amount of memory to store. Image processing operators, and especially combinations of image processing operators, provide a rich space of potential features for use in machine learning for image processing tasks but they are expensive to generate and store. In this paper we apply OFS to the problem of edge detection in grayscale imagery. We use a standard data set and compare our results to those obtained with traditional edge detectors, as well as with results obtained more recently using "statistical edge detection." We compare several different OFS approaches, including hill climbing, best first search, and grafting.
Learning strategies for story comprehension: a reinforcement learning approach
Authors: Eugene Grois, David C. Wilkins
Venue: ICML
Year: 2005

This paper describes the use of machine learning to improve the performance of natural language question answering systems. We present a model for improving story comprehension through inductive generalization and reinforcement learning, based on classified examples. In the process, the model selects the most relevant and useful pieces of lexical information to be used by the inference procedure. We compare our approach to three prior non-learning systems, and evaluate the conditions under which learning is effective. We demonstrate that a learning-based approach can improve upon "matching and extraction"-only techniques.
Near-optimal sensor placements in Gaussian processes
Authors: Carlos Guestrin, Andreas Krause 0001, Ajit Paul Singh
Venue: ICML
Year: 2005

When monitoring spatial phenomena, which are often modeled as Gaussian Processes (GPs), choosing sensor locations is a fundamental task. A common strategy is to place sensors at the points of highest entropy (variance) in the GP model. We propose a mutual information criteria, and show that it produces better placements. Furthermore, we prove that finding the configuration that maximizes mutual information is NP-complete. To address this issue, we describe a polynomial-time approximation that is within (1 -- 1/e) of the optimum by exploiting the submodularity of our criterion. This algorithm is extended to handle local structure in the GP, yielding significant speedups. We demonstrate the advantages of our approach on two real-world data sets.
Bayesian hierarchical clustering
Authors: Katherine A. Heller, Zoubin Ghahramani
Venue: ICML
Year: 2005

We present a novel algorithm for agglomerative hierarchical clustering based on evaluating marginal likelihoods of a probabilistic model. This algorithm has several advantages over traditional distance-based agglomerative clustering algorithms. (1) It defines a probabilistic model of the data which can be used to compute the predictive distribution of a test point and the probability of it belonging to any of the existing clusters in the tree. (2) It uses a model-based criterion to decide on merging clusters rather than an ad-hoc distance metric. (3) Bayesian hypothesis testing is used to decide which merges are advantageous and to output the recommended depth of the tree. (4) The algorithm can be interpreted as a novel fast bottom-up approximate inference method for a Dirichlet process (i.e. countably infinite) mixture model (DPM). It provides a new lower bound on the marginal likelihood of a DPM by summing over exponentially many clusterings of the data in polynomial time. We describe procedures for learning the model hyperpa-rameters, computing the predictive distribution, and extensions to the algorithm. Experimental results on synthetic and real-world data sets demonstrate useful properties of the algorithm.
Multi-class protein fold recognition using adaptive codes
Authors: Eugene Ie, Jason Weston, William Stafford Noble, Christina S. Leslie
Venue: ICML
Year: 2005

We develop a novel multi-class classification method based on output codes for the problem of classifying a sequence of amino acids into one of many known protein structural classes, called folds. Our method learns relative weights between one-vs-all classifiers and encodes information about the protein structural hierarchy for multi-class prediction. Our code weighting approach significantly improves on the standard one-vs-all method for the fold recognition problem. In order to compare against widely used methods in protein sequence analysis, we also test nearest neighbor approaches based on the PSI-BLAST algorithm. Our code weight learning algorithm strongly outperforms these PSI-BLAST methods on every structure recognition problem we consider. 1.
Evaluating machine learning for information extraction
Authors: Neil Ireson, Fabio Ciravegna, Mary Elaine Califf, Dayne Freitag, Nicholas Kushmerick, Alberto Lavelli
Venue: ICML
Year: 2005

Comparative evaluation of Machine Learning (ML) systems used for Information Extraction (IE) has suffered from various inconsistencies in experimental procedures. This paper reports on the results of the Pascal Challenge on Evaluating Machine Learning for Information Extraction, which provides a standardised corpus, set of tasks, and evaluation methodology. The challenge is described and the systems submitted by the ten participants are briefly introduced and their performance is analysed.
A smoothed boosting algorithm using probabilistic output codes
Authors: Rong Jin 0001, Jian Zhang 0003
Venue: ICML
Year: 2005

AdaBoost.OC has shown to be an effective method in boosting "weak" binary classifiers for multi-class learning. It employs the Error Correcting Output Code (ECOC) method to convert a multi-class learning problem into a set of binary classification problems, and applies the AdaBoost algorithm to solve them efficiently. In this paper, we propose a new boosting algorithm that improves the AdaBoost.OC algorithm in two aspects: 1) It introduces a smoothing mechanism into the boosting algorithm to alleviate the potential overfitting problem with the AdaBoost algorithm, and 2) It introduces a probabilistic coding scheme to generate binary codes for multiple classes such that training errors can be efficiently reduced. Empirical studies with seven UCI datasets have indicated that the proposed boosting algorithm is more robust and effective than the AdaBoost.OC algorithm for multi-class learning.
Efficient discriminative learning of Bayesian network classifier via boosted augmented naive Bayes
Authors: Yushi Jing, Vladimir Pavlovic 0001, James M. Rehg
Venue: ICML
Year: 2005

The use of Bayesian networks for classification problems has received significant recent attention. Although computationally efficient, the standard maximum likelihood learning method tends to be suboptimal due to the mismatch between its optimization criteria (data likelihood) and the actual goal for classification (label prediction). Recent approaches to optimizing the classification performance during parameter or structure learning show promise, but lack the favorable computational properties of maximum likelihood learning. In this paper we present the Boosted Augmented Naive Bayes (BAN) classifier. We show that a combination of discriminative data-weighting with generative training of intermediate models can yield a computationally efficient method for discriminative parameter learning and structure selection. 1.
A comparison of tight generalization error bounds
Authors: Matti Kääriäinen, John Langford 0001
Venue: ICML
Year: 2005

We investigate the empirical applicability of several bounds (a number of which are new) on the true error rate of learned classifiers which hold whenever the examples are chosen independently at random from a fixed distribution.The collection of tricks we use includes:1. A technique using unlabeled data for a tight derandomization of randomized bounds.2. A tight form of the progressive validation bound.3. The exact form of the test set bound.The bounds are implemented in the semibound package and are freely available.