nils-herrmann/clean_scirepeval huggingface dataset:
Online Region Prediction with Real Teachers

In the online prediction scenario the predictor’s task is to predict the label of an object given by Nature at each trial, based on the labels for the objects learned so far. At each trial Nature discloses the correct label for the current object, so the predictor is being taught. While this pure online scenario is convenient for theoretical studies, it is a poor model for many practical applications: the situation where the correct answers are given immediately after each prediction does not often occur in reality. In this work we suggest a more general scenario for online prediction, according to which correct answers may be given with some delay and not at every trial. We modify a particular class of region predictors, Transductive Confidence Machines, which have been proved to have several useful properties, to work in the new scenario, and find some sufficient conditions under which their rates of erroneous and uncertain predictions remain the same in the new online scenario as in the traditional one.
Just a clever substitute for measure zero ?

We are grateful that Professor Delbaen has reviewed our book. Seldom paid and often scorned, reviewers play an essential role in the dissemination and validation of new ideas. So we appreciate Professor Delbaen’s willingness to grapple with a book that mingles heuristic and mathematical reasoning more than he likes. His review is friendly in many respects, and we take pleasure in its acknowledgement that we have something important and interesting to say. The review also raises an interesting question about our book’s gametheoretic framework for probability theory (how broad a range of behaviors by the market would permit arbitrage in our option pricing games), and it gives us an opportunity to comment on an aspect of the book that we would like to improve (our exposition of nonstandard analysis). Unfortunately, the review discusses only a small fraction of the book’s results, the ones closest to the measure-theoretic approach that the book challenges, and it fails to warn the reader about this narrow focus. This distresses us, because readers of the review may be left with the impression that the book is much less innovative and far ranging than it actually is. Readers can easily draw the following conclusions:
Mondrian Confidence Machine

Mondrian Confidence Machine (MCM) is an on-line prediction algorithm that, given a split of all examples into a finite number of types k and for each type a significance level δk, outputs as its prediction the set of labels deemed possible at the level δk. MCM includes as special cases Transductive Confidence Machine (TCM) and Inductive Confidence Machine (ICM) and is designed to take care of such issues as different risks of false positive and false negative predictions, conditional inference, and a slow teacher. In this paper we generalize known results about TCM and ICM showing that each MCM is type-wise well-calibrated, in the sense that predictions at significance levels δk will be wrong with relative frequency at most δk for each type k in the long run. Our experimental results show advantages of MCM over the previously known algorithms.
On-line confidence machines are well-calibrated

Transductive Confidence Machine (TCM) and its computationally efficient modification, inductive confidence machine (ICM), are ways of complementing machine-learning algorithms with practically useful measures of confidence. We show that when TCM and ICM are used in the on-line mode, their confidence measures are well-calibrated, in the sense that predictive regions at confidence level 1-/spl delta/ will be wrong with relative frequency at most /spl delta/ (approaching /spl delta/ in the case of randomised TCM and ICM) in the long run. This is not just an asymptotic phenomenon: actually the error probability of randomised TCM and ICM is d at every trial and errors happen independently at different trials.
Inductive Confidence Machines for Regression

The existing methods of predicting with confidence give good accuracy and confidence values, but quite often are computationally inefficient. Some partial solutions have been suggested in the past. Both the original method and these solutions were based on transductive inference. In this paper we make a radical step of replacing transductive inference with inductive inference and define what we call the Inductive Confidence Machine (ICM); our main concern in this paper is the use of ICM in regression problems. The algorithm proposed in this paper is based on the Ridge Regression procedure (which is usually used for outputting bare predictions) and is much faster than the existing transductive techniques. The inductive approach described in this paper may be the only option available when dealing with large data sets.
Asymptotic Optimality of Transductive Confidence Machine

