Metrics for more than two points at once
David H. Wolpert$^1$
The conventional definition of a topological metric over a space specifies properties that must be obeyed by any measure of ``how separated" two points in that space are. Here it is shown how to extend that definition, and in particular the triangle inequality, to concern arbitrary numbers of points. Such a measure of how separated the points within a collection are can be bootstrapped, to measure ``how separated" from each other are two (or more) collections. The measure presented here also allows fractional membership of an element in a collection. This means it directly concerns measures of ``how spread out" a probability distribution over a space is. When such a measure is bootstrapped to compare two collections, it allows us to measure how separated two probability distributions are, or more generally, how separated a distribution of distributions is.
nlin0404032.tex
  % ****** Start of file apssamp.tex ******
   %
   %   This file is part of the APS files in the REVTeX 4 distribution.
   %   Version 4.0 of REVTeX, August 2001
   %
   %   Copyright (c) 2001 The American Physical Society.
   %
   %   See the REVTeX 4 README file for restrictions and more information.
   %
   % TeX'ing this file requires that you have AMS-LaTeX 2.0 installed
   % as well as the rest of the prerequisites for REVTeX 4.0
   %
   % See the REVTeX 4 README file
   % It also requires running BibTeX. The commands are as follows:
   %
   %  1)  latex apssamp.tex
   %  2)  bibtex apssamp
   %  3)  latex apssamp.tex
   %  4)  latex apssamp.tex
   %
   \documentclass[twocolumn,showpacs,preprintnumbers,amsmath,amssymb]{revtex4}


   \usepackage{psfig} 
   \usepackage{graphicx} % standard LaTeX graphics tool
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{tabularx}
\usepackage{subfigure}
\usepackage{psfrag}
\usepackage{url}


   \begin{document}



 \title{Metrics for more than two points at once}


   \author{David H. Wolpert$^1$}
   \affiliation{$^1$NASA Ames Research Center, Moffett Field, CA 94035,
    \tt \{dhw@email.arc.nasa.gov}

   \begin{abstract} 
The conventional definition of a topological metric over a
space specifies properties that must be obeyed by any measure of ``how
separated" two points in that space are. Here it is shown how to
extend that definition, and in particular the triangle inequality, to
concern arbitrary numbers of points. Such a measure of how
separated the points within a collection are can be bootstrapped, to
measure ``how separated" from each other are two (or more)
collections. The measure presented here also allows fractional
membership of an element in a collection. This means it directly
concerns measures of ``how spread out" a probability distribution over
a space is. When such a measure is bootstrapped to compare two
collections, it allows us to measure how separated two probability
distributions are, or more generally, how separated a distribution of
distributions is.
   \end{abstract}




\maketitle
                           









 \section{Introduction}

The conventional definition of a topological metric formalizes the
concept of distance. It specifies properties required of any function
that purports to measure ``how separated" two elements of a space
are. However often one wants to measure ``how separated" the members
of a collection of more than two elements is. The conventional way to
do this is to combine the pair-wise metric values for all pairs of
elements in the collection, into an aggregate measure. This is ad hoc
however.

As an alternative, here the formal definition of a topological metric
is extended to apply to collections of more than two elements.  In
particular, the triangle inequality is extended to concern such
collections.  The measure presented here applies even to collections
with duplicate elements. It also applies to collections with
``fractional" numbers of elements, i.e., to probability distributions.

This measure can be directly incorporated into many domains where ad
hoc combinations of pair-wise metrics are currently used. In addition,
when applied to different projections of a high-dimensional data set,
it provides a novel type of vector-valued characterization of that
data set.

This new measure can be bootstrapped in a natural way, to measure
``how separated" from each other two collections are. In other words,
given a measure $\rho$ of how separated from each other the elements
in an arbitrary collection $\xi$ are, one can define a measure of how
separated from each other two collections $\xi_1$ and $\xi_2$ are.
(Intuitively, the idea is to subtract the sum of the measure's values
for each of the two separate collections $\xi_1$ and $\xi_2$ from the
value of the measure for the union of the collections.) More
generally, one can measure how separated a collection of such
collections is. Indeed, with fractional memberships, such
bootstrapping allows us to measure how separated a distribution of
distributions is.

In the next section the definition of a multi-argument metric
({\bf{multimetric}}, for short) is presented. Also in that section is
an extensive set of examples and a list of some elementary
properties. For instance, it is shown that the standard deviation of a
probability distribution across $\mathbb{R}^N$ is a multimetric,
whereas the variance of that distribution is not.

The following section presents a way to bootstrap from a multimetric
for elements within a collection to a multimetric over collections.
Some examples and elementary properties of this bootstrapped measure
are also in that section.

A short concluding section considers some of the possible uses of
multimetrics. 






 \section{Multimetrics}

Collections of elements from a space $X$ are represented as vectors of
counts, i.e., functions from $x \in X \rightarrow \{0, 1, 2,
\ldots\}$.  So for example, if $X = \{A, B, C\}$, and we have the
collection of three $A$'s, no $B$'s, and one $C$, we represent that as
the vector $(3, 0, 1)$. It is natural to extend this to functions from
$x \in X$ to $\mathbb{R}$.  In particular, doing this will allow us to
represent probability distributions (or density functions, depending
on the cardinality of $X$) over $X$. Accordingly, our formalization of
multimetrics will provide a measure for how how spread out a
distribution over distributions is.\footnote{See
\cite{lin91,hall99,judg04,osva03,futo04,woma04a} and references
therein for work on how spread out a pair of distributions is.}  Given
$X$, the associated space of all functions from $X$ to $\mathbb{R}$ is
written as $\mathbb{R}^X$. The subspace of functions that are
nowhere-negative is written as $(\mathbb{R}^+)^X$.

As a notational comment, integrals are written with the measure
implicitly set by the associated space. In particular, for a finite
space, the point-mass measure is implied, and the integral symbol
indicates a sum. In addition $\delta_{x}$ is used to indicate the
appropriate type of delta function (Dirac, Kronecker, etc.) about $x$.
Other shorthand is ${\cal{R}}^X \equiv ({\mathbb{R}}^+)^X -
\{0\}$ and $||v||$ to mean $\int dx \;v(x)$.

In this representation of collections of elements from $X$, any
conventional metric taking two arguments in $X$ can be written as a
function $\rho$ over a subset of the vectors in ${\cal{R}}^X$. That
subset consists of all vectors that either have two of their
components equal to 1 and all others 0, or one component equal to 2
and all others 0. For example, for $X = \{A, B, C\}$, the metric
distance between $A$ and $B$ is $\rho(1,0,1)$, and from $A$ to itself
is $\rho(2,0,0)$.

Generalizing this, a multimetric for $T(X) \subseteq {\cal{R}}^X$ is
defined as a real-valued function $\rho$ over ${\cal{R}}^X$ such that
$\forall u, v, w \in {\cal{R}}^X$,

$ $

1) $u,v,w \in T(X) \;\;\Rightarrow\;\; \rho(u + v) \; \le \; \rho(u +
w) + \rho(v + w).$

$ $

2) $\rho(u) \ge 0, \; \rho(k \delta_{x}) = 0 \; \forall x, k > 0.$

$ $

3) $\rho(u) = 0  \;\;\Rightarrow \;\; u = k \delta_{x} \; {\mbox{for
    some}} \; k, x.$

$ $

In this representation of collections, if only one $x \in X$ is in a
collection (perhaps occurring more than once), then only one component
of $u$ is non-zero. Accordingly, conditions (2) and (3) are extensions
of the usual condition defining a metric that it be non-negative and
equal 0 iff its arguments are the same. Condition (1) is an extension
of the triangle inequality, to both allow repeats of elements from $X$
and/or more than two elements from $X$ to be in the collection. Note
though that condition (1) involves sums in its argument rather than
(as in a conventional norm-based metric for a Euclidean space)
differences. Intuitively, $T(X)$ is that subset of ${\cal{R}}^X$ over
which the generalized version of the triangle inequality
holds.\footnote{A natural extension of this analysis allows
${\cal{R}}^X$ to be any subset of ${\mathbb{R}}^X$ --- potentially
including vectors with negative components --- so long as $k \delta_x
\in {\cal{R}}^X \; \forall x \in X, k > 0$. Indeed, with care, one can
even take the range of $\rho$ to include complex numbers, so that
$\rho$ includes Hilbert vectors like those that arise in quantum
mechanics. In the interests of clarity, we do not pursue such
extensions here.}

Condition (1) implies that multimetrics obey a second triangle
inequality, just as conventional metrics do:

$ $

$\rho(u + v) \ge |\rho(u + w) - \rho(v + w)|$.

$ $

 \noindent (This follows by rewriting condition (1) as $\rho(u + w) \ge
\rho(u + v) - \rho(v + w)$, and then relabeling twice.) 

$ $

 \noindent {\bf{Example 1}}: Set $X = \mathbb{R}^N$. Take $T(X)$ to be those
elements of ${\cal{R}}^X$ whose norm equals 1, i.e., the probability
density functions over $\mathbb{R}^N$.  Then have $\rho(s)$ for any $s
\in {\cal{R}}^X$ (whether in $T(X)$ or not) be the standard
deviation of the distribution $\frac{s}{||s||}$, i.e., $\rho(s) =
\sqrt{\frac{1}{2}\int dx dx' \; \frac{s(x) s(x')}{||s||^2} (x -
x')^2}$.

Conditions (2) and (3) are immediate. To understand condition (1),
first, as an example, say that all three of $u, v$ and $w$ are
separate single delta functions over $X$. Then condition (1) reduces
to the conventional triangle inequality over $\mathbb{R}^N$, here
relating the points (in the supports of) $u, v$ and $w$. This example
also demonstrates that the variance (i.e., the square of our $\rho$)
is not a multimetric.

For a vector $s$ that involves multiple delta functions, $\rho(s)$
measures the square root of the sum of the squares of the Euclidean
distances between the points (in the support of) $s$. In this sense it
tells us how ``spread out'' those points are. Condition (1) even holds
for vectors that are not sums of delta functions however (see appendix). 

$ $

 \noindent {\bf{Example 2}}: As a variant of Ex. 1, have $X$ be the
unit simplex in $\mathbb{R}^N$, and use the same $\rho$ as in
Ex. 1. In this case any element of $X$ is a probability distribution
over a variable with $N$ possible values. So any element of $T(X)$ is
a probability density function over such probability distributions. In
particular, say $s$ is a sum of some delta functions for such an
$X$. Then $\rho(s)$ measures how spread out the probability
distributions in (the support of) $s$ are. If those probability
distributions are themselves sums of delta functions, they just
constitute subsets of our $N$ values, and $\rho(s)$ measures how
spread out from one another those subsets are.

$ $

 \noindent {\bf{Example 3}}: As another variant of Ex. 1, for any
$X$, take $T(X) = {\cal{R}}^X$. Define the tensor contraction $\langle
s \mid t \rangle \equiv \int dx dx' s(x) t(x) F(x, x')$ where $F$ is
symmetric and nowhere-negative, and where $F(x, x') = 0
\Leftrightarrow x = x'$. Then $\rho(s) \equiv \sqrt{{\langle}s \mid
s{\rangle}}$ obeys conditions (2) and (3) by inspection.  It also
obeys condition (1) (see appendix).

Note that the ${\langle} ., . \rangle$ operator is not an inner
product over ${\mathbb{R}}^X$, the extension of $T(X)$ to a full vector
space. When components of $s$ can be negative, $\langle s, s \rangle$
may be as well.  Note also that there is a natural differential
geometric interpretation of this $\rho$ when $X$ consists of $N$
values. Say we have a curve on an $N$-dimensional manifold with metric
tensor $F$ at a particular point on the curve, and that at that point
the tangent vector to the curve is $s$. Then $\rho(s)$ is the
derivative of arc length along that curve, evaluated at that point.

This suggest an extension of this multimetric, in which rather than a
tensor contraction between two vectors, we form the tensor contraction
of $n$ vectors: ${\langle}s^1, \ldots , s^n{\rangle} \equiv \int dx^1
\ldots dx^n s^1(x^1) \ldots s^n(x^n) F(x^1, \ldots, x^n)$, where $F$
is invariant under permutation of its arguments, nowhere-negative, and
equals 0 if and only if all its arguments have the same value. Any
$\rho(s)$ that is a monotonically increasing function of ${\langle}s,
s, \ldots, s{\rangle}^{1/n}$ automatically obeys conditions (2) and
(3).

$ $

It is worth collecting a few elementary results concerning
multimetrics:

$ $

 \noindent {\bf{Lemma 1}}:

 \begin{enumerate}

 \item Let $\{\rho_i\}$ be a set of functions that obey conditions (2)
and (3), and $\{a_i\}$ a set of non-negative real numbers at least one
of which is non-zero. Then $\sum_i a_i \rho_i$ also obeys conditions
(2) and (3).

 \item Let $\{\rho_i\}$ be a set of functions that obey condition (1),
and $\{a_i\}$ a set of non-negative real numbers at least one of which
is non-zero. Then $\sum_i a_i \rho_i$ also obeys conditions (1).

 \item Let $f : {\mathbb{R}} \rightarrow {\mathbb{R}}^+$ be a
monotonically increasing concave function that equals 0 when its
argument does.  Then if $\rho$ is a multimetric for some $T(X)$,
$f(\rho)$ is also a multimetric for $T(X)$ (see appendix).

 \item Let $f : X \rightarrow Y$ be invertible, and let $\rho_Y$ be a
multimetric over $Y$. Define the operator $B_f : {\cal{R}}^X
\rightarrow {\cal{R}}^Y$ by $[B_f(s)](y) \equiv s(f^{-1}(y))$ if
$f^{-1}(y)$ exists, 0 otherwise. $B_f$ is a linear operator. This
means $\rho_X(s) \equiv \rho_Y(A_f(s))$ is a
multimetric.\footnote{Such mappings are analogous to the mapping from
a ``data space" to a ``feature space" underlying kernel machines
~\cite{chsh00}.}

 \end{enumerate}

$ $

 \noindent {\bf{Example 4}}: Take $X = \mathbb{R}^N$ again, and let
$T(X)$ be all of ${\cal{R}}^X$ with bounded support.  Then by Lemma 1,
the width along $x_1$ of (the support of) $s \in T(X)$ is a
multimetric function of $s$ (see appendix).

This means that the average of the width in $x_1$ over all possible
rotations of $X$ is also a multimetric. Similarly, consider the
smallest axis-parallel box enclosing the (support of the) Euclidean
points in $s$.  Then the sum of the lengths of the edges of that box
is a multimetric function of $s$.  

On the other hand, while the volume of that box obeys conditions (2)
and (3), in general it can violate condition (1). Similarly, the
volume of the convex hull of the (support of) the points in $s$ obeys
conditions (2) and (3) but can violate (1). (In general, multimetrics
have the dimension of a length, so volumes have to be raised to the
appropriate power to make them be multimetrics.)

It is worth comparing the sum-of-edge-lengths multimetric to the
standard deviation multimetric of Ex. 1 for the case where all
arguments $s$ are finite sums of delta functions (i.e., ``consist of a
finite number of points''). For such an $s$ we can write the
sum-of-edge-lengths multimetric as a sum over all $N$ dimensions $i$
of ${\mbox{max}}_j \; s^j_i - {\mbox{min}}_j \; s^j_i$, where $s^j$ is
the $j$'th point in $s$. In contrast, the (square of the) standard
deviation multimetric is also a sum over all $i$, but of the (square
of the) standard deviation of the $i$'th components of the points in
$s$. Another difference is that the standard deviation multimetric is
a continuous function of its argument, unlike the sum-of-edge-lengths
multimetric.

