This editorial contains Vladimir V’yugin’s short biography and a selective review of his contributions to several areas of mathematics, computer science, and their applications.

Abstract The topic of this paper is testing the assumption of exchangeability, which is the standard assumption in mainstream machine learning. The common approaches are online testing by betting (such as conformal testing) and the older batch testing using p-values (as in classical hypothesis testing). The approach of this paper is intermediate in that we are interested in batch testing by betting; as a result, p-values are replaced by e-values. As a first step in this direction, this paper concentrates on the Markov model as alternative. The null hypothesis of exchangeability is formalized as a Kolmogorov-type compression model, and the Bayes mixture of the Markov model w.r. to the uniform prior is taken as simple alternative hypothesis. Using e-values instead of p-values leads to a computationally efficient testing procedure. Two appendixes discuss connections with the algorithmic theory of randomness; in particular, the test proposed in this paper can be interpreted as a poor man’s version of Kolmogorov’s deficiency of randomness.

This paper discusses a counterpart of conformal prediction for e-values, conformal e-prediction . Conformal e-prediction is conceptually simpler and had been developed in the 1990s as a precursor of conformal prediction. When conformal prediction emerged as result of replacing e-values by p-values, it seemed to have important advantages over conformal e-prediction without obvious disadvantages. This paper re-examines relations between conformal prediction and conformal e-prediction systematically from a modern perspective. Conformal e-prediction has advantages of its own, such as the ease of designing conditional conformal e-predictors and the guaranteed validity of cross-conformal e-predictors (whereas for cross-conformal predictors validity is only an empirical fact and can be broken with excessive randomization). Even where conformal prediction has clear advantages, conformal e-prediction can often emulate those advantages, more or less successfully. • Re-examination of relations between conformal prediction and conformal e-prediction. • Design of conditional conformal e-predictors. • Guaranteed validity of cross-conformal e-predictors. • Design of criteria of predictive efficiency for conformal e-predictors. • Law of the iterated logarithm for e-prediction.

There is a useful counterpart of conformal prediction for e-values, called conformal e-prediction . Conformal prediction can serve as basis for testing the assumption of exchangeability, leading to conformal testing . Similarly, conformal e-prediction can also serve as basis for testing exchangeability. The resulting conformal e-testing looks very different from but inherits some strengths of conformal testing; it even has some advantages over conformal testing. In this paper we discuss systematically both strengths and limitations of conformal e-testing.

Conformal predictive systems are a recent modification of conformal predictors that output, in regression problems, probability distributions for labels of test observations rather than set predictions. The extra information provided by conformal predictive systems may be useful, e.g., in decision making problems. Conformal predictive systems inherit the relative computational inefficiency of conformal predictors. In this paper we discuss two computationally efficient versions of conformal predictive systems, which we call split conformal predictive systems and cross-conformal predictive systems. The main advantage of split conformal predictive systems is their guaranteed validity, whereas for cross-conformal predictive systems validity only holds empirically and in the absence of excessive randomization. The main advantage of cross-conformal predictive systems is their greater predictive efficiency.

This paper applies conformal prediction to derive predictive distributions that are valid under a nonparametric assumption. Namely, we introduce and explore predictive distribution functions that always satisfy a natural property of validity in terms of guaranteed coverage for IID observations. The focus is on a prediction algorithm that we call the Least Squares Prediction Machine (LSPM). The LSPM generalizes the classical Dempster–Hill predictive distributions to nonparametric regression problems. If the standard parametric assumptions for Least Squares linear regression hold, the LSPM is as efficient as the Dempster–Hill procedure, in a natural sense. And if those parametric assumptions fail, the LSPM is still valid, provided the observations are IID.

For the prediction with expert advice setting, we consider methods to construct algorithms that have low adaptive regret. The adaptive regret of an algorithm on a time interval $[t_1,t_2]$ is the loss of the algorithm minus the loss of the best expert over that interval. Adaptive regret measures how well the algorithm approximates the best expert locally, and so is different from, although closely related to, both the classical regret, measured over an initial time interval $[1,t]$, and the tracking regret, where the algorithm is compared to a good sequence of experts over $[1,t]$. We investigate two existing intuitive methods for deriving algorithms with low adaptive regret, one based on specialist experts and the other based on restarts. Quite surprisingly, we show that both methods lead to the same algorithm, namely Fixed Share, which is known for its tracking regret. We provide a thorough analysis of the adaptive regret of Fixed Share. We obtain the exact worst-case adaptive regret for Fixed Share, from which the classical tracking bounds follow. We prove that Fixed Share is optimal for adaptive regret: the worst-case adaptive regret of any algorithm is at least that of an instance of Fixed Share.

