Bài giảng Xử lý ngôn ngữ tự nhiên - Chương 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