chapter7.tex

% !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
%----------------------------------------------------------------------------------------

\renewcommand\figurename{图}%将figure改为图
\renewcommand\tablename{表}%将figure改为图
\chapterimage{fig-NEU-7.jpg} % Chapter heading image

%----------------------------------------------------------------------------------------
%	CHAPTER 7
%----------------------------------------------------------------------------------------

\chapter{基于短语的模型}

\parinterval 机器翻译的一个问题是要定义翻译的基本单元是什么。比如，可以像第三章介绍的那样，以单词为单位进行翻译，即把句子的翻译看作是单词之间对应关系的一种组合。基于单词的模型是符合人类对翻译问题的认知的，因为单词本身就是人类加工语言的一种基本单元。另一方面，在进行翻译时也可以使用一些更``复杂''的知识。比如，很多词语间的搭配需要根据语境的变化进行调整，而且对于句子结构的翻译往往需要更上层的知识，如句法知识。因此，在对单词翻译进行建模的基础上，需要探索其他类型的翻译知识，使得搭配和结构翻译等问题可以更好地被建模。

\parinterval 本章会介绍基于短语和基于句法的翻译模型。在过去二十年中，它们一直是机器翻译的主流方法。相比于基于单词的翻译模型，基于短语和基于句法的模型可以更好地对单词之间的依赖关系进行描述，同时可以对句子的上层结构进行有效的表示。这些方法也在相当长的一段时期内占据着机器翻译的统治地位。虽然近些年随着神经机器翻译的崛起，基于短语和基于句法的统计翻译模型有些``降温''，但是它仍然是机器翻译的主要框架之一，其中的思想和很多技术手段对今天的机器翻译研究仍然有很好的借鉴意义。
%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------
\sectionnewpage
\section{翻译中的结构信息}

\parinterval 首先，回顾一下基于单词的统计翻译模型是如何完成翻译的。图\ref{fig:7-1}展示了一个实例。其中，左侧是一个单词的``翻译表''，它记录了源语言（中文）单词和目标语言（英文）单词之间的对应关系，以及这种对应的可能性大小（用P表示）。在翻译时，会使用这些单词一级的对应，生成目标语言译文。比如，图\ref{fig:7-1}右侧就展示了一个基于词的模型生成的翻译结果，其中$\mathbf{s}$和$\mathbf{t}$分别表示源语言和目标语言句子，单词之间的连线表示两个句子中单词一级的对应。

%----------------------------------------------
\begin{figure}[htp]
\centering
\begin{tabular}{l r}
\subfigure{\input{./Chapter7/Figures/figure-example-of-translation-base-word-1}} & \subfigure{\input{./Chapter7/Figures/figure-example-of-translation-base-word-2}} \\
\end{tabular}
\caption{基于单词的翻译实例}
\label{fig:7-1}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:7-1}体现的是一个典型的基于单词对应关系的翻译方法。它非常适合{\small\bfnew{组合性翻译}}\index{组合性翻译}（Compositional Translation）\index{Compositional Translation}的情况，也就是通常说的直译。不过，自然语言作为人类创造的高级智能的载体，远比想象的复杂。比如，即使是同一个单词，词义也会根据不同的语境产生变化。

%----------------------------------------------
\begin{figure}[htp]
\centering
\begin{tabular}{l r}
\subfigure{\input{./Chapter7/Figures/figure-example-of-translation-black-tea-1}} & \subfigure{\input{./Chapter7/Figures/figure-example-of-translation-black-tea-2}}
\end{tabular}
\caption{基于单词的模型对搭配``红\ 茶''进行翻译}
\label{fig:7-2}
\end{figure}
%-------------------------------------------


\parinterval 图\ref{fig:7-2}给出了一个新的例子。如果同样使用概率化的单词翻译对问题进行建模，对于输入的句子``我\ 喜欢\ 红\ 茶''，翻译概率最大的译文是``I like red tea''。显然，``red tea''并不是英文中``红\ 茶''的说法，正确的译文应该是``black tea''。

\parinterval 这里的问题在于，``black tea''不能通过``红''和``茶''这两个单词直译的结果组合而成，也就是，把``红''翻译为``red''并不符合``红\ 茶''这种特殊的搭配的翻译。即使在训练数据中``红''有很高的概率被翻译为``red''，在这个例子中，应该选择概率更低的译文``black''。那如何做到这一点呢？如果让人来做，这个事不难，因为所有人学习英语的时候都知道``红''和``茶''放在一起构成了一个短语，或者说一种搭配，这种搭配的译文是固定的，记住就好。同理，如果机器翻译系统也能学习并记住这样的搭配，显然可以做得更好。这也就形成了基于短语和句法的机器翻译建模的基本思路。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{更大粒度的翻译单元}

\parinterval 既然仅仅使用单词的直译不能覆盖所有的翻译现象，那就可以考虑在翻译中使用更大颗粒度的单元，这样能够对更大范围的搭配和依赖关系进行建模。一种非常简单的方法是把单词扩展为$n$-gram（这里视为{\small\bfnew{短语}}\index{短语}）。也就是，翻译的基本单元是一个个连续的词串，而非一个个相互独立的单词。

%----------------------------------------------
\begin{figure}[htp]
\centering
\begin{tabular}{l r}
\subfigure{\input{./Chapter7/Figures/figure-example-of-n-gram-1}} & \subfigure{\input{./Chapter7/Figures/figure-example-of-n-gram-2}} \\
\end{tabular}
\caption{基于短语（$n$-gram）的翻译的实例}
\label{fig:7-3}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:7-3}展示了一个引入短语之后的翻译结果。其中的翻译表不仅包含源语言和目标语言单词之间的对应，同时也包括短语（$n$-gram）的翻译。这样，``红\ 茶''可以作为一个短语包含在翻译表中，它所对应译文是``black tea''。对于待翻译句子，可以使用单词翻译的组合得到``红\ 茶''的译文``red tea''，也可以直接使用短语翻译得到``black tea''。由于短语翻译``红\ 茶 $\to$ black tea''的概率更高，因此最终会输出正确的译文``black tea''。

\parinterval 一般来说，统计机器翻译的建模对应着一个两阶段的过程：首先，得到每个翻译单元所有可能的译文；然后，通过对这些译文的组合得到可能的句子翻译结果，并选择最佳的目标语言句子输出。如果基本的翻译单元被定义下来，机器翻译系统可以学习这些单元翻译所对应的翻译知识（对应训练过程），之后运用这些知识对新的句子进行翻译（对应解码过程）。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-word-translation-regard-as-path}
\caption{基于单词的翻译被看作是一条``路径''}
\label{fig:7-4}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:7-4}给出了基于单词的机器翻译过程的一个示例。首先，每个单词的候选译文都被列举出来，而机器翻译系统就是要找到覆盖所有源语言单词的一条路径，它所对应的译文概率是最高的。比如，图中的红色折线就代表了一条翻译路径，也就是一个单词译文的序列\footnote[1]{为了简化问题，这里没有描述单词译文的调序。对于调序的建模，可以把它当作是对目标语单词串的排列，这个排列的好坏需要用额外的调序模型进行描述。详细内容见\ref{subsection-7.4}节。}。

\parinterval 在引入短语翻译之后，并不需要对上述过程进行太大的修改。仍然可以把翻译当作是一条贯穿源语言所有单词译文的路径，只是这条路径中会包含短语，而非一个个单词。图\ref{fig:7-5}给出了一个实例，其中的蓝色折线表示包含短语的翻译路径。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-word-and-phrase-translation-regard-as-path}
\caption{翻译被看作是由单词和短语组成的``路径''}
\label{fig:7-5}
\end{figure}
%-------------------------------------------

\parinterval 实际上，单词本身也是一种短语。从这个角度说，基于单词的翻译模型是包含在基于短语的翻译模型中的。而这里的所说的短语包括多个连续的单词，可以直接捕捉翻译中的一些局部依赖。而且，由于引入了更多样翻译单元，可选择的翻译路径数量也大大增加。本质上，引入更大颗粒度的翻译单元给建模增加了灵活性，同时增大了翻译假设空间。如果建模合理，更多的翻译路径会增加找到高质量译文的机会。在\ref{section-4.2}节还将看到，基于短语的模型会从多个角度对翻译问题进行描述，包括基础数学建模、调序等等。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{句子的结构信息}

\parinterval 使用短语的优点在于可以捕捉具有完整意思的连续词串，因此能够对局部上下文信息进行建模。当单词之间的搭配和依赖关系出现在连续词串中时，短语可以很好地对其进行描述。但是，当单词之间距离很远时，使用短语的``效率''很低。同$n$-gram语言模型一样，当短语长度变长时，数据会变得非常稀疏。比如，很多实验已经证明，测试数据中超过5个的连续单词在训练数据中往往是很低频的现象，更长的短语甚至都很难在训练数据中找到。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-long-distance-dependence-in-zh2en-translation}
\caption{汉英翻译中的长距离依赖}
\label{fig:7-6}
\end{figure}
%-------------------------------------------

\parinterval 当然，可以使用平滑算法对长短语的概率进行估计，但是使用过长的短语在实际系统研发中仍然不现实。图\ref{fig:7-6}展示了一个汉语到英语的翻译实例。源语言的两个短语（蓝色和红色高亮）在译文中产生了调序。但是，这两个短语在源语言句子中横跨11个单词。如果直接使用这个11个单词构成的短语进行翻译，显然会有非常严重的数据稀疏问题，因为很难期望在训练数据中见到一模一样的短语。

