LUẬN VĂN: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

Chia sẻ: Sunflower Sunflower_1 | Ngày: | Loại File: PDF | Số trang:51

Thêm vào BST

Báo xấu

99
lượt xem 31
download

LUẬN VĂN: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

Mô tả tài liệu

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bố cục của luận văn chia 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ủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: LUẬN VĂN: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- 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 1
-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 2
-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 3
-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 4
-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 5
-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 6
-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 7
-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 8
-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 9
- 10 - luận văn và hướng nghiên cứ u trong tương lai. 10
- 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ữ 11
- 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]: P(Yv | X ,Y ,   v)  P(Yv | X , Y ,  N(v)) (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: Yn-1 Y Y Y Y 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]): P (y | x )    A ( A | x ) (1.2) AC 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. 12
- 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ũ.  A  A | x  exp   k f k  A | x (1.3) k Ở đâ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: 1   exp k tk (y i 1 , y i , x)   k sk (y i , x)  (1.4) P(y | x)  Z (x)  i k  i k Ở đâ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. 1 nếu xi=Bill và yi= B_PER si = 0 nếu ngược lại 1 nếu xi-1= “Bill”, xi=”Clinton” và yi-1=B_PER,yi=I_PER ti = 0 nếu ngược lại = Thừa số chuẩn hóa Z(x) được tính như sau:   Z (x)   exp   k t k (y i 1 , y i , x)     k sk (y i , x)  (1.5) i k  y i k Đặt  (1 , 2 ,..., 1,  2 ..) 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. 13
- 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: M i ( x)  M i ( y ' , y, x) (1.6)   M i ( y ' , y , x)  exp   k t k ( y ' , y, x)    k s k ( y, x)  (1.7) k  k Ở đâ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  i ( y ) 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ả  i ( y k ) với mọ i yk thuộc tập trạng thái S của mô hình, cần xác định  i 1 ( y j ) . Từ hình 2, ta suy ra công thức truy hồi  i 1 ( y j )  max  i 1 ( y k ) * M i ( y k , y j , x) y k  S (1.9)  i 1 ( y j ) Pr  i ( y1 ) ?  i ( y2 ) Pr  i ( y N ) Hình 2. Một bước trong thuật toán Viterbi cải tiến Đặt Pr ei ( y )  arg max  i 1 ( y ' ) * M i ( y ' , y, x)  . 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 y * ( n)  arg max n ( y )  o in 14
- 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 tham số cho một mô hình CRFs chính là bài toán tìm cực đại của hàm log-likelihood. Có nhiều phương pháp tìm cực đại của hàm log-likelihood như các phương pháp lặp (IIS, GIS), các phương pháp 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 hoá tính toán toá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ề 15
- 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 toá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ự đoá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 16
- 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 toán được một phép ánh xạ thông qua thực thi dự đoá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 toá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 toá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ẻ, toàn bộ một từ viết tay, hay toà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 toá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 17
- 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ự đoá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. Hoà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 toán 18
- 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 toá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 toá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 toá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 toán cực đại hóa kỳ vọng EM [DLR77] để tính toán ước lượng cực 19
- 20 - đại likelihood của tham số mô hình. Những thuật toá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 Naï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 toá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 toán điể n hình của phương pháp này được Xiaojin Zhu đề cập trong [Zhu08] như: Thuật toán học bán giám sát cực đại kỳ vọng EM địa phương, Thuật toá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 toá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 20