Why fully connected neural network cannot learn to count I am writing some educational material, and I am actually trying to find some proof for something. Consider the following case: you generate random vectors of length (let's say 20) containing only 0 and 1.
I have developed and tested succesfully LSTM that can easily learn to count the number of 1 in each vector.
Now I know that a standard fully connected neural network (let's say one layer with 15 neurons) cannot learn this. Can someone point me to a proof (at least an intuitive one). I have my intuitive understanding, but would love to see something more.
 A: Let's break it down to an extreme case - one neuron, linear activation - and build up from there.
You assign a static (once trained) weight to each index. Now, if you only used it on a single training case, you'd get the right answer quite easily - just assign a weight of 1 to each index where there's a one and zero to zeros.
Your layer performs a sum operation on the activations, passes it on to the output with a weight of 1 for the whole thing, and since your values are binary, you get the correct number of ones... for this specific case.
Now you try to apply it to a new random vector with the exact same amount of ones. And it fails catastrophically - the positions of ones and zeros shifted, but the weights remain fixed to the indices of the input.

But hey, your output layer can handle more than one input - let's add more neurons to solve the problem! But... each of those neurons has the exact same limitation - it can only output one accurate prediction per permutation. 
By adjusting the layer weights at the output layer, you get a model that effectively learns the error rate of each memorized permutation and uses that rate to construct an approximation of Adaboost.
Given enough neurons, you may be able to brute-force your way into a somewhat close approximation, but the model will never figure out that there is an underlying algorithm to exploit. 
As such, it would fail to generalize to a case where your random number generator started generating slighly skewed distributions of values for the vectors - the model memorized the error rate for the original distribution, which no longer holds true.
Even if you use a nonlinear activation on the output layer, at best you can only attenuate the influence of very weak classifiers for a slightly better prediction. The activation on the hidden layer doesn't really matter here, since it's connected directly to a binary input with no inherent structure so there's only two possibly true activation states - hitting all-ones, or all-zeros.
This is a XOR-like problem, so a single layer on its own quite simply won't ever find an actually decent solution - that you can find an approximation at all is all thanks to the output layers having its own set of weights.

Both LSTM and simply adding another hidden layer will address this issue simply by introducing more neuron layers - each layer being in a way a discrete step in an algorithm - and thus empowering the network to make a smarter representation. For LSTM, the network presumably tends to learn to remember a running tally, but it's just a slice of the space of possible solutions - with enough depth, you could arrive at some quite exotic ones.
