July 2008


July 27, 2008
This article is being prepared for publication in Cambridge University’s Plus! Maths magazine. Feel free to comment.

Story of my Life

WALLE

Recently, I went to the cinema to watch Disney Pixar’s newest movie, WALL-E. A bleak, post-apocalyptic tour-de-force, the movie depicts the gentle romance between two robots of the future: WALL-E, the not-so-bright and not-so-attractive ‘guy’ with the big heart and sweet personality, and EVE, the sleek, sexy, totally out-of-his-league babe.

The story goes like this: A hundred years into the future, Earth — over-polluted and overtaken by garbage — can no longer sustain life. So we flee to outer space, leaving the planet’s cleanup in the mechanical pincers of an army of stout, capable robots.

Seven hundred, entirely uneventful years pass and now, pillars of compacted trash line the city skies like towering skyscrapers. One day, WALL-E — now the sole surviving creature of his kind — meets EVE, a visitor from outer space with a mysterious mission.

However, Pixar designed these robots so that they’re — well, they’re human. We see them as human. We see them communicate, we see them think, act, understand, love. And we accept this. By the end of the movie, we’ve accepted WALL-E and EVE as equals and we may even shed a tear here and there for our newfound friends.

But what exactly is WALL-E? Is he pure fantasy and fiction?

Or is he — is Artificial Intelligence — simply the way of the future?

Alan Turing’s Vision

I believe that in about fifty years’ time it will be possible to programme computers […] so well, that an average interrogator will not have more than 70 per cent chance of making the right identification [between human and machine] after five minutes of questioning.

Alan Turing in 1950

This prophecy, published in 1950 by English mathematician Alan Turing was a bold statement indeed. Remember, in that day and age, computers weren’t sleek, glossy, or available in a variety of neat colours; no, they where clunky, they weighed nearly 30 tons, and they took gaggles of people to operate.

Turing, however, saw past all that. He envisioned a day when digital computers programmed with rules and facts would possess the intelligence of man.

2001

This boldness and guiding confidence was exactly what researchers needed and thus was borne the field of artificial intelligence (AI). In the 1950s and 1960s, the field would see enormous growth and popularity. It became the hot topic of students, researchers, writers, and even the movies.

In the 1960s, for example, when Stanley Kubrick directed his 2001: A Space Odyssey, starring HAL, the omniscient and omnipotent robot, he had taken care to directly consult MIT Professor and AI expert Marvin Minsky, who assured him that yes, by the end of the 20th century, robots like HAL would not only live among us, but they would exceed us in many capacities.

It no longer became a question of if machines would become intelligent, but when.

A Philosophical Fork in the Toaster

At a time when researchers were proposing grand plans for general problem solvers and automatic translation machines, Dreyfus predicted that they would fail because their conception of mental functioning was naive, and he suggested that they would do well to acquaint themselves with modern philosophical approaches to human being.

‘What Computers Still Can’t Do’, 1993

Dreyfus

However in 1973, Berkeley philosophy professor, Hubert Dreyfus published his book, “What Computers Can’t Do”, in which he proposed the exact opposite of what was on everyone’s mind: Machines, he reasoned — as they were progressing now — would never, ever, reach the same intellectual capacities as a human.

There is a passage in Dreyfus’ book in which he recounts the results of a meeting among the top minds in computer science; here, his (early) report of A.I. was deemed to be “sinister”, “dishonest”, “hilariously funny”, and an “incredible misrepresentation of history”.

But of course, researchers in the A.I. community would be incensed. They would be, in fact, deeply, unapologetically pissed off.

After all, they’d just spent the last two decades of their lives telling the world what computers could and would do…only to have their fundamental beliefs and dreams attacked by — of all people — a philosophy scholar?

Hubert Dreyfus Criticises

The core of Dreyfus’ critique was about rules. See, a conventional machine is programmed to accept an input and apply a set of rules to produce an output. The idea is that any intellectual activity, whether it be adding numbers, playing chess, translating languages, or disposing of garbage, could be mimicked using a set of rules.

Dreyfus, however, argued that rules — by themselves — did not contain the necessary information for their application. Suppose we were to design a robot to process the following phrase:

Mary saw a puppy in the window. She wanted it.

What does “it” refer to, the puppy or the window?

But of course, even a child could tell you that it refers to the puppy. But how does a computer know? Does the computer know that puppies are furry, cute, and love to be hugged and touched by children? Can the computer understand that Mary probably doesn’t want a silly windowpane?

