Báo cáo 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 tồ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 hồn tồ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 tố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 tố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 tố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 tốn Viterbi cải tiến................................... 14 Hình 3/4. Mơ hình đề xuất giải quyết bài tố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 Để hồ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, đồ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à hồ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 để hồ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 tố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 tồ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 tố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 tố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 tồ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 tồ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 tố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 tồn cục vào X. Trong các bài tố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 tố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 tồ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 tố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 tố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 tố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 tồ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 tồ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 tồ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 tốn học, bài tốn ước lượng tham số cho một mơ hình CRFs chính là bài tố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 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 [Mal02]. 1.2. Học máy bán giám sát CRFs 1.2.1. Học máy bán giám sát Trong lý thuyết xác suất, một dãy các biến ngẫu nhiên được gọi là cĩ độc lập cùng phân phối nếu chúng cĩ cùng một phân phối và độc lập với nhau. Các quan sát trong một mẫu thường được giả thiết là độc lập cùng phân phối nhằm làm đơn giản hố tính tốn tốn học bên dưới của nhiều phương pháp thống kê. Trong nhiều ứng dụng, điều này thường khơng thực tế. Trước khi nghiên cứu về - 16 - 16 học máy bán giám sát, tơi giới thiệu sơ bộ về hai phương pháp học máy cơ bản là Học khơng cĩ giám sát và Học cĩ giám sát. 1.2.1.1. Học khơng cĩ giám sát và Học cĩ giám sát Học khơng cĩ giám sát (unsupervised learning): Là phương pháp học máy nhằm tìm ra một mơ hình phù hợp với các quan sát. Cho trước một mẫu chỉ gồm các đối tượng (objects), cần tìm kiếm cấu trúc quan tâm (interesting structures) của dữ liệu, và nhĩm các đối tượng giống nhau. Học khơng giám sát thường coi các đối tượng đầu vào là một tập các biến ngẫu nhiên. Sau đĩ, một mơ hình mật độ kết hợp sẽ được xây dựng cho tập dữ liệu đĩ. Biểu diễn tốn học của phương pháp này như sau: Cho X=(x1 , x2 , …, xn ) là tập hợp gồm n mẫu (examples or points), xi ∈ X với mọi i∈[N]:= {1,2, ..., n}. Thơng thường, ta giả thiết rằng các mẫu được tạo ra một cách độc lập và giống nhau (i.i.d – independently and identically distributed) từ một phân phối chung trên Χ. Mục đích của học khơng giám sát là tìm ra một cấu trúc thơng minh trên tập dữ liệu đĩ. Học khơng cĩ giám sát cĩ thể được dùng kết hợp với suy diễn Bayes (Bayesian inference) để cho ra xác suất cĩ điều kiện (nghĩa là học cĩ giám sát) cho bất kì biến ngẫu nhiên nào khi biết trước các biến khác. Học khơng giám sát cũng hữu ích cho việc nén dữ liệu: về cơ bản, mọi giải thuật nén dữ liệu hoặc là dựa vào một phân bố xác suất trên một tập đầu vào một cách tường minh hay khơng tường minh. Học giám sát (supervised learning): Là phương pháp học máy xây dựng một hàm từ dữ liệu huấn luyện. Cho trước một mẫu bao gồm các cặp đối tượng - nhãn (xi,yi), cần tìm ra mối quan hệ dự đốn giữa các đối tượng và các nhãn. Mục đích là học một phép ánh xạ từ x tới y, khi cho trước một tập huấn luyện - 17 - 17 gồm các cặp (xi,yi), trong đĩ yi ∈ Y gọi là các nhãn hoặc đích của các mẫu Xi. Nếu nhãn là các số, biểu diễn vector cột của các nhãn. Như đã nêu, một yêu cầu chuẩn là các cặp (xi,yi) tuân theo giả thiết i.i.d trải khắp trên X×Y. Nhiệm vụ được định rõ là, ta cĩ thể tính tốn được một phép ánh xạ thơng qua thực thi dự đốn của nĩ trên tập kiểm thử. Nếu các nhãn lớp là liên tục, nhiệm vụ phân lớp được gọi là hồi quy. Cĩ hai họ thuật tốn giám sát: generative model và discriminative model: Generative model: Phương pháp này sẽ tạo ra một mơ hình mật độ phụ thuộc vào lớp (class-conditional density) p(x|y) bằng một vài thủ tục học khơng giám sát. Một mật độ sinh cĩ thể được suy luận bằng cách sử dụng lý thuyết Bayes. Gọi là mơ hình sinh vì ta cĩ thể tự tạo ra các mẫu dữ liệu. Discriminative model: Phương pháp này sẽ thay vì đánh giá xi được tạo ra như thế nào mà tập trung đánh giá p(y|x) . Một vài phương pháp discriminative hạn chế chúng để mơ hình xem p(y|x) lớn hơn hoặc nhỏ hơn 0.5, ví dụ như SVM. Trong thực hành, phương pháp này thường được đánh giá là hiệu quả hơn phương pháp sinh (generative). Để cĩ thể giải quyết một bài tốn nào đĩ của học cĩ giám sát người ta phải xem xét nhiều bước khác nhau: 1. Xác định loại của các ví dụ huấn luyện. Trước khi làm bất cứ điều gì, người kĩ sư nên quyết định loại dữ liệu nào sẽ được sử dụng làm ví dụ. Chẳng hạn, đĩ cĩ thể là một kí tự viết tay đơn lẻ, tồn bộ một từ viết tay, hay tồn bộ một dịng chữ viết tay. 2. Thu thập tập huấn luyện. Tập huấn luyện cần đặc trưng cho thực tế sử dụng của hàm chức năng. Vì thế, một tập các đối tượng đầu vào được thu thập và đầu ra tương ứng được thu thập, hoặc từ các chuyên gia hoặc từ việc đo đạc tính tốn. 3. Xác định việc biễu diễn các đặc trưng đầu vào cho hàm chức năng cần tìm. Sự chính xác của hàm chức năng phụ thuộc lớn vào cách các đối - 18 - 18 tượng đầu vào được biểu diễn. Thơng thường, đối tượng đầu vào được chuyển đổi thành một vec-tơ đặc trưng, chứa một số các đặc trưng nhằm mơ tả cho đối tượng đĩ. Số lượng các đặc trưng khơng nên quá lớn, do sự bùng nổ tổ hợp; nhưng phải đủ lớn để dự đốn chính xác đầu ra. 4. Xác định cấu trúc của hàm chức năng cần tìm và giải thuật học tương ứng. Ví dụ, người kĩ sư cĩ thể lựa chọn việc sử dụng mạng nơ-ron nhân tạo hay cây quyết định. 5. Hồn thiện thiết kế. Người kĩ sư sẽ chạy giải thuật học từ tập huấn luyện thu thập được. Các tham số của giải thuật học cĩ thể được điều chỉnh bằng cách tối ưu hĩa hiệu năng trên một tập con (gọi là tập kiểm chứng -validation set) của tập huấn luyện, hay thơng qua kiểm chứng chéo (cross-validation). Sau khi học và điều chỉnh tham số, hiệu năng của giải thuật cĩ thể được đo đạc trên một tập kiểm tra độc lập với tập huấn luyện. Trong “học cĩ giám sát”, các dữ liệu được gán nhãn nên việc giải quyết vấn đề thường thuận lợi hơn rất nhiều. Tuy nhiên, với một số lượng dữ liệu lớn thì cơng việc gán nhãn cho dữ liệu địi hỏi nỗ lực của con người và tốn nhiều thời gian. Cịn “học khơng cĩ giám sát” là mơ hình hĩa một tập dữ liệu, trong đĩ dữ liệu đầu vào chưa được gán nhãn mà nĩ dựa trên mơt mơ hình phù hợp với các quan sát, vì vậy với một số lượng lớn dữ liệu thì sự chính xác của kết quả thu được khơng cao. Thực tế cho thấy rằng, dữ liệu chưa được gán nhãn cĩ thể thu thập được rất nhiều và một cách dễ dàng. Tuy nhiên để xử lý số lượng dữ liệu đĩ cĩ kết quả tốt cũng gặp nhiều khĩ khăn. 1.2.1.2. Học máy bán giám sát “Học máy bán giám sát” là sự kết hợp giữa “học cĩ giám sát” và “học khơng cĩ giám sát”. Với một số lượng lớn dữ liệu, kể cả dữ liệu chưa gán nhãn và những dữ liệu đã được gán nhãn, sẽ được “máy học” giải quyết bằng một cách tốt nhất bằng các giải thuật “học bán giám sát. Từ đĩ, học bán giám sát cĩ thể được xem là: - Học giám sát cộng thêm dữ liệu chưa gán nhãn (Supervised learning +additional unlabeled data). - Học khơng giám sát cộng thêm dữ liệu gán nhãn (Unsupervised learning + additional labeled data). Học bán giám sát chính là cách học sử dụng thơng tin cĩ ở cả dữ liệu gán nhãn (trong tập dữ liệu huấn luyện) lẫn dữ liệu chưa gán nhãn. Các thuật tốn - 19 - 19 học bán giám sát cĩ nhiệm vụ chính là mở rộng tập các dữ liệu gán nhãn ban đầu. Hiệu quả của thuật tốn phụ thuộc vào chất lượng của các mẫu gán nhãn được thêm vào ở mỗi vịng lặp và được đánh giá dựa trên hai tiêu chí: - Các mẫu được thêm vào phải được gán nhãn một cách chính xác. - Các mẫu được thêm vào phải mang lại thơng tin hữu ích cho bộ phân lớp (hoặc dữ liệu huấn luyện). Các phương pháp học bán giám sát sẽ rất hữu ích khi dữ liệu chưa gán nhãn nhiều hơn dữ liệu gán nhãn. Việc thu được dữ liệu gán nhãn là rẻ, nhưng để gán nhãn chúng thì tốn rất nhiều thời gian, cơng sức và tiền bạc. Đĩ là tình trạng của rất nhiều các lĩnh vực ứng dụng trong học máy như: - Trong nhận dạng lời nĩi, ta sẽ dễ dàng ghi lại một lượng lớn các bài diễn thuyết, nhưng để gán nhãn chúng yêu cầu con người phải lắng nghe rồi đánh máy sao chép lại. - Sự phong phú của hàng tỉ các trang web sẵn sàng cho xử lý tự động, nhưng để phân lớp chúng một cách tin cậy địi hỏi con người phải đọc chúng. - ... Học bán giám sát là việc học trên cả dữ liệu đã và chưa được gán nhãn. Từ một số lượng lớn các dữ liệu chưa được gán nhãn, và một tập với số luợng nhỏ dữ liệu đã được gán nhãn ban đầu (thường gọi là seed set) để xây dựng một bộ phân lớp thậm chí là tốt hơn. Trong quá trình học như thế, phương pháp học sẽ tận dụng được những thơng tin phong phú của dữ liệu chưa gán nhãn, mà chỉ yêu cầu một số lượng rất nhỏ các dữ liệu đã gán nhãn. 1.2.1.3. Một số thuật tốn học máy bán giám sát Theo Zhi-Hua Zhou và Ming Li, 2010 [ZL10], cĩ rất nhiều các thuật tốn học máy bán giám sát và cĩ thể chia thành bốn nhĩm phương pháp như sau: phương pháp sinh [MU97, NCT00, SL94], S3VMs (Semi-Supervised Support Vector Machines – phương pháp máy vectơ hỗ trợ bán giám sát) [CZ05, GY05, Joa99, LJ05], phương pháp dựa trên đồ thị [BN04, BNS05, BNS06, ZBL04, ZGL03] và phương pháp dựa trên mâu thuẫn [ZL07, ZL05, ZZY07, ZC06, NG00, GZ00, BS06, BM98]. - Trong phương pháp sinh, cả tập mẫu gán nhãn và chưa gán nhãn được giả thiết được sinh ra từ mơ hình cùng tham số. Do đĩ, những tham số mơ hình cĩ liên kết trực tiếp những mẫu chưa gán nhãn với mục tiêu học. Những mơ hình trong phương pháp này thường coi những nhãn của dữ liệu chưa gán nhãn là những giá trị thiếu của tham số mơ hình và sử dụng thuật tốn cực đại hĩa kỳ vọng EM [DLR77] để tính tốn ước lượng cực - 20 - 20 đại likelihood của tham số mơ hình. Những thuật tốn trong phương pháp này khác nhau ở mơ hình sinh được sử dụng để phù hợp với dữ liệu, ví dụ phương pháp pha trộn Gaussian [SL94], phương pháp Nạve Bayes [NCT00]. Những mơ hình sinh thực thi đơn giản, dễ dàng và cĩ thể hiệu quả hơn mơ hình discriminative khi học với mẫu gán nhãn nhỏ. Tuy nhiên, nhĩm thuật tốn này cĩ nhược điểm lớn đĩ là khi giả thiết mơ hình sai hoặc mơ hình sử dụng tập dữ liệu chưa gán nhãn lớn thì việc thực thi bị kém hiệu quả. Do đĩ, để mơ hình này thực thi cĩ hiệu quả trong những ứng dụng thực, cần phải tạo được mơ hình sinh chính xác dựa trên miền tri thức, hoặc người ta cĩ thể kết hợp những mặt tích cực của mơ hình sinh và mơ hình discriminative [AG05, FUS05]. Một số thuật tốn điển hình của phương pháp này được Xiaojin Zhu đề cập trong [Zhu08] như: Thuật tốn học bán giám sát cực đại kỳ vọng EM địa phương, Thuật tốn Self-training... - Phương pháp S3VMs cố gắng sử dụng dữ liệu chưa gán nhãn để điều chỉnh đường biên quyết định được học từ tập nhỏ những mẫu dữ liệu gán nhãn, nhờ đĩ cĩ thể đi qua được những vùng dày đặc trong khi vẫn giữ được phân lớp chính xác cho dữ liệu gán nhãn. T. Joachims, 1999 [Joa99] đề xuất mơ hình TSVM (Transductive Support Vector Machine). Đầu tiên, thuật tốn này khởi tạo một SVM sử dụng những mẫu gán nhãn và gán những nhãn tiềm năng cho dữ liệu chưa gán nhãn. Sau đĩ, nĩ lặp lại việc cực đại hĩa biên của cả dữ liệu gán nhãn và chưa gán nhãn với những nhãn tiềm năng bằng cách đặt nhãn của dữ liệu chưa gán nhãn trên các mặt của biên quyết định. Cách này cĩ thể đạt được giải pháp tối ưu đĩ là biên quyết định khơng chỉ phân lớp chính xác dữ liệu gán nhãn mà cịn tránh được việc đi qua vùng mật độ cao. Tuy nhiên, độ khơng lồi của hàm thiệt hại (loss function) trong TSVM sẽ dẫn đến thực tế là cĩ nhiều điểm tối ưu cục bộ. Do đĩ nhiều nghiên cứu được đề xuất để giảm tác động tiêu cực này. - Phương pháp học bán giám sát dựa trên đồ thị đầu tiên cĩ thể thực thi được đề xuất bởi Blum và Chawla, 2001 [BC01], họ xây dựng một đồ thị với các nút là những mẫu huấn luyện (cả gán nhãn và chưa gán nhãn) và cạnh giữa các nút thể hiện mối quan hệ giữa những mẫu tương ứng ví dụ như quan hệ đồng dạng. Dựa trên đồ thị này, vấn đề học bán giám sát cĩ thể được giải quyết bằng việc tìm đường cắt nhỏ nhất của đồ thị mà theo đĩ những nút trong mỗi phần cĩ cùng nhãn. Sau đĩ, A. Blum và cộng sự, 2004 [BLR04] làm nhiễu đồ thị bằng một số điểm ngẫu nhiên và tạo ra - 21 - 21 đường cắt “mềm” nhỏ nhất sử dụng phiếu bầu tối đa. Cả [BC01] và [BLR04] đều sử dụng hàm dự đốn rời rạc ví dụ dự đốn của những mẫu chưa gán nhãn cĩ thể là một trong các nhãn cĩ thể. X. Zhu và cộng sự, 2003 [ZGL03] mở rộng hàm dự đốn rời rạc thành hàm liên tục. D. Zhou và cộng sự, 2004 [ZBL04] định nghĩa độ thiệt hại bình phương của hàm dự đốn thơng qua cả dữ liệu gán nhãn và chưa gán nhãn và đồ thị Laplacian chuẩn hĩa. Hầu hết những nghiên cứu trước đây về học bán giám sát dựa trên đồ thị thường tập trung vào việc xây dựng một đồ thị phản ánh được mối quan hệ thiết yếu gữa những mẫu, đây là điều then chốt cĩ tác động lớn đến thực thi việc học. Sau này, nhiều nghiên cứu đã cố gắng cải thiện đồ thị bằng việc thêm vào những đặc trưng miền tri thức. X. Zhang và W. S. Lee, 2007 [ZL07b] chọn dải thơng RBF tốt hơn để cực tiểu hĩa lỗi dự đốn trên dữ liệu gán nhãn sử dụng đánh giá chéo. M. Hein và M. Maier, 2007 [HM07] cố gắng giảm dữ liệu nhiễu để đạt được đồ thị tốt hơn... Mặc dù phương pháp học bán giám sát dựa trên đồ thị được ứng dụng khá rộng rãi nhưng nĩ cĩ nhược điểm lớn về quy mơ. - Phương pháp học bán giám sát dựa trên mâu thuẫn được đưa ra gần đây bởi Z. H. Zhou, 2008 [Zho08] dựa trên những nghiên cứu của A. Blum và T. Mitchell, 1998 [BM98]. Trong phương pháp này, nhiều máy học được huấn luyện cho cùng tác vụ và mẫu thuẫn giữa các máy học sẽ nảy sinh trong quá trình học. Ở đây, dữ liệu chưa gán nhãn được coi là “cơ sở” cho việc trao đổi thơng tin. Nếu một máy học nào chắc chắn hơn các máy học khác về một mẫu chưa gán nhãn đang tranh luận thì máy học đĩ sẽ dạy cho các máy học khác về mẫu này, sau đĩ mẫu này cĩ thể được chọn để truy vấn. Do đĩ, phương pháp này khơng cĩ những nhược điểm như những mơ hình khác như vi phạm giả thiết mơ hình, hàm thiệt hại khơng lồi, hay nhược điểm về quy mơ của thuật tốn học. Thuật tốn điển hình của nhĩm phương pháp này được Ziaojin Zhu đề cập trong [Zhu08] là Thuật tốn Co-training. Mỗi phương pháp học bán giám sát đều cĩ những ưu và nhược điểm riêng. Do đĩ tùy thuộc vào ứng dụng và loại dữ liệu mà lựa chọn phương pháp học và thuật tốn cụ thể cho phù hợp. 1.2.2. Sơ bộ về mơ hình học máy bán giám sát CRFs Như phân tích ở 1.2.1, cĩ nhiều phương pháp học bán giám sát và mỗi phương pháp cĩ những ưu và nhược điểm riêng. Luận văn của tác giả tập trung - 22 - 22 nghiên cứu mơ hình học bán giám sát CRFs, mơ hình này thuộc nhĩm phương pháp sinh. Mơ hình học bán giám sát CRFs là mơ hình kết hợp được cả dữ liệu chuỗi đã gán nhãn và chưa gán nhãn; mơ hình đã khắc phục được những yếu điểm của các mơ hình khác và được ứng dụng trong nhiều nghiên cứu về xử lý ngơn ngữ. Feng Jiao và cộng sự, 2006 [JWL06] đã đề xuất thuật tốn tận dụng dữ liệu chưa gán nhãn qua chuẩn hĩa entropy (entropy regularization) – thuật tốn được mở rộng từ tiếp cận được đề xuất trong [GB04] cho mơ hình CRFs cĩ cấu trúc. Một tiếp cận khác, Gideon S.Mann và Andrew McCallum [MC08], Gregory Druck và cộng sự [DMC08] đề xuất phương pháp học bán giám sát CRFs sử dụng tiêu chuẩn kỳ vọng tổng quát GE, phương pháp này sẽ giới thiệu trong mục 2.2. Trong phương pháp này, thay vì sử dụng các mẫu gán nhãn máy học sẽ truy cập các đặc trưng gán nhãn. Những đặc trưng này cĩ thể được gán nhãn với chi phí thấp hơn nhiều so với gán nhãn tồn bộ mẫu dữ liệu vì việc gán nhãn đặc trưng cĩ thể chỉ cần gán nhãn cho những phần nhỏ của cấu trúc chuỗi hoặc cây. Bên cạnh đĩ, việc sử dụng tiêu chuẩn kỳ vọng tổng quát xác lập các tham số trong huấn luyện hàm mục tiêu cho phép tạo được kỳ vọng mơ hình gần với phân phối mục tiêu. Luận văn sẽ tiến hành thực thi mơ hình này trên tập dữ liệu tiếng Việt và so sánh với một số phương pháp khác. Kết quả thực nghiệm sẽ thể hiện ở Chương 4. 1.3. Kết luận chương 1 Chương này giới thiệu về mơ hình trường ngẫu nhiên cĩ điều kiện – một mơ hình khá phổ biến và hiệu quả trong các ứng dụng về xử lý ngơn ngữ tự nhiên - và giới thiệu về các phương pháp học máy bán giám sát – một phương pháp được coi là tận dụng được các ưu điểm của hai phương pháp học máy cĩ giám sát và học khơng cĩ giám sát. Từ đĩ, sơ lược về một số mơ hình học máy bán giám sát áp dụng vào mơ hình trường ngẫu nhiên cĩ điều kiện, nổi bật là mơ hình học máy bán giám sát CRFs sử dụng tiêu chuẩn kỳ vọng tổng quát; mơ hình này sẽ được giới thiệu và phân tích trong chương tiếp theo của luận văn. - 23 - 23 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 2.1. Tiêu chuẩn kỳ vọng tổng quát 2.1.1. Giới thiệu sơ bộ Những phương pháp học cĩ giám sát địi hỏi tập các trường hợp gán nhãn lớn và nĩ hạn chế khả năng học ở những miền tri thức mới. Những phương pháp học bán giám sát với mục tiêu tăng cường sử dụng tập các trường hợp chưa gán nhãn là giải pháp lý tưởng nhằm giảm các nỗ lực gán nhãn dữ liệu. Tuy nhiên, phương pháp này thường phức tạp về tính tốn và phải tính đến độ tin cậy trong các trường hợp siêu tham số nhạy cảm của những phương pháp học bán giám sát. Trong khi đĩ, chúng ta cần một phương pháp đơn giản nhưng hiệu quả cho phép thực hiện những mơ hình huấn luyện trên những miền tri thức mới và địi hỏi tối thiểu việc gán nhãn. Một phương pháp bán giám sát mới kết hợp tri thức tiền nhiệm giữa những đặc trưng và lớp vào việc huấn luyện sử dụng tiêu chuẩn kỳ vọng tổng quát (GEC), được Andrew McCallum và cộng sự, 2007 [CMD07] giới thiệu, đã và đang gây được nhiều chú ý và đưa vào nhiều ứng dụng. Tiêu chuẩn kỳ vọng tổng quát (GEC) [CMD07] là những điều kiện (term) trong hàm mục tiêu huấn luyện cho phép gán giá trị cho kỳ vọng mơ hình. GEC cĩ điểm giống với phương pháp mơ-men, nhưng cho phép biểu diễn những tham chiếu vơ hướng tùy ý trên các kỳ vọng của những hàm tùy biến mà khơng yêu cầu sự cân bằng mơ-men mẫu và mơ-men mơ hình. Đồng thời, GEC cũng cĩ 3 điểm khác căn bản với những hàm mục tiêu huấn luyện truyền thống; Đĩ là, khơng cần ánh xạ một-một giữa những điều kiện GEC và những tham số mơ hình, những kỳ vọng mơ hình cho những điều kiện GEC khác nhau cĩ thể được huấn luyện trên những tập dữ liệu khác nhau, kỳ vọng tham chiếu (hàm score) cĩ thể xác định từ nguồn khác như những tác vụ khác, những tri thức tiền nghiệm. Phương pháp được sử dụng trong luận văn này là sử dụng kết hợp những đặc trưng và lớp biết trước. Kỳ vọng của mơ hình được ước lượng từ những phân phối lớp được huấn luyện từ những đặc trưng lựa chọn và hàm tỷ số là phân kỳ KL (S. Kullback và R. A. Leibler, 1951 [KL51], S. Kullback, 1959, [Kul59]) – là độ đo khơng đối xứng giữa 2 phân bố xác suất – phân phối xác - 24 - 24 suất thực và phân phối xác suất mục tiêu - từ những phân phối tham chiếu được ước lượng từ những nguồn đã cĩ. Kết hợp những điều kiện GEC với tham số đã biết cho phép sử dụng những mẫu đồng xuất hiện trong dữ liệu chưa gán nhãn để học những tham số cho những đặc trưng mà chưa cĩ trong thơng tin tiền nghiệm. Phương pháp áp dụng trong luận văn để thực hiện tác vụ Nhận dạng tên thực thể (NER) như tên người, tên địa điểm, tổ chức và những thực thể khác. 2.1.2. Tiêu chuẩn kỳ vọng tổng quát Những mơ hình học bán giám sát trước đây đã khắc phục một số hạn chế là sử dụng dữ liệu được gán nhãn đầy đủ với dữ liệu khơng được gán nhãn hoặc với các ràng buộc (ví dụ những đặc trưng được đánh dấu với nhãn chính của nĩ). GEC cĩ thể sử dụng nhiều thơng tin hơn những mơ hình trước nĩ. Trong GEC cĩ thể tận dụng thuận lợi của phân bố xác suất điều kiện của những nhãn cho trước một đặc trưng (p(y|fk(x) = 1)). Thơng tin này cung cấp ràng buộc phong phú hơn cho mơ hình trong khi vẫn giữ lại tính dễ dịch. Con người thường cĩ trực giác tốt về khả năng dự đốn quan hệ của những đặc trưng khác nhau. Ví dụ, rõ ràng là xác suất của nhãn PERSON gán cho từ đặc trưng JOHN là cao, cĩ thể đến 0.95 trong khi cho từ BROWN thì tỉ lệ thấp hơn cĩ thể là 0.4. Những phân bố cần được ước lượng với độ chính xác cao và việc tự do biểu diễn mức độ phân bố tốt hơn nhiều so với việc sử dụng tín hiệu giám sát nhị phân. Thuận lợi khác của việc sử dụng những phân bố xác suất điều kiện - ràng buộc xác suất là chúng cĩ thể dễ dàng ước lượng từ dữ liệu. Đối với đặc trưng bắt đầu bằng chữ hoa INITIAL-CAPITAL, tơi xác định tất cả thẻ với đặc trưng đĩ và đếm số nhãn xuất hiện cùng. GEC cố gắng khớp những phân bố xác suất điều kiện này bằng kỳ vọng mơ hình trên dữ liệu chưa gán nhãn, ví dụ khuyến khích mơ hình dự đốn rằng tỉ lệ nhãn PERSON gán cho từ John cĩ thể là 0.95 trên tất cả điều kiện chưa gán nhãn. Cho X là tập các biến kí hiệu là x X. Cho θ là những tham số của một số mơ hình, cho phép xác định phân bố xác suất trên tập X, pθ(X). Kỳ vọng của các hàm f(X) theo mơ hình là (2.1) Trong đĩ, f(x) là một hàm bất kỳ của biến x cho giá trị vơ hướng hoặc vecto. Hàm này cĩ thể chỉ phụ thuộc vào tập con của tập biến x. - 25 - 25 Và những kỳ vọng cũng cĩ thể được xác định trên những phép gán giá trị biến, ví dụ, khi thực hiện huấn luyện xác suất điều kiện của một số mơ hình. Trong trường hợp này, những biến được chia thành biến đầu vào X và biến đầu ra Y. Một tập các phép gán cho biến đầu vào (những trường hợp dữ liệu huấn luyện) = {x1, x2,...} cĩ thể cho trước và kỳ vọng điều kiện là (2.2) Một GEC được định nghĩa là một hàm G, sử dụng tham số là kỳ vọng của mơ hình f(X) và trả về một giá trị vơ hướng, giá trị này được bổ sung vào như là một điều kiện trong hàm mục tiêu ước lượng tham số: (2.3) Trong một số trường hợp, G cĩ thể được định nghĩa dựa trên khoảng cách đến giá trị đích cho Eθ[f(X)]. Cho là giá trị đích và cho ∆(·, ·) là hàm khoảng cách. Trong trường hợp này, G cĩ thể định nghĩa là: (2.4) Như đã mơ tả ở trên, GEC là một dạng tổng quát, nĩ coi các phương pháp ước lượng tham số truyền thống khác là trường hợp đặc biệt. Cĩ thể phân chia GEC theo mức độ linh hoạt như sau: 1. Một GEC được xác định một cách độc lập theo tham số hĩa. Trong các phương pháp ước lượng tham số truyền thống - phương pháp đồ thị, cĩ sự tương ứng một-một giữa các tập con của các biến sử dụng trong mỗi phần tham số hĩa của mơ hình và tập con của các biến trong đĩ các kỳ vọng được xac định cho hàm mục tiêu. Trong GEC, mỗi tập con này cĩ thể được lựa chọn độc lập. 2. Những GEC điều kiện khác nhau khơng cần tất cả các điều kiện cho những trường hợp giống nhau, chúng cĩ thể tác động đến những tập dữ liệu khác nhau hoặc những sự kết hợp khác nhau của những tập dữ liệu. 3. “Dấu hiệu huấn luyện” cĩ giám sát bất kể ở kỳ vọng đích hay tổng quát, trạng thái của hàm tỷ số, G, cĩ thể xác định từ dữ liệu huấn luyện gán nhãn hoặc bất kỳ nguồn nào, bao gồm cả những tác vụ khác hoặc tri thức tiền nghiệm. Do đĩ, một GEC cĩ thể được xác định một cách độc lập với tham số hĩa và độc lập với những lựa chọn của bất kỳ tập dữ liệu điều kiện nào. Và một GEC cĩ - 26 - 26 thể hoạt động trên một số tập con bất kỳ của các biến trong x. Thêm vào đĩ, hàm f cĩ thể được định nghĩa theo kỳ vọng sinh ra mơ-men của phân bố pθ(X) hoặc bất kỳ kỳ vọng nào khác. Hàm tỷ số G và hàm khoảng cách ∆ cĩ thể dựa trên nguyên lý thơng tin hoặc những hàm bất kỳ. Những giá trị GEC cĩ thể được sử dụng như là những thành phần duy nhất của hàm mục tiêu ước lượng tham số hoặc chúng cĩ thể được sử dụng kết hợp với những giá trị khác. Ví dụ, GEC cĩ thể được áp dụng trong nhiều sơ đồ học khác nhau trong đĩ sử dụng những hàm mục tiêu, bao gồm học kết hợp/sinh, học khơng giám sát, học điều kiện/phân biệt, học cĩ giám sát, học với những biến ẩn, học cĩ cấu trúc… 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 Nhìn chung, GEC biểu diễn một tham chiếu trên giá trị của kỳ vọng mơ hình [CMD07]. Một kiểu tham chiếu cĩ thể được biểu diễn bằng hàm khoảng cách , kỳ vọng mục tiêu , dữ liệu D, hàm f và phân bố mơ hình , hàm mục tiêu GEC là . Trong [MC10], Gideon S. Mann và Andrew McCallum đặt những hàm là phân bố xác suất điều kiện và đặt , phân kỳ KL là độ đo khơng đối xứng giữa 2 phân bố xác suất p và q. Đối với huấn luyện bán giám sát của CRFs, các tác giả bổ sung hàm mục tiêu với điều kiện chuẩn hĩa. (2.5) Trong đĩ là phân bố mục tiêu và (2.6) Với tiềm năng khơng chính thức (2.7) Trong đĩ fm(x,j) là một đặc trưng phụ thuộc chỉ vào chuỗi quan sát x và j* được định nghĩa là {j:fm(x,j)=1} và Um là tập các chuỗi mà fm(x,j) cĩ mặt cho một số j. Tính tốn Gradient (Độ chênh lệch) - 27 - 27 Để tính độ chênh lệch của GEC, D( , đầu tiên giảm những điều kiện ràng buộc cĩ tính đến dẫn xuất thành phần và các tác giả thu được độ chênh lệch như sau: (2.8) Trong đĩ y-j = . Bước cuối cùng như sau từ định nghĩa của xác suất biên P(yi|x). Bây giờ, nhận được dạng quen thuộc lấy ra độ chênh lệch của chuỗi nhãn cụ thể, tiếp tục: (2.9) Sau khi kết hợp các số hạng và sắp xếp lại, sẽ thu được dạng cuối cùng của độ chênh lệch như sau: (2.10) Ở đây, số hạng thứ 2 dễ dàng được thu thập từ thuật tốn tiến/lùi, nhưng đạt được số hạng thứ nhất thì ít nhiều phức tạp hơn. Tính tốn số hạng này một cách chất phác sẽ địi hỏi thực thi nhiều tiến/lùi bị ràng buộc. Ở đây, các tác giả trình - 28 - 28 bày một phương pháp hiệu quả hơn và chỉ địi hỏi một thực thi của tiến/lùi. Đầu tiên, chia xác suất thành 2 phần: . (2.11) Vậy làm thế nào để tính những số hạng này một cách hiệu quả? Tương tự như thuật tốn tiến/lùi, xây dựng một giàn kết quả trung gian: (2.12) Để hiệu quả, được lưu ở mỗi giai đoạn trong giàn. cĩ thể được tính theo cách tương tự. Để tính giàn cần thời gian O(ns2) và một giàn phải được tính cho mỗi nhãn, do đĩ thời gian là O(ns3). 2.3. Kết luận chương 2 Chương 2 tập trung nghiên cứu định nghĩa tiêu chuẩn kỳ vọng tổng quát, phân tích cách xây dựng cơng thức, cách phân chia tiêu chuẩn kỳ vọng tổng quát. Từ đĩ áp dụng vào mơ hình học máy bán giám sát CRFs, thiết lập các thơng số cho mơ hình theo tiêu chuẩn kỳ vọng tổng quát như bổ sung hàm mục tiêu với điều kiện chuẩn hĩa, tính tốn Gradient. Chương tiếp theo, luận văn đề nghị một 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 áp dụng cho bài tốn trích chọn thơng tin từ văn bản pháp luật tiếng Việt. - 29 - 29 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 3.1. Trích chọn thơng tin từ văn bản pháp luật tiếng Việt 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 Trong cơng tác điều tra các vụ án và quản lý đối tượng, bên cạnh việc tiến hành các biện pháp nghiệp vụ các điều tra viên đồng thời phải lập các loại biên bản như biên bản lấy lời khai người bị hại, biên bản lấy lời khai người làm chứng, biên bản khám nghiệm hiện trường, biên bản về việc thu thập chứng cứ… tất cả được lưu vào hồ sơ. Như vậy, hồ sơ đối tượng, hồ sơ vụ án sẽ lưu giữ tất cả những thơng tin về đối tượng tham gia vụ án, về các tình tiết vụ án, mơ tả chi tiết phương thức, thủ đoạn, cơng cụ sử dụng, thời gian, địa điểm xảy ra vụ án… Đây chính là những bằng chứng để xét xử vụ án, đồng thời việc lưu giữ những thơng tin này cĩ ý nghĩa quan trọng trong việc thống kê, phân tích xu hướng, dự báo tình hình, cũng như cung cấp thơng tin cho những vụ án liên quan về cùng đối tượng, cùng thời gian, địa điểm, cùng phương thức thủ đoạn… giúp cho việc phá án được nhanh chĩng hơn. Luận văn tập trung nghiên cứu trên tập các hồ sơ điều tra vụ án với ngơn ngữ tiếng Việt. Tiếng Việt cũng như bất kỳ một ngơn ngữ nào cũng cĩ những đặc trưng riêng và việc nghiên cứu những đặc trưng này là cơ sở cho việc phân tích, lựa chọn và trích rút thơng tin trên văn bản tiếng Việt. Tiếng Việt thuộc ngơn ngữ đơn lập, tức là mỗi một tiếng (âm tiết) được phát âm tách rời nhau và được thể hiện bằng một chữ viết. Đặc điểm này thể hiện rõ rệt ở tất cả các mặt ngữ âm, từ vựng và ngữ pháp.  Đặc điểm ngữ âm o Trong tiếng Việt cĩ một loại đơn vị đặc biệt gọi là tiếng. Về mặt ngữ âm, mỗi tiếng là một âm tiết.  Đặc điểm từ vựng o Mỗi tiếng, nĩi chung, là một yếu tố cĩ nghĩa. Tiếng là đơn vị cơ sở của hệ thống các đơn vị cĩ nghĩa của tiếng Việt. Từ tiếng, người ta - 30 - 30 tạo ra các đơn vị từ vựng khác để định danh sự vật, hiện tượng,… chủ yếu nhờ phương thức ghép và phương thức láy. o Việc tạo ra các đơn vị từ vựng ở phương thức ghép luơn chịu sự chi phối của quy luật kết hợp ngữ nghĩa, ví dụ: đất nước, máy bay, nhà lầu xe hơi, nhà tan cửa nát,… Hiện nay, đây là phương thức chủ yếu để sản sinh ra các đơn vị từ vựng. Theo phương thức này, tiếng Việt triệt để sử dụng các yếu tố cấu tạo từ thuần Việt hay vay mượn từ các ngơn ngữ khác để tạo ra các từ, ngữ mới, ví dụ: tiếp thị, karaoke, thư điện tử (e-mail), thư thoại (voice mail), phiên bản (version), xa lộ thơng tin, siêu liên kết văn bản, truy cập ngẫu nhiên, v.v… o Việc tạo ra các đơn vị từ vựng ở phương thức láy thì quy luật phối hợp ngữ âm chi phối chủ yếu việc tạo ra các đơn vị từ vựng, chẳng hạn: chơm chỉa, chỏng chơ, đỏng đa đỏng đảnh, thơ thẩn, lúng lá lúng liếng, v.v… o Vốn từ vựng tối thiểu của tiếng Việt phần lớn là các từ đơn tiết (một âm tiết, một tiếng). Sự linh hoạt trong sử dụng, việc tạo ra các từ ngữ mới một cách dễ dàng đã tạo điều kiện thuận lợi cho sự phát triển vốn từ, vừa phong phú về số lượng, vừa đa dạng trong hoạt động. Cùng một sự vật, hiện tượng, một hoạt động hay một đặc trưng, cĩ thể cĩ nhiều từ ngữ khác nhau biểu thị. Tiềm năng của vốn từ ngữ tiếng Việt được phát huy cao độ trong các phong cách chức năng ngơn ngữ, đặc biệt là trong phong cách ngơn ngữ nghệ thuật. Hiện nay, do sự phát triển vượt bậc của khoa học-kĩ thuật, đặc biệt là cơng nghệ thơng tin, thì tiềm năng đĩ cịn được phát huy mạnh mẽ hơn.  Đặc điểm ngữ pháp o Từ của tiếng Việt khơng biến đổi hình thái. Đặc điểm này sẽ chi phối các đặc điểm ngữ pháp khác. Khi từ kết hợp từ thành các kết cấu như ngữ, câu, tiếng Việt rất coi trọng phương thức trật tự từ và hư từ. o Việc sắp xếp các từ theo một trật tự nhất định là cách chủ yếu để biểu thị các quan hệ cú pháp. Trong tiếng Việt khi nĩi “Anh ta lại đến” là khác với “Lại đến anh ta“. Khi các từ cùng loại kết hợp với nhau theo quan hệ chính phụ thì từ đứng trước giữ vai trị chính, từ đứng sau giữ vai trị phụ. Nhờ trật tự kết hợp của từ mà “củ cải” khác với “cải củ“, “tình cảm” khác với “cảm tình“. Trật tự chủ ngữ - 31 - 31 đứng trước, vị ngữ đứng sau là trật tự phổ biến của kết cấu câu tiếng Việt. o Phương thức hư từ cũng là phương thức ngữ pháp chủ yếu của tiếng Việt. Nhờ hư từ mà tổ hợp “anh của em” khác với tổ hợp “anh và em“, “anh vì em“. Hư từ cùng với trật tự từ cho phép tiếng Việt tạo ra nhiều câu cùng cĩ nội dung thơng báo cơ bản như nhau nhưng khác nhau về sắc thái biểu cảm. o Ngồi trật tự từ và hư từ, tiếng Việt cịn sử dụng phương thức ngữ điệu. Ngữ điệu giữ vai trị trong việc biểu hiện quan hệ cú pháp của các yếu tố trong câu, nhờ đĩ nhằm đưa ra nội dung muốn thơng báo. Trên văn bản, ngữ điệu thường được biểu hiện bằng dấu câu. Chúng ta thử so sánh 2 câu sau để thấy sự khác nhau trong nội dung thơng báo: - Đêm hơm qua, cầu gãy. - Đêm hơm, qua cầu gãy. Các đặc điểm tiếng Việt sẽ được tiếp tục đề cập ở các phân tích trong mơ hình các phần tiếp theo. 3.1.2. Bài tốn trích chọn thơng tin văn bản pháp luật tiếng Việt Như phân tích ở trên, trong hồ sơ vụ án sẽ chứa rất nhiều thơng tin hữu ích. Trong khuơn khổ luận văn này, tác giả tập trung vào việc xác định những thực thể quan tâm cĩ trong hồ sơ. Việc xác định các thực thể này là tạo cơ sở cho các bài tốn hay yêu cầu cao hơn như hệ thống trả lời tự động, thống kê, dự báo… Bài tốn mà luận văn sẽ giải quyết được phát biểu đơn giản như sau: Đầu vào: Các hồ sơ vụ án. Yêu cầu: Xác định các thực thể cĩ trong hồ sơ. Tuy nhiên, do yêu cầu chính trị và yêu cầu nghiệp vụ, các hồ sơ vụ án là các tài liệu mật, khơng được sử dụng rộng rãi. Vì lý do đĩ, nên trong khuơn khổ luận văn này tơi khơng sử dụng hồ sơ vụ án làm dữ liệu, thay vào đĩ tơi sử dụng các bài báo là các phĩng sự điều tra, ghi chép về các vụ án được đăng tải cơng khai trên website chính thức của Bộ Cơng an là 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 3.2.1. Một số phân tích Bài tốn gán nhãn tên thực thể này bản chất là gán nhãn tên thực thể cho mỗi từ sau khi được phân tách. Các loại thực thể được xác định trong luận văn dựa theo các thực thể trong tác vụ CoNLL2003 bao gồm: LOC (Location), PER - 32 - 32 (Person), ORG (Organization) và MISC (Miscellaneous). Do đĩ, các nhãn thực thể được sử dụng ở đây là: - B-TYPE: nhãn đánh dấu từ bắt đầu của nhãn NER - I-TYPE: nhãn đánh dấu cho từ tiếp theo trong nhãn NER - O: nhãn đánh dấu cho từ khơng thuộc nhĩm thực thể nào. (nhãn TYPE sẽ thuộc vào một trong bốn loại thực thể trên) Ví dụ: Thủy_thủ O Nguyễn_Ngọc_Hới B-PER xã B-LOC Quảng_Phúc I-LOC , O Quảng_Trạch B-LOC từng O là O bộ_đội O đi O chiến_trường O B B-MISC năm O 1968 O . O Để nâng cao kết quả, người ta đưa thêm đặc trưng từ loại nên với mỗi từ được gán thêm nhãn từ loại POS (Part of Speech). Do đĩ tập dữ liệu huấn luyện - training và dữ liệu kiểm tra – testing phải được xây dựng theo cùng định dạng: Mỗi từ nằm trên một dịng; Một dịng trống được thêm vào sau mỗi dấu kết thúc câu; Mỗi dịng (token) bao gồm các thành phần: . 3.2.2. Mơ hình đề nghị Từ những phân tích trên đây, tác giả đề xuất xây dựng mơ hình các bước trong quá trình nhận dạng thực thể như sau: Quá trình nhận dạng được chia làm hai giai đoạn như sau: - 33 - 33 Giai đoạn 1. Các bước tiền xử lý dữ liệu Mơ hình CRFs Dữ liệu kiểm tra Kết quả đánh giá mơ hình Mơ hình CRFs với GEC (được hiệu chỉnh sau mỗi bước) Dữ liệu cĩ nhãn và dữ liệu khơng cĩ nhãn (cập nhật sau mỗi bước học) Kết thúc học ? Giai đoạn 2. Hoc bán giám sát CRFs voi GEC Tập các văn bản đầu vào chứa các đoạn văn Tập dữ liệu ra với định dạng Module tách từ Tiếng Việt Gán nhãn POS Gán nhãn NER - 34 - 34 Hình 3/4. Mơ hình đề xuất giải quyết bài tốn Giai đoạn 1: Tập văn bản dữ liệu cần tiến hành hai bước tiền xử lý tự bán tự động đĩ là tách từ, gán nhãn từ loại POS (Part Of Speech), gán nhãn thực thể NER (Named Entities Recognition). Bước 1: Sử dụng phần mềm tách từ tự động JvnSegmenter của NCS Nguyễn Cẩm Tú tại trang web . Đây là phần mềm tách từ tự động dựa trên phương pháp trường điều kiện ngẫu nhiên CRFs [1], phương pháp này chứng tỏ hiệu lực tốt trong nhiều bài tốn xử lý văn bản, đặc biệt là các bài tốn trích chọn thơng tin trên Web. Sau bước này ta thu được tập dữ liệu gồm mỗi từ nằm trên một dịng. Và giữa mỗi câu cĩ một dịng trống. Bước 2: Tiến hành gán nhãn POS cho mỗi từ. Việc gán nhãn POS tơi cĩ sử dụng tool vnTagger của tác giả Lê Hồng Phương tại trang web . Đây là phần mềm gán nhãn từ loại POS cho tiếng Việt cĩ độ chính xác cao (khoảng 95%), phần mềm được viết dựa trên phương pháp maximum entropy. Sau đĩ tiến hành kiểm tra nhãn POS lại một cách thủ cơng. Bước 3: Tiến hành gán nhãn NER cho mỗi từ một cách thủ cơng. Sau bước này sẽ thu được tập dữ liệu với định dạng mong muốn. Giai đoạn 2: Tiến hành nhận dạng tên thực thể bằng Mallet Tool. Mallet là bộ cơng cụ được xây dựng bởi Andrew McCallum và đồng nghiệp năm 2002 và ngày càng được cải tiến và nâng cấp phiên bản. Đây là một bộ cơng cụ với nhiều chức năng xử lý ngơn ngữ tự nhiên như: Phân lớp, phân cụm, triết lọc thơng tin và những ứng dụng học máy khác. Bộ cơng cụ này được cơng bố rộng rãi tại website Trong đĩ, Andrew McCallum và đồng nghiệp xây dựng rất nhiều cơng cụ gán nhãn dữ liệu cho những ứng dụng như trích chọn tên thực thể. Những thuật tốn gán nhãn bao gồm: mơ hình Markov ẩn, mơ hình Markov entropy cực đại và mơ hình trường điều kiện ngẫu nhiên CRFs. Nhĩm phát triển Mallet xây dựng nhiều phương pháp học máy như học bán giám sát và học cĩ giám sát. Trên cơ sở đĩ, tác giả đã phát triển thành cơng cụ gán nhãn cho tiếng Việt dựa trên phương pháp học bán giám sát CRFs theo tiêu chuẩn kỳ vọng tổng quát. Như phân tích ở 2.2, mơ hình học bán giám sát CRFs này sử dụng tiêu chuẩn kỳ vọng tổng quát, tác giả tiến hành xây dựng ràng buộc (Constraint) thể hiện mối quan hệ giữa từ và nhãn. Định dạng tổng quát của tập ràng buộc Constraint được xác định như sau: Feature_name label_name = probability label_name = probability … - 35 - 35 Số xác suất (probability) phải bằng với số nhãn. Các đặc trưng và tên nhãn phải khớp chính xác với các đặc trưng và tên nhãn trong dữ liệu và bảng mẫu tự đích (target alphabets). Do đĩ để xây dựng tập Constraint, cĩ thể làm theo hai cách: Cách 1: xây dựng thủ cơng, lựa chọn những đặc trưng và xác định xác suất cĩ thể cho mỗi đặc trưng theo từng nhãn. Việc ước lượng những xác suất này dựa trên kinh nghiệm chủ quan của người thực hiện. Cách 2: xây dựng tập Constraint dựa theo phương pháp LDA (Latent Dirichlet allocation). LDA [BNJ03] là mơ hình xác suất sinh cho những tập dữ liệu rời rạc, cho phép xác định tập dữ liệu quan sát dựa trên tập dữ liệu khơng quan sát dựa trên tính tương đồng. Từ đĩ, cho phép xác định xác suất một từ, một đặc trưng cĩ mặt trong các chủ đề là các nhĩm thực thể cho trước. Trong khuơn khổ luận văn, tác giả tiến hành xây dựng tập ràng buộc Constraint theo cả 2 phương pháp. Tiến hành xây dựng một tập các đặc trưng là các từ thường xuất hiện trong các tài liệu điều tra chia theo các nhĩm thực thể. Sử dụng phương pháp LDA để xác định ràng buộc về xác suất thuộc về các nhĩm thực thể khác nhau. Sau đĩ tác giả tiến hành kiểm tra, chỉnh sửa các ràng buộc một cách thủ cơng nhằm xây dựng được một tập ràng buộc Constraint tốt nhất. Do thời gian và kinh nghiệm cĩ hạn, nên tập ràng buộc được xây dựng theo chủ quan và kiến thức nghiên cứu được của tác giả cĩ thể chưa hồn thiện và sẽ ảnh hưởng phần nào đến kết quả mơ hình. Hình 5. Tập các ràng buộc (Constraint file) - 36 - 36 3.2.3. Lựa chọn thuộc tính Các thuộc tính được chọn theo mẫu ngữ cảnh từ vựng (kích thước cửa sổ trượt bằng 5): Mẫu ngữ cảnh Ý nghĩa S-2 Âm tiết quan sát tại vị trí -2 so với vị trí hiện tại S-1 Âm tiết quan sát tại vị trí liền trước so với vị trí hiện tại S1 Âm tiết quan sát tại vị trí liền sau so với vị trí hiện tại S2 Âm tiết quan sát tại vị trí +2 so với vị trị hiện tại S0S1 Âm tiết quan sát tại vị trí hiện tại và vị trí liền sau S-1S0 Âm tiết quan sát tại vị trí liền trước và vị trí hiện tại S-2S-1 Âm tiết quan sát tại vị trí -2 và vị trí liền trước S1S2 Âm tiết quan sát tại vị trí 2 và vị trí liền sau S-1S0S1 Âm tiết quan sát tại vị trí liền trước, hiện tại và liền sau S-2S-1S0 Âm tiết quan sát tại vị trí -2, vị trí liền trước và hiện tại S0S1S2 Âm tiết quan sát tại vị trí 2, vị trí liền sau và hiện tại Bảng 1. Mẫu ngữ cảnh từ vựng Các tên thực thể thường được viết hoa ký tự đầu tiên, vì thế ta cĩ thể thêm thuộc tính viết hoa vào mơ hình. Nếu tất cả các ký tự đều viết hoa thì khả năng đĩ là tên viết tắt của tổ chức. Đơi khi tên thực thể cĩ thể đi cùng với các ký tự số. Việc lựa chọn thuộc tính cịn được dựa trên ngữ cảnh phát hiện tên thực thể: Mẫu ngữ cảnh Ý nghĩa InitialCap Viết hoa chữ cái đầu AllCaps Viết hoa tất cả các chữ cái CapsMix Chữ cái thường và hoa lẫn lộn SingleDigit Số 1 chữ số HasDigit Cĩ chứa số DoubleDigits Số 2 chữ số Bảng 2. Mẫu ngữ cảnh phát hiện tên thực thể 3.2.4. Cách đánh giá Cĩ nhiều cách đánh giá độ chính xác của mơ hình, nhưng cách phổ biến nhất hiện nay là sử dụng các độ đo như độ chính xác (precision), độ hồi tưởng (recall) và độ đo F1. Độ đo F1 là một chỉ số cân bằng giữa độ chính xác và độ - 37 - 37 hồi tưởng. Nếu độ chính xác và độ hồi tưởng cao và cân bằng thì độ đo F1 lớn, cịn độ chính xác và hồi tưởng nhỏ và khơng cân bằng thì độ đo F1 nhỏ. Mục tiêu của ta là xây dựng mơ hình phân đoạn từ cĩ chỉ số F1 cao. Độ đo dựa theo từ được tính theo các cơng thức sau: (3.1) (3.2) (3.3) Trong đĩ: a là số thực thể gán đúng b là số thực thể mơ hình gán c là số thực thể do người gán 3.3. Kết luận chương 3 Chương 3 tập trung phân tích bài tốn trích chọn thơng tin trên tập văn bản pháp luật trên cơ sở phân tích các đặc trưng miền dữ liệu. Từ đĩ đề xuất mơ hình giải quyết bài tốn bao gồm 2 giai đoạn: Giai đoạn 1 là tiền xử lý dữ liệu và Giai đoạn 2 là đưa tập dữ liệu và các ràng buộc tự thiết lập vào huấn luyện mơ hình theo tiêu chuẩn kỳ vọng tổng quát. b aecision Pr c acall Re callecision callecisionmeasureF Re(Pr Re*Pr*2   - 38 - 38 CHƯƠNG 4 THỰC NGHIỆM VÀ ĐÁNH GIÁ 4.1. Mơ hình thực nghiệm 4.1.1. Dữ liệu thực nghiệm Do yêu cầu bảo vệ tài liệu hồ sơ vụ án, nên dữ liệu thực nghiệm được thu thập từ trang web Trang web này chứa nhiều thơng tin pháp luật về những vụ án, những tình tiết sự việc vi phạm pháp luật được cơng khai, khá gần với tài liệu hồ sơ vụ án cần khai thác. Tiến hành thu thập hơn 400 bài viết điều tra, ghi chép các vụ án về an ninh trật tự, an ninh kinh tế… Sau khi tiến hành bước tiền xử lý thu được tập dữ liệu huấn luyện training với hơn 50.000 dịng và tập dữ liệu kiểm tra testing với hơn 30000 dịng. Tác giả đã xây dựng một tập constraint với hơn 800 ràng buộc về xác suất cĩ thể cĩ của 4.1.2. Bộ cơng cụ Mallet Tác giả sử dụng bộ cơng cụ Mallet 2.0.6 phiên bản mới nhất. Dữ liệu đầu vào cho cơng cụ bao gồm: - File huấn luyện (training). - File constraint - File kiểm tra (testing) 4.2. Thực nghiệm và đánh giá 4.2.1. Mơi trường thực nghiệm Phần cứng: Máy tính IBM T61, Core 2 Duo, 4.00 GHz, RAM 2GB Phần mềm: Sử dụng tool Mallet được viết bởi Andrew McCallum và đồng nghiệp. Ngồi ra cịn sử dụng các cơng cụ JvnSegmenter để tách từ; vnTagger để gán nhãn POS cho từ. 4.2.2. Mơ tả quy trình thực nghiệm Tác giả tiến hành 4 thực nghiệm. Để đánh giá mức độ ảnh hưởng của tập dữ liệu huấn luyện đến kết quả gán nhãn, tác giả tiến hành chia tập dữ liệu huấn luyện lớn (hơn 50.000 dịng) thành các tập huấn luyện như sau: - Tập dữ liệu huấn luyện 10%: Lấy 10% dữ liệu của tập dữ liệu huấn luyện gốc. - Tập dữ liệu huấn luyện 20%: Lấy 20% dữ liệu của tập dữ liệu huấn luyện gốc. - 39 - 39 - Tập dữ liệu huấn luyện 40%: Lấy 40% dữ liệu của tập dữ liệu huấn luyện gốc. - Tập dữ liệu huấn luyện 80%: Lấy 80% dữ liệu của tập dữ liệu huấn luyện gốc. - Tập dữ liệu huấn luyện 100%: Lấy tồn bộ tập dữ liệu huấn luyện gốc. Như vậy, tác giả sẽ tiến hành 5 nhĩm thực nghiệm, mỗi nhĩm thực nghiệm sử dụng một tập dữ liệu huấn luyện phân chia như trên và tiến hành gán nhãn dữ liệu theo 3 mơ hình: Mơ hình CRFs đơn thuần; Mơ hình bán giám sát CRFs sử dụng Entropy Regularization và Mơ hình học bán giám sát CRFs theo phương pháp tiêu chuẩn kỳ vọng tổng quát trên cùng tập dữ liệu huấn luyện và tập dữ liệu kiểm tra. 4.2.3. Kết quả thực nghiệm Nhĩm thực nghiệm 1: Tiến hành gán nhãn theo 3 mơ hình trên sử dụng tập dữ liệu huấn luyện 10% và tập dữ liệu kiểm tra. Bảng 3. Kết quả nhĩm thực nghiệm 1 CRF CRF.ER CRF.GE Precision Recall F-measure Precision Recall F- measure Precision Recall F- measure ORG 0.9883 0.9989 0.9936 0.9442 0.8089 0.8714 0.9330 0.9876 0.9596 PER 0.9205 0.9697 0.9444 0.9180 0.9247 0.9213 0.9116 0.9652 0.9376 LOC 0.9458 0.9751 0.9602 0.9447 0.9161 0.9302 0.9267 0.9789 0.9521 MISC 0.1408 1.0000 0.2469 0.0000 NaN 0.0000 0.0000 NaN 0.0000 OVERALL 0.7489 0.9859 0.7863 0.9290 0.8825 0.9051 0.9044 0.9756 0.9386 - 40 - 40 Hình 6. Kết quả nhĩm thực nghiệm 1 Nhĩm thực nghiệm 2: Tiến hành gán nhãn theo 3 mơ hình trên sử dụng tập dữ liệu huấn luyện 20% và tập dữ liệu kiểm tra. CRFs CRFs.ER CRFs.GE Precision Recall F-measure Precision Recall F- measure Precision Recall F- measure ORG 0.9894 0.9852 0.9873 0.8931 0.9045 0.8987 0.97024 0.94027 0.95502 PER 0.9225 0.9875 0.9539 0.9199 0.9313 0.9255 0.91570 0.96532 0.93985 LOC 0.9742 0.9840 0.9791 0.9824 0.9986 0.9905 0.99917 0.99091 0.99502 MISC 0.5070 0.9000 0.6486 1.0000 0.7460 0.1389 0.05634 1.00000 0.10667 OVERALL 0.8483 0.9642 0.8922 0.9354 0.9245 0.9299 0.9403 0.9672 0.9536 Bảng 4. Kết quả nhĩm thực nghiệm 2 Hình 7. Kết quả nhĩm thực nghiệm 2 Nhĩm thực nghiệm 3: Tiến hành gán nhãn theo 3 mơ hình trên sử dụng tập dữ liệu huấn luyện 40% và tập dữ liệu kiểm tra. Trong nhĩm thực nghiệm này, tác giả mới chỉ đưa ra được kết quả của việc gán nhãn theo mơ hình CRFs đơn thuần và mơ hình bán giám sát CRFs sử dụng Entropy Regularization. Việc gán nhãn theo mơ hình học bán giám sát CRFs theo - 41 - 41 phương pháp tiêu chuẩn kỳ vọng tổng quát tác giả chưa thực hiện được do việc sử dụng mơ hình này cần bộ nhớ rất lớn, vượt quá khả năng đáp ứng của máy tính 32bit của tác giả. Nên trong nhĩm thực nghiệm này và 2 nhĩm thực nghiệm sau tác giả chỉ báo cáo kết quả của 2 mơ hình CRFs đơn thuần và CRFs sử dụng Entropy Regularization. CRF CRF.ER Precision Recall F-measure Precision Recall F-measure ORG 0.9989 0.9947 0.9968 0.9800 0.9363 0.9577 PER 0.9232 0.9912 0.9560 0.9232 0.9313 0.9272 LOC 0.9867 0.9867 0.9867 0.9918 1.0000 0.9959 MISC 0.8310 0.9833 0.9008 0.9815 0.7910 0.8760 OVERALL 0.9350 0.9890 0.9601 0.9518 0.9483 0.9500 Bảng 5. Kết quả nhĩm thực nghiệm 3 Hình 8. Kết quả nhĩm thực nghiệm 3 Nhĩm thực nghiệm 4: Tiến hành gán nhãn theo 3 mơ hình trên sử dụng tập dữ liệu huấn luyện 80% và tập dữ liệu kiểm tra. CRF CRF.ER Precision Recall F-measure Precision Recall F-measure ORG 0.9989 0.9958 0.9973 0.9873 0.9873 0.9873 PER 0.9232 0.9453 0.9341 0.9912 0.9912 0.9912 LOC 0.9867 0.9850 0.9858 0.9986 1.0000 0.9993 MISC 0.8310 0.9833 0.9008 0.9828 0.8507 0.9120 OVERALL 0.9350 0.9773 0.9545 0.9927 0.9895 0.9911 - 42 - 42 Bảng 6. Kết quả nhĩm thực nghiệm 4 Hình 9. Kết quả nhĩm thực nghiệm 4 Nhĩm thực nghiệm 5: Tiến hành gán nhãn theo 3 mơ hình trên sử dụng tập dữ liệu huấn luyện 100% và tập dữ liệu kiểm tra. CRF CRF.ER Precision Recall F-measure Precision Recall F-measure ORG 0.9989 1.0000 0.9995 0.9777 0.9777 0.9777 PER 0.9931 0.9993 0.9962 0.9956 0.9927 0.9941 LOC 1.0000 1.0000 1.0000 0.9973 1.0000 0.9986 MISC 0.9155 0.9559 0.9353 1.0000 0.9254 0.9612 OVERALL 0.9769 0.9888 0.9827 0.9939 0.9911 0.9925 Bảng 7. Kết quả nhĩm thực nghiệm 5 - 43 - 43 Hình 10. Kết quả nhĩm thực nghiệm 5 4.2.4. Đánh giá Qua 5 nhĩm thực nghiệm trên ta thấy cĩ một số nhận xét như sau: - Đối với mơ hình CRFs đơn thuần, khi càng tăng kích thước tập dữ liệu huấn luyện thì độ chính xác càng cao hay hàm F-measure càng cao. Điều này phù hợp với mơ hình học máy cĩ giám sát. Thậm chí ở nhĩm thực nghiệm thứ 3 kết quả của mơ hình CRFs đơn thuần cịn nhỉnh hơn so với kết quả của mơ hình CRFs sử dụng Entropy Regularization. - Kết quả của 2 mơ hình học máy bán giám sát (Mơ hình CRFs sử dụng Entropy Regularization và Mơ hình CRFs theo phương pháp tiêu chuẩn kỳ vọng tổng quát) tốt hơn so với kết quả của mơ hình học máy cĩ giám sát (Mơ hình CRFs đơn thuần), đặc biệt là với tập dữ liệu huẫn luyện nhỏ. - Mặc dù Mơ hình học máy bán giám sát CRFs theo phương pháp tiêu chuẩn kỳ vọng tổng quát mới chỉ thực hiện được ở 2 tập dữ liệu huấn luyện nhỏ (tập dữ liệu huấn luyện 10% và 20%), nhưng cũng cho thấy mơ hình này cho kết quả tốt hơn mơ hình học máy bán giám sát CRFs sử dụng Entropy Regularization. Các kết quả thực nghiệm trên cĩ thể chưa hồn thiện, kết quả cĩ thể bị ảnh hưởng bởi bản thân dữ liệu thu thập và một số trường hợp nhập nhằng trong tiếng Việt, nhưng nĩ cũng gĩp phần phản ánh ưu điểm của phương pháp học máy bán giám sát so với phương pháp học máy cĩ giám sát nĩi chung, đồng thời cũng cho thấy hiệu quả của mơ hình học máy bán giám sát theo tiêu chuẩn kỳ vọng tổng quát. 4.3. Kết luận chương 4 Tiến hành các thực nghiệm để phân tích đánh giá kết quả đạt được. Ở đây, tác giả tiến hành năm nhĩm thực nghiệm, mỗi nhĩm thực nghiệm sử dụng một tập dữ - 44 - 44 liệu huấn luyện được phân chia khác nhau và tiến hành gán nhãn dữ liệu theo 3 mơ hình: Mơ hình CRFs đơn thuần; Mơ hình bán giám sát CRFs sử dụng Entropy Regularization và Mơ hình học bán giám sát CRFs theo phương pháp tiêu chuẩn kỳ vọng tổng quát trên cùng tập dữ liệu huấn luyện và tập dữ liệu kiểm tra. Qua đĩ đánh giá hiệu quả của các mơ hình nĩi riêng và hiệu quả của các phương pháp học máy cĩ giám sát và bán giám sát nĩi chung. - 45 - 45 KẾT LUẬN Sau một thời gian tìm hiểu và nghiên cứu về bài tốn trích lọc thơng tin và phương pháp 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, luận văn đã đạt được một số kết quả sau. - Giới thiệu về mơ hình trường điều kiện ngẫu nhiên CRFs và phương pháp học máy bán giám sát. CRFs 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. CRFs cĩ nhiều ưu điểm của các mơ hình xác suất khác đồng thời khắc phục được nhược điểm mà các mơ hình xác suất khác gặp phải tiêu biểu là vấn đề “label bias”. Phương pháp học máy bán giám sát là sự kết hợp của 2 phương pháp truyền thống – học máy cĩ giám sát và học máy khơng cĩ giám sát, là cách học sử dụng thơng tin chứa trong cả dữ liệu chưa gán nhãn và tập dữ liệ gán nhãn nhằm mở rộng tập các dữ liệu gán nhãn ban đầu. Trong quá trình học như thế phương pháp sẽ tận dụng được những thơng tin phong phú của dữ liệu chưa gán nhãn, mà chỉ yêu cầu một số lượng rất nhỏ các dữ liệu đã gán nhãn. - Giới thiệu về tiêu chuẩn kỳ vọng tổng quát và áp dụng vào mơ hình CRFs. Tiêu chuẩn kỳ vọng tổng quát là những điều kiện trong hàm mục tiêu huấn luyện cho phép gán giá trị cho kỳ vọng mơ hình. Luận văn cùng đề cập đến cách xây dựng cơng thức, cách cách phân chia tiêu chuẩn kỳ vọng tổng quát, từ đĩ áp dụng vào mơ hình CRFs thiết lập các thơng số cho mơ hình theo tiêu chuẩn kỳ vọng tổng quát. - Đề xuất một mơ hình cho bài tốn trích chọn thơng tin thực thể trên tập văn bản pháp luật dựa trên phương pháp 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. Đồng thời sử dụng bộ cơng cụ Mallet được viết bởi Andrew McCallum và đồng nghiệp cho tập dữ liệu tiếng Việt theo mơ hình đề xuất ở trên trích lọc ra 4 loại thực thể: LOC, PER, ORG VÀ MISC. Tuy nhiên, để cĩ được một tập huấn luyện tốt địi hỏi nhiều thời gian và cơng sức. Trong thời gian cĩ hạn, tác giả mới chỉ xây dựng được tập dữ liệu huấn luyện và tập ràng buộc dữ liệu vừa phải. Với tập dữ liệu này, khi đưa vào tập dữ liệu kiểm tra bất kỳ kết quả thu được cịn hạn chế. Mặc dù, mơ hình này thu được kết quả khả quan ở tập ngơn ngữ tiếng Anh, nhưng đây là lần đầu tiên mơ hình này được áp dụng cho ngơn ngữ tiếng Việt và do - 46 - 46 những đặc điểm riêng biệt của tiếng Việt nên luận văn khơng thể tránh khỏi những thiếu sĩt và hạn chế nhất định. Tơi rất mong nhận được những ý kiến và nhận xét gĩp ý để luận văn được hồn thiện hơn. Xử lý ngơn ngữ tự nhiên là một vấn đề phức tạp. Hiện này đã cĩ nhiều cơng cụ xử lý ngơn ngữ tự nhiên, tuy nhiên hầu hết chúng được áp dụng cho tiếng Anh và tiếng Pháp. Các đặc thù của các ngơn ngữ là khác nhau nên việc chuyển đổi giữa các ngơn ngữ cũng gặp rất nhiều khĩ khăn đặc biệt là đối với một ngơn ngữ phong phú và đa dạng như tiếng Việt. Trong thời gian tới, tác giả sẽ tập trung xây dựng và hồn thiện bộ dữ liệu huấn luyện và tập các ràng buộc đặc trưng của dữ liệu nhằm cải thiện độ chính xác của mơ hình. - 47 - 47 TÀI LIỆU THAM KHẢO [AG05] M. R. Amini and P. Gallinari. Semi-supervised learning with an imperfect supervisor. Knowledge and Information Systems, 8(4):385–413, 2005. [BC01] A. Blum and S. Chawla. Learning from labeled and unlabeled data using graph mincuts. In Proceedings of the 18th International Conference on Machine Learning, pages 19–26, Williamston, MA, 2001. [BC09] Kedar Bellare, Andrew McCallum (2009). Generalized Expectation Criteria for Bootstrapping Extractors using Record-Text Alignment, The 2009 Conference on Empirical Methods in Natural Language Processing: 131– 140, 2009. [BLR04] A. Blum, J. Lafferty, M. Rwebangira, and R. Reddy. Semi-supervised learning using ran-domized mincuts. In Proceedings of the 21st International Conference on Machine Learning, pages 13–20, Ban, Canada, 2004. [BM98] A. Blum and T. Mitchell. Combining labeled and unlabeled data with co- training. In Proceedings of the 11th Annual Conference on Computational Learning Theory, pages 92–100, Madison, WI, 1998. [BN04] M. Belkin and P. Niyogi. Semi-supervised learning on Riemannian manifolds. Machine Learning, 56(1-3):209–239, 2004. [BNJ03] David M. Blei, Andrew Y.Ng và Michael I.Jordan. Latent Dirichlet Allocation. University of California, Berkeley, Berkeley, CA 94720. 2003 [BNS05] M. Belkin, P. Niyogi, and V. Sindhwani. On manifold regularization. In Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics, pages 17–24, Savannah, Barbados, 2005. [BNS06] M. Belkin, P. Niyogi, and V. Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 7:2399–2434, 2006. [BS06] U. Brefeld and T. Scheffer. Semi-supervised learning for structured output variables. In Proceedings of the 23rd International Conference on Machine Learning, pages 145–152, Pittsburgh, PA, 2006. [Car10] Andrew Carlson (2010). Coupled Semi-Supervised Learning, PhD Thesis (CMU-ML-10-104), Carnegie Mellon University, 2010. - 48 - 48 [CMD07] Andrew McCallum, Gideon Mann, Gregory Druck (2007). Generalized Expectation Criteria, Technical Report UM-CS-2007-60, University of Massachusetts Amherst, August, 2007 [CZ05] O. Chapelle and A. Zien. Semi-supervised learning by low density separation. In proceedings of the 10th International Workshop on Artificial Intelligence and Statistics, pages 57–64. Savannah Hotel, Barbados, 2005. [DLR77] A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series B, 39(1):1–38, 1977. [DMC07] Gregory Druck, Gideon Mann, Andrew McCallum (2007). Leveraging Existing Resources using Generalized Expectation Criteria, NIPS WS, 2007. [DMC08] Gregory Druck, Gideon Mann and Andrew McCallum (2008). Learning from Labeled Features using Generalized Expectation Criteria, SIGIR 08, 2008. [DMC09] Gregory Druck, Gideon Mann, Andrew McCallum (2009). Semi-supervised Learning of Dependency Parsers using Generalized Expectation Criteria, The 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP: 360–368. [Erk10] Ayse Naz Erkan (2010). Semi-supervised Learning via Generalized Maximum Entropy, PhD Thesis, New York University, 2010. [FUS05] A. Fujino, N. Ueda, and K. Saito. A hybrid generative/discriminative approach to semi-supervised classifier design. In Proceedings of the 20th National Conference on Artificial Intelligence, pages 764–769, Pittsburgh, PA, 2005. [GB04] Y.Grandvaletand, Y.Bengio. Semi-supervised learning by entropy minimization. In Advances in Neural Information Processing Systems, 2004. [GY05] Y. Grandvalet and Y. Bengio. Semi-supervised learning by entropy minimization. In L. K. Saul, Y.Weiss, and L. Bottou, editors, Advances in Neural Information Processing Systems 17, pages 529–536. MIT Press, Cambridge, MA, 2005. [GZ00] S. Goldman and Y. Zhou. Enhancing supervised learning with unlabeled data. In Proceedings of the 17th International Conference on Machine Learning, pages 327–334, San Francisco, CA, 2000. [HC71] J.Hammersley and P. Clifford (1971). Markov fields on finite graphs and lattices. Unpublished manuscript. [HM07] M. Hein and M. Maier. Manifold denoising. In B. Sch¨olkopf, J. C. Platt, and T. Homan, editors, Advances in Neural Information Processing Systems 19, pages 561–568. MIT Press, Cambridge, MA, 2007. - 49 - 49 [Joa99] T. Joachims. Transductive inference for text classification using support vector machines. In Proceedings of the 16th International Conference on Machine Learning, pages 200–209, Bled, Slovenia, 1999 [JWL06] Feng Jiao, Shaojun Wang, Chi-Hoon Lee, Russell Greiner, Dale Schuurmans (2006). Semi-supervised conditional random fields for improved sequence segmentation and labeling, The 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics: 209-216, 2006. [KL51] S. Kullback and R. A. Leibler. On Information and Sufficiency. Annuals of Mathematical Statistics 22 (1): pages 79–86, 1951. [KQ10] Pavel P. Kuksa, Yanjun Qi (2010). Semi-Supervised Bio-Named Entity Recognition with Word-Codebook Learning, SDM 2010: 25-36, 2010. [Kul59] S. Kullback. Information theory and statistics. John Wiley and Sons, NY, 1959. [LCP01] John Laferty, Andrew McCallum, Fernando Pereira. Conditional Random Fields: Probabilistic Models for segmenting and labeling Sequence Data. In Proc. of the Eighteenth International Conference on Machine Learning (ICML-2001), 2001. [LJ05] N. D. Lawrence and M. I. Jordan. Semi-supervised learning via Gaussian processes. In L. K. Saul, Y. Weiss, and L. Bottou, editors, Advances in Neural Information Processing Systems 17, pages 753–760. MIT Press, Cambridge, MA, 2005. [Mal02] Robert Malouf. “A comparison of algorithms for maximum entropy parameter estimation.” In Proceedings of the Sixth Conference on Natural Language Learning (CoNLL-2002). Pages 49–55. [MC08] Gideon S. Mann, Andrew McCallum (2008). Generalized Expectation Criteria for Semi-Supervised Learning of Conditional Random Fields, ACL- 08 (HLT): 870–878, 2008. [MC10] Gideon S. Mann, Andrew McCallum (2010). Generalized Expectation Criteria for Semi-Supervised Learning with Weakly Labeled Data, Journal of Machine Learning Research, 11 (2010): 955-984 [MGZ04] Scott Miller, Jethran Guinness, Alex Zamanian (2004). Name Tagging with Word Clusters and Discriminative Training, ACL 04, 2004. [MMI02] Masaki Murata, Qing Ma, Hitoshi Isahara. Comparison of Three Machine- Learning Methods for Thai Part-of-Speech Tagging. In Proc. ACM Transactions on Asian Language Information Processing, Vol. 1, No. 2, June 2002, Pages 145-158. [MU97] D. J. Miller and H. S. Uyar. A mixture of experts classifier with learning based on both labelled and unlabelled data. In M. Mozer, M. I. Jordan, and - 50 - 50 T. Petsche, editors, Advances in Neural Information Processing Systems 9, pages 571–577. MIT Press, Cambridge, MA, 1997. [NCT00] K.Nigam, A. K. McCallum, S. Thrun, and T. Mitchell. Text classification from labeled and unlabeled documents using EM. Machine Learning, 39(2- 3):103–134, 2000. [NG00] K. Nigam and R. Ghani. Analyzing the effectiveness and applicability of co- training. In Proceedings of the 9th ACM International Conference on Information and Knowledge Management, pages 86–93, Washington, DC, 2000. [QKC09] Yanjun Qi, Pavel Kuksa, Ronan Collobert, Kunihiko Sadamasa, Koray Kavukcuoglu, and Jason Weston (2009). Semi-Supervised Sequence Labeling with Self-Learned Features, The 2009 Ninth IEEE International Conference on Data Mining: 428-437, 2009. [SL94] B. Shahshahani and D. Landgrebe. The effect of unlabeled samples in reducing the small sample size problem and mitigating the hughes phenomenon. IEEE Transactions on Geo-science and Remote Sensing, 32(5):1087–1095, 1994. [Spr07] Richard Sproat. Introduction to Speech Technology (Language Models, HMMs, Forward Algorithm, Viterbi Algorithm…) Slide. Department of Electrical and Computer Engineering, University of Illinois at Urbana- Champaign. ECE 398RS Courses, Fall 2007. [Wal02] Hanna M. Wallach. Efficient Training of Conditional Random Fields. Technical Report, University of Edinburgh, 2002 [Wal04] Hanna M.Wallach. Conditional Random Fields: An introduction. Technical Report MS-CIS-04-21, Department of Computer and Information Science, University of Pennsylvania. February 24, 2004. [WHW09] Yang Wang, Gholamreza Haffari, Shaojun Wang, Greg Mori (2009). A Rate Distortion Approach for Semi-Supervised Conditional Random Fields, NIPS2009, 2009. [ZBL04] D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Sch¨olkopf. Learning with local and global consistency. In S. Thrun, L. Saul, and B. Sch¨olkopf, - 51 - 51 editors, Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2004. [ZC06] Z.-H. Zhou, K.-J. Chen, and H.-B. Dai. Enhancing relevance feedback in image retrieval using unlabeled data. ACM Transactions on Information Systems, 24(2):219–244, 2006. [ZGL03] X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. In Proceedings of the 20th International Conference on Machine Learning, pages 912–919, Washington, DC, 2003. [Zho08] Z. H. Zhou. Semi-supervised learning by disagreement. In Proceedings of the 4th IEEE International Conference on Granular Computing, Hangzhou, China, 2008. [ZL05] Z. H. Zhou and M. Li. Tri-training: Exploiting unlabeled data using three classifiers. IEEE Transactions on Knowledge and Data Engineering, 17(11):1529–1541, 2005. [ZL07] Z. H. Zhou and M. Li. Semi-supervised regression with co-training style algorithms. IEEE Transactions on Knowledge and Data Engineering, 19(11):1479–1493, 2007. [ZL07b] X. Zhang and W. S. Lee. Hyperparameter learning for graph based semi- supervised learning algorithms. In B. Sch¨olkopf, J. Platt, and T. Hofmann, editors, Advances in Neural Information Processing Systems 19, pages 1585–1592. MIT Press, Cambridge, MA, 2007. [ZL10] Zhi-Hua Zhou and Ming Li. Semi-supervised Learning by Disagreement. National Key Laboratory for Novel Software Technology Nanjing University, Nanjing 210093, China. 2010. [ZZY07] Z.-H. Zhou, D.-C. Zhan, and Q. Yang. Semi-supervised learning with very few labeled training examples. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence, pages 675–680, Vancouver, Canada, 2007.