nils-herrmann/clean_scirepeval huggingface dataset:
Experiments with a New Boosting Algorithm

In an earlier paper, we introduced a new "boosting" algorithm called AdaBoost which, theoretically, can be used to significantly reduce the error of any learning algorithm that con- sistently generates classifiers whose performance is a little better than random guessing. We also introduced the related notion of a "pseudo-loss" which is a method for forcing a learning algorithm of multi-label concepts to concentrate on the labels that are hardest to discriminate. In this paper, we describe experiments we carried out to assess how well AdaBoost with and without pseudo-loss, performs on real learning problems. We performed two sets of experiments. The first set compared boosting to Breiman's "bagging" method when used to aggregate various classifiers (including decision trees and single attribute- value tests). We compared the performance of the two methods on a collection of machine-learning benchmarks. In the second set of experiments, we studied in more detail the performance of boosting using a nearest-neighbor classifier on an OCR problem.
Game theory, on-line prediction and boosting

We study the close connections between game theory, on-line prediction and boosting. After a brief review of game theory, we describe an algorithm for learning to play repeated games based on the on-line prediction methods of Littlestone and Warmuth. The analysis of this algorithm yields a simple proof of von Neumann’s famous minmax theorem, as well as a provable method of approximately solving a game. We then show that the on-line prediction model is obtained by applying this gameplaying algorithm to an appropriate choice of game and that boosting is obtained by applying the same algorithm to the “dual” of this game.
Learning Sparse Multivariate Polynomials over a Field with Queries and Counterexamples

We consider the problem of learning a polynomial over an arbitrary eld F de ned on a set of boolean variables. We present the rst provably e ective algorithm for exactly identifying such polynomials using membership and equivalence queries. Our algorithm runs in time polynomial in n, the number of variables, and t, the number of nonzero terms appearing in the polynomial. The algorithm makes at most nt+ 2 equivalence queries, and at most (nt+ 1)(t 2 + 3t)=2 membership queries. Our algorithm is equally e ective for learning a generalized type of polynomial de ned on certain kinds of semilattices. We also present an extension of our algorithm for learning multilinear polynomials when the domain of each variable is the entire eld F .
Predicting Nearly As Well As the Best Pruning of a Decision Tree

Many algorithms for inferring a decision tree from data involve a two-phase process: First, a very large decision tree is grown which typically ends up “over-fitting” the data. To reduce over-fitting, in the second phase, the tree is pruned using one of a number of available methods. The final tree is then output and used for classification on test data.In this paper, we suggest an alternative approach to the pruning phase. Using a given unpruned decision tree, we present a new method of making predictions on test data, and we prove that our algorithm's performance will not be “much worse” (in a precise technical sense) than the predictions made by the best reasonably small pruning of the given decision tree. Thus, our procedure is guaranteed to be competitive (in terms of the quality of its predictions) with any pruning algorithm. We prove that our procedure is very efficient and highly robust.Our method can be viewed as a synthesis of two previously studied techniques. First, we apply Cesa-Bianchi et al.'s (1993) results on predicting using “expert advice” (where we view each pruning as an “expert”) to obtain an algorithm that has provably low prediction loss, but that is computationally infeasible. Next, we generalize and apply a method developed by Buntine (1990, 1992) and Willems, Shtarkov and Tjalkens (1993, 1995) to derive a very efficient implementation of this procedure.
Gambling in a rigged casino: The adversarial multi-armed bandit problem

In the multi-armed bandit problem, a gambler must decide which arm of K non-identical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has received much attention because of the simple model it provides of the trade-off between exploration (trying out each arm to find the best one) and exploitation (playing the arm believed to give the best payoff). Past solutions for the bandit problem have almost always relied on assumptions about the statistics of the slot machines. In this work, we make no statistical assumptions whatsoever about the nature of the process generating the payoffs of the slot machines. We give a solution to the bandit problem in which an adversary, rather than a well-behaved stochastic process, has complete control over the payoffs. In a sequence of T plays, we prove that the expected per-round payoff of our algorithm approaches that of the best arm at the rate O(T/sup -1/3/), and we give an improved rate of convergence when the best arm has fairly low payoff. We also consider a setting in which the player has a team of "experts" advising him on which arm to play; here, we give a strategy that will guarantee expected payoff close to that of the best expert. Finally, we apply our result to the problem of learning to play an unknown repeated matrix game against an all-powerful adversary.
The Minimal Disagreement Parity Problem as a Hard Satisfiability Problem

