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
Thái Nguyên - 2011


Thái Nguyên - 2011

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

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

Cao Đức Tư

2

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 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

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
3.10.Các phƣơng pháp làm mịn 53
4

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.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

Stanford Research Institute
học viện nghiên cứu sờ ten phoóc
LM
language Model
Mô hình ngôn ngữ
MM
Maximum Mactching
Khớp tối đa
LRMM
Left Right Max Matching
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ố

6

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

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
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
8

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

ứ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
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ó.
10

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

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.


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 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
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à

… Đề 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,
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. 14

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.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

|w
1
) * P(w
3
|w
1
w
2
) *…* P(w
m
|w
1
w
2
…w
m-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(w
1
)=P(w
1
|start) là xác suất để w
1
đứ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,

m-n+1
…w
m-1
) chứ không
phải phụ thuộc vào toàn bộ dãy từ đứng trƣớc (w
1
w
2
…w
m-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(w
1
w
2
…w
m
) = P(w
1
) * P(w
2
|w
1
) * P(w
3
|w
1
w
2

 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(w
i-n+1
w
i-1
w
i
) là tần số xuất hiện của cụm w
i-n+1
w
i-1
w
i
trong tập
văn bản huấn luyện.
Gọi P(w
i
|w
i-n+1
w
i-1
) là xác suất w
i
đi sau cụm w

Dễ thấy,


w
C(w
i-n+1
w
i-1
w) chính là tần số xuất hiện của cụm w
i-n+1
w
i-1

trong văn bản huấn luyện. Do đó công thức trên viết lại thành:
P(w
i
|w
i-n+1
w
i-1
) =
C(w
i-n+1
w
i-1
w
i
)
C(w
i-n+1

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à
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ó
18

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

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
giá lại xác suất của các cụm n-gram bằng cách:
● Gán cho các cụm n-gram có xác suất 0 (không xuất hiện trong tập
huấn luyện) một giá trị khác 0.
● 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
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%).
Các phƣơng pháp làm mịn có thể đƣợc chia ra thành một số loại nhƣ sau:
● Chiết khấu (Discounting): giảm (lƣợng nhỏ) xác suất của các

C
i
*
= (C
i
+1)
M
M‟

với C
i
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:
P
i
* =
C
i
*
M
=
(C
i
+1)
M + V

Xét các cụm n-gram với n>1, thay M bằng C(w
i-n+1
w
i-1

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
20

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

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(w
1
w
2
w
n
) =
C(w
1
w
2
w
n
) +

C(w
1
w
2
w
n-1
) + M


P* =
T
Z(T+M)
, và xác suất xuất hiện của các cụm unigram có tần
số khác 0 đƣợc tính lại theo công thức:
P(w) =
c(w)
T+M
với c(w) là số lần xuất hiện của cụm w
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(w
i-n+1
w
i-1
) thì xác suất của cụm w
i-n+1
w
i-1
w
i
với C(w
i-n+1
w
i-1
w
i
)
= 0 đƣợc tính theo công thức sau:
P(w

i
) > 0, thì xác suất cụm (w
i-n+1
w
i-1
w
i
) đƣợc tính bằng
công thức:
P(w
i
|w
i-n+1
w
i-1
) =
C(w
i-n+1
w
i-1
w
i
)
C(w
i-n+1
w
i-1
) + T(w
i-n+1
w

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:
22

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(w) =
c*
N
với N = 
c = 

c = 0
N
c
c = 
c = 

c = 0
N
c
c* = 
c = 

c = 0
N
c+1
(c+1)
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ữ

w
i
đƣợc tính lại theo công thức sau:
P
B
(w
i
|w
i-n+1
w
i-1
)=



P(w
i
|w
i-n+1
w
i-1
) nếu C(w
i-n+1
w
i-1
w
i
) > 0
 * P
B

i-1
w
i
) > 0
 * P(w
i
) nếu C(w
i-1
w
i
) = 0

Công thức trên có thể viết lại thành:
P
B
(w
i
|w
i-1
) = P(w
i
|w
i-1
) +

(w
i-1
w
i
) *

i-2
w
i-1
w
i
) > 0

1
* P(w
i
|w
i-1
) nếu C(w
i-2
w
i-1
w
i
) = 0 và C(w
i-1
w
i
) > 0

2
* P(w
i
) nếu C(w
i-2
w

w
i-1
w
i
)*
1
*P(w
i
|w
i-1
) + (w
i-1
w
i
)*
2
* P(w
i
)
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

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

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.
Công thức tính xác suất theo phƣơng pháp nội suy nhƣ sau: