Chapter3.tex

%----------------------------------------------------------------------------------------
%	CHAPTER 3
%----------------------------------------------------------------------------------------
\renewcommand\figurename{图}%将figure改为图
\renewcommand\tablename{表}%将figure改为图
\definecolor{ublue}{rgb}{0.152,0.250,0.545}
\definecolor{ugreen}{rgb}{0,0.5,0}
\chapterimage{chapter_head_1} % Chapter heading image
%公式1.7之后往后串一个
\chapter{基于词的翻译模型}
\hspace{2em}统计机器翻译和神经机器翻译在当前具有统治性意义。这两种方法各有优缺点，并没有哪种方法具有绝对的优势。但从研究的角度来看，神经机器翻译整体上更具有前沿性。本章主要介绍了统计机器翻译的开山之作—IBM模型，它主要讲了怎么使用词汇对机器翻译进行建模。IBM模型由Peter E. Brown等人在1993年提出，并详细阐述于论文—《The Mathematics of Statistical Machine Translation: Parameter Estimation》。这篇文章的视野和对问题的定义远超当时人所能看到的东西，其衍生出来的一系列方法和新的问题还被后人花费将近10年的时间来进行研究与讨论。
\section{什么是基于词的翻译模型}\index{Chapter3.1}%Index的作用，目前不清晰
\hspace{2em}在机器翻译中，我们希望得到一个源语句到目标语译文的翻译。但机器并不知道如何翻译。因此在做机器翻译的过程中，最初面临的一个问题是：如何对翻译进行建模？从计算机的角度看，建模的目的就是把抽象的问题转换为可计算的问题。所以机器翻译的一个核心问题是：如何将翻译转换为一个可计算的模型或过程。

\noindent\hspace{2em}基于单词的统计机器翻译模型又是如何描述翻译的呢？IBM模型提出了一个观点：在翻译源语句时，通常是把每个源语句的单词翻译成对应的目标语单词，然后调整这些单词的顺序，最后得到翻译结果。尽管在人看来基于单词的对应进行翻译是很自然的事，但是机器并不一定。

\noindent\hspace{2em}举个例子说明如何基于单词的对应进行翻译。如图 \ref{figureC3.1}所示，表示的是汉译英的例子。其中源语句是“我 对 你 感到 满意”。首先我们把源语句的单词“我”、“对”、\\“你”、“感到”和“满意”分别翻译为“I”、“with”、“you”、“am”和“satisfied”，然后调整单词的顺序，比如“am”放在译文的第2个位置，“you”应该放在最后的位置等，最后得到译文“I am satisfied with you”。
%空一行用来段落换行，noindent取消首行缩进，hspace{}指定缩进距离，1em等于两个英文字符|一个汉字
%----------------------------------------------
% 图3.1

\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure31}
    \caption{此处为图片的描述...例：基于词对应进行翻译.}
    \label{figureC3.1}
\end{figure}
%-------------------------------------------

\noindent\hspace{2em}传统观点认为基于词的翻译过程包含如下三个步骤。如图 \ref{figureC3.2}所示。

\noindent\hspace{2em}第一、分析。将源语句或目标语句切分或者表示为能够处理的最小单元的过程。在基于词的翻译模型的最小处理单元就是单词。在这里也可以简单地将分析理解为分词。

\noindent\hspace{2em}第二、转换。把源语句中的每个单词都翻译成目标语单词。

\noindent\hspace{2em}第三、生成。基于转换的结果，将目标语译文变成通顺且合乎语法的句子。


%----------------------------------------------
% 图3.2
\begin{figure}[htp]
 \centering
\input{./Chapter3/Figures/figure32}
    \caption{此处为图片的描述...例：基于词的翻译过程.}
    \label{figureC3.2}
\end{figure}
%---------------------------
\noindent\hspace{2em}从现在的角度看，分析、转换和生成依然是非常深刻的一个观点。该过程蕴含于很多的任务，比如句法分析。即使对于神经机器翻译，从大的框架来说，依然在做分析、转换和生成，只不过有些过程隐含在神经网络的设计中。
\section{构建一个简易机器翻译系统}\index{Chapter3.2}%Index的作用，目前不清晰

\noindent\hspace{2em}本节首先对比人工翻译流程和机器翻译流程的异同点，从中我们可以归纳出构建机器翻译系统的两个主要流程：训练和解码。其次从单词翻译概率、句子级翻译模型和解码三个方面描述如何构建一个简易机器翻译系统。其中单词翻译概率和句子级翻译模型属于训练流程。
\subsection{机器翻译的思路}\index{Chapter3.2.1}
\textbf{人工翻译流程}\index{Chapter3.2.1.1}

\noindent\hspace{2em}当我们翻译一个句子时，首先会快速地分析出句子中词的构成，然后基于以往的知识，得到每个词的候选翻译，最后利用对单词的理解拼出来一个译文。这描述了人在翻译时的基本过程。尽管并不是严格的从心理学或者脑科学得出来的观点，但至少可以帮助我们理解人的翻译。
%----------------------------------------------
% 图3.3
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure33}
    \caption{此处为图片的描述...例：人工翻译的过程}
    \label{figureC3.3}
\end{figure}
%---------------------------

\noindent\hspace{2em}如图\ref{figureC3.3}所示，表示的是人工翻译的过程。其中待翻译的句子是“我 对 你表示 满意”，它的一个可能译文是“I’m satisfied with you”。我们可以把上述过程总结为如下两个过程。

\noindent\hspace{2em}第一、学习单词的翻译。即获取待翻译句子的每个单词的候选翻译。比如“对”的可能译文有“to”、“with”和“for”等。对于人来说，可以通过阅读、背诵、做题或者老师教等途径获得，并在大脑中形成知识。这些知识就包含了源语词与目标语词对应关系。我们也把这个过程称之为学习过程。

\noindent\hspace{2em}第二、运用知识生成译文。当翻译一个课本上没有见过的句子时，我们可能会想到词之间的翻译关系、一些常见的单词搭配、主谓宾等语法知识等，比如“satisfied”后面常使用介词“with”来表示对人的满意等，并基于这些知识快速地对译文进行生成。

\noindent\textbf{机器翻译流程}\index{Chapter3.2.1.2}

\noindent\hspace{2em}那么机器是如何完成翻译的呢？机器翻译可能没有人那么智能。因为一方面没有老师教给它一些非常好用的规则，使它能够快速得到译文。另一方面机器很笨，尽管它能知道每个单词的译文，但是不知道这些译文怎么拼装成句，甚至不知道哪些译文是对的。为了更加直观地理解机器在翻译时的困境，我们将其中需要解决的问题归纳如下。

\noindent\hspace{2em}问题一、如何将单词的译文拼装成句？

\noindent\hspace{2em}问题二、如果可以将译文成句，那如何判断结果的好坏？

\noindent\hspace{2em}对于问题一。机器最擅长的就是计算，它可以类似于走一条路径，尝试把译文拼装成句。如图\ref{figureC3.4}中蓝色和红色的线，表示的就是两条译文选择路径，区别在于“满意”和“对”的翻译候选是不一样的，蓝色线选择的是“satisfy”和“to”，而红色线是“satisfied”和“with”。换句话说，翻译就是一条译文选择路径，不同的译文对应不同的路径，并且词序也可以不同。机器可以利用它的计算能力找到很多这样的路径。
%----------------------------------------------
% 图3.4
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure34}
    \caption{此处为图片的描述...例：机器翻译的流程（1）}
    \label{figureC3.4}
\end{figure}
%---------------------------

\noindent\hspace{2em}对于问题二。尽管机器能够找到很多这样的译文选择路径，但它并不知道那些路径是好的。因此机器还需要运用它的知识判断哪个结果是好的。机器没有人脑这样复杂的神经元结构，那它知识又该怎么表示呢？如图\ref{figureC3.4}所示，其中的数字表示的是概率，它们就是机器对每个局部翻译或翻译路径的描述。换句话说，机器用概率化的模型描述了每个翻译候选的可能性。基于每个候选翻译的可能性，机器可以对所有的译文选择路径进行打分，图\ref{figureC3.4}中第一条翻译路径的分数为0.042，第二条是0.006,...,以此类推。最后机器可以选择分数最高的路径作为源语句的最终译文。
\textbf{人工 vs. 机器}\index{Chapter3.2.1.3}

\noindent\hspace{2em}人在翻译时的决策和推断是非常确定并且快速的，但机器却充满了不确定性和概率化的思想。当然它们也有类似的地方。机器学习概率的过程相当于人学习知识的过程，而寻找路径以及给它们打分相当于人应用知识的过程。在统计机器翻译中，我们称前者是训练，目的是从双语平行数据中自动学习翻译知识。后者是解码或推断，目的是使用学习的知识对未知的句子进行翻译。这就是当前机器实现翻译的两个角度：训练和解码。

\noindent\hspace{2em}实际上，上述机器翻译的过程可以总结为三个方面。第一、建模，基于词的思想去构建翻译模型。第二、训练，有了这个思想如何学习这个模型。第三、解码，应用训练好的模型对新的句子进行翻译。
%----------------------------------------------
% 图3.5
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure35}
    \caption{此处为图片的描述...例：机器翻译的流程（2）}
    \label{figureC3.5}
\end{figure}
%---------------------------
\subsection{简单的建模}\index{Chapter3.2.2}

\noindent\hspace{2em}下面我们将介绍如何构建一个简易的基于词的机器翻译系统。本小节首先进行简单的建模。如图\ref{figureC3.6}所示，表示的是基于数据驱动的方法的框架，它主要包括两个步骤。

\noindent\hspace{2em}第一、模型学习。从双语平行数据中学习模型，这个模型称为$\textrm{P}(t|s)$。其中$s$表示源语言，$t$表示目标语，它表示给定源语句的条件下，翻译为目标语句子的概率。总而言之，这一步我们需要从大量的双语平行数据中求解$\textrm{P}(t|s)$。

\noindent\hspace{2em}第二、解码。当面对一个新的句子时，我们需要使用学习得到的模型进行推断。推断的方式可描述为穷举和计算，换句话说，我们尽可能的枚举更多的翻译结果，然后对每个翻译结果进行打分，最后选择得分最高的翻译结果。
%----------------------------------------------
% 图3.6
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure36}
    \caption{此处为图片的描述...例：基于数据驱动的方法的框架}
    \label{figureC3.6}
\end{figure}
%---------------------------

\noindent\hspace{2em}接下来，我们将介绍这个简易机器翻译系统的模型学习和解码的过程。在模型学习中，我们分两小节进行描述，即单词翻译概率和句子级翻译模型，它们属于递进的关系。换言之，句子级翻译概率模型是建立在单词翻译概率之上。
\subsection{单词翻译概率}\index{Chapter3.2.3}\label{chapter3.2.3}
\textbf{什么是单词翻译概率？}\index{Chapter3.2.3.1}

\noindent\hspace{2em}单词翻译概率主要解决的是翻译时的“择词”问题，即选择什么样的目标语单词作为候选译文。当人在翻译某个单词时，可以利用积累的知识，快速地得到它的候选译文。举个汉译英的例子，当翻译“我”这个单词时，可能会想到用“I”、“me”或“I’m”作为它的译文，而几乎不会选择“you”、“satisfied”等含义相差太远的目标语单词。这是为什么呢？如果从概率的角度来分析这个问题，无论是我们的课本还是其他学习材料，绝大部分情况下“我”都翻译成了“I”、“me”等，几乎没有看到翻译成“you”或“satisfied”等的情况。换句话说，“我”翻译成“I”、“me”等属于高频事件，而翻译成“you”、“satisfied”等属于低频或小概率事件，它们在整个语料中出现的概率是不一样的。因此人在翻译时也是选择概率更大的目标语单词作为候选译文。

\noindent\hspace{2em}如何用概率化模型描述上述思想呢？下面我们先介绍如何从一个双语平行数据中估计或者学习单词翻译概率，再介绍如何从大量的双语平行数据中学习更准确的单词翻译概率。

\noindent\textbf{如何从一个双语平行数据中学习？}\index{Chapter3.2.3.2}

\noindent\hspace{2em}在上一节的骰子游戏中，我们重复地掷骰子很多次，然后计算“1”到“6”各出现的次数，再除以掷的总次数，最后得到它们出现的近似概率。我们同样用类似的方式估计单词翻译概率。假设$x$表示任意源语单词，所有的目标语单词$y \in Y$都可能是它的译文。当给定一个互译的句对$(s,t)$，我们定义$\textrm{P}(x \leftrightarrow y; s, t)$表示在$(s,t)$中$x$和$y$互译的可能性或概率。其中$x$属于句子$s$中的词，而$y$属于$t$中的词，具体计算如公式\ref{eqC3.1}所示。
\begin{equation}
\textrm{P}(x \leftrightarrow y; s,t) \equiv \textrm{P}(x,y;s,t) = \frac{c(x,y;s,t)}{\sum_{x',y'} c(x',y';s,t)}
\label{eqC3.1}
\end{equation}

\noindent\hspace{2em}上式中分子$c(x,y;s,t)$表示$x$和$y$在句对$(s,t)$中共现的总次数,分母$\sum_{x',y'} c(x',y';$ $s,t)$表示任意的$x'$和任意的$y'$在$(s,t)$共现的总次数。为了更加清晰的理解如何计算$c(x,y;s,t)$，我们用图\ref{figureC3.7}描述的算法进行了说明。由图可得，计算$c(x,y;s,t)$的过程主要是两层\textbf{for}循环，外层的\textbf{for}循环用于遍历$s$中的词，内层的\textbf{for}循环用于遍历$t$中的词，当$s$中的词等于$x$且$t$中的词等于$y$时，count加1，最后count的值就是$x$和$y$的总共现次数。
%----------------------------------------------
% 图3.7
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure37}
    \caption{此处为图片的描述...单词x和y在句对(s, t)中的共现总次数的算法}
    \label{figureC3.7}
\end{figure}
%---------------------------

\noindent\hspace{2em}举个例子，如果互译的句对$(s,t)$分别如图\ref{figureC3.8}所示，$x$和$y$分别是“翻译”和“transl-\\ation”，那么它们的单词翻译概率是多少呢？
%----------------------------------------------
% 图3.8
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure38}
    \caption{此处为图片的描述...一个互译的句对}
    \label{figureC3.8}
\end{figure}
%---------------------------

\noindent\hspace{2em}在上述例子中，”翻译”和”translation”分别在$s$和$t$中出现了2次，因此$c('\text{翻译}',$\\$'\text{translation}';s,t)$等于4。而对于$\sum_{x',y'} c(x',y';s,t)$，因为$x'$和$y'$分别是$s$和$t$的任意的词，所以等于$s$的词数乘以$t$的词数。最后“翻译”和“translation”的单词翻译概率如式\ref{eqC3.2}所示。
\begin{equation}
\textrm{P}('\text{翻译}','translation'; s,t)  = \frac{c(x,y;s,t)}{\sum_{x',y'} c(x',y';s,t)} = \frac{4}{|s|\times |t|} = \frac{4}{63}
\label{eqC3.2}
\end{equation}

\noindent\hspace{2em}公式\ref{eqC3.2}中运算$|\bullet|$表示计算句长。类似的可以得到“机器”和“translation”、“机器”和“look”的单词翻译概率，如式\ref{eqC3.3}和\ref{eqC3.4}所示。
\begin{equation}
\textrm{P}('\text{机器}','translation'; s,t)  = \frac{2}{63}
\label{eqC3.3}
\end{equation}
\begin{equation}
\textrm{P}('\text{机器}','look'; s,t)  =  \frac{0}{63}
\label{eqC3.4}
\end{equation}
\textbf{如何从大量的双语平行数据中学习？}\index{Chapter3.2.3.3}

\noindent\hspace{2em}在很多时候，我们有多个互译句对$(s^1,t^1),...,(s^n,t^n)$。如果能从更多的数据中进行统计，那么单词翻译概率也会更加的准确。当我们从大规模的双语平行数据中计算单词翻译概率时，其可定义为公式\ref{eqC3.5}。与公式\ref{eqC3.1}相比，分子分母都多了一项累加符号$\sum_{i-1}^{n}\bullet$，它表示遍历语料库中所有的句对，其中$n$表示语料库中句对的数量。换句话说，当我们计算词的共现次数时，需要对每个句对上的结果进行累加。
\begin{equation}
\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';x^i,y^i)}}}
\label{eqC3.5}
\end{equation}

\noindent\hspace{2em}举个例子。如图\ref{figureC3.9}所示，表示的是两个双语句对。我们使用$s^1$和$s^2$分别表示第一个句对和第二个句对的源语句，$t^1$和$t^2$表示目标语句。
%----------------------------------------------
% 图3.9
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure39}
    \caption{此处为图片的描述...多个互译的句对}
    \label{figureC3.9}
\end{figure}
%---------------------------

\noindent\hspace{2em}如公式\ref{eqC3.6}所示，表示的是词对“翻译”和“translation”基于上述双语句对计算得到的单词翻译概率。分子是两个句对的“翻译”和“translation”共现次数的累计，分母是两个句对的源语词和目标语词的组合数的累加。
{\footnotesize
\begin{equation}
\begin{split}
{\textrm{P}(\textrm{'翻译'},\textrm{'translation'})}&={\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})}}\\
&={{\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}}}
\label{eqC3.6}
\end{split}
\end{equation}
}
\subsection{句子级翻译模型}\index{Chapter3.2.4}

\noindent\hspace{2em}本节介绍如何获取句子级翻译概率。如图\ref{figureC3.10}所示，我们用条件概率$\textrm{P}(t|s)$表示句子级翻译模型，它表示给定源语句$s$时，目标语句$t$的概率或者可能性。下面展开详细的描述。
%----------------------------------------------
% 图3.10
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure310}
    \caption{此处为图片的描述...句子级翻译模型就是翻译模型$\textrm{P}(t|s)$}
    \label{figureC3.10}
\end{figure}
%---------------------------

\noindent\textbf{初级句子级翻译模型}\index{Chapter3.2.4.1}

\noindent\hspace{2em}直接定义句子级翻译概率并不容易。一个退而求其次的方法是：找到一个函数$g(s,t)$来衡量翻译结果的质量。它描述了这样一个事：当翻译结果$t$的质量越好，则它的值越大；当$t$的翻译质量越差，则它的值越小。换句话说，$g(s,t)$的单调性和翻译质量呈正相关。假如我们已经找到了一个这样的函数$g(s,t)$，就能够间接地定义句子级翻译概率，如公式\ref{eqC3.7}所示。
\begin{equation}
\textrm{P}(t|s)  =  \frac{g(s,t)}{\sum_{t}g(s,t)}
\label{eqC3.7}
\end{equation}

\noindent\hspace{2em}公式\ref{eqC3.7}相当于在函数$g$上做了归一化，使其具有概率的意义。具体来说，我们枚举了源语句$s$的所有翻译结果$t$,并把所有$t$对应的函数$g$的计算结果相加作为分母，而分子是某个翻译结果$t$的函数$g$的值。

\noindent\hspace{2em}上述过程初步建立了句子级翻译模型，但发现一些问题不好解决。我们主要面临两个问题，第一、函数$g(s,t)$怎么定义。即给定单词翻译概率，如何求句子级互译概率。第二、公式\ref{eqC3.7}中分母的计算需要累加所有翻译结果$t$的函数$g$的计算结果，但求解所有$t$几乎是不可能。实际上最核心的问题还是函数$g(s,t)$的定义或计算。而第二个问题其实不需要解决，这是因为我们通常只关注于可能性最大的翻译结果，即$g(s,t)$的计算结果最大时对应译文。

\noindent\hspace{2em}因此如何定义$g(s,t)$成为关键。换句话说，如何表示两个词串之间的对应关系呢？这里我们使用的一个基础思想是大题小做。具体来说，直接表示句子之间的对应太困难了，但可以利用词之间的对应来描述句子之间的对应。这里就用到了上一小节的单词翻译概率。

\noindent\hspace{2em}我们首先引入一个非常重要的概率—词对齐，它是统计机器翻译中最基本的概念之一。词对齐描述了句子间的对应，它指出本质上句子之间的对应是由词之间的对应表示的。如图\ref{figureC3.11}所示，$s$和$t$分别表源语句和目标语句，单词的右下标表示的是该词在句中的位置，而虚线描述的是句子$s$和$t$中的词对齐关系。比如“满意”的右下表“5”表示该词在句子$s$中处于第5个位置，“satisfied”的右下表“3”表示在句子$t$中处于第3个位置，并且“满意”和“satisfied”用虚线连接来表示对应。为方便描述，我们用二元组$(j,i)$来描述词对齐，它表示源语句第$j$个单词对应目标语句第$i$个单词，即单词$s_j$和$t_i$对应。图\ref{figureC3.11}中共有5条虚线，表示有5组单词之间的对应。我们把它们构成集合称为$A$，并按如下方式记录下所有的对齐链接，即$A={(1,1),(2,4),(3,5),(4,2)(5,3)}$。
%----------------------------------------------
% 图3.11
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure311}
    \caption{此处为图片的描述...蓝色的虚线表示的是对齐关系（词对齐）}
    \label{figureC3.11}
\end{figure}
%---------------------------

\noindent\hspace{2em}当给定一个源语和目标语的句对$(s,t)$，以及它们的最优词对齐$\widehat{A}$,可以使用单词翻译概率计算$g(s,t)$,如公式\ref{eqC3.8}所示。其中$g(s,t)$被定义为句子$s$中的单词和句子$t$中的单词的翻译概率的乘积，并且这两个单词必须对齐或具有对齐链接。$\textrm{P}(s_j,t_i)$表示具有对齐链接的源语词$s_j$和目标语词$t_i$的单词翻译概率。
\begin{equation}
g(s,t) = \prod_{(j,i)\in \widehat{A}}\textrm{P}(s_j,t_i)
\label{eqC3.8}
\end{equation}

\noindent\hspace{2em}用图\ref{figureC3.11}表示的句对$(s,t)$进行举例。其中“我”与“I”、“对”与“with”、“你”与“you”\\等相互对应，它们的翻译概率相乘就是$g(s,t)$的计算结果。如公式\ref{eqC3.9}所示。显然如果每个单词的翻译概率都高，那么整句的模型得分也高。
\begin{equation}
\begin{split}
{g(s,t)}&={ \textrm{P}(\textrm{'我','I'}) \times \textrm{P}(\textrm{'对','with'}) \times \textrm{P}(\textrm{'你','you'}) \times}\\
&{\textrm{P}(\textrm{'感到','am'}) \times \textrm{P}(\textrm{'满意','satisfied'})}
\label{eqC3.9}
\end{split}
\end{equation}
\textbf{语言模型加强的句子翻译概率}\index{Chapter3.2.4.2}

\noindent\hspace{2em}公式\ref{eqC3.8}定义的$g(s,t)$存在的问题是没有考虑词序信息。我们用一个简单的例子说明这个问题。如图\ref{figureC3.12}所示，表示源语句“我 对 你 感到 满意”的两个翻译结果，第一个翻译结果是“I am satisfied with you”，第二个是“I with you am satisfied”。虽然它们选择的目标语单词是一样的，但词序存在很大差异。比如它们都选择“satisfied”作为源语单词“满意”的译文，但是在第一个翻译结果中处于第3个位置，而第二个中处于最后的位置。显然第一个翻译结果更符合英文的表达习惯，翻译的质量更高。但是当用公式\ref{eqC3.8}计算得到的函数$g$的值却是一样的。
%----------------------------------------------
% 图3.12
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure312}
    \caption{此处为图片的描述...蓝色的虚线表示的是对齐关系（词对齐）}
    \label{figureC3.12}
\end{figure}
%---------------------------

\noindent\hspace{2em}如何在$g(s,t)$引入词序信息呢？我们希望函数$g(s,t)$对符合自然语言表达习惯的翻译结果给更高的分数，对于不合符的或不通顺的句子给更低的分数。因此我们引入一种常用于衡量句子流畅度的方法—$n$元文法(n-gram)语言模型。

\noindent\hspace{2em}$n$元文法语言模型是统计机器翻译中非常重要的特征。它用概率化模型描述了句子的流畅度。概率越高表示句子的流畅度越高，越贴近于人的表达习惯。概率越低表示句子越不符合人的表达。一个常用的$n$元文法(unigram)语言模型的定义见公式\ref{eqC3.10}。$\textrm{P}_{lm}(t)$表示语言模型给句子$t$的打分，其中$t$依次由单词$t_1t_2...t_m$组成。具体而言，$\textrm{P}_{lm}(t)$被定义为$\textrm{P}(t_i|t_{i-1})(i=1,2,...,m)$的连乘，其中$\textrm{P}(t_i|t_{i-1})(i=1,2,...,m)$表示当前一个单词是$t_{i-1}$时，当前单词是$t_i$的概率。
\begin{equation}
\textrm{P}_{lm}(t)=\textrm{P}_{lm}(t_1...t_m)=\textrm{P}(t_1)\times \textrm{P}(t_2|t_1)\times \textrm{P}(t_3|t_2)\times ... \times \textrm{P}(t_m|t_{m-1})
\label{eqC3.10}
\end{equation}

