How are non-linear surfaces formed in the training of a neural network?
Hi and welcome to the community. It's important to understand these basic concepts very clearly.

You have to first understand the basic unit of a neural network, a single node/neuron/perceptron. Let us forget all about Neural Networks for a bit, and talk about something far simpler.

Linear Regression



In the above figure, we clearly have one independent variable on the x-axis, and one dependent variable on the y-axis. The red line has an intercept of zero, and let's say a slope of 0.5. Therefore,
$$ y = 0.5x + 0 $$ 

This, right here, is a single perceptron. You take a value of x, lets say 8, pass it through the the node, and get a value as output, 4. Simple!
But what is the model in this case? Is it the output? No. Its the set [0.5, 0] that represents the red line above. The outputs are simply points on that line.

A neural network model is always a set of values - a matrix or a tensor, if you will.

The plots in your question, do not represent outputs. They represent the models. But now that you've possibly understood what a linear model with one indpendent variable looks like, I hope you can appreciate that having 2 independent variables will give us a plane in 3-D space. This is called multiple regression.



This forms the first layer of a neural network with linear activation functions. Assuming $ x_{i} $ and $ x_{j} $ as the two independent variables, the first layer computes
$$ y_{1} = w_{1}x_{i} + w_{2}x_{j} + b_{1} $$

Note that while $ y_{1} $ is the output of the first layer, the set $ [w_{1}, w_{2}, b_{1}] $ is the model of the first layer and can be plotted as a plane in 3D space.
The second layer, again a linear layer, computes
$$ y_{2} = w_{3}y_{1} + b_{2} $$

Substitute $ y_{1} $ in above and what do you get? Another linear model!

$$ y_{2} = w_{3}(w_{1}x_{i} + w_{2}x_{j} + b_{1}) + b_{2} $$

Adding layers to a neural network is only compounding of functions.

Compounding linear functions on linear functions result in linear functions.

Well, then, what was the point of adding a layer? Seems useless, right?

Yes, adding linear layers to a neural network is absolutely useless. But what happens if the activation functions of each perceptron, each layer was not linear? For example the sigmoid or the most widely used today, ReLU.

Compounding non-linear functions on non-linear functions can increase non-linearity.

The ReLU looks like this
$$ y = max(0, x) $$


This is definitely non-linear but not as non-linear as let's say the sine wave. But can we approximate the sine wave by somehow "compounding" multiple, say $ N $ ReLUs?

$$ \sin(x) \approx a + \sum_{N}b*max(0, c + dx)$$

And here the variables $ a, b,c, d $ are the trainable "weights" in neural network terminology.



If you remember the structure of the perceptron, the first operation is often denoted as a summation over all the inputs. This is how non-linearity is approximated in Neural Networks. Now one may ask: So, summing over non-linear functions can approximate any function, right? So a single hidden layer between input layer and output layer (one that sums over all the outputs of the hidden layer units) should be enough? Why do we often see neural network architectures with so many hidden layers? This is one of the most important yet often overlooked aspect of neural networks and deep-learning.

To quote, Dr. Ian J Goodfellow, one of the brightest minds in AI, 


  A feedforward network with a single (hidden) layer is sufficient to represent any function, but the layer may be infeasibly large and may fail to learn and generalize correctly.


So, what is the ideal number of hidden layers? There's no magic number! ;-)

For more mathematical rigor on how neural networks approximate non-linear functions, one should learn about the Universal Approximation Theorem. Beginners should check this out.

But why should we care for increased non-linearity? For that I'd direct you to this.

Note that all of the above discussion is with respect to regression. For classification, the non-linear surface learned is regarded as a decision boundary and points above and below the surface are classified into different classes. However, an alternative, and arguably better, way to look at this is that given a dataset that is not linearly seperable, a neural network first transforms the input dataset into a linearly seperable form and then uses a linear decision boundary on it. For more on this, definitely check out Christopher Olah's amazing blog.

Finally, yes all independent variables must be normalized before training a neural network. This is to equalize the scale of different variables. More info here.