\documentclass{article}
\usepackage{import}
\subimport*{../}{macro}

\providecommand*{\eu}{\ensuremath{\mathrm{e}}}

\setlength\parindent{0px}

\begin{document}
\setcounter{aprob}{0}
\setcounter{bprob}{0}
\title{Homework \#4}
\author{
    \normalsize{CSE 446: Machine Learning}\\
    \normalsize{Prof. Sewoong Oh}\\
    \normalsize{Due: \textbf{Sunday} 3/13, 2022 11:59pm}\\
    \normalsize{97 points}
}
\date{{}}
\maketitle

\noindent\fbox{%
    \parbox{\textwidth}{%
        Note: Since we have delayed the deadline for this assignment, in order to ensure final grades can be provided on time, you may use a MAXIMUM of 3 late days on this assignment (if you have sufficient days remaining).
    }%
}

\noindent Please review all homework guidance posted on the website before submitting to GradeScope. Reminders:
\begin{itemize}
    \item Make sure to read the ``What to Submit'' section following each question and include all items.
    \item Please provide succinct answers and supporting reasoning for each question. Similarly, when discussing experimental results, concisely create tables and/or figures when appropriate to organize the experimental results. All explanations, tables, and figures for any particular part of a question must be grouped together. 
    \item For every problem involving generating plots, please include the plots as part of your PDF submission.
    \item When submitting to Gradescope, please link each question from the homework in Gradescope to the location of its answer in your homework PDF. Failure to do so may result in deductions of up to \points{5}. For instructions, see \url{https://www.gradescope.com/get_started#student-submission}.
    \item If you collaborate on this homework with others, you must indicate who you worked with on your homework. Failure to do so may result in accusations of plagiarism.
    \item Please indicate your final answer to each question by placing a box around the main result(s). To do this in \LaTeX, one option is using the \texttt{boxed} command.
    \item For problems asking you to write some code, please submit code both to Gradescope and \textbf{embed the relevant code snippet in your PDF}. Failure to embed code in your PDF will result in point deductions.
\end{itemize}

Not adhering to these reminders may result in point deductions. \\

% \textcolor{red}{\textbf{Changelog:}}

% \begin{itemize}
%     \item \textbf{11/28} Updated \textt{reconstruction\_error} test in PCA.
%     \item \textbf{11/28} Removed square from k-means objective function.
%     \item \textbf{11/28} Added colab notebook for B1 problem.
%     \item \textbf{11/30} Removed plot of objective function as requirement for k-means sub-problem b.
%     \item \textbf{11/30} Updated test cluster data for k-means.
%     \item \textbf{11/30} Updated due date.
%     \item \textbf{12/1} Correct \textbt{What To Submit} for B Problems.
% \end{itemize}

\clearpage{}


% Start of Problems:

\setcounter{aprob}{0}
 
\section*{Conceptual Questions}
\begin{aprob}  The answers to these questions should be answerable without referring to external materials. Briefly justify your answers with a few words.
    \begin{enumerate}
      \item \points{2} True or False: Given a data matrix $X \in R^{n \times d}$ where $d$ is much smaller than $n$ and $k = \textrm{rank}(X)$, if we project our data onto a $k$ dimensional subspace using PCA, our projection will have zero reconstruction error (in other words, we find a perfect representation of our data, with no information loss).
      \item \points{2} True or False: Suppose that an $n \times n$ matrix $X$ has a singular value decomposition of $USV^{\top}$, where $S$ is a diagonal $n \times n$ matrix. Then, the rows of $V$ are equal to the eigenvectors of $X^{\top}X$.
      \item \points{2} True or False: choosing $k$ to minimize the $k$-means objective (see Equation \eqref{eq:kmeans_obj} below) is a good way to find meaningful clusters.
    	\item \points{2} True or False: The singular value decomposition of a matrix is unique. 
    	\item \points{2} True or False: The rank of a square matrix equals the number of its nonzero eigenvalues. 
      \item \points{2} True or False: Autoencoders, where the encoder and decoder functions are both neural networks with nonlinear activations, can capture more variance of the data in its encoded representation than  PCA using the same number of dimensions.
    \end{enumerate}

    \subsection*{What to Submit:}
    \begin{itemize}
        \item \textbf{Parts a-f:} 1-2 sentence explanation containing your answer.
    \end{itemize}

\end{aprob}
\pagebreak

\clearpage
\section*{Think before you train}
\begin{aprob} \textbf{The first part of this problem (parts a, b)} explores how you would apply machine learning theory and techniques to real-world problems. There are two scenarios detailing a setting, a dataset, and a specific result we hope to achieve. Your job is to describe how you would handle each of the below scenarios with the tools we’ve learned in this class. Your response should include
\begin{enumerate}[label=(\arabic*),topsep=0.2em,itemsep=-0.2em]
    \item any pre-processing steps you would take (i.e., data acquisition and processing),
    \item the specific machine learning pipeline you would use (i.e., algorithms and techniques learned in this class),
    \item how your setup acknowledges the constraints and achieves the desired result.
\end{enumerate}
You should also aim to leverage some of the theory we have covered in this class. Some things to consider may be: the nature of the data (i.e., \textit{How hard is it to learn? Do we need more data? Are the data sources good?}), the effectiveness of the pipeline (i.e., \textit{How strong is the model when properly trained and tuned?}), and the time needed to effectively perform the pipeline.

% Because of the open-ended nature of the question, any thoroughly written responses will receive full credit.

\begin{enumerate}
    \item \points{5} \textbf{Scenario 1: Disease Susceptibility Predictor}
\begin{itemize}
    \item \underline{Setting}: You are tasked by a research institute to create an algorithm that learns the factors that contribute most to acquiring a specific disease.
    \item \underline{Dataset}: A rich dataset of personal demographic information, location information, risk factors, and whether a person has the disease or not.
    \item \underline{Result}: The company wants a system that can determine how susceptible someone is to this disease when they enter in personal information. The pipeline should take limited amount of personal data from a new user and infer more detailed metrics about the person.
\end{itemize}
\item \points{5} \textbf{Scenario 2: Social Media App Facial Recognition Technology}
\begin{itemize}
    \item \underline{Setting}: You are tasked with developing a machine learning pipeline that can quickly map someone’s face for the application of filters (i.e., Snapchat, Instagram).
    \item \underline{Dataset}: A set of face images compiled from the company’s employees and their families.
    \item  \underline{Result}: The company wants an algorithm that can quickly identify the key features of a person’s face to apply a filter. (\textbf{Note:} Do not worry about describing the actual filter application).
\end{itemize}
\end{enumerate}

\textbf{The second part of this problem (parts c, d)} focuses on exploring possible shortcomings of these models, and what real-world implications might follow from ignoring these issues.

\begin{enumerate}
\setcounter{enumi}{2}
\item \points{5} Recall in Homework 2 we trained models to predict crime rates using various features. It is important to note that \textbf{datasets describing crime have various shortcomings in describing the entire landscape of illegal behavior in a city, and that these shortcomings often fall disproportionately on minority communities}. Some of these shortcomings include that crimes are reported at different rates in different neighborhoods, that police respond differently to the same crime reported or observed in different neighborhoods, and that police spend more time patrolling in some neighborhoods than others. What real-world implications might follow from ignoring these issues?

\item \points{5} Pick one of either Scenario 1 or Scenario 2 (in parts a and b). Briefly describe (1) some potential shortcomings of your training process that may result in your algorithm having different accuracy on different populations, and (2) how you may modify your procedure to address these shortcomings.

% \item \points{5} \textbf{Malware Detection:}
% \begin{itemize}
%     \item Setting: You are tasked by a major tech company to create a service that ingests malware metadata and provides accurate assessments as to whether a new file is malicious or not.
%     \item Dataset: A set of malware file metadata from users worldwide describing all attributes of offending files including its contents, publisher, and attributes of the resultant activity.
%     \item Result: The company wants an accurate, scalable solution to detect whether incoming files are malicious for users across the globe.
% \end{itemize}
\end{enumerate}

\medskip

\subsection*{What to Submit:}
\begin{itemize}
    \item For parts (a) and (b): One short paragraph (4-7) sentences for each of the described scenarios.
    \item For part (c): One short paragraph on real-world implications that may follow from ignoring dataset issues.
    \item For part (d): Clear and well-thought-out answers addressing (1) and (2) (as described in the problem). Two short paragraphs or one medium paragraph suffice. You only need to pick one of the scenarios to expand on here.
\end{itemize}
\end{aprob}

\section*{$k$-means clustering}

\begin{aprob}
Given a dataset $\bx_1,..., \bx_n \in \R^{d}$ and an integer $1 \leq k \leq n$, recall the following $k$-means objective function
\begin{align}
    \min_{\pi_1, ..., \pi_k} \sum_{i=1}^{k} \sum_{j \in \pi_i} \norm{2}{ \bx_j - \mu_{i} } \ , \quad \mu_i = \frac{1}{|\pi_i|} \sum_{j \in \pi_i} \bx_j \ . \label{eq:kmeans_obj}
\end{align}
Above, $\{\pi_i\}_{i=1}^{k}$ is a partition of $\{1, 2, ..., n\}$. The objective \eqref{eq:kmeans_obj} is NP-hard\footnote{
To be more precise, it is both NP-hard in $d$ when $k=2$ and $k$ when $d=2$. See the references on the wikipedia page for $k$-means for more details.} to find a global minimizer of. Nevertheless the commonly-used algorithm we discussed in lecture (Lloyd's algorithm), typically works well in practice.

\vspace{.8em}
\textcolor{red!80!black}{\textbf{Note on Time to Run} --- This problem can be implemented fairly quickly; if you find it taking upwards of one hour, please check your implementation! (Hint: \textbf{For loops are costly.} Can you vectorize it or use Numpy operations to make it faster in some ways? If not, is looping through data-points or through centers faster?)}

\medskip


\begin{enumerate}
    \item \points{5} Implement Lloyd's algorithm for solving the $k$-means objective \eqref{eq:kmeans_obj}. Do not use any off-the-shelf implementations, such as those found in \texttt{scikit-learn}. Include your code in your submission.
    
    \item \points{5} Run the algorithm on the \emph{training} dataset of MNIST with $k=10$. Visualize (and include in your report) the cluster centers as a $28\times 28$ image.

    \item \points{5} For $k=\{2, 4, 8, 16, 32, 64\}$ run the algorithm on the \emph{training} dataset to obtain centers $\{\mu_{i}\}_{i=1}^k$. If $\{(\bx_i,y_i)\}_{i=1}^n$ and $\{(\bx_i',y_i')\}_{i=1}^m$ denote the training and test sets, respectively, plot the training error $\frac{1}{n} \sum_{i=1}^n \min_{j=1,\dots,k} \| \mu_j - \bx_i \|_2$ and test error $\frac{1}{m} \sum_{i=1}^m \min_{j=1,\dots,k} \| \mu_j - \bx_i' \|_2$ as a function of $k$ on the same plot.
\end{enumerate}
 \subsection*{What to Submit:}
    \begin{itemize}
        \item \textbf{For part (a):} Lloyd's algorithm code
        \item \textbf{For part (b):} 10 images of cluster centers.
        \item \textbf{For part (c):} Plot of training and test error as function of k.
        \item Code for parts a-c
    \end{itemize}


\end{aprob}

\section*{PCA}
\begin{aprob}
Let's do PCA on MNIST dataset and reconstruct the digits in the dimensionality-reduced PCA basis. You will actually compute your PCA basis using the training dataset only, and evaluate the quality of the basis on the test set, similar to the k-means reconstructions of above. 
We have $n_{train}=50,000$ training examples of size $28 \times 28$. Begin by flattening each example to a vector to obtain $X_{train} \in \mathbb{R}^{50,000 \times d}$ and $X_{test} \in \mathbb{R}^{10,000 \times d}$ for $d:= 784$. \\

Let $\mu \in \mathbb{R}^{d}$ denote the average of the training examples in $X_{train}$, i.e., $\mu = \frac{1}{n_{train}} X_{train}^\top \mathbf{1}^\top$. Now let $\Sigma =  (X_{train} - \mathbf{1} \mu^\top)^\top (X_{train} - \mathbf{1} \mu^\top)/50000$ denote the sample covariance matrix of the training examples, and let $\Sigma = UDU^T$ denote the eigenvalue decomposition of $\Sigma$.
\begin{enumerate}
\item \points{2}
    If $\lambda_i$ denotes the $i$th largest eigenvalue of $\Sigma$, what are the eigenvalues $\lambda_1$, $\lambda_2$, $\lambda_{10}$, $\lambda_{30}$, and $\lambda_{50}$? What is the sum of eigenvalues $\sum_{i=1}^d{\lambda_i}$?
 
\item \points{5}
    Let $x \in \mathbb{R}^d$ and $k \in 1,2,\dots,d$. Write a formula for the rank-$k$ PCA approximation of $x$.
 
\item \points{5} Using this approximation, plot the reconstruction error from $k=1$ to $100$ (the $X$-axis is $k$ and the $Y$-axis is the mean-squared error reconstruction error) on the training set and the test set (using the $\mu$ and the basis learned from the training set). 
    On a separate plot, plot  $1-\frac{\sum_{i=1}^{k}{\lambda_i}}{\sum_{i=1}^{d}{\lambda_i}}$ from $k=1$ to $100$.
    
\item \points{3}
    Now let us get a sense of what the top PCA directions are capturing. Display the first $10$ eigenvectors as images, and provide a brief interpretation of what you think they capture.
    
\item \points{3}
    Finally, visualize a set of reconstructed digits from the training set for different values of $k$. In particular provide the reconstructions for digits $2,6,7$ with values $k = 5, 15, 40, 100$ (just choose an image from each digit arbitrarily). Show the original image side-by-side with its reconstruction. Provide a brief interpretation, in terms of your perceptions of the quality of these reconstructions and the dimensionality you used.
    
\end{enumerate}
 \subsection*{What to Submit:}
    \begin{itemize}

        \item \textbf{For part (a):} Eigenvalues λ1, λ2, λ10, λ30, and λ50 and the sum. At least 6 leading digits.
        \item \textbf{For part (b):} The Formula. If you are defining new variables/matrices make sure their definition is stated
        clearly.
        \item \textbf{For part (c):} Plot containing reconstruction error on train and test sets. Plot of $1-\frac{\sum_{i=1}^{k}{\lambda_i}}{\sum_{i=1}^{d}{\lambda_i}}$
        \item \textbf{For part (d):} 10 eigenvectors as images.
        \item \textbf{For part (e):} 15 total images, including 3 original and 12 reconstructed ones. Each reconstructed image
        corresponds to a certain digit (2, 6 or 7) and k value (5, 15, 40 or 100).
        \item Code for parts c-e
    \end{itemize}
\end{aprob}


\section*{Unsupervised Learning with Autoencoders}
\begin{aprob}
In this exercise, we will train two simple autoencoders to perform
dimensionality reduction on MNIST. As discussed in lecture, autoencoders are a
long-studied neural network architecture comprised of an encoder component to
summarize the latent features of input data and a decoder component to try and
reconstruct the original data from the latent features.

\subsubsection*{Weight Initialization and PyTorch}
Last assignment, we had you refrain from using \texttt{torch.nn} modules. For
this assignment, we recommend using \texttt{nn.Linear} for your linear layers.
You will not need to initialize the weights yourself; the default
He/Kaiming uniform initialization in PyTorch will be sufficient for this problem. \emph{Hint: we also recommend using the \text{\texttt{nn.Sequential}} module to organize your
network class and simplify the process of writing the forward pass. However, you may choose to organize your code however you'd like.}
\subsubsection*{Training}
Use \texttt{optim.Adam} for this question. Feel free to experiment with different learning rates, though you can use $5 \cdot 10^{-5}$ as mentioned in the code. Use mean
squared error (\texttt{nn.MSELoss()} or \texttt{F.mse\_loss()}) for the loss function.

\begin{enumerate}
  \item \points{10} Use a network with a single linear layer. Let $W_{\text{e}} \in \mathbb{R}^{h \times d}$ and
    $W_{\text{d}} \in \mathbb{R}^{d\times h}$. Given some $x \in \mathbb{R}^d$,
    the forward pass is formulated as \[
      \mathcal{F}_{1}(x) = W_{\text{d}} W_{\text{e}} x
    .\]
    Run experiments for $h \in \{ 32, 64, 128 \}$. For
    each of the different $h$ values, report your final training error and visualize a
    set of 10 reconstructed digits, side-by-side with the original image. \emph{Note:} we omit the bias term in the formulation
    for notational convenience since \texttt{nn.Linear} learns bias
    parameters alongside weight parameters by default.
    
  \item \points{10} Use a single-layer network with non-linearity. Let $W_{\text{e}} \in \mathbb{R}^{h \times d}$, $W_{\text{d}} \in \mathbb{R}^{d\times h}$, and activation $\sigma: \mathbb{R} \longmapsto \mathbb{R}$, where $\sigma$ is the ReLU function. Given some $x \in \mathbb{R}^d$,
    the forward pass is formulated as 
    \[
      \mathcal{F}_{2}(x) = \sigma(W_{\text{d}} \sigma(W_{\text{e}} x))
    .\] Report the same findings as asked for in part a (for $h \in \{ 32,64,128 \}$).
  \item \points{5} Now, evaluate $\mathcal{F}_1(x)$ and $\mathcal{F}_2(x)$ (use $h=128$
    here) on the test set. Provide the test reconstruction errors in a
    table.
  \item \points{5} In a few sentences, compare the quality of the reconstructions from these two autoencoders with those of PCA from problem A5. You may need to re-run your code for PCA using the ranks $k \in \{32, 64, 128\}$ to match the $h$ values used above.
\end{enumerate}
 \subsection*{What to Submit:}
    \begin{itemize}

        \item \textbf{For parts (a, b):} Final training error and set of 10 reconstructed images of digits, side-by-side with the
original image (10 images for each h).
        \item \textbf{For part (c):} Errors of networks from part a and b on testing set.
        \item \textbf{For part (d):} 2-3 sentences on differences in quality of solutions between PCA and Autoencoders, with
example images
        \item Code for parts a-c
    \end{itemize}

\end{aprob}

\section*{Administrative}
\begin{aprob}
\begin{enumerate}
    \item \points{2} About how many hours did you spend on this homework? There is no right or wrong answer :)
\end{enumerate}
\end{aprob}

\end{document}