\parinterval 如果仅仅使用连续词串不能处理所有的翻译问题，根本的原因在于句子的表层串很难描述片段之间大范围的依赖。一个新的思路是使用句子的结构信息进行建模。第二章已经介绍了句子的句法表示形式。对于每个句子，都可以用句法树描述它的结构。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-chinese-syntax-tree}
\caption{一个英文句法树（短语结构树）}
\label{fig:7-7}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:7-7}就展示了一棵英文句法树（短语结构树）。句法树描述了一种递归的结构，每个句法结构都可以用一个子树来描述，子树之间的组合可以构成更大的子树，最终完成整个句子的表示。相比线性的序列模型，树结构更容易处理大片段之间的关系。比如，两个在序列中距离``很远''的单词，在树结构中可能会``很近''。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-example-of-translation-use-syntactic-structure}
\caption{使用句法结构进行机器翻译的实例}
\label{fig:7-8}
\end{figure}
%-------------------------------------------

\parinterval 句法树结构可以赋予机器翻译一种对语言进一步抽象的能力，这样，并不需要使用连续词串，而是通过句法结构来对大范围的译文生成和调序进行建模。图\ref{fig:7-8}是一个在翻译中融入源语言（中文）句法信息的实例。这个例子中，介词短语包含15个单词，因此，使用短语很难涵盖``在 $...$ 后''这样的片段。这时，系统会把``在 $...$ 后''错误的翻译为``In $...$''。通过句法树，可以知道``在 $...$ 后''对应着一个完整的子树结构PP（介词短语）。因此也很容易知道介词短语中``在 $...$ 后''是一个模板（红色），而``在''和``后''之间的部分构成从句部分（蓝色）。最终得到正确的译文``After $...$''。

\parinterval 使用句法信息在机器翻译中不新鲜。在基于规则和模板的翻译模型中，就大量地使用了句法等结构信息。只是由于早期句法分析技术不成熟，系统的整体效果并不突出。在统计机器翻译时代，句法可以很好地融合在统计建模中。通过概率化的文法设计，可以对翻译过程进行很好的描述。在本章的\ref{section-4.3}节和\ref{section-4.4}节中将会详细讨论句法信息在统计机器翻译中的应用。
%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{机器翻译中的短语}

\parinterval 基于短语的机器翻译的基本假设是：双语句子的生成可以用短语之间的对应关系进行表示。图\ref{fig:7-9}展示了一个基于短语的翻译实例。可以看到，这里的翻译单元是连续的词串。比如，``进口''的译文``The imports have''就包含了三个单词，而``下降\ 了''也是一个包含两个单词的源语言片段。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-example-of-zh2en-translation-base-phrase}
\caption{基于短语的汉英翻译实例}
\label{fig:7-9}
\end{figure}
%-------------------------------------------

\parinterval 不过，这里所说的短语并不是语言学上的短语，本身也没有任何语言学句法的结构约束。在基于短语的模型中，可以把短语简单地理解为一个词串。具体来说，有如下定义。

%-------------------------------------------
\begin{definition} 短语

{\small
对于一个句子$\mathbf{w} = w_1...w_n$，任意子串$w_i...w_j$($i\leq j$且$0\leq i,j\leq n$)都是句子$\mathbf{w}$的一个{\small\bfnew{短语}}。
}
\end{definition}
%-------------------------------------------

\parinterval 根据这个定义，对于一个由$n$个单词构成的句子，可以包含$\frac{n(n-1)}{2}$个短语（子串）。进一步，可以把每个句子看作是由一系列短语构成的序列。组成这个句子的短语序列也可以被看作是句子的一个{\small\bfnew{短语切分}}\index{短语切分}（Phrasal Segmentation）\index{Phrasal Segmentation}。

%-------------------------------------------
\vspace{0.5em}
\begin{definition} 句子的短语切分

{\small
如果一个句子$\mathbf{w} = w_1...w_n$可以被切分为$m$个子串，则称$\mathbf{w}$由$m$个短语组成，记为$\mathbf{w} = p_1...p_m$，其中$p_i$是$\mathbf{w}$的一个短语，$p_1...p_m$也被称作句子$\mathbf{w}$的一个{\small\bfnew{短语切分}}。
}
\end{definition}
%-------------------------------------------

\parinterval 比如，对于一个句子，``$\text{机器}\ \text{翻译}\ \text{是}\ \text{一}\ \text{项}\ \text{很}\ \text{有}\ \text{挑战}\ \text{的}\ \text{问题}$''，一种可能的短语切分为：
\begin{eqnarray}
p_1 &=& \text{机器}\ \text{翻译} \nonumber \\
p_2 &=& \text{是}\ \text{一}\ \text{项} \nonumber \\
p_3 &=& \text{很有}\ \text{挑战}\ \text{的} \nonumber \\
p_4 &=& \text{问题}\nonumber
\end{eqnarray}

\parinterval 进一步，把单语短语的概念推广到双语的情况：

%-------------------------------------------
\vspace{0.5em}
\begin{definition} 双语短语（或短语对）

{\small
对于源语和目标语句对($\mathbf{s}$,$\mathbf{t}$)，$\mathbf{s}$中的一个短语$\bar{s}_i$和$\mathbf{t}$中的一个短语$\bar{t}_j$可以构成一个双语短语对($\bar{s}_i,\bar{t}_j$)，简称{\small\bfnew{短语对}}\index{短语对}($\bar{s}_i,\bar{t}_j$)。
}
\end{definition}
%-------------------------------------------

\parinterval 也就是说，源语言句子中任意的短语和目标语言句子中任意的短语都构成一个双语短语。这里用$\leftrightarrow$表示互译关系。对于一个双语句对``进口\ 大幅度\ 下降\ 了 $\leftrightarrow$ the imports have drastically fallen''，可以得到很多双语短语，比如：
\begin{eqnarray}
&&\text{大幅度}\ \leftrightarrow\ \textrm{drastically} \nonumber \\
&&\text{大幅度}\ \ \text{下降}\ \leftrightarrow\ \textrm{have}\ \textrm{drastically}\ \textrm{fallen} \nonumber \\
&&\text{进口}\ \ \text{大幅度}\ \leftrightarrow\ \textrm{imports}\ \textrm{have}\ \textrm{drastically} \nonumber \\
&&\text{大幅度}\ \ \text{下降}\ \ \text{了}\ \leftrightarrow\ \textrm{drastically}\ \textrm{fallen} \nonumber \\
&&\text{了}\ \leftrightarrow\ \textrm{have}\ \textrm{drastically} \nonumber \\
&&... \nonumber
\end{eqnarray}

\parinterval 接下来的问题是，如何使用双语短语描述双语句子的生成，即句子翻译的建模问题。在基于词的翻译模型里，可以用词对齐来描述双语句子的对应关系。类似的，也可以使用双语短语描述句子的翻译。这里，借用形式文法中{\small\bfnew{推导}}\index{推导}（Derivation）\index{Derivation}的概念。把生成双语句对的过程定义为一个基于短语的翻译推导：

%-------------------------------------------
\vspace{0.5em}
\begin{definition} 基于短语的翻译推导

{\small
对于源语言和目标语言句对($\mathbf{s}, \mathbf{t}$)，分别有短语切分$\{\bar{s}_i\}$和$\{\bar{t}_j\}$，且$\{\bar{s}_i\}$和$\{\bar{t}_j\}$之间存在一一对应的关系。令$\{\bar{a}_j\}$表示$\{\bar{t}_j\}$ 中每个短语对应到源语言短语的编号，则称短语对$\{(\bar{s}_{\bar{a}_j},\bar{t}_j)\}$构成了$\mathbf{s}$到$\mathbf{t}$的{\small\bfnew{基于短语的翻译推导}}(简称推导)，记为$d(\{(\bar{s}_{\bar{a}_j},\bar{t}_j)\},\mathbf{s},\mathbf{t})$(简记为$d(\{(\bar{s}_{\bar{a}_j},\bar{t}_j)\})$或$d$)。
}
\end{definition}
%-------------------------------------------

\parinterval 基于短语的翻译推导定义了一种从源语言短语序列到目标语言短语序列的对应，其中源语言短语序列是源语言句子的一种切分，同样的，目标语言短语序列是目标语言句子的一种切分。翻译推导提供了一种描述翻译过程的手段：对于一个源语言句子，可以找到从它出发的翻译推导，推导中短语的目标语部分就构成了译文。也就是，每个源语言句子$\mathbf{s}$上的一个推导$d$都蕴含着一个目标语句子$\mathbf{t}$。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-derivation-consist-of-bilingual-phrase}
\caption{三个双语短语$\{(\bar{s}_{\bar{a}_1},\bar{t}_1),(\bar{s}_{\bar{a}_2},\bar{t}_2),(\bar{s}_{\bar{a}_3},\bar{t}_3)\}$构成的翻译推导}
\label{fig:7-10}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:7-10}给出了一个由三个双语短语$\{(\bar{s}_{\bar{a}_1},\bar{t}_1),(\bar{s}_{\bar{a}_2},\bar{t}_2),(\bar{s}_{\bar{a}_3},\bar{t}_3)\}$ 构成的汉英互译句对，其中短语对齐信息为$\bar{a}_1 = 1$，$\bar{a}_2 = 2$，$\bar{a}_3 = 3$。这里，可以把这三个短语对的组合看作是翻译推导，形式化表示为如下公式。其中，${} \circ $表示短语的组合\footnote[2]{短语的组合是指将两个短语a和b进行拼接，形成新的短语ab。在机器翻译中，可以把双语短语的组合看作是对目标语短语的组合。比如，对于两个双语短语$(\bar{s}_{\bar{a}_1},\bar{t}_1),(\bar{s}_{\bar{a}_2},\bar{t}_2)$，短语的组合表示将$\bar{t}_1$和$\bar{t}_2$进行组合，而源语言端作为输入已经给定，因此直接匹配源语言句子中相应的部分即可。根据两个短语在源语言中位置的不同，通常又分为顺序翻译、反序翻译、不连续翻译。关于这部分内容将会在后面\ref{subsection-7.4}节调序模型的部分进行介绍。}。
\begin{eqnarray}
d = {(\bar{s}_{\bar{a}_1},\bar{t}_1)} \circ {(\bar{s}_{\bar{a}_2},\bar{t}_2)} \circ {(\bar{s}_{\bar{a}_3},\bar{t}_3)}
\label{eq:7-1}
\end{eqnarray}

