Partners

Abstract:
We consider the notion of prediction functions (or predictors) studied before in the context of randomness and stochasticity by Ko, and later by Ambos‐Spies and others. Predictor is a total computable function which tries to predict bits of some infinite binary sequence. The prediction error is defined as the limit of the number of incorrect answers divided by the number of answers given so far. We discuss indefiniteness of prediction errors for weak 1‐generics and show that this phenomenon affects certain c.e. sequences as well. On the other hand, a notion of optimal predictor is considered. It is shown that there is a sequence for which increasingly better predictors exist but for which no predictor is optimal.

Abstract:
Understanding when learning is possible is a fundamental task in the theory of machine learning. However, many characterizations known from the literature deal with abstract learning as a mathematical object and ignore the crucial question: when can learning be implemented as a computer program? We address this question for universal online learning, a generalist theoretical model of online binary classification, recently characterized by Bousquet et al. (STOC´21). In this model, there is no hypothesis fixed in advance; instead, Adversary—playing the role of Nature—can change their mind as long as local consistency with the given class of hypotheses is maintained. We require Learner to achieve a finite numer of mistakes while using a strategy that can be implemented as a computer program. We show that universal online learning does not imply computable universal online learning, even if the class of hypotheses is relatively easy from a computability- theoretic perspective. We then study the agnostic variant of computable universal online learning and provide an exact characterization of classes that are learnable in this sense. We also consider a variant of proper universal online learning and show exactly when it is possible. Together, our results give a more realistic perspective on the existing theory of online binary classification and the related problem of inductive inference

Abstract:
A novel kind of a negative result is presented for the problem of computable prediction. A non-stationary binary stochastic process is constructed for which almost surely no effective method of prediction achieves the infimum of prediction errors defined as the normalized Hamming distance between the sequence of predictions and the realization of the process. Yet it is shown that this process may be effectively predicted almost surely up to an arbitrarily small error since the infimum of prediction errors is zero.