nils-herrmann/clean_scirepeval huggingface dataset:
On-line predictive linear regression

We consider the on-line predictive version of the standard problem of linear regression; the goal is to predict each consecutive response given the corresponding explanatory variables and all the previous observations. The standard treatment of prediction in linear regression analysis has two drawbacks: (1) the classical prediction intervals guarantee that the probability of error is equal to the nominal significance level $\varepsilon$, but this property per se does not imply that the long-run frequency of error is close to $\varepsilon$; (2) it is not suitable for prediction of complex systems as it assumes that the number of observations exceeds the number of parameters. We state a general result showing that in the on-line protocol the frequency of error for the classical prediction intervals does equal the nominal significance level, up to statistical fluctuations. We also describe alternative regression models in which informative prediction intervals can be found before the number of observations exceeds the number of parameters. One of these models, which only assumes that the observations are independent and identically distributed, is popular in machine learning but greatly underused in the statistical theory of regression.
Non-asymptotic calibration and resolution

We analyze a new algorithm for probability forecasting of binary labels, without making any assumptions about the way the data is generated. The algorithm is shown to be well calibrated and to have high resolution for big enough data sets and for a suitable choice of its parameter, a kernel on the Cartesian product of the forecast space [0,1] and the object space. Our results are non-asymptotic: we establish explicit inequalities for the performance of the algorithm.
Competing with wild prediction rules

We consider the problem of on-line prediction competitive with a benchmark class of continuous but highly irregular prediction rules. It is known that if the benchmark class is a reproducing kernel Hilbert space, there exists a prediction algorithm whose average loss over the first N examples does not exceed the average loss of any prediction rule in the class plus a “regret term” of O(N−1/2). The elements of some natural benchmark classes, however, are so irregular that these classes are not Hilbert spaces. In this paper we develop Banach-space methods to construct a prediction algorithm with a regret term of O(N−1/p), where p∈[2,∞) and p−2 reflects the degree to which the benchmark class fails to be a Hilbert space. Only the square loss function is considered.
On-Line Regression Competitive with Reproducing Kernel Hilbert Spaces

We consider the problem of on-line prediction of real-valued labels, assumed bounded in absolute value by a known constant, of new objects from known labeled objects. The prediction algorithm’s performance is measured by the squared deviation of the predictions from the actual labels. No stochastic assumptions are made about the way the labels and objects are generated. Instead, we are given a benchmark class of prediction rules some of which are hoped to produce good predictions. We show that for a wide range of infinite-dimensional benchmark classes one can construct a prediction algorithm whose cumulative loss over the first N examples does not exceed the cumulative loss of any prediction rule in the class plus $O(\sqrt{N})$; the main differences from the known results are that we do not impose any upper bound on the norm of the considered prediction rules and that we achieve an optimal leading term in the excess loss of our algorithm. If the benchmark class is “universal” (dense in the class of continuous functions on each compact set), this provides an on-line non-stochastic analogue for universally consistent prediction in non-parametric statistics. We use two proof techniques: one is based on the Aggregating Algorithm and the other on the recently developed method of defensive forecasting.
Algorithmic Learning in a Random World

Algorithmic Learning in a Random World describes recent theoretical and experimental developments in building computable approximations to Kolmogorov's algorithmic notion of randomness. Based on these approximations, a new set of machine learning algorithms have been developed that can be used to make predictions and to estimate their confidence and credibility in high-dimensional spaces under the usual assumption that the data are independent and identically distributed (assumption of randomness). Another aim of this unique monograph is to outline some limits of predictions: The approach based on algorithmic theory of randomness allows for the proof of impossibility of prediction in certain situations. The book describes how several important machine learning problems, such as density estimation in high-dimensional spaces, cannot be solved if the only assumption is randomness.
Introduction: Probability and Finance as a Game

1 Jean Ville (1910–1988) as a student at thé Ecole Normale Supérieure in Paris. His study of martingales helped inspire our framework for probability. We propose a framework for the theory and use of mathematical probability that rests more on game theory than on measure theory. This new framework merits attention on purely mathematical grounds, for it captures the basic intuitions of probability simply and effectively. It is also of philosophical and practical interest. It goes deeper into probability's conceptual roots than the established measure-theoretic framework, it is better adapted to many practical problems, and it clarifies the close relationship between probability theory and finance theory. From the viewpoint of game theory, our framework is very simple. Its most essential elements were already present in Jean Ville's 1939 book, ´ Etude critique de la notion de collectif, which introduced martingales into probability theory. Following Ville, we consider only two players. They alternate moves, each is immediately informed of the other's moves, and one or the other wins.
Defensive Forecasting for Linear Protocols

