Luận văn Thạc sĩ: Nghiên cứu mô hình ngôn ngữ N-Gram và ứng dụng thêm dấu cho tiếng Việt không dấu

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CNTT&TT

CAO ĐỨC TƯ

NGHIÊN CỨU MÔ HÌNH NGÔN NGỮ N-GRAM VÀ ỨNG DỤNG TRONG BÀI TOÁN THÊM DẤU CHO TIẾNG VIỆT KHÔNG DẤU

CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 60.48.01

LUẬN VĂN THẠC SĨ : KHOA HỌC MÁY TÍNH

Thái Nguyên - 2011

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CNTT&TT

CAO ĐỨC TƯ

NGHIÊN CỨU MÔ HÌNH NGÔN NGỮ N-GRAM VÀ ỨNG DỤNG TRONG BÀI TOÁN THÊM DẤU CHO TIẾNG VIỆT KHÔNG DẤU

CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 60.48.01

LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC TS. VŨ TẤT THẮNG

Thái Nguyên - 2011

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

LỜI CAM ĐOAN

Tôi xin cam đoan, toàn bộ nội dung liên quan tới đề tài đƣợc trình bày

trong luận văn là bản thân tôi tự tìm hiểu và nghiên cứu, dƣới sự hƣớng dẫn

khoa học của TS. Vũ Tất Thắng Viện công nghệ thông tin thuộc Viện Khoa

học và Công nghệ Việt Nam. Các tài liệu, số liệu tham khảo đƣợc trích dẫn

đầy đủ nguồn gốc.

Tôi xin chịu trách nhiệm trƣớc pháp luật lời cam đoan của mình.

Thái Nguyên, ngày 30 tháng 9 năm 2011

Học viên

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Cao Đức Tư

LỜI CẢM ƠN

Luận văn được hoàn thành bởi sự nỗ lực của bản thân, sự giúp đỡ tận

tình của các thầy cô trường Đại học công nghệ thông tin và truyền thông

thuộc Đại học Thái Nguyên, thầy cô Viện công nghệ thông tin thuộc Viện

Khoa học và Công nghệ Việt Nam.Đã tận tình chỉ dạy, giúp đỡ em trong cả

quá trình học tập và hoàn thành luận văn.

Xin bày tỏ lòng biết ơn sâu sắc đến TS. Vũ Tất Thắng Viện công nghệ

thông tin thuộc Viện Khoa học và Công nghệ Việt Nam, người đã tận tình chỉ

dẫn tôi trong suốt quá trình xây dựng đề cương và hoàn thành luận văn.

Xin cảm ơn các anh chị em trong lớp cao học K8 đã giúp đỡ, đóng góp

ý kiến chia sẽ những kinh nghiệm học tập, nghiên cứu trong suốt khóa học.

Mặc dù đã cố gắng hết sức để hoàn thành luận văn , song không thể

tránh khỏi sai sót. Xin kính mong nhận được nhận xét và sự đóng góp của qu ý

Thầy Cô và bạn bè.

Thái Nguyên, ngày 30 tháng 9 năm 2011

Học viên

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Cao Đức Tư

MỤC LỤC

CHƢƠNG 1: GIỚI THIỆU CHUNG ............................................................. 5

1.1.Đặt vấn đề: ............................................................................................ 5

1.2.Mục tiêu: ............................................................................................... 7

1.3.Cấu trúc của luận văn: ........................................................................... 7

CHƢƠNG 2: MÔ HÌNH NGÔN NGỮ N-GRAM .......................................... 8

2.1.Giới thiệu chung .................................................................................... 8

2.2.Công thức tính “xác suất thô” ................................................................ 9

2.3.Vần đề khó khăn khi xây dựng mô hình ngôn ngữ N-gram.................. 10

2.4.Các phƣơng pháp làm mịn ................................................................... 11

2.5.Kỹ thuật làm giảm kích thƣớc dữ liệu:................................................. 19

2.6.Độ đo .................................................................................................. 23

2.7.Tổng kết chƣơng ................................................................................. 23

CHƢƠNG 3: XÂY DỰNG N-GRAM CHO TIẾNG VIỆT .......................... 27

3.1.Giới thiệu ............................................................................................ 27

3.2.Công cụ tách từ cho tiếng Việt - vnTokenizer.................................. 3427

3.3.Bộ công cụ SRILM ............................................................................. 35

3.4.Bộ công cụ trợ giúp xây dựng tập văn bản huấn luyện......................... 39

3.5.Phƣơng pháp tách câu, tách từ, gán nhãn từ loại và phân tích cú pháp. .............................................................................................................. 3340

3.6.Dữ liệu huấn luyện .............................................................................. 40

3.7.Kết quả xây dựng mô hình................................................................... 40

3.8.Tần số của tần số ................................................................................. 49

3.9.Cut-off (loại bỏ) .................................................................................. 52

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

3.10.Các phƣơng pháp làm mịn ................................................................. 53

3.11.Tổng kết chƣơng ............................................................................... 55

CHƢƠNG 4: ỨNG DỤNG N-GRAM TRONG BÀI TOÁN ........................ 56

THÊM DẤU TIẾNG VIỆT .......................................................................... 56

4.1. Bài toán thêm dấu tiếng Việt .............................................................. 56

4.2. Các phƣơng pháp đánh giá kết quả thêm dấu: ..................................... 57

4.3. Các hệ thống thêm dấu ứng dụng về N-gram đã có: ........................... 59

4.4. Đề xuất hệ thống: ............................................................................... 63

4.5. Thử nghiệm hệ thống: ........................................................................ 66

CHƢƠNG 5: KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN CỦA ĐỀ TÀI .... 6760

5.1. Các kết quả đạt đƣợc: ..................................................................... 6760

5.2.Hạn chế và hƣớng phát triển của đề tài: ........................................... 6760

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

DANH MỤC CÁC KÝ HIỆU VIẾT TẮT

Diễn giải

Ý nghĩa

Hiệp hội ngôn ngữ học tính toán

Viết tắt ACL

Association for Computational Linguistics Short Message Services Stanford Research Institute language Model Maximum Mactching

SMS SRI LM MM LRMM Left Right Max Matching

Dịch vụ tin nhắn học viện nghiên cứu sờ ten phoóc Mô hình ngôn ngữ Khớp tối đa tìm đoạn tƣơng ứng dài nhất tính từ trái/phải

WFST Weighted finite-state Transducer Mạng chuyển dịch trạng thái có trọng

số

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

DANH MỤC HÌNH

Hình 3-1. Quy trình tách từ .......................................................................... 34

Hình 3-2 Số lƣợng các cụm n-gram với âm tiết tăng kích thƣớc dữ liệu ....... 48

Hình 3-3: số lƣợng các cụm N-gram với từ khi tăng kích thƣớc dữ liệu ....... 49

Hình 3-4: số lƣợng các cụm Ngram (âm tiết) có tần số từ 1 đến 10 .............. 50

Hình 3-5. Số lƣợng các cụm Ngram (từ) có tần số từ 1 đến 10 ..................... 51

Hình 4-1. Sự trùng khớp của các bản dịch máy với bản dịch mẫu ............ 5158

Hình 4-2. Lƣu đồ thực hiện mô hình ứng dụng trong VietPad ...................... 60

Hình 4-3. Lƣu đồ thực hiện của mô hình N-gram ......................................... 55

Hình 4-4. Lƣu đồ thực hiện của mô hình đề xuất ...................................... 6356

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Hình 4.5. Mô hình test thêm dấu đề xuất. ................................................. 6659

DANH MỤC BẢNG

Bảng 3 -1. Số lƣợng các cụm n-gram trong văn bản huấn luyện với âm tiết . 48

Bảng 3-2: Số lƣợng các cụm N-gram trong văn bản huấn luyện với từ ..... 4942

Bảng 3-3: Tần số của tần số các cụm N-gram áp dụng cho âm tiết ........... 5043

Bảng 3-4. Tần số của tần số các cụm Ngram với từ ...................................... 51

Bảng 3-5: Bộ nhớ và độ hỗn loạn thông tin khi áp dụng loại bỏ trong âm tiết ................................................................................................................. 4552

Bảng 3-6: Bộ nhớ và độ hỗn loạn thông tin khi áp dụng loại bỏ với từ ......... 53

Bảng 3-7: Độ hỗn loạn thông tin của các phƣơng pháp làm mịn cho âm tiết ................................................................................................................. 5447

Bảng 3-8: Độ hỗn loạn thông tin của các phƣơng pháp làm mịn cho từ .... 5447

MỞ ĐẦU

1. Lý do chọn đề tài:

Trong lĩnh vực xử lí ngôn ngữ tự nhiên, sử dụng các mô hình ngôn ngữ

sẽ giúp giới hạn không gian tìm kiếm để có các giải pháp tốt nhất có thể có

trong khoảng thời gian ngắn. Chúng ta cần ƣớc lƣợng độ hợp lý của câu văn

đƣợc đƣa ra trong ngôn ngữ thực tế. Trong thực tế, chúng ta có thể thực hiện

từng phần, mỗi phần là một chuỗi các từ. Vì ngôn ngữ thực ra chỉ đƣợc học từ

sự quan sát và vì chúng ta không bao giờ quan sát hết đƣợc ngôn ngữ tự nhiên

để có thể xem xét tất cả các câu có thể xảy ra.

Hiện tại, chúng ta có thể dễ dàng tìm thấy ngày càng nhiều những hệ

thống dịch tự động miễn phí trên mạng nhƣ: Systran, Reverso,

WorldLingo, IBM translator… Những hệ thống này cho phép dịch tự động

các văn bản với một cặp ngôn ngữ chọn trƣớc (ví dụ: dịch một văn bản giữa

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

tiếng Anh và tiếng Pháp, hoặc tiếng Anh và tiếng Việt). Tuy nhiên, chất lƣợng

dịch là vấn đề mà ngƣời sử dụng quan tâm vì đa số các hệ thống dịch tự động

hiện nay có chất lƣợng khá thấp. Ví dụ, để dịch văn bản giữa tiếng Việt và

tiếng Anh chúng ta có thể chọn sử dụng hệ thống dịch của Google nhƣng chất

lƣợng dịch theo chiều Việt-Anh là thấp so với chiều dịch Anh-Việt, và đặt

biệt thấp cho dịch Việt-Anh với văn bản đầu vào là tiếng Việt không dấu. Vấn

đề đặt ra là, làm sao để chuẩn hóa văn bản đầu vào cho hệ thống dịch. Ở đó

thêm dấu, hay chuẩn hóa dấu văn bản là một vấn đề rất quan trọng.

Từ những vấn đề trên cũng nhƣ những kiến thức đã đƣợc học tôi lựa

chọn đề tài: “Nghiên cứu mô hình Ngôn ngữ N-gram và ứng dụng trong

bài toán thêm dấu cho tiếng Việt không dấu”, một trong những vấn đề có

tính cấp thiết trong lĩnh vực xử lí ngôn ngữ tự nhiên tiếng Việt nói riêng và

khoa học công nghệ trong đời sống xã hội nói chung.

2. Mục đích và nhiệm vụ:

 Mục tiêu

Về học thuật:

Đề tài này tập trung vào việc ứng dụng một số phƣơng pháp tách từ,

tiếng, phƣơng pháp làm mịn trong mô hình ngôn ngữ N-gram nhằm tăng hiệu

quả thêm dấu cho tiếng Việt không dấu.

Về phát triển và triển khai ứng dụng: Kết quả của đề tài sẽ ứng dụng trong việc hỗ trợ trong việcthêm dấu

cho tiếng Việt không dấu.

 Nhiệm vụ

- Nghiên cứu các vấn đề khi xây dựng mô hình ngôn ngữ N-gram

- Nghiên cứu các phƣơng pháp làm mịn trong mô hình ngôn ngữ N-

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

gram.

- Nghiên cứu các kỹ thuật làm giảm kích thƣớc dữ liệu.

3. Phƣơng pháp nghiên cứu:

Nghiên cứu N-gram thông qua tài liệu về cơ sở thống kê của phƣơng

pháp xử lý ngôn ngữ tự nhiên và cơ sở của nó.

Nghiên cứu phƣơng pháp xác định ngôn ngữ văn bản thực tế đƣợc các

chƣơng trình thêm dấu tự động sử dụng.

Tìm hiểu, vận dụng và kế thừa các thuật tuán và quy trình đã công bố

kết quả.

Áp dụng mô hình ngôn ngữ cho bài toán thêm dấu, có đối sánh với kết

quả của các phƣơng pháp thêm dấu tự động khác.

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

- Đối tượng nghiên cứu: Nghiên cứu về mô hình ngôn ngữ N-gram, và

các kỹ thuật liên quan tới việc làm trơn hóa phân bố xác suất của mô hình.

- Phạm vi nghiên cứu: Nghiên cứu về mô hình ngôn ngữ N gram, và

ứng dụng trong bài toán thêm dấu cho tiếng Việt không dấu sử dụng mô hình

ngôn ngữ N-gram.

5. Ý nghĩa khoa học của luận văn.

 Ý nghĩa khoa học

- Trình bày các kiến thức toán học cơ bản về mô hình ngôn ngữ N-gram

, lý thuyết độ phức tạp của thuật toán.

- Trình bày các phƣơng pháp làm mịn trong mô hình N-gram.

 Ý nghĩa thực tiễn

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Cài đặt hoàn chỉnh chƣơng trình thêm dấu cho tiếng Việt không dấu Đƣa ra kết quả so sánh với những phần mềm đã có.

6. Bố cục của luận văn

Mở đầu

1. Lý do chọn đề tài.

2. Mục đích và nhiệm vụ.

3. Phƣơng pháp nghiên cứu.

4. Đối tƣợng và phạm vi nghiên cứu. 5. Ý nghĩa khoa học và thực tiễn của luận văn

Chƣơng 1.Giới thiệu chung

1.1. Đặt vấn đề

1.2. Mục tiêu

13. Cấu trúc

Chƣơng 2. Mô hình ngôn ngữ N-gram

2.1.Giới thiệu chung

2.2.Vấn đề công thức tính “xác suất thô”.

2.3.Vấn đề khi xây dựng mô hình ngôn ngữ N-gram.

2.4.Các phƣơng pháp làm min.

2.5.Kỹ thuật làm giảm kích thƣớc dữ liệu.

2.6.Độ đo

2.7.Tổng kết chƣơng

Chƣơng 3.Xây dựngN-gram cho tiếng Việt

3.1. Giới thiệu.

3.2. Công cụ tách từ cho tiếng việt-VnTokenizer.

3.3. Bộ công cụ SRILM.

3.4. Bộ công cụ trợ giúp xây dựng tập văn bản huấn luyện.

3.5. Phƣơng pháp tách câu, tách từ, gán nhãn từ loại và phân tích cú pháp.

3.6. Dữ liệu huấn luyện.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

3.7. Kết quả xây dựng mô hình.

3.8. Tần số của tần số

3.9. Cut-of ( loại bỏ)

3.10. Các phƣơng pháp làm mịn.

3.11. Tổng kết chƣơng

Chƣơng 4.Ứng dụng N-gram trong bài toán thêm dấu tiếng Việt

4.1.Bài toán thêm dấu tiếng Việt.

4.2. Các phƣơng pháp đánh giá kết quả thêm dấu.

4.3. Các hệ thống thêm dấu ứng dụng về N-gram đã có.

4.4. Đề xuất hệ thống. 4.5. Thử nghiệm hệ thống.

Chƣơng 5: Kết luận và hƣớng phát triển của đề tài

5.1. Các kết quả đạt đƣợc:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

5.2.Hạn chế và hƣớng phát triển của đề tài:

CHƢƠNG 1: GIỚI THIỆU CHUNG

