MDL Regularizer: A New Regularizer based on the MDL Principle
Kazumi Saito and Ryohei Nakano
NTT Communication Science Laboratories
2 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-02 Japan{saito,nakano}@cslab.kecl.ntt.jp
Abstract
This paper proposes a new regularization method
based on the MDL (Minimum Description Length)principle. An adequate precision weight vector istrained by approximately truncating the maximum likelihood weight vector. The main advantage of the proposed regularizer over existing ones is that it automatically determines a regularization factor without assuming any specific prior distribution with respect tothe weight values. Our experiments using a regression problem showed that the MDL regularizer significantly improves the generalization error of a secondorder learning algorithm and shows a comparable generalization performance to the best tuned weight-decay
regularizer.

1. Introduction
It has been found that adding some regularization(penalty) term to an objective function in the learningof neural networks can lead to signiﬁcant improvements
in network generalization. Such terms have been proposed on the basis of several viewpoints such as weightdecay [7], function-smoothing [11, 3], weight-pruning[6, 8], and Bayesian priors [9, 17]. Some are calculated
by using simple arithmetic operations, while others utilize higher-order derivatives.
Most of these methods require an adequate regularization factor be determined by using some method
which can reasonably estimate the generalization
performance. Resampling methods such as crossvalidation [16] or bootstrap [4] have been widely used
for this purpose, but they require a large amount ofcomputation even for mid-scale problems. On the other
hand, Bayesian methods can automatically determinea regularization factor (hyperparameter value) by assuming some speciﬁc prior distribution with respect tothe weight values; however, we generally cannot knowa suitable prior distribution in advance.
Standard statistical criteria such as AIC [1] or MDL[12] cannot be applied directly to determine the regularization factor, because they only compromise on thenumber of model parameters. Quite recently, however,it has been shown in the context of the VC-dimensionthat the model complexity of neural networks increases
when we allow a wider range of weight values [2]. Thus,
it would be expected that some statistical criterion canbe used to automatically determine a value of the regularization factor without assuming any speciﬁc priordistribution.
This paper proposes a new regularization method
based on the MDL principle. Section 2 explains the
proposed MDL regularizer and how to embed it in asecond-order learning algorithm. Section 3 shows experimental results for a regression problem and evaluates the generalization performance of the MDL regularizer in comparison to a weight-decay regularizer.

2. Regularization technique based on
MDL principle
2.1. BackgroundLet {(x1 , y1 ), · · · , (xm , ym )} be a set of examples,
where xt denotes an n-dimensional input vector andyt a target value corresponding to xt . In a threelayer neural network, let h be the number of hidden
units, wj (j = 1, · · · , h) be the weight vector between all the input units and the hidden unit j, and
w0 = (w00 , · · · , w0h )T be the weight vector between
all the hidden units and the output unit; wj0 means abias term and xt0 is set to 1. Note that aT denotes thetransposed vector of a. Hereafter, a vector consistingof all parameters, (w0T , · · · , whT )T , is simply expressedas Φ = (φ1 , · · · , φN )T , where N (= nh + 2h + 1) denotes the dimension of Φ. Then, the output value ofthe three-layer neural network can be described asz(xt ; Φ) = w00 +h

w0j f (wjT xt ),

(1)

j=1

where
f (v) =

1.
1 + e−v

Now, we assume that each value of y was corrupted
by Gaussian noise with a mean of 0 and an unknown
standard deviation of σ. Then, the learning problem
in neural networks can be formalized as the maximum
likelihood problem which maximizes the logarithmic
likelihood
m


u,σ

log P (yt |xt ; Φ, σ2 )

t=1

= −

m
m
1 
log 2πσ2 − 2(yt − z(xt ; Φ))2 . (2)22σ t=1

Here, since the maximum likelihood weight vector, Φ̂,which maximizes (2), is nothing but the least-squares
estimate for the second term of (2), it can be calculated
by using some learning algorithm.

