\section{EM Clustering}
\label{appendix:EM-clustering}

Clustering using finite mixture models is a well-known method and has been used
for a long time in pattern recognition \cite{duda,fuku90,jain88} and statistics
\cite{mixture,titterington,fraley}.
In this model, one assumes that the data is generated
from a mixture of component density functions, in which each component
density function represents a cluster.  The probability distribution
function of the data has the following form:
\begin{equation}
f(X_{i}|\Phi) =
\sum_{j=1}^{k} \pi_{j} f_{j}(X_{i}|\theta_{j}) 
\end{equation}
where
$f_{j}(X_{i}|\theta_{j})$ is the probability density function for
class $j$, $\pi_{j}$ is the mixing proportion of class $j$ (prior
probability of class $j$), $k$ is the number of clusters, $X_{i}$ is a
$d$-dimensional random data vector, $\theta_{j}$ is the set of
parameters for class $j$, $\Phi = (\pi, \theta)$ is the set of all
parameters and $f(X_{i}|\Phi)$ is the probability density function of
our observed data point $X_{i}$ given the parameters $\Phi$.  Since the
$\pi_{j}$'s are prior probabilities, they are subject to the following
constraints: $\pi_{j} \geq 0$ and $\sum_{j=1}^{k}\pi_{j}=1$.

The $X_{i}$'s, where $i=1 \ldots N$, are the data vectors we are trying to cluster,
and $N$ is the number of samples.
To cluster $X_{i}$, we need to estimate the parameters, $\Phi$.
One method for estimating $\Phi$ is
to find $\Phi$ that maximizes the log-likelihood, $\log \,
f(X|\Phi)=\sum_{i=1}^{N} \log \, f(X_{i}|\Phi)$.  To compute
$f(X_{i}|\Phi)$, we need to know the cluster (the missing data) to which 
$X_{i}$ (the observed data) belongs.
We apply the EM algorithm, which provides us with ``soft-clustering'' information; i.e.,
a data point $X_{i}$ can belong to more than one cluster (weighted by its probability to 
belong to each cluster).
The expectation-maximization (EM) algorithm, introduced in some generality by 
Dempster, Laird and Rubin in 1977\nocite{DLR}, is an iterative approximation algorithm 
for computing the maximum likelihood (ML) estimate of missing data problems. 

Going through the derivation of applying EM on our Gaussian mixture model, 
we obtain the following EM update equations \cite{wolfe}:
\begin{equation}
E[z_{ij}]^{(t)} = p(z_{ij}=1|X,\Phi^{(t)}) = \frac{f_{j}(X_{i}|\Phi_{j}^{(t)}) \,
\pi_{j}^{(t)}}{\sum_{s=1}^{k} \, f_{s}(X_{i}|\Phi_{s}^{(t)}) \, \pi_{s}^{(t)}}
\label{eqn:EZ}
\end{equation}

\begin{center}
\begin{eqnarray}
\label{eqn:EMupdate0}
\pi_{j}^{(t+1)}  & = & \frac{1}{N} \, \sum_{i=1}^{N} \, E[z_{ij}]^{(t)} \\
\mu_{j}^{(t+1)}  & = & \frac{1}{N\pi_{j}^{(t+1)}} \, \sum_{i=1}^{N} \, E[z_{ij}]^{(t)}
\, X_{i} \\ 
\Sigma_{j}^{(t+1)} & = & \frac{1}{N\pi_{j}^{(t+1)}} \, \sum_{i=1}^{N} \, E[z_{ij}]^{(t)}
 \, (X_{i}-\mu_{j}^{(t+1)})(X_{i}-\mu_{j}^{(t+1)})^{T} 
\label{eqn:EMupdate}
\end{eqnarray}
\end{center}
where $E[z_{ij}]$ is the 
probability that $X_{i}$
 belongs to cluster $j$ given our current parameters and $X_{i}$,