One common approach to generating hard instances for SAT algorithms is to encode other NP-complete problems into SAT. An obvious problem with this approach is that many NP-complete problems are trivially solvable in the average case [4]. One solution to this problem is to choose problem classes which are randomly self-reducible. As we show in section 3, randomly self-reducible problems are as hard in the average case as they are in the worst case. The minimal disagreement parity (MPD) problem is a simple example of a randomly self-reducible problem. Informally the problem is the following: given a set of sample input vectors and a set of sample parities, find the bits of the input vectors on which the parities were computed. In the absence of noise this problem has a known polynomial solution. In the presence of a moderate amount of noise (i.e., corruption of around 1/4 of the parity bits), however, there is reason to believe that the problem is quite hard.
Efficient algorithms for learning to play repeated games against computationally bounded adversaries

We examine the problem of learning to play various games optimally against resource-bounded adversaries, with an explicit emphasis on the computational efficiency of the learning algorithm. We are especially interested in providing efficient algorithms for games other than penny-matching (in which payoff is received for matching the adversary's action in the current round), and for adversaries other than the classically studied finite automata. In particular, we examine games and adversaries for which the learning algorithm's past actions may strongly affect the adversary's future willingness to "cooperate" (that is, permit high payoff), and therefore require carefully planned actions on the part of the learning algorithm. For example, in the game we call contract, both sides play O or 1 on each round, but our side receives payoff only if we play 1 in synchrony with the adversary; unlike penny-matching, playing O in synchrony with the adversary pays nothing. The name of the game is derived from the example of signing a contract, which becomes valid only if both parties sign (play 1).
On the Sample Complexity of Weakly Learning

In this paper, we study the sample complexity of weak learning. That is, we ask how many data must be collected from an unknown distribution in order to extract a small but significant advantage in prediction. We show that it is important to distinguish between those learning algorithms that output deterministic hypotheses and those that output randomized hypotheses. We prove that in the weak learning model, any algorithm using deterministic hypotheses to weakly learn a class of Vapnik-Chervonenkis dimension d(n) requires ? ) examples. In contrast, when randomized hypotheses are allowed, we show that ? (1) examples suffice in some cases. We then show that there exists an efficient algorithm using deterministic hypotheses that weakly learns against any distribution on a set of size d(n) with only O(d(n)2/3) examples. Thus for the class of symmetric Boolean functions over n variables, where the strong learning sample complexity is ? (n), the sample complexity for weak learning using deterministic hypotheses is ? ) and O(n2/3), and the sample complexity for weak learning using randomized hypotheses is ? (1). Next we prove the existence of classes for which the distribution-free sample size required to obtain a slight advantage in prediction over random guessing is essentially equal to that required to obtain arbitrary accuracy. Finally, for a class of small circuits, namely all parity functions of subsets of n Boolean variables, we prove a weak learning sample complexity of ?(n). This bound holds even if the weak learning algorithm is allowed to replace random sampling with membership queries, and the target distribution is uniform on {0, 1}n.
Predicting Nearly as Well as the Best Pruning of a Decision Tree

Many algorithms for inferring a decision tree from data involve a two-phase process: First, a very large decision tree is grown which typically ends up “over-fitting” the data. To reduce over-fitting, in the second phase, the tree is pruned using one of a number of available methods. The final tree is then output and used for classification on test data. 
 
In this paper, we suggest an alternative approach to the pruning phase. Using a given unpruned decision tree, we present a new method of making predictions on test data, and we prove that our algorithm‘s performance will not be “much worse” (in a precise technical sense) than the predictions made by the best reasonably small pruning of the given decision tree. Thus, our procedure is guaranteed to be competitive (in terms of the quality of its predictions) with {\it any} pruning algorithm. We prove that our procedure is very efficient and highly robust. 
 
Our method can be viewed as a synthesis of two previously studied techniques. First, we apply Cesa-Bianchi et al.‘s (1993) results on predicting using “expert advice” (where we view each pruning as an “expert”) to obtain an algorithm that has provably low prediction loss, but that is computationally infeasible. Next, we generalize and apply a method developed by Buntine (1990, 1992) and Willems, Shtarkov and Tjalkens (1993, 1995) to derive a very efficient implementation of this procedure.
A decision-theoretic generalization of on-line learning and an application to boosting

In the first part of the paper we consider the problem of dynamically apportioning resources among a set of options in a worst-case on-line framework. The model we study can be interpreted as a broad, abstract extension of the well-studied on-line prediction model to a general decision-theoretic setting. We show that the multiplicative weightupdate Littlestone Warmuth rule can be adapted to this model, yielding bounds that are slightly weaker in some cases, but applicable to a considerably more general class of learning problems. We show how the resulting learning algorithm can be applied to a variety of problems, including gambling, multiple-outcome prediction, repeated games, and prediction of points in R. In the second part of the paper we apply the multiplicative weight-update technique to derive a new boosting algorithm. This boosting algorithm does not require any prior knowledge about the performance of the weak learning algorithm. We also study generalizations of the new boosting algorithm to the problem of learning functions whose range, rather than being binary, is an arbitrary finite set or a bounded segment of the real line.
The study of dialect convergence and divergence: conceptual and methodological considerations

