nils-herrmann/clean_scirepeval huggingface dataset:
The Forgetron: A Kernel-Based Perceptron on a Fixed Budget

The Perceptron algorithm, despite its simplicity, often performs well on online classification tasks. The Perceptron becomes especially effective when it is used in conjunction with kernels. However, a common difficulty encountered when implementing kernel-based online algorithms is the amount of memory required to store the online hypothesis, which may grow unboundedly. In this paper we present and analyze the Forgetron algorithm for kernel-based online learning on a fixed memory budget. To our knowledge, this is the first online learning algorithm which, on one hand, maintains a strict limit on the number of examples it stores while, on the other hand, entertains a relative mistake bound. In addition to the formal results, we also present experiments with real datasets which underscore the merits of our approach.
Learning Preferences Graphs by Soft Projections onto Polyhedra

A measuring apparatus for determining the position of a movable element with respect to a pair of spaced reference means, e.g. mirrors, rotatable around parallel shafts. The movable element emits a light beam from a position to both mirrors. As a result of the rotation, the two mirrors convert the reflected light beam into a light pulse series. Each of these light pulse series is detected by a detector, which detected light pulse series are supplied to a processing unit for calculating from the light pulse series and from a starting pulse the position of the movable element with respect to both mirrors.
A Temporal Kernel-Based Model for Tracking Hand Movements from Neural Activities

We devise and experiment with a dynamical kernel-based system for tracking hand movements from neural activity. The state of the system corresponds to the hand location, velocity, and acceleration, while the system's input are the instantaneous spike rates. The system's state dynamics is defined as a combination of a linear mapping from the previous estimated state and a kernel-based mapping tailored for modeling neural activities. In contrast to generative models, the activity-to-state mapping is learned using discriminative methods by minimizing a noise-robust loss function. We use this approach to predict hand trajectories on the basis of neural activity in motor cortex of behaving monkeys and find that the proposed approach is more accurate than both a static approach based on support vector regression and the Kalman filter.
Large margin hierarchical classification

We present an algorithmic framework for supervised classification learning where the set of labels is organized in a predefined hierarchical structure. This structure is encoded by a rooted tree which induces a metric over the label set. Our approach combines ideas from large margin kernel methods and Bayesian analysis. Following the large margin principle, we associate a prototype with each label in the tree and formulate the learning task as an optimization problem with varying margin constraints. In the spirit of Bayesian methods, we impose similarity requirements between the prototypes corresponding to adjacent labels in the hierarchy. We describe new online and batch algorithms for solving the constrained optimization problem. We derive a worst case loss-bound for the online algorithm and provide generalization analysis for its batch counterpart. We demonstrate the merits of our approach with a series of experiments on synthetic, text and speech data.
An Efficient Extension to Mixture Techniques for Prediction and Decision Trees

We present an efficient method for maintaining mixtures of prunings of a prediction or decision tree that extends the previous methods for “node-based” prunings (Buntine, 1990; Willems, Shtarkov, & Tjalkens, 1995; Helmbold & Schapire, 1997; Singer, 1997) to the larger class of edge-based prunings. The method includes an online weight-allocation algorithm that can be used for prediction, compression and classification. Although the set of edge-based prunings of a given tree is much larger than that of node-based prunings, our algorithm has similar space and time complexity to that of previous mixture algorithms for trees. Using the general online framework of Freund and Schapire (1997), we prove that our algorithm maintains correctly the mixture weights for edge-based prunings with any bounded loss function. We also give a similar algorithm for the logarithmic loss function with a corresponding weight-allocation algorithm. Finally, we describe experiments comparing node-based and edge-based mixture models for estimating the probability of the next word in English text, which show the advantages of edge-based models.
An Online Algorithm for Hierarchical Phoneme Classification

We present an algorithmic framework for phoneme classification where the set of phonemes is organized in a predefined hierarchical structure. This structure is encoded via a rooted tree which induces a metric over the set of phonemes. Our approach combines techniques from large margin kernel methods and Bayesian analysis. Extending the notion of large margin to hierarchical classification, we associate a prototype with each individual phoneme and with each phonetic group which corresponds to a node in the tree. We then formulate the learning task as an optimization problem with margin constraints over the phoneme set. In the spirit of Bayesian methods, we impose similarity requirements between the prototypes corresponding to adjacent phonemes in the phonetic hierarchy. We describe a new online algorithm for solving the hierarchical classification problem and provide worst-case loss analysis for the algorithm. We demonstrate the merits of our approach by applying the algorithm to synthetic data and as well as speech data.
On the Learnability and Design of Output Codes for Multiclass Problems

