Luận văn Thạc sĩ Khoa học máy tính: Sử dụng mô hình ngôn ngữ Bloom Filter trong cải tiến dịch máy thống kê

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CNTT & TT

TRẦN TIẾN THÀNH

THÁI NGUYÊN 2015

SỬ DỤNG MÔ HÌNH NGÔN NGỮ BLOOM FILTER TRONG CẢI TIẾN DỊCH MÁY THỐNG KÊ

LỜI CAM ĐOAN

Em - Trần Tiến Thành, học viên lớp Cao học K12E Trường Đại học

Công nghệ thông tin và Truyền thông Thái Nguyên - cam kết Luận văn thạc

sỹ khoa học máy tính: “Sử dụng mô hình ngôn ngữ Bloom Filter trong cải

tiến dịch máy thống kê” là công trình nghiên cứu của bản thân em dưới sự

hướng dẫn của thầy giáo TS. Nguyễn Văn Vinh, Bộ môn Khoa học máy tính,

Khoa Công nghệ thông tin – Trường Đại học Công nghệ - Đại học Quốc gia

Hà Nội.

Các kết quả trong luận văn tốt nghiệp là trung thực, không sao chép

toàn văn của bất kỳ công trình nào khác.

Thái Nguyên, ngày 05 tháng 10 năm 2015

TÁC GIẢ

Trần Tiến Thành

LỜI CẢM ƠN

Em xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo, TS. Nguyễn Văn

Vinh, Bộ môn Khoa học máy tinh, Khoa Công nghệ thông tin - Trường Đại

học Công nghệ - Đại học Quốc gia Hà Nội đã khuyến khích và tận tình hướng

dẫn em trong suốt quá trình thực hiện luận văn. Em cũng xin cảm ơn anh Trần

Hồng Việt, nghiên cứu sinh Trường Đại học Công nghệ, giảng viên Trường

Đại học Kinh tế kĩ thuật công nghiệp đã hết lòng giúp đỡ em trong quá trình

thực hiện đề tài. Nhờ sự quan tâm chỉ bảo và những ý kiến đóng góp quý báu

của thầy và của anh em mới có thể hoàn thành luận văn này.

Em xin chân thành cảm ơn tập thể các thầy, cô giáo Trường Đại học

Công nghệ thông tin và Truyền thông Thái Nguyên đã tận tình giảng dạy

truyền đạt cho em những kiến thức, kinh nghiệm quý báu trong suốt những

năm học vừa qua.

Em cũng xin cảm ơn Sở Giáo dục và Đào tạo Phú Thọ, Trường THPT

Minh Đài đã tạo điều kiện về kinh phí và thời gian để em có thể học tập và

hoàn thành luận văn.

Cuối cùng em xin chân thành cảm ơn gia đình, người thân đã hết lòng

giúp đỡ, hỗ trợ về vật chất lẫn tinh thần giúp em yên tâm học tập và nghiên

cứu trong suốt quá trình học tập và thực hiện luận văn.

Trong khoảng thời gian có hạn, cũng như kiến thức còn nhiều hạn chế

luận văn không tránh khỏi những sai sót về nội dung cũng như hình thức.

Kính mong nhận được sự góp ý của quý thầy cô, bạn bè và đồng nghiệp.

Thái Nguyên, ngày 05 tháng 10 năm 2015

TÁC GIẢ

Trần Tiến Thành

DANH SÁCH CÁC TỪ VIẾT TẮT

Viết tắt Đầy đủ

BF Bloom Filter

BF-LM Mô hình ngôn ngữ dựa trên Bloom Filter

LF-BF-LM Mô hình ngôn ngữ Log-Frequency Bloom Filter

LM Mô hình ngôn ngữ

MKN Phương pháp làm mịn Kneser-Ney cải tiến

MLE Ước lượng cực đại hóa khả năng

MSE Lỗi trung bình bình phương

MT Dịch máy

NLP Xử lý ngôn ngữ tự nhiên

PDS Cấu trúc dữ liệu xác suất

RDS Cấu trúc dữ liệu ngẫu nhiên

SMT Dịch máy bằng phương pháp thống kê

DANH MỤC CÁC HÌNH VẼ

Hình Tên hình Trang

Hình 1 Kiến trúc của một hệ thống SMT 14

Hình 2 Minh họa dịch máy thống kê dựa vào cụm 15

Hình 3 35 Ví dụ về hàm băm. Các xâu ký tự được chuyển thành chữ ký đại diện.

Hình 4 36

Cặp khóa ki và giá trị ai của tập S được ánh xạ thông qua hàm băm vào bảng băm. Xuất hiện xung đột giữa 2 phần tử k1 và k3.

Hình 5 Huấn luyện Bloom Filter 37

Hình 6 Truy vấn Bloom Filter 38

Hình 7 Lỗi một phía trong Bloom Filter 39

MỤC LỤC

MỞ ĐẦU .......................................................................................................... 9

1. Đặt vấn đề .................................................................................................... 9

2. Đối tượng và phạm vi nghiên cứu ............................................................ 10

3. Nhiệm vụ nghiên cứu ................................................................................ 10

4. Những nội dung nghiên cứu chính .......................................................... 10

NỘI DUNG ..................................................................................................... 11

CHƯƠNG I .................................................................................................... 11

TỔNG QUAN VỀ DỊCH MÁY THỐNG KÊ DỰA VÀO CỤM TỪ ............. 11

VÀ MÔ HÌNH NGÔN NGỮ ........................................................................... 11

1.1 Dịch máy thống kê dựa trên cụm từ ...................................................... 11

1.1.1 Dịch máy và dịch máy thống kê ............................................................. 11

1.1.2 Dịch máy thống kê dựa trên cụm ......................................................... 15

1.2.1 N-gram ................................................................................................... 17

1.2.2 Mô hình ngôn ngữ ................................................................................ 19

1.2.3 Huấn luyện mô hình ngôn ngữ ............................................................ 21

1.2.3.1 Ước lượng cực đại hóa khả năng (Maximium Likelihood Estimation -

MLE) ................................................................................................................ 21

1.2.3.2 Các phương pháp làm mịn .................................................................. 22

1.2.3.2.1 Kneser-Ney ...................................................................... 24 1.2.3.2.2 Kneser-Ney cải tiến (Modified Kneser-Ney - MKN) ...... 25 1.2.3.2.3 Stupid Backoff ................................................................. 26 1.3 Đánh giá mô hình ngôn ngữ ................................................................... 27

1.3.1 Entropy – Độ đo thông tin .................................................................... 27

1.3.2 Độ hỗn loạn thông tin (Perplexity) ...................................................... 29

1.3.3 Tỉ lệ lỗi (Error rate) ............................................................................... 30

1.4 Đánh giá chất lượng dịch tự động dựa trên điểm BLEU .................... 31

CHƯƠNG 2 .................................................................................................... 32

MÔ HÌNH NGÔN NGỮ BLOOM FILTER .................................................... 32

2.1 Các cấu trúc dữ liệu xác suất (PDS) ...................................................... 33

2.2 Hàm băm (Hash function) ...................................................................... 35

2.3 Bloom Filter cơ bản ................................................................................. 37

2.4 Mô hình ngôn ngữ Bloom Filter ............................................................ 43

2.4.1 Bloom Filter tần số log (Log-frequency Bloom Filter) .......................... 43

2.4.2 Bộ lọc dựa vào chuỗi con (sub-sequence filtering) ............................... 45

CHƯƠNG 3 .................................................................................................... 47

ỨNG DỤNG BLOOM FILTER CHO HỆ DỊCH MÁY THỐNG KÊ DỰA

VÀO CỤM TỪ ................................................................................................ 47

3.1 Hệ dịch máy thống kê mã nguồn mở Moses ......................................... 47

3.2 Tích hợp Mô hình ngôn ngữ Bloom Filter vào hệ thống Moses ......... 48

3.2.1 Xây dựng LM với RandLM và SRILM ................................................ 48

3.2.1.1 Ngữ liệu ............................................................................... 49 3.2.1.2 Thuật toán làm mịn ............................................................. 53 3.2.1.3. Xây dựng LM với SRILM và RandLM .............................. 53 3.3 Thử nghiệm và đánh giá ......................................................................... 65

KẾT LUẬN .................................................................................................... 78

TÀI LIỆU THAM KHẢO ............................................................................ 79

MỞ ĐẦU

1. Đặt vấn đề

Mô hình ngôn ngữ (Language Model - LM) là một phần không thể

thiếu trong lĩnh vực xử lý ngôn ngữ tự nhiên. Mô hình ngôn ngữ được sử

dụng ở các lĩnh vực trong xử lý ngôn ngữ tự nhiên như: nhận dạng tiếng nói,

kiểm lỗi chính tả, phân đoạn từ hay dịch máy thống kê… Để ứng dụng tốt mô

hình ngôn ngữ phải lớn, cũng chính vì vậy mà việc tìm kiếm không gian lưu

trữ là vô cùng quan trọng trong mô hình ngôn ngữ. Chính vì thế, luận văn này

tôi lựa chọn và thực hiện đề tài: “Sử dụng mô hình ngôn ngữ Bloom Filter

trong cải tiến dịch máy thống kê”.

Trong luận văn này, chúng tôi nghiên cứu và tìm hiểu mô hình ngôn

ngữ xây dựng dựa trên cấu trúc dữ liệu Bloom Filter. Không lưu trữ toàn bộ

tập n-gram giống như các mô hình truyền thống, loại mô hình ngôn ngữ

này sử dụng một quy trình mã hóa đặc biệt, cho phép chia sẻ một cách hiệu

quả các bit khi lưu trữ thông tin thống kê n-gram, nhờ đó tiết kiệm đáng kể bộ

nhớ. Sau khi tìm hiểu sơ lược về mô hình ngôn ngữ, chúng ta sẽ nghiên cứu

kiểu cấu trúc dữ liệu dựa trên Bloom Filter là Bloom Map. Qua các thử

nghiệm, chúng tôi chỉ ra sự ưu việt của các mô hình ngôn ngữ dựa trên

Bloom Filter trên cả phương diện dung lượng và tính hiệu quả khi ứng dụng

trong thực tế, cụ thể ở đây là hệ thống dịch máy bằng phương pháp thống kê

với Moses [2].

2. Đối tượng và phạm vi nghiên cứu

- Luận văn này chúng tôi nghiên cứu về n-gram và cách ước lượng, tính toán

biễu diễn mô hình ngôn ngữ.

- Thực hiện thử nghiệm với dữ liệu tiếng Việt.

3. Nhiệm vụ nghiên cứu

- Thông qua luận văn, trình bày các hiểu biết cơ bản cần biết về mô hình ngôn

ngữ như n-gram, các thuật toán làm mịn được sử dụng trong mô hình ngôn

ngữ và các thước đo để đánh giá một mô hình ngôn ngữ.

- Luận văn tập trung nghiên cứu về các trúc dữ liệu dựa trên Bloom Filter được

sử dụng cho mô hình ngôn ngữ cụ thể là Log-Frequency Bloom Filter.

- Thực hiện thử nghiệm xây dựng mô hình ngôn ngữ trên một ngữ liệu tiếng

Việt và một ngữ liệu tiếng Anh..

- Ngoài ra, luận văn còn giới thiệu sơ lược về dịch máy thống kê, thử nghiệm

dịch máy thống kê với hệ thống dịch máy mã nguồn mở Moses sử dụng các

mô hình ngôn ngữ xây dựng ở chương 3.

4. Những nội dung nghiên cứu chính

Luận văn được trình bày thành 3 phần:

MỞ ĐẦU

NỘI DUNG

Chương 1 - Tổng quan về dịch máy thống kê dựa vào cụm từ và mô

hình ngôn ngữ

Chương 2 - Mô hình ngôn ngữ Bloom Filter

Chương 3 - Ứng dụng Bloom Filter cho hệ dịch máy thống kê dựa vào

cụm từ

KẾT LUẬN

NỘI DUNG

CHƯƠNG I

TỔNG QUAN VỀ DỊCH MÁY THỐNG KÊ DỰA VÀO CỤM TỪ

VÀ MÔ HÌNH NGÔN NGỮ

1.1 Dịch máy thống kê dựa trên cụm từ

1.1.1 Dịch máy và dịch máy thống kê

Dịch máy (Machine Translation - MT) xuất hiện từ thập kỷ 50 của thế

kỷ trước và đặc biệt được phát triển mạnh mẽ từ thập kỷ 80 cho đến ngày nay.

Trên thế giới, hiện tại có rất nhiều hệ dịch máy thương mại nổi tiếng như

Systrans, Kant, … hay những hệ dịch máy mở tiêu biểu là hệ dịch của

Google, hỗ trợ hàng chục cặp ngôn ngữ phổ biến như Anh-Pháp, Anh-Trung,

Anh-Nhật, Hoa-Nhật, … Các cách tiếp cận MT chia làm bốn lớp chính là dịch

trực tiếp (direct), dịch dựa trên luật chuyển đổi (transfer), dịch liên ngữ

(interlingua) và dịch dựa vào thống kê (statistical MT). Trước đây, phương

pháp dịch dựa trên luật chuyển đổi và dịch liên ngữ chủ yếu dựa vào cú pháp

có thời gian phát triển khá dài và hiện vẫn còn được sử dụng phổ biến trong

nhiều hệ dịch thương mại. Những hệ dịch máy loại này này đã đạt được kết

quả khá tốt với những cặp ngôn ngữ tương đồng nhau về cú pháp như Anh-

Pháp, Anh-Tây Ban Nha, … nhưng còn gặp nhiều hạn chế đối với các cặp

ngôn ngữ có cú pháp rất khác nhau như Anh-Trung, Anh-Nhật, …

Dịch Anh-Việt, Việt-Anh ở nước ta cũng vấp phải những khó khăn

tương tự do sự khác biệt về mặt cấu trúc ngữ pháp và tính nhập nhằng của

ngữ nghĩa. Hệ thống dịch Anh-Việt dựa trên luật chuyển đổi được thương mại

hóa đầu tiên ở Việt Nam là EVTran. Nhiều nghiên cứu với yêu cầu tăng chất

lượng dịch hiện nay vẫn đang được thực hiện và có thể thích nghi với đặc

điểm của các cặp ngôn ngữ khác nhau.

Dịch máy thống kê (SMT) là một phương pháp dịch máy, trong đó các

bản dịch được tạo ra trên cơ sở các mô hình thống kê có các tham số được bắt

nguồn từ việc phân tích các cặp câu song ngữ. Các phương pháp tiếp cận

thống kê tương phản với các phương pháp tiếp cận dựa trên luật trong dịch

máy cũng như với dịch máy dựa trên ví dụ.

Những ý tưởng đầu tiên của dịch máy thống kê đã được giới thiệu

bởi Warren Weaver vào năm 1949 [1], bao gồm cả những ý tưởng của việc áp

dụng lý thuyết thông tin của Claude Shannon. Dịch máy thống kê được tái

giới thiệu vào năm 1991 bởi các nhà nghiên cứu làm việc tại Trung tâm

nghiên cứu Thomas J. Watson của IBM[2] và đã góp phần đáng kể trong sự

hồi sinh việc quan tâm đến dịch máy trong những năm gần đây. Ngày nay nó

là phương pháp dịch máy được nghiên cứu nhiều nhất.

Dịch máy bằng phương pháp thống kê (Statistical Machine

Translation) đã chứng tỏ là một hướng tiếp cận đầy đầy tiềm năng bởi những

ưu điểm vượt trội so với các phương pháp dịch máy dựa trên cú pháp truyền

thống qua nhiều thử nghiệm về dịch máy. Thay bằng việc xây dựng các từ

điển, các luật chuyển đổi bằng tay, hệ dịch này tự động xây dựng các từ điển,

các quy luật dựa trên kết quả thống kê có được từ dữ liệu. Vì thế, dịch máy

dựa vào thống kê có tính khả chuyển cao, có khả năng áp dụng được cho cặp

ngôn ngữ bất kỳ. Hệ thống SMT được đề xuất lần đầu tiên bởi Brown năm

1990 sử dụng mô hình kênh nhiễu và đã phát triển áp đảo trong ngành MT