$ $

 \noindent {\bf{Example 5}}: Let $X$ be countable and have $T(X) =
{\cal{R}}^X$. Then $\rho(s) = \int dx \Theta(s(x)) - 1$ where $\Theta$
is the Heaviside function is a multimetric (see appendix). This is the
volume of the support of $s$, minus 1.

$ $

 \noindent {\bf{Example 6}}: Let $X$ be countable and have $T(X) =
{\cal{R}}^X$. Then $\rho(s) = ||s|| - {\mbox{max}}_x s(x)$ obeys
conditions (2) and (3), by inspection. Canceling terms, for this
$\rho$ condition (1) holds iff ${\mbox{max}}_x (u(x) + v(x)) \ge
{\mbox{max}}_x (u(x) + w(x)) + {\mbox{max}}_x (v(x) + w(x)) -
2||w||$. This is not true in general, for example when $||w|| = 0$ and
the supports of $u$ and $v$ are disjoint. However if we take $T(X)$ to
be the unit simplex in ${\cal{R}}^X$, then condition (1) is obeyed,
and $\rho$ is a multimetric (see appendix).

$ $

 \noindent {\bf{Example 7}}: Let $X$ have a finite number of elements and
set $T(X) = {\cal{R}}^X$. Say that $\rho(s) = 0$ along all of the
axes, and that everywhere else, $k \le \rho(s) \le 2k$ for some fixed
$k > 0$. Then $\rho$ is a multimetric.





 \subsection{Vector-valued multimetrics}

It is straightforward to extend the definition of a multimetric to
have range ${\mathbb{R}}^M$ rather than $\mathbb{R}$, so long as one
has a linear ordering over ${\mathbb{R}}^M$ to specify the appropriate
extension of condition (1). For example, consider the component-wise
ordering: $\forall a, b, \vec{a} \le \vec{b} \Leftrightarrow a_i \le
b_i \; \forall i \in \{1, 2, \ldots M\}$. Say we have a set of $M$
scalar multimetrics. Then the $M$-fold Cartesian product of those
multimetrics is an $M$-dimensional multimetric, when component-wise
ordering defines the inequality in condition (1).

More generally, say we have chosen such a linear ordering over
${\mathbb{R}}^M$, and have an $M$-dimensional function with domain
${\cal{R}}^X$. Say this function obeys conditions (1) and (2) of an
$M$-dimensional multimetric for our linear ordering.  Then this
function can be used as a low-dimensional characterization of an
element of ${\cal{R}}^X$. In general, such characterizations may have
$M$ is less than $|{\mathbb{R}}^X|$, the dimension of the space in
which ${\cal{R}}^X$ is embedded, and may violate condition (1).  The
following examples illustrates this:

$ $

{ \noindent {\bf{Example 8}}: Consider again Ex. 1. To define our
vector-valued multimetric for the  $X$ of Ex. 1, say we have a scalar
multimetric $\rho_{\mathbb{R}}$ for the subspace, $X' = T(X') =
{\mathbb{R}}$. Let $\{v^1, v^2, \ldots v^M\}$ be a set of $M$
unit norm vectors living in $X$. Then we can define our
$M$-dimensional multimetric by
 \begin{eqnarray*} 
\rho_i(u) &\equiv& \rho_{\mathbb{R}}[f_{u, v^i}(t)] ; \\
f_{u, v^i}(t) &\equiv& \int dx \; u(x) \delta(v^i \cdot x - t).
 \end{eqnarray*}

To illustrate this, take $M= N$ and have the $\{v^i\}$ be the unit
normals along the $N$ axes of $X$. Let $u$ be a sum of delta
functions; $u = \delta_{x^1} + \delta_{x^2}$. Let $\rho_{\mathbb{R}}$
be the standard deviation multimetric of Ex. 1 for one-dimensional
probability density functions. So each component $\rho_i(u)$ is just
the $i$'th component of the difference $x^1 - x^2$.  Accordingly, $u$
can be reconstructed from the vector $\rho_i(u)$.

In this illustration conditions (1) and (2) are immediate.  If $M =
N$, then condition (3) also holds for $u$'s like the one considered
here that are sums of two delta functions, but not more generally.
Now modify this illustration by having $M < N$ and the $\{v^i\}$ not
all point along the axes of $X$. Then for general $u$, the components
$\rho_i(u)$ are the projections of $u$ along the different vectors
$\{v^i\}$. As in techniques like Principal Components
Analysis~\cite{duha00}, those projections provide a low-dimensional
characterization of $u$.








 \section{Concavity gaps and dispersions}

In Ex. 1, $\rho$ can be used to tell us how spread out a distribution
over $\mathbb{R}^N$ is. One would like to be able to use that $\rho$
to construct a measure of how spread out a collection of multiple
distributions over $\mathbb{R}^N$ is. Intuitively, we want a way to
construct a metric for a space of sets (generalized to be able to work
sets with duplicates, fractional memberships, etc.) from a metric for
the members within a single set. This would allow us to directly
incorporate the distance relation governing $X$ into the distance
relation for ${\cal{R}}^X$.

To do this, first let $\{Y, S(Y)\}$ be any pair of a subset of a
vector space together with a subset of $\mathbb{R}^Y$ such that
$\forall g \in S(Y), \frac{\int dy g(y) y}{||g||} \in Y$. (As an
example, we could take $Y$ to be any convex subspace of a vector
space, with $S(Y)$ any subset of ${\cal{R}}^Y$.) Then the associated
{\bf{concavity gap}} operator ${\cal{C}} : S(Y) \rightarrow
{\mathbb{R}}^{S(Y)}$ is defined by
 \begin{eqnarray*}
({\cal{C}}\sigma)(g) = \sigma(\frac{\int dy \; g(y) y}{||g||}) -
\frac{\int dy \; g(y) \sigma(y)}{||g||}
 \end{eqnarray*}
 \noindent where $y \in Y$, and both $\sigma$ and $g$ are arbitrary
elements in $S(Y)$.  So the concavity gap operator takes any single
member of the space $S(Y)$ (namely $\sigma$) and uses it to generate a
function (namely, ${\cal{C}}\sigma$) over all of
$S(Y)$.\footnote{Equivalently, it can be viewed as a non-symmetric
function from $S(Y) \times S(Y) \rightarrow
\mathbb{R}$, although we will not exploit that perspective here.}

In particular, say $Y = T(X)$ for some space $X$. Say we are given a
multimetric $\sigma$ measuring the ($X$-space) spread specified by any
element of $Y$. Say we are also given a $g$ which is a normalized
distribution over $Y$. Then ${\cal{C}}\sigma(g)$ is a measure of how
spread out the distribution $g$ is. Note that in this example space
$S(Y)$ is both the space of multimetrics over $Y$ and the space of
distributions for $Y$, exemplified by $\sigma$ and $g$, respectively.

We can rewrite the definition of the concavity gap in several ways:
 \begin{eqnarray*}
{\cal{C}}\sigma(g) &=& \sigma(E_g(y)) - E_g(\sigma) \\
&=& \sigma(\frac{{\bf{y}} \cdot g}{||g||}) - \frac{\sigma \cdot
g}{||g||}
 \end{eqnarray*}
 \noindent where $E_g$ means expected value evaluated according to the
probability distribution $\frac{g}{||g||}$, and in the last expression
{\bf{y}} is the (infinite-dimensional) matrix whose $y$'th column is
just the vector $y$, and the inner products are over the vector space
$S(Y)$. Taken together, these equations say that the concavity gap of
$\sigma$, applied to the distribution $g$, is given by evaluating the
function $\sigma$ at the center of mass of the distribution $g$,
and then subtracting the inner product between $\sigma$ and $g$.

$ $

 \noindent {\bf{Example 9}}: Let $Y = {\mathbb{R}}^N$, and choose
$S(Y)$ to be the set of nowhere-negative functions of $Y$ with
non-zero magnitude. Choose $\sigma(y) = 1 - \sum_{i=1}^N y_i^2$. Then
${\cal{C}}\sigma(g) = Var(\frac{g}{||g||})$.

$ $

 \noindent {\bf{Example 10}}: Say $X$ has $N$ values, with $T(X) =
{\cal{R}}^X$. Consider a $u \in T(X)$ whose components are all either
0 or some particular constant $a$ such that $\int dx \; u(x) = 1$. So
$u$ is a point on the unit hypercube in $T(X)$, projected down to the
unit simplex.  Let $\cal{T}$ be the set of all such points $u$. In the
usual way, the support of each element of $\cal{T}$ specifies a set of
elements of $X$.

Let $Y = T(X)$, and have $S(Y) = {\cal{R}}^Y$. Have $g$ be a uniform
average of a countable set of delta functions, each of which is
centered on a member of $\cal{T}$. So each of the delta functions
making up $g$ specifies a set of elements of $X$; $g$ is a
specification of a collection of such $X$-sets.

In this scenario $\sigma(E_g(y))$ is $\sigma$ applied to the union
(over $X$) of all the $X$-sets specified in $g$. In contrast,
$E_g(\sigma)$ is the average value you get when you apply $\sigma$ to
one of the $X$-sets specified in $g$. ${\cal{C}}\sigma(g)$ is the
difference between these two values. Intuitively, it reflects how much
overlap there is among the $X$-sets specified in $g$.

$ $

 \noindent {\bf{Example 11}}: Say $X$ has $N$ values, with $T(X) =
{\cal{R}}^X$.  Have $Y = T(X)$, and $S(Y)= {\cal{R}}^Y$, i.e., the set
of all nowhere-negative non-zero functions over those points in
${\mathbb{R}}^N$ with no negative components.  Choose $\sigma(y) =
H({y}) \; \forall y \in Y$, where $H(.) = -\int dy \; y(x)
{\mbox{ln}}[y(x)]$, the Shannon entropy function extended to
non-normalized $y$. This $\sigma$ is a natural choice to measure how
``spread out'' any point in $Y$ with magnitude 1 is. 

Have $g$ be a sum of a set of delta functions, about the distributions
over $\mathbb{B}$, $\{v^1, v^2, \ldots\}$. Then ${\cal{C}}\sigma(g)$
is a measure of how ``spread out'' those distributions are. In the
special case where $g = \delta_{v^1} + \delta_{v^2}$,
${\cal{C}}\sigma(g)$ is the Jensen-Shannon divergence between $v^1$
and $v^2$ \cite{tops02,lin91}. More generally, if $g$ is a probability density
function across the space of all distributions over $\mathbb{B}$,
${\cal{C}}\sigma(g)$ is a measure of how ``spread out'' that density
function is. 

$ $

There are several elementary properties of concavity gaps worth
mentioning: 

$ $

 \noindent {\bf{Lemma 2}}: 

 \begin{enumerate}
 \item $\cal{C}$ is linear.

 \item $\cal{C}\sigma$ is linear $\Leftrightarrow$ it equals 0
everywhere $\Leftrightarrow$ $\sigma$ is linear.

 \item $\cal{C}\sigma$ is continuous $\Leftrightarrow$ $\sigma$ is
continuous.

 \item ${\cal{C}}\sigma(g) = 0$ if $g \propto \delta_{y'}$ for some $y'
\in Y$.

 \item Giving $\cal{C}\sigma$ and the values of $\sigma$ at $1 + |Y|$
  distinct points in $Y$ fixes the value of $\sigma$ across all $Y$.
  ($|Y|$ is the dimension of $Y$.)

 \item The equivalence class of all $\sigma'$ having a particular 
concavity gap $\cal{C}\sigma$ is the set of functions of $y \in Y$
having the form $\{\sigma(y) + b \cdot y + a \;:\; a \in {\mathbb{R}},
b \in Y, \sigma(y) + b \cdot y + a \in S(Y)\}$.

 \end{enumerate}

$ $

{\bf{Proof}}: (1.1) and (1.4) are immediate. The first iff in (1.2)
follows from the fact that ${\cal{C}}\sigma(g) =
{\cal{C}}\sigma(\alpha g) \; \forall \alpha \in \mathbb{R}$. To see
the forward direction of the second iff, take $g = \delta_{y}/2$ and
$h = \delta_{y'}/2$ and expand ${\cal{C}}\sigma(g + h) = \sigma(y +
y') - [\sigma(y) + \sigma(y')]$. To see the forward direction of
(1.3), choose $g$ to have its center of mass infinitesimally to one
side of the discontinuity in $\sigma$, and then move it
infinitesimally to the other side to get a discontinuity in the
associated values of $({\cal{C}}(\sigma))(g)$.

 \noindent To prove (1.5), consider the case where $Y$ is
one-dimensional for simplicity. Say I give you $\sigma$ at $A$ and at
$B > A$, and also give you ${\cal{C}}\sigma$. Then for every $C > B$,
choose $g = \frac{B-C}{A-C} \delta_A + \frac{A-B}{A-C}
\delta_C$. Evaluating the associated value ${\cal{C}}\sigma(g) =
\sigma(B) - \frac{B-C}{A-C}\sigma(A) - \frac{A-B}{A-C}\sigma(C)$
allows us to solve for $\sigma(C)$. Similar reasoning holds for $C <
A$ and $C \in (A, B)$. For higher dimensions we need the value of
$\sigma$ at one extra point for each extra dimension of $Y$. This
completes the proof.

 \noindent To prove (1.6), first note that all members of that set do
indeed have the same concavity gap, $\cal{C}\sigma$.  To complete the
proof we must show that there are no other $\sigma$ with that
concavity gap. Let $\sigma'$ be any element of $S(Y)$ with the same
concavity gap as $\sigma$. By (1.5), if we know the value of $\sigma'$
at a total of $1 + |Y|$ points in $Y$, then we know $\sigma'$ {\it{in
toto}}. In turn, for any such set of $1 + |Y|$ values, we can always
find an $a$ and $b$ such that $a + b \cdot y + \sigma(y)$ lies in
$S(Y)$ and has those values. This means that $\sigma'$ is identical to
that $a + b \cdot y + \sigma(y)$. {\bf{QED.}}

$ $

 \noindent By (1.4), $\cal{C}\sigma$ necessarily obeys the second part
of condition (2) if $S(Y) = {\cal{R}}^Y$.

Next define a (strict) {\bf{dispersion}} over a space $X$ as a
(strictly) concave real-valued function over ${\cal{R}}^X$ that obeys
conditions (2) and (3) of a multimetric $\forall u, v, w \in
{\cal{R}}^X$.

$ $

 \noindent {\bf{Example 12}}: Take $X = \{1, 2\}$, with $T(X) =
{\cal{R}}^X = {\mathbb{R}}^2 - \{0\}$. Define $\sigma(u \in
{\mathbb{R}}^2)$ to equal 0 if $u_1 = 0$ or $u_2 = 0$, and equal
${\mbox{ln}}(1 + u_1) + {\mbox{ln}}(1 + u_2)$ otherwise. Then $\sigma$
is a (not everywhere continuous) strict dispersion.

$ $ 

 \noindent {\bf{Example 13}}: The $X, {\cal{R}}^X$, and $\rho$ of Ex. 3 
form a strict dispersion (see appendix).

$ $

 \noindent {\bf{Example 14}}: The $X, {\cal{R}}^X$, and $\sigma$ of
Ex. 5 form a dispersion.

$ $

 \noindent {\bf{Example 15}}: The $X, {\cal{R}}^X$, and $\sigma$ of
Ex. 11 form a strict dispersion.

$ $

There are several relations between concavity gaps and dispersions:

$ $

 \noindent {\bf{Lemma 3}}: Let $T(X) = {\cal{R}}^X$.

 \begin{enumerate}
 \item $\sigma$ is a dispersion over $T(X)$ $\Rightarrow$