2.2. MDL regularizer
The intuitive idea of the MDL principle [12] can be
explained as a communication problem where a senderwishes to transmit a data set to a receiver using a message of the shortest possible length. In regression problems, we suppose that the input data values are alreadyknown to the receiver, since we are trying to predict theoutput data, using the input data.
Now, by sending an adequate weight vector, thereceiver can estimate some approximated output values. Thus, by sending only the diﬀerence between theactual and approximated values, the receiver can obtain the complete output data values. In the case of
the maximum likelihood weight vector Φ̂, the message
lengthfor the diﬀerence values can be optimally givenmby − t=1 log P (yt |xt ; Φ̂, σ2 ); however, the message
length for Φ̂ usually requires a large number of bits,
due to its high precision. To compromise these two
message lengths, Rissanen [12] proposed a criterion forderiving the standard MDL criterion, by introducing
a truncated weight vector Φ̄ for Φ̂. Here, Rissanen’s
criterion is almost equivalent to the following one.
 m

N


log P (yt |xt ; Φ̄, σ2 ) −log |φ̂k − φ̄k |
min −
Φ̄,σ2

t=1

Indeed, the second term goes down if we use a coarser
precision, while the ﬁrst term generally increases because the coarser truncated vector can deviate morefrom Φ̂.
On the basis of the criterion (3), we propose a new
regularization technique. For any truncated weightvector Φ̄, there exists an N -dimensional vector u =(u1 , · · · , uN )T such that φ̄k = f (uk )φ̂k . Here, recall
that f (uk ) represents a sigmoidal function, f (uk ) =1/(1 + e−uk ), and 0 < f (uk ) < 1. Conversely, forany vector u, f (uk )φ̂k gives an approximation to sometruncated weight value φ̄k . Thus, the following criterion can be regarded as a continuous version of (3).
 mmin2 −
log P (yt |xt ; Φ̄(u)), σ2 )

k=1

(3)

t=1

−

N



log |φ̂k − f (uk )φ̂k |

k=1



m
2
1 
m
log 2πσ2 + 2
yt −z(xt ; Φ̄(u))
u,σ22σ t=1NN−log(1 − f (uk )) −log |φ̂k |(4)≡ min2

k=1

k=1

N
Note that the fourth term, k=1 log |φ̂k |, is constantand independent of the minimization process. Incidentally, directly minimizing (3) with respect to Φ̄ will bea tough constrained minimization problem, because wemust always assure that Φ̄ is a truncation of Φ̂.
In the minimization problem deﬁned by (4), since
there are two kinds of parameters, u and σ2 , we employ
a coordinate descent strategy. Namely, for a ﬁxed u,
by diﬀerentiating (4) with respect to σ2 and setting it
to 0, we obtain the relative minimum for σ2 as follows:
σ̂2

=

m
2
1 
yt − z(xt ; Φ̄(u)) .
m t=1

(5)

Conversely, for a ﬁxed σ̂2 , by ignoring independent
terms and multiplying σ̂2 , (4) can be equivalently
transformed to a problem which minimizes the following objective function.

where

F (u) = F1 (u) + σ̂2 F2 (u)
(6)
m
2
1 
F1 (u) =yt − z(xt ; Φ̄(u)) ,2 t=1
F2 (u) = −Nlog(1 − f (uk )).

k=1Here, we can see that the second derivative of F2 (u)with respect to uk is always positive, since∂F2 (u)∂uk∂ 2 F2 (u)∂u2k= f (uk ),= f (uk )(1 − f (uk )) > 0.

Therefore, the second term of (6) can be regarded as aregularization term whose regularization factor is automatically determined by (5).

In order to explain the step-length calculation, we
introduce Pearlmutter’s operators [10] deﬁned by∆u {F (u)}=2∆u {F (u)}=Then, when ∆u {F (u)} < 0 and 2∆u {F (u)} > 0, theoptimal step-length of a second-order approximation tothe objective function is expressed by