Output coding is a general framework for solving multiclass categorization problems. Previous research on output codes has focused on building multiclass machines given predefined output codes. In this paper we discuss for the first time the problem of designing output codes for multiclass problems. For the design problem of discrete codes, which have been used extensively in previous works, we present mostly negative results. We then introduce the notion of continuous codes and cast the design problem of continuous codes as a constrained optimization problem. We describe three optimization problems corresponding to three different norms of the code matrix. Interestingly, for the l2 norm our formalism results in a quadratic program whose dual does not depend on the length of the code. A special case of our formalism provides a multiclass scheme for building support vector machines which can be solved efficiently. We give a time and space efficient algorithm for solving the quadratic program. We describe preliminary experiments with synthetic data show that our algorithm is often two orders of magnitude faster than standard quadratic programming packages. We conclude with the generalization properties of the algorithm.
Leveraging the margin more carefully

Boosting is a popular approach for building accurate classifiers. Despite the initial popular belief, boosting algorithms do exhibit overfitting and are sensitive to label noise. Part of the sensitivity of boosting algorithms to outliers and noise can be attributed to the unboundedness of the margin-based loss functions that they employ. In this paper we describe two leveraging algorithms that build on boosting techniques and employ a bounded loss function of the margin. The first algorithm interleaves the expectation maximization (EM) algorithm with boosting steps. The second algorithm decomposes a non-convex loss into a difference of two convex losses. We prove that both algorithms converge to a stationary point. We also analyze the generalization properties of the algorithms using the Rademacher complexity. We describe experiments with both synthetic data and natural data (OCR and text) that demonstrate the merits of our framework, in particular robustness to outliers.
The power of amnesia: Learning probabilistic automata with variable memory length

We propose and analyze a distribution learning algorithm for variable memory length Markov processes. These processes can be described by a subclass of probabilistic finite automata which we name Probabilistic Suffix Automata (PSA). Though hardness results are known for learning distributions generated by general probabilistic automata, we prove that the algorithm we present can efficiently learn distributions generated by PSAs. In particular, we show that for any target PSA, the KL-divergence between the distribution generated by the target and the distribution generated by the hypothesis the learning algorithm outputs, can be made small with high confidence in polynomial time and sample complexity. The learning algorithm is motivated by applications in human-machine interaction. Here we present two applications of the algorithm. In the first one we apply the algorithm in order to construct a model of the English language, and use this model to correct corrupted text. In the second application we construct a simple stochastic model for E.coli DNA.
Online and batch learning of pseudo-metrics

We describe and analyze an online algorithm for supervised learning of pseudo-metrics. The algorithm receives pairs of instances and predicts their similarity according to a pseudo-metric. The pseudo-metrics we use are quadratic forms parameterized by positive semi-definite matrices. The core of the algorithm is an update rule that is based on successive projections onto the positive semi-definite cone and onto half-space constraints imposed by the examples. We describe an efficient procedure for performing these projections, derive a worst case mistake bound on the similarity predictions, and discuss a dual version of the algorithm in which it is simple to incorporate kernel operators. The online algorithm also serves as a building block for deriving a large-margin batch algorithm. We demonstrate the merits of the proposed approach by conducting experiments on MNIST dataset and on document filtering.
Logistic Regression, AdaBoost and Bregman Distances

We give a unified account of boosting and logistic regression in which each learning problem is cast in terms of optimization of Bregman distances. The striking similarity of the two problems in this framework allows us to design and analyze algorithms for both simultaneously, and to easily adapt algorithms designed for one problem to the other. For both problems, we give new algorithms and explain their potential advantages over existing methods. These algorithms are iterative and can be divided into two types based on whether the parameters are updated sequentially (one at a time) or in parallel (all at once). We also describe a parameterized family of algorithms that includes both a sequential- and a parallel-update algorithm as special cases, thus showing how the sequential and parallel approaches can themselves be unified. For all of the algorithms, we give convergence proofs using a general formalization of the auxiliary-function proof technique. As one of our sequential-update algorithms is equivalent to AdaBoost, this provides the first general proof of convergence for AdaBoost. We show that all of our algorithms generalize easily to the multiclass case, and we contrast the new algorithms with the iterative scaling algorithm. We conclude with a few experimental results with synthetic data that highlight the behavior of the old and newly proposed algorithms in different settings.
Learning to Align Polyphonic Music

We describe an efficient learning algorithm for aligning a symbolic representation of a musical piece with its acoustic counterpart. Our method employs a supervised learning approach by using a training set of aligned symbolic and acoustic representations. The alignment function we devise is based on mapping the input acousticsymbolic representation along with the target alignment into an abstract vector-space. Building on techniques used for learning support vector machines (SVM), our alignment function distills to a classifier in the abstract vectorspace which separates correct alignments from incorrect ones. We describe a simple iterative algorithm for learning the alignment function and discuss its formal properties. We use our method for aligning MIDI and MP3 representations of polyphonic recordings of piano music. We also compare our discriminative approach to a generative method based on a generalization of hidden Markov models. In all of our experiments, the discriminative method outperforms the HMM-based method.
Learning Theory, Proceedings of 17th Annual Conference on Learning Theory, COLT 2004

