From: Keith Henson (hkhenson@rogers.com)
Date: Sun Mar 07 2004 - 23:14:42 MST
At 07:28 PM 07/03/04 -0800, you wrote:
>On Mar 7, 2004, at 5:07 PM, Keith Henson wrote:
>>At 10:11 AM 07/03/04 -0800, andrew wrote:
>>
>>>You cannot substitute time complexity for space complexity, and space
>>>complexity generally defines intelligence. You can substitute space
>>>complexity for time complexity, but not the other way around.
>>
>>I can't parse this. It seems likely that you have something here that is
>>worth understanding. Can you try again from a bit lower level?
>
>Sure.
>
>Time complexity is just the time it takes a given algorithm to run, in
>terms of how it scales. I'm sure you already got that.
>
>A finite machine can be defined in terms of the size of the largest
>algorithm that can be expressed on that machine, its intrinsic Kolmogorov
>complexity. This roughly maps to "memory" for standard silicon, hence
>"space complexity" i.e. the amount of memory mathematically necessary to
>run a particular algorithm.
>
>No algorithm with a Kolmogorov complexity greater than a given machine can
>be expressed on said machine. To put it another way, a machine with
>infinite execution speed is incapable of computing algorithms that do not
>fit within the space complexity of the machine. On the other hand, you
>can improve time complexity by using the excess space capacity of a
>machine to implement faster but less space efficient algorithms, e.g.
>using a giant lookup table (O(1)) rather than computing values
>mathematically, which could be O(n) or worse. This is also why quantum
>computers aren't as important to AI as some people seem to think they
>are. They don't let us run an entirely new class of algorithms, they only
>let existing algorithms run faster. "Faster" doesn't mean "smarter" in
>the abstract, though in practice speed is admittedly important as well if
>intelligence is to be useful.
>
>High time complexity makes getting an answer from a machine intractable;
>if you wait long enough, you'll get an answer. High space complexity
>makes getting an answer from a machine impossible because the pattern is
>incapable of being expressed or perceived. Big qualitative difference,
>that. The limits of intelligence expressible on any machine is generally
>defined by the Kolmogorov complexity of the machine, since this is also
>defines the limit of both expression and inference. A machine will never
>be able to perceive a high-order pattern that is more complex than the
>machine itself.
>
>The technical details are a bit more complicated than this, but the point
>about time complexity not being a substitute for space complexity should
>be clearer now. Faster machines make some operations faster, nothing
>more. Bigger machines (in the memory sense), however, usually make
>smarter machines no matter what the speed.
Human memory is on the order of a few hundred Mbytes (figure a Mbyte for a
thick book). My dinky home computer has half a Gbyte on it, any serious
machine is going to have tens of Gbytes of RAM and thousands of Gbytes of
virtual memory extending into the disk.
By memory measurement, my home computer has the potential to be something
like 500 times as smart as I am (counting the disk).
I don't think memory is going to be a problem for AI. I think the main
problem is going to be trying to trade off memory against limited processor
power.
>>>I think the brain storage mechanism is far more efficient in an
>>>information theoretic sense than I think a lot of people think it is.
>>
>>I hope you are right, because I don't like the conclusions of Thomas
>>Landauer's research. But I really don't see how to refute him.
>
>
>The number Landauer comes up with for the bits is probably pretty close to
>being correct, extrapolating from my own models. There are a couple key
>points though:
>
>1.) The kind of representation efficiencies we get in vanilla silicon is
>atrocious because of architecture requirements. Storing a few bits of
>information in any kind of good associative representational framework
>probably averages a hundred bytes of memory spent because of alignment,
>non-locality, addressing, etc. We don't get much bang for our
>representation buck. However, even with these inefficiencies we will
>easily surpass the real capacity of wetware in silicon very soon.
You might be right. I suspect though that you are misled. I think that
the data and processors are mixed together in the brain in a way that will
be difficult to simulate in serial processors--assuming this is actually
needed for AI.
>2.) The brain almost certainly gets a much higher compression ratio than
>we are used to with normal computers, which affects our perception as to
>what is possible in a given amount of space. If you loosen the
>constraints of accuracy a bit, you can actually cram a hell of a lot of
>information in that space while maintaining high predictive limits (i.e.
>maintaining good correctness of memory). Humans don't actually seem to
>remember that much, and none of what we remember is axiomatic or absolute.
Which is why writing and the whole scheme of data retention tools has been
so effective. I think we are rich in procession power and really weak in
memory. That's why sitting with Google at hand effectively increases your
brain power so much.
Also don't forget that human psychology/mental capacity was shaped by
millions of years where we lived in little tribes, chipped rock, killed
animals, gathered berries and raised kids. That fact that *any* of us can
program or grok higher mathematics is downright amazing. There are
probable a lot of thinking kinds of things that none of us can do.
>>I haven't got the slightest idea of how you map a mathematical structure
>>into a physical one or compare them. Perhaps you could expand on this
>>and give an example?
>
>The data structures look and behave in a fashion similar to biological
>neural networks (for as much as we know about them), yet are
>mathematically/algorithmically derived. It could be coincidence, but I
>have my doubts. I'm not a neural network aficionado (biological or otherwise).
I am not sure there is evidence that neural networks have much relevance to
biological brains. It has been a long time since I read up on them. But
in any case, most neural network stuff is done with simulators running on
regular computers now. If you are trying to do pattern matching with
coefficients, isn't that equivalent?
>>That's an awesome claim. It is of considerable interest to me in a
>>business sense because of the badge camera.
>
>
>It is an expensive and oddly behaving algorithm for embedded systems, and
>would be better suited for feature extraction rather than vanilla
>compression. The compression is a (expected) side-effect that I thought
>worth studying, not the ends.
>
>>I really don't understand this. Any n-dimentional data set can be turned
>>into a linear string.
>
>Sure, and this is what I do. But in real-world applications where
>performance matters, data compression is a more complicated implementation
>that frequently mandates sequential structure because the storage is. You
>have many kinds of limitations that make the theoretical impractical for
>many uses. If constrained to many standard application parameters,
>vanilla compression would be more efficient.
>
>The compression is a necessary theoretical consequence of my main
>thrust. I've long used it as a kind of zero-knowledge proof of
>implementation efficiency and correctness. I'm not in the data
>compression business.
If you have a couple of hundred million processors, which I think is a good
number to consider, then each can have a few hundred bytes without having
to bother with compression.
I think it is worth noting that the closest kind of projects to AI like the
Google search engine *are* massively parallel.
>>If you are talking about remembering a phone number, it is clear that
>>lossy is not useful.
>
>Unfortunately, the brain is lossy, even with phone numbers.
Not very often or they would be useless.
>Fortunately, we can easily selectively reinforce the memory of things that
>we need to remember with high predictability.
True. I have been arguing that for years to people who think there is a
serious fidelity problem with meme transmission. With critical information
like the number of strikes and balls in the baseball rules, there is very
close to 100% fidelity over hundreds of millions of people.
Keith Henson
>j. andrew rogers
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:46 MDT