too few data while too many degrees of freedom in linear regression

Question

To recognize handwritten digits, I have a fully connected network, containing only 2 layers: input layer (all pixels of the image) and output layer (0 or 1). I use the simplest linear regression for training (with gradient descent) and got excellent results.

However, I just realized that my model had far more degrees of freedom than data points. Say the data are all nn pixel pictures to recognize, so the number of degrees of freedom is nn+1. I use n=50, but I only use less than 20 data points (20 training pictures). From the point of view of linear fitting/regression, the number of data points should at least surpass that of degrees of freedom. But now in my model the reverse happens, no solution should be found. What happened

Answer 1

Good question. The solution lies in understanding how weights play into the model's prediction. I've glossed over a bunch of issues here, but the big picture is what is most important.

Theory

1. When you create a model all the weights are psuedo-randomly initialized. This solves your problem of not having enough degrees of freedom to solve a linear regression. We've interpolated our weights and our model will update only the weights it needs as it trains.
2. Additionally, your model will probably find that most of your weights converge to zero. If you are using sklearn's load_digits() function, I recall that about half of each image was just white pixels. It is likely that there is a significant percentage of pixels that do not matter across all images (and thus might be assigned a weight of zero). Your question of how can you trust the prediction of the model is thus answered and we can modify our statement about degrees of freedom to: There cannot exist a greater number of discovered statistical trends than there are data samples. It is hard to measure "number of discovered statistical trends", but it follows that there is a finite number and that they are less than the number of samples minus 1.

Example

With a fully-connected, shallow neural network consisting of the input layer with weights and an output layer with two neurons, the input to the activation function of each of the output neurons will be something like the following:

$$f(B_1+\sum_{i=1}^{i}W_i*{I_i}_A)=P$$

where

1. $P$ is the class probability,
2. $B_1$ is the bias of the output layer,
3. $W_i$ is the weight of a specific neuronal connection,
4. ${I_i}_A$ is the output of the connected neuron if activated (in this case the pixel value), and
5. $f()$ is the activation function of the output layer neuron.

If we didn't initialize $W_i$ to something/anything, we would be unable to solve the equation (more variables than samples). However, by randomly initializing them, the equation immediately becomes solvable and we can use stochastic gradient descent or a different algorithm to optimize our weights. I hope this shows how pseudo-randomly initializing $W_i$ solves the mathematical problem of degrees of freedom.