\documentstyle[psfig]{slides}
%\documentstyle{slides}
\pagestyle{plain}

\newcommand{\topline}{\par\hrule\par}

\begin{document}
\input{psfig}

%\onlyslides{}

%slide 0-title page
\begin{slide}{}
\begin{center}
{\bf Minimum Description Length Principle and Model Selection}
\vspace{2.0cm}



Bin Yu\\ 
Statistics Department\\
University of California, Berkeley

\vspace{1.0cm}
Collaborators: \\
Mark Hansen (Bell Labs)\\

Andrew Barron (Yale)\\
Jorma Rissanen (IBM)\\
\vspace{1.0cm}

June 2, 1998

UC Santa Barbara
\vspace{3.0cm}


\end{center}
\end{slide}


\parindent=0pt


%slide 2
\begin{slide}{}

{\bf Outline:}
%\vspace{0.5cm}
{\small
\begin{itemize}
\item Why Description Length in Statistics? 
      \begin{itemize}
	 \item Kraft's inequality
      \end{itemize}
\item Forms of Description Length 
\item Which Form to Use in MDL?
      \begin{itemize}
      \item Shannon's coding theorem:\\[0.1in]
      MDL is MLE 
      \item Universal coding theorem:\\[0.1in]
      MDL for model selection
      \end{itemize}  
%\item Performance of MDL in model selection
\item MDL in Action: Model Selection in Regression 
      \begin{itemize}
       \item AIC, BIC, gMDL and iMDL
       \item Number of Bristles on Fruit Fly
       \item A Simulation Study
      \end{itemize}
\item Concluding Remarks
 
\end{itemize}

}
\end{slide}


\begin{slide}{}
{\bf 1. Why description length in statistics?}
%\vspace{.5cm}

What is a code?

Given a finite alphabet (or set) ${\cal A}$, a binary
code ${\cal C}$ is a map from ${\cal A}$
to strings of 0's and 1's.

Example:\\

\hbox{
\vbox{\psfig{figure=tree.ps,width=2.5in}}\hspace*{-1.25in}
\vbox{
\begin{eqnarray*}
code: \cal A & \rightarrow & \{ 0,1 \}^*
\\ a & \rightarrow & 0\\ b & \rightarrow & 10\\ c & \rightarrow & 11
\end{eqnarray*}

\vspace*{1in}
}
}
\end{slide}

\begin{slide}{}

\begin{array}{cccc}
code/description length: & L & \rightarrow & $Z^+$ \\
  & L(a) & = &1 \\
  & L(b) & = &2 \\
  & L(c) & = &2.
\end{array}

Hence 
\[ L(\cdot)=-\log_2 P(\cdot) \]

with $P(a)=1/2,\; P(b)=P(c)=1/4.$
\end{slide}

\begin{slide}{}
For any probability distribution $P(\cdot)$ on ${\cal A}$,

$-\log P(x)$ may be regarded as the code length
of $x$ of a prefix code by 