2.3. Second-order learning algorithm
In order to minimize the objective function deﬁnedby (6), we employ a newly invented second-order learning algorithm based on a quasi-Newton method [5],called BPQ [14], where the descent direction, ∆u, iscalculated on the basis of a partial BFGS update anda reasonably accurate step-length, λ, is eﬃciently calculated as the minimal point of a second-order approximation. In ﬁrst-order learning algorithms [13] whichcalculate the search direction as the gradient direction,a large number of iterations are often required untilconvergence. On the other hand, in existing secondorder methods [5] which converge more quickly by using both gradient and curvature information, it is difﬁcult to suitably scale up for large problems, and alarge amount of computation is required for calculating
the optimal step-length. The newly developed secondorder algorithm called BPQ can be reasonably scaled
up by introducing a storage space parameter, and thecomputational complexity for calculating the optimal
step-length is reasonably small, almost equivalent tothat of gradient vector evaluation. Incidentally, we can
employ other learning algorithms, but BPQ has worked
the most eﬃciently among several representative algorithms in our experiences [14].
In BPQ, the descent direction is calculated from thegradient vector, by directly applying the partial BFGS
update. Here, the derivative of (6) with respect to uk
is calculated by∂F (u)∂uk∂F1 (u)∂uk===∂F2 (u)∂uk∂F1 (u)∂F2 (u)
+ σ̂2
∂uk
∂uk
∂F1 (Φ̄) ∂ φ̄k (uk )
∂uk
∂ φ̄k
∂F1 (Φ̄)f (uk )(1 − f (uk ))φˆk∂ φ̄k= f (uk )where ∂∂φ̄ F1 (Φ̄) can be calculated by using the stankdard back propagation algorithm.

∂
F (u + λ∆u)|λ=0 ,∂λ∂2F (u + λ∆u)|λ=0 .
∂λ2

λ = −

∆u {F (u)}.
2∆u {F (u)}Here, the method for coping with the other cases isexactly the same as described in [14].
In the case of the objective function deﬁned by (6),the ﬁrst-order derivative is calculated as follows:∆u {F1 (u)}= ∆u {F1 (u)} + σ̂2 ∆u {F2 (u)}T= ∇Φ̄ F1 (Φ̄(u)) Φ̄ (u)∆u {F2 (u)}=∆u {F (u)}Nf (uk )∆uk

k=1

On the other hand, the second-order derivative is calculated as follows:2∆u {F (u)}= 2∆u {F1 (u)} + σ̂2 2∆u {F2 (u)}2∆u {F1 (u)}T= ∆u {Φ̄(u)} ∇2Φ̄ F1 (Φ̄) ∆u {Φ̄(u)}T+ ∇Φ̄ F1 (Φ̄) 2∆u {Φ̄(u)}= 2∆u {Φ̄(u)} {F1 (Φ̄)}
T+ ∇Φ̄ F1 (Φ̄) 2∆u {Φ̄(u)}2∆u {F1 (u)}=Nf (uk )(1 − f (uk ))(∆uk )2

k=1

Here, by regarding ∆u {Φ̄(u)} as the search direction,
2∆u {Φ̄(u)} {F (Φ̄)} can be calculated as the secondorder derivative with respect to a standard three-layer
neural network; thus, we can use BPQ [14]. Therefore,
by noting that∆ui {φ̄i (ui )}2∆ui {φ̄i (ui )}= f (ui )(1 − f (ui ))φ̂i ∆ui ,= ∆ui {φ̄i (ui )}×(1 − 2f (ui ))φ̂i (∆ui ).

we can see that a reasonably accurate step-length iscalculated eﬃciently.

2.4. Learning algorithm with MDL regularizer

3

In the coordinate method described above, σ̂2 canbe updated by using (5) at any time while minimizing
the objective function deﬁned by (6). However, since
BPQ is based on a quasi-Newton method, the best opportunity for updating σ̂2 is when an approximation
to the inverse Hessian matrix is restarted by discarding the accumulated search information. Let s be thevalue of the partiality parameter used for the partial
BFGS update; then, the proposed algorithm can besummarized as follows:2

