Normalized Maximum Likelihood with Luckiness for
Multivariate Normal Distributions
Kohei Miyaguchi∗

arXiv:1708.01861v3 [math.ST] 1 Sep 2017

September 4, 2017

Abstract
The normalized maximum likelihood (NML) is one of the most important distribution in
coding theory and statistics. NML is the unique solution (if exists) to the pointwise minimax
regret problem. However, NML is not defined even for simple family of distributions such as the
normal distributions. Since there does not exist any meaningful minimax-regret distribution
for such case, it has been pointed out that NML with luckiness (LNML) can be employed as
an alternative to NML. In this paper, we develop the closed forms of LNMLs for multivariate
normal distributions.

1

Introduction

The normalized maximum likelihood (NML) is known to be the minimax optimal code length for
data compression or statistical model selection with respect to the MDL principle [1]. However, for
some distribution class including the normal distributions, NML is not well-defined. Restricting
sample spaces can solve the problem [2], but it has an intrinsic flaw that samples can fall outside of
any valid restrictions. We will introduce a treatment for this issue, NML with luckiness (LNML),
and give an exact formula for LNML of the multivariate normal distributions.
The rest of the paper is organized as follows: We first introduce NML and its optimality in
Section 2. Then we present the notion of LNML as an extension of NML in Section 3. The main
theorems about LNMLs of multivariate normal distributions are shown in Section 4. Finally, in
Section 5, we discuss on the choice of the hyperparameters and future perspective.

2

Normalized Maximum Likelihood (NML)

Let M be a set of probability density (or mass) functions, which we call a (statistical) model. The
NML relative to a statistical model M is given by
def

p̄n (xn ) =

maxp∈Mn p(xn )
,
C(Mn )

R
n
where xn = {xi }i=1 and C(·) denotes the normalizing constant C(Mn ) = maxp∈Mn p(xn )dµ(xn ).
Here Mn denotes the model of n i.i.d. observations drawn from a density in model M. The
normalizing constant C(·) is also referred to as the capacity function because of intuitions from the
theory of channel capacity [3]. It is known that the NML is the unique distribution that attains
the minimax point-wise regret on description lengths with respect to the model M [4]
max

p∈M,xn ∈X n
def

R(p̄; p, xn ) = min
R

max

q: q=1 p∈M,xn ∈X n