\parinterval 到此为止，就得到了一个基于短语的翻译模型。对于每个双语句对($\mathbf{s}, \mathbf{t}$)，每个翻译推导$d$都对应了一个基于短语的翻译过程。而基于短语的机器翻译的目标就是对$d$进行描述。有四个基本问题：

\begin{itemize}
\vspace{0.5em}
\item 如何用统计模型描述每个翻译推导的好坏\ \dash \ 即翻译的统计建模问题；
\vspace{0.5em}
\item 如何获得可使用的双语短语对\ \dash \ 即短语翻译获取问题；
\vspace{0.5em}
\item 如何对翻译中的调序问题进行建模\ \dash \ 即调序问题；
\vspace{0.5em}
\item 如何找到输入句子$\mathbf{s}$的最佳译文\ \dash \ 即解码问题。
\vspace{0.5em}
\end{itemize}

\parinterval 这四个问题也构成了基于短语的翻译模型的核心，下面对其逐一展开讨论。

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------
\sectionnewpage
\section{数学建模}\label{section-7.2}

\parinterval 对于统计机器翻译，其目的是找到输入句子的可能性最大的译文：
\begin{eqnarray}
\hat{\mathbf{t}} = \argmax_{\mathbf{t}} \textrm{P}(\mathbf{t}|\mathbf{s})
\label{eq:7-2}
\end{eqnarray}

\parinterval 公式\ref{eq:7-2}中，$\mathbf{s}$是输入的源语言句子，$\mathbf{t}$是一个目标语译文。$\textrm{P}(\mathbf{t}|\mathbf{s})$被称为翻译模型，它描述了把$\mathbf{s}$翻译为$\mathbf{t}$的可能性。通过$\argmax \textrm{P}(\mathbf{t}|\mathbf{s})$可以找到使$\textrm{P}(\mathbf{t}|\mathbf{s})$达到最大的$\mathbf{t}$。

\parinterval 这里的第一个问题是如何定义$\textrm{P}(\mathbf{t}|\mathbf{s})$。直接描述$\textrm{P}(\mathbf{t}|\mathbf{s})$是非常困难的，因为$\mathbf{s}$和$\mathbf{t}$分别对应了巨大的样本空间，而在训练数据中能观测到的只是空间中的一小部分样本。直接用有限的训练数据描述这两个空间中样本的对应关系会面临着严重的数据稀疏问题。对于这个问题，常用的解决办法是把复杂的问题转化为容易计算的简单问题。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{基于翻译推导的建模}

\parinterval 基于短语的翻译模型假设$\mathbf{s}$到$\mathbf{t}$的翻译可以用翻译推导进行描述，这些翻译推导都是由双语短语组成。于是，两个句子之间的映射就可以被看作是一个个短语的映射。显然短语翻译的建模要比整个句子翻译的建模简单得多。从模型上看，可以把翻译推导$d$当作是从$\mathbf{s}$到$\mathbf{t}$翻译的一种隐含结构。这种结构定义了对问题的一种描述，即翻译由一系列短语组成。根据这个假设，可以把句子的翻译概率定义为：
\begin{eqnarray}
\textrm{P}(\mathbf{t}|\mathbf{s}) = \sum_{d} \textrm{P}(d,\mathbf{t}|\mathbf{s})
\label{eq:7-3}
\end{eqnarray}


\parinterval 公式\ref{eq:7-3}中，$\textrm{P}(d,\mathbf{t}|\mathbf{s})$表示翻译推导的概率。公式\ref{eq:7-3}把翻译问题转化为翻译推导的生成问题。但是，由于翻译推导的数量十分巨大\footnote[3]{如果把推导看作是一种树结构，推导的数量与词串的长度成指数关系。}，公式\ref{eq:7-3}的右端需要对所有可能的推导进行枚举并求和，这几乎是无法计算的。

\parinterval 对于这个问题，常用的解决办法是利用一个化简的模型来近似完整的模型。如果把翻译推导的全体看作一个空间$D$，可以从$D$中选取一部分样本参与计算，而不是对整个$D$进行计算。比如，可以用最好的$n$个翻译推导来代表整个空间$D$。令$D_{n\textrm{-best}}$表示最好的$n$个翻译推导所构成的空间，于是可以定义：
\begin{eqnarray}
\textrm{P}(\mathbf{t}|\mathbf{s}) \approx \sum_{d \in D_{n\textrm{-best}}} \textrm{P}(d,\mathbf{t}|\mathbf{s})
\label{eq:7-4}
\end{eqnarray}

\parinterval 进一步，把公式\ref{eq:7-4}带入公式\ref{eq:7-2}，可以得到翻译的目标为：
\begin{eqnarray}
\hat{\mathbf{t}} = \arg\max_{\mathbf{t}} \sum_{d \in D_{n\textrm{-best}}} \textrm{P}(d,\mathbf{t}|\mathbf{s})
\label{eq:7-5}
\end{eqnarray}

\parinterval 另一种常用的方法是直接用$\textrm{P}(d,\mathbf{t}|\mathbf{s})$的最大值代表整个翻译推导的概率和。这种方法假设翻译概率是非常尖锐的，``最好''的推导会占有概率的主要部分。它被形式化为：
\begin{eqnarray}
\textrm{P}(\mathbf{t}|\mathbf{s}) \approx \max \textrm{P}(d,\mathbf{t}|\mathbf{s})
\label{eq:7-6}
\end{eqnarray}

\parinterval 于是，翻译的目标可以被重新定义：
\begin{eqnarray}
\hat{\mathbf{t}} = \arg\max_{\mathbf{t}} (\max \textrm{P}(d,\mathbf{t}|\mathbf{s}))
\label{eq:7-7}
\end{eqnarray}

\parinterval 值得注意的是，翻译推导中蕴含着译文的信息，因此每个翻译推导都与一个译文对应。因此可以把公式\ref{eq:7-7}所描述的问题重新定义为：
\begin{eqnarray}
\hat{d} = \arg\max_{d} \textrm{P}(d,\mathbf{t}|\mathbf{s})
\label{eq:7-8}
\end{eqnarray}

\parinterval 也就是，给定一个输入句子$\mathbf{s}$，找到从它出发的最优翻译推导$\hat{d}$，把这个翻译推导所对应的目标语词串看作最优的译文。假设函数$t(\cdot)$可以返回一个推导的目标语词串，则最优译文也可以被看作是：
\begin{eqnarray}
\hat{\mathbf{t}} = t(\hat{d})
\label{eq:7-9}
\end{eqnarray}

\parinterval 注意，公式\ref{eq:7-8}-\ref{eq:7-9}和公式\ref{eq:7-7}本质上是一样的。它们也构成了统计机器翻译中最常用的方法\ \dash \ Viterbi方法\cite{DBLP:journals/tit/Viterbi67}。在后面机器翻译的解码中还会看到它们的应用。而公式\ref{eq:7-5}也被称作$n$-best方法，常常作为Viterbi方法的一种改进。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{对数线性模型}

\parinterval 对于如何定义$\textrm{P}(d,\mathbf{t}|\mathbf{s})$有很多种思路，比如，可以把$d$拆解为若干步骤，然后对这些步骤分别建模，最后形成描述$d$的{\small\bfnew{生成式模型}}\index{生成式模型}（Generative Model）\index{Generative Model}。这种方法在第三章的IBM模型中也大量使用。但是，生成式模型的每一步推导需要有严格的概率解释，这也限制了研究人员从更多的角度对$d$进行描述。这里，可以使用另外一种方法\ \dash \ {\small\bfnew{判别式模型}}\index{判别式模型}（Discriminative Model）\index{Discriminative Model}来对$\textrm{P}(d,\mathbf{t}|\mathbf{s})$进行描述\cite{DBLP:conf/acl/OchN02}。其模型形式如下：
\begin{eqnarray}
\textrm{P}(d,\mathbf{t}|\mathbf{s}) &=& \frac{\textrm{exp}(\textrm{score}(d,\mathbf{t},\mathbf{s}))}{\sum_{d',\mathbf{t}'} \textrm{exp}(\textrm{score}(d',\mathbf{t}',\mathbf{s}))} \label{eqa4.10} \\
\textrm{score}(d,\mathbf{t},\mathbf{s}) &=& \sum_{i=1}^{M} \lambda_i \cdot h_i (d,\mathbf{t},\mathbf{s})
\label{eq:7-11}
\end{eqnarray}

