node1.html

高斯混合模型算法

buttons to switch between 2D and 3D. Use the mouse to rotate the plot
(must be enabled in <TT>Tools</TT> menu: <TT>Rotate 3D</TT>, or by the
<!-- MATH
 $\circlearrowleft$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="14" HEIGHT="25" ALIGN="MIDDLE" BORDER="0"
 SRC="img42.gif"
 ALT="$ \circlearrowleft$"></SPAN> button).

<P>

<H3><A NAME="SECTION00011400000000000000">
Questions:</A>
</H3>
By simple inspection of 2D views of the data and of the corresponding
pdf contours, how can you tell which sample corresponds to a spherical
process (as the sample <SPAN CLASS="MATH"><IMG
 WIDTH="21" HEIGHT="26" ALIGN="MIDDLE" BORDER="0"
 SRC="img34.gif"
 ALT="$ X_1$"></SPAN>), which sample corresponds to a process
with a diagonal covariance matrix (as <SPAN CLASS="MATH"><IMG
 WIDTH="21" HEIGHT="26" ALIGN="MIDDLE" BORDER="0"
 SRC="img36.gif"
 ALT="$ X_2$"></SPAN>), and which to a process
with a full covariance matrix (as <SPAN CLASS="MATH"><IMG
 WIDTH="21" HEIGHT="26" ALIGN="MIDDLE" BORDER="0"
 SRC="img38.gif"
 ALT="$ X_3$"></SPAN>)?

<P>

<H3><A NAME="SECTION00011500000000000000">
Find the right statements:</A>
</H3>
<DL COMPACT>
<DT><SPAN CLASS="MATH"><IMG
 WIDTH="14" HEIGHT="13" ALIGN="BOTTOM" BORDER="0"
 SRC="img43.gif"
 ALT="$ \Box$"></SPAN></DT>
<DD>In process 1 the first and the second component of the
  vectors <!-- MATH
 $\ensuremath\mathbf{x}_i$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="16" HEIGHT="25" ALIGN="MIDDLE" BORDER="0"
 SRC="img44.gif"
 ALT="$ \ensuremath\mathbf{x}_i$"></SPAN> are independent.

<P>
</DD>
<DT><SPAN CLASS="MATH"><IMG
 WIDTH="14" HEIGHT="13" ALIGN="BOTTOM" BORDER="0"
 SRC="img43.gif"
 ALT="$ \Box$"></SPAN></DT>
<DD>In process 2 the first and the second component of the
  vectors <!-- MATH
 $\ensuremath\mathbf{x}_i$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="16" HEIGHT="25" ALIGN="MIDDLE" BORDER="0"
 SRC="img44.gif"
 ALT="$ \ensuremath\mathbf{x}_i$"></SPAN> are independent.

<P>
</DD>
<DT><SPAN CLASS="MATH"><IMG
 WIDTH="14" HEIGHT="13" ALIGN="BOTTOM" BORDER="0"
 SRC="img43.gif"
 ALT="$ \Box$"></SPAN></DT>
<DD>In process 3 the first and the second component of the
  vectors <!-- MATH
 $\ensuremath\mathbf{x}_i$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="16" HEIGHT="25" ALIGN="MIDDLE" BORDER="0"
 SRC="img44.gif"
 ALT="$ \ensuremath\mathbf{x}_i$"></SPAN> are independent.

<P>
</DD>
<DT><SPAN CLASS="MATH"><IMG
 WIDTH="14" HEIGHT="13" ALIGN="BOTTOM" BORDER="0"
 SRC="img43.gif"
 ALT="$ \Box$"></SPAN></DT>
<DD>If the first and second component of the vectors <!-- MATH
 $\ensuremath\mathbf{x}_i$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="16" HEIGHT="25" ALIGN="MIDDLE" BORDER="0"
 SRC="img44.gif"
 ALT="$ \ensuremath\mathbf{x}_i$"></SPAN>
  are independent, the cloud of points and the pdf contour has the
  shape of a circle.