This paper studies theoretically and empirically a method of turning machine-learning algorithms into probabilistic predictors that automatically enjoys a property of validity (perfect calibration) and is computationally efficient. The price to pay for perfect calibration is that these probabilistic predictors produce imprecise (in practice, almost precise for large data sets) probabilities. When these imprecise probabilities are merged into precise probabilities, the resulting predictors, while losing the theoretical property of perfect calibration, are consistently more accurate than the existing methods in empirical studies.

Conformal prediction is a method of producing prediction sets that can be applied on top of a wide range of prediction algorithms. The method has a guaranteed coverage probability under the standard IID assumption regardless of whether the assumptions (often considerably more restrictive) of the underlying algorithm are satisfied. However, for the method to be really useful it is desirable that in the case where the assumptions of the underlying algorithm are satisfied, the conformal predictor loses little in efficiency as compared with the underlying algorithm (whereas being a conformal predictor, it has the stronger guarantee of validity). In this paper we explore the degree to which this additional requirement of efficiency is satisfied in the case of Bayesian ridge regression; we find that asymptotically conformal prediction sets differ little from ridge regression prediction intervals when the standard Bayesian assumptions are satisfied.

In this paper we apply Conformal Prediction (CP) to the k-Nearest Neighbours Regression (k-NNR) algorithm and propose ways of extending the typical nonconformity measure used for regression so far. Unlike traditional regression methods which produce point predictions, Conformal Predictors output predictive regions that satisfy a given confidence level. The regions produced by any Conformal Predictor are automatically valid, however their tightness and therefore usefulness depends on the nonconformity measure used by each CP. In effect a nonconformity measure evaluates how strange a given example is compared to a set of other examples based on some traditional machine learning algorithm. We define six novel nonconformity measures based on the k-Nearest Neighbours Regression algorithm and develop the corresponding CPs following both the original (transductive) and the inductive CP approaches. A comparison of the predictive regions produced by our measures with those of the typical regression measure suggests that a major improvement in terms of predictive region tightness is achieved by the new measures.

We construct prediction intervals for the linear regression model with IID errors with a known distribution, not necessarily Gaussian. The coverage probability of our prediction intervals is equal to the nominal confidence level not only unconditionally but also conditionally given a natural sigma-algebra of invariant events. This implies, in particular, the perfect calibration of our prediction intervals in the on-line mode of prediction.

Ovarian cancer is characterized by vague, non-specific symptoms, advanced stage at diagnosis and poor overall survival. A nested case control study was undertaken on stored serial serum samples from women who developed ovarian cancer and healthy controls (matched for serum processing and storage conditions as well as attributes such as age) in a pilot randomized controlled trial of ovarian cancer screening. The unique feature of this study is that the women were screened for up to 7 years. The serum samples underwent prefractionation using a reversed-phase batch extraction protocol prior to MALDI-TOF MS data acquisition. Our exploratory analysis shows that combining a single MS peak with CA125 allows statistically significant discrimination at the 5% level between cases and controls up to 12 months in advance of the original diagnosis of ovarian cancer. Such combinations work much better than a single peak or CA125 alone. This paper demonstrates that mass spectra from the low molecular weight serum proteome carry information useful for early detection of ovarian cancer. The next step is to identify the specific biomarkers that make early detection possible.

We show that the Brier game of prediction is mixable and find the optimal learning rate and substitution function for it. The resulting prediction algorithm is applied to predict results of football and tennis matches. The theoretical performance guarantee turns out to be rather tight on these data sets, especially in the case of the more extensive tennis data.

Conformal prediction (CP) is a method that can be used for complementing the bare predictions produced by any traditional machine learning algorithm with measures of confidence. CP gives good accuracy and confidence values, but unfortunately it is quite computationally inefficient. This computational inefficiency problem becomes huge when CP is coupled with a method that requires long training times, such as neural networks. In this paper we use a modification of the original CP method, called inductive conformal prediction (ICP), which allows us to a neural network confidence predictor without the massive computational overhead of CP The method we propose accompanies its predictions with confidence measures that are useful in practice, while still preserving the computational efficiency of its underlying neural network.

Recent advances in machine learning make it possible to design efficient prediction algorithms for data sets with huge numbers of parameters. This paper describes a new technique for "hedging" the predictions output by many such algorithms, including support vector machines, kernel ridge regression, kernel nearest neighbours, and by many other state-of-the-art methods. The hedged predictions for the labels of new objects include quantitative measures of their own accuracy and reliability. These measures are provably valid under the assumption of randomness, traditional in machine learning: the objects and their labels are assumed to be generated independently from the same probability distribution. In particular, it becomes possible to control (up to statistical fluctuations) the number of erroneous predictions by selecting a suitable confidence level. Validity being achieved automatically, the remaining goal of hedged prediction is efficiency: taking full account of the new objects' features and other available information to produce as accurate predictions as possible. This can be done successfully using the powerful machinery of modern machine learning.

