% !Mode:: "TeX:GBK"

\def\CTeXPreproc{Created by ctex v0.2.13, don't edit!}
\documentclass[cjk,t,compress,12pt]{beamer}
%\documentclass[cjk,t,compress,handout,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{arrows,decorations.pathreplacing}
\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}

%%%------------------------------------------------------------------------------------------------------------
%%% landscape
\begin{frame}{Landscape}

\vspace{-1em}
\begin{center}
\begin{tikzpicture}

\node [] (history) at (0,0) {\includegraphics[scale=0.29]{./Figures/mt-history.png}};

\visible<2->{
\draw[-,thick] ([xshift=-1.1in]history.south) coordinate (top01) -- ([yshift=-2em]top01);
\draw[-,thick] ([xshift=1in]history.south) coordinate (top02) -- ([yshift=-2em]top02);
\draw[-,thick] ([xshift=-0.3in]history.south east) coordinate (top03) -- ([yshift=-2em]top03);
\draw[<->,thick] ([yshift=-1em]top01) -- ([yshift=-1em]top02) node [pos=0.5,below,align=left,yshift=-0.5em] {\footnotesize{\textbf{Sections 3-4:}}\\\footnotesize{统计机器翻译}};
\draw[<->,thick] ([yshift=-1em]top02) -- ([yshift=-1em]top03) node [pos=0.5,below,align=left,yshift=-0.5em] {\footnotesize{\textbf{Sections 5-6:}}\\\footnotesize{神经机器翻译}};
}

\visible<3->{
\draw[<-,thick] ([xshift=-0.9in,yshift=-0.2in]history.north) coordinate (label01) -- ([yshift=1.5em,xshift=1.5em]label01) coordinate (label02);
\node[anchor=south west,align=left] (label) at ([xshift=-5em]label02) {\textbf{\alert{本章内容（Section 3）：}}\\统计机器翻译开山之作 - IBM模型\\\textit{The Mathematics of Statistical Machine Translation:}\\\textit{Parameter Estimation} by Peter E. Brown et al., 1993.};
}

\end{tikzpicture}
\end{center}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
\section{按单词翻译：一个实例}

%%%------------------------------------------------------------------------------------------------------------
\subsection{基本思想}

%%%------------------------------------------------------------------------------------------------------------
%%% 基于单词翻译思想
\begin{frame}{按单词进行翻译}

\begin{beamerboxesrounded}[upper=uppercolblue,lower=lowercolblue,shadow=true]{基于单词的(统计)机器翻译思想}
两个互译句子之间存在一种\alert{单词}间的对应，而整句的翻译是由\alert{单词}的翻译"组成"
\begin{center}
\begin{tikzpicture}

\begin{scope}
\node [anchor=west] (s1) at (0,0) {我};
\node [anchor=west] (s2) at ([xshift=0.5em]s1.east) {对};
\node [anchor=west] (s3) at ([xshift=0.5em]s2.east) {你};
\node [anchor=west] (s4) at ([xshift=0.5em]s3.east) {感到};
\node [anchor=west] (s5) at ([xshift=0.5em]s4.east) {满意};
\end{scope}

\begin{scope}[yshift=-3em]
\node [anchor=west] (t1) at (0.35em,0) {I};
\node [anchor=west] (t2) at ([xshift=0.3em,yshift=-0.1em]t1.east) {am};
\node [anchor=west] (t3) at ([xshift=0.3em,yshift=0.1em]t2.east) {satisfied};
\node [anchor=west] (t4) at ([xshift=0.3em]t3.east) {with};
\node [anchor=west] (t5) at ([xshift=0.3em,yshift=-0.2em]t4.east) {you};
\end{scope}

\visible<1>{
\draw [<->,double,thick,ublue] (s3.south east) -- ([yshift=-1.5em]s3.south east);
}
\visible<2->{
\draw [-,thick,ublue,dashed] (s1.south) -- (t1.north);
\draw [-,thick,ublue,dashed] (s4.south) -- ([yshift=0.3em]t2.north);
\draw [-,thick,ublue,dashed] (s2.south) ..controls +(south:1em) and +(north:1em).. (t4.north);
\draw [-,thick,ublue,dashed] (s3.south) ..controls +(south:0.5em) and +(north:1.5em).. (t5.north);
\draw [-,thick,ublue,dashed] (s5.south) -- (t3.north);
}

\end{tikzpicture}
\end{center}
\end{beamerboxesrounded}

\begin{itemize}
\item<3-> 传统观点下的(基于词)的翻译过程 - 三个步骤\\
\vspace{-0.8em}
\begin{minipage}[t]{0.58\linewidth}
\begin{enumerate}
\item \textbf{分析}：将输入句子进行分词
\vspace{-0.5em}
\item<4-> \textbf{转换}：获得每个源语单词的翻译
\vspace{-0.5em}
\item<5-> \textbf{生成}：将单词的翻译组成通顺的整句译文
\end{enumerate}
\visible<6->{
本章的重点内容为\textbf{转换}和\textbf{生成}
}
\end{minipage}
\hfill
\begin{minipage}[t]{0.40\linewidth}
\vspace{0.3em}
\begin{center}
\begin{tikzpicture}
\node [anchor=west,draw,thick,minimum width=6.7em,minimum height=0.8em] (sent) at (0,0) {};

\node [anchor=west,draw,thick,circle,minimum size=0.3em,red] (s1) at ([yshift=-1.5em]sent.south west) {};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,ugreen] (s2) at ([xshift=0.4em]s1.east) {};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,orange] (s3) at ([xshift=0.4em]s2.east) {};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,ublue] (s4) at ([xshift=0.4em]s3.east) {};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,purple] (s5) at ([xshift=0.4em]s4.east) {};

\visible<4->{
\node [anchor=west,draw,thick,circle,minimum size=0.3em,red,fill=red] (t1) at ([yshift=-2.0em]s1.west) {};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,ugreen,fill=ugreen] (t2) at ([xshift=0.4em]t1.east) {};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,orange,fill=orange] (t3) at ([xshift=0.4em]t2.east) {};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,ublue,fill=ublue] (t4) at ([xshift=0.4em]t3.east) {};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,purple,fill=purple] (t5) at ([xshift=0.4em]t4.east) {};
}

\visible<5->{
\node [anchor=west,draw,thick,circle,minimum size=0.3em,red,fill=red] (ft1) at ([yshift=-2.0em]t1.west) {};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,ublue,fill=ublue] (ft2) at ([xshift=0.4em]ft1.east) {};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,purple,fill=purple] (ft3) at ([xshift=0.4em]ft2.east) {};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,ugreen,fill=ugreen] (ft4) at ([xshift=0.4em]ft3.east) {};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,orange,fill=orange] (ft5) at ([xshift=0.4em]ft4.east) {};
}

\draw [->,thick,double] ([yshift=-0.1em]sent.south) -- ([yshift=-0.8em]sent.south);

\visible<4->{
\draw [->,thick] ([yshift=-0.1em]s1.south) -- ([yshift=0.1em]t1.north);
\draw [->,thick] ([yshift=-0.1em]s2.south) -- ([yshift=0.1em]t2.north);
\draw [->,thick] ([yshift=-0.1em]s3.south) -- ([yshift=0.1em]t3.north);
\draw [->,thick] ([yshift=-0.1em]s4.south) -- ([yshift=0.1em]t4.north);
\draw [->,thick] ([yshift=-0.1em]s5.south) -- ([yshift=0.1em]t5.north);
}

\visible<5->{
\draw [->,thick] ([yshift=-0.1em]t1.south) -- ([yshift=0.1em]ft1.north);
\draw [->,thick] ([yshift=-0.1em]t2.south) -- ([yshift=0.1em]ft4.north);
\draw [->,thick] ([yshift=-0.1em]t3.south) -- ([yshift=0.1em]ft5.north);
\draw [->,thick] ([yshift=-0.1em]t4.south) -- ([yshift=0.1em]ft2.north);
\draw [->,thick] ([yshift=-0.1em]t5.south) -- ([yshift=0.1em]ft3.north);
}

\node [anchor=north west] (label1) at ([yshift=0.3em]sent.south east) {{\scriptsize \textbf{分析(分词)}}};
\visible<4->{
\node [anchor=north west] (label2) at ([yshift=-0.5em]label1.south west) {{\scriptsize \textbf{转换}}};
}
\visible<5->{
\node [anchor=north west] (label3) at ([yshift=-0.5em]label2.south west) {{\scriptsize \textbf{生成}}};
}

\visible<6->{
\node [anchor=west,draw=red,thick,dotted,minimum width=9em,minimum height=5.3em] (focus) at ([xshift=-0.2em]t1.west) {};
}

\end{tikzpicture}
\end{center}
\end{minipage}
\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 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. 一个简单的翻译实例}}};

\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. IBM模型}}\\\gray{\textbf{\hspace{1.5em}$\bullet$  建模}}\\\gray{\textbf{\hspace{1.5em}$\bullet$  解码}}\\\gray{\textbf{\hspace{1.5em}$\bullet$  模型训练}}};
}

\end{tikzpicture}
\end{center}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
\subsection{翻译流程：人工 vs. 机器}

%%%------------------------------------------------------------------------------------------------------------
%%% 流程示例 - 人工翻译
\begin{frame}{我们人是如何进行翻译的？}

\vspace{-0.5em}

\begin{flushright}
\begin{tikzpicture}

\begin{scope}

\node [anchor=west] (s1) at (0,0) {\textbf{我}};
\node [anchor=west] (s2) at ([xshift=2em]s1.east) {\textbf{对}};
\node [anchor=west] (s3) at ([xshift=2em]s2.east) {\textbf{你}};
\node [anchor=west] (s4) at ([xshift=2em]s3.east) {\textbf{表示}};
\node [anchor=west] (s5) at ([xshift=2em]s4.east) {\textbf{满意}};

\node [anchor=south west] (sentlabel) at ([yshift=-0.5em]s1.north west) {\scriptsize{\textbf{\alert{待翻译句子(已经分词):}}}};