<P>
</DD>
<DT><SPAN CLASS="MATH"><IMG
 WIDTH="14" HEIGHT="13" ALIGN="BOTTOM" BORDER="0"
 SRC="img43.gif"
 ALT="$ \Box$"></SPAN></DT>
<DD>If the first and second component of the vectors <!-- MATH
 $\ensuremath\mathbf{x}_i$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="16" HEIGHT="25" ALIGN="MIDDLE" BORDER="0"
 SRC="img44.gif"
 ALT="$ \ensuremath\mathbf{x}_i$"></SPAN>
  are independent, the cloud of points and pdf contour has to be
  elliptic with the principle axes of the ellipse aligned with the
  abscissa and ordinate axes.

<P>
</DD>
<DT><SPAN CLASS="MATH"><IMG
 WIDTH="14" HEIGHT="13" ALIGN="BOTTOM" BORDER="0"
 SRC="img43.gif"
 ALT="$ \Box$"></SPAN></DT>
<DD>For the covariance matrix <!-- MATH
 $\ensuremath\boldsymbol{\Sigma}$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="15" HEIGHT="14" ALIGN="BOTTOM" BORDER="0"
 SRC="img10.gif"
 ALT="$ \ensuremath\boldsymbol{\Sigma}$"></SPAN> the elements have to
  satisfy <!-- MATH
 $c_{ij} = c_{ji}$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="54" HEIGHT="25" ALIGN="MIDDLE" BORDER="0"
 SRC="img45.gif"
 ALT="$ c_{ij} =
c_{ji}$"></SPAN>.

<P>
</DD>
<DT><SPAN CLASS="MATH"><IMG
 WIDTH="14" HEIGHT="13" ALIGN="BOTTOM" BORDER="0"
 SRC="img43.gif"
 ALT="$ \Box$"></SPAN></DT>
<DD>The covariance matrix has to be positive definite
  (<!-- MATH
 $\ensuremath\mathbf{x}^{\mathsf T}\ensuremath\boldsymbol{\Sigma}\, \ensuremath\mathbf{x}\ge 0$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="68" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
 SRC="img46.gif"
 ALT="$ \ensuremath\mathbf{x}^{\mathsf T}\ensuremath\boldsymbol{\Sigma}  \ensuremath\mathbf{x}\ge 0$"></SPAN>). (If yes, what happens if not? Try it
  out in M<SMALL>ATLAB</SMALL>).
</DD>
</DL>

<P>

<H2><A NAME="SECTION00012000000000000000">
Gaussian modeling: Mean and variance of a sample</A>
</H2>

<P>
We will now estimate the parameters <!-- MATH
 $\ensuremath\boldsymbol{\mu}$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="13" HEIGHT="25" ALIGN="MIDDLE" BORDER="0"
 SRC="img9.gif"
 ALT="$ \ensuremath\boldsymbol{\mu}$"></SPAN> and <!-- MATH
 $\ensuremath\boldsymbol{\Sigma}$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="15" HEIGHT="14" ALIGN="BOTTOM" BORDER="0"
 SRC="img10.gif"
 ALT="$ \ensuremath\boldsymbol{\Sigma}$"></SPAN> of the Gaussian
models from the data samples.

<P>

<H3><A NAME="SECTION00012100000000000000">
Useful formulas and definitions:</A>
</H3>

<UL>
<LI>Mean estimator: <!-- MATH
 $\displaystyle \hat{\ensuremath\boldsymbol{\mu}} = \frac{1}{N}
\sum_{i=1}^{N} \ensuremath\mathbf{x}_i$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="86" HEIGHT="58" ALIGN="MIDDLE" BORDER="0"
 SRC="img47.gif"
 ALT="$ \displaystyle \hat{\ensuremath\boldsymbol{\mu}} = \frac{1}{N}
\sum_{i=1}^{N} \ensuremath\mathbf{x}_i$"></SPAN>
</LI>
<LI>Unbiased covariance estimator: <!-- MATH
 $\displaystyle \hat{\ensuremath\boldsymbol{\Sigma}} =
