i

 

 

ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG
 
 
 
 
VŨ CHÍ HIẾU

 
 
 

NGHIÊN CỨU MÔ HÌNH NGÔN NGỮ N-GRAM CHO
TIẾNG VIỆT VÀ ỨNG DỤNG SỬA LỖI DẤU THANH
TRONG TIẾNG VIỆT

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

Thái Nguyên - 2016


ii

 



 
 

 

  NGHIÊN CỨU MÔ HÌNH NGÔN NGỮ N-GRAM CHO
 

TIẾNG VIỆT VÀ ỨNG DỤNG SỬA LỖI DẤU THANH
TRONG TIẾNG VIỆT

 
 
 
 

Chuyên ngành: Khoa học máy tính
Mã số:60 48 0101

 
 
 
 
 

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Giáo viên hướng dẫn: TS. VŨ TẤT THẮNG

 


ii

LỜI CẢM ƠN

Tôi xin gửi lời cảm ơn tới trường Đại học CNTT&TT – Đại học Thái
Nguyên đã tạo điều kiện và tổ chức khóa học này để tôi có thể có điều kiện
tiếp thu kiến thức mới và có thời gian để hoàn thành Luận văn Cao học này.
Tôi xin được cảm ơn TS.Vũ Tất Thắng, 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.
Tôi xin chân thành cảm ơn các thày cô đã truyền đạt cho em những
kiến thức quý báu trong quá trình học Cao học và làm Luận văn.
Tôi chân thành cảm ơn các bạn bè, anhchị em trong lớp cao học K13
đã 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.
Cuối cùng tôi kính gửi thành quả này đến gia đình và người thân của
tôi, những người đã hết lòng chăm sóc, dạy bảo và động viên tôi để tôi có kết
quả ngày hôm nay.
Mặc dù tôi đã cố gắng hoàn thành Luận văn trong phạm vi và khả năng
cho phép nhưng chắc chắn không tránh khỏi những thiếu sót. Xin kính mong
nhận được sự cảm thông và tận tình chỉ bảo của quý Thầy Cô và các bạn.
 

 

Thái Nguyên, ngày 20 tháng 3 năm 2016

Học viên

Vũ Chí Hiếu

1.4.1.2. Phương pháp làm mịn Witten - Bell: ..................................................................... 9
1.4.1.3. Phương pháp làm mịn Good - Turing: ................................................................. 10

1.4.2. Phương pháp truy hồi: ........................................................................................... 11
1.4.3. Phương pháp nội suy: ............................................................................................ 12
1.4.4. Phương pháp làm mịn Kneser - Ney: ..................................................................... 13
1.4.5. Phương pháp làm mịn Chen - GoodMan: .............................................................. 15

1.5.

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

1.5.1. Đồng hóa (Quantization): ...................................................................................... 16
1.5.2. Loại bỏ (pruning): ................................................................................................. 16
1.5.2.1. Cắt bỏ (cut-off):.................................................................................................... 17
1.5.2.2. Sự khác biệt trọng số (Weighted difference): ...................................................... 18

1.5.3. Nén (Compression): .............................................................................................. 19

1.6.

Độ đo trong đánh giá mô hình: ......................................................................... 20

1.6.1. Entropy - Độ đo thông tin: ..................................................................................... 20
1.6.2. Perplexity - Độ hỗn loạn thông tin: ........................................................................ 21
1.6.3. Error rate - Tỉ lệ lỗi: .............................................................................................. 22

CHƯƠNG II: XÂY DỰNG N-GRAM CHO TIẾNG VIỆT ................................. 24
2.1. Giới thiệu: ........................................................................................................... 24


2.10.2. Với từ: ................................................................................................................... 47

CHƯƠNG  III:  ỨNG  DỤNG  N-GRAM  TRONG  BÀI  TOÁN  BÀI  TOÁN 
SỬA LỖI DẤU THANH TRONG TIẾNG VIỆT ................................................. 49
3.1. Tổng quan: .......................................................................................................... 49
3.2. Bài toán sửa lỗi dấu thanh trong tiếng Việt: ......................................................... 50
3.2.1. Phát biểu bài toán: .................................................................................................... 50
3.2.2. Đặc điểm: ................................................................................................................. 50
3.2.3. Hướng giải quyết: .................................................................................................. 51

3.3. Các hệ thống thêm dấu ứng dụng về N-gram đã có: ............................................. 51
3.3.1. Công cụ AMPad: ...................................................................................................... 51


v

3.3.2. VietPad: ................................................................................................................... 52

3.4. Đề xuất hệ thống: ................................................................................................ 53
3.5. Cài đặt thử nghiệm và đánh giá hệ thống ............................................................. 56

KẾT LUẬN .......................................................................................................... 60
HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI ................................................................ 61
 
 

 


vi

Bảng 2- 7: Độ hỗn loạn thông tin của các phương pháp làm mịn cho âm tiết ............. 47
Bảng 2- 8: Độ hỗn loạn thông tin của các phương pháp làm mịn cho từ ................ 48

 
 


1

LỜI NÓI ĐẦU
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.  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. 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ụ: 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 = 10-3 
P[“trời mưa sẽ mai ngày”]  ~ 10-11 
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 

P(AB) = P(B|A) * P(A). 
Với:  
+ P(A): Xác suất xảy ra sự kiện A 
+ P(B): Xác suất xảy ra sự kiện B 
+ P(B|A): Xác suất (có điều kiện) xảy ra sự kiện B nếu biết rằng sự kiện 
A đã xảy ra. 
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). 
- Với n = 1, unigram. 
- Với n = 2, ta có khái niệm bigram.  
- Với n = 3, ta có trigram. Nhưng vì n càng lớn thì số trường hợp càng 
lớn nên thường người ta chỉ sử dụng với n = 1,2 hoặc đôi lúc là 3.  


