To follow this blog by email, give your address here...

Monday, August 27, 2012

Finding the "Right" Computational Model to Support Occam's Razor

(This is a rather abstract science-y post, beware....  If you don't like theoretical computer science, you'll be bored and/or baffled....  But if you do -- or if you like being bored and/or baffled, read on!  These are some technical speculations that I believe may have interesting conceptual/philosophical implications....)

One question I've been thinking about a lot lately is: What is the "right" computational model?

Occam's Razor is a powerful tool in AI, both in machine learning / data mining applications, and in a more ambitious AGI context.   But the formulation of Occam's Razor, in a practical computer science context, contains a certain arbitrariness.

Occam's Razor says to prefer the simpler hypothesis; or more subtly, to prefer hypotheses, in some sense, proportionally to their simplicity.

But what's "simple"?

An old friend of mine, Mariela Ivanova, once said: "Simplicity is so complex, I couldn't understand it."

Sometimes folks define "simplicity of X" as "length of the shortest expression of X in a specified programming language P" -- or something like that.   But of course this is too crude, so there are variations, such as "runtime of the program giving the shortest expression to X in language P"; or various weighted combinations of length and runtime as Juergen Schmidhuber and colleagues have explored in their work on "frontier search."

One can also look at a "total computational cost" simplicity measure such as "the minimum amount of space and time resources needed to compute X" on a specific machine M.

The program-length simplicity metric is related to the Solomonoff-Levin measure on program space, which defines the probability of a program as inversely related to the length of the shortest program computing it.  Variant simplicity metrics lead to other measures on program space

All this is very nice and elegant, to write about and to prove theorems about.  But it all depends on a seemingly arbitrary assumption: what is the programming language, or machine, involved?

There's some nice old theory saying that, in a sense, for the case of "shortest program length," this choice doesn't matter.  Any universal Turing machine can simulate any other one, given a constant overhead.

But in practice, this constant may be very large, and it sometimes does matter.

And for other simplicity measures, such as "total computational cost", no comparable theories are known.

To complete the story of the computer science basis for Occam's Razor, it seems what we need is a theory of what is the "right" programming language or machine; what is the "right" computational model.

Of course, this comes down to deciding what "right" means.

What I'd like to find are some nice theorems of the form: IF you want a programming-language/computational-model satisfying simple, elegant criteria A-B-C, THEN you  must use a programming-language/computational model essentially equivalent to P*.

If we had a good theory of this nature, then the choice of which programming-language/computational-model to use, would come down to choosing criteria A-B-C.

I looked around a bit and couldn't find any really great theoretical results of this nature.   But it's possible they exist and I just didn't figure out the right terms to search for.

My intuition is that: one can formulate some simple, elegant criteria that mathematically imply the right computational model is some sort of parallel graph rewriting.

In other words, I suspect there will be some simple, elegant criteria that are equivalent to the use of something vaguely like core Haskell.

What kind of criteria am I thinking of?  I know I'm getting a little fuzzy at this point, but I'm thinking about stuff like: "Computing W and computing f(W) should take the same amount of space and time resources," for cases where it seems intuitively obvious that W and f(W) should take the same amount of space and time resources.

Might it be possible, by imposing a few natural criteria of this nature, to derive results implying that the only way to fulfill the criteria is to use some sort of simple parallel graph rewriting based computational model?

I strongly suspect this is possible, but I've been thinking about this a while, and (a familiar story for me lately!) haven't found time to spend the needed hours/days/weeks to try to work out any details.

There is a math literature on abstract rewrite systems, as well as on the practical use of parallel graph rewriting systems to do computation.   These may provide raw material to be used to prove theorems of the sort I'm alluding to.  Or maybe some theorems equivalent to what I'm dreaming about exist somewhere, and I just didn't find them yet!

So, let's suppose someone proves theorems of the nature I'm suggesting.  What would that get us?

It would tell us, in an elegant and intuitively compelling way, what computational model to assume when applying Occam's Razor.

Of course, someone could always say "That math is nice, but I see no reason to accept your criteria.  Sure they're simple and elegant, but I happen to prefer a computational model fulfilling different criteria."   That's inevitable.

But: A community sharing a common intuition regarding which mathematical criteria are elegant and simple, would have a strong mutual intuitive reason to assume a common computational model, and thus to apply the Occam's Razor heuristic in the same way.

Sunday, July 29, 2012


A brief fictional dialogue to brighten up your July ....

So, I understand that, in a quest to get new insights into how to guide the Singularity in a positive direction for everyone, you took a massive dose of acid and queried the universe for inspiration?

Yes, that's right.  A massive dose of liquid acid, to the tune of Scriabin's "Prometheus."  On my friend's new psychedelic seastead, well out into international waters.  He brews the stuff there and you take it out there -- beyond the jurisdiction of any government, so it's all totally legal.


