
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%   Robust Estimators under the Imprecise Dirichlet Model   %%
%%     Marcus Hutter: Start: 01.08.02  LastEdit: 08.08.02    %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%-------------------------------%
%   Document-Style              %
%-------------------------------%
\documentclass[12pt,twoside]{article}
%\usepackage{latexsym}
%\usepackage{epsf}
\usepackage{amsmath}
\usepackage{amssymb}

\def\contentsname{\centering Contents}
\pagestyle{myheadings}
\markboth{\sc Marcus Hutter, Technical Report, IDSIA-03-03
}{\sc Robust Estimators under the Imprecise Dirichlet Model}
\setcounter{tocdepth}{4} \setcounter{secnumdepth}{2}
\topmargin=0mm  \oddsidemargin=5mm \evensidemargin=5mm
\textwidth=15cm \textheight=22.1cm
\sloppy

%-------------------------------%
%       My Math-Spacings        %
%-------------------------------%
\def\,{\mskip 3mu} \def\>{\mskip 4mu plus 2mu minus 4mu} \def\;{\mskip 5mu plus 5mu} \def\!{\mskip-3mu}
\def\dispmuskip{\thinmuskip= 3mu plus 0mu minus 2mu \medmuskip=  4mu plus 2mu minus 2mu \thickmuskip=5mu plus 5mu minus 2mu}
\def\textmuskip{\thinmuskip= 0mu                    \medmuskip=  1mu plus 1mu minus 1mu \thickmuskip=2mu plus 3mu minus 1mu}
\textmuskip
\def\beq{\dispmuskip\begin{equation}}    \def\eeq{\end{equation}\textmuskip}
\def\beqn{\dispmuskip\begin{displaymath}}\def\eeqn{\end{displaymath}\textmuskip}
\def\bqa{\dispmuskip\begin{eqnarray}}    \def\eqa{\end{eqnarray}\textmuskip}
\def\bqan{\dispmuskip\begin{eqnarray*}}  \def\eqan{\end{eqnarray*}\textmuskip}

%-------------------------------%
%   Macro-Definitions           %
%-------------------------------%
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}

\newenvironment{keywords}{\centerline{\bf
Keywords}\vspace{0.5ex}\begin{quote}\small}{\par\end{quote}\vskip
1ex}