Dialect change can have several different manifestations. Among these, dialect convergence (dc) and dialect divergence (dd) noticeably affect the relationships between related dialects. Dc and dd have probably been present for as long as dialects have existed. Various historical developments, including the ‘modernisation’ of society, have left their mark on the very nature of dialects and have partly changed the dynamics of dc and dd; moreover, they have broadened them to dialect – standard language convergence. This chapter sets the stage for the various aspects of the study of dc and dd presented in this book, in that it both provides a general introduction and constitutes a springboard for the discussion of the themes and approaches which play a role in the individual chapters. As an introduction, the chapter presents the central terminology (section 2), provides the background information necessary for the interested non-specialist (section 3), sketches what we see as the main research methods (section 4), and binds together the issues featured in the various chapters (section 5). Definitions of the Key Concepts We will use the notion of ‘dialect’ to refer to a language variety which is used in a geographically limited part of a language area in which it is ‘roofed’ by a structurally related standard variety; a dialect typically displays structural peculiarities in several language components (cf. Chambers and Trudgill 1998: 5), though some of the authors in this book deal mainly with phonetic (or ‘accent’) features.
The role of interpersonal accommodation in a theory of language change

In this chapter, we will discuss the available evidence for Niedzielski and Giles' claim that ‘accommodation theory should be one of the major frameworks to which researchers in language change should turn’ (1996: 338). We will investigate the validity of a model of the implementation of structural language change which is intricately linked to verbal communication in face-to-face situations, and which, if only for this reason, is highly appealing. In its prototypical version, the model stipulates the following (hierarchically ordered) components. 1st component . In face-to-face communication between speakers with more traditional speech habits and those who use an innovative form, the former accommodates to the linguistic behaviour of the latter. Accommodation may consist of either the adoption of the new feature and/or the abandonment of the older one(s). It is the first case which may, in the long run, lead to the expansion of the innovation in geographical and social space. Thus, interpersonal accommodation is seen as the root of any structural convergence or advergence (as it should more correctly be called since in the prototypical case it is unilateral). However, interpersonal accommodation does not always lead to language change, since it is restricted to the interactional episode at hand, i.e. it does not always have a lasting effect on the accommodating speaker's linguistic ‘habits’. In order to have such an effect, two further steps are necessary. 2nd component . Short-term accommodation becomes long-term accommodation as soon as it permanently affects the accommodating speakers.
Being a "colono" and being "daitsch" in Rio Grande do Sul: Language choice and linguistic heterogeneity as a resource for

This paper investigates sociolinguistic styles as indexes to social identities in the context of the 'German' colonial zone in Rio Grande do Sul, Brazil. On the basis of a detailed sequential and stylistic analysis of three interactional episodes in a sindicato office it is shown that the deployment of sociolinguistic style is relevant for the display and ascription of identity-related features of ethnic belonging (daitsch) and positioning on the rural-urban continuum (colono). In particular, the paper focuses on language choice and code-switching/mixing.
Projection in Interaction and Projection in Grammar

In this paper, I argue that there are fundamental common features shared by interaction and grammar that suggest some kind of interdependence between the two and a nonautonomy of the language faculty; one of these fundamental common features is that of ‘projectability’. Human interaction rests on the possibility of projection; the grammars of human languages provide interlocutors with sedimentated and shared ways of organizing them. Empirical evidence for this view comes from structural homologies between action projection and grammatical projection. In particular, it is shown (on the basis of conversational examples from German) that in both cases: (1) the strength of the projective force can vary; (2) emerging gestalts can be framed by weakly projecting introductions; (3) projections can be interrupted; (4) full gestalts can be expanded; and (5) projections can be abandoned. The projectability of syntactic as well as sequence structures suggests an approach to syntax that takes into account the temporal unfolding of speech in time. It also suggests looking at the indeterminate areas between syntax and conversational structure in which the borderline between grammar and interaction can only be drawn on an ad hoc basis.
The construction of linguistic borders and the linguistic construction of borders

Contrary to an important explanatory principle of traditional dialectology, according to which (political) borders impede communication and thereby lead to the emergence of linguistic differences, I will argue that putative or factual linguistic differences are used for the social construction of (political) borders, and that existing (political) borders are symbolically reinforced by attracting linguistic differences. I will draw on various empirical sources, from ethnodialectological representations of dialect borders in Germany over studies on dialect change at the borders between Germany and neighbouring states (Netherlands, Switzerland, Austria) to studies on the border between the GDR and the FRG and its ideological implications.
Object Recognition using Geometric Properties and a variant of Boosting 1 )

