最近在上机器翻译的课程。作为机器翻译领域的统计学模型的开山模型，姑且记录一下吧。
背景
一段时间之前，机器翻译主要靠专家手写语法规则，这样做机器翻译太慢、太贵、太难维护，比如我们看下面两句话：
Time flies like an arrow.
Fruit flies like a banana.
这两句话的结构极其相似，唯一的区别便是用词不同，词的含义不同。如果想要通过写规则，从语法句法上将这两句话翻译成中文，就会很麻烦。
随着技术的不断发展，我们获得了大量的平行语料，所谓平行语料，就是意义相同的句子，用两种语言书写，比如：
{
"zh-cn": "我是一只猫",
"en-US": "I am a cat",
"ja": "私は猫が好き"
}那么学者就想，可否应用统计学的方法，从双语语料中自动学习出对应关系？学者发现，不同语言的句子之间，词语之间是有一个大致的对应关系的。比如在我们的例子中，从中文到英语，单词之间是严格对应的，但是从中文到日语，会发现有些语法助词，比如「は」和「が」，没有一个很好的对应关系。所以我们需要在工程上做一点设计。
核心思想
学者们首先不去想如何解决这个问题，它们首先想，什么是一个好的机器翻译系统。这很简单，给定平行语料，对于一个意义的句子，源端目标端分别是$s$和$t$，那么对于一个理想的机器翻译系统$M$，它必然满足：
$$ M(s)=t $$
即给定源端，它会输出一个最合适的目标端句子，那么模型的参数就相当于：
$$ \theta =\arg\max P(f\mid e) $$
让理想的目标端句子出现的概率最高即可，但是当我们部署系统之后，源语言句子和目标语言句子几乎不可能在语料库中出现过，因此这个概率无法直接从语料库统计得到。所以我们不直接学习分布，而是先找到共现关系！我们先引入一个变量，叫做对齐变量：$a_j=i$，表示源端的第$i$个词，会翻译成目标端的第$j$词。那么有些词没有很好的对应关系，就把它们看作是由空白词（记作null）生成过来的。比如：
SRC: null 我 喜欢 猫
TGT：私 は 猫 が 好き
对于目标端（TGT）的「私」，是由源端（SRC）的「我」一次生成过来的，从0开始索引，这就是第一个词……按照这个规律，我们能得到对齐变量为$a=(1,0,3,0,2)$。
数学推导
根据全概率公式，我们的目标：
$$ P(e\mid f) = \sum P(f,a\mid e) $$
然后把对齐变量打开，用$t(f_j|e_{a_j})$表示从$e_{a_j}$，源端的第$a_j$个词，翻译到目标端的第$j$个词的概率（$l$为源端句子长，$m$为目标端句子长）：
$$ P(e\mid f) = \sum_{a_1=0}^l\sum_{a_2=0}^l\cdots\sum_{a_m=0}^l\frac{1}{(l+1)^m}\prod_{j=1}^mt(f_j|e_{a_j}) $$
直接计算这个公式，复杂度太高，做一个简化，我们先考虑目标和源端都有两个词的情况：
$$ P(f\mid e)=\sum_{a_1=0}^l\sum_{a_2=0}^lt(f_1|e_{a_1})t(f_2|e_{a_2}) $$
根据高等数学的知识，级数前后两项分别只于自己的求和下标有关，拆开：
$$ P(f\mid e)=\sum_{a_1=0}^l\sum_{a_2=0}^lt(f_1|e_{a_1})t(f_2|e_{a_2})=(\sum_{a_1=0}^l(f_1|e_i))(\sum_{a_2=0}^l(f_2|e_i)) $$
Good，现在推导到$m$个词的情况：
$$ P(f\mid e)=\frac{1}{(l+1)^m}\prod_{j=1}^m\sum_{i=0}^lt(f_j|e_i) $$
这个公式的感性理解就是：目标词$f_j$可以由源句中任意一个词生成，所以它的概率是所有可能来源的贡献之和。整个目标句由每个目标词独立生成，所以再把每个目标词的概率乘起来。所以，我们的问题从「构造翻译系统」，变成了「找到一个最大化概率的词对齐关系」！但是……不知道怎么去学习！
训练推导
训练这里就用EM算法，严格的推导需要拉格朗日乘子法，但是没学过太难了看不懂，用一个比较直觉的方法！假设有一个新人进了汉化组，新人什么都不懂，所以觉得：
猫 可能是 cats
猫 也可能是 like
猫 甚至可能是 I
看字幕总结一下规律：
猫 和 cats 总是一起出现
好き 和 like 总是一起出现
犬 和 dogs 总是一起出现
那么就把：
猫 -> cats 的概率高一点
好き -> like 的概率高一点
犬 -> dogs 的概率高一点
最后就能学到一个真正的对应关系。
落到形式上，假设我们有双语平行语料：$D=\{(e^{(s)},f^{(s)})\}_{s=1}^S$，我们的目标是找一个概率分布，让训练目标端句子出现概率最大：
$$ L(t)=\prod_{s=1}^SP(f^{(s)}\mid e^{(s)}) $$
取对数积变和，因为加法远比乘法好处理：
$$ l(t)=\log L(t)=\sum_{s=1}^S\log P(f^{(s)}\mid e^{(s)}) $$
把后面的概率用上面的推导代入：
$$ l(t)=\sum_{s=1}^S\log [\frac{1}{(l_s+1)^{m_s}}\prod_{j=1}^{m_s}\sum_{i=0}^{l_s}t(f_j^{(s)}\mid e_i^{(s)})] $$
拆开：
$$ l(t)=\sum_{s=1}^S[-m_s\log(l_s+1)+\sum_{j=1}^{m_s}\log\sum_{i=0}^{l_s}t(f_j^{(s)}\mid e_i^{(s)})] $$
加和的前一项和句子长度有关，和优化没关，要优化的就只有后面一项，约束为$\sum_ft(f\mid e)=1$。
这之后我们就用E步，估计隐变量的概率，也就是「在当前模型看来，每种词对齐概率是多少呀？」，随后用M步更新参数，「重新估计一下概率吧？」。EM算法的思想就是，「当模型里有看不见的隐变量时，先根据当前参数“猜”隐变量的分布，再用这个猜出来的分布重新估计参数。不断重复」。
E步我们要求的概率是：$P(a\mid e,f;\theta^{old})$，首先根据「每个词独立生成」的假设，和贝叶斯公式：
$$ P(a_j=i\mid f,e)=\frac{P(a_j=i,f_j\mid e)}{\sum_{i'=0}^lP(a_j=i',f_j|e)} $$
然后根据条件概率的知识：
$$ P(a_j=i,f_j\mid e)=P(a_j=i\mid e)P(f_j\mid a_j=i,e) $$
以及我们第一次迭代的时候假设，每个词翻译到目标词的概率都是均等的：
$$ P(a_j=i\mid e)=\frac{1}{l+1} $$
那么上面的公式变成：
$$ P(a_j=i,f_j\mid e)=\frac{1}{l+1}t(f_j\mid e_i) $$
代入到上面的式子，上下约去$\frac{1}{l+1}$：
$$ P(a_j=i\mid f,e)=\frac{t(f_j\mid e_i)}{\sum_{i'=0}^lt(f_j\mid e_i')} $$
这是一个类似Softmax的形式，其含义为：一个源词$e_i$对目标词$f_j$的责任，等于它的翻译概率除以所有候选源词的翻译概率总和。举个例子，假设我们的例子：
SRC: null 我 喜欢 猫
TGT：私 は 猫 が 好き
对于日语的「猫」，从「null」、「我」、「喜欢」和「猫（中文）」翻译到它的概率分别是0.01、0.02、0.05和0.88,那么：
$$ P(a_j=猫\mid f,e)=\frac{0.88}{0.01+0.02+0.05+0.88}=0.92 $$
这个0.92我们称之为软计数。
到达M步，如果我们已知词对齐的话，只需要计算：
$$ t(f|e)=\frac{\text{count}(e,f)}{\sum_{f'}\text{count}(e,f')} $$
但是，我们不知道真实的词对齐关系，就用软计数代替$\text{count}$去更新。
总结
有没有方便记忆的方法呀……公式看不懂一点！当然有了！因为翻译不只是翻译，也可以是广义的序列任务！
假设你有一集电视剧/电影/番剧。你要根据视频生成最有可能的弹幕/即时评论列表。有很多弹幕，但是你很笨，不知道这些弹幕要在什么时候发出去。
那么可以做这样的事情：
1.把这个视频切分成若干片段。（分词）
2.尝试对应片段和弹幕。（加入对齐变量和E步）
3.根据已有的训练集，大量片段和弹幕，慢慢找到共现规律。（M步）
4.训练完成。
效果：名场面 ← 反派登场 ？？？？？？ ← 主角做出反人类的举动