\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 3: Streaming Phrase Finding}
\author{Due Tuesday, February 14, 2012 via Blackboard}
\date{Out February 7, 2012}
\begin{document}
\maketitle

\section{Important Note}
This assignment is the first of two that use the phrase finding algorithm we discussed in class (see Tomokiyo and Hurst, 2003, http://dl.acm.org/citation.cfm?id=1119287).  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}.  

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{Streaming Phrase Finding}

This assignment is based on the method in \emph{�A language model approach to keyphrase extraction�}, Tomokiyo and Hurst, 2003, http://dl.acm.org/citation.cfm?id=1119287 .  The basic goal is to pick out word sequences in a corpus that are meaningful as phrases (in the paper's words, have high �phraseness�), and over-represented in the corpus (have high �informativeness�).  Phraseness and informativeness are computed based on some simple frequency features, which we will denote as

\begin{table}[htdp]
\begin{center}
\begin{tabular}{|l|l|}
\hline
C(x,y) &frequency of the phrase �x y� in the corpus of interest\\
B(x,y)& analogous for the background corpus\\
C(x), C(y)& frequency of a word x or y in the corpus of interest\\
B(x), B(y)& analogous for the background corpus \\
\hline
\end{tabular}
\end{center}
\end{table}%

You also need a handful of constants, like the number of words and bigrams in each corpus, and the vocabulary sizes.  For this assignment, the \emph{corpus of interest} (foreground corpus) is those books published in the years 1990-1999.  The background corpus is those books published in the years 1960-1989.  We've done some of the preprocessing for you (for example, we've thrown out words and phrases with non-letter characters, normalized the words to their lowercase variants, and aggregated the counts by decade).  As before, there is a smaller test set for debugging your code.


We suggest using a simple data structure that associates a set of attribute-value pairs with a phrase.  Once you have this data structure - for instance like the examples below - it�s easy to compute phraseness and informativeness in a streaming setting:
\begin{table}[htdp]
\begin{center}
\begin{tabular}{|l|l|}
\hline
Key	& Value \\
\hline
united states&	Cxy=104324,Bxy=214442,Cx=321313,Cy=424134,Bx=23141,By=444141\\
white house&	Cxy=4343003,Bxy=43322,Cx=2344233,Cy=786677,Bx=235661,By=1056773\\
\hline
\end{tabular}
\end{center}

\end{table}%

Consider the first row in the example above. Cxy denotes the C(x,y) count for the phrase \texttt{united states} in the foreground corpus.  Cx is the count for \texttt{united} and Cy is the count for \texttt{states} in the foreground corpus.  It�s easy enough to tally up these counts over the corpus. The tricky part is getting these counts in one place.

As in assignment 2, we're going to assume the unigrams won't fit in memory; all Java commands must be followed with -Xmx128m.  We must implement a stream and sort algorithm to request count, fulfill the requests, and aggregate the responses.  Here's a general outline of the algorithm for aggregating the counts (refer also to the lecture slides from January 31):
 \begin{enumerate}
\item Compute counter files mapping $x \rightarrow Bx, x \rightarrow Cx, xy \rightarrow Cxy, xy \rightarrow Bxy$
 \begin{itemize}