1.1.Đặt vấn đề:

Ngôn ngữ tự nhiên là những ngôn ngữ đƣợc con ngƣời sử dụng trong các

giao tiếp hàng ngày: nghe, nói, đọc, viết[13]. Mặc dù con ngƣời có thể dễ

dàng hiểu và học các ngôn ngữ tự nhiên, việc làm cho máy hiểu đƣợc ngôn

ngữ tự nhiên không phải là chuyện dễ dàng. Sở dĩ có khó khăn là do ngôn ngữ tự nhiên có các bộ luật, cấu trúc ngữ pháp phong phú hơn nhiều các ngôn ngữ

máy tính, hơn nữa để hiểu đúng nội dung các giao tiếp, văn bản trong ngôn

ngữ tự nhiên cần phải nắm đƣợc ngữ cảnh của nội dung đó. Do vậy, để có thể

xây dựng đƣợc một bộ ngữ pháp, từ vựng hoàn chỉnh, chính xác để máy có

thể hiểu ngôn ngữ tự nhiên là một việc rất tốn công sức và đòi hỏi ngƣời thực

hiện phải có hiểu biết rất sâu sắc về ngôn ngữ học.

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[8],[13].

Nói một cách đơ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à có xác suất sinh ra là bao nhiêu.

Ví dụ 1.1: Khi áp dụng mô hình ngôn ngữ cho tiếng Việt, ta có thể có

một kết quả có dạng tƣơng tự nhƣ sau:

P[“ngày mai trời sẽ mưa”] ~ 0.001

P[“trời mưa sẽ mai ngày”] ~ 0

Với các vấn đề của xử lí ngôn ngữ tự nhiên, việc sử dụng các mô hình

ngôn ngữ để xác định xác suất xẩy ra nhƣ trên sẽ giúp giới hạn lại không gian tìm kiếm, để có thể tìm ra các giải pháp tốt nhất trong một khoảng thời gian đủ ngắn.

Cốt lõi nhất của các phƣơng pháp để máy tính xử lý ngôn ngữ tự nhiên

chính là việc xây dựng mô hình ngôn ngữ, mà ngày nay ngƣời ta thƣờng dùng

ở dạng mô hình thống kê. Các phƣơng pháp xử lý ngôn ngữ tự nhiên dựa trên

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

thống kê không nhằm tới việc con ngƣời tự xây dựng mô hình ngữ pháp mà lập chƣơng trình cho máy tính có thể “học” nhờ vào việc thống kê các từ và

cụm từ có trong các văn bản. Trong các mô hình ngôn ngữ tiếng nói, thì N- gram là một trong số những mô hình đƣợc sử dụng rộng rãi nhất.

Mục tiêu của luận văn, là nghiên cứu nắm bắt đƣợc những vấn đề cốt lõi

của mô hình ngôn ngữ N-gram, đặc biệt là các kỹ thuật làm trơn các phân bố

xác suất thống kê (Smoothing techniques), nhằm nâng cao chất lƣợng về

lƣợng giá xác suất bởi mô hình. Ngoài ra, luận văn hƣớng tới việc đƣa ra một

ứng dụng cụ thể của mô hình này cho tiếng Việt, mà cụ thể là bài toán thêm

dấu cho văn bản tiếng Việt không dấu.

Dấu là một thành phần không thể thiếu và mang những thông tin, nội

dung quan trọng của văn bản tiếng Việt. Chúng không là mẫu tự mà là một

phần của mẫu tự. Tuy nhiên có rất nhiều trƣờng hợp mà ngƣời sử dụng đã loại

bỏ các thành phần này, chẳng hạn trong các tin nhắn SMS qua điện thoại, các

liên lạc kiểu thƣ điện tử, chat, …

Khái niệm dấu ở đây không chỉ giới hạn với 5 ký hiệu về dấu thanh điệu đƣợc thể hiện trong chữ Việt để thể hiện cho sáu loại thanh điệu khác nhau:

ngang, huyền, ngã, hỏi, sắc, và nặng. Mà hơn thế nữa, nó còn bao gồm các

nhiều dấu phụ trợ cho 5 nguyên âm không dấu: a, i, u, e, o để tạo lập các ký tự

đủ đa dạng cho việc ký âm các nguyên âm tiếng Việt, a ă â e ê i o ô ơ u ƣ y.

Ngoài ra chữ Việt có thêm dấu gạch trên đầu d để ký âm cho một phụ âm

khác là đ.

Trong đa số trƣờng hợp, ngƣời đọc văn bản phải nội suy đƣợc dấu tƣơng

ứng của các đoạn văn không dấu, cố gắng hiểu đƣợc ý nghĩa chuyển tải của

mỗi đoạn văn dựa theo ngữ cảnh của cả văn bản. Đối với các hệ thống xử lí văn bản tự động thì đây chính là một nhập nhằng rất khó giải quyết, đặc biệt là các hệ thống phân tích cú pháp, hệ thống tìm kiếm, hệ thống dịch tự động,

… Đề tài này sẽ tập trung vào một phƣơng pháp cơ bản là sử dụng mô hình ngôn ngữ N-gram để tính toán các khả năng thêm giấu với xác suất cao nhất,

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

giúp máy tính tự động thêm dấu cho các văn bản không dấu tiếng Việt.

1.2.Mục tiêu:

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ục tiêu chính của luận văn là tìm hiểu lý thuyết về mô hình N-gram và

các vấn đề trong đó, đặc biệt là các phƣơng pháp làm mịn. Về thực nghiệm,

luận văn có sử dụng bộ công cụ SRILM để xây dựng mô hình ngôn ngữ cho

tiếng Việt với các phƣơng pháp làm mịn khác nhau. Bằng việc áp dụng các

mô hình ngôn ngữ khác nhau đó vào bài toán thêm dấu cho tiếng Việt không dấu, và chỉ ra đƣợc phƣơng pháp làm mịn nào là tốt nhất khi áp dụng cho mô

hình ngôn ngữ tiếng Việt.

1.3.Cấu trúc của luận văn:

Sau phần giới thiệu chung và mục tiêu nghiên cứu đƣợc trình bày ở

Chƣơng 1, phần còn lại của Luận văn đƣợc cấu trúc nhƣ sau:

Chƣơng 2: Nghiên cứu các vấn đề của mô hình ngôn ngữ N-gram, các sự

cố gặp phải và cách khắc phục trong việc xây dựng tối ƣu mô hình N-gram.

Chƣơng 3: Luận văn tập trung vào việc mô tả thực nghiệm, bao gồm công việc xây dựng và cài đặt những chƣơng trình hỗ trợ việc xây dựng đƣợc mô

hình ngôn ngữ. và các kết quả đạt đƣợc.

Chƣơng 4: Tập trung vào việc áp dụng mô hình ngôn ngữ trong bài toán

thêm dấu cho tiếng Việt không dấu.

Chƣơng 5: Tổng kết những gì luận văn đã đạt đƣợc và đƣa ra kế hoạch

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

nghiên cứu trong tƣơng lai.

CHƢƠNG 2: MÔ HÌNH NGÔN NGỮ N-GRAM

2.1.Giới thiệu chung

Mô hình ngôn ngữ thống kê cho phép gán (ƣớc lƣợng) xác suất cho một

chuỗi m phần tử (thƣờng là từ) P(w1w2…wm) tức là cho phép dự đoán khả năng một chuỗi từ xuất hiện trong ngôn ngữ đó. Theo công thức Bayes: P(AB) = P(B|A) * P(A), thì ta dễ dàng suy ra đƣợc.

P(w1w2…wm) = P(w1) * P(w2|w1) * P(w3|w1w2) *…* P(wm|w1w2…wm-1).

Theo công thức này thì bài toán tính xác suất của mỗi chuỗi từ quy về

bài toán tính xác suất của một từ với điều kiện biết các từ trƣớc nó (có thể hiểu P(w1)=P(w1|start) là xác suất để w1 đứng đầu chuỗi hay nói cách khác ngƣời ta có thể đƣa thêm ký hiệu đầu dòng start vào mỗi chuỗi).

Trong thực tế, dựa vào giả thuyết Markov ngƣời ta chỉ tính xác suất của

một từ dựa vào nhiều nhất N từ xuất hiện liền trƣớc nó, và thông thƣờng

N=0,1,2,3. Vì vậy nhiều ngƣời gọi mô hình ngôn ngữ là mô hình N-gram,

trong đó N là số lƣợng từ ( bao gồm cả từ cần tính và các từ ngữ cảnh phía

trƣớc).

Theo công thức Bayes, mô hình ngôn ngữ cần phải có một lƣợng bộ nhớ

vô cùng lớn để có thể lƣu hết xác suất của tất cả các chuỗi độ dài nhỏ hơn m.

Rõ ràng, điều này là không thể khi m là độ dài của các văn bản ngôn ngữ tự

nhiên (m có thể tiến tới vô cùng). Để có thể tính đƣợc xác suất của văn bản

với lƣợng bộ nhớ chấp nhận đƣợc, ta sử dụng xấp xỉ Markov bậc n:

P(wm|w1,w2,…, wm-1) = P(wm|wm-n,wn-m+1, …,wm-1).

Nếu áp dụng xấp xỉ Markov, xác suất xuất hiện của một từ (wm) đƣợc coi nhƣ chỉ phụ thuộc vào n từ đứng liền trƣớc nó (wm-nwm-n+1…wm-1) chứ không phải phụ thuộc vào toàn bộ dãy từ đứng trƣớc (w1w2…wm-1). Nhƣ vậy, công thức tính xác suất văn bản đƣợc tính lại theo công thức:

P(w1w2…wm) = P(w1) * P(w2|w1) * P(w3|w1w2) *…

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

* P(wm-1|wm-n-1wm-n …wm-2)* P(wm|wm-nwm-n+1…wm-1).

Với công thức này, ta có thể xây dựng mô hình ngôn ngữ dựa trên việc

thống kê các cụm có ít hơn n+1 từ. Các mô hình N-gram đƣợc hình dung

thông qua ví dụ nhƣ sau:

Ví dụ 2.1: Giả sử cần tính xác suất p=P(nên | không thầy đố mày làm):

 Mô hình 1-Gram(unigram )tính xác suất của một từ mà không phụ thuộc vào các từ trƣớc nó, tức là không có ngữ

cảnh:

p=P(nên)

 Mô hình 2-Gram(bigram ) tính xác suất của một từ dựa vào

một từ trƣớc nó:

p=P(nên|mày)

 Mô hình 3-Gram(trigram ) tính xác suất của một từ dựa vào

hai từ trƣớc nó:

p=P(nên|mày làm)

2.2.Công thức tính “xác suất thô”

Gọi C(wi-n+1...wi-1wi) là tần số xuất hiện của cụm wi-n+1...wi-1wi trong tập

văn bản huấn luyện.

Gọi P(wi|wi-n+1...wi-1) là xác suất wi đi sau cụm wi-n+1..wi-2wi-1.

Ta có công thức tính xác suất nhƣ sau:

P(wi|wi-n+1...wi-1) =

C(wi-n+1...wi-1w) C(wi-n+1...wi-1wi)  w

C(wi-n+1..wi-1w) chính là tần số xuất hiện của cụm wi-n+1...wi-1 Dễ thấy,  w

trong văn bản huấn luyện. Do đó công thức trên viết lại thành:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

P(wi|wi-n+1...wi-1) = C(wi-n+1...wi-1wi) C(wi-n+1...wi-1)

Tỉ lệ ở vế phải còn gọi là tỉ lệ tần số. Cách tính xác suất dựa vào tỉ lệ tần

số còn gọi là ƣớc lƣợng xác suất cực đại. Cũng có thể gọi đây là công thức

tính “xác suất thô” để phân biệt với các cách tính xác suất theo các thuật toán

sẽ xét ở phần sau.

2.3.Vần đề khó khăn khi xây dựng mô hình ngôn ngữ N-gram

2.3.1.Phân bố không đều

Với mô hình N-gram đƣợc xây dựng theo công thức “xác suất thô”, sự

phân bố không đều trong tập văn bản huấn luyện có thể dẫn đến các ƣớc

lƣợng không chính xác. Khi các n-gram phân bố thƣa, nhiều cụm n-gram

không xuất hiện hoặc chỉ có số lần xuất hiện nhỏ, việc ƣớc lƣợng xác suất để

đánh giá các câu có chứa các cụm n-gram này sẽ cho ta một kết quả không

tốt. Với V là kích thƣớc bộ từ vựng, ta sẽ có V cụm n-gram có thể sinh từ bộ

từ vựng. Tuy nhiên, thực tế thì số cụm n-gram có nghĩa và thƣờng gặp chỉ

chiếm rất ít.

Ví dụ 2.2: Tiếng Việt có số lƣợng âm tiết nhiều hơn con số mà ở đây ta

tạm đặt là 5000 âm tiết khác nhau, ta có tổng số cụm 3-gram có thể có là: 5.0003 = 125.000.000.000. Tuy nhiên, số cụm 3-gram thống kê đƣợc chỉ xấp xỉ 1.500.000. Nhƣ vậy sẽ có rất nhiều cụm 3-gram không xuất hiện hoặc chỉ

xuất hiện rất ít nên khả năng rất dễ xẩy ra là nó không xuất hiện trong dữ liệu huấn luyện mô hình.

Khi tính toán xác suất của một câu, có rất nhiều trƣờng hợp sẽ gặp cụm

n-gram chƣa xuất hiện trong dữ liệu huấn luyện bao giờ. Điều này làm xác suất của cả câu bằng 0, trong khi câu đó có thể là một câu hoàn toàn đúng về mặt ngữ pháp và ngữ nghĩa. Đề khắc phục tình trạng này, ngƣời ta phải sử

dụng một số phƣơng pháp “làm mịn” kết quả thống kê mà chúng ta sẽ đề cập

ở phần 2.5.

2.3.2.Kích thƣớc bộ nhớ của mô hình ngôn ngữ

Khi kích thƣớc tập văn bản huấn luyện lớn, số lƣợng các cụm n-gram và

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

kích thƣớc của mô hình ngôn ngữ cũng rất lớn. Nó không những gây khó

khăn trong việc lƣu trữ mà còn làm tốc độ xử lý của mô hình ngôn ngữ giảm xuống do bộ nhớ của máy tính là hạn chế. Để xây dựng mô hình ngôn ngữ

hiệu quả, chúng ta phải giảm kích thƣớc của mô hình ngôn ngữ mà vẫn đảm

bảo độ chính xác. Vấn đề này sẽ đƣợc giải quyết ở phần 2.6

2.4.Các phƣơng pháp làm mịn

Để khắc phục tình trạng các cụm n-gram phân bố ngƣời ta đã đƣa ra các

phƣơng pháp “làm mịn” các kết quả thống kê nhằm đánh giá chính xác hơn

(mịn hơn) xác suất của các cụm n-gram. Các phƣơng pháp “làm mịn” đánh

● Gán cho các cụm n-gram có xác suất 0 (không xuất hiện trong tập

giá lại xác suất của các cụm n-gram bằng cách:

● Thay đổi lại giá trị xác suất của các cụm n-gram có xác suất khác

huấn luyện) một giá trị khác 0.

0 khác (có xuất hiện khi thống kê) thành một giá trị phù hợp (tổng

xác suất của tất cả các khả năng N-gram khác nhau phải đảm bảo

là không đổi, với giá trị là 100%).

● Chiết khấu (Discounting): giảm (lƣợng nhỏ) xác suất của các

Các phƣơng pháp làm mịn có thể đƣợc chia ra thành một số loại nhƣ sau:

cụm n-gram có xác suất lớn hơn 0 để bù cho các cụm n-gram

● Truy hồi (Back-off) : tính toán xác suất các cụm n-gram không

