nils-herrmann/clean_scirepeval huggingface dataset:
Multiclass and Multiview Learning at One-class Complexity

We introduce a maximum margin framework realizing a regression type learning in an arbitrary Hilbert space whilst the corresponding dual problem preserving the structure and, therefore, the complexity that of the binary Support Vector Machine(SVM). We demonstrate via some examples this learning framework is broadly applicable in several seemingly different problems. One example is the multiclass classification problem which, in this way, can be implemented with the complexity of a binary SVM. The reduction of the complexity does not involve diminishing performance but, in some cases this approach can improve the classification accuracy. The multiclass classification is realized where the output labels are vector valued. Other examples implement multiview learning problems.
An Investigation of Feature Models for Music Genre Classification Using the Support Vector Classifier

In music genre classification the decision time is typically of the order of several seconds, however, most automatic music genre classification systems focus on short time features derived from 10 50ms. This work investigates two models, the multivariate Gaussian modeland the multivariate autoregressive modelfor modelling short time features. Furthermore, it was investigated how these models can be integrated over a segment of short time features into a kernel such that a support vector machine can be applied. Two kernels with this property were considered, the convolution kernel and product probability kernel. In order to examine the different methods an 11 genre music setup was utilized. In this setup the Mel Frequency Cepstral Coefficients were used as short time features. The accuracy of the best performing model on this data set was � 44% compared to a human performance of � 52% on the same data set.
Two view learning: SVM-2K, Theory and Practice

Kernel methods make it relatively easy to define complex high-dimensional feature spaces. This raises the question of how we can identify the relevant subspaces for a particular learning task. When two views of the same phenomenon are available kernel Canonical Correlation Analysis (KCCA) has been shown to be an effective preprocessing step that can improve the performance of classification algorithms such as the Support Vector Machine (SVM). This paper takes this observation to its logical conclusion and proposes a method that combines this two stage learning (KCCA followed by SVM) into a single optimisation termed SVM-2K. We present both experimental and theoretical analysis of the approach showing encouraging results and insights.
Analysis of Generic Perceptron-Like Large Margin Classifiers

We analyse perceptron-like algorithms with margin considering both the standard classification condition and a modified one which demands a specific value of the margin in the augmented space. The new algorithms are shown to converge in a finite number of steps and used to approximately locate the optimal weight vector in the augmented space. As the data are embedded in the augmented space at a larger distance from the origin the maximum margin in that space approaches the maximum geometric one in the original space. Thus, our procedures exploiting the new algorithms can be regarded as approximate maximal margin classifiers.
Mixture of Vector Experts

We describe and analyze an algorithm for predicting a sequence of n-dimensional binary vectors based on a set of experts making vector predictions in [0,1]n. We measure the loss of individual predictions by the 2-norm between the actual outcome vector and the prediction. The loss of an expert is then the sum of the losses experienced on individual trials. We obtain bounds for the loss of our expert algorithm in terms of the loss of the best expert analogous to the well-known results for scalar experts making real-valued predictions of a binary outcome.
Generic object recognition by combining distinct features in machine learning

In a generic image object recognition or categorization system, the relevant features or descriptors from a characteristic point, patch or region of an image are often obtained by different approaches. These features are often separately selected and learned by machine learning methods. In this paper, the relation between distinct features obtained by different feature extraction approaches from the same original images was studied by Kernel Canonical Correlation Analysis (KCCA). We apply a Support Vector Machine (SVM) classifier in the learnt semantic space of the combined features and compare against SVM on the raw data and previously published state-of-the-art results. Experiment show that significant improvement is achieved with the SVM in the semantic space in comparison with direct SVM classification on the raw data.
Improving "bag-of-keypoints" image categorisation: Generative Models and PDF-Kernels

In this paper we propose two distinct enhancements to the basic “bag-of-keypoints” image categorisation scheme proposed in . In this approach images are represented as a variable sized set of local image features (keypoints). Thus, we require machine learning tools which can operate on sets of vectors. In  this is achieved by representing the set as a histogram over bins found by k-means. We show how this approach can be improved and generalised using Gaussian Mixture Models (GMMs). Alternatively, the set of keypoints can be represented directly as a probability density function, over which a kernel can be defined. This approach is shown to give state of the art categorisation performance.
Semantic text features from small world graphs

We present a set of methods for creating a semantic representation from a collection of textual documents. Given a document collection we use a simple algorithm to connect the documents into a tree or a graph. Using the imposed topology we define a feature and document similarity measures. We use the kernel alignment to compare the quality of various similarity measures. Results show that the document similarity defined over the topology gives better alignment than standard cosine similarity measure on a bag of words document representation.
PAC-Bayesian Compression Bounds on the Prediction Error of Learning Algorithms for Classification

We consider bounds on the prediction error of classification algorithms based on sample compression. We refine the notion of a compression scheme to distinguish permutation and repetition invariant and non-permutation and repetition invariant compression schemes leading to different prediction error bounds. Also, we extend known results on compression to the case of non-zero empirical risk.We provide bounds on the prediction error of classifiers returned by mistake-driven online learning algorithms by interpreting mistake bounds as bounds on the size of the respective compression scheme of the algorithm. This leads to a bound on the prediction error of perceptron solutions that depends on the margin a support vector machine would achieve on the same training sample.Furthermore, using the property of compression we derive bounds on the average prediction error of kernel classifiers in the PAC-Bayesian framework. These bounds assume a prior measure over the expansion coefficients in the data-dependent kernel expansion and bound the average prediction error uniformly over subsets of the space of expansion coefficients.
The use of machine translation tools for cross-lingual text mining

Eigen-analysis such as LSI or KCCA was already successfully applied to cross-lingual information retrieval. This approach has a weakness in that it needs an aligned training set of documents. In this paper we address this weakness and show that it can be successfully avoided through the use of machine translation. We show that the performance is similar on the domains where human generated training seta are available. However for other domains artificial training sets can be generated that significantly outperform human generated ones obtained from a different domain.
KCCA Feature Selection for fMRI Analysis

We use Kernel Canonical Correlation Analysis (KCCA) to infer brain activity in functional MRI by learning a semantic representation of fMRI brain scans and their associated activity signal. The semantic space provides a common representation and enables a comparison between the fMRI and the activity signal. We compare the approach against Canonical Correlation Analysis (CCA) and the more commonly used Ordinary Correlation Analysis (OCA) by localising “activity” on a simulated null data set. We also compare performance of the methods on the localisation of brain regions which control finger movement and regions that are involved in mental calculation. Finally we present an approach to reconstruct an activity signal from an “unknown” testing-set fMRI scans. This is used to validate the learnt semantics as non-trivial.
Enlarging the Margins in Perceptron Decision Trees

Capacity control in perceptron decision trees is typically performed by controlling their size. We prove that other quantities can be as relevant to reduce their flexibility and combat overfitting. In particular, we provide an upper bound on the generalization error which depends both on the size of the tree and on the margin of the decision nodes. So enlarging the margin in perceptron decision trees will reduce the upper bound on generalization error. Based on this analysis, we introduce three new algorithms, which can induce large margin perceptron decision trees. To assess the effect of the large margin bias, OC1 (Journal of Artificial Intelligence Research, 1994, 2, 1–32.) of Murthy, Kasif and Salzberg, a well-known system for inducing perceptron decision trees, is used as the baseline algorithm. An extensive experimental study on real world data showed that all three new algorithms perform better or at least not significantly worse than OC1 on almost every dataset with only one exception. OC1 performed worse than the best margin-based method on every dataset.
Support Vector Machine to Synthesise Kernels

In this paper, we introduce a new method (SVM_2K) which amalgamates the capabilities of the Support Vector Machine (SVM) and Kernel Canonical Correlation Analysis (KCCA) to give a more sophisticated combination rule that the boosting framework allows. We show how this combination can be achieved within a unified optimisation model to create a consistent learning rule which combines the classification abilities of the individual SVMs with the synthesis abilities of KCCA. To solve the unified problem, we present an algorithm based on the Augmented Lagrangian Method. Experiments show that SVM_2K performs well on generic object recognition problems in computer vision.
Complexity of Pattern Classes and Lipschitz Property

Rademacher and Gaussian complexities are successfully used in learning theory for measuring the capacity of the class of functions to be learned. One of the most important properties for these complexities is their Lipschitz property: a composition of a class of functions with a fixed Lipschitz function may increase its complexity by at most twice the Lipschitz constant. The proof of this property is non-trivial (in contrast to the other properties) and it is believed that the proof in the Gaussian case is conceptually more difficult then the one for the Rademacher case. In this paper we give a detailed prove of the Lipschitz property for the Rademacher case and generalize the same idea to an arbitrary complexity (including the Gaussian). We also discuss a related topic about the Rademacher complexity of a class consisting of all the Lipschitz functions with a given Lipschitz constant. We show that the complexity is surprisingly low in the one-dimensional case. The question for higher dimensions remains open.
KCCA for fMRI Analysis

