MiniProjectReport.tex

\documentclass{article}

\usepackage[table]{xcolor}
\usepackage{fancyhdr}
\usepackage{graphicx}
\graphicspath{ {images/} }
\usepackage{extramarks}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{tikz}
\usepackage[plain]{algorithm}
\usepackage{algpseudocode}
\usepackage{bbm}

\usetikzlibrary{automata,positioning}

%
% Basic Document Settings
%

\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in

\linespread{1.1}

\pagestyle{fancy}
\lhead{\hmwkAuthorName}
\chead{\hmwkTitle}
\rhead{\firstxmark}
\lfoot{\lastxmark}
\cfoot{\thepage}

\renewcommand\headrulewidth{0.4pt}
\renewcommand\footrulewidth{0.4pt}

\setlength\parindent{0pt}

%
% Create Exercise Sections
%

\newcommand{\enterExerciseHeader}[1]{
    \nobreak\extramarks{}{Question \arabic{#1} continued on next page\ldots}\nobreak{}
    \nobreak\extramarks{Question \arabic{#1} (continued)}{Question \arabic{#1} continued on next page\ldots}\nobreak{}
}

\newcommand{\exitExerciseHeader}[1]{
    \nobreak\extramarks{Question \arabic{#1} (continued)}{Question \arabic{#1} continued on next page\ldots}\nobreak{}
    \stepcounter{#1}
    \nobreak\extramarks{Question \arabic{#1}}{}\nobreak{}
}

\setcounter{secnumdepth}{0}
\newcounter{partCounter}
\newcounter{homeworkExerciseCounter}
\setcounter{homeworkExerciseCounter}{1}
\nobreak\extramarks{Question \arabic{homeworkExerciseCounter}}{}\nobreak{}

\newenvironment{homeworkExercise}{
    \section{Question \arabic{homeworkExerciseCounter}}
    \setcounter{partCounter}{1}
    \enterExerciseHeader{homeworkExerciseCounter}
}{
    \exitExerciseHeader{homeworkExerciseCounter}
}

%
% Homework Details
%   - Title
%   - Due date
%   - Class
%   - Section/Time
%   - Instructor
%   - Author
%

\newcommand{\hmwkTitle}{Mini Project}
\newcommand{\hmwkDueDate}{December 8, 2017}
\newcommand{\hmwkClass}{Introduction to Graphical Models}
\newcommand{\hmwkClassTime}{}
\newcommand{\hmwkClassInstructor}{Taught by Assisitant Professor Umut Simsekli}
\newcommand{\hmwkAuthorName}{Pengfei MI, Rui SONG, Yanting LI}

%
% Title Page
%

\title{
    \vspace{2in}
    \textmd{\textbf{\hmwkClass:\ \hmwkTitle}}\\
    \normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate\ at 11:55 pm}\\
    \vspace{0.1in}\large{\textit{\hmwkClassInstructor\ \hmwkClassTime}}
    \vspace{3in}
}

\author{\textbf{\hmwkAuthorName}}
\date{}

\renewcommand{\part}[1]{\textbf{\large Part \Alph{partCounter}}\stepcounter{partCounter}\\}

%
% Various Helper Commands
%

% Useful for algorithms
\newcommand{\alg}[1]{\textsc{\bfseries \footnotesize #1}}

% For derivatives
\newcommand{\deriv}[1]{\frac{\mathrm{d}}{\mathrm{d}x} (#1)}

% For partial derivatives
\newcommand{\pderiv}[2]{\frac{\partial}{\partial #1} (#2)}

% Integral dx
\newcommand{\dx}{\mathrm{d}x}

% Alias for the Solution section header
\newcommand{\solution}{\textbf{\large Solution}}

% Probability commands: Expectation, Variance, Covariance, Bias
\newcommand{\E}{\mathrm{E}}
\newcommand{\Var}{\mathrm{Var}}
\newcommand{\Cov}{\mathrm{Cov}}
\newcommand{\Bias}{\mathrm{Bias}}

\begin{document}

\maketitle

\pagebreak


\textit{This document is the report for the Mini-Project of the course "Introduction to Graphical Models" of Master 2 Data Science. 
This project is done in group of three, with group members: Pengfei MI, Rui SONG, and Yanting LI.}


\begin{homeworkExercise}
    \textbf{Draw the directed graphical model for the described model.}
    \\
    
    \textbf{Solutions:} \\
    The directed graphical model for our model can be drawn like below
    \begin{figure}[h]
    	\includegraphics[width = 9cm]{Q1}
	\centering
    \end{figure}

\end{homeworkExercise}

\pagebreak

\begin{homeworkExercise}
	\textbf{Construct the transition matrix.}
	\\
	
	\textbf{Solutions:} \\
	Define a variable $\Psi_{n} \equiv [s_{n}, m_{n}, c_{n}]$. The set of all states can be listed in a vector $\Omega$ then the state of the system at pixel $n$ can be represented as $\Psi_{n} = \Omega(j)$ where $j \in \{1, 2, ..., (S\times M\times C)\}$ and $C = max_{s,k}\mathit{l}(s) $ ($=7$ in our model). Then the transition matrix is:
	\begin{equation}
    	\begin{split}
	A(i, j) &= p(\Psi_{n+1} = \Omega(i) | \Psi_{n} = \Omega(j)) \\
	& = p(c_{n+1} = c_{i}, s_{n+1} = s_{i},  m_{n+1} = m_{i} | c_{n} = c_{j}, s_{n} = s_{j},  m_{n} = m_{j}) \\
	& = p(c_{n+1} = c_{i} | c_{n} = c_{j}, s_{n} = s_{j})p(s_{n+1} = s_{i},  m_{n+1} = m_{i} | c_{n} = c_{j}, s_{n} = s_{j},  m_{n} = m_{j}) \\
	& = p(c_{n+1} = c_{i} | c_{n} = c_{j}, s_{n} = s_{j}) p(s_{n+1} = s_{i} | c_{n} = c_{j}, s_{n} = s_{j}, m_{n} = m_{j}) p(m_{n+1} = m_{i} |s_{n+1} = s_{i}, c_{n} = c_{j}, s_{n} = s_{j})\\
	& = \begin{cases}
			\delta(c_{n+1} - c_{n} -1) \delta(s_{n+1} - s_{n}) \delta(m_{n+1} - m_{n}) &\mbox{if $c_{n} \neq \mathit{l}(s_{n})$}\\
			\delta(c_{n+1} -1)\tau(s_{n+1}|s_{n}, m_{n} )\tau(m_{n+1}|s_{n+1}, m_{n}) &\mbox{if $c_{n} = \mathit{l}(s_{n})$}
	       \end{cases}
	\end{split}
     \end{equation}
     where $\tau(s_{n+1}|s_{n}, m_{n} )$ and $\tau(m_{n+1}|s_{n+1}, m_{n})$ are defined in the description.\\
     Then the observation model can be written like: 
     $$p(x_{n} | \Psi_{n}) = \prod_{i=0}^{1} \mathcal{N}(x_{n}; \mu_{i}, \sigma_{i}^{2}) ^{\mathbbm{1}(f(\Psi_{n})=i)}$$
     
     Then the graphical model becomes:
     \begin{figure}[h]
    	   \includegraphics[width = 9cm]{Q2}
	   \centering
     \end{figure}
	
\end{homeworkExercise}

\pagebreak

\begin{homeworkExercise}
	\textbf{Simulate the HMM and visualize the simulated data.}
	\\
	
	\textbf{Solutions:} \\
	The general idea to simulate the HMM model is: for each states $j \in \{1,2, ... , (S\times M\times C)\}$, we generate a random number $r$ according to a uniform distribution in the interval $[0, 1]$. Then we find the state $k$ such that $\sum_{i=1}^{k}A(i,j) < r$ and $\sum_{i=1}^{k+1}A(i,j) >= r$. Then we will transfer from state $j$ to state $i$. \\
	For the code, please look at file $template\_code.ipynb$. The barcode simulated is :
	\begin{figure}[h]
    		\includegraphics[width = 9cm]{Q3}
		\centering
         \end{figure}
         As we can see this looks very much like a real scanline. And the barcode string is "184525950079".
	
\end{homeworkExercise}

\pagebreak

\begin{homeworkExercise}
	\textbf{Fill code part 1, 2, and 3}
	\\
	
	\textbf{Solutions:} \\
	Please refer to file $template\_code.ipynb$.
\end{homeworkExercise}

\pagebreak

\begin{homeworkExercise}
	Compute the filtering distribution and marginals
	\\
	
	\textbf{Solutions:} \\
	The filtering distribution $p(\Psi_{n} | x_{1:n})$ can be got from the Bayesian rule:
$$p(\Psi_{n} | x_{1:n}) = \frac{p(\Psi_{n}, x_{1:n})}{p(x_{1:n})}$$
where $p(\Psi_{n}, x_{1:n})$ is the message $\alpha_{n|n}(\Psi_{n})$ which can be got by forward recursion. Since $x_{1:n}$ is our observation, $p(x_{1:n})$ is therefore a constant. So $p(\Psi_{n} | x_{1:n})$ is the normalization of $p(\Psi_{n}, x_{1:n})$.\\

To compute the marginals $p(s_{n}|x_{1:n})$, $p(c_{n}|x_{1:n})$ and $p(m_{n}|x_{1:n})$, since they are not independent, we need to sum up all $p(\Psi_{n}|x_{1:n})$ with the same $s_{n}$ for computing $p(s_{n}|x_{1:n})$, and the same process for $p(c_{n}|x_{1:n})$ and $p(m_{n}|x_{1:n})$.\\

	Please refer to file $template\_code.ipynb$ part 4.
\end{homeworkExercise}

\pagebreak

\begin{homeworkExercise}
	\textbf{Compute the smoothing distribution and marginals.}
	\\
	
	\textbf{Solutions:} \\
	Similar with the previous question, the smoothing distribution $p(\Psi_{n} | x_{1:N})$ can be got from:
$$p(\Psi_{n} | x_{1:N}) = \frac{p(\Psi_{n}, x_{1:N})}{p(x_{1:N})} \propto p(\Psi_{n}, x_{1:N})$$
by message $\beta_{n|n+1}(\Psi_{n}) \alpha_{n|n}(\Psi_{n})$ via Forward-Backward recursion.\\

The computation of the smoothing distribution of $s_{n}$, $c_{n}$ and $m_{n}$ are also the sum of $p(\Psi_{n} | x_{1:N})$ with the same $s_{n}$, $c_{n}$ and $m_{n}$ respectively.\\

	Please refer to file $template\_code.ipynb$ part 5.
\end{homeworkExercise}

\pagebreak

\begin{homeworkExercise}
	\textbf{Compute the most-likely path by using the Viterbi algorithm.}
	\\
	
	\textbf{Solutions:} \\
	We apply the Viterbi algorithm in backward pass. \\
	That is, for $t \in \{1, 2, ..., T - 1\}$, when we compute $\beta_{t|t} (x_t)$ using $\beta_{t|t+1} (x_t)$, instead of using the sum of terms of all $x_{t+1}$, we keep only the maximum term. At the same time, we also record the argmax in a matrix. After we get the argmax of $x_1$, we generate the most likely path by the argmax matrix.\\
	Please refer to file $template\_code.ipynb$  "Viterbi algorithm" part.\\
\end{homeworkExercise}

\pagebreak

\begin{homeworkExercise}
	\textbf{Run algorithms on different random barcodes.}
	\\
	
	\textbf{Solutions:} \\
	In this question, we tested the program with observation noise 20 and 50. Set $\mu_{0} = 255$, $\mu_{1} = 0$. and $\sigma_{0}^{2} = \sigma_{1}^{2} = 1$.\\

With obs\_noise = 20, we generated the following barcode:\\
\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=8cm]{n20_bar}
\end{center}
\end{figure}

The filtering distribution, smoothing distribution and the most-likely path are shown below:
\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=8cm]{n20_filtering}
\end{center}
\end{figure}

\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=8cm]{n20_smoothing}
\end{center}
\end{figure}

\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=8cm]{n20_mlp}
\end{center}
\end{figure}

With obs\_noise = 80:
\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=8cm]{n80_bar}
\end{center}
\end{figure}

\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=8cm]{n80_filtering}
\end{center}

\end{figure}\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=8cm]{n80_smoothing}
\end{center}
\end{figure}

\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=8cm]{n80_mlp}
\end{center}
\end{figure}

When the noise is increased, in both filtering and smoothing distribution, the result becomes more "ambiguous". In each state, a specific result is got "later" than the previous case with a smaller noise.\\
\end{homeworkExercise}


\end{document}