$\sum_{i=1}^{N} \, E[z_{ij}]$ is the estimated number of data points in class $j$,
and the superscript $t$ refers to the iteration.

\section{Additional Proofs on ML's Bias with Dimension}
\label{appen:MLsoftcase}

%\newtheorem{lemma}{Lemma}
\setcounter{theorem}{0}
\newcounter{corollary}
\setcounter{corollary}{0}

In this appendix, we prove Theorem \ref{theorem:MLgeneral} and
Corollary \ref{cor:MLsoftQ}
which state the 
condition that needs to be satisfied for the maximum likelihood of feature subset $A$, $ML(\Phi_{A})$, to be greater
than or equal to the maximum likelihood of feature subset $B$, $ML(\Phi_{B})$. 
To prove these results, we first define the maximum likelihood criterion for a mixture of
Gaussians, prove Lemma \ref{lemma:expQ2}
which derives a simplified form of $\exp(Q(\Phi,\Phi))$ for a finite Gaussian mixture,
and Lemma \ref{lemma:MLsoftQ} which states the condition that needs to be satisfied for the
complete expected data log-likelihood $Q(\cdot)$ function given the observed data and the
parameter estimates in feature subset $A$, $Q(\Phi_{A},\Phi_{A})$, to be greater
than or equal to the $Q(\cdot)$ function of feature subset $B$, $Q(\Phi_{B},\Phi_{B})$.



The maximum likelihood of our data, $X$, is
\begin{equation}
ML = \max_{\Phi} (f(X|\Phi)) = \max_{\Phi} \prod_{i=1}^{N}  (\sum_{j=1}^{k} \pi_{j} f_{j}(X_{i}|\theta_{j}))
\label{eqn:ML}
\end{equation}
where $f_{j}(X_{i}|\theta_{j})$ is the probability density function for
class $j$, $\pi_{j}$ is the mixing proportion of class $j$ (prior
probability of class $j$), $N$ is the number of data points, 
$k$ is the number of clusters, $X_{i}$ is a
$d$-dimensional random data vector, $\theta_{j}$ is the set of
parameters for class $j$, $\Phi = (\pi, \theta)$ is the set of all
parameters and $f(X|\Phi)$ is the probability density function of
our observed data $X = X_{1}, X_{2}, \ldots X_{N}$ given the parameters $\Phi$.
We choose the feature subset that maximizes this criterion. 

\begin{lemma}
For a finite mixture of Gaussians, 
\begin{eqnarray}
\exp(Q(\Phi,\Phi)) & = & \prod_{j=1}^{K} \pi_{j}^{N \pi_{j} }
                        \frac{1}{ (2\pi)^{\frac{dN\pi_{j}}{2}} |\Sigma_{j}|^{\frac{N\pi_{j}}{2}} }
                        e^{ -\frac{1}{2} d N \pi_{j}} \nonumber
\end{eqnarray}
\noindent where $x_{i}$, $i=1 \ldots N$, are the $N$ observed data points,
$z_{ij}$ is the missing variable equal to one if $x_{i}$ belongs to cluster $j$ and zero otherwise,
$\pi_{j}$ is the mixture proportion, $\mu_{j}$ is the mean and $\Sigma_{j}$ is the covariance matrix
of each Gaussian cluster respectively, and $\Phi=(\pi,\mu,\Sigma)$ is the set of all estimated parameters.

\label{lemma:expQ2}
\end{lemma}
{\bf Proof:}

\begin{eqnarray}
Q(\Phi,\Phi) & \stackrel{\triangle}{=} &  E_{z|x}[\log f(x,z|\Phi)|x,\Phi] \nonumber \\
                   & = &  E_{z|x}[\log f(x|z,\Phi)|x,\Phi] + E_{z|x}[\log f(z|\Phi)|x,\Phi] \nonumber \\
                   & = &  \sum_{i=1}^{N} \sum_{j=1}^{K} p(z_{ij}=1|x,\Phi) \log f_{j}(x_{i}|\phi_{j}) 
                        + \sum_{i=1}^{N} \sum_{j=1}^{K} p(z_{ij}=1|x,\Phi) \log \pi_{j} \nonumber \\
                   & = &  \sum_{i=1}^{N} \sum_{j=1}^{K} p(z_{ij}=1|x,\Phi) \log (\pi_{j} f_{j}(x_{i}|\phi_{j}) ) \\ 
                   & = &  \sum_{i=1}^{N} \sum_{j=1}^{K} E[z_{ij}] \log (\pi_{j} f_{j}(x_{i}|\phi_{j}) )  \nonumber \\ 
\exp(Q(\Phi,\Phi)) & = & \prod_{i=1}^{N} \prod_{j=1}^{K} (\pi_{j} f_{j}(x_{i}|\phi_{j}))^{E[z_{ij}]} 
\label{eqn:expQ}
\end{eqnarray}

Substituting our parameter estimates to Equation \ref{eqn:expQ} and sample data $x_{i}$'s,
\begin{eqnarray}
\exp(Q(\Phi,\Phi)) & = & \prod_{j=1}^{K} \pi_{j}^{\sum_{i=1}^{N} E[z_{ij}]} 
                        \prod_{i=1}^{N} ( \frac{1}{ (2\pi)^{\frac{d}{2}} |\Sigma_{j}|^{\frac{1}{2}} }
                        e^{ -\frac{1}{2} (x_{i}-\mu_{j})^{T} \Sigma_{j}^{-1} (x_{i}-\mu_{j}) }  )^{E[z_{ij}]} \nonumber \\
                  & = & \prod_{j=1}^{K} \pi_{j}^{N \pi_{j} } 
                        \frac{1}{ (2\pi)^{\frac{dN\pi_{j}}{2}} |\Sigma_{j}|^{\frac{N\pi_{j}}{2}} }      
                        e^{ -\frac{1}{2} \sum_{i=1}^{N} E[z_{ij}] (x_{i}-\mu_{j})^{T} \Sigma_{j}^{-1} (x_{i}-\mu_{j}) } 
\end{eqnarray}

Simplifiying the exponent of $e$ we obtain,
\begin{flushleft}
\[-\frac{1}{2} \sum_{i=1}^{N} E[z_{ij}] (x_{i}-\mu_{j})^{T} \Sigma_{j}^{-1} (x_{i}-\mu_{j}) \] 
\end{flushleft}
\begin{eqnarray}
        & = &  -\frac{1}{2} \sum_{i=1}^{N} E[z_{ij}] tr( (x_{i}-\mu_{j})^{T} \Sigma_{j}^{-1} (x_{i}-\mu_{j}) ) \nonumber \\
        & = &  -\frac{1}{2} \sum_{i=1}^{N} E[z_{ij}] tr( \Sigma_{j}^{-1} (x_{i}-\mu_{j}) (x_{i}-\mu_{j})^{T} ) \nonumber \\
        & = &  -\frac{1}{2} tr( \Sigma_{j}^{-1} ( \sum_{i=1}^{N} E[z_{ij}] (x_{i}-\mu_{j}) (x_{i}-\mu_{j})^{T} ) ) \nonumber \\
 & & \mbox{Adding and subtracting $\overline{x_{j}}$, where} \ \overline{x_{j}} = \frac{1}{N\pi_{j}} \sum_{i=1}^{N} E[z_{ij}] x_{i},  \nonumber \\ 
        & = &  -\frac{1}{2} tr( \Sigma_{j}^{-1} ( \sum_{i=1}^{N} E[z_{ij}] (x_{i}- \overline{x_{j}} + 
                \overline{x_{j}} - \mu_{j}) (x_{i}- \overline{x_{j}} + \overline{x_{j}} - \mu_{j})^{T} ) ) \nonumber \\
 & & \mbox{Cancelling cross-product terms,} \nonumber \\
        & = &  -\frac{1}{2} tr( \Sigma_{j}^{-1} ( \sum_{i=1}^{N} E[z_{ij}] (x_{i}-\overline{x_{j}}) (x_{i}-\overline{x_{j}})^{T}
                + \sum_{i=1}^{N} E[z_{ij}] (\overline{x_{j}}- \mu_{j}) (\overline{x_{j}} - \mu_{j})^{T} ) ) \nonumber \\ 
 & & \mbox{Substituting the parameter estimates (Equations \ref{eqn:EMupdate0}-\ref{eqn:EMupdate}),} \nonumber \\
        & = &  -\frac{1}{2} tr( \Sigma_{j}^{-1} \Sigma_{j} N \pi_{j} ) \nonumber \\
        & = &  -\frac{1}{2} d N \pi_{j} 
\end{eqnarray}

Thus, $\exp(Q(\Phi,\Phi))$ can be expressed as
\begin{eqnarray}
\exp(Q(\Phi,\Phi)) & = & \prod_{j=1}^{K} \pi_{j}^{N \pi_{j} } 
                        \frac{1}{ (2\pi)^{\frac{dN\pi_{j}}{2}} |\Sigma_{j}|^{\frac{N\pi_{j}}{2}} }      
                        e^{ -\frac{1}{2} d N \pi_{j}} \ \ \ \ \ \ \ \ \fbox{} \nonumber
\end{eqnarray}

\begin{lemma}
Assuming identical clustering assignments
for feature subsets $A$ and $B$ with dimensions $d_{B} \geq d_{A}$,
$Q(\Phi_{A},\Phi_{A}) \geq
Q(\Phi_{B},\Phi_{B})$  iff
\begin{eqnarray}
\prod_{j=1}^{k} \left( \frac{|\Sigma_{B}|_{j}}{|\Sigma_{A}|_{j}} \right)^{\pi_{j}} & \geq & \frac{1}{ (2\pi e)^{(d_{B}-d_{A})} } \nonumber
\end{eqnarray}
\label{lemma:MLsoftQ}
\end{lemma}
{\bf Proof:}


Applying Lemma \ref{lemma:expQ2}, and
assuming subsets $A$ and $B$ have equal clustering assignments, 
\begin{eqnarray}
\frac{\exp(Q(\Phi_{A},\Phi_{A}))}{\exp(Q(\Phi_{B},\Phi_{B}))} & \geq & 1 \nonumber \\
\frac{\prod_{j=1}^{k} \pi_{j}^{N\pi_{j}} \frac{1}{(2\pi e)^{\frac{d_{A}N\pi_{j}}{2}}} \frac{1}{|\Sigma_{A}|_{j}^{\frac{N\pi_{j}}{2}}}} {\prod_{j=1}^{k} \pi_{j}^{N\pi_{j}} \frac{1}{(2\pi e)^{\frac{(d_{B})N\pi_{j}}{2}}} \frac{1}{|\Sigma_{B}|_{j}^{\frac{N\pi_{j}}{2}} } } & \geq & 1 
\label{eqn:soft}
\end{eqnarray}

Given $d_{B} \geq d_{A}$, without loss of generality and cancelling common terms,
\begin{eqnarray}
\prod_{j=1}^{k} \left( \frac{|\Sigma_{B}|_{j}}{|\Sigma_{A}|_{j}} \right)^{\frac{N \pi_{j}}{2}} (2\pi e)^{\frac{(d_{B}-d_{A})N \pi_{j}}{2}} & \geq & 1 \nonumber \\
\prod_{j=1}^{k} \left( \frac{|\Sigma_{B}|_{j}}{|\Sigma_{A}|_{j}} \right)^{\pi_{j}} (2\pi e)^{(d_{B}-d_{A}) \pi_{j}} & \geq & 1 \nonumber \\
(2\pi e)^{(d_{B}-d_{A}) \sum_{j=1}^{k} \pi_{j}} \prod_{j=1}^{k} \left( \frac{|\Sigma_{B}|_{j}}{|\Sigma_{A}|_{j}} \right)^{\pi_{j}} & \geq & 1 \nonumber \\
\prod_{j=1}^{k} \left( \frac{|\Sigma_{B}|_{j}}{|\Sigma_{A}|_{j}} \right)^{\pi_{j}} & \geq & \frac{1}{ (2\pi e)^{(d_{B}-d_{A})} } \ \ \ \ \ \ \ \ \fbox{} \nonumber  
\end{eqnarray}

\begin{theorem}
For a finite multivariate Gaussian mixture, assuming identical clustering assignments
for feature subsets $A$ and $B$ with dimensions $d_{B} \geq d_{A}$,
$ML(\Phi_{A}) \geq ML(\Phi_{B})$  iff
\begin{eqnarray}
\prod_{j=1}^{k} \left( \frac{|\Sigma_{B}|_{j}}{|\Sigma_{A}|_{j}} \right)^{\pi_{j}} & \geq & \frac{1}{ (2\pi e)^{(d_{B
}-d_{A})} } \nonumber
\end{eqnarray}
\label{theorem:MLgeneral}
\end{theorem}
{\bf Proof:}

The log-likelihood, $\log L(\Phi^{'}) = \log f(x|\Phi^{'})$.

\begin{center}
\[\begin{array}{rcccc}
\log L(\Phi^{'}) & = & E_{z|x}[\log f(x,z|\Phi^{'})|x,\Phi] & - & E_{z|x}[\log f(z|x,\Phi^{'})|x,\Phi] \nonumber \\
                 & \stackrel{\triangle}{=} & Q(\Phi^{'},\Phi)  & + & H(\Phi^{'},\Phi)
\end{array}\]
\end{center}

\begin{eqnarray}
H(\Phi,\Phi) & = & - E[\log f(z|x,\Phi)|x,\Phi] \nonumber \\ 
             & = & - \sum_{i=1}^{N} \sum_{j=1}^{k} p(z_{ij}=1|x_{i},\phi_{j}) \log p(z_{ij}=1|x_{i},\phi_{j}) \nonumber \\
             & = & - \sum_{i=1}^{N} \sum_{j=1}^{k} E[z_{ij}] \log E[z_{ij}]
\label{eqn:H} 
\end{eqnarray}


Since the identical clustering assignment assumption means that $E[z_{ij}]$ for feature set $A$ is
equal to $E[z_{ij}]$ for feature set $B$,
\[H(\Phi_{A},\Phi_{A}) = H(\Phi_{B},\Phi_{B}) \]
 
Thus,
\[\frac{ML(\Phi_{A})}{ML(\Phi_{B})} = \frac{\exp(Q(\Phi_{A},\Phi_{A}))}{\exp(Q(\Phi_{B},\Phi_{B}))}\]

For a finite Gaussian mixture,
from Lemma \ref{lemma:MLsoftQ},
$\frac{ML(\Phi_{A})}{ML(\Phi_{B})} \geq 1$ iff
\begin{eqnarray}
\prod_{j=1}^{k} \left( \frac{|\Sigma_{B}|_{j}}{|\Sigma_{A}|_{j}} \right)^{\pi_{j}} & \geq & \frac{1}{ (2\pi e)^{(d_{B}-d_{A})} } \ \ \ \ \ \ \ \ \fbox{} \nonumber
\end{eqnarray}

\begin{corollary}
For a finite multivariate Gaussian mixture, assuming identical clustering assignments
for feature subsets $X$ and $(X,Y)$, where $X$ and $Y$ are disjoint,
$ML(\Phi_{X}) \geq ML(\Phi_{XY})$  iff
\begin{eqnarray}
\prod_{j=1}^{k} |\Sigma_{YY} - \Sigma_{YX} \Sigma_{XX}^{-1} \Sigma_{XY}|_{j}^{\pi_{j}} & \geq & \frac{1}{(2\pi e)^{d_{Y}}} \nonumber
\end{eqnarray}
\label{cor:MLsoftQ}
\end{corollary}
{\bf Proof:}

Applying Theorem \ref{theorem:MLgeneral}, and if 
we let $A$ be the marginal feature vector $X$ with dimension $d_{X}$ and $B$ be the joint
feature vector $(X,Y)$ with dimension $d_{X} + d_{Y}$ (where subsets $X$ and $Y$ are disjoint),
then
the maximum likelihood of $X$ is greater than or equal to the maximum likelihood
of $(X,Y)$ iff
\begin{eqnarray}
\frac{ML(\Phi_{X})}{ML(\Phi_{XY})} & \geq & 1 \nonumber \\
(2\pi e)^{d_{Y}} \prod_{j=1}^{k} \left( \frac{\left| \begin{array}{cc}
\Sigma_{XX} & \Sigma_{XY} \\
\Sigma_{YX} & \Sigma_{YY} \\
\end{array} \right|_{j} }
{|\Sigma_{XX}|_{j}} \right)^{\pi_{j}}
& \geq & 1 \nonumber
\end{eqnarray}

Exercise 4.11 of \cite{multivariatebook} shows that for any square matrix $A$,
\begin{center}
\[\begin{array}{rll}
& A = \left[ \begin{array}{cc}
A_{11} & A_{12} \\
A_{21} & A_{22} \end{array} \right] & \\
|A| &= \, |A_{22}||A_{11} - A_{12} A_{22}^{-1} A_{21}| & \mbox{for $|A_{22}| \neq 0$} \\
    &= \, |A_{11}||A_{22} - A_{21} A_{11}^{-1} A_{12}| & \mbox{for $|A_{11}| \neq 0$} \\
\end{array}\]
\end{center}
Thus,
\begin{center}
\begin{eqnarray}
(2\pi e)^{d_{Y}} \prod_{j=1}^{k} \left( \frac{1}{|\Sigma_{XX}|_{j}} |\Sigma_{XX}|_{j} |\Sigma_{YY} - \Sigma_{YX} \Sigma_{XX}^{-1} \Sigma_{XY}|_{j} \right)^{\pi_{j}}  & \geq & 1  \nonumber \\
\prod_{j=1}^{k} |\Sigma_{YY} - \Sigma_{YX} \Sigma_{XX}^{-1} \Sigma_{XY}|_{j}^{\pi_{j}} & \geq & \frac{1}{(2\pi e)^{d_{Y}}} \nonumber \ \ \ \ \ \ \ \ \fbox{}
\end{eqnarray}
\end{center}
 

Now, what do these results mean?
One can compute the maximum log-likelihood, $\log$ ML efficiently
as $Q(\Phi,\Phi) + H(\Phi,\Phi)$ by applying Lemma \ref{lemma:expQ2} and Equation \ref{eqn:H}.
Lemma \ref{lemma:expQ2} shows that the ML criterion prefers
low covariance clusters.  Equation \ref{eqn:H} shows that the ML criterion penalizes increase
in cluster entropy.
Theorem \ref{theorem:MLgeneral} and Corollary \ref{cor:MLsoftQ} reveal the dependencies of
comparing the ML criterion for different dimensions.
Note that the left hand side term of Corollary \ref{cor:MLsoftQ} is the determinant of
the covariance of $f(Y|X)$.  It is the covariance of $Y$ minus the correlation of $Y$ and $X$.
For a criterion measure to be unbiased with respect to dimension, the criterion value should be the
same for the different subsets when the cluster assignments are equal (and should not be dependent on the
dimension).  But, in this case, ML increases when the additional feature has small variance and
decreases when the additional feature has large variance.

\vfill
\pagebreak

