% !Mode:: "TeX:GBK"

\def\CTeXPreproc{Created by ctex v0.2.13, don't edit!}
\documentclass[cjk,t,compress,12pt]{beamer}
%\documentclass{article}
%\usepackage{beamerarticle}
\usepackage{pstricks}
\usepackage{etex}
\usepackage{eso-pic,graphicx}
\usepackage{fancybox}
\usepackage{amsmath,amssymb}
\usepackage{setspace}
\usepackage{xcolor}
\usepackage{CJK}
\usepackage{tikz}
\usepackage{tikz-qtree}
\usepackage{hyperref}

\usetikzlibrary{shadows} % LATEX and plain TEX when using Tik Z


\usepgflibrary{arrows} % LATEX and plain TEX and pure pgf
\usetikzlibrary{arrows} % LATEX and plain TEX when using Tik Z
\usetikzlibrary{decorations}
\usetikzlibrary{arrows,shapes}

\usetikzlibrary{positioning,fit,calc}

\usetikzlibrary{mindmap,backgrounds} % mind map

\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}

\setbeamertemplate{items}[ball]
\usefonttheme[onlymath]{serif}  % fout of math

\definecolor{ugreen}{rgb}{0,0.5,0}
\definecolor{lgreen}{rgb}{0.9,1,0.8}
\definecolor{xtgreen1}{rgb}{0.824,0.898,0.8}
\definecolor{xtgreen}{rgb}{0.914,0.945,0.902}
\definecolor{lightgray}{gray}{0.85}

\setbeamercolor{uppercol}{fg=white,bg=ugreen}
\setbeamercolor{lowercol}{fg=black,bg=xtgreen}

%\definecolor{ublue}{rgb}{0,0.298,0.525}
\definecolor{ublue}{rgb}{0.152,0.250,0.545}
\setbeamercolor{uppercolblue}{fg=white,bg=ublue}
\setbeamercolor{lowercolblue}{fg=black,bg=blue!10}


%\usetheme{default}
%\usetheme{Darmstadt}
%\usetheme{Madrid}
%\usetheme{Frankfurt}
%\usetheme{Dresden}
%\usetheme{Boadilla}
%\usecolortheme{dolphin}


\usefonttheme[onlylarge]{structurebold}

\begin{CJK}{GBK}{song}
\end{CJK}

\setbeamerfont*{frametitle}{size=\large,series=\bfseries}
\setbeamertemplate{navigation symbols}{\begin{CJK}{GBK}{hei} 第二章 词法、语法及概率思想基础 \hspace*{2em} 肖桐\&朱靖波 \end{CJK} \hspace*{2em} \today \hspace*{2em} \insertframenumber{}/\inserttotalframenumber}

\setbeamertemplate{itemize items}[circle] % if you want a circle
\setbeamertemplate{itemize subitem}[triangle] % if you wnat a triangle
\setbeamertemplate{itemize subsubitem}[ball] % if you want a ball

\begin{document}

\begin{CJK}{GBK}{you}