\parinterval 公式\ref{eq:7-11}是一种典型的{\small\bfnew{对数线性模型}}\index{对数线性模型}（Log-linear Model）\index{Log-linear Model}。所谓``对数线性''体现在对多个量求和后进行指数运算（$\textrm{exp}(\cdot)$），这相当于对多个因素进行乘法。公式\ref{eqa4.10}的右端是一种归一化操作。分子部分可以被看作是一种对翻译推导$d$的对数线性建模。具体来说，对于每个$d$，用$M$个特征对其进行描述，每个特征用函数$h_i (d,\mathbf{t},\mathbf{s})$表示。每个特征都对应一个权重$\lambda_i$，表示特征$i$的重要性。$\sum_{i=1}^{M} \lambda_i \cdot h_i (d,\mathbf{t},\mathbf{s})$表示了对这些特征的线性加权和，值越大表示模型得分越高，相应的$d$和$\mathbf{t}$的质量越高。公式\ref{eqa4.10}的分母部分实际上不需要计算，因为其值与求解最佳推导的过程无关。把公式\ref{eqa4.10}带入公式\ref{eq:7-8}得到：
\begin{eqnarray}
\hat{d} &=& \arg\max_{d} \frac{\textrm{exp}(\textrm{score}(d,\mathbf{t},\mathbf{s}))}{\sum_{d',\mathbf{t}'} \textrm{exp}(\textrm{score}(d',\mathbf{t}',\mathbf{s}))} \nonumber \\
&=& \arg\max_{d}\ \textrm{exp}(\textrm{score}(d,\mathbf{t},\mathbf{s}))
\label{eq:7-12}
\end{eqnarray}

\parinterval 公式\ref{eq:7-12}中，$\ \textrm{exp}(\textrm{score}(d,\mathbf{t},\mathbf{s}))$表示指数化的模型得分，记为$\textrm{mscore}(d,\mathbf{t},\mathbf{s}) = \textrm{exp}(\textrm{score}(d,\mathbf{t},\mathbf{s}))$。于是，翻译问题就可以被描述为找到使函数$\textrm{mscore}(d,\mathbf{t},\mathbf{s})$达到最大的$d$。由于，$\textrm{exp}(\textrm{score}(d,\mathbf{t},\mathbf{s}))$和$\textrm{score}(d,\mathbf{t},\mathbf{s})$是单调一致的，因此有时也直接把$\textrm{score}(d,\mathbf{t},\mathbf{s})$当做模型得分。

\parinterval 判别式模型最大的好处在于它可以更灵活地引入特征。系统开发者可以设计任意的特征来描述翻译，特征的设计甚至都不需要统计上的解释，比如0-1特征、计数特征等。此外，判别式模型并不需要像生成式模型那样对问题进行具有统计学意义的``分解''，更不需要对每个步骤进行严格的数学推导。相反，它直接对问题的后验概率进行建模。由于不像生成式模型那样需要引入假设来对每个生成步骤进行化简，判别式模型对问题的刻画更加直接，因此也受到自然语言处理研究者的青睐。
%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{机器翻译中的特征}






%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{搭建模型的基本流程}

\parinterval 对于翻译的判别式建模，需要回答两个问题：

\begin{itemize}
\vspace{0.5em}
\item 如何设计特征函数$\{h_i(d,\mathbf{t}|\mathbf{s})\}$?
\vspace{0.5em}
\item 如何获得最好的特征权重$\{\lambda_i\}$?
\vspace{0.5em}
\end{itemize}

在基于短语的翻译模型中，通常包含三类特征：短语翻译特征、调序特征、语言模型相关的特征。这些特征都需要从训练数据中学习。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-process-of-machine-translation-base-phrase}
\caption{基于短语的机器翻译的系统流程}
\label{fig:7-11}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:7-11}展示了一个基于短语的机器翻译模型的搭建流程。其中的训练数据包括双语平行语料和目标语言单语语料。首先，需要从双语平行数据中学习短语的翻译，并形成一个短语翻译表；然后，再从双语平行数据中学习调序模型；最后，从目标语单语数据中学习语言模型。短语翻译表、调序模型、语言模型都会作为特征被送入判别式模型，由解码器完成对新句子的翻译。而这些特征的权重可以在额外的开发集上进行调优。关于短语翻译、调序模型和特征权重的学习，会在本章的\ref{subsection-4.2.3}-\ref{subsection-4.2.6}节进行介绍。

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\sectionnewpage
\section{短语抽取}\label{subsection-4.2.3}

\parinterval 在基于短语的模型中，学习短语翻译是重要的步骤之一。获得短语翻译的方法有很多种，最常用的方法是从双语平行语料中进行{\small\bfnew{短语抽取}}\index{短语抽取}（Phrase Extraction）\index{Phrase Extraction}。前面已经介绍过短语的概念，句子中任意的连续子串都被称为短语。例如在图\ref{fig:7-12}中，用点阵的形式来表示双语之间的对应关系，那么图中任意一个矩形框都可以构成一个双语短语（或短语对），例如``什么\ 都\ 没''对应``learned nothing ？''。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-unlimited-phrase-extraction}
\caption{无限制的短语抽取}
\label{fig:7-12}
\end{figure}
%-------------------------------------------

\parinterval 按照上述抽取短语的方式可以找到所有可能的双语短语，但是这种不加限制的抽取是非常十分低效的。一是可抽取的短语数量爆炸，二是抽取得到的大部分短语是没有意义的，如上面的例子中抽取到``到\ ？''对应``Have you learned nothing？''这样的短语对在翻译中并没有什么意义。对于这个问题，一种解决方法是基于词对齐进行短语抽取，或者是抽取与词对齐相一致的短语。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{与词对齐一致的短语}

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-phrase-extraction-consistent-with-word-alignment}
\caption{与词对齐一致的短语抽取}
\label{fig:7-13}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:7-13}中大蓝色方块代表词对齐。通过词对齐信息，可以很容易地获得双语短语``天气 $\leftrightarrow$ The weather''。这里称其为与词对齐一致（兼容）的双语短语。具体定义如下：

%-------------------------------------------
\vspace{0.5em}
\begin{definition} 与词对齐一致（兼容）的双语短语

{\small
对于源语言句子$\mathbf{s}$和目标语句子$\mathbf{t}$，存在$\mathbf{s}$和$\mathbf{t}$之间的词对齐。如果有$(\mathbf{s},\mathbf{t})$中的双语短语$(\bar{s},\bar{t})$，且$\bar{s}$中所有单词仅对齐到$\bar{t}$中的单词，同时$\bar{t}$中所有单词仅对齐到$\bar{s}$中的单词，那么称$(\bar{s},\bar{t})$与是与词对齐一致的（兼容的）双语短语。
}
\end{definition}
%-------------------------------------------

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-consistence-of-word-alignment}
\caption{词对齐一致性}
\label{fig:7-14}
\end{figure}
%-------------------------------------------

\parinterval 如图\ref{fig:7-14}所示，左边的例子中的$t_1$和$t_2$严格地对应到$s_1$、$s_2$、$s_3$，所以短语是与词对齐相一致的；中间的例子中的$t_2$对应到短语$s_1$和$s_2$的外面，所以短语是与词对齐不一致的；类似的，右边的例子也是与词对齐相一致的短语。

\parinterval 图\ref{fig:7-15}展示了与词对齐一致的短语抽取过程，首先判断抽取得到的双语短语是否与词对齐保持一致，若一致，则抽取出来。在实际抽取过程中，通常需要对短语的最大长度进行限制，以免抽取过多的无用短语。比如，在实际系统中，最大短语长度一般是5-7个词。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-phrase-extraction-consistent-with-word-alignment-1}
\caption{与词对齐一致的短语抽取}
\label{fig:7-15}
\end{figure}
%-------------------------------------------

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{获取词对齐}

\parinterval 如何获得词对齐呢？上一章介绍的IBM模型本身就是一个词对齐模型，因此一种常用的方法是直接使用IBM模型生成词对齐。IBM模型约定每个源语言单词必须对应、也只能对应到一个目标语单词。因此，IBM 模型得到的词对齐结果是不对称的。正常情况下词对齐可以是一个源语言单词对应多个目标语言单词，或者多对一，甚至多对多的情况。为了获得对称的词对齐，一种简单的方法是，分别进行正向翻译和反向翻译的词对齐，然后利用启发性方法生成对称的词对齐，例如，双向词对齐取交集、并集等。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-get-word-alignment}
\caption{词对齐的获取}
\label{fig:7-16}
\end{figure}
%-------------------------------------------

\parinterval 如图\ref{fig:7-16}中，左边两个图就是正向和反向两种词对齐的结果。右边的图是融合双向词对齐的结果，取交集是蓝色的方框，取并集是红色的方框。当然，还可以设计更多的启发性规则生成词对齐\cite{koehn2000estimating,koehn2007factored}。

\parinterval 除此之外，一些外部工具也可以用来获取词对齐，如Fastalign\cite{dyer2013a}、Berkeley Word Aligner\cite{taskar2005a}等。词对齐的质量通常使用词对齐错误率（AER）来评价\cite{DBLP:conf/coling/OchN00}。但是词对齐并不是一个独立的系统，它一般会服务于其他任务。因此，也可以使用下游任务来评价词对齐的好坏。比如，改进词对齐后观察机器翻译系统性能的变化。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{度量双语短语质量}