không xuất hiện trong tập huấn luyện.

xuất hiện trong tập huấn luyện dựa vào các cụm n-gram thành

● Nội suy (Interpolation): tính toán xác suất của tất cả các cụm n-

phần có độ dài ngắn hơn và có xác suất lớn hơn 0

gram dựa vào xác suất của các cụm n-gram ngắn hơn.

2.4.1.Các thuật toán chiết khấu (discounting)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Vấn đề của các thuật toán chiết khấu là giảm xác suất của các cụm n- gram có xác suất lớn hơn 0 và bù cho các cụm N-gram chƣa từng xuất hiện trong tập huấn luyện[13]. Các thuật toán dạng này sẽ trực tiếp làm thay đổi

● Thuật toán Add-one

● Thuật toán Witten-Bell

● Thuật toán Good-Turing

tần số xuất hiện của tất cả các cụm n-gram. Ở đây tôi sẽ đề cập đến 3 thuật toán chiết khấu phổ biến:

2.4.1.1.Phƣơng pháp làm mịn Add-one

Thuật toán làm mịn Add-one cộng thêm 1 vào số lần xuất hiện của mỗi

cụm n-gram bất kỳ rồi nhân với phân số chuẩn hóa (để bảo toàn tổng xác suất

vẫn giữ nguyên là 1).

Ví dụ, với unigram, khi cộng thêm 1 vào số lần xuất hiện của mỗi cụm

unigram, thì tổng số cụm unigram đƣợc thêm vào là:

M‟ = M + V với M là tổng số cụm unigram đã xuất hiện, V là kích

thƣớc bộ từ vựng.

Để bảo toàn tổng số cụm unigram vẫn bằng M, thì tần số mới của các

cụm unigram đƣợc tính lại theo công thức:

* = (Ci+1)

Ci M M‟

với Ci là tần số của cụm unigram trƣớc khi làm mịn. Nhƣ vậy, xác suất của các cụm unigram cũng đƣợc tính lại:

= Pi* = Ci* M (Ci+1) M + V

Xét các cụm n-gram với n>1, thay M bằng C(wi-n+1...wi-1) thì xác suất

của cụm (wi-n+1...wi-1wi) đƣợc tính theo công thức sau:

P(wi|wi-n+1...wi-1) = C(wi-n+1...wi-1wi) + 1 C(wi-n+1...wi-1) + V

Chúng ta có thể thấy thuật toán này sẽ làm thay đổi đáng kể xác suất của

các cụm N-gram đã xuất hiện trong tập huấn luyện nếu kích thƣớc bộ từ điển

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

V là rất lớn. Trong thực nghiệm, một vài cụm n-gram có xác suất giảm đi gần

10 lần, do kích thƣớc bộ từ điển là lớn trong khi tần số xuất hiện của cụm n-

gram đó không cao. Để thuật toán thêm hiệu quả, ngƣời ta có thể sử dụng

công thức tƣơng tự ở dạng sau:

P(w1w2...wn) = C(w1w2...wn) +  C(w1w2...wn-1) + M

Công thức trên là một phiên bản cải tiến thông dụng của thuật toán add-

one. Để bảo toàn tổng xác suất của tất cả các cụm N-gram, thì  đƣợc chọn

trong khoảng [0, 1], với một số giá trị thông dụng sau:

  = 0: không làm mịn

  = 1: thuật toán add-one

: đƣợc gọi là thuật toán Jeffreys - Perks 1   = 2

2.4.1.2.Phƣơng pháp làm mịn Witten - Bell

Thuật toán Witten-Bell hoạt động dựa trên nguyên tắc:

Khi gặp những cụm n-gram có tần số 0, ta coi đây là lần đầu tiên cụm từ

này xuất hiện. Nhƣ vậy, xác suất của cụm n-gram có tần số bằng 0 có thể tính

dựa vào xác suất gặp một cụm n-gram lần đầu tiên.

Với unigram, gọi T là số cụm unigram khác nhau đã xuất hiện, còn M là

tổng số các cụm unigram đã thống kê, khi đó tổng số sự kiện sẽ là (T+M), và

xác suất để gặp cụm unigram lần đầu tiên (hay tổng xác suất của các cụm

unigram chƣa xuất hiện lầnnào) đƣợc tính bằng: T T+M

Gọi V là kích thƣớc bộ từ vựng, còn Z là số cụm unigram chƣa xuất hiện

lần nào: Z = V - T

Xác suất xuất hiện của một cụm unigram chƣa xuất hiện lần nào (có tần

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

số bằng 0) đƣợc tính bằng:

P* = , và xác suất xuất hiện của các cụm unigram có tần T Z(T+M)

số khác 0 đƣợc tính lại theo công thức:

P(w) = với c(w) là số lần xuất hiện của cụm w c(w) T+M

Cũng giống thuật toán add-one, khi xét các cụm N-gram với n>1, thay M bằng C(wi-n+1...wi-1) thì xác suất của cụm wi-n+1...wi-1wi với C(wi-n+1...wi-1wi) = 0 đƣợc tính theo công thức sau:

. P(wi|wi-n+1...wi-1) = T(wi-n+1...wi-1) Z(wi-n+1...wi-1)(C(wi-n+1...wi-1) + T(wi-n+1...wi-1))

Với C(wi-n+1...wi-1wi) > 0, thì xác suất cụm (wi-n+1...wi-1wi) đƣợc tính bằng công thức:

P(wi|wi-n+1...wi-1) = C(wi-n+1...wi-1wi) C(wi-n+1...wi-1) + T(wi-n+1...wi-1)

2.4.1.3.Phƣơng pháp làm mịn Good - Turing

Thuật toán Good-Turing dựa trên việc tính toán Nc, với Nc là số cụm n-

gram xuất hiện c lần. Nhƣ vậy:

N0 là số cụm N-gram có tần số 0 (số cụm n-gram không xuất hiện lần

nào)

N1 là số cụm N-gram có tần số 1 (số cụm n-gram xuất hiện 1 lần)

…

Nc có thể hiểu đơn giản là: Nc =  w:count(w)=c

Khi đó, thuật toán Good-Turing sẽ thay thế tần số c bằng một tần số mới

c* theo công thức:

c* = (c+1) * Nc+1 Nc

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Xác suất của một cụm N-gram với tần số là c đƣợc tính lại theo công thức:

c =  với N =  c = 0

c =  Ncc =  c = 0

c =  Ncc* =  c = 0

P(w) = Nc+1(c+1) c* N

Trên thực tế, ngƣời ta không tính toán và thay thế mọi tần số c bởi một

tần số mới c*. Ngƣời ta chọn một ngƣỡng k nhất định, và chỉ thay thế tần số c

bởi tần số mới c* khi c nhỏ hơn hoặc bằng k, còn nếu c lớn hơn k thì giữ

nguyên tần số..

2.4.2.Phƣơng pháp truy hồi(back-off).

Trong các phƣơng pháp chiết khấu nhƣ phƣơng pháp Add-One hay Witten-Bell, nếu cụm (w1w2…wn) không xuất hiện trong tập huấn luyện, và cụm (w1w2…wn) cũng không xuất hiện, thì xác suất của cụm (w1w2…wn) sau khi làm mịn vẫn bằng 0. Phƣơng pháp truy hồi tránh rắc rối trên bằng cách

ƣớc lƣợng xác suất các cụm n-gram chƣa xuất hiện lần nào dựa vào xác suất

của các cụm N-gram ngắn hơn có xác suất khác 0.[9],[13].

Cụ thể, xác suất của cụm wi-n+1...wi-1wi đƣợc tính lại theo công thức sau:

P(wi|wi-n+1...wi-1) nếu C(wi-n+1...wi-1wi) > 0   * PB(wi|wi-n+2...wi-1) nếu C(wi-n+1...wi-1wi) = 0 

PB(wi|wi-n+1...wi-1)=

P(wi|wi-1) nếu C(wi-1wi) > 0 PB(wi|wi-1) =   * P(wi) nếu C(wi-1wi) = 0 

Áp dụng cho bigram, ta có:

Công thức trên có thể viết lại thành:

1 nếu C(x) = 0 0 nếu C(x) > 0  

PB(wi|wi-1) = P(wi|wi-1) + (wi-1wi) *  * P(wi) với u(x) =

Tƣơng tự, khi áp dụng cho trigram ta có:

PB(wi|wi-2wi-1)=

P(wi|wi-2wi-1) nếu C(wi-2wi-1wi ) > 0  1 * P(wi|wi-1) nếu C(wi-2wi-1wi ) = 0 và C(wi-1wi ) > 0  2 * P(wi) nếu C(wi-2wi-1wi ) = 0 và C(wi-1wi ) = 0

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Công thức trên cũng có thể viết lại thành:

PB(wi|wi-2wi-1) = P(wi|wi-2wi-1) + (wi-2wi-1wi)*1*P(wi|wi-1) + (wi-1wi)*2 * P(wi)

Sự chính xác của mô hình truy hồi phụ thuộc vào các tham số 1 và 2.

Có vài kỹ thuật giúp lựa chọn đƣợc những tham số này, tùy theo tập huấn

luyện và mô hình ngôn ngữ. Một cách đơn giản, có thể chọn 1 và 2 là các

hằng số. Tuy nhiên rất khó có thể chọn đƣợc hai hằng số để tổng xác suất của

tất cả các cụm n-gram không thay đổi. Việc chọn hằng số không chính xác, sẽ

làm ảnh hƣởng lớn đến độ chính xác của cả môhình ngôn ngữ. Do đó, ta có

thể chọn tham số  nhƣ một hàm của N-gram:

1 = 1(wi-1wi) và 2 = 2(wi-1wi)

Tuy nhiên, trong phƣơng pháp truy hồi, tổng xác suất của tất cả các

cụm n-gram sẽ luôn lớn hơn 1, do xác suất của các cụm n-gram đã xuất hiện

thì không thay đổi, trong khi xác suất của các cụm n-gram chƣa xuất hiện thì

đƣợc tăng lên. Do đó, để thuật toán chính xác hơn, thì ta cần kết hợp nó với

một thuật toán chiết khấu nhƣ Witten-Bell hay Good-Turing để làm giảm xác

suất của các cụm n-gram đã xuất hiện. Do đó, trong thực tế, chúng ta có công

thức sau:

P‟(wi|wi-2wi-1) nếu C(wi-2wi-1wi) > 0  1 * P‟(wi|wi-1) nếu C(wi-2wi-1wi) = 0 và C(wi-1wi) > 0 P(wi|wi-2wi-1) =  2 * P‟(wi) nếu C(wi-2wi-1wi) = 0 và C(wi-1wi) = 0

Trong đó P‟ chính là xác suất của cụm n-gram khi áp dụng thuật toán

làm mịn chiết khấu.

2.4.3.Phƣơng pháp nội suy(Interpolation)

Phƣơng pháp này có chung nguyên lý với phƣơng pháp truy hồi: “sử

dụng các cụm n-gram ngắn hơn để tính xác suất của cụm n-gram dài

hơn”[6],[8]. Tuy nhiên, phƣơng pháp này khác phƣơng pháp truy hồi ở điểm:

phƣơng pháp này không phụ thuộc vào sự xuất hiện của các cụm n-gram.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Công thức tính xác suất theo phƣơng pháp nội suy nhƣ sau:

PI(wi|wi-n+1...wi-1) = P(wi|wi-n+1...wi-1) + (1-)PI(wi|wi-n+2...wi-1)

Áp dụng cho bigram và trigram ta có:

PI(wi|wi-1) = P(wi|wi-1) + (1-)P(wi) PI(wi|wi-n+1...wi-1) = 1P(wi

i = 1 |wi-2wi-1) + 2P(wi|wi-1) + 3P(wi) với 

Ở công thức trên, do tổng của tất cả các tham số  bằng 1 nên để đơn

giản ta có thể chọn tất cả  bằng nhau và bằng . 1 3

Tuy nhiên, cũng có thể chọn các tham số  nhƣ là một hàm của N-gram:

1 = 1(wi-2wi-1wi), 2 = 2(wi-1wi) và 3 = 3(wi)

2.4.4.Phƣơng pháp làm mịn Kneser - Ney

Thuật toán Kneser-Ney xây dựng theo hai mô hình: truy hồi và nội suy,

tuy nhiên trong thuật toán này không cần phải áp dụng các thuật toán chiết

khấu trƣớc khi áp dụng công thức truy hồi.

nếu C(wi-n+1...wi) > 0

C(wi-n+1...wi) - D  C(wi-n+1...wi-1) PBKN(wi|wi-n+1..wi-1) =  (wi-n+1...wi-1)PBKN(wi|wi-n+2...wi-1) nếu C(wi-n+1...wi) = 0 

Trong đó:

N(vwi) - D

với N(vw) là số lƣợng từ v khác nhau xuất hiện

o PBKN(wi) =

N(vw)

 w

trƣớc w trong tập huấn luyện

C(wi-n+1..wi-1w) - D

 w:C(wi-n+1..wi-1w)>0

1 -

C(wi-n+1..wi-1)

o (wi-n+1..wi-1) =

1 -

PBKN(w|wi-n+2..wi-1)

 w:C(wi-n+1..wi-1w>0)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

a. Mô hình truy hồi:

Nhƣ vậy:

nếu C(wi-2wi-1wi) > 0

PBKN(wi|wi-2wi-1) =

C(wi-2wi-1wi) - D  C(wi-2wi-1)  

(wi-2wi-1)PBKN(wi|wi-1) nếu C(wi-2wi-1wi) = 0

nếu C(wi-1wi) > 0

C(wi-1wi) - D  C(wi-1) PBKN(wi|wi-1) =  

(wi-1)PBKN(wi) nếu C(wi-1wi) = 0

N(vwi) - D

PBKN(wi) =

N(vw)

 w

PIKN(wi|wi-n+1..wi-1) =

+ (wi-n+1..wi-1)PIKN(wi|wi-n+2..wi-1)

C(wi-n+1..wi) - D C(wi-n+1..wi-1)

Trong đó:

(wi-n+1..wi-1) =

với N(wi-n+1..wi-1v) là số lƣợng từ v khác

D N(wi-n+1..wi-1v) C(wi-n+1..wi-1)

nhau xuất hiện liền sau cụm wi-n+1..wi trong tập huấn luyện

N(vwi) - D

+ 

với N(vw) là số lƣợng từ v khác nhau xuất

o PIKN(wi) =

1 V

N(vw)

 w

hiện liền trƣớc từ w trong tập huấn luyện.

o  =

N(vw)

D N(v)  w

Nhƣ vậy:

PIKN(wi|wi-2wi-1) =

+ (wi-2wi-1)PIKN(wi|wi-1)

C(wi-2wi-1wi) - D C(wi-2wi-1)

PIKN(wi|wi-1) =

+ (wi-1)PIKN(wi)

C(wi-1wi) - D C(wi-1)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

b. Mô hình nội suy:

N(vwi) - D

+ 

PIKN(wi) =

1 V

N(vw)

 w

Trong cả 2 mô hình nội suy và truy hồi, D đƣợc chọn: D =

N1 N1 + 2N2

2.4.5.Phƣơng pháp làm mịn Chen - GoodMan

Công thức tính toán của thuật toán Kneser-Ney cải tiến bởi Chen và

GoodMan giống công thức của thuật toán Kneser-Ney, tuy nhiên hằng số D bị

thay đổi.

Chen và GoodMan chọn D nhƣ sau:

0 nếu c(wi-n+1..wi) = 0  D1 nếu c(wi-n+1.. wi) = 1 D =  D2 nếu c(wi-n+1.. wi) = 2  D3 nếu c(wi-n+1.. wi) >= 3

Với Y = N1 (N1 + 2N2)

D1 = 1 - 2Y N2 N1

