% !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-8.jpg} % Chapter heading image

%----------------------------------------------------------------------------------------
%	CHAPTER 8
%----------------------------------------------------------------------------------------

\chapter{基于句法的模型}

人类的语言是具有结构的，这种结构往往体现在句子的句法信息上。比如，人们在翻译一个句子的时候会将待翻译的主干确定下来，之后得到译文的主干，最后形成完整的译文。一个人学习外语时，也会先学习外语句子的基本构成，比如，主语、谓语等。之后用这种句子结构知识生成外语句子。

使用句法分析也可以很好的处理翻译中的结构调序、远距离依赖等问题。而基于句法的机器翻译长期受到研究者关注。比如，早期基于规则的方法里就大量使用了句法信息来定义翻译规则。机器翻译的统计建模时代，句法信息的使用同样是领域主要研究方向之一。这也产生了很多基于句法的机器翻译模型及方法，而且在很多任务上取得非常出色的结果。本章将对这些模型和方法进行介绍，内容涉及机器翻译中句法信息的表示、句法翻译规则的学习、基于句法的翻译建模等。

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------
\sectionnewpage
\section{翻译中句法信息的使用}

\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 使用句法信息在机器翻译中不新鲜。在基于规则和模板的翻译模型中，就大量地使用了句法等结构信息。只是由于早期句法分析技术不成熟，系统的整体效果并不突出。在数据驱动的方法中，句法可以很好地融合在统计建模中。通过概率化的文法设计，可以对翻译过程进行很好的描述。

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

\sectionnewpage
\section{基于层次短语的模型}\label{section-4.3}

\parinterval 在机器翻译中，如果翻译需要局部上下文的信息，把短语作为翻译单元是一种理想的方案。但是，单词之间的关系并不总是``局部''的，很多时候需要距离更远一些的搭配。比较典型的例子是含有从句的情况。比如：
\begin{eqnarray}
\qquad \textrm{{\small\bfnew{我}}\ \ 在\ \ 今天\ \ 早上\ \ 没有\ \ 吃\ \ 早\ \ 饭\ \ 的\ \ 情况\ \ 下\ \ 还是\ \ 正常\ \ {\small\bfnew{去}}\ \ {\small\bfnew{上班}}\ \ 了。} \nonumber
\end{eqnarray}

\parinterval 这句话的主语``我''和谓语``去\ 上班''构成了主谓搭配，而二者之间的部分是状语。显然，用短语去捕捉这个搭配需要覆盖很长的词串，也就是整个``我 $...$ 去 上班''的部分。如果把这样的短语考虑到建模中，会面临非常严重的数据稀疏问题，因为无法保证这么长的词串在训练数据中能够出现。

%----------------------------------------------
\begin{table}[htp]{
\begin{center}
\caption{不同短语在训练数据中出现的频次}
\label{tab:8-1}
\begin{tabular}{p{12em} | r}
短语(中文) & 训练数据中出现的频次 \\
\hline

包含 & 3341\\
包含\ 多个 & 213\\
包含\ 多个\ 词 & 12\\
包含\ 多个\ 词\ 的 & 8\\
包含\ 多个\ 词\ 的\ 短语 & 0\\
包含\ 多个\ 词\ 的\ 短语\ 太多 & 0\\
\end{tabular}
\end{center}
}\end{table}
%-------------------------------------------

\parinterval 实际上，随着短语长度变长，短语在数据中会变得越来越低频，相关的统计特征也会越来越不可靠。表\ref{tab:8-1}就展示了不同长度的短语在训练数据中出现的频次。可以看到，长度超过3的短语已经非常低频了，更长的短语甚至在训练数据中一次也没有出现过。

\parinterval 显然，利用过长的短语来处理长距离的依赖并不是一种十分有效的方法。过于低频的长短语无法提供可靠的信息，而且使用长短语会导致模型体积急剧增加。

\parinterval 再来看一个翻译实例\cite{Chiang2012Hope}，图\ref{fig:8-1}是一个基于短语的机器翻译系统的翻译结果。这个例子中的调序有一些复杂，比如，``少数\ 国家\ 之一''和``与\ 北韩\ 有\ 邦交''的英文翻译都需要进行调序，分别是``one of the few countries''和``have diplomatic relations with North Korea''。基于短语的系统可以很好地处理这些调序问题，因为它们仅仅使用了局部的信息。但是，系统却无法在这两个短语（1和2）之间进行正确的调序。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-an-example-of-phrase-system}
\caption{基于短语的机器翻译实例\cite{Chiang2012Hope}}
\label{fig:8-1}
\end{figure}
%-------------------------------------------

\parinterval 这个例子也在一定程度上说明了长距离的调序需要额外的机制才能得到更好地被处理。实际上，两个短语（1和2）之间的调序现象本身对应了一种结构，或者说模板。也就是汉语中的：
\begin{eqnarray}
\text{与}\ \ \text{[什么东西]}\ \ \text{有}\ \ \text{[什么事]} \quad \nonumber
\end{eqnarray}

\parinterval 可以翻译成：
\begin{eqnarray}
\textrm{have}\ \ \text{[什么事]}\ \ \textrm{with}\ \ \text{[什么东西]} \nonumber
\end{eqnarray}

\parinterval 这里[什么东西]和[什么事]表示模板中的变量，可以被其他词序列替换。通常，可以把这个模板形式化描述为：
\begin{eqnarray}
\langle \ \text{与}\ \textrm{X}_1\ \text{有}\ \textrm{X}_2,\quad \textrm{have}\ \textrm{X}_2\ \textrm{with}\ \textrm{X}_1\ \rangle \nonumber
\end{eqnarray}

\noindent 其中，逗号分隔了源语言和目标语言部分，$\textrm{X}_1$和$\textrm{X}_2$表示模板中需要替换的内容，或者说变量。源语言中的变量和目标语言中的变量是一一对应的，比如，源语言中的$\textrm{X}_1$ 和目标语言中的$\textrm{X}_1$代表这两个变量可以``同时''被替换。假设给定短语对：
\begin{eqnarray}
\langle \ \text{北韩},\quad \textrm{North Korea} \ \rangle \qquad\ \quad\quad\ \  \nonumber \\
\langle \ \text{邦交},\quad \textrm{diplomatic relations} \ \rangle\quad\ \ \ \nonumber
\end{eqnarray}

\parinterval 可以使用第一个短语替换模板中的变量$\textrm{X}_1$，得到：
\begin{eqnarray}
\langle \ \text{与}\ \text{[北韩]}\ \text{有}\ \textrm{X}_2,\quad \textrm{have}\ \textrm{X}_2\ \textrm{with}\ \textrm{[North Korea]} \ \rangle \nonumber
\end{eqnarray}

\noindent 其中，$[\cdot]$表示被替换的部分。可以看到，在源语言和目标语言中，$\textrm{X}_1$被同时替换为相应的短语。进一步，可以用第二个短语替换$\textrm{X}_2$，得到：
\begin{eqnarray}
\quad\langle \ \text{与}\ \text{北韩}\ \text{有}\ \text{[邦交]},\quad \textrm{have}\ \textrm{[diplomatic relations]}\ \textrm{with}\ \textrm{North Korea} \ \rangle \nonumber
\end{eqnarray}

\parinterval 至此，就得到了一个完整词串的译文。类似的，还可以写出其他的翻译模板，如下：
\begin{eqnarray}
\langle \ \textrm{X}_1\ \text{是}\ \textrm{X}_2,\quad \textrm{X}_1\ \textrm{is}\ \textrm{X}_2 \ \rangle \qquad\qquad\ \nonumber \\
\langle \ \textrm{X}_1\ \text{之一},\quad \textrm{one}\ \textrm{of}\ \textrm{X}_1 \ \rangle \qquad\qquad\ \nonumber \\
\langle \ \textrm{X}_1\ \text{的}\ \textrm{X}_2,\quad \textrm{X}_2\ \textrm{that}\ \textrm{have}\ \textrm{X}_1\ \rangle\quad\ \nonumber
\end{eqnarray}

\parinterval 使用上面这种变量替换的方式，就可以得到一个完整句子的翻译。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-translation-rule-describe-two-sentence-generation}
\caption{使用短语和翻译模板进行双语句子的同步生成}
\label{fig:8-2}
\end{figure}
%-------------------------------------------

\parinterval 这个过程如图\ref{fig:8-2}所示。其中，左右相连接的方框表示翻译模版的源语言和目标语言部分。可以看到，模版中两种语言中的变量会被同步替换，替换的内容可以是其他模版生成的结果。这也就对应了一种层次结构，或者说互译的句对可以被双语的层次结构同步生成出来。

\parinterval 实际上，在翻译中使用这样的模版就构成了层次短语模型的基本思想。下面就一起看看如何对翻译模版进行建模，以及如何自动学习并使用这些模版。

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

\subsection{同步上下文无关文法}

\parinterval {\small\bfnew{基于层次短语的模型}}\index{基于层次短语的模型}（Hierarchical Phrase-based Model）\index{Hierarchical Phrase-based Model}是David Chiang于2005提出的统计机器翻译模型\cite{chiang2005a,chiang2007hierarchical}。这个模型可以很好地解决短语系统对翻译中长距离调序建模不足的问题。基于层次短语的系统也在多项机器翻译比赛中取得了很好的成绩。这项工作也获得了自然处理领域顶级会议ACL2015的最佳论文奖。

\parinterval 层次短语模型的核心是把翻译问题归结为两种语言词串的同步生成问题。实际上，词串的生成问题是自然语言处理中的经典问题，早期的研究更多的是关注单语句子的生成，比如，如何使用句法树描述一个句子的生成过程。层次短语模型的创新之处是把传统单语词串的生成推广到双语词串的同步生成上。这使得机器翻译可以使用类似句法分析的方法进行求解。

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

\subsubsection{文法定义}

\parinterval 层次短语模型中一个重要的概念是{\small\bfnew{同步上下文无关文法}}\index{同步上下文无关文法}（Synchronous Context-free Grammar\index{Synchronous Context-free Grammar}，简称SCFG）。SCFG可以被看作是对源语言和目标语言上下文无关文法的融合，它要求源语言和目标语言的产生式及产生式中的变量具有对应关系。具体定义如下：

%-------------------------------------------
\vspace{0.5em}
\begin{definition} 同步上下文无关文法

{\small
一个同步上下文无关文法由五部分构成$(N, T_s, T_t, I, R)$，其中：
\begin{enumerate}
\item $N$是非终结符集合。
\item $T_s$和$T_t$分别是源语言和目标语言的终结符集合。
\item $I \subseteq N$起始非终结符集合。
\item $R$是规则集合，每条规则$r \in R$有如下形式：
\end{enumerate}
\begin{displaymath}
\textrm{LHS} \to <\alpha, \beta, \sim>
\end{displaymath}
其中，$\textrm{LHS} \in N$表示规则的左部，它是一个非终结符；规则的右部由三部分组成，$\alpha \in (N \bigcup T_s)^{*}$表示由源语言终结符和非终结符组成的串；$\beta \in (N \bigcup T_t)^{*}$ 表示由目标语言终结符和非终结符组成的串；$\sim$表示$\alpha$和$\beta$中非终结符的1-1对应关系。
}
\end{definition}
%-------------------------------------------

\parinterval 根据这个定义，源语言和目标语言有不同的终结符集合（单词），但是它们会共享同一个非终结符集合（变量）。每个产生式包括源语言和目标语言两个部分，分别表示由规则左部生成的源语言和目标语言符号串。由于产生式会同时生成两种语言的符号串，因此这是一种``同步''生成，可以很好地描述翻译中两个词串之间的对应。\\

\parinterval 下面是一个简单的SCFG实例：
\begin{eqnarray}
\textrm{S}\ &\to\ &\langle \ \textrm{NP}_1\ \text{希望}\ \textrm{VP}_2,\quad \textrm{NP}_1\ \textrm{wish}\ \textrm{to}\ \textrm{VP}_2\ \rangle \nonumber \\
\textrm{VP}\ &\to\ &\langle \ \text{对}\ \textrm{NP}_1\ \text{感到}\ \textrm{VP}_2,\quad \textrm{be}\ \textrm{VP}_2\ \textrm{wish}\ \textrm{NP}_1\ \rangle \nonumber \\
\textrm{NN}\ &\to\ &\langle \ \text{强大},\quad \textrm{strong}\ \rangle \nonumber
\end{eqnarray}

\parinterval 这里的S、NP、VP等符号可以被看作是具有句法功能的标记，因此这个文法和传统句法分析中的CFG很像，只是CFG是单语文法，而SCFG是双语同步文法。当然，复杂的句法功能标记并不是必须的。比如，也可以使用更简单的文法形式：
\begin{eqnarray}
\textrm{X}\ &\to\ &\langle \ \textrm{X}_1\ \text{希望}\ \textrm{X}_2,\quad \textrm{X}_1\ \textrm{wish}\ \textrm{to}\ \textrm{X}_2\ \rangle \nonumber \\
\textrm{X}\ &\to\ &\langle \ \text{对}\ \textrm{X}_1\ \text{感到}\ \textrm{X}_2,\quad \textrm{be}\ \textrm{X}_2\ \textrm{wish}\ \textrm{X}_1\ \rangle \nonumber \\
\textrm{X}\ &\to\ &\langle \ \text{强大},\quad \textrm{strong}\ \rangle \nonumber
\end{eqnarray}

\parinterval 这个文法只有一种非终结符X，因此所有的变量都可以使用任意的产生式进行推导。这就给翻译提供了更大的自由度，也就是说，规则可以被任意使用，进行自由组合。这也符合基于短语的模型中对短语进行灵活拼接的思想。基于此，层次短语系统中也使用这种并不依赖语言学句法标记的文法。在本章的内容中，如果没有特殊说明，本章中把这种没有语言学句法标记的文法称作{\small\bfnew{基于层次短语的文法}}\index{基于层次短语的文法}（Hierarchical Phrase-based Grammar）\index{Hierarchical Phrase-based Grammar}，或简称层次短语文法。

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

