Limitations of Perceptron

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.

• Could you give a reference to the specific lecture/slide? Apr 12, 2017 at 6:45
• Apr 12, 2017 at 6:55

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.

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.

• 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? Apr 12, 2017 at 8:45
• @KAY_YAK: I put that question and a repsonse to it into my answer. Apr 12, 2017 at 18:49
• 0 1 1 0 -> 1; 1 1 1 0 -> 2; 0 1 0 1 -> 3; 1 1 1 0 -> 2; 0 1 1 1 -> 0 Why do we have same input vectors?? So this example has 4 class??  0 1 1 0 -> 1 0 0 0 0; 1 1 1 0 -> 0 1 0 0 0; 0 1 0 1 -> 0 0 1 0 0; 1 1 1 0 -> 0 1 0 0 0; 0 1 1 1 -> 0 0 0 1 0; 0 1 0 0 -> 0 0 0 0 1 Which feature was one-hot-encoded? And while training if we are one-hot encoding input why would we not encode an input and try to learn it?? Apr 12, 2017 at 20:31
• @KAY_YAK: I repeated the first list because it is supposed to represent input features, which may repeat. There are 4 classes in the example, but actually I don't want you to think I am one-hot encoding the class, so I'm gonna change that now. The second list shows how the one-hot-encoding works - i.e. you one-hot-encode across the whole input, which is the point of what Geoffrey Hinton is getting at. Apr 13, 2017 at 7:04
• data 1 1 1 0 -> class 2 why repeat this in the list?? If we are learning this won't add any new information. If we one-hot-encode 1 1 1 0 we should be getting 0 1 0 1 0 1 0 0 or 1 0 1 0 1 0 0 0 since each feature is binary and our data has 4 features so 4 x 2^1 = 8 features. If we are deriving features like this we will do the same for both training and test data otherwise it won't make sense right?? Apr 13, 2017 at 8:41

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.

• I understand what generalization is and how look-up isn't generalization. I know what variance is and how higher complexity models have higher variance. What I don't understand is what is he trying to explain with binary input vectors. _ if you use enough features, you can do almost anything_ why in case of perceptrons with binary input features? and how in this case the perceptron will behave like a lookup table? Apr 12, 2017 at 23:22
• @KAY_YAK Neil Slater already explains that part. Apr 13, 2017 at 8:13