D2 = 1 - 3Y N3 N2

D3 = 1 - 4Y N4 N3

Trong đó: Ni là số lƣợng cụm n-gram có số lần xuất hiện bằng i

Chú ý rằng: với mỗi bậc của n-gram ta lại có một bộ 3 hằng số trên. Điều

đó có nghĩa là: unigram, bigram, ... có các hằng số trên là khác nhau.

2.5.Kỹ thuật làm giảm kích thƣớc dữ liệu:

Các kỹ thuật này làm giảm kích thƣớc của mô hình ngôn ngữ. Mặc dù đều

có chung một mục tiêu, nhƣng mỗi kỹ thuật lại có hiệu quả khác nhau. Có ba

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

kỹ thuật chính, bao gồm:

● Pruning (loại bỏ): làm giảm số lƣợng các cụm n-gram trong mô hình ngôn ngữ bằng cách loại bỏ các cụm n-gram không quan trọng

● Quantization (lƣợng tử hóa): thay đổi lại cấu trúc thông tin của

● Compression (nén): nén cấu trúc dữ liệu sử dụng trong việc lƣu trữ

mỗi cụm n-gram trong mô hình ngôn ngữ.

các cụm n-gram trong mô hình ngôn ngữ

2.5.1.Đồng hóa (Quantization):

Thuật toán quantization (đồng hóa) làm giảm số lƣợng bit dùng để lƣu

trữ các biến trong mô hình ngôn ngữ. Thuật toán này gồm hai bƣớc chính

Bƣớc thứ nhất, liệt kê và lƣu trữ tất cả các tần số của các cụm n-gram

vào một bảng. Sau đó, thay thế tần số của các cụm n-gram trong mô hình

ngôn ngữ bằng chỉ số của tần số trong bảng. Nhƣ vậy, thay vì sử dụng b =

log(tần số lớn nhất) bit để lƣu trữ tần số của một cụm n-gram, thì chúng ta chỉ

cần sử dụng b‟ = log(kích thƣớc của bảng) bit cho mỗi cụm n-gram. Do kích

thƣớc của bảng nhỏ hơn nhiều so với giá trị tần số lớn nhất của các cụm n-

gram nên b‟ < b, tức là kích thƣớc mô hình ngôn ngữ đã giảm so với cách lƣu trữ ban đầu.

Tuy nhiên, để tăng tính hiệu quả, ở bƣớc thứ hai, thuật toán này đồng

hóa một số giá trị trong bảng tần số. Điều đó có nghĩa là, một số giá trị trong

bảng có giá trị gần với nhau sẽ đƣợc thay thế bằng một con số chung. Sau

bƣớc này, chúng ta sẽ thu đƣợc một bảng tần số với ít giá trị hơn, cũng tức là

đã làm giảm kích thƣớc của mô hình ngôn ngữ đi một lần nữa.

2.5.2.Loại bỏ (pruning):

Số lƣợng các cụm n-gram xuất hiện vài lần trong tập huấn luyện

thƣờng là lớn so với tổng số các cụm n-gram. Các cụm n-gram đó thƣờng là

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

lỗi ngữ pháp trong tập huấn luyện, hoặc là một số dạng đặc biệt nhƣ: tên riêng, từ viết tắt,.[13]. Những cụm n-gram này thƣờng rất ít sử dụng trong thực tế, do đó việc tồn tại của chúng có thể làm ảnh hƣởng đến độ chính xác

● Cut-off (cắt bỏ): phƣơng pháp này tập trung vào việc loại bỏ các

của mô hình ngôn ngữ. Chính vì lý do đó, kỹ thuật pruning tập trung vào việc loại bỏ các cụm n-gram nhƣ vậy. Có 2 phƣơng pháp chính:

● Weighted difference: phƣơng pháp này tập trung vào việc đánh

cụm Ngram có tần số thấp trong tập huấn luyện

giá và loại bỏ các cụm Ngram không hiệu quả dựa vào xác suất

của các cụm Ngram trƣớc và sau khi làm mịn theo phƣơng pháp

truy hồi.

2.5.2.1.Cắt bỏ (cut-off):

Phƣơng pháp này là phƣơng pháp thông dụng, thƣờng đƣợc sử dụng để

làm giảm kích thƣớc mô hình ngôn ngữ. Trong thực tế, trong tập văn bản

huấn luyện, có rất nhiều cụm bigram và trigram chỉ xuất hiện một hoặc hai lần

trong đoạn văn bản chứa trên một triệu từ. Khi loại bỏ các cụm n-gram này ra

khỏi mô hình ngôn ngữ, thông tin về chúng (bao gồm tần số và xác suất) của

chúng vẫn có thể nhận lại đƣợc thông qua việc sử dụng mô hình truy hồi hay

nội suy.

Phƣơng pháp cut-off hoạt động nhƣ sau: Nếu cụm n-gram xuất hiện ít hơn

k lần trong tập văn bản huấn luyện thì cụm n-gram đó sẽ bị loại bỏ ra khỏi mô

hình ngôn ngữ. Khi tính toán, nếu gặp lại các cụm n-gram này, thì tần số và

xác suất của chúng sẽ đƣợc tính toán thông qua các phƣơng pháp làm mịn đã

trình bày ở trên.

Trong một mô hình ngôn ngữ, chúng ta có thể sử dụng các tham số k khác

nhau với các cụm n-gram có độ dài khác nhau. Ví dụ: với unigram thì sử dụng k = 10, với bigram thì k = 1, và trigram thì k =5

Nhƣ vậy, việc chọn tham số k cho phƣơng pháp cut-off chính là vấn đề

chính của kỹ thuật này. Nếu k quá lớn, chúng ta sẽ bỏ sót thông tin về một số

cụm n-gram, hiệu suất của ứng dụng cũng bị giảm. Nhƣng ngƣợc lại, nếu k

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

quá nhỏ, thì kích thƣớc của mô hình ngôn ngữ cũng giảm không đáng kể. Có

2 cách để chọn k: chọn k theo phƣơng pháp chạy thử nhiều lần hoặc chọn k theo tỉ lệ phần trăm của số lƣợng các cụm n-gram.

Chọn k theo phƣơng pháp chạy thử nhiều lần nghĩa là ta dùng phƣơng

pháp cut-off cho mô hình ngôn ngữ với nhiều giá trị k khác nhau rồi đánh giá

độ hỗn loạn thông tin(perplexity) của tập văn bản đầu vào sau khi sử dụng

phƣơng pháp cut-off. Sau khi có kết quả, ta sẽ chọn tham số k sao cho mô

hình ngôn ngữ là hiệu quả nhất (độ hỗn loạn thông tin của tập văn bản huấn

luyện và kích thƣớc mô hình ngôn ngữ đều thấp). Kỹ thuật này giúp chúng ta

chọn đƣợc k phù hợp, tuy nhiên rất mất thời gian do phải chạy thử với rất

nhiều giá trị của k. Tuy nhiên, để đạt đƣợc một mô hình ngôn ngữ hiệu quả thì

đây là một phƣơng pháp tốt.

Phƣơng pháp thứ hai, chọn k dựa theo tỷ lệ phần trăm của số lƣợng các

cụm n-gram phải bảo đảm rằng số cụm n-gram xuất hiện không quá k lần

chiếm h% so với tổng số các cụm n-gram.

Ví dụ 2.3: Nếu h=50, thì chọn k sao cho số lƣợng các cụm n-gram xuất

hiện không quá k lần (sẽ bị loại bỏ) chiếm 50% tổng số các cụm n-gram đã

thống kê. Phƣơng pháp này tuy nhanh hơn nhƣng độ chính xác không cao

bằng phƣơng pháp thứ nhất đã đề cập ở trên

2.5.2.2.Sự khác biệt trọng số (Weighted difference):

Phƣơng pháp cut-off chỉ quan tâm đến việc loại bỏ các cụm n-gram có

tần số thấp, trong khi phƣơng pháp weighted difference(sự khác biệt trọng số)

thì quan tâm đến nhiều thông tin trong mô hình ngôn ngữ hơn nhƣ mối quan hệ giữa các cụm n-gram, xác suất của từng cụm n-gram[13]. Nhƣ đã trình bày ở các phần trên, nếu một cụm n-gram không xuất hiện trong tập huấn luyện,

thì xác suất của nó đƣợc ƣớc lƣợng thông qua xác suất của các cụm n-gram

ngắn hơn (phƣơng pháp làm mịn kiểu truy hồi) Do đó, nếu xác suất thực tế

của một cụm n-gram xấp xỉ với xác suất có đƣợc theo công thức truy hồi, thì

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

chúng ta chẳng cần lƣu trữ cụm n-gram đó làm gì nữa. Đó chính là ý tƣởng

của phƣơng pháp weighted difference. Sự khác biệt trọng số của một cụm n- gram đƣợc định nghĩa bằng:

w.d.factor = K * log((xác suất ban đầu) - log(xác suất truy hồi))

K chính là tham số sử dụng trong phƣơng pháp làm mịn Good Turing.

Dựa vào nhân tố w.d.factor ở trên, chúng ta sẽ biết nên giữ lại hay loại bỏ một

cụm n-gram. Nếu w.d.factor nhỏ hơn một ngƣỡng nhất định, thì cụm n-gram

đó sẽ bị loại bỏ khỏi mô hình ngôn ngữ. Và ngƣỡng nhất định đó chúng ta có

thể bằng cách tìm theo phƣơng pháp thử sai hoặc đặt nó bằng một giá trị hằng

số.

Trong thực tế, phƣơng pháp này mất nhiều thời gian hơn phƣơng pháp

cut-off do phải tính toán hệ số w.d.factor cho tất cả các cụm n-gram trong mô

hình ngôn ngữ. Và sự khác biệt lớn nhất giữa 2 phƣơng pháp loại bỏ này

chính là phƣơng pháp weighted different chỉ hoạt động trong mô hình ngôn

ngữ kiểu truy hồi, còn phƣơng pháp cut-off thì chỉ hoạt động trong mô hình ngôn ngữ lƣu trữ dữ liệu dƣới dạng tần số.

2.5.3.Nén (Compression)

Mô hình ngôn ngữ nào cũng có một cấu trúc dữ liệu. Do đó nếu cấu trúc

dữ liệu đó đƣợc nén lại bằng các thuật toán nén, thì kích thƣớc của mô hình

ngôn ngữ tất nhiên là giảm. Tuy nhiên, khi một mô hình ngôn ngữ bị nén, thì

độ chính xác và tốc độ của mô hình ngôn ngữ đều giảm (do phải giải nén,

hoặc bị mất dữ liệu do thuật toán nén chƣa tốt)[13]. Do không hiệu quả nên

kỹ thuật này hiện nay không còn phổ biến nhƣ hai kỹ thuật trên.

2.6.Độ đo

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

● Entropy - Độ đo thông tin ● Perplexity - Độ hỗn loạn thông tin

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

đá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ữ:

● Error rate - Tỉ lệ lỗi

2.6.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 một ngôn ngữ, và dự đoán đƣợc từ tiếp theo trong cụm n-gram[6],[13].

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

H(X) = -  p(x)log2p(x) x  X

Xét các câu gồm hữu hạn m từ W = (w1, w2, ..., wm) trong ngôn ngữ L.

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

H(w1, w2, ..., wm) = -  p(w1, w2, ..., wm)log2p(w1, w2, ..., wm) W  L

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:

H(w1, w2, ..., wm) = - p(w1, w2, ..., wm)log2p(w1, w2, ..., 1 m 1 m  W  L

wm)

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[2]. 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:

H(w1, w2, ..., wm) 1 m H(L) = - lim m 

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

p(w1, w2, ..., wm)log2p(w1, w2, ..., wm) 1 m = - lim m   W  L

Đị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:

log p(w1,w2,...,wm) 1 m H(L) = - lim m 

Với công thức nhƣ ở 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 P(w1,w2,...,wn):

log [ p(wn|w1w2..wn-1) * p(wn+1|w2w3.. wn) * ... * p(wm|wm-n+1 1 m H(L) = - lim m 

...wm-1) ]

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.

Độ hỗn loạn thông tin (perplexity) cũng đƣợc dùng làm thƣớc đo để đánh giá độ chính xác của một mô hình ngôn ngữ. Trong mô hình ngôn ngữ, độ hỗn loạn

thông tin của một văn bản với từ “cái” thể hiện số từ có thể đi sau từ “cái”. Độ hỗn loạn thông tin của một mô hình ngôn ngữ nói chung, có thể hiểu đơn giản là số lựa chọn từ trung bình mà mô hình ngôn ngữ phải đƣa ra quyết định. Nhƣ vậy, độ hỗn

loạn thông tin càng thấp, thì độ chính xác của mô hình ngôn ngữ càng cao.

Độ hỗn loạn thông tin có thể tính theo công thức:

P(L) = 2H(L)

2.6.2. Perplexity – Độ hỗn loạn thông tin:

Ví du 2.4: L dãy kí tự a, b, …, z có perplexity là 26 còn bảng mã ASCII có

perplexity là 256.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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ữ[13] .

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.

2.6.3.Error rate – Tỉ lệ lỗi:

2.7.Tổng kết chƣơng

Trong chƣơng 2, tác giả tập trung vào nghiên cứu mô hình ngôn ngữ

N-gram nhƣ:

-Các phƣơng pháp làm mịn

-Các kỹ thuật làm giảm kích thƣớc dữ liệu.

Để xây dựng đƣợc mô hình ngôn ngữ có hiệu quả thì cần phải có cách

đánh giá chúng. Từ những vấn đề nêu trên tác giả cũng đã đề cập đến một số

● Entropy - Độ đo thông tin ● Perplexity - Độ hỗn loạn thông tin ● Error rate - Tỉ lệ lỗi

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

phƣơng pháp đánh giá một mô hình ngôn ngữ nhƣ:

CHƢƠNG 3: XÂY DỰNG N-GRAM CHO TIẾNG VIỆT

3.1.Giới thiệu

Kho văn bản mà trong đó mỗi câu đƣợc chú giải cấu trúc cú pháp là

nguồn tài nguyên rất hữu ích trong lĩnh vực xử lý ngôn ngữ tự nhiên. Kho văn

bản này đƣợc gọi là treebank. Treebank có nhiều ứng dụng quan trọng nhƣ

đánh giá, kiểm định các công cụ xử lí ngôn ngữ tự động, các phần mềm dịch

máy, tóm tắt văn bản, các hệ thống hỏi đáp…

3.2.Công cụ tách từ cho tiếng Việt - vnTokenizer

VnTokenizer là công cụ tách từ tiếng Việt đƣợc nhóm tác giả Nguyễn

Thị Minh Huyền, Vũ Xuân Lƣơng và Lê Hồng Phƣơng phát triển dựa trên

phƣơng pháp so khớp tối đa (Maximum Matching) với tập dữ liệu sử dụng là

bảng âm tiết tiếng Việt và từ điển từ vựng tiếng Việt.

Công cụ đƣợc xây dựng bằng ngôn ngữ Java, mã nguồn mở. Có thể đễ

dàng sửa đổi nâng cấp và tích hợp vào các hệ thống phân tích văn bản tiếng

Việt khác.

Văn bản

Chuyển các đơn vị từ

Tách từ

Từ điển

Quy trình thực hiện tách từ theo phƣơng pháp khớp tối đa:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Hình 3-1. Quy trình tách từ

- Đầu vào của công cụ tách từ vnTokenizer là một câu hoặc một văn bản

đƣợc lƣu dƣới dạng tệp.

- Đầu ra là một chuỗi các đơn vị từ đƣợc tách.

- Các đơn vị từ bao gồm các từ trong từ điển cũng nhƣ các chuỗi số,