Transductive Confidence Machine (TCM) is a way of converting standard machine-learning algorithms into algorithms that output predictive regions rather than point predictions. It has been shown recently that TCM is well-calibrated when used in the on-line mode: at any confidence level 1 - ?, the long-run relative frequency of errors is guaranteed not to exceed ? provided the examples are generated independently from the same probability distribution P. Therefore, the number of "uncertain" predictive regions (i.e., those containing more than one label) becomes the sole measure of performance. The main result of this paper is that for any probability distribution P (assumed to generate the examples), it is possible to construct a TCM (guaranteed to be well-calibrated even if the assumption is wrong) that performs asymptotically as well as the best region predictor under P.
On a Review by V. N. Tutubalin

Valery Nikolaevich Tutubalin, of the Department of Probability Theory at Moscow University, has recently reviewed our book, Probability and Finance: It’s Only a Game! (Wiley, 2001). It is our understanding that his review will appear in Russian in “Teori vero tnoste i ee primeneni ”, the Russian journal that is regularly translated into English as Theory of Probability and Its Applications. Professor Tutubalin raises important questions about the range of usefulness of our book’s game-theoretic framework for probability. In this response, we discuss his questions in some detail. We have translated the review into English, and with Professor Tutubalin’s permission we have posted both the Russian text and our translation at the web site for our book, http://www.cs.rhul.ac.uk/~vovk/book/. This response can also be downloaded from there.
Comparing the Bayes and Typicalness Frameworks

When correct priors are known, Bayesian algorithms give optimal decisions, and accurate confidence values for predictions can be obtained. If the prior is incorrect however, these confidence values have no theoretical base - even though the algorithms' predictive performance may be good. There also exist many successful learning algorithms which only depend on the iid assumption. Often however they produce no confidence values for their predictions. Bayesian frameworks are often applied to these algorithms in order to obtain such values, however they can rely on unjustified priors. 
 
In this paper we outline the typicalness framework which can be used in conjunction with many other machine learning algorithms. The framework provides confidence information based only on the standard iid assumption and so is much more robust to different underlying data distributions. We show how the framework can be applied to existing algorithms. We also present experimental results which show that the typicalness approach performs close to Bayes when the prior is known to be correct. Unlike Bayes however, the method still gives accurate confidence values even when different data distributions are considered.
Kolmogorov’s Complexity Conception of Probability

Kolmogorov's goal in proposing his complexity conception of probability was to provide a better foundation for the applications of probability (as opposed to the theory of probability; he believed that his 1933 axioms were suucient for the theory of probability). The complexity conception was a natural development of Kolmogorov's earlier frequentist conception combined with (a) his conviction that only nite data sequences are of any interest in the applications of probability, and (b) Turing's discovery of the universal computing device. Besides the complexity conception itself , its developments by Martin-LL of, Levin et al will be brieey discussed; I will also list some advantages and limitations of Kolmogorov's complexity conception and the algorithmic theory of randomness in general.
Pattern Recognition and Density Estimation under the General i.i.d. Assumption

Statistical learning theory considers three main problems, pattern recognition, regression and density estimation. This paper studies solvability of these problems (mainly concentrating on pattern recognition and density estimation) in the "high-dimensional" case, where the patterns in the training and test sets are never repeated. We show that, assuming an i.i.d. data source but without any further assumptions, the problems of pattern recognition and regression can often be solved (and there are practically useful algorithms to solve them). On the other hand, the problem of density estimation, as we formalize it, cannot be solved under the general i.i.d. assumption, and additional assumptions are required.
Game-Theoretic Capital Asset Pricing in Continuous Time

We derive formulas for the performance of capital assets in continuous time from an efficient market hypothesis, with no stochastic assumptions and no assumptions about the beliefs or preferences of investors. Our efficient market hypothesis says that a speculator with limited means cannot beat a particular index by a substantial factor. Our results include a formula that resembles the classical CAPM formula for the expected simple return of a security or portfolio. This version of the article was essentially written in December 2001 but remains a working paper.
Loss Functions, Complexities, and the Legendre Transformation

