1. The Puzzle of Simplicity.

Philosophy of science, statistics, and machine learning all recommend the selection of simple theories or models on the basis of empirical data, where simplicity has something to do with minimizing independent entities, principles, causes, or equational coefficients. This intuitive preference for simplicity is called Ockham's razor, after the fourteenth century theologian and logician William of Ockham. But in spite of its intuitive appeal, how could Ockham's razor help us find the true theory? For, in an updated version of Plato's Meno paradox, if we already know that the truth is simple, we don't need Ockham's help. And if we don't already know that the truth is simple, what entitles us to assume that it is?

It does not help to say that simplicity is associated with other virtues such as testability (Popper Reference Popper1968), unity (Friedman Reference Friedman1983), better explanations (Harman Reference Harman1965), higher “confirmation” (Carnap Reference Carnap1950; Glymour Reference Glymour1980), or minimum description length (Rissanen Reference Rissanen1983), since if the truth were not simple, it would not have these nice properties either. To assume otherwise is to engage in wishful thinking (van Fraassen Reference van Fraassen1981).

Over-fitting arguments (Akaike Reference Akaike, Petrov and Csaki1973; Forster and Sober Reference Forster and Sober1994) show that using a simple model for predictive purposes in the presence of random noise can decrease the expected squared error of predictions. But that is still the case when one knows in advance that the truth is complex, so over-fitting arguments concern accuracy of prediction rather than finding the true theory. Furthermore, if one is interested in predicting the causal outcome of a policy on the basis of non-experimental data, the prediction could end up far from the mark because the counterfactual distribution after the policy is enacted may be quite different from the distribution sampled (Spirtes and Zhang Reference Spirtes, Zhang, Meek and Kjærulff2003). Finally, such arguments work only in statistical settings, but Ockham's razor seems no less compelling in deterministic ones.

Nor is Ockham's razor explained by a prior probabilistic bias in favor of simple possibilities, for the propriety of a systematic bias in favor of simplicity is precisely what is at issue. The argument remains circular even if complex and simple theories receive equal prior probabilities, for theories with more free parameters can be true in more ‘ways’, so that each way the complex theory might be true ends up carrying less prior probability than each of the ways the simple theory might be true; that prior bias toward simple possibilities is merely passed through Bayes’ theorem (e.g., Rosenkrantz Reference Rosenkrantz and Earman1983 and the discussion of the Bayes information criterion in Wasserman Reference Wasserman2004).

There are noncircular, relevant arguments for Ockham's razor, if one is willing to grant premises far more dubious than the theories Ockham's razor is used to justify. Leibniz (Reference Leibniz and Loemker[1714] 1875) appealed to the Creator's taste for elegance. More recently, some “naturalistic” philosophers and machine learning researchers have replaced Providence with an equally vague and optimistic appeal to Evolution (e.g., Giere Reference Giere1985; Duda et al. Reference Duda, Stork and Hart2000, 464–465). But whereas a sufficiently powerful and kind Deity could save us from error in scientific questions never before encountered, it is hardly clear how selective pressures on our hominid ancestors could do so—unless Ockham's razor is invoked to argue that our evolved penchant for simplicity is a reliable guide to the truth in questions never before encountered.

Even if Providence or Evolution did arrange the truth of simple theories after a fashion that may remain eternally obscure, it would surely be nice, in addition, to have a clear, normative argument to the effect that Ockham's razor is the most efficient possible method for finding the true theory when the problem involves theory choice. This note presents just such an argument.Footnote ¹ The idea is that it is hopeless to provide an a priori explanation of how simplicity points at the truth immediately, since the truth may depend upon subtle empirical effects that have not yet been observed or even conceived. The best that Ockham's razor could guarantee a priori is to keep us on the straightest possible path to the truth, allowing for unavoidable twists and turns along the way as new effects are discovered—and that is just what it does guarantee. Readers who wish to cut to the chase may prefer to peek immediately at Theorem 1 in Section 5 prior to reviewing the relevant definitions.

2. Illustration: Empirical Effects.

Suppose that you are interested in the structure S of an unknown polynomial law