chuỗi kí từ nƣớc ngoài. Các đơn vị từ không chỉ bao gồm các từ có trong từ

điển, mà cả các từ mới hoặc các từ đƣợc sinh tự do theo một quy tắc nào đó

(nhƣ phƣơng thức thêm phụ tố hay phƣơng thức láy) hoặc các chuỗi kí hiệu

không đƣợc liệt kê trong từ điển.

Công cụ sử dụng tập dữ liệu đi kèm là tập từ điển từ vựng tiếng Việt,

danh sách các đơn vị từ mới bổ sung, đƣợc biểu diễn bằng ôtômat tối thiểu

hữu hạn trạng thái, tệp chứa các biểu thức chính quy cho phép lọc các đơn vị

từ đặc biệt (xâu dạng số, ngày tháng,…), và các tệp chứa các thống kê

unigram và bigram trên kho văn bản tách từ mẫu.

Với các đơn vị từ đã có trong từ điển, khi thực hiện tách từ cũng đƣợc

xử lý hiện tƣợng nhập nhằng bằng cách kết hợp với các thống kê unigram và

bigram. Chẳng hạn trong tiếng Việt thƣờng gặp các trƣờng hợp nhập nhằng

nhƣ:

- Xâu AB vừa có thể hiểu là 1 đơn vị từ, vừa có thể là chuỗi 2 đơn vị

từ A-B.

- Xâu ABC có thể tách thành 2 đơn vị AB-C hoặc A-BC.

3.3.Bộ công cụ SRILM

SRILM là bộ công cụ để xây dựng và áp dụng các mô hình ngôn ngữ thống kê, và các mô hình ngôn ngữ này chủ yếu là để sử dụng trong các bài toán của nhận dạng tiếng nói, gắn thẻ thống kê và phân khúc, và dịch máy

thống kê. Bộ công cụ này đƣợc phát triển bởi “Phòng thí nghiệm và nghiên

cứu công nghệ giọng nói SRI” từ năm 1995, có thể chạy trên nền tảng Linux

cũng nhƣ Windows.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

SRILM bao gồm các thành phần sau:

● Một tập hợp các thƣ viện C++ giúp cài đặt mô hình ngôn ngữ, hỗ

● Một tập hợp các chƣơng trình thực thi thực hiện nhiệm vụ xây

trợ cấu trúc dữ liệu và các chức năng tiện ích nhỏ.

dựng mô hình ngôn ngữ, đào tạo và thử nghiệm mô hình ngôn ngữ

trên dữ liệu, gắn thẻ hoặc phân chia văn bản, ...

Bộ công cụ SRILM có rất nhiều chƣơng trình con, để xây dựng mô hình

ngôn ngữ ta sử dụng 2 chƣơng trình chính sau:

3.3.1.N-gram-count.

Chƣơng trình N-gram-count thống kê tần số xuất hiện của các cụm N-

gram. Kết quả của việc thống kê đƣợc ghi lại vào một tệp hoặc sử dụng chúng

để xây dựng mô hình ngôn ngữ[6]. Kết quả của việc thống kê đƣợc ghi lại

theo định dạng sau:

\data\

ngram 1=n1

ngram 2=n2

...

ngram N=nN

\1-grams:

p w [bow]

...

\2-grams:

p w1 w2 [bow]

...

\N-grams:

p w1 ... wN

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

...

\end\

Văn bản trên bắt đầu với một tiêu đề giới thiệu số lƣợng các cụm N-

gram với chiều dài là 1, 2, ...n. Tiếp theo, là từng đoạn chứa thông tin về các

cụm N-gram có độ dài từ 1 đến n, mỗi đoạn bắt đầu bằng từ khóa \N-grams:

trong đó N là độ dài của các cụm N-gram đƣợc liệt kê ở bên dƣới. Mỗi dòng

tiếp theo của từng đoạn bắt đầu bằng một số thực là logarit cơ số 10 xác suất

của cụm N-gram, tiếp theo là n từ w1, w2, ... wn của cụm Ngram đó, và cuối

cùng là trọng số truy hồi của cụm N-gram đó (có thể có)

Chƣơng trình N-gram có một số tùy chọn chính sau:

-text textfile: thống kê tần số các cụm N-gram từ tệp văn bản đầu vào

textfile. Tệp văn bản này có thể chứa mỗi câu trên một dòng. Kí hiệu kết thúc

và bắt đầu dòng mới sẽ đƣợc tự động thêm vào nếu trong tệp đầu vào chƣa có.

Các dòng trống trong tệp này cũng bị loại bỏ.

-order n : thiết lập độ dài lớn nhất của các cụm N-gram sẽ thống kê bằng

n. Giá trị mặc định nếu không thiết lập tham số này là n = 3

-memuse: hiển thị thông tin bộ nhớ mà chƣơng trình sử dụng

-lm lmfile: xây dựng mô hình ngôn ngữ truy hồi từ các tần số vừa thống

kê, sau đó ghi lại vào tệp lmfile theo định dạng ở trên.

-gtnmin count: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9.

Tham số này thiết lập giá trị tần số nhỏ nhất với các cụm N-gram có độ dài là

n. Tất cả các cụm n-gram có độ dài là n, có tần số nhỏ hơn count sẽ bị loại bỏ

khỏi mô hình ngôn ngữ

Và dƣới đây là một số tham số thiết lập phƣơng pháp làm mịn cho mô

hình ngôn ngữ. Nếu không tham số nào dƣới đây đƣợc thiết lập thì chƣơng

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

trình sẽ sử dụng phƣơng pháp làm mịn Good-Turing.

-wbdiscountn: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9. Sử

dụng phƣơng pháp làm mịn Witten-Bell cho N-gram với độ dài là n.

-kndiscountn: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9. Sử

dụng phƣơng pháp làm mịn của Kneser-Ney đƣợc thay đổi bởi Chen và

GoodMan cho N-gram với độ dài là n.

-ukndiscountn: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9. Sử

dụng phƣơng pháp làm mịn của Kneser-Ney với độ dài là n.

-addsmoothn delta: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9.

Làm mịn bằng cách thêm một lƣợng delta vào tần số của tất cả các cụm N-

gram với độ dài là n.

-interpolaten: với n nhận các giá trị là 1, 2, 3, 4, 5, 6, 7, 8, hoặc 9. Tính

toán tần số của các cụm N-gram có độ dài là n bằng cách nội suy từ các cụm

Ngram có độ dài nhỏ hơn.

3.3.2.N-gram

N-gram là chƣơng trình áp dụng mô hình ngôn ngữ để tính xác suất của

một câu, tính toán độ hỗn loạn thông tin của văn bản, hay dùng để sinh các

câu tiếp theo của một văn bản, còn việc tính toán của chƣơng trình bị chi phối

bởi các tham số chính nhƣ sau:

-order n : thiết lập độ dài lớn nhất của các cụm N-gram sẽ thống kê bằng

n. Giá trị mặc định nếu không thiết lập tham số này là n = 3

-memuse: hiển thị thông tin bộ nhớ mà chƣơng trình sử dụng

-lm file: đọc mô hình ngôn ngữ từ tệp file. Tham số này là tham số bắt

buộc, trừ khi tham số -null đƣợc chọn.

-null: không sử dụng mô hình ngôn ngữ đọc từ tệp, mà sử dụng một mô

hình ngôn ngữ đặt biệt (xác suất bằng 1 cho tất cả các từ). Tham số này

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

thƣờng đƣợc sử dụng trong việc gỡ lỗi.

-ppl textfile: tính toán điểm(logarit cơ số 10 của xác suất) và độ hỗn loạn

thông tin của tất cả các câu trong tệp textfile, mỗi câu viết trên một dòng.

-gen number: sinh ngẫu nhiên number câu từ mô hình ngôn ngữ.

3.4.Bộ công cụ trợ giúp xây dựng tập văn bản huấn luyện

Bộ công cụ này đƣợc cài đặt bằng ngôn ngữ C#. Bộ công cụ có các công

cụ nhƣ: lấy nội dung văn bản từ các trang báo mạng, chuẩn hóa văn bản, cắt

và ghép các tệp văn bản.

Để có kích thƣớc tệp văn bản lớn phục vụ cho quá trình huấn luyện mô

hình ngôn ngữ, chúng tôi đã phải xây dựng một chƣơng trình có nhiệm vụ lọc

nội dung văn bản từ các file html. Chƣơng trình này tự động tìm tất cả các file

có định dạng html trong một thƣ mục nào đó, bỏ các đoạn mã, bỏ các thẻ,

link, bảng, hình ảnh, ... chỉ giữ lại nội dung văn bản rồi ghi lại dƣới định dạng

txt.

Sau đó, chúng tôi tiếp tục xây dựng một chƣơng trình khác, có nhiệm vụ

chuẩn hóa văn bản. Chƣơng trình này có các chức năng chính nhƣ: chuẩn hóa

dấu cách, chuẩn hóa dấu cho tiếng Việt (ví dụ: hoà sửa thành hòa, vìên sửa

thành viền, ...), tách ra mỗi câu trên một dòng. Đặc biệt, do văn bản đầu ra của

chƣơng trình dùng cho quá trình huấn luyện mô hình ngôn ngữ, nên chƣơng

trình này của chúng tôi còn có thêm một số tính năng nhƣ: thay thế các từ đặc

biệt bởi một từ nào đó đặc trƣng hơn (ví dụ: tên ngƣời, số, ngày tháng, ...),

xóa bỏ các câu quá ngắn, xóa bỏ các câu các từ không có trong từ điển tiếng

Việt.

Ngoài ra, để tăng và giảm kích thƣớc tệp văn bản một cách dễ dàng,

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

chúng tôi còn xây dựng thêm các tiện ích cắt và ghép tệp văn bản. Tiện ích

này giúp ngƣời dùng dễ dàng tạo đƣợc file văn bản có kích thƣớc phù hợp để

dễ dàng huấn luyện và khảo sát mô hình ngôn ngữ.

3.5.Phƣơng pháp tách câu, tách từ, gán nhãn từ loại và phân tích cú pháp.

3.5.1.Tách câu.

Vấn đề tách một văn bản ra thành các đơn vi câu độc lập dƣờng nhƣ

đƣợc ít các nhà nghiên cứu quan tâm nhất, mặc dù nó cũng là phần việc quan

trọng trong phân tích văn bản. Để tách một văn bản ra thành các đơn vi câu

độc lập đối với tiếng Việt không đơn thuần là chỉ dựa vào các dấu hiệu kết

câu (dấu chấm „.‟, dấu chấm than „!‟ và dấu chấm hỏi „?‟). Vẫn có những câu

tiếng Việt mà các dấu hiệu kết câu đó vẫn chƣa phải là kết câu. Ví dụ nhƣ

“Giá xăng mới tăng lên thành 21.000 đồng/lít”, hay “Tp.Hà Nội”, “TS.Vũ Tất

Thắng”,…

Theo tạp chí Computational Linguistics, đối với các ngôn ngữ Âu –

Mỹ, trong thời gần đây có một số bài báo giới thiệu một số phƣơng pháp và

hệ thống tách câu. Các phƣơng pháp chủ yếu là dựa trên luật, học máy có

giám sát và học máy không giám sát.

Trong văn bản tiếng Anh hay bất kỳ ngôn ngữ thông dụng nào khác,

thông thƣờng thì ta chỉ dùng dấu chấm(.), chấm than(!), chấm hỏi(?) và một

số dấu khác để nhận biết kết thúc câu. Tuy nhiên do tính nhập nhằng của dấu

báo hiệu kết thúc câu ( chẳng hạn nhƣ kết thúc câu trong từ viết tắt,…) nên

việc xác định ranh giới câu không đơn giản chút nào.

Ví dụ 3.1:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

1. The group inclided Dr.J.M.Freeman and T. Boone Pickens Jr.

2. “This issue crosses party lines and crosses philosophical lines! said

Rep. John Rowland (R.,Conn.).

3.It was due Friday 5 p.m. Saturday would be too late.

4.She has an appointment at 5 p.m. Saturday to get her car fixed.

Trong trƣờng hợp 1 và 2 từ nằm ngay trƣớc hoặc ngay sau dấu chấm

câu cho ta những thông tin quan trọng về vai trò của dấu trong câu.Tuy nhiên,

bộ phận tách câu cần phải có nhiều thông tin về ngữ cảnh hơn trong trƣờng

hợp việc chấm câu xuất hiện ở một câu con trong dấu ngoặc đơn hoặc ngoặc

kép nhƣ trong trƣờng hợp 2; hay khi chữ viết tắt xuất hiện ở cuối câu nhƣ

trong trƣờng hợp 3,4. Để nhận diện dấu chấm câu, ngƣời ta có thể dùng

cácheuristics hoặc các mô hình học phức tạp hơn nhƣ: mạng neural.

Tách câu bằng Heristics.

Sau khi nhận đoạn văn bản đã đƣợc lọc các ký tự dƣ thừa, các ký tự

phụ, bộ phận tách câu bắt đầu phân tích dựa trên cách chấm câu và ngữ nghĩa

một số từ để tách ra các câu riêng biệt.

 Xử lý dấu chấm:

Dấu chấm “.” là dấu có nhiều trƣờng hợp mơ hồ nhất. Sau đây sẽ một

số ví dụ dấu chấm xuất hiện.

Ví dụ 3.2:

1.Dấu chấm kết thúc câu.

2. Dấu chấm thập phân trong chữ số (1,345.567)

3. Dấu chấm biểu thị sự viết tắt (Mr.,Dr.,…)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

4.Dấu chấm trong các trƣờng hợp email (caoductu.hui@gamil.com)

Để có thể phân biệt đƣợc các trƣờng hợp trên ta có thể dựa vào một số

đặc trƣng riêng trong cách trình bày của từng trƣờng hợp.

1. Nếu dấu chấm không thuộc các trƣờng hợp (2,3,4) thì dấu hiệu để

nhận biết kết thúc sẽ là: “ Luôn luôn có ít nhất một khoàn trắng sau dấu chấm

và ký tự tiếp theo sẽ là chữ cái sẽ đƣợc viết hoa”.

2.Ta có thể nhận biết dấu chấm thập phân bằng cách đọc toàn bộ phần

liền trƣớc và phần liền sau dấu chấm để phát hiện số có dấu chấm thập phân.

3.Để nhận biết dấu chấm trong các trƣờng hợp các từ viết tắt, ta xây

dựng một danh sách các từ viết tắt để tra cứu khi cần.

4. Trƣờng hợp này là trƣờng hợp đa dạng nhất, nhƣng vẫn có tính chất

chung là dấu chấm không bao giờ nằm cuối từ, luôn ở giữa hai ký tự nào đó (

nghĩa là không có khoảng trắng liền sau) nên có thể dễ dàng phân biệt đƣơc.

Những quy luật trên đây là những quy luật chung nhất trong cách trình

bày văn bản tiếng Anh. Đối với văn bản tiếng Việt, các trƣờng hợp cững nhƣ

thế. Do dựa chủ yếu vào cách trình bày văn bản nên có điểm yếu là dễ nhầm

lẫn khi văn bản đƣa vào có cách trình bày khác chuẩn và do không hiểu nghĩa

câu nên không thể phân biệt một số trƣờng hợp mơ hồ nhƣ trong ví dụ sau:

Ví dụ 3.3:

1. It was due Friday 5p.m. Saturday would be too late.

2.She has an appointment at 5 p.m. Saturday to get her car fixed.

Để xác định đƣợc dấu chấm ( in đậm) trong 2 trƣờng hợp trên có phải

là dấu chấm hết câu không cũng là việc không đơn giản đối với máy. Thậm

chí đối với con ngƣời mà trình độ tiếng Anh chƣa vững. Trong cả hai trƣờng