\subsubsection{推导}

\parinterval 下面是一个完整的层次短语文法：
\begin{eqnarray}
r_1:\quad \textrm{X}\ &\to\ &\langle \ \text{进口}\ \textrm{X}_1,\quad \textrm{The}\ \textrm{imports}\ \textrm{X}_1\ \rangle \nonumber \\
r_2:\quad \textrm{X}\ &\to\ &\langle \ \textrm{X}_1\ \text{下降}\ \textrm{X}_2,\quad \textrm{X}_2\ \textrm{X}_1\ \textrm{fallen}\ \rangle \nonumber \\
r_3:\quad \textrm{X}\ &\to\ &\langle \ \text{大幅度},\quad \textrm{drastically}\ \rangle \nonumber \\
r_4:\quad \textrm{X}\ &\to\ &\langle \ \text{了},\quad \textrm{have}\ \rangle \nonumber
\end{eqnarray}

\noindent 其中，规则$r_1$和$r_2$是含有变量的规则，这些变量可以被其他规则的右部替换；规则$r_2$是调序规则；规则$r_3$和$r_4$是纯词汇化规则，表示单词或者短语的翻译。

\parinterval 对于一个双语句对：
\begin{eqnarray}
&\text{{\small\bfnew{源语}}：}\ \ \ &\text{进口}\ \text{大幅度}\ \text{下降}\ \text{了} \nonumber \\
&\text{{\small\bfnew{目标语}}：}&\textrm{The}\ \textrm{imports}\ \textrm{have}\ \textrm{drastically}\ \textrm{fallen} \nonumber
\end{eqnarray}

\parinterval 可以进行如下的推导（假设起始符号是X）：
\begin{eqnarray}
& & \langle\ \textrm{X}_1, \textrm{X}_1\ \rangle \nonumber \\
& \xrightarrow[]{r_1} & \langle\ {\red{\textrm{进口}\ \textrm{X}_2}},\ {\red{\textrm{The imports}\ \textrm{X}_2}}\ \rangle \nonumber \\
& \xrightarrow[]{r_2} & \langle\ \textrm{进口}\ {\red{\textrm{X}_3\ \textrm{下降}\ \textrm{X}_4}},\ \textrm{The imports}\ {\red{\textrm{X}_4\ \textrm{X}_3\ \textrm{fallen}}}\ \rangle \nonumber \\
& \xrightarrow[]{r_3} & \langle\ \textrm{进口}\ {\red{\textrm{大幅度}}}\ \textrm{下降}\ \textrm{X}_4, \nonumber \\
& & \ \textrm{The imports}\ \textrm{X}_4\ {\red{\textrm{drastically}}}\ \textrm{fallen}\ \rangle \nonumber \\
& \xrightarrow[]{r_4} & \langle\ \textrm{进口}\ \textrm{大幅度}\ \textrm{下降}\ {\red{\textrm{了}}}, \nonumber \\
& & \ \textrm{The imports}\ {\red{\textrm{have}}}\ \textrm{drastically}\ \textrm{fallen}\ \rangle \nonumber
\end{eqnarray}

\noindent 其中，每使用一次规则就会同步替换源语言和目标语言符号串中的一个非终结符。通常，可以把上面这个过程称作翻译{\small\bfnew{推导}}\index{推导}（Derivation）\index{Derivation}，记为：
\begin{eqnarray}
d = {r_1} \circ {r_2} \circ {r_3} \circ {r_4}
\label{eq:4-22}
\end{eqnarray}

\parinterval 在层次短语模型中，每个翻译推导都唯一的对应一个目标语译文。因此，可以用推导的概率$\textrm{P}(d)$描述翻译的好坏。同基于短语的模型是一样的（见\ref{subsection-4.2.2}节），层次短语翻译的目标是：求概率最高的翻译推导$\hat{d}=\arg\max\textrm{P}(d)$。值得注意的是，基于推导的方法在句法分析中也十分常用。层次短语翻译实质上也是通过生成翻译规则的推导来对问题的表示空间进行建模。在\ref{section-4.4} 节还将看到，这种方法可以被扩展到语言学上基于句法的翻译模型中。而且这些模型都可以用一种被称作超图的结构来进行建模。从某种意义上讲，基于规则推导的方法将句法分析和机器翻译进行了形式上的统一。因此机器翻译也借用了很多句法分析的思想。

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

\subsubsection{胶水规则}

\parinterval 由于翻译现象非常复杂，在实际系统中往往需要把两个局部翻译线性拼接到一起。在层次短语模型中，这个问题通过引入{\small\bfnew{胶水规则}}\index{胶水规则}（Glue Rule）\index{Glue Rule}来处理，形式如下：
\begin{eqnarray}
\textrm{S} & \to & \langle\ \textrm{S}_1\ \textrm{X}_2,\ \textrm{S}_1\ \textrm{X}_2\ \rangle \nonumber \\
\textrm{S} & \to & \langle\ \textrm{X}_1,\ \textrm{X}_1\ \rangle \nonumber
\end{eqnarray}

\parinterval 胶水规则引入了一个新的非终结符S，S只能和X进行顺序拼接，或者S由X生成。如果把S看作文法的起始符，使用胶水规则后，相当于把句子划分为若干个部分，每个部分都被归纳为X。之后，顺序地把这些X拼接到一起，得到最终的译文。比如，最极端的情况，整个句子会生成一个X，之后再归纳为S，这时并不需要进行胶水规则的顺序拼接；另一种极端的情况，每个单词都是独立的被翻译，被归纳为X，之后先把最左边的X归纳为S，再依次把剩下的X依次拼到一起。这样的推导形式如下：
\begin{eqnarray}
\textrm{S} & \to & \langle\ \textrm{S}_1\ \textrm{X}_2,\ \textrm{S}_1\ \textrm{X}_2\ \rangle \nonumber \\
                & \to & \langle\ \textrm{S}_3\ \textrm{X}_4\ \textrm{X}_2,\ \textrm{S}_3\ \textrm{X}_4\ \textrm{X}_2\ \rangle \nonumber \\
                & \to & ... \nonumber \\
                & \to & \langle\ \textrm{X}_n\ ...\ \textrm{X}_4\ \textrm{X}_2,\ \textrm{X}_n\ ...\ \textrm{X}_4\ \textrm{X}_2\ \rangle \nonumber
\end{eqnarray}

\parinterval 实际上，胶水规则在很大程度上模拟了基于短语的系统中对字符串顺序翻译的操作，而且在实践中发现，这个步骤是十分必要的。特别是对法-英翻译这样的任务，由于语言的结构基本上是顺序翻译的，因此引入顺序拼接的操作符合翻译的整体规律。同时，这种拼接给翻译增加了灵活性，系统会更加健壮。

\parinterval 需要说明的是，使用同步文法进行翻译时由于单词的顺序是内嵌在翻译规则内的，因此这种模型并不依赖额外的调序模型。一旦文法确定下来，系统就可以进行翻译。

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

\subsubsection{处理流程}

\parinterval 层次短语系统的流程如图\ref{fig:8-3}所示。其核心是从双语数据中学习同步翻译文法，并进行翻译特征的学习，形成翻译模型（即规则+特征）。同时，要从目标语言数据中学习语言模型。最终，把翻译模型和语言模型一起送入解码器，在特征权重调优后，完成对新输入句子的翻译。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-processing-of-hierarchical-phrase-system}
\caption{层次短语系统的处理流程}
\label{fig:8-3}
\end{figure}
%-------------------------------------------

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

\subsection{层次短语规则抽取}

\parinterval 层次短语系统所使用的文法包括两部分：1）不含变量的层次短语规则（短语翻译）；2）含有变量的层次短语规则。短语翻译的抽取直接复用基于短语的系统即可。此处重点讨论如何抽取含有变量的层次短语规则。

\parinterval 在\ref{subsection-4.2.3}节已经介绍了短语与词对齐相兼容的概念。这里，所有层次短语规则也是与词对齐相兼容（一致）的。

%-------------------------------------------
\vspace{0.5em}
\begin{definition} 与词对齐相兼容的层次短语规则

{\small
对于句对$(\mathbf{s},\mathbf{t})$和它们之间的词对齐$\mathbf{a}$，令$N$表示在句对$(\mathbf{s},\mathbf{t})$上与$\mathbf{a}$相兼容的双语短语集合。则：
\begin{enumerate}
\item 	如果$(x,y)\in N$，则$\textrm{X} \to \langle x,y,\phi \rangle$是与词对齐相兼容的层次短语规则。
\item 	对于$(x,y)\in N$，存在$m$个双语短语$(x_i,y_j)\in N$，同时存在(1,$...$,$m$)上面的一个排序$\sim = {\pi_1 , ... ,\pi_m}$，且：
\end{enumerate}
\vspace{-1.5em}
\begin{eqnarray}
x&=&\alpha_0 x_1 \alpha_1 x_2 ... \alpha_{m-1} x_m \alpha_m \label{eqa4.23}\\
y&=&\beta_0 y_{\pi_1} \beta_1 y_{\pi_2} ... \beta_{m-1} y_{\pi_m} \beta_m
\label{eq:4-24}
\end{eqnarray}
其中，${\alpha_0, ... ,\alpha_m}$和${\beta_0, ... ,\beta_m}$表示源语言和目标语言的若干个词串（包含空串）。则$\textrm{X} \to \langle x,y,\sim \rangle$是与词对齐相兼容的层次短语规则。这条规则包含$m$个变量，变量的对齐信息是$\sim$。
}
\end{definition}
%-------------------------------------------

\parinterval 这个定义中，所有规则都是由双语短语生成。如果规则中含有变量，则变量部分也需要满足与词对齐相兼容的定义。按上述定义实现层次短语规则抽取也很简单。只需要对短语抽取系统进行改造：对于一个短语，可以通过挖``槽''的方式生成含有变量的规则。每个``槽''就代表一个变量。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-extract-hierarchical-phrase-rules}
\caption{通过双语短语抽取层次短语规则}
\label{fig:8-4}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:8-4}展示了一个层次短语抽取的示意图。可以看到，在获取一个`` 大''短语的基础上（红色），直接在其内部挖掉另一个``小''短语（绿色），这样就生成了一个层次短语规则。

\parinterval 这种方式可以抽取出大量的层次短语规则。但是，不加限制的抽取，会带来规则集合的过度膨胀，对解码系统造成很大负担。比如，如果考虑任意长度的短语会使得层次短语规则过大，一方面这些规则很难在测试数据上被匹配，另一方面抽取这样的``长''规则会使得抽取算法变慢，而且规则数量猛增之后难以存储。还有，如果一个层次短语规则中含有过多的变量，也会导致解码算法变得更加复杂，不利于系统实现和调试。针对这些问题，在标准的层次短语系统中会考虑一些限制，包括：

\begin{itemize}
\vspace{0.5em}
\item 抽取的规则最多可以跨越10个词；
\vspace{0.5em}
\item 规则的（源语言端）变量个数不能超过2；
\vspace{0.5em}
\item 规则的（源语言端）变量不能连续出现。
\vspace{0.5em}
\end{itemize}
\parinterval 在具体实现时还会考虑其他的限制，比如，限定规则的源语言端终结符数量的上限等。

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

\subsection{翻译模型及特征}

\parinterval 在层次短语模型中，每个翻译推导都有一个模型得分$\textrm{score}(d,\mathbf{s},\mathbf{t})$。$\textrm{score}(d,\mathbf{s},\mathbf{t})$是若干特征的线性加权之和：$\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})$是特征函数。层次短语模型的特征包括与规则相关的特征和语言模型特征，如下：

\parinterval 对于每一条翻译规则LHS$\to \langle \alpha, \beta ,\sim \rangle$，有：

\begin{itemize}
\vspace{0.5em}
\item 	(h1-2)短语翻译概率（取对数），即$\textrm{log}(\textrm{P}(\alpha \mid \beta))$和$\textrm{log}(\textrm{P}(\beta \mid \alpha))$，特征的计算与基于短语的模型完全一样；
\vspace{0.5em}
\item 	(h3-4)词汇化翻译概率（取对数），即$\textrm{log}(\textrm{P}_{\textrm{lex}}(\alpha \mid \beta))$和$\textrm{log}(\textrm{P}(\beta \mid \alpha))$，特征的计算与基于短语的模型完全一样；
\vspace{0.5em}
\item (h5)翻译规则数量，让模型自动学习对规则数量的偏好，同时避免使用过少规则造成分数偏高的现象；
\vspace{0.5em}
\item (h6)胶水规则数量，让模型自动学习使用胶水规则的偏好；
\vspace{0.5em}
\item (h7)短语规则数量，让模型自动学习使用纯短语规则的偏好。
\vspace{0.5em}
\end{itemize}

\parinterval 这些特征可以被具体描述为：
\begin{eqnarray}
h_i (d,\mathbf{t},\mathbf{s})=\sum_{r \in d}h_i (r)
\label{eq:4-25}
\end{eqnarray}

\parinterval 公式\ref{eq:4-25}中，$r$表示推导$d$中的一条规则，$h_i (r)$表示规则$r$上的第$i$个特征。可以看出，推导$d$的特征值就是所有包含在$d$中规则的特征值的和。进一步，可以定义
\begin{eqnarray}
\textrm{rscore}(d,\mathbf{t},\mathbf{s})=\sum_{i=1}^7 \lambda_i \cdot h_i (d,\mathbf{t},\mathbf{s})
\label{eq:4-26}
\end{eqnarray}

