\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 2: Small Memory Footprint Streaming Naive Bayes}
\author{Due Tuesday, February 7 via Blackboard}
%\date{}                                           % Activate to display a given date or no date

\begin{document}
\maketitle
%\section{}
%\subsection{}
\section{Important Note}
This assignment is the second of three that use the Naive Bayes algorithm.  You will be expected to reuse the code you develop for this assignment for a future assignment, and {\bf you are expected to use Java for this assignment}.  

Ni Lao (nlao@cs.cmu.edu) is the contact TA for this homework.  Please post clarification questions to the Google Group:  \\
\url{machine-learning-with-large-datasets-10-605-in-spring-2012}

\section{Naive Bayes with limited memory}
The algorithm for this assignment is exactly the same as for assignment 1, but now we will constrain the size of the memory footprint.  In your makefile for this assignment, all Java commands must be followed with -Xmx128m which limits the size of the Java heap space.

\section{The Data}

For this assignment, we will be classifying Wikipedia articles by the languages in which they are also available.  The data appears at \url{/afs/cs.cmu.edu/project/bigML/dbpedia/}


The data format is the same as for Assignment 1.  There is one instance per line.  The first token of each line is the (comma separated) list of class names , then a tab, then the data.  Please do multi-label learning and evaluation as described for Assignment 1.

  There are 6 data sets for this assignment.  Again, they are in increasing size so that you can debug your code on smaller data.  The files that start with \emph{abstract} include Wikipidia text.  The files that start with \emph{links} are the outlinks from each wikipedia page.

\begin{verbatim}
 abstract.small.test
 abstract.small.train
 abstract.test
 abstract.train
 abstract.tiny.test
 abstract.tiny.train
 links.small.test
 links.small.train
 links.test
 links.train
 links.tiny.test
 links.tiny.train
\end{verbatim}

\section{Deliverables}

Submit a compressed archive (zip, tar, etc) of your code.  With it, include a makefile so that 
\begin{itemize}
\item The command \emph{make demo}  will build and test a classifier using the training and test files for the ``abstract.tiny'' dataset.
\item The command  \emph{make test TESTFILE=``test.txt''} builds a classifier using the ``abstract.tiny''  training file, and then classifies the documents in the file provided (test.txt in this example).
\end{itemize}
Your classification code should print out the classification results, with format the same as Assignment 1.

In addition to your code and a makefile, please include a pdf document with:

\begin{enumerate}
\item The output of your ``make demo'' command, as well as the percent correct on the other five test sets (using classifiers trained with the corresponding train set).
\item Answers to the following questions:
 \begin{enumerate}
 \item Compare and discuss the performance for the full links vs full abstract data.
\item For the last assignment we were classifying into the top level of the Reuter's hierarchy, and we asked you how you would extend the Naive Bayes Algorithm to handle news articles with multiple labels.  The Reuter's hierarchy is actually several levels deep, and the links denote an \emph{is-a} relationship.  For example, Figure~\ref{f.rcv1m} shows the \emph{Markets} subtree.  The tree shows that an article about Metals Trading is an article about the Commodity Market, which is an article about Markets.  The full list of class codes can be found at \url{http://jmlr.csail.mit.edu/papers/volume5/lewis04a/a02-orig-topics-hierarchy/rcv1.topics.hier.orig}.    

 \begin{enumerate}
\item Consider the meaning of multiple labels in a hierarchy.  An article cannot be about Metals trading if it is not also about the Commodity Market.  How can you extend your algorithm to ensure such inconsistencies in classification don't occur?
\item As the RCV1 class labels become more specific, there are fewer training instances, and the word counts can become more sparse.  So, while you may not have seen word {\bf A} in a \emph{Forex Markets} article, you may have seen it in a \emph{Money Markets} article.  How can you leverage the information from the articles from parent classes to improve your smoothing algorithm for children classes?  (Hint: It may be wise to reflect upon the lecture of January 24, and specifically the strategy for affect/effect classification when we encountered a new unseen word context at test time.)
\end{enumerate} 
\end{enumerate}
\end{enumerate}

BONUS question:
\begin{enumerate}
%\item compare the difference in accessing a local copy of a file vs an AFS copy of the same file.  
%\begin{verbatim}
%time cat /afs/cs.cmu.edu/project/bigML/dbpedia/abstract.train > /dev/null
%time cat ./abstract.train > /dev/null
%\end{verbatim}
%To more accurately measure the difference, use the command "fs flush $<$file name$>$" before accessing the file on AFS, and average the ``real'' time returned over 10 calls.
\item Using a local copy of the RCV1.small\_train.txt file from Assignment 1, compare the performance of creating your Naive Bayes feature dictionary for last assignment and this assignment.  Time all parts of the dictionary creation (including, for example, sorting and combining counts for your Assignment 2 solution).  Average over 10 calls.  Please include in your write up the commands you used to do this comparison.
\end{enumerate}

\section{Marking breakdown}
\begin{itemize}
\item Code correctness and makefile functionality {\bf [60 points]}.
\item 1 {\bf [10 points]} 
\item 2a  {\bf [10 points]} 
\item 2b i  {\bf [10 points]} 
\item 2b ii  {\bf [10 points]} 
\item Bonus question: {\bf [10 points]}
\end{itemize}


\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.5]{rcv1_hieararchy}
\caption{The \emph{Markets} subtree of the RCV1 hierarchy.}
\label{f.rcv1m}
\end{center}
\end{figure}

\section{Hints/Good to know}
Unix sort can handle very large files.  This is helpful when you need to collect together the counts for a particular key.  To ensure sort behaves properly, you should set the following environment variable:
\begin{verbatim}
LC_ALL='C'
\end{verbatim}
Get it to sort using tabs by setting this flag:
\begin{verbatim}
-t $'\t'
\end{verbatim}
And, when files are large it may be a good idea to tell sort where to store its temporary files:
\begin{verbatim}
-T /some/dir
\end{verbatim}
\end{document}  