\noindent\hspace{2em}概率$\textrm{P}(t_i|t_{i-1})(i=1,2,...,m)$也是从大规模的单语数据中统计得到的，它的计算如公式\ref{eqC3.11}所示。其中$c(t_i,t_{i-1})$表示单词$t_{i-1}$和$t_i$在单语语料中依次连续出现的次数，而$c(t',t_{i-1})$表示$t_{i-1}$和任意单词$t'$在语料中依次连续出现的次数，它们相除就表示$\textrm{P}(t_i|t_{i-1})$。
\begin{equation}
\textrm{P}(t_i|t_{i-1})=\frac{c(t_i|t_{i-1})}{c(t'|t_{i-1})}
\label{eqC3.11}
\end{equation}

\noindent\hspace{2em}举个例子说明。如图\ref{figureC3.13}所示，表示的是4个英文句子$t^1\textrm{、}t^2\textrm{、}t^3$和$t^4$。其中<s>\\和</s>也是单词，用于标识句子的开头和结尾。我们将从这4个句子中估计 ，即“machine”后面是“translation”的概率。
%----------------------------------------------
% 图3.13
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure313}
    \caption{此处为图片的描述...}
    \label{figureC3.13}
\end{figure}
%---------------------------

\noindent\hspace{2em}如公式\ref{eqC3.12}所示。分母是“machine”后面跟任意单词的次数，在4个句子中各出现一个。分子是“machine”后面跟“translation”的次数，仅在第一个句子中出现一次。因此$\textrm{P}('translation'|'machine')$等于$1/4$。当单语语料的规模更大时，我们得到的计算结果将越来越准确。
\begin{equation}
\textrm{P}('translation'|'machine')=\frac{1}{1+1+1+1}=\frac{1}{4}
\label{eqC3.12}
\end{equation}

\noindent\hspace{2em}语言模型$\textrm{P}_{lm}{(t)}$概率化地描述了目标语句的流畅度，这里将不再对语言模型做过多的介绍，而将重点放在句子级翻译模型的构建。

\noindent\hspace{2em}如果我们将语言模型$\textrm{P}_{lm}{(t)}$和公式\ref{eqC3.8}表示$g(s,t)$相乘，就得到了一个考虑词序信息的$g(s,t)$。如公式\ref{eqC3.13}所示。但这样做能否筛选出词序正确的翻译结果呢？

\begin{equation}
g(s,t) \equiv \prod_{j,i \in \widehat{A}}{\textrm{P}(s_j,t_i) \times  \textrm{P}_{lm}(t)}
\label{eqC3.13}
\end{equation}

\noindent\hspace{2em}如图\ref{figureC3.14}所示，语言模型$\textrm{P}_{lm}(t)$给分别$t^{'}$和$t^{''}$赋予0.0107和0.0009的概率，这表明句子$t^{'}$更符合英文的表达。这与我们的观察相吻合。当再分别乘以$\prod_{j,i \in \widehat{A}}{\textrm{P}(s_j,t_i)}$\\的值，就得到公式\ref{eqC3.13}定义的函数$g$的值。显然句子$t^{'}$的分数更高。同时它也是我们希望得到的翻译结果。至此我们完成了对函数$g(s,t)$的定义，当代入公式\ref{eqC3.7}就得到了考虑词序的句子级翻译模型。
%----------------------------------------------
% 图3.14
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure314}
    \caption{此处为图片的描述...}
    \label{figureC3.14}
\end{figure}
%---------------------------
\subsection{解码}\index{Chapter3.2.5}

\noindent\hspace{2em}当我们得到句子级翻译模型后，做的一件事就是对于输入模型的任意句子翻译为对应的目标语译文，这个过程称为解码。具体地说，当给定任意的源语句$s$，找到翻译概率最大的目标语译文$\widehat{t}$。如公式\ref{eqC3.14}所示。这里$\emph{argmax}_t{\textrm{P}(t|s)}$表示找到使$\textrm{P}(t|s)$达到最大时的$t$进行输出。换句话说，我们想找到这样一个$t$，它使得$\textrm{P}(t|s)$的计算结果最大。
\begin{equation}
\widehat{t}=\emph{argmax}\textrm{P}(t|s)
\label{eqC3.14}
\end{equation}

\noindent\hspace{2em}结合上一小节对句子级翻译模型的定义和公式\ref{eqC3.14}得到一个新的解码描述。如公式\ref{eqC3.15}所示。
\begin{equation}
\widehat{t}=\argmax_{t}\frac{g(s,t)}{\sum_{t^{'}g(s,t^{'})}}
\label{eqC3.15}
\end{equation}

\noindent\hspace{2em}在公式\ref{eqC3.15}中，我们发现${\sum_{t^{'}g(s,t^{'})}}$仅是关于$s$的函数，当给定源语句$s$时，它是一个常数，不影响对$\widehat{t}$的求解，因此可以进行化简。化简后的解码形式化描述，如公式\ref{eqC3.16}所示。其中g函数的计算见公式\ref{eqC3.13}。
\begin{equation}
\widehat{t}=\argmax_{t}g(s,t)
\label{eqC3.16}
\end{equation}

\noindent\hspace{2em}现在的问题是当面对一个新的源语句$s$时，我们怎么实现公式\ref{eqC3.16}。一个简单粗暴的做法是枚举所有可能的$t$，然后计算函数$g(s,t)$，将分数最高对于的$t$作为最终的翻译结果。

\noindent\hspace{2em}如何枚举所有的$t$呢？假设源语句$s$有$m$个词，每个词有$n$个翻译候选。我们从左到右一步步地扩展译文单词。因为词的候选翻译可以任意调序，所以每一步需要扩展所有没有被翻译的源语单词的翻译候选。换句话说，第一步扩展$m \times n$个候选翻译；第二步扩展$(m-1)\times n$个单词；...... ；第$m-1$步扩展$2\times n$个单词；第$m$步扩展$1 \times n$个单词，直到源语句的全部单词都被翻译。上述过程可以用图3.15表示。其中$\phi$表示空，$w_j^i$表示第$i$步的第$j$个候选翻译，实线表示连接成句。因此源语句$S$对应的可能译文至少有$n^m \bullet m!$。计算见公式\ref{eqC3.17}。
\begin{equation}
(m \times n) \times((m-1)\times n) \times((m-2) \times n) \times ...\times (1 \times n)= n^m \bullet m!
\label{eqC3.17}
\end{equation}
%----------------------------------------------
% 图3.15
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure315}
    \caption{此处为图片的描述...}
    \label{figureC3.15}
\end{figure}
%---------------------------

\noindent\hspace{2em}$n^{m}\bullet m!$是什么样的概念呢？当$m$和$n$分别为2和10时，译文可能有200个，这个计算量并不大。但是当$m$和$n$分别为20和10时，即源语句的词数20，每个词有10个候选译文。此时约有$2.4329 \times 10^{38}$个候选翻译，这几乎是不可计算的。这说明潜在翻译结果的非常多，几乎无法枚举，因此我们需要高效的搜索算法找到理想的解。
%----------------------------------------------
% 图3.16
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure316}
    \caption{此处为图片的描述...}
    \label{figureC3.16}
\end{figure}
%---------------------------

\noindent\hspace{2em}这里介绍一种贪婪的解码算法，它并不从整体最优考虑译文的生成。换句话说，贪婪算法不枚举所有可能的译文，而是每步选择一个源语言单词，利用它的翻译候选扩展译文，并只保留当前步“最好”的结果，直到所有源语言的单词都被翻译。	
%----------------------------------------------
% 图3.17
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure317}
    \caption{此处为图片的描述...}
    \label{figureC3.17}
\end{figure}
%---------------------------

\noindent\hspace{2em}如图\ref{figureC3.17}所示，表示的是贪婪解码的示意图。其中红色实线上的单词串联在一起就得到最终的翻译结果。每一步的计算都是基于上一步的翻译结果，比如在第二步的计算，是基于第一步生成的译文$w_1^1$进行扩展的。换句话说，我们需要选择一个单词$w_{?}^2$，使得$w_1^1$$w_{?}^2$的句子级翻译概率最大。
%----------------------------------------------
% 图3.18
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure318}
    \caption{此处为图片的描述...}
    \label{figureC3.18}
\end{figure}
%---------------------------

\noindent\hspace{2em}贪婪解码的伪代码见图\ref{figureC3.18}。简略地分析下代码。其中$\pi$保存所有源语单词的候选译文，$\pi[j]$表示第$j$个源语单词的候选翻译集合，$best$保存当前最好翻译结果，$h$保存当前步生成的所有译文候选。主体是两层循环，在内层循环中如果第$j$个源语单词没有被翻译过，则用$best$和它的候选译文$\pi[j]$生成新的译文翻译，再存于$h$中，即操作$h=h\cup{JOIN(best,\pi[j])}$。外层循环再从$h$中选择得分最好的结果存于$best$中，即操作$best=PruneForTop1(h)$，并标识相应的源语单词已翻译，即$used[best.j]=true$。
\section{基于词的翻译建模}\index{Chapter3.3}

\noindent\hspace{2em}在上一节中，我们以实现为目的简单地介绍了基于词的机器翻译的建模、训练和解码，但很多问题并没有深入思考。比如如何用更严密的数学模型描述翻译过程，更科学的优化方法完成训练以及更多系统化的方法进行解码，还包括空翻译问题、调序模型问题等等还待解决。只有把这些问题解决了才能接近今天的机器翻译水平。本节将介绍统计机器翻译模型基础，即噪声信道模型以及建模方法，这也是IBM模型中最基本的建模思想。

\subsection{噪声信道模型}\index{Chapter3.3.1}

\noindent\hspace{2em}首先分析下统计机器翻译或IBM模型是从什么角度去完成翻译的。人在做翻译时比较简单。对于给定的源语句$s$，不会尝试太多的可能性，而是快速地翻译一个或者若干个正确的译文$\widehat{t}$。因此在人看来除了正确的译文外，其他的翻译都是不正确的。而统计机器翻译更多地强调可能性大小，即所有的译文都是可能的。换句话说，对于源语句$s$，所有可能的目标语词串$t$都是可能的译文，只是可能性大小不同。即每对$(s,t)$都有一个概率值$\textrm{P}(t|s)$来描述$s$翻译为$t$的好与坏。如图\ref{figureC3.19}所示。
%----------------------------------------------
% 图3.19
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure319}
    \caption{此处为图片的描述...}
    \label{figureC3.19}
\end{figure}
%---------------------------

\noindent\hspace{2em}总之统计机器翻译模型是用概率化的思想指导翻译过程。那如何对这种思想进行建模呢？在IBM模型中使用的建模方式是噪声信道模型，它是由香农在上世纪40年代末提出来的，并于上世纪80年代应用在语言识别领域，后来又被Brown等人用于统计机器翻译中。

\noindent\hspace{2em}噪声信道模型这样看待翻译问题，即源语言句子$s$(信宿)是由目标语句子$t$(信源)经过一个有噪声的信道得到的。如果知道了$s$和信道的性质，我们可以通过$\textrm{P}(t|s)$得到可能的信源的概率，这个过程如图\ref{figureC3.20}所示。
%----------------------------------------------
% 图3.20
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure320}
    \caption{此处为图片的描述...}
    \label{figureC3.20}
\end{figure}
%---------------------------

\noindent\hspace{2em}举个例子来说明噪声信道模型。对于汉译英的翻译任务，汉语句子$s$可以看做英语句子$t$加入噪声后得到的。换句话说，英语经过噪声-信道传输时发生了扭曲变形，在信道的输出端呈现汉语。于是我们需要根据观察到的汉语特征，通过概率$\textrm{P}(t|s)$猜测最为可能的英语句子。

\noindent\hspace{2em}通过上述过程找到最可能的目标语句（信源）的过程称之为解码或翻译。该过程也可以表述为给定源语句$s$，寻找最可能的目标语译文$t$，使得概率$\textrm{P}(\widehat{t}|s)$最大。如公式\ref{eqC3.18}所示。
\begin{equation}
\widehat{t}=\argmax_t\textrm{P}(t|s)
\label{eqC3.18}
\end{equation}

\noindent\hspace{2em}对于公式\ref{eqC3.18}中的 ，我们利用贝叶斯公式进行简单的变换，变换后的形式见公式\ref{eqC3.19}。
\begin{equation}
\textrm{P}(t|s)=\frac{\textrm{P}(s,t)}{\textrm{P}(s)}=\frac{\textrm{P}(s|t)\textrm{P(t)}}{\textrm{P}(s)}
\label{eqC3.19}
\end{equation}

\noindent\hspace{2em}公式\ref{eqC3.19}可以分为三部分。第一部分是$\textrm{P}(s|t)$，也称为翻译模型。它表示给定目标语句$t$生成源语句$s$的概率，需要注意翻译的方向已经从$\textrm{P}(s|t)$转向了$\textrm{P}(t|s)$，但无须刻意的区分，可以简单地理解为翻译模型刻画了$s$和$t$的翻译对应程度。第二部分是$\textrm{P}(t)$，也称为语言模型。它表示的是目标语句$t$的通顺程度。第三部分是$\textrm{P}(s)$，也是语言模型，但刻画的是源语句$s$的通顺程度，在后续的建模中这一项是可以被化简的。

\noindent\hspace{2em}因此我们可以将翻译问题重新表示为公式\ref{eqC3.20}。其中因为$s$的变化不会影响对目标译文$t$的选择，所以可以省略$\textrm{P}(s)$。该式可以理解为：给定源语句子$s$，要寻找这样的目标语译文$t$，它使得翻译模型$\textrm{P}(s|t)$和语言模型$\textrm{P}(t)$乘积最大。
\begin{equation}
\begin{split}
{\widehat{t}}&={\argmax_t\textrm{P}(t|s)}\\
&={\argmax_t \frac{\textrm{P}(t|s)\textrm{P}(t)}{\textrm{P}(s)}=\argmax_t\textrm{P}(s|t)\textrm{P}(t) }
\label{eqC3.20}
\end{split}
\end{equation}

\noindent\hspace{2em}公式\ref{eqC3.20}是IBM模型最基础的建模方式，它把问题分解为两项：翻译模型和语言模型。这样的做法隐含着一个深刻的概念：如果没有语言模型，并且翻译模型不够强大的话，可能会生成局部翻译得当，但整体上不通顺的句子。见图\ref{figureC3.12}描述的例子。为了避免这个问题，从数学技巧上把$\textrm{P}$加了进来，但这并不是必要的过程。

\noindent\hspace{2em}上述就是IBM模型的建模思想。其中的过程就是为了引入$\textrm{P}(t)$，而非简单地为了使用贝叶斯变换。
\subsection{建模}\index{Chapter3.3.2}

\noindent\hspace{2em}IBM模型把翻译问题描述为：给定源语句$s$，在所有可能的译文中找到使翻译模型$\textrm{P}(s|t)$和语言模型$\textrm{P}(t)$乘积最大的译文$\widehat{t}$，如公式\ref{eqC3.20}所示。在具体解决翻译问题时，需要面临三个基本问题，如下所示。