This book constitutes the refereed proceedings of the 17th Annual Conference on Learning Theory, COLT 2004, held in Banff, Canada in July 2004. The 46 revised full papers presented were carefully reviewed and selected from a total of 113 submissions. The papers are organized in topical sections on economics and game theory, online learning, inductive inference, probabilistic models, Boolean function learning, empirical processes, MDL, generalisation, clustering and distributed learning, boosting, kernels and probabilities, kernels and kernel matrices, and open problems.
A Comparison of New and Old Algorithms for a Mixture Estimation Problem

We investigate the problem of estimating the proportion vector which maximizes the likelihood of a given sample for a mixture of given densities. We adapt a framework developed for supervised learning and give simple derivations for many of the standard iterative algorithms like gradient projection and EM. In this framework, the distance between the new and old proportion vectors is used as a penalty term. The square distance leads to the gradient projection update, and the relative entropy to a new update which we call the exponentiated gradient update (EGή). Curiously, when a second order Taylor expansion of the relative entropy is used, we arrive at an update EMή which, for ή=1, gives the usual EM update. Experimentally, both the EMή-update and the EGή-update for ή > 1 outperform the EM algorithm and its variants. We also prove a polynomial bound on the rate of convergence of the EGή algorithm.
BoosTexter: A Boosting-based System for Text Categorization

This work focuses on algorithms which learn from examples to perform multiclass text and speech categorization tasks. Our approach is based on a new and improved family of boosting algorithms. We describe in detail an implementation, called BoosTexter, of the new boosting algorithms for text categorization tasks. We present results comparing the performance of BoosTexter and a number of other text-categorization algorithms on a variety of tasks. We conclude by describing the application of our system to automatic call-type identification from unconstrained spoken customer responses.
Learning Theory: 17th Annual Conference on Learning Theory, COLT 2004, Banff, Canada, July 1-4, 2004, Proceedings

Economics and Game Theory.- Towards a Characterization of Polynomial Preference Elicitation with Value Queries  Deterministic Calibration and Nash Equilibrium.- Reinforcement Learning for Average Reward Zero-Sum Games.- OnLine Learning.- Polynomial Time Prediction Strategy with Almost Optimal Mistake Probability.- Minimizing Regret with Label Efficient  Regret Bounds for Hierarchical Classification with Linear-Threshold Functions.- Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary.- Inductive Inference.- Learning Classes of Probabilistic Automata.- On the Learnability of E-pattern Languages over Small Alphabets.- Replacing Limit Learners with Equally Powerful One-Shot Query Learners.- Probabilistic Models.- Concentration Bounds for Unigrams Language  Inferring Mixtures of Markov Chains.- Boolean Function Learning.- PExact = Exact Learning.- Learning a Hidden Graph Using O(log n) Queries Per Edge.- Toward Attribute Efficient Learning of Decision Lists and Parities.- Empirical Processes.- Learning Over Compact Metric Spaces.- A Function Representation for Learning in Banach Spaces.- Local Complexities for Empirical Risk Minimization.- Model Selection by Bootstrap Penalization for Classification.- MDL.- Convergence of Discrete MDL for Sequential  On the Convergence of MDL Density Estimation.- Suboptimal Behavior of Bayes and MDL in Classification Under Misspecification.- Generalisation I.- Learning Intersections of Halfspaces with a Margin.- A General Convergence Theorem for the Decomposition Method.- Generalisation II.- Oracle Bounds and Exact Algorithm for Dyadic Classification Trees.- An Improved VC Dimension Bound for Sparse Polynomials.- A New PAC Bound for Intersection-Closed Concept Classes.- Clustering and Distributed Learning.- A Framework for Statistical Clustering with a Constant Time Approximation Algorithms for K-Median Clustering.- Data Dependent Risk Bounds for Hierarchical Mixture of Experts Classifiers.- Consistency in Models for Communication Constrained Distributed Learning.- On the Convergence of Spectral Clustering on Random Samples: The Normalized Case.- Boosting.- Performance Guarantees for Regularized Maximum Entropy Density Estimation.- Learning Monotonic Linear  Boosting Based on a Smooth Margin.- Kernels and Probabilities.- Bayesian Networks and Inner Product Spaces.- An Inequality for Nearly Log-Concave Distributions with Applications to Learning.- Bayes and Tukey Meet at the Center Point.- Sparseness Versus Estimating Conditional Probabilities: Some Asymptotic  Kernels and Kernel  A Statistical Mechanics Analysis of Gram Matrix Eigenvalue Spectra.- Statistical Properties of Kernel Principal Component  Kernelizing Sorting, Permutation, and Alignment for Minimum Volume PCA.- Regularization and Semi-supervised Learning on Large Graphs.- Open Problems.- Perceptron-Like Performance for Intersections of Halfspaces.- The Optimal PAC Algorithm.- The Budgeted Multi-armed Bandit Problem.
The Power of Selective Memory: Self-Bounded Learning of Prediction Suffix Trees