hợp, từ ngay trƣớc hoặc ngay sau dấu chấm câu cho ta những thông tin quan

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

trọng về vai trò của dấu trong câu.Tuy nhiên bộ phận tách câu sẽ phải cần

nhiều thông tin về ngữ cảnh và cú pháp hơn trong trƣờng hợp sự chấm câu

xuất hiện ở một câu con nhƣ trong trƣờng hợp 1.

 Xử lý dấu chấm trong ngoặc.

Khi bộ tách câu gặp dấu mở ngoặc đơn hoặc ngoặc kép thì nó sẽ quét

trong đoạn văn bản đang xét để tìm dấu đóng tƣơng ứng. Nếu tìm thấy, toàn

bộ phần trong ngoặc sẽ đƣợc giữ nguyên và tìm câu kết thúc câu tiếp theo

ngoài dấu ngoặc. Nếu không tìm thấy dấu đóng tƣơng ứng, dấu mở sẽ bị bỏ

qua và xử lý tiếp ký tự sau dấu mở nhƣ bình thƣờng.

3.5.2.Tách từ

Trong những năm gần đây có nhiều công trình nghiên cứu để giải quyết

bài toán tách từ tiếng Việt. Các nghiên cứu này thƣờng tập trung vào 2 hƣớng

tiếp cận lớn để giải quyết bài toán này là tách từ dựa trên đơn vị từ và tách từ

dựa trên âm tiết.

 Hƣớng tiếp cận dựa trên đơn vị từ:

Hƣớng tiếp cận dựa trên từ với mục tiêu tách đƣợc các từ hoàn chỉnh

trong câu. Hƣớng tiếp cận này có thể chia ra theo ba hƣớng: dựa trên thống kê

(statistics - based), dựa trên từ điển (dictionary – based) và hydrid (kết hợp

nhiều phƣơng pháp với hy vọng đạt đƣợc những ƣu điểm của các phƣơng

pháp này)

 Hƣớng tiếp cận dựa trên thống kê: Dựa trên các thông tin nhƣ tần số

xuất hiện của từ trong tập huấn luyện ban đầu. Hƣớng tiếp cận này đặc

biệt dựa trên tập ngữ liệu huấn luyện, nhờ vậy nên hƣớng tiếp cận này

tỏ ra linh hoạt và hữu dụng trong nhiều lĩnh vực khác nhau.

 Hƣớng tiếp cận dựa trên từ điển: Ý tƣởng của hƣớng tiếp cận này là

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

những cụm từ đƣợc tách ra từ văn bản phải đƣợc so khớp với các từ

trong từ điển. Do đó trong hƣớng tiếp cận này đòi hỏi từ điển riêng cho

từng lĩnh vực quan tâm. Hƣớng tiếp cận “full word / phrase” cần sử

dụng một từ điển hoàn chỉnh để có thể tách đƣợc đầy đủ các từ hoặc

ngữ trong văn bản, trong khi đó hƣớng tiếp cận thành phần

“component” lại sử dụng từ điển thành phần. Từ điển thành phần chỉ

chứa các thành phần của từ và ngữ nhƣ hình vị và các từ đơn giản.

Hƣớng tiếp cận theo từ điển vẫn còn một số hạn chế trong việc tách từ

vì thực hiện hoàn toàn dựa vào từ điển. Nếu nhƣ thực hiện thao tác tách

từ bằng cách sử dụng từ điển hoàn chỉnh thì trong thực tế việc xây dựng

một bộ từ điển hoàn chỉnh là khó thực hiện vì đòi hỏi nhiều thời gian và

công sức. Nếu tiếp cận theo hƣớng sử dụng từ điển thành phần thì sẽ

giảm nhẹ hạn chế, khó khăn khi xây dựng từ điển, vì khi đó chúng ta sẽ

sử dụng các hình vị từ và các từ đơn giản và các từ khác để hình thành

nên từ, cụm từ hoàn chỉnh.

 Hƣớng tiếp cận theo Hybrid: Với mục đích kết hợp các hƣớng tiếp

cận khác nhau để thừa hƣởng đƣợc các ƣu điểm của nhiều kỹ thuật và

các hƣớng tiếp cận khác nhau nhằm nâng cao kết qủa. Hƣớng tiếp cận

này thƣờng kết hợp giữa hƣớng dựa trên thống kê và dựa trên từ điển

nhằm tận dụng các mặt mạnh của các phƣơng pháp này. Tuy nhiên

hƣớng tiếp cận Hybrid lại mất nhiều thời gian xử lý, không gian đĩa và

đòi hỏi nhiều chi phí.

 Hƣớng tiếp cận dựa trên đơn vị âm tiết

Trong tiếng Việt, hình vị nhỏ nhất là âm tiết (tiếng) đƣợc hình thành

bởi nhiều ký tự trong bảng chữ cái. Hƣớng tiếp cận này đơn thuần rút trích ra

một số lƣợng nhất định các tiếng trong văn bản nhƣ rút trích từ 1 ký tự

(unigram) hay nhiều ký tự (n-gram) và cũng mang lại một số kết qủa nhất

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

định. Qua nhiều công trình nghiên cứu của các tác giả đã đƣợc công bố,

hƣớng tiếp cận tách từ dựa trên nhiều ký tự, cụ thể là cách tách từ hai ký tự

đƣợc cho là sự lựa chọn thích hợp.

3.5.3.Gán nhãn từ loại

Gán nhãn từ loại chính là việc xác định chức năng ngữ pháp của từ

trong câu. Đây là bƣớc cơ bản khi phân tích sâu văn phạm hay các vấn đề xử

lý ngôn ngữ phức tạp khác.

Quá trình gán nhãn có thể đƣợc chia thành các bƣớc sau:

 Gán nhãn tiên nghiệm, tức là tìm cho mỗi từ tập tất cả các nhãn từ loại

mà nó có thể có. Tập nhãn này có thể thu đƣợc từ cơ sở dữ liệu từ điển

hoặc kho văn bản đã gán nhãn bằng tay. Đối với một từ mới chƣa xuất

hiện trong cơ sở ngữ liệu thì có thể dùng một nhãn ngầm định hoặc gắn

cho nó tập tất cả các nhãn. Trong các ngôn ngữ biến đổi hình thái ngƣời

ta cũng dựa vào hình thái từ để đoán nhận lớp từ loại tƣơng ứng của từ

đang xét.

 Quyết định kết quả gán nhãn, đó là giai đoạn loại bỏ nhập nhằng, tức là

lựa chọn cho mỗi từ một nhãn phù hợp nhất với ngữ cảnh trong tập

nhãn tiên nghiệm. Có nhiều phƣơng pháp để thực hiện việc này, trong

đó ngƣời ta phân biệt chủ yếu các phƣơng pháp dựa vào quy tắc ngữ

pháp và các phƣơng pháp xác suất. Ngoài ra còn có các hệ thống sử

dụng mạng nơ-ron, các hệ thống lai sử dụng kết hợp tính toán xác suất

và ràng buộc ngữ pháp, gán nhãn nhiều tầng.

Về mặt ngữ liệu, các phƣơng pháp phân tích từ loại thông dụng hiện

nay dùng một trong các loại tài nguyên ngôn ngữ sau:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

- Từ điển và các văn phạm loại bỏ nhập nhằng.

- Kho văn bản đã gán nhãn, có thể kèm theo các quy tắc ngữ pháp xây

dựng bằng tay.

- Kho văn bản chƣa gán nhãn, có kèm theo các thông tin ngôn ngữ nhƣ là

tập từ loại và các thông tin mô tả quan hệ giữa từ loại và hậu tố.

- Kho văn bản chƣa gán nhãn, với tập từ loại cũng đƣợc xây dựng tự

động nhờ các tính toán thống kê. Trong trƣờng hợp này khó có thể dự

đoán trƣớc về tập từ loại.

Các bộ gán nhãn từ loại dùng từ điển và văn phạm gần giống với một

bộ phân tích cú pháp. Các hệ thống học sử dụng kho văn bản để học cách

đoán nhận từ loại cho mỗi từ. Từ giữa những năm 1980 các hệ thống này

đƣợc triển khai rộng rãi vì việc xây dựng kho văn bản mẫu ít tốn kém hơn

nhiều so với việc xây dựng một từ điển chất lƣợng cao và một bộ quy tắc ngữ

pháp đầy đủ. Một số hệ thống sử dụng đồng thời từ điển để liệt kê các từ loại

có thể cho một từ, và một kho văn bản mẫu để loại bỏ nhập nhằng.

Các bộ gán nhãn thƣờng đƣợc đánh giá bằng độ chính xác của kết quả:

[số từ đƣợc gán nhãn đúng] / [tổng số từ trong văn bản]. Các bộ gán nhãn tốt

nhất hiện nay có độ chính xác đạt tới 98%.

3.5.4.Phân tích cú pháp

Các hƣớng tiếp cận để giải bài toán phân tích cú pháp đều sử dụng văn

phạm phi ngữ cảnh để biểu diễn ngôn ngữ, sau đó dùng một số kỹ thuật phân

tích để xác định cây phân tích cú pháp. Sở dĩ vậy là vì nó biểu diễn đƣợc hầu

hết các ngôn ngữ tự nhiên, và nó cũng có đủ hạn chế để xây dựng các trình

phân tích câu hiệu quả.

Văn phạm phi ngữ cảnh khi đƣợc sử dụng để biểu diễn cấu trúc cú pháp

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

thì các ký hiệu kết thúc tƣơng ứng với các từ trong ngôn ngữ, các ký hiệu

không úc tƣơng ứng với các phân loại cú pháp (hay từ loại). Tiên đề biểu diễn

phân loại "câu". Các quy tắc sinh biểu diễn các quy tắc ngữ pháp. Ta có thể

chia chúng thành các qui tắc từ vựng (chứa ít nhất một ký hiệu kết thúc) và

các qui tắc ngữ đoạn (không chứa ký hiệu kết thúc nào). Với mỗi từ trong từ

vựng có một tập các qui tắc sinh chứa từ này trong vế phải. Một cây dẫn xuất

cũng đƣợc gọi là cây cú pháp cho một phân tích của một ngữ đoạn thành các

thành phần kế tiếp.

3.6.Dữ liệu huấn luyện

Dữ liệu huấn luyện sử dụng trong mô hình ngôn ngữ là dữ liệu văn bản,

đƣợc chúng tôi tải về từ các trang báo mạng nhƣ: dantri.com.vn,

vnexpress.net, vietnamnet.vn, ... Sau khi tải từ các trang báo mạng về máy

tính dƣới dạng các file html, chúng tôi cho chạy qua các công cụ đã miêu tả ở

phần 3.4, (phân đoạn từ, chuẩn hóa, ....) Kết quả thu đƣợc hơn 300 Mb dữ liệu

văn bản đã chuẩn hóa dƣới hai dạng: âm tiết và từ.

3.7.Kết quả xây dựng mô hình

Hệ thống của chúng tôi thống kê số lƣợng cụm N-gram với kích thƣớc

tập văn bản huấn luyện tăng dần trong hai trƣờng hợp là: âm tiết và từ.

3.7.1.Số lƣợng các cụm n-gram với tiếng Việt dựa trên âm tiết.

Số lƣợng cụm n-gram Số âm tiết trong văn

bản huấn luyện Uni-gram Bi-gram Tri-gram

687.003 155.297 86.069 4.567

1.203.440 299.039 178.001 4.953

2.177.198 318.888 264.599 5.549

3.778.983 358.262 432.089 5.796

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

4.071.536 631.253 375.105 5.814

6.360 666.968 954.041 9.765.347

6.706 850.333 1.613.000 17.420.051

7.712 1.835.726 13.162.180 58.854.325

Bảng 3 -1. Số lượng các cụm n-gram trong văn bản huấn luyện với âm tiết

2-gram 3-gram

m a r g - N m ụ c

c á c g n ợ ư

16000000 14000000 12000000 10000000 8000000 6000000 4000000 2000000 0

l

ố S

Hình 3-2 Số lượng các cụm n-gram với âm tiết tăng kích thước dữ liệu

3.7.2.Số lƣợng các cụm n-gram với tiếng Việt dựa trên từ

Số lƣợng cụm n-gram Số từ trong văn bản huấn

luyện Uni-gram Bi-gram Tri-gram

940.032 15.627 268.019 93.194

1.687.023 19.057 406.975 167.114

2.334.297 20.452 517.773 238.531

3.303.231 20.683 535.861 588.976

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

7.778.893 26.920 1.116.428 790.995

13.814.890 27.798 1.554.965 1.255.119

15.286.851 31.609 1.794.882 1.613.000

24.366.642 36.279 3.780.751 17.410.504

Bảng 3-2: Số lượng các cụm N-gram trong văn bản huấn luyện với từ

2-gram

3-gram

25000000

20000000

m a r g - N m ụ c

15000000

10000000

c á c g n ợ ư

l

5000000

ố S

0

Hình 3-3: số lượng các cụm N-gram với từ khi tăng kích thước dữ liệu

3.8.Tần số của tần số

Trong khi xây dƣng mô hình ngôn ngữ, chúng tôi cũng đã thống kê đƣợc

tần số của tần số các cụm n-gram với kích thƣớc tập văn bản huấn luyện rất