\noindent\hspace{2em}1. 建模：如何描述计算$\textrm{P}(s|t)$和$\textrm{P}(t)$的计算方式。换句话说，如何用可计算的方式把概率描述出来。这也是最核心的问题。

\noindent\hspace{2em}2. 训练：如何获得计算$\textrm{P}(s|t)$和$\textrm{P}(t)$所需的参数。即如何从数据中得到得到模型的最优参数。

\noindent\hspace{2em}3. 解码：如何完成搜索最优解的过程$argmax$。

\noindent\hspace{2em}我们先不介绍上述三个问题该如何解决，而与\ref{chapter3.2.3}小节中的公式\ref{eqC3.13}做比较，即$g(s,t)$函数。如图\ref{figureC3.21}所示，我们看到$g(s,t)$函数可以与本节的建模方式相对应。即$g(s,t)$函数中红色部分求译文$t$的可能性大小，对应翻译模型$\textrm{P}(s|t)$；蓝色部分求译文的平滑或流畅程度，对应语言模型$\textrm{P}(t)$。尽管这种对应并不是严格的，但也间接地完成了翻译问题的建模。
%----------------------------------------------
% 图3.21
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure321}
    \caption{此处为图片的描述...}
    \label{figureC3.21}
\end{figure}
%---------------------------

\noindent\hspace{2em}但$g(s,t)$函数对翻译问题的建模很粗糙。因此下面我们将介绍IBM模型中更严谨和科学的定义与建模。对于语言模型$\textrm{P}(t)$和解码过程（即$argmax$）在前面的内容中都有介绍，所以重点介绍如何求解$\textrm{P}(s|t)$。主要包括两个问题：第一、翻译模型建模，即$\textrm{P}(s|t)$的计算方法；第二、翻译模型参数估计，即计算$\textrm{P}(s|t)$所需的参数。本节主要回答第一个问题，第二个问题留在后面进行介绍。

\noindent\textbf{词对齐}\index{Chapter3.3.2.1}

\noindent\hspace{2em}IBM模型中有一个非常基础的假设—词对齐（或称单词对齐）。词对齐描述了句子和它的译文之间在单词级别的对应。具体地说，给定源语句$s$和目标语译文$t$，并且$s$由$s_1$到$s_m$共$m$个单词组成，$t$由$t_1$到$t_n$共n个单词组成。IBM模型假设词对齐满足下述两个条件。

\noindent\hspace{2em}第一、一个源语言单词只能对应一个目标语单词。图\ref{figureC3.22}表示的例子中，(a)和\\(c)都满足该条件，尽管(c)中的“谢谢”和“你”都对应“thanks”，但并不违背该规则。而(b)不满足该条件，因为“谢谢”同时对应到了两个目标语单词上。因此这种词对齐称为非对称的词对齐。这样假设的目的也是为了减少建模的复杂度。在后来的方法中也提出了双向词对齐，用于建模一个源语言单词对应到多个目标语单词的情况。
%----------------------------------------------
% 图3.21
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure322}
    \caption{此处为图片的描述...}
    \label{figureC3.22}
\end{figure}
%---------------------------

\noindent\hspace{2em}第二、源语言单词可以翻译为空，这时它对应到一个虚拟或伪造的目标语单词$t_0$。图\ref{figureC3.23}表示的例子中，“在”没有对应到“on the table”中的任意词，而是把它对应到$t_0$上。此时所有的源语言单词都能找到一个目标语单词对应，只不过有的单词对应到 上。这个条件或规则的提出主要建模对空翻译，即源语言单词对应第0个目标语单词$t_0$的情况。
%----------------------------------------------
% 图3.21
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure323}
    \caption{此处为图片的描述...}
    \label{figureC3.23}
\end{figure}
%---------------------------

\noindent\hspace{2em}那如何描述词对齐呢？给定源语句子$s$、目标译文$t$和词对齐$a$。其中$a_1$是由$a_m$\\到 共$m$个项依次组成，即$a=a_1...a_m$。$a_j$表示第$j$个源语单词$s_j$对应的目标语单词的位置。如图\ref{figureC3.24}所示，实线表示的是“在 桌子 上”和“on the table”单词之间的对应。该对应关系记为$a_1=0$,$a_2=3$,$a_3=1$。它表示第1个源语单词“在”对应到目标语译文的第0个位置，第2个源语单词“桌子”对应在目标语译文的位置是3，第3个源语单词“上”对应在目标语译文的位置是1。
%----------------------------------------------
% 图3.21
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure324}
    \caption{此处为图片的描述...}
    \label{figureC3.24}
\end{figure}
%---------------------------

\noindent\textbf{建模翻译模型}\index{Chapter3.3.2.2}

\noindent\hspace{2em}直接对句子的翻译概率分布$\textrm{P}(s|t)$进行建模很难，因为大部分句子即使在大规模的语料中也只出现过一次。为了解决这个问题，IBM模型提出的第一个建模思想：句子之间的对应可以由单词之间的对应进行表示。更具体的说，把句子之间对应的概率转换为所有可能的词对齐的生成概率，如公式\ref{eqC3.21}所示。
\begin{equation}
\textrm{P}(s|t)=\sum_a\textrm{P}(s,a|t)
\label{eqC3.21}
\end{equation}

\noindent\hspace{2em}换句话说，公式\ref{eqC3.21}在求解$t$到$s$的翻译概率或者$s$和$t$的互译概率时，枚举$s$和$t$之间所有可能的单词对齐，并把对应的对齐概率进行求和，得到了$t$到$s$的翻译概率。

\noindent\hspace{2em}举个例子说明公式\ref{eqC3.21}。如图\ref{figureC3.25}所示，表示把求“谢谢 你”到“thank you”的翻译概率分解为9种可能的词对齐对应的概率的加和。我们用$t$和$s$分别表示“谢谢 你”和“thank you”。为什么是9种词对齐呢？$s$加上空标记共3个词，而$t$仅有2个词，并且都有可能对应到$s$中任意词，所以共有$3\times3=9$种可能。
%----------------------------------------------
% 图3.21
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure325}
    \caption{此处为图片的描述...}
    \label{figureC3.25}
\end{figure}
%---------------------------

\noindent\hspace{2em}在求解词对齐对应的概率 时，我们也可以用公式\ref{eqC3.13}定义的$g(s,t)$函数，但IBM模型用生成模型更加深刻更加细致地定义了它的计算，如公式\ref{eqC3.22}所示。其中$s$、$a$和$t$分别代表源语句子、目标语译文和词对齐；$s_j$和$a_j$分别表示第$j$个源语单词及其对齐；$s_1^{j-1}$和$a_1^{j}$表示第$j-1$个源语单词和第$j$个源语单词的对齐；$m$表示源语句子的长度。
\begin{equation}
\textrm{P}(s,a|t)=\textrm{P}(m|t)\prod_{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)}
\label{eqC3.22}
\end{equation}

\noindent\hspace{2em}生成模型不像端到端的深度学习，而是把生成数据的过程分解成若干步，通过概率分布对每一步进行建模，然后把它们组合成联合概率。如图\ref{figureC3.26}所示，我们将公式\ref{eqC3.22}分解为四个部分，并用不同的序号和颜色进行表示。下面我们介绍下每一部分的含义。

\noindent\hspace{2em}1. 根据译文$t$选择源文$s$的长度$m$，即估计概率分布$\textrm{P}(m|t)$。

\noindent\hspace{2em}2. 当确定源文长度$m$后，循环每个位置$j$逐次生成单词。

\noindent\hspace{2em}3. 根据译文$t$、源文长度$m$、已经生成的源语单词$s_1^{j-1}$和对齐$a_1^{j-1}$，生成第$j$个位置的对齐结果$a_j$，用概率分布$\textrm{P}(a_j|a_1^{j-1},s_1^{j-1},m,t)$表示。

\noindent\hspace{2em}4. 根据译文$t$、源文长度$m$、已经生成的源语单词$s_1^{j-1}$和对齐$a_1^j$，生成第$j$个位置的源语言单词$s_j$，即$\textrm{P}(s_j|a_1^{j},s_1^{j-1},m,t)$。
%----------------------------------------------
% 图3.26
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure326}
    \caption{此处为图片的描述...}
    \label{figureC3.26}
\end{figure}
%---------------------------

\noindent\hspace{2em}换句话说，当我们求概率分布$\textrm{P}(s,a|t)$时，首先根据译文$t$确定源文$s$的长度$m$；当知道源文有多少个单词后，循环$m$次，依次生成第1个到第$m$个源文单词；当生成第$j$个源文单词时，要先确定它是由哪个目标语译文单词生成的，即确定生成的源语单词对应的译文单词；当知道了目标语译文单词的位置或词对齐，就能确定第$j$个位置有哪些候选的源文单词。

\noindent\textbf{举例说明}\index{Chapter3.3.2.3}

\noindent\hspace{2em}我们用一个简单的例子来说明公式\ref{eqC3.22}。如图3.25所示，源语句子$s$是“在 桌子 上”，目标语译文$t$是“on the table”，以及词对齐$a$等于${1-0,2-3,3-1}$。基于当前的假设，我们套用公式\ref{eqC3.22}用$t$生成$s$和$a$，即求概率$\textrm{P}(s,a|t)$。求解的过程如下所示。
%----------------------------------------------
% 图3.26
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure327}
    \caption{此处为图片的描述...}
    \label{figureC3.27}
\end{figure}
%---------------------------

\noindent\hspace{2em}1. 首先根据译文确定源文$s$的单词数量，可知有3个单词。我们用公式\ref{eqC3.23}表示。
\begin{equation}
\textrm{P}(m=3|'t_0\;on\;the\;table')
\label{eqC3.23}
\end{equation}

\noindent\hspace{2em}2. 再确定源语单词$s_1$由谁生成的且生成的是什么。由词对齐知道$s_1$由第0个目标语单词生成的，也就是$t_0$。当知道了$s_1$由$t_0$生成的，就可以通过$t_0$生成源语第一个单词“在”。我们用公式\ref{eqC3.24}表示。
\begin{equation}
\begin{split}
&{\textrm{P}(a_1\;= 0\;\; |\phi,\phi,3,'t_0\;on\;the\;table')\quad \times}\\
&{\textrm{P}(s_1\;= \textrm{在}\;|\{1-0\},\phi,3,'t_0\;on\;the\;table') }
\label{eqC3.24}
\end{split}
\end{equation}

\noindent\hspace{2em}3. 类似于过程2，我们依次确定源语单词$s_2$和$s_3$由谁生成且生成的是什么。如公式\ref{eqC3.25}和\ref{eqC3.26}所示。
\begin{equation}
\begin{split}
&{\textrm{P}(a_2\;= 3\;\; |\{1-0\},'\textrm{在}',3,'t_0\;on\;the\;table')\quad \times}\\
&{\textrm{P}(s_1\;= \textrm{桌子}\;|\{1-0,2-3\},'\textrm{在}',3,'t_0\;on\;the\;table') }
\label{eqC3.25}
\end{split}
\end{equation}
\begin{equation}
\begin{split}
&{\textrm{P}(a_3\;= 1\;\; |\{1-0,2-3\},'\textrm{在\;桌子}',3,'t_0\;on\;the\;table')\quad \times}\\
&{\textrm{P}(s_1\;= \textrm{上}\;|\{1-0,2-3,3-1\},'\textrm{在\;桌子}',3,'t_0\;on\;the\;table') }
\label{eqC3.26}
\end{split}
\end{equation}

\noindent\hspace{2em}4. 最后将公式\ref{eqC3.23}、\ref{eqC3.24}、\ref{eqC3.25}和\ref{eqC3.26}乘到一起，就得到概率 ，如公式\ref{eqC3.27}所示。
\begin{equation}
\begin{split}
{\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)}\\
&={\textrm{P}(m=3 \mid \textrm{'$t_0$ on the table'}){\times}}\\
&\quad\;{\textrm{P}(a_1=0 \mid \phi,\phi,3,\textrm{'$t_0$ on the table'}){\times} }\\
&\quad\;{\textrm{P}(f_1=\textrm{在} \mid \textrm{\{1-0\}},\phi,3,\textrm{'$t_0$ on the table'}){\times} } \\
&\quad\;{\textrm{P}(a_2=3 \mid \textrm{\{1-0\}},\textrm{'在'},3,\textrm{'$t_0$ on the table'}) {\times}}\\
&\quad\;{\textrm{P}(f_2=\textrm{桌子} \mid \textrm{\{1-0,2-3\}},\textrm{'在'},3,\textrm{'$t_0$ on the table'}) {\times}} \\
&\quad\;{\textrm{P}(a_3=1 \mid \textrm{\{1-0,2-3\}},\textrm{'在 桌子'},3,\textrm{'$t_0$ on the table'}) {\times}}\\
&\quad\;{\textrm{P}(f_3=\textrm{上} \mid \textrm{\{1-0,2-3,3-1\}},\textrm{'在 桌子'},3,\textrm{'$t_0$ on the table'})  }
\label{eqC3.27}
\end{split}
\end{equation}
\section{IBM模型1-2}\index{Chapter3.4}

\noindent\hspace{2em}回顾公式\ref{eqC3.21}和公式\ref{eqC3.22}，我们发现了两个严重的问题。问题一、对于公式(3.20)，如何遍历所有的对齐$a$；问题二、对于公式\ref{eqC3.22}，如何计算$\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)$。Peter E. Brown等人总共提出了5种解决方法。第一个问题可以通过一定的数学技巧进行高效的求解；对于第二个问题，可以通过一些假设进行化简，依据化简的层次和复杂度不同，可以分为IBM模型1、IBM模型2、IBM模型3、IBM模型4以及IBM模型5。本节首先介绍较为简单的IBM模型1-2。
%从此处往下公式+2
\subsection{IBM模型1}\index{Chapter3.4.1}

