\documentclass[12pt]{article}
%\usepackage{times}

\newcommand{\coursenumber}{10-701/15-781}
\newcommand{\coursetitle}{Machine Learning}
\newcommand{\courseterm}{Fall 2003}
\newcommand{\doctitlea}{Homework 3 Documentation}
\newcommand{\doctitleb}{Text Data and Naive Bayes Code}

\addtolength{\textwidth}{1.00in}
\addtolength{\textheight}{1.00in}
\addtolength{\evensidemargin}{-.50in}
\addtolength{\oddsidemargin}{-.50in}
\addtolength{\topmargin}{-.50in}


\begin{document}

\parskip = 8pt
\parindent = 0pt

This directory provides an implementation of the Naive Bayes learning algorithm similar to that described in Table 6.2 of the textbook. It also provides a dataset containing 20,000 newsgroup messages drawn from the 20 newsgroups described in Table 6.3.  This code and data are only supported under the Unix and Linux operating systems. For example, one of the {\tt unixXXX.andrew.cmu.edu} servers will do fine. 

There are four files with extension {\tt tar.gz} under this directory.  Copy each to your home directory and unpack with the following commands:

\begin{verbatim}
cp /afs/cs/project/theo-20/www/mlc/hw3/text/XXX.tar.gz ./
gtar zxvf XXX.tar.gz
\end{verbatim}

Now you should find four subdirectories under your home directory: {\tt <./20\_newsgroups>}, {\tt <./mini\_newsgroups>}, {\tt <./bow-20020213>} and {\tt <./example>}.


\section*{Newsgroup Data}

{\tt <./20\_newsgroups>} contains 20 subdirectories with names described in Table 6.3 of the text book. Each of these subdirectories contains 1000 newsgroup articles drawn from the corresponding newsgroup, forming a dataset of 20,000 documents. Each document is a Unix ASCII file with header information (e.g. newsgroup name, subject, date, etc).

{\tt <./mini\_newsgroups>} is a subset of the Newsgroup data, which contains 100 randomly selected messages from each newsgroup. This is a useful dataset for learning to use the provided code. 


\section*{Naive Bayes Code}

You will use the program Rainbow written by Andrew McCallum. Rainbow provides a suite of learning methods for text classification, including the Naive Bayes method described in section 6.10 of the Machine Learning textbook. This code may be used as both a building block for creating other programs, or as a stand-alone learning/classification system.

Rainbow is based on Bow/Libbow, a library of C code useful for writing statistical text analysis, language modeling and information retrieval programs. The current distribution includes the library, as well as front-ends for document classification (rainbow), document retrieval (arrow) and document clustering (crossbow). 

{\tt <./bow-20020213>} contains the most recent Bow/Libbow source code. You need to compile the package first by issuing the following commands:

\begin{verbatim}
cd ./bow-20020213
./configure
gmake
\end{verbatim}

When the compilation is done, you should see the executable program {\tt rainbow} under the source code directory. Copy it to the directory where training/test is carried out, say your home directory.

\verb=cp rainbow ../=

For your convenience, the distribution has provided a Perl script {\tt rainbow-stats} that helps you look at the classification result. Copy it to the directory where training/test is carried out, say your home directory.

\begin{verbatim}
cp rainbow-stats.pl ../rainbow-stats
cd ../
chmod a+x rainbow-stats
\end{verbatim}

A list of options and their functionalities for Rainbow is available with the following command: 

\verb=./rainbow --help | more =

The example below will step you through the process of training and testing a classifier. However, for a more complete tutorial on using Rainbow, please consult its online documentation at

\verb=http://www.cs.cmu.edu/~mccallum/bow/rainbow/=


\section*{Example}

{\tt <./example>} is a self-contained example of using Rainbow to implement the Naive Bayes text classifier. You will find an executable file {\tt rainbow} under this directory which is precompiled on the Andrew-side Unix machine.  Replace it with the program you compiled from the source code if necessary. 

Rainbow assumes each training or test document is a Unix ASCII file. To provide training data, you must create a directory containing no files, then create one subdirectory per target value and place the files in these subdirectories. An example is the subdirectory {\tt <./example/mini\_newsgroups>}. Here you will find two subdirectories named {\tt alt.atheism} and {\tt misc.forsale}. Each of these subdirectories contains 100 files, drawn from the corresponding newsgroup.

To get started, switch to the {\tt <./example>} directory, and type the following command on a single line to define the alias {\tt naivebayes}:

\begin{verbatim}
alias naivebayes './rainbow -m naivebayes --no-stoplist --skip-header
                        --prune-vocab-by-occur-count=1 -d ./learned-model'
\end{verbatim}

This tells Rainbow to use naivebayes as its learning method, to consider every word found in every document, to skip header information in documents, and to store its learned model in the subdirectory {\tt <./learned-model>} of the example directory.

Train a Naive Bayes classifier to classify newsgroup articles as {\tt alt.atheism} versus {\tt misc.forsale} by typing

\verb=naivebayes --index mini_newsgroups/*=

This should produce output something like:

\begin{verbatim}
Created directory `./learned-model'.
Class `alt.atheism'
  Counting words... files : unique-words ::                  
Class `misc.forsale'
  Counting words... files : unique-words ::                  
Class `alt.atheism'
  Gathering stats... files : unique-words ::    100 :     6330
Class `misc.forsale'
  Gathering stats... files : unique-words ::    100 :     6330
\end{verbatim}

Notice Rainbow should now have created a subdirectory for you named {\tt <./learned-model>} in which you will find a number of files.

After the training has finished, examine the words with highest information gain for discriminating the two target classes by typing

\verb+./rainbow -d ./learned-model --print-word-infogain=10+

This should produce output something like:

\begin{verbatim}
Loading data files...
Placed remaining 200 documents in the train set:
Calculating info gain... words ::        30
 0.32457 writes
 0.23588 that
 0.21752 article
 0.14941 sale
 0.13943 not
 0.11935 say
 0.11286 condition
 0.11021 what
 0.10589 of
 0.10338 it
\end{verbatim}

You may ask Rainbow to classify new documents using the model we just trained.

\verb+./rainbow -d ./learned-model --query="mini_newsgroups/misc.forsale/75987"+

The output produced by Rainbow for this query is a list of the classes, each followed by a number. This number is the probability $P(class|document)$ calculated using the Naive Bayes formula. Note in this example, the probabilities output for the two classes are 1 and 0 respectively.

\begin{verbatim}
misc.forsale 1
alt.atheism 0
\end{verbatim}

You can command Rainbow to classify all the data in the training set by using the command

\verb+./rainbow -d ./learned-model --test-files mini_newsgroups/+

Each line of output lists a file name, its true classification, and the posterior probabilities assigned to each class by the learned Naive Bayes model. You can put the output into a file and look at a summary of the results using the provided Pearl script.

\begin{verbatim}
./rainbow -d ./learned-model --test-files mini_newsgroups/ > f
./rainbow-stats < f
\end{verbatim}

You can tell Rainbow to test the classification performance on a hold-out set, i.e. a portion of the data that will not be used for training the classifier. This should give much more trustworthy results than testing on the training data itself. For example, 

\begin{verbatim}
./rainbow -d ./learned-model --test-set=.4 --test=3 > h
./rainbow-stats < h
\end{verbatim}

will output the results of three trials, each with a randomized test-train split in which 60 percent of the documents are used for training, and 40 percent for testing.

\end{document}