\parinterval 抽取双语短语之后，需要对每个双语短语的质量进行评价。这样，在使用这些双语短语时，可以更有效地估计整个句子翻译的好坏。在统计机器翻译中，一般用双语短语出现的可能性大小来度量双语短语的好坏。这里，使用相对频度估计对短语的翻译条件概率进行计算，公式如下：
\begin{eqnarray}
\textrm{P}(\bar{t}|\bar{s}) = \frac{\textrm{count}(\bar{s},\bar{t})}{\textrm{count}(\bar{s})}
\label{eq:7-13}
\end{eqnarray}

\parinterval 给定一个双语句对$(\mathbf{s},\mathbf{t})$，$\textrm{count}(\bar{s})$表示短语$\bar{s}$在$\mathbf{s}$中出现的次数，$\textrm{count}(\bar{s},\bar{t})$表示双语短语$(\bar{s},\bar{t})$在$(\mathbf{s},\mathbf{t})$中被抽取出来的次数。对于一个包含多个句子的语料库，$\textrm{count}(\bar{s})$和$\textrm{count}(\bar{s},\bar{t})$可以按句子进行累加。类似的，也可以用同样的方法，计算$\bar{t}$到$\bar{s}$的翻译概率，即$\textrm{P}(\bar{s}|\bar{t})$。一般会同时使用$\textrm{P}(\bar{t}|\bar{s})$和$\textrm{P}(\bar{s}|\bar{t})$度量一个双语短语的好与坏。

\parinterval 当遇到低频短语时，短语翻译概率的估计可能会不准确。例如，短语$\bar{s}$和$\bar{t}$在语料中只出现了一次，且在一个句子中共现，那么$\bar{s}$到$\bar{t}$的翻译概率为$\textrm{P}(\bar{t}|\bar{s})=1$，这显然是不合理的，因为$\bar{s}$和$\bar{t}$的出现完全可能是偶然事件。既然直接度量双语短语的好坏会面临数据稀疏问题，一个自然的想法就是把短语拆解成单词，利用双语短语中单词翻译的好坏间接度量双语短语的好坏。为了达到这个目的，可以使用{\small\bfnew{词汇化翻译概率}}\index{词汇化翻译概率}（Lexical Translation Probability）\index{Lexical Translation Probability}。前面借助词对齐信息完成了双语短语的抽取，因此，词对齐信息本身就包含了短语内部单词之间的对应关系。因此同样可以借助词对齐来计算词汇翻译概率，公式如下：
\begin{eqnarray}
\textrm{$\textrm{P}_{\textrm{lex}}$}(\bar{t}|\bar{s}) = \prod_{j=1}^{|\bar{s}|} \frac{1}{|\{j|a(j,i) = 1\}|} \sum_{\forall(j,i):a(j,i) = 1} w(t_i|s_j)
\label{eq:7-14}
\end{eqnarray}

\parinterval 它表达的意思是短语$\bar{s}$和$\bar{t}$存在词汇级的对应关系，其中$w$表示词汇翻译概率用来度量两个单词之间翻译的可能性大小（见第三章），作为两个词之间对应的强度。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-example-of-vocabulary-translation-probability}
\caption{词汇翻译概率实例}
\label{fig:7-17}
\end{figure}
%-------------------------------------------

\parinterval 下面来看一个具体的例子，如图\ref{fig:7-17}所示。对于一个双语短语，将它们的词对齐关系代入到上面的公式就会得到短语的词汇翻译概率。对于词汇翻译概率，可以使用IBM 模型中的单词翻译表，也可以通过统计获得\cite{koehn2002learning}。如果一个单词的词对齐为空，则用$N$表示它翻译为空的概率。和短语翻译概率一样，可以使用双向的词汇化翻译概率来评价双语短语的好坏。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-example-of-phrase-table}
\caption{短语表实例}
\label{fig:7-18}
\end{figure}
%-------------------------------------------

\parinterval 经过上面的介绍，可以从双语平行语料中把双语短语抽取出来，同时得到相应的翻译概率（即特征），组成{\small\bfnew{短语表}}\index{短语表}（Phrase Table）\index{Phrase Table}。图\ref{fig:7-18}展示了一个真实短语表的片段。其中包括源语言短语和目标语言短语，用|||进行分割。每个双语对应的得分，包括正向和反向的词汇翻译概率以及短语翻译概率，还包括词对齐信息（0-0、1-1）等其他信息。

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------
\sectionnewpage
\section{翻译调序建模}\label{subsection-7.4}

\parinterval 尽管已经知道了如何将一个源语言短语翻译成目标语言短语，但是想要获得一个高质量的译文，仅有互译的双语短语是远远不够的。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-reorder-base-phrase-translation}
\caption{基于短语翻译的调序}
\label{fig:7-19}
\end{figure}
%-------------------------------------------

\parinterval 如图\ref{fig:7-19}所示，按照从左到右的顺序对一个句子``在\ \ 桌子\ \ 上\ \ 的\ \ 苹果''进行翻译，得到的译文``on the table the apple''的语序是不对的。虽然可以使用$n$-gram语言模型对语序进行建模，但是此处仍然需要用更加准确的方式描述目标语短语间的次序。一般，把这个问题称为短语调序，或者简称{\small\bfnew{调序}}\index{调序}（Reordering）\index{Reordering}。通常，基于短语的调序模型会作为判别式模型的特征参与到翻译过程中来。接下来，会介绍3 种不同的调序方法，分别是基于距离的调序、基于方向的调序（MSD模型）以及基于分类的调序。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{基于距离的调序}

\parinterval 基于距离的调序是最简单的一种调序模型。很多时候，语言的翻译基本上都是顺序的，也就是，译文单词出现的顺序和源语言单词的顺序基本上是一致的。反过来说，如果译文和源语言单词（或短语）的顺序差别很大，就认为出现了调序。

\parinterval 基于距离的调序方法的核心思想就是度量当前翻译结果与顺序翻译之间的差距。对于译文中的第$i$个短语，令$start_i$表示它所对应的源语言短语中第一个词所在的位置，$end_i$表示它所对应的源语言短语中最后一个词所在的位置。于是，这个短语（相对于前一个短语）的调序距离为：
\begin{eqnarray}
dr = start_i-end_{i-1}-1
\label{eq:7-15}
\end{eqnarray}

\parinterval 在图\ref{fig:7-20}的例子中，``the apple''所对应的调序距离为4，``on the table''所对应的调序距离为-5。显然，如果两个源语短语按顺序翻译，则$start_i = end_{i-1} + 1$，这时调序距离为0。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-reorder-base-distance}
\caption{基于距离的调序}
\label{fig:7-20}
\end{figure}
%-------------------------------------------

\parinterval 如果把调序距离作为特征，一般会使用指数函数$f(dr) = a^{|dr|}$作为特征函数（或者调序代价的函数），其中$a$是一个参数，控制调序距离对整个特征值的影响。调序距离$dr$的绝对值越大，调序代价越高。基于距离的调序模型比较适用于像法–英翻译这样的任务，因为两种语言的语序基本上是一致的。但是，对于汉–日翻译，由于句子结构存在很大差异（日语是谓词后置，而汉语中谓词放在宾语前），使用基于距离的调序会带来一些问题。因此，具体应用时应该根据语言之间的差异性有选择的使用该模型。

%----------------------------------------------------------------------------------------
%    NEW SUBSUB-SECTION
%----------------------------------------------------------------------------------------

\subsubsection{基于方向的调序}

\parinterval 基于方向的调序模型是另一种常用的调序模型。该模型是一种典型的词汇化调序模型，因此调序的结果会根据不同短语有所不同。简单来说，在目标语言端连续的情况下，该模型会判断两个双语短语在源语言端的调序情况，包含三种调序类型：顺序的单调翻译（M）、与前一个短语交换位置（S）、非连续翻译（D）。因此，这个模型也被称作MSD调序模型\cite{Gros2008MSD}。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-three-types-of-reorder-method-in-msd}
\caption{词汇化调序模型的三种调序类型}
\label{fig:7-21}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:7-21}展示了这三种调序类型，当两个短语对在源语言和目标语言中都是按顺序排列时，它们就是单调的（如：从左边数前两个短语）；如果对应的短语顺序在目标语中是反过来的，属于交换调序（如：从左边数第三和第四个短语）；如果两个短语之间还有其他的短语，就是非连续翻译（如：从右边数的前两个短语）。

\parinterval 对于每种调序类型，都可以定义一个调序概率，如下：
\begin{eqnarray}
\textrm{P}(\mathbf{o}|\mathbf{s},\mathbf{t},\mathbf{a}) = \prod_{i=1}^{K} \textrm{P}(o_i| \bar{s}_{a_i}, \bar{t}_i, a_{i-1}, a_i)
\label{eq:7-16}
\end{eqnarray}

\noindent 其中，$o_i$表示（目标语言）第$i$个短语的调序方向，$\mathbf{o}=\{o_i\}$表示短语序列的调序方向，$K$表示短语的数量。短语之间的调序概率是由双语短语以及短语对齐决定的，$o$表示调序的种类，可以取M、S、D 中的任意一种。而整个句子调序的好坏就是把相邻的短语之间的调序概率相乘（对应取log后的加法）。这样，公式\ref{eq:7-16}把调序的好坏定义为新的特征，对于M、S、D总共就有三个特征。除了当前短语和前一个短语的调序特征，还可以定义当前短语和后一个短语的调序特征，即将上述公式中的$a_{i-1}$换成$a_{i+1}$。 于是，又可以得到三个特征。因此在MSD调序中总共可以有6个特征。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-judge-type-of-reorder-method}
\caption{调序类型的判断}
\label{fig:7-22}
\end{figure}
%-------------------------------------------