$\sigma$ is nowhere-decreasing over $T(X)$.

 \item $\sigma$ is a dispersion over $T(X)$ and
$\sigma(s)$ is independent of $||s|| \; \forall \; s \ne 0 \in T(X)$
$\Rightarrow$ $\sigma$ is constant over the interior of $T(X)$.

 \item $\sigma$ is (strictly) concave over $V(X)$ $\Leftrightarrow$ 
$\cal{C}\sigma$ obeys condition (2) in full (and condition (3)) over $T(X)$.

 \item Say that $\sigma$ is continuous over $T(X)$. Then
$\cal{C}\sigma$ is separately (strictly) concave over each simplex in $T(X)$
$\Leftrightarrow$ $\sigma$ is (strictly) concave over $T(X)$.

 \end{enumerate}

$ $

 \noindent {\bf{Proof}}: (3.1) arises from the fact that a dispersion
is both concave and nowhere negative. To establish (3.2), first
consider any two vectors $u, v$ in the interior of $T(X)$ that differ
in only one component, $i$. Since no component of $u$ equals 0, there
must be an $s \in T(X)$ such that $\frac{u}{||u||} = \frac{v +
s}{||v+s||}$. (If $u_i > v_i, s = (u_i - v_i) \delta_i$. Otherwise
$s_i = 0$, and $s_j = u_j[\frac{v_i}{u_i} - 1] \; \forall j \ne i$.)
component is $i$, which is set so that $\frac{v_i + s_i}{v_j + s_j} =
\frac{u_i}{u_j}$ for every $j \ne i$.) By (3.1), this means that if
$\sigma$ is independent of the magnitude of its argument, $\sigma(v)
\le \sigma(u)$. Since the reverse argument must also hold, we have
$\sigma(u) = \sigma(v)$. Now repeat this reasoning to equate
$\sigma(v)$ with $\sigma(w)$ for some $w$ that differs from $v$ in
only one component, but differs from $u$ in two components. Continuing
in this way, we equate $\sigma(u)$ with $\sigma(z)$ for any $z$ that
differs in an arbitrary number of components from $u$.

 \noindent (3.3) is immediate from the definition of concavity and
Jensen's inequality.  To derive (3.4), first expand
${\cal{C}\sigma}(\frac{a+b}{2}) - \frac{{\cal{C}}\sigma(a) +
{\cal{C}}\sigma(b)}{2} \; = \; \sigma(\frac{E_a(y) + E_b(y)}{2}) -
\frac{\sigma(E_a(y)) + \sigma(E_b(y))}{2}$ when $||a|| = ||b||$.
($y$ being a generic argument of $T(X)$.) Next invoke (1.3) and
Jensen's inequality. {\bf{QED.}}

$ $

Let $f: {\mathbb{R}} \rightarrow {\mathbb{R}}$ be monotonically
increasing and strictly concave. Then by Lemma 3.3, if $\sigma$ is
strictly concave, $f({\cal{C}}\sigma)$ obeys conditions (2) and
(3). For example, this is the case for $\sqrt{{\cal{C}}\sigma}$. In
other words, so long as $\sigma$ is a strict dispersion,
$\sqrt{{\cal{C}}\sigma}$ obeys those conditions.

On the other hand, Lemma 3.2 means that any nontrivial $\sigma$ that
normalizes its argument (so that it is a probability distribution) and
then evaluates a function of that normalized argument cannot be a
dispersion.  So for example, if a concavity gap is a dispersion, it
must be constant.

Fortunately it is not the case that if $f({\cal{C}}\sigma)$ is a
multimetric it must be constant. In particular, often for a strictly
concave $\sigma$, $\sqrt{{\cal{C}}\sigma}$ for space $\{Y, S(Y)\}$ is a
multimetric for an appropriate $T(Y) \subseteq S(Y)$. 

$ $

 \noindent {\bf{Example 16}}: Choose $\{\sigma, Y, S(Y)\}$ as in
Ex. 11, and take $T(Y)$ to be all elements of $S(Y)$ which are sums of
two delta functions. This $\sigma$ is strictly concave, so we know
conditions (2) and (3) are obeyed by $\sqrt{{\cal{C}}\sigma}$.
Furthermore, for this choice of $T(Y)$, obeying condition (1) reduces
to obeying the conventional triangle inequality of two-argument
metrics, and it is known that the square root of the Jensen Shannon
divergence obeys that inequality ~\cite{tops02,futo04}. Therefore all
three conditions are met.

$ $

 \noindent {\bf{Example 17}}: Choose $\{\sigma, Y, S(Y)\}$ as in
