2.1. Sequential Prediction

A prediction game consists of an infinite history of events, a pool Π of prediction strategies, and a loss function ℓ. The prototypical game is the binary probabilistic prediction game, where the events are binary (elements of {0, 1}), the predictions issued by the strategies are probabilities (values in [0, 1]), and the loss function is the logarithmic loss function (specified below).

Each round n of the game, every strategy P submits a prediction pred_n(P). Then the event y_n, the nth element of the history, is revealed. Finally, each strategy’s prediction is charged with a real-valued loss ℓ(pred_n, y_n) for this round, which quantifies how much the prediction was off.

The most basic example of a loss function is the absolute loss function, defined by ${\ell }_{\mathrm{abs}}\left(\mathrm{pred},y\right)=\left|\mathrm{pred}-y\right|$. Important, among other things, for its strong connection to Bayesian prediction (sec. 3.1 below) is the logarithmic or log-loss function defined by

${\ell }_{\log }\left(\mathrm{pred},y\right)=\{\begin{array}{cc}-\ln (1-\mathrm{pred})& \text{if }y=0\\ -\mathrm{ln pred}& \text{if }y=1\end{array}\text{.}$

For a given loss function, the cumulative loss of P by the conclusion of round n is the sum ${\mathrm{Loss}}_n\left(P\right)≔{\sum }_{i=1}^n\ell \left({\mathrm{pred}}_n\left(P\right),y_n\right)$. The loss rate loss_n(P) of P by n is the average ${\mathrm{Loss}}_n\left(P\right)/n$ of its losses up to n.

2.2. The Goal: An Optimal Strategy

Given a pool Π of strategies, we aim to design a metainductive strategy MI that, having access to the predictions of all the other strategies, predicts in such a way that it is optimal with respect to Π. That is, by following MI, we will always do about as good as, in hindsight, we possibly could have done—given that the strategies in Π represent what we could have done. Here ‘always’ means: on every single history of events.

What it means for a metainductive strategy to be ‘about as successful’ as any other strategy we make precise in terms of the divergence between MI’s loss rate and the quantity ${\mathrm{minloss}}_n≔{\min }_{P\in \Pi \cup \left\{\mathrm{MI}\right\}}{\mathrm{loss}}_n\left(P\right)$, the minimum loss rate among all the strategies by round n. Specifically, we seek a function f that depends on n and inevitably also on the size $K≔\left|\Pi \right|$ of the pool of strategies, such that for all rounds n,

$\begin{array}{}\text{(1)}& {\mathrm{loss}}_n\left(\mathrm{MI}\right)\le {\mathrm{minloss}}_n+f\left(n,K\right)\text{.}\end{array}$

A minimal requirement is that f is such that it entails long-run convergence,

$\begin{array}{}\text{(2)}& \underset{n\to \infty }{\lim }\left({\mathrm{loss}}_n\left(\mathrm{MI}\right)-{\mathrm{minloss}}_n\right)=0\text{,}\end{array}$

for which it at least needs to be decreasing in n. But as we will see below, there actually exist prediction algorithms that achieve bounds (1) for f that decrease in n at a very fast rate, giving strong short-run guarantees.

3.1. Step 1: The Analytical Optimality of Metainduction

A general type of metainductive strategy is the weighted-average strategy waMI, specified by

$\begin{array}{}\text{(3)}& {\mathrm{pred}}_{n+1}\left(\mathrm{waMI}\right)≔\sum _{P\in \Pi }{w}_n\left(P\right)\cdot {\mathrm{pred}}_{n+1}\left(P\right)\text{.}\end{array}$

Here the weight function w_n assigns a weight to each strategy P based on its past success.

An important example of a weighted-average strategy in the probabilistic binary prediction game, for the particular choice of the log-loss function, is the Bayesian strategy BayMI, which updates its weights via Bayes’s rule. It is given by

$\begin{array}{}\text{(4)}& w_n\left(P\right)=\frac{w_0\left(P\right)\cdot \exp (-{\mathrm{Loss}}_n\left(P\right))}{Z}\text{,}\end{array}$

with the normalization term $Z={\sum }_{P\in \Pi }{w}_0\left(P\right)\cdot \exp (-{\mathrm{Loss}}_n\left(P\right))$. Here w ₀ is some prior probability assignment or initial weight function over Π. With a uniform initial weight assignment, where $w_0\left(P\right)=1/K$ for each $P\in \Pi$, assignment (4) simplifies to

$\begin{array}{}\text{(5)}& w_n\left(P\right)=\frac{\exp (-{\mathrm{Loss}}_n\left(P\right))}{Z}\text{,}\end{array}$

so that the weights depend on the strategies’ performance only.

Now one can derive that BayMI, for the log-loss function, satisfies, for each $P\in \Pi$,

$\begin{array}{}\text{(6)}& {\mathrm{Loss}}_n\left(\mathrm{BayMI}\right)\le -\ln w_0\left(P\right)+{\mathrm{Loss}}_n\left(P\right)\text{.}\end{array}$

Choosing again a uniform w ₀, this translates in the short-run optimality bound

$\begin{array}{}\text{(7)}& {\mathrm{loss}}_n\left(\mathrm{BayMI}\right)\le {\mathrm{minloss}}_n+\frac{\ln K}{n}\text{.}\end{array}$

That is, for this game we can achieve bound (1) with f of order $1/n$. What is more, it turns out to be possible, for a wider class of loss functions, to design strategies that explicitly mimic the Bayesian strategy for the log-loss function, for these loss functions, in order to achieve a similar bound. These are the strongest possible bounds for any game, but for an even wider class of loss functions that also includes the absolute loss function, it is still possible to define metainductive strategies—specifically, exponentially weighted strategies that can also be seen as generalizations of the Bayesian strategy—with bounds of order $1/\sqrt{n}$.

In sum, for a wide class of games there exist metainductive strategies that are optimal in a very strong sense. Moreover, these optimal strategies predict by combining weighted predictions of all the other strategies in the pool, where the weights depend on these strategies’ past performance—and in the case of uniform weights, on their past performance only. In particular, the strategy in the pool that so far has been performing best receives the largest weight: it is in that sense that we say that the metainductive strategy favors the most successful strategy so far. Thus, the first step of Schurz’s argument is that

3.2. Step 2: The Empirical Success of Object Induction

The second step is the empirical observation that object induction has turned out to be the most successful prediction strategy so far. In Sterkenburg (Reference Sterkenburg2019), I argued that the relevant perspective here is to view the object-inductive or scientific method as competing with a number of alternative nonscientific methods. Importantly, for Schurz’s argument it is not necessary to further specify what this scientific method actually consists in, the notorious problem of description (see, e.g., Lipton Reference Lipton2004). It is enough to recognize that there is something like the scientific procedure, which we wish to find justification for, and, plausibly, that its predictions have been highly successful so far, at least more successful than those of nonscientific alternatives. Thus, the second step of Schurz’s argument is that

3.3. Conclusion: Metainduction Favors Object Induction

From A and E it follows that

In Sterkenburg (Reference Sterkenburg2019), I noted that, for C to yield the desired justification of OI, we also need to say that an optimal strategy favoring OI actually amounts to a justification for it. The discussion of this step brings out a limitation of the argument: it cannot provide a justification for the object-inductive strategy (for always sticking with object induction) but at best—although this would still be an important result—a justification for sticking with the object-inductive prediction for now (thus allowing for the possibility that in the more distant future it will no longer be a good strategy to follow). And even then, I argued, this justification would only go through on a very strong empirical claim E, stating that OI has been much more successful than its competitors.

Moreover, I noted that we would also still need to argue that the optimality of the metainductive strategy actually amounts to a justification for following it. I observed that this step is tricky in its details (including the exact demand of optimality) but that it becomes more straightforward in those cases in which, again, the empirical situation is straightforward—if there is a single strategy that has been much more successful than the others. There is, however, a presupposition about the employed notion of optimality that I did not further discuss there. This is the presupposition that, in Schurz’s argument, the pool of strategies is appropriate, a proper rendition of all we could possibly do. We will now investigate whether this is truly so.

4.1. The Impossibility Result

Arnold’s observation, his impossibility theorem 3 (Reference Arnold2010, 589), comes down to this. For every strategy MI we might propose, nature can construct an adversarial history that makes it fail maximally: in each round, it can choose $y=0$ precisely if our strategy’s $\mathrm{pred}>0.5$. Then our strategy’s total loss grows linearly, and its loss rate loss_n(MI) never goes to 0. However, for a rich enough infinite pool of strategies—say a pool that includes all computable strategies—there exists for every finite history some strategy that has managed to predict this history perfectly. That is, ${\mathrm{minloss}}_n=0$ for every round n. Hence, our strategy’s loss rate does not converge to the best strategy’s.

This shows that optimality is impossible to achieve in the general case of infinite pools of strategies. At least for sufficiently rich such pools, we can for any given strategy construct a history that refutes its optimality.

4.2. Universal but Nonuniform Optimality

Arnold writes (Reference Arnold2010, 592, emphasis mine), “If only a finite number of prediction strategies are taken into account, then we exclude the overwhelming majority of possible prediction strategies from the game right from the beginning.” Arnold’s suggestion that Schurz’s argument needs a notion of optimality relative to infinite pools of strategies thus appears to be motivated by a more definite demand: the argument would need a notion of optimality relative to the infinite pool of all possible strategies. The argument would need an optimality that is no longer relative but truly universal.

The general move from reliability to optimality actually makes universality look genuinely more feasible. Namely, it seems reasonable to “take into consideration only those prediction strategies that can be described by an algorithm” (Arnold Reference Arnold2010, 592; see Sterkenburg [Reference Sterkenburg2018] for more details). While there seems little justification for limiting possible histories to computable sequences of events, it does seem reasonable to limit the methods of prediction we could possibly devise to the computable ones. Rather than the continuum of all possible histories, we then only need to consider the vastly more restricted pool of computable prediction strategies.

Of course, this is also still a countably infinite number, and so optimality in the original sense is ruled out by the impossibility result above. However, we can still attain a weaker, nonuniform optimality for countably infinite pools.

Consider again the Bayesian strategy in the log-loss game and the bound (6) on its cumulative loss: notably, this bound holds just as well for an initial weight assignment over a countably infinite pool of strategies. Thus, even in case of an infinite pool Π, we can still derive, parallel to (7), that for every strategy $P\in \Pi$, for all n,

$\begin{array}{}\text{(8)}& {\mathrm{loss}}_n\left(\mathrm{BayMI}\right)-{\mathrm{loss}}_n\left(P\right)\le \frac{-\ln w_0\left(P\right)}{n}\text{,}\end{array}$

so that in particular, for all $P\in \Pi$,

$\begin{array}{}\text{(9)}& \underset{n\to \infty }{\lim }\left({\mathrm{loss}}_n\left(\mathrm{BayMI}\right)-{\mathrm{loss}}_n\left(P\right)\right)\le 0.\end{array}$

The crux here is that (8) depends on the given strategy, specifically, on the initial weight w ₀(P) assigned to it. Now in case of only a finite number of strategies, it is possible to uniformly assign each the same initial weight, and we can derive a uniform bound (1) and consequently uniform convergence (2). But in case of an infinite number of strategies, this is obviously impossible: we are forced to give some nonuniform initial weight assignment. Consequently, the convergence (9) is nonuniform: we are not guaranteed to eventually match the success of all strategies in the pool, at the same time. We are guaranteed, for any given strategy in Π, to eventually match the success of this strategy, but by the time we do other strategies might still be way ahead of us; this is the reason why this bound is consistent with the impossibility result of section 4.1 above.

But could we not at least have a strategy that is universally optimal in this nonuniform sense? In particular, the Bayesian strategy over the pool of all computable strategies is nonuniformly optimal relative to all computable strategies. If we identify all possible strategies with the computable ones, does this not give a strategy that meets at least a nonuniform version of Arnold’s demand?

Unfortunately, it does not, and the reason is that this Bayesian strategy is no longer computable. This follows from an impossibility argument that is actually very similar to that of section 4.1 above. What it means is that, on our earlier restriction of the possible strategies to the computable ones, the candidate optimal strategy is actually no longer a proper strategy, nor is any optimal strategy for the pool of computable strategies proper. This quandary holds with great generality: it is not restricted to the log-loss function, and we cannot escape it by looking for weaker computability constraints (Sterkenburg Reference Sterkenburg2018). Thus, Arnold’s demand is, indeed, unrealizable, even on a weaker notion of nonuniform optimality: there cannot be a universally optimal prediction strategy.

4.3. The Necessity of Finiteness

On reading Arnold’s presentation, one gets the impression that Schurz’s proposed justification of induction boils down to the description of an optimal strategy. In contrast to “most of the proposed solutions to the problem of induction [that] tried to prove the reliability of the inductive procedure,” Arnold writes, “Schurz, following Reichenbach, merely tries to show the optimality of a specific inductive strategy” (Reference Arnold2010, 585). With the understanding that this must be universal optimality, such a project, we just discussed, is indeed doomed to fail.

But Schurz’s actual argument is more subtle than that. Its aim, recall, is to justify object induction, a strategy that is presumably not optimal itself. The metainductive strategy, optimal relative to all of OI’s competitors, only comes in to confer justification to OI. But now there is an even more direct reason why the pool of competitors must be finite, for Schurz’s actual argument to work.

To see this, we return to the observation in section 4.2 above that the optimality bound (7), and in general a bound (3) for any metainductive strategy, must involve an initial weight assignment w ₀. It is only with a uniform prior, which is only possible for a finite pool, that the initial weights all cancel out and P’s weights in later rounds depend on its success only. Thus, for a countably infinite pool of strategies, a metainductive strategy must express some prior preference for some strategies above others, which works through in the posterior weights.

But this would be devastating to Schurz’s argument. Conclusion C follows from step E if the optimal strategy at this point in time favors the most successful strategy, OI. In case of a finite pool of strategies, where the weights are only determined by the success, it does. But in case of an infinite pool, the metainductive strategy only favors OI at this point in time if it assigned strategy OI a sufficiently high initial weight. The metainductivist will not favor OI, even if OI has been the most successful strategy, if it assigned OI too low an initial weight (and conversely, it would favor OI, even if OI had not been successful at all, if this were compensated by a high enough initial weight). In short, the metainductive justification of object induction would have to presuppose a sufficiently strong prior preference for object induction, and this would render it an obviously circular argument.

4.4. The Finite Pool of Proposed Alternatives

Thus, in the end Arnold is right to worry that Schurz’s argument is not compatible with an infinite pool of competing strategies: indeed it is not. This leads us to “the philosophical question whether an optimality result demonstrated for a finite number of prediction strategies might suffice to answer the problem of induction” (Arnold Reference Arnold2010, 585).

Schurz writes, “I make the realistic assumption that [the metainductive strategy] has finite computational means, whence I restrict my investigation to prediction games with finitely many strategies” (Reference Schurz2009, 206; also see Reference Schurz2008, 284; Reference Schurz2018, 3891). But as Arnold noted already, the observation that a metainductive strategy can only deal with finitely many strategies falls short of a justification for this restriction: in itself, this “merely amounts to admitting that under this ‘realistic assumption’ [the metainductive strategy] simply cannot always perform optimally” (Reference Arnold2010, 592). Arnold continues, “as there is no logical contradiction involved in the assumption of an infinite number of alternative strategies, the only grounds on which it could be defended are empirical” (592). These are exactly the grounds, I will now argue, on which it can be defended, in the context of Schurz’s actual argument.

Again, Schurz’s argument is not to identify a universally optimal strategy: it is to justify object induction, from the empirical observation E that object induction has been most successful so far. Most successful among what? Certainly not among all possible strategies—unless object induction is flawless, we can always, in hindsight, conceive of strategies that would have been more successful still. No: object induction has been most successful, so far, among all actually proposed alternative strategies. The relevant empirical observation E is that object induction has been most successful among the various actually proposed nonscientific strategies—of necessity a finite number of strategies.

It is in this sense that Schurz (Reference Schurz2018, 3891) is surely right when he, after his initial and unconvincing defense, adds that “in any case, the problem of choosing among finitely many competing methods captures the most important part of the induction problem.” The problem is to give a good reason for sticking to OI, as opposed to turning to one of its contestant strategies, and the hope, again, is to derive such a noncircular reason with the help of the optimality of a metainductive strategy that by E favors it. But then it seems enough to have an optimality relative to this same pool of all actually proposed strategies. The pool of all actually proposed strategies seems to properly represent all we could have done, and so an optimal strategy for this pool would be justified.

Unfortunately, as I will argue now, there is an important way in which this optimality still falls short of including all we could have done.

5.1. The Expanding Pool of Proposed Alternatives

A metainductivist can be optimal for a finite pool of strategies, like the finite pool of actually proposed strategies, but, crucially, we need to assume that this pool is fixed. Yet it is only plausible that the pool of actually proposed strategies will expand in the course of time: informed by the actual history of events, brand new strategies may be proposed.

The metainductive strategies we have been considering cannot guarantee optimality with respect to new strategies—simply because they do not allow for dynamically incorporating new strategies in their pool. Imagine that we fix the pool of strategies that have been proposed by this time in history and design and follow a metainductive strategy that is optimal relative to this pool. But in the future a new strategy might be proposed, and this strategy might continue to be forever much more successful than all the original strategies—and hence than our metainductive strategy. This means that our metainductive strategy is no longer optimal in the sense of being as good as we could be: surely we could have started following the new and much more successful strategy instead.

5.2. Truly Analytical Optimality

Is this really a problem for Schurz’s argument, though? Was the goal, specified above, not to justify following object induction among the alternative strategies we have now?

Yes, this is still the goal, and the relevant empirical fact E is still that object induction has been most successful among the alternatives we have now. However, I now claim, the analytical step A, to be truly analytical, must involve a notion of optimality that is robust against all possible empirical circumstances, that is, against all possible histories of events but also against all possible evolutions of the pool of strategies.

Again, the crucial component of analytical optimality is that it covers every possible history: it should not and does not depend on the contingent fact of the actual history of events we have seen occur. But likewise, it should not depend on the contingent fact of the actual alternative strategies that we have seen proposed. This does not mean that we must demand optimality relative to all possible finite pools of alternative strategies at the same time (this would be Arnold’s infeasible demand of optimality relative to all possible strategies), but it does mean that we must demand optimality relative to all possible expanding pools or histories of finite pools.

Otherwise, the metainductive method is simply not optimal in the sense of being analytically the best we could do. The metainductive method that we fix at this point in time, relative to the current pool of alternative strategies, was not guaranteed to be optimal: it might not have been if other, better, strategies had been proposed in the past. And it might still fail to be if other, better, strategies are proposed in the future. As such, it is not a strategy one is justified to follow without any empirical assumptions, and it cannot fulfill the analytical role required for Schurz’s argument.

5.3. Dynamic Optimality

What are the prospects for the design of a ‘dynamic’ metainductive strategy that is optimal in the above sense? Such a strategy must allow for dynamically adding new strategies to its pool as they appear, while somehow preserving optimality guarantees with respect to all the available strategies in each round. There are some choices to be made here, starting with a suitable standard of optimality.

It appears too strict, for instance, to demand that the metainductivist keep its loss rate low with respect to new strategies on past data: it cannot, of course, guard itself against new strategies that simply fit their past predictions to the past data and thereby can claim to have a perfect score. This demand indeed goes beyond a notion of optimality as the best we could do, since we could only have followed a strategy from the moment it is actually available. But, it also appears infeasible to first measure the success of a new strategy from the moment it comes in. Take as an extreme scenario: in each round a new strategy appears that makes an initial perfect prediction and then stops predicting well; now after each round the best strategy again has a perfect score, while the metainductivist has not necessarily been doing very well.

So perhaps we need to argue for a middle way, where new strategies are assigned some ‘virtual’ loss for the rounds where they were not yet participating. This is indeed an approach taken in the literature that comes closest to our problem: the framework of ‘specialists’, experts who are in each round allowed to ‘sleep’ and refrain from making predictions (Freund et al. Reference Freund, Schapire, Singer and Warmuth1997). The ‘abstention trick’ due to Chernov and Vovk (Reference Chernov, Vovk, Gavaldà, Lugosi, Zeugmann and Zilles2009) advocates the assignment to asleep strategies of the same predictions as the metainductivist; using this trick, Mourtada and Maillard (Reference Mourtada, Maillard, Hanneke and Reyzin2017) derive bounds for the specific case of growing expert pools. In particular, preserving a uniform assignment of weights (as required in Schurz’s argument; sec. 4.3 above), they derive a short-term optimality bound with f of the form$-\ln K_n/n$, where K_n is the number of strategies by round n (Reference Mourtada, Maillard, Hanneke and Reyzin2017, 524). This is certainly a powerful bound—provided that not too many new strategies enter each round.

It remains to be argued in detail that these results are enough: that they can support both the analytical and the empirical step of the argument. I will leave it here at this briefest of sketches and suggest further investigation as a challenge for Schurz’s research program.