\title{\Large{词法、语法及统计思想基础}}
\author{\large{\textbf{肖桐\ \ 朱靖波}}}
\institute{
\blue{\url{xiaotong@mail.neu.edu.cn}} \black{} \\
\blue{\url{zhujingbo@mail.neu.edu.cn}} \black{} \\
\vspace{1.0em}
东北大学 自然语言处理实验室 \\
\blue{\underline{\url{http://www.nlplab.com}}} \black{} \\
\vspace{0.2cm}
\hspace{0.1cm} \includegraphics[scale=0.1]{../Figures/logo.pdf}
}
\date{}

\maketitle

\setlength{\leftmargini}{1em}
\setlength{\leftmarginii}{1em}

%%%------------------------------------------------------------------------------------------------------------
\section{机器翻译的输入和输出}

%%%------------------------------------------------------------------------------------------------------------
%%% 机器翻译的输入、输出
\begin{frame}{输入和输出是啥样子？}

\only<1>{我们看到的}\only<2->{\alert{真实的}}机器翻译(MT)系统 - \visible<2->{词序列？}\visible<3->{树？}\\

\vspace{0.3em}
\begin{tikzpicture}

\begin{scope}
\node [] (input) at (0,0) {{\scriptsize 猫喜欢吃鱼}};

\visible<2->{
\begin{scope}[scale=0.8,xshift=0.9in,yshift=-0.87in,level distance=20pt,sibling distance=-1pt,grow'=up]
{\scriptsize
\Tree[.\node(sn0){IP};
          [.\node(sn1){NP};
               [.\node(sn2){NN}; \node(sw1){猫}; ]
          ]
          [.\node(sn3){VP};
               [.\node(sn4){VV}; \node(sw2){喜欢}; ]
               [.\node(sn5){VP}; \edge[roof]; \node(sw3){吃 \ 鱼}; ]
          ]
     ]
}
\end{scope}

\node [anchor=west,draw,thick,inner sep=3pt,ublue] (mtengine) at ([xshift=1.05in]input.east) {{\scriptsize MT系统}};

\begin{scope}[scale=0.8,xshift=3.0in,yshift=-0.87in,level distance=20pt,sibling distance=-3pt,grow'=up]
{\scriptsize
\Tree[.\node(tn0){S};
          [.\node(tn1){NP};
               [.\node(tn2){NNS}; \node(tw1){cats}; ]
          ]
          [.\node(tn3){VP};
               [.\node(tn4){VB}; \node(tw2){like}; ]
               [.\node(tn5){VP}; \edge[roof]; \node(tw3){eating fish}; ]
          ]
     ]
}

\end{scope}
}

\node [] (output) at ([xshift=3.35in]input.east) {{\scriptsize Cats like eating fish}};

\visible<7->{
\draw[<-,thick,dotted,ublue] ([xshift=0.2em,yshift=-0.3em]input.east)--([xshift=0.2em,yshift=-5em]input.east);
\draw[<-,thick,dotted,ublue] ([xshift=-0.5em,yshift=-0.3em]output.west)--([xshift=-0.5em,yshift=-5em]output.west);
\node [draw,thick,ublue,anchor=north] (preprocessing) at ([xshift=0.2em,yshift=-5em]input.east) {{\scriptsize 预处理}};
\node [draw,thick,ublue,anchor=north] (postprocessing) at ([xshift=-0.5em,yshift=-5em]output.west) {{\scriptsize 后处理}};
}

\draw[->,thick] ([xshift=-1pt]input.east) -- ([xshift=8pt]input.east);
\draw[->,thick] ([xshift=-10pt]output.west) -- ([xshift=-0pt]output.west);

\visible<2->{
\draw[->,thick] ([xshift=-12pt]mtengine.west) -- ([xshift=-2pt]mtengine.west);
\draw[->,thick] ([xshift=2pt]mtengine.east) -- ([xshift=12pt]mtengine.east);
}

\visible<2>{
\node[minimum height=4em,minimum width=4.5em,fill=white] (inputmarking) at (0.85in,-0.39in) {};
\node[minimum height=4em,minimum width=5.2em,fill=white] (outputmarking) at (2.55in,-0.39in) {};
}

\node [anchor=south] (inputlabel) at ([yshift=-0.5em]input.north) {{\scriptsize \alert{\textbf{输入}}}};
\node [anchor=south] (outputlabel) at ([yshift=-0.5em]output.north) {{\scriptsize \alert{\textbf{输出}}}};

\visible<2->{
\node [anchor=west] (mtinputlabel) at ([xshift=0.29in]inputlabel.east) {{\scriptsize \alert{\textbf{实际的输入}}}};
\node [anchor=west] (mtoutputlabel) at ([xshift=0.86in]mtinputlabel.east) {{\scriptsize \alert{\textbf{实际的输出}}}};
\node[rectangle,draw=ublue, inner sep=0mm] [fit = (mtinputlabel) (mtoutputlabel) (inputmarking) (outputmarking)] {};
}

\visible<1>{
\node[rectangle,fill=ublue,inner sep=0mm] [fit = (mtinputlabel) (mtoutputlabel) (inputmarking) (outputmarking)] {{\color{white} \textbf{\Large{MT 系统}}}};
}


\begin{scope}[scale=0.9,xshift=1.2in,yshift=-1.2in,level distance=20pt,sibling distance=0pt]

\visible<4>{
{\footnotesize
\Tree[.\node(bsn0){IP};
          [.\node(bsn1){NP};
               [.\node(bsn2){NN}; \node(bsw1){猫}; ]
          ]
          [.\node(bsn3){VP};
               [.\node(bsn4){VV}; \node(bsw2){喜欢}; ]
               [.\node(bsn5){VP}; \edge[roof]; \node(bsw3){吃 \ 鱼}; ]
          ]
     ]
}
}

\visible<4->{
\draw[->,thick] (sn3.-30) .. controls +(south east:1) and +(north west:1) .. ([xshift=-0.5em]bsn0.west);
}

\visible<5>{
{\footnotesize
\Tree[.\node(bsn0){IP};
          [.\node(bsn1){NP};
               [.\node(bsn2){NN}; \node(bsw1){\alert{\textbf{猫}}}; ]
          ]
          [.\node(bsn3){VP};
               [.\node(bsn4){VV}; \node(bsw2){\alert{\textbf{喜欢}}}; ]
               [.\node(bsn5){VP}; \edge[roof]; \node(bsw3){\alert{\textbf{吃 \ 鱼}}}; ]
          ]
     ]
}
}

\visible<6->{
{\footnotesize
\Tree[.\node(bsn0)[fill=ugreen!50,inner sep=2pt]{IP};
          [.\node(bsn1)[fill=ugreen!50,inner sep=2pt]{NP};
               [.\node(bsn2)[fill=ublue!50,inner sep=2pt]{NN}; \node(bsw1){\alert{\textbf{猫}}}; ]
          ]
          [.\node(bsn3)[fill=ugreen!50,inner sep=2pt]{VP};
               [.\node(bsn4)[fill=ublue!50,inner sep=2pt]{VV}; \node(bsw2){\alert{\textbf{喜欢}}}; ]
               [.\node(bsn5)[fill=ugreen!50,inner sep=2pt]{VP}; \edge[roof]; \node(bsw3){\alert{\textbf{吃 \ 鱼}}}; ]
          ]
     ]
}
}

{\scriptsize
\visible<4->{
\node[anchor=west] (line1) at (0.8in,-0.0in) {啥东东？？？};
}
\visible<5->{
\node[anchor=north west] (line2) at (line1.south west) {1. 句子按单词切开};
}
\visible<6->{
\node[anchor=north west] (line3) at (line2.south west) {2. 归纳为树状结构};
}
}
\end{scope}

\end{scope}

\end{tikzpicture}

\visible<8->{
\begin{spacing}{1.0}
{\small
机器翻译系统依赖\alert{预处理}和\alert{后处理}系统，以汉英翻译为例：
\vspace{-0.3em}
\begin{itemize}
\item 预处理：对输入句子进行单词切分，有时进行专名识别和句法分析
\vspace{-0.8em}
\item 后处理：对输出结果进行detoken，有时进行大小写恢复
\end{itemize}
}
\end{spacing}
}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 本章的内容 - 分词、句法树、概率描述
\begin{frame}{这一章都讲啥}
\begin{spacing}{1.1}
\begin{itemize}
\item 机器翻译系统的输入及输出会依赖\alert{很多}语言学分析工具，比如，分词、词语形态学分析、专名识别/翻译、词性标注、短语结构句法分析等等
\item<2-> 不同翻译任务所使用的语言学工具不同，我们这里以汉语为例，介绍三方面内容：
    \begin{itemize}
    \item<2-> （中文）分词：将句子按单词进行切割
    \item<3-> 短语结构分析：将单词序列表示为短语结构树
    \item<4-> 概率思想介绍：上面两者的概率化描述 - \alert{作为统计机器翻译内容介绍的基础}
    \end{itemize}
\end{itemize}
\end{spacing}

\vspace{-1.5em}
\begin{center}
\begin{tikzpicture}
\begin{scope}
\visible<2->{
\node [] (sent) at (0,0) {猫喜欢吃鱼};
\node [anchor=north west] (words) at ([yshift=-1em]sent.south west) {猫 / 喜欢 / 吃 / 鱼};
\draw [<-,double,thick,ublue] (words.north) -- ([yshift=1em]words.north);
}
\visible<4->{
\node [anchor=east] (p) at ([xshift=0.5em]words.west) {\alert{\large{P(}}};
\node [anchor=west] (eq) at ([xshift=-0.5em]words.east) {\alert{\large{)=?}}};
}
\end{scope}

\begin{scope}[xshift=2in,yshift=2.5em,level distance=22pt]
\visible<3->{
\Tree[.\node(bsn0){IP};
          [.\node(bsn1){NP};
               [.\node(bsn2){NN}; \node(bsw1){猫}; ]
          ]
          [.\node(bsn3){VP};
               [.\node(bsn4){VV}; \node(bsw2){喜欢}; ]
               [.\node(bsn5){VP}; \edge[roof]; \node(bsw3){吃 \ 鱼}; ]
          ]
     ]
}
\visible<4->{
\node [anchor=east] (p) at ([xshift=0em]\subtreeof{bsn0}.west) {\alert{\large{P}\LARGE{(}}};
\node [anchor=west] (eq) at ([xshift=-0em]\subtreeof{bsn0}.east) {\alert{\LARGE{)}\large{=?}}};
}
\end{scope}
\end{tikzpicture}
\end{center}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
\section{中文分词}

%%%------------------------------------------------------------------------------------------------------------
\subsection{如何定义"词"}

%%%------------------------------------------------------------------------------------------------------------
%%% outline
\begin{frame}{Outline}

\begin{center}
\begin{tikzpicture}

{\Large
\node [anchor=west,draw,ublue,very thick,rounded corners=4pt,text width=15em,align=left,fill=white,drop shadow={shadow xshift=0.1em,shadow yshift=-0.1em}] (p1) at (0,0) {\black{\textbf{1. 词法分析}}\\\black{\textbf{\hspace{1.0em} - 中文分词 + 统计思想介绍}}};

\node [anchor=north west,draw,gray,very thick,rounded corners=4pt,text width=15em,align=left,fill=white,drop shadow={shadow xshift=0.1em,shadow yshift=-0.1em}] (p21) at ([yshift=-1em]p1.south west) {\gray{\textbf{2. 句法分析}}\\\gray{\textbf{\hspace{1.0em} - 中文短语结构树分析}}};
}

\end{tikzpicture}
\end{center}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 词法分析 - 分词
\begin{frame}{词法分析}
\label{wordsegdef}

\begin{itemize}
\item 对于统计机器翻译系统而言，输入的是已经切分好的单词序列，而不是原始的字符串
    \begin{itemize}
    \item 我们需要通过\alert{词法分析}系统来得到这种切分
    \end{itemize}
    \vspace{0.5em}
    \begin{tikzpicture}
    {\footnotesize
    \node [ugreen] (input) at (0,0) {猫喜欢吃鱼};
    \node [draw,thick,anchor=west,ublue] (preprocessing) at ([xshift=1em]input.east) {分词系统};
    \node [ugreen,anchor=west] (mtinput) at ([xshift=1em]preprocessing.east) {猫/喜欢/吃/鱼};
    \node [draw,thick,anchor=west,ublue] (smt) at ([xshift=1em]mtinput.east) {SMT系统};
    \node [anchor=west] (mtoutput) at ([xshift=1em]smt.east) {...};
    \draw [->,thick,ublue] ([xshift=0.1em]input.east) -- ([xshift=-0.2em]preprocessing.west);
    \draw [->,thick,ublue] ([xshift=0.2em]preprocessing.east) -- ([xshift=-0.1em]mtinput.west);
    \draw [->,thick,ublue] ([xshift=0.1em]mtinput.east) -- ([xshift=-0.2em]smt.west);
    \draw [->,thick,ublue] ([xshift=0.2em]smt.east) -- ([xshift=-0.1em]mtoutput.west);
    }
    \end{tikzpicture}
\item \alert{词法分析}通常是指将输入的符号序列转化为单词序列的过程，这里我们称之为\alert{分词}\\
Canyouseemywords? $\to$ Can you see my words ?
\item<2-> 几乎所有语言的句子都需要经过上述切分才能变成机器翻译系统的输入
    \begin{itemize}
    \item 比如，中文、日文中单词间没有空格
    \item 英文也需要上述切分，主要是处理标点（比如句号）和周围单词的粘连
    \item 过程可能非常复杂，如进行复杂的词汇形态学分析
    \end{itemize}

\end{itemize}

\visible<3->{
\begin{tikzpicture}
\node [draw,thick,red] (note) at (0,0) {\alert{\textbf{统计机器翻译系统的开发依赖性能优良的分词系统！}}};
\end{tikzpicture}
}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 基于概念的定义
\begin{frame}{中文分词任务定义}

\textbf{中文分词}就是把中文句子按词切割开

\begin{spacing}{0.9}
\begin{itemize}
\item 小学生都能很容易地完成 - 我们从小的语言学习就是以词为单位的
\item 什么是"词"或"单词"？\\
\vspace{0.5em}
\begin{beamerboxesrounded}[upper=uppercolblue,lower=lowercolblue,shadow=true]{"词"的定义}
\begin{spacing}{0.6}
词是最小的能够独立运用的语言单位。
\begin{flushright}
--- \textit{百度百科}
\end{flushright}
单词（word），含有语义内容或语用内容，且能被单独念出来的最小单位。
\begin{flushright}
--- \textit{维基百科}
\end{flushright}
单辞亦作"单词"，谓极简短的言词。
\begin{flushright}
--- \textit{辞海在线}
\end{flushright}
\vspace{-1em}
\end{spacing}
\end{beamerboxesrounded}

\item<2-> \alert{问题来了！！}以上这种定义计算机是无法理解的，需要其它的方式来让计算机能够进行中文分词

\end{itemize}
\end{spacing}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 基于词典的分词方法
\begin{frame}{基于词典的分词方法}

现在给计算机一本\alert{词典}（可读），里面定义了所有的单词
\begin{itemize}
\item 只需扫描输入句子，查询每个词串是否出现在词典中

\begin{tikzpicture}

\begin{scope}
\visible<2->{
{\small
\node [anchor=north west] (entry1) at (0,0) {\textbf{1:} 很};
\node [anchor=north west] (entry2) at ([yshift=0.1em]entry1.south west) {\textbf{2:} 高};
\node [anchor=north west] (entry3) at ([yshift=0.1em]entry2.south west) {\textbf{3:} 现在};
\node [anchor=north west] (entry4) at ([yshift=0.1em]entry3.south west) {\textbf{4:} 物价};
\node [anchor=north west] (entry5) at ([yshift=0.1em]entry4.south west) {\textbf{5:} 确实};
\node [anchor=north west] (entry6) at ([yshift=0.1em]entry5.south west) {\textbf{6:} 实现};
\node [anchor=south west] (dictionarylabel) at (entry1.north west) {{\color{ublue} 分词词典}};
}
}

\begin{pgfonlayer}{background}
\visible<2->{
\node[rectangle,draw=ublue, inner sep=0.2em] [fit = (entry1) (entry2) (entry3) (entry4) (entry5) (entry6) (dictionarylabel)] {};
}
\end{pgfonlayer}

\end{scope}

\visible<2->{
\begin{scope}[xshift=1.2in,yshift=1em]
\node [anchor=west] (c1) at (0,0) {确};
\node [anchor=west] (c2) at ([xshift=0em]c1.east) {实};
\node [anchor=west] (c3) at ([xshift=0em]c2.east) {现};
\node [anchor=west] (c4) at ([xshift=0em]c3.east) {在};
\node [anchor=west] (c5) at ([xshift=0em]c4.east) {物};
\node [anchor=west] (c6) at ([xshift=0em]c5.east) {价};
\node [anchor=west] (c7) at ([xshift=0em]c6.east) {很};
\node [anchor=west] (c8) at ([xshift=0em]c7.east) {高};
\end{scope}
}


\visible<3,6>{
\node [anchor=west,thick,draw,minimum width=3.4em,minimum height=1.5em] (w1) at (c3.west){};
\draw [->,thick] (entry3.30) ..controls +(70:1) and +(south:1.5).. ([xshift=0.3em]w1.south) node [pos=0.5, above] {\alert{\footnotesize{命中}}};
}

\visible<4>{
\node [anchor=west,thick,draw,minimum width=3.4em,minimum height=1.5em] (w2) at (c5.west){};
\draw [->,thick] ([yshift=-0.3em]entry4.30) ..controls +(70:1) and +(south:2).. (w2.south) node [pos=0.5, above] {\alert{\footnotesize{命中}}};
}

\visible<6>{
\node [anchor=west,very thick,draw,dotted,minimum width=3.4em,minimum height=1.9em,red] (w3) at (c2.west){};
\draw [->,very thick,dotted,red] ([yshift=-0.2em]entry6.30) ..controls +(60:2) and +(south:3).. ([xshift=-0.6em]w3.south) node [pos=0.5, below] {\alert{\footnotesize{命中}}};
}

\begin{scope}[xshift=1.2in,yshift=-4em]
\visible<11->{
\node [anchor=west] (bc1) at (0,0) {确};
\node [anchor=west] (bc2) at ([xshift=0em]bc1.east) {实};
}
\visible<14->{
\node [anchor=west] (bc3) at ([xshift=0em]bc2.east) {现};
\node [anchor=west] (bc4) at ([xshift=0em]bc3.east) {在};
}
\visible<17->{
\node [anchor=west] (bc5) at ([xshift=0em]bc4.east) {物};
\node [anchor=west] (bc6) at ([xshift=0em]bc5.east) {价};
}
\visible<19->{
\node [anchor=west] (bc7) at ([xshift=0em]bc6.east) {很};
}
\visible<20->{
\node [anchor=west] (bc8) at ([xshift=0em]bc7.east) {高};
}
\visible<11->{
\draw [-,very thick] ([xshift=-0.3em,yshift=0.1em]bc2.south east) -- ([xshift=0.3em,yshift=-0.1em]bc3.north west);
}
\visible<14->{
\draw [-,very thick] ([xshift=-0.3em,yshift=0.1em]bc4.south east) -- ([xshift=0.3em,yshift=-0.1em]bc5.north west);
}
\visible<17->{
\draw [-,very thick] ([xshift=-0.3em,yshift=0.1em]bc6.south east) -- ([xshift=0.3em,yshift=-0.1em]bc7.north west);
}
\visible<19->{
\draw [-,very thick] ([xshift=-0.3em,yshift=0.1em]bc7.south east) -- ([xshift=0.3em,yshift=-0.1em]bc8.north west);
}
\end{scope}

\visible<8->{
\draw [<-,thick] ([yshift=-0.2em]c1.north west) -- ([yshift=0.2em]c1.north west);
\node [anchor=south] (b1) at ([yshift=0.0em]c1.north west) {\scriptsize{起始}};
}

\visible<9>{
\node [anchor=west,thick,draw,ublue,minimum width=1.6em,minimum height=1.3em] (w11) at ([xshift=0.1em]c1.west){};
\node [anchor=north] (l11) at ([yshift=0.2em]w11.south) {{\color{ublue} \footnotesize{无命中}}};
}

\visible<10>{
\node [anchor=west,thick,draw,red,minimum width=3.2em,minimum height=1.3em] (w12) at ([xshift=0.1em]c1.west){};
\node [anchor=north] (l12) at ([yshift=0.2em]w12.south) {{\color{red} \footnotesize{命中:5}}};
}

\visible<11->{
\draw [<-,thick] ([yshift=-0.2em]c3.north west) -- ([yshift=0.2em]c3.north west);
\node [anchor=south] (b2) at ([yshift=0.0em]c3.north west) {\scriptsize{起始}};
}

\visible<12>{
\node [anchor=west,thick,draw,ublue,minimum width=1.6em,minimum height=1.3em] (w13) at ([xshift=0.1em]c3.west){};
\node [anchor=north] (l13) at ([yshift=0.2em]w13.south) {{\color{ublue} \footnotesize{无命中}}};
}

\visible<13>{
\node [anchor=west,thick,draw,red,minimum width=3.2em,minimum height=1.3em] (w14) at ([xshift=0.1em]c3.west){};
\node [anchor=north] (l14) at ([yshift=0.2em]w14.south) {{\color{red} \footnotesize{命中:3}}};
}

\visible<14->{
\draw [<-,thick] ([yshift=-0.2em]c5.north west) -- ([yshift=0.2em]c5.north west);
\node [anchor=south] (b3) at ([yshift=0.0em]c5.north west) {\scriptsize{起始}};
}

\visible<15>{
\node [anchor=west,thick,draw,ublue,minimum width=1.6em,minimum height=1.3em] (w15) at ([xshift=0.1em]c5.west){};
\node [anchor=north] (l15) at ([yshift=0.2em]w15.south) {{\color{ublue} \footnotesize{无命中}}};
}

\visible<16>{
\node [anchor=west,thick,draw,red,minimum width=3.2em,minimum height=1.3em] (w16) at ([xshift=0.1em]c5.west){};
\node [anchor=north] (l16) at ([yshift=0.2em]w16.south) {{\color{red} \footnotesize{命中:4}}};
}

\visible<17->{
\draw [<-,thick] ([yshift=-0.2em]c7.north west) -- ([yshift=0.2em]c7.north west);
\node [anchor=south] (b4) at ([yshift=0.0em]c7.north west) {\scriptsize{起始}};
}

\visible<18>{
\node [anchor=west,thick,draw,red,minimum width=1.6em,minimum height=1.3em] (w17) at ([xshift=0.1em]c7.west){};
\node [anchor=north] (l17) at ([yshift=0.2em]w17.south) {{\color{red} \footnotesize{命中:1}}};
}

\visible<19->{
\draw [<-,thick] ([yshift=-0.2em]c8.north west) -- ([yshift=0.2em]c8.north west);
\node [anchor=south] (b5) at ([yshift=0.0em]c8.north west) {\scriptsize{起始}};
}

\visible<20>{
\node [anchor=west,thick,draw,red,minimum width=1.6em,minimum height=1.3em] (w18) at ([xshift=0.1em]c8.west){};
\node [anchor=north] (l18) at ([yshift=0.2em]w18.south) {{\color{red} \footnotesize{命中:2}}};
}

\end{tikzpicture}

\vspace{0.5em}

\item<5-> 但是基于词典的方法很"硬"，要面对很多歧义
    \begin{itemize}
    \item 常见问题：合法的单词之间有重叠 - 交叉型歧义
    \item<7-> 解决方案：自左向右扫描 + 最大匹配
    \end{itemize}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
\subsection{统计思想}

%%%------------------------------------------------------------------------------------------------------------
%%% 基于统计的方法
\begin{frame}{基于统计的方法}
\begin{itemize}
\item 基于词典的方法是典型的基于规则的方法
    \begin{itemize}
    \item 词典需要人工给定，很多时候词典的覆盖度有限
    \item 出现歧义的地方需要人工定义消除歧义的规则
    \end{itemize}
\item<2-> 另外一种思路是利用"数据"来完成"定义"，让计算机直接从数据中学习知识
    \begin{itemize}
    \item 也就是我们常说的\alert{数据驱动}的方法
    \item 这个过程也是一个典型的\alert{统计学习}的过程
    \end{itemize}
\item<3-> 何为数据驱动？何为统计学习？在分词任务中：
    \begin{itemize}
    \item \textbf{(有标注)数据}：经过人工分词好的句子
    \item<4-> \textbf{统计学习}：从数据中学习一种对分词现象的统计描述，即概率函数P($\cdot$)
    \end{itemize}
\end{itemize}

\vspace{-0.5em}

\begin{tikzpicture}

{\scriptsize
\visible<3->{
\node [anchor=north west] (entry1) at (0,0) {\textbf{1:} 这 / 是 / 数据};
\node [anchor=north west] (entry2) at ([yshift=0.1em]entry1.south west) {\textbf{2:} 现在 / 已经 / 实现};
\node [anchor=north west] (entry3) at ([yshift=0.1em]entry2.south west) {\textbf{3:} 确实 / 有 / 很 / 多};
\node [anchor=north west] (entry4) at ([yshift=0.1em]entry3.south west) {...};
\node [anchor=south west] (corpuslabel) at (entry1.north west) {{\color{ublue} \textbf{学习用数据}}};
}

\begin{pgfonlayer}{background}
\visible<3->{
\node[rectangle,draw=ublue,thick,inner sep=0.2em,fill=white,drop shadow] [fit = (entry1) (entry2) (entry3) (entry4) (corpuslabel)] (corpus) {};
}
\end{pgfonlayer}

}

\visible<4->{
\node [anchor=west,ugreen] (P) at ([xshift=4em,yshift=-0.8em]corpus.east){\large{P($\cdot$)}};
\node [anchor=south] (modellabel) at (P.north) {{\color{ublue} {\scriptsize \textbf{统计模型}}}};
}

\begin{pgfonlayer}{background}
\visible<4->{
\node[rectangle,draw=ublue,thick,inner sep=0.2em,fill=white,drop shadow] [fit = (P) (modellabel)] (model) {};
}
\end{pgfonlayer}

\visible<4->{
\draw [->,very thick,ublue] ([xshift=0.2em]corpus.east) -- ([xshift=3.2em]corpus.east)  node [pos=0.5, above] {\alert{\scriptsize{统计学习}}};
}

\visible<6->{
\draw [->,very thick,ublue] ([xshift=0.2em]model.east) -- ([xshift=3.2em]model.east)  node [pos=0.5, above] {\alert{\scriptsize{穷举\&计算}}};
}

{\scriptsize
\visible<5->{
\node [anchor=north west] (sentlabel) at ([xshift=5.5em,yshift=2em]model.north east) {\alert{新的句子}};
\node [anchor=north west] (sent) at (sentlabel.south west) {\textbf{确实现在数据很多}};
}
\visible<6->{
\node [anchor=north west] (seg1) at ([xshift=0em]sent.south west) {确/实现/在/数/据很/多};
\node [anchor=north west] (seg2) at (seg1.south west) {确实/现在/数据/很/多};
\node [anchor=north west] (seg3) at (seg2.south west) {确实/现在/数/据/很/多};
}
\visible<7->{
\node [anchor=north west] (seg4) at ([yshift=0.5em]seg3.south west) {...};
\node [anchor=east,ugreen] (p1seg1) at ([xshift=0.5em]seg1.west) {P(};
\node [anchor=west,ugreen] (p2seg1) at ([xshift=-0.5em]seg1.east) {)=.1};
\node [anchor=east,ugreen] (p1seg2) at ([xshift=0.5em]seg2.west) {P(};
\node [anchor=west,ugreen] (p2seg2) at ([xshift=-0.5em]seg2.east) {)=.6};
\node [anchor=east,ugreen] (p1seg3) at ([xshift=0.5em]seg3.west) {P(};
\node [anchor=west,ugreen] (p2seg3) at ([xshift=-0.5em]seg3.east) {)=.2};
}

\visible<8->{
\node [anchor=east,draw,dashed,red,thick,minimum width=13em,minimum height=1.5em] (final) at (p2seg2.east) {};
\node [anchor=west,red] (finallabel) at ([xshift=2em]sentlabel.east) {输出概率最大};
\node [anchor=north east,red] (finallabel2) at ([yshift=0.5em]finallabel.south east) {的结果};
\draw [->,thick,red] ([xshift=-1.5em]final.north east) ..controls +(north:0.5) and +(south:0.5).. (finallabel2.south);
}

}

\end{tikzpicture}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 定义P()
\begin{frame}{P($\cdot$)是什么？}
\label{probdef}

\begin{itemize}
\item P($\cdot$)表示一个随机事件的可能性，即事件发生的\alert{概率}
    \begin{itemize}
    \item P(太阳从东方升起)："太阳从东方升起"这件事的可能性
    \item P($A=B$)："A=B"这件事的可能性
    \end{itemize}
\item<2-> 如果把$A$看做一个(离散)变量，$a$看做变量$A$的一个取值
    \begin{itemize}
    \item P($A$)被称作$A$的概率函数
    \item P($A=a$)被称作$A=a$的概率值，简记为P($a$)\\
    \item \textbf{非负性}：$\forall x$, P($x) \ge 0$；归一性：$\sum_{x} \textrm{P}(x)=1$
    \item \textbf{联合概率}：两个事件A和B同时出现的概率，记为P($AB$)
    \item \textbf{条件概率}：事件A出现的前提下和B出现的概率，记为P($B|A$)
    \end{itemize}
\item<3-> 所谓\alert{统计建模}是用概率来描述要解决的问题，就这么简单!!!\\
    \begin{center}
    \includegraphics[scale=0.3]{./Figures/stat.jpg}
    \end{center}
\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% story: 骰子游戏
\begin{frame}{看一个实例：扯远一点儿 - 骰子游戏}
\begin{itemize}
\item<1-> 掷一个骰($\textrm{t}\acute{\textrm{o}}\textrm{u}$)子（1-6），你押一个数字，压中算你赢 \\
    \vspace{0.5em}
    \begin{tikzpicture}
    \node[anchor=west,draw,very thick,minimum size=20pt] (s1) at (0,0) {\Large{\textbf{1}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s2) at ([xshift=0.2cm]s1.east) {\Large{\textbf{2}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s3) at ([xshift=0.2cm]s2.east) {\Large{\textbf{3}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s4) at ([xshift=0.2cm]s3.east) {\Large{\textbf{4}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s5) at ([xshift=0.2cm]s4.east) {\Large{\textbf{5}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s6) at ([xshift=0.2cm]s5.east) {\Large{\textbf{6}}};
    \end{tikzpicture}

    \visible<2->{
    我说：
    \begin{itemize}
    \item 很难赢，六个面，你只能压一个面
    \item 也能赢，除非你的运气极好
    \end{itemize}
    }

\vspace{0.5em}
\item<3-> 不管了，随便压一个数字，比如：1。掷30次，结果如何 \\
    \vspace{0.5em}
    \begin{tikzpicture}

    \visible<4->{
    \begin{scope}
    \node[anchor=west,draw,very thick,minimum size=20pt] (s1) at (0,0) {\Large{\textbf{2}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s2) at ([xshift=0.2cm]s1.east) {\Large{\textbf{3}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s3) at ([xshift=0.2cm]s2.east) {\Large{\textbf{\only<4>{1}\only<5->{\alert{1}}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s4) at ([xshift=0.2cm]s3.east) {\Large{\textbf{4}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s5) at ([xshift=0.2cm]s4.east) {\Large{\textbf{4}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s6) at ([xshift=0.2cm]s5.east) {\Large{\textbf{\only<4>{1}\only<5->{\alert{1}}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s7) at ([xshift=0.2cm]s6.east) {\Large{\textbf{5}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s8) at ([xshift=0.2cm]s7.east) {\Large{\textbf{\only<4>{1}\only<5->{\alert{1}}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s9) at ([xshift=0.2cm]s8.east) {\Large{\textbf{4}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s10) at ([xshift=0.2cm]s9.east) {\Large{\textbf{4}}};
    \end{scope}

    \begin{scope}[yshift=-1cm]
    \node[anchor=west,draw,very thick,minimum size=20pt] (s1) at (0,0) {\Large{\textbf{5}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s2) at ([xshift=0.2cm]s1.east) {\Large{\textbf{6}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s3) at ([xshift=0.2cm]s2.east) {\Large{\textbf{4}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s4) at ([xshift=0.2cm]s3.east) {\Large{\textbf{4}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s5) at ([xshift=0.2cm]s4.east) {\Large{\textbf{3}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s6) at ([xshift=0.2cm]s5.east) {\Large{\textbf{2}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s7) at ([xshift=0.2cm]s6.east) {\Large{\textbf{\only<4>{1}\only<5->{\alert{1}}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s8) at ([xshift=0.2cm]s7.east) {\Large{\textbf{4}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s9) at ([xshift=0.2cm]s8.east) {\Large{\textbf{5}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s10) at ([xshift=0.2cm]s9.east) {\Large{\textbf{\only<4>{1}\only<5->{\alert{1}}}}};
    \end{scope}

    \begin{scope}[yshift=-2cm]
    \node[anchor=west,draw,very thick,minimum size=20pt] (s1) at (0,0) {\Large{\textbf{4}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s2) at ([xshift=0.2cm]s1.east) {\Large{\textbf{2}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s3) at ([xshift=0.2cm]s2.east) {\Large{\textbf{2}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s4) at ([xshift=0.2cm]s3.east) {\Large{\textbf{3}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s5) at ([xshift=0.2cm]s4.east) {\Large{\textbf{4}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s6) at ([xshift=0.2cm]s5.east) {\Large{\textbf{\only<4>{1}\only<5->{\alert{1}}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s7) at ([xshift=0.2cm]s6.east) {\Large{\textbf{5}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s8) at ([xshift=0.2cm]s7.east) {\Large{\textbf{\only<4>{1}\only<5->{\alert{1}}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s9) at ([xshift=0.2cm]s8.east) {\Large{\textbf{3}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s10) at ([xshift=0.2cm]s9.east) {\Large{\textbf{4}}};
    \end{scope}
    }

    \end{tikzpicture}\\
    \vspace{0.5em}
    \visible<5->{命中\alert{7/30} $>$ 1/6 还不错}

\end{itemize}
\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% story: 骰子游戏 - 建模
\begin{frame}{骰子游戏 - 建模}
\begin{itemize}
\item 似乎你的胜利只能来源于运气
\item no! no! no! "随便选一个数字"本身就是一个概率\alert{模型}，它对骰子的六个面做了均匀分布的假设\\
\vspace{-1.0em}
\begin{displaymath}
\textrm{P}("1") = \textrm{P}("2") = ... = \textrm{P}("5") = \textrm{P}("6") = 1/6
\end{displaymath}
\item<2-> 看出问题来了，我们可以用一种更加"聪明"的方式来定义一个新\alert{模型}，定义骰子的每个面都以一定的概率出现（不一定是均匀分布）\\
\vspace{-2.0em}
\visible<3->{
\begin{eqnarray}
\textrm{P}("1") & = & \theta_{1} \nonumber \\
\textrm{P}("2") & = & \theta_{2} \nonumber \\
\textrm{P}("3") & = & \theta_{3} \nonumber \\
\textrm{P}("4") & = & \theta_{4} \nonumber \\
\textrm{P}("5") & = & \theta_{5} \nonumber \\
\textrm{P}("6") & = & 1 - \sum\nolimits_{1 \leq i \leq 5} \theta_{i} \ \ \ \vartriangleleft \textrm{归一性}\nonumber
\end{eqnarray}\\
    \vspace{-1.0em}
    \visible<4->{问题：如何获得$\theta_{i}$的值？}
    }
\end{itemize}
\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% story: 骰子游戏 - 模型学习
\begin{frame}{骰子游戏 - 模型学习}
\begin{itemize}
\item<1-> 我们可以从大量的实例中学习模型参数。比如，先实验性的掷很多次($X$次)，发现"1"出现$X_1$次、"2"出现$X_2$次...
\item<2-> 假设$i$服从多项式分布，那么各种概率的极大似然估计为 \\
\vspace{-0.5em}
\begin{displaymath}
\textrm{P}("i") = \frac{X_i}{X}
\end{displaymath}\\
    \alert{注意}：$X$足够大的话，$\frac{X_i}{X}$可以无限逼近$\textrm{P}("i")$的真实值\\
    何为多项式分布？何为极大似然估计??? - 自己翻翻书
\item<3-> 重新来一次，我们在正式开始前先掷30次 \\
    \vspace{0.3em}

    \begin{tikzpicture}

    \begin{scope}
    \node[anchor=west,draw,very thick,minimum size=20pt] (s1) at (0,0) {\Large{\textbf{{\color{ublue} 3}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s2) at ([xshift=0.2cm]s1.east) {\Large{\textbf{{\color{ugreen} 4}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s3) at ([xshift=0.2cm]s2.east) {\Large{\textbf{{\color{red} 2}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s4) at ([xshift=0.2cm]s3.east) {\Large{\textbf{{\color{ublue} 3}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s5) at ([xshift=0.2cm]s4.east) {\Large{\textbf{{\color{ugreen} 4}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s6) at ([xshift=0.2cm]s5.east) {\Large{\textbf{{\color{purple} 5}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s7) at ([xshift=0.2cm]s6.east) {\Large{\textbf{1}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s8) at ([xshift=0.2cm]s7.east) {\Large{\textbf{{\color{ugreen} 4}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s9) at ([xshift=0.2cm]s8.east) {\Large{\textbf{{\color{ugreen} 4}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s10) at ([xshift=0.2cm]s9.east) {\Large{\textbf{{\color{ublue} 3}}}};
    \end{scope}

    \begin{scope}[yshift=-1cm]
    \node[anchor=west,draw,very thick,minimum size=20pt] (s1) at (0,0) {\Large{\textbf{{\color{red} 2}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s2) at ([xshift=0.2cm]s1.east) {\Large{\textbf{1}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s3) at ([xshift=0.2cm]s2.east) {\Large{\textbf{{\color{ugreen} 4}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s4) at ([xshift=0.2cm]s3.east) {\Large{\textbf{{\color{purple} 5}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s5) at ([xshift=0.2cm]s4.east) {\Large{\textbf{{\color{ugreen} 4}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s6) at ([xshift=0.2cm]s5.east) {\Large{\textbf{{\color{ugreen} 4}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s7) at ([xshift=0.2cm]s6.east) {\Large{\textbf{{\color{ugreen} 4}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s8) at ([xshift=0.2cm]s7.east) {\Large{\textbf{{\color{ublue} 3}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s9) at ([xshift=0.2cm]s8.east) {\Large{\textbf{1}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s10) at ([xshift=0.2cm]s9.east) {\Large{\textbf{{\color{ugreen} 4}}}};
    \end{scope}

    \begin{scope}[yshift=-2cm]
    \node[anchor=west,draw,very thick,minimum size=20pt] (s1) at (0,0) {\Large{\textbf{{\color{ugreen} 4}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s2) at ([xshift=0.2cm]s1.east) {\Large{\textbf{{\color{ublue} 3}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s3) at ([xshift=0.2cm]s2.east) {\Large{\textbf{{\color{red} 2}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s4) at ([xshift=0.2cm]s3.east) {\Large{\textbf{{\color{orange} 6}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s5) at ([xshift=0.2cm]s4.east) {\Large{\textbf{1}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s6) at ([xshift=0.2cm]s5.east) {\Large{\textbf{{\color{red} 2}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s7) at ([xshift=0.2cm]s6.east) {\Large{\textbf{{\color{ublue} 3}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s8) at ([xshift=0.2cm]s7.east) {\Large{\textbf{{\color{ugreen} 4}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s9) at ([xshift=0.2cm]s8.east) {\Large{\textbf{{\color{ugreen} 4}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s10) at ([xshift=0.2cm]s9.east) {\Large{\textbf{1}}};
    \end{scope}

    \end{tikzpicture}

\end{itemize}
\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% story: 骰子游戏 - 测试
\begin{frame}{骰子游戏：在新一轮游戏上实践}
\vspace{-0.6em}
\begin{itemize}
\item 我们得到一个有倾向性的模型(a model with a bias)

\begin{tikzpicture}[scale=0.6]
\begin{scope}
{\footnotesize
\foreach \i in {1,...,5}{
    \node [draw,thick,minimum size=10pt] at (\i,0) {1};
}
}
\node [anchor=west] at (31em,0) {$\textrm{P}("1") = 5/30$};
\end{scope}

\begin{scope}[yshift=-2.5em]
{\footnotesize
\foreach \i in {1,...,4}{
    \node [draw,thick,minimum size=10pt] at (\i,0) {{\color{red} 2}};
}
}
\node [anchor=west] at (31em,0) {$\textrm{P}("2") = 4/30$};
\end{scope}

\begin{scope}[yshift=-5.0em]
{\footnotesize
\foreach \i in {1,...,6}{
    \node [draw,thick,minimum size=10pt] at (\i,0) {{\color{ublue} 3}};
}
}
\node [anchor=west] at (31em,0) {$\textrm{P}("3") = 6/30$};
\end{scope}

\begin{scope}[yshift=-7.5em]
{\footnotesize
\foreach \i in {1,...,12}{
    \node [draw,thick,minimum size=10pt] at (\i,0) {{\color{ugreen} 4}};
}
}
\node [anchor=west] at (31em,0) {$\textrm{P}("4") = 12/30$};
\end{scope}

\begin{scope}[yshift=-10.0em]
{\footnotesize
\foreach \i in {1,...,2}{
    \node [draw,thick,minimum size=10pt] at (\i,0) {{\color{purple} 5}};
}
}
\node [anchor=west] at (31em,0) {$\textrm{P}("5") = 2/30$};
\end{scope}

\begin{scope}[yshift=-12.5em]
{\footnotesize
\foreach \i in {1,...,1}{
    \node [draw,thick,minimum size=10pt] at (\i,0) {{\color{orange} 6}};
}
}
\node [anchor=west] at (31em,0) {$\textrm{P}("6") = 1/30$};
\end{scope}

\end{tikzpicture}

\vspace{-0.5em}

\item<2-> 那我们选择一个数字（显然是4），然后开始正式的游戏 \\
    \vspace{0.3em}

    \begin{tikzpicture}

    \visible<3->{
    \begin{scope}
    \node[anchor=west,draw,very thick,minimum size=20pt] (s1) at (0,0) {\Large{\textbf{\only<3>{4}\only<4->{{\color{ugreen} 4}}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s2) at ([xshift=0.2cm]s1.east) {\Large{\textbf{\only<3>{4}\only<4->{{\color{ugreen} 4}}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s3) at ([xshift=0.2cm]s2.east) {\Large{\textbf{3}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s4) at ([xshift=0.2cm]s3.east) {\Large{\textbf{1}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s5) at ([xshift=0.2cm]s4.east) {\Large{\textbf{\only<3>{4}\only<4->{{\color{ugreen} 4}}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s6) at ([xshift=0.2cm]s5.east) {\Large{\textbf{5}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s7) at ([xshift=0.2cm]s6.east) {\Large{\textbf{1}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s8) at ([xshift=0.2cm]s7.east) {\Large{\textbf{3}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s9) at ([xshift=0.2cm]s8.east) {\Large{\textbf{2}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s10) at ([xshift=0.2cm]s9.east) {\Large{\textbf{2}}};
    \end{scope}

    \begin{scope}[yshift=-1cm]
    \node[anchor=west,draw,very thick,minimum size=20pt] (s1) at (0,0) {\Large{\textbf{\only<3>{4}\only<4->{{\color{ugreen} 4}}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s2) at ([xshift=0.2cm]s1.east) {\Large{\textbf{6}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s3) at ([xshift=0.2cm]s2.east) {\Large{\textbf{\only<3>{4}\only<4->{{\color{ugreen} 4}}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s4) at ([xshift=0.2cm]s3.east) {\Large{\textbf{\only<3>{4}\only<4->{{\color{ugreen} 4}}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s5) at ([xshift=0.2cm]s4.east) {\Large{\textbf{2}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s6) at ([xshift=0.2cm]s5.east) {\Large{\textbf{2}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s7) at ([xshift=0.2cm]s6.east) {\Large{\textbf{3}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s8) at ([xshift=0.2cm]s7.east) {\Large{\textbf{\only<3>{4}\only<4->{{\color{ugreen} 4}}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s9) at ([xshift=0.2cm]s8.east) {\Large{\textbf{1}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s10) at ([xshift=0.2cm]s9.east) {\Large{\textbf{\only<3>{4}\only<4->{{\color{ugreen} 4}}}}};
    \end{scope}

    \begin{scope}[yshift=-2cm]
    \node[anchor=west,draw,very thick,minimum size=20pt] (s1) at (0,0) {\Large{\textbf{6}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s2) at ([xshift=0.2cm]s1.east) {\Large{\textbf{3}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s3) at ([xshift=0.2cm]s2.east) {\Large{\textbf{2}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s4) at ([xshift=0.2cm]s3.east) {\Large{\textbf{\only<3>{4}\only<4->{{\color{ugreen} 4}}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s5) at ([xshift=0.2cm]s4.east) {\Large{\textbf{\only<3>{4}\only<4->{{\color{ugreen} 4}}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s6) at ([xshift=0.2cm]s5.east) {\Large{\textbf{\only<3>{4}\only<4->{{\color{ugreen} 4}}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s7) at ([xshift=0.2cm]s6.east) {\Large{\textbf{1}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s8) at ([xshift=0.2cm]s7.east) {\Large{\textbf{2}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s9) at ([xshift=0.2cm]s8.east) {\Large{\textbf{\only<3>{4}\only<4->{{\color{ugreen} 4}}}}};
    \node[anchor=west,draw,very thick,minimum size=20pt] (s10) at ([xshift=0.2cm]s9.east) {\Large{\textbf{\only<3>{4}\only<4->{{\color{ugreen} 4}}}}};
    \end{scope}
    }

    \end{tikzpicture}\\
    \visible<4->{这次得到的结果是 13/30 - 非常不错!}

\end{itemize}
\end{frame}

%%%------------------------------------------------------------------------------------------------------------
\subsection{统计建模实例：基于全切分的概率分词}

%%%------------------------------------------------------------------------------------------------------------
%%% 骰子游戏 vs. 分词
\begin{frame}{骰子游戏 vs. 分词}
假设我们有已经人工分好词的句子（称之为语料或数据），其中每个单词的出现就好比投掷一个巨大骰子
\begin{itemize}
\item 骰子有很多个面，每个面代表一个单词
\item 骰子是不均匀的，有些面会出现比较多次
\end{itemize}

\vspace{0.3em}
\begin{tikzpicture}

\visible<2->{
\begin{scope}
\node[anchor=west,draw,very thick,minimum size=25pt] (s1) at (0,0) {\only<2>{88}\only<3->{这}};
\node[anchor=west,draw,very thick,minimum size=25pt] (s2) at ([xshift=0.2cm]s1.east) {\only<2>{87}\only<3->{是}};
\node[anchor=west,draw,very thick,minimum size=25pt] (s3) at ([xshift=0.2cm]s2.east) {\only<2>{45}\only<3->{一}};
\node[anchor=west,draw,very thick,minimum size=25pt] (s4) at ([xshift=0.2cm]s3.east) {\only<2>{47}\only<3->{种}};
\node[anchor=west,draw,very thick,minimum size=25pt, inner sep=0] (s5) at ([xshift=0.2cm]s4.east) {\only<2>{100}\only<3->{\small{数据}}};
\node[anchor=west,draw,very thick,minimum size=25pt] (s6) at ([xshift=0.2cm]s5.east) {\only<2>{15}\only<3->{。}};
\visible<6->{
\node[anchor=west] (s7) at ([xshift=0.2cm]s6.east) {...};
}
\end{scope}

\begin{scope}[yshift=-1cm]
\node[anchor=west,draw,very thick,minimum size=25pt, inner sep=0] (s1) at (0,0) {\only<2>{5}\only<3->{现在}};
\node[anchor=west,draw,very thick,minimum size=25pt, inner sep=0] (s2) at ([xshift=0.2cm]s1.east) {\only<2>{230}\only<3->{已经}};
\node[anchor=west,draw,very thick,minimum size=25pt] (s3) at ([xshift=0.2cm]s2.east) {\only<2>{7}\only<3->{有}};
\node[anchor=west,draw,very thick,minimum size=25pt, inner sep=0] (s4) at ([xshift=0.2cm]s3.east) {\only<2>{234}\only<3->{不少}};
\node[anchor=west,draw,very thick,minimum size=25pt, inner sep=0] (s5) at ([xshift=0.2cm]s4.east) {\only<2>{500}\only<3->{\small{可}}};
\node[anchor=west,draw,very thick,minimum size=25pt] (s6) at ([xshift=0.2cm]s5.east) {\only<2>{39}\only<3->{用}};
\node[anchor=west,draw,very thick,minimum size=25pt, inner sep=0] (s7) at ([xshift=0.2cm]s6.east) {\only<2>{100}\only<3->{数据}};
\node[anchor=west,draw,very thick,minimum size=25pt] (s8) at ([xshift=0.2cm]s7.east) {\only<2>{15}\only<3->{。}};
\visible<6->{
\node[anchor=west] (s9) at ([xshift=0.2cm]s8.east) {...};
}
\end{scope}

\begin{scope}[yshift=-2cm]
\node[anchor=west,draw,very thick,minimum size=25pt, inner sep=0] (s1) at (0,0) {\only<2>{975}\only<3->{确实}};
\node[anchor=west,draw,very thick,minimum size=25pt] (s2) at ([xshift=0.2cm]s1.east) {\only<2>{7}\only<3->{有}};
\node[anchor=west,draw,very thick,minimum size=25pt, inner sep=0] (s3) at ([xshift=0.2cm]s2.east) {\only<2>{234}\only<3->{很}};
\node[anchor=west,draw,very thick,minimum size=25pt, inner sep=0] (s4) at ([xshift=0.2cm]s3.east) {\only<2>{294}\only<3->{多}};
\node[anchor=west,draw,very thick,minimum size=25pt, inner sep=0] (s5) at ([xshift=0.2cm]s4.east) {\only<2>{15}\only<3->{疑问}};
\node[anchor=west,draw,very thick,minimum size=25pt] (s6) at ([xshift=0.2cm]s5.east) {\only<2>{15}\only<3->{。}};
\visible<6->{
\node[anchor=west] (s7) at ([xshift=0.2cm]s6.east) {...};
}
\end{scope}

}

\begin{scope}[yshift=-2.8cm,xshift=-0.5em]
\visible<4->{
\node [anchor=west] (label1) at (0,0) {总词数：$6 + 8 + 5 = 20$};
}
\visible<5->{
\node [anchor=north west] (p1) at (label1.south west) {$\textrm{P}('\textrm{很}')=1/20=0.05$};
\node [anchor=north west] (p2) at (p1.south west) {$\textrm{P}('\textrm{。}')=3/20=0.15$};
\node [anchor=north west] (p3) at (p2.south west) {$\textrm{P}('\textrm{确实}')=1/20=0.05$};
}
\end{scope}

\begin{scope}[yshift=-2.8cm,xshift=6cm]
\visible<6->{
\node [anchor=west] (label1) at (0,0) {更多数据-总词数:100K $\sim$ 1M};
\node [anchor=north west] (p1) at (label1.south west) {$\textrm{P}('\textrm{很}')=0.000010$};
\node [anchor=north west] (p2) at (p1.south west) {$\textrm{P}('\textrm{。}')=0.001812$};
\node [anchor=north west] (p3) at (p2.south west) {$\textrm{P}('\textrm{确实}')=0.000001$};
}
\end{scope}

\end{tikzpicture}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 分词概率
\begin{frame}{真正的分词过程}

\begin{itemize}
\item 通过上述的'学习'，我们得到了每个词出现的概率。而现在的问题是如何计算整句分词结果的概率\\
$\textrm{P}(\textrm{'确实/现在/数据/很/多'})=?$
\item<2-> 这里我们考虑把整句切分的概率转化为词的概率，怎么办？
    \begin{itemize}
    \item \alert{独立性假设}$\textrm{P}(AB)=\textrm{P}(A)\textrm{P}(B)$：每个词都是相互独立的
    \item 设$w_1 w_2 ... w_m$表示一个由单词$w_1$,$w_2$,...,$w_m$组成的切分结果\\
    \vspace{-1.0em}
    \begin{displaymath}
    \textrm{P}(w_1 w_2 ... w_m) = \textrm{P}(w_1) \cdot \textrm{P}(w_2) \cdot ... \cdot \textrm{P}(w_m)
    \end{displaymath}
    \end{itemize}

\vspace{-1.5em}

\begin{eqnarray}
&   & \visible<3->{\textrm{P}(\textrm{'确实/现在/数据/很/多'})} \nonumber \\
& \visible<4->{=} & \visible<4->{\textrm{P}(\textrm{'确实'}) \cdot \textrm{P}(\textrm{'现在'}) \cdot \textrm{P}(\textrm{'数据'}) \cdot \textrm{P}(\textrm{'很'}) \cdot \textrm{P}(\textrm{' 多'})} \nonumber \\
& \visible<5->{=} & \visible<5->{0.000001 \times 0.000022 \times 0.000009 \times 0.000010 \times 0.000078} \nonumber \\
& \visible<5->{=} & \visible<5->{1.5444 \times 10^{-25}} \nonumber
\end{eqnarray}

\end{itemize}

\vspace{-1.0em}

\visible<6->{
\begin{center}
\begin{tikzpicture}
\node [draw,thick,red] (note) at (0,0) {\alert{\textbf{核心思想：通过独立性假设对问题进行'大题小做'}}};
\end{tikzpicture}
\end{center}
}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 分词系统
\begin{frame}{自动分词系统}
\label{wordsegmethod}

\begin{tikzpicture}

{\scriptsize
\node [anchor=north west] (entry1) at (0,0) {\textbf{1:} 这 / 是 / 数据};
\node [anchor=north west] (entry2) at ([yshift=0.1em]entry1.south west) {\textbf{2:} 现在 / 已经 / 实现};
\node [anchor=north west] (entry3) at ([yshift=0.1em]entry2.south west) {\textbf{3:} 确实 / 有 / 很 / 多};
\node [anchor=north west] (entry4) at ([yshift=0.1em]entry3.south west) {...};
\node [anchor=south west] (corpuslabel) at (entry1.north west) {{\color{ublue} \textbf{学习用数据}}};

\begin{pgfonlayer}{background}
\node[rectangle,draw=ublue,thick,inner sep=0.2em,fill=white,drop shadow] [fit = (entry1) (entry2) (entry3) (entry4) (corpuslabel)] (corpus) {};
\end{pgfonlayer}
}

\node [anchor=west,ugreen] (P) at ([xshift=4em,yshift=-0.8em]corpus.east){\large{P($\cdot$)}};
\node [anchor=south] (modellabel) at (P.north) {{\color{ublue} {\scriptsize \textbf{统计模型}}}};

\begin{pgfonlayer}{background}
\node[rectangle,draw=ublue,thick,inner sep=0.2em,fill=white,drop shadow] [fit = (P) (modellabel)] (model) {};
\end{pgfonlayer}

\draw [->,very thick,ublue] ([xshift=0.2em]corpus.east) -- ([xshift=3.2em]corpus.east)  node [pos=0.5, above] {\alert{\scriptsize{统计学习}}};

\draw [->,very thick,ublue] ([xshift=0.2em]model.east) -- ([xshift=3.2em]model.east)  node [pos=0.5, above] {\alert{\scriptsize{穷举\&计算}}};

{\scriptsize
\node [anchor=north west] (sentlabel) at ([xshift=5.5em,yshift=-1em]model.north east) {\alert{自动分词系统}};
\node [anchor=north west] (sent) at (sentlabel.south west) {\textbf{对任意句子进行分词}};
}

\begin{pgfonlayer}{background}
\node[rectangle,draw=ublue,thick,inner sep=0.2em,fill=white,drop shadow] [fit = (sentlabel) (sent)] (segsystem) {};
\end{pgfonlayer}

{\footnotesize
\visible<2->{
\node [anchor=west] (label1) at (0,6em) {实际上，通过学习我们得到了一个分词模型P($\cdot$)，给定任意的};
\node [anchor=north west] (label1part2) at ([yshift=0.5em]label1.south west) {分词结果$W=w_1 w_2...w_n$，都能通过P($W$)=$\textrm{P}(w_1) \cdot \textrm{P}(w_2) \cdot ... \cdot \textrm{P}(w_n)$};
\node [anchor=north west] (label1part3) at ([yshift=0.5em]label1part2.south west) {计算这种分词的概率值};
}

\begin{pgfonlayer}{background}
\visible<2->{
\node[rectangle,fill=blue!10,thick,dotted,inner sep=0.2em] [fit = (label1) (label1part2) (label1part3)] (label1content) {};
}
\end{pgfonlayer}

\visible<2->{
\draw [-,thick,red,dotted] ([yshift=0.3em]modellabel.north) ..controls +(north:0.5) and +(south:0.5).. ([xshift=-3em]label1content.south);
}

}

{\footnotesize
\visible<3->{
\node [anchor=west] (label1) at (0,-6.8em) {\textbf{自动分词系统}：对任意的数据句子$S$，找到最佳的分词结果$W^{*}$输出};
}
\visible<4->{
\node [anchor=north west] (label2) at (label1.south west) {假设输入$S$='确实现在数据很多'};
}
\visible<5->{
\node [anchor=north west,draw,thick,inner sep=2pt] (data11) at (label2.south west) {枚举所有可能的切分};
}
\visible<6->{
\node [anchor=west,draw,thick,inner sep=2pt] (data12) at ([xshift=2em]data11.east) {计算每种切分的概率};
}
\visible<7->{
\node [anchor=west,draw,thick,inner sep=2pt] (data13) at ([xshift=3.5em]data12.east) {选择最佳结果};
}
\visible<6->{
\draw [->,thick] ([xshift=0.1em]data11.east) -- ([xshift=-0.1em]data12.west);
}
\visible<7->{
\draw [->,thick] ([xshift=0.1em]data12.east) -- ([xshift=-0.1em]data13.west);
}

{\scriptsize
\visible<5->{
\node [anchor=north west] (data21) at (data11.south west) {确/实现/在/数/据很/多};
}
\visible<6->{
\node [anchor=north west] (data22) at (data12.south west) {$\textrm{P}(\textrm{'确'}) \cdot \textrm{P}(\textrm{'实现'}) \cdot \textrm{P}(\textrm{'在'}) \cdot \textrm{P}(\textrm{'数'}) \cdot $};
}
\node [anchor=north west,minimum height=1.6em] (data23) at (data13.south west) {};
\node [anchor=north west,minimum height=1.6em] (data31) at ([yshift=0.3em]data21.south west) {};
\visible<6->{
\node [anchor=north west] (data32) at ([yshift=0.3em]data22.south west) {$\textrm{P}(\textrm{'据很'}) \cdot  \textrm{P}(\textrm{'多'}) = 2.13 \times 10^{-45}$};
}
\node [anchor=north west,minimum height=1.6em] (data33) at ([yshift=0.3em]data23.south west) {};

\visible<5->{
\node [anchor=north west] (data41) at (data31.south west) {确实/现在/数据/很多};
}
\visible<6->{
\node [anchor=north west] (data42) at (data32.south west) {$\textrm{P}(\textrm{'确实'}) \cdot \textrm{P}(\textrm{'现在'}) \cdot \textrm{P}(\textrm{'数据'}) \cdot $};
}
\visible<7->{
\node [anchor=north west] (data43) at ([yshift=-0.2em]data33.south west) {\alert{\textbf{输出}}};
\draw [->,red,thick] (data43.west)--([xshift=-1em]data43.west);
}
\visible<5->{
\node [anchor=north west] (data51) at (data41.south west) {...};
}
\visible<6->{
\node [anchor=north west] (data52) at ([yshift=0.3em]data42.south west) {$\textrm{P}(\textrm{'很'}) \cdot  \textrm{P}(\textrm{'多'}) = 1.54 \times 10^{-25}$};
}
\node [anchor=north west] (data53) at ([yshift=0.3em]data43.south west) {};
}
}

\begin{pgfonlayer}{background}
\visible<3->{
\node[rectangle,fill=blue!10,thick,dotted,inner sep=0.1em] [fit = (label1) (data11) (data13) (data51) (data52) (data53)] (segcontent) {};
}
\end{pgfonlayer}

\visible<3->{
\draw [-,thick,red,dotted] (segcontent.north) ..controls +(north:0.7) and +(south:0.7).. (segsystem.south);
}

\end{tikzpicture}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 进一步扩展，基于n-gram LM的方法
\begin{frame}{进一步扩展：基于$n$-gram语言模型的方法}

\begin{itemize}
\item 这种方法也被称作基于1-gram(统计)语言模型的方法\\
      所谓统计语言模型就是计算$\textrm{P}(w_1 w_2 ... w_m)$的概率
\end{itemize}

{\scriptsize
\tabcolsep 5pt
\begin{tabular}{l | l | l l l}
链式法则 & 1-gram & 2-gram & ... & $n$-gram \\
$\textrm{P}(w_1 w_2 ... w_m)=$ & $\textrm{P}(w_1 w_2 ... w_m)=$ & $\textrm{P}(w_1 w_2 ... w_m)=$ & ... & $\textrm{P}(w_1 w_2 ... w_m)=$ \\
$\textrm{P}(w_1) \times$ & $\textrm{P}(w_1) \times$ & $\textrm{P}(w_1) \times$ & ... & $\textrm{P}(w_1) \times$ \\
$\textrm{P}(w_2|w_1) \times$ & $\textrm{P}(w_2) \times$ & $\textrm{P}(w_2|w_1) \times$ & ... & $\textrm{P}(w_2|w_1) \times$ \\
$\textrm{P}(w_3|w_1 w_2) \times$ & $\textrm{P}(w_3) \times$ & $\textrm{P}(w_3|w_2) \times$ & ... & $\textrm{P}(w_3|w_1 w_2) \times$ \\
$\textrm{P}(w_4|w_1 w_2 w_3) \times$ & $\textrm{P}(w_4) \times$ & $\textrm{P}(w_4|w_3) \times$ & ... & $\textrm{P}(w_4|w_1 w_2 w_3) \times$ \\
... & ... & ... & ... & ... \\
$\textrm{P}(w_m|w_1...w_{m-1})$ & $\textrm{P}(w_m)$ & $\textrm{P}(w_m|w_{m-1})$ & ... & $\textrm{P}(w_m|w_{m-n+1} ... w_{m-1})$ \\
\end{tabular}
}

\begin{itemize}
\item<2-> \textbf{$n$-gram语言模型}的核心思想是当前词($w_m$)出现的概率只依赖于前$n-1$个词($w_{m-n+1} ... w_{m-1}$)

\vspace{-2em}

\begin{eqnarray}
&   & \textrm{P}_{2\textrm{-gram}}(\textrm{'确实/现在/数据/很/多'}) \nonumber \\
& = & \textrm{P}(\textrm{'确实'}) \times \textrm{P}(\textrm{'现在'$|$'确实'}) \times \textrm{P}(\textrm{'数据'$|$'现在'}) \times  \nonumber \\
&   & \textrm{P}(\textrm{'很'$|$'数据'}) \times \textrm{P}(\textrm{'多'$|$'很'}) \nonumber
\end{eqnarray}

\vspace{-1em}

\item<2-> \textbf{训练} - 相对频率估计：$\textrm{P}(\textrm{'现在'$|$'确实'}) = \frac{count(\textrm{'确实 现在'})}{count(\textrm{'确实'})}$

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 其它一些问题
\begin{frame}{理解思想就可以了- 分词/方法/本身/不是/重点}

\begin{itemize}
\item *上面这个过程就是一个典型的\alert{数据驱动}的\alert{统计学习}方法，记住上一页的图就可以了
    \begin{itemize}
    \item 也称作全概率分词或者基于语言模型的分词
    \item 所谓数据驱动就是利用标注好的数据进行学习
    \item 最大的优点：整个学习（模型训练）和推导（处理新的句子）过程都\alert{全自动}进行
    \end{itemize}
\item<2-> 实现真实的分词系统还需要解决很多问题
    \begin{itemize}
    \item 如何高效搜索最优解：可以利用动态规划(DP)\\
          推荐黄老师的"Dynamic programming-based search algorithms in NLP"
    \item 未见过的词：概率等于0？赋予一个比较小的缺省值？
    \item 如何获取切分好的数据用于模型学习：人工？半自动？
    \end{itemize}
\item<3-> 其它可以应用于中文分词的统计方法
    \begin{itemize}
    \item google一下"中文分词"和"word segmentation"，看看2005年以后的文章
    \item google一下CRF，maximum entropy，LSTM+CRF
    \end{itemize}
\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
\section{句法分析}

%%%------------------------------------------------------------------------------------------------------------
\subsection{句子的树表示}

%%%------------------------------------------------------------------------------------------------------------
%%% 句子的树表示
\begin{frame}{休息一下，捋捋思路}

\begin{spacing}{1.1}

\begin{itemize}
\item 已经介绍的内容
    \begin{itemize}
    \item 句子是由单词构成的
    \item 如何定义单词、如何分词
    \item 如何利用统计模型完成自动分词系统的构建
    \end{itemize}
\item<2-> 即将要介绍的内容
    \begin{itemize}
    \item 可以用基于树的结构进一步描述句子的句法结构 - 句法树
    \item<3-> 如何获得一个句子的最佳句法树结构
    \end{itemize}
\end{itemize}

\end{spacing}

\vspace{-1.0em}

\begin{center}
\begin{tikzpicture}

\begin{scope}

\node [] (sent) at (0,0) {猫喜欢吃鱼};
\node [anchor=north west] (words) at ([yshift=-1em]sent.south west) {猫 / 喜欢 / 吃 / 鱼};
\draw [<-,double,thick,ublue] (words.north) -- ([yshift=1em]words.north);

\node [anchor=south west,minimum width=10em, minimum height=7em,draw,thick,ublue] (part1) at ([xshift=-0.5em]words.south west) {};
\node [anchor=north] (part1label) at ([yshift=-0.5em]part1.south) {part1: 句子表示为单词串};
%\draw [->,double,thick,red] (part1label.north)--([yshift=0.7em]part1label.north);
\node [anchor=center,draw=ublue,circle,thick,fill=white,inner sep=1pt,circular drop shadow={shadow xshift=0.1em,shadow yshift=-0.1em}] (head1) at ([xshift=-0.2em,yshift=-0.2em]part1.north east) {{\color{ugreen} \textbf{ok}}};

\visible<3->{
\node [anchor=west,draw=ublue,thick,fill=white,inner sep=2.5pt,drop shadow={shadow xshift=0.1em,shadow yshift=-0.1em}] (inputhead) at ([xshift=0.5em,yshift=-0.2em]part1.north west) {\textbf{输入}};
}

\end{scope}

\begin{scope}[xshift=2.3in,yshift=2.5em,level distance=22pt]

\visible<2->{

\Tree[.\node(bsn0){IP};
          [.\node(bsn1){NP};
               [.\node(bsn2){NN}; \node(bsw1){猫}; ]
          ]
          [.\node(bsn3){VP};
               [.\node(bsn4){VV}; \node(bsw2){喜欢}; ]
               [.\node(bsn5){VP}; \edge[roof]; \node(bsw3){吃 \ 鱼}; ]
          ]
     ]

\node [anchor=south west,minimum width=10em, minimum height=7em,draw,thick,ublue] (part2) at ([xshift=3.5em]part1.south east) {};
\node [anchor=north] (part2label) at ([yshift=-0.5em]part2.south) {part2: 句子表示为句法树};
%\draw [->,double,thick,red] (part2label.north)--([yshift=0.7em]part2label.north);
\node [anchor=center,draw=ublue,circle,thick,fill=white,inner sep=2.5pt,circular drop shadow={shadow xshift=0.1em,shadow yshift=-0.1em}] (head2) at ([xshift=-0.2em,yshift=-0.2em]part2.north east) {{\color{red} \textbf{?}}};

}

\visible<3->{
\node [anchor=west,draw=ublue,thick,fill=white,inner sep=2.5pt,drop shadow={shadow xshift=0.1em,shadow yshift=-0.1em}] (outputhead) at ([xshift=0.5em,yshift=-0.2em]part2.north west) {\textbf{输出}};
}

\end{scope}
\end{tikzpicture}
\end{center}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% outline
\begin{frame}{Outline}

\begin{center}
\begin{tikzpicture}

{\Large
\node [anchor=west,draw,gray,very thick,rounded corners=4pt,text width=15em,align=left,fill=white,drop shadow={shadow xshift=0.1em,shadow yshift=-0.1em}] (p1) at (0,0) {\gray{\textbf{1. 词法分析}}\\\gray{\textbf{\hspace{1.0em} - 中文分词 + 统计思想介绍}}};

\node [anchor=north west,draw,ublue,very thick,rounded corners=4pt,text width=15em,align=left,fill=white,drop shadow={shadow xshift=0.1em,shadow yshift=-0.1em}] (p21) at ([yshift=-1em]p1.south west) {\black{\textbf{2. 句法分析}}\\\black{\textbf{\hspace{1.0em} - 中文短语结构树分析}}};
}

\end{tikzpicture}
\end{center}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 句法树
\begin{frame}{先看两个例子}

\begin{tikzpicture}

\begin{scope}[sibling distance=7pt,level distance=22pt]
\node [anchor=west] (label) at (-0.7in,2em) {\small{\textbf{例子1:短语结构(成分)句法树}}};
\visible<1>{
\Tree[.\node[inner sep=1pt](sn0){IP\scriptsize{:句子}};
          [.\node[inner sep=1pt](sn1){NP\scriptsize{:名}};
               [.\node[inner sep=1pt](sn2){NN\tiny{:名词}}; \node(sw1){猫}; ]
          ]
          [.\node[inner sep=1pt](sn3){VP\scriptsize{:动}};
               [.\node[inner sep=1pt](sn4){VV\tiny{:动词}}; \node(sw2){喜欢}; ]
               [.\node[inner sep=1pt](sn5){VP\scriptsize{:动}};
                     [.\node[inner sep=1pt](sn6){VV\tiny{:动词}}; \node(sw1){吃}; ]
                     [.\node[inner sep=1pt](sn7){NN\tiny{:名词}}; \node(sw1){鱼}; ]
               ]
          ]
     ]
}

\visible<2>{
\Tree[.\node[inner sep=1pt](sn0){IP\scriptsize{:句子}};
          [.\node[inner sep=1pt](sn1){NP\scriptsize{:名}};
               [.\node[inner sep=1pt,fill=blue!20](sn2){NN\tiny{:名词}}; \node(sw1){猫}; ]
          ]
          [.\node[inner sep=1pt](sn3){VP\scriptsize{:动}};
               [.\node[inner sep=1pt,fill=blue!20](sn4){VV\tiny{:动词}}; \node(sw2){喜欢}; ]
               [.\node[inner sep=1pt](sn5){VP\scriptsize{:动}};
                     [.\node[inner sep=1pt,fill=blue!20](sn6){VV\tiny{:动词}}; \node(sw1){吃}; ]
                     [.\node[inner sep=1pt,fill=blue!20](sn7){NN\tiny{:名词}}; \node(sw1){鱼}; ]
               ]
          ]
     ]
}

\visible<3>{
\Tree[.\node[inner sep=1pt,fill=red!20](sn0){IP\scriptsize{:句子}};
          [.\node[inner sep=1pt,fill=red!20](sn1){NP\scriptsize{:名}};
               [.\node[inner sep=1pt,fill=blue!20](sn2){NN\tiny{:名词}}; \node(sw1){猫}; ]
          ]
          [.\node[inner sep=1pt,fill=red!20](sn3){VP\scriptsize{:动}};
               [.\node[inner sep=1pt,fill=blue!20](sn4){VV\tiny{:动词}}; \node(sw2){喜欢}; ]
               [.\node[inner sep=1pt](sn5){VP\scriptsize{:动}};
                     [.\node[inner sep=1pt,fill=blue!20](sn6){VV\tiny{:动词}}; \node(sw1){吃}; ]
                     [.\node[inner sep=1pt,fill=blue!20](sn7){NN\tiny{:名词}}; \node(sw1){鱼}; ]
               ]
          ]
     ]
}

\visible<4->{
\Tree[.\node[inner sep=1pt,fill=red!20](sn0){IP\scriptsize{:句子}};
          [.\node[inner sep=1pt,fill=red!20](sn1){NP\scriptsize{:名}};
               [.\node[inner sep=1pt,fill=blue!20](sn2){NN\tiny{:名词}}; \node(sw1){猫}; ]
          ]
          [.\node[inner sep=1pt,fill=red!20](sn3){VP\scriptsize{:动}};
               [.\node[inner sep=1pt,fill=blue!20](sn4){VV\tiny{:动词}}; \node(sw2){喜欢}; ]
               [.\node[inner sep=1pt,fill=green!20](sn5){VP\scriptsize{:动}};
                     [.\node[inner sep=1pt,fill=green!20](sn6){VV\tiny{:动词}}; \node(sw1){吃}; ]
                     [.\node[inner sep=1pt,fill=green!20](sn7){NN\tiny{:名词}}; \node(sw1){鱼}; ]
               ]
          ]
     ]
}

\end{scope}

\begin{scope}[xshift=1.7in,yshift=-0.4in]

\visible<5->{

\node [anchor=west] (label) at (1em,4.5em) {\small{\textbf{例子2:依存句法树}}};

\node [,inner sep=2pt] (w1) at (0,0) {猫};
\node [anchor=west,inner sep=2pt] (w2) at ([xshift=0.8em,yshift=3em]w1.east) {喜欢};
\node [anchor=west,inner sep=2pt] (w3) at ([xshift=4.5em]w1.east) {吃};
\node [anchor=west,inner sep=2pt] (w4) at ([xshift=2em,yshift=-3em]w3.east) {鱼};
\visible<5>{
\draw [-] (w1.north east) -- (w2.south);
}
\visible<5-6>{
\draw [-] (w3.north west) -- (w2.south);
}
\visible<5-7>{
\draw [-] (w3.south east) -- (w4.north west);
}
\visible<6->{
\draw [-,ultra thick,ublue] (w1.north east) -- (w2.south) node [pos=0.3, above, xshift=-0.5em] {\alert{\tiny{主谓}}};
}
\visible<7->{
\draw [-,ultra thick,red] (w3.north west) -- (w2.south) node [pos=0.3, above, xshift=0.5em] {\alert{\tiny{连动}}};
}
\visible<8->{
\draw [-,ultra thick,ugreen] (w3.south east) -- (w4.north west) node [pos=0.5, above, xshift=0.5em] {\alert{\tiny{谓宾}}};
}

}

\end{scope}

\end{tikzpicture}

\begin{minipage}[t]{0.48\linewidth}
\visible<2->{
从上图可以了解
}
\begin{itemize}
\item<2-> 每个单词都有词性 \tikz{\node[minimum height=0.7em,minimum width=0.7em,fill=blue!40] {};}
\item<3-> 名动结构 \tikz{\node[minimum height=0.7em,minimum width=0.7em,fill=red!40] {};}
\item<4-> 动宾结构 \tikz{\node[minimum height=0.7em,minimum width=0.7em,fill=green!40] {};}
\end{itemize}
\end{minipage}
\hfill
\begin{minipage}[t]{0.48\linewidth}
\visible<6->{
从上图可以了解
}
\begin{itemize}
\item<6-> '猫'依赖'喜欢' \tikz{\draw[ultra thick,-,ublue] (0,0)--(1em,0);}
\item<7-> '吃'依赖'喜欢' \tikz{\draw[ultra thick,-,red] (0,0)--(1em,0);}
\item<8-> '鱼'依赖'吃' \tikz{\draw[ultra thick,-,ugreen] (0,0)--(1em,0);}
\end{itemize}
\end{minipage}

\vspace{1.0em}

\visible<9->{
显然这些句法树都可以帮助机器翻译系统\alert{理解}句子的结构!
}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 句法分析是个啥
\begin{frame}{句法分析是什么？}
\label{parsingdef}

\begin{itemize}

\item 简单的实例就是我们上小学时学的句子结构分析
    \begin{itemize}
    \item 句子的成分：主语、谓语、宾语、状语...
    \item 各个成分内部/外部的关系：并列、介宾、连动
    \end{itemize}

    \begin{tikzpicture}
    {\small
    \node[anchor=west,fill=purple!20,inner sep=2pt] (w1) at (0,0) {小};
    \node[anchor=west,fill=green!20,inner sep=2pt] (w2) at ([xshift=0.5em]w1.east) {猫};
    \node[anchor=west,fill=red!20,inner sep=2pt] (w3) at ([xshift=0.5em]w2.east) {爬};
    \node[anchor=west,fill=blue!20,inner sep=2pt] (w4) at ([xshift=0.5em]w3.east) {到 树 上};
    \node[anchor=west,fill=orange!20,inner sep=2pt] (w5) at ([xshift=0.5em]w4.east) {去 了};
    }
    {\scriptsize
    \node[anchor=north,inner sep=0] (l1) at (w1.south) {定语};
    \node[anchor=north,inner sep=0] (l2) at (w2.south) {主语};
    \node[anchor=north,inner sep=0] (l3) at (w3.south) {谓语};
    \node[anchor=north,inner sep=0] (l4) at (w4.south) {宾语(方位)};
    \node[anchor=north,inner sep=0] (l5) at (w5.south) {补语};
    }
    \end{tikzpicture}

\item<2-> 更权威一点儿的定义\\
\vspace{0.2em}
\begin{beamerboxesrounded}[upper=uppercolblue,lower=lowercolblue,shadow=true]{句法分析(parsing或syntactic parsing)}
在自然语言或者计算机语言中，句法分析是利用形式化的\alert{文法}规则对一个\alert{符号串}进行\alert{分析}的过程
\begin{flushright}
---维基百科(译文)
\end{flushright}
\end{beamerboxesrounded}
\vspace{-0.5em}

    \begin{itemize}
    \item 符号串：可以理解为前面说的单词串
    \item 文法：关于语言结构的形式化定义，由规则组成
    \item 分析：利用文法解释句子结构
    \end{itemize}

\item<3-> 以上这些概念最好能记住，不过似乎和前面画的树也扯不上啊！ 实际上，句法树就是句法分析的一种形象表示

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 上下文无关文法
\begin{frame}{上下文无关文法}

\vspace{0.5em}

\begin{itemize}

\item 形式文法是句法分析中的核心内容。但是它本身是非常复杂的一套理论，这里不做深入讨论。推荐一个不错的介绍 \url{http://en.wikipedia.org/wiki/Formal_grammar}\\
\vspace{0.5em}
\item<2-> 作为抛砖引玉这里只介绍一下最常用的\alert{上下文无关文法}\\
\vspace{0.5em}
\begin{beamerboxesrounded}[upper=uppercolblue,lower=lowercolblue,shadow=true]{上下文无关文法(context-free grammar)}
一个上下文无关文法可以被视为一个系统\\
$G=<N,\Sigma,R,S>$，其中
\vspace{-0.3em}
\begin{itemize}
\item $N$为一个非终结符集合
\vspace{-0.5em}
\item $\Sigma$为一个终结符集合
\vspace{-0.5em}
\item $R$为一个规则(产生式)集合，每条规则 $r \in R$的形式为$X \to Y_1Y_2...Y_n$，其中$X \in N$, $Y_i \in N \cup \Sigma$
\vspace{-0.5em}
\item $S$为一个起始符号集合且$S \subseteq N$
\end{itemize}
\end{beamerboxesrounded}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
\subsection{上下文无关文法}

%%%------------------------------------------------------------------------------------------------------------
%%% 上下文无关文法 - 实例
\begin{frame}{上下文无关文法：实例}

\begin{itemize}

\item 把非终结符定义为不同的句法标记\\
$N=\{\textrm{NN},\textrm{VV},\textrm{NP},\textrm{VP},\textrm{IP}\}$\\
\alert{注意}，词性：NN-名词，VV-动词\\
短语结构：NP-名词短语，VP-动词短语，IP-单句
\item 把终结符定义为不同的单词\\
$\Sigma=\{\textrm{猫},\textrm{喜欢},\textrm{吃},\textrm{鱼}\}$
\item 把起始非终结符定义为整句的开始
$S=\{\textrm{IP}\}$
\item<2-> 规则集为对上述句法结构的组装($r_i$为规则的编号)\\
\vspace{0.3em}
\begin{tikzpicture}
\begin{scope}
{\small
\visible<2>{
\node [anchor=west,inner sep=2pt] (r1) at (0,0) {$r_1$: NN $\to$ 猫};
\node [anchor=west,inner sep=2pt] (r2) at ([xshift=6em]r1.east) {$r_2$: VV $\to$ 喜欢};
\node [anchor=north west,inner sep=2pt] (r3) at ([yshift=-0.2em]r1.south west) {$r_3$: VV $\to$ 吃};
\node [anchor=north west,inner sep=2pt] (r4) at ([yshift=-0.2em]r2.south west) {$r_4$: NN $\to$ 鱼};
}
\visible<2-3>{
\node [anchor=north west,inner sep=2pt] (r5) at ([yshift=-0.2em]r3.south west) {$r_5$: NP $\to$ NN};
}
\visible<2-4>{
\node [anchor=north west,inner sep=2pt] (r6) at ([yshift=-0.2em]r4.south west) {$r_6$: VP $\to$ VV NN};
\node [anchor=north west,inner sep=2pt] (r7) at ([yshift=-0.2em]r5.south west) {$r_7$: VP $\to$ VV VP};
\node [anchor=north west,inner sep=2pt] (r8) at ([yshift=-0.2em]r6.south west) {$r_8$: IP $\to$ NP VP};
}


\visible<3->{
\node [anchor=west,inner sep=2pt,fill=blue!20] (r1) at (0,0) {$r_1$: NN $\to$ 猫};
\node [anchor=west,inner sep=2pt,fill=blue!20] (r2) at ([xshift=6em]r1.east) {$r_2$: VV $\to$ 喜欢};
\node [anchor=north west,inner sep=2pt,fill=blue!20] (r3) at ([yshift=-0.2em]r1.south west) {$r_3$: VV $\to$ 吃};
\node [anchor=north west,inner sep=2pt,fill=blue!20] (r4) at ([yshift=-0.2em]r2.south west) {$r_4$: NN $\to$ 鱼};
}
\visible<4->{
\node [anchor=north west,inner sep=2pt,fill=red!20] (r5) at ([yshift=-0.2em]r3.south west) {$r_5$: NP $\to$ NN};
}
\visible<5->{
\node [anchor=north west,inner sep=2pt,fill=green!20] (r6) at ([yshift=-0.2em]r4.south west) {$r_6$: VP $\to$ VV NN};
\node [anchor=north west,inner sep=2pt,fill=green!20] (r7) at ([yshift=-0.2em]r5.south west) {$r_7$: VP $\to$ VV VP};
\node [anchor=north west,inner sep=2pt,fill=green!20] (r8) at ([yshift=-0.2em]r6.south west) {$r_8$: IP $\to$ NP VP};
}

\visible<3->{
\node [anchor=north west,fill=blue!20] (sent1) at ([yshift=-0.4em]r7.south west) {$r_1,r_2,r_3,r_4$};
\node [anchor=west] (sent1part2) at (sent1.east) {为生成单词词性的规则};
}
\visible<4->{
\node [anchor=north west,fill=red!20] (sent2) at ([yshift=-0.2em]sent1.south west) {$r_5$};
\node [anchor=west] (sent2part2) at (sent2.east) {为单变量规则，它将词性NN进一步抽象为名词短语NP};
}
\visible<5->{
\node [anchor=north west,fill=green!20] (sent3) at ([yshift=-0.2em]sent2.south west){$r_6,r_7,r_8$};
\node [anchor=west] (sent3part2) at (sent3.east) {为句法结构规则，比如$r_8$表示了主(NP)+谓(VP)结构};
}

}
\end{scope}
\end{tikzpicture}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 上下文无关文法 - 规则使用
\begin{frame}{上下文无关文法：规则使用}

\begin{itemize}

\item 上下文无关文法规则(下简称CFG规则)是一种产生式规则。对于规则$\alpha \to \beta$，它表示把规则左端的非中介符$\alpha$替换为规则右端的符号序列$\beta$。

\vspace{0.5em}

\visible<2->{

\begin{beamerboxesrounded}[upper=uppercolblue,lower=lowercolblue,shadow=true]{规则的使用}

一个符号序列$u$可以通过使用规则$r$替换其中的某个非终结符，并得到符号序列$v$，我们说$v$是在$u$上使用$r$的结果，记为：

\hspace{2em}
\begin{tikzpicture}
\begin{scope}
\node [anchor=west] (arule) at (0,0) {\large{$u \overset{r}{\Rightarrow} v$}};

\visible<3->{
\node [anchor=west,inner sep=2pt] (u) at ([xshift=-4em,yshift=-4em]arule.west) {VV};
}

\visible<5->{
\node [anchor=west,inner sep=2pt,fill=orange!40] (u) at ([xshift=-4em,yshift=-4em]arule.west) {VV};
}

\visible<3->{
\node [anchor=west] (upart2) at (u.east) {NN};
\node [anchor=east] (unumber) at (u.west) {$u:$};
}

\visible<4->{
\node [anchor=west,inner sep=2pt] (r) at ([xshift=-3em,yshift=2.5em]u.west) {VV};
}

\visible<5->{
\node [anchor=west,inner sep=2pt,fill=orange!40] (r) at ([xshift=-3em,yshift=2.5em]u.west) {VV};
}

\visible<4->{
\node [anchor=west] (rpart2) at (r.east) {$\to$};
\node [anchor=west,inner sep=2pt] (rpart3) at (rpart2.east) {吃};
\node [anchor=east] (rnumber) at (r.west) {$r:$};
}

\visible<5->{
\node [anchor=west,inner sep=2pt,fill=red!20] (rpart3) at (rpart2.east) {吃};
}

\visible<6->{
\node [anchor=west] (v) at ([xshift=5.5em]u.east) {$v$:};
\node [anchor=west,inner sep=2pt,fill=red!20] (vpart2) at (v.east) {吃};
\node [anchor=west] (vpart3) at (vpart2.east) {NN};
\node [anchor=west] (arrow) at ([xshift=3em]u.east) {$\Rightarrow$};
}

\visible<3->{
\draw [<-,dotted,thick] ([xshift=0.6em]arule.south west) ..controls +(south:0.7) and +(north:0.7).. ([xshift=-1.0em]upart2.north east);
}

\visible<6->{
\draw [<-,dotted,thick] ([xshift=-0.6em]arule.south east) ..controls +(south:0.7) and +(north:0.7).. ([xshift=1.0em]v.north west);
}

\visible<4->{
\draw [<-,dotted,thick] ([xshift=-0.4em,yshift=-0.5em]arule.north) ..controls +(180:0.7) and +(50:0.7) .. ([xshift=1em]rpart2.north west);
}

\visible<5->{
\draw [->,dotted,thick,ublue] (r.south) ..controls +(south:0.5) and +(north:0.5).. ([yshift=0]u.north);
}

\end{scope}
\end{tikzpicture}
\end{beamerboxesrounded}
}

\vspace{0.5em}

\item<7-> 如果$v$是在$u$上使用多条规则得到的结果，则记为：$u \overset{*}{\Rightarrow} v$

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 上下文无关文法 - 推导 vs. 树
\begin{frame}{上下文无关文法：推导 vs. 树}

实际上，我们可以从一个起始非终结符，不断地使用规则，最终生成一个终结符串。这个过程通常也被成为\alert{推导}的生成过程。\\

\vspace{-1.5em}

\begin{minipage}[t]{0.38\linewidth}
{\small
\begin{eqnarray}
& & \visible<3->{\textrm{IP}} \nonumber \\
& \visible<4->{\overset{r_8}{\Rightarrow}} & \visible<4->{\textrm{NP VP}} \nonumber \\
& \visible<5->{\overset{r_5}{\Rightarrow}} & \visible<5->{\textrm{NN VP}} \nonumber \\
& \visible<6->{\overset{r_1}{\Rightarrow}} & \visible<6->{\textrm{猫 VP}} \nonumber \\
& \visible<7->{\overset{r_7}{\Rightarrow}} & \visible<7->{\textrm{猫 VV VP}} \nonumber \\
& \visible<8->{\overset{r_2}{\Rightarrow}} & \visible<8->{\textrm{猫 喜欢 VP}} \nonumber \\
& \visible<9->{\overset{r_6}{\Rightarrow}} & \visible<9->{\textrm{猫 喜欢 VV NN}} \nonumber \\
& \visible<10->{\overset{r_3}{\Rightarrow}} & \visible<10->{\textrm{猫 喜欢 吃 NN}} \nonumber \\
& \visible<10->{\overset{r_4}{\Rightarrow}} & \visible<10->{\textrm{猫 喜欢 吃 鱼}} \nonumber
\end{eqnarray}
}
\end{minipage}
\hfill
\begin{minipage}[t]{0.55\linewidth}
\vspace{1.0em}
\begin{center}
\begin{tikzpicture}

\begin{scope}
{\scriptsize
\node [anchor=west,inner sep=2pt] (r1) at (0,0) {$r_1$: NN $\to$ 猫};
\node [anchor=west,inner sep=2pt] (r2) at ([xshift=3em]r1.east) {$r_2$: VV $\to$ 喜欢};
\node [anchor=north west,inner sep=2pt] (r3) at ([yshift=-0.2em]r1.south west) {$r_3$: VV $\to$ 吃};
\node [anchor=north west,inner sep=2pt] (r4) at ([yshift=-0.2em]r2.south west) {$r_4$: NN $\to$ 鱼};
\node [anchor=north west,inner sep=2pt] (r5) at ([yshift=-0.2em]r3.south west) {$r_5$: NP $\to$ NN};
\node [anchor=north west,inner sep=2pt] (r6) at ([yshift=-0.2em]r4.south west) {$r_6$: VP $\to$ VV NN};
\node [anchor=north west,inner sep=2pt] (r7) at ([yshift=-0.2em]r5.south west) {$r_7$: VP $\to$ VV VP};
\node [anchor=north west,inner sep=2pt] (r8) at ([yshift=-0.2em]r6.south west) {$r_8$: IP $\to$ NP VP};

\visible<6>{
\node [anchor=west,inner sep=2pt,fill=green!20] (r1) at (0,0) {$r_1$: NN $\to$ 猫};
}
\visible<8>{
\node [anchor=west,inner sep=2pt,fill=green!20] (r2) at ([xshift=3em]r1.east) {$r_2$: VV $\to$ 喜欢};
}
\visible<10>{
\node [anchor=north west,inner sep=2pt,fill=green!20] (r3) at ([yshift=-0.2em]r1.south west) {$r_3$: VV $\to$ 吃};
\node [anchor=north west,inner sep=2pt,fill=green!20] (r4) at ([yshift=-0.2em]r2.south west) {$r_4$: NN $\to$ 鱼};
}
\visible<5>{
\node [anchor=north west,inner sep=2pt,fill=green!20] (r5) at ([yshift=-0.2em]r3.south west) {$r_5$: NP $\to$ NN};
}
\visible<9>{
\node [anchor=north west,inner sep=2pt,fill=green!20] (r6) at ([yshift=-0.2em]r4.south west) {$r_6$: VP $\to$ VV NN};
}
\visible<7>{
\node [anchor=north west,inner sep=2pt,fill=green!20] (r7) at ([yshift=-0.2em]r5.south west) {$r_7$: VP $\to$ VV VP};
}
\visible<4>{
\node [anchor=north west,inner sep=2pt,fill=green!20] (r8) at ([yshift=-0.2em]r6.south west) {$r_8$: IP $\to$ NP VP};
}

}
\end{scope}

\begin{scope}[xshift=4.5em,yshift=-5.5em,level distance=20pt,sibling distance=13pt]

\visible<3->{
\Tree[.IP \edge[white];
          [.{\color{white} NP} \edge[white];
               [.{\color{white} NN} \edge[white]; \node[white](sw1){猫}; ]
          ] \edge[white];
          [.{\color{white} VP} \edge[white];
               [.{\color{white} VV} \edge[white]; \node[white](sw2){喜欢}; ] \edge[white];
               [.{\color{white} VP} \edge[white];
                     [.{\color{white} VV} \edge[white]; \node[white](sw1){吃}; ] \edge[white];
                     [.{\color{white} NN} \edge[white]; \node[white](sw1){鱼}; ]
               ]
          ]
     ]
}

\visible<4->{
\Tree[.IP
          [.NP \edge[white];
               [.{\color{white} NN} \edge[white]; \node[white](sw1){猫}; ]
          ]
          [.VP \edge[white];
               [.{\color{white} VV} \edge[white]; \node[white](sw2){喜欢}; ] \edge[white];
               [.{\color{white} VP} \edge[white];
                     [.{\color{white} VV} \edge[white]; \node[white](sw1){吃}; ] \edge[white];
                     [.{\color{white} NN} \edge[white]; \node[white](sw1){鱼}; ]
               ]
          ]
     ]
}

\visible<5->{
\Tree[.IP
          [.NP
               [.NN \edge[white]; \node[white](sw1){猫}; ]
          ]
          [.VP \edge[white];
               [.{\color{white} VV} \edge[white]; \node[white](sw2){喜欢}; ] \edge[white];
               [.{\color{white} VP} \edge[white];
                     [.{\color{white} VV} \edge[white]; \node[white](sw1){吃}; ] \edge[white];
                     [.{\color{white} NN} \edge[white]; \node[white](sw1){鱼}; ]
               ]
          ]
     ]
}

\visible<6->{
\Tree[.IP
          [.NP
               [.NN \node(sw1){猫}; ]
          ]
          [.VP \edge[white];
               [.{\color{white} VV} \edge[white]; \node[white](sw2){喜欢}; ] \edge[white];
               [.{\color{white} VP} \edge[white];
                     [.{\color{white} VV} \edge[white]; \node[white](sw1){吃}; ] \edge[white];
                     [.{\color{white} NN} \edge[white]; \node[white](sw1){鱼}; ]
               ]
          ]
     ]
}

\visible<7->{
\Tree[.IP
          [.NP
               [.NN \node(sw1){猫}; ]
          ]
          [.VP
               [.VV \edge[white]; \node[white](sw2){喜欢}; ]
               [.VP \edge[white];
                     [.{\color{white} VV} \edge[white]; \node[white](sw1){吃}; ] \edge[white];
                     [.{\color{white} NN} \edge[white]; \node[white](sw1){鱼}; ]
               ]
          ]
     ]
}

\visible<8->{
\Tree[.IP
          [.NP
               [.NN \node(sw1){猫}; ]
          ]
          [.VP
               [.VV \node(sw2){喜欢}; ]
               [.VP \edge[white];
                     [.{\color{white} VV} \edge[white]; \node[white](sw1){吃}; ] \edge[white];
                     [.{\color{white} NN} \edge[white]; \node[white](sw1){鱼}; ]
               ]
          ]
     ]
}

\visible<9->{
\Tree[.IP
          [.NP
               [.NN \node(sw1){猫}; ]
          ]
          [.VP
               [.VV \node(sw2){喜欢}; ]
               [.VP
                     [.VV \edge[white]; \node[white](sw1){吃}; ]
                     [.NN \edge[white]; \node[white](sw1){鱼}; ]
               ]
          ]
     ]
}

\visible<10->{
\Tree[.IP
          [.NP
               [.NN \node(sw1){猫}; ]
          ]
          [.VP
               [.VV \node(sw2){喜欢}; ]
               [.VP
                     [.VV \node(sw1){吃}; ]
                     [.NN \node(sw1){鱼}; ]
               ]
          ]
     ]
}

\end{scope}

\end{tikzpicture}
\end{center}

\end{minipage}

\vspace{-1em}

\visible<11->{
\begin{tikzpicture}
\node [draw,thick,red] (note) at (0,0) {\alert{\textbf{这个规则的使用序列本质上就对应了句法树的生成过程}}};
\end{tikzpicture}
}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 上下文无关文法 - 推导
\begin{frame}{上下文无关文法：推导 - 没有图的一页}

\vspace{0.5em}

\begin{beamerboxesrounded}[upper=uppercolblue,lower=lowercolblue,shadow=true]{推导}

给定一个文法$G=<N,\Sigma,R,S>$，对于一个字符串序列$s_0,s_1,...,s_n$和规则序列$r_1,r_2,...,r_n$，满足

\vspace{-0.5em}
\begin{displaymath}
s_0 \overset{r_1}{\Rightarrow} s_1 \overset{r_2}{\Rightarrow} s_2 \overset{r_3}{\Rightarrow} ... \overset{r_{n}}{\Rightarrow} s_n
\end{displaymath}

且

\begin{itemize}
\item $\forall i \in [0,n], s_i \in (N\cup\Sigma)^*$ \hspace{3em} $\lhd$ $s_i$为合法的字符串
\item $\forall j \in [1,n], r_j \in R$ \hspace{6em} $\lhd$ $r_j$为G的规则
\item $s_0 \in S$ \hspace{10.9em} $\lhd$ $s_0$为起始非终结符
\item $s_n \in \Sigma^{*}$ \hspace{10.4em} $\lhd$ $s_n$为终结符序列
\end{itemize}

则$s_0 \overset{r_1}{\Rightarrow} s_1 \overset{r_2}{\Rightarrow} s_2 \overset{r_3}{\Rightarrow} ... \overset{r_{n}}{\Rightarrow} s_n$为一个推导(derivation)

\end{beamerboxesrounded}

通常我们也把推导简记为$d=r_1 \circ r_2 \circ ... \circ r_n$，其中$\circ$表示规则的组合

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
\subsection{歧义}

%%%------------------------------------------------------------------------------------------------------------
%%% 歧义1：相同的树对应不同的推导
\begin{frame}{歧义1：相同的树对应不同的推导}
生成同一棵句法树，我们可以使用不同的规则序列，即，不同的推导最终会得到相同的句法树
\begin{itemize}
\item<2-> 解决方法：规则使用都服从最左优先原则
\item<3-> 这样得到的推导被称为最左优先推导，无歧义
\end{itemize}

\vspace{-3em}
\hspace{-1em}

\begin{minipage}[t]{0.32\linewidth}
\vspace{1.5em}
\begin{tikzpicture}
\begin{scope}[sibling distance=3pt, level distance=25pt]
{\small
\Tree[.IP
          [.NP
               [.NN \node(sw1){猫}; ]
          ]
          [.VP
               [.VV \node(sw2){喜欢}; ]
               [.VP
                     [.VV \node(sw1){吃}; ]
                     [.NN \node(sw1){鱼}; ]
               ]
          ]
     ]
}
\end{scope}
\end{tikzpicture}
\end{minipage}
\hfill
\begin{minipage}[t]{0.32\linewidth}
{\small
\begin{eqnarray}
& & \textrm{\textbf{推导1 \ \visible<3->{- \ \alert{YES}}}} \nonumber \\
& & \textrm{IP} \nonumber \\
& \overset{r_8}{\Rightarrow} & \textrm{NP VP} \nonumber \\
& \overset{r_5}{\Rightarrow} & \textrm{NN VP} \nonumber \\
& \overset{r_1}{\Rightarrow} & \textrm{猫 VP} \nonumber \\
& \overset{r_7}{\Rightarrow} & \textrm{猫 VV VP} \nonumber \\
& \overset{r_2}{\Rightarrow} & \textrm{猫 喜欢 VP} \nonumber \\
& \overset{r_6}{\Rightarrow} & \textrm{猫 喜欢 VV NN} \nonumber \\
& \overset{r_3}{\Rightarrow} & \textrm{猫 喜欢 吃 NN} \nonumber \\
& \overset{r_4}{\Rightarrow} & \textrm{猫 喜欢 吃 鱼} \nonumber
\end{eqnarray}
}
\end{minipage}
\hfill
\begin{minipage}[t]{0.32\linewidth}
{\small
\begin{eqnarray}
& & \textrm{\textbf{推导2 \ \visible<3->{- \ {\color{ublue} NO}}}} \nonumber \\
& & \textrm{IP} \nonumber \\
& \overset{r_8}{\Rightarrow} & \textrm{NP VP} \nonumber \\
& \overset{r_7}{\Rightarrow} & \textrm{NP VV VP} \nonumber \\
& \overset{r_2}{\Rightarrow} & \textrm{NP 喜欢 VP} \nonumber \\
& \overset{r_6}{\Rightarrow} & \textrm{NP 喜欢 VV NN} \nonumber \\
& \overset{r_4}{\Rightarrow} & \textrm{NP 喜欢 VV 鱼} \nonumber \\
& \overset{r_5}{\Rightarrow} & \textrm{NN 喜欢 VV 鱼} \nonumber \\
& \overset{r_3}{\Rightarrow} & \textrm{NN 喜欢 吃 鱼} \nonumber \\
& \overset{r_1}{\Rightarrow} & \textrm{猫 喜欢 吃 鱼} \nonumber
\end{eqnarray}
}
\end{minipage}


\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 歧义2：相同的串对应不同的树
\begin{frame}{歧义2：相同的句子对应不同的句法分析树}
生成一个单词序列，我们可以使用不同的最左推导，即，同一个句子可以有不同的树与之对应

\vspace{0.2em}

\begin{tabular}{l c c c}

&

\begin{tikzpicture}
\begin{scope}[sibling distance=-5pt, level distance=20pt]
{\footnotesize
\Tree[.IP
          [.VP
               [.VP
                    [.NN 猫 ]
                    [.VV 喜欢 ]
               ]
               [.VV 吃 ]
          ]
          [.NP
               [.NN 鱼 ]
          ]
     ]
}
\end{scope}
\end{tikzpicture}

&

\begin{tikzpicture}
\begin{scope}[sibling distance=-5pt, level distance=20pt]
{\footnotesize
\Tree[.IP
          [.NP
               [.NN 猫 ]
          ]
          [.VP
               [.VV 喜欢 ]
               [.VP
                     [.VV 吃 ]
                     [.NN 鱼 ]
               ]
          ]
     ]
}
\end{scope}
\end{tikzpicture}

&

\begin{tikzpicture}
\begin{scope}[sibling distance=-5pt, level distance=20pt]
{\footnotesize
\Tree[.IP
          [.NP
               [.NN 猫 ]
          ]
          [.VP
              [.VP
                   [.VV 喜欢 ]
                   [.VV 吃 ]
              ]
              [.NP
                   [.NN 鱼 ]
              ]
          ]
     ]
}
\end{scope}
\end{tikzpicture}

\\ \pause

语言学家: & 不对 & 对 & 不对  \\ \pause
我们: & 似乎对了 & 比较肯定 & 不太可能 \\ \pause
分析器: & P=0.2 & P=0.6 & P=0.1

\end{tabular}

\begin{itemize}
\item<5-> 句法分析任务本质上就是从所有可能的推导（句法树）中选择最优结果。
    \begin{itemize}
    \item 人：确定的结果 - 对 or 错
    \item 统计句法分析系统：所有结果都有可能，只是出现的概率不同
    \end{itemize}
\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
\subsection{基于统计的句法分析}

%%%------------------------------------------------------------------------------------------------------------
%%% 统计句法分析
\begin{frame}{统计句法分析}
\begin{itemize}
\item 我们现在知道，在给定上下文无关文法(CFG)的情况下:
    \begin{itemize}
    \item 每个(最左)推导都对应一棵句法树 (反之不一定成立)\\
          \begin{center}$d = $CFG句法分析树\end{center}
    \item 每个句子可能对应多个翻译推导
    \end{itemize}
\item<2-> 统计句法分析：对于任意的句子，找到概率最大的句法树(推导)输出
\end{itemize}

\vspace{-1.5em}

\begin{center}
\begin{tikzpicture}

\visible<3->{
\begin{scope}
\node [] (sent) at (0,0) {\textbf{猫 喜欢 吃 鱼}};
\end{scope}
}

\visible<4->{
\begin{scope}[xshift=-8em,yshift=-9em,sibling distance=-5pt,level distance=17pt,grow'=up]
{\footnotesize
\Tree[.IP
          [.VP
               [.VP
                    [.NN 猫 ]
                    [.VV 喜欢 ]
               ]
               [.VV 吃 ]
          ]
          [.NP
               [.NN 鱼 ]
          ]
     ]
}
\end{scope}

\begin{scope}[xshift=-1em,yshift=-9em,sibling distance=-5pt,level distance=17pt,grow'=up]
{\footnotesize
\Tree[.IP
          [.NP
               [.NN 猫 ]
          ]
          [.VP
               [.VV 喜欢 ]
               [.VP
                     [.VV 吃 ]
                     [.NN 鱼 ]
               ]
          ]
     ]
}
\end{scope}

\begin{scope}[xshift=8em,yshift=-9em,sibling distance=-5pt, level distance=17pt,grow'=up]
{\footnotesize
\Tree[.IP
          [.NP
               [.NN 猫 ]
          ]
          [.VP
              [.VP
                   [.VV 喜欢 ]
                   [.VV 吃 ]
              ]
              [.NP
                   [.NN 鱼 ]
              ]
          ]
     ]
}
\end{scope}

\draw [->,thick,ublue] ([xshift=-2em]sent.south) ..controls + (south:2em) and +(north:2em).. ([xshift=-8em,yshift=-2em]sent.south);
\draw [->,thick,ublue] ([xshift=-1em]sent.south) ..controls + (south:2em) and +(north:2em).. ([xshift=-2em,yshift=-3em]sent.south);
\draw [->,thick,ublue] ([xshift=0em]sent.south) ..controls + (south:2em) and +(north:2em).. ([xshift=6.5em,yshift=-2em]sent.south);
\draw [->,thick,ublue,dotted] ([xshift=1em]sent.south) ..controls + (south:1.5em) and +(north:2.5em).. ([xshift=12.5em,yshift=-2em]sent.south);

\node [anchor=north west] (others) at (11.8em,-3em) {...};

}

\visible<5->{
\node [] (d1) at (-9em,-10em) {$d_1$};
\node [] (d2) at (0em,-10em) {$d_2$};
\node [] (d3) at (8.5em,-10em) {$d_2$};
}

\visible<6->{
\node [anchor=east] (d1p) at ([xshift=0.4em]d1.west) {P(};
\node [anchor=west] (d1p2) at ([xshift=-0.4em]d1.east) {)=0.0123};
\node [anchor=east] (d2p) at ([xshift=0.4em]d2.west) {P(};
\node [anchor=west] (d2p2) at ([xshift=-0.4em]d2.east) {)=0.4031};
\node [anchor=east] (d3p) at ([xshift=0.4em]d3.west) {P(};
\node [anchor=west] (d3p2) at ([xshift=-0.4em]d3.east) {)=0.0056};
}

\visible<7->{
\node [anchor=center,fill=white,draw=red,thick,minimum width=25em] at (1em,-10.2em) {\alert{如何计算每棵句法树的概率，即推导的概率P($d$)???}};
}

\end{tikzpicture}
\end{center}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 分析概率
\begin{frame}{P($d$)=?}

\begin{itemize}
\item 在上下文无关文法中，每条规则之间的使用是相互独立的，因此可以把P($d$)分解为规则概率的乘积
      \begin{eqnarray}
      \textrm{P}(d) & = & \textrm{P}(r_1 \circ r_2 \circ ... \circ r_n) \nonumber \\
                    & \equiv & \textrm{P}(r_1) \cdot \textrm{P}(r_2) \cdot ... \cdot \textrm{P}(r_n) \nonumber
      \end{eqnarray}
      注意：上下文无关文法本身就包含规则使用的独立性假设，因此上式在CFG框架下并不是近似
\item<2-> 不太简单的问题：如何得到规则的生成概率？\\
      简单的方法：假设我们有人工标注的数据，其中包括很多句子的人工标注的句法树，称之为\alert{树库}。然后，对于规则$r: \alpha \to \beta$
      \begin{displaymath}
      \textrm{P}(r) = \frac{\textrm{规则}r\textrm{在树库中出现的次数}}{\alpha\textrm{在树库中出现的次数}}
      \end{displaymath}
      这里$\textrm{P}(r)\equiv\textrm{P}(\beta | \alpha)$，即规则的概率就是给定左手端生成右手端的概率。
\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 规则概率
\begin{frame}{P($r$)=?}

不用看前面的公式，来个例子

\begin{center}
\begin{tikzpicture}

\begin{scope}[sibling distance=0pt,level distance=17pt]
{\footnotesize
\Tree[.\node[inner sep=2pt](t1n1){IP};
          [.\node[inner sep=2pt](t1n2){NP};
               [.\node[inner sep=2pt](t1n3){NN}; 狗 ]
          ]
          [.\node[inner sep=2pt](t1n4){VP};
               [.\node[inner sep=2pt](t1n5){VV}; 喜欢 ]
               [.\node[inner sep=2pt](t1n6){VP};
                     [.\node[inner sep=2pt](t1n7){VV}; 吃 ]
                     [.\node[inner sep=2pt](t1n8){NN}; 骨头 ]
               ]
          ]
     ]
}
\end{scope}

\begin{scope}[sibling distance=0pt,level distance=17pt,yshift=-7em]
{\footnotesize
\Tree[.\node[inner sep=2pt](t2n1){IP};
          [.\node[inner sep=2pt](t2n2){VP};
               [.\node[inner sep=2pt](t2n3){VV}; \node[](t2w1){请}; ]
          ]
          [.\node[inner sep=2pt](t2n4){IP};
               [.\node[inner sep=2pt](t2n5){VP};
                    [.\node[inner sep=2pt](t2n6){VV}; 看 ]
               ]
               [.\node[inner sep=2pt](t2n7){NP};
                    [.\node[inner sep=2pt](t2n8){QP};
                          [.\node[inner sep=2pt](t2n9){CD}; 一 ]
                          [.\node[inner sep=2pt](t2n10){M}; 个 ]
                    ]
                    [.\node[inner sep=2pt](t2n11){ADJP};
                          [.\node[inner sep=2pt](t2n12){JJ}; 新 ]
                    ]
                    [.\node[inner sep=2pt](t2n13){NP};
                          [.\node[inner sep=2pt](t2n14){NN}; \node[](t2wn){句子}; ]
                    ]
               ]
          ]
     ]
}
\end{scope}

\node [anchor=south] (treebanklabel) at (t1n1.north) {{\color{ublue} 数据：树库}};

\begin{pgfonlayer}{background}
\node[rectangle,draw=ublue, inner sep=0.2em] [fit = (treebanklabel) (t1n1) (t2w1) (t2wn)] (treebank) {};
\end{pgfonlayer}

\node [anchor=north west] (math1) at ([xshift=2em]treebank.north east) {P('VP $\to$ VV NN')};
\node [anchor=north west] (math1part2) at ([xshift=-1em,yshift=0.2em]math1.south west) {$=\frac{\textrm{'VP'和'VV NN'同时出现的次数\visible<3->{=1}}}{\textrm{'VP'出现的次数}\visible<2->{=4}}$};
\visible<4->{
\node [anchor=north west] (math1part3) at ([yshift=0.2em]math1part2.south west){$=\frac{1}{4}$};
}

\visible<5->{
\node [anchor=north west] (math2) at ([yshift=-6em]math1.north west) {P('NP $\to$ NN')};
\node [anchor=north west] (math2part2) at ([xshift=-1em,yshift=0.2em]math2.south west) {$=\frac{\textrm{'NP'和'NN'同时出现的次数\visible<7->{=2}}}{\textrm{'NP'出现的次数}\visible<6->{=3}}$};
\visible<8->{
\node [anchor=north west] (math2part3) at ([yshift=0.2em]math2part2.south west){$=\frac{2}{3}$};
}
}

\visible<9->{
\node [anchor=north west] (math3) at ([yshift=-6em]math2.north west) {P('IP $\to$ NP NP')};
\node [anchor=north west] (math3part2) at ([xshift=-1em,yshift=0.2em]math3.south west) {$=\frac{\textrm{'IP'和'NP NP'同时出现的次数\visible<11->{=0}}}{\textrm{'IP'出现的次数}\visible<10->{=3}}$};
\visible<12->{
\node [anchor=north west] (math3part3) at ([yshift=0.2em]math3part2.south west){$=0$ or 一个很小的值(平滑?)};
}
}

\begin{pgfonlayer}{background}

\visible<2>{
\path [fill=red!20] (t1n4.north east) -- (t1n4.north west) -- (t1n4.south west) -- (t1n4.south east);
\path [fill=red!20] (t1n6.north east) -- (t1n6.north west) -- (t1n6.south west) -- (t1n6.south east);
\path [fill=red!20] (t2n2.north east) -- (t2n2.north west) -- (t2n2.south west) -- (t2n2.south east);
\path [fill=red!20] (t2n5.north east) -- (t2n5.north west) -- (t2n5.south west) -- (t2n5.south east);
}

\visible<3>{
\path [fill=red!20] (t1n6.north west) -- (t1n7.north west) -- (t1n7.south west) -- (t1n8.south east) -- (t1n8.north east) -- (t1n6.north east);
}

\visible<6>{
\path [fill=red!20] (t1n2.north east) -- (t1n2.north west) -- (t1n2.south west) -- (t1n2.south east);
\path [fill=red!20] (t2n7.north east) -- (t2n7.north west) -- (t2n7.south west) -- (t2n7.south east);
\path [fill=red!20] (t2n13.north east) -- (t2n13.north west) -- (t2n13.south west) -- (t2n13.south east);
}

\visible<7>{
\path [fill=red!20] (t1n2.north west) -- (t1n3.south west) -- (t1n3.south east) -- (t1n2.north east) -- (t1n2.north west);
\path [fill=red!20] (t2n13.north west) -- (t2n14.south west) -- (t2n14.south east) -- (t2n13.north east) -- (t2n13.north west);
}

\visible<10>{
\path [fill=red!20] (t1n1.north east) -- (t1n1.north west) -- (t1n1.south west) -- (t1n1.south east);
\path [fill=red!20] (t2n4.north east) -- (t2n4.north west) -- (t2n4.south west) -- (t2n4.south east);
\path [fill=red!20] (t2n1.north east) -- (t2n1.north west) -- (t2n1.south west) -- (t2n1.south east);
}

\end{pgfonlayer}

\end{tikzpicture}
\end{center}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 句法分析
\begin{frame}{句法分析过程}
\label{parsingmethod}

\vspace{-1.7em}

\begin{center}
\begin{tikzpicture}

{\scriptsize

\begin{scope}[level distance=10pt,xshift=1.5em,yshift=-0.5em]
{\tiny
\Tree[.\node[inner sep=1pt](t1n1){IP};
     [.\node[inner sep=1pt](t1n2){VP};
         [.\node[inner sep=1pt](t1n3){VV}; \node[](t1w1){看}; ]
     ]
     [.\node[inner sep=1pt](t1n4){NP};
         [.\node[inner sep=1pt](t1n5){M}; 个 ]
         [.\node[inner sep=1pt](t1n6){NN}; 例子 ]
     ]
]
}
\end{scope}

\begin{scope}[level distance=10pt,xshift=6.5em,yshift=-0.5em]
{\tiny
\Tree[.\node[inner sep=1pt](t2n1){IP};
     [.\node[inner sep=1pt](t2n2){NP};
         [.\node[inner sep=1pt](t2n3){PN}; 你 ]
     ]
     [.\node[inner sep=1pt](t2n4){VP};
         [.\node[inner sep=1pt](t2n5){VV}; 看到 ]
         [.\node[inner sep=1pt](t2n6){AS}; \node[](t2wn){了}; ]
     ]
]
}
\end{scope}

\node [anchor=west] (othertrees) at ([xshift=1em]t2n1.east) {...};

\node [anchor=south west] (corpuslabel) at ([xshift=-1em]t1n1.north west) {{\color{ublue} \textbf{学习用数据}}};

\begin{pgfonlayer}{background}
\node[rectangle,draw=ublue,thick,inner sep=0.2em,fill=white,drop shadow] [fit = (t1n1) (t1w1) (t2wn) (othertrees) (corpuslabel)] (corpus) {};
\end{pgfonlayer}
}

\node [anchor=west,ugreen] (P) at ([xshift=4.5em,yshift=-0.8em]corpus.east){\large{P($\cdot$)}};
\node [anchor=south] (modellabel) at (P.north) {{\color{ublue} {\scriptsize \textbf{统计分析模型}}}};

\begin{pgfonlayer}{background}
\node[rectangle,draw=ublue,thick,inner sep=0.2em,fill=white,drop shadow] [fit = (P) (modellabel)] (model) {};
\end{pgfonlayer}

\draw [->,very thick,ublue] ([xshift=0.2em]corpus.east) -- ([xshift=3.0em]corpus.east)  node [pos=0.5, above] {\alert{\scriptsize{统计学习}}};

\draw [->,very thick,ublue] ([xshift=0.2em]model.east) -- ([xshift=3.2em]model.east)  node [pos=0.5, above] {\alert{\scriptsize{穷举\&计算}}};

{\scriptsize
\node [anchor=north west] (sentlabel) at ([xshift=5.0em,yshift=-1em]model.north east) {\alert{句法分析系统}};
\node [anchor=north west] (sent) at (sentlabel.south west) {\textbf{对任意句子进行分析}};
}

\begin{pgfonlayer}{background}
\node[rectangle,draw=ublue,thick,inner sep=0.2em,fill=white,drop shadow] [fit = (sentlabel) (sent)] (parser) {};
\end{pgfonlayer}

\visible<2->{
{\footnotesize
\node [anchor=west] (label1) at (-0.5em,4.5em) {我们学习得到了一个(CFG)句法分析模型P($\cdot$)，对任意的句法分析结果};
\node [anchor=north west] (label1part2) at ([yshift=0.5em]label1.south west) {$d=r_1 \circ r_2 \circ ... \circ  r_n$，都能通过P($d$)=$\prod_{i=1}^{n} \textrm{P}(r_i)$计算其概率值};
}
}

\begin{pgfonlayer}{background}
\visible<2->{
\node[rectangle,fill=blue!10,thick,dotted,inner sep=0.2em] [fit = (label1) (label1part2)] (label1content) {};
}
\end{pgfonlayer}

\visible<2->{
\draw [-,very thick,red,dotted] ([yshift=0.3em]modellabel.north) ..controls +(north:0.3) and +(south:0.4).. ([xshift=-3em]label1content.south);
}


\begin{scope}[xshift=13em,yshift=-4.7em]

\visible<3->{
\node [inner sep=1pt] (sent) at (0,0) {\textbf{猫 喜欢 吃 鱼}};
}

\visible<4->{
\begin{scope}[xshift=-9.3em,yshift=-7em,sibling distance=4pt,level distance=12pt,grow'=up]
{\scriptsize
\Tree[.\node[inner sep=1pt](t1n1){IP};
          [.\node[inner sep=1pt]{VP};
               [.\node[inner sep=1pt]{VP};
                    [.\node[inner sep=1pt](t1n2){NN}; \node[inner sep=1pt]{猫}; ]
                    [.\node[inner sep=1pt]{VV}; \node[inner sep=1pt]{喜欢}; ]
               ]
               [.\node[inner sep=1pt]{VV}; \node[inner sep=1pt]{吃}; ]
          ]
          [.\node[inner sep=1pt]{NP};
               [.\node[inner sep=1pt]{NN}; \node[inner sep=1pt](t1wn){鱼}; ]
          ]
     ]
}
\end{scope}

\begin{scope}[xshift=-2em,yshift=-7em,sibling distance=4pt,level distance=12pt,grow'=up]
{\scriptsize
\Tree[.\node[inner sep=1pt](t2n1){IP};
          [.\node[inner sep=1pt]{NP};
               [.\node[inner sep=1pt]{NN}; \node[inner sep=1pt]{猫}; ]
          ]
          [.\node[inner sep=1pt]{VP};
               [.\node[inner sep=1pt]{VV}; \node[inner sep=1pt]{喜欢}; ]
               [.\node[inner sep=1pt]{VP};
                     [.\node[inner sep=1pt]{VV}; \node[inner sep=1pt]{吃}; ]
                     [.\node[inner sep=1pt]{NN}; \node[inner sep=1pt]{鱼}; ]
               ]
          ]
     ]
}
\end{scope}

\begin{scope}[xshift=8em,yshift=-7em,sibling distance=4pt,level distance=12pt,grow'=up]
{\scriptsize
\Tree[.\node[inner sep=1pt](t3n1){IP};
          [.\node[inner sep=1pt]{NP};
               [.\node[inner sep=1pt]{NN}; \node[inner sep=1pt]{猫}; ]
          ]
          [.\node[inner sep=1pt]{VP};
              [.\node[inner sep=1pt]{VP};
                   [.\node[inner sep=1pt]{VV}; \node[inner sep=1pt]{喜欢}; ]
                   [.\node[inner sep=1pt]{VV}; \node[inner sep=1pt]{吃}; ]
              ]
              [.\node[inner sep=1pt]{NP};
                   [.\node[inner sep=1pt]{NN}; \node[inner sep=1pt]{鱼}; ]
              ]
          ]
     ]
}
\end{scope}

\draw [->,thick,ublue] ([xshift=-2em]sent.south) ..controls + (south:2em) and +(north:2em).. ([xshift=-8em,yshift=-2em]sent.south);
\draw [->,thick,ublue] ([xshift=-1em]sent.south) ..controls + (south:1.5em) and +(north:1.5em).. ([xshift=-2em,yshift=-2em]sent.south);
\draw [->,thick,ublue] ([xshift=0em]sent.south) ..controls + (south:2em) and +(north:2em).. ([xshift=6.5em,yshift=-2em]sent.south);
\draw [->,thick,ublue,dotted] ([xshift=1em]sent.south) ..controls + (south:1.5em) and +(north:2.5em).. ([xshift=12.5em,yshift=-2em]sent.south);

\node [anchor=north west] (others) at (11.8em,-3em) {...};

}

\end{scope}

{\scriptsize

\visible<5>{
\node [anchor=west] (pd1) at ([xshift=-5em,yshift=-1.5em]t1n1.west) {$\textrm{P}(d_1)=\textrm{P}(\textrm{IP}\to\textrm{NP VP}) \cdot \textrm{P}(\textrm{NP}\to\textrm{NN}) \cdot \textrm{P}(\textrm{NN}\to\textrm{猫}) \cdot \textrm{P}(\textrm{VP}\to\textrm{VP VV}) \cdot$};
\node [anchor=north west] (pd1part2) at ([xshift=3.7em,yshift=0.2em]pd1.south west) {$\textrm{P}(\textrm{VV}\to\textrm{喜欢}) \cdot \textrm{P}(\textrm{VP}\to\textrm{NN VV}) \cdot \textrm{P}(\textrm{VV}\to\textrm{吃}) \cdot \textrm{P}(\textrm{NN}\to\textrm{鱼})$};
\node [anchor=north west] (pd1part3) at ([xshift=2.7em,yshift=-1.2em]pd1.south west) {=0.0004};
}

\visible<6->{
\node [anchor=west] (pd1final) at ([xshift=-5em,yshift=-1.5em]t1n1.west) {$\textrm{P}(d_1)=\prod_{r_i \in d_1} \textrm{P}(r_i)$};
\node [anchor=north west] (pd1part2final) at ([xshift=2.7em,yshift=0.2em]pd1final.south west) {=0.0004};

\node [anchor=west] (pd2final) at ([xshift=-2em,yshift=-1.5em]t2n1.west) {$\textrm{P}(d_2)=\prod_{r_i \in d_2} \textrm{P}(r_i)$};
\node [anchor=north west] (pd2part2final) at ([xshift=2.7em,yshift=0.2em]pd2final.south west) {=0.0128};

\node [anchor=west] (pd3final) at ([xshift=-3em,yshift=-1.5em]t3n1.west) {$\textrm{P}(d_3)=\prod_{r_i \in d_3} \textrm{P}(r_i)$};
\node [anchor=north west] (pd3part2final) at ([xshift=2.7em,yshift=0.2em]pd3final.south west) {=0.0002};
}

\visible<7->{
\node [anchor=center,draw=ublue,circle,thick,fill=white,inner sep=1pt,minimum size=1.9em,circular drop shadow={shadow xshift=0.1em,shadow yshift=-0.1em}] (result1) at ([xshift=1em,yshift=-0em]pd1part2final.south east) {{\color{red} \textbf{no}}};

\node [anchor=center,draw=ublue,circle,thick,fill=white,inner sep=1pt,minimum size=1.9em,circular drop shadow={shadow xshift=0.1em,shadow yshift=-0.1em}] (result1) at ([xshift=1em,yshift=-0em]pd2part2final.south east) {{\color{ugreen} \textbf{yes}}};

\node [anchor=center,draw=ublue,circle,thick,fill=white,inner sep=1pt,minimum size=1.9em,circular drop shadow={shadow xshift=0.1em,shadow yshift=-0.1em}] (result1) at ([xshift=1em,yshift=-0em]pd3part2final.south east) {{\color{red} \textbf{no}}};
}

}

\begin{pgfonlayer}{background}
\visible<3->{
\node[rectangle,fill=blue!10,thick,dotted,inner sep=0.2em] [fit = (sent) (t1n2) (others) (pd1part3)] (label2content) {};
}
\end{pgfonlayer}

\visible<3->{
\draw [-,very thick,red,dotted] ([yshift=-0.3em]parser.south) ..controls +(south:0.5) and +(north:0.5).. ([xshift=3em]label2content.north);
}

\end{tikzpicture}
\end{center}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 其它问题
\begin{frame}{句法分析并不简单}

句法分析是自然语言处理的难题之一，这里只介绍了皮毛

\begin{itemize}
\item \textbf{文法形式：}除了上下文无关文法，还有不下20种其它的文法
    \begin{itemize}
    \item TAG(树邻接文法)、TSG(树替换文法)等 - 不是本课程重点
    \end{itemize}
\item \textbf{句法分析算法：}如何高效地搜索最优解 - 这里没说
    \begin{itemize}
    \item 构建句法分析器最重要的部分，与机器翻译解码问题相关
    \item 非常重要，在后面统计机器翻译解码中还有相关算法介绍
    \item 自底向上、A$^*$等算法
    \end{itemize}
\item \textbf{统计学习：}如何学习句法分析模型
    \begin{itemize}
    \item 机器学习中的基础问题，句法分析可以看做是一种应用
    \item google一下parsing supervised unsupervised learning
    \end{itemize}
\item \textbf{句法(树)表现形式：}短语结构树 vs. 依存树
    \begin{itemize}
    \item 本课程以短语结构树为基础 - 但是这两种结构在统计机器翻译中都有使用
    \item 关于依存分析，google一下dependency parsing
    \end{itemize}
\item ...
\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
\section{小结}

%%%------------------------------------------------------------------------------------------------------------
%%% 总结
\begin{frame}{内容已经介绍完了，总结一下}

\setlength\fboxsep{0pt}
\setlength\fboxrule{0.3pt}

说了很多，记住三方面主要内容就可以了：

\begin{enumerate}
\item \textbf{任务：}啥是分词、啥是句法分析？\\
       见{\color{ublue} \hyperref[wordsegdef]{第\hspace{-0.2em}~\ref{wordsegdef}页}}和{\color{ublue} \hyperref[parsingdef]{第\hspace{-0.2em}~\ref{parsingdef}页}} \raisebox{-3em}{\fbox{\includegraphics[scale=0.09]{./Figures/page-segdef.jpg}}} \raisebox{-3em}{\fbox{\includegraphics[scale=0.09]{./Figures/page-parsingdef.jpg}}}
\vspace{0.2em}
\item \textbf{手段：}啥是P($\cdot$)? \\
       见{\color{ublue} \hyperref[probdef]{第\hspace{-0.2em}~\ref{probdef}页}} \raisebox{-3em}{\fbox{\includegraphics[scale=0.09]{./Figures/page-probdef.jpg}}}
\vspace{0.2em}
\item \textbf{方法：}如何用P($\cdot$)解决分词和句法分析问题？\\
       见{\color{ublue} \hyperref[wordsegmethod]{第\hspace{-0.2em}~\ref{wordsegmethod}页}}和{\color{ublue} \hyperref[parsingmethod]{第\hspace{-0.2em}~\ref{parsingmethod}页}} \raisebox{-3em}{\fbox{\includegraphics[scale=0.09]{./Figures/page-segmethod.jpg}}} \raisebox{-3em}{\fbox{\includegraphics[scale=0.09]{./Figures/page-parsingmethod.jpg}}}
\end{enumerate}

\vspace{0.5em}

\visible<2->{
\begin{tikzpicture}
\node [draw,thick,red] (note) at (0,0) {\alert{\textbf{还是那句话：理解思想最最重要，实现方法可以后面再消化}}};
\end{tikzpicture}
}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 最后一页
\begin{frame}{第二章内容也结束喽！}

\begin{center}
\begin{tikzpicture}
\node [] (l1) at (0,0) {谢谢对本教程的关注};

\node [anchor=north] (l2) at ([yshift=-1em]l1.south) {谢谢/对/本/教程/的/关注};
\draw [->,double,thick,ublue] (l1.south) -- (l2.north);
\draw [->,double,thick,ublue] (l2.south) -- ([yshift=-1em]l2.south);

\begin{scope}[yshift=-2.9in,xshift=-1em,grow'=up,level distance=23pt]
\Tree[.IP
           [.VP
                 [.VV 谢谢 ]
           ]
           [.NP
                 [.DNP
                       [.PP
                            [.P 对 ]
                            [.NP
                                  [.DT 本 ]
                                  [.NN 教程 ]
                            ]
                       ]
                       [.DEG 的 ]
                 ]
                 [.NP
                       [.NN 关注 ]
                 ]
           ]
     ]
\end{scope}


\end{tikzpicture}
\end{center}

\end{frame}

\end{CJK}
\end{document}