Ex. 9. As in Ex. 16, this $\sigma$ is strictly concave, and therefore
$\sqrt{{\cal{C}}\sigma}$ automatically obeys conditions (2) and
(3). Now take $T(Y) = S(Y)$. Write ${\cal{C}}\sigma(g)$ as $\langle g,
g \rangle$ for the tensor contraction of Ex. 3, where $F(y, y') =
\frac{(y - y') \cdot (y - y')}{2}$. So by that example, we know that
$\sqrt{{\cal{C}}\sigma}$ is a multimetric.





 \section{Potential uses of multimetrics}

In addition to their intrinsic mathematical interest, multimetrics
have numerous potential applications. One of them is to allow more
nuanced complexity measures for physical systems, as described in
~\cite{woma04a}. Following is a list of some other from machine
learning~\cite{duha00}:

 \begin{enumerate}

 \item Mixture of Gaussians density estimation: In density estimation
one is given a data set of vectors $\{x^i\}$ that were generated by
IID sampling an unknown distribution over $X$ and wants to infer that
distribution. Say we have a probability distribution across $X$ given
by a linear combination of $n$ Gaussian distributions over $X$,
centered at the $n$ points $\mu^i$. Such a distribution induces a
probability of the set $\{x^i\}$. Accordingly, one way to estimate the
distribution that generated $\{x^i\}$ is to search for the linear
combination of $n$ Gaussians that maximizes the associated probability
of $\{x^i\}$.

One shortcoming of this procedure is that even though there are a
total of $n$ points used to parameterize the distribution, that
distribution is based solely on metric values for pairs of points
(namely the distances between $x$ and each of the $\mu^i$).  If we
have a multimetric $\rho$ though, we have several ways to avoid
this. For example, we could model the probability of each $x^i$ as a
Gaussian of $\rho(\delta_{x^i} + \sum_j \delta_{\mu^j})$.  We would
then take the probability of $\{x^i\}$ to be the product of the
probabilities of the $x^i$, as in conventional Gaussian mixtures
modeling. We could even model the probability of $\{x^i\}$ given the
$n$ points $\mu^i$ as a single Gaussian, with argument 
$\rho(\sum_i \delta_{x^i} + \sum_j \delta_{\mu^j})$.

 \item Kernel density estimation: In kernel density estimation, one
does not estimate the distribution over $x$ as a linear combination of
$n$ kernel functions (e.g., Gaussians) that are free to be centered
anywhere in $X$, and then search for which such linear combination
maximizes the probability of one's data.  Instead one centers a kernel
function on each of the data points, and searches for the optimal
parameters of those kernels functions. Conventionally such kernel
functions only take two arguments. However exactly as in application
1, if one has a multimetric over $X$, one can use kernel functions
whose argument involves more than two points at once.

 \item Classification can always be done via density estimation and
Bayes' theorem. So with applications 1 and 2, we have new ways of doing
classification.

 \item Kernel machines are a recent advance in machine learning in
which data is first mapped non-linearly into a feature space where
standard algorithms (like linear regression, linear discriminant
analysis, PCA, etc) are applied \cite{chsh00}. Because of the
non-linear mapping such methods work even when relationships in the
data are highly non-linear. All that is required for such methods is a
positive definite kernel function, $k(x,x')$, giving inner products in
the feature space. Multimetrics are not positive definite functions
but can easily be made so by taking $k(x,x') = \exp[-\rho(\delta_x +
\delta_{x'})]$ as the kernel. So any of the multimetrics discussed
above can be used for statistical analysis with kernel-based learning
algorithms. In particular, this is the case for either for supervised
or unsupervised learning with kernel machines. In particular, we can
use exponentials of multimetrics for regression by using them instead
of the conventional kernels of kernel machines, with the
multiplicative coefficients of each kernel (in the linear combination
that gives our fit to the data) set to minimize some appropriate
quadratic objective function.

 \end{enumerate}






 \section{Appendix}

 \subsection{Proof of Lemma 1.3}

That $f(\rho)$ obeys conditions (2) and (3) when $\rho$ does is
immediate. To prove that condition (1) is obeyed, consider any $u, v,
w \in T(X)$ such that $\rho(u + v) \le \rho(u + w) + \rho(v +
w)$. First assume that $\rho(u + v) \le {\mbox{max}}[\rho(u + w),
\rho(v + w)]$. Then since $f$ is increasing, $f(\rho(u + v)) \le
{\mbox{max}}[f(\rho(u + w)), f(\rho(v + w))]$. Since in turn
${\mbox{max}}[f(\rho(u + w)), f(\rho(v + w))] \le f(\rho(u + w)) +
f(\rho(v + w)$, condition (1) is obeyed. 

Now consider the other case, where $\rho(u + v) > {\mbox{max}}[\rho(u
+ w), \rho(v + w)]$. In this situation, because $f$ is concave, we
know that $f$ increases $\rho(u + v)$ less than it increases both
$\rho(u + w)$ and/or $\rho(v + w)$. So again condition (1) is
obeyed. {\bf{QED}}.

 \subsection {Proof of claim in Ex. 1}
Consider any $u, v$ and $w$ whose norms equal 1.  Then
squaring both sides of condition (1) for our $\rho$ implies that

$Var(\frac{u + v}{2}) \le Var(\frac{u + w}{2}) + Var(\frac{v + w}{2})
+ 2 \sqrt{Var(\frac{u + w}{2})Var(\frac{v + w}{2})}$.

 \noindent Use the expansion $Var(\frac{s + t}{2}) = \frac{Var(s) +
Var(t)}{2} + (\frac{E_s(x) - E_t(x)}{2})^2$ and cancel terms. The
hardest case for the resultant inequality to hold is where our three
variances all equal 0. Setting them to 0, we see that condition (1)
holds if for any three real numbers $a, b, c$,

$|a - b| \le |a - c| + |b - c|.$

 \noindent This is just the conventional triangle inequality though. So
condition (1) always holds. {\bf{QED.}}


 \subsection {Proof of claim in Ex. 3}
First note that for any $s \in T(X), {\langle}s \mid s{\rangle} \ge
0$, since all all components of $F$ are non-negative. Furthermore, all
$s, t \in T(X), {\langle}s \mid t{\rangle} \ge 0$, since all
components of those vectors are non-negative as are all components of
$F$. In addition, we can use the properties of $F$ to prove that our
tensor contraction obeys the Cauchy-Schwartz inequality: ${\langle}u
\mid v{\rangle}^2 \le {\langle}u \mid u{\rangle}{\langle}v \mid
v{\rangle} \; \forall u, v \in T(X)$. (Exampnd $\langle s, s \rangle
\ge 0$ for $s \equiv u - \alpha v$. Solve for the $\alpha$ minimizing
the lefthand side (which is quadratic in $\alpha$), and plug that
in. Collecting terms establishes the desired inequality.)

Now to check condition (1) for our $\rho$, square both sides of it and
cancel terms. So the lefthand side is just ${\langle}u \mid
v{\rangle}$. Since all inner products are non-negative, the right-hand
side is bounded below by $\sqrt{{\langle}u \mid u{\rangle}{\langle}v
\mid v{\rangle}}$. Plugging in the Cauchy-Schwarz inequality
establishes that condition (1) does indeed hold. {\bf{QED.}}


 \subsection {Proof of claim in Ex. 4}
Conditions (2) and (3) are immediate. To prove condition (1), first
note that it holds for $\rho_1(s) = {\mbox{max}}(x_1 : s(x_1 \ne
0)$. Then note that it holds for $\rho_1(s) = -{\mbox{min}}(x_1 :
s(x_1 \ne 0)$, and invoke Lemma 1.2, to see that the width in $x_1$
of the support obeys condition (1). {\bf{QED.}}



 \subsection {Proof of claim in Ex. 5}
Conditions (2) and (3) are immediate. Condition (1) also holds if (the
supports of) $u$ and $v$ overlap, since any non-zero volume must equal
at least 1, and that overlap volume gets counted twice in the sum
$\rho(u + w) + \rho(v + w)$, regardless of $w$. If (the supports of)
$u$ and $v$ do not overlap, then (the support of) $w$ must either
extend outside of (the support) of $u$ or of $v$. This means that
condition (1) must hold in this case as well. {\bf{QED.}}


 \subsection{Proof of claim in Ex. 6}
Define ${\mbox{argmax}}_x u(x) \equiv a, {\mbox{argmax}}_x v(x) \equiv
b, {\mbox{max}}_x (u(x) + v(x)) \equiv M$, and ${\mbox{max}}_x (u(x) +
w(x)) + {\mbox{max}}_x (v(x) + w(x)) - 2||w|| \equiv N$; we want to
prove that $M > N$.  To that end, note that if the support of $w(x)$
is restricted to $a$ and $b$, then $N$ becomes $u(a) + v(b) - ||w|| =
u(a) + v(b) - 1 \le u(a)$. On the other hand, $M$ is bounded below by
$u(a)$. So condition (1) holds for this situation.

We now consider the situation where $w$'s support is not restricted to
$a$ and $b$. It will be useful to define ${\mbox{argmax}}_x (u(x) +
w(x)) = d$ and ${\mbox{argmax}}_x (v(x) + w(x)) = e$. First consider
the case where $d \ne e$. Then it is immediate that by transferring
any $w(c \not \in \{d, e\})$ to $w(d)$ and/or $w(e)$, we do not
decrease $N$ (since $||w||$ doesn't change). We can then transfer
$w(d)$ to $w(a)$ and $w(e)$ to $w(b)$, again not decreasing $N$.
After doing this for all such points $c$, we recover the case where
the support of $w(x)$ is restricted to $a$ and $b$, as in the
preceding paragraph. So we can conclude that condition (1) is obeyed
for this case.

The remaining case to consider is where $d = e$. For this case we can
transfer all $w(c \ne d)$ to $w(d)$, and in doing so increase
$N$. Doing this for all such $c$ restricts $w$'s support to $d$. After
having done this, ${\mbox{max}}_x (u(x) + w(x)) = u(d) + ||w|| \le
u(a) + 1$, and similarly ${\mbox{max}}_x (v(x) + w(x)) \le v(b) +
1$. So we again get $N \le u(a) + v(b) - 1$, which means $M \ge
N$. There are no more cases to consider. {\bf{QED.}}



 \subsection{Proof of claim in Ex. 13}
First note that we have already established that our $\rho$ obeys
conditions (2) and (3) of being a multimetric, and therefore only need
to establish that it is strictly concave. That will be the case iff
$\rho(\alpha u + (1 - \alpha)v) \le \alpha \rho(u) + (1 -
\alpha)\rho(v) \; \forall u \in T(X), v \in T(X), \alpha \in [0,
1]$. Square both sides of this inequality and cancel terms. Then
exploit the Cauchy Schwarz inequality for ${\langle}. \mid
.{\rangle}$, established in the proof of the claim in
Ex. 3. {\bf{QED.}}



 \section{Acknowledgements}

I would like to thank Bill Macready and Creon Levit for stimulating
discussion.


\begin{thebibliography}{10}

\bibitem{chsh00}
Nello Christianini and John Shawe-Taylor.
\newblock {\em An introduction to support vector machines and other
  kernel-based learning methods}.
\newblock Cambridge University Press, 2000.

\bibitem{duha00}
R.~O. Duda, P.~E. Hart, and D.~G. Stork.
\newblock {\em Pattern Classification (2nd ed.)}.
\newblock Wiley and Sons, 2000.

\bibitem{futo04}
Bent Fuglede and Flemming Topsoe.
\newblock Jensen-shannon divergence and hilbert space embedding.
\newblock Submitted to ISIT2004, 2004.

\bibitem{hall99}
M.~Hall.
\newblock Universal geometric approach to uncertainty, entropy, and
  information.
\newblock {\em Physical Review A}, 59:2602, 1999.

\bibitem{judg04}
George Judge.
\newblock Semiparametric moment based estimation for binary response models.
\newblock RMBE-DE1-4-2-04.doc, 2004.

\bibitem{lin91}
Jianhua Lin.
\newblock Divergence measures based on the shannon entropy.
\newblock {\em IEEE Trans. Info. Theory}, 37(1):145--151, 1991.

\bibitem{osva03}
Ferdinand Osterreicher and Igor Vajda.
\newblock A new class of metric divergiences on probability spaces and its
  applicability in statistics.
\newblock {\em Ann. Inst. Statist. Math.}, 55(3):639--653, 2003.

\bibitem{tops02}
Flemming Topsoe.
\newblock Inequalities for the jensen-shannon divergence.
\newblock 2002.
\newblock unpublished.

\bibitem{woma04a}
David~H. Wolpert and William Macready.
\newblock Self-dissimilarity as a high dimensional complexity measure.
\newblock In {\em Proceedings of the International Conference on Complex
  Systems, 2004}, 2004.
\newblock in press.

\bibitem{woma04b}
David~H. Wolpert and William Macready.
\newblock Self-dissimilarity as a high dimensional complexity measure.
\newblock http://xxx..., 2004.

\end{thebibliography}






 \end{document}


REFERENCES (to be integrated)

Zhang,  Chidong and Jonathan Gottschalck, 2002:: " SST Anomalies
of ENSO and the Madden-Julian Oscillation in the Equatorial
Pacific" Journal of Climate: Vol. 15, No. 17, pp. 2429-2445.

Wang,B, A. Barcilon and Z. Fang, 1998: "Stochastic Dynamics of El
Ni�o-Southern Oscillation", Journal of the Atmospheric Sciences:
Vol. 56, No. 1, pp. 5-23.

Chang,  Ping, Link Ji Bin Wang and  Tim Li, 19xx: "Interactions
between the Seasonal Cycle and El Ni�o-Southern Oscillation in an
Intermediate Coupled Ocean-Atmosphere Model", Journal of the
Atmospheric Sciences: Vol. 52, No. 13, pp. 2353-2372.

Wang, Risheng  and Bin Wang, 20XX: "Phase Space Representation and
Characteristics of El Ni�o-La Ni�a", Journal of the Atmospheric
Sciences: Vol. 57, No. 19, pp. 3315-3333.

Tsonis , A.A., G.N. Triantafyllou, J.B. Elsner, J.J. Holdzkom II,
and A.D. Kirwan Jr, 19xx: "An Investigation of the Ability of
Nonlinear Methods to Infer Dynamics from Observables", Bulletin of
the American Meteorological Society: Vol. 75, No. 9, pp.
1623-1634.

Tsonis,  A.A.,  J.B. Elsner, and K.P. Georgakakos, 2XXX:
"Estimating the Dimension of Weather and Climate Attractors:
Important Issues about the Procedure and Interpretation", Journal
of the Atmospheric Sciences: Vol. 50, No. 15, pp. 2549-2555.

Higgins, R. W. and W. Shi, 19XX: " Intercomparison of the
Principal Modes of Interannual and Intraseasonal Variability of
the North American Monsoon System", Journal of Climate: Vol. 14,
No. 3, pp. 403-417.

Lau, Nar-Cheung and Mary Jo Nath, 19xx: "Impact of ENSO on the
Variability of the Asian-Australian Monsoons as Simulated in GCM
Experiments", Journal of Climate: Vol. 13, No. 24, pp. 4287-4309.

Gu, Guojun and Chidong Zhang, 19xx: "A Spectrum Analysis of
Synoptic-Scale Disturbances in the ITCZ", Journal of Climate: Vol.
14, No. 12, pp. 2725-2739.  [ wavelets]

Meehl, Grald A. and Julie M. Arblaster, 20XX: "The Tropospheric
Biennial Oscillation and Asian-Australian Monsoon Rainfall",
Journal of Climate: Vol. 15, No. 7, pp. 722-744. (SVD, Anomaly
Correlation)

Smith, Leonard, 2000: " Disentangling Uncertainty and Error: On
the Predictability of Nonlinear Systems, 2000, Chapter 2 in
Nonlinear Dynamics and Statistics,  pp 31-64ed. A. Mees, Published
by Birkhauser. Elsner, J. B., and A.A. Tsonis, 1992: Nonlinear
Prediction, Chaos,  and Noise", Bulletin of the American
Meteorological Society, Vol. 73, No. 1, pp 49 - 60. Hou, A. Y., S.
Q. Zhang, A. M. da Silva, W. S. Olson, C. D. Kummerow, and J.
Simpson, 2001: Improving global analysis and short-range forecast
using rainfall and moisture observations derived from TRMM and
SSM/I passive microwave sensors. Bull. Amer. Meteoro. Soc., 82,
659-679.

Hou, A. Y., S. Q. Zhang, A. M. da Silva, and W. S. Olson, 2000:
Improving assimilated global datasets using TMI rainfall and
columnar moisture observations. J. Climate, 13, 4180-4195.

Hou, A. Y., D. V. Ledvina, A. M. da Silva S. Q. Zhang, J. Joiner,
and R. M. Atlas, 2000: Assimilation of SSM/I-Derived Surface
Rainfall and Total Precipitable Water for Improving the GEOS
Analysis for Climate Studies. Mon. Wea. Rev., 128, 509-537.
Compressed postscript version (2.3MB)

==============================================================

The first formalization of SD appeared in \cite{woma00}. There, an
encompassing framework was proposed, which unfortunately was
difficult to apply to real-world data. Two years ago we won a
competitive NASA Ames Director's Discretionary Funding grant to
investigate alternative SD quantifications. These awards provide
seed money to perform high-risk high-payoff research that, if
successful, can then be migrated to a mid-level NASA Technical
Readiness Level (TRL). Under that award we have developed a
quantification of self-dissimilarity that can be applied to
real-world data; the purpose of the current proposal is to migrate
that self-dissimilarity measure to a higher TRL by applying it to
IDU domains with particular focus on the Earth climate system, We
will use SD to characterize and deepen understanding of the
coupled land-ocean-atmosphere system through an empirical analysis
of structures operating at different spatio-temporal scales,
exploit the resulting SD signatures as a source of features for
improved predictive machine learning algorithms, and validate
models by comparing model SD signatures with observation.

Before presenting a broadly applicable SD framework, we summarize
the two basic steps of the approach that should help to motivate
the details that follow.

In all SD analysis applications there are only two fundamental
tasks being carried out. The first characterizes the types of
patterns seen within the system under study, and the second
compares these patterns. For the broadest applicability we have
generalized these basic notions considerably.

 \begin{itemize}
 \item \textit{Generation of scale-indexed probability
distributions from a data set:} Typically there is a set of
transformations of a data set that we wish to be ignored by our
self- dissimilarity measure. For example, we might want the
measure to give the same value when applied both to an image and
to a slight translation of that image. We apply those
transformations to the data set, thereby generating a set of data
sets. We then apply a domain-appropriate magnification to each of
those data sets. In this way we generate a set of data sets for
each scale. We then use machine learning and available prior
knowledge \cite{duha00} to transform each such set into a
probability distribution. Intuitively, each scale's probability
distribution reflects what one is ``likely to see" if the original
data set were examined at that scale, and if no attention were
paid to the transformations we wish to ignore.  \item
\textit{Quantifying the dissimilarity among a set of probability
distributions:} Given our scale-indexed set of distributions, we
need a way of quantifying the ``distance" between two or more such
distributions. To do this we needed to create a real-valued
function of one or more probability distributions that
 \begin{enumerate}
 \item obeys the usual properties of a metric (e.g., symmetry) when
it takes two arguments;  \item is finite even for
"delta-function-like" distributions commonly formed from small
data sets;  \item  obeys the requirements of an extended definition
of a metric for more that two arguments (even then those arguments
are themselves sets of multiple points), a definition we needed to
formulate;  \item can be quickly calculated for large spaces;  \item
has a natural interpretation in terms of the "total amount of
information stored in its (probability distribution) arguments".
 \end{enumerate}
Unfortunately, no such measure existed prior to our
work\footnote{The nearest measure which does not even satisfy 1
and 2 is the Jensen-Shannon distance \textbf{REF}.} so we had to
develop a new multi-argument version of distance called
\textbf{multimetrics}. Multimetrics obey all of 1 through 5 and
promise application in many domains outside of SD analysis. We
will illustrate these measures later.
 \end{itemize}

With this high-level picture in mind we turn to a detailed
description of self-dissimilarity.

 \subsubsection{Self-Dissimilarity Analysis}

To apply self-dissimilarity to many different domains, we need to
formalize it, so we can be sure it is the same mathematical
structure every time we apply it. There are five components to
using self-dissimilarity to measure complexity in any particular
domain:
 \begin{enumerate}
 \item Let $q_0$ be an object in a space of objects $Q_0$ whose
self-dissimilarity interests us.  \item There is a set of
invariances of $Q_0$  that we wish ignore when measuring SD.
Intuitively, such an invariance is a partition of $Q_0$ into sets
of elements equivalent under that invariance. We quantify such an
invariance with a function $g$ that maps any $q_0$ in $Q_0$ to the
set of all elements of $Q_0$ related by our invariance to that
$q_0$. Formally, we require that for all $q_0, q_0'\in g(q_0)$
then $g(q_0) = g(q_0')$. Working, with the entire set $g(q_0)$ is
the most direct way of incorporating the invariance into the
analysis.\footnote{Alternative ways of transforming $q_0$ to
incorporate the invariances limit the types of $Q_0$ on which SD
may be applied, and introduce statistical biases.} 3) We then have
a set of transformations $W_\theta:Q_0\mapsto Q_1$ indexed by
$\theta$. $\theta$ is the generalized notion of scale. We apply
$W_\theta$ to the set $g(q_0)$ for many different $\theta$ values.
This gives a $\theta$-indexed set of subsets of $Q_1$. We then
numerically compare all those subsets using a multimetric with the
comparisons constituting the SD signature of $q_0$.  \item  A
multimetric is a real-valued mapping $K$ that takes subsets of as
arguments. Intuitively, this is how we quantify ``dissimilarity",
while the $\{ W_\theta\}$ are how we quantify ``self-".  \item In
applying the above procedure, we rarely know $q_0$ directly, but
instead have a data set together with a likelihood function giving
the likelihood of generating the observed data $D$. So what we're
interested in is the expected value where represents the
multimetric applied to the generated data  .
 \end{enumerate}

To ground this abstract discussion we consider a few concrete
examples.

\textit{Example 1:} $Q_0$ is the space probability density
functions (pdf's) over some Euclidean space $E$. A point in $E$
might represent a satellite image and consist of a matrix of
intensities $I(x)$ at different pixel locations $x$. If we wish
our measure to ignore translations over $x$ then $g(q_0)$ is the
set of all translations of the pdf. Thus if
$q_0=\pr\bigl(I(x)\bigr)$ represents a satellite image then
$g(q_0)$ represents the set $\{\pr\bigl(I(x-x_1)\bigr),
\pr\bigl(I(x-x_2)\bigr), \cdots\}$ where $x_i$ are translation
vectors. If we are interested in scalings of the image, each
$W_\theta$ may be magnification by $\theta$ followed by windowing
about the origin so that only the local structure of the image
around $x_i$ is considered. If $T$ is an operator which truncates
an image $I(x)$ to a window around the origin then
$W_\theta\{g(q_0)\} = \{\pr(T[I(x/\theta-x_1)]\bigr),
\pr(T[I(x/\theta-x_2)]\bigr), \cdots \}$. Each
$q^{\theta,i}_1\equiv\pr(T[I(x/\theta-x_i)]\bigr)$ is a
probability density over a subspace of $E$. For satellite images
the observed data of pixel intensities is usually generated from
by some windowing process of its own (since the camera focuses on
a certain patch of the Earth), together with blurring of nearby
points due to finite sensor resolution. These effects may be
accounted for in a likelihood model $P(D|q_0)$ which smooths
intensities and admits Gaussian noise. To compare the resulting
scaled image sets $W_\theta\{g(q_0)\}$, the simplest possible
approach is to form the symmetric matrix of all pairwise
comparisons whose $i$, $j$ element is the multimetric (or perhaps
Jensen-Shannon or Kullback Leibler) distance between
$W_{\theta_i}\{g(q_0)\}$ and
$W_{\theta_j}\{g(q_0)\}$.\footnote{While multimetrics generalize
to distances between objects which are not probability densities,
to apply the Jensen-Shannon and Kullback Leibler distances to the
sets $W_\theta\{g(q_0\}$ we may interpret these as probabilities
which are uniform over the set and zero off it.} This measure
might have be susceptible to some of problems that typically arise
with averages of distances though, like being over-sensitive to
outliers. An alternative is to have $K$ be KL distance between
$P(q_1)$ and $P(q'_1)$. Or KL distance between $\int dq_1 P(q_1)
q_1$ and the other average, $\int dq'_1 P(q'_1) q'_1$.

\textit{Example 2:} This example extends the previous purely
spatial example by including time. In this variant, the
translations constituting g are only those along the first $N-1$
dimensions of the $N$-dimensional space $E$. $\theta$ has two
components, a vector pointing along the $N$th dimension of $E$,
$t$, and a scalar $k$. $W_{t,k}(q_0)$ translates $q_0$ by $t$, and
then scales the first $N-1$ dimensions of $E$ by $k$ and windows
them, exactly as in Example 1. $K$ can be any of the measures
discussed in Example 1. In particular, if $K$ is the KL distance
between its arguments, then $K(\theta, \theta')$ measures how
information on scale $k$ at time $t$ is related to the information
at time $t'$ on scale $k'$. In this way we can investigate the
dynamics of information coupling between different scales of an
evolving $(N-1)$-dimensional pdf at different times. In
particular, we can investigate the nonstationarity of that
evolving pdf.

 \noindent \textit{Example 3:} This example is also a variant of
Example 1, but is meant to convey the generality of the SD
framework.  Rather than pdf's over $E$, we let $Q_0$ be the set of
possible mappings from $E$ into a finite set of symbols. So an
element of $Q_0$ could be the positions of particles of various
types of particles in $\mathbb{R}^3$, for example. $g$ is again
the set of all translations. However say we are not interested in
comparing a $q_0$ to a scaled version of itself. Instead have each
$\theta$ equal a set of $n$ vectors $\{v_i \in E\}$. Then have
$W_\theta(q_0)$ be the symbols $q_0(v_1), q_0(v_2), \cdots
q_0(v_n)$. Then we could have K take two sets of elements in $Q_1$
as its arguments, and return the KL distance between those sets,
as in Example 1. As an example, we could have $v_1 = 0$ for all
$\theta$, and then have $v_2 = ka$, where $k$ is a scalar, and the
vector $a$ is the same for all $\theta$. In this example
$W_\theta$ isolates a pair of symbols separated by s multiple of
the vector a; changing theta changes that multiple. So our
self-dissimilarity measure quantifies how the patterns of pairs of
symbols separated by $ka$ change as one varies $k$. Another
possibility is to have $v_1 = R_k(a)$, where $R_k(\cdot)$ is
rotation by $k$. In this case our measure quantifies how the
patterns of pairs of symbols changes as one rotates the space.
Another important modification is to allow $n > 2$, so that we
aren't just looking at pairs of symbols.

\textit{Example 4:} This example is the same as Example 3, except
that $E$ is an $M$-dimensional infinite lattice rather than a
Euclidean space. This means that the two examples in Example 1 and
2 of $W_\theta$ have to be changed, to not allow all scale factors
$k$, and not allow all rotation angles, respectively. Only those
transformations which map the lattice into itself are allowed. No
other changes are necessary. As an example, we could have $M = 1$,
so that an element of $q_0$ is a symbolic time series. Take $n =
2$, with $v_1 = 0$, and $v_2 = k$, $k$ now being an integer. In
this case our measure is an information-theoretic quantification
of how time-lagged samples of the time-series $q_0$ differ from
each other as one changes the lag size.

Having $n > 2$ allows even more nuanced versions of this
quantification. Furthermore, other choices of $K$ (described
below) allow it take more than two sets at once as arguments. In
this case, $K$ takes an entire set of time-lagged samples, running
over many time lags, and measures how "spread out" that full set
is.

These measures complement more conventional information-theoretic
approaches to measuring the time-lagged character of $q_0$ varies
with lag size. A typical such approach would evaluate the mutual
information between a the symbol at a random point in $q_0$ and
the symbol $k$ away, and see how that changes with $k$. Such an
approach compares singletons: it sees how the distribution of
symbols at a single point are related to the distribution of
symbols at the single time-lagged version of that point. These new
measures instead allow us to compare distributions of $n$-tuples
to one another.

Note that while our measure can be viewed as quantifying the
time-lag character of $q_0$, it can also be viewed as quantifying
its scaling nature, just like in Ex. 1. This is most obvious when
$n > 2$, and $v_1 = 0, v_2 = k, v_3 = 2k, \cdots$ In this case any
$q_1$ is a decimation of a $q_0$ -- in the same sense as
decimation is used for scaling in renormalization group theory --
followed by a windowing. In addition, it is natural to modify the
measure to allow $q_0$ to be a probability distribution over the
space of bi-infinite symbol strings, again just like in Ex. 1.

\textit{Example 5:} This is a dramatically different example to
show that self dissimilarity can be measured for quite different
kinds of objects. Let $Q_0$ be a network, i.e., an undirected
graph with labelled nodes. Have $g(q_0)$ be the set of
relabelings of the nodes of net $q_0$. Have each $W_\theta$ run
an iterative decimation algorithm on $q_0$. Each such algorithm
grows outward from some fixed starting (theta-independent) node
$a$, removing some nodes as it does so, and introducing some
compensating new links. After passing over a node without removing
it the algorithm tags that node so that it will not be removed at
subsequent iterations. At the first iteration that at least $N$
nodes have been tagged this way, all remaining nodes in $q_0$ are
removed. Some fixed rule is then used for removing any excess
nodes to ensure that the final net has exactly $N$ nodes.
Different $W_\theta$ run different such algorithms (e.g.,
algorithms that remove nodes at different iterations).
Intuitively, such an algorithm $W_\theta$ magnifies the network,
and then windows it. Different $W_\theta$ magnify by different
amounts.

Then we could have $D$ be generated from $q_0$ via some
simplification process, i.e., some separate decimation algorithm.
The reason for this is that, for example, typically an ecologist
can't give you an actual food web in a particular region, but only
a simplified version of it. We could then have $K$ incorporate any
convenient way of comparing nets.

In all of these examples $Q_0$ is a set of functions over an
underlying space $E$, and the invariance $g$ is a group of
transformations over $E$. Each $W_\theta$ then can be cast as an
element in another group of transformations of $E$, followed by a
fixed function taking the resultant element of $Q_0$ to the new
space $Q_1$. For example, $W_\theta$ can be magnification followed
by windowing (Example 1), or a rotation followed by sampling at a
fixed set of points (Example 2). Accordingly, in these examples
self-dissimilarity is an information-theoretic characterization of
the relation of two groups over the same space. This does not have
to be the case however.

 \subsubsection{Multimetrics}
Before presenting preliminary results on the applicability of the
method we briefly describe a powerful approach to quantifying
distance amongst a set of probability distributions which result
the different scale analyses.

Applying the analysis of the preceding subsection to a $q_0$ will
give us a collections of sets, $W_\theta\{g(q_0)\}$, one such set
for each value of theta. All elements in all those sets live in
the same space, $Q_1$. It is this collection as a whole that
characterizes the system's self-dissimilarity.

Note though that different domains will have different spaces
$Q_1$. So to have self-dissimilarity be able to apply to many
different domains, we need to distill a collection
$W_\theta\{g(q_0)\}$ of elements of the associated $Q_1$'s into a
set of real numbers. Given a way to compare sets of real numbers,
we can then compare the collections from different domains. In
addition, often there is too much information in a collection of
$Q_1$ values for it to be a useful way of analyzing a system. Even
when just analyzing a system by itself, without comparing it to
other systems, usually will want to distill its collection down to
a set of real numbers.

Since what we are interested in is the dissimilarity of a
collection of $Q_1$ values, the numbers distilled from the
collection should measure how ``spread out'' its elements are.
Intuitively, what we need is a metric for measuring the dispersion
of a set of elements. To do this we need to extend the
conventional concept of a metric, which only takes a pair of
arguments, to allow an arbitrary number of arguments. In
addition, to compare the sets of numbers distilled from different
collections, we also need a metric that tells us how ``spread
out'' from one another some sets are. These two extensions of
conventional metrics are the topic of this section.

Given a space $X$, fix some scheme for ordering the members of any
set of elements of $X$. Let $Y$ be such an ordered set of elements
from some space $X$.  Write $Y^i$ to mean the $i$'th element of
$Y$, and $Y^{(i)}$ to mean $Y$ with the $i$'th element removed.
Then taking our cue from the formal definition of a two-argument
metric, we define a multi-argument metric ({\bf{multimetric}}, for
short) for $X$ as a function $\rho$ from any such $Y$ to the reals
that obeys the following:
 \begin{enumerate}
 \item[1)] $\rho(Y^{(1)}) \le \sum_{j>1} \rho(Y^{(j)})$.  \item[2)]
$\rho(Y) \ge 0$.  \item[3)] $\rho(Y) = 0$ if and only if the
elements in $Y$ are all identical.  \item[$\tilde{3}$)] An
alternative to (3), appropriate when $X$ is a Euclidean space, is
that $\rho(Y) = 0$ iff the elements in $Y$ are contained in a
hyperplane of dimension $\le |Y| - 2$, where $|Y|$ indicates the
cardinality of $Y$.
 \end{enumerate}
Note that condition (3) means that $\rho(Y) = 0$ if $|Y| = 1$.

Example: Take $X$ to be an $N$-dimensional Euclidean space. Order
any finite set of elements from $X$ so that $x \in X$ follows $x'
\in X$ iff either $x = x'$ or there is some component $i$ such
that $x_j \ge x'_i$ for all $j \le i$. (Any ordering will do.)
Then with the alternative $\tilde{3}$), $\rho(Y)$ can be the
volume of the convex hull of the points in $Y$.

So for example, if $N = 2$ and $|Y| = 3$, all three subsets
$Y^(i)$ contain two points, and the associated value of $\rho$ is
the distance between those two points. Note that this equals 0 if
the two points in $Y^{(i)}$ lie on top of each other, in accord
with $\tilde{3}$). The rest of $\tilde{3}$) is immediate, as is
(ii), and (1) is just the standard triangle inequality.

For $|Y| = 4$, all four subsets $Y^{(i)}$ contain three points,
and the associated value of $\rho$ is the area of the triangle
subtended by those three points. For such a triple of points being
collinear, that area equals 0, in agreement with $\tilde{3}$). The
rest of $\tilde{3}$) and 2) are again immediate, and it is
straightforward to check that 1) holds.