The paper introduces a way of re-constructing a loss function from predictive complexity. We show that a loss function and expectations of the corresponding predictive complexity w.r.t. the Bernoulli distribution are related through the Legendre transformation. It is shown that if two loss functions specify the same complexity then they are equivalent in a strong sense. The expectations are also related to the so-called generalized entropy.
Probability and Finance: It's Only a Game!

Preface. Probability and Finance as a Game. PROBABILITY WITHOUT MEASURE.  The Bounded Strong Law of Large Numbers. Kolmogorov's Strong Law of Large Numbers. The Law of the Iterated Logarithm. The Weak Laws. Lindeberg's Theorem. The Generality of Probability Games.  Games for Pricing Options in Discrete Time. Games for Pricing Options in Continuous Time. The Generality of Game-Theoretic Pricing. Games for American Options. Games for Diffusion Processes. The Game-Theoretic Efficient-Market Hypothesis.
Computationally Efficient Transductive Machines

In this paper we propose a new algorithm for providing confidence and credibility values for predictions on a multi-class pattern recognition problem which uses Support Vector machines in its implementation. Previous algorithms which have been proposed to achieve this are very processing intensive and are only practical for small data sets. We present here a method which overcomes these limitations and can deal with larger data sets (such as the US Postal Service database). The measures of confidence and credibility given by the algorithm are shown empirically to reflect the quality of the predictions obtained by the algorithm, and are comparable to those given by the less computationally efficient method. In addition to this the overall performance of the algorithm is shown to be comparable to other techniques (such as standard Support Vector machines), which simply give flat predictions and do not provide the extra confidence/credibility measures.
Machine-Learning Applications of Algorithmic Randomness