We consider a general class of forecasting protocols, called “linear protocols”, and discuss several important special cases, including multi-class forecasting. Forecasting is formalized as a game between three players: Reality, whose role is to generate objects and their labels; Forecaster, whose goal is to predict the labels; and Skeptic, who tries to make money on any lack of agreement between Forecaster’s predictions and the actual labels. Our main mathematical result is that for any continuous strategy for Skeptic in a linear protocol there exists a strategy for Forecaster that does not allow Skeptic’s capital to grow. This result is a meta-theorem that allows one to transform any constructive law of probability in a linear protocol into a forecasting strategy whose predictions are guaranteed to satisfy this law. We apply this meta-theorem to a weak law of large numbers in inner product spaces to obtain a version of the K29 prediction algorithm for linear protocols and show that this version also satisfies the attractive properties of proper calibration and resolution under a suitable choice of its kernel parameter, with no assumptions about the way the data is generated.
PRICING EUROPEAN OPTIONS WITHOUT PROBABILITY

It is well known that in the case where the stock price St is governed by the equation dSt/St = μdt + σdWt, any European option satisfying weak regularity conditions has a fair price (the Black—Scholes formula and its generalizations). We consider the case where no probabilistic assumptions are made about St; instead, we assume that the derivative security D which pays a dividend of (dSt/St) (the squared relative increase in the price of St) each instant dt is traded in the market. We prove that the “regular” European options have fair prices provided that both St and Dt (the price process of D) are continuous and the fractal dimensions of the graphs of St and Dt satisfy certain inequalities. Intuitively our assumptions are much weaker than the usual assumption dSt/St = μdt + σdWt.
Preface to this special issue

This issue of JMLR is devoted to the memory of Alexey Chervonenkis. Over the period of a dozen years between 1962 and 1973 he and Vladimir Vapnik created a new discipline of statistical learning theory—the foundation on which all our modern understanding of pattern recognition is based. Alexey was 28 years old when they made their most famous and original discovery, the uniform law of large numbers. In that short period Vapnik and Chervonenkis also introduced the main concepts of statistical learning theory, such as VCdimension, capacity control, and the Structural Risk Minimization principle, and designed two powerful pattern recognition methods, Generalised Portrait and Optimal Separating Hyperplane, later transformed by Vladimir Vapnik into Support Vector Machine—arguably one of the best tools for pattern recognition and regression estimation. Thereafter Alexey continued to publish original and important contributions to learning theory. He was also active in research in several applied fields, including geology, bioinformatics, medicine, and advertising. Alexey tragically died in September 2014 after getting lost during a hike in the Elk Island park on the outskirts of Moscow. Vladimir Vapnik suggested to prepare an issue of JMLR to be published at the first anniversary of the death of his long-term collaborator and close friend. Vladimir and the editors contacted a few dozen leading researchers in the fields of machine learning related to Alexey’s research interests and had many enthusiastic replies. In the end eleven papers were accepted. This issue also contains a first attempt at a complete bibliography of Alexey Chervonenkis’s publications. Simultaneously with this special issue will appear Alexey’s Festschrift (Vovk et al., 2015), to which the reader is referred for information about Alexey’s research, life, and death. The Festschrift is based in part on a symposium held in Pathos, Cyprus, in 2013 to celebrate Alexey’s 75th anniversary. Apart from research contributions, it contains Alexey’s reminiscences about his early work on statistical learning with Vladimir Vapnik, a reprint of their seminal 1971 paper, a historical chapter by R. M. Dudley, reminiscences of Alexey’s and Vladimir’s close colleague Vasily Novoseltsev, and three reviews of various measures of complexity used in machine learning (“Measures of Complexity” is both the name of the symposium and the title of the book). Among Alexey’s contributions to machine learning (mostly joint with Vladimir Vapnik) discussed in the book are:
How many strings are easy to predict?

It is well known in the theory of Kolmogorov complexity that most strings cannot be compressed; more precisely, only exponentially few (θ(2 n-m )) strings of length n can be compressed by m bits. This paper extends the 'incompressibility' property of Kolmogorov complexity to the 'unpredictability' property of predictive complexity. The 'unpredictability' property states that predictive complexity (defined as the loss suffered by a universal prediction algorithm working infinitely long) of most strings is close to a trivial upper bound (the loss suffered by a trivial minimax constant prediction strategy). We show that only exponentially few strings can be successfully predicted and find the base of the exponent.
Competitive on-line learning with a convex loss function