\frac{1}{N-1} \; \sum_{i=1}^{N} (\ensuremath\mathbf{x}_i-\ensuremath\boldsymbol{\mu})^{\mathsf T}(\ensuremath\mathbf{x}_i-\ensuremath\boldsymbol{\mu}) $
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="210" HEIGHT="58" ALIGN="MIDDLE" BORDER="0"
 SRC="img48.gif"
 ALT="$ \displaystyle \hat{\ensuremath\boldsymbol{\Sigma}} =
\frac{1}{N-1} \; \sum_{i...
...dsymbol{\mu})^{\mathsf T}(\ensuremath\mathbf{x}_i-\ensuremath\boldsymbol{\mu}) $"></SPAN>
</LI>
</UL>

<P>

<H3><A NAME="SECTION00012200000000000000">
Experiment:</A>
</H3>
Take the sample <SPAN CLASS="MATH"><IMG
 WIDTH="21" HEIGHT="26" ALIGN="MIDDLE" BORDER="0"
 SRC="img38.gif"
 ALT="$ X_3$"></SPAN> of 10000 points generated from <!-- MATH
 ${\cal
N}(\ensuremath\boldsymbol{\mu},\ensuremath\boldsymbol{\Sigma}_3)$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="62" HEIGHT="28" ALIGN="MIDDLE" BORDER="0"
 SRC="img49.gif"
 ALT="$ {\cal
N}(\ensuremath\boldsymbol{\mu},\ensuremath\boldsymbol{\Sigma}_3)$"></SPAN>. Compute an estimate <!-- MATH
 $\hat{\ensuremath\boldsymbol{\mu}}$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="13" HEIGHT="27" ALIGN="MIDDLE" BORDER="0"
 SRC="img50.gif"
 ALT="$ \hat{\ensuremath\boldsymbol{\mu}}$"></SPAN> of its mean and an
estimate <!-- MATH
 $\hat{\ensuremath\boldsymbol{\Sigma}}$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="15" HEIGHT="17" ALIGN="BOTTOM" BORDER="0"
 SRC="img51.gif"
 ALT="$ \hat{\ensuremath\boldsymbol{\Sigma}}$"></SPAN> of its variance:

<OL>
<LI>with all the available points  <!-- MATH
 $\hat{\ensuremath\boldsymbol{\mu}}_{(10000)}
=$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="65" HEIGHT="27" ALIGN="MIDDLE" BORDER="0"
 SRC="img52.gif"
 ALT="$ \hat{\ensuremath\boldsymbol{\mu}}_{(10000)}
=$"></SPAN> <!-- MATH
 $\hat{\ensuremath\boldsymbol{\Sigma}}_{(10000)} =$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="67" HEIGHT="33" ALIGN="MIDDLE" BORDER="0"
 SRC="img53.gif"
 ALT="$ \hat{\ensuremath\boldsymbol{\Sigma}}_{(10000)} =$"></SPAN> <BR>
<BR>
<BR>
</LI>
<LI>with only 1000 points  <!-- MATH
 $\hat{\ensuremath\boldsymbol{\mu}}_{(1000)}
=$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="60" HEIGHT="27" ALIGN="MIDDLE" BORDER="0"
 SRC="img54.gif"
 ALT="$ \hat{\ensuremath\boldsymbol{\mu}}_{(1000)}
=$"></SPAN> <!-- MATH
 $\hat{\ensuremath\boldsymbol{\Sigma}}_{(1000)} =$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="61" HEIGHT="33" ALIGN="MIDDLE" BORDER="0"
 SRC="img55.gif"
 ALT="$ \hat{\ensuremath\boldsymbol{\Sigma}}_{(1000)} =$"></SPAN> <BR>
<BR>
<BR>
</LI>
<LI>with only 100 points  <!-- MATH
 $\hat{\ensuremath\boldsymbol{\mu}}_{(100)}
=$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="54" HEIGHT="27" ALIGN="MIDDLE" BORDER="0"
 SRC="img56.gif"
 ALT="$ \hat{\ensuremath\boldsymbol{\mu}}_{(100)}
