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

\title{Chunk Parsing}

\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{What is it?}

\begin{frame}
\begin{itemize}
\item chunk parsing:
  \begin{itemize}
    \item efficient and robust approach to parsing natural language
    \item a popular alternative to the full parsing
  \end{itemize}
\item chunks:
  \begin{itemize}
  \item non-overlapping regions of text
  \item contain a head word (e.g. noun)
  \item adjacent modifiers and function words
  \end{itemize}
\item motivations:
  \begin{itemize}
  \item extract information
  \item ignore information
  \end{itemize}
\end{itemize}
\end{frame}
\subsection{Motivation}

\pgfdeclareimage[width=12cm]{chunk-coref}{../images/chunk-coref}
\begin{frame}
  \frametitle{Extracting Information: Coreference Annotation}
  \centerline{\pgfuseimage{chunk-coref}}
\end{frame}

\pgfdeclareimage[width=12cm]{chunk-muc}{../images/chunk-muc}
\begin{frame}
  \frametitle{Extracting Information: Message Understanding}
  \centerline{\pgfuseimage{chunk-muc}}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Ignoring Information: Lexical Acquisition}

  \begin{itemize}
  \item studying syntactic patterns, e.g. finding verbs in a corpus, displaying possible arguments
  \item e.g. \texttt{gave}, in 100 files of the Penn Treebank corpus
  \item replaced internal details of each noun phrase with \texttt{NP}

\begin{verbatim}
  gave NP
  gave up NP in NP
  gave NP up
  gave NP help
  gave NP to NP
\end{verbatim}
    
  \item use in lexical acquisition, grammar development
  \end{itemize}
\end{frame}

\subsection{Analogy with Tokenization and Tagging}

\pgfdeclareimage[width=8cm]{chunk-segmentation}{../images/chunk-segmentation}
\begin{frame}[fragile]
  \frametitle{Analogy with Tokenization and Tagging}

  \begin{itemize}
  \item fundamental in NLP: segmentation and labelling
  \item tokenization and tagging \\[2ex]
  \centerline{\pgfuseimage{chunk-segmentation}}
  \item other similarities: skipping material; finite-state; application specific
  \end{itemize}
\end{frame}

\subsection{Chunking vs Parsing}

\begin{frame}[fragile]
  \frametitle{Chunking vs Parsing}
  \scriptsize

  \begin{enumerate}
  \item Parsing
\begin{verbatim}
  [
    [ G.K. Chesterton ],
    [
      [ author ] of
      [
        [ The Man ] who was
        [ Thursday ]
      ]
    ]
  ]
\end{verbatim}

  \item Chunking:
\begin{verbatim}
  [ G.K. Chesterton ],
  [ author ] of
  [ The Man ] who was
  [ Thursday ]
\end{verbatim}
\end{enumerate}
\end{frame}

\begin{frame}
  \frametitle{Chunking vs Parsing}
  \begin{enumerate}
  \item flat vs nested
  \item context
  \item robustness
  \item efficiency
  \item methodology
  \end{enumerate}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Perfection is unattainable}

\begin{verbatim}
  1. Prepositional phrase:
  [
    [ I ]
    [ turned ]
    [ off the spectroroute ]
  ]

  2. Verb-particle construction:
  [
    [ I ]
    [ turned off ]
    [ the spectroroute ]
  ]
\end{verbatim}
\end{frame}


\section{Accessing Chunked Corpora}

\subsection{Representing Chunks: Tags vs Trees}

\pgfdeclareimage[width=8cm]{chunk-tagrep}{../images/chunk-tagrep}
\begin{frame}
  \frametitle{Tag Representation}
  \centerline{\pgfuseimage{chunk-tagrep}}
\end{frame}

\pgfdeclareimage[width=8cm]{chunk-treerep}{../images/chunk-treerep}
\begin{frame}
  \frametitle{Tree Representation}
  \centerline{\pgfuseimage{chunk-treerep}}
\end{frame}

\subsection{Chunk Structures}

\begin{frame}[fragile]
  \frametitle{Chunk Structures}
\begin{verbatim}
  (S: (NP: 'I')
      'saw'
      (NP: 'the' 'big' 'dog')
      'on'
      (NP: 'the' 'hill'))
\end{verbatim}
  \begin{itemize}
  \item Demonstration: reading chunk structures from Treebank and CoNLL-2000 corpora
  \end{itemize}
\end{frame}

\section{Chunk Parsing}

\subsection{Chunking with Regular Expressions}