We consider the problem of sequential decision making under uncertainty in which the loss caused by a decision depends on the following binary observation. In competitive on-line learning, the goal is to design decision algorithms that are almost as good as the best decision rules in a wide benchmark class, without making any assumptions about the way the observations are generated. However, standard algorithms in this area can only deal with finite-dimensional (often countable) benchmark classes. In this paper we give similar results for decision rules ranging over an arbitrary reproducing kernel Hilbert space. For example, it is shown that for a wide class of loss functions (including the standard square, absolute, and log loss functions) the average loss of the master algorithm, over the first N observations, does not exceed the average loss of the best decision rule with a bounded norm plus O(N 1/2 ). Our proof technique is very different from the standard ones and is based on recent results about defensive forecasting. Given the probabilities produced by a defensive forecasting algorithm, which are known to be well calibrated and to have good resolution in the long run, we use the expected loss minimization principle to find a suitable decision.
Defensive Prediction with Expert Advice

The theory of prediction with expert advice usually deals with countable or finite-dimensional pools of experts. In this paper we give similar results for pools of decision rules belonging to an infinite-dimensional functional space which we call the Fermi–Sobolev space. For example, it is shown that for a wide class of loss functions (including the standard square, absolute, and log loss functions) the average loss of the master algorithm, over the first N steps, does not exceed the average loss of the best decision rule with a bounded Fermi–Sobolev norm plus O(N−−1/2). Our proof techniques are very different from the standard ones and are based on recent results about defensive forecasting. Given the probabilities produced by a defensive forecasting algorithm, which are known to be well calibrated and to have high resolution in the long run, we use the Expected Loss Minimization principle to find a suitable decision.
Game‐Theoretic Probability in Finance

In this introductory chapter, we sketch our game-theoretic approach to some basic topics of finance theory. We concentrate on how the Black-Scholes method for pricing and hedging a European option can be made purely game-theoretic, but begin with an examination of the apparently random behavior of stock-market prices, and we conclude with a discussion of informational efficiency. The usual derivation of the Black-Scholes formula for the price of an option relies on the assumption that the market price S(t) of the underlying security S follows a diffusion process. As we explain in the first two sections of this chapter, this stochastic assumption is used in two crucial ways: Taming the Market The diffusion model limits the wildness of fluctuations in S(t). This is the celebrated √ dt effect: the change in S(t) over an increment of time of positive length dt has the order of magnitude (dt) 1/2. This is wild enough, because (dt) 1/2 is much larger than dt when dt is small, but one can imagine much wilder fluctuations—say fluctuations of order (dt) 1/3. Averaging Market Changes The diffusion model authorizes the use of the law of large numbers on a relatively fine time scale. The model says that relative changes in S(t) over nonoverlapping time intervals are independent, no matter how small the intervals, and so by breaking a small interval of time [t 1 , t 2 ] into many even smaller intervals, we can use the law of large numbers to replace certain effects by their theoretical mean values. Our purely game-theoretic approach does not need the diffusion model for either of these purposes.
Game-theoretic versions of Kolmogorov’s strong law of large numbers

We prove two variants of Kolmogorov’s strong law of large numbers in a completely worst-case framework, eschewing any probabilistic assumptions. The first variant is an assertion about a game involving the Bookmaker predicting the values of unprobabilized random variables; in an intuitive sense it is much stronger than the usual strong law of large numbers for martingales. The second variant is an assertion about a security market. 1 Predictive strong law of large numbers In this section we consider the following perfect-information game between 3 players, the Bookmaker, the Statistician, and the Nature. The game proceeds in trials. At each trial i, i = 1, 2, . . ., the Bookmaker tries to predict the real number Xi the Nature is to produce at the end of the trial. His prediction consists of two numbers, Ei and Di ≥ 0; roughly, Ei is the Bookmaker’s expectation of Xi, and Di is his expectation of the accuracy Li := (Xi−Ei) (measured by the Brier scoring rule, see Dawid ) of the prediction Ei. ∗The research described in this publication was made possible in part by Grant No. MRS000 from the International Science Foundation.
Derandomizing Stochastic Prediction Strategies

AbstractIn this paper we continue study of the games of prediction with expert advice with uncountably many experts. A convenient interpretation of such games is to construe the pool of experts as one “stochastic predictor”, who chooses one of the experts in the pool at random according to the prior distribution on the experts and then replicates the (deterministic ) predictions of the chosen expert. We notice that if the stochastic predictor's total loss is at most L with probability at least p then the learner's loss can be bounded by cL + aln 
$$\frac{1}{{\text{P}}}$$
 for the usual constants c and a. This interpretation is used to revamp known results and obtain new results on tracking the best expert. It is also applied to merging overconfident experts and to fitting polynomials to data.
A Criterion for the Existence of Predictive Complexity for Binary Games

