NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/comp/ai/neuraln/3338

Text File | 1992-08-29 | 3.8 KB | 81 lines

Xref: sparky comp.ai.neural-nets:3338 comp.ai:3251 comp.theory:1833
Newsgroups: comp.ai.neural-nets,comp.ai,comp.theory
Path: sparky!uunet!haven.umd.edu!darwin.sura.net!jvnc.net!yale.edu!yale!gumby!destroyer!ubc-cs!fornax!jamie
From: [e-mail] (Jamie Andrews)
Subject: Re: measuring complexity (was Re: Kolmogorov Complexity)
Message-ID: <[e-mail]>
Organization: CSS, Simon Fraser University, Burnaby, B.C., Canada
References: <[e-mail]> <[e-mail]> <[e-mail]>
Date: Thu, 27 Aug 1992 18:18:10 GMT
Lines: 69

In article <[e-mail]> [e-mail] (Seth Breidbart) writes:
|In article <[e-mail]> [e-mail]
|(Jamie Andrews) writes:
|
|>     So, for instance, the K-complexity of a given list of
|>numbers might be defined as:  the length of the shortest program
|>in pure LISP such that the value of the s-expression "(result)"
|>is that list.  (Well, I guess it would have to be pure LISP plus
|>some arithmetic functions.)  The "length" of a program might be
|>defined as the total number of atoms plus the total number of
|>sets of parentheses, to give a more realistic idea of the
|>storage space needed by the program.
|
|If any number will fit in one atom, then all strings have complexity
|bounded above by some small number.

     Good point, I should have said that the length of an
integer is its log, or something like that.  When I said "atom"
I was thinking only of LISP's symbols.  I suppose we would have
to factor in the possibility of encoding via large numbers of
distinct atoms:  the length of each symbolic atom should be the
log of the number of distinct atoms in the program.

|>     A measure of K-complexity relative to some standard suite
|>of function definitions could be given, too.  The relative
|>K-complexity would be the length of the shortest pure LISP
|>program containing that suite of definitions, _minus_ the length
|>of those definitions.  The minimal program could then make use
|>of the "knowledge" in the standard functions without having to
|>derive it.
|
|Since the answer is almost always undecidable, I doubt you could get
|any interesting results.

     Not interesting to automata theorists, perhaps, but the
original poster was interested in AI applications where the
minimal program is taken as an encoding of the knowledge.
Randomized algorithms (see below) might be interesting to
complexity theorists too.

|If a randomized algorithm is any that _can_ output the string, a
|trivial one exists: (output random bit; maybe loop).  If it _must_
|output the string, or can only output the string (or die), or outputs
|the string with some minimal probability, then you haven't gained
|anything from randomness.

     I suppose I was intending to mean something like this:  an
epsilon-delta algorithm A which, when given a string S, outputs
a program P such that
(a) P outputs S, and
(b) with probability (1-delta), the length of P is within
    epsilon percent of the length of the minimal program which
    outputs S.
(It's trivial to output *some* program which outputs S -- it
would be just (defun (result) (quote S)), where S is the listing
of the string.  The problem is getting the length down, for long S.)

     This might not be the exact formulation needed... is this
problem trivial too?  Do we need some tighter epsilon-delta
bound?  What is the sample space -- all strings of length k
or less, or all strings output by programs of length k or less,
or something else?  What is the distribution on the sample
space?  And what would the algorithms look like, and what would
be their time and space bounds?  I think these are pretty
interesting questions.

--Jamie.
  [e-mail]
"Every \item command in item_list must have an optional argument." LaTeX pg.168