=$"></SPAN> <!-- MATH
 $\hat{\ensuremath\boldsymbol{\Sigma}}_{(100)} =$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="56" HEIGHT="33" ALIGN="MIDDLE" BORDER="0"
 SRC="img57.gif"
 ALT="$ \hat{\ensuremath\boldsymbol{\Sigma}}_{(100)} =$"></SPAN> <BR>
<BR>
<BR>
</LI>
</OL>
Compare the estimated mean vector <!-- MATH
 $\hat{\ensuremath\boldsymbol{\mu}}$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="13" HEIGHT="27" ALIGN="MIDDLE" BORDER="0"
 SRC="img50.gif"
 ALT="$ \hat{\ensuremath\boldsymbol{\mu}}$"></SPAN> to the original mean
vector <!-- MATH
 $\ensuremath\boldsymbol{\mu}$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="13" HEIGHT="25" ALIGN="MIDDLE" BORDER="0"
 SRC="img9.gif"
 ALT="$ \ensuremath\boldsymbol{\mu}$"></SPAN> by measuring the Euclidean distance that separates them.
Compare the estimated covariance matrix <!-- MATH
 $\hat{\ensuremath\boldsymbol{\Sigma}}$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="15" HEIGHT="17" ALIGN="BOTTOM" BORDER="0"
 SRC="img51.gif"
 ALT="$ \hat{\ensuremath\boldsymbol{\Sigma}}$"></SPAN> to the original
covariance matrix <!-- MATH
 $\ensuremath\boldsymbol{\Sigma}_3$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="21" HEIGHT="26" ALIGN="MIDDLE" BORDER="0"
 SRC="img41.gif"
 ALT="$ \ensuremath\boldsymbol{\Sigma}_3$"></SPAN> by measuring the matrix 2-norm of their
