ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Vương Hoài Thu
PHÂN TÍCH CÚ PHÁP TIẾNG VIỆT THEO TIẾP
CẬN THỐNG KÊ
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
HÀ NỘI - 2009
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Vương Hoài Thu
PHÂN TÍCH CÚ PHÁP TIẾNG VIỆT THEO TIẾP
CẬN THỐNG KÊ
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hướng dẫn: TS. Lê Anh Cường
HÀ NỘI – 2009
LỜI CẢM ƠN
Đầu tiên tôi xin tỏ lòng biết ơn sâu sắc đến thầy giáo hướng dẫn của tôi,TS Lê
Anh Cường, người đã hướng dẫn, chỉ bảo và tạo điều kiện để tôi hoàn thành luận văn
này.
Tôi xin gửi lời cảm ơn sâu sắc tới thầy giáo TS Nguyễn Phương Thái và nhóm
xây dựng ngữ liệu Viet Treebank, đặc biệt là thầy Ngyễn Phương Thái, người đã
hướng dẫn và cung cấp tài liệu, dữ liệu cần thiết cho tôi trong quá trình hoàn thành
luận văn.
Tôi xin chân thành cảm ơn các thầy cô giáo trong trường Đại học Công nghệ, đặc
biệt là những thầy cô trong bộ môn Khoa học máy tính, những người đã dạy bảo, tạo
điều kiện cho tôi trong suốt quá trình học tập tại trường.
Cuối cùng, gia đình và bạn bè là hậu phương vững chắc, là nguồn động viên giúp
tôi hoàn thành luận văn này.
TÓM TẮT
Phân tích cú pháp là một trong những bài toán cơ bản và quan trọng nhất trong
xử lý ngôn ngữ tự nhiên (XLNNTN). Kết quả của phân tích cú pháp được sử dụng
trong rất nhiều ứng dụng XLNNTN khác như dịch máy, hỏi đáp, trích chọn thông
tin… Xây dựng một bộ phân tích cú pháp cho tiếng Việt có độ chính xác cao là một
công việc rất có ý nghĩa. Mục tiêu đề ra của luận văn là xây dựng bộ phân tích cú pháp
tiếng Việt theo tiếp cận thống kê. Đây là một hướng tiếp cận khá mới mẻ trong cách
xây dựng bộ phân tích cú pháp tiếng Việt. Luận văn sẽ trình bày khái quát về các cách
tiếp cận trong việc xây dựng bộ phân tích cú pháp, và đi sâu tìm hiều về văn phạm phi
ngữ cảnh xác suất từ vựng (Lexicalized Probabilistic Context Free Grammar). Cụ thể
hơn, tôi tìm hiểu, nghiên cứu 3 mô hình xác suất của Collins [11], và áp dụng công cụ
phân tích của Bikel’s [9] để thử nghiệm cho phân tích cú pháp tiếng Việt. Phân tích cú
pháp dựa theo thống kê cần có dữ liệu để huấn luyện mô hình. Trong luận văn, tôi sẽ
sử dụng ngữ liệu Viet Treebank. Kết quả thực nghiệm cho thấy độ chính xác
(precision) là trên 80% với hơn 9000 câu huấn luyện và 500 câu kiểm tra. Những kết
quả của luận văn cho thấy rằng, đối với tiếng Việt, mô hình 1 của Collin có độ chính
xác thấp hơn so với mô hình 2, và mô hình 3 chưa thực sự hiệu quả. Ngoài ra, kết quả
thực nghiệm còn chỉ ra một số tham số của mô hình 2 của Collins có ảnh hưởng tới độ
chính xác của bộ phân tích cú pháp.
MỤC LỤC
MỞ ĐẦU ............................................................................................................1
Chương 1. Giới thiệu...........................................................................................2
1.1. Xử lý ngôn ngữ tự nhiên và các vấn đề chính............................................2
1.2. Phân tích cú pháp và ứng dụng trong xử lý ngôn ngữ tự nhiên..................3
1.2.1. Định nghĩa: ........................................................................................3
1.2.2. Vai trò của phân tích cú pháp trong xử lý ngôn ngữ tự nhiên .............3
1.3. Phân tích cú pháp dành cho tiếng Việt ......................................................4
1.3.1. Nhập nhằng – vấn đề chính của xử lý ngôn ngữ tự nhiên: ..................4
1.3.2. Phân tích cú pháp trong tiếng Việt .....................................................5
1.4. Mục tiêu ...................................................................................................6
Chương 2. Phương pháp phân tích cú pháp..........................................................7
2.1. Văn phạm phi ngữ cảnh ............................................................................7
2.2. Các phương pháp cổ điển..........................................................................8
2.2.1. Phân tích top – down..........................................................................8
2.2.2. Phân tích bottom – up: .....................................................................10
2.2.3. So sánh giữa top – down và bottom – up..........................................13
2.2.4. Thuật toán CYK (Cocke – Younger – Kasami) ................................13
2.2.5. Thuật toán Earley.............................................................................15
2.3. Văn phạm phi ngữ cảnh xác suất (PCFGs)..............................................19
2.3.1. Định nghĩa .......................................................................................19
2.3.2. Nhược điểm của văn phạm phi ngữ cảnh xác suất............................20
2.4. Văn phạm phi ngữ cảnh xác suất từ vựng (LPCFGs) ..............................22
2.4.1. Cấu trúc head...................................................................................22
2.4.2. Mô hình một: Mô hình cơ sở............................................................23
2.4.3. Mô hình 2: Phân biệt định ngữ và bổ ngữ, subcategorization ...........25
2.4.4. Mô hình 3: Trace và Wh-movement.................................................27