where S is assumed to be a finite set of indices such that for each $i\in S$ , $a_{i}\neq 0$ . It seems that structures involving fewer monomial terms are simpler, so Ockham's razor favors them. Suppose that patience and improvements in measurement technology allow one to obtain ever tighter open intervals around $f(x) $ for each specified value of x as time progresses.Footnote ² Suppose that the true degree is zero, so that f is a constant function. Each finite collection of open intervals around values of f is compatible with degree one (linearity), since there is always a bit of wiggle room within finitely many open intervals to tilt the line. So suppose that the truth is the tilted line that fits the data received so far. Eventually you can obtain data from this line that refutes degree zero. Call such data a (first order) effect. Any further, finite, amount of data collected for the linear theory is compatible (due to the remaining minute wiggle room) with a quadratic law, etc. The truth is assumed to be polynomial, so the story must end, eventually, at some finite set S of effects. Thus, determining the true polynomial law amounts, essentially, to determining the finite set S of all monomial effects that one will ever see.

So conceived, empirical effects have the property that they never appear if they do not exist but may appear arbitrarily late if they do exist.Footnote ³ To reduce the curve fitting problem to its essential elements, let E be a denumerable set of potential effects and assume that at most finitely many of these effects will ever occur. Assume that your laboratory merely reports the finite set of all effects that have been detected so far, so an input sequence is an upwardly nested sequence of finite subsets of E that converges to some finite subset S of E. An input stream or empirical world is an infinite input sequence. Let the effects presented in input sequence e be denoted $S_{e}$ . The true answer to the effect accounting problem in empirical world w is then just $S_{w}$ . Call this abstract problem the effect accounting problem. The effect accounting problem reflects, approximately, the structure of a number of naturally posed inference problems, such as determining the set of independent variables a dependent variable depends upon, determining quantum numbers from a set of reactions (Schulte Reference Schulte2000), and causal inference (Spirtes et al. Reference Spirtes, Glymour and Scheines2000), in addition to the polynomial inference problem already mentioned.Footnote ⁴

A strategy for effect accounting responds to an arbitrary input sequence either with a finite set of effects or with ‘?’, indicating a refusal to choose. Strategy M solves the effect accounting problem if and only if M converges to the true set of effects $S_{w}$ in each empirical world w. One obvious solution to the effect accounting problem is the strategy $M_{0}(e) =S_{e}$ , which guesses exactly the effects it has seen so far. If the possibility of infinitely many effects were admitted, then the effect accounting problem would not be solvable at all, due to a classic result by Gold (Reference Gold1978).

Ockham's razor is the principle that one should never output an informative answer unless that answer is among the simplest answers compatible with experience. In the effect accounting problem, there is a uniquely simplest answer compatible with experience e, namely, the set $S_{e}$ of effects reported so far along e.Footnote ⁵ Thus, strategy M is Ockham at e if and only if M produces either $S_{e}$ or ‘?’ in response to finite input sequence e.

If the inputs received so far are $e=(e_{0},\,\ldots,\, e_{n+1}) $ , then let the immediately preceding evidential state be $e_{-}=(e_{0},\,\ldots,\, e_{n}) $ (where $e_{-}$ is stipulated to denote the empty sequence if e does). Say that solution M is stalwart at e if and only if $M(e) =M_{e_{-}}$ when $M(e_{-}) =S_{e}$ —that is, if you are already accepting the simplest answer, don't drop it until it is no longer simplest. One may speak of stalwartness and of Ockham's razor as being satisfied from e onward (i.e., at each extension $e^{\prime }$ of e compatible with K).

The simplicity puzzle now arises because, although every convergent strategy must agree with an Ockham strategy eventually (since the true structure $S_{w}$ in w is eventually the uniquely simplest structure compatible with the data presented along w), convergence is compatible with arbitrarily severe violations of Ockham's razor and stalwartness in the short run; for example, one could start with some complex answer $S\neq \emptyset $ and retract back to $\emptyset $ if $S\neq S_{e}$ at stage 1000 (Salmon Reference Salmon1967). The trouble is that there are infinitely many ways to converge to the truth in the effect accounting problem, just as there are infinitely many algorithmic solutions to a solvable computational problem. The nuances of programming practice—the very stuff of textbook computer science—are derived not from solvability itself, but from efficiency or computational complexity (e.g., the time or storage space required to find the right answer). The proposal is that Ockham's razor is similarly grounded in the efficiency of empirical inquiry, rather than in mere convergence (solvability).