\begin{frame}[fragile]
  \frametitle{Chunk Parsing}
  \small

  \begin{itemize}
  \item regular expressions over part-of-speech tags: \texttt{parse.RegexpChunk}
  \item \textit{Tag string:} a string consisting of tags
    delimited with angle-brackets,
    e.g. \verb/<DT><JJ><NN><VBD><DT><NN>/
  \item \textit{Tag pattern:} regular expression over tag strings
    \begin{itemize}
    \item \verb/<DT><JJ>?<NN>/
    \item \verb/<NN|JJ>+/
    \item \verb/<NN.*>/
    \end{itemize}
  \item chunk a sequence of words matching a tag pattern: \texttt{parse.ChunkRule}

\begin{verbatim}
    >>> grammar = "NP: {<DT|NN>+}  # Chunk sequences of DT and NN'"
\end{verbatim}

  \end{itemize}
\end{frame}


\begin{frame}[fragile]
  \frametitle{A Simple NP Chunker}
  \scriptsize

\begin{verbatim}
    import nltk
    grammar = r"""
    NP:
      {<DT>?<JJ>*<NN>}    # chunk determiners, adjectives and nouns
      {<NNP>+}            # chunk sequences of proper nouns
    """
    cp = nltk.RegexpParser(grammar)
    tagged_tokens = [("the", "DT"), ("little", "JJ"), ("cat", "NN"),
         ("sat", "VBD"), ("on", "IN"), ("the", "DT"), ("mat", "NN")]

    >>> print cp.parse(tagged_tokens)
    (S (NP the/DT little/JJ cat/NN) sat/VBD on/IN (NP the/DT mat/NN))
\end{verbatim}
\end{frame}

\subsection{Developing Chunkers}

\begin{frame}[fragile]
  \frametitle{Developing Chunkers}
  \tiny

\begin{verbatim}
    cp1 = nltk.RegexpParser(r"""
    NP: {<DT><JJ><NN>}      # Chunk det+adj+noun
        {<DT|NN>+}          # Chunk sequences of NN and DT
    """)
    cp2 = nltk.RegexpParser(r"""
    NP: {<DT|NN>+}          # Chunk sequences of NN and DT
        {<DT><JJ><NN>}      # Chunk det+adj+noun
    """)
    
    >>> print cp1.parse(tagged_tokens, trace=1)
    # Input:
     <DT>  <JJ>  <NN>  <VBD>  <IN>  <DT>  <NN> 
    # Chunk det+adj+noun:
    {<DT>  <JJ>  <NN>} <VBD>  <IN>  <DT>  <NN> 
    # Chunk sequences of NN and DT:
    {<DT>  <JJ>  <NN>} <VBD>  <IN> {<DT>  <NN>}
\end{verbatim}

\begin{itemize}
  \item tracing; rule ordering; overlapping contexts
\end{itemize}
\end{frame}

\subsection{More Chunking Rules}

\begin{frame}[fragile]
  \frametitle{More Chunking Rules: Chinking}
  \small

  \begin{itemize}
  \item \textit{chink:} sequence of stopwords
  \item \textit{chinking:} process of removing tokens from a chunk
  \end{itemize}

  \tiny

\begin{tabular}{llll}
& \textbf{Entire chunk}
& \textbf{Middle of a chunk}
& \textbf{End of a chunk} \\
\textbf{Input:}
& \verb|[a/DT  big/JJ  cat/NN]|
& \verb|[a/DT  big/JJ  cat/NN]|
& \verb|[a/DT  big/JJ  cat/NN]| \\
\textbf{Operation:}
& Chink \verb|a/DT big/JJ cat/NN|
& Chink \verb|big/JJ|
& Chink \verb|cat/NN| \\
\textbf{Output:}
& \verb|a/DT  big/JJ  cat/NN|
& \verb|[a/DT] big/JJ [cat/NN]|
& \verb|[a/DT  big/JJ] cat/NN|
\end{tabular}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Chinking Example}
  \scriptsize

\begin{verbatim}
    >>> grammar = r"""
    ... NP:
    ...   {<.*>+}          # Chunk everything
    ...   }<VBD|IN>+{      # Chink sequences of VBD and IN
    ... """
    >>> cp = nltk.RegexpParser(grammar)
    >>> print cp.parse(tagged_tokens)
    (S:
      (NP: ('the', 'DT') ('little', 'JJ') ('cat', 'NN'))
      ('sat', 'VBD')
      ('on', 'IN')
      (NP: ('the', 'DT') ('mat', 'NN')))
    >>> print nltk.chunk.accuracy(cp, nltk.corpus.conll2000.chunked_sents(chunk_types=('NP',)))
    0.581041433607
\end{verbatim}
\end{frame}

\section{Evaluating Chunk Parsers}

\subsection{Precision and Recall}