nhiều năm trở lại đây. Thêm vào đó dịch máy thống kê có những ưu điểm sau:

Dịch máy (MT) là vấn đề quyết định: Cho trước những từ trong ngôn

ngữ nguồn, chúng ta phải quyết định chọn những từ trong ngôn ngữ đích. Vì

vậy, nó tạo cho chúng ta một cảm giác là có thể giải quyết nó bằng định lý

quyết định thống kê. Điếu đó dẫn đến cách tiếp cận thống kê được đề xuất.

Mối quan hệ giữa đối tượng ngôn ngữ như từ, cụm từ và cấu trúc ngữ

pháp thường yếu và mơ hồ. Để mô hình hóa những phụ thuộc này, chúng ta

cần một công thức hóa như đưa ra phân phối xác suất mà nó có thể giải quyết

với những vấn đề phụ thuộc lẫn nhau.

Để thực hiện MT, chúng ta nhất thiết phải kết hợp nhiều nguồn trí thức.

Trong dịch thống kê, chúng ta dựa vào toán học để thực hiện kết hợp tối ưu

của các nguồn trí thức.

Trong dịch máy thống kê (SMT), trí thức dịch được học một cách tự

động từ dữ liệu huấn luyện. Với kết quả như vậy, việc phát triển một hệ dịch

dựa vào thống kê sẽ rất nhanh so với hệ dịch dựa vào luật.

SMT khá phù hợp với ứng dụng nhúng mà ở đây MT là một phần của

ứng dụng lớn hơn. Ví dụ, trong dịch các bài nói chuyện, máy nhận dạng tiếng

nói sẽ được thêm vào. SMT xem như rất phù hợp với cách tiếp cận này bởi vì

nó tận dụng được sức mạnh của ngôn ngữ tự nhiện.

Việc đưa ra khái niệm “chính xác” của mối quan hệ ngữ pháp, ngữ

nghĩa, văn phong là rất khó khăn nếu không nói là không thể. Vì vậy, việc

hình thức hóa vấn đề này càng chính xác càng tốt không thể dựa vào sự giằng

buộc bởi các luật mô tả chúng. Thay vào đó, trong cách tiếp cận thống kê, các

giả định mô hình được kiểm định bằng thực nghiệm dựa vào dữ liệu huấn

luyện.

SMT đã cho chất lượng dịch khá tốt. Hệ thống CANDIDE của IBM

được coi là một trong những hệ dịch tốt nhất hiện nay trên thế giới. Chất

lượng đạt trên 80%.

Với phương pháp dịch trực tiếp, từng từ được dịch từ ngôn ngữ nguồn

sang ngôn ngữ đích. Trong dịch dựa trên luật chuyển đổi, đầu tiên chúng ta

cần phải phân tích cú pháp của câu vào, rồi áp dụng các luật chuyển đổi để

biến đổi cấu trúc câu này ở ngôn ngữ nguồn sang cấu trúc của ngôn ngữ đích;

cuối cùng ta mới dịch ra câu hoàn chỉnh. Đối với dịch liên ngữ, câu vào được

phân tích thành một dạng biểu diễn trừu tượng hóa về ngữ nghĩa, được gọi là

“interlingua”, sau đó ta tìm cách xây dựng câu đích phù hợp nhất với

“interlingua” này. Dịch máy thống kê có cách tiếp cận hoàn toàn khác, khả

năng dịch có được là dựa trên các mô hình thống kê được huấn luyện từ các

ngữ liệu song ngữ. Kiến trúc chung của một hệ thống SMT được thể hiện

trong hình 1.

Mô hình của Brown (hay còn gọi là mô hình IBM) [7] biểu diễn quá

trình dịch bằng một mô hình kênh nhiễu (noisy channel model) bao gồm ba

thành phần: một mô hình dịch (translation model), có nhiệm vụ liên hệ các từ,

cụm từ tương ứng của các ngôn ngữ khác nhau; một mô hình ngôn ngữ (LM),

đại diện cho ngôn ngữ đích; một bộ giải mã (decoder), kết hợp mô hình dịch

và mô hình ngôn ngữ để thực hiện nhiệm vụ dịch.

Ngôn ngữ nguồn ( )

Tiền xử lý

Mô hình ngôn ngữ Bộ giải mã

Mô hình dịch

Hậu xử lý

Ngôn ngữ đích ( )

Hình 1: Kiến trúc của một hệ thống SMT

1.1.2 Dịch máy thống kê dựa trên cụm

He is a good doctor

Anh ấy là một bác sỹ giỏi

Hình 2: Minh họa dịch máy thống kê dựa vào cụm

Với dịch dựa trên cụm, một chuỗi các từ liên tiếp (cụm) được dịch sang

ngôn ngữ đích, với độ dài cụm ngôn ngữ nguồn và đích có thể không giống

nhau. Hình 2 minh họa phương pháp dịch cụm: câu vào được chia thành một

số cụm; từng cụm một được dịch sang ngôn ngữ đích và sau đó các cụm được

đảo trật tự theo một cách nào đó rồi ghép với nhau. Kết quả ta thu được câu

dịch trong ngôn ngữ đích.

Nếu gọi ngôn ngữ nguồn là f và ngôn ngữ đích là e, ta sẽ cố gắng tối

đa hóa xác suất với mong muốn có được bản dịch tốt nhất. Trong

thực tế tồn tại hơn một bản dịch đúng cho cùng một câu, mục đích của ta là

tìm ra câu ngôn ngữ e phù hợp nhất khi cho trước câu ngôn ngữ nguồn f. Dịch

dựa vào cụm áp dụng mô hình kênh nhiễu, sử dụng công thức Bayes ta có:

Vì Pr(f) là không thay đổi đối với e, bài toán trở thành việc tìm câu e

nhằm cực đại hoá giá trị , có giá trị cực đại khi

và cực đại. Việc xây dựng mô hình ngôn ngữ cần sử dụng một

ngữ liệu đơn ngữ lớn, trong khi đó mô hình dịch lại cần đến ngữ liệu song ngữ

tốt. Bộ giải mã được sử dụng để tìm ra câu dịch tốt nhất khi đã biết được

I . Giả

Để có được câu dịch, câu nguồn được chia thành I cụm liên tiếp f1

sử rằng phân phối xác suất là như nhau đối với các cụm này. Mỗi cụm fi trong

I được dịch thành cụm tương ứng trong ngôn ngữ đích ei . Các cụm trong

ngôn ngữ đích có thể đảo ví trí cho nhau. Quá trình dịch cụm được mô hình

hóa bởi phân phối xác suất .

Việc đảo vị trí (reodering) của các cụm đầu ra được mô hình bởi phân

phối xác suất d(ai – bi-1), trong đó ai đại diện cho vị trí bắt đầu của cụm trong

câu nguồn được dịch thành cụm thứ i trong câu đích, và bi-1 là ký hiệu chỉ vị

trí kết thúc của cụm trong câu nguồn được dịch thành cụm (i-1) trong câu

đích. Ở đây chúng ta sử dụng mô hình đảo cụm như sau:

Trong đó α là giá trị tham số thích hợp.

Muốn xác định độ dài phù hợp của câu dịch, ta đưa thêm thừa số ω khi

sinh ra câu trong ngôn ngữ đích. Qua quá trình tìm kiếm câu dịch tối ưu thừa

số này sẽ được tối ưu. Độ dài của câu trong ngôn ngữ đích càng dài khi thừa

số này càng lớn hơn 1.

Như vậy, câu dịch tốt nhất được sinh ra từ câu nguồn theo mô

hình trong là:

Với được phân tích:

1.2 Tổng quan về mô hình ngôn ngữ

Mô hình ngôn ngữ là một phân bố xác suất trên các tập văn bản. Nói

đơn giản, mô hình ngôn ngữ có thể cho biết xác suất một câu (hoặc cụm từ)

thuộc một ngôn ngữ là bao nhiêu.

Ví dụ: Khi áp dụng mô hình ngôn ngữ cho tiếng Việt:

P[“hôm qua là ngày nghỉ lễ”] = 0.001

P[“nghỉ lễ là qua hôm ngày”] = 0

Mô hình ngôn ngữ được áp dụng trong rất nhiều lĩnh vực của xử lý

ngôn ngữ tự nhiên như: kiểm lỗi chính tả, dịch máy hay phân đoạn từ... Chính

vì vậy, nghiên cứu mô hình ngôn ngữ chính là tiền đề để nghiên cứu các lĩnh

vực tiếp theo.

Mô hình ngôn ngữ có nhiều hướng tiếp cận, nhưng chủ yếu được xây

dựng theo mô hình Ngram.

1.2.1 N-gram

Phương pháp đơn giản nhất để ngắt một chuỗi kí tự thành các thành

phần nhỏ hơn gọi là các chuỗi con. Mỗi chuỗi con n-từ như vậy được gọi là n-

gram.

Với n = 1 ta gọi là unigram hay còn gọi là từ;

Với n = 2 ta gọi là bigram;

Với n = 3 ta gọi là trigram.

Nếu một chuỗi kí tự có rất nhiều n-gram hợp lệ thì ta có thể kết luận

chuỗi kí tự đó là chuỗi hợp lệ. Kí hiệu b(y/x) là xác suất mà từ y theo sau từ x.

Chúng ta có thể ước lượng xác suất này dựa vào Corpus.

Xác suất bigram điều kiện là thương số của phép chia số lần xuất hiện

cụm “xy” cho số lần xuất hiện từ “x” trong Corpus, được kí hiệu là p(x|y).

Ví dụ về xác suất bigram điều kiện:

P(qua | hôm,): ta có thể hiểu là xác suất để từ “qua” xuất hiện sau từ

“hôm”. Về giá trị này, chúng ta có thể xác định trực tiếp và tự động từ corpus

tiếng Anh. Giả sử trong corpus mà ta test, “hôm” xuất hiện 468 lần, còn “hôm

qua” xuất hiện 63 lần, thì P(qua | hôm) = 63/468 = 0,13.

Tương tự, ta có định nghĩa tương tự đối với xác suất trigram điều kiện.

Ví dụ về xác suất trigram điều kiện:

P(là | hôm qua): ta có thể hiểu là xác suất để từ “là” xuất hiện sau dãy

hai từ “ hôm qua”. Giả sử trong corpus mà ta test, “hôm qua là” xuất hiện 9

lần, còn “hôm qua” xuất hiện là 28 lần, như vậy P(là | hôm qua) = 9/28 =

0,32.

Ta nhận thấy rằng mỗi từ sẽ liên quan có điều kiện tới toàn bộ các từ

trước nó (ta sẽ gọi đây là lịch sử của sự kiện hoặc từ đó).

Tuy nhiên, việc sử dụng toàn bộ các từ trước đó để đoán nhận từ tiếp

theo là không thể thực hiện được vì hai nguyên nhân sau. Đầu tiên là phương

pháp này không khả thi về mặt tính toán do tốn quá nhiều thời gian, tài

nguyên hệ thống cho mỗi lần dự đoán. Hai là, trong rất nhiều trường hợp, chỉ

sau khi duyệt vài từ trong lịch sử, ta đã nhận thấy rằng đó là một câu chưa

từng gặp trước đây. Bởi vậy kể cả khi đã biết toàn bộ lịch sử của một từ, xác

suất của nó vẫn có thể là không biết. Thay vào đó, các mô hình ngôn ngữ

thường được ước lượng tương đối xác suất dựa trên giả định Markov (hay mô

hình Markov ẩn), rằng từ tiếp theo chỉ chịu ảnh hưởng từ một vài từ trước đó.

Một mô hình Markov bậc n giả định rằng chỉ n từ trước đó có liên hệ ngữ

cảnh với từ đang cần xác định. Việt quyết định bao nhiêu từ trước đó mà LM

quan tâm được gọi là bậc n (order) của LM, và thường được gọi là 1-gram

(unigram), 2-gram (bigram), 3- gram (trigram), 4-gram (fourgram) tương ứng

với các mô hình Markov bậc một, hai, ba, bốn. Ví dụ, nếu chúng ta muốn ước

lượng xác suất 3-gram của một từ wi với mô hình Markov bậc 2 thì chúng ta

sẽ dựa trên hai từ trước đó:

Pr(w1, w2, ..., wi) ≈ Pr(wi|wi-2, wi-1)

Hình 1: Mô hình Markov bậc 2

Một cách tổng quát, gọi là một n-gram chiều dài n kết thúc bằng

từ . Khi đó để ước lượng xác xuất n-gram cho một chuỗi chiều dài N ta sử

dụng công thức:

1.2.2 Mô hình ngôn ngữ

Trước hết chúng ta xem xét về trật tự từ. Giả sử trong cách dịch của

chúng ta, có một hộp chứa các từ và chúng ta muồn lấy chúng ra theo một thứ

tự hợp lý. Nhưng giả sử rằng chúng ta có vài hộp khác nhau, tương ứng là tập

các nghĩa của cách dịch các từ ở hộp trên. Chúng ta có thể tìm thứ tự từ tốt

nhất của mỗi hộp nhưng làm thế nào để chúng ta chọn câu của ngôn ngữ đích

hợp lý nhất. Câu trả lời là chúng ta sử dụng mô hình n-gram, gán xác suất cho

bất kì một dãy các từ có thể hiểu được. Sau đó chúng ta chọn ra dãy có thể

nhất (xác suất cao nhất).

Ví dụ: dãy các từ “hôm qua là ngày nghỉ lễ” và “tôi vẫn phải đi làm” là

có thể hiểu được (có thể tồn tại) ngược lại dãy “nghỉ lễ là qua hôm ngày” và

“đi tôi vẫn làm phải” là không thể hiểu được (không tồn tại). Về ngôn ngữ

học, theo truyền thống chúng ta chia các dãy các từ này thành hai loại: đúng

ngữ pháp và sai ngữ pháp nhưng trong dịch máy chúng ta luôn luôn phải chọn

giữa hai câu đúng ngữ pháp.

Ví dụ: Cách dịch nào là tốt hơn trong (A) và (B)

(A) Hôm qua là ngày nghỉ lễ nhưng tôi vẫn phải đi làm.

(B) Ngày hôm qua là nghỉ lễ nhưng tôi vẫn phải đi làm.

Mặt khác, trong nhận dạng tiếng nói người ta sử dụng khá nhiều xác

suất theo kinh nghiệm gán cho dãy các từ. Ví dụ: “nghỉ lễ là” đúng hơn là “là

nghỉ lễ”.

Phương pháp sử dụng ở đây là dựa vào bigram hoặc trigram để chuyển

chúng thành xác suất để so sánh.

Để gán xác suất cho toàn bộ một câu, ta nhân xác suất điều kiện n-gram

mà nó bao gồm. Vì vậy, một câu tốt (càng đúng ngữ pháp) là câu mà có nhiều

dãy n-gram. Ví dụ trong bigram ta có:

P(Hôm qua là ngày nghỉ lễ) =

P(Hôm | đầu câu) *

P(qua | Hôm) *

P(là | qua) *

P(ngày | là) *

P(nghỉ | ngày) *

P(cuổi câu | nghỉ lễ)

Dễ dàng thấy rằng điều này có ích như thế nào đối với trật tự từ. Dựa

vào cách tính xác suất như trên ta thấy rằng câu “Hôm qua là ngày nghỉ lễ” tốt

hơn “Nghỉ lễ ngày là qua hôm”.

Như vậy, ta có thể coi toàn bộ các chủ đề về gán xác suất cho một câu

được gọi là mô hình ngôn ngữ.

Mô hình ngôn ngữ không chỉ có ích cho thứ tự các từ mà còn có ích

cho việc chọn nghĩa giữa các cách dịch khác nhau.

Ví dụ: Cho 2 câu (A) và (B)

(A) Áo trắng em đến trường, cùng đàn chim ca rộn ràng.

(B) Em đến trường áo trắng, cùng đàn chim ca rộn ràng.

Quyết định này dịch từ tiếng Anh sang tiếng Việt, cụm từ “Áo trắng em

đến trường” dùng để chỉ nữ sinh còn “Em đến trường áo trắng” lại dùng để

chỉ trang phục. Nếu trong corpus của chúng ta, giả sử trigram “Áo trắng em

