What does "degree of freedom" mean in neural networks? In Bishop's book "Pattern Classification and Machine Learning", it describes a technique for regularization in the context of neural networks. However, I don't understand a paragraph describing that during the training process, the number of degrees of freedom increases along with the model complexity. The relevant quote is the following:

An alternative to regularization as a way of controlling the effective
  complexity of a network is the procedure of early stopping. The
  training of nonlinear network models corresponds to an iterative
  reduction of the error function defined with respect to a set of
  training data. For many of the optimization algorithms used for
  network training, such as conjugate gradients, the error is a
  nonincreasing function of the iteration index. However, the error
  measured with respect to independent data, generally called a
  validation set, often shows a decrease at first, followed by an increase as the network starts to over-fit. Training can therefore be
  stopped at the point of smallest error with respect to the validation
  data set, as indicated in Figure 5.12, in order to obtain a network
  having good generalization performance. The behaviour of the network
  in this case is sometimes explained qualitatively in terms of the
  effective number of degrees of freedom in the network, in which this
  number starts out small and then to grows during the training process,
  corresponding to a steady increase in the effective complexity of the
  model.

It also says that the number of parameters grows during the course of training. I was assuming that by "parameters", it refers to the number of weights controlled by the network's hidden units. Maybe I'm wrong because the weights are prevented to increase in magnitude by the regularization process but they don't change in number. Could it be referring to the process of finding a good number of hidden units?
What's a degree of freedom in a neural network? What parameters increase during  training?
 A: The phrase "sometimes explained qualitatively" suggests that he is merely making a analogy to simple linear regression.  Each time we add a term to a linear regression model we add a degree of freedom to the model and subtract a degree of freedom from those associated with the error term.  If we put enough independent terms into a model, we can perfectly "predict" history from a set of random numbers, but we will be totally unable to predict the future.
A: The issue of the degrees of freedom on complicated statistical learning models has been discussed in Ye 1998 JASA. Basically, the idea is to see by how much the output of a complicated model, such as the neural network, responds to a unit change in inputs. For linear models, the relation is unsurpisingly one-to-one, so the degrees of freedom for a model of complexity $p$ (number of regressors) is $p$. For more complicated models (Ye considered regression trees), an ability to add an extra node provides way more flexibility, as the CART model will look for a good variable to split, and a good split point. That's way more than what adding a regressor to a linear model can do, and Ye found the regression trees to consume about 3.5-4 d.f.s per node. Neural networks may be somewhere in between, but the degrees of freedom is surely way larger than the number of units, and may be larger than the number of weights.
I think something similar was provided by HTF Sec. 7.6, although they surprisingly don't refer to Ye (1998). They do refer to Bishop as a special case, though.
A: He says the "effective complexity of the network". He actually refers to the size of the weights of the network. This can be understood in terms of the minimum description length principle. But before I get into that, the intuition is that the bigger the weights, the more different sort of functions your network can fit, and thus the higher the degrees of freedom (and effective complexity).
In that chapter he is talking about regularization, which is a technique of effectively reducing the risk of overfitting, by demanding the weights to be as small as possible. In general,
$$p(D|\mathbf{w}) = \prod_{n} p(t_{n}|\mathbf{x_{n}},\mathbf{w}) = \prod_{n}\exp \left(\frac{\beta}{2} \left[t_{n}- y(\mathbf{x_{n}},\mathbf{w}) \right]^{2}\right)/Z_{D}(\beta)$$. where $\mathbf{w}$ is a vector containing all parameters which characterize your algorithm and $Z_{D}(\beta)$ is a normalization constant. If you maximize the log-likelihood if this expression you get the ML estimate.
Now, you add a prior on the parameters which acts as a regularizer and helps you avoid overfitting by controlling the complexity of your classifier. Concretely, in the case it is natural to assume that your parameters are Gaussian distributed,
$$p(\mathbf{w}) = \exp \left( -\frac{\alpha ||\mathbf{w}||^{2}}{2}\right)/Z_{W}(\alpha)$$
MAP is defined as $\arg\max_{w} p(\mathbf{w}|D)$. Using Bayes' theorem, 
$$p(\mathbf{w}|D) = p(D|\mathbf{w})p(\mathbf{w})$$
If you substitute the above expressions and take logarithms you end up with (the $Z$'s do not depend on $\mathbf{w}$),
$$\arg\min_{w} \sum_{n}\frac{\beta}{2} \left[t_{n}- y(\mathbf{x_{n}},\mathbf{w}) \right]^{2} + \frac{\alpha}{2}\sum_{i}w_{i}^{2}$$
More generally, you have that the MAP estimate is equivalent to the following,
$$\mathbf{w}_{MAP} = \operatorname{argmin}_{\mathbf{w}} -log_{2}P(D|\mathbf{w}) - log_{2}(\mathbf{w})$$
The right hand side of the expression can be interpreted as the number of bits necessary to describe your classifier. The first term represent the number of bits necessary to code the errors your network does on the training data. The second represents the number of bits necessary to code the weights.
The MAP estimate is thus equivalent to choosing the most compact representation possible. In other words, you look for the set of weights which account for the training data as faithfully as possible which can be expressed with the least number of bits.
Notice that this is another form of the bias/variance problem: the bigger the weights, the lower the first term, because the network can fit the training data better (overfitting). But at the same time the higher the complexity of weights. The smaller the weights, the smaller the complexity of the network, but the higher the error term (bias). The higher the number of bits necessary to code the errors of the network.
Hope this gives you an good enough idea of what he is referring to.
P.S. adding a longer argument to the ongoing discussion
Maybe I misunderstand you. Let me please try to explain myself a last time.
The prior on the weights means represent the assumption we make about the function you want to fit. The bigger the prior (i.e. the weights) the broader the Gaussian, i.e. the more possible configurations one considers to fit the network.
Let us consider the case of regression (as in the paper I referred to). Low generalization error means that the network is able to map unseen samples very close to the actual values. If you are fitting a straight line, then a first order polynomial suffices (low complexity). Now, you could also fit the data with a higher order polynomial (let higher order coefficients be different from zero). The complexity of the network is higher because you allow for oscillations, for a more complex curve. Nevertheless, if the coefficients corresponding to higher order terms are low enough, the network can approximate the straight line very well, thus resulting in good generalization.
So the whole point of MDL is to make your weights as small as possible, as long as the generalization error can me minimized along.
Finally, quoting you: "I still find troublesome the argument that as the model starts to overfit, its capabilities to model other functions will increase. I think that's quite the opposite because a model that overfits, can't generalize to be applied to new information.". Yes, it can model OTHER, more complex functions, but it will fail to model the function at hand properly. In the figure 5.12 in the book, the error first declines, as the size of the weight increases (reduction in bias). Up to a given point when it starts to increase again (decrease in generalization, overfit). 
A: I suspect this is what Bishop means:
If you think of a neural net as a function that maps inputs to an output, then when you first initialize a neural net with small random weights, the neural net looks a lot like a linear function.  The sigmoid activation function is close to linear around zero (just do a Taylor expansion), and small incoming weights will guarantee that the effective domaine of each hidden unit is just a small interval around zero, so the entire neural net, regardless of how many layers you have, will look very much like a linear function.  So you can heuristically describe the neural net as having a small number of degrees of freedom (equal to the dimension of the input).  As you train the neural net, the weights can become arbitrarily large, and the neural net can better approximate arbitrary non-linear functions. So as training progresses, you can heuristically describe that change as an increase in the number of degrees of freedom, or, more specifically, in increase in the size of the class of functions that the neural net can closely approximate.  