\item This is mostly done, but you will need to aggregate together the counts for the different decades in the background corpus.
\end{itemize}
\item Gather together the background and foreground counts for each unigram to create one data structure with key \texttt{x} and value \texttt{Bx=some number,Cx=some number}.  Do the same for the bigrams.
\item Stream through all the phrases and for each phrase �x y�, create two �messages�--one �asking� for the unigram frequencies for x, and one �asking� for the frequencies of y.  Each �message� is just a pair consisting of the query word and the phrase making the request: so the phrase �united states� will generate the messages
\begin{verbatim}
�united�,�united states�
�states�,�united states�
\end{verbatim}
\item To �deliver� the messages, sort them in with the unigram frequency file.  Use a secondary key so the attribute-value pairs come first, and the messages come last (as described in lecture).  While scanning through the unigram file, you will do something like this:
\begin{enumerate}
\item for each distinct key $x$ (e.g. \texttt{united})
\begin{enumerate}
\item read the attribute-value pairs for $x$ (e.g. \texttt{Bx=14342,Cx=24123})
\item for each message from step two addressed to $x$  from a phrase of the form $xz$ (e.g. \texttt{united states}):
\begin{enumerate}
\item send a message to $xz$ with the attribute-value list at the content.  (i.e. write out a pair with key $xz$ and value of the attribute-value list (eg, \texttt{united states, Bx=14342,Cx=24123})
\end{enumerate}
\item for each message  from step two addressed to $x$ from a phrase of the form $zx$ (e.g. \texttt{fly united}):
\begin{enumerate}
\item send a message to $zx$ with the attribute-value list at the content.  (i.e. write out a pair with key $zx$ and value of the attribute-value list (eg, \texttt{united states, By=14342,Cy=24123}) 

(***Notice the change from $x$ to $y$ in the value list***)
\end{enumerate}
\end{enumerate}
\end{enumerate}
\item Now you've created two new data structures for each bigram, one with \texttt{Bx=some number,Cx=some number} and one with \texttt{By=some number,Cy=some number} . To �deliver� these messages, sort them in with the bigram frequency file that contains \texttt{Bxy=some number,Cxy=some number} , and merge the data structures.
\end{enumerate}

Now you have all of the counts in the same data structure, and can compute the phraseness and informativeness scores as described in the paper.  Recall the definition of point wise KL Divergence:

\begin{equation}
\delta_w(p || q) = p(w) log\left(\frac{p(w)}{q(w)} \right)
\end{equation}
Phraseness is point wise KL Divergence 
\begin{equation}
p=p_{fg}(x \land y) \quad q = p_{fg}(x)p_{fg}(y).
\end{equation}
Informativeness is point wise KL Divergence with 
\begin{equation}p=p_{fg}(x \land y) \quad q = p_{bg}(x \land y)
\end{equation}
Where $p_{fg}$ is the probability of an event under the foreground corpus (corpus of interest), and $p_{bg}$ is the probability of an event under the background corpus.  The phrase score is just the sum of phraseness and informativeness.
Please use the natural logarithm for this assignment.  The paper uses a more complex smoothing algorithm, but you should just use add one smoothing, as in Assignments 1 \& 2.

\section{The Data}

We are using the google books corpus.  We've done some preprocessing of the data, and created two sets of data files.  This is unsupervised learning, so there is no test set.

The data has the following format:
\begin{verbatim}
<text>\t<decade>\t<count>
\end{verbatim}
where \texttt{text} is either a bigram or a unigram, and count is the number of times that text occurred in a book in the given decade.  The smaller dataset is all bigrams that contain the word \emph{apple}, and all unigrams appearing in those bigrams.  This subsample was chosen because Apple Computer became a more popular company in the 90s, and thus the word Apple took on a different meaning.  You should be able to see that trend in the phrase statistics you calculate for the smaller dataset.

The data appears at \url{/afs/cs.cmu.edu/project/bigML/phrases/}.  Files with the word \emph{apple} in the name are the subsampled datasets.
  
\section{Deliverables}

Submit a compressed archive (zip, tar, etc) of your code.  Your code should print out the phrases and the scores in this format:
\begin{verbatim}
<phrase>\t<total score>\t<phraseness score>\t<informativeness score>
\end{verbatim}
where total score is the sum of phraseness score and informativeness score.

With it, include a makefile so that 
\begin{itemize}
\item The command \emph{make demo}  will compile counts from scratch (i.e. perform all of the steps outlined above) using the apple corpus on afs, and write to stdout the top 20 phrases sorted by by total score.
\end{itemize}


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

\begin{enumerate}
\item The top 20 phrases (sorted by total score) from the full data set and the apple data set.
\item Answers to the following questions:
 \begin{enumerate}
 \item What do you notice about the phrases ranked highest in your results for the two data sets?  Do they give you any insights into what was going on in the 90s?
\item Are there any downfalls you see to using the total phrase score?  For example, are there some phrases that are ranked high even though you don't think they should be?  Why are they ranked so high?
\item How could you improve upon the total score proposed by Tomokiyo and Hurst?
\end{enumerate}
\end{enumerate}

BONUS question:
\begin{enumerate}
\item Implement the improvement you outlined for question 2 (c), and show the results.  How is your method better?  Are there any further improvements to be made?
\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  {\bf [10 points]} 
\item 2c  {\bf [10 points]} 
\item Bonus question: {\bf [15 points]}
\end{itemize}

\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}  