R(q; p, xn ),

)
where R(q; p, xn ) = log p(x
q(xn ) , if the minimum exists.
However, not a few of NMLs are difficult to obtain their closed form, and on the other hand
demanding to compute numerically due to the integral of capacity function. Though an asymptotic
approximation up to the constant term has been given by [5], there are still two major problems.
n

0 Graduate Schoold of Information Science and Technology, The University of Tokyo
kohei_miyaguchi@mist.i.u-tokyo.ac.jp

1

One is the problem of small samples such that the approximation is valid only for sufficiently large
sample and that it is not known how many samples we need for the accurate approximation. The
other is the problem of improper capacities such that the integral of the capacity is not finite and
that the NML does not exist. One can sidestep the former problem exploiting a formula (e.g. [6])
for calculating exact NMLs. However the latter problem is inevitable since there does not exist
any target values.

3

NML with Luckiness (LNML)

Since NMLs may be improper (e.g. their capacities are undefined), a number of treatments such
as restriction on the range of data and restriction on the range of parameters has been considered
so far. In a previous study [2], on exponential families of distributions, exact formulae for NMLs
with a variable restricted range of data, Y (η), were presented. However there is a flaw on such
restriction technique that it is impossible to design Y (η) to include any unseen data.
NML with luckiness (LNML) [7] is another approach for solving the problem of improper NMLs.
It is a general solution that includes as special cases the restriction on the range of the parameters
and the conditional NML. One of the biggest advantage of LNMLs over restriction of the range of
data is that it is well-defined regardless of the support of data. A LNML density is relative to a
model M and luckiness π : M → (0, ∞),
def

pLNML
(xn ) =
n

maxp∈Mn p(xn )π(p)
,
C(Mn , π)

R
where C(Mn , π) = maxp∈Mn p(xk )π(p)dµ(xn ) denotes the normalizing constant. Here we assume that the maximum exists. If π(p) = 1 for all p ∈ M, then the LNML coincides with the
NML. On the other hand one can avoid the problem of infinite integrals by choosing π properly.
Note that there are two variants (LNML1 and LNML3) except the above LNML, as known as
LNML2, but here we focus on LNML2 for the sake of simplicity. See [7] for the detailed definitions
and differences.
Another remarkable property of LNMLs is tilted minimax optimality. The LNML uniquely
achieves the minimax pointwise tilted regret,
max

p∈M,xn ∈X n

Rπ (pLNML
; p, xn ) = min
R
n

max

q: q=1 p∈M,xn ∈X n

Rπ (q; p, xn ),

where Rπ (q; p, xn ) = log p(xq(x)π(p)
denotes a tilted regret function. This is a straight extension of
n)
the previous minimax regret problem. Constant π(= c) implies zero subjectivity on the regret,
hence NML is the minimax optimal with respect to the completely objective regret Rc (q; p, xn ). On
the other hand LNMLs are minimax optimal with respect to their subjective regrets Rπ (q; p, xn ).
Therefore luckiness π embodies one’s subjectivity on the true distribution in minimax encoding,
and it is necessary to avoid the infinite capacity problem.

Now let Mkπ be a set of non-negative functions pk (·)π(p) p ∈ M . Then, LNML relative to
(M, π) can be written with the same notation as ordinary NMLs,
n

(xn ) = p̄n (xn ) = maxn
pLNML
n
p∈Mπ

p(xn )
.
C(Mnπ )

This is a natural generalization of NMLs on unnormalized density functions. Moreover, by extending the domain of π to any probability densities such that π(p) = 0 (∀p ∈
/ M), π can be seen
equivalent to the model Mπ itself.
Henceforth we omit π and regard M = Mπ as the unnormalized statistical model. Given any
unnormalized models M, one can recover their luckiness π; Let πM denote the extended luckiness
function relative to model M,
def

πM (p) = sup {α ∈ [0, 1] | αp ∈ M ∪ {0}} ,
for all probability densities p. Conversely, luckiness πM also has sufficient information for recovering
the original model M.

2

4

LNML for Multivariate Normal Distributions

In this section we give two formulae for LNMLs relative to the m-dimensional normal distributions
with both mean µ ∈ Rm and variance Σ(> 0) ∈ Rm×m unknown, whose density function is as
follows:
(
)
n
1X
1
def
⊤ −1
n
−
(xi − µ) Σ (xi − µ) .
f (x ; µ, Σ) =
mn
n exp
2 i=1
(2π) 2 |Σ| 2
Here, Σ > 0 denotes that Σ is positive definite. First, we start from a simple case, where the
luckiness is given by
π(µ, Σ; ν, σ 2 , ρ2 ) =
for ν > m − 1 and σ 2 , ρ2 > 0.

1
(2π)

mν
2

h ν 
i
exp − tr Σ−1 (σ 2 Im + ρ2 µµ⊤ ) ,
2
|Σ|
ν
2

(1)

Theorem 1 (Simple luckiness) Let Mn be the model of n independent observations drawn from
an m-dimensional normal distribution with luckiness π given by (1). Then, the capacity of Mn is
calculated as
C(Mn ) = C(m, n, ν, σ 2 , ρ2 )

  m2

n
n+ν
1
+
(n
+
ν)
2ν
Γm ( ν2 )
ρ
1
def

,
= mν 
σ
(2e)n+ν (πν)ν
Γm ( n+ν
2 )

m(m−1) Qm−1
j
where Γm (z) = π 4
j=0 Γ(z− 2 ) denotes the multivariate gamma function. Correspondingly,
n
the LNML relative to M is given by

f (xn ; µ̄n , Σ̄n )π(µ̄n , Σ̄n ; ν, σ 2 , ρ2 )
C(n, m, ν, σ 2 , ρ2 )
! m2
Γm ( n+ν
νν
σ mν
2 )
=
,
n
ν
π n (n + ν)n+ν (1 + ρ2 ν )
Γm ( 2 ) |Σ̄n | n+ν
2

p̄n (xn ) =

Pn
Pn
Pn
1
1
1
⊤
2
⊤
where µ̄n = n+ρ
2ν
i=1 xi xi + νσ Im ) − (ν+n)(ρ2 ν+n)
i=1 xi and Σ̄n = n+ν (
i,j=1 xi xj denote
the maximum a-posteriori probability (MAP) estimates under the prior proportional to π.
Proof It is suffice to show the closed form of the capacity C(Mn ). By the definition of the
capacity, we have
Z
C(Mn ) =
max f (xn ; µ, Σ)π(µ, Σ; ν, σ 2 , ρ2 )dxn
µ∈Rm ,Σ>0
Z
= f (xn ; µ̄n , Σ̄n )π(µ̄n , Σ̄n ; ν, σ 2 , ρ2 )dxn
Z
1
1
n
(2)
=
ν+n dx .
m(ν+n)
2
2
(2πe)
Σ̄n
On the other hand, we have a recursive expression of Σ̄n such that
Σ̄n =

ν +n−1
ρ2 ν + n − 1
Σ̄n−1 +
(xn − µ̄n−1 )(xn − µ̄n−1 )⊤ .
ν +n
(ν + n)(ρ2 ν + n)

Therefore, using the matrix determinant lemma, the last integral (2) satisfies the following recursive

3

formula,
Z

1

Σ̄n

n

ν+n
2

dx =

=

1

Z

dxn

ν+n
2

ν+n
ν+n Σ̄n

1

Z

1

ν+n−1
ν+n Σ̄n−1

ν+n
2



1 + cn−1 (xn −

π 2 Γ( ν+n−m
)
2
=
 m2
ν+n−1
Γ( ν+n
ν+n cn−1
2 )
m

Z

µ̄n−1 )⊤ Σ̄−1
n−1 (xn
1

ν+n−1
ν+n Σ̄n−1

ν+n−1
2

− µ̄n−1 )

ν+n
2

dxn

dxn−1 ,

2

ρ ν+k
where ck = (ν+k)(ρ
2 ν+k+1) . In the last equation, we exploits the normalizing factor of the multivariate t-distributions. Therefore, we have

Z

1
Σ̄n

1

n

ν+n
2

dx =

ν
ν+n Σ̄0

ν
2

n
Y

π 2 Γ( ν+i−m
)
2
 m2

i=1 ν+i−1 ci−1
Γ( ν+i
ν+n
2 )
m

 mν
n
2 Y

Γ( ν+i−m
)π 2
2
=
 m2

2
1 ρ ν+i−1
i=1
Γ( ν+i
ν+n ρ2 ν+i
2 )
m


m(ν+n)
2
mn
Γm ( ν2 )π 2 (ν + n) 2
1 + ρn2 ν
=
,
mν
2
σ mν Γm ( ν+n
2 )ν


ν+n
νσ 2

m

which, combined with (2), yields the formula of the capacity.
Now, we derive an LNML with more flexible luckiness in terms of location and scale. Since
the space of normal distributions is closed with respect to affine transformations on data and the
capacity is invariant to any reparametrization of data,
M′

n def

=



f ′ (y n ; µ, Σ)π(µ, Σ; ν, σ 2 , ρ2 ) µ ∈ Rm , Σ ∈ Rm×m , Σ > 0 ,

where yi = A−1 xi + µ0 (0 ≤ i < n) denotes a bijective affine mapping and f ′ (; µ, Σ) denotes the
probability density function of y n , has the same capacity C(M′n ) = C(n, m, ν, σ 2 , ρ2 ). This yields
the following theorem.
Theorem 2 (Luckiness with location and scale parameters) Let Mn be the multivariate
normal distributions of n observations with the luckiness given by
1

def

π(µ, Σ; ν, µ0 , Σ0 , ρ2 ) =

(2π)

mν
2

h ν 
 i
exp − tr Σ−1 Σ0 + ρ2 (µ − µ0 )(µ − µ0 )⊤
,
2
|Σ|
ν
2

where µ0 ∈ Rm and Σ0 (> 0) ∈ Rm×m . Therefore the capacity is calculated as
C(Mn ) = C(n, m, ν, |Σ0 |1/m , ρ2 ).
The corresponding LNML is also given by

f (xn ; µ̄n , Σ̄n )π(µ̄n , Σ̄n ; ν, µ0 , Σ0 , ρ2 )
C(n, m, ν, |Σ0 |1/m , ρ2 )
! m2
ν
2
Γm ( n+ν
νν
2 ) |Σ0 |
=
n+ν .
n
ν
n
n+ν
π (n + ν)
(1 + ρ2 ν )
Γm ( 2 ) |Σ̄n | 2

p̄n (xn ) =

Pn
Pn
Pn
1
1
1
⊤
where µ̄n = µ0 + n+ρ
2ν
i=1 (xi −µ0 )(xi −µ0 ) +νΣ0 )− (ν+n)(ρ2 ν+n)
i=1 (xi −µ0 ) and Σ̄n = n+ν (
i,j=1 (xi −
⊤
µ0 )(xj − µ0 ) denote the maximum a-posteriori probability (MAP) estimates under the prior proportional to π.

4

Proof Taking the scale σ and the transformation A such that Σ0 = (σA−1 )(σA−1 )⊤ and that
|A| = 1, we have
f ′ (y n ; µ, Σ)π(µ, Σ; ν, σ 2 , ρ2 ) = f (y n ; A−1 µ + µ0 , A−1 Σ(A⊤ )−1 )π(µ, Σ; ν, σ 2 , ρ2 )
= f (y n ; µ′ , Σ′ )π(A(µ′ − µ0 ), AΣ′ A⊤ ; ν, σ 2 , ρ2 )
= f (y n ; µ′ , Σ′ )π(µ′ , Σ′ ; ν, µ0 , Σ0 , ρ2 ),
where µ′ = A−1 µ + µ0 and Σ′ = A−1 Σ(A⊤ )−1 . Therefore, since the transformation from (µ, Σ) to
(µ′ , Σ′ ) is bijective, we have

M′n = f (y n ; µ′ , Σ′ )π(µ′ , Σ′ ; ν, µ0 , Σ0 , ρ2 ) µ′ ∈ Rm , Σ′ ∈ Rm×m , Σ′ > 0 = Mn
Then it follows that C(Mn ) = C(M′n ) = C(n, m, ν, σ 2 , ρ2 ) = C(n, m, ν, |Σ0 |1/m , ρ2 ).

Note that the result of the last theorem can be applied to calculate the conditional NML
(CNML) for the multivariate normal distributions, since π(µ, Σ; ν, µ0 , Σ0 , 1) is proportional to the
conjugate prior of the normal distributions.
As an immediate result of Theorem 2, we have the sequential decomposition of the LNML.
Corollary 3 (Sequential decomposition) The LNML distribution given in Theorem 2 is decomposed as


n
Y
(ρ2 ν + i)(ν + i − 1)
tν−m+i xi µ̄i−1 , 2
p̄n (xn ) =
Σ̄i−1 ,
(ρ ν + i − 1)(ν − m + i)
i=1
where tν (x|µ, Σ) denotes the multivariate t-distribution with degree of freedom ν, location µ and
scale Σ.
Note that the decomposition given by Corollary 3 is independent of the number of observations n.
Therefore, it defines an exchangeable stochastic process over positive integers.

5

Discussion

The hyperparameters (ν, µ0 , Σ0 , ρ2 ) can be chosen by the prior knowledge or by the nature of given
data. In either way, it does not matter to the asymptotic growth rate of the capacity since the
effect of luckiness function is no more than constant. However, smaller ν, e.g., ν = m, is preferable
if there is no specific reason, because larger ν makes π pointy and the associated regret Rπ more
distorted. On the other hand, Σ0 should be smaller than the expected scale of the data distribution
as it softly bounds the covariance estimate Σ̄n from below in terms of eigenvalues. As for the other
hyperparameters, µ0 and ρ2 , we recommend
to choose them such that the possible
location of data
n
o
1
distribution is included in the ball µ ∈ Rm (µ − µ0 )⊤ Σ−1
(µ
−
µ
)
≤
.
Hence,
for instance,
0
0
νρ2
2

σ
2
is an approximate
a reasonable choice of luckiness is π(µ, Σ; m, σ 2 , mR
2 ) given by (1), where σ
lower bound of the minimum eigenvalue of the true covariance and R is an approximate upper
bound of the maximum norm of the true mean. It remains for future work to extend the result to
other classes of distributions such as exponential families of distributions.

References
[1] J. Rissanen, “Universal coding, information, prediction, and estimation,” IEEE Transactions
on Information Theory, vol. 30, no. 4, pp. 629–636, 1984.
[2] S. Hirai and K. Yamanishi, “Efficient computation of normalized maximum likelihood coding
for gaussian mixtures with its applications to optimal clustering,” in Proceedings of IEEE
International Symposium on Information Theory, 2011, pp. 1031–1035.
[3] J. Rissanen, Optimal estimation of parameters.

Cambridge University Press, 2012.

[4] Y. M. Shtarkov, “Universal sequential coding of single messages,” Problemy Peredachi Informatsii, vol. 23, no. 3, pp. 3–17, 1987.
5

[5] J. J. Rissanen, “Fisher information and stochastic complexity,” IEEE Transactions on Information Theory, vol. 42, no. 1, pp. 40–47, 1996.
[6] P. Kontkanen and P. Myllymäki, “A linear-time algorithm for computing the multinomial
stochastic complexity,” Information Processing Letters, vol. 103, no. 6, pp. 227–233, 2007.
[7] P. D. Grünwald, The minimum description length principle.

6

MIT press, 2007.

