基于单词的统计翻译模型 IBM Model1

统计翻译模型的基本思想是对大量平行(parallel)语料进行统计分析。之前实习的时候有幸接触到一些简单的模型,而事实上这种简单的模型在大量数据训练的基础上,发挥还是挺不错的。

IBM的统计翻译模型从简单到繁琐,一共有Model1-Model5五个模型,全都是基于词的统计模型。

本文只对Model1作简单介绍,方便起见,文中以将法文(French)翻译为英文(English)为例。

噪声信道模型。机器翻译=翻译模型+语言模型

模型假定源语言中的(法语)句子是由目标语言(英语)经过含有噪声的信道编码后得到的。寻找最佳的英文翻译结果等同于寻找\arg\max_{e}p(e|f)

根据贝叶斯公式,容易得到\arg\max_{e}p(e|f)=\arg\max_{e}\frac{p(f|e)p(e)}{p(f)},由于对于同一个法语单词来说,p(f)是一定的,因此上式等同于\arg\max_{e}p(f|e)p(e),其中

  • p(f|e)称为翻译模型,即给定信号源,观察到信号的概率;
  • p(e)称为语言模型,即信号源发生的概率;

机器翻译的任务就被拆解成这两个模型的任务了。本文只负责翻译模型:)

词对齐(Alignment)

Word Alignment

我们假设要翻译的法语句子包含m个单词,即F=f_1, f_2, ..., f_m,翻译出来的英语句子包含l个单词,即E=e_1, e_2, ..., e_l,那么之前提到的翻译概率p(F|E)=p(f_1,f_2,...,f_m|e_1,e_2,...,e_l, m)其中包含了对句子长度服从这么个条件分布p(m|l)的假设。

然而这个概率是很难直接建模的,于是一帮聪明的人想出来一个方案:引入词对齐(word alignment):p(F|E)=p(F,A|E)=p(f_1,f_2,...,f_m,a_1,a_2,...,a_m|e_1,e_2,...,e_l, m),其中这个a就是词对齐,它是个隐变量,表示源语言(法语)中的某个单词是用目标语言(英语)翻译而来的。

具体可以看这个例子:

这个例子中,l=6, m=7,一个理想的对齐方式如下:

它对应的alignment标记可以表示为a_1,a_2,...,a_7=<2,3,4,5,6,6,6>

此外在英文中还有加入个特殊的NULL单词,它表示法语中那些对于英语翻译“无用”的词。

IBM Model 1:翻译模型=对齐+词-词翻译

根据之前单词对齐的假设,我们可以把翻译任务进一步拆分成两部分:对齐和词到词的翻译,边际化参数A

p(F|E)=\sum_{A}p(F,A|E)=\sum_{A}p(A|E)p(F|E,A)

第一部分是对齐,在Model 1中做了一个最简单的假设:每个对齐都是等概率发生的。所以p(a|e)=\prod_{i=1}^{m}\frac{1}{l+1}

第二部分是词-词翻译,也是整个模型的核心部分,这里当然不能再精简了,否则就没有了…

P(F|E,A)=\prod_{j=1}^{m}tr(f_j|e_{A_{j}})

这里头的tr(.|.)就是单词到单词的翻译概率,也就是模型要学习的东西。

模型训练:期望最大化(EM)

很显然,要学习到词-词翻译概率,就必须知道单词对齐;要学习单词对齐,就得知道翻译概率,这种鸡生蛋的问题就需要用EM来解。

定义一个参数\delta(k,i,j)表示第k组平行预料(训练集中法文-英文句子)里的第i个法文词,第j个英文词。如果是上帝模式,那\delta(k,i,j)=1/0分别表示这两个词之间应当/不应当对齐。然而目前无人能观测到这个隐变量,所以采用最大似然估计来估计这个东西,意思就是说翻译概率的大小决定了单词对齐的概率,即

\delta(k,i,j)=\frac{q(j|i,l_k,m_k)tr(f_i^{(k)}|e_j^{(k)})}{\sum_{j=0}^{l_k}q(j|i,l_k,m_k)tr(f_i^{(k)}|e_j^{(k)})}=\frac{tr(f_i^{(k)}|e_j^{(k)})}{\sum_{j=0}^{l_k}tr(f_i^{(k)}|e_j^{(k)})}

注意上面这个式子是根据Model 1“句子中的对齐都是等概率”假定推导来的:q(j|i,l_k,m_k)=\frac{1}{l^{(k)}+1}

算法

输入:训练集(f^{(k)}, e^{(k)})其中k=1,...,n,其中f^{(k)}=f_1^{(k)}...f_m^{(k)}, e^{(k)}=e_1^{(k)}...e_l^{(k)}

初始化:初始化所有词-词翻译概率t(f|e)

步骤:关键部分我用绿色的字注释了

  • for t=1…T
    • Set all counts c=0
    • for k=1...N
      • for i=1...m_k
        • for j=1...l_k
          • // word(i,j) in parallel corpus line k
          • \delta(k,i,j)=\frac{tr(f_i^{(k)}|e_j^{(k)}}{\sum_{j=0}^{l_k}tr(f_i^{(k)}|e_j^{(k)})} //estimate alignment
          • c(e_j^{(k)},f_i^{(k)})+=\delta(k,i,j) //update co-occurence count for word-word pair
          • c(e_j^{(k)})+=\delta(k,i,j)
    • tr(f|e)=\frac{c(e,f)}{c(e)} //update word-word pair translation probabilities

输出:tr(f|e)

 

参考文献

  1. http://www.cs.columbia.edu/~mcollins/courses/nlp2011/notes/ibm12.pdf
  2. http://cpmarkchang.logdown.com/posts/245418-mt-ibm-model-1
  3. https://zh.wikipedia.org/wiki/%E7%BB%9F%E8%AE%A1%E6%9C%BA%E5%99%A8%E7%BF%BB%E8%AF%91

召回率 Recall、精确度Precision、准确率Accuracy、虚警、漏警等分类判定指标

转载自:http://hi.baidu.com/lwhptl/item/c2da5a3c098e4ac6382ffa5f

假设原始样本中有两类,其中:
1:总共有 P个类别为1的样本,假设类别1为正例。
2:总共有N个类别为0 的样本,假设类别0为负例。
经过分类后:
3:有 TP个类别为1 的样本被系统正确判定为类别1,FN 个类别为1 的样本被系统误判定为类别 0,显然有P=TP+FN;
4:有 FP 个类别为0 的样本被系统误判断定为类别1,TN 个类别为0 的样本被系统正确判为类别 0,显然有N=FP+TN;

那么:
精确度(Precision):
P = TP/(TP+FP) ;  反映了被分类器判定的正例中真正的正例样本的比重(

准确率(Accuracy)
A = (TP + TN)/(P+N) = (TP + TN)/(TP + FN + FP + TN);    反映了分类器统对整个样本的判定能力——能将正的判定为正,负的判定为负

召回率(Recall),也称为 True Positive Rate:
R = TP/(TP+FN) = 1 – FN/T;  反映了被正确判定的正例占总的正例的比重

转移性(Specificity,不知道这个翻译对不对,这个指标用的也不多),也称为 True NegativeRate
S = TN/(TN + FP) = 1 – FP/N;   明显的这个和召回率是对应的指标,只是用它在衡量类别0 的判定能力。

F-measure or balanced F-score
F = 2 *  召回率 *  准确率/ (召回率+准确率);这就是传统上通常说的F1 measure,另外还有一些别的F measure,可以参考下面的链接

上面这些介绍可以参考:
http://en.wikipedia.org/wiki/Precision_and_recall
同时,也可以看看:http://en.wikipedia.org/wiki/Accuracy_and_precision

为什么会有这么多指标呢?
        这是因为模式分类和机器学习的需要。判断一个分类器对所用样本的分类能力或者在不同的应用场合时,需要有不同的指标。 当总共有个100 个样本(P+N=100)时,假如只有一个正例(P=1),那么只考虑精确度的话,不需要进行任何模型的训练,直接将所有测试样本判为正例,那么 A 能达到 99%,非常高了,但这并没有反映出模型真正的能力。另外在统计信号分析中,对不同类的判断结果的错误的惩罚是不一样的。举例而言,雷达收到100个来袭导弹的信号,其中只有 3个是真正的导弹信号,其余 97 个是敌方模拟的导弹信号。假如系统判断 98 个(97 个模拟信号加一个真正的导弹信号)信号都是模拟信号,那么Accuracy=98%,很高了,剩下两个是导弹信号,被截掉,这时Recall=2/3=66.67%,Precision=2/2=100%,Precision也很高。但剩下的那颗导弹就会造成灾害。

因此在统计信号分析中,有另外两个指标来衡量分类器错误判断的后果:
漏警概率(Missing Alarm)
MA = FN/(TP + FN) = 1 – TP/T = 1 – R;  反映有多少个正例被漏判了(我们这里就是真正的导弹信号被判断为模拟信号,可见MA此时为 33.33%,太高了)

虚警概率(False Alarm)
FA = FP / (TP + FP) = 1 – P;反映被判为正例样本中,有多少个是负例。

统计信号分析中,希望上述的两个错误概率尽量小。而对分类器的总的惩罚旧是上面两种错误分别加上惩罚因子的和:COST = Cma *MA + Cfa * FA。不同的场合、需要下,对不同的错误的惩罚也不一样的。像这里,我们自然希望对漏警的惩罚大,因此它的惩罚因子 Cma 要大些。

       个人观点:虽然上述指标之间可以互相转换,但在模式分类中,一般用 P、R、A 三个指标,不用MA和 FA。而且统计信号分析中,也很少看到用 R 的。如果有错误的地方,欢迎指出并改正