\documentclass[14pt]{beamer}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Meta informations:
\newcommand{\trauthor}{Jim Martens}
\newcommand{\trtype}{Proseminar} %{Proseminar} %{Seminar} %{Workshop}
\newcommand{\trcourse}{Proseminar Artificial Intelligence}
\newcommand{\trtitle}{Methods for understanding natural language}
\newcommand{\trmatrikelnummer}{6420323}
\newcommand{\tremail}{2martens@informatik.uni-hamburg.de}
\newcommand{\trinstitute}{}
\newcommand{\trwebsiteordate}{26.02.2014}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Languages:

% Falls die Ausarbeitung in Deutsch erfolgt:
% \usepackage[german]{babel}
% \usepackage[T1]{fontenc}
% \usepackage[latin1]{inputenc}
% \usepackage[latin9]{inputenc}	 				
% \selectlanguage{german}

% If the thesis is written in English:
\usepackage[english]{babel} 						
\selectlanguage{english}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Bind packages:
\usepackage{beamerthemesplit}
\usetheme{Boadilla}
%\usetheme{Copenhagen}
%\usetheme{Darmstadt}
%\usetheme{Frankfurt}
%\usetheme{Ilmenau}
%\usetheme{JuanLesPins}
%\usetheme{Madrid}
%\usetheme{Warsaw }
%\usecolortheme{dolphin}
%\setbeamertemplate{sections/subsections in toc}[sections numbered]
%\beamertemplatenavigationsymbolsempty
%\setbeamertemplate{headline}[default] 	% deaktiviert die Kopfzeile
\setbeamertemplate{navigation symbols}{}% deaktiviert Navigationssymbole
%\useinnertheme{rounded}

\usepackage{acronym}                    % Acronyms
\usepackage{algorithmic}								% Algorithms and Pseudocode
\usepackage{algorithm}									% Algorithms and Pseudocode
\usepackage{amsfonts}                   % AMS Math Packet (Fonts)
\usepackage{amsmath}                    % AMS Math Packet
\usepackage{amssymb}                    % Additional mathematical symbols
\usepackage{amsthm}
\usepackage{color}                      % Enables defining of colors via \definecolor
\usepackage{fancybox}                   % Gleichungen einrahmen
\usepackage{fancyhdr}										% Paket zur schickeren der Gestaltung der 
\usepackage{graphicx}                   % Inclusion of graphics
\usepackage{tikz}
%\usepackage{wrapfig}
%\usepackage{latexsym}                  % Special symbols
\usepackage{longtable}									% Allow tables over several parges
\usepackage{listings}                   % Nicer source code listings
\usepackage{lmodern}
\usepackage{multicol}										% Content of a table over several columns
\usepackage{multirow}										% Content of a table over several rows
\usepackage{rotating}										% Alows to rotate text and objects
\usepackage[section]{placeins}          % Ermoeglich \Floatbarrier fuer Gleitobj. 
\usepackage[hang]{subfigure}            % Allows to use multiple (partial) figures in a fig
%\usepackage[font=footnotesize,labelfont=rm]{subfig}	% Pictures in a floating environment
\usepackage{tabularx}										% Tables with fixed width but variable rows
\usepackage{url,xspace,boxedminipage}   % Accurate display of URLs

\definecolor{uhhRed}{RGB}{254,0,0}		  % Official Uni Hamburg Red
\definecolor{uhhGrey}{RGB}{136,136,136} % Official Uni Hamburg Grey
\definecolor{uhhLightGrey}{RGB}{180,180,180} % Official Uni Hamburg LightGrey
\definecolor{uhhLightLightGrey}{RGB}{220,220,220} % Official Uni Hamburg LightLightGrey
\setbeamertemplate{itemize items}[ball]
\setbeamercolor{title}{fg=uhhRed,bg=white}
\setbeamercolor{title in head/foot}{bg=uhhRed}
\setbeamercolor{block title}{bg=uhhGrey,fg=white}
\setbeamercolor{block body}{bg=uhhLightLightGrey,fg=black}
\setbeamercolor{section in head/foot}{bg=black}
\setbeamercolor{frametitle}{bg=white,fg=uhhRed}
\setbeamercolor{author in head/foot}{bg=black,fg=white}
\setbeamercolor{author in footline}{bg=white,fg=black}
\setbeamercolor*{item}{fg=uhhRed}
\setbeamercolor*{section in toc}{fg=black}
\setbeamercolor*{separation line}{bg=black}
\setbeamerfont*{author in footline}{size=\scriptsize,series=\mdseries}
\setbeamerfont*{institute}{size=\footnotesize}

