What's after AlphaGo?

What's AlphaGo?

AlphaGo is a system that can play Go at least as well as the best humans. Go was widely cited as the hardest (and only remaining) game at which humans could beat machines, so this is a big deal. AlphaGo has just defeated a top-ranked human expert.

• AlphaGo Nature paper (Silver et al 2016)

Why is Go hard?

Go is hard because the search-space of possible moves is so large that tree search and pruning techniques, such as those used to beat humans at Chess, won't work - or at least, they won't work well enough, with a feasible amount of memory, to play Go better than the best humans. 

Instead, to play Go well, you need to have "intuition" rather than brute search power: To look at the board and spot local (or gross) patterns that represent opportunities or dangers. And in fact, AlphaGo is able to play in this way. It beat the next best computer algorithm "Pachi" 85% of the time without any tree search - just predicting the best action based on its interpretation of the current state. The authors of the AlphaGo Nature paper say:

“During the match against Fan Hui, AlphaGo evaluated thousands of times fewer positions than Deep Blue did in its chess match against Kasparov; compensating by selecting those positions more intelligently, using the policy network, and evaluating them more precisely, using the value network—an approach that is perhaps closer to how humans play.”

How does AlphaGo work?

AlphaGo is trained by both supervised and reinforcement learning. Supervised learning feedback comes from recordings of moves in expert games. However, these are finite in size and used naively, would lead to overfitting. 

Instead, in AlphaGo a Supervised Learning deep neural network learns to model and predict expert behaviour in the recorded games, via conventional deep learning techniques. Then, a reinforcement learning network is used to generate reward data for novel games that AlphaGo plays against itself! This mitigates the limited size of the supervised learning dataset.

Of course, AlphaGo also wants the play better than the best play observed in the training data. To achieve this, the reinforcement learning network is further trained by playing pairs of them (networks) against each other - mixing the pairs up to prevent policies overfitting each other. This is a really clever feature because it allows AlphaGo to go beyond its training data.

Note also that the neural networks cannot possibly fully represent a sufficiently deep tree of board outcomes within their limited set of weights. Instead, the network has to learn to represent good and bad situations with limited resources. It has to form its own representation of the most salient features, during training.

The neural networks function without pre-defined rules specific to Go; instead they have learned from training data collected from many thousands of human and simulated games.

Key advances

AlphaGo is an important advance because it is able to make good judgments about play situations based on a lossy interpretation in a finitely-sized deep neural network.

What’s more, Go wasn’t simply taught to copy human experts - it went further, and improved, by playing against itself.

So, what doesn't it do?

The techniques used in deep neural networks have recently been scaled to work effectively on a wide range of problems. In some subject areas, narrow AIs are reaching superhuman performance. However, it is not clear that these techniques will scale indefinitely. Problems such as vanishing gradients have been pushed back, but not necessarily eliminated.

Much greater scale is needed to get intelligent agents into the real world without them being immediately smashed by cars or stuck in holes. But already, it is time to consider what features or characteristics constitute an artificial general intelligence (AGI), beyond raw intelligence (which AIs now have).

AlphaGo isn't a general intelligence; it's designed specifically to play Go. Sure, it's trained rather than programmed manually, but it was designed for this purpose. The same techniques are likely to generalize to many other problems, but they'll need to be applied thoughtfully and retrained.

AlphaGo isn't an Agent. It doesn't have any sense of self, or intent, and its behaviour is pretty static - its policies would probably work the same way in all similar situations, learning only very slowly. You could say that it doesn't have moods, or other transient biases. Maybe this is a good thing! But this also limits its ability to respond to dynamic situations.

AlphaGo doesn't have any desire to explore, to seek novelty or to try different things. AlphaGo couldn't ever choose to teach itself to play Go because it found it interesting. On the other hand, AlphaGo did teach itself to play Go… 

All in all, it's a very exciting time to study artificial intelligence!

by David Rawlinson & Gideon Kowadlo

Some interesting finds: Acyclic hierarchical modelling and sequence unfolding

This week we have a couple of interesting links to share.

From our experiments with generative hierarchical models, we claimed that the model produced by feed-forward processing should not have loops. Now we have discovered a paper by Bengio et al titled "Towards biologically plausible deep learning" [1] that supports this claim. The paper looks for biological mechanisms that mimic key features of deep learning. Probably the credit assignment problem is the most difficult feature to substantiate - ensuring each weight is updated correctly in response to its contribution to the overall output of the network - but the paper does leave me thinking it's plausible.

Anyway the reason I'm talking about it is this quote:

"There is strong biological evidence of a distinct pattern of connectivity between cortical areas that distinguishes between “feedforward” and “feedback” connections (Douglas et al., 1989) at the level of the microcircuit of cortex (i.e., feedforward and feedback connections do not land in the same type of cells). Furthermore, the feedforward connections form a directed acyclic graph with nodes (areas) updated in a particular order, e.g., in the visual cortex (Felleman and Essen, 1991)."

This says that the feedforward modelling process (which we believe is constructing a hierarchical model) is a directed acyclic graph (DAG) - which means it does not have loops, as we predicted. Secondly, it is another source claiming that the representation produced is hierarchical (in this case, a DAG). The cited work is a much older paper - "Distributed hierarchical processing in the primate cerebral cortex" [2]. We're still reading, but there's a lot of good background information here.

The second item to look at this week is a demo by Felix Andrews featuring temporal pooling [3] and sequence unfolding. "Unfolding" means transforming the pooled sequence representation back into its constituent parts - i.e. turning a sequence into a series of steps.