\noindent\hspace{2em}在IBM模型1中通过一些假设，对公式\ref{eqC3.22}中的三个项进行了简化。

\noindent\hspace{2em}第一、假设$\textrm{P}(m|t)$为常数$\varepsilon$，即源语言的长度是等分布的。如公式\ref{eqC3.28}所示。
\begin{equation}
\textrm{P}(m|t)\; \equiv \; \varepsilon
\label{eqC3.28}
\end{equation}

\noindent\hspace{2em}第二、对齐概率$\textrm{P}(a_j|a_1^{j-1},s_1^{j-1},m,t)$仅依赖于译文长度$l=1$，即假设对齐概率也是均匀分布。换句话说，对于任何$j$到它对齐到目标语句子的任何位置都是等概率的。比如译文为“on the table”，再加上$t_0$共4个位置，相应的源语句子的单词对齐到这4个位置的概率是一样的。
\begin{equation}
\textrm{P}(a_j|a_1^{j-1},s_1^{j-1},m,t) \equiv \frac{1}{l+1}
\label{eqC3.29}
\end{equation}

\noindent\hspace{2em}第三、源语单词$s_j$生成概率$\textrm{P}(a_j|a_1^{j-1},s_1^{j-1},m,t)$仅依懒与其对齐的译文单词$t_{a_i}$，即词汇翻译概率$f(s_j|t_{a_i})$。此时词汇翻译概率满足$\sum_{s_j}{f(s_j|t_{a_i})}=1$。比如在图\ref{figureC3.27}表示的例子中，源语单词“上”生成的概率只和与它对齐的“on”有关系，与其他单词没有关系。
\begin{equation}
\textrm{P}(s_j|a_1^{j},s_1^{j-1},m,t) \equiv f(s_j|t_{a_i})
\label{eqC3.30}
\end{equation}

\noindent\hspace{2em}我们用一个简单的例子说明公式\ref{eqC3.30}。如图\ref{figureC3.28}所示，其中“桌子”对齐“table”。可形象化的描述为$f(s_2 |t_(a_2 ))=f(桌子|table)$，表示给定“table”翻译为“桌子”的概率。
%----------------------------------------------
% 图3.28
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure328}
    \caption{此处为图片的描述...}
    \label{figureC3.28}
\end{figure}
%---------------------------

\noindent\hspace{2em}将上述三个假设和公式\ref{eqC3.22}代入公式\ref{eqC3.21}中，得到概率$\textrm{P}(s|t)$的表示式，如公式\ref{eqC3.31}所示。
\begin{equation}
\begin{split}
{\textrm{P}(s|t)}&=\;{\sum_a{\textrm{P}(s,a|t)}}\\
&=\;{\sum_a{\textrm{P}(m|t)}\prod_{j=1}^{m}{\textrm{P}(a_j|a_1^{j-1},s_1^{j-1},m,t)\textrm{P}(s_j |a_1^j,m,t)}}\\
&=\;{\sum_a{\varepsilon}\prod_{j=1}^{m}{\frac{1}{l+1}f(s_j|t_{a_j})}}\\
&=\;{\sum_a{\frac{\varepsilon}{(l+1)^m}}\prod_{j=1}^{m}f(s_j|t_{a_j})}
\label{eqC3.31}
\end{split}
\end{equation}

\noindent\hspace{2em}在公式\ref{eqC3.31}中需要遍历所有的对齐，即$\sum_a{\bullet}$。但这种表示不够直观，因此我们把这个过程重新表示为公式\ref{eqC3.32}。
\begin{equation}
\textrm{P}(s|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{eqC3.32}
\end{equation}

\noindent\hspace{2em}我们可以把公式\ref{eqC3.32}分为两个部分进行理解和计算。第一部分：遍历所有的对齐$a$。其中$a$由$\{a_1,...,a_m\}$组成，每个$a_j\in \{a_1,...,a_m\}$从译文的开始位置$(0)$循环到截止位置$(l)$。如图\ref{figureC3.28}表示的例子，描述的是源语单词$s_3$从译文的开始$t_0$遍历到结尾$t_3$，即$a_3$。第二部分: 对于每个$a$累计对齐概率$\textrm{P}(s,a|t)$。
%----------------------------------------------
% 图3.29
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure329}
    \caption{此处为图片的描述...}
    \label{figureC3.29}
\end{figure}
%---------------------------

\noindent\hspace{2em}这样就得到了模型1中翻译概率的计算式。它的形式相比原始的计算式要简单许多。可以看出模型1的假设把翻译模型化简成了非常简单的形式。对于给定的$s$，$a$和$t$，只要知道$\varepsilon$和$t(s_j |t_(a_j ))$就可以计算出$\textrm{P}(s|t)$，进而求出$\textrm{P}(s|t)$。

\subsection{IBM模型2}\index{Chapter3.4.2}

\noindent\hspace{2em}IBM模型1中的假设大大化简了问题的难度，但是这些假设显然并不与实际相符。特别是模型1中假设词对齐服从均与分布，这显然存在问题。如图\ref{figureC3.28}，尽管译文$t$比$t'$的质量更好，但对于IBM模型1来说翻译概率相同。这是因为当词对齐服从均匀分布时，模型会忽略了翻译的调序问题。因此当单词翻译相同但顺序不同时，翻译概率一样。
%----------------------------------------------
% 图3.30
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure330}
    \caption{此处为图片的描述...}
    \label{figureC3.30}
\end{figure}
%---------------------------

\noindent\hspace{2em}IBM模型2认为词对齐是有倾向性的，对齐至少要与源语单词的位置和目标语单词的位置有关。基于这种想法，模型2对模型1的词对齐假设进行了修改。它假设对齐对齐位置$a_j$的生成概率与语言单位位置$j$，源语句子长度$m$和译文长度$l$有关。形式化的描述见公式\ref{eqC3.33}。
\begin{equation}
\textrm{P}(a_j|a_1^{j-1},s_1^{j-1},m,t) \equiv a(a_j|j,m,l)
\label{eqC3.33}
\end{equation}

\noindent\hspace{2em}我们用一个简单的例子来说明公式\ref{eqC3.33}。如图\ref{figureC3.31}所示，其中“桌子”对齐“table”。如果在模型1中，“桌子”对齐的译文中的$t_0$、“on”、“the”、和“table”的概率是一样的。但在模型2中可形式化的表示为$a(a_j |j,m,l)=a(3|2,3,3)$，意思是对于源文位置2（$j=2$）的词，如果它的源文是和目标语译文都是3个词（$l=m=3$），对齐到目标语译文位置3（$a_j=3$）的概率是多少。
%----------------------------------------------
% 图3.31

\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure331}
   \caption{此处为图片的描述...}
   \label{figureC3.31}
\end{figure}
%---------------------------

\noindent\hspace{2em}IBM模型2的其他假设均与模型1相同，如公式\ref{eqC3.28}和公式\ref{eqC3.29}所示。把公式\ref{eqC3.28}、\ref{eqC3.29}和\ref{eqC3.33}代入得到完整的模型。如公式\ref{eqC3.34}所示。
\begin{equation}
\textrm{P}(s|t)=\;\sum_a{\textrm{P}(s,a|t)}=\sum_{a_1=0}^{l}{\cdots}\sum _{a_m=0}^{l}{\varepsilon}\prod_{j=1}^{m}{a(a_j|j,m,l)f(s_j|t_{a_j})} 
\label{eqC3.34}
\end{equation}

\noindent\hspace{2em}类似于模型1，模型2的表达式\ref{eqC3.31}也能拆分为两部分进行理解和计算。第一部分：遍历所有的$a$。第二部分：对于每个$a$累加对齐概率$\textrm{P}(s,a|t)$，即计算对齐概率和词汇翻译概率。

\subsection{计算优化}\index{Chapter3.4.3}

\noindent\hspace{2em}暂时没有内容
\begin{equation}
\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{次循环}}
\label{eqC3.35}
\end{equation}

\noindent\hspace{2em}暂时没有内容
%----------------------------------------------
% 图3.32
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure332}
   \caption{此处为图片的描述...}
   \label{figureC3.32}
\end{figure}
%---------------------------

\subsection{训练}\index{Chapter3.4.4}

\noindent\hspace{2em}在前面的章节中我们完成的对翻译的建模，但如何求解出模型的参数的呢？这也是本节需要解决的问题。下面我们将目标函数、极大似然估计、最大化$\textrm{P}(s|t)$和对目标函数求导这四个部分逐步介绍参数的求解过程。

\noindent\textbf{目标函数}\index{Chapter3.4.4.1}

\noindent\hspace{2em}一般来说训练是在训练集上调整参数使得目标函数的值达到最大（最下），此时得到对的参数称为该模型在该目标函数下的最优解，如下图所示。
%----------------------------------------------
% 图3.32
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure333}
   \caption{此处为图片的描述...}
   \label{figureC3.33}
\end{figure}
%---------------------------

\noindent\hspace{2em}在IBM模型中，训练就是对于给定的句对$(s,t)$，最大化翻译概率$\textrm{P}(s|t)$。这里用符号$\textrm{P}_{\theta}(s|t)$表示概率由参数$\theta$决定，公式如下所示。
\begin{equation}
\widehat{\theta}=\argmax_{\theta}\textrm{P}_{\theta}(s|t)
\label{eqC3.36}
\end{equation}

\noindent\hspace{2em}上述公式可以分解为两个部分，如图所示。其中我们的目标函数是$\textrm{P}_{\theta}(s|t)$，而$argmax_{\theta}$表示求最优参数。
%----------------------------------------------
% 图3.34
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure334}
   \caption{此处为图片的描述...}
   \label{figureC3.34}
\end{figure}
%---------------------------

\noindent\textbf{极大似然估计}\index{Chapter3.4.4.2}

\noindent\hspace{2em}那如何求解上述目标函数的最优参数呢？这里我们用到了极大似然估计。所谓极大似然估计，就是要找到使似然函数达到最大的$\theta$。其中$\textrm{P}(s|t)$可以被看做是$(s,t)$上的似然函数，记做$\textrm{L}(s,t;\theta)$。上述公式可以改写为下述公式。其中$L(s,t;\theta)$\\表示$\textrm{L}(\bullet)$依赖模型参数$\theta$，\{$\widehat{\theta}$\}表示可能有多个组的结果，$\Theta$表示参数空间。

\noindent\hspace{2em}那如何找到一组$\theta$使$\textrm{P}_{\theta}(s|t)$达到最大。求函数最大值问题。比如，我们可以对$\textrm{P}_{\theta}(s|t)$求导，令导数为零，得到极值点。

\noindent\textbf{最大化$\textrm{P}(s|t)$}\index{Chapter3.4.4.3}

\noindent\hspace{2em}那如何找到一组$\theta$使$\textrm{P}_{\theta}(s|t)$达到最大呢？一般求函数的最大值问题的做法是：对目标函数进行求导，并令导数为零，得到极值点。如图所示。
%----------------------------------------------
% 图3.35
\begin{figure}[htp]
    \centering
\includegraphics[scale=1]{./Chapter3/Figures/figure1.jpg}
    \caption{求极值点}
    \label{figureC3.35}
\end{figure}
%-------------------------------------------

\noindent\hspace{2em}以IBM模型1为例，我们基于极大似然估计可以把对应的模型训练问题描述为：
\begin{equation}
\begin{split}
&{max(\frac{\varepsilon}{((l+1)^m}\prod_{j=1}^{m}\sum_{i=0}^{l}{f{s_j|t_i}})}\\
&{s.t.\;for\;each\;word\;t_{y}:\;\sum_{s_x}{f(s_x|t_y)}}\\
&{=1}
\label{eqC3.37}
\end{split}
\end{equation}

\noindent\hspace{2em}上述公式的含义解释如下。需要注意的是$\{f(s_x |t_y)\}$对应很多参数，每个源语言单词和每个目标语单词的组合都对应一个$f(s_x |t_y)$。
%----------------------------------------------
% 图3.36
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure337}
    \caption{公式图解}
    \label{figureC3.36}
\end{figure}
%-------------------------------------------

\noindent\textbf{对目标函数求导}\index{Chapter3.4.4.4}

\noindent\hspace{2em}如何解决带约束的目标函数优化问题呢？这里用到了拉格朗日乘数法。在百度百科中关于它的定义如下所示。简单地说，拉格朗日乘数法解决了把含有约束的优化问题转换为了不含约束的优化问题。
%----------------------------------------------
% 图3.37
\begin{figure}[htp]
%    \centering
\includegraphics{./Chapter3/Figures/figure1.png}
    \caption{拉格朗日乘数法}
    \label{figureC3.37}
\end{figure}
%-------------------------------------------

\noindent\hspace{2em}这里我们的目标是$max(\textrm{P}_{\theta}(s|t))$，约束是对于任意的$\forall{t_y}$，都有$\sum_{s_x}{\textrm{P}(s_x|t_y)}=1$。根据拉格朗日乘数法，我们可以把上述优化问题重新定义如下。
\begin{equation}
\begin{split}
L(f,\lambda)=\frac{\epsilon}{(l+1)^m}\prod_{j=1}^{m}\sum_{i=0}^{l}\prod_{j=1}^{m}{f(s_j|t_i)}-\sum_{u}{\lambda_{t_y}(\sum_{s_x}{f(s_x|t_y)}-1)}
\label{eqC3.37}
\end{split}
\end{equation}

