\documentclass{beamer}             % for slides
% \documentclass[handout]{beamer}    % for handout
\input{beamer}

\title{Tagging}

\author{Steven Bird \and Ewan Klein \and Edward Loper}
\institute{
  University of Melbourne, AUSTRALIA
  \and
  University of Edinburgh, UK
  \and
  University of Pennsylvania, USA
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\frame{\titlepage}

\section{Introduction}

\subsection{Parts of Speech}

\begin{frame}
  \frametitle{Parts of speech}

  \begin{itemize}
  \item How can we predict the bahaviour of a previously unseen word?
  \item Words can be divided into classes that behave similarly.
  \item Traditionally eight parts of speech: noun, verb,
    pronoun, preposition, adverb, conjunction, adjective and article.
  \item More recently larger sets have been used: eg Penn Treebank (45
    tags), Susanne (353 tags).
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Parts of Speech}

  \begin{alertblock}{What use are parts of speech?}
    They tell us a lot about a word (and the words near it).
  \end{alertblock}

  \pause
  \begin{itemize}
  \item Tell us what words are likely to occur in the neighbourhood
    (eg adjectives often followed by nouns, personal pronouns often
    followed by verbs, possessive pronouns by nouns)
  \item Pronunciations can be dependent on part of speech, eg
    \textcolor{green}{object, content, discount} (useful for speech
    synthesis and speech recognition)
  \item Can help information retrieval and extraction (stemming,
    partial parsing) 
  \item Useful component in many NLP systems
  \end{itemize}
  
\end{frame}

\subsection{Open and closed classes}

\begin{frame}
  \frametitle{Closed and open classes}
  \begin{itemize}
  \item Parts of speech may be categorised as \emph{open} or
    \emph{closed} classes
  \item Closed classes have a fixed membership of words (more or
    less), eg determiners, pronouns, prepositions
  \item Closed class words are usually \emph{function words} ---
    frequently occurring, grammatically important, often short (eg
    \textcolor{green}{of,it,the,in})
  \item The major open classes are \emph{nouns}, \emph{verbs},
    \emph{adjectives} and \emph{adverbs}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Closed classes in English}
  \textcolor{black}{
  \begin{tabular}{ll}
  \textbf{prepositions} & on, under, over, to, with, by\\
  \textbf{determiners} & the, a, an, some\\
  \textbf{pronouns} & she, you, I, who\\
  \textbf{conjunction}s & and, but, or, as, when, if\\
  \textbf{auxiliary verbs} & can, may, are\\
  \textbf{particles} & up, down, at, by\\
  \textbf{numeral}s & one, two, first, second\\
  \end{tabular}}
\end{frame}

\begin{frame}
  \frametitle{Open classes}
  \textcolor{black}{
  \begin{description}
  \item[nouns] Proper nouns (\textcolor{green}{Scotland}, \textcolor{green}{BBC}),\\
    common nouns:
    \begin{itemize}
    \item count nouns (\textcolor{green}{goat},
      \textcolor{green}{glass})
    \item mass nouns (\textcolor{green}{snow},
      \textcolor{green}{pacifism})
    \end{itemize}
  \item[verbs] actions and processes (\textcolor{green}{run},
    \textcolor{green}{hope}), also auxiliary verbs
  \item[adjectives] properties and qualities (age, colour, value)
  \item[adverbs] modify verbs, or verb phrases, or other adverbs:\\
    \textcolor{green}{\emph{Unfortunately} John walked \emph{home
        extremely slowly yesterday}}
  \end{description}}
\end{frame}


\subsection{Tagsets}