As a more trivial example, the function $\rho(Y)$ that equals 1 so
long as $Y$ contains at least two elements is a tight multimetric.
In particular, if $X$ is an $N$-dimensional Euclidean vector
space, then all sets $Y$ that consist of two points obey condition
(1) for this $\rho$, i.e., they obey the triangle inequality.

Finally, while often other multimetrics are more appropriate, it
should be noted that one can always produce a multimetric $\rho$
over a non-vector space $X$ by using a multimetric $\rho'$ over a
vector space, $X'$. All one needs to do is specify a bijection $f$
from $X$ to $X'$: $\rho(Y) = \rho({Y^i}) = \rho'({f(Y^i)})$. (If
$f$ is not invertible, then having $\rho'({f(Y^i)}) = 0$ need not
imply that all $Y^i$ are identical.) One can do similar things
even for vector spaces $X$, if desired. (Such mappings are
analogous to the mapping from a "data space" to a "feature space"
underlying kernel machines \cite{chsh00}.)

>From now on, we use the shorthand $\rho(\cup_i Y^i) = \prod_i
Y^i$, where we implicitly assume the elements of $\cup_i Y^i$ are
ordered according to our pre-fixed scheme. So for example, $\rho(A
\cup B)$ is written $AB$, and $\rho(Y)$ is written simply as $Y$,
with the context indicating whether we mean the set or its
multimetric value.

We call a multimetric *tight* if it obeys the following for all
subsets $A, B, C$ of $X$:
 \begin{enumerate}
 \item[4] For all $A, B, C \in 2^X$ where $A$ and $C$ are nonempty,
 \begin{enumerate}
 \item  $AB \le AC + BC - C$;  \item $AB = A \implies B$ is a subset
of $A$.
 \end{enumerate}
 \end{enumerate}

Example: The convex hull $\rho$ is not tight. To see this take $X
= \mathbb{R}^2$, $|Y| = 4$, and have $A$ contains two points while
$B$ and $C$ each contain a single point. Finally, have $C$'s point
be collinear with the two in $A$, but not with $B$'s point. Then
$AC$ equals 0, as does $BC$ and $C$. However $AB$ is greater than
zero. On the other hand, if we restrict attention to sets of
points in $\mathbb{R}^n$ such that no subset of $n$ of them lies
on a hyperplane of dimension $< n$, then the convex hull $\rho$ is
tight.

As another example, with no restrictions on $Y$, take $\rho(Y)$ to
be the volume of the smallest axis-parallel box enclosing the
Euclidean points in $Y$. A variant is to have it be the volume of
the smallest enclosing axis-parallel box that also encloses the
origin. We can also replace the volume of such boxes with the sum
of the lengths of their edges, or the sum of the coordinates of
its highest corner (i.e., $\sum_j \max_i Y^i_j$).

Yet another variant is where rather than set the faces for
coordinate $i$ to $\max_j Y^j_i$ and $\min_j Y^j_i$, we set them
to the $m$'th and $n$'th percentiles of the values $\{Y^i_j\}$,
respectively, where $n < m$. It is straightforward to verify that
(ii) - (4) are obeyed for all of these measures. \textbf{dhw: We
should explicitly verify this.}

An example similar to these bounded box examples is where
$\rho(Y)$ is the $V(Y)$, the volume of the smallest hypersphere
enclosing the elements $Y$. \textbf{dhw: ditto.} A variant is the
volume of the smallest hypersphere that encloses a fraction $m$ of
the points in $Y$. Yet another variant is the square root of the
average of the squares of the Euclidean distances of the points in
$Y$ from one another. This variant can be re-expressed as $\sqrt{
[\sum_{i,j>i} [V(Y^i, Y^j)]^{2/N}] / [\sum_{i,j} 1]}$. This can be
generalized to involve sums over triples of points, quadruples of
points, etc., We can also extend the square root variant to
triples in other ways, e.g., $\sqrt{ [\sum_{i,j>i,k>j} \Omega(Y^i,
Y^j, Y^k)] / [\sum_{i,j>i,k>j} 1] }$, where $\Omega(Y^i, Y^j,
Y^k)$ is the area subtended by $Y^i$, $Y^j$, and $Y^k$.
\textbf{dhw: ditto}

Unlike the volume of the axis-parallel box, these alternative
measures are invariant under coordinate rotations. They can be
more computationally expensive to calculate exactly however.

As a last comment, note that the multimetric that takes any $Y$ of
at least two points to the value 1 is not tight, since it violates
(ii).

A multimetric tells us how much a specified set of elements of X
``differ from one another".  It will be important to also define a
multimetric for how much a specified set of subsets of X differ
from one another. To that end, let $\rho$ be any tight multimetric
for X. Indicate a set of elements of $2^X$ by $Z$, with $Z^(i)$
indicating the set of all subsets of $X$ other than the $i$'th
one, and $Z^i$ a single such subset.  Then define a *set
multimetric* $2^{\rho}(Z^1, Z^2, ...) \equiv \prod_i Z^i - \sum_i
Z^i / \sum_i 1 $.

Note that the $Z^i$ can have different cardinalities. Note also
that ${\cal{C}}\rho(x^1, x^2, ...)$  -- the value of ${\cal{C}}\rho$ when its
arguments are all single-element subsets of $X$ --  equals
$\rho(x^1, x^2, ...)$. In other words, ${\cal{C}}\rho$ and $\rho$ agree
when ${\cal{C}}\rho$'s arguments are all singletons.

There is an extensive algebra governing multimetrics, tightness,
and associated set multimetrics. That algebra is described in the
appendix, where in particular it is proven that if rho is tight,
then ${\cal{C}}\rho$ is a multimetric. If $\rho$ is not tight though,
${\cal{C}}\rho$ need need be a multimetric.

Example: As discussed in an example above, the volume of the
convex hull of a set of points in a Euclidean space is a non-tight
multimetric. To show that the associated ${\cal{C}}\rho$ is not a
multimetric, using the sets $A$, $B$, and $C$ from that previous
example, take $Z^1 = A$, $Z^2 = B$, and $Z^3 = C$; it is not the
case that ${\cal{C}}\rho(Z^1, Z^2) \le {\cal{C}}\rho(Z^1, Z^3) + {\cal{C}}\rho(Z^2,
Z^3)$ for those choices.

In this document we focus on the use of multimetrics for
self-dissimilarity analysis. However it is worth briefly
mentioning some of their myriad other possible applications. Here
we illustrate that breadth of possible uses with some examples of
applying multimetrics to sets of Euclidean vectors.
 \begin{enumerate}
 \item Clustering: Say that rho is tight, so that ${\cal{C}}\rho$ is a
multimetric, and have $X$ be a vector space. Let $Z$ be a
partition of $Y$ into a set of subsets. Then we can search for
that partition that minimizes the average intra-subset values of
$\rho$, $E(\rho(Z^i))$, while maximizing the value of ${\cal{C}}\rho$
among those subsets, ${\cal{C}}\rho(Z)$.  \item Density estimation: In
mixtures of Gaussians density estimation, one is given a data set
of vectors $Y$ that were generated by IID sampling an unknown
distribution over $X$. Say we have a probability distribution
across $X$ given by a linear combination of $n$ Gaussian
distributions over $X$, centered at the $n$ points $\mu_i$. Such a
distribution induces a probability of the set $Y$. Accordingly,
one way to estimate the distribution that generated $Y$ is to
search for the linear combination of $n$ Gaussians that maximizes
the associated probability of $Y$.

