Đồ Án Ứng dụng mô hình Markov ẩn để giải quyết vấn đề nhập nhằng trong văn phạm liên kết

TÓM TẮT NỘI DUNG ĐỒ ÁN TỐT NGHIỆP
Trong xử lý ngôn ngữ tự nhiên, phân tích cú pháp là vấn đề hết sức quan trọng. Nó là quá
trình phân tích một dãy các từ để xác định cấu trúc cú pháp của chúng dựa trên một văn
phạm cho trước. Với mô hình văn phạm phi ngữ cảnh, sau khi thực hiện bước phân tích cú
pháp thì đối với văn phạm có nhập nhằng thì sẽ sinh ra nhiều cây phân tích khác nhau đối
với một câu đầu vào. Vậy ta sẽ lựa chọn cây phần tích cú pháp nào làm kết quả của quá trình
phân tích này. Hướng giải quyết của đồ án là dựa vào mô hình văn phạm phi ngữ cảnh xác
suất sử dụng Văn phạm liên kết để đưa ra một xác suất ứng với mỗi cây phân tích cú pháp
thu được.Từ đó ta có thể lựa chọn cây phân tích cú pháp phù hợp.
Chương đầu của đồ án giới thiệu về cách tiếp cận thống kê cho bài toán phân tích cú pháp
bao gồm các khái niệm về văn phạm phi ngữ cảnh, văn phạm phi ngữ cảnh xác suất, bài toán
phân tích cú pháp.
Chương hai đồ án đề cập tới việc phân tích cú pháp theo mô hình văn phạm liên kết. Phần
này sẽ giới thiệu về văn phạm liên kết Link Grammar, định nghĩa dạng tuyển, xây dựng biểu
thức kết nối.
Chương ba của đồ án trình bày về mô hình Markov ẩn và các giải thuật .
Chương cuối đồ án ứng dụng giải thuật tính xác suất trong và giải thuật Viterbi giải quyết
vấn đề khử nhập nhằng bài toán phân tích cú pháp văn phạm liên kết.





MỤC LỤC
PHIẾU GIAO NHIỆM VỤ ĐỒ ÁN TỐT NGHIỆP . . 1
TÓM TẮT NỘI DUNG ĐỒ ÁN TỐT NGHIỆP . . 2
LỜI CẢM ƠN . 3
MỤC LỤC . 4
DANH MỤC HÌNH VẼ . . 6
DANH MỤC BẢNG . . 7
DANH MỤC TỪ VIẾT TẮT . 8
CHƯƠNG 1: MÔ HÌNH VĂN PHẠM PHI NGỮ CẢNH XÁC SUẤT VÀ BÀI
TOÁN PHÂN TÍCH CÚ PHÁP . . 9
1.1. Văn phạm . 10
1.2.Văn phạm phi ngữ cảnh. . 11
1.2.1 Dẫn xuất và ngôn ngữ . 11
1.2.2 Cây dẫn xuất . . 12
1.2.3. Văn phạm nhập nhằng . . 14
1.4.Văn phạm phi ngữ cảnh xác suất (PCFG) . 16
1.4.1 Định nghĩa . . 16
1.4.2 Một ví dụ về văn phạm phi ngữ cảnh xác suất . . 17
1.5. Bài toán phân tích cú pháp trong văn phạm phi ngữ cảnh . . 19
CHƯƠNG 2: MÔ HÌNH VĂN PHẠM LIÊN KẾT . 20
2.1 Giới thiệu văn phạm liên kết . . 20
2.2. Định nghĩa và ký hiệu . . 23
2.2.1. Các văn phạm liên kết đơn giản . 23
2.2.2. Dạng tuyển . 24
2.3. Văn phạm liên kết cho tiếng Việt . 26
2.3.1. Danh từ và cụm danh từ . . 26
2.3.2. Động từ và cụm động từ . . 31
2.3.3. Tính từ và cụm tính từ . . 34
2.3.4. Các liên kết giữa cụm danh từ, cụm động từ và cụm tính từ . 35
2.3.5. Các cấu trúc câu khác . . 39

2.3.6. Liên từ kết hợp . 43
CHƯƠNG 3: MÔ HÌNH MARKOV ẨN TRONG VĂN PHẠM LIÊN KẾT 46
3.1. Mô hình Markov ẩn . 46
3.1.1. Giải thuật tiến . . 48
3.1.2. Giải thuật lùi . . 49
3.1.3. Giải thuật Viterbi . 50
3.2. Thuật toán trong - ngoài . . 51
3.2.1. Cơ sở lý thuyết . 51
3.2.2. Thuật toán trong-ngoài trong văn phạm phi ngữ cảnh xác suất . . 54
CHƯƠNG 4: ỨNG DỤNG TRONG PHÂN TÍCH CÚ PHÁP VĂN PHẠM
LIÊN KẾT . . 58
4.1. Bài toán phân tích cú pháp . . 58
4.2. Bài toán khử nhập nhằng trong phân tích cú pháp văn phạm phi ngữ cảnh . . 58
4.2.1 Giải thuật tính xác suất trong giải quyết bài toán đoán nhận. 59
4.2.2. Giải thuật Viterbi tìm phân tích tốt nhất cho câu . . 61
4.3. Bài toán khử nhập nhằng trong phân tích cú pháp văn phạm liên kết . . 62
4.3.1. Bài toán đoán nhận văn phạm liên kết . 63
4.3.2. Tìm cây tốt nhất cho câu văn phạm liên kết . . 65
4.4. Sự phụ thuộc vào tree bank . 66
KẾT LUẬN . . 67
TÀI LIỆU THAM KHẢO . . 68