Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!uflorida!gatech!hubcap!ncrcae!usceast!park
From: park@usceast.UUCP (Kihong Park)
Newsgroups: comp.ai.neural-nets
Subject: Re: Data Complexity
Message-ID: <2957@usceast.UUCP>
Date: 18 Oct 89 15:14:04 GMT
References: <4542@imagen.UUCP>
Organization: University of South Carolina, Columbia
Lines: 36
To: ncrcae!hubcap!gatech!rutgers!cmcl2!lanl!opus!ted
In-Reply-To: <TED.89Oct16113856@aigyptos.nmsu.edu>
Cc:
Bcc:

In article <TED.89Oct16113856@aigyptos.nmsu.edu> you write:
>
>ivan bach is very enthusiastic, but relatively uninformed about recent
>developments in determining the complexity of finite sequences.
>
I agree with your comments regarding the outdatedness and errors of Ivan's
statements. As to describing the information content of a sequence over a
finite alphabet set, the algorithmic information complexity measure as
developed independently by Kolmogorov, Chaitin, and Solomonov can be fruitfully
applied here.
Basically, they define the complexity of a sequence as the size of the
minimum program which faithfully generates the sequence, if run on some
universal turing machine. Thus, for a DNA sequence to encode maximum 
information, i.e., be maximally patternless, its algorithmic complexity 
must nearly equal the length of the sequence.
As to Ivan's comments about the applicability of entropy to represent the
efficiency of information coding in a network, many workers in the field
have realized that for a given task, a more or less 'adequate' network size
should be strived for. One of the principal motivations for doing this is
the empirical observation that if a network size is 'too large' compared to
the complexity of the task at hand, then it may generate solutions which do
not 'generalize' well, given the opportunity to do so. What 'generalization'
means is a different problem altogether, but what this observation shows us
is that one has to constrain the degree of freedom of a network to entice it
to capture the most compact representation. This constitutes so to say, the
'minimal program'. Thus, the problem at hand is knowing the optimal size of
a network for a given task. I do not see an easy way how entropies can help
us in solving this correspondence problem.

>			Dem Dichter war so wohl daheime
>			In Schildas teurem Eichenhain!
>			Dort wob ich meine zarten Reime
>			Aus Veilchenduft und Mondenschein

It's interesting to notice that some people equate our profession to that
of poets. Is this a revival of romanticism ?