One infelicity of this procedure is that even though there are a
total of $n$ points used to parameterize the distribution, that
distribution is based solely on metric values for pairs of points
(namely the distances between $x$ and each of the $\mu_i$).  If we
have a tight multimetric rho though, we have several ways to avoid
this. For example, we could model the probability of each $Y^j$ as
a Gaussian of ${\cal{C}}\rho(Y^j, \mathcal{M})$, where $\mathcal{M}$ is
the set of $n$ $\mu_i$. We would then take the probability of $Y$
to be the product of the probabilities of the $Y^j$, as in
conventional Gaussian mixtures modeling. We could even model the
probability of $Y$ given the $n$ points $\mu_i$ as a single
Gaussian, with argument given by ${\cal{C}}\rho(Y, \mathcal{M})$.

 \item  Density estimation: In kernel density estimation, one does
not estimate the distribution over $x$ as a linear combination of
n Gaussians and then search for which such Gaussians are optimal.
Instead one estimates the distribution as a linear combination of
$|Y|$ kernel functions (e.g., Gaussians), each of which is
centered at a different one of the elements of Y. Conventionally
such kernel functions only take two arguments

 \item Classification can always be done via density estimation and
Bayes' theorem. So with (ii) and (iii) we have new ways of doing
classification.

 \item Kernel machines. Note that a multimetric is a kernel, that
is an inner product \cite{chsh00}. So any of the multimetrics
discussed above can be used for statistical analysis with
kernel-based learning algorithms. In particular, this is the case
for either for supervised or unsupervised learning with kernel
machines.
 \end{enumerate}

In particular, we can use multimetrics for regression by using
them instead of the conventional kernels of kernel machines, with
the multiplicative coefficients of each kernel (in the linear
combination of them that gives our fit to the data) set to
minimize some appropriate quadratic objective function.
\textbf{dhw: We must check all this.}

 \subsubsection{Multimetrics for probability distributions}

Recall that when using self-dissimilarity, we must statistically
estimate the collection of elements of $Q_1$ based on some data.
More generally, often there are an infinite number of elements in
such a collection, even if there is no statistical uncertainty.
(For example, this is the case if the invariances are translations
in a Euclidean space.)

To deal with these cases we will need to multimetrics over
probability distributions and density functions. Historically,
this is a fraught exercise even for simple pairs of distributions.
The most commonly used way to define a distance between two
distributions is their Kullback-Leibler distance \cite{coth91}.
This is the infinite limit log-likelihood of generating data from
one distribution but mis-attributing it to the other
distributions.

Unfortunately, the Kullback-Leibler distance between two
distributions is infinite if either distribution has points at
which it is identically zero; violates the triangle inequality; is
not even a symmetric argument of its two arguments. (It is
non-negative though, equaling zero iff its two arguments are
identical.) Some proposals have been made for overcoming some of
these shortcomings. In particular, the Jensen-Shannon distance
between two distributions - the entropy of their average minus the
average of their entropies - does not blow up and is symmetric.
However it violates the triangle inequality
\textbf{[dhw:reference]}.

The theory of multimetrics provides one class of ways to overcome
all of these shortcomings.  Perhaps the simplest is to simply view
a probability distribution as an element of a vector space $X$,
and then choose a tight multimetric rho over that vector space to
define a set multimetric. That set multimetric will then tell us
how far apart a set of probability distributions over $X$ are from
one another. To incorporate information-theoretic concerns into
the multimetric rho, it may make sense to preprocess the
distribution before applying that multimetric to it.

Example: Say that $X$ is finite. Replace each element of a
probability distribution $\pi(x)$ by $f(\pi(x)) =
-\pi(x)\ln[\pi(x)]$. This is the Shannon information of any $x$
produced by sampling the distribution $\pi$. Accordingly, in some
circumstances it makes sense to consider multimetrics over the
space of possible vectors $f(\pi)$ rather than the space of
possible $\pi$. (Note that $f$ is not invertible, and therefore
ignores certain aspects of $\pi$. In particular it is invariant
under permutation of the components of $\pi$, i.e., relabelling of
the elements of $X$.)

We can then use any convenient tight multimetric over $f(\pi)$,
and thereby define a set multimetric that tells us how far apart
from one another a set of probability distributions are. For
instance, we could take the sqrt of the average distance
multimetric. This means that
 \begin{equation*}
