Formal Learning Theory (Stanford Encyclopedia of Philosophy) Cite this entry Search the SEP • Advanced Search • Tools • RSS FeedTable of Contents• What's New• Archives• Projected ContentsEditorial Information• About the SEP• Editorial Board• How to Cite the SEP• Special CharactersSupport the SEPContact the SEP ©Metaphysics Research Lab,CSLI,Stanford University  Open access to the SEP is made possible by a world-wide funding initiative. Please Read How You Can Help Keep the Encyclopedia FreeFormal Learning TheoryFirst published Sat Feb 2, 2002; substantive revision Wed May 21, 2008Formal learning theory is the mathematical embodiment of a normativeepistemology. It deals with the question of how an agent should useobservations about her environment to arrive at correct and informativeconclusions. Philosophers such as Putnam, Glymour and Kelly havedeveloped learning theory as a normative framework for scientificreasoning and inductive inference.Terminology. Cognitive science and related fields typicallyuse the term “learning” for the process of gaininginformation through observation—hence the name “learningtheory”. To most cognitive scientists, the term “learningtheory” suggests the empirical study of human and animallearning stemming from the behaviourist paradigm in psychology. Theepithet “formal” distinguishes the subject of this entryfrom behaviourist learning theory. Because many developments in, andapplications of, formal learning theory come from computer science,the term “computational learning theory” is alsocommon. Philosophical terms for learning-theoretic epistemologyinclude “logical reliability” (Kelly [1996], Glymour[1991]) and “means-ends epistemology” (Schulte[1999a]).This entry focuses on the philosophical ideas and insights behindlearning theory. It eschews theorems and definitions in favour ofexamples and informal arguments. Those interested in the mathematicalsubstance of learning theory will find some references in the Bibliography, and a summary of the basic definitions inthe Supplementary Document.Philosophical characteristics. We can categorize normativeepistemologies according to two criteria: (1) what are the objects ofnormative evaluation, and (2) what are the evaluation criteria to beemployed? In learning theory, the basic object of normative evaluationis an inquirer's disposition to form beliefs given some evidence. Thenormative question that drives the theory is whether a given doxasticdisposition serves the goals of inquiry or not. Most of learning theoryexamines which investigative strategies reliably lead to correctbeliefs about the world.Overview. A number of examples will illustrate howmeans-ends analysis can lead us to endorse some ways of drawinginductive inferences and to reject others. Then I outline some of thegeneral insights that lie behind such examples. Finally I relatemeans-ends epistemology to some other traditions in inductiveepistemology.1. Some Basic Examples2. Case Studies in Scientific Practice3. The Long Run in The Short Run4. The Limits of Inquiry and the Complexity of Empirical Problems5. Categorical vs. Hypothetical ImperativesSupplementary Document: Basic Formal DefinitionsBibliographyOther Internet ResourcesRelated Entries1. Some Basic ExamplesLearning-theoretic analysis assesses doxastic dispositions. Severalterms for doxastic dispositions are in common use in philosophy; I willuse “inductive strategy”, “inference method” and most frequently“inductive method” to mean the same thing. The best way to understandhow learning theory evaluates inductive methods is to work through someexamples. The following presentation begins with some very simpleinductive problems and moves on to more complicated—and morerealistic—settings.Universal GeneralizationLet's revisit the classic question of whether all ravens are black.Imagine an ornithologist who tackles this problem by examining oneraven after another. There is exactly one observation sequence in whichonly black ravens are found; all others feature at least one nonblackraven. The figure below illustrates the possible observation sequences.Dots in the figure denote points at which an observation may be made. Ablack bird to the left of a dot indicates that at this stage, a blackraven is observed; similarly for a white bird to the right of a dot.Given a complete sequence of observations, either all observed ravensare black or not; the figure labels complete observation sequences withthe statement that is true of them. The gray fan indicates that afterthe observation of a white raven, the claim that not all ravens areblack holds on all observation sequences resulting from furtherobservations. If the world is such that only black ravens are found, we would likethe ornithologist to settle on this generalization. (It may be possiblethat some nonblack ravens remain forever hidden from sight, but eventhen the generalization “all ravens are black” at least gets theobservations right.) If the world is such that eventually a nonblackraven is found, then we would like the ornithologist to arrive at theconclusion that not all ravens are black. This specifies a set of goalsof inquiry. For any given inductive method that might represent theornithologist's disposition to adopt conjectures in the light of theevidence, we can ask whether that method measures up to these goals ornot. There are infinitely many possible methods to consider; we'll lookat just two, a sceptical one and one that boldly generalizes. The boldmethod conjectures that all ravens are black after seeing that thefirst raven is black. It hangs on to this conjecture unless somenonblack raven appears. The sceptical method does not go beyond what isentailed by the evidence. So if a nonblack raven is found, theskeptical method concludes that not all ravens are black, but otherwisethe method does not make a conjecture one way or another. The figurebelow illustrates both the generalizing and the sceptical method. Do these methods attain the goals we set out? Consider the boldmethod. There are two possibilities: either all observed ravens areblack, or some nonblack raven is found. In the first case, the methodconjectures that all ravens are black and never abandons thisconjecture. In the second case, the method concludes that not allravens are black as soon as the first nonblack raven is found. Henceno matter how the evidence comes in, eventually the methodgives the right answer as to whether all ravens are black andsticks with this answer. Learning theorists call such methodsreliable because they settle on the right answer no matterwhat observations the world provides.The skeptical method does not measure up so well. If a nonblackraven appears, then the method does arrive at the correct conclusionthat not all ravens are black. But if all ravens are black, the skepticnever takes an “inductive leap” to adopt this generalization. So inthat case, the skeptic fails to provide the right answer to thequestion of whether all ravens are black.This illustrates how means-ends analysis can evaluate methods: thebold method meets the goal of reliably arriving at the right answer,whereas the skeptical method does not. Note the character of thisargument against the skeptic: The problem, in this view, is not thatthe skeptic violates some canon of rationality, or fails to appreciatethe “uniformity of nature”. The learning-theoretic analysis concedes tothe skeptic that no matter how many black ravens have been observed inthe past, the next one could be white. The issue is that if allobserved ravens are indeed black, then the skeptic neveranswers the question “are all ravens black?”. Getting the rightanswer to that question requires generalizing from the evidenceeven though the generalization could be wrong.As for the bold method, it's important to be clear on what it doesand does not achieve. The method will eventually settle on the rightanswer—but it (or we) may never be certain that it has doneso. As William James put it, “no bell tolls”when science has found the right answer. We are certain that the methodwill eventually settle on the right answer; but we may never be certainthat the current answer is the right one. This is a subtle point. Thenext example illustrates this point further.A Riddle of InductionNelson Goodman posed a famous puzzle about inductive inference knownas the (New) Riddle of Induction ([Goodman 1983]). Our next example isinspired by his puzzle. Goodman considered generalizations aboutemeralds, involving the familiar colours of green and blue, as well ascertain unusual ones:Suppose that all emeralds examined before a certain timet are green ... Our evidence statements assert that emeralda is green, that emerald b is green, and so on... Now let us introduce another predicate less familiar than“green”. It is the predicate “grue” and itapplies to all things examined before t just in case they aregreen but to other things just in case they are blue. Then at timet we have, for each evidence statement asserting that a givenemerald is green, a parallel evidence statement asserting that emeraldis grue.The question is whether we should conjecture that all emeralds aregreen rather than that all emeralds are grue when we obtain a sample ofgreen emeralds examined before time t, and if so, why.Clearly we have a family of grue predicates in this problem,corresponding to different “critical times” t; let's writegrue(t) to denote these. Following Goodman, let us refer tomethods as projection rules in discussing this example. A projectionrule succeeds in a world just in case it settles on a generalizationthat is correct in that world. Thus in a world in which all examinedemeralds are found to be green, we want our projection rule to convergeto the proposition that all emeralds are green. If all examinedemeralds are grue(t), we want our projection rule to convergeto the proposition that all emeralds are grue(t). Note thatthis stipulation treats green and grue predicates completely on a par,with no bias towards either. As before, let us consider two rules: the“natural” projection rule which conjectures that all emeralds are greenas long as only green emeralds are found, and the “gruesome” rule whichkeeps projecting the next grue predicate consistent with the availableevidence. Expressed in the green-blue vocabulary, the gruesomeprojection rule conjectures that after observing some number ofn green emeralds, all future ones will be blue. The figurebelow illustrates the possible observation sequences and the naturalprojection rule in this model of the New Riddle of Induction. The following figure shows the gruesome projection rule.  How do these rules measure up to the goal of arriving at a truegeneralization? Suppose for the sake of the example that the onlyserious possibilities under consideration are that either all emeraldsare green or that all emeralds are grue(t) for some criticaltime t. Then the natural projection rule settles on thecorrect generalization no matter what the correct generalization is.For if all emeralds are green, the natural projection rule asserts thisfact from the beginning. And suppose that all emeralds aregrue(t) for some critical time t. Then at timet, a blue emerald will be observed. At this point the naturalprojection rule settles on the conjecture that all emeralds aregrue(t), which must be correct given our assumption about thepossible observation sequences. Thus no matter what evidence isobtained in the course of inquiry—consistent with our backgroundassumptions—the natural projection rule eventually settles on acorrect generalization about the colour of emeralds.The gruesome rule does not do as well. For if all emeralds aregreen, the rule will never conjecture this fact because it keepsprojecting grue predicates. Hence there is a possible observationsequence—namely those on which all emeralds are green—on whichthe gruesome rule fails to converge to the right generalization. Someans-ends analysis would recommend the natural projection rule overthe gruesome rule. Some comments are in order.1. As in the previous example, nothing in this argument hinges onarguments to the effect that certain possibilities are not to be takenseriously a priori. In particular, nothing in the argument says thatgeneralizations with grue predicates are ill-formed, unlawlike, or insome other way a priori inferior to “all emeralds are green”.2. The analysis does not depend on the vocabulary in which theevidence and generalizations are framed. For ease of exposition, I havemostly used the green-blue reference frame. However, grue-bleenspeakers would agree that the aim of reliably settling on a correctgeneralization requires the natural projection rule rather than thegruesome one, even if they would want to express the conjectures of thenatural rule in their grue-bleen language rather than the blue-greenlanguage that we have used so far. (For more on the language-invarianceof means-ends analysis see Section 4 (The Limits ofInquiry and the Complexity of Empirical Problems), as well as Schulte[1999a, 1999b]).3. Though the analysis does not depend on language, it does dependon assumptions about what the possible observation sequences are. Theexample as described above seems to comprise the possibilities thatcorrespond to the colour predicates Goodman himself discussed. Butmeans-ends analysis applies just as much to other sets of possiblepredicates. Schulte [1999a, 1999b] and Chart [2000] discuss a number ofother versions of the Riddle of Induction, in some of which means-endsanalysis favours projecting that all emeralds are grue on a sample ofall green emeralds.4. Even with the assumptions granted so far, there are reliableprojection rules that project that all emeralds are grue(t) ona sample of all green emeralds. For example, the projection rule“conjecture that all emeralds are grue(3) until 3 green emeralds areobserved; then conjecture that all emeralds are green until a blueemerald is observed” is guaranteed to eventually settle on a correctgeneralization just like the natural projection rule. (It's aworthwhile exercise to verify the reliability of this rule.) I willdiscuss criteria for further restricting the space of rules in Section 3 (The Long Run in The Short Run).Generalizations with ExceptionsLet's return to the world of ravens. This time the ornithologicalcommunity is more guarded in its generalizations concerning the colourof ravens. Two competing hypotheses are under investigation: (1) Thatbasically all ravens are black, but there may be a finite number ofexceptions to that rule, and (2) that basically all ravens are white,but there may be a finite number of exceptions to that rule. Assumingthat one or the other of these hypotheses is correct, is there aninductive method that reliably settles on the right one? What makesthis problem more difficult than our first two is that each hypothesisunder investigation is consistent with any finite amount of evidence.If 100 white ravens and 50 black ravens are found, either the 50 blackravens or the 100 white ravens may be the exception to the rule. Interminology made familiar by Karl Popper'swork, we may say that neither hypothesis is falsifiable. As aconsequence, the inductive strategy from the previous two examples willnot work here. This strategy was basically to adopt a “bold” universalgeneralization, such as “all ravens are black” or “all emeralds aregreen”, and to hang on to this conjecture as long as it “passesmuster”. However, when rules with possible exceptions are underinvestigation, this strategy is unreliable. For example, suppose thatan inquirer first adopts the hypothesis that “all but finitely manyravens are white”. It may be the case that from then on, only blackravens are found. But each of these apparent counterinstances can be“explained away” as an exception. If the inquirer follows the principleof hanging on to her conjecture until the evidence is logicallyinconsistent with the conjecture, she will never abandon her falsebelief that all but finitely many ravens are white, much less arrive atthe correct belief that all but finitely many ravens are black.Reliable inquiry requires a more subtle investigative strategy. Hereis one (of many). Begin inquiry with either competing hypothesis, say“all but finitely many ravens are black”. Choose some cut-off ratio torepresent a “clear majority”; for definiteness, let's say 70%. If thecurrent conjecture is that all but finitely many ravens are black,change your mind to conjecture that all but finitely many ravens arewhite just in case over 70% of observed ravens are in fact white.Proceed likewise if the current conjecture is that all but finitelymany ravens are white when over 70% of observed ravens are in factblack.A bit of thought shows that this rule reliably identifies thecorrect hypothesis in the long run, no matter which of the twocompeting hypotheses is correct. For if all but finitely many ravensare black, eventually the nonblack exceptions to the rule will beexhausted, and an arbitrarily large majority of observed ravens will beblack. Similarly if all but finitely many ravens are white.The way in which this reliable method is sensitive to the frequencyof occurrences of black resp. white ravens is reminiscent ofstatistical methods. This suggests considering statisticalgeneralizations such as “the percentage of white ravens in the totalpopulation of ravens is 20%”. Hans Reichenbach held that the centralaim of inductive inference were generalizations of precisely that sort.More generally, we may consider hypotheses about proportions such as“the proportion of white ravens is between 10% and 20%”. Kelly examinesin detail various hypotheses of this kind and establishes when thereare reliable methods for testing them. He also provides alearning-theoretic interpretation of classical statistical tests of aparameter for a probability distribution [Kelly 1996, Ch.3.4].Generalizations with exceptions illustrate some subtle nuances inthe relationship between Popperian falsificationism and thelearning-theoretic idea of reliable convergence to the truth. In somesettings of inquiry, notably those involving universal generalizations,a naively Popperian “conjectures-and-refutations” approach of hangingon to conjectures until the evidence falsifies them does yield areliable inductive method. In other problems, like the current example,it does not. Generally speaking problems with unfalsifiable hypothesesrequire something other than the conjectures-and-refutations recipe forreliable methods (this assertion hinges on what exactly one means by“falsifiable hypothesis”; see Section 4 (The Limits ofInquiry and the Complexity of Empirical Problems) as well as [Schulteand Juhl 1996]). A Popperian might respond that such hypotheses are“unscientific” and hence it is no concern that theconjectures-and-refutations approach fails to reliably identify acorrect hypothesis when unfalsifiable hypotheses are involved. Butintuitively, a claim like “all but finitely many ravens are black”appears to be a respectable empirical hypothesis. More importantly thanintuition, at least from the point of view of means-ends epistemology,it is possible to reliably assess the truth of such claims in the longrun, even though all hypotheses under investigation are consistent withany finite amount of evidence. This constitutes a clear sense in whichinquiry can test these hypotheses against empirical evidence in orderto find the truth. If we allow that we would want inductive methodologyto extend to problems like this one, the moral is that relying onfalsifications is sometimes, but not always, the best way forinquiry to proceed.2. Case Studies in Scientific PracticeThis section provides further examples to illustratelearning-theoretic analysis. The examples in this section are morerealistic and address methodological issues arising in scientificpractice. The space constraints of the encyclopedia format allow onlyan outline of the full analysis; there are references to more detaileddiscussions below.Conservation Laws in Particle PhysicsOne of the hallmarks of elementary particle physics is the discoveryof new conservation laws that apply only in the subatomic realm [Ford1963, Ne'eman and Kirsh 1983, Feynman 1965]. (Feynman groups one ofthem, the conservation of Baryon Number, with the other “greatconservation laws” of energy, charge and momentum.) Simplifyingsomewhat, conservation principles serve to explain why certainprocesses involving elementary particles do not occur: the explanationis that some conservation principle was violated (cf. Omnes [1971,Ch.2] and Ford [1963]). So a goal of particle inquiry is to find a setof conservation principles, such that for every process that ispossible according to the (already known) laws of physics, there issome conservation principle that rules out that process. And if aprocess is in fact observed to occur, then it ought to satisfy allconservation laws that we have introduced.This constitutes an inference problem to which we may applymeans-ends analysis. An inference method produces a set of conservationprinciples in response to reports of observed processes. Means-endsanalysis asks which methods are guaranteed to settle on conservationprinciples that account for all observations, that is, that rule outunobserved processes and allow observed processes. [Schulte 2000]describes an inductive method that accomplishes this goal.It turns out that the conservation principles that this method would positon the currently available evidence are empirically equivalent to the ones thatphysicists have introduced. That is, the predictions of physicists about whichreactions are possible and which are impossible are exactly the ones that the learning-theoretic method would make. It turns out that for some physical processes, the only way to getempirically adequate conservation principles is by positing that somehidden particles have gone undetected. It is remarkable that to findconservation principles that are consistent with what is observed,sometimes the only option is to form hypotheses about what isunobserved. It is easy to miss this phenomenon without thescrutiny that means-ends analysis requires. Extending our problem sothat inference methods not only posit conservation laws but also hiddenparticles makes inquiry more difficult. But if we grant the particletheorist the assumption that there are only finitely many types ofhidden particles, then a method does exist that is guaranteed to settleeventually on a theory that makes correct predictions about theobservable phenomena, using a combination of conservation laws andhidden particles. A detailed discussion of the conservation lawinference problem is in [Schulte 2000]; the relationship to other topics in the philosophy of science such as simplicity and natural kinds is examined in [Schulte 2008].Models of Cognitive ArchitectureSome philosophers of mind have argued that the mind is composed offairly independent modules. Each module has its own “input” from othermodules and sends “output” to other modules. For example, an “auditoryanalysis system” module might take as input a heard word and send aphonetic analysis to an “auditory input lexicon”. The idea of modularorganization raises the empirical question of what mental modulesthere are and how they are linked to each other. A prominent traditionof research in cognitive neuroscience has attempted to develop a modelof mental architecture along these lines by studying the responses ofnormal and abnormal subjects to various stimuli. The idea is tocompare normal reactions with abnormal ones—often caused bybrain damage—so as to draw inferences about which mentalcapacities depend on each other and how.Glymour [1994] asked the reliabilist question whether there areinference methods that are guaranteed to eventually settle on a truetheory of mental organization, given exhaustive evidence about normaland abnormal capacities and reactions. He argued that for some possiblemental architectures, no amount of evidence of the stimulus-responsekind can distinguish between them. Since the available evidencedetermines the conjectures of an inductive method, it follows thatthere is no guarantee that a method will settle on the true model ofcognitive architecture.In further discussion, Bub [1994] showed that if we grant certainrestrictive assumptions about how mental modules are connected, then acomplete set of behavioural observations would allow aneuropsychologist to ascertain the module structure of a (normal) mind.In fact, under Bub's assumptions there is a reliable method foridentifying the modular structure. Glymour has also explored to whatextent richer kinds of evidence would resolve underdetermination ofmental architecture by behavioural evidence. (One example of richerevidence are double disassocations. An example of a double dissocationwould be a pair of patients, one who has a normal capacity forunderstanding spoken words, but fails to understand written ones, andanother who understands written words but not spoken ones.)Some more case studies of this sort may be found in [Kelly 1996, Ch.7.7, Harell 2000]. The main interest of such studies lies of course inwhat they say about the particular domain under investigation. But theyalso illustrate some general features of learning theory:1. Generality. The basic notions of the theory are verygeneral. Essentially, the theory applies whenever one has a questionthat prompts inquiry, a number of candidate answers, and some evidencefor deciding among the answers. Thus means-ends analysis can be appliedin any discipline aimed at empirical knowledge, for example physics orpsychology.2. Context Dependence. Learning theory is pure normative apriori epistemology, in the sense that it deals with standards forassessing methods in possible settings of inquiry. But the approachdoes not aim for universal, context-free methodological maxims. Themethodological recommendations depend on contingent factors, such asthe operative methodological norms, the questions under investigation,the background assumptions that the agent brings to inquiry, theobservational means at her disposal, her cognitive capacities, and herepistemic aims. As a consequence, to evaluate specific methods in agiven domain, as in the case studies mentioned, one has to study thedetails of the case in question. The means-ends analysis often rewardsthis study by pointing out what the crucial methodological features ofa given scientific enterprise are, and by explaining precisely why andhow these features are connected to the success of the enterprise inattaining its epistemic aims.3. Trade-offs. In the perspective of means-endsepistemology, inquiry involves an ongoing struggle with hard choices,rather than the execution of a universal “scientific method”. Theinquirer has to balance conflicting values, and may consider variousstrategies such as accepting difficulties in the short run hoping toresolve them in the long run. For example in the conservation lawproblem, there can be conflicts between theoretical parsimony, i.e.,positing fewer conservation laws, and ontological parsimony, i.e.,introducing fewer hidden particles. For another example, a particletheorist may accept positing undetected neutrinos in the hopes thatthey will eventually be observed as science progresses. An importantlearning-theoretic project is to examine when such tradeoffs arise andwhat the options for resolving them are. The next section deals withsome aspects of this topic.3. The Long Run in the Short RunA longstanding criticism of convergence to the truth as an aim ofinquiry is that, while fine in itself, this aim is consistent with anycrazy behaviour in the short run [Salmon 1991]. For example, we saw inthe New Riddle of Induction that a reliable projection rule canconjecture that the next emerald will be blue no matter how many greenemeralds have been found—as long as eventually the ruleprojects “all emeralds are green”. One response is that if means-endsanalysis takes into account other epistemic aims in additionto long-run convergence, then it can provide strong guidancefor what to conjecture in the short run.To illustrate this point, let us return to the Goodmanian Riddle ofInduction. Since Plato, philosophers have considered the idea thatstable true belief is better than unstable true belief, andepistemologists such as Sklar [1975] have advocated similar principlesof “epistemic conservatism”. Kuhn tells us that a major reason forconservatism in paradigm debates is the cost of changing scientificbeliefs [Kuhn 1970]. In this spirit, learning theorists have examinedmethods that minimize the number of times that they change theirtheories before settling on their final conjecture. Such methods aresaid to minimize mind changes. The New Riddle of Inductionturns out to be a nice illustration of this idea. Consider the naturalprojection rule (conjecture that all emeralds are green on a sample ofgreen emeralds). If all emeralds are green, this rule never changes itsconjecture. And if all emeralds are grue(t) for some criticaltime t, then the natural projection rule abandons itsconjecture “all emeralds are green” at time t—one mindchange—and thereafter correctly projects “all emeralds aregrue(t)”. Remarkably, rules that project grue rather thangreen do not do as well. For example, consider a rule that conjecturesthat all emeralds are grue(3) after observing one green emerald. If twomore green emeralds are observed, the rule's conjecture is falsifiedand it must eventually change its mind, say to conjecture that allemeralds are green (suppose that green emeralds continue to be found).But then at that point, a blue emerald may appear, forcing a secondmind change. This argument can be generalized to show that the aim ofminimizing mind changes allows only the green predicate to be projectedon a sample of all green emeralds [Schulte 1999a]. We saw in a figureabove how the natural projection rule changes its mind at most once;the figure below illustrates in a typical case how an unnaturalprojection rule may have to change its mind twice or more. The conservation law problem discussed in the previous sectionprovides another illustration of how additional epistemic aims canlead to constraints in the short run. In this problem, reliability andminimizing mind changes require a particle theorist to adopt aconservation theory that rules out as many unobserved reactions aspossible. In certain circumstances, the only way to attain this aim isto introduce hidden particles. Long-run reliability by itself mayrequire that the theorist introduce hidden particleseventually; the additional goal of minimizing mindchanges—stable belief—dictates exactly when this shouldoccur [Schulte 2000].Kelly has developed the idea of minimizing mind changes as anexplanation of why we should follow Occam's Razor, understood as apreference for simpler theories [Kelly 2007a]. He suggests anapplication of this understanding of Occam's Razor to the discovery ofcausal relationships [see also Kelly 2007b, Schulte et al. 2007].4. The Limits of Inquiry and the Complexity of Empirical ProblemsAfter seeing a number of examples like the ones above, one begins towonder what the pattern is. What is it about an empirical question thatallows inquiry to reliably arrive at the correct answer? What generalinsights can we gain into how reliable methods go about testinghypotheses? Learning theorists answer these questions withcharacterization theorems. Characterization theorems aregenerally of the form “it is possible to attain this standard ofempirical success in a given inductive problem if and only if theinductive problem meets the following conditions”. There are anumber of standards of success in inquiry—reliable convergence tothe truth, fast reliable convergence, reliable convergence with fewmind changes—and hence correspondingly many characterizationtheorems.A fundamental result describes the conditions under which a methodcan reliably find the correct hypothesis among a countably infinite orfinite number H1, H2, …,Hn, …. of mutually exclusive hypotheses thatjointly cover all possibilities consistent with the inquirer'sbackground assumptions. This is possible just in case each of thehypotheses is a countable disjunction of refutable empirical claims. By“refutable” I mean that if the claim is false, the evidencecombined with the inquirer's background assumptions will eventuallyconclusively falsify the hypothesis (see Schulte and Juhl [1996], Kelly[1996, Ch. 3.3]). For illustration, let's return to the ornithologicalexample with two alternative hypotheses: (1) all but finitely manyswans are white, and (2) all but finitely many swans are black. As wesaw, it is possible in the long run to reliably settle which of thesetwo hypotheses is correct. Hence by the characterization theorem, eachof the two hypotheses must be a disjunction of refutable empiricalclaims. To see that this indeed is so, observe that “all butfinitely many swans are white” is logically equivalent to thedisjunction“at most 1 swan is black or at most 2 swans are black …or at most n swans are black … or…”,and similarly for “all but finitely many swans are black”.Each of the claims in the disjunction is refutable, in the sense ofbeing eventually falsified whenever it is false. For example, take theclaim that “at most 3 swans are black”. If this is false,more than 3 black swans will be found, at which point the claim isconclusively falsified. A few points will help explain the significance of characterizationtheorems like this one.1. Structure of Reliable Methods. Characterization theoremstell us how the structure of reliable methods corresponds to thestructure of the hypotheses under investigation. For example, thetheorem mentioned establishes a connection between falsifiability andtestability, but one that is more attenuated than the naïvePopperian envisions: it is not necessary that the hypotheses under testbe directly falsifiable; rather, there must be ways of strengtheningeach hypothesis that yield a countable number of refutable“subhypotheses”. We can think of these refutablesubhypotheses as different ways in which the main hypothesis may betrue. (For example, one way in which “all but finitely many ravens arewhite” is true is if there are are at most 10 black ravens; another ifthere are at most 100 black ravens, etc.)2. Import of Background Assumptions. The characterizationresult draws a line between the solvable and unsolvable problems.Background knowledge reduces the inductive complexity of a problem;with enough background knowledge, the problem crosses the thresholdbetween the unsolvable and the solvable. In many domains of empiricalinquiry, the pivotal background assumptions are those that makereliable inquiry feasible. (Kuhn [1970] makes similar points). Forexample, in the particle dynamics problem, it is the assumption thatsome set of linear conservation laws is empirically adequate thatpermits us to reliably find an empirically adequate theory of particlereactions. It seems that, conversely, in domains in which the availablebackground assumptions do not reduce the complexity of the empiricalproblems enough, there is a sense that inquiry is not sufficientlyconstrained for steady progress. One example might be Chomsky's programof universal grammar whose inductive complexity hinges on how broad weassume the set of humanly learnable languages to be. It is aninteresting question how much the complexity of an empiricalinvestigation, as determined by the strength of the availablebackground assumptions, connects with the practitioners' sense ofprogress and feasibility. In the domains considered so far,learning-theoretic complexity corresponds quite well to intuitivemethodological difficulty, but more case studies are required. In anycase, learning-theoretic characterization theorems help us to pinpointthe sources of inductive complexity, and thus the methodologicallycentral assumptions and the weak spots in a given empiricalenterprise.3. Universal Measure of Inductive Complexity. There arecharacterization theorems for a number of standards of empiricalsuccess. The more demanding the standard, the more stringent theconditions that such standards require. It turns out that a number ofnatural standards of inductive success fall into a hierarchy offeasibility, in the sense that standards higher in the hierarchy areattainable if standards lower in the hierarchy are. For a trivialexample, if it is possible to settle on a correct hypothesis with atmost 5 mind changes, then a fortiori it is possible to succeed with 10mind changes. For other cognitive aims the inclusion is moresurprising; see Schulte [1999a]. We may think of the hierarchy ofstandards of empirical success as establishing a scale for inductiveproblems: The more difficult the problem, the less we can expect frominquiry. The hierarchy of empirical success allows us to weigh suchdiverse problems as Goodman's Riddle, particle dynamics and languagelearning on the same scale. For example, it should be clear that thecharacteristic condition for reliable inquiry—that eachhypothesis be equivalent to a countable disjunction of refutableassertions—applies in every domain of investigation. Thusmeans-ends analysis uncovers common structure among seeminglydisparate problems.4. Language Invariance. Learning-theoretic characterizationtheorems concern what Kelly calls the “temporal entanglement” ofvarious observation sequences [Kelly 2000] (see also [Schulte and Juhl1996]). Ultimately they rest on entailment relations between givenevidence, background assumptions and empirical claims. Since logicalentailment does not depend on the language we use to frame evidence andhypotheses, the inductive complexity of an empirical problem asdetermined by the characterization theorems is language-invariant.Indeed, it turns out that inductive complexity can be captured in termsof point-set topology and corresponds to a scale of topologicalcomplexity that has much importance in mathematics (the Borel andfinite-difference hierarchies [Kelly 1996]).5. Categorical vs. Hypothetical ImperativesKant distinguished between categorical imperatives that one ought tofollow regardless of one's personal aim and circumstances, andhypothetical imperatives that direct us to employ our means towards ourchosen end. One way to think of learning theory is as the study ofhypothetical imperatives for empirical inquiry. Many epistemologistshave proposed various categorical imperatives for inductive inquiry,for example in the form of an “inductive logic” or norms of “epistemicrationality”. In principle, there are three possible relationshipsbetween hypothetical and categorical imperatives for empiricalinquiry.1. The categorical imperative will lead an inquirer to obtain hiscognitive goals. In that case means-ends analysis vindicatesthe categorical imperative. For example, when faced with a simpleuniversal generalization such as “all ravens are black”, we saw abovethat following the Popperian recipe of adopting the falsifiablegeneralization and sticking to it until a counter example appears leadsto a reliable method.2. The categorical imperative may prevent an inquirer fromachieving his aims. In that case the categorical imperativerestricts the scope of inquiry. For example, in the case ofthe two alternative generalizations with exceptions, the principle ofmaintaining a universal generalization until it is falsified leads toan unreliable method (cf. [Kelly 1996, Ch. 9.4]).3. Some methods meet both the categorical imperative andthe goals of inquiry, and others don't. Then we may take the best ofboth worlds and choose those methods that attain the goals of inquiryand satisfy categorical imperatives. (See the further discussion inthis section.)For a proposed norm of inquiry, we can apply means-ends analysis toask whether the norm helps or hinders the aims of inquiry. This was thespirit of Putnam's critique of Carnap's confirmation functions [Putnam1963]: the thrust of his essay was that Carnap's methods were not asreliable in detecting general patterns as other methods would be. Morerecently, learning theorists have investigated the power of Bayesianconditioning (see the entry on Bayesian epistemology). JohnEarman has conjectured that if there is any reliable method for a givenproblem, then there is a reliable method that proceeds by Bayesianupdating [Earman 1992, Ch.9, Sec.6]. Cory Juhl [1997] provided apartial confirmation of Earman's conjecture: He proved that it holdswhen there are only two potential evidence items (e.g., “emeraldis green” vs. “emerald is blue”). The general case isstill open.Epistemic conservatism is a methodological norm that hasbeen prominent in philosophy at least since Quine's notion of “minimalmutilation” of our beliefs [1951]. One version of epistemicconservatism, as we saw above, holds that inquiry should seek stablebelief. Another formulation, closer to Quine's, is the general preceptthat belief changes in light of new evidence should be minimal. Fairlyrecent work in philosophical logic has proposed a number of criteriafor minimal belief change known as the AGM axioms[Gärdenfors 1988]. Learning theorists have shown that wheneverthere is a reliable method for investigating an empirical question,there is one that proceeds via minimal changes (as defined by the AGMpostulates). The properties of reliable inquiry with minimal beliefchanges are investigated in [Kelly et al. 1995, Martin and Osherson1998, Kelly 1999].Much of computational learning theory focuses on inquirers withbounded rationality, that is, agents with cognitivelimitations such as a finite memory or bounded computationalcapacities. Many categorical norms that do not interfere with empiricalsuccess for logically omniscient agents nonetheless limit the scope ofcognitively bounded agents. For example, consider the norm ofconsistency: Believe that a hypothesis is false as soon as the evidenceis logically inconsistent with it. The consistency principle is part ofboth Bayesian confirmation theory and AGM belief revision. Kelly andSchulte [1995] show that consistency prevents even agents withinfinitely uncomputable cognitive powers from reliably assessingcertain hypotheses. The moral is that if a theory is sufficientlycomplex, agents who are not logically omniscient may be unable todetermine immediately whether a given piece of evidence is consistentwith the theory, and need to collect more data to detect theinconsistency. But the consistency principle—and a fortiori,Bayesian updating and AGM belief revision—rule out this kind ofscientific strategy.More reflection on this and other philosophical issues in means-endsepistemology can be found in sources such as [Glymour 1991], [Kelly1996, Chs. 2,3], [Glymour and Kelly 1992], [Kelly et al.1997], [Schulte and Juhl 1996], [Glymour 1994], [Bub 1994]. Ofparticular interest in the philosophy of science may belearning-theoretic models that accommodate historicist and relativistconceptions of inquiry, chiefly by expanding the notion of aninductive method so that methods may actively select paradigms forinquiry; for more details on this topic, see [Kelly 2000, Kelly 1996,Ch.13]. Booklength introductions to the mathematics of learningtheory are [Kelly 1996, Martin and Osherson 1998, Jain etal. 1999]. “Induction, Algorithmic Learning Theory and Philosophy” isa recent collection of writings on learning theory [Friend etal. 2007]. Contributions include introductory papers (Harizanov,Schulte), mathematical advances (Martin, Sharma, Stephan, Kalantari),philosophical reflections on the strengths and implications oflearning theory (Glymour, Larvor, Friend), applications of the theoryto philosophical problems (Kelly), and a discussion oflearning-theoretic thinking in the history of philosophy (Goethe).Supplementary Document: Basic Formal DefinitionsBibliographyBub, J. [1994]: ‘Testing Models of Cognition Through theAnalysis of Brain-Damaged Performance’, British Journal forthe Philosophy of Science, 45, pp.837-55.Chart, D. [2000]: ‘Schulte and Goodman's Riddle’,British Journal for the Philosophy of Science, 51,pp.837-55.Earman, J. [1992]: Bayes or Bust?. Cambridge, Mass.: MITPress.Feynman, R. [1965; 19th ed. 1990]: The Character of PhysicalLaw, Cambridge, Mass.: MIT Press. Induction, Algorithmic Learning Theory, and Philosophy,eds. M. Friend, N. Goethe and V. Harazinov (2007). Dordrecht:Springer, pp. 111-144.Ford, K. [1963]: The World of Elementary Particles, NewYork: Blaisdell Publishing.Gärdenfors, P. [1988]: Knowledge In Flux: modeling thedynamics of epistemic states, Cambridge, Mass.: MIT Press.Glymour, C. [1991]: ‘The Hierarchies of Knowledge and theMathematics of Discovery’, Minds and Machines 1, pp.75-95.––– [1994]: ‘On the Methods of CognitiveNeuropsychology’, British Journal for the Philosophy ofScience 45, pp. 815-35.Glymour, C. and Kelly, K. [1992]: ‘Thoroughly ModernMeno’, in: Inference, Explanation and OtherFrustrations, ed. John Earman, University of CaliforniaPress.Goodman, N. [1983]. Fact, Fiction and Forecast. Cambridge,MA: Harvard University Press.Harrell, M. [2000]: Chaos and Reliable Knowledge, Ph.D.Thesis, University of California at San Diego.Jain, S. et al [1999]: Systems That Learn 2nded. Cambridge, MA: MIT Press.James, W. [1982]: ‘The Will To Believe’, inPragmatism, ed. H.S. Thayer. Indianapolis: Hackett.Juhl, C. [1997]: ‘Objectively Reliable SubjectiveProbabilities’, Synthese 109, pp. 293-309.Kelly, K. [1996]: The Logic of Reliable Inquiry, Oxford:Oxford University Press.––– [1999]: ‘ Iterated Belief Revision,Reliability, and Inductive Amnesia’, Erkenntnis 50:11-58.––– [2000]: ‘The Logic of Success’,British Journal for the Philosophy of Science 51:4,639-660.––– [2007a]: ‘How Simplicity Helps YouFind the Truth Without Pointing at it’, in Induction,Algorithmic Learning Theory, and Philosophy, eds. M. Friend,N. Goethe and V. Harazinov. Dordrecht: Springer, pp. 111-144.––– [2007b]: ‘Ockham's Razor, Truth, andInformation’, in n Handbook of the Philosophy ofInformation eds. J. van Behthem and P. Adriaans, to appear.Kelly, K., and Schulte, O. [1995]: ‘The ComputableTestability of Theories Making Uncomputable Predictions’,Erkenntnis 43, pp. 29-66.Kelly, K., Schulte, O. and Juhl, C. [1997]: ‘Learning Theoryand the Philosophy of Science’, Philosophy of Science64, 245-67.Kelly, K., Schulte, O. and Hendricks, V. [1995]: ‘ReliableBelief Revision’. Proceedings of the XIIJoint International Congress for Logic, Methodology and the Philosophyof Science.Kuhn, T. [1970]: The Structure of Scientific Revolutions.Chicago: University of Chicago Press.Martin, E. and Osherson, D. [1998]: Elements of ScientificInquiry. Cambridge, MA: MIT Press.Ne'eman, Y. and Kirsh, Y. [1983]: The Particle Hunters,Cambridge: Cambridge University Press.Omnes, R. [1971]: Introduction to Particle Physics,London, New York: Wiley Interscience.Putnam, H. [1963]: “Degree of Confirmation and InductiveLogic”, in The Philosophy of Rudolf Carnap,ed. P.a. Schilpp, La Salle, Ill: Open Court.Quine, W.: [1951]: ‘Two Dogmas of Empiricism’,Philosophical Review 60, 20-43.Salmon, W. [1991]: ‘Hans Reichenbach's Vindication ofInduction,’ Erkenntnis 35:99-122.Schulte, O. [1999a]: ‘Means-Ends Epistemology’, TheBritish Journal for the Philosophy of Science, 50, 1-31.––– [1999b]: ‘The Logic of Reliable andEfficient Inquiry’, Journal of Philosophical Logic 28,399-438.––– [2000]: ‘Inferring ConservationPrinciples in Particle Physics: A Case Study in the Problem ofInduction’, The British Journal for thePhilosophy of Science, 51: 771-806.––– [2007]: ‘Mind Change Optimal Learningof Bayes Net Structure’, O. Schulte, W. Luo and R. Greiner(2007). In Proceedings of the 20th Annual Conference on LearningTheory (COLT), San Diego, CA, June 12-15.––– [2008]: ‘The Co-Discovery ofConservation Laws and Particle Families’, O. Schulte (2008). In Studies in History and Philosophy of Modern Physics, Vol39:2, pp 288-314.Schulte, O., and Juhl, C. [1996]: ‘Topology asEpistemology’, The Monist 79, 1:141-147.Sklar, L. [1975]: ‘Methodological Conservatism’,Philosophical Review LXXXIV, pp. 374-400.Other Internet ResourcesA number of Kevin Kelly's papers on Occam's Razor are posted on his website.Learning Theory in Computer ScienceInductive Logic Website on Formal Learning Theory and Belief RevisionRelated Entries confirmation | epistemology: Bayesian | induction: new problem of | induction: problem of | James, William | logic: inductive | Peirce, Charles Sanders | Popper, Karl Copyright © 2008 byOliver Schulte<oschulte@sfu.ca> |
|