It is well known that there exists a universal (i.e., optimal to within an additive constant if allowed to work infinitely long) algorithm for lossless data compression (Kolmogorov, Levin). The game of lossless compression is an example of an on-line prediction game; for some other on-line prediction games (such as the simple prediction game) a universal algorithm is known not to exist. In this paper we give an analytic characterisation of those binary on-line prediction games for which a universal prediction algorithm exists.
A Universal Well-Calibrated Algorithm for On-line Classification

We study the problem of on-line classification in which the prediction algorithm is given a confidence level 1 - δ and is required to output as its prediction a range of labels (intuitively, those labels deemed compatible with the available data at the level δ) rather than just one label; as usual, the examples are assumed to be generated independently from the same probability distribution P. The prediction algorithm is said to be well-calibrated for P and δ if the long-run relative frequency of errors does not exceed δ almost surely w.r. to P. For well-calibrated algorithms we take the number of uncertain predictions (i.e., those containing more than one label) as the principal measure of predictive performance. The main result of this paper is the construction of a prediction algorithm which, for any (unknown) P and any δ: (a) makes errors independently and with probability 6 at every trial (in particular, is well-calibrated for P and δ); (b) makes in the long run no more uncertain predictions than any other prediction algorithm that is well-calibrated for P and δ; (c) processes example n in time O(log n).
On-line Prediction with Kernels and the Complexity Approximation Principle

The paper describes an application of Aggregating Algorithm to the problem of regression. It generalizes earlier results concerned with plain linear regression to kernel techniques and presents an on-line algorithm which performs nearly as well as any oblivious kernel predictor. The paper contains the derivation of an estimate on the performance of this algorithm. The estimate is then used to derive an application of the Complexity Approximation Principle to kernel methods.
Self-calibrating Probability Forecasting

In the problem of probability forecasting the learner's goal is to output, given a training set and a new object, a suitable probability measure on the possible values of the new object's label. An on-line algorithm for probability forecasting is said to be well-calibrated if the probabilities it outputs agree with the observed frequencies. We give a natural non-asymptotic formalization of the notion of well-calibratedness, which we then study under the assumption of randomness (the object/label pairs are independent and identically distributed). It turns out that, although no probability forecasting algorithm is automatically well-calibrated in our sense, there exists a wide class of algorithms for "multiprobability forecasting" (such algorithms are allowed to output a set, ideally very narrow, of probability measures) which satisfy this property; we call the algorithms in this class "Venn probability machines". Our experimental results demonstrate that a 1-Nearest Neighbor Venn probability machine performs reasonably well on a standard benchmark data set, and one of our theoretical results asserts that a simple Venn probability machine asymptotically approaches the true conditional probabilities regardless, and without knowledge, of the true probability measure generating the examples.
Testing Exchangeability On-Line

The majority of theoretical work in machine learning is done under the assumption of exchangeability: essentially, it is assumed that the examples are generated from the same probability distribution independently. This paper is concerned with the problem of testing the exchangeability assumption in the on-line mode: examples are observed one by one and the goal is to monitor on-line the strength of evidence against the hypothesis of exchangeability. We introduce the notion of exchangeability martingales, which are online procedures for detecting deviations from exchangeability; in essence, they are betting schemes that never risk bankruptcy and are fair under the hypothesis of exchangeability. Some specific exchangeability martingales are constructed using Transductive Confidence Machine. We report experimental results showing their performance on the USPS benchmark data set of hand-written digits (known to be somewhat heterogeneous); one of them multiplies the initial capital by more than 1018; this means that the hypothesis of exchangeability is rejected at the significance level 10-18.
A Game-Theoretic Explanation of the √(dt) Effect

The returns from a traded security typically have the order of magnitude √ dt. This can be explained by the absence of riskless opportunities for making money: any different order of magnitude would permit such opportunities. The explanation has been made rigorous in the standard measure-theoretic framework for continuous-time probability, but this requires the assumption that the security’s price process follows a particular stochastic process (usually fractional Brownian motion). This note makes the explanation rigorous without any stochastic assumption, using our purely game-theoretic framework for finance . This is a preliminary draft.
Kolmogorov's Contributions to the Foundations of Probability

Andrei Nikolaevich Kolmogorov was the foremost contributor to the mathematical and philosophical foundations of probability in the twentieth century, and his thinking on the topic is still potent today. In this article we first review the three stages of Kolmogorov's work on the foundations of probability: (1) his formulation of measure-theoretic probability, 1933; (2) his frequentist theory of probability, 1963; and (3) his algorithmic theory of randomness, 1965–1987. We also discuss another approach to the foundations of probability, based on martingales, which Kolmogorov did not consider.