\begin{frame}
  \frametitle{Evaluating Chunk Parsers}

  \begin{itemize}
  \item Process:
    \begin{enumerate}
    \item take some already chunked text
    \item strip off the chunks
    \item rechunk it
    \item compare the result with the original chunked text
    \end{enumerate}
  \item \texttt{ChunkScore.score()}
    \begin{itemize}
    \item \textit{precision}: what fraction of the returned chunks were correct?
    \item \textit{recall}: what fraction of correct chunks were returned?
    \end{itemize}
  \end{itemize}
\end{frame}

\pgfdeclareimage[width=8cm]{precision-recall}{../images/precision-recall}
\begin{frame}
  \frametitle{Precision and Recall}
  \centerline{\pgfuseimage{precision-recall}}
\end{frame}

\subsection{Evaluation in NLTK}

\begin{frame}[fragile]
  \frametitle{Chunker evaluation in NLTK}
  \scriptsize

\begin{verbatim}
>>> chunkscore = nltk.chunk.ChunkScore()
>>> for chunk_struct in nltk.corpus.treebank.chunked_sents()[:10]:
...     test_sent = cp.parse(chunk_struct.leaves())
...     chunkscore.score(chunk_struct, test_sent)
>>> print chunkscore
ChunkParse score:
    Precision:  48.6%
    Recall:     34.0%
    F-Measure:  40.0%
\end{verbatim}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Error Analysis: Missed Chunks}
  \scriptsize

\begin{verbatim}
>>> from random import randint
>>> missed = chunkscore.missed()
>>> for i in range(15):
...     print missed[randint(0,len(missed)-1)]
(('A', 'DT'), ('Lorillard', 'NNP'), ('spokewoman', 'NN'))
(('it', 'PRP'),)
(('symptoms', 'NNS'),)
(('even', 'RB'), ('brief', 'JJ'), ('exposures', 'NNS'))
(('its', 'PRP$'), ('Micronite', 'NN'), ('cigarette', 'NN'), ('filters', 'NNS'))
(('30', 'CD'), ('years', 'NNS'))
(('workers', 'NNS'),)
(('preliminary', 'JJ'), ('findings', 'NNS'))
(('Medicine', 'NNP'),)
(('cancer', 'NN'), ('deaths', 'NNS'))
(('Consolidated', 'NNP'), ('Gold', 'NNP'), ('Fields', 'NNP'), ('PLC', 'NNP'))
(('Medicine', 'NNP'),)
(('its', 'PRP$'), ('Micronite', 'NN'), ('cigarette', 'NN'), ('filters', 'NNS'))
(('a', 'DT'), ('forum', 'NN'))
(('researchers', 'NNS'),)
\end{verbatim}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Error Analysis: Incorrect Chunks}
  \scriptsize

\begin{verbatim}
>>> incorrect = chunkscore.incorrect()
>>> for i in range(15):
...     print incorrect[randint(0,len(incorrect)-1)]
(('New', 'JJ'), ('York-based', 'JJ'))
(('Micronite', 'NN'), ('cigarette', 'NN'))
(('a', 'DT'), ('forum', 'NN'), ('likely', 'JJ'))
(('later', 'JJ'),)
(('later', 'JJ'),)
(('brief', 'JJ'),)
(('preliminary', 'JJ'),)
(('New', 'JJ'), ('York-based', 'JJ'))
(('resilient', 'JJ'),)
(('group', 'NN'),)
(('cancer', 'NN'),)
(('the', 'DT'),)
(('cancer', 'NN'),)
(('Micronite', 'NN'), ('cigarette', 'NN'))
(('A', 'DT'),)
\end{verbatim}
\end{frame}

\subsection{Evaluation Methodology}

\begin{frame}
  \frametitle{Evaluation Methodology}
  \begin{itemize}
  \item Baseline:
    \begin{itemize}
    \item How hard is chunking?
    \item What is a good baseline for evaluation?
    \end{itemize}
  \item Bake-off
  \end{itemize}
\end{frame}

\subsection{Development Methodology}

\begin{frame}
  \frametitle{Development Methodology}
  \begin{itemize}
  \item approaches
    \begin{itemize}
    \item different rules and combinations
    \item hand-crafted vs automatic
    \end{itemize}
  \item focus on diagnosis:
    \begin{itemize}
    \item manual
    \item utility functions
    \item error analysis
    \item evaluation
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Conclusion}
  \begin{itemize}
  \item light-weight methods: as seen in tagging
  \item applications: extraction, lexical acquisition\\
    (aside: chunking as a utility method in parsing)
  \item next: parsing
  \item but first: switch to application focus
  \end{itemize}
\end{frame}

\end{document}