\underline{Kraft's ineqaulity:}\\[0.1in]
$L( \cdot )$ is the code length of a binary prefix code 
iff
\[ \sum_{x \in {\cal A}} 2^{- L(x)} \leq 1 .\]

Take $L(x) = - \log P(x)$.

\end{slide}

\begin{slide}{}
{\bf 2. Forms of Description Length through an Example}

Consider the ups and downs of the New York Dow-Jones daily
{\bf return} and {\bf volatility} of a 6430 day period from July 1962 to June
1988.

Return string: 50.71\% 1's or up's;

Volatility string: 31.47\% 1's or up's.
\end{slide}

\begin{slide}{}

\centerline{ \vbox{\psfig{figure=ret1.ps,width=7in} 
%\par
\kern -1.75in
\psfig{figure=ret2.ps,width=7in}
}
}
\end{slide}

\begin{slide}{}


\centerline{
\vbox{\psfig{figure=vol1.ps,width=7in} 
%\par
\kern -1.75in
\psfig{figure=vol2.ps,width=7in}
}
}

\end{slide}

\begin{slide}{}
Imagine tranmission of these sequences
from one location to another: 
\vspace*{-0.3in}
\begin{itemize}
\item their length ($n=6429$) is assumed known to both ends;
\vspace*{-0.3in}
\item IID Bernoulli model is postulated for\\ compression purposes.
\vspace*{-0.3in}
\end{itemize}
\end{slide}

\begin{slide}{}
(i) Two-stage Description Length

$\widehat{model}$: $k$ = \# of 1's or $\hat{p}=k/n$ 

%\mbox{Total DL of data} \\
Total DL of data
\vspace*{-0.1in}
\begin{eqnarray*}
& = & L(\hat{p})+L( data|  \hat{ p}) \\
 & = & \log_2 6429 + \log_2 [(k/n)^k (1-k/n)^{n-k}] 
\end{eqnarray*}

Return: 6441 bits\\ \hspace*{0.5in}  (0.2\% extra over no coding: 6429 bits)

Volatility: 5789 bits\\ \hspace*{0.5in} (10\% saving)

In general,
\[  L(\hat{\theta })+L( data |  \hat{ \theta}) \]



\end{slide}

\begin{slide}{}
(ii) Mixture Form of Description Length

With a uniform[0,1] prior on $p$, we get the mixture probability dist
\[ m(x^n) = \int_0^1 p^k (1-p)^{n-k} dp 
=\frac{k! (n-k)!}{(n+1)!} .\]

Total code length
\[ - \log_2 m(x^n) = -\log_2 \frac{k! (n-k)!}{(n+1)!}\]

Return: 6434 bits

Volatility: 5782 bits

In general,
\[  -\log_2 m(x^n) = -\log_2 \int_\theta
f(x^n |\theta) w(\theta)d\theta .\]
 

\end{slide}
%\begin{slide}{}
%(iii) Predictive: learning $p$ on-line

%At day $t$, use the Bernoulli coder with
%$\hat{p}_{t-1} = (k_{t-1}+1)/(t+1)$, to get code length
%\[ L(x_t)= -x_t \log_2 \hat{p}_{t-1} - (1-x_t) \log_2 (1-\hat{p}_{t-1}).\]
%Total: 
%\[ \sum_t L(x_t) = - \log_2 \prod_t p_{bern} (x_t|\hat{p}_{t-1}),\]
%which turns out to be the same as
%\[ -log_2 m(x^n) .\]
 
%In general,

%$\sum_t -\log_2 f(x_t|\hat{\theta_{t-1}}) $.

%\end{slide}


\begin{slide}{}

{\bf 3. Which Form to Use in MDL?}

Minimum Description Length (MDL) principle (Rissanen, '78):

Choose the model which gives the minimal description length 
of the data.\\

Precursors to MDL:

Algorithmic complexity (Kolmogorov, Solomonoff, Chatin, 60's);

Shortest description length for classification (Wallace and Boulton, '68)

AIC model selection criterion (Akaike, '74)

\end{slide}

\begin{slide}{}

{\bf 3a. Shannon's Coding Theorem:\\ MDL is MLE}

Suppose a parametric family is given:
\[ {\cal M} = \{ f_\theta: \theta \in \Theta \subset R^d \} \]
Want to estimate $\theta$ based  on $x^n= (x_1, ..., x_n)$.

\underline{Shannon's coding theorem:}\\[0.1in]
For any prefix code $C$ with length function $L$,
the average code length $L(P)$ satisfies
\[
L(P) \geq H(P) \equiv -\sum_{a \in A} P(a)\log P(a),
\]
the  equality holds if and only if 
$$
L= L_P= -\log P.
$$
\end{slide}

\begin{slide}{}

It follows that the best (on average) description length of data generated
by $f_\theta$ is 
\[ -\log f_\theta (x^n) .\]
MDL says 
\[ \min -\log f_\theta (x^n) \Leftrightarrow \max f_\theta (x^n). \]

Hence MDL is the same as MLE: it shares MLE's
good estimation properties.

%Bayes estimator needs a prior.

%MDL differs from the Bayesian approach unless the prior is uniform.

\end{slide}

\begin{slide}{}
{\bf 3b. Universal Coding Theorem:\\ MDL in Model selection}

More than one model class are given and we need to select one:
\[{\cal M}_d = \{ f_{\theta_d} : \theta_d \in \Theta_d \subset 
R^d \} \] 
The simplest case is the same as hypothesis testing:


{\em Example:} Assume $x^n$ are iid observations from
$N(\theta, 1)$ ($ \theta \in R^1$) and we want to test the hypothesis

$H_0: \theta =0$ vs. $H_1: \theta \neq 0$.

It is the same as choosing between
\[ {\cal M}_0 =\{ N(0, 1) \} \;\; \mbox{ and }
{\cal M}_1 = \{ N( \theta, 1) : \theta \neq  0 \}. \]

\end{slide}

\begin{slide}{}

What description length $L_i (x^n)$ to use?

Based on ${\cal M}_0$, by Shannon's theorem:

{\small
\begin{eqnarray*}
L_0 (x^n) & = & - \log f_0 (x^n) \\
& = &  - n \log (2 \pi)/ 2 + \sum_{t=0}^{n-1} x_{t+1}^2/2 .
\end{eqnarray*}
}

Based on ${\cal M}_1$, it is attempting to use

{\small
\begin{eqnarray*}
 L_1 (x^n)& =& -\log f_{\bar{x}_n} (x^n)\\
&=& n \log (2 \pi)/2 + \sum_{i=1}^n (x_i - \bar{x}_n)^2/2   +
 \frac{1}{2}  \log n 
\end{eqnarray*}

}


\end{slide}

\begin{slide}{}

How do we know we can't do better than $L_1 (x^n)$ based
on ${\cal M}_1$? or

Why $L_1 (x^n)$ is the "description length" based on ${\cal M}_1$?

Without specific information on the members of the class,
the description length has to be fair to all of them. 

Need a Universal Coding Theorem over the model class:
\vspace*{-0.3in}
\begin{enumerate}
\item a lower bound;
\vspace*{-0.3in}
\item a code which achieves it.
\end{enumerate}

\end{slide}

\begin{slide}{}
\underline{Rissanen's pointwise lower bound (1986):}
\vspace*{-0.3in}
\begin{itemize}
\item $x_1, x_2, \ldots, x_n$ IID $f_\theta^n$
\vspace*{-0.3in}
\item Model class
${\cal M}_d = \{ f_\theta: \theta \in \Theta_d \subset R^d \}$,
\vspace*{-0.3in}
\item $\theta$ can be estimated at the $n^{-1/2}$ rate.
\end{itemize}
\vspace*{-0.3in}
Then for any joint density $q_n$,
its average expected redundancy
\begin{eqnarray*}
E_{f_\theta^n} \log (f_\theta (x^n))/q_n(x^n) ) \geq d/2 \times 
 \log n (1+o(1))
\end{eqnarray*}
for all $\theta$ values except for a set which depends
on $q$ and has Lebesgue measure zero.

\end{slide}

\begin{slide}{}
\begin{itemize}
\item
The term $d/2 \times \log n $ measures the complexity of the model class
${\cal M}_d$, relative to the sample size $n$.
\vspace*{-0.3in}
\item
Two-stage and mixture forms achieve this lower bound hence
can be used in MDL applications.
\end{itemize}

\end{slide}

\begin{slide}{}

{\bf 4. MDL in Normal Linear Regression}

Model:
\begin{eqnarray*}
y = \sum_{\gamma_m = 1} \beta_m x_m + \epsilon ,
\label{reg:eqn}
\end{eqnarray*}
where 
\vspace*{-0.3in}
\begin{itemize}
\item $\epsilon  \equiv N(0, \sigma^2)$, 
\vspace*{-0.3in}
\item $\gamma = (\gamma_1,\ldots,\gamma_M) \in \{0,1\}^M$ 
index for the $2^M$ possible models.
\end{itemize}

Two-stage MDL is the same as
\begin{eqnarray*}
BIC(\gamma)= n/2 \times \log RSS(\gamma) + \frac{k_\gamma}{2} \times \log n.
\label{eqn:bic}
\end{eqnarray*}

Recall
\begin{eqnarray*}
AIC(\gamma)= n/2 \times \log RSS(\gamma) + \frac{k_\gamma}{2} \times 2.
\label{eqn:aic}
\end{eqnarray*}
\end{slide}

\begin{slide}{}
Under the finite-dim model assumption,
MDL criteria have been shown
to be consistent and have good prediction
properties (cf. Wei, 1991, Yu and Speed, 1994,
Barron et al, 1998).
\end{slide}

\begin{slide}{}

Deriving Two Mixture Forms of MDL:\\ gMDL and iMDL

\begin{itemize}
\item For any given $\gamma$, 
take an inverted gamma prior on $\tau = \sigma^2$,
$$
p(\tau) = \sqrt{\frac{a}{2\pi}}\tau^{-3/2}
\exp\left(\frac{-a}{2\tau}\right),
$$
\item
given $\tau$, $\beta$ has a multivariate Gaussian prior
$$p(\beta|\tau) \sim N(0,c\tau\Sigma).$$
\end{itemize}
\end{slide}

\begin{slide}{}

Set
$$
S_c = y^t (I_{n \times n} + c X \Sigma X^t)^{-1} y,
$$
so that the negative, log-marginal density of $y$ is given by
\begin{eqnarray*}
-\log m(y) & = & -\frac{1}{2} \log a + \frac{n+1}{2} \log (a + S_c)
\nonumber \\ & & \hspace*{3mm}+ \frac{1}{2} \log |I_{n \times n} + c X
\Sigma X^t|.
\label{eqn:mmdl}
\end{eqnarray*}

Optimizing over $a$ by taking $\hat{a}=S_c/n > 0$, 
yields
\begin{eqnarray*}
-\log m(y) = \frac{n}{2}\log S_c + \frac{1}{2} \log |I_{n \times n}
+ c X \Sigma X^t|.
\end{eqnarray*}

\end{slide}

\begin{slide}{}

Using Zellner's g-prior (1973) 
$\Sigma = (X^t X)^{-1}$ and minimizing over $c$, we
get
\begin{eqnarray*}
gMDL =\left\{
\begin{array}{l}
\frac{n}{2}\log{S} + \frac{k}{2}\log{F},
\quad R^2 \geq k/n, \\[3mm] \frac{n}{2} \log
(y^t y) \quad \mbox{otherwise}
\end{array}
\right.
\end{eqnarray*}

where we make the usual definitions

$ S = RSS/(n-k)$ and
$F = \frac{(y^ty-RSS)}{kS} $.

Using $\Sigma=I_{k\times k}$ as in Rissanen (1989),
we get iMDL whose minimizing $c$ 
has no closed form but
can be computed via in an iterative formula.
\end{slide}

\begin{slide}{}

{\bf 4a. Number of Bristles on the Fruit Fly}

Original data collected by Long et al (1995)
to identify genetic loci that influence
the number of bristles on the fruit fly.

As a linear regression variable selection problem:
(Cowen (1989), Doerge and Churchill (1996), Broman (1997)).

$y$: number of bristles 

$x$: gender indicator,on-and-off indictors at 19 genetic markers,
and their iteraction terms with gender (39 variables total).

\end{slide}
\begin{slide}{}
Broman (1997) used 
\[ BIC_\eta = n/2 \times \log RSS + \eta \times k/2 \times \log n ,\]
with $\eta=2, 2.5, 3$ to adapt to this problem.

All three give rise to an 8-term model:
\vspace*{-0.3in}
\begin{itemize}
\item constant term 
\vspace*{-0.3in}
\item  main effect for gender 
\vspace*{-0.3in}
\item five marker main effects (markers 2, 5, 9, 13 and 17), and
\vspace*{-0.3in}
\item one gender $\times$ marker interaction (at marker~5). 
\end{itemize}

\end{slide}

\begin{slide}{}
\begin{center}
\begin{tabular}{lrr}
 & Estimate & StdErr \\[0.1in]  \hline
 & & \\[0.1in]
intercept & 12.9 & 0.2\\
sex & -1.4 & 0.1 \\
M13.5 & 1.2 & 0.2\\
M35 & 1.1 & 0.3\\
M46 & 1.8 & 0.3 \\
M69.5 & 1.1 & 0.2 \\
M90 & 1.7 & 0.2 \\
sex $\times$ M35 & 0.9 & 0.1 \\
\end{tabular}
\end{center}
\end{slide}


\begin{slide}{}

\centerline{\psfig{figure=cmp.ps,width=6in}}

\end{slide}

\begin{slide}{}

{\bf 4b. A Simulation Study}

Set-up:  $y=X\beta+\epsilon$
\begin{itemize}
\vspace*{-0.3in}
\item $X \sim  N(0,\Sigma_{20\times 20})$, $\Sigma_{i,j}=\rho^{|i-j|}$,
\vspace*{-0.3in}
\item $\beta$ built from $k$ IID exp(1) and rest zero,
\vspace*{-0.3in}
\item $\epsilon \sim N(0,\sigma^2 I_{n\times n})$.
\end{itemize}
\vspace*{-0.3in}

Design:

$\rho( \{0.25, 0.77\}) \times$\\
\hspace*{1.5in} $k (\{5, 15\}) \times$\\
\hspace*{2.0in} $\sigma^2 (\{1/3, 3\}) \times$\\
\hspace*{3.5in} $n (\{100, 250\})$.

\end{slide}

\begin{slide}{}

\centerline{\psfig{figure=g1.ps,width=3in}
\psfig{figure=g2.ps,width=3in}}

\centerline{\psfig{figure=i1.ps,width=3in}
\psfig{figure=i2.ps,width=3in}}
\end{slide}

\begin{slide}{}
 
\centerline{\psfig{figure=g1.ps,width=6in}}

\end{slide}

\begin{slide}{}


\centerline{\psfig{figure=g2.ps,width=6in}}

\end{slide}

\begin{slide}{}

\centerline{\psfig{figure=i1.ps,width=6in}}
\end{slide}

\begin{slide}{}
\centerline{\psfig{figure=i2.ps,width=6in}}
\end{slide}

\begin{slide}{}
\vbox{
\centerline{Simulation: n=250, k=5 }
\vspace*{-0.25in}
\centerline{\psfig{figure=fig1a.ps,width=8in}}
}
\end{slide}

\begin{slide}{}
\vbox{
\centerline{Simulation: n=250, k=15 }
\vspace*{-0.25in}
\centerline{\psfig{figure=fig1b.ps,width=8in}}
}
\end{slide}

\begin{slide}{}
\vbox{
\centerline{Simulation: n=100, k=5 }
\vspace*{-0.25in}
\centerline{\psfig{figure=fig1c.ps,width=8in}}
}
\end{slide}

\begin{slide}{}
\vbox{
\centerline{Simulation: n=100, k=15 }
\vspace*{-0.25in}
\centerline{\psfig{figure=fig1d.ps,width=8in}}
}
\end{slide}



\begin{slide}{}

{\bf 5. Concluding Remarks}

Mixture forms of MDL criteria can be made adaptive...

Minimax framework in parametric case: connection to Jeffreys' prior
(Barron and Clarke, 1990)

PMDL: predictive description length...
 
New forms of MDL emerging: Normalized Maximum Likelihood
Rissanen (1996)...

Beyond $\log n$ term in parametric case...

Nonparametric: threoretical results in minimax framework
(Barron et al, 1997), but 
practical criteria just beginning (gMDl and iMDL in
spline knots selection, Hansen and Yu (1998)).

...
\end{slide}
\begin{slide}{}

Related papers:

Hansen and Yu: Model Selection and the MDL Principle
{\em (in preparation)}

Barron, Rissanen and Yu: Minimum Description Length Principle
in Coding and Modeling.
{\em IEEE Trans. Information Theory (Special Issue
for the 50th Anniversary of IT) (in press)}.
 
\end{slide}





\end{document}
\begin{slide}{}
{\large 5. Assessing MDL model selection criteria}

Frameworks under which to evaluate MDL criteria:

A. Finite dimensional model: the true model is finite dimensional.


B. Infinite dimensional model: all the model classes
are finite dimensional, but the true model is infinite
dim.
 
\end{slide}

\begin{slide}{}
1. Consistency: choose the true model eventually.

It makes sense only under A. 

Roughly speaking, all three forms of MDL
are consistent (so is BIC).  

cf. Hemerly and Davis (1989), Speed and Yu (1994), and Wei (1992).

Why?
\end{slide}

\begin{slide}{}

{\em Example 2 continued} 

The two part code leads to the following selection criterion:

choose ${\cal M}_0$ iff $|\bar{x}_n  | \leq \sqrt{\log n/n}$

When ${\cal M}_1 $ is true, 

the underfit prob \\
= $P_\theta ( |\bar{x}_n| \leq \sqrt{\log n/n} ) $\\
 $\approx P_\theta ( N(0,1) \geq \theta \sqrt{n} - \sqrt{\log n} ) $\\
$ \approx O(e^{-n \theta^2/2}) $.


When ${\cal M}_0$ is true,

the overfit prob\\ 
= $P_\theta ( |\bar{x}_n| > \sqrt{\log n/n} ) $\\
= $P_\theta ( |N(0,1)| > \sqrt{\log n} ) $\\
$ \approx O(1/\sqrt{n}) $.

\end{slide}

\begin{slide}{}
In terms of model bias: 

``cliff" phenomenen in asymptopia

\vspace{10cm} 

In practice, what matters is the magnitude of $\theta^2$ (or
squared bias in general) relative to $n$.

MDL (or BIC) is more conservative than AIC, which
is not consistent. 
\end{slide}

\begin{slide}{}
2. Prediction errors

Prediction without refitting and with refitting.

Finite dim true model: MDL (and BIC) optimal, but
AIC not too bad.

Infinite dim true model: AIC optimal.

``Transition" is gradual...

\vspace{5cm}

\end{slide}

\begin{slide}{}
{\large 6. MDL in the non-paramatric case} 

Model classes are smooth density classes

\begin{eqnarray*}
&&  LIP(s, C) =\\
& & \{f \mbox{ density on } [0,1]:\\
& & \sup_{0 \leq x \leq 1} |f^{(i)} (x)| \leq C\;\;\;
\mbox{ for } i = 1, ..., k,\\
& & |f^{(k)}(x)-f^{(k)}(y)| \leq C|x-y|^\nu \;\;\;
\mbox{ for } 0 \leq x, y \leq 1 \},
\end{eqnarray*}

where $C$ is a fixed constant, $k$ is a positive integer,
and $\nu$ is such that $0 < \nu \leq 1$ and $s=k+\nu >1 $.

Then $LIP(1,C)$ is the class of bounded derivatives.

\end{slide}

\begin{slide}{}
Expected redundancy of $q_n$:
\begin{eqnarray*}
& & E_{f^n} \log f^n(X^n)/q_n(X^n)\\
& =& \sum_t E_{f^{t-1}} E_f\log f(X_t)/\hat{q}_{t-1}(X_t)\\
& =& \sum_t E_{f^{t-1}} K(f,\hat{q}_{t-1})\\
& =& \mbox{ accumulated est. error in K-L divergence}.
\end{eqnarray*}

\begin{eqnarray*}
& & \sum_t E_{f^{t-1}} K(f,\hat{q}_{t-1})\\
& \geq & \sum_t E_{f^{t-1}} H^2 (f,\hat{q}_{t-1}).
\end{eqnarray*}

\end{slide}

\begin{slide}{}
Universal coding theorem is equiv.
to lower bounds:

``Pointwise": Rissanen, Speed and Yu (1992).

Minimax:

via estimation error, see Yu and Speed (1992).

via infor. theoretic means, see Yu (1996),
and Yang and Barron (1995).



\end{slide}
\begin{slide}{}

MDL motivated results on estimation:

Within $\log n$ factor of optimal rate:

Barron and Cover (1991), Yu and Speed (1992).

Adaptive to smoothness of Sobolev spaces:

Yang and Barron (1996).

\end{slide}

\end{document}