3. Costs of Inquiry.

An obvious, doxastic cost of inquiry is the total number of times one's strategy produces a false answer prior to convergence to the true answer. Another is the number of times a conclusion is ‘taken back’ or retracted prior to convergence, which corresponds to the degree of ‘straightness’ of the path followed to the truth.Footnote ⁶ One might also wish to minimize the respective times by which these retractions occur, since there is no point ‘living a lie’ longer than necessary or allowing subsidiary conclusions to accumulate prior to being ‘flushed’ when the retraction occurs. Taken together, these costs reflect the directness and timeliness with which one surmounts obstacles on one's way to the truth, and a strategy that minimizes them can be said to have the strongest possible connection with the truth. Insofar as epistemology is distinguishable from ‘psychologism’ by its regard for truth conduciveness (Bonjour Reference Bonjour1985), minimization of retractions, retraction times, and errors is a properly epistemic consideration—indeed, more so than coherence, plausibility, confirmation, or rhetorical force. For a given strategy M and infinite input stream w, let the total loss of M in w be represented by the pair

where q is the total number of errors or false answers output by M in w, k is the total number of retractions performed by M in w, and $r_{i}$ is the stage of inquiry at which the ith retraction occurs.

Happily, it turns out that one need only consider comparisons in which one cost sequence is as good as or better than another in each of the above dimensions (i.e., Pareto comparisons). Accordingly, let $(q,\,(r_{1},\,\ldots,\, r_{k})) \leq (q^{\prime },\,(r^{\prime }_{0},\,\ldots,\, r^{\prime }_{k^{\prime }})) $ if and only if $q\leq q^{\prime }$ and there exists a subsequence $(u_{0},\,\ldots,\, u_{k}) $ of $(r^{\prime }_{0},\,\ldots,\, r^{\prime }_{k^{\prime }}) $ such that for each i from 1 to k, $r_{i}\leq u_{i}$ . Then for cost pairs $\mathbf{v},\,\mathbf{v}^{\prime }$ , define $\mathbf{v}< \mathbf{v}^{\prime }$ iff $\mathbf{v}\leq \mathbf{v}^{\prime }$ but $\mathbf{v}^{\prime }\leq \mathbf{v}$ .

A potential cost bound is like a cost pair except that the first infinite ordinal ω may occur. Potential cost bound $\mathbf{b}$ is a cost bound on set X of cost pairs if and only if each $\mathbf{v}$ in X is $\leq \mathbf{b}$ . If $\mathbf{b},\,\mathbf{b}^{\prime }$ are both potential cost bounds, say that $\mathbf{b}\leq \mathbf{b}^{\prime }$ if and only if for each cost pair $\mathbf{v}$ , if $\mathbf{v}\leq \mathbf{b}$ then $\mathbf{v}\leq \mathbf{b}^{\prime }$ . Then each set X of cost pairs has a unique, least upper cost bound $\mathrm{sup}\,(X) $ (see Kelly Reference Kelly2007).

4. Empirical Complexity and Efficiency.

No solution to the effect accounting problem achieves a nontrivial cost bound over the whole effect accounting problem, since each theory can be overturned by future effects in the arbitrarily remote future. Computational complexity theory (Aho et al. Reference Aho, Hopcroft and Ullman1974) has long since sidestepped a similar conceptual difficulty by partitioning potential inputs into respective sizes (i.e., lengths) and by then examining worst case resource bounds over the finitely many inputs of a given length. In empirical problems, each input stream w has infinite length, but it remains natural to partition potential input streams by empirical complexity. After finite input sequence e has been received, let the conditional empirical complexity of w given e be defined as $c(w,\, e) =\vert S_{w}\vert -\vert S_{e}\vert $ , where $\vert S\vert $ is the cardinality of S, and let the nth empirical complexity cell given e be the set $C_{e}(n) $ of all worlds w such that $c(w,\, e) =n$ . Let M be an arbitrary solution to the effect accounting problem. Define the worst case loss of solution M over complexity class $C_{e}(n) $ as $\lambda _{e}(M,\, n) =\mathrm{\sup}_{w\in C_{e}(n) }\lambda (M,\, w) $ , where the supremum is understood in the sense of the preceding section.

Suppose that input sequence e has just been received and the question concerns the efficiency of one's strategy M. Since the past cannot be altered, the only relevant alternatives are strategies that produce the same answers as M along $e_{-}$ (recall that $e_{-}$ denotes the result of deleting the last entry of e). Say that such a strategy agrees with M along $e_{-}$ (abbreviated $M\stackrel{\equiv }{e_{-}}M^{\prime }$ ).

Given solutions $M,\, M^{\prime }$ , the following, natural, worst case performance comparisons can be defined at e:

These comparisons give rise to two natural properties of strategies:

A solution that is strongly beaten does worse than some alternative solution in worst case performance in each nonempty, empirical complexity cell. A solution that is beaten does worse than some solution in some complexity cell and no better in the rest of the cells. An efficient solution is as good as an arbitrary solution in worst case performance in each empirical complexity cell. One may speak of being efficient from e onward. Being strongly beaten implies being beaten, which implies inefficiency.

5. The New Solution.

Here is the proposed efficiency argument for Ockham's razor. The proof is in the appendix.

So the set of all solutions to the effect accounting problem is cleanly partitioned given e into two groups: the solutions that are stalwart, Ockham, and efficient from e onward and the solutions that are strongly beaten at some stage $e^{\prime }\geq e$ due to future violations of the stalwart, Ockham property. As promised, the argument is a priori, normative, truth directed, and yet noncircular. The argument presumes no prior probabilistic bias, so there is no question of a circular appeal to such a bias. The argument is driven only by efficient convergence to the truth, so there is no bait-and-switch from truth finding to some other aim. There is no confusion between ‘confirmation’ and truth finding, since the concept of confirmation is never mentioned. There is no wishful presumption that the truth must be testable or nice in any other way. There is no appeal to the hidden hands of Providence, the Synthetic a Priori, Convention, or Evolution. There is nothing built into the argument other than a question, simplicity relative to the question, and efficient convergence to the true answer to the question.

Furthermore, the argument is stable in the sense that born again Ockhamism strongly beats recidivism at each contemplated violation, so past violations, no matter how severe, do not undermine the normative force of the argument at each moment. That is important, for Ockham violations are practically unavoidable in real science, either due to a failure to think of the simplest answer in time or due to spurious, auxiliary objections that are resolved only later.

The argument does not accomplish the impossible. Ockham's razor cannot be shown, without circularity, to point at or track the truth immediately, for some effects may be arbitrarily hard to detect given current technologies and sample sizes, in which case all possible, convergent strategies—Ockham strategies included—can be forced to retract their opinions any finite number of times. Nor can one demand a stronger notion of efficiency with respect to retractions and errors. (1) One cannot establish weak dominance for Ockham methods with respect to all problem instances jointly, because anticipation of unseen effects might be vindicated immediately, saving retractions that the Ockham method would have to perform when the effects appear. (2) Nor can one show that Ockham's razor does best in terms of a global worst case bound over all problem instances (minimax theory), for such worst case bounds on errors and retractions are trivially infinite for all methods at every stage. (3) Nor can one show a decisive advantage for Ockham's razor in terms of expected retractions. For example, if the question is whether one will see at least one effect, then the expected retractions of the obvious strategy $M(e) =S_{e}$ are less than those of an arbitrary Ockham violator only if the prior probability of the simpler answer is at least one half, so that if more than one complex world carries nonzero probability, no complex world is as probable as the simplest world, which begs the question in favor of simplicity.Footnote ⁷ If the prior probability of the simple hypothesis drops below 0.5, the advantage lies not only with violating Ockham's razor, but with violating it more rather than less. So Bayesians must either beg the question or rule strongly against Ockham.