\parinterval 具体实现时，通常使用词对齐对两个短语间的调序关系进行判断。图\ref{fig:7-22}展示了这个过程。先判断短语的左上角和右上角是否存在词对齐，再根据其位置对调序类型进行划分。每个短语对应的调序概率都可以用相对频率估计进行计算。而MSD调序模型也相当于在短语表中的每个双语短语后添加6个特征。不过，调序模型一般并不会和短语表一起存储，因此在系统中通常会看到两个独立的模型文件，分别保存短语表和调序模型。

%----------------------------------------------------------------------------------------
%    NEW SUBSUB-SECTION
%----------------------------------------------------------------------------------------

\subsubsection{基于分类的调序}

\parinterval 在MSD调序中，双语短语所对应的调序概率$\textrm{P}(o_i| \bar{s}_{a_i}, \bar{t}_i, a_{i-1}, a_i)$是用极大似然估计方法进行计算的。但是，这种方法也会面临数据稀疏问题，同时对调序产生影响的细致特征也没有考虑进来。另一种有效的方法是直接用统计分类模型对调序进行建模，比如，可以使用最大熵、SVM等分类器输出调序概率或者得分\cite{xiong2006maximum,DBLP:journals/coling/OchN04,DBLP:conf/naacl/KumarB05}。对于基于分类的调序模型，有两方面问题需要考虑：

\begin{itemize}
\vspace{0.5em}
\item 训练样本的生成。可以把M、S、D看作是类别标签，把所对应的短语及短语对齐信息看作是输入。这样就得到了大量分类器训练所需的样本；
\vspace{0.5em}
\item 分类特征设计。这部分是传统统计机器学习中的重要组成部分，好的特征会对分类结果产生很大影响。在调序模型中，一般直接使用单词作为特征，比如用短语的第一个单词和最后一个单词作为特征就可以达到很好的效果。
\vspace{0.5em}
\end{itemize}

\parinterval 随着神经网络方法的兴起，也可以考虑使用多层神经网络构建调序模型\cite{li-etal-2014-neural}。这时，可以把短语直接送入一个神经网络，之后由神经网络完成对特征的抽取和表示，并输出最终的调序模型得分。

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------
\sectionnewpage
\section{翻译特征}

\parinterval 基于短语的模型使用判别式模型对翻译推导进行建模，给定双语句对$(\mathbf{s},\mathbf{t})$，每个翻译推导$d$都有一个模型得分，由$M$个特征线性加权得到，记为$\textrm{score}(d,\mathbf{t},\mathbf{s}) = \sum_{i=1}^{M} \lambda_i \cdot h_i (d,\mathbf{t},\mathbf{s})$，其中$\lambda_i$表示特征权重，$h_i (d,\mathbf{t},\mathbf{s})$表示特征函数（简记为$h_i (d)$）。这些特征包含刚刚介绍过的短语翻译概率、调序模型得分等，除此之外，还包含语言模型等其他特征，它们共同组成了特征集合。这里列出了基于短语的模型中常用的特征：

\begin{itemize}
\vspace{0.5em}
\item 短语翻译概率（取对数），包含正向翻译概率$\textrm{log}(\textrm{P}(\bar{t}|\bar{s}))$和反向翻译概率$\textrm{log}(\textrm{P}(\bar{s}$\\$|\bar{t}))$，它们是基于短语的模型中最主要的特征；
\vspace{0.5em}
\item 词汇化翻译概率（取对数），同样包含正向词汇化翻译概率$\textrm{log(P}_{\textrm{lex}}(\bar{t}|\bar{s}\textrm{))}$和反向词汇化翻译概率$\textrm{log(P}_{\textrm{lex}}(\bar{s}|\bar{t}\textrm{))}$，它们用来描述双语短语中单词间对应的好坏；
\vspace{0.5em}
\item $n$-gram语言模型，用来度量译文的流畅程度，可以通过大规模目标端单语数据得到；
\vspace{0.5em}
\item 译文长度，避免模型倾向于短译文，同时让系统自动学习对译文长度的偏好；
\vspace{0.5em}
\item 翻译规则数量，为了避免模型仅使用少量特征构成翻译推导（规则数量少，短语翻译概率相乘的因子也会少，得分一般会大一些），同时让系统自动学习对规则数量的偏好；
\vspace{0.5em}
\item 被翻译为空的源语言单词数量。注意，空翻译规则有时也被称作evil feature，这类特征在一些数据上对BLEU有很好的提升作用，但会造成人工评价结果的下降，需要谨慎使用；
\vspace{0.5em}
\item 基于MSD的调序模型，包括与前一个短语的调序模型$f_{\textrm{M-pre}}(d)$\ 、$f_{\textrm{S-pre}}(d)$\ 、$f_{\textrm{D-pre}}(d)$和与后一个短语的调序模型$f_{\textrm{M-fol}}(d)$\ 、$f_{\textrm{S-fol}}(d)$\ 、$f_{\textrm{D-fol}}(d)$，共6个特征。
\vspace{0.5em}
\end{itemize}

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\sectionnewpage
\subsection{最小错误率训练}\label{subsection-4.2.6}

\parinterval 除了特征设计，统计机器翻译也需要找到每个特征所对应的最优权重$\lambda_i$。这也就是机器学习中所说的模型训练问题。不过，需要指出的是，统计机器翻译关于模型训练的定义与传统机器学习稍有不同。在统计机器翻译中，短语抽取和翻译概率的估计被看作是{\small\bfnew{模型训练}}\index{模型训练}（Model Training）\index{Model Training}，也就是说这里的模型训练是指特征函数的学习；而特征权重的训练，一般被称作{\small\bfnew{权重调优}}\index{权重调优}（Weight Tuning）\index{Weight Tuning}，而这个过程才真正对应了传统机器学习（如分类任务）中的模型训练过程。在本章中，如果没有特殊说明，权重调优就是指特征权重的学习，模型训练是指短语抽取和特征函数的学习。

\parinterval 想要得到最优的特征权重，最简单的方法是枚举所有的特征权重可能的取值，然后评价每组权重所对应的翻译性能，最后选择最优的特征权重作为调优的结果。但是特征权重是一个实数值，因此可以考虑把实数权重进行量化，即把权重看作是在固定间隔上的取值，比如，每隔0.01取值。即使是这样，同时枚举多个特征的权重也是非常耗时的工作，当特征数量增多时这种方法的效率仍然很低。

\parinterval 这里介绍一种更加高效的特征权重调优方法$\ \dash \ ${\small\bfnew{最小错误率训练}}\index{最小错误率训练}（Minimum Error Rate Training\index{Minimum Error Rate Training}，MERT）。最小错误率训练是统计机器翻译发展中代表性工作，也是从机器翻译中原创的重要技术方法之一\cite{och2003minimum}。最小错误率训练假设：翻译结果相对于标准答案的错误是可度量的，进而可以通过降低错误数量的方式来找到最优的特征权重。假设有样本集合$S = \{(s_1,\mathbf{r}_1),...,(s_N,\mathbf{r}_N)\}$，$s_i$为样本中第$i$个源语言句子，$\mathbf{r}_i$为相应的参考译文。注意，$\mathbf{r}_i$可以包含多个参考译文。$S$通常被称为{\small\bfnew{调优集合}}\index{调优集合}（Tuning Set）\index{Tuning Set}。对于$S$中的每个源语句子$s_i$，机器翻译模型会解码出$n$-best推导$d_{i}^{\ast} = \{\mathbf{d}_{ij}^{\ast}\}$，其中$d_{ij}^{\ast}$表示翻译源语言句子$s_i$时得到的第$j$个最好的推导。$\{d_{ij}^{\ast}\}$可以被定义如下：
\begin{eqnarray}
\{d_{ij}^{\ast}\} = \arg\max_{\{d_{ij}\}} \sum_{i=1}^{M} \lambda_i \cdot h_i (d,\mathbf{t},\mathbf{s})
\label{eq:7-17}
\end{eqnarray}

\parinterval 对于每个样本都可以得到$n$-best推导集合，整个数据集上的推导集合被记为$\mathbf{D}^{\ast} = \{\mathbf{d}_{1}^{\ast},...,\mathbf{d}_{s}^{\ast}\}$。进一步，令所有样本的参考译文集合为$\mathbf{R} = \{\mathbf{r}_1,...,\mathbf{r}_N\}$。最小错误率训练的目标就是降低$\mathbf{D}^{\ast}$相对于$\mathbf{R}$的错误。也就是，通过调整不同特征的权重$\lambda = \{ \lambda_i \}$，让错误率最小，形式化描述为：
\begin{eqnarray}
\lambda^{\ast} = \arg\min_{\lambda} \textrm{Error}(\mathbf{D}^{\ast},\mathbf{R})
\label{eq:7-18}
\end{eqnarray}
%公式--------------------------------------------------------------------

\noindent 其中\textrm{Error}$(\cdot)$是错误率函数。\textrm{Error}$(\cdot)$的定义方式有很多，一般来说\textrm{Error}$(\cdot)$会与机器翻译的评价指标相关，例如，词错误率(WER)、位置错误率(PER)、BLEU 值、NIST值等都可以用于\textrm{Error}$(\cdot)$的定义。这里使用1-BLEU作为错误率函数，即$\textrm{Error}(\mathbf{D}^{\ast},\mathbf{R}) = 1 - \textrm{BLEU}(\mathbf{D}^{\ast},\mathbf{R})$。则公式\ref{eq:7-18}可改写为：
%公式--------------------------------------------------------------------
\begin{eqnarray}
\lambda^{\ast} &=& \arg\min_{\lambda}\ 1 - \textrm{BLEU}(\mathbf{D}^{\ast},\mathbf{R})   \nonumber \\
&=& \arg\max_{\lambda} \textrm{BLEU}(\mathbf{D}^{\ast},\mathbf{R})
\label{eq:7-19}
\end{eqnarray}
%公式--------------------------------------------------------------------