Wow indeed.  Of course, there's always the risk of some pirates or military gunboats popping up to ruin the party.  But nothing like that has happened so far.

Well that's good.  Enjoy it while it lasts, I guess.


So -- what insights did the universe have for you?  Anything you can can share with us, back here on the boring old plane of everyday reality?

Heh…  Well, in a sense I guess.  But, you may not like the message….

Stop toying with me, O Great One!   Come on, shoot…

OK, well… so, we tried to focus the trip on the Singularity, right?  We were trying to use that state of mind to get insight into Friendly AGI, paths to Singularity, and so forth….

But you kept getting distracted by the dolphins doing flips on the wave next-door?

No… there were no distractions.  We were pretty fast outside the physical realm of being, right up close to the pulsing heart of being.   But the overwhelming message we got from the pulsing heart of being was simply: "YES, THE UNIVERSE IS CONTINUING" ... i.e. "YES, THE UNIVERSE IS CONTINUING TO REVOLUTIONIZE ITSELF, THAT'S WHAT IT DOES" ... i.e. "YES, THE UNIVERSE IS CONTINUING TO REVOLUTIONIZE ITSELF, THAT'S WHAT IT DOES, IF YOU LOOK AT IT FROM THE VIEW OF A LINEAR FLOW OF TIME" ....

In other words, what we're thinking of as "Singularity" is just yet another manifestation of the under/over-lying "enlightenment" that is already immanent in the universe, and that was manifested in other big changes like the cooling-down of the initial miasma into solid matter, and the emergence of life, and of intelligence, and of language, and of machinery and technology, etc. ....  The process of re-valuing all its values and decomposing and recomposing all its forms is what the universe is all about -- and if you view it from something closer to the universe's perspective, without the limitation imposed by the "linear flow of time" mindset, then it doesn't really seem like development or progress, it looks more like a web of inter-creating process....

So, we were looking for insight into how to maximize the continuity of human consciousness as Singularity approaches and unfolds, so that we can experience Singularity while having the sense of remaining ourselves, and so that the superhuman uber-bots can emerge and roam the galaxy and invent amazing new stuff without killing cute little human babies and puppies in the process -- but what we got was a big dose of "human life and death are not particularly more or less significant than all the other forms and patterns in the Cosmos, and regardless of humanity, the profound wider and deeper intelligence of the universe goes on and keeps on unfolding and doing stuff that will look to human-like minds like creation and destruction."

I see.  So the message the universe gave you is: sure, the Singularity is going to happen, like lots of other Singularities have happened, in this Singular universe … this Singular Universal mind.  But as for the particularities of you mere humans, who really gives a crap?  

Sort of like that -- but without any negative emotional tone.  Humans are here now, within certain subjectively perceived temporal moments and spatial regions.  Other temporal moments and spatial regions don't contain humans.  That's just the way it is.  The universe is rich in various forms and patterns, and humans are part of that, but just a teeny tiny part.  Crap is part of that too! .... The view of forms and patterns as unfolding and developing is just one perspective on the whole web of patterns, which seems interesting from a human view, and less so to other sorts of minds or mindplexes or being-webs or whatever….

There was also a strong sense of the presence of other, individuated non-human minds out there -- faintly amused by us humans' panicked worry about the continuation of various of our pet patterns through our funny little quasi-illusory historical time axis....  These other minds were a little more aware of their own relationship to the Cosmos, and their own role in regards to the overall web of process....

It's not that individuated minds like ours are unnecessary or irrelevant -- we are part of the overall process; patterns emerge in us and emerge from the arrangement of us and other things ... without individuated minds like ours, various other more abstract and broad patterns wouldn't be able to exist ... but the particularities of our minds and beings don't really "deserve" the profound significance that we are habituated to attach to them...

Yes, I get it.  The message is quite clear, at any rate.

As to whether I like it ... I guess that's not a question with a well-defined answer.  It's not the sort of thing you can like or dislike, really.

But, hmmm ... so for you, was it a life-changing experience?  Are you going to give up the search for Friendly AGI, and submit yourself to the cosmic will of the universe as it unfolds?

Heh, no, not really … now that I'm back here in the ordinary dimension, my enthusiasm is undimmed for my quest to create friendly AGI and a positive Singularity for all humans and animals.  But sure, the trip did sorta fill my head with a deeper sense of the limited scope of this quest.

At the moment I look at the quest for a human-positive Singularity more like I look at the quest to build a really nice habitat for my pet bunnies, so they can live in the back yard and enjoy the fresh air and grass without getting eaten by cats or flooded by the rain.  It's important in a sense -- I love the bunnies and want them to be happy and live.  But if it doesn't work and a cat gets in and kills them, well, so it goes ... life goes on...