4

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:  

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-1wi)

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

 
Dễ thấy,  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 
w

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

 

C(wi-n+1...wi-1wi)
P(wi|wi-n+1...wi-1) =  
 
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.  

đư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ụmN-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.   


7

● 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ụm Ngram có xác suất lớn hơn 0 để bù cho các cụm N-gram không xuất hiện trong 
tập huấn luyện.  
● Truy hồi (Back-off): Tính toán xác suất các cụm N-gram không xuất 
hiện trong tập huấn luyện dựa vào các cụm N-gram thành phần có độ dài ngắn 
hơn và có xác suất lớn hơn 0. 
● Nội suy (Interpolation): Tính toán xác suất của tất cả các cụm N-gram 
dựa vào xác suất của các cụm N-gram ngắn hơn. 
1.4.1. Các thuật toán chiết khấu (discounting):
Nguyên lý 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 Ngram có xác suất lớn hơn 0 đề bù cho các cụm N-gram chưa từng xuất hiện 
trong tập huấn luyện. Các thuật toán này sẽ trực tiếp làm thay đổi tần số xuất 
hiện của tất cả các cụm N-gram. Ở đây đề cập đến 3 thuật toán chiết khấu phổ 
biến: 
●Thuật toán Add-One 
●Thuật toán Witten-Bell 
●Thuật toán Good-Turing 

là tần suất của unigram, c(1) là số lần xuất 
(1)
n v

hiện của Unigram trước khi làm mịn bằng phương pháp Add-one. 
 Vớicụm N-gram w=w1w2...wi, i>1, ta có , 

 C (w w ...w
1

i 1

2

w)  C ( w1w2 ...wi 1 )  

w

Do đó: 
P( wi | w1w2 ...wi1 ) 

C ( w1w2 ...wi )  1
(1.4.2)
C ( w1w2 ...wi 1 )  V

Để ý rằng, có rất nhiều cụm N-gram không nhìn thấy (bậc thấp) so với 
những N-gram nhìn thấy (bậc cao). Trong khi đó, có những cụm N-gram có 
nghĩa (cần thiết) bị giảm đi còn những cụm N-gram tối nghĩa lại có xác suất 
tăng lên. Để hạn chế điều này, người ta đưa thêm hệ số   thay vì cộng 1 nhằm 
cân đối lại xác suất (Phương pháp làm mịn Add- ).  


C ( wi 1wi )  MP( wi )
 
C ( wi1 )  M

1.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 Uni-gram, gọi T là số cụm Uni-gram khác nhau đã xuất hiện, còn M 
là tổng số các cụm Uni-gram đã thống kê, khi đó tổng số sự kiện sẽ là (T+M), 
và xác suất để gặp cụm Uni-gram lần đầu tiên (hay tổng xác suất của các cụm 
T
Uni-gram chưa xuất hiện lần nào) được tính bằng: 
 
T+M
Gọi  V  là kích  thước bộ  từ vựng,  còn  Z  là  số  cụm  Uni-gram  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 Uni-gram chưa xuất hiện lần nào (có tần 
số bằng 0) được tính bằng: 
T
P* = 
 
Z(T+M)


10

Và xác suất xuất hiện của các cụm Uni-gram có tần số khác 0 được tính 


 

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:  
N
c* = (c+1) *  c+1 
Nc
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: 


11

c = 

 

 

c = 

c = 

c*
P(w) =   với N =     Ncc =     Ncc* =     Nc+1(c+1) 
N
c = 0
c = 0
c = 0


Tương tự, khi áp dụng cho Tri-gram ta có: 

P(wi|wi-2wi-1)   nếu C(wi-2wi-1wi ) > 0 
PB(wi|wi-2wi-1) = 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


12

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 Ngram  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ế, 

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)                               
1.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. 
a) Môhìnhtruyhồi:

C(wi-n+1...wi) - D                             nếu C(wi-n+1...wi) > 0 
PBKN(wi|wi-n+1..wi-1)=  C(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 đó: 
o PBKN(wi)  =   

N(vwi) - D
  với  N(vw)  là  số  lượng  từ  v  khác  nhau  xuất 
 
 N(vw)
w

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


14

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

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

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

Trong đó:                               
o (wi-n+1..wi-1) =   

D N(wi-n+1..wi-1v)
 với N(wi-n+1..wi-1v) là số lượng từ v 
C(wi-n+1..wi-1)

khác nhau xuất hiện liền sau cụm wi-n+1..wi trong tập huấn luyện             
o PIKN(wi)  =     

N(vwi) - D
1
+     với  N(vw)  là  số  lượng  từ  v  khác  nhau 
 
V
 N(vw)
w

xuất hiện liền trước từ w trong tập huấn luyện. 
D N(v)
o  =   
 
 
 N(vw)

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 =   D  nếu c(w .. w ) = 2   
i-n+1
i
 2
D3 nếu c(wi-n+1.. wi) >= 3
N1
Với Y = 
 
(N1 + 2N2)
N
D1 = 1 - 2Y  2 
N1
N
D2 = 1 - 3Y  3 
N2
N
D3 = 1 - 4Y  4 
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à: Uni-gram, Bi-gram, ... có các hằng số trên là khác nhau.   
1.5. Kỹ thuật làm giảm kích thước dữ liệu: