nils-herrmann/clean_scirepeval huggingface dataset:
On the learnability and usage of acyclic probabilistic finite automata

We propose and analyze a distribution learning algorithm for a subclass ofacyclic probalistic finite automata(APFA). This subclass is characterized by a certain distinguishability property of the automata's states. Though hardness results are known for learning distributions generated by general APFAs, we prove that our algorithm can efficiently learn distributions generated by the subclass of APFAs we consider. In particular, we show that the KL-divergence between the distribution generated by the target source and the distribution generated by our hypothesis can be made arbitrarily small with high confidence in polynomial time. We present two applications of our algorithm. In the first, we show how to model cursively written letters. The resulting models are part of a complete cursive handwriting recognition system. In the second application we demonstrate how APFAs can be used to build multiple-pronunciation models for spoken words. We evaluate the APFA-based pronunciation models on labeled speech data. The good performance (in terms of the log-likelihood obtained on test data) achieved by the APFAs and the little time needed for learning suggests that the learning algorithm of APFAs might be a powerful alternative to commonly used probabilistic models.
Nonparametric Quantile Regression

In regression, the desired estimate of y|x is not always given by a conditional mean, although this is most common. Sometimes one wants to obtain a good estimate that satisfies the property that a proportion, , of y|x, will be below the estimate. For = 0.5 this is an estimate of the median. What might be called median regression, is subsumed under the term quantile regression. We present a nonparametric version of a quantile estimator, which can be obtained by solving a simple quadratic programming problem and provide uniform convergence statements and bounds on the quantile property of our estimator. Experimental results show the feasibility of the approach and competitiveness of our method with existing ones. We discuss several types of extensions including an approach to solve the quantile crossing problems, as well as a method to incorporate prior qualitative knowledge such as monotonicity constraints.
Kernel Methods for Missing Variables

We present methods for dealing with missing variables in the context of Gaussian Processes and Support Vector Machines. This solves an important problem which has largely been ignored by kernel methods: How to systematically deal with incomplete data? Our method can also be applied to problems with partially observed labels as well as to the transductive setting where we view the labels as missing data. Our approach relies on casting kernel methods as an estimation problem in exponential families. Hence, estimation with missing variables becomes a problem of computing marginal distributions, and finding efficient optimization methods. To that extent we propose an optimization scheme which extends the Concave Convex Procedure (CCP) of Yuille and Rangarajan, and present a simplified and intuitive proof of its convergence. We show how our algorithm can be specialized to various cases in order to efficiently solve the optimization problems that arise. Encouraging preliminary experimental results on the USPS dataset are also presented.
Learning the Kernel with Hyperkernels

This paper addresses the problem of choosing a kernel suitable for estimation with a support vector machine, hence further automating machine learning. This goal is achieved by defining a reproducing kernel Hilbert space on the space of kernels itself. Such a formulation leads to a statistical estimation problem similar to the problem of minimizing a regularized risk functional.We state the equivalent representer theorem for the choice of kernels and present a semidefinite programming formulation of the resulting optimization problem. Several recipes for constructing hyperkernels are provided, as well as the details of common machine learning problems. Experimental results for classification, regression and novelty detection on UCI data show the feasibility of our approach.
Parametric model-based clustering

Parametric, model-based algorithms learn generative models from the data, with each model corresponding to one particular cluster. Accordingly, the model-based partitional algorithm will select the most suitable model for any data object (Clustering step}, and will recompute parametric models using data specifically from the corresponding clusters {Maximization step). This Clustering-Maximization framework have been widely used and have shown promising results in many applications including complex variable-length data. The paper proposes (Experience-Innovation} (EI) method as a natural extension of the (Clustering-Maximization} framework. This method includes 3 components: (1) keep the best past experience and make empirical likelihood trajectory monotonical as a result; (2) find a new model as a function of existing models so that the corresponding cluster will split existing clusters with bigger number of elements and smaller uniformity; (3) heuristical innovations, for example, several trials with random initial settings. Also, we introduce clustering regularisation based on the balanced complex of two conditions: (1) significance of any particular cluster; (2) difference between any 2 clusters. We illustrate effectiveness of the proposed methods using first-order Markov model in application to the large web-traffic dataset. The aim of the experiment is to explain and understand the way people interact with web sites.
Step size-adapted online support vector learning

We present an online Support Vector Machine (SVM) that uses Stochastic Meta-Descent (SMD) to adapt its step size automatically. We formulate the online learning problem as a stochastic gradient descent in Reproducing Kernel Hilbert Space (RKHS) and translate SMD to the nonparametric setting, where its gradient trace parameter is no longer a coefficient vector but an element of the RKHS. We derive efficient updates that allow us to perform the step size adaptation in linear time. We apply the online SVM framework to a variety of loss functions and in particular show how to achieve efficient online multiclass classification. Experimental evidence suggests that our algorithm outperforms existing methods.
Measuring Statistical Dependence with Hilbert-Schmidt Norms

We propose an independence criterion based on the eigen-spectrum of covariance operators in reproducing kernel Hilbert spaces (RKHSs), consisting of an empirical estimate of the Hilbert-Schmidt norm of the cross-covariance operator (we term this a Hilbert-Schmidt Independence Criterion, or HSIC). This approach has several advantages, compared with previous kernel-based independence criteria. First, the empirical estimate is simpler than any other kernel dependence test, and requires no user-defined regularisation. Second, there is a clearly defined population quantity which the empirical estimate approaches in the large sample limit, with exponential convergence guaranteed between the two: this ensures that independence tests based on HSIC do not suffer from slow learning rates. Finally, we show in the context of independent component analysis (ICA) that the performance of HSIC is competitive with that of previously published kernel-based criteria, and of other recently published ICA methods.
Universal Clustering with Regularization in Probabilistic Space

We propose universal clustering in line with the concepts of universal estimation. In order to illustrate above model we introduce family of power loss functions in probabilistic space which is marginally linked to the Kullback-Leibler divergence. Above model proved to be effective in application to the synthetic data. Also, we consider large web-traffic dataset. The aim of the experiment is to explain and understand the way people interact with web sites. 
 
The paper proposes special regularization in order to ensure consistency of the corresponding clustering model.
NICTA at TRECVID 2005 Shot Boundary Detection Task

National ICT Australia (NICTA) participated in TRECVID Shot Boundary Detection Task for the first time in 2005. ’s system is based on a generic framework that integrates feature extraction from video analysis and statistical machine learning. We are pleased to see that the NICTA system performed very well in TRECVID 2005. We submitted 10 test runs with results included in Table 1. Major differences between the test runs include turning on/off some modules when making the shot boundary detection decision, and changes to some parameters.
Heteroscedastic Gaussian process regression

This paper presents an algorithm to estimate simultaneously both mean and variance of a non parametric regression problem. The key point is that we are able to estimate variance locally unlike standard Gaussian Process regression or SVMs. This means that our estimator adapts to the local noise. The problem is cast in the setting of maximum a posteriori estimation in exponential families. Unlike previous work, we obtain a convex optimization problem which can be solved via Newton's method.
A Short Tour of Kernel Methods for Graphs

Machine learning research has – apart from some exceptions – originally concentrated on learning from data that can naturally be represented in a single table without links between the instances. Due to the needs of many real-world applications , in recent years an increasing amount of reserch has been devoted to machine learning on relational data with more complex structure. This book is then concerned with a very popular subject among this research, graphical models for relational data. In this chapter now we will give a short introduction to another popular subject, kernel methods for relational data, in particular graph spaces. Kernel Methods can loosely be characterised as learning algorithms that take as information about the data only the covariance structure of the dataset. This way we can look at two separate aspects of kernel methods almost independently, the kernel function defining the covariance structure and the kernel-based learning algorithm. Most popular kernel methods can naturally be derived from a regularised risk minimisation setting. In this setting, positive-definiteness of the kernel function has the additional benefit of rendering the optimisation problem convex such that the globally optimal solution can efficiently be found by appropriate algorithms. The relation between kernel methods and graphical models can perhaps be described best by having a brief look at Gaussian process regression. This algorithm is based on the idea of modelling the distribution of the labels of any finite dataset by a multivariate normal distribution with given covariance function and additive Gaussian noise. If the data obeys the Markov properties relative to a graph G, the
A Tutorial Review of RKHS Methods in Machine Learning

Over the last ten years, estimation and learning methods utilizing positive definite kernels have become rather popular, particularly in machine learning. Since these methods have a stronger mathematical slant than earlier machine learning methods (e.g., neural networks), there is also significant interest in the statistical and mathematical community for these methods. The present review aims to summarize the state of the art on a conceptual level. In doing so, we build on various sources (including the books [Vapnik, 1998, Burges, 1998, Cristianini and Shawe-Taylor, 2000, Herbrich, 2002] and in particular [Schölkopf and Smola, 2002]), but we also add a fair amount of recent material which helps unifying the exposition. The main idea of all the described methods can be summarized in one paragraph. Traditionally, theory and algorithms of machine learning and statistics has been very well developed for the linear case. Real world data analysis problems, on the other hand, often requires nonlinear methods to detect the kind of dependences that allow successful prediction of properties of interest. By using a positive definite kernel, one can sometimes have the best of both worlds. The kernel corresponds to a dot product in a (usually high dimensional) feature space. In this space, our estimation methods are linear, but as long as we can formulate everything in terms of kernel evaluations, we never explicitly have to work in the high dimensional feature space.
Support Vector Machines

We describe the central ideas of Support Vector (SV) learning in a nutshell. This includes the notion of learning from data via risk minimization and the notion of kernels as an efficient means of encoding prior information. We give an overview over the optimization problems arising from SV classification and discuss various extensions such as kernel PCA and automatic margin adaptation. 
 
 
 
 
support vectors; 
kernels; 
feature space; 
regularization; 
risk minimization; 
optimization; 
classification
Kernel Methods for Measuring Independence

We introduce two new functionals, the constrained covariance and the kernel mutual information, to measure the degree of independence of random variables. These quantities are both based on the covariance between functions of the random variables in reproducing kernel Hilbert spaces (RKHSs). We prove that when the RKHSs are universal, both functionals are zero if and only if the random variables are pairwise independent. We also show that the kernel mutual information is an upper bound near independence on the Parzen window estimate of the mutual information. Analogous results apply for two correlation-based dependence functionals introduced earlier: we show the kernel canonical correlation and the kernel generalised variance to be independence measures for universal kernels, and prove the latter to be an upper bound on the mutual information near independence. The performance of the kernel dependence functionals in measuring independence is verified in the context of independent component analysis.
Protein function prediction via graph kernels

Computational approaches to protein function prediction infer protein function by finding proteins with similar sequence, structure, surface clefts, chemical properties, amino acid motifs, interaction partners or phylogenetic profiles. We present a new approach that combines sequential, structural and chemical information into one graph model of proteins. We predict functional class membership of enzymes and non-enzymes using graph kernels and support vector machine classification on these protein graphs.



Our graph model, derivable from protein sequence and structure only, is competitive with vector models that require additional protein information, such as the size of surface pockets. If we include this extra information into our graph model, our classifier yields significantly higher accuracy levels than the vector models. Hyperkernels allow us to select and to optimally combine the most relevant node attributes in our protein graphs. We have laid the foundation for a protein function prediction system that integrates protein information from various sources efficiently and effectively.


AVAILABILITY
More information available via www.dbs.ifi.lmu.de/Mitarbeiter/borgwardt.html.
Boîte à outils SVM simple et rapide

If SVM (Support Vector Machines) are now considered as one of the best learning methods, they are still considered as slow. Here we propose a Matlab toolbox that enables the usage of SVM in a fast and simple way. This is done thanks to the projected gradient method which is well adapted to the problem : SimpleSVM (VIS 03). We chose to implement this algorithm with Matlab environment since it is user-friendly and efficient - it uses the ATLAS (Automatically Tuned Linear Algebra Software) library. The comparison to the state of the art in this field, SMO (Sequential Minimal Optimization) shows that in some cases, our solution is faster and less complex. In order to point out how fast and simple our method is, we give here results on the MNITS database. It was possible to compute a satisfying solution in a quite short time (one hour and a half on a PC with Linux distribution to compute 45 binary classifiers, with
Invariances in Classification: an efficient SVM implementation

Often, in pattern recognition, complementary knowledge is available. This could be useful to improve the performance of the recognition system. Part of this knowledge regards invariances, in particular when treating images or voice data. Many approaches have been proposed to incorporate invariances in pattern recognition systems. Some of these approaches require a pre-processing phase, others integrate the invariances in the algorithms. We present a unifying formulation of the problem of incorporating invariances into a pattern recognition classifier and we extend the SimpleSVM algorithm [Vishwanathan et al., 2003] to handle invariances efficiently.
Online learning with kernels

Kernel-based algorithms such as support vector machines have achieved considerable success in various problems in batch setting, where all of the training data is available in advance. Support vector machines combine the so-called kernel trick with the large margin idea. There has been little use of these methods in an online setting suitable for real-time applications. In this paper, we consider online learning in a reproducing kernel Hilbert space. By considering classical stochastic gradient descent within a feature space and the use of some straightforward tricks, we develop simple and computationally efficient algorithms for a wide range of problems such as classification, regression, and novelty detection. In addition to allowing the exploitation of the kernel trick in an online setting, we examine the value of large margins for classification in the online setting with a drifting target. We derive worst-case loss bounds, and moreover, we show the convergence of the hypothesis to the minimizer of the regularized risk functional. We present some experimental results that support the theory as well as illustrating the power of the new algorithms for online novelty detection.
Une boîte à outils rapide et simple pour les SVM

Resume : Si les SVM (Support Vector Machines, ou Separateurs a Vaste Marge) sont aujourd’hui reconnus comme l’une des meilleures methodes d’apprentissage, ils restent consideres comme lents. Nous proposons ici une boite a outils Matlab permettant d’utiliser simplement et rapidement les SVM grâce a une methode de gradient projete particulierement bien adaptee au probleme : SimpleSVM (Vishwanathan et al., 2003). Nous avons choisi de coder cet algorithme dans l’environnement Matlab afin de profiter de sa convivialite tout en s’assurant une bonne efficacite. La comparaison de notre solution avec l’etat de l’art dans le domaine SMO (Sequential Minimal Optimization), montre qu’il s’agit la d’une solution dans certains cas plus rapide et d’une complexite moindre. Pour illustrer la simplicite et la rapidite de notre methode, nous montrons enfin que sur la base de donnees MNIST, il a ete possible d’obtenir des resultats satisfaisants en un temps relativement court (une heure et demi de calcul sur un PC sous linux pour construire 45 classifieurs binaires sur 60.000 exemples en dimension 576). Mots-cles : Support Vector Machine, Separateur a Vaste Marge, SVM, Apprentissage, Boite a outils Matlab, Contraintes actives, Gradient projete, MNIST.
Binet-Cauchy Kernels

We propose a family of kernels based on the Binet-Cauchy theorem and its extension to Fredholm operators. This includes as special cases all currently known kernels derived from the behavioral framework, diffusion processes, marginalized kernels, kernels on graphs, and the kernels on sets arising from the subspace angle approach. Many of these kernels can be seen as the extrema of a new continuum of kernel functions, which leads to numerous new special cases. As an application, we apply the new class of kernels to the problem of clustering of video sequences with encouraging results.
Learning with non-positive kernels

In this paper we show that many kernel methods can be adapted to deal with indefinite kernels, that is, kernels which are not positive semidefinite. They do not satisfy Mercer's condition and they induce associated functional spaces called Reproducing Kernel Kreĭn Spaces (RKKS), a generalization of Reproducing Kernel Hilbert Spaces (RKHS).Machine learning in RKKS shares many "nice" properties of learning in RKHS, such as orthogonality and projection. However, since the kernels are indefinite, we can no longer minimize the loss, instead we stabilize it. We show a general representer theorem for constrained stabilization and prove generalization bounds by computing the Rademacher averages of the kernel class. We list several examples of indefinite kernels and investigate regularization methods to solve spline interpolation. Some preliminary experiments with indefinite kernels for spline smoothing are reported for truncated spectral factorization, Landweber-Fridman iterations, and MR-II.
Gaussian process classification for segmenting and annotating sequences

Many real-world classification tasks involve the prediction of multiple, inter-dependent class labels. A prototypical case of this sort deals with prediction of a sequence of labels for a sequence of observations. Such problems arise naturally in the context of annotating and segmenting observation sequences. This paper generalizes Gaussian Process classification to predict multiple labels by taking dependencies between neighboring labels into account. Our approach is motivated by the desire to retain rigorous probabilistic semantics, while overcoming limitations of parametric methods like Conditional Random Fields, which exhibit conceptual and computational difficulties in high-dimensional input spaces. Experiments on named entity recognition and pitch accent prediction tasks demonstrate the competitiveness of our approach.
A Second Order Cone programming Formulation for Classifying Missing Data

We propose a convex optimization based strategy to deal with uncertainty in the observations of a classification problem. We assume that instead of a sample (xi, yi) a distribution over (xi, yi) is specified. In particular, we derive a robust formulation when the distribution is given by a normal distribution. It leads to Second Order Cone Programming formulation. Our method is applied to the problem of missing data, where it outperforms direct imputation.
Laplace Propagation

We present a novel method for approximate inference in Bayesian models and regularized risk functionals. It is based on the propagation of mean and variance derived from the Laplace approximation of conditional probabilities in factorizing distributions, much akin to Minka's Expectation Propagation. In the jointly normal case, it coincides with the latter and belief propagation, whereas in the general case, it provides an optimization strategy containing Support Vector chunking, the Bayes Committee Machine, and Gaussian Process chunking as special cases.