\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 1: Streaming Naive Bayes}
\author{Due Tuesday, January 31 via Blackboard}
%\date{}                                           % Activate to display a given date or no date

\begin{document}
\maketitle
%\section{}
%\subsection{}
\section{Important Note}
This assignment is the first of three that use the Naive Bayes algorithm.  You will be expected to reuse the code you develop for this assignment for future assignments.  Thus, the more you adhere to good programming practices now (e.g. abstraction, encapsulation, documentation), the easier the subsequent assignments will be.

Alona Fyshe (afyshe@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}
Much of machine learning with big data involves - sometimes exclusively - counting events.  Multinomial Naive Bayes fits nicely into this framework.   The classifier needs just a few counters.  

For this assignment we will be performing document classification using streaming Multinomial Naive Bayes.  We call it streaming because the input and output of each program are read from stdin and written to stdout.  This allows us to use Unix pipe ``$|$'' to chain our programs together.  For example:
\begin{verbatim}
cat train.txt | java NBTrain | sort -k1,1 | java NBTest -t test.txt 
\end{verbatim}

The streaming formulation allows us to process large amounts of data without having to hold it all in memory.

Let $y$ be the labels for the training documents and $wi$ be the $i$th word in a document.  Here are the counters we need to maintain:

\begin{description}
    \item [(Y=y)]  for each label $y$ the number of training instances of that class
    \item [(Y=*)] here * means �anything�, so this is just the total number of training instances
    \item [(Y=y,W=w)] number of times token w appears in a document with label $y$.
    \item [(Y=y,W=*)] total number of tokens for documents with label $y$.
\end{description}

The learning algorithm just increments counters:
\begin{verbatim}

    for each example {y [w1,...,wN]}:
        increment #(Y=y) by 1
        increment #(Y=*) by 1
        for i=i to N:
            increment #(Y=y,W=wi) by 1
        increment #(Y=y,W=*) by N
        
\end{verbatim}

You may elect to use a tab-separated  format for the event counters as well: eg, a pair $<$event,count$>$ is stored on a line with two tab-separated fields.  Classification will  take a new documents with words w1,...,wN  and score each possible label y with the log probability of y (as covered in class).

For now (hint, hint), you may keep a hashtable in memory, with keys like �Y=news�, �Y=sports,W=aardvark�, etc.  You may NOT load all the training documents in memory.   That is, you must make one pass through the data to collect the count statistics you need to do classification.  Then, write these counts (feature dictionary) to disk via stdout.

\emph{Important Notes}: 
\begin{itemize}
\item At classification time, use Laplace smoothing with $\alpha=1$ as described here: \url{http://en.wikipedia.org/wiki/Additive_smoothing}.   
\item You may assume that all of the test documents will fit into memory.  
\item With the exception of the test set, all files should be read from stdin and written to stdout
\item Use this function to change documents into features:
\begin{verbatimtab}[8]
static Vector<String> tokenizeDoc(String cur_doc) {
	String[] words = cur_doc.split("\\s+");
	Vector<String> tokens = new Vector<String>();
	for (int i = 0; i < words.length; i++) {
		words[i] = words[i].replaceAll("\\W", "");
		if (words[i].length() > 0) {
			tokens.add(words[i]);
		}
	}
	return tokens;
}
\end{verbatimtab}
\end{itemize}  

\section{The Data}
For this assignment, we are using the Reuters Corpus, which is a set of news stories split into a hierarchy of categories.  
There are multiple class labels per document.  This means that there is more than one correct answer to the question ``What kind of news article is this?''  
For this assignment, we will ignore all class labels except for those ending in CAT.  This way, we'll just be classifying into the top-level nodes of the hierarchy:
\begin{itemize}
\item CCAT: Corporate/Industrial
\item ECAT: Economics
\item GCAT: Government/Social
\item MCAT: Markets
\end{itemize}
There are some documents with more than one CAT label.  Treat those documents as if you observed the same document once for each CAT label (that is, add to the counters for all labels ending in CAT).
If you're interested, a description of the class hierarchy can be found at \url{http://jmlr.csail.mit.edu/papers/volume5/lewis04a/a02-orig-topics-hierarchy/rcv1.topics.hier.orig}.

The data for this assignment is at:
\url{/afs/cs.cmu.edu/project/bigML/RCV1}\\
Note that you may need to issue the command \emph{kinit} before you can access the afs files.  The format is one document per line, with the class labels first (comma separated), a tab character, and then the document.  There are three file sets:
\begin{verbatim}

RCV1.full.*
RCV1.small.*
RCV1.very_small.*

\end{verbatim}
The two file sets with ``small'' in the name contain smaller subsamples of the full data set.  They are provided to assist you in debugging your code.  Each data set appears in full in one file, and is split into a train and test set, as indicated by the file suffix.



\section{Deliverables}
%Write a streaming Naive Bayes ``train� program that keeps event counts in memory, then stores them on disk at termination.  A second program �classify� loads the event counters from disk and will classify a stream of documents.  

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 ``very\_small'' dataset.
\item The command  \emph{make test TESTFILE=``test.txt''} builds a classifier using the ``very\_small''  training file, and then classifies the documents in file provided (test.txt in this example).
\end{itemize}
Your classification code should print out the classification results, including the log probabilities of the best class $y$:
\begin{equation}
\label{eq.log_prob}
ln(p(Y=y))+\sum_{w_i} ln(p(W=w_i|Y=y))
\end{equation}
***Notice that we're using the natural logarithm here.*** The output format should have one test result per line, and each line should have the format:
\begin{quote}
{\bf [Label1, Label2, ...]$<$tab$>$Best Class$<$tab$>$Log prob }
\end{quote}

where {\bf  [Label1, Label2, ...]} are the true labels of the test instance, {\bf Best Class} is the class with the maximum log probability (as in Equation~\ref{eq.log_prob}), and the last field is the log probability.  The last line of the file should give the percent correct.  Here's an example of the output format: 

\begin{verbatimtab}[8]

[CCAT, C181, C18, GCAT]	CCAT	-1042.8524
[GCAT]	CCAT	-4784.8523
...
Percent correct: 9/10=90.0%
\end{verbatimtab}

You may count a document correct if the most probable class matches any of the labels (as in the first line of the example above).  This way you get credit for multiply labeled documents if you get any of the labels correct.

  In addition to your code an 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 two test sets (using classifiers trained with the corresponding train set).
\item Answers to the following two questions:
 \begin{enumerate}
\item What changes could you make to reduce the amount of RAM required for the feature dictionary?
\item Right now we're basically ignoring the fact that there are multi-labeled instances in the train/test sets.  How would you extend your algorithm to enable it to predict multiple labels?
\end{enumerate}
\end{enumerate}

\section{Marking breakdown}
\begin{itemize}
\item Code correctness and makefile functionality {\bf [70 points]}.
\item 1a {\bf [10 points]} 
\item 2a  {\bf [10 points]} 
\item 2b  {\bf [10 points]} 
\end{itemize}
\end{document}  