13
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Nomenclature. A parameter is a single weight. Number of parameters increasing means the number of "neurons" or "connections between neurons" is increasing. This means the topology is non-constant. $\endgroup$ – EngrStudent Apr 24 '13 at 5:20
  • $\begingroup$ Thanks! But then why does the training increase the number of weights? $\endgroup$ – Robert Smith Apr 24 '13 at 5:23
  • $\begingroup$ could you quote the section, or at least specify chapter and page in the book? $\endgroup$ – jpmuc Apr 24 '13 at 7:14
  • $\begingroup$ There are in fact training algorithms that manipulate the structure of a neural network during training (Cascade Correlation, NEAT, ...). They usually constantly increase the number of weights. But I don't think Bishop mentions that in his book. $\endgroup$ – alfa Apr 24 '13 at 9:26
  • $\begingroup$ @alfa Interesting. I haven't read the whole book yet, so I don't know if it mentions that kind of algorithms. I don't think it refers to them in this section of the book, though. $\endgroup$ – Robert Smith Apr 24 '13 at 15:52
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for your answer. I added the relevant part of the book as a quote, so you can see the context. Not sure if it confirms your suggestion, though. $\endgroup$ – Robert Smith Apr 24 '13 at 15:55
  • $\begingroup$ Yes, that does confirm what I thought Bishop meant. $\endgroup$ – Marc Shivers Apr 24 '13 at 21:22
  • $\begingroup$ Reading a couple of times your answer, I think that as the training progresses and the model starts to overfit, the number of functions that the model can approximate is actually reduced because it will approximate extremely well points from the training data but its predictions won't be good as it can't generalize to fit other points or similar datasets. $\endgroup$ – Robert Smith Apr 24 '13 at 22:16
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks. That seems about right but what about the relation with the training of a neural network? I found in "The Elements of Statistical Learning" in page 96 (docs.google.com/…) an expression relating degrees of freedom and covariance, and I can see why more training would reduce the error function and as a consequence increase covariance and degrees of freedom. However, I don't understand why that equation (3.60 in the book) holds. $\endgroup$ – Robert Smith Apr 24 '13 at 18:39
  • $\begingroup$ By the way, it also seems a bit different from the definition of (generalized) degrees of freedom talked about in Ye's paper. $\endgroup$ – Robert Smith Apr 24 '13 at 18:42
  • 1
    $\begingroup$ I guess you can think of that covariance as a rough version of derivative... or may be the other way round: the derivative, defined as the limit as the size of the step goes to zero, can be thought of as the plim of that covariance as the variance of the disturbance goes to zero. Equation (3.60) does not have to hold, it's a definition, so there's nothing to hold. What does hold is the equivalence with the standard definition of d.f.s for the linear models that they mention briefly on the next page, and that is simply the linear algebra of linear models. Ye (1998) must talks about it, too. $\endgroup$ – StasK Apr 25 '13 at 2:22
3
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ Thanks. This is similar to the idea of Marc, however, 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. $\endgroup$ – Robert Smith Apr 24 '13 at 22:02
  • 1
    $\begingroup$ Robert, I believe that is some misunderstading of what generalization error means vs. complexity of the network, i.e. the ability to model more complex functions. There are a number of papers describing the different terms, like cbcl.mit.edu/projects/cbcl/publications/ps/…. $\endgroup$ – jpmuc Apr 24 '13 at 22:19
  • $\begingroup$ I don't think there is confusion when the term "complexity" is used because if you have a bunch of weights with crazy values, that makes the model very complex and you can immediately tell by the resulting plot. On the other hand, being able to manage a wide set of functions requires a model capable of generalize well from the data which can be obtained by avoiding overfitting. $\endgroup$ – Robert Smith Apr 24 '13 at 22:28

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.