step 1: Calculate the maximum likelihood weightvector Φ̂;
step 2: Initialize u, calculate σ̂2 by using (5),and set k = 1;
step 3: Terminate the iteration if a stopping criterion
is satisﬁed;
step 4: Calculate the current descent direction ∆uk ,
calculate the step-length λk ,and update the vector u;
step 5: If k ≡ 0 (mod s),
update σ̂2 by using (5);step 6: Set k = k + 1, and return to step 3;

training example
true function

1
0
-4

-2

0

2

4

2

4

(a) without regularizer
3
2
1
0
-4

-2

0

(b) with MDL regularizer

Figure 1. Curves obtained

3. Evaluation by experiments
learning was terminated when the gradient vector was
suﬃciently small,

3.1. Regression problem
By using a regression problem for a functiony2= (1 − x + 2x2 )e−0.5x ,the performance of the proposed MDL regularizer was
evaluated. In the experiment, the value of x was randomly generated in the range of [−4, 4], and the corresponding value of y was calculated from x; each valueof y was corrupted by adding Gaussian noise with amean of 0 and a standard deviation of 0.2. The total
number of training examples was set to 30, and thenumber of hidden units was set to 10.
In learning without the regularizer to obtain the
maximum likelihood weight vector, the initial values
for the weights between the input and hidden units
were independently generated according to a normal
distribution with a mean of 0 and a standard deviationof 1; the initial values for the weights between the hidden and output units were set to 0, but the bias value
at the output unit was initially set to the average output value of all training examples. The iteration of∇F1 (Φ) 2 /N

< 10−8 .

In learning with the MDL regularizer, the initial values for the vector u were set to the same value such thatf (uk ) = 0.9. The iteration of learning was terminatedwhen the gradient vector was suﬃciently small,∇F (u) 2 /N

< 10−8 ,and the modiﬁcation value to σ2 was suﬃciently small,
σ2 − 2F1 (u)/m< 10−4 σ2 .

3.2. Learning results
Figure 1(a) shows a function obtained through learning without the regularizer, together with the training
examples and the true function. We can see that theresult was over-ﬁtted to the training examples to somedegree. On the other hand, Figure 1(b) shows a function obtained through learning with the MDL regularizer. Clearly, the result with the regularizer more

avg.
without
regularizer s.d.

0.889
0.404

avg.
with MDL
regularizer s.d. 0.005

0.6

0.239

0.2
0.4
0.6
0.8
1
generalization error(a) comparison of generalization performance
1251.3437.5

with MDL avg.
regularizer s.d.

MDL regularizer

0.4

0without avg.
regularizer s.d.

Generalization error
0.8

0.2
0
40 4-1 4-2 4-3 4-4 4-5 4-6 4-7 4-8Regularization factor µ

4-9

Figure 3. MDL regularizer vs. weight-decay
regularizer

331.4
82.7
0

500
1000
number of iterations(b) comparison of number of iterations

1500

Figure 2. Performance of MDL regularizer
closely approximated to the true function than the result without it.
Figure 2(a) compares the generalization performance with and without the MDL regularizer, where
trials were performed 10 times. Here, the generalization performance was evaluated by using the average
RMSE (root mean squared error) for a set of 5, 000
test examples. The best possible RMSE level is 0.2 because each test example includes the same amount ofGaussian noise as given to a training example. The average generalization error of the MDL regularizer was
3.7 times as small as that without it. Moreover, by applying the proposed regularizer, the standard deviation
got much smaller. This indicates that the MDL regularizer played a leading role in stabilizing the learning
performance. Figure 2(b) compares the number of iterations required for the learning process with and without the regularizer. This ﬁgure shows that the MDL
regularizer shortened the number of iterations by 3.8
times on average.

3.3. Comparison with weight-decay regularizer
To evaluate how much the proposed regularizer improves the generalization performance, we compared
it with a weight-decay regularizer which employs asquared penalty term Ω deﬁned by
Ω = µ

N

k=1

φ2k .

