Limitations of Perceptron

Question

If you are allowed to choose the features by hand and if you use enough features, you can do almost anything.For binary input vectors, we can have a separate feature unit for each of the exponentially many binary vectors and so we can make any possible discrimination on binary input vectors.This type of table look-up won’t generalize.But once the hand-coded features have been determined, there are very strong limitations on what a perceptron can learn.

This is what Hinton explains in his Neural Networks course but I don't get the binary input example and why it is a table look-up type problem and why it won't generalize? What does he mean by hand generated features? I understand that perceptrons cannot classify non-linear data but I cannot relate this to his slide (slide 26). It would be nice if anybody explains this with proper example.

Answer 1

The slide explains a limitation which applies to any linear model. It would equally apply to linear regression for example.

What does he mean by hand generated features?

This means any features generated by analysis of the problem. For instance if you wanted to categorise a building you might have its height and width. A hand generated feature could be deciding to multiply height by width to get floor area, because it looked like a good match to the problem.

I don't get the binary input example and why it is a table look-up type problem and why it won't generalize?

A table look-up solution is just the logical extreme of this approach. If you have a really complex classification, and your raw features don't relate directly (as a linear multiple of the target), you can craft very specific manipulations of them that give just the right answer for each input example. Essentially this is the same as marking each example in your training data with the correct answer, which has the same structure, conceptually, as a table of input: desired output with one entry per example.

In fact this might generalize, but only exactly as well as the crafted features do. In practice, when you have a complex problem and sample data that only partially explains your target variable (i.e. in most data science scenarios), then generating derived features until you find some that explain the data is strongly related to overfitting.

From your comment:

In his video lecture, he says "Suppose for example we have binary input vectors. And we create a separate feature unit that gets activated by exactly one of those binary input vectors. We'll need exponentially many feature units. But now we can make any possible discrimination on binary input vectors. So for binary input vectors, there's no limitation if you're willing to make enough feature units." 1.What feature? 2.Why are we creating this feature? And why adding exponential such features we can discriminate these vectors?

Here is an example of the scheme that Geoffrey Hinton describes. Say you have 4 binary features, associated with one target value and see the following data:

data 0 1 1 0 -> class 1
data 1 1 1 0 -> class 2 
data 0 1 0 1 -> class 1
data 1 1 1 0 -> class 2
data 0 1 1 1 -> class 2
data 0 1 0 0 -> class 1

It is possible to get a perceptron to predict the correct output values by crafting features as follows:

data 0 1 1 0 -> features 1 0 0 0 0 -> class 1
data 1 1 1 0 -> features 0 1 0 0 0 -> class 2
data 0 1 0 1 -> features 0 0 1 0 0 -> class 1
data 1 1 1 0 -> features 0 1 0 0 0 -> class 2
data 0 1 1 1 -> features 0 0 0 1 0 -> class 2
data 0 1 0 0 -> features 0 0 0 0 1 -> class 1

Each unique set of original data gets a new one-hot-encoded category assigned. It is clear that ultimately if you had $n$ original features, you would need $2^n$ such derived categories - which is an exponential relationship to $n$.

Working like this, there is no generalisation possible, because any pattern you had not turned into a derived feature and learned the correct value for would not have any effect on the perceptron, it would just be encoded as all zeroes. However, it would learn to fit the training data very well, it could just associate each unique vector with a weight equal to the training output - this is effectively a table lookup.

The whole point of this description is to show that hand-crafted features to "fix" perceptrons are not a good strategy. Even though they can be made to work for training data, ultimately you would be fooling yourself.

Answer 2

Why doesn't table-look up generalize?

Generalization means you find rules which apply to unseen situations. For example, let's say I have a function $f: \mathbb{R} \rightarrow \mathbb{R}$ and I give you the (input, output) pairs (0, 1), (1, 2), (3, 4), (3.141, 4.141).

If you learn by table look-up, you know exactly those 4 tuples. But If I ask you what $f(5)$ is, you have a problem. Because you didn't find the general rule/pattern, but you simply memorized the data.

Another example: Imagine you have $n$ data points $(x, y)$ and you decide to fit a polynomial to it. As you know, you can fit any $n$ points (with the x's pairwise different) to a polynomial of degree $n-1$. But if you do that, even the slightest noise or a different unterlying model causes your predictions to be awefully wrong because your polynomial bounces like crazy.

What does he mean by hand generated features?

If you have a vector of $n$ numbers $(x_1, \dots, x_n)$ as input, you might decided that the pair-wise multiplication $x_3 \cdot x_{42}$ helps the classification process. Hence you add $x_{n+1} = x_3 \cdot x_{42}$. This is a hand generated feature. In contrast, neural networks learn non-linear combinations of the input.