\documentclass[11pt]{article}
\usepackage{geometry}                % See geometry.pdf to learn the layout options. There are lots.
\geometry{letterpaper}                   % ... or a4paper or a5paper or ...
%\geometry{landscape}                % Activate for for rotated page geometry
%\usepackage[parfill]{parskip}    % Activate to begin paragraphs with an empty line rather than an indent
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{epstopdf}
\usepackage{url}
\usepackage{verbatim}
\usepackage{moreverb}
\let\verbatiminput=\verbatimtabinput
\def\verbatimtabsize{4\relax}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}

\title{BigML Assignment 4: Naive Bayes and Phrases on Hadoop}
\author{Naive Bayes Part Due Wednesday, February 27, 2013 via Blackboard\\Phrase Finding Part Due Wednesday, March 6, 2013 via Blackboard}
\date{Out February 13, 2013}
\begin{document}
\maketitle

\section{Important Note}
As usual, {\bf you are expected to use Java for this assignment}.

{\bf This assignment is worth a total of 200 points} because there are conceptually two assignments here: the Hadoop implementation of Naive Bayes (Assignment 2) and the Hadoop implementation of Phrase finding (Assignment 3). If you choose not to do this assignment, you will be counted as missing \textbf{two} assignments. If you choose to do only one of the two assignments, either Hadoop Naive Bayes, or Hadoop phrase finding, you will be counted as missing \textbf{one} assignment.

Bin Zhao (binzhao@cs.cmu.edu) is the contact TA for Hadoop naive Bayes, and Yanbo Xu (yanbox@cs.cmu.edu) is the contact TA for Hadoop phrase finding. Please post clarification questions to the Google Group:  \\
\url{machine-learning-with-large-datasets-10-605-in-spring-2013}


\section{Introduction}
For this assignment, you will re-implement Phrase finding and Naive Bayes (Assignments 2 and 3) for the Hadoop Mapreduce framework.  You are free (and encouraged) to reuse your code from those assignments.

\section{Getting started}
\subsection{Installing Hadoop Virtual Appliance (Optional)}
You may install a Hadoop virtual appliance on your own machine for ease of debugging, however, this step is optional, and you can directly run your code on Andrew cluster or AWS.

Cloudera has offered a single node virtual appliance. Follow the instructions on the page \url{https://ccp.cloudera.com/display/SUPPORT/Cloudera%27s+Hadoop+Demo+VM+for+CDH4} to download the image and also VMware Player (for Windows and Linux) or VMware Fusion (for Mac). Start up the VM. Inside the VM, Hadoop is running in what's called "pseudo-distributed mode", which means that all the daemon processes are running on the same machine and communicating via loopback.


\subsection{Using AWS}
We have distributed AWS credits to every registered student. If you have not got one, let us know. Here are a few hints for running jobs on AWS:
\subsubsection{Submitting a Jar job}
The easiest way to submit jobs to AWS is via the commandline.  You need to install the elastic mr command line interface - there are many versions for many different languages.  I used the ruby one and found it to be painless to install/use

\url{http://aws.amazon.com/code/Elastic-MapReduce/2264}

You can also start a job with the AWS console's web interface  - go to the elastic mapreduce tab in your AWS console, click create new jobflow, choose the custom JAR jobtype and the rest is pretty self-explanatory.  I find this takes longer than the command line, but if you�re more comfortable with a GUI, that's fine.

\subsubsection{Viewing job progress}
Tutorial for viewing the jobtracker on your local machine (via proxy)

\url{http://docs.amazonwebservices.com/ElasticMapReduce/latest/DeveloperGuide/UsingtheHadoopUserInterface.html}

(You can also ssh into the machine using the command line interface, and then use the lynx commands in the login preamble to view the job tracker)

\section{The Data}

We are using the data from Assignments 2 \& 3.  They are still on AFS, and they are also in this public s3 bucket:
\url{s3://bigml-shared/phrases} and  \url{s3://bigml-shared/webdocs}

The data format is the same as for Assignments 2 \& 3, with one small change:  The phrase data has format:
\begin{verbatim}
<text>\t<year>\t<text>\t<year>\t<count>
\end{verbatim}
Where text is the unigram/bigram, count is the number of times the text occurred in books during the decade indicated by year.  This change is a byproduct of changing a SequenceFile to a TextFile.  If you ignore the first two fields of the tab-separated line, the format is the same as you saw for Assignment 3.


\section{One Small Change}
In the interest of freshness, this time, use the bigrams/unigrams from the 1960s as your corpus, and those from 1970-1990 as the background corpus.

\section{Deliverables}

Submit a compressed archive (zip, tar, etc) of your code. Please also include the controller and syslog files {\bf from AWS} for each of the mapreduce jobs in both of your pipelines. The controller and syslog files can be downloaded from the AWS console.  Simply go to the Elastic Mapreduce tab.  Click your job in the list, and then the debug button, the syslog link, and save the resulting file.  Please include a pdf document with answers to the questions below.

\paragraph{Part A: Naive Bayes}
\begin{enumerate}
 \item For parallel computing, the optimal speedup gained through parallelization is linear with respect to the number of jobs running in parallel. For example, with 5 reducers, ideally we would expect parallel computing to take 1/5 wall clock time of single machine run. However, this optimal speedup is usually not achievable. In this question, set the number of reducers in your hadoop run to 2, 4, 6, 8, 10, and record the wall clock time. Plot a curve, where the horizontal axis is the number of reducers, and the vertical axis is the wall time. Is the wall time linear with respect to the number of reducers? Explain what you observed.
 \item Set the number of reducers to 10, and run your hadoop job on AWS. Tell us how much it costs to run your job on AWS. 
\end{enumerate}
For the Naive Bayes pipeline, include the controller and syslog files created when you process the full abstracts dataset.  Create a folder called \texttt{naivebayes}.  In it, put the controller and syslog files from each of your Mapreduces, named syslogN and controllerN for $N={1..n}$ where $n$ is the number of Mapreduce jobs in your pipeline. Create a README file briefly describing each of the steps of your pipeline, numbered in the same order as the controller/syslog files.

\paragraph{Part B: Phrase Finding}
\begin{enumerate}
\item What are the top 20 phrases (sorted by  \emph{total score}) from the \emph{full data set only} (again, with the 1960s as the foreground corpus this time).
 \item What do your phrase finding results tell you about the 1960s?  Are there any interesting phrases?
 \item Tell us about your experience using Hadoop for this portion of the assignment.  Was it easy to port your code over from the Assignment 3?  Is there anything that would have made the process easier?
 \end{enumerate}
 For the Phrases pipeline, include the controller and syslog files created when you process the full dataset.   Create a folder called \texttt{phrases}.  In it, put the controller and syslog files from each of your mapreduces, named syslogN and controllerN for $N={1..n}$ where $n$ is the number of mapreduce jobs in your pipeline. Create a README file briefly describing each of the steps of your pipeline, numbered in the same order as the controller/syslog files.




%\paragraph{Naive Bayes}
% For the Naive Bayes pipeline, include the logs created when you process the full abstracts dataset.  Create a folder called \texttt{naivebayes}.  In it, put the controller and syslog files from each of your Mapreduces, named syslogN and controllerN for $N={1..n}$ where $n$ is the number of Mapreduce jobs in your pipeline. Create a README file briefly describing each of the steps of your pipeline, numbered in the same order as the controller/syslog files.
%
%\paragraph{Phrases}
%For the Phrases pipeline, include the logs created when you process the full dataset.   Create a folder called \texttt{phrases}.  In it, put the controller and syslog files from each of your mapreduces, named syslogN and controllerN for $N={1..n}$ where $n$ is the number of mapreduce jobs in your pipeline. Create a README file briefly describing each of the steps of your pipeline, numbered in the same order as the controller/syslog files.


\section{Marking breakdown}
\subsection{Naive Bayes}
\begin{itemize}
\item Code correctness {\bf [75 points]}.
\item Part A: Question 1 {\bf [10 points]}
\item  Part A: Question 2 {\bf [5 points]}
\item Controller/Syslog files  {\bf [10 points]}
\end{itemize}


\subsection{Phrase Finding}
\begin{itemize}
\item Code correctness {\bf [70 points]}.
\item Part B: Question  1 {\bf [10 points]}
\item  Part B: Question 2  {\bf [5 points]}
\item  Part B: Question 3 {\bf [5 points]}
\item Controller/Syslog files  {\bf [10 points]}
\end{itemize}

\section{Hints/Good to know}
You may consider using the GenericOptionsParser for passing command line arguments - it parses all arguments that have the form \texttt{-D name=value} and turns them into name/value pairs in your Configuration object.
\end{document}  