The computer that can navigate the subway

How do you get from Moorgate to Piccadilly Circus?

Here, let me help you.

Here, let me help you.

It may look easy to you (or does it?), but it’s borderline impossible for artificial intelligence. Or it was, until Google DeepMind (that employs several physicists) unleashed its Differentiable Neural Computer (DNC). According to the DeepMind scientists, neural networks are very good at recognizing patterns, or finding the best move for a given situation (as their own AlphaGo did). However, they cannot stack up a complex sequence of actions, because they cannot remember.


A representation of DNC: the “controller” neural network at the center takes in the data coming from the left, stores it on the right, or links it to information already there. Then combines them all to produce the answer at the bottom. Credit: DeepMind

tumblr_nklw7hj3o51t55xupo1_400In a way, you could think of data as ingredients, and of the neural network as a somewhat limited cook, that can only work sequentially on them. So it can’t set aside the dough for a pie while it prepares the filling. Chef DNC can: it makes the dough, puts it in the memory, works on the filling and then finishes our data pie.

Whether we realize it or not, when we plan a subway journey we store and link information all the time. At each stop we make a decision: stay on, get down, or change. Then we remember where we are, where we started and where we’re headed. That’s how DNC do.

Big whoop—you may say—public transportation apps and satnavs have been doing this for years. Indeed they have, and are probably better at it. But they were specifically programmed for that, and that’s all they can do.

DNC wasn’t: it learned to compute paths, starting from sets of randomly connected dots (graphs, if you want to be fancy). It would memorize the different connections (what points are connected, with what line), then try to find the shortest path between two points. Time after time, it would be told whether the answer was correct.


An example of randomly connected dots, like those DNC was trained on—only those were a lot more complicated!

Once it learned, DNC was able to navigate the London Tube—quite the random graph after all—, but it could just as easily guide you through the NY subway, plan out the solution to a simple puzzle, or answer complex questions about family trees.

This video shows DNC memorizing connection (who’s whose child or sibling) and answering “who is X’s maternal great uncle?” I had to take a moment to parse the question—and I’m a reasonably competent human. Try asking that to a satnav!

Often in artificial intelligence, what the machine can do is not as important as what it might learn to do. And DNC proved it can learn a lot.

Cover photo: I think we got out at the wrong station, CC-BY-NC-ND The Hamster Factor, via Flickr. Some rights reserved.

If you want more
  • The Nature paper detailing how DNC works and how it was trained.
  • A very nice post on the DeepMind blog about DNC
  • Want to see DNC solve one of many tasks on a puzzle? There’s a video of that, too.

Why teach a computer to play Go

Two opponets face off in an ancient strategy game. However, only one of them is a person, and he’s not winning. The historic victory of AlphaGo has made quite the round in the news. Why is it so important?

Now for the short review: Go is a Chinese board game. One of its distinguishing features (at least for computer scientists) is the mind-boggling number of possible moves and countermoves,  which make direct calculations—like the ones used in chess software—unfeasible.

Enter AlphaGo, an artificial intelligence created by a division of Google called DeepMind to learn the game. It didn’t just learn: in 5-game series, it swept the European champion Fan Hui 5-0, then punished Lee Sedol, one of the best players in the world, by 4-1. It was the first time an artificial intelligence ever even beat an expert human player.

A Go-playing computer, however capable is not of much use in itself. But board games have a lot in common with real-life problems: they pose hard questions, require to take complex decisions, and evaluate pros and cons of several options.

At the same time, they are a controlled and well-defined environment, there is a limited number of possible moves, strategies and situations, and it’s possible to assign objective values to each option or outcome. In other words, the game is a testbed for real-life decisions.

For computers it’s even more: while for us learning comes naturally, they have to learn how to do that. AlphaGo, for example, was not programmed specifically to play Go, but just to observe games and soak up the best strategies. If we put it in front of a different problem or a different game, it could use the same system to quickly learn and solve that.

Computers trained on poker or Jeopardy!, for example, now help doctors with their diagnoses. Google says they hope, in the future, “to help us address some of society’s toughest and most pressing problems, from climate modelling to complex disease analysis.”

But something tells me that, before they save the world, they will use AlphaGo for really important things: find us more cat videos.


Cover photo: from above, CC-BY-NC tommpouce, via Flickr. Some rights reserved.