统计机器翻译
3.基于词的机器翻译模型
3.1 词在翻译中的作用
先把句子中的每个词对应翻译后重新排序。包括三个步骤：分析、转换、生成。
3.2构建简单的机器翻译系统
人为翻译：翻译知识的学习（翻译候选），运用知识生成译文（处理常见的单词搭配、主谓一致的问题，生成译文）
机器翻译：
1.获得每个单词的译文，拼装成句
翻译词典，对单词进行进行拼装，相当于贯穿路径，计算机生成尽可能多的路径。
2.评价译文的好坏
设计统计模型，计算单词的翻译概率，最后得到整句的概率。
[^训练模型=学习知识]:
统计机器翻译的核心：建模、训练和解码
基本框架
很多思想来自IBM模型
1.训练：从双语平行数据中学习翻译，记为P(t|s),表示把s翻译为t的概率。
2.解码：为每一个翻译结果打分，最后选择得分最高的输出
如何从双语平行数据中学习？
[^X,Y分别表示源语言和目标语言的词汇表。任意x∈X，所有的y∈Y都可能是它的译文P(x<->y;s,t)在观测到（s,t)的前提下X和y互译的概率。x是句子中t中的词，y属于句子t中的词。分子表示x和y在句子(s,t)中出现的次数，分母是任意x’和任意y‘在(s,t)共同出现的次数。]:
出现零概率使用平滑算法。
如何从大量的双语平行数据中学习？
[^分子分母多了一项累加符号，表示遍历所有的句对。]:
句子级翻译模型
基础模型
句子级翻译并不简单，定义新函数g(s,t),g(s,t)与翻译概率正相关。
词对齐
用二元组(j,i)来描述词对齐，即原文与译文之间对应词语的位置编号。
[^g(s,t):句子s中的单词和句子t中的单词翻译概率的乘积。g(s,t)越高，词对齐越准确，s和t之间存在翻译关系的可能性越大。]:
生成流畅的译文
上文的公式没有考虑词序信息，引入n-gram语言模型（确保流畅翻译结果）。
Plm(t)和g(s,t)相乘，这样就得到了一个新的g(s,t),同时考虑翻译准确性和流畅度。
解码（Decoding)
解码系统要找到翻译概率最大的目标译文t，
依次计算g(s,t)不可行，源语句s有m个词，每个词有n个可能的翻译候选，则有n的m次方种组合，翻译结果又有m！种排序，至少有
不同个译文。
[^机器翻译是NP问题,该算法的思想是贪心算法，系统每次都保存当前最好的结果，然后进一步保存扩展后的所有可能，计算得分后保存最好结果。]:
3.3基于词的翻译建模
空翻译？调序问题建模？数学模型描述翻译？更复杂的统计模型训练？
IBM模型基础是噪声信道，已知s和信道的性质，可以通过P(t|s)得到信源的信息，找到最可能的目标语句的过程被称为解码。
[^注意翻译的方向改变，P(s|t)而非P(t|s),P(t)是目标语句t出现的可能，P(s)是源句子s出现的可能性。引入P(s|t)和P(t)的原因是单纯使用P(t|s)会得到翻译对应比较好但不合法的语句。]:
3.3.2三个基本问题
建模：建立P(s|t)和P(t)的模型
训练：获得P(s|t)和P(t)所需的参数
解码：完成搜索最优解的过程，完成argmax
[^红的部分表示译文的可能性，蓝色表示译文的流畅程度]:
词对齐
源语言句子和目标语言单词之间的对应。
[^这里的词对齐是非对称词对齐，只对源语言做了约束，目标语言没有，如果没有对齐的目标词，就定义一个t0，引入空对齐的思想，该思想在虚词的翻译中体现较多]:
基于词对齐的翻译模型
[^引入隐含变量可将困难的问题转化为分步学习问题，aj表示第j个源单词对应到目标语单词的位置。将a视为隐含变量从t生成s就变成从t同时生成s和隐含变量的问题。]:
因为隐含变量啊很复杂，所以使用链式法则。
源语言句子：“在桌子上”，目标语“on the table”
3.4IBM模型1-2
[^词对齐的数量随着句子长度呈指数增长，如何遍历所有的对齐a，如何计S算P(m|t)、P(aj|aj−11,sj−11,m,t) 和 P(sj|aj1,sj−11,m,t)，提出了5个IBM模型.]:
[^对于每个位置 j，根据译文 t、源文长度 m、已经生成的源语言单词 sj−11和对齐 aj−11，生成第 j 个位置的对齐结果 aj，用 P(aj|aj−11,sj−11,m,t) 表示；]:
[^• 对于每个位置 j，根据译文 t、源文长度 m、已经生成的源语言单词 sj−11和对齐 aj1，生成第 j 个位置的源语言单词 sj，用 P(sj|aj1,sj−11,m,t) 表示]:
3.4.1IBM模型1
IBM1模型对公式3.19进行简化。
假设P(m|t)为常数 ε，源语言的长度的生成概率服从均匀分布，
对齐概率仅依赖于译文长度l，每个词对齐连接的概率服从均匀分布
源语单词sj的生成概率及依赖于对齐的译文单词
将三式和公式3.19代入公式3.18中
3.4.2IBM模型2
IBM模型1简化了问题，但假设太强，但如果词对齐的生成概率服从均匀分布，模型会忽略目标语言单词的位置信息，IBM2考虑了这一点，生成位置aj与j、m、l有关。
[^这样要执行O((l+1)^m)如果将计算式改为3.29，则计算复杂度降为O((l+1)m,先乘后加改为先加后乘。]:
3.4.4训练
完成建模与解码，接下来要进行设置参数，最重要的。训练的过程就是在给定数据集上调整参数得到最优解。可以把优化目标视为对似然函数的优化。可以描述为对目标函数Pθ(s|t)的优化过程。
优化
解决这类问题的常用方法是把带约束的目标函数转化为不带约束的目标函数。用到的是拉格朗日乘数法，
调整为无约束的函数后通过求偏导，再更新一组参数。
这种方法叫期望最大化，简称EM方法
3.5IBM模型及隐马尔可夫模型
[^采用更细致的建模方法，引入产出率、单词的抽象，隐马尔科夫模型和IBM有一定的联系但是从另一个视角看翻译问题。]:
IBM1-2的基础上把奴痛的源语言单词看作相互独立的单元进行词对齐和翻译，这里提出另一个模型。首先确定每个目标语言单词生成源语言单词的个数，再决定译文中的每个单词生成的源语言单词，形成了一个列表。
[^蓝色：生成元语言单词的个数eg:scientists有两个含义“科学家”和”们“，红色用来存储可以用Π来表示元语言单词存储的位置eg：{Π1}={Π11=1，Π12=2}]:
[^s、t、m 和 l 分别表示源语言句子、目标语译文、源语言单词数量以及译文单词数量。φ、τ 和 π 分别记录产出率、生成的源语言单词以及它们在源文中的位置。]:
一组 τ 和 π（记为 < τ,π >）可以决定一个对齐 a 和一个源语句子 s。相反的，一个对齐 a 和一个源语句子 s 可以对应多组 < τ,π >，这里把不同的 < τ, π > 对应到的相同的源语句子 s 和对齐 a 记为 < s,a >。因此计算 P(s,a|t) 时需要把每个可能结果的概率加起来，如下：
，<s,a>包含
个不同的二元组< τ,π >
s、t、m 和 l 分别表示源语言句子、目标语译文、源语言单词数量以及译文单词数量。φ、τ 和 π 分别记录产出率、生成的源语言单词以及它们在源文中的位置。
[^红色：目标单词产出率建模，即 φi的概率。绿色：词汇翻译建模 。黄色：[1, l] 的目标语言单词生成的源语言单词的扭曲度。灰色：i = 0 时的扭曲度建模，即空标记 t0生成的源语言单词在源语言句子中位置的概率。]
IBM模型3
IBM模型3通过一些假设对图3.31进行化简
在已经放置了k个空对齐源语言单词的时候,应该 φ0-k个空位置,如果第i个位置为空,
,,对于上式就有
在IBM模型3中假设在所有的非空对齐源语言单词都被生成出来后.这些单词都以p1概率随机产生”槽”来放置空对齐单词.这样φ0就服从了一个二项分布.
,可得到P(s|t)的表达式
IBM模型4
IBM1-3中都不能很好地处理一个目标语言对应多个源语言单词的情况,因为相同目标语言对应多个源语言那么这些源语言单词往往构成短语或搭配.,但是模型1-3把这些源语言单词堪称独立的单元
[^概念单元或概念(concept)是具有独立语法的一组词语,源语言和目标语言的cept不一定相等,在IBM词框架下,每个cept只能由一个目标语组成[i]表示位置⊙i表示位置为[i]的目标语对应源语言位置的平均值]:
模型4对3进行修改,主要把扭曲度分解为两类参数,[i]对应源语言单词列表(τ[i]) 中的第一个单词 (τ[i]1）
[^这里的函数A,B分别把目标语言和源语言的单词影射到单词的词类,这样可以减少数据的稀疏程度也可以减少参数空间的大小]:
IBM4模型的过程就是将t[i]生成的第一个源语言单词代表整个t[i]生成的单词列表,先把第一个源语言单词放在合适的位置,再根据相对距离放置其他单词,这样就保证了同一目标单词生成的源语言单词之间可以互相影响
IBM模型5
模型34都有可能将一部分概率分配给一些不存在的句子(缺陷Deficiency),因为没有这样的约束,如果已经放置了某个源语言单词的位置不能防止其他词放入同样的位置.,模型5针对这个问题增加了约束,即预先判断目标位置是否为空
3.5.5隐马尔科夫模型(Hidden Markov Model，HMM)
隐马尔科夫模型是针对IBM2模型的改进版.描述一个系统,隐含状态的转移和可见状态的概率.
HMM包括三个问题:
- 估计：给定模型根据可见状态链计算该结果概率。（前后向算法）
- 参数学习：给定隐含状态数量，根据多个可见状态链估计模型的参数（EM算法）
- 解码问题：给定模型和可见状态链，计算最可能出现的状态序列。(Viterbi Algorithm,动态规划）
HMM词对齐模型，词语与词语之间并不是毫无联系的，对其概率取决于对齐位置的差异。不是所有的模型使用EM算法都能找到全局最优解，IBM模型1是一个凹凸函数，理论上使用EM方法是能找到全局最优解的。IBM1是凸函数，理论上使用EM方法能找到全局最优解，IBM1训练结果与参数初始化过程无关
基于短语和句法的机器翻译模型
4.1翻译中的结构信息
相较于基于单词的机器翻译模型，如果在翻译红茶时很大概率会翻译成“red tea”而非”black tea”,如果机器翻译系统能记住这样的搭配就可以做得更好。
使用短语的优点在于引入更大颗粒度的翻译单元给建模增加了灵活性，同时增大了翻译假设空间
4.2基于短语的翻译模型
定义4.2.1对于一个句子W=w1w2w3…wn,任意子串w1…wj（i<=j且0<=i,j<=n)都是句子W的一个短语
定义4.2.2如果一个句子W=w1w2….wn可以被分为m个子串，则称W由m个短语组成，记W=p1..pm,pi是W的一个短语，p1,,pm被称为句子W的一个切分
定义4.2.3双语短语
源语和目标语句对(s,t),s和t中的任意一个短语都可以构成一个双语短语对，简称短语对，<->表示互译关系
定义4.2.4基于短语的翻译推导
{aj}表示{tj}中每个短语对应到源语言短语的编号，构成了s到t的基于短语的翻译推导
有四个基本问题
- 用统计模型描述每个翻译推导的好坏——翻译的统计建模问题
- 获得双语短语对
- 对调序问题建模
- 找到输入句子s的最佳译文
4.2.2数学建模及判别式模型
统计学习的目标是找到生成概率最大的译文即t=argmax(P(t|s)),可以把翻译推导d当作从s到t翻译的隐含结构。P(t|s)=ΣP(d,t|s),因为空间D中d数量太大枚举很费时间，所以可以选择最好的n个翻译推导来代表整个空间D，
另一种方法是用P(d,t|s)的最大值代表整个翻译推导的概率和，翻译的目标可以被重新定义为
对数线性模型
how to denifite P(d,t|s)?可以使用判别式模型对P(d,t|s)进行描述。
[^每个特征用函数 hi(d,t,s) 表示。每个特征都对应一个权重 λi，这样值越大得分越高，最大的好处在于它可以更灵活的引入特征。]:
搭建模型
设计特征函数+获得最好的特征权重{ λi}
4.2.3短语抽取
获得短语翻译的常用方法，图中任意一个矩阵框都是双语短语，为了提高效率获得有效的短语对
定义4.2.5与词对齐一致的双语短语
对于源语言句子 s 和目标语句子 t，存在 s 和 t 之间的词对齐。如果有 (s,t) 中的双语短语 (s,t)，且 s 中所有单词仅对齐到t 中的单词，同时t 中所有单词仅对齐到s 中的单词，那么称 (s,t) 与是与词对齐一致的（兼容的）双语短语。
获取词对齐
IBM模型获得的模型是不对称的，为了获得对称的，先前向后反向再取交并集
词对齐质量可以用词对齐错误率AER评价
度量双语短语质量
[^分母是短语s在S中出现的次数，count(s,t)在（S,T）中被抽取出来的次数。]:
这样对于低频短语不合理，但是可以把短语拆解为单词，简介度量，可以使用词汇话翻译概率，词对齐信息本身就包含了
调序
为了使得译文质量提高，在双语短语之外还需要进行调序，调序包括基于距离、基于方向(WSD)以及基于分类。
基于距离：度量当前结果与顺序翻译之间的差距
基于方向的调序模型:顺序(M)：monotone,源与目标的顺序相同,与前一个短语交换位置（S）：swap,对应的短语顺序在目标语中是相反的,非连续翻译（D）：discontinuous,两个短语之间有其他的短语
基于分类的调序
使用最大熵、SVM等分类器输出调序概率
4.2.6 最小错误率训练（Minimum Error Rate Training,WERT)
在统计机器翻译中，短语抽取和翻译概率被看作是模型训练，特征权重的训练，被称作权重调优。
[^假设翻译结果相对于标准答案的错误是可度量的，通过降低错误数量的方式来找到最优的特征权重]:
[^所有样本的参考译文集合为R={r1,r2,..,rN},通过调整不同特征的权重λ = {λi}，让错误率最小Error(),Error可以是WER,PER,BLEU,NIST。]:
BLEU本身是不可微分函数，无法梯度下降，可以使用线搜索
横坐标为所有的M个特征函数，纵坐标为权重可能的取值，遍历所有的特征权重取值的组合有
种。假设计算BLEU的时间开销为B，那么遍历所有的路径时间复杂度为
,对全搜索的改进可以是局部搜索，循环处理每个特征，每一次只调整一个特征值，找到使BLEU达到最大的权重，这种方法被称为格搜索。
[^BLEU(Bilingual Evaluation Understudy双语评估替补）]:
假设对于每个输入的句子，翻译模型生成了两个推导(d1,d2),score(d)表示成关于第i个特征值的权重λi的线性函数
在交叉点右边d1是最优的翻译结果，左侧是d2是最优的结果，只需要比较左侧右侧BLEU谁高就好
4.2.7栈解码
解码的目的是根据模型和输入找到模型得分最高的推导。机器翻译被证明是一个NP问题，无法简单暴力搜索，介绍一种基于栈的从左到右的方法。
剪枝
在句子变长时，有可能空间爆炸，可以使用束剪枝，即思路一：在每次翻译扩展时最多生成k个新的翻译假设，对束宽度进行限制，也称为直方图剪枝。思路二：每次扩展只保留与最优翻译假设得分相差在δ 之内的翻译假设。即阈值剪枝
假设重组
对翻译假设进行的重新组合，把代表同一个译文的不同翻译假设融合为一个翻译假设，两个不同的翻译假设需要舍弃分数较低的
解码中的栈结构
因为质量较差的翻译假设在早期出现时，会被剪枝，这样可以减少搜索空间，但是删除的翻译假设可能又被重新搜索出来，过早地删除翻译假设也可能导致无法搜索到最优。
所以我们可以引入栈结构，对翻译假设进行整理，当放入栈的翻译假设超过一定阈值可以删除模型得分低的，每个栈代表覆盖源语言单词数量相同的翻译假设，翻译相同数量的单词所对应的翻译假设
翻译相同数量的单词所对应的翻译假设一般是 “可比的”，因此
在同一个栈里对它们进行剪枝带来的风险较小。
基于层次短语的模型
单词间的距离有时需要距离很远的搭配，但是如果使用长短语来解决长距离依赖问题。
[^左右连接的方框表示翻译模板的源语言和目标语言中的变量被同步替换。]:
同步上下文无关法（Synchronous Context-free Grammar，SCFG)
很好的解决短语系统对翻译中长距离调序建模不足的问题。
胶水规则
在实际系统中需要把两个局部翻译拼接到一起。需要引入胶水规则
引入一个新的非终止符S，S只能和X顺序拼接，或者S由X生成，胶水规则将句子都划分为若干部分，每个部分都被归纳为X
处理流程
双语数据中学习同步翻译语法，进行翻译特征的学习）规则+特征即为翻译模型，从目标语言数据中学习语言模型，将二者一起送入解码器。
4.3.2层次短语规则抽取
通过挖槽的方法来进行大量的层次短语抽取，但是我们需要进行限制，包括：抽取的规则最多可以跨越 10 个词； 规则的（源语言端）变量个数不能超过 2； 规则的（源语言端）变量不能连续出现
4.3.3翻译模型及特征
对每一条翻译规则有:
(h1-2)短语翻译概率
(h3-4)词汇话翻译概率
(h5)翻译规则数量
(h7)短语规则数量
最终模型得分为：
[^log表示语言模型得分，|t|表示译文长度]:
4.3.4CKY解码
CKY方法可以看作是基于二叉规则的一种分析方法，从小范围开始不断扩大，最终完成整个字符串的分析，跨度是表示从一个起始位置到一个结束位置中间的部分。
CKY方法跨度由小到大的次序执行，是一种自上而下的分析。对每个跨度要检查：
是否有形如 A→a 的规则可以匹配
是否有形如 A→BC 的规则可以匹配。
[^第一种匹配字符串即可第二种需要将当前跨度分为两部分，左边归纳为B右边为C]:
还有两个实践问题：
1.剪枝：CKY中每个跨度的推导呈指数关系，存储有困难所以使用束剪枝，只保留top-k个推导，局部结果只保留最好的k个，k=1为贪心
2.n-best:整个句子的翻译结果保存在最大跨度所对应的结构，去除排名前n即可
4.3.5立方剪枝
[^立方剪枝假设如果空间某个点的得分较高，那么它周围的点得分也较高。]:
4.4基于语言学句法的模型
在翻译中使用树结构可以更有效的对句子结构进行抽象，在句子中距离较远的在树结构可以很近，层次短语没有语言学句法标记，而且不允许对多个结构进行调序。
4.4.2基于树结构的文法
有两种规则：树到树、树到串
树到树翻译规则
（Nt,Ns,Ts,Tt,Is,It,R)
Ns,Nt源、目标非终结符集合
Ts,Tt源、目标终结符集合
Is∈Ns,It∈Nt，其实非终结符集合
R是规则集合，r∈R，
[^αh∈Ns，βh∈Nt，αr，βr表示由源语言(目标）终结符和非终结符组成的树结构，~是αr和βr叶子非终结符1-1对应关系]:
基于树结构的翻译推导
树到树：同步树替换文法规则
树到串翻译规则
4.4.3树到串翻译规则抽取
文法归纳和解码，文法归纳学习规则以及特征，解码利用得到的文法进行分析获得概率最高的翻译推导。介绍树到串的经典方法——GHKM
树的切割与最小规则
GHKM input：源语言句子及句法树、目标语言句子、源与目标之间的词对齐
定义4.4.2Span目标语言第一个单词与最后一个单词所构成的范围，4.4.3Comlement Span除了祖先和子孙外其他节点Span的并集
4.4.4对于Span与Complement Span不相交，节点node可信，说明和其他部份无歧义
4.4.5一个树片段根节点和叶子结点的非终结系节点都是可信节点，那么树片段合格
所有可信节点可以看作是边缘集合，边缘集合定义了哪些可以被切割，切割后得到的片段不能再被分割，被称为最小规则
组合规则
同时处理多个变量的调序，需要规则同时处理多个变量时需要更大的规则，称为composed-m规则（m个最小规则）
SPMT规则
对任意一个与词对齐兼容的短语可以找到包含它的最小翻译规则。
句法树二叉化
句法树是描述句子结构的工具，但是过于扁平抽取困难，可以进行二叉化，树二叉化可以帮助规则抽取到更细颗粒度的规则
4.2.4树到树翻译规则抽取
可以基于节点对齐进行规则抽取，这样可以避免词对齐的错误：先利用外部节点对其工具或的对应关系，再将每个对其的节点看作是树片段的根节点进行规则抽取。也可以使用对齐矩阵
4.4.6基于超图的推导空间表示
在句法分析中，上下文无关文法（CFG）可以被组织成一个叫有向超图的结构。或称为超图