\parinterval 最终，模型得分被定义为：
\begin{eqnarray}
\textrm{score}(d,\mathbf{t},\mathbf{s})=\textrm{rscore}(d,\mathbf{t},\mathbf{s})+ \lambda_8 \textrm{log}⁡(\textrm{P}_{\textrm{lm}}(\mathbf{t}))+\lambda_9 \mid \mathbf{t} \mid
\label{eq:4-27}
\end{eqnarray}

\noindent 其中：

\begin{itemize}
\vspace{0.5em}
\item $\textrm{log}⁡(\textrm{P}_{\textrm{lm}}(\textrm{t}))$表示语言模型得分；
\vspace{0.5em}
\item $\mid \textrm{t} \mid$表示译文的长度。
\vspace{0.5em}
\end{itemize}

\parinterval 在定义特征函数之后，特征权重$\{ \lambda_i \}$可以通过最小错误率训练在开发集上进行调优。关于最小错误率训练可以参考\ref{subsection-4.2.6}节的内容。

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

\subsection{CKY解码}\label{subsection-4.3.4}

\parinterval 层次短语模型解码的目标是找到模型得分最高的推导，即：
\begin{eqnarray}
\hat{d} = \arg\max_{d} \textrm{score}(d,\mathbf{s},\mathbf{t})
\label{eq:4-28}
\end{eqnarray}

\parinterval $\hat{d}$的目标语部分即最佳译文$\hat{\mathbf{t}}$。令函数$t(\cdot)$返回翻译推导的目标语词串，于是有：
\begin{eqnarray}
\hat{\mathbf{t}}=t(\hat{d})
\label{eq:4-29}
\end{eqnarray}

\parinterval 由于层次短语规则本质上就是CFG规则，因此公式\ref{eq:4-28}代表了一个典型的句法分析过程。需要做的是，用模型源语言端的CFG对输入句子进行分析，同时用模型目标语言端的CFG生成译文。基于CFG的句法分析是自然语言处理中的经典问题。一种广泛使用的方法是：首先把CFG转化为$\varepsilon$-free的{\small\bfnew{乔姆斯基范式}}\index{乔姆斯基范式}（Chomsky Normal Form）\index{Chomsky Normal Form}\footnote[5]{能够证明任意的CFG都可以被转换为乔姆斯基范式，即文法只包含形如A$\to$BC或A$\to$a的规则。这里，假设文法中不包含空串产生式A$\to\varepsilon$，其中$\varepsilon$表示空字符串。}，之后采用CKY方法进行分析。

\parinterval CKY是形式语言中一种常用的句法分析方法\cite{cocke1969programming,younger1967recognition,kasami1966efficient}。它主要用于分析符合乔姆斯基范式的句子。由于乔姆斯基范式中每个规则最多包含两叉（或者说两个变量），因此CKY方法也可以被看作是基于二叉规则的一种分析方法。对于一个待分析的字符串，CKY方法从小的``范围''开始，不断扩大分析的``范围''，最终完成对整个字符串的分析。在CKY方法中，一个重要的概念是{\small\bfnew{跨度}}\index{跨度}（Span）\index{Span}，所谓跨度表示了一个符号串的范围。这里可以把跨度简单的理解为从一个起始位置到一个结束位置中间的部分。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-word-and-index-of-pos}
\caption{一个单词串及位置索引}
\label{fig:8-5}
\end{figure}
%-------------------------------------------

比如，如图\ref{fig:8-5} 所示，每个单词左右都有一个数字来表示序号。可以用序号的范围来表示跨度，例如：
\begin{eqnarray}
span\textrm{[0,1]}&=&\textrm{``猫''} \nonumber \\
span\textrm{[2,4]}&=&\textrm{``吃} \quad \textrm{鱼''} \nonumber \\
span\textrm{[0,4]}&=&\textrm{``猫} \quad \textrm{喜欢} \quad \textrm{吃} \quad \textrm{鱼''} \nonumber
\end{eqnarray}

\parinterval CKY方法是按跨度由小到大的次序执行的，这也对应了一种{\small\bfnew{自下而上的分析}}\index{自下而上的分析}（Top-down Parsing）\index{Top-down Parsing}过程。对于每个跨度，检查：

\begin{itemize}
\vspace{0.5em}
\item 	是否有形如A$\to$a的规则可以匹配；
\vspace{0.5em}
\item 	是否有形如A$\to$BC的规则可以匹配。
\vspace{0.5em}
\end{itemize}

\parinterval 对于第一种情况，简单匹配字符串即可；对于第二种情况，需要把当前的跨度进一步分割为两部分，并检查左半部分是否已经被归纳为B，右半部分是否已经被归纳为C。如果可以匹配，会在这个跨度上保存匹配结果。后面，可以访问这个结果（也就是A）来生成更大跨度上的分析结果。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-cky-algorithm}
\caption{CKY算法}
\label{fig:8-6}
\end{figure}
%-------------------------------------------

\parinterval CKY算法的伪代码如图\ref{fig:8-6}所示。整个算法的执行顺序是按跨度的长度（$l$）组织的。对于每个$span[j,j + l]$，会在位置$k$进行切割。之后，判断$span[j,k]$和$span[k,j +l]$是否可以形成一个规则的右部。也就是判断$span[j,k]$是否生成了B，同时判断$span[k,j + l]$是否生成了C，如果文法中有规则A$\to$BC，则把这个规则放入$span[j,j+l]$。这个过程由Compose函数完成。如果$span[j,j + l]$可以匹配多条规则，所有生成的推导都会被记录在$span[j,j + l]$所对应的一个列表里\footnote[6]{通常，这个列表会用优先队列实现。这样可以对推导按模型得分进行排序，方便后续的剪枝操作。}。

%----------------------------------------------
\begin{figure}[t]
\centering
\input{./Chapter8/Figures/figure-example-of-cky-algorithm-execution-label}
\input{./Chapter8/Figures/figure-example-of-cky-algorithm-execution}
\caption{CKY算法执行实例}
\label{fig:8-7}
\end{figure}
%----------------------------------------------

\parinterval 图\ref{fig:8-7}展示了CKY方法的一个运行实例（输入词串是aabbc）。算法在处理完最后一个跨度后会得到覆盖整个词串的分析结果，即句法树的根结点S。

\parinterval 不过，CKY方法并不能直接用于层次短语模型。有两个问题：

\begin{itemize}
\vspace{0.5em}
\item 层次短语模型的文法不符合乔姆斯基范式；
\vspace{0.5em}
\item 机器翻译中需要语言模型。由于当前词的语言模型得分需要前面的词做条件，因此机器翻译的解码过程并不是上下文无关的。
\vspace{0.5em}
\end{itemize}

\parinterval 解决第一个问题有两个思路：

\begin{itemize}
\vspace{0.5em}
\item 把层次短语文法转化为乔姆斯基范式，这样可以直接使用原始的CKY方法进行分析；
\vspace{0.5em}
\item 对CKY方法进行改造。解码的核心任务要知道每个跨度是否能匹配规则的源语言部分。实际上，层次短语模型的文法是一种特殊的文法。这种文法规则的源语言部分最多包含两个变量，而且变量不能连续。这样的规则会对应一种特定类型的模版，比如，对于包含两个变量的规则，它的源语言部分形如$\alpha_0 \textrm{X}_1 \alpha_1 \textrm{X}_2 \alpha_2$。其中，$\alpha_0$、$\alpha_1$和$\alpha_2$表示终结符串，$\textrm{X}_1$和$\textrm{X}_2$是变量。显然，如果$\alpha_0$、$\alpha_1$和$\alpha_2$确定下来那么$\textrm{X}_1$和$\textrm{X}_2$的位置也就确定了下来。因此，对于每一个词串，都可以很容易的生成这种模版，进而完成匹配。而$\textrm{X}_1$和$\textrm{X}_2$和原始CKY中匹配二叉规则本质上是一样的。由于这种方法并不需要对CKY方法进行过多调整，因此层次短语系统中广泛使用这种改造的CKY方法进行解码。
\vspace{0.5em}
\end{itemize}

\parinterval 对于语言模型在解码中的集成问题，一种简单的办法是：在CKY分析的过程中，用语言模型对每个局部的翻译结果进行评价，并计算局部翻译（推导）的模型得分。注意，局部的语言模型得分可能是不准确的，比如，局部翻译片段最左边单词的概率计算需要依赖前面的单词。但是由于每个跨度下生成的翻译是局部的，当前跨度下看不到前面的译文。这时会用1-gram语言模型的得分代替真实的高阶语言模型得分。等这个局部翻译片段和其他片段组合之后，可以知道前文的内容，这时才会得出最终的语言模型得分。

\parinterval 另一种解决问题的思路是，先不加入语言模型，这样可以直接使用CKY方法进行分析。在得到最终的结果后，对最好的多个推导用含有语言模型的完整模型进行打分，选出最终的最优推导。

\parinterval 不过，在实践中发现，由于语言模型在机器翻译中起到至关重要的作用，因此对最终结果进行重排序会带来一定的性能损失。不过这种方法的优势在于速度快，而且容易实现。另外，在实践时，还需要考虑两方面问题：

\begin{itemize}
\vspace{0.5em}
\item 剪枝：在CKY中，每个跨度都可以生成非常多的推导（局部翻译假设）。理论上，这些推导的数量会和跨度大小成指数关系。显然不可能保存如此大量的翻译推导。对于这个问题，常用的办法是只保留top-$k$个推导。也就是每个局部结果只保留最好的$k$个。这种方法也被称作{\small\bfnew{束剪枝}}\index{束剪枝}（Beam Pruning）\index{Beam Pruning}。在极端情况下，当$k$=1时，这个方法就变成了贪婪的方法；
\vspace{0.5em}
\item $n$-best结果的生成：$n$-best推导（译文）的生成是统计机器翻译必要的功能。比如，最小错误率训练中就需要最好的$n$个结果用于特征权重调优。在基于CKY的方法中，整个句子的翻译结果会被保存在最大跨度所对应的结构中。因此一种简单的$n$-best生成方法是从这个结构中取出排名最靠前的$n$个结果。另外，也可以考虑自上而下遍历CKY生成的推导空间，得到更好的$n$-best结果\cite{huang2005better}。
\end{itemize}

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

\subsection{立方剪枝}

\parinterval 相比于基于短语的模型，基于层次短语的模型引入了``变量''的概念。这样，可以根据变量周围的上下文信息对变量进行调序。变量的内容由其所对应的跨度上的翻译假设进行填充。图\ref{fig:8-8}展示了一个层次短语规则匹配词串的实例。可以看到，规则匹配词串之后，变量X的位置对应了一个跨度。这个跨度上所有标记为X的局部推导都可以作为变量的内容。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-hierarchical-phrase-rule-match-generate}
\caption{层次短语规则匹配及译文生成}
\label{fig:8-8}
\end{figure}
%-------------------------------------------

\parinterval 真实的情况会更加复杂。对于一个规则的源语言端，可能会有多个不同的目标语言端与之对应。比如，如下规则的源语言端完全相同，但是译文不同：
\begin{eqnarray}
\textrm{X} & \to & \langle\ \textrm{X}_1\ \text{大幅度}\ \text{下降}\ \text{了},\ \textrm{X}_1\ \textrm{have}\ \textrm{drastically}\ \textrm{fallen}\ \rangle \nonumber \\
\textrm{X} & \to & \langle\ \textrm{X}_1\ \text{大幅度}\ \text{下降}\ \text{了},\ \textrm{X}_1\ \textrm{have}\ \textrm{fallen}\ \textrm{drastically}\ \rangle \nonumber \\
\textrm{X} & \to & \langle\ \textrm{X}_1\ \text{大幅度}\ \text{下降}\ \text{了},\ \textrm{X}_1\ \textrm{has}\ \textrm{drastically}\ \textrm{fallen}\ \rangle \nonumber
\end{eqnarray}

\parinterval 这也就是说，当匹配规则的源语言部分``$\textrm{X}_1$ 大幅度 下降 了''时会有三个译文可以选择。而变量$\textrm{X}_1$部分又有很多不同的局部翻译结果。不同的规则译文和不同的变量译文都可以组合出一个局部翻译结果。图\ref{fig:8-9}展示了这种情况的实例。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-combination-of-translation-with-different-rules}
\caption{不同规则目标语端及变量译文的组合}
\label{fig:8-9}
\end{figure}
%-------------------------------------------

\parinterval 假设有$n$个规则源语言端相同，规则中每个变量可以被替换为$m$个结果，对于只含有一个变量的规则，一共有$nm$种不同的组合。如果规则含有两个变量，这种组合的数量是$n{m}^2$。由于翻译中会进行大量的规则匹配，如果每个匹配的源语言端都考虑所有$n{m}^2$种译文的组合，解码速度会很慢。

\parinterval 在层次短语系统中，会进一步对搜索空间剪枝。简言之，此时并不需要对所有$n{m}^2$种组合进行遍历，而是只考虑其中的一部分组合。这种方法也被称作{\small\bfnew{立方剪枝}}\index{立方剪枝}（Cube Pruning）\index{Cube Pruning}。所谓`` 立方''是指组合译文时的三个维度：规则的目标语端、第一个变量所对应的翻译候选、第二个变量所对应的翻译候选。立方剪枝假设所有的译文候选都经过排序，比如，按照短语翻译概率排序。这样，每个译文都对应一个坐标，比如，$(i,j,k)$就表示第$i$个规则目标语端、第二个变量的第$j$个翻译候选、第三个变量的第$k$个翻译候选的组合。于是，可以把每种组合看作是一个三维空间中的一个点。在立方剪枝中，开始的时候会看到$(0,0,0)$这个翻译假设，并把这个翻译假设放入一个优先队列中。之后每次从这个优先队里中弹出最好的结果，之后沿着三个维度分别将坐标加1，比如，如果优先队列弹出$(i,j,k)$，则会生成$(i+1,j,k)$、$(i,j+1,k)$和$(i,j,k+1)$这三个新的翻译假设。之后，计算出它们的模型得分，并压入优先队列。这个过程不断被执行，直到达到终止条件，比如，扩展次数达到一个上限。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-execution-of-cube-pruning}
\caption{立方剪枝执行过程（行表示规则，列表示变量可替换的内容）}
\label{fig:8-10}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:8-10}展示了立方剪枝的过程（规则只含有一个变量的情况）。可以看到，每个步骤中，算法只会扩展当前最好结果周围的两个点（对应两个维度，横轴对应变量被替换的内容，纵轴对应规则的目标语端）。

\parinterval 理论上，立方剪枝最多访问$n{m}^2$个点。但是在实践中发现，如果终止条件设计的合理，搜索的代价基本上与$m$或者$n$呈线性关系。因此，立方剪枝可以大大提高解码速度。立方剪枝实际上是一种启发性的搜索方法。它把搜索空间表示为一个三维空间。它假设：如果空间中某个点的模型得分较高，那么它``周围''的点的得分也很可能较高。这也是对模型得分沿着空间中不同维度具有连续性的一种假设。这种方法也大量的使用在句法分析中，并取得了很好的效果。

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

\sectionnewpage
\section{基于语言学句法的模型}\label{section-4.4}

\parinterval 层次短语模型是一种典型的基于翻译文法的模型。它把翻译问题转化为语言分析问题。在翻译一个句子的时候，模型会生成一个树形结构，这样也就得到了句子结构的某种表示。图\ref{fig:4-41}展示了一个使用层次短语系统进行翻译时所生成的翻译推导$d$，以及这个推导所对应的树形结构（源语言）。这棵树体现了机器翻译的视角下的句子结构，尽管这个结构并不是人类语言学中的句法树。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-derivation-of-hierarchical-phrase-and-tree-structure-model}
\setlength{\belowcaptionskip}{-0.5em}
\caption{层次短语模型所对应的翻译推导及树结构（源语言）}
\label{fig:4-41}
\end{figure}
%-------------------------------------------

\parinterval 在翻译中使用树结构的好处在于，模型可以更加有效地对句子的层次结构进行抽象。而且树结构可以作为对序列结构的一种补充，比如，在句子中距离较远的两个单词，在树结构中可以很近。不过，层次短语模型也存在一些不足：

\begin{itemize}
\vspace{0.5em}
\item 层次短语规则没有语言学句法标记，很多规则并不符合语言学认知，因此译文的生成和调序也不遵循语言学规律。比如，层次短语系统经常会把完整的句法结构打散，或者``破坏''句法成分进行组合；
\vspace{0.5em}
\item 层次短语系统中有大量的工程化约束条件。比如，规则的源语言部分不允许两个变量连续出现，而且变量个数也不能超过两个。这些约束在一定程度上限制了模型处理翻译问题的能力。
\vspace{0.5em}
\end{itemize}

\parinterval 实际上，基于层次短语的方法可以被看作是介于基于短语的方法和基于语言学句法的方法之间的一种折中。它的优点在于，具备短语模型简单、灵活的优点，同时，由于同步翻译文法可以对句子的层次结构进行表示，因此也能够处理一些较长距离的调序问题。但是，另一方面，层次短语模型并不是一种``精细''的句法模型，当翻译需要复杂的结构信息时，这种模型可能会无能为力。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-examples-of-translation-with-complex-ordering}
\setlength{\belowcaptionskip}{-0.5em}
\caption{含有复杂调序的翻译实例（汉语翻译到英语）}
\label{fig:4-42}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:4-42}展示了一个翻译实例，对图中句子进行翻译需要通过复杂的调序才能生成正确译文。为了完成这样的翻译，需要对多个结构（超过两个）进行调序，但是这种情况在标准的层次短语系统中是不允许的。

\parinterval 从这个例子中可以发现，如果知道源语言的句法结构，翻译其实并不``难''。比如，语言学句法结构可以告诉模型句子的主要成分是什么，而调序实际上是在这些成分之间进行的。从这个角度说，语言学句法可以帮助模型进行更上层结构的表示和调序。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-phrase-structure-tree-and-dependency-tree}
\setlength{\belowcaptionskip}{-1.0em}
\caption{短语结构树 vs 依存树}
\label{fig:4-43}
\end{figure}
%-------------------------------------------

\parinterval 显然，使用语言学句法对机器翻译进行建模也是一种不错的选择。不过，语言学句法有很多种，因此首先需要确定使用何种形式的句法。比如，在自然语言处理中经常使用的是短语结构分析和依存分析（图\ref{fig:4-43}）。二者的区别已经在第二章进行了讨论。

\parinterval 在机器翻译中，上述这两种句法信息都可以被使用。不过为了后续讨论的方便，这里仅介绍基于短语结构树的机器翻译建模。使用短语结构树的原因在于，它提供了较为丰富的句法信息，而且相关句法分析工具比较成熟。如果没有特殊说明，本章中所提到的句法树都是指短语结构树（或成分句法树），有时也会把句法树简称为树。此外，这里也假设所有句法树都可以由句法分析器自动生成\footnote[7]{对于汉语、英语等大语种，句法分析器的选择有很多。不过，对于一些小语种，句法标注数据有限，句法分析可能并不成熟，这时在机器翻译中使用语言学句法信息会面临较大的挑战。}。

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

\subsection{基于句法的翻译模型分类}

\parinterval 可以说基于句法的翻译模型贯穿了现代统计机器翻译的发展历程。从概念上讲，不管是层次短语模型，还是语言学句法模型都是基于句法的模型。基于句法的机器翻译模型种类繁多，这里先对相关概念进行简要介绍，以避免后续论述中产生歧义。表\ref{tab:4-2}给出了基于句法的机器翻译中涉及的一些概念。

%----------------------------------------------
\begin{table}[htp]{
\begin{center}
\caption{基于句法的机器翻译中常用概念}
\label{tab:4-2}
{
\begin{tabular}{p{6.5em} | l}
术语 & 说明 \\
\hline
\rule{0pt}{15pt}翻译规则 & 翻译的最小单元（或步骤） \\
\rule{0pt}{15pt}推导 & 由一系列规则组成的分析或翻译过程，推导可以被看作是规\\
&则的序列 \\
\rule{0pt}{15pt}规则表 & 翻译规则的存储表示形式，可以高效进行查询 \\
\rule{0pt}{15pt}层次短语模型 & 基于同步上下文无关文法的翻译模型，非终结符只有S和X\\
&两种，文法并不需要符合语言学句法约束 \\
\rule{0pt}{15pt}树到串模型 & 一类翻译模型，它使用源语语言学句法树，因此翻译可以被\\
&看作是从一颗句法树到词串的转换 \\
\rule{0pt}{15pt}串到树模型 & 一类翻译模型，它使用目标语语言学句法树，因此翻译可以\\
&被看作是从词串到句法树的转换 \\
\rule{0pt}{15pt}树到树模型 & 一类翻译模型，它同时使用源语和目标语语言学句法树，因\\
&此翻译可以被看作从句法树到句法树的转换 \\
\rule{0pt}{15pt}基于句法 & 使用语言学句法 \\
\rule{0pt}{15pt}基于树 &（源语言）使用树结构（大多指句法树） \\
\rule{0pt}{15pt}基于串 &（源语言）使用词串，比如串到树翻译系统的解码器一般\\
&都是基于串的解码方法 \\
\rule{0pt}{15pt}基于森林 &（源语言）使用句法森林，这里森林只是对多个句法树的一 \\
&种压缩表示
\end{tabular}
}
\end{center}
}\end{table}
\begin{table}[htp]{
\begin{center}
{
\begin{tabular}{p{6.5em} | l}
术语 & 说明 \\
\hline
\rule{0pt}{15pt}词汇化规则 & 含有终结符的规则 \\
\rule{0pt}{15pt}非词汇规则 & 不含有终结符的规则 \\
\rule{0pt}{15pt}句法软约束 & 不强制规则推导匹配语言学句法树，通常把句法信息作为特\\
&征使用 \\
\rule{0pt}{15pt}句法硬约束 & 要求推导必须符合语言学句法树，不符合的推导会被过滤掉 \\
\end{tabular}
}
\end{center}
}\end{table}
%----------------------------------------------

\parinterval 基于句法的翻译模型可以被分为两类：基于形式化文法的模型和语言学上基于句法的模型（图\ref{fig:4-44}）。基于形式化文法的模型的典型代表包括，吴德恺提出的基于反向转录文法的模型\cite{wu1997stochastic}和David Chiang提出的基于层次短语的模型\cite{chiang2007hierarchical}。而语言学上基于句法的模型包括，句法树到串的模型\cite{liu2006tree,huang2006statistical}、串到句法树的模型\cite{galley2006scalable,galley2004s}、句法树到句法树的模型\cite{eisner2003learning,zhang2008tree,liu2009improving,chiang2010learning}等。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-classification-of-models-based-on-syntax}
\caption{基于句法的机器翻译模型的分类}
\label{fig:4-44}
\end{figure}
%-------------------------------------------

\parinterval 通常来说，基于形式化文法的模型并不需要句法分析技术的支持。这类模型只是把翻译过程描述为一系列形式化文法规则的组合过程。而语言学上基于句法的模型则需要源语言和（或者）目标语言句法分析的支持，以获取更丰富的语言学信息来提高模型的翻译能力。这也是本节所关注的重点。当然，所谓分类也没有唯一的标准，比如，还可以把句法模型分为基于软约束的模型和基于硬约束的模型，或者分为基于树的模型和基于串的模型。

%----------------------------------------------
\begin{table}[htp]{
\begin{center}
\caption{基于句法的机器翻译模型对比}
\label{tab:4-3}
{
\begin{tabular}{l | l | l | l | l}
模型 & 形式句法 & \multicolumn{3}{c}{语言学句法} \\
\cline{3-5}
\rule{0pt}{15pt} & & \multicolumn{1}{c|}{树到串} & \multicolumn{1}{c}{串到树} & \multicolumn{1}{|c}{树到树} \\
\hline
源语句法 & No & Yes & No & Yes \\
目标语句法 & No & No & Yes & Yes \\
基于串的解码 & Yes & No & Yes & Yes \\
基于树的解码 & No & Yes & No & Yes \\
健壮性 & High & Mid & Mid & Low \\
\end{tabular}
}
\end{center}
}\end{table}
%-------------------------------------------

\parinterval 表\ref{tab:4-3}进一步对比了不同模型的区别。其中，树到串和树到树模型都使用了源语言句法信息，串到树和树到树模型使用了目标语言句法信息。不过，这些模型都依赖句法分析器的输出，因此会对句法分析的错误比较敏感。相比之下，基于形式文法的模型并不依赖句法分析器，因此会更健壮一些。

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

\subsection{基于树结构的文法}

\parinterval 基于句法的翻译模型的一个核心问题是要对树结构进行建模，进而完成树之间或者树和串之间的转换。在计算机领域中，所谓树就是由一些节点组成的层次关系的集合。计算机领域的树和自然世界中的树没有任何关系，只是借用了相似的概念，因为这种层次结构很像一个倒过来的树。在使用树时，经常会把树的层次结构转化为序列结构，称为树结构的{\small\bfnew{序列化}}\index{序列化}或者{\small\bfnew{线性化}}\index{线性化}（Linearization）\index{Linearization}。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-different-representations-of-syntax-tree}
\caption{树结构的不同表示形式}
\label{fig:4-45}
\end{figure}
%-------------------------------------------

\parinterval 比如，使用树的先序遍历就可以得到一个树的序列表示。图\ref{fig:4-45}就对比了同一棵树的不同表示方式。实际上，树的序列表示是非常适合计算机进行读取和处理的。因此，本章也会使用树的序列化结果来表示句法结构。

\parinterval 在基于语言学句法的机器翻译中，两个句子间的转化仍然需要使用文法规则进行描述。有两种类型的规则：

\begin{itemize}
\vspace{0.5em}
\item {\small\bfnew{树到串翻译规则}}\index{树到串翻译规则}（Tree-to-String Translation Rule）\index{Tree-to-String Translation Rule}：在树到串、串到树模型中使用；
\vspace{0.5em}
\item {\small\bfnew{树到树翻译规则}}\index{树到树翻译规则}（Tree-to-Tree Translation Rule）\index{Tree-to-Tree Translation Rule}：在树到树模型中使用。
\vspace{0.5em}
\end{itemize}

\parinterval 树到串规则描述了一端是树结构而另一端是串的情况，因此树到串模型和串到树模型都可以使用这种形式的规则。树到树模型需要在两种语言上同时使用句法树结构，需要树到树翻译规则。

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

\subsubsection{树到树翻译规则}

\parinterval 虽然树到串翻译规则和树到树翻译规则蕴含了不同类型的翻译知识，但是它们都在描述一个结构（树/串）到另一个结构（树/串）的映射。这里采用了一种更加通用的文法\ \dash \ 基于树结构的文法\ \dash \ 将树到串翻译规则和树到树翻译规则进行统一。定义如下：

%-------------------------------------------
\vspace{0.5em}
\begin{definition} 基于树结构的文法

{\small
一个基于树结构的文法由七部分构成$(N_s, N_t, T_s, T_t, I_s, I_t, R)$，其中
\begin{enumerate}
\item $N_s$和$N_t$是源语言和目标语言非终结符集合；
\item $T_s$和$T_t$是源语言和目标语言终结符集合；
\item $I_s \subseteq N_s$和$I_t \subseteq N_t$是源语言和目标语言起始非终结符集合；
\item $R$是规则集合，每条规则$r \in R$有如下形式：
\vspace{-1em}
\begin{displaymath}
\langle\  \alpha_h, \beta_h\ \rangle \to \langle\ \alpha_r, \beta_r, \sim\ \rangle
\end{displaymath}

其中，规则左部由非终结符$\alpha_h \in N_s$和$\beta_h \in N_t$构成；规则右部由三部分组成，$\alpha_r$表示由源语言终结符和非终结符组成的树结构；$\beta_r$ 表示由目标语言终结符和非终结符组成的树结构；$\sim$表示$\alpha_r$和$\beta_r$中叶子非终结符的1-1对应关系。
\end{enumerate}
}
\end{definition}
%-------------------------------------------

\parinterval 基于树结构的规则非常适合于描述树结构到树结构的映射。比如，图\ref{fig:4-46}是一个汉语句法树结构到一个英语句法树结构的对应。其中的树结构可以被看作是完整句法树上的一个片段，称为{\small\bfnew{树片段}}\index{树片段}（Tree Fragment）\index{Tree Fragment}。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-example-of-tree-structure-correspondence}
\vspace{-2em}
\caption{汉语句法树到英语句法树的结构对应}
\label{fig:4-46}
\end{figure}
%-------------------------------------------

\parinterval 树片段的叶子节点既可以是终结符（单词）也可以是非终结符。当叶子节点为非终结符时，表示这个非终结符会被进一步替换，因此它可以被看作是变量。而源语言树结构和目标语言树结构中的变量是一一对应的，对应关系用虚线表示。

\parinterval 这个双语映射关系可以被表示为一个基于树结构的文法规则，套用规则的定义$\langle\  \alpha_h, \beta_h\ \rangle \to \langle\ \alpha_r, \beta_r, \sim\ \rangle$形式，可以知道：
\begin{eqnarray}
\langle\ \alpha_h, \beta_h\ \rangle &=& \langle\ \textrm{VP}, \textrm{VP}\ \rangle \nonumber \\
\alpha_r &=& \textrm{VP}(\textrm{PP:}x\ \textrm{VP(VV(表示)}\ \textrm{NN:}x)) \nonumber \\
\beta_r &=& \textrm{VP}(\textrm{VBZ(was)}\ \textrm{VP(VBN:}x\ \textrm{PP:}x)) \nonumber \\
\sim &=& \{1-2,2-1\} \nonumber
\end{eqnarray}

\parinterval 这里，$\alpha_h$和$\beta_h$表示规则的左部，对应树片段的根节点；$\alpha_r$和$\beta_r$是两种语言的树结构（序列化表示），其中标记为$x$的非终结符是变量。$\sim = \{1-2,2-1\}$表示源语言的第一个变量对应目标语言的第二个变量，而源语言的第二个变量对应目标语言的第一个变量，这也反应出两种语言句法结构中的调序现象。有时候为了化简规则的形式，会把规则中变量的对应关系用下标进行表示。例如，上面的规则也可以被写为如下形式。
\begin{eqnarray}
\langle\ \textrm{VP}, \textrm{VP}\ \rangle\ \to\ \langle\ \textrm{PP}_{1} \ \textrm{VP(VV(表示)}\ \textrm{NN}_{2}))\ \textrm{VP}(\textrm{VBZ(was)}\ \textrm{VP(VBN}_{2} \ \textrm{PP}_{1})) \ \rangle \nonumber
\end{eqnarray}

\noindent 其中，两种语言中变量的对应关系为$\textrm{PP}_1 \leftrightarrow \textrm{PP}_1$，$\textrm{NN}_2 \leftrightarrow \textrm{VBN}_2$。

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

\subsubsection{基于树结构的翻译推导}

\parinterval 规则中的变量预示着一种替换操作，即变量可以被其他树结构替换。实际上，上面的树到树翻译规则就是一种{\small\bfnew{同步树替换文法规则}}\index{同步树替换文法规则}（Synchronous Tree Substitution Grammar Rule）\index{Synchronous Tree Substitution Grammar Rule}。不论是源语言端还是目标语言端，都可以通过这种替换操作不断生成更大的树结构，也就是通过树片段的组合得到更大的树片段。图\ref{fig:4-47}就展示了树替换操作的一个实例。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-operation-of-tree-replace}
\caption{树替换操作（将NN替换为一个树结构）}
\label{fig:4-47}
\end{figure}
%-------------------------------------------

\parinterval 这种方法也可以被扩展到双语的情况。图\ref{fig:4-48}给出了一个使用基于树结构的同步文法生成双语句对的实例。其中，每条规则都同时对应源语言和目标语言的一个树片段（用矩形表示）。变量部分可以被替换，这个过程不断执行。最后，四条规则组合在一起形成了源语言和目标语言的句法树。这个过程也被称作规则的推导。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-based-on-tree-structure-generate-sentence-pairs}
\caption{使用基于树结构的同步文法生成汉英句对}
\label{fig:4-48}
\end{figure}
%-------------------------------------------

\parinterval 规则的推导对应了一种源语言和目标语言树结构的同步生成的过程。比如，使用下面的规则集：
{
\begin{eqnarray}
r_3: \quad \textrm{AD(大幅度)} \rightarrow \textrm{RB(drastically)}\qquad\qquad\qquad\qquad\qquad\qquad\qquad\ \nonumber \\
r_4: \quad \textrm{VV(减少)} \rightarrow \textrm{VBN(fallen)}\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\ \,\nonumber \\
r_6: \quad \textrm{AS(了)} \rightarrow \textrm{VBP(have)}\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\, \nonumber \\
r_7: \quad \textrm{NN(进口)} \rightarrow \textrm{NP(DT(the)}\ \textrm{NNS(imports)} \nonumber\ \qquad\qquad\qquad\qquad\qquad\ \,\\
r_8: \quad \textrm{VP(}\textrm{AD}_1\ \textrm{VP(} \textrm{VV}_2\ \textrm{AS}_3)) \rightarrow \textrm{VP(}\textrm{VBP}_3\ \textrm{ADVP(} \textrm{RB}_1\ \textrm{VBN}_2))\ \nonumber \qquad\ \ \,\\
r_9: \quad \textrm{IP(}\textrm{NN}_1\ \textrm{VP}_2) \rightarrow \textrm{S(}\textrm{NP}_1\ \textrm{VP}_2) \qquad\qquad\qquad\qquad\qquad\qquad\qquad\nonumber\ \ \ \ \,
\end{eqnarray}
}

\noindent 可以得到一个翻译推导：
{\footnotesize
\begin{eqnarray}
&& \langle\ \textrm{IP}^{[1]},\ \textrm{S}^{[1]}\ \rangle \nonumber \\
& \xrightarrow[r_9]{\textrm{IP}^{[1]} \Leftrightarrow \textrm{S}^{[1]}} & \langle\ \textrm{IP(}\textrm{NN}^{[2]}\ \textrm{VP}^{[3]}),\ \textrm{S(}\textrm{NP}^{[2]}\ \textrm{VP}^{[3]})\ \rangle \nonumber \\
& \xrightarrow[r_7]{\textrm{NN}^{[2]} \Leftrightarrow \textrm{NP}^{[2]}} & \langle\ \textrm{IP(NN(进口)}\ \textrm{VP}^{[3]}),\ \textrm{S(NP(DT(the) NNS(imports))}\ \textrm{VP}^{[3]})\ \rangle \nonumber \\
& \xrightarrow[r_8]{\textrm{VP}^{[3]} \Leftrightarrow \textrm{VP}^{[3]}} & \langle\ \textrm{IP(NN(进口)}\ \textrm{VP(AD}^{[4]}\ \textrm{VP(VV}^{[5]}\ \textrm{AS}^{[6]}))), \nonumber \\
&                 & \ \ \textrm{S(NP(DT(the) NNS(imports))}\ \textrm{VP(VBP}^{[6]}\ \textrm{ADVP(RB}^{[4]}\ \textrm{VBN}^{[5]})))\ \rangle \hspace{4.5em} \nonumber \\
& \xrightarrow[r_3]{\textrm{AD}^{[4]} \Leftrightarrow \textrm{RB}^{[4]}} & \langle\ \textrm{IP(NN(进口)}\ \textrm{VP(AD(大幅度)}\ \textrm{VP(VV}^{[5]}\ \textrm{AS}^{[6]}))), \nonumber \\
&                 & \ \ \textrm{S(NP(DT(the) NNS(imports))}\ \textrm{VP(VBP}^{[6]}\ \textrm{ADVP(RB(drastically)}\  \textrm{VBN}^{[5]})))\ \rangle \nonumber \\
& \xrightarrow[r_4]{\textrm{VV}^{[5]} \Leftrightarrow \textrm{VBN}^{[5]}} & \langle\ \textrm{IP(NN(进口)}\ \textrm{VP(AD(大幅度)}\ \textrm{VP(VV(减少)}\ \textrm{AS}^{[6]}))), \hspace{10em} \nonumber \\
&                 & \ \ \textrm{S(NP(DT(the) NNS(imports))}\ \textrm{VP(VBP}^{[6]}\ \nonumber \\
&                 & \ \ \textrm{ADVP(RB(drastically)}\ \textrm{VBN(fallen)})))\ \rangle \nonumber
\end{eqnarray}
\begin{eqnarray}
& \xrightarrow[r_6]{\textrm{AS}^{[6]} \Leftrightarrow \textrm{VBP}^{[6]}} & \langle\ \textrm{IP(NN(进口)}\ \textrm{VP(AD(大幅度)}\ \textrm{VP(VV(减少)}\ \textrm{AS(了)}))), \nonumber \\
&                 & \ \ \textrm{S(NP(DT(the) NNS(imports))}\ \textrm{VP(VBP(have)}\ \nonumber \\
&                 & \ \ \textrm{ADVP(RB(drastically)}\ \textrm{VBN(fallen)})))\ \rangle \hspace{15em} \nonumber
\end{eqnarray}
}

\noindent 其中，箭头$\rightarrow$表示推导之意。显然，可以把翻译看作是基于树结构的推导过程（记为$d$）。因此，与层次短语模型一样，基于语言学句法的机器翻译也是要找到最佳的推导$\hat{d} = \arg\max\textrm{P}(d)$。

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

\subsubsection{树到串翻译规则}

\parinterval 基于树结构的文法可以很好的表示两个树片段之间的对应关系，即树到树翻译规则。那树到串翻译规则该如何表示呢？实际上，基于树结构的文法也同样适用于树到串模型。比如，图\ref{fig:4-49}是一个树片段到串的映射，它可以被看作是树到串规则的一种表示。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-tree-fragment-to-string-mapping}
\caption{树片段到串的映射}
\label{fig:4-49}
\end{figure}
%-------------------------------------------

\noindent 其中，源语言树片段中的叶子结点NN表示变量，它与右手端的变量NN对应。这里仍然可以使用基于树结构的规则对上面这个树到串的映射进行表示。参照规则形式$\langle\  \alpha_h, \beta_h\ \rangle \to \langle\ \alpha_r, \beta_r, \sim\ \rangle$，有：
\begin{eqnarray}
\alpha_h & = & \textrm{VP} \nonumber \\
\beta_h & = & \textrm{VP}\ (=\alpha_h) \nonumber \\
\alpha_r & = & \textrm{VP(VV(提高) NN:}x) \nonumber \\
\beta_r & = & \textrm{VP(increases\ NN:}x) \nonumber \\
\sim & = & \{1-1\} \nonumber
\end{eqnarray}

\parinterval 这里，源语言部分是一个树片段，因此$\alpha_h$和$\alpha_r$很容易确定。对于目标语部分，可以把这个符号串当作是一个单层的树片段，根结点直接共享源语言树片段的根结点，叶子结点就是符号串本身。这样，也可以得到$\beta_h$和$\beta_r$。从某种意义上说，树到串翻译仍然体现了一种双语的树结构，只是目标语部分不是语言学句法驱动的，而是一种借用了源语言句法标记所形成的层次结构。

\parinterval 这里也可以把变量的对齐信息用下标表示，同时将左部两个相同的非终结符合并\footnote[8]{在树到串规则中，$\alpha_h$和$\beta_h$是一样的。}，于是规则可以被写作：
\begin{eqnarray}
\textrm{VP} \rightarrow \langle\ \textrm{VP(VV(提高)}\ \textrm{NN}_1),\ \textrm{increases}\ \textrm{NN}_1\ \rangle \nonumber
\end{eqnarray}

\parinterval 另外，在机器翻译领域，大家习惯把规则看作源语言结构（树/串）到目标语言结构（树/串）的一种映射，因此常常会把上面的规则记为：
\begin{eqnarray}
\textrm{VP(VV(提高)}\ \textrm{NN}_1) \rightarrow \textrm{increases}\ \textrm{NN}_1 \nonumber
\end{eqnarray}

\parinterval 在后面的内容中也会使用这种形式来表示基于句法的翻译规则。

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

\subsection{树到串翻译规则抽取}

\parinterval 基于句法的机器翻译包括两个步骤：文法归纳和解码。其中，文法归纳是指从双语平行数据中自动学习翻译规则及规则所对应的特征；解码是指利用得到的文法对新的句子进行分析，并获取概率最高的翻译推导。

\parinterval 本节首先介绍树到串文法归纳的经典方法 —— GHKM方法\cite{galley2004s,galley2006scalable}。所谓GHKM是四位作者名字的首字母。GHKM方法的输入包括：

\begin{itemize}
\vspace{0.5em}
\item 源语言句子及其句法树；
\vspace{0.5em}
\item 目标语言句子；
\vspace{0.5em}
\item 源语言句子和目标语言句子之间的词对齐。
\vspace{0.5em}
\end{itemize}

\parinterval 它的输出是这个双语句对上的树到串翻译规则。GHKM不是一套单一的算法，它还包括很多技术手段用于增加规则的覆盖度和准确性。下面就具体看看GHKM是如何工作的。

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

\subsubsection{树的切割与最小规则}

\parinterval 获取树到串规则就是要找到源语言树片段与目标语言词串之间的对应关系。一棵句法树会有很多个树片段，那么哪些树片段可以和目标语言词串产生对应关系呢？

\parinterval 在GHKM方法中，源语言树片段和目标语言词串的对应是由词对齐决定的。GHKM假设：一个合法的树到串翻译规则，不应该违反词对齐。这个假设和双语短语抽取中的词对齐一致性约束是一样的（见\ref{subsection-4.2.3}节）。简单来说，规则中两种语言互相对应的部分不应包含对齐到外部的词对齐连接。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-example-of-tree-to-string-rule-and-word-alignment}
\caption{树到串规则与词对齐兼容性示例}
\label{fig:4-50}
\end{figure}
%-------------------------------------------

\parinterval 为了说明这个问题，来看一个例子。图\ref{fig:4-50}包含了一棵句法树、一个词串和它们之间的词对齐结果。图中包含如下规则：
\begin{eqnarray}
\textrm{PP(P(对)}\ \textrm{NP(NN(回答)))} \rightarrow \textrm{with}\ \textrm{the}\ \textrm{answer} \nonumber
\end{eqnarray}

\parinterval 该规则是一条满足词对齐约束的规则（对应于图\ref{fig:4-50}中红色部分），因为不存在从规则的源语言或目标语言部分对齐到规则外部的情况。但是，如下的规则却是一条不合法的规则：
\begin{eqnarray}
\textrm{NN(满意)} \rightarrow \textrm{satisfied} \nonumber
\end{eqnarray}

\parinterval 这是因为，``satisfied''除了对齐到``满意''，还对齐到``表示''。也就是，这条规则会产生歧义，因为``satisfied''不应该只由``满意''生成。

\parinterval 为了能够获得与词对齐相兼容的规则，GHKM引入了几个概念。首先，GHKM方法中定义了Span和Complement Span：

%-------------------------------------------
\vspace{0.5em}
\begin{definition} Span

{\small
对于一个源语言句法树节点，它的Span是这个节点所对应到的目标语言第一个单词和最后一个单词所构成的索引范围。
}
\end{definition}
%-------------------------------------------

%-------------------------------------------
\vspace{0.5em}
\begin{definition} Complement Span

{\small
对于一个源语言句法树节点，它的Complement Span是除了它的祖先和子孙节点外的其他节点Span的并集。
}
\end{definition}
%-------------------------------------------

\parinterval Span定义了每个节点覆盖的源语言片段所对应的目标语言片段。实际上，它表示了目标语言句子上的一个跨度，这个跨度代表了这个源语言句法树节点所能达到的最大范围。因此Span实际上是一个目标语单词索引的范围。Complement Span是与Span相对应的一个概念，它定义了句法树中一个节点之外的部分对应到目标语的范围，但是这个范围并不必须是连续的。

\parinterval 有了Span和Complement Span的定义之后，可以进一步定义：

%-------------------------------------------
\vspace{0.5em}
\begin{definition} 可信节点(Admissible Node)

{\small
对于源语言树节点$node$，如果它的Span和Complement Span不相交，节点$node$就是一个可信节点，否则是一个不可信节点。
}
\end{definition}
%-------------------------------------------

\parinterval 可信节点表示这个树节点$node$和树中的其他部分（不包括$node$的祖先和孩子）没有任何词对齐上的歧义。也就是说，这个节点可以完整的对应到目标语言句子的一个连续范围，不会出现在这个范围中的词对应到其他节点的情况。如果节点不是可信节点，则表示它会引起词对齐的歧义，因此不能作为树到串规则中源语言树片段的根节点或者变量部分。图\ref{fig:4-51}给出了一个可信节点的实例。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-syntax-tree-with-admissible-node}
\caption{标注了可信节点信息的句法树}
\label{fig:4-51}
\end{figure}
%-------------------------------------------

\parinterval 进一步，可以定义树到串模型中合法的树片段：

%-------------------------------------------
\vspace{0.5em}
\begin{definition} 合法的树片段

{\small
如果一个树片段的根节点是可信节点，同时它的叶子节点中的非终结符系节点也是可信节点，那么这个树片段就是不产生词对齐歧义的树片段，也被称为合法的树片段。
}
\end{definition}
%-------------------------------------------

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-translation-rule-based-on-admissible-node}
\caption{根据可信结点得到的树到串翻译规则}
\label{fig:4-52}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:4-52}是一个基于可信节点得到的树到串规则：
\begin{eqnarray}
\textrm{VP(PP(P(对)}\ \textrm{NP(NN(回答)))}\ \textrm{VP}_1) \rightarrow \textrm{VP}_1\ \textrm{with}\ \textrm{the}\ \textrm{answer} \nonumber
\end{eqnarray}

\noindent 其中，蓝色部分表示可以抽取到的规则，显然它的根节点和叶子非终结符节点都是可信节点。由于源语言树片段中包含一个变量（VP），因此需要对VP节点的Span所表示的目标语言范围进行泛化（红色方框部分）。

\parinterval 至此，对于任何一个树片段都能够使用上述方法判断它是否合法。如果合法，就可以抽取相应的树到串规则。但是，枚举句子中的所有树片段并不是一个很高效的方法，因为对于任何一个节点，以它为根的树片段数量随着其深度和宽度的增加呈指数增长。在GHKM方法中，为了避免低效的枚举操作，可以使用另一种方法抽取规则。实际上，可信节点确定了哪些地方可以作为规则的边界（合法树片段的根节点或者叶子节点），可以把所有的可信节点看作是一个{\small\bfnew{边缘集合}}\index{边缘集合}（Frontier Set）\index{Frontier Set}。所谓边缘集合就是定义了哪些地方可以被``切割''，通过这种切割可以得到一个个合法的树片段，这些树片段无法再被切割为更小的合法树片段。图\ref{fig:4-53}给出了一个通过边缘集合定义的树切割。图右侧中的矩形框表示切割得到的树片段。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-tree-cutting-defined-by-edge-nodes}
\caption{根据边缘节点定义的树切割}
\label{fig:4-53}
\end{figure}
%-------------------------------------------

\parinterval 需要注意的是，因为``NP$\rightarrow$PN$\rightarrow$他''对应着一个单目生成的过程，所以这里``NP(PN(他))''被看作是一个最小的树片段。当然，也可以把它当作两个树片段``NP( PN)''和``PN(他)''，不过这种单目产生式往往会导致解码时推导数量的膨胀。因此，这里约定把连续的单目生成看作是一个生成过程，它对应一个树片段，而不是多个。

\parinterval 将树进行切割之后，可以得到若干树片段，每个树片段都可以对应一个树到串规则。由于这些树片段不能被进一步切割，因此这样得到的规则也被称作{\small\bfnew{最小规则}}\index{最小规则}（Minimal Rules）\index{Minimal Rules}。它们就构成了树到串模型中最基本的翻译单元。图\ref{fig:4-54}展示了基于树切割得到的最小规则。其中左侧的每条规则都对应着右侧相同编号的树片段。

%----------------------------------------------
\begin{figure}[htp]
\centering
\begin{tabular}{l l}
\subfigure{\input{./Chapter8/Figures/figure-minimum-rule-from-tree-cutting-1}} &  \subfigure{\input{./Chapter8/Figures/figure-minimum-rule-from-tree-cutting-2}}
\end{tabular}
\caption{基于树切割得到的最小规则实例}
\label{fig:4-54}
\end{figure}
%-------------------------------------------

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

\subsubsection{空对齐处理}

\parinterval 空对齐是翻译中的常见现象。比如，一些虚词经常找不到在另一种语言中的对应，因此不会被翻译，这种情况也被称作空对齐。比如，在图\ref{fig:4-54}中目标语中的``was''就是一个空对齐单词。空对齐的使用可以大大增加翻译的灵活度。具体到树到串规则抽取任务，需要把空对齐考虑进来，这样能够覆盖更多的语言现象。

\parinterval 处理空对齐单词的手段非常简单。只需要把空对齐单词附着在它周围的规则上即可。也就是，检查每条最小规则，如果空对齐单词能够作为规则的一部分进行扩展，就可以生成一条新的规则。

%----------------------------------------------
\begin{figure}[htp]
\centering
\begin{tabular}{l l}
\subfigure{\input{./Chapter8/Figures/figure-tree-to-string-rule-empty-alignment-1}} &  \subfigure{\input{./Chapter8/Figures/figure-tree-to-string-rule-empty-alignment-2}}
\end{tabular}
\caption{树到串规则抽取中空对齐单词的处理（绿色矩形）}
\label{fig:4-55}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:4-55}展示了前面例子中``was''被附着在周围的规则上的结果。其中，含有红色``was''的规则是通过附着空对齐单词得到的新规则。比如，对于规则：
\begin{eqnarray}
\textrm{NP(PN(他))} \rightarrow \textrm{he} \nonumber
\end{eqnarray}

\parinterval ``was''紧挨着这个规则目标端的单词``he''，因此可以把``was''包含在规则的目标端，形成新的规则：
\begin{eqnarray}
\textrm{NP(PN(他))} \rightarrow \textrm{he}\ \textrm{was} \nonumber
\end{eqnarray}

\parinterval 通常，在规则抽取中考虑空对齐可以大大增加规则的覆盖度。

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

\subsubsection{组合规则}

\parinterval 最小规则是句法翻译模型中最小的翻译单元。但是，在翻译复杂句子的时候，往往需要更大范围的上下文信息，比如，本节开始图\ref{fig:4-42}中的例子，需要一条规则同时处理多个变量的调序，而这种规则很可能不是最小规则。为了得到``更大''的规则，一种方法是对最小规则进行组合。得到的规则称为composed-$m$规则，其中$m$表示这个规则是由$m$条最小规则组合而成。

%----------------------------------------------
\begin{figure}[htp]
\centering
\begin{tabular}{l l l}
& \subfigure{\input{./Chapter8/Figures/figure-combine-minimum-rule-1}} &  \subfigure{\input{./Chapter8/Figures/figure-combine-minimum-rule-2}}
\end{tabular}
\caption{对最小规则进行组合（绿色矩形）}
\label{fig:4-56}
\end{figure}
%-------------------------------------------

\parinterval 规则的组合非常简单。只需要在得到最小规则之后，对相邻的规则进行拼装。也就是说，如果某个树片段的根节点出现在另一个树片段的叶子节点处，就可以把它们组合成更大的树片段。图\ref{fig:4-56}给了规则组合的实例。其中，规则1、5、6、7可以组合成一条composed-4规则，这个规则可以进行非常复杂的调序。

\parinterval 在真实系统开发中，组合规则一般会带来明显的性能提升。不过随着组合规则数量的增加，规则集也会膨胀。因此往往需要在翻译性能和文法大小之间找到一种平衡。

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

\subsubsection{SPMT规则}

\parinterval 组合规则固然有效，但并不是所有组合规则都非常好用。比如，在机器翻译中已经发现，如果一个规则含有连续词串（短语），这种规则往往会比较可靠。但是由于句法树结构复杂，获取这样的规则可能会需要很多次规则的组合，规则抽取的效率很低。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-tree-segment-corresponding-to-phrase}
\caption{短语（红色）所对应的树片段（绿色）}
\label{fig:4-57}
\end{figure}
%-------------------------------------------

\parinterval 针对这个问题，一种解决办法是直接从词串出发进行规则抽取。这种方法被称为SPMT方法\cite{marcu2006spmt:}。它的思想是：对于任意一个与词对齐兼容的短语，可以找到包含它的``最小''翻译规则，即SPMT规则。如图\ref{fig:4-57}所示，可以得到短语翻译：
\begin{eqnarray}
\textrm{对}\ \textrm{形式} \rightarrow \textrm{about}\ \textrm{the}\ \textrm{situation} \nonumber
\end{eqnarray}

\parinterval 然后，从这个短语出发向上搜索，找到覆盖这个短语的最小树片段，之后生成规则即可。在这个例子中可以得到SPMT规则：
\begin{eqnarray}
\textrm{VP(P(对)}\ \textrm{NP(NN(局势))}\ \textrm{VP}_1) \rightarrow \textrm{VP}_1\ \textrm{about}\ \textrm{the}\ \textrm{situation} \nonumber
\end{eqnarray}

\parinterval 而这条规则需要组合三条最小规则才能得到，但是在SPMT中可以直接得到。相比规则组合的方法，SPMT方法可以更有效的抽取包含短语的规则。

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

\subsubsection{句法树二叉化}

\parinterval 句法树是使用人类语言学知识归纳出来的一种解释句子结构的工具。比如， CTB\cite{xue2005building}、PTB\cite{DBLP:journals/coling/MarcusSM94}等语料就是常用的训练句法分析器的数据。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-syntax-tree-in-ctb}
\caption{CTB中含有多个分句的句法树结构}
\label{fig:4-58}
\end{figure}
%-------------------------------------------

\parinterval 但是，这些数据的标注中会含有大量的扁平结构，如图\ref{fig:4-58}所示，多个分句可能会导致一个根节点下有很多个分支。这种扁平的结构会给规则抽取带来麻烦。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-tree-binarization}
\caption{一个扁平的句法结构所对应的规则抽取结果}
\label{fig:4-59}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:4-59}给出了一个实例，其中的名词短语（NP），包含四个词，都在同一层树结构中。由于``唐纳德$\ $特朗普''并不是一个独立的句法结构，因此无法抽取类似于下面这样的规则：
\begin{eqnarray}
\textrm{NP(NN(唐纳德))}\ \textrm{NN(特朗普))} \rightarrow \textrm{Trump} \nonumber
\end{eqnarray}

\parinterval 对于这个问题，一种解决办法是把句法树变得更深，使局部的翻译片段更容易被抽取出来。常用的手段是树{\small\bfnew{二叉化}}\index{二叉化}（Binarization）\index{Binarization}。比如，图\ref{fig:4-60}就是一个树二叉化的实例。二叉化生成了一些新的节点（记为X-BAR），其中``唐纳德$\ $特朗普''被作为一个独立的结构体现出来。这样，就能够抽取到规则：
\begin{eqnarray}
&& \textrm{NP-BAR(NN(唐纳德))}\ \textrm{NN(特朗普))} \rightarrow \textrm{Trump} \nonumber \\
&& \textrm{NP-BAR(}\textrm{NN}_1\ \textrm{NP-}\textrm{BAR}_2) \rightarrow \textrm{NN}_1\ \textrm{NP-}\textrm{BAR}_2 \nonumber
\end{eqnarray}

\parinterval 由于树二叉化可以帮助规则抽取得到更细颗粒度的规则，提高规则抽取的召回率，因此成为了基于句法的机器翻译中的常用方法。二叉化方法也有很多不同的实现策略，比如：左二叉化\cite{DBLP:conf/naacl/ZhangHGK06}、右二叉化\cite{Tong2009Better}、基于中心词的二叉化\cite{DBLP:conf/acl/KleinM03,charniak2006multilevel}等。具体实现时可以根据实际情况进行选择。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-result-of-tree-binarization}
\caption{句法树二叉化结果}
\label{fig:4-60}
\end{figure}
%-------------------------------------------

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

\subsection{树到树翻译规则抽取}

\parinterval 树到串/串到树模型只在一个语言端使用句法树，而树到树模型可以同时利用源语言和目标语言句法信息，因此可以更细致地刻画两种语言结构的对应关系，进而更好地完成句法结构的调序和生成。树到树翻译中，需要两端都有树结构的规则，比如：
\begin{eqnarray}
\langle\ \textrm{VP},\textrm{VP}\ \rangle \rightarrow \langle\ \textrm{VP(}\textrm{PP}_1\ \textrm{VP(VV(表示)}\ \textrm{NN}_2\textrm{))}, \nonumber \\
\textrm{VP(VBZ(was)}\ \textrm{VP(}\textrm{VBN}_2\ \textrm{PP}_1\textrm{))}\ \rangle \nonumber
\end{eqnarray}

\parinterval 也可以把它写为如下形式：
\begin{eqnarray}
\textrm{VP(}\textrm{PP}_1\ \textrm{VP(VV(表示)}\ \textrm{NN}_2\textrm{))} \rightarrow \textrm{VP(VBZ(was)}\ \textrm{VP(}\textrm{VBN}_2\ \textrm{PP}_1\textrm{))} \nonumber
\end{eqnarray}

\noindent 其中，规则的左部是源语言句法树结构，右部是目标语言句法树结构，变量的下标表示对应关系。为了获取这样的规则，需要进行树到树规则抽取。最直接的办法是把GHKM方法推广到树到树翻译的情况。比如，可以利用双语结构的约束和词对齐，定义树的切割点，之后找到两种语言树结构的映射关系\cite{liu2009improving}。

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

\subsubsection{基于节点对齐的规则抽取}

\parinterval 不过，GHKM方法的问题在于过于依赖词对齐结果。在树到树翻译中，真正需要的是树结构（节点）之间的对应关系，而不是词对齐。特别是在两端都加入句法树结构约束的情况下，词对齐的错误可能会导致较为严重的规则抽取错误。图\ref{fig:4-61}就给出了一个实例，其中，中文的``了''被错误的对齐到了英文的``the''，导致很多高质量的规则无法被抽取出来。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-tree-to-tree-rule-extraction-base-word-alignment}
\caption{基于词对齐的树到树规则抽取}
\label{fig:4-61}
\end{figure}
%-------------------------------------------

\parinterval 换一个角度来看，词对齐实际上只是帮助模型找到两种语言句法树中节点的对应关系。如果能够直接得到句法树节点的对应，就可以避免掉词对齐的错误。也就是，可以直接使用节点对齐来进行树到树规则的抽取。首先，利用外部的节点对齐工具获得两棵句法树节点之间的对齐关系。之后，将每个对齐的节点看作是树片段的根节点，再进行规则抽取。图\ref{fig:4-62}展示了基于节点对齐的规则抽取结果。

%----------------------------------------------
\begin{figure}[htb]
\centering
\input{./Chapter8/Figures/figure-tree-to-tree-rule-extraction-base-node-alignment}
\caption{基于节点对齐的树到树规则抽取}
\label{fig:4-62}
\end{figure}
%-------------------------------------------

\parinterval 可以看到，节点对齐可以避免词对齐错误造成的影响。不过，节点对齐需要开发额外的工具。有很多方法可以参考，比如可以基于启发性规则\cite{DBLP:conf/coling/GrovesHW04}、基于分类模型\cite{DBLP:conf/coling/SunZT10}、基于无指导的方法\cite{xiao2013unsupervised}等。

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

\subsubsection{基于对齐矩阵的规则抽取}

\parinterval 同词对齐一样，节点对齐也会存在错误，这样就不可避免的造成规则抽取的错误。既然单一的对齐中含有错误，那能否让系统看到更多样的对齐结果，进而提高正确规则被抽取到的几率呢？答案是肯定的。实际上，在基于短语的模型中就有基于多个词对齐（如$n$-best词对齐）进行规则抽取的方法，这种方法可以在一定程度上提高短语的召回率。在树到树规则抽取中也可以使用多个节点对齐结果进行规则抽取。但是，简单使用多个对齐结果会使系统运行代价线性增长，而且即使是$n$-best对齐，也无法保证涵盖到正确的对齐结果。对于这个问题，另一种思路是使用对齐矩阵进行规则的``软''抽取。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-one-best-node-alignment-and-alignment-matrix}
\caption{使用1-best节点对齐和概率化节点对齐矩阵的树到树规则抽取\cite{xiao2013unsupervised}}
\label{fig:4-63}
\end{figure}
%-------------------------------------------

\parinterval 所谓对齐矩阵，是描述两个句法树节点之间对应强度的数据结构。矩阵的每个单元中都是一个0到1之间的数字。规则抽取时，可以认为所有节点之间都存在对齐，这样可以抽取出很多$n$-best对齐中无法覆盖的规则。图\ref{fig:4-63}展示了一个用对齐矩阵的进行规则抽取的实例。其中矩阵1（Matrix 1）表示的标准的1-best节点对齐，矩阵2（Matrix 2）表示的是一种概率化的对齐矩阵。可以看到使用矩阵2可以抽取到更多样的规则。另外，值得注意的是，基于对齐矩阵的方法也同样适用于短语和层次短语规则的抽取。关于对齐矩阵的生成可以参考相关论文的内容\cite{xiao2013unsupervised,liu2009weighted,sun2010exploring,sun2010discriminative}。

\parinterval 此外，在基于句法的规则抽取中，一般会对规则进行一些限制，以避免规则数量过大，系统无法处理。比如，可以限制树片段的深度、变量个数、规则组合的次数等等。这些限制往往需要根据具体任务进行设计和调整。

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

\subsection{句法翻译模型的特征}

\parinterval 基于语言学句法的翻译模型使用判别式模型对翻译推导进行建模（\ref{subsection-4.2.2}节）。给定双语句对($\mathbf{s}$,$\mathbf{t}$)，由$M$个特征经过线性加权，得到每个翻译推导$d$的得分，记为$\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})$表示特征函数。翻译的目标就是要找到使$\textrm{score(}d,\mathbf{t},\mathbf{s})$达到最高的推导$d$。

\parinterval 这里，可以使用最小错误率训练对特征权重进行调优（\ref{subsection-4.2.6}节）。而特征函数可参考如下定义：

\vspace{0.5em}
\parinterval {\small\bfnew{基于短语的特征}}\index{基于短语的特征}（对应于每条规则$r : \langle\  \alpha_h, \beta_h\ \rangle \to \langle\ \alpha_r, \beta_r, \sim\ \rangle$ ）

\begin{itemize}
\vspace{0.5em}
\item (h1-2)短语翻译概率，即规则源语言和目标语言树覆盖的序列翻译概率。令函数$\tau(\cdot)$返回一个树片段的叶子节点序列。对于规则：
\begin{displaymath}
\textrm{VP(}\textrm{PP}_1\ \textrm{VP(VV(表示)}\ \textrm{NN}_2\textrm{))} \rightarrow \textrm{VP(VBZ(was)}\ \textrm{VP(}\textrm{VBN}_2\ \textrm{PP}_1\textrm{))}
\end{displaymath}
\noindent 可以得到：
\begin{eqnarray}
\tau( \alpha_r ) & = & \textrm{PP}\ \textrm{表示}\ \textrm{NN} \nonumber \\
\tau( \beta_r ) & = & \textrm{was}\ \textrm{VBN}\ \textrm{PP} \nonumber
\end{eqnarray}
\noindent 于是，可以定义短语翻译概率为$\textrm{P(}\tau( \alpha_r )|\tau( \beta_r ))$和$\textrm{P(}\tau( \beta_r )|\tau( \alpha_r ))$。它们的计算方法与基于短语的系统是完全一样的\footnote[9]{对于树到串规则，$\tau( \beta_r )$就是规则目标语言端的符号串。}；
\vspace{0.5em}
\item (h3-4) 词汇化翻译概率，即$\textrm{P}_{\textrm{lex}}(\tau( \alpha_r )|\tau( \beta_r ))$和$\textrm{P}_{\textrm{lex}}(\tau( \beta_r )|\tau( \alpha_r ))$。这两个特征的计算方法与基于短语的系统也是一样的。
\vspace{0.5em}
\end{itemize}

\vspace{0.5em}
\parinterval {\small\bfnew{基于句法的特征}}\index{基于句法的特征}（对应于每条规则$r : \langle\  \alpha_h, \beta_h\ \rangle \to \langle\ \alpha_r, \beta_r, \sim\ \rangle$ ）

\begin{itemize}
\vspace{0.5em}
\item (h5)基于根节点句法标签的规则生成概率，即$\textrm{P(}r|\textrm{root(}r\textrm{))}$。这里，$\textrm{root(}r)$是规则所对应的双语根节点$(\alpha_h,\beta_h)$；
\vspace{0.5em}
\item (h6)基于源语言端的规则生成概率，即$\textrm{P(}r|\alpha_r))$，给定源语言端生成整个规则的概率；
\vspace{0.5em}
\item (h7)基于目标语言端的规则生成概率，即$\textrm{P(}r|\beta_r))$，给定目标语言端生成整个规则的概率。
\end{itemize}

\vspace{0.5em}
\parinterval {\small\bfnew{其他特征}}（对应于整个推导$d$）

\begin{itemize}
\vspace{0.5em}
\item (h8)语言模型，即$\textrm{P}_{\textrm{lm}}(\mathbf{t})$，用于度量译文的流畅度；
\vspace{0.5em}
\item (h9)译文长度，即$|\mathbf{t}|$，用于避免模型过于倾向生成短译文（因为短译文语言模型分数高）；
\vspace{0.5em}
\item (h10)翻译规则数量，学习对使用规则数量的偏好。比如，如果这个特征的权重较高，则表明系统更喜欢使用数量多的规则；
\vspace{0.5em}
\item (h11)组合规则的数量，学习对组合规则的偏好；
\vspace{0.5em}
\item (h12)词汇化规则的数量，学习对含有终结符规则的偏好；
\vspace{0.5em}
\item (h13)低频规则的数量，学习对训练数据中出现频次低于3的规则的偏好。低频规则大多不可靠，设计这个特征的目的也是为了区分不同质量的规则。
\end{itemize}

\vspace{0.5em}

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

\subsection{基于超图的推导空间表示}

\parinterval 在完成建模后，剩下的问题是：如何组织这些翻译推导，完成高效的计算？本质上，基于句法的机器翻译与句法分析是一样的，因此关于翻译推导的组织可以借用句法分析中的一些概念。

\parinterval 在句法分析中，上下文无关文法（CFG）的分析过程可以被组织成一个叫{\small\bfnew{有向超图}}\index{有向超图}（Directed Hyper-graph）\index{Directed Hyper-graph}的结构，或者简称为{\small\bfnew{超图}}\cite{ilprints729}：

%-------------------------------------------
\vspace{0.5em}
\begin{definition} 有向超图

{\small
一个有向超图$G$包含一个节点集合$N$和一个有向{\small\bfnew{超边}}\index{超边}（Hyper-edge）\index{Hyper-edge}集合$E$。每个有向超边包含一个头（Head）和一个尾（Tail），头指向$N$中的一个节点，尾是若干个$N$中的节点所构成的集合。
}
\end{definition}
%-------------------------------------------

\parinterval 与传统的有向图不同，超图中的每一个边（超边）的尾可以包含多个节点。也就是说，每个超边从若干个节点出发最后指向同一个节点。这种定义完美契合了CFG的要求。比如，如果把节点看作是一个推导所对应树结构的根节点（含有句法标记），那么每个超边就可以表示一条CFG规则。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-example-of-hyper-graph}
\caption{超图实例}
\label{fig:4-64}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:4-64}就展示了一个简单的超图。其中每个节点都有一个句法标记，句法标记下面记录了这个节点的跨度。超边edge1和edge2分别对应了两条CFG规则：
\begin{eqnarray}
\textrm{VP} \rightarrow \textrm{VV}\ \textrm{NP} \nonumber \\
\textrm{NP} \rightarrow \textrm{NN}\ \textrm{NP} \nonumber
\end{eqnarray}

\parinterval 对于规则``$\textrm{VP} \rightarrow \textrm{VV}\ \textrm{NP}$''，超边的头指向VP，超边的尾表示规则右部的两个变量VV和NP。规则``$\textrm{NP} \rightarrow \textrm{NN}\ \textrm{NP}$''也可以进行类似的解释。

\parinterval 不难发现，超图提供了一种非常紧凑的数据结构来表示多个推导，因为不同推导之间可以共享节点。如果把图\ref{fig:4-64}中的蓝色和红色部分看作是两个推导，那么它们就共享了同一个节点NN[1,2]。能够想象，简单枚举一个句子所有的推导几乎是不可能的，但是用超图的方式却可以很有效地对指数级数量的推导进行表示。另一方面，超图上的运算常常被看作是一种基于半环的代数系统，而且人们发现许多句法分析和机器翻译问题本质上都是{\small\bfnew{半环分析}}\index{半环分析}（Semi-ring Parsing）\index{Semi-ring Parsing}。不过，由于篇幅有限，这里不会对半环等结构展开讨论。感兴趣的读者可以查阅相关文献\cite{goodman1999semiring,eisner2002parameter}。

\parinterval 从句法分析的角度看，超图最大程度地复用了局部的分析结果，使得分析可以``结构化''。比如，有两个推导：
\begin{eqnarray}
d_1 = {r_1} \circ {r_2} \circ {r_3} \circ {r_4} \label{eqa4.30}\\
d_2 = {r_1} \circ {r_2} \circ {r_3} \circ {r_5}
\label{eq:4-31}
\end{eqnarray}

\noindent 其中，$r_1$-$r_5$分别表示不同的规则。${r_1} \circ {r_2} \circ {r_3}$是两个推导的公共部分。在超图表示中，${r_1} \circ {r_2} \circ {r_3}$可以对应一个子图，显然这个子图也是一个推导，记为${d'}= {r_1} \circ {r_2} \circ {r_3}$。这样，$d_1$和$d_2$不需要重复记录${r_1} \circ {r_2} \circ {r_3}$，重新写作：
\begin{eqnarray}
d_1 = {d'} \circ {r_4} \label{eqa4.32}\\
d_1 = {d'} \circ {r_5}
\label{eq:4-33}
\end{eqnarray}

\parinterval 引入$d'$的意义在于，整个分析过程具有了递归性。从超图上看，$d'$可以对应以一个（或几个）节点为``根''的子图，因此只需要在这个（或这些）子图上增加新的超边就可以得到更大的推导。这个过程不断执行，最终完成对整个句子的分析。

\parinterval 在句法分析中，超图的结构往往被组织为一种Chart结构。所谓Chart，就是一个表格，每个格代表了一个跨度，因此可以把所有覆盖这个跨度的推导都放入相应的表格单元（Chart Cell）。对于上下文无关文法，表格里的每一项还会增加一个句法标记，用来区分不同句法功能的推导。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-structure-of-chart}
\caption{Chart结构}
\label{fig:4-65}
\end{figure}
%-------------------------------------------

\parinterval 如图\ref{fig:4-65}所示，覆盖相同跨度的节点会被放入同一个Chart Cell，但是不同句法标记的节点会被看作是不同的项（Item）。这种组织方式建立了一个索引，通过索引可以很容易的访问同一个跨度下的所有推导。比如，如果采用自下而上的分析，可以从小跨度的Chart Cell开始，构建推导，并填写Chart Cell。这个过程中，可以访问之前的Chart Cell来获得所需的局部推导（类似于前面提到的$d'$）。该过程重复执行，直到处理完最大跨度的Chart Cell。而最后一个Chart Cell就保存了完整推导的根节点。通过回溯的方式，能够把所有推导都生成出来。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-hyper-graph-representation-of-machine-translation-derivation}
\caption{机器翻译推导的超图表示}
\label{fig:4-66}
\end{figure}
%-------------------------------------------

\parinterval 基于句法的机器翻译仍然可以使用超图进行翻译推导的表示。和句法分析一样，超图的每条边可以对应一个基于树结构的文法，超边的头代表文法的左部，超边的尾代表规则中变量所对应的超图中的节点\footnote[10]{ 也可以把每个终结符看作是一个节点，这样一个超边的尾就对应规则的树片段中所有的叶子。}。图\ref{fig:4-66} 给出了一个使用超图来表示机器翻译推导的实例。可以看到，超图的结构是按源语言组织的，但是每个规则（超边）会包含目标语言的信息。由于同步翻译文法可以确保规则的源语言端和目标语言端都覆盖连续的词串，因此超图中的每个节点都对应一个源语言跨度，同时对应一个目标语的连续译文。这样，每个节点实际上代表了一个局部的翻译结果。

\parinterval 不过，机器翻译与句法分析也有不同之处。最主要的区别在于机器翻译使用了语言模型作为一个特征，比如$n$-gram语言模型。因为语言模型并不是上下文无关的，因此机器翻译中计算最优推导的方法和句法分析会有不同。常用的方法是，直接在每个Chart Cell中融合语言模型的分数，保留前$k$个结果；或者，在构建超图时不计算语言模型得分，等到构建完整个超图之后对最好的若干个推导用语言模型重新排序；再或者，将译文和语言模型都转化为加权有限状态自动机，之后直接对两个自动机做{\small\bfnew{组合}}\index{组合}（Composition）\index{Composition}得到新的自动机，最后得到融合语言模型得分的译文表示。

\parinterval 基于超图的推导表示方法有着很广泛的应用。比如，\ref{section-4.3}节介绍的层次短语系统也可以使用超图进行建模，因为它也使用了同步文法。从这个角度说，基于层次短语的模型和基于语言学句法的模型本质上是一样的。它们的主要区别在于规则中的句法标记和抽取规则的方法不同。

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

\subsection{基于树的解码 vs 基于串的解码}

\parinterval 解码的目标是找到得分score($d$)最大的推导$d$。这个过程通常被描述为：
\begin{eqnarray}
\hat{d} = \arg\max_d \textrm{score} (d,\mathbf{s},\mathbf{t})
\label{eq:4-34}
\end{eqnarray}

\parinterval 这也是一种标准的{\small\bfnew{基于串的解码}}\index{基于串的解码}（String-based Decoding）\index{String-based Decoding}，即通过句法模型对输入的源语言句子进行翻译得到译文串。不过，搜索所有的推导会导致巨大的解码空间。对于树到串和树到树翻译来说，源语言句法树是可见的，因此可以使用另一种解码方法\ \dash \ {\small\bfnew{基于树的解码}}\index{基于树的解码}（Tree-based Decoding）\index{Tree-based Decoding}，即把输入的源语句法树翻译为目标语串。

%----------------------------------------------
\begin{table}[htp]{
\begin{center}
\caption{基于串的解码 vs 基于树的解码}
\label{tab:4-4}
{
\begin{tabular}{l | p{16.5em} p{12em}}
对比 & 基于树的解码 & 基于串的解码 \\
\hline
\rule{0pt}{15pt}解码方法 & $\hat{d} = \arg\max_{d \in D_{\textrm{tree}}} \textrm{score} (d)$ & $\hat{d} = \arg\max_{d \in D} \textrm{score} (d)$ \\
\rule{0pt}{15pt}搜索空间 & 与输入的源语句法树兼容的推导$D_{\textrm{tree}}$ & 所有的推导$D$
\end{tabular}
}
\end{center}
}\end{table}
\begin{table}[htp]{
\begin{center}
{
\begin{tabular}{l | p{16.5em} p{12em}}
对比 & 基于树的解码 & 基于串的解码 \\
\hline
\rule{0pt}{15pt}适用模型 & 树到串、树到树 & 所有的句法模型 \\
\rule{0pt}{15pt}解码算法 & Chart解码 & CKY + 规则二叉化 \\
\rule{0pt}{15pt}速度 & 快 & 一般较慢
\end{tabular}
}
\end{center}
}\end{table}
%-------------------------------------------

\parinterval 表\ref{tab:4-4}对比了基于串和基于树的解码方法。可以看到，基于树的解码只考虑了与源语言句法树兼容的推导，因此搜索空间更小，解码速度会更快。

\parinterval 这里需要注意的是，不论是基于串的解码还是基于树的解码都是使用句法模型的方法，在翻译过程中都会生成翻译推导和树结构。二者的本质区别在于，基于树的解码把句法树作为显性的输入，而基于串的解码把句法树看作是翻译过程中的隐含变量。图\ref{fig:4-67}进一步解释了这个观点。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-role-of-syntax-tree-in-different-decoding-methods}
\caption{句法树在不同解码方法中的角色}
\label{fig:4-67}
\end{figure}
%-------------------------------------------

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

\subsubsection{基于树的解码}

\parinterval 基于树和基于串的解码都可以使用前面的超图结构进行推导的表示。基于树的解码方法相对简单。直接使用Chart结构组织解码空间即可。这里采用自底向上的策略，具体步骤如下：
\begin{itemize}
\vspace{0.5em}
\item 从源语言句法树的叶子节点开始，自下而上访问输入句法树的节点；
\vspace{0.5em}
\item 对于每个树节点，匹配相应的规则；
\vspace{0.5em}
\item 从树的根节点可以得到翻译推导，最终生成最优推导所对应的译文。
\vspace{0.5em}
\end{itemize}

\parinterval 这个过程如图\ref{fig:4-68}所示，可以看到，不同的Chart Cell对应不同跨度，每个Chart Cell会保存相应的句法标记（还有译文的信息）。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-content-of-chart-in-tree-based-decoding}
\caption{基于树的解码中Chart的内容}
\label{fig:4-68}
\end{figure}
%-------------------------------------------

\parinterval 这里的问题在于规则匹配。对于每个树节点，需要知道以它为根可以匹配的规则有哪些。比较直接的解决方法是遍历这个节点下一定深度的句法树片段，用每个树片段在文法中找出相应的匹配规则，如图\ref{fig:4-69}所示。不过这种匹配是一种严格匹配，因为它要求句法树片段内的所有内容都要与规则的源语言部分严格对应。有时，句法结构中的细微差别都会导致规则匹配不成功。因此，也可以考虑采用模糊匹配的方式提高规则的命中率，进而增加可以生成推导的数量\cite{zhu2011improving}。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-rule-matching-base-tree}
\caption{基于树的规则匹配}
\label{fig:4-69}
\end{figure}
%-------------------------------------------

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

\subsubsection{基于串的解码}

\parinterval 基于串的解码过程和句法分析几乎一样。对于输入的源语言句子，基于串的解码需要找到这个句子上的最优推导。唯一不同的地方在于，机器翻译需要考虑译文的生成（语言模型的引入会使问题稍微复杂一些），但是源语言部分的处理和句法分析是一样的。因为不要求用户输入句法树，所以这种方法同时适用于树到串、串到树、树到树等多种模型。本质上，基于串的解码可以探索更多潜在的树结构，并增大搜索空间（相比基于树的解码），因此该方法更有可能找到高质量翻译结果。

\parinterval 基于串的解码仍然可以用Chart来组织翻译推导。不过，一个比较有挑战的问题是如何找到每个规则能够匹配的源语言跨度。也就是，对于每个Chart Cell，需要知道哪些规则可以被填入其中。因为，没有用户输入的句法树做指导，理论上输入句子的所有子串要与所有规则进行匹配。匹配时，需要考虑规则中源语言端的符号串（或者树结构的叶子序列）与输入词串匹配的全部可能性。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter8/Figures/figure-cut-different-positions-of-word-string}
\caption{在一个词串上匹配``NP 对 NP VP''。连续变量的匹配对应了对词串不同位置的切割。}
\label{fig:4-70}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:4-70}展示了规则匹配输入句子（包含13个词）的所有可能。可以看到，规则源语言端的连续变量会使得匹配情况变得复杂。对于长度为$n$的词串，匹配含有$m$个连续变量的规则的时间复杂度是O($n^{m-1}$)。显然当变量个数增加时规则匹配是相当耗时的操作，甚至当变量个数过多时解码无法在可接受的时间内完成。

\parinterval 对于这个问题，有两种常用的解决办法：
\begin{itemize}
\vspace{0.5em}
\item 对文法进行限制。比如，可以限制规则中变量的数量；或者不允许连续的变量，这样的规则也被称作满足{\small\bfnew{Lexicalized Norm Form}}\index{Lexicalized Norm Form}（LNF）的规则。比如，层次短语规则就是LNF规则。由于LNF 中单词（终结符）可以作为锚点，因此规则匹配时所有变量的匹配范围是固定的；
\vspace{0.5em}
\item 对规则进行二叉化，使用CKY方法进行分析。这个方法也是句法分析中常用的策略。所谓规则二叉化是把规则转化为最多只含两个变量或连续词串的规则（串到树规则）。比如，对于如下的规则：
\begin{eqnarray}
\textrm{喜欢}\ \textrm{VP}_1\ \textrm{NP}_2 \rightarrow \textrm{VP(VBZ(likes)}\ \textrm{VP}_1\ \textrm{NP}_2 ) \nonumber
\end{eqnarray}

\noindent 二叉化的结果为：
\begin{eqnarray}
\textrm{喜欢}\ \textrm{V103} &\rightarrow& \textrm{VP}(\textrm{VBZ}(\textrm{likes})\ \textrm{V103} ) \nonumber \\
\textrm{VP}_1\ \textrm{NP}_2 &\rightarrow& \textrm{V103(}\ \textrm{VP}_1\ \textrm{NP}_2 ) \nonumber
\end{eqnarray}
\noindent 可以看到，这两条新的规则源语言端只有两个部分，代表两个分叉。V103是一个新的标签，它没有任何句法含义。不过，为了保证二叉化后规则目标语部分的连续性，需要考虑源语言和目标语二叉化的同步性\cite{zhang2006synchronous,Tong2009Better}。这样的规则与CKY方法一起使用完成解码，具体内容可以参考\ref{subsection-4.3.4}节的内容。
\vspace{0.5em}
\end{itemize}

\parinterval 总的来说，基于句法的解码器较为复杂。无论是算法的设计还是工程技巧的运用，对开发者的能力都有一定要求。因此开发一个优秀的基于句法的机器翻译系统是一项有挑战的工作。

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------
\sectionnewpage
\section{小结及深入阅读}