Machine-LearningApplicationsofAlgorithmicRandomnessVolodyaovk,AlexGammerman,CraigSaundersComputerLearningResearchCentreandDepartmentofScienceRoyalHollowa,UniversitofLondon,Egham,SurreyTW200EX,Englandfvovk,alex,craigg@dcs.rhbnc.ac.ukAbstractMostmachinelearningalgorithmssharethefollowingdrawback:theyonlyoutputbarepredictionsbutnotthecon denceinthosepredictions.Inthe1960salgorithmicinfor-mationtheorysupplieduniversalmeasuresofcon dencebuttheseare,unfortunately,non-computable.Inthispap erwecombinetheideasofalgorithmicinformationtheorywiththetheoryofSupp ortVectormachinestoobtainpracticableapproximationsuni-versalmeasuresofcon dence.Weshowthatinsomestandardproblemsofpatternrecog-nitionourapproximationsworkell.1INTRODUCTIONTwoimp ortantdi erencesofmostmo dernmetho dsmachinelearning(suchasstatisticaltheory,seeVapnik[21],1998,orPACtheory)fromclassicalstatisticalmetho dsarethat:machinelearningmetho dspro ducebarepredic-tions,withoutestimatingcon denceinthosepre-dictions(unlike,eg,predictionoffutureobser-vationsintraditionalstatistics(Guttman[5],1970));manymachinelearningmetho dsaredesignedtowork(andtheirp erformanceisanalysed)un-derthegeneraliidassumption(unlikeclas-sicalparametricstatistics)andtheyareabletodealwithextremelyhigh-dimensionalhyp othesisspaces;cfVapnik[21](1998).Inthispap erwewillfurtherdeveloptheapproachofGammermanetal[4](1998)andSaunders[17Figure1:Ifthetrainingsetonlycontainsclear2sand7s,weouldliktoattachmucloercon dencethemiddleimagethantorightandleftones(1999),wherethegoalistoobtaincon dencesforpredictionsunderthegeneraliidassumptioninhigh-dimensionalsituations.Figure1demonstratesthede-sirabilityofcon dences.Themaincontributionthispap erisemb eddingtheapproachesofGammermanetal[4](1998)andSaunderset[17(1999)intoagen-eralschemebasedonthenotionofalgorithmicran-domness.Aswillb ecomeclearlater,theproblemofassigningcon dencestopredictionsiscloselyconnectedtheproblemofde ningrandomsequences.ThelatterproblemwassolvedbyKolmogorov[8](1965),whobasedhisde nitionontheexistenceUniver-salTuringMachine(thoughitb ecameclearthatKol-mogorov'sde nitiondo essolvetheproblemofde ningrandomsequencesonlyafterMartin-Lof 'spap er[15],1966);Kolmogorov'sde nitionmovedthenotionofrandomnessfromthegreyareasurroundingprobabil-itytheoryandstatisticstomathematicalcomputersci-ence.Kolmogorovb elievedhisnotionofrandomnesstob easuitablebasisforapplicationsofprobability.Unfor-tunately,fateideaasdi erentfromKol-mogorov's1933axioms(Kolmogorov[7],1933),which
Kolmogorov Complexity: Sources, Theory and Applications

1. UNIVERSALITYThe theory of Kolmogorov complexity is based on thediscovery, by Alan Turing in 1936, of the universal Turingmachine. After proposing the Turing machine as anexplanation of the notion of a computing machine, Turingfound that there exists one Turing machine which cansimulate any other Turing machine.Complexity, according to Kolmogorov, can be measuredby the length of the shortest program for a universal Turingmachine that correctly reproduces the observed data. It hasbeen shown that, although there are many universal Turingmachines(andthereforemanypossible ‘shortest’ programs),the corresponding complexities differ by at most an additiveconstant.The main thrust of the theory of Kolmogorov complexityis its ‘universality’; it strives to construct universal learningmethods based on universal coding methods. Thisapproach was originated by Solomonoff and made moreappealing to mathematicians by Kolmogorov. Typicallythese universal methods will be computable only in someweak sense. In applications, therefore, we can only hopeto approximate Kolmogorov complexity and related notions(such as randomnessdeﬁciency and algorithmic informationmentioned below). This special issue contains both materialon non-computable aspects of Kolmogorov complexity andmaterial on many fascinating applications based on differentways of approximating Kolmogorov complexity.2. BEGINNINGSAs we have already mentioned, the two main originators ofthe theory of Kolmogorovcomplexity were Ray Solomonoff(born 1926) and Andrei Nikolaevich Kolmogorov (1903–1987). The motivations behind their work were completelydifferent; Solomonoff was interested in inductive inferenceand artiﬁcial intelligence and Kolmogorov was interestedin the foundations of probability theory and, also, ofinformation theory. They arrived, nevertheless, at the samemathematical notion, which is now known as Kolmogorovcomplexity.In 1964 Solomonoff published his model of inductiveinference. He argued that any inference problem can bepresentedas a problemof extrapolatinga verylongsequenceof binary symbols; ‘given a very long sequence, representedby T, what is the probability that it will be followed by a
Complexity Approximation Principle

We propose a new inductive principle, which we call the complexity approximation principle (CAP). This principle is a natural generalization of Rissanen’s minimum description length (MDL) principle and Wallace’s minimum message length (MML) principle and is based on the notion of predictive complexity, a recent generalization of Kolmogorov complexity. Like the MDL principle, CAP can be regarded as an implementation of Occam’s razor.
Transduction with Confidence and Credibility

In this paper we follow the same general ideology as in [Gammerman et al., 1998], and describe a new transductive learning algorithm using Support Vector Machines. The algorithm presented provides confidence values for its predicted classifications of new examples. We also obtain a measure of "credibility" which serves as an indicator of the reliability of the data upon which we make our prediction. Experiments compare the new algorithm to a standard Support Vector Machine and other transductive methods which use Support Vector Machines, such as Vapnik's margin transduction. Empirical results show that the new algorithm not only produces confidence and credibility measures, but is comparable to, and sometimes exceeds the performance of the other algorithms.
Prequential probability: principles and properties

Forcaster has to predict, sequentially, a string of uncertain quantities (X1, X2, .. .), whose values are determined and revealed, one by one, by Nature. Various criteria may be proposed to assess Forecaster's empirical performance. The weak prequential principle requires that such a criterion should depend on Forecaster's behaviour or strategy only through the actual forecasts issued. A wide variety of appealing criteria are shown to respect this principle. We further show that many such criteria also obey the strong prequential principle, which requires that, when both
Learning by Transduction

We describe a method for predicting a classification of an object given classifications of the objects in the training set, assuming that the pairs object/classification are generated by an i.i.d. process from a continuous probability distribution. Our method is a modification of Vapnik's support-vector machine; its main novelty is that it gives not only the prediction itself but also a practicable measure of the evidence found in support of that prediction. We also describe a procedure for assigning degrees of confidence to predictions made by the support vector machine. Some experimental results are presented, and possible extensions of the algorithms are discussed.
Ridge Regression Learning Algorithm in Dual Variables

In this paper we study a dual version of the Ridge Regression procedure. It allows us to perform non-linear regression by constructing a linear regression function in a high dimensional feature space. The feature space representation can result in a large increase in the number of parameters used by the algorithm. In order to combat this “curse of dimensionality”, the algorithm allows the use of kernel functions, as used in Support Vector methods. We also discuss a powerful family of kernel functions which is constructed using the ANOVA decomposition method from the kernel corresponding to splines with an infinite number of nodes. This paper introduces a regression estimation algorithm which is a combination of these two elements: the dual version of Ridge Regression is applied to the ANOVA enhancement of the infinitenode splines. Experimental results are then presented (based on the Boston Housing data set) which indicate the performance of this algorithm relative to other algorithms.
Universal portfolio selection

A typical problem in portfolio selection in stock markets is that it is not clear which of the many available strategies should be used. We apply a general algorithm of prediction with expert advice (the Aggregating Algorithm) to two different idealizations of the stock market. One is the well-known game introduced by Cover in connection with his “universal portfolio” algorithm; the other is a more realistic modification of Cover’s game introduced in this paper, where market’s participants are allowed to take “short positions”, so that the algorithm may be applied to currency and futures markets. Besides applying the Aggregating Algorithm to a countable (or finite) family of arbitrary investment strategies, we also apply it, in the case of Cover’s game, to the uncountable family of “constant rebalanced portfolios” considered by Cover. We generalize Cover’s worst-case bounds for his “universal portfolio” algorithm (which can be regarded as a special case of the Aggregating Algorithm corresponding to learning rate 1) to the case of learning rates not exceeding 1. Finally, we discuss a general approach to designing investment strategies in which, instead of making statistical or other assumptions about the market, natural assumptions of computability are made about possible investment strategies; this approach leads to natural extensions of the notion of Kolmogorov complexity.
Competitive On-line Linear Regression

We apply a general algorithm for merging prediction strategies (the Aggregating Algorithm) to the problem of linear regression with the square loss; our main assumption is that the response variable is bounded. It turns out that for this particular problem the Aggregating Algorithm resembles, but is slightly different from, the well-known ridge estimation procedure. From general results about the Aggregating Algorithm we deduce a guaranteed bound on the difference between our algorithm's performance and the best, in some sense, linear regression function's performance. We show that the AA attains the optimal constant in our bound, whereas the constant attained by the ridge regression procedure in general can be 4 times worse.
Derandomizing stochastic prediction strategies

In 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}{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.
Learning about the Parameter of the Bernoulli Model

We consider the problem of learning as much information as possible about the parameter?of the Bernoulli model {P????0, 1} from the statistical datax?{0, 1}n,n?1 being the sample size. Explicating this problem in terms of the Kolmogorov complexity and Rissanen's minimum description length principle, we construct a computable point estimator which (a) extracts from x all information it contains about?, and (b) discards all sample noise inx. Our result is closely connected with Rissanen's theorem about the optimality of his scheme of coding statistical data.