Le 15-juil.-05, à 20:55, scerir a écrit :

Ben Goertzel:
but this doesn't mean induction is unformalizable,
it just means that the formalization of cognitive-science
induction in terms of algorithmic information theory
(rather than experience-grounded semantics) is

Imo, induction only works when the complexity
of the data is not larger than the complexity
of the theorem (or the model, or the theory,
etc.) we wish to prove. In other words, if those
data are special, induction does not work.
Isn't this another parameter for that formalization?

Actually this is a subject of a whole sub-branch of theoretical computer science called Computational Learning Theory.

You are right that automated induction cannot work on sequences as complex as they minimal description, but you are optimist if you think the reverse is true, at least in term of class of sequences recognizable by a unique machine. (An individual computable sequence is always trivially inferable if only by the stupid machine which knows only the program of that sequence, so the interesting notion in learning theory is the learning of class of sequences (or of computable total function). A class of sequence is learnable by a machine if for any sequence taken from that class and presented by finite pieces the machine eventually (after a finite time) output a program predicting or computing the sequence.

The class of ALL computable sequences (or the set of computable total functions) cannot be recognized in that sense by any learning machine. By using genuinely the notion of "dovetailing" it is not hard to show that all Recursively (Mechanically) Enumerable set of computable total function can be learned. By weakening the criteria of identification, some hierarchies of learnable class can be studied. Putnam and Popper have wrote some important prehistorical papers. Important works by BLUM. But also by Blum and Blum. Blum wrote with her husband the paper on the "NON UNION THEOREM", which, roughly speaking, says that if you evaluate intelligence of machine by the learnable class, then (in a sense) What is uncomputably more intelligent than a machine? Two machines! (where a sequence is recognize if one of the two machine get the correct predicting program).

BLUM L. & BLUM M., 1975, Toward a Mathematical Theory of Inductive Inference. Information and Control 28,.pp. 125-155.

My favorite paper (a classical one):

CASE J. & SMITH C., 1983, Comparison of Identification Criteria for Machine Inductive Inference. In Theoretical Computer Science 25,.pp 193-220.

A book (there is a new edition quite augmented by I have not the reference): OSHERSON D.N., STOB M.and WEINSTEIN S., 1986, Systems that Learn, MIT press.

See also:

http://www.cis.udel.edu/~case/colt.html and links therein,

See perhaps a short summary of the main result by Case & Smith in the section 5.2 of:



Reply via email to