% !Mode:: "TeX:UTF-8"
% !TEX encoding = UTF-8 Unicode
%----------------------------------------------------------------------------------------
% 机器翻译：统计建模与深度学习方法
% Machine Translation: Statistical Modeling and Deep Learning Methods
%
% Copyright 2020
% 肖桐(xiaotong@mail.neu.edu.cn) 朱靖波 (zhujingbo@mail.neu.edu.cn)
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
% CONFIGURATIONS
%----------------------------------------------------------------------------------------
\part{统计机器翻译}
\renewcommand\figurename{图}%将figure改为图
\renewcommand\tablename{表}%将figure改为图
\chapterimage{fig-NEU-5.jpg} % Chapter heading image
%----------------------------------------------------------------------------------------
% CHAPTER 5
%----------------------------------------------------------------------------------------
\chapter{基于词的机器翻译建模}
\parinterval 使用统计方法对翻译问题进行建模是机器翻译发展中的重要里程碑。这种思想也影响了当今的统计机器翻译和神经机器翻译范式。虽然技术不断发展，传统的统计模型已经不再“新鲜”，但它对于今天机器翻译的研究仍然有着重要的启示作用。在了解前沿、展望未来的同时，更要冷静地思考前人给我们带来了什么。基于此，这里将介绍统计机器翻译的开山之作\ \dash \ IBM 模型，它提出了使用统计模型进行翻译的思想，并在建模中引入了单词对齐这一重要概念。
IBM模型由Peter F. Brown等人于上世纪九十年代初提出\upcite{DBLP:journals/coling/BrownPPM94}。客观地说，这项工作的视野和对问题的理解，已经超过当时很多人所能看到的东西，其衍生出来的一系列方法和新的问题还被后人花费将近10年的时间来进行研究与讨论。时至今日，IBM模型中的一些思想仍然影响着很多研究工作。本章将重点介绍一种简单的基于单词的统计翻译模型（IBM模型1），以及在这种建模方式下的模型训练方法。这些内容可以作为后续章节中统计机器翻译和神经机器翻译建模方法的基础。
%----------------------------------------------------------------------------------------
% NEW SECTION
%----------------------------------------------------------------------------------------
\section{词在翻译中的作用}
\parinterval 在翻译任务中，我们希望得到一个源语言到目标语言的翻译。对于人类来说这个问题很简单，但是让计算机做这样的工作却很困难。这里面临的第一个问题是：如何对翻译进行建模？从计算机的角度来看，这就需要把自然语言的翻译问题转换为计算机可计算的问题。
\parinterval 那么，基于单词的统计机器翻译模型又是如何描述翻译问题的呢？Peter F. Brown等人提出了一个观点\upcite{DBLP:journals/coling/BrownPPM94}：在翻译一个句子时，可以把其中的每个单词翻译成对应的目标语言单词，然后调整这些目标语言单词的顺序，最后得到整个句子的翻译结果，而这个过程可以用统计模型来描述。尽管在人看来使用两个语言单词之间的对应进行翻译是很自然的事，但是对于计算机来说可是向前迈出了一大步。
\parinterval 先来看一个例子。图 \ref{fig:5-1}展示了一个汉语翻译到英语的例子。首先，可以把源语言句子中的单词“我”、“对”、“你”、“感到”和“满意”分别翻译为“I”、“with”、“you”、“am”\ 和“satisfied”，然后调整单词的顺序，比如，“am”放在译文的第2个位置，“you”应该放在最后的位置等等，最后得到译文“I am satisfied with you”。
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-zh-en-translation-example}
\caption{汉语到英语的翻译实例及两种语言单词之间的对应关系}
\label{fig:5-1}
\end{figure}
%----------------------------------------------
\parinterval 上面的例子反映了人在做翻译时所使用的一些知识：首先，两种语言单词的顺序可能不一致，而且译文需要符合目标语的习惯，这也就是常说的翻译的流畅度；其次，源语言单词需要准确地被翻译出来，也就是常说的翻译的准确性问题和充分性问题。为了达到以上目的，传统观点认为翻译过程需要包含三个步骤\upcite{parsing2009speech}：
\begin{itemize}
\vspace{0.5em}
\item {\small\sffamily\bfseries{分析：}}将源语言句子表示为适合机器翻译的结构。在基于词的翻译模型中，处理单元是单词，因此在这里也可以简单地将分析理解为分词\footnote{在后续章节中会看到，分析也包括对句子深层次结构的生成，但是这里为了突出基于单词的概念，因此把问题简化为最简单的情况。}。
\vspace{0.5em}
\item {\small\sffamily\bfseries{转换：}}把源语言句子中的每个单词翻译成目标语言单词。
\vspace{0.5em}
\item {\small\sffamily\bfseries{生成：}}基于转换的结果，将目标语译文变成通顺且合乎语法的句子。
\vspace{0.5em}
\end{itemize}
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-translation-pipeline}
\caption{翻译过程中的分析、转换和生成}
\label{fig:5-2}
\end{figure}
%----------------------------------------------
\parinterval 图\ref{fig:5-2}给出了上述过程的一个示例。对于今天的自然语言处理研究，“分析、转换和生成”依然是一个非常深刻的观点。包括机器翻译在内的很多自然语言处理问题都可以用这个过程来解释。比如，对于现在比较前沿的神经机器翻译方法，从大的框架来说，依然在做分析（编码器）、转换（编码-解码注意力）和生成（解码器），只不过这些过程隐含在神经网络的设计中。当然，这里并不会对“分析、转换和生成”的架构展开过多的讨论，随着后面技术内容讨论的深入，这个观念会进一步体现。
%----------------------------------------------------------------------------------------
% NEW SECTION
%----------------------------------------------------------------------------------------
\sectionnewpage
\section{一个简单实例}
\label{sec:simple-mt-example}
\parinterval 本节首先对比人工翻译和机器翻译过程的异同点，从中归纳出实现机器翻译过程的两个主要步骤：训练和解码。之后，会从学习翻译知识和运用翻译知识两个方面描述如何构建一个简单的机器翻译系统。
%----------------------------------------------------------------------------------------
% NEW SUB-SECTION
%----------------------------------------------------------------------------------------
\subsection{翻译的流程}
%----------------------------------------------------------------------------------------
% NEW SUBSUB-SECTION
%----------------------------------------------------------------------------------------
\subsubsection*{1. 人工翻译流程}
\parinterval 当人翻译一个句子时，首先会快速地分析出句子的（单词）构成，然后根据以往的知识，得到每个词可能的翻译，最后利用对目标语的理解拼出来一个译文。尽管这个过程并不是严格来自心理学或者脑科学的相关结论，但至少可以帮助我们理解人在翻译时的思考方式。
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-human-translation}
\caption{人工翻译的过程}
\label{fig:5-3}
\end{figure}
%----------------------------------------------
\vspace{-0.2em}
\parinterval 图\ref{fig:5-3}展示了人在翻译“我/对/你/感到/满意”时可能会思考的内容\footnote{这里用斜杠表示单词之间的分隔。}。具体来说，有如下两方面内容：
\begin{itemize}
\vspace{0.5em}
\item {\small\bfnew{翻译知识的学习}}：对于输入的源语言句子，首先需要知道每个单词可能的翻译有什么，这些翻译被称为{\small\sffamily\bfseries{翻译候选}}\index{翻译候选}（Translation Candidate）\index{Translation Candidate}。比如，汉语单词“对”可能的译文有“to”、“with”和“for”等。对于人来说，可以通过阅读、背诵、做题或者老师教等途径获得翻译知识，这些知识就包含了源语言与目标语言单词之间的对应关系。通常，也把这个过程称之为学习过程。
\vspace{0.5em}
\item {\small\bfnew{运用知识生成译文}}：当翻译一个从未见过的句子时，可以运用学习到的翻译知识，得到新的句子中每个单词的译文，并处理常见的单词搭配、主谓一致等问题，比如，英语中“satisfied” 后面常常使用介词“with”构成搭配。基于这些知识可以快速生成译文。
\vspace{0.5em}
\end{itemize}
当然，每个人进行翻译时所使用的方法和技巧都不相同，所谓人工翻译也没有固定的流程。但是，可以确定的是，人在进行翻译时也需要“学习”和“运用”翻译知识。对翻译知识“学习”和“运用”的好与坏，直接决定了人工翻译结果的质量。
%----------------------------------------------------------------------------------------
% NEW SUBSUB-SECTION
%----------------------------------------------------------------------------------------
\subsubsection{2. 机器翻译流程}
\parinterval 人进行翻译的过程比较容易理解，那计算机是如何完成翻译的呢？虽然人工智能这个概念显得很神奇，但是计算机远没有人那么智能，有时甚至还很“笨”。一方面，它没有能力像人一样，在教室里和老师一起学习语言知识；另一方面，即使能列举出每个单词的候选译文，但是还是不知道这些译文是怎么拼装成句的，甚至不知道哪些译文是对的。为了更加直观地理解机器在翻译时要解决的挑战，可以将问题归纳如下：
\begin{itemize}
\vspace{0.5em}
\item 如何让计算机获得每个单词的译文，然后将这些单词的译文拼装成句？
\vspace{0.5em}
\item 如果可以形成整句的译文，如何让计算机知道不同译文的好坏？
\vspace{0.5em}
\end{itemize}
\parinterval 对于第一个问题，可以给计算机一个翻译词典，这样计算机可以发挥计算方面的优势，尽可能多地把翻译结果拼装出来。比如，可以把每个翻译结果看作是对单词翻译的拼装，这可以被形象地比作贯穿多个单词的一条路径，计算机所做的就是尽可能多地生成这样的路径。图\ref{fig:5-4}中蓝色和红色的折线就分别表示了两条不同的译文选择路径，区别在于“满意”和“对”的翻译候选是不一样的，蓝色折线选择的是“satisfy”和“to”，而红色折线是“satisfied”和“with”。换句话说，不同的译文对应不同的路径（即使词序不同也会对应不同的路径）。
\parinterval 对于第二个问题，尽管机器能够找到很多译文选择路径，但它并不知道哪些路径是好的。说地再直白一些，简单地枚举路径实际上就是一个体力活，没有太多的智能。因此计算机还需要再聪明一些，运用它的能够“掌握”的知识判断翻译结果的好与坏。这一步是最具挑战的，当然也有很多思路。在统计机器翻译中，这个问题被定义为：设计一种统计模型，它可以给每个译文一个可能性，而这个可能性越高表明译文越接近人工翻译。
\parinterval 如图\ref{fig:5-4}所示，每个单词翻译候选的右侧黑色框里的数字就是单词的翻译概率，使用这些单词的翻译概率，可以得到整句译文的概率（用符号$\funp{P}$表示）。这样，就用概率化的模型描述了每个翻译候选的可能性。基于这些翻译候选的可能性，机器翻译系统可以对所有的翻译路径进行打分，比如，图\ref{fig:5-4}中第一条路径的分数为0.042，第二条是0.006，以此类推。最后，系统可以选择分数最高的路径作为源语言句子的最终译文。
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-process-of-machine-translation}
\caption{机器翻译的过程\ \dash \ 把单词的译文进行拼装，并找到最优的拼装路径}
\label{fig:5-4}
\end{figure}
%----------------------------------------------
%----------------------------------------------------------------------------------------
% NEW SUBSUB-SECTION
%----------------------------------------------------------------------------------------
\subsubsection{3. 人工翻译 vs. 机器翻译}
\parinterval 人在翻译时的决策是非常确定并且快速的，但计算机处理这个问题时却充满了概率化的思想。当然它们也有类似的地方。首先，计算机使用统计模型的目的是把翻译知识变得可计算，并把这些“知识”储存在模型参数中，这个模型和人类大脑的作用是类似的\footnote{这里并不是要把统计模型等同于生物学或者认知科学上的人脑，这里是指它们处理翻译问题时发挥的作用类似。}；其次，计算机对统计模型进行训练相当于人类对知识的学习，二者都可以被看作是理解、加工知识的过程；再有，计算机使用学习到的模型对新句子进行翻译的过程相当于人运用知识的过程。在统计机器翻译中，模型学习的过程被称为训练，目的是从双语平行数据中自动学习翻译“知识”；而使用模型处理新句子的过程是一个典型的预测过程，也被称为解码或推断。图\ref{fig:5-4}的右侧标注在翻译过程中训练和解码的作用。最终，统计机器翻译的核心由三部分构成\ \dash \ 建模、训练和解码。本章后续内容会围绕这三个问题展开讨论。
%----------------------------------------------------------------------------------------
% NEW SUB-SECTION
%----------------------------------------------------------------------------------------
\subsection{统计机器翻译的基本框架}
\parinterval 为了对统计机器翻译有一个直观的认识，下面将介绍如何构建一个非常简单的统计机器翻译系统，其中涉及到的很多思想来自IBM模型。这里，仍然使用数据驱动的统计建模方法。图\ref{fig:5-5}展示了系统的主要流程，包括两个步骤：
\begin{itemize}
\vspace{0.5em}
\item {\small\sffamily\bfseries{训练}}：从双语平行数据中学习翻译模型，记为$\funp{P}(\seq{t}|\seq{s})$，其中$\seq{s}$表示源语言句子，$\seq{t}$表示目标语句子。$\funp{P}(\seq{t}|\seq{s})$表示把$\seq{s}$翻译为$\seq{t}$的概率。简言之，这一步需要从大量的双语平行数据中学习到$\funp{P}(\seq{t}|\seq{s})$的准确表达。
\vspace{0.5em}
\item {\small\sffamily\bfseries{解码}}：当面对一个新的句子时，需要使用学习到的模型进行预测。预测可以被视为一个搜索和计算的过程，也就是，尽可能搜索更多的翻译结果，然后用训练好的模型对每个翻译结果进行打分，最后选择得分最高的翻译结果作为输出。
\vspace{0.5em}
\end{itemize}
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-processes-smt}
\caption{简单的统计机器翻译流程}
\label{fig:5-5}
\end{figure}
%----------------------------------------------
\vspace{-0.5em}
\parinterval 接下来，本节将介绍统计机器翻译模型训练和解码的方法。在模型学习中，会分两小节进行描述\ \dash \ 单词级翻译和句子级翻译。实现单词级翻译是实现句子级翻译的基础。换言之，句子级翻译的统计模型是建立在单词翻译之上的。在解码中，本节将介绍一个高效的搜索算法，其中也使用到了剪枝和启发式搜索的思想。
%----------------------------------------------------------------------------------------
% NEW SUB-SECTION
%----------------------------------------------------------------------------------------
\subsection{单词翻译概率}\label{chapter5.2.3}
%----------------------------------------------------------------------------------------
% NEW SUBSUB-SECTION
%----------------------------------------------------------------------------------------
\subsubsection{1. 什么是单词翻译概率？}
\parinterval 单词翻译概率描述的是一个源语言单词与目标语言译文构成正确翻译的可能性，这个概率越高表明单词翻译越可靠。使用单词翻译概率，可以帮助机器翻译系统解决翻译时的“择词”问题，即选择什么样的目标语译文是合适的。当人在翻译某个单词时，可以利用积累的知识，快速得到它的高质量候选译文。
\parinterval 以汉译英为例，当翻译“我”这个单词时，可能直接会想到用“I”、“me”或“I'm”作为它的译文，而几乎不会选择“you”、“satisfied”等含义相差太远的译文。这是为什么呢？如果从统计学的角度来看，无论是何种语料，包括教材、新闻、小说等，绝大部分情况下“我”都翻译成了“I”、“me”等，几乎不会看到我被翻译成“you”或“satisfied”的情况。可以说“我”翻译成“I”、“me”等属于高频事件，而翻译成“you”、“satisfied”等属于低频或小概率事件。因此人在翻译时也是选择在统计意义上概率更大的译文，这也间接反映出统计模型可以在一定程度上描述人的翻译习惯和模式。
\parinterval 表\ref{tab:5-1}展示了汉语到英语的单词翻译实例及相应的翻译概率。可以看到，“我”翻译成“I”的概率最高，为0.5。这是符合人类对翻译的认知的。此外，这种概率化的模型避免了非0即1的判断，所有的译文都是可能的，只是概率不同。这也使得统计模型可以覆盖更多的翻译现象，甚至捕捉到一些人所忽略的情况。\\ \\ \\
%----------------------------------------------
\begin{table}[htp]
\centering
\begin{tabular}{c | c c}
源语言 & 目标语言 & 翻译概率 \\ \hline
& I & 0.50 \\
& me & 0.20 \\
我 & I'm & 0.10 \\
& we & 0.05 \\
& am & 0.10 \\
... & ... & ... \\
\end{tabular}
\caption{汉译英单词翻译概率}
\label{tab:5-1}
\end{table}
%----------------------------------------------
%\vspace{-0.5em}
%----------------------------------------------------------------------------------------
% NEW SUBSUB-SECTION
%----------------------------------------------------------------------------------------
\subsubsection{2. 如何从双语平行数据中进行学习？}
\parinterval 假设有一定数量的双语对照的平行数据，是否可以从中自动获得两种语言单词之间的翻译概率呢？回忆一下{\chaptertwo}中的掷骰子游戏，其中使用了相对频次估计方法来自动获得骰子不同面出现概率的估计值。其中，重复投掷骰子很多次，然后统计“1”到“6”各面出现的次数，再除以投掷的总次数，最后得到它们出现的概率的极大似然估计。这里，可以使用类似的方式计算单词翻译概率。但是，现在有的是句子一级对齐的数据，并不知道两种语言之间单词的对应关系。也就是，要从句子级对齐的平行数据中学习单词之间对齐的概率。这里，需要使用稍微“复杂”一些的模型来描述这个问题。
令$X$和$Y$分别表示源语言和目标语言的词汇表。对于任意源语言单词$x \in X$，所有的目标语单词$y \in Y$都可能是它的译文。给定一个互译的句对$(\seq{s},\seq{t})$，可以把$\funp{P}(x \leftrightarrow y; \seq{s}, \seq{t})$定义为：在观测到$(\seq{s},\seq{t})$的前提下$x$和$y$互译的概率。其中$x$是属于句子$\seq{s}$中的词，而$y$是属于句子$\seq{t}$ 中的词。$\funp{P}(x \leftrightarrow y; \seq{s},\seq{t})$的计算公式描述如下：
\vspace{-0.5em}
\begin{eqnarray}
\funp{P}(x \leftrightarrow y; \seq{s},\seq{t}) & \equiv & \funp{P}(x,y;\seq{s},\seq{t}) \nonumber \\
& = & \frac{c(x,y;\seq{s},\seq{t})}{\sum_{x',y'} c(x',y';\seq{s},\seq{t})}
\label{eq:5-1}
\end{eqnarray}
\noindent 其中，$\equiv$表示定义式。分子$c(x,y;\seq{s},\seq{t})$表示$x$和$y$在句对$(\seq{s},\seq{t})$中共现的总次数,分母 $\sum_{x',y'} c(x',y';$ $\seq{s},\seq{t})$表示任意的源语言单词$x'$和任意的目标语言单词$y'$在$(\seq{s},\seq{t})$共同出现的总次数。
\parinterval 看一个具体的例子，如例\ref{eg:5-1}所示，有一个汉英互译的句对$(\seq{s},\seq{t})$。
\begin{example}
一个汉英互译的句对
$\seq{s}$ = 机器\quad \underline{翻译}\; 就\; 是\; 用\; 计算机\; 来\; 生成\; \underline{翻译}\; 的\; 过程
$\seq{t}$ = machine\; \underline{translation}\; is\; a\; process\; of\; generating\; a\; \underline{translation}\; by\; computer
\label{eg:5-1}
\end{example}
\parinterval 假设，$x=\textrm{“翻译”}$，$y=\textrm{“translation”}$，现在要计算$x$和$y$共现的总次数。“翻译”和“translation”分别在$\seq{s}$和$\seq{t}$中出现了2次，因此$c(\textrm{“翻译”},\textrm{“translation”};\seq{s},\seq{t})$ 等于4。而对于$\sum_{x',y'} c(x',y';\seq{s},$ $\seq{t})$，因为$x'$和$y'$分别表示的是$\seq{s}$和$\seq{t}$中的任意词，所以$\sum_{x',y'} c(x',y';\seq{s},\seq{t})$表示所有单词对的数量\ \dash \ 即$\seq{s}$的词数乘以$\seq{t}$的词数。最后，“翻译”和“translation”的单词翻译概率为：
\begin{eqnarray}
\funp{P}(\text{翻译},\text{translation}; \seq{s},\seq{t}) & = & \frac{c(\textrm{翻译},\textrm{translation};\seq{s},\seq{t})}{\sum_{x',y'} c(x',y';\seq{s},\seq{t})} \nonumber \\
& = & \frac{4}{|\seq{s}|\times |\seq{t}|} \nonumber \\
& = & \frac{4}{121}
\label{eq:5-2}
\end{eqnarray}
\noindent 这里运算$|\cdot|$表示句子长度。类似的，可以得到“机器”和“translation”、“机器”和“look”的单词翻译概率：
\begin{eqnarray}
\funp{P}(\text{机器},\text{translation}; \seq{s},\seq{t}) & = & \frac{2}{121} \\
\funp{P}(\text{机器},\text{look}; \seq{s},\seq{t}) & = & \frac{0}{121}
\label{eq:5-3}
\end{eqnarray}
\noindent 注意，由于“look”没有出现在数据中，因此$\funp{P}(\text{机器},\text{look}; \seq{s},\seq{t})=0$。这时，可以使用{\chaptertwo}介绍的平滑算法赋予它一个非零的值，以保证在后续的步骤中整个翻译模型不会出现零概率的情况。
%----------------------------------------------------------------------------------------
% NEW SUBSUB-SECTION
%----------------------------------------------------------------------------------------
\subsubsection{3. 如何从大量的双语平行数据中进行学习？}
\parinterval 如果有更多的句子，上面的方法同样适用。假设，有$K$个互译句对$\{(\seq{s}^{[1]},\seq{t}^{[1]})$,...,\\$(\seq{s}^{[K]},\seq{t}^{[K]})\}$。仍然可以使用基于相对频次的方法估计翻译概率$\funp{P}(x,y)$，具体方法如下:
\begin{eqnarray}
\funp{P}(x,y) = \frac{{\sum_{k=1}^{K} c(x,y;\seq{s}^{[k]},\seq{t}^{[k]})}}{\sum_{k=1}^{K}{{\sum_{x',y'} c(x',y';\seq{s}^{[k]},\seq{t}^{[k]})}}}
\label{eq:5-4}
\end{eqnarray}
\parinterval 与公式\eqref{eq:5-1}相比，公式\eqref{eq:5-4}的分子、分母都多了一项累加符号$\sum_{k=1}^{K} \cdot$，它表示遍历语料库中所有的句对。换句话说，当计算词的共现次数时，需要对每个句对上的计数结果进行累加。从统计学习的角度，使用更大规模的数据进行参数估计可以提高结果的可靠性。计算单词的翻译概率也是一样，在小规模的数据上看，很多翻译现象的特征并不突出，但是当使用的数据量增加到一定程度，翻译的规律会很明显的体现出来。
\parinterval 举个例子，实例\ref{eg:5-2}展示了一个由两个句对构成的平行语料库。
\begin{example}
两个汉英互译的句对
$\seq{s}^{[1]}$ = 机器\quad \underline{翻译}\; 就\; 是\; 用\; 计算机\; 来\; 生成\; \underline{翻译}\; 的\; 过程
$\seq{t}^{[1]}$ = machine\; \underline{translation}\; is\; a\; process\; of\; generating\; a\; \underline{translation}\; by\; computer
$\seq{s}^{[2]}$ = 那\quad 人工\quad \underline{翻译}\quad 呢\quad ?
$\seq{t}^{[2]}$ = So\; ,\; what\; is\; human\; \underline{translation}\; ?
\label{eg:5-2}
\end{example}
\noindent 其中，$\seq{s}^{[1]}$和$\seq{s}^{[2]}$分别表示第一个句对和第二个句对的源语言句子，$\seq{t}^{[1]}$和$\seq{t}^{[2]}$表示对应的目标语言句子。于是，“翻译”和“translation” 的翻译概率为
{\small
\begin{eqnarray}
{\funp{P}(\textrm{翻译},\textrm{translation})} & = & {\frac{c(\textrm{翻译},\textrm{translation};\seq{s}^{[1]},\seq{t}^{[1]})+c(\textrm{翻译},\textrm{translation};\seq{s}^{[2]},\seq{t}^{[2]})}{\sum_{x',y'} c(x',y';\seq{s}^{[1]},\seq{t}^{[1]}) + \sum_{x',y'} c(x',y';\seq{s}^{[2]},\seq{t}^{[2]})}} \nonumber \\
& = & \frac{4 + 1}{|\seq{s}^{[1]}| \times |\seq{t}^{[1]}| + |\seq{s}^{[2]}| \times |\seq{t}^{[2]}|} \nonumber \\
& = & \frac{4 + 1}{11 \times 11 + 5 \times 7} \nonumber \\
& = & \frac{5}{156}
\label{eq:5-5}
\end{eqnarray}
}
\parinterval 公式\eqref{eq:5-5}所展示的计算过程很简单，分子是两个句对中“翻译”和“translation”共现次数的累计，分母是两个句对的源语言单词和目标语言单词的组合数的累加。显然，这个方法也很容易推广到处理更多句子的情况。
%----------------------------------------------------------------------------------------
% NEW SUB-SECTION
%----------------------------------------------------------------------------------------
\subsection{句子级翻译模型}
\label{sec:sentence-level-translation}
\parinterval 下面继续回答如何获取句子级翻译概率的问题，即：对于源语言句子$\seq{s}$和目标语言句子$\seq{t}$，计算$\funp{P}(\seq{t}|\seq{s})$。这也是整个句子级翻译模型的核心，一方面需要从数据中学习这个模型的参数，另一方面，对于新输入的句子，需要使用这个模型得到最佳的译文。下面介绍句子级翻译的建模方法。
%----------------------------------------------------------------------------------------
% NEW SUBSUB-SECTION
%----------------------------------------------------------------------------------------
\subsubsection{1. 基础模型}
\parinterval 计算句子级翻译概率并不简单。因为自然语言非常灵活，任何数据无法覆盖足够多的句子，因此，无法像公式\eqref{eq:5-4}一样直接用简单计数的方式对句子的翻译概率进行估计。这里，采用一个退而求其次的方法：找到一个函数$g(\seq{s},\seq{t})\ge 0$来模拟翻译概率对译文可能性进行估计。可以定义一个新的函数$g(\seq{s},\seq{t})$，令其满足：给定$\seq{s}$，翻译结果$\seq{t}$出现的可能性越大，$g(\seq{s},\seq{t})$的值越大；$\seq{t}$出现的可能性越小，$g(\seq{s},\seq{t})$的值越小。换句话说，$g(\seq{s},\seq{t})$和翻译概率$\funp{P}(\seq{t}|\seq{s})$呈正相关。如果存在这样的函数$g(\seq{s},\seq{t}
)$，可以利用$g(\seq{s},\seq{t})$近似表示$\funp{P}(\seq{t}|\seq{s})$，如下：
\begin{eqnarray}
\funp{P}(\seq{t}|\seq{s}) \equiv \frac{g(\seq{s},\seq{t})}{\sum_{\seq{t}'}g(\seq{s},\seq{t}')}
\label{eq:5-6}
\end{eqnarray}
\parinterval 公式\eqref{eq:5-6}相当于在函数$g(\cdot)$上做了归一化，这样等式右端的结果具有一些概率的属性，比如，$0 \le \frac{g(\seq{s},\seq{t})}{\sum_{\seq{t'}}g(\seq{s},\seq{t'})} \le 1$。具体来说，对于源语言句子$\seq{s}$，枚举其所有的翻译结果，并把所对应的函数$g(\cdot)$相加作为分母，而分子是某个翻译结果$\seq{t}$所对应的$g(\cdot)$的值。
\parinterval 上述过程初步建立了句子级翻译模型，并没有直接求$\funp{P}(\seq{t}|\seq{s})$，而是把问题转化为对$g(\cdot)$的设计和计算上。但是，面临着两个新的问题：
\begin{itemize}
\vspace{0.5em}
\item 如何定义函数$g(\seq{s},\seq{t})$？即，在知道单词翻译概率的前提下，如何计算$g(\seq{s},\seq{t})$；
\vspace{0.5em}
\item 公式\eqref{eq:5-6}中分母$\sum_{seq{t'}}g(\seq{s},{\seq{t}'})$需要累加所有翻译结果的$g(\seq{s},{\seq{t}'})$，但枚举所有${\seq{t}'}$是不现实的。
\vspace{0.5em}
\end{itemize}
\parinterval 当然，这里最核心的问题还是函数$g(\seq{s},\seq{t})$的定义。而第二个问题其实不需要解决，因为机器翻译只关注于可能性最大的翻译结果，即$g(\seq{s},\seq{t})$的计算结果最大时对应的译文。这个问题会在后面进行讨论。
\parinterval 回到设计$g(\seq{s},\seq{t})$的问题上。这里，采用“大题小作”的方法，这个技巧在{\chaptertwo}已经进行了充分的介绍。具体来说，直接建模句子之间的对应比较困难，但可以利用单词之间的对应来描述句子之间的对应关系。这就用到了上一小节所介绍的单词翻译概率。
\parinterval 首先引入一个非常重要的概念\ \dash \ {\small\sffamily\bfseries{词对齐}}\index{词对齐}（Word Alignment）\index{Word Alignment}，它是统计机器翻译中最核心的概念之一。词对齐描述了平行句对中单词之间的对应关系，它体现了一种观点：本质上句子之间的对应是由单词之间的对应表示的。当然，这个观点在神经机器翻译或者其他模型中可能会有不同的理解，但是翻译句子的过程中考虑词级的对应关系是符合人类对语言的认知的。
\parinterval 图\ref{fig:5-7} 展示了一个句对$\seq{s}$和$\seq{t}$，单词的右下标数字表示了该词在句中的位置，而虚线表示的是句子$\seq{s}$和$\seq{t}$中的词对齐关系。比如，“满意”的右下标数字5表示在句子$\seq{s}$中处于第5个位置，“satisfied”的右下标数字3表示在句子$\seq{t}$中处于第3个位置，“满意”和“satisfied”之间的虚线表示两个单词之间是对齐的。为方便描述，用二元组$(j,i)$ 来描述词对齐，它表示源语言句子的第$j$个单词对应目标语言句子的第$i$个单词，即单词$s_j$和$t_i$对应。通常，也会把$(j,i)$称作一条{\small\sffamily\bfseries{词对齐连接}}\index{词对齐连接}（Word Alignment Link\index{Word Alignment Link}）。图\ref{fig:5-7} 中共有5 条虚线，表示有5组单词之间的词对齐连接。可以把这些词对齐连接构成的集合作为词对齐的一种表示，记为$A$，即$A={\{(1,1),(2,4),(3,5),(4,2)(5,3)}\}$。
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-zh-en-translation-sentence-pairs&word-alignment-connection}
\caption{汉英互译句对及词对齐连接（蓝色虚线）}
\label{fig:5-7}
\end{figure}
%----------------------------------------------
\vspace{-0.5em}
\parinterval 对于句对$(\seq{s},\seq{t})$，假设可以得到最优词对齐$\widehat{A}$，于是可以使用单词翻译概率计算$g(\seq{s},\seq{t})$，如下
\begin{eqnarray}
g(\seq{s},\seq{t}) = \prod_{(j,i)\in \widehat{A}}\funp{P}(s_j,t_i)
\label{eq:5-7}
\end{eqnarray}
\noindent 其中$g(\seq{s},\seq{t})$被定义为句子$\seq{s}$中的单词和句子$\seq{t}$中的单词的翻译概率的乘积，并且这两个单词之间必须有词对齐连接。$\funp{P}(s_j,t_i)$表示具有词对齐连接的源语言单词$s_j$和目标语言单词$t_i$的单词翻译概率。以图\ref{fig:5-7}中的句对为例，其中“我”与“I”、“对”与“with”、“你” 与“you”等相互对应，可以把它们的翻译概率相乘得到$g(\seq{s},\seq{t})$的计算结果，如下：
\begin{eqnarray}
{g(\seq{s},\seq{t})}&= & \funp{P}(\textrm{我,I}) \times \funp{P}(\textrm{对,with}) \times \funp{P}(\textrm{你,you}) \times \nonumber \\
& & \funp{P}(\textrm{感到, am}) \times \funp{P}(\textrm{满意,satisfied})
\label{eq:5-8}
\end{eqnarray}
\parinterval 显然，如果每个词对齐连接所对应的翻译概率变大，那么整个句子翻译的得分也会提高。也就是说，词对齐越准确，翻译模型的打分越高，$\seq{s}$和$\seq{t}$之间存在翻译关系的可能性越大。
%----------------------------------------------------------------------------------------
% NEW SUBSUB-SECTION
%----------------------------------------------------------------------------------------
\subsubsection{2. 生成流畅的译文}
\parinterval 公式\eqref{eq:5-7}定义的$g(\seq{s},\seq{t})$存在的问题是没有考虑词序信息。这里用一个简单的例子说明这个问题。如图\ref{fig:5-8}所示，源语言句子“我 对 你 感到 满意”有两个翻译结果，第一个翻译结果是“I am satisfied with you”，第二个是“I with you am satisfied”。虽然这两个译文包含的目标语单词是一样的，但词序存在很大差异。比如，它们都选择了“satisfied”作为源语单词“满意”的译文，但是在第一个翻译结果中“satisfied”处于第3个位置，而第二个结果中处于最后的位置。显然第一个翻译结果更符合英语的表达习惯，翻译的质量更高。遗憾的是，对于有明显差异的两个译文，公式\eqref{eq:5-7}计算得到的函数$g(\cdot)$的值却是一样的。
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-example-translation-alignment}
\caption{同一个源语言句子的不同译文所对应的$g(\cdot)$得分}
\label{fig:5-8}
\end{figure}
%----------------------------------------------
\parinterval 如何在$g(\seq{s},\seq{t})$引入词序信息呢？理想情况下，函数$g(\seq{s},\seq{t})$对符合自然语言表达习惯的翻译结果给出更高的分数，对于不符合的或不通顺的句子给出更低的分数。这里很自然想到使用语言模型，因为语言模型可以度量一个句子出现的可能性。流畅的句子语言模型得分越高，反之越低。
\parinterval 这里可以使用{\chaptertwo}介绍的$n$-gram语言模型，它也是统计机器翻译中确保流畅翻译结果的重要手段之一。$n$-gram语言模型用概率化方法描述了句子的生成过程。以2-gram语言模型为例，可以使用如下公式计算一个词串的概率：
\begin{eqnarray}
\funp{P}_{\textrm{lm}}(\seq{t}) & = & \funp{P}_{\textrm{lm}}(t_1...t_l) \nonumber \\
& = & \funp{P}(t_1)\times \funp{P}(t_2|t_1)\times \funp{P}(t_3|t_2)\times ... \times \funp{P}(t_l|t_{l-1})
\label{eq:5-9}
\end{eqnarray}
\noindent 其中，$\seq{t}=t_1...t_l$表示由$l$个单词组成的句子，$\funp{P}_{\textrm{lm}}(\seq{t})$表示语言模型给句子$\seq{t}$的打分。具体而言，$\funp{P}_{\textrm{lm}}(\seq{t})$被定义为$\funp{P}(t_i|t_{i-1})(i=1,2,...,l)$的连乘\footnote{为了确保数学表达的准确性，本书中定义$\funp{P}(t_1|t_0) \equiv \funp{P}(t_1)$}，其中$\funp{P}(t_i|t_{i-1})(i=1,2,...,l)$表示前面一个单词为$t_{i-1}$时，当前单词为$t_i$的概率。语言模型的训练方法可以参看{\chaptertwo}相关内容。
\parinterval 回到建模问题上来。既然语言模型可以帮助系统度量每个译文的流畅度，那么可以使用它对翻译进行打分。一种简单的方法是把语言模型$\funp{P}_{\textrm{lm}}{(\seq{t})}$ 和公式\eqref{eq:5-7}中的$g(\seq{s},\seq{t})$相乘，这样就得到了一个新的$g(\seq{s},\seq{t})$，它同时考虑了翻译准确性（$\prod_{j,i \in \widehat{A}}{\funp{P}(s_j,t_i)}$）和流畅度（$\funp{P}_{\textrm{lm}}(\seq{t})$）:
\begin{eqnarray}
g(\seq{s},\seq{t}) \equiv \prod_{j,i \in \widehat{A}}{\funp{P}(s_j,t_i)} \times \funp{P}_{\textrm{lm}}(\seq{t})
\label{eq:5-10}
\end{eqnarray}
\parinterval 如图\ref{fig:5-9}所示，语言模型$\funp{P}_{\textrm{lm}}(\seq{t})$分别给$\seq{t}^{'}$和$\seq{t}^{”}$赋予0.0107和0.0009的概率，这表明句子$\seq{t}^{'}$更符合英文的表达，这与期望是相吻合的。它们再分别乘以$\prod_{j,i \in \widehat{A}}{\funp{P}(s_j},t_i)$的值，就得到公式\eqref{eq:5-10}定义的函数$g(\cdot)$的值。显然句子$\seq{t}^{'}$的分数更高。至此，完成了对函数$g(\seq{s},\seq{t})$的一个简单定义，把它带入公式\eqref{eq:5-6}就得到了同时考虑准确性和流畅性的句子级统计翻译模型。
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-scores-of-different-translation_model&language_model}
\caption{同一个源语言句子的不同译文所对应的语言模型得分和翻译模型得分}
\label{fig:5-9}
\end{figure}
%----------------------------------------------
%----------------------------------------------------------------------------------------
% NEW SUB-SECTION
%----------------------------------------------------------------------------------------
\subsection{解码}
\label{sec:simple-decoding}
\parinterval 解码是指在得到翻译模型后，对于新输入的句子生成最佳译文的过程。具体来说，当给定任意的源语言句子$\seq{s}$，解码系统要找到翻译概率最大的目标语译文$\hat{\seq{t}}$。这个过程可以被形式化描述为：
\begin{eqnarray}
\widehat{\seq{t}}=\argmax_{\seq{t}} \funp{P}(\seq{t}|\seq{s})
\label{eq:5-11}
\end{eqnarray}
\noindent 其中$\argmax_{\seq{t}} \funp{P}(\seq{t}|\seq{s})$表示找到使$\funp{P}(\seq{t}|\seq{s})$达到最大时的译文$\seq{t}$。结合上一小节中关于$\funp{P}(\seq{t}|\seq{s})$的定义，把公式\eqref{eq:5-6}带入公式\eqref{eq:5-11}得到：
\begin{eqnarray}
\widehat{\seq{t}}=\argmax_{\seq{t}}\frac{g(\seq{s},\seq{t})}{\sum_{\seq{t}^{'}g(\seq{s},\seq{t}^{'})}}
\label{eq:5-12}
\end{eqnarray}
\parinterval 在公式\eqref{eq:5-12}中，可以发现${\sum_{\seq{t}^{'}g(\seq{s},\seq{t}^{'})}}$是一个关于$\seq{s}$的函数，当给定源语句$\seq{s}$时，它是一个常数，而且$g(\cdot) \ge 0$，因此${\sum_{\seq{t}^{'}g(\seq{s},\seq{t}^{'})}}$不影响对$\widehat{\seq{t}}$的求解，也不需要计算。基于此，公式\eqref{eq:5-12}可以被化简为：
\begin{eqnarray}
\widehat{\seq{t}}=\argmax_{\seq{t}}g(\seq{s},\seq{t})
\label{eq:5-13}
\end{eqnarray}
\parinterval 公式\eqref{eq:5-13}定义了解码的目标，剩下的问题是实现$\argmax$，以快速准确地找到最佳译文$\widehat{\seq{t}}$。但是，简单遍历所有可能的译文并计算$g(\seq{s},\seq{t})$ 的值是不可行的，因为所有潜在译文构成的搜索空间是十分巨大的。为了理解机器翻译的搜索空间的规模，假设源语言句子$\seq{s}$有$m$个词，每个词有$n$个可能的翻译候选。如果从左到右一步步翻译每个源语言单词，那么简单的顺序翻译会有$n^m$种组合。如果进一步考虑目标语单词的任意调序，每一种对翻译候选进行选择的结果又会对应$m!$种不同的排序。因此，源语句子$\seq{s}$至少有$n^m \cdot m!$ 个不同的译文。
\parinterval $n^{m}\cdot m!$是什么样的概念呢？如表\ref{tab:5-2}所示，当$m$和$n$分别为2和10时，译文只有200个，不算多。但是当$m$和$n$分别为20和10时，即源语言句子的长度20，每个词有10个候选译文，系统会面对$2.4329 \times 10^{38}$个不同的译文，这几乎是不可计算的。
%----------------------------------------------
\begin{table}[htp]{
\begin{center}
\caption{机器翻译搜索空间大小的示例}
\label{tab:5-2}
\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{table}
%----------------------------------------------
\parinterval 已经有工作证明机器翻译问题是NP难的\upcite{knight1999decoding}。对于如此巨大的搜索空间，需要一种十分高效的搜索算法才能实现机器翻译的解码。在{\chaptertwo}已经介绍一些常用的搜索方法。这里使用一种贪婪的搜索方法实现机器翻译的解码。它把解码分成若干步骤，每步只翻译一个单词，并保留当前“ 最好”的结果，直至所有源语言单词都被翻译完毕。
\vspace{0.3em}
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-greedy-mt-decoding-pseudo-code}
\caption{贪婪的机器翻译解码算法的伪代码}
\label{fig:5-10}
\end{figure}
%----------------------------------------------
\parinterval 图\ref{fig:5-10}给出了贪婪解码算法的伪代码。其中$\pi$保存所有源语单词的候选译文，$\pi[j]$表示第$j$个源语单词的翻译候选的集合，$best$保存当前最好的翻译结果，$h$保存当前步生成的所有译文候选。算法的主体有两层循环，在内层循环中如果第$j$个源语单词没有被翻译过，则用$best$和它的候选译文$\pi[j]$生成新的翻译，再存于$h$中，即操作$h=h\cup{\textrm{Join}(best,\pi[j])}$。外层循环再从$h$中选择得分最高的结果存于$best$中，即操作$best=\textrm{PruneForTop1}(h)$；同时标识相应的源语单词已翻译，即$used[best.j]=true$。
%----------------------------------------------
%\begin{figure}[htp]
% \centering
%\subfigure{\input{./Chapter5/Figures/figure-greedy-mt-decoding-process-1}}
%\subfigure{\input{./Chapter5/Figures/greedy-mt-decoding-process-3}}
%\setlength{\belowcaptionskip}{14.0em}
%\caption{贪婪的机器翻译解码过程实例}
%\label{fig:5-11}
%\end{figure}
%----------------------------------------------
%----------------------------------------------
\begin{figure}[htp]
\centering
\subfigure{\input{./Chapter5/Figures/figure-greedy-mt-decoding-process-1}}
\subfigure{\input{./Chapter5/Figures/figure-greedy-mt-decoding-process-3}}
\caption{贪婪的机器翻译解码过程实例}
\label{fig:5-11}
\end{figure}
%----------------------------------------------
该算法的核心在于，系统一直维护一个当前最好的结果，之后每一步考虑扩展这个结果的所有可能，并计算模型得分，然后再保留扩展后的最好结果。注意，在每一步中，只有排名第一的结果才会被保留，其他结果都会被丢弃。这也体现了贪婪的思想。显然这个方法不能保证搜索到全局最优的结果，但是由于每次扩展只考虑一个最好的结果，因此该方法速度很快。图\ref{fig:5-11}给出了算法执行过程的简单示例。当然，机器翻译的解码方法有很多，这里仅仅使用简单的贪婪搜索方法来解决机器翻译的解码问题，在后续章节会对更加优秀的解码方法进行介绍。
%----------------------------------------------------------------------------------------
% NEW SECTION
%----------------------------------------------------------------------------------------
\section{噪声信道模型}
\vspace{0.5em}
\parinterval 在\ref{sec:simple-mt-example}节中，我们实现了一个简单的基于词的统计机器翻译模型，内容涉及建模、训练和解码。但是，还有很多问题还没有进行深入讨论，比如，如何处理空翻译？如何对调序问题进行建模？如何用更严密的数学模型描述翻译过程？如何对更加复杂的统计模型进行训练？等等。针对以上问题，本节将系统地介绍IBM统计机器翻译模型。作为经典的机器翻译模型，对IBM模型的学习将有助于对自然语言处理问题建立系统化建模思想，特别是对问题的数学描述方法将会成为理解本书后续内容的基础工具。
\parinterval 首先，重新思考一下人类进行翻译的过程。对于给定的源语句$\seq{s}$，人不会像计算机一样尝试很多的可能，而是快速准确地翻译出一个或者少数几个正确的译文。在人看来，除了正确的译文外，其他的翻译都是不正确的，或者说除了少数的译文人甚至都不会考虑太多其他的可能性。但是，在统计机器翻译的世界里，没有译文是不可能的。换句话说，对于源语言句子$\seq{s}$，所有目标语词串$\seq{t}$都是可能的译文，只是可能性大小不同。这个思想可以通过统计模型实现：每对$(\seq{s},\seq{t})$都有一个概率值$\funp{P}(\seq{t}|\seq{s})$来描述$\seq{s}$翻译为$\seq{t}$ 的好与坏（图\ref{fig:5-12}）。
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-different-translation-candidate-space}
\caption{不同翻译候选空间的对比：人（左）vs 机器翻译 （右）}
\label{fig:5-12}
\end{figure}
%----------------------------------------------
\vspace{-0.5em}
\parinterval IBM模型也是建立在如上统计模型之上。具体来说，IBM模型的基础是{\small\sffamily\bfseries{噪声信道模型}}\index{噪声信道模型}（Noise Channel Model）\index{Noise Channel Model}，它是由Shannon在上世纪40年代末提出来的\upcite{shannon1949communication}，并于上世纪80年代应用在语言识别领域，后来又被Brown等人用于统计机器翻译中\upcite{brown1990statistical,DBLP:journals/coling/BrownPPM94}。
\parinterval 在噪声信道模型中，源语言句子$\seq{s}$（信宿）被看作是由目标语言句子$\seq{t}$（信源）经过一个有噪声的信道得到的。如果知道了$\seq{s}$和信道的性质，可以通过$\funp{P}(\seq{t}|\seq{s})$得到信源的信息，这个过程如图\ref{fig:5-13}所示。
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-noise-channel-model}
\caption{噪声信道模型}
\label{fig:5-13}
\end{figure}
%----------------------------------------------
\parinterval 举个例子，对于汉译英的翻译任务，英语句子$\seq{t}$可以被看作是汉语句子$\seq{s}$加入噪声通过信道后得到的结果。换句话说，汉语句子经过噪声-信道传输时发生了变化，在信道的输出端呈现为英语句子。于是需要根据观察到的汉语特征，通过概率$\funp{P}(\seq{t}|\seq{s})$猜测最为可能的英语句子。这个找到最可能的目标语句（信源）的过程也被称为
{\small\sffamily\bfseries{解码}}（Decoding）。直到今天，解码这个概念也被广泛地使用在机器翻译及相关任务中。这个过程也可以表述为：给定输入$\seq{s}$，找到最可能的输出$\seq{t}$，使得$\funp{P}(\seq{t}|\seq{s})$达到最大：
\begin{eqnarray}
\widehat{\seq{t}}=\argmax_{\seq{t}}\funp{P}(\seq{t}|\seq{s})
\label{eq:5-14}
\end{eqnarray}
\parinterval 公式\eqref{eq:5-14}的核心内容之一是定义$\funp{P}(\seq{t}|\seq{s})$。在IBM模型中，可以使用贝叶斯准则对$\funp{P}(\seq{t}|\seq{s})$进行如下变换：
\begin{eqnarray}
\funp{P}(\seq{t}|\seq{s}) & = &\frac{\funp{P}(\seq{s},\seq{t})}{\funp{P}(\seq{s})} \nonumber \\
& = & \frac{\funp{P}(\seq{s}|\seq{t})\funp{P}(\seq{t})}{\funp{P}(\seq{s})}
\label{eq:5-15}
\end{eqnarray}
\parinterval 公式\eqref{eq:5-15}把$\seq{s}$到$\seq{t}$的翻译概率转化为$\frac{\funp{P}(\seq{s}|\seq{t})\textrm{P(t)}}{\funp{P}(\seq{s})}$，它包括三个部分：
\begin{itemize}
\vspace{0.5em}
\item 第一部分是由译文$\seq{t}$到源语言句子$\seq{s}$的翻译概率$\funp{P}(\seq{s}|\seq{t})$，也被称为翻译模型。它表示给定目标语句$\seq{t}$生成源语句$\seq{s}$的概率。需要注意是翻译的方向已经从$\funp{P}(\seq{t}|\seq{s})$转向了$\funp{P}(\seq{s}|\seq{t})$，但无须刻意地区分，可以简单地理解为翻译模型刻画了$\seq{s}$和$\seq{t}$的翻译对应程度；
\vspace{0.5em}
\item 第二部分是$\funp{P}(\seq{t})$，也被称为语言模型。它表示的是目标语言句子$\seq{t}$出现的可能性；
\vspace{0.5em}
\item 第三部分是$\funp{P}(\seq{s})$，表示源语言句子$\seq{s}$出现的可能性。因为$\seq{s}$是输入的不变量，而且$\funp{P}(\seq{s}) > 0$，所以省略分母部分$\funp{P}(\seq{s})$ 不会影响$\frac{\funp{P}(\seq{s}|\seq{t})\funp{P}(\seq{t})}{\funp{P}(\seq{s})}$最大值的求解。
\vspace{0.5em}
\end{itemize}
于是，机器翻译的目标可以被重新定义为：给定源语言句子$\seq{s}$，寻找这样的目标语言译文$\seq{t}$，它使得翻译模型$\funp{P}(\seq{s}|\seq{t})$和语言模型$\funp{P}(\seq{t})$乘积最大：
\begin{eqnarray}
\widehat{\seq{t}} & = & \argmax_{\seq{t}} \funp{P}(\seq{t}|\seq{s}) \nonumber \\
& = & \argmax_{\seq{t}} \frac{\funp{P}(\seq{s}|\seq{t})\funp{P}(\seq{t})}{\funp{P}(\seq{s})} \nonumber \\
& = & \argmax_{\seq{t}} \funp{P}(\seq{s}|\seq{t})\funp{P}(\seq{t})
\label{eq:5-16}
\end{eqnarray}
\parinterval 公式\eqref{eq:5-16}展示了IBM模型最基础的建模方式，它把模型分解为两项：（反向）翻译模型$\funp{P}(\seq{s}|\seq{t})$和语言模型$\funp{P}(\seq{t})$。一个很自然的问题是：直接用$\funp{P}(\seq{t}|\seq{s})$定义翻译问题不就可以了吗，为什么要用$\funp{P}(\seq{s}|\seq{t})$和$\funp{P}(\seq{t})$的联合模型？从理论上来说，正向翻译模型$\funp{P}(\seq{t}|\seq{s})$和反向翻译模型$\funp{P}(\seq{s}|\seq{t})$的数学建模可以是一样的，因为我们只需要在建模的过程中把两个语言调换即可。使用$\funp{P}(\seq{s}|\seq{t})$和$\funp{P}(\seq{t})$的联合模型的意义在于引入了语言模型，它可以很好地对译文的流畅度进行评价，确保结果是通顺的目标语言句子。
\parinterval 可以回忆一下\ref{sec:sentence-level-translation}节中讨论的问题，如果只使用翻译模型可能会造成一个局面：译文的单词都和源语言单词对应的很好，但是由于语序的问题，读起来却不像人说的话。从这个角度说，引入语言模型是十分必要的。这个问题在Brown等人的论文中也有讨论\upcite{DBLP:journals/coling/BrownPPM94}，他们提到单纯使用$\funp{P}(\seq{s}|\seq{t})$会把概率分配给一些翻译对应比较好但是不合法的目标语句子，而且这部分概率可能会很大，影响模型的决策。这也正体现了IBM模型的创新之处，作者用数学技巧把$\funp{P}(\seq{t})$引入进来，保证了系统的输出是通顺的译文。语言模型也被广泛使用在语音识别等领域以保证结果的流畅性，甚至应用的历史比机器翻译要长得多，这里的方法也有借鉴相关工作的味道。
实际上，在机器翻译中引入语言模型是一个很深刻的概念。在IBM模型之后相当长的时间里，语言模型一直是机器翻译各个部件中最重要的部分。对译文连贯性的建模也是所有系统中需要包含的内容（即使隐形体现）。
%----------------------------------------------------------------------------------------
% NEW SECTION
%----------------------------------------------------------------------------------------
\section{统计机器翻译的三个基本问题}
\parinterval 公式\eqref{eq:5-16}给出了统计机器翻译的数学描述。为了实现这个过程，面临着三个基本问题：
\begin{itemize}
\vspace{0.5em}
\item {\small\sffamily\bfseries{建模}}（Modeling）：如何建立$\funp{P}(\seq{s}|\seq{t})$和$\funp{P}(\seq{t})$的数学模型。换句话说，需要用可计算的方式对翻译问题和语言建模问题进行描述，这也是最核心的问题。
\vspace{0.5em}
\item {\small\sffamily\bfseries{训练}}（Training）：如何获得$\funp{P}(\seq{s}|\seq{t})$和$\funp{P}(\seq{t})$所需的参数。即从数据中得到模型的最优参数。
\vspace{0.5em}
\item {\small\sffamily\bfseries{解码}}（Decoding）：如何完成搜索最优解的过程。即完成$\argmax$。
\vspace{0.5em}
\end{itemize}
\parinterval 为了理解以上的问题，可以先回忆一下\ref{sec:sentence-level-translation}小节中的公式\eqref{eq:5-10}，即$g(\seq{s},\seq{t})$函数的定义，它用于评估一个译文的好与坏。如图\ref{fig:5-14}所示，$g(\seq{s},\seq{t})$函数与公式\eqref{eq:5-16}的建模方式非常一致，即$g(\seq{s},\seq{t})$函数中红色部分描述译文$\seq{t}$的可能性大小，对应翻译模型$\funp{P}(\seq{s}|\seq{t})$；蓝色部分描述译文的平滑或流畅程度，对应语言模型$\funp{P}(\seq{t})$。尽管这种对应并不十分严格的，但也可以看出在处理机器翻译问题上，很多想法的本质是一样的。
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-correspondence-between-ibm-model&formula-1.13}
\caption{IBM模型与公式\eqref{eq:5-10}的对应关系}
\label{fig:5-14}
\end{figure}
%----------------------------------------------
\parinterval 但$g(\seq{s},\seq{t})$函数的建模很粗糙，因此下面将介绍的IBM模型对问题有着更严谨的定义与建模。对于语言模型$\funp{P}(\seq{t})$和解码过程在前面的内容中都有介绍，所以本章的后半部分会重点介绍如何定义翻译模型$\funp{P}(\seq{s}|\seq{t})$以及如何训练模型参数。
%----------------------------------------------------------------------------------------
% NEW SUB-SECTION
%----------------------------------------------------------------------------------------
\subsection{词对齐}
\parinterval IBM模型的一个基本的假设是词对齐假设。词对齐描述了源语言句子和目标语句子之间单词级别的对应。具体来说，给定源语句子$\seq{s}=s_1...s_m$和目标语译文$\seq{t}=t_1...t_l$，IBM模型假设词对齐具有如下两个性质。
\begin{itemize}
\vspace{0.5em}
\item 一个源语言单词只能对应一个目标语言单词。如图\ref{fig:5-15}所示，(a)和(c)都满足该条件，尽管(c)中的“谢谢”和“你”都对应“thanks”，但并不违背这个约束。而(b)不满足约束，因为“ 谢谢”同时对应到了两个目标语单词上。这个约束条件也导致这里的词对齐变成一种{\small\sffamily\bfseries{非对称的词对齐}}\index{非对称的词对齐}（Asymmetric Word Alignment）\index{Asymmetric Word Alignment}，因为它只对源语言做了约束，但是目标语言没有。使用这样的约束的目的是为了减少建模的复杂度。在IBM模型之后的方法中也提出了双向词对齐，用于建模一个源语言单词对应到多个目标语单词的情况\upcite{och2003systematic}。
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-different-alignment-comparison}
\setlength{\belowcaptionskip}{-0.5em}
\caption{不同词对齐对比}
\label{fig:5-15}
\end{figure}
%----------------------------------------------
\item 源语言单词可以翻译为空，这时它对应到一个虚拟或伪造的目标语单词$t_0$。在图\ref{fig:5-16}所示的例子中，“在”没有对应到“on the table”中的任意一个词，而是把它对应到$t_0$上。这样，所有的源语言单词都能找到一个目标语单词对应。这种设计也很好地引入了{\small\sffamily\bfseries{空对齐}}\index{空对齐}（Empty Alignment\index{Empty Alignment}）的思想，即源语言单词不对应任何真实存在的单词的情况。而这种空对齐的情况在翻译中是频繁出现的，比如虚词的翻译。
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-word-alignment-instance}
\setlength{\belowcaptionskip}{-0.5em}
\caption{词对齐实例（“在”对应到$t_0$）}
\label{fig:5-16}
\end{figure}
%----------------------------------------------
\end{itemize}
\parinterval 通常，把词对齐记为$\seq{a}$，它由$a_1$到$a_m$共$m$个词对齐连接组成，即$\seq{a}=a_1...a_m$。$a_j$表示第$j$个源语单词$s_j$对应的目标语单词的位置。在图\ref{fig:5-16}的例子中，词对齐关系可以记为$a_1=0, a_2=3, a_3=1$，即第1个源语单词“在”对应到目标语译文的第0个位置，第2个源语单词“桌子”对应到目标语译文的第3个位置，第3个源语单词“上”对应到目标语译文的第1个位置。
%----------------------------------------------------------------------------------------
% NEW SUB-SECTION
%----------------------------------------------------------------------------------------
\subsection{基于词对齐的翻译模型}
\parinterval 直接准确估计$\funp{P}(\seq{s}|\seq{t})$很难，训练数据只能覆盖整个样本空间非常小的一部分，绝大多数句子在训练数据中一次也没出现过。为了解决这个问题，IBM模型假设：句子之间的对应可以由单词之间的对应进行表示。于是，翻译句子的概率可以被转化为词对齐生成的概率：
\begin{eqnarray}
\funp{P}(\seq{s}|\seq{t})= \sum_{\seq{a}}\funp{P}(\seq{s},\seq{a}|\seq{t})
\label{eq:5-17}
\end{eqnarray}
\parinterval 公式\eqref{eq:5-17}使用了简单的全概率公式把$\funp{P}(\seq{s}|\seq{t})$进行展开。通过访问$\seq{s}$和$\seq{t}$之间所有可能的词对齐$\seq{a}$，并把对应的对齐概率进行求和，得到了$\seq{t}$到$\seq{s}$的翻译概率。这里，可以把词对齐看作翻译的隐含变量，这样从$\seq{t}$到$\seq{s}$的生成就变为从$\seq{t}$同时生成$\seq{s}$和隐含变量$\seq{a}$的问题。引入隐含变量是生成式模型常用的手段，通过使用隐含变量，可以把较为困难的端到端学习问题转化为分步学习问题。
\parinterval 举个例子说明公式\eqref{eq:5-17}的实际意义。如图\ref{fig:5-17}所示，可以把从“谢谢\ 你”到“thank you”的翻译分解为9种可能的词对齐。因为源语言句子$\seq{s}$有2个词，目标语言句子$\seq{t}$加上空标记$t_0$共3个词，因此每个源语言单词有3个可能对齐的位置，整个句子共有$3\times3=9$种可能的词对齐。
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-alignment-of-all-words-in-zh-en-sentence}
\caption{一个汉译英句对的所有词对齐可能}
\label{fig:5-17}
\end{figure}
%----------------------------------------------
\parinterval 接下来的问题是如何定义$\funp{P}(\seq{s},\seq{a}|\seq{t})$\ \dash \ 即定义词对齐的生成概率。但是，隐含变量$\seq{a}$仍然很复杂，因此直接定义$\funp{P}(\seq{s},\seq{a}|\seq{t})$也很困难，在IBM模型中，为了化简问题，$\funp{P}(\seq{s},\seq{a}|\seq{t})$被进一步分解。使用链式法则，可以得到：
\begin{eqnarray}
\funp{P}(\seq{s},\seq{a}|\seq{t})=\funp{P}(m|\seq{t})\prod_{j=1}^{m}{\funp{P}(a_j|\seq{a}{}_1^{j-1},\seq{s}{}_1^{j-1},m,\seq{t})\funp{P}(s_j|\seq{a}{}_1^{j},\seq{s}{}_1^{j-1},m,\seq{t})}
\label{eq:5-18}
\end{eqnarray}
\noindent 其中$s_j$和$a_j$分别表示第$j$个源语言单词及第$j$个源语言单词对齐到的目标位置，\seq{s}${{}_1^{j-1}}$表示前$j-1$个源语言单词（即\seq{s}${}_1^{j-1}=s_1...s_{j-1}$），\seq{a}${}_1^{j-1}$表示前$j-1$个源语言的词对齐（即\seq{a}${}_1^{j-1}=a_1...a_{j-1}$），$m$表示源语句子的长度。公式\eqref{eq:5-18}将$\funp{P}(\seq{s},\seq{a}|\seq{t})$分解为四个部分，具体含义如下：
\begin{itemize}
\vspace{0.5em}
\item 根据译文$\seq{t}$选择源文$\seq{s}$的长度$m$，用$\funp{P}(m|\seq{t})$表示；
\vspace{0.5em}
\item 当确定源语言句子的长度$m$后，循环每个位置$j$逐次生成每个源语言单词$s_j$，也就是$\prod_{j=1}^m \cdot$计算的内容；
\vspace{0.5em}
\item 对于每个位置$j$，根据译文$\seq{t}$、源文长度$m$、已经生成的源语言单词$\seq{s}_1^{j-1}$和对齐$\seq{a}_1^{j-1}$，生成第$j$个位置的对齐结果$a_j$，用$\funp{P}(a_j|\seq{a}_1^{j-1},\seq{s}_1^{j-1},m,\seq{t})$表示；
\vspace{0.5em}
\item 对于每个位置$j$，根据译文$\seq{t}$、源文长度$m$、已经生成的源语言单词$\seq{s}_1^{j-1}$和对齐$\seq{a}_1^j$，生成第$j$个位置的源语言单词$s_j$，用$\funp{P}(s_j|\seq{a}_1^{j},\seq{s}_1^{j-1},m,\seq{t})$表示。
\vspace{0.5em}
\end{itemize}
\parinterval 换句话说，当求$\funp{P}(\seq{s},\seq{a}|\seq{t})$时，首先根据译文$\seq{t}$确定源语言句子$\seq{s}$的长度$m$；当知道源语言句子有多少个单词后，循环$m$次，依次生成第1个到第$m$个源语言单词；当生成第$j$个源语言单词时，要先确定它是由哪个目标语译文单词生成的，即确定生成的源语言单词对应的译文单词的位置；当知道了目标语译文单词的位置，就能确定第$j$个位置的源语言单词。
\parinterval 需要注意的是公式\eqref{eq:5-18}定义的模型并没有做任何化简和假设，也就是说公式的左右两端是严格相等的。在后面的内容中会看到，这种将一个整体进行拆分的方法可以有助于分步骤化简并处理问题。
%----------------------------------------------------------------------------------------
% NEW SUB-SECTION
%----------------------------------------------------------------------------------------
\subsection{基于词对齐的翻译实例}
\parinterval 用前面图\ref{fig:5-16}中例子来对公式\eqref{eq:5-18}进行说明。例子中，源语言句子“在\ \ 桌子\ \ 上”目标语译文“on the table”之间的词对齐为$\seq{a}=\{\textrm{1-0, 2-3, 3-1}\}$。 公式\eqref{eq:5-18}的计算过程如下：
\begin{itemize}
\vspace{0.5em}
\item 首先根据译文确定源文$\seq{s}$的单词数量（$m=3$），即$\funp{P}(m=3|\textrm{“}t_0\;\textrm{on\;the\;table”})$；
\vspace{0.5em}
\item 再确定源语言单词$s_1$由谁生成的且生成的是什么。可以看到$s_1$由第0个目标语单词生成，也就是$t_0$，表示为$\funp{P}(a_1\;= 0\;\; |\phi,\phi,3,\textrm{“}t_0\;\textrm{on\;the\;table”})$，其中$\phi$表示空。当知道了$s_1$是由$t_0$生成的，就可以通过$t_0$生成源语言第一个单词“在”，即$\funp{P}(s_1\;= \textrm{“ 在”}\;|\{1-0\},\phi,3,\textrm{“$t_0$\;on\;the\;table”}) $；
\vspace{0.5em}
\item 类似于生成$s_1$，依次确定源语言单词$s_2$和$s_3$由谁生成且生成的是什么；
\vspace{0.5em}
\end{itemize}
\parinterval 最后得到基于词对齐$\seq{a}$的翻译概率为：
\begin{eqnarray}
\funp{P}(\seq{s},\seq{a}|\seq{t})\; &= & \funp{P}(m|\seq{t}) \prod\limits_{j=1}^{m} \funp{P}(a_j|a_{1}^{j-1},s_{1}^{j-1},m,\seq{t}) \funp{P}(s_j|a_{1}^{j},s_{1}^{j-1},m,\seq{t}) \nonumber \\
&=&\funp{P}(m=3 \mid \textrm{$t_0$ on the table}){\times} \nonumber \\
&&{\funp{P}(a_1=0 \mid \phi,\phi,3,\textrm{$t_0$ on the table}){\times} } \nonumber \\
&&{\funp{P}(s_1=\textrm{在} \mid \textrm{\{1-0\}},\phi,3,\textrm{$t_0$ on the table}){\times} } \nonumber \\
&&{\funp{P}(a_2=3 \mid \textrm{\{1-0\}},\textrm{在},3,\textrm{$t_0$ on the table}) {\times}} \nonumber \\
&&{\funp{P}(s_2=\textrm{桌子} \mid \textrm{\{1-0, 2-3\}},\textrm{在},3,\textrm{$t_0$ on the table}) {\times}} \nonumber \\
&&{\funp{P}(a_3=1 \mid \textrm{\{1-0, 2-3\}},\textrm{在\ \ 桌子},3,\textrm{$t_0$ on the table}) {\times}} \nonumber \\
&&{\funp{P}(s_3=\textrm{上} \mid \textrm{\{1-0, 2-3, 3-1\}},\textrm{在\ \ 桌子},3,\textrm{$t_0$ on the table}) }
\label{eq:5-19}
\end{eqnarray}
%----------------------------------------------------------------------------------------
% NEW SECTION
%----------------------------------------------------------------------------------------
\sectionnewpage
\section{IBM模型1}
\parinterval 公式\eqref{eq:5-17}和公式\eqref{eq:5-18}把翻译问题定义为对译文和词对齐同时进行生成的问题。其中有两个问题：
\begin{itemize}
\vspace{0.3em}
\item 首先，公式\eqref{eq:5-17}的右端（$ \sum_{\seq{a}}\funp{P}(\seq{s},\seq{a}|\seq{t})$）要求对所有的词对齐概率进行求和，但是词对齐的数量随着句子长度是呈指数增长，如何遍历所有的对齐$\seq{a}$？
\vspace{0.3em}
\item 其次，公式\eqref{eq:5-18}虽然对词对齐的问题进行了描述，但是模型中的很多参数仍然很复杂，如何计算$\funp{P}(m|\seq{t})$、$\funp{P}(a_j|a_1^{j-1},s_1^{j-1},m,\seq{t})$ 和$\funp{P}(s_j|a_1^{j},s_1^{j-1},m,\seq{t})$？
\vspace{0.3em}
\end{itemize}
针对这些问题，Brown等人总共提出了5种解决方案，这也就是被后人所熟知的5个IBM翻译模型。第一个问题可以通过一定的数学或者工程技巧进行求解；第二个问题可以通过一些假设进行化简，依据化简的层次和复杂度不同，可以分为IBM模型1、IBM模型2、IBM模型3、IBM模型4以及IBM模型5。本节首先介绍较为简单的IBM模型1。
%----------------------------------------------------------------------------------------
% NEW SUB-SECTION
%----------------------------------------------------------------------------------------
\vspace{-0.5em}
\subsection{IBM模型1}
\parinterval IBM模型1对公式\eqref{eq:5-18}中的三项进行了简化。具体方法如下：
\begin{itemize}
\item 假设$\funp{P}(m|\seq{t})$为常数$\varepsilon$，即源语言句子长度的生成概率服从均匀分布，如下：
\begin{eqnarray}
\funp{P}(m|\seq{t})\; \equiv \; \varepsilon
\label{eq:5-20}
\end{eqnarray}
\item 对齐概率$\funp{P}(a_j|a_1^{j-1},s_1^{j-1},m,\seq{t})$仅依赖于译文长度$l$，即每个词对齐连接的生成概率也服从均匀分布。换句话说，对于任何源语言位置$j$对齐到目标语言任何位置都是等概率的。比如译文为“on the table”，再加上$t_0$共4个位置，相应的，任意源语单词对齐到这4个位置的概率是一样的。具体描述如下：
\begin{eqnarray}
\funp{P}(a_j|a_1^{j-1},s_1^{j-1},m,\seq{t}) \equiv \frac{1}{l+1}
\label{eq:5-21}
\end{eqnarray}
\item 源语单词$s_j$的生成概率$\funp{P}(s_j|a_1^{j},s_1^{j-1},m,\seq{t})$仅依赖与其对齐的译文单词$t_{a_j}$，即词汇翻译概率$f(s_j|t_{a_j})$。此时词汇翻译概率满足$\sum_{s_j}{f(s_j|t_{a_j})}=1$。比如在图\ref{fig:5-18}表示的例子中，源语单词“上”出现的概率只和与它对齐的单词“on”有关系，与其他单词没有关系。
\begin{eqnarray}
\funp{P}(s_j|a_1^{j},s_1^{j-1},m,\seq{t}) \equiv f(s_j|t_{a_j})
\label{eq:5-22}
\end{eqnarray}
用一个简单的例子对公式\eqref{eq:5-22}进行说明。比如，在图\ref{fig:5-18}中，“桌子”对齐到“table”，可被描述为$f(s_2 |t_{a_2})=f(\textrm{“桌子”}|\textrm{“table”})$，表示给定“table”翻译为“桌子”的概率。通常，$f(s_2 |t_{a_2})$被认为是一种概率词典，它反应了两种语言词汇一级的对应关系。
\end{itemize}
\parinterval 将上述三个假设和公式\eqref{eq:5-18}代入公式\eqref{eq:5-17}中，得到$\funp{P}(\seq{s}|\seq{t})$的表达式：
\begin{eqnarray}
\funp{P}(\seq{s}|\seq{t}) & = & \sum_{\seq{a}}{\funp{P}(\seq{s},\seq{a}|\seq{t})} \nonumber \\
& = & \sum_{\seq{a}}{\funp{P}(m|\seq{t})}\prod_{j=1}^{m}{\funp{P}(a_j|a_1^{j-1},s_1^{j-1},m,\seq{t})\funp{P}(s_j |a_1^j,s_1^{j-1},m,\seq{t})} \nonumber \\
& = & \sum_{\seq{a}}{\varepsilon}\prod_{j=1}^{m}{\frac{1}{l+1}f(s_j|t_{a_j})} \nonumber \\
& = & \sum_{\seq{a}}{\frac{\varepsilon}{(l+1)^m}}\prod_{j=1}^{m}f(s_j|t_{a_j})
\label{eq:5-23}
\end{eqnarray}
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-zh-en-bilingual-sentence-pairs}
\caption{汉译英双语句对及词对齐}
\label{fig:5-18}
\end{figure}
%----------------------------------------------
\parinterval 在公式\eqref{eq:5-23}中，需要遍历所有的词对齐，即$ \sum_{\seq{a}}{\cdot}$。但这种表示不够直观，因此可以把这个过程重新表示为如下形式：
\begin{eqnarray}
\funp{P}(\seq{s}|\seq{t})={\sum_{a_1=0}^{l}\cdots}{\sum_{a_m=0}^{l}\frac{\varepsilon}{(l+1)^m}}{\prod_{j=1}^{m}f(s_j|t_{a_j})}
\label{eq:5-24}
\end{eqnarray}
\parinterval 公式\eqref{eq:5-24}分为两个主要部分。第一部分：遍历所有的对齐$\seq{a}$。其中$\seq{a}$由$\{a_1,...,a_m\}$\\ 组成，每个$a_j\in \{a_1,...,a_m\}$从译文的开始位置$(0)$循环到截止位置$(l)$。如图\ref{fig:5-19}表示的例子，描述的是源语单词$s_3$从译文的开始$t_0$遍历到结尾$t_3$，即$a_3$的取值范围。第二部分: 对于每个$\seq{a}$累加对齐概率$\funp{P}(\seq{s},a| \seq{t})=\frac{\varepsilon}{(l+1)^m}{\prod_{j=1}^{m}f(s_j|t_{a_j})}$。
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-formula-3.25-part-1-example}
\caption{公式{\eqref{eq:5-24}}第一部分实例}
\label{fig:5-19}
\end{figure}
%----------------------------------------------
\parinterval 这样就得到了IBM模型1中句子翻译概率的计算式。可以看出IBM模型1的假设把翻译模型化简成了非常简单的形式。对于给定的$\seq{s}$，$\seq{a}$和$\seq{t}$，只要知道$\varepsilon$和$f(s_j |t_{a_j })$ 就可以计算出$\funp{P}(\seq{s}| \seq{t})$。
%----------------------------------------------------------------------------------------
% NEW SUB-SECTION
%----------------------------------------------------------------------------------------
\subsection{解码及计算优化}\label{decoding&computational-optimization}
\parinterval 如果模型参数给定，可以使用IBM模型1对新的句子进行翻译。比如，可以使用\ref{sec:simple-decoding}节描述的解码方法搜索最优译文。在搜索过程中，只需要通过公式\eqref{eq:5-24}计算每个译文候选的IBM模型翻译概率。但是，公式\eqref{eq:5-24}的高计算复杂度导致这些模型很难直接使用。以IBM模型1为例，这里把公式\eqref{eq:5-24}重写为：
\begin{eqnarray}
\funp{P}(\seq{s}| \seq{t}) = \frac{\varepsilon}{(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{次循环}}
\label{eq:5-27}
\end{eqnarray}
\noindent 可以看到，遍历所有的词对齐需要$(l+1)^m$次循环，遍历所有源语言位置累计$f(s_j|t_{a_j})$需要$m$次循环，因此这个模型的计算复杂度为$O((l+1)^m m)$。当$m$较大时，计算这样的模型几乎是不可能的。不过，经过仔细观察，可以发现公式右端的部分有另外一种计算方法，如下：
\begin{eqnarray}
\sum\limits_{a_1=0}^{l} ... \sum\limits_{a_m=0}^{l} \prod\limits_{j=1}^{m} f(s_j|t_{a_j}) = \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i)
\label{eq:5-28}
\end{eqnarray}
\noindent 公式\eqref{eq:5-28}的技巧在于把若干个乘积的加法（等式左手端）转化为若干加法结果的乘积（等式右手端），这样省去了多次循环，把$O((l+1)^m m)$的计算复杂度降为$O((l+1)m)$。此外，公式\eqref{eq:5-28}相比公式\eqref{eq:5-27}的另一个优点在于，公式\eqref{eq:5-28}中乘法的数量更少，因为现代计算机中乘法运算的代价要高于加法，因此公式\eqref{eq:5-28}的计算机实现效率更高。图\ref{fig:5-21} 对这个过程进行了进一步解释。
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-example-of-formula3.29}
\caption{$\sum\limits_{a_1=0}^{l} ... \sum\limits_{a_m=0}^{l} \prod\limits_{j=1}^{m} f(s_j|t_{a_j}) = \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i)$的实例}
\label{fig:5-21}
\end{figure}
%----------------------------------------------
\parinterval 接着，利用公式\eqref{eq:5-28}的方式，可以把公式\eqref{eq:5-24}重写表示为：
\begin{eqnarray}
\textrm{IBM模型1：\ \ \ \ } \funp{P}(\seq{s}| \seq{t}) & = & \frac{\varepsilon}{(l+1)^{m}} \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i) \label{eq:5-64}
\label{eq:5-29}
\end{eqnarray}
公式\eqref{eq:5-64}是IBM模型1的最终表达式，在解码和训练中可以被直接使用。
%----------------------------------------------------------------------------------------
% NEW SUB-SECTION
%----------------------------------------------------------------------------------------
\subsection{训练}
\parinterval 在完成了建模和解码的基础上，剩下的问题是如何得到模型的参数。这也是整个统计机器翻译里最重要的内容。下面将会对IBM模型1的参数估计方法进行介绍。
%----------------------------------------------------------------------------------------
% NEW SUBSUB-SECTION
%----------------------------------------------------------------------------------------
\subsubsection{1. 目标函数}
\parinterval 统计机器翻译模型的训练是一个典型的优化问题。简单来说，训练是指在给定数据集（训练集）上调整参数使得目标函数的值达到最大（或最小），此时得到的参数被称为是该模型在该目标函数下的最优解（图\ref{fig:5-22}）。
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-the-optimal-solution-to-an-objective-function}
\caption{一个目标函数的最优解}
\label{fig:5-22}
\end{figure}
%----------------------------------------------
\parinterval 在IBM模型中，优化的目标函数被定义为$\funp{P}(\seq{s}| \seq{t})$。也就是，对于给定的句对$(\seq{s},\seq{t})$，最大化翻译概率$\funp{P}(\seq{s}| \seq{t})$。 这里用符号$\funp{P}_{\theta}(\seq{s}|\seq{t})$表示模型由参数$\theta$决定，模型训练可以被描述为对目标函数$\funp{P}_{\theta}(\seq{s}|\seq{t})$的优化过程：
\begin{eqnarray}
\widehat{\theta}=\argmax_{\theta}\funp{P}_{\theta}(\seq{s}|\seq{t})
\label{eq:5-30}
\end{eqnarray}
\noindent 其中，$\argmax_{\theta}$表示求最优参数的过程（或优化过程）。
\parinterval 公式\eqref{eq:5-30}实际上也是一种基于极大似然的模型训练方法。这里，可以把$\funp{P}_{\theta}(\seq{s}|\seq{t})$看作是模型对数据描述的一个似然函数，记作$L(\seq{s},\seq{t};\theta)$。也就是，优化目标是对似然函数的优化：$\{\widehat{\theta}\}=\{\argmax_{\theta \in \Theta}L(\seq{s},\seq{t};\theta)\}$，其中\{$\widehat{\theta}$\} 表示可能有多个结果，$\Theta$表示参数空间。
\parinterval 回到IBM模型的优化问题上。以IBM模型1为例，优化的目标是最大化翻译概率$\funp{P}(\seq{s}| \seq{t})$。使用公式\eqref{eq:5-64} ，可以把这个目标表述为：
\begin{eqnarray}
& & \textrm{max}\Big(\frac{\varepsilon}{(l+1)^m}\prod_{j=1}^{m}\sum_{i=0}^{l}{f({s_j|t_i})}\Big) \nonumber \\
& \textrm{s.t.} & \textrm{任意单词} t_{y}:\;\sum_{s_x}{f(s_x|t_y)}=1 \nonumber
\label{eq:5-31}
\end{eqnarray}
\noindent 其中，$\textrm{max}(\cdot)$表示最大化，$\frac{\varepsilon}{(l+1)^m}\prod_{j=1}^{m}\sum_{i=0}^{l}{f({s_j|t_i})}$是目标函数，$f({s_j|t_i})$是模型的参数，$\sum_{s_x}{f(s_x|t_y)}=1$是优化的约束条件，以保证翻译概率满足归一化的要求。需要注意的是$\{f(s_x |t_y)\}$对应了很多参数，每个源语言单词和每个目标语单词的组合都对应一个参数$f(s_x |t_y)$。
%----------------------------------------------------------------------------------------
% NEW SUBSUB-SECTION
%----------------------------------------------------------------------------------------
\subsubsection {2. 优化}
\parinterval 可以看到，IBM模型的参数训练问题本质上是带约束的目标函数优化问题。由于目标函数是可微分函数，解决这类问题的一种常用手法是把带约束的优化问题转化为不带约束的优化问题。这里用到了{\small\sffamily\bfseries{拉格朗日乘数法}}\index{拉格朗日乘数法}（Lagrange Multiplier Method）\index{The Lagrange Multiplier Method}，它的基本思想是把含有$n$个变量和$m$个约束条件的优化问题转化为含有$n+m$个变量的无约束优化问题。
\parinterval 这里的目标是$\max(\funp{P}_{\theta}(\seq{s}|\seq{t}))$，约束条件是对于任意的目标语单词$t_y$有\\$\sum_{s_x}{\funp{P}(s_x|t_y)}=1$。根据拉格朗日乘数法，可以把上述优化问题重新定义最大化如下拉格朗日函数：
\vspace{-0.5em}
\begin{eqnarray}
L(f,\lambda)=\frac{\varepsilon}{(l+1)^m}\prod_{j=1}^{m}\sum_{i=0}^{l}{f(s_j|t_i)}-\sum_{t_y}{\lambda_{t_y}(\sum_{s_x}{f(s_x|t_y)}-1)}
\label{eq:5-32}
\end{eqnarray}
\vspace{-0.3em}
\parinterval $L(f,\lambda)$包含两部分，$\frac{\varepsilon}{(l+1)^m}\prod_{j=1}^{m}\sum_{i=0}^{l}{f(s_j|t_i)}$是原始的目标函数，\\$\sum_{t_y}{\lambda_{t_y}(\sum_{s_x}{f(s_x|t_y)}-1)}$是原始的约束条件乘以拉格朗日乘数$\lambda_{t_y}$，拉格朗日乘数的数量和约束条件的数量相同。图\ref{fig:5-23}通过图例说明了$L(f,\lambda)$各部分的意义。
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-lagrange-multiplier-method-(ibm-model-1)}
\caption{拉格朗日函数的解释（IBM模型1）}
\label{fig:5-23}
\end{figure}
%----------------------------------------------
\noindent 因为$L(f,\lambda)$是可微分函数，因此可以通过计算$L(f,\lambda)$导数为零的点得到极值点。因为这个模型里仅有$f(s_x|t_y)$一种类型的参数，只需要对如下导数进行计算。
\begin{eqnarray}
\frac{\partial L(f,\lambda)}{\partial f(s_u|t_v)}& = & \frac{\partial \big[ \frac{\varepsilon}{(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{\varepsilon}{(l+1)^{m}} \cdot \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)} - \lambda_{t_v}
\label{eq:5-33}
\end{eqnarray}
\noindent 这里$s_u$和$t_v$分别表示源语言和目标语言词表中的某一个单词。为了求$\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$ 的函数，显然，
$\frac{\partial g(z)}{\partial z} = \alpha \beta z^{\beta-1} = \frac{\beta}{z}\alpha z^{\beta} = \frac{\beta}{z} g(z)$。这里可以把$\prod_{j=1}^{m} \sum_{i=0}^{l} f(s_j|t_i)$看做$g(z)=\alpha z^{\beta}$的实例。首先，令$z=\sum_{i=0}^{l}f(s_u|t_i)$，注意$s_u$为给定的源语单词。然后，把$\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$相同的单词的个数。
\begin{eqnarray}
\beta=\sum_{j=1}^{m} \delta(s_j,s_u)
\label{eq:5-34}
\end{eqnarray}
\noindent 其中，当$x=y$时，$\delta(x,y)=1$，否则为0。
\parinterval 根据$\frac{\partial g(z)}{\partial z} = \frac{\beta}{z} g(z)$，可以得到
\begin{eqnarray}
\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)
\label{eq:5-35}
\end{eqnarray}
\parinterval 根据$\frac{\partial g(z)}{\partial z}$和$\frac{\partial z}{\partial f}$计算的结果，可以得到
\begin{eqnarray}
{\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 \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]}} \cdot{\frac{\partial \big[ \sum\limits_{i=0}^{l}f(s_u|t_i) \big]}{\partial f(s_u|t_v)}}} \nonumber \\
& = &{\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)}
\label{eq:5-36}
\end{eqnarray}
\parinterval 将$\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)}$，得到$L(f,\lambda)$的导数
\begin{eqnarray}
& &{\frac{\partial L(f,\lambda)}{\partial f(s_u|t_v)}}\nonumber \\
&=&{\frac{\varepsilon}{(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 \\
&=&{\frac{\varepsilon}{(l+1)^{m}} \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}}
\label{eq:5-37}
\end{eqnarray}
\parinterval 令$\frac{\partial L(f,\lambda)}{\partial f(s_u|t_v)}=0$，有
\begin{eqnarray}
f(s_u|t_v) = \frac{\lambda_{t_v}^{-1} \varepsilon}{(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)
\label{eq:5-38}
\end{eqnarray}
\parinterval 将上式稍作调整得到下式：
\begin{eqnarray}
f(s_u|t_v) = \lambda_{t_v}^{-1} \frac{\varepsilon}{(l+1)^{m}} \prod\limits_{j=1}^{m} \sum\limits_{i=0}^{l} f(s_j|t_i) \sum\limits_{j=1}^{m} \delta(s_j,s_u) \sum\limits_{i=0}^{l} \delta(t_i,t_v) \frac{f(s_u|t_v) }{\sum\limits_{i=0}^{l}f(s_u|t_i)}
\label{eq:5-39}
\end{eqnarray}
\parinterval 可以看出，这不是一个计算$f(s_u|t_v)$的解析式，因为等式右端仍含有$f(s_u|t_v)$。不过它蕴含着一种非常经典的方法\ $\dash$\ {\small\sffamily\bfseries{期望最大化}}\index{期望最大化}（Expectation Maximization）\index{Expectation Maximization}方法，简称EM方法（或算法）。使用EM方法可以利用上式迭代地计算$f(s_u|t_v)$，使其最终收敛到最优值。EM方法的思想是：用当前的参数，求似然函数的期望，之后最大化这个期望同时得到新的一组参数的值。对于IBM模型来说，其迭代过程就是反复使用公式\eqref{eq:5-39}，具体如图\ref{fig:5-24}所示。
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-ibm-model-iteration-process-diagram}
\caption{IBM模型迭代过程示意图}
\label{fig:5-24}
\end{figure}
%----------------------------------------------
\parinterval 为了化简$f(s_u|t_v)$的计算，在此对公式\eqref{eq:5-39}进行了重新组织，见图\ref{fig:5-25}。其中，红色部分表示翻译概率P$(\seq{s}|\seq{t})$；蓝色部分表示$(s_u,t_v)$ 在句对$(\seq{s},\seq{t})$中配对的总次数，即“$t_v$翻译为$s_u$”在所有对齐中出现的次数；绿色部分表示$f(s_u|t_v)$对于所有的$t_i$的相对值，即“$t_v$翻译为$s_u$”在所有对齐中出现的相对概率；蓝色与绿色部分相乘表示“$t_v$翻译为$s_u$”这个事件出现次数的期望的估计，称之为{\small\sffamily\bfseries{期望频次}}\index{期望频次}（Expected Count）\index{Expected Count}。
\vspace{-0.3em}
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-a-more-detailed-explanation-of-formula-3.40}
\caption{公式\eqref{eq:5-39}的解释}
\label{fig:5-25}
\end{figure}
%----------------------------------------------
\parinterval 期望频次是事件在其分布下出现次数的期望。另$c_{\mathbb{E}}(X)$为事件$X$的期望频次，其计算公式为：
\begin{equation}
c_{\mathbb{E}}(X)=\sum_i c(x_i) \cdot \funp{P}(x_i)
\end{equation}
\noindent 其中$c(x_i)$表示$X$取$x_i$时出现的次数，$\funp{P}(x_i)$表示$X=x_i$出现的概率。图\ref{fig:5-26}展示了事件$X$的期望频次的详细计算过程。其中$x_1$、$x_2$和$x_3$分别表示事件$X$出现2次、1次和5次的情况。
%----------------------------------------------
\begin{figure}[htp]
\centering
\subfigure{\input{./Chapter5/Figures/figure-calculation-of-the-expected-frequency-1}}
\subfigure{\input{./Chapter5/Figures/figure-calculation-of-the-expected-frequency-2}}
\caption{总频次（左）和期望频次（右）的实例}
\label{fig:5-26}
\end{figure}
%----------------------------------------------
\parinterval 因为在$\funp{P}(\seq{s}|\seq{t})$中，$t_v$翻译（连接）到$s_u$的期望频次为：
\begin{eqnarray}
c_{\mathbb{E}}(s_u|t_v;\seq{s},\seq{t}) \equiv \sum\limits_{j=1}^{m} \delta(s_j,s_u) \cdot \sum\limits_{i=0}^{l} \delta(t_i,t_v) \cdot \frac {f(s_u|t_v)}{\sum\limits_{i=0}^{l}f(s_u|t_i)}
\label{eq:5-40}
\end{eqnarray}
\parinterval 所以公式\ref {eq:5-39}可重写为：
\begin{eqnarray}
f(s_u|t_v)=\lambda_{t_v}^{-1} \cdot \funp{P}(\seq{s}| \seq{t}) \cdot c_{\mathbb{E}}(s_u|t_v;\seq{s},\seq{t})
\label{eq:5-41}
\end{eqnarray}
\parinterval 在此如果令$\lambda_{t_v}^{'}=\frac{\lambda_{t_v}}{\funp{P}(\seq{s}| \seq{t})}$，可得：
\begin{eqnarray}
f(s_u|t_v) &= &\lambda_{t_v}^{-1} \cdot \funp{P}(\seq{s}| \seq{t}) \cdot c_{\mathbb{E}}(s_u|t_v;\seq{s},\seq{t}) \nonumber \\
&=&{(\lambda_{t_v}^{'})}^{-1} \cdot c_{\mathbb{E}}(s_u|t_v;\seq{s},\seq{t})
\label{eq:5-42}
\end{eqnarray}
\parinterval 又因为IBM模型对$f(\cdot|\cdot)$的约束如下：
\begin{eqnarray}
\forall t_y : \sum\limits_{s_x} f(s_x|t_y) =1
\label{eq:5-43}
\end{eqnarray}
\parinterval 为了满足$f(\cdot|\cdot)$的概率归一化约束，易知$\lambda_{t_v}^{'}$为：
\begin{eqnarray}
\lambda_{t_v}^{'}=\sum\limits_{s_u} c_{\mathbb{E}}(s_u|t_v;\seq{s},\seq{t})
\label{eq:5-44}
\end{eqnarray}
\parinterval 因此，$f(s_u|t_v)$的计算式可再一步变换成下式：
\begin{eqnarray}
f(s_u|t_v)=\frac{c_{\mathbb{E}}(s_u|t_v;\seq{s},\seq{t})} { \sum\limits_{s_u} c_{\mathbb{E}}(s_u|t_v;\seq{s},\seq{t}) }
\label{eq:5-45}
\end{eqnarray}
\parinterval 进一步，假设有$K$个互译的句对（称作平行语料）：
$\{(\seq{s}^{[1]},\seq{t}^{[1]}),...,(\seq{s}^{[K]},\seq{t}^{[K]})\}$，$f(s_u|t_v)$的期望频次为：
\begin{eqnarray}
c_{\mathbb{E}}(s_u|t_v)=\sum\limits_{k=1}^{K} c_{\mathbb{E}}(s_u|t_v;s^{[k]},t^{[k]})
\label{eq:5-46}
\end{eqnarray}
\parinterval 于是有$f(s_u|t_v)$的计算公式和迭代过程图\ref{fig:5-27}所示。完整的EM算法如图\ref{fig:5-28}所示。其中E-Step对应4-5行，目的是计算$c_{\mathbb{E}}(\cdot)$；M-Step对应6-9行，目的是计算$f(\cdot|\cdot)$。
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-calculation-formula&iterative-process-of-function}
\caption{$f(s_u|t_v)$的计算公式和迭代过程}
\label{fig:5-27}
\end{figure}
%----------------------------------------------
%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter5/Figures/figure-em-algorithm-flow-chart}
\caption{EM算法流程图（IBM模型1）}
\label{fig:5-28}
\end{figure}
%----------------------------------------------
\parinterval 至此，本章完成了对IBM模型1训练方法的介绍。其可以通过图\ref{fig:5-27}所示的算法进行实现。算法最终的形式并不复杂，因为只需要遍历每个句对，之后计算$f(\cdot|\cdot)$的期望频次，最后估计新的$f(\cdot|\cdot)$，这个过程迭代直至$f(\cdot|\cdot)$收敛至稳定状态。
\vspace{-1.5em}
%----------------------------------------------------------------------------------------
% NEW SECTION
%----------------------------------------------------------------------------------------
\sectionnewpage
\section{小结及拓展阅读}
\parinterval 本章对IBM系列模型中的IBM模型1进行了详细的介绍和讨论，从一个简单的基于单词的翻译模型开始，本章从建模、解码、训练多个维度对统计机器翻译进行了描述，期间涉及了词对齐、优化等多个重要概念。IBM模型共分为5个模型，对翻译问题的建模依次由浅入深，同时模型复杂度也依次增加，我们将在{\chaptersix}对IBM模型2-5进行详细的介绍和讨论。IBM模型作为入门统计机器翻译的“必经之路”，其思想对今天的机器翻译仍然产生着影响。虽然单独使用IBM模型进行机器翻译现在已经不多见，甚至很多从事神经机器翻译等前沿研究的人对IBM模型已经逐渐淡忘，但是不能否认IBM模型标志着一个时代的开始。从某种意义上讲，当使用公式$\hat{\seq{t}} = \argmax_{\seq{t}} \funp{P}(\seq{t}|\seq{s})$描述机器翻译问题的时候，或多或少都在使用与IBM模型相似的思想。
\parinterval 当然，本书也无法涵盖IBM模型的所有内涵，很多内容需要感兴趣的读者继续研究和挖掘。其中最值得关注的是统计词对齐问题。由于词对齐是IBM模型训练的间接产物，因此IBM模型成为了自动词对齐的重要方法。比如IBM模型训练装置GIZA++更多的是被用于自动词对齐任务，而非简单的训练IBM模型参数\upcite{och2003systematic}。
\begin{itemize}
\vspace{0.5em}
\item 在IBM基础模型之上，有很多改进的工作。例如，对空对齐、低频词进行额外处理\upcite{DBLP:conf/acl/Moore04}；考虑源语言-目标语言和目标语言-源语言双向词对齐进行更好地词对齐对称化\upcite{肖桐1991面向统计机器翻译的重对齐方法研究}；使用词典、命名实体等多种信息对模型进行改进\upcite{2005Improvin}；通过引入短语增强IBM基础模型\upcite{1998Grammar}；引入相邻单词对齐之间的依赖关系增加模型鲁棒性\upcite{DBLP:conf/acl-vlc/DaganCG93}等；也可以对IBM模型的正向和反向结果进行对称化处理，以得到更加准确词对齐结果\upcite{och2003systematic}。
\item 随着词对齐概念的不断深入，也有很多词对齐方面的工作并不依赖IBM模型。比如，可以直接使用判别式模型利用分类器解决词对齐问题\upcite{ittycheriah2005maximum}；使用带参数控制的动态规划方法来提高词对齐准确率\upcite{DBLP:conf/naacl/GaleC91}；甚至可以把对齐的思想用于短语和句法结构的双语对应\upcite{xiao2013unsupervised}；无监督的对称词对齐方法，正向和反向模型联合训练，结合数据的相似性\upcite{DBLP:conf/naacl/LiangTK06}；除了GIZA++，研究人员也开发了很多优秀的自动对齐工具，比如，FastAlign\upcite{DBLP:conf/naacl/DyerCS13}、Berkeley Word Aligner\upcite{taskar2005a}等，这些工具现在也有很广泛的应用。
\vspace{0.5em}
\item 一种较为通用的词对齐评价标准是{\bfnew{对齐错误率}}（Alignment Error Rate, AER）\upcite{DBLP:journals/coling/FraserM07}。在此基础之上也可以对词对齐评价方法进行改进，以提高对齐质量与机器翻译评价得分BLEU的相关性\upcite{DBLP:conf/acl/DeNeroK07,paul2007all,黄书剑2009一种错误敏感的词对齐评价方法}。也有工作通过统计机器翻译系统性能的提升来评价对齐质量\upcite{DBLP:journals/coling/FraserM07}。不过，在相当长的时间内，词对齐质量对机器翻译系统的影响究竟如何并没有统一的结论。有些时候，词对齐的错误率下降了，但是机器翻译系统的译文品质没有带来性能提升。但是，这个问题比较复杂，需要进一步的论证。不过，可以肯定的是，词对齐可以帮助人们分析机器翻译的行为。甚至在最新的神经机器翻译中，如何在神经网络模型中寻求两种语言单词之间的对应关系也是对模型进行解释的有效手段之一\upcite{DBLP:journals/corr/FengLLZ16}。
\vspace{0.5em}
\item 基于单词的翻译模型的解码问题也是早期研究者所关注的。比较经典的方法的是贪婪方法\upcite{germann2003greedy}。也有研究者对不同的解码方法进行了对比\upcite{germann2001fast}，并给出了一些加速解码的思路。随后，也有工作进一步对这些方法进行改进\upcite{DBLP:conf/coling/UdupaFM04,DBLP:conf/naacl/RiedelC09}。实际上，基于单词的模型的解码是一个NP完全问题\upcite{knight1999decoding}，这也是为什么机器翻译的解码十分困难的原因。关于翻译模型解码算法的时间复杂度也有很多讨论\upcite{DBLP:conf/eacl/UdupaM06,DBLP:conf/emnlp/LeuschMN08,DBLP:journals/mt/FlemingKN15}。
\end{itemize}