Active learning with kernel machines
Habilitation Regulations of the Faculty of Mechanical Engineering (University of Paderborn)Published 1 January 2004Open access
Klaus Brinker
Citations2
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.
Abstract
Science and Research of the state North Rhine-Westphalia, for establishing a stimulating and supportive environment for research, and
Keywords
Arts and HumanitiesHealth Professions
ACM Transactions on Intelligent Systems and TechnologyLIBSVM
41,340 Citations2011Chih-Chung Chang, Chih‐Jen Lin
Issues such as solving SVM optimization problems theoretical convergence multiclass classification probability estimates and parameter selection are discussed in detail.
Machine LearningSupport-Vector Networks
33,035 Citations1995Corinna Cortes, Vladimir Vapnik
High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated and the performance of the support- vector network is compared to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.
TechnometricsStatistical Learning Theory
26,913 Citations1999Yuhai Wu, Vladimir Vapnik
Presenting a method for determining the necessary and sufficient conditions for consistency of learning process, the author covers function estimates from small data pools, applying these estimations to real-life problems, and much more.
American Mathematical Society eBooksTheory of games and economic behavior
16,943 Citations2019Stephan Ramon Garcia, Steven J. Miller
Data Mining and Knowledge DiscoveryA Tutorial on Support Vector Machines for Pattern Recognition
16,433 Citations1998Christopher J. C. Burges
There are several arguments which support the observed high accuracy of SVMs, which are reviewed and numerous examples and proofs of most of the key theorems are given.
Cambridge University Press eBooksAn Introduction to Support Vector Machines and Other Kernel-based Learning Methods
13,883 Citations2000Nello Cristianini, John Shawe‐Taylor
A training algorithm for optimal margin classifiers
11,594 Citations1992Bernhard E. Boser, Isabelle Guyon +1 more
A training algorithm that maximizes the margin between the training patterns and the decision boundary is presented, applicable to a wide variety of the classification functions, including Perceptrons, polynomials, and Radial Basis Functions.
The MIT Press eBooksLearning with Kernels
9,548 Citations2001Bernhard Schölkopf, Alexander J. Smola
Learning with Kernels provides an introduction to SVMs and related kernel methods that provide all of the concepts necessary to enable a reader equipped with some basic mathematical knowledge to enter the world of machine learning using theoretically well-founded yet easy-to-use kernel algorithms.
Neural ComputationEstimating the Support of a High-Dimensional Distribution
5,946 Citations2001Bernhard Schölkopf, John Platt +3 more
The algorithm is a natural extension of the support vector algorithm to the case of unlabeled data by carrying out sequential optimization over pairs of input patterns and providing a theoretical analysis of the statistical performance of the algorithm.
The MIT Press eBooksFast Training of Support Vector Machines Using Sequential Minimal Optimization
5,462 Citations1998John Platt
Probabilistic Outputs for Support vector Machines and Comparisons to Regularized Likelihood Methods
4,863 Citations1999John Platt
The output of a lassi(cid:12)er should be a alibrated posterior probability to enable post-pro essing and a method to train a kernel lassi with a logit link and a regularized maximum likelihood is proposed.
Technical reportsMaking Large-Scale SVM Learning Practical
4,317 Citations2006Thorsten Joachims
This chapter presents algorithmic and computational results developed for SVM light V 2.0, which make large-scale SVM training more practical and give guidelines for the application of SVMs to large domains.
A theory of the learnable
4,242 Citations1984Leslie G. Valiant
This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.
Optimizing search engines using clickthrough data
3,898 Citations2002Thorsten Joachims
The goal of this paper is to develop a method that utilizes clickthrough data for training, namely the query-log of the search engine in connection with the log of links the users clicked on in the presented ranking.
TechnometricsNonparametrics: Statistical Methods Based on Ranks
3,373 Citations1979Mitchell J. Mergenthaler, E. L. Lehmann
Journal of Artificial Intelligence ResearchSolving Multiclass Learning Problems via Error-Correcting Output Codes
2,718 Citations1995Tom Dietterich, Ghulum Bakiri
It is demonstrated that error-correcting output codes provide a general-purpose method for improving the performance of inductive learning programs on multiclass problems.
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.
TechnometricsMachine Learning, Neural and Statistical Classification
2,188 Citations1995Bill Fulkerson, D. Michie +2 more
Philosophical Transactions of the Royal Society of London Series A Containing Papers of a Mathematical or Physical CharacterXVI. Functions of positive and negative type, and their connection the theory of integral equations
1,980 Citations1909James W. Mercer
On the algorithmic implementation of multiclass kernel-based vector machines
1,790 Citations2002Koby Crammer, Yoram Singer
This paper describes the algorithmic implementation of multiclass kernel-based vector machines using a generalized notion of the margin to multiclass problems, and describes an efficient fixed-point algorithm for solving the reduced optimization problems and proves its convergence.
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.
Large Margin DAGs for Multiclass Classification
1,644 Citations1999John Platt, Nello Cristianini +1 more
An algorithm, DAGSVM, is presented, which operates in a kernel-induced feature space and uses two-class maximal margin hyperplanes at each decision-node of the DDAG, which is substantially faster to train and evaluate than either the standard algorithm or Max Wins, while maintaining comparable accuracy to both of these algorithms.
Machine LearningQueries and Concept Learning
1,622 Citations1988Dana Angluin
This work considers the problem of using queries to learn an unknown concept, and several types of queries are described and studied: membership, equivalence, subset, superset, disjointness, and exhaustiveness queries.
Lecture notes in computer scienceA Generalized Representer Theorem
1,587 Citations2001Bernhard Schölkopf, Ralf Herbrich +1 more
The result shows that a wide range of problems have optimal solutions that live in the finite dimensional span of the training examples mapped into feature space, thus enabling us to carry out kernel algorithms independent of the (potentially infinite) dimensionality of the feature space.
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 LearningImproving Generalization with Active Learning
1,311 Citations1994David Cohn, Les Atlas +1 more
A formalism for active concept learning called selective sampling is described and it is shown how it may be approximately implemented by a neural network.
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.
Bioinformatics the machine learning approach
929 Citations1998Pierre Baldi, Søren Brunak
DSpace@MIT (Massachusetts Institute of Technology)A family of algorithms for approximate bayesian inference
902 Citations2001Thomas P. Minka, Rosalind W. Picard
This thesis presents an approximation technique that can perform Bayesian inference faster and more accurately than previously possible, and is found to be convincingly better than rival approximation techniques: Monte Carlo, Laplace's method, and variational Bayes.
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.
NeurocomputingSingle-layer learning revisited: a stepwise procedure for building and training a neural network
825 Citations1990S. Knerr, L. Personnaz +1 more
A stepwise procedure for building and training a neural network intended to perform classification tasks, based on single layer learning rules, is presented, which breaks up the classification task into subtasks of increasing complexity in order to make learning easier.
Toward Optimal Active Learning through Sampling Estimation of Error Reduction
824 Citations2001Nicholas Roy, Andrew McCallum
The European Symposium on Artificial Neural NetworksSupport vector machines for multi-class pattern recognition.
794 Citations1999Jason Weston, Chris Watkins
A formulation of the SVM is proposed that enables a multi-class pattern recognition problem to be solved in a single optimisation and a similar generalization of linear programming machines is proposed.
Semi-Supervised Support Vector Machines
793 Citations1998Kristin P. Bennett, Ayhan Demiriz
A general S3VM model is proposed that minimizes both the misclassification error and the function capacity based on all the available data that can be converted to a mixed-integer program and then solved exactly using integer programming.
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.
Journal of the ACMA random polynomial-time algorithm for approximating the volume of convex bodies
701 Citations1991Martin Dyer, Alan Frieze +1 more
The proof of correctness of the algorithm relies on recent theory of rapidly mixing Markov chains and isoperimetric inequalities to show that a certain random walk can be used to sample nearly uniformly from within K within Euclidean space.
Bayesian methods for adaptive models
629 Citations1992David Mackay
The Bayesian framework for model comparison and regularisation is demonstrated by studying interpolation and classification problems modelled with both linear and non-linear models, and it is shown that the careful incorporation of error bar information into a classifier's predictions yields improved performance.
The MIT Press eBooksPranking with Ranking
550 Citations2002Koby Crammer, Yoram Singer
A simple and efficient online algorithm is described, its performance in the mistake bound model is analyzed, its correctness is proved, and it outperforms online algorithms for regression and classification applied to ranking.
Applied Physics Letters10.1162/15324430152733133
506 Citations2000
A general method for combining the classifiers generated on the binary problems is proposed, and a general empirical multiclass loss bound is proved given the empirical loss of the individual binary learning algorithms.
Encyclopedia of Machine Learning and Data MiningLearning from Labeled and Unlabeled Data
469 Citations2017Claude Sammut, Geoffrey I. Webb
Incorporating diversity in active learning with support vector machines
452 Citations2003Klaus Brinker
This work presents a new approach that is especially designed to construct batches and incorporates a diversity measure that has low computational requirements making it feasible for large scale problems with several thousands of examples.
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.
Communications of the ACMIntroduction: personalized views of personalization
348 Citations2000Doug Riecken
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.
Machine LearningA Simple Decomposition Method for Support Vector Machines
300 Citations2002Chih‐Wei Hsu, Chih‐Jen Lin
This paper through the design of decomposition methods for bound-constrained SVM formulations it is demonstrated that the working set selection is not a trivial task and a simple selection is proposed which leads to faster convergences for difficult cases.
Random Structures and AlgorithmsRandom walks and anO*(n5) volume algorithm for convex bodies
293 Citations1997Ravi Kannan, L�szl� Lov�sz +1 more
This algorithm introduces three new ideas: the use of the isotropic position (or at least an approximation of it) for rounding; the separation of global obstructions and local obstructions for fast mixing; and a stepwise interlacing of rounding and sampling.
Active + Semi-supervised Learning = Robust Multi-View Learning
288 Citations2002Ion Muslea, Steven Minton +1 more
A new multi-view algorithm, Co-EMT, which combines semi-supervised and active learning is introduced, which outperforms the other algorithms both on the parameterized problems and on two additional real world domains.
European Journal of Operational ResearchDecision-theoretic foundations of qualitative possibility theory
260 Citations2001Didier Dubois, Henri Prade +1 more
A justification of two qualitative counterparts of the expected utility criterion for decision under uncertainty, which only require bounded, linearly ordered, valuation sets for expressing uncertainty and preferences, and proposes an operationally testable description of possibility theory.
Journal of Computer and System SciencesSimulated annealing in convex bodies and an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msup><mml:mrow><mml:mi>O</mml:mi></mml:mrow><mml:mrow><mml:mo>*</mml:mo></mml:mrow></mml:msup><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mrow><mml:mi>n</mml:mi></mml:mrow><mml:mrow><mml:mn>4</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> volume algorithm
250 Citations2005László Lovász, Santosh Vempala
A new algorithm for computing the volume of a convex body in R^n is presented, improving on the previous best algorithm by a factor of n and using a ''morphing'' technique that can be viewed as a variant of simulated annealing.
Multi-criteria-based active learning for named entity recognition
233 Citations2004Dan Shen, Jie Zhang +3 more
A multi-criteria-based active learning approach is proposed and effectively applied to named entity recognition and includes all the criteria using two selection strategies, both of which result in less labeling cost than single-criterion-based method.
Lecture notes in computer sciencePairwise Preference Learning and Ranking
226 Citations2003Johannes Fürnkranz, Eyke Hüllermeier
The main objective of this work is to investigate the trade-off between the quality of the induced ranking function and the computational complexity of the algorithm, both depending on the amount of preference information given for each example.
Optimization methods & softwareSemi-superyised support vector machines for unlabeled data classification
204 Citations2001Glenn Fung, O. L. Mangasarian
The Faculty Digital Archive (New York University)Active Sampling for Class Probability Estimation and Ranking
192 Citations2004Foster Provost, Maytal Saar‐Tsechansky
Active learning for structure in Bayesian networks
186 Citations2001Simon Tong, Daphne Koller
Experimental results show that active learning can substantially reduce the number of observations required to determine the structure of a domain.
Lecture notes in computer scienceConstraint Classification: A New Approach to Multiclass Classification
176 Citations2002Sariel Har-Peled, Dan Roth +1 more
A new view of multiclass classification is presented and the constraint classification problem is introduced, a generalization that captures many flavors of multiclass classification and provides the first optimal, distribution independent bounds for many multiclass learning algorithms, including winner-take-all (WTA).
IEEE Transactions on Neural NetworksNeural net algorithms that learn in polynomial time from examples and queries
169 Citations1991Eric B. Baum
The author's algorithm is proved to PAC learn in polynomial time the class of target functions defined by layered, depth two, threshold nets having n inputs connected to k hidden threshold units connected to one or more output units, provided k=/<4.
Knowledge-Based Support Vector Machine Classifiers
156 Citations2002Glenn Fung, O. L. Mangasarian +1 more
Numerical results show improvement in test set accuracy after the incorporation of prior knowledge into ordinary, data-based linear support vector machine classifiers, and one experiment shows that a linear classifier, based solely on prior knowledge, far outperforms the direct application of priorknowledge rules to classify data.
Journal of Artificial Intelligence ResearchCommittee-Based Sample Selection for Probabilistic Classifiers
150 Citations1999Shlomo Argamon-Engelson, Ido Dagan
A family of empirical methods for committee-based sample selection in probabilistic classification models, which evaluate the informativeness of an example by measuring the degree of disagreement between several model variants, are described.
Active Learning with Committees for Text Categorization
143 Citations1997Ray Liere, Prasad Tadepalli
This paper reports on experiments using a committee of Winnowbased learners and demonstrates that this approach can reduce the number of labeled training examples required over that used by a single Winnow learner by l-2 orders of magnitude.
Active Learning for Parameter Estimation in Bayesian Networks
134 Citations2000Simon Tong, Daphne Koller
This paper provides a theoretical framework for this problem, and an algorithm that chooses which active learning queries to generate based on the model learned so far, and presents experimental results showing that the active learning algorithm can significantly reduce the need for training data in many situations.
Discrete & Computational GeometryA geometric inequality and the complexity of computing volume
117 Citations1986Gy. Elekes
The volume of the convex hull of anym points of ann-dimensional ball with volumeV is at mostV·m/2n, which implies that no polynomial time algorithm can compute the volume of a convex set given by an oracle with less than exponential relative error.
Lecture notes in computer scienceMachine learning for adaptive user interfaces
108 Citations1997Pat Langley
This paper examines the growing interest in personalized user interfaces and explores the potential of machine learning in meeting that need, and considers some examples of adaptive interfaces that use inductive methods to personalize their behavior.
Applied Physics Letters10.1162/153244301753683717
107 Citations2000
It is found that Bayes point machines consistently outperform support vector machines on both surrogate data and real-world benchmark data sets and it is demonstrated that the real-valued output of single Bayes points on novel test points is a valid confidence measure and leads to a steady decrease in generalisation error when used as a rejection criterion.
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.
Constraint Classification: A New Approach to Multiclass Classification and Ranking
67 Citations2002Sariel Har-Peled, Dan Roth +1 more
Constraint classification is introduced, a framework capturing many flavors of multiclass classification including multilabel classification and ranking, and a meta-algorithm for learning in this framework is presented.
Further results on the margin distribution
64 Citations1999John Shawe‐Taylor, Nello Cristianini
It is shown that in the linear case the approach can be viewed as a change of kernel and that the algorithms arising from the approach are exactly those originally proposed by Cortes and Vapnik.
Active Learning in the Drug Discovery Process
64 Citations2001Manfred K. Warmuth, Gunnar Rätsch +3 more
This work investigates the following data mining problem from Computational Chemistry: From a large data set of compounds, find those that bind to a target molecule in as few iterations of biological testing as possible.
IEEE Transactions on Information TheoryA PAC-Bayesian margin bound for linear classifiers
44 Citations2002Ralf Herbrich, Thore Graepel
A bound on the generalization error of linear classifiers in terms of a refined margin quantity on the training sample is presented and it is shown that the classical margin is too coarse a measure for the essential quantity that controls the generalization error: the fraction of hypothesis space consistent with the training sample.
Active learning of label ranking functions
41 Citations2004Klaus Brinker
This work introduces a novel generalization of pool-based active learning to address the problem of labeled sets of examples in supervised learning.
On the sample complexity of pac-learning using random and chosen examples
41 Citations1990Bonnie Eisenberg, Ronald L. Rivest
Theoretical Computer ScienceQuery by committee, linear separation and random walks
36 Citations2002Shai Fine, Ran Gilad-Bachrach +1 more
A connection between random walks and certain Machine Learning notions such as e-net and support vector machines is exhibited and a useful geometric lemma which bounds the maximal radius of a ball contained in a convex body is drawn.
Comparison of Ranking Procedures in Pairwise Preference Learning
32 Citations2004Eyke Hüllermeier, Johannes Fürnkranz
A method for learning valued preference structures, using a natural extension of so-called pairwise classification, which can be used in order to induce a ranking, that is a linear ordering of a given set of alternatives.
Efficient Learning of Linear Perceptrons
31 Citations2000Shai Ben-David, Hans Ulrich Simon
It is proved that unless P=NP, there is no algorithm that runs in time polynomial in the sample size and in 1/µ that is µ-margin successful for all µ > 0.
Anytime Interval-Valued Outputs for Kernel Machines: Fast Support Vector Machine Classification via Distance Geometry
27 Citations2002Dennis DeCoste
A computational geometry method for which classification cost becomes roughly proportional to the difficulty of each example is introduced.
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.
Solving convex programs by random walks
21 Citations2002Dimitris Bertsimas, Santosh Vempala
A simple new algorithm for convex optimization based on sampling by a random walk is presented, which solves for a natural generalization of the problem.
Ranking by pairwise comparison a note on risk minimization
20 Citations2005Eyke Hüllermeier, Johannes Fürnkranz
A potential application of the ranking by pairwise comparison method in (qualitative) fuzzy classification is outlined by outlining a potential application and identifying some extensions necessary in this context.
The MIT Press eBooksComputing the Bayes Kernel Classifier
16 Citations2000P. Ruján, Mario Marchand
This chapter contains sections titled: Introduction, A Simple Geometric Problem, The Maximal Margin Perceptron, The Bayes Perceptrons, The Kernel-Billiard, Numerical Tests, Conclusions, Appendix.
Large Scale Bayes Point Machines
16 Citations2000Ralf Herbrich, Thore Graepel
Experimental results on the MNIST data set of handwritten digits are presented which show that Bayes point machines (BPMs) are competitive with the current world champion, the support vector machine.
Applied Physics Letters10.1162/153244304773633843
14 Citations2000
An approach to elicitation of user preference models in which assumptions can be used to guide but not constrain the elicitation process is presented, demonstrating that when domain knowledge is available, even in the form of weak and somewhat inaccurate assumptions, significantly less data is required to build an accurate model of user preferences when no domain knowledge is provided.
Active Learning with Model Selection — Simultaneous Optimization of Sample Points and Models for Trigonometric Polynomial Models
9 Citations2003Masashi Sugiyama, Hidemitsu Ogawa
It is shown that the dilemma can be dissolved if there is a set of sample points that is optimal for all models in consideration, and a practical procedure is given for active learning with model selection in trigonometric polynomial models.
Lecture notes in computer scienceBayes and Tukey Meet at the Center Point
7 Citations2004Ran Gilad-Bachrach, Amir Navot +1 more
It is shown that when learning linear classifiers, the Bayes Point is almost identical to the Tukey Median and Center Point, and a bound on the generalization error for Bayes point Machines is proved, independent of the input dimension and length of training.
Local search in smooth convex sets
3 Citations2002Ramachandran Kannan, Andreas Nolte
A simple notation of smoothness of convex sets is defined and two very simple techniques to minimize a linear function over a convex set are analysed, showing that both algorithms provide a near optimal solution for smooth conveX sets in polynomial time.
European Conference on Artificial IntelligenceOn multiclass active learning with support vector machines
3 Citations2004Klaus Brinker
This work considers three common decomposition methods to express multiclass problems in terms of sets of binary classification problems and proposes novel active learning heuristics in order to reduce the labeling effort.
…