Xref: utzoo alt.cyb-sys:32 comp.ai.neural-nets:975
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!wuarchive!psuvax1!rutgers!shelby!mcnc!uvaarpa!uvaee!aam9n
From: aam9n@uvaee.ee.virginia.EDU (Ali Minai)
Newsgroups: alt.cyb-sys,comp.ai.neural-nets
Subject: Data Complexity
Message-ID: <517@uvaee.ee.virginia.EDU>
Date: 6 Oct 89 02:26:16 GMT
Organization: EE Dept, U of Virginia, Charlottesville
Lines: 58



I have a question which might or might not make sense. Still, since
it is of great interest to me, I shall be grateful if people share
their views, suggestions and references on this topic with me. Of
course, I shall be particularly grateful if someone pointed out the
absurdity of the whole issue.

The question is this:

Given deterministic data {(X,Y)} where X is in a finite interval of
n-d real space and Y is in a finite interval of m-d real space,
what *structural* measures (if any) have people suggested for
the "complexity" of the data?

This immediately raises several other issues:

1) What possible notions of "complexity" might one admit in this regard?

2) What might be the *order* of this complexity? Should it, for example,
be defined over the set of all points, all pairs, all triplets etc.?

3) Given that the data is not uniformly distributed over the domain (i.e.
it is "lumpy"), what assumptions must be made regarding the blank areas?
Should these be statistical? (probably yes).

4) How can such a "complexity" measure be made scale-invariant?

etc.

Also, what about such complexity measures for continuous functions?
I mean measures defined structurally, not according to the type
of the function (e.g. degree for polynomials).

My gut feeling is that some sort of information-based measure is
appropriate, but whatever is used must be efficiently computable.
Have other people tried to deal with this problem? Since I am sure
they have, where can I find the material? What would be the appropriate
area of mathematics to look for such references? I am currently searching
approximation theory, statistical modelling, maximum-entropy theory,
measure theory, information theory, complexity theory (both system
and computational) and non-linear dynamics literature. Obviously, I
will miss more than I will find, hence this request. A particularly
helpful thing would be names of journals which regularly carry material
relevant to this issue. Also, is the International Journal of General
Systems still published? If not, what did it turn into? Or rather, who
carries articles about "the theory of things", "the calculus of
indications" etc? I am extremely interested.

Thank you.

Ali Minai
Dept. of Electrical Engg.
Thornton Hall,
University of Virginia,
Charlottesville, VA 22903.

aam9n@uvaee.ee.virginia.edu