We use Kernel Canonical Correlation Analysis (KCCA) to infer brain activity in functional MRI by learning a semantic representation of fMRI brain scans and their associated activity signal. The semantic space provides a common representation and enables a comparison between the fMRI and the activity signal. We compare the approach against Canonical Correlation Analysis (CCA) by localising “activity” on a simulated null data set. Finally we present an approach to reconstruct an activity signal from a testing-set fMRI scans (both simulated and real), a method which allows us to validate our initial analysis.
Efficient computation of gap-weighted string kernels on large alphabets

We present a sparse dynamic programming algorithm that, given two strings s, t, a gap penalty λ, and an integer p, computes the value of the gap-weighted length-p subsequences kernel. The algorithm works in time O(p|M | log min(|s|, |t|)), where M = {(i, j)|si = tj} is the set of matches of characters in the two sequences. The new algorithm is empirically evaluated against a full dynamic programming approach and a trie-based algorithm on synthetic data. Based on the experiments, the full dynamic programming approach is the fastest on short strings, and on long strings if the alphabet is small. On large alphabets, the new sparse dynamic programming algorithm is the most efficient. On medium-sized alphabets the trie-based approach is best if the maximum number of allowed gaps is strongly restricted.
Latent Semantic Kernels

Kernel methods like support vector machines have successfully been used for text categorization. A standard choice of kernel function has been the inner product between the vector-space representation of two documents, in analogy with classical information retrieval (IR) approaches.Latent semantic indexing (LSI) has been successfully used for IR purposes as a technique for capturing semantic relations between terms and inserting them into the similarity measure between two documents. One of its main drawbacks, in IR, is its computational cost.In this paper we describe how the LSI approach can be implemented in a kernel-defined feature space.We provide experimental results demonstrating that the approach can significantly improve performance, and that it does not impair it.
Kernel Methods for Pattern Analysis: Detecting stable patterns

As discussed in Chapter 1 perhaps the most important property of a pattern analysis algorithm is that it should identify statistically stable patterns. A stable relation is one that reflects some property of the source generating the data, and is therefore not a chance feature of the particular dataset. Proving that a given pattern is indeed significant is the concern of ‘learning theory’, a body of principles and methods that estimate the reliability of pattern functions under appropriate assumptions about the way in which the data was generated. The most common assumption is that the individual training examples are generated independently according to a fixed distribution, being the same distribution under which the expected value of the pattern function is small. Statistical analysis of the problem can therefore make use of the law of large numbers through the ‘concentration’ of certain random variables. Concentration would be all that we need if we were only to consider one pattern function. Pattern analysis algorithms typically search for pattern functions over whole classes of functions, by choosing the function that best fits the particular training sample. We must therefore be able to prove stability not of a pre-defined pattern, but of one deliberately chosen for its fit to the data. Clearly the more pattern functions at our disposal, the more likely that this choice could be a spurious pattern. The critical factor that controls how much our choice may have compromised the stability of the resulting pattern is the ‘capacity’ of the function class.
Canonical Correlation Analysis: An Overview with Application to Learning Methods

We present a general method using kernel canonical correlation analysis to learn a semantic representation to web images and their associated text. The semantic space provides a common representation and enables a comparison between the text and images. In the experiments, we look at two approaches of retrieving images based on only their content from a text query. We compare orthogonalization approaches against a standard cross-representation retrieval technique known as the generalized vector space model.
Texture Classification by Combining Wavelet and Contourlet Features

In the recent decades, many features used to represent a texture were proposed. However, these features are always used exclusively. In this paper, a novel approach is presented that combines two types of features extracted by discrete wavelet transform and contourlet transform. Support vector machines (SVMs), which have demonstrated excellent performance in a variety of pattern recognition problems, are used as classifiers. The algorithm is tested on four different datasets, selected from Brodatz and VisTex database. The experimental results show that the combined features result in better classification rates than using only one type of those.
Kernel Methods for Pattern Analysis

The lectures will introduce the kernel methods approach to pattern analysis  through the particular example of support vector machines for classification. The presentation touches on: generalization, optimization, dual representation, kernel design and algorithmic implementations. We then broaden the discussion to consider general kernel methods by introducing different kernels, different learning tasks, and subspace methods such as kernel PCA. The emphasis is on the flexibility of the approach in applying the analyses to different data, with the caveat that the design of the kernel must rely on domain knowledge. Nonetheless we will argue that, ignoring the technical requirement of positive semi-definiteness, kernel design is not an unnatural task for a practitioner. The overall aim is to give a view of the subject that will enable newcomers to the field to gain their bearings so that they can move to apply or develop the techniques for their particular application.
Learning Theory

Communication complexity has recently been recognized as a major obstacle in the implementation of combinatorial auctions. In this paper, we consider a setting in which the auctioneer (elicitor), instead of passively waiting for the bids presented by the bidders, elicits the bidders’ preferences (or valuations) by asking value queries. It is known that in the more general case (no restrictions on the bidders’ preferences) this approach requires the exchange of an exponential amount of information. However, in practical economic scenarios we might expect that bidders’ valuations are somewhat structured. In this paper, we consider several such scenarios, and we show that polynomial elicitation in these cases is often sufficient. We also prove that the family of “easy to elicit” classes of valuations is closed under union. This suggests that efficient preference elicitation is possible in a scenario in which the elicitor, contrary to what it is commonly assumed in the literature on preference elicitation, does not exactly know the class to which the function to elicit belongs. Finally, we discuss what renders a certain class of valuations “easy to elicit with value queries”.
Linear Programming Boosting via Column Generation

We examine linear program (LP) approaches to boosting and demonstrate their efficient solution using LPBoost, a column generation based simplex method. We formulate the problem as if all possible weak hypotheses had already been generated. The labels produced by the weak hypotheses become the new feature space of the problem. The boosting task becomes to construct a learning function in the label space that minimizes misclassification error and maximizes the soft margin. We prove that for classification, minimizing the 1-norm soft margin error function directly optimizes a generalization error bound. The equivalent linear program can be efficiently solved using column generation techniques developed for large-scale optimization problems. The resulting LPBoost algorithm can be used to solve any LP boosting formulation by iteratively optimizing the dual misclassification costs in a restricted LP and dynamically generating weak hypotheses to make new LP columns. We provide algorithms for soft margin classification, confidence-rated, and regression boosting problems. Unlike gradient boosting algorithms, which may converge in the limit only, LPBoost converges in a finite number of iterations to a global solution satisfying mathematically well-defined optimality conditions. The optimal solutions of LPBoost are very sparse in contrast with gradient based methods. Computationally, LPBoost is competitive in quality and computational cost to AdaBoost.
On Maximum Margin Hierarchical Classification

We present work in progress towards maximum margin hierarchical classification where the objects are allowed to belong to more than one category at a time. The classification hierarchy is represented as a Markov network equipped with an exponential family defined on the edges. We present a variation of the maximum margin multilabel learning framework, suited to the hierarchical classification task and allows efficient implementation via gradient-based methods. We compare the behaviour of the proposed method to the recently introduced hierarchical regularized least squares classifier as well as two SVM variants in Reuter's news article classification.
Kernel Methods for Pattern Analysis: Basic kernels and kernel types

There are two key properties that are required of a kernel function for an application. Firstly, it should capture the measure of similarity appropriate to the particular task and domain, and secondly, its evaluation should require significantly less computation than would be needed in an explicit evaluation of the corresponding feature mapping ϕ. Both of these issues will be addressed in the next four chapters but the current chapter begins the consideration of the efficiency question. A number of computational methods can be deployed in order to shortcut the computation: some involve using closed-form analytic expressions, others exploit recursive relations, and others are based on sampling. This chapter aims to show several different methods in action, with the aim of illustrating how to design new kernels for specific applications. It will also pave the way for the final three chapters that carry these techniques into the design of advanced kernels. We will also return to an important theme already broached in Chapter 3, namely that kernel functions are not restricted to vectorial inputs: kernels can be designed for objects and structures as diverse as strings, graphs, text documents, sets and graph-nodes. Given the different evaluation methods and the diversity of the types of data on which kernels can be defined, together with the methods for composing and manipulating kernels outlined in Chapter 3, it should be clear how versatile this approach to data modelling can be, allowing as it does for refined customisations of the embedding map ϕ to the problem at hand.
Signal Extraction for Brain-Computer Interface

We use Kernel Canonical Correlation Analysis (KCCA) for detecting brain activity in function MRI by learning a semantic representation of fMRI brain scans and their associated time frequency. The semantic space provides a common representation and enables a comparison between the fMRI and time frequency. We compare the approach against Canonical Correlation Analysis (CCA) by localising brain regions that control finger movement and regions that are involved in mental calculation. We also compare the two approaches on a simulated null data set. We hypothesis that once a link can be established between regions of the brain to task one could create a brain-computer interface were computer related tasks could be activated by brain "thought" activity.