\documentclass{article}
\usepackage{fullpage}
\usepackage{bold-extra}
\usepackage{ulem}

\addtolength{\textheight}{1.7cm}
\addtolength{\topmargin}{-0.8cm}
\usepackage{upquote} % fix quotes ''

\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{tikz}
\usetikzlibrary{automata,arrows}

\title{\vspace{-1cm}AI 539 Natural Language Processing, Fall 2022\\HW 6: Recurrent Neural Language Models}
\author{Prof.~Liang Huang}
\date{\vspace{-1cm}}

\begin{document}

\maketitle

{\bf Instructions:}
\begin{itemize}
\item Submit \underline{\bf individually} by Saturday Dec 10, 11:59pm on {\bf Canvas}. No late submissions will be accepted. 
\item Only {\tt hw6.zip} (which contains {\tt report.pdf} and all your code) should be submitted.
\item Worth {\bf 12\%} of the final grade.
\item This HW aims to give you some basic exposure to recurrent neural language models and deep learning.
\item This HW compares NLM with $n$-gram models from EX2 in many of the same tasks: entropy, random generation, space and vowel recovery.
\end{itemize}

\smallskip

To make it simple, our TA has trained two recurrent neural language models (NLMs) for you, the smaller one (``\verb|base|'') on your EX2 \verb|train.txt|,
the larger one (``\verb|large|'') on a subset of wiki-2 corpus,
and a huge one (``\verb|huge|'') on 10\% of the ``one-billion-word'' corpus.
This Exercise asks you to train and use char-based $n$-gram language models. 
Please download \url{http://classes.engr.oregonstate.edu/eecs/fall2022/ai539-003/hw6/hw6-data.tgz} which contains

\begin{enumerate}
\item Trigram models (cf.~EX2) trained on base and large settings (the first one is almost identical to the one from EX2 solutions)

\verb|trigram.base.wfsa.norm| and \verb|trigram.large.wfsa.norm|.
\item NLMs (base, large, and huge) in directory \verb|saved_models/*|. The use of 'huge' is optional.
\item The NLM code: \verb|nlm.py| which provides a class \verb|NLM|.
\item The evaluation scripts: \verb|eval_space.py| (from EX2) and \verb|eval_vowels.py| (from HW1).

\end{enumerate}

You need to run these experiments on \verb|Pytorch| (but you don't need to know anything about it), which we have installed
on \verb|pelican.eecs.oregonstate.edu| machines (all 4 of them, \verb|pelican01| to \verb|pelican04|). This HW does \underline{\bf not} need GPUs, though each \verb|pelican| machine does have reasonably good GPUs.

\begin{verbatim}
$ ssh <ONID>@pelican.eecs.oregonstate.edu

<pelican04:~> ~huanlian/anaconda3/bin/python3
Python 3.9.12 (main, Apr  5 2022, 06:56:58)
[GCC 7.5.0] :: Anaconda, Inc. on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import torch
\end{verbatim}

\section{Playing with the NLM (0 pts)}

You can use the NLM to evaluate the probability of a given sequence:

\begin{verbatim}
>>> from nlm import NLM
>>> NLM.load('large') # load neural model from file; choose 'base', 'large', or 'huge'
>>> h = NLM() # initialize a state (and observing <s>)
>>> p = 1 # probability
>>> for c in 't h e _ e n d _ '.split():
>>>     print("%.3f" % p, h) # cumulative prob and current state (and distribution of the next char)
>>>     p *= h.next_prob(c)  # include prob (c | ...)
>>>     h += c  # observe another character (changing NLM state internally)
        
1.000 "<s>": [t: 0.19, i: 0.10, a: 0.09, m: 0.07, s: 0.06, h: 0.06, c: 0.05, b: 0.04, p: 0.04, f: 0.04, r: 0.03, o: 0.03, d: 0.03, w: 0.03, e: 0.03, n: 0.03, l: 0.02, k: 0.02, g: 0.02, j: 0.01]
0.189 "<s> t": [h: 0.82, o: 0.09, r: 0.03, e: 0.02, i: 0.01, w: 0.01]
0.156 "<s> t h": [e: 0.88, i: 0.07, a: 0.02, r: 0.01]
0.138 "<s> t h e": [_: 0.88, y: 0.04, r: 0.03, s: 0.01]
0.121 "<s> t h e _": [s: 0.13, c: 0.09, f: 0.08, t: 0.07, p: 0.06, a: 0.05, m: 0.05, r: 0.05, b: 0.05, n: 0.04, w: 0.04, g: 0.04, l: 0.04, e: 0.04, d: 0.03, i: 0.03, h: 0.03, o: 0.03, u: 0.01, v: 0.01]
0.004 "<s> t h e _ e": [n: 0.24, a: 0.13, x: 0.11, v: 0.08, p: 0.07, r: 0.05, l: 0.05, m: 0.04, s: 0.04, u: 0.03, f: 0.03, i: 0.02, c: 0.02, d: 0.02, g: 0.01, t: 0.01]
0.001 "<s> t h e _ e n": [d: 0.41, g: 0.23, t: 0.18, v: 0.03, c: 0.03, o: 0.02, e: 0.01, r: 0.01]
0.000 "<s> t h e _ e n d": [_: 0.84, </s>: 0.05, i: 0.05, e: 0.02, s: 0.02]
\end{verbatim}

You can also use the NLM to greedily generate (i.e., always choose the most likely next character):

\begin{verbatim}
>>> NLM.load("large")
>>> h = NLM()
>>> for i in range(100):
>>>      c, p = max(h.next_prob().items(), key=lambda x: x[1])
>>>      print(c, "%.2f <- p(%s | ... %s)" % (p, c, " ".join(map(str, h.history[-4:]))))
>>>      h += c
\end{verbatim}

You get something like:

\begin{tabular}{p{7cm} | p{7cm}}
\begin{verbatim}
t 0.19 <- p(t | ... <s>)
h 0.82 <- p(h | ... <s> t)
e 0.88 <- p(e | ... <s> t h)
_ 0.88 <- p(_ | ... <s> t h e)
s 0.13 <- p(s | ... t h e _)
e 0.18 <- p(e | ... h e _ s)
c 0.31 <- p(c | ... e _ s e)
o 0.88 <- p(o | ... _ s e c)
n 1.00 <- p(n | ... s e c o)
d 1.00 <- p(d | ... e c o n)
_ 0.97 <- p(_ | ... c o n d)
s 0.13 <- p(s | ... o n d _)
e 0.22 <- p(e | ... n d _ s)
a 0.30 <- p(a | ... d _ s e)
s 0.82 <- p(s | ... _ s e a)
o 0.99 <- p(o | ... s e a s)
n 1.00 <- p(n | ... e a s o)
_ 0.88 <- p(_ | ... a s o n)
o 0.21 <- p(o | ... s o n _)
f 0.92 <- p(f | ... o n _ o)
_ 0.98 <- p(_ | ... n _ o f)
t 0.28 <- p(t | ... _ o f _)
h 0.90 <- p(h | ... o f _ t)
e 0.94 <- p(e | ... f _ t h)
_ 0.96 <- p(_ | ... _ t h e)
s 0.12 <- p(s | ... t h e _)
e 0.18 <- p(e | ... h e _ s)
c 0.26 <- p(c | ... e _ s e)
o 0.86 <- p(o | ... _ s e c)
n 1.00 <- p(n | ... s e c o)
d 1.00 <- p(d | ... e c o n)
_ 0.94 <- p(_ | ... c o n d)
\end{verbatim}
&
\begin{verbatim}
s 0.13 <- p(s | ... o n d _)
e 0.21 <- p(e | ... n d _ s)
a 0.29 <- p(a | ... d _ s e)
s 0.81 <- p(s | ... _ s e a)
o 0.99 <- p(o | ... s e a s)
n 1.00 <- p(n | ... e a s o)
_ 0.87 <- p(_ | ... a s o n)
o 0.18 <- p(o | ... s o n _)
f 0.89 <- p(f | ... o n _ o)
_ 0.98 <- p(_ | ... n _ o f)
t 0.28 <- p(t | ... _ o f _)
h 0.90 <- p(h | ... o f _ t)
e 0.94 <- p(e | ... f _ t h)
_ 0.96 <- p(_ | ... _ t h e)
s 0.12 <- p(s | ... t h e _)
e 0.18 <- p(e | ... h e _ s)
c 0.26 <- p(c | ... e _ s e)
o 0.86 <- p(o | ... _ s e c)
n 1.00 <- p(n | ... s e c o)
d 1.00 <- p(d | ... e c o n)
_ 0.94 <- p(_ | ... c o n d)
s 0.13 <- p(s | ... o n d _)
e 0.21 <- p(e | ... n d _ s)
a 0.29 <- p(a | ... d _ s e)
s 0.81 <- p(s | ... _ s e a)
o 0.99 <- p(o | ... s e a s)
n 1.00 <- p(n | ... e a s o)
_ 0.87 <- p(_ | ... a s o n)
o 0.18 <- p(o | ... s o n _)
f 0.88 <- p(f | ... o n _ o)
_ 0.98 <- p(_ | ... n _ o f)
t 0.28 <- p(t | ... _ o f _)
\end{verbatim}
\end{tabular}

\section{Evaluating Entropy (2 pts)}

\begin{enumerate}
\item Like EX2, please first evaluate the trigram entropies (base and large) on EX2 \verb|test.txt|
%cat <text> | sed -e 's/ /_/g;s/\(.\)/\1 /g' | carmel -slib <your_wfsa>

\begin{verbatim}
cat <text> | sed -e 's/ /_/g;s/\(.\)/\1 /g' | awk '{printf("<s> %s </s>\n", $0)}' \
           | carmel -sribI <your_wfsa>
\end{verbatim} 

Hint: both should be around 2.9. 

Q: Is the large version intuitively better than the small version? If so, why? If not, why?

\item Now write a short program to evaluate the entropy of NLMs on the same \verb|test.txt|.

Hint: they should be around 2.6 and 2.0, respectively. 

Q: Which version (base or large) is better? Why?

\item Is NLM better than trigram in terms of entropy? Does it make sense?
\end{enumerate}


\section{Random Generation (2 pts)}

\begin{enumerate}
\item Random generation from $n$-gram models.

Use \verb|carmel -GI 10 <your_wfsa>| to stochastically generate
character sequences. Show the results.
Do these results make sense?

\item Write a short code to randomly generate 10 sentences (from \verb|<s>| to \verb|</s>|) from NLMs.

Hint: use \verb|random.choices()| to draw the random sample from a distribution.

\item Compare the results between NLMs and trigrams.

\end{enumerate}

\section{Restoring Spaces (4 pts)}


\begin{enumerate}
\item 

Recall from EX2 that you can use LMs to recover spaces:

\verb|therestcanbeatotalmessandyoucanstillreaditwithoutaproblem|

\verb|thisisbecausethehumanminddoesnotreadeveryletterbyitselfbutthewordasawhole.|

First, redo the trigram experiments using our provided trigrams, and using Carmel.

What are the precisions, recalls, and F-scores?   (use \verb|eval_space.py|).

Hint: F-scores (for base and large) should be around 61\% and 64\%, respectively.

\item
Then design an algorithm to recover spaces using NLMs. 
Note: you can't use dynamic programming any more due to the infinite history that NLM remembers. You can use beam search instead.

Describe your algorithm in English and pseudocode, and analyze the complexity.

\item
Implement it, and report the precisions, recalls, and F-scores.

Hint: F-scores should be $\sim$81\% and $\sim$94\% using beam size of 20 (and 100\% using the 'huge' model).

\end{enumerate}

\section{Restoring vowels (4 pts)}

\begin{enumerate}
\item Redo trigram vowel recovery and report the accuracy.  (use \verb|eval_vowels.py|)

Hint: should be around 42\% and 41\% (for base and large).

\item Now design an algorithm to recover spaces using NLMs.

Describe your algorithm in English and pseudocode, and analyze the complexity.

\item
Implement it, and report the precisions, recalls, and F-scores.

Hint: should be around 54\% and 80\% using beam size of 40.
If you use the 'huge' NLM, it will be around 93\% (it might be slow to run).


\end{enumerate}

%\section{{Cancelled: Extra Credit: Decipherment with Neural LM (5 pts)}}
%
%\sout{Redo HW4 part 5 with NLMs.}

\end{document}
