\documentclass[10pt]{article}
\usepackage{amssymb,amsmath}
\usepackage{graphicx}
\usepackage{color}


\addtolength{\textheight}{1.5in}
\addtolength{\topmargin}{-0.8in}
\addtolength{\oddsidemargin}{-0.5in}
\addtolength{\evensidemargin}{-0.5in}
\addtolength{\textwidth}{1.in}

\newcommand{\comment}[1]{}
\newcommand{\mmp}[1]{\textcolor{blue}{MMP: #1}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\beqa}{\begin{eqnarray}}
\newcommand{\eeqa}{\end{eqnarray}}
\newcommand{\bit}{\begin{itemize}\setlength{\itemsep}{0cm}\setlength{\topsep}{0cm}}
\newcommand{\eit}{\end{itemize}}
\newcommand{\benum}{\begin{enumerate}\setlength{\itemsep}{0cm}\setlength{\parsep
}{0cm}}
\newcommand{\eenum}{\end{enumerate}}
\newcommand{\bprogram}{\begin{tabbing}mm\=mm\=mm\=mm\= \kill\\}
\newcommand{\eprogram}{\end{tabbing}}

% math mode commands

\newcommand{\bigOO}{{\cal O}}
\newcommand{\bbone}{{\mathbf 1}}
\newcommand {\argmax}[2]{\mbox{\raisebox{-1.7ex}{$\stackrel{\textstyle{\rm #1}}{\scriptstyle #2}$}}\,}
\newcommand{\dataset}{{\cal D}}
\newcommand{\datasett}{\dataset=\{x^1,\ldots x^n\}}
\newcommand{\tilDD}{\tilde{\dataset}}

\newcommand{\rrr}{{\mathbb R}}
\newcommand{\fracpartial}[2]{\frac{\partial #1}{\partial #2}}

\newcommand{\setxx}[1]{\{x\,|\,{#1} \}}
\newcommand{\tilN}{\tilde{N}}
\newcommand{\tilx}{\tilde{x}}
\newcommand{\hatl}{\hat{L}}
\newcommand{\llogit}{_{\rm logit}}
\newcommand{\supind}[1]{^{(#1)}}
\newcommand{\ssig}{\sigma^2}
\newcommand{\N}{\mathcal{N}}


\newlength{\picwi}
\begin{document}
\setlength{\parindent}{0em}
\setlength{\parskip}{1.3em}

\begin{large}
\centerline{CS 480/680 Homework 7}  % assignment number here

\centerline{Out March 18, 2026}       % out date here
\centerline{Due March 30, 2026}       % due date here
\end{large}

%\centerline{\bf } % title here

\centerline{\large \copyright Marina Meil\u{a} and Benjamin Schneider}
\centerline{\large mmp@uwaterloo.ca}

\vspace{2em}
\begin{small}
\end{small}

%{\em All plots must be included in the .pdf writeup}

{\bf Problem 1 -- Kmeans++ and K-logK}\\
The data $\dataset=\{x^1,\ldots x^n\}$. 
You are initializing K-means with $K$ clusters by different methods. In each case, calculate the number of distance computations necessary for the initialization as functions of $K$ and $n$; you can ignore constant terms but not logarithmic or lower order terms. 

{\bf 1.a} Sample $K$ centers uniformly at random without replacement from $\dataset$. 
\\
{\bf 1.b} Choose $K$ centers from $\dataset$ by Fastest First Traversal.
\\
{\bf 1.c} Choose $K$ centers by Kmeans++.
\\
{\bf 1.d} Choose the $K$ centers by the K-logK method, with $K'={\tt round}(K\ln K)$ (assume that $K\ln K$ is an integer in your evaluation). 
\\
{\bf 1.e} Order the four methods above by the number of distance computations, assuming $n\gg K$ and $n-K\approx n$. 

{\bf Problem 2 -- Simple exercise with K-means}
\\
\setlength{\picwi}{0.32\textwidth}
\begin{tabular}{ccc}
  Example -- initial centers & 
    {\bf a.} Initial centers &     {\bf b.} Initial centers\\
    \includegraphics[width=\picwi]{fig-kmeans-squares-ex0.png}
    &
  \includegraphics[width=\picwi]{fig-kmeans-squares-hwa0}
  &
  \includegraphics[width=\picwi]{fig-kmeans-squares-hwb0}
  \\
  -- after 1 step &
  -- after 1 step &
     -- after 1 step\\
     \includegraphics[width=\picwi]{fig-kmeans-squares-ex1.png}
     &
     \includegraphics[width=\picwi]{fig-kmeans-squares-empty.png}
     & 
     \includegraphics[width=\picwi]{fig-kmeans-squares-empty.png}
     \\
     &  final & final\\
     &
     \includegraphics[width=\picwi]{fig-kmeans-squares-empty.png}
     & 
     \includegraphics[width=\picwi]{fig-kmeans-squares-empty.png}
  \\
\end{tabular}
\\
Draw the position of the centers after 1 step of K-means in the cases {\bf a, b} above.

\newpage
    {\bf Problem 3 -- K-means facts}
    \\
 {\bf a.}
 Prove that the K-means loss can be written as the sum of the squared distances between all pairs of points in the same cluster.
 \beq
     {\cal L}(\Delta,\dataset)=\sum_{k=1}^K\frac{1}{n_k}\sum_{i,j\in C_k}\|x^i-x^j\|^2
\eeq

    {\bf b. CS 680 students only} Assume that $n=mK$ and that the data set contains $K$ equal clusters. You initialize by picking $K$ data points at random, and assigning them to centers $\mu_{1:K}$. For simplicity, we write this as $\mu_{1:K}\sim uniform(\dataset)$. What is the probability that each of the $K$ clusters contains exactly one $\mu_k$? Compute the numerical values of this probability for $K=2,5,10$. Assume sampling is {\em with replacement} (a simplification that everyone uses in practice).

    {\bf c. Where is $K\ln K$ coming from? CS 680 students only}  Now you pick $K'=cK\ln K$ centers at random i.e. $\mu_{1:K'}\sim uniform(\dataset)$   (still with replacement), where $c>1$ is a constant.  Calculate the probability that the first cluster contains none of the $K'$ centers (another simplification), using the approximation $(1+\frac{1}{z})^z\approx e$ for $z>0$ large. What is the value you obtain (should be a simple formula depending on $K$ and $c$).


{\bf  Problem 4 -- Mixture likelihod and gradient descent}
\\
We will consider the finite Mixture of Gaussians model defined by 
%
\beq \label{eq:mixture}
f(x)\;=\;\frac{1}{K}\sum_{k=1}^K\N(x;\mu_k,\ssig_kI_d)\,, 
\eeq
%
where $x,\mu_{1:K}\in \rrr^d$, $\ssig_{1:K}\in (0,\infty)$, $I_d$ is
the unit matrix of order $d$, $\N(x;\mu_k,\ssig_kI_d)=f_k(x)$ is the normal distribution, and $K>1$ an integer.

The gradient w.r.t. $\mu_{1:k},\ssig_{1:K}$ of the likelihood of a single point $x$ under model $f(x)$ are respectively:
\beq
\fracpartial{f}{\mu_k}\;=\;\frac{1}{K\ssig_k}(x-\mu_k)\N(x;\mu_k,\ssig_kI_d)\,, 
\eeq
\beq
\fracpartial{f}{\ssig_k}\;=\;\left[\frac{||x-\mu_k||^2}{2K(\ssig_k)^2}-\frac{n}{2\ssig_k}\right]\N(x;\mu_k,\ssig_kI_d)\,.
\eeq
For the rest of the problem, assume that we observe a sample $\datasett$.

{\bf 4.a} Write the explicit formula for the E step of the EM algorithm for this model. 

{\bf 4.b} Write the M step of the EM algorithm for fitting the model
in \eqref{eq:mixture} to the data $\dataset$ by specializing the formulas in the lecture. 

{\bf 4.c} Write now the log-likelihood of the data and derive the  expression of the gradient of the log-likelihood w.r.t $\mu_k$. Your final expression should be simple and depend on some variables from {\bf a, b}.  

{\bf 4.d}  Denote by $\hat{\mu}_{1:K}$ the values of the centers $\mu_{1:K}$
at a local maximum of the log-likelihood.  Show that $\hat{\mu}_k$ can
be written as a weighted mean of the data, i.e \beq\label{eq:muhat}
\hat{\mu}_k=\sum_i u_{ki}x^i\,, \eeq with $u_{ki}\geq 0$ for all $k,i$ and $\sum_i u_{ki}=1$.
Which equation in Lecture VI have you recovered?

\end{document}
