\documentclass{article}

\usepackage{amsmath,amssymb,amsthm}
\usepackage{csquotes}
\usepackage{dsfont}
\usepackage{thmtools}
\usepackage{etoolbox}
\usepackage{enumitem}
\usepackage{fullpage}
\usepackage{parskip}
\usepackage{xcolor}
\usepackage{verbatim}

\usepackage[colorlinks,linkcolor=red!80!black]{hyperref}
\usepackage[noabbrev,capitalize]{cleveref}

\newlist{qlist}{enumerate}{1}
\setlist[qlist,1]{leftmargin=*, label=\textbf{(\alph*)}, ref={(\alph*)}}
\crefname{qlisti}{part}{parts}
\AtBeginEnvironment{qlist}{\color{blue}}

\crefname{section}{Question}{Questions}

\definecolor{answer}{rgb}{0,.5,0}
\newcommand{\ans}[1]{\par\textcolor{answer}{Answer: #1}}
\newenvironment{answer}{\par\begingroup\color{answer}Answer: }{\endgroup}

\definecolor{points}{rgb}{0.6,0.3,0}
\newcommand{\pts}[1]{\textcolor{points}{[#1~points]}}

\newcommand{\hint}[1]{\textcolor{black!60!white}{\emph{Hint: #1}}}
\newcommand{\meta}[1]{\textcolor{black!60!white}{\emph{#1}}}

\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\cZ}{\mathcal{Z}}
\DeclareMathOperator{\E}{\mathbb{E}}
\newcommand{\eps}{\varepsilon}
\newcommand{\op}{\mathit{op}}
\newcommand{\R}{\mathbb{R}}
\DeclareMathOperator{\spn}{span}
\newcommand{\tp}{^\mathsf{T}}
\DeclareMathOperator{\tr}{tr}
\newcommand{\dist}{\mathcal{D}}
\newcommand{\xdist}{\mathcal{D}_x}

%%begin novalidate  % overleaf code check gives false positives here
\makeatletter
% \abs{} uses regular-sized bars, \abs*{} uses auto-sized ones
\newcommand{\abs}{\@ifstar{\@Abs}{\@abs}}
\newcommand{\@abs}[1]{\lvert #1 \rvert}
\newcommand{\@Abs}[1]{\left\lvert #1 \right\rvert}

\newcommand{\norm}{\@ifstar{\@Norm}{\@norm}}
\newcommand{\@norm}[1]{\lVert #1 \rVert}
\newcommand{\@Norm}[1]{\left\lVert #1 \right\rVert}

\newcommand{\ceil}{\@ifstar{\@Ceil}{\@ceil}}
\newcommand{\@ceil}[1]{\lceil #1 \rceil}
\newcommand{\@Ceil}[1]{\left\lceil #1 \right\rceil}

\newcommand{\floor}{\@ifstar{\@Floor}{\@norm}}
\newcommand{\@floor}[1]{\lfloor #1 \rfloor}
\newcommand{\@Floor}[1]{\left\lfloor #1 \right\rfloor}
\makeatother
%%end novalidate

\declaretheorem[name=Theorem,numberwithin=section]{thm}
\declaretheorem[name=Proposition,sibling=thm]{prop}

\begin{document}
\begin{center}
\Large
CPSC 532D, Fall 2022: Assignment 1
\\
due \textcolor{red}{Tuesday, 20} September 2022, \textbf{12:00 noon}
\end{center}


Prepare your answers to these questions using \LaTeX;
hopefully you're reasonably familiar with it,
but if not, try using Overleaf and looking around for tutorials online.
Feel free to ask questions if you get stuck on things on Piazza
(but remove any details about the actual answers to the questions\dots
make a private post if that's tough).
If you prefer, the \texttt{.tex} source for this file is available on the course website,
and you can put your answers in
\verb|\begin{answ|\verb|er} My answer here... \end{answer}|
% that weird formatting so my answer-stripping script doesn't catch it :p
environments to make them stand out if so;
feel free to delete whatever boilerplate you want.
Or answer in a fresh document.

You can do this with a partner if you'd like (there's a ``find a group'' post on Piazza).
If you look stuff up anywhere other than in SSBD or MRT,
\textbf{cite your sources}:
just say in the answer to that question where you looked.
If you ask anyone else for help, \textbf{cite that too}.
Please do not look at solution manuals / search for people proving the things we're trying to prove / etc.

Submit your answers as a single PDF on Gradescope:
link and login instructions on \href{https://canvas.ubc.ca/courses/101911}{the Canvas site},
which you should now be able to get to even if you're not yet officially enrolled yet.
Make sure to use the Gradescope group feature if you're working in a group.
You'll be prompted to mark where each question is in your PDF;
make sure you mark all relevant pages for each part (which save a surprising amount of grading time).

Please \textbf{put your names on the first page} as a backup, just in case.
If something goes wrong, you can also email your assignment to me directly (\texttt{dsuth@cs.ubc.ca}).


\clearpage
\section{Concentrating on concentric circles \pts{40 + 4 bonus}} \label{q:circles}

In this problem, we'll show that a particular infinite hypothesis class can be PAC-learned with a ``direct'' proof.
\meta{Based in part on SSBD exercise 3.3.}

Let $\cX = \R^2$, $\cY = \{0, 1\}$,
and let $\cH$ be the class of indicator functions for circles around the origin
-- that is, $\cH = \{ h_r : r \in \R_{\ge 0} \}$,
where $h_r(x) = \mathds{1}_{[ \norm x \le r]}$
(a function which is 1 if $\norm x \le r$, 0 otherwise).
Use 0-1 loss.

For a given sample $S$,
let $r_S = \max_{i : y_i = 1} \norm{x_i}$,
and use $\hat h_S$ to denote $h_{r_S}$,
the indicator function of a circle with radius $r_S$,
the tightest circle containing all of the positive training points.

To start with, let's assume \emph{realizability}:
that there is an $h^* \in \cH$ such that $L_\dist(h^*) = 0$.

\begin{qlist}
\item \pts{5}
Show that $\hat h_S$ is an empirical risk minimizer for the hypothesis class $\cH$.

\begin{answer}\textcolor{red}{TODO}\end{answer}

\item \pts{20 + 4 bonus} \label{q:circles:pac}
Prove that if we observe $n \ge \frac1\eps \log \frac1\delta$ samples from a realizable $\dist$,
then the probability that ${\color{red} L_\dist}(\hat h_S) \ge \varepsilon$
is at most $\delta$.

You may assume that $\xdist$, the distribution of $x$s sampled from $\dist$,
is continuous.
For \pts{4 bonus}, also handle the case where $\xdist$ is not continuous (e.g.\ if it has a point mass).

\hint{Three steps: first, what makes a hypothesis have high error in this setting? Next, what would $S$ have to look like in order to get one of those ``bad'' hypotheses? Last, how likely is it to see an $S$ like that?}

\hint{A frequently useful inequality is that $1 - a \le \exp(- a)$.}

\hint{If you're stuck and want to see something similar-ish (but a little more complicated), check out Example 2.4 of MRT, which is also Exercise 2.3 of SSBD.}

\begin{answer}\textcolor{red}{TODO}\end{answer}
\end{qlist}

Now let's make things a little harder on our learner,
by adding random noise.
Rather than perfect realizability,
let $\dist$ be such that
$\Pr(y = 1 \mid x) = \begin{cases}
    1 - \eta & \text{if } h^*(x) = 1 \\
    \eta     & \text{if } h^*(x) = 0
\end{cases}$
for some $h^* \in \cH$:
that is, labels are randomly flipped with probability $\eta \in (0, \tfrac12)$.
The learner knows the value of $\eta$, but not which points have been flipped.

\begin{qlist}[resume]
\item \pts{5}
Is $\hat h_S$ still an ERM?
\begin{answer}\textcolor{red}{TODO}\end{answer}

\item \pts{10}
\begingroup \color{black}
Ambitious Angus claims to have proven the following:
\begin{displayquote}
    For any $\eps, \delta \in (0, 1)$ and $0 \le \eta < \frac12$,
    there is a function $n_\cH(\eta, \eps, \delta)$ such that,
    for any $n \ge n(\eta, \eps, \delta)$ and any $\dist$ of the form above,
    \[ \Pr_{S \sim \dist^n}(L_\dist(\hat h_S) > \eta + \eps) \le \delta .\]
\end{displayquote}
This is followed by an unreadably long computer-assisted proof using both category theory and complicated partial differential equations. Without reading that proof,
\endgroup
argue that Angus must be wrong: no such function $n_\cH$ can exist.

\begin{answer}\textcolor{red}{TODO}\end{answer}
\end{qlist}

\clearpage
\section{Loss functions \pts{35}}

The general form of learning problems we'll usually work with in this course is as follows:
$\dist$ is some distribution over a space $\cZ$,
and $\ell : \cH \times \cZ \to \R$ is a loss function.

For example,
classification problems as we've mostly considered so far are usually framed with
$\cZ = \cX \times \cY$,
with the zero-one loss function $\ell(h, (x, y)) = \mathds{1}(h(x) \ne y)$.
The true risk is $L_\dist(h) = \E_{z \sim \dist} \ell(h, z)$,
and the empirical risk is $L_S(h) = \frac{1}{n} \sum_{i=1}^n \ell(h, z_i)$
for a sample $S = (z_1, \dots, z_n) \sim \dist^n$.
(The notation $\dist^n$ here refers to a \emph{product distribution}:
a distribution which gives $n$ independent and identically-distributed samples from $\dist$.)

\begin{qlist}
\item \pts{10}
Prove that, for any given $h \in \cH$, $L_S$ is unbiased: $\E L_S(h) = L_\dist(h)$.
\begin{answer}\textcolor{red}{TODO}\end{answer}

\item \pts{5}
Prove that the zero-one loss for $k$-way classification ($\cY = \{1, \dots, k\}$) is equal to one minus the accuracy (the portion of correct answers).
\begin{answer}\textcolor{red}{TODO}\end{answer}

\item \pts{5}
\textcolor{black}{For the canonical ImageNet Large Scale Visual Recognition Challenge, images are given with one of a thousand possible labels, and one major way of evaluating those models is the top-5 accuracy: models can make 5 guesses at the label, and we count how often the correct label is one of those 5 guesses.} Frame this in the language above: what kind of object does $h(x)$ output, and what does $\ell(h, (x, y))$ look like?
\begin{answer}\textcolor{red}{TODO}\end{answer}

\item \pts{5}
\textcolor{black}{
\emph{Semantic segmentation} is a computer vision problem where we try to label each pixel of an image as belonging to one of several classes (``tree,'' ``street,'' ``dog,'' etc.).
Let $S = ((x_1, y_1), \dots, (x_n, y_n))$ where $x_i$ are the given input images and $y_i$ their corresponding pixel labels.
One typical evaluation metric is called mIoU (``mean intersection over union''), and is measured on a test set as follows:
\[
    \frac{1}{\text{\# of classes}} \sum_{k=1}^{\text{\# of classes}}
    \frac{\text{\# of pixels from all images predicted as $k$ with label $k$}}
         {\text{\# of pixels from all images predicted as $k$ and/or with label $k$}}
.\]
}

Argue that this metric \emph{cannot} be expressed using the form of loss function above on the given $S$.
(A formal proof isn't necessary on this question, just a good intuitive argument.)
\begin{answer}\textcolor{red}{TODO}\end{answer}

\item \pts{5}
\begingroup\color{black}
Principal component analysis (PCA) is a common technique that can try to find an underlying low-dimensional structure by a linear mapping to a low-dimensional space:
a data point $x \in \R^d$ is mapped to a latent code $z = W x \in \R^k$,
where $W \in \R^{k \times d}$ is a matrix with orthonormal rows ($W W^\top = I$) that we want to learn.
To reconstruct a point from its latent code $z$, we take $W^\top z$.
To find $W$, we minimize the squared reconstruction error on a training set:
\begin{equation} \label{eq:pca}
    \argmin_{W : W W^\top = I} \sum_{i=1}^n \norm{W^\top W x_i - x_i}^2
    \tag{PCA}
.\end{equation}
\endgroup
Frame PCA as an empirical risk minimization problem:
what are the data domain $\cZ$, the sample $S$, the hypothesis class $\cH$, and the loss function $\ell : \cH \times \cZ \to \R$ such that the set of ERMs is exactly the set of solutions to \eqref{eq:pca}?
\begin{answer}\textcolor{red}{TODO}\end{answer}

\item \pts{5}
Frame the problem of fitting a Gaussian distribution to a set of scalar observations as loss minimization above:
what are the data domain $\cZ$, the sample $S$, the hypothesis class $\cH$, and the loss function $\ell : \cH \times \cZ \to \R$ such that the ERM agrees with the maximum likelihood estimate?
\begin{answer}\textcolor{red}{TODO}\end{answer}


\end{qlist}



\clearpage
\section{Bayes optimality \pts{25}}

A Bayes-optimal predictor is a predictor which achieves the lowest possible error for any function, regardless of a choice of hypothesis class or anything like that.\footnote{As usual in this course, I'm ignoring issues of measurability and so on; this should all be formalizable by being appropriately careful and using ``disintegrations'' of probability measures, etc, but for the purpose of this question you can just ignore such issues.}

We'll consider loss functions of the form
$\ell(h, (x, y)) = \lambda(h(x), y)$,
where $h : \cX \to \hat\cY$ and $\lambda : \hat\cY \times \cY \to \R$.%
\footnote{This is often how loss functions are defined in the first place;
there are a few cases in the course where the more general $\ell$ form is more convenient,
but for this question, the $\lambda$ form is a little easier.}
(We often have $\hat\cY = \cY$, as in binary classification, but not necessarily, as you may have seen in the previous question.)

A Bayes-optimal predictor has no pesky constraints on the form of function it's going to be,
so it can just give an arbitrary different prediction for each $x$.
Let $\mathcal F(x)$ denote the conditional distribution of $y$ for a given $x$ under $\dist$:
if $\dist$ is deterministic, this won't be a very interesting distribution (a point mass), but in general it might be more complicated.

\begin{qlist}
    \item \pts{10}
    Argue that if $h$ and $g$ are predictors such that for every $x$, $\E_{y \sim \mathcal F(x)} \lambda(h(x), y) \le \E_{y \sim \mathcal F(x)} \lambda(g(x), y)$,
    then we necessarily have that $L_\dist(h) \le L_\dist(g)$.
    \begin{answer}\textcolor{red}{TODO}\end{answer}
\end{qlist}

Thus, we can find a generic Bayes-optimal predictor according to
\[
    f_{\dist,\lambda}(x) \in \argmin_{\hat y \in \hat\cY} \E_{y \sim \mathcal F(x)} \lambda(\hat y, y)
.\]

\begin{qlist}[resume]
    \item \pts{5}
    Use the above formulation to argue that
    \[
        f_{\dist,\mathit{0-1}}(x) = \begin{cases}
            1 & \text{if } \Pr_{y \sim \mathcal F(x)}(y = 1) \ge \frac12 \\
            0 & \text{otherwise}
        \end{cases}
    \]
    is Bayes-optimal for binary classification problems with 0-1 loss.
    \begin{answer}\textcolor{red}{TODO}\end{answer}

    \item \pts{5}
    Use the above formulation to
    derive the Bayes-optimal predictor for a binary classification problem with the loss of an ``is this mushroom edible'' classifier:
    \[
        \lambda(\hat y, y) = \begin{cases}
            0    & \text{if } \hat y = y \\
            0.01 & \text{if } \hat y = 0 \ne y = 1 \\
            1    & \text{if } \hat y = 1 \ne y = 0 \\
        \end{cases}
    .\]
    \begin{answer}\textcolor{red}{TODO}\end{answer}

    \item \pts{5}
    Use the above formulation to argue that
    \[
        f_{\dist,\mathit{sq}}(x) = \E_{y \sim \mathcal F(x)} y
    \]
    is Bayes-optimal for scalar regression problems with squared loss $\lambda(\hat y, y) = (\hat y - y)^2$.
    \begin{answer}\textcolor{red}{TODO}\end{answer}
\end{qlist}

\end{document}
