nils-herrmann/clean_scirepeval huggingface dataset:
Learning Kernel Classifiers - Theory and Algorithms

From the Publisher: 
Linear classifiers in kernel spaces have emerged as a major topic within the field of machine learning. The kernel technique takes the linear classifier--a limited, but well-established and comprehensively studied model--and extends its applicability to a wide range of nonlinear pattern-recognition tasks such as natural language processing, machine vision, and biological sequence analysis. This book provides the first comprehensive overview of both the theory and algorithms of kernel classifiers, including the most recent developments. It begins by describing the major algorithmic advances: kernel perceptron learning, kernel Fisher discriminants, support vector machines, relevance vector machines, Gaussian processes, and Bayes point machines. Then follows a detailed introduction to learning theory, including VC and PAC-Bayesian theory, data-dependent structural risk minimization, and compression bounds. Throughout, the book emphasizes the interaction between theory and algorithms: how learning algorithms work and why. The book includes many examples, complete pseudo code of the algorithms presented, and an extensive source code library.
Microsoft Cambridge at TREC 2002: Filtering Track

Six runs were submitted for the Adaptive Filtering track, four on the adaptive filtering task (ok11af??), and two on the routing task (msPUM?). The adaptive filtering system has been somewhat modified from the one used for TREC–10, largely for efficiency and flexibility reasons; the basic filtering algorithms remain similar to those used in recent TRECs. For the routing task, a completely new system based on perceptrons with uneven margins was used.
Average Precision and the Problem of Generalisation

In this paper we study the problem of generalisation in information retrieval. In particular we study precision-recall curves and the average precision value. We provide two types of bounds: large-deviation bounds of the average precision and maximum deviation bounds with respect to a given point of the precision recall curve. The rst type of bounds are useful to answer the question: how far can true average precision be from the value observed on a test collection? The second is useful for obtaining bounds on average precision when tight bounds on a particular point of the curve can be established, as is the case when training SVMs or Perceptrons for document categorisation.
Fast Sparse Gaussian Process Methods: The Informative Vector Machine

We present a framework for sparse Gaussian process (GP) methods which uses forward selection with criteria based on information-theoretic principles, previously suggested for active learning. Our goal is not only to learn d-sparse predictors (which can be evaluated in O(d) rather than O(n), d ≪ n, n the number of training points), but also to perform training under strong restrictions on time and memory requirements. The scaling of our method is at most O(n · d2), and in large real-world classification experiments we show that it can match prediction performance of the popular support vector machine (SVM), yet can be significantly faster in training. In contrast to the SVM, our approximation produces estimates of predictive probabilities ('error bars'), allows for Bayesian model selection and is less complex in implementation.
Learning on Graphs in the Game of Go

We consider the game of Go from the point of view of machine learning and as a well-defined domain for learning on graph representations. We discuss the representation of both board positions and candidate moves and introduce the common fate graph (CFG) as an adequate representation of board positions for learning. Single candidate moves are represented as feature vectors with features given by subgraphs relative to the given move in the CFG. Using this representation we train a support vector machine (SVM) and a kernel perceptron to discriminate good moves from bad moves on a collection of life-and-death problems and on 9 × 9 game records. We thus obtain kernel machines that solve Go problems and play 9 × 9 Go.
A Sparse B ayesian Compression Scheme — The Informative Vector Machine

Kernel based learning algorithms allow the mapping of dataset into an infinite dimensional feature space in which a classification may be perform ed. As such kernel methods represent a powerful approach to the solution of many non-li near problems. However kernel methods do suffer from one unfortunate drawback, the Gra m matrix containsm rows and columns wherem is the number of data-points. Many operations are precluded (e.g. matrix inverseO(m3)) when data-sets containing more than about 104 points are encountered. One approach to resolving these issues is to look for s parse representations of the data-set [7, 5, 2]. A sparse representation contains a reduc ed number of examples. Loosely speaking we are interested in extracting the maximu m amount of information from the minimum number of data-points. To achieve this in a p rincipled manner we are interested in estimating the amount of information each data-point contains. In the framework presented here we make use of the Bayesian methodo logy t determine how much information is gained from each data-point.
Bayes Point Machines