\def\subsection#1{\vspace{1ex}\noindent{\bf{#1.}}}
\def\paragraph#1{\vspace{1ex}\noindent{\bf{#1.}}}
\def\ff{\Longrightarrow}
\def\gdw{\Longleftrightarrow}
\def\toinfty#1{\stackrel{#1\to\infty}{\longrightarrow}}
\def\nq{\hspace{-1em}}
\def\look{\(\uparrow\)}
\def\qed{\hspace*{\fill}$\Box\quad$}
\def\odt{{\textstyle{1\over 2}}}
\def\eps{\varepsilon}
\def\blank{{\,_\sqcup\,}}                 % blank position
\def\mnx{{\mathop{\rm mnx}}}          % maxarg
\def\p{{\scriptscriptstyle+}}
\def\pp{{\scriptscriptstyle++}}
\def\n{{n}}
\def\npp{\n}
\def\u{u} %u or \theta or \vartheta
\def\kdot{{\dot\kappa}}
\def\v{\boldsymbol} %\boldsymbol\frak\Bbb\pmb\text
\def\vt{{\v t}}\def\vu{{\v u}}\def\vpi{{\v\pi}}
\def\pin{{\scriptstyle\Pi}}
\def\Var{{\mbox{Var}}}
\def\Cov{{\mbox{Cov}}}
\def\qmbox#1{{\quad\mbox{#1}\quad}}
\def\propersubset{\subsetneq}
\def\low{\underline}
\def\up{\overline}
\def\DeltaOX{\Delta\hspace{-8pt}{\scriptscriptstyle^{_\otimes}}}
\def\deltaOX{\Delta\hspace{-6.5pt}{\scriptscriptstyle^{_\otimes}}}
\def\Deltapi{\Delta}
\def\Deltal{\Delta_e}
\def\Deltapl{\Delta'_e}
\def\ots{{\scriptscriptstyle\!\otimes}}
\def\Vol{\mbox{Vol}}
\def\argmax{\mathop{\rm arg\,max}}          % maxarg
\def\argmin{\mathop{\rm arg\,min}}          % minarg
\def\leqsq{\sqsubseteq}
\def\geqsq{\sqsupseteq}
\def\Set#1{{\if#1Q{I\!\!\!#1}\else\if#1Z{Z\!\!\!Z}\else{I\!\!#1}\fi\fi}}
\def\maxo{\max}                        %supremum over open Delta
\def\mino{\min}                        %infimum over open Delta

\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                      T i t l e - P a g e                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{\vskip -5mm\normalsize\sc Technical Report \hfill IDSIA-03-03
\vskip 2mm\bf\LARGE\hrule height5pt \vskip 3mm
\sc Robust Estimators under the \\ Imprecise Dirichlet Model%\thanks{%
\vskip 6mm \hrule height2pt \vskip 5mm}
\author{{\bf Marcus Hutter}\\[3mm]
\normalsize IDSIA, Galleria 2, CH-6928\ Manno-Lugano, Switzerland\\
\normalsize marcus@idsia.ch \hspace{8.5ex} http://www.idsia.ch/$^{_{_\sim}}\!$marcus}
\date{May 5, 2003}
\maketitle

\begin{abstract}
Walley's Imprecise Dirichlet Model (IDM) for categorical data
overcomes several fundamental problems which other approaches to
uncertainty suffer from. Yet, to be useful in practice, one needs
efficient ways for computing the imprecise=robust sets or
intervals. The main objective of this work is to derive exact,
conservative, and approximate, robust and credible interval
estimates under the IDM for a large class of statistical
estimators, including the entropy and mutual information.
\end{abstract}
\vspace{5cm}

\pagebreak

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}\label{secInt}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
This work derives interval estimates under the Imprecise Dirichlet
Model (IDM) \cite{Walley:96} for a large class of statistical
estimators. In the IDM one considers an i.i.d.\ process with
unknown chances\footnote{Also called {\em objective} or {\em
aleatory} probabilities.} $\pi_i$ for outcome $i$. The prior
uncertainty about $\vpi$ \footnote{We denote vectors by $\v
x:=(x_1,...,x_d)$ for $\v x\in\{\v n,\vt,\vu,\vpi,...\}$.}is
modeled by a set of Dirichlet priors\footnote{Also
called {\em second order} or {\em subjective} or {\em belief} or
{\em epistemic} probabilities.}
$\{p(\vpi)\propto\prod_i\pi_i^{st_i-1}\,:\,\vt\in\Delta\}$, where%
\footnote{Strictly speaking, $\Delta$ should be the open simplex
\cite{Walley:96}, since $p(\vpi)$ is improper for $\vt$ on the
boundary of $\Delta$. For simplicity we assume that, if necessary,
considered functions of $\vt$ can and are continuously extended
to the boundary of $\Delta$, so that, for instance, minima and
maxima exist. All considerations can straightforwardly, but
cumbersomely, be rewritten in terms of an open simplex. Note that
open/closed $\Delta$ result in open/closed robust intervals, the
difference being numerically/practically irrelevant.
} $\Delta:=\{\vt\,:\,t_i\geq 0,\, \sum_i t_i=1\}$, and $s$ is a
hyper-parameter, typically chosen between 1 and 2. Sets of
probability distributions are often called Imprecise
probabilities, hence the name IDM for this model. We avoid the
term {\em imprecise} and use {\em robust} instead, or capitalize
{\em Imprecise}. IDM overcomes several fundamental problems which
other approaches to uncertainty suffer from \cite{Walley:96}. For
instance, IDM satisfies the representation invariance principle
and the symmetry principle, which are mutually exclusive in a pure
Bayesian treatment with proper prior \cite{Walley:96}. The counts
$n_i$ for $i$ form a minimal sufficient statistic of the data of
size $n=\sum_i n_i$. Statistical estimators $F(\v n)$ usually also
depend on the chosen prior: so a set of priors leads to a set of
estimators $\{F_\vt(\v n)\,:\;\vt\in\Delta\}$. For instance,
the expected chances $E_\vt[\pi_i]={n_i+st_i\over
n+s}=:\u_i(\vt)$ lead to a robust interval estimate $[{n_i\over
n+s},{n_i+s\over n+s}]\ni E_\vt[\pi_i]$. Robust intervals for
the variance $\Var[\pi_i]$ \cite{Walley:96} and for the mean and
variance of linear-combinations $\sum_i\alpha_i\pi_i$ have also
been derived \cite{Bernard:01}. Bayesian estimators (like
expectations) depend on $\vt$ and $\v n$ only through $\vu$
(and $n+s$ which we suppress), i.e.\ $F_\vt(\v n)=F(\vu)$.
The main objective of this work is to derive approximate,
conservative, and exact intervals $[\mino_{\vt\in\Delta}F(\vu),\maxo_{\vt\in\Delta}F(\vu)]$ for general
$F(\vu)$, and for the expected (also called predictive) entropy
and the expected mutual information in particular. These results
are key building blocks for applying IDM. Walley suggests, for
instance, to use $\mino_\vt P_\vt[{\cal F}\geq c]\geq\alpha$
for inference problems and $\mino_\vt E_\vt[{\cal F}]\geq c$
for decision problems \cite{Walley:96}, where $\cal F$ is some
function of $\vpi$. One application is the inference of robust
tree-dependency structures \cite{Zaffalon:01tree,Hutter:03tree},
in which edges are partially ordered based
on Imprecise mutual information.

Section \ref{secIDM} gives a brief introduction to
IDM and describes our problem setup.
%
In Section \ref{secEEI} we derive exact robust intervals for
concave functions $F$, such as the entropy.
%
Section \ref{secAEI} derives approximate robust intervals for arbitrary
$F$.
%
In Section \ref{secEP} we show how bounds of elementary functions
can be used to get bounds for composite function, especially for
sums and products of functions. The results are used in
%
Section \ref{secIEMI} for deriving robust intervals for the
mutual information.
%
The issue of how to set up IDM models on
product spaces is discussed in Section \ref{secPS}.
%
Section \ref{secCI} addresses the problem of how to combine
Bayesian credible intervals with the robust intervals of the IDM.
%
Conclusions are given in Section \ref{secConc}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Imprecise Dirichlet Model}\label{secIDM}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%-------------------------------%
\subsection{Random i.i.d.\ processes}
%-------------------------------%
We consider discrete random variables $\imath\in\{1,...,d\}$ and
an i.i.d.\ random process with outcome $i\in\{1,...,d\}$ having
probability $\pi_i$. The chances $\vpi$ form a probability
distribution, i.e.\ $\vpi\in\Deltapi:=\{\v x\in\Set R^d\,:\,x_i\geq
0\,\forall i,\; x_\p=1\}$, where we have used the abbreviation $\v
x=(x_1,...,x_d)$ and $x_\p:=\sum_{i=1}^d x_i$. The likelihood of a
specific data set $\v D$ with $n_i$ observations $i$ and total
sample size $n=n_\p=\sum_i n_i$ is $p(\v
D|\vpi)=\prod_i\pi_i^{n_i}$.
%
The chances $\pi_i$ are usually unknown and have to be estimated
from the sample frequencies $n_i$. The frequency estimate
${n_i\over n}$ for $\pi_i$ is one possible point estimate.

%-------------------------------%
\subsection{Second order p(oste)rior}
%-------------------------------%
In the Bayesian approach one models the initial uncertainty in
$\vpi$ by a (second order) prior ``belief'' distribution
$p(\vpi)$ with domain $\vpi\in\Deltapi$. The Dirichlet priors
$p(\vpi)\propto\prod_i\pi_i^{n'_i-1}$, where $n'_i$ comprises prior
information, represent a large class of priors. $n'_i$ may be
interpreted as (possibly fractional) virtual number of ``observation''.
High prior belief in $i$ can be modeled by large $n'_i$. It is
convenient to write $n'_i=s\cdot t_i$ with $s:=n'_+$, hence $\vt\in\Delta$. Having no initial bias one should choose a prior in
which all $t_i$ are equal, i.e.\ $t_i={1\over d}\,\forall i$.
Examples for $s$ are $0$ for Haldane's prior \cite{Haldane:48},
$1$ for Perks' prior \cite{Perks:47}, ${d\over 2}$ for Jeffreys'
prior \cite{Jeffreys:46}, and $d$ for Bayes-Laplace's uniform
prior \cite{Gelman:95}. From the prior and the data likelihood one
can determine the posterior $p(\vpi|\v D)=p(\vpi|\v
n)\propto\prod_i\pi_i^{n_i+st_i-1}$.

The posterior $p(\vpi|\v D)$ summarizes all statistical
information available in the data. In general, the posterior is a
very complex object, so we are interested in summaries of this
plethora of information. A possible summary is the expected
value or mean
$
  E_\vt[\pi_i]={n_i+st_i\over n+s}
$
which is often used for estimating $\pi_i$. The accuracy may be
obtained from the covariance of $\vpi$.

Usually one is not only interested in an estimation of the whole
vector $\vpi$, but also in an estimation of scalar functions
${\cal F}:\Deltapi\to I\!\!R$ of $\vpi$, such as the entropy
${\cal H}(\vpi)=-\sum_i\pi_i\log\pi_i$, where $\log$ denotes the
natural logarithm. Since $\cal F$ is itself a random variable we
could determine the posterior distribution $p({\cal F}_0|\v
n)=\int_{\Deltapi}\delta({\cal F}(\vpi)-{\cal F}_0)p(\vpi|\v
n)d\vpi$ of ${\cal F}$, which may further be summarized by the
posterior mean $E_\vt[{\cal F}]=\int_{\Deltapi}{\cal
F}(\vpi)p(\vpi|\v n)d\vpi$ and possibly the posterior variance
$\Var[{\cal F}]$.
%
A simple, but crude approximation for the mean can be obtained by
exchanging $E$ with ${\cal F}$ (exact only for linear functions):
$E_\vt[{\cal F}(\vpi)]\approx {\cal F}(E_\vt[\vpi])$. The
approximation error is typically of the order $1\over n$.

%-------------------------------%
\subsection{The Imprecise Dirichlet Model}
%-------------------------------%
The classical approach, which consists of selecting a single
prior, suffers from a number of problems. Firstly, choosing for
example a uniform prior $t_i={1\over d}$, the prior depends on the
particular choice of the sampling space.
Secondly, it assumes exact prior knowledge of $p(\vpi)$. The
solution to the second problem is to model our ignorance by
considering sets of priors $p(\vpi)$, often called Imprecise
probabilities. The specific {\em Imprecise Dirichlet Model} (IDM)
\cite{Walley:96} considers the set of {\em all} $\vt\in\Delta$,
i.e. $\{p(\vpi|\v n):\vt\in\Delta\}$ which solves also the first
problem. Walley suggests to fix the hyperparameter $s$ somewhere
in the interval $[1,2]$. A set of priors results in a set of
posteriors, set of expected values, etc. For real-valued
quantities like the expected entropy $E_\vt[{\cal H}]$ the sets
are typically intervals, which we call robust
intervals
\beqn
  E_\vt[{\cal F}] \in [\mino_{\vt\in\Delta}E_\vt[{\cal F}] \,,\,
    \maxo_{\vt\in\Delta}E_\vt[{\cal F}]].
\eeqn

%-------------------------------%
\subsection{Problem setup and notation}
%-------------------------------%
Consider any statistical estimator $F$. $F$ is a function of the
data $\v D$ and the hyperparameters $\vt$.
We define the general correspondence
\beq\label{thtrel}
 \u_i^{\cdots}={n_i+st_i^{\cdots}\over n+s},
 \quad\mbox{where $^{\ldots}$ can be various superscripts}.
\eeq
$F$ can, hence, be rewritten as a function of $\vu$ and $\v D$.
Since we regard $\v D$ as fixed, we suppress this dependence and
simply write $F=F(\vu)$. This is further motivated by the fact
that all Bayesian estimators of functions $\cal F$ of $\vpi$ only
depend on $\vu$ and the sample size $n+s$. It is easy to see
that this holds for the mean, i.e.\ $E_\vt[{\cal
F}]=F(\vu\,;\,n+s)$, and similarly for the variance and all higher
(central) moments. The main focus of this work is to derive exact
and approximate expressions for upper and lower $F$ values
\beqn
 \up{F}:=\maxo_{\vt\in\Delta}F(\vu)
 \qmbox{and}
 \low F:=\mino_{\vt\in\Delta}F(\vu),\qquad
 \up{\low F}:=[\low F,\up F]
\eeqn
$\vt\in\Delta$ $\Leftrightarrow$
$\vu\in\Delta'$, where $\Delta':=\{\vu\,:\,\u_i\geq{n_i\over
n+s},\;\u_\p=1\}$. We define $\vu^{\up F}$ as the
$\vu\in\Delta'$ which maximizes $F$, i.e.\ $\up F=F(\vu^{\up
F})$, and similarly $\vt^{\up F}$ through relation
(\ref{thtrel}). If the maximum of $F$ is assumed in a corner of
$\Delta'$ we denote the index of the corner by $i^{\up F}$, i.e.\
$t_i^{\up F}=\delta_{ii^{\up F}}$, where $\delta_{ij}$ is
Kronecker's delta function. Similarly $\vu^{\low F}$, $\vt^{\low F}$, $i^{\low F}$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Exact Robust Intervals for Concave Estimators}\label{secEEI}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this section we derive exact expressions for $\up{\low F}$ if
$F:\Delta\to I\!\!R$ is of the form
\beq\label{Fconc}
  F(\vu)=\sum_{i=1}^d f(\u_i)
  \qmbox{and concave} f:[0,1]\to I\!\!R.
\eeq
The expected entropy is such an example (discussed later). Convex
$f$ are treated similarly (or simply take $-f$).

%-------------------------------%
\subsection{The nature of the solution}
%-------------------------------%
The approach to a solution of this problem is motivated as
follows: Due to symmetry and concavity of $F$, the global maximum
is attained at the center $\u_i={1\over d}$ of the probability
simplex $\Delta$, i.e.\ the more uniform $\vu$ is, the larger
$F(\vu)$. The nearer $\vu$ is to a vertex of $\Delta$, i.e.\
the more unbalanced $\vu$ is, the smaller is $F(\vu)$. The
constraints $t_i\geq 0$ restrict $\vu$ to the smaller simplex
\beqn
  \Delta'=\{\vu\,:\,\u_i\geq\u_i^0,\;\u_\p=1\}
  \qmbox{with} \u_i^0:={n_i\over n+s},