This paper describes an approach for learning object descriptions as combinations of simple features using labeled still images. The contribution of this paper is a new method for constructing geometric relations of simple features with the LPBoost algorithm. A full search for relevant geometric relations between simple features is rather impossible because of the computation time required. We therefore use a greedy search strategy. In comparison, our recognition results are better than results using related approaches.
A Simple Feature Extraction for High Dimensional Image Representations

We investigate a method to find local clusters in low dimensional subspaces of high dimensional data, e.g. in high dimensional image descriptions. Using cluster centers instead of the full set of data will speed up the performance of learning algorithms for object recognition, and might also improve performance because overfitting is avoided. Using the Graz01 database, our method outperforms a current standard method for feature extraction from high dimensional image representations.
'Embedded language' and 'matrix language' in insertional language mixing: Some problematic cases

It is mostly assumed that the way in which languages may be combined within a syntactic unit is such that language A is dominant and language B (embedded language) is inserted (in the form of single words or of larger constituents) into the grammatical frame defined by language A (matrix language). The grammar of the matrix language provides the grammatical frame of the sentence as a whole, while the grammar of the embedded language is used only in complex insertions to determine the structure of the inserted constituent. We will provide empirical evidence that, on the one hand, simple insertions do not necessarily take on the morphology of the matrix language, but may be treated according to the rules of the embedded language; and, on the other hand, that the language of complex insertions does not necessarily follow the grammar of the embedded language. The ‘dominance’ of one language over another in intrasentential code-mixing seems rather to be a matter of gradience and can mean different things in different situations of language contact.
Learning Theory, 18th Annual Conference on Learning Theory, COLT 2005, Bertinoro, Italy, June 27-30, 2005, Proceedings

Learning to Rank.- Ranking and Scoring Using Empirical Risk Minimization.- Learnability of Bipartite Ranking  Stability and Generalization of Bipartite Ranking Algorithms.- Loss Bounds for Online Category Ranking.- Boosting.- Margin-Based Ranking Meets Boosting in the Middle.- Martingale Boosting.- The Value of Agreement, a New Boosting Algorithm.- Unlabeled Data, Multiclass Classification.- A PAC-Style Model for Learning from Labeled and Unlabeled Data.- Generalization Error Bounds Using Unlabeled Data.- On the Consistency of Multiclass Classification Methods.- Sensitive Error Correcting Output Codes.- Online Learning I.- Data Dependent Concentration Bounds for Sequential Prediction Algorithms.- The Weak Aggregating Algorithm and Weak  Tracking the Best of Many Experts.- Improved Second-Order Bounds for Prediction with Expert Advice.- Online Learning II.- Competitive Collaborative Learning.- Analysis of Perceptron-Based Active  A New Perspective on an Old Perceptron Algorithm.- Support Vector Machines.- Fast Rates for Support Vector Machines.- Exponential Convergence Rates in Classification.- General Polynomial Time Decomposition Algorithms.- Kernels and Embeddings.- Approximating a Gram Matrix for Improved Kernel-Based Learning.- Learning Convex Combinations of Continuously Parameterized Basic Kernels.- On the Limitations of Embedding Methods.- Leaving the Span.- Inductive Inference.- Variations on U-Shaped Learning.- Mind Change Efficient Learning.- On a Syntactic Characterization of Classification with a Mind Change Bound.- Unsupervised Learning.- Ellipsoid Approximation Using Random Vectors.- The Spectral Method for General Mixture Models.- On Spectral Learning of Mixtures of Distributions.- From Graphs to Manifolds - Weak and Strong Pointwise Consistency of Graph Laplacians.- Towards a Theoretical Foundation for Laplacian-Based Manifold Methods.- Generalization Bounds.- Permutation Tests for Classification.- Localized Upper and Lower Bounds for Some Estimation Problems.- Improved Minimax Bounds on the Test and Training Distortion of Empirically Designed Vector Quantizers.- Rank, Trace-Norm and Max-Norm.- Query Learning, Attribute Efficiency, Compression Schemes.- Learning a Hidden Hypergraph.- On Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions.- Unlabeled Compression Schemes for Maximum Classes.- Economics and Game Theory.- Trading in Markovian Price Models.- From External to Internal Regret.- Separation Results for Learning  Separating Models of Learning from Correlated and Uncorrelated Data.- Asymptotic Log-Loss of Prequential Maximum Likelihood Codes.- Teaching Classes with High Teaching Dimension Using Few  Open Problems.- Optimum Follow the Leader Algorithm.- The Cross Validation Problem.- Compute Inclusion Depth of a Pattern.