Khóa luận Phân tích cú pháp tiếng việt theo tiếp cận thống kê

ĐẠ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 Chương 3. Tiếp cận trong xây dựng bộ phân tích cú pháp Tiếng Việt................28 3.1. Penn Treebank........................................................................................28 3.1.1. Gán nhãn từ loại...............................................................................28 3.1.2. Bracketing .......................................................................................30 3.2. Viet Treebank.........................................................................................32 3.2.1. Mục tiêu...........................................................................................32 3.2.2. Danh sách từ loại và các nhãn cú pháp .............................................32 3.2.3. Một số đặc điểm của Viet Treebank .................................................34 Chương 4. Bộ phân tích cú pháp của Bikel ........................................................35 4.1. Một số nhiệm vụ cơ bản..........................................................................35 4.1.1. Tiền xử lý ........................................................................................35 4.1.2. Huấn luyện ......................................................................................40 4.1.3. Các loại tham số và các đánh giá......................................................42 4.1.4. Decode.............................................................................................48 4.2. Tổng quan về bộ phân tích cú pháp.........................................................49 4.2.1. Mở đầu ............................................................................................49 4.2.2. Vấn đề cơ bản ..................................................................................50 4.2.3. Tổng quan về hệ thống.....................................................................50 4.2.4. Khả năng..........................................................................................54 4.3. Kết luận..................................................................................................55 Chương 5. Áp dụng bộ phân tích cú pháp của Bikel và dữ liệu Viet Treebank...56 5.1. Gói ngôn ngữ tiếng Việt .........................................................................56 5.2. Quá trình thực hiện: ................................................................................57 5.2.1. Xử lý dữ liệu....................................................................................57 5.2.2. Cấu hình để thực hiện: .....................................................................58 5.2.3. Huấn luyện ......................................................................................61 5.2.4. Phân tích cú pháp.............................................................................62 5.2.5. Đánh giá kết quả: .............................................................................62 5.3. Kết quả đạt được:....................................................................................63 KẾT LUẬN.......................................................................................................67 TÀI LIỆU THAM KHẢO .................................................................................68 DANH SÁCH CÁC BẢNG Bảng 1: Bảng phân tích bằng thuật toán CYK ..................................................15 Bảng 2: Bảng nhãn từ loại trong Penn Treebank................................................29 Bảng 3: Bảng nhãn cú pháp trong Penn Treebank..............................................31 Bảng 4: Nhãn từ loại trong Viet Treebank .........................................................32 Bảng 5: Bảng nhãn cụm từ trong Penn Treebank...............................................33 Bảng 6: Bảng nhãn mệnh đề trong Viet Treebank..............................................34 Bảng 7: Các mức back-off với ...........................................................47 Bảng 8: Tham số do Bikel đề xuất ....................................................................47 Bảng 9: Cấu trúc back-off đối với các tham số .................................................48 Bảng 10: Sô lượng câu để huấn luyện................................................................58 Bảng 11: Bảng so sánh kết quả đối với xâu dài không quá 40 từ.......................63 Bảng 12: Bảng so sánh kết quả đối với xâu dài không quá 100 từ.....................64 DANH SÁCH CÁC HÌNH VẼ Hình 1: Mô hình xử lý ngôn ngữ tự nhiên...........................................................1 Hình 2: Cây cú pháp của câu "tôi nhìn cô gái với chiếc ống nhòm" .....................5 Hình 3: Dẫn xuất phân tích top - down ..............................................................10 Hình 4: Dẫn xuất phân tích bottom - up.............................................................13 Hình 5: Mã giả của thuật toán Earley.................................................................17 Hình 6: Miêu tả dẫn xuất xâu từ Ni .....................................................................1 Hình 7: Cây cú pháp của câu "bò ăn cỏ " ...........................................................20 Hình 8: Cây dẫn xuất thứ nhất của xâu "Trung hiểu Nam hơn Thắng"...............21 Hình 9: Cây dẫn xuất thứ hai của xâu "Trung hiểu Nam hơnThắng"..................21 Hình 10: Cây cú pháp của xâu "bò ăn cỏ" có thêm thông tin từ vựng.................23 Hình 11: Miêu tả độ đo khoảng cách trong câu..................................................25 Hình 12: Cây cú pháp với hậu tố - C đánh dấu complement. "IBM" và "Lotus" là chủ ngữ và bổ ngữ, trong khi "Last week" là định ngữ. ..............................................25 Hình 13: Hai ví dụ về các thành phần bổ trợ được sinh ra một cách độc lập đã gây ra sai số. ..............................................................................................................26 Hình 14: Dữ liệu đã gán nhãn trước khi xử lý thủ công .....................................30 Hình 15: Dữ liệu đã gán nhãn sau khi xử lý thủ công ........................................30 Hình 16: Dữ liệu hoàn chỉnh..............................................................................32 Hình 17: Liên kết từ trong Penn Treebank.........................................................36 Hình 18: Liên kết từ trong Viet Treebank ..........................................................36 Hình 19: Nút NBP cần thêm nút NP ..................................................................37 Hình 20: Nhãn NBP được chỉnh sửa..................................................................38 Hình 21: Nâng cấc dấu câu lên, trong cây bên phải xuất hiện các dấu phẩy nằm cạnh nhau ..................................................................................................................39 Hình 22: Nút có nhãn HEAD cũng không là ngoại lệ khi thay đổi nhãn chức năng ..................................................................................................................................40 Hình 23: Một ví dụ về hàm vi (“verb intervening”) nhận giá trị true, do nhãn NP có chứ động từ ...........................................................................................................41 Hình 24: Các thành phần và luồng làm việc......................................................51 1 MỞ ĐẦU Phân tích cú pháp là một bài toán trung tâm trong XLNNTN. Phân tích cú pháp được sử dụng trong rất nhiều ứng dụng của XLNNTN. Độ chính xác của bộ phân tích cú pháp có ảnh hưởng lớn tới kết quả của các ứng dụng xử lý ngôn ngữ khác. Các nghiên cứu về xây dựng phân tích cú pháp tự động đã được phát triển từ rất sớm và đã có nhiều bộ phân tích cú pháp với chất lượng rất tốt cho các ngôn ngữ như tiếng Anh, tiếng Trung [9]. Ngày nay, nhiều ứng dụng trong XLNNTN đang được nghiên cứu và phát triển cho tiếng Việt và nhu cầu về một bộ phân tích cú pháp tiếng Việt với độ chính xác cao là rất cấp thiết. Tuy nhiên, các nghiên cứu về phân tích cú pháp tiếng Việt vẫn còn hạn chế và tập trung chủ yếu vào tiếp cận cũ (Knowledge-based), với kết quả còn hạn chế và chưa có bộ phân tích nào được công bố rộng rãi. Vì vậy, khóa luận này hướng tới việc xây dựng bộ phân tích cú pháp tiếng Việt theo tiếp cận thống kê. Chúng tôi theo tiếp cận này sử dụng văn phạm phi ngữ cảnh xác suất từ vựng (Lexicalized Probabilistic Context Free Grammar). Luận văn sẽ nghiên cứu các cách tiếp cận cơ bản trong phân tích cú pháp, đi sâu tìm hiểu văn phạm phi ngữ cảnh xác suất từ vựng theo 3 mô hình của Collins [11]. Từ đó, dựa vào hiểu biết về ngữ liệu Viet Treebank để huấn luyện và đánh giá độ chính xác của mô hình dựa trên việc tích hợp tiếng Việt vào bộ phân tích cú pháp của Bikel [9]. Kiến trúc cúa hệ phân tích cú pháp của Bikel cũng được nghiên cứ và phân tích để có thể sửa đổi đối tượng tương thích cho tiếng Việt cũng như khảo sát ảnh hưởng của các tham số khác nhau đối với phân tích cú pháp tiếng Việt. 2 Chương 1. Giới thiệu Đã từ lâu, con người luôn ước mơ phát minh ra một chiếc máy có khả năng nghe và thực hiện các mệnh lệnh của con người. Cho đến nay, một hệ thống như vậy vẫn còn trong ước mơ bởi máy móc vẫn gặp khó khăn trong việc nhận biết ngôn ngữ của con người, từ việc nghe đúng cho đến việc hiểu đúng được lời nói của con người rất là khó khăn. Tuy nhiên, con người đang tích cực nghiên cứu phát triển ra công nghệ mới để thực hiện được một hệ thống thông minh như con người, lĩnh vực đó là xử lý ngôn ngữ tự nhiên. 1.1. Xử lý ngôn ngữ tự nhiên và các vấn đề chính Xử lý ngôn ngữ tự nhiên là lĩnh vực trong khoa học máy tính, nhiệm vụ của nó là xây dựng một hệ thống có thể phân tích, hiểu được ngôn ngữ của con người, không những thế hệ thống này còn có khả năng phản hồi lại bằng chính ngôn ngữ của con người. Như vậy ta có một mô hình đơn giản về một hệ thống xử lý ngôn ngữ tự nhiên như sau: Xử lý ngôn ngữ tự nhiên có rất nhiều ứng dụng trong thực tế, có thể kể ra ở đây một vài ứng dụng của xử lý ngôn ngữ tự nhiên như là dịch máy (machine translation), tìm kiếm thông tin (information retrieval), trích chọn thông tin (information retrieval) hay như là nhận dạng tiếng nói (speech recognition). - Dịch máy (machine translation) là một ứng dụng có nhiệm vụ dịch một văn bản từ một ngôn ngữ (ví dụ như tiếng Anh) sang một ngôn ngữ khác (chẳng hạn là tiếng Việt), giống như người phiên dịch. Hệ thống ngôn ngôn hiểu ngôn sinh ra ngôn Hình 1: Mô hình xử lý ngôn ngữ tự nhiên 3 - Tìm kiếm thông tin (information retrieval): ở đây ta có thể thấy một ví dụ rất điển hình đó là web search engine, www.google.com, website này là một dạng của tìm kiếm thông tin, tức là khi cần một thông tin, hệ thống sẽ thực hiện việc tìm kiếm trong dữ liệu (tập rất nhiều các văn bản) một hay nhiều văn bản tương tự với thông tin ta cần tìm kiếm. - Trích chọn thông tin (information extraction): khi đưa vào một tập văn bản, hệ thống này có thể trả về cho ta những đoạn trong văn bản đó miêu tả thông tin chúng ta quan tâm. Một ví dụ đơn giản ở đây là khi gặp một trang blog ta cần xác định một số thông tin về cá nhân sở hữu blog như tên, giới tính, địa chỉ, v.v… thì hệ thống trích chọn thông tin có nhiệm vụ trả về cho ta các thông tin này. - Nhận dạng tiếng nói (speech recognition): Khi bạn nói một câu, chúng ta đã có những hệ thống có thể ghi lại những âm thanh này ở dạng dữ liệu số, mục tiêu của ứng dụng này là chuyển được sóng âm thanh này thành dữ liệu văn bản. Trên đây là một số ứng dụng của xử lý ngôn ngữ tự nhiên và trong thực tế còn nhiều ứng dụng khác đang được nghiên cứu và phát triển. Tuy nhiên, các ứng dụng ngôn ngữ tự nhiên đều có chung một số bài toán cơ sở như là phân tích từ tố, phân tích cú pháp, phân tích ngữ nghĩa. Trong đó, phân tích cú pháp đóng vai trò trung tâm trong ứng dụng XLNNTN và là mục tiêu của luân văn này. 1.2. Phân tích cú pháp và ứng dụng trong xử lý ngôn ngữ tự nhiên 1.2.1. Định nghĩa: Phân tích cú pháp (parsing hay syntatic analys) là quá trình phân tích một chuỗi từ tố (chuỗi từ tố này là kết quả của quá trình phần tích từ tố, thông thường đối với xử lý ngôn ngữ là các từ), nhằm đưa ra cấu trúc ngữ pháp của chuỗi từ đó dựa vào một văn phạm nào đó. Thông thường cấu trúc ngữ pháp được chọn ở đây thường là ở dạng cây, bởi thông qua dạng này sự phụ thuộc của các thành phần là trực quan. 1.2.2. Vai trò của phân tích cú pháp trong xử lý ngôn ngữ tự nhiên Có thể nói phân tích cú pháp là bài toán cơ sở, xuất hiện rất nhiều trong các ứng dụng của xử lý ngôn ngữ tự nhiên. Ví dụ đầu tiên ta có thể thấy ngay đó là áp dụng phân tích cú pháp trong kiểm tra lỗi ngữ pháp. Đối với việc kiểm tra lỗi ngữ pháp ta cần thực hiện việc phân tích cú pháp câu đầu vào, xem cấu trúc có đúng không? Trong dịch máy, hiện nay, có ba chiến lược dịch cơ bản là dịch trực tiếp, dịch chuyển đổi và dịch liên ngữ. Đối với dịch trực tiếp, cách dịch này dựa vào bộ từ điền 4 song ngữ để dịch, không sử dụng đến phân tích cú pháp. Tuy nhiên trong dịch chuyển đổi và dịch liên ngữ, quá trình phân tích cú pháp là một bước quan trọng. Tư tưởng chung ở đây là đều phân tích câu nguồn trở thành cây cú pháp sử dụng bộ phân tích cú pháp. Đối với dịch chuyển đổi, hệ thống sẽ xây dựng cây cú pháp tương đương trong ngôn ngữ đích và cuối cùng đưa cây cú pháp thành câu cần đưa ra. Đối với dịch liên ngữ, cây cú pháp ở ngôn ngữ nguồn được đưa thành một biểu diễn chung giữa hai ngôn ngữ sau đó dạng biểu diễn chung này được chuyển về cây cú pháp ở ngôn ngữ đích, cuối cùng trả về câu cần dịch. Trong lĩnh vực như nhận dạng tiếng nói (speech recoginition) sử dụng phân tích cú pháp có thể giúp sửa sai quá trình nhận dạng. Trong tổng hợp tiếng nói, phân tích cú pháp giúp đặt trọng âm vào đúng vị trí trong câu. Những ví dụ ở trên đây đã khẳng định được vai trò của phân tích cú pháp trong xử lý ngôn ngữ tự nhiên. Vì vậy, ứng dụng xử lý ngôn ngữ tự nhiên cho tiếng Việt cần phải giải quyết được bài toán cơ sở và trọng tâm là phân tích cú pháp cho tiếng Việt. 1.3. Phân tích cú pháp dành cho tiếng Việt 1.3.1. Nhập nhằng – vấn đề chính của xử lý ngôn ngữ tự nhiên: Trước tiên, ta lấy một câu làm ví dụ: “Con ngựa đá con ngựa đá”. Trong câu này, từ “đá” xuất hiện hai lần, từ đá thứ nhất là động từ chỉ hành động sử dụng chân tác động vào vật khác, từ “đá” thứ hai lại là tính từ thể hiện chất liệu của con ngựa thứ hai. Có một số nhập nhằng trong xử lý ngôn ngữ tự nhiên như là - Nhập nhằng trong việc phân đoạn từ (word segmentation): ví dụ câu học sinh học sinh học, việc phân đoạn từ chính xác sẽ là học_sinh học sinh_học, nhưng có thể gặp tách như học_sinh học_sinh học, hoặc học sinh_học sinh_học. Có thể thấy việc phân đoạn từ các từ đều chính xác nhưng trong hai cách tách từ cuối đều không chấp nhận được vì các cụm từ này không có ý nghĩa. - Nhập nhằn trong gán nhãn từ loại: giống như ví dụ “con ngựa đá con ngựa đá” từ “đá” thứ hai có thể được gán nhãn là V (nhãn chỉ động từ) trong khi nó là một tính từ thể hiện chất liệu. - Nhập nhằng trong phân tích cú pháp: Đối với phân tích cú pháp ta có thể thấy hai loại như sau: + Nhập nhằng do việc xác định từ bổ nghĩa: Ví dụ: “Tôi nhìn cô gái với ống nhòm” 5 Ta sử dụng cây cú pháp để miêu tả 2 trường hợp của câu này Hình 2: Cây cú pháp của câu "tôi nhìn cô gái với chiếc ống nhòm" Cây cú pháp bên trái miêu tả trường hợp “với ống nhòm” bổ nghĩa cho từ “cô gái”, trong trường hợp này câu được hiều là “tôi” “nhìn” “cô gái với ống nhòm” (tôi nhìn thấy cố gái và cô gái ấy có một cái ống nhòm). Còn hình bên phải miêu ta trường hợp “với ống nhòm” bổ nghĩa cho động từ “nhìn”. Câu này có thể hiểu là “tôi” “nhìn” “cô gái” “với ống nhòm” (tôi dùng ống nhòm để nhìn cô gái). + Nhập nhằng thứ hai là hiện tượng liên kết từ: Nhập nhằng này xảy ra trong một câu mà một từ có thể liên kết với từ trước hay từ đằng sau nó tạo thành một câu có ý nghĩa hoàn toàn khác nhau. Ví dụ như câu sau: “Nam hiểu Trung hơn Thành”. Nếu như từ “Thành” liên kết với từ “Trung” ta có thể hiểu câu này là Nam hiểu Trung nhiều hơn là Nam hiểu Thành, nhưng ta có thể hiểu câu này theo một cách khác là Nam hiểu Trung nhiều hơn Thành hiểu Trung. 1.3.2. Phân tích cú pháp trong tiếng Việt Mặc dù phân tích cú pháp có vai trò trung tâm trong các ứng dụng XLNNTN, nhưng những nghiên cứu về phân tích cú pháp cho tiếng Việt còn rất hạn chế và chưa có bộ phân tích cú pháp nào được công bố rộng rãi. Một số bộ phân tích cú pháp đi theo hướng tiếp cận cũ (knowledge-base) thực hiện việc xây dựng luật ngữ pháp thủ công và không sử dụng thống kê trong đó. Do việc xây dựng luật ngữ pháp thủ công nên độ chính xác của bộ phân tích cú pháp này còn chưa cao, chỉ phân tích được một 6 số lượng hữu hạn câu do văn phạm sinh ra. Hướng tiếp cận sử dụng thống kê cũng đã được nghiên cứu [6], nhưng còn sơ lược và đặc biệt là chưa có kết quả thực nghiệm. 1.4. Mục tiêu Luận văn hướng tới việc xây dựng bộ phân tích cú pháp tiếng Việt theo tiếp cận thống kê với các nghiên cứu cụ thể sau: - Nghiên cứu các tiếp cận và phương pháp cơ bản trong phân tích cú pháp, tập trung vào tiếp cận sử dụng thông kê và thông tin từ vựng. - Phân tích và áp dụng bộ phân tích cú pháp của Bikel [9] để xây dựng bộ phân tích cú pháp tiếng Việt. Với mục tiêu đó luận văn sẽ trình bày các nội dung sau: Chương 2 trình bày về các phương pháp tiếp cận trong việc xây dựng bộ phân tích cú pháp từ phương pháp cổ điển như chiến lược phân tích top-down hay chiến lược phân tích bottom-up, cho đến hướng tiếp cận thống kê như sử dụng văn phạm phi ngữ cảnh xác suất, cuối cùng là sử dụng văn phạm phi ngữ cảnh xác suất từ vựng để xây dựng bộ phân tích cú pháp. Chương 3 sẽ trình bày về kho ngữ liệu, một thành phần không thể thiếu theo hướng tiếp cận sử dụng thống kê. Chương này sẽ giới thiệu về một số đặc điểm, cách tiếp cận xây dựng kho ngữ liệu tiếng Anh – Penn Treebank và kho ngữ liệu tiếng Việt – Viet Treebank. Chương 4 sẽ cung cấp cái nhìn tổng quan nhất về bộ phân tích cú pháp của Bikel. Chương 5 sẽ trình bày về cách thức thực hiện thực nghiệm thông qua việc sử dụng bộ phân tích cú pháp của Bikel cho tiếng Việt dựa vào kho ngữ liệu Viet Treebank và các kết quả cũng như đánh giá với hướng tiếp thống kê sử dụng Viet Treebank để huấn luyện. Cuối cùng là kết luận và tài liệu tham khảo. 7 Chương 2. Phương pháp phân tích cú pháp Trong chương trước chúng ta đã thấy được một số khái niệm cơ bản về xử lý ngôn ngữ tự nhiên, phân tích cú pháp là gì và vai trò của nó trong các vấn đề của xử lý ngôn ngữ tự nhiên. Để xây dựng bộ phân tích cú pháp, hầu hết các phương pháp hiện nay đều sử dụng văn phạm phi ngữ cảnh (Context Free Grammar) hay những cải tiến bố sung để miêu tả các ngữ pháp. Trong chương này, chúng ta sẽ tìm hiểu một số phương pháp xây dựng bộ phân tích cú pháp từ trước đến nay. Đầu tiên phần 2.1, sẽ nêu lại khái niệm về văn phạm phi ngữ cảnh, khái niệm chung để biểu diễn ngôn ngữ và nền tảng cho các phương pháp sau này. Trong phần 2.2, chúng ta sẽ nhắc lại hai phương pháp cổ điển là top – down và bottom – up (thuật toán CYK – cook, young and kasami), chart parsing (thuật toán Earley – phương pháp kết hợp giữa top – down và bottom – up). Phần 2.2 sẽ đưa ra hướng đi mới trong việc xây dựng bộ phân tích cú pháp, bài toán phân tích cú pháp được coi như là một vấn đề trong học máy. Và trong chương cuối, chúng ta sẽ tiếp cận với một mô hình sử dụng từ tố kết hợp với xác suất để giải quyết bài toán. 2.1. Văn phạm phi ngữ cảnh Muốn thực hiện được phân tích cú pháp trước tiên ta cần phải biểu diễn được ngôn ngữ đó bằng máy tính. Ngôn ngữ được định nghĩa là tập các xâu mà mỗi xâu này được tạo ra bởi một tập hữu hạn các phần tử không rỗng gọi là bảng chữ cái, ví dụ như bảng chữ cái tiếng Việt và ngôn ngữ tiếng Việt. Văn phạm là một bộ gồm 4 phần từ: G = với -    chứa hữu hạn các phần từ được gọi là phần tử kết thúc – terminal. -    chứa hưu hạn các phần tử được gọi là phần tử không kết thúc – nonterminal và     . - S là một trong những phần tử   được gọi là ký tự bắt đầu. - R là một tập hữu hạn các văn phạm, chứa các luật ngữ pháp(đôi khi gọi là sản xuất – production). Hợp giữ  và  được gọi là từ điển đầy đủ của ngôn ngữ. Một xâu gọi là được sinh ra bởi văn phạm khi và chỉ khi xâu đó có một dẫn xuất đầy đủ trong G. Chomsky đưa ra phân loại của mình về văn phạm: - Văn phạm loại 0: Văn phạm cấu trúc câu là các văn phạm mà luật có dạng - Văn phạm loại 1: Văn pham cảm ngữ cảnh là văn phạm mà luật có dạng với là độ xài của xâu . - Văn phạm loại 2: Văn phạm phi ngữ cảnh là văn phạm mà luật có dạng - Văn phạm loại 3: Văn phạm chính quy là văn phạm mà luật có dạng 8 Trong phân tích cú pháp người ta sử dụng văn phạm phi ngữ cảnh hoặc một số cải tiến của văn phạm phi ngữ cảnh để biểu diễn văn phạm xây dựng các phương pháp để giải quyết bài toán phân tích cú pháp. Phần tiếp theo sẽ trình bày về các phương pháp này. 2.2. Các phương pháp cổ điển 2.2.1. Phân tích top – down 2.2.1.1. Định nghĩa Cây cú pháp sinh ra bởi bộ phân tích top – down là kết quá của quá trình xây dựng cây bằng việc xuất phát từ một ký tự bắt đầu(gốc của cây), sử dụng các luật trong văn phạm phi ngữ cảnh để đi từ gốc đến là (ký tự kết thúc – nằm trong chuỗi cần phân tích). Đối với các luật có cùng vế trái, việc lựa chọn luật có thể đơn giản dựa theo độ lớn của xâu về phải (so sánh giữa các xâu về phải) hoặc đơn giản là thứ tự của các xâu vế phải trong bộ luật. Trong trường hợp phân tích top – dowm chưa kết thúc (chưa phát triển được toàn bộ xâu đầu vào) thì ta thực hiện quay lui để tìm luật khai triển phù hợp. 2.2.1.2. Mô tả thuật toán Đầu vào: văn phạm phi ngữ cảnh không đệ quy trái (nếu văn phạm đệ quy trái thì khi phân tích sẽ xảy ra hiện tượng lặp vô hạn) và chuỗi từ cần phân tích. Đầu ra: là các cây cú pháp của chuỗi từ cân phân tích. - Bước 1: Ta gọi gốc của cây là S (ký tự bắt đầu). Ta sử dụng một con trỏ chỉ vào xâu cần phân tích. Từ vào hiện tại là từ trong xâu vào được con trỏ trỏ đến. Vị trí đầu tiên của con trỏ là từ trái nhất của xâu. - Bước 2: Giả sử A là ký tự đỉnh hiện tại và con trỏ đang trỏ vào ký tự x của xâu đầu vào (đỉnh hiện tại là đỉnh sẽ được xây dựng tiếp theo) +Nếu A thuộc tập ký tự không kết thúc thì chọn luật mà vế trái là A, giả sử luật này có dạng A  X1X2..Xk thì ta chọn nút X1 làm nút đang xét. Nếu như k = 0 thì đỉnh phân tích tiếp theo sẽ là ký tự bên phải của A. + Nếu A thuộc tập ký tự kết thúc thì thực hiện so sánh với từ vào hiện tại. Nếu trùng nhau thì lấy ký tự bên phải A là đỉnh phân tích tiếp và con trỏ dịch sang phải một ký tự. Nếu như khác nhau thì quay lại bước 2a, chọn luật kế tiếp bắt đầu bằng A. Sau một số hữu hạn bước ta sẽ phân tích được hết xâu vào, lúc đó sẽ có trường hợp sau: - Xây dựng được cây cú pháp với đầu vào là văn phạm và xâu - Không xây dựng được cây cú pháp 2.2.1.3. Ví dụ Ta sử dụng văn phạm sau: S  NP VP (1) NP  N (2) 9 N  “tôi” (3) N  “bò” (4) N  “cỏ” (5) VP  V (6) VP  V PP (7) V  “ăn” (8) V  “bò” (9) PP  N (10) Ta thực hiện việc phân tích câu “tôi bò”. Sau đây là dẫn xuất của quá trình phân tích 10 Hình 3: Dẫn xuất phân tích top - down Quá trình phân tích từ trái qua phải, tìm dẫn xuất của ký tự không kết thúc trái nhất, ưu tiên luật từ trên xuống dưới, ở đây từ dẫn xuất d  e ta thấy xâu “tôi” “ăn” không chính xác nên quay lui, ta có được dẫn xuất f khi sử dụng luật 9. Cuối cùng ta thu được xâu cần phân tích. 2.2.2. Phân tích bottom – up: 2.2.2.1. Định nghĩa: Khác hẳn với phân tích top – down, bộ phân tích bottom – up xuất phát từ một câu đầu vào, sử dụng hai hành động chính là đẩy vào (shift) và thu gọn (reduce) để thu gọn chuỗi đầu vào thành ký tự bắt đầu (gốc của cây cú pháp). Sử dụng một ngăn xếp, ta tiến hành đẩy các từ đầu vào vào ngăn xếp theo chiều từ trái sang phải (shift), nếu như ngăn xếp có thể thu gọn (reduce – ngăn xếp lúc này chứa vế phải của một luật và những ký tự này có thể được thay bằng vế trái của luật đó). Cũng giống như trong phân tích top – down, khi xảy ra lỗi, hoặc không phân tích được, chúng ta thực hiện hành động quay lui để phát triển theo một luật khác. Quá trình này tiếp tục cho đến khi ta không thể quay lui được nữa, lúc này nếu ngăn xếp không được thu gọn về trạng thái bắt đầu thì bộ phân tích bottom – up không thể phân tích chuỗi từ đầu vào. 2.2.2.2. Ví dụ Ta sử dụng lại văn phạm đã định nghĩa ở trên để phân tích câu “bò ăn cỏ” S  NP VP (1) NP  N (2) N  “tôi” (3) N  “bò” (4) N  “cỏ” (5) 11 VP  V (6) VP  V PP (7) V  “ăn” (8) V  “bò” (9) PP  N (10) Ta có cây phân tích 12 13 Hình 4: Dẫn xuất phân tích bottom - up Ta thấy có quá trình tích khi đến trạng thái (e) có lỗi xảy ra nên thực hiện quay lui, chú ý ở đây có trường hợp N  bò, và V  bò, tuy nhiên với cách sắp xếp luật như trên nên trường hợp này không bị phân tích lỗi, tuy nhiên khi có lỗi xảy ra có thể vẫn quay lui về cây cú pháp đúng này. 2.2.3. So sánh giữa top – down và bottom – up Cả hai phương pháp này đều có những ưu điểm và nhược điểm riêng. Chiến lược phân tích top – down không lãng phí thời gian để duyệt các cây không là kết quả đối với gốc S, khi mà nó bắt đầu được sinh ra bởi những cây này. Điều đó có nghĩa là nó cũng không bao giờ thăm các cây con mà không thể tìm được vị trí trong các gốc cây S. Ngược lại, đối với chiến lược bottom – up, cây cú pháp có thể không được sinh ra bởi ký tự bắt đầu S hoặc phù hợp với bất kỳ nốt liền kề nào đó, mà được sinh ra một cách ngẫu nhiên. Cách tiếp cận có những nhược điểm nhất định. Trong khi không lãng phí thời gian với nhưng cây không bắt đầu bởi S, bộ phân tích lại dành quá nhiều nỗ lực vào cây S mà không phù hợp với đầu vào. Điểm yếu này của bộ phân tích là do việc sinh cây diễn tra trước khi kiểm tra về đầu vào. 2.2.4. Thuật toán CYK (Cocke – Younger – Kasami) 2.2.4.1. Mô tả: Thuật toán CYK, đôi khi được gọi là thuật toán CKY, có thể xác định được một xâu có do một văn phạm phi ngữ cảnh sinh ra hay không, và cách mà nó được sinh ra. Thuật toán này là một dạng phân tích bottom – up sử dụng quy hoạch động. Thuật toán CYK làm việc với văn phạm phi ngữ cảnh chuẩn. Văn phạm phi ngữ cảnh chuẩn là văn phạm phi ngữ cảnh trong đó luật có dạng , và nếu văn phạm phi ngữ cảnh không chứa xâu rỗng thì đều có thể phân tích về dạng chuẩn Chomsky. 14 2.2.4.2. Mã giả và ví dụ - Mã giả của thuật toán CYK Let the variable Carlos be the input string consisting of n letters, a1 ... an. Let the grammar contain r nonterminal symbols R1 ... Rr. This grammar contains the subset Rs which is the set of start symbols. Let P[n,n,r] be an array of booleans. Initialize all elements of P to false. For each i = 1 to n For each unit production Rj -> ai, set P[i,1,j] = true. For each i = 2 to n -- Length of span For each j = 1 to n-i+1 -- Start of span For each k = 1 to i-1 -- Partition of span For each production RA -> RB RC If P[j,k,B] and P[j+k,i-k,C] then set P[j,i,A] = true If any of P[1,n,x] is true (x is iterated over the set s, where s are all the indices for Rs) Then Carlos is member of language Else Carlos is not member of language - Ví dụ Ta sử dụng lại văn phạm ở ví dụ trước và phân tích lại câu “bò ăn cỏ” sử dụng thuật toán CYK S  NP VP (1) NP  N (2) N  “tôi” (3) N  “bò” (4) N  “cỏ” (5) VP  V (6) VP  V PP (7) V  “ăn” (8) V  “bò” (9) PP  N (10) Trước hết, ta thấy văn phạm này chưa phải là văn phạm phi ngữ cảnh chuẩn. Ta thực hiện việc chuyển đổi về văn phạm mới S  NP VP (1a) NP  “tôi” (2a) (ghép luật (2) với luật (3)) NP  “bò” (3a) (ghép luật (2) với luật (4)) NP  “cỏ” (4a) (ghép luật (2) với luật (5)) N  “tôi” (5a) N  “bò” (6a) N  “cỏ” (7a) 15 VP  “ăn” (8a) (ghép luật (6) với luật (8)) VP  “bò” (9a) (ghép luật (6) với luật (9)) VP  V PP (10a) V  “ăn” (11a) V  “bò” (12a) PP  “tôi” (13a) (ghép luật (10) với luật (3)) PP  “bò” (14a) (ghép luật (10) với luật (4)) PP  “cỏ” (15a) (ghép luật (10) với luật (5)) Ta có bảng phân tích sau: S S VP NP, N, PP, VP VP, V NP, N, PP, VP Bò ăn cỏ Bảng 1: Bảng phân tích bằng thuật toán CYK 2.2.5. Thuật toán Earley 2.2.5.1. Mô tả Cũng giống nhưng CYK, Earley (Earley, 1970) sử dụng cách tiếp cận bằng quy hoạch động để đưa ra bộ phân tích top – down. Như mọi lời giải của quy hoạch động, thuật toán này giảm thời gian chạy từ hàm mũ về hàm đa thức bằng cách loại bỏ những giải pháp con do việc quay lui sinh ra. Trong trường hợp này, quy hoạch động làm cho thuật toán có thời gian chạy là O (N3) với N là tống số từ của chuỗi đầu vào. Tư tưởng chính của thuật toán Earley là duyệt từ trái qua phải và tạo ra một mạng được gọi là chart có N + 1 thực thể. Mỗi từ trong câu, chart chứa một danh sách các trạng thái biểu diễn từng thành phần của cây phân tích mà nó được sinh ra. Khi phân tích xong một câu, chart đánh dấu việc phân tích câu đầu vào đã kết thúc. Mỗi cây con có thể chỉ được biểu diễn một lần duy nhất và có thể được bộ phân tích sử dụng lại. Mỗi trạng thái riêng chứa một thực thể chart bao gồm ba thông tin: một cây con tương ứng với một luật ngữ pháp, thông tin về quá trình phát triển cây, và vị trí của cây con tương ứng với đầu vào. Chúng ta đặt ký tự chấm (.) ở bên phải của một luât ngữ pháp để miêu tả quá trình phát triển đã phân tích được luật đó. Cấu trúc này được gọi là dotted rule. Trạng thái của vị trí sẽ được miêu tả bởi hai số: xác định vị trí trạng thái bắt đầu và vị trí của dấu chấm. Sử dụng văn phạm ở phần 2.2.1 ta có ví dụ về dotted rule như sau: S   NP VP [0, 0] VP  V  PP [1, 2] N  “cỏ”  [2, 2] Nguyên lý cơ bản của bộ phân tích Earley là phát triển thông qua tập N + 1 trạng thái trong chart từ trái qua phải, xử lý từng trạng thái nằm trong tập đó. Tại mỗi bước, một trong ba toán từ được miêu tả ở dưới đay được áp dụng đối với mỗi trạng thái của của luật. Trong mỗi trường hợp, kết quả được đưa thêm vào một trạng thái mới dựa vào trạng thái hiện tại hoặc kế tiếp trong chart. Thuật toán luôn phát triển tiếp thông 16 qua việc tạo thêm thông tin vào chart, trạng thái không bao giờ bị hủy bỏ và không có quay lui về thực thể chart trước đó. Và trạng thái S  α , [0, N] trong danh sách các trạng thái là thực thể chart cuối cùng, thể hiện quá trình phân tích thành công đầu vào. Ba toán từ chính của thuật toán Earley là PREDICTOR, COMPLETER và SCANNER. Các toán từ này nhận đầu vào là một từ và dưa ra một trạng thái. Hai toán từ PREDICTOR và COMPLETER đưa thêm các trạng thái vào thực thể, còn SCANNER thêm trạng thái vào một thực thể chart mới. + Predictor Predictor có nghĩa là người dự đoán, đúng như tên gọi của nó toán từ này có nhiệm vụ tạo ra trạng thái mới, biểu diễn các trạng thái có thể xảy ra trong suốt quá trình phân tích. PREDICTOR được áp dụng đối với bất kỳ trạng thái nào mà ký tự không kết thúc nằm ở bên phải của dấu chấm và không nằm trong nhóm part-of- speech. Kết quả của toán tử này là một trạng thái mới cho mỗi mở rộng được thay thế cho kí tự không kết thúc trong ngữ pháp. Chúng bắt đầu và kết thúc tại vị trí của dấu chấm trong xâu đầu vào tại điểm mà trạng thái được sinh ra kết thúc. + Scanner Khi một trạng thái có từ được gán nhãn nằm ở bên phải của dấu chấm, toán từ Scanner được goi để kiểm tra đầu vào và hợp nhất trạng thái tương ứng với các nhãn để đưa vào chart. Nhiệm vụ hoàn thành khi một trạng thái mới được tạo ra và thay đổi vị trí của dấu chấm dựa vào nhóm đầu vào đã dự đoán. Chú ý rằng, bộ phân tích Earley sử dụng đầu vào như bộ phân tích top – down để tránh nhập nhằng trong quá trình phân tích, chỉ những ký tự kết thúc (được gán nhãn) , những từ được dự đoán bởi những trạng thái, sẽ được phân tích bởi chart. + Completer Toán tử Completer áp dụng cho những trạng thái mà dấu chấm đã ở cuối luật. Dễ dàng nhận thấy, trạng thái hiện tại thể hiện rằng bộ phân tích đã thành công trong việc tìm ra dẫn xuất theo ngôn ngữ của đầu vào. Mục địch của toán tử Completer là tìm trong những luật ngữ pháp và phát triển những trạng thái trước đối với vị trí hiện tại của đầu vào. Trạng thái mới được tạo bằng việc lấy những trạng thái cũ, và phát triển dấu chấm thông qua luật của ngữ pháp và đưa những trạng thái mới vào thực thể chart hiện tại. 17 Hình 5: Mã giả của thuật toán Earley Ta sử dụng văn phạm ở phần trước để phân tích câu “tôi bò” dùng thuật toán Earley: S  NP VP (1) NP  N (2) N  “tôi” (3) N  “bò” (4) N  “cỏ” (5) VP  V (6) VP  V PP (7) V  “ăn” (8) V  “bò” (9) PP  N (10) Chart[0]: S   NP VP [0, 0] NP   N [0, 0] N   “tôi” [0, 0] 18 N   “bò” [0, 0] N   “cỏ” [0, 0] Xét từ “tôi” Chart[1] N  “tôi”  [0, 1] NP  N  [0, 1] S  NP  VP [0, 1] VP   V [1, 1] VP   V PP [1, 1] V   “ăn” [1, 1] V   “bò” [1, 1] Xét từ: “bò” Chart[2] V  “bò”  [1, 2] VP  VP  [1, 2] VP  VP  PP [1, 2] PP   N [2, 2] N   “tôi” [2, 2] N   “bò” [2, 2] N   “cỏ” [2, 2] S  NP VP  [0, 2] Trong Chart[2] có trạng thái S  NP VP  [0, 2] và độ dài xâu là 2 nên thông báo phân tích thành công. 2.2.5.2. Khôi phục cây cú pháp từ Chart Thuật toán Earley như ở trên chỉ có tác dụng xác định xem câu cần phân tích có thuộc bộ phân tích cú pháp hay không chứ không phải là một bộ phân tích cú pháp. Sau khi thuật toán kết thúc, thực thể chart cuối cùng sẽ chứa một trạng thái như sau: S  α [0, N]. Tuy nhiên, chúng ta không có phương pháp nào để thu hồi được cấu trúc của S. Để xây dựng bộ phân tích cú pháp từ thuật toán Earley, chung ta cần đưa ra thông tin về cú pháp từ chart. Để là được điều này, chúng ta sẽ miêu tả mỗi trạng thái bằng một tham số kết hợp với thông tin hỗ trợ để lưu trữ thông tin về trạng thái kết thúc. Những thông tin hỗ trợ này được sinh ra khi ta thay đổi toán tử COMPLETER. Bằng việc đánh dấu trạng thái mới được sinh ra từ trạng thái nào trước đó. Việc truy vết cây cú pháp từ chart chỉ đơn thuần là quá trình hồi quy bứt đầu với trạng thái kết thúc của S trong thực thể chart cuối cùng. Nếu có nhiều cây cú pháp đối với một câu, thuật toán Earley không thể trả về toàn bộ kết quả trong thời gian đa thức. Nhưng thời gian tốt nhất để sinh ra chart là thời gian đa thức. Một nhược điểm nữa đó là trong quá trình tạo ra các chart thì thuật toán cũng tạo ra những trạng thái thừa. 19 2.3. Văn phạm phi ngữ cảnh xác suất (PCFGs) 2.3.1. Định nghĩa Một hướng tiếp cận mới trong việc xây dựng bộ phân tích cú pháp là sử dụng phương pháp thống kê. Bài toán phân tích cú pháp giống như một bài toán trong học máy, thông qua quá trình huấn luyện xây dựng một mô hình xác suất, để thực hiện việc lựa chọn cây cú pháp phù hợp nhất. Trong phần này chúng ta sẽ tiếp cận văn phạm phi ngữ cảnh xác suất (PCFG – Probabilistic Context Free Grammar). Mô hình đơn giản nhất của PCFG là văn phạm phi ngữ cảnh (CFG – Context Free Grammar) với xác suất được thêm vào mỗi luật. Tại sao lại sử dụng PCFGs, đó là vì: PCFGs rất đơn giản và mô hình xác suất đơn giản đối với cấu trúc cây, mô hình toán học đơn giản, thuật toán không quá phức tạp, v.v… Văn phạm phi ngữ cảnh xác suất bao gồm: - Tập các ký tự kết thúc { wk } với k = 1, 2, … V - Tập các ký tự không kết thúc { Ni } với i = 1, 2, … n - Ký tự N1 được gọi là ký tự bắt đầu - Tập các luật có dạng Ni  αj với α  [ w x N ]* - Tương ứng với mỗi luật là một xác suất P (Ni  αj) sao cho với J là tống số luật có vế trái là Ni. Khi viết P (Ni  αj) có nghĩa là P (Ni  αj | Ni) – xác suất sử dụng luật Ni  αj khi xuất hiện vế trái Ni. Để miêu tả một câu là dùng chuỗi sau: w1w2…wm hay wab để miêu tả một chuỗi ký tự không kết thúc wa…wb. Một dạng rút gọn khi biểu diễn các nhánh cây có gốc là nốt Ni và dẫn xuất ra xâu wa…wb như sau: Ta có thể hiểu rằng xâu wa…wb có thể dẫn xuất từ Nj. Xác suất của một câu sẽ được tính theo công thức với t là cây cú pháp của xâu. Ta thử áp dụng PCFGs cho tập văn phạm ở phần 2.1: S  NP VP 1.0 (1) NP  N 1.0 (2) N  “tôi” 0.33 (3) N  “bò” 0.33 (4) N  “cỏ” 0.34 (5) VP  V 0.5 (6) VP  V PP 0.5 (7) V  “ăn” 0.5 (8) V  “bò” 0.5 (9) wa…wb N Hình 6: Miêu tả dẫn xuất xâu từ Ni 20 PP  N 1.0 (10) Hình 7: Cây cú pháp của câu "bò ăn cỏ " Giả sử với cây cú pháp này ta sẽ tính toán xác suất của cây 2.3.2. Nhược điểm của văn phạm phi ngữ cảnh xác suất - Văn phạm phi ngữ cảnh thiếu sự nhạy bén đối với các thông tin từ vựng. Trong ngôn ngữ, ý nghĩa và cấu trúc câu phụ thuộc nhiều vào ngữ cảnh của câu đó, chằng hạn câu “Trung hiểu Nam hơn Thắng”. Câu này có thể đưa phân tích thành 2 cấu trúc như Hình 8 và Hình 9. 21 Hình 8: Cây dẫn xuất thứ nhất của xâu "Trung hiểu Nam hơn Thắng" Hình 9: Cây dẫn xuất thứ hai của xâu "Trung hiểu Nam hơnThắng" 22 Câu này hoàn toàn đúng về mặt cú pháp, nếu xác suất của hai câu, ta phải đưa thông tin về từ vựng như ngữ cảnh nói vào để phân biệt. - Văn phạm phi ngữ cảnh xác suất thiếu nhạy bén trong việc xác định cấu trúc ngữ pháp: đôi khi trong việc phân tích cú pháp việc xác định cấu trúc còn phụ thuộc vào từ cấu tạo nên câu. Một ví dụ đơn giản là nếu ta có một luật là NP  N N, ta thấy trong ngôn ngữ có một số từ không thể đi cùng với nhau, nhưng trong quá trình tính toán cấu trúc có sự phi lý đó lại có xác suất lớn, vì vậy đó xảy ra hiện tượng nhập nhằng. Vì vậy, đối với văn phạm phi ngữ cảnh xác suất việc đưa thêm thông tin cú pháp vào là cải tiến có lợi. 2.4. Văn phạm phi ngữ cảnh xác suất từ vựng (LPCFGs) Như ở phần trước, chúng ta đã tiếp cận mô hình xác suất cho bộ phân tích cú pháp. Tuy nhiên, mô hình nà vẫn còn một số nhược điểm. Năm 1996, trong luận án, Collin đã đưa ra mô hình xác suất mới dựa vào từ vựng (LPCFG – Lexical Probabilistic Context Free Grammar). Trong ba mô hình, Collin đưa vào văn phạm phi ngữ cảnh xác suất cấu trúc head. 2.4.1. Cấu trúc head Giả sử ta có một cụm từ như sau: “một mái tóc đẹp”. Đối với cụm này ta có thể phân chia thành các phần như sau: “một” – thành phần phụ trược “mái” – thành phần trung tâm “tóc” – thành phần phụ sau “đẹp” – thành phần phụ sau Từ mái ở đây là thành phần trung tâm của cụm từ ta thử bỏ thành phần trung tâm này đi thì cụm từ sẽ là: “một tóc đẹp”. Đối với cụm mới tạo ra này, ta thấy rõ ràng cụm này vô nghĩa, bởi “tóc” là danh từ không đếm được không thể đi với từ chỉ số lượng “một”. Tuy nhiên chú ý rằng ta có thể bỏ từ “một” nhưng cụm từ vẫn có nghĩa (“mái tóc đẹp”) … Như vậy, từ “mái” là thành phần trung tâm của cụm từ hay câu (head). Như vậy, trong văn phạm này, mỗi ký tự không kết thúc được gắn thêm thành phần trung tâm của cụm từ hay câu đó. Việc xác định head của một ký tự không kết thúc, ta phải dựa vào head của các ký tự con. 23 Hình 10: Cây cú pháp của xâu "bò ăn cỏ" có thêm thông tin từ vựng 2.4.2. Mô hình một: Mô hình cơ sở Đây là mô hình cơ bản nhất trong các mô hình do Collins đưa ra. Đầu tiên ta có một luật giống như trong văn phạm phi ngữ cảnh xác suất (PCFG) có dạng như sau: 1 H là ký tự không kết thúc đánh dấu cho thành phần head và h là từ trung tâm được gán cho ký tự này. L1, … Ln và R1.. Rm là thành phần trái, phải của ký tự H. Nếu như n hoặc m bằng không hay cả n và m đều bằng không thì luật unary. Ngoải ra, ở vế trái và phải của chuỗi ta thêm 2 ký tự STOP nhằm đánh đấu kết thúc luật. Vì vậy ta có Ln+1 = Rm+1 = STOP. Ta lấy dẫn suất S (ăn)  NP (bò) VP (ăn) làm ví dụ ở đây n = 1, m = 0, P = S, H = VP, L1 = NP, L2 = STOP, R1 = STOP, h = (ăn, V), l1 = (bò, N). Xác suất của luật có thể được tính dựa vào chain rule như sau: 24 2 Tiếp theo đó, chúng ta giả sử rằng các ký tự không kết thúc hoàn toàn độc lập thì ta có thể viết lại biểu thức như sau: 3 4 Như vậy, mỗi bước phân tích về phải của luật từ vế trái của luật thì bao gồm ba bước chính sau: 1. Sinh ra nhãn head của cây với xác suất là 2. Tính toán xác suất đối với vế trái của head có xác suất là , trong đó Ln+1 (ln+1) = STOP. Ký tự STOP sẽ được thêm vào bảng ký tự không kết thúc, và mô hình sẽ dừng việc sinh tiếp xác suất vế trái cho đến khi gặp ký tự STOP. 3. Tính toán xác suất đối với vế phải của head là và ký tự Rm+1(rm+1) cũng là STOP giống như ở bước 2. Áp dụng phương trình 2 vào ví dụ trên ta sẽ có Tuy nhiên, trong thực tế, các từ không hoàn toàn độc lập với nhau mà có một độ phụ thuộc nào đó. Đề giải quyết việc này, ta có thể sử dụng history base model để ước lượng xác suất. Sử dụng hàm  để miêu tả cho ước lượng xác suất dựa vào history base model. Ta có: 5 6 Có thể nhận thấy rằng phương trình 5 và 6 là trường hợp ta loại bỏ mọi thứ đối với hàm  chỉ giữ lại P, H và h. 25 Chú ý rằng, khoảng cách giữa các từ bổ nghĩa cho thành phần trung tâm cũng rất quan trọng. Trong một số trường hợp đặc biệt, đó là dấu hiệu để nhận biết của cấu trúc phân nhánh (độ phụ thuộc của các từ liền kề nhau), hay sự phụ thuộc thông qua động từ. Thông tin về khoảng cách có thể được đưa vào mô hình nhằm nâng cao sự phụ thuộc giữa các từ bổ trợ. Ta có thể viết lại công thức như sau: 7 8 Hình 11: Miêu tả độ đo khoảng cách trong câu 2.4.3. Mô hình 2: Phân biệt định ngữ và bổ ngữ, subcategorization Ta thử lấy một cây như sau trong tiếng Anh: Hình 12: Cây cú pháp với hậu tố - C đánh dấu complement. "IBM" và "Lotus" là chủ ngữ và bổ ngữ, trong khi "Last week" là định ngữ. Trong mô hình hai này, để đánh dấu đâu là bổ ngữ thì ta đưa thêm hậu tố -C vào mỗi ký tự không kết thúc. Tại sao việc xác định bổ ngữ lại quan trọng? Trong ví dụ trên, “IBM” được xác định là chủ ngữ của câu, còn “Last week” là thành phần bổ nghĩa, mặc dù cả hai cùng được gán nhãn NP, ngoài ra “Lotus” cũng là một danh từ được gán nhãn NP, ở đây “Last week” là một thành phần bổ nghĩa cho sự kiện, còn “Lotus” lại bổ nghĩa cho động từ “bought”. Vì vậy “Lotus” là bổ ngữ (complement), “Last week” là định ngữ (adjunction). Sự khác biệt về chức năng của hai nhãn NP 26 (“Last week”, và “IBM”) là không phù hợp trong cây cú pháp, vì hai nhãn NP đặt cùng vị trí. Ngoài ra, chúng ta chỉ có thể đưa những thông tin này vào trong quá trình phân tích. Việc đưa thông tin này vào làm tăng khả năng xác định cây cú pháp đúng, giảm sự nhập nhằng của văn phạm. - Việc xác định bổ ngữ rất phức tạp đối với việc sử dụng xác suất. Thông tin về từ vựng là cần thiết. Ngoài ra, độ ưu tiên của các subcategoziation cũng cần được để ý đến. - Trong quá trình phân tích cú pháp, việc phân biệt bổ ngữ và định ngữ cũng làm tăng độ chính xác. Ta sử dụng ví dụ sau: Hình 13: Hai ví dụ về các thành phần bổ trợ được sinh ra một cách độc lập đã gây ra sai số. Việc xác định định ngữ và bổ ngữ có thể thông qua các luật đơn giản ví dụ như đối với Penn Treebank đó là một ký tự không kết thúc nếu là NP, SBAR, hoặc S có cha là S thì sẽ được đưa vào trong subcategoration frame. Trong ngôn ngữ có rất nhiêu luật quy định thành phần nào được đưa vào trong subcategorization frame, ví dụ trên chỉ là một trường hợp nhỏ. Dựa vào subcategorization frame ta có thể đưa ra được mô hình xác suất cho mô hình 2. Mô hình một có thể được huấn luyện với tập dữ luyện nâng cao bao gồm các ký tự không kết thúc và quá trình học các thông tin từ vựng có thể chỉ ra được sự phân biệt giữa bổ ngữ và định ngữ. Tuy nhiên, nó vẫn còn gặp phải những ước lượng độc lập tồi. Đề giải quyết vấn đề này, quá trình xử lý mới thừa kế mô hình một được cải tiến bằng cách thêm vào xác suất phụ thuộc của subcategorization frame trái và phải: - Lựa chọn head H với xác suất - Lựa chọn subcat frames trái và phải, LC và RC với xác suất và . Mỗi một subcat frame là một tập (tập này có thể chứa các ký tự không kết thúc có nhãn giống nhau) các từ bổ nghĩa cho head ở phía trái hoặc phải. 27 - Tính toán xác suất cho các từ bồ nghĩa ở vế trái hoặc phải của head dựa vào biểu thức và . Vì vậy, subcat cần được thêm vào trạng thái của ngữ cảnh. Trong trường hợp bổ ngữ được sinh ra, chúng sẽ bị loại bỏ trong các tập subcat thích hợp. Quan trọng nhất là xác suất của ký tự STOP được gán là 0 khi tập subcat không rỗng và xác suất của bổ ngữ bằng 0 khi nó không nằm trong tập subcat nào cả. 2.4.4. Mô hình 3: Trace và Wh-movement Một khó khăn cho việc phân tích vị ngữ đối với bộ phân tích cú pháp đó là wh- movement (trong tiếng Anh, đây là thành phần nằm trong mệnh đề như which, whom v.v…, với tiếng việt đôi khi từ liên kết bị giảm đi ví dụ như câu “Nguyễn Văn A sinh viên trường công nghệ đã đoạt giải trong kỳ thi Sao Mai 2008 – Nguyen van A who is student in coltech, have just get price in Sao Mai 2008”). Ở đây, TRACE được dùng để dánh dấu các mệnh đề quan hệ như trong ví dụ sau: Ví dụ 1: “Câu chuyên (SBAR mà TRACE mua Lotus) Ví dụ 2: “Câu chuyện (SBAR mà IBM mua TRACE) Ví dụ 3: “Câu chuyện (SBAR mà IBM mua Lotus từ TRACE) Ta có thể viết các luật cơ bản để nhận dạng ra trường hợp này trong cây cú pháp. Tuy nhiên, nhiệm vụ này nên được đưa vào trong bộ phân tích cú pháp bởi vì nó đủ phức tạp để nhân ra được sự thay đổi của xác suất và việc đưa vào bộ phân tích có thể nâng cao độ chính xác. Nguyên nhân thứ hai để đưa tham số này vào bộ phân tích cú pháp là nhằm nâng cao các tham số cho mô hình. Thông thường, xác suất của các subcategorization không rõ ràng trong quá trình phân tích. Trong 3 ví dụ ở trên động từ “mua” là ngoại động từ nhưng nếu không có thông tin truy vết thì xác suất của “mua” sẽ làm cho nó trở thành nội động từ. Như vậy, đối với mỗi một ký tự không kết thúc trong cây cú pháp ta đưa thêm vào đó một đặc trưng gap giống như GPSG (Gazadar et al. 95) và đưa thêm đặc trưng này vào cây cho đến khi không thể truy vết được nữa. 28 Chương 3. Tiếp cận trong xây dựng bộ phân tích cú pháp Tiếng Việt Như trong chương trước, bộ phân tích cú pháp giống như bài toán trong học máy. Để xây dựng mô hình xác suất cho bộ phân tích chúng ta cần thông qua quá trình huấn luyện. Vậy dữ liệu để huấn luyện bộ phân tích cú pháp là gì? Hiện nay, trên thế giới đã có một số ngữ liệu cho Tiếng Anh (Penn Treebank), Tiếng Trung (Chinese Treebank) và kho ngữ liệu dành cho tiếng Việt (Việt Treebank) đang được xây dựng. Chương này sẽ tập trung miêu tả về kho ngữ liệu Penn Treebank và Việt Treebank. 3.1. Penn Treebank Treebank là một kho ngữ liệu trong đó mỗi câu đều có cấu trúc cú pháp thường ở dạng cây. Treebank thường được xây dựng dựa vào tập ngữ liệu đã gán nhãn, đôi khi các thông tin về ngôn ngữ hoặc ngữ nghĩa cũng được đưa vào cấu trúc cú pháp nhằm tăng chất lượng của Treebank. Việc xây dựng Treebank có thể được thực hiện hoàn toàn thủ công hoặc bán tự động với bộ phân tích cú pháp, sau khi phân tích cú pháp, cây cú pháp cần được kiểm tra đôi khi phải hoàn chỉnh lại nó. Công việc này có thể kéo dài đến hàng năm. Penn treebank do đại học Pennsylvania phát triển, chứa khoảng 4.5 triệu câu Anh – Mỹ. Trong ba năm từ 1989 đến 1992, người ta thực hiện việc gán nhãn từ loại cho các câu. Ngữ liệu này có thể được tìm thấy trên website: Phần tiếp theo sẽ trình bày về một số nhãn từ loại trong Penn Treebank. Sau đó, chúng ta chuyển sang nhiệm vụ xếp các thành phần với nhau để đưa ra một cây cú pháp. 3.1.1. Gán nhãn từ loại 3.1.1.1. Miêu tả: Ngữ liệu Brown được coi là tập ngữ liệu đầu tiên trên thế giới, sau nó xuất hiện thêm nhiều ngữ liệu khác. Trong tập ngữ liệu Brown có 87 nhãn từ loại cơ bản và cho phép thực hiện việc ghép những nhãn từ loại với nhau tạo ra một nhãn từ loại mới. Khối ngữ liệu này khá đồ sộ với 135 nhãn từ loại, một số ngữ liệu sau này cũng có số lượng nhãn từ loại tương đương. Tuy nhiên, khác hẳn với các ngữ liệu trước đây, tập nhãn từ loại của Penn Treebank ít hơn rất nhiều so với các khối ngữ liệu khác. Mặc dù dựa trên tập nhãn cơ sở là các nhãn trong khối ngữ liệu Brown, nhưng nhóm xây dựng Penn Treebank sử dụng thông tin cú pháp và thông tin từ vựng trong việc làm giảm tập nhãn cú pháp. Ngoài ra, việc kích thước tập nhãn cú pháp cũng làm 29 tăng tính nhất quán trong ngữ liệu. Một ví dụ đơn giản ở đây đó là nếu hai cụm từ hay câu về cú pháp có một sự tương đồng nhưng được gán nhãn hoàn toàn khác nhau là điều không thích hợp. Trong Penn Treebank, nhóm xây dựng ngữ liệu đã đưa thêm thông tin liên quan đến ngữ cảnh vào để thực hiện việc gán nhãn, qua đó tăng độ chính xác của ngữ liệu. Một đặc điểm riêng nữa của Penn Treebank đó là tính đa dạng. Không như các ngữ liệu khác, việc gán nhãn không nhất thiết là một nhãn duy nhất mà nó còn có thể có nhiêu loại nhãn khác nhau. 3.1.1.2. Bảng nhãn từ loại Nhãn từ loại trong Penn Treebank được biểu diễn bởi hình 3.. Nó chứa tất cả 36 nhãn từ loại và 12 loại nhãn khác (dành cho tiền tệ và dấu câu). Bảng 2: Bảng nhãn từ loại trong Penn Treebank 3.1.1.3. Quá trình gán nhãn từ loại Theo dự án Penn Treebank [15], quá trình gán nhãn từ loại bao gồm hai giai đoạn thực hiện việc gán nhãn tự động và chỉnh sửa thủ công. - Quá trình tự động: trong dự án này, câu được gán nhãn bằng PART (Church 1988), thuật toán thống kê được phát triển bởi AT&T Bell Labs. PARTS sử dụng một mô hình chỉnh sửa của tập nhãn của Brown Corpus với sai số khoảng 3-5%. Đầu tiên, 30 đẩu ra của PARTS sẽ được tự động từ tố hóa, sau đó được gán dựa vào tập các nhãn từ loại của Penn Treebank. Sai số ở đây khoảng 7-9%. - Quá trình chỉnh sửa thủ công: sau khi được gán nhãn tự động bởi PARTS, đầu ra bây giờ cần được chỉnh sửa lại cho đúng. Công việc này được thực hiện bởi con người – người chú giải. Anh ta sử dụng một trình soạn thảo văn bản (ở đây là GNU Emacs Lisp) để thao tác. Dưới đây là ví dụ trước và sau khi xử lý được lấy ra từ tài liệu của nhóm xây dựng Penn Treebank. Hình 14: Dữ liệu đã gán nhãn trước khi xử lý thủ công Hình 15: Dữ liệu đã gán nhãn sau khi xử lý thủ công Hình 3. 1: Sau khi được xử lý 3.1.2. Bracketing 3.1.2.1. Phương pháp cơ bản Phương pháp để gộp toàn bộ ngữ liệu là xử lý song song đối với việc gán nhãn và chỉnh sửa thủ công. Với bộ nhãn như trên, người ta sử dụng Fidditch, bộ phân tích tất định được phát triển bởi Donald Hindle. Một số thuộc tính cơ bản của bộ phân tích: - Fidditch luôn đưa ra ít nhất một cây cú pháp đối với một đầu vào, nên không cần tìm kiếm trong nhiều kết quả. 31 - Fidditch không đính kèm bất kỳ thành phần nào có vai trò quá quá lớn. Fidditch tách đầu vào thành xâu các cây, đưa ra cấu trúc cho mỗi một câu. - Fidditch có một độ phủ ngữ pháp tốt. Vì vậy, mà câu phân tích được khác chính xác. 3.1.2.2. Tập nhãn cú pháp. Nhãn cú pháp là tập nhãn liên quan đến ngữ pháp, ví nhụ như ADJP là nhãn để đánh dấu cụm tính từ. Trong tập nhãn này có một số thành phần miêu tả cho các thành phần rỗng. Hình 3.3 được lấy ra từ tài liệu của nhóm xây dựng Penn Treebank miêu tả các nhãn cú pháp: Bảng 3: Bảng nhãn cú pháp trong Penn Treebank 3.1.2.3. Ví dụ Đây là một ví dụ về đầu ra của quá trình bracketing. Sau quá trình này ta có những cây cú pháp hoàn chỉnh: 32 Hình 16: Dữ liệu hoàn chỉnh 3.2. Viet Treebank 3.2.1. Mục tiêu Cũng giống như Penn Treebank, Viet Treebank là kho ngữ liệu dành cho Tiếng Việt, bao gồm các câu được biểu diễn dưới dạng cấu trúc cú pháp (cây cú pháp). Viet Treebank được xây dựng nhằm đáp ứng những yêu cầu về dữ liệu đối với những nghiên cứu trong xử lý ngôn ngữ tự nhiên, ví dụ như việc sử dụng Viet Treebank làm dữ liệu để huấn luyện và kiểm chứng mô hình phân tích cú pháp sử dụng văn phạm phi ngữ cảnh xác suất từ vựng (LPCFG) trong luận văn này. Mục tiêu dự án là xây dựng 10000 câu tiếng việt dưới dạng cây cú pháp. Theo tài liệu của nhóm xây dựng của Viet Treebank [4], phương phướng tiếp cận để xây dựng cây cú pháp tương tự với phương pháp của nhóm xây dựng Penn Treebank (chia làm hai quá trình gán nhãn tự động và chỉnh sửa thủ công). 3.2.2. Danh sách từ loại và các nhãn cú pháp Trong quá trình xây dựng cây cú pháp, nhóm xây dựng Viet Treebank tiếp cận theo quan điểm phân từ loại (quan điểm đối lập là không phân từ loại, phủ nhận sự tồn tại của từ loại – Lê Quang Trinh, Nguyễn Hiển Lê, Hồ Hữu Tùng). Thông qua nhãn từ loại ta có thể biết được một số thông tin như: từ loại (động từ, danh từ…), chức năng của ngữ pháp của từ (chủ ngữ, vị ngữ, …) Bảng 4: Nhãn từ loại trong Viet Treebank STT Tên Chú thích 1 N Danh từ 2 Np Danh từ riêng 3 Nc Danh từ chỉ loại 4 Nu Danh từ đơn vị 5 V Động từ 33 6 A Tính từ 7 P Đại từ 8 L Định từ 9 M Số từ 10 R Phụ từ 11 E Giới từ 12 C Liên từ 13 I Thán từ 14 T Trợ từ, tiểu từ, từ tình thái 15 U Từ đơn lẻ 16 Y Từ viết tắt 17 X Các từ không phân loại được Ngoài ra, đối với các từ nhãn từ viết tắt là nhãn kép, ví dụ như từ HIV có nhãn là Ny. Trong dữ liệu mới nhất của nhóm, có xuất hiện thêm nhãn Nb miêu tả các từ vay mượn. Cũng giống như trong Penn Treebank hay bất kỳ một kho ngữ liệu khác, Viet Treebank có tập nhãn chức năng, cụm từ riêng biệt. Bảng 5: Bảng nhãn cụm từ trong Penn Treebank STT Tên Chú thích 1 NP Cụm danh từ 2 VP Cụm động từ 3 AP Cụm tính từ 4 RP Cụm phụ từ 5 PP Cụm giới từ 6 QP Cụm từ chỉ số lượng 7 MDP Cụm từ tình thái 8 UCP Cụm từ gồm hai hay nhiều thành phần không cùng loại được nối với nhau bằng liên từ đẳng lập 9 LST Cụm từ đánh dấu đầu mục của danh sách 34 10 WHNP Cụm danh từ nghi vấn (ai, cái gì, con gì, v.v.) 11 WHAP Cụm tính từ nghi vấn (lạnh thế nào, đẹp ra sao, v.v.) 12 WHRP Cụm từ nghi vấn dùng khi hỏi về thời gian, nơi chốn, v.v. 13 WHPP Cụm giới từ nghi vấn (với ai, bằng cách nào, v.v.) Bảng 6: Bảng nhãn mệnh đề trong Viet Treebank STT Tên Chú thích 1 S Câu trần thuật (khẳng định hoặc phủ định) 2 SQ Câu hỏi 3 S-EXC Câu cảm thán 4 S-CMD Câu mệnh lệnh 5 SBAR Mệnh đề phụ kết (bổ nghĩa cho danh từ, động từ, và tính từ) 3.2.3. Một số đặc điểm của Viet Treebank - Trong tiếng Việt, một câu hay một cụm từ luôn có một từ có ý nghĩa quan trọng, nếu bỏ từ này đi thì cụm từ, hay câu đó mất hết ý nghĩa hoặc có thể trở nên sai. Từ này được gọi là thành phần trung tâm (head). Ví dụ như trong cụm từ sau: “quả bóng màu xanh” thì thành phần chính ở đây là từ “quả” các từ còn lại đều bổ nghĩa cho từ này. Trong Viet Treebank, thành phần trung tâm có một nhãn riêng cho nó là H (điều này không có trong Penn Treebank). Việc xác định thành phần trung tâm trong Penn Treebank dựa vào các luật ngữ pháp khá phức tạp, riêng đối với Viet Treebank ta chỉ cần dựa vào nhãn của từ đó. Ngoài ra, do tính chất tịnh tiến của tiếng Việt, nếu trong câu có nhiều head thì việc xác định thành phần trung tâm của cả câu dựa thành phần trung tâm của thành phần chính rồi đến phụ. - Trong tập dữ liệu mới nhất chứa khoảng 9000 câu huấn luyện và 500 câu để kiểm chứng, có sự khác biệt so với tập dữ liệu cũ. Trong tập dữ liệu mới này, đưa thêm vào nhãn ‘-‘ gắn với dấu ‘-‘ hoặc ‘–‘. Việc sử dụng nhãn ‘-‘ có thể gây nhập nhằng trong quá trình phân tích bởi dấu ‘-‘ được dùng để phân cách giữa nhãn từ loại và nhãn chức năng ví dụ như nhãn N-H. 35 Chương 4. Bộ phân tích cú pháp của Bikel 4.1. Một số nhiệm vụ cơ bản 4.1.1. Tiền xử lý Khác với bộ phân tích cú pháp của Collins, trong bộ phân tích này, Bikel đã thực hiện một số quá trình trước khi đưa dữ liệu vào huấn luyện: - loại bỏ một số nút không cần thiết - thêm vào nút cơ bản của NP (NPBs) - chỉnh sửa lại những nhãn NP - thêm vào thông tin gap (chỉ dành cho mô hình 3 - Collins) - gán lại nhãn cho câu không có chủ ngữ. - loại bỏ các thành phần rỗng - phát triển dấu câu - xác định tham số của ký tự không kết thúc - bỏ qua một số đối số của ký tự không kết thúc - chỉnh sửa các câu không có chủ ngữ - tìm kiếm head 4.1.1.1. Liên kết các cụm từ Liên kết các cụm từ là khái niệm quan trọng và một số bước tiền xử lý dựa vào khái niệm này. Một nút được biểu diễn là liên kết giữa cụm từ nếu: - nó không chứa các thành phần trung tâm trong nốt con và là chứa liên từ - là liên từ khi - là ký tự đứng sau head nhưng không kết thúc - là ký tự đứng ngay trước head nhưng không là ký tự bắt đầu Trong Penn Treebank, liên từ được gán nhãn CC, còn trong Viet Treebank nhãn là C. Ví dụ trong Penn Treebank và Viet Treebank: 36 Hình 17: Liên kết từ trong Penn Treebank Hình 18: Liên kết từ trong Viet Treebank 4.1.1.2. Loại bỏ các nút không cần thiết Quá trình tiền xử lý này nhằm loại bỏ các ký tự tiền kết thúc, không có hoặc ít liên hệ đế hiệu suất của quá trình phân tích cú pháp. Đối với dữ liệu Treebank tiếng Anh, ta có thể loại bỏ các cây con, mà nhãn gốc của nó là một trong những nhãn {, “, .}. Có hai lý do để thực hiện việc loại bỏ này khi phân tích dữ liệu tiếng Anh đó là: các ký tự trích dẫn thường có độ ưu tiên thấp, và không xuất hiện trong các bao đóng chắc chắn trong bất kỳ trường hợp nào, nên không được đếm trong khi tính toán xác suất. Trong tiếng Việt, trường hợp loại bỏ này cũng tương tự. 37 4.1.1.3. Thêm vào các nốt base NP Nút có nhãn là NP là một trong nút cơ bản (NP – cụm danh từ (Penn Treebank và Viet Treebank đều giống nhau) khi mà nó không chi phối một nút NP khác. Chính xác hơn, một nút có nhãn là NP là nút cơ bản khi nó không ảnh hưởng tới các nút có nhãn NP khác, ngoại trừ trường hợp nút NP sở hữu, những có nhãn NP và đi kèm với nút có nhãn là POS nhằm xác định đại từ sở hữu ví dụ như “(NP (NNP California) (POS 's)”. Chính bản thân các nút NP sở hữu cũng chính là nút NP cơ sở, vì vậy các nút này sẽ được thay nhãn thành NPB. Để đảm bảo bộ phân tích làm việc chính xác, khi một nút NP được gán lại nhãn là NPB, các nút NP bình thường khác cũng được thêm vào như là một ký tự không kết thúc cha. Việc thêm vào này bảo đảm cho các nốt NPB luôn bị chi phối bởi nút NP. Để thêm các nút NP này cần phải thỏa mãn một số điều kiện sau: - nút cha của NPB không phải là nút NP - nút cha của NPB là một nút NP nhưng tạo ra hiện tượng liên kết các cụm từ - nút cha của NPB là một nút NP nhưng - nút cha của thành phần trung tâm không phải là NPB - nút chả chưa được gán lại nhãn là NPB (Xem Hình 19) Hình 19: Nút NBP cần thêm nút NP Trong quá trình tiền xử lý, khi một nút NPB là nút con duy nhất của một nút NP, thì nút NP thêm vào sẽ bị loại bỏ bằng việc ghép hai nút trở thành một nút NP duy nhât và tất cả nút NPB còn lại sẽ bị gán lại nhãn thành NP 4.1.1.4. Khôi phục những nút NP cơ bản Việc thêm các nhãn NP như trên đã làm cho các nút NP đạt được một mức đồng bộ nhất định, hiệu quả của việc phân chia mô hình sẽ làm cho việc tạo ra các nút con của NP giảm bớt độ phức tạp. Trong bộ phân tích cú pháp của mình, Collins dường như cũng cố gắng nâng cao tính ổn định của mô hình NPB. Các nút NPB, có các nút sentential như là nút cuối cùng (ở bên phải nhất) được chỉnh sửa: các nút con “sentential” được nâng lên để trở thành một nốt con bên phải của nút NPB 38 Hình 20: Nhãn NBP được chỉnh sửa 4.1.1.5. Thêm thông tin “gap” Đặc trưng “gap” chỉ xuất hiện trong mô hình 3 của Collins, việc sử dụng đặc trưng này nhằm nâng cao khả năng phân tích câu, khi có hiện tượng truy vết và wh- movement (xuất hiện mệnh đề quan hệ trong câu). Quá trình tiền xử lý này, xác định tất cả các thành phần rỗng, xác định chỉ mục của nhãn WHNP (Penn Treebank, trong Viet Treebank cũng sử dụng nhãn này), thay thế các nhãn rỗng này bằng nhãn truy vết đặc biệt, và liên kết các đặc trưng gap trong tất các các ký tự không kết thúc trong chuỗi từ mà đại từ quan hệ thay thế và cụm từ truy vết. Trong quá trình tiền xử lý này có một điểm cần chú ý đó là việc thực thi bước tiền xử lý này cần kiểm tra các trường hợp tại đó việc liên kết là không thể, chẳng hạn như có hai tiến trình thêm gap phụ thuộc vào nhau. Quá trình thực thi cần phải điều khiển được sự phụ thuộc của hai tiến trình thêm gap. 4.1.1.6. Gán lại nhãn cho nhãn chức năng chủ ngữ Những nút mà nhãn của câu không có chủ ngữ sẽ được chuyển từ S thành SG (trong Penn Treebank và Viet Treebank đều có nhãn SG). Bước này cho phép bộ phân tích cú pháp nhạy bén đối với các ngữ cảnh khác nhau mà câu không có chủ ngữ xuất hiện nhưng gán nhãn S giống như câu bình thường, trong trường hợp này các câu không có chủ ngữ xử sự giống như một cụm danh từ. Một ví dụ [S[SFlying planes] is dangerous] của Collins miêu tả trường hợp này. Tuy nhiên, điều kiện để một nhãn S có thể được gán lại nhãn không được giải thích rõ ràng, một trường hợp là mỗi nhãn S của chủ ngữ (trong Penn Treebank là nhãn –SBJ, trong Viet Treebank là nhãn –SUB) phụ thuộc vào thành phần rỗng sẽ được gán lại nhãn là SG. Các điều kiện là: - một thành phần con của nhãn bị tri phối bởi thành phần rỗng được đánh dấu bởi nhãn –SBJ - có nhãn cha là VP - không có tham số xuất hiện ưu tiên so với thành phần trung tâm 4.1.1.7. Loại bỏ thành phần rỗng Bước này chỉ đơn giản bao gồm việc cắt cây để khử các cây con chỉ bị tác động bởi các thành phần rỗng. Các nhãn truy vết được thêm vào ở bước “thêm đặc trưng 39 gap” không được xét đến ở đây, trừ khi nút được đánh dấu bởi nhãn –NONE– (trong Penn Treebank, cũng tương tự trong Viet Treebank). 4.1.1.8. Đưa dấu câu lên Tư tưởng chính của việc đưa dấu câu lên là làm cho các dấu câu bao gồm dấu chấm và dấu phẩy ở vị trí cao nhất có thể trong cây phân tích, nằm ở giữa hai ký tự không kết thúc. Dấu câu xuất hiện ở đầu hoặc cuối câu thường được thay đổi. Ngoài ra, bước này cần được điều khiển trường hợp xuất hiện nhiều dấu câu bắt đầu hoặc kết thúc một nút, tốt hơn trường hợp các nút dấu câu xuất hiện một cách vô lý như trường hợp dấu câu xuất hiện thành một chuỗi trái hoặc phải của cây con (Xem Hình 21). Cuối cùng, trường hợp nút chỉ chi phối một dấu câu đứng trước một ký tự kết thúc. Bộ phân tích của Bikel chỉ thông báo trong trường hợp này. Hình 21: Nâng cấc dấu câu lên, trong cây bên phải xuất hiện các dấu phẩy nằm cạnh nhau 4.1.1.9. Xác định đối số của ký tự không kết thúc Collins đưa ra tập phương pháp để đánh dấu các ký tự không kết thúc như là các đối số, bằng cách thêm –A vào nhãn của ký tự không kết thúc. Bộ phân tích cú pháp của Bikel sử dụng ba thông tin không được Collin công bố về tìm kiếm các đối số: - Nhãn PP được chọn như là ký tự không kết thúc đầu tiên sau head (thành phần trung tâm). Trong nhiều trường hợp, đối số của nút có nhãn là NP sẽ được đánh dấu. Một nguyên tắc phức tạp hơn là ký tự không kết thúc đầu tiên ở bên phải của head không là nhãn PRN (Viet Treebank không có nhãn này) hay các nhãn từ loại được đánh dấu là đối số. Nhãn PRN trong Penn Treebank đánh đấu cho biểu thức mở - đóng ngoặc đơn, thường xuất hiện trong nút PP như ví dụ sau: “on (or above) the desk”. - Nút con là một phần của liên kết các cụm từ được gán lại nhãn là đối số của ký tự không kết thúc. - Head khác biệt so với các nút cùng cấp (các nút bên trái và bên phải của head) bởi hiệu quả của các loại tham số sinh ra head trong mô hình phân tích cú pháp. (Xem Hình 22). 40 Hình 22: Nút có nhãn HEAD cũng không là ngoại lệ khi thay đổi nhãn chức năng 4.1.1.10. Loại bỏ cá đối số của ký tự không kết thúc không được sử dụng Bước này loại bỏ tất các các đối số của các ký tự không kết thúc, ngoại trừ những thành phần được thêm vào từ bước tiền xử lý khác (như nhãn –A trong nhãn đối số). Đồng thời cũng loại bỏ tất cá nhãn chức năng được đánh dấu bởi Treebank. 4.1.1.11. Thay đổi câu không có chủ ngữ Với đối số như miêu tả ở phần trước, nếu một câu không có chủ ngữ được tìm thấy mà đối số có ảnh hưởng tới head của nó thì bước này chuyển ngược lại từ SG về nhãn S. 4.1.1.12. Tìm head Trong bộ phân tích cú pháp của Bikel, khi thực hiện tìm kiếm head, sẽ có một số luật được dùng để miêu tả cho một số nhãn. Các luật để tìm kiếm được đóng gói trong bộ phân tích cú pháp như là một “Java package”. Tuy nhiên trong [9], Bikel cũng miêu tả một trường hợp không có luật để phân tích ví dụ như nhãn NX, hay một số trường thợp liên quan đến nhãn CC. Do đặc điểm của Viet Treebank, thành phần trung tâm có nhãn là –H, vì vậy việc tìm kiếm thành phần trung tâm dựa vào nhãn –H này. Ngoài ra, tiếng Việt có tính chất tịnh tiến, như vậy trong một câu có nhiều head, thì head của câu đó sẽ là phần từ trái nhất. 4.1.2. Huấn luyện Công việc của bộ huấn luyện là phân tích dứ liệu huấn luyện (cây cú pháp của câu được gán nhãn từ loại) thành chuỗi head và các bước sinh thành phần bổ trợ, thực hiện việc xác định xác suất trong mỗi bước. Tại mỗi bước, thành phần H, Li, Ri đều được sinh ra dựa vào trạng thái trước đó, và mỗi sự kiện đều sinh ra các thành phần và một vài giá trị ngữ cảnh được đếm. Tuy nhiên, trong quá trình phân tích, vẫn còn tồn tại một số vấn đề, vì vậy xác suất cần được làm mịn (smoothing). 41 4.1.2.1. Verb intervening Trong chương 2, khi nói về văn phạm phi ngữ cảnh xác suất, ta thấy trong mô hình 1, xác suất phụ thuộc vào một độ đo khoảng cách. Trong bộ phân tích cú pháp của Bikel, có một hàm có nhiệm vụ đưa ra độ đo khoảng cách này. Một trong hai thành phần của độ đo khoảng cách đó được gọi là “verb intervening”, là tính chất vi có giá trị true nếu động từ được sinh ra trong quá trình duyệt xâu cùng về một phía so với head. Như Hình 23. Định nghĩa của đặc trưng này rất đơn giản giống như tên của nó cv (“contain verb”), đặc trưng này nhận giá trị true khi và chỉ khi một nốt chứa động từ 9 Chúng ta định nghĩa verb intervening đệ quy trong mô hình Markov bậc 1 10 tương tự với đối với các ký tự bên phải Trong Penn Treebank, bộ phân tích cú pháp của Bikel xác định một từ được coi là động từ nếu nhãn từ loại của nó nằm trong tập {VB, VBD, VBG, VBN, VBP, VBZ}, đối với Viet Treebank chỉ có một nhãn duy nhất là V. Nếu muốn đạt được những kết quả của collins chúng ta cần đưa thêm cv (NPB) = false, trong bộ phân tích của Bikel, nếu như một động từ nằm trong nhãn base NP thì sẽ không được tính. Dưới đây là một ví dụ được lấy từ [9] Hình 23: Một ví dụ về hàm vi (“verb intervening”) nhận giá trị true, do nhãn NP có chứ động từ 4.1.2.2. Bỏ qua một số cây Trong bộ phân tích của Collins, các câu dài quá 500 token (bao gồm từ, ký tự không kết thúc, mở ngoặc) đều bị bỏ qua trong quá trình phân tích. Một nguyên nhân có thể phỏng đoán đó là với các câu quá dài thì có thể có nhiều cây phân tích vì vậy nó 42 sẽ làm giảm độ chính xác của bộ phân tích cú pháp. Trong dữ liệu chuấn WSJ (Wall Street Journal) phần 02-21 của Penn Treebank có khoảng 120 câu bị loại bỏ. 4.1.2.3. Các từ chưa biết - Các từ nếu xuất hiện trong tập dữ liệu thấp hơn một ngưỡng nào đó sẽ được đánh dấu là “UNKNOW”. Giá trị ngưỡng này trong bộ phân tích của Collins là 5 lần. Giá trị này có thể thay đổi thông qua việc gán giá trị cho thuộc tính “unknow word threshold”. - Một sự khác biệt giữa bộ phân tích cú pháp của Collins và Bikel là với những ký tự được đánh dấu là UNKNOW, các ký tự này vẫn được đếm và tính toán xác suất, còn Collins không làm điều này. Chú ý rằng các từ trong cây cú pháp dùng để huấn luyện sẽ không bị bộ phân tích chỉnh sửa, không thực hiện việc phá vỡ thành các mức sự kiện. Việc ánh xạ các từ có tần số xuất hiện thấp chỉ được thực hiện khi tất cả dữ liệu được thu thập và thực hiện đếm. 4.1.3. Các loại tham số và các đánh giá. Tất cả các tham số được sinh ra đều ước lượng xác suất có điều kiện. Mặc dù, các loại tham số đều là cực đại xác suất có điều kiện, tham số rất quan trọng trong việc tạo ra một mô hình xác suất và luôn làm trơn xác suất dựa vào “linear interpolation” của ước lượng “maximum-likelihood, sự dụng trong ngữ cảnh khác nhau. - Ánh xạ các mức của tập các ký tự không kết thúc: Trong dữ liệu của Penn Treebank sử dụng đối số với nhãn là –A và –g. Một sự tương đồng so với bộ phân tích cú pháp của Collins, đó là hai ánh xạ trên cũng được Collins đưa ra trong hàm loại bỏ các tham số. Hàm “argument removal” được gọi là hàm α, còn hàm “gap removal” gọi là hàm γ. Ví dụ: - - - Hàm loại bỏ gap chỉ có tác dụng trong mô hình 3, bởi mô hình 2 và 1 không sử dụng đặc trưng. 4.1.3.1. Loại tham số head: Ký tự không kết thúc head được tạo ra với điều kiện nút cha là một ký tự không kết thúc giống như head word và had tag, và nút cha thì nhận được thông tin về từ vựng dựa vào nút con. Xác suất được miêu tả như sau: 11 với P là ký tự thể hiện nút cha, w và t là word và tag. 4.1.3.2. Loại tham số subcat: Khi mô hình đưa ra ký tự không kết thúc là head cho các ký tự cha, subcategorization frame (subcat) cũng được tạo ra ở hai phía của head với xác suất như sau: 43 12 13 Trong bộ phân tích cú pháp cho tiếng Anh, Bikel đưa ra một số luật tìm kiếm subcat thông qua các nhãn NPs, Ss, SBARs và PPs, và một số trường hợp cho PP. 4.1.3.3. Thay đổi loại tham số của ký tự không kết thúc: Ngoài các nút head, và sucat được tạo ra, các thành phàn bổ trợ cũng được tạo ra dựa vào thành phần head… Một ký tự không kết thúc có đầy đủ thông tin từ vựng gồm ba thành phần chính, nhãn của ký tự không kết thúc, head word (thành phần trung tâm) và nhãn từ loại của nó. Để tạo ra được ký tự không kết thúc có đầy đủ các thông tin về từ vựng việc thay đổi các ký tự không kết thúc được thực hiện trong hai bước, cho phép tham số được làm trơn(smooth) một cách độc lập, và trong một chu kỳ, việc này nhằm nhăng chặn các vấn đề dư thừa thời gian. Hai bước ước lượng này dùng công thức chuỗi để liên kết các sự kiện của ba thành phần với nhau. Đầu tiên, một phần từ vựng (partially-lexicalized) một dạng của ký tự không kết thúc được tạo ra, bao gồm các nhãn không là ký tự và các nhãn từ loại của từ head (thành phần trung tâm). Thành phần từ vựng này thay đổi các ký tự không kết thúc, sinh ra các điều kiện trong nhãn cha, nhãn head, từ head, head tag, trạng thái của subcat và độ đo khoảng cách. Tham số ở đây bao gồm: 14 15 ở đây  là ký hiệu của độ đo khoảng cách (xác định bằng hàm verb intervening). Như thảo luận ở trước, một trong hai thành phần của độ đo khoảng cách là vi (“verb intervening”). Thành phần còn lại là một tính chất được biết thông qua thành phần bổ trợ hiện tại là thành phần bổ trợ đầu hiên hay trường hợp i = 1. Bước thứ hai là sinh ra head word, do luật chuỗi (chain rule), ngữ cảnh chứa các điều kiện đều ở trong phương trình 14 và 15. 4.1.3.4. Loại tham số cho dấu câu và liên kết các cụm từ - Mô hình không đồng nhất Trong một bước tiền xử lý, các dấu câu đều được nâng lên vị trí cao nhất trong cây cú pháp. Điều đó có nghĩa là trong một số trường hợp, dấu câu hành xử như là một liên kết giữa các cụm từ bên trái và bên phải của dấu câu. Quan sát được hiện tượng này sẽ có ích cho các liên từ trong việc đưa ra các điều kiện sinh ra. Trong Penn Treebank, liên từ được gán nhãn CC (C ở trong Viet Treebank) và nút dấu câu thường là nút nằm ở bên phải của head hay nút phía sau của head (post-head). Như vậy, nút liên từ hoặc nút dấu câu xảy ra ở trước head (pre-head), nó sẽ không được tạo ra trong mô hình này. Ngoài ra, nếu có một thành phần ở giữa head và vế phải của liên từ, tham số sẽ được tính toán để đảm bảo rằng về trái luôn là nút head. Tham số mới kết hợp chặt chẽ với mô hình bằng việc xem xét tất cả thành phần bổ trợ thông qua hai cờ: coord, đánh dấu ký tự không kết thúc liên kết với head thông 44 qua nhãn ký tự CC (trong gói tiếng việt ký hiệu CC miêu tả liên từ, nhưng nhãn từ loại của nó là C phù hợp với Viet Treebank, đối với gói tiếng Anh, nhãn từ loại vẫn là CC), và punc, đánh dấu sự liên kết thông qua dấu câu. Nếu như cả hai cờ này đều nhận giá trị true, ta sẽ xem xét tỷ lệ giữa để đưa ra lựa chọn. - Máy sự kiện: Khi thực hiện việc giả lập lại các kết quả của Collins, Bikel sử dụng sự kiện cũ để ước lượng sự kiện sinh ra liên kết bởi liên từ hoặc dấu câu với 2 về của liên từ đó. Sự thay đổi lớn đầu tiên đó là việc đối xử giữa nút có nhãn dấu câu và nút có nhãn là CC như là lớp đối tượng đầu tiên, có nghĩa là việc sinh ra như là một hành động chỉnh sửa các ký tự không kết thúc. Sự thay đổi tiếp theo là khá là phức tạp. Bikel đưa ra định nghĩa mới về độ đo khoảng cách, dựa vào thuộc tính vi. Sau đó, thêm vào các điều kiện để ánh xạ các mức của việc sinh ra thành phần bổ trợ trước đó dựa vào hàm ánh xạ sau: 16 trong đó là một trong các ký tự không kết thúc hoặc . Như vậy xác suất có thể được tính dựa vào biểu thức sau 17 trong đó side là một biến logic nhằm xác định ký tự M nằm ở bên trái hay bên phải của head. Bằng cách đối xử nút nhãn CC và dấu câu như là lớp ký tự không kết thúc đầu tiên, và thêm ánh xạ của các ký tự không kết thúc trước đó, Bikel, đã liên kết chặt chẽ giữa trường hợp “no intervening” trong thành phần độ đo của Collins (khi i = 0 đối với trường hợp của hàm ) với những trường hợp khác mà sự phụ thuộc là khác nhau. 4.1.3.5. Mô hình NP cơ sở: từ mô hình đến mô hình Trong bộ phân tích cú pháp của Collins có rất nhiều cách để một nút NP cơ sở đặc biệt. Điều đó là do cấu trúc phẳng của nút cấu trúc NP cơ sở trong Penn Treebank được sử dụng khác nhau trong mô hình trong quá trình tạo ra chúng. Mô hình tạo ra các nút con của nút NPB được gọi là mô hình bigram của ký tự không kết thúc (“bigrams of nonterminals”). Sự khác nhau của mô hình này và mô hình bigram language đó là các items tuy được sinh ra không phải là một từ, nhưng được từ vựng hóa các ký tự không kết thúc. Head của một nút NPB được sinh ra không phải dựa vào head, mà tất cả các ký tự bổ trợ sinh ra trước đó. 18 19 Trong bộ phân tích cú pháp của Collins, các thành phần phụ được sinh ra trước đó là head, đối với tất cả trường hợp. Vì vậy, subcat và độ đo khoảng cách không liên 45 quan đến nhau, nếu như thành phần bổ trợ hiện tại đứng ngay trước head (điều này làm cho cv (“contain verb”) luôn trả về giá trị false đối với NPBs). Ngoài ra, các nút NPB không bao giờ được coi là thành phần liên kết các cụm từ và CCs chi phối bởi NPB không bao giờ sử dụng tham số PCC, mặc dù, nó sử dụng các tham số được sinh ra khác. Dấu câu bị chi phối bởi NPB, được tạo ra thông qua tham số Ppunc, nhưng chủ yếu các thành phần bổ trợ được liên kết với head tạm thời (pseudo head) thông qua những thành phần bổ trợ được tạo ra trước đó. Khi tạo ra các thành phần bổ trợ bên phải Ri, các thành phần bổ trợ trướ đó (cùng phía với Ri) không bao giờ là các dấu câu, nhưng lại là những ký tự tiền kết thúc thật sự. Một ngoại lệ khác của thành phần NP cơ bản là sự so sánh giữa các char item dự vào luật cắt bỏ cây và cắt bỏ theo khoảng (beam-pruning). 4.1.3.6. Tham số ứng với độ ưu tiên của các ký tự không kết thúc được từ vựng hóa Trong bộ phân tích cú pháp của Collins, dành cho các ký tự không kết thúc được từ vựng hóa có hai loại tham số, hai loại này tính toán những lề tương đồng dành cho ký tự không kết thúc chứa yếu tố từ vựng (lexical nonterminal). Những lề này là những giá trị thô của xác suất bên ngoài chart item (xem (Barker, 1979, Lari và Young, 1990) thuật toán Inside-Outside). Những nghiên cứu trước đây chỉ ra rằng, chỉ những xác suất bên trong thì chưa đủ để làm độ đo khi so sánh các chart item trong cùng một khoảng thời gian khi thực hiện decoding, do đó các xác suất bên ngoài chart item cũng phải là thừa số đề so sánh. Như vậy ta sẽ có công thức sau: 20 4.1.3.7. Trọng số làm trơn Hầu hết các loại tham số trong mô hình của Collins, cũng như trong hầu hết các mô hình phân tích cú pháp dựa vào thống kê, là xác suất điều kiện với nhiều điều kiện và trường hợp khác nhau. Các điều kiện và trường hợp này được thể hiện thông qua tập các sự kiện trong quá trình xử lý. Thông thường với tiếp cận sử dụng thống kê, quá trình huấn luyện thường đòi hỏi tập dữ liệu dùng để huấn luyện càng lớn càng tốt, do vậy các điều kiện và trường hợp cũng lớn dần theo. Giải pháp ở đây là ta phải thực hiện việc là trơn các phân phối xác suất (smoothing) nếu như có quá nhiều giá trị bằng 0 (các trường hợp này không hề xảy ra, ta có thể lấy ví dụ như trong tiếng việt cụm từ “vui vẻ” có tồn tại nhưng cụm từ “vẻ vui” không tồn tại nên nếu thực hiện xác định phân bố xác suất thì “vẻ vui” có xác suất bằng 0, tập dữ liệu càng lớn, mật độ các xác suất bằng 0 càng tăng lên). Trong bộ phân tích cú pháp của mình, Bikel thừa kế phương thức làm trơn xác suất của Collins là sử dụng “deleted interpolation”, làm trơn xác suất dựa trên phân phối phụ thuộc đầy đủ vào ngữ cảnh và một phần của ngữ cảnh, thực hiện việc xóa thành phần trong ngữ cảnh tại mỗi mức back-off. Giả sử việc làm trơn xác suất của tham số head sẽ là với và . Giả sử ta có một xác suất điều kiện , gọi hàm loại bỏ ngữ cảnh tại mức back-off thứ i là , với . Trong một chuỗi back-off xác suất được 46 ước lượng dựa vào phương pháp maximum likelihood, và xác suất sau khi làm trơn được tính toán dựa vào n – 1 trọng số làm trơn (với n mức back-off) được ký hiệu là . Sử dụng cách định nghĩa đệ quy, ta sẽ có với trọng số tại mỗi mức back-off là được tính như sau: 21 Dễ dàng để chứng minh được rằng nếu 22 thì 23 - Mô hình không đầy đủ Như ở trên ta thấy, việc sử dụng mô hình n mức back-off cần có n – 1 trọng số làm trơn, tuy nhiên, cũng giống như Collin, Bikel đưa thêm một hằng số rất nhỏ (cỡ 10-19) làm tham số thứ n. Việc thêm hằng số này vào có thể làm cho bộ phân tích cú pháp trở nên kém cỏi, vì nó kết thúc bằng việc sử dụng một hằng số. Việc này sẽ không đảm bảo cho phương trình 23 đúng. - Thừa số và giới hạn làm trơn. Để xác định trọng số làm trơn, bộ phân tích cú pháp sử dụng công thức sau: 24 trong đó ci = count (history context of ) và ui là số lượng các ngữ cảnh. Ở đây, hằng số 5 có tác dụng làm giảm độ lớn của trọng số làm trơn, làm cho trọng số nhỏ đi so với mỗi mức back-off. Để đưa ra được giá trị này, Bikel đã thực hiện một số thông kê và quan sát trên tập dữ liệu. Hằng số này được đặt tên là thừa số làm trơn (smoothing factor), ký hiệu là ff. Như vậy ta sẽ có công thức sau: 25 với ft là giới hạn làm trơn. Với mỗi loại tham số, ngoại trừ tham số subcat và , thì ft = 0 và ff = 5. Đối với tham số subcat thì ngược lại tức là ft = 5 và ff = 0, với là ft = 1 và ff = 0. Điều này được giải thích bởi vì, trong khi làm trơn các xác suất tạo ra subcat thì tính đa dạng không xảy ra. Trường hợp thứ hai xảy ra khi ngữ cảnh không được quan sát trên tập huấn luyên v.v…, khi ấy ci = ui = 0. Trong trường hợp này , các xác suất còn lại nhận giá trị thông qua trọng số ngay sau đó . 47 4.1.3.8. Bộ sinh các bổ trợ cho head word Như ta đã biết, một ký tự không kết thúc khi có đầy đủ các thông tin từ vựng được tạo ra thông qua hai bước (xem 4.1.2.c). Bước đầu tiêp nhãn và nhãn từ loại được tạo ra như trường hợp PL hoặc PR. Tiếp theo head được tạo ra nhờ một trong hai đối tượng PL hoặc PR. Tham số back-off được đưa ra được miêu tả như sau: Bảng 7: Các mức back-off với Back-off level 0 1 2 Ở đây với mức cuối, khác hẳn 2 mức trên là do việc loại bỏ hoàn toàn các thành phần đi. Ở đây, Collins sử dụng từ xuất hiện ở hai phía để ước lượng xác suất. Tuy nhiên, trong bộ phân tích cú pháp của Bikel, Bikel chỉ sử dụng một lớp chung cho công việc so với việc sử dụng hai thành phần để đánh giá như Collins. Bằng cách đưa thêm một tham số logic side để xác định phía Bảng 8: Tham số do Bikel đề xuất Back-off level 0 1 2 Một vấn đề nữa đó là việc ánh xạ các từ chưa biết (unknow word). Đối với một số từ do tần sô xuất hiện quá thấp sẽ được gán nhãn là +unknow+, và sau đó nó phải được khôi phục lạ là từ ban đầu. Trong bộ phân tích cú pháp của Bikel, đưa ra một số phương thức tính toán để thực hiện việc này. 4.1.3.9. Lớp tham số TOP Tất cả các cây đều có thể được tạo ra bởi mô hình sử dụng một ký tự không kết thúc nhãn là +TOP+, nhãn cha của gốc cây. Thông tin về từ vựng của ký tự không kết thúc head được sinh ra dựa vào nút +TOP+ (có xác suất ưu tiên là 1.0) bằng cách sử dụng tham số . Trong luận văn Collin đã miêu tả chi tiết về tham số đặc biệt này. Có hai loại tham số được dùng để quan sát gốc của cây, một tham số được sinh ra bởi 48 ký tự không kết thúc đánh dấu gốc cây và được chèn thêm các thông tin từ vựng (ngoài nhãn của nút còn có nhãn từ vựng, nhãn của ký tự không kết thúc), tham số còn lại sinh ra head word trong mỗi câu, được gọi là và . Những tham số này liên quan đến một số kết quả không được Collin công bố trong bài báo của ông. Bảng 9: Cấu trúc back-off đối với các tham số Back-off level 0 +TOP+ t, H, +TOP+ 1 n/a t Chú ý rằng, có backs off tương đương với ước lượng . Tức là, xác suất xuất hiện word khi nhãn của ký tự không kết thúc là tag. Ở đây, có một sự khác biệt giữa mức back-off cuối cùng trong tham số bổ trợ của head-word, thành phần có xác suất là trong không gian các từ tiền kết thúc được từ vựng hóa. Sự khác nhau đó là trong cùng một câu, cùng một head word xuất hiện có thể cùng với một tag trong nhiều nút. Mặc dù vậy, Collins vẫn sử dụng hàm đếm chia sẻ các mức cuối của back-off với tham số khi thực hiện ước lượng xác suất cho tham số . Còn trong bộ phân tích của Bikel, trong mọi trường hợp việc đếm sẽ được chia sẻ với tham số , đối với tham số chỉ là một sự mô phỏng. 4.1.4. Decode Trong bộ phân tích cú pháp của mình, Bikel sử dụng thuật toán CKY (Cook – Kasamy – Young) phân tích cú pháp dựa vào chart và xác suất. Thuật toán phân tích dựa vào chart sử dụng đồng thời phân tích top – down và bottom – up. - Chart item: mục tiêu của quá trình decoding là xác định giả thiết giống nhau nhiều nhất giữa các đối tượng (maximally-likely theory), nếu trong quá trình decoding các chart item là tương đương với các item khác trong chart, thì item nào có xác suất lớn hơn sẽ được tồn tại. Độ tương đồng giữa các chart item được đánh giá bằng khả năng tạo ra các tham số được sử dụng để tạo ra các dẫn xuất: chúng ta đối xử với hai chart item như là không tương đương nếu chúng biểu diễn dẫn xuất mà được coi như không tương đương dựa vào các thành phần đầu ra và điều kiện ngữ cảnh của các tham số đã tạo ra nó, đưa ra giả thuyết về độc lập của mô hình. Ví dụ về hai chart item được cho là tương đương khi chúng có cùng môt nhãn (nhãn của nút gốc của cây dẫn xuất), cùng một head word và tag, và có cùng tập subcat trái và phải. Ngoài ra, chúng cần có cùng nhãn của head giống nhau (nhãn của nút head). Nếu một chart item có nhãn của nút gốc là NP, nhãn của head thường là nhãn NPB, đưa thêm một nút NP thêm vào trong quá trình tiền xử lý để đảm bảo cho nhãn NPB luôn bị ảnh hưởng bởi nhãn NP. Trong trường hợp này, sử dụng một con trỏ ngược trỏ vào nút NP cơ bản (base NP). Ở đây, có một sự khác giữa bộ phân tích cú pháp của Collin và của Bikel, Collins cho rằng nhãn head của nút NP trong chart item không là NPB, chính xác hơn là nhãn head của NPB chart item. Ngoài ra, để có được 49 nhãn của head của một chart item có NP, chúng ta cần dựa vào nút NPB và nhãn của nút NPB. Có được điều đó là do trong một số trường hợp ta coi các nút NPB như là nút được thêm vào. Điều đó làm cho độ chính xác của bộ phân tích tăng lên một chút. - Lược bỏ: Mọi item đều được giữa lại nhưng chúng ta chỉ lựa chọn những item ở trên cùng. Vì vây, để tăng tốc, trong bộ phân tích cú pháp, Collins đưa ra ba kiểu loại bỏ. Đầu tiên đó là sử dụng một thông tin: chart nhớ tất cả các dẫn xuất có xác suất lớn nhất trong mỗi giai đoạn phân tích, và nếu như chart item không mỗi bước không nằm trong các thừa số có xác suất lớn nhất thì chart item không được đưa vào chart. Trong bộ phân tích, Collin đưa ra giá trị 105. Giá trị này thay đổi tùy thuộc vào ngôn ngữ cũng như kinh nghiệm khi chạy dựa trên tập dữ liệu. Nếu chart item biểu diễn dẫn xuất với NP và NP-A có nhiều hơn một nút con, giá trị này sẽ là 104.e3. Một loại nữa đó là phụ thuộc của sự kiện vào dấu phẩy. Qua quá trình thống kê trên Penn Treebank, Collins nhận thấy khoảng 90%, khi một yếu tố chứa dấu phẩy, từ ngay cuối cùng của chu kỳ đang xét là dấu phảy hay là từ cuối cùng của câu. Dấu phẩy thường được sử dụng thường xuyên với cụm nằm trong dấu ngoặc. Vì vậy, nếu dấu phẩy trong câu đầu vào xuất hiện sau một dấu mở ngoặc và trước dấu đóng ngoặc hoặc ở cuối câu, dấu phẩy này không được xét trong sự phụ thuộc trên. Việc sử dụng sự phụ thuộc vào dấu phẩy có thể làm tăng độ chính xác của mô hình. Cuối cùng, một kiểu loại bỏ nữa là với mỗi ô của chart, sẽ chứa các item bao gồm các đoạn trong câu, Collin sử dụng nhóm các item mà có cùng nhãn của nút gốc trong quá trình dẫn xuất. Chỉ có 100 item có xác suất cao nhất mới được lưu trong nhóm này. Một chart có xác suất cao mới được đưa vào nhóm, những thành phần nhỏ sẽ bị loại ra, như vậy trong nhóm sẽ có 100 item có cùng một khoảng và cùng nhãn trong một chart. Tuy nhiên, Bikel không đưa kiểu loại bỏ này vào trong bộ phân tích của mình vì hiệu quả của nó không cao. - Từ và nhãn chưa xác định Trong quá trình tiền xử lý, nếu các từ xuất hiện dưới một ngưỡng (Bikel lấy giá trị này là 5) thì đều được gán nhãn là +UNKNOW+ trong quá trình phân tích. Trong quá trình phân tích, nếu gặp một từ không xác định, nhãn tốt nhất sẽ được gán dựa vào bộ gán nhãn của Ratnaparkhi (Ratnaparkhi, 1996). Một bộ từ điển các nhãn sẽ được xây dựng nếu quá trình huấn luyện chứa các thực thể cần được quan sát kể cả những từ có tần số xuất hiện thấp. Khi đó, nếu thực hiện decoding, đầu ra của bộ gán nhãn chỉ sử dụng đối với từ không xác định, không được quan sát trong khi huấn luyện. Đối với những từ khác, chart liên kết với các item phân chia mỗi nhãn quan sát với một từ trong quá trình huấn luyện 4.2. Tổng quan về bộ phân tích cú pháp. 4.2.1. Mở đầu Trong phần này, chúng ta sẽ đi sâu vào tìm hiểu bộ phân tích cú pháp của Bikel, để thấy được khả năng linh hoạt trong việc xử lý đối với các ngôn ngữ khác nhau. Ngoài ra, bộ phân tích cú pháp còn khá thành công trong việc xây dựng một hệ thống có khả năng xử lý song song. 50 4.2.2. Vấn đề cơ bản 4.2.2.1. Cấu trúc xác suất plug-‘n’-play và xử lý song song giữa các mức câu: Cấu trúc xác suất từ vựng trong WordNet có tính chất đa dạng (Bikel, 2000). Từ sự phát hiện đó, Bikel đã phát triển kiến trúc “plug-‘n’-play” cho cấu trúc xác suất từ vựng. Bikel thừa kế và mở rộng mô hình của mình từ hệ thống BBN’s SIFT (Miller et al., 1998), hệ thống dựa vào history-base model và dẫn xuất từ mô hình hai của (Collins, 1997). Để tính toán, ước lượng các xác suất, bộ phân tích cú pháp BBN có một thành phần khởi tạo các đối tượng dữ liệu để biểu diễn cho đặc trưng và sự kiện trước đó, ước lượng maximum-likelihood đối với với là hàm đếm các sự kiện trong dữ liệu huấn luyện. Trong kiến trúc của Bikel, có một lớp trừu tượng (abstract layer) có nhiệm vụ tính toán giá trị trước đối với từng mức back-off khác nhau trong bộ phân tích cú pháp, trong mã giả, việc khởi tạo đối tượng trước trở nên đơn giản: history = probabilityStructure.get (backOffLevel, fullContext); Ngoài ra, Bikel còn giúp cho hệ thống xử lý nhanh hơn bằng quá trình xử lý song song thông qua việc phát triển đa luồng các sentence server, cung cấp song song các câu ở các mức khác nhau trong cụm môi trường tính toán. 4.2.2.2. Độc lập về ngôn ngữ Trong bộ phân tích cú pháp này, Bikel mở ra khả năng phát triển bộ phân tích đa ngôn ngữ. Bikel và Chiang (2000) đã áp dụng các mô hình phân tích cú pháp (dẫn xuất của bộ phân tích cú pháp BBN’s SIFT và bộ phân tích cú pháp thống kê của David Chiang) cho bộ phân tích cú pháp tiếng Trung. Nhìn chung độ chính xác của bộ phân tích cú pháp tiếng Trung không khác nhiều so với bộ phân tích cú pháp tiếng Anh, việc đánh giá này được thực hiện trên tập ngữ liệu và tập test của mỗi loại ngôn ngữ. Sự khác nhau chính ở đây là do mỗi ngôn ngữ sử dụng các ký tự khác nhau và chức năng của một số nhãn từ loại trong ngôn ngữ. Qua đó, nhận thấy rằng bộ phân tích này có thể hoạt động tốt mà không phụ thuộc vào ngôn ngữ nào, nó cho phép ta tạo ra các gói ngôn ngữ (chứa các dữ liệu và phương thức của ngôn ngữ theo cấu trúc của Treebank). 4.2.3. Tổng quan về hệ thống Bộ phân tích cú pháp của Bikel hỗ trợ cho mô hình phân tích cú pháp dựa vào head (thành phần trung tâm), bao gồm hệ thống BBN’s SIFT, cũng như hỗ trợ mô hình 2 và 3 của Collins (Collins 1997). 51 Hình 24: Các thành phần và luồng làm việc 52 Luồng điều khiển SwitchBoard có tác dụng điều phối quá trình tính toán. Thành phần CYK decoder client và DecoderServer chạy trên các máy chủ đang hoạt động (available hosts), hoặc chạy trên bộ đa xử lý địa phương (local mutiprocessor) hoặc máy chủ trên mạng (thông thường là mạng cục bộ - LAN). Khi bắt đầu chạy bộ decoder và DecoderServer đều thông báo cho SwitchBoard. Sau đó, mỗi bộ decoder gửi yêu cầu đến SwitchBoard để nhận về thông tin về DecoderServer để có thể liên kết được với DecoderServer. Cuối cùng, decoder thực hiện vòng lặp chờ đợi các câu chưa xử lý được gửi tới từ SwitchBoard. Khi tất cả các câu trong tập tin được xử lý, SwitchBoard thu thập các câu có trong câu đầu vào (input file) để đưa ra tập đẩu ra (output file). Khi toàn bộ các câu đã được xử lý, SwitchBoard có nhiệm vụ hủy tất các các decoder và DecoderServer. Hệ thống được thiết kế cho phép sự kết nối lỏng lẻo giữa decoder và DecoderServer. Tuy nhiên, nếu như máy tính có đủ dung lượng bộ nhớ và CPU tốt cung cấp cho mô hình và decoder, nó sẽ có hiệu quả rất lớn khi mỗi decoder tự động kích hoạt DecoderServer riêng và kết nối trực tiếp đến DecoderServer thông qua giao thức mạng. Cơ chế xử lý lỗi Nếu bất kỳ một decoder nào không hoạt động, quá trình xử lý sẽ không bị đứt quãng, nếu như decoder không hoạt động trong khi phân tích một câu, SwitchBoard sẽ đảm bảo rằng câu đó sẽ được phân tích bởi một decoder khác. Nếu bất kỳ một DecoderServer không hoạt động nữa, tất cả decoder kết nối đến DeocderServer sẽ yêu cầu khởi tạo một DecoderServer mới từ SwitchBoard, và trả về thông tin cho decoder có thể kết nối khi các yêu cầu gửi đến, trong thực tế DecoderServer có thể dừng hoạt động trong quá trình phân tích và DecoderServer mới được tạo ra và sử dụng mà không ảnh hưởng đến quá trình phân tích ở mức cao hơn. SwitchBoard luôn theo dõi decoder thông qua các tập tin ghi nhớ (log file), vì vậy nếu như bản thân SwitchBoard dừng hoạt động, thì một SwitchBoard khác sẽ được chạy và có thể khôi phục được tất cả trạng thái trước khi xảy ra sự cố. Trong trường hợp này, tất cả decoder và DecoderServer sẽ chờ đợi SwitchBoard sẵn sàng và đăng ký lại với SwitchBoard, và trở lại việc xử lý các câu. 4.2.3.1. Gói ngôn ngữ: Đối với một ngôn ngữ ví dụ như tiếng Anh, tiếng Trung hay tiếng Việt đều được đóng gói thành “Java package” – tập hợp những lớp thực thi các giao diện nhằm cung cấp các đặc tả và dữ liệu đặc biệt cho ngôn ngữ và miêu tả Treebank. Có bốn lớp chính là : Treebank, Training, HeadFinder và WordFeatures. Lớp Treebank cung cấp dữ liệu và phương thức đề miêu tả Treebank như là nhãn của các ký tự không kết thúc phức tạp. Lớp Training cung cấp các phương thức để tiền xử lý cây trước khi huấn luyện. Lớp HeadFinder có chức năng chính là đọc dữ liệu chứa các luật của head (tập tin nằm trong gói data miêu tả các luật để chọn ra head (thành phần trung tâm) của một câu hay cụm từ) và cung cấp hàm tìm kiếm thành phần trung tâm. Cuối cùng, lớp WordFeatures cung cấp các ánh xạ giữa các yếu tố từ vựng với vector đặc trưng cho hình thái học và phép chính tả nhằm giúp cho quá trình gán nhãn từ loại. Để đảm bảo tính độc lập của ngôn ngữ, tất cả các tập tin vào và ra liên quan đến gói ngôn ngữ đều 53 được đọc và viết theo mã hóa ký tự do người dùng quy định. Bộ phân tích cú pháp của Bikel đảm bảo cho người dùng có thể tạo ra một gói ngôn ngữ trong thời gian ngắn. 4.2.3.3. Đối tượng cấu trúc xác suất Như trong phần trước, mỗi tham số của lớp có liên kết với hàm ánh xạ , 0 ≤ i < n, với n là tống số mức back-off. Cả hai bộ phân tích cú pháp (BBN SIFT và Collins) đều gặp khó khăn trong việc viết mã, với bộ phân tích BBN còn gặp khó khăn trong việc tách biệt kiểu dữ liệu đối với mỗi mức back-off và tham số của lớp. Trong bộ phân tích của Bikel, mỗi kiểu của đơn vị đầu ra của mô hình – bao gồm các ký tự không kết thúc, ký tự tiền kết thúc, từ, đặc trưng của các từ, gap, và subcat frame – đều liên kết với đối tượng ProbabilityStructure, miêu tả cách thức mà đối tượng dữ liệu biểu diễn các đặc trưng và trạng thái trước tại mỗi mức back-off đối với các thành phần đầu ra. Đố tượng chứa ngữ cảnh toàn diện nhất, được gọi là TrainEvent, đều được phân tích thông qua phương thức đơn giản để đưa ra một trạng thái trước hoặc đặc trưng cho mức back-off như đoạn mã giả sau: history = probabilityStructure.get (backOffLevel, fullContext); Với mỗi một lớp trừu tượng cũng có xác suất của các sự kiện, đối tượng miêu tả các sự kiện cần dựa vào interface Event. Lớp trừu tượng này làm tăng độ mềm dẻo của bộ phân tích cú pháp trong quá trình phân tích các sự kiện cũng như xác định kiểu của các thành phần trả về bao gồm các đặc trưng từ thành phần đầu ra. 4.2.3.3. Khả năng linh hoạt của subcat frame. Mô hình 2 và 3 của Collin sử dụng subcategorization frame (subcat), tập các ký tự không kết thúc nằm ở hai phía của head (thành phần trung tâm). Đây là việc cập nhật subcat một cách linh động, khi yêu cầu được thực thi, các ký tự sẽ được tự động xóa khỏi tập. Ví dụ như, subcat chứa ký tự {NP-A}, và nút NP-A được sinh ra ở bên trái của head (thành phần trung tâm), thì chuỗi phân tích con sẽ sinh ra một subcat rỗng, {}. Bằng cách này, subcat động xử sự giống như một history- based model. Trong bộ phân tích cú pháp của Bikel, subcat frames được thực thi từ interface Subcat. Trong quá trình huấn luyện, tất cả các ký tự bổ sung (không có từ vựng) của thành phần head trong mỗi luật đều gọi phương thức add Subcat, sẽ có một quá trình lựa chọn các ký tự không kết thúc để đưa vào subcat. Một số đối