In our previous experience [15], this term gave thebest result among other simple terms such as absolute
penalty or normalized penalty. In the experiments, theregularization factor µ was changed from 40 to 4−9 bymultiplying by 4−1 ; trials were performed 10 times foreach regularization factor.
Figure 3 compares the average generalization performance of MDL and weight-decay regularizers. Thisﬁgure shows that the MDL regularizer has the best
performance for any of the regularization factors of theweight-decay regularizer; only the weight-decay regularizer with adequate factors worked comparably. Since
the performance of the weight-decay regularizer depends on its regularization factors, ﬁnding suitable factors mean a considerable amount of computation if wehave little prior knowledge about the problems. Thus,
it has been shown that the proposed technique is apromising approach for learning neural networks witha regularizer.

4. Conclusion
This paper proposed a new regularization method
based on the MDL principle. In the MDL regularizer,
an adequate precision weight vector is trained by approximately truncating the maximum likelihood weightvector. The main advantage of the proposed regularizer
over existing ones is that it automatically determines aregularization factor achieving excellent generalization
without assuming any prior distribution. Our experiments using a regression problem showed that the MDL
regularizer signiﬁcantly improves the generalization error of a second-order learning algorithm and shows
a comparable performance to the best tuned weightdecay regularizer. In the future, we plan to do further
evaluations using a wider variety of problems.

References[1] H. Akaike. A new look at the statistical model identiﬁcation. IEEE Trans. Autom. Contor., AC-19:716–723,
1973.
[2] P. Bartlett. The sample complexity of pattern classiﬁcation with neural networks: the size of the weights
is more important than the size of the network. Technical report, Australian National University, 1996.
[3] C. Bishop. Neural networks for pattern recognition.
Oxford Press, 1995.
[4] B. Efron and R. Tibshirani. An introduction to thebootstrap. Chapman & Hall, New York, 1993.
[5] P. Gill, W. Murray, and M. Wright. Practical optimization. Academic Press, London, 1981.
[6] S. Hanson and L. Pratt. Comparing biases for minimal network construction with back-propagation. In
D. Touretzky, editor, Advances in Neural Information
Processing Systems, volume 1, pages 177–185, San Mateo, CA, 1989. Morgan Kaufmann.
[7] G. Hinton. Learning translation invariant recognitionin massively parallel networks. In J. de Bakker, A. Nijman, and P. Treleaven, editors, Proc. PARLE Conference on Parallel Architectures and Languages Europe,
pages 1–13, Berlin, 1987. Springer-Verlag.
[8] M. Ishikawa. A structural learning algorithm with forgetting of link weight. Technical report, Tech. Rep.
TR-90-7, Electrotechnical Lab. Tsukuba-City, Japan,
1990.
[9] D. MacKay. Bayesian interpolation. Neural Computation, 4(3):415–447, 1992.
[10] B. Pearlmutter. Fast exact multiplication by the Hessian. Neural Computation, 6(1):147–160, 1994.
[11] T. Poggio and F. Girosi. Regularization algorithms
for learning that are equivalent to multilayer networks.
Science, 247:978–982, 1990.
[12] J. Rissanen. Stochastic complexity in statistical inquiry. World Scientiﬁc, 1989.
[13] D. Rumelhart, G. Hinton, and R. Williams. Learning internal representations by error propagation. In
D. Rumelhart and J. McClellandnd, editors, Parallel Distributed Processing, pages 318–362. MIT Press,
1986.
[14] K. Saito and R. Nakano. Partial BFGS update andeﬃcient step-length calculation for three-layer neuralnetworks. Neural Computation, 9(1):123–141, 1997.
[15] K. Saito and R. Nakano. Second-order learning algorithm with squared penalty term. In Advances in Neural Information Processing Systems, volume 9, 1997.
[16] M. Stone. Cross-validation: A review. Operationsforsch. Statist. Ser. Statistics B, 9(1):111–147, 1978.
[17] P. Williams. Bayesian regularization and pruning using a Laplace prior. Neural Computation, 7(1):117–
143, 1995.