% This template was designed by Victor Lin (victorlin@cs.stanford.edu) with edits by Lisa Yan.
% You should compile this with PDFLaTeX (default), not XeLaTeX.

% This is a comment!

% This is the document declaration
\documentclass[12pt]{article}

% these are some useful packages. these add functionality to your document
\usepackage{newtxtext} % sets font
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathdots}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
%\usepackage[margin=1in]{geometry}
\usepackage{multicol}
\usepackage{bm}
\usepackage{listings}
\PassOptionsToPackage{usenames,dvipsnames}{color}  %% Allow color names
\usepackage{pdfpages}
\usepackage{algpseudocode}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage[T1]{fontenc}
\usepackage{inconsolata}
\usepackage{framed}
\usepackage[thinlines]{easytable}
\usepackage{minted}
\def\code#1{\texttt{#1}} % add some code in-line
\usepackage{mdframed}
\usepackage{colortbl}
\usepackage{makecell}
\usepackage{amsmath}  % math symbols
\usepackage{wrapfig}  % in case you want to use a figure
\usepackage{hyperref} % add hyper links

% This package controls the margins of the page.
\usepackage[top=1in, bottom=1in, left=0.8in, right=1in]{geometry}

\usepackage{multicol} % in case you want to use multiple columns
\setlength{\columnsep}{0.1pc}

