Khóa luận Xây dựng mô hình ngôn ngữ cho tiếng Việt
Mô hình ngôn ngữ Ngram - Cao Văn Việt K51KHMT
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Cao Văn Việt
XÂY DỰNG MÔ HÌNH NGÔN NGỮ CHO TIẾNG VIỆT
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Khoa học máy tính
HÀ NỘI – 2010
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 Lê Anh Cường, 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ệ, đặc biệt là các thầy cô trong bộ môn Khoa học Máy tính , 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à thực hành ở trường.
Cuối cùng, tôi xin gửi gờ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
TÓM TẮT
Mô hình ngôn ngữ là một bộ phận quan trọng của lĩnh vực xử lý ngôn ngữ tự
nhiên. Có rất nhiều lĩnh vực trong xử lý ngôn ngữ tự nhiên sử dụng mô hình ngôn ngữ
như: kiểm lỗi chính tả, dịch máy hay phân đoạn từ... Trên thế giới đã có rất nhiều nước
công bố nghiên cứu về mô hình ngôn ngữ áp dụng cho ngôn ngữ của họ nhưng ở Việt
Nam, việc nghiên cứu và xây dựng một mô hình ngôn ngữ chuẩn cho tiếng Việt vẫn
còn mới mẻ và gặp nhiều khó khăn. Chính điều này đã gợi ý và thúc đẩy chúng tôi lựa
chọn và tập trung nghiên cứu vấn đề này để có thể tạo điều kiện cho việc xử lý ngôn
ngữ tiếng Việt vốn vô cùng phong phú của chúng ta.
Luận văn sẽ trình bày khái quát về mô hình ngôn ngữ, đồng thời chỉ ra các khó
khăn còn tồn tại để rồi đưa ra những phương pháp khắc phục, trong đó trọng tâm
nghiên cứu các phương pháp làm mịn. Trong luận văn này này, chúng tôi sử dụng chủ
yếu bộ công cụ mã nguồn mở SRILIM để xây dựng mô hình ngôn ngữ cho tiếng Việt,
sau đó áp dụng mô hình ngôn ngữ đã tạo ra để tính toán độ hỗn loạn thông tin của văn
bản và dịch máy thống kê. Kết quả có được sẽ là cơ sở chính để chúng tôi chỉ ra
phương pháp làm mịn nào là tốt nhất khi sử dụng trong việc xây dựng mô hình ngôn
ngữ tiếng Việt.
MỤC LỤC
Chương 1 Giới thiệu vấn đề................................................................................ 1
1.1 Đặt vấn đề: ......................................................................................................... 1
1.2 Mục tiêu: ............................................................................................................ 1
1.3 Cấu trúc của luận văn: ........................................................................................ 2
Chương 2 Mô hình ngôn ngữ Ngram: ................................................................. 3
2.1 Khái quát:........................................................................................................... 3
2.2 Công thức tính “xác suất thô”:............................................................................ 3
2.3 Khó khăn khi xây dựng mô hình ngôn ngữ N-gram ............................................ 4
2.3.1 Phân bố không đều: .................................................................................................4
2.3.2 Kích thước bộ nhớ của mô hình ngôn ngữ................................................................5
2.4 Các phương pháp làm mịn .................................................................................. 5
2.4.1 Các thuật toán chiết khấu (discounting): .................................................................5
2.4.2 Phương pháp truy hồi:..............................................................................................8
2.4.3 Phương pháp nội suy: ............................................................................................10
2.4.4 Phương pháp làm mịn Kneser - Ney: .....................................................................10
2.4.5 Phương pháp làm mịn Kneser - Ney cải tiến bởi Chen - GoodMan: .......................12
2.5 Kỹ thuật làm giảm kích thước dữ liệu:.............................................................. 13
2.5.1 Loại bỏ (pruning):..................................................................................................13
2.5.2 Đồng hóa (Quantization):.......................................................................................15
2.5.3 Nén (Compression):...............................................................................................16
2.6 Độ đo:............................................................................................................... 16
2.6.1 Entropy – Độ đo thông tin:.....................................................................................16
2.6.2 Perplexity – Độ hỗn loạn thông tin:........................................................................18
2.6.3 Error rate – Tỉ lệ lỗi: ..............................................................................................18
Chương 3 Ứng dụng của mô hình ngôn ngữ trong mô hình dịch máy thống kê:19
3.1 Dịch máy:......................................................................................................... 19
3.2 Dịch máy thống kê:........................................................................................... 19
3.2.1 Giới thiệu: .............................................................................................................19
3.2.2 Nguyên lý và các thành phần: ................................................................................19
3.2.3 Mô hình dịch: ........................................................................................................21
3.2.4 Bộ giải mã: ............................................................................................................25
3.3 Các phương pháp đánh giá bản dịch: ................................................................ 25
3.3.1 Đánh giá trực tiếp bằng con người: ........................................................................25
3.3.2 Đánh giá tự động: phương pháp BLEU..................................................................26
Chương 4 Thực nghiệm: ................................................................................... 28
4.1 Công cụ: ........................................................................................................... 28
4.1.1 Bộ công cụ trợ giúp xây dựng tập văn bản huấn luyện: ..........................................28
4.1.2 Công cụ tách từ cho tiếng Việt - vnTokenizer: .......................................................28
4.1.3 Bộ công cụ xây dựng mô hình ngôn ngữ - SRILM:................................................29
4.1.4 Bộ công cụ xây dựng mô hình dịch máy thống kê – MOSES: ................................32
4.2 Dữ liệu huấn luyện: .......................................................................................... 34
4.3 Kết quả:............................................................................................................ 34
4.3.1 Số lượng các cụm ngram:.......................................................................................34
4.3.2 Tần số của tần số: ..................................................................................................36
4.3.3 Cut-off (loại bỏ):....................................................................................................39
4.3.4 Các phương pháp làm mịn: ....................................................................................40
4.3.5 Áp dụng vào mô hình dịch máy thống kê:..............................................................41
Chương 5 Kết luận............................................................................................ 43
Tài liệu tham khảo................................................................................................ 44
Danh sách các bảng sử dụng trong luận văn:
Bảng 4-1: số lượng các cụm Ngram trong văn bản huấn luyện với âm tiết.................35
Bảng 4-2: số lượng các cụm Ngram trong văn bản huấn luyện với từ.........................36
Bảng 4-3: tần số của tần số các cụm Ngram áp dụng cho âm tiết ...............................37
Bảng 4-4: tần số của tần số các cụm Ngram với từ.....................................................38
Bảng 4-5: bộ nhớ và độ hỗn loạn thông tin khi áp dụng loại bỏ trong âm tiết.............39
Bảng 4-6: bộ nhớ và độ hỗn loạn thông tin khi áp dụng loại bỏ với từ .......................40
Bảng 4-7: độ hỗn loạn thông tin của các phương pháp làm mịn cho âm tiết ...............40
Bảng 4-8: độ hỗn loạn thông tin của các phương pháp làm mịn cho từ.......................41
Bảng 4-9: điểm BLEU của bản dịch máy với mô hình ngôn ngữ sử dụng dữ liệu huấn
luyện có kích thước nhỏ (50Mb)................................................................................41
Bảng 4-10: điểm BLEU của bản dịch máy với mô hình Ngram sử dụng dữ liệu huấn
luyện có kích thước lớn (300Mb)...............................................................................42
Danh sách các hình sử dụng trong luận văn:
Hình 3-1: mô hình dịch máy thống kê từ tiếng Anh sang tiếng Việt...........................20
Hình 3-3: sự tương ứng một - một giữa câu tiếng Anh và câu tiếng Pháp...................21
Hình 3-4: sự tương ứng giữa câu tiếng Anh với câu tiếng Tây Ban Nha khi cho thêm từ
vô giá trị (null) vào đầu câu tiếng Anh.......................................................................22
Hình 3-5: sự tương ứng một - nhiều giữa câu tiếng Anh với câu tiếng Pháp...............22
Hình 3-6: sự tương ứng nhiều - nhiều giữa câu tiếng Anh với câu tiếng Pháp. ...........22
Hình 3-7: mô hình dịch dựa trên cây cú pháp.............................................................25
Hình 3-8: sự trùng khớp của các bản dịch máy với bản dịch mẫu...............................26
Hình 4-1: số lượng các cụm Ngram với âm tiết khi tăng kích thước dữ liệu...............35
Hình 4-2: số lượng các cụm Ngram với từ khi tăng kích thước dữ liệu.......................36
Hình 4-3: số lượng các cụm Ngram (âm tiết) có tần số từ 1 đến 10............................37
Hình 4-4: số lượng các cụm Ngram (từ) có tần số từ 1 đến 10....................................38
Chương 1 Giới thiệu vấn đề
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 [10]. 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 sâu về ngôn ngữ học.
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à 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. Cốt lõi nhất của
các phương pháp xử lý ngôn ngữ tự nhiên dựa trên thống kê chính là việc xây dựng mô
hình ngôn ngữ.
Mô hình ngôn ngữ là một phân bố xác suất trên các tập văn bản [2][10]. Nói đơn
giản, mô hình ngôn ngữ có thể cho biết xác suất một câu (hoặc cụm từ) thuộc một
ngôn ngữ là bao nhiêu.
Ví dụ: khi áp dụng mô hình ngôn ngữ cho tiếng Việt:
P[“hôm qua là thứ năm”] = 0.001
P[“năm thứ hôm là qua”] = 0
Mô hình ngôn ngữ được áp dụng trong rất nhiều lĩnh vực của xử lý ngôn ngữ tự
nhiên như: kiểm lỗi chính tả, dịch máy hay phân đoạn từ... Chính vì vậy, nghiên cứu
mô hình ngôn ngữ chính là tiền đề để nghiên cứu các lĩnh vực tiếp theo.
Mô hình ngôn ngữ có nhiều hướng tiếp cận, nhưng chủ yếu được xây dựng theo
mô hình Ngram. Vấn đề này sẽ trình bày rõ ràng hơn trong chương 2.
1.2 Mục tiêu:
1
Mục tiêu chính của luận văn là tìm hiểu lý thuyết về mô hình Ngram 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
dịch máy thống kê, chúng tôi đã 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ữ. Để đạt được thành tựu đó, chúng tôi cũng đã phải tìm
hiểu lý thuyết dịch máy thống kê và thực nghiệm dựa trên bộ công cụ Moses.
1.3 Cấu trúc của luận văn:
Luận văn có cấu trúc như sau:
Chương 2 xem xét các vấn đề liên quan đến mô hình ngôn ngữ Ngram, các sự cố
gặp phải và cách khắc phục.
Chương 3 đề cập đến lý thuyết mô hình dịch máy thống kê.
Chương 4, 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ữ, mô
hình dịch máy thống kê và các kết quả đạt được
Chương 5 tổng kết lại những gì luận văn đạt được và đưa ra kế hoạch nghiên cứu
trong tương lai.
2
Chương 2 Mô hình ngôn ngữ Ngram:
2.1 Khái quát:
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...wm là
bao nhiêu. Theo công thức Bayes: P(AB) = P(B|A) * P(A), thì:
P(w1w2…wm) = P(w1) * P(w2|w1) * P(w3|w1w2) *…* P(wm|w1w2…wm-1)
Theo công thức này, 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) *…* 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ừ. Mô hình ngôn ngữ này gọi là mô hình ngôn ngữ N-gram.
Một cụm N-gram là một dãy con gồm n phần tử liên tiếp của 1 dãy các phần tử
cho trước (trong bộ dữ liệu huấn luyện) [2].
Ví dụ: cụm 2-gram “tôi đã” thuộc câu “tôi đã từng đọc quyển sách ấy”.
Các phần tử được xét ở đây thường là kí tự, từ hoặc cụm từ; tùy vào mục đích
sử dụng. Dựa vào số phần tử của 1 cụm N-gram, ta có các tên gọi cụ thể:
N = 1: Unigram
N = 2: Bigram
N = 3: Trigram
2.2 Công thức tính “xác suất thô”:
3
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:
C(wi-n+1...wi-1wi)
P(wi|wi-n+1...wi-1) =
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 trong
w
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.
2.3 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:
Khi sử dụng mô hình N-gram 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 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” kết quả thống kê mà chúng ta sẽ đề cập ở phần 2.5.
4
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 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
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ố thưa như đã đề cập ở phần
2.4.1, người ta đã đưa ra các phương pháp “làm mịn” 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) 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 (có
xuất hiện khi thống kê) thành một giá trị phù hợp (tổng xác suất không
đổi).
Các phương pháp làm mịn có thể được chia ra thành 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 Ngram 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 Ngram không xuất hiện
trong tập huấn luyện dựa vào các cụm Ngram ngắn hơn 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 Ngram dựa
vào xác suất của các cụm Ngram ngắn hơn.
2.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 Ngram chưa từng xuất hiện trong tập huấn luyện
[10]. 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
Ngram. Ở đây đề cập đến 3 thuật toán chiết khấu phổ biến:
5
Thuật toán Add-one
Thuật toán Witten-Bell
Thuật toán Good-Turing
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 tần số xuất hiện của tất cả các cụm
N-gram rồi nhân với phân số chuẩn hóa (để bảo toàn tổng xác suất).
Với unigram, khi cộng thêm 1 vào tần số của mỗi cụm unigram, thì tổng số cụm
unigram đã xuất hiện bằng:
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:
M
M’
Ci* = (Ci+1)
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:
Ci* (Ci+1)
Pi* =
=
M
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:
C(wi-n+1...wi-1wi) + 1
P(wi|wi-n+1...wi-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
Ngram đã 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 Ngram 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) +
P(w1w2...wn) =
C(w1w2...wn-1) + M
6
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 Ngram, 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
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ần
T
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 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ố bằng
0) được tính bằng:
T
P* =
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:
c(w)
T+M
P(w) =
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(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:
7
T(wi-n+1...wi-1)
Z(wi-n+1...wi-1)(C(wi-n+1...wi-1) + T(wi-n+1...wi-1))
P(wi|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 tính bằng công thức:
C(wi-n+1...wi-1wi)
P(wi|wi-n+1...wi-1) =
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:
Nc+1
Nc
c* = (c+1) *
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 =
c =
c =
c*
N
P(w) = với N = Ncc = Ncc* = Nc+1(c+1)
c = 0
c = 0
c = 0
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 (ví dụ giá trị lớn nhất)
2.4.2 Phương pháp truy hồi:
Trong các phương pháp chiết khấu như Add-One hay Witten-Bell, nếu cụm
wi-n+1...wi-1wi không xuất hiện trong tập huấn luyện, và cụm wi-n+1...wi-1 cũng không
xuất hiện, thì xác suất của cụm wi-n+1...wi-1wi 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 Ngram chưa
8
xuất hiện lần nào dựa vào xác suất của các cụm Ngram ngắn hơn có xác suất khác 0
[10][4].
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(w |wi-n+1...wi-1)
nếu C(wi-n+1...wi-1wi) > 0
i
PB(wi|wi-n+1...wi-1) =
* P (w |wi-n+2...wi-1) nếu C(wi-n+1...wi-1wi) = 0
B
i
Áp dụng cho bigram, ta có:
P(w |w ) nếu C(w w ) > 0
i
i-1
i-1
i
PB(wi|wi-1) =
* P(w ) nếu C(w w ) = 0
i
i-1
i
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ó:
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
PB(wi|wi-2wi-1) =
2 * P(wi)
nếu C(wi-2wi-1wi ) = 0 và C(wi-1wi ) = 0
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 Ngram:
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 Ngram
sẽ luôn lớn hơn 1, do xác suất của các cụm Ngram đã xuất hiện thì không thay đổi,
trong khi xác suất của các cụm Ngram 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ư
9
Witten-Bell hay Good-Turing để làm giảm xác suất của các cụm Ngram đã 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)
Trong đó P’ chính là xác suất của cụm Ngram khi áp dụng thuật toán làm mịn
chiết khấu.
nếu C(wi-2wi-1wi) = 0 và C(wi-1wi) = 0
2.4.3 Phương pháp nội suy:
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 Ngram ngắn hơn để tính xác suất của cụm Ngram dài hơn”[1][2]. 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 Ngram.
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)
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.
Mô hình truy hồi:
10
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) =
Trong đó:
o PBKN(wi) =
N(vwi) - D
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
C(wi-n+1..wi-1w) - D
w:C(wi-n+1..wi-1w)>0
1 -
1 -
C(wi-n+1..wi-1)
o (wi-n+1..wi-1) =
PBKN(w|wi-n+2..wi-1)
w:C(wi-n+1..wi-1w>0)
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) =
(w w )PBKN(wi|wi-1) nếu C(wi-2wi-1wi) = 0
C(w w ) - D
i-1
i
nếu C(wi-1wi) > 0
(w )PBKN(wi) nếu C(wi-1wi) = 0
C(wi-1)
PBKN(wi|wi-1) =
i-1
N(vwi) - D
PBKN(wi) =
N(vw)
w
Mô hình nội suy:
PIKN(wi|wi-n+1..wi-1) =
Trong đó:
C(wi-n+1..wi) - D
C(wi-n+1..wi-1)
+ (wi-n+1..wi-1)PIKN(wi|wi-n+2..wi-1)
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
11
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)
C(wi-1wi) - D
PIKN(wi|wi-1) =
+ (wi-1)PIKN(wi)
C(wi-1)
N(vwi) - D
1
V
PIKN(wi) =
+
N(vw)
w
N1
N1 + 2N2
Trong cả 2 mô hình nội suy và truy hồi, D được chọn: D =
2.4.5 Phương pháp làm mịn Kneser - Ney cải tiến bởi 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 =
i-n+1.. wi) = 2
D3 nếu c(wi-n+1.. wi) >= 3
D nếu c(w
2
N1
Với Y =
(N1 + 2N2)
N2
D1 = 1 - 2Y
N1
N3
D2 = 1 - 3Y
N2
12
N4
N3
D3 = 1 - 4Y
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 kỹ thuật
chính, bao gồm:
Pruning (loại bỏ): làm giảm số lượng các cụm Ngram trong mô hình ngôn
ngữ bằng cách loại bỏ các cụm Ngram không quan trọng
Quantization (lượng tử hóa): thay đổi cấu trúc thông tin của mỗi cụm
Ngram trong mô hình ngôn ngữ.
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 Ngram trong mô hình ngôn ngữ
2.5.1 Loại bỏ (pruning):
Số lượng các cụm Ngram 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 Ngram. Các cụm Ngram đó thường là 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, ... [10] Những cụm
Ngram 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 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 Ngram như vậy. Có 2 phương pháp chính:
Cut-off (cắt bỏ): phương pháp này tập trung vào việc loại bỏ các cụm
Ngram có tần số thấp trong tập huấn luyện
Weighted difference: phương pháp này tập trung vào việc đánh 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.1.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
13
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 Ngram 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 Ngram xuất hiện ít hơn k lần
trong tập văn bản huấn luyện thì cụm Ngram đó 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 Ngram 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 đã trihf 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 Ngram 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 Ngram, hiệu
suất của ứng dụng cũng bị giảm. Nhưng ngược lại, nếu k 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 số lượng các cụm
Ngram.
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
Ngram phải bảo đảm rằng số cụm Ngram xuất hiện không quá k lần chiếm h% so với
tổng số các cụm Ngram. Ví dụ: nếu h=50, thì chọn k sao cho số lượng các cụm Ngram
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 Ngram đã 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
14
2.5.1.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 Ngram 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
Ngram, xác suất của từng cụm Ngram, ... [10] Như đã trình bày ở các phần trên, nếu
một cụm Ngram 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 Ngram 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 Ngram xấp xỉ với xác suất có được
theo công thức truy hồi, thì chúng ta chẳng cần lưu trữ cụm Ngram đó 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 Ngram đượ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 Ngram. Nếu
w.d.factor nhỏ hơn một ngưỡng nhất định, thì cụm Ngram đó 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 Ngram 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.2 Đồ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 Ngram vào một
bảng. Sau đó, thay thế tần số của các cụm Ngram 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 = log2(tần số lớn nhất) bit để lưu trữ
tần số của một cụm Ngram, thì chúng ta chỉ cần sử dụng b’ = log2(kích thước của
bảng) bit cho mỗi cụm Ngram. 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 Ngram 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.
15
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.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) [10] 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, tuy vẫn được sử dụng bởi Microsoft (trong modul kiểm lỗi chính
tả của Microsoft Office 2007)
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 để đánh
giá chúng. Dưới đây là một số phương pháp phổ biến để đánh giá một mô hình ngôn
ngữ:
Entropy - Độ đo thông tin
Perplexity - Độ hỗn loạn thông tin
Error rate - Tỉ lệ lỗi
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 Ngram[1][10]. 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:
16
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)
W L
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 [9]. 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
m
= - lim
p(w1, w2, ..., wm)log2p(w1, w2, ..., wm)
W L
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):
1
m
H(L) = - lim
log [ p(wn|w1w2..wn-1) * p(wn+1|w2w3.. wn) * ... * p(wm
m
|wm-n+1...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
17
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.
2.6.2 Perplexity – Độ hỗn loạn thông tin:
Độ 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)
Ví duL dãy kí tự a, b, …, z có perplexity là 26 còn bảng mã ASCII có perplexity là
256.
2.6.3 Error rate – Tỉ lệ lỗi:
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ữ [10].
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.
18
Chương 3 Ứng dụng của mô hình ngôn ngữ trong mô hình
dịch máy thống kê:
3.1 Dịch máy:
Dịch tự động hay còn gọi là dịch máy là một trong những ứng dụng quan trọng
của xử lý ngôn ngữ tự nhiên, là sự kết hợp của ngôn ngữ, dịch thuật và khoa học máy
tính[2]. Như tên gọi, dịch tự động thực hiện dịch một ngôn ngữ này (gọi là ngôn ngữ
nguồn) sang một hoặc nhiều ngôn ngữ khác (gọi là ngôn ngữ đích) một cách tự động
dựa vào máy tính mà không có sự can thiệp của con người.
Dịch máy có hai hướng tiếp cận chính như sau:
Hướng luật (Rules-based): dịch dựa vào các luật viết tay. Các luật này dựa
trên từ vựng hoặc cú pháp của ngôn ngữ. Ưu điểm của phương pháp này là
có thể giải quyết được một số trường hợp dịch , nhưng thường mất rất
nhiều công sức khi xây dựng và tính khả chuyển không cao.
Thống kê (Statistical): tạo ra bản dịch sử dụng phương pháp thống kê dựa
trên bản dịch song ngữ.
3.2 Dịch máy thống kê:
3.2.1 Giới thiệu:
Dịch máy thống kê là một hướng tiếp cận của dịch máy đặc trưng bởi việc sử
dụng các phương pháp học máy. Thay vì xây dựng các từ điển, các quy luật chuyển
đổi bằng tay, hệ dịch này tự động xây dựng các từ điển, các quy luật dựa trên kết quả
thống kê có được từ các kho ngữ liệu. Chính vì vậy, dịch máy thống kê có tính khả
chuyển cao áp dụng được cho bất kỳ cặp ngôn ngữ nào.
Ý tưởng đầu tiên về dịch máy thống kê được giới thiệu bởi Warren Weaver vào
năm 1949. Tuy nhiên, khi dịch máy thống kê mới được giới thiệu lại bởi các nhà
nghiên cứu thuộc trung tâm nghiên cứu IBM Thomas J. Watson vào năm 1991, nó mới
bắt đầu được chú y và thu hút được rất nhiều nhà nghiên cứu. Cho tới hôm nay, dịch
máy thống kê đang là phương pháp dịch thuật được nghiên cứu rộng rãi nhất.
3.2.2 Nguyên lý và các thành phần:
Cho trước câu ngôn ngữ nguồn f, mục tiêu của mô hình dịch máy là tìm ra câu e
của ngôn ngữ đích sao cho xác suất P(e|f) là cao nhất.
19
Có nhiều cách tiếp cận để tính được xác suất P(e|f), tuy nhiên cách tiếp cận trực
quan nhất là áp dụng công thức Bayes:
P(e)P(f|e)
P(e|f) =
P(f)
Trong đó P(f|e) là xác suất câu ngôn ngữ nguồn là bản dịch của câu ngôn ngữ
đích, còn P(e) là xác suất xuất hiện câu e trông ngôn ngữ. Việc tìm kiếm câu e* phù
hợp chính là việc tìm kiếm e* làm cho giá tri P(e*)P(f|e*) là lớn nhất.
Để mô hình dịch là chính xác, thì công việc tiếp theo là phải tìm ra tất cả các câu
e* có thể có trong ngôn ngữ đích từ câu ngôn ngữ nguồn f. Thực hiện công việc tìm
kiếm hiệu quả chính là nhiệm vụ của bộ giải mã (decoder). Như vậy, một mô hình dịch
máy bao gồm 3 thành phần:
Mô hình ngôn ngữ: Tính toán được xác suất của câu ngôn ngữ nguồn.
Thành phần này chính là mô hình ngôn ngữ đã được mô tả ở phần 2 của
luận văn
Mô hình dịch: Cho biết xác suất của câu ngôn ngữ nguồn là bản dịch từ
câu ngôn ngữ đích .
Bộ giải mã: Tìm kiếm tất cả các câu ngôn ngữ đích e có thể có từ câu
ngôn ngữ nguồn f.
Mô hình dịch từ tiếng Anh sang tiếng Việt có thể hình dung thông qua biểu đồ
dưới đây:
Hình 3-1: mô hình dịch máy thống kê từ tiếng Anh sang tiếng Việt
Mô hình dịch của mô hình ngôn ngữ đã được trình bày ở chương 2 của luận văn.
Ở hai phần 3.2.3 và 3.2.4, luận văn chỉ đề cập đến hai thành phần còn lại của mô hình
dịch máy thống kê.
20
3.2.3 Mô hình dịch:
Mô hình dịch có 3 hướng tiếp cận chính:
Mô hình dịch dựa trên từ (word-based)
Mô hình dịch dựa trên cụm từ (phrase-based)
Mô hình dịch dựa trên cú pháp (syntax-based)
Cả 3 hướng tiếp cận trên đều dựa trên một tư tưởng. Đó là sự tương ứng giữa hai
câu (alignment)
3.2.3.1 Sự gióng hàng (alignment):
Tất cả các mô hình dịch thống kê đều dựa trên sự tương ứng của từ. Sự tương
ứng của từ ở đây chính là một ánh xạ giữa một hay nhiều từ của ngôn ngữ nguồn với
một hay nhiều từ của ngôn ngữ đích trong tập hợp các câu văn bản song ngữ.[2]
Theo nguyên tắc, chúng ta có thể có mối liên hệ tùy ý giữa các từ của ngôn ngữ
nguồn với các từ của ngôn ngữ đích. Tuy nhiên, để cho đơn giản, mô hình dịch máy
dựa trên từ (word-based) đưa ra một giả định: mỗi từ của ngôn ngữ đích chỉ tương ứng
với một từ của ngôn ngữ nguồn. Nếu áp dụng giả định này, chúng ta có thể biểu diễn
một sự tương ứng từ bằng chỉ số của các từ trong ngôn ngữ nguồn tương ứng với từ
trong ngôn ngữ đích. Như trong ví dụ ở hình 3.1[2] dưới đây có thể biểu diễn một
tương ứng từ giữa tiếng Pháp và tiếng Anh bởi một dãy các chỉ số như sau: A = 2, 3, 4,
5, 6, 6, 6.
Hình 3-2: sự tương ứng một - một giữa câu tiếng Anh và câu tiếng Pháp
Trong thực tế, có rất nhiều từ ở ngôn ngữ đích không tương ứng với từ nào trong
ngôn ngữ nguồn. Để cho tổng quát, ta thêm một từ vô giá trị (null) vào đầu câu ngôn
ngữ nguồn và những từ ở ngôn ngữ đích không tương ứng với từ nào sẽ được ánh xạ
21
với từ vô giá trị đó. Hình 3.2[2] ở dưới thể hiện một tương ứng từ giữa hai câu tiếng
Anh và tiếng Tây Ban Nha khi cho thêm từ vô giá trị vào đầu câu tiếng Anh.
Hình 3-3: sự tương ứng giữa câu tiếng Anh với câu tiếng Tây Ban Nha khi cho thêm từ
vô giá trị (null) vào đầu câu tiếng Anh
Trong khi mô hình dịch dựa trên từ (word-based) chỉ giải quyết trường hợp một
từ của ngôn ngữ đích chỉ tương ứng bởi một từ của ngôn ngữ nguồn, thì mô hình dịch
dựa trên cụm từ (pharse-based) có thể giải quyết cả hai trường hợp còn lại là: một từ
của ngôn ngữ này tương ứng với nhiều từ của ngôn ngữ kia và nhiều từ của ngôn ngữ
này tương ứng với nhiều từ của ngôn ngữ kia. Hình 3.3 và 3.4[2] ở dưới minh họa các
tương ứng nói trên.
Hình 3-4: sự tương ứng một - nhiều giữa câu tiếng Anh với câu tiếng Pháp
Hình 3-5: sự tương ứng nhiều - nhiều giữa câu tiếng Anh với câu tiếng Pháp.
3.2.3.2 Mô hình dịch dựa trên từ (Word-based):
Mô hình dịch dựa trên từ là thế hệ đầu tiên của mô hình dịch máy thống kê và
được nghiên cứu và phát triển bởi IBM[2]. Như đã trình bày ở phần 3.2.3.1, mô hình
dịch này dựa trên sự tương ứng của các từ theo tương ứng một một (một từ của ngôn
ngữ này chỉ tương ứng với một từ của ngôn ngữ kia và ngược lại). Cụ thể hơn, giả sử
22
câu ngôn ngữ nguồn là e1e2...en và câu ngôn ngữ đích là f1f2...fm, khi đó mỗi từ fj chỉ
tương ứng với 1 và chỉ 1 từ trong câu ngôn ngữ nguồn hoặc là không tương ứng với từ
nào. Do đó, một sự tương ứng giữa các từ của câu ngôn ngữ nguồn và câu ngôn ngữ
đích có thể biểu diễn bằng một dãy m số: {a1, a2, ... am} trong đó aj là chỉ số của từ
trong ngôn ngữ nguồn tương ứng với từ fj của ngôn ngữ đích(aj nhận các giá trị từ 1
đến l). Với mô hình IBM thứ nhất, giả định rằng mỗi biến aj là độc lập, khi đó tương
ứng tối ưu nhất chính là:
i = m
a = argmax p(ai)*p(fi|eai)
a1m
i = 1
Như vậy, theo mô hình IBM thứ nhất, chúng ta có thể tính xác suất P(f|e) theo
công thức sau:
i = m ai = n
P(f|e) = p(ai)*p(fi|eai)
i = 1 a = 0
i
Tuy nhiên trên thực tế, mô hình IBM thứ nhất này có chất lượng dịch không cao.
Ở các mô hình IBM tiếp theo, người ta cải tiến các công thức và đưa ra những tương
ứng, cũng như tính lại xác suất P(f|e) một cách tốt hơn. Tuy nhiên, do tiếp cận theo
hướng tương ứng một một giữa các từ, nên mô hình dịch dựa trên từ nói chung và các
mô hình dịch IBM nói riêng đã không còn phổ biến. Hiện nay, các mô hình dịch theo
hướng cụm từ được sử dụng rộng rãi và dần trở nên phổ biến hơn.
3.2.3.3 Mô hình dịch dựa trên cụm từ (Phrase-based):
Trong thực tế, người ta thường dựa vào cụm từ để dịch nhiều hơn là dựa vào từ.
Ví dụ như cụm “take time” được dịch là “mất thời gian” trong khi nếu dịch theo từ, thì
kết quả sẽ là “giữ” và “thời gian”. Rõ ràng có thể thấy, dịch dựa vào cụm từ sẽ cho kết
quả tốt hơn so với dịch dựa vào từ.
Có nhiều mô hình dịch dựa trên cụm từ nhưng luận văn này chỉ đề cập đến mô
hình của Koehn[2]. Với mô hình dịch này, một câu ngôn ngữ nguồn e được tách thành
e1
e
e
các cụm từ
fi
,
, ..., ; sau đó các cụm này được dịch ra thành các cụm thuộc ngôn
2
n
fi
ngữ đích . Cuối cùng các cụm
này được sắp xếp lại theo một thứ tự nhất định.
23
Tải về để xem bản đầy đủ
51 trang
07/07/2025
1040
Bạn đang xem 30 trang mẫu của tài liệu "Khóa luận Xây dựng mô hình ngôn ngữ cho tiếng Việt", để 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:
- khoa_luan_xay_dung_mo_hinh_ngon_ngu_cho_tieng_viet.pdf