đến trường” xuất hiện 10 lần, trong khi “Em đến trường áo trắng” không xuất

hiện (hoặc khá nhỏ so với “Áo trắng em đến trường”) thì (A) là câu tốt hơn

(được chọn). Điều đó có nghĩa là ta có thể giả quyết vấn đề nhập nhằng ngữ

nghĩa chỉ dựa vào ngôn ngữ đích.

1.2.3 Huấn luyện mô hình ngôn ngữ

Khi huấn luyện (xây dựng) một mô hình ngôn ngữ ta cần chuẩn bị dữ

liệu là một ngữ liệu đơn ngữ (corpus) (kích thước dữ liệu huấn luyện lớn sẽ

cho mô hình ngôn ngữ tốt) và một bộ ước lượng thống kê có nhiệm vụ mô

hình hóa lượng xác suất của ngữ liệu. Các bộ ước lượng được mà LM sử dụng

đều cần đến tần suất của các n-gram, vì vậy ta cần đếm tần suất xuất hiện của

các n-gram từ 1-gram cho đến số bậc mô hình đang huấn luyện.

1.2.3.1 Ước lượng cực đại hóa khả năng (Maximium Likelihood

Estimation - MLE)

Để xây dựng một mô hình ước lượng cực đại hóa khả năng với tần suất

tương đối của các n-gram trong ngữ liệu ta có thể sử dụng kết quả đếm các n-

gram. Với ước lượng cực đại hoá khả năng, xác suất một unigram nhất định

nào đó sẽ xuất hiện tiếp theo đơn giản là tần suất nó xuất hiện trong ngữ liệu.

Với là số lần xuất hiện của từ trong ngữ liệu.

Phương pháp này được gọi như vậy bởi vì nó cực đại hóa giá trị đầu ra để mô

hình hóa ngữ liệu huấn luyện. Ví dụ, trong ngữ liệu Brown1, một ngữ liệu với

một triệu từ, từ khóa ”Chinese” xuất hiện 400 lần. Vậy thì xác suất mà một

mô hình ngôn ngữ dùng MLE sẽ gán cho unigram ”Chinese” là

Xác suất điều kiện của một n-gram tổng quát với bậc >1 là:

Nghĩa là một từ nào đó có tần suất xuất hiện thường xuyên sau lịch sử

có bậc n-1. Để minh họa, ta tiếp tục ví dụ trên, xác suất bigram ”Chinese

food” xuất hiện là số lần từ ”food” xuất hiện sau từ ”Chinese” chia cho

c(Chinese) = 400. Với ngữ liệu Brown, cụm từ ”Chinese food” xuất hiện 120

lần, ta có:

PrMLE(food|Chinese) = 0.3

1.2.3.2 Các phương pháp làm mịn

MLE là một phương pháp dễ hiểu, dễ sử dụng để ước lượng xác suất

cho mô hình, tuy nhiên trong thực tế ta gặp phải vấn đề dữ liệu thưa (data

sparseness problem). Nghĩa là tập ngữ liệu dùng để xây dựng LM dù lớn cũng

chỉ là tập hữu hạn các câu trong vô số câu có thể của một ngôn ngữ tự nhiên.

Do đó một LM chỉ sử dụng MLE sẽ gán xác suất bằng 0 cho nhiều n-gram tốt.

Để hạn chế vấn đề này, người ta thường sử dụng các phương pháp ước lượng

xác suất thống kê phức tạp hơn thay cho MLE. Những phương pháp này được

gọi là làm mịn (smoothing) hay trừ hao (discounting), khi mà một phần xác

suất từ các sự kiện trong mô hình sẽ được dành cho những sự kiện chưa từng

xuất hiện. Việc lấy từ cái gì và trừ hao như thế nào là một đề tài vẫn đang

được nghiên cứu nhiều. Ví dụ, cách cổ điển nhất của làm mịn là phương pháp

Add-one smoothing [13], trong phương pháp này, ta thêm một lượng vào

kết quả đếm số lần xuất hiện của tất cả từ vựng trong ngữ liệu.

Backoff và interpolation là hai khái niệm quan trọng được sử dụng

trong quá trình làm mịn. Khi LM gặp một n-gram chưa biết, việc tính xác suất

sẽ sử dụng thông tin từ (n-1)-gram, khi sự kiện (n-1)-gram cũng chưa từng

xuất hiện trong quá trình huấn luyện thì LM lại sử dụng thông tin xác suất từ

(n-2)-gram, ... cứ tiếp tục như vậy cho đến khi tính được xác suất của n-gram.

Quá trình này được gọi là backoff và được định nghĩa như sau:

Với là hệ số trừ hao dựa trên tần suất xuất hiện của trong lịch

sử, là tham số backoff. Khi số lượng từ vựng đủ lớn, chúng ta có thể sẽ cần

gán xác suất bằng 0 cho một số từ ngoài từ điển (out of vocabulary – OOV)

khi ở mức unigram. Ví dụ như khi ta có một cuốn từ điển chuyên ngành và

không muốn chia sẻ lượng xác suất của các từ vựng đó (các danh từ chung,

các số thực đặc biệt, ...) cho các OOV. Một cách khác là chúng ta làm mịn

LM và dành một lượng xác suất nhỏ gán cho các OOV khi ở mức unigram.

Interpolation là phương pháp kết hợp thông tin thống kê n-gram qua tất

cả các bậc của LM. Nếu bậc của LM là n thì công thức đệ quy interpolation

như sau:

Với là trọng số quyết định bậc của LM có ảnh hưởng lớn nhất đến

giá trị đầu ra. Tổng trọng số được sử dụng cho tất cả các bậc n-gram bằng

một. Có nhiều cách để xác định giá trị cho các trọng số này, đối với

phương pháp interpolation đơn giản thì các giá trị này giảm theo số bậc n-

gram. Tuy nhiên thông thường chúng sẽ tính toán theo điều kiện ngữ cảnh cụ

thể, nghĩa là theo tần suất của các bậc n-gram trong lịch sử. Các trọng số này

không được tính toán từ dữ liệu huấn luyện, mà sử dụng tập dữ liệu held-out

riêng biệt – tập này chỉ được dùng để huấn luyện các tham số, mà trong

trường hợp này là các giá trị . Cần thấy rằng sự khác biệt cơ bản giữa hai

phương pháp này là interpolation sử dụng thông tin từ các bậc thấp hơn ngay

cả khi dữ liệu xác suất của n-gram cần tính đã khác 0; trong khi đó backoff lại

chỉ tìm kiếm đến dữ liệu khác 0 gần nhất.

Những tiểu mục tiếp theo sẽ trình bày về một số phương pháp làm mịn

phổ biến nhất hiện nay, như Kneser-Ney[6] hay Stupid backoff của

Google[5].

1.2.3.2.1 Kneser-Ney

Kneser-Ney (KN) là thuật toán làm mịn công bố năm 1995 [6], được

phát triển bởi Reinhard Kneser và Hermann Ney. Trong thuật toán KN, xác

suất của một unigram không tỉ lệ thuận với tần suất xuất hiện của nó mà với

số tiền tố mà nó có.

Có thể minh họa như sau, bigram “San Francisco” rất phổ biến trong

cuốn sách “Lịch sử thành phố San Francisco”. Với tần suất bigram này cao

như vậy thì nếu sử dụng phương pháp đơn giản, tần suất của từng từ “San” và

“Francisco” cũng sẽ phải rất cao. Tuy nhiên trong thuật toán KN thì xác suất

Pr(Francisco) lại có thể là rất thấp, vì từ “Francisco” thường chỉ đứng sau từ

“San”. Do các LM bậc thấp thường được sử dụng cho việc tính xác suất

backoff của các LM bậc cao hơn, nên thuật toán KN muốn tận dụng sự lãng

phí lượng xác suất này trong các thuật toán trước đó để dành cho các sự kiện

có khả năng xảy ra lớn hơn.

Trước hết chúng ta định nghĩa số lượng tiền tố của một từ như sau:

Thuật ngữ để chỉ số lượng các từ xuất hiện một lần hoặc nhiều

hơn và ký tự “ ” chỉ một từ bất kỳ nào đó. Thay vì sử dụng tần suất như trong

MLE, tần suất thô của mỗi từ được thay thế bằng số lượng từ (khác nhau)

đứng trước từ đó. Xác suất của unigram trong thuật toán KN được tính là:

Tức là bằng số lượng tiền tố của từ chia cho tổng số tiền tố của tất

cả các unigram trong ngữ liệu.

Với các bậc cao hơn, xác suất này được tính như sau:

Trong đó tử số:

Và mẫu số là tổng số lượng tiền tố của tất cả các n-gram có cùng chiều

. Mô hình đầy đủ của thuật toán KN được nội suy và có dạng như dài

Với:

Là số lượng hậu tố (khác nhau) xuất hiện sau từ ; và D là tham số

trừ hao.

1.2.3.2.2 Kneser-Ney cải tiến (Modified Kneser-Ney - MKN)

Thuật toán làm mịn Kneser-Ney cải tiến do Chen và Goodman nghiên

cứu, công bố năm 1999 [11], được phát triển từ thuật toán KN. Thuật toán KN

dùng phương pháp trừ hao tuyệt đối (absolutely discounting), trừ đi một giá

trị D duy nhất, 0 < D < 1, cho mọi kết quả đếm khác 0. Thuật toán MKN nâng

cao hiệu quả của KN bằng cách sử dụng các giá trị trừ hao khác nhau trong

những trường hợp khác nhau, dựa trên giá trị đếm của mỗi n-gram. Công thức

tổng quát của MKN là:

Với:

Và:

Với là tổng số n-gram có kết quả đếm là i của mô hình bậc n đang

được nội suy. Tổng tất cả các phân phối phải bằng một, do vậy:

Trong đó và tương ứng đại diện cho số sự kiện có kết quả đếm

là hai và ba hoặc nhiều hơn ba.

1.2.3.2.3 Stupid Backoff

Thuật toán Kneser-Ney và Kneser-Ney cải tiến ở trên tuy hiệu quả

trong thực tế nhưng việc tính toán lại khá phức tạp, khối lượng tính toán sẽ trở

nên rất lớn khi dữ liệu nhiều, chẳng hạn như ngữ liệu n-gram Trillion Words

của Google.

Thay vì sử dụng thuật toán KN và MKN, Google sử dụng một thuật

toán làm mịn đơn giản hơn là Stupid Backoff. Thuật toán này sử dụng tần suất

tương đối của các n-gram một cách trực tiếp như sau:

Với N là cỡ của ngữ liệu huấn luyện. Brants[5] đã tuyên bố rằng khi có

lượng dữ liệu đủ lớn, thì hiệu quả của Stupid Backoff xấp xỉ làm mịn MKN.

Lý do ở đây ký hiệu S được sử dụng thay cho P là để nhấn mạnh rằng phương

pháp này trả lại điểm số tương đối chứ không phải là xác suất được chuẩn

hóa.

1.3 Đánh giá mô hình ngôn ngữ

Để xây dựng được một mô hình ngôn ngữ hiệu quả, chúng ta phải có

cách để đánh giá chúng. Dưới đây là một số phương pháp phổ biến để đánh

giá một mô hình ngôn ngữ:

- Entropy – Độ đo thông tin

- Perplexity – Độ hỗn loạn thông tin

- Error rate – Tỉ lệ lỗi

1.3.1 Entropy – Độ đo thông tin

Entropy là thước đo thông tin, có giá trị rất lớn trong xử lý ngôn ngữ.

Nó thể hiện mức độ thông tin trong ngữ pháp, thể hiện sự phù hợp của một

câu với ngôn ngữ, và dự đoán được từ tiếp theo trong cụm n-gram. Entropy

của một biến ngẫu nhiên X được tính theo công thức:

Xét các câu gồm hữu hạn m từ trong ngôn ngữ L.

Ta có công thức tính entropy như sau:

Từ công thức trên, ta có thể đưa ra công thức tính tỉ lệ entropy trên các

từ như sau:

Thực tế thì tỉ lệ entropy trên các từ thường được sử dụng vì giá trị của

nó không phụ thuộc vào độ dài các câu. Tuy nhiên, để tính được entropy của

một ngôn ngữ L theo công thức trên thì ta phải xét tới các câu dài vô hạn (tất

cả các câu có thể có trong ngôn ngữ L), đó là điều không thể. Do đó, ta có thể

tính xấp xỉ tỉ lệ entropy trên các từ theo công thức sau:

Định lý Shannon-McMillan-Breiman đã chỉ ra rằng nếu ngôn ngữ ổn

định (chứa các câu gồm các từ với cấu trúc thông dụng) thì công thức trên có

thể biến đổi thành:

Với công thức trên, ta có thể sử dụng công thức Bayes và xác suất của

các n-gram để tính :

Công thức trên đã được biến đổi qua nhiều bước với các xấp xỉ gần

đúng, do vậy để tăng tính chính xác khi sử dụng độ đo entropy thì câu kiểm

tra cần phải đủ dài và tổng quát (phân tán rộng) để tránh tập trung vào các xác

suất lớn (chỉ chứa các cụm thông dụng).

Các bước biến đổi gần đúng công thức trên khiến giá trị H(L) tình theo

công thức cuối cùng sẽ lớn hơn giá trị H(L) gốc. Do vậy, khi tính H(L) của

các mô hình ngôn ngữ khác nhau trên ngôn ngữ L, mô hình nào cho H(L) nhỏ

hơn thì mô hình ngôn ngữ đó thể hiện chính xác ngôn ngữ L hơn.

1.3.2 Độ hỗn loạn thông tin (Perplexity)

LM sau khi được huấn luyện cần phải đánh giá chất lượng của mô hình.

Cách đánh giá chính xác nhất một mô hình ngôn ngữ là kiểm tra trong thực tế.

Ví dụ trong nhận dạng tiếng nói, chúng ta có thể so sánh hiệu quả của 2 mô

hình ngôn ngữ bằng cách chạy bộ nhận dạng ngôn ngữ 2 lần, mỗi lần với 1

mô hình và xem mô hình nào cho kết quả chính xác hơn. Nhưng cách này lại

rất tốn thời gian, vì thế, chúng ta cần 1 công cụ mà có thể nhanh chóng đánh

giá hiệu quả của một mô hình, Perplexity (PP) [3] là thước đo thường được

dùng cho công việc này.

Perplexity thực chất là một dạng biến đổi của entropy chéo (cross

entropy) của mô hình. Entropy chéo là cận trên của entropy. Entropy là một

khái niệm cơ bản trong Thuyết thông tin, đánh giá lượng thông tin của dữ liệu

bằng độ đo sự không chắc chắn. Nếu một biến ngẫu nhiên x tồn tại trong

khoảng X của thông tin đang được đánh giá với phân phối xác suất là p, thì

khi đó entropy của x được định nghĩa là:

Ví dụ khi tung một đồng xu, x chỉ có thể là mặt ngửa hoặc mặt sấp và

xác suất p=0.5 trong cả hai trường hợp. Nhưng khi tung một hột xúc xắc 6 mặt,

khoảng giá trị có thể của kết quả rộng hơn, và các xác suất là . Vì hành

động tung xúc xắc có độ đo không chắc chắn lớn hơn, nên entropy của nó cũng

cao hơn hành động tung đồng xu.

Entropy chéo của một mô hình là độ đo thông tin giữa hai phân phối xác

suất. Đối với một phân phối xác suất q nào đó mà chúng ta sử dụng để mô hình

hóa phân phối xác suất p, entropy chéo được định nghĩa là:

Định lý Shannon-McMillan-Breiman [3] chỉ ra rằng đối với tất cả

entropy và entropy chéo chúng ta đều có thể bỏ đi phần p nếu chuỗi giá trị x đủ

dài. Nếu chúng ta cần tính entropy cho từng từ thì chỉ việc chia cho tổng số từ:

Perplexity được định nghĩa là . Do entropy chéo là cận trên

của entropy, , chúng ta sử dụng entropy chéo trong Perplexity để

không bao giờ đánh giá thấp entropy thực sự của mô hình. Perplexity của một

mô hình được đánh giá trên tập kiểm tra. Trong thực tế, Perplexity là thước đo

đầu tiên để đánh giá một mô hình ngôn ngữ, và có thể được coi là hàm của cả

