\documentclass[11pt]{article}
\usepackage[margin=1.5cm,tmargin=1.2cm]{geometry}
\usepackage{xspace}
\usepackage{amsmath}
\usepackage{upquote}
\usepackage{fancyvrb}

\usepackage{tikz}
%\usepackage{layout}

%\addtolength{\topmargin}{-

\newcommand{\longspace}{\underline{\hspace{4.5cm}}}
\newcommand{\shortspace}{\underline{\hspace{2.5cm}}}
\newcommand{\vecx}{\ensuremath{\mathbf{x}}\xspace}
\newcommand{\matA}{\ensuremath{\mathbf{A}}\xspace}
\newcommand{\vecw}{\ensuremath{\mathbf{w}}\xspace}

\title{Applied Machine Learning HW4}
\author{Due Monday May 30  @ 11:59pm on Canvas}
%\title{Machine Learning HW2 (10\%, in groups of 2 or 3)}
%\author{Instructor: Liang Huang\\[0.2cm]
%Due Sun Oct 29 @ 11:59pm}
%\author{\small Last: \longspace \; First: \longspace \; ONID: \shortspace {\tt @oregonstate.edu} }
\date{}
\setcounter{section}{-1}
\begin{document}


\maketitle
%\thispagestyle{empty}

Instructions:
\begin{enumerate}
\item This homework is about sentiment classification, using (averaged) perceptron (and optionally,
  other ML algorithms such as SVM). I provided a very simple naive perceptron baseline. The point of this homework is more about learning from my code and extending it, rather than implementing yours from scratch.
%\item Before you submit, please join your group on Canvas under {\tt People / HW1 Groups}.
      %Each group just needs to submit one copy.
%      If any group member submits, it's automatically considered submission for his/her group.
%If you'd like to install them on your own computers, we suggest installing {\tt anaconda} 
%which comes with both packages.
%\item Do \underline{not} use any other non-built-in packages.
%Your code should only depend on standard built-in packages plus {\tt numpy}.

%\item Download your HW1 data from the course homepage.
%It contains the training data, the dev set (held-out), 
%and a semi-blind test set. The test set does not contain target labels, and you will need to predict them using your best model.
%Part of your grade is based on the relative ranking of your test performance.
\item Download HW4 data from the course homepage, which includes training, dev, and semi-blind test files.
%However, since SVM training (by default) is {\em much} slower than perceptron/MIRA, let's just use \underline{the first 5,000 training examples} (dev/test remain unchanged):
%\begin{verbatim}
%head -5000 income.train.txt > income.train.txt.5k
%\end{verbatim}
\item You should submit a single {\tt .zip} file containing {\tt hw4.pdf}, {\tt test.txt.predicted}, and all your code.
  Again, \LaTeX'ing is recommended but not required.
  Make sure your \verb|test.txt.predicted| has the same format as \verb|train.txt| and \verb|dev.txt|.
\end{enumerate}

\section{Sentiment Classification Task and Dataset}

Sentiment classification is one of the most widely used applications of machine learning. Basically, given a sentence (e.g., a movie review or a restaurant review), we want to label it as either ``positive'' or ``negative''. I have collected a movie review data set which contains 8,000 training, 1,000 dev, and 1,000 test sentences. To make it simple, I made sure that each set is exactly 50\% positive and 50\% negative.

Some examples from the training set (the labels were manually annotated by paid annotators):

\begin{verbatim}
+    i admired this work a lot
+    if steven soderbergh 's ` solaris ' is a failure it is a glorious failure
+    it 's refreshing to see a romance this smart
+    i could n't recommend this film more
+    manages to be original , even though it rips off many of its ideas

-    extremely bad
-    the kind of movie you see because the theater has air conditioning
-    the only thing i laughed at were the people who paid to see it
-    the entire movie is about a boring , sad man being boring and sad
-    though catch me if you can is n't badly made , the fun slowly leaks out of the movie
\end{verbatim}

To simplify your job I have done the following preprocessing steps:
\begin{enumerate}
\item All words are lowercased;
\item Punctuations are split from adjoining words and become separate ``words''  (e.g., the commas above);
\item Verb contractions and the genitive of nouns are split into their component morphemes, and each morpheme is tagged separately,
e.g.:
\begin{verbatim}
children's -> children 's   parents' -> parents '   won't -> wo n't    that's -> that 's
gonna -> gon na   i'm -> i 'm  you'll -> you 'll   we'd -> we 'd  you're -> you 're
\end{verbatim}
\item Single quotes are changed to forward- and backward- quotes 
(e.g., \verb|'solaris' --> ` solaris '|) and double quotes are changed 
to double single forward- and backward- quotes, e.g.:

\verb|"catch me if you can" --> `` catch me if you can ''|
\item There were a small amount of reviews in Spanish; I've removed them.
\end{enumerate}

{\bf Question: why is each of these steps necessary or helpful for machine learning?}

\section{Naive Perceptron Baseline}

I have written a very simple naive perceptron baseline for this task (included in the data):

\begin{verbatim}
$ python3 train.py train.txt dev.txt

epoch 1, update 38.8%, dev 36.6%
epoch 2, update 25.1%, dev 34.6%
epoch 3, update 20.7%, dev 33.8%
epoch 4, update 16.7%, dev 31.7%
epoch 5, update 13.8%, dev 34.0%
epoch 6, update 12.1%, dev 31.9%
epoch 7, update 10.3%, dev 30.1%
epoch 8, update 9.2%, dev 30.6%
epoch 9, update 8.4%, dev 31.8%
epoch 10, update 7.0%, dev 31.4%
best dev err 30.1%, |w|=16743, time: 2.3 secs
\end{verbatim}

Here the update \% is the update ratio on the training set, which approximates training error rate but not exactly the same (see HW1/HW3), and {\tt |w|} is the dimensionality of the weight vector.

This implementation is extremely simple (about 40 lines of code). Basically, each (unique) word is a feature, and to make it very simple, we treat each sentence as a ``bag of words'', i.e.,
a ``set'' of words where the word order does not matter. This is also known as ``one-hot'' representation because for each word, only the corresponding dimension is on (or 1) and all other dimensions are off (or 0), and a sentence's representation is simply the sum of its word vectors, e.g. the sentence \verb|the man bit the dog| is represented as 
\begin{verbatim}
....  bit ... dog ... man ... the ...
....   1  ...  1  ...  1  ...  2  ...
\end{verbatim}

 To represent this space I use my very simple sparse vector library \verb|svector.py| (also included), which provides an \verb|svector| class based on Python's built-in default dictionary (\verb|collections.defaultdict|). Unlike numpy vectors which has a fixed dimensions, my \verb|svector| does not assume any dimensionality, and each unique key is a dimension. This made it perfectly suitable for natural language tasks where the vocabulary size is huge, e.g., in the training file there are 16,743 unique words (including punctuatons). I made \verb|svector| very similar to numpy vector, so that you can add, subtract, and dot-product with sparse vectors:

\begin{verbatim}
>>> from svector import svector
>>> a = svector()
>>> a
defaultdict(<type 'float'>, {})
>>> a['the'] = 1
>>> a
defaultdict(<type 'float'>, {'the': 1})
>>> a += a
>>> a
defaultdict(<type 'float'>, {'the': 2})
>>> a.dot(a)
4
>>> a * 2
defaultdict(<type 'float'>, {'the': 4})
>>> 2 * a
defaultdict(<type 'float'>, {'the': 4})
>>> - a
defaultdict(<type 'float'>, {'the': -2})
>>> a['boy'] = 1
>>> a
defaultdict(<type 'float'>, {'boy': 1, 'the': 2})
>>> a.dot({'the': -1, 'girl': 2})
-2.0
\end{verbatim}

Now the sentence \verb|the man bit the dog| is represented as \verb|{'dog': 1, 'bit': 1, 'the': 2, 'man': 1}|.


Questions:

\begin{enumerate}
\item Take a look at \verb|svector.py|, and briefly explain why it can support addition, subtraction, scalar product, dot product, and negation.
\item Take a look at \verb|train.py|, and briefly explain \verb|train()| and \verb|test()| functions.
\item There is one thing missing in my \verb|train.py|: the bias dimension! Try add it. How did you do it? (Hint: by adding \verb|bias| or \verb|<bias>|?) Did it improve error on dev?
\item Wait a second, I thought the data set is already balanced (50\% positive, 50\% negative). I remember the bias being important in highly unbalanced data sets. Why do I still need to add the bias dimension here??

\end{enumerate}


\section{Average Perceptron}% and Vocabulary Pruning}
Now implement averaged perceptron based on the version with the bias discussed above. Note that unlike in HW1, this time you have to use the smart implementation of averaging, otherwise it will be way too slow to run, due to 
the much bigger dimensionality (sparse vectors).

\begin{enumerate}
 \item Train for 10 epochs and report the results. Did averaging improve on dev? (Hint: should be around 26\%). Did it make dev error rates more smooth?
\item Did smart averaging slow down training?
\item What are the top 20 most positive and top 20 most negative features? Do they make sense?
\item Show 5 negative examples in dev where your model most strongly believes to be positive. Show 5 positive examples in dev where your model most strongly believes to be negative. What observations do you get?
\item Try improve the speed by caching  sentence vectors from training and dev sets, and show timing results.
\end{enumerate}

\section{Pruning the Vocabulary}

Actually many words only appear once in the training set, and many of them are unlikely to appear in the dev set. Therefore it is common to remove low-frequency words from the training set, as a regularization trick (smaller models alleviate overfitting; those rare words might just make the model memorize idiosyncrasies or noises in the training set).
\begin{enumerate}
\item Try neglecting one-count words in the training set during training. Did it improve on dev? (Hint: should help a little bit, error rate lower than 26\%).
\item Did your model size shrink? (Hint: should almost halve).
\item Did update \% change? Does the change make sense?
\item Did the training speed change?
\item What about further pruning two-count words (words that appear twice in the training set), etc?
\end{enumerate}
%\section{Adding Bigram}

\section{Try some other learning algorithms with sklearn}

Now you can try {\bf at least one} other machine learning algorithms of your choice
(either covered or uncovered in our course) using \verb|sklearn| (so that you don't need to implement them),
such as $k$-NN, SVM, logistic regression, neural networks, decision trees, XGBoost, etc.
To use \verb|sklearn|, like in HW3, you will need to convert an \verb|svector| object to a numpy vector.
Note that this training might take a very long time,
so you should  prune one-count and two-count words first.
After pruning, the training might still take a long time.
If you find it too slow, you can further prune more low-count words,
and/or use a subset (e.g., 5,000) of the training set.

%% You can choose either SVM or logistic regression. In either case, there is a regularization strength parameter $C$ to tune: smaller values indicate stronger regularization (recall that $C \rightarrow +\infty$ means hard-margin SVM, i.e., no regularization).

\smallskip



Q: What did you learn in terms of the comparison between averaged perceptron and these other (presumably more popular and well-known)
learning algorithms?

\section{Deployment}

%% (Optional, extra credit) You can try other tricks that you can think of, e.g., using bigrams (two consecutive words) or using \verb|word2vec|, a dense representation (Google these terms). 

%% \bigskip

You can also try other tricks such as bigrams (two consecutive words) and removing STOP words
(such as ``the'', ``an'', ``in'', ``and''; just Google it).
Collect your best model and predict on {\tt test.txt} to {\tt test.txt.predicted}. 

Q: what's your best error rate on dev, and which algorithm and setting achieved it? 

\bigskip
{%\small
\section{Debriefing  (required):}
\begin{enumerate}
\item Approximately how many hours did you spend on this assignment?
\item Would you rate it as easy, moderate, or difficult?
\item Did you work on it mostly alone, or mostly with other people?
\item How deeply do you feel you understand the material it covers (0\%--100\%)?
\item Any other comments?
\end{enumerate}
}

\end{document}