\noindent\hspace{2em}分析上式可得。我们可以看到$\lambda_(t_y)$是我们引入的拉格朗日乘数，它的数量和参数约束条件的数量相同。
%----------------------------------------------
% 图3.35
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure338}
   \caption{拉格朗日乘数法}
   \label{figureC3.35}
\end{figure}
%---------------------------

\noindent\hspace{2em}现在我们需要对目标函数L进行求导。首先用$s_u$和$t_v$分别表示任意一个源语单词和一个目标语单词，再进行求导，得到如下公式。
\begin{equation}
\begin{split}
{\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)}}\\
&-{\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)}}\\
&={\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}}
\label{eqC3.38}
\end{split}
\end{equation}

\noindent\hspace{2em}为了求$\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)$

\noindent\hspace{2em}这里可以把$\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{equation}
\beta=\sum_{j=1}^{m} \delta(s_j,s_u)
\label{eqC3.38}
\end{equation}

\noindent\hspace{2em}其中$\delta(x,y)$，当$x=y$时为1，否则为0。

\noindent\hspace{2em}根据$\frac{\partial g(z)}{\partial z} = \frac{\beta}{z} g(z)$。可以得到
\begin{equation}
\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{eqC3.39}
\end{equation}

\noindent\hspace{2em}即目标语译文单词中与$t_v$相同的个数。

\noindent\hspace{2em}根据$\frac{\partial g(z)}{\partial z}$和$\frac{\partial z}{\partial f}$计算的结果，可以得到
%----------------------------------------------
% 图3.36
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure336}
   \caption{拉格朗日乘数法}
   \label{figureC3.36}
\end{figure}
%---------------------------

