For the Computer Scientists
And now for something completely different…
If you watched Sesame Street as a kid, you’re undoubtedly familiar with “one of these things is not like the other” song. If not, you’ve encountered the exercise elsewhere. There are a number of objects that are similar in some obvious way and one object is obviously different. The goal is to identify which one is different.
Preschoolers can play the game. Can a computer? Let me toss out a few details and restrictions.
- You can have all the computing power you desire.
- Since input is always a tricky question, let’s just assume that the you would be physically presented with a number of objects and can collect any sort of data you feel like. Photograph them. Weigh them. Measure them. Burn them. Dissolve it them acid.
- You can’t have any sort of human interraction. So can’t have somebody describe them.
- Similarly, you can’t do a Google Fight or the equivalent. For example, if things were just the words Tiger, Lion, House Cat, and Motor Home you could not search for “Tiger Lion Motor Home” and “Tiger Lion House Cat” and so on and see which gets the most hits. I’m doing an unbelievably bad job of describing this—but I think you know what I’m getting at. The computer has to identify the relevant differences. It can’t search the sum total of human writing and find that when similar objects have popped up, they were most often grouped in a specific way. Similarly, you can’t have a program that plays the game ten trillion times and is told the correct answer each time so that it eventually has the answer to pretty much every set of objects it is likely to encounter.
- Finally, the things could be anything that can be represented in some tangible form. Objects. Pictures of objects. Pictures of words. Abstract patterns. The only rule is that 1) a preschooler should have no difficulty at all identifying which doesn’t belong, and 2) whoever choses the objects wants the computer to fail.
I’m pretty sure it’s an impractical task. But is it possible? Can a computer do taxonomy?
Short answer, absolutely. There is a field of computer science called machine learning. The idea is that one gives the machine some data, and it tries to create a mathematical model to somehow “explain” the data.
The data can be of two forms. In supervised machine learning, you give the system some data and some labels for that data. It then tries to come up with a model to predict the label given the data.
In unsupervised machine learning, you give the system some data without any labels. It then (generally) tries to cluster the data according to some measure of similarity. Each cluster then can be thought of as a set of data points all of which have the same label.
The difficulty is two fold (in terms of creating good models). First, you need to be able to have a good representation of the data. You (or the machine) need to figure out exactly what are the relevant features of the data you’ve given it. In the case of a image, say, it needs to know “OK, which parts of the image do I look at in order to make a decision, and which do I ignore”. Second, you need to figure out the form of the model. Typically, what we do is we say “the model (usually a function) has this form. For example, a linear function, could be used to separate out the data points for different labels (assuming you have only two labels). The task of the system, then, would be to learn the parameters (i.e. the coefficients) for this linear function. Or, for example, you could assume that the data is modeled by a particular probability distribution, say, a Gaussian, and then the job of the learner is to figure out the parameters for the distribution.
This is actually my area of research, finding good learning algorithms and data representation for a system to learn how to translate between languages. In what I do, I have some data, say, a document and it’s translation, and the job of the computer is to figure out what is the model that “explains” the translated document given the original document. Once we have this model, we can then use it to translate unseen sentences or documents.
The situation squashed describes is a comparatively straightforward thing for a computer to do.
