\documentclass{article}

\usepackage{fullpage}
\usepackage{color}
\usepackage{amsmath}
\usepackage{url}
\usepackage{verbatim}
\usepackage{graphicx}
\usepackage{parskip}
\usepackage{amssymb}
\usepackage{nicefrac}
\usepackage{listings} % For displaying code
\usepackage{algorithm2e} % pseudo-code

% Answers
\def\ans#1{\par\gre{Answer: #1}}

% Colors
\definecolor{blu}{rgb}{0,0,1}
\def\blu#1{{\color{blu}#1}}
\definecolor{gre}{rgb}{0,.5,0}
\def\gre#1{{\color{gre}#1}}
\definecolor{red}{rgb}{1,0,0}
\def\red#1{{\color{red}#1}}
\def\norm#1{\|#1\|}

% Math
\def\R{\mathbb{R}}
\def\argmax{\mathop{\rm arg\,max}}
\newcommand{\argmin}[1]{\mathop{\hbox{argmin}}_{#1}}
\newcommand{\mat}[1]{\begin{bmatrix}#1\end{bmatrix}}
\newcommand{\alignStar}[1]{\begin{align*}#1\end{align*}}
\def\half{\frac 1 2}
\def\cond{\; | \;}

% LaTeX
\newcommand{\fig}[2]{\includegraphics[width=#1\textwidth]{a4f/#2}}
\newcommand{\centerfig}[2]{\begin{center}\includegraphics[width=#1\textwidth]{a4f/#2}\end{center}}
\def\items#1{\begin{itemize}#1\end{itemize}}
\def\enum#1{\begin{enumerate}#1\end{enumerate}}


\begin{document}

\title{CPSC 540 Assignment 4 (due March 14 at midnight)}
\author{}
\date{}
\maketitle
\vspace{-4em}

The assignment instructions are the same as for the previous assignment.


\blu{\enum{
\item Name(s):
\item Student ID(s):
}}



\section{Discrete Markov Chains}

\subsection{Sampling, Inference, and Decoding}

The function \emph{example\_markovChain.jl} loads the initial state probabilities and transition probabilities for three Markov chain models on $d$ binary variables,
\[
p(x_1,x_2,\dots,x_d) = p(x_1)\prod_{j=2}^{d}{p(x_j\cond x_{j-1})}.
\]
It then finds the optimal decoding (the most likely assignment to the variables $\{x_1,x_2,\dots,x_d\}$) in the first two chains. In the demo, decoding is done by enumerating all possible assignments to the variables. This works for the first two chains as they only have 4 variables, but is too slow to decode the last chain because it has 31 variables. In this question you'll explore two ways to estimate the marginals in the third Markov chain and two ways to estimate the most-probable sequence (you only need to report results on the third Markov chain for this question, but the first two may be helpful for debugging).

\enum{
\item Write a function, \emph{sampleAncestral.m}, that uses ancestral sampling to sample a sequence $x$. \blu{Hand in this code and report all the univariate marginal probabilities using a Monte Carlo estimate based on 10000 samples.}
\item Write a function, \emph{marginalCK.m}, that uses the CK equations to compute the exact univariate marginals. \blu{Hand in this code, report all exact univariate marginals, and report how this differs from the marginals in the previous question.}
\item Write a function, \emph{viterbiDecode.m}, that implements the Viterbi decoding algorithm for Markov chains. \blu{Hand in this code and report the optimal decoding of the third Markov chain, and how this differs from the sequence defined by the most likely state at each time (the states maximizing the marginal probabilities)}.
}
Hint: for parts 2-3, you can use a $2$ by $d$ matrix $M$ to represent the dynamic programming table, and for part 3 you can use another matrix $B$ containing the argmax values that lead to each entry in the table. 


\subsection{Simple  Conditioniing Queries}

The long sequence from the previous question usually starts with state 1 and most of the time ends in state 2. In this question you'll consider conditioning on these events not happening. First, compute the following quantities which can be done using your functions from the previous question:
\enum{
\item \blu{Report all the univariate conditional probabilities $p(x_j \cond  x_1 = 2)$ obtained using a Monte Carlo estimate based on 10000 samples}.
\item \blu{Report all the exact univariate conditionals $p(x_j \cond  x_1 = 2)$.}
\item \blu{Report the sequence beginning with $x_1=2$ that has the highest probability. How does this differ from the (unconditional) optimal decoding?}
\item \blu{Report the sequence ending with $x_d=1$ that has the highest probability. How does this differ from the (unconditional) optimal decoding?}
}
Hint: these conditions can be done by changing the input to the functions from the previous question.

\subsection{Conditioning Queries Requiring Inference}

Next consider the following cases (which require implementing an extra rejection step or backward phase):
\enum{
\item \blu{Report all the univariate conditional probabilities $p(x_j \cond  x_d = 1)$ obtained using a Monte Carlo estimate based on 10000 samples and rejection sampling. Also report the number of samples accepted among the 10000 samples.}
\item Write a function, \emph{sampleBackwards.m} that uses backwards sampling to sample sequences where $x_d = 1)$. \blu{Hand in this code and report all the univariate conditional probabilities $p(x_j \cond  x_d = 1)$ obtained using a Monte Carlo estimate based on 10000 samples}.
\item Write a function, \emph{forwardBackwards.m} that is able compute all exact univariate conditionals $p(x_j \cond  x_d = 1)$ in $O(dk^2)$. \blu{Hand in the code and report all the exact univariate conditionals $p(x_j \cond  x_d = 1)$.}
}

\section{Directed Acyclic Graphical Models}


\subsection{D-Separation}

Consider a  directed acyclic graphical (DAG) model with the following graph structure:
\centerfig{.4}{DAG}

Assuming that the conditional independence properties are faithful to the graph, using d-separation \blu{briefly explain why the following are true or false:}
\begin{enumerate}
\item $B \perp F$.
\item $B \perp F \; \cond  \; A$ .
\item $B \perp F \; \cond  \; C$.
\item $B \perp F \; \cond  \; E$.
\item $B \perp F \; \cond  \; I$.
\item $B \perp F \; \cond  \; J$.
\item $B \perp F \; \cond  \; C,E$.
\end{enumerate}



\subsection{Exact Inference}


While DAGs can be used as a visual representation of independence assumptions, they can also be used to simplify computations. This question will give you practice using the basic properties which allow efficient computations in graphical models.
Consider the DAG model below, for distinguishing between different causes of shortness-of-breath (dyspnoea) and the causes of an abnormal lung x-ray, while  modelling potential causes of these diseases too (whether the person is a smoker or had a `visit' to a country with a high degree of tuberculosis).

\centerfig{.7}{bayesNet}


For this question, let's assume that we use the following parameterization of the network:
\begin{align*}
\text{Visit}\\
p(V = 1) & = 0.01\\
\text{Smoking}\\
p(S = 1) & = 0.2\\
\text{Tuberculosis}\\
p(T = 1 \cond  V = 1) & = 0.05\\
p(T = 1 \cond  V = 0) & = 0.01\\
\text{Lung Cancer}\\
p(L = 1 \cond  S = 1) & = 0.10\\
p(L = 1 \cond  S = 0) & = 0.01\\
\text{Bronchitis}\\
p(B = 1 \cond  S = 1) & = 0.60\\
p(B = 1 \cond  S = 0) & = 0.30\\
\text{Abnormal X-Ray}\\
p(X = 1 \cond  T = 1, L = 1) & = 1.00\\
p(X = 1 \cond  T = 1, L = 0) & = 0.98\\
p(X = 1 \cond  T = 0, L = 1) & = 0.9\\
p(X = 1 \cond  T = 0, L = 0) & = 0.05\\
\end{align*}
\begin{align*}
\text{Dyspnoea}\\
p(D = 1 \cond  T = 1, L = 1, B = 1) & = 0.90\\
p(D = 1 \cond  T = 1, L = 1, B = 0) & = 0.70\\
p(D = 1 \cond  T = 1, L = 0, B = 1) & = 0.85\\
p(D = 1 \cond  T = 1, L = 0, B = 0) & = 0.65\\
p(D = 1 \cond  T = 0, L = 1, B = 1) & = 0.82\\
p(D = 1 \cond  T = 0, L = 1, B = 0) & = 0.60\\
p(D = 1 \cond  T = 0, L = 0, B = 1) & = 0.80\\
p(D = 1 \cond  T = 0, L = 0, B = 0) & = 0.10\\
\end{align*}

\blu{Compute the following quantities} (hints are given on the right, and these will be easier to do in order and if you use conditional independence properties to simplify the calculations):
\enum{
\item$ p(S = 0) $ (negation of marginal of root node; use sum to one constraint).
\item$ p(L = 1) $ (marginal of child node; marginalize over parent).
\item$p(X = 1 \cond  T = 1) $ (conditional of child with missing parent; marginalize over missing parent).
\item$ p(X=1\cond T=1,S=1) $ (conditional of child given parent and grand-parent, marginalize over missing parent).
\item$ p(X = 1) $ (marginal of leaf node; marginalize over parents and use independence to simplify).
\item$ p(T = 1 \cond  X = 1)$ (conditional of parent given child; use Bayes rule).
\item$ p(T = 1 \cond  L = 1) $ (conditional of parent given co-parent; use independence and then marginal).
\item$p(T = 1 \cond  X = 1, L = 1)$ (conditional of parent given child and co-parent; use Bayes rule).
}



\subsection{Inpainting}


The function \emph{example\_fil.jl} loads a variant of the MNIST dataset. It contains all the training images but the test images are missing their bottom half. Running this function fits an independent Bernoulli model to the training set, and then shows the result of applying the density model to ``fill in'' four random test examples. It performs pretty badly because the independent model can't condition on the known top-half of the images.
\enum{
\item Make a variant of the demo where you fit an inhomogeneous Markov chain to each image column. \blu{Hand in your code and an example of using this model to fill in 4 random test images.}
\item Make a variant of the demo where you fit a directed acyclic graphical model to the data, using general discrete conditional probabilities and where the parents of pixel $(i,j)$ are the other 8 pixels in the region $(i-2:i,j-2:j)$.
\blu{Hand in your code and an example of using this model to fill in 4 random test images.}
\item Make a variant of the demo where you fit a sigmoid belief network to the data, where the parents of pixel $(i,j)$ are the other pixels in the region $(1:i,1:j)$.
\blu{Hand in your code and an example of using this model to fill in 4 random test images.}
}



\section{Very-Short Answer Questions}


Give a short and concise 1-sentence answer to the below questions.
\enum{
\item What are two reasons that we might want to be able to sample from a distribution?
\item What is the inverse transform method used for?
\item Describe how we could use ancestral sampling to sample from a naive Bayes model.
\item What is the cost of generating a sample from a Markov chain of length $d$ with $k$ possible states for each time? What is the cost of decoding?
\item Suppose we have a black-box procedure for sampling from a student $t$ distribution. Describe how we could use this black box to get an approximation of the variance of the distribution.
\item What is the difference between inference and decoding in Markov chains?
\item What is ``explaining away''?
\item If two variables are not d-separated, are they necessarily depenent? If two variables are d-separated, are they necessarily independent?
\item Why do we enforce that DAG models are acyclic?
\item What is the relationship between multivariate Gaussians and UGMs?
\item For each of the following, name a method we covered in class that applies for UGMs:
\enum{
\item Approximate decoding.
\item Approximate sampling.
\item Approximate inference.
} 
}

\section{Relevant Papers for Project}

\subsection{Finding Relevant Papers}

To help you make progress on your project, for this part you should \blu{hand in a list of 10 academic papers} related to your current project topic. Finding related work is often one of the first steps towards getting a new project started, and it gives you an idea of what has (and has not) been explored. Some strategies for finding related papers are:
\enum{
\item Use Google: try the keywords you think are most relevant. Asking people in your lab (or related labs) for references is also often a good starting point.
\item Once you have found a few related papers, read their introduction section to find references that these papers think are worth mentioning.
\item Once you have found a few related papers, use Google Scholar to look through the list of references that are \emph{citing} these papers. You may have to do some sifting if there are a lot of citations. Reasonable criteria to sift through large reference lists include looking for the ones with the most citations or focusing on the more recent ones (then returning to Step 2 to find the more-relevant older references).
}
For this question you only need to provide a list, but in Assignment 5 you will have to do a survey of 10 papers. So it's worth trying to identify papers that are both relevant and important at this point.
For some types of projects it will be easier to find papers than others. If you are having trouble, post on Piazza.

Although the papers do not need to all be machine learning papers, the course project does need to be related to machine learning in some way, so at least a subset of the papers should be machine learning papers. Here is a rough guide to some of the most reputable places to where you see machine learning works published:
\items{
\item The International Conference on Machine Learning (ICML) and the conference on Advances in Neural Information Processing (NIPS) are the top places to publish machine learning work. The Journal of Machine Learning Research (JMLR) is the top journal, although in this field conference publications are usually viewed as more prestigious.
\item Other good venues include AISTATS (emphasis on statistics), UAI (emphasis on graphical models), COLT (emphasis on theory), ICLR (emphasis on deep learning), ECML-PKDD (European version of ICML), CVPR and ICCV/ECCV (emphasis on computer vision), ACL and EMNLP (emphasis on language), KDD (emphasis on data mining),  AAAI/IJCAI (emphasis on AI more broadly), JRSSB and Annals of Stats (emphasis on statistics more broadly), and Science and Nature (emphasis on science more broadly).
}

\subsection{Paper Review}

Among your list of 10 papers, choose one paper and \blu{write a review of this paper}. It makes sense to choose a paper that is closely-related to your project or to choose one of the most important-looking papers. The review should have two parts:
\enum{
\item A short summary of the contributions of the paper. Say what problem the paper is addressing, why this is an important problems, what is proposed, and how it is being evaluated.
\item A list of strengths and weaknesses of the paper, and whether the claims are appropriately evaluated. For ideas of what issues to discuss, see the JMLR guidelines for reviewers:\\
\url{http://www.jmlr.org/reviewer-guide.html}
}
Note that you should include a non-empty list of strengths \emph{and} weaknesses. 
Many students when doing their first reviews focus either purely on strengths or purely on weaknesses. It's important to recognize that all papers have weaknesses or limitations (even ones written by famous people or that are published in impressive places or that proved to be historically important) and all papers have strengths or at least a motivation (the authors must have thought it was worth writing for some reason).


 
\end{document}