on Chaitin, Solomonoff, etc

[gusl]

http://groups.yahoo.com/group/theory-edge/message/2640

Hello Vlad,

I am going to try to change the tenor of my comments on
compressibility et al. I also wanted to let things cool down a bit
before I replied.

--- In theory-edge@y..., vznuri@e... wrote:
> hi JW
>
> I recall when I was an undergraduate I was more likely
> to use words like "insipid" or "insidious" or other harsh/shrill
> adjectives being flung around lately on the list in describing
> other's research. keep in mind, in science, your credibility is
usually
> inversely proportional to the extremeness of your adjectives.
> (yes, I know, mea culpa).

Just for the record, I never used the word "insipid" on this list.
Also, with reference to mathematics and computer science I should
probably be regarded as pre-undergraduate based on my academic
background (business).

> I think undergraduates/scientific newcomers
> are likely to be upset by how arcane & theoretical
> some theories are. that was my case. it bothered me to hear about
some
> scientists achieving fame for very theoretical results that seemed
to
> have no application. imho another factor in the recent criticisms
> on the list.

Fair enough. Time Series Analysis (TSA) is probably the discipline
which I should be discussing, but, unfortunately it is most probably
off-charter. However, computer science theory (Solomonoff's Theory of
Prediction and inductive inference) comes closer to being useful in
analyzing data series. The general intent when analyzing data series
in this context is to determine the type of regularity that allows
for better than random predictions about future instances of data
from the same or similar sources.

Please note that the 32-bit integer series 4,7,5,9,3,2,7,2,12,3,6,12
is highly compressible because all values are <14 and >1, but this
kind of compression is not of interest to the practical predictor of
the next value, who is much more likely to be interested in whether
the next value is > 6, (6 being the mean). This is a VERY important
point about compression and predictability, don't let the apparent
simplicity disguise the importance here.

> there is no requirement that people here understand an entire
> theory before posting, but especially if you want to be critical
> of one, you'd better have all your p's and q's in order.
>
> again I find your post a bit vague/nebulous on the exact/specific
> problems you have with c-k complexity. I dont consider myself an
> advocate of c-k complexity, but naive objections do bother me enough
> to address in detail. re: some of your semi-specific
> comments.

I really wish that those in more applied fields had taken more from
the implications of Solomonoff's work. I know that I have been doing
just that for fourteen years (as have numerous others, but without
the rigor that true academics could bring to generalizing and
formalizing the very powerful concepts).

"Essentially, combining the ideas of Epicurus, Ockham, Bayes, and
modern computability theory, Solomonoff has successfully invented
a "perfect" theory of induction. It incorporates Epicurus's multiple
explanations idea, since no hypothesis that is still consistent with
the data will be eliminated. It incorporates Ockham's simplest
explanation ideas since the hypotheses with low Kolmogorov complexity
are more probable. The inductive reasoning is performed by means of
the mathematically sound rule of Bayes."

M. Li and Paul Vitanyi, "An Introduction to Kolmogorov Complexity and
Its Applications" Second Edition, Springer-Verlag, 1997, p. 323.

The definition of induction from logic (not mathematics) is "... the
process of inferring a general law or principle from the observations
of particular instances."

Source: Oxford English Dictionary

It is a very powerful combination, computers and inductive inference.
However, imho, the work to automate and generalize the theory of
prediction and inductive inference has been quite limited.


> I am going into quite a bit of detail because I like major aspects
> of c-k complexity & your criticisms strike a nerve. I still feel you
> are resisting/not giving due credit where it is due.
>
> - let me agree with you that c-k complexity is a relatively new
field and
> every new field has a problem with fuzzy terminology. sometimes it
> can take decades for the terminology to standardize. even in
> a field as well established as e.g. linear algebra, you sometimes
> have a lot of different names for "eigenvalues". but again, please
> give exact reasons why particular terms are fuzzy or the terminology
> is being abused.
>
> - "fudge factors". suppose there is a constant which one can
> adjust. in c-k complexity you have these & the theory is referring
> to limit cases. not a nebulous use of constants. one cannot accuse
> complexity theory of using a fudge factor because O(n) notation
> skips constant factors-- that is precisely the point. to throw out
> unnecessary baggage. please be specific on what you consider a
> "fudge factor"
>

Li and Vitanyi refer to fudge factors within the context of comparing
different methods of quantifying information content. I hasten to add
that they weren't referring to the description of language
constant "c".

> - "the body of compression research needs to be greatly improved
> for finite strings". but you have so far made almost no comments
> on the status of compression on finite strings. its a vast field,
> image processing is only one of the tips of it. lempel-ziv encoding
> is a good place to start. the statement "there needs to be
more/improved
> research into [x]" is basically a tautology in any scientific
context.

The extreme success (already acknowledged) of compression has
overshadowed, imho, the more important (and vastly more difficult)
problem of practical prediction from a finite set.

>
> - "if researchers in finding predictive structure were more
successful
> they wouldn't need funding and the job opportunities would be
> ridiculously abundant".. have no idea what you are talking about.
are
> you annoyed that one cannot be paid to invent compression algorithms
> or do basic research [y]? but that is true of so many subjects.

No, actually, if the work of academics dealing with prediction were
valuable then such researchers could earn tremendous fees for
consulting and advising on projects in which discovery of predictive
structure is needed. It also follows that such researchers could use
their methods to greatly outperform economists who proclaim the stock
market to be a random walk. (Sorry, that last sentence was decidedly
off-charter, but I know that you personally have an interest in
nonrandom walks in the markets)

