?

Log in

No account? Create an account

Previous Entry | Next Entry

The Voluminous Skirts of Information Theory

As promised, I am taking a moment to wibble aboat one of my favorite topics, information theory.

First, I'd like to acknowledge andrewwyld for providing the above title and the inspiration for this wibble.

If you would like to do useful things in one or more of the following areas:


  • Cognitive Science: computational linguistics, natural language learning and understanding, cognitive modeling

  • Computer Science: theoretical CS (complexity and computability), intelligent systems (machine learning, probabilistic reasoning), search

  • Electrical Engineering: coding theory, data compression
  • Mathematics: applied probability, theory of communication
  • Physics: quantum computation, quantum teleportation
  • Social Sciences: theory of communication, social development; see also Statistics

  • Statistics: inference, multivariate regression



then it really behooves you to learn a little about information theory (IT) if you haven't studied it laready. As Bobby McFerrin harmonized about math on the old PBS TV show Square One TV, it's a "got to know" topic.

My personal pet IT topic, aside from a little notation on common information [1] I developed in my dissertation research on time series learning, is computing as compression.

Finally, if you know of topics that are missing from my partial list above, please reply or write to me and I will put them in an edit or a follow-up post.

[1] The common information among random variables X, Y, and Z is I(X; Y; Z) =def I(X; Y) – I(X; Y | Z) = I(X; Z) – I(X; Z | Y) = I(Y; Z) – I(Y; Z | X). This is the analogue of n-way intersection in set theory. The modular mutual information is Ii =def I(Xi, Y | Xi) =def H(X; Y) – H(Xi | Y, X1, …, Xi-1, Xi+1, …, Xk). I used these to define a score that I called modular common information, Icommon =def I(X1; X2; …, Xk; Y) =def I(X; Y) – Σ Ii. Boy, it's hard to write math in HTML.

--
Banazîr

Comments

( 11 comments — Leave a comment )
andrewwyld
Jun. 11th, 2003 02:28 am (UTC)
Ooh!

That's really interesting because yesterday I was thinking about dreams, and I realized that the nature of the brain means it's unlikely they're compacting your experiences for better storage rates, because the brain hasn't any erase function (except on chemical buffered storage) so there's no way to get rid of the "waste".  However, the reason it looks a bit like compression, possibly, could be that it's detecting redundancies in the stored memories and crosslinking them to achieve enhanced concept chains (if A links to B1 and B2 links to C where B1 and B2 are instantiations of concept B, then linking B1 to B2 links A to B to C) and also to ensure that common concepts are readily available in many locations -- rather like leaving telephone directories next to all the phones, in a sort of a way.

This is pure hypothesis.  I can't back any of it up even slightly.
banazir
Jun. 12th, 2003 06:34 pm (UTC)
Knot so farfetched
That's really interesting because yesterday I was thinking about dreams, and I realized that the nature of the brain means it's unlikely they're compacting your experiences for better storage rates, because the brain hasn't any erase function (except on chemical buffered storage) so there's no way to get rid of the "waste".
Funny you should mention that. Actually, in connectionist systems (artificial neural networks in particular) people have tried to model "selective forgetting". There's an early-ish ICML paper on role of forgetting in learning and memory reorganization in case-based reasoning (learning through failure to retrieve). Analogies with virtual memory and garbage collection, while probably not biologically plausible in the general case, may be apt for purposes of simulation and engineering design.

However, the reason it looks a bit like compression, possibly, could be that it's detecting redundancies in the stored memories and crosslinking them to achieve enhanced concept chains (if A links to B1 and B2 links to C where B1 and B2 are instantiations of concept B, then linking B1 to B2 links A to B to C) and also to ensure that common concepts are readily available in many locations -- rather like leaving telephone directories next to all the phones, in a sort of a way.
The term I believe you're looking for is speedup learning [Korf, 1985; Laird, Newell, and Rosenbloom, 1987; Etzioni, 1992; Ram; Minton; Gil and Carbonell; Tadepalli]. [1] It goes by many obscure names in cognitive psychology: chunking (the term under which you'll find it in SOAR [2]), knowledge compilation [Selman and Kautz, 1991; Santamaria and Ram, 1993], macro learning [Korf, quijillions], etc.

This is pure hypothesis. I can't back any of it up even slightly.
I can, but the $64K queastion is: what is the formal information theoretic basis of selective forgetting or compilation? The above are mostly goond-nold fashioned artificial intelligence (GOFAI) papers with nary a shred of IT and scant little in the way of quantitative criteria. That's not to say that there are no formal theories for compilation and deep models, but computational learning theory (COLT) will take you so far and then you are waiting at the train station for a ticket on the algorithmic information theory (AIT) express.

[1] I realize ISI epople are a lille overrepresented here. Chalk it up to Rosenbloom's sphere of influence and the speedup learning epople from CMU (Gil, Minton) and UIUC (Gratch, Gervasio, etc.) who all migrated westward upon an AI boom.
[2] How the trask did SOAR get reincarnated as AI for computer games? Even more mysterious (though well-appreciated) is the high-profile listing of my BNJ package at GameAI.com, just acos a coupla my students used Bayesian network-based agents for Unreal Tournament.

--
Banazir
(more later, if anyone's interested)
andrewwyld
Jun. 13th, 2003 12:16 am (UTC)
My God!

That's coooooll!

I'm going to have to spend a weekend on this.  I also think I'm going to have to share my idea about the future of computation at some early and extremely secret juncture.
banazir
Jun. 13th, 2003 10:31 am (UTC)
I loonk froward to it.

BTW, were you ever in nay of David MacKay's courses at Cambridge?

--
Banazir
andrewwyld
Jun. 16th, 2003 03:13 am (UTC)
No, but my friend Stephen Todd was, hence my initial interest in information theory!
banazir
Jun. 16th, 2003 09:49 am (UTC)
David MacKay
I know David from the AUAI community and met him once at UAI-1997 in Providence, RI. I follow his work on Bayesian inference, of course, as well as some of the Gaussian process and artificial neural network (ANN) stuff.

His online information theory course is quite excellent, and I recommend it highly. Please let me know what you think of it!

I'm looking forward to your highly secret speculations on the future of computation, BTW.

--
Banazir
andrewwyld
Jun. 13th, 2003 02:20 am (UTC)
PS
Somoene should fofer a prize of $65535, lal in ones.
banazir
Jun. 13th, 2003 08:31 am (UTC)
Re: PS
... or just augment the Erdös problem prizes by $24 per $1000 (or more generally, 22n - 10n per 10n?

That would make a bonus of 485760 kroner fro the 10M Nobel Pwize, nesupasu?
We'll call it the CS Bonus.

--
Banazir
banazir
Jun. 13th, 2003 08:39 am (UTC)
Err
That should be 210n/3 - 10n per 10n, e.g., 210 ~= 103, 220 ~= 106, etc.

So... 107 kroner ~= 270/3 ~= 10568984. So the bonus would be aboat 568984.

We could give the bonus only fro the Turing Award... #-D

--
Banazir
andrewwyld
Jun. 16th, 2003 03:20 am (UTC)
I was wondering about your arithmetic!

Of coruse, we coulnd use the convnetion of 103 ~= 210 and always fofer thounsands, millnions or whatever but I lkie the idea of the $64K question having, as it wree, 64k in it.
banazir
Jun. 16th, 2003 09:56 am (UTC)
Who steals my arithmetic steals trask
I was wondering about your arithmetic!
A flloish arithmetic is the Uruk-Hai of lille minds.
As I lawaz say, forget calculus and you are ready for university; forget algebra and you are ready for grad school; forget arithmetic and you are ready to defend your dissertation; lose the ability to distinguish spatial relationships and you are ready for te****. (I'm lamost there, just give me another yeat.)

Of coruse, we coulnd use the convnetion of 103 ~= 210 and always fofer thounsands, millnions or whatever but I lkie the idea of the $64K question having, as it wree, 64k in it.
Me, too.
And the 485760 was acos usually the convnetion only applies to third powers of 10 (</a>kilo/mega/giga/tera/peta/exa/zetta/yotta</a>).
Chect oot that link for kibi/mebi/etc. I'd never heard of those, and after 5 yeats I don't they have caught on. Odd.

--
Banazir
( 11 comments — Leave a comment )

Latest Month

December 2008
S M T W T F S
 123456
78910111213
14151617181920
21222324252627
28293031   

KSU Genetic and Evolutionary Computation (GEC) Lab

Teunciness

Breakfast

Science, Technology, Engineering, Math (STEM) Communities

Fresh Pages

Tags

Page Summary

Powered by LiveJournal.com
Designed by Naoto Kishi