\section{$k$-Nearest Neighbors [19 Points]}

\begin{enumerate}

        \item \textbf{[6 pts]} In a $k$NN classification problem, assume that the distance measure is not explicitly specified to you. Instead, you are given a “black box” where you input a set of data points $P_1, P_2, \dots P_n$ and an unlabelled data point $Q$, and the black box outputs the nearest neighbor of $Q$, say $P_i$ and its corresponding label $C_i$. Is it possible to construct a $k$NN classification algorithm (w.r.t the unknown distance metrics) based on this black box alone? If so, how and if not, why not?
        \begin{tcolorbox}[fit,height=7cm, width=0.9\textwidth, blank, borderline={1pt}{-2pt}]
        
        \end{tcolorbox}
        
        \item \textbf{[4 pts]} Now suppose the black box returns the $j$ nearest neighbors (and their corresponding labels) instead of the single nearest neighbor (assume $j \neq k$). Is it still possible to construct a $k$NN classification algorithm based on the black box? If so, how and if not, why not?

        \textbf{Note:} The black box operates with a \emph{set} of data points, which assumes they are distinct.
        \begin{tcolorbox}[fit,height=7cm, width=0.9\textwidth, blank, borderline={1pt}{-2pt}]
         
        \end{tcolorbox}
        

        \item \textbf{[3 pts]} Assume we have a dataset with binary labels and we know that the leave-one-out cross validation accuracy (LOOCV) \footnote{K-fold cross validation splits data into K roughly equal sized parts. For the kth part, we fit the model to the other $K-1$ parts of the data, and calculate the prediction error of the fitted model when predicting the kth part of the data. We do this for $k = 1,2,\ldots,K$ and combine the K estimates of prediction error. The case where $K = N$ is known as leave-one-out cross validation. (Elements of Statistical Learning. Hastie, Tibshirani, and Friedman 2009, Section 7.10.1, p. 261) } of a $1$-NN classifier on this dataset is $1$. Now suppose that we introduce some noise to the dataset: each label has a 10\% chance of being flipped to the other class. What is the \emph{expected} LOOCV accuracy of a $1$-NN classifier in this setting?
        

        \begin{tcolorbox}[fit,height=5cm, width=0.9\textwidth, blank,       borderline={1pt}{-2pt}]
        
        \end{tcolorbox}


        \item \textbf{[3 pts]} Suppose that in the dataset from the previous question, exactly $10 \%$ of the labels got flipped. What is the \emph{maximum} possible LOOCV accuracy? Justify your answer using a formal proof or by constructing an example. 

        \begin{tcolorbox}[fit,height=3cm, width=0.9\textwidth, blank,       borderline={1pt}{-2pt}]
        
        \end{tcolorbox}


    
        \item \textbf{[3 pts]} How should the noise level (i.e., the probability of a label being flipped) affect your choice of $k$ for the $k$-NN algorithm, if at all? You do not need to provide a formal proof but you should give a brief justification. 

        \begin{tcolorbox}[fit,height=3cm, width=0.9\textwidth, blank,       borderline={1pt}{-2pt}]
        
        \end{tcolorbox}


    \clearpage
\end{enumerate}