ngôn ngữ và mô hình. Trên phương diện là hàm của mô hình, nó đánh giá một

mô hình mô phỏng ngôn ngữ chính xác đến mức độ nào. Còn trên phương diện

là hàm của ngôn ngữ, nó đo tính phức tạp của ngôn ngữ.

1.3.3 Tỉ lệ lỗi (Error rate)

Người ta thường sử dụng độ đo entropy và perplexity để so sánh độ

chính xác của các mô hình ngôn ngữ khi xây dựng một mô hình ngôn ngữ tổng

quát. Trong các bài toán cụ thể, người ta sử dụng tỉ lệ lỗi để so sánh độ chính

xác của các mô hình ngôn ngữ.

Soát lỗi chính tả: xét tỉ lệ giữa số lỗi phát hiện sai hoặc không phát hiện

được trên tổng số lỗi có trong văn bản.

Phân đoạn từ: xét tỉ lệ giữa từ phân đoạn sai trên tổng số từ có trong văn

bản.

Bỏ dấu tự động: xét tỉ lệ giữa số từ bị bỏ dấu nhầm trên tổng số từ có

trong văn bản.

Tỉ lệ lỗi thấp chứng tỏ mô hình ngôn ngữ hiệu quả. Việc sử dụng tỉ lệ lỗi

để đánh giá đưa lại kết quả chính xác nhất khi muốn chọn lựa mô hình ngôn

ngữ phù hợp để giải quyết bài toán cụ thể. Tỉ lệ lỗi thường tỉ lệ thuận với giá trị

entropy nhưng đôi khi mức độ tăng/giảm của tỉ lệ lỗi và entropy không đều.

1.4 Đánh giá chất lượng dịch tự động dựa trên điểm BLEU

Muốn đánh giá chất lượng các hệ thống dịch có thể sử dụng phương

pháp thủ công bởi chuyên gia hoặc sử dụng phương pháp đánh giá tự động.

Quá trình đánh giá thủ công cho điểm cho các câu dịch dựa trên sự trôi chảy

và chính xác của câu dịch. Có thể khẳng định rằng đây là phương pháp đánh

giá có độ chính xác nhất. Tuy nhiên, công việc đánh giá thủ công này lại tiêu

tốn quá nhiều thời gian, đặc biệt khi cần so sánh nhiều mô hình ngôn ngữ,

nhiều hệ thống khác nhau. Công bằng mà nói, mỗi phương pháp đều có ưu

nhược điểm riêng. Mặc dù đánh giá tự động có thể không phản ánh được hết

mọi khía cạnh của chất lượng dịch, nhưng nó có thể nhanh chóng cho ta biết:

chất lượng của hệ dịch ở mức nào, có tăng hay không sau khi được cải tiến

hoặc thay đổi một vài tham số nào đó. Thực tế, hai phương pháp này được sử

dụng song song, và điểm BLEU là độ đo chất lượng hệ dịch phổ biến nhất

hiện nay, được đề xuất bởi Papineni năm 2002.

Đối chiếu kết quả dịch với tài liệu dịch tham khảo và tài liệu nguồn là

cách tính điểm của BLEU. Dù [9] chỉ ra rằng điểm BLEU thường không thực

sự tương quan với đánh giá thủ công bằng chuyên gia với các loại hệ thống

khác nhau, thế nhưng vẫn có thể khá chính xác để đánh giá trên cùng một hệ

thống, hoặc những hệ thống tương tự nhau. Vì thế, trong khóa luận này, tôi sử

dụng điểm BLEU làm thước đo chất lượng dịch và từ đó so sánh các loại mô

hình ngôn ngữ khác nhau.

CHƯƠNG 2

MÔ HÌNH NGÔN NGỮ BLOOM FILTER

Mô hình ngôn ngữ kể từ khi xuất hiện đến nay đã có những bước phát

triển đáng kể cùng với các thuật toán làm mịn ngày càng tốt hơn [5]. Tuy

nhiên cũng còn nhiều thách thức mà LM phải đối mặt. Đó là làm thế nào tạo

ra được mô hình đại diện hiệu quả ngôn ngữ tự nhiên, bằng cách sử dụng ngữ

liệu lớn, tăng bậc mô hình n-gram và giảm độ phức tạp trong tính toán và sử

dụng ít bộ nhớ. Một tập ngữ liệu như của Google là quá lớn (24GB khi đã

nén), bộ nhớ RAM thông thường không thế chứa vừa. Điều này là động lực

thúc đẩy các nhà nghiên cứu cần tìm ra một giải pháp thay thế cách biểu diễn

n-gram truyền thống, nếu vẫn muốn tận dụng ưu thế của các tập ngữ liệu lớn

mà không cần sử dụng các phương thức tốn kém truyền thống như hệ thống

siêu máy tính trong môi trường điện toán phân tán của Google.

Bloom Fillter (BF) [4] là một loại cấu trúc dữ liệu có khả năng đáp ứng

phần nào những yêu cầu nêu trên, đó chính là, sử dụng một dạng mã hóa có

mất mát thông tin (lossy encoding), ý tưởng của BF là thay vì lưu trữ tất cả

các n-gram, chúng ta chỉ lưu tập đại diện mang tính ngẫu nhiên của nó. Mã

hóa có mất mát thông tin là một loại kỹ thuật phổ biến thường được dùng

trong lưu trữ đa phương tiện như chuẩn nén JPEG cho hình ảnh, MP3 cho âm

thanh hay MPEG cho nén video. Trong đó mặc dù một phần dữ liệu bị mất đi

khi mã hóa, nhưng đại diện mới được tạo thành sau khi được giải mã vẫn

chứa đựng khá đầy đủ các thông tin hữu ích.

Để trả lời cho câu hỏi “Liệu phần tử x có thuộc tập S hay không?” mà

một cấu trúc dữ liệu xác suất Bloom Filter đã được xây dựng. Nếu câu trả lời

là có thì ta gọi đó là một HIT, còn ngược lại thì ta gọi là MISS. Khi đối tượng

được truy vấn không thuộc tập S ( ), nhưng lại HIT có hai loại lỗi có thể

xảy ra. Còn false negative thì trái ngược với false positive, tức là một đối

tượng bị kết luận là MISS trong khi thực tế thì hoàn toàn ngược lại. Cấu

trúc dữ liệu thống kê nào chỉ gặp một trong hai loại lỗi này được gọi là có lỗi

một phía (one-side error) và lỗi hai phía trong trường hợp còn lại. BF là cấu

trúc dữ liệu chỉ có lỗi một phía.

Cấu trúc dữ liệu này yêu cầu dung lượng lưu trữ thấp hơn khá nhiều

ngưỡng dưới của thuyết Entropy nhưng lại có tỉ lệ lỗi khá thấp và có thể xác

định được. Bloom Filter nguyên bản không hỗ trợ lưu trữ cả cặp khóa-giá trị.

Tuy nhiên Talbot và Osborne đã đề xuất những cách cho phép tích hợp giá trị

vào trong mô hình ngôn ngữ Bloom Filter.

2.1 Các cấu trúc dữ liệu xác suất (PDS)

Lưu trữ và xử lý dữ liệu là một bước quan trọng trong khâu thiết kế của

một chương trình. Cấu trúc dữ liệu sử dụng trong chương trình được đánh giá

và lựa chọn cẩn trọng có ý nghĩa rất quan trọng: tiết kiệm tài nguyên, tăng

đáng kể hiệu năng của chương trình, dễ dàng bảo trì hệ thống trong tương lai

nếu được lựa chọn đúng; ngược lại, khả năng vận hành của hệ thống có thể bị

hạn chế do khối lượng tính toán quá lớn hay hoạt động thiếu ổn định, thậm

chí không hoạt động được với những tập dữ liệu lớn nếu sử dụng một cấu trúc

dữ liệu tồi.

Hiện nay tuỳ thuộc vào mục đích sử dụng khác nhau mà tồn tại nhiều

dạng cấu trúc dữ liệu khác nhau. Một vài cấu trúc dữ liệu chỉ là những kho

chứa dữ liệu thông thường, còn một số khác lại được dùng cho những ứng

dụng đặc biệt và chỉ phát huy được hiệu năng tối đa trong điều kiện nhất định.

Thực tế nhiều trường hợp, khi tập ngữ liệu quá lớn đến mức hiện tại

không một siêu máy tính nào có khả năng quản lý được và cũng chưa có cấu

trúc dữ liệu chuẩn nào có thể lưu trữ được nó. Ví dụ như, trong lĩnh vực dịch

máy thống kê, năm 2006, Google đã khiến cả cộng đồng ngành NLP phải

kinh ngạc khi họ công bố một ngữ liệu Ngram khổng lồ. Với khoảng 3 tỉ từ,

chiếm 24 GB bộ nhớ khi đã nén, tập ngữ liệu như vậy là quá lớn, thậm chí

ngay cả với hệ thống bộ nhớ của những siêu máy tính. Rõ ràng là ta có thể lưu

trữ nó trong ổ đĩa cứng, nhưng ví dụ như với dịch máy thống kê (SMT), một

mô hình ngôn ngữ có thể được truy vấn hàng trăm nghìn lần mỗi câu, vậy nên

hiển nhiên đây không phải là một phương án khả thi. Chúng ta cần tìm ra một

hướng tiếp cận khác cho những tập ngữ liệu khổng lồ như vậy.

Có một cách tiếp cận khả thi hơn là thay vì tìm cách biểu diễn đầy đủ

một tập ngữ liệu lớn, không mất mát (lossless), ta chấp nhận sử dụng một tập

đại diện có mất mát (lossy) của nó. Nghĩa là bằng cách sử dụng một số kỹ

thuật nào đó:

i) Một lượng dữ liệu mà ta kiểm soát được bị mất đi.

ii) Sự toàn vẹn dữ liệu bị tổn hại gây ra bởi lượng dữ liệu đã mất có

thể được coi là nhỏ khi so sánh với không gian lưu trữ đáng kể ta tiết kiệm

được. Đồng thời thay vì không thể kiểm soát được dữ liệu (không sử dụng

được trong các chương trình do tập này quá lớn, thời gian tìm kiếm lâu, …),

giờ đây ta đã có thể kiểm soát được chúng.

Phương pháp này phát triển thành một lớp cấu trúc dữ liệu mới, được

gọi là các Cấu trúc dữ liệu ngẫu nhiên (Randomised Data Structure - RDS)

hay còn được gọi là các Cấu trúc dữ liệu xác suất (Probabilistic Data

Structure - PDS). Trong các PDS, dữ liệu được mã hóa và tối ưu dưới dạng bị

mất mát, và từ “ngẫu nhiên” ám chỉ các cấu trúc dữ liệu này dựa trên những

thuật toán mã hóa mang tính ngẫu nhiên nhất định.

Có thể định nghĩa một thuật toán ngẫu nhiên là “thuật toán sử dụng các

lựa chọn tùy ý, không xác định trước trong quá trình tính toán” [14]. Khi mã

hóa vào một PDS, một phần dữ liệu sẽ bị mất. Tuy vậy thông tin sẽ được lưu

trữ sao cho dạng biểu diễn mất mát này của dữ liệu vẫn có hiệu quả tương

đồng với dạng biểu diễn đầy đủ (không mất mát) của nó.

Trong những năm gần đây có nhiều loại cấu trúc dữ liệu xác suất đã

được nghiên cứu, phát triển và ứng dụng, có thể kể đến như Skip List, Sparse

Partition [8], Lossy Dictionary và một cấu trúc dữ liệu tuy đã xuất hiện từ khá

lâu nhưng hiện tại lại tiếp tục được nghiên cứu nhiều đó là Bloom Filter.

Bloom Filter có một số ưu điểm như tốc độ, khả năng tiết kiệm bộ nhớ

đáng kể, tôi đã chọn nghiên cứu loại cấu trúc dữ liệu này và trình bày trong

luận văn. Cấu trúc dữ liệu Bloom Filter cơ bản sẽ được giới thiệu trong phần

sau của chương này. Tiếp đó là cải tiến đơn giản để có thể lưu trữ dữ liệu theo

cặp {khóa, giá trị} – Logarithmic Frequency Bloom Filter (hay Bloom Filter

tần số log).

2.2 Hàm băm (Hash function)

Hàm băm là một thành phần rất quan trọng được sử dụng trong Bloom

Filter. Vì vậy trước khi đi sâu tìm hiểu cấu trúc dữ liệu BF, mục này trình bày

vài nét sơ lược về hàm băm.

Một hàm ánh xạ phần tử từ tập này sang một tập khác (thường là nhỏ

hơn) được gọi là Hàm băm.

INPUT OUTPUT

DFA2C4ED Quả Hàm băm

BE34C87A Quả táo Hàm băm

7 CD4ADE Quả cam Hàm băm

Hình 3: Ví dụ về hàm băm. Các xâu ký tự được chuyển thành chữ ký đại diện. Phần tử cần được băm thuộc tập S có cỡ n, tập này nằm trong tập dữ

liệu ban đầu U với S U và U = . Đại diện của phần tử đó trong miền

b được gọi là chữ ký hay dấu ấn của dữ liệu. Hàm h này phải ổn định, nghĩa là

khi cùng một dữ liệu đi qua hàm h nhiều lần thì luôn cho kết quả không đổi và nếu đầu ra của hai phần tử qua hàm h khác nhau thì hai phần tử đó là khác nhau.

Khóa ki được đưa vào hàm băm h(ki), kết quả của hàm băm này trỏ đến

một ô trong bảng giá trị cỡ m: {0,1,...,m-1} (được gọi là bảng băm), ô đó chứa

giá trị ai. Đặc tính đáng chú ý của bảng giá trị băm này là thời gian tìm kiếm

không phụ thuộc vào kích cỡ của tập dữ liệu được mã hóa vào bảng.

w , a k 1 4

w 1 , a k 2

w 2 , k a 4

… …

w , a k 3 3

… …

???

… …

U

… …

Hình 4: Cặp khóa ki và giá trị ai của tập S được ánh xạ thông qua hàm băm vào bảng băm. Xuất hiện xung đột giữa 2 phần tử k1 và k3.

Hàm băm tốt khi giá trị của nó phải có phân phối đều. Số lượng giá trị

chúng ta có thể lưu trữ với b-bits là 2b. Nếu tập S lớn và b < w thì một số

phần tử thuộc tập S sẽ xung đột với nhau khi được ánh xạ từ không gian lớn

cỡ w vào không gian nhỏ hơn là b. Ta có thể tối thiểu hóa va chạm khi chọn

được hàm băm có đầu ra phân phối đều trên b. Bởi vì nếu hàm băm không có

phân phối đều, đầu ra của chúng sẽ chỉ tập trung ánh xạ vào một số vị trí

trong bảng băm, trong khi nhiều vị trí khác lại bị bỏ trống.

2.3 Bloom Filter cơ bản

Mô hình ngôn ngữ có nguồn gốc từ Bloom Filter (BF) cơ bản [4] được

xây dựng dựa trên các cấu trúc dữ liệu dựa trên Bloom Filter. BF, trước hết là

một cấu trúc dữ liệu xác suất (PDS), hỗ trợ truy vấn kiểm tra một đối tượng

có thuộc tập hợp hay không. BF sử dụng một thuật toán mã hóa cho phép tiết

kiệm đáng kể không gian lưu trữ, thời gian truy vấn gần như giữ nguyên,

không phụ thuộc vào kích cỡ của tập cần đại diện và có tỉ lệ lỗi-một-phía điều

h k1 x ( k )

m bits

h k2 ( x k )

h k3 ( x k )

khiển được.

x k

1 0 1 0 0 1 0 1 1 0 1

Hình 5: Huấn luyện Bloom Filter

Một BF đại diện cho một tập S = với n phần tử được lấy

ngẫu nhiên từ tập ban đầu U cỡ N. Bộ nhớ BF sử dụng là một mảng bit cỡ m.

Trước quá trình huấn luyện, mảng này chỉ chứa các giá trị 0. Để huấn luyện

BF, chúng ta sử dụng k hàm băm độc lập, mỗi hàm băm có đầu ra trỏ đến một

vị trí trong mảng bit m tùy theo giá trị đầu vào . Mỗi