Prediction suffix trees (PST) provide a popular and effective tool for tasks such as compression, classification, and language modeling. In this paper we take a decision theoretic view of PSTs for the task of sequence prediction. Generalizing the notion of margin to PSTs, we present an online PST learning algorithm and derive a loss bound for it. The depth of the PST generated by this algorithm scales linearly with the length of the input. We then describe a self-bounded enhancement of our learning algorithm which automatically grows a bounded-depth PST. We also prove an analogous mistake-bound for the self-bounded algorithm. The result is an efficient algorithm that neither relies on a-priori assumptions on the shape or maximal depth of the target PST nor does it require any parameters. To our knowledge, this is the first provably-correct PST learning algorithm which generates a bounded-depth PST while being competitive with any fixed PST determined in hindsight.
The Hierarchical Hidden Markov Model: Analysis and Applications

We introduce, analyze and demonstrate a recursive hierarchical generalization of the widely used hidden Markov models, which we name Hierarchical Hidden Markov Models (HHMM). Our model is motivated by the complex multi-scale structure which appears in many natural sequences, particularly in language, handwriting and speech. We seek a systematic unsupervised approach to the modeling of such structures. By extending the standard Baum-Welch (forward-backward) algorithm, we derive an efficient procedure for estimating the model parameters from unlabeled data. We then use the trained model for automatic hierarchical parsing of observation sequences. We describe two applications of our model and its parameter estimation procedure. In the first application we show how to construct hierarchical models of natural English text. In these models different levels of the hierarchy correspond to structures on different length scales in the text. In the second application we demonstrate how HHMMs can be used to automatically identify repeated strokes that represent combination of letters in cursive handwriting.
Learning Algorithm for Enclosing Points in Bregmanian Spheres

We discuss the problem of finding a generalized sphere that encloses points originating from a single source. The points contained in such a sphere are within a maximal divergence from a center point. The divergences we study are known as the Bregman divergences which include as a special case both the Euclidean distance and the relative entropy. We cast the learning task as an optimization problem and show that it results in a simple dual form which has interesting algebraic properties. We then discuss a general algorithmic framework to solve the optimization problem. Our training algorithm employs an auxiliary function that bounds the dual’s objective function and can be used with a broad class of Bregman functions. As a specific application of the algorithm we give a detailed derivation for the relative entropy. We analyze the generalization ability of the algorithm by adopting margin-style proof techniques. We also describe and analyze two schemes of online algorithms for the case when the radius of the sphere is set in advance.
Ultraconservative Online Algorithms for Multiclass Problems

In this paper we study online classification algorithms for multiclass problems in the mistake bound model. The hypotheses we use maintain one prototype vector per class. Given an input instance, a multiclass hypothesis computes a similarity-score between each prototype and the input instance and then sets the predicted label to be the index of the prototype achieving the highest similarity. To design and analyze the learning algorithms in this paper we introduce the notion of ultracon-servativeness. Ultraconservative algorithms are algorithms that update only the prototypes attaining similarity-scores which are higher than the score of the correct label's prototype. We start by describing a family of additive ultraconservative algorithms where each algorithm in the family updates its prototypes by finding a feasible solution for a set of linear constraints that depend on the instantaneous similarity-scores. We then discuss a specific online algorithm that seeks a set of prototypes which have a small norm. The resulting algorithm, which we term MIRA (for Margin Infused Relaxed Algorithm) is ultraconservative as well. We derive mistake bounds for all the algorithms and provide further analysis of MIRA using a generalized notion of the margin for multiclass problems.
Smooth e-Intensive Regression by Loss Symmetrization

We describe new loss functions for regression problems along with an accompanying algorithmic framework which utilizes these functions. These loss functions are derived by symmetrization of margin-based losses commonly used in boosting algorithms, namely, the logistic loss and the exponential loss. The resulting symmetric logistic loss can be viewed as a smooth approximation to the e-insensitive hinge loss used in support vector regression. We describe and analyze two parametric families of batch learning algorithms for minimizing these symmetric losses. The first family employs an iterative log-additive update which can be viewed as a regression counterpart to recent boosting algorithms. The second family utilizes an iterative additive update step. We also describe and analyze online gradient descent (GD) and exponentiated gradient (EG) algorithms for the symmetric logistic loss. A byproduct of our work is a new simple form of regularization for boosting-based classification and regression algorithms. Our regression framework also has implications on classification algorithms, namely, a new additive update boosting algorithm for classification. We demonstrate the merits of our algorithms in a series of experiments.