difference (the norm <!-- MATH
 $\|\mathbf{A}-\mathbf{B}\|_2$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="64" HEIGHT="28" ALIGN="MIDDLE" BORDER="0"
 SRC="img58.gif"
 ALT="$ \Vert\mathbf{A}-\mathbf{B}\Vert _2$"></SPAN> constitutes a
measure of similarity of two matrices <!-- MATH
 $\mathbf{A}$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="15" HEIGHT="14" ALIGN="BOTTOM" BORDER="0"
 SRC="img59.gif"
 ALT="$ \mathbf{A}$"></SPAN> and <!-- MATH
 $\mathbf{B}$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="15" HEIGHT="14" ALIGN="BOTTOM" BORDER="0"
 SRC="img60.gif"
 ALT="$ \mathbf{B}$"></SPAN>;
use M<SMALL>ATLAB</SMALL>'s <TT>norm</TT> command).

<P>

<H3><A NAME="SECTION00012300000000000000">
Example:</A>
</H3>
In the case of 1000 points (case 2.): 
<BR>
<TT>&#187; X = X3(1:1000,:);</TT> 
<BR>
<TT>&#187; N = size(X,1)</TT> 
<BR>
<TT>&#187; mu_1000 = sum(X)/N</TT> 
<BR>
<SPAN  CLASS="textit">-or-</SPAN>
<BR>
<TT>&#187; mu_1000 = mean(X)</TT> 
<BR>
<TT>&#187; sigma_1000 = (X - repmat(mu_1000,N,1))' * (X - repmat(mu_1000,N,1)) / (N-1)</TT> 
<BR>
<SPAN  CLASS="textit">-or-</SPAN>
<BR>
<TT>&#187; sigma_1000 = cov(X)</TT> 
<BR>
<P>

<TT>&#187; % Comparison of means and covariances:</TT> 
<BR>
<TT>&#187; e_mu =  sqrt((mu_1000 - mu) * (mu_1000 - mu)')</TT> 
<BR>
<TT>&#187; % (This is the Euclidean distance between mu_1000 and mu)</TT> 
<BR>
<TT>&#187; e_sigma = norm(sigma_1000 - sigma_3)</TT> 
<BR>
<TT>&#187; % (This is the 2-norm of the difference between sigma_1000 and sigma_3)</TT>

<P>

<H3><A NAME="SECTION00012400000000000000">
Question:</A>
</H3>
When comparing the estimated values <!-- MATH
 $\hat{\ensuremath\boldsymbol{\mu}}$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="13" HEIGHT="27" ALIGN="MIDDLE" BORDER="0"
 SRC="img50.gif"
 ALT="$ \hat{\ensuremath\boldsymbol{\mu}}$"></SPAN> and <!-- MATH
 $\hat{\ensuremath\boldsymbol{\Sigma}}$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="15" HEIGHT="17" ALIGN="BOTTOM" BORDER="0"
 SRC="img51.gif"
 ALT="$ \hat{\ensuremath\boldsymbol{\Sigma}}$"></SPAN> to
the original values of <!-- MATH
 $\ensuremath\boldsymbol{\mu}$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="13" HEIGHT="25" ALIGN="MIDDLE" BORDER="0"
 SRC="img9.gif"
 ALT="$ \ensuremath\boldsymbol{\mu}$"></SPAN> and <!-- MATH
 $\ensuremath\boldsymbol{\Sigma}_3$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="21" HEIGHT="26" ALIGN="MIDDLE" BORDER="0"
 SRC="img41.gif"
 ALT="$ \ensuremath\boldsymbol{\Sigma}_3$"></SPAN> (using the Euclidean
distance and the matrix 2-norm), what can you observe?

<P>

<H3><A NAME="SECTION00012500000000000000">
Find the right statements:</A>
</H3>
<DL COMPACT>
<DT><SPAN CLASS="MATH"><IMG
 WIDTH="14" HEIGHT="13" ALIGN="BOTTOM" BORDER="0"
 SRC="img43.gif"
 ALT="$ \Box$"></SPAN></DT>
<DD>An accurate mean estimate requires more points than an
  accurate variance estimate.
</DD>
<DT><SPAN CLASS="MATH"><IMG
 WIDTH="14" HEIGHT="13" ALIGN="BOTTOM" BORDER="0"
 SRC="img43.gif"
 ALT="$ \Box$"></SPAN></DT>
<DD>It is very important to have enough training examples to
  estimate the parameters of the data generation process accurately.
</DD>
</DL>

<P>

<H2><A NAME="SECTION00013000000000000000"></A>
<A NAME="sec:likelihood"></A>
<BR>
Likelihood of a sample with respect to a Gaussian model
</H2>

<P>
In the following we compute the likelihood of a sample point <!-- MATH
 $\ensuremath\mathbf{x}$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="12" HEIGHT="13" ALIGN="BOTTOM" BORDER="0"
 SRC="img20.gif"
 ALT="$ \ensuremath\mathbf{x}$"></SPAN>,
and the joint likelihood of a series of samples <SPAN CLASS="MATH"><IMG
 WIDTH="16" HEIGHT="14" ALIGN="BOTTOM" BORDER="0"
 SRC="img29.gif"
 ALT="$ X$"></SPAN> for a given model
<!-- MATH
 $\ensuremath\boldsymbol{\Theta}$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="16" HEIGHT="14" ALIGN="BOTTOM" BORDER="0"
 SRC="img61.gif"
 ALT="$ \ensuremath\boldsymbol{\Theta}$"></SPAN> with one Gaussian.  The likelihood will be used in the formula
for classification later on (sec.&nbsp;<A HREF="node2.html#sec:classification">2.3</A>).

<P>

<H3><A NAME="SECTION00013100000000000000">
Useful formulas and definitions:</A>
</H3>

<UL>
<LI><EM>Likelihood</EM>: the likelihood of a sample point <!-- MATH
 $\ensuremath\mathbf{x}_i$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="16" HEIGHT="25" ALIGN="MIDDLE" BORDER="0"
 SRC="img44.gif"
 ALT="$ \ensuremath\mathbf{x}_i$"></SPAN> given
  a data generation model (i.e., given a set of parameters <!-- MATH
 $\ensuremath\boldsymbol{\Theta}$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="16" HEIGHT="14" ALIGN="BOTTOM" BORDER="0"
 SRC="img61.gif"
 ALT="$ \ensuremath\boldsymbol{\Theta}$"></SPAN> for
  the model pdf) is the value of the pdf <!-- MATH