What if instead the phrase was:

Mary saw a puppy in the window. She pressed her nose up against it.

Now, it refers to the window. But does the computer know that children enjoy pressing their noses against windows? Does the computer know that the puppy is out of Mary’s reach, separated by a layer of glass?

Not only does understanding the nature of the word “it” in these sentences require such obvious facts about dogs and windows, but it also requires a certain human element. It requires us to empathize with how Mary may feel. It requires us to understand the physical nature of Mary’s body and how she interacts with her surroundings.

Previously, many A.I. researchers believed that programming an understanding of language could be done syntactically – that is, by appealing only to the rules of grammar and dictionary definitions. But Dreyfus (and linguists such as Noam Chomsky) pointed out that the issue was much, much more complex. So much of what we do and say depends on context.

And they were right. A.I. researchers would begin having difficulty producing machines with the common-sense understanding of a mere four-year old. There were simply too many rules — too many rules and each rule leading to more and more rules so that even the most basic statements and stories could simply not be understood without appealing to millions of common-sense facts.

So…Is WALL-E Dead?

But what does this all mean for poor WALL-E? Did Hubert Dreyfus destroy the dream of ever producing a WALL-E? Is true Artificial Intelligence unlikely to ever happen?

No, no, and no!

Dreyfus never intended his original critique to be a crushing blow to Artificial Intelligence. The dream continues to live on, but today, researchers are older and wizen by his words. The field is no longer as naïve and wide-eyed as it was half-a-century ago.

Neuron

For example, one possible avenue for modern AI research is provided by our own brains: Instead of programming a computer to abide by the traditional step-by-step rules approach, we model it like the neurons in the human brain where the results of the program depend on the ‘strengths’ of each particular neuron.

This radically different method of computing not only combines the work of psychologists and cognitive scientists in understanding how the human mind works, but also biologists and neuroscientists who study the physical brain, and finally, mathematicians and computer scientists, who work to develop the models for artificial neural networks.

If Artificial Intelligence is to succeed – if WALL-E is to ever exist – we know now that it is going to take the work of all of us — of mathematicians, computer scientists, cognitive scientists, philosophers, and psychologists. The dream of imbuing a machine with an intellect – if it is ever to happen – will be the crowning achievement of not any one discipline, but of humankind as a whole.

In which the author explains how facial recognition works in order to unravel a seventh grade mystery of mistaken identity.

July 19, 2008
This is a heavily edited version of an article I posted some time back. It’s being prepared for publication in Oxford’s Bang! Science magazine. Feel free to comment.

Seventh Grade Blues

the one

When I was in the seventh grade, one of the girls told me I looked like Keannu Reeves.

Was this some awfully cruel, sadistic joke little girls liked to play on unsuspecting boys?

When I was in the seventh grade, one of the girls told me I looked like Keannu Reeves. No, seriously.

I was hanging upside-down on the jungle gym, minding my own business, and she just walked over and blurted it out. Then she giggled like a moron and ran away. Girls can be so mean.

This became the highlight of my school year (my academic career, even), but you see, I was torn. On one hand, how could anyone confuse Keannu (black shades, gothic trench coat, infinite awesomeness) with me (pubescent, angst-ridden, gawky)? Was this all some awfully cruel, sadistic joke little girls liked to play on unsuspecting boys?

But on the other hand, maybe — maybe she was on to something. Maybe somewhere — somehow, behind all that bad acne and ruffled hair, I really did look like Neo. After all, who was I to disagree?

Today, however, I no longer have to wonder because, according to the latest advances in facial recognition, she was right.

Who in the Land is Fairest of All?

MyHeritage is an internet-based company that offers you the chance to see which celebrity you most resemble. Remember how in Snow White, the queen has a magical mirror which provides her with uninhibited flattery? This is the same, but like, tons better.

After a free signup, you upload a large-ish jpeg of your mug, then let the software crank away. Here were my results: Brad Pitt (71%), Keannu Reeves (63%), Luke Perry (63%), Matt Daemon (63%), and Jordana Brewster (60%).

Results

Brad Pitt? Really? Matt Daemon? Really? Who wouldathunk? But y’know, as I gaze into the mirror…well…yes, I see it now. Definitely. We’re practically brothers!

How does it all work? Is this actual science or just deceptive flattery? To understand how facial recognition works, we’re going to have to delve into the mathematics behind the algorithm.

Recognizing Faces

