Query by Transduction
IEEE Transactions on Pattern Analysis and Machine IntelligencePublished 24 July 2008
Shen-Shyang Ho, Harry Wechsler
Citations57
SJR quartileQ1
SJR score3.91
SNIP5.99
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper proposes Query-by-Transduction (QBT) as a novel active learning algorithm that compares favorably, in terms of mean generalization, against random sampling, committee-based active learning, margin-basedactive learning, and QBC in the stream-based setting.
Abstract
There has been recently a growing interest in the use of transductive inference for learning. We expand here the scope of transductive inference to active learning in a stream-based setting. Towards that end this paper proposes Query-by-Transduction (QBT) as a novel active learning algorithm. QBT queries the label of an example based on the p-values obtained using transduction. We show that QBT is closely related to Query-by-Committee (QBC) using relations between transduction, Bayesian statistical testing, Kullback-Leibler divergence, and Shannon information. The feasibility and utility of QBT is shown on both binary and multi-class classification tasks using SVM as the choice classifier. Our experimental results show that QBT compares favorably, in terms of mean generalization, against random sampling, committee-based active learning, margin-based active learning, and QBC in the stream-based setting.
Keywords
Computer Science
The Nature of Statistical Learning Theory
39,279 Citations1995Vladimir Vapnik
Neural ComputationBackpropagation Applied to Handwritten Zip Code Recognition
11,878 Citations1989Yann LeCun, Bernhard E. Boser +5 more
This paper demonstrates how constraints from the task domain can be integrated into a backpropagation network through the architecture of the network, successfully applied to the recognition of handwritten zip code digits provided by the U.S. Postal Service.
The Nature of Statistical Learning Theory
10,566 Citations2000Vladimir Vapnik
The MIT Press eBooksSemi-Supervised Learning
4,308 Citations2006Olivier Chapelle, Schölkopf, B. +1 more
This first comprehensive overview of semi-supervised learning presents state-of-the-art algorithms, a taxonomy of the field, selected applications, benchmark experiments, and perspectives on ongoing and future research.
Texts in computer scienceAn Introduction to Kolmogorov Complexity and Its Applications
3,734 Citations2019Ming Li, Paul Vitányi
Transductive Inference for Text Classification using Support Vector Machines
2,717 Citations1999Thorsten Joachims
An analysis of why TSVMs are well suited for text classi(cid:12)cation is presented, and an algorithm for training TSVMs e(cid:14)-ciently, handling 10,000 examples and more is proposed.
Query by committee
1,657 Citations1992H. Sebastian Seung, Manfred Opper +1 more
It is suggested that asymptotically finite information gain may be an important characteristic of good query algorithms, in which a committee of students is trained on the same data set.
Support vector machine active learning for image retrieval
1,333 Citations2001Simon Tong, Edward Yi Chang
This work proposes the use of a support vector machine active learning algorithm for conducting effective relevance feedback for image retrieval and achieves significantly higher search accuracy than traditional query refinement schemes after just three to four rounds of relevance feedback.
Machine LearningSoft Margins for AdaBoost
1,306 Citations2001Gunnar Rätsch, Takashi Onoda +1 more
It is found that ADABOOST asymptotically achieves a hard margin distribution, i.e. the algorithm concentrates its resources on a few hard-to-learn patterns that are interestingly very similar to Support Vectors.
Learning from Data: Concepts, Theory, and Methods
1,293 Citations1998Vladimir Cherkassky, Filip Mulier
Journal of Artificial Intelligence ResearchActive Learning with Statistical Models
1,286 Citations1996David Cohn, Zoubin Ghahramani +1 more
This work shows how the same principles may be used to select data for two alternative, statistically-based learning architectures: mixtures of Gaussians and locally weighted regression.
Neural ComputationInformation-Based Objective Functions for Active Data Selection
1,250 Citations1992David Mackay
Within a Bayesian learning framework, objective functions are discussed that measure the expected informativeness of candidate measurements that depend on the assumption that the hypothesis space is correct.
Incremental and Decremental Support Vector Machine Learning
1,158 Citations2000Gert Cauwenberghs, Tomaso Poggio
An on-line recursive algorithm for training support vector machines, one vector at a time, is presented and interpretation of decremental unlearning in feature space sheds light on the relationship between generalization and geometry of the data.
Elsevier eBooksHeterogeneous Uncertainty Sampling for Supervised Learning
1,142 Citations1994David Lewis, Jason Catlett
This work test the use of one classifier (a highly efficient probabilistic one) to select examples for training another (the C4.5 rule induction program) and finds that the uncertainty samples yielded classifiers with lower error rates than random samples ten times larger.
Machine LearningSelective Sampling Using the Query by Committee Algorithm
1,118 Citations1997Yoav Freund, H. Sebastian Seung +2 more
It is shown that if the two-member committee algorithm achieves information gain with positive lower bound, then the prediction error decreases exponentially with the number of queries, and this exponential decrease holds for query learning of perceptrons.
Algorithmic Learning in a Random World
1,049 Citations2005Vladimir Vovk, Glenn Shafer +1 more
Applied Physics Letters10.1162/153244302760185243
898 Citations2000
Experimental results showing that employing the active learning method can significantly reduce the need for labeled training instances in both the standard inductive and transductive settings are presented.
The American StatisticianCalibration of<i>ρ</i>Values for Testing Precise Null Hypotheses
857 Citations2001Thomas Sellke, M. J. Bayarri +1 more
Toward Optimal Active Learning through Sampling Estimation of Error Reduction
824 Citations2001Nicholas Roy, Andrew McCallum
Less is More: Active Learning with Support Vector Machines
775 Citations2000Greg Schohn, David Cohn
A simple active learning heuristic is described which greatly enhances the generalization behavior of support vector machines (SVMs) on several practical document classification tasks and frequently does so in less time than the naive approach of training on all available data.
Employing EM and Pool-Based Active Learning for Text Classification
681 Citations1998Andrew McCallum, Kamal Nigam
The Query-by-Committee method of active learning is modified to use the unlabeled pool for explicitly estimating document density when selecting examples for labeling, and the combination of EM and active learning requires only slightly more than half as many labeled training examples to achieve the same accuracy as either the improved active learning or EM alone.
Elsevier eBooksCommittee-Based Sampling For Training Probabilistic Classifiers
497 Citations1995Ido Dagan, Sean P. Engelson
A general method for efficiently training probabilistic classifiers, by selecting for training only the more informative examples in a stream of unlabeled examples, which is particularly attractive because it evaluates the expected information gain from a training example implicitly.
Proceedings of the ninth ACM international conference on Multimedia - MULTIMEDIA '01Support vector machine active learning for image retrieval
486 Citations2001Simon Tong, Edward Yi Chang
Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions
471 Citations2003Xiaojin Zhu, John Lafferty +1 more
The active learning scheme requires a much smaller number of queries to achieve high accuracy compared with random query selection, and the semi-supervised learning scheme requires a much smaller number of queries to achieve high accuracy compared with random query selection.
Batch mode active learning and its application to medical image classification
424 Citations2006Steven C. H. Hoi, Rong Jin +2 more
A framework for "batch mode active learning" that applies the Fisher information matrix to select a number of informative examples simultaneously and is more effective than the state-of-the-art algorithms for active learning.
Journal of Chemical Information and Computer SciencesActive Learning with Support Vector Machines in the Drug Discovery Process
359 Citations2003Manfred K. Warmuth, Jun Liao +4 more
A thorough comparative study of various other selection strategies on data sets provided by DuPont Pharmaceuticals is performed and it is shown that the strategies based on the maximum margin hyperplane clearly outperform the simpler ones.
Active learning via transductive experimental design
353 Citations2006Kai Yu, Jinbo Bi +1 more
This paper considers the problem of selecting the most informative experiments x to get measurements y for learning a regression model y, and proposes a novel and simple concept for active learning, transductive experimental design, that has a better scalability in comparison with classic experimental design methods.
Query Learning with Large Margin Classifiers
348 Citations2000Colin Campbell, Nello Cristianini +1 more
This paper proposes an algorithm for the training of support vector machines using instance selection, a theoretical justification for the strategy and experimental results on real and artificial data demonstrating its effectiveness.
Diverse ensembles for active learning
328 Citations2004Prem Melville, Raymond J. Mooney
This paper introduces ACTIVE-DECORATE, which uses DECORATE committees to select good training examples and outperforms both Query by Bagging and Query by Boosting.
Machine LearningLetter Recognition Using Holland-Style Adaptive Classifiers
326 Citations1991Peter W. Frey, David J. Slate
This research focused on machine induction techniques for generating IF-THEN classifiers in which the IF part was a list of values for each of the 16 attributes and the THEN part was the correct category, i.e., one of the 26 letters of the alphabet.
Journal of the Royal Statistical Society Series D (The Statistician)Exact Statistical Methods for Data Analysis.
256 Citations1996Vicente Núñez‐Antón, Samaradasa Weerahandi
Large-scale text categorization by batch mode active learning
255 Citations2006Steven C. H. Hoi, Rong Jin +1 more
A novel active learning algorithm that selects a batch of text documents for labeling manually in each iteration and uses the Fisher information matrix as the measurement of model uncertainty and chooses the set of documents to effectively maximize the Fisher Information matrix of a classification model.
Machine LearningLetter recognition using Holland-style adaptive classifiers
255 Citations1991Peter W. Frey, David J. Slate
This research focused on machine induction techniques for generating IF-THEN classifiers in which the IF part was a list of values for each of the 16 attributes and the THEN part was the correct category, i.e., one of the 26 letters of the alphabet.
Springer series in statisticsExact Statistical Methods for Data Analysis
247 Citations1995Samaradasa Weerahandi
IEEE Transactions on Pattern Analysis and Machine IntelligenceConfidence-based active learning
226 Citations2006Mingkun Li, Ishwar K. Sethi
This paper proposes a new active learning approach, confidence-based active learning, based on identifying and annotating uncertain samples, which takes advantage of current classifiers' probability preserving and ordering properties and is robust without additional computational effort.
Lecture notes in computer scienceAnalysis of Perceptron-Based Active Learning
224 Citations2005Sanjoy Dasgupta, Adam Tauman Kalai +1 more
A simple selective sampling algorithm is presented, which combines a modification of the perceptron update with an adaptive filtering rule for deciding which points to query and reaches generalization error e after asking for just O(d log 1/∈) labels.
IEEE Transactions on MultimediaAn active learning framework for content-based information retrieval
204 Citations2002Cha Zhang, Tsuhan Chen
This work proposes a general active learning framework for content-based information retrieval and uses this framework to guide hidden annotations in order to improve the retrieval performance.
Online Choice of Active Learning Algorithms
187 Citations2003Yoram Baram, Ran El‐Yaniv +1 more
Taking an ensemble containing two of the best known active learning algorithms and a new algorithm, the resulting new active learning master algorithm is empirically shown to consistently perform almost as well as and sometimes outperform the best algorithm in the ensemble on a range of classification problems.
Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004.Active learning to recognize multiple types of plankton
184 Citations2004Tong Luo, Kurt Kramer +5 more
The experimental results from a plankton recognition system indicate that the active learning approach to multiple class support vector machines often requires significantly less labeled images to maintain the same accuracy level as random sampling.
IEEE Transactions on Pattern Analysis and Machine IntelligenceOpen set face recognition using transduction
174 Citations2005Fayin Li, Harry Wechsler
Open set TCM-kNN (transduction confidence machine-k nearest neighbors), suitable for multiclass authentication operational scenarios that have to include a rejection option for classes never enrolled in the gallery, is shown to be suitable for PSEI (pattern specific error inhomogeneities) error analysis in order to identify difficult to recognize faces.
Automatically labeling video data using multi-class active learning
159 Citations2003Yan Yan, Jie Yang +1 more
This work proposes a unified multiclass active learning approach for automatically labeling video data and shows that the proposed approach works effectively even with a significantly reduced amount of labeled data.
ePrints Soton (University of Southampton)Machine-Learning Applications of Algorithmic Randomness
156 Citations1999Vladimir Vovk, Alex Gammerman +1 more
Journal of Machine Learning ResearchActive Learning to Recognize Multiple Types of Plankton
153 Citations2005Tong Luo, Kurt Kramer +5 more
Lecture notes in computer scienceTransductive Confidence Machines for Pattern Recognition
145 Citations2002Kostas Proedrou, Ilia Nouretdinov +2 more
A new algorithm for pattern recognition that outputs some measures of "reliability" for every prediction made, in contrast to the current algorithms that output "bare" predictions only.
ePrints Soton (University of Southampton)Transduction with Confidence and Credibility
142 Citations1999Craig Saunders, Alex Gammerman +1 more
A new transductive learning algorithm using Support Vector Machines is described, which provides confidence values for its predicted classifications of new examples and a measure of "credibility" which serves as an indicator of the reliability of the data upon which it makes its prediction.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA probabilistic active support vector learning algorithm
101 Citations2004Pabitra Mitra, C.A. Murthy +1 more
A probabilistic active learning strategy for support vector machine (SVM) design in large data applications that queries for a set of points according to a distribution as determined by the current separating hyperplane and a newly defined concept of an adaptive confidence factor.
Query by Committee Made Real
85 Citations2005Ran Gilad-Bachrach, Amir Navot +1 more
A new algorithm, KQBC, is introduced, capable of actively learning large scale problems by using selective sampling, which overcomes the costly sampling step of the well known Query By Committee (QBC) algorithm by projecting onto a low dimensional space.
Multimodal concept-dependent active learning for image retrieval
81 Citations2004King-Shy Goh, Edward Yi Chang +1 more
This work first characterize a concept's complexity using three measures: hit-rate, isolation and diversity, and proposes a multimodal learning approach that uses images' semantic labels to guide a concept-dependent, active-learning process.
Lecture notes in computer scienceComparing the Bayes and Typicalness Frameworks
79 Citations2001Thomas Melluish, Craig Saunders +2 more
This paper outlines the typicalness framework, which provides confidence information based only on the standard iid assumption and so is much more robust to different underlying data distributions, and shows how the framework can be applied to existing algorithms.
2003 IEEE International Conference on Acoustics, Speech, and Signal Processing, 2003. Proceedings. (ICASSP '03).Active learning for spoken language understanding
70 Citations2003Gökhan Tür, Robert E. Schapire +1 more
These active learning methods for reducing the labeling effort in a statistical call classification system used for AT&T customer care indicate that it is possible to reduce human labeling effort at least by a factor of two.
Lecture notes in computer scienceActive Learning for Probability Estimation Using Jensen-Shannon Divergence
61 Citations2005Prem Melville, Stewart Yang +2 more
Novel approaches to active learning based on the algorithms Bootstrap-LV and ActiveDecorate are introduced, by using Jensen-Shannon divergence (a similarity measure for probability distributions) to improve sample selection for optimizing CPEs.
Theoretical Computer SciencePrediction algorithms and confidence measures based on algorithmic randomness theory
60 Citations2002Alex Gammerman, Volodya Vovk
A new set of machine learning algorithms have been developed that can be used not just to make predictions but also to estimate the confidence under the usual iid assumption of Kolmogorov's algorithmic notion of randomness.
Machine LearningDerandomizing Stochastic Prediction Strategies
49 Citations1999Vladimir Vovk
If the stochastic predictor's total loss is at most L with probability at least p then the learner's loss can be bounded by cL + aln for the usual constants c and a and this interpretation is used to revamp known results and obtain new results on tracking the best expert.
IEEE Transactions on Neural NetworksLearning from labeled and unlabeled data using a minimal number of queries
35 Citations2003Rohit Kothari, Vivek Jain
This work uses a Genetic Algorithm (GA) to iteratively refine the class membership of the unlabeled patterns so that the maximum a posteriori (MAP) based predicted labels of the patterns in the labeled dataset are in agreement with the known labels.
Bayesian Transduction
27 Citations1999Thore Graepel, Ralf Herbrich +1 more
Experimental results on real world data indicate that Bayesian Transduction compares favourably to the well-known Support Vector Machine, in particular if the posterior probability of labellings is used as a confidence measure to exclude test points of low confidence.
Transductive confidence machine for active learning
24 Citations2004Shen-Shyang Ho, Harry Wechsler
The experimental results presented show the feasibility and usefulness of the novel approach using a non-separable two-class classification problem, and the hybrid learning strategy achieves competitive performance against standard nearest neighbor methods using much fewer training examples.
Active Learning For Outdoor Obstacle Detection
21 Citations2005Cristian Dima, Martial Hebert
This paper shows that several standard active learning algorithms can be adapted to meet specific constraints characteristic to their domain, such as the need to learn from data with severely unbalanced class priors, and concludes that active learning techniques are applicable to the authors' domain.
The Kernel Gibbs Sampler
21 Citations2000Thore Graepel, Ralf Herbrich
An algorithm that samples the hypothesis space of kernel classifiers with a uniform prior over normalised weight vectors and a likelihood based on a model of label noise leads to a piecewise constant posterior that can be sampled by the kernel Gibbs sampler (KGS).
Multi-class active learning for video semantic feature extraction
14 Citations2005Rong Yan, Alex Hauptmann
This work presents a multi- class active learning approach which extends active learning from binary classification to multi-class classification using a unified representation with margin-based loss functions and shows that the proposed activeLearning approach works effectively even with a significantly reduced amount of labeled data.
Query expansion with the minimum user feedback by transductive learning
7 Citations2005Masayuki Okabe, Kyoji Umemura +1 more
This paper introduces two refinements to a well-known query expansion technique which performs well even if a user notifies just a relevant document and a non-relevant document and tries to differentiate the importance of candidate terms for expansion in relevant documents.
Habilitation Regulations of the Faculty of Mechanical Engineering (University of Paderborn)Active learning with kernel machines
2 Citations2004Klaus Brinker
Protein classification using transductive learning on phylogenetic profiles
1 Citations2006Roger A. Craig, Li Liao
A novel learning method based on phylogenetic profiles, which takes into account both the phylogenetic tree structure and the likelihood of proteins presence in genomes, and shows that the classification accuracy was greatly increased.