> - you say you prefer solomonoff as more applied, but I & anyone else
> reading this list would still have no idea why you say he is
> more applied than chaitin. it is totally reasonable to prefer his
> approach over chaitin's, but why, specifically? can you give an
> example? keep in mind imho chaitin's theory probably encompasses
> solomonoff's, is solomonoff even still alive?

Yes, he is alive and I believe he is 76.

See the above quote concerning Solomonoff, which is definitely an
outline for a much more applied use of these concepts.

Also, please see this paper from Solomonoff himself entitled "Does
Algorithmic Probability Solve the Problem of Induction?":
http://world.std.com/~rjs/isis96.html

> - chaitin/kolmogorov probably have no pretenses to try to be
> "applied" so imho it is useless to criticize them on the grounds
they
> are not. c-k theory is extremely abstract, I gave a theorem as an
> example of that aspect. if you want practical compression algorithms
> you are really barking up the wrong tree.
>

I don't need practical compression algorithms. I create my own
prediction algorithms and I am working to generalize and further
automate my concepts, which happen to coincide, on a theoretical
level, with Solomonoff's ideas. I am also interested in learning the
state of computer science theory on the subject so that I *might*
eventually be capable of publishing some of my results from a
theoretical perspective.

> - you say you are interested in applying compression to
bioinformatics--
> please expand on this if possible.

This relates to: more compression == more understanding of the
patterns and regularities in a given data set. There is a tremendous
amount of brute force computing going on with the huge body of data
in bioinformatics. In my next email to the list I will give three
specific sources so that I don't come off as vague.

>
> - please expand on solomonoff's theory of prediction & "inductive
> inference" & how you have found it useful, if possible.

I have found algorithmic inductive inference very valuable in
prediction of stock prices. I am currently preparing to hire experts
in computer science and statistics so that I can hasten the
generalization and automation of my research.

> - would you object less to chaitin if he didn't use the
term "random"
> and simply stuck to "incompressible"?

Yes, because now that I understand the field a bit, I have realized
that I am exploiting predictability in data sets for which the
generally found compressibility does not serve the practical purpose
of actually being useful for prediction. The easy compression relates
to the 12-item string mentioned above, as well as other obvious
structure in data.

>I agree it is a bit of a paradox
> to call anything random when no cutoff point is defined. but it is
a bit
> like criticizing complexity theory for calling exponential
algorithms
> "intractable". how can one problem be "tractable" and another
problem
> be "intractable"? if you think about it I think you will find the
> exact same problem.
>
> - [taming chaos via math] "I have a problem with folks that believe
that we
> have reached the end of our taming potential" .. but nobody is
asserting
> that. however I do agree that undecidability results are seen as
much
> greater obstacles by the scientific community
> than they really are, much of my own research focuses
> on this paradox.

Agreed.

>
> - "there is more order (probablistic
> regularity) than the existing body of computer science theory
> recognizes, and I am upset that Chaitin, Kolmogorov, and Solomonoff
> haven't further explored it." but JW, surely you must acknowledge
> they are in fact the pioneers in defining the boundaries. they are
> at the forefront of exploration.

Agreed, I guess I am just naive enough to think that the scientific
process can go much faster. I should also be thankful that it hasn't,
as this fact has allowed me to work for myself on a truly beautiful
problem in mathematics, prediction.

> everyone in mathematical fields probably
> would agree that order seems to be inexhaustable. there is a great
> deathbed quote by newton on the subject, about science as
> finding pretty stones on a beach "while the vast ocean of truth
> lay undiscovered before me". most non-hubristic scientists would
agree..
>
> - "The
> boundary between the island and the sea of randomness has not been
> set in stone by one Gregory Chaitin, but he would like to believe
> that he has." sorry, you have no quote. again imho you are reading
> more into his claims than exists. afaik chaitin phrases almost all
his
> findings in the typically conservative scientific fashion.

My apologies. I got carried away with the randomness quote (Godel,
Turing, Chaitin) and thought it was sufficient to imply that.

> you continue to fight the basic breakthrough status of chaitin's
> understandings. it may be true
> solomonoff/kolmogorov came up with the ideas first, but there
> is much to be said for someone who actually publicizes & makes the
> scientific community aware of the true importance of a set of ideas.
> chaitin fits this very reputable role; imho mandelbrot is
> an example of another scientist-publicist along these
> lines.

I don't much care who came up with it first. Randomness should be
more closely associated with predictability, compression more closely
with information content. Chaitin does not do this. I think I know
what the problem is, I am working on it. It has to do with
practicality, which, I freely admit, is generally not part of the
repertoire of a theoretical mathematician.

I have a feeling that the type of predictability to which I refer
only makes a data set compressible (and only a tiny percentage, at
that) after the data set is quite huge (on the order of 10^12
datapoints). I may or may not go into this further, I hope that Vlad
is not the only one left following this thread.

> if you ordered chaitin's new book, then you may be one of the first
> of anyone on the list to do so, I commend you & hope you will
> favor us with future (specific) comments on the book.

Yes, I await its arrival.

>
> thanks for the excellent link on chaitin's sci am article (1975),
> a very nice introduction to the subject although surely a bit
> dated (by a quarter of a century now =). for anyone
> who missed it.

Best wishes,

Jaffray

Comments

[mathemajician.livejournal.com]

He's a director at IDSIA which is where I work.