% document headers!
\title{CS 109: Probability for Computer Scientists\\Problem Set\#6}
\author{author} % Change this to your name!
\date{\today} % today does the right thing

\lhead{author}
\chead{Problem Set \#6}
\rhead{\today}

\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\absfit}[1]{\left\lvert #1 \right\rvert}
\newcommand{\norm}[1]{\left\lVert #1 \right\rVert}
\newcommand{\eval}[3]{\left[#1\right]_{#2}^{#3}}
\renewcommand{\(}{\left(}
\renewcommand{\)}{\right)}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\pd}[1]{\frac{\partial}{\partial #1}}
\newcommand{\inner}[1]{\langle#1\rangle}
\newcommand{\cond}{\bigg|}
\newcommand{\rank}[1]{\mathbf{rank}(#1)}
\newcommand{\range}[1]{\mathbf{range}(#1)}
\newcommand{\nullsp}[1]{\mathbf{null}(#1)}
\newcommand{\repr}[1]{\left\langle#1\right\rangle}

\DeclareMathOperator{\Var}{Var}
\newcommand{\SD}{\operatorname{SD}}
\newcommand{\Cov}{\operatorname{Cov}}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Tr}{\mathbf{Tr}}
\DeclareMathOperator{\diag}{\mathbf{diag}}
\DeclareMathOperator{\dist}{\mathbf{dist}}
\DeclareMathOperator{\prob}{\mathbf{prob}}
\DeclareMathOperator{\dom}{\mathbf{dom}}
\DeclareMathOperator{\E}{\mathbf{E}}
\DeclareMathOperator{\R}{\mathbb{R}}
\DeclareMathOperator{\var}{\mathbf{var}}
\DeclareMathOperator{\quartile}{\mathbf{quartile}}
\DeclareMathOperator{\conv}{\mathbf{conv}}
\DeclareMathOperator{\VC}{VC}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\newcommand{\Uni}{\operatorname{Uni}}
\newcommand{\Ber}{\operatorname{Ber}}
\newcommand{\Bin}{\operatorname{Bin}}
\newcommand{\Geo}{\operatorname{Geo}}
\newcommand{\NegBin}{\operatorname{NegBin}}
\newcommand{\Zipf}{\operatorname{Zipf}}
\newcommand{\HypG}{\operatorname{HypG}}
\newcommand{\Poi}{\operatorname{Poi}}
\newcommand{\Beta}{\operatorname{Beta}}
\newcommand{\Normal}{\operatorname{\mathcal{N}}}
\newcommand{\N}{\operatorname{\mathcal{N}}}
\newcommand{\Exp}{\operatorname{Exp}}
\DeclareMathOperator{\NP}{\mathbf{NP}}
\DeclareMathOperator{\coNP}{\mathbf{coNP}}
\DeclareMathOperator{\TIME}{\mathsf{TIME}}
\DeclareMathOperator{\polytime}{\mathbf{P}}
\DeclareMathOperator{\PH}{\mathbf{PH}}
\DeclareMathOperator{\SIZE}{\mathbf{SIZE}}
\DeclareMathOperator{\ATIME}{\mathbf{ATIME}}
\DeclareMathOperator{\SPACE}{\mathbf{SPACE}}
\DeclareMathOperator{\ASPACE}{\mathbf{ASPACE}}
\DeclareMathOperator{\NSPACE}{\mathbf{NSPACE}}
\DeclareMathOperator{\Z}{\mathbb{Z}}
\DeclareMathOperator{\EXP}{\mathbf{EXP}}
\DeclareMathOperator{\NEXP}{\mathbf{NEXP}}
\DeclareMathOperator{\NTIME}{\mathbf{NTIME}}
\DeclareMathOperator{\DTIME}{\mathbf{DTIME}}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\BPP}{\mathbf{BPP}}
\DeclareMathOperator{\ZPP}{\mathbf{ZPP}}
\DeclareMathOperator{\RP}{\mathbf{RP}}
\DeclareMathOperator{\coRP}{\mathbf{coRP}}
\DeclareMathOperator{\BPL}{\mathbf{BPL}}
\DeclareMathOperator{\IP}{\mathbf{IP}}
\DeclareMathOperator{\PSPACE}{\mathbf{PSPACE}}
\DeclareMathOperator{\NPSPACE}{\mathbf{NPSPACE}}
\DeclareMathOperator{\SAT}{\mathsf{SAT}}
\DeclareMathOperator{\NL}{\mathbf{NL}}
\DeclareMathOperator{\PCP}{\mathbf{PCP}}
\DeclareMathOperator{\PP}{\mathbf{PP}}
\DeclareMathOperator{\cost}{cost}
\let\Pr\relax
\DeclareMathOperator*{\Pr}{\mathbf{Pr}}

\usepackage{booktabs}
\usepackage{diagbox}
  % configure display of tables
\newcommand{\ra}[1]{\renewcommand{\arraystretch}{#1}}
\newcommand\tab[1][1cm]{\hspace*{#1}}
\newcommand\tabhead[1]{\small\textbf{#1}}

\theoremstyle{definition}
\newtheorem*{answer}{Answer}

\definecolor{shadecolor}{gray}{0.95}

\setlength{\parindent}{0pt}

\pagestyle{fancy}
\setlength{\headheight}{15pt}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

% begin the document
\begin{document}

% actually insert the title.
\maketitle
  
\begin{enumerate}
% 1
\item Consider the Exponential distribution. It is your friend \dots really. Specifically, consider a sample of I.I.D.\ exponential random variables $X_1, X_2, \dotsc, X_n$, where each $X_i \sim \Exp(\lambda)$.  

    \begin{enumerate}[label=\alph*.]

    \item Derive the maximum likelihood estimate for the parameter $\lambda$ in the Exponential distribution.

    \item Is the estimator you derived in part (a) biased?  You should give a ``yes'' or ``no'' answer and a short informal justification for your answer.  A formal derivation/proof is not needed. (Hint: Johan Jensen might be interested in your answer).

    \end{enumerate}

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
    \newpage


% 2
\item Say you have a set of binary input features/variables $X_1, X_2, \dotsc, X_m$ that can be used to make a prediction about a discrete binary output variable $Y$ (i.e., each of the $X_i$ as well as $Y$ can only take on the values 0 or 1). Say that the first $k$ input variables $X_1, X_2, \dotsc, X_k$ are actually all identical copies of each other, so that when one has the value 0 or 1, they all do.  Explain informally, but precisely, why this may be problematic for the model learned by the Na\"{i}ve Bayes classifier.

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
    \newpage


% 3
\item 
Consider this 4-neuron neural network that is trained on $n$ datapoints $(x^{(i)}, y^{(i)})$:


% to include this image with your code:
% 1) download the website image: http://web.stanford.edu/class/cs109/img/psets/pset6_neuralnet_figure.pdf
% 2) save the PDF image to the same folder as this file (e.g., upload to overleaf)
% otherwise just comment out everything from \begin{figure} to \end{figure}.
\begin{figure}[h]
\centering
\includegraphics[width=\textwidth]{pset6_neuralnet_figure}
\end{figure}

\begin{enumerate}
\item Calculate the gradients of the log-likelihood function with respect to all four parameters.

\item Explain in a few sentences how you could use the function that you calculated in part (a) to train the neural network.
\end{enumerate}

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
    \newpage


% 4
\item Implement the Na\"{i}ve Bayes classifier for binary input/output data.  Specifically, your classifier should make predictions for the output variable using the rule: $ \hat{Y} = \underset{y}{\operatorname{argmax }} P({\bf X} | Y) P(Y)$, by employing the Na\"{i}ve Bayes assumption, which states that:

\[ P({\bf X} | Y) = P(X_1, X_2, \dots X_m | Y) = \prod_{i=1}^{m} P(X_i | Y). \]

Thus, your program will need to estimate the values $P(Y)$ as well as $P(X_i \| Y)$ for all $1 \leq i \leq m$ from the training data.  Note that to estimate the probability mass function $P(X_i \| Y)$, you will need to estimate both $P(X_i \| Y = 0)$ and $P(X_i \| Y = 1)$.
\begin{enumerate}[label=\alph*.]

    \item Train your algorithm on the data file \texttt{simple-train.txt}.  Test your algorithm on the data file \texttt{simple-test.txt} and report your classification accuracy.  Run your algorithm twice---once with Maximum Likelihood Estimators (MLE) and once with Laplace Estimatiors.  As a sanity check, you should be able to achieve 100\% classification accuracy on the testing data using a model trained with MLE.

    \item Train your algorithm on the data file \texttt{netflix-train.txt}.  Test your algorithm on the data file \texttt{netflix-test.txt}.  Run your algorithm twice---once with MLE and once with Laplace Estimators. For both versions of Na\"ive Bayes, answer the following questions:
    
    \begin{enumerate}[label=\roman*.]
    \item What is your estimate for $P(Y=1)$?
    \item For all values of $i$, what is your estimate $P(X_i = 1| Y = 0)$?
    \item For all values of $i$, what is your estimate $P(X_i = 1 | Y = 1)$?
    \item Report your classification accuracy for both MLE and Laplace estimators.
    \end{enumerate}
    
    \item For Na\"ive Bayes trained on \texttt{netflix-train.txt} with an MLE estimator, answer the following questions:
    \begin{enumerate}[label=\roman*.]
    \item Using the probabilities that you estimated for Na\"ive Bayes, decide which five movies are the most indicative that a user will like \textit{Love Actually}. In other words, for which five movies is the ratio $P(Y = 1| X_ i = 1) / P(Y = 1 | X_i = 0)$ the largest?
    \item Give one example of a misprediction. Try to explain what went wrong.
    \end{enumerate}

	\item Train your algorithm on the data file \texttt{ancestry-train.txt}. Test your algorithm on the data file \texttt{ancestry-test.txt} and report your classification accuracy. Again, remember to do this once with MLE and once with Laplace Estimators. 
	
	\item Train your algorithm on the data file \texttt{heart-train.txt}. Test your algorithm on the data file \texttt{heart-test.txt} and report your classification accuracy.  Again, remember to do this once with MLE and once with Laplace Estimators. 

    \item Make sure to turn in a copy of your code for the Na\"{i}ve Bayes classifier in a zip with all of your code for this problem set.

\end{enumerate}

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
    \newpage


% 5
\item Implement Logistic Regression for binary input/output data. Specifically, you should implement the gradient ascent algorithm described in class.

Note that you will need to use an exponential function ($e^x$) to implement Logistic Regression. In Python, you will find the function \texttt{exp(x)} from the \texttt{math} library helpful.

\begin{enumerate}[label=\alph*.]

\item Train your algorithm on the data file \texttt{simple-train.txt}. Use learning rate $\eta = 0.0001$ and $10,000$ training steps.  Test your algorithm on the data file \texttt{simple-test.txt} and report your classification accuracy. You should be able to achieve 100\% classification accuracy on the testing data.

    \item Train your algorithm on the data file \texttt{netflix-train.txt}. Use learning rate $\eta = 0.0001$ and $3,000$ training steps. Test your algorithm on the data file \texttt{netflix-test.txt}, then answer the following questions:
    
    \begin{enumerate}[label=\roman*.]
    \item Report your final parameter weights after training.
    \item Report your classification accuracy.
    \item According to the weights of your logistic regression function, which five movies are the strongest predictors that a user will like \textit{Love Actually}?
    \item What is the log-likelihood of the training data when all of the parameters are 0?
    \item What is the log-likelihood of the training data after training?
    \end{enumerate}
    
	\item Train your algorithm on the data file \texttt{ancestry-train.txt}. Use learning rate $\eta = 0.0001$ and $10,000$ training steps. Test your algorithm on the data file \texttt{ancestry-test.txt} and report your classification accuracy.
	
	\item Train your algorithm on the data file \texttt{heart-train.txt}. Experiment with using different learning rates $\eta$, where you are still testing your algorithm on the data file \texttt{heart-test.txt}. Each time use $10,000$ training steps. As a starting point for experimenting, try $\eta = 0.0005$ and $\eta = 0.00002$ (i.e., values for $\eta$ that are larger and smaller than $0.0001$ by a factor of 5), and then continue experimenting from there. Report the highest classification accuracy you could obtain on the testing data, as well as what was the value of the learning rate $\eta$ you used to obtain it. Explain why you think the learning rate had such an effect on your classification accuracy.
	
    \item Make sure to turn in a copy of your code for Logistic Regression in a zip with all of your code for this problem set. 

\end{enumerate}

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
    \newpage


% 6
\item \textbf{[Extra Credit]} For extra credit, try to write a simple neural network algorithm (or even train a Bayesian Network). Train on the data file \texttt{netflix-train.txt}. Report the maximum accuracy that you were able to obtain for the data file \texttt{netflix-test.txt}.

    \begin{shaded}
    \begin{answer}

    \end{answer}
    \end{shaded}
    \newpage



\end{enumerate}


\end{document}
  