Phân tách cụm danh từ cơ sở tiếng Việt dùng mô hình CRFs

  • Số trang: 55 |
  • Loại file: PDF |
  • Lượt xem: 52 |
  • Lượt tải: 1
nhattuvisu

Đã đăng 26946 tài liệu

Mô tả:

i ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ HƢƠNG THẢO PHÂN TÁCH CỤM DANH TỪ CƠ SỞ TIẾNG VIỆT SỬ DỤNG MÔ HÌNH CRFs Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60 48 05 LUẬN VĂN THẠC SĨ NGƢỜI HƢỚNG DẪN KHOA HỌC: TS.Nguyễn Phƣơng Thái Hà Nội – 2010 i MỤC LỤC Lời cảm ơn .....................................................................Error! Bookmark not defined. Tóm tắt nội dung ...........................................................Error! Bookmark not defined. Lời cam đoan .................................................................Error! Bookmark not defined. Danh mục bảng số liệu..............................................................................................iii Danh mục hình vẽ ..................................................................................................... iv Lời mở đầu ................................................................................................................. 1 Chương 1: Khái quát về bài toán phân tách cụm danh từ cơ sở ............................. 3 1.1. Giới thiệu bài toán ......................................................................................... 3 1.2. Một số nghiên cứu về bài toán phân tách cụm danh từ cơ sở ......................... 5 1.3. Một số phương pháp biểu diễn dữ liệu........................................................... 7 1.4. Một số phương pháp giải quyết bài toán ........................................................ 8 1.4.1. Thuật toán học dựa vào biến đổi ............................................................. 9 1.4.2. Thuật toán máy vector hỗ trợ ................................................................ 10 1.4.3. Phương pháp tiếp cận của luận văn ....................................................... 12 Chương 2: Mô hình trường ngẫu nhiên có điều kiện ............................................. 13 2.1. Mô hình đồ thị............................................................................................. 14 Mô hình đồ thị vô hướng ................................................................................ 14 2.2. Mô hình trường ngẫu nhiên có điều kiện ..................................................... 15 2.3. Ước lượng tham số và suy diễn CRFs ......................................................... 17 2.3.1. Ước lượng tham số cho CRFs ............................................................... 17 2.3.2. Suy diễn CRFs...................................................................................... 19 Chương 3: Đặc điểm cụm danh từ tiêng Việt và phương pháp xây dựng tập dữ liệu ............................................................................................................................ 21 3.1. Đặc điểm cụm danh từ tiếng Việt ................................................................ 21 3.2. Phương pháp xây dựng tập dữ liệu .............................................................. 26 3.2.1. Phương pháp xây dựng tập dữ liệu tiếng Anh ....................................... 26 3.2.2 Phương pháp xây dựng tập dữ liệu Tiếng Việt ....................................... 26 Chương 4: Bài toán phân tách cụm danh từ tiếng Việt sử dụng mô hình CRFs .. 33 4.1. Phân tách cụm từ tiếng Việt sử dụng mô hình CRFs .................................... 33 4.2. Thực nghiệm ............................................................................................... 34 ii 4.2.1. Dữ liệu và chương trình ............................................................................ 34 4.2.2. Kết quả thử nghiệm .................................................................................. 36 4.2.2.1 Thực nghiệm 1: Đánh giá sự phục thuộc tập thuộc tính ...................... 36 4.2.2.2. Đánh giá sự phụ thuộc của kích thước tập dữ liệu huấn luyện ............ 40 4.2.2.3. Đánh giá và phân tích lỗi ................................................................... 41 Kết luận .................................................................................................................... 43 Tài liệu tham khảo ................................................................................................... 45 Phụ lục: Tập nhãn từ loại và nhãn cú pháp trong Viet Treebank ........................ 49 Tập nhãn từ loại: ................................................................................................ 49 Tập nhãn cú pháp ............................................................................................... 49 Tập nhãn mệnh đề: ............................................................................................. 50 Tập nhãn chức năng cú pháp: ............................................................................. 50 iii Danh mục bảng số liệu Bảng 1: Một số kết quả bài toán phân tách cụm danh từ cơ sở tiếng Anh ..................... 6 Bảng 2: Một số kết quả bài toán phân tách cụm danh từ cơ sở ngôn ngữ khác ............. 6 Bảng 3: Ví dụ về các phương pháp biểu diễn dữ liệu ................................................... 8 Bảng 4: Cấu trúc phần đầu của cụm danh từ tiếng Việt .............................................. 23 Bảng 5: Cấu trúc phần đầu của cụm danh từ tiếng Việt .............................................. 24 Bảng 6: Ví dụ về tệp dữ liệu được sử dụng trong thực nghiệm ................................... 34 Bảng 7: Một vài thống kê về tập dữ liệu..................................................................... 36 Bảng 8: Một số ví dụ về mẫu thuộc tính ..................................................................... 37 Bảng 9: Chi tiết tập thuộc tính của thí nghiệm 7......................................................... 39 Bảng 10: Kết quả của bộ phân tách cụm danh từ tiếng Việt ....................................... 40 iv Danh mục hình vẽ Hình 1: Quá trình huấn luyện của thuật toán TBL ........................................................ 9 Hình 2: Siêu phẳng có lề hẹp ..................................................................................... 11 Hình 3: Siêu phẳng có lề rộng .................................................................................... 11 Hình 4: Dữ liệu có nhiễu ............................................................................................ 11 Hình 5: Dữ liệu không thể phân tách tuyến tính ......................................................... 11 Hình 6: Mô hình đồ thị CRFs..................................................................................... 16 Hình 7: Ví dụ về biểu diễn dạng cây của một câu đã phân tích cú pháp...................... 27 Hình 8: Ví dụ về nhánh NP có độ sâu bằng 1 hoặc 2 .................................................. 28 Hình 9: Ví dụ về nhánh NP có độ sâu lớn hơn 2......................................................... 29 Hình 10: Nhánh NP có độ sâu lớn hơn 3 .................................................................... 30 Hình 11: Nhánh QP có độ sâu bằng 1 ........................................................................ 30 Hình 12: Nhánh QP có độ sâu bằng 2 ........................................................................ 30 Hình 13: Nhánh QP có độ sâu bằng 3 và chứa NP ..................................................... 30 Hình 14: Nhánh QP có độ sâu lớn hơn 3 và chứa NP có độ sâu bằng 1 ...................... 31 Hình 15: Ví dụ về cụm danh từ chứa liên từ “và” ....................................................... 31 Hình 16: Mô hình hoạt động của bộ tách cụm danh từ tiếng Việt ............................... 33 Hình 17: Sự tác động của tập thuộc tính đến độ chính xác của mô hình phân cụm ..... 38 Hình 18: Kết quả bộ phân tách cụm danh từ theo kích thước tập dữ liệu huấn luyện .. 40 1 Lời mở đầu Thế giới bước vào thế kỷ 21 với sự phát triển nhanh và đạt được nhiều thành tựu trong tất cả các lĩnh vực kinh tế, kỹ thuật, văn hóa, xã hội… Cùng với sự phát triển này, nhân loại đã tạo ra một lượng thông tin khổng lồ và phần lớn những thông tin đó chúng ta có thể tìm thấy thông qua hệ thống mạng Internet. World Wide Web (gọi tắt là Web) đã trở thành một môi trường chuyển tải thông tin không thể thiếu trong thời đại Công nghệ thông tin ngày nay. Sự phổ biến và bùng nổ thông tin trên Web cũng đặt ra một thách thức mới là làm thế nào để khai thác được thông tin trên Web một cách hiệu quả, mà cụ thể là làm sao để máy tính có thể trợ giúp xử lý tự động được chúng. Có thể nói xử lý ngôn ngữ tự động trên máy tính là một trong những vấn đề khó nhất của Công nghệ thông tin. Cái khó nằm ở chỗ làm sao cho máy được hiểu ngôn ngữ con người, từ việc hiểu nghĩa từng từ trong mỗi hoàn cảnh cụ thể, đến việc hiểu nghĩa một câu, rồi hiểu cả văn bản. Trong nỗ lực xây dựng một cơ sở tri thức tiếng Việt thì các bài toán cơ bản như tách từ, gán nhãn từ loại, xác định cụm từ, phân tích cú pháp, … là những công việc không thể thiếu. Tùy từng ứng dụng sẽ cần phân tích thông tin ở các mức độ khác nhau. Nhiều ứng dụng của xử lý ngôn ngữ tự nhiên (như dịch máy) yêu cầu thông tin về cú pháp và các công cụ để phân tích cú pháp. Tuy nhiên với tiếng Việt, hầu hết các nhà nghiên cứu hiện tại mới chỉ tập trung vào bài toán tách từ và gán nhãn từ loại (theo [21]). Quá trình xây dựng bộ công cụ và dữ liệu đã gán nhãn cho các bài toán nền tảng như phân tách cụm từ và phân tích cú pháp hiện đang được nghiên cứu, phát triển. Đây là một bước quan trọng cho các ứng dụng phát triển ngôn ngữ tự nhiên yêu cầu hiểu sâu hơn về ngôn ngữ. Nhu cầu cần phải phát triển những công cụ như này là động lực thúc đẩy tôi nghiên cứu và tìm hiểu về bài toán phân tách cụm từ danh từ tiếng Việt, với mục tiêu phát triển được một công cụ cho bài toán này. Luận văn với đề tài “Phân tách cụm danh từ cơ sở tiếng Việt sử dụng mô hình CRFs” được tổ chức thành bốn chương mà nội dung chính của các chương được giới thiệu như dưới đây. Chương 1: Khái quát về bài toán phân tách cụm danh từ giới thiệu bài toán và các nghiên cứu trước đó cũng như kết quả đã đạt được về bài toán này. Chương này cũng trình bày một số thuật toán điển hình phân tách cụm danh từ, từ đó chọn ra 2 hướng tiếp cận với ngôn ngữ tiếng Việt. Một số phương pháp biểu diễn dữ liệu cũng được giới thiệu trong chương này. Chương 2: Mô hình trường ngẫu nhiên có điều kiện trình bày cơ bản về CRFs mô hình học máy được đánh giá là môt trong những phương pháp tốt nhất cho bài toán gán nhãn dữ liệu dạng chuỗi. Chương 3. Đặc điểm cụm danh từ tiếng Việt và phương pháp xây dựng tập dữ liệu trình bày cấu trúc của cụm danh từ tiếng Việt, từ đó đề xuất phương pháp thích hợp xây dựng tập dữ liệu tiếng Việt. Chương 4. Bài toán phân tách cụm danh từ tiếng Việt sử dụng mô hình CRFs trình bày các kết quả thực nghiệm khi áp dụng mô hình CRFs để phân tách cụm danh từ tiếng Việt với bộ dữ liệu do luận văn xây dựng. Một số nhận xét, đánh giá cũng được trình bày. 3 Chương 1: Khái quát về bài toán phân tách cụm danh từ cơ sở 1.1. Giới thiệu bài toán Trong những năm gần đây, nhiều ứng dụng xử lý ngôn ngữ tự nhiên như trích chọn thông tin, tóm tắt văn bản, hỏi đáp và dịch máy phát triển mạnh mẽ đem lại nhiều lợi ích thiết thực. Trong các ứng dụng này, cụm danh từ cơ sở đóng một vai trò quan trọng. Chính vì vậy, ngay từ những năm 1990, đã có nhiều nghiên cứu liên quan đến lĩnh vực này trên tiếng Anh và cho đến nay các nghiên cứu đó vẫn liên tục được cải tiến và đã đạt được một số kết quả khả quan nhất định. Các ngôn ngữ khác như tiếng Trung, tiếng Hàn Quốc, tiếng Ấn Độ … cũng rất được quan tâm và nghiên cứu khá nhiều. Nhiều công trình nghiên cứu và bài báo khoa học liên quan đến vấn đề này đã được công bố, điển hình phải kể đến hai hội nghị: Hội nghị về xử lý ngôn ngữ tự nhiên CoNLL1 năm 2000 với chủ đề chính là phân tách cụm từ và phân tách cụm danh từ; Hội nghị về phân tích sơ bộ các ngôn ngữ Nam Á SPSAL 2007 2. Đối với tiếng Việt, hiện nay hầu hết các nhà nghiên cứu mới chỉ tập trung vào bài toán tách từ và gán nhãn từ loại. Phân tách cum danh từ cơ sở tiếng Việt vẫn còn là bài toán mở. Các nghiên cứu về bài toán này rất ít và mới chỉ dừng ở mức thử nghiệm quy mô nhỏ, chưa được công bố rộng rãi. Phân tách các cụm từ là bài toán chia một câu thành các cụm sao cho các từ trong cùng một cụm có liên quan với nhau về mặt cú pháp. Các cụm này không chồng lên nhau (non-overlapping) theo nghĩa một từ chỉ được phép thuộc một cụm duy nhất. Ví dụ câu tiếng Anh dưới đây sẽ được tách thành các cụm như sau: [NP He] [VP reckons] [NP the current account deficit] [VP will narrow] [PP to] [NP only £ 1.8 billion] Hoặc một câu tiếng Việt sẽ được tách thành các cụm như sau: [NP Cô ấy] [VP học] [PP ở] [NP trường Đại học Công nghệ] Ở đây, các cụm được biểu diễn như một nhóm các từ liền kề nhau nằm giữa hai dấu ngoặc vuông: Dấu ngoặc vuông mở biểu thị bắt đầu một cụm; Dấu ngoặc vuông đóng biểu thị kết thúc một cụm. Các chữ viết hoa liền sau dấu ngoặc vuông mở là kí hiệu viết tắt biểu thị loại của các cụm, ví dụ NP là cụm danh từ, VP là cụm động từ, PP là cụm giới từ. Trong các loại cụm thì cụm danh từ chiếm tỷ lệ lớn nhất, tập dữ liệu 1 2 http://www.cnts.ua.ac.be/conll2000/ http://shiva.iiit.ac.in/SPSAL2007/ 4 tiếng Anh WSJ 15-18 có tới 51% là cụm danh từ [12]. Hơn nữa, trong nhiều ứng dụng xử lý ngôn ngữ tự nhiên, việc tách các cụm danh từ là bước trung gian quan trọng để xử lý các bước tiếp theo. Vì vậy, phân tách cụm danh từ cũng đóng vai trò quan trọng trong xử lý ngôn ngữ tự nhiên. Phân tách cụm danh từ là một phần của bài toán phân tách cụm từ, giải quyết việc nhận biết các cụm danh từ không đệ quy (non-recursive noun phrase) hay cụm danh từ không chồng nhau (non-overlappling noun phrase) trong câu. Các cụm danh từ được phân tách ở đây là các cụm danh từ đơn giản, hay cụm danh từ cơ sở. Đó là các cụm danh từ không đệ quy, tức là không chứa một cụm danh từ khác bên trong nó và không chứa thành phần bổ nghĩa là một cụm danh từ. Trong khuôn khổ luận văn này, tôi chỉ tập trung giải quyết bài toán tách cụm danh từ cơ sở tiếng Việt. Tuy nhiên, do các đặc trưng ngôn ngữ của tiếng Việt nên cấu trúc của cụm danh từ cơ sở tiếng Việt sẽ khác cấu trúc cụm danh từ đơn giản trong các xử lý trích cụm danh từ tiếng Anh. Đặc trưng và cấu trúc cụm danh từ cơ sở tiếng Việt sẽ được trình bày kỹ ở Chương 3. Một hệ thống phân tách cụm danh từ cơ sở tốt có thể được áp dụng trong nhiều bài toán như:  Trong hệ thống tìm kiếm thông tin, thay vì tìm kiếm tài liệu chứa các từ riêng lẻ, hệ thống sẽ tìm kiếm dựa vào các cụm từ. Khi đó một số cụm từ và danh từ riêng sẽ rất hữu ích cho mục đích tìm kiếm tài liệu. Phân tách các cụm từ cũng rất hữu ích cho các bài toán trích chọn thông tin, máy hỏi-đáp.  Hệ thống dịch máy dựa vào thống kê có thể gồm các hệ con có nhiệm vụ dịch các cụm như cụm danh từ, cụm động từ, cụm giới từ,… như một tác vụ nhỏ trong quá trình dịch. Hệ dịch con có thể được huấn luyện trên tập dữ liệu học là các cụm danh từ, cụm động từ, cụm giới từ,… Với hệ dịch máy sử dụng tập dữ liệu huấn luyện song song, các cụm danh từ cũng được sử dụng để gióng hàng văn bản. Các câu trong tập dữ liệu song song được gióng hàng bằng cách sử dụng các thông tin cụm từ và liên kết cụm ở ngôn ngữ nguồn với cụm ở ngôn ngữ đích.  Phân tách cụm danh từ có thể được sử dụng như một bước tiền xử lý trước khi phân tích cả câu. Vì ngôn ngữ tự nhiên có tính nhập nhằng cao nên việc phân tích một câu có thể trở nên rất phức tạp. Trong những trường hợp này, phân tách cụm từ có thể được sử dụng như một bước tiền xử lý giải quyết những nhập nhằng này. 5  Xác định đồng tham chiếu là bài toán xác định các cụm danh từ cùng tham chiếu tới một thực thể nào đó. Xác định đồng tham chiếu là một trong những nghiên cứu cốt lõi trong xử lý ngôn ngữ tự nhiên, đóng vai trò quan trọng trong các lĩnh vực như máy hỏi-đáp, dịch tự động, tóm tắt văn bản. Để giải quyết bài toán phải qua nhiều bước, nhưng bước quan trọng đầu tiên là phải xác định được các cụm danh từ trong từng câu. Vì vậy, phân tách cụm danh từ là bài toán cơ sở để xác định tham chiếu trong văn bản.  Trong hệ thống tự động sinh chỉ mục các thuật ngữ cho một cuốn sách, bước đầu tiên là phải xác định được các thuật ngữ để đánh chỉ mục. Các thuật ngữ này thường là danh từ hoặc cụm danh từ. Do đó, bài toán phát hiện và phân tách cụm danh từ sẽ là một bước quan trọng trong quá trình sinh chỉ mục tự động. 1.2. Một số nghiên cứu về bài toán phân tách cụm danh từ cơ sở Năm 1991, Stenven Abney đã đề xuất bài toán phân tích một câu đầu vào thành các cụm từ trong đó các từ trong cùng một cụm tương liên với nhau [7]. Nghiên cứu của tác giả dựa vào kết quả nghiên cứu của hai nhà tâm lý học Gee và Grojean (1983), theo đó các cụm là những quãng ngắt khi đọc một câu. Giả sử khi đọc một câu, ta không đọc liền mạch cả câu đó mà sẽ ngắt ra thành các cụm như sau: [I begin] [with an intuition] : [when I read] [a sentence], [I read it] [a chunk] [at a time] Những cụm này được gọi là cụm  . Cụm  điển hình gồm một từ nội dung, xung quanh là các từ chức năng. Từ chức năng (function word) là những từ chứa ít nghĩa từ vựng hoặc nhập nhằng về ngữ nghĩa nhưng nó diễn tả quan hệ ngữ pháp với các từ khác trong một câu như giới từ, đại từ, …); Những từ không phải là từ chức năng được gọi là từ nội dung (content word). Sau Abney, một số nghiên cứu khác tập trung chủ yếu vào phát hiện các cụm danh từ ở mức thấp, thường là trích chọn các thuật ngữ (Bourigault 1992, Voutilainen 1993) (theo [19]) bằng cách sử dụng văn phạm. Phải đến năm 1995 khi Lance Ramshaw và Mitch Marcus đề xuất phương pháp phân tách cụm từ bằng phương pháp học máy thì bài toán này mới được biết đến rộng rãi và được nhiều nhà khoa học quan tâm. Phương pháp học máy dựa vào biến đổi (Transformation-Based Learning - TBL) được Ramshaw và Marcus sử dụng và đem lại kết quả khả quan với F1 bằng 92.03% [19]. Hai tác giả cũng xây dựng bộ dữ liệu chuẩn tiếng Anh mà hầu hết các nghiên cứu sau này thường sử dụng để so sánh, đánh giá kết quả. Ba nhà nghiên cứu Abney, Ramshaw, Marcus được coi là những người đi tiên phong trong vấn đề này. 6 Sau nghiên cứu của Ramshaw và Marcus, nhiều nhà nghiên cứu khác đã đi sâu tìm hiểu, giải quyết bài toán, trong đó phải kể tới hội nghị CONLL-2000 tập trung về phân tách cụm danh từ và các loại cụm từ khác. Nhiều phương pháp học máy khác nhau đã được sử dụng để thử nghiệm và thu được kết quả khá tốt. Có thể được chia thành bốn nhóm phương pháp: phương pháp học dựa vào luật, học dựa vào bộ nhớ, học thống kê và các hệ thống kết hợp. Một số kỹ thuật mới được phát triển gần đây như mô hình trường ngẫu nhiên có điều kiện (Conditional Random Fields, CRFs), phương pháp học cấu trúc, học bán giám sát,… cũng đã được áp dụng, phát triển. Mặc dù đã được nghiên cứu trong gần hai mươi năm qua nhưng đến nay nhiều nhà nghiên cứu vẫn quan tâm và tìm cách cải tiến. Điều này chứng tỏ sự cần thiết và tầm quan trọng của một hệ thống phân tách cụm từ danh từ nói riêng và các cụm từ nói chung. Một số kết quả tốt nhất cho bài toán phân tách cụm danh từ cơ sở tiếng Anh được biểu diễn trong bảng 1. Bảng 1: Một số kết quả bài toán phân tách cụm danh từ cơ sở tiếng Anh Tác giả Phương pháp F1 Hieu, Minh 2006 [25] Trường ngẫu nhiên có điều kiện 96.74 Kudo, Matsumoto 2001 [34] Máy vector hỗ trợ 95.77 Sang 2000 [13] Kết hợp các phương pháp 94.90 Sha, Pereira 2003 [31] Trường ngẫu nhiên có điều kiện 94.38 Với các ngôn ngữ khác, hầu hết kết quả tách cụm danh từ thấp hơn khá nhiều so với tiếng Anh, do mỗi ngôn ngữ có những đặc trưng và khó khăn riêng. Ngôn ngữ Trung Quốc đạt kết quả cao khi sử dụng phương pháp máy vector hỗ trợ và mô hình trường ngẫu nhiên có điều kiện [15]. Ba ngôn ngữ của Ấn Độ là Bengali, Hindi và Telugu đạt kết quả phân tách cụm từ cao nhất khi sử dụng phương pháp CRFs [10]. Ngôn ngữ Hàn Quốc cũng đạt kết quả rất cao với CRFs khi phân tách cụm danh từ cơ sở. Một số kết quả phân tách cụm danh từ của các ngôn ngữ khác được biểu diễn trong bảng 2. Bảng 2: Một số kết quả bài toán phân tách cụm danh từ cơ sở ngôn ngữ khác Tác giả Phương pháp Chen, Zang, Isahara 2006 CRFs [36] Xu, Zong, Zhao 2006 [15] Kết hợp SVMs và CRFs Ngôn ngữ F1 Trung Quốc 89.79 Trung Quốc 89.27 7 Avinesh, Karthik 2007 [10] Lee, Kim, Lee [38] CRFs Bengali (Ấn Độ) 82.74 (phân tách cụm từ) Hindi (Ấn Độ) 80.97 Telugu (Ấn Độ) 79.15 Hàn Quốc 94.27 CRFs Các nhà nghiên cứu xử lý ngôn ngữ tiếng Việt hiện vẫn đang nỗ lực trong quá trình xây dựng bộ công cụ và tập dữ liệu cho các bài toán nền tảng như phân tích cú pháp, phân tách cụm từ. Tuy nhiên hiện nay vẫn chưa có một bộ dữ liệu chuẩn nào cho việc đánh giá và so sánh hệ thống tách cụm danh từ tiếng Việt, do việc xây dựng bộ dữ liệu này rất tốn kém về mặt thời gian cũng như công sức. Hi vọng rằng trong thời gian gần sắp tới, chúng ta sẽ có được bộ dữ liệu chuẩn hỗ trợ trong việc nghiên cứu bài toán này. 1.3. Một số phương pháp biểu diễn dữ liệu Bài toán phân tách cụm danh từ tiếng Việt có thể được xem là bài toán gán nhãn hoặc phân lớp cho các từ trong câu. Ví dụ, đối với bài toán xác định từ loại của các từ trong câu là gán nhãn các lớp từ loại cố định có sẵn (danh từ, động từ, tính từ, đại từ, số từ, …) cho các từ trong câu. Hay như bài toán xác định trọng âm của từ là xác định loại trọng âm nào tại mỗi ký tự trong từ, trong câu. Như vậy, tùy theo tác vụ xử lý ngôn ngữ tự nhiên mà có thể gán nhãn giá trị của lớp trên mỗi ký tự hoặc trên mỗi từ trong câu. Riêng đối với xác định cụm danh từ trong câu thì dữ liệu cần gán nhãn là nhóm các từ liên tục nhau và cần xác định xem mỗi từ có thuộc cụm danh từ hay không. Tùy vào phương pháp biểu diễn, ta sẽ có tập các nhãn để gán cho các từ trong câu. Bộ dữ liệu do Ramshaw và Marcus xây dựng năm 1995 được biểu diễn theo phương pháp IOB, sử dụng tập nhãn là {I, O, B}. Sau này khi Sang và Veenstra giới thiệu ba biến thể khác là IOB2, IOE1, IOE2 năm 1999 [35] thì phương pháp biểu diễn của Ramshaw và Marcus được gọi là IOB1. Bốn phương pháp biểu diễn dữ liệu này giống nhau ở cách gán nhãn cho từ không thuộc cụm – nhãn O; và khác nhau ở cách gán nhãn cho từ đầu tiên và từ cuối cùng của một cụm danh từ. Cụ thể như sau:  IOB1: Từ đầu tiên của một cụm danh từ cơ sở theo sau một cụm danh từ cơ sở khác được gán nhãn B. 8  IOB2: Từ đầu tiên của cụm danh từ cơ sở được gán nhãn B, những từ tiếp theo của cụm danh từ cơ sở được gán nhãn I, từ không thuộc cụm danh từ nào được gán nhãn là O.  IOE1: Từ cuối cùng của một cụm danh từ cơ sở đứng liền trước cụm danh từ khác được gán nhãn E.  IOE2: Từ cuối cùng của tất cả cụm danh từ cơ sở được gán nhãn E. Đây là một số phương pháp thường được sử dụng trong các hệ thống phân tách cụm danh từ cơ sở. Ngoài ra còn một số phương pháp khác như [+], [+IO, IO+]. Ví dụ, câu “Tốc độ tăng trưởng GDP trên địa bàn TP đạt 12% năm 2005” sẽ được gán nhãn như sau: Bảng 3: Ví dụ về các phương pháp biểu diễn dữ liệu Từ Nhãn từ loại IOB1 IOB2 IOE1 IOE2 Tốc_độ N-H I B I I tăng_trưởng V-H I I I I GDP Ny I I I E trên E-H O O O O địa_bàn N-H I B I I TP Ny I I I E đạt V-H O O O O 12% M I B E E năm N-H B B I I 2005 M I I I E 1.4. Một số phương pháp giải quyết bài toán Phân tách cụm danh từ là một trong các bài toán xử lý ngôn ngữ tự nhiên có ứng dụng khá rộng rãi trong nhiều lĩnh vực khác nhau. Chính vì vậy, ngay từ những năm 1990, đã có nhiều nghiên cứu liên quan đến bài toán này và cho đến nay các nghiên cứu đó vẫn tiếp tục được cải tiến, đạt được những kết quả khả quan và ngày càng được áp dụng trên nhiều ngôn ngữ khác nhau. 9 Hiện nay tồn tại nhiều phương pháp giải quyết bài toán phân tách cụm danh từ cơ sở, nhưng nhìn chung có thể chia thành bốn nhóm chính sau: học dựa trên luật (rule-based methods), học mẫu (memory-based methods), các phương pháp dựa vào thống kê (statistical methods) và các phương pháp kết hợp (combined methods). Phần này sẽ trình bày hai thuật toán học máy là học dựa vào biến đổi và máy vector hỗ trợ. Thuật toán học dựa vào biến đổi là phương pháp học máy đầu tiên được áp dụng để xác định cụm danh từ tiếng Anh và đã thu được kết quả khá tốt. Máy vector hỗ trợ hiện là một trong những phương pháp đem lại kết quả tốt nhất cho bài toán này. 1.4.1. Thuật toán học dựa vào biến đổi Học dựa vào biến đổi (Transformation-based learning hay Transformationbased error-driven learning, TBL) là phương pháp học máy dựa trên luật hiệu quả, được Brill giới thiệu năm 1993 [11]. TBL là thuật toán linh hoạt, có thể dễ dàng mở rộng với nhiều bài toán và miền ứng dụng khác nhau. TBL đã được áp dụng cho nhiều bài toán và đem lại kết quả khả quan như gán nhãn từ loại, phân tách cụm danh từ, phân đoạn và hiểu văn bản. Ý tưởng cơ bản của TBL là học một tập các luật từ dữ liệu huấn luyện. Tập luật này được sắp thứ tự và phát triển tăng dần dựa vào trạng thái hiện tại của tập dữ liệu học. Tập luật đầu tiên được lựa chọn dựa vào thống kê đơn giản, sau đó các luật được học tăng dần để hiệu chỉnh những lỗi sai cho đến khi độ chính xác không thể tăng lên được nữa. Dữ liệu huấn luyện Hệ dự đoán cơ sở Tập mẫu luật Đánh giá các luật ứng cử Tập dữ liệu hiện tại Tập nhãn đúng Lựa chọn luật Áp dụng luật Tập luật kết quả Hình 1: Quá trình huấn luyện của thuật toán TBL 10 Quá trình học được thực hiện như sau (hình 1): Đầu tiên, một hệ thống cơ sở (baseline system) được sử dụng để gán nhãn cho tập ví dụ học. Hệ thống cơ sở thường dựa vào kinh nghiệm, có thể là nhãn phổ biến nhất trong tập dữ liệu huấn luyện, hoặc có thể là kết quả của một bộ phân lớp khác. Sau đó, với các ví dụ bị hệ thống cơ sở dự đoán sai, các mẫu luật sẽ được sử dụng để lựa chọn danh sách các luật ứng cử (candidate). Các luật ứng cử này được kiểm tra với các ví dụ còn lại, xác định số ví dụ bị được gán đúng và số ví dụ bị gán sai khi áp dụng luật. Luật nào có tỉ số (số ví dụ gán đúng trừ số ví dụ gán sai) lớn nhất sẽ được lựa chọn. Luật này sẽ là luật đầu tiên trong danh sách luật được học. Quá trình học này được lặp lại trên tập dữ liệu đã bị biến đổi: tìm tập luật ứng cử, đánh giá chúng và lựa chọn luật tốt nhất. Quá trình này được lặp đi lặp lại, cho đến khi độ chính xác không thể tăng lên được nữa. Kết quả của quá trình này ta sẽ được một tập các mẫu được sắp xếp theo thứ tự, luật nào được lựa chọn trước sẽ đứng trước, luật nào được lựa chọn sau sẽ đứng sau. Để dự đoán một tài liệu, đầu tiên ta áp dụng hệ dự đoán cơ sở và sau đó áp dụng lần lượt từng luật trong tập luật trả về từ quá trình học. 1.4.2. Thuật toán máy vector hỗ trợ Máy vector hỗ trợ (Support Vector Machines – SVMs) được Vapnik giới thiệu lần đầu tiên năm 1995, là một hướng tiếp cận học máy mới dựa trên lý thuyết thống kê để giải quyết các bài toán nhận dạng hai lớp. SVMs được biết tới rộng rãi bởi độ chính xác cao khi áp dụng cho nhiều bài toán nhận dạng. Gần đây, SVMs được ứng dụng trong nhiều bài toán xử lý ngôn ngữ tự nhiên như phân lớp văn bản, phân tách cụm danh từ [15,33,34]. Đã có những kết quả lý thuyết cũng như thực nghiệm chỉ ra rằng SVM có thể đem lại kết quả tốt với không gian thuộc tính nhiều chiều mà không gặp phải hiện tượng quá khớp (over-fitting) dữ liệu huấn luyện. Về cơ bản, SVM là một bộ phân lớp tuyến tính giải quyết bài toán phân lớp nhị phân. Bài toán được định nghĩa như sau: Cho tập dữ liệu học D  ( xi , y i ), i  1,..., n với xi  R m và yi 1,1 là một số nguyên xác định xi là dữ liệu dương hay âm. Một tài liệu xi được gọi là dữ liệu dương nếu nó thuộc lớp ci ; xi được gọi là dữ liệu âm nếu nó không thuộc lớp ci . Các ví dụ huấn luyện sẽ được phân tách thành hai miền âm và dương bởi siêu phẳng có dạng:  x : f ( x)  w T   w0  0 Trong đó w  R m và w0  R đóng vai trò là tham số của mô hình. Hàm phân lớp nhị phân h : Rm  0,1 có thể thu được bằng cách xác định dấu của f(x) : 11 1 nếu f ( x)  0 h( x)   ngược lại 0 Hình 2: Siêu phẳng có lề hẹp Hình 3: Siêu phẳng có lề rộng Nếu dữ liệu được phân tách tuyến tính thì sẽ tồn tại nhiều siêu phẳng có khả năng phân tách dữ liệu thành hai miền. Hai trong số những siêu phẳng được minh họa như trên hình 2 và hình 3. Câu hỏi đặt ra là trong hai siêu phẳng này thì siêu phẳng nào tốt hơn, và làm thế nào để xác định được siêu phẳng tối ưu? Định nghĩa biên M của bộ phân lớp là khoảng cách giữa các siêu phẳng và các dữ liệu học gần nhất. Vapnik chứng minh rằng, siêu phẳng tối ưu nhất là siêu phẳng có biên lớn nhất, điều đó có nghĩa là chúng ta cần tìm siêu phẳng sao cho khoảng cách từ siêu phẳng đến những điểm gần nhất là lớn nhất. Vapnik cũng chứng minh rằng khả năng overfitting với siêu phẳng tối ưu nhỏ hơn so với các siêu phẳng khác. Hình 4: Dữ liệu có nhiễu Hình 5: Dữ liệu không thể phân tách tuyến tính Vì khoảng cách nhỏ nhất giữa f và dữ liệu huấn luyện là 1/||w||, SVM sẽ tìm w và wo sao cho: 12 Cực đại hóa 1 w 2 2 với ràng buộc: yi  wT xi  w 0   1 , i = 1, 2, … n Nếu dữ liệu có thể phân tách tuyến tính như trên thì SVM có thể tìm được siêu phẳng phân tách dữ liệu huấn luyện với độ chính xác lý tưởng. Tuy nhiên, trong thực tế rất hiếm khi dữ liệu có thể phân tách tuyến tính mà thường bị nhiễu (hình .. ) hoặc không tồn tại siêu phẳng phân tách (hình). Khi đó, thêm vào tham số độ sai lệch C, bài toán tối ưu trở thành: Cực tiểu hóa n 1 2 w  C  i với ràng buộc yi  wT xi  w 0   1  i in1 : i  0 2 i 1 Trong đó,  i là độ sai lệch của mỗi ví dụ huấn luyện, được đo bằng khoảng cách giữa ví dụ đó và biên của lớp chứa ví dụ. Bộ phân lớp theo cách này được gọi là bộ phân lớp máy vector hỗ trợ – Support Vector Machine. 1.4.3. Phương pháp tiếp cận của luận văn Các kết quả nghiên cứu về phân tách cụm danh từ đối với tiếng Anh và một số ngôn ngữ khác như tiếng Trung, tiếng Hàn Quốc, và một số ngôn ngữ của Ấn Độ cho thấy, trường ngẫu nhiên có điều kiện (CRFs) là một trong những phương pháp cho kết quả cao nhất khi giải quyết bài toán này. CRFs là phương pháp được các nhà nghiên cứu rất quan tâm hiện nay bởi những ưu điểm nổi trội như cho phép biểu diễn thuộc tính phụ thuộc vào các thành phần của dữ liệu quan sát, kết hợp nhiều thuộc tính phong phú từ dữ liệu một cách mềm dẻo. Hơn nữa, huấn luyện CRFs thực hiện dựa trên việc tối ưu hoá hàm log-likelihood - bản chất là một hàm lồi, do đó cho phép thu được tối ưu toàn cục. Xuất phát từ những lý do trên, luận văn lựa chọn mô hình trường ngẫu nhiên có điều kiện để giải quyết bài toán phân tách cụm danh từ tiếng Việt. Chương sau sẽ trình bày kỹ hơn về mô hình này. 13 Chương 2: Mô hình trường ngẫu nhiên có điều kiện Bài toán phân tích dữ liệu dạng chuỗi hay gán nhãn dữ liệu dạng chuỗi trong ngôn ngữ học thường được mô tả như việc ánh xạ chuỗi dữ liệu đầu vào thành chuỗi nhãn tương ứng. Ví dụ, một số bài toán trong xử lý ngôn ngữ tự nhiên như tách từ, phân tích cú pháp, nhận dạng thực thể tên, phân tách cụm từ, …. Bài toán này cũng xuất hiện khá nhiều trong các lĩnh vực khác như tin sinh học, nhận dạng tiếng nói, trích chọn thông tin. Một trong những phương pháp phổ biến để giải quyết bài toán gán nhãn và phân đoạn là sử dụng các mô hình Markov ẩn (Hidden Markov Models, HMMs) hoặc mô hình máy hữu hạn trạng thái dựa vào xác suất. Mô hình Markov ẩn là một dạng của mô hình sinh, định nghĩa phân phối xác suất đồng thời p(X,Y) với X và Y là các biến ngẫu nhiên biểu diễn chuỗi quan sát và chuỗi nhãn tương ứng. Để tính xác suất đồng thời này, mô hình sinh phải liệt kê tất cả các chuỗi quan sát có thể; trong nhiều miền ứng dụng thì điều này là không thể thực hiện được trừ khi các thành phần được biểu diễn như những đơn vị riêng biệt, độc lập với các thành phần khác trong chuỗi quan sát. Nói cách khác, tại một thời điểm, quan sát hiện tại chỉ phụ thuộc vào trạng thái tại thời điểm đó. Giả thiết này chỉ phù hợp cho một vài tập dữ liệu đơn giản, vì hầu hết các chuỗi quan sát trong thế giới thực đều được biểu diễn bởi nhiều thuộc tính có ảnh hưởng lẫn nhau và phụ thuộc vào nhiều quan sát. Đây là một trong những vấn đề cơ bản khi giải quyết bài toán gán nhãn dữ liệu dạng chuỗi. Như vậy, rõ ràng một mô hình khắc phục được nhược điểm trên phải thoả mãn hai tiêu chí: thứ nhất, bài toán suy diễn trong mô hình có thể thực hiện được; thứ hai, loại bỏ được giả thiết độc lập của chuỗi quan sát. Một cách để thoả mãn được hai tiêu chí này là sử dụng mô hình xác định phân phối có điều kiện p(Y|X) - là xác suất của chuỗi trạng thái với điều kiện đã biết chuỗi quan sát, thay vì tính xác suất đồng thời của chuỗi trạng thái và chuỗi quan sát như trên. Vì mô hình là có điều kiện, phụ thuộc toàn cục vào X nên có thể sử dụng nhiều thuộc tính đa dạng, phong phú. Ví dụ, trong các bài toán xử lý ngôn ngữ tự nhiêu, những thuộc tính hữu ích như các từ láng giềng, tiền tố, hậu tố, chữ viết hoa, và các thông tin ngữ nghĩa từ các nguồn như WordNet. Trường ngẫu nhiên có điều kiện (Conditional Random Fields, CRFs) [18] được McCallum giới thiệu năm 2000 là một mô hình đồ thị vô hướng để gán nhãn và phân đoạn dữ liệu dạng chuỗi dựa theo hướng tiếp cận có điều kiện như trên. Ưu điểm chính của CRFs so với mô hình Markov ẩn là bản chất có điều kiện của nó, cho phép biểu diễn được nhiều thuộc tính phong phú, và bài toán suy diễn có thể giải được. Hơn nữa CRFs cũng tránh được vấn đề “bias”, nhược điểm của mô hình Markov entropy cực 14 đại (Maximum entropy Markov models, MEMMs) [18] và các mô hình Markov có điều kiện dựa trên mô hình đồ thị có hướng. CRFs cho kết quả tốt hơn cả MEMMs và HMMs trong nhiều bài toán gãn nhãn chuỗi dữ liệu trong thế giới thực [8, 23]. Phần sau sẽ trình bày những nét khái quát về mô hình đồ thị, làm cơ sở để từ đó giới thiệu về mô hình CRFs. 2.1. Mô hình đồ thị Cho G  (V , E ) là một đồ thị với V là tập các đỉnh và E là tập các cạnh. Trong đó V  X  Y với X, Y là tập các biến ngẫu nhiên, được biểu diễn bằng các nút hình tròn. X thường là tập các biến đầu vào mà ta quan sát được, và Y là tập các biến đầu ra mà ta cần dự đoán. Nếu giữa hai nút không có cạnh nối thì hai nút đó độc lập có điều kiện. Độc lập có điều kiện nghĩa là hai biến ngẫu nhiên a, b độc lập với một biến ngẫu nhiên cho trước c nếu hai biến này độc lập với phân phối xác suất có điều kiện của chúng, hay p(a, b | c)  p(a | c) p(b | c) . Những đồ thị biểu diễn được tính chất độc lập có điều kiện của các phân phối cơ sở như này được gọi là đồ thị độc lập, vì đồ thị có thể biểu diễn tính chất độc lập có điều kiện của các phân phối cơ sở. Độc lập có điều kiện là một khái niệm quan trọng vì nó có thể được sử dụng để phân tích một phân phối xác suất phức tạp thành tích của các thừa số, trong đó mỗi thừa số chứa tập con các biến ngẫu nhiên tương ứng. Khái niệm này giúp cho các tính toán phức tạp trở nên hiệu quả hơn. Kí hiệu các chữ thường đậm x, y, s, v… là vector biểu diễn chuỗi dữ liệu quan sát, vector biểu diễn chuỗi trạng thái.…. Phân phối xác suất đồng thời sẽ được phân tích thành tích các thừa số  s với v s là tập con các biến ngẫu nhiên tương ứng cấu thành nên thừa số  s này. p( v)    s ( v s ) s (2.1) Hai dạng phổ biến nhất của mô hình đồ thị là mô hình đồ thị có hướng và mô hình đồ thị vô hướng. Điểm khác nhau của hai dạng này là cách phân tích phân phối xác suất đồng thời thành tích các thừa số. Phần sau sẽ trình bày về mô hình đồ thị vô hướng. Mô hình đồ thị vô hướng Khái niệm clique: Trong lý thuyết đồ thị, một clique trong một đồ thị vô hướng G là một tập các đỉnh V thoả mãn: với mỗi cặp đỉnh thuộc V luôn tồn tại một cạnh nối. 15 Do vậy một đồ thị con được tạo ra từ V sẽ là một đồ thị đầy đủ. Kích thước của một clique là số đỉnh của nó. Một clique tối đa (maximal clique) là tập các đỉnh V sao cho đồ thị con được tạo ra từ V là một đồ thị con đầy đủ và không là tập đỉnh con của bất kỳ đồ thị đầy đủ lớn hơn nào khác. Kí hiệu C là tập clique tối đa của đồ thị. Với mỗi clique c  C , gọi  c ( v c ) là hàm tiềm năng của các biến ngẫu nhiên v C . Mô hình đồ thị vô hướng sẽ phân tích xác suất đồng thời p( v) thành tích các hàm tiềm năng: p( v)  1  C (v C ) Z cC (2.2) Hàm tiềm năng có thể là hàm bất kỳ nhưng phải thoả mãn điều kiện hàm dương, nhận giá trị thực. Vì tính tổng quát này nên hàm tiềm năng không nhất thiết phải là một hàm xác suất. Do đó, cần đưa thêm hệ số chuẩn hoá Z đảm bảo tổng xác suất của tất cả các chuỗi đầu vào bằng 1 tức là  p( v)  1 . Hệ số Z được tính theo v công thức: Z    c ( v c ) v (2.3) cC Việc tính toán Z là một trong những thách thức khi học tham số mô hình. Để đơn giản, các nhà nghiên cứu thường xấp xỉ giá trị này. 2.2. Mô hình trường ngẫu nhiên có điều kiện Kí hiệu X là biến ngẫu nhiên tương ứng với chuỗi quan sát và Y là biến ngẫu nhiên tương ứng với chuỗi nhãn. Mỗi thành phần Y i của Y là một biến ngẫu nhiên nhận trá trị trong tập hữu hạn các trạng thái S. Một CRF là một mô hình đồ thị vô hướng phụ thuộc toàn cục vào biến ngẫu nhiên biểu diễn chuỗi quan sát. Một cách hình thức, định nghĩa G  (V , E ) là một đồ thị vô hướng sao cho mỗi nút v V tương ứng với một biến ngẫu nhiên biểu diễn thành phần Yv của Y. Nếu biến ngẫu nhiên Y v tuân theo tính chất Markov đối với đồ thị G tức là xác suất của biến ngẫu nhiên Y v khi đã biết X và tất cả các biến ngẫu nhiên khác Y{u|u  v, {u,v}  V} bằng xác suất của biến ngẫu nhiên Y v khi đã biết X và các biến ngẫu nhiên khác tương ứng với các đỉnh kề với đỉnh v trong đồ thị: p(Yv | X, Yu, u  v, {u,v}  V) = p(Yv | X, Yu, (u,v)  E)
- Xem thêm -