phần tử x trong tập S cỡ n chúng ta đang cần biểu diễn được băm k lần sử

dụng k hàm băm nêu trên, và bit tương ứng với đầu ra của mỗi hàm băm trong

bảng m được thiết lập giá trị bằng 1. Như vậy là với mỗi phần tử vị trí

tương ứng được “bật lên”, nếu một bit hk nào đó đã có giá trị bằng 1 rồi thì

bit đó vẫn giữ nguyên trạng thái. Nghĩa là, một khi đã được thiết lập, giá trị

này sẽ không bị thay đổi nữa qua cả quá trình huấn luyện. Cần lưu ý rằng có

thể tồn tại khả năng k hàm băm của một phần tử có đầu ra không trỏ đến k vị

trí riêng biệt trong mảng bit, BF không tránh sự va chạm này. Các bit trong

mảng do cơ chế này mà có thể được chia sẻ cho các phần tử dùng chung, đem

lại khả năng tiết kiệm đáng kể bộ nhớ cho BF, tuy nhiên lại tồn tại một xác

suất lỗi false positive khác 0.

Hình 6: Truy vấn Bloom Filter

Chúng ta lại đưa nó chạy qua k hàm băm trên để kiểm tra một phần tử

nào đó có thuộc tập đã được mã hóa trong BF hay không. Khi tất cả các bit

được tham chiếu bởi k hàm băm có giá trị bằng 1 thì ta coi phần tử đó thuộc

tập hợp; còn nếu tồn tại bất cứ giá trị nào bằng 0 thì chúng ta biết chắc chắn

nó không thuộc tập hợp. Tại sao ở đây cần phải nhấn mạnh từ “coi” và “chắc

chắn” ? Đó là vì các phần tử thực sự của tập S thì luôn được xác định chính

xác, nhưng có một xác suất lỗi false positive sẽ xuất hiện nếu như k bit tương

ứng thực ra được thiết lập do các phần tử trong tập huấn luyện mà phần tử

đang xét thì không thuộc tập này. Đây được gọi là lỗi một phía.

Sử dụng Bloom Filter thay vì thực sự lưu trữ tập S, thực chất chúng ta

chỉ đang lưu trữ một đại diện của nó - B, một mảng bit cỡ m. Các phần tử

trong S thực chất bị mất: Bloom Filter không thể giúp chúng ta khôi phục

được tập đó. Nhưng nếu vấn đề chúng ta quan tâm đến là liệu một phần tử có

nằm trong tập S hay không thì Bloom Filter lại có thể thực hiện được, đồng

thời tiết kiệm một lượng lớn bộ nhớ trong khi tốc độ truy vấn là bất biến.

Mặc dù không thể tránh khỏi, tuy nhiên lỗi một phía của Bloom Filter

lại là yếu tố mà ta có thể kiểm soát được, đó cũng là một ưu điểm đáng chú ý

h k1 x ( k )

m bits

h k2 ( x k )

h k3 ( x k )

nữa của Bloom Filter.

x k k x S S xk Nhưng HIT

1 0 1 0 0 1 0 1 1 0 1

Hình 7: Lỗi một phía trong Bloom Filter

Nếu chúng ta coi các hàm băm có phân phối đều và hoàn toàn ngẫu

nhiên, tức là chúng sẽ chọn các vị trí trong mảng m-bit với xác suất tương

đương nhau thì xác suất một bit bất kỳ được thiết lập bằng 1 bởi một hàm

băm là 1/m. Xác suất một bit bất kỳ không phải là 1 sau khi thực hiện một

hàm băm là:

Sau khi mới chỉ có một phần tử chạy qua k hàm băm xác suất một bit

vẫn là 0:

Sau quá trình huấn luyện xác suất một bit vẫn là 0:

Xác suất một bit xác định nào đó có giá trị bằng 1 sau quá trình huấn

luyện là:

Biểu đồ 1: Tỉ lệ lỗi và Không gian lưu trữ (giữ nguyên n)

Biểu đồ 2: Tỉ lệ lỗi và Số lượng khóa (giữ nguyên m)

Nếu một phần tử nào đó không phải là thành viên của tập S, xác suất nó

lúc nào cũng trỏ tới những bit bằng 1 đối với tất cả k hàm băm nó được chạy

qua, gây ra lỗi false positive là:

Sử dụng giới hạn của cơ số logarit tự nhiên, công thức trên tương đương:

Để xác suất lỗi là nhỏ nhất, từ công thức trên ta lấy đạo hàm thì sẽ tính

được số hàm băm k tối ưu là:

nghĩa là một nửa số bit của mảng BF nên được thiết lập giá trị bằng 1 sau quá

trình huấn luyện. Điều này sẽ dẫn đến xác suất lỗi false positive là:

Vậy nếu giữ nguyên n, xác suất lỗi giảm khi m tăng (sử dụng nhiều

không gian lưu trữ hơn). Còn nếu m không đổi thì tỉ lệ lỗi tăng nếu n tăng.

Biểu đồ 1 và 2 có thể chỉ ra sự tương quan giữa tỉ lệ lỗi với không gian lưu

trữ, và số lượng khóa (số phần tử trong tập S).

Cấu trúc của Bloom Filter không cho phép liệt kê hoặc lấy giá trị các

phần tử lưu trong đó một cách trực tiếp. Ta cũng không thể loại bỏ một đối

tượng khỏi Bloom Filter mà không làm hỏng các phần tử khác. Thế nhưng BF

vẫn là một trong những cấu trúc dữ liệu xác suất được sử dụng rộng rãi trong

NLP do sự đơn giản và hiệu quả của nó. Các ứng dụng của BF có thể kể đến

như trong kiểm tra chính tả, các ứng dụng cơ sở dữ liệu [12] và định tuyến

mạng [6].

2.4 Mô hình ngôn ngữ Bloom Filter

Phương pháp sử dụng một cấu trúc lưu trữ dữ liệu có mất mát như BF

để mô hình ngôn ngữ được giới thiệu vào năm 2007 bởi David Talbot và

Miles Osborne (School of Informatics, University of Edinburgh 2 Buccleuch

Place, Edinburgh, EH8 9LW, UK), họ cũng đưa ra ý tưởng giúp giảm tỉ lệ lỗi

false positive, tích hợp khóa và giá trị trong Bloom Filter với việc công bố hai

cấu trúc dữ liệu Log Frequency Bloom Filter và Bloom Map.

2.4.1 Bloom Filter tần số log (Log-frequency Bloom Filter)

Một thuật toán có tên mã hóa tần số log (log-frequency encoding) được

sử dụng để biến BF thành một cấu trúc dữ liệu hỗ trợ lưu trữ cặp khóa - giá

trị, với khóa là n-gram còn giá trị là số lần xuất hiện n-gram trong ngữ liệu,

nhằm tối thiểu hóa số bit cần sử dụng. Số lần xuất hiện của các n-gram c(x)

trước tiên được lượng tử hóa thành qc(x) sử dụng công thức:

Tần suất xuất hiện của các n-gram sẽ bị suy giảm theo hàm mũ khi sử

dụng quy trình mã hóa tần số log. Tuy nhiên do có sự khác biệt lớn trong phân

phối của các sự kiện này nên tỉ lệ của mô hình vẫn được lưu giữ gần như

nguyên vẹn trong BFLM. Kích thước khoảng giá trị qc(x) được quyết định bởi

cơ số b trong công thức trên.

Từng n-gram được lưu trữ vào trong BF cùng với giá trị qc(x) được

biểu diễn bằng một số nguyên j tăng từ 1 đến qc(x). Đến giai đoạn kiểm tra,

tần suất của một n-gram được lấy ra bằng cách đếm tăng dần lên bắt đầu từ 1.

Với mỗi loạt k hàm băm có kết quả trỏ tới các giá trị bằng 1 trong mảng bit

BF, giá trị của n-gram lại được tăng thêm 1 đơn vị. Quá trình này tiếp diễn

cho đến khi một hàm băm nào đó trỏ đến bit 0 trong mảng hoặc đạt đến giá trị

đếm tối đa. Và khi đó giá trị đếm hiện tại trừ đi một được trả lại, chính là cận

trên của qc(x) n-gram đó. Đối với hầu hết các n-gram thì quá trình này chỉ

diễn ra một hoặc hai lần nhờ có quy trình mã hóa tần số log. Đặc tính lỗi-một-

phía của Bloom Filter đảm bảo rằng giá trị lượng tử hóa qc(x) không thể lớn

hơn giá trị được trả lại này. Quá trình huấn luyện và kiểm tra được minh họa

qua Thuật toán 1 và Thuật toán 2.

Thuật toán 1: Thuật toán huấn luyện BF

- Đầu vào: key/frequency pair x, f (x); Bloom filter B; Hàm băm

- Đầu ra: Bloom filter B

while while i ≤ k do

end while

Thuật toán 2: Thuật toán kiểm tra BF

- Đầu vào: x ∈ U; Bloom filter B; Hàm băm

- Đầu ra: Ước tính tần số F (x)

while do

while i ≤ k do

if then

return

else

return

end if

end while

Số lần xuất hiện của n-gram sau đó được ước lượng sử dụng công thức:

tiếp theo một thuật toán làm mịn sẽ được sử dụng để lấy ra lượng xác suất

thực tế sẽ sử dụng trong tính toán.

2.4.2 Bộ lọc dựa vào chuỗi con (sub-sequence filtering)

Xác suất điều kiện của n-gram trong một ngữ cảnh cụ thể được các mô

hình ngôn ngữ n-gram chuẩn lưu trữ. Phần lớn những mô hình ngôn ngữ này

sử dụng một số phương pháp nội suy để kết hợp xác suất điều kiện của n-

gram đang xét với xác suất n-gram bậc thấp hơn. Phụ thuộc vào phương pháp

làm mịn được sử dụng, có thể chúng ta còn cần đến các thông số thống kê phụ

cho từng n-gram như số lượng hậu tố (đối với làm mịn WittenBell, Kneser-

Ney) hay tiền tố ngữ cảnh (đối với làm mịn Kneser-Ney, Stupid Backoff).

Chúng ta có thể sử dụng một BF duy nhất để lưu trữ những số liệu

thống kê này nhưng cần chỉ rõ loại của chúng (tần suất xuất hiện thô, số tiền

tố, số hậu tố, …), bằng cách sử dụng các tập k hàm băm khác nhau cho từng

loại.

Cần thiết phải lưu trữ các dữ liệu thống kê này một cách trực tiếp vào

BF, thay vì lưu các xác suất được tính toán sẵn bởi vì sử dụng dữ liệu thống

kê ngữ liệu trực tiếp, chúng ta có thể tiết kiệm cả không gian lưu trữ đồng thời

giảm tỉ lệ lỗi nhờ sử dụng các thông tin trung gian khác được kết xuất từ ngữ

liệu.

Khi phân tích tỉ lệ lỗi ở phần trên chỉ tập trung vào lỗi false positive

của BF. Tuy nhiên trong thực tế, không giống như các cấu trúc dữ liệu thông

thường khác, độ chính xác của mô hình BF còn phụ thuộc vào các yếu tố khác

trong hệ thống và cách thức mô hình được truy vấn.

Ta có thể tận dụng tính đơn điệu của không gian sự kiện n-gram trong

ngữ liệu ngôn ngữ tự nhiên để thiết lập một cận trên cho tần suất của tất cả

các n-gram này. Nhờ vậy mà có thể giảm bớt số lần thực hiện vòng lặp lớn

trong thuật toán kiểm tra (Thuật toán 2). Cụ thể, khi đã lưu trữ các n-gram bậc

thấp hơn trong BF, ta có thể nói rằng một n-gram không thể tồn tại nếu có bất

kỳ chuỗi con nào của nó không tồn tại, ý tưởng này được gọi là bộ lọc dựa

vào chuỗi con. Do quy trình lưu trữ tần suất BF sử dụng không bao giờ đánh

giá thấp tần suất của một sự kiện nên tần suất của một n-gram không thể lớn

hơn tần suất của chuỗi con ít xảy ra nhất của nó.

Với phương pháp làm mịn nội suy bộ lọc này giảm tỉ lệ lỗi của các mô

hình ngôn ngữ BF bằng cách sử dụng giá trị nhỏ nhất được trả lại bởi các mô

hình bậc thấp làm cận trên cho các mô hình cấp cao hơn.

CHƯƠNG 3

ỨNG DỤNG BLOOM FILTER CHO HỆ DỊCH MÁY THỐNG KÊ DỰA

VÀO CỤM TỪ

3.1 Hệ dịch máy thống kê mã nguồn mở Moses

Moses là hệ dịch máy thống kê cho phép người dùng dễ dàng tạo ra mô hình dịch cho bất cứ một cặp ngôn ngữ nào. Moses cung cấp cả hai loại mô hình dịch là dựa trên cụm và dựa trên cây. Bộ công cụ Moses (Moses Toolkit) là một bộ nghiên cứu dịch học thuật đầy đủ. Nó bao gồm đầy đủ các thành phần để tiền xử lý dữ liệu, huấn luyện mô hình ngôn ngữ và mô hình dịch. Nó cũng bao gồm các công cụ tuning cho các mô hình này sử dụng huấn luyện với lỗi tối thiểu và đánh giá kết quả dịch sử dụng điểm BLEU. Moses sử dụng các chuẩn công cụ ngoài cho một số công việc để tránh sự trùng lặp, như GIZA++[8](Och, et al., 2003) cho gióng hàng từ và SRILM cho mô hình hóa ngôn ngữ.

Moses sử dụng các chuẩn công cụ ngoài với một số công việc để tránh sự trùng lặp, như GIZA++ cho gióng hàng từ và SRILM cho mô hình hóa ngôn ngữ. Đồng thời, bởi các tác vụ thường tốn CPU, bộ công cụ được thiết kế để làm việc với Sun Grid Engine trong môi trường song song để tăng hiệu quả đầu ra.

