Luận văn Mô hình ngôn ngữ sử dụng Mapreduce
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
VŨ THỊ THANH
MÔ HÌNH NGÔN NGỮ SỬ DỤNG MAPREDUCE
Ngành: Công nghệ thông tin
Chuyên ngành: Kỹ thuật phần mềm
Mã Số: 60480103
LUẬN VĂN THẠC SĨ
NGƢỜI HƢỚNG DẪN KHOA HỌC CHÍNH: TS. NGUYỄN VĂN VINH
NGƢỜI HƢỚNG DẪN KHOA HỌC PHỤ: TS. NGUYỄN PHÚ BÌNH
Hà nội – 2016
i
MỤC LỤC
MỤC LỤC.............................................................................................................................i
LỜI CẢM ƠN..................................................................................................................... iii
LỜI CAM ĐOAN................................................................................................................iv
DANH MỤC THUẬT NGỮ VIẾT TẮT.............................................................................v
Giới thiệu..............................................................................................................................6
Chƣơng 1: Mô hình ngôn ngữ ..............................................................................................8
1.1 Giới thiệu: ..................................................................................................................8
1.2 Mô hình ngôn ngữ N-gram ........................................................................................9
1.3.1 Phân bố không đều:..........................................................................................11
1.3.2 Kích thƣớc bộ nhớ của mô hình ngôn ngữ .......................................................11
1.4 Các phƣơng pháp làm mịn .......................................................................................12
1.4.1 Phƣơng pháp Add-one......................................................................................12
1.4.2 Phƣơng pháp Good – Turing ............................................................................13
1.4.3 Phƣơng pháp truy hồi back-off.........................................................................14
1.4.4 Phƣơng pháp nội suy ........................................................................................16
1.4.5 Phƣơng pháp Kneser – Ney..............................................................................16
1.4.6 Phƣơng pháp Kneser – Ney cải tiến .................................................................18
1.5 Đánh giá mô hình ngôn ngữ.....................................................................................18
1.5.1 Entropy – Độ đo thông tin: ...............................................................................19
1.5.2 Perplexity – Độ hỗn loạn thông tin:..................................................................20
1.5.3 Error rate – Tỉ lệ lỗi: .........................................................................................20
Chƣơng 2: Tổng quan về Hadoop MapReduce..................................................................22
2.2 Các thành phần của Hadoop.....................................................................................22
2.2.1 Kiến trúc hệ thống tệp phân tán........................................................................22
ii
2.3.1 Kiến trúc của Mapreduce..................................................................................23
2.3.2 Cơ chế hoạt động ..............................................................................................24
2.4 Ƣu điểm của Hadoop ...............................................................................................25
Chƣơng 3:Ƣớc lƣợng mô hình ngôn ngữ với Mapreduce..................................................26
3.1 Đếm các từ ...............................................................................................................26
3.2 Đếm số lần xuất hiện (Generate count of counts)....................................................27
3.3 Sinh số làm mịn Good-Turing..................................................................................27
3.4 Ƣớc lƣợng xác suất n-gram......................................................................................28
3.5 Sinh bảng Hbase.......................................................................................................28
3.5.1 Cấu trúc dựa trên n-gram..................................................................................28
3.5.2 Cấu trúc dựa trên từ hiện tại .............................................................................28
3.5.3 Cấu trúc dựa trên đoạn văn...............................................................................29
3.5.4 Cấu trúc dựa trên nửa ngram ............................................................................29
3.5.5 Cấu trúc dựa trên số nguyên .............................................................................30
3.6 Truy vấn trực tiếp.....................................................................................................30
Chƣơng 4: Các phƣơng pháp đánh giá và thực nghiệm .....................................................31
4.1 Các phƣơng pháp đánh giá.......................................................................................31
4.1.1 Thời gian và bộ nhớ..........................................................................................31
4.2 Thực nghiệm ............................................................................................................32
4.2.1 Môi trƣờng chạy thực nghiệm ..........................................................................32
4.2.2 Dữ liệu ..............................................................................................................32
4.2.3 Đánh giá thời gian và bộ nhớ cho các ngram ...................................................32
4.2.4 So sánh thời gian chạy với SRILM...................................................................33
iii
LỜI CẢM ƠN
Đầu tiên, cho phép tôi gửi lời cảm ơn sâu sắc tới TS Nguyễn Văn Vinh và TS
Nguyễn Phú Bình, ngƣời đã trực tiếp hƣớng dẫn, chỉ bảo và tạo điều kiện cho tôi trong
quá trình hoàn thành luận văn này.
Đồng thời tôi cũng xin gửi lời cảm ơn chân thành tới các thầy cô giáo trƣờng Đại
học Công Nghệ, Đai học Quốc Gia Hà Nội, những ngƣời đã trực tiếp giảng dạy, hƣớng
dẫn và tạo điều kiện cho tôi trong quá trình học tập và làm luận văn.
Cuối cùng, tôi xin gửi lời cảm ơn tới tất cả các bạn đồng học và gia đình đã ủng
hộ, giúp đỡ tôi hoàn thành luận văn.
iv
LỜI CAM ĐOAN
Tôi xin cam đoan kết quả trong luận văn là sản phẩm của riêng cá nhân tôi.
Trong toàn bộ nội dung của luận văn, những điều đƣợc trình bày hoặc là của cá nhân
hoặc là đƣợc tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có
xuất xứ rõ ràng và đƣợc trích dẫn hợp pháp.
Tôi xin hoàn toàn chịu trách nhiệm theo quy định cho lời cam đoan của mình.
Hà Nội, ngày 25 tháng 10 năm 2016
Ngƣời cam đoan
Vũ Thị Thanh
v
DANH MỤC THUẬT NGỮ VIẾT TẮT
STT Từ viết tắt Từ đầy đủ
Ý nghĩa
1
2
WER
ASR
Word Error Rate.
Tỉ lệ lỗi
Automatic Speech
Recognition
Nhận dạng tiếng nói tự động
3
MLE
Maximum Likelihood
Estimation
Ƣớc lƣợng hợp lý hóa cực đại.
4
5
MSE
Mean Squared Error
Sai số toàn phƣơng trung bình
Hệ thống tệp phân tán Hadoop
HDFS
Hadoop Distributed File
System
6
FIFO
First in first out
Vào trƣớc ra trƣớc
6
Giới thiệu
Ngày nay với sự phát triển của công nghệ thông tin, lƣợng dữ liệu trao đổi trên
mạng là rất lớn. Dữ liệu về văn bản, hình ảnh, âm thanh đang trở thành những nguồn
dữ liệu khổng lồ để phục vụ các nhu cầu về lƣu trữ và trao đổi thông tin của con ngƣời.
Đã có nhiều ứng dụng ra đời để hỗ trợ con ngƣời các công việc nhƣ: kiểm tra chính tả
trên các văn bản, nhận dạng dữ liệu, nhận dạng giọng nói, dịch máy thống kê. Để phát
triển các ứng dụng đó ngƣời ta đã đƣa ra mô hình ngôn ngữ nhƣ là một tiền đề để ứng
dụng vào các lĩnh vực trên. Mô hình ngôn ngữ là một vấn đề quan trọng của lĩnh vực
xử lý ngôn ngữ tự nhiên. Mô hình ngôn ngữ là các phân bố xác suất của một đoạn văn
trên một tập văn bản lớn. Vì vậy một mô hình ngôn ngữ tốt sẽ đánh giá câu đúng ngữ
pháp và độ trôi chảy tốt hơn những câu có thứ tự ngẫu nhiên. Cách thông dụng nhất
đƣợc dùng để mô hình hóa ngôn ngữ là thông qua các N-gram. Mô hình N- gram sử
dụng các tập dữ liệu văn bản lớn để ƣớc lƣợng xác suất của mô hình. Nhìn chung thì
dữ liệu càng lớn thì mô hình sẽ càng tốt hơn [13].
Khi xây dựng mô hình ngôn ngữ cần phải có một lƣợng bộ nhớ khá lớn để có thể
lƣu trữ đƣợc xác suất của tất cả các chuỗi và cần cấu hình máy phải mạnh để tính toán
và xử lý. Có nhiều phƣơng pháp, kỹ thuật đã đƣợc đƣa ra để tối ƣu bộ nhớ và bộ xử lý.
Các phƣơng pháp làm mịn, truy hồi, đồng hóa, nén là những phƣơng pháp trƣớc đây
dùng để tối ƣu giá trị xác suất và tối ƣu bit lƣu trữ. Một số ứng dụng về xây dựng mô
hình ngôn ngữ đƣợc sử dụng gần đây nhƣ công cụ SRILM, Random Forest Language
Model Toolkit, … Mục đích chính của SRILM là để hỗ trợ ƣớc lƣợng và đánh giá mô
hình ngôn ngữ. Random Forest Language Model Toolkit xây dựng dựa trên công cụ
SRILM, là một trong các mô hình ngôn ngữ cây quyết định cho kết quả thực nghiệm
khá tốt. Tuy nhiên hạn chế của các công cụ trên là với dữ liệu rất lớn thì sẽ tốn rất
nhiều thời gian để thực hiện. Với những dữ liệu cực lớn thì có thể sẽ không chạy đƣợc.
Để giải quyết bài toán với dữ liệu huấn luyện lớn thì hadoop và mapreduce là một
công cụ tối ƣu nhất. Đó chính là lý do tại sao tôi lựa chọn đề tài “ Mô hình ngôn ngữ
sử dụng MapReduce” cho nghiên cứu của mình.
Đề tài này nhằm mục đích nghiên cứu sử dụng Hadoop và MapReduce vào việc
xây dựng mô hình ngôn ngữ nhằm cải tiến tốc độ cho việc xây dựng mô hình ngôn ngữ
và ƣớc lƣợng mô hình để có thể thực hiện với lƣợng dữ liệu rất lớn để đƣa ra mô hình
ngôn ngữ chính xác hơn. Trong phần ứng dụng xây dựng mô hình ngôn ngữ với
MapReduce luận văn sẽ sử dụng phƣơng pháp làm mịn GoodTuring. Có nhiều phƣơng
pháp làm mịn có thể cho kết quả tốt hơn nhƣ Kneser-Ney nhƣng do thời gian có hạn
nên luận văn đã sử dụng phƣơng pháp làm mịn GoodTuring để đơn giản cho việc xây
dựng chƣơng trình nhƣng cũng đủ tốt để xây dựng mô hình ngôn ngữ.
7
Nội dung luận văn này đƣợc trình bày trong bốn chƣơng. Phần giới thiệu về đề
tài. Phần này trình bày các ngữ cảnh, các nghiên cứu đã có về vấn đề cần giải quyết, lý
do lựa chọn đề tài, mục tiêu của đề tài và cấu trúc nội dung của luận văn.
Chƣơng 1 trình bày các khái niệm cơ bản phục vụ cho đề tài. Chƣơng này sẽ
trình bày các kiến thức cơ bản về mô hình ngôn ngữ, mô hình N-gram, các phƣơng
pháp làm mịn và các độ đo dùng để đánh giá mô hình ngôn ngữ.
Chƣơng 2 trình bày các kiến thức cơ bản về Hadoop và MapReduce, giới thiệu
về kiến trúc của Hadoop, MapReduce cũng nhƣ cơ chế làm việc của chúng.
Chƣơng 3 sẽ trình bày về việc ứng dụng Hadoop và MapReduce vào mô hình
ngôn ngữ.
Chƣơng 4 giới thiệu về công cụ thực nghiệm và kết quả thực nghiệm.
Phần kết luận đƣa ra kết luận, định hƣớng phát triển cho đề tài. Cuối cùng là tài
liệu tham khảo.
8
Chƣơng 1: Mô hình ngôn ngữ
Trong xử lý ngôn ngữ tự nhiên, mô hình ngôn ngữ đƣợc sử dụng rộng rãi. Mô hình
ngôn ngữ đƣợc áp dụng trong nhiều lĩnh vực nhƣ nhận dạng giọng nói, dịch máy. Mô
hình ngôn ngữ ngày càng đƣợc nhận đƣợc nhiều sự quan tâm bởi các nhà khoa học.
Trong chƣơng này tôi sẽ trình bày về các kiến thức cơ bản về mô hình ngôn ngữ nhƣ
định nghĩa mô hình ngôn ngữ, mô hình n-gram, các phƣơng pháp đánh giá mô hình
ngôn ngữ và các phƣơng pháp làm mịn.
1.1 Giới thiệu:
Mô hình ngôn ngữ là một phân bố xác suất của một đoạn văn bản trên một tập dữ
liệu văn bản lớn. Ví dụ, trong ngôn ngữ tiếng việt thì xác suất của câu “Tôi ăn cơm” sẽ
cao hơn câu “cơm ăn tôi”.
Thuật ngữ mô hình ngôn ngữ bắt nguồn từ các mô hình xác suất sinh ngôn ngữ
dùng cho hệ thống nhận dạng tiếng nói đƣợc phát triển vào những năm 1980. Vào đầu
thế kỷ 20 Andrey Markov đƣa ra mô hình Markov sử dụng để lập mô hình cho chuỗi
các chữ cái. Sau đó Claude Shannon đƣa ra mô hình cho các chữ cái và các từ.
Mô hình ngôn ngữ đƣợc định nghĩa nhƣ sau: Tập V là tập các từ trong ngôn ngữ
Ví dụ khi xây dựng một mô hình ngôn ngữ cho tiếng anh chúng ta có thể có
V = {the, dog, laughs, saw, barks, cat…}
Tập V có thể rất lớn: nó có thể chứa vài nghìn hoặc chục nghìn từ và là tập hữu
hạn. Một câu trong ngôn ngữ là một tập các từ đứng gần nhau w1w2...wn (với n ≥ 1 và
wiϵ Vvới i = {1,…,(n-1)}), một ký hiệu <s> ở đầu câu và </s> ở cuối câu (hai ký hiệu
<s> và </s> không thuộc tập V).
Ví dụ:
<s> the dog barks </s>
<s> the cat laughs </s>
<s> the cat saw the dog </s>
Tập V+ là tập các câu sinh ra từ các từ trong tập V, đây là tập vô hạn bởi vì các
câu có thể có độ dài bất kỳ.
Từ đó chúng ta có định nghĩa sau:
Mô hình ngôn ngữ: Là mô hình gồm một tập hữu hạn V và một hàm
P(w1w2…wn) nhƣ sau:
1. Với cụm (w1w2…wn) Є V+, P(w1w2…wn) ≥ 0
2. w1w2…wnЄ 푉+ 푃 w1w2 … wn = 1
Khi đó P(w1w2…wn) là một phân bố xác suất của câu trên tập V+.
9
Gọi C(w1w2…wn) là số lần xuất hiện của câu w1w2…wn trong tập huấn luyện, N
là tổng các câu. Mô hình ngôn ngữ trên tập dữ liệu huấn luyện có thể định nghĩa nhƣ
sau:
C(w1w2…wn)
P(w1w2…wn) =
(1.1)
N
Tuy nhiên đây không phải là một mô hình tốt vì trên thực tế nó sẽ cho xác suất
bằng 0 cho các câu không có trong tập huấn luyện, do đó không thể tổng quát hóa cho
trƣờng hợp câu không có trong tập V+. Mặc dù có hạn chế nhƣng mô hình ngôn ngữ
vẫn đƣợc xem xét để nghiên cứu cải tiến vì những lý do sau:
1. Mô hình ngôn ngữ rất cần thiết cho những ứng dụng lớn nhƣ nhận diện
giọng nói và dịch máy.
2. Từ các kỹ thuật định nghĩa hàm P và cho sự ƣớc lƣợng các tham số từ tập
huấn luyện sẽ cho kết quả với nhiều ngữ cảnh khác nhau nhƣ mô hình ngôn
ngữ Markov ẩn.
1.2 Mô hình ngôn ngữ N-gram
Nhiệm vụ của mô hình ngôn ngữ là cho biết xác suất của một câu w1w2…wn là
bao nhiêu. Theo công thức Bayes: P(AB) = P(B|A)*P(A), thì có thể suy ra đƣợc
P(w1w2…wm) = P(w1)*P(w2|w1)* P(w3|w1 w2) * ….* P(wm|w1w2…wm-1). (1.2)
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ó. Do đó mô hình cần một
lƣợng bộ nhớ khá lớn để lƣu xác xuất của tất cả các cụm từ. Rõ ràng công thức này
vẫn không hiệu quả khi chiều dài của các cụm từ lớn. Để có thể tính đƣợc xác suất của
văn bản với bộ nhớ chấp nhận đƣợc thì ta có thể sử dụng xấp xỉ Markov với giả định
rằng xác suất của một từ chỉ phụ thuộc vào hữu hạn từ trƣớc đó chứ không phải phụ
thuộc toàn bộ vào dãy đứng trƣớc. Xấp xỉ Markov có thể dự đoán xác suất của một từ
khi biết 1,…,n từ trƣớc đó. Nhƣ vậy công thức tính xác suất văn bản (1.2) tƣơng
đƣơng với công thức sau:
P(w1w2…wm) = P(w1) * P(w2|w1) * P(w3|w1w2) *…* P(wm-1|wm-n-1wm-n
…wm-2)* P(wm|wm-nwm-n+1…wm-1)
(1.3)
Mô hình Markov còn đƣợc gọi là mô hình N-gram [1][2].
Ví dụ cho câu sau: “This is a sentence”, mô hình N-gram cho câu đó nhƣ sau
N = 1(unigrams): This,
is,
a,
sentence
10
N = 2 (bigrams): This is,
is a,
a sentence
N = 3 (trigrams): This is a,
is a sentence
Áp dụng công thức xấp xỉ Markov cho các mô hình N-gram sẽ tƣơng đƣơng với
các công thức sau:
Với N = 1: Mô hình ngôn ngữ Unigram
P(wk|w1,…,wk-1) ≈ P(wk)
P(w1,w2,…,wT) ≈ P(w1) P(w2) …P(wT)
Với N = 2: Mô hình ngôn ngữ Bigram
P(wk|w1,…,wk-1) ≈ P(wk|wk-1)
P(w1,w2,…,wT) ≈ P(w1|<S>) P(w2|w1) …P(wT|wT-1)
Với N = 3: Mô hình ngôn ngữ Trigram
P(wk|w1,…,wk-1) ≈ P(wk|wk-2, wk-1)
P(w1,w2,…,wT) ≈ P(w1|<S><S>) …P(wT| wT-2wT-1)
Xây dựng mô hình N-Gram
Sử dụng những câu có sẵn để tính các ƣớc lƣợng xác xuất n-gram
Chúng ta sử dụng các thuật ngữ sau [1]:
N = Tổng số các từ trong tập huấn luyện
V = Tập từ vựng
C(w1,…,wk) = số lần xuất hiện của n-gram w1,…,wk trong tập
huấn luyện
P(w1,…,wk) = ƣớc lƣợng xác suất cho n-gram w1,…,wk
P(wk| w1,…,wk-1) = xác xuất của wk với lịch sử w1,…,wk-1
Áp dụng ƣớc lƣợng hợp lý hóa cực đại cho xác xuất n-gram cụ thể nhƣ sau:
C(wi)
N
Unigram: P(wi) =
C(wi,wj)
Bigram: P(wi,wj) =
N
P(wi, wj) C(wi, wj)
P(wj|wi) =
=
P(wi)
C(wi)
Sử dụng tần số tƣơng đối khi ƣớc lƣợng
Ƣớc lƣợng hợp lý hóa cực đại của tập dữ liệu huấn luyện cho mô hình là P(D|M)
11
Xét ví dụ với tập huấn luyện nhƣ sau:
<s> I am sam </s>
<s> Sam I am </s>
<s> I do not like green eggs and ham </s>
Xác xuất 2-gram của tập dữ liệu trên sẽ là
2
1
P(I| <s>) = = 0.67
3
P(Sam| <s>) = = 0.33
3
2
1
P(am| I) = = 0.67
3
P(do |I) = = 0.33
3
1
1
P(</s>| Sam) = = 0.5
2
P(sam| am) = = 0.5
2
1.3 Khó khăn khi xây dựng mô hình ngôn ngữ N-gram
1.3.1 Phân bố không đều:
Khi sử dụng mô hình N-gram 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
các câu có chứa các cụm n-gram này sẽ có kết quả tồi. Với V là kích thƣớc bộ từ vựng,
ta sẽ có Vn 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ụ: tiếng Việt có khoảng hơn 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.
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 Ngram
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”
1.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 Ngram 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ó 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
12
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.
1.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ố thƣa nhƣ đã đề cập ở phần
1.3.1 ngƣời ta đã đƣa ra các phƣơng pháp làm mịn. Thuật ngữ làm mịn (smoothing) sử
dụng cho việc đánh giá lại xác suất của các cụm N-gram. Các phƣơng pháp làm mịn có
thể chia thành các loại nhƣ sau:
Chiết khấu (Discounting): giảm xác suất của các cụm N-gram 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. Ví dụ: phƣơng
pháp Add-one, Good-Turing.
Truy hồi (Back-off): tính toán xác suất của 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 ngắn hơn có xác suất lớn hơn 0. Ví dụ:
Katz back-off.
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 Phƣơng pháp Add-one
Phƣơng pháp làm mịn Add-one hay còn gọi là phƣơng pháp làm mịn Laplace
Smoothing thực hiện cộng thêm 1 vào tần số xuất hiện của tất cả các cụm N-gram
[3][4]
Xác suất của các cụm 1 từ wi với tần suất xuất hiện là ci là:
Ci
P(wi) =
N
Phƣơng pháp Add-one thêm 1 vào các ci, với V là số các từ trong bộ dữ liệu từ
điển, ta có xác suất nhƣ sau:
Ci+1
PAdd-one(wi) =
N+V
N
N+V
Đặt C* = (Ci+1)
Thì khi đó công thức xác xuất sẽ là
C*
P*(wi) =
N
Với các cụm 2-gram thì ta có công thức sau
13
C(wi,wj)
N
C(wi, wj)+1
N+V2
P(wi,wj) =
=> PAdd-one(wi, wj) =
PAdd-one(wi, wj) C(wi,wj)+1
Khi đó PAdd-one(wj|wi) =
=
PAdd-one(wi)
Xét các cụm N-gram với N>1thì xác suất của cụm wi-n+1...wi-1wi đƣợc tính theo
công thức sau:
C(wi)+V
C(wi-n+1...wi-1wi) + 1
C(wi-n+1...wi-1) + V
P(wi|wi-n+1...wi-1) =
(1.4)
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 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 Ngram đó không cao. Để
thuật toán thêm hiệu quả, ngƣời ta sử dụng công thức sau:
C(w1w2...wn) +
C(w1w2...wn-1) + M
P(w1w2...wn) =
(1.5)
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
1
2
= : đƣợc gọi là thuật toán Jeffreys – Perks
Phƣơng pháp Add-one có ƣu điểm là dễ cài đặt tính toán. Nhƣợc điểm là làm
giảm xác suất của những cụm từ hay xuất hiện trong tập huấn luyện. Nếu tỉ lệ các từ
không xuất hiện càng lớn thì xác suất gán cho các từ này sẽ tăng và làm giảm đáng kể
xác suất của các từ khác.
1.4.2 Phƣơng pháp Good – Turing
Ý tƣởng của các phƣơng pháp làm mịn bằng phƣơng pháp chiết khấu là đếm tần
suất xuất hiện của các từ có trong tập huấn luyện để tính xác suất của các từ chƣa xuất
hiện. Thuật toán Good-Turing [5][6] đƣợc đƣa ra đầu tiên bởi Good. Thuật toán Good-
Turing thực hiện ƣớc lƣợng lại xác suất của những cụm từ (N-gram) có tần suất bằng 0
dựa trên số các từ có tần suất xuất hiện bằng 1.
14
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)
Tổng quát ta có :
Nc = 푥:푐표푢푛푡 푥 =푐 1
Khi đó, với mỗi c một ƣớc lƣợng tần số đƣợc tính nhƣ sau:
Nc+1
c* = (c+1)
Nc
Dùng công thức trên thay thế công thức MLE với bigram thì ta có công thức xác
xuất sau:
CGT(wi,wj)
N
PGT(wi, wj) =
PGT(wj|wi) =
CGT(wi,wj)
C(wi)
Với những bigram chƣa xuất hiện:
N1
c* = CGT = (0+1)
N0
CGT
PGT =
N
Số cụm N-gram không xuất hiện lần nào trong bigram đƣợc tính nhƣ sau
N0 = V2 – những bigram đã xuất hiệ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ố. Để đơn giản,
ngƣời ta chọn k đủ lớn dựa vào kết quả huấn luyện.
1.4.3 Phƣơng pháp truy hồi back-off
Giống nhƣ thuật toán chiết khấu, thuật toán truy hồi đƣợc sử dụng để giải quyết
các vấn đề của tần suất bằng 0 trong N-gram. Ý tƣởng của thuật toán backoff là tìm
một (N-1) – gram nếu không có N- gram trong một chuỗi. Tiếp tục lùi lại các N-gram
trƣớc đó cho đến khi có tần suất lớn hơn 0.
15
Ví dụ với trigram chúng ta không có chuỗi wn-2wn-1wn để tính P(wn|wn-2wn-1) thì có
thể dùng xác suất bigram P(wn|wn-1). Tƣơng tự nhƣ vậy nếu không thể tính P(wn|wn-1)
chúng ta có thể dùng unigram P(wn).
Thuật toán backoff đƣợc đƣa ra bởi Katz và công thức tính xác suất đƣợc đƣa ra
nhƣ sau:
n-1
P*(wn|wn-N-1
)
nếu C(wnn-N+1) >0
Pkatz(wn|wn-N-1) =
(1.6)
α( wn-1n-N+1)Pkatz(wn| wn-1n-N+2) nếu C(wnn-N+1) = 0
Áp dụng mô hình này cho 3-gram. Với “x, y, z” là một 3-gram thì
P*(z|xy)
nếu C(xyz) > 0
Pkatz(z|xy) =
α(x, y)Pkatz(z|y)
P*(z)
nếu C(xyz) = 0 và C(xy) > 0
trƣờng hợp còn lại
Với 2 – gram thì:
PGT(z|y)
nếu C(yz) > 0
nếu ngƣợc lại
Pkatz(z|y) =
α(y)PGT(z)
Katz kết hợp phƣơng pháp chiết khấu và giá trị α để cho tổng xác suất bằng 1. Vì
nếu sử dụng xác suất MLE và dùng truy hồi về các gram nhỏ hơn thì xác suất sẽ đƣợc
tính thêm một lƣợng, do đó tổng xác suất sẽ khác 1. Hệ số α sẽ đảm bảo tổng xác suất
ở mức dƣới bằng lƣợng để chiết khấu cho mức trên.
Sự chính xác của mô hình phụ thuộc vào hệ số α. Có một số kỹ thuật để chọn α
tùy theo tập huấn luyện và mô hình ngôn ngữ. Một cách đơn giản là chọn α là một
hằng số. Tuy nhiên rất khó để chọn một hằng số sao cho tổng xác suất của tất cả các
N-gram không đổi. Gọi β là hàm biểu diễn tổng xác suất bên trái của hàm xác suất
khối, β là một hàm của cụm (N-1) –gram. Hàm β tính bằng 1 trừ đi tổng xác suất khối
giảm tại mức N –gram.
Mỗi cụm từ trong (N-1) – gram sẽ nhận một phần nhỏ trong khối xác suất.
16
1.4.4 Phƣơng pháp nội suy
Các phƣơng pháp chiết khấu đƣợc để cập trong mục trên giúp giải quyết đƣợc
vấn đề của các cụm từ có tần suất xuất hiện bằng 0. Giả sử phải tính xác suất có điều
kiện P(wn| wn-1wn-2) nhƣng không có cụm từ wn-2wn-1wn trong tập huấn luyện. Xác xuất
này có thể tính thông qua xác suất của P(wn|wn-1). Nếu không tính đƣợc xác suất
P(wn|wn-1) ta sử dụng P(wn). Có hai cách để thực hiện điều này là dùng phƣơng pháp
truy hồi và phƣơng pháp nội suy. Phƣơng pháp truy hồi sẽ thực hiện truy hồi xuống
mức thấp khi mà tần suất của cụm từ đó bằng 0. Ngƣợc lại phƣơng pháp nội suy thực
hiện kết hợp các xác xuất ở các N-gram.
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|wi-2wi-1) + 2P(wi|wi-1) + 3P(wi) với i = 1
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ó
1
3
thể chọn tất cả bằng nhau và bằng .
Tuy nhiên, cũng có thể chọn các tham số nhƣ là một hàm của Ngram:
1 = 1(wi-2wi-1wi), 2 = 2(wi-1wi) và 3 = 3(wi)
1.4.5 Phƣơng pháp Kneser – Ney
Kneser và Ney đƣa ra phƣơng pháp nội suy bằng các kết hợp xác suất ở gram
mức dƣới và xác suất ở gram mức trên [7][8]. Ví dụ khi xây dựng mô hình 2-gram trên
tập dữ liệu huấn luyện xem xét trƣờng hợp từ Francisco luôn xuất hiện sau từ San. Khi
c(Francisco) cao thì xác suất 1-gram P(Francisco) cũng sẽ cao. Tuy nhiên trong trƣờng
hợp c(Francisco) thấp và từ Francisco chỉ đứng sau mỗi từ San nhƣng xác suất 2-gram
thì lại cao. Phƣơng pháp Kneser-Ney xác suất của từ không tính dựa trên tần suất xuất
hiện của từ đó mà dựa trên số từ khác nhau mà nó đứng liền kề sau. Phƣơng pháp này
đƣợc xây dựng theo hai mô hình là truy hồi và nội suy.
Mô hình truy hồi:
C(wi-n+1...wi) - D
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
nếu C(wi-n+1...wi) > 0
PBKN(wi|wi-n+1..wi-1) =
(1.7)
Trong đó:
17
N(vwi) - D
o PBKN(wi) =
với N(vw) là số lƣợng từ v khác nhau xuất hiện
N(vw)
w
trƣớc w trong tập huấn luyện
Nhƣ vậy:
C(w w w ) - D
i-2 i-1
i
nếu C(wi-2wi-1wi) > 0
C(wi-2wi-1)
PBKN(wi|wi-2wi-1) =
(ww)PBKN(wi|wi-1) nếu C(wi-2wi-1wi) = 0
C(w w ) - D
i-1
i
nếu C(wi-1wi) > 0
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
Mô hình nội suy:
C(wi-n+1..wi) - D
C(wi-n+1..wi-1)
PIKN(wi|wi-n+1..wi-1) =
Trong đó:
+ (wi-n+1..wi-1)PIKN(wi|wi-n+2..wi-1) (1.8)
D N(wi-n+1..wi-1v)
C(wi-n+1..wi-1)
o (wi-n+1..wi-1) =
với N(wi-n+1..wi-1v) là số lƣợng từ v
khác nhau xuất hiện liền sau cụm wi-n+1..wi trong tập huấn luyện
N(vwi) - D
1
V
o PIKN(wi) =
+ với N(vw) là số lƣợng từ v khác nhau xuất
N(vw)
w
hiện liền trƣớc từ w trong tập huấn luyện.
D N(v)
o =
N(vw)
w
Nhƣ vậy:
PIKN(wi|wi-2wi-1) =
C(wi-2wi-1wi) - D
C(wi-2wi-1)
+ (wi-2wi-1)PIKN(wi|wi-1)
+ (wi-1)PIKN(wi)
C(wi-1wi) - D
PIKN(wi|wi-1) =
C(wi-1)
N(vwi) - D
1
V
PIKN(wi) =
+
N(vw)
w
18
N1
N1 + 2N2
Trong cả 2 mô hình nội suy và truy hồi, D đƣợc chọn: D =
1.4.6 Phƣơng pháp Kneser – Ney cải tiến
Phƣơng pháp làm mịn Kneser-Ney cải tiến đƣợc Chen và Goodman đƣa ra năm
1999. Phƣơng pháp này đƣợc pháp triển từ thuật toán Kneser-Ney. Thay vì sử dụng
chiết khấu đơn D cho tất cả các từ có số lần xuất hiện bằng 0 trong phƣơng pháp
Kneser-Ney, phƣơng pháp này đƣa ra ba giá trị chiết khấu D1, D2, D3 cho các N-gram
có số lần xuất hiện bằng 1, 2 và 3.
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
D2 nếu c(wi-n+1.. wi) = 2
D3 nếu c(wi-n+1.. wi) >= 3
D =
N1
Với Y =
(N1 + 2N2)
N2
D1 = 1 - 2Y
N1
N3
D2 = 1 - 3Y
N2
N4
D3 = 1 - 4Y
N3
Trong đó: Ni là số lƣợng cụm N-gram có số lần xuất hiện
1.5 Đánh giá mô hình ngôn ngữ
Rất nhiều mô hình ngôn ngữ đã đƣợc đƣa ra thì một câu hỏi cho những ngƣời sử
dụng là làm sao để biết đƣợc mô hình nào tốt hay dở. Cách tốt nhất là đƣa mô hình đó
nhúng vào một ứng dụng khác để đánh giá. Ví dụ với hệ thống nhận dạng tiếng nói
ngƣời ta thực hiện so sánh hiệu năng của hai mô hình ngôn ngữ bằng cách chạy lần
lƣợt từng mô hình và xem kết quả trả về. Hạn chế của cách đánh giá này là phải nhờ
đến hệ thống bên ngoài và thƣờng chi phí đắt và khá lâu. Vì vậy các nhà nghiên cứu đã
đƣa ra các phƣơng pháp đánh giá hiệu quả của mô hình ngôn ngữ độc lập với ứng
dụng. Các phƣơng pháp đó là
Entropy - Độ đo thông tin
Perplexity - Độ hỗn loạn thông tin
19
Error rate - Tỉ lệ lỗi
1.5.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 Ngram[1]. 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:
1
m
1
m
H(w1, w2,...,wm) = -
p(w1, w2, ..., wm)log2p(w1, w2, ..., 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. 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:
1
H(L) = - lim H(w1, w2, ..., wm)
m m
1
= - lim
p(w1, w2, ..., wm)log2p(w1, w2, ..., wm)
W L
m m
Đị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:
1
H(L) = - lim log p(w1, w2, ..., wm)
m m
Với công thức trên, ta có thể sử dụng công thức Bayes và xác suất của các n-
gram để tính p(w1, w2, ..., wn):
Tải về để xem bản đầy đủ
36 trang
22220
Free
Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Mô hình ngôn ngữ sử dụng Mapreduce", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- luan_van_mo_hinh_ngon_ngu_su_dung_mapreduce.pdf