Some applications, like the search for causal structure (Spirtes et al. Reference Spirtes, Glymour and Scheines2000), imply a priori restrictions on the possible, finite sets of effects that correspond to possible answers. Let Γ be the set of a priori possible, finite sets of effects that nature might reveal for eternity. Let $\Gamma _{e}$ denote the subset of Γ whose elements are all consistent with e (where S is consistent with e if $S_{e}\subseteq S$ ). A directed path in $\Gamma _{e}$ is just an upwardly nested, finite sequence of elements of $\Gamma _{e}$ . Now define the conditional empirical complexity $c(S,\, e) $ of world $S\in \Gamma _{e}$ given e as one less than the length of a longest path in $\Gamma _{e}$ terminating in S and let $c(w,\, e) =c(S_{w},\, e) $ . Theorem 1 extends to such cases (cf. Kelly Reference Kelly, Benthem and Adriaans2008), except that the beating incurred by Ockham violators may fail to be strong when there is more than one simplest answer compatible with e.

The preceding approach still assumes that the theorist is fed pre-digested empirical effects, rather than raw experience itself. Here is a very general definition of empirical complexity that agrees with the preceding account when applied to pre-digested problems (cf. Kelly Reference Kelly, Benthem and Adriaans2008). In general, an empirical problem $\mathstrut{\cal P} $ consists of a set K of possible input streams or worlds and an empirical question Π, which is just a partition of K into potential answers. No objectionable pre-digestion is assumed here: the successive inputs presented by $w\in K$ could be boolean bits in a highly ‘gruified’ coding scheme with an ocean of information irrelevant to the question Π thrown in. If e is a finite input sequence, let $K_{e}$ denote the restriction of K to input streams extending finite input sequence e. Let p be a finite sequence of answers drawn from Π. Say that p is forcible by nature given finite input sequence e in $\mathstrut{\cal P} $ if and only if for each strategy M guaranteed to converge to the true answer in $\mathstrut{\cal P} $ , there exists w in $K_{e}$ such that M responds to w, after the end of e, with a sequence of outputs of which p is a subsequence. Let $S_{e}$ denote the set of all finite sequences of answers forcible in $\mathstrut{\cal P} $ given e. Restrict attention to the natural problems $\mathstrut{\cal P} $ in which $\mathrm{\lim}_{i\rightarrow \infty }S_{w\vert i}$ exists, for each $w\in K$ , and let $S_{w}$ denote this limit. Let $\Gamma _{e}$ denote the set of all $S_{w}$ such that $w\in K_{e}$ . If $S,\, S^{\prime }\in \Gamma _{e}$ , say that $S\leq S^{\prime }$ if and only if for each $e^{\prime }$ extending e such that $S=S_{e^{\prime }}$ , there exists $e^{\prime \prime }$ extending $e^{\prime }$ such that $S^{\prime }=S_{e^{\prime \prime }}$ . Now define $c(w,\, e) $ in terms of longest $\leq $ -path length in $\Gamma _{e}$ to $S_{e}$ , just as in the preceding paragraph. This definition of simplicity depends only upon the (semantic) structures of $K,\,\Pi $ , so it is invariant under arbitrary, grue-like (Goodman Reference Goodman1983) recodings of the inputs (which leave the semantics of the problem intact). Moreover, if $\mathstrut{\cal P} _{\Gamma }$ is the (pre-digested) sort of problem discussed in the preceding paragraph, then it can be shown that the complexity degree assignment $c(w,\, e) $ just defined is identical to the one defined in the preceding paragraph. Finally, applying this definition to problems that look, intuitively, like effect accounting problems (e.g., polynomial structure, causal structure, or conservation laws) identifies what intuition would point out as the empirical effects relevant to the question Π given. So careful attention to truth finding efficiency provides not only a novel explanation of Ockham's razor, but also a fresh perspective on the nature of simplicity, itself.