Bộ công cụ được lưu trữ và phát triển trên sourceforge.net từ khi tạo ra. Moses có một cộng đồng nghiên cứu đang hoạt động . (Tải về tại: http://sourceforge.net/projects/mosesdecoder/).

Các thử nghiệm trình bày trong luận văn này đều được thực hiện trên

• CPU: Intel(R) Core(TM) i3 – 3110M 2.40GHz RAM: 4GB DDR2

• Hệ điều hành: Ubuntu 12.04 64-bit

cùng một máy tính cấu hình như sau:

Trong chương này, chúng tôi trình bày thử nghiệm xây dựng các mô hình

ngôn ngữ với hai công cụ RandLM và SRILM.

3.2 Tích hợp Mô hình ngôn ngữ Bloom Filter vào hệ thống Moses

Mô hình ngôn ngữ sử dụng trong huấn luyện là mô hình 3-gram và sử

dụng thuật toán làm mịn Kneser-Ney cải tiến. GIZA++ 2.0 1 , SRILM và bộ

huấn luyện cực tiểu hóa tỉ lệ lỗi (Minimum Error Rate Training – MERT) để

gióng hàng các từ, xây dựng mô hình ngôn ngữ, tối ưu hóa các tham số sử

dụng trong quá trình dịch được tôi sử dụng trong quá trình xây dựng hệ thống

dịch.

Một số script hỗ trợ 2 được tôi sử dụng khi xây dựng và thử nghiệm

 Bộ tách từ tokenizer.perl

 Script chuyển toàn bộ văn bản sang chữ thường lowercase.perl

 SGML-Wrapper có nhiệm vụ đóng gói dữ liệu theo định dạng XML

trên hệ thống dịch này gồm:

 Script NIST MTeval version 11b mteval-v11b.pl dùng để tính điểm

của hệ thống tính điểm NIST BLEU : wrap-xml.perl

BLEU

 Các mô hình ngôn ngữ BF-LM được xây dựng với công cụ mã nguồn

3.2.1 Xây dựng LM với RandLM và SRILM

mở RandLM3. Công cụ này được phát triển để xây dựng LM dung lượng thấp

nhờ sử dụng các cấu trúc dữ liệu xác suất, điển hình là Bloom Filter. Sau khi

biên dịch, công cụ này tạo ra hai file thực thi là buildlm và querylm. File

2 Download từ http://www.statmt.org/wmt08/scripts.tgz Script MTeval: ftp://jaguar.ncsl.nist.gov/mt/resources/mteval-v11b.pl 3 Mã nguồn RandLM có thể được download miễn phí từ:

http://sourceforge.net/projects/randlm/

5 Tài liệu hƣớng dẫn và mã nguồn của SRILM có thể đƣợc download miễn phí

từ: http://www.speech.sri.com/projects/srilm/

1 http://code.google.com/p/giza-pp/

buildlm được dùng để xây dựng các mô hình ngôn ngữ. Còn file querylm sử

dụng để truy vấn LM, trả lại kết quả thống kê n-gram hoặc xác suất điều kiện

 Các mô hình ngôn ngữ chuẩn, không mất mát được xây dựng sử dụng

log.

SRI Language Modelling Toolkit (SRILM) 5. SRILM là một dự án mã nguồn

mở bao gồm nhiều chương trình, thư viện C++ và script hỗ trợ trong việc xây

dựng và thử nghiệm các mô hình ngôn ngữ cho nhận dạng tiếng nói hoặc các

ứng dụng khác. Nó hỗ trợ nhiều kiểu mô hình ngôn ngữ khác nhau dựa trên

thống kê về n-gram. SRILM đã được phát triển từ năm 1995 ở Phòng nghiên

cứu công nghệ tiếng nói SRI, và vẫn còn đang được tiếp tục sửa chữa, mở

rộng bởi nhiều nhà nghiên cứu trong cộng đồng NLP.

3.2.1.1 Ngữ liệu

Thử nghiệm này được thực hiện trên bộ ngữ liệu đơn ngữ Tiếng Việt được

sưu tầm từ các bài báo, tạp chí. Các thống kê về ngữ liệu này được liệt kê

trong bảng dưới đây:

Bảng 1: Thống kê về ngữ liệu Tiếng Việt

Thống kê chung

Dung lượng Số lượng câu Số lượng từ Độ dài trung bình câu 131.9 MB 842,452 16,369,034 19.43

Thống kê n-gram

315,095 3,342,615 1,784,125 1,441,396 1-gram 2-gram 3-gram 4-gram

Do hạn chế về thời gian thử nghiệm, vì thế trong khuôn khổ luận văn

chỉ thực hiện thử nghiệm trên bộ ngữ liệu này (bộ ngữ liệu lớn nhất được sử

dụng trong thử nghiệm là bộ ngữ liệu 842,452 câu dịch). Toàn bộ ngữ liệu

được chuyển thành chữ thường sử dụng script lowercase.perl.

Ngữ liệu đầu vào là tệp tin đơn ngữ của ngôn ngữ đích - tiếng Việt. Ví

dụ: tệp tin 50001b_train.vn.1, có nội dung như sau:

50001b_train.vn.1

- Cảnh sát cố giải tán đám đông.

- Những người biểu tình cho biết WTO không công

bằng đối với nông dân và ngư dân của các nước

nghèo.

- Họ cho rằng các chính sách thương mại của tổ

chức này sẽ làm tổn hại điều kiện sinh sống.

- Một điều tra viên của Châu âu cho biết dường

như có bằng chứng là cơ quan tình báo trung ương

Mỹ đã bắt cóc người ở Châu âu.

- Thượng nghị sĩ Thụy sĩ Dick Marty cũng cho

biết bằng chứng này dường như cho thấy cia đã

chuyển những người bị bắt cóc từ nước này sang

nước kia một cách bất hợp pháp.

.....

Ngữ liệu này cần được tiền xử lý (prepare data): phân tích từ tố, tắt chữ

hoa ở đầu câu, và tách từ cho file tiếng Việt. Để làm việc này ta sử dụng 2

script đó là: tokenizer.perl và lowercase.perl. Ta thực hiện các lệnh sau:

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/tokenizer.perl -l fr

<~/tools/Work/50001_utf8/Baseline/data/50001b_train.

vn.1 >

~/tools/Work/50001_utf8/Baseline/data/50001b_train.t

ok.vn

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/lowercase.perl <

~/tools/Work/50001_utf8/Baseline/data/50001b_train.t

ok.vn >

~/tools/Work/50001_utf8/Baseline/data/50001b_train.l

ower.vn

Tệp tin kết quả có nội dung như sau:

50001b_train.lower.vn

- cảnh _ sát cố giải _ tán đám _ đông .

- những người _ biểu _ tình cho biết wto không _

công bằng đối _ với nông _ dân và ngư _ dân của

các nước nghèo.

- họ cho rằng các chính _ sách thương _ mại của

tổ _ chức này sẽ làm _ tổn _ hại điều _ kiện

sinh _ sống .

- một điều _ tra viên của châu âu cho biết dường

_ như có bằng _ chứng là cơ _ quan _ tình _ báo

_ trung _ ương _ mỹ đã bắt _ cóc người _ ở châu

âu.

- thượng _ nghị _ sĩ thụy _ sĩ _ dick _ marty

cũng cho biết bằng _ chứng này dường _ như cho _

thấy cia đã chuyển những người _ bị _ bắt cóc từ

nước này sang nước kia một _ cách bất _ hợp _

pháp .

.....

Các tập ngữ liệu đã được trích xuất và tiền xử lý ở trên được sử dụng

để huấn luyện các mô hình ngôn ngữ 3-gram và 4-gram sử dụng hai bộ công

cụ SRILM và RandLM. Dung lượng các tập ngữ liệu này được thể hiện trong

Bảng 2.

Bảng 2: Thống kê các tập ngữ liệu tiếng Việt được sử dụng để xây dựng LM

(Set 1->3)

Set 1 Set 2 Set 3

Số lượng câu 442,453 642,452 842,452

Số lượng từ 7,013,558 11,894,513 16,369,034

Độ dài trung bình câu 15.85 18.51 19.43

Từ vựng 161,376 255,115 315,092

Dung lượng 56 MB 95.9 MB 131.9 MB

3.2.1.2 Thuật toán làm mịn

Mô hình ngôn ngữ không mất mát được huấn luyện sử dụng thuật toán

làm mịn Kneser-Ney cải tiến (MKN). Do trong những thử nghiệm này, chúng

ta chỉ quan tâm đến đặc tính, hiệu suất của các cấu trúc dữ liệu (không mất

mát và có mất mát thông tin) mà không cần xác suất chính xác của từng sự

kiện, nên thuật toán Stupid Backoff của Google được sử dụng trong quá trình

xây dựng BF-LM vì nó nhanh và đơn giản. Hơn nữa chất lượng của thuật toán

làm mịn Stupid Backoff đã được chứng minh là xấp xỉ với thuật toán MKN

với ngữ liệu lớn [5].

3.2.1.3. Xây dựng LM với SRILM và RandLM

Sau khi ngữ liệu được tiền xử lý, ta đi xây dựng mô hình ngôn ngữ (Build

Language Model). Để thấy rõ hiệu quả của mô hình ngôn ngữ RandLM so với

SRILM ngữ liệu được thử nghiệm ta tiến hành so sánh ngữ liệu đơn ngữ tiếng

Việt (ngôn ngữ đích).

Trước hết ta tiến hành xây dựng mô hình ngôn ngữ chuẩn. Các mô hình

ngôn ngữ chuẩn, không mất mát được xây dựng sử dụng SRI Language

Modelling Toolkit (SRILM). SRILM là một dự án mã nguồn mở bao gồm

nhiều chương trình, thư viện C++ và script hỗ trợ trong việc xây dựng và thử

nghiệm các mô hình ngôn ngữ cho nhận dạng tiếng nói hoặc các ứng dụng

khác. Nó hỗ trợ nhiều kiểu mô hình ngôn ngữ khác nhau dựa trên thống kê về

n-gram. SRILM đã được phát triển từ năm 1995 ở Phòng nghiên cứu công

nghệ tiếng nói SRI, và vẫn còn đang được tiếp tục sửa chữa, mở rộng bởi

nhiều nhà nghiên cứu trong cộng đồng NLP.

Ta sử dụng script ngram-count trong SRILM để xây dựng mô hình ngôn

ngữ, mô hình ngôn ngữ chỉ được xây dựng trên ngôn ngữ đích, ví dụ:

tranthanh@tranthanh:~$ ~/tools/srilm/bin/i686-

m64/ngram-count -order 4 -interpolate -kndiscount -

unk -text

~/tools/Work/50001_utf8/Baseline/lm/50001b_train.low

er.vn -lm

~/tools/Work/50001_utf8/Baseline/lm/5001b.srilm

Trong đó 50001b_train.lower.vn là tệp ngữ liệu đầu vào của ngôn

5001b.srilm

ngữ đích sau khi tiền xử lý, kết quả của quá trình này được lưu lại vào file

Khi thực hiện câu lệnh trên sẽ tạo ra một mô hình ngôn ngữ 4-gram

trong file 5001b.srilm từ file ngữ liệu 50001b_train.lower.vn.

Ngoài ra, ta có thể yêu cầu SRILM tạo ra những mô hình ngôn ngữ bậc cao

hơn như 5-gram, 6-gram, thậm chí lớn hơn nữa. Tuy nhiên, khi tham số này

tăng thì đồng thời kéo theo lượng bộ nhớ cần dùng cũng tăng lên rất nhanh.

SRILM sử dụng RAM để lưu trữ kết quả đếm n-gram tạm thời, với cấu hình

máy tính thử nghiệm đã nêu trên (sử dụng 4GB RAM), tôi đã xây dựng được

mô hình ngôn ngữ 4-gram từ tập ngữ liệu 131.9 MB; nhưng không tạo được

mô hình 5-gram với cùng lượng dữ liệu do thiếu RAM trong giai đoạn thống

kê n-gram. Tham số -kndiscount yêu cầu SRILM sử dụng thuật toán Kneser-

Ney cải tiến trong bước làm mịn. Cũng có thể sử dụng các thuật toán làm mịn

khác trong SRILM như Good-Turing hay Witten-Bell.

Quá trình xây dựng mô hình chiếm khoảng 1 phút cho tập ngữ liệu 56

MB (Set 1) cho đến hơn 3 phút đối với tập ngữ liệu 131.9 MB (Set 4). Ta có

thể xem có bao nhiêu n-gram mỗi bậc trong file mô hình ngôn ngữ vừa được

tạo ra sau khi xây dựng.

Bảng 4: Thống kê số lượng các n-gram trong các tập ngữ liệu

1-gram 2-gram 3-gram 4-gram

161,379 1,727,176 691,281 452,241 Set 1

255,118 2,659,220 1,194,095 854,777 Set 2

315,095 3,342,615 1,784,125 1,441,396 Set 3

File 5001b.srilm có cấu trúc như sau:

\data\

ngram 1=315095

ngram 2=3342615

ngram 3=1784125

ngram 4=1441396

\1-grams:

-2.619509 ! -1.174945

-5.019643 !' -0.1231811

-2.499407 " -0.362864

-5.180512 # -0.1231812

-5.180512 $ -0.1231812

-5.180512 $594 -0.1231812

-5.180512 $8,35 -0.1231812

-3.496327 % -0.3279912

-4.346717 & -0.1231812

-5.180512 &davis -0.1231812

-5.180512 &giữa -0.1231812

-4.922648 ' -0.1231812

-4.922648 'anh -0.1231811

-4.669695 'bạn -0.2013319

-5.180512 'bộ -0.1231812

-5.180512 'chia -0.1231811

-5.180512 'chill' -0.1231812

-5.019643 'chúng -0.2464038

-5.180512 'con -0.1231812

-5.180512 'cá -0.1231812

.....

\2-grams:

-3.702029 " anhchàng

-3.702029 " anhchị

-3.10137 " anhta

-3.236941 " anhấy

-3.741899 " annulus

-3.744986 " bannãy

-3.647394 " banđêm

-3.368595 " baogồm

-3.744986 " bigbird

-3.715676 " biểutượng

-3.734566 " blackfriday

-3.204183 " bongbóng -0.1929192

-7.111882 "D" -0.1273738

-7.111882 "DOS -0.1273738

-7.111882 "Danh -0.1273738

-7.111882 "De -0.1273738

-7.111882 "Debra" -0.1273738

-7.111882 "Dumbo" -0.1273738

-7.111882 "Dân -0.1273738.....

\3-grams:

-0.2644063 anh ) .

-1.433459 bà ) ,

-0.7637519 bà ) .

-1.476914 bà ) bị

-1.521228 bà ) có

-1.155089 bà ) cóthể

-1.413331 bà ) cần

-1.889307 bà ) dùng

-2.105258 bà ) giấychứngnhận

-2.435822 bà ) khoẻmạnh

-1.458335 bà ) không

-1.890747 bà ) khôngcần

-2.104658 bà ) khôngnên

-1.554726 bà ) khôngđược

-1.733998 bà ) là

-2.436294 bà ) mấtsức

-2.054061 bà ) một

-2.414719 bà ) nghỉviệc

-0.9841987 bà ) phải

-0.8705663 bà ) sẽ

-1.890674 bà ) ta

-2.156 bà ) trong

-1.959944 bà ) và

-2.432107 bà ) ăn

-0.2726102 bàn ) .

-0.5362333 bánhàng ) ,

......

\end\

Tiếp theo ta tiến hành xây dưng mô hình ngôn ngữ Bloom Filter. Để

xây dựng mô hình ngôn ngữ Bloom Filter ta sử dụng RandLM, có thể được

thực hiện theo 3 cách:

i) Từ ngữ liệu đã được chia từ sẵn;

ii) Từ một tập các cặp n-gram và số lần xuất hiện của nó (cặp ngram-

count);

iii) Từ một mô hình ngôn ngữ backoff đã được xây dựng trước đó với

định dạng ARPA (định dạng của mô hình ngôn ngữ được tạo ra từ SRILM).

Khi xây dựng theo cách đầu tiên hoặc thứ hai, mô hình được gọi là

CountRandLM, sử dụng loại thứ ba thì được gọi là BackoffRandLM.

CountRandLM có thể sử dụng làm mịn StupidBackoff hoặc Witten-Bell.

BackoffRandLM có thể sử dụng bất kỳ phương pháp làm mịn nào mà SRILM

hỗ trợ. Ví dụ ta xây dựng BloomMap-LM 4-gram từ tập ngữ liệu 131.9 MB

sử dụng lệnh sau:

tranthanh@tranthanh:~$~/tools/Work/corpus$

~/tools/randlm-0.2.5/bin/buildlm –struct BloomMap –

falsepos 8 –values 8 –output-prefix randlm_4-

grams_131.9MB –input-path /corpus/news.lowercased.gz

 Tham số -falsepos quyết định tỉ lệ lỗi false positive của cấu trúc dữ

–order 4 –working-mem 1500

 Tham số values quyết định khoảng lượng tử hóa của mô hình, bậc của

liệu, ví dụ falsepos 8 cho ta tỉ lệ lỗi là 1/28.

logarit sử dụng trong quá trình lượng tử hóa sẽ là 21/values nếu ta sử dụng

 Tham số order xác định bậc của mô hình n-gram.

 Tham số input-path: đường dẫn tới ngữ liệu được dùng để tạo LM.

 Đặc biệt tham số -struct quyết định cấu trúc dữ liệu được sử dụng để

tham số -values 8.

xây dựng mô hình ngôn ngữ. Hiện tại, RandLM hỗ trợ hai loại cấu trúc

dữ liệu là Log-Frequency Bloom Filter (-struct LogFreqBloomFilter)

và Bloom Map (-struct BloomMap). Sử dụng RandLM, chúng tôi sẽ

xây dựng các mô hình ngôn ngữ với cả hai loại cấu trúc dữ liệu này để

 Tham số “-working-mem 1500” có nghĩa là cho phép sử dụng 1500MB

so sánh kích thước cũng như hiệu quả của từng cấu trúc dữ liệu.

trong quá trình sắp xếp các n-gram.

- randlm_4-grams_131.9MB.BloomMap

Sau quá trình xây dựng LM với câu lệnh trên các file được tạo ra gồm:

Mô hình

- randlm_4-grams_131.9MB.counts.sorted.gz Thống

ngôn ngữ

- randlm_4-grams_131.9MB.stats.gz