Suppose we were given someone’s picture. How might we go about identifying that person from a large database of faces?

One way we can go about it is by identifying the characteristics of the subject – perhaps the person has small lips, or a pointed chin, or distinct eyes. From here, we then study the database, going from picture to picture, each time isolating the features of the faces and checking for a match.

But while this might work, it’s also a lot of work; algorithms would need to be defined to analyse each desired feature and a large number of faces to mix and match and could potentially take eons to compute.

A more efficient way to proceed would be to examine these faces as a statistical whole rather than as the sum of its parts. This is similar to the difference between identifying a city by its landmarks and identifying the same city by the density of its roads, the clusters and heights of its buildings, its downtown areas and rural areas, and so on.

A Picture is Worth a Thousand Digits

Snap! But what are pictures, really?

Grid

As stored in a computer, a picture is nothing more than a great big grid of dots (or pixels). If the picture is greyscale, each pixel is associated with a number from 0 to 255 representing its brightness, from pitch black (0) to pure white (255).

Now in the abstract theory of Linear Algebra, these grids of pixels are called ‘vectors’. You’ve probably encountered vectors before in Physics class and in fact, these ‘face vectors’ are quite similar.

Like vectors representing force or motion, these new ‘face vectors’ have a `magnitude’ (an overall brightness), as well as a ‘direction’ — the only difference is that they inhabit some higher-dimensional Face Space, rather than the two or three-dimensional physical world we live in.

Coords

Thus, faces found in the database are nothing more than vectors that, like other mathematical quantities, can be added, subtracted, multiplied, and generally manipulated as they roam about in the Face Space.

What’s Your Eigenface?

However, Face Spaces are complicated affairs — they’re high dimensional boxes stuffed with a large number of faces, each face containing thousands of pixels.

It would thus be foolish to try and compare each face pixel by pixel; instead we look to construct a small group of pictures representing the general facial patterns of the database. This small but crucial group is called the Eigenface Basis.

Think of how, when we analyse the motion of a ball flying through the air, we break the motion into its horizontal and vertical components. These horizontal and vertical components provide a fundamental basis for which all motion can be broken down into.

Similarly, once the eigenface basis is found using Linear Algebra, each face in the database can then be expressed using certain percentages of each eigenface. For example, we may say that a picture is composed of 10% of the first eigenface, 25% of the second, 4% of the third, and so on.

Eigenfaces

The beauty of this treatment is that even in a large database, each unique face can be expressed very simply using its eigenface decomposition. We no longer have to express each face using thousands of pixels; now, like a simple recipe in which the eigenfaces are the key ingredients, the entire database can be reconstructed as it was before.

A Problem of Distance

Now imagine each face in the database, represented in terms of its eigenface percentages, akin to coordinates lying in some higher-dimensional plane. Our test subject (which may or may not lie in the database) is then projected onto this plane by expressing it in terms of the eigenface components.

Matching

But now, the problem of recognising the subject becomes as simple as finding the shortest distance (or closest match) between our subject and each face in the database, a problem which is aided enormously by the fact each face is represented by only a handful of eigenface components.

The Future and You

But really, just how accurate are these eigenface algorithms?

In optimal conditions (with good lighting, a representative database, front-facing pictures, etc.), a simple eigenface routine might produce accurate readings of up to 90%.

Unfortunately, real life is never that simple, and in reality, one must contend with other ‘noisy’ factors. Factors like variance in pose (person facing at an angle), obstructions (sunglasses or other people), resolution and lighting, and so on. Despite this, however, the science of facial recognition has steadily improved to the point where today, it is becoming a standard for many military, security, and commercial applications.

Yeah, yeah. But now that you know how facial recognition works, go and try it on yourself.

What celebrity do you look like?

Today was my ninth (and final) trip over the Atlantic Ocean in one year’s time.

This is not something to be proud of.

I’m tired. And I’m pretty sure I have the faint outline of “Air Canada” imprinted on the back of my ass from sitting on their seat cushions.

1. June 14th, 2007: En Route to Kenya

2. July 15th, 2007: To Ottawa

3. July 21st, 2007: To England (Conference)

4. July 29th, 2007: To Ottawa

5. September 20th, 2007: To England

6. December 24th, 2007: To Ottawa (Christmas)

7. December 31st, 2007: To England

8. June 29th, 2008: To Ottawa (Summer)

9. July 7th, 2008: To England

That was, by the way, a joke. You don’t get monogrammed seat cushions unless you fly first class.