We are very grateful to all discussants for their interest in our article and their comments. We will organize our response by major topics raised by them. References to our article's bibliography will be given as e.g. [A3], and references to the discussion's bibliography as e.g. [D26]. All formula numbers, such as (3), refer to the formulas in the article. As we say in the article, the two most important properties expected from confidence predictors are validity (they must tell the truth) and efficiency (the truth must be as informative as possible). Conformal predictors are automatically valid, so there is little to discuss here, but so far achieving efficiency has been an art, to a large degree, and Alexey Chervonenkis, Phil Long and Sally McClean comment on this aspect of conformal prediction. Indeed, as Prof. Chervonenkis notices, the article does not contain any theoretical results about efficiency. Such a result appears as Theorem 3.1 in our book [A3]. We use a non-conformity measure based on the nearest neighbours procedure to obtain a conformal predictor whose efficiency asymptotically approaches that of the Bayes-optimal confidence predictor. (Remember that the Bayes-optimal confidence predictor is optimized under the true probability distribution, which is unknown to the Predictor.) This result only applies to the case of classification, and it is asymptotic. Nevertheless, it is our only step towards a ‘more principled way of designing good measures of strangeness’, as Prof. McClean puts it. Her question suggests the desirability of such more principled ways; we agree and would very much welcome further results in this direction.

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.

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.

We briefly discuss the origins, main ideas and principal applications of the theory of Kolmogorov complexity.

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.

Article Free Access Share on Universal portfolio selection Authors: V. Vovk Department of Computer Science, Royal Holloway, University of London, Egham, Surrey TW20 0EX, UK Department of Computer Science, Royal Holloway, University of London, Egham, Surrey TW20 0EX, UKView Profile , C. Watkins Department of Computer Science, Royal Holloway, University of London, Egham, Surrey TW20 0EX, UK Department of Computer Science, Royal Holloway, University of London, Egham, Surrey TW20 0EX, UKView Profile Authors Info & Claims COLT' 98: Proceedings of the eleventh annual conference on Computational learning theoryJuly 1998 Pages 12–23https://doi.org/10.1145/279943.279947Published:24 July 1998Publication History 52citation1,377DownloadsMetricsTotal Citations52Total Downloads1,377Last 12 Months113Last 6 weeks21 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We give a new interpretation of the games of prediction with expert advice.Instead of a pool of experts we consider only one Ystochsstic predictor" and 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 + a In f 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. AGGREGATING ALGORITHMOur learning protocol is as follows.The learner interacts with the stochastic predictor and the nature in the following way.At each trial t, t = 1,2,. ..:l The stochastic predictor makes a random prediction ('t in a fixed prediction space I'.

Article Learning an optimal decision strategy in an influence diagram with latent variables Share on Author: V. G. Vovk Department of Computer Science, Royal Holloway, University of London Egham, Surrey TW20 0EX, UK Department of Computer Science, Royal Holloway, University of London Egham, Surrey TW20 0EX, UKView Profile Authors Info & Claims COLT '96: Proceedings of the ninth annual conference on Computational learning theoryJanuary 1996 Pages 110–121https://doi.org/10.1145/238061.238076Online:01 January 1996Publication History 0citation291DownloadsMetricsTotal Citations0Total Downloads291Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We consider the following problem. At each point of discrete time the learner must make a prediction; he is given the predictions made by a pool of experts. Each prediction and the outcome, which is disclosed after the learner has made his prediction, determine the incurred loss. It is known that, under weak regularity, the learner can ensure that his cumulative loss never exceeds cL+a ln n, where c and a are some constants, n is the size of the pool, and L is the cumulative loss incurred by the best expert in the pool. We find the set of those pairs (c, a) for which this is true.]1998 Academic Press 1. MAIN RESULT Our learning protocol is as follows. We consider a learner who acts in the following environment. There are a pool of n experts and the nature, which interact with the learner in the following way. At each trial t, t=1, 2,...: 1. Each expert i, i=1,..., n, makes a prediction #t(i) # 1,

We describe and compare two paradigms of on-line learning, which we call Bayesian and Popperian. In this paper the Bayesian paradigm is represented by Littlestone and Warmuth's Weighted Majority Algorithm, and the Popperian paradigm is represented by Rivest and Schapire's reset-free algorithm for exact learning of finite automata with membership and equivalence queries. Both algorithms are applied to the problem of optimal control of a finite-state plant in a finite-state environment. The advantage of the control strategy based on the Weighted Majority Algorithm is its robustness and better performance (actually, its performance is nearly optimal in the class of deterministic control strategies), and the advantage of the control strategy based on Rivest and Schapire's algorithm is its computational efficiency.