kê n-gram

Thống kê

- randlm_4-grams_131.9MB.vcb.gz

kết quả đếm

File chứa

từ vựng

Trong đó, hai file .stats.gz và .counts.sorted.gz đều có thể được khai báo

sử dụng lại, không cần thiết phải tính toán nhiều lần khi xây dựng thêm LM từ

bộ ngữ liệu giống nhau. Trong thử nghiệm nhiều khi cần xây dựng LM nhiều

lần với giá trị các tham số khác nhau điều này là rất cần thiết, ví dụ:

tranthanh@tranthanh:~$~/buildlm –struct BloomMap –

falsepos 8 –values 10 –order 4 –output-prefix

randlm_4-grams_131.9MB_values10 –input-path

randlm_4-grams_131.9MB.counts.sorted.gz -input-type

counts -stats-path randlm_4-grams_131.9MB.stats.gz

–working-mem 1500

sẽ xây dựng một BloomMap-LM mới từ cùng ngữ liệu đã sử dụng trước đó

nhưng với giá trị lượng tử hóa khác (–values 10) mà không cần tính toán lại

các file thống kê.

Khi xây dựng các BF-LM sử dụng RandLM sẽ chiếm thời gian lâu hơn

với cùng lượng dữ liệu trong SRILM; mất xấp xỉ 6 phút RandLM mới xây

dựng xong mô hình ngôn ngữ 4-gram với 131.9 MB ngữ liệu (Set 3).

RandLM sử dụng đĩa cứng để lưu trữ, vì thế việc thống kê, sắp xếp cũng mất

nhiều thời gian hơn. Tuy nhiên, RandLM lại có thể xây dựng các mô hình

ngôn ngữ bậc cao hơn, sử dụng nhiều dữ liệu hơn SRILM. Ví dụ, trên máy

tính thử nghiệm, RandLM đã có thể xây dựng thành công mô hình ngôn ngữ

5-gram từ 131,9 MB ngữ liệu huấn luyện, trong khi SRILM thì không thể.

Với thời gian huấn luyện của RandLM lâu hơn SRILM nhưng đó không phải

là vấn đề lớn, vì ta chỉ cần xây dựng mô hình ngôn ngữ một lần duy nhất. Hơn

nữa, dung lượng các mô hình ngôn ngữ Bloom Filter xây dựng từ RandLM sử

dụng ít bộ nhớ hơn các mô hình chuẩn từ SRILM rất nhiều. Bảng 5 thống kê

dung lượng các mô hình ngôn ngữ 4-gram tạo bởi hai công cụ này (không

nén) với các bộ ngữ liệu kích thước khác nhau.

Bảng 5: Kích thước các loại LM khác nhau trên các tập ngữ liệu

Set 1 Set 2 Set 3

21.21 MB 32.73 MB 45.28 MB Log-Freq BF

97.3 MB 164 MB 235 MB SRILM

Qua bảng trên ta có thể thấy rằng dung lượng các mô hình ngôn

ngữ tạo bởi RandLM chỉ bằng khoảng 1/5 lần dung lượng mô hình ngôn ngữ

chuẩn tạo bởi SRILM nếu sử dụng cấu trúc dữ liệu Log-Frequency Bloom

Filter.

Biểu đồ 1: Dung lượng các LM tạo từ RandLM và SRILM

Từ Biểu đồ 1, có thể kết luận rằng càng sử dụng nhiều dữ liệu huấn

luyện, thì càng tiết kiệm được không gian lưu trữ; nghĩa là tỉ lệ chênh lệch

giữa dung lượng LM chuẩn và mô hình xây dựng bằng công cụ RandLM tạo

ra từ cùng một ngữ liệu huấn luyện càng tăng. Bằng các thực nghiệm ta có thể

biết được rằng việc tiết kiệm dung lượng này làm hiệu quả LM giảm như thế

nào so với LM chuẩn.

Kết quả xây dựng LM bậc 2, 3 và 4 từ bộ ngữ liệu tiếng Việt được thể

hiện trong biểu đồ dưới đây:

Biểu đồ 2: Dung lượng các LM tiếng Việt

Các LM này được xây dựng với bậc n-gram khác nhau, từ 2-gram cho

đến 4-gram. Kết quả thể hiện trong biểu đồ một lần nữa cho thấy sự chênh

lệch lớn về dung lượng giữa các mô hình ngôn ngữ SRILM chuẩn và

RandLM.

Các mô hình được xây dựng ở trên sẽ được dùng trong dịch máy thống

kê sử dụng hệ thống dịch máy mã nguồn mở Moses. Kết quả dịch sau đó

được đánh giá bằng điểm BLEU. Qua đó ta có thể so sánh hiệu quả của mô

hình ngôn ngữ sử dụng Bloom Filter với mô hình ngôn ngữ chuẩn truyền

thống.

3.3 Thử nghiệm và đánh giá

Hệ thống dịch được thử nghiệm với các mô hình ngôn ngữ SRILM và

RandLM, với việc dịch 1000 câu tiếng Anh. Quá trình thử nghiệm được tiến

hành như sau:

3.3.1 Chuẩn bị ngữ liệu

Ngữ liệu đầu vào là cặp ngữ liệu song ngữ với 44,638 câu Anh – Việt.

Để chuẩn hoá dữ liệu ta thực hiện các lệnh sau:

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/tokenizer.perl -l en

<~/tools/Work/50001_utf8/Baseline/data/t_train.en.1

~/tools/Work/50001_utf8/Baseline/data/t_train.tok.en

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/tokenizer.perl -l fr

<~/tools/Work/50001_utf8/Baseline/data/t_train.vn.1

~/tools/Work/50001_utf8/Baseline/data/t_train.tok.vn

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/lowercase.perl <

~/tools/Work/50001_utf8/Baseline/data/t_train.tok.vn

~/tools/Work/50001_utf8/Baseline/data/t_train.lower.

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/lowercase.perl <

~/tools/Work/50001_utf8/Baseline/data/t_train.tok.en

~/tools/Work/50001_utf8/Baseline/data/t_train.lower.

3.3.2 Huấn luyện mô hình ngôn ngữ

- Với mô hình ngôn ngữ chuẩn ta thực hiện các lệnh sau:

tranthanh@tranthanh:~$ ~/tools/srilm/bin/i686-

m64/ngram-count -order 3 -interpolate -kndiscount -

unk -text

~/tools/Work/50001_utf8/Baseline/lm/t_train.lower.vn

-lm ~/tools/Work/50001_utf8/Baseline/lm/t.srilm

- Với mô hình ngôn ngữ Bloom Filter ta thực hiện các lệnh sau:

tranthanh@tranthanh:~$~/tools/Work/corpus$

~/tools/randlm-0.2.5/bin/buildlm -struct BloomMap -

falsepos 8 -values 8 -output-prefix model -order 3 <

~/tools/Work/corpus/t_train.lower.vn

3.3.3 Sinh bảng cụm từ

- Với mô hình ngôn ngữ chuẩn sinh ra ở trên, sinh bảng cụm từ được thực

hiện bởi các lệnh sau (quá trình này chiếm khoảng 40 phút):

tranthanh@tranthanh:~$

~/tools/Work/50001_utf8/Baseline$ nohup nice

~/tools/moses/scripts/training/train-model.perl -

root-dir ~/tools/Work/50001_utf8/Baseline -corpus

~/tools/Work/50001_utf8/Baseline/data/t_train.lower

\-f en -e vn -alignment grow-diag-final-and -

reordering msd-bidirectional-fe \-lm

0:3:/home/tranthanh/tools/Work/50001_utf8/Baseline/l

m/t.srilm:8 -external-bin-dir ~/tools/bin >&

~/tools/Work/50001_utf8/Baseline/training.out &

Tiếp theo ta tiến hành thực hiện các lệnh:

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/tokenizer.perl -l en

<~/tools/Work/50001_utf8/Baseline/data/t_dev.en.1 >

~/tools/Work/50001_utf8/Baseline/data/t_dev.tok.en

tranthanh@tranthanh:~$

~/tools/Work/50001_utf8/Baseline$

~/tools/moses/scripts/tokenizer/tokenizer.perl -l en

<~/tools/Work/50001_utf8/Baseline/data/t_dev.vn.1 >

~/tools/Work/50001_utf8/Baseline/data/t_dev.tok.vn

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/lowercase.perl <

~/tools/Work/50001_utf8/Baseline/data/t_dev.tok.vn >

~/tools/Work/50001_utf8/Baseline/data/t_dev.lower.vn

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/lowercase.perl <

~/tools/Work/50001_utf8/Baseline/data/t_dev.tok.en >

~/tools/Work/50001_utf8/Baseline/data/t_dev.lower.en

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/tokenizer.perl -l fr

< ~/tools/Work/50001_utf8/Baseline/data/t_test.vn.1

~/tools/Work/50001_utf8/Baseline/data/t_test.tok.vn

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/tokenizer.perl -l en

< ~/tools/Work/50001_utf8/Baseline/data/t_test.en.1

~/tools/Work/50001_utf8/Baseline/data/t_test.tok.en

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/lowercase.perl <

~/tools/Work/50001_utf8/Baseline/data/t_test.tok.en

~/tools/Work/50001_utf8/Baseline/data/t_test.lower.e

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/lowercase.perl <

~/tools/Work/50001_utf8/Baseline/data/t_test.tok.vn

~/tools/Work/50001_utf8/Baseline/data/t_test.lower.v

- Với mô hình ngôn ngữ Bloom Filter sinh ra ở trên, sinh bảng cụm từ được

thực hiện bởi các lệnh sau:

tranthanh@tranthanh:~$

~/tools/Work/50001_utf8/Baseline$ nohup nice

~/tools/moses/scripts/training/train-model.perl -

root-dir ~/tools/Work/50001_utf8/Baseline -corpus

~/tools/Work/50001_utf8/Baseline/data/t_train.lower

\-f en -e vn -alignment grow-diag-final-and -

reordering msd-bidirectional-fe \-lm

0:3:/home/tranthanh/tools/Work/50001_utf8/Baseline/l

m/model.BloomMap:8 -external-bin-dir ~/tools/bin >&

~/tools/Work/50001_utf8/Baseline/training.out &

Sau đó ta thực hiện các lệnh:

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/tokenizer.perl -l en

<~/tools/Work/50001_utf8/Baseline/data/t_dev.en.1 >

~/tools/Work/50001_utf8/Baseline/data/t_dev.tok.en

tranthanh@tranthanh:~$

~/tools/Work/50001_utf8/Baseline$

~/tools/moses/scripts/tokenizer/tokenizer.perl -l en

<~/tools/Work/50001_utf8/Baseline/data/t_dev.vn.1 >

~/tools/Work/50001_utf8/Baseline/data/t_dev.tok.vn

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/lowercase.perl <

~/tools/Work/50001_utf8/Baseline/data/t_dev.tok.vn >

~/tools/Work/50001_utf8/Baseline/data/t_dev.lower.vn

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/lowercase.perl <

~/tools/Work/50001_utf8/Baseline/data/t_dev.tok.en >

~/tools/Work/50001_utf8/Baseline/data/t_dev.lower.en

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/tokenizer.perl -l fr

< ~/tools/Work/50001_utf8/Baseline/data/t_test.vn.1

~/tools/Work/50001_utf8/Baseline/data/t_test.tok.vn

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/tokenizer.perl -l en

< ~/tools/Work/50001_utf8/Baseline/data/t_test.en.1

~/tools/Work/50001_utf8/Baseline/data/t_test.tok.en

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/lowercase.perl <

~/tools/Work/50001_utf8/Baseline/data/t_test.tok.en

~/tools/Work/50001_utf8/Baseline/data/t_test.lower.e

tranthanh@tranthanh:~$

~/tools/moses/scripts/tokenizer/lowercase.perl <

~/tools/Work/50001_utf8/Baseline/data/t_test.tok.vn

~/tools/Work/50001_utf8/Baseline/data/t_test.lower.v

3.3.4 Huấn luyện các tham số của mô hình dịch máy

Ta thực hiện lệnh sau (quá trình này chiếm khoảng hơn 10 phút):

tranthanh@tranthanh:~/tools/Work/50001_utf8/Baseline

$ nohup nice ~/tools/moses/scripts/training/mert-

moses.pl

~/tools/Work/50001_utf8/Baseline/tuning/t_dev.lower.

vn ~/tools/moses/bin/moses

~/tools/Work/50001_utf8/Baseline/model/moses.ini --

mertdir ~/tools/moses/bin/ &>

~/tools/Work/50001_utf8/Baseline/tuning/mert.out &

Sau khi thực hiện lệnh trên ta tiến hành copy file moses.ini như sau:

home/tools/Work/50001_utf8/Baseline/mert-work/moses.ini

Vào:

home/tranthanh/tools/Work/50001_utf8/Baseline/tuning

Sau đó ta thực hiện các lệnh sau:

tranthanh@tranthanh:~$ ~/tools/moses/scripts/reuse-

weights.perl

~/tools/Work/50001_utf8/Baseline/tuning/moses.ini <

~/tools/Work/50001_utf8/Baseline/model/moses.ini >

~/tools/Work/50001_utf8/Baseline/tuning/moses-

tuned.ini

tranthanh@tranthanh:~$

~/tools/moses/scripts/training/filter-model-given-

input.pl

~/tools/Work/50001_utf8/Baseline/evaluation/t_test.l

ower ~/tools/Work/50001_utf8/Baseline/tuning/moses-

tuned.ini

~/tools/Work/50001_utf8/Baseline/evaluation/t_test.l

ower.en

tranthanh@tranthanh:~$

~/tools/moses/scripts/recaser/train-recaser.perl -

train-script ~/tools/moses/scripts/training/train-

model.perl -ngram-count ~/tools/srilm/bin/i686-

m64/ngram-count -corpus

~/tools/Work/50001_utf8/Baseline/data/t_test.tok.en

-dir

/home/tranthanh/tools/Work/50001_utf8/Baseline/recas

er -scripts-root-dir ~/tools/moses/scripts

- Riêng đối với hệ dịch máy thống kê Moses sử dụng mô hình ngôn ngữ

Bloom Filter ta thực hiện cấu hình lại tham số trong file moses.ini như sau:

Mở tệp moses.ini tại phần [feature] thay KENLM path=filename.arpa ….

bằng RANDLM path=filename.irstlm …

3.3.5 Dịch văn bản

Ta thực hiện các lệnh sau:

tranthanh@tranthanh:~$

~/tools/Work/50001_utf8/Baseline$ nohup nice

~/tools/moses/bin/moses -config

~/tools/Work/50001_utf8/Baseline/tuning/moses-

tuned.ini -input-file

~/tools/Work/50001_utf8/Baseline/evaluation/t_test.l

ower.en 1>

~/tools/Work/50001_utf8/Baseline/evaluation/t_test.t

uned.output 2>

~/tools/Work/50001_utf8/Baseline/evaluation/tuned.de

code.out &

tranthanh@tranthanh:~$ nohup nice

~/tools/moses/bin/moses -config

~/tools/Work/50001_utf8/Baseline/evaluation/t_test.l

ower/moses.ini -input-file

~/tools/Work/50001_utf8/Baseline/evaluation/t_test.l

ower.en 1>

~/tools/Work/50001_utf8/Baseline/evaluation/t_test.t

uned-filtered.output 2>

~/tools/Work/50001_utf8/Baseline/evaluation/tuned-

filtered.decode.out &

tranthanh@tranthanh:~$

~/tools/moses/scripts/recaser/recase.perl -model

~/tools/Work/50001_utf8/Baseline/recaser/moses.ini -

~/tools/Work/50001_utf8/Baseline/evaluation/50001_te

st.tuned-filtered.output -moses

~/tools/moses/bin/moses >

~/tools/Work/50001_utf8/Baseline/evaluation/t_test.t

uned-filtered.output.recased

tranthanh@tranthanh:~$

~/tools/moses/scripts/detokenizer.perl -l vn <

~/tools/Work/50001_utf8/Baseline/evaluation/t_test.t

uned-filtered.output.recased >

~/tools/Work/50001_utf8/Baseline/evaluation/t_test.t

uned-filtered.output.detokenized

