Tài liệu 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

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM THỊ NGÂ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 LUẬN VĂN THẠC SĨ Hà Nội - 2011 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM THỊ NGÂ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 Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 604805 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: TIẾN SĨ NGUYỄN LÊ MINH Hà Nội, 2011 -1MỤC LỤC LỜI CAM ĐOAN................................................ Error! Bookmark not defined. MỤC LỤC ............................................................................................................. 1 DANH MỤC HÌNH VẼ ........................................................................................ 3 DANH MỤC BẢNG BIỂU .................................................................................. 4 KÝ TỰ VIẾT TẮT ................................................................................................ 5 LỜI CẢM ƠN ....................................................................................................... 6 LỜI MỞ ĐẦU ....................................................................................................... 7 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 ....................................................................................... 8 1.1.Phƣơng pháp học máy Trƣờng ngẫu nhiên có điều kiện ................................ 8 1.1.1. Khái niệm trƣờng ngẫu nhiên có điều kiện ............................................. 8 1.1.2. Học máy CRFs ...................................................................................... 10 1.1.2.1. Hàm tiềm năng của các mô hình CRFs...................................... 10 1.1.2.2. Thuâ ̣t toán gán nhañ cho dƣ̃ liê ̣u da ̣ng chuỗi. ............................ 11 1.1.2.3. Ƣớc lƣợng tham số cho các mô hình CRFs ............................... 12 1.2.Học máy bán giám sát CRFs ......................................................................... 12 1.2.1. Học máy bán giám sát ........................................................................... 12 1.2.1.1. Học không có giám sát và Học có giám sát .............................. 13 1.2.1.2. Học máy bán giám sát ................................................................ 15 1.2.1.3. Một số thuật toán học máy bán giám sát ................................... 16 1.2.2. Sơ bộ về mô hình học máy bán giám sát CRFs .................................... 18 1.3.Kết luận chƣơng 1 ......................................................................................... 19 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 ......................................................................................... 20 2.1.Tiêu chuẩn kỳ vọng tổng quát ....................................................................... 20 2.1.1. Giới thiệu sơ bộ ..................................................................................... 20 2.1.2. Tiêu chuẩn kỳ vọng tổng quát ............................................................... 21 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 ... 23 2.3.Kết luận chƣơng 2 ......................................................................................... 25 -2- 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........................................... 26 3.1. Trích chọn thông tin từ văn bản pháp luật tiếng Việt .................................. 26 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 ........... 26 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 .................. 28 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 .......................................................................................................... 28 3.2.1. Một số phân tích .................................................................................... 28 3.2.2. Mô hình đề nghị .................................................................................... 29 3.2.3. Lựa chọn thuộc tính .............................................................................. 33 3.2.4. Cách đánh giá ........................................................................................ 33 3.3.Kết luận chƣơng 3 ......................................................................................... 34 CHƢƠNG 4: THỰC NGHIỆM VÀ ĐÁNH GIÁ ............................................... 35 4.1. Mô hình thực nghiệm ................................................................................... 35 4.1.1. Dữ liệu thực nghiệm.............................................................................. 35 4.1.2. Bộ công cụ Mallet ................................................................................. 35 4.2. Thực nghiệm và đánh giá ............................................................................. 35 4.2.1. Môi trƣờng thực nghiệm ....................................................................... 35 4.2.2. Mô tả quy trình thực nghiệm................................................................. 35 4.2.3. Kết quả thực nghiệm ............................................................................. 36 4.2.4. Đánh giá ................................................................................................ 37 4.3. Kết luận chƣơng 4 ........................................................................................ 40 KẾT LUẬN ......................................................................................................... 42 TÀI LIỆU THAM KHẢO ................................................................................... 44 -3- DANH MỤC HÌNH VẼ Hình 1. Đồ thị vô hướng mô tả CRFs ........................................................... 9 Hình 2. Một bước trong thuật toán Viterbi cải tiế n.................................... 11 Hình 3/4. Mô hình đề xuất giải quyết bài toán ........................................... 30 Hình 5. Tập các ràng buộc (Constraint file)............................................... 32 Hình 6. Kết quả nhóm thực nghiệm 1 ......................................................... 36 Hình 7. Kết quả nhóm thực nghiệm 2 ......................................................... 37 Hình 8. Kết quả nhóm thực nghiệm 3 ......................................................... 38 Hình 9. Kết quả nhóm thực nghiệm 4 ......................................................... 39 Hình 10. Kết quả nhóm thực nghiệm 5 ....................................................... 40 -4- DANH MỤC BẢNG BIỂU Bảng 1. Mẫu ngữ cảnh từ vựng ........................................................................... 33 Bảng 2. Mẫu ngữ cảnh phát hiện tên thực thể .................................................... 33 Bảng 3. Kết quả nhóm thực nghiệm 1 ................................................................. 36 Bảng 4. Kết quả nhóm thực nghiệm 2 ................................................................. 37 Bảng 5. Kết quả nhóm thực nghiệm 3 ................................................................. 38 Bảng 6. Kết quả nhóm thực nghiệm 4 ................................................................. 38 Bảng 7. Kết quả nhóm thực nghiệm 5 ................................................................. 39 -5- KÝ TỰ VIẾT TẮT CRFs EM GE GEC GIS i.i.d IIS KL L-BFGS LOC MISC NER ORG PER Conditional Random Fields Entropy Maximum Generalized Expectation Generalized Expectation Criteria Generalized Iterative Scaling independently and identically Improved Iterative Scaling Kullback Leibler Limited memory Broyden–Fletcher–Goldfarb–Shanno LOCation MIScellaneous Named Entity Recognition ORGanization PERson -6- 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 -7- 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 luận văn và hƣớng nghiên cứu trong tƣơng lai. -8- 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 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 cu ̣c” của CRF s cho phép mô hiǹ h này khắ c phu ̣c đƣơ ̣c những nhƣơ ̣c điể m của các mô hiǹ h trƣ ớc đó trong việc gán nhãn và phân đoa ̣n các dƣ̃ liê ̣u da ̣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 tra ̣ng thái.  S: Tâ ̣p hƣ̃u ha ̣n các tra ̣ng thái của mô ̣t mô hiǹ h CRFs. 1.1. 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á tri ̣là chuỗi dƣ̃ liê ̣u cầ n phải gán nhañ 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 n hâ ̣n g iá trị trong tập hữu hạn các trạng thái S. Trong bài toán gán nhãn t ừ loại, X có thể nhận giá trị là các câu trong ngôn ngữ tƣ̣ nhiên (gồm các từ), Y là một chuỗi ngẫu nhiên các nhãn tƣơng ứng với các t ừ -9- 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 đồ thi ̣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ƣớn g nố i các đin̉ h đồ thi ̣ . 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 ta ̣i ánh xa ̣ mô ̣t - mô ̣t giƣ̃a mô ̣t đin̉ h 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 đồ thi 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 phu ̣ thuô ̣c toàn cu ̣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à da ̣ng chuỗi G = (V={1,2,…m}, E={(i,i+1)}). Kí hiệu X=(X1, X2,…, Xn), Y=(Y1,Y2,...,Yn). Mô hiǹ h đồ thị cho CRF s có dạng: X Y1 Y2 Y3 Yn-1 Yn 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 - đồ thi ̣biể u diễn cấ u trúc của mô ̣t CRFs. Áp du ̣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 nhañ 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) AC (1.2) Vì trong các bài toán xử lý dữ liệu dạng chuỗ i, đồ thi ̣biể u diễn cấ u trúc của mô ̣t CRF có da ̣ng đƣờng thẳ ng nhƣ trong hiǹ h 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 ca ̣nh của G. - 10 - 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 đa ̣i hóa Entropy . Cƣ̣c đa ̣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 du ̣ng nguyên lý cƣ̣c đa ̣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 đa ̣t thông tin của thuô ̣c tiń h 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: P ( y | x)  1   exp    k t k (y i 1 , y i , x)    k s k (y i , x)  Z ( x)  i k i k  (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 tiń h của tòan bô ̣ chuỗi quan sát và các tra ̣ng thái ta ̣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 ta ̣i ví trí i trong chuỗi tra ̣ng thái. 1 nế u xi=Bill và yi= B_PER si = 0 nế u ngƣơ ̣c la ̣i 1 nế u xi-1= “Bill”, xi=”Clinton” và yi-1=B_PER,yi=I_PER ti = = 0 nế u ngƣơ ̣c la ̣i Thƣ̀a số chuẩ n hóa Z(x) đƣơ ̣c tiń h nhƣ sau:   Z (x)   exp    k t k (y i 1 , y i , x)    k s k (y i , x)  y i k  i k  Đặt  (1 , 2 ,..., 1,  2 ..) là các vector các tham số của mô hình (1.5) ,  đƣơ ̣c ƣớc lƣơ ̣ng giá tri ̣nhờ các phƣơng pháp ƣớc lƣơ ̣ng tham số cho mô hiǹ h sẽ đƣơ ̣c đề câ ̣p trong phầ n sau. - 11 1.1.2.2. Thuâ ̣t toán gán nhãn cho dƣ̃ liêụ da ̣ng chuỗi. Tại mỗi vị trí i trong chuỗi dƣ̃ liê ̣u quan sát , ta đinh ̣ nghiã mô ̣t ma trâ ̣n chuyể n |S|×|S| nhƣ sau: (1.6) M i (x)  M i ( y' , y, x)   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 tra ̣ng thái y với chuỗi dƣ̃ liê ̣u quan sát là x. Chuỗi tra ̣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 đinh ̣ bằ ng thu ật toán Viterbi cải tiến [Spr07] nhƣ mô tả trong hình 2. Đinh ̣ nghiã  i ( y) là xác suất của “chuỗi trạng thái độ dài i kế t thúc bởi tra ̣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 mo ̣i yk thuô ̣c tâ ̣p tra ̣ng thái S của mô hình, cầ n xác định  i 1 ( y j ) . Tƣ̀ hin ̀ h 2, ta suy ra công thƣ́c truy hồi  i 1 ( y j )  max  i 1 ( yk ) * M i ( yk , y j , x)yk  S Pr  i ( y1 ) y 1 ob= y  i ( y2 ) Pr  i ( y N ) 2 (1.9)  i 1 ( y j ) ? y j y N ob= 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ƣ̉ du ̣ng ki ̃ thuâ ̣t backtracking để tim ̀ chuỗi tra ̣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 - 12 -  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ô hiǹ h CRF s nhƣ là mô ̣t máy tra ̣ng thái xác suấ t với các tro ̣ng số không chuẩ n hóa , mỗi tro ̣ng số gắ n liề n với mô ̣t bƣớc chuyể n tra ̣ng thái . Bản chất không chuẩn hóa của các tro ̣ng số cho phép các bƣớc chuyể n tra ̣ng thái có thể nhâ ̣n các giá tri ̣quan tro ̣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 tra ̣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 cu ̣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 CRF s là làm cƣ̣c đa ̣i hóa đô ̣ đo likelihood giƣ̃a phân phố i mô hiǹ h 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 ho ̣c , bài toán ƣớc lƣợng tham số cho một mô hình CRF s 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 đa ̣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ƣợn g tham số mô hiǹ h . Trong các phƣơng pháp tim ̀ cƣ̣c tri ̣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ề - 13 - 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 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. - 14 - 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 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. - 15 - 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 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. - 16 - - ... 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 đạ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... - 17 - - 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 đƣờ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ự đoán rời rạc ví dụ dự đoá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ự đoá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ự đoá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ự đoá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 - 18 - đƣợ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 toán học. Thuật toá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 toá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 toá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 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 toán tận dụng dữ liệu chƣa gán nhãn qua chuẩn hóa entropy (entropy regularization) – thuật toá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 toà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.