Felix demonstrates that high-level sequence selection can successfully be used to track and predict through observation of the corresponding lower-level sequence. This is achieved by causing the high-level sequence to predict all steps, and then tracking through the predicted sequence using first-order predictions in the lower level. Both levels are necessary - the high level prediction provides guidance for the low-level to ensure it predicts correctly through forks. The low level prediction keeps track of what's next in the sequence.

[1] "Towards Biologically Plausible Deep Learning" Yoshua Bengio, Dong-Hyun Lee, Jorg Bornschein and Zhouhan Lin (2015) http://arxiv.org/pdf/1502.04156v2.pdf

[2] "Distributed hierarchical processing in the primate cerebral cortex" Felleman DJ, Van Essen DC (1991) http://www.ncbi.nlm.nih.gov/pubmed/1822724

[3] Felix Andrews HTM temporal pooling and sequence unfolding demo http://viewer.gorilla-repl.org/view.html?source=gist&id=95da4401dc7293e02df3&filename=seq-replay.clj

Reading list - July 2015

This month's reading list continues with a subtheme on recurrent neural networks, and in particular Long Short Term Memory (LSTM).

First here's an interesting report on a panel discussion about the future of Deep Learning at the International Conference on Machine Learning (ICML), 2015:

http://deeplearning.net/2015/07/13/a-brief-summary-of-the-panel-discussion-at-dl-workshop-icml-2015/

Participants included Yoshua Bengio (University of Montreal), Neil Lawrence (University of Sheffield), Juergen Schmidhuber (IDSIA), Demis Hassabis (Google DeepMind), Yann LeCun (Facebook, NYU) and Kevin Murphy (Google).

It was great to hear the panel express an interest in some of our favourite topics, notably hierarchical representation, planning and action selection (reported as sequential decision making) and unsupervised learning. From the Deep Learning community this is a new focus - most DL is based on supervised learning.

In the Q&A session, it was suggested that reinforcement learning be used to motivate the exploration of search-spaces to train unsupervised algorithms. In robotics, robustly trading off the potential reward of exploration vs using existing knowledge has been a hot topic for several years (example).

The theory of Predictive Coding suggests that the brain strives to eliminate unpredictability. This presents difficulties for motivating exploration - critics have asked why we don't seek out quiet, dark solitude! Friston suggests that prior expectations balance the need for immediate predictability with improved understanding in the longer term. For a good discussion, see here.

Our in-depth reading this month has continued on the theme of LSTM. The most thorough introduction we have found is Alex Graves' "Supervised Sequence Labelling with Recurrent Neural Networks":

www.cs.toronto.edu/~graves/preprint.pdf

However, a critical limitation of LSTM as presented in Graves' work is that online training is not possible - so you can't use this variant of LSTM in an embodied agent.

The best and online variant of LSTM seems to be Derek Monner's Generalized LSTM algorithm, introduced in D. Monner and J. A. Reggia (2012). "A generalized LSTM-like training algorithm for second-order recurrent neural networks". You download the paper from Monner's website here:

http://www.overcomplete.net/papers/nn2012.pdf

We'll be back with some actual code soon, including our implementation of Generalized LSTM. And don't worry, we'll be back to unsupervised learning soon with a focus on Growing Neural Gas.

Reading List - May 2015

John Lisman, "The Challenge of Understanding the Brain: Where We Stand in 2015", Neuron, 2015

For many in ML and AI,  biological knowledge is focussed on cortex. This paper gives an excellent broad overview of current biological understanding of intelligence.

Sebastian Billaudelle and Subutai Ahmad, "Porting HTM Models to the Heidelberg Neuromorphic Computing Platform", arXiv.org, 2015

Progress in Numenta's HTM and particularly interesting to see collaboration with the Human Brain Project. Does this signify growing collaboration with computational biologists?

Yann LeCun, Yoshua Bengio and Geoffrey Hinton, "Deep learning", Nature, 2015

Review of Deep learning by the guys that are recognised as THE fathers of the field - they have been working on NN for years without due acclaim, until recently.

LSTM Tutorial, Department of Computer Science, University of Kaiserslautem, 2015

Nitish Srivastava, Elman Mansimov and Ruslan Salakhutdinov, Unsupervised Learning of Video Representations using LSTMs", arXiv.org, 2015

Andrej Karpathy, "The Unreasonable Effectiveness of Recurrent Neural Networks", Andrej Karpathy blog, 2015

We have a renewed interest in RNN's and LSTM's and their great potential. Here are a few papers and tutorials that are well worthwhile for learning about this area.

Deep learning, a history in context

DeepMind, based on a deep learning architecture made a big impact in the tech industry. Deep learning continues to gain traction in the machine learning community and in the mainstream, both in terms of public awareness of its capabilities as well as through commercialisation.

This article by Simon Winder provides a very accessible introduction to the topic:
What is deep learning

It goes well with this great TED talk that showcases some recent impressive applications:
TEDx Brussels talk by Jeremy Howard, on the wonderful and terrifying implications of Machine Learning

A Unifying View of Deep Networks and Hierarchical Temporal Memory

Browsing the NUPIC Theory mailing list, I came across a post by Fergal Byrne on the differences and similarities between Deep Learning and MPF/HTM. It's a great background into some of the pros and cons of each.

Given the popularity and demonstrated success of Deep Learning methods it's good to understand how they work and how they relate to MPF/HTM theory. For example, both involve construction of hierarchical data representations created via a series of unsupervised classifiers. Fergal rightly admonishes proponents of both methods for their reluctance to research the alternatives!

The article can be found here:

http://inbits.com/2014/09/a-unifying-view-of-deep-networks-and-hierarchical-temporal-memory/