\rho(\pi) = \sqrt{ \sum_{x,x'} [\pi(x)\ln[\pi(x)] -
\pi(x')\ln[\pi(x')]]^2} / \sqrt{ \sum_{x,x'} 1}.
 \end{equation*}
This $\rho$ then induces a ${\cal{C}}\rho$ in the usual way.


Another approach relies on the fact that sets are just special
kinds of probability distributions. For example, any finite set
$Y$ specifies a probability distribution over $X$, namely the
fraction of times each $x \in X$ appears in $Y$. Define the
two-component function $F$ by $F(Y) = (pi, |Y|)$ where $\pi$ is
the distribution associated with $Y$.  So for example, the
distribution corresponding to the the union of two sets is just
the weighted average of the two associated probability
distributions: $F_1(Y \cup Y') = (|Y| F_1(Y) + |Y'|F_1(Y')) /
(F_2(Y) + F_2(Y'))$, and $F_2(Y \cup Y') = F_2(Y) + F_2(Y')$. The
extension to infinite $Y$ is immediate, so long as we only take
unions of sets of the same cardinality.

\textbf{dhw: What I want is to have a multimetric over
distributions evaluated for the distribution sets $\{\pi_i\}$ be a
set multimetric ${\cal{C}}\rho$ over sets $Y$ whose images under $F_1$
equal those $\{\pi_i\}$. I would also have $\rho(Y)$ defined in
terms of $\rho'(F_1(Y))$ for some appropriate multimetric $\rho'$
over the vector space containing possible distributions. This
would allow things like the Jensen-Shannon example just below. The
problem is we have to deal with the cardinalities of the sets -
the second components of F - and have to make sure all mappings we
introduce are invertible, to maintain condition (3) of
ultrametrics. I'm stuck at seeing how to do this in general.
Example: Say that we choose $\rho(\pi)$ to be the Shannon entropy
of $\pi$. It is straightforward to verify that the associated set
multimetric is the Jensen-Shannon distance. Unfortunately, Shannon
entropy is not a tight multimetric. This is reflected in the fact
that Jensen-Shannon distance violates the triangle inequality.
Example of how Shannon rho is not a tight multimetric: Have $X$
consist of 5 categories, $\{1, 2, 3, 4, 5\}$. Have $A = (123)$, $B
= (45)$, and $C = (234)$. Then $\rho(AB)$ is the entropy of a
distribution with probability 1/5 over all five elements, i.e.,
ln(5). Similarly $\rho(C) = \ln(3)$, $\rho(AC) = (1/3)\ln[6] +
(2/3)\ln[3]$, and $\rho(BC) = (3/5)\ln[5] + (2/5)\ln[5/2]$. So
tightness would require that $\ln(5) - (1/3) \ln(2) \le \ln(5) -
(2/5)\ln(2)$. This is not true. QED.}


Other multimetrics over probability distributions can be defined
directly, by modifying the type of reasoning originally employed
by Shannon. For example, rather than as a communication channel,
view each probability distribution as a repository, noisily
storing the elements of $X$. Say that we want to retrieve a
particular element of $x, x'$, in that set of repositories.
Formally, what this means is we specify a probability distribution
over the repositories, and then sample the induced distribution
over $X$, in an effort to retrieve $x'$. Our goal is to choose the
distribution over repositories that will maximize the probability
of our retrieving $x'$. Clearly the optimal choice we can make is
a distribution that is zero for all repositories except the one
with maximal $\pi(x')$.

We can next ask ``how much information-theoretic work" it took to
retrieve $x'$. The natural way to quantify this is as $-\pi^i(x')
\ln[\pi^i(x')]$, where $i$ is the repository maximizing the
probability of $x'$. The associated multimetric is directly given
by the equality $\rho(\{\pi\}) = \sum_x \max_i -\pi^i(x)
\ln[\pi^i(x)]$. (We know this is a multimetric since it is just
the sum of the coordinates of the highest point in the box
enclosing the vectors $(-\pi^i(x) \ln[\pi^i(x)])$, one such vector
for each $i$.)

Note that adding a new $p_i$ to the set that lies on top of
another one already in the set doesn't affect this measure. Note
also that having the distributions be ```spread out" - even
interior to a set of other points - will typically result in a
larger value. Note also that this

Another approach is to compare two averages. Both averages run
over all possible sequences of $x$'s and labels of one of the
$\pi$'s. Each such sequence is generated by simultaneously
sampling all the distributions.  The first of the two average is
of the Shannon information in that set of labelled sequences,
according to the actual joint distribution that produced it. (For
our purposes we can take the joint distribution to just be the
product of the $\pi$'s.) The second average is the information in
those sequences according to the ``background" version of the
joint distribution, in which all information about which
distribution generated which $x$ is averaged out. So intuitively,
this measure tells us how much information there is in the labels
of the distributions:
 \begin{equation*}
\rho(\{\pi\})  =  -\sum_{x_1, x_2, \cdots} \prod  \pi_i (x_i)
\ln\left[ \frac{\sum_{P} \prod_k \pi_k(Px_k)}{\prod_k \pi_k(x_k)}
\right]
 \end{equation*}
where the $\sum_P$ notation means a sum over all permutations of
the $\{x_j\}$ that rearranges them as the $P\{x_j\}$, and the sum
is over all such permutations.

Being a Kullback-Leibler distance, this $\rho$ equals 0 when all
the distributions are equal, and is never negative. It is not yet
known though if it is a full-blown multimetric.



Indicate a set of elements of 2^X by Z, with z^(i) indicating the
set of all subsets of X other than the i'th one, and Z^i a single such
subset.  Then define a *set multimetric*

2^rho(Z^1, Z^2, ...) = prod_i Z^i - sum_i Z^i / \sum_i 1 .

Note that the Z^i can have different cardinalities. Note also that
2^rho(x^1, x^2, ...)  - the value of 2^rho when its arguments are all
single-element subsets of X -  equals rho(x^1, x^2, ...). In other
words, 2^rho and rho agree when 2^rho's arguments are all singletons.

There is an extensive algebra governing multimetrics, tightness, and
associated set multimetrics. That algebra is described in the
appendix, where in particular it is proven that if rho is tight, then
2^rho is a multimetric. If rho is not tight though, 2^rho need need be
a multimetric.

Example: As discussed in an example above, the volume of the convex
hull of a set of points in a Euclidean space is a non-tight
multimetric. To show that the associated 2^rho is not a multimetric,
using the sets A, B, and C from that previous example, take Z^1 = A,
Z^2 = B, and Z^3 = C; it is not the case that 2^rho(Z^1, Z^2) <=
2^rho(Z^1, Z^3) + 2^rho(Z^2, Z^3) for those choices.

In this document we focus on the use of multimetrics for
self-dissimilarity analysis. However it is worth briefly mentioning
some of their myriad other possible applications. Here we illustrate
that breadth of possible uses with some examples of applying
multimetrics to sets of Euclidean vectors.

i) Clustering: Say that rho is tight, so that 2^rho is a multimetric,
and have X be a vector space. Let Z be a partition of Y into a set of
subsets. Then we can search for that partition that minimizes the
average intra-subset values of rho, E(rho(Z^i)), while maximizing the
value of 2^rho among those subsets, 2^rho(Z).

ii) Density estimation: In mixtures of Gaussians density estimation,
one is given a data set of vectors Y that were generated by IID
sampling an unknown distribution over X. Say we have a probability
distribution across X given by a linear combination of n Gaussian
distributions over X, centered at the n points mu^i. Such a
distribution induces a probability of the set Y. Accordingly, one way
to estimate the distribution that generated Y is to search for the
linear combination of n Gaussians that maximizes the associated
probability of Y.
	One infelicity of this procedure is that even though there are
a total of n points used to parameterize the distribution, that
distribution is based solely on metric values for pairs of points
(namely the distances between x and each of the mu_i).  If we have a
tight multimetric rho though, we have several ways to avoid this. For
example, we could model the probability of each Y^j as a Gaussian of
2^rho(Y^j, Mu), where Mu is the set of n mu_i. We would then take the
probability of Y to be the product of the probabilities of the Y^j, as
in conventional Gaussian mixtures modeling. We could even model the
probability of Y given the n points mu_i as a single Gaussian, with
argument given by 2^rho(Y, Mu).

iii) Density estimation: In kernel density estimation, one does not
estimate the distribution over x as a linear combination of n
Gaussians and then search for which such Gaussians are
optimal. Instead one estimates the distribution as a linear
combination of |Y| kernel functions (e.g., Gaussians), each of which
is centered at a different one of the elements of Y. Conventionally
such kernel functions only take two arguments

iv) Classification can always be done via density estimation and
Bayes' theorem. So with (ii) and (iii) we have new ways of doing
classification.

v) Kernel machines. Note that a multimetric is a kernel, that is an
inner product [christianni's book]. So any of the multimetrics
discussed above can be used for statistical analysis with kernel-based
learning algorithms. In particular, this is the case for either for
supervised or unsupervised learning with kernel machines.
	In particular, we can use multimetrics for regression by using
them instead of the conventional kernels of kernel machines, with the
multiplicative coefficients of each kernel (in the linear combination
of them that gives our fit to the data) set to minimize some
appropriate quadratic objective function. {dhw: We must check all this.}




MULTIMETRICS FOR PROBABILITY DISTRIBUTIONS/


Recall that when using self-dissimilarity, we must statistically
estimate the collection of elements of Q_1 based on some
data. More generally, often there are an infinite number of elements
in such a collection, even if there is no statistical
uncertainty. (For example, this is the case if the invariances are
translations in a Euclidean space.)

To deal with these cases we will need to multimetrics over probability
distributions and density functions. Historically, this is a fraught
exercise even for simple pairs of distributins. The most commonly used
way to define a distance between two distributions is their
Kullback-Leibler distance [dhw:reference]. This is the infinite limit
log-likelihood of generating data from one distribution but
mis-attributing it to the other distributions.

Unfortunately, the Kullback-Leibler distance between two distributions
is infinite if either distribution has points at which it is
identically zero; violates the triangle inequality; is not even a
symmetric argument of its two arguments. (It is non-negative though,
equalling zero iff its two arguments are identical.) Some proposals
have been made for overcoming some of these shortcomings. In
particular, the Jensen-Shannon distance between two distributions -
the entropy of their average minus the average of their entropies -
does not blow up and is symmetric. However it violates the triangle
inequality [dhw:reference].

The theory of multimetrics provides one class of ways to overcome all
of these shortcomings.  Perhaps the simplest is to simply view a
probability distribution as an element of a vector space X, and then
choose a tight multimetric rho over that vector space to define a set
multimetric. That set multimetric will then tell us how far apart a
set of probability distributions over X are from one another. To
incorporate information-theoretic concerns into the multimetric rho,
it may make sense to preprocess the distribution before applying that
multimetric to it.

Example: Say that X is finite. Replace each element of a probability
distribution pi(x) by f(pi(x)) = -pi(x)ln[pi(x)]. This is the Shannon
information of any x produced by sampling the distribution
pi. Accordingly, in some circumstances it makes sense to consider
multimetrics over the space of possible vectors f(pi) rather than the
space of possible pi. (Note that f is not invertible, and therefore
ignores certain aspects of pi. In particular it is invariant under
permutation of the components of pi, i.e., relabelling of the elements
of X.)
	We can then use any convenient tight multimetric over f(pi),
and thereby define a set multimetric that tells us how far apart from
one another a set of probability distributions are. For instance, we
could take the sqrt of the average distance multimetric. This means
that rho(pi) = sqrt( sum_{x,x'} [pi(x)ln[pi(x)] - pi(x')ln[pi(x')]]^2)
/ sqrt( sum_{x,x'} 1). This rho then induces a 2^rho in the usual
way. 




Another approach relies on the fact that sets are just special kinds
of probability distributions. For example, any finite set Y specifies
a probability distribution over X, namely the fraction of times each x
\in X appears in Y. Define the two-component function F by F(Y) = (pi,
|Y|) where pi is the distribution associated with Y.  So for example,
the distribution corresponding to the the union of two sets is just
the weighted average of the two associated probability distributions:
F_1(Y union Y') = (|Y| F_1(Y) + |Y'|F_1(Y')) / (F_2(Y) + F_2(Y')), and
F_2(Y union Y') = F_2(Y) + F_2(Y'). The extension to infinite Y is
immediate, so long as we only take unions of sets of the same
cardinality.

{dhw: What I want is to have a multimetric over distributions
evaluated for the distribution sets {pi_i} be a set multimetric 2^rho
over sets Y whose images under F_1 equal those {pi_i}. I would also
have rho(Y) defined in terms of rho'(F_1(Y)) for some appropriate
multimetric rho' over the vector space containing possible
distributions. This would allow things like the Jensen-Shannon example
just below. The problem is we have to deal with the cardinalities of
the sets - the second components of F - and have to make sure all
mappings we introduce are invertible, to maintain condition (3) of
ultrametrics. I'm stuck at seeing how to do this in general.

Example: Say that we choose rho(pi) to be the Shannon entropy of
pi. It is straightforward to verify that the associated set
multimetric is the Jensen-Shannon distance. Unfortunately, Shannon
entropy is not a tight multimetric. This is reflected in the fact that
Jensen-Shannon distance violates the triangle inequality.
	Example of how Shannon rho is not a tight multimetric: Have X
consist of 5 categories, {1, 2, 3, 4, 5}. Have A = (123), B = (45),
and C = (234). Then rho(AB) is the entropy of a distribution with
probability 1/5 over all five elements, i.e., ln(5). Similarly rho(C)
= ln(3), rho(AC) = (1/3)ln[6] + (2/3)ln[3], and rho(BC) = (3/5)ln[5] +
(2/5)ln[5/2]. So tightness would require that ln(5) - (1/3) ln(2) <=
ln(5) - (2/5)ln(2). This is not true. QED.
}

Other multimetrics over probability distributions can be defined
directly, by modifying the type of reasoning originally employed by
Shannon. For example, rather than as a communication channel, view
each probability distribution as a repository, noisily storing the
elements of X. Say that we want to retrieve a particular element of x,
x', in that set of repositories. Formally, what this means is we
specify a probability distribution over the repositories, and then
sample the induced distribution over X, in an effort to retrieve
x'. Our goal is to choose the distribution over repositories that will
maximize the probability of our retrieving x'. Clearly the optimal
choice we can make is a distribution that is zero for all repositories
except the one with maximial pi(x').

We can next ask ``how much information-theoretic work" it took to
retrieve x'. The natural way to quantify this is as -pi^i(x')
ln[pi^i(x')], where i is the repository maximizing the probability of
x'. The associated multimetric is directly given by the equality
rho({pi}) = sum_x max_i -pi^i(x) ln[pi^i(x)].  (We know this is a
multimetric since it is just the sum of the coordinates of the highest
point in the box enclosing the vectors (-pi^i(x) ln[pi^i(x)]), one
such vector for each i.)

Note that adding a new p_i to the set that lies on top of another one
already in the set doesn't affect this measure. Note also that having
the distributions be ```spread out" - even interior to a set of other
points - will typically result in a larger value. Note also that this 

Another approach is to compare two averages. Both averages run over
all possible sequences of x's and labels of one of the pi's. Each such
sequence is generated by simultaneously sampling all the
distributions.  The first of the two average is of the Shannon
information in that set of labelled sequences, according to the actual
joint distribution that produced it. (For our purposes we can take the
joint distribution to just be the product of the pi's.) The second
average is the information in those sequences according to the
``background" version of the joint distribution, in which all
information about which distribution generated which x is averaged
out. So intuitively, this measure tells us how much information there
is in the labels of the distributions:
 
 
rho({pi})  =  -sum            prod  pi (x ) x 
                  x , x , ...     i   i  i 
                   1   2 
 
                                   sum                 prod  pi (x' ) 
                                      PI({x } -> {x' })    k   k   k 
                                           j        j 
                               ln[-----------------------------------]
, 
                                             prod  pi (x ) 
                                                 k   k  k 
 
where the PI notation means a permutation of the {x_j} that rearranges 
them as the {x'_j}, and the sum is over all such permutations. 
 
Being a Kullback-Leiber distance, this rho equals 0 when all the
distributions are equal, and is never negative. It is not yet known
though if it is a full-blown multimetric.









APPENDIX: THE ALGEBRA OF MULTIMETRICS

i) Implications of condition (4)/

First note that by setting the B in condition (4i) to the empty set,
we get A <= AC, and by condition (4ii) we get equality only if A = A
union C. In other words, for a tight multimetric, A <= B if A is a
subset of B, with equality only if A = B (or A not contained in B).

Condition (4i) is equivalent to many other conditions:

(5) For all A, B, C, D \in 2^X where A and C are nonempty, it must be
that AB + CD <= ACD + BCD.

(6) For all Z where no Z^(i) is empty, Z^(1) <= \sum_{i>1} Z^(i) -
Z^1.

Proof: To prove the equivalence of conditions (4, 5), first expand C
in condition (4i) as CD to get AB + CD <= ACD + BCD.  The reverse
direction follows by taking D empty.

For condition (6), first note that it immediately implies condition
(4i) by taking Z = {C, A, B}. To prove the other direction, we use
induction on the number of terms in the sum in condition
(6). Condition (4i) bases the induction at two terms in the sum. Assume
condition (6) holds for any set of n separate subsets {Z^i}. To
complete the proof we must prove that condition (6) must therefore
holds for any set of n+1 separate subsets {Z'^i}.

To do this rewrite condition (6) as

	prod_{i>1} Z^i <= sum_{i>1} prod_{j \ne i} Z^j - Z^1.

Next take Z^i = union_{j \ne i, 1} Z'^j for any set of n+1 separate
subsets {Z'^i}, and Z^1 = Z'^1. So the LHS of our equation equals
prod_{i>1} Z'^i. The RHS equals

[Z'^1 Z'^3  Z'^4  ...] + [Z'^1 Z'^2 Z'^4 ... ] + ... - [Z'^1].

Collecting terms, we get Z'^(1) <= sum_{i>1} Z'^(i) - Z'^1. QED.

Condition (6) implies condition (1), as can be seen simply by taking
all subsets Z^i to be singletons. So we can define a tight multimetric
as any rho obeying conditions (2) through (4i).



ii) The relation between 2^rho and rho/

One interesting characteristic of these equivalent versions of
condition (4i) is that they must hold for all sets of all sizes
simultaneously. As a result, they imply other conditions that are
stronger than themselves. In particular, condition (6) for |Z| = 3 can
be used to establish that for any Z with cardinality >= 3,
                                    
7) Z^(1) <= sum_{i>1} Z^(i) - Z^1 +

                                sum_{i>1} [Z^(i) + (|Z| - 2) Z^i Z^1]
                                ------------------------------------ .
                                              |Z| - 1

{dhw: Not sure about this - see end of the proof.}

Proof: Condition (6) implies condition (4i). Next expand A in condition
(4i) as Z^2 Z^3 ... Z^{|Z|-1}, and take B = Z^{|Z|}, C = Z^1. Also
write down all the inequalities one gets from this one by successively
interchanging Z^{|Z|} with each of the Z^2 through Z^{|Z|-1}. Add all
the resulting inequalities and divide by |Z| - 1 to get

Z^2 Z^3 ... Z^{|Z|} + Z^1 <= 

                             sum_{i>1} [prod_{j \ne i} Z^j + Z^i Z^1]
                              -------------------------------------- .
                                             |Z| - 1

Next rewrite the righthand side as

                                
sum_{i>1} prod_{j \ne i} Z^i +

                   sum_{i>1} [Z^i Z^1 - (|Z| - 2) prod_{j \ne i} Z^i ]
                   -------------------------------------------------- .
                                       |Z| - 1

Rewriting this in terms of the Z^(i) gives condition (7). {dhw: Huh?} QED.

Making repeated use of A <= AC in the summand of the righthand side of
condition (7) implies that {dhw: Just use the last equation in the
supposed proof of condition (7) instead of condition (7).}

8)  Z^(1) <= sum_{i>1} Z^(i) - Z^1 +

                                sum_{i>1} (3 - |Z|) Z^1 Z^i
                                ---------------------------- .
                                          |Z| - 1

For any particular |Z| > 3 condition (8) is stronger than the
corresponding version of condition (6) for the same |Z|. This means
that condition (8) implies condition (6). Since condition (6) implies
condition (4i) implies condition (7) implies condition (8), we see that
conditions (4i) through (8) are all equivalent.

Condition (8) also implies that that 2^rho is a multimetric if rho is a
tight metric.

Proof: That condition (2) holds for 2^rho is immediate. The fact that A
<= AC then ensures that 2^rho is non-negative, and equals 0 if all its
arguments are the same. It also means that if 2^rho(Z) = 0, then Z^i
= prod_j Z^j for all i. By condition (4ii), this means that all Z^i
are identical. So condition (iii) holds for 2^rho.

To establish condition (1), expand 2^rho(Z^(1)) - sum_{i>1} 2^rho(Z^i) in
terms of rho, getting

Z^(1) - sum_{i>1} Z^(i) -

                 sum_{i>1} Z^i - sum_{i>1} sum_{j \ne i} Z^j] 
                 -------------------------------------------- .
                                 |Z| - 1

Rewrite the ratio as

         |Z| - 3  
  Z^1 +  -------  sum_{i>1} Z^i .
         |Z| - 1

If we use condition (8), we see that the resultant expression cannot
exceed 0. QED




OLD STUFF/

***

There are numerous other versions of the triple (condition (1),
definition of tightness, definition of $\hat{\sigma}$). In particular,
say we have some function $g : (\mathbb{R}^+)^X \times
(\mathbb{R}^+)^X \rightarrow (\mathbb{R}^+)^X$. Replace condition (1)
by $\rho(g(u, v)) \le \rho(g(u, w)) + \rho(g(v, w))$, tightness by
$\sigma(g(u, v)) + \int ds \;W(s) \sigma(s) \le \sigma(g(u, w)) +
\sigma(g(v, w))$, and the definition of $\hat{\sigma}$ by
$\hat{\sigma}(a) = \sigma(\int ds \; a(s) s) - \frac{\int ds \; a(s)
\sigma(s)}{||a||}$. Then it is still true that for a tight
$\sigma$, $\hat{\sigma}$ obeys condition (1). The foregoing chooses
$g(s, s') = s + s'$, but other choices are reasonable. For example,
one might choose $g(s, s') = \int dx \; \delta_x {\mbox{max}} (s(x),
s(x'))$.

Say we have a set $D$ of points in a Euclidean space $X$, and know the
set of all pair-wise distances between the elements of that set.  If
the Euclidean space is ${\mathbb{R}}^1$, then those distances give you
the correlation function of the elements of $D$. Accordingly, those
2-point distances give you the the original density (up to
translations). When $X$ is more than one-dimensional though, that set
of distances doesn't give you the correlation function (which takes a
vector as its argument). Accordingly, in general there is more
information in $D$, even considered only up to translations of $X$,
than is contained in the set of all pair-wise distances. 

 \item $\sigma$ is a dispersion over $U(X)$ $\Rightarrow$
$\sigma$ is a multimetric over $U(X)$.

***

 \item $\cal{C}\sigma$ is a multimetric over the unit simplex in
   $(\mathbb{R}^+)^{T(X)}$ $\Leftrightarrow$ $\cal{C}\sigma$ is a
   dispersion over $(\mathbb{R}^+)^{T(X)} - \{0\}$.

 \noindent To prove (2.6), we must show that if $\cal{C}\sigma$ is a
multimetric over the unit simplex, it is concave. To do that first
note that if $\sigma$ is concave over $T(X)$, then the second order
difference about $r$, $\sigma(r + s + t) - \sigma(r + t) - \sigma(s +
t) + \sigma(s) \le 0 \; \forall \; r, s, t \in T(X)$. So in
particular, if we define $w \equiv t, u \equiv 2r + t, v \equiv 2s +
t$, we see that so long as $\sigma(\frac{u + v}{2}) - \sigma(\frac{u +
w}{2}) - \sigma(\frac{v + w}{2}) + \sigma(w) \le 0 \; \forall \; u, v,
w \in T(X)$, $\sigma$ is concave over $T(X)$.
 \noindent Next expand ${\cal{C}}\sigma(a + b) - {\cal{C}}\sigma(a + c)
- {\cal{C}}\sigma(b + c)$ for $||a|| = ||b|| = ||c|| = 1$, which is
non-positive by hypothesis. Choose $c = \delta_{w'}$ for some $w' \in
T(X)$, and then define $u' \equiv E_a(s), v' \equiv E_b(s)$. The
result is $\sigma(\frac{u' + v'}{2}) - \sigma(\frac{u' + w'}{2}) -
\sigma(\frac{v' + w'}{2}) + \sigma(w') \le 0 \; \forall u', v', w'\in
T(X)$. Equating $u = u', v = v', w = w'$ and combining our results, we
see that under our hypothesis concerning $\cal{C}\sigma$, $\sigma$
must be concave over $T(X)$. Combining this with the first result in
(2.4) gives the claimed result. {\bf{QED}}.

However Lemma (c.6) says that it does hold for concavity gaps. This
means that not every multimetric can be written as a concavity gap of
a concave function.

***

 \item $\sigma$ is a dispersion over $U(X) \Rightarrow \sigma$ is a
multimetric over $U(X)$, where $U(X)$ be any sufficient subset of
$T(X)$ closed under addition.

 \noindent To prove (2.3) first recall that $\sigma$ is concave iff its second
difference about $w$ is nowhere-positive, i.e., iff $\forall \; u, v,
w \in T(X), \sigma(u + v + w) + \sigma(w) \le \sigma(u + w) + \sigma(v
+ w)$. (Proof sketch: To prove the forward direction first establish
that $\sigma(w + v) \ge \frac{u}{u + v}\sigma(w) +
\frac{v}{u+v}\sigma(u + v + w)$, and that $\sigma(u + w) \ge
\frac{u}{u + v}\sigma(u + v + w) +  \frac{v}{u+v}\sigma(w)$. Then add.
Take $u = v$ to prove the backward direction.)  (2.3) then arises
directly from applying (2.1) to this inequality to first remove the
$\sigma(w)$ term, and then replace the $ \sigma(u + v + w)$ with
$\sigma(u + v)$.

Note that the reverse of Lemma (2.3) does not always hold, as the
example above of a non-concave multimetric illustrates. 

***


$ $

 \noindent {\bf{Example}}: A variant of the box multimetric is where
rather than set the faces for coordinate $i$ to max$_{x : s(x) \ne 0}
\; x_i$ and min$_{x : s(x) \ne 0} \; x_i$, we set them to the $m$'th
and $n$'th percentiles of the values in the set $\{x_i : s(x) \ne
0\}$, respectively, where $n < m$.  It is straightforward to verify
that conditions (1) - (3) are obeyed for this measure. {\bf{dhw: I
don't think so anymore.}}

***

Say $T(X)$ contains the origin. The associated $\rho$ cannot be
simultaneously differentiable there and independent of the magnitude
of its argument, unless it is identically 0. In addition, it cannot be
analytic everywhere unless it is identically 0 (see the proof of
Thm. 1 below).

Now stipulate that $\rho$ be everywhere differentiable. Then we know
from condition (2) that $\rho(0) = 0$.  Given this, by taking $u$ and
$v$ to equal 0 and $w$ infinitesimal, we see that all partial
derivatives of $\rho$ are non-negative at the origin. Next set $w=0$
and take $v$ infinitesimal. Then set $v=0$ and take $w$
infinitesimal. These two scenarios establish that for any component
$x$ and any $u \in (\mathbb{R^+})^X$,

$ $

$|\frac{\partial \rho(v)}{\partial v(x)}|_{v = 0} \; \ge \; |\frac{\partial
  \rho(u)}{\partial u(x)}|$.

$ $

 \noindent This restriction is not sufficient for $\rho$ to obey
condition (1) however (as can be easily verified with $\rho(u) = \int
dx \sqrt{u(x)}$).

*** 

{\bf{dhw: The following discussion of (2.4) are of the old (2.4), not
the new one.}}

Combining Lemma (2.3) and Lemma (2.4), we see that to establish that
$\cal{C}\sigma$ is a dispersion over $(\mathbb{R}^+)^{T(X)}$ it
suffices to establish that it obeys conditions (2) and (3) over
$(\mathbb{R}^+)^{T(X)}$. Combining those results differently, we see
that when $\sigma$ obeys conditions (2) and (3), it is a strict
dispersion iff $\cal{C}\sigma$ is a dispersion over
$(\mathbb{R}^+)^{T(X)}$. We also see that so long as $\sigma$ is
strictly concave (whether or not it obeys conditions (2) and (3)),
${\cal{C}}\sigma$ is a dispersion.

$ $

***

There are many other natural assumptions to make about $\rho$. For
example, one might require that $\rho$ be invariant under rotation of
$v$ about the unit vector $(1, 1, \ldots)$ (a generalization of
invariance under permutation of the elements of $X$).

$ $

***

 \noindent {\bf{Example}}: The standard deviation multimetric is not
tight. As a trivial example of tightness, the function $\rho(s)$ that
equals $1$ if $||s|| \ge 2$ and 0 otherwise is tight and itself obeys
conditions (1) and (2), being a full multimetric if $T(X)$
contains those vectors with norm 1. It is not concave however.

$ $


{\it{Example}}: $\sigma(s) = \int dx \sqrt{s(x)}$ is strictly concave
but not tight. {\bf{dhw: You sure?}} On the other hand, say $X$ is
countable, and define ${T(X)}$ as the subset of
$(\mathbb{R}^+)^X$ of vectors $a$ such that $||a|| = 1$ and $a(s) \ne
0 \Rightarrow ||s|| = 1$. (So any $a \in {T(X)}$ is a
probability distribution over probability distributions.)  $\sigma(s)
= 1 - \sqrt{2} + \int dx [\sqrt{(1 + s(x)}) - 1]$ is both strictly
concave and tight over ${T(X)}$. In other words,
${\cal{C}}\sigma$ is a multimetric over ${T(X)}$. $\sigma$ is
also a multimetric over $X$.

***

There is an extensive algebra of tight concave functions, arising from
substitutions for the vectors in the definition of tight concave
functions. A trivial example is $\rho(u + v) + \rho(s + t) \le \rho(u
+ s + t) + \rho(v + s + t)$. Other less trivial examples are presented
in the appendix.

***

{\bf{dhw}}: What about the other examples presented above of
multimetrics? What about $S(u / ||u||)$ where $S$ is the entropy? What
about the square root of this - how does that relate to the
Jensen-Shannon divergence and its violation of the triangle
inequality? How can we classify the functional forms of all functions
obeying condition (1)? Of all tight functions?



{\bf{Just after the end(document) command in the latex of this
document is the pre-latexing notes on the algebra of multimetrics and
tightness.}}

***


Prove that if the leading eigenvalue of the Hessian of $\sigma$ is
$k$, then $f({\cal{C}}\sigma)$ is concave so long as $|f''| \le
...$. Apply this to the JS divergence to see why it isn't a metric but
its square root is, and similarly for why the variance isn't a metric
but the standard deviation is.

Do the dispersion results, together with the fact that JS is not a
metric, mean that entropy can't be embedded in a concave function?

Can (2.3) be extended to hold for $T'(T(X)) = (\mathbb{R}^+)^{T(X)}$?

Can any (2-argument) metric be embedded in a dispersion? I.e., do the
set of dispersions (over)parameterize the set of metrics?

What are the general implications of all of this work on
generalizations of topological metrics for tensor metrics?

How do the dispersion results recommend one form a metric over 
probabilities?


***

Note that this multimetric is translation-invariant over $X$, i.e.,
$\rho(s(x)) = \rho(s(x + a))$ for any $s \in T(X)$, $a \in X$. This
suggests we can define a ``multinorm" based on this multimetric. The
idea is to proceed by analogy with how one can exploit translation
invariance to construct a conventional (two-argument) norm over a
vector space from a conventional metric for that space.

For any $u \in T(X)$, write ${\hat{u}}$ to indicate the set of all $s
\in {\cal{R}}^X$ such that we can write $u(x) = \int dx' dx''
s(x')s(x'') \delta(x' - x'' - x)$, where if $s$ contains delta
functions the integral is implicitly restricted to not allow $x'$ to
equal $x''$. Intuitively, ${\hat{u}}$ is the set of all $s$ such that
$u$ can be viewed as the difference vector connecting the parts of
$s$. Let ${\hat{T}}(X)$ be those such $u$ meeting two
conditions. First, ${\hat{u}}$ must be non-empty for $u$ to be in
${\hat{T}}(X)$ (i.e., there must be some vector $s$ ``whose parts are
connected" by $u$). Second, all of the elements of ${\hat{u}}$ must be
$X$-translations of one another (i.e., if $s^1$ and $s^2$ are both in
such a ${\hat{u}}$, then there is some $a$ such that $s^1(x) = s^2(x +
a) \; \forall x$). Then we define the {\bf{multinorm}} of any $u \in
{\hat{T}}(X)$ as $\rho({\hat{u}})$.

As an example, if $N$ = 3, and $u = \delta_{1, 1, 2} + \delta_{-1, 5,
3} + \delta_{0, 6, 5}$, then a member of ${\hat{u}}$ is $\delta_{1, 1,
1} + \delta_{2, 2, 3} + \delta_{1, 7, 6}$, since the vectors in the
support of $u$ give the differences between the vectors in the support
of ${\hat{u}}$ (e.g, $(2, 2, 3) - (1, 1, 1) = (1, 1, 2)$). So the
multinorm of $u$ is the square root of the average squared Euclidean
distance among the three vectors $(1, 1, 1), (2, 2, 3)$, and $(1, 7,
6)$. Note that if $u$ had been a sum of only two delta functions, then
its norm would reduce to the Euclidean distance between (the supports
of) those two delta functions, exactly like the conventional Euclidean
norm.

Just as the triangle inequality of a conventional metric implies a
triangle inequality for the norm it induces, so does the triangle
inequality of a multimetric implies a triangle inequality for the
multinorm it induces...

***

Consider Ex. 2, which has $X$ consist
of $N$ separate elements, so that an element of $T(X)$ is a
probability distribution over $X$. Say those elements of $X$ are
ordered, and that $N$ is a power of 2. So we can express any $x \in X$
as a sequence of $N$ bits. Say we have a multimetric over
${\mathbb{R}}^{\mathbb{B}}$, $\rho_{\mathbb{B}}$. So the argument of
$\rho_{\mathbb{B}}$ is a pair of real numbers. Let
 \begin{eqnarray*}
\rho_1(u) &=& \rho_{\mathbb{B}}[\int dx_1 \ldots dx_{N/2} \;u(x), \int
dx_{N/2+1} \ldots dx_{N} \;u(x)] ; \\
\rho_2(u) &=& \rho_{\mathbb{B}}[\int dx_1 d\ldots dx_{N/4} \;u(x) + \int dx_{N/2+1}
\ldots dx_{3N/4} \;u(x), \\
&& \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \int dx_{N/4+1} d\ldots dx_{N/2} \;u(x) + \int dx_{3N/4+1}
\ldots dx_{N} \;u(x)] ; \\
&\ldots&
 \end{eqnarray*}
for a total of $M \le N$ components of $\rho$.

For a component-wise linear ordering over ${\mathbb{R}}^M$, this
$\rho$ obeys conditions (1) and (2) of an $M$-dimensional
multimetric. Each successive component of $\rho(u)$, $\rho_i(u)$, is
$\rho_{\mathbb{B}}$ applied to the marginal distribution of $u$ over
the $i$'th bit of $X$.

***

Recall how the def. of inner product gives that $\sqrt{(a - b) \cdot
(a -b)}$ is a metric.  Combine that with Bill's statement that
$\exp^{metric}$ is always a kernel, to put in the ``future work'' list
the extension of the notion of dispersions and the like to inner
products. {\bf{dhw: Er, isn't Bill's statement for a tensor metric,
not a topological one?}}

***

\subsubsection{Multimetrics for probability distributions}

Recall that when using self-dissimilarity, we must statistically
estimate the collection of elements of $Q_1$ based on some data.
More generally, often there are an infinite number of elements in
such a collection, even if there is no statistical uncertainty.
(For example, this is the case if the invariances are translations
in a Euclidean space.)

To deal with these cases we will need to use multimetrics over
probability distributions and pdf's. Historically, even constructing
metrics over such spaces is a fraught exercise. For example, the most
commonly used way to define a distance between two distributions is
their Kullback-Leibler distance \cite{coth91}. This is the infinite
limit log-likelihood of generating data from one distribution but
mis-attributing it to the other distributions.  Unfortunately, the
Kullback-Leibler distance between two distributions is infinite if
either distribution has points at which it is identically zero;
violates the triangle inequality; is not even a symmetric argument of
its two arguments. (It is non-negative though, equalling zero iff its
two arguments are identical.) Some proposals have been made for
overcoming some of these shortcomings. In particular, the
Jensen-Shannon distance between two distributions - the entropy of
their average minus the average of their entropies - does not blow up
and is symmetric.  However it violates the triangle inequality
\textbf{[dhw:reference]}.

One way to construct a multimetric over probability distributions is
to cast any such distribution as a Euclidean vector and then use one
of the multimetrics discussed above for such vectors. In particular,
we can use the multimetric of the sum of the lengths of the edges of
the smallest axis-parallel box enclosing any set of such probability
distribution vectors. 

Other multimetrics over probability distributions can be defined
by modifying the type of reasoning originally employed by Shannon.
For example, rather than as a communication channel, view each
probability distribution as a repository, noisily storing the
elements of $X$. Say that we want to retrieve a particular element
of $x, x'$, in that set of repositories.  Formally, what this
means is we specify a probability distribution over the
repositories, and then sample the induced distribution over $X$,
in an effort to retrieve $x'$. Our goal is to choose the
distribution over repositories that will maximize the probability
of our retrieving $x'$. Clearly the optimal choice we can make is
a distribution that is zero for all repositories except the one
with maximial $\pi(x')$.

We can next ask ``how much information-theoretic work" it took to
retrieve $x'$. The natural way to quantify this is as $-\pi^i(x')
\ln[\pi^i(x')]$, where $i$ is the repository maximizing the
probability of $x'$. The associated multimetric is directly given
by the equality $\rho(\{\pi\}) = \sum_x \max_i [-\pi^i(x)
\ln[\pi^i(x)]]$. (We know this is a multimetric since it is just
the sum of the coordinates of the highest point in the box
enclosing the vectors $(-\pi^i(x) \ln[\pi^i(x)])$, one such vector
for each $i$.)

Note that adding a new $p_i$ to the set that lies on top of
another one already in the set doesn't affect this measure. Note
also that having the distributions be ```spread out" - even
interior to a set of other points - will typically result in a
larger value.

Another approach is to compare two averages. Both averages run
over all possible sequences of $x$'s and labels of one of the
$\pi$'s. Each such sequence is generated by simultaneously
sampling all the distributions.  The first of the two average is
of the Shannon information in that set of labelled sequences,
according to the actual joint distribution that produced it. (For
our purposes we can take the joint distribution to just be the
product of the $\pi$'s.) The second average is the information in
those sequences according to the ``background" version of the
joint distribution, in which all information about which
distribution generated which $x$ is averaged out. So intuitively,
this measure tells us how much information there is in the labels
of the distributions:
 \begin{equation*}
\rho(\{\pi\})  =  -\sum_{x_1, x_2, \cdots} \prod  \pi_i (x_i)
\ln\left[ \frac{\sum_{P} \prod_k \pi_k(Px_k)}{\prod_k \pi_k(x_k)}
\right]
 \end{equation*}
where the $\sum_P$ notation means a sum over all permutations of
the $\{x_j\}$ that rearranges them as the $P\{x_j\}$, and the sum
is over all such permutations.

Being a Kullback-Leiber distance, this $\rho$ equals 0 when all
the distributions are equal, and is never negative. It is not yet
known though if it is a full-blown multimetric.

***

 \item Clustering: Define $I(u, X^0)$ for any subset $X^0 \subseteq X$ and
$u \in (\mathbb{R}^+)^X$ as the vector that equals $u(x)$ for
components $x \in X^0$, and equals 0 for all other components.  Then
given a $u \in (\mathbb{R}^+)^X$, we can search for that partition of
$X$, $\{X^i\}$, that minimizes the average intra-subset values of
$\rho$, $\frac{\sum_i \rho(I(u, X^i))}{\sum_i 1}$, while maximizing
the value of ${\cal{C}}\rho$ among those subsets, ${\cal{C}}\rho(\sum_i
\delta_{I(u,X^i)})$.


nlin0404032.extracted_bib
\begin{thebibliography}{10}

\bibitem{chsh00}
Nello Christianini and John Shawe-Taylor.
\newblock {\em An introduction to support vector machines and other
  kernel-based learning methods}.
\newblock Cambridge University Press, 2000.

\bibitem{duha00}
R.~O. Duda, P.~E. Hart, and D.~G. Stork.
\newblock {\em Pattern Classification (2nd ed.)}.
\newblock Wiley and Sons, 2000.

\bibitem{futo04}
Bent Fuglede and Flemming Topsoe.
\newblock Jensen-shannon divergence and hilbert space embedding.
\newblock Submitted to ISIT2004, 2004.

\bibitem{hall99}
M.~Hall.
\newblock Universal geometric approach to uncertainty, entropy, and
  information.
\newblock {\em Physical Review A}, 59:2602, 1999.

\bibitem{judg04}
George Judge.
\newblock Semiparametric moment based estimation for binary response models.
\newblock RMBE-DE1-4-2-04.doc, 2004.

\bibitem{lin91}
Jianhua Lin.
\newblock Divergence measures based on the shannon entropy.
\newblock {\em IEEE Trans. Info. Theory}, 37(1):145--151, 1991.

\bibitem{osva03}
Ferdinand Osterreicher and Igor Vajda.
\newblock A new class of metric divergiences on probability spaces and its
  applicability in statistics.
\newblock {\em Ann. Inst. Statist. Math.}, 55(3):639--653, 2003.

\bibitem{tops02}
Flemming Topsoe.
\newblock Inequalities for the jensen-shannon divergence.
\newblock 2002.
\newblock unpublished.

\bibitem{woma04a}
David~H. Wolpert and William Macready.
\newblock Self-dissimilarity as a high dimensional complexity measure.
\newblock In {\em Proceedings of the International Conference on Complex
  Systems, 2004}, 2004.
\newblock in press.

\bibitem{woma04b}
David~H. Wolpert and William Macready.
\newblock Self-dissimilarity as a high dimensional complexity measure.
\newblock http://xxx..., 2004.

\end{thebibliography}