June 23, 2009

The Mathematics of Statistical Machine Translation: Parameter Estimation
Peter E Brown, Vincent J. Della Pietra, Stephen A. Della Pietra, Robert L. Mercer
Computational Linguistics, Vol 19‐2, 1993, ACL, pp.263‐311 (Jun.,23,2009 揚石担当)
目的
• 背景
– 統計機械翻訳に注目
• 利用可能なパラレルコーパスが増大
• 過去の研究により、有用性確認
• 統計モデルの提案
– 文対からのパラメタ推定
• 単語アラインメント
5つのmodelを提案
アラインメントの種類
英単語が独立
フランス単語が独立
一般的
統計翻訳
• フランス語Ｆから英語Ｅへの翻訳
– Ｐ（e|f） が最大となるようなe^が最尤な翻訳
•
– ベイズの定理より
•
– P(f)は無視⇒入力に対し、一定値
– P(e)
：language model
– P(f|e)
：translation model ⇒これに注目
翻訳モデル
• アラインメントを導入
–
–
• 英文：
• 仏文：
• アラインメント：
– a1=2
それぞれ 0からｌの間の値を持つ
Model1
•
– 様々な仮定を適用
• Pr(m|e)
•
•
•
= 仏文の長さ(単語数)がmである確率
= ある定数ε
=j 番目の仏単語がつながるのが
aj番目の英単語の確率
= どの場所にも同確率
=(l+1)‐1
=j 番目の仏単語がfjの確率
= fjとeajのみで決まる
=
Model1
•
• aについて和をとる
–
（ｊ:1～m、aj:0～l）
– 上式で推定すべきパラメタはt()のみ
– 制約条件：
より
ラグランジュの未定乗数法を用いて極値を求める
–
• t(f|e)で偏微分
–
– これを0として
eとfがaで繋がっている回数
•
• 両辺にt()が出現
– ＥＭアルゴリズムによりt()を求める
• 簡単化
よりt(f|e)は
–
–
– 期待値を定義
•
• Pr(a|e,f)=Pr(f,a|e)/Pr(f|e)を用いλePr(f|e)をλeとすると
–
–
S個のデータセットでは
λe:正規化項
計算量の問題
•
(l+1)m回の計算が必要
を導入
•
– 計算量:(l+1)m⇒m(l+1)
– m = 3,l = 1として
• 左辺:t10t20t30 +t10t20t31 +…+ t11t21t30 + t11t21t31
• 右辺:(t10+t11) (t20+t21) (t30+t31)
– また、Pr(f|e)は
•
偏微分の再計算
•
• これにより
–
重み
– 計算量:l+m
fとeの対応数
パラメタ推定アルゴリズム
1. t(f|e)の初期化
2. 各文sについて、
3. 各eについて、λeを計算
–
4. 各ｆについて、t(f|e)を更新
–
5. 繰り返し
を計算
実行例
– 私 は 、 皆 と 喜び を 分かち 合う こと の 中 に
1 2 3 4 5 6 7 8 9 10 11 12 13 共同 の 冒険 が ある こと を 主張 し たい 。
14 15 16 17 18 19 20 21 22 23 24
– NULL ({ 2 24 }) I ({ 1 }) call ({ 5 7 20 22 }) for ({ }) a ({ 3 17 }) collective ({ 18 }) adventure ({ 16 }) in ({ 11 13 15 }) generalized ({ 4 8 9 10 12 14 19 21 23 }) joy ({ 6 }) Model2
• Model1：単語の位置を考慮しない
⇒単語の位置考慮で精度向上の可能性
• Mode1を変更
–
• (l+1)m⇒
• 制約条件を追加：
–
–
Model2
の変更
•
– 期待値：
– Model1と同様に
•
•
– 効率化
•
• これにより、期待値は
–
–
Model2
• Model1
– Model2の特殊なケース
• a(i|j,m,l)=(l+1)m
• Model2
– 複数の極大値を持つ＝最適解の保証はなし
– 初期値をModel1によって計算
Model3
• Model1、Model2
– 1対１の単語対応を想定
– 実際の翻訳
• 1対多 または 1対なし がありえる
• “the”
⇒ “le lo,…” or “ ”
• “only”
⇒ “seulement” or “ne…que”
• Model3
– これを扱う明示的なパラメータを導入
• “fertility”：繁殖力
Model3のパラメタ
• n(φ|ei) :繁殖確率(fertility probabilities)
– 英単語eがφ個の仏単語に対応する確率
• t(f|ei):翻訳確率 (translation probabilities)
– 英単語eが仏単語fに翻訳される確率
• d(j|i,l,m):歪み確率(distortion probabilities)
– 英文長がl、仏文長がm で、i番目の英単語がj の
仏単語に翻訳される確率
Model3のパラメタ
• e0の繁殖確率φ0:別の確率を仮定
– 翻訳されない語数⇒仏文長に依存
–
• p0+p1=1
• 翻訳されない語数＝翻訳されない回数
Model3
•
Model3の構成
1. 繁殖確率で単語をコピー
– n(φ|ei)
2. Null生成
–
3. 単語ごとに翻訳確率で翻訳
– t(f|ei)
4. 歪み確率で位置決定
– d(j|i,l,m)
計算量の問題
• Model1,2と同様に計算すると
–
– 膨大な計算量⇒近似的に求める
ビタビアライメントと近傍の定義
• ビタビアライメント(Viterbi alighment)
– 対訳ペア中の全アライメントで、確率最大アライメント
• 近傍
– あるアライメントa • 一つの仏単語fの対応先
– 別の英単語に移動させたことによって得られるアライメントa’
• aの二つの仏語単語の対応先
– 交換することによって得られるアライメントa – a’はaの近傍
効率的な計算
• i⇒i’の変更によって得られる近傍アラインメントa’
–
効率的な計算
• i⇒i’の変更によって得られる近傍アラインメントa’
–
変更先の繁殖力
効率的な計算
• i⇒i’の変更によって得られる近傍アラインメントa’
–
変更先の繁殖確率
効率的な計算
• i⇒i’の変更によって得られる近傍アラインメントa’
–
変更前の繁殖確率
効率的な計算
• i⇒i’の変更によって得られる近傍アラインメントa’
–
変更先の翻訳確率
効率的な計算
• i⇒i’の変更によって得られる近傍アラインメントa’
–
変更先の歪み確率
– aをModel2によって計算
• 近傍を探索することにより効率化
Model4
• Model3
– 単語の位置（歪み確率）：絶対位置
• Model4
– 相対位置
– 単語同士の位置も考慮
• 英語：形容詞＋名詞
• 仏語：名詞＋形容詞
Model4の歪み確率
• head
– ある英単語に対応する仏単語の中で、最も先頭
に近いもの
CE NE EST PAS CLAIR
It is not clear
Model4の歪み確率
• head
– ある英単語に対応する仏単語の中で、最も先頭
に近いもの
• headの場合
–
– Θi‐1:i‐1番目の英単語が対応する仏単語の位置
• Θi‐1:3
• d1(‐1|A(e),B(f))が高くなるのが望ましい
CE NE EST PAS CLAIR
It is not clear
A,B:単語クラス
Model4の歪み確率
• head
– ある英単語に対応する仏単語の中で、最も先頭
に近いもの
• それ以外
–
– π[i]k‐1:同じ英単語に対応している直前の仏単語
• notの翻訳:ne pas でもしばしば動詞が挿入
• d>1(2|B(pas))が高確率
CE NE EST PAS CLAIR
It is not clear
Model5
• Model4
– 単語位置：直前の語のみ考慮
• 複数の単語を同じ位置に配置する可能性
• Model5
– 単語を空白部分に配置するよう改善
• vj:j番目までの空白数
•
•
ｊが空白：1
それ以外：0
IBM Model まとめ
•
•
•
•
•
Model1:翻訳確率のみ
Model2:Model1+単語位置（絶対）
Model3:Model2+繁殖確率
Model4:Model3+単語位置（相対）
Model5:Model4+単語位置（相対）の改良