Đề tài Trích chọn thông tin trên tập văn bản pháp luật dùng kỹ thuật học máy bán giám sát dựa trên mô hình crfs theo tiêu chuẩn kỳ vọng tổng quát

- 1 - 1 TRƯỜNG …………………. KHOA………………………. ---------- Báo cáo tốt nghiệp Đề tài: TRÍCH CHỌN THÔNG TIN TRÊN TẬP VĂN BẢN PHÁP LUẬT DÙNG KỸ THUẬT HỌC MÁY BÁN GIÁM SÁT DỰA TRÊN MÔ HÌNH CRFs THEO TIÊU CHUẨN KỲ VỌNG TỔNG QUÁT - 2 - 2 LỜI CAM ĐOAN Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá nhân tôi, không sao chép lại của người khác. Trong toàn bộ nội dung của luận văn, những điều được trình bày hoặc là của cá nhân hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp pháp. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luận theo quy định cho lời cam đoan của mình. Hà Nội, 05/2011 Phạm Thị Ngân - 3 - 3 MỤC LỤC LỜI CAM ĐOAN .............................................................................................. 1 MỤC LỤC ......................................................................................................... 3 DANH MỤC HÌNH VẼ ..................................................................................... 5 DANH MỤC BẢNG BIỂU................................................................................ 6 KÝ TỰ VIẾT TẮT............................................................................................. 7 LỜI CẢM ƠN .................................................................................................... 8 LỜI MỞ ĐẦU.................................................................................................... 9 CHƯƠNG 1: HỌC BÁN GIÁM SÁT THEO MÔ HÌNH TRƯỜNG NGẪU NHIÊN CÓ ĐIỀU KIỆN.................................................................................. 11 1.1. Phương pháp học máy Trường ngẫu nhiên có điều kiện ............................. 11 1.1.1. Khái niệm trường ngẫu nhiên có điều kiện ......................................... 11 1.1.2. Học máy CRFs ................................................................................... 13 1.1.2.1. Hàm tiềm năng của các mô hình CRFs .................................... 13 1.1.2.2. Thuật toán gán nhãn cho dữ liệu dạng chuỗi. ........................... 14 1.1.2.3. Ước lượng tham số cho các mô hình CRFs .............................. 15 1.2. Học máy bán giám sát CRFs ...................................................................... 15 1.2.1. Học máy bán giám sát......................................................................... 15 1.2.1.1. Học không có giám sát và Học có giám sát ............................. 16 1.2.1.2. Học máy bán giám sát.............................................................. 18 1.2.1.3. Một số thuật toán học máy bán giám sát .................................. 19 1.2.2. Sơ bộ về mô hình học máy bán giám sát CRFs ................................... 21 1.3. Kết luận chương 1 ...................................................................................... 22 CHƯƠNG 2: HỌC MÁY BÁN GIÁM SÁT CRFs THEO TIÊU CHUẨN KỲ VỌNG TỔNG QUÁT ...................................................................................... 23 2.1. Tiêu chuẩn kỳ vọng tổng quát .................................................................... 23 2.1.1. Giới thiệu sơ bộ .................................................................................. 23 2.1.2. Tiêu chuẩn kỳ vọng tổng quát............................................................. 24 2.2. Mô hình học máy bán giám sát CRFs theo tiêu chuẩn kỳ vọng tống quát ... 26 - 4 - 4 2.3. Kết luận chương 2 ...................................................................................... 28 CHƯƠNG 3: MỘT MÔ HÌNH HỌC MÁY BÁN GIÁM SÁT CRFs TRÍCH CHỌN THÔNG TIN PHÁP LUẬT TIẾNG VIỆT ......................................... 29 3.1. Trích chọn thông tin từ văn bản pháp luật tiếng Việt ................................. 29 3.1.1. Một số đặc trưng về miền dữ liệu văn bản pháp luật tiếng Việt........... 29 3.1.2. Bài toán trích chọn thông tin văn bản pháp luật tiếng Việt .................. 31 3.2. Một mô hình học máy bán giám sát CRFs trích chọn thông tin pháp luật tiếng Việt ...................................................................................................... 31 3.2.1. Một số phân tích ................................................................................. 31 3.2.2. Mô hình đề nghị ................................................................................. 32 3.2.3. Lựa chọn thuộc tính............................................................................ 36 3.2.4. Cách đánh giá ..................................................................................... 36 3.3. Kết luận chương 3 ...................................................................................... 37 CHƯƠNG 4: THỰC NGHIỆM VÀ ĐÁNH GIÁ ............................................. 38 4.1. Mô hình thực nghiệm ................................................................................ 38 4.1.1. Dữ liệu thực nghiệm ........................................................................... 38 4.1.2. Bộ công cụ Mallet .............................................................................. 38 4.2. Thực nghiệm và đánh giá .......................................................................... 38 4.2.1. Môi trường thực nghiệm..................................................................... 38 4.2.2. Mô tả quy trình thực nghiệm............................................................... 38 4.2.3. Kết quả thực nghiệm........................................................................... 39 4.2.4. Đánh giá ............................................................................................. 40 4.3. Kết luận chương 4 ..................................................................................... 43 KẾT LUẬN...................................................................................................... 45 TÀI LIỆU THAM KHẢO ................................................................................ 47 - 5 - 5 DANH MỤC HÌNH VẼ Hình 1. Đồ thị vô hướng mô tả CRFs ....................................................... 12 Hình 2. Một bước trong thuật toán Viterbi cải tiến................................... 14 Hình 3/4. Mô hình đề xuất giải quyết bài toán.......................................... 34 Hình 5. Tập các ràng buộc (Constraint file) ............................................. 35 Hình 6. Kết quả nhóm thực nghiệm 1 ....................................................... 40 Hình 7. Kết quả nhóm thực nghiệm 2 ....................................................... 40 Hình 8. Kết quả nhóm thực nghiệm 3 ....................................................... 41 Hình 9. Kết quả nhóm thực nghiệm 4 ....................................................... 42 Hình 10. Kết quả nhóm thực nghiệm 5 ..................................................... 43 - 6 - 6 DANH MỤC BẢNG BIỂU Bảng 1. Mẫu ngữ cảnh từ vựng ........................................................................ 36 Bảng 2. Mẫu ngữ cảnh phát hiện tên thực thể .................................................. 36 Bảng 3. Kết quả nhóm thực nghiệm 1............................................................... 39 Bảng 4. Kết quả nhóm thực nghiệm 2............................................................... 40 Bảng 5. Kết quả nhóm thực nghiệm 3............................................................... 41 Bảng 6. Kết quả nhóm thực nghiệm 4............................................................... 42 Bảng 7. Kết quả nhóm thực nghiệm 5............................................................... 42 - 7 - 7 KÝ TỰ VIẾT TẮT CRFs Conditional Random Fields EM Entropy Maximum GE Generalized Expectation GEC Generalized Expectation Criteria GIS Generalized Iterative Scaling i.i.d independently and identically IIS Improved Iterative Scaling KL Kullback Leibler L-BFGS Limited memory Broyden–Fletcher–Goldfarb–Shanno LOC LOCation MISC MIScellaneous NER Named Entity Recognition ORG ORGanization PER PERson - 8 - 8 LỜI CẢM ƠN Để hoàn thành luận văn này tác giả đã nhận được sự giúp đỡ từ rất nhiều cơ quan, đoàn thể và cá nhân. Trước hết tôi xin chân thành cảm ơn các thầy giáo, cô giáo trong Khoa Công nghệ Thông tin, trường Đại học Công nghệ, Đại học Quốc gia Hà Nội đã tận tình giảng dạy, trang bị cho tôi những kiến thức quý báu trong suốt quá trình học tập tại trường. Tôi xin bày tỏ lòng biết ơn sâu sắc đến TS. Nguyễn Lê Minh - người thầy đã trực tiếp hướng dẫn tôi trong suốt quá trình xây dựng và hoàn thành luận văn này. Tôi xin bày tỏ lòng biết ơn chân thành đến thầy giáo PGS.TS. Hà Quang Thụy và các bạn trong Phòng thí nghiệm công nghệ tri thức, Trường Đại học Công nghệ đã giúp đỡ và đóng góp nhiều ý kiến quý báu cho tôi. Cuối cùng, tôi xin bày tỏ lòng biết ơn sâu sắc tới gia đình, bạn bè, những người luôn động viên, giúp đỡ tôi rất nhiệt tình để hoàn thành luận văn. Hà Nội, tháng 05 năm 2011 Học viên Phạm Thị Ngân - 9 - 9 LỜI MỞ ĐẦU Trích chọn thông tin là một khâu cơ bản trong bài toán khai phá dữ liệu. Ngày nay, cùng với sự phát triển của công nghệ thông tin, Tin học đã dần được ứng dụng rộng rãi trong nhiều lĩnh vực như kinh tế, thương mại, y tế, ngân hàng và mang lại nhiều lợi ích to lớn. Bản thân tôi hiện đang công tác tại Học viện Cảnh sát nhân dân, tôi có những hiểu biết nhất định về công tác giữ gìn trật tự an toàn xã hội của lực lượng cảnh sát nhân dân. Tôi nhận thấy, các hoạt động của lực lượng cảnh sát có liên quan nhiều đến việc lưu trữ hồ sơ dữ liệu, tra cứu, phân tích tổng hợp dữ liệu... Tuy nhiên, công tác quản lý hồ sơ dữ liệu này vẫn còn kém hiệu quả do những hạn chế nhất định. Do đó tôi đã mạnh dạn chọn đề tài tập trung nghiên cứu vào việc trích lọc thông tin trên tập văn bản pháp luật này. Trong nhiều thập kỷ qua, các nhà khoa học quan tâm đến lĩnh vực xử lý ngôn ngữ tự nhiên đã nghiên cứu và đề xuất được nhiều phương pháp, mô hình xử lý ngôn ngữ với hiệu quả cao. Nổi bật trong số đó là phương pháp học máy bán giám sát dựa trên mô hình trường ngẫu nhiên có điều kiện theo tiêu chuẩn kỳ vọng tổng quát, phương pháp này đạt được kết quả rất khả quan trên tập dữ liệu ngôn ngữ tiếng Anh và hiện chưa được áp dụng cho tiếng Việt. Được sự giúp đỡ và đồng ý của Thầy giáo hướng dẫn TS. Nguyễn Lê Minh, tác giả quyết định sử dụng mô hình này ứng dụng cho tập văn bản pháp luật. Bố cục của luận văn chia thành 4 chương như sau:  Chương 1: Trình bày những kiến thức cơ bản về mô hình trường ngẫu nhiên có điều kiện và phương pháp học máy bán giám sát.  Chương 2: Trình bày về tiêu chuẩn kỳ vọng tổng quát và áp dụng tiêu chuẩn kỳ vọng tổng quát vào mô hình trường ngẫu nhiên có điều kiện.  Chương 3: Trình bày về bài toán trích chọn thưc thể trên tập văn bản pháp luật và đề xuất mô hình giải quyết bài toán dựa trên mô hình CRFs theo tiêu chuẩn kỳ vọng tổng quát.  Chương 4: Trình bày các thực nghiệm trên tập dữ liệu sử dụng một số mô hình học máy có giám sát CRFs, và mô hình học máy bán giám sát CRFs theo chuẩn hóa entropy và theo tiêu chuẩn kỳ vọng tổng quát; Từ đó đánh giá kết quả thu được. Trong phần kết luận, luận văn tóm tắt lại những công việc đã thực hiện và các kết quả đạt được. Đồng thời cũng đề cập đến những điểm còn hạn chế của - 10 - 10 luận văn và hướng nghiên cứu trong tương lai. - 11 - 11 CHƯƠNG 1 HỌC BÁN GIÁM SÁT THEO MÔ HÌNH TRƯỜNG NGẪU NHIÊN CÓ ĐIỀU KIỆN 1.1. Phương pháp học máy Trường ngẫu nhiên có điều kiện Mô hình trường ngẫu nhiên có điều kiện (Conditional Random Fields, viết tắt là CRFs) được Lafferty và cộng sự, 2001 [LCP01] giới thiệu lần đầu tiên vào năm 2001. CRFs là mô hình dựa trên xác suất có điều kiện, nó cho phép 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 nhiên, khác với các mô hình xác suất khác, CRFs là mô hình đồ thị vô hướng. Điều này cho phép CRFs 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 đồ thị có hướng khác. Theo Lafferty và cộng sự [LCP01], Hanna M. Wallach, 2002 và 2004 [Wal02, Wal04], bản chất “phân phối điều kiện” và “phân phối toàn cục” của CRFs cho phép mô hình này khắc phục được những nhược điểm của các mô hình trước đó 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’. Khi đề cập đến trường ngẫu nhiên có điều kiện, chúng ta sử dụng một số qui ước kí hiệu:  Chữ viết hoa X, Y, Z…kí hiệu các biến ngẫu nhiên.  Chữ thường đậm x, y, t, s,…kí hiệu các vector như vector biểu diễn chuỗi các dữ liệu quan sát, vector biểu diễn chuỗi các nhãn …  Chữ viết thường in đậm và có chỉ số là kí hiệu của một thành phần trong một vector, ví dụ xi chỉ một thành phần tại vị trí i trong vector x.  Chữ viết thường không đậm như x, y,… là kí hiệu các giá trị đơn như một dữ liệu quan sát hay một trạng thái.  S: Tập hữu hạn các trạng thái của một mô hình CRFs. 1.1.1. Khái niệm trường ngẫu nhiên có điều kiện 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 giá 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ữ - 12 - 12 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 phi 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 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) 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 [LCP01]: ))(,,|(),,|( vNYXYPvYXYP vv    (1.1) Ở đâ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 CRFs có dạng: Hình 1. Đồ thị vô hướng mô tả CRFs 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 CRFs. Áp dụng kết quả của J.Hammersley và P. Clifford, 1971 [HC71] cho các trường ngẫu nhiên Markov, sẽ 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 (theo [Wal04]):    CA A AP )|()|( xxy  (1.2) 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 1 cho 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. Yn-1 Y Y Y Y - 13 - 13 1.1.2. Học máy CRFs 1.1.2.1. Hàm tiềm năng của các mô hình CRFs Lafferty và cộng sự [LCP01] giới thiệu phương pháp xác định các hàm tiềm năng cho các mô hình CRFs dựa trên 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. 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|  (1.3) Ở đâ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 (1.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  (1.4) Ở đâ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  (1.5) Đặt ..),...,,( 2,121  là các vector các tham số của mô hình,  đượ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. si = 1 nếu xi=Bill và yi= B_PER 0 nếu ngược lại ti = = 1 nếu xi-1= “Bill”, xi=”Clinton” và yi-1=B_PER,yi=I_PER 0 nếu ngược lại - 14 - 14 1.1.2.2. 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  (1.6)          k k kkkki ysyytyyM ),(),,'(exp),,'( xxx  (1.7) Ở đâ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)} (1.8) Chuỗi y* được xác định bằng thuật toán Viterbi cải tiến [Spr07] như mô tả trong hình 2. Đị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. 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 2, ta suy ra công thức truy hồi   SyyyMyy kjkikiji   ),,(*)(max)( 11 x (1.9) Hình 2. Một bước trong thuật toán Viterbi cải tiến Đặ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 ? Pr Pr )( Ni y )( 1yi )( 2yi )(1 ji y - 15 - 15  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, CRFs 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 MEM [MMI02, Wal04]. Ở phương diện lý thuyết mô hình, ta có thể coi mô hình CRFs 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. 1.1.2.3. Ước lượng tham số cho các mô hình CRFs Kĩ thuật được sử dụng để đánh giá tham số cho một mô hình CRFs 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. Nguyên lý cực đại likelihood được phát biểu như sau: 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. Như vậy, về phương diện toán học, bài toán ước lượng