lớn (hơn 54 triệu với âm tiết và hơn 25 triệu với từ. Việc thống kê nhƣ vậy sẽ

giúp chúng tôi chọn đƣợc các tham số phù hợp cho các phƣơng pháp làm mịn,

và xây dựng cấu trúc dữ liệu phù hợp hơn

3.8.1.Với âm tiết

Số lƣợng cụm ngram có tần số Uni-gram Bi-gram Tri-gram

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

1 514 742.986 8.428.814

225 263.052 1.834.374 2

128 141.940 773.793 3

119 92.484 428.780 4

80 65.979 272.156 5

84 50.620 188.533 6

45 40.048 138.643 7

50 32.422 107.227 8

57 26.961 84.581 9

53 22.759 68.083 10

6.355 351.791 619.766 >10

Bảng 3-3: Tần số của tần số các cụm N-gram áp dụng cho âm tiết

2-gram

3-gram

m a r g - N m ụ c

c á c g n ợ ư

l

ố S

10000000 9000000 8000000 7000000 6000000 5000000 4000000 3000000 2000000 1000000 0

1 2 3 4 5 6 7 8 9

Tần số

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Hình 3-4: số lượng các cụm Ngram (âm tiết) có tần số từ 1 đến 10

3.8.2.Với từ

Số lƣợng cụm ngram có tần số unigram bigram trigram

1 2526 2.014.193 12603741

2 1669 558.703 2.077.917

3 1.363 267.004 769.502

4 1.052 161.639 394.105

5 895 108.849 238.249

6 792 79.277 157.384

7 689 60.829 113.525

8 638 48.450 84.245

9 520 39.188 64.686

10 509 32.688 51.210

>10 25.624 393.618 394.167

Bảng 3-4. Tần số của tần số các cụm Ngram với từ

2-gram

3-gram

m a r g - N m ụ c c á c g n ợ ư

l

ố S

16000000 14000000 12000000 10000000 8000000 6000000 4000000 2000000 0

Tần số

1 2 3 4 5 6 7 8 9

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Hình 3-5. Số lượng các cụm Ngram (từ) có tần số từ 1 đến 10

Nhƣ vậy, qua các trƣờng hợp, có thể nhận thấy số lƣợng các cụm n-gram

có tần số bằng 1 và 2 chiếm tỉ lệ rất lớn trong tổng số các cụm n-gram (trên

50%). Nếu sử dụng các phƣơng pháp loại bỏ nhƣ đã trình bày ở phần 2.6, thì

sẽ tiết kiệm đƣợc khá nhiều bộ nhớ, đồng thời sẽ làm tăng tốc độ mà không

làm giảm độ chính xác của mô hình ngôn ngữ.

3.9.Cut-off (loại bỏ)

Dựa vào kết quả thống kê tần số của tần số các cụm n-gram nhƣ đã trình

bày, chúng ta áp dụng phƣơng pháp loại bỏ (cut-off) cho tập văn bản huấn

luyện có kích thƣớc lớn nhất với các tham số khác nhau. Dƣới đây là bảng thể

hiện kích thƣớc bộ nhớ sử dụng và độ hỗn loạn thông tin (perplexity) của mô

hình ngôn ngữ khi áp dụng phƣơng pháp cut-off với các tham số khác nhau.

3.9.1.Với âm tiết

Loại bỏ Loại bỏ Loại bỏ Độ hỗn loạn unigram có tần bigram có tần trigram có tần Bộ nhớ sử thông tin số không lớn số không lớn số không lớn dụng (MB) (perplexity) hơn: hơn: hơn:

0 0 149 31,89 0

2 2 58 44,80 2

5 5 56 45,60 2

10 5 36 51,36 3

1 3 24 56,04 5

5 5 16 57,22 5

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Bảng 3-5: Bộ nhớ và độ hỗn loạn thông tin khi áp dụng loại bỏ trong âm tiết

3.9.2.Với từ

0 0 0 234 37,77

2 2 2 68 81,12

2 5 5 63 87,38

3 10 5 36 106,23

5 1 3 24 113,94

5 5 5 21 121,79

10 5 3 16 127,17

Bảng 3-6: Bộ nhớ và độ hỗn loạn thông tin khi áp dụng loại bỏ với từ

3.10.Các phƣơng pháp làm mịn

Áp dụng các phƣơng pháp làm mịn khác nhau với tập văn bản huấn

luyện có kích thƣớc lớn nhất, sau đó sử dụng mô hình ngôn ngữ xây dựng

đƣợc để tính độ hỗn loạn thông tin của tập văn bản huấn luyện. Dƣới đây là

bảng thể hiện độ hỗn loạn thông tin của tập văn bản huấn luyện khi áp dụng

mô hình ngôn ngữ với các phƣơng pháp làm mịn khác nhau: Add-one,

Witten-Bell, Good-Turing, Nội suy Kneser-Ney, Truy hồi Kneser-Ney, Nội

suy Kneser-Ney và Truy hồi Kneser-Ney cải tiến bởi Chen-GoodMan.

3.10.1.Với âm tiết

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Add- Witten- Good- Nội Truy Nội suy KN cải Truy hồi KN cải one Bell Turing suy KN hồi KN tiến tiến

1- 656.09 656.09 656.09 656.09 607.09 656.09 656.09 gram

2- 112.60 100.21 98.73 98.43 99.49 99.26 101.43 gram

3- 173.44 44.90 43.73 30.56 32.75 31.90 35.20 gram

Bảng 3-7: Độ hỗn loạn thông tin của các phương pháp làm mịn cho âm tiết

3.10.2.Với từ

Nội suy Truy hồi Add- Witten- Good- Nội Truy KN cải KN cải one Bell Turing suy KN hồi KN tiến tiến

1- 906.07 906.09 906.07 906.07 906.07 906.09 906.09 gram

2- 201.02 149.21 146.7 188.01 192.11 192.28 199.17 gram

3- 449.77 32.62 37.77 34.9 38.79 36.80 42.16 gram

Bảng 3-8: Độ hỗn loạn thông tin của các phương pháp làm mịn cho từ

Từ kết quả tại bảng 3-7 và bảng 3-8 rút ra hai nhận xét nhƣ sau:

- Trong các phƣơng pháp làm mịn thì phƣơng pháp Good-Turing ( so

sánh với Add- one , Witten-Bell) cho kết quả tốt nhất trên cả 3 loại unigram,

bigram và trigram, trong đó Witten-Bell, Good-Turing cho kết quả gần tƣơng

tự nhau. Khi thực nghiệm trên N-gram với N tăng dần từ 1 đến 3 chúng ta

thấy khoảng cách perplexity đo đƣợc bằng Witten-Bell, Good-Turing càng xa

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

so với phƣơng pháp Add-one. Điều đó chứng tỏ rằng khi dùng N-gram vơi N

lớn hơn 1 thì dùng phƣơng pháp chiết khấu Add-one sẽ kém hiệu quả hơn

nhiều so với các phƣơng pháp còn lại.

-Phƣơng pháp Kneser-Ney đối với hai cách tiếp cận truy hồi và nội suy

cho giá trị perplexity thấp hơn Good-Turing và Witten-Bell. Trong đó Nội suy

Kneser-Ney cho kết quả tốt hơn Truy hồi Kneser-Ney. So sánh các kết quả

trên 2-gram và 3-gram chúng ta có thể thấy khi các N-gram có độ dài càng

lớn thì sự cách biệt giữa các kết quả này càng cao. Tức là khi N càng lớn thì

phƣơng pháp Nội suy Kneser-Ney càng chứng tỏ ra hiệu quả.

3.11.Tổng kết chƣơng

Chƣơng này, tác giả đã khảo sát một cách chi tiết trên cả mặt lý thuyết

và thực nghiệm đối với mô hình ngôn ngữ tiếng Việt. Các kết quả trên phản

ánh một cách trực quan và rõ ràng về chất lƣợng cũng nhƣ cho phép chúng ta

so sánh một cách định lƣợng các mô hình N-gram với các phƣơng pháp làm

mịn khác nhau.

Từ các kết quả thực nghiệm chứng tỏ các phƣơng pháp Good-Turing

,Witten-Bell và Nội suy Kneser-Ney, Truy hồi Kneser-Ney trong đó phƣơng

pháp Nội suy Kneser-Ney cho ta kết quả là tốt nhất.

Tuy nhiên một lựa chọn khác là phƣơng pháp Good-Turing là một

phƣơng pháp chiết khấu với kỹ thuật tính toán đơn giản hơn các phƣơng pháp

truy hồi hay nội suy nhƣng vẫn cho kết quả tốt và có thể chấp nhận đƣợc cho

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

nhiều ứng dụng.

CHƢƠNG 4: ỨNG DỤNG N-GRAM TRONG BÀI TOÁN THÊM DẤU TIẾNG VIỆT

4.1. Bài toán thêm dấu tiếng Việt

4.1.1. Phát biểu bài toán

Bài toán được phát biểu như sau:

Cho một văn bản tiếng Việt không dấu. Chuyển văn bản không dấu thành có

dấu với độ chính xác cao.

Yêu cầu khác:

Chỉ sử dụng từ điển từ và kho dữ liệu thô làm đầu vào.

Chỉ xử lý các văn bản tiếng Việt có mã Unicode,TCVN3.

4.1.2. Đặc điểm

Chữ viết tiếng Việt có một đặc điểm đặc biệt là sự xuất hiện của các

dấu thanh cũng nhƣ dấu của các ký tự. Tiếng Việt có thanh điệu và trong văn

bản dấu của ký tự này làm phong phú thêm cho ngôn ngữ tiếng Việt, và tăng

độ biểu cảm của tiếng Việt.

Dấu thanh là một thành phần không thể thiếu trong âm tiết tiếng Việt.

Khi loại bỏ dấu thanh, việc hiểu nghĩa của từ, gồm một hay nhiều âm tiết kết

hợp với nhau trở nên khó khăn và dễ hiểu nhầm nghĩa của tiếng Việt.

Để thêm dấu, trƣớc tiên ta cần phải xác định ranh giới của từ. Bài toán

xác định ranh giới từ đối với văn bản tiếng Việt có dấu đó là vấn đề khó chính

điều đó khi không có dấu thì việc nhận ranh giới từ càng trở nên khó khăn

hơn.Trong tiếng Việt, các tiếng hay còn gọi là âm tiết đƣợc phân cách bởi

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

khoảng trắng chứ không phải từ.

Vậy sau khi nhận đƣợc ranh giới từ, ta cần phải xác định cho đúng từ

có dấu nào có dạng thể hiện không dấu nhƣ vậy. Việc xác định này cũng

không ít khó khăn.

Ví dụ 4.1: Từ không dấu “bo” có tới 3 từ có dấu tƣơng ứng nhƣ “bô”,

“bố”, “bỏ”…

Do đó, sau khi đã giải quyết xong bài toán về tách từ tiếng Việt không

dấu, ta cần phải giải quyết thêm bài toán xác định từ có dấu thích hợp với từ

không dấu đó.Đây chính là hƣớng giải quyết bài toán đặt ra cho luận văn.

4.1.3. Hƣớng giải quyết:

Đối với tách từ có dấu, có nhiều mô hình đƣợc sử dụng và đạt kết quả

tốt nhƣ MM (Maximum Mactching: forward/backward hay còn gọi là

LRMM:Left Right; mạng chuyển dịch trạng thái hữu hạn có trọng số WFST

(Weighted finite-state Transducer); giải thuật dựa trên nén(compression).

Hƣớng giải quyết đƣợc đề xuất là sử dụng phƣơng pháp tách từ LRMM kết

hợp với mô hình Bigram đã giải quyết khá hiệu quả 2 vấn đề của bài toán này.

4.2. Các phƣơng pháp đánh giá kết quả thêm dấu:

Cách đánh giá độ chính xác của hệ thống thêm dấu cũng gần tƣơng tƣ

nhƣ đánh giá kết quả của một hệ thông dịch máy thông kê, là một nhiệm vụ

rất vất vả và khó khăn. Để đánh giá độ chính xác của bản dịch, ta có thể đánh

giá trực tiếp thông qua ngƣời dùng hoặc đánh giá tự động bằng máy tính.

4.2.1. Đánh giá kết quả trực tiếp bằng con ngƣời:

Để đánh giá độ chính xác của hệ thống thêm dấu văn bản tiếng Việt, ta

có thể để con ngƣời trực tiếp đánh giá. Chúng ta có thể đƣa ra một thƣớc đo

cho độ trôi chảy của bản dịch (ví dụ từ 1 đến 5 hay từ 1 đến 10 tùy thuộc vào

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

độ trôi chảy của bản dịch), sau đó cho những ngƣời tham gia đánh giá đánh

giá các câu trong bản dịch theo thang điểm đó. Nhƣ vậy, văn bản nào có điểm

trung bình càng cao, thì chất lƣợng bản dịch đó càng tốt. Ngoài ra, cũng có

thể đánh giá độ trôi chảy, độ chính xác của bản dịch thông qua thời gian mà

ngƣời đọc đọc hiểu đƣợc bản dịch đó. Rõ ràng, bản dịch nào mà ngƣời đọc

đọc hiểu càng nhanh, thì bản dịch đó càng chính xác.

Phƣơng án đánh giá bản thêm dấu tiếng Việt bằng chính con ngƣời tuy

rất dễ thực hiện, nhƣng chi phí thì rất lớn, và nếu văn bản thêm dấu có kích

thƣớc càng lớn thì phƣơng pháp này càng kém hiệu quả. Một phƣơng án khác

là cũng tƣơng tự nhƣ bài toán của các mô hình dịch máy, ta có thể áp dụng

phƣơng pháp đánh giá tự động, chi phí thấp nhƣng hiệu quả cũng khá là cao.

4.2.2. Đánh giá kết quả tự động: phƣơng pháp BLEU

BLEU (BiLingual Evaluation Understudy) là một phƣơng pháp dùng để

đánh giá chất lƣợng bản dịch của bài toán dịch máy thông kê, đƣợc đề xuất

bới IBM tại hội nghị ACL ở Philadelphie vào tháng 7-2001. Ý tƣởng chính

của phƣơng pháp này là so sánh kết quả bản dịch tự động bằng máy với các

bản dịch mẫu của con ngƣời, bản dịch máy nào càng giống với bản dịch mẫu

của con ngƣời thì bản dịch đó càng chính xác. Việc so sánh trên đƣợc thực

hiện thông qua việc thống kê sự trùng khớp của các từ trong hai bản dịch có

tính đến thứ tự của chúng trong câu (phƣơng pháp N-gram theo từ)[12].

Hình 4-1. Sự trùng khớp của các bản dịch máy với bản dịch mẫu

Với một bản dịch máy và bản dịch mẫu thứ n, phƣơng pháp BLEU trƣớc

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

tiên thống kê số lần tối thiểu của các cụm n-gram xuất hiện trong từng cặp câu

(câu dịch máy và câu dịch mẫu), sau đó đem tổng trên chia cho tổng số cụm

n-gram trong toàn bản dịch máy. Tỉ lệ trùng khớp của một bản dịch máy và

số lƣợng tối thiểu cụm w có trong bản mẫu

Pn=

số lƣợng cụm n-gram w trong bản dịch máy

 s  bản dịch máy  s  bản dịch máy

 w  s  w  s

bản dịch mẫu thứ n đƣợc tính theo công thức :

Trong đó s là các câu trong bản dịch máy, w là các cụm ngram có trong

câu s.

Điểm BLEU đánh giá một bản dịch máy với n bản dịch mẫu đƣợc tính

theo công thức :

i = N  i = 1

BLEU = BP * ( log pi) 1 N

Trong đó :

1 nếu c>r  e(1-r/c) với c<=r 

BP = với c là độ dài của bản dịch máy, r là độ

dài lớn nhất của các bản dịch mẫu

N là số lƣợng các bản dịch mẫu

Từ công thức trên, có thể thấy giá trị BLEU nằm trong khoảng 0 đến 1.

Bản dịch nào có điểm BLEU càng cao, chứng tỏ độ trùng khớp giữa bản dịch

máy và bản dịch mẫu càng nhiều, thì bản dịch đó càng chính xác.

4.3. Các hệ thống thêm dấu ứng dụng về N-gram đã có:

4.3.1. VietPad

VietPad là trình soạn thảo hỗ trợ tiếng Việt Unicode, đƣợc phát triển

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

bới Quân Nguyễn và nhóm phát triển trên http://www.VietPad.sourceforge.net. Ngoài chức năng thêm dấu tự động

online mà văn bản đang nghiên cứu, VietPad còn là một trình soạn thảo tiếng

Việt hỗ trợ rất tốt Unicode và mã nguồn mở

Mô hình thêm dấu tiếng Việt của VietPad

Bắt đầu

Tiền xử lý

Tách Token

Tách các từ không dấu

Từ điển chuyển đổi Chuyển thành có dấu

Xuất ra màn hình

Hình 4-2. Lưu đồ thực hiện mô hình ứng dụng trong VietPad

a) Tiền xử lý

Chuẩn hóa văn bản theo định dạng mà VietPad quy định

b) Tách token VietPad không tách từng câu mà tách ra từng token mô token có thể gồm 1 chuỗi các ký tự không phải là ký tự (:,.;”@#$...) hay một chuỗi các

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

ký tự hay là “chữ” tiếng Việt.

Ví dụ 4.2: Câu “ Ngay mai troi se nang ” sẽ đƣợc VietPad tách thành từng token nhƣ sau:

Token 1: \b (ký hiệu cho khẳng trắng)

Token 2: Ngay

Token 3:\b

Token 4:mai

Token 5:\b

Token 6:troi

Token 7:\b

Token 8:se

Token 9:\b

Token 10:nang

Token 11:\b

c) Lấy ra các từ không dấu, chuyển thành có dấu: Với phƣơng pháp tách token đơn giản trên, thêm phƣơng pháp

tách từ LRMM(từ có tối đa 3 tiếng),VietPad lấy ra các từ không dấu, sau

đó thông qua 1 từ điển ánh xạ 1-1 giữa từ không dấu và từ có dấu ( từ điển

chuyển đổi) để chuyển từ không dấu sang có dấu.

Ví dụ 4.3:

Câu “Nhung van de lien quan toi nguoi dong tinh luyen ai duoc ban bac