\parinterval 需要注意的是， BLEU本身是一个不可微分函数。因此，无法使用梯度下降等方法对式\ref{eq:7-19}进行求解。那么如何能快速得到最优解？这里会使用一种特殊的优化方法，称作{\small\bfnew{线搜索}}\index{线搜索}（Line Search）\index{Line Search}，它是Powell搜索的一种形式\cite{powell1964an}。这种方法也构成了最小错误率训练的核心。

\parinterval 首先，重新看一下特征权重的搜索空间。按照前面的介绍，如果要进行暴力搜索，需要把特征权重的取值按小的间隔进行划分。这样，所有特征权重的取值可以用图\ref{fig:7-23}的网格来表示。

%----------------------------------------------
\begin{figure}[htp]
\centering
\begin{tabular}{l l l}
& \subfigure{\input{./Chapter7/Figures/figure-search-space-representation-of-feature-weight-1}} \subfigure{\input{./Chapter7/Figures/figure-search-space-representation-of-feature-weight-2}} \subfigure{\input{./Chapter7/Figures/figure-search-space-representation-of-feature-weight-3}} &  \\
\end{tabular}
\caption{特征权重的搜索空间表示}
\label{fig:7-23}
\end{figure}
%-------------------------------------------

\parinterval 其中横坐标为所有的$M$个特征函数，纵坐标为权重可能的取值。假设每个特征都有$V$种取值，那么遍历所有特征权重取值的组合有$M^V$种。每组$\lambda = \{\lambda_i\}$的取值实际上就是一个贯穿所有特征权重的折线，如图\ref{fig:7-23}中间红线所展示的路径。当然，可以通过枚举得到很多这样的折线（图\ref{fig:7-23}右）。假设计算BLEU的时间开销为$B$，那么遍历所有的路径的时间复杂度为$\textrm{O}(M^V \cdot B)$，由于$V$可能很大，而且$B$往往也无法忽略，因此这种计算方式的时间成本是极高的。

\parinterval 对全搜索的一种改进是使用局部搜索。循环处理每个特征，每一次只调整一个特征权重的值，找到使BLEU达到最大的权重。反复执行该过程，直到模型达到稳定状态（例如BLEU不再降低）。

%----------------------------------------------
\begin{figure}[htp]
\centering
\begin{tabular}{l l}
\subfigure{\input{./Chapter7/Figures/figure-grid-search-1}} &  \subfigure{\input{./Chapter7/Figures/figure-grid-search-2}} \\
\end{tabular}
\caption{格搜索（左侧：所有点都访问（蓝色）；右侧：避开无效点（绿色））}
\label{fig:7-24}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:7-24}左侧展示了这种方法。其中红色部分为固定住的权重，相应的虚线部分为当前权重所有可能的取值，这样搜索一个特征权重的时间复杂度为$\textrm{O}(V \cdot B)$。而整个算法的时间复杂度为$\textrm{O}(L \cdot V \cdot B)$，其中$L$为循环访问特征的总次数。这种方法也被称作{\small\bfnew{格搜索}}\index{格搜索}（Grid Search）\index{Grid Search}。

\parinterval 格搜索的问题在于，每个特征都要访问$V$个点，且不说$V$个点无法对连续的特征权重进行表示，里面也会存在大量的无用访问。也就是说，这$V$个点中绝大多数点根本``不可能''成为最优的权重。可以把这样的点称为无效取值点。

\parinterval 能否避开这些无效的权重取值点呢？再重新看一下优化的目标BLEU。实际上，当一个特征权重发生变化时，BLEU的变化只会产生在系统1-best译文发生变化的时候。那么，可以只关注使1-best译文发生变化的取值点，而其他的取值点都不会对优化的目标函数产生变化。这也就构成了线搜索的思想。

\parinterval 假设对于每个输入的句子，翻译模型生成了两个推导$\mathbf{d} = \{d_1,d_2\}$，每个推导$d$的得分score($d$)可以表示成关于第$i$个特征的权重$\lambda_i$的线性函数：
\begin{eqnarray}
\textrm{score}(d) &=& \sum_{k=1} \lambda_k \cdot h_k (d) \nonumber \\
&=& h_i (d) \cdot \lambda_i + \sum_{k \neq i} \lambda_k \cdot h_k (d) \nonumber \\
&=& a \cdot \lambda_i + b
\label{eq:7-20}
\end{eqnarray}

\parinterval 这里，$a = h_i(d)$是直线的斜率，$b = \sum_{k \neq i}^{M} \lambda_k \cdot h_k (d)$是截距。有了关于权重$\lambda_i$的直线表示，可以将$d_1$和$d_2$分别画成两条直线，如图\ref{fig:7-25}所示。在两条直线交叉点的左侧，$d_2$是最优的翻译结果；在交叉点右侧，$d_1$是最优的翻译结果。也就是说，只需知道交叉点左侧和右侧谁的BLEU 值高，$\lambda_i$的最优值就应该落在相应的范围，比如，这个例子中交叉点右侧（即$d_2$）所对应的BLEU值更高，因此最优特征权重应该在交叉点右侧（$\lambda_x \sim \lambda_i$任意取值都可以）。

%----------------------------------------------
\begin{figure}[htp]
\centering
\begin{tabular}{l l}
\subfigure{\input{./Chapter7/Figures/figure-function-image-about-weight-and-Bleu-1}} &  \subfigure{\input{./Chapter7/Figures/figure-function-image-about-weight-and-Bleu-2}} \\
\end{tabular}
\caption{推导得分关于权重的函数以及对应的BLEU值变化}
\label{fig:7-25}
\end{figure}
%-------------------------------------------

\parinterval 这样，最优权重搜索的问题就被转化为找到最优推导BLEU值发生变化的点的问题。理论上，对于$n$-best翻译，交叉点计算最多需要$\frac{n(n-1)}{2}$次。由于$n$一般不会过大，这个时间成本完全是可以接受的。此外，在实现时还有一些技巧，比如，并不需要在每个交叉点处对整个数据集进行BLEU计算，可以只对BLEU产生变化的部分（比如$n$-gram匹配的数量）进行调整，因此搜索的整体效率会进一步得到提高。相比于格搜索，线搜索可以确保在单个特征维度上的最优值，同时保证搜索的效率。

\parinterval 还有一些经验性的技巧用来完善基于线搜索的MERT。例如：

\begin{itemize}
\vspace{0.5em}
\item 随机生成特征权重的起始点；
\vspace{0.5em}
\item 搜索中，给权重加入一些微小的扰动，避免陷入局部最优；
\vspace{0.5em}
\item 随机选择特征优化的顺序；
\vspace{0.5em}
\item 使用先验知识来指导MERT（对权重的取值范围进行约束）；
\vspace{0.5em}
\item 使用多轮迭代训练，最终对权重进行平均。
\vspace{0.5em}
\end{itemize}

\parinterval MERT最大的优点在于可以用于目标函数不可微、甚至不连续的情况。对于优化线性模型， MERT是一种很好的选择。但是，也有研究发现，简单使用MERT无法处理特征数量过多的情况。比如，用MERT优化10000个稀疏特征的权重时，优化效果可能会不理想，而且收敛速度慢。这时也可以考虑使用在线学习等技术对大量特征的权重进行调优，比较有代表性的方法包括MIRA\cite{DBLP:conf/emnlp/ChiangMR08}和PRO\cite{Hopkins2011Tuning}。由于篇幅所限，这里不对这些方法做深入讨论，感兴趣的读者可以参考\ref{section-4.5}节的内容，对相关文献进行查阅。

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\sectionnewpage
\section{栈解码}

\parinterval 解码的目的是根据模型以及输入，找到模型得分最高的推导，即：
\begin{eqnarray}
\hat{d} = \arg\max_{d} \textrm{score}(d,\mathbf{t},\mathbf{s})
\label{eq:7-21}
\end{eqnarray}

\parinterval 然而想要找到得分最高的翻译推导并不是一件简单的事情。对于每一句源语言句子，可能的翻译结果是指数级的。而机器翻译解码也已经被证明是一个NP难问题\cite{knight1999decoding}。简单的暴力搜索显然不现实。因此，在机器翻译中会使用特殊的解码策略来确保搜索的效率。本节将介绍基于栈的自左向右解码方法。它是基于短语的模型中的经典解码方法，非常适于处理语言生成的各种任务。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-basic-process-of-translation}
\caption{翻译的基本流程}
\label{fig:7-26}
\end{figure}
%-------------------------------------------

\parinterval 首先，看一下翻译一个句子的基本流程。如图\ref{fig:7-26}所示，首先需要得到译文句子的第一个单词。在基于短语的模型中，可以从源语言端找出生成句首译文的短语，之后把译文放到目标语言端，例如，源语言的``有''对应的译文是``There is''。这个过程可以重复执行，直到生成完整句子的译文。但是，有两点需要注意：

\begin{itemize}
\vspace{0.5em}
\item 源语言的每个单词（短语）只能被翻译一次；
\vspace{0.5em}
\item 译文的生成需自左向右连续进行。
\vspace{0.5em}
\end{itemize}

