Khóa luận Cách so sánh một số phương pháp học máy cho bài toán gán nhãn từ loại tiếng Việt

1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Lê Hoàng Quỳnh SO SÁNH MỘT SỐ PHƯƠNG PHÁP HỌC MÁY CHO BÀI TOÁN GÁN NHÃN TỪ LOẠI TIẾNG VIỆT KHOÁ 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 2 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Lê Hoàng Quỳnh SO SÁNH MỘT SỐ PHƯƠNG PHÁP HỌC MÁY CHO BÀI TOÁN GÁN NHÃN TỪ LOẠI TIẾNG VIỆT KHOÁ 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: PGS. TS. Hà Quang Thụy Cán bộ đồng hướng dẫn: ThS. Trần Thị Oanh H NI - 2009 3 Chương 1. KHÁI QUÁT VỀ BÀI TOÁN GÁN NHÃN TỪ LOẠI 1.1. Khái niệm và vị trí của bài toán gán nhãn từ loại trong xử lý ngôn ngữ tự nhiên Mỗi từ trong một ngôn ngữ nói chung đôi khi có thể gắn với nhiều từ loại và việc giải thích đúng nghĩa một từ phụ thuộc vào việc nó được xác định đúng từ loại hay không. Công việc gán nhãn từ loại cho một văn bản là xác định từ loại của mỗi từ trong phạm vi văn bản đó, tức là phân loại các từ thành các lớp từ loại dựa trên thực tiễn hoạt động ngôn ngữ [abc]. Việc gán nhãn từ loại thường được thể hiện bằng cách đánh dấu cho mỗi từ một “nhãn” có sẵn theo tập nhãn cho trước, “nhãn” có thể được nhận biết bằng cách viết hoa và đi liền với từ mà nó xác định, hoặc phân cách với từ mà nó xác định bằng dấu “/”. • Input: Một chuỗi các từ và tập nhãn từ loại (Ví dụ như chuỗi các từ “Book that flight.” và tập nhãn từ loại Penn Treebank của tiếng Anh.) • Output: Một nhãn tốt nhất cho từng từ trong chuỗi từ đã được đưa ra (Ví dụ:, đối với chuỗi từ “Book that flight.” thì nhãn thích hợp tương ứng cho từng từ sẽ là Book/VB that/DT flight/NN ./.) Gán nhãn từ loại là một công việc quan trọng và bắt buộc phải có đối với hầu hết các ứng dụng xử lý ngôn ngữ tự nhiên. Nếu coi quá trình xử lý ngôn ngữ tự nhiên gồm các bước: tiền xử lý văn bản, phân tích hình thái, phân tích cú pháp và phân tích ngữ nghĩa thì gán nhãn từ loại thuộc vào bước phân tích hình thái. Bước này có nhiệm vụ phân tích câu thành một bảng các từ (hay cụm từ) riêng biệt, đồng thời kèm theo tất cả các thông tin về từ đó, như là: từ loại (part-of-speech), phạm trù ngữ pháp (category), các biến cách của từ, tiền tố, hậu tố của từ (nếu có). [abc] 1.2. Các vấn đề cơ bản của bài toán gán nhãn từ loại Nếu một từ chỉ có một nhãn và ta có thể xây dựng được một từ điển hữu hạn các từ và nhãn tương ứng của nó thì chắc chắn có thể giải quyết được bài toán gán nhãn từ loại một cách tối ưu. Tuy nhiên, trong thực tế một từ đôi khi có thể có nhiều hơn một từ loại thích hợp, và ta cũng không thể kiểm soát được toàn bộ các từ có thể xuất hiện trong văn bản, điều này dẫn đến hai vấn đề mà bài toán gán nhãn từ loại phải đối mặt: Nhập nhằng từ loại và từ mới. 4 Vấn đề chủ yếu của bài toán gán nhãn từ loại thực chất là việc loại bỏ nhập nhằng về từ loại, tức là khi một từ có nhiều từ loại, nhưng trong một ngữ cảnh cụ thể, nó chỉ có thể có một từ loại đúng mà thôi. [abc] Ví dụ: • Trong câu “I can can a can”, bộ gán nhãn từ loại sẽ phải đánh dấu từ loại như sau: I/PRO can/AUX can/V a/DET can/N”. • Trong hai câu sau đây, từ “race” được gán nhãn khác nhau: - Secretariat/NNP is/VBZ expected/VBN to/TO race/VB tomorrow/NN - People/NNS continue/VBP to/TO inquire/VB the/DT reason/NN for/IN the/DT race/NN for/IN outer/JJ space/NN Đây là một vấn đề rất phức tạp và tồn tại trong hầu như tất cả mọi ngôn ngữ mà ta không thể tránh được, lấy ví dụ như trong tập từ vựng Brown và tập thẻ Brown của nó trong tiếng Anh thì có 35340 từ không có nhập nhằng (tức là một từ chỉ có đúng duy nhất một nhãn trong mọi trường hợp), và 4100 từ chứa nhập nhằng (tức là một từ có thể có từ 2 đến 7 nhãn trong các ngữ cảnh khác nhau) – Kết quả này do Derose tổng kết năm 1988 [abc], chi tiết cho ở bảng 1 dưới đây: Bảng 1. Tổng kết số nhãn có thể có của một từ trong tập từ vựng Brown Số nhãn 1 2 3 4 5 6 7 Số từ 35340 3760 264 61 12 2 1 Nhìn chung, các nhập nhằng từ loại thường được giải quyết bằng cách xét đến ngữ cảnh mà từ đó xuất hiện, tuy nhiên trong một số trường hợp, ngay cả khi có thông tin về ngữ cảnh mà một số từ vẫn còn tiềm tàng nhập nhằng về từ loại. Một vấn đề khác mà bài toán gán nhãn từ loại cần phải xử lý là khi gặp những từ “lạ” mà bộ gán nhãn không thể giải quyết được bằng những cách thông thường. Trong trường hợp này, thường thì hệ thống sẽ để nguyên và đánh dấu một từ loại đặc biệt để chuyển sang phần xử lý tên riêng (proper name) hay từ mới (unknown word) [abc]. 5 1.3. Tập nhãn từ loại Từ loại là những lớp từ có cùng bản chất ngữ pháp, được phân chia theo ý nghĩa khái quát, theo khả năng kết hợp với các từ ngữ khác trong ngữ lưu và thực hiện những chức năng ngữ pháp nhất định ở trong câu (Đinh Văn Đức. Ngữ pháp tiếng Việt – Từ loại [abc]). Trong thực tế, các tập nhãn sử dụng cho việc gán nhãn từ loại thường được xây dựng và phát triển từ các lớp cơ bản là các lớp từ đóng (Closed word class, function word class, còn được gọi là các từ chức năng , là một tập cố định và không thể mở rộng, các lớp này thường chỉ chứa một số lượng ít các từ có liên quan. Ví dụ: giới từ, mạo từ, đại từ, số đếm, ...) và các lớp từ mở (Open class, là các lớp từ có khả năng mở rộng bằng cách tạo thêm từ mới hoặc “mượn” từ các ngôn ngữ khác. Có 4 lớp tử mở chính là danh từ - nouns, động từ - verb, tính từ - adjective và một phần của phó từ - [adverb]). Thường thì một lớp từ sẽ được chia thành nhiều từ loại theo các đặc tính riêng nào đó. Chỉ xét riêng đối với Tiếng Anh, cho đến hiện nay đã có rất nhiều tập nhãn từ loại khác nhau được xây dựng và sử dụng [abc]. Hình 1. Một số tập nhãn từ loại cho Tiếng Anh Có thể kể đến một số tập nhãn từ loại điển hình như: + Brown corpus (Francis, 1979; Francis and Kucera, 1982): 87 nhãn + Penn Treebank (Marcus et al., 1993): 45 nhãn 6 Bảng 2. Tập nhãn từ loại Penn Treebank + Lancaster UCREL C5 (Dùng để gán nhãn BNC – British National Corpus; Garside et al., 1997): 61 nhãn + Lancaster C7: 145 nhãn Việc chọn tập nhãn ảnh hướng rất lớn đến độ khó của bài toán gán nhãn từ loại. Chọn tập nhãn lớn sẽ làm tăng độ khó nhưng tập nhãn nhỏ hơn có thể không đủ đáp ứng cho một mục đích nhất định nào đó. Việc chọn tập nhãn nào sẽ tùy thuộc vào từng ứng dụng cụ thể, nói cách khác là tùy thuộc vào số lượng thông tin mà ứng dụng đó đòi hỏi. Như vậy, cần phải có sự cân đối giữa: • Có được lượng thông tin rõ ràng hơn (Tức là phạm vi phân lớp từ loại nhỏ hơn, chia thành nhiều từ loại hơn dựa trên nhiều yếu tố thể hiện sự khác biệt). • Có khả năng tiến hành thực hiện việc gán nhãn (Tức là số lượng các từ loại càng ít càng dễ tiến hành). 7 Tức là cần phải có một sự thoả hiệp để xây dựng được một bộ nhãn (bộ chú thích, bộ thẻ) từ loại không quá lớn và có chất lượng. Đối với tiếng Việt, việc thiết kế một tập nhãn từ loại còn vấp phải một vấn đề lớn, đó là ngay trong tiếng Việt thì vấn đề từ loại vẫn còn gây nhiều tranh cãi. Theo Diệp Quang Ban [abc], việc phân định từ loại phải dựa trên các tiêu chí sau đây: • Tiêu chuẩn 1 - Ý nghĩa khái quát của từ. Các từ loại là những nhóm từ rất to lớn về khối lượng mà mỗi nhóm có một đặc trưng phân loại: tính vật thể, phẩm chất, hành động hoặc trạng thái … Ví dụ, những từ như: nhà, bàn, học sinh, con, quyển, sự … được phân vào lớp danh từ, vì ý nghĩa từ vựng của chúng đượi khái quát hóa và trừu tượng hóa thành ý nghĩa thực thể - ý nghĩa phạm trù ngữ pháp của danh từ. • Tiêu chuẩn 2 - Khả năng kết hợp với các từ ngữ khác trong ngữ lưu. Với ý nghĩa khái quát, các từ có thể có khả năng tham gia vào một kết hợp có nghĩa. Ở mỗi vị trí của kết hợp có thể xuất hiện những từ có khả năng lần lượt thay thế nhau, trong khi đó, ở các vị trí khác nhau trong kết hợp, các từ còn lại tạo ra bối cảnh cho sự xuất hiện khả năng thay thế của những từ nói trên. Những từ cùng xuất hiện trong cùng một bối cảnh, có khả năng thay thế nhau ở cùng một vị trí, có tình chất thường xuyên, được tập hơn vào một lớp từ. Vận dụng vào tiếng Việt, những từ; nhà, bàn, cát, đá … có thể xuất hiện và thay thế nhau trong kết hợp kiểu: nhàn ày, bàn này, cát này, đá này … và được xếp vào lớp danh từ. Chúng không thể xuất hiện và thay thế cho nhau trong kết hợp kiểu: hãy ăn, hãy mua, ăn xong, mua xong … vốn là kiểu kết hợp của động từ. • Tiêu chuẩn 3 - Chức năng ngữ pháp. Tham gia vào cấu tạo câu, các từ có thể đứng ở một hay một số vị trí nhất định trong câu, hoặc có thể thay thế nhau ở vị trí đó, và cùng biểu thị một mối quan hệ về chức năng cú pháp với các thành phần khác trong cấu tạo câu, có thể phân vào một từ loại. Ví dụ, các từ; nhà, bàn, cát, đá … có thể đứng ở nhiều vị trí trong câu. Chúng có thể thay thế nhau ở những vị trí đó, và có quan hệ về chức năng giống nhau với các thành phần khác trong câu ở mỗi vị trí, nhưng thường ở vị trí chủ ngữ trong quan hệ với vị ngữ. Chủ ngữ và vị ngữlà hai chức năng cú pháp cơ bản, chức năng chủ ngữ là chức năng cú pháp chủ yếu để phân loại các từ nói trên vào lớp danh từ; còn chức năng vị ngữ lại là chức năng cú pháp chủ yếu của các động từ và tính từ … 8 Có hai dạng tập nhãn từ loại thường được sử dụng cho các công cụ gán nhãn từ loại tiếng Việt [abc]: • Loại thứ nhất, xuất phát từ tập gồm 8 nhãn từ loại tiếng Việt thông dụng được các nhà nghiên cứu ngôn ngữ học công nhận nhiều nhất (bao gồm: danh từ, động từ, tính từ, đại từ, phụ từ, kết từ, trợ từ, cảm từ) để xây dựng tập nhãn “mịn” hơn bằng cách phân nhỏ mỗi từ loại trên thành các tiểu từ loại. Việc phân nhỏ này dựa trên nền tảng là các tiểu loại từ được nêu ra trong cuốn Ngữ pháp tiếng Việt của Ủy ban khoa học xã hội Việt Nam, xuất bản năm 1993, có bổ sung thêm một số nhãn từ loại để tránh trường hợp một từ mang cùng một lúc nhiều nhãn từ loại (chẳng hạn động từ ngoại động chỉ cảm nghĩ hay động từ nội động chỉ cảm nghĩ). Tùy thuộc vào từng loại ứng dụng xem cần thông tin cú pháp và từ vựng ở mức nào mà việc xây dựng, xác định tập nhãn từ loại sẽ dừng ở mức thô hay mịn khác nhau. Hiện nay, ở Việt Nam đã có một số tập nhãn từ loại được xây dựng, chủ yếu ở mức thô, tiêu biểu có thể kể đến bộ nhãn VnPOStag của tác giả Trần Thị Oanh gồm 14 nhãn, 01 nhãn không xác định và các nhãn ký hiệu đặc biệt khác; bộ VietTreeBank gồm 16 nhãn và 01 nhãn cho từ không phân loại được, … Bộ nhãn gồm nhiều nhãn nhất hiện nay được xây dựng bởi nhóm tác giả Nguyễn Thị Minh Huyền sử dụng cho công cụ VnQtag gồm 48 nhãn và 01 nhãn không xác định. • Loại thứ hai, tập nhãn tiếng Việt được xây dựng thông qua việc xây dựng kho ngữ liệu song ngữ Anh-Việt mà trong đó các câu tiếng Việt đã được gán nhãn từ loại chính xác nhờ kết quả liên kết từ Anh-Việt và phép chiếu từ loại từ Anh sang Việt. Tiêu biểu là trong nghiên cứu “Gán nhãn từ loại tự động cho Tiếng Việt” của nhóm tác giả Đinh Điền xây dựng tập nhãn quy chiếu từ tập nhãn tiếng Anh Brown Corpus. 1.4. Quá trình gán nhãn từ loại Quá trình gán nhãn từ loại có thể chia làm 3 bước [abc]: • Giai đoạn tiền xử lý: phân tách xâu ký tự thành chuỗi các từ. Giai đoạn này có thể đơn giản hay phức tạp tuỳ theo ngôn ngữ và quan niệm về đơn vị từ vựng. Chẳng hạn đối với tiếng Anh hay tiếng Pháp, việc phân tách từ phần lớn là dựa vào các ký hiệu trắng. Tuy nhiên vẫn có những từ ghép hay những cụm từ gây tranh cãi về cách xử lý. Trong khi đó với tiếng Việt thì dấu trắng càng không 9 phải là dấu hiệu để xác định ranh giới các đơn vị từ vựng do tần số xuất hiện từ ghép rất cao. • Khởi tạo gán nhãn, tức là tìm cho mỗi từ tập tất cả các nhãn từ loại mà nó có thể có. Tập nhãn này có thể thu được từ cơ sở dữ liệu từ điển hoặc kho ngữ liệu đã gán nhãn bằng tay. Đối với một từ mới chưa xuất hiện trong cơ sở ngữ liệu thì có thể dùng một nhãn ngầm định hoặc gắn cho nó tập tất cả các nhãn. Trong các ngôn ngữ biến đổi hình thái người ta cũng dựa vào hình thái từ để đoán nhận lớp từ loại tương ứng của từ đang xét. • Quyết định kết quả gán nhãn, đó là giai đoạn loại bỏ nhập nhằng, tức là lựa chọn cho mỗi từ một nhãn phù hợp nhất với ngữ cảnh trong tập nhãn khởi tạo nói trên. Có nhiều phương pháp để thực hiện việc này, trong đó người ta phân biệt chủ yếu các phương pháp dựa vào quy tắc ngữ pháp mà đại diện nổi bật là phương pháp Brill và các phương pháp xác suất. Ngoài ra còn có các hệ thống sử dụng mạng nơ-ron, các hệ thống lai sử dụng kết hợp tính toán xác suất và ràng buộc ngữ pháp, gán nhãn nhiều tầng. Hình dưới đây cho ta mô hình tổng quát cho bài toán gán nhãn từ loại [abc]: Hình 2. Mô hình tổng quát của bài toán gán nhãn từ loại Hiện nay, bài toán gán nhãn từ loại cho tiếng Anh đã được giải quyết khá tốt, đạt độ chính xác cao (Khoảng hơn 97%), bên cạnh việc hoàn thiện hơn nữa các bộ gán nhãn đã có, ngày càng nhiều bộ gán nhãn mới ra đời, đem lại kết quả tiến gần tới mức tối ưu. Tuy nhiên, đối với các ngôn ngữ khác, đặc biệt là các ngôn ngữ tượng hình (như tiếng Trung Quốc, Nhật, Hàn Quốc …), các ngôn ngữ của Nga, Ấn Độ, A Rập, Thái Lan … cũng như đối với tiếng Việt thì bài toán gán nhãn từ loại vẫn là một thách 10 thức lớn, các phương pháp và công cụ đã được xây dựng gần như hoàn thiện cho Tiếng Anh khi đem áp dụng cho các ngôn ngữ khác loại trên thường đưa lại kết quả thấp hoặc chưa đáp ứng được nhu cầu ứng dụng. Như vậy, yêu cầu đặt ra với từng ngôn ngữ là phải kế thừa, tận dụng được các phương pháp sẵn có, tiến hành hiệu chỉnh hoặc đề xuất ra các hướng tiếp cận mới sao cho phù hợp với đặc điểm riêng của từng ngôn ngữ. 1.5. Ứng dụng của bài toán gán nhãn từ loại • Như đã nói ở phần 1.1, gán nhãn từ loại thuộc vào bước phân tích hình thái trong xử lý ngôn ngữ tự nhiên. Đây là bước tiền xử lý cho các phần tiếp theo trong quá trình xử lý ngôn ngữ tự nhiên như phân tích cú pháp, phân tích ngữ nghĩa, … Hình 3. Các bước xử lý ngôn ngữ tự nhiên • Khi hệ thống văn bản đã được gán nhãn, hay nói cách khác là đã được chú thích từ loại thì nó sẽ được ứng dụng rộng rãi trong các hệ thống tìm kiếm thông tin, trong các ứng dụng tổng hợp tiếng nói, các hệ thống nhận dạng tiếng nói cũng như trong các hệ thống dịch máy. • Một trong những ứng dụng thường được nhắc đến nhiều nhất của gán nhãn từ loại là trong hệ thống dịch máy. Cho đến nay, sau hơn 50 năm phát triển, dịch 11 máy chứng tỏ là một ứng dụng vô cùng thiết thực, đồng thời cũng là một bài toán khá hóc búa đặt ra cho các nhà khoa học trên toàn thế giới. Từ đầu thập niên 1960, các nhà khoa học đã đúc kết lại ba chiến lược dịch máy cơ bản, đó là dịch trực tiếp, dịch thông qua ngôn ngữ trung gian và dịch dựa trên chuyển đổi. Và qua thực tế, chiến lược dịch dựa trên chuyển đổi đã khẳng định được tính hiệu quả và tiềm năng của nó. Trong hệ dịch dựa trên sự chuyển đổi, khối chuyển đổi cây cú pháp (cấu trúc) giữ một vai trò quan trọng, quyết định chất lượng hệ dịch. Khối này phụ thuộc rất lớn vào sự chính xác của quá trình phân tích ở bước trước, trong đó có bộ phận gán nhãn từ loại, giả sử như các từ trong cây cú pháp bị gán nhãn từ loại sai dẫn đến cây cú pháp của câu cũng bị sai. • Gán nhãn từ loại cũng là một bước quan trọng để xây dựng hệ thống hệ thống text-to-speech. • Thành công của việc gán nhãn từ loại tiếng Việt sẽ là cơ sở cho những bước đi tiếp theo trong việc xử lý tiếng Việt, như: xác định ranh giới ngữ (danh ngữ, động ngữ, …), phân tích cú pháp, phân tích ngữ nghĩa, … • … 12 Chương 2. CÁC HƯỚNG TIẾP CẬN BÀI TOÁN GÁN NHÃN TỪ LOẠI Như đã nói ở chương I, bài toán gán nhãn từ loại là một trong những bài toán cơ bản của xử lý ngôn ngữ tự nhiên và được quan tâm từ rất sớm, cùng với đó là sự xuất hiện của rất nhiều phương pháp giải quyết bài toán này, cho đến ngày nay, việc hoàn thiện các phương pháp đã có và xây dựng các phương pháp mới nhằm đạt được kết quả tốt hơn vẫn là mục đích của nhiều nghiên cứu. Sơ đồ dưới đây điểm qua một vài phương pháp cơ bản nổi bật theo thời gian: Hình 4. Một số phương pháp giải quyết bài toán gán nhãn từ loại Theo [abc], hầu hết các thuật toán được sử dụng để giải quyết bài toán gán nhãn từ loại thuộcvào một trong hai loại: gán nhãn dựa trên luật và gán nhãn xác suất. 2.1. Phương pháp gán nhãn thủ công Đây là phương pháp gán nhãn từ loại ra đời sớm nhất, các bộ gán nhãn “sơ khai” đều thực hiện theo phương pháp này. Nội dung chính của phương pháp gán nhãn thủ công (hand-coded) là xây dựng một cơ sở dữ liệu lớn các “luật” được viết bằng tay, vì vậy phương pháp này còn được gọi là phương pháp gán nhãn dựa trên hệ luật. Các luật được xây dựng dựa vào ngữ cảnh chứa từ đang xét nhằm loại bỏ nhập nhằng nếu từ đó có thể có nhiều nhãn từ loại thích hợp, ví dụ, nếu một từ nhập nhằng đang xét đi sau một từ chỉ định thì nó có xu hướng là một danh từ hơn là một động từ. Đại diện tiêu biểu cho nhóm các phương pháp thủ công dựa trên hệ luật này là ENGTWOL (Voutilainen, 1995) [abc]. Về thực chất, phương pháp này dựa trên kỹ thuật hai bước dưới đây: • Bước 1: Xác định cho mỗi từ một danh sách các từ loại có khả năng của nó. 13 Đối với ENGTWOL, việc này được thực hiện mởi một bộ phân tích hình thái hai mức độ (Máy chuyển hữu hạn trạng thái). Ví dụ: Để gán nhãn từ loại cho câu “Pavlov had shown that salivation”, ở bước này, bộ gán nhãn tạo một danh sách tất cả các nhãn có thể cho từng từ như sau: Pavlov: PAVLOV N NOM SG PROPER had : HAVE V PAST VFIN SVO HAVE PCP2 SVOO shown : SHOW PCP2 SVOO SVO SG that : ADV PRON DEM SG DET CENTRAL DEM SG CS salivation: N NOM SG • Bước 2: Sử dụng một danh sách các ràng buộc không có nhập nhằng (các luật nếu-thì), và sử dụng các thông tin về ngữ cảnh để chọn ra một nhãn thích hợp nhất trong số các nhãn có thể. Như vậy, ở bước này, các ràng buộc đóng vai trò như một bộ lọc (Filters). Với ENGTWOL, danh sách các ràng buộc gồm khoảng 1100 ràng buộc. Trên thực tế, mỗi luật trên đều chứa một số lượng lớn các ngoại lệ. Thậm chí ngay cả khi người thiết kế tìm cách giải quyết hết các ngoại lệ mà họ nghĩ đến thì vẫn tồn tại những trường hợp chỉ xuất hiện khi hệ thống được đưa vào thực nghiệm. Hơn nữa, một hệ thống luật dù rất đồ sộ cũng khó có thể bao quát được hết tất cả các trường hợp ngôn ngữ, vì vậy, hiện nay các phương pháp dựa trên luật thường chỉ được sử dụng bằng cách kết hợp bổ sung với các phương pháp khác. Đối với tiếng Việt, nhóm nghiên cứu của Nguyễn Quang Châu [abc] đề xuất một phương pháp gán nhãn từ loại cho TiếngViệt dựa trên văn phong và tính toán xác suất. Nhóm tác giả xây dựng bộ gán nhãn là một hệ thống kết hợp bộ gán nhãn tri-gram và bộ gán nhãn dựa trên văn phong. Văn phong là đặc trưng, cách viết văn riêng của mỗi người, mỗi thể loại văn bản. Phương pháp gán nhãn từ loại dựa trên văn phong thực chất là căn cứ vào cách thể hiện của văn bản trong một ngữ cảnh cụ thể để xác định từ loại cho các từ, điều này bao hàm việc xác định phải đảm bảo các luật văn phạm của 14 các từ trong câu. Mô hình của phương pháp gán nhãn từ loại dựa trên văn phong được mô phỏng như sau: Hình 5. Mô hình của phương pháp gán nhãn từ loại dựa trên văn phong Trong đó, về phương pháp xây dựng hệ thống luật, nhóm tác giả dựa vào JAPE (Java Annotation Patterns Engine) để xây dựng được hệ thống trên 270 luật để xác định cho 48 từ loại (danh từ riêng, đại từ xưng hô, danh từ loại thể, .vv..) Kết quả thử nghiệm tốt nhất với các tập mẫu đã xây dựng đạt tới độ chính xác ~80% nếu chỉ dùng phương pháp gán nhãn bằng xác suất và đạt ~90% nếu dùng phương pháp gán nhãn dựa trên văn phong kết hợp với phương pháp xác suất. 2.2. Các phương pháp học máy Như đã nói ở trên, phương pháp dựa trên luật là một phương pháp thủ công còn tiềm tàng rất nhiều nhập nhằng. Cùng với đó, việc xây dựng một hệ thống trích chọn dựa trên các luật là rất tốn công sức, thông thường để xây dựng một hệ thống như vậy đòi hỏi công sức vài tháng từ một lập trình viên với nhiều kinh nghiệm về ngôn ngữ học. Giải pháp cho các giới hạn này là phải xây dựng một hệ thống bằng cách nào đó có thể “tự học”, điều này sẽ giúp giảm bớt sự tham gia của các chuyên gia ngôn ngữ và làm tăng tính khả chuyển cho hệ thống, các phương pháp như vậy được gọi là các phương pháp học máy. Phần này sẽ xem xét một đại diện tiêu biểu của phương pháp học máy giải quyết nhập nhằng bằng cách sử dụng một bộ dữ liệu huấn luyện để tính toán xác suất của một từ cho sẵn sẽ được gán với một nhãn nào đó trong ngữ cảnh cho trước, vì bản chất đó, họ các phương pháp này còn được gọi là các phương pháp xác suất. 15 Xác suất cho một từ, tức là xác suất mà một nhãn cho trước t là thích hợp với một từ cho trước w được tính bằng công thức: (2.0) Để minh họa cho phương pháp xác suất, phần này sẽ giới thiệu một bộ gán nhãn điển hình sử dụng mô hình Markov ẩn (HMM). Mô hình Markov ẩn [abc] được giới thiệu và nghiên cứu vào cuối những năm 1960 và đầu những năm 1970, cho đến nay nó được ứng dụng nhiều trong nhận dạng tiếng nói, tin sinh học và xử lý ngôn ngữ tự nhiên. HMM lựa chọn một chuỗi nhãn tốt nhất cho toàn bộ câu, thông thường người ta sử dụng thuật toán Viterbi để tìm chuỗi nhãn tốt nhất đó. Mô hình HMM có thể được xây dựng bởi automat hữu hạn trạng thái (probabilistic finite state automata) với các tham số biểu diễn xác suất chuyển trạng thái và xác suất sinh dữ liệu quan sát tại mỗi trạng thái. Các trạng thái trong mô hình HMM được xem là bị ẩn đi bên dưới dữ liệu quan sát sinh ra do mô hình. Quá trình sinh ra chuỗi dữ liệu quan sát trong HMM thông qua một loạt các bước chuyển trạng thái xuất phát từ một trong các trạng thái bắt đầu và dừng lại ở một trạng thái kết thúc. Tại mỗi trạng thái, một thành phần của chuỗi quan sát được sinh ra trước khi chuyển sang trạng thái tiếp theo. Trong bài toán gán nhãn từ loại dữ liệu, ta có thể xem tương ứng mỗi trạng thái với một trong nhãn từ loại: NN, NP, VB ...và dữ liệu quan sát là các từ trong câu. Mặc dù các lớp này không sinh ra các từ, nhưng mỗi lớp được gán cho một từ bất kì có thể xem như là sinh ra từ này theo một cách thức nào đó. Giả sử, với câu đầu vào W (w1, w2,…, wn), ta cần tìm một chuỗi các thẻ tốt nhất cho toàn bộ câu, trong đó mỗi thẻ tương ứng với một từ của câu đầu vào T (t1, t2,…, tn). Bộ gán nhãn sử dụng mô hình HMM sẽ tìm chuỗi các nhãn sao cho giá trị của tích P(Từ |nhãn) * P (nhãn | n nhãn trước đó) là cực đại, tức là thỏa mãn công thức (2.1) (2.1) Sử dụng luật Bayes, P(T|W) được viết theo công thức (2.2) (2.2) Ta đang quan tâm tới việc tìm chuỗi nhãn phù hợp nhất làm cực đại công thức (2.2) nên mẫu số trong tất cả các trường hợp là giống nhau, vì vậy ta có thể loại bỏ nó. Do đó, bài toán trở thành tìm chuỗi các nhãn thỏa mãn công thức (2.3) ( , )( | ) ( ) f t wP t w f w = ˆ ( | )TT argmax P T Wτ∈= ( ) ( | )( | ) ( ) P T P W TP T W P W = 16 (2.3) Áp dụng luật chuỗi xác suất, ta có công thức (2.4) (2.4) Vẫn không có phương pháp hiệu quả để tính xác suất của chuỗi này một cách chính xác, vì nó yêu cầu quá nhiều dữ liệu. Tuy nhiên, xác suất có thể được xấp xỉ bởi một xác suất đơn giản hơn bằng các áp dụng các giả thiết độc lập điều kiện (giả thiết rằng mỗi từ đều là độc lập với các từ khác và đặc tính của một từ chỉ phụ thuộc vào nhãn của nó). Mặc dù các giả thiết này không đúng trong thực tế, nhưng trong thực hành thì việc đánh giá đó có thể được chấp nhận. Ở đây, ta sử dụng giả thiết N-gram để mô hình hóa xác suất chuỗi từ (2.5a) Cụ thể ta dùng mô hình phổ biến nhất là mô hình tri-gram. (2.5b) Đầu tiên, ta làm đơn giản hóa rằng xác suất của một từ thì chỉ phụ thuộc vào nhãn của nó: (2.6) Tiếp theo, ta giả thiết rằng các nhãn phía trước có thể được xấp xỉ bởi 2 nhãn trước và gần nó nhất: (2.7) Vì vậy, công thức (2.1) được biến đổi tương đương với công thức (2.8) dưới đây, ta phải lựa chọn chuỗi nhãn làm cực đại công thức (2.8) này (2.8) Các thành phần thừa số trong công thức (2.8) có thể được tính toán từ tập dữ liệu huấn luyện của mô hình. Chú ý rằng để có thể tránh xác suất bằng 0 ta cần sửa dụng các kỹ thuật làm trơn. ˆ ( ) ( | )TT argmax P T P W Tτ∈= ( ) ( | ) ( | ... ) ( | ... )n i 1 1 i 1 i 1 i i 1 1 i 1 i 1i 1P T P W T P w w t w t t P t w t w t− − − −==∏ ( | ... ) ( | )i 1 1 i 1 i 1 i i iP w w t w t t P w t− − = ( | ... ) ( | )i 1 1 i 1 i 1 i i-2 i-1P t w t w t P t t t− − = ( ) ( | ) ( | )[ ( | )] n n 1 2 1 i i-2 i-1 i i i 3 i 1 P t P t t P t t t P w t = = ∏ ∏ n 1 n i i-1 i=1 P(t ,...,t )= P(t | t )∏ ( ) ( ) ( )1 2 3 2 1 3 2P t ,t ,t = P t | t P t | t 17 Ta có thể mô hình hóa HMM dưới dạng một đồ thị có hướng như sau: Hình 6: Đồ thị có hướng mô tả mô hình HMM Ví dụ, mô hình HMM tiến hành gán nhãn từ loại cho câu “Fed raises interest rates”: Hình 7. Một ví dụ gán nhãn bởi mô hình HMM Như đã nói ở trên, thông thường trong mô hình HMM thuật toán hay được sử dụng là Viterbi, thuật toán này được định nghĩa và mô tả bởi công thức (2.9) và hình 8 dưới đây. (2.9) T1 T2 T3 Tn-1 Tn W1 W 2 W 3 W n-1 W n 18 Hình 8. Thuật toán Viterbi Một trong những bộ gán nhãn tiêu biểu sử dụng phương pháp này là bộ gán nhãn TnT của tác giả Thorsten Brants [abc] sử dụng phương pháp tri-gram, cho kết quả 96.7% với tập nhãn Penn TreeBank và bộ dữ liệu WallStreet. QTAG là một bộ gán nhãn dựa trên mô hình HMM do nhóm nghiên cứu Corpus Research thuộc trường đại học tổng hợp Birmingham phát triển, cung cấp miễn phí cho mục đích nghiên cứu. Một điểm nổi trội của QTAG là dù được xây dựng cho tiếng Anh nhưng nó có thể được huấn luyện để sử dụng cho các ngôn ngữ khác. Nhóm nghiên cứu của tác giả Nguyễn Thị Minh Huyền đã sửa đổi phần mềm này để thích nghi với việc thao tác trên văn bản tiếng Việt, cũng như cho phép sử dụng từ điển từ vựng có thông tin từ loại bên cạnh việc sử dụng kho văn bản đa gán nhãn [abc]. Kết quả thử nghiệm tốt nhất của vnQTag với các tập mẫu đa xây dựng đạt tới độ chính xác ~94% đối với bộ nhãn thứ nhất (9 nhãn từ vựng và 10 nhãn cho các loại kí hiệu), trong khi với bộ nhãn thứ hai chỉ đạt tới ~85% (48 nhãn từ vựng và 10 nhãn cho các loại kí hiệu). Phương pháp xác suất còn được sử dụng để gán nhãn từ loại trong rất nhiều ngôn ngữ khác nhau, ví dụ áp dụng mô hình HMM với tiếng Trung Quốc đạt đến 93.5 % trong nghiên cứu của các tác giả GouDong Zhou và Jian Su [abc]; Hai tác giả Fábio N.Kepler và Marcelo Finger cũng công bố kết quả sử dụng mô hình HMM để gán nhãn từ loại cho tiếng Bồ Đào Nha với kết quả 93.48 % [abc]. JVnTagger là công cụ gán nhãn từ loại tiếng Việt dựa trên Conditional Random Fields và Maximum Entropy. JVnTagger được xây dựng trong khuôn khổ đề tài cấp nhà nước VLSP với dữ liệu huấn luyện khoảng 10.000 câu của Viet Treebank. Thử nghiệm với pháp 5-fold cross validation cho thấy kết quả gán 19 nhãn với CRFs có thể đạt giá trị F1 lớn nhất lài 90.40% và Maxent đạt giá trị F1 lớn nhất là 91.03%. Tuy nhiên, mặc dù tính đến thời điểm hiện tại, đây là một trong những phương pháp gán nhãn theo phương pháp xác suất thông dụng nhất được biết đến nhưng nó vẫn còn tiềm tàng những giới hạn của mình. Trong bài báo “Maximum Entropy Markov Model for Information Extraction and Segmentation”[abc], Adrew McCallum đã đưa ra hai vấn đề mà các mô hình HMM truyền thống nói riêng và các mô hình sinh (generative models) nói chung gặp phải khi gán nhãn cho dữ liệu dạng chuỗi. • Thứ nhất, để có thể tính được xác suất P(T, W) (2.1), thông thường ta phải liệt kê hết các trường hợp có thể của chuỗi T và chuỗi W. Nếu như các chuỗi T có thể liệt kê được vì số lượng các trạng thái là có hạn thì trong nhiều ứng dụng ta không thể nào liệt kê hết được các chuỗi W vì dữ liệu quan sát là hết sức phong phú và đa dạng. Để giải quyết vấn đề này, HMM phải đưa ra giả thiết về sự độc lập giữa các dữ liệu quan sát, đó là dữ liệu quan sát được tại thời điểm i chỉ phụ thuộc trạng thái tại thời điểm đó. Tuy vậy, với các bài toán gán nhãn cho dữ liệu dạng chuỗi, ta nên đưa ra các phương thức biểu diễn các dữ liệu quan sát mềm dẻo hơn như là biểu diễn dữ liệu quan sát dưới dạng các thuộc tính (features) không phụ thuộc lẫn nhau. Ví dụ với bài toán phân loại các câu hỏi và câu trả lời trong một danh sách FAQ, các thuộc tính có thể là bản thân các từ hay độ dài của dòng, số lượng các kí tự trắng, dòng hiện tại có viết lùi đầu dòng hay không, số các kí tự không nằm trong bảng chữ cái, các thuộc tính về các chức năng ngữ pháp của chúng… Rõ ràng những thuộc tính này không nhất thiết phải độc lập với nhau. • Vấn đề thứ hai mà các mô hình sinh gặp phải khi áp dụng vào các bài toán phân lớp dữ liệu dạng chuỗi đó là chúng sử dụng xác suất đồng thời để mô hình hóa các bài toán có tính điều kiện.Với các bài toán này sẽ thích hợp hơn nếu ta dùng một mô hình điều kiện có thể tính toán P (T|W) trực tiếp thay vì P (T, W) như trong công thức (2.1). Ngoài HMM, còn rất nhiều phương pháp xác suất khác có thể sử dụng để giải quyết bài toán gán nhãn từ loại nói chung và bài toán gán nhãn từ loại tiếng Việt nói riêng, nhiều trong số chúng có những ưu điểm giải quyết được các hạn chế của mô hình HMM mà ta đã nói ở trên. Cùng với đó, bên cạnh các phương pháp học máy xác suất, còn có các phương pháp học máy khác, ví dụ phương pháp học máy dựa trên độ đo, mà tiêu biểu là phương pháp SVM. Ở các chương sau sẽ trình bày rõ hơn về 3 20 phương pháp học máy tiêu biểu đã đạt được kết quả khả quan khi áp dụng cho bài toán gán nhãn từ loại ở các ngôn ngữ khác, đó là mô hình Markov cực đại hóa Entropy MEMM, mô hình miền ngẫu nhiên điều kiện CRF và mô hình máy véc tơ hỗ trợ SVM. 2.3. Phương pháp lai Phương pháp lai là phương pháp dựa trên học chuyển đổi (transformation-based learning), đây là một phương pháp học có giám sát, đòi hỏi một tập ngữ liệu đã được gán nhãn.Phương pháp này sử dụng cả hai đặc tính của hai kiến trúc gán nhãn nói trên. Giống như bộ gán nhãn dựa trên luật, nó dựa vào luật để xác định khi một từ nhập nhằng thì nó có khả năng là một nhãn nào nhất. Giống như bộ gán nhãn xác suất, nó có một thành phần học máy để tạo ra các luật một cách tự động từ một bộ dữ liệu huấn luyện đã được gán nhãn trước. Ý tưởng chính của thuật toán này là bắt đầu với một vài giải pháp đơn giản (hoặc tinh vi) cho vấn đề (gọi là “baseline tagging”) và từng bước áp dụng những luật biến đổi (luật chuyển) tối ưu (tìm ra từ tập ngữ liệu huấn luyện đã được đánh dấu chính xác) để dần dần giải quyết vấn đề (tức là chuyển từ nhãn không chính xác sang nhãn chính xác). Quá trình này sẽ dừng lại khi không còn luật chuyển tối ưu nào được lựa chọn hoặc đã hết dữ liệu Hình 9. Mô hình tổng quát của phương pháp lai 21 Thuật toán bao gồm 5 bước • Bước 1: Gán nhãn cho từng từ bằng nhãn thông dụng nhất. • Bước 2: Chọn một phép chuyển có tính quyết định thay thế nhãn đã gán bằng nhán mới mà kết quả đem lại có hệ số đánh giá lỗi thấp hơn (Đánh giá một phép chuyển bằng hệ số đánh giá lỗi thực chất là so sánh nó với “sự thật”). • Bước 3: Áp dụng phép chuyển này cho cả tập huấn luyện. • Bước 4: Thực hiện lại các bước trên • Bước 5: Đưa ra kết quả là một bộ gán nhãn mà nhãn đầu tiên sử dụng unigrams, sau đó áp dụng phép chuyển đã được “học” ở trên theo thứ tự. Ví dụ: Xét từ “race” trong hai câu dưới đây - It is expected to race tomorrow. - The race for outer space. Thuật toán sẽ thực hiện như sau: • Đầu tiên, gán nhãn tất cả các từ “race” là NN (nhãn thường gặp nhất trong tập ngữ liệu Brown corpus). Tức là: “It is expected to race/NN tomorrow” “The race/NN for outer space” • Sau đó, sử dụng luật biến đổi để thay thế các nhãn NN bằng VB cho tất cả các từ “race” mà đứng trước nó là từ được gán nhãn TO. Tức là: “It is expected to race/VB tomorrow” Và “The race/NN for outer space” Ví dụ về một số luật chuyển thường được áp dụng cho phương pháp lai được cho bởi bảng 3. 22 Bảng 3. Ví dụ về một số luật chuyển Đại diện tiêu biểu cho phương pháp này là bộ gán nhãn từ loại Brill’s (được xây dựng bởi Eric Brill) sử dụng cho tiếng Anh, đây là một bộ gán nhãn rất thông dụng vì các ưu điểm của nó như miễn phí, đem lại kết quả khá khả quan (Độ chính xác là 96.6% cho tập ngữ liệu Wall Street Journal). Nhóm các tác giả Ðinh Ðiền, Nguyễn Văn Toàn và Diệp Chí Cường trong nghiên cứu “gán nhãn từ loại tự động cho tiếng Việt” [abc] đã áp dụng thử nghiệm mô hình này với tập nhãn đối chiếu từ tập nhãn Brown corpus của tiếng Anh và cho kết quả bước đầu vào khoảng hơn 80%. 23 Chương 3. BA MÔ HÌNH HỌC MÁY ÁP DỤNG CHO BÀI TOÁN GÁN NHÃN TỪ LOẠI TIẾNG VIỆT Qua khảo sát các phương pháp học máy được áp dụng thành công cho nhiều ngôn ngữ (chủ yếu là khảo sát các phương pháp đã được sử dụng cho 3 ngôn ngữ tiêu biểu là tiếng Anh, tiếng Trung Quốc và tiếng Thái), em nhận thấy có khá nhiều phương pháp học máy có thể áp dụng cho bài toán gán nhãn từ loại Tiếng Việt. Trong khóa luận này, em lựa chọn ba phương pháp học máy điển hình đã cho kết quả khả quan ở nhiều ngôn ngữ và có khả năng đạt kết quả tốt đối với tiếng Việt, đó là MEMM, CRF và SVM. Trong đó MEMM và CRF là các mô hình cải tiến dựa trên mô hình xác suất HMM truyền thống, còn SVM là đại diện đặc trưng cho các phương pháp học máy dựa trên độ đo, cơ sở lý thuyết ở chương này sẽ là nền tảng cho phần thực nghiệm để đưa ra đánh giá về độ chính xác cũng như phù hợp của các phương pháp này với Tiếng Việt. Ở đây, bài toán gán nhãn từ loại được xem là bài toán phân lớp với các lớp chính là các nhãn từ loại đã được xác định trước. 2.1. Mô hình Markov cực đại hóa Entropy (MEMM) Như đã nói ở phần trên, mô hình HMM tuy là một mô hình học máy khá tốt, nhưng nó vẫn còn những mặt hạn chế khó có thể khắc phục. Mô hình Markov cực đại hóa Entropy MEMM (Maximum Entropy Markov Model) do McCallum đề xuất [abc] chính là đáp án cho những vấn đề còn hạn chế của mô hình Markov truyền thống. 2.1.1.Khái niệm mô hình MEMM MEMM là một mô hình cải tiến dựa trên mô hình Markov truyền thống. So với mô hình HMM, MEMM thay thế các xác suất chuyển trạng thái và xác suất sinh quan sát trong HMM bởi một hàm xác suất duy nhất P (Ti|Ti-1, Oi) - xác suất để trạng thái hiện tại là Ti với điều kiện trạng thái trước đó là Ti-1 và dữ liệu quan sát hiện tại là Wi. Mô hình MEMM quan niệm rằng các quan sát đã được cho trước và chúng ta không cần quan tâm đến xác suất sinh ra chúng, điều duy nhất cần quan tâm là các xác suất chuyển trạng thái. So sánh với HMM, ở đây quan sát hiện tại không chỉ phụ thuộc vào trạng thái hiện tại mà còn có thể phụ thuộc vào trạng thái trước đó, điều đó có nghĩa là quan sát hiện tại được gắn liền với quá trình chuyển trạng thái thay vì gắn liền với các trạng thái riêng lẻ như trong mô hình HMM truyền thống. 24 Hình 9: Đồ thị có hướng mô tả một mô hình MEMM Áp dụng tính chất Markov thứ nhất, xác suất P(T|W) có thể tính theo công thức : ∏ = −∗= n t tt WTTPWTPWTP 1 1111 ),|()|()|( (3.1) MEMM coi các dữ liệu quan sát là các điều kiện cho trước thay vì coi chúng như các thành phần được sinh ra bởi mô hình như trong HMM vì thế xác suất chuyển trạng thái có thể phụ thuộc vào các thuộc tính đa dạng của chuỗi dữ liệu quan sát. Các thuộc tính này không bị giới hạn bởi giả thiết về tính độc lập như trong HMM và giữ vai trò quan trọng trong việc xác định trạng thái kế tiếp. Kí hiệu PTi-1(Ti|Wi)=P(Ti|Ti-1,Wi). Áp dụng phương pháp cực đại hóa Entropy (sẽ được đề cập ở phần dưới), McCallum xác định phân phối cho xác suất chuyển trạng thái có dạng hàm mũ như sau: ⎟⎠ ⎞⎜⎝ ⎛= ∑ − − a iiaa ii iiT TWfTWZ WTP i ),(exp ),( 1)|( 1 1 λ (3.2) Ở đây, aλ là các tham số cần được huấn luyện (ước lượng); Z (Wi, Ti) là thừa số chẩn hóa để tổng xác suất chuyển từ trạng thái Ti-1 sang tất cả các trạng thái Ti kề đều bằng 1; fa (Wi, Ti) là hàm thuộc tính tại vị trí thứ i trong chuỗi dữ liệu quan sát và trong chuỗi trạng thái. Mỗi hàm thuộc tính fa (Wi,Ti) nhận hai tham số, một là dữ liệu quan sát hiện tại Wi và một là trạng thái hiện tại Ti. McCallum định nghĩa a=, ở đây b là thuộc tính nhị phân chỉ phụ thuộc vào dữ liệu quan sát hiện tại và Si là trạng thái hiện tại. Sau đây là một ví dụ về một thuộc tính b: Hàm thuộc tính fa (Wi, Ti) xác định nếu b (Wi) xác định và trạng thái hiện tại nhận một giá trị cụ thể nào đó: b(Wi) = 1 nếu dữ liệu quan sát hiện tại là “the” 0 nếu ngược lại T T2 Tn-1 Tn T3 W1 W2 W 3 W n-1 W n 25 Để gán nhãn cho dữ liệu, MEMM xác định chuỗi trạng thái T làm cực đại P(T|W) trong công thức (2.3).Việc xác định chuỗi nhãn T cũng được thực hiện bằng cách áp dụng thuật toán Viterbi như trong HMM. 2.1.2. Nguyên lý cực đại hóa Entropy và mô hình xác suất 2.1.2.1. Nguyên lý cực đại hóa entropy Cực đại hóa Entropy là một nguyên lý cho phép đánh giá các phân phối xác suất từ một tập các dữ liệu huấn luyện. Entropy là độ đo về tính đồng đều hay tính không chắc chắn của một phân phối xác suất. Độ đo Entropy điều kiện của một phân phối mô hình trên “một chuỗi trạng thái với điều kiện biết một chuỗi dữ liệu quan sát” p(y|x) có dạng sau ∑−= yx xyxyx , )|(log*)|(*)(~)( ppppH (3.3) Tư tưởng chủ đạo của nguyên lý cực đại hóa Entropy là ta phải xác định một phân phối mô hình sao cho “phân phối đó tuân theo mọi giả thiết đã biết từ thực nghiệm và ngoài ra không đưa thêm bất kì một giả thiết nào khác”. Điều này có nghĩa là phân phối mô hình phải thỏa mãn mọi ràng buộc được rút ra từ thực nghiệm, và phải gần nhất với phân phối đều. Nói theo ngôn ngữ toán học, ta phải tìm phân phối mô hình p(y|x) thỏa mãn hai điều kiện, một là nó phải thuộc tập P’ (CRF.7) và hai là nó phải làm cực đại Entropy điều kiện (CRF.3). Với P là không gian của tất cả các phân phối xác suất điều kiện,và P’ là tập con của P, P’ được xác định như sau: { }{ }nifEfEPpP ipip ...,3,2,1)()(|' ~ ∈∀=∈= 2.1.2.1.2. Mô hình xác suất fa (Wi,Ti)= 1 nếu b (Wi) =1 và Ti=Ti- 0 nếu ngược lại 26 Theo [6] mô hình xác suất được định nghĩa theo không gian H x T, trong đó H là tập từ có thể và ngữ cảnh từ loại, hoặc còn gọi là “lịch sử”, và T là tập các thẻ có thể có. Xác suất mô hình của lịch sử h cùng với thẻ t được định nghĩa theo công thức 3.4: ∏ = ∏= k j thf j jthp 1 ),(),( αµ (3.4) Trong đó, ∏ là hằng số chuẩn hóa, {µ, α1, … αk} là các tham số mang giá trị dương của mô hình và {f1, …, fk} chính là các đặc trưng, thỏa mãn fj (h,t)∈{0, 1} . Chú ý rằng mỗi tham số aj tương ứng với một đặc trưng fj. Cho trước một tập các từ {w1, …, wn} và một chuỗi thẻ {t1, …, tn} được xem là dữ liệu huấn luyện, ta định nghĩa hi là lịch sử khi dự đoán thẻ ti. Các tham số {µ, α1, … αk} được chọn sao cho làm cực đại likelihood dữ liệu huấn luyện sử dụng p theo công thức 3.5 ∏ ∏∏ = == Π== n i k j thf j n i ii iijthppL 1 1 ),( 1 ),()( αµ (3.5) Mô hình này được xem xét dưới dạng Maximum Entropy, trong đó mục tiêu là cực đại entropy của một phân phối dưới những ràng buộc nhất định. Ở đây, entropy của phân phối p được định nghĩa theo công thức 3.6 ∑ ∈∈ −= τtHh thpthppH , ),(log),()( (3.6) Và các ràng buộc được cho bởi công thức 3.7 kjfEEf ji ≤≤= 1,~ (3.7) Trong đó kỳ vọng đặc trưng của mô hình là 3.8 ),(),( , thfthpEf tHh ji ∑ ∈∈ = τ (3.8) và kỳ vọng đặc trưng quan sát là 3.9 ∑ = = n i iijiii thfthpfE 1 ),(),(~~ (3.9) 27 Trong đó ),(~ ii thp là xác suất của (hi, ti) trong dữ liệu huấn luyện. Vì thế, các ràng buộc này sẽ ép buộc mô hình phải đáp ứng được yêu cầu phù hợp tương ứng giữa các kỳ vọng đặc trưng đó với kỳ vọng đặc trưng quan sát trong dữ liệu huấn luyện. 2.1.3. Hạn chế của mô hình MEMM Trong một số trường hợp đặc biệt, các mô hình MEMM và các mô hình định nghĩa một phân phối xác suất cho mỗi trạng thái có thể gặp phải vấn đề “label bias” [abc]. Vấn đề “label bias” là vấn đề do các trạng thái có phân phối chuyển với entropy thấp (ít đường đi ra) có xu hướng ít chú ý hơn đến quan sát hiện tại, mô hình MEMM gặp phải vấn đề này tức là không xác định được nhánh rẽ đúng, điều này sẽ có ảnh hưởng đến kết quả mà nó đạt được. Năm 1991, Léon Bottou đưa ra hai giải pháp cho vấn đề “label bias”.Giải pháp thứ nhất là gộp các trạng thái và trì hoãn việc rẽ nhánh cho đến khi gặp một quan sát xác định. Đây chính là trường hợp đặc biệt của việc chuyển một automata đa định sang một automata đơn định. Nhưng vấn đề ở chỗ ngay cả khi có thể thực hiện việc chuyển đổi này thì cũng gặp phải sự bùng nổ tổ hợp các trạng thái của automata. Giải pháp thứ hai mà Bottou đưa ra là chúng ta sẽ bắt đầu mô hình với một đồ thị đầy đủ của các trạng thái và để cho thủ tục huấn luyện tự quyết định một cấu trúc thích hợp cho mô hình.Tiếc rằng giải pháp này sẽ làm mất tính đi tính có thứ tự của mô hình, một tính chất rất có ích cho các bài tóan trích chọn thông tin [abc]. Một giái pháp đúng đắn hơn cho vấn đề này là xem xét toàn bộ chuỗi trạng thái như một tổng thể và cho phép một số các bước chuyển trong chuỗi trạng thái này đóng vai trò quyết định với việc chọn chuỗi trạng thái. Điều này có nghĩa là xác suất của toàn bộ chuỗi trạng thái sẽ không phải được bảo tồn trong quá trình chuyển trạng thái mà có thể bị thay đổi tại một bước chuyển tùy thuộc vào quan sát tại đó. 28 2.2. Mô hình trường ngẫu nhiên điều kiện (CRF) Mô hình trường ngẫu nhiên điều kiện CRF (Conditional Random Fields) [abc] được giới thiệu lần đầu vào năm 2001 bởi Lafferty và các đồng nghiệp. Giống như MEMM, CRF là mô hình dựa trên xác suất điều kiện, nó có thể tích hợp được các thuộc tính đa dạng của chuỗi dữ liệu quan sát nhằm hỗ trợ cho quá trình phân lớp. Tuy vậy, khác với MEMM, CRF là mô hình đồ thị vô hướng. Điều này cho phép CRF có thể định nghĩa phân phối xác suất của toàn bộ chuỗi trạng thái với điều kiện biết chuỗi quan sát cho trước thay vì phân phối trên mỗi trạng thái với điều kiện biết trạng thái trước đó và quan sát hiện tại như trong các mô hình MEMM. Bản chất “phân phối điều kiện” và “phân phối toàn cục” của CRF cho phép mô hình này khắc phục được các nhược điểm của những mô hình học máy khác như HMM và MEMM trong việc gán nhãn và phân đoạn các dữ liệu dạng chuỗi mà tiêu biểu là vấn đề ‘label bias’. Phần này sẽ đưa ra định nghĩa CRF, nguyên lý cực đại hóa Entropy – một phương pháp đánh giá phân phối xác suất từ dữ liệu và là cơ sở để chọn các “hàm tiềm năng” cho các mô hình CRF, thuật toán Viterbi cải tiến để tìm chuỗi trạng thái tốt nhất mô tả một chuỗi dữ liệu quan sát cho trước, một số phương pháp để ước lượng các tham số cho mô hình CRF. 2.2.1. Khái niệmCRF Kí hiệu X là biến ngẫu nhiên nhận giá trị là chuỗi dữ liệu cần phải gán nhãn và Y là biến ngẫu nhiên nhận giá trị là chuỗi nhãn tương ứng. Mỗi thành phần Yi của Y là một biến ngẫu nhiên nhận gía trị trong tập hữu hạn các trạng thái S. Trong bài toán gán nhãn từ loại, X có thể nhận giá trị là các câu trong ngôn ngữ tự nhiên (gồm các từ), Y là một chuỗi ngẫu nhiên các nhãn tương ứng với các từ tạo thành câu này và mỗi một thành phần Yi của Y có miền giá trị là tập tất cả các nhãn từ loại có thể (danh từ, động từ, tính từ,...). Cho một đồ thị vô hướng không có chu trình G=(V,E), ở đây V là tập các đỉnh của đồ thị và E là tập các cạnh vô hướng nối các đỉnh đồ thị. Các đỉnh V biểu diễn các thành phần của biến ngẫu nhiên Y sao cho tồn tại ánh xạ một-một giữa một đỉnh và một thành phần của Yv của Y. Ta nói (Y|X) là một trường ngẫu nhiên điều kiện (Conditional Random Field - CRF) khi với điều kiện X, các biến ngẫu nhiên Yv tuân theo tính chất Markov đối với đồ thị G: ))(,,|(),,|( vNYXYPvYXYP vv ∈=≠ ωω ωω (3.10) 29 Ở đây, N(v) là tập tất cả các đỉnh kề với v. Như vậy, một CRF là một trường ngẫu nhiên phụ thuộc toàn cục vào X. Trong các bài toán xử lý dữ liệu dạng chuỗi, G đơn giản chỉ là dạng chuỗi G=(V={1,2,…m},E={(i,i+1)}). Kí hiệu X=(X1, X2,…, Xn), Y=(Y1,Y2, ...,Yn). Mô hình đồ thị cho CRF có dạng: Hình 10: Đồ thị vô hướng mô tả CRF Gọi C là tập hợp tất cả các đồ thị con đầy đủ của đồ thị G - đồ thị biểu diễn cấu trúc của một CRF. Áp dụng kết quả của Hammerley-Clifford [14- Markov fields on finite graphs and lattices. Unpublished manuscript, 1971] cho các trường ngẫu nhiên Markov, ta thừa số hóa được p(y|x) - xác suất của chuỗi nhãn với điều kiện biết chuỗi dữ liệu quan sát- thành tích của các hàm tiềm năng như sau: ∏ ∈ = CA A AP )|()|( xxy ψ (3.11) Vì trong các bài toán xử lý dữ liệu dạng chuỗi đồ thị biểu diễn cấu trúc của một CRF có dạng đường thẳng như trong hình 5 nên tập C phải là hợp của E và V, trong đó E là tập các cạnh của đồ thị G và V là tập các đỉnh của G, hay nói cách khác đồ thị con A hoặc chỉ gồm một đỉnh hoặc chỉ gồm một cạnh của G. 2.2.2. Hàm tiềm năng của các mô hình CRF Lafferty [abc] xác định các hàm tiềm năng cho các mô hình CRF dựa trên nguyên lý cực đại hóa Entropy [abc]. Cực đại hóa Entropy là một nguyên lý cho phép đánh giá các phân phối xác suất từ một tập các dữ liệu huấn luyện. Bằng cách áp dụng nguyên lý cực đại hóa Entropy, Lafferty xác định hàm tiềm năng của một CRF có dạng một hàm mũ. ( ) ( )∑= k kkA AfA xx |exp| γψ (3.12) Yn-1 Y1 X Y3 Y2 Yn 30 Ở đây fk là một thuộc tính của chuỗi dữ liệu quan sát và kγ là trọng số chỉ mức độ biểu đạt thông tin của thuộc tính fk . Có hai loại thuộc tính là thuộc tính chuyển (kí hiệu là t) và thuộc tính trạng thái(kí hiệu là s) tùy thuộc vào A là đồ thị con gồm một đỉnh hay một cạnh của G. Thay các hàm tiềm năng vào công thức (CRF.2) và thêm vào đó một thừa sổ chuẩn hóa Z(x) để đảm bảo tổng xác suất của tất cả các chuỗi nhãn tương ứng với một chuỗi dữ liệu quan sát bằng 1, ta được: ⎟⎠ ⎞⎜⎝ ⎛ += ∑ ∑∑∑ − i i k ikk k iikk stZ P ),(),,(exp )( 1)|( 1 xyxyyx xy µλ (3.13) Ở đây, x,y là chuỗi dữ liệu quan sát và chuỗi trạng thái tương ứng; tk là thuộc tính của tòan bộ chuỗi quan sát và các trạng thái tại ví trí i-1, i trong chuỗi trạng thái; sk là thuộc tính của toàn bộ chuỗi quan sát và trạng thái tại ví trí i trong chuỗi trạng thái. Thừa số chuẩn hóa Z(x) được tính như sau: ∑ ∑ ∑∑∑ ⎟⎠ ⎞⎜⎝ ⎛ += − y i i k ikk k iikk stZ ),(),,(exp)( 1 xyxyyx µλ (3.14) ..),...,,( 2,121 µµλλθ là các vector các tham số của mô hình, teta sẽ được ước lượng giá trị nhờ các phương pháp ước lượng tham số cho mô hình sẽ được đề cập trong phần sau. 2.2.3. Thuật toán gán nhãn cho dữ liệu dạng chuỗi Tại mỗi vị trí i trong chuỗi dữ liệu quan sát, ta định nghĩa một ma trận chuyển |S|*|S| như sau: [ ]),,'()( xx yyMM ii = (3.15) ti = 1 nếu xi-1= “Bill”, xi=”Clinton” và yi-1=B_PER,yi=I_PER 0 nếu ngược lại si = 1 nếu xi=Bill và yi= B_PER 0 nếu ngược lại 31 ⎟⎠ ⎞⎜⎝ ⎛ += ∑ ∑ k k kkkki ysyytyyM ),(),,'(exp),,'( xxx µλ (3.16) Ở đây Mi(y’,y,x) là xác suất chuyển từ trạng thái y’ sang trạng thái y với chuỗi dữ liệu quan sát là x. Chuỗi trạng thái y* mô tả tốt nhất cho chuỗi dữ liệu quan sát x là nghiệm của phương trình: y* = argmax{p(y|x)} (3.17) Chuỗi y* được xác định bằng thuật toán Viterbi cải tiến. Định nghĩa )( yi∂ là xác suất của “chuỗi trạng thái độ dài i kết thúc bởi trạng thái y và có xác suất lớn nhất” biết chuỗi quan sát là x. Hình 11: Một bước trong thuật toán Viterbi cải tiến Giả sử biết tất cả )( ki y∂ với mọi yk thuộc tập trạng thái S của mô hình, cần xác định )(1 ji y+∂ . Từ hình 7, ta suy ra công thức đệ quy ( ) SyyyMyy kjkikiji ∈∀∂=∂ −+ ),,(*)(max)( 11 x (3.18) Đặt ( )),,'(*)'(maxarg)(Pr 1 xyyMyye iii −∂= . Giả sử chuỗi dữ liệu quan sát x có độ dài n, sử dụng kĩ thuật backtracking để tìm chuỗi trạng thái y* tương ứng như sau: • Bước 1: Với mọi y thuộc tập trạng thái tìm o ( ))(maxarg)(* yn n∂=y o i Å n ? )( Ni y∂Prob= yj )( 1yi∂ y1 y2 yN Prob= )( 2yi∂ )(1 ji y+∂ 32 • Bước lặp: chừng nào i>0 o i Å i-1 o y Å Prei(y) o y*(i) = y Chuỗi y* tìm được chính là chuỗi có xác suất p(y*|x) lớn nhất, đó cũng chính là chuỗi nhãn phù hợp nhất với chuỗi dữ liệu quan sát cho trước. Như vậy ,do bản chất phân phối toàn cục của mình, CRF có thể giải quyết được vấn đề ‘label bias’, một nhược điểm tiêu biểu của mô hình MEMM. Ở phương diện lý thuyết mô hình, ta có thể coi mô hình CRF như là một máy trạng thái xác suất với các trọng số không chuẩn hóa, mỗi trọng số gắn liền với một bước chuyển trạng thái. Bản chất không chuẩn hóa của các trọng số cho phép các bước chuyển trạng thái có thể nhận các giá trị quan trọng khác nhau. Vì thế bất cứ một trạng thái nào cũng có thể làm tăng hoặc giảm xác suất được truyền cho các trạng thái sau nó mà vẫn đảm bảo xác suất cuối cùng được gán cho toàn bộ chuỗi trạng thái thỏa mãn định nghĩa về xác suất nhờ thừa số chuẩn hóa toàn cục. 3.2.5.Ước lượng tham số cho các mô hình CRF Kĩ thuật được sử dụng để đánh giá tham số cho một mô hình CRF là làm cực đại hóa độ đo likelihood giữa phân phối mô hình và phân phối thực nghiệm. Giả sử dữ liệu huấn luyện gồm một tập N cặp, mỗi cặp gồm một chuỗi quan sát và một chuỗi trạng thái tương ứng, D={(x(i),y(i))} Ni K1=∀ . Độ đo likelihood giữa tập huấn luyện và mô hình điều kiện tương ứng p(y|x,θ ) là: ∏= yx yxxy , ),(~),|()( ppL θθ (3.19) Ở đây ..),...,,( 2,121 µµλλθ là các tham số của mô hình và ),(~ yxp là phân phối thực nghiệm đồng thời của x,y trong tập huấn luyện. Nguyên lý cực đại likelihood: các tham số tốt nhất của mô hình là các tham số làm cực đại hàm likelihood. )(maxarg θθ θ LML = (3.20) MLθ đảm bảo những dữ liệu mà chúng ta quan sát được trong tập huấn luyện sẽ nhận được xác suất cao trong mô hình. Nói cách khác, các tham số làm cực đại hàm 33 likelihood sẽ làm phân phối trong mô hình gần nhất với phân phối thực nghiệm trong tập huấn luyện. Vì việc tính teta dựa theo công thức (4.1) rất khó khăn nên thay vì tính toán trực tiếp, ta đi xác định teta làm cực đại logarit của hàm likelihood (thường được gọi tắt là log-likelihood): ( )∑= yx xyyx , ),|(log),(~)( θθ ppl (3.21) Vì hàm logarit là hàm đơn điệu nên việc làm này không làm thay đổi giá trị của θ được chọn.Thay p(y|x,θ ) của mô hình CRF vào công thức (4.3), ta có: ∑ ∑∑ ∑ −⎥⎦ ⎤⎢⎣ ⎡ += + = =yx x xstyx , 1 1 1 log*)(~**),(~)( Zppl n i n i µλθ (3.22) Ở đây, ),..,( 21 nλλλλ và ),...,,( 21 mµµµµ là các vector tham số của mô hình, t là vector các thuộc tính chuyển (t1(yi-1,yi,x),t2(yi-1,yi,x),…), s là vector các thuộc tính trạng thái (s1(yi,x),s2(yi,x),…). Hàm log-likelihood cho mô hình CRF là một hàm lõm và trơn trong toàn bộ không gian của tham số. Bản chất hàm lõm của log-likelihood cho phép ta có thể tìm được giá trị cực đại toàn cục θ bằng cách thiết lập các thành phần của vector gradient của hàm log-likelihood bằng không. Mỗi thành phần trong vector gradient của hàm log-likelihood là đạo hàm của hàm log-likelihood theo một tham số của mô hình. Đạo hàm hàm log – likelihood theo tham số kλ ta được: ∑ ∑ = −=∂ ∂ yx xyyyx , 1 1 ),,(),(~ )( n i iik k tplλ θ -∑ ∑ = − x xyyxyx n i iiktpp 1 1 ),,(),|()(~ θ = [ ] [ ]kpkp tEtE ),|(),(~ θxyyx − (3.23) Việc thiết lập phương trình trên bằng 0 tương đương với việc đưa ra một ràng buộc cho mô hình: giá trị trung bình của tk theo phân phối ),|()(~ θxyx pp bằng giá trị trung bình của tk theo phân phối thực nghiệm ),(~ yxp . Như vậy, về phương diện toán học, bài toán ước lượng tham số cho một mô hình CRF chính là bài toán tìm cực đại của hàm log-likelihood. Có nhiều phương pháp tìm cực đại của hàm log-likelihood như các phương pháp lặp (IIS, GIS), các phương pháp 34 tối ưu số (phương pháp dựa trên vector gradient như phương pháp gradient liên hợp, quasi-Newton …) và L-BFGs có thể phục vụ cho ước lượng tham số mô hình. Trong các phương pháp tìm cực trị hàm log-likelihood này, phương pháp L-BFGs được đánh giá là vượt trội và có tốc độ hội tụ nhanh nhất. 2.3. Mô hình máy véc tơ hỗ trợ (SVM) 2.3.1. Khái niệm và cơ sở của phương pháp SVM Phương pháp máy véc tơ hỗ trợ SVM (Support Vector Machine) ra đời từ lý thuyết học thống kê do Vapnik và Chervonekis xây dựng năm 1995 [abc] 11,12 và có nhiều tiềm năng phát triển về mặt lý thuyết cũng như ứng dụng trong thực tế. SVM là một họ các phương pháp dựa trên cơ sở các hàm nhân (kernel) để tối thiểu hóa rủi ro ước lượng.Các thử nghiệm thực tế cho thấy, phương pháp SVM có khả năng phân loại khá tốt đối với bài toán phân lớp cũng như trong nhiều ứng dụng khác (ước lượng hồi quy, nhân dạng chữ viết tay …). Ý tưởng của phương pháp là cho trước một tập huấn luyện được biểu diễn trong không gian vector , trong đó mỗi một văn bản được xem như một điểm trong không gian này. Rõ ràng, có nhiều cách có thể chia không gian này thành hai nửa riêng biệt: Hình 12. Hai cách chia không gian véc tơ thành hai nửa riêng biệt Phương pháp SVM tìm ra một siêu mặt phẳng h quyết định tốt nhất có thể chia các điểm trên không gian này thành hai lớp riêng biệt tương ứng, tạm gọi là lớp âm (-) 35 và lớp dương (+). Chất lượng của siêu mặt phẳng này được quyết định bởi một khoảng cách (được gọi là lề) của điểm dữ liệu gần nhất của mỗi lớp đến mặt phẳng này. Khoảng cách lề càng lớn thì thì xác suất của việc phân lớp sai sẽ là nhỏ, tức là càng có sự phân chia tốt các điểm ra thành hai lớp, như vậy, ta sẽ đạt được kết quả phân lớp tốt. [abc] đưa ra khái niệm bộ phân lớp SVM là mặt siêu phẳng phân tách các mẫu dương khỏi các mẫu âm với độ chênh lệch cực đại, trong đó độ chênh lệch – còn gọi là lề (margin) xác định bằng khoảng cách giữa các mẫu dương và các mẫu âm gần mặt siêu phẳng nhất. Mặt siêu phẳng này được gọi là mặt siêu phẳng lề tối ưu. Tóm lại, mục tiêu của thuật toán SVM là tìm được khoảng cách lề lớn nhất để tạo kết quả phân lớp tốt. Hình dưới đây cho ta mô tả trực quan về phương pháp SVM. Hình 13. Bản chất của mô hình SVM Mặt siêu phẳng tách các mẫu dương khỏi các mẫu âm. Mặc dù bản chất của phương pháp này đã được định nghĩa ở trên, nhưng có rất nhiều phiên bản khác nhau của nó, thường thì miền trong của lề trong tập dữ liệu huấn luyện có thể chứa một lượng nhỏ các điểm, dẫn đến việc sự “thẳng” của siêu phẳng được biến đổi trở thành “không thẳng” bằng cách sử dụng các hàm nhân. Việc phân 36 lớp trong trường hợp mở rộng này cũng tương tự trường hợp cơ sở , dựa trên giá trị âm hoặc dương của đầu ra. 2.3.2. Áp dụng phương pháp SVM cho bài toán gán nhãn từ loại Có thể nói SVM thực chất là một bài toán tối ưu , mục tiêu của thuật toán là tìm được một không gian H và siêu mặt phẳng quyết định h trên H sao cho sai số khi phân lớp là thấp nhất , nghĩa là kết quả phân lớp sẽ cho kết quả tốt nhất . Đối với bài toán gán nhãn từ loại, ta gọi x là ngữ cảnh (một tập các đặc trưng) của mẫu đầu vào đang cần gán nhãn, xi và yi (với i=1, …, l; yi ∈ {1, -1}) lần lượt chỉ ra ngữ cảnh của dữ liệu huấn luyện và lớp tương ứng của nó. 1 ( ) sgn( ( , ) ) l i i i i f x a y K x x b = = +∑ (3.24) , -1 , 1max min- 2 i ii y i i y i b b b = = += (3.25) 1 ( , ) l i j j j i j b a y K x x = = ∑ (3.26) Trong đó, hàm sgn được định nghĩa như sau: sgn(x) = 1 (x ≥ 0) -1 (trong trường hợp ngược lại) Mỗi αi được cố định khi giá trị L(α) trong biểu thức dưới đây được cực đại hóa dưới điều kiện của biểu thức (10) và (11) 1 , 1 1( ) ( , ) 2 l l i i j i j i j i i j L a y y K x xα α α = = = −∑ ∑ (3.27) 0 ( 1,..., )i C i lα≤ ≤ = (3.28) 1 0 l i i i yα = =∑ (3.29) Hàm K trong biểu thức (3.27) được gọi là hàm nhân và rất nhiều dạng của hàm nhân có thể được sử dụng, hình 14 dưới đây mô tả hàm nhân Basis Radial. 37 Đối với bài toán gán nhãn từ loại, hàm đa thức dưới đây thường được sử dụng [abc]: ( , ) ( 1)dK x y x y= • + (3.30) Trong đó C (trong biểu thức(3.28)) và d (trong biểu thức (3.30)) luôn nhận giá trị không đổi và được xác định trong thực nghiệm. Thông thường thì C và d lần lượt được cố định là 1 và 2 cho tất cả các thực nghiệm. Một tập các giá trị xi thỏa mãn α >0 được gọi là véc tơ hỗ trợ, phần biểu thức được tính tổng trong biểu thức (3.24) có thể được tính chỉ sử dụng các vector hỗ trợ. Hình 14. Hàm nhân Basis Radial. Chúng ta thấy rằng SVM là mặt phẳng quyết định chỉ phụ thuộc vào các vector hỗ trợ, khi các điểm khác bị xóa đi thì thuật toán vẫn cho kết quả giống như ban đầu. Chính đặc điểm này làm cho SVM khác với các thuật toán khác như kNN , LLSF , Nnet , NB vì tất cả dữ liệu trong tập huấn luyện đều được dùng để tối ưu hóa kết quả. Một vấn đề được đặt ra là, phương pháp SVM có thể chia dữ liệu làm hai lớp, tuy nhiên đối với bài toán gán nhãn từ loại cho dữ liệu văn bản, số lớp tương ứng với số từ loại mà ta cần xác định luôn lớn hơn hai, vậy liệu phương pháp SVM có phù hợp để giải quyết bài toán gán nhãn từ loại hay không?. Để giải quyết vấn đề này. thường thì dữ liệu với hơn hai lớp sẽ được xử lý bằng phương pháp pair-wise, tức là với dữ liệu 38 chứa N lớp, ta sẽ xây dựng tất cả các cặp của hai lớp khác nhau, tổng số sẽ là N(N-1)/2 cặp. Từng lớp tốt hơn trong một cặp hai lớp sẽ được xác định bằng cách sử dụng bộ phân lớp 2 lớp, cuối cùng, lớp chính xác sẽ được xác định dựa trên cơ sở đánh giá kết quả của N(N-1)/2 bộ phân lớp 2-lớp nói trên. 2.3.3. Huấn luyện SVM Huấn luyện SVM thực chất là việc giải bài toán quy hoạch toàn phương SVM. Các phương pháp số giải bài toán quy hoạch này yêu cầu phải lưu trữ một ma trận có kích thước bằng bình phương của số lượng mẫu huấn luyện. Trong những bài toán thực tế, điều này là không khả thi vì thông thường kích thước của tập dữ liệu huấn luyện thường rất lớn (có thể lên tới hàng chục nghìn mẫu). Nhiều thuật toán khác nhau được phát triển để giải quyết vấn đề nêu trên. Những thuật toán này dựa trên việc phân rã tập dữ liệu huấn luyện thành những nhóm dữ liệu. Điều đó có nghĩa là bài toán quy hoạch toàn phương lớn được phân rã thành các bài toán quy hoạch toàn phương với kích thước nhỏ hơn. Sau đó, những thuật toán này kiểm tra các điều kiện KKT [abc] để xác định phương án tối ưu. Một số thuật toán huấn luyện dựa vào tính chất được nêu bởi công thức (3.29) ở phần trên: nếu trong tập dữ liệu huấn luyện của bài toán quy hoạch toàn phương con cần giải ở mỗi bước có ít nhất một mẫu vi phạm các điều kiện KKT, thì sau khi giải bài toán này, hàm mục tiêu sẽ tăng. Như vậy, một chuỗi các bài toán quy hoạch toàn phương con với ít nhất một mẫu vi phạm các điều kiện KKT được đảm bảo hội tụ đến một phương án tối ưu. Do đó, ta có thể duy trì một tập dữ liệu làm việc đủ lớn có kích thước cố định và tại mỗi bước huấn luyện, ta loại bỏ và thêm vào cùng một số lượng mẫu. Một trong những phương pháp tiêu biểu là thuật toán huấn luyện SVM tối ưu hóa tuần tự cực tiểu (Sequential Minimal Optimization - SMO) [abc] dựa vào lý thuyết Lagrange để giải bài toán quy hoạch toàn phương. Thuật toán này sử dụng tập dữ liệu huấn luyện (còn gọi là tập làm việc) có kích thước nhỏ nhất bao gồm hai hệ số Lagrange. Bài toán quy hoạch toàn phương nhỏ nhất phải gồm hai hệ số Lagrange vì các hệ số Lagrange phải thỏa mãn ràng buộc đẳng thức (3.29). Phương pháp SMO cũng có một số heuristic cho việc chọn hai hệ số Lagrange để tối ưu hóa ở mỗi bước. Mặc dù có nhiều bài toán quy hoạch toàn phương con hơn so với các phương pháp khác, mỗi 39 bài toán con này được giải rất nhanh dẫn đến bài toán quy hoạch toàn phương tổng thể cũng được giải một cách nhanh chóng. 40 Chương 4. THỰC NGHIỆM VÀ ĐÁNH GIÁ 4.1. Môi trường thực nghiệm 4.1.1. Phần cứng Máy tính cá nhân Celeron R, Chip 3.06 GHz, Ram 1GB 4.1.2. Phần mềm Sử dụng các công cụ dưới đây để tiến hành thực nghiệm gán nhãn từ loại tiếng Việt: • Thực nghiệm gán nhãn từ loại tiếng việt sử dụng mô hình Markov cực đại hóa Entropy bằng hệ thống tích hợp mô hình tách từ và gán nhãn từ loại tiếng Việt được xây dựng bởi tác giả Trần Thị Oanh, phòng thí nghiệm các hệ tích hợp thông minh, trường đại học Công nghệ, đại học Quốc gia Hà nội, năm 2008. • Thực nghiệm gán nhãn từ loại tiếng việt sử dụng mô hình miền ngẫu nhiên điều kiện CRF bằng công cụ CRF++ xây dựng bởi tác giả người Nhật Taku Ku được cung cấp miễn phí tại địa chỉ Công cụ được viết bằng C++, bản cập nhật mới nhất ngày 06 tháng 05 năm 2009. • Thực nghiệm gán nhãn từ loại tiếng việt sử dụng mô hình máy véc tơ hỗ trợ SVM dựa trên công cụ SVMmulticlass. Đây là một công cụ phát triển từ công cụ SVMlight, được xây dựng bởi tác giả Thorsten Joachims (Department of Computer Science, Cornell University). Công cụ được cung cấp miễn phí tại địa chỉ bản cập nhật mới nhất là version 2.20 ngày 14 tháng 8 năm 2008. • Xây dựng các công cụ trợ giúp bằng ngôn ngữ C++ và Delphi, bao gồm o Chuẩn hóa dữ liệu theo định dạng phù hợp o Mã hóa dữ liệu theo yêu cầu của hệ thống gán nhãn o Áp dụng đặc trưng chuẩn hóa biểu thức chính quy 41 o Xây dựng từ điển để hỗ trợ trích chọn đặc trưng o Trích chọn đặc trưng về thông tin từ vựng và thông tin nhãn từ loại o Đánh giá độ chính xác của kết quả 4.1.3. Dữ liệu thực nghiệm và tập nhãn từ loại Để áp dụng thực nghiệm ba phương pháp học máy MEMM, CRF và SVM, ở đây em sử dụng hai bộ dữ liệu riêng biệt được với hai tập nhãn khác nhau để huấn luyện và kiểm thử nhằm tăng tính khách quan cho kết quả đạt được. Hai bộ dữ liệu đều được thu thập từ các báo điện tử có uy tín ở Việt Nam và bao gồm nhiều văn bản thuộc các chủ đề khác nhau như Công nghệ thông tin, Kinh tế, Chính trị, Xã hội, Pháp luật, Đời sống … • Bộ dữ liệu thứ nhất, được xây dựng bởi nhóm các tác giả [abc]: Gồm 142 văn bản, tương ứng với khoảng hơn 10.000 câu và khoảng 230.000 từ. Bộ dữ liệu này được gán nhãn từ loại bằng tập nhãn từ loại VTB (Viet Tree Bank) gồm 16 nhãn từ loại, 1 nhãn cho từ không gán nhãn được và 1 nhãn cho ký hiệu đặc biệt. Bảng 4. Tập nhãn từ loại Viet Tree Bank cho tiếng Việt STT Tên nhãn Ý nghĩa của nhãn 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ừ 6 A Tính từ 7 P Đại từ 42 8 L Định từ 2 9 M Số từ 10 R Phó từ 11 E Giới từ 3 (kết từ chính phụ) 12 C Liên kết từ (kết từ đẳng lập) 13 I Thán từ 14 T Trợ từ, tình thái từ (tiểu từ) 4 15 B Từ tiếng nước ngoài (hay từ vay mượn) 16 Y Từ viết tắt 17 X Các từ không phân loại được 18++ Ký hiệu Các ký hiệu đặc biệt khác (?, /, #, $ …) • Bộ dữ liệu thứ hai được xây dựng bởi nhóm tác giả Trần Thị Oanh, gồm 780 văn bản, tương ứng với khoảng 8000 câu và khoảng 150.000 từ. Bộ dữ liệu này được gán nhãn từ loại bằng tập nhãn VnPOS gồm 13 nhãn từ loại, 1 nhãn cho các từ không thể gán nhãn và các nhãn ký hiệu đặc biệt. Bảng 5. Tập nhãn từ loại VnPOS cho tiếng Việt STT Tên nhãn Ý nghĩa của nhãn 1 NN Danh từ thường 2 NC Danh từ chỉ loại 3 NP Danh từ riêng 4 VB Động từ 5 JJ Tính từ 43 6 PP Đại từ 7 D Định từ và số từ 8 AD Phụ từ 9 IN Giới từ 10 CC Liên từ 11 UH Thán từ 12 RB Trợ từ 13 TN Thành ngữ 14 X Các từ không thể gán nhãn được 15++ Ký hiệu Các ký hiệu đặc biệt khác (#, ^, &, …) Trong nội dung của khóa luận này, dữ liệu đã được qua bước tiền xử lý, tức là đã được tách từ, quy chuẩn theo đúng định dạng cần thiết và đã được gán nhãn sẵn để phục vụ cho quá trình học có giám sát. Các nhãn sẽ được xác định bằng cách viết hoa và đi liền (cách một dấu cách) hoặc phân cách với từ mà nó xác định bằng dấu “/” hay “//”, quy tắc ký hiệu này có thể thay đổi một cách dễ dàng tuy thuộc vào yêu cầu sử dụng dữ liệu. Dưới đây là hai ví dụ về hai câu đã được gán nhãn ở hai bộ dữ liệu nói trên: • Một câu ví dụ ở bộ dữ liệu thứ nhất: Một/M buổi/N trưa/N đang/R ngồi/V chờ/V khách/N ở/E bến/N Đinh_Bộ_Lĩnh/Np ,/, tôi/P thấy/V một/M đồng_nghiệp/N già/A móc/V trong/E bao/N nilông/N ra/V một/M quyển/Nc giáo_trình/N đại_học/N môn/N Triết_học/N Mác/Np - /- Lênin/Np ./. • Một câu ví dụ ở bộ dữ liệu thứ hai: Tờ//NC Wall_Street_Journal//NP ghi//VB lời//NC phát_biểu//VB của//IN Tổng_Giám_đốc//NN kiêm//VB Giám_đốc_điều_hành//NN Mazda//NP ,//, Hisakazu_Imaki//NP ://: Chúng_tôi//PP sẽ//AD đảm_nhiệm//VB vai_trò//NN 44 phát_triển//VB nền_tảng//NN kiến_trúc//NN cho//IN các//D thế_hệ//NN xe//NN Ford//NP hạng//NC nhỏ//JJ trong//IN tương_lai//NN .//. Nhìn chung cả hai tập nhãn đều mới được xây dựng ở mức thô, nhưng tạm thời trong các yêu cầu trước mắt thì số lượng nhãn là đủ đáp ứng yêu cầu thực nghiệm để đối chiếu, so sánh kết quả đạt được khi sử dụng các mô hình học máy khác nhau cho bài toán gán nhãn từ loại. 4.2. Thiết kế tập đặc trưng Lựa chọn các thuộc tính từ tập dữ liệu huấn luyện là nhiệm vụ quan trọng nhất, giữ vai trò quyết định chất lượng của một hệ thống gán nhãn từ loại. Các thuộc tính được lựa chọn càng tinh tế thì độ chính xác của hệ thống càng tăng. Do tiếng Việt còn tiềm tàng nhiều nhập nhằng chưa được giải quyết, bản thân ngữ pháp tiếng Việt cũng còn những điểm tranh cãi thiếu thống nhất, nên để có thể đạt được độ chính xác gần với độ chính xác đạt được với các hệ thống xây dựng cho tiếng Anh cần phải lựa chọn các thuộc tính một cách cẩn thận và hợp lý. 4.2.1. Các đặc trưng dựa vào thông tin từ vựng và thông tin từ loại Các thuộc tính tại vị trí i trong chuỗi dữ liệu quan sát gồm hai phần, một là thông tin ngữ cảnh tai vị trí i của chuỗi dữ liệu quan sát, một là phần thông tin về nhãn tương ứng. Công việc lựa chọn các thuộc tính thực chất là chọn ra các mẫu vị từ ngữ cảnh (context predicate template), các mẫu này thể hiện những các thông tin đáng quan tâm tại một vị trí bất kì trong chuỗi dữ liệu quan sát. Áp dụng các mẫu ngữ cảnh này tại môt vị trí trong chuỗi dữ liệu quan sát cho ta các thông tin ngữ cảnh (context predicate) tại vị trí đó. Mỗi thông tin ngữ cảnh tại i khi kết hợp với thông tin nhãn tương ứng tại vị trí đó sẽ cho ta một thuộc tính của chuỗi dữ liệu quan sát tại i. Như vậy một khi đã có các mẫu ngữ cảnh, ta có thể rút ra được hàng nghìn thuộc tính một cách tự động từ tập dữ liệu huấn luyện. [abc] Xét một cửa sổ trượt với kích cỡ bằng 5 trượt dọc theo dữ liệu đang xét như ví dụ trong hình 14. Thông tin từ vựng và thông tin từ loại sử dụng cho việc lựa chọn đặc trưng cho MEMM, CRF và SVM được cho trong bảng sau: 45 Bảng 6. Thông tin từ vựng và thông tin từ loại sử dụng cho việc lựa chọn đặc trưng Loại Ký hiệu Giải thích Thông tin từ vựng w-2, w-1, w0, w1, w2 wi cho biết dữ liệu quan sát được tại vị trí thứ i trong chuỗi đầu vào (chuỗi đầu vào được coi là chuỗi nằm trong cửa số trượt với kích cỡ 5). Trong đó wi là dữ liệu quan sát được ngay tại vị trí hiện tại. Thông tin nhãn từ loại t-2, t-1 ti cho biết nhãn của từ tại vị trí thứ i trong chuỗi đầu vào. Hình 14. Cửa sổ trượt với kích cỡ size=5 chuyển động dọc theo dữ liệu Thông tin ngữ cảnh còn được gọi là lịch sử h, thông tin về nhãn ta ký hiệu là t, xác suất đồng thời của lịch sử h và thông tin về nhãn được xác định bằng các tham số mà các đặc trưng tương ứng của nó là ữu ích, ví dụ αi thỏa mãn fi(h,t) = 1. Khi cho trước (h, t), một đặc trưng phải tồn tại trên bất cứ từ nào hoặc nhãn nào trong lịch sử h, và phải chứa thông tin giúp dự đoán thẻ t, ví dụ như thông tin chính tả của từ hiện tại, hoặc thông tin về hai thẻ trước từ hiện tại. Ngữ cảnh từ và nhãn xác định đối với một đặc trưng được cho bằng định nghĩa của lịch sử h, như công thức , , , , , , ,{ }i i i 1 i 2 i 1 i 2 i 1 i 2h w w w w w t t+ + − − − −= (4.1) Ví dụ: Áp dụng mẫu ngữ cảnh trên tại vị trí 1 trong chuỗi “3000 đồng” ta được ngữ cảnh w0:đồng. Giả sử trong dữ liệu huấn luyện, từ đồng trong chuỗi dữ liệu trên được gán nhãn Nu (Với Nu là nhãn danh từ đơn vị trong tập nhãn Viet Tree Bank), kết hợp với ngữ cảnh ta có thể rút ra được một thuộc tính của chuỗi dữ liệu quan sát là 46 fi(h,t) = 1 nếu từ hiện tại là ‘đồng’ và nhãn là Nu 0 nếu ngược lại Ngoài ra còn phải quan tâm đến mẫu ngữ cảnh thể hiện đặc điểm của từ: • Từ đang xét có phải là dấu câu hay ký tự đặc biệt? • Từ đang xét có phải từ đầu tiên của câu ? • Từ đang xét có ký tự đầu của mỗi hình vị là viết hoa hay không ? 4.2.2. Mẫu ngữ cảnh dạng regular expression Các mẫu ngữ cảnh biểu thức chính quy có tác dụng hỗ trợ xác định nhãn từ loại một các nhanh chóng và chính xác hơn. Trong nhiều trường hợp nếu chỉ dựa vào thông tin về từ và từ loại của các từ trước và sau từ đang xét thì có thể gặp phải nhập nhằng làm ảnh hưởng đến kết quả của hệ thống, trong khi đó nếu dựa vào các mẫu ngữ cảnh biểu thức chính quy thì sẽ xác định được ngay các nhãn từ loại. Bảng dưới đây là một ví dụ cho các mẫu ngữ cảnh biểu thức chính quy xác định dữ liệu có dạng số: Bảng 7. Một số mẫu ngữ cảnh BTCQ xác định dữ liệu dạng số Mẫu ngữ cảnh Ví dụ Ý nghĩa ^[0-9]* 123456 Số ^[0-9]+/[0-9]+/[0-9]+$ 12/04/2005 Ngày tháng ^[0-9]+/[0-9]+$ 22/5 Ngày tháng hoặc phân số ^[0-9][0-9][0-9][0-9]$ 2005 Năm ^[0-9]đồng$ ^[0-9]USD$ 10000 đồng 30 USD Tiền tệ ^[0-9]%$ 7% Phần trăm 47 … … … 4.3. Hệ thống gán nhãn từ loại cho tiếng Việt Sử dụng các phương pháp học máy MEMM, CRF và SVM, bài toán gán nhãn từ loại được xem là bài toán phân lớp với các lớp chính là các nhãn từ loại đã được xác định trước. Trong phần này, ta quan tâm tới kiến trúc đường ống (pipeline), tức là việc gán nhãn từ loại được thực hiện sau khi đã có thông tin về từ vựng. Kiến trúc tổng thể của mô hình gán nhãn từ loại sẽ được sử dụng trong thực nghiệm được thể hiện trong hình Hình 15. Một mô hình gán nhãn từ loại tiếng Việt Trong đó, có hai pha chính là pha huấn luyện mô hình và pha kiểm thử sử dụng mô hình. • Pha huấn luyện mô hình: Đầu vào là văn bản đã được tách từ, đưa qua bộ trích chọn đặc trưng (cách thiết kế tập đặc trưng hữu ích cho tiếng Việt sẽ được trình 48 bày ở phần sau) rồi đưa vào mô hình học máy để huấn luyện. Ta sẽ sử dụng MEMM, CRF hoặc SVM để huấn luyện mô hình ở bước này. • Pha giải mã: Văn bản đầu vào sẽ được qua pha giải mã theo thuật toán phù hợp, ví dụ như thuật toán beam search [abc], kết quả sẽ cho ra chuỗi thẻ tốt nhất tương ứng với dữ liệu đầu vào (chuỗi nhãn gồm các nhãn thuộc tập nhãn được chọn) Có thể tiến hành gán nhãn từ loại theo hai hướng tiếp cận: • Hướng tiếp cận dựa trên mức từ • Hướng tiếp cận dựa trên mức hình vị 4.3.1. Gán nhãn từ loại dựa vào thông tin từ Phương pháp Ratmaparkhi giả thiết rằng một câu đã được tách từ trước và gán nhãn từ loại dựa trên mức từ sử dụng các đặc trưng ngữ cảnh xung quanh từ đang xét. Các mẫu đặc trưng được mô tả như ở dưới đây, trong đó W đề cập tới từ còn POS đề cập tới nhãn từ loại của từ. Từ Wi (i = -2, -1, 0, 1, 2) Thẻ của từ đằng trước từ hiện tại POS(W-1) Hai thẻ hai hai từ đằng trước từ hiện tại POS(W-2) POS(W-1) Bảng dưới đây mô tả các đặc trưng dùng cho gán nhãn từ loại tiếng Việt ở mức từ dưới dạng Unigram Bảng 8. Các đặc trưng sử dụng cho gán nhãn từ loại biểu diễn dưới dạng Unigram # Unigram U00:%x[-2,0] //(Thông tin về từ của từ trước từ hiện tại 2 từ) U01:%x[-1,0] //(Thông tin về từ của từ trước từ hiện tại 1 từ) 49 U02:%x[0,0] //(Thông tin về từ của từ hiện tại) U03:%x[1,0] //(Thông tin về từ của từ sau từ hiện tại 1 từ) U04:%x[2,0] //(Thông tin về từ của từ sau từ hiện tại 2 từ) U10:%x[-2,1] //( Thông tin về nhãn từ loại của từ trước từ hiện tại 2 vị trí) U11:%x[-1,1] //( Thông tin về nhãn từ loại của từ trước từ hiện tại 1 vị trí) U05:%x[-1,0]/%x[0,0] //(Từ trước từ hiện tại một từ và từ hiện tại) U06:%x[0,0]/%x[1,0] //(Từ hiện tại và từ sau từ hiện tại một từ) Hướng tiếp cận gán nhãn từ loại ở mức hình vị dựa trên đặc điểm của tiếng Việt là các từ được cấu thành từ các hình vị. Trong tiếng việt, hình vị nhỏ nhất là “tiếng” được hình thành bởi nhiều ký tự trong bảng chữ cái . 4.3.2. Gán nhãn từ loại dựa vào thông tin hình vị Dưới đây là mô tả đặc trưng dựa trên hình vị: Hình vị S-i (i = -2, -1, 0, 1, 2) Đối với hướng tiếp cận này, đặc trưng về thông tin thẻ từ loại của hình vị được biểu diễn là Thẻ của hình vị đằng trước hình vị hiện tại B(S-1Wo)POS(S-1Wo) Thẻ của 2 hình vị đằng trước hình vị hiện tại B(S-2Wo)POS(S-2Wo)B(S-1Wo)POS(S- 1Wo) B là thông tin về từ, là B (Begin_of_word) hoặc là I (Inner_Of_Word), còn POS là thông tin về từ loại của hình vị đang xét đó. 50 4.4. Phương pháp thực nghiệm và các tham số đánh giá thực nghiệm 4.4.1. Phương pháp thực nghiệm Hệ thống được thử nghiệm theo phương pháp “5-fold cross validation”. Theo phương pháp này, dữ liệu thực nghiệm được chia thành 5 phần bằng nhau, lần lượt lấy 4 phần để huấn luyện và 1 phần còn lại để kiểm tra, kết quả sau 5 lần thực nghiệm được ghi lại và đánh giá tổng thể. Một yêu cầu cơ bản và đặc biệt quan trọng cần phải được đảm bảo là việc huấn luyện các mô hình MEMM, CRF và SVM phải được thực hiện trên cùng một môi trường phần cứng, sử dụng một tập đặc trưng, điều này đảm bảo cho sự so sánh kết quả là khách quan và chính xác. Ta sẽ đánh giá chủ yếu dựa trên kết quả trung bình có được từ kết quả của 5 lần thực nghiệm, ngoài ra sẽ phân tích kết quả một cách rõ ràng hơn ở lần thực nghiệm cho kết quả tốt nhất. 4.4.2. Các tham số đánh giá thực nghiệm Có 3 yếu tố quan trọng thường được dùng để đánh giá độ “tốt” của một hệ thống gán nhãn từ loại tiếng Việt • Độ chính xác của kết quả (tức là dữ liệu đầu ra của mô hình). Đây là một trong những yếu tố quan trọng nhất cần phải xem xét để đánh giá độ tốt của một mô hình. Đối với các thực nghiệm đã được tiến hành, độ chính xác của dữ liệu đầu ra được tính bằng công thức correctpre correct incorrect = + • Thuật toán sử dụng để phân loại phải có thời gian xử lý hợp lý, thời gian này bao gồm: thời gian huấn luyện, thời gian kiểm thử (tức là thời gian mà mô hình đã được tạo ra sau bước huấn luyện tiến hành gán nhãn cho dữ liệu kiểm thử). Ở đây ta ký hiệu thời gian huấn luyện là T (tính bằng đơn vị giây) và thời gian kiểm thử là t (tính bằng đơn vị giây), ở đây thời gian kiểm thử được tính bằng thời gian từ lúc mô hình bắt đầu gán nhãn cho dữ 51 liệu kiểm thử đến lúc đầu ra được in ra file một cách hoàn chỉnh (thời gian in ra file đầu ra có các định dạng không quá khác nhau sẽ không chênh lệch nhiều).. • Ngoài ra thuật toán này phải có tính tăng cường (incremental function) nghĩa là không gán nhãn lại toàn bộ tập văn bản khi thêm một số từ mới vào tập dữ liệu mà chỉ gán nhãn cho các từ mới đó, như vậy thuật toán phải có khả năng giảm độ nhiễu (noise) khi tiến hành gán nhãn từ loại. 4.5. Kết quả thực nghiệm Các mô hình học máy MEMM, CRF và SVM đã được huấn luyện trên cùng một môi trường phần cứng và sử dụng cùng một tập đặc trưng như đã được thiết kế ở phần trước. 4.5.1. Kết quả của 05 lần thực nghiệm 4.5.1.1. Thực nghiệm với bộ dữ liệu thứ nhất Bộ dữ liệu thứ nhất gồm 142 văn bản, tương ứng với khoảng hơn 10.000 câu và khoảng 230.000 từ được gán nhãn từ loại bằng tập nhãn từ loại VTB (Viet Tree Bank) gồm 16 nhãn từ loại, 1 nhãn cho từ không gán nhãn được và các nhãn cho ký hiệu đặc biệt. • Thực nghiệm ở mức từ: Bảng 9. Mô tả bộ dữ liệu thứ nhất trong thực nghiệm ở mức từ Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình Dữ liệu train (token/câu) 170,161 7,775 178,818 8,503 177,994 8,323 177,024 8,407 179,115 8,439 176,622 8,289 Dữ liệu test (token/câu) 50,617 2,569 41,960 1,858 42,784 2,038 43,754 1,954 41,663 1,922 44,157 2,068 52 Bảng 11. Kết quả thực nghiệm mức từ với bộ dữ liệu thứ nhất sử dụng mô hình MEMM Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình T (s) t (s) P (%) Bảng 12.Kết quả thực nghiệm mức từ với bộ dữ liệu thứ nhất sử dụng mô hình CRF T (s) 14,825.36 16,412.65 16,951.23 15,701.11 17,565.25 16,291.12 t (s) 1.45 1.91 2.24 2.16 2.54 2.06 P (%) 90.01 91.02 90.87 90.36 89.56 90.36 Bảng 13.Kết quả thực nghiệm mức từ với bộ dữ liệu thứ nhất sử dụng mô hình SVM Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình T (s) t (s) P (%) • Thực nghiệm ở mức hình vị: Bảng 14. Mô tả bộ dữ liệu thứ nhất trong thực nghiệm ở mức hình vị Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình Dữ liệu train (token/câu) 204,104 7,775 214,969 8,503 214,391 8,323 213,246 8,407 215,182 8,439 212,378 8,289 Dữ liệu test (token/câu) 61,369 2,569 52,504 1,858 51,082 2,038 52,227 1,954 50,291 1,922 53,495 2,068 53 Bảng 15. Kết quả thực nghiệm mức hình vị với bộ dữ liệu thứ nhất sử dụng mô hình MEMM Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình T (s) t (s) P (%) Bảng 16. Kết quả thực nghiệm mức hình vị với bộ dữ liệu thứ nhất sử dụng mô hình CRF Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình T (s) 15,125.45 17,056.91 17,563.01 16,174.81 17,968.32 16,777.70 t (s) 0.93 2.05 1.76 1.15 1.34 1.45 P (%) 90.52 91.88 91.49 90.97 90.43 91.06 Bảng 17. Kết quả thực nghiệm mức hình vị với bộ dữ liệu thứ nhất sử dụng mô hình SVM Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình T (s) t (s) P (%) 4.5.1.2. Thực nghiệm với bộ dữ liệu thứ hai Bộ dữ liệu thứ hai gồm 780 văn bản, tương ứng với khoảng 8000 câu và khoảng 150.000 từ được gán nhãn từ loại bằng tập nhãn VnPOS gồm 13 nhãn từ loại, 1 nhãn cho các từ không thể gán nhãn và các nhãn ký hiệu đặc biệt. • Thực nghiệm ở mức từ 54 Bảng 18. Mô tả bộ dữ liệu thứ hai trong thực nghiệm ở mức từ Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình Dữ liệu train (token/câu) 123,077 6,186 121,115 6,157 122,278 6,166 122,202 6,158 121,268 6,165 121,988 6,166 Dữ liệu test (token/câu) 29,408 1,522 31,370 1,550 30,207 1,541 30,283 1,549 31,217 1,542 30,497 1,541 Bảng 19. Kết quả thực nghiệm mức từ với bộ dữ liệu thứ hai sử dụng mô hình MEMM Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình T (s) t (s) P (%) 85.17 85.64 85.51 85.71 85.81 85.57 Bảng 20. Kết quả thực nghiệm mức từ với bộ dữ liệu thứ hai sử dụng mô hình CRF Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình T (s) 15,125.45 17,056.91 17,563.01 16,174.81 17,968.32 16,777.70 t (s) 0.93 2.05 1.76 1.15 1.34 1.45 P (%) 88.73 90.65 90.05 89.45 88.98 89.57 Bảng 21. Kết quả thực nghiệm mức từ với bộ dữ liệu thứ hai sử dụng mô hình SVM Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình T (s) t (s) P (%) 55 • Thực nghiệm ở mức hình vị Bảng 22. Mô tả bộ dữ liệu thứ hai trong thực nghiệm ở mức hình vị Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình Dữ liệu train (token/câu) 148,189 6,186 145,912 6,157 146,733 6,166 144,040 6,158 144,752 6,165 145,925 6,166 Dữ liệu test (token/câu) 34,689 1,522 36,744 1,550 36,549 1,541 37,071 1,549 37,215 1,542 36,454 1,541 Bảng 23. Kết quả thực nghiệm mức hình vị với bộ dữ liệu thứ hai sử dụng mô hình MEMM Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình T (s) t (s) P (%) 88.63 89.64 89.26 89.36 89.63 89.22 Bảng 24. Kết quả thực nghiệm mức hình vị với bộ dữ liệu thứ hai sử dụng mô hình CRF Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình T (s) 15,316.05 17,401.48 17,683.70 16,298.69 18,002.56 16,940.50 t (s) 1.26 2.25 1.89 1.35 1.62 1.67 P (%) 89.82 91.08 90.76 89.79 89.63 90.22 56 Bảng 25. Kết quả thực nghiệm mức hình vị với bộ dữ liệu thứ hai sử dụng mô hình SVM Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình T (s) t (s) P (%) 4.5.2. Lần thực nghiệm cho kết quả tốt nhất 4.5.2.1. Thực nghiệm với bộ dữ liệu thứ nhất Bảng 26. Kết quả tốt nhất cho bộ dữ liệu thứ nhất MEMM CRF SVM Dữ liệu train Dữ liệu test T (s) t (s) P (%) 4.5.2.1. Thực nghiệm với bộ dữ liệu thứ hai Bảng 27. Kết quả tốt nhất cho bộ dữ liệu thứ hai MEMM CRF SVM Dữ liệu train Dữ liệu test T (s) t (s) P (%) 57 4.5.3. Trung bình 05 lần thực nghiệm 4.5.3.1. Thực nghiệm với bộ dữ liệu thứ nhất Trung bình, huấn luyện với 8289 câu và kiểm thử với khoảng 2068 câu. Bảng 27. Kết quả trung bình cho bộ dữ liệu thứ nhất Mô hình Thời gian huấn luyện T (s) Thời gian kiểm thử t (s) Độ chính xác (%) MEMM CRF SVM 4.5.3.2. Thực nghiệm với bộ dữ liệu thứ hai Trung bình, huấn luyện với 6166 câu và kiểm thử với khoảng 1541 câu. Bảng 28. Kết quả trung bình cho bộ dữ liệu thứ hai Mô hình Thời gian huấn luyện T (s) Thời gian kiểm thử t (s) Độ chính xác (%) MEMM CRF SVM 4.5.4. Đánh giá và thảo luận