3.3.6 Đánh giá kết quả

Ta thực hiện các lệnh:

tranthanh@tranthanh:~$

~/tools/Work/50001_utf8/Baseline/plain2sgm -r test

~/tools/Work/50001_utf8/Baseline

~/tools/Work/50001_utf8/Baseline/data/t_test.vn.1

~/tools/Work/50001_utf8/Baseline/t_test.vn.sgm

tranthanh@tranthanh:~$

~/tools/Work/50001_utf8/Baseline/plain2sgm -s test

~/tools/Work/50001_utf8/Baseline

~/tools/Work/50001_utf8/Baseline/data/t_test.en.1

~/tools/Work/50001_utf8/Baseline/t_test.en.sgm

tranthanh@tranthanh:~$

~/tools/Work/50001_utf8/Baseline/plain2sgm -t test

~/tools/Work/50001_utf8/Baseline

~/tools/Work/50001_utf8/Baseline/evaluation/t_test.t

uned-filtered.output

~/tools/Work/50001_utf8/Baseline/t_test.tuned-

filtered.output.sgm

tranthanh@tranthanh:~$

~/tools/Work/50001_utf8/Baseline/mteval-v11b.pl -r

~/tools/Work/50001_utf8/Baseline/t_test.vn.sgm -s

~/tools/Work/50001_utf8/Baseline/t_test.en.sgm -t

~/tools/Work/50001_utf8/Baseline/t_test.tuned-

filtered.output.sgm -c

Bảng 6: Thống kê ngữ liệu sử dụng trong dịch thử nghiệm

Độ dài Ngữ liệu Ngôn ngữ Câu Từ trung bình

Tiếng Anh 44,638 498,041 11.15 Ngữ liệu huấn luyện Tiếng Việt 44,638 463,795 10.39

Tiếng Anh 201 Ngữ liệu điều chỉnh 2,403 11.95

tham số Tiếng Việt 201 2,221 11.04

Tiếng Anh 500 5,620 11.24 Ngữ liệu đánh giá Tiếng Việt 500 5,264 10.52

Thời gian để dịch hết 500 câu này khi sử dụng mô hình ngôn ngữ

SRILM là 415 giây, đối với LF-BF-LM là 539 giây. Như vậy là khi sử dụng

các loại BF-LM, thời gian dịch lâu hơn khi sử dụng mô hình ngôn ngữ chuẩn

khoảng 1.3 lần. Khoảng thời gian dịch lâu hơn này không phải là tồi khi ta

xem xét đến phần bộ nhớ đã tiết kiệm được nhờ sử dụng các LM dựa trên

Bloom Filter.

Bảng 7: Thời gian dịch 500 câu tiếng Anh khi sử dụng các loại

LM khác nhau

Loại LM 3 gram Thời gian dịch (giây)

SRI-LM LF-BF-LM 415 539

Để đánh giá kết quả dịch, chúng tôi sử dụng điểm BLEU. Do đó, sau

khi dịch, kết quả được đóng gói lại theo định dạng XML của hệ thống tính

điểm NIST MT. Script MTeval sử dụng ba đầu vào để đánh giá kết quả dịch:

file chứa văn bản ở ngôn ngữ nguồn, file chứa kết quả dịch ở ngôn ngữ đích

và một file dịch chuẩn dùng để tham chiếu.

Điểm BLEU cho kết quả dịch với các LM khác nhau được thể hiện

trong bảng 8. Các mô hình ngôn ngữ này đều được xây dựng từ tập ngữ liệu

Set 3 gồm 131.9 MB ngữ liệu tiếng Việt. Nhìn vào kết quả này ta có thể thấy

rằng nếu cùng sử dụng mô hình 3-gram thì hệ thống dịch sử dụng mô hình

ngôn ngữ SRI-LM có điểm cao hơn khi sử dụng mô hình các mô hình

RandLM. Nhưng sự chênh lệch này không phải là lớn, trong trường hợp này

là SRILM cho điểm cao hơn LF-BF-LM 0,79 nên ta có thể coi các điểm số

này là tương đương nhau với cùng bậc n-gram. Thế nhưng, như đã nói ở phần

trên, với cấu hình máy tính dùng cho thử nghiệm, ta chỉ có thể xây dựng mô

hình ngôn ngữ 4-gram nếu sử dụng BF-LM. Sử dụng mô hình ngôn ngữ 4-

gram BF-LM này trong hệ thống dịch cho điểm số là 31.90, cao hơn rõ rệt khi

sử dụng mô hình ngôn ngữ SRI-LM với 30.25 điểm.

Bảng 8: Điểm BLEU cho kết quả dịch với các LM khác nhau

Cỡ LM 173 MB 35.17 MB 58.46 MB Điểm BLEU 30.25 29.46 31.90 SRI-LM 3-gram LF-BF-LM 3-gram LF-BF-LM 4-gram

Nhìn vào kết quả này, ta có thể thấy rõ ưu thế vượt trội của của cấu trúc

dữ liệu LF-BF-LM so với cấu trúc dữ liệu SRI-LM, vừa sử dụng ít bộ nhớ

hơn, vừa hiệu quả hơn.

KẾT LUẬN

Dịch máy là một trong những vấn đề khó của lĩnh vực xử lý ngôn ngữ

tự nhiên. Hiện nó vẫn là vấn đề thách thức và có nhiều công việc cần giải

quyết đối với các nhà tin học hiện nay. Hướng tiếp cận thống kê là hướng tiếp

cận dựa vào dữ liệu và được phát triển khá mạnh từ cuối thế kỉ XX cho tới

nay. Hướng tiếp cận này đã khắc phục được các nhược điểm của cách tiếp cận

dựa vào luật (dịch chuyển đổi). Qua ba chương, luận văn đã trình bày cách

tiếp cận, phương pháp giải quyết cho vấn đề dịch máy bằng thống kê và đồng

thời cải tiến về mô hình ngôn ngữ của hệ dịch nhằm giảm thiểu dung lượng

bộ nhớ mà mô hình ngôn ngữ chiếm dụng. Tuy chất lượng dịch chưa cao

nhưng khi chúng ta huấn luyện với nhiều dữ liệu hơn, chất lượng dịch sẽ được

nâng cao. Mặt khác ta hoàn toàn có thể áp dụng cho chiều dịch ngược lại

Việt-Anh.

1- Các kết quả đạt được

- Trình bày về cách tiếp cận dịch máy bằng thống kê;

- Xây dựng mô hình ngôn ngữ bằng SRI-LM và RAND-LM;

- Áp dụng cách tiếp cận này vào bài toán dịch Anh-Việt;

- Xây dựng chương trình thử nghiệm dịch Anh-Việt bằng

thống kê.

2- Hướng phát triển

- Tiếp tục cải tiến các mô hình dịch cho bài toán dịch Anh-Việt;

- Thử nghiệm với ngữ liệu đa dạng hơn và lớn hơn;

- Áp dụng cho chiều dịch từ Việt – Anh.

TÀI LIỆU THAM KHẢO

Tiếng Việt

[1] Nguyễn Văn Vinh (2005). “Xây dựng chương trình dịch tự động Anh-Việt bằng phương pháp dịch thống kê”. Luận văn Thạc sĩ, Đại học Công nghệ, ĐHQGHN.

Tiếng Anh

[2] Brants, T., Popat, A. C., Xu, P., Och, F. J., and Dean, J.. “Large language models in machine translation”. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), 2007, pages 858–867.

[3] Callison-Burch, Chris, Miles Osborne, and Philipp Koehn. “Re- evaluating the role of Bleu in machine translation research”. In EACL 2006: Proceedings the Eleventh Conference of the European Chapter of the Association for Computational Linguistics, 2006.

[4] Costa, L. H. M. K., Fdida, S., and Duarte, O. C. M. B. “Incremental service deployment using the hop-by-hop multicast routing protocol”. IEEE/ACM Trans. Netw., 2006, 14(3): pages 543–556.

[5] de Laplace, M.. “A Philosophical Essay on Probabilities”. Dover

Publications, 1996.

[6] To Hong Thang. “Building language model for Vietnamese and its application”. Dissertation, Bachelor of IT, College of Technology, Vietnam National University, 2008.

[7] Koehn, P.. “Empirical Methods in Natural Language Processing”.

From course slides at http://www.inf.ed.ac.uk/teaching/courses/emnlp/, 2007. [8] Talbot, D. and Talbot, J.. “Bloom maps”. In Proceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). Society for Industrial and Applied Mathematics, 2008.

[9] Koehn, P. and Hoang, H.. “Factored translation models”. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural

Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), 2007, pages 868–876.

[10] Levenberg, A. D. “Bloom filter and lossy dictionary based language models”. Dissertation, master of science, School of Informatics, University of Edinburgh, 2007.

[11] Masao Utiyama. “A survey of statistical machine translation”.

Lecture slides, Kyoto University, 2006.

[12] Och, F. “The Google Statistical Machine Translation System for the 2005 NIST MT Evaluation”. Oral presentation at the 2005 NIST MT Evaluation workshop, 2005.

[13] Pagh, A., Pagh, R., and Rao, S. S.. “An optimal bloom filter replacement”. In SODA ’05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics, 2005, pages 823–829.

[14] Talbot, D. and Osborne, M., “Randomised language modelling for statistical machine translation”. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, Prague, Czech Republic. Association for Computational Linguistics, 2007a, pages 512–519.

[15] Talbot, D. and Osborne, M., “Smoothed Bloom filter language models: Tera-scaleLMs on the cheap”. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), 2007b, pages 468–476.

Luận văn Thạc sĩ Khoa học máy tính: Sử dụng mô hình ngôn ngữ Bloom Filter trong cải tiến dịch máy thống kê

LỜI CAM ĐOAN

LỜI CẢM ƠN

DANH SÁCH CÁC TỪ VIẾT TẮT

DANH MỤC CÁC HÌNH VẼ

MỤC LỤC

MỞ ĐẦU

NỘI DUNG

U

1 0 1 0 0 1 0 1 1 0 1

1 0 1 0 0 1 0 1 1 0 1

KẾT LUẬN

- Tiếp tục cải tiến các mô hình dịch cho bài toán dịch Anh-Việt;

- Thử nghiệm với ngữ liệu đa dạng hơn và lớn hơn;

- Áp dụng cho chiều dịch từ Việt – Anh.

TÀI LIỆU THAM KHẢO

Có thể bạn quan tâm

Luận văn Thạc sĩ: Quản lý hoạt động phát triển nhận thức cho trẻ mẫu giáo ở các trường mầm non, huyện Hoàng Su Phì, tỉnh Hà Giang

Mô hình chú ý ngữ cảnh đa tầm nhìn cải tiến cho bài toán trả lời câu hỏi dựa trên hình ảnh bằng tiếng Việt

Luận văn Thạc sĩ tóm tắt: Pháp luật về điều kiện đầu tư kinh doanh trong lĩnh vực giáo dục, đào tạo ở Việt Nam

Luận văn Thạc sĩ: Sự nghiệp nghiên cứu phê bình văn học của Hoài Thanh

Luận văn Thạc sĩ: Tiểu thuyết của Đỗ Phấn từ góc nhìn sinh thái

Luận văn Thạc sĩ: Giải pháp ứng phó với nhập cư ở Liên minh Châu Âu

Luận văn Thạc sĩ: Diễn ngôn về giới nữ trong văn xuôi nữ Việt Nam đương đại (khảo sát sáng tác của Dạ Ngân, Y Ban, Lý Lan, Nguyễn Thị Thu Huệ)

Luận văn Thạc sĩ: Xây dựng mức phát thải tham chiếu rừng khu vực huyện Bảo Lâm tỉnh Lâm Đồng

Luận văn Thạc sĩ: Đặc điểm nhân vật chính trong ba tác phẩm của Franz Kafka: Lâu đài, Vụ án, Hóa thân

Kháo luận tốt nghiệp: Vận dụng lí thuyết học tập trải nghiệm vào dạy học Thống kê - Xác suất ở lớp Hai

Luận văn Thạc sĩ: Xây dựng hệ thống điều khiển và thu nhận dữ liệu cho Robot dịch vụ

Luận văn Thạc sĩ: Thế giới nhân vật trong truyện ngắn Lê Minh Khuê sau năm 1975

Luận văn Thạc sĩ: Tác động của cấu trúc vốn đến hiệu quả hoạt động của các ngân hàng thương mại cổ phần niêm yết trên thị trường chứng khoán Việt Nam

Luận văn Thạc sĩ: Kiểm soát rủi ro tín dụng bán lẻ tại Ngân hàng Thương mại Cổ phần Đầu tư và Phát triển Việt Nam chi nhánh Thủ Thiêm

Luận văn Thạc sĩ: Các yếu tố ảnh hưởng đến hiệu quả kinh doanh của ngân hàng thương mại cổ phần niêm yết trên thị trường chứng khoán Việt Nam

Luận văn Thạc sĩ: Các nhân tố ảnh hưởng đến hành vi sử dụng dịch vụ ngân hàng điện tử tại Ngân hàng Thương mại Cổ phần Ngoại thương Việt Nam – Chi nhánh Thủ Đức

Luận văn Thạc sĩ: Các yếu tố tác đồng đến nợ xấu tại Ngân hàng Nông nghiệp và Phát triển Nông thôn - Chi nhánh Tiền Giang

Luận văn Thạc sĩ: Yếu tố ảnh hưởng đến quyết định sử dụng dịch vụ thanh toán không dùng tiền mặt tại Ngân hàng TMCP Công thương Việt Nam (Vietinbank)

So sánh độ tương đồng câu hỏi trong diễn đàn

Luận văn Thạc sĩ tóm tắt: Pháp luật về du lịch biển, thực tiễn tại tỉnh Bình Định

Tài liêu mới

Luận án Tiến sĩ: Nghiên cứu xây dựng thuật toán thích nghi và học tăng cường cấu trúc Actor - Critic điều khiển bám quỹ đạo cho robot di động đa hướng mecanum

Luận án Tiến sĩ: Cơ cấu bệnh tim mạch và chất lượng cuộc sống của người cao tuổi mắc suy tim, rung nhĩ điều trị tại Bệnh viện Thống Nhất, thành phố Hồ Chí Minh

Tóm tắt Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

Tóm tắt Luận án Tiến sĩ: Nghiên cứu xây dựng giải pháp đảm bảo an toàn thông tin cho quá trình học liên kết dựa trên mật mã

Tóm tắt Luận án Tiến sĩ: Phát triển năng lực đánh giá công nghệ cho học sinh trong dạy học môn Công nghệ 11 ở trường trung học phổ thông

Tóm tắt Luận án Tiến sĩ: Nghiên cứu phân loại chi cầu diệp – Bulbophyllum Thouars (Orchidaceae) ở vùng Tây Nguyên bằng phương pháp hình thái và phân tử

Tóm tắt Luận án Tiến sĩ: Nghiên cứu đặc điểm phân bố và dinh dưỡng của các loài lưỡng cư ở Vườn Quốc gia Bến En và Khu bảo tồn thiên nhiên Pù Luông, tỉnh Thanh Hóa

Luận án Tiến sĩ: Tổng hợp luật dẫn và điều khiển cho một lớp tên lửa đối hải trên cơ sở ứng dụng mạng nơ ron và hệ mờ

Luận án Tiến sĩ: Nghiên cứu tổng hợp hệ điều khiển góc Pitch tua bin gió trong điều kiện có nhiễu tác động

Luận án Tiến sĩ: Nghiên cứu hóa học lipid của hai loài san hô thủy tức Millepora dichotoma và Millepora platyphylla ở Việt Nam

Luận án Tiến sĩ: Nghiên cứu kiểm soát phân phối công suất kéo trên cầu chủ động của ô tô con bằng ABS

Luận án Tiến sĩ: Ứng dụng phản ứng Domino vào tổng hợp các dẫn xuất Podophyllotoxin, Pyrimidine và đánh giá hoạt tính sinh học của các chất tổng hợp được

Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và một số hoạt tính sinh học của cây chùm ngây (Moringa oleifera)

Tóm tắt Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và ứng dụng ức chế ăn mòn cho thép của cao chiết xuất từ cây Lộc vừng thuộc họ Lecythidaceae

Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok