% !Mode:: "TeX:UTF-8"
% !TEX encoding = UTF-8 Unicode

%----------------------------------------------------------------------------------------
% 机器翻译：基础与模型
% Machine Translation: Foundations and Models
%
% Copyright 2020
% 肖桐(xiaotong@mail.neu.edu.cn) 朱靖波 (zhujingbo@mail.neu.edu.cn)
%----------------------------------------------------------------------------------------

%----------------------------------------------------------------------------------------
%    CONFIGURATIONS
%----------------------------------------------------------------------------------------

\part{附录}

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

%----------------------------------------------------------------------------------------
%	CHAPTER  APPENDIX A
%----------------------------------------------------------------------------------------
\fancyhead[LO]{\rightmark} % Print the nearest section name on the left side of odd pages
\fancyhead[RE]{\leftmark} % Print the current chapter name on the right side of even pages

\begin{appendices}
\chapter{附录A}
\label{appendix-A}
\parinterval  从实践的角度，机器翻译的发展离不开开源系统的推动作用。开源系统通过代码共享的方式使得最新的研究成果可以快速传播，同时实验结果可以复现。此外，开源项目也促进了不同团队之间的协作，让研究人员在同一个平台上集中力量攻关。

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

\section{统计机器翻译开源系统}

\begin{itemize}
\vspace{0.5em}
\item NiuTrans.SMT。NiuTrans\upcite{Tong2012NiuTrans}是由东北大学自然语言处理实验室自主研发的统计机器翻译系统，该系统可支持基于短语的模型、基于层次短语的模型以及基于句法的模型。由于使用C++ 语言开发，所以该系统运行时间快，所占存储空间少。系统中内嵌有$n$-gram语言模型，故无需使用其他的系统即可对完成语言建模。
\vspace{0.5em}
\item Moses。Moses\upcite{Koehn2007Moses}是统计机器翻译时代最著名的系统之一，（主要）由爱丁堡大学的机器翻译团队开发。最新的Moses系统支持很多的功能，例如，它既支持基于短语的模型，也支持基于句法的模型。Moses 提供因子化翻译模型（Factored Translation Model），因此该模型可以很容易地对不同层次的信息进行建模。此外，它允许将混淆网络和字格作为输入，可缓解系统的1-best输出中的错误。Moses还提供了很多有用的脚本和工具，被机器翻译研究人员广泛使用。
\vspace{0.5em}
\item Joshua。Joshua\upcite{Li2010Joshua}是由约翰霍普金斯大学的语言和语音处理中心开发的层次短语翻译系统。由于Joshua是由Java语言开发，所以它在不同的平台上运行或开发时具有良好的可扩展性和可移植性。Joshua也是使用非常广泛的开源机器翻译系统之一。
\vspace{0.5em}
\item SilkRoad。SilkRoad是由五个国内机构（中科院计算所、中科院软件所、中科院自动化所、厦门大学和哈尔滨工业大学）联合开发的基于短语的统计机器翻译系统。该系统是中国乃至亚洲地区第一个开源的统计机器翻译系统。SilkRoad支持多种解码器和规则提取模块，这样可以组合成不同的系统，提供多样的选择。
\vspace{0.5em}
\item SAMT。SAMT\upcite{zollmann2007the}是由卡内基梅隆大学机器翻译团队开发的基于语法增强的统计机器翻译系统。SAMT在解码的时候使用目标树来生成翻译规则，而不严格遵守目标语言的语法。SAMT 的一个亮点是它提供了简单但高效的方式在机器翻译中使用句法信息。由于SAMT在hadoop中实现，所以具备hadoop处理大数据集的优势。
\vspace{0.5em}
\item HiFST。HiFST\upcite{iglesias2009hierarchical}是剑桥大学开发的统计机器翻译系统。该系统完全基于有限状态自动机实现，因此非常适合对搜索空间进行有效的表示。
\vspace{0.5em}
\item cdec。cdec\upcite{dyer2010cdec}是一个强大的解码器，是由Chris Dyer 和他的合作者们一起开发。cdec的主要功能是它使用了翻译模型的一个统一的内部表示，并为结构预测问题的各种模型和算法提供了实现框架。所以，cdec也可以被用来做一个对齐系统或者一个更通用的学习框架。此外，由于使用C++语言编写，cdec的运行速度较快。
\vspace{0.5em}
\item Phrasal。Phrasal\upcite{Cer2010Phrasal}是由斯坦福大学自然语言处理小组开发的系统。除了传统的基于短语的模型，Phrasal还支持基于非层次短语的模型，这种模型将基于短语的翻译延伸到非连续的短语翻译，增加了模型的泛化能力。
\vspace{0.5em}
\item Jane。Jane\upcite{vilar2012jane}是一个基于层次短语的机器翻译系统，由亚琛工业大学的人类语言技术与模式识别小组开发。Jane提供了系统融合模块，因此可以非常方便的对多个系统进行融合。
\vspace{0.5em}
\item GIZA++。GIZA++\upcite{och2003systematic}是Franz Och研发的用于训练IBM模型1-5和HMM单词对齐模型的工具包。在早期，GIZA++是所有统计机器翻译系统中词对齐的标配工具。
\vspace{0.5em}
\item FastAlign。FastAlign\upcite{DBLP:conf/naacl/DyerCS13}是一个快速，无监督的词对齐工具，由卡内基梅隆大学开发。
\vspace{0.5em}
\end{itemize}

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------
\section{神经机器翻译开源系统}

\begin{itemize}
\vspace{0.5em}
\item GroundHog。GroundHog\upcite{bahdanau2014neural}基于Theano\upcite{al2016theano}框架，由蒙特利尔大学LISA 实验室使用Python语言编写的一个框架，旨在提供灵活而高效的方式来实现复杂的循环神经网络模型。它提供了包括LSTM在内的多种模型。Bahdanau等人在此框架上又编写了GroundHog神经机器翻译系统。该系统也作为了很多论文的基线系统。
\vspace{0.5em}
\item Nematus。Nematus\upcite{DBLP:journals/corr/SennrichFCBHHJL17}是英国爱丁堡大学开发的，基于Theano框架的神经机器翻译系统。该系统使用GRU作为隐层单元，支持多层网络。Nematus 编码端有正向和反向的编码方式，可以同时提取源语言句子中的上下文信息。该系统的一个优点是，它可以支持输入端有多个特征的输入（例如词的词性等）。
\vspace{0.5em}
\item ZophRNN。ZophRNN\upcite{zoph2016simple}是由南加州大学的Barret Zoph 等人使用C++语言开发的系统。Zoph既可以训练序列表示模型（如语言模型），也可以训练序列到序列的模型（如神经机器翻译模型）。当训练神经机器翻译系统时，ZophRNN也支持多源输入。
\vspace{0.5em}
\item Fairseq。Fairseq\upcite{Ottfairseq}是由Facebook开发的，基于PyTorch框架的用以解决序列到序列问题的工具包，其中包括基于卷积神经网络、基于循环神经网络、基于Transformer的模型等。Fairseq是当今使用最广泛的神经机器翻译开源系统之一。
\vspace{0.5em}
\item Tensor2Tensor。Tensor2Tensor\upcite{Vaswani2018Tensor2TensorFN}是由谷歌推出的，基于TensorFlow框架的开源系统。该系统基于Transformer模型，因此可以支持大多数序列到序列任务。得益于Transformer 特殊的网络结构，系统的训练速度较快。现在，Tensor2Tensor也是机器翻译领域广泛使用的开源系统之一。
\vspace{0.5em}
\item OpenNMT。OpenNMT\upcite{KleinOpenNMT}系统是由哈佛大学自然语言处理研究组开源的，基于Torch框架的神经机器翻译系统。OpenNMT系统的早期版本使用Lua 语言编写，现在也扩展到了基于python的TensorFlow和PyTorch，设计简单易用，易于扩展，同时保持效率和翻译精度。
\vspace{0.5em}
\item 斯坦福神经机器翻译开源代码库。斯坦福大学自然语言处理组（Stanford NLP）发布了一篇教程，介绍了该研究组在神经机器翻译上的研究信息，同时实现了多种翻译模型\upcite{luong2016acl_hybrid}。 
\vspace{0.5em}
\item THUMT。清华大学NLP团队实现的神经机器翻译系统，支持Transformer等模型\upcite{ZhangTHUMT}。该系统主要基于TensorFlow和Theano实现，其中Theano版本包含了RNNsearch模型，训练方式包括MLE （Maximum Likelihood Estimate）, MRT（Minimum Risk Training）, SST（Semi-Supervised Training）。TensorFlow 版本实现了Seq2Seq, RNNsearch, Transformer三种基本模型。
\vspace{0.5em}
\item NiuTrans.NMT。由小牛翻译团队基于NiuTensor实现的神经机器翻译系统。该系统支持循环神经网络、Transformer等结构，并支持语言建模、序列标注、机器翻译等任务，为开发人员提供快速二次开发基础，支持GPU与CPU 训练及解码，小巧易用。此外，NiuTrans.NMT已经得到了大规模应用，形成了可用于304种语言翻译的小牛翻译系统。
\vspace{0.5em}
\item MARIAN。主要由微软翻译团队搭建\upcite{JunczysMarian}，其使用C++实现的可用于GPU/CPU训练和解码的引擎，支持多GPU训练和批量解码，最小限度依赖第三方库，静态编译一次之后，复制其二进制文件就能在其他平台使用。
\vspace{0.5em}
\item Sockeye。由Awslabs开发的神经机器翻译框架\upcite{hieber2017sockeye}。其中支持RNNsearch、Transformer、CNN等翻译模型，同时提供了从图片翻译到文字的模块以及WMT 德英新闻翻译、领域适应任务、多语言零资源翻译任务的教程。
\vspace{0.5em}
\item CytonMT。由NICT开发的一种用C++实现的神经机器翻译开源工具包\upcite{WangCytonMT}。主要支持Transformer模型，并支持一些常用的训练方法以及解码方法。
\vspace{0.5em}
\item OpenSeq2Seq。由NVIDIA团队开发的\upcite{DBLP:journals/corr/abs-1805-10387}基于TensorFlow的模块化架构，用于序列到序列的模型，允许从可用组件中组装新模型，支持利用NVIDIA Volta Turing GPU中的Tensor核心进行混合精度训练，基于Horovod的快速分布式训练，支持多GPU，多节点多模式。
\vspace{0.5em}
\item NMTPyTorch。由勒芒大学语言实验室发布的基于序列到序列框架的神经网络翻译系统\upcite{nmtpy2017}，NMTPyTorch的核心部分依赖于Numpy，PyTorch和tqdm。可以训练各种端到端神经体系结构，包括但不限于神经机器翻译、图像字幕和自动语音识别系统。
\vspace{0.5em}
\end{itemize}

\end{appendices}
%----------------------------------------------------------------------------------------
%	CHAPTER  APPENDIX B
%----------------------------------------------------------------------------------------

\begin{appendices}
\chapter{附录B}
\label{appendix-B}
\parinterval 除了开源系统，机器翻译的发展还离不开评测比赛。在评测比赛中，各个研究组织的成果可以进行科学的对比，且各个研究组织可以互相学习，共同推动机器翻译的发展与进步。另外在构建机器翻译系统的过程中，数据是必不可少的，尤其是现在主流的神经机器翻译系统，系统的性能往往受限于语料库规模和质量。所幸的是，随着语料库语言学的发展，一些主流语种的相关语料资源已经十分丰富。

\parinterval 为了方便读者进行相关研究，本书汇总了几个常见的公开评测任务、一些常用的基准数据集和常用的平行语料。

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------
\section{公开评测任务}
\parinterval 机器翻译相关评测主要有两种组织形式，一种是由政府及国家相关机构组织，权威性强。如由美国国家标准技术研究所组织的NIST评测、日本国家科学咨询系统中心主办的NACSIS Test Collections for IR（NTCIR）PatentMT、日本科学振兴机构（Japan Science and Technology Agency，简称JST）等组织联合举办的Workshop on Asian Translation（WAT）以及国内由中文信息学会主办的全国机器翻译大会（China Conference on Machine Translation，简称CCMT）；另一种是由相关学术机构组织，具有领域针对性的特点，如倾向新闻领域的Conference on Machine Translation（WMT）以及面向口语的International Workshop on Spoken Language Translation（IWSLT）。下面将针对上述评测进行简要介绍。

\begin{itemize}
\vspace{0.5em}
\item CCMT。CCMT（全国机器翻译大会）前身为CWMT，是国内机器翻译领域的旗舰会议，自2005年起已经组织多次机器翻译评测，对国内机器翻译相关技术的发展产生了深远影响。该评测主要针对汉语、英语以及国内的少数民族语言（蒙古语、藏语、维吾尔语等）进行评测，领域包括新闻、口语、政府文件等，不同语言方向对应的领域也有所不同。评价方式不同届略有不同，主要采用自动评价的方式，自CWMT\ 2013起则针对某些领域增设人工评价。自动评价的指标一般包括BLEU-SBP、BLEU-NIST、TER、METEOR、NIST、GTM、mWER、mPER 以及ICT 等，其中以BLEU-SBP 为主，汉语为目标语言的翻译采用基于字符的评价方式，面向英语的翻译采用基于词的评价方式。每年该评测吸引国内外近数十家企业及科研机构参赛，业内认可度极高。关于CCMT的更多信息可参考中文信息学会机器翻译专业委员会相关页面。

\vspace{0.5em}
\item WMT。WMT由Special Interest Group for Machine Translation（SIGMT）主办，会议自2006年起每年召开一次，是一个机器翻译领域的综合性会议，WMT公开评测任务包括多领域翻译评测任务、质量评价任务以及其他与机器翻译的相关任务（如文档对齐评测等）。现在WMT已经成为机器翻译领域的旗舰评测会议，很多研究工作都以WMT评测结果作为基准。WMT评测涉及的语言范围较广，包括英语、德语、芬兰语、捷克语、罗马尼亚语等十多种语言，翻译方向一般以英语为核心，探索英语与其他语言之间的翻译性能，领域包括新闻、信息技术、生物医学。如今，也增加了无指导机器翻译等热门问题。WMT在评价方面类似于CCMT，也采用人工评价与自动评价相结合的方式，自动评价的指标一般为BLEU、TER 等。此外，WMT公开了所有评测数据，因此也经常被机器翻译相关人员所使用。更多WMT的机器翻译评测相关信息可参考SIGMT官网。

\vspace{0.5em}
\item NIST。NIST机器翻译评测开始于2001年，是早期机器翻译公开评测中颇具代表性的任务，现在WMT和CCMT很多任务的设置也大量参考了当年NIST评测的内容。NIST评测由美国国家标准技术研究所主办，作为美国国防高级计划署（DARPA）中TIDES计划的重要组成部分。早期，NIST评测主要评价阿拉伯语和汉语等语言到英语的翻译效果，评价方法一般采用人工评价与自动评价相结合的方式。人工评价采用5分制评价。自动评价使用多种方式，包括BLEU，METEOR，TER以及HyTER。此外NIST从2016 年起开始对稀缺语言资源技术进行评估，其中机器翻译作为其重要组成部分共同参与评测，评测指标主要为BLEU。除对机器翻译系统进行评测之外，NIST在2008 和2010年对于机器翻译的自动评价方法（MetricsMaTr）也进行了评估，以鼓励更多研究人员对现有评价方法进行改进或提出更加贴合人工评价的方法。同时NIST评测所提供的数据集由于数据质量较高受到众多科研人员喜爱，如MT04，MT06等（汉英）平行语料经常被科研人员在实验中使用。不过，近几年NIST评测已经停止。更多NIST的机器翻译评测相关信息可参考官网。

\vspace{0.5em}
\item IWSLT。从2004年开始举办的IWSLT也是颇具特色的机器翻译评测，它主要关注口语相关的机器翻译任务，测试数据包括TED talks的多语言字幕以及QED 教育讲座影片的字幕等，语言涉及英语、法语、德语、捷克语、汉语、阿拉伯语等众多语言。此外在IWSLT 2016 中还加入了对于日常对话的翻译评测，尝试将微软Skype中一种语言的对话翻译成其他语言。评价方式采用自动评价的模式，评价标准和WMT类似，一般为BLEU 等指标。另外，IWSLT除了包含文本到文本的翻译评测外，还有自动语音识别以及语音转另一种语言的文本的评测。更多IWSLT的机器翻译评测相关信息可参考IWSLT\ 官网。

\vspace{0.5em}
\item WAT。日本举办的机器翻译评测WAT是亚洲范围内的重要评测之一，由日本科学振兴机构（JST）、情报通信研究机构（NICT）等多家机构共同组织，旨在为亚洲各国之间交流融合提供便宜之处。语言方向主要包括亚洲主流语言（汉语、韩语、印地语等）以及英语对日语的翻译，领域丰富多样，包括学术论文、专利、新闻、食谱等。评价方式包括自动评价（BLEU、RIBES以及AMFM 等）以及人工评价，其特点在于对于测试语料以段落为单位进行评价，考察其上下文关联的翻译效果。更多WAT的机器翻译评测相关信息可参考官网。

\vspace{0.5em}
\item NTCIR。NTCIR计划是由日本国家科学咨询系统中心策划主办的，旨在建立一个用在自然语言处理以及信息检索相关任务上的日文标准测试集。在NTCIR-9和NTCIR-10中开设的Patent Machine Translation（PatentMT）任务主要针对专利领域进行翻译测试，其目的在于促进机器翻译在专利领域的发展和应用。在NTCIR-9中，评测方式采取人工评价与自动评价相结合，以人工评价为主导。人工评价主要根据准确度和流畅度进行评估，自动评价采用BLEU、NIST等方式进行。NTCIR-10评价方式在此基础上增加了专利审查评估、时间评估以及多语种评估，分别考察机器翻译系统在专利领域翻译的实用性、耗时情况以及不同语种的翻译效果等。更多NTCIR评测相关信息可参考官网。
\end{itemize}

\parinterval 以上评测数据大多可以从评测网站上下载，此外部分数据也可以从LDC（Lingu-istic Data Consortium）上申请。ELRA（European Language Resources Association）上也有一些免费的语料库供研究使用。从机器翻译发展的角度看，这些评测任务给相关研究提供了基准数据集，使得不同的系统都可以在同一个环境下进行比较和分析，进而建立了机器翻译研究所需的实验基础。此外，公开评测也使得研究人员可以第一时间了解机器翻译研究的最新成果，比如，有多篇ACL会议最佳论文的灵感就来自当年参加机器翻译评测任务的系统。

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

\section{基准数据集}
\parinterval 表\ref{tab:Reference-data-set}所展示的数据集已经在机器翻译领域中被广泛使用，有很多之前的相关工作使用这些数据集进行实验，读者可以复现这些工作，或者将其在数据集上的结果与自己的工作进行比较。

%----------------------------------------------
\begin{table}[htp]{
\footnotesize
\begin{center}
\caption{基准数据集}
\label{tab:Reference-data-set}
\begin{tabular}{p{1.6cm} | p{1.3cm} p{1.6cm} p{5.2cm}}
{任务} & {语种} &{领域} &{描述} \\
\hline
\rule{0pt}{15pt}WMT & En-Zh、En-De等& 新闻、医学、翻译 & 以英语为核心的多语种机器翻译数据集，涉及多种任务\\
\rule{0pt}{15pt}IWSLT & En-De、En-Zh等 & 口语翻译 & 文本翻译数据集来自TED演讲，数据规模较小\\
\rule{0pt}{15pt}NIST & Zh-En、En-Cs等 & 新闻翻译 & 评测集包括4句参考译文，质量较高\\
\rule{0pt}{15pt}TVsub & Zh-En & 字幕翻译 & 数据抽取自电视剧字幕，用于对话中长距离上下文研究\\
\rule{0pt}{15pt}Flickr30K & En-De & 多模态翻译 & 31783张图片，每张图片5个语句标注 \\
\rule{0pt}{15pt}Multi30K  & En-De、En-Fr & 多模态翻译 & 31014张图片，每张图片5个语句标注  \\
\rule{0pt}{15pt}IAPRTC-12 & En-De & 多模态翻译 & 20000张图片及对应标注  \\
\rule{0pt}{15pt}IKEA & En-De、En-Fr & 多模态翻译 & 3600张图片及对应标注   \\
\end{tabular}
\end{center}
}\end{table}
%----------------------------------------------


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

\section{平行语料}
\parinterval 神经机器翻译系统的训练需要大量的双语数据，这里本节汇总了一些公开的平行语料，方便读者获取。
\vspace{0.5em}
\begin{itemize}
\item News Commentary Corpus：包括汉语、英语等12个语种，64个语言对的双语数据，爬取自Project Syndicate网站的政治、经济评论。
\vspace{0.5em}
\item CWMT Corpus：中国计算机翻译研讨会社区收集和共享的中英平行语料，涵盖多种领域，例如新闻、电影字幕、小说和政府文档等。
\vspace{0.5em}
\item Common Crawl corpus：包括捷克语、德语、俄语、法语4种语言到英语的双语数据，爬取自互联网网页。
\vspace{0.5em}
\item Europarl Corpus：包括保加利亚语、捷克语等20种欧洲语言到英语的双语数据，来源于欧洲议会记录。
\vspace{0.5em}
\item ParaCrawl Corpus：包括23种欧洲语言到英语的双语语料，数据来源于网络爬取。
\vspace{0.5em}
\item United Nations Parallel Corpus：包括阿拉伯语、英语、西班牙语、法语、俄语、汉语6种联合国正式语言，30种语言对的双语数据，来源自联合国公共领域的官方记录和其他会议文件。
\vspace{0.5em}
\item TED Corpus：TED大会演讲在其网站公布了自2007年以来的演讲字幕，以及超过100种语言的翻译版本。WIT收集整理了这些数据，以方便科研工作者使用，同时，会为每年的IWSLT评测比赛提供评测数据集。
\vspace{0.5em}
\item OpenSubtitle：由P. Lison和J. Tiedemann收集自opensubtitles电影字幕网站，包含62种语言、1782个语种对的平行语料，资源相对比较丰富。
\vspace{0.5em}
\item Wikititles Corpus：包括古吉拉特语等14个语种，11个语言对的双语数据，数据来源自维基百科的标题。
\vspace{0.5em}
\item CzEng:捷克语和英语的平行语料，数据来源于欧洲法律、信息技术和小说领域。
\vspace{0.5em}
\item Yandex Corpus：俄语和英语的平行语料，爬取自互联网网页。
\vspace{0.5em}
\item Tilde MODEL Corpus：欧洲语言的多语言开放数据，包含多个数据集，数据来自于经济、新闻、政府、旅游等门户网站。
\vspace{0.5em}
\item Setimes Corpus：包括克罗地亚语、阿尔巴尼亚等9种巴尔干语言，72个语言对的双语数据，来源于东南欧时报的新闻报道。
\vspace{0.5em}
\item TVsub：收集来自电视剧集字幕的中英文对话语料，包含超过200万的句对，可用于对话领域和长距离上下文信息的研究。
\vspace{0.5em}
\item Recipe Corpus：由Cookpad公司创建的日英食谱语料库，包含10万多个句对。
\end{itemize}


\end{appendices}

%----------------------------------------------------------------------------------------
%	CHAPTER  APPENDIX C
%----------------------------------------------------------------------------------------

\begin{appendices}
\chapter{附录C}
\label{appendix-C}

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

\section{IBM模型2的训练方法}

\parinterval IBM模型2与模型1的训练过程完全一样，本质上都是基于EM的方法，因此可以直接复用{\chapterfive}中训练模型1的流程。对于源语言句子$\seq{s}=\{s_1,\dots,s_m\}$和目标语言句子$\seq{t}=\{t_1,\dots,t_l\}$，E-Step的计算公式如下：

\begin{eqnarray}
c(s_u|t_v;\seq{s},\seq{t}) &=&\sum\limits_{j=1}^{m} \sum\limits_{i=0}^{l} \frac{f(s_u|t_v)a(i|j,m,l) \delta(s_j,s_u)\delta (t_i,t_v) }   {\sum_{k=0}^{l} f(s_u|t_k)a(k|j,m,l)} \\
c(i|j,m,l;\seq{s},\seq{t}) &=&\frac{f(s_j|t_i)a(i|j,m,l)}   {\sum_{k=0}^{l} f(s_j|t_k)a(k,j,m,l)}
\label{eq:append-1}
\end{eqnarray}

\noindent M-Step的计算公式如下：

\begin{eqnarray}
f(s_u|t_v) &=&\frac{c(s_u|t_v;\seq{s},\seq{t}) }    {\sum_{s'_u} c(s'_u|t_v;\seq{s},\seq{t})} \\
a(i|j,m,l) &=&\frac{c(i|j,m,l;\seq{s},\seq{t})}  {\sum_{i'}c(i'|j,m,l;\seq{s},\seq{t})}
\label{eq:append-2}
\end{eqnarray}

\noindent 其中，$f(s_u|t_v)$与IBM模型1 一样表示目标语言单词$t_v$到源语言单词$s_u$的翻译概率，$a(i|j,m,l)$表示调序概率。

\parinterval 对于由$K$个样本组成的训练集$\{(\seq{s}^{[1]},\seq{t}^{[1]}),...,(\seq{s}^{[K]},\seq{t}^{[K]})\}$，可以将M-Step的计算调整为：

\begin{eqnarray}
f(s_u|t_v) &=&\frac{\sum_{k=1}^{K}c(s_u|t_v;\seq{s}^{[k]},\seq{t}^{[k]}) }    {\sum_{s'_u} \sum_{k=1}^{K} c(s'_u|t_v;\seq{s}^{[k]},\seq{t}^{[k]})} \\
a(i|j,m,l) &=&\frac{\sum_{k=1}^{K}c(i|j,m^{[k]},l^{[k]};\seq{s}^{[k]},\seq{t}^{[k]})}  {\sum_{i'}\sum_{k=1}^{K}c(i'|j,m^{[k]},l^{[k]};\seq{s}^{[k]},\seq{t}^{[k]})}
\label{eq:append-3}
\end{eqnarray}

\noindent 其中，$m^{[k]}=|\seq{s}^{[k]}|$，$l^{[k]}=|\seq{t}^{[k]}|$。

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

\section{IBM模型3的训练方法}
\parinterval IBM模型3采用与模型1和模型2相同的参数估计方法，辅助函数被定义如下：
\begin{eqnarray}
h(t,d,n,p, \lambda,\mu, \nu, \zeta) & = &  \funp{P}_{\theta}(\seq{s}|\seq{t})-\sum_{t_v}\lambda_{t_v}\big(\sum_{s_u}t(s_u|t_v)-1\big)  \nonumber \\
& & -\sum_{i}\mu_{iml}\big(\sum_{j}d(j|i,m,l)-1\big) \nonumber \\
& & -\sum_{t_v}\nu_{t_v}\big(\sum_{\varphi}n(\varphi|t_v)-1\big)-\zeta(p_0+p_1-1)
\label{eq:1.1}
\end{eqnarray}

\parinterval 这里略去推导步骤，直接给出不同参数对应的期望频次计算公式，如下：
\begin{eqnarray}
c(s_u|t_v,\seq{s},\seq{t}) & = & \sum_{\seq{a}}\big[\funp{P}_{\theta}(\seq{s},\seq{a}|\seq{t}) \times \sum_{j=1}^{m} (\delta(s_j,s_u) \cdot \delta(t_{a_{j}},t_v))\big] \label{eq:1.2} \\
c(j|i,m,l;\seq{s},\seq{t}) & = & \sum_{\seq{a}}\big[\funp{P}_{\theta}(\seq{s},\seq{a}|\seq{t}) \times \delta(i,a_j)\big] \label{eq:1.3} \\
c(\varphi|t_v;\seq{s},\seq{t}) & = & \sum_{\seq{a}}\big[\funp{P}_{\theta}(\seq{s},\seq{a}|\seq{t}) \times \sum_{i=1}^{l}\delta(\varphi,\varphi_{i})\delta(t_v,t_i)\big] \label{eq:1.4} \\
c(0|\seq{s},\seq{t}) & = & \sum_{\seq{a}}\big[\funp{P}_{\theta}(\seq{s},\seq{a}|\seq{t})  \times (m-2\varphi_0) \big] \label{eq:1.5} \\
c(1|\seq{s},\seq{t}) & = & \sum_{\seq{a}}\big[\funp{P}_{\theta}(\seq{s},\seq{a}|\seq{t}) \times \varphi_0 \big] \label{eq:1.6}
\end{eqnarray}

\parinterval 进一步，对于由$K$个样本组成的训练集，有：
\begin{eqnarray}
t(s_u|t_v) & = & \lambda_{t_v}^{-1} \times \sum_{k=1}^{K}c(s_u|t_v;\seq{s}^{[k]},\seq{t}^{[k]}) \label{eq:1.7} \\
d(j|i,m,l) & = & \mu_{iml}^{-1} \times \sum_{k=1}^{K}c(j|i,m,l;\seq{s}^{[k]},\seq{t}^{[k]}) \label{eq:1.8} \\
n(\varphi|t_v) & = & \nu_{t_v}^{-1} \times \sum_{k=1}^{K}c(\varphi |t_v;\seq{s}^{[k]},\seq{t}^{[k]}) \label{eq:1.9} \\
p_x & = & \zeta^{-1} \sum_{k=1}^{K}c(x;\seq{s}^{[k]},\seq{t}^{[k]}) \label{eq:1.10}
\end{eqnarray}

\parinterval 在模型3中，因为繁衍率的引入，并不能像模型1那样，通过简单的数学技巧加速参数估计的过程（见{\chapterfive}）。因此在计算公式\eqref{eq:1.2}-\eqref{eq:1.6}时，我们不得不面对大小为$(l+1)^m$的词对齐空间。遍历所有$(l+1)^m$个词对齐所带来的高时间复杂度显然是不能被接受的。因此就要考虑能否仅利用词对齐空间中的部分词对齐对这些参数进行估计。比较简单的方法是仅使用Viterbi词对齐来进行参数估计，这里Viterbi 词对齐可以被简单的看作搜索到的最好词对齐。遗憾的是，在模型3中并没有方法直接获得Viterbi对齐。这样只能采用一种折中的策略，即仅考虑那些使得$\funp{P}_{\theta}(\seq{s},\seq{a}|\seq{t})$ 达到较高值的词对齐。这里把这部分词对齐组成的集合记为$S$。以公式\eqref{eq:1.2}为例，它可以被修改为：
\begin{eqnarray}
c(s_u|t_v,\seq{s},\seq{t}) &\approx & \sum_{\seq{a} \in S}\big[\funp{P}_{\theta}(\seq{s},\seq{a}|\seq{t}) \times \sum_{j=1}^{m}(\delta(s_j,s_u) \cdot \delta(t_{a_{j}},t_v)) \big]
\label{eq:1.11}
\end{eqnarray}

\parinterval 可以以同样的方式修改公式\eqref{eq:1.3}-\eqref{eq:1.6}的修改结果。进一步，在IBM模型3中，可以定义$S$如下：
\begin{eqnarray}
S &=& N(b^{\infty}(V(\seq{s}|\seq{t};2))) \cup (\mathop{\cup}\limits_{ij} N(b_{i \leftrightarrow j}^{\infty}(V_{i \leftrightarrow j}(\seq{s}|\seq{t};2))))
\label{eq:1.12}
\end{eqnarray}

\parinterval 为了理解这个公式，先介绍几个概念。
\begin{itemize}
\item $V(\seq{s}|\seq{t})$表示Viterbi词对齐，$V(\seq{s}|\seq{t};1)$、$V(\seq{s}|\seq{t};2)$和$V(\seq{s}|\seq{t};3)$就分别对应了模型1、2 和3 的Viterbi 词对齐；
\item 把那些满足第$j$个源语言单词对应第$i$个目标语言单词（$a_j=i$）的词对齐构成的集合记为$\seq{a}_{i \leftrightarrow j}(\seq{s},\seq{t})$。通常称这些对齐中$j$和$i$被``钉''在了一起。在$\seq{a}_{i \leftrightarrow j}(\seq{s},\seq{t})$中使$\funp{P}(\seq{s},\seq{a}| \seq{t})$达到最大的那个词对齐被记为$V_{i \leftrightarrow j}(\seq{s}|\seq{t})$；
\item 如果两个词对齐，通过交换两个词对齐连接就能互相转化，则称它们为邻居。一个词对齐$\seq{a}$的所有邻居记为$N(\seq{a})$。
\end{itemize}

\vspace{0.5em}
\parinterval 公式\eqref{eq:1.12}中，应该使用 $V(\seq{s}|\seq{t};3)$ 和 $V_{i \leftrightarrow j}(\seq{s}|\seq{t};3)$进行计算，但其复杂度较高，因此使用 $b^{\infty}(V(\seq{s}|\seq{t};2))$ 和 $b_{i \leftrightarrow j}^{\infty}(V_{i \leftrightarrow j}(\seq{s}|\seq{t};2))$ 分别对 $V(\seq{s}|\seq{t};3)$ 和 $V_{i \leftrightarrow j}(\seq{s}|\seq{t};3)$ 进行估计。在计算$S$的过程中，需要知道一个对齐$\seq{a}$的邻居$\seq{a}'$的概率，即通过$\funp{P}_{\theta}(\seq{a},\seq{s}|\seq{t})$计算$\funp{P}_{\theta}(\seq{a}',\seq{s}|\seq{t})$。在模型3中，如果$\seq{a}$和$\seq{a}'$仅区别于某个源语言单词$s_j$，对齐从$a_j$变到$a_{j}'$，且$a_j$和$a'_j$均不为零，令$a_j=i$，$a'_{j}=i'$，那么

\begin{eqnarray}
\funp{P}_{\theta}(\seq{a}',\seq{s}|\seq{t}) & = & \funp{P}_{\theta}(\seq{a},\seq{s}|\seq{t}) \cdot  \nonumber \\
                                                                                   &     & \frac{\varphi_{i'}+1}{\varphi_i} \cdot \frac{n(\varphi_{i'}+1|t_{i'})}{n(\varphi_{i'}|t_{i'})} \cdot \frac{n(\varphi_{i}-1|t_{i})}{n(\varphi_{i}|t_{i})} \cdot \nonumber \\
                                                                                   &     & \frac{t(s_j|t_{i'})}{t(s_{j}|t_{i})} \cdot \frac{d(j|i',m,l)}{d(j|i,m,l)}
\label{eq:1.13}
\end{eqnarray}

\parinterval 如果$\seq{a}$和$\seq{a}'$区别于两个位置$j_1$和$j_2$的对齐，即$a_{j_{1}}=a'_{j_{2}}$且$a_{j_{2}}=a'_{j_{1}}$，那么
\begin{eqnarray}
\funp{P}_{\theta}(\seq{a}',\seq{s}|\seq{t}) &=& \funp{P}_{\theta}(\seq{a},\seq{s}|\seq{t}) \cdot \nonumber \\
                                                                 &  & \frac{t(s_{j_{1}}|t_{a_{j_{2}}})}{t(s_{j_{1}}|t_{a_{j_{1}}})} \cdot \frac{t(s_{j_{2}}|t_{a_{j_{1}}})}{t(s_{j_{2}}|t_{a_{j_{2}}})} \cdot \nonumber \\
                                                                 &  & \frac{d(j_{1}|a_{j_{2}},m,l)}{d(j_{1}|a_{j_{1}},m,l)} \cdot \frac{d(j_{2}|a_{j_{1}},m,l)}{d(j_{2}|a_{j_{2}},m,l)}
\label{eq:1.14}
\end{eqnarray}

\parinterval 相比整个词对齐空间，$S$只是一个非常小的子集，因此计算时间可以被大大降低。可以看到，模型3的参数估计过程是建立在模型1和模型2的参数估计结果上的。这不仅是因为模型3要利用模型2的Viterbi对齐，而且还因为模型3参数的初值也要直接利用模型2的参数。从这个角度说，模型1、2、3是有序的且向前依赖的。单独的对模型3的参数进行估计是较为困难的。实际上IBM的模型4和模型5也具有这样的性质，即它们都可以利用前一个模型参数估计的结果作为自身参数的初始值。

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

\section{IBM模型4的训练方法}

\parinterval 模型4的参数估计基本与模型3一致。需要修改的是扭曲度的估计公式，目标语言的第$i$个cept.生成的第一个单词为（假设有$K$个训练样本）：
\begin{eqnarray}
d_1(\Delta_j|ca,cb) &=& \mu_{1cacb}^{-1} \times \sum_{k=1}^{K}c_1(\Delta_j|ca,cb;\seq{s}^{[k]},\seq{t}^{[k]})
\label{eq:1.15}
\end{eqnarray}

\noindent 其中，

\begin{eqnarray}
c_1(\Delta_j|ca,cb;\seq{s},\seq{t})           & = & \sum_{\seq{a}}\big[\funp{P}_{\theta}(\seq{s},\seq{a}|\seq{t}) \times z_1(\Delta_j|ca,cb;\seq{a},\seq{s},\seq{t})\big] \label{eq:1.16} \\
z_1(\Delta_j|ca,cb;\rm{a},\seq{s},\seq{t}) & = & \sum_{i=1}^l \big[\varepsilon(\varphi_i) \cdot \delta(\pi_{i1}-\odot _{i},\Delta_j) \cdot \nonumber \\
                                                                           &     & \delta(A(t_{i-1}),ca) \cdot \delta(B(\tau_{i1}),cb) \big] \label{eq:1.17}
\end{eqnarray}

\noindent 且

\begin{eqnarray}
\varepsilon(x) &=& \begin{cases}
0 & x \leq 0 \\
1 & x > 0
\end{cases}
\label{eq:1.21}
\end{eqnarray}

\noindent 目标语言的第$i$个cept.生成的其他单词（非第一个单词）为：

\begin{eqnarray}
d_{>1}(\Delta_j|cb) &=& \mu_{>1cb}^{-1} \times \sum_{k=1}^{K}c_{>1}(\Delta_j|cb;\seq{s}^{[k]},\seq{t}^{[k]})
\label{eq:1.18}
\end{eqnarray}

\noindent 其中，

\begin{eqnarray}
c_{>1}(\Delta_j|cb;\seq{s},\seq{t})                  & = & \sum_{\seq{a}}\big[\funp{P}_{\theta}(\seq{s},\seq{a}|\seq{t}) \times z_{>1}(\Delta_j|cb;\seq{a},\seq{s},\seq{t}) \big] \label{eq:1.19} \\
z_{>1}(\Delta_j|cb;\seq{a},\seq{s},\seq{t}) & = & \sum_{i=1}^l \big[\varepsilon(\varphi_i-1)\sum_{k=2}^{\varphi_i}\delta(\pi_{[i]k}-\pi_{[i]k-1},\Delta_j) \cdot \nonumber ß\\
                                                                                  &    & \delta(B(\tau_{[i]k}),cb) \big] \label{eq:1.20}
\end{eqnarray}

\noindent 这里，$ca$和$cb$分别表示目标语言和源语言的某个词类。注意，在公式\eqref{eq:1.17}和\eqref{eq:1.20}中，求和操作$\sum_{i=1}^l$是从$i=1$开始计算，而不是从$i=0$。这实际上跟IBM模型4的定义相关，因为$d_{1}(j-{\odot}_{i-1}|A(t_{[i-1]}),B(s_j))$和$d_{>1}(j-\pi_{[i]k-1}|B(s_j))$是从$[i]>0$开始定义的，详细信息可以参考{\chaptersix}的内容。

\parinterval 模型4 需要像模型3 一样，通过定义一个词对齐集合$S$，使得每次训练迭代都在$S$ 上进行，进而降低运算量。模型4 中$S$的定义为：

\begin{eqnarray}
S &=& N(\tilde{b}^{\infty}(V(\seq{s}|\seq{t};2))) \cup (\mathop{\cup}\limits_{ij} N(\tilde{b}_{i \leftrightarrow j}^{\infty}(V_{i \leftrightarrow j}(\seq{s}|\seq{t};2))))
\label{eq:1.22}
\end{eqnarray}

\parinterval 对于一个对齐$\seq{a}$，可用模型3对它的邻居进行排名，即按$\funp{P}_{\theta}(b(\seq{a})|\seq{s},\seq{t};3)$排序，其中$b(\seq{a})$表示$\seq{a}$的邻居。$\tilde{b}(\seq{a})$ 表示这个排名表中满足$\funp{P}_{\theta}(\seq{a}'|\seq{s},\seq{t};4) > \funp{P}_{\theta}⁡(\seq{a}|\seq{s},\seq{t};4)$的最高排名的$\seq{a}'$。 同理可知$\tilde{b}_{i \leftrightarrow j}^{\infty}(\seq{a})$ 的意义。这里之所以不用模型3中采用的方法直接利用$b^{\infty}(\seq{a})$得到模型4中高概率的对齐，是因为模型4中要想获得某个对齐$\seq{a}$的邻居$\seq{a}'$必须做很大调整，比如：调整$\tau_{[i]1}$和$\odot_{i}$等等。这个过程要比模型3的相应过程复杂得多。因此在模型4中只能借助于模型3的中间步骤来进行参数估计。
\setlength{\belowdisplayskip}{3pt}%调整空白大小

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

\section{IBM模型5训练方法}
\parinterval 模型5的参数估计过程也和模型4的过程基本一致，二者的区别在于扭曲度的估计公式。在模型5中，对于目标语言的第$i$个cept.生成的第一单词，可以得到（假设有$K$个训练样本）：

\begin{eqnarray}
d_1(\Delta_j|cb) &=& \mu_{1cb}^{-1} \times \sum_{k=1}^{K}c_1(\Delta_j|cb;\seq{s}^{[k]},\seq{t}^{[k]})
\label{eq:1.23}
\end{eqnarray}

\noindent 其中，

\begin{eqnarray}
c_1(\Delta_j|cb,v_x,v_y;\seq{s},\seq{t})                   & = & \sum_{\seq{a}}\Big[ \funp{P}(\seq{s},\seq{a}|\seq{t}) \times z_1(\Delta_j|cb,v_x,v_y;\seq{a},\seq{s},\seq{t}) \Big] \label{eq:1.24} \\
z_1(\Delta_j|cb,v_x,v_y;\seq{a},\seq{s},\seq{t}) & = & \sum_{i=1}^l \Big [ \varepsilon(\varphi_i) \cdot \delta(v_{\pi_{i1}},\Delta_j) \cdot \delta(v_{\odot _{i-1}},v_x) \nonumber \\
                                                                                          &    & \cdot \delta(v_m-\varphi_i+1,v_y) \cdot \delta(v_{\pi_{i1}},v_{\pi_{i1}-1} )\Big] \label{eq:1.25}
\end{eqnarray}


\noindent 目标语言的第$i$个cept.生成的其他单词（非第一个单词）为：

\begin{eqnarray}
d_{>1}(\Delta_j|cb,v) &=& \mu_{>1cb}^{-1} \times \sum_{k=1}^{K}c_{>1}(\Delta_j|cb,v;\seq{s}^{[k]},\seq{t}^{[k]})
\label{eq:1.26}
\end{eqnarray}

\noindent 其中，

\begin{eqnarray}
c_{>1}(\Delta_j|cb,v;\seq{s},\seq{t})                   & =  & \sum_{\seq{a}}\Big[\funp{P}(\seq{a},\seq{s}|\seq{t}) \times z_{>1}(\Delta_j|cb,v;\seq{a},\seq{s},\seq{t}) \Big] \label{eq:1.27} \\
z_{>1}(\Delta_j|cb,v;\seq{a},\seq{s},\seq{t}) & = & \sum_{i=1}^l\Big[\varepsilon(\varphi_i-1)\sum_{k=2}^{\varphi_i} \big[\delta(v_{\pi_{ik}}-v_{\pi_{[i]k}-1},\Delta_j)  \nonumber \\
                                                                                    &     & \cdot \delta(B(\tau_{[i]k}) ,cb) \cdot \delta(v_m-v_{\pi_{i(k-1)}}-\varphi_i+k,v) \nonumber \\
                                                                                    &     & \cdot \delta(v_{\pi_{i1}},v_{\pi_{i1}-1}) \big] \Big] \label{eq:1.28}
\end{eqnarray}

\vspace{0.5em}

\parinterval 从公式\eqref{eq:1.24}中可以看出，因子$\delta(v_{\pi_{i1}},v_{\pi_{i1}-1})$保证了，即使对齐$\seq{a}$不合理（一个源语言位置对应多个目标语言位置）也可以避免在这个不合理的对齐上计算结果。也就是因子$\delta(v_{\pi_{p1}},v_{\pi_{p1-1}})$确保了$\seq{a}$中不合理的部分不产生坏的影响，而$\seq{a}$中其他正确的部分仍会参与迭代。

\parinterval 不过上面的参数估计过程与IBM前4个模型的参数估计过程并不完全一样。IBM前4个模型在每次迭代中，可以在给定$\seq{s}$、$\seq{t}$和一个对齐$\seq{a}$的情况下直接计算并更新参数。但是在模型5的参数估计过程中（如公式\eqref{eq:1.24}），需要模拟出由$\seq{t}$生成$\seq{s}$的过程才能得到正确的结果，因为从$\seq{t}$、$\seq{s}$和$\seq{a}$中是不能直接得到 的正确结果的。具体说，就是要从目标语言句子的第一个单词开始到最后一个单词结束，依次生成每个目标语言单词对应的源语言单词，每处理完一个目标语言单词就要暂停，然后才能计算公式\eqref{eq:1.24}中求和符号里面的内容。

\parinterval 从前面的分析可以看出，虽然模型5比模型4更精确，但是模型5过于复杂以至于给参数估计增加了计算量（对于每组$\seq{t}$、$\seq{s}$和$\seq{a}$都要模拟$\seq{t}$生成$\seq{s}$的翻译过程）。因此模型5的系统实现是一个挑战。

\parinterval 在模型5中同样需要定义一个词对齐集合$S$，使得每次迭代都在$S$上进行。可以对$S$进行如下定义
\begin{eqnarray}
S &=& N(\tilde{\tilde{b}}^{\infty}(V(\seq{s}|\seq{t};2))) \cup (\mathop{\cup}\limits_{ij} N(\tilde{\tilde{b}}_{i \leftrightarrow j}^{\infty}(V_{i \leftrightarrow j}(\seq{s}|\seq{t};2))))
\label{eq:1.29}
\end{eqnarray}
\vspace{0.5em}

\noindent 其中，$\tilde{\tilde{b}}(\seq{a})$借用了模型4中$\tilde{b}(\seq{a})$的概念。不过$\tilde{\tilde{b}}(\seq{a})$表示在利用模型3进行排名的列表中满足$\funp{P}_{\theta}(\seq{a}'|\seq{s},\seq{t};5)$的最高排名的词对齐，这里$\seq{a}'$表示$\seq{a}$的邻居。
\end{appendices}