soi noi trong buoi hop nhom toi hom qua” sẽ đƣợc VietPad chuyển thành

câu có dấu sau thông qua từ điển ( dấu/thể hiện sự tách từ của VietPad).

“Nhƣng vẫn/ để / liên quan / tôi ngƣời / động tĩnh / luyến ái /

đƣợc / bần bạc / sôi nổi / trong / buổi /hợp / nhóm / tôi / hôm qua/”.

4.3.2.VnMark-Mô hình thêm dấu tiếng việt:

Căn cứ vào mô hình N-gram mô hình đánh dấu tự động tiếng Việt đƣợc

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

tác giả thực hiện theo lƣu đồ sau:

Bắt đầu

Tiền xử lý

Tách câu

Tìm các khả năng đánh dấu có thể có của từng từ

VnmarkDic.txt

Tính toán các khả năng đánh dấu có thể có của câu

Tra bảng để tính trọng số cho từng câu ứng viên nêu trên

Chọn câu có trọng số

thích hợp

Xuất ra màn hình

Hình 4-3. Lưu đồ thực hiện của mô hình N-gram

a) Tiền xử lý

Xóa các khoảng trắng thừa. Thực hiện các công việc chuẩn hóa dữ liệu

nhập vào thay thế các ký tự tƣơng tự.

Ngƣời ta sử dụng việc đánh chữ việt không dấu thì thì ngƣời ta vẫn

đánh đƣợc các ký tự viết hoa nhƣ các danh từ riêng. Do đó, các từ viết hoa sẽ

không “thƣờng hóa” (lowercase) và các từ viết hoa này sẽ đƣợc căn cứ để

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

nhận dạng danh từ riêng.

Ví dụ 4.4:

Thanh Hoa -> Thanh Hóa

thanh hoa -> thanh hòa

Do đó tác giả lƣu ý ngƣời dùng về đặc điểm khi sử dụng chƣơng trình.

b) Tách câu

Căn cứ vào các đặc điểm của ngôn ngữ tiếng Việt: các từ đƣợc cách

nhau bởi các ký tự nhƣ “.”, “,”, “:”… để tách thành các câu. Mỗi câu là một

đơn vị xử lý chính trong chƣơng trình. Việc quyết định câu là đơn vị cơ bản là

do nhiều khi nghĩa của câu sẽ đƣợc quyết định sự lựa chọn về dấu trong câu.

4.4. Đề xuất hệ thống:

4.4.1.Mô hình

Căn cứ vào mô hình Bigram và dựa vào ý tƣởng của việc thống kê các

cụm từ tôi đề xuất mô hình thêm dấu tự động nhƣ sau:

Bắt đầu

Tiền xử lý

Tách câu

Tách từ

Tập các từ không dấu Từ điển chuyển đổi

sử dụng N-gram Chọn từ thích hợp

Xuất ra màn hình

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

Hình 4-4. Lưu đồ thực hiện của mô hình đề xuất

a)Tách câu

Sử dụng phƣơng pháp tách câu huristic đã nêu trong chƣơng 3. Qua

phƣơng pháp tách câu trên ta có thể phân biệt đƣợc một số trƣờng hợp đặc

biệt của dấu chấm câu “.” nhƣ từ viết tắt (Mr., Mrs…) địa chỉ

mail(caoductu.hui@gmail.com), số thập phân (1,345.567). Đầu ra của bƣớc

này sẽ cho ra một tập các câu là đầu vào của bƣớc sau.

b) Tách từ bằng phương pháp LRMM.

Ta dùng phƣơng pháp tách từ LRMM tách các từ không dấu từng câu

một. Lý do chọn phƣơng pháp này là: Cài đặt phƣơng pháp đơn giản, sai số

khi tách sai từ có thể chấm nhận đƣợc khi tách từ không dấu.

Ta có cách tách từ câu có dấu và câu không dấu sau ( các từ phân cách Ví dụ 4.5:

nhau bằng dấu /)

 “Học sinh / học / sinh học”

 “Học sinh / học sinh / học” -> khi chuyển thành câu có dấu cũng tao đƣợc câu “ Học sinh / học sinh / học” nhƣ trên -> sai khi tách từ có thể

chấp nhận đƣợc trong 1 phạm vi nào đó.

Khi tách từ bằng phƣơng pháp LRMM, ta có chú ý đến việc nhận diện

và tách các từ tên riêng ra dựa trên một từ điển tên riêng. Việc xác định

các tên riêng dựa trên chữ cái viết hoa đầu của từ, một cụm tên riêng có

thể chỉ cần viết hoa tiếng đầu tiên là đƣợc.

Vi dụ: 4.6:

Thanh Hoa -> Thanh Hóa

Thanh hoa -> Thanh Hóa

thanh hoa -> Thanh hòa

c) Chọn từ thích hợp: Với từ điển chuyển đổi initial.txt, ta có ánh xạ 1-1 để chuyển một từ không dấu thành có dấu. Ngoài ra để tăng độ linh hoạt và chính xác của

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

phƣơng pháp, ta có thể thêm một từ điển phụ, gọi là từ điển cụm từ Cumtu.txt, lƣu những cụm từ thƣờng xuyên xuất hiện.

Ví dụ: 4.7 Câu “Nhung van de lien quan toi nguoi dong tinh luyen ai duoc

ban bac soi noi trong buoi hop nhom toi hom qua” sẽ đƣợc chuyển thành

 Tách câu: Tạo ra một câu duy nhất là “Nhung van de lien quan toi

câu có dấu qua các bƣớc sau:

nguoi dong tinh luyen ai duoc ban bac soi noi trong buoi hop nhom toi hom qua”.1

 Tách từ ( Các từ phân cách nhau bằng dấu / ): “Nhung / van de / lien

quan / toi / nguoi / dong tinh luyen ai / duoc / ban bac / soi noi /

trong / buoi / hop / nhom / toi / hom qua”.

4.4.2. Mô hình huấn luyện.

Nhƣ đã trình bày ở trên, cốt lõi của vấn đề là tập tin từ huấn luyện

initial.txt. Tập tin này sẽ chứa xác suất các nhóm âm tiết có thể xuất hiện

trong văn bản tiếng việt.

Ngoài ra mô hình huấn luyện sử dụng các phƣơng pháp làm mịn khác

nhau trong mô hình ngôn ngữ N-gram nhƣ: Addone, Witten-Bell, Good-

Turing.. với phƣơng pháp làm trơn hóa mô hình giúp việc thêm dấu đƣợc

chính xác.

Khác với các mô hình thêm dấu tiếng Việt trƣớc đây, tập tin từ điển

không những lƣu các từ tiếng Việt mà còn lƣu các dãy âm tiết trong Tiếng

Việt. Điều này giúp cho mô hình có thể “vét cạn” các thông tin giúp cho việc

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

thêm dấu chính xác hơn.

4.5. Thử nghiệm hệ thống:

Ví dụ 4.8:

Hình 4.5. Mô hình test thêm dấu đề xuất.

Mô hình N-gram cho tiếng Việt giúp việc xây dựng một hệ thống thêm

dấu cho tiếng Việt không dấu với kết quả khá tốt.

Tuy nhiên kết quả thêm dấu có thể sẽ tốt hơn nữa tăng N để có những

đánh giá sâu hơn. Việc dùng các phƣơng pháp làm trơn khác, có thể cũng

giúp tăng khả năng ƣớc lƣợng giá trị xác suất quyết định, và làm chất lƣợng

của hệ thống tăng lên. Tuy nhiên, sẽ cần một lƣợng dữ liệu lớn hơn, và đa

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

dạng hơn cho huấn luyện mô hình.

CHƢƠNG 5: KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN CỦA ĐỀ TÀI

5.1. Các kết quả đạt đƣợc:

Mục tiêu của luận văn, là nghiên cứu nắm bắt đƣợc những vấn đề cốt lõi

của mô hình ngôn ngữ N-gram, đặc biệt là làm trơn các phân bố xác suất

thống kê (Smoothing techniques), nhằm nâng cao chất lƣợng, làm giảm kích

thƣớc của mô hình ngôn ngữ dựa vào một số kỹ thuậtnhƣ: Pruning (loại bỏ)

làm giảm số lƣợng các cụm n-gram ,Quantization (lƣợng tử hóa) thay đổi lại

cấu trúc thông tin của mỗi cụm n-gram,Compression (nén) nén cấu trúc dữ

liệu sử dụng trong việc lƣu trữ các cụm n-gram trong mô hình ngôn ngữ .

Ngoài ra, luận văn hƣớng tới việc đƣa ra một ứng dụng cụ thể của mô

hình này cho tiếng Việt, mà cụ thể là bài toán thêm dấu cho văn bản tiếng

Việt không dấu.

Trong luận văn này mô hình thống kê tần số xuất hiện của từ, kèm theo

phƣơng pháp tách từ không dấu LRMM và sử dụng thêm từ điển cụm từ, khả

năng chính xác của mô hình là tƣơng đối cao.Tuy nhiên, phải nói là mô hình

còn những hạn chế và cũng là hƣớng mở mà luận văn cần phải tiếp tục nghiên

cứu và phát triển trong thời gian tiếp theo nhằm tăng độ chính xác lên cao hơn

nữa.

Chƣơng trình hoàn thiện cần có sự đầu tƣ nhiều hơn về thời gian và

công sức. Đề tài có thể tiếp tục phát triển để đem lại ứng dụng đáp ứng đƣợc

yêu cầu tốt hơn trong thực tế.

5.2.Hạn chế và hƣớng phát triển của đề tài: Bài toán thêm dấu vào văn bản không dấu là bàii toán mới, còn đang

hoàn thiện dần về mô hình cũng nhƣ cách thực hiện. Hiện nay, mô hình

thƣờng dùng cho bài toán này là thống kế tần số xuất hiện của từ, đồng thời,

tùy theo mỗi tác giả mà có thêm những biến đổi, thuật giải khác nhau giúp

cho việc thêm dấu đƣợc chính xác hơn.

Tác giả mong muốn có thể tiếp tục phát triển để đƣa các kết quả đã

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

nghiên cứu vào ứng dụng trong thực tế…

TÀI LIỆU THAM KHẢO

Tiếng việt.

[1]. TS. Đinh Điền, Giáo trình xử lý ngôn ngữ tự nhiên, Khoa Công nghệ

Thông tin, Đại học Khoa học Tự nhiên Thành phố Hồ Chí Minh, Tháng 12-

2004.

[2]. Đoàn Xuân Kiên, “Bàn về chuyện đánh dấu thanh trong tiếng Việt”, đăng

tại trang http://home.tiscali.be/centre.vietnam/

[3]. Đoàn Xuân Kiên, “xem lại một số vấn đề ngữ âm tiếng Việt: cấu trúc âm

tiết”, đăng tại trang http://home.tiscali.be/centre.vietnam/

[4]. Tài liệu về phần mềm VietPad đƣợc công bố tại trang web

http://vietpad.sourceforge.net

[5]. Tài liệu về phần mềm AMPad đƣợc công bố tại trang web:

http://www.echip.com.vn/echiproot/weblh/qcbg/duynghi/automark

Tiếng anh.

[6].Chris Manning and Hinrich Schutze, Foundations of Statistical Natural

Language Processing, MIT Press. Cambridge, May 1999.

[7]. Boulos Harb, Ciprian Chelba, Jeffrey Dean, Sanjay Ghemawat, “Back-

Off Language Model Compression”, Proceedings of Interspeech 2009, pp. 325-355.

[8].Daniel Jurafsky and James H. Martin, Speech and Language Processing:

An Introduction to Natural Language Processing, Computational Linguistics

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

and Speech Recognition, chapter 6, February 2000.

[9]. R. Kneser and H. Ney, “Improved backing-off for M-gram language

modeling”, Acoustics, Speech, and Signal Processing, 1995. ICASSP-95.,

1995 International Conference on

[10]. Andreas stolcke, “Entropy-based pruning of backoff language models”,

Proceedings of the ARPA Workshop on human language technology, 1998

[11]. Andreas stolcke, SRILM – an extensible language modeling toolkit,

Conference on spoken language processing, 2002.

[12]. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu, Bleu:

a Method for Automatic Evaluation of Machine Translation, IBM T. J.

Watson Research Center, Proceedings of the 40th Annual Meeting of the

Association for Computational Linguistics (ACL), Philadelphia, July 2002

[13]. Tô Hồng Thắng, Building language model for vietnamese and its

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

application, graduation thesis, 2008.

Luận văn Thạc sĩ: Nghiên cứu mô hình ngôn ngữ N-Gram và ứng dụng trong bài toán thêm dấu cho tiếng Việt không dấu

Chủ đề:

NGHIÊN CỨU MÔ HÌNH NGÔN NGỮ N-GRAM VÀ ỨNG DỤNG TRONG BÀI TOÁN THÊM DẤU CHO TIẾNG VIỆT KHÔNG DẤU

LUẬN VĂN THẠC SĨ : KHOA HỌC MÁY TÍNH

Thái Nguyên - 2011

CAO ĐỨC TƯ

NGHIÊN CỨU MÔ HÌNH NGÔN NGỮ N-GRAM VÀ ỨNG DỤNG TRONG BÀI TOÁN THÊM DẤU CHO TIẾNG VIỆT KHÔNG DẤU

LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC TS. VŨ TẤT THẮNG

Thái Nguyên - 2011

Diễn giải

Ý nghĩa

Viết tắt ACL

P(wi|wi-2wi-1) nếu C(wi-2wi-1wi ) > 0  1 * P(wi|wi-1) nếu C(wi-2wi-1wi ) = 0 và C(wi-1wi ) > 0  2 * P(wi) nếu C(wi-2wi-1wi ) = 0 và C(wi-1wi ) = 0

P‟(wi|wi-2wi-1) nếu C(wi-2wi-1wi) > 0  1 * P‟(wi|wi-1) nếu C(wi-2wi-1wi) = 0 và C(wi-1wi) > 0 P(wi|wi-2wi-1) =  2 * P‟(wi) nếu C(wi-2wi-1wi) = 0 và C(wi-1wi) = 0

+ 

0 nếu c(wi-n+1..wi) = 0  D1 nếu c(wi-n+1.. wi) = 1 D =  D2 nếu c(wi-n+1.. wi) = 2  D3 nếu c(wi-n+1.. wi) >= 3

Ví du 2.4: L dãy kí tự a, b, …, z có perplexity là 26 còn bảng mã ASCII có

m a r g - N m ụ c

c á c g n ợ ư

16000000 14000000 12000000 10000000 8000000 6000000 4000000 2000000 0

l

ố S

2-gram

3-gram

25000000

20000000

m a r g - N m ụ c

15000000

10000000

c á c g n ợ ư

l

5000000

ố S

0

2-gram

3-gram

m a r g - N m ụ c

c á c g n ợ ư

l

ố S

10000000 9000000 8000000 7000000 6000000 5000000 4000000 3000000 2000000 1000000 0

1 2 3 4 5 6 7 8 9

Tần số

2-gram

3-gram

m a r g - N m ụ c c á c g n ợ ư

l

ố S

16000000 14000000 12000000 10000000 8000000 6000000 4000000 2000000 0

Tần số

1 2 3 4 5 6 7 8 9

soi noi trong buoi hop nhom toi hom qua” sẽ đƣợc VietPad chuyển thành

ban bac soi noi trong buoi hop nhom toi hom qua” sẽ đƣợc chuyển thành

nguoi dong tinh luyen ai duoc ban bac soi noi trong buoi hop nhom toi hom qua”.1

Ví dụ 4.8:

Tài liệu liên quan

Tài liêu mới

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

Hỗ trợ

Phương thức thanh toán

Theo dõi chúng tôi