Kernel-classifiers comprise a powerful class of non-linear decision functions for binary classification. The support vector machine is an example of a learning algorithm for kernel classifiers that singles out the consistent classifier with the largest margin, i.e. minimal real-valued output on the training sample, within the set of consistent hypotheses, the so-called version space. We suggest the Bayes point machine as a well-founded improvement which approximates the Bayes-optimal decision by the centre of mass of version space. We present two algorithms to stochastically approximate the centre of mass of version space: a billiard sampling algorithm and a sampling algorithm based on the well known perceptron algorithm. It is shown how both algorithms can be extended to allow for soft-boundaries in order to admit training errors. Experimentally, we find that - for the zero training error case - Bayes point machines consistently outperform support vector machines on both surrogate data and real-world benchmark data sets. In the soft-boundary/soft-margin case, the improvement over support vector machines is shown to be reduced. Finally, we demonstrate 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.
Proofs and Derivations—Part II

This chapter contains sections titled: C.1 VC and PAC Generalization Error Bounds, C.2 Bound on the Growth Function, C.3 Luckiness Bound, C.4 Empirical VC Dimension Luckiness, C.5 Bound on the Fat Shattering Dimension, C.6 Margin Distribution Bound, C.7 The Quantifier Reversal Lemma, C.8 A PAC-Bayesian Marin Bound, C.9 Algorithmic Stability Bounds
List of Symbols

Linear classifiers in kernel spaces have emerged as a major topic within the field of machine learning. The kernel technique takes the linear classifier--a limited, but well-established and comprehensively studied model--and extends its applicability to a wide range of nonlinear pattern-recognition tasks such as natural language processing, machine vision, and biological sequence analysis. This book provides the first comprehensive overview of both the theory and algorithms of kernel classifiers, including the most recent developments. It begins by describing the major algorithmic advances: kernel perceptron learning, kernel Fisher discriminants, support vector machines, relevance vector machines, Gaussian processes, and Bayes point machines. Then follows a detailed introduction to learning theory, including VC and PAC-Bayesian theory, data-dependent structural risk minimization, and compression bounds. Throughout, the book emphasizes the interaction between theory and algorithms: how learning algorithms work and why. The book includes many examples, complete pseudo code of the algorithms presented, and an extensive source code library.
A PAC-Bayesian margin bound for linear classifiers

We present a bound on the generalisation error of linear classifiers in terms of a refined margin quantity on the training set. The result is obtained in a PAC-Bayesian framework and is based on geometrical arguments in the space of linear classifiers. The new bound constitutes an exponential improvement of the so far tightest margin bound by Shawe-Taylor et al.  and scales logarithmically in the inverse margin. Even in the case of less training examples than input dimensions sufficiently large margins lead to non-trivial bound values and - for maximum margins - to a vanishing complexity term. Furthermore, the classical margin is too coarse a measure for the essential quantity that controls the generalisation error: the volume ratio between the whole hypothesis space and the subset of consistent hypotheses. The practical relevance of the result lies in the fact that the well-known support vector machine is optimal w.r.t. the new bound only if the feature vectors are all of the same length. As a consequence we recommend to use SVMs on normalised feature vectors only - a recommendation that is well supported by our numerical experiments on two benchmark data sets.
Large Scale Bayes Point Machines

The concept of averaging over classifiers is fundamental to the Bayesian analysis of learning. Based on this viewpoint, it has recently been demonstrated for linear classifiers that the centre of mass of version space (the set of all classifiers consistent with the training set) - also known as the Bayes point - exhibits excellent generalisation abilities. However, the billiard algorithm as presented in  is restricted to small sample size because it requires O(m2) of memory and O(N ċ m2) computational steps where m is the number of training patterns and N is the number of random draws from the posterior distribution. In this paper we present a method based on the simple perceptron learning algorithm which allows to overcome this algorithmic drawback. The method is algorithmically simple and is easily extended to the multi-class case. We present experimental results on the MNIST data set of handwritten digits which show that Bayes point machines (BPMs) are competitive with the current world champion, the support vector machine. In addition, the computational complexity of BPMs can be tuned by varying the number of samples from the posterior. Finally, rejecting test points on the basis of their (approximative) posterior probability leads to a rapid decrease in generalisation error, e.g. 0.1% generalisation error for a given rejection rate of 10%.
Robust Bayes Point Machines

Support V ectorMachines choose the hypothesis corresponding to the centre of the largest hypersphere that can be inscribed in version space. If version space is elongated or irregularly shaped a potentially superior approach is take into account the whole of version space. We propose to construct the Bayes point whic h is approximated by the centre of mass. Our implementation of a Bayes Point Machine (BPM) uses an ergodic billiard to estimate this point in the k ernel space. We show that BPMs outperform hard margin Support Vector Machines (SVMs) on real world datasets. We introduce a technique that allows the BPM to construct hypotheses with non{zero training error similar to soft margin SVMs with quadratic penelisation of the margin slacks. An experimental study reveals that with decreasing penelisation of training error the improvement of BPMs over SVMs decays, a nding that is explained by geometrical considerations.
A PAC-Bayesian study of linear classifiers: why SVMs work

In this paper we present a bound on the generalisation error of linear classi ers in terms of a re ned margin quantity on the training set. The result is obtained by a fundamentally di erent reasoning than in the classical PAC framework. We show that the generalisation error of a classi er can be bounded purely by geometrical arguments. In contrast to the classical results our bound does not contain awkward constants (see, e.g. [10, p. xxi]) and is an exponential improvement of the result in  by scaling inverse logarithmically in the margin. In the form presented the result is an improvement of a result in . A much more rigorous analysis shows that even in the case of having less examples than input dimensions we can bene t from large margins. Furthermore it is shown that the margins is too coarse a measure for the real quantity controlling the generalisation error: the volume of the consistent classi ers to the volume of the whole hypothesis space. In case of ellipsoidal shapes of the input space the minimal real valued output on the training set (margin) is largely a ected by a few points on the longest principal axis. Instead of considering the eigenvalue spectrum of the Gram matrix (see, e.g. [7]) we show that a simple rescaling of the single margins at each training point su ces to compensate the e ect of kernels. An appealing feature of our bound is that the capacity term vanishes for maximally large margins independent on the number of training examples. This will never be the case in classical PAC bounds.
The Kernel Gibbs Sampler

We present an algorithm that samples the hypothesis space of kernel classifiers. Given 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). The KGS is a Markov Chain Monte Carlo method that chooses a random direction in parameter space and samples from the resulting piecewise constant density along the line chosen. The KGS can be used as an analytical tool for the exploration of Bayesian transduction, Bayes point machines, active learning, and evidence-based model selection on small data sets that are contaminated with label noise. For a simple toy example we demonstrate experimentally how a Bayes point machine based on the KGS outperforms an SVM that is incapable of taking into account label noise.
Regression Models for Ordinal Data: A Machine Learning Approach

In contrast to the standard machine learning tasks of classi fication and metric regression we investigate the problem of predicting var iables of ordinal scale, a setting referred to as ordinal regression. The task of ordinal regression arises frequently in the social sciences and in information retrie val where human preferences play a major role. Also many multi–class problems ar e really problems of ordinal regression due to an ordering of the classes. Alth oug the problem is rather novel to the Machine Learning Community it has been wi dely considered in Statistics before. All the statistical methods rely on a p robability model of a latent (unobserved) variable and on the condition of st chastic ordering . In this paper we develop a distribution independent formulation of the problem and give uniform bounds for our risk functional. The main difference to classification is the restriction that the mapping of objects to ranks must be tran sitive and asymmetric. Combining our theoretical framework with results from measurement theory we present an approach that is based on a mapping from objects to scalar utility values and thus guarantees transitivity and asymmetry. App lying the principle of Structural Risk Minimization as employed in Support Vector Machines we derive a new learning algorithm based on large margin rank boundari es for the task of ordinal regression. Our method is easily extended to nonlinea r utility functions. We give experimental results for an Information Retrieval tas k of learning the order of documents with respect to an initial query. Moreover, we sho w that our algorithm outperforms more naive approaches to ordinal regression su ch as Support Vector Classification and Support Vector Regression in the case of m ore than two ranks . 1This paper is a preliminary version of (Herbrich et al. 1999)
Bayes Point Machines: Estimating the Bayes Point in Kernel Space

From a Bayesian perspective Support Vector Machines choose the hypothesis corresponding to the largest possible hypersphere that can be inscribed in version space, i.e. in the space of all consistent hypotheses given a training set. Those boundaries of version space which are tangent to the hypersphere define the support vectors. An alternative and potentially better approach is to construct the hypothesis using the whole of version space. This is achieved by using a Bayes Point Machine which finds the midpoint of the region of intersection of all hyperplanes bisecting version space into two halves of equal volume (the Bayes point). It is known that the center of mass of version space approximates the Bayes point [Watkin, 1993]. We suggest estimating the center of mass by averaging over the trajectory of a billiard ball bouncing in version space. Experimental results are presented indicating that Bayes Point Machines consistently outperform Support Vector Machines.
Using unlabeled data for supervised learning

4-(3-Nitrophenyl)pyridine, an intermediate useful in the preparation of 1-(lower-alkyl)-1,4-dihydro-4-oxo-7-(4-pyridyl)-3-quinolinecarboxylates, which are useful as antibacterial agents, is prepared by reacting 3-nitrobenzaldehyde with two molar equivalents of di-(lower-alkyl) oxalacetate (II) in the presence of a catalytic condensing agent, preferably piperidine and/or its acetate, to produce tetra-(lower-alkyl) 3-(3-nitrophenyl)-1,5-pentanedione-1,2,4,5-tetracarboxylate (III), reacting III with ammonia to produce tetra-(lower-alkyl) 1,4-dihydro-4-(3-nitrophenyl)-2,3,5,6-pyridinetetracarboxylate (IV), oxidizing IV to produce tetra-(lower-alkyl) 4-(3-nitrophenyl)-2,3,5,6-pyridinetetracarboxylate (V), hydrolyzing V to produce 4-(3-nitrophenyl)-2,3,5,6-pyridinetetracarboxylic acid (VI) and decarboxylating VI to produce 4-(3-nitrophenyl)pyridine (VI). Intermediates III, IV, V and VI are novel.
Neural Networks in Economics

Neural Networks – originally inspired from Neuroscience – provide powerful models for statistical data analysis. Their most prominent feature is their ability to “learn” dependencies based on a finite number of observations. In the context of Neural Networks the term “learning” means that the knowledge acquired from the samples can be generalized to as yet unseen observations. In this sense, a Neural Network is often called a Learning Machine. As such, Neural Networks might be considered as a metaphor for an agent who learns dependencies of his environment and thus infers strategies of behavior based on a limited number of observations. In this contribution, however, we want to abstract from the biological origins of Neural Networks and rather present them as a purely mathematical model.
Bayesian Learning in Reproducing Kernel Hilbert Spaces

Support Vector Machines nd the hypothesis that corresponds to the centre of the largest hypersphere that can be placed inside version space, i.e. the space of all consistent hypotheses given a training set. The boundaries of version space touched by this hypersphere de ne the support vectors. An even more promising approach is to construct the hypothesis using the whole of version space. This is achieved by the Bayes point: the midpoint of the region of intersection of all hyperplanes bisecting version space into two volumes of equal magnitude. It is known that the centre of mass of version space approximates the Bayes point [30]. The centre of mass is estimated by averaging over the trajectory of a billiard in version space. We derive bounds on the generalisation error of Bayesian classi ers in terms of the volume ratio of version space and parameter space. This ratio serves as an e ective VC dimension and greatly in uences generalisation. We present experimental results indicating that Bayes Point Machines consistently outperform Support Vector Machines. Moreover, we show theoretically and experimentally how Bayes Point Machines can easily be extended to admit training errors.
Support vector learning for ordinal regression

We investigate the problem of predicting variables of ordinal scale. This task is referred to as ordinal regression and is complementary to the standard machine learning tasks of classification and metric regression. In contrast to statistical models we present a distribution independent formulation of the problem together with uniform bounds of the risk functional. The approach presented is based on a mapping from objects to scalar utility values. Similar to support vector methods we derive a new learning algorithm for the task of ordinal regression based on large margin rank boundaries. We give experimental results for an information retrieval task: learning the order of documents with respect to an initial query. Experimental results indicate that the presented algorithm outperforms more naive approaches to ordinal regression such as support vector classification and support vector regression in the case of more than two ranks.
Bayesian Transduction

Transduction is an inference principle that takes a training sample and aims at estimating the values of a function at given points contained in the so-called working sample as opposed to the whole of input space for induction. Transduction provides a confidence measure on single predictions rather than classifiers - a feature particularly important for risk-sensitive applications. The possibly infinite number of functions is reduced to a finite number of equivalence classes on the working sample. A rigorous Bayesian analysis reveals that for standard classification loss we cannot benefit from considering more than one test point at a time. The probability of the label of a given test point is determined as the posterior measure of the corresponding subset of hypothesis space. We consider the PAC setting of binary classification by linear discriminant functions (perceptrons) in kernel space such that the probability of labels is determined by the volume ratio in version space. We suggest to sample this region by an ergodic billiard. 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.
Generation of task-specific segmentation procedures as a model selection task

In image segmentation problems, there is usually a vast amount of filter operations available, a subset of which has to be selected and instantiated in order to obtain a satisfactory segmentation procedure fo r a particular domain. In supervised segmentation, a mapping from features, such as filter outputs for individual pixels, to classes is induced automa tically. However, since the sample size required for supervised learning grow s exponentially in the number of features it is not feasible to learn a segment ation procedure from a large amount of possible filters. But we argue that auto matic model selection methods are able to select a region model in terms of some filters.