The New Turing Omnibus Chapter 27 Perceptrons
We began by welcoming some visiting members of the Cambridge Programmers' Study Group and circulating copies of the chapter and Chris' notes.
We began with Chris giving us an overview of the chapter (the "Big Picture" as we've taken to calling it), walking through the description of the human brain's neurons, axons and synapses and how propositional logic can be expressed in terms of neurons. Using this model, we can build special neural networks known as Perceptrons to classify images. This lead to a tantalising time—dubbed the "cybernetic age"—when artificial brains seemed within grasp. Sadly, the chapter shows there are classes of problems which cannot be solved using Perceptrons and—in our favourite quote from the book so far—the cybernetic age is described as:
A time in which vain imaginings far outstripped actual results.
With everyone agreed on the overall message, we then stepped through the chapter using its examples of a Perceptron to detect disjoint rectangles and then its failure to solve the connectedness problem.
We established that a Perceptron ultimately classifies images on a retina: returning a boolean that determines whether a given image is within a certain classification or not.
It consists of a single evidence weighing unit and many predicates. The predicates each gather evidence about a portion of the image (using any function of the pixels of the image) and return a numeric value for use in the evidence weighing unit. This evidence weighing unit then combines all the predicates' results and determines whether it falls below a given threshold or not thereby classifying the image.
We began by looking at the disjoint rectangles problem which develops a Perceptron to detect whether images consist entirely of disjoint rectangles or not.
We took particular care to break down the mathematical notation used in the book with Chris Lowis taking to the whiteboard to visualise the formulae.
We saw how the predicates in this particular Perceptron each compared different, overlapping 2 x 2 pixel squares in the image to a given blacklist of patterns. If such a blacklisted pattern of pixels was found, the predicate would return 1.
The results of these predicates (either 0 or 1) were then all multiplied by -1 and summed in the evidence weighing unit. This means that the presence of any of the blacklisted patterns would result in a negative output from the evidence weighing unit. As the threshold of this Perceptron is set to 0, it would result in a negative number thereby successfully distinguishing images with disjoint rectangles from those without.
Happy that our Perceptron worked (and having walked through a few examples on the whiteboard), we braced ourselves for the upsetting result that some problems cannot be solved by Perceptrons. One such problem is known as the connectedness problem and attempts to distinguish images consisting solely of connected pixels from those without.
Before diving into the formal proof, we discussed our intuition about the problem: specifically that such a Perceptron would only be able to make the distinction if it considered all pixels in the image. The bizarre analogy that we took to using was that of looking through a toilet roll tube at an image: we could solve the disjoint rectangle problem by looking only for one of a few blacklisted patterns in small parts of the image but the connectedness problem would require us to see the whole image at all times.
If we could see the entire image in our predicates then we could just store every permutation of pixels that fits a given classification. This solution is discussed in the chapter but dismissed as being against the "spirit" of Perceptrons and, more damningly, as requiring super exponential space. For example, for a 3 x 3 grid of monochrome pixels, there are 2^(3*3) possible images. The book also asks us to consider an infinite retina which leads us to abandon this approach.
We then discussed the two ways of limiting Perceptrons:
- Diameter-limited: as we used in the disjoint rectangles problem, looking at a particular portion of the image
k x kin size; - Order-limited: looking at a particular
kpixels in the image.
With these two limitations, we then stepped through the proof by contradiction that showed it is impossible for a Perceptron to solve the connectedness problem.
As we finished the chapter with time to spare, we decided to tackle the first problem: design a Perceptron to detect images consisting only of vertical stripes.
After some debate about what constituted vertical stripes, we agreed that—not dissimilar to the disjoint rectangles problem—we could use a set of 2 x 2 pixel patterns in the predicates. Unlike disjoint rectangles, this set would be whitelist of patterns meaning that we would have to adjust our weight and threshold accordingly.
As we finished with time to spare, Chris demonstrated his JavaScript implementation of Perceptrons and updated it live as we attempted to create a Perceptron that detected vertical stripes.
- We agreed that we had all benefited hugely from Chris' preparation and shepherding from the meeting;
- Like Tom previously, Chris did flag that the meeting preparation required a large time commitment from him and we discussed the perils of this for future meetings. We agreed that such large amounts of preparation—though obviously appreciated—should not be required for every meeting and, in the worst case, we could always go back to working through chapters without preparation if people did not want to volunteer;
- Attendees from the Cambridge Programmers' Study Group contrasted their experiences discussing Perceptrons which revolved around pair-programming to work through a simpler example prepared beforehand;
- We did mourn the lack of programming of late and debated whether we should try to restore the mob programming aspect of the club (mindful of the issues we had with our approach to the previous book).
Thanks to Leo and Geckoboard for hosting, to Chris Patuzzo for leading the meeting and his preparation and to Chris Lowis for illustrating on the whiteboard.