\eeqn
which prevents setting $\u_i^{\up
F}={1\over d}$ and $\u_i^{\low F}=\delta_{i1}$.
Nevertheless, the basic idea of choosing $\vu$ as
uniform / as unbalanced as possible still works, as we will see.

%-------------------------------%
\subsection{Greedy $F(\vu)$ minimization}
%-------------------------------%
Consider the following procedure for obtaining $\vu^{\low F}$.
We start with $\vt\equiv\v 0$ (outside the usual domain $\Delta$
of $F$, which can be extended to
$[0,1]^d$ via (\ref{Fconc})) and then gradually increase $\vt$ in
an axis-parallel way until $t_\p=1$. With axis-parallel we mean
that only one component of $\vt$ is increased, which one possibly
changes during the process. The total zigzag curve from $\vt^{start}=\v 0$ to $\vt^{end}$ has length $t_\p^{end}=1$. Since
all possible curves have the same (Manhattan) length 1,
$F(\vu^{end})$ is minimized for the curve which has (on average)
smallest $F$-gradient along its path. A greedy strategy is to
follow the direction $i$ of currently smallest $F$-gradient
${\partial F\over\partial t_i}=f'(\u_i){s\over n+s}$. Since $f'$
is monotone decreasing ($f''<0$), ${\partial F\over\partial t_i}$
is smallest for largest $\u_i$. At $\vt^{start}=\v 0$,
$\u_i={n_i\over n+s}$ is largest for $i=i^{min}:=\arg\max_i n_i$.
Once we start in direction $i^{min}$, $\u_{i^{min}}$ increases
even further whereas all other $\u_i$ ($i\neq i^{min}$) remain
constant. So the moving direction is never changed and finally we
reach a local minimum at $t_i^{end}=\delta_{ii^{min}}$.
In \cite{Hutter:03idmx} we show that this is a global minimum,
i.e.\
\beq\label{Fmin}
  t_i^{\low F}=\delta_{ii^{\low F}} \qmbox{with}
  i^{\low F}:=\arg\max_i n_i.
\eeq

%-------------------------------%
\subsection{Greedy $F(\vu)$ maximization}
%-------------------------------%
Similarly we maximize $F(\vu)$. Now we increase $\vt$ in direction
$i=i_1$ of maximal ${\partial F\over\partial t_i}$, which is
the direction of smallest $\u_i\propto n_i+st_i$.
Again, (only) $\u_{i_1}$ increases, but possibly reaches a value
where it is no longer the smallest one. We stop if it becomes
equal to the second smallest $\u_i$, say $i=i_2$. We now have to
increase $\u_{i_1}$ and $\u_{i_2}$ with same speed (or in an
$\eps$-zigzag fashion) until they become equal to $\u_{i_3}$, etc
or until $\u_\p=1=t_\p$ is reached. Assume the process stops with
direction $i_m$ and minimal $\u$ being $\tilde\u$, i.e.\ finally
$\u_{i_k}=\tilde\u$ for $k\leq m$ and $t_{i_k}=0$ for $k>m$.
From the constraint $1=\u_\p=\sum_{k\leq
m}\u_{i_k}+\sum_{k>m}\u_{i_k} = m\tilde\u+\sum_{k>m}{n_{i_k}\over
n+s}$ we obtain $\tilde\u(m)={1\over m}[1-\sum_{k>m}{n_{i_k}\over n+s}]=
[s+\sum_{k\leq m}n_{i_k}]/[m(n+s)]$. One can show that
$\tilde\u(m)$ has one global minimum (no local ones)
and that the final $m$
is the one which minimizes $\tilde\u$, i.e.\
\beq\label{Fmax}
  \tilde\u = \min_{m\in\{1...d\}} {s+\sum_{k\leq m} n_{i_k}\over
  m(n+s)}, \;\;\mbox{where}\;\; n_{i_1}\leq
  n_{i_2}\leq...\leq\n_{i_d},\quad
  \u_i^{\up F}=\max\{\u_i^0,\tilde\u\}.
