Bài giảng Xử lý ngôn ngữ tự nhiên - Bài 6: Dịch máy - Lê Thanh Hương

1Dịch máy
1
Lê Thanh Hương
Bộ môn Hệ thống Thông tin
Viện CNTT &TT – Trường ĐHBKHN
Email: huonglt-fit@mail.hut.edu.vn
Ví dụ
Au sortir de la saison 97/98 et surtout 
au debut de cette saison 98/99 
2
With leaving season 97/98 and 
especially at the beginning of this 
season 98/99
Các vấn đề
1. Xử lý sự giống và khác nhau giữa các ngôn ngữ
Hình vị: # số âm tiết/từ:
Ngôn ngữ đơn âm tiết ( tiếng Việt, Trung Quốc) – 1
3
tiếng/từ
Ngôn ngữ đa âm tiết (Siberian Yupik), 1 từ = cả 1 câu
Mức độ phân chia âm tiết
Các vấn đề
2. Cú pháp: trật tự từ trong câu
To Yukio; Yukio ne
Tiếng Anh – tiếng Việt:
The (affix1) red (affix2) flag (head)
Lá cờ (head) đỏ (affix2) ấy (affix1)
4
3. Các nét riêng biệt
English brother Vietnamese anh
em
English wall German wand (inside)
mauer(outside)
German berg English hill
mountain
Không gian khái niệm
5
Khoảng trống từ vựng: tiếng Nhật không có từ nào nghĩa privacy;
tiêgns Anh không có từ ứng với yakoko (lòng hiếu thảo)
Ba khối chính trong dịch máy
ngôn 
ngữ 
nguồn S
ngôn ngữ đích
T
hiểu 
ngôn ngữ
dịch 
ngôn ngữ
6
thông tin ánh xạ 
ngôn ngữ 
nguồn - đích
2Hiểu ngôn ngữ
1. Nhập nhằng từ vựng:
English: book - Spanish libro, reservar
⇒ Sử dụng thông tin cú pháp
2. Nhập nhằng cú pháp:
I saw the guy on the hill with the telescope
7
3. Nhập nhằng ngữ nghĩa:
E: While driving, John swerved & hit a tree
John’s car
S: Minetras que John estaba manejando, se desvio y 
golpeop con un arbo
Các phương pháp dịch máy
cú pháp
mức trừu 
tượng
cao
ngữ nghĩa
siêu ngôn ngữ siêu ngôn ngữ
dịch chuyển đổi
8
s t
a g
từ-từthấp
a = a(s)
g = f(a(s)); f – hàm chuyển đổi
t=g(f(a(s)))
dịch trực tiếp
Sơ đồ chuyển đổi
9
Luật chuyển đổi
10
Sơ đồ chuyển đổi
11
Cách tiếp cận siêu ngôn ngữ: sử dụng 
nghĩa
Chuyển đổi: các luật chuyển đổi từ ngôn ngữ này 
sang ngôn ngữ khác
ĐỐi tượng/sự kiện (ontology)
12
3Dịch máy thống kê
13
Các kiểu dịch máy
mức độ
trừu tượng
cao
ngữ nghĩa
siêu ngôn ngữ
} chuyển đổi
14
s t
a g
từ-từ
cú pháp
thấp
ý tưởng
Coi việc dịch như bài toán kênh có nhiễu
Input (Nguồn) “Noisy” Output (đích)
The channel
E: English words... (adds “noise”) F: Les mots Anglais...
15
Mô hình dịch: P(E|F) = P(F|E) P(E) / P(F) 
Khôi phục lại E khi biết F:
Sau khi đơn giản hóa (P(F) không đổi): 
argmaxE P(E|F) = argmaxE P(F|E) P(E)
Dịch máy thống kê
16
Các yếu tố
Mô hình ngôn ngữ - Language Model (LM): xác suất thấy 
1 câu tiếng Anh (E) (xác suất tiền nghiệm):
P(E) 
Mô hình dịch - Translation Model (TM): câu đích trong 
17
tiếng Pháp (F) khi có câu tiếng Anh:
P(F|E)
Thủ tục tìm kiếm:
Cho F, tìm E tốt nhất sử dụng mô hình ngôn ngữ LM và 
mô hình dịch TM.
Vấn đề: thiếu dữ liệu!
Ta không thể tạo từ điển câu E ↔ F
Thậm thí bình thường ta không thấy 1 câu lặp lại 2 lần
Ý tưởng gióng hàng
Mô hình dịch TM không quan tâm đến chuỗi đúng các từ 
tiếng Anh
Sử dụng cách tiếp cận gán nhãn:
18
• 1 từ tiếng Anh(“tag”) ~ 1 từ tiếng Pháp (“word”)
→ không thực tế: thậm chí số từ trong 2 câu không bằng 
nhau
→ sử dụng “gióng hàng”.
Gióng hàng câu: tìm các nhóm câu trong 1 ngôn ngữ tương 
ứng với các nhóm câu khác trong ngôn ngữ khác
4Gióng hàng câu
The old man is 
happy. He has 
fished many
El viejo está feliz 
porque ha pescado 
muchos veces Su
19
times. His wife 
talks to him. The 
fish are jumping. 
The sharks await.
 . 
mujer habla con él. 
Los tiburones 
esperan.
Gióng hàng câu
1. The old man is 
happy. 
2. He has fished many 
times
1. El viejo está feliz 
porque ha pescado 
muchos veces. 
20
. 
3. His wife talks to him. 
4. The fish are jumping. 
5. The sharks await.
2. Su mujer habla 
con él. 
3. Los tiburones 
esperan.
Gióng hàng câu
1. The old man is 
happy. 
2. He has fished many 
times. 
1. El viejo está feliz 
porque ha pescado 
muchos veces. 
2. Su mujer habla con 
21
3. His wife talks to him. 
4. The fish are jumping.
5. The sharks await.
él. 
3. Los tiburones 
esperan.
Khó khăn:
Sự liên quan chéo: trật tự câu thay đổi khi dịch
Gióng hàng từ - Mức dễ
22
Gióng hàng từ - Khó hơn
23
Gióng hàng từ - Khó hơn
24
5Gióng hàng từ - Khó
25
Gióng hàng từ - Mã hóa
0 1 2 3 4 5 6 
e0 And the program has been implemented 
26
f0 Le programme a été mis en application
0 1 2 3 4 5 6 7
Gán thông tin tuyến tính:
• f0(1) Le(2) programme(3) a(4) été(5) mis(6) en(6) 
application(6)
• e0 And(0) the(1) program(2) has(3) been(4) 
implemented(5,6,7)
Học việc gióng hàng từ sử dụng 
EM
27
Học việc gióng hàng từ sử dụng EM
28
Học việc gióng hàng từ sử dụng EM
29
Kênh nhiễu
Mô hình ngôn ngữ
P(e)
Mô hình dịch
P(f|e)
e Giải mã
Argmax
=P(e|f)
f
e
30
e
6Các thành phần của mô hình dịch
Giả thiết 
Individual translations are independance
1 từ tiếng Anh – n từ tiếng Pháp
1 từ tiếng Pháp - (0-1) từ tiếng Anh
1( | ) ( | )
ml l
P f e P f e= ∑ ∑ ∏L
31
fj - từ j trong f; 
aj - vị trí trong e được gióng hàng với fj
eaj - từ trong e được gióng hàng với fj
Z là hằng số chuẩn hóa
aj = 0: từ j trong câu tiếng Pháp được gióng hàng với một 
từ rỗng (không dịch sang)
m – độ dài của f
1 0 1
j
m
j a
a a jZ = =
Ví dụ
P(Jean aime Marie| John loves Mary)
Gióng hàng(Jean, John), (aime, loves), (Marie, 
Mary) ta có 3 xác suất
32
, 
P(Jean|John) x P(aime|loves) xP(Marie|Mary)
Giải mã
)|()(maxarg
)(
)|()(maxarg
)|(maxarg
efPeP
fP
efPeP
fePe
e
e
e
=
=
=
33
Vấn đề: không gian tìm kiếm vô hạn
Mẹo:
tìm kiếm dùng ngăn xếp: xây dựng dần, lưu trong stack các 
phần đã dịch
sử dụng một số độ đo về độ phù hợp, vd., chamber/house, 
(nhưng có thể đi sai đường nếu 1 từ thường xuất hiện với từ 
khác, như commune/house, vì có Chambre de Communes (hạ 
nghị viện)
Thuật toán EM
E-step
Khởi tạo giá trị P(wf|we) ngẫu nhiên
Tính số lần tìm thấy wf trong tiếng Pháp khi có we trong 
tiếng Anh
∑
34
M-step
Đánh giá lại xác suất dịch prs từ giá trị z trên:
tổng được tính trên tất cả các từ tiếng Pháp v
( , ) . . ,
, ( | )
ef
e f
w w f e
e f s t w e w f
z P w w
= =
=
∑= v ewv
ww
ef z
z
wwP ef
,
,)|(
Đánh giá
Đánh giá dựa trên tập ngữ liệu Hansard:
48% câu tiếng Pháp được dịch đúng
2 loại lỗi:
Dịch sai nghĩa:
Permettez que je donne un example à chambre
35
• 
• Let me give an example in the House (incorrect decoding)
• (Let me give the House an example)
Dịch sai ngữ pháp:
• Vous avez besoin de toute l’aide disponsible
• You need all of the benefits available (ungrammatical 
decoding)
• (You need all the help you can get)
Lý do
Hiện tượng méo: từ tiếng Anh ở đầu câu được 
gióng hàng với từ tiếng Pháp ở cuối câu – hiện 
tượng này giảm xác suất gióng hàng
36
Hiện tượng sinh (fertility): sự tương ứng giữa từ 
tiếng Anh và tiếng Pháp (1-to-1, 1-to-2, 1-to-0, 
), 
Vd, fertility(farmers) trong tập ngữ liệu = 2, 
vì từ này khi dịch sang tiếng Anh thường gồm 
2 từ : les argiculteurs
To go → aller
7Lý do
Các giả thiết độc lập: các câu ngắn được ưu tiên hơn 
vì có ít xác suất hơn (khi nhân)
⇒ nhân kết quả với 1 hằng số tỉ lệ thuận với độ dài 
câu
37
Phụ thuộc dữ liệu luyện: 1 thay đổi nhỏ trong dữ liệu 
luyện gây ra thay đổi lớn trong các giá trị ước lượng 
tham số
Vd, P(le|the) thay đổi từ 0.610 xuống 0.497
TÍnh hiệu quả. Bỏ các câu > 30 từ, vì làm không gian 
tìm kiếm tăng theo cấp số mũ
Thiếu tri thức ngôn ngữ
Thiếu tri thức ngôn ngữ
Không lưu thông tin về các ngữ: ví dụ không 
gióng hàng được “to go” và “aller” 
Không có ràng buộc cục bộ:
38
Eg, is she a mathematician
Âm vị. Các từ tạo bởi các âm vị khác nhau được 
coi là các ký hiệu riêng biệt
Dữ liệu thưa. Các đánh giá cho các từ ít gặp 
không chính xác
Các hệ thống gióng hàng khác
Các tập ngữ liệu sử dụng giả thiết:
• Dữ liệu song song (dịch E ↔ F)
Gióng hàng câu
39
• Phát hiện câu
• Gióng hàng câu
Gióng hàng từ
• Tách từ
• Gióng hàng từ (với 1 số ràng buộc)
Phát hiện biên của câu
Sử dụng luật, danh sách liệt kê:
Dấu kết thúc câu:
• Dấu ngắt đoạn (nếu được đánh dấu)
• 1 số ký tự: ?, !, ; 
40
• Vấn đề: dấu chấm ‘.’
– Kết thúc câu (... left yesterday. He was heading to...)
– Dấu chấm thập phân : 3.6 (three-point-six)
– Dấu chấm hàng nghìn: 3.200 
– Viết tắt: cf., e.g., Calif., Mt., Mr.
– Vân vân: ...
– 1 số ngôn ngữ: 2nd ~ 2.
– Ký hiệu đầu: A. B. Smith
Phương pháp thống kê: vd Maximum Entropy
Gióng hàng câu
Vấn đề với phát hiện biên của câu:
E:
F:
41
Đầu ra mong đợi: Các phân mảnh với cùng số 
lượng mảnh liên tiếp nhau.
Gióng hàng:
E:
F:
Kết quả: 2-1, 1-1, 1-1, 2-2, 2-1, 0-1 
Các phương pháp gióng hàng
Nhiều phương pháp (xác suất hoặc không)
Dựa trên độ dài ký tự
Dựa trên độ dài từ
42
“cùng gốc” (sử dụng nghĩa từ)
• Sử dụng từ điển (F: prendre ~ E: make, take)
• Sử dụng khoảng cách từ (độ tương tự): tên, số, từ vay mượn, 
từ gốc Latin
Kết quả tốt nhất: 
Thống kê, dựa trên từ hoặc dựa trên ký tự
8Gióng hàng dựa trên độ dài
Định nghĩa bài toán như việc tính xác suất:
argmaxA P(A|E,F) = argmaxA P(A,E,F) (E,F cố định)
Đị h hĩ 1 “b d” “bead” (2:2)
43
n ng a ea :
E:
F:
Lấy xấp xỉ:
P(A,E,F) ≅ Πi=1..nP(Bi),
Trong đó Bi là 1 bead; P(Bi) không phụ thuộc vào phần còn 
lại của E,F. 
Nhiệm vụ gióng hàng
Định nghĩa:
Cho P(A,E,F) ≅ Πi=1..nP(Bi),
tìm cách chia (E,F) thành n bead Bi 1 n, sao cho
44
 = .. 
tối đa xác suất P(A,E,F) trên tập luyện.
Bi = p:qαi, với p:q ∈ {0:1,1:0,1:1,1:2,2:1,2:2}
mô tả phép gióng hàng
Pref(i,j) – xác suất của cách gióng hàng tốt nhất từ 
điểm đầu cho đến (i,j) 
Định nghĩa đệ qui
Khởi tạo: Pref(0,0) = 0.
Pref(i,j) = max (
Pref(i,j-1) P(0:1αk), Pref(i-1,j) P(1:0αk), Pref(i-1,j-1) P(1:1αk),
45
Pref(i-1,j-2) P(1:2αk), Pref(i-2,j-1) P(2:1αk), Pref(i-2,j-2) P(2:2αk) )
E:
F:
i
j
Pref(i-2,j-2) P(2:2αk)Pref(i-2,j-1) P(2:1αk)1 2 P(1:2αk)Pref(i- ,j-1) P(1:1αk)Pref(i-1,j
P(1:0αk)Pref(i,j-1)
0:1 k
Xác suất của 1 Bead
Định nghĩa P(p:qαk):
k đề cập đến “bead” kế tiếp, với các đoạn của câu p và q, 
độ dài lk,e và lk,f.
Sử d hâ bố h ẩ h á độ dài khá h
46
 ụng p n c u n c o c c c n au:
P(p:qαk) = P(δ(lk,e,lk,f,μ,σ2),p:q) ≅ P(δ(lk,e,lk,f,μ,σ2))P(p:q)
δ(lk,e,lk,f,μ,σ2) = (lk,f - μlk,e)/√lk,eσ2
Đánh giá P(p:q) từ tập dữ liệu nhỏ, hoặc đoán và đánh 
gía lại sau khi gióng hàng
Từ có thể được dùng như dấu hiệu tốt hơn để định 
nghĩa P(p:qak).
Gióng hàng từ
Nếu chỉ dựa trên độ dài, không thực hiện được:
từ có thể bị đảo trật tự, các phép dịch thường có 
độ dài khác nhau
47
Ý tưởng:
Đưa ra vài mô hình dịch đơn giản. 
Tìm các tham số bằng cách xét tất cả các cách 
gióng hàng.
Sau khi có tham số, tìm cách gióng hàng tốt nhất 
khi có các tham số này.
Thuật toán gióng hàng từ
Khởi tạo với tập ngữ liệu gióng hàng câu.
Cho (E,F) là 1 cặp câu (là 1 bead).
1. Khởi tạo ngẫu nhiên p(f|e), f∈F, e∈E.
48
2. Đếm trên tập ngữ liệu:
c(f,e) = Σ(E,F);e∈E,f∈F p(f|e)
với ∀ cặp gióng hàng (E,F), kiểm tra xem e có trong E và f 
có trong F không. Nếu đúng, bổ sung p(f|e).
3. Đánh giá lại:
p(f|e) = c(f,e) / c(e) [c(e) = Σf c(f,e)]
4. Lặp đến khi p(f|e) thay đổi ít.
9Cách gióng hàng tốt nhất
Với mỗi cặp (E,F), tìm
A = argmaxA P(A|F,E) = argmaxA P(F,A|E)/P(F) =
49
argmaxA P(F,A|E) = argmaxA (ε / (l+1)m Πj=1..m
p(fj|eaj)) = argmaxA Πj=1..mp(fj|eaj)
Sử sụng thuật toán lập trình động theo 
kiểuViterbi.
Tính lại p(f|e)
Dịch máy sử dụng cú pháp
50
Tại sao dùng cú pháp
Cần thông tin ngữ pháp
Cần các ràng buộc khi sắp lại câu
Khi chèn các từ chức năng vào câu, cần 
đặt ở vị trí chính xác
Khi dịch từ cần sử dụng từ có cùng từ 
loại với nó
51
Yamada and Knight (2001):
Lý do cần cú pháp
52
Mô hình dựa trên cú pháp
Mô hình dịch
Cây cú pháp
(tiếng Anh)
Câu
(tiếng Nhật)
Tiền xử lý câu tiếng Anh bằng bộ PTCP
Thực hiện các phép tính xác suất trên cây cú 
pháp
Sắp lại trật tự các nút
Chèn nút mới vào
Dịch các từ ở lá
53
Cây cú pháp (Anh) Æ câu (Nhật)
54
10
1. Sắp lại trật tự
Đặc trưng điều kiện = dãy các nhãn con
55
Bảng tham số: sắp lại
Trật tự gôc Sắp lại P(Sắp lại| Trật tự gốc)
56
2. Chèn
Đặc trưng điều kiện = nhãn cha & nhãn nút (vị trí) & none (là từ)
57
Bảng tham số: chèn
58
3. Dịch
59
Đặc trưng điều kiện = từ (tiếng Anh)
Bảng tham số: Dịch 
60
Ghi chú: Dịch thành NULL Æ xóa
11
Thử nghiệm
Dữ liệu luyện: 2000 cặp câu J-E
J: tách từ sử dụng Chasen 
E: PTCP sử dụng bộ PTCP Collins
Luyện trên 40000 câu từ Treebank, độ cx 
~90%
E: từ cây cú pháp, xác định trật tự từ 
và chuyển đổi (SVO SOV)
Luyện sử dụng EM: 20 vòng lặp
61
Kết quả
Điểm trung bình #câu
Y/K model 0.582 10
IBM model 5 0 431 0
Điểm trung bình được tính trên 3 người với 50 câu
ok(1.0), không chắc (0.5), sai (0.0)
chỉ tính độ chính xác 
 .
62
Kết quả: gióng hàng 1
63
Kết quả: gióng hàng 2
64
Một số hệ thống dịch máy trên 
Internet
 altavista digital com/
65
. . .
66
12
67
69 70