I recently watched a charming documentary on Shannon, called The Bit Player [0]. The film has some annoying flaws, but it really highlights how much Shannon was outside the box for a mathematician. He seems to have been extremely playful, and tinkering with hardware projects throughout his life.
How he even managed to make a (very limited) endgame chess computer [1] ~70 years ago still blows my mind.
It's interesting to note why this was considered AI in 1952 and some may not consider it to be AI today. The AI was the search algorithm to find an effecient solution to the maze, not the mouse being able to navigate it later in a second run. The second run was just a demonstration of it having found the solution demonstrating it's intelligence. The actual intelligence was it's first run through the maze. Almost any configuration of the maze could be solved using algorithms like depth first, breadth first and a star search (didn't check which one the video demonstrates). Even though the algorithm was trivial it's ability to be applied to problems of today is still extraordinary. Nerural networks being equally trivial algorithms capable of remarkable things. Id argue this is as much AI today as it was back then, just more people know how Shannon performed this magic trick.
>> The AI was the search algorithm to find an effecient solution to the maze, not the mouse being able to navigate it later in a second run.
But that's not the whole story! The program can update its solution of the maze when the maze changes, but it is capable of only changing that part of the solution that has actually changed. When Shannon changes the maze and places Theseus in the modified part of the maze, I kind of rolled my eyes, sure that it was going to start a new search, all over again, but I was wrong: it searches until it finds where the unmodified part of the maze begins, then it continues on the path it learned before.
It seems that, in solving the maze, the program is building some kind of model of its world, that it can then manipulate with economy. For comparison, neural nets cannot update their models - when the world changes, a neural net can only train its model all over again, from scratch, just like I thought Theseus would start a whole new search when Shannon changed the maze. And neural nets can certainly not update parts of their models!
This demonstration looks primitive because everything is so old (a computer made with telephone relays!), but it's actually attacking problems that continue to tie AI systems of today into knots. It is certainly AI. And, in "early 1950's", it's AI avant la lettre.
Great observation. The solution to the update problem is relatively simple. It doesn't do a search again on update. Instead everytime it encounters an update in what it knows, it just changes the data stored in memory. All it is doing is updating its learned representation. After this it still knows what the other obstacles are without having to do DFS or BFS again. If the solution was a graph, it just deleted a edge it still knows what all the other edges are. If it encounters another change it updates the state of the graph again.
With regards to Neural Networks, if they are given a reward function, which can be dynamically evaluated (in this case did I reach the end or not) they are pretty good at learning without feedback.
You make it sound simple, but from my point of view the ability to update one's
learned representation requires a representation that can withstand being
updated. I mentioned John McCarthy's concept of "elaboration tolerance" in
another comment, i.e. the ability of a representation to be modified easily.
This was not a solved problem in McCarthy's time and it's not a solved problem
today either (see my sibling comment about "catastrophic forgetting" in neural
nets). For shannon's time it was definitely not a solved problem, perhaps not
even a recognised problem. That's the 1950's we're talking about, yes? :)
Sorry, I didn't get what you mean about the dynamically evaluated reward
function.
>For comparison, neural nets cannot update their models - when the world changes, a neural net can only train its model all over again, from scratch
I mean, sure they can. Training a neural network is literally nothing but the network's model being updated one batch of training examples at a time. You can stop, restart, extend or change the data at any point in the process. There's whole fields of transfer learning and online learning which extend that to updating a trained model with new data.
edit: Also in a way reinforcement learning where the model controls the future data it sees and updates itself on.
The problem I'm describing is formally known as "catastrophic forgetting".
Quoting from wikipedia:
Catastrophic interference, also known as catastrophic forgetting, is the
tendency of an artificial neural network to completely and abruptly forget
previously learned information upon learning new information.
Of course neural nets can update their weights as they are trained, but the
problem is that weight updates are destructive: the new weights replace the old
weights and the old state of the network cannot be recalled.
Transfer learning, online learning and (deep) reinforcement learning are as
susceptible to this problem as any neural network techniques.
This is a widely recognised limitation of neural network systems, old and new,
and overcomging it is an active area of research. Many approaches have been
proposed over the years but it remains an open problem.
I always say that AI is a forever moving goal post. It is simply a task a human can do that you wouldn't expect a machine to be able to do. So as soon as a machine can do it, people no longer consider it intelligent (i.e. it is just A*, it is just a chess engine, it is just a network picking up on patches of texture, ..., it isn't really "intelligent").
This is because we originally thought "only a human would be able to play chess", "only a human would be able to drive a car". The thinking there is that if we were to solve these problems, we'd have to get closer to a true artificial intelligence (the kind that today we'd call "AGI" because "AI" doesn't mean anything anymore).
This line of thinking has been shown to be pretty faulty. We've come up with engines and algorithms that can play Go and Chess, but we aren't any closer to anything that resembles a general intelligence.
Well, GPT3 is definitely not a general intelligence, but I would say it's much closer than deep blue. Progress is happening! It's just a question of how far and fast we run with the goalposts.
Shannon did not use the word intelligence to describe the mouse in this demonstration - instead, he talked about learning. That's why the second run was considered more important than whatever algorithm was used to solve the maze.
To that end, I'm curious about their cache invalidation solution. Are there timestamps, or is it a flag system?
You are being far, far, far too generous with the complexity of this design if you think there's some kind of cache invalidation. It's a purely mechanical computer, which means it is going to be very simple in abstract design, because doing anything even mildly complex would require an insane amount of space.
I can't find design documents for this, but I can make a pretty educated guess about its design.
Each square has two relays, representing the number of left turns necessary to exit the square. Each time a whisker touches a wall, a signal is sent to a mechanical adder which will add 1 to the relays in the space. When the mouse enters a square, a "register" is set with a value, based on if it entered from the left, top, right, or bottom, then the mouse is turned and the register decremented until it hit 0, then the mouse attempts to walk in the indicated direction.
Where the mice starts on x and turns the number of times in each square. You can actually put the mouse down anywhere and it will exit the maze, if the walls are left unchanged.
If my memory serves me right, you are right. I think I've read that it was implemented with two relays per cell. These encode the last cardinal direction the mouse exited the cell in.
> I'm curious about their cache invalidation solution
My guess: there would be a model somewhere (probably a binary relay map of walls) of the maze, and as soon as the mouse hits an inconsistency, this map is updated. So there isn't really a cache, it's more like a model, or perhaps you can think of collision-based cache (model) invalidation. The mouse probably then follows the solution to this modified maze, modified only insofar as it has measured modifications.
Is there a technical specification somewhere? I'd certainly be curious to read it.
What a wonderful era of creativity in machine design. Building a machine to reproduce the behavior of living systems goes a long way back, and this mouse acting like a mouse makes me think of a great documentary on automata, spending some time talking about the people and politics around building these fantastically expensive robotic birds and swans and whole towns driven by a clock. [1]
Building a machine that mimics neural processing is just a continuation of that tradition. One other machine that amazed me is Paul Westons's numa-rete, an early attempt at neural networks composed of 400 "synapses" which can count the number of objects on its surface without any CPU to coordinate it, just direct parallel analog computation. A good explanation is here [2], this was in 1961.
`What will be done is to show what is inside, revealing how little intelligence it really had. However, many uninitiated persons who tried and failed at the time to “trick” it into error by, e.g., inserting objects within holes in larger objects were ready to believe that it was intelligent`
Here is our current modern version of mouse maze competition: https://youtu.be/NqdZ9wbXt8k?t=86 ... its so smooth. Would love to learn more how to build one of these if anyone has suggestions starting with basic servos for a light introduction.
I don't think you'd want to use servos to drive the wheels for something like this. You probably want very fast steppers (so you can get precise rotations) or geared DC motors (so you can move very fast). I'm assuming the robot has some very basic black and white computer vision, or maybe even simple laser range finders, which would be simpler to work with and more likely to generalize to new mazes.
"The norms of consumer culture and domesticity were disseminated via new and popular forms of entertainment – not just the television, which became a fixture in middle-class American households during the 1950s, but also women’s magazines, popular psychology, and cinema. Shows promoting the values of domesticity, like Leave it to Beaver and Father Knows Best, became especially popular. These shows portrayed the primary roles of women as wives and mothers. Lucille Ball, in I Love Lucy, inevitably met with disaster whenever she pursued job opportunities or interests that took her outside of the household." [0]
What is striking about this video is not only the advancement of technology but also women actively working outside the home which was counter culture for the time even though the one woman sitting down symbolically is in a subordinate position with the man standing over her.
Of note, he talks about using Bell systems for guided missiles.
I always want to reinforce that cutting edge computing systems and the defense department have always been bedfellows. The DoD isn't new to technology, even machine learning or reinforcement learning (The US Air Force sponsored the Dartmouth Conference on AI after all).
Honestly this is pretty impressive even today. It'd be fun to work with a school class to implement it as a project. I mean it's the kind of thing you can gloss over and say, here's the algorithm but then to actually build it is really interesting. Maybe a lego kit or something.
I'm no fan of Youtube but...not being able to increase the playback speed is highly sought after when I watch videos on any sites (like the OP on att.com). Here is YT's version of the same video [1].
Edit: I removed the link because the pixelation was unbearable.
I couldn't find any design details online for how this was built. I'd love to read more technical details.
Since this is purely mechanical, it is probably extremely simple in design. I suspect that there are two relays (representing 2 bits) under each square's reed switch, encoding the number of "left turns" to make upon entering that square. The whiskers probably trigger a simple incrementer for each square to keep track of the number of left turns to make. When the mouse is dropped in a space, it probably turns left to reorient itself, but then knows the direction to walk once it reaches a point in the path where it has solved before because the number of left turns it needs to make in that space is already solved.
The relays are behind the maze- what's under the maze is a couple of arms with electromagnets that move to drag the mouse around the maze.
In fact the "relays" are an electromechanical computer. I don't know much about the computers of that era, but since this is in Bell Labs in the early '50s, it may have been the model VI:
Mechanical arms under the maze not much different than an XY plotter, move the mouse similar to Pac-Man but without needing a game controller or human player attached.
Under the maze an auto position (re)locator, followed by directional XY servo advancing plus a N/S/E/W impact sensor provide the input data for the memory to learn the maze from. This stuff actually all could be implemented in hardware with no memory needed.
All you need to do is place the mouse anywhere, grab the joystick and head on directly to the target like Pac-Man without any enemies or time limit. This would be a really easy game so far.
If you didn't see that wall coming and hit one anyway, the gameboard lets you know. At this point you already know which direction you are going so now you really know where that wall is. The gameboard doesn't need to tell you whether it's a N/S/E or W impact, surely you could figure it out.
Or if you did have just enough memory for a map of the maze but no _software_ hooked up to the sensors you could run the joystick yourself whatever direct path you might want and that would be enough of a maze map, whether you entered the data manually or could automatically somehow.
Then if the gameboard were able to play the movements back from memory when the mouse was placed at the identical starting position, that would not require code either. You could even play back from less than the full path on a previously memorized trajectory.
While you're at it memorize the entire maze anyway, this is just a preliminary training session, later there will be a quiz.
Then, without looking at the maze any more, just do the exact same series of joystick movements needed to get from anywhere directly to the goal as long as you know where the mouse is at the start. The gameboard itself tells you exactly where the puck is dropped and you just take it from there. If you can't remember and take a wrong turn, the gameboard throws a flag and lets you know it's bad. So you can refresh your memory. But you'll have to remember which way you are going, which way you were coming from and which ways were right or wrong, even better than when you were looking and hit the wall anyway. It hardly ever happens and it was just a little wall wasn't it.
Well, that's training. When you get really good then you don't need to look at any maze to begin with, and you can handle any combination of maze rearrangement including during real time. As long as it's truly solvable and you've got enough time.
When the machine actually did learn without a human or a joystick, that's ML. The final result was simply the full details of the entire landscape as if it was static. No actual higher machine intelligence necessary, the intelligence was naturally still contained within Shannon.
He made sure the machine would move in the useful ways and collect the desired data as it goes no matter how long it takes to memorize the maze.
His program allowed any maze to be memorized automatically, then perform without obstacle. The memory alone could guide the performance perfectly after that, but in real-time an unexpected obstacle had to be "learned the hard way" again, however after the memory was updated the new obstacles were perfectly dealt with after that. It only learned what it needed to learn and knew when it had enough. The rest of the time it just ran perfectly until more learning was needed. And it always got it right.
Keep in mind how many full-speed collisions it takes for the mouse just to memorize enough of the maze to get to the goal the first time.
No forgetting anything but a single element at a time, and only when it undoubtably needs updating.
In this case a single bit, each changed bit only allowed if it gives a more realistic representation of the maze, building only on what is absolutely known.
He had more digital memory to work with than almost anyone in history at the time, even though it's just one relay per bit somebody was bound to think of numbering the possible states 0 and 1 sooner or later.
The actual electro-mechanical processor and relay memory banks were much bigger than would ever fit under the gameboard. Tonnes.
All making up a static program which reads the gameboard sensors in real time, controls the mouse along as much proven path as there is before searching, and builds the variable maze map in memory systematically but mindlessly. Every time the routine is complete on a static maze it's always correct.
So the program itself is good enough to be burned to a ROM and you need almost insignificant RAM.
RAM is only for the intermediate variables needed by the program which can always start zeroed, plus a single variable in memory of the exact position within the current maze, and the maze itself at any one time to whatever degree it is known.
When it seems fairly intelligent but the machine didn't learn a damn thing compared to how smart it should be, that's current AI.
Shannon had an auto-learning ML machine including its immutable _software_ which on any static playing field eliminated all mistakes then after self-learning did exactly what was expected without mistake from that point forward. Other features built on top of that were the only thing that made the mouse hit a wall again. Even though a human could do it the first time without hitting any walls if looking at the gameboard. When the human can not see the gameboard and has to depend on the sensors alone, he will make mistakes the pre-programmed robot will not make. But the machine is not expected to learn the exact same path to success that the human does even when the exact same goal is reached. Shannon did it without ever having anything of consequence be unknown in memory except what could be easily audited in full detail whenever needed because it was small and to the point.
From the title I was sure that this would be some horrible misuse of "machine
learning" to stand-in for "AI" but while Shannon himself never uses the term in
the video, the title seems accurate enough.
To summarise: a model mouse, named Theseus, is moved around a maze by a system
of electromagnets placed under the maze and guided by an electromechanical
computer (made with telephone relays). The computer is from Bell Labs and given
the date listed for the video ("early 1950's") it may be a Model VI.
The program that drives the mouse is a combination of a search algorithm with
some kind of modular memory. The mouse first finds its way around the maze by
successivly trying a set of four moves at right angles. The sequence seems to
be: move forward; if that's impossible, turn 90° CW; repeat. This eventually
finds a path to the end of the maze, where a goal is placed (possibly magnetic).
In more modern terms, the program learns a plan to navigate the maze. Once the
plan is learned it can be re-used any number of times to solve the maze without
any more searching.
The interesting thing is that, if the maze changes, the program only needs to
replace part of its learned plan. Shannon demonstrates this by moving around
some of the walls of the maze, which are modular segments. Theseus initially
enters its searching routine, until it finds its way to the part of the maze
that it knows already. After that, it's smooth sailing, following the plan it
already knows.
I have no idea what that technique is that does that. If I guessed, I'd guess
that the program has a model of its world -a map of the maze- or, more
interestingly, it builds one as it goes along. When the maze changes, the
program updates its model, but it is able to update only as much of the model as
corresponds to the part of the world that has really changed. This suggests some
kind of object permanence assumption, an encoding of the knowledge that if the
state of some entity in the world is not known to have changed, then it has not
changed. Or, in other words, some solution to the frame problem (which was
actually described about a decade later than Shannon's demonstration).
Note well that modern AI systems very rarely exhibit this ability. For instance,
deep neural networks cannot update their models - not partly, not wholesale.
Like I say, I have no idea what the approach is that is demonstrated. It may be
something well-known but rarely used these days. It may be something that
Shannon came up with before John McCarthy fathered AI and so it never really
caught on as an AI approach. If anyone knows, please do tell, I'm very curious.
In any case "Theseus" (rather, its AI) seems to exhibit what McCarthy called
"elaboration tolerance", making formal representations of facts that can be
modified easily:
What a grave misunderstanding! What he is demonstrating is remembering, or memory.
It appears that the state of the mouse is [X, Y, Heading], where X and Y are discrete positions in the available cells.
Once the maze has been solved by "a rather involved strategy of trial and error", the solution is saved, and for any of the known states, the mouse "remembers" its way to the exit of the maze.
All learning amounts to remembering. A machine learning model is basically remembered weights. Everything we've learned is what we remember as solidified in our neurons, etc.
Note that learning is not about discovering yourself. You also learn if you're capable of remembering (and optionally applying) something that somebody else taught you. Students e.g. learn a formula for X, the periodic table, etc.
And this contraption not only remembers (that is, learns), but also has an algorithm to figure the solution in the first place (that is, tries and discovers).
So the title "machine learning" or even "AI" is perfectly legitimate. It's not GAI, but it's also not 2020 (not that we have GAI in 2020).
>All learning amounts to remembering. A machine learning model is basically remembered weights. Everything we've learned is what we remember as solidified in our neurons, etc.
That's "not even wrong", as Pauli would say. Your paragraph suffers from using a shaky non inversible analogy:
Machine learning often uses an analogy for the brain, neurons, activation functions, etc. Some accuracy about the real world is sacrificed in that analogy for the sake of being useful and to have something to reason with and shared taxonomy. We accept that loss for the sake of being productive and for lack of actual equivalents.
What your first paragraph did is use that analogy of the brain used in machine learning, that is shaky to begin with, and use it to reason about the biological brain as if we did not have the actual thing.
In other words, we had a biological brain that we clumsily modeled to get work done in ML, and the paragraph used that model to reason about the brain itself. Similar to how you translate from French --> English --> French and get a different output than the input.
Remembering certainly plays a role in learning, though it is but one component. For it to be what learning is, everything has to be exactly the same with every instance.
To use the analogy, a machine learning model returns predictions/output for instances it has not necessarily seen. Our brain produces outputs based on situations that had not yet happened, at least not in the 'anisotropic time' universe, before that.
>Your paragraph suffers from using a shaky non inversible analogy
That's neither here nor there though. The brain doesn't have to follow a specific model (e.g. the shaky model ML uses, and I alluded to), for the analogy to work.
It just has to have memory and remembrance as a core attribute of learning, which it does.
Whether this happens through neurons and weights or some other mechanism, it's still remembering. Your counter-argument focused on implementation details.
>Remembering certainly plays a role in learning, though it is but one component. For it to be what learning is, everything has to be exactly the same with every instance.
Well, remembering doesn't just "play a role", it plays the biggest role in learning. It's not even remotely optional: without remembering there's no learning.
And inversely, discovering ourselves what we learn or applying it are both optional. I can listen to a professor tell me about something someone else discovered, and never apply it, but as long as I remember that information, I have learned it.
And, of course, as I already wrote, the contraption doesn't just remember but also discovers the solution (and can even re-apply it).
>Well, remembering doesn't just "play a role", it plays the biggest role in learning. It's not even remotely optional: without remembering there's no learning.
This is different from the phrase in your first paragraph that stated:
>All learning amounts to remembering.
There is a difference between saying that remembering is a necessary condition for learning, and saying that remembering is learning.
Memory plays a role in learning. Does it play the biggest role? Let's assume it does. Is learning only memory? I don't think so. Did you not mean to say that all learning is remembering and but wrote so even though your thoughts on that are more nuanced? Probably.
>And inversely, discovering ourselves what we learn or applying are both optional. I can listen to a professor tell me about something someone else discovered, and never apply it, but as long as I remember that information, I have learned it.
See, here again I'll have to disagree. I'm looking at it from the standpoint of output and outcome of a system where that output is not simply information retrieval.
Let's say the information is about driving. I can have a driving manual memorized. Can I remember that information about driving? Yes. Have I "learned" driving? No.
>Memory plays a role in learning. Does it play the biggest role? Let's assume it does. Is learning only memory? I don't think so.
The end result of learning (having learnt) is, I'd say, only memory.
If the memory is of static information or dynamic state (the difference between a file with data and a program's runtime loaded with state) it's still however just memory.
What else would it be?
Sure, the process of learning, on the other hand, can take different forms. Those would be analogous to loading a memory store via different mechanisms.
>Let's say the information is about driving. I can have a driving manual memorized. Can I remember that information about driving? Yes. Have I "learned" driving? No.
Let's say we can distinguish between two types of learnable things.
When it comes to information from the digits of pie or the lyrics of a song, or the periodic table and many other things, having such things memorized is enough for us to say we "learned them".
Your example with driving, however, is not about mere learning some information, but about learning an activity. In your example we can surely say you've learned the contents of the driving manual. That's not the same as learning to drive, but nobody said it is. It is still learning the information within the manual, though.
Now, for learning to drive one would need to learn some/all of the same information (perhaps in another form, simpler, more colloqual, etc), and also the motions involved, how to respond to various road situations, etc. This however is a "loading the memory part".
Isn't the end result the same though? Information (somehow, not really relevant how) stored in the brain of the person that learned to drive (including things like "muscle memory")? The process is not the same as memorizing static information (e.g. a piece of text), but the end result is still a brain that has a new state, similar to an RAM or SSD that has a new state.
See also my point above regarding static vs dynamic memory.
1952. After 70 years, millions of people, and billions of dollars, it makes sense that our algorithms are more sophisticated and our definitions more precise.
How he even managed to make a (very limited) endgame chess computer [1] ~70 years ago still blows my mind.
[0] https://thebitplayer.com/
[1] https://www.chess.com/article/view/the-man-who-built-the-che...