\begin{frame}
  \frametitle{The Penn Treebank tagset (1)}
  \textcolor{black}{\footnotesize
    \begin{tabular}{|lll|lll|}
      \hline
      CC & Coord Conjuncn & \emph{and,but,or} &  
      NN & Noun, sing. or mass & \emph{dog} \\
      CD & Cardinal number & \emph{one,two} & 
      NNS & Noun, plural & \emph{dogs} \\
      DT & Determiner & \emph{the,some} &  
      NNP & Proper noun, sing. & \emph{Edinburgh} \\
      EX & Existential there & \emph{there} &  
      NNPS & Proper noun, plural & \emph{Orkneys} \\
      FW & Foreign Word & \emph{mon dieu} &  
      PDT & Predeterminer & \emph{all, both}\\
      IN & Preposition & \emph{of,in,by} & 
      POS & Possessive ending & \emph{'s} \\
      JJ & Adjective & \emph{big} & 
      PP & Personal pronoun & \emph{I,you,she} \\
      JJR & Adj., comparative & \emph{bigger} & 
      PP\$ & Possessive pronoun & \emph{my,one's} \\
      JJS & Adj., superlative & \emph{biggest} &  
      RB & Adverb & \emph{quickly} \\
      LS & List item marker & \emph{1,One} &  
      RBR & Adverb, comparative & \emph{faster} \\
      MD & Modal & \emph{can,should} &
      RBS & Adverb, superlative & \emph{fastest} \\
      \hline
    \end{tabular}
  }
\end{frame}

\begin{frame}
  \frametitle{The Penn Treebank tagset (2)}
  \textcolor{black}{\footnotesize
    \begin{tabular}{|lll|lll|}
      \hline
      RP & Particle & \emph{up,off} &
      WP\$ & Possessive-Wh & \emph{whose} \\ 
      SYM & Symbol & \emph{+,\%,\&}  &
      WRB & Wh-adverb & \emph{how,where} \\
      TO & ``to'' & \emph{to} &
      \$ & Dollar sign & \emph{\$}\\
      UH & Interjection & \emph{oh, oops} &
      \# & Pound sign & \emph{\#} \\
      VB & verb, base form &     \emph{eat} &
      `` & Left quote & ` , `` \\
      VBD & verb, past tense & \emph{ate} &
      '' & Right quote & ', '' \\
      VBG & verb, gerund & \emph{eating} &
      ( & Left paren & ( \\
      VBN & verb, past part & \emph{eaten} &
      ) & Right paren & ) \\
      VBP & Verb, non-3sg, pres & \emph{eat} &
      , & Comma & , \\
      VBZ & Verb, 3sg, pres & \emph{eats} &
      . & Sent-final punct & . ! ? \\
      WDT & Wh-determiner &  \emph{which,that} &
      : & Mid-sent punct. & : ; --- ... \\
      WP & Wh-pronoun & \emph{what,who} & & & \\
      \hline
    \end{tabular}
  }
\end{frame}

\subsection{Tagging}

\begin{frame}
  \frametitle{Tagging}
  \begin{itemize}
  \item Definition: POS Tagging is the assignment of a single
    part-of-speech tag to each word (and punctuation marker) in a
    corpus.  For example:\\
    {\scriptsize
    \textcolor{green}{``/``  The/DT  guys/NNS  that/WDT  make/VBP
      traditional/JJ  hardware/NN  are/VBP  really/RB  being/VBG
      obsoleted/VBN  by/IN  microprocessor-based/JJ  machines/NNS  ,/,
      ''/''  said/VBD  Mr./NNP  Benton/NNP  ./.}}
  \item Non-trivial: POS tagging must resolve ambiguities since the
    same word can have different tags in different contexts
  \item In the Brown corpus 11.5\% of word types and 40\% of word
    tokens are ambiguous
  \item In many cases one tag is much more likely for a given word
    than any other
  \item Limited scope: only supplying a tag for each word, no larger
    structures created (eg prepositional phrase attachment)
  \end{itemize}  
\end{frame}

%There                  EX
%are                    VBP
%11                     CD
%players                        NNS
%in                     IN
%a                      DT
%football               NN
%team                   NN
%.                      .

\begin{frame}
  \frametitle{Information sources for tagging}
  \textcolor{black}{
  What information can help decide the correct PoS tag for a word?
  \begin{description}
  \item[Other PoS tags] Even though the PoS tags of other words may be
    uncertain too, we can use information that some tag sequences are
    more likely than others (eg \emph{the/AT red/JJ drink/NN} vs \emph{the/AT
      red/JJ drink/VBP}).\newline
    Using \emph{only} information about the most likely PoS tag
    sequence does not result in an accurate tagger (about 77\%
    correct)
  \item[The word identity] Many words can gave multiple possible tags,
    but some are more likely than others (eg \emph{fall/VBP} vs
    \emph{fall/NN}) \newline
    Tagging each word with its most common tag results in a tagger
    with about 90\% accuracy
  \end{description}}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Simple Taggers and Evaluation}

\subsection{Simple taggers} 

\begin{frame}[fragile]
  \frametitle{Tagging in NLTK}
\textcolor{black}{The simplest possible tagger tags everything as a noun:}
\small
\begin{verbatim}
text = 'There are 11 players in a football team'
text_tokens = text.split()
# ['There', 'are', '11', 'players', 'in', 'a', 'football', 'team']
\end{verbatim}
  \pause
\begin{verbatim}
import nltk
mytagger = nltk.DefaultTagger('NN')
for t in mytagger.tag(text_tokens):
    print t
# ('There', 'NN')
# ('are', 'NN')
# ...
\end{verbatim}
\end{frame}

\begin{frame}[fragile]
  \frametitle{A regular expression tagger}
\textcolor{black}{
We can use regular expressions to tag tokens based on regularities in
the text, eg numerals:}
\small
\begin{verbatim}
default_pattern = (r'.*', 'NN')
cd_pattern = (r' ^[0-9]+(.[0-9]+)?$', 'CD')
patterns = [cd_pattern, default_pattern]
NN_CD_tagger = nltk.RegexpTagger(patterns)
re_tagged = NN_CD_tagger.tag(text_tokens)
# [('There', 'NN'), ('are', 'NN'), ('11', 'NN'), ('players', 'NN'), 
('in', 'NN'), ('a', 'NN'), ('football', 'NN'), ('team', 'NN')]
\end{verbatim}
\end{frame}


\subsection{Unigram taggers} 

\begin{frame}[fragile]
  \frametitle{A unigram tagger}
The NLTK UnigramTagger class implements a tagging algorithm based on a
table of unigram probabilities:
\[ \mbox{tag}(w) = \arg\max_{t_i} P(t_i|w) \]

\pause
Training a UnigramTagger on the Penn Treebank:
{\small
\begin{verbatim}
# sentences 0-2999
train_sents = nltk.corpus.treebank.tagged_sents()[:3000]
# from sentence 3000 to the end
test_sents = nltk.corpus.treebank.tagged_sents()[3000:]

unigram_tagger = nltk.UnigramTagger(train_sents)
\end{verbatim}}
\end{frame}



\begin{frame}[fragile]
  \frametitle{Unigram tagging}
{\small
\begin{verbatim}
>>> sent = "Mr. Jones saw the book on the shelf"
>>> unigram_tagger.tag(sent.split())
[('Mr.', 'NNP'), ('Jones', 'NNP'), ('saw', 'VBD'), ('the', 'DT'), 
('book', 'NN'), ('on', 'IN'), ('the', 'DT'), ('shelf', None)]
\end{verbatim}}

  The UnigramTagger assigns the default tag \texttt{None} to words
  that are not in the training data (eg \emph{shelf})

  \pause
  We can combine taggers to ensure every word is tagged:
{\small
\begin{verbatim}
>>> unigram_tagger = nltk.UnigramTagger(train_sents, cutoff=0, backoff=NN_CD_tagger)
>>> unigram_tagger.tag(sent.split())
[('Mr.', 'NNP'), ('Jones', 'NNP'), ('saw', 'VBD'), ('the', 'DT'), 
('book', 'VB'), ('on', 'IN'), ('the', 'DT'), ('shelf', 'NN')]
\end{verbatim}}
\end{frame}


\subsection{Evaluating taggers}

\begin{frame}
  \frametitle{Evaluating taggers}
  \begin{itemize}
  \item Basic idea: compare the output of a tagger with a
    human-labelled \emph{gold standard}
  \item Need to compare how well an automatic method does with the
    agreement between people
  \item The best automatic methods have an accuracy of about 96-97\%
    when using the (small) Penn treebank tagset (but this is still an
    average of one error every couple of sentences...)
  \item Inter-annotator agreement is also only about 97\% 
  \item A good unigram baseline (with smoothing) can obtain 90-91\%!
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Evaluating taggers in NLTK}
  NLTK provides a function \texttt{tag.accuracy} to automate
  evaluation.  It needs to be provided with a tagger, together with
  some text to be tagged and the gold standard tags.  
  
  \pause
  We can make print more prettily:
\begin{verbatim}
def print_accuracy(tagger, data):
    print '%3.1f%%' % (100 * nltk.tag.accuracy(tagger, data))
\end{verbatim}

  \pause
\begin{verbatim}
>>> print_accuracy(NN_CD_tagger, test_sents)
15.0%
>>> print_accuracy(unigram_tagger, train_sents)
93.8%
>>> print_accuracy(unigram_tagger, test_sents)
82.8%
\end{verbatim}
\end{frame}

\subsection{Error analysis} 

\begin{frame}
  \frametitle{Error analysis}
  \begin{itemize}
  \item The \% correct score doesn't tell you everything --- it is
    useful know what is misclassified as what
  \item \emph{Confusion matrix}: A matrix (ntags x ntags) where the rows
    correspond to the correct tags and the columns correspond to the
    tagger output.  Cell $(i,j)$ gives the count of the number of
    times tag $i$ was classified as tag $j$
  \item The leading diagonal elements correspond to correct
    classifications
  \item Off diagonal elements correspond to misclassifications 
  \item Thus a confusion matrix gives information on the major
    problems facing a tagger (eg NNP vs. NN vs. JJ)
  \item See section 3 of the NLTK tutorial on Tagging
  \end{itemize}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{More Powerful Taggers}

\subsection{N-gram Taggers}

\begin{frame}
  \frametitle{N-gram taggers}
  \begin{itemize}
  \item Basic idea:  Choose the tag  that maximises:
    \[ P(\mbox{word} | \mbox{tag}) \cdot 
       P(\mbox{tag} | \mbox{previous n tags}) \]
       
  \item For a bigram model the best tag at position $i$ is:
    \[ t_i = \arg\max_{t_j} P(w_i|t_j) P(t_j | t_{i-1}) \]
    Assuming that you know the previous tag, $t_{i-1}$.
  \item Interpretation: choose the tag $t_i$ that is most likely to
    \alert{generate} word $w_i$ given that the previous tag was $t_{i-1}$ 
  \end{itemize}
\end{frame}

\pgfdeclareimage[width=8cm]{tag-context}{../images/tag-context}
\begin{frame}
  \frametitle{N-gram taggers}
  \pgfuseimage{tag-context}
\end{frame}

\begin{frame}
  \frametitle{Example (J+M, p304)}
  {\small
  Secretariat/NNP is/VBZ expected/VBZ to/TO \alert{race/VB} tomorrow/NN

  \medskip
  People/NNS continue/VBP to/TO inquire/VB the/DT reason/NN for/IN the/DT
  \alert{race/NN} for/IN outer/JJ space/NN
  }

  \begin{itemize}
  \item<2-> ``race'' is a verb in the first, a noun in the second.
  \item<3-> Assume that race is the only untagged word, so we can assume
    the tags of the others.
  \item<4-> Probabilities of ``race'' being a verb, or race being a noun
    in the first example:
    \begin{align*}
      P(\mbox{race is }VB) &= P(VB|TO) P(\mbox{race}|VB) \\
      P(\mbox{race is }NN) &= P(NN|TO) P(\mbox{race}|NN) 
    \end{align*}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Example (continued)}
  \begin{align*}
    P(NN|TO) &= 0.021 \\
    P(VB|TO) &= 0.34 \\
    \\
    P(\mbox{race}|NN) &= 0.00041\\
    P(\mbox{race}|VB) &= 0.00003\\
    \\
    P(\mbox{race is }VB) &= P(VB|TO) P(\mbox{race}|VB) \\
    &= 0.34 \times 0.00003 = 0.00001 \\
    P(\mbox{race is }NN) &= P(NN|TO) P(\mbox{race}|NN) \\
    &= 0.021 \times 0.00041 = 0.000007
   \end{align*}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Simple bigram tagging in NLTK}
{\small
\begin{verbatim}
>>> default_pattern = (r'.*', 'NN')
>>> cd_pattern = (r' ^[0-9]+(.[0-9]+)?$', 'CD')
>>> patterns = [cd_pattern, default_pattern]
>>> NN_CD_tagger = nltk.RegexpTagger(patterns)
>>> unigram_tagger = nltk.UnigramTagger(train_sents, cutoff=0, backoff=NN_CD_tagger)
>>> bigram_tagger = tag.BigramTagger(train_sents, backoff=unigram_tagger)
\end{verbatim}%$

\begin{verbatim}
>>> print_accuracy(bigram_tagger, train_sents)
95.6%
>>> print_accuracy(bigram_tagger, test_sents)
84.2%
\end{verbatim}
}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Limitation of NLTK n-gram taggers}

  \begin{itemize}
  \item Does not find the most likely sequence of tags, simply works
    left to right always assigning the most probable single tag (given
    the previous tag assignments)
  \item Does not cope with zero probability problem well (no smoothing
    or discounting)
  \item see module \verb|nltk.tag.hmm|
  \end{itemize}
\end{frame}

\subsection{The Brill Tagger}

\begin{frame}
  \frametitle{Brill Tagger}
  \begin{itemize}
  \item Problem with n-gram taggers: size
  \item A rule-based system...
  \item ...but the rules are learned from a corpus
  \item Basic approach: start by applying general rules, then
    successively refine with additional rules that correct the
    mistakes (painting analogy)
  \item Learn the rules from a corpus, using a set of rule templates,
    eg:\\
    Change tag \textbf{a} to \textbf{b} when the following word is
    tagged \textbf{z}
  \item Choose the best rule each iteration    
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Brill Tagger: Example}

{\scriptsize
\begin{tabular}{lllp{4cm}p{4cm}}
\textbf{Sentence}
& \textbf{Gold}
& \textbf{Unigram}
& \textbf{Replace \texttt{NN} with \texttt{VB}}
& \textbf{Replace \texttt{TO} with \texttt{IN}} \\
&&& \textbf{when the previous word is \texttt{TO}}
& \textbf{when the next tag is \texttt{nns}} \\ \hline
The            & AT      & AT \\
President      & NN-TL   & NN-TL \\
said           & VBD     & VBD \\
he             & PPS     & PPS \\
will           & MD      & MD \\
ask            & VB      & VB \\
Congress       & NP      & NP \\
to             & TO      & TO \\
increase       & VB      & \textit{NN}     &    \textit{VB} \\
grants         & NNS     & NNS \\
to             & IN      & \textit{TO}     &    \textit{TO} &   \textit{IN} \\
states         & NNS     & NNS \\
for            & IN      & IN \\
vocational     & JJ      & JJ \\
rehabilitation & NN      & NN
\end{tabular}
}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Summary}

\begin{frame}
  \frametitle{Summary}

  \begin{itemize}
  \item \textbf{Reading:} 
    Jurafsky and Martin, chapter 8 (esp. sec 8.5); 
    Manning and Sch\"utze, chapter 10; 
  \item Rule-based and statistical tagging
  \item HMMs and n-grams for statistical tagging
  \item Operation of a simple bigram tagger
  \item TnT --- an accurate trigram-based tagger
  \end{itemize}
\end{frame}

\end{document}