\noindent\hspace{2em}将$\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)}$
\begin{equation}
\begin{split}
&{\frac{\partial L(f,\lambda)}{\partial f(s_u|t_v)}}\\
&={\frac{\epsilon}{(l+1)^{m}} \cdot \color{red}{\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}}\\
&={\frac{\epsilon}{(l+1)^{m}} \cdot \color{red}{\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{eqC3.40}
\end{split}
\end{equation}

\noindent\hspace{2em}令$\frac{\partial L(f,\lambda)}{\partial f(s_u|t_v)}=0$，有
\begin{equation}
\begin{split}
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)
\label{eqC3.41}
\end{split}
\end{equation}

\noindent\hspace{2em}(二)求$f(s_u |t_v)$的最优解
\section{IBM模型及隐马尔可夫模型}\index{Chapter3.5}
\subsection{基本翻译模型}\index{Chapter3.5.1}

\noindent\hspace{2em}从前面的介绍可知，IBM模型1和模型2都把不同的源文单词都看作相互独立的单元来进行词对齐和翻译。换句话说，即使源语中的某个短语中的两个单词都对齐到同一个目标语单词，它们之间也是相互独立的。这样模型1和模型2对于多个源语单词对齐到同一个目标语单词的情况并不能进行很好的描述。

\noindent\hspace{2em}这里将会给出另一个翻译模型，它能更细致的描述翻译过程，同时在一定程度上解决上面提到的问题。

\noindent\hspace{2em}我们把目标语译文生成源文的过程分解为如下几个步骤。首先确定每个目标语单词生成源语单词的个数，这里把它称为产出率（fertility）。其次决定译文中每个的单词生成的源语单词都是什么，即决定生成的第一个源语单词是什么，生成的第二个源语单词是什么……。这样每个目标语单词就对应了一个源语单词列表。最后把各组源语单词列表中的每个单词都放置到源语句子的某个位置上，完成目标语译文到源文的生成。

\noindent\hspace{2em}{\ref{figureC3.5.1}}中的实例描述了$<\textrm{科学家们 并不 知道}|Scientists(1,2) do(0) not(3) know(\\4)>$的生成过程。首先对于目标语译文$t$的每个单词$t_j$决定它的产出率$\varphi_{j}$。比如“Scie\\-ntists”的产出率是2，可表示为${\varphi}_{1}=2$。这表明它会生成2个源语言单词。其次确定译文中每个单词生成的源语单词列表。比如“Scientists”生成“科学家”和“们”两个源语单词，可表示为${\tau}_1=\{{\tau}_{11}=\textrm{'科学家'},{\tau}_{12}=\textrm{'科学家'}$。这里用特殊的空标记$NULL$表示翻译对空的情况。最后把生成的所有源语言单词放在合适的位置。比如“科学家”和“们”分别放在$s$的位置1和位置2。我们用符号$\pi$记录生成的单词在源语言句子s的位置。比如“Scientists”生成的源语言单词在s中的位置表示为${\pi}_{1}=\{{\pi}_{11}=1,{\pi}_{12}=2\}$。
%----------------------------------------------
% 图3.5.1
\begin{figure}[htp]
    \centering
\includegraphics{./Chapter3/Figures/figure2.jpg}
   \caption{此处为图片的描述...}
   \label{figureC3.5.1}
\end{figure}
%---------------------------

\noindent\hspace{2em}为了表述方便，我们重新说明每个符号的含义。$s$、$t$、$m$和$l$分别表示源文、目标语译文、源文单词数量以及译文单词数量。$\phi$、$\tau$和$\phi$分别记录产出率、生成的源语言单词以及它们在源文中的位置。${\phi}_{j}$表示第$j$个译文单词$t_j$的产出率。${\tau}_{j}$和${\phi}_j$分别表示$t_j$生成的源语言单词列表及其在源语句s中的位置列表。

\noindent\hspace{2em}可以看出，一组$\tau$和$\phi$（记为$<\tau,\phi>$）可以决定一个对齐$a$和一个源语句子$s$。相反的，一个对齐$a$和一个源语句子$s$可以对应多组$<\tau,\phi>$。\ref{figureC3.5.2}所示，表示不同的$<\tau,\phi>$对应同一个源语句子和对齐。它们的区别是目标语单词“Scientists”生成的源语言单词“科学家”和“们”的顺序不同。我们把不同的$<\tau,\phi>$对应到的相同的对齐$a$和源语句子$s$记为$<s,a>$。因此计算$\textrm{P}(s,a|t)$时需要把每个可能结果的概率加起来。如公式\ref{eqC3.5.1}所示。

\begin{equation}
\textrm{P}(s,a|t)=\sum_{{<\tau,\phi>}\in{<s,a>}}{\textrm{P}(\tau,\phi|t) }
\label{eqC3.5.1}
\end{equation}

\noindent\hspace{2em}不过$<s,a>$中有多少个元素呢？通过图\ref{figureC3.5.1}中的例子，可以推出$<s,a>$应该包含$\prod_{i=0}^{l}{\varphi !}$个不同的二元组$<\tau,\pi>$。这是因为在给定源文和对齐时，对于每一个$\tau_i$都有$\varphi_{i}!$种排列。
%----------------------------------------------
% 图3.5.2
\begin{figure}[htp]
    \centering
\includegraphics{./Chapter3/Figures/figure3.jpg}
   \caption{此处为图片的描述...}
   \label{figureC3.5.2}
\end{figure}
%---------------------------

\noindent\hspace{2em}如何表示$\textrm{P}(\tau,\pi|t)$呢？对于一个$t$，在给出$\tau$和$\pi$的情况下，可以得到公式\ref{eqC3.5.2}。其中$τ_{j1}^{k-1}$表示$\tau_{j1}\tau_{j2}\cdots \tau_{j(k-1)}$，$\pi_{j1}^{ k-1}$表示$\pi_{j1}\pi_{j2}\cdots \pi_{j(k-1)}$。
\begin{equation}
\begin{split}
{\textrm{P}(\tau,\pi|t)} &={\prod_{j=0}^{l}{\textrm{P}(\varphi_j|\varphi_{1}^{j-1},t)} \times {\textrm{P}(\varphi_0|\varphi_{1}^{l},t)}} \\
& \times {\prod_{j=0}^l{\prod_{k=1}^{\varphi_j}{\textrm{P}(\tau_{jk}|\tau_{j1}^{k-1},\tau_{1}^{j-1},\varphi_{0}^{l},t )}}}\\
& \times {\prod_{j=1}^l{\prod_{k=1}^{\varphi_j}{\textrm{P}(\pi_{jk}|\pi_{j1}^{k-1},\pi_{1}^{j-1},\tau_{0}^{l},\varphi_{0}^{l},t )}}}\\
& \times{\prod_{k=1}^{\varphi_0}{\textrm{P}(\pi_{0k}|\pi_{01}^{k-1},\pi_{1}^{l},\tau_{0}^{l},\varphi_{0}^{l},t )}}
\label{eqC3.5.2}
\end{split}
\end{equation}

\noindent\hspace{2em}如图\ref{{figureC3.5.3}}所示，我们可以把公式\ref{eqC3.5.2}分为5个部分，并用不同的序号和颜色进行标注。下面我们介绍每一部分的含义。

\noindent\hspace{2em}第一、对于每个$j\in[1,l]$的目标语单词的繁衍率建模。即$\varphi_j$的概率。它依赖于$t$和区间$[1,j-1]$的目标语单词的繁衍率$\varphi_1^{j-1}$。

\noindent\hspace{2em}第二、$j=0$时的繁衍率建模。即空标记$t_0$的繁衍率的概率。它依赖于$t$和区间$[1,j-1]$的目标语单词的繁衍率$\varphi_1^l$。

\noindent\hspace{2em}第三、词汇翻译建模。目标语单词$t_j$生成的第$k$个源语言单词$\tau_{jk}$时的概率，依赖于$t$、所有目标语单词的繁衍率$\varphi_0^l$、区间$j\in[1,l]$的目标语单词生成的源语言单词$\tau_1^{j-1}$和目标语单词$t_j$生成的前$k$个源语言单词$\tau_{j1}^{k-1}$。

\noindent\hspace{2em}第四、对于每个$j\in[1,l]$的目标语单词生成的源语单词的扭曲度（distortion）建模。即第$j$个译文单词生成的第$k$个源语言单词在源文中的位置$\pi_{jk}$的概率。其中$\pi_1^{j-1}$和$\pi_{j1}^{k-1}$分别表示区间$[1,j-1]$的目标语单词生成的源语单词的扭曲度和第$j$译文单词生成的前$k$个源语单词的扭曲度。

\noindent\hspace{2em}第五、$j=0$时的扭曲度建模。即空标记$t_0$生成的源语单词在源文中的位置的概率。
%----------------------------------------------
% 图3.5.3
\begin{figure}[htp]
    \centering
\includegraphics{./Chapter3/Figures/figure4.jpg}
   \caption{此处为图片的描述...}
   \label{figureC3.5.3}
\end{figure}
%---------------------------
\subsection{IBM 模型3}\index{Chapter3.5.2}

\noindent\hspace{2em}IBM模型3通过一些假设对基本翻译模型进行了化简。对于每个$j\in[1,l]$，假设$\textrm{P}(\varphi_j |\varphi_1^{j-1},t)$仅依赖于$\phi_j$和$t_j$，$\textrm{P}(\pi_{jk}|\pi_{j1}^{k-1},\pi_1^{j-1},\tau_0^l,\varphi_0^l,t)$仅依赖于$\pi_{jk}$、$j$、$m$和$l$。而对于所有的$j\in[0,l]$，假设$\textrm{P}(\tau_{jk}|\tau_{j1}^{k-1},\tau_1^{j-1},\phi_0^l,t)$仅依赖于$\tau_{jk}$和$t_j$。形式化这些假设，我们得到公式\ref{eqC3.5.3}$~$\ref{eqC3.5.5}。
\begin{equation}
\textrm{P}(\varphi_j|\varphi_1^{j-1},t)={\textrm{P}(\varphi_j|t_j)}
\label{eqC3.5.3}
\end{equation}
\begin{equation}
\textrm{P}(\tau_{jk}|\tau_{j1}^{k-1},\tau_{1}^{j-1},\varphi_0^t,t)=t(s|t_j)
\label{eqC3.5.4}
\end{equation}
\begin{equation}
\textrm{P}(\pi_{jk}|\pi_{j1}^{k-1},\pi_{1}^{j-1},\tau_{0}^{l},\varphi_{0}^{l},t)=d(i|j,m,l)
\label{eqC3.5.5}
\end{equation}

\noindent\hspace{2em}通常把$d(i|j,m,l)$称为扭曲度（distortion）。这里$\textrm{P}(\varphi_j|\varphi_1^{j-1},t)={\textrm{P}(\varphi_j|t_j)}$和$\textrm{P}(\pi_{jk}$\\$|\pi_{j1}^{k-1},\pi_{1}^{j-1},\tau_0^l,\varphi_0^l,t)=d(i|j,m,l)$仅对$1≤j≤l$成立。此时完成了公式\ref{eqC3.5.2}中第1、3和4部分的建模。

\noindent\hspace{2em}对于$j=0$要单独进行考虑。实际上，$t_0$只是一个虚拟的单词。它要对应源文$s$中原本为空对应的单词（unaligned word）。这里假设，要等其他非空对应单词都被生成（放置）后，才考虑这些空对单词的生成（放置）。即非空对单词都被生成后，在那些还有空的位置上放置这些空对的源语单词。此外，在任何的空位置上放置空对的源语单词都是等概率的，即放置空对源语单词服从均匀分布。这样在已经放置了$k$个空对源语言单词的时候，应该还有$\varphi_0-k$个空位置。如果第$j$个位置为空，那么$\textrm{P}(\pi_{0k}=j|\pi_{01}^{k-1},\pi_1^l,\tau_0^l,\varphi_0^l,t)=(\varphi_0-k)^{-1}$，否则$\textrm{P}(\pi_{0k}=j|\pi_{01}^{k-1},\pi_1^l,\tau_0^l,\varphi_0^l,t)=0$。这样对于$t_0$所对应的$\tau_0$，就有
\begin{equation}
\prod_{k=1}^{\varphi_0}{\textrm{P}(\pi_{0k}|\pi_{01}^{k-1},\pi_{1}^{l},\tau_{0}^{l},\varphi_{0}^{l},e)         }=\frac{1}{\varphi_{0}!}
\label{eqC3.5.6}
\end{equation}

\noindent\hspace{2em}而上面提到的这些$t_0$所对应的空位置是如何生成的呢？即如何确定哪些位置是要放置空对的源语单词。在IBM模型3中，假设在所有的非空对源语单词都被生成出来后（共$\varphi_1+\varphi_2+\cdots {\varphi}_l$个非空对源语单词），这些单词后面都以$p_1$概率随机地产生一个“空”用来放置空对单词。这样，${\varphi}_0$就服从了一个二项分布。于是我们得到
\begin{equation}
\textrm{P}(\varphi_0|t)=(\begin{array}{c}
\varphi_1+\varphi_2+\cdots \varphi_l\\
\varphi_0\\
\end{array})p_0^{\varphi_1+\varphi_2+\cdots \varphi_l+\varphi_0}p_1^{\varphi_0}
\label{eqC3.5.7}
\end{equation}

\noindent\hspace{2em}公式\ref{eqC3.5.7}中$p_0+p_1=1$。此时我们完成了公式\ref{eqC3.5.7}中第2和5部分的建模。最终根据这些假设可以得到$\textrm{P}(s|t)$。其中$n(\varphi_j |e_j)$表示繁衍率的分布。
\begin{equation}
\begin{split}
{\textrm{P}(s|t)}&= {\sum_{a_1=0}^{l}{\cdots}\sum_{a_m=0}^{l}{(\begin{array}{c}
m-\varphi_0\\
\varphi_0\\
\end{array})}p_0^{m-2\varphi_0}p_1^{\varphi_0}\prod_{j=1}^{l}{{\varphi_j}!n(\varphi_j|e_j)    }}\\
& \times{\prod_{i=1}^{m}{t(s_i|t_{s_{ai}})}\prod_{i=1,ai\neq 0}{d(i|a_i,m,l)}}
\label{eqC3.5.8}
\end{split}
\end{equation}

\noindent\hspace{2em}这里面的约束条件为，
\begin{equation}
\sum_{f}{t(s|t)=1}
\label{eqC3.5.9}
\end{equation}
\begin{equation}
\sum_{i}{d(i|j,m,l)=1}
\label{eqC3.5.10}
\end{equation}
\begin{equation}
\sum_{\varphi}{n(\varphi|t)=1}
\label{eqC3.5.11}
\end{equation}
\begin{equation}
p_0+p_1=1
\label{eqC3.5.12}
\end{equation}
\subsection{IBM 模型4}\index{Chapter3.5.3}

\noindent\hspace{2em}经过分析，可以发现IBM模型3并不能很好的处理一个目标语言单词生成多个源语单词的情况。这个问题在模型1和模型2中也存在。如果一个目标语单词对应多个源语单词，往往这些源语单词构成短语或搭配。但是前面这三个模型都把这些源语单词看成独立的单元，而实际上它们应该被看成一个翻译的整体。这就造成了在前三个模型中，这些源语单词可能“分散”开。为了解决这个问题，模型4对模型3进行了修改。

\noindent\hspace{2em}为了更清楚的阐述，我们引入术语—概念单元。以{\color{red}图3.6.1}为例进行说明。图中表示的是源语句“我 改变 主意 了”翻译为目标语语句“I changed my mind”。其中的词对齐关系是“我”对应“I”、“改变”对应“changed”、“主意”对应“mind”、“。”对应“.”以及“了”对空。
%----------------------------------------------
% 图3.6.1
\begin{figure}[htp]
    \centering
\includegraphics[scale=1]{./Chapter3/Figures/figure7.jpg}
   \caption{此处为图片的描述...}
   \label{figureC3.6.1}
\end{figure}
%---------------------------

\noindent\hspace{2em}词对齐又可以被看作概念(concept)之间的对应。这里的概念是指具有独立语法或语义功能的一组单词。依照Brown等人的表示方法，我们把概念记为cept.。每个句子都可以被表示成一系列的cept.。这里要注意的是，源语言句子中的cept.数量不一定等于目标句子中的cept.数量。因为有些cept.可以为空，我们把那些空对的单词看作空cept.。比如在本例中“了”就是（对应）一个空cept.。

\noindent\hspace{2em}在IBM模型的词对齐框架下，目标语的cept.只能是那些非空对的目标语单词，而且每个cept.只能由一个目标语单词组成（通常把这类由一个单词组成的cept.称为单单词cept.）。我们用$[j]$表示第$j$个单单词cept.在目标语句子中的位置。换句话说，$[j]$表示第$j$个非空对的目标语单词在目标语句子中的位置。比如在本例中“mind”在t中的位置表示为$[3]$。

\noindent\hspace{2em}另外，我们用$\odot[j]$表示位置为$[j]$的目标语单词对应的那些源语单词的位置的单单词cept.平均值，如果这个平均值不是整数则对它向上取整。比如在本例中，目标语句中第4个cept.（“.”）对应在源文中第5个输出值。可表示为${\odot}_{[4]}=5$。

\noindent\hspace{2em}利用这些新引进的概念，模型4对模型3的扭曲度进行了修改。主要是把扭曲度分解为两类参数。对于$[j]$对应的源语单词列表($\tau[j]$)中的第一个单词($\tau[j]1$），它的扭曲度用如下等式计算。其中目标语译文的第$j$个单词生成的第$k$个源语单词在源文中的位置用变量$\pi_{jk}$表示，$\pi$表示它的观测值。
\begin{equation}
\textrm{P}(\pi_{[j]=1}=i|{\pi}_1^{[j]-1},{\tau}_0^l,\varphi_0^l,t)=d1(i-{\odot}_{[j-1]}|A(e_{[j-1]}),B(f_i))
\label{eqC3.6.1}
\end{equation}

\noindent\hspace{2em}而对于列表($\tau[j]$)中的其它的单词($\tau[j]k,1<k<\varphi[j]$)的扭曲度计算，如公式(3.6.\\2)所示。
\begin{equation}
\textrm{P}(\pi_{[j]k}=i|{\pi}_{[j]1}^{k-1},\pi_1^{[j]-1},\tau_0^l,\varphi_0^l,t)=d>1(i-\pi_{[j]k-1}|B(f_i))
\label{eqC3.6.1}
\end{equation}

\noindent\hspace{2em}这里的函数$A(.)$和函数$B(.)$分别把目标语和源语的单词影射到单词的词类。这么做的目的一方面要减小参数空间的大小，另一方面是要减小数据的稀疏程度。不过，我们并不会讨论词聚类算法。这里可以提供一种简单的方法，那就把单词直接映射为它的词性即可。这样可以直接用现在已经非常成熟的词性标注技术就可以解决这个问题。

\noindent\hspace{2em}从上面改进的扭曲度模型中可以看出，对于$t[j]$生成的第一个源语单词，要考虑中心$\odot_{[j]}$和这个源语单词之间的绝对距离。实际上也就要把$t[j]$生成的所有源语单词看成一个整体并把它放置在合适的位置。这个过程要依据第一个源语单词的位置$i$及其词类，和前一个非空对目标语单词$t[j-1]$的词类。而对于$t[j]$生成的其它源语单词，只需要考虑它与前一个刚放置完的源语单词的相对位置和这个源语单词的词类。

\noindent\hspace{2em}实际上，上述过程就要先用$t[j]$生成的第一个源语单词代表整个$t[j]$生成的单词列表，并把第一个源语单词放置在合适的位置。然后，把列表中的其它单词放置在相对于前一个刚生成的源语单词合适的地方。这样就可以在一定程度上保证由同一个目标语单词生成的源语单词之间可以相互影响，达到了改进的目的。
\subsection{ IBM 模型5}\index{Chapter3.5.4}

\noindent\hspace{2em}模型3和模型4并不是“准确”的模型。这两个模型会把一部分概率分配给一些根本就不存在的句子。这个问题被称作IBM模型3和模型4的缺陷（Deficiency）。

\noindent\hspace{2em}说的具体一些。模型3和模型4中并没有这样的约束：如果已经放置了某个源语单词的位置不能再放置其它单词，也就是说句子的任何位置只能放置一个词，不能多也不能少。由于缺乏这个约束，模型3和模型4中 在所有合法的对齐 上概率和不等于1。这部分缺失的概率被分配到其它不合法的对齐上。举例来说（图*），“吃 早饭”和“Have breakfast”之间的合法词对齐为 - 。但是在模型3和模型4中， 在它们上的概率和为0.9<0.1。损失掉的概率被分配到像 和 这样的对齐上了。虽然IBM模型并不支持一对多的对齐，但是模型3和模型4并不能保证满足这个假设，因此也就产生所谓的dificency问题。

%----------------------------------------------
% 图3.5.4

\begin{figure}[htp]
    \centering
\includegraphics[scale=1]{./Chapter3/Figures/figure5.jpg}
    \caption{Model 3的对齐实例}
    \label{figureC3.5.4}
\end{figure}
%-------------------------------------------

\noindent\hspace{2em}为了解决这个问题，模型5在模型中增加了约束。模型5的基本想法是，在放置一个源语单词的时候检查要放置的位置是否已经放置了单词，如果可以则把这个放置过程赋予一定的概率，否则把它作为不可能事件。依据这个想法，就需要在逐个放置源语单词的时候判断源语句子的哪些位置为空。这里引进一个变量$v(i, {\tau_1}^{[j]-1}, \\\tau_{[i]1}^{k-1})$，他表示在放置$\tau_{[i]k}$之前（$\tau_1^{[j]-1}$和$\tau_{[i]1}^{k-1}$已经被放置完了），从源语句子的第一个位置到位置i（包括i）为止还有多少个空位置。本文中把这个变量简写为$v_j$。这样，

\noindent\hspace{2em}对于[j]对应的源语单词列表（$\tau_{[j]}$）中的第一个单词（$\tau_{[j]1}$），

\begin{equation}
\textrm{P}(\prod_{[j]1} = i | \pi_1^{[j]-1}, \tau_0^l, \phi_0^l, t) = d_1(v_i|\textbf{B}(f_i), v_{j-1}, v_m-\phi_{[j]}+1)(1-\delta(v_i,v_{i-1}))
\label{eqC3.5.41}
\end{equation}

\noindent\hspace{2em}对于其它单词（$\tau_{[j]k}$, $1<k\leqslant\phi_{[j]}$）,

\begin{equation}
\begin{split}
&\textrm{P}(\prod_{[j]k}=i|\pi_{[j]1}^{k-1}, \pi_1^{[j]-1}, \tau_0^l, \phi_0^l, t) \\
&= d_{>1}(v_i-v_{\phi_{[j]}k-1}|\textbf{B}(f_i), v_{j-1}, v_m-v_{\phi_{[j]}k-1}-\phi_{[j]}+1)(1-\delta(v_i,v_{i-1}))
\end{split}
\label{eqC3.5.42}
\end{equation}

\noindent\hspace{2em}这里，因子$1-\delta(v_j, v_{j-1})$是用来判断第i个位置是不是为空。如果第i个位置为空则$v_j = v_{j-1}$，这样$\textrm{P}(\prod_{[j]1}=i|\pi_1^{[j]-1}, \tau_0^l, \phi_0^l, t) = 0$。这样就从模型上避免了模型3和模型4中生成不存在的字符串的问题。这里还要注意的是，对于放置第一个单词的情况，影响放置的因素有$v_j$，$\textbf{B}(f_i)$和$v_{j-1}$。此外还要考虑在i位置放置了第一个单词以后它的右边是不是还有足够的位置留给剩下的k-1个单词。参数$v_m-\phi_{[j]}+1$就是为了考虑这个因素，这里$v_m$表示整个源语言句子中还有多少空位置，$\phi_{[j]}-1$表示i位置右边至少还要留出的空格数。对于放置非第一个单词的情况，主要是要考虑它和前一个放置位置的相对位置。这主要体现在参数$v_i-v_{\phi_{[j]}k-1}$上。式(4.99)的其它部分都可以的用上面的理论解释，这里不再重复。

\noindent\hspace{2em}实际上，模型5和模型4的思想基本一致，即，先确定$\tau_{[j]1}$的绝对位置，然后再确定$\tau_{[j]}$中剩余单词的相对位置。模型5消除了产生不存在的句子的可能性，不过模型5的复杂性也大大增加了。

\subsection{隐马尔可夫模型}\index{Chapter3.5.5}

\noindent\hspace{2em}是

\section{IBM模型的若干问题分析}\index{Chapter3.6}%Index的作用，目前不清晰

\subsection{词对齐}\index{Chapter3.6.1}

\noindent\textbf{问题分析}\index{Chapter3.6.1.1}

\noindent\hspace{2em}IBM的五个模型都是基于一个词对齐的假设 —— 一个源语单词最多只能对齐到一个目标语单词。这个约束大大化简了IBM模型的建模。最初，Brown等人提出这个假设可能是因为在法英翻译中一对多的对齐情况并不多见，这个假设带来的问题也不是那么严重。但是，在像汉英翻译这样的机器翻译任务中，一个中文单词对应多个英文单词的翻译很常见。这时IBM模型的词对齐假设就表现出了明显的问题。比如在翻译<I will have a try .|我 会 试一试 。>中，IBM模型根本不可能把单词“试一试”对齐到三个单词“have a try”，因而很难得到正确的翻译结果。可见IBM模型的词对齐假设所带来的问题还是很严重的。

\noindent\hspace{2em}本质上说，IBM模型的词对齐的不“完整”问题是IBM模型本身的缺陷。说得更清楚一些，这个问题就是IBM模型建模的缺陷。因此要想从根本上解决这个问题，只有对IBM模型进行修改或者提出新的词对齐模型来避免对IBM模型词对齐假设的依赖。但是不论是对IBM模型进行修改还是提出新的词对齐模型，至今仍没有太多的进展。这主要是由于建模问题本身就是NLP乃至整个人工智能领域中最困难的问题之一，对经典的IBM的修改或替换谈何容易。

\noindent\textbf{解决方法}\index{Chapter3.6.1.2}

\noindent\hspace{2em}前面已经提到，对IBM模型的直接修改是非常困难的。不过也有一些不需要改动模型就可以缓解该问题的方法。

\noindent\hspace{2em}第一种方法就是，反向训练后，合并源语单词，然后再正向训练。这里用汉英翻译为例来解释这个方法。首先反向训练，就是把英语当作待翻译语言，而把汉语当作目标语言进行训练（参数估计）。这样可以得到一个词对齐结果（参数估计的中间结果，比如可以让系统输出训练中使P(a|t,s;3)达到最大的词对齐结果）。在这个词对齐结果里面，一个中文单词可对应多个英文单词。之后，扫描每个英文句子，如果有多个英文单词对应同一个中文单词，就把这些英文单词合并成一个英文单词。处理完之后，再把汉语当作源语言把英语当作目标语言进行训练。这样就可以把一个中文词对应到合并的英文单词上。虽然从模型上看，还是一个中文单词对应一个英文“单词”，但实质上已经把这个中文单词对应到多个英文单词上了。训练完之后，再利用这些参数进行翻译（解码）时，就能把一个中文单词翻译成多个英文单词了。这个方法的流程如图所示。%\ref{figureC6.1}

%----------------------------------------------
%图6.1
\begin{figure}[h]
    \centering
\includegraphics{./Chapter3/Figures/figure6.jpg}
    \caption{此处为图片的描述...单词x和y在句对(s, t)中的共现总次数的算法}
    \label{figureC6.1}
\end{figure}
%---------------------------

\noindent\hspace{2em}但是反向训练后再训练也存在一些问题。首先，合并英文单词会使数据变得更稀疏，使训练不充分。其次，由于IBM模型的词对齐结果并不是高精度的，利用它的词对齐结果来合并一些英文单词可能造成严重的错误，比如：把本来很独立的几个单词合在了一起。因此，此方法也并不完美。具体使用时还要考虑实际需要和问题的严重程度来决定是否使用这个方法。

\noindent\hspace{2em}第二个方法，双向对齐。这个方法可以帮助我们在IBM词对齐的基础上获得“完整”的词对齐结果。它的思路很简单，就是用正向（汉语为源语，英语为目标语）和反向（汉语为目标语，英语为源语）同时训练。这样可以得到两个词对齐结果。然后可以对这两个词对齐结果求“并集”，这样就可以得到包含1对多和多对多的词对齐结果。

\noindent\hspace{2em}不过这个方法只是提供了获得“完整”的词对齐的手段。因为基于IBM模型的解码器还是不支持这种对齐，因此还并不能直接使用它。如何利用这个“完整”的词对齐结果也是一个问题。在基于短语的统计机器翻译中已经很成功地使用了这些词对齐信息。这里并不对此做深入讨论。

\subsection{Deficiency}\index{Chapter3.6.2}

\noindent\textbf{问题分析}\index{Chapter3.6.2.1}

\noindent\hspace{2em}Deficiency问题是指翻译模型会把一部分的概率分配给一些根本不存在的源语言字符串。

\noindent\hspace{2em}如果用P(well|e)表示P(f|e)在所有的正确的（可以理解为语法上正确的）f上的和，即
\begin{equation}
\textrm{P}(well|e)=\sum_{\textbf{f}\;is\;well\;formed}{\textrm{p}(\textbf{f}|\textbf{e})}
\label{eqC3.6.1}
\end{equation}

\noindent\hspace{2em}类似地，用$\textrm{P}(ill|e)$表示$\textrm{P}(f|e)$在所有的错误的$（$可以理解为语法上错误的$）$$f$上的和。如果$\textrm{P}r(well|e)+ \textrm{P}r(ill|e)<1$，就把剩余的部分定义为$\textrm{P}(failure|e)$。它的形式化定义为，
\begin{equation}
\textrm{P}({failure|e})  = 1 - \textrm{P}({well|e}) - \textrm{P}({ill|e})
\label{eqC3.6.1}
\end{equation}

\noindent\hspace{2em}本质上来说，模型3和模型4就是对应P(failure|e)>0的情况。这部分概率是模型损失掉的。有时候也把这类Deficiency问题称为technical deficiency。还有一种Deficien\\-cy问题被称作spiritual deficiency，它是指Pr(well|e)+ Pr(ill|e)=1且Pr(ill|e)>0的情况。模型1和模型2就有spiritually deficiency的问题。比如，在模型1中< 我 改变 主意 了|I(1) changed(2) my(0) mind(3)>和<主意 了 改变 我| I(4) changed(3) my(0) mind(1)>的翻译概率是相同的。显然“主意 了 改变 我”不是一个很合理的且符合中文语法的句子。

\noindent\hspace{2em}应该注意到，technical deficiency只存在于模型3和模型4中，模型1和模型2并没有technical deficiency问题。根本原因是模型1和模型2的词对齐是从源语出发对应到目标语，e到f的翻译过程实际上是从f1开始到fm结束，依次把每个fi对应到唯一一个目标语位置。显然，这个过程能够保证每个源语言单词仅对应一个目标语单词。但是，模型3和模型4中对齐是从目标语出发对应到源语言，e到f的翻译过程从e1开始el结束，依次把ej生成的单词对应到某个源语言位置上。但是这个过程不能保证，ej中生成的单词所对应的位置没有被其它已经完成对齐的ej’生成的某个单词对应过。因此也就产生了deficency问题。

\noindent\hspace{2em}这里还要强调的是，technical deficiency是模型3和模型4是模型本身的缺陷造成的，如果有一个“更好”的模型就可以完全避免这个问题。而spiritually deficiency几乎是不能从模型上根本解决的，因为对于任意一种语言我们都不能枚举所有的句子（Pr(ill|e)实际上是得不到的）。也就是说，我们还很难找到一个通用的模型解决spiritually deficiency问题。无论是引入语言模型还是使用其它方法，都只是缓解这个问题。

\noindent\textbf{解决方法}\index{Chapter3.6.2.2}

\noindent\hspace{2em}IBM的模型5已经解决了technical deficiency问题。不过模型5过于复杂。实际上technical deficiency问题是不是需要解决，这一点在本节—其他问题还要进行讨论。

\noindent\hspace{2em}spiritually deficiency的解决很困难，因为即使对于人来说也很难判断一个句子是不是“良好”的句子。当然可以考虑用语言模型Pr(f)来缓解这个问题，不过由于在翻译的时候f都是定义“良好”的句子，Pr(ill|e)对Pr(f|e)的影响并不大。但用输入的f的“良好性”并不能解决technical deficiency，因为technical deficiency是模型的问题或者模型参数估计方法的问题。无论输入什么样的f，模型3和模型4的technical deficiency问题都存在。

\subsection{单词翻译}\index{Chapter3.6.3}

\noindent\textbf{问题分析}\index{Chapter3.6.3.1}

\noindent\hspace{2em}在IBM模型中翻译的单元是单词。但除了字符串它没有考虑单词的时态、语态、句法等信息。比如，在实验中我们发现，系统把“他 去…”翻译成了“He go to …”。这是由于“去”这个单词经常和“go”共现，这样系统很容易就把“去”翻译成了“go”，不管它是不是第三人称单数。类似的单词翻译问题还有一些。如在下面的实例1中，“year”使用的是单数形式，而实际上应该是复数形式。在实例2中，increase应该使用第三人称单数或者被动语态。而实例3中，“3月15日”被翻译成了“three month 15”这些显然都是不正确的翻译。

\noindent\hspace{2em}实例1

\noindent\hspace{2em}源语句子：经过10多年的建设 …

\noindent\hspace{2em}IBM模型4翻译结果：After 10 year of construction …

\noindent\hspace{2em}实例2

\noindent\hspace{2em}源语句子：今年北京考生填报志愿继续实行网上填报。

\noindent\hspace{2em}IBM模型4翻译结果：Through this elevate the railway passenger transport capacity increase by 18\% and 12\% respectively .

\noindent\hspace{2em}实例3

\noindent\hspace{2em}源语句子：从3月15日 …

\noindent\hspace{2em}IBM模型4翻译结果：From three month 15

\noindent\hspace{2em}产生这些问题的原因是，IBM模型处理的单元是单词（字符串）。只有在语料中训练很充分的情况下，才可能得到准确的翻译结果。如果语料中一个单词的某种翻译出现的很少，那么这个翻译对应的翻译概率通常也不会很高。这样即使对于某些句子这个翻译是正确的，也就很难选择它作为译词。比如在实例3中，如果训练语料中“15”从来没有被翻译为“15th”，那么测试语料就不可能得到它的正确翻译。本质上，这个问题还是由于数据的稀疏性造成的。

\noindent\textbf{解决方法}\index{Chapter3.6.3.2}

\noindent\hspace{2em}解决这类问题的最理想方法就是在模型中加入除了句子以外的其它特征，比如：时态、词性、专名等信息。但是这些特征的引入将会使模型异常复杂。而且它也并不会解决数据的稀疏问题。它并不是很好的方法。

\noindent\hspace{2em}另一种方法是，通过预处理和后处理把某些有相同特征的单词（或词组）表示成相同的“单词”。比如：在预处理的时候把语料中的日期都用\$date替换，而是在后处理的时候在再对\$date进行单独翻译。或者把单词都替换成词性，通过训练获得对齐模板（因为对齐的并不是单词）。然后用对齐模板修正基于单句子的对齐结果。这些方法都能在一定程度上缓解数据稀疏问题。

\subsection{句子长度}\index{Chapter3.6.4}

\noindent\textbf{问题分析}\index{Chapter3.6.4.1}

\noindent\hspace{2em}在IBM模型中，P(e)P(f|e)会随着l（目标语句子长度）的增加而减少。这也就是说，IBM模型会更“偏向”选择长度短一些的目标语句子。显然这种对短句子的偏向性并不是我们所期望的。

\noindent\textbf{解决方法}\index{Chapter3.6.4.2}

\noindent\hspace{2em}对于这个问题，可以通过在模型中增加一个短句子惩罚引子来抵消调模型对短句子的倾向性。比如，可以重新定义P(e|f)，

\begin{equation}
\textrm{P}({e|f}) \approx {LB} \times \textrm{P}({e}) \times \textrm{P}({f|e})
\label{eqC3.6.2}
\end{equation}

\begin{equation}
{LB} = c^1
\label{eqC3.6.3}
\end{equation}

\noindent\hspace{2em}其中LB为惩罚引子，c为一个大于1的常数。LB会随着l的增加而增大。

\noindent\hspace{2em}本质上说，式\ref{eqC3.6.3}并不符合一个严格的噪声信道模型。它对应一个基于最大熵框架的翻译模型，在这个模型中一共有三个特征LB、P(e)和P(e|f)每个特征的权重都是1。

\subsection{其它问题}\index{Chapter3.6.5}

\noindent\textbf{模型5的意义}\index{Chapter3.6.5.1}

\noindent\hspace{2em}模型5的提出是为了消除了模型3和模型4的deficiency问题。Deficiency问题本质是，P(f,a|e)在所有合理的对齐上概率和不为1。但是，在统计机器翻译中我们根关心是哪个对齐a使P(f,a|e)达到最大，即使P(f,a|e)不符合概率分布的定义，也并不影响我们寻找理想的a。从这个角度说，P(f,a|e)不归一并不是一个十分严重的问题。

\noindent\hspace{2em}实际上至今也没有人对IBM模型3和模型4中的deficiency问题进行过系统的实验和分析，这个问题到底有多严重并没有定论。当然用模型5是可以解决这个问题。但是如果用一个非常复杂的模型去解决了一个并不产生严重后果的问题，那这个模型也就没有太大意义了。

\noindent\textbf{概念（Cept.）的意义}\index{Chapter3.6.5.2}

\noindent\hspace{2em}经过前面的分析可知，IBM模型的词对齐模型是使用了cept.这个概念。但是实质上，在IBM模型中使用的cept.最多只能对应一个目标语单词（模型并没有用到源语cept.的概念）。因此可以直接用单词代替cept.。这样，即使不引入cept.的概念，也并不影响IBM模型的建模。

\noindent\hspace{2em}实际上cept.的引入确实可以帮助我们从语法和语义的角度解释词对齐过程。不过，这个概念并没在IBM模型中发挥出效果。它对IBM模型的建模的意义并不是很大。