\eeq
%
If there is a unique minimal $n_{i_1}$ with gap
$\geq s$ to the 2nd smallest $n_{i_2}$ (which is quite likely for not
too small $n$), then $m=1$ and the maximum is attained at a
corner of $\Delta$ ($\Delta'$).

\begin{theorem}[Exact extrema for concave functions on simplices]\label{thEEI}
Assume $F:\Delta'\to I\!\!R$ is a concave function of the form
$F(\vu)=\sum_{i=1}^df(\u_i)$.
%, where $\Delta'=\{\vu\,:\,\u_i\geq {n_i\over n+s},\;\u_\p=1\}$.
Then $F$ attains the global maximum $\up F$ at $\vu^{\up F}$
defined in (\ref{Fmax}) and the global minimum $\low F$ at
$\vu^{\low F}$ defined in (\ref{Fmin}).
\end{theorem}

\paragraph{Proof} What remains to be shown is that the solutions
obtained in the last paragraphs by greedy
minimization/maximization of $F(\vu)$ are actually global
minima/maxima. For this assume that $\vt$ is a local minimum of
$F(\vu)$. Let $j:=\arg\max_i\u_i$ (ties broken arbitrarily).
Assume that there is a $k\neq j$ with non-zero $t_k$. Define
$\vt'$ as $t'_i=t_i$ for all $i\neq j,k$, and $t'_j=t_j+\eps$,
$t'_k=t_k-\eps$, for some $0<\eps\leq t_k$. From $\u_k\leq \u_j$
and the concavity of $f$ we get\footnote{Slope
${f(\u+\eps)-f(\u)\over\eps}$ is a decreasing function in $\u$
for any $\eps>0$, since $f$ is concave.}
\bqan
  F(\vt')-F(\vt) &=& [f(\u'_j)+f(\u'_k)]-[f(\u_j)+f(\u_k)]
  \\ &=&
  [f(\u_j\!+\!\sigma\eps)-f(\u_j)]-[f(\u_k)-f(\u_k\!-\!\sigma\eps)] \;<\; 0
\eqan
where $\sigma:={s\over n+s}$. This contradicts the minimality
assumption of $\vt$. Hence, $t_i=0$ for all $i$ except one (namely $j$,
where it must be 1). (Local) minima are attained in the vertices
of $\Delta$. Obviously the global minimum is for $t_i^{\low
F}=\delta_{ii^{\low F}}$ with $i^{\low F}:=\arg\max_i n_i$. This
solution coincides with the greedy solution. Note that the global
minimum may not be unique, but since we are only interest in
the value of $F(\vu^{\low F})$ and not its argument this
degeneracy is of no further significance.

Similarly for the maximum, assume that $\vt$ is a (local)
maximum of $F(\vu)$. Let $j:=\arg\min_i\u_i$ (ties broken
arbitrarily). Assume that there is a $k\neq j$ with
non-zero $t_k$ {\em and} $\u_k>\u_j$. Define $\vt'$ as above with
$0<\eps<\min\{t_k\,,\,t_k-t_j\}$. Concavity of $f$ implies
\beqn
  F(\vt')-F(\vt) =
  [f(\u_j\!+\!\sigma\eps)-f(\u_j)]-[f(\u_k)-f(\u_k\!-\!\sigma\eps)] > 0,
\eeqn
which contradicts the maximality assumption of $\vt$. Hence
$t_i=0$ if $\u_i$ is not minimal ($\tilde\u$). The previous
paragraph constructed the unique solution $\vu^{\up F}$ satisfying
this condition. Since this is the only local maximum it must be
the unique global maximum (contrast this to the minimum case).
\qed

\begin{theorem}[Exact extrema of expected entropy]\label{corEEI}
Let ${\cal H}(\vpi)=-\sum_i \pi_i\log\pi_i$ be the entropy of
$\vpi$ and the uncertainty of $\vpi$ be modeled by the Imprecise
Dirichlet Model. The expected entropy $H(\vu):=E_\vt[{\cal
H}]$ for given hyperparameter $\vt$ and sample $\v n$ is given by
\beq\label{hex}
  H(\vu)=\sum_i h(\u_i) \qmbox{with}
  h(\u)=\u\!\cdot\![\psi(n\!+\!s\!+\!1)-\psi((n\!+\!s)\u\!+\!1)] =
  \u\cdot\!\!\!\!\nq\sum_{k={(n+s)}u+1}^{n+s}\nq\!\! k^{-1}
\eeq
where $\psi(x)=d\,\log\Gamma(x)/dx$ is the logarithmic derivative of
the Gamma function and the last expression is valid for integral $s$
and $(n+s)u$. The lower $\low H$ and upper $\up H$ expected
entropies are assumed at $\vu^{\low H}$ and $\vu^{\up H}$ given in
(\ref{Fmin}) and (\ref{Fmax}) (with $F\leadsto H$, see also
(\ref{thtrel})).
\end{theorem}

A derivation of the exact expression (\ref{hex}) for the
expected entropy can be found in
\cite{Wolpert:95,Hutter:01xentropy}. The only thing to be shown is
that $h$ is concave. This may be done by exploiting special
properties of the digamma function $\psi$ (see
\cite{Abramowitz:74}).

There are fast implementations of $\psi$ and its derivatives and
exact expressions for integer and half-integer arguments

\paragraph{Example} For $d=2$, $n_1=3$, $n_2=6$, $s=1$ we have $n=9$,
$\u_1={3+t_1\over 10}$, $\u_2={6+t_2\over 10}$, $\vt^0=0$,
$\vu^0=({.3\atop .6})$, see (\ref{thtrel}).
%
From (\ref{Fmin}), $i^{\low H}=2$, $\vt^{\low
H}=({0\atop 1})$, $\vu^{\low H}=({.3\atop .7})$.
%
From (\ref{Fmax}), $i_1=1$, $i_2=2$, $\tilde\u=\min\{{1+3\over
9+1},{1+3+6\over 2\cdot(9+1)}\}={4\over 10}$, $\vu^{\up
H}=\max\{\vu^0,\tilde\u\}=({.4\atop .6})$ $\Rightarrow$
$\vt^{\up H}=({1\atop 0})$ is in corner.
%
From (\ref{hex}), %
$h({3\over 10})={2761\over 8400}$,
$h({4\over 10})={2131\over 6300}$,
$h({6\over 10})={1207\over 4200}$,
$h({7\over 10})={847\over 3600}$, hence
$\up{\low H}=[H(\vu^{\low H}),H(\vu^{\up H})]=
 [h({3\over 10})+h({7\over 10})\, ,\, h({4\over 10})+h({6\over 10})]
 =[0.5639...,0.6256...]$, so $\up H-\low H=O({1\over 10})$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Approximate Robust Intervals}\label{secAEI}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%-------------------------------%
%\subsection{Taylor expansion of $F(\vu)$}
%-------------------------------%
In this section we derive approximations for $\up{\low F}$
suitable for arbitrary, twice differentiable functions
$F(\vu)$.
%
The derived approximations for $\up{\low F}$ will be robust in the
sense of covering set $\up{\low F}$ (for any $n$), and the
approximations will be ``good'' if $n$ is not too small.
%
In the following, we treat $\sigma:={s\over n+s}$ as a (small)
expansion parameter.
%
For $\vu,\vu^*\in\Delta'$ we have
\beq\label{dtbnd}
  \u_i-\u_i^* \;=\; \sigma\!\cdot\!(t_i-t_i^*) \qmbox{and}
  |\u_i-\u_i^*| \;=\; \sigma|t_i-t_i^*| \;\leq\; \sigma
  \qmbox{with} \sigma:=\textstyle{s\over n+s}.
\eeq
Hence we may Taylor-expand $F(\vu)$ around $\vu^*$, which
leads to a Taylor series in $\sigma$. This shows that $F$ is
approximately linear in $\vu$ and hence in $\vt$. A linear
function on a simplex assumes its extreme values at the vertices
of the simplex. This has already been encountered in Section
\ref{secEEI}. The consideration above is a simple explanation for
this fact. This also shows that the robust interval $\up{\low F}$
is of size $\up F-\low F=O(\sigma)$.\footnote{$f(\v n,\vt,s)=O(\sigma^k)$ $\;:\Leftrightarrow\;$ $\exists c\,\forall\v
n\in I\!\!N_0^d,\,\vt\in\Delta,\,s>0$ : $|f(\v n,\vt,s)|\leq
c\sigma^k$, where $\sigma={s\over n+s}$.} Any approximation to
$\up{\low F}$ should hence be at least $O(\sigma^2)$. The
expansion of $F$ to $O(\sigma)$ is
\beq\label{Fexpand}
  F(\vu) \;=\; \overbrace{F(\vu^*)}^{F_0=O(1)} +
  \overbrace{\sum_i[\partial_i F(\v{\check\u})](\u_i-\u_i^*)}^{F_R=O(\sigma)}
\eeq
where $\partial_i F(\v{\check\u})$ is the partial derivative
$\partial_i F(\v{\check\u})\over\partial\check\u_i$ of
$F(\v{\check\u})$ w.r.t.\ $\check\u_i$. For suitable
$\v{\check\u}=\v{\check\u}(\vu,\vu^*)\in\Delta'$ this expansion is
exact ($F_R$ is the exact remainder).
%
Natural points for expansion are $t_i^*={1\over d}$ in the center
of $\Delta$, or possibly also $t_i^*={n_i\over n}=\u_i^*$. See
\cite{Hutter:03idmx}
for such a general expansion. Here, we expand around the improper
point $t_i^*:=t_i^0\equiv 0$, which is outside(!) $\Delta$, since
this makes expressions particularly
simple.$\!\!$\footnote{The order of accuracy
$O(\sigma^2)$ we will encounter is for all choices of $\vu^*$
the same. The concrete numerical errors differ of course. The
choice $\vt^*=\v 0$ can lead to $O(d)$ smaller $F_R$ than the
natural center point $\vt^*={1\over d}$, but is more likely a
factor $O(1)$ larger. The exact numerical values depend on the
structure of $F$.} (\ref{dtbnd}) is still valid in this case,
and $F_R$ is exact for some
$\v{\check\u}$ in
\beqn
  \Deltapl:=\{\vu\,:\,\u_i\geq\u_i^0\,\forall i,\;\u_\p\leq 1\},
  \qmbox{where}
  \u_i^0={n_i\over n+s}.
\eeqn
Note that we keep the exact condition
$\vu\in\Delta'$. $F$ is usually already defined on
$\Deltapl$ or extends from $\Delta'$ to $\Deltapl$
without effort in a natural way (analytical continuation). We
introduce the notation
\beq\label{eqleqsq}
  F\leqsq G \quad:\Leftrightarrow\quad
  F\leq G \qmbox{and} F=G+O(\sigma^2)
\eeq
stating that $G$ is a ``good'' upper bound on $F$.
The following bounds hold for arbitrary differentiable functions.
In order for the bounds to be ``good,$\!$'' $F$ has to be Lipschitz
differentiable in the sense that there exists a constant $c$ such that
\beqn
  |\partial_i F(\vu)|\leq c \qmbox{and}
  |\partial_i F(\vu)-\partial_i F(\vu')|
  \leq c|\vu-\vu'|
\eeqn
\beq\label{Lipschitz}
  \forall\,\vu,\vu'\in\Deltapl
  \qmbox{and} \forall\,1\leq i \leq d.
\eeq
\beqn
  \mbox{If $F$ depends also on $\v n$, e.g.\ via $\sigma$ or
  $\vu^0$, then $c$ shall be independent of them.}
\eeqn
The Lipschitz condition is satisfied, for instance, if the
curvature $\partial^2 F$ is uniformly bounded. This is satisfied
for the expected entropy $H$ (see (\ref{hex})), but violated for
the approximation $E_\vt[{\cal H}]\approx{\cal H}(\vu)$ if $n_i=0$ for
some $i$.

\begin{theorem}[Approximate robust intervals]\label{thARI}
Assume $F:\Deltapl\to I\!\!R$ is a Lipschitz differentiable
function (\ref{Lipschitz}).
Let $[\low F,\up F]$ be the global [minimum,maximum] of $F$ restricted
to $\Delta'$. Then
\beqn
  F(\vu^1) \;\leqsq\; \up F \;\leqsq\; F_0+F_R^{ub}
  \;\;\mbox{where}\;\; F_R^{ub}=\max_i F_{iR}^{ub}
  \;\mbox{and}\;\;
  F_{iR}^{ub} \;=\; \sigma\maxo_{\vu\in\Deltapl}
    [\partial_i F(\vu)]
\eeqn\vspace{-1ex}
\beqn
  F_0+F_R^{lb} \;\leqsq\; \low F \;\leqsq\; F(\vu^2)
  \;\;\mbox{where}\;\; F_R^{lb}=\min_i F_{iR}^{lb}
  \;\;\mbox{and}\;\;
  F_{iR}^{lb} \;=\; \sigma\mino_{\vu\in\Deltapl}
    [\partial_i F(\vu)]
\eeqn
$F_0=F(\vu^0)$, and
$\u^1_i=\delta_{ii^1}$ with $i^1=\argmax_i F_{iR}^{ub}$, and
$\u^2_i=\delta_{ii^2}$ with $i^2=\argmin_i F_{iR}^{lb}$, and $\leqsq$
defined in (\ref{eqleqsq}) means $\leq$ {\em and} $=\;+O(\sigma^2)$,
where $\sigma=1-\u_\p^0$.
\end{theorem}
%
For conservative estimates, the lower bound on $\low F$ and the upper
bound on $\up F$ are the interesting ones.

\paragraph{Proof} We start by giving an $O(\sigma^2)$ bound on
$\up F_R=\maxo_{\vu\in\Delta'}F_R(\vu)$. We first insert
(\ref{dtbnd}) with $\vt^*=\vt^0\equiv\v 0$ into
(\ref{Fexpand}) and treat $\v{\check\u}$ and $\vt$ as separate
variables:
\beqn
  F_R(\v{\check\u},\vt) \;=\; \sigma\sum_i
  [\partial_i F(\v{\check\u})]\cdot t_i
  \;\leqsq\; \maxo_{\v{\check\u}\in\Deltapl}
  \bigg\{\sigma\sum_i[\partial_i F(\v{\check\u})]\cdot t_i\bigg\}
  \;\leqsq\;
  \sum_i F_{iR}^{ub}\cdot t_i
\eeqn
\beq\label{defFiRub} %\label{F1gen}
  \qmbox{with}
  F_{iR}^{ub} \;:=\; \sigma\maxo_{\v{\check\u}\in\Deltapl}
    [\partial_i F(\v{\check\u})]
\eeq
The first inequality is obvious, the second follows from the
convexity of $\max$. From assumption (\ref{Lipschitz}) we get
$\partial_i F(\vu)-\partial_i F(\vu') = O(\sigma)$ for all
$\vu,\vu'\in\Deltapl$, since $\Deltapl$ has
dia\-meter $O(\sigma)$. Due to one additional $\sigma$ in
(\ref{defFiRub}) the expressions in (\ref{defFiRub}) change only by %{F1gen}
$O(\sigma^2)$ when introducing or dropping
$\maxo_{\v{\check\u}}$ anywhere. This shows that the
inequalities are tight within $O(\sigma^2)$ and justifies
$\leqsq$. We now upper bound $F_R(\vu)$:
\beq\label{FRup}
  \up F_R = \maxo_{\vu\in\Delta'} F_R(\vu)
  \leqsq \maxo_{\vt\in\Delta}\maxo_{\v{\check\u}\in\Deltapl}
  F_R(\v{\check\u},\vt)
  \leqsq
  \maxo_{\vt\in\Delta}\sum_i F_{iR}^{ub}\cdot t_i
  =
  \max_i F_{iR}^{ub} =: F_R^{ub}
\eeq
A linear function on $\Delta$ is maximized by setting the $t_i$
component with largest coefficient to 1. This shows the last
equality. The maximization over $\v{\check\u}$ in (\ref{defFiRub}) can
often be performed analytically, leaving an easy $O(d)$ time task
for maximizing over $i$.

We have derived an upper bound $F_R^{ub}$ on $\up F_R$. Let us
define the corner $t_i=\delta_{ii^1}$ of $\Delta$ with
$i^1:=\arg\max_i F_{iR}^{ub}$. Since $\up F_R\geq F_R(\vu)$
for all $\vu$, $F_R(\vu^1)$ in particular is a lower bound
on $\up F_R$. A similar line of reasoning as above shows that that
$F_R(\vu^1)=\up F_R+O(\sigma^2)$. Using $\up{F+const.}=\up
F+const.$ we get $O(\sigma^2)$ lower and upper bounds on $\up F$,
i.e.\ $F(\vu^1)\leqsq\up F\leqsq F_0+F_R^{ub}$. $\low F$ is bound
similarly with all max's replaced by min's and inequalities
reversed.
%
Together this proves the Theorem \ref{thARI}. \qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Error Propagation}\label{secEP}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%-------------------------------%
\subsection{Approximation of $\up{\low F}$ (special cases)}
%-------------------------------%
For the special case $F(\vu)=\sum_i f(\vu)$ we have $\partial_i
F(\vu)=f'(\u_i)$. For concave $f$ like in case of the entropy we
get particularly simple bounds
\beqn
  F_{iR}^{ub} = \sigma\maxo_{\vu\in\Deltapl} f'(\u_i)
%  = \sigma\max_{\u_i\in[\u_i^0,\u_i^0+\sigma]} f'(\u_i)
  = \sigma f'(\u_i^0),\quad\;\;
  F_R^{ub}=\sigma\max_i f'(\u_i^0)
  = \sigma f'(\textstyle{\min_i n_i\over n+s}),\quad\;\;
\eeqn
\beqn
  F_{iR}^{lb} = \sigma\mino_{\vu\in\Deltapl} f'(\u_i)
%  = \sigma\min_{\u_i[\u_i^0,\u_i^0+\sigma]} f'(\u_i)
  = \sigma f'(\u_i^0+\sigma),\quad
  F_R^{lb}=\sigma\min_i f'(\u_i^0+\sigma)
  = \sigma f'(\textstyle{\max_i n_i+s\over n+s}),
\eeqn
where we have used $\maxo_{\vu\in\Deltapl} f'(\u_i)
=\max_{\u_i\in[\u_i^0,\u_i^0+\sigma]} f'(\u_i)=f'(\u_i^0)$, and similarly
for $\min$. Analogous results hold for convex functions. In case
the maximum cannot be found exactly one is allowed to further
increase $\Deltapl$ as long as its diameter remains $O(\sigma)$.
Often an increase to
$\Box':=\{\vu:\u_i^0\leq\u_i\leq\u_i^0+\sigma\} \supset
\Deltapl \supset \Delta'$ makes the problem easy. Note that if we
were to perform these kind of crude enlargements on
$\maxo_{\vu}F(\vu)$ directly we would loose the bounds by
$O(\sigma)$.

\paragraph{Example (continued)}
$\sigma={1\over 10}$,
$h'({3\over 10})= {13051\over 2520}-\odt\pin^2$,
$h'({7\over 10})= {91717\over 8400}-{7\over 6}\pin^2$,
$H_0=H(\vu^0)=h({3\over 10})+h({6\over 10})$,
$H_R^{ub}={1\over 10}h'({3\over 10})$,
$H_R^{lb}={1\over 10}h'({7\over 10})$ $\Rightarrow$
$[H_0+H_R^{lb}\, ,\, H_0+H_R^{ub}]=[0.5564...,0.6404...]$, hence
$H_0+H_R^{ub}-\up H=0.0148=O({1\over 10^2})$,
$\low H-H_0-H_R^{lb}=0.0074...=O({1\over 10^2})$.

%-------------------------------%
\subsection{Error propagation}
%-------------------------------%
Assume we found bounds for estimators $G(\vu)$ and
$H(\vu)$ and we want now to bound the sum
$F(\vu):=G(\vu)+H(\vu)$. In the direct approach $\up
F\leq \up G+\up H$ we may lose $O(\sigma)$. A simple example is
$G(\vu)=\u_i$ and $H(\vu)=-\u_i$ for which
$F(\vu)=0$, hence $0=\up F\leq \up G+\up
H=\u_i^0+\sigma-\u_i^0=\sigma$, i.e.\ $\up F\not\leqsq \up G+\up
H$.
%
We can exploit the techniques of the previous section to obtain
$O(\sigma^2)$ approximations.
\beqn
  F_{iR}^{ub} \;=\;
  \sigma\maxo_{\vu\in\Deltapl}\partial_i F(\vu)
  \;\leqsq\;
  \sigma\maxo_{\vu\in\Deltapl}\partial_i G(\vu) +
  \sigma\maxo_{\vu\in\Deltapl}\partial_i H(\vu)
  \;=\; G_{iR}^{ub} + H_{iR}^{ub}
\eeqn
\begin{theorem}[Error propagation: Sum]\label{thEps}
Let $G(\vu)$ and $H(\vu)$ be Lipschitz differentiable and
$F(\vu)=\alpha G(\vu)+\beta H(\vu)$, $\alpha,\beta\geq 0$,
then $\up F\leqsq F_0+F_R^{ub}$ and $\low F\geqsq
F_0+F_R^{lb}$, where $F_0=\alpha G_0+\beta H_0$, and
$F_{iR}^{ub}\leqsq \alpha G_{iR}^{ub}+\beta H_{iR}^{ub}$, and
$F_{iR}^{lb}\geqsq \alpha G_{iR}^{lb}+\beta H_{iR}^{lb}$.
\end{theorem}
%
It is important to notice that $F_R^{ub}\not\leqsq
G_R^{ub}+H_R^{ub}$ (use previous example),
i.e.\ $\max_i[G_{iR}^{ub}+H_{iR}^{ub}]\not\leqsq\max_i
G_{iR}^{ub}+\max_i H_{iR}^{ub}$. $\max_i$ can not be pulled in and
it is important to propagate $F_{iR}^{ub}$, rather than
$F_R^{ub}$.

Every function $F$ with bounded curvature can be written as a sum
of a concave function $G$ and a convex function $H$. For convex and concave
functions, determining bounds is particularly easy, as we have seen.
Often $F$ decomposes naturally into convex and concave parts as is
the case for the mutual information, addressed later.
Bounds can also be derived for products.
%
\begin{theorem}[Error propagation: Product]\label{thEpp}
Let $G,H:\Deltapl\to[0,\infty)$ be non-nega\-tive
Lipschitz differentiable
functions (\ref{Lipschitz}) with non-negative
derivatives $\partial_i G,\partial_i H\geq 0$ $\forall i$ and
$F(\vu)=G(\vu)\cdot H(\vu)$, then $\up F\leqsq
F_0+F_R^{ub}$, where $F_0= G_0\cdot H_0$, and $F_{iR}^{ub}\leqsq
G_{iR}^{ub}(H_0+H_R^{ub})+ (G_0+G_R^{ub})H_{iR}^{ub}$, and
similarly for $\low F$.
\end{theorem}

\paragraph{Proof} We have
\beqn
  F_{iR}^{ub}
  \;=\; \sigma\max\partial_i F
  \;=\; \sigma\max\partial_i (G\!\cdot\!H)
  \;=\; \sigma\max[(\partial_i G)H+G(\partial_i H)]
  \;\leqsq\;
\eeqn
\beqn
         \sigma(\max\partial_i G)(\max H) +
         \sigma(\max G)(\max \partial_i H)
  \leqsq G_{iR}^{ub}(H_0\!+\!H_R^{ub}) + (G_0\!+\!G_R^{ub})H_{iR}^{ub}
\eeqn
where all functions depend on $\vu$ and all $\max$ are over
$\vu\in\Deltapl$. There is one subtlety in the last
inequality: $\max G\neq \up G\leqsq G_0+G_R^{ub}$.
The reason for the $\neq$ being that the maximization is taken
over $\Deltapl$, not over $\Delta'$ as in the definition
of $\up G$. The
correct line of reasoning is as follows:
\beqn
  \maxo_{\vu\in\Deltapl} G_R(\vu)
  \leqsq
  \maxo_{\vt\in\Deltal}\sum_i G_{iR}^{ub}\cdot t_i
  =
  \max\{0,\max_i G_{iR}^{ub}\} = G_R^{ub}
  \;\Rightarrow\;
  \max G\leqsq G_0+G_R^{ub}
\eeqn
The first inequality can be proven in the same way as
(\ref{FRup}). In the first equality we set the $t_i=1$ with
maximal $G_{iR}^{ub}$ {\em if} it is positive. If all
$G_{iR}^{ub}$ are negative we set $\vt\equiv\v 0$. We assumed
$G\geq 0$ and $\partial_i G\geq 0$, which implies $G_R\geq 0$. So,
since $G_R\geq 0$ anyway, this subtlety is ineffective. Similarly
for $\max H_R$.\qed

It is possible to remove the rather strong non-negativity
assumptions. Propagation of errors for other combinations like
ratios $F=G/H$ may also be obtained.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Robust Intervals for Mutual Information}\label{secIEMI}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%-------------------------------%
\subsection{Mutual Information}
%-------------------------------%
We illustrate the application of the previous results on the
Mutual Information between two random variables
$\imath\in\{1,...,d_1\}$ and $\jmath\in \{1,...,d_2\}$. Consider
an i.i.d.\ random process with outcome
$(i,j)\in\{1,...,d_1\}\times\{1,...,d_2\}$ having joint
probability $\pi_{ij}$, where $\vpi\in\Deltapi :=\{\v x\in
I\!\!R^{d_1\times d_2}\,:\,x_{ij}\geq 0\,\forall ij,\; x_\pp=1\}$.
An important measure of the stochastic dependence of $\imath$ and
$\jmath$ is the mutual information
\beq\label{mi}
  {\cal I}(\vpi) = \sum_{i=1}^{d_1}\sum_{j=1}^{d_2}
  \pi_{ij}\log{\pi_{ij}\over\pi_{i\p}\pi_{\p j}} =
  \sum_{ij}\pi_{ij}\log\pi_{ij} -\!
  \sum_{i}\pi_{i\p}\log\pi_{i\p} -\!
  \sum_{j}\pi_{\p j}\log\pi_{\p j}
\eeq
\beqn
  \;=\; {\cal H}(\vpi_{\imath\p}) +
        {\cal H}(\vpi_{\p\jmath}) - {\cal
        H}(\vpi_{\imath\jmath})
\eeqn
$\pi_{i\p}=\sum_j\pi_{ij}$ and $\pi_{\p j}=\sum_i\pi_{ij}$ are row
and column marginal chances. Again, we assume a Dirichlet prior
over $\vpi_{\imath\jmath}$, which leads to a Dirichlet posterior
$p(\vpi_{\imath\jmath}|\v
n)\propto\prod_{ij}\pi_{ij}^{n_{ij}+st_{ij}-1}$ with $\vt\in
\Delta$. The expected value of $\pi_{ij}$ is
\beqn
  E_\vt[\pi_{ij}]={n_{ij}+st_{ij}\over n+s}=:\u_{ij}
\eeqn
The marginals $\vpi_{i\p}$ and $\vpi_{\p j}$ are also Dirichlet
with expectation $\u_{i\p}$ and $\u_{\p j}$.
%
The expected mutual information $I(\vu):=E_\vt[{\cal I}]$
can, hence, be expressed in terms of the expectations of
three entropies $H(\vu):=E_\vt[{\cal H}]$ (see (\ref{hex}))
\beqn
  I(\vu) = H(\vu_{\imath\p})+H(\vu_{\p\jmath})-H(\vu_{\imath\jmath})
 \;=\; H_{row}+H_{col}-H_{joint}
\eeqn
\beqn
 \;=\; \sum_i h(\u_{i\p})+\sum_j h(\u_{\p j})-\sum_{ij}h(\u_{ij})
\eeqn
where here and in the following we index quantities with $joint$,
$row$, and $col$ to denote to which distribution the quantity
refers.

%-------------------------------%
\subsection{Crude bounds for $I(\vu)$}
%-------------------------------%
Estimates for the robust IDM interval $[\mino_{\vt\in\Delta}E_\vt[{\cal I}] \,,\, \maxo_{\vt\in\Delta }E_\vt[{\cal I}]]$ can
be obtained by [minimizing,maximizing] $I(\vu)$. A crude upper
bound can be obtained as
\beqn
  \up I \;:=\; \maxo_{\vt\in\Delta} I(\vu) \;=\;
  \max[H_{row}+H_{col}-H_{joint}] \;\leq\;
\eeqn
\beqn
  \max H_{row} + \max H_{col} - \min H_{joint} \;=\;
  \up H_{row} + \up H_{col} -  \low H_{joint},
\eeqn
where exact solutions to $\up H_{row}$, $\low H_{row}$ and
$\low H_{joint}$ are available from Section \ref{secEEI}.
Similarly
$
  \low I \geq \low H_{row} + \low H_{col} -  \up H_{joint}
$. The problem with these bounds is that, although good in some
cases, they can become arbitrarily crude.
The following $O(\sigma^2)$ bound can be derived by exploiting the
error sum propagation Theorem \ref{thEps}.

\begin{theorem}[Bound on lower and upper Mutual Information]\label{thMIbnd}
The following bounds on the expected mutual information
$I(\vu)=E_\vt[{\cal I}]$ are valid:
\bqan
 & & \nq I(\vu^1) \leqsq \up I\leqsq I_0+I_R^{ub} \qmbox{and}
 I_0+I_R^{lb} \leqsq \low I \leqsq  I(\vu^2),
 \qmbox{where} \\
 & & \nq I_0=I(\vu^0)=H_{0row}+H_{0col}-H_{0joint} =
 h(\u_{i\p}^0)+h(\u_{\p j}^0)-h(\u_{ij}^0), \\
 & & \nq I_{ijR}^{ub}\leqsq
 H_{iRrow}^{ub}+H_{jRcol}^{ub}-H_{ijRjoint}^{lb} =
 h'(\u_{i\p}^0)+h'(\u_{\p j}^0)-h'(\u_{ij}^0\!+\!\sigma), \\
 & & \nq I_{ijR}^{lb}\geqsq
 H_{iRrow}^{lb}+H_{jRcol}^{lb}-H_{ijRjoint}^{ub} =
 h'(\u_{i\p}^0\!+\!\sigma)+h'(\u_{\p j}^0\!+\!\sigma)-h'(\u_{ij}^0),
\eqan
with $h$ defined in (\ref{hex}), and $t^0_{ij}=0$, and
$t^1_{ij}=\delta_{(ij)(ij)^1}$ with $(ij)^1=\argmax_{ij}
I_{ijR}^{ub}$, and $t^2_{ij}=\delta_{(ij)(ij)^2}$ with
$(ij)^2=\argmin_{ij} I_{ijR}^{lb}$.
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{IDM for Product Spaces}\label{secPS}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%-------------------------------%
%\subsection{IDM for product spaces}
%-------------------------------%
Product spaces $\Omega=\Omega_1\times...\times\Omega_m$ with
$\Omega_k=\{1,...d_k\}$ occur frequently in practical problems,
e.g.\ in the mutual information ($m=2$), in robust trees ($m=3$),
or in Bayesian nets in general ($m$ large). Without loss of
generality we only discuss the $m=2$ case in the following.
Ignoring the underlying structure in $\Omega$, a Dirichlet prior
in case of unknown chances $\pi_{\imath\jmath}$ and an IDM as used
in Section \ref{secIEMI} with
\beq\label{IDMfull}
\vt\in\Delta :=\{\vt\in I\!\!R^{d_1\times
d_2}\equiv I\!\!R^{d_1}\otimes I\!\!R^{d_2}\,:\,t_{ij}\geq
0\,\forall ij,\; t_\pp=1\}
\eeq
seems natural. On the other hand, if we take into account the
structure of $\Omega$ and go back to the original motivation of
IDM this choice is far less obvious. Recall that one of the major
motivations of IDM was its reparametrization invariance in the
sense that inferences are not affected when grouping or splitting
events in $\Omega$. For unstructured spaces like $\Omega_k$ this
is a reasonable principle. For illustration, let us consider
objects of various {\em shape} and {\em color}, i.e.\
$\Omega=\Omega_1\times\Omega_2$, $\Omega_1=\{ball, pen, die,
...\}$, $\Omega_2=\{yellow, red, green, ...\}$ in generalization
to Walleys bag of marbles example. Assume we want to detect a
potential dependency between {\em shape} and {\em color} by means
of their mutual information $I$. If we have no prior idea on the
possible kind of colors, a model which is independent of the
choice of $\Omega_2$ is welcome. Grouping red and green, for
instance, corresponds to $(x_{i1}$, $x_{i2}$, $x_{i3}$, $x_{i4},
...)$ $\leadsto$ $(x_{i1}$, $x_{i2}+x_{i3}$, $x_{i4}, ...)$ {\em
for all shapes $i$}, where $\v x\in\{\v n,\vpi,\vt,\vu\}$.
Similarly for the different shapes, for instance we could group
all round or all angular objects. The ``smallest IDM'' which
respects this invariance is the one which considers all
\beq\label{IDMprod}
  \vt\in\DeltaOX:=\Delta_{d_1}\otimes\Delta_{d_2}
  \;\propersubset\;\Delta.
\eeq
The tensor or outer product $\otimes$ is defined as $(\v
v\otimes\v w)_{ij}:=v_iw_j$ and $V\otimes W:=\{\v v\otimes\v w:\v
v\in V,\, \v w\in W\}$. It is a bilinear (not linear!) mapping.
This ``small tensor'' IDM is invariant under arbitrary grouping of
columns and rows of the chance matrix $(\vpi_{ij})_{1\leq i\leq
d_1,1\leq j\leq d_2}$. In contrast to the larger $\Delta$ IDM
model it is not invariant under arbitrary grouping of matrix
cells, but there is anyway little motivation for the necessity of
such a general invariance. General non-column/row cross groupings
would destroy the product structure of $\Omega$ and with that the
mere concepts of shape and color, and their correlation. For $m>2$
as in Bayes-nets cross groupings look even less natural. Whether
the $\DeltaOX$ or the larger simplex $\Delta$ is the more
appropriate IDM model depends on whether one regards the structure
$\Omega_1\times\Omega_2$ of $\Omega$ as a natural prior knowledge
or as an arbitrary a posteriori choice. The smaller IDM has the
potential advantage of leading to more precise
predictions (smaller robust sets).

Let us consider an estimator $F:\Delta\to\Set R$ and its
restriction $F_\ots:\DeltaOX\to\Set R$.
%
Robust intervals $[\low F,\up F]$ for $\Delta$ are generally wider
than robust intervals $[\low{F}_\ots,\up F_\ots]$ for $\DeltaOX$.
Fortunately not much. Although $\DeltaOX$ is a {\em
lower-dimensional} subspace of $\Delta$, it contains all vertices
of $\Delta$. This is possible since $\DeltaOX$ is a {\em
nonlinear} subspace. The set of ``vertices'' in both cases is
$\{\vt\,:\,t_{ij}=\delta_{ii_0}\delta_{jj_0},\;i_0\in\Omega_1,\;j_0\in\Omega_2\}$.
%
Hence, {\em if} the robust interval boundaries $\up{\low F}$ are
assumed in the vertices of $\Delta$ {\em then} the
interval for the $\DeltaOX$ IDM model is the
same ($\up{\low F}=\up{\low F}_\ots$). Since the condition is
``approximately'' true, the conclusion is
``approximately'' true. More precisely:

\begin{theorem}[IDM bounds for product spaces]
The $O(\sigma^2)$ bounds of Theorem \ref{thARI} on the robust
interval $\up{\low F}$ in the full IDM model $\Delta$
(\ref{IDMfull}), remain valid for $\up{\low
F}_\ots$ in the product IDM model
$\DeltaOX$
(\ref{IDMprod}).
\end{theorem}

\paragraph{Proof}\vspace{-3ex}
\beqn
  F(\vu^1) \leq \up F_\ots \leq \up F \leq
  F_0+F_R^{ub} = F(\vu^1)+O(\sigma^2),
\eeqn
where $\up F_\ots:=\maxo_{\vt\in\deltaOX}F(\vu)$ and $\vu^1$
was the ``$F_R$ maximizing'' vertex as defined in Theorem
\ref{thMIbnd} ($F(\vu^1)\leqsq\up F$). The first inequality
follows from the fact that all $\Delta$ vertices also belong to
$\DeltaOX$, i.e.\ $\vt^1\in\DeltaOX$. The second inequality
follows from $\DeltaOX\subset\Delta$. The remaining (in)equalities
follow from Theorem \ref{thARI}. This shows that $|\up F_\ots-\up
F|=O(\sigma^2)$, hence $F_0+F_R^{ub}$ is also an $O(\sigma^2)$
upper bound to $\up F_\ots$. This implies that to the
approximation accuracy we can achieve, the choice between $\Delta$
and $\DeltaOX$ is irrelevant. \qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Robust Credible Intervals}\label{secCI}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%-------------------------------%
\subsection{Bayesian credible sets/intervals}
%-------------------------------%
For a probability distribution $p:I\!\!R^d\to[0,1]$, an
$\alpha$-credible region is a measurable set $A$ for which
$p(A):=\int p(x)\chi_A(x) d^dx\geq\alpha$, where $\chi_A(x)=1$ if
$x\in A$ and $0$ otherwise, i.e.\ $x\in A$ with probability at
least $\alpha$. For given $\alpha$, there are many choices for
$A$. Often one is interested in ``small'' sets, where the size of
$A$ may be measured by its volume $\Vol(A):=\int\chi_A(x)d^dx$.
Let us define a/the smallest $\alpha$-credible set
\beqn
  A^{min}:=\argmin_{A:p(A)\geq\alpha}\Vol(A)
\eeqn
with ties broken arbitrarily. For unimodal $p$, $A^{min}$ can be
chosen as a connected set. For $d=1$ this means that
$A^{min}=[a,b]$ with $\int_a^b p(x)dx=\alpha$ is a minimal length
$\alpha$-credible interval. If, additionally $p$ is symmetric
around $E[x]$, then $A^{min}=[E[x]-a,E[x]+a]$ is also symmetric
around $E[x]$.

%-------------------------------%
\subsection{Robust credible sets}
%-------------------------------%
If we have a set of probability distributions $\{p_t(x)$, $t\in
T\}$, we can choose for each $t$ an $\alpha$-credible set $A_t$
with $p_t(A_t)\geq\alpha$, a minimal one being
$A_t^{min}:=\argmin_{A:p_t(A)\geq\alpha}\Vol(A)$. A robust
$\alpha$-credible set is a set $A$ which contains $x$ with
$p_t$-probability at least $\alpha$ for {\em all} $t$. A minimal
size robust $\alpha$-credible set is
\beq\label{eqRCI}
  A^{min}:=\argmin_{A={\textstyle\cup}_t A_t:p_t(A_t)\geq\alpha\forall t\in T}
  \Vol(A)
\eeq
It is not easy to deal with this expression, since $A^{min}$ is
{\em not} a function of $\{A_t^{min}:t\in T\}$, and especially does
not coincide with $\bigcup_t A_t^{min}$ as one might expect.

%-------------------------------%
\subsection{Robust credible intervals}
%-------------------------------%
This can most easily be seen for univariate symmetric
unimodal distributions, where $t$ is a translation, e.g.\
$p_t(x)=\mbox{Normal}(E_t[x]=t,\sigma=1)$ with 95\% credible
intervals $A_t^{min}=[t-2,t+2]$. For, e.g.\ $T=[-1,1]$ we get
$\bigcup_t A_t^{min}=[-3,3]$. The credible intervals {\em move}
with $t$. One can get a smaller union if we take the intervals
$A_t^{sym}=[-a_t,a_t]$ symmetric around 0. Since $A_t^{sym}$ is a
non-central interval w.r.t.\ $p_t$ for $t\neq 0$, we have $a_t>2$, i.e.\
$A_t^{sym}$ is larger than $A_t^{min}$, but one can show that the
increase of $a_t$ is smaller than the shift of $A_t^{min}$ by $t$,
hence we save something in the union. The optimal choice is
neither $A_t^{sym}$ nor $A_t^{min}$, but something in-between.
In the extended version \cite{Hutter:03idmx} this
is illustrated for the triangular distribution
$p_t(x)=\max\{0\,,\,1\!-\!|x\!-\!t|\}$ with $t\in T:=[-\gamma,\gamma]$,
where closed form solutions can be given.

An interesting open question is under which general conditions we
can expect $A^{min}\subseteq\bigcup_t A_t^{min}$. In any case,
$\bigcup_t A_t$ can be used as a conservative estimate for a
robust credible set, since $p_t(\bigcup_{t'} A_{t'})\geq
p_t(A_t) \geq \alpha$ for all $t$.

A special (but important) case which falls outside the above
framework are one-sided credible intervals, where only $A_t$ of
the form $[a,\infty)$ are considered. In this case
$A^{min}=\bigcup_t A_t^{min}$, i.e.\ $A^{min}=[a_{min},\infty)$
with $a_{min}=\max\{a:p_t([a,\infty])\geq\alpha\forall t\}$.

%-------------------------------%
\subsection{Approximations}
%-------------------------------%
For complex distributions like for the mutual information we have
to approximate (\ref{eqRCI}) somehow. We use the following notation
for shortest $\alpha$-credible {\em intervals} w.r.t.\
a univariate distribution $p_t(x)$:
\beqn
  {\mathop{\widetilde{x}}\limits_\sim}\!\,_t \;\equiv\;
  [ {\mathop{x}\limits_\sim}\!\,_t , \widetilde{x}_t] \;\equiv\;
  [ E_t[x]-\Delta{\mathop{x}\limits_\sim}\!\,_t \,,\,
  E_t[x]+\Delta\widetilde{x}_t ] \;:=\;
  \argmin_{[a,b]:p_t([a,b])\geq\alpha}(b-a),
\eeqn
where $\Delta\widetilde{x}_t:=\widetilde{x}_t-E_t[x]$
($\Delta{\mathop{x}\limits_\sim}\!\,_t :=
E_t[x]-{\mathop{x}\limits_\sim}\!\,_t$) is the distance from the
right boundary $\widetilde{x}_t$ (left boundary
${\mathop{x}\limits_\sim}\!\,_t$) of the shortest
$\alpha$-credible interval
${\mathop{\widetilde{x}}\limits_\sim}\!\,_t$ to the mean $E_t[x]$
of distribution $p_t$. We can use
$\mathop{\up{\widetilde{x}}}\limits_\simeq \equiv
[\mathop{x}\limits_\simeq , \up{\widetilde{x}}] :=\bigcup_t
{\mathop{\widetilde{x}}\limits_\sim}\!\,_t$ as a (conservative,
but not shortest) robust credible interval, since
$p_t(\mathop{\up{\widetilde{x}}}\limits_\simeq)\geq p_t
({\mathop{\widetilde{x}}\limits_\sim}\!\,_t)\geq\alpha$ for all
$t$. We can upper bound $\up{\widetilde{x}}$ (and similarly lower
bound $\mathop{x}\limits_\simeq$) by
\beq\label{eqCRCI}
  \up{\widetilde{x}} \;=\;
  \max_t(E_t[x]+\Delta\widetilde{x}_t) \;\leq\;
  \max_t E_t[x]+\max_t \Delta\widetilde{x}_t \;=\;
  \up{E[x]}+ \up{\Delta\widetilde{x}}.
\eeq
We have already intensively discussed how to compute upper and
lower quantities, particularly for the upper mean $\up{E[x]}$ for
$x\in\{{\cal F}, {\cal H}, {\cal I}, ... \}$, but the linearization
technique introduced in Section \ref{secAEI} is general enough to
deal with all in $t$ differentiable quantities, including
$\Delta\widetilde{x}_t$. For example for Gaussian $p_t$ with
variances $\sigma_t$ we have
$\Delta\widetilde{x}_t=\kappa\sigma_t$ with $\kappa$ given by
$\alpha=\mbox{erf}(\kappa/\sqrt{2})$, where erf is the error
function (e.g.\ $\kappa=2$ for $\alpha\approx 95\%)$. We only need to
estimate $\max_t\sigma_t$.

For non-Gaussian distributions, exact expression for
$\Delta\widetilde{x}_t$ are often hard or impossible to obtain and
to deal with. Non-Gaussian distributions depending on some sample
size $n$ are usually close to Gaussian for large $n$ due to the
central limit theorem.
%
One may simply use $\kappa\sigma_t$ in place of
$\Delta\widetilde{x}_t$ also in this case, keeping in mind that
this could be a non-conservative approximation. More
systematically, simple (and for large $n$ good) upper bounds on
$\Delta\widetilde{x}_t$ can often be obtained and should preferably be used.

Further, we have seen that the variation of sample depending
differentiable functions (like $E_t[x]=E_t[x|\v n]$) w.r.t.\ $t\in\Delta$
are of order ${s\over n+s}$. Since in such cases the standard
deviation $\sigma_t\sim n^{-1/2} \sim \Delta\widetilde{x}_t$ is
itself suppressed, the variation of $\Delta\widetilde{x}_t$ with
$t$ is of order $n^{-3/2}$. If we regard this as negligibly
small, we may simply fix some $t^*\in\Delta$:
\beqn
  \max_t\Delta\widetilde{x}_t = \kappa\sigma_{t^*}+O(n^{-3/2})
\eeqn
Since $\Delta\widetilde{x}_t$ is ``nearly'' constant, this also
shows that we lose at most $O(n^{-3/2})$ precision in the bound
(\ref{eqCRCI}) (equality holds for $\Delta\widetilde{x}_t$
independent of $t$).
Expressions for the variance of $\cal I$, for instance, have been
derived in \cite{Wolpert:95,Hutter:01xentropy}:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusions}\label{secConc}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Section 1 & 2
This is the first work, providing a systematic approach for
deriving closed form expressions for interval estimates in the
Imprecise Dirichlet Model (IDM).
% Section 3 & 4
We concentrated on exact and conservative {\em robust} interval
([lower,upper]) estimates for concave functions
$F=\sum_i f_i$ on simplices, like the entropy. The
conservative estimates widened the intervals by $O(n^{-2})$, where
$n$ is the sample size.
%
Here is a dilemma, of course: For large $n$ the approximations are
good, whereas for small $n$ the bounds are more interesting, so
the approximations will be most useful for intermediate $n$. More
precise expressions for small $n$ would be highly interesting.
% Section 5 and 6
We have also indicated how to
propagate robust estimates from simple functions to composite
functions, like the mutual information.
% Section 7
We argued that a reduced IDM on product spaces, like Bayesian
nets, is more natural and should be preferred in order to improve
predictions. Although improvement is formally only $O(n^{-2})$,
the difference may be significant in Bayes nets or for very small $n$.
%
Finally, the basics of how to combine robust with credible
intervals have been laid out. Under certain conditions
$O(n^{-3/2})$ approximations can be derived, but the presented
approximations are not conservative.
%
All in all this work has shown that IDM has not only interesting
theoretical properties, but that explicit
(exact/conservative/approximate) expressions for robust
(credible) intervals for various quantities can be derived. The
computational complexity of the derived bounds on $F=\sum_i f_i$
is very small, typically one or two evaluations of $F$ or related
functions, like its derivative.
%
First applications of these (or more precisely, very similar)
results, especially the mutual information, to robust
inference of trees look promising \cite{Hutter:03tree}.

%------------------------------%
\subsection{Acknowledgements}
%------------------------------%
I want to thank Peter Walley for introducing IDM to me and
Marco Zaffalon for encouraging me to investigate this topic.
This work was supported by SNF grant 2000-61847.00 to
J{\"u}rgen Schmidhuber.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%         Bibliography        %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\small
\begin{thebibliography}{GCSR95}\parskip=0ex

\bibitem[AS74]{Abramowitz:74}
M.~Abramowitz and I.~A. Stegun, editors.
\newblock {\em Handbook of mathematical functions}.
\newblock Dover publications, inc., 1974.

\bibitem[Ber01]{Bernard:01}
J.-M. Bernard.
\newblock Non-parametric inference about an unknown mean using the {I}mprecise
  {D}irichlet {M}odel.
\newblock In G.~{d}e Cooman, T.~Fine, and T.~Seidenfeld, editors, {\em
  Proceedings of the 2nd International Symposium on Imprecise Probabilities and
  Their Application ({ISIPTA-2001})}, pages 40--50, The Netherlands, 2001.
  Shaker Publishing.

\bibitem[GCSR95]{Gelman:95}
A.~Gelman, J.~B. Carlin, H.~S. Stern, and D.~B. Rubin.
\newblock {\em Bayesian Data Analysis.}
\newblock Chapman, 1995.

\bibitem[Hal48]{Haldane:48}
J.~B.~S. Haldane.
\newblock The precision of observed values of small frequencies.
\newblock {\em Biometrika}, 35:297--300, 1948.

\bibitem[Hut02]{Hutter:01xentropy}
M.~Hutter.
\newblock Distribution of mutual information.
\newblock In T.~G. Dietterich, S.~Becker, and Z.~Ghahramani, editors, {\em
  Advances in Neural Information Processing Systems 14}, pages 399--406,
  Cambridge, MA, 2002. MIT Press.

\bibitem[Hut03]{Hutter:03idmx}
M.~Hutter.
\newblock Robust estimators under the {I}mprecise {D}irichlet {M}odel (extended
  version).
\newblock Technical report, IDSIA, Manno(Lugano), Switzerland, 2003.
\newblock http://www.idsia.ch/$\sim$marcus/ai/idmx.ps.

\bibitem[Jef46]{Jeffreys:46}
H.~Jeffreys.
\newblock An invariant form for the prior probability in estimation problems.
\newblock In {\em Proc. Royal Soc. London (A)}, volume 186, pages 453--461,
  1946.

\bibitem[Per47]{Perks:47}
W.~Perks.
\newblock Some observations on inverse probability.
\newblock {\em J. Inst. Actuar.}, 73:285--312, 1947.

\bibitem[Wal96]{Walley:96}
P.~Walley.
\newblock Inferences from multinomial data: learning about a bag of marbles.
\newblock {\em Journal of the Royal Statistical Society B}, 58(1):3--57, 1996.

\bibitem[WW95]{Wolpert:95}
D.~H. Wolpert and D.~R. Wolf.
\newblock Estimating functions of distributions from a finite set of samples.
\newblock {\em Physical Review E}, 52(6):6841--6854, 1995.

\bibitem[Zaf01]{Zaffalon:01tree}
M.~Zaffalon.
\newblock Robust discovery of tree-dependency structures.
\newblock In G.~{d}e Cooman, T.~Fine, and T.~Seidenfeld, editors, {\em
  Proceedings of the 2nd International Symposium on Imprecise Probabilities and
  Their Application ({ISIPTA-2001})}, pages 394--403, The Netherlands, 2001.
  Shaker Publishing.

\bibitem[ZH03]{Hutter:03tree}
M.~Zaffalon and M.~Hutter.
\newblock Robust inference of trees.
\newblock Technical Report IDSIA-11-03, IDSIA, Manno(Lugano), CH, 2003.

\end{thebibliography}
}

\end{document}

%---------------------------------------------------------------
