Basic HTML Version

Notes to Chapter 9
The topic of minimizing mind-changes prior to convergence has been investigated extensively
in the area of formal learning theory (cf. Jain et al. 1999). The connection between learning
performance and Ockham’s razor has been developed by Schulte (1999) and Kelly (2002, 2007a,
b, 2008, 2010) and Kelly and Glymour (2004). Kelly’s earlier approach was to derive Ockham’s
razor from retraction minimization, where a retraction occurs whenever one no longer affirms
what one used to affirm. Retractions are more complicated to analyze and the derived version of
Ockham’s razor is not as plausible. This chapter substitutes reversals and cycles for retractions,
with smoother and more plausible results.
In computational learning theory, crookedness is measured in terms of
(Jain et
al. 1999) and cycles are called
U-shaped learning
(Carlucci et al. 2007).
As long as we are channeling ancient, eastern wisdom, we may as well give some air time to
ancient, western wisdom. Plato, in his dialogue
The Meno
, distinguished knowledge from mere,
true belief in terms of the stability of the former, in the sense that one would not give it up in the
face of true information. Note that the sequence (3, 0) is unstable in that sense, whereas the
sequence (0, 1, 2, 3, …,
) is stable, in Plato’s sense.
Counting reversals is a bit crude, since the simplicity order may have infinite descending
chains or other peculiarities that make the worst-case reversal count infinite. More generally, say
that a reversal sequence is a finite sequence of answers or disjunctions of answers such that each
successive entry contradicts its predecessor. Then say that one method is
as good as
another, in
terms of worst-case reversals over answer
, if for every reversal sequence performed by the first
method, given that
is true, the second method generates a reversal sequence whose successive
entries entail those in the first method’s sequence. The first method is better, in terms of worst-