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
>> flawed...
>
> 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:
http://iridia.ulb.ac.be/~marchal/publications/M&PI_15-MAI-91.pdf
Bruno
http://iridia.ulb.ac.be/~marchal/
Received on Sat Jul 16 2005 - 10:06:58 PDT