\parinterval 前者对应了一种{\small\bfnew{覆盖度模型}}\index{覆盖度模型}（Coverage Model）\index{Coverage Model}；后者定义了解码的方向，这样可以确保$n$-gram语言模型的计算是准确的。这样，就得到了一个简单的基于短语的机器翻译解码框架。每次从源语言句子中找到一个短语，作为译文最右侧的部分，重复执行直到整个译文被生成出来。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{翻译候选匹配}

\parinterval 在解码时，首先要知道每个源语言短语可能的译文都是什么。对于一个源语言短语，每个可能的译文也被称作{\small\bfnew{翻译候选}}\index{翻译候选}（Translation Candidate）\index{Translation Candidate}。实现翻译候选的匹配很简单。只需要遍历输入的源语言句子中所有可能的短语，之后在短语表中找到相应的翻译即可。比如，图\ref{fig:7-27}展示了句子``桌子\ 上\ 有\ 一个\ 苹果''的翻译候选匹配结果。可以看到，不同的短语会对应若干翻译候选。这些翻译候选会保存在所对应的跨度中。比如，``upon the table''是短语``桌子 上 有''的翻译候选，即对应源语言跨度[0,3]。

%----------------------------------------------
\begin{figure}[t]
\centering
\input{./Chapter7/Figures/figure-translation-option}
\caption{一个句子匹配的短语翻译候选}
\label{fig:7-27}
\end{figure}
%-------------------------------------------

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{翻译假设扩展}

\parinterval 下一步，需要使用这些翻译候选生成完整的译文。在机器翻译中，一个很重要的概念是{\small\bfnew{翻译假设}}\index{翻译假设}（Translation Hypothesis）\index{Translation Hypothesis}。 它可以被当作是一个局部译文所对应的短语翻译推导。在解码开始时，只有一个空假设，也就是任何译文单词都没有被生成出来。接着，可以挑选翻译选项来扩展当前的翻译假设。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-translation-hypothesis-extension}
\caption{翻译假设扩展}
\label{fig:7-28}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:7-28}展示了翻译假设扩展的过程。在翻译假设扩展时，需要保证新加入的翻译候选放置在旧翻译假设译文的右侧，也就是要确保翻译自左向右的连续性。而且，同一个翻译假设可以使用不同的翻译候选进行扩展。例如，扩展第一个翻译假设时，可以选择``桌子''的翻译候选``table''；也可以选择``有''的翻译候选``There is''。扩展完之后需要记录输入句子中已翻译的短语，同时计算当前所有翻译假设的模型得分。这个过程相当于生成了一个图的结构，每个节点代表了一个翻译假设。当翻译假设覆盖了输入句子所有的短语，不能被继续扩展时，就生成了一个完整的翻译假设（译文）。最后需要找到得分最高的完整翻译假设，它对应了搜索图中的最优路径。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{剪枝}

\parinterval 假设扩展建立了解码算法的基本框架。但是，当句子变长时，这种方法还是面临着搜索空间爆炸的问题。对于这个问题，常用的解决办法是{\small\bfnew{剪枝}}\index{剪枝}（Pruning）\index{Pruning}，也就是在搜索图中排除掉一些节点。比如，可以使用{\small\bfnew{束剪枝}}\index{束剪枝}（Beam Pruning）\index{Beam Pruning}，确保每次翻译扩展时，最多生成$k$个新的翻译假设。这里$k$可以被看做是束的宽度。通过控制$k$的大小，可以在解码精度和速度之间进行平衡。这种基于束宽度进行剪枝的方法也被称作{\small\bfnew{直方图剪枝}}\index{直方图剪枝}（Histogram Pruning）\index{Histogram Pruning}。另一种思路是，每次扩展时只保留与最优翻译假设得分相差在$\delta$之内的翻译假设。$\delta$可以被看作是一种与最优翻译假设之间距离的阈值，超过这个阈值就被剪枝。这种方法也被称作{\small\bfnew{阈值剪枝}}\index{阈值剪枝}（Threshold Pruning）\index{Threshold Pruning}。

\parinterval 不过，即使引入束剪枝，解码过程中仍然会有很多冗余的翻译假设。有两种方法可以进一步加速解码：

\begin{itemize}
\vspace{0.5em}
\item 对相同译文的翻译假设进行重新组合；
\vspace{0.5em}
\item 对低质量的翻译假设进行裁剪。
\vspace{0.5em}
\end{itemize}

\parinterval 对翻译假设进行重新组合又被称作{\small\bfnew{假设重组}}\index{假设重组}（Hypothesis Recombination）\index{Hypothesis Recombination}。其核心思想是，把代表同一个译文的不同翻译假设融合为一个翻译假设。如图29所示，对于给定的输入短语``一个\ \ 苹果''，系统可能将两个单词``一个''、``苹果''分别翻译成``an''和``apple''，也可能将这两个单词作为一个短语直接翻译成``an apple''。虽然这两个翻译假设得到的译文相同，并且覆盖了相同的源语言短语，但是却是两个不同的翻译假设，模型给它们的打分也是不一样的。这时，可以舍弃两个翻译假设中分数较低的那个，因为分数较低的翻译假设永远不可能成为最优路径的一部分。这也就相当于把两个翻译假设重组为一个假设。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-example-of-hypothesis-recombination}
\caption{假设重组示例}
\label{fig:7-29}
\end{figure}
%-------------------------------------------

\parinterval 即使翻译假设对应的译文不同也可以进行假设重组。图\ref{fig:7-29}的下半部分给出了一个这样的实例。在两个翻译假设中，第一个单词分别被翻译成了``it''和``he''，紧接着它们后面的部分都被翻译成了``is not''。这两个翻译假设是非常相似的，因为它们译文的最后两个单词是相同的，而且翻译假设都覆盖了相同的源语言部分。这时，也可以对这两个翻译假设进行假设重组：如果得分较低的翻译假设和得分较高的翻译假设都使用相同的翻译候选进行扩展，且两个翻译假设都覆盖相同的源语言单词，分数低的翻译假设可以被剪枝掉。此外，还有两点需要注意：

\begin{itemize}
\vspace{0.5em}
\item $n$-gram语言模型将前$n-1$单词作为历史信息，所以当两个假设最后$n-1$个单词不相同时，不能进行假设重组，因为后续的扩展可能会得到不同的语言模型得分，并影响最终的模型得分；
\vspace{0.5em}
\item 调序模型通常是用来判断当前输入的短语与前一个输入短语之间的调序代价。因此当两个翻译假设对应短语在源语言中的顺序不同时，也不能被重新组合。
\vspace{0.5em}
\end{itemize}

\parinterval 然而在实际处理中，并不需要``删掉''分数低的翻译假设，而是将它们与分数高的翻译假设连在了一起。对于搜索最优翻译，这些连接可能并没有什么作用，但是如果需要分数最高的前两个或前三个翻译，就可能需要用到这些连接。

\parinterval 翻译假设的重组有效地减少了解码过程中相同或者相似翻译假设带来的冗余。因此这些方法在机器翻译中被广泛使用。包括本章后面将要介绍的基于句法的翻译模型解码中，也可以使用假设重组进行系统加速。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{解码中的栈结构}

\parinterval 当质量较差的翻译假设在扩展早期出现时，这些翻译假设需要被剪枝掉，这样可以忽略所有从它扩展出来的翻译假设，进而有效地减小搜索空间。但是这样做也存在着一定的问题，首先，删除的翻译假设可能会在后续的扩展过程中被重新搜索出来。其次，过早地删除某些翻译假设可能会导致无法搜索到最优的翻译假设。所以最好的情况是尽早删除质量差的翻译假设，同时又不会对整个搜索结果产生过大影响。但是这个``质量''从哪个方面来衡量，也是一个需要思考的问题。理想的情况就是从早期的翻译假设中，挑选一些可比的翻译假设进行筛选。

\parinterval 目前比较通用的做法是将翻译假设进行整理，放进一种栈结构中。这里所说的``栈''是为了描述方便的一种说法。它实际上就是保存多个翻译假设的一种数据结构\footnote[4]{虽然被称作栈，实际上使用一个堆进行实现。这样可以根据模型得分对翻译假设进行排序。}。当放入栈的翻译假设超过一定阈值时（比如200），可以删除掉模型得分低的翻译假设。一般，会使用多个栈来保存翻译假设，每个栈代表覆盖源语言单词数量相同的翻译假设。

\parinterval 比如，第一个堆栈包含了覆盖一个源语言单词的翻译假设，第二个堆栈包含了覆盖两个源语言单词的翻译假设，以此类推。利用覆盖源语言单词数进行栈的划分的原因在于：翻译相同数量的单词所对应的翻译假设一般是``可比的''，因此在同一个栈里对它们进行剪枝带来的风险较小。

\parinterval 在基于栈的解码中，每次都会从所有的栈中弹出一个翻译假设，并选择一个或者若干个翻译假设进行扩展，之后把新得到的翻译假设重新压入解码栈中。这个过程不断执行，并可以配合束剪枝、假设重组等技术。最后在覆盖所有源语言单词的栈中得到整个句子的译文。图\ref{fig:7-30}展示了一个简单的栈解码过程。第一个栈（0号栈）用来存放空翻译假设。之后通过假设扩展，不断将翻译假设填入对应的栈中。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter7/Figures/figure-example-of-stack-decode}
\caption{栈解码示例}
\label{fig:7-30}
\end{figure}
%-------------------------------------------

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\sectionnewpage
\section{小节及深入阅读}