Luận văn Canh lề văn bản song ngữ và ứng dụng giải quyết những trường hợp đặc thù của ngôn ngữ anh - Việt

iện thực được. Trong việc loại bỏ phụ tố (affix removal), phần quan trọng nhất là loại bỏ hậu tố (suffix removal) bởi vì hầu hết những biến thể của một từ được sinh ra bằng cách thêm vào các hậu tố (suffix) thay vì các tiền tố (prefix). Có 3 hoặc 4 giải thuật loại bỏ hậu tố nổi tiếng. Trong đó giải thuật Porter được xem là nổi tiếng nhất bởi tính đơn giản và tính tao nhã (elegance) của nó. Porter’s Algorithm: Giải thuật Porter được thực hiện theo 5 giai đoạn và được thực hiện tuần tự từ giai đoạn 1 đến giai đoạn 5. Giải thuật Porter tuân thủ theo ngôn ngữ lập trình mã giả (pseudo programming language) và được định nghĩa như sau: Một biến phụ âm (consonant variable) được ký hiệu bằng ký tự C là các chữ cái khác với a, e, i, o, u và khác với ký tự y mà đứng trước nó là một phụ âm. Một biến nguyên âm (vowel variable) được ký hiệu bằng ký tự V là các chữ cái (letter) mà không phải là phụ âm. Một từ chung (generic letter) là nguyên âm (vowel) hoặc phụ âm (consonant) được ký hiệu bằng ký tự L. Ký hiệu ø được dùng để chỉ một chuỗi rỗng (empty string). Sự kết hợp của C, V và L được gọi là patterns. Ký hiệu * được dùng để chỉ không hoặc nhiều pattern. Ký hiệu + được dùng để chỉ một hoặc nhiều pattern. Giải thuật Porter được thực hiện tuần tự như sau: % Phase 1: Plurals and past participles. select rule with longest suffix { sses → ss; ies → i; ss → ss; s → ø; } select rule with longest suffix { if ( (C)*((V)+(C)+)+(V)*eed) then eed → ee; if (*V*ed or *V*ing) then { select rule with longest suffix { ed → ø; ing → ø; } select rule with longest suffix { at → ate; bl → ble; iz → ize; if ((* C1C2) and ( C1 = C2) and ( C1 ¢ {l,s,z})) then C1C2 → C1; if (( (C)*((V)+(C)+)C1V1C2) and ( C2 ¢ {w,x,y})) then C1V1C2 → C1V1C2e; } } } % Phase 2: if (*V*y) then y → i; if ( (C)*((V)+(C)+)+(V)*) then select rule with longest suffix { ational → ate; tional → tion; enci → ence; anci → ance; izer → ize; abli → able; alli → al; entli → ent; eli → e; ousli → ous; ization → ize; ation → ate; ator → ate; alism → al; iveness → ive; fulness → ful; ousness → ous; aliti → al; iviti → ive; biliti → ble; } % Phase 3: if ( (C)*((V)+(C)+)+(V)*) then select rule with longest suffix { icate → ic; ative → ø; alize → al; iciti → ic; ical → ic; ful → ø; ness → ø; } % Phase 4: if ( (C)*((V)+(C)+)((V)+(C)+)+(V)*) then select rule with longest suffix { al → ø; ance → ø; ence → ø; er → ø; ic → ø; able → ø; ible → ø; ant → ø; ement → ø; ment → ø; ent → ø; ou → ø; ism → ø; ate → ø; iti → ø; ous → ø; ive → ø; ize → ø; if (*s or *t) then ion → ø; } % Phase 5: select rule with longest suffix { if ( (C)*((V)+(C)+)((V)+(C)+)+(V)*) then e → ø; if (( (C)*((V)+(C)+)(V)*) and not (( *C1V1C2) and ( C2 ¢ {w,x,y}))) then e → nil; } if ( (C)*((V)+(C)+)((V)+(C)+)+V*ll) then ll → l; Giải thuật phân đoạn câu: Trong rất nhiều bài toán xử lý ngôn ngữ tự nhiên, việc phân đoạn câu là một trong những công việc bắt buộc phải thực hiện trước tiên. Trong canh lề văn bản cũng vậy. Rất nhiều phương pháp canh lề văn bản đòi hỏi văn bản phải được phân đoạn câu trước. Ví dụ như phương pháp canh lề văn bản theo chiều dài câu, phương pháp canh lề theo giải thuật SIRM và GSA. Để có thể hiểu rõ điều này, chúng ta cần định nghĩa câu là gì. Câu là một chuỗi các từ kết thúc bằng một trong các dấu: dấu chấm (.), dấu chấm thang (!), dấu chấm hỏi (?). Đó là định nghĩa đơn giản. Thật sự, giải thuật phân đoạn câu không đơn giản như thế. Theo thống kê, có khoảng 90% câu kết thúc bằng dấu chấm. Dấu chấm thang và dấu chấm hỏi là một ký hiệu kết thúc câu tương đối rõ ràng. Có những câu không có ký hiệu kết thúc câu, nhưng nó ở vị trí cuối đoạn văn (kết thúc bằng ký hiệu xuống dòng). Ngoài ra, không phải tất cả các dấu chấm đều là ký hiệu kết thúc câu. Dấu chấm có thể xuất hiện trong các trường hớp khác: Dấu chấm trong chữ viết tắt. Ví dụ: U.S. Dấu chấm trong các con số. Ví dụ: 12,000.00 Dấu chấm trong dấu ba chấm (…) Dấu chấm trong địa chỉ Website. Ví dụ: Dấu chấm trong địa chỉ email. Ví dụ: ngocsoncntt@yahoo.com Đôi khi, không thể phân biệt được dễ dàng dấu chấm đang ở vai trò nào. Nó có thể là trong chữ viết tắt, có thể là ký hiệu kết thúc câu, hay cũng có thể là trongchữ viết tắt, lại ở vị trí kết thúc một câu. Xét ví dụ sau: (1) She needs her car by 5 p.m. on Saturday evening. (2) At 5 p.m. I had to go to the bank. Như vậy, trong câu trường hợp (1) “p.m.” là một chữ viết tắt, vì sau nó là một chữ viết thường. Trong trường hợp (2) sau “p.m.” lại là chữ viết in hoa. Trong một ví dụ khác, việc xác định lại càng khó khăn hơn: (1) It was due Friday by 5 p.m. Saturday would be too late. (2) She has an appointment at 5 p.m. Saturday to get her car fixed . Hay trong ví dụ sau: (1) The Office of the U.S. Trade Representative includes two deputy USTRs, one based in Washington, D.C., and the other in Geneva, Switzerland. (2) I bought the apples, pears, lemons, ect. Did you eat them? Chữ “etc.” vừa là một chữ viết tắt, vừa ở vị trí kết thúc câu. Một số phương pháp phân đoạn câu: Phương pháp mạng Neural của tác giả Palmer và Hearst (1997) có độ chính xác đạt tới 98.5% (theo báo cáo của tác giả khi áp dụng cho corpus Wall Street Journal – WSJ). Phương pháp dùng các luật kết hợp với danh sách từ viết tắt của tác giả Grefenstette và Tapanainen (1994). Phương pháp maximum-entropy của tác giả Ratnaparkhi (1997) đạt độ chính xác 98% khi áp dụng cho corpus WSJ. Phương pháp áp dụng luật và yếu tố ngữ pháp của tác giả Nilani Aluthgedara. Có 3 luật cơ bản: Mỗi các câu đều có một động từ. Tất cả các câu bắt đầu bằng một từ viết hoa. Các danh từ riêng bắt đầu bằng chữ cái viết hoa. Phương pháp dùng mô hình trực tiếp: Phương pháp này dựa vào danh sách các từ viết tắt để giải quyết tình trạng nhập nhằng. Giải thuật canh lề văn bản theo chiều dài câu [16]: Giải thuật lợi dụng đặc điểm những câu dài trong một ngôn ngữ thường có xu hướng được dịch thành những câu dài trong một ngôn ngữ khác và một câu ngắn cũng được dịch thành những câu ngắn trong một ngôn ngữ khác. Thống kê xác suất đã tiến hành kiểm chứng độ dài những cặp câu tương ứng với nhau, dựa trên tỷ lệ về độ dài của những câu này. Thống kê này được dùng trong khung lập trình động nhằm tìm ra mức độ giống nhau nhất về độ dài giữa những câu tương ứng. Đồ thị tương quan độ dài giữa tiếng Anh và tiếng Đức chứng minh cho điều đó. Hình 41 Đồ thị tương quan chiều dài giữa tiếng Anh và tiếng Đức Khung lập trình động (A Dynamic Programming Framework): Lập trình động thường được sử dụng cho việc canh lề hai chuỗi ký hiệu ở những định dạng khác nhau, ví dụ như cách sắp xếp các gene ở các loài khác nhau, sự so trùng các chuỗi tín hiệu âm thanh khác nhau của những người nói khác nhau, quang phổ của các chất khác nhau, và thành phần địa chất của các nơi khác nhau (Sankoff và Kruskal, 1983). Chúng ta mong rằng những kỹ thuật này có thể hữu dụng, khi thứ tự sắp xếp các câu không khác nhau nhiều trong những ngôn ngữ khác nhau. Kỹ thuật sắp xếp chi tiết có thể khác nhau trong các ứng dụng, nhưng tất cả đều sử dụng tính toán khoảng cách để so sánh hai thành trong hai chuỗi, và một thuật toán lập trình động để tối thiểu khoảng cách giữa các thành phần tương ứng trong hai chuỗi. Chúng ta thấy rằng bài toán canh lề câu rất phù hợp để áp dụng, mặc dù cần có một số điều chỉnh trong công thức tính khoảng cách. Kruskal và Liberman (1983) mô tả tính khoảng cách thuộc vào hai loại: “trace” và “time-warp”. Sự khác biệt quan trọng giữa chúng khi một thành phần trong chuỗi này được tìm thấy tương ứng với nhiều thành phần trong một chuỗi khác. Những ứng dụng thuộc loại “trace” (trace application) ví dụ như trong tìm kiếm mã gene, một thành phần trong chuỗi này chỉ được nối tương ứng với duy nhất một trong các thành phần được tìm thấy, tất cả những thành phần còn lại sẽ bỏ qua. Ngược lại, trong những ứng dụng thuộc loại “time-warp” (time warp application), ví dụ như nhận dạng các mẫu tiếng nói, một mẫu sẽ được so trùng với tất cả các thành phần tồn tại trong chuỗi. Thật thú vị là ứng dụng của chúng ta không nằm trong bất cứ loại nào kể trên vì chúng ta tính khoảng cách để so sánh một thành phần với một tổ hợp các thành phần khác. Rất thuận tiện để tính khoảng cách dựa trên một mô hình thống kê xác suất, để từ đó các câu được canh lề một cách thống nhất. Gọi match là một phép canh lề. Khoảng cách được tính bằng –log(Prob(match|d)), với d phụ thuộc vào l1 và l2, lần lượt là độ dài của hai đoạn trong văn bản canh lề. Log được sử dụng ở đây để khi cộng những khoảng cách sẽ tạo ra những kết quả kỳ vọng. Tính khoảng cách dựa trên giả thuyết rằng mỗi từ trong ngôn ngữ L1, được đối sánh với một số lượng từ bất kỳ trong một ngôn ngữ L2. Giả thuyết rằng những biến ngẫu nhiên này là độc lập và phân bố đều với một phân phối chuẩn (normal distribution). Mô hình này có giá trị trung bình c, phương sai s2. Cụ thể ở đây giá trị trung bình c là tỷ lệ trung bình một từ tiếng Anh được dịch thành c từ tiếng Việt. Chúng ta định nghĩa d bằng . Do đó nó có một phân phối chuẩn với trung bình là 0 và phương sai bằng 1. Điều này có nghĩa là phép canh lề chính xác nhất phải có d gần bằng 0. Mục đích của việc dùng –log trong tính khoảng cách của phép canh lề bằng –log(Prob(match | d)) là: nếu xác suất của phép canh lề càng lớn thì khoảng cách của phép canh lề càng nhỏ. Mục đích của ta là đi tìm các phép canh lề sau cho tổng các khoảng cách của chúng nhỏ nhất hay tích xác suất của chúng đạt giá trị lớn nhất. Bài toán này tương tự như việc tìm tổng chi phí nhỏ nhất trong lập trình động. Theo công thức Bayes ta có: Prob(match | d) = Prob(d | match).Prob(match)/Prob(d). Tuy nhiên với hai câu cho trước thì chiều dài của chúng là cố định nên Prob(d) là hằng số nên ta có thể bỏ qua. Vì vậy ta chỉ cần phải tính Prob(d | match) và Prob(match), trong đó Prob(d | match) được tính gần đúng theo công thức sau: Prob(d | match) =2(1-Prob(|d|)) Với Prob(|d|) là xác suất biến ngẫu nhiên z, có phân bố chuẩn (trung bình = 0 và độ lệch=1) Như vậy các tham số mà ta cần tính là c và s2. Giá trị trung bình c được tính bằng cách thông kê số từ trong các văn bản song ngữ. Bình phương độ lệch s2 được tính bằng cách thống kê loại canh lề và tần suất xuất hiện của nó. Các tính toán này sẽ được trình bày trong phần hiện thực ở chương sau. Các loại phép canh lề bao gồm: phép canh lề một-một (1-1), một-không (1-0), không-một (0-1), hai-một (2-1), một-hai (1-2) và hai-hai (2-2). Các phép canh lề khác, như phép canh lề ba-một (3-1) và một-ba (1-3) cũng có xuất hiện nhưng tần suất rất thấp. Do đó, hầu như tất cả các nghiên cứu đều bỏ qua phép canh lề này. Hàm tính khoảng cách d(x1,x2,y1,y2), được định nghĩa một cách tổng quát để thêm, xóa và thay thế… Hàm bao gồm những biến số: x1, x2, y3, y4. d(x1, y1 ; 0, 0) là chi phí thay thế x1 bằng y1. d(x1, 0; 0, 0) là chi phí của xóa x1. d(0, y1; 0, 0) là chi phí thêm y1. d(x1, y1; x2, 0) là chi phí thu giảm x1 và x2 bằng y1. d(x1, y1; 0, y2) là chi phí khai triển x1 thành y1 và y2 d(x1, y1; x2, y2) là chi phí kết hợp x1 và x2 sau đó đối sánh với y1 và y2. Thuật toán lập trình động (A Dynamic Programming Algorithm): Thuật toán này là kết quả của phương trình đệ quy. Cho s1, i = 1….I. là câu của ngôn ngữ L1, tj, j= 1…J , là những bản dịch ở ngôn ngữ L2. Với d là hàm khoảng cách được mô tả ở trên. Với D (i;j) là khoảng cách nhỏ nhất giữa s1…si và bản dịch t1 … tj, trong một phép canh lề tốt nhất. D(i;j) được tính bằng cách chọn giá trị nhỏ nhất của 6 trường hợp (thay thế, xóa, thêm, thu giảm, mở rộng, kết hợp). Nghĩa là, D(i;j) được định nghĩa bằng đệ quy với điều kiện ban đầu D(i;j) = 0. D(i,j-1) + d(0,tj;0,0) D(i-1,j) + d(si,0;0,0) D(i-1,j-1) + d(si,tj;0,0) D(i-1,j-2) + d(si,tj;0,tj-1) D(i-2,j-1) + d(si,tj;si-1,0) D(i-2,j-2) + d(si,tj;si-1,tj-1) D(i,j) = Phương pháp canh lề sử dụng dãy giới hạn (Confidence Bands Algorithm - CBA) [8]: Tác giả xây dựng một phương pháp độc lập ngôn ngữ. Có thể tóm tắt quá trình canh lề qua các bước như sau: Tạo điểm dùng Homograph Lọc nhiễu dùng biểu đồ khoảng cách (Histofram of Distances) Chọn điểm dùng CBA Trong giai đoạn tạo điểm, tác giả đối sánh hai từ có cách viết tương tự nhau (homograph), và có tần suất xuất hiện giống nhau (equal frequencies) trong hai văn bản thuộc hai ngôn ngữ. Để tránh những cặp từ giống nhau nhưng không phải là điểm tương ứng thực sự (Ví dụ, từ “a” trong tiếng Bồ Đào Nha và tiếng Anh), phải giới hạn bằng cách dùng tần suất xuất hiện. Có nghĩa là chỉ chọn những cặp từ mà tần suất xuất hiện trong hai ngôn ngữ là như nhau. Từ những điểm nhận dạng được trong quá trình tạo điểm, ta xây dựng nên một tập các điểm tương ứng dự tuyển. Dựa vào đó, ta có thể vẽ ra được một đường thẳng dựa trên hồi qui tuyến tính. Hình 42 Đường thẳng hồi qui tuyến tính Nhìn vào đồ thị ta thấy những điểm rút ra được từ bước tạo điểm, mặc dù đã sử dụng tần suất xuất hiện giống nhau vẫn còn có những điểm nhiễu. Đầu tiên, giải thuật tính toán điểm mong đợi của các điểm và khoảng cách của nó so với điểm mong đợi. Ví dụ: Phương trình của đường thẳng hồi qui tuyến tính: y=a.x+b. Một điểm p(xi,yi) à điểm mong đợi là p’(xi,y’i) với y’i= a.xi+b. Khoảng cách d=y’i-yi. Hình 43 Biểu đồ khoảng cách Để xây dựng biểu đồ khoảng cách, tác giả sử dụng luật Sturges (Sturges rule). Số lượng cột (classes, bars, bins) = 1+ log2n, với n=tổng số điểm. Chiều rộng cột (size of the classes) = dmax – dmin Với dmax = khoảng cách lớn nhất; dmin = khoảng cách nhỏ nhất Để chọn được những điểm canh lề đáng tin cậy, tác giả sử dụng dãy giới hạn của đường thẳng hồi qui tuyến tính (Confidence Bands of Linear Regression Lines). Hình 44 Dãy giới hạn (CB) Dựa vào đường thẳng hồi qui sau giai đoạn lọc nhiễu ở trên, chúng ta tính khoảng tin cậy: [(ax+b-error(x), (ax+b+error(x)]. Những điểm nằm ngoài khoảng tin cậy bị loại ra khỏi tập hợp. Theo Thomas Wonnacott & Ronald Wonnacott, 1990: với t0.005: giá trị t-statistics với khoảng tin cậy 99.9%, hoặc dùng giá trị z-statistics cho những mẫu lớn (large samples of points) (>120) khi đó t0.005=z0.005=3.27 n: tổng số điểm s: độ lệch chuẩn so với điểm mong đợi Phương pháp canh lề sử dụng “chuỗi được sắp xếp dài nhất” (Longest Sorted Sequence Algorithm - LSSA) [1]: Trên cơ sở cải tiến phương pháp canh lề dùng Confidence Bands của các tác giả Antonio Ribeiro, Gabriel Lopes và Joao Mexia, nhóm của Tiago Ildefono and Gabtiel Pereira Lopes nhận thấy nhiều vấn đề chưa giải quyết được của phương pháp dùng Confidence Bands. Các bước tạo điểm và lọc nhiễu dùng biểu đồ khoảng cách. Sự khác biệt duy nhất là sự thay thế phương pháp Confidence Bands bằng giải thuật Longest Sorted Sequence (LSSA). Ở mục sau sẽ so sánh và trình bày lý do tại sao lại thay thế Confidence Bands bằng LSSA. Ưu điểm nổi bật là nó nhanh hơn và gia tăng số lượng các điểm được canh lề. Giải thuật dựa trên ý tưởng chọn phép canh lề có chuỗi các từ được canh lề là dài nhất. Cụ thể như sau: Định nghĩa 3 vector: L2_array_pos: chứa thứ tự các điểm tương ứng trong ngôn ngữ L2 sắp xếp theo thứ tự tăng dần trong ngôn ngữ L1. L2_array_weights: lưu trọng số mỗi phần tử trong L2_array_pos. L2_array_lss: giống như L2_array_pos, nhưng chỉ chứa các điểm tin cậy sau quá trình lọc. Bước 1: Gán tất cả các trọng số bằng 1. (điều này tương ứng với việc có một điểm canh lề kết thúc phân đoạn). Bước 2: Với mỗi phần tử trong mảng, tính trọng số tương ứng. Việc này cần phải duyệt qua tất cả các phần tử trước nó và so sánh giá trị và trọng số của mỗi phần tử. Nếu phần tử hiện tại có giá trị lớn hơn một trong các phần tử k trước, và có trọng số nhỏ hơn hoặc bằng, cập nhật trọng số của phần tử hiện tại bằng trọng số của phần tử k cộng thêm 1. Sau khi trọng số được cập nhật, ghi nhận lại phần tử nào đang có trọng số lớn nhất. Bước 3: Khi tất cả các trọng số được tính toán, duyệt từ phải qua trái các phần tử (L2_array_weights, L2_array_pos), bắt đầu từ phần tử có trọng số lớn nhất, chọn những phần tử có trọng số bằng trọng số của phần tử hiện tại trừ 1. Xét ví dụ sau: Mảng L2_array_pos đã được sắp xếp theo thứ tự tăng dần của các phần tử trong L1.  0 1 2 3 4 5 6 7 8 L2_array_pos 1 10 30 200 100 41 45 50 54 L2_array_weights 1 2 3 4 4 4 5 6 7 L2_array_lss 1 10 30 41 45 50 54 Bảng 41. Giá trị các vector trong LSSA Ta thấy rằng: hai phần tử thứ 3 và thứ 4 bị loại ra khỏi danh sách các điểm tương ứng được canh lề. So sánh phương pháp LSSA với CBA: Rõ ràng qui trình canh lề của LSSA và CBA hoàn toàn giống nhau trừ lần lọc cuối cùng để quyết định giữ lại các điểm được canh lề. Sau lần lọc nhiễu dùng biểu đồ khoảng cách và loại ra những điểm nằm ngoài, một bộ lọc khác tốt hơn (CBA hoặc LSSA) cần được áp dụng để giữ lại những điểm tin cậy. Đây là 5 vấn đề mà CBA gặp phải mà LSSA có thể khắc phục. Vấn đề 1: Tính nghiêm khắc (Restrictiveness) CBA rất nghiêm khắc. Nó không chấp nhận một lượng lớn các điểm dự tuyển canh lề tốt (good alignment candidate point). Một giải thuật canh lề tốt nhất nên thỏa mãn các điều kiện sau: Các đoạn song song (parallel segments) phải là bản dịch của nhau à Điều này có liên quan với độ chính xác (precision). Các đoạn càng nhỏ càng tốt à Điều này có liên quan với độ hoàn toàn (recall). Một ví dụ canh lề do tác giả Tiago Ildefonso và Gabriel Pereira Lopes hiện thực trên cả hai phương pháp: Hình 45. Kết quả thu được khi sử dụng CBA Hình 46. Kết quả thu được khi sử dụng LSSA Chúng ta nhận thấy rằng CBA bỏ đi 6 điểm tốt (good point) khi canh lề. Trong trường hợp này, độ chính xác khi sử dụng CBA là 100%. Đối với LSSA, độ chính xác là 92,8%, vì có lỗi canh lề trong đoạn 552, nhưng độ hoàn toàn (recall) cao gấp 6 lần. Vấn đề 2: Cạm bẫy khi canh lề chéo (Disordering Pitfall). Ví dụ dưới đây minh họa cách 2 giải thuật xử lý sau khi áp dụng lọc nhiễu bằng biểu đồ khoảng cách. Confidence Bands xác định độ lệch cho phép lớn nhất (maximum admitted deviation) từ giá trị mong đợi được tính theo đường thẳng hồi qui tuyến tính. Giá trị này thể hiện trong cột “distance_admitted_CB”, khoảng cách thực được thể hiện trong cột “distance”: Hình 47. Tính khoảng cách trong CBA Giải thuật CBA không loại bỏ bất cứ điểm canh lề dự tuyển nào. Xem 2 cột cuối của “table_7cols”, chúng ta thấy rằng tất cả chúng tuân theo “distance ≤ distance_admitted_CB”. Điểm yếu của hầu hết các giải thuật là không cho phép canh lề chéo nên khi duyệt lại danh sách các điểm canh lề thật sự theo thứ tự, kết quả canh lề như sau: Hình 48. Kết quả canh lề sử dụng CBA Với LSSA, giải thuật sẽ quyết định chọn chuỗi canh lề dài nhất, Kết quả cho thấy cả hai thông số, độ chính xác (precision) và độ hoàn toàn (recall), CBA đều có kết quả thấp hơn. Hình 49. Kết quả canh lề sử dụng CBA Vấn đề 3: Mô hình CB không phù hợp cho canh lề văn bản song ngữ Hai vấn đề trên làm rõ được điều này. CBA là một giải thuật hay, nó áp dụng thành công trong các ứng dụng khác, tuy nhiên nó có vẻ không phù hợp khi áp dụng cho canh lề văn bản song ngữ. CB có tính chất là rộng ở hai đầu và hẹp hơn ở đoạn giữa của đường thẳng hồi qui. Đó là lý do tại sao ở vấn đề 1, nó bỏ qua những điểm canh lề ở đoạn giữa, và nó lại chấp nhận điểm không phù hợp ở vị trí đầu tiên trong vấn đề 2. Vấn đề 4: Ba điểm dự tuyển hoặc không có điểm nào Xét ví dụ canh lề song ngữ Bồ Đào Nha và Pháp. Hình 410. Kết quả canh lề dùng CBA Hình 411. Kết quả canh lề dùng LSSA Giải thuật LSSA chia đoạn 205 thành 11 đoạn, trong khi CBA lại không tìm thấy điểm tương ứng. Có thể giải thích: do trong đoạn 205, chỉ có 2 điểm dự tuyển được chấp nhận bởi biểu đồ khoảng cách (Histogram Filter), và tiếp tục qua bước lọc dùng CBA. Vì không thể áp dụng CBA khi có ít hơn 3 điểm dự tuyển, chúng ta không chia nhỏ văn bản được nữa. Theo Ribeiro et al (2000), thông số s (độ lệch chuẩn) có mẫu số bằng “n-2”, trong đó n là số lượng điểm dự tuyển. Vì thế, n phải lớn hơn hoặc bằng 3. LSSA không có giới hạn nào về số lượng điểm tối thiểu. Vấn đề này thật sự quan trọng trong bước đệ qui của giải thuật. Không thực hiện đệ qui, chúng ta không thể đạt được độ hoàn toàn như mong đợi. Hơn nữa, thực nghiệm thấy rằng 25% các cơ hội xuất hiện khi đệ qui, nhưng chỉ có một hoặc hai điểm được chấp nhận bởi CBA. Vấn đề 5: Giá trị t_students (trên 120 điểm) Ribeiro et al cũng cho rằng, đối với công thức Confidence Bands, họ sử dụng một giá trị t_students là 3.27 đối với số điểm lớn (large samples of points)(trên 120). Nhưng giá trị này nên được điều chỉnh động tùy vào số lượng điểm mà chúng ta có đối với mỗi tình huống được áp dụng giải thuật. Hiển nhiên là giải thuật có đệ qui, và phần lớn các lần chạy giải thuật CB sẽ có ít hơn 120 điểm dự tuyển. Ngay cả không thực hiện đệ quy, một số văn bản nhỏ hơn cũng sẽ không có 120 điểm dự tuyển khi khảo sát toàn bộ văn bản. Những khó khăn gặp phải khi áp dụng SIRM (Smooth Injective Map Recognizer) và GSA [10] Như đã giới thiệu trong phần 2 (các công trình nghiên cứu liên quan), SIMR là một giải thuật tham lam, phụ thuộc vào sự tương quan chiều dài của các văn bản thành phần trong văn bản song ngữ. Nó tìm ra một bản đồ ánh xạ dựa trên những điểm giống nhau trên mặt phẳng xác suất của văn bản song ngữ. Có thể nhắc lại các bước trong quá trình canh lề: Giải thuật SIMR gồm các giai đoạn: Tạo điểm. Nhận dạng chuỗi. Lọc nhiễu. Chọn điểm. Thu giảm không gian tìm kiếm. SIMR không có ý tưởng đối sánh những câu trong văn bản song ngữ, nó chỉ xuất ra một tập hợp các điểm mà ở đó có sự tương ứng về nghĩa trong văn bản song ngữ. Để tạo ra sự tương ứng lớn hơn như sự tương ứng về câu, về đoạn thì cần sự hỗ trợ của thuật toán GSA. Trong giai đoạn tạo điểm, bắt đầu từ một hình chữ nhật nhỏ cho trước có đường chéo song song với đường chéo chính, SIMR sẽ tạo ra tất cả các điểm thoả mãn vị từ so trùng (matching predicate). Trong giai đoạn nhận dạng chuỗi, SIMR sẽ gọi thuật toán nhận dạng để nhận ra các chuỗi thích hợp từ các điểm được tạo ra. Nếu không tìm thấy một chuỗi thích hợp nào cả, thì hình chữ nhật ở trên sẽ được mở rộng sao cho đường chéo của nó vẫn song song với đường chéo chính, sau đó quá trình tạo điểm và nhận dạng chuỗi lại được lặp lại. Hình chữ nhật trên sẽ được tiếp tục mở rộng cho đến khi ít nhất một chuỗi được tìm thấy. Trong trường hợp có nhiều chuỗi được tìm thấy thì SIMR sẽ lựa chọn chuỗi mà có các điểm tương đối tập trung gần đường thẳng hồi quy của chuỗi. Khi SIMR tìm thấy một chuỗi thì nó sẽ chọn một hình chữ nhật nhỏ khác cũng có đường chéo song song với đường chéo chính để tìm chuỗi tiếp theo. Hình chữ nhật đầu tiên mà SIMR chọn có một đỉnh trùng với điểm gốc, trong quá trình tìm kiếm tiếp theo thì hình chữ nhật kế tiếp sẽ có đỉnh nằm trên góc trên bên phải của chuỗi vừa tìm thấy (hình 4-2). Hình 412. Quá trình tạo điểm và mở rộng hình chữ nhật tìm kiếm Phần tiếp theo sẽ trình bày sự không phù hợp của SIRM khi áp dụng vào các trường hợp canh lề chéo mà chúng ta đang quan tâm. Vấn đề 1: Một đoạn lớn các điểm không đều (Large Non-monotonic Segments) Đối với những đoạn nhỏ không đều thì SIRM có thể phát hiện được. Tuy nhiên cách mở rộng hình chữ nhật tìm kiếm như trên có thể bỏ sót những đoạn không đều lớn, mà nguyên nhân là do sự dịch chéo. Hình 413. Phát hiện những đoạn canh lề sót trong giải thuật SIRM. Đoạn i và đoạn j bị đổi chỗ cho nhau trong quá trình dịch thuật. Thành phần theo trục ngang của đoạn i tương ứng với khoảng trống theo trục ngang của bản đồ, thành phần theo trục đứng của đoạn j tương ứng với khoảng trống theo trục đứng trong bản đồ ánh xạ. Đề xuất hướng giải quyết của tác giả ở đây là tìm kiếm lại một lần nữa ở những đoạn lớn mà nó không tìm thấy điểm tương ứng. Sau khi nhận dạng ra được chuỗi những điểm mới, chúng ta phải tiến hành cập nhật bảng đồ ánh xạ và thực hiện một số thao tác khác. Vấn đề 2: Sự biến đổi độ nghiêng cục bộ Khái niệm góc lệch lớn nhất (maximum angle deviation threshold) xuất hiện nhằm loại bỏ những chuỗi không thật. Giá trị này phải nhỏ. Tuy nhiên, như các quyết định cảm tính (heuristic) khác, nó có thể từ chối một số các điểm canh lề tốt. Hình 414. Sự biến đổi độ nghiêng cục bộ trong giải thuật SIRM. Chuỗi X là một chuỗi hợp lệ, mặc dù góc nghiêng của nó lớn hơn góc nghiêng cực đại cho phép. Những chuỗi có giá trị mà bị từ chối vì giá trị thông số này đôi khi lại được chấp nhận thành hai chuỗi tách rời. Nếu chuỗi C, và D được chấp nhận một cách hợp lệ thì góc nghiêng của bản đồ ánh xạ giữa điểm cuối của chuỗi C và điểm đầu của chuỗi D, thì gần hơn là góc nghiêng của đường chéo chính. Chuỗi X nên được chấp nhận. Nó cũng sẽ được phát hiện trong quá trình tìm kiếm lần thứ 2. Một trường hợp khác xảy ra biến đổi độ nghiêng cục bộ là đoạn văn bản “non-linguistic” như khoảng trắng hay bảng số liệu. Thông thường, những đoạn văn bản như vậy có nội dung hoàn toàn giống nhau trong dịch thuật, nên trong không gian văn bản, độ dốc bằng 1. Nếu như đoạn văn bản loại này đủ lớn nó sẽ kéo lệch độ nghiêng của đường chéo chính. Điều này sẽ đánh lừa SIRM trong quá trình tìm kiếm trên toàn b