\visible<2->{
\draw [->,very thick,ublue] (s1.south) -- ([yshift=-0.7em]s1.south);
\draw [->,very thick,ublue] (s2.south) -- ([yshift=-0.7em]s2.south);
\draw [->,very thick,ublue] (s3.south) -- ([yshift=-0.7em]s3.south);
\draw [->,very thick,ublue] (s4.south) -- ([yshift=-0.7em]s4.south);
\draw [->,very thick,ublue] (s5.south) -- ([yshift=-0.7em]s5.south);

{\small
\node [anchor=north,inner sep=2pt,fill=red!20,minimum height=1.5em,minimum width=2.5em] (t11) at ([yshift=-1em]s1.south) {I};
\node [anchor=north,inner sep=2pt,fill=red!20,minimum height=1.5em,minimum width=2.5em] (t12) at ([yshift=-0.2em]t11.south) {me};
\node [anchor=north,inner sep=2pt,fill=red!20,minimum height=1.5em,minimum width=2.5em] (t13) at ([yshift=-0.2em]t12.south) {I'm};
\node [anchor=north west,inner sep=1pt,fill=black] (tl11) at (t11.north west) {\tiny{{\color{white} \textbf{1}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (tl12) at (t12.north west) {\tiny{{\color{white} \textbf{1}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (tl13) at (t13.north west) {\tiny{{\color{white} \textbf{1}}}};

\node [anchor=north,inner sep=2pt,fill=green!20,minimum height=1.5em,minimum width=2.5em] (t21) at ([yshift=-1em]s2.south) {to};
\node [anchor=north,inner sep=2pt,fill=green!20,minimum height=1.5em,minimum width=2.5em] (t22) at ([yshift=-0.2em]t21.south) {with};
\node [anchor=north,inner sep=2pt,fill=green!20,minimum height=1.5em,minimum width=2.5em] (t23) at ([yshift=-0.2em]t22.south) {for};
\node [anchor=north west,inner sep=1pt,fill=black] (tl21) at (t21.north west) {\tiny{{\color{white} \textbf{2}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (tl22) at (t22.north west) {\tiny{{\color{white} \textbf{2}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (tl23) at (t23.north west) {\tiny{{\color{white} \textbf{2}}}};

\node [anchor=north,inner sep=2pt,fill=blue!20,minimum height=1.5em,minimum width=2.5em] (t31) at ([yshift=-1em]s3.south) {you};
\node [anchor=north west,inner sep=1pt,fill=black] (tl31) at (t31.north west) {\tiny{{\color{white} \textbf{3}}}};

\node [anchor=north,inner sep=2pt,fill=orange!20,minimum height=1.5em,minimum width=3em] (t41) at ([yshift=-1em]s4.south) {$\phi$};
\node [anchor=north,inner sep=2pt,fill=orange!20,minimum height=1.5em,minimum width=3em] (t42) at ([yshift=-0.2em]t41.south) {show};
\node [anchor=north west,inner sep=1pt,fill=black] (tl41) at (t41.north west) {\tiny{{\color{white} \textbf{4}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (tl42) at (t42.north west) {\tiny{{\color{white} \textbf{4}}}};

\node [anchor=north,inner sep=2pt,fill=purple!20,minimum height=1.5em,minimum width=4.5em] (t51) at ([yshift=-1em]s5.south) {satisfy};
\node [anchor=north,inner sep=2pt,fill=purple!20,minimum height=1.5em,minimum width=4.5em] (t52) at ([yshift=-0.2em]t51.south) {satisfied};
\node [anchor=north,inner sep=2pt,fill=purple!20,minimum height=1.5em,minimum width=4.5em] (t53) at ([yshift=-0.2em]t52.south) {satisfies};
\node [anchor=north west,inner sep=1pt,fill=black] (tl51) at (t51.north west) {\tiny{{\color{white} \textbf{5}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (tl52) at (t52.north west) {\tiny{{\color{white} \textbf{5}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (tl53) at (t53.north west) {\tiny{{\color{white} \textbf{5}}}};

}

}

\invisible{
{\tiny

\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt11) at (t11.east) {{\color{white} \textbf{P=.4}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt12) at (t12.east) {{\color{white} \textbf{P=.2}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt13) at (t13.east) {{\color{white} \textbf{P=.4}}};

\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt21) at (t21.east) {{\color{white} \textbf{P=.4}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt22) at (t22.east) {{\color{white} \textbf{P=.3}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt23) at (t23.east) {{\color{white} \textbf{P=.3}}};

\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt31) at (t31.east) {{\color{white} \textbf{P=1}}};

\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt41) at (t41.east) {{\color{white} \textbf{P=.5}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt42) at (t42.east) {{\color{white} \textbf{P=.5}}};

\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt51) at (t51.east) {{\color{white} \textbf{P=.5}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt52) at (t52.east) {{\color{white} \textbf{P=.4}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt53) at (t53.east) {{\color{white} \textbf{P=.1}}};

}
}

\end{scope}

\begin{scope}
{\small

\visible<3->{
\node [anchor=west,inner sep=2pt,fill=red!20,minimum height=1.5em,minimum width=2.5em] (ft11) at ([yshift=-1.2in]t11.west) {I'm};
\node [anchor=center,inner sep=2pt,fill=purple!20,minimum height=1.5em,minimum width=5em] (ft12) at ([xshift=5.0em]ft11.center) {satisfied};
\node [anchor=center,inner sep=2pt,fill=green!20,minimum height=1.5em,minimum width=2.5em] (ft13) at ([xshift=5.0em]ft12.center) {with};
\node [anchor=center,inner sep=2pt,fill=blue!20,minimum height=1.5em,minimum width=2.5em] (ft14) at ([xshift=4.0em]ft13.center) {you};
}

\invisible{
\node [anchor=west,inner sep=2pt,fill=red!20,minimum height=1.5em,minimum width=2.5em] (ft21) at ([yshift=-2em]ft11.west) {I'm};
\node [anchor=center,inner sep=2pt,fill=purple!20,minimum height=1.5em,minimum width=5em] (ft22) at ([xshift=5.0em]ft21.center) {satisfies};
\node [anchor=center,inner sep=2pt,fill=green!20,minimum height=1.5em,minimum width=2.5em] (ft23) at ([xshift=5.0em]ft22.center) {to};
\node [anchor=center,inner sep=2pt,fill=blue!20,minimum height=1.5em,minimum width=2.5em] (ft24) at ([xshift=4.0em]ft23.center) {you};

\node [anchor=west,inner sep=2pt,fill=red!20,minimum height=1.5em,minimum width=2.5em] (ft31) at ([yshift=-2em]ft21.west) {I'm};
\node [anchor=center,inner sep=2pt,fill=purple!20,minimum height=1.5em,minimum width=5em] (ft32) at ([xshift=5.0em]ft31.center) {satisfies};
\node [anchor=center,inner sep=2pt,fill=blue!20,minimum height=1.5em,minimum width=2.5em] (ft33) at ([xshift=5.0em]ft32.center) {you};
\node [anchor=center,inner sep=2pt,fill=green!20,minimum height=1.5em,minimum width=2.5em] (ft34) at ([xshift=4.0em]ft33.center) {to};
}

\visible<3->{
\node [anchor=north west,inner sep=1pt,fill=black] (ftl11) at (ft11.north west) {\tiny{{\color{white} \textbf{1}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (ftl12) at (ft12.north west) {\tiny{{\color{white} \textbf{5}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (ftl13) at (ft13.north west) {\tiny{{\color{white} \textbf{2}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (ftl14) at (ft14.north west) {\tiny{{\color{white} \textbf{3}}}};
}

\invisible{
\node [anchor=north west,inner sep=1pt,fill=black] (ftl21) at (ft21.north west) {\tiny{{\color{white} \textbf{1}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (ftl22) at (ft22.north west) {\tiny{{\color{white} \textbf{5}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (ftl23) at (ft23.north west) {\tiny{{\color{white} \textbf{2}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (ftl24) at (ft24.north west) {\tiny{{\color{white} \textbf{3}}}};

\node [anchor=north west,inner sep=1pt,fill=black] (ftl31) at (ft31.north west) {\tiny{{\color{white} \textbf{1}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (ftl32) at (ft32.north west) {\tiny{{\color{white} \textbf{5}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (ftl33) at (ft33.north west) {\tiny{{\color{white} \textbf{3}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (ftl34) at (ft34.north west) {\tiny{{\color{white} \textbf{2}}}};
}

\invisible{
{\tiny
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft11) at (ft11.east) {{\color{white} \textbf{P=.4}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft12) at (ft12.east) {{\color{white} \textbf{P=.4}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft13) at (ft13.east) {{\color{white} \textbf{P=.3}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft14) at (ft14.east) {{\color{white} \textbf{P=1}}};

\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft21) at (ft21.east) {{\color{white} \textbf{P=.4}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft22) at (ft22.east) {{\color{white} \textbf{P=.1}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft23) at (ft23.east) {{\color{white} \textbf{P=.4}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft24) at (ft24.east) {{\color{white} \textbf{P=1}}};

\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft31) at (ft31.east) {{\color{white} \textbf{P=.4}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft32) at (ft32.east) {{\color{white} \textbf{P=.1}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft33) at (ft33.east) {{\color{white} \textbf{P=1}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft34) at (ft34.east) {{\color{white} \textbf{P=.4}}};

}

\node [anchor=west,inner sep=2pt,minimum height=1.5em,minimum width=2.5em] (ft41) at ([yshift=-2em]ft31.west) {...};

}

\visible<3->{
\draw [->,thick] ([yshift=-0.1em]t13.south) -- ([yshift=0.1em]ft11.north);
\draw [->,thick] ([yshift=0.1em]t22.south east) ..controls +(280:3em) and +(north:3em).. ([yshift=0.1em]ft13.north);
\draw [->,thick] ([yshift=-0.1em,xshift=0.2em]t31.south west) ..controls +(south:3em) and +(north:3em).. ([yshift=0.1em,xshift=0.2em]ft14.north west);
\draw [->,thick] ([yshift=0.1em]t52.south west) ..controls +(250:4em) and +(north:4em).. ([yshift=0.1em]ft12.north);


\node [anchor=east,inner sep=1pt] (nulltranslabel) at (t42.south west) {\scriptsize{\textbf{翻空}}};
\draw [->,thick] ([yshift=0.1em]t41.south west) ..controls +(250:1em) and +(north:1em).. (nulltranslabel.north);
}

}
\end{scope}

\begin{scope}

\visible<3->{
\node [anchor=north west] (label1) at (ft11.south west) {\small{选择最佳单词翻译，调整词序，得到完美的结果}};
}

\visible<4->{
\draw[decorate,thick,decoration={brace,amplitude=5pt,mirror}] ([yshift=8em,xshift=-0.5em]t13.south west) -- ([xshift=-0.5em]t13.south west) node [pos=0.5,left,xshift=-0.5em,yshift=0.5em] (label2) {\footnotesize{\textbf{学习到的}}};
\node [anchor=north west] (label2part2) at ([yshift=0.3em]label2.south west) {\footnotesize{\textbf{单词翻译}}};
}

\visible<4->{
\draw[decorate,thick,decoration={brace,amplitude=5pt,mirror}] ([yshift=-0.2em,xshift=-0.5em]t13.south west) -- ([yshift=-5em,xshift=-0.5em]t13.south west) node [pos=0.5,left,xshift=-0.5em,yshift=0.5em] (label3) {\footnotesize{\textbf{运用知识}}};
\node [anchor=north west] (label3part2) at ([yshift=0.3em]label3.south west) {\footnotesize{\textbf{生成译文}}};
}

\invisible{
\node [anchor=east] (label4) at ([yshift=0.4em]ft11.west) {\scriptsize{翻译就是一条}};
\node [anchor=north west] (label4part2) at ([yshift=0.5em]label4.south west) {\scriptsize{译文选择路径}};

\node [anchor=east] (label5) at ([yshift=0.4em]ft21.west) {\scriptsize{不同的译文对}};
\node [anchor=north west] (label5part2) at ([yshift=0.5em]label5.south west) {\scriptsize{应不同的路径}};

\node [anchor=east] (label6) at ([yshift=0.4em]ft31.west) {\scriptsize{单词翻译的译}};
\node [anchor=north west] (label6part2) at ([yshift=0.5em]label6.south west) {\scriptsize{序也可能不同}};

\node [anchor=east] (label7) at ([yshift=0.4em]ft41.west) {\scriptsize{可能的翻译路}};
\node [anchor=north west] (label7part2) at ([yshift=0.5em]label7.south west) {\scriptsize{径非常多}};
}

\end{scope}

\begin{scope}

\invisible{
\node [anchor=west] (score1) at ([xshift=1.5em]ft14.east) {\footnotesize{P=0.042}};
\node [anchor=west] (score2) at ([xshift=1.5em]ft24.east) {\footnotesize{P=0.006}};
\node [anchor=west] (score3) at ([xshift=1.5em]ft34.east) {\footnotesize{P=0.003}};
\node [anchor=south] (scorelabel) at (score1.north) {\scriptsize{\textbf{\alert{模型得分}}}};
\node [anchor=north] (scorelabel2) at (score3.south) {\scriptsize{\textbf{选择得分}}};
\node [anchor=north west] (scorelabel2part2) at ([xshift=-0.5em,yshift=0.5em]scorelabel2.south west) {\scriptsize{\textbf{最高的译文}}};
\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.3em]score1.east) {\scriptsize{{\color{ugreen} \textbf{ok}}}};
}

\end{scope}

\begin{scope}

\invisible{
\draw [->,ultra thick,ublue,line width=2pt,opacity=0.7] ([xshift=-0.5em]t13.west) -- ([xshift=0.8em]t13.east) -- ([xshift=-0.2em]t21.west) -- ([xshift=0.8em]t21.east) -- ([xshift=-0.2em]t31.west) -- ([xshift=0.8em]t31.east) -- ([xshift=-0.2em]t41.west) -- ([xshift=0.8em]t41.east) -- ([xshift=-0.2em]t51.west) -- ([xshift=1.2em]t51.east);

\draw [->,ultra thick,red,line width=2pt,opacity=0.7] ([xshift=-0.5em]t13.west) -- ([xshift=0.8em]t13.east) -- ([xshift=-0.2em]t22.west) -- ([xshift=0.8em]t22.east) -- ([xshift=-0.2em]t31.west) -- ([xshift=0.8em]t31.east) -- ([xshift=-0.2em]t41.west) -- ([xshift=0.8em]t41.east) -- ([xshift=-0.2em]t52.west) -- ([xshift=1.2em]t52.east);
}

\end{scope}

\end{tikzpicture}
\end{flushright}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 流程示例 - 机器翻译
\begin{frame}{机器翻译系统是如何进行翻译的？}

\vspace{-0.5em}


\begin{flushright}
\begin{tikzpicture}

\begin{scope}

\node [anchor=west] (s1) at (0,0) {\textbf{我}};
\node [anchor=west] (s2) at ([xshift=2em]s1.east) {\textbf{对}};
\node [anchor=west] (s3) at ([xshift=2em]s2.east) {\textbf{你}};
\node [anchor=west] (s4) at ([xshift=2em]s3.east) {\textbf{表示}};
\node [anchor=west] (s5) at ([xshift=2em]s4.east) {\textbf{满意}};

\node [anchor=south west] (sentlabel) at ([yshift=-0.5em]s1.north west) {\scriptsize{\textbf{\alert{待翻译句子(已经分词):}}}};

\draw [->,very thick,ublue] (s1.south) -- ([yshift=-0.7em]s1.south);
\draw [->,very thick,ublue] (s2.south) -- ([yshift=-0.7em]s2.south);
\draw [->,very thick,ublue] (s3.south) -- ([yshift=-0.7em]s3.south);
\draw [->,very thick,ublue] (s4.south) -- ([yshift=-0.7em]s4.south);
\draw [->,very thick,ublue] (s5.south) -- ([yshift=-0.7em]s5.south);

{\small
\node [anchor=north,inner sep=2pt,fill=red!20,minimum height=1.5em,minimum width=2.5em] (t11) at ([yshift=-1em]s1.south) {I};
\node [anchor=north,inner sep=2pt,fill=red!20,minimum height=1.5em,minimum width=2.5em] (t12) at ([yshift=-0.2em]t11.south) {me};
\node [anchor=north,inner sep=2pt,fill=red!20,minimum height=1.5em,minimum width=2.5em] (t13) at ([yshift=-0.2em]t12.south) {I'm};
\node [anchor=north west,inner sep=1pt,fill=black] (tl11) at (t11.north west) {\tiny{{\color{white} \textbf{1}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (tl12) at (t12.north west) {\tiny{{\color{white} \textbf{1}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (tl13) at (t13.north west) {\tiny{{\color{white} \textbf{1}}}};

\node [anchor=north,inner sep=2pt,fill=green!20,minimum height=1.5em,minimum width=2.5em] (t21) at ([yshift=-1em]s2.south) {to};
\node [anchor=north,inner sep=2pt,fill=green!20,minimum height=1.5em,minimum width=2.5em] (t22) at ([yshift=-0.2em]t21.south) {with};
\node [anchor=north,inner sep=2pt,fill=green!20,minimum height=1.5em,minimum width=2.5em] (t23) at ([yshift=-0.2em]t22.south) {for};
\node [anchor=north west,inner sep=1pt,fill=black] (tl21) at (t21.north west) {\tiny{{\color{white} \textbf{2}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (tl22) at (t22.north west) {\tiny{{\color{white} \textbf{2}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (tl23) at (t23.north west) {\tiny{{\color{white} \textbf{2}}}};

\node [anchor=north,inner sep=2pt,fill=blue!20,minimum height=1.5em,minimum width=2.5em] (t31) at ([yshift=-1em]s3.south) {you};
\node [anchor=north west,inner sep=1pt,fill=black] (tl31) at (t31.north west) {\tiny{{\color{white} \textbf{3}}}};

\node [anchor=north,inner sep=2pt,fill=orange!20,minimum height=1.5em,minimum width=3em] (t41) at ([yshift=-1em]s4.south) {$\phi$};
\node [anchor=north,inner sep=2pt,fill=orange!20,minimum height=1.5em,minimum width=3em] (t42) at ([yshift=-0.2em]t41.south) {show};
\node [anchor=north west,inner sep=1pt,fill=black] (tl41) at (t41.north west) {\tiny{{\color{white} \textbf{4}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (tl42) at (t42.north west) {\tiny{{\color{white} \textbf{4}}}};

\node [anchor=north,inner sep=2pt,fill=purple!20,minimum height=1.5em,minimum width=4.5em] (t51) at ([yshift=-1em]s5.south) {satisfy};
\node [anchor=north,inner sep=2pt,fill=purple!20,minimum height=1.5em,minimum width=4.5em] (t52) at ([yshift=-0.2em]t51.south) {satisfied};
\node [anchor=north,inner sep=2pt,fill=purple!20,minimum height=1.5em,minimum width=4.5em] (t53) at ([yshift=-0.2em]t52.south) {satisfies};
\node [anchor=north west,inner sep=1pt,fill=black] (tl51) at (t51.north west) {\tiny{{\color{white} \textbf{5}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (tl52) at (t52.north west) {\tiny{{\color{white} \textbf{5}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (tl53) at (t53.north west) {\tiny{{\color{white} \textbf{5}}}};

}

{\tiny

\visible<5->{
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt11) at (t11.east) {{\color{white} \textbf{P=.4}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt12) at (t12.east) {{\color{white} \textbf{P=.2}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt13) at (t13.east) {{\color{white} \textbf{P=.4}}};

\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt21) at (t21.east) {{\color{white} \textbf{P=.4}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt22) at (t22.east) {{\color{white} \textbf{P=.3}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt23) at (t23.east) {{\color{white} \textbf{P=.3}}};

\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt31) at (t31.east) {{\color{white} \textbf{P=1}}};

\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt41) at (t41.east) {{\color{white} \textbf{P=.5}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt42) at (t42.east) {{\color{white} \textbf{P=.5}}};

\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt51) at (t51.east) {{\color{white} \textbf{P=.5}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt52) at (t52.east) {{\color{white} \textbf{P=.4}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.55em,fill=black] (pt53) at (t53.east) {{\color{white} \textbf{P=.1}}};
}

}

\end{scope}

\begin{scope}
{\small

\node [anchor=west,inner sep=2pt,fill=red!20,minimum height=1.5em,minimum width=2.5em] (ft11) at ([yshift=-1.2in]t11.west) {I'm};
\node [anchor=center,inner sep=2pt,fill=purple!20,minimum height=1.5em,minimum width=5em] (ft12) at ([xshift=5.0em]ft11.center) {satisfied};
\node [anchor=center,inner sep=2pt,fill=green!20,minimum height=1.5em,minimum width=2.5em] (ft13) at ([xshift=5.0em]ft12.center) {with};
\node [anchor=center,inner sep=2pt,fill=blue!20,minimum height=1.5em,minimum width=2.5em] (ft14) at ([xshift=4.0em]ft13.center) {you};

\visible<2->{
\node [anchor=west,inner sep=2pt,fill=red!20,minimum height=1.5em,minimum width=2.5em] (ft21) at ([yshift=-2em]ft11.west) {I'm};
\node [anchor=center,inner sep=2pt,fill=purple!20,minimum height=1.5em,minimum width=5em] (ft22) at ([xshift=5.0em]ft21.center) {satisfy};
\node [anchor=center,inner sep=2pt,fill=green!20,minimum height=1.5em,minimum width=2.5em] (ft23) at ([xshift=5.0em]ft22.center) {to};
\node [anchor=center,inner sep=2pt,fill=blue!20,minimum height=1.5em,minimum width=2.5em] (ft24) at ([xshift=4.0em]ft23.center) {you};
}

\visible<3->{
\node [anchor=west,inner sep=2pt,fill=red!20,minimum height=1.5em,minimum width=2.5em] (ft31) at ([yshift=-2em]ft21.west) {I'm};
\node [anchor=center,inner sep=2pt,fill=purple!20,minimum height=1.5em,minimum width=5em] (ft32) at ([xshift=5.0em]ft31.center) {satisfy};
\node [anchor=center,inner sep=2pt,fill=blue!20,minimum height=1.5em,minimum width=2.5em] (ft33) at ([xshift=5.0em]ft32.center) {you};
\node [anchor=center,inner sep=2pt,fill=green!20,minimum height=1.5em,minimum width=2.5em] (ft34) at ([xshift=4.0em]ft33.center) {to};
}

\node [anchor=north west,inner sep=1pt,fill=black] (ftl11) at (ft11.north west) {\tiny{{\color{white} \textbf{1}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (ftl12) at (ft12.north west) {\tiny{{\color{white} \textbf{5}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (ftl13) at (ft13.north west) {\tiny{{\color{white} \textbf{2}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (ftl14) at (ft14.north west) {\tiny{{\color{white} \textbf{3}}}};

\visible<2->{
\node [anchor=north west,inner sep=1pt,fill=black] (ftl21) at (ft21.north west) {\tiny{{\color{white} \textbf{1}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (ftl22) at (ft22.north west) {\tiny{{\color{white} \textbf{5}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (ftl23) at (ft23.north west) {\tiny{{\color{white} \textbf{2}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (ftl24) at (ft24.north west) {\tiny{{\color{white} \textbf{3}}}};
}

\visible<3->{
\node [anchor=north west,inner sep=1pt,fill=black] (ftl31) at (ft31.north west) {\tiny{{\color{white} \textbf{1}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (ftl32) at (ft32.north west) {\tiny{{\color{white} \textbf{5}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (ftl33) at (ft33.north west) {\tiny{{\color{white} \textbf{3}}}};
\node [anchor=north west,inner sep=1pt,fill=black] (ftl34) at (ft34.north west) {\tiny{{\color{white} \textbf{2}}}};
}

{\tiny

\visible<5->{
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft11) at (ft11.east) {{\color{white} \textbf{P=.4}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft12) at (ft12.east) {{\color{white} \textbf{P=.4}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft13) at (ft13.east) {{\color{white} \textbf{P=.3}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft14) at (ft14.east) {{\color{white} \textbf{P=1}}};

\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft21) at (ft21.east) {{\color{white} \textbf{P=.4}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft22) at (ft22.east) {{\color{white} \textbf{P=.1}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft23) at (ft23.east) {{\color{white} \textbf{P=.4}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft24) at (ft24.east) {{\color{white} \textbf{P=1}}};

\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft31) at (ft31.east) {{\color{white} \textbf{P=.4}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft32) at (ft32.east) {{\color{white} \textbf{P=.1}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft33) at (ft33.east) {{\color{white} \textbf{P=1}}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=2.5em,fill=black] (pft34) at (ft34.east) {{\color{white} \textbf{P=.4}}};
}

}

\begin{pgfonlayer}{background}
\node[rectangle,draw=ublue,red,inner sep=0.1em,fill=white] [fit = (ft11) (pft14)] (trans1) {};
\visible<2->{
\node[rectangle,draw=ublue,ublue,inner sep=0.1em,fill=white] [fit = (ft21) (pft24)] (trans1) {};
}
\visible<3->{
\node[rectangle,draw=ublue,ublue,inner sep=0.1em,fill=white] [fit = (ft31) (pft34)] (trans1) {};
}
\end{pgfonlayer}

\visible<4->{
\node [anchor=west,inner sep=2pt,minimum height=1.5em,minimum width=2.5em] (ft41) at ([yshift=-2em]ft31.west) {...};
}

\visible<5->{
\node [anchor=west,inner sep=2pt,minimum height=1.5em,minimum width=2.5em] (ft42) at ([yshift=-2em]ft32.west) {\scriptsize{\textbf{所有翻译单元都是概率化的}}};
\node [anchor=west,inner sep=1pt,fill=black] (ft43) at (ft42.east) {{\color{white} \tiny{\textbf{P=概率}}}};
}

\visible<1>{
\draw [->,thick] ([yshift=-0.1em]t13.south) -- ([yshift=0.1em]ft11.north);
\draw [->,thick] ([yshift=0.1em]t22.south east) ..controls +(280:3em) and +(north:3em).. ([yshift=0.1em]ft13.north);
\draw [->,thick] ([yshift=-0.1em,xshift=0.2em]t31.south west) ..controls +(south:3em) and +(north:3em).. ([yshift=0.1em,xshift=0.2em]ft14.north west);
\draw [->,thick] ([yshift=0.1em]t52.south west) ..controls +(250:4em) and +(north:4em).. ([yshift=0.1em]ft12.north);


\node [anchor=east,inner sep=1pt] (nulltranslabel) at (t42.south west) {\scriptsize{\textbf{翻空}}};
\draw [->,thick] ([yshift=0.1em]t41.south west) ..controls +(250:1em) and +(north:1em).. (nulltranslabel.north);
}

}
\end{scope}

\begin{scope}

\invisible{
\node [anchor=north west] (label1) at (ft11.south west) {\small{选择最佳的译文，并调整词序，得到完美的结果}};
}

\visible<8->{
\draw[decorate,thick,decoration={brace,amplitude=5pt,mirror}] ([yshift=8em,xshift=-0.5em]t13.south west) -- ([xshift=-0.5em]t13.south west) node [pos=0.5,left,xshift=-0.5em,yshift=2.0em] (label2) {\footnotesize{\textbf{从双语数}}};
\node [anchor=north west] (label2part2) at ([yshift=0.3em]label2.south west) {\footnotesize{\textbf{据中自动}}};
\node [anchor=north west] (label2part3) at ([yshift=0.3em]label2part2.south west) {\footnotesize{\textbf{学习词典}}};
\node [anchor=north west] (label2part4) at ([yshift=0.3em]label2part3.south west) {\footnotesize{\textbf{(训练)}}};
}

\visible<8->{
\draw[decorate,thick,decoration={brace,amplitude=5pt,mirror}] ([yshift=-0.2em,xshift=-0.5em]t13.south west) -- ([yshift=-9.5em,xshift=-0.5em]t13.south west) node [pos=0.5,left,xshift=-0.5em,yshift=2.0em] (label3) {\footnotesize{\textbf{利用概率}}};
\node [anchor=north west] (label3part2) at ([yshift=0.3em]label3.south west) {\footnotesize{\textbf{化的词典}}};
\node [anchor=north west] (label3part3) at ([yshift=0.3em]label3part2.south west) {\footnotesize{\textbf{进行翻译}}};
\node [anchor=north west] (label3part4) at ([yshift=0.3em]label3part3.south west) {\footnotesize{\textbf{(解码)}}};
}

\visible<1-7>{
\node [anchor=east] (label4) at ([yshift=0.4em]ft11.west) {\scriptsize{翻译就是一条}};
\node [anchor=north west] (label4part2) at ([yshift=0.7em]label4.south west) {\scriptsize{译文选择路径}};
}

\visible<2-7>{
\node [anchor=east] (label5) at ([yshift=0.4em]ft21.west) {\scriptsize{不同的译文对}};
\node [anchor=north west] (label5part2) at ([yshift=0.7em]label5.south west) {\scriptsize{应不同的路径}};
}

\visible<3-7>{
\node [anchor=east] (label6) at ([yshift=0.4em]ft31.west) {\scriptsize{单词翻译的词}};
\node [anchor=north west] (label6part2) at ([yshift=0.7em]label6.south west) {\scriptsize{序也可能不同}};
}

\visible<4-7>{
\node [anchor=east] (label7) at ([yshift=0.4em]ft41.west) {\scriptsize{可能的翻译路}};
\node [anchor=north west] (label7part2) at ([yshift=0.7em]label7.south west) {\scriptsize{径非常多}};
}

\end{scope}

\begin{scope}

\visible<6->{
\node [anchor=west] (score1) at ([xshift=1.5em]ft14.east) {\footnotesize{P=0.042}};
\node [anchor=west] (score2) at ([xshift=1.5em]ft24.east) {\footnotesize{P=0.006}};
\node [anchor=west] (score3) at ([xshift=1.5em]ft34.east) {\footnotesize{P=0.003}};
\node [anchor=south] (scorelabel) at (score1.north) {\scriptsize{\textbf{\alert{都赋予一个模型得分}}}};
\node [anchor=south] (scorelabel2) at ([yshift=-0.5em]scorelabel.north) {\scriptsize{\textbf{\alert{系统给每个译文}}}};
}
\visible<7->{
\node [anchor=north] (scorelabel2) at (score3.south) {\scriptsize{\textbf{选择得分}}};
\node [anchor=north west] (scorelabel2part2) at ([xshift=-0.5em,yshift=0.5em]scorelabel2.south west) {\scriptsize{\textbf{最高的译文}}};
\node [anchor=center,draw=ublue,circle,thick,fill=white,inner sep=1pt,circular drop shadow={shadow xshift=0.05em,shadow yshift=-0.05em}] (head1) at ([xshift=0.3em]score1.east) {\scriptsize{{\color{ugreen} \textbf{ok}}}};
}

\end{scope}

\begin{scope}

\visible<2->{
\draw [->,ultra thick,ublue,line width=2pt,opacity=0.7] ([xshift=-0.5em]t13.west) -- ([xshift=0.8em]t13.east) -- ([xshift=-0.2em]t21.west) -- ([xshift=0.8em]t21.east) -- ([xshift=-0.2em]t31.west) -- ([xshift=0.8em]t31.east) -- ([xshift=-0.2em]t41.west) -- ([xshift=0.8em]t41.east) -- ([xshift=-0.2em]t51.west) -- ([xshift=1.2em]t51.east);
}

\draw [->,ultra thick,red,line width=2pt,opacity=0.7] ([xshift=-0.5em]t13.west) -- ([xshift=0.8em]t13.east) -- ([xshift=-0.2em]t22.west) -- ([xshift=0.8em]t22.east) -- ([xshift=-0.2em]t31.west) -- ([xshift=0.8em]t31.east) -- ([xshift=-0.2em]t41.west) -- ([xshift=0.8em]t41.east) -- ([xshift=-0.2em]t52.west) -- ([xshift=1.2em]t52.east);

\end{scope}

\end{tikzpicture}
\end{flushright}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
\subsection{实例：构建一个简易机器翻译系统}

%%%------------------------------------------------------------------------------------------------------------
%%% 简易机器翻译系统 - step 1 learning word translation probablities
\begin{frame}{实现一个简单的机器翻译系统：学习单词翻译概率}
\label{wordtranslationprob}

\begin{itemize}
\item 构建一个简单的机器翻译系统
    \begin{enumerate}
    \item 模型学习 - 从双语平行数据中学习单词翻译知识
    \item<2-> 解码 - 利用单词翻译知识，对新的句子进行翻译
    \end{enumerate}

\begin{tikzpicture}

{\scriptsize
\node [anchor=north west,inner sep=1pt] (entry1) at (0,0) {\tiny{\textbf{1:} 这 是 数据 $\leftrightarrow$ This is data}};
\node [anchor=north west,inner sep=1pt] (entry2) at ([yshift=0.1em]entry1.south west) {\tiny{\textbf{2:} 小心 ！$\leftrightarrow$ Look out !}};
\node [anchor=north west,inner sep=1pt] (entry3) at ([yshift=0.1em]entry2.south west) {\tiny{\textbf{3:} 你 是 谁 $\leftrightarrow$ Who are you}};
\node [anchor=north west,inner sep=2pt] (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,minimum height=1.6cm] [fit = (entry1) (entry2) (entry3) (entry4) (corpuslabel)] (corpus) {};
\end{pgfonlayer}
}

\node [anchor=west,ugreen] (P) at ([xshift=4em,yshift=-0.7em]corpus.east){P($t|s$)};
\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,minimum height=1.6cm] [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{模型学习}}};

\visible<2->{
\draw [->,very thick,ublue] ([xshift=0.4em]model.east) -- ([xshift=3.4em]model.east)  node [inner sep=0pt,pos=0.5, above,yshift=0.3em] (decodingarrow) {\alert{\scriptsize{穷举\&计算}}};

{\scriptsize
\node [anchor=north west,inner sep=2pt] (sentlabel) at ([xshift=5.5em,yshift=-0.3em]model.north east) {{\color{ublue} \textbf{机器翻译引擎}}};
\node [anchor=north west] (sent) at ([yshift=-0.5em]sentlabel.south west) {\textbf{对任意句子}};
\node [anchor=north west] (sentpart2) at ([yshift=0.3em]sent.south west) {\textbf{进行翻译}};
}
}

\begin{pgfonlayer}{background}
\visible<2->{
\node[rectangle,draw=ublue,thick,inner sep=0.2em,fill=white,drop shadow,minimum height=1.6cm] [fit = (sentlabel) (sent) (sentpart2)] (segsystem) {};
}
\end{pgfonlayer}


\visible<3->{
\node[rectangle,fill=white,fill opacity=0.85,inner sep=0pt] [fit = (segsystem) (decodingarrow)] (segsystem2) {};
}

\end{tikzpicture}

\item<3-> \textbf{步骤1}：构建单词翻译表 - 翻译词典\\
          \small{对于任意的源语言单词$x$，要获得它所有可能的译文$Y$。给定一个互译句对$(s,t)$，对于$y \in Y$，定义$\textrm{P}(x \leftrightarrow y; s, t)$表示$x$和$y$在$(x,y)$中互译的概率，我们用$x$和$y$的联合概率表示：

          \vspace{-2.0em}

          \begin{eqnarray}
          \textrm{P}(x \leftrightarrow y; s,t) & \equiv & \textrm{P}(x,y;s,t) \nonumber \\
                                          & = & \frac{c(x,y;s,t)}{\sum_{x',y'} c(x',y';s,t)} \nonumber
          \end{eqnarray}

          \vspace{-0.5em}

          $c(x,y;s,t)$表示$(x,y)$在$(s,t)$中共现的次数; $\sum_{x',y'} c(x',y';s,t)$表示$(s,t)$中任意源/译文单词共现的总次数
          }

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 简易机器翻译系统 - step 1 learning word translation probablities - for single sentence
\begin{frame}{实现一个简单的机器翻译系统：学习单词翻译概率(2)}
\vspace{-1em}
\begin{eqnarray}
\textrm{P}(x,y;s,t) & = & \frac{c(x,y;s,t)}{\sum_{x',y'} c(x',y';s,t)} \nonumber
\end{eqnarray}

\vspace{-0.5em}

\begin{flushleft}
\begin{tikzpicture}

\node [anchor=west] (s) at (0,0) {$s=$};
\node [anchor=center] (sw1) at ([xshift=1em]s.east) {机器};
\visible<1,4->{
\node [anchor=center] (sw2) at ([xshift=1.3em]sw1.east) {翻译};
}
\node [anchor=center] (sw3) at ([xshift=5.5em]sw2.east) {就 是 用 计算机 来 进行};
\visible<1-3,6->{
\node [anchor=center] (sw4) at ([xshift=1.0em]sw3.east) {翻译};
}

\node [anchor=north west] (t) at (s.south west) {$t=$};
\node [anchor=center] (tw1) at ([xshift=1.8em]t.east) {machine};
\visible<1,3,5->{
\node [anchor=center] (tw2) at ([xshift=2.2em]tw1.east) {translation};
}
\node [anchor=center] (tw3) at ([xshift=1.4em,yshift=-0.1em]tw2.east) {is just};
\visible<1,2,4,6->{
\node [anchor=center] (tw4) at ([xshift=2.3em,yshift=0.1em]tw3.east) {translation};
}
\node [anchor=center] (tw5) at ([xshift=2.6em,yshift=-0.1em]tw4.east) {by computer};

\visible<2-3>{
\node [anchor=center,red] (sw2highlight) at ([xshift=1.3em]sw1.east) {\underline{翻译}};
}
\visible<4-5>{
\node [anchor=center,red] (sw4highlight) at ([xshift=1.0em]sw3.east) {\underline{翻译}};
}
\visible<2,4>{
\node [anchor=center,red] (tw2highlight) at ([xshift=2.2em]tw1.east) {\underline{translation}};
}
\visible<3,5>{
\node [anchor=center,red] (tw4highlight) at ([xshift=2.3em,yshift=0.1em]tw3.east) {\underline{translation}};
}

\end{tikzpicture}
\end{flushleft}

\vspace{-1.0em}

\begin{itemize}

\item $c(\textrm{'翻译'},\textrm{'translation'};s,t)=\only<1>{?}\visible<2->{1}\visible<3->{+1}\visible<4->{+1}\visible<5->{+1=4}$
\item<6-> $\sum_{x',y'} c(x',y';s,t)= \textrm{使劲数...}  = 63\visible<7->{ = 9 \times 7 = |s| \times |t|}$
    \vspace{0.3em}
    \begin{itemize}
    \item<7-> $|\cdot|$表示句子长度
    \end{itemize}
    \vspace{0.3em}
\item<8-> '翻译'和'translation'的互译概率为
\begin{displaymath}
\textrm{P}(\textrm{'翻译'},\textrm{'translation'};s,t) = 4/63
\end{displaymath}
\vspace{-0.5em}
类似的
\vspace{-0.5em}
\begin{eqnarray}
\textrm{P}(\textrm{'机器'},\textrm{'translation'};s,t) & = & 2/63 \nonumber \\
\textrm{P}(\textrm{'机器'},\textrm{'look'};s,t) & = & 0/63 \nonumber
\end{eqnarray}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 简易机器翻译系统 - step 1 learning word translation probablities - for several sentences
\begin{frame}{实现一个简单的机器翻译系统：学习单词翻译概率(3)}

\begin{itemize}

\item 很多时候，我们有多个互译句对$(s^{[1]},t^{[1]}),...,(s^{[n]},t^{[n]})$，称之为\alert{双语平行数据(语料)}。翻译概率可以被定义为

\vspace{-1em}

\begin{eqnarray}
\textrm{P}(x,y) & = & \frac{\sum_{i=1}^{n}c(x,y;s^{[i]},t^{[i]})}{\sum_{i=1}^{n} \sum_{x',y'} c(x',y';s^{[i]},t^{[i]})} \nonumber
\end{eqnarray}

\item<2-> 说白了就是计算$(x,y)$的频次时，在每个句子上累加

\begin{flushleft}
\begin{tikzpicture}

\node [anchor=west] (s1) at (0,0) {$s_1=$ 机器 翻译 就 是 用 计算机 进行 翻译};
\node [anchor=north west] (t1) at ([yshift=0.4em]s1.south west) {$t_1=$ Machine translation is just translation by computer};

\node [anchor=north west] (s2) at (t1.south west) {$s_2=$ 那 人工 翻译 呢 ?};
\node [anchor=north west] (t2) at ([yshift=0.4em]s2.south west) {$t_2=$ so , what is human translation ?};

\end{tikzpicture}
\end{flushleft}

\vspace{-1.5em}

{\footnotesize
\begin{eqnarray}
&   & \textrm{P}(\textrm{'翻译'},\textrm{'translation'}) \nonumber \\
& = & \frac{c(\textrm{'翻译'},\textrm{'translation'};s^{[1]},t^{[1]})+c(\textrm{'翻译'},\textrm{'translation'};s^{[2]},t^{[2]})}{\sum_{x',y'} c(x',y';s^{[1]},t^{[1]}) + \sum_{x',y'} c(x',y';s^{[2]},t^{[2]})} \nonumber \\
\visible<3->{& = & \frac{4 + 1}{|s^{[1]}| \times |t^{[1]}| + |s^{[2]}| \times |t^{[2]}|} = \frac{4 + 1}{9 \times 7 + 5 \times 7} = \frac{5}{102}} \nonumber
\end{eqnarray}
}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 简易机器翻译系统 - step 2 modeling sentence translaiton probability
\begin{frame}{实现一个简单的机器翻译系统：句子级翻译模型}

\begin{center}
\begin{tikzpicture}

{\scriptsize
\node [anchor=north west,inner sep=1pt] (entry1) at (0,0) {\tiny{\textbf{1:} 这 是 数据 $\leftrightarrow$ This is data}};
\node [anchor=north west,inner sep=1pt] (entry2) at ([yshift=0.1em]entry1.south west) {\tiny{\textbf{2:} 小心 ！$\leftrightarrow$ Look out !}};
\node [anchor=north west,inner sep=1pt] (entry3) at ([yshift=0.1em]entry2.south west) {\tiny{\textbf{3:} 你 是 谁 $\leftrightarrow$ Who are you}};
\node [anchor=north west,inner sep=2pt] (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,minimum height=1.6cm] [fit = (entry1) (entry2) (entry3) (entry4) (corpuslabel)] (corpus) {};
\end{pgfonlayer}
}

\node [anchor=west,ugreen] (P) at ([xshift=4em,yshift=-0.7em]corpus.east){P($t|s$)};
\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,minimum height=1.6cm] [fit = (P) (modellabel)] (model) {};
\end{pgfonlayer}

\draw [->,very thick,ublue] ([xshift=0.2em]corpus.east) -- ([xshift=3.0em]corpus.east)  node [inner sep=0pt,pos=0.5,above,yshift=0.3em] (trainingarrow) {\alert{\scriptsize{模型学习}}};

\draw [->,very thick,ublue] ([xshift=0.4em]model.east) -- ([xshift=3.4em]model.east)  node [inner sep=0pt,pos=0.5,above,yshift=0.3em] (decodingarrow) {\alert{\scriptsize{穷举\&计算}}};

{\scriptsize
\node [anchor=north west,inner sep=2pt] (sentlabel) at ([xshift=5.5em,yshift=-0.3em]model.north east) {{\color{ublue} \textbf{机器翻译引擎}}};
\node [anchor=north west] (sent) at ([yshift=-0.5em]sentlabel.south west) {\textbf{对任意句子}};
\node [anchor=north west] (sentpart2) at ([yshift=0.3em]sent.south west) {\textbf{进行翻译}};
}

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

\node[rectangle,fill=white,fill opacity=0.85,inner sep=0pt] [fit = (segsystem) (decodingarrow)] (segsystem2) {};
\node[rectangle,fill=white,fill opacity=0.85,inner sep=0pt] [fit = (corpus) (trainingarrow)] (corpus2) {};

\end{tikzpicture}
\end{center}

\begin{itemize}
\item \textbf{步骤2}: 对任意的句对$(s,t)$计算句子级翻译概率$\textrm{P}(t|s)$ \\

      \vspace{0.5em}
      \visible<2->{
      用一种比较简单的思路：定义$(s,t)$上的一种分数$g(s,t)$
      \begin{itemize}
      \item $g(s,t)$的值越大翻译质量越好
      \item $g(s,t)$的值越小翻译质量越差
      \end{itemize}
      }

      \vspace{0.5em}

      \visible<3->{
      于是，我们进一步定义

      \begin{displaymath}
      \textrm{P}(t|s) = \frac{g(s,t)}{\sum_{t'}g(s,t')}
      \end{displaymath}

      实际上就是对$g(s,t)$在所有可能的译文集合上做归一化，使其具有概率意义
      }

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 简易机器翻译系统 - step 2 modeling sentence translaiton probability - word alignment
\begin{frame}{实现一个简单的机器翻译系统：句子级翻译模型(2)}

\vspace{0.5em}

\begin{spacing}{1.1}
\begin{itemize}

\item 两个问题
    \begin{enumerate}
    \item 如何计算$g(s,t)$ \visible<2->{- 最关键的建模问题，马上开始}
    \item 如何计算$\sum_{t'} g(s,t')$ \visible<2->{- 实际上\alert{不用计算}，后面再说}
    \end{enumerate}

\item<3-> \textbf{对$g(s,t)$建模: }根据本章第一页的假设，$s$与$t$之间存在一种单词间的对应，我们称之为\alert{词对齐}关系

\begin{center}
\begin{tikzpicture}

\begin{scope}
\node [anchor=west] (s1) at (0,0) {我\footnotesize{$_1$}};
\node [anchor=west] (s2) at ([xshift=0.5em]s1.east) {对\footnotesize{$_2$}};
\node [anchor=west] (s3) at ([xshift=0.5em]s2.east) {你\footnotesize{$_3$}};
\node [anchor=west] (s4) at ([xshift=0.5em]s3.east) {感到\footnotesize{$_4$}};
\node [anchor=west] (s5) at ([xshift=0.5em]s4.east) {满意\footnotesize{$_5$}};
\node [anchor=east] (s) at (s1.west) {$s=$};
\end{scope}

\begin{scope}[yshift=-3.0em]
\node [anchor=west] (t1) at (0.35em,0) {I\footnotesize{$_1$}};
\node [anchor=west] (t2) at ([xshift=0.3em,yshift=-0.1em]t1.east) {am\footnotesize{$_2$}};
\node [anchor=west] (t3) at ([xshift=0.3em,yshift=0.1em]t2.east) {satisfied\footnotesize{$_3$}};
\node [anchor=west] (t4) at ([xshift=0.3em]t3.east) {with\footnotesize{$_4$}};
\node [anchor=west] (t5) at ([xshift=0.3em,yshift=-0.2em]t4.east) {you\footnotesize{$_5$}};
\node [anchor=east] (t) at ([xshift=-0.3em]t1.west) {$t=$};
\end{scope}


\draw [-,thick,ublue,dashed] (s1.south) -- (t1.north);
\draw [-,thick,ublue,dashed] (s4.south) -- ([yshift=0.3em]t2.north);
\draw [-,thick,ublue,dashed] (s2.south) ..controls +(south:1em) and +(north:1em).. (t4.north);
\draw [-,thick,ublue,dashed] (s3.south) ..controls +(south:0.5em) and +(north:1.5em).. (t5.north);
\draw [-,thick,ublue,dashed] (s5.south) -- (t3.north);

\end{tikzpicture}
\end{center}

每根虚线代表一个\alert{对齐链接}，记为$(j,i)$，意思是源语言的第$j$个单词对应目标语言第$i$个单词，即$s_j$与$t_i$对应。

\item<3-> 所有对齐链接构成集合$A$，对于上例：
      $A=\{(1,1),(2,4),(3,5),(4,2),(5,3)\}$

\end{itemize}
\end{spacing}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 简易机器翻译系统 - step 2 modeling sentence translaiton probability - model score
\begin{frame}{实现一个简单的机器翻译系统：句子级翻译模型(3)}

\begin{itemize}
\item 给定一个句对$(s,t)$，及它们之间的(最优)词对齐$\hat{A}$，可以定义模型得分为：
\begin{displaymath}
g(s,t) \equiv \prod_{(j,i) \in \hat{A}} \textrm{P}(s_j,t_i)
\end{displaymath}
      显然每个单词翻译概率都高，那么整句的模型得分也高

\begin{center}
\begin{tikzpicture}

\begin{scope}
\node [anchor=west] (s1) at (0,0) {我\footnotesize{$_1$}};
\node [anchor=west] (s2) at ([xshift=0.5em]s1.east) {对\footnotesize{$_2$}};
\node [anchor=west] (s3) at ([xshift=0.5em]s2.east) {你\footnotesize{$_3$}};
\node [anchor=west] (s4) at ([xshift=0.5em]s3.east) {感到\footnotesize{$_4$}};
\node [anchor=west] (s5) at ([xshift=0.5em]s4.east) {满意\footnotesize{$_5$}};
\node [anchor=east] (s) at (s1.west) {$s=$};
\end{scope}

\begin{scope}[yshift=-3.0em]
\node [anchor=west] (t1) at (0.35em,0) {I\footnotesize{$_1$}};
\node [anchor=west] (t2) at ([xshift=0.3em,yshift=-0.1em]t1.east) {am\footnotesize{$_2$}};
\node [anchor=west] (t3) at ([xshift=0.3em,yshift=0.1em]t2.east) {satisfied\footnotesize{$_3$}};
\node [anchor=west] (t4) at ([xshift=0.3em]t3.east) {with\footnotesize{$_4$}};
\node [anchor=west] (t5) at ([xshift=0.3em,yshift=-0.2em]t4.east) {you\footnotesize{$_5$}};
\node [anchor=east] (t) at ([xshift=-0.3em]t1.west) {$t=$};
\end{scope}


\draw [-,thick,ublue,dashed] (s1.south) -- (t1.north);
\draw [-,thick,ublue,dashed] (s4.south) -- ([yshift=0.3em]t2.north);
\draw [-,thick,ublue,dashed] (s2.south) ..controls +(south:1em) and +(north:1em).. (t4.north);
\draw [-,thick,ublue,dashed] (s3.south) ..controls +(south:0.5em) and +(north:1.5em).. (t5.north);
\draw [-,thick,ublue,dashed] (s5.south) -- (t3.north);

\end{tikzpicture}
\end{center}

\vspace{-2.5em}

\begin{eqnarray}
g(s,t) & = & \textrm{P}(\textrm{'我','I'}) \times \textrm{P}(\textrm{'对','with'}) \times \textrm{P}(\textrm{'你','you'}) \times \nonumber \\
       &   & \textrm{P}(\textrm{'感到','am'}) \times \textrm{P}(\textrm{'满意','satisfied'}) \nonumber
\end{eqnarray}

\item<2-> \textbf{其它问题}：如果有单词翻译为空怎么办？
    \begin{itemize}
    \item 简单的解决方案是平滑，给予这种翻译一个很小的概率值
    \item 或者在建模中考虑，见后面的IBM模型
    \end{itemize}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 简易机器翻译系统 - step 2 modeling sentence translaiton probability - introducing LM into the model
\begin{frame}{实现一个简单的机器翻译系统：句子级翻译模型(4)}

\begin{itemize}
\item \textbf{但是}，这样设计的$g(s,t)$没有考虑词序的信息。相同译词出现在不同的位置，得分相同 - 无法选择流畅的译文

\vspace{0.5em}

\begin{tabular}{l | l }

& \footnotesize{$\prod\limits_{(j,i) \in \hat{A}} \textrm{P}(s_j,t_i)$} \visible<2->{\alert{\footnotesize{$\times\textrm{P}_{lm}(t)$}}} \\ \hline

\begin{tikzpicture}

\begin{scope}

{\footnotesize
\begin{scope}
\node [anchor=west] (s1) at (0,0) {我\footnotesize{$_1$}};
\node [anchor=west] (s2) at ([xshift=0.5em]s1.east) {对\footnotesize{$_2$}};
\node [anchor=west] (s3) at ([xshift=0.5em]s2.east) {你\footnotesize{$_3$}};
\node [anchor=west] (s4) at ([xshift=0.5em]s3.east) {感到\footnotesize{$_4$}};
\node [anchor=west] (s5) at ([xshift=0.5em]s4.east) {满意\footnotesize{$_5$}};
\node [anchor=east] (s) at (s1.west) {$s=$};
\end{scope}

\begin{scope}[yshift=-2.6em]
\node [anchor=west] (t1) at (0.35em,0) {I\footnotesize{$_1$}};
\node [anchor=west] (t2) at ([xshift=0.3em,yshift=-0.1em]t1.east) {am\footnotesize{$_2$}};
\node [anchor=west] (t3) at ([xshift=0.3em,yshift=0.1em]t2.east) {satisfied\footnotesize{$_3$}};
\node [anchor=west] (t4) at ([xshift=0.3em]t3.east) {with\footnotesize{$_4$}};
\node [anchor=west] (t5) at ([xshift=0.3em,yshift=-0.2em]t4.east) {you\footnotesize{$_5$}};
\node [anchor=east] (t) at ([xshift=-0.3em]t1.west) {$t'=$};
\end{scope}


\draw [-,thick,ublue,dashed] (s1.south) -- (t1.north);
\draw [-,thick,ublue,dashed] (s4.south) -- ([yshift=0.3em]t2.north);
\draw [-,thick,ublue,dashed] (s2.south) ..controls +(south:1em) and +(north:1em).. (t4.north);
\draw [-,thick,ublue,dashed] (s3.south) ..controls +(south:0.5em) and +(north:1.5em).. (t5.north);
\draw [-,thick,ublue,dashed] (s5.south) -- (t3.north);
}

\end{scope}

\end{tikzpicture}

& \tikz{\node[minimum height=3.2em]{\small{0.0023}\only<2->{\alert{\small{$\times$0.0107}}}};} \\

\begin{tikzpicture}

\begin{scope}

{\footnotesize
\begin{scope}
\node [anchor=west] (s1) at (0,0) {我\footnotesize{$_1$}};
\node [anchor=west] (s2) at ([xshift=0.5em]s1.east) {对\footnotesize{$_2$}};
\node [anchor=west] (s3) at ([xshift=0.5em]s2.east) {你\footnotesize{$_3$}};
\node [anchor=west] (s4) at ([xshift=0.5em]s3.east) {感到\footnotesize{$_4$}};
\node [anchor=west] (s5) at ([xshift=0.5em]s4.east) {满意\footnotesize{$_5$}};
\node [anchor=east] (s) at (s1.west) {$s=$};
\end{scope}

\begin{scope}[yshift=-2.6em]
\node [anchor=center] (t1) at ([yshift=-1.6em]s1.south) {I\footnotesize{$_1$}};
\node [anchor=center] (t2) at ([yshift=-1.6em]s2.south) {with\footnotesize{$_2$}};
\node [anchor=center] (t3) at ([yshift=-1.7em]s3.south) {you\footnotesize{$_3$}};
\node [anchor=center] (t4) at ([yshift=-1.7em]s4.south) {am\footnotesize{$_4$}};
\node [anchor=center] (t5) at ([yshift=-1.6em]s5.south) {satisfied\footnotesize{$_5$}};
\node [anchor=center] (t) at ([xshift=-1.3em]t1.west) {$t''=$};
\end{scope}


\draw [-,thick,ublue,dashed] (s1.south) -- (t1.north);
\draw [-,thick,ublue,dashed] (s2.south) -- (t2.north);
\draw [-,thick,ublue,dashed] (s3.south) -- (t3.north);
\draw [-,thick,ublue,dashed] (s4.south) -- (t4.north);
\draw [-,thick,ublue,dashed] (s5.south) -- (t5.north);
}

\end{scope}

\end{tikzpicture}

& \tikz{\node[minimum height=3em]{\small{0.0023}\only<2->{\alert{\small{$\times$0.0009}}}};}

\end{tabular}

\item<2-> \textbf{解决方案}：引入语言模型$\textrm{P}_{lm}(t)$来度量译文的流畅度

$\textrm{P}_{\textrm{2-gram}}(w_1...w_m)=\textrm{P}(w_1) \times \textrm{P}(w_2 | w_1) \times \textrm{P}(w_3 | w_2) ... \times \textrm{P}(w_m | w_{m-1})$

\item<2-> \textbf{最终}

\vspace{-1em}

\begin{displaymath}
g(s,t)=\prod\nolimits_{(j,i) \in \hat{A}} \textrm{P}(s_j,t_i) \times \textrm{P}_{lm}(t)
\end{displaymath}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 简易机器翻译系统 - step 3 decoding - problem definition
\begin{frame}{实现一个简单的机器翻译系统：解码}

\begin{center}
\begin{tikzpicture}

{\scriptsize
\node [anchor=north west,inner sep=1pt] (entry1) at (0,0) {\tiny{\textbf{1:} 这 是 数据 $\leftrightarrow$ This is data}};
\node [anchor=north west,inner sep=1pt] (entry2) at ([yshift=0.1em]entry1.south west) {\tiny{\textbf{2:} 小心 ！$\leftrightarrow$ Look out !}};
\node [anchor=north west,inner sep=1pt] (entry3) at ([yshift=0.1em]entry2.south west) {\tiny{\textbf{3:} 你 是 谁 $\leftrightarrow$ Who are you}};
\node [anchor=north west,inner sep=2pt] (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,minimum height=1.6cm] [fit = (entry1) (entry2) (entry3) (entry4) (corpuslabel)] (corpus) {};
\end{pgfonlayer}
}

\node [anchor=west,ugreen] (P) at ([xshift=4em,yshift=-0.7em]corpus.east){P($t|s$)};
\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,minimum height=1.6cm] [fit = (P) (modellabel)] (model) {};
\end{pgfonlayer}

\draw [->,very thick,ublue] ([xshift=0.2em]corpus.east) -- ([xshift=3.0em]corpus.east)  node [inner sep=0pt,pos=0.5,above,yshift=0.3em] (trainingarrow) {\alert{\scriptsize{模型学习}}};

\draw [->,very thick,ublue] ([xshift=0.4em]model.east) -- ([xshift=3.4em]model.east)  node [inner sep=0pt,pos=0.5,above,yshift=0.3em] (decodingarrow) {\alert{\scriptsize{穷举\&计算}}};

{\scriptsize
\node [anchor=north west,inner sep=2pt] (sentlabel) at ([xshift=5.5em,yshift=-0.3em]model.north east) {{\color{ublue} \textbf{机器翻译引擎}}};
\node [anchor=north west] (sent) at ([yshift=-0.5em]sentlabel.south west) {\textbf{对任意句子}};
\node [anchor=north west] (sentpart2) at ([yshift=0.3em]sent.south west) {\textbf{进行翻译}};
}

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

\node[rectangle,fill=white,fill opacity=0.85,inner sep=0pt] [fit = (corpus) (trainingarrow)] (corpus2) {};

\end{tikzpicture}
\end{center}

\begin{itemize}
\item \textbf{步骤3：解码 - }对任意的$s$，找到翻译概率最大的译文$\hat{t}$
\begin{displaymath}
\hat{t} = \argmax_{t} \textrm{P}(t|s)
\end{displaymath}

这里$\argmax_{a} f(a)$表示找到使$f(a)$达到最大的$a$输出

\item<2-> 现在我们可以对任意的$(s,t)$计算$\textrm{P}(t|s) = \frac{g(s,t)}{\sum_{t'}g(s,t')}$
      \begin{itemize}
      \item 给定$s$，$\sum_{t'}g(s,t')$是个常数(因为$\sum_{t'}g(s,t')$的变量只有$s$)
      \item \textbf{这样，我们得到解码步骤的形式化描述为}
      \end{itemize}


\vspace{-1em}

\begin{eqnarray}
\hat{t} & = & \argmax_{t} \frac{g(s,t)}{\sum_{t'}g(s,t')} \nonumber \\
        & =      & \argmax_{t} g(s,t) \nonumber
\end{eqnarray}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 简易机器翻译系统 - step 3 decoding - implementation
\begin{frame}{实现一个简单的机器翻译系统：解码(2)}
\vspace{0.5em}
\begin{itemize}
\item \textbf{解码的核心问题}是在所有可能的翻译结果中找到使$g(s,t)$达到最大的译文\\
\vspace{-1em}
\begin{minipage}[t]{0.58\linewidth}
\begin{itemize}
\item 若$s$有$m$个词，每个词有$n$个翻译候选 - 共有$n^m$种组合
\vspace{-0.5em}
\item<2-> 词的翻译候选可以任意调序
\vspace{-0.5em}
\item<3-> $s$对应可能的译文至少有$n^m \cdot m!$
\end{itemize}
\end{minipage}
\hfill
\begin{minipage}[t]{0.40\linewidth}
\vspace{-0.5em}
\begin{center}
\begin{tikzpicture}

\node [anchor=west,draw,thick,circle,minimum size=0.3em,inner sep=2.1pt,red] (s1) at ([yshift=-1.5em]sent.south west){\tiny{1}};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,inner sep=2.1pt,ugreen] (s2) at ([xshift=0.4em]s1.east) {\tiny{2}};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,inner sep=2.1pt,orange] (s3) at ([xshift=0.4em]s2.east) {\tiny{3}};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,inner sep=2.6pt,ublue] (s4) at ([xshift=0.4em]s3.east) {.};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,inner sep=1.5pt,purple] (s5) at ([xshift=0.4em]s4.east) {\tiny{$m$}};

\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,red,fill=red] (t1) at ([yshift=-1.7em]s1.center) {{\color{white} \tiny{$n$}}};
\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,ugreen,fill=ugreen] (t2) at ([yshift=-1.7em]s2.center) {{\color{white} \tiny{$n$}}};
\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,orange,fill=orange] (t3) at ([yshift=-1.7em]s3.center) {{\color{white} \tiny{$n$}}};
\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,ublue,fill=ublue] (t4) at ([yshift=-1.7em]s4.center) {{\color{white} \tiny{$n$}}};
\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,purple,fill=purple] (t5) at ([yshift=-1.7em]s5.center) {{\color{white} \tiny{$n$}}};

\visible<2->{
\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,purple,fill=purple] (tt1) at ([yshift=-1.2em]t1.center) {{\color{white} \tiny{$n$}}};
\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,ublue,fill=ublue] (tt2) at ([yshift=-1.2em]t2.center) {{\color{white} \tiny{$n$}}};
\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,orange,fill=orange] (tt3) at ([yshift=-1.2em]t3.center) {{\color{white} \tiny{$n$}}};
\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,ugreen,fill=ugreen] (tt4) at ([yshift=-1.2em]t4.center) {{\color{white} \tiny{$n$}}};
\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,red,fill=red] (tt5) at ([yshift=-1.2em]t5.center) {{\color{white} \tiny{$n$}}};
}

\draw [->,thick] ([yshift=-0.1em]s1.south) -- ([yshift=0.1em]t1.north);
\draw [->,thick] ([yshift=-0.1em]s2.south) -- ([yshift=0.1em]t2.north);
\draw [->,thick] ([yshift=-0.1em]s3.south) -- ([yshift=0.1em]t3.north);
\draw [->,thick] ([yshift=-0.1em]s4.south) -- ([yshift=0.1em]t4.north);
\draw [->,thick] ([yshift=-0.1em]s5.south) -- ([yshift=0.1em]t5.north);

\visible<3->{
\node [anchor=center,rotate=90] (dots) at ([yshift=-1.1em]tt3.center) {\footnotesize{...}};

\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,purple,fill=purple] (ttt1) at ([yshift=-2.2em]tt1.center) {{\color{white} \tiny{$n$}}};
\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,red,fill=red] (ttt2) at ([yshift=-2.2em]tt2.center) {{\color{white} \tiny{$n$}}};
\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,ugreen,fill=ugreen] (ttt3) at ([yshift=-2.2em]tt3.center) {{\color{white} \tiny{$n$}}};
\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,orange,fill=orange] (ttt4) at ([yshift=-2.2em]tt4.center) {{\color{white} \tiny{$n$}}};
\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,ublue,fill=ublue] (ttt5) at ([yshift=-2.2em]tt5.center) {{\color{white} \tiny{$n$}}};

\draw[decorate,thick,decoration={brace,amplitude=5pt,mirror}] ([yshift=-0em,xshift=0.3em]ttt5.south east) -- ([yshift=-0em,xshift=0.3em]t5.north east) node [pos=0.5,right,xshift=0.3em,yshift=0.2em] (label3) {\scriptsize{\textbf{$m!$}}};
}

\end{tikzpicture}
\end{center}
\end{minipage}

\item<4-> 潜在翻译结果数量巨大，无法穷尽，因此我们需要\alert{高效}的搜索算法找到理想的解

\begin{center}

\begin{tabular}{l | l | l}
$m$ & $n$ & $n^m \cdot m!$ \\ \hline
1 & 1 & 1 \\
1 & 10 & 10 \\
2 & 10 & 200 \\
10 & 10 & 36288000000000000 \\
20 & 10 & 2.43290200817664 $\times 10^{38}$ \\
20 & 30 & 8.48300477127188 $\times 10^{47}$ \\
\end{tabular}

\end{center}

\end{itemize}
\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 简易机器翻译系统 - step 3 decoding - algorithm
\begin{frame}{实现一个简单的机器翻译系统：解码(3)}
\label{simpledecodingalgorithm}
我们这里使用一种\alert{贪婪}的解码算法：每轮选择一个源语言单词，利用它的翻译候选扩展译文，保留"最好"的结果，反复进行直到所有源语言单词都被翻译

\vspace{-1.5em}

\begin{flushleft}
\begin{tikzpicture}

{\scriptsize

\node [anchor=north west,inner sep=2pt,align=left] (line1) at (0,0) {\textrm{\textbf{Function} \textsc{WordDecoding}($s$)}};
\node [anchor=north west,inner sep=2pt,align=left] (line2) at ([yshift=-1pt]line1.south west) {\textrm{1: $\pi = $\textsc{GetTransOptions}($s$)}};
\node [anchor=north west,inner sep=2pt,align=left] (line3) at ([yshift=-1pt]line2.south west) {\textrm{2: $best = \phi$}};
\node [anchor=north west,inner sep=2pt,align=left] (line4) at ([yshift=-1pt]line3.south west) {\textrm{3: \textbf{for} $i$ in $[1,m]$ \textbf{do}}};
\node [anchor=north west,inner sep=2pt,align=left] (line5) at ([yshift=-1pt]line4.south west) {\textrm{4: \hspace{1em} $h = \phi$}};
\node [anchor=north west,inner sep=2pt,align=left] (line6) at ([yshift=-1pt]line5.south west) {\textrm{5: \hspace{1em} \textbf{foreach} $j$ in $[1,m]$ \textbf{do}}};
\node [anchor=north west,inner sep=2pt,align=left] (line7) at ([yshift=-1pt]line6.south west) {\textrm{6: \hspace{2em} \textbf{if} $used[j]=$ \textbf{true} \textbf{then}}};
\node [anchor=north west,inner sep=2pt,align=left] (line8) at ([yshift=-1pt]line7.south west) {\textrm{7: \hspace{3em} $h = h \cup \textrm{\textsc{Join}}(best,\pi[j])$}};
\node [anchor=north west,inner sep=2pt,align=left] (line9) at ([yshift=-1pt]line8.south west) {\textrm{8: \hspace{1em} $best = \textrm{\textsc{PruneForTop1}}(h)$}};
\node [anchor=north west,inner sep=2pt,align=left] (line10) at ([yshift=-1pt]line9.south west) {\textrm{9: \hspace{1em} $used[best.j] = \textrm{\textsc{\textbf{true}}}$}};
\node [anchor=north west,inner sep=2pt,align=left] (line11) at ([yshift=-1pt]line10.south west) {\textrm{10: \textbf{return} $best.translatoin$}};

\node [anchor=south west,inner sep=2pt,align=left] (head1) at ([yshift=1pt]line1.north west) {输出: 找的最佳译文};
\node [anchor=south west,inner sep=2pt,align=left] (head2) at ([yshift=1pt]head1.north west) {输入: 源语句子$s=s_1...s_m$};

}

\begin{pgfonlayer}{background}
\node[rectangle,draw=ublue,thick,inner sep=0.2em,fill=white,drop shadow,minimum height=1.6cm] [fit = (head2) (line8) (line11)] (algorithm) {};

%% highlights
%\begin{pgfonlayer}{background}
\visible<2->{
\node[anchor=west,fill=blue!20,minimum height=0.16in,minimum width=1.8in] (line2highlight) at (line2.west) {};
}
\visible<3->{
\node[anchor=west,fill=blue!20,minimum height=0.16in,minimum width=1.8in] (line3highlight) at (line3.west) {};
\node[anchor=west,fill=blue!20,minimum height=0.16in,minimum width=1.8in] (line5highlight) at (line5.west) {};
}
\visible<4->{
\node[anchor=west,fill=blue!20,minimum height=0.16in,minimum width=1.8in] (line8highlight) at (line8.west) {};
}
\visible<5->{
\node[anchor=west,fill=blue!20,minimum height=0.16in,minimum width=1.8in] (line9highlight) at (line9.west) {};
}
\visible<6->{
\node[anchor=west,fill=blue!20,minimum height=0.16in,minimum width=1.8in] (line10highlight) at (line10.west) {};
}
%\end{pgfonlayer}

\end{pgfonlayer}

{\footnotesize

%% remark 1
\begin{scope}
\visible<2->{
\node [anchor=north west,align=left] (remark1) at ([xshift=0.2in]algorithm.north east) {获取每个单词\\的翻译候选};

\node [anchor=west,draw,thick,circle,minimum size=0.3em,inner sep=2.1pt,red] (s1) at ([yshift=-1.0em,xshift=0.5em]remark1.north east){\tiny{1}};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,inner sep=2.1pt,ugreen] (s2) at ([xshift=0.4em]s1.east) {\tiny{2}};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,inner sep=2.1pt,orange] (s3) at ([xshift=0.4em]s2.east) {\tiny{3}};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,inner sep=3.0pt,ublue] (s4) at ([xshift=0.4em]s3.east) {.};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,inner sep=1.5pt,purple] (s5) at ([xshift=0.4em]s4.east) {\tiny{$m$}};

\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,red,fill=red] (t1) at ([yshift=-1.7em]s1.center) {{\color{white} \tiny{$n$}}};
\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,ugreen,fill=ugreen] (t2) at ([yshift=-1.7em]s2.center) {{\color{white} \tiny{$n$}}};
\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,orange,fill=orange] (t3) at ([yshift=-1.7em]s3.center) {{\color{white} \tiny{$n$}}};
\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,ublue,fill=ublue] (t4) at ([yshift=-1.7em]s4.center) {{\color{white} \tiny{$n$}}};
\node [anchor=center,draw,thick,circle,minimum size=0.3em,inner sep=2pt,purple,fill=purple] (t5) at ([yshift=-1.7em]s5.center) {{\color{white} \tiny{$n$}}};

\draw [->,thick] ([yshift=-0.1em]s1.south) -- ([yshift=0.1em]t1.north);
\draw [->,thick] ([yshift=-0.1em]s2.south) -- ([yshift=0.1em]t2.north);
\draw [->,thick] ([yshift=-0.1em]s3.south) -- ([yshift=0.1em]t3.north);
\draw [->,thick] ([yshift=-0.1em]s4.south) -- ([yshift=0.1em]t4.north);
\draw [->,thick] ([yshift=-0.1em]s5.south) -- ([yshift=0.1em]t5.north);

\begin{pgfonlayer}{background}
\visible<2->{
\node[rectangle,draw,inner sep=0.2em,fill=blue!10] [fit = (remark1) (t5)] (remark1label) {};
}
\end{pgfonlayer}
}
\end{scope}
%% end of remark 1

%% remark 2
\begin{scope}
\visible<3->{
\node [anchor=north west,draw,inner sep=2pt,fill=blue!10] (remark2) at ([xshift=-0.2em,yshift=-1em]remark1.south west) {$best$用于保存当前最好的翻译结果};
}
\end{scope}
%% end of remark 2

%% remark 3
\begin{scope}
\visible<3->{
\node [anchor=north west,draw,inner sep=2pt,fill=blue!10] (remark3) at ([yshift=-0.5em]remark2.south west) {$h$用于保存每步生成的所有译文候选};
}
\end{scope}
%% end of remark 3

%% remark 4
\begin{scope}
\visible<4->{
\node [anchor=north west,inner sep=2pt,align=left] (remark4) at ([xshift=0.25em,yshift=-0.6em]remark3.south west) {\textsc{Join}($a,b$) 返回\\$a$ 和$b$ 的所有组合};

{\scriptsize
\node [anchor=north west,inner sep=1pt,align=center,draw] (a1) at ([yshift=-0.5em]remark4.north east) {a1\\a2};
\node [anchor=west] (join) at (a1.east) {$\times$};
\node [anchor=north west,inner sep=1pt,align=center,draw] (b1) at ([xshift=1.5em]a1.north east) {b1\\b2};
\node [anchor=west] (join) at (b1.east) {$=$};
\node [anchor=north west,inner sep=1pt,align=center,draw] (result) at ([xshift=1.5em]b1.north east) {a1b1 a1b2\\a2b1 a2b2};
}

\begin{pgfonlayer}{background}
\visible<4->{
\node[rectangle,draw,inner sep=2pt,fill=blue!10] [fit = (remark4) (result)] (remark4label) {};
}
\end{pgfonlayer}
}
\end{scope}
%% end of remark 4

%% remark 5
\begin{scope}
\visible<5->{
\node [anchor=north west,align=left] (remark5) at ([xshift=0.0em,yshift=-1em]remark4.south west) {\textsc{PruneForTop1}\\保留得分最高的结果};
\node [anchor=west,draw,inner sep=1pt] (s1) at ([yshift=-0.5em,xshift=1.2em]remark5.north east){\tiny{0.234}};
\node [anchor=north west,draw,inner sep=1pt] (s2) at ([yshift=-0.2em]s1.south west){\tiny{0.197}};
\node [anchor=north west,draw,inner sep=1pt] (s3) at ([yshift=-0.2em]s2.south west){\tiny{0.083}};

\draw [-] ([yshift=-0.1em,xshift=-0.2em]s1.south west) -- ([yshift=-0.1em,xshift=3em]s1.south east);
\node [anchor=west] (top1) at ([xshift=0.1em]s1.east) {\tiny{\alert{$\gets$ top1}}};

\begin{pgfonlayer}{background}
\visible<5->{
\node[rectangle,draw,inner sep=0.2em,fill=blue!10] [fit = (remark5) (top1)] (remark5label) {};
}
\end{pgfonlayer}
}
\end{scope}
\%% end of remark 5

%% remark 6
\begin{scope}
\visible<6->{
\node [anchor=north west,align=left] (remark6) at ([xshift=0.0em,yshift=-1em]remark5.south west) {记录已经翻译过\\的源语单词};

\node [anchor=west,draw,thick,circle,minimum size=0.3em,inner sep=2.1pt,red] (s1) at ([yshift=-1.0em,xshift=0.5em]remark6.north east){\tiny{1}};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,inner sep=2.1pt,ugreen] (s2) at ([xshift=0.4em]s1.east) {\tiny{2}};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,inner sep=2.1pt,orange] (s3) at ([xshift=0.4em]s2.east) {\tiny{3}};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,inner sep=3.0pt,ublue] (s4) at ([xshift=0.4em]s3.east) {.};
\node [anchor=west,draw,thick,circle,minimum size=0.3em,inner sep=1.5pt,purple] (s5) at ([xshift=0.4em]s4.east) {\tiny{$m$}};

\draw [-,thick,red] (s1.north east) -- (s1.south west);
\draw [-,thick,orange] (s3.north east) -- (s3.south west);

\begin{pgfonlayer}{background}
\visible<6->{
\node[rectangle,draw,inner sep=0.2em,fill=blue!10] [fit = (remark6) (s5)] (remark6label) {};
}
\end{pgfonlayer}
}
\end{scope}
\%% end of remark 6

\visible<2->{
\draw [->,thick] (line2highlight.east) ..controls +(east:1em) and +(west:1em).. (remark1label.west);
}
\visible<3->{
\draw [->,thick] (line3highlight.east) ..controls +(east:1em) and +(west:1em).. ([yshift=0.3em]remark2.south west);
\draw [->,thick] (line5highlight.east) ..controls +(east:1em) and +(west:1em).. ([yshift=0.3em]remark3.south west);
}
\visible<4->{
\draw [->,thick] (line8highlight.east) ..controls +(east:1em) and +(west:1em).. ([yshift=0.5em]remark4label.west);
}
\visible<5->{
\draw [->,thick] (line9highlight.east) ..controls +(east:1em) and +(west:1em).. ([yshift=0.5em]remark5label.west);
}
\visible<6->{
\draw [->,thick] (line10highlight.east) ..controls +(east:1em) and +(west:1em).. ([yshift=0.5em]remark6label.south west);
}
}

\end{tikzpicture}
\end{flushleft}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 简易机器翻译系统 - step 3 decoding - example
\begin{frame}{实现一个简单的机器翻译系统：解码(4)}

来看一个解码过程的运行实例

\vspace{0.5em}

\begin{tikzpicture}

\begin{scope}[xshift=-2.0in,yshift=-0.1in]

{\tiny

\node [anchor=north west,inner sep=2pt,align=left] (line1) at (0,0) {\textrm{\textbf{Function} \textsc{WordDecoding}($s$)}};
\node [anchor=north west,inner sep=2pt,align=left] (line2) at ([yshift=-3pt]line1.south west) {\textrm{1: $\pi = $\textsc{GetTransOptions}($s$)}};
\node [anchor=north west,inner sep=2pt,align=left] (line3) at ([yshift=-3pt]line2.south west) {\textrm{2: $best = \phi$}};
\node [anchor=north west,inner sep=2pt,align=left] (line4) at ([yshift=-3pt]line3.south west) {\textrm{3: \textbf{for} $i$ in $[1,m]$ \textbf{do}}};
\node [anchor=north west,inner sep=2pt,align=left] (line5) at ([yshift=-3pt]line4.south west) {\textrm{4: \hspace{1em} $h = \phi$}};
\node [anchor=north west,inner sep=2pt,align=left] (line6) at ([yshift=-3pt]line5.south west) {\textrm{5: \hspace{1em} \textbf{foreach} $j$ in $[1,m]$ \textbf{do}}};
\node [anchor=north west,inner sep=2pt,align=left] (line7) at ([yshift=-3pt]line6.south west) {\textrm{6: \hspace{2em} \textbf{if} $used[j]=$ \textbf{false} \textbf{then}}};
\node [anchor=north west,inner sep=2pt,align=left] (line8) at ([yshift=-3pt]line7.south west) {\textrm{7: \hspace{3em} $h = h \cup \textrm{\textsc{Join}}(best,\pi[j])$}};
\node [anchor=north west,inner sep=2pt,align=left] (line9) at ([yshift=-3pt]line8.south west) {\textrm{8: \hspace{1em} $best = \textrm{\textsc{PruneForTop1}}(h)$}};
\node [anchor=north west,inner sep=2pt,align=left] (line10) at ([yshift=-3pt]line9.south west) {\textrm{9: \hspace{1em} $used[best.j] = \textrm{\textsc{\textbf{true}}}$}};
\node [anchor=north west,inner sep=2pt,align=left] (line11) at ([yshift=-3pt]line10.south west) {\textrm{10: \textbf{return} $best.translatoin$}};

{\scriptsize
\node [anchor=north west,inner sep=2pt,align=left] (timeo) at ([yshift=-1em]line11.south west) {\textbf{时间复杂度: } $O(m^2 \cdot n)$};
\node [anchor=north west,inner sep=2pt,align=left] (spaceo) at ([yshift=0em]timeo.south west) {\textbf{空间复杂度: } $O(m \cdot n)$};
}

\node [anchor=south west,inner sep=2pt,align=left] (head1) at ([yshift=3pt]line1.north west) {输出: 找的最佳译文};
\node [anchor=south west,inner sep=2pt,align=left] (head2) at ([yshift=3pt]head1.north west) {输入: 源语句子$s=s_1...s_m$};

}

\begin{pgfonlayer}{background}
\node [rectangle,draw=ublue,thick,inner sep=0.2em,fill=white,drop shadow,minimum height=1.6cm] [fit = (head2) (line8) (line11)] (algorithm) {};

\visible<2-4>{
\node [anchor=west,fill=blue!20,minimum height=1.0em,minimum width=9.7em] (highlight2) at (line2.west) {};
}
\visible<5>{
\node [anchor=west,fill=blue!20,minimum height=1.0em,minimum width=9.7em] (highlight3) at (line3.west) {};
}
\visible<6,12,18,25,31>{
\node [anchor=west,fill=blue!20,minimum height=1.0em,minimum width=9.7em] (highlight5) at (line5.west) {};
}
\visible<7-8,13-14,19-21,26-27,32>{
\node [anchor=west,fill=blue!20,minimum height=1.0em,minimum width=9.7em] (highlight7) at (line7.west) {};
\node [anchor=west,fill=blue!20,minimum height=1.0em,minimum width=9.7em] (highlight8) at (line8.west) {};
}
\visible<9-10,15-16,22-23,28-29,33-34>{
\node [anchor=west,fill=blue!20,minimum height=1.0em,minimum width=9.7em] (highlight9) at (line9.west) {};
}
\visible<11,17,24,30,35>{
\node [anchor=west,fill=blue!20,minimum height=1.0em,minimum width=9.7em] (highlight10) at (line10.west) {};
}
\end{pgfonlayer}

\end{scope}

\begin{scope}[scale=0.6]

{\scriptsize

%% input words
\node [anchor=west] (s1) at (0,0) {\textbf{我}};
\node [anchor=west] (s2) at ([xshift=3em]s1.east) {\textbf{对}};
\node [anchor=west] (s3) at ([xshift=3em]s2.east) {\textbf{你}};
\node [anchor=west] (s4) at ([xshift=2.5em]s3.east) {\textbf{表示}};
\node [anchor=west] (s5) at ([xshift=2.5em]s4.east) {\textbf{满意}};

\node [anchor=south west,inner sep=1pt] (sentlabel) at ([yshift=0.8em]s1.north west) {\scriptsize{\textbf{输入: 待翻译句子(已经分词)}}};

\visible<2->{
\draw [->,very thick,ublue] ([yshift=0.2em]s1.south) -- ([yshift=-0.8em]s1.south) node [pos=0.5,right] (pi1) {\tiny{$\pi$(1)}};
\draw [->,very thick,ublue] ([yshift=0.2em]s2.south) -- ([yshift=-0.8em]s2.south) node [pos=0.5,right] (pi2) {\tiny{$\pi$(2)}};
\draw [->,very thick,ublue] ([yshift=0.2em]s3.south) -- ([yshift=-0.8em]s3.south) node [pos=0.5,right] (pi3) {\tiny{$\pi$(3)}};
\draw [->,very thick,ublue] ([yshift=0.2em]s4.south) -- ([yshift=-0.8em]s4.south) node [pos=0.5,right] (pi4) {\tiny{$\pi$(4)}};
\draw [->,very thick,ublue] ([yshift=0.2em]s5.south) -- ([yshift=-0.8em]s5.south) node [pos=0.5,right] (pi5) {\tiny{$\pi$(5)}};
}

\visible<11->{
\node [anchor=south] (used1) at ([yshift=-1em]s1.north) {\tiny{\alert{\textbf{used}}}};
}
\visible<30->{
\node [anchor=south] (used2) at ([yshift=-1em]s2.north) {\tiny{\alert{\textbf{used}}}};
}
\visible<35->{
\node [anchor=south] (used3) at ([yshift=-1em]s3.north) {\tiny{\alert{\textbf{used}}}};
}
\visible<24->{
\node [anchor=south] (used4) at ([yshift=-1em]s4.north) {\tiny{\alert{\textbf{used}}}};
}
\visible<17->{
\node [anchor=south] (used5) at ([yshift=-1em]s5.north) {\tiny{\alert{\textbf{used}}}};
}

}

{\tiny

%% translation options
\visible<2->{
\node [anchor=north,inner sep=2pt,fill=red!20,minimum height=1.5em,minimum width=2.5em] (t11) at ([yshift=-1.3em]s1.south) {I'm};
\node [anchor=north,inner sep=2pt,fill=red!20,minimum height=1.5em,minimum width=2.5em] (t12) at ([yshift=-0.2em]t11.south) {I};
\node [anchor=north,inner sep=2pt,fill=red!20,minimum height=1.5em,minimum width=2.5em] (t13) at ([yshift=-0.2em]t12.south) {me};
}
\visible<2-3>{
\node [anchor=north,inner sep=2pt,fill=red!20,minimum height=1.5em,minimum width=2.5em] (t14) at ([yshift=-0.2em]t13.south) {am};
\node [anchor=north,inner sep=2pt,fill=red!20,minimum height=1.5em,minimum width=2.5em] (t15) at ([yshift=-0.2em]t14.south) {...};
}

\visible<2->{
\node [anchor=north,inner sep=2pt,fill=green!20,minimum height=1.5em,minimum width=2.5em] (t21) at ([yshift=-1.3em]s2.south) {to};
\node [anchor=north,inner sep=2pt,fill=green!20,minimum height=1.5em,minimum width=2.5em] (t22) at ([yshift=-0.2em]t21.south) {with};
\node [anchor=north,inner sep=2pt,fill=green!20,minimum height=1.5em,minimum width=2.5em] (t23) at ([yshift=-0.2em]t22.south) {for};
}
\visible<2-3>{
\node [anchor=north,inner sep=2pt,fill=green!20,minimum height=1.5em,minimum width=2.5em] (t24) at ([yshift=-0.2em]t23.south) {to};
\node [anchor=north,inner sep=2pt,fill=green!20,minimum height=1.5em,minimum width=2.5em] (t25) at ([yshift=-0.2em]t24.south) {...};
}

\visible<2->{
\node [anchor=north,inner sep=2pt,fill=blue!20,minimum height=1.5em,minimum width=2.5em] (t31) at ([yshift=-1.3em]s3.south) {you};
\node [anchor=north,inner sep=2pt,fill=blue!20,minimum height=1.5em,minimum width=2.5em] (t32) at ([yshift=-0.2em]t31.south) {your};
}

\visible<2->{
\node [anchor=north,inner sep=2pt,fill=orange!20,minimum height=1.5em,minimum width=3.5em] (t41) at ([yshift=-1.3em]s4.south) {$\phi$};
\node [anchor=north,inner sep=2pt,fill=orange!20,minimum height=1.5em,minimum width=3.5em] (t42) at ([yshift=-0.2em]t41.south) {show};
\node [anchor=north,inner sep=2pt,fill=orange!20,minimum height=1.5em,minimum width=3.5em] (t43) at ([yshift=-0.2em]t42.south) {shows};
}
\visible<2-3>{
\node [anchor=north,inner sep=2pt,fill=orange!20,minimum height=1.5em,minimum width=3.5em] (t44) at ([yshift=-0.2em]t43.south) {means};
\node [anchor=north,inner sep=2pt,fill=orange!20,minimum height=1.5em,minimum width=3.5em] (t45) at ([yshift=-0.2em]t44.south) {...};
}

\visible<2->{
\node [anchor=north,inner sep=2pt,fill=purple!20,minimum height=1.5em,minimum width=4.5em] (t51) at ([yshift=-1.3em]s5.south) {satisfy};
\node [anchor=north,inner sep=2pt,fill=purple!20,minimum height=1.5em,minimum width=4.5em] (t52) at ([yshift=-0.2em]t51.south) {satisfied};
\node [anchor=north,inner sep=2pt,fill=purple!20,minimum height=1.5em,minimum width=4.5em] (t53) at ([yshift=-0.2em]t52.south) {satisfies};
}
\visible<2-3>{
\node [anchor=north,inner sep=2pt,fill=purple!20,minimum height=1.5em,minimum width=4.5em] (t54) at ([yshift=-0.2em]t53.south) {it};
\node [anchor=north,inner sep=2pt,fill=purple!20,minimum height=1.5em,minimum width=4.5em] (t55) at ([yshift=-0.2em]t54.south) {...};
}

\visible<2->{
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,fill=black] (pt11) at (t11.east) {{\color{white} .4}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,fill=black] (pt12) at (t12.east) {{\color{white} .3}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,fill=black] (pt13) at (t13.east) {{\color{white} .1}};
}
\visible<2-3>{
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,fill=black] (pt14) at (t14.east) {{\color{white} .1}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,minimum height=0.95em,fill=black] (pt15) at (t15.east) {{\color{white} ...}};
}

\visible<2->{
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,fill=black] (pt21) at (t21.east) {{\color{white} .3}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,fill=black] (pt22) at (t22.east) {{\color{white} .3}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,fill=black] (pt23) at (t23.east) {{\color{white} .2}};
}
\visible<2-3>{
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,fill=black] (pt24) at (t24.east) {{\color{white} .1}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,minimum height=0.95em,fill=black] (pt25) at (t25.east) {{\color{white} ...}};
}

\visible<2->{
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,fill=black] (pt31) at (t31.east) {{\color{white} .7}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,fill=black] (pt32) at (t32.east) {{\color{white} .3}};
}

\visible<2->{
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,fill=black] (pt41) at (t41.east) {{\color{white} .4}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,fill=black] (pt42) at (t42.east) {{\color{white} .2}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,fill=black] (pt43) at (t43.east) {{\color{white} .1}};
}
\visible<2-3>{
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,fill=black] (pt44) at (t44.east) {{\color{white} .1}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,minimum height=0.95em,fill=black] (pt45) at (t45.east) {{\color{white} ...}};
}

\visible<2->{
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,fill=black] (pt51) at (t51.east) {{\color{white} .3}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,fill=black] (pt52) at (t52.east) {{\color{white} .2}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,fill=black] (pt53) at (t53.east) {{\color{white} .2}};
}
\visible<2-3>{
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,fill=black] (pt54) at (t54.east) {{\color{white} .1}};
\node [anchor=north,rotate=90,inner sep=1pt,minimum width=1.5em,minimum height=0.95em,fill=black] (pt55) at (t55.east) {{\color{white} ...}};
}

}

\visible<3>{
\draw [-] ([yshift=-0.5pt,xshift=-0.5em]t13.south west) -- ([yshift=-0.5pt,xshift=1.5em]t53.south east);
}
\visible<4>{
\node [anchor=center,rotate=90] (tablepruninglabel) at ([xshift=-1.5em]t12.west) {\tiny{\alert{只保留前$n$个结果}}};
}


{\scriptsize

%% 1-best hypothesis
\visible<5->{
\node [anchor=west] (translation) at ([yshift=-4em]t13.south west) {$best.translation = $};
}
\visible<5-9>{
\node [anchor=west,inner sep=2pt,minimum height=1.5em,minimum width=2em] (transword0) at (translation.east) {$\phi$};
}
\visible<10->{
\node [anchor=west,fill=red!20,inner sep=2pt,minimum height=1.5em,minimum width=2em] (transword1) at (translation.east) {I'm};
}
\visible<16->{
\node [anchor=west,fill=purple!20,inner sep=2pt,minimum height=1.5em] (transword2) at ([xshift=2pt]transword1.east) {satisfied};
}
\visible<29->{
\node [anchor=west,fill=green!20,inner sep=2pt,minimum height=1.5em] (transword3) at ([xshift=2pt]transword2.east) {with};
}
\visible<34->{
\node [anchor=west,fill=blue!20,inner sep=2pt,minimum height=1.5em] (transword4) at ([xshift=2pt]transword3.east) {you};
}

\visible<7-8,13-14>{
\node [anchor=west,draw,inner sep=0pt,minimum height=1.8em,minimum width=2.3em] (hypotrans1) at ([xshift=-0.2em]transword1.west) {};
}
\visible<19-21,26-27>{
\node [anchor=west,draw,inner sep=0pt,minimum height=1.8em,minimum width=6.20em] (hypotrans2) at ([xshift=-0.2em]transword1.west) {};
}
\visible<32>{
\node [anchor=west,draw,inner sep=0pt,minimum height=1.8em,minimum width=8.50em] (hypotrans3) at ([xshift=-0.2em]transword1.west) {};
}

\visible<5-9>{
\node [anchor=north west] (jlabel) at (translation.south west) {$best.j = -1$};
}
\visible<10-15>{
\node [anchor=north west] (jlabel) at (translation.south west) {$best.j = 1$};
}
\visible<16-22>{
\node [anchor=north west] (jlabel) at (translation.south west) {$best.j = 5$};
}
\visible<23-28>{
\node [anchor=north west] (jlabel) at (translation.south west) {$best.j = 4$};
}
\visible<29-33>{
\node [anchor=north west] (jlabel) at (translation.south west) {$best.j = 2$};
}
\visible<34->{
\node [anchor=north west] (jlabel) at (translation.south west) {$best.j = 3$};
}

}

%% translation option lists
\visible<7>{
\node[anchor=west,draw,minimum height=2.8em,minimum width=2.1em] (list1) at ([xshift=-2pt]t12.west) {};
}
\visible<8,13,19,26>{
\node[anchor=west,draw,minimum height=2.8em,minimum width=2.1em] (list2) at ([xshift=-2pt]t22.west) {};
}
\visible<14>{
\node[anchor=west,draw,minimum height=2.8em,minimum width=3.2em] (list5) at ([xshift=-2pt]t52.west) {};
}
\visible<20,27,32>{
\node[anchor=west,draw,minimum height=1.85em,minimum width=2.1em] (list3) at ([xshift=-2pt,yshift=1pt]t32.north west) {};
}
\visible<21>{
\node[anchor=west,draw,minimum height=2.8em,minimum width=2.6em] (list4) at ([xshift=-2pt]t42.west) {};
}

%% translaiton hypotheses (h)
{\tiny

\visible<7>{
\node [anchor=west] (hlabel) at ([yshift=-5em]jlabel.west) {\scriptsize{$i = 1, j = 1$}};
}
\visible<8>{
\node [anchor=west] (hlabel) at ([yshift=-5em]jlabel.west) {\scriptsize{$i = 1, j = 2$}};
}
\visible<9-12>{
\node [anchor=west] (hlabel) at ([yshift=-5em]jlabel.west) {\scriptsize{$i = 1, j = 5$}};
}
\visible<13>{
\node [anchor=west] (hlabel) at ([yshift=-5em]jlabel.west) {\scriptsize{$i = 2, j = 2$}};
}
\visible<14-18>{
\node [anchor=west] (hlabel) at ([yshift=-5em]jlabel.west) {\scriptsize{$i = 2, j = 5$}};
}
\visible<19>{
\node [anchor=west] (hlabel) at ([yshift=-5em]jlabel.west) {\scriptsize{$i = 3, j = 2$}};
}
\visible<20>{
\node [anchor=west] (hlabel) at ([yshift=-5em]jlabel.west) {\scriptsize{$i = 3, j = 3$}};
}
\visible<21-25>{
\node [anchor=west] (hlabel) at ([yshift=-5em]jlabel.west) {\scriptsize{$i = 3, j = 4$}};
}
\visible<26>{
\node [anchor=west] (hlabel) at ([yshift=-5em]jlabel.west) {\scriptsize{$i = 4, j = 2$}};
}
\visible<27-31>{
\node [anchor=west] (hlabel) at ([yshift=-5em]jlabel.west) {\scriptsize{$i = 4, j = 3$}};
}
\visible<32->{
\node [anchor=west] (hlabel) at ([yshift=-5em]jlabel.west) {\scriptsize{$i = 5, j = 3$}};
}

\visible<6->{
\node [anchor=north west] (glabel) at (hlabel.south west) {$g(s,t)$};
\node [anchor=west] (translabel) at (glabel.east) {翻译结果};
\draw [-] (glabel.north east) -- ([yshift=-1.9in]glabel.north east);
\draw [-] (glabel.south west) -- ([xshift=3.5in]glabel.south west);

\node [anchor=center,rotate=90] (hlabel2) at ([xshift=-1.5em,yshift=-8em]glabel.west) {\tiny{$h$存放临时翻译结果}};
}

%% the 'join' operation
\visible<7-8,13-14,19-21,26-27,32>{
\node [anchor=center,draw=ublue,circle,thick,fill=white,inner sep=2.5pt,circular drop shadow={shadow xshift=0.1em,shadow yshift=-0.1em}] (join) at ([xshift=8em,yshift=-1em]hlabel.north east) {\scriptsize{\textsc{Join}}};
}

%% round 1
\visible<7-11>{
\node [anchor=north west] (g1) at ([yshift=-3pt]glabel.south west) {.1744};
\node [anchor=north west] (g2) at ([yshift=-1pt]g1.south west) {.1674};
\node [anchor=north west] (g3) at ([yshift=-1pt]g2.south west) {.1041};
}
\visible<8-11>{
\node [anchor=north west] (g4) at ([yshift=-1pt]g3.south west) {.0561};
\node [anchor=north west] (g5) at ([yshift=-1pt]g4.south west) {.0013};
\node [anchor=north west] (g6) at ([yshift=-1pt]g5.south west) {.0013};
}
\visible<9-11>{
\node [anchor=north west] (g7) at ([yshift=-1pt]g6.south west) {...};
\node [anchor=north west] (g8) at ([yshift=-1pt]g7.south west) {.1452};
}

\visible<7-11>{
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=red!20] (hword11) at ([xshift=2.0em]g1.east) {I'm};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=red!20] (hword21) at ([xshift=2.0em]g2.east) {I};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=red!20] (hword31) at ([xshift=2.0em]g3.east) {me};
}
\visible<8-11>{
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=green!20] (hword41) at ([xshift=2.0em]g4.east) {to};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=green!20] (hword51) at ([xshift=2.0em]g5.east) {with};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=green!20] (hword61) at ([xshift=2.0em]g6.east) {for};
}
\visible<9-11>{
\node [anchor=west,inner sep=2pt,minimum height=1.3em] (hword71) at ([xshift=4.0em]g7.east) {...};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=purple!20] (hword81) at ([xshift=2.0em]g8.east) {satisfies};
}

\visible<7-8>{
\draw [->,thick] (hypotrans1.south) ..controls +(south:0.5) and +(north:0.5).. (join.north);
}
\visible<7>{
\draw [->,thick] (list1.south) ..controls +(300:3) and +(north west:3).. (join.north west);
\draw [->,thick] (join.south) ..controls +(south:1) and +(east:1).. ([xshift=7em]g2.east);
}
\visible<8>{
\draw [->,thick] (list2.south) ..controls +(south:2) and +(north:2).. (join.110);
\draw [->,thick] (join.south) ..controls +(south:3) and +(east:1).. ([xshift=7em]g5.east);
}

\visible<9-11>{
\node [anchor=west] (top1) at (hword11.east) {\alert{$\gets$ top1}};
}

%% round 2
\visible<13-17>{
\node [anchor=north west] (g1) at ([yshift=-3pt]glabel.south west) {.0099};
\node [anchor=north west] (g2) at ([yshift=-1pt]g1.south west) {.0300};
\node [anchor=north west] (g3) at ([yshift=-1pt]g2.south west) {.0231};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword11) at ([xshift=2.0em]g1.east) {I'm};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword21) at ([xshift=2.0em]g2.east) {I'm};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword31) at ([xshift=2.0em]g3.east) {I'm};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=green!20] (hword12) at ([xshift=0.2em]hword11.east) {to};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=green!20] (hword22) at ([xshift=0.2em]hword21.east) {with};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=green!20] (hword32) at ([xshift=0.2em]hword31.east) {for};
}
\visible<14-17>{
\node [anchor=north west] (g4) at ([yshift=-1pt]g3.south west) {...};
\node [anchor=north west] (g5) at ([yshift=-1pt]g4.south west) {.0121};
\node [anchor=north west] (g6) at ([yshift=-1pt]g5.south west) {.0314};
\node [anchor=north west] (g7) at ([yshift=-1pt]g6.south west) {.0081};
\node [anchor=west,inner sep=2pt,minimum height=1.3em] (hword41) at ([xshift=4.0em]g4.east) {...};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword51) at ([xshift=2.0em]g5.east) {I'm};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword61) at ([xshift=2.0em]g6.east) {I'm};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword71) at ([xshift=2.0em]g7.east) {I'm};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=purple!20] (hword52) at ([xshift=0.2em]hword51.east) {satisfy};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=purple!20] (hword62) at ([xshift=0.2em]hword61.east) {satisfied};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=purple!20] (hword72) at ([xshift=0.2em]hword71.east) {satisfies};
}
\visible<15-17>{
\node [anchor=west] (top1) at (hword62.east) {\alert{$\gets$ top1}};
}
\visible<13-14>{
\draw [->,thick] (hypotrans1.south) ..controls +(south:0.5) and +(north:0.5).. (join.north);
}
\visible<13>{
\draw [->,thick] (list2.south) ..controls +(south:2) and +(north:2).. (join.110);
\draw [->,thick] (join.south) ..controls +(south:1) and +(east:1).. ([xshift=1em]hword22.east);
}
\visible<14>{
\draw [->,thick] (list5.south) ..controls +(200:3) and +(20:3).. (join.north east);
\draw [->,thick] (join.south) ..controls +(south:2) and +(east:0.5).. ([xshift=1em]hword62.east);
}

%% round 3
\visible<19-24>{
\node [anchor=north west] (g1) at ([yshift=-3pt]glabel.south west) {.0082};
\node [anchor=north west] (g2) at ([yshift=-1pt]g1.south west) {.0103};
\node [anchor=north west] (g3) at ([yshift=-1pt]g2.south west) {.0073};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword11) at ([xshift=2.0em]g1.east) {I'm satisfied};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword21) at ([xshift=2.0em]g2.east) {I'm satisfied};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword31) at ([xshift=2.0em]g3.east) {I'm satisfied};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=green!20] (hword12) at ([xshift=0.2em]hword11.east) {to};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=green!20] (hword22) at ([xshift=0.2em]hword21.east) {with};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=green!20] (hword32) at ([xshift=0.2em]hword31.east) {for};
}
\visible<20-24>{
\node [anchor=north west] (g4) at ([yshift=-1pt]g3.south west) {.0033};
\node [anchor=north west] (g5) at ([yshift=-1pt]g4.south west) {.0039};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword41) at ([xshift=2.0em]g4.east) {I'm satisfied};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword51) at ([xshift=2.0em]g5.east) {I'm satisfied};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=blue!20] (hword42) at ([xshift=0.2em]hword41.east) {you};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=blue!20] (hword52) at ([xshift=0.2em]hword51.east) {your};
}
\visible<21-24>{
\node [anchor=north west] (g6) at ([yshift=-1pt]g5.south west) {.0106};
\node [anchor=north west] (g7) at ([yshift=-1pt]g6.south west) {.0035};
\node [anchor=north west] (g8) at ([yshift=-1pt]g7.south west) {.0028};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword61) at ([xshift=2.0em]g6.east) {I'm satisfied};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword71) at ([xshift=2.0em]g7.east) {I'm satisfied};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword81) at ([xshift=2.0em]g8.east) {I'm satisfied};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=orange!20] (hword62) at ([xshift=0.2em]hword61.east) {$\phi$};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=orange!20] (hword72) at ([xshift=0.2em]hword71.east) {show};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=orange!20] (hword82) at ([xshift=0.2em]hword81.east) {shows};
}
\visible<22-24>{
\node [anchor=west] (top1) at (hword62.east) {\alert{$\gets$ top1}};
}
\visible<19-21>{
\draw [->,thick] (hypotrans2.south) ..controls +(south:0.5) and +(north:0.5).. (join.north);
}
\visible<19>{
\draw [->,thick] ([xshift=-2em]list2.south) ..controls +(south:2) and +(north:2).. (join.110);
\draw [->,thick] (join.south east) ..controls +(330:0.5) and +(30:0.3).. ([xshift=1em]hword22.east);
}
\visible<20>{
\draw [->,thick] ([xshift=-2em]list3.south) ..controls +(south:2) and +(north:2).. (join.110);
\draw [->,thick] (join.south east) ..controls +(330:1) and +(30:0.3).. ([xshift=1em]hword42.south east);
}
\visible<21>{
\draw [->,thick] (list4.south) ..controls +(south:1) and +(north:3).. (join.north west);
\draw [->,thick] (join.south east) ..controls +(330:1) and +(30:0.3).. ([xshift=1em]hword72.south east);
}

%% round 4
\visible<26-30>{
\node [anchor=north west] (g1) at ([yshift=-3pt]glabel.south west) {.0032};
\node [anchor=north west] (g2) at ([yshift=-1pt]g1.south west) {.0040};
\node [anchor=north west] (g3) at ([yshift=-1pt]g2.south west) {.0028};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword11) at ([xshift=2.0em]g1.east) {I'm satisfied};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword21) at ([xshift=2.0em]g2.east) {I'm satisfied};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword31) at ([xshift=2.0em]g3.east) {I'm satisfied};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=green!20] (hword12) at ([xshift=0.2em]hword11.east) {to};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=green!20] (hword22) at ([xshift=0.2em]hword21.east) {with};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=green!20] (hword32) at ([xshift=0.2em]hword31.east) {for};
}
\visible<27-30>{
\node [anchor=north west] (g4) at ([yshift=-1pt]g3.south west) {.0012};
\node [anchor=north west] (g5) at ([yshift=-1pt]g4.south west) {.0014};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword41) at ([xshift=2.0em]g4.east) {I'm satisfied};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword51) at ([xshift=2.0em]g5.east) {I'm satisfied};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=blue!20] (hword42) at ([xshift=0.2em]hword41.east) {you};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=blue!20] (hword52) at ([xshift=0.2em]hword51.east) {your};
}
\visible<28-30>{
\node [anchor=west] (top1) at (hword22.east) {\alert{$\gets$ top1}};
}
\visible<26-27>{
\draw [->,thick] (hypotrans2.south) ..controls +(south:0.5) and +(north:0.5).. (join.north);
}
\visible<26>{
\draw [->,thick] ([xshift=-2em]list2.south) ..controls +(south:2) and +(north:2).. (join.110);
\draw [->,thick] (join.south east) ..controls +(330:0.5) and +(30:0.3).. ([xshift=1em]hword22.east);
}
\visible<27>{
\draw [->,thick] ([xshift=-2em]list3.south) ..controls +(south:2) and +(north:2).. (join.110);
\draw [->,thick] (join.south east) ..controls +(330:1) and +(30:0.3).. ([xshift=1em]hword42.south east);
}

%% round 5
\visible<32-35>{
\node [anchor=north west] (g1) at ([yshift=-3pt]glabel.south west) {.0011};
\node [anchor=north west] (g2) at ([yshift=-1pt]g1.south west) {.0010};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword11) at ([xshift=2.0em]g1.east) {I'm satisfied with};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=gray!20] (hword21) at ([xshift=2.0em]g2.east) {I'm satisfied with};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=green!20] (hword12) at ([xshift=0.2em]hword11.east) {you};
\node [anchor=west,inner sep=2pt,minimum height=1.3em,fill=green!20] (hword22) at ([xshift=0.2em]hword21.east) {your};
}
\visible<33-35>{
\node [anchor=west] (top1) at (hword12.east) {\alert{$\gets$ top1}};
}
\visible<32>{
\draw [->,thick] (hypotrans3.south) ..controls +(south:0.5) and +(north:0.5).. (join.north);
}
\visible<32>{
\draw [->,thick] ([xshift=-2em]list3.south) ..controls +(south:2) and +(north:2).. (join.110);
\draw [->,thick] (join.south east) ..controls +(340:1) and +(30:0.3).. ([xshift=1em]hword22.north east);
}

}

\end{scope}

\end{tikzpicture}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 停顿，介绍本节主要内容
\begin{frame}{即将开始正式的内容}

\begin{itemize}

\item 基于词的统计机器翻译很简单 - 建议实现一下前面所描述的方法，确实不难
    \begin{itemize}
    \item \textbf{是的}，思想很简单
    \item \textbf{不对}，前面的例子主要面向实现，还有很多问题没有回答
        \begin{itemize}
        \item \textbf{建模：}还需要更严密的数学模型来描述翻译过程
        \item \textbf{训练：}需要有一个科学的优化方法
        \item \textbf{解码：}是否还有其它更系统的解码方法？A*，Bottom-up decoding?
        \item \textbf{其它：}空翻译问题、调序建模问题等等
        \end{itemize}
    \end{itemize}
\item<2-> \textbf{下面}，继续对一些问题进行进一步介绍及分析
    \begin{enumerate}
    \item 统计机器翻译基础模型和IBM模型
        \begin{itemize}
        \item 统计机器翻译模型基础(生成模型)
        \item IBM Models 1-2的建模及训练
        \item IBM Models 3-5的建模
        \end{itemize}
    \item 统计词对齐
        \begin{itemize}
        \item 基于HMMs的词对齐
        \item 基于判别式模型的词对齐
        \end{itemize}
    \end{enumerate}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
\section{IBM模型}

%%%------------------------------------------------------------------------------------------------------------
\subsection{噪声信道模型}

%%%------------------------------------------------------------------------------------------------------------
%%% 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. 一个简单的翻译实例}}};

\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. IBM模型}}\\\black{\textbf{\hspace{1.5em}$\bullet$  建模}}\\\gray{\textbf{\hspace{1.5em}$\bullet$  解码}}\\\gray{\textbf{\hspace{1.5em}$\bullet$  模型训练}}};
}

\end{tikzpicture}
\end{center}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% IBM Models的地位
\begin{frame}{统计机器翻译}

\begin{itemize}
\item 统计机器翻译源于1941年的Warren Weaver的思想，而正式开始于
    {\footnotesize
    \begin{itemize}
    \item \textit{\textbf{A Program for Aligning Sentences in Bilingual Corpora}}\\
          William A. Gale; Kenneth W. Church. 1993.
    \item \textit{\textbf{The Mathematics of Statistical Machine Translation: Parameter Estimation}}\\
          Peter E. Brown; Stephen A. Della Pietra; Vincent J. Della Pietra; Robert L. Mercer. 1993.
    \end{itemize}
    }
\item 特别是IBM Waston研究中心Brown等人的基于词的统计机器翻译模型，成为机器翻译领域至今\alert{经典中的经典}
\vspace{0.3em}
\begin{beamerboxesrounded}[upper=uppercolblue,lower=lowercolblue,shadow=true,width=\linewidth]{\small{Brown等人的工作(IBM Waston)} - on Wikipedia}
{\scriptsize
\begin{spacing}{1}
\textit{The first ideas of statistical machine translation were introduced by Warren Weaver in 1949, including the ideas of applying Claude Shannon's information theory. Statistical machine translation was re-introduced in 1991 by researchers at IBM's Thomas J. Watson Research Center and has contributed to the significant resurgence in interest in machine translation in recent years. Nowadays it is by far the most widely-studied machine translation method}
\vspace{-0.7em}
\end{spacing}
}
\end{beamerboxesrounded}
\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 机器翻译中的统计思想
\begin{frame}{机器翻译的统计建模}

\begin{itemize}
\item \textbf{一个人在做翻译时}：对于给定的源语言句子$s$，可以了翻译为一个（或者若干个）正确的译文$\hat{t}$
    \begin{itemize}
    \item 也就是说除了正确的译文，其它的翻译都是不正确的
    \end{itemize}

\begin{center}
\begin{tikzpicture}

\node [draw,red,fill=red!10,thick,anchor=center,circle,inner sep=3.5pt] (s) at (0,0) {\black{$s$}};
\node [draw,ublue,fill=blue!10,thick,anchor=center,circle,inner sep=2pt] (t) at ([xshift=1in]s.east) {\black{$\hat{t}$}};

\draw [->,thick,] (s.north east) .. controls +(north east:1em) and +(north west:1em).. (t.north west) node[pos=0.5,below] {\tiny{正确翻译}};

\end{tikzpicture}
\end{center}

\item<2-> \textbf{统计机器翻译的思想是}：对于$s$，所有可能的目标语词串$t$都是可能的译文。每一对($s$,$t$)都有一个概率值$\textrm{P}(t|s)$ 来描述$s$ 翻译为$t$的好与坏

\begin{center}
\begin{tikzpicture}

\node [draw,red,fill=red!10,thick,anchor=center,circle,inner sep=3.5pt] (s) at (0,0) {\black{$s$}};
\node [draw,ublue,fill=blue!10,thick,anchor=center,circle,inner sep=2pt] (t1) at ([xshift=1in]s.east) {\black{$t_1$}};
\node [draw,ublue,fill=blue!10,thick,anchor=center,circle,inner sep=2pt] (t2) at ([xshift=3em,yshift=2em]t1.north east) {\black{$t_2$}};
\node [draw,ublue,fill=blue!10,thick,anchor=center,circle,inner sep=2pt] (t3) at ([xshift=1em,yshift=4em]t1.north east) {\black{$t_3$}};
\node [draw,ublue,fill=blue!10,thick,anchor=center,circle,inner sep=2pt] (t4) at ([xshift=3em,yshift=-1.5em]t1.north east) {\black{$t_4$}};

\node [draw,dashed,ublue,fill=blue!10,thick,anchor=center,circle,minimum size=18pt] (t5) at ([xshift=3em]t3.east) {};
\node [draw,dashed,ublue,fill=blue!10,thick,anchor=center,circle,minimum size=18pt] (t6) at ([xshift=3em]t2.east) {};
\node [draw,dashed,ublue,fill=blue!10,thick,anchor=center,circle,minimum size=18pt] (t7) at ([xshift=3em]t4.east) {};

\draw [->,thick,] (s.north east) .. controls +(north east:1em) and +(north west:1em).. (t1.north west) node[pos=0.5,below] {\tiny{P ($t_1|s$)=0.1}};
\draw [->,thick,] (s.60) .. controls +(50:4em) and +(west:1em).. (t2.west) node[pos=0.5,below] {\tiny{P($t_2|s$)=0.2}};
\draw [->,thick,] (s.north) .. controls +(70:4em) and +(west:1em).. (t3.west) node[pos=0.5,above,xshift=-1em] {\tiny{P($t_3|s$)=0.3}};
\draw [->,thick,] (s.south east) .. controls +(300:3em) and +(south west:1em).. (t4.south west) node[pos=0.5,below] {\tiny{P($t_4|s$)=0.1}};

\end{tikzpicture}
\end{center}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 噪声信道模型
\begin{frame}{噪声信道模型}

\begin{itemize}
\item \textbf{噪声信道模型}：源语言句子$s$(信宿)是由目标语句子$t$(信源)经过一个有噪声的信道得到的。如果知道了$s$和信道的性质，我们可以通过$\textrm{P}(t|s)$得到可能的信源的概率。\\

\begin{center}
\begin{tikzpicture}

\node [draw,red,fill=red!10,thick,anchor=center,circle,inner sep=3.5pt] (s) at (0,0) {\black{$s$}};
\node [draw,ublue,fill=blue!10,thick,anchor=center,circle,inner sep=3.3pt] (t) at ([xshift=1.5in]s.east) {\black{$t$}};

\draw [<->,thick,] (s.east) -- (t.west) node [pos=0.5,draw,fill=white] {噪声信道};
\node [anchor=east] at (s.west) {\scriptsize{信宿}};
\node [anchor=west] at (t.east) {\scriptsize{信源}};

\end{tikzpicture}
\end{center}

    而通过上述过程找到最可能的信源的过程被称之为\alert{解码}

    \begin{displaymath}
    \hat{t} = \argmax_{t} \textrm{P}(t|s)
    \end{displaymath}

\item<2-> \textbf{贝叶斯变换}
    \begin{eqnarray}
    \textrm{P}(t|s) & = & \frac{\textrm{P}(s,t)}{\textrm{P}(s)} \nonumber \\
                    & = & \frac{\textrm{P}(s|t) \textrm{P}(t)}{\textrm{P}(s)} \nonumber
    \end{eqnarray}
\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% 翻译模型 + 语言模型
\begin{frame}{噪声信道模型(2)}

\begin{center}
\begin{tikzpicture}

\node [anchor=west] (p) at (0,0) {$\textrm{P}(t|s)$};
\node [anchor=west] (eqiv) at (p.east) {=};
\node [anchor=south west,inner sep=2pt] (transmodel) at ([yshift=-2pt]eqiv.north east) {$\textrm{P}(s|t)$};
\node [anchor=west,inner sep=2pt] (lmmodel) at ([xshift=2pt]transmodel.east) {$\textrm{P}(t)$};
\node [anchor=north west,inner sep=2pt] (sp) at ([yshift=4pt,xshift=1.5em]eqiv.south east) {$\textrm{P}(s)$};

\visible<2->{
\node [anchor=south west,fill=red!20,inner sep=2pt] (transmodel) at ([yshift=-2pt]eqiv.north east) {$\textrm{P}(s|t)$};
\node [anchor=west,fill=blue!20,inner sep=2pt] (lmmodel) at ([xshift=2pt]transmodel.east) {$\textrm{P}(t)$};
\node [anchor=north west,fill=green!20,inner sep=2pt] (sp) at ([yshift=4pt,xshift=1.5em]eqiv.south east) {$\textrm{P}(s)$};
}

\draw [-] ([yshift=-4pt]transmodel.south west) -- ([yshift=-4pt]lmmodel.south east);

\visible<2->{
\node [anchor=south east,fill=red!20,draw,align=left] (tmmark) at ([xshift=0.5in,yshift=0.4in]p.north) {\footnotesize{给定信源$t$，得到信宿$s$ }\\\footnotesize{的概率，称作\textbf{翻译模型}}};

\node [anchor=west,fill=blue!20,draw,align=left] (lmmark) at ([xshift=0.5in]tmmark.east) {\footnotesize{信源$t$出现的概率}\\\footnotesize{称作\textbf{语言模型}}};

\node [anchor=west,fill=green!20,draw,align=left] (smark) at ([xshift=0.2in,yshift=-0.3in]lmmodel.east) {\footnotesize{信宿$s$出现的概率}\\\footnotesize{给定$s$，$\textrm{P}(s)$为\textbf{常量}}};

\draw [->,thick] (transmodel.north) .. controls +(north:1.5em) and + (south:1.5em) .. (tmmark.south);
\draw [->,thick] (lmmodel.north) .. controls +(north:1.5em) and + (south:1.3em) .. (lmmark.south);
\draw [->,thick] (sp.east) .. controls +(east:2em) and + (west:2em) .. ([yshift=0.3em]smark.south west);
}

\end{tikzpicture}
\end{center}

\begin{itemize}
\item<3-> \textbf{因此}，翻译问题可以被重新描述为

\vspace{-0.5em}

\begin{eqnarray}
\hat{t} & = & \argmax_{t} \frac{\textrm{P}(s|t) \textrm{P}(t)}{\textrm{P}(s)} \nonumber \\
        & = & \argmax_{t} \textrm{P}(s|t) \textrm{P}(t) \nonumber
\end{eqnarray}

即，在所有可能的译文中找到使翻译模型$\textrm{P}(s|t)$和语言模型$\textrm{P}(t)$乘积最大的译文

\end{itemize}
\
\end{frame}

%%%------------------------------------------------------------------------------------------------------------
\subsection{三个基本问题}

%%%------------------------------------------------------------------------------------------------------------
%%% 统计机器翻译的三个基本问题
\begin{frame}{基本问题}

\begin{displaymath}
\hat{t} = \argmax_{t} \textrm{P}(s|t) \textrm{P}(t)
\end{displaymath}

\begin{itemize}
\item \textbf{三个基本问题}
    \begin{enumerate}
    \item \textbf{建模}：如何描述计算$\textrm{P}(s|t)$和$\textrm{P}(t)$的计算方式
    \item \textbf{训练}：如何获得计算$\textrm{P}(s|t)$和$\textrm{P}(t)$所需的参数
    \item \textbf{解码}：如何完成搜索最优解的过程$argmax$
    \end{enumerate}
\item<2-> 回忆一下本章开始的实例，是不是有似曾相识的感觉？
    \vspace{0.5em}
    \begin{center}
    \begin{tikzpicture}
    \node [anchor=west] (e1) at (0,0) {$g(s,t)$};
    \node [anchor=west] (e2) at (e1.east) {$=$};
    \node [anchor=west,inner sep=2pt,fill=red!20] (e3) at (e2.east) {$\prod\nolimits_{(j,i) \in \hat{A}} \textrm{P}(s_j,t_i)$};
    \node [anchor=west,inner sep=1pt] (e4) at (e3.east) {$\times$};
    \node [anchor=west,inner sep=3pt,fill=blue!20] (e5) at (e4.east) {$\textrm{P}_{lm}(t)$};
    \node [anchor=north west,inner sep=1pt] (n1) at ([xshift=2.5em,yshift=-1em]e1.south west) {$\textrm{P}(s|t)$};
    \node [anchor=north] (n1part2) at ([yshift=0.3em]n1.south) {\scriptsize{\textbf{翻译模型}}};
    \node [anchor=west,inner sep=1pt] (n2) at ([xshift=2em]n1.east) {$\textrm{P}(t)$};
    \node [anchor=north] (n2part2) at ([yshift=0.3em]n2.south) {\scriptsize{\textbf{语言模型}}};
    \draw [->,thick] (e3.south) .. controls +(south:1em) and +(north:1em) .. (n1.north);
    \draw [->,thick] (e5.south) .. controls +(south:1em) and +(70:1em) .. (n2.north);
    \end{tikzpicture}
    \end{center}
    \vspace{-0.5em}
    \begin{itemize}
    \item 词汇翻译概率和ngram概率使用相对频率估计({\color{ublue} \hyperref[wordtranslationprob]{第\hspace{-0.2em}~\ref{wordtranslationprob}页}})
    \item $argmax$使用{\color{ublue} \hyperref[simpledecodingalgorithm]{第\hspace{-0.2em}~\ref{simpledecodingalgorithm}页}}所描述的解码算法
    \end{itemize}
\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
\subsection{建模}

%%%------------------------------------------------------------------------------------------------------------
%%% IBM model-style word alignment
\begin{frame}{IBM模型中的假设 - 词对齐}
\label{ibmmodelingstart}

\begin{itemize}
\item \textbf{$\textrm{P}(t)$和解码}在前面的内容中有介绍，下面重点求解$\textrm{P}(s|t)$，即：
    \begin{itemize}
    \item \textbf{翻译模型建模} - $\textrm{P}(s|t)$的计算方法
    \item \textbf{翻译模型参数估计} - 计算$\textrm{P}(s|t)$所需的参数
    \end{itemize}
    \vspace{0.5em}
\item<2-> \textbf{IBM模型的假设}：$s=s_1...s_m$和$t=t_1...t_n$之间有单词一级的对应，称作\alert{单词对齐}或者\alert{词对齐}。此外：
    \begin{itemize}
    \item \textbf{约束}：一个源语言单词只能对应一个目标语单词
    \vspace{0.5em}
    \begin{center}
    \begin{tikzpicture}
    \begin{scope}
    {\small
    \node [anchor=west,inner sep=2pt] (s1) at (0,0) {谢谢};
    \node [anchor=west,inner sep=2pt] (s2) at ([xshift=1em]s1.east) {你};
    \node [anchor=north,inner sep=2pt] (t1) at ([yshift=-1.2em]s1.center) {thank};
    \node [anchor=north,inner sep=2pt] (t2) at ([yshift=-1.45em]s2.center) {you};
    \draw [-] (s1.south) -- ([yshift=-0.2em]t1.north);
    \draw [-] (s2.south) -- (t2.north);
    \node [anchor=center,draw=ublue,circle,thick,fill=white,inner sep=1pt,circular drop shadow={shadow xshift=0.1em,shadow yshift=-0.1em}] (mark) at ([xshift=0.5em,yshift=-0.2em]s2.south east) {{\color{ugreen} \tiny{\textbf{Yes}}}};
    }
    \end{scope}
    \begin{scope}[xshift=1.3in]
    {\small
    \node [anchor=west,inner sep=2pt] (s1) at (0,0) {谢谢};
    \node [anchor=west,inner sep=2pt] (s2) at ([xshift=1em]s1.east) {你};
    \node [anchor=north,inner sep=2pt] (t1) at ([yshift=-1.2em]s1.center) {thank};
    \node [anchor=north,inner sep=2pt] (t2) at ([yshift=-1.45em]s2.center) {you};
    \draw [-] (s1.south) -- ([yshift=-0.2em]t1.north);
    \draw [-] (s1.south) -- (t2.north);
    \node [anchor=center,draw=ublue,circle,thick,fill=white,inner sep=1.5pt,circular drop shadow={shadow xshift=0.1em,shadow yshift=-0.1em}] (mark) at ([xshift=0.5em,yshift=-0.2em]s2.south east) {{\color{red} \tiny{\textbf{No}}}};
    }
    \end{scope}
    \begin{scope}[xshift=2.6in]
    {\small
    \node [anchor=west,inner sep=2pt] (s1) at (0,0) {谢谢};
    \node [anchor=west,inner sep=2pt] (s2) at ([xshift=1em]s1.east) {你};
    \node [anchor=north,inner sep=2pt] (t1) at ([yshift=-1.2em]s1.center) {thank};
    \node [anchor=north,inner sep=2pt] (t2) at ([yshift=-1.45em]s2.center) {you};
    \draw [-] (s1.south) -- ([yshift=-0.2em]t1.north);
    \draw [-] (s2.south) -- ([yshift=-0.2em]t1.north);
    \node [anchor=center,draw=ublue,circle,thick,fill=white,inner sep=1pt,circular drop shadow={shadow xshift=0.1em,shadow yshift=-0.1em}] (mark) at ([xshift=0.5em,yshift=-0.2em]s2.south east) {{\color{ugreen} \tiny{\textbf{Yes}}}};
    }
    \end{scope}
    \end{tikzpicture}
    \end{center}
    \vspace{0.5em}
    \item<3-> \textbf{空翻译(删词)}：源语言单词可以翻空，这时它对应到一个虚拟的目标语单词$t_0$
    \vspace{0.3em}
    \begin{center}
    \begin{tikzpicture}
    {\small
    \node [anchor=west,inner sep=2pt] (s1) at (0,0) {在};
    \node [anchor=west,inner sep=2pt] (s2) at ([xshift=1em]s1.east) {桌子};
    \node [anchor=west,inner sep=2pt] (s3) at ([xshift=1em]s2.east) {上};
    \node [anchor=north,inner sep=2pt] (t1) at ([yshift=-1.7em]s1.center) {on};
    \node [anchor=north,inner sep=2pt] (t2) at ([yshift=-1.5em]s2.center) {the};
    \node [anchor=north,inner sep=2pt] (t3) at ([yshift=-1.5em]s3.center) {table};
    \node [anchor=east,inner sep=2pt] (t0) at ([xshift=-1.5em]t1.west) {$t_0$};
    \draw [-] (s1.south) -- (t0.north);
    \draw [-] (s2.south) -- (t3.north);
    \draw [-] (s3.south) .. controls +(south:1em) and +(north:1em) .. (t1.north);
    }
    \end{tikzpicture}
    \end{center}
    \end{itemize}
\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% modeling P(s|t)
\begin{frame}{建模 - $\textrm{P}(s|t)$}

\begin{itemize}
\item 给定$s$和$t$，它们之间的\alert{词对齐}被记为$a=a_1...a_m$
    \begin{itemize}
    \item $a_j$表示第$j$个源语单词$s_j$对应的目标语单词的位置
    \begin{center}
    \begin{tikzpicture}
    {\small
    \node [anchor=west,inner sep=2pt] (s1) at (0,0) {$s_1$:在};
    \node [anchor=west,inner sep=2pt] (s2) at ([xshift=1em]s1.east) {$s_2$:桌子};
    \node [anchor=west,inner sep=2pt] (s3) at ([xshift=1em]s2.east) {$s_3$:上};
    \node [anchor=north,inner sep=2pt] (t1) at ([yshift=-1.7em]s1.center) {$t_1$:on};
    \node [anchor=north,inner sep=2pt] (t2) at ([yshift=-1.6em]s2.center) {$t_2$:the};
    \node [anchor=north,inner sep=2pt] (t3) at ([yshift=-1.6em]s3.center) {$t_3$:table};
    \node [anchor=east,inner sep=2pt] (t0) at ([xshift=-1.5em]t1.west) {$t_0$};
    \draw [-] (s1.south) -- (t0.north);
    \draw [-] (s2.south) -- (t3.north);
    \draw [-] (s3.south) -- (t1.north);
    \node [anchor=west] (a) at ([xshift=2em,yshift=-1em]s3.east) {$a_1=0,a_2=3,a_3=1$};
    }
    \end{tikzpicture}
    \end{center}
    \end{itemize}
\item<2-> \textbf{\alert{建模!!}}: $\textrm{P}(s|t)$被表示为所有可能的词对齐的生成概率\\
    \vspace{-0.5em}
    \begin{displaymath}
    \textrm{P}(s|t) = \sum_{a} \textrm{P}(s,a|t)
    \end{displaymath}\\
    \vspace{-0.5em}

    \visible<3->{
    每一种$a$对应一个$\textrm{P}(s,a|t)$

    \vspace{-0.8em}
    \begin{center}
    \begin{tikzpicture}
    \begin{scope}
    {\scriptsize
    \node [anchor=west,inner sep=2pt] (s1) at (0,0) {谢谢};
    \node [anchor=west,inner sep=2pt] (s2) at ([xshift=0.4em]s1.east) {你};
    \node [anchor=north,inner sep=2pt] (t1) at ([yshift=-1.2em]s1.center) {thank};
    \node [anchor=north,inner sep=2pt] (t2) at ([yshift=-1.45em]s2.center) {you};
    \node [anchor=east,inner sep=2pt] (t0) at ([xshift=-0.2em,yshift=-0.1em]t1.west) {$t_0$};
    \draw [-] (s1.south) -- (t0.north);
    \draw [-] (s2.south) -- (t0.north);
    \visible<4->{
    \node [anchor=south east,inner sep=0pt] (p) at (t0.north west) {\small{{\color{ugreen} P(}}};
    \node [anchor=south west,inner sep=0pt] (p2) at ([yshift=0.2em]t2.north east) {\small{{\color{ugreen} )}}};
    \node [anchor=west] (eq) at (p2.east) {\small{+}};
    }
    }
    \end{scope}
    \begin{scope}[xshift=1.2in]
    {\scriptsize
    \node [anchor=west,inner sep=2pt] (s1) at (0,0) {谢谢};
    \node [anchor=west,inner sep=2pt] (s2) at ([xshift=0.4em]s1.east) {你};
    \node [anchor=north,inner sep=2pt] (t1) at ([yshift=-1.2em]s1.center) {thank};
    \node [anchor=north,inner sep=2pt] (t2) at ([yshift=-1.45em]s2.center) {you};
    \node [anchor=east,inner sep=2pt] (t0) at ([xshift=-0.2em,yshift=-0.1em]t1.west) {$t_0$};
    \draw [-] (s1.south) -- (t0.north);
    \draw [-] (s2.south) -- (t1.north);
    \visible<4->{
    \node [anchor=south east,inner sep=0pt] (p) at (t0.north west) {\small{{\color{ugreen} P(}}};
    \node [anchor=south west,inner sep=0pt] (p2) at ([yshift=0.2em]t2.north east) {\small{{\color{ugreen} )}}};
    \node [anchor=west] (eq) at (p2.east) {\small{+}};
    }
    }
    \end{scope}
    \begin{scope}[xshift=2.4in]
    {\scriptsize
    \node [anchor=west,inner sep=2pt] (s1) at (0,0) {谢谢};
    \node [anchor=west,inner sep=2pt] (s2) at ([xshift=0.4em]s1.east) {你};
    \node [anchor=north,inner sep=2pt] (t1) at ([yshift=-1.2em]s1.center) {thank};
    \node [anchor=north,inner sep=2pt] (t2) at ([yshift=-1.45em]s2.center) {you};
    \node [anchor=east,inner sep=2pt] (t0) at ([xshift=-0.2em,yshift=-0.1em]t1.west) {$t_0$};
    \draw [-] (s1.south) -- (t0.north);
    \draw [-] (s2.south) -- (t2.north);
    \visible<4->{
    \node [anchor=south east,inner sep=0pt] (p) at (t0.north west) {\small{{\color{ugreen} P(}}};
    \node [anchor=south west,inner sep=0pt] (p2) at ([yshift=0.2em]t2.north east) {\small{{\color{ugreen} )}}};
    \node [anchor=west] (eq) at (p2.east) {\small{+}};
    }
    }
    \end{scope}
    \begin{scope}[yshift=-0.5in]
    {\scriptsize
    \node [anchor=west,inner sep=2pt] (s1) at (0,0) {谢谢};
    \node [anchor=west,inner sep=2pt] (s2) at ([xshift=0.4em]s1.east) {你};
    \node [anchor=north,inner sep=2pt] (t1) at ([yshift=-1.2em]s1.center) {thank};
    \node [anchor=north,inner sep=2pt] (t2) at ([yshift=-1.45em]s2.center) {you};
    \node [anchor=east,inner sep=2pt] (t0) at ([xshift=-0.2em,yshift=-0.1em]t1.west) {$t_0$};
    \draw [-] (s1.south) -- ([yshift=-0.2em]t1.north);
    \draw [-] (s2.south) -- (t0.north);
    \visible<4->{
    \node [anchor=south east,inner sep=0pt] (p) at (t0.north west) {\small{{\color{ugreen} P(}}};
    \node [anchor=south west,inner sep=0pt] (p2) at ([yshift=0.2em]t2.north east) {\small{{\color{ugreen} )}}};
    \node [anchor=west] (eq) at (p2.east) {\small{+}};
    }
    }
    \end{scope}
    \begin{scope}[xshift=1.2in,yshift=-0.5in]
    {\scriptsize
    \node [anchor=west,inner sep=2pt] (s1) at (0,0) {谢谢};
    \node [anchor=west,inner sep=2pt] (s2) at ([xshift=0.4em]s1.east) {你};
    \node [anchor=north,inner sep=2pt] (t1) at ([yshift=-1.2em]s1.center) {thank};
    \node [anchor=north,inner sep=2pt] (t2) at ([yshift=-1.45em]s2.center) {you};
    \node [anchor=east,inner sep=2pt] (t0) at ([xshift=-0.2em,yshift=-0.1em]t1.west) {$t_0$};
    \draw [-] (s1.south) -- ([yshift=-0.2em]t1.north);
    \draw [-] (s2.south) -- ([yshift=-0.2em]t1.north);
    \visible<4->{
    \node [anchor=south east,inner sep=0pt] (p) at (t0.north west) {\small{{\color{ugreen} P(}}};
    \node [anchor=south west,inner sep=0pt] (p2) at ([yshift=0.2em]t2.north east) {\small{{\color{ugreen} )}}};
    \node [anchor=west] (eq) at (p2.east) {\small{+}};
    }
    }
    \end{scope}
    \begin{scope}[xshift=2.4in,yshift=-0.5in]
    {\scriptsize
    \node [anchor=west,inner sep=2pt] (s1) at (0,0) {谢谢};
    \node [anchor=west,inner sep=2pt] (s2) at ([xshift=0.4em]s1.east) {你};
    \node [anchor=north,inner sep=2pt] (t1) at ([yshift=-1.2em]s1.center) {thank};
    \node [anchor=north,inner sep=2pt] (t2) at ([yshift=-1.45em]s2.center) {you};
    \node [anchor=east,inner sep=2pt] (t0) at ([xshift=-0.2em,yshift=-0.1em]t1.west) {$t_0$};
    \draw [-] (s1.south) -- ([yshift=-0.2em]t1.north);
    \draw [-] (s2.south) -- (t2.north);
    \visible<4->{
    \node [anchor=south east,inner sep=0pt] (p) at (t0.north west) {\small{{\color{ugreen} P(}}};
    \node [anchor=south west,inner sep=0pt] (p2) at ([yshift=0.2em]t2.north east) {\small{{\color{ugreen} )}}};
    \node [anchor=west] (eq) at (p2.east) {\small{+}};
    }
    }
    \end{scope}
    \begin{scope}[yshift=-1in]
    {\scriptsize
    \node [anchor=west,inner sep=2pt] (s1) at (0,0) {谢谢};
    \node [anchor=west,inner sep=2pt] (s2) at ([xshift=0.4em]s1.east) {你};
    \node [anchor=north,inner sep=2pt] (t1) at ([yshift=-1.2em]s1.center) {thank};
    \node [anchor=north,inner sep=2pt] (t2) at ([yshift=-1.45em]s2.center) {you};
    \node [anchor=east,inner sep=2pt] (t0) at ([xshift=-0.2em,yshift=-0.1em]t1.west) {$t_0$};
    \draw [-] (s1.south) -- (t2.north);
    \draw [-] (s2.south) -- (t0.north);
    \visible<4->{
    \node [anchor=south east,inner sep=0pt] (p) at (t0.north west) {\small{{\color{ugreen} P(}}};
    \node [anchor=south west,inner sep=0pt] (p2) at ([yshift=0.2em]t2.north east) {\small{{\color{ugreen} )}}};
    \node [anchor=west] (eq) at (p2.east) {\small{+}};
    }
    }
    \end{scope}
    \begin{scope}[xshift=1.2in,yshift=-1in]
    {\scriptsize
    \node [anchor=west,inner sep=2pt] (s1) at (0,0) {谢谢};
    \node [anchor=west,inner sep=2pt] (s2) at ([xshift=0.4em]s1.east) {你};
    \node [anchor=north,inner sep=2pt] (t1) at ([yshift=-1.2em]s1.center) {thank};
    \node [anchor=north,inner sep=2pt] (t2) at ([yshift=-1.45em]s2.center) {you};
    \node [anchor=east,inner sep=2pt] (t0) at ([xshift=-0.2em,yshift=-0.1em]t1.west) {$t_0$};
    \draw [-] (s1.south) -- (t2.north);
    \draw [-] (s2.south) -- (t1.north);
    \visible<4->{
    \node [anchor=south east,inner sep=0pt] (p) at (t0.north west) {\small{{\color{ugreen} P(}}};
    \node [anchor=south west,inner sep=0pt] (p2) at ([yshift=0.2em]t2.north east) {\small{{\color{ugreen} )}}};
    \node [anchor=west] (eq) at (p2.east) {\small{+}};
    }
    }
    \end{scope}
    \begin{scope}[xshift=2.4in,yshift=-1in]
    {\scriptsize
    \node [anchor=west,inner sep=2pt] (s1) at (0,0) {谢谢};
    \node [anchor=west,inner sep=2pt] (s2) at ([xshift=0.4em]s1.east) {你};
    \node [anchor=north,inner sep=2pt] (t1) at ([yshift=-1.2em]s1.center) {thank};
    \node [anchor=north,inner sep=2pt] (t2) at ([yshift=-1.45em]s2.center) {you};
    \node [anchor=east,inner sep=2pt] (t0) at ([xshift=-0.2em,yshift=-0.1em]t1.west) {$t_0$};
    \draw [-] (s1.south) -- (t2.north);
    \draw [-] (s2.south) -- (t2.north);
    \visible<4->{
    \node [anchor=south east,inner sep=0pt] (p) at (t0.north west) {\small{{\color{ugreen} P(}}};
    \node [anchor=south west,inner sep=0pt] (p2) at ([yshift=0.2em]t2.north east) {\small{{\color{ugreen} )}}};
    \node [anchor=west] (eq) at (p2.east) {\normalsize{= \ P($s|t$)}};
    }
    }
    \end{scope}
    \end{tikzpicture}
    \end{center}
    }

\end{itemize}
\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% modeling P(s,a|t)
\begin{frame}{建模 - $\textrm{P}(s,a|t)$}

\begin{itemize}

\item \alert{\textbf{进一步建模!!}}：对于源语句子$s=s_1...s_m$($m$个词)、目标语译文$t=t_0...t_n$($n$个词)和词对齐$a=a_1...a_m$，按如下方式计算$\textrm{P}(s,a|t)$

    \begin{itemize}
    \item 符号定义：$s_x^y=s_x...s_y$, $a_x^y=a_x...a_y$
    \end{itemize}


\vspace{-1.5em}

\begin{center}
\begin{tikzpicture}

\node [anchor=west] (eq1) at (0,0) {$\textrm{P}(s,a|t)=$};
\node [anchor=west,inner sep=1pt,minimum height=2.64em] (eq2) at (eq1.east) {$\textrm{P}(m|t)$};
\node [anchor=west,inner sep=1pt,minimum height=2.64em] (eq3) at ([xshift=1pt]eq2.east) {$\prod\limits_{j=1}^{m}$};
\node [anchor=west,inner sep=1pt,minimum height=2.64em] (eq4) at ([xshift=1pt]eq3.east) {$\textrm{P}(a_j|a_{1}^{j-1},s_{1}^{j-1},m,t)$};
\node [anchor=west,inner sep=1pt,minimum height=2.64em] (eq5) at ([xshift=1pt]eq4.east) {$\textrm{P}(s_j|a_{1}^{j},s_{1}^{j-1},m,t)$};

\visible<2->{
\node [anchor=west,inner sep=1pt,minimum height=2.64em,fill=red!20] (eq2) at (eq1.east) {$\textrm{P}(m|t)$};
}
\visible<3->{
\node [anchor=west,inner sep=1pt,minimum height=2.64em,fill=blue!20] (eq3) at ([xshift=1pt]eq2.east) {$\prod\limits_{j=1}^{m}$};
}
\visible<4->{
\node [anchor=west,inner sep=1pt,minimum height=2.64em,fill=green!20] (eq4) at ([xshift=1pt]eq3.east) {$\textrm{P}(a_j|a_{1}^{j-1},s_{1}^{j-1},m,t)$};
}
\visible<5->{
\node [anchor=west,inner sep=1pt,minimum height=2.64em,fill=purple!20] (eq5) at ([xshift=1pt]eq4.east) {$\textrm{P}(s_j|a_{1}^{j},s_{1}^{j-1},m,t)$};
}

\visible<2->{
\node [anchor=north,draw,circle,inner sep=1pt,ublue] (c1) at ([yshift=-1pt]eq2.south) {\tiny{\textbf{1}}};
}
\visible<3->{
\node [anchor=north,draw,circle,inner sep=1pt,ublue] (c2) at ([yshift=-1pt]eq3.south) {\tiny{\textbf{2}}};
}
\visible<4->{
\node [anchor=north,draw,circle,inner sep=1pt,ublue] (c3) at ([yshift=-1pt]eq4.south) {\tiny{\textbf{3}}};
}
\visible<5->{
\node [anchor=north,draw,circle,inner sep=1pt,ublue] (c4) at ([yshift=-1pt]eq5.south) {\tiny{\textbf{4}}};
}

\end{tikzpicture}
\end{center}

\vspace{-0.0em}

    \begin{itemize}
    \item<2-> \textbf{生成模型}：给定译文$t$生成源文$s$和对齐$a$
        \begin{enumerate}
        \item<2-> 根据译文$t$选择源文的长度$m$
        \item<3-> 循环源文的每个位置$j$
        \item<4-> 根据译文$t$、源文长度$m$、已经生成的源语单词$s_{1}^{j-1}$和对齐$a_{1}^{j-1}$，生成第$j$个位置的对齐结果$a_j$
        \item<5-> 根据译文$t$、源文长度$m$、已经生成的源语单词$s_{1}^{j-1}$和对齐$a_{1}^{j}$，生成第$j$个位置的源语言单词$s_j$（注意：这时$a_j$已经生成了）
        \end{enumerate}
    \end{itemize}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% generation of s and a given t -  a running example
\begin{frame}{实例 - $\textrm{P}(s,a|t)$}

$s$ = 在 桌子 上 \ \ \ \ \ $t$ = $t_0$ on the table \ \ \ \ \ $a$ = \{1-0,2-3,3-1\}

\begin{center}
\begin{tikzpicture}
\visible<1,5->{
\node [anchor=west,inner sep=2pt] (s1) at (0,0) {$s_1$:在};
}
\visible<1,7->{
\node [anchor=west,inner sep=2pt] (s2) at ([xshift=2em]s1.east) {$s_2$:桌子};
}
\visible<1>{
\node [anchor=west,inner sep=2pt] (s3) at ([xshift=2em]s2.east) {$s_3$:上};
}
\node [anchor=north,inner sep=2pt] (t1) at ([yshift=-2.4em]s1.center) {$t_1$:on};
\node [anchor=north,inner sep=2pt] (t2) at ([yshift=-2.4em]s2.center) {$t_2$:the};
\node [anchor=north,inner sep=2pt] (t3) at ([yshift=-2.4em]s3.center) {$t_3$:table};
\node [anchor=east,inner sep=2pt] (t0) at ([xshift=-2.2em]t1.west) {$t_0$};

\visible<1,4->{
\draw [-,thick] (s1.south) -- (t0.north);
}
\visible<1,6->{
\draw [-,thick] (s2.south) -- (t3.north);
}
\visible<1,8->{
\draw [-,thick] (s3.south) .. controls +(south:1.5em) and +(north:1.5em) .. (t1.north);
}

\visible<2-3>{
\node [anchor=center] at (s1) {$\bullet$};
}

\visible<2-5>{
\node [anchor=center] at (s2) {$\bullet$};
}

\visible<2-7>{
\node [anchor=center] at (s3) {$\bullet$};
}

\visible<4>{
\node [anchor=west,inner sep=2pt,fill=red!20] (s1) at (0,0) {$s_1$:在};
}
\visible<6>{
\node [anchor=west,inner sep=2pt,fill=red!20] (s2) at ([xshift=2em]s1.east) {$s_2$:桌子};
}
\visible<8>{
\node [anchor=west,inner sep=2pt,fill=red!20] (s3) at ([xshift=2em]s2.east) {$s_3$:上};
}
\visible<3>{
\draw [-,thick,red] (s1.south) -- (t0.north);
}
\visible<5>{
\draw [-,thick,red] (s2.south) -- (t3.north);
}
\visible<7>{
\draw [-,thick,red] (s3.south) .. controls +(south:1.5em) and +(north:1.5em) .. (t1.north);
}

\end{tikzpicture}
\end{center}

\vspace{-1.5em}

{\small
\begin{eqnarray}
\textrm{P}(s,a|t) & = & \textrm{P}(m|t) \prod\limits_{j=1}^{m} \textrm{P}(a_j|a_{1}^{j-1},s_{1}^{j-1},m,t) \textrm{P}(s_j|a_{1}^{j},s_{1}^{j-1},m,t) \nonumber \\
                  & \visible<2->{=} & \visible<2->{\textrm{P}(m=3 \mid \textrm{'$t_0$ on the table'})} \visible<3->{\times} \nonumber \\
                  &   & \visible<3->{\textrm{P}(a_1=0 \mid \phi,\phi,3,\textrm{'$t_0$ on the table'})} \visible<4->{\times} \nonumber \\
                  &   & \visible<4->{\textrm{P}(f_1=\textrm{在} \mid \textrm{\{1-0\}},\phi,3,\textrm{'$t_0$ on the table'})} \visible<5->{\times} \nonumber \\
                  &   & \visible<5->{\textrm{P}(a_2=3 \mid \textrm{\{1-0\}},\textrm{'在'},3,\textrm{'$t_0$ on the table'})} \visible<6->{\times} \nonumber \\
                  &   & \visible<6->{\textrm{P}(f_2=\textrm{桌子} \mid \textrm{\{1-0,2-3\}},\textrm{'在'},3,\textrm{'$t_0$ on the table'})} \visible<7->{\times} \nonumber \\
                  &   & \visible<7->{\textrm{P}(a_3=1 \mid \textrm{\{1-0,2-3\}},\textrm{'在 桌子'},3,\textrm{'$t_0$ on the table'})} \visible<8->{\times} \nonumber \\
                  &   & \visible<8->{\textrm{P}(f_3=\textrm{上} \mid \textrm{\{1-0,2-3,3-1\}},\textrm{'在 桌子'},3,\textrm{'$t_0$ on the table'})} \nonumber
\end{eqnarray}
}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% problems
\begin{frame}{问题来了}

\begin{itemize}

\item \textbf{\alert{重点}}：重新回顾一下这个模型 - 两个公式

\vspace{-1.0em}

\begin{eqnarray}
\textrm{P}(s|t) & = & \sum_{a} \textrm{P}(s,a|t)  \nonumber \\
\textrm{P}(s,a|t) & = & \textrm{P}(m|t) \prod\limits_{j=1}^{m} \textrm{P}(a_j|a_{1}^{j-1},s_{1}^{j-1},m,t) \textrm{P}(s_j|a_{1}^{j},s_{1}^{j-1},m,t)  \nonumber
\end{eqnarray}

\item \textbf{两个严重问题}
    \begin{enumerate}
    \item 第一个公式：如何遍历所有的对齐$a$
    \item 第二个公式：如何计算$\textrm{P}(m|t)$、$\textrm{P}(a_j|a_{1}^{j-1},s_{1}^{j-1},m,t)$和$\textrm{P}(s_j|a_{1}^{j},s_{1}^{j-1},m,t)$
    \end{enumerate}

\item<2-> Brown等人(1993)的解决方法：对问题进行化简
    \begin{itemize}
    \item IBM Models 1-2: 化简公式2的参数，精确高效求解公式1\\
    \alert{$\to$本教程内容}
    \item IBM Models 3-5: 简单化简公式2的参数，近似求解公式1\\
    \alert{$\to$自学内容}
    \end{itemize}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
\subsection{IBM模型1}

%%%------------------------------------------------------------------------------------------------------------
%%% assumptions in IBM Model 1
\begin{frame}{IBM模型1的假设}

\begin{itemize}

\item \textbf{IBM模型1假设}
    \begin{enumerate}
    \item 源语长度概率为常数$\epsilon$
    \begin{displaymath}
    \textrm{P}(m|t) \equiv \epsilon
    \end{displaymath}
    \item 对齐概率$\textrm{P}(a_j|a_{1}^{j-1},s_{1}^{j-1},m,t)$仅依赖于译文长度$l+1$(均匀分布)
    \begin{displaymath}
    \textrm{P}(a_j|a_{1}^{j-1},s_{1}^{j-1},m,t) \equiv \frac{1}{l+1}
    \end{displaymath}
    \item 源语单词$s_j$生成概率$\textrm{P}(s_j|a_{1}^{j},s_{1}^{j-1},m,t)$仅依赖与其对齐的译文单词$t_{a_j}$，即词汇翻译概率$f(s_j|t_{a_j})$ ($\sum_{s_j} f(s_j|t_{a_j}) = 1$)
    \begin{displaymath}
    \textrm{P}(s_j|a_{1}^{j},s_{1}^{j-1},m,t) \equiv f(s_j|t_{a_j})
    \end{displaymath}
    \end{enumerate}

\item<2-> \textbf{核心思想是}把复杂参数化简为简单参数
    \begin{itemize}
    \item 比如：$\textrm{P}(a_j|a_{1}^{j-1},s_{1}^{j-1},m,t) \equiv \frac{1}{l-1}$把参数空间$(a_{1}^{j},s_{1}^{j-1},m,t)$化简为$l$
    \item \alert{优点}: 模型大大化简；\alert{缺点}：化简导致模型不准确
    \end{itemize}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% the full model of IBM Model 1
\begin{frame}{IBM模型1 - 完整模型}

\begin{itemize}
\item \textbf{代入假设}

\vspace{-1em}

\begin{center}
\begin{tikzpicture}

\node [anchor=west] (eq1) at (0,0) {$\textrm{P}(s,a|t)$};
\node [anchor=west] (eq1part2) at (eq1.east) {$=$};
\node [anchor=west,inner sep=1pt] (eq2) at (eq1part2.east) {$\textrm{P}(m|t)$};
\node [anchor=west,inner sep=1pt] (eq3) at ([xshift=1pt]eq2.east) {$\prod\limits_{j=1}^{m}$};
\node [anchor=west,inner sep=1pt] (eq4) at ([xshift=1pt]eq3.east) {$\textrm{P}(a_j|a_{1}^{j-1},s_{1}^{j-1},m,t)$};
\node [anchor=west,inner sep=1pt] (eq5) at ([xshift=1pt]eq4.east) {$\textrm{P}(s_j|a_{1}^{j},s_{1}^{j-1},m,t)$};

\node [anchor=east,rotate=90] (yes1) at (eq2.south) {$\equiv$};
\node [anchor=east,rotate=90] (yes2) at (eq4.south) {$\equiv$};
\node [anchor=east,rotate=90] (yes3) at (eq5.south) {$\equiv$};

\node [anchor=north,inner sep=1pt] at (yes1.west) {$\epsilon$};
\node [anchor=north,inner sep=1pt] at (yes2.west) {$\frac{1}{l+1}$};
\node [anchor=north,inner sep=1pt] at (yes3.west) {$f(s_j|t_{a_j})$};

\node [anchor=west] (neweq1) at ([yshift=-5em]eq1part2.west) {$=$};
\node [anchor=west,inner sep=1pt] (neweq2) at (neweq1.east) {$\epsilon \prod\limits_{j=1}^{m} \frac{1}{l+1} f(s_j|t_{a_j})$};

\node [anchor=west] (new2eq1) at ([yshift=-2.5em]neweq1.west) {$=$};
\node [anchor=west,inner sep=1pt] (new2eq2) at (new2eq1.east) {$\frac{\epsilon}{(l+1)^{m}} \prod\limits_{j=1}^{m} f(s_j|t_{a_j})$};

\end{tikzpicture}
\end{center}

\item<2-> \textbf{将上式代入$\textrm{P}(s|t)=\sum_a \textrm{P}(s,a|t)$}

\vspace{-1.0em}

\begin{eqnarray}
\textrm{P}(s|t) & = & \sum\limits_{a} \textrm{P}(s,a|t) \nonumber \\
                & = & \sum\limits_{a} \frac{\epsilon}{(l+1)^{m}} \prod\limits_{j=1}^{m} f(s_j|t_{a_j}) \nonumber
\end{eqnarray}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% full model of IBM Model 1 - cont.
\begin{frame}{IBM模型1 - 完整模型(2)}

\begin{itemize}

\item $\textrm{P}(s|t) = \sum\limits_{a} \frac{\epsilon}{(l+1)^{m}} \prod\limits_{j=1}^{m} f(s_j|t_{a_j})$中需要对遍历所有的对齐，即$\sum_{a}$。这个过程可以被重新表示为

\vspace{-0.5em}

\begin{center}
\begin{tikzpicture}

\node [anchor=west] (eq1) at (0,0) {$\textrm{P}(s|t)$};
\node [anchor=west] (eq2) at (eq1.east) {$=$};
\node [anchor=west,inner sep=2pt] (eq3) at (eq2.east) {$\sum\limits_{a_1=0}^{l}$};
\node [anchor=west,inner sep=0] (eq4) at (eq3.east) {...};
\node [anchor=west,inner sep=2pt] (eq5) at (eq4.east) {$\sum\limits_{a_m=0}^{l}$};
\node [anchor=west,inner sep=2pt] (eq6) at ([xshift=0.2em]eq5.east) {$\frac{\epsilon}{(l+1)^{m}} \prod\limits_{j=1}^{m} f(s_j|t_{a_j})$};

\visible<3>{
\node [anchor=west,inner sep=2pt,fill=red!20] (eq3) at (eq2.east) {$\sum\limits_{a_1=0}^{l}$};
}
\visible<4>{
\node [anchor=west,inner sep=2pt,fill=red!20] (eq5) at (eq4.east) {$\sum\limits_{a_m=0}^{l}$};
}

\visible<6->{
\node [anchor=east] (label) at ([xshift=-0.5em,yshift=0.1em]eq1.west) {\alert{\textbf{IBM模型1:}}};
}

\begin{pgfonlayer}{background}
\visible<2-5>{
\node[rectangle,draw,ublue,inner sep=0.1em,fill=white] [fit = (eq3) (eq5)] (align) {};
\node [anchor=north,draw,circle,inner sep=1pt,ublue] (c1) at ([yshift=-1pt]align.south) {\tiny{\textbf{1}}};
}
\visible<5>{
\node[rectangle,draw,ublue,inner sep=0.0em,minimum height=3.2em,fill=white] [fit = (eq6)] (prob) {};
\node [anchor=north,draw,circle,inner sep=1pt,ublue] (c1) at ([yshift=-1pt]prob.south) {\tiny{\textbf{2}}};
}
\visible<6->{
\node[rectangle,draw,thick,red,inner sep=0.3em,minimum height=3em,fill=white] [fit = (label) (eq6)] (prob) {};
}
\end{pgfonlayer}

\end{tikzpicture}
\end{center}

    \begin{enumerate}
    \item<2-> 遍历所有的的对齐$a$。$a$由\{$a_1$,...,$a_m$\}组成，每个$a_j \in \{a_1,...,a_m\}$从第译文开始位置(0)循环到截止位置($l$)

    \vspace{0.5em}
    \begin{center}
    \begin{tikzpicture}

    \visible<3->{
    \node [anchor=west,inner sep=2pt] (s1) at (0,0) {$s_1$:在};
    \node [anchor=west,inner sep=2pt] (s2) at ([xshift=2em]s1.east) {$s_2$:桌子};
    \node [anchor=west,inner sep=2pt] (s3) at ([xshift=2em]s2.east) {$s_3$:上};

    \node [anchor=north,inner sep=2pt] (t1) at ([yshift=-2.4em]s1.center) {$t_1$:on};
    \node [anchor=north,inner sep=2pt] (t2) at ([yshift=-2.4em]s2.center) {$t_2$:the};
    \node [anchor=north,inner sep=2pt] (t3) at ([yshift=-2.4em]s3.center) {$t_3$:table};
    \node [anchor=east,inner sep=2pt] (t0) at ([xshift=-2.2em]t1.west) {$t_0$};
    }

    \visible<3>{
    \draw [-,dashed,thick] (s1.south) -- (t0);
    \draw [-,dashed,thick] (s1.south) -- (t1);
    \draw [-,dashed,thick] (s1.south) -- (t2);
    \draw [-,dashed,thick] (s1.south) -- (t3);
    }

    \visible<4->{
    \draw [-,dashed,thick] (s3.south) -- (t0);
    \draw [-,dashed,thick] (s3.south) -- (t1);
    \draw [-,dashed,thick] (s3.south) -- (t2);
    \draw [-,dashed,thick] (s3.south) -- (t3);
    }

    \end{tikzpicture}
    \end{center}
    \vspace{0.5em}

    \item<5-> 对于每个$a$累加对齐概率$\textrm{P}(s,a|t)$
    \end{enumerate}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
\subsection{IBM模型2}

%%%------------------------------------------------------------------------------------------------------------
%%% the assumptions in IBM Model 2
\begin{frame}{IBM模型2的假设}

\begin{itemize}

\item IBM模型1虽然形式非常简单，但是问题是忽略了翻译的调序问题。对于同一个源语言句子，单词翻译相同，但是译文顺序不同，模型得分（翻译概率相同）

\begin{center}
\begin{tikzpicture}

\begin{scope}

\node [anchor=west] (s1) at (0,0) {$s$ = 在\ \ 桌子\ \ 上};
\node [anchor=west] (t1) at ([yshift=-2em]s1.west) {$t$ = on\ \ the\ \ table};
\draw [->,double,thick,ublue] ([yshift=0.2em]s1.south) -- ([yshift=-0.8em]s1.south);

\end{scope}

\begin{scope}[xshift=1.5in]

\node [anchor=west] (s2) at (0,0) {$s$ = 在\ \ 桌子\ \ 上};
\node [anchor=west] (t2) at ([yshift=-2em]s2.west) {$t'$ = table \ on\ \ the};
\draw [->,double,thick,ublue] ([yshift=0.2em]s2.south) -- ([yshift=-0.8em]s2.south);

\end{scope}

\node [anchor=north] (score11) at ([yshift=-2.0em]s1.south) {$\textrm{P}(s|t)$};
\node [anchor=north] (score12) at ([yshift=-2.0em]s2.south) {$\textrm{P}(s|t')$};
\node [anchor=west] (comp1) at ([xshift=2.3em]score11.east) {\large{$\mathbf{=}$}};
\node [anchor=east] (label1) at ([xshift=-1em,yshift=0.1em]score11.west) {\textbf{IBM模型1:}};

\visible<2->{
\node [anchor=north] (score21) at ([yshift=0.2em]score11.south) {$\textrm{P}(s|t)$};
\node [anchor=north] (score22) at ([yshift=0.2em]score12.south) {$\textrm{P}(s|t')$};
\node [anchor=west] (comp2) at ([xshift=2.3em]score21.east) {\large{$\mathbf{>}$}};
\node [anchor=east] (label2) at ([xshift=-1em,yshift=0.1em]score21.west) {\textbf{理想:}};
}

\end{tikzpicture}
\end{center}

\vspace{-0.5em}

\item<3-> \textbf{IBM模型2的假设}：对齐位置$a_j$的生成概率与语言单词位置$j$，源语句子长度$m$和译文长度和$l$有关。记为$a(a_j|j,m,l)$，称作$a_j$的\alert{对齐概率}
    \vspace{-0.8em}

    \begin{displaymath}
    \textrm{P}(a_j|a_{1}^{j-1},s_{1}^{j-1},m,t) \equiv a(a_j|j,m,l)
    \end{displaymath}

    其它假设与IBM模型1相同，即$\textrm{P}(m|t) \equiv \epsilon$和$\textrm{P}(s_j|a_{1}^{j},s_{1}^{j-1},m,t) \equiv f(s_j|t_{a_j})$

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% the full model in IBM Model 2
\begin{frame}{IBM模型2 - 完整模型}

\begin{itemize}

\item \textbf{代入假设}

\vspace{-1em}

\begin{center}
\begin{tikzpicture}

\node [anchor=west] (eq1) at (0,0) {$\textrm{P}(s,a|t)$};
\node [anchor=west] (eq1part2) at (eq1.east) {$=$};
\node [anchor=west,inner sep=1pt] (eq2) at (eq1part2.east) {$\textrm{P}(m|t)$};
\node [anchor=west,inner sep=1pt] (eq3) at ([xshift=1pt]eq2.east) {$\prod\limits_{j=1}^{m}$};
\node [anchor=west,inner sep=1pt] (eq4) at ([xshift=1pt]eq3.east) {$\textrm{P}(a_j|a_{1}^{j-1},s_{1}^{j-1},m,t)$};
\node [anchor=west,inner sep=1pt] (eq5) at ([xshift=1pt]eq4.east) {$\textrm{P}(s_j|a_{1}^{j},s_{1}^{j-1},m,t)$};

\node [anchor=east,rotate=90] (yes1) at (eq2.south) {$\equiv$};
\node [anchor=east,rotate=90] (yes2) at (eq4.south) {$\equiv$};
\node [anchor=east,rotate=90] (yes3) at (eq5.south) {$\equiv$};

\node [anchor=north,inner sep=1pt] at (yes1.west) {$\epsilon$};
\node [anchor=north,inner sep=1pt] at (yes2.west) {$a(a_j|j,m,l)$};
\node [anchor=north,inner sep=1pt] at (yes3.west) {$f(s_j|t_{a_j})$};

\node [anchor=west] (neweq1) at ([yshift=-5em]eq1part2.west) {$=$};
\node [anchor=west,inner sep=1pt] (neweq2) at (neweq1.east) {$\epsilon \prod\limits_{j=1}^{m} a(a_j|j,m,l) f(s_j|t_{a_j})$};

\end{tikzpicture}
\end{center}

\item<2-> \textbf{将上式代入$\textrm{P}(s|t)=\sum_a \textrm{P}(s,a|t)$}

\vspace{-0.5em}

\begin{center}
\begin{tikzpicture}

\node [anchor=west] (eq1) at (0,0) {$\textrm{P}(s|t)$};
\node [anchor=west] (eq2) at (eq1.east) {$=$};
\node [anchor=west,inner sep=2pt] (eq3) at (eq2.east) {$\sum\limits_{a_1=0}^{l}$};
\node [anchor=west,inner sep=0] (eq4) at ([xshift=-0.2em]eq3.east) {...};
\node [anchor=west,inner sep=2pt] (eq5) at ([xshift=-0.4em]eq4.east) {$\sum\limits_{a_m=0}^{l}$};
\node [anchor=west,inner sep=2pt] (eq6) at ([xshift=0.2em]eq5.east) {$\epsilon \prod\limits_{j=1}^{m} a(a_j|j,m,l) f(s_j|t_{a_j})$};

\visible<3->{
\node [anchor=east] (label) at ([xshift=-0.0em,yshift=0.1em]eq1.west) {\alert{\textbf{IBM模型2:}}};
}

\begin{pgfonlayer}{background}
\visible<2>{
\node[rectangle,draw,ublue,inner sep=0.1em,fill=white] [fit = (eq3) (eq5)] (align) {};
\node [anchor=north,draw,circle,inner sep=1pt,ublue] (c1) at ([yshift=-1pt]align.south) {\tiny{\textbf{1}}};
}
\visible<2>{
\node[rectangle,draw,ublue,inner sep=0.0em,minimum height=3.2em,fill=white] [fit = (eq6)] (prob) {};
\node [anchor=north,draw,circle,inner sep=1pt,ublue] (c1) at ([yshift=-1pt]prob.south) {\tiny{\textbf{2}}};
}
\visible<3->{
\node[rectangle,draw,thick,red,inner sep=0.3em,minimum height=3em,fill=white] [fit = (label) (eq6)] (prob) {};
}
\end{pgfonlayer}

\end{tikzpicture}
\end{center}

\vspace{-0.5em}

    \begin{enumerate}
    \item 遍历所有的的对齐$a$
    \item 对于每个$a$累加对齐概率$\textrm{P}(s,a|t)$，即计算$\epsilon \prod\limits_{j=1}^{m} a(a_j|j,m,l) f(s_j|t_{a_j})$
    \end{enumerate}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% review the IBM Models 1-2
%%% model parameters
\begin{frame}{停顿一下，重新看看这两个模型}

\vspace{-1.0em}

\begin{eqnarray}
\textrm{\textbf{IBM模型1}}: \textrm{P}(s|t) & = & \frac{\epsilon}{(l+1)^{m}} \sum\limits_{a_1=0}^{l} ... \sum\limits_{a_m=0}^{l} \prod\limits_{j=1}^{m} f(s_j|t_{a_j}) \nonumber \\
\textrm{\textbf{IBM模型2}}: \textrm{P}(s|t) & = & \epsilon \sum\limits_{a_1=0}^{l} ... \sum\limits_{a_m=0}^{l} \prod\limits_{j=1}^{m} a(a_j|j,m,l) f(s_j|t_{a_j}) \nonumber
\end{eqnarray}

\begin{itemize}

\item 参数
    \begin{itemize}
    \item $\epsilon$为常量
    \item<2-> $f(s_j|t_{a_j})$: 给定单词$t_{a_j}$翻译为$s_j$的概率
    \item<3-> $a(a_j|j,m,l)$: 给定位置$j$和句对长度$m$和$l$，对齐$a_j$的概率
    \end{itemize}

    \begin{center}
    \begin{tikzpicture}

    \visible<2->{
    \node [anchor=west,inner sep=2pt] (s1) at (0,0) {$s_1$:在};
    \node [anchor=west,inner sep=2pt] (s2) at ([xshift=2em]s1.east) {$s_2$:桌子};
    \node [anchor=west,inner sep=2pt] (s3) at ([xshift=2em]s2.east) {$s_3$:上};

    \node [anchor=north,inner sep=2pt] (t1) at ([yshift=-2.4em]s1.center) {$t_1$:on};
    \node [anchor=north,inner sep=2pt] (t2) at ([yshift=-2.4em]s2.center) {$t_2$:the};
    \node [anchor=north,inner sep=2pt] (t3) at ([yshift=-2.4em]s3.center) {$t_3$:table};
    \node [anchor=east,inner sep=2pt] (t0) at ([xshift=-2.2em]t1.west) {$t_0$};

    \draw [-,dashed,thick] (s1.south) -- (t0.north);
    \draw [-,dashed,thick] (s2.south) -- (t3.north);
    \draw [-,dashed,thick] (s3.south) -- (t1.north);
    }

    \begin{pgfonlayer}{background}
    \visible<2>{
    \path [fill=red!20] (s2.north west) -- (s2.south west) -- (t3.north west) -- (t3.south west) -- (t3.south east) -- (t3.north east) -- (s2.south east) -- (s2.north east) -- (s2.north west);
    }
    \end{pgfonlayer}

    \visible<2>{
    \node [anchor=south,inner sep=1pt] (mark1) at (s2.north) {\alert{\tiny{表示给定'table'翻译为'桌子'的概率}}};
    \node [anchor=south west,inner sep=1pt] (mark1part2) at (mark1.north west) {\alert{\tiny{$f(s_2|t_{a_2})=f(\textrm{桌子}|\textrm{table})$}}};
    }

    \visible<3->{
    \draw [-,dashed,thick,red] (s2.south) -- (t3.north);

    \node [anchor=west,inner sep=1pt] (mark2) at ([xshift=0.1in]s3.south east) {\alert{\tiny{$a(a_j|j,m,l)=a(3|2,3,3)$}}};
    \node [anchor=north west,inner sep=1pt] (mark2part2) at (mark2.south west) {\alert{\tiny{表示对于位置$j=2$}}};
    \node [anchor=north west,inner sep=1pt] (mark2part3) at (mark2part2.south west) {\alert{\tiny{句子长度$m=3$和$l=3$}}};
    \node [anchor=north west,inner sep=1pt] (mark2part4) at (mark2part3.south west) {\alert{\tiny{对齐到目标语位置3($a_j=3$)的概率}}};

    \draw [->] (mark2.south west) -- ([yshift=0.1in,xshift=-0.1in]t3.north);
    }

    \end{tikzpicture}
    \end{center}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% review the IBM Models 1-2
%%% two problems - the computation problem and the training problem
\begin{frame}{停顿一下，重新看看这两个模型(2)}
\label{ibmmodelingend}

\vspace{-1.0em}

\begin{eqnarray}
\textrm{\textbf{IBM模型1}}: \textrm{P}(s|t) & = & \frac{\epsilon}{(l+1)^{m}} \sum\limits_{a_1=0}^{l} ... \sum\limits_{a_m=0}^{l} \prod\limits_{j=1}^{m} f(s_j|t_{a_j}) \nonumber \\
\textrm{\textbf{IBM模型2}}: \textrm{P}(s|t) & = & \epsilon \sum\limits_{a_1=0}^{l} ... \sum\limits_{a_m=0}^{l} \prod\limits_{j=1}^{m} a(a_j|j,m,l) f(s_j|t_{a_j}) \nonumber
\end{eqnarray}

\begin{spacing}{1.2}
\begin{itemize}

\item 对于翻译模型$\textrm{P}(s|t)$，再来回顾一下统计机器翻译的三个基本问题
    \begin{enumerate}
    \item \textbf{建模}：如何描述$\textrm{P}(s|t)$ \visible<2->{\alert{$\gets$ 已解！见上面两个公式}}
    \item \textbf{解码}：给定模型参数$\epsilon$、$a(a_j|j,m,l)$和$f(s_j|t_{a_j})$，如何利用上面的公式计算$\textrm{P}(s|t)$(语言模型计算暂不讨论)，并找到最佳译文$\hat{t}$ \visible<2->{\alert{$\gets$ 下面讨论}}
    \item \textbf{训练}；如何从数据中自动学习模型参数$\epsilon$、$a(a_j|j,m,l)$和$f(s_j|t_{a_j})$ \visible<2->{\alert{$\gets$ 下面讨论}}
    \end{enumerate}

\end{itemize}
\end{spacing}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
\subsection{解码}

%%%------------------------------------------------------------------------------------------------------------
%%% 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. 一个简单的翻译实例}}};

\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. IBM模型}}\\\gray{\textbf{\hspace{1.5em}$\bullet$  建模}}\\\black{\textbf{\hspace{1.5em}$\bullet$  解码}}\\\gray{\textbf{\hspace{1.5em}$\bullet$  模型训练}}};
}

\end{tikzpicture}
\end{center}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% decoding with IBM Models 1-2
\begin{frame}{解码 = 搜索 + 模型得分计算}
\label{ibmdecoding}

\begin{itemize}

\item \textbf{何为模型}：统计描述 + 参数

\vspace{-0.8em}

\begin{center}
\begin{tikzpicture}

\node [anchor=west] (model) at (0,0) {\footnotesize{$\textrm{P}(s|t) = \epsilon \sum\limits_{a_1=0}^{l} ... \sum\limits_{a_m=0}^{l} \prod\limits_{j=1}^{m} a(a_j|j,m,l) f(s_j|t_{a_j})$}};
\node [anchor=east] (modellabel) at ([yshift=0.1em]model.west) {\footnotesize{\textbf{问题的统计描述:}}};
\node [anchor=north west] (paras) at (model.south west) {\footnotesize{$\epsilon = ?;\ \ \forall a_j,j,m,l: a(a_j|j,m,l) = ?, f(s_j|t_{a_j}) = ?$}};
\node [anchor=east] (paraslabel) at ([yshift=0.1em]paras.west) {\footnotesize{\textbf{模型的参数:}}};

\begin{pgfonlayer}{background}
\node[rectangle,draw=ublue,red,inner sep=0.1em,fill=white] [fit = (model) (modellabel) (paras) (paraslabel)] {};
\end{pgfonlayer}

\end{tikzpicture}
\end{center}

\item<2-> \textbf{何为解码}：模型得分计算 + 找到模型得分最高的译文

\vspace{-0.8em}

\begin{center}
\begin{tikzpicture}

\node [anchor=west] (scoring) at (0,0) {\footnotesize{对任意的$s$和$t$，(高效地)计算$\textrm{P}(s|t)$(同时计算$\textrm{P}(t)$)}};
\node [anchor=east] (scoringlabel) at ([yshift=0.1em]scoring.west) {\footnotesize{\textbf{模型得分计算:}}};
\node [anchor=north west] (search) at (scoring.south west) {\footnotesize{对所有可能的$t$，找到模型得分($\textrm{P}(s|t)\textrm{P}(t)$)最高}};
\node [anchor=north west] (searchpart2) at ([yshift=0.3em]search.south west) {\footnotesize{的译文输出}};
\node [anchor=east] (searchlabel) at ([yshift=0.1em]search.west) {\footnotesize{\textbf{搜索:}}};

\begin{pgfonlayer}{background}
\node[rectangle,draw=ublue,red,inner sep=0.1em,fill=white] [fit = (scoring) (scoringlabel) (search) (searchlabel) (searchpart2)] {};
\end{pgfonlayer}

\end{tikzpicture}
\end{center}

\vspace{-0.7em}

    \begin{itemize}
    \item \textbf{搜索(解码)问题}前面的实例已经描述了一种解法（见{\color{ublue} \hyperref[simpledecodingalgorithm]{第\hspace{-0.2em}~\ref{simpledecodingalgorithm}页}}）：自左向右添加译文单词 + 剪枝技术。这里不再讨论，可以自行学习
    \item \textbf{剩下的问题是}：对于任意的$s$和$t$，如何\alert{高效地}计算$\textrm{P}(s|t)$
    \end{itemize}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% efficient ways of computing model score
\begin{frame}{模型得分的计算}

\begin{itemize}

\item $O((l+1)^m \cdot m)$ - IBM模型得分的直接计算几乎不可能！

\begin{displaymath}
\textrm{P}(s|t) = \frac{\epsilon}{(l+1)^{m}} \underbrace{\sum\limits_{a_1=0}^{l} ... \sum\limits_{a_m=0}^{l}}_{(l+1)^m\textrm{次循环}} \underbrace{\prod\limits_{j=1}^{m} f(s_j|t_{a_j})}_{m\textrm{次循环}}
\end{displaymath}

\item<2-> $O(l \cdot m)$ - 实际上我们可以做的更好

\vspace{-0.5em}

\begin{center}
\begin{tikzpicture}

\node [anchor=west] (eq1) at (0,0) {$\sum\limits_{a_1=0}^{l} ... \sum\limits_{a_m=0}^{l} \prod\limits_{j=1}^{m} f(s_j|t_{a_j})$};
\node [anchor=west] (eq1part2) at (eq1.east) {$=$};
\node [anchor=west,inner sep=2pt] (eq1part3) at (eq1part2.east) {$\prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i)$};
\visible<3->{
\node [anchor=west,inner sep=2pt,fill=red!20] (eq1part3) at (eq1part2.east) {$\prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i)$};
}

\visible<2>{
\draw[decorate,thick,decoration={brace,amplitude=5pt,mirror}] ([xshift=0.2em,yshift=0.2em]eq1part3.south west) -- ([xshift=-0.2em,yshift=0.2em]eq1part3.south east) node [pos=0.5,below,yshift=-0.2em] (label2) {\scriptsize{\textbf{$m \cdot l$次循环}}};
}

\visible<3->{
\node [anchor=west] (eq2) at ([xshift=5em,yshift=-4.5em]eq1.west) {$\textrm{P}(s|t) = \frac{\epsilon}{(l+1)^{m}} $};
\node [anchor=west,inner sep=2pt] (eq2part2) at ([xshift=-0.3em]eq2.east) {$\prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i)$};
\node [anchor=east] (eq2label) at ([xshift=-0em,yshift=0.2em]eq2.west) {\small{IBM模型1:}};

\node [anchor=west,inner sep=2pt,fill=red!20] (eq2part2) at ([xshift=-0.3em]eq2.east) {$\prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i)$};
}

\visible<4->{
\node [anchor=west] (eq3) at ([xshift=5em,yshift=-7.5em]eq1.west) {$\textrm{P}(s|t) = \epsilon$};
\node [anchor=west,inner sep=2pt] (eq3part2) at ([xshift=-0.3em]eq3.east) {$\prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} a(i|j,m,l) f(s_j|t_i)$};
\node [anchor=east] (eq3label) at ([xshift=-0em,yshift=0.2em]eq3.west) {\small{类似的，IBM模型2:}};
}

\begin{pgfonlayer}{background}
\visible<4->{
\node[rectangle,draw=red,inner sep=2pt] [fit = (eq2) (eq2part2) (eq2label) (eq3) (eq3part2) (eq3label)] {};
}
\end{pgfonlayer}

\visible<3->{
\draw [->,thick] ([xshift=-1em]eq1part3.south) .. controls +(south:1.3em) and +(north:1.3em) .. ([xshift=1em]eq2part2.north);
}

\end{tikzpicture}
\end{center}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% the trick used in computing the score
\begin{frame}{$\sum_{a_1=0}^{l} ... \sum_{a_m=0}^{l} \prod_{j=1}^{m} f(s_j|t_{a_j})=\prod_{j=1}^{m} \sum_{i=0}^{l} f(s_j|t_i)$}

\begin{itemize}

\item 定义$\alpha(x,y)$为一个函数，$x$和$y$是两个变量

\end{itemize}

\vspace{-0.0em}

\begin{center}
\begin{tikzpicture}

{\footnotesize
\node [anchor=west] (mid) at (0,0) {$\alpha(1,0)\alpha(2,0) + \alpha(1,0)\alpha(2,1) + \alpha(1,0)\alpha(2,2) +$};
\node [anchor=west] (mid2) at ([yshift=-2em]mid.west) {$\alpha(1,1)\alpha(2,0) + \alpha(1,1)\alpha(2,1) + \alpha(1,1)\alpha(2,2)+$};
\node [anchor=west] (mid3) at ([yshift=-2em]mid2.west) {$\alpha(1,2)\alpha(2,0) + \alpha(1,2)\alpha(2,1) + \alpha(1,2)\alpha(2,2)$};
}

\begin{pgfonlayer}{background}
\node[rectangle,draw=ublue,red,inner sep=0.1em,fill=white] [fit = (mid) (mid2) (mid3)] (exampleeq) {};
\end{pgfonlayer}

{\footnotesize
\visible<2->{
\node [anchor=north] (eq1) at ([xshift=2em,yshift=-2em]exampleeq.south west) {$\sum\limits_{y_1=0}^{2} \sum\limits_{y_2=0}^{2} \alpha(1,y_1)\alpha(2,y_2)$};
\node [anchor=west] (eq1part2) at ([xshift=-1em,yshift=-3em]eq1.west) {$=$};
\node [anchor=west] (eq1part3) at ([xshift=-0.5em]eq1part2.east) {$\sum\limits_{y_1=0}^{2} \sum\limits_{y_2=0}^{2} \prod\limits_{x=1}^{2} $};
\node [anchor=west,inner sep=2pt] (eq1part4) at ([xshift=-0.3em]eq1part3.east) {$\alpha(x,y_x)$};
}

\visible<3->{
\node [anchor=north] (eq2) at ([xshift=-2em,yshift=-2em]exampleeq.south east) {$(\alpha(1,0)+\alpha(1,1)+\alpha(1,2))\cdot$};
\node [anchor=west] (eq2part2) at ([yshift=-1.5em]eq2.west) {$(\alpha(2,0)+\alpha(2,1)+\alpha(2,2))$};
\node [anchor=west] (eq2part3) at ([xshift=2.1in]eq1part2.east){$=$};
\node [anchor=west] (eq2part4) at ([xshift=-0.5em]eq2part3.east){$\prod\limits_{x=1}^{2} \sum\limits_{y=0}^{2}$};
\node [anchor=west,inner sep=2pt] (eq2part5) at ([xshift=-0.3em]eq2part4.east){$\alpha(x,y)$};
}
}

\begin{pgfonlayer}{background}
\visible<2->{
\node[rectangle,draw=ublue,red,inner sep=0.1em,fill=white] [fit = (eq1) (eq1part2) (eq1part3)] (eq1full) {};
}
\visible<3->{
\node[rectangle,draw=ublue,red,inner sep=0.1em,fill=white] [fit = (eq2) (eq2part2) (eq2part3) (eq2part4)] (eq2full) {};
}
\end{pgfonlayer}

\visible<2->{
\draw [->,thick] ([xshift=-3em]exampleeq.south) .. controls +(south:1.5em) and +(north:1.5em) .. (eq1full.north);
}
\visible<3->{
\draw [->,thick] ([xshift=3em]exampleeq.south) .. controls +(south:1.5em) and +(north:1.5em) .. (eq2full.north);
}

\visible<4->{
\node [anchor=west] at ([xshift=0.7em]eq1full.east) {\LARGE{\textbf{=}}};
}

\visible<5->{
{\large
\node [anchor=west] (feq) at ([xshift=3em,yshift=-3em]eq1full.south west) {$\sum\limits_{a_1=0}^{l} ... \sum\limits_{a_m=0}^{l} \prod\limits_{j=1}^{m}$};
\node [anchor=west,inner sep=2pt,fill=blue!20] (feqpart2) at ([xshift=-0.3em]feq.east) {$f(s_j|t_{a_j})$};
\node [anchor=west,inner sep=1pt] (feqpart3) at (feqpart2.east) {=};
\node [anchor=west] (feqpart4) at (feqpart3.east) {$\prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l}$};
\node [anchor=west,inner sep=2pt,fill=blue!20] (feqpart5) at ([xshift=-0.3em]feqpart4.east) {$f(s_j|t_i)$};
}

\draw [->,thick] (eq1part4.south) .. controls +(south:2.5em) and +(north:2.5em) .. (feqpart2.north);
\draw [->,thick] (eq2part5.south) .. controls +(south:1.5em) and +(north:1.5em) .. (feqpart5.north);

\node [anchor=west,inner sep=2pt,fill=blue!20] (eq1part4) at ([xshift=-0.3em]eq1part3.east) {\footnotesize{$\alpha(x,y_x)$}};
\node [anchor=west,inner sep=2pt,fill=blue!20] (eq2part5) at ([xshift=-0.3em]eq2part4.east){\footnotesize{$\alpha(x,y)$}};

}

\end{tikzpicture}
\end{center}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
\subsection{训练}

%%%------------------------------------------------------------------------------------------------------------
%%% 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. 一个简单的翻译实例}}};

\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. IBM模型}}\\\gray{\textbf{\hspace{1.5em}$\bullet$  建模}}\\\gray{\textbf{\hspace{1.5em}$\bullet$  解码}}\\\black{\textbf{\hspace{1.5em}$\bullet$  模型训练}}};
}

\end{tikzpicture}
\end{center}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% objectives of training
\begin{frame}{训练 - 目标函数}

\begin{beamerboxesrounded}[upper=uppercolblue,lower=lowercolblue,shadow=true]{\textbf{训练 = 优化}}
在训练集上调整参数使得\alert{目标函数}的值达到最大（最小），此时的参数称作该模型在该目标函数下的\alert{最优解}

\vspace{-0.5em}

\begin{center}
\begin{tikzpicture}

\begin{scope}[scale=0.8]

\draw [-,very thick] (0,0) sin (1,1) cos (2,0) sin (3,-1) cos (4,0) sin (7,-1);
\draw [-latex,thick] (-0.5,-1.2) -- (8,-1.2);
\draw [-latex,thick] (-0.5,-1.2) -- (-0.5,1.3);
\draw [-,dashed] (1,1) -- (1,-1.2);

\node [anchor=north] at (1,-1.2) {\scriptsize{参数$x$的最优解}};
\node [anchor=center] at (1,-1.2) {$\bullet$};
\node [anchor=center] at (1,1) {$\bullet$};
\node [anchor=west] at (1.3,1) {\scriptsize{目标函数$f(x)$的最大值}};
\draw [<-] (6.5,-0.8) -- (7.0,-0.3);
\node [anchor=south west,inner sep=1pt] at (7.0,-0.3) {\scriptsize{$f(x)$}};

\end{scope}

\end{tikzpicture}
\end{center}

\end{beamerboxesrounded}

\begin{itemize}

\item<2-> \textbf{IBM模型的训练：对于给定的句对$(s,t)$，最大化翻译概率$\textrm{P}(s|t)$}。这里用符号$\textrm{P}_{\theta}(s|t)$表示概率由参数$\theta$决定

\begin{center}
\begin{tikzpicture}

\node [anchor=west] (eq1) at (0,0) {$\hat{\theta}$};
\node [anchor=west] (eq2) at ([yshift=-0.2em]eq1.east) {=};
\node [anchor=west,inner sep=2pt] (eq3) at ([yshift=-0.0em]eq2.east) {$\argmax$};
\node [anchor=north,inner sep=1pt] (eq3part2) at ([yshift=-0.2em]eq3.south) {\scriptsize{$\theta$}};
\node [anchor=west,inner sep=2pt] (eq4) at ([xshift=0.1em]eq3.east) {$\textrm{P}_{\theta}(s|t)$};

\visible<3->{
\node [anchor=west,inner sep=2pt,fill=red!20,minimum height=1.35em] (eq3) at ([yshift=-0.0em]eq2.east) {$\argmax$};
\node [anchor=west,inner sep=2pt,fill=green!20] (eq4) at ([xshift=0.1em]eq3.east) {$\textrm{P}_{\theta}(s|t)$};

\node [anchor=north,draw,inner sep=3pt,fill=red!20] (eq3label) at ([yshift=-1.5em]eq3.south west) {\footnotesize{\textbf{求最优参数}}};
\node [anchor=north,draw,inner sep=3pt,fill=green!20] (eq4label) at ([yshift=-1.5em]eq4.south east) {\footnotesize{\textbf{目标函数}}};

\draw [->,thick] ([xshift=-1em]eq3.south) .. controls +(south:1em) and +(north:1em) .. (eq3label.north);
\draw [->,thick] (eq4.south) .. controls +(south:1em) and +(north:1em) .. (eq4label.north);
}

\end{tikzpicture}
\end{center}


\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% maximizing the likelihood
\begin{frame}{极大似然估计}

\begin{itemize}

\item $\textrm{P}(s|t)$可以被看做是$(s,t)$上的\alert{似然}函数($L(s,t;\theta)$)。所谓\alert{极大似然估计}，就是要找到使$L(s,t;\theta)$达到最大的$\theta$：

    \vspace{-0.5em}

    \begin{displaymath}
    \{\hat{\theta}\} \subseteq \{\argmax_{\theta \in \Theta} L(s,t;\theta)\}
    \end{displaymath}

    \vspace{-0.3em}

    $L(s,t;\theta)$表示$L(\cdot)$依赖模型参数$\theta$（注意分号），$\{\hat{\theta}\}$表示可能有多组结果，$\Theta$表示参数空间

\vspace{0.5em}

\item<2-> 先不用考虑上面的公式。我们还是回归到原始问题：如何找到一组$\theta$使$\textrm{P}_{\theta}(s|t)$达到最大？\\
    \begin{itemize}
    \item \textbf{求函数最大值问题}。比如，我们可以对$\textrm{P}_{\theta}(s|t)$求导，令导数为零，得到极值点
    \end{itemize}

\end{itemize}

\vspace{-0.5em}

\visible<2->{
\begin{center}
\begin{tikzpicture}

\begin{scope}[scale=0.18]
\draw[-,thick,ublue,domain=-4.2:3.5,samples=100] plot (\x,{ - 1/14 * (\x + 4) * (\x + 1) * (\x - 1) * (\x - 3)});
\draw[->] (-6,0) -- (5,0);
\draw[->] (-5,-5) -- (-5,5);
\node[anchor=north,inner sep=1pt] at (4.5,-0.3) {\tiny{$\theta$}};
\node[anchor=west,inner sep=1pt] (label1) at (2.0,4.5) {\tiny{$g(\theta)$}};
\draw[->] ([xshift=-3em]label1.south) -- (2.3,2);
\end{scope}

\draw[->,double,thick] (0.6in,0) -- (0.9in,0) node [pos=0.5,below,yshift=-3pt] {\tiny{\textbf{求导}}};

\begin{scope}[scale=0.18,xshift=8.5in]
\draw[-,thick,ublue,domain=-3.5:3.0,samples=100] plot (\x,{ - 1/14 * (4*\x*\x*\x + 3*\x*\x - 26*\x - 1)});
\draw[->] (-6,0) -- (5,0);
\draw[->] (-5,-5) -- (-5,5);
\node[anchor=north,inner sep=1pt] at (4.5,-0.3) {\tiny{$\theta$}};
\node[anchor=west,inner sep=1pt] (label1) at (2.0,4.5) {\tiny{$\frac{\partial g(\theta)}{\partial \theta}$}};
\draw[->] ([xshift=-3em]label1.south) -- (2.3,2);
\node [red] at (0,0) {\tiny{$\bullet$}};
\node [red] at (-3.0,0) {\tiny{$\bullet$}};
\node [red] at (2.2,0) {\tiny{$\bullet$}};
\end{scope}

\draw[->,double,thick] (2.1in,0) -- (2.4in,0) node [pos=0.5,below,yshift=-3pt] (ltmp) {\tiny{\textbf{令$\frac{\partial g(\theta)}{\partial \theta}=0$}}};
\node [anchor=north west] at ([yshift=5pt]ltmp.south west) {\tiny{\textbf{求极值点}}};

\begin{scope}[scale=0.18,xshift=17in]
\draw[-,thick,ublue,domain=-4.2:3.5,samples=100] plot (\x,{ - 1/14 * (\x + 4) * (\x + 1) * (\x - 1) * (\x - 3)});
\draw[-,dashed,ublue,domain=-3.8:3.0,samples=100] plot (\x,{ - 1/14 * (4*\x*\x*\x + 3*\x*\x - 26*\x - 1)});
\draw[->] (-6,0) -- (5,0);
\draw[->] (-5,-5) -- (-5,5);
\node[anchor=north,inner sep=1pt] at (4.5,-0.3) {\tiny{$\theta$}};

%\node [red] at (0,0) {\tiny{$\bullet$}};
\node [red] at (-3.0,0) {\tiny{$\bullet$}};
%\node [red] at (2.2,0) {\tiny{$\bullet$}};
\draw[-,red] (-3,0)--(-3,3.3);
\node [red] at (-3.0,3.3) {\tiny{$\bullet$}};
\node[anchor=south,inner sep=1pt] (label1) at (-3.0,6) {\tiny{\textbf{最大值}}};
\draw[->] ([xshift=1em]label1.south) -- (-3.0,4);

\node[anchor=south,inner sep=1pt] (label2) at (-3.0,-5) {\tiny{\textbf{最优$\theta$}}};
\draw[->] ([xshift=-1em]label2.north) -- (-3.1,-1.0);
\end{scope}

\end{tikzpicture}
\end{center}
}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% maximizing P(s|t)
\begin{frame}{最大化$\textrm{P}(s|t)$}

\begin{itemize}

\item 以IBM模型1为例，它所对应的(基于极大似然估计）的\alert{模型训练问题}可以被描述为：

\vspace{-0.8em}

\begin{center}
\begin{tikzpicture}

{\large
\node [anchor=west,minimum height=3em,inner sep=2pt] (eq11) at (0,0) {max};
\node [anchor=west,inner sep=2pt] (eq12) at ([xshift=2pt]eq11.east) {$\Big( \frac{\epsilon}{(l+1)^{m}} \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l}$};
\node [anchor=west,inner sep=2pt] (eq13) at (eq12.east) {$f(s_j|t_i)$};
\node [anchor=west,inner sep=2pt] (eq14) at ([yshift=0.2em]eq13.east) {$\Big)$};

\node [anchor=north west,minimum height=1.8em,inner sep=2pt] (eq21) at ([yshift=-0.5em]eq11.south west) {s.t.};
\node [anchor=west] (eq22) at ([xshift=0.5em,yshift=-0.1em]eq21.east) {\normalsize{for each word $t_y$}:};
\node [anchor=west] (eq23) at ([xshift=0.1em,yshift=-0.0em]eq22.east) {$\sum_{s_x} f(s_x|t_y) = 1$};

\visible<2->{
\node [anchor=west,minimum height=3em,inner sep=2pt,fill=green!20] (eq11) at (0,0) {max};
\node [anchor=west,draw,thin,ublue,inner sep=2pt,fill=blue!20] (eq13) at (eq12.east) {\black{$f(s_j|t_i)$}};

\node [anchor=north west,minimum height=1.8em,inner sep=2pt,fill=purple!20] (eq21) at ([yshift=-0.5em]eq11.south west) {s.t.};
\node [anchor=west,fill=orange!20] (eq23) at ([xshift=0.1em,yshift=-0.0em]eq22.east) {$\sum_{s_x} f(s_x|t_y) = 1$};
}

\begin{pgfonlayer}{background}
\visible<2->{
\node[rectangle,red,inner sep=0pt,fill=red!20] [fit = (eq12) (eq13) (eq14)] (eq1full) (eq1obj) {};
}
\end{pgfonlayer}
}

\visible<2->{
\node [anchor=west,draw,fill=green!20] (label1) at ([xshift=-2em,yshift=3em]eq11.north west) {最大化函数};
\node [anchor=west,draw,fill=red!20] (label2) at ([xshift=4em]label1.east) {目标函数};
\node [anchor=west,draw,fill=blue!20] (label3) at ([xshift=4em]label2.east) {参数};

\node [anchor=west,draw,fill=purple!20] (label4) at ([xshift=-2em,yshift=-2.5em]eq21.south west) {subject to=满足...约束};
\node [anchor=west,draw,fill=orange!20] (label5) at ([xshift=3em]label4.east) {翻译概率归一化约束条件};

\draw [<-,thick] ([xshift=-2em]label1.south) .. controls +(south:2em) and +(north:2em) .. (eq11.north);
\draw [<-,thick] ([xshift=-0em]label2.south) .. controls +(south:1.7em) and +(north:1.7em) .. (eq1obj.north);
\draw [<-,thick] ([xshift=-0em]label3.south) .. controls +(south:2.5em) and +(north:2.5em) .. (eq13.north);
\draw [<-,thick] ([xshift=2em]label4.north) .. controls +(north:1.5em) and +(south:1.5em) .. (eq21.south);
\draw [<-,thick] ([xshift=0em]label5.north) .. controls +(north:1.0em) and +(south:1.0em) .. (eq23.south);
}

\end{tikzpicture}
\end{center}

    \begin{itemize}
    \item<2-> \alert{注意}：\{$f(s_x|t_y)$\}对应很多参数，每个源语言单词和每个目标语单词的组合都对应一个$f(s_x|t_y)$
    \end{itemize}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% optimizaton -  Lagrange multipliers
\begin{frame}{拉格朗日乘数法 - Lagrange multiplier}

\begin{itemize}

\item \textbf{含有约束的优化问题}: 不好解\\
      \textbf{目标:} $\max(\textrm{P}_{\theta}(s|t))$ + \textbf{约束:} $\forall t_y: \sum_{s_x} \textrm{P}(s_x|t_y)=1$

\vspace{0.3em}
\item<2-> \textbf{解决方法}: 含有约束优化 $\Rightarrow$ 不含约束优化\\
\vspace{0.3em}
\begin{beamerboxesrounded}[upper=uppercolblue,lower=lowercolblue,shadow=true,width=\linewidth]{\textbf{拉格朗日乘数法 - 百度百科}}

{\small
      \textit{\alert{拉格朗日乘数法}是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法。这种方法将一个有$n$个变量与$k$个约束条件的最优化问题转换为一个有$n+ k$个变量的方程组的极值问题，其变量不受任何约束。这种方法引入了一种新的标量未知数，即拉格朗日乘数。}
}
\end{beamerboxesrounded}

    \begin{itemize}
    \item 对于每个$t_y$所对应的约束，引入一个拉格朗日乘数$\lambda_{t_y}$
    \end{itemize}

    \vspace{-1em}

    {\small
    \begin{eqnarray}
    L(f,\lambda) & = & \frac{\epsilon}{(l+1)^{m}} \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} \prod\limits_{j=1}^{m} f(s_j|t_i) - \nonumber \\
                 &   & \sum_{t_y} \lambda_{t_y} (\sum_{s_x} f(s_x|t_y) -1) \nonumber
    \end{eqnarray}
    }

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% illustration -  Lagrange multipliers
\begin{frame}{拉格朗日乘数法 - Lagrange multiplier (2)}

\begin{center}
\begin{tabular}{c | c}
\makebox[0.35\textwidth][c]{\textbf{原始问题}} & \makebox[0.35\textwidth][c]{\textbf{转化后的问题}} \\ \hline
$\max (\textrm{P}(s|t))$ & $\max (L(f,\lambda))$ \\
s.t. $\forall t_y: \sum_{s_x} f(s_x|t_y) =1 $ & \\
\end{tabular}
\end{center}


\begin{center}
\begin{tikzpicture}

\node [anchor=west,inner sep=2pt,fill=green!20] (eq1) at (0,0) {$L(f,\lambda)$};
\node [anchor=west,inner sep=2pt] (eq2) at (eq1.east) {$=$};
\node [anchor=west,inner sep=2pt] (eq3) at (eq2.east) {$\frac{\epsilon}{(l+1)^{m}} \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l}$};
\node [anchor=west,inner sep=2pt] (eq4) at (eq3.east) {\black{$f(s_j|t_{i})$}};
\node [anchor=west,inner sep=2pt] (eq5) at (eq4.east) {$-$};
\node [anchor=north west,inner sep=2pt] (eq6) at ([yshift=-6pt]eq3.south west) {$\sum_{t_y}$};
\node [anchor=west,inner sep=1pt,minimum height=1.85em] (eq7) at (eq6.east) {$\lambda_{t_y}$};
\node [anchor=west,inner sep=1pt,minimum height=1.5em] (eq8) at ([xshift=3pt]eq7.east) {$(\sum_{s_x}$};
\node [anchor=west,inner sep=1pt,minimum height=1.5em] (eq9) at (eq8.east) {\black{$f(s_x|t_y)$}};
\node [anchor=west,inner sep=1pt,minimum height=1.5em] (eq10) at (eq9.east) {$-1)$};

\visible<2->{
\node [anchor=west,inner sep=2pt,fill=green!20] (eq1) at (0,0) {$L(f,\lambda)$};
\node [anchor=west,inner sep=2pt] (eq2) at (eq1.east) {$=$};
\node [anchor=west,inner sep=2pt] (eq3) at (eq2.east) {$\frac{\epsilon}{(l+1)^{m}} \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l}$};
\node [anchor=west,inner sep=2pt,draw,ublue,fill=blue!20] (eq4) at (eq3.east) {\black{$f(s_j|t_{i})$}};
\node [anchor=west,inner sep=2pt] (eq5) at (eq4.east) {$-$};
\node [anchor=north west,inner sep=2pt] (eq6) at ([yshift=-6pt]eq3.south west) {$\sum_{t_y}$};
\node [anchor=west,inner sep=1pt,fill=purple!20,minimum height=1.85em] (eq7) at (eq6.east) {$\lambda_{t_y}$};
\node [anchor=west,inner sep=1pt,minimum height=1.5em] (eq8) at ([xshift=3pt]eq7.east) {$(\sum_{s_x}$};
\node [anchor=west,inner sep=1pt,draw,ublue,fill=blue!20,minimum height=1.5em] (eq9) at (eq8.east) {\black{$f(s_x|t_y)$}};
\node [anchor=west,inner sep=1pt,minimum height=1.5em] (eq10) at (eq9.east) {$-1)$};
}

\begin{pgfonlayer}{background}
\node[rectangle,red,inner sep=2pt,fill=red!20] [fit = (eq3) (eq4)] (oldobj) {};
\visible<2->{
\node[rectangle,red,inner sep=2pt,fill=orange!20] [fit = (eq8) (eq9) (eq10)] (constraint) {};
}
\end{pgfonlayer}

\node [anchor=west,draw,fill=green!20] (label1) at ([xshift=-2em,yshift=3em]eq1.north west) {新目标函数};
\node [anchor=west,draw,fill=red!20] (label2) at ([xshift=2em]label1.east) {旧目标函数};

\visible<2->{
\node [anchor=west,draw,fill=blue!20] (label3) at ([xshift=2em]label2.east) {参数：词翻译概率};
\node [anchor=west,draw,fill=purple!20] (label4) at ([xshift=-4em,yshift=-2.5em]eq6.south west) {参数：拉格朗日乘数};
\node [anchor=west,draw,fill=orange!20] (label5) at ([xshift=3em]label4.east) {参数约束条件};
}

\draw [<-,thick] ([xshift=-1em]label1.south) .. controls +(south:2em) and +(north:2em) .. (eq1.north);
\draw [<-,thick] ([xshift=-1em]label2.south) .. controls +(south:1.0em) and +(north:1.0em) .. (oldobj.north);

\visible<2->{
\draw [<-,thick] ([xshift=0em]label3.south) .. controls +(south:6.5em) and +(north:1.5em) .. (eq9.north);
\draw [<-,thick] ([xshift=0em]label3.south) .. controls +(south:1.5em) and +(north:1.5em) .. (eq4.north);
\draw [<-,thick] ([xshift=-2em]label4.north) .. controls +(north:1.5em) and +(south:1.5em) .. (eq7.south);
\draw [<-,thick] ([xshift=0em]label5.north) .. controls +(north:1.5em) and +(south:1.5em) .. (constraint.south);
}

\end{tikzpicture}
\end{center}

\begin{itemize}
\item<3-> \textbf{剩下的问题}：计算$\frac{\partial L(f,\lambda)}{\partial f(s_u|t_v)}$，并求解$\frac{\partial L(f,\lambda)}{\partial f(s_u|t_v)} = 0$
\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% d L / d \theta = ?
\begin{frame}{对$L$求导}

\begin{itemize}
\item 令$s_u$和$t_v$表示任意一个源语单词和一个目标语单词
\vspace{-0.5em}
\begin{eqnarray}
\frac{\partial L(f,\lambda)}{\partial f(s_u|t_v)} & = & \frac{\partial \big[ \frac{\epsilon}{(l+1)^{m}} \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i) \big]}{\partial f(s_u|t_v)} - \nonumber \\
 &   & \frac{\partial \big[ \sum_{t_y} \lambda_{t_y} (\sum_{s_x} f(s_x|t_y) -1) \big]}{\partial f(s_u|t_v)} \nonumber \\
 & = & \frac{\epsilon}{(l+1)^{m}} \cdot \frac{\partial \big[ \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_{a_j}) \big]}{\partial f(s_u|t_v)} - \lambda_{t_v} \nonumber
\end{eqnarray}

\vspace{-0.3em}

\item<2-> 为了求$\frac{\partial \big[ \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i) \big]}{\partial f(s_u|t_v)}$，先看一个简单的例子： $g(z)=\alpha z^{\beta}$为一个变量$z$的多项式函数，显然
\vspace{-0.3em}
\begin{displaymath}
\frac{\partial g(z)}{\partial z} = \alpha \beta z^{\beta-1} = \frac{\beta}{z}\alpha z^{\beta} = \frac{\beta}{z} g(z)
\end{displaymath}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% d L / d \theta = ? (continued)
\begin{frame}{对$L$求导(2)}
\begin{itemize}
\item 这里可以把$\prod_{j=1}^{m} \sum_{i=0}^{l} f(s_j|t_i)$看做$g(z)=\alpha z^{\beta}$的实例
    \begin{itemize}
    \item 令$z=\sum_{i=0}^{l}f(s_u|t_i)$，注意$s_u$为给定的源语单词
    \item 那么$\beta$为$\sum_{i=0}^{l}f(s_u|t_i)$在$\prod_{j=1}^{m} \sum_{i=0}^{l} f(s_j|t_i)$中出现的次数，即源语句子中与$s_u$相同的单词的个数
    \end{itemize}
    \begin{displaymath}
    \beta=\sum_{j=1}^{m} \delta(s_j,s_u)
    \end{displaymath}
    $\delta(x,y)$：当$x=y$时为1，否则为0
    \vspace{0.5em}
\item<2-> 根据$\frac{\partial g(z)}{\partial z} = \frac{\beta}{z} g(z)$
    \begin{displaymath}
    \frac{\partial g(z)}{\partial z} = \frac{\partial \big[ \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i) \big]}{\partial \big[ \sum\limits_{i=0}^{l}f(s_u|t_i) \big]} = \frac{\sum\limits_{j=1}^{m} \delta(s_j,s_u)}{\sum\limits_{i=0}^{l}f(s_u|t_i)} \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i)
    \end{displaymath}
\end{itemize}
\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% d L / d \theta = ? (continued)
\begin{frame}{对$L$求导(3)}
\begin{itemize}
\item 如果把$z$看成$f$的函数，有$\frac{\partial g(z)}{\partial f} = \frac{\partial g(z)}{\partial z} \cdot \frac{\partial z}{\partial f}$
    \begin{itemize}
    \item \textbf{因为}$z=\sum_{i=0}^{l}f(s_u|t_i)$，很容易得到
    \begin{displaymath}
    \frac{\partial z}{\partial f} = \frac{\partial \big[ \sum_{i=0}^{l}f(s_u|t_i) \big]}{\partial f(s_u|t_v)} = \sum_{i=0}^{l} \delta(t_i,t_v)
    \end{displaymath}
    即目标语译文单词中与$t_v$相同的个数
    \vspace{0.5em}
    \item<2-> \textbf{根据}$\frac{\partial g(z)}{\partial z}$和$\frac{\partial z}{\partial f}$计算的结果，可以得到
    \begin{center}
    \begin{tikzpicture}
    \node[anchor=west,inner sep=2pt] (eq11) at (0,0) {\large{$\frac{\partial \big[ \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i) \big]}{\partial f(s_u|t_v)}$}};
    \node[anchor=west,inner sep=2pt] (eq12) at ([yshift=-9pt]eq11.east) {=};
    \node[anchor=west,inner sep=2pt,fill=red!20] (eq13) at ([yshift=2pt]eq12.east) {\large{$\frac{\partial \big[ \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i) \big]}{\partial \big[ \sum\limits_{i=0}^{l}f(s_u|t_i) \big]}$}};
    \node[anchor=west,inner sep=2pt] (eq14) at ([yshift=-1pt]eq13.east) {$\cdot$};
    \node[anchor=west,inner sep=2pt,fill=blue!20,minimum height=4em] (eq15) at ([yshift=8pt]eq14.east) {\large{$\frac{\partial \big[ \sum\limits_{i=0}^{l}f(s_u|t_i) \big]}{\partial f(s_u|t_v)}$}};
    \node[anchor=south,inner sep=1pt] (label1) at ([yshift=1pt]eq13.north) {\footnotesize{$\partial g(z)/\partial z$}};
    \node[anchor=south,inner sep=1pt] (label2) at ([yshift=1pt]eq15.north) {\footnotesize{$\partial z/\partial f$}};
    \node[anchor=north west,inner sep=2pt] (eq21) at (eq13.south west) {$\frac{\sum\limits_{j=1}^{m} \delta(s_j,s_u)}{\sum\limits_{i=0}^{l}f(s_u|t_i)} \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i) \cdot \sum\limits_{i=0}^{l} \delta(t_i,t_v)$};
    \node[anchor=east,inner sep=2pt] (eq20) at (eq21.west) {=};
    \end{tikzpicture}
    \end{center}
    \end{itemize}
\end{itemize}
\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% d L / d \theta = ? (continued)
\begin{frame}{对$L$求导(4)}
\begin{itemize}
\item 将$\frac{\partial \big[ \prod_{j=1}^{m} \sum_{i=0}^{l} f(s_j|t_i) \big]}{\partial f(s_u|t_v)}$进一步代入$\frac{\partial L(f,\lambda)}{\partial f(s_u|t_v)}$
\end{itemize}
{\small
\begin{eqnarray}
&   & \frac{\partial L(f,\lambda)}{\partial f(s_u|t_v)} \nonumber \\
& = & \frac{\epsilon}{(l+1)^{m}} \cdot \alert{\frac{\partial \big[ \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_{a_j}) \big]}{\partial f(s_u|t_v)}} - \lambda_{t_v} \nonumber \\
& = & \frac{\epsilon}{(l+1)^{m}} \cdot \alert{\frac{\sum_{j=1}^{m} \delta(s_j,s_u) \cdot \sum_{i=0}^{l} \delta(t_i,t_v)}{\sum_{i=0}^{l}f(s_u|t_i)} \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i)} - \lambda_{t_v} \nonumber
\end{eqnarray}
}

\begin{itemize}
\item<2-> 令$\frac{\partial L(f,\lambda)}{\partial f(s_u|t_v)}=0$，有
\end{itemize}

\vspace{-1em}

\visible<2->{
{\small
\begin{displaymath}
f(s_u|t_v) = \frac{\lambda_{t_v}^{-1} \epsilon}{(l+1)^{m}} \cdot \frac{\sum\limits_{j=1}^{m} \delta(s_j,s_u) \cdot \sum\limits_{i=0}^{l} \delta(t_i,t_v)}{\sum\limits_{i=0}^{l}f(s_u|t_i)} \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i) \cdot f(s_u|t_v)
\end{displaymath}
}
}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% learning P(s_u |t_v) - EM
\begin{frame}{求$f(s_u |t_v)$的最优解 - 这不是一个解析式！！！}
\begin{itemize}
\item \alert{注意}：这不是一个计算$f(s_u |t_v)$的解析式，因为等式右端仍含有$f(s_u |t_v)$
\end{itemize}

\vspace{-1em}

\begin{center}
\begin{tikzpicture}

{\small
\node [anchor=west,inner sep=2pt,fill=red!20,minimum height=3em] (eq1) at (0,0) {$f(s_u|t_v)$};
\node [anchor=west,inner sep=2pt] (eq2) at ([xshift=-2pt]eq1.east) {$=$};
\node [anchor=west,inner sep=2pt] (eq3) at ([xshift=-2pt]eq2.east) {$\lambda_{t_v}^{-1}$};
\node [anchor=west,inner sep=2pt] (eq4) at ([xshift=-2pt]eq3.east) {$\frac{\epsilon}{(l+1)^{m}}$};
\node [anchor=west,inner sep=2pt,fill=red!20,minimum height=3em] (eq5) at ([xshift=-2pt]eq4.east) {\footnotesize{$\prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i)$}};
\node [anchor=west,inner sep=2pt] (eq6) at ([xshift=-2pt]eq5.east) {\footnotesize{$\sum\limits_{j=1}^{m} \delta(s_j,s_u) \sum\limits_{i=0}^{l} \delta(t_i,t_v)$}};
\node [anchor=west,inner sep=2pt,fill=red!20,minimum height=3em] (eq7) at ([xshift=-2pt,yshift=-0pt]eq6.east) {$\frac{f(s_u|t_v)}{\sum_{i=0}^{l}f(s_u|t_i)}$};
}

\end{tikzpicture}
\end{center}

\vspace{-0.5em}

\begin{itemize}
\item<2-> \textbf{怎么办?} - 我们仍可以利用上式迭代地计算$f(s_u |t_v)$，使其最终收敛到最优值
    \begin{itemize}
    \item 这是一个非常经典的方法，称作期望最大化(Expectation Maximization)，简称EM方法(或算法)
    \item \textbf{思想}：用当前的参数，求一个似然函数的期望，之后最大化这个期望值同时得到新的一组参数的值
    \item \textbf{对于IBM模型，很简单}：反复使用上式即可！
    \end{itemize}
\end{itemize}

\vspace{-1.3em}

\visible<2->{
\begin{center}
\begin{tikzpicture}

\node [anchor=west,inner sep=2pt,fill=red!20,minimum height=3em] (eq1) at (0,0) {$f(s_u|t_v)$};
\node [anchor=west,inner sep=2pt] (eq2) at ([xshift=-2pt]eq1.east) {$=$};
\node [anchor=west,inner sep=2pt] (eq3) at ([xshift=-2pt]eq2.east) {$\lambda_{t_v}^{-1}$};
\node [anchor=west,inner sep=2pt] (eq4) at ([xshift=-2pt]eq3.east) {$\frac{\epsilon}{(l+1)^{m}}$};
\node [anchor=west,inner sep=2pt,fill=red!20,minimum height=3em] (eq5) at ([xshift=-2pt]eq4.east) {\footnotesize{$\prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i)$}};
\node [anchor=west,inner sep=2pt] (eq6) at ([xshift=-2pt]eq5.east) {\footnotesize{$\sum\limits_{j=1}^{m} \delta(s_j,s_u) \sum\limits_{i=0}^{l} \delta(t_i,t_v)$}};
\node [anchor=west,inner sep=2pt,fill=red!20,minimum height=3em] (eq7) at ([xshift=-2pt,yshift=-0pt]eq6.east) {$\frac{f(s_u|t_v)}{\sum_{i=0}^{l}f(s_u|t_i)}$};

\node [anchor=south west,inner sep=2pt] (label1) at ([yshift=1em]eq1.north west) {\footnotesize{\textbf{新的参数值}}};
\node [anchor=south east,inner sep=2pt] (label2) at ([yshift=1em,xshift=-5em]eq7.north east) {\footnotesize{\textbf{旧的参数值}}};


\draw [<-,thick] (label1.south) .. controls +(south:1em) and +(north:1em) .. ([xshift=-1em]eq1.north);
\draw [<-,thick] (label2.south) .. controls +(300:1em) and +(north:1em) .. ([xshift=1em]eq7.north);
\draw [<-,thick] ([xshift=-0.5em]label2.south) .. controls +(240:1em) and +(north:1em) .. ([xshift=1em]eq5.north);

\visible<3->{
\node [anchor=west,inner sep=2pt,fill=blue!20,minimum height=3em] (eq3) at ([xshift=-2pt]eq2.east) {$\lambda_{t_v}^{-1}$};
\node [anchor=west,inner sep=2pt,fill=blue!20] (label3) at ([xshift=2em,yshift=-0.1em]label1.east) {\footnotesize{\textbf{问题：$\lambda_{t_v}=?$}}};
\draw [<-,thick] (label3.south) .. controls +(south:1em) and +(north:1em) .. (eq3.north);
}

\end{tikzpicture}
\end{center}
}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% learning P(s_u |t_v) - a simiplied form
\begin{frame}{对$f(s_u |t_v)$的计算进行化简}

\begin{itemize}
\item 为了计算$f(s_u |t_v)$，重新组织一下上面的公式
\end{itemize}

\vspace{-2.0em}

\begin{center}
\begin{tikzpicture}

\node [anchor=west,inner sep=2pt,minimum height=2em] (eq1) at (0,0) {$f(s_u|t_v)$};
\node [anchor=west,inner sep=2pt] (eq2) at ([xshift=-2pt]eq1.east) {$=$};
\node [anchor=west,inner sep=2pt,minimum height=2em] (eq3) at ([xshift=-2pt]eq2.east) {$\lambda_{t_v}^{-1}$};
\node [anchor=west,inner sep=2pt,minimum height=3.0em] (eq4) at ([xshift=-3pt]eq3.east) {\footnotesize{$\frac{\epsilon}{(l+1)^{m}} \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i)$}};
\node [anchor=west,inner sep=2pt,minimum height=3.0em] (eq5) at ([xshift=1pt]eq4.east) {\footnotesize{$\sum\limits_{j=1}^{m} \delta(s_j,s_u) \sum\limits_{i=0}^{l} \delta(t_i,t_v)$}};
\node [anchor=west,inner sep=2pt,minimum height=3.0em] (eq6) at ([xshift=1pt]eq5.east) {$\frac{f(s_u|t_v)}{\sum_{i=0}^{l}f(s_u|t_i)}$};


\visible<2->{
\node [anchor=west,inner sep=2pt,fill=red!20,minimum height=3.0em] (eq4) at ([xshift=-3pt]eq3.east) {\footnotesize{$\frac{\epsilon}{(l+1)^{m}} \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i)$}};
}
\visible<3->{
\node [anchor=west,inner sep=2pt,fill=blue!20,minimum height=3.0em] (eq5) at ([xshift=1pt]eq4.east) {\footnotesize{$\sum\limits_{j=1}^{m} \delta(s_j,s_u) \sum\limits_{i=0}^{l} \delta(t_i,t_v)$}};
}
\visible<4->{
\node [anchor=west,inner sep=2pt,fill=green!20,minimum height=3.0em] (eq6) at ([xshift=1pt]eq5.east) {$\frac{f(s_u|t_v)}{\sum_{i=0}^{l}f(s_u|t_i)}$};
}

\visible<2->{
\node [anchor=south west,inner sep=2pt] (label1) at (eq4.north west) {\textbf{\scriptsize{翻译概率$\textrm{P}(s|t)$}}};
}
\visible<3->{
\node [anchor=south west,inner sep=2pt] (label2) at (eq5.north west) {\textbf{\scriptsize{配对的总次数}}};
\node [anchor=south west,inner sep=2pt] (label2part2) at ([yshift=-3pt]label2.north west) {\textbf{\scriptsize{$(s_u,t_v)$在句对$(s,t)$中}}};
}
\visible<4->{
\node [anchor=south west,inner sep=2pt] (label3) at (eq6.north west) {\textbf{\scriptsize{有的$t_i$的相对值}}};
\node [anchor=south west,inner sep=2pt] (label4) at ([yshift=-3pt]label3.north west) {\textbf{\scriptsize{$f(s_u|t_v)$对于所}}};
}

\visible<2->{
\node [anchor=east,rotate=90] (neweq1) at ([yshift=-0em]eq4.south) {=};
\node [anchor=north,inner sep=1pt] (neweq1full) at (neweq1.west) {\large{$\textrm{P}(s|t)$}};
}

\visible<5->{
\draw[decorate,thick,decoration={brace,amplitude=5pt,mirror}] ([yshift=-0.2em]eq5.south west) -- ([yshift=-0.2em]eq6.south east) node [pos=0.4,below,xshift=-0.0em,yshift=-0.3em] (expcount1) {\footnotesize{\textbf{'$t_v$翻译为$s_u$'这个事件}}};
\node [anchor=north west] (expcount2) at ([yshift=0.5em]expcount1.south west) {\footnotesize{\textbf{出现次数的期望的估计}}};
\node [anchor=north west] (expcount3) at ([yshift=0.5em]expcount2.south west) {\footnotesize{\textbf{称之为期望频次expected count}}};
}

\end{tikzpicture}
\end{center}

\vspace{-1.2em}

\begin{itemize}
\item<6-> \textbf{啥是事件的期望频次？？？} - 事件在其分布下出现的次数的期望$c_{\mathbb{E}}(X) = \sum_i c(x_i) \cdot \textrm{P}(x_i)$
\end{itemize}

\vspace{-0.8em}

\visible<6->{
\begin{center}
\begin{minipage}[t]{0.30\linewidth}
\begin{tabular}{c | c}
$x_i$ & $c(x_i)$ \\ \hline
$x_1$ & 2 \\
$x_2$ & 1 \\
$x_3$ & 5 \\ \hline
\multicolumn{2}{c}{\visible<7->{$c(X)=8$}}
\end{tabular}
\end{minipage}
\begin{minipage}[t]{0.50\linewidth}
\begin{tabular}{c | c | c | c}
$x_i$ & $c(x_i)$ & $\textrm{P}(x_i)$ & $c(x_i) \cdot \textrm{P}(x_i)$\\ \hline
$x_1$ & 2 & 0.1 & 0.2 \\
$x_2$ & 1 & 0.3 & 0.3 \\
$x_3$ & 5 & 0.2 & 1.0 \\ \hline
\multicolumn{4}{c}{\visible<8->{$c_{\mathbb{E}}(X)=0.2+0.3+1.0=1.5$}}
\end{tabular}
\end{minipage}
\end{center}
}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% introducing the expected counts
\begin{frame}{期望频次}

\begin{center}
\begin{tikzpicture}

\node [anchor=west,inner sep=2pt,minimum height=3.0em] (eq5) at (0,0) {$\sum\limits_{j=1}^{m} \delta(s_j,s_u) \sum\limits_{i=0}^{l} \delta(t_i,t_v)$};
\node [anchor=west,inner sep=2pt,minimum height=3.0em,minimum width=9.0em] (eq6) at ([xshift=1pt]eq5.east) {\Large{$\frac{f(s_u|t_v)}{\sum_{i=0}^{l}f(s_u|t_i)}$}};

\visible<2->{
\node [anchor=west,inner sep=2pt,minimum height=3.0em,fill=blue!20] (eq5) at (0,0) {$\sum\limits_{j=1}^{m} \delta(s_j,s_u) \sum\limits_{i=0}^{l} \delta(t_i,t_v)$};
}
\visible<3->{
\node [anchor=west,inner sep=2pt,minimum height=3.0em,minimum width=9.0em,fill=green!20] (eq6) at ([xshift=1pt]eq5.east) {\Large{$\frac{f(s_u|t_v)}{\sum_{i=0}^{l}f(s_u|t_i)}$}};
}

\visible<2->{
\node [anchor=north] (label1) at (eq5.south) {\footnotesize{'$t_v$翻译为$s_u$'在所有}};
\node [anchor=north west] (label1part2) at ([yshift=6pt]label1.south west) {\footnotesize{对齐中出现的次数}};
}
\visible<3->{
\node [anchor=north] (label2) at ([xshift=-1em]eq6.south) {\footnotesize{'$t_v$翻译为$s_u$'在所有}};
\node [anchor=north west] (label2part2) at ([yshift=6pt]label2.south west) {\footnotesize{对齐中出现的相对概率}};
}

\visible<2->{
\node [anchor=north] (c) at (label1part2.south) {$c$('$t_v$翻译为$s_u$')};
}
\visible<3->{
\node [anchor=north] (p) at (label2part2.south) {$\textrm{P}$('$t_v$翻译为$s_u$')};
}

\visible<4->{
\node [anchor=west] (times) at ([xshift=0.3em]c.east) {$\times$};
\node [anchor=north east] (eqeq) at (c.south west) {=};
\node [anchor=west] (eqfinal) at (eqeq.east) {$c_{\mathbb{E}}$('$t_v$翻译为$s_u$')};
}

\end{tikzpicture}
\end{center}

\begin{itemize}
\item<5-> \textbf{定义}：在$\textrm{P}(s|t)$中，$t_v$翻译(连接)到$s_u$的期望频次为
    \vspace{-0.5em}
    \begin{displaymath}
    c_{\mathbb{E}}(s_u|t_v;s,t) \equiv \sum\limits_{j=1}^{m} \delta(s_j,s_u) \sum\limits_{i=0}^{l} \delta(t_i,t_v) \cdot \frac{f(s_u|t_v)}{\sum_{i=0}^{l}f(s_u|t_i)}
    \end{displaymath}
    \vspace{-0.8em}
\item<6-> \textbf{重写$f(s_u|t_v)$}!!!
    \begin{center}
    \begin{tikzpicture}
    \node [anchor=west,draw,red,thick,inner sep=5pt] (p) at (0,0) {\black{$f(s_u|t_v) = \lambda_{t_v}^{-1} \cdot \textrm{P}(s|t) \cdot c_{\mathbb{E}}(s_u|t_v;s,t)$}};
    \end{tikzpicture}
    \end{center}
\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% calculating f(s_u|t_v) by expected counts
\begin{frame}{通过期望频次计算$f(s_u|t_v)$}

\begin{itemize}
\item \textbf{一个小trick}: 令$\lambda_{t_v}^{'}=\frac{\lambda_{t_v}}{\textrm{P}(s|t)}$

\vspace{-1.0em}

\begin{eqnarray}
f(s_u|t_v) & = & \lambda_{t_v}^{-1} \cdot \textrm{P}(s|t) \cdot c_{\mathbb{E}}(s_u|t_v;s,t) \nonumber \\
                    & = & (\lambda_{t_v}^{'})^{-1} \cdot c_{\mathbb{E}}(s_u|t_v;s,t) \nonumber
\end{eqnarray}

\item<2-> \textbf{$\lambda_{t_v}^{'}$究竟是什么？} - 回忆一下IBM模型对$f(\cdot|\cdot)$的约束
\begin{displaymath}
\forall t_y: \sum_{s_x} f(s_x|t_y) = 1
\end{displaymath}
\vspace{-0.3em}
为了满足$f(\cdot|\cdot)$的概率归一化约束，显然

\vspace{-0.3em}

\begin{displaymath}
\lambda_{t_v}^{'}=\sum_{s_u} c_{\mathbb{E}}(s_u|t_v;s,t)
\end{displaymath}

\vspace{-0.6em}

\item<3-> \textbf{$f(s_u|t_v)$的计算式}
    \begin{center}
    \begin{tikzpicture}
    \node [anchor=west] (eq1) at (0,0) {$f(s_u|t_v) =$};
    \draw [-] (eq1.east) -- ([xshift=8em]eq1.east);
    \node [anchor=south west] (eq2) at ([xshift=1em]eq1.east) {$c_{\mathbb{E}}(s_u|t_v;s,t)$};
    \node [anchor=north west] (eq3) at (eq1.east) {$\sum_{s_u} c_{\mathbb{E}}(s_u|t_v;s,t)$};

    \begin{pgfonlayer}{background}
    \node[rectangle,draw,red,thick,inner sep=0] [fit = (eq1) (eq2) (eq3)] {};
    \end{pgfonlayer}
    \end{tikzpicture}
    \end{center}

\end{itemize}

\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% scale it up to the full corpus
\begin{frame}{在整个数据集上计算}
\begin{itemize}
\item \textbf{更真实的情况}：我们拥有一系列互译的句对（称作\alert{平行语料}），记为$\{(s^{[1]},t^{[1]}),(s^{[2]},t^{[2]}),...,(s^{[N]},t^{[N]})\}$。对于这$N$个训练用句对，定义$f(s_u|t_v)$的期望频次为
    \begin{displaymath}
    c_{\mathbb{E}}(s_u|t_v) = \sum_{i=1}^{N} c_{\mathbb{E}}(s_u|t_v;s^{[i]},t^{[i]})
    \end{displaymath}
\item<2-> \textbf{于是}
    \begin{center}
    \begin{tikzpicture}
    \node [anchor=west,inner sep=2pt] (eq1) at (0,0) {$f(s_u|t_v)$};
    \node [anchor=west] (eq2) at (eq1.east) {$=$\ };
    \draw [-] ([xshift=0.3em]eq2.east) -- ([xshift=11.6em]eq2.east);
    \node [anchor=south west] (eq3) at ([xshift=1em]eq2.east) {$\sum_{i=1}^{N} c_{\mathbb{E}}(s_u|t_v;s^{[i]},t^{[i]})$};
    \node [anchor=north west] (eq4) at (eq2.east) {$\sum_{s_u} \sum_{i=1}^{N} c_{\mathbb{E}}(s_u|t_v;s^{[i]},t^{[i]})$};

    \visible<4->{
    \node [anchor=south] (label1) at ([yshift=-6em,xshift=3em]eq1.north west) {利用这个公式计算};
    \node [anchor=north west] (label1part2) at ([yshift=0.3em]label1.south west) {新的$f(s_u|t_v)$值};
    }
    \visible<3->{
    \node [anchor=west] (label2) at ([xshift=5em]label1.east) {用当前的$f(s_u|t_v)$};
    \node [anchor=north west] (label2part2) at ([yshift=0.3em]label2.south west) {计算期望频次$c_{\mathbb{E}}(\cdot)$};
    }

    \visible<4->{
    \node [anchor=west,fill=red!20,inner sep=2pt] (eq1) at (0,0) {$f(s_u|t_v)$};
    }

    \begin{pgfonlayer}{background}
    \visible<3->{
    \node[rectangle,fill=blue!20,inner sep=0] [fit = (eq3) (eq4)] (c) {};
    }
    \visible<4->{
    \node[rectangle,draw,red,inner sep=0] [fit = (label1) (label1part2)] (flabel) {};
    }
    \visible<3->{
    \node[rectangle,draw,ublue,inner sep=0] [fit = (label2) (label2part2)] (clabel) {};
    }
    \end{pgfonlayer}

    \visible<4->{
    \draw [->,thick] (eq1.south) ..controls +(south:1.5em) and +(north:1.5em).. (flabel.north);
    }
    \visible<3->{
    \draw [->,thick] (c.south) ..controls +(south:1.0em) and +(north:1.0em).. (clabel.north);
    }

    \visible<5->{
    \draw [->,thick] ([yshift=1em]flabel.east) -- ([yshift=1em]clabel.west);
    \draw [<-,thick] ([yshift=-1em]flabel.east) -- ([yshift=-1em]clabel.west) node [pos=0.5,above,yshift=0.3em] {\footnotesize{\textbf{反复执行}}};
    }
    \end{tikzpicture}
    \end{center}
\end{itemize}
\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% the EM algorithm - training IBM model 1
\begin{frame}{完整的模型训练方法 - EM算法}
\label{ibmtraining}

\begin{beamerboxesrounded}[upper=uppercolblue,lower=lowercolblue,shadow=true]{IBM模型1的训练（EM算法）}
输入: 平行语料$\{(s^{[1]},t^{[1]}),...,(s^{[N]},t^{[N]})\}$\\
输出：参数$f(\cdot|\cdot)$的最优值\\
1: \textbf{Function} \textsc{TrainItWithEM}($\{(s^{[1]},t^{[1]}),...,(s^{[N]},t^{[N]})\}$) \\
2: \ \ Initialize $f(\cdot|\cdot)$ \hspace{5em} $\rhd$ 比如给$f(\cdot|\cdot)$一个均匀分布\\
3: \ \ Loop until $f(\cdot|\cdot)$ converges\\
4: \ \ \ \ \textbf{foreach} $k = 1$ to $N$ \textbf{do}\\
5: \ \ \ \ \ \ \ \footnotesize{$c_{\mathbb{E}}(s_u|t_v;s^{[k]},t^{[k]}) = \sum\limits_{j=1}^{|s^{[k]}|} \delta(s_j,s_u) \sum\limits_{i=0}^{|t^{[k]}|} \delta(t_i,t_v) \cdot \frac{f(s_u|t_v)}{\sum_{i=0}^{l}f(s_u|t_i)}$}\normalsize{}\\
6: \ \ \ \ \textbf{foreach} $t_v$ appears at least one of $\{t^{[1]},...,t^{[N]}\}$ \textbf{do}\\
7: \ \ \ \ \ \ \ $\lambda_{t_v}^{'} = \sum_{s_u} \sum_{k=1}^{N} c_{\mathbb{E}}(s_u|t_v;s^{[k]},t^{[k]})$\\
8: \ \ \ \ \ \ \ \textbf{foreach} $s_u$ appears at least one of $\{s^{[1]},...,s^{[N]}\}$ \textbf{do}\\
9: \ \ \ \ \ \ \ \ \ $f(s_u|t_v) = \sum_{k=1}^{N} c_{\mathbb{E}}(s_u|t_v;s^{[k]},t^{[k]}) \cdot (\lambda_{t_v}^{'})^{-1}$\\
10: \ \textbf{return} $f(\cdot|\cdot)$
\end{beamerboxesrounded}
\vspace{-0.3em}
\begin{itemize}
\item<2-> \alert{\textbf{E-Step: 行4-5，计算$c_{\mathbb{E}}(\cdot)$；M-Step：行6-9，计算$f(\cdot)$}}
\end{itemize}
\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% the EM algorithm - training IBM model 2
\begin{frame}{EM算法与IBM模型2}
\begin{itemize}
\item EM算法可以直接用于训练IBM模型2(这里省去推导)
    \begin{itemize}
    \item 参数1：$f(s_j|t_i)$ - 与IBM模型1一样
    \item 参数2：$a(i|j,m,l)$ - 调序概率
    \end{itemize}
\end{itemize}
\begin{enumerate}
\item \textbf{E-Step} (对于句对$(s,t)$，$m=|s|,l=|t|$)
\begin{eqnarray}
c_{\mathbb{E}}(s_u|t_v;s,t) & = & \sum_{j=1}^{m} \sum_{i=0}^{l} \frac{f(s_u|t_v)a(i|j,m,l)\delta(s_j,s_u)\delta(t_i,t_v)}{\sum_{k=0}^{l} f(s_u|t_k)a(k|j,m,l)} \nonumber \\
c_{\mathbb{E}}(i|j,m,l;s,t) & = & \frac{f(s_j|t_i)a(i|j,m,l)}{\sum_{k=0}^{l} f(s_j|t_k)a(k|j,m,l)} \nonumber
\end{eqnarray}
\item \textbf{M-Step}
\begin{eqnarray}
f(s_u|t_v) & = & \frac{\sum_{k=0}^{K} c_{\mathbb{E}}(s_u|t_v;s^{[k]},t^{[k]})}{\sum_{s_u} \sum_{k=0}^{K} c_{\mathbb{E}}(s_u|t_v;s^{[k]},t^{[k]})}  \nonumber \\
a(i|j,m,l) & = & \frac{\sum_{k=0}^{K} c_{\mathbb{E}}(i|j;s^{[k]},t^{[k]})}{\sum_{i} \sum_{k=0}^{K} c_{\mathbb{E}}(i|j;s^{[k]},t^{[k]})} \nonumber
\end{eqnarray}
\end{enumerate}
\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% the remaining problems
\begin{frame}{IBM模型1和2基本介绍完了}
\begin{itemize}
\item 再来回顾一下，IBM模型1和2包括以下三方面内容：
    \begin{enumerate}
    \item \textbf{建模} - {\color{ublue} \hyperref[ibmmodelingstart]{第\hspace{-0.2em}~\ref{ibmmodelingstart}页}}$\sim${\color{ublue} \hyperref[ibmmodelingend]{第\hspace{-0.2em}~\ref{ibmmodelingend}页}}
    \item \textbf{解码} - {\color{ublue} \hyperref[ibmdecoding]{第\hspace{-0.2em}~\ref{ibmdecoding}页}}
    \item \textbf{训练} - {\color{ublue} \hyperref[ibmtraining]{第\hspace{-0.2em}~\ref{ibmtraining}页}}
    \end{enumerate}
\item 还有很多很多问题没有讨论
    \begin{itemize}
    \item 解码：{\color{ublue} \hyperref[simpledecodingalgorithm]{第\hspace{-0.2em}~\ref{simpledecodingalgorithm}页}}所描述的解码算法很粗糙
        \begin{itemize}
        \item 需要考虑更多的翻译假设 - beam search - 随后章节会介绍
        \end{itemize}
    \item<2-> 训练：EM算法的问题是：
        \begin{itemize}
        \item 在目标函数为非突(凹)集函数时，容易陷入局部最优

        \begin{tikzpicture}

        \begin{scope}[scale=0.18]
        \draw[-,thick,ublue,domain=-4.2:3.5,samples=100] plot (\x,{ 1/14 * (\x + 4) * (\x + 1) * (\x - 1) * (\x - 3)});
        \draw[->] (-6,0) -- (5,0);
        \draw[->] (-5,-4) -- (-5,3);
        \node[anchor=west,inner sep=1pt] (label1) at (-3,3) {\tiny{多个极值点}};
        \draw[->] ([xshift=-3em]label1.south) -- (2.3,-0.5);
        \draw[->] ([xshift=-3em]label1.south) -- (-2.5,-1);
        \node [anchor=east] at (-6,0) {\tiny{\alert{非}突(non-convex)函数}};
        \end{scope}

        \begin{scope}[scale=0.18,xshift=10in]
        \draw[-,thick,ublue,domain=-4.2:3.5,samples=100] plot (\x,{ 1/7 * (\x + 1) * (\x + 1) - 2});
        \draw[->] (-6,0) -- (5,0);
        \draw[->] (-5,-4) -- (-5,3);
        \node[anchor=west,inner sep=1pt] (label1) at (-3,3) {\tiny{一个极值点}};
        \draw[->] ([xshift=-3em]label1.south) -- ([xshift=-3em,yshift=-10em]label1.south);
        \node [anchor=east] at (-6,0) {\tiny{突(convex)函数}};
        \end{scope}

        \end{tikzpicture}

        比较幸运的是IBM模型1有单个极值点，EM可以得到全局最优。而且通常会把IBM模型1的参数作为高阶模型(如模型2)的输入，保证后面的训练从较好的初始值开始

        \item 会有degenerate analysis的问题\\
        Google一下variational EM和bayesian inference
        \end{itemize}
    \end{itemize}
\end{itemize}
\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% papers and systems
\begin{frame}{GIZA++}
\begin{itemize}
\item IBM模型3-5不是本教程的重点
    \begin{itemize}
    \item 建模相对复杂一些，当然模型也更强大
    \item 训练和解码不太简单
    \item 推荐一些阅读材料
        {\footnotesize
        \begin{itemize}
        \item \textit{\textbf{A Program for Aligning Sentences in Bilingual Corpora}}.
              William A. Gale and Kenneth W. Church. 1993.
        \item \textit{\textbf{A systematic comparison of various statistical alignment models}}.
              Franz Och and Hermann Ney. 2003.
        \item \textit{\textbf{基于IBM模型的统计机器翻译技术的研究}}.
              肖桐. 2008. (硕士论文)
        \end{itemize}
        }
    \end{itemize}
\item<2-> \textbf{不得不提的GIZA++}：实现了IBM模型+HMM模型，现在广泛用于双语平行语料的自动词对齐
    \begin{itemize}
    \item 完全开源\\
          \url{http://code.google.com/p/giza-pp/}
    \item NiuTrans中也有使用方式的介绍\\
          \url{http://www.nlplab.com/NiuPlan/NiuTrans.YourData.ch.html}
    \end{itemize}
\end{itemize}
\end{frame}

%%%------------------------------------------------------------------------------------------------------------
%%% last slide
\begin{frame}{这章内容先写到这儿~}

\vspace{2em}

\begin{center}
\textbf{这章内容写了很多，但是还没弄完 :(}\\
\textbf{后面(可能过两年)补上单词自动对齐的内容 :)}

\vspace{3em}

\begin{tikzpicture}

{\LARGE
\node [anchor=west,inner sep=2pt,ublue] (s1) at (0,0) {谢谢};
\node [anchor=west,inner sep=2pt,ublue] (s2) at ([xshift=1.0em]s1.east) {大家};
\node [anchor=north,inner sep=2pt,ublue] (t1) at ([yshift=-1.7em]s1.center) {thank};
\node [anchor=north,inner sep=2pt,ublue] (t2) at ([yshift=-1.95em]s2.center) {you};
\node [anchor=west,inner sep=2pt,ublue] (t3) at ([xshift=1.5em,yshift=0.2em]t2.east) {all};

\draw [-,thick,ublue] ([yshift=-0.1em]s1.south) -- (t1.north);
\draw [-,thick,ublue] ([yshift=-0.1em]s2.south) -- ([yshift=0.2em]t2.north);
\draw [-,thick,ublue] ([yshift=-0.1em]s2.south) -- (t3.north);

}

\end{tikzpicture}

\end{center}

\end{frame}

\end{CJK}
\end{document}