\newcommand{\opticalseperator}{0.0025\paperwidth}

\institute{Universit\"at Hamburg\\\trinstitute}
\title{\trtitle}
\subtitle{\trtype}
\author{\trauthor}
\date{}
\logo{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Configurationen:
%\hypersetup{pdfpagemode=FullScreen}

\hyphenation{whe-ther} 									% Manually use: "\-" in a word: Staats\-ver\-trag

%\lstloadlanguages{C}                   % Set the default language for listings
\DeclareGraphicsExtensions{.pdf,.svg,.jpg,.png,.eps} % first try pdf, then eps, png and jpg
\graphicspath{{./src/} {/home/jim/Pictures/}} 	% Path to a folder where all pictures are located

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Costom Definitions:
\setbeamertemplate{title page}
{
  \vbox{}
	\vspace{0.4cm}
  \begin{centering}
    \begin{beamercolorbox}[sep=8pt,center,colsep=-4bp]{title}
      \usebeamerfont{title}\inserttitle\par%
      \ifx\insertsubtitle\@empty%
      \else%
        \vskip0.20em%
        {\usebeamerfont{subtitle}\usebeamercolor[fg]{subtitle}\insertsubtitle\par}%
      \fi%     
    \end{beamercolorbox}%
		\vskip0.4em
    \begin{beamercolorbox}[sep=8pt,center,colsep=-4bp,rounded=true,shadow=true]{author}
      \usebeamerfont{author}\insertauthor \\ \insertinstitute
    \end{beamercolorbox}

	  \vfill
	  %\begin{beamercolorbox}[ht=8ex,center]{}
	  %  \includegraphics[width=0.20\paperwidth]{wtmIcon.pdf}
	  %\end{beamercolorbox}%
    \begin{beamercolorbox}[sep=8pt,center,colsep=-4bp,rounded=true,shadow=true]{institute}
      \usebeamerfont{institute}\trwebsiteordate
    \end{beamercolorbox}
		\vspace{-0.1cm}
  \end{centering}
}

\setbeamertemplate{frametitle}
{
\begin{beamercolorbox}[wd=\paperwidth,ht=3.8ex,dp=1.2ex,leftskip=0pt,rightskip=4.0ex]{frametitle}%
		\usebeamerfont*{frametitle}\centerline{\insertframetitle}
	\end{beamercolorbox}
	\vspace{0.0cm}
}

\setbeamertemplate{footline}
{
  \leavevmode
	\vspace{-0.05cm}
  \hbox{
	  \begin{beamercolorbox}[wd=.32\paperwidth,ht=4.8ex,dp=2.7ex,center]{author in footline}
	    \hspace*{2ex}\usebeamerfont*{author in footline}\trauthor
	  \end{beamercolorbox}%
	  \begin{beamercolorbox}[wd=.60\paperwidth,ht=4.8ex,dp=2.7ex,center]{author in footline}
	    \usebeamerfont*{author in footline}\trtitle
	  \end{beamercolorbox}%
	  \begin{beamercolorbox}[wd=.07\paperwidth,ht=4.8ex,dp=2.7ex,center]{author in footline}
	    \usebeamerfont*{author in footline}\insertframenumber{}
	  \end{beamercolorbox}
  }
	\vspace{0.15cm}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Additional 'theorem' and 'definition' blocks:
\newtheorem{axiom}{Axiom}[section] 	
%\newtheorem{axiom}{Fakt}[section]			% Wenn in Deutsch geschrieben wird.
%Usage:%\begin{axiom}[optional description]%Main part%\end{fakt}

%Additional types of axioms:
\newtheorem{observation}[axiom]{Observation}

%Additional types of definitions:
\theoremstyle{remark}
%\newtheorem{remark}[section]{Bemerkung} % Wenn in Deutsch geschrieben wird.
\newtheorem{remark}[section]{Remark} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Provides TODOs within the margin:
\newcommand{\TODO}[1]{\marginpar{\emph{\small{{\bf TODO: } #1}}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Abbreviations and mathematical symbols
\newcommand{\modd}{\text{ mod }}
\newcommand{\RS}{\mathbb{R}}
\newcommand{\NS}{\mathbb{N}}
\newcommand{\ZS}{\mathbb{Z}}
\newcommand{\dnormal}{\mathit{N}}
\newcommand{\duniform}{\mathit{U}}

\newcommand{\erdos}{Erd\H{o}s}
\newcommand{\renyi}{-R\'{e}nyi}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Display of TOCs:
%\AtBeginSection[]
%{
%	\setcounter{tocdepth}{2}  
%	\frame
%	{
%	  \frametitle{Outline}
%		\tableofcontents[currentsection]
%	}
%}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Document:
\begin{document}
\renewcommand{\arraystretch}{1.2}

\begin{frame}[plain] % plain => kein Rahmen
  \titlepage
\end{frame}
%\setcounter{framenumber}{0}

%%%%%%%%%%%%%%
% Your Content

\section*{Motivation and Question}

\begin{frame}[t]{Motivation}
	\begin{columns}[t]
		\begin{column}{0.5\textwidth}	
			\begin{itemize}
	  			\item<2-> Dialogue in computer games
				\begin{itemize}
					\item<3-> spoken
					\item<4-> written
				\end{itemize}
				\item<5-> Ambiguity
				\item<5-> Disambiguation
				%\item Use references \textsuperscript{[Author, 2010]}
			\end{itemize}
		\end{column}
		\begin{column}{68mm}\centering
			\begin{pgfpicture}{0cm}{3cm}{1cm}{0cm}
				\pgfbox[center,center]{\includegraphics[scale=0.15]{massEffectDialogScreenshot}}
			\end{pgfpicture}
		\end{column}
		
	\end{columns}
\end{frame}

\begin{frame}{Outline}
	\tableofcontents
\end{frame}

\section{Definitions}

\begin{frame}[t]{Definitions}
	\begin{itemize}
		\item Syntax
		\begin{itemize}
			\item Describes the sentence structure (e.g. simple subject--predicate--object order) and kind (e.g. declarative, question, order)
		\end{itemize}
		\item Grammar
		\begin{itemize}
			\item Specifies valid sentences
		\end{itemize}
		\item Semantics
		\begin{itemize}
			\item Meaning of the written words
		\end{itemize}
		\item Pragmatics
		\begin{itemize}
			\item Meaning of words in a given context or actual meaning
		\end{itemize}
	\end{itemize}
\end{frame}

\section{Syntactic Parsing}

\begin{frame}[t,fragile]{Lexicon}
	\begin{columns}[t]
		\begin{column}{0.5\textwidth}
			\begin{itemize}
				\item Allowed words \textsuperscript{[Russel, 2009]}
				\item Probabilities
			\end{itemize}
		\end{column}
		\begin{column}{0.5\textwidth}
			Example:
			\begin{alignat*}{2}
				Noun &\rightarrow && \text{tree [1.00]} \\
				Verb &\rightarrow && \text{is [1.00]} \\
				Adjective &\rightarrow && \text{high [1.00]} \\
				Article &\rightarrow && \text{the [1.00]} \\
			\end{alignat*}
		\end{column}
	\end{columns}
\end{frame}

\begin{frame}[t]{Grammar}
	\begin{itemize}
		\item Combines words into valid phrases \textsuperscript{[Russel, 2009]}
		\item Base for all kinds of parsing
		\item Probabilities
		\item Defines valid syntax
	\end{itemize}
\end{frame}
\begin{frame}[t,fragile]{Grammar}
	Example:
	\begin{alignat*}{2}
				S \;&\rightarrow &\; NP\;\;VP \;&[1.00] \\
				NP \;&\rightarrow &\; A\;N \;&[1.00]\\
				A \;&\rightarrow &\; Article\;&[1.00]\\
				N \;&\rightarrow &\; Noun\;&[1.00]\\
				VP \;&\rightarrow &\; Verb \;&[0.40] \\
				\;&|&\; VP\;Adjs \;&[0.60] \\
				Adjs \;&\rightarrow &\; Adjective \;&[0.80] \\
				\;&|&\; Adjective\;Adjs \;&[0.20]
			\end{alignat*}
\end{frame}

\begin{frame}[t]{Cocke Younger Kasami (CYK)}
	\begin{itemize}
		\item Named after inventors \textsuperscript{[Russel, 2009]}
		\begin{itemize}
			\item John Cocke (1925--2002)
			\item Daniel H. Younger
			\item Tadeo Kasami (1930--2007)
		\end{itemize}
		\item Dynamic programming parsing algorithm \textsuperscript{[Russel, 2009]}
		\item Works only with grammars in CNF \textsuperscript{[Russel, 2009]}
		\item Probabilities serve as disambiguation \textsuperscript{[Russel, 2009]}
		\item Best algorithm for general CFGs \textsuperscript{[Russel, 2009]}
	\end{itemize}
\end{frame}

\begin{frame}[t]{CYK Example}
	\centering
	\begin{tabular}{|c|c|c|c|}
			\hline
			X & start & length & p \\
			\hline
			\hline
			A & 1 & 1 & 1.00 \\
			\hline
			N & 2 & 1 & 1.00 \\
			\hline				
			VP & 3 & 1 & 0.40 \\
			\hline
			Adjs & 4 & 1 & 0.80 \\
			\hline
			Adjs & 5 & 1 & 0.80 \\
			\hline
		\end{tabular}
\end{frame}

\section{Semantic Analysis}

\begin{frame}[t]{Semantic Analysis}
	\begin{itemize}
		\item Syntax-driven semantic analysis \textsuperscript{[Jurafsky, 2009]}
		\item Syntax representation
		\begin{itemize}
			\item Parse trees \textsuperscript{[Jurafsky, 2009]}
			\item Dependency structures \textsuperscript{[Jurafsky, 2009]}
			\item etc
		\end{itemize}
		\item First--Order Logic
		\item Lambda notation
		\item Semantic attachments
		\item Meaning representation
	\end{itemize}
\end{frame}

\begin{frame}[t,fragile]{Semantic Analysis}
	Example of semantic attachment:
	\[
		A \rightarrow the \;\{\lambda x.\lambda P.\exists x.P(x)\}
	\]
	Example of meaning representation:
	\[
		\exists x.Tree(x) \Rightarrow \exists a.Very(a) \wedge HighThing(a, x)
	\]
\end{frame}


\section{Conclusion}

\begin{frame}[t]{Conclusion}
	\begin{itemize}
		\item Ambiguity remains large problem
		\item Parsing and semantic analysis need restriction
		\item Context is key
	\end{itemize}
\end{frame}

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

\begin{frame}[c]{The End}
	\begin{center}
		Thank you for your attention.\\[1ex]
		Any questions?\\[5ex]
	\end{center}
	\footnotesize
	Literature:
	\begin{itemize}
		\item Daniel Jurafsky and James H. Martin. \emph{Speech and Language processing}. Pearson, 2009
		\item Stuart J. Russel and Peter Norvig. \emph{Artificial intelligence: A Modern Approach}. Pearson, 2009
	\end{itemize}
	Pictures:
	\begin{itemize}
		\item Motivation: Mass Effect 1 Screenshot from IGN.com
	\end{itemize}
\end{frame}

\end{document}