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

- 2 -

LỜI CAM ĐOAN

Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá nhân tôi, không sao chép lại của người khác. Trong toàn bộ nội dung của luận văn, những điều được trình bày hoặc là của cá nhân hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp pháp. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luận theo quy định cho lời cam đoan của mình.

Hà Nội, 05/2011

Phạm Thị Ngân

- 3 -

MỤC LỤC

LỜI CAM ĐOAN .............................................................................................. 1

MỤC LỤC ......................................................................................................... 3

DANH MỤC HÌNH VẼ ..................................................................................... 5

DANH MỤC BẢNG BIỂU ................................................................................ 6

KÝ TỰ VIẾT TẮT............................................................................................. 7

LỜI CẢM ƠN .................................................................................................... 8

LỜI MỞ ĐẦU.................................................................................................... 9

CHƯƠNG 1: HỌC BÁN GIÁM SÁT THEO MÔ HÌNH TRƯỜNG NGẪU NHIÊN CÓ ĐIỀU KIỆN .................................................................................. 11

1.1. Phương pháp học máy Trường ngẫu nhiên có điều kiện ............................. 11

1.1.1. Khái niệm trường ngẫu nhiên có điều kiện ......................................... 11

1.1.2. Học máy CRFs ................................................................................... 13

1.1.2.1. Hàm tiềm năng của các mô hình CRFs .................................... 13

1.1.2.2. Thuật toán gán nhãn cho dữ liệu dạng chuỗi. ........................... 14

1.1.2.3. Ước lượng tham số cho các mô hình CRFs .............................. 15

1.2. Học máy bán giám sát CRFs ...................................................................... 15

1.2.1. Học máy bán giám sát......................................................................... 15

1.2.1.1. Học không có giám sát và Học có giám sát ............................. 16

1.2.1.2. Học máy bán giám sát.............................................................. 18

1.2.1.3. Một số thuật toán học máy bán giám sát .................................. 19

1.2.2. Sơ bộ về mô hình học máy bán giám sát CRFs ................................... 21

1.3. Kết luận chương 1 ...................................................................................... 22

CHƯƠNG 2: HỌC MÁY BÁN GIÁM SÁT CRFs THEO TIÊU CHUẨN KỲ VỌNG TỔNG QUÁT ...................................................................................... 23

2.1. Tiêu chuẩn kỳ vọng tổng quát .................................................................... 23

2.1.1. Giới thiệu sơ bộ .................................................................................. 23

2.1.2. Tiêu chuẩn kỳ vọng tổng quát............................................................. 24

2.2. Mô hình học máy bán giám sát CRFs theo tiêu chuẩn kỳ vọng tống quát ... 26

- 4 -

2.3. Kết luận chương 2 ...................................................................................... 28

CHƯƠNG 3: MỘT MÔ HÌNH HỌC MÁY BÁN GIÁM SÁT CRFs TRÍCH CHỌN THÔNG TIN PHÁP LUẬT TIẾNG VIỆT ......................................... 29

3.1. Trích chọn thông tin từ văn bản pháp luật tiếng Việt ................................. 29

3.1.1. Một số đặc trưng về miền dữ liệu văn bản pháp luật tiếng Việt........... 29

3.1.2. Bài toán trích chọn thông tin văn bản pháp luật tiếng Việt.................. 31

3.2. Một mô hình học máy bán giám sát CRFs trích chọn thông tin pháp luật tiếng Việt ...................................................................................................... 31

3.2.1. Một số phân tích ................................................................................. 31

3.2.2. Mô hình đề nghị ................................................................................. 32

3.2.3. Lựa chọn thuộc tính ............................................................................ 36

3.2.4. Cách đánh giá ..................................................................................... 36

3.3. Kết luận chương 3 ...................................................................................... 37

CHƯƠNG 4: THỰC NGHIỆM VÀ ĐÁNH GIÁ ............................................. 38

4.1. Mô hình thực nghiệm ................................................................................ 38

4.1.1. Dữ liệu thực nghiệm ........................................................................... 38

4.1.2. Bộ công cụ Mallet .............................................................................. 38

4.2. Thực nghiệm và đánh giá .......................................................................... 38

4.2.1. Môi trường thực nghiệm ..................................................................... 38

4.2.2. Mô tả quy trình thực nghiệm............................................................... 38

4.2.3. Kết quả thực nghiệm........................................................................... 39

4.2.4. Đánh giá ............................................................................................. 40

4.3. Kết luận chương 4 ..................................................................................... 43

KẾT LUẬN...................................................................................................... 45

TÀI LIỆU THAM KHẢO ................................................................................ 47

- 5 -

DANH MỤC HÌNH VẼ

Hình 1. Đồ thị vô hướng mô tả CRFs ....................................................... 12

Hình 2. Một bước trong thuật toán Viterbi cải tiến................................... 14

Hình 3/4. Mô hình đề xuất giải quyết bài toán.......................................... 34

Hình 5. Tập các ràng buộc (Constraint file) ............................................. 35

Hình 6. Kết quả nhóm thực nghiệm 1 ....................................................... 40

Hình 7. Kết quả nhóm thực nghiệm 2 ....................................................... 40

Hình 8. Kết quả nhóm thực nghiệm 3 ....................................................... 41

Hình 9. Kết quả nhóm thực nghiệm 4 ....................................................... 42

Hình 10. Kết quả nhóm thực nghiệm 5 ..................................................... 43

- 6 -

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 -

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

- 8 -

LỜI CẢM ƠN

Để hoàn thành luận văn này tác giả đã nhận được sự giúp đỡ từ rất nhiều cơ

quan, đoàn thể và cá nhân.

Trước hết tôi xin chân thành cảm ơn các thầy giáo, cô giáo trong Khoa

Công nghệ Thông tin, trường Đại học Công nghệ, Đại học Quốc gia Hà Nội đã

tận tình giảng dạy, trang bị cho tôi những kiến thức quý báu trong suốt quá trình

học tập tại trường.

Tôi xin bày tỏ lòng biết ơn sâu sắc đến TS. Nguyễn Lê Minh - người thầy

đã trực tiếp hướng dẫn tôi trong suốt quá trình xây dựng và hoàn thành luận văn

này. Tôi xin bày tỏ lòng biết ơn chân thành đến thầy giáo PGS.TS. Hà Quang

Thụy và các bạn trong Phòng thí nghiệm công nghệ tri thức, Trường Đại học

Công nghệ đã giúp đỡ và đóng góp nhiều ý kiến quý báu cho tôi.

Cuối cùng, tôi xin bày tỏ lòng biết ơn sâu sắc tới gia đình, bạn bè, những

người luôn động viên, giúp đỡ tôi rất nhiệt tình để hoàn thành luận văn.

Hà Nội, tháng 05 năm 2011 Học viên Phạm Thị Ngân

- 9 -

LỜI MỞ ĐẦU

Trích chọn thông tin là một khâu cơ bản trong bài toán khai phá dữ liệu. Ngày nay, cùng với sự phát triển của công nghệ thông tin, Tin học đã dần được ứng dụng rộng rãi trong nhiều lĩnh vực như kinh tế, thương mại, y tế, ngân hàng và mang lại nhiều lợi ích to lớn. Bản thân tôi hiện đang công tác tại Học viện Cảnh sát nhân dân, tôi có những hiểu biết nhất định về công tác giữ gìn trật tự an toàn xã hội của lực lượng cảnh sát nhân dân. Tôi nhận thấy, các hoạt động của lực lượng cảnh sát có liên quan nhiều đến việc lưu trữ hồ sơ dữ liệu, tra cứu, phân tích tổng hợp dữ liệu... Tuy nhiên, công tác quản lý hồ sơ dữ liệu này vẫn còn kém hiệu quả do những hạn chế nhất định. Do đó tôi đã mạnh dạn chọn đề tài tập trung nghiên cứu vào việc trích lọc thông tin trên tập văn bản pháp luật này.

Trong nhiều thập kỷ qua, các nhà khoa học quan tâm đến lĩnh vực xử lý ngôn ngữ tự nhiên đã nghiên cứu và đề xuất được nhiều phương pháp, mô hình xử lý ngôn ngữ với hiệu quả cao. Nổi bật trong số đó là phương pháp học máy bán giám sát dựa trên mô hình trường ngẫu nhiên có điều kiện theo tiêu chuẩn kỳ vọng tổng quát, phương pháp này đạt được kết quả rất khả quan trên tập dữ liệu ngôn ngữ tiếng Anh và hiện chưa được áp dụng cho tiếng Việt. Được sự giúp đỡ và đồng ý của Thầy giáo hướng dẫn TS. Nguyễn Lê Minh, tác giả quyết định sử dụng mô hình này ứng dụng cho tập văn bản pháp luật. Bố cục của luận văn chia thành 4 chương như sau:  Chương 1: Trình bày những kiến thức cơ bản về mô hình trường ngẫu

nhiên có điều kiện và phương pháp học máy bán giám sát.

 Chương 2: Trình bày về tiêu chuẩn kỳ vọng tổng quát và áp dụng tiêu chuẩn kỳ vọng tổng quát vào mô hình trường ngẫu nhiên có điều kiện.  Chương 3: Trình bày về bài toán trích chọn thưc thể trên tập văn bản pháp luật và đề xuất mô hình giải quyết bài toán dựa trên mô hình CRFs theo tiêu chuẩn kỳ vọng tổng quát.

 Chương 4: Trình bày các thực nghiệm trên tập dữ liệu sử dụng một số mô hình học máy có giám sát CRFs, và mô hình học máy bán giám sát CRFs theo chuẩn hóa entropy và theo tiêu chuẩn kỳ vọng tổng quát; Từ đó đánh giá kết quả thu được.

Trong phần kết luận, luận văn tóm tắt lại những công việc đã thực hiện và các kết quả đạt được. Đồng thời cũng đề cập đến những điểm còn hạn chế của

- 10 -

luận văn và hướng nghiên cứu trong tương lai.

- 11 -

CHƯƠNG 1

HỌC BÁN GIÁM SÁT THEO MÔ HÌNH TRƯỜNG NGẪU NHIÊN CÓ ĐIỀU KIỆN

1.1. Phương pháp học máy Trường ngẫu nhiên có điều kiện

Mô hình trường ngẫu nhiên có điều kiện (Conditional Random Fields, viết tắt là CRFs) được Lafferty và cộng sự, 2001 [LCP01] giới thiệu lần đầu tiên vào năm 2001. CRFs là mô hình dựa trên xác suất có điều kiện, nó cho phép tích hợp được các thuộc tính đa dạng của chuỗi dữ liệu quan sát nhằm hỗ trợ cho quá trình phân lớp. Tuy nhiên, khác với các mô hình xác suất khác, CRFs là mô hình đồ thị vô hướng. Điều này cho phép CRFs có thể định nghĩa phân phối xác suất của toàn bộ chuỗi trạng thái với điều kiện biết chuỗi quan sát cho trước thay vì phân phối trên mỗi trạng thái với điều kiện biết trạng thái trước đó và quan sát hiện tại như trong các mô hình đồ thị có hướng khác. Theo Lafferty và cộng sự [LCP01], Hanna M. Wallach, 2002 và 2004 [Wal02, Wal04], bản chất “phân phối điều kiện” và “phân phối toàn cục” của CRFs cho phép mô hình này khắc phục được những nhược điểm của các mô hình trước đó trong việc gán nhãn và phân đoạn các dữ liệu dạng chuỗi mà tiêu biểu là vấn đề ‘label bias’.

Khi đề cập đến trường ngẫu nhiên có điều kiện, chúng ta sử dụng một số

qui ước kí hiệu:

 Chữ viết hoa X, Y, Z…kí hiệu các biến ngẫu nhiên.  Chữ thường đậm x, y, t, s,…kí hiệu các vector như vector biểu diễn

chuỗi các dữ liệu quan sát, vector biểu diễn chuỗi các nhãn …

 Chữ viết thường in đậm và có chỉ số là kí hiệu của một thành phần trong một vector, ví dụ xi chỉ một thành phần tại vị trí i trong vector x.  Chữ viết thường không đậm như x, y,… là kí hiệu các giá trị đơn như

một dữ liệu quan sát hay một trạng thái.

 S: Tập hữu hạn các trạng thái của một mô hình CRFs.

1.1.1. Khái niệm trường ngẫu nhiên có điều kiện

Kí hiệu X là biến ngẫu nhiên nhận giá trị là chuỗi dữ liệu cần phải gán nhãn và Y là biến ngẫu nhiên nhận giá trị là chuỗi nhãn tương ứng. Mỗi thành phần Yi của Y là một biến ngẫu nhiên nhận giá trị trong tập hữu hạn các trạng thái S. Trong bài toán gán nhãn từ loại, X có thể nhận giá trị là các câu trong ngôn ngữ

- 12 -

vN (



))

(

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ừ,...).

(1.1) 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]:  ,  ,  ) YXYP YXYPv ( |   v v

Ở đâ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ó

Yn-1

Y Hình 1. Đồ thị vô hướng mô tả CRFs

dạng:

xy |





x

)

(



CA 

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]): ( A A (1.2)

Vì trong các bài toán xử lý dữ liệu dạng chuỗi, đồ thị biểu diễn cấu trúc của một CRF có dạng đường thẳng như trong hình 1 cho nên tập C phải là hợp của E và V, trong đó E là tập các cạnh của đồ thị G và V là tập các đỉnh của G, hay nói cách khác đồ thị con A hoặc chỉ gồm một đỉnh hoặc chỉ gồm một cạnh của G.

- 13 -

1.1.2. Học máy CRFs

x

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ũ. 





 Af k

 A

 k

 exp

(1.3)

k là trọng số chỉ

Ở đây fk là một thuộc tính của chuỗi dữ liệu quan sát và

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:

xy )| ( P





y (





t kk

1 

(1.4)

xy ), i

s kk

xy ( ), i





1 x )(

 exp  

  

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

Ở đây, x, y là chuỗi dữ liệu quan sát và chuỗi trạng thái tương ứng; tk là thuộc tính của tòan bộ chuỗi quan sát và các trạng thái tại ví trí i-1, i trong chuỗi trạng thái; sk là thuộc tính của toàn bộ chuỗi quan sát và trạng thái tại ví trí i trong chuỗi trạng thái.

= Thừa số chuẩn hóa Z(x) được tính như sau:

x )(





(

y



(

t kk

(1.5)

xy ), i

1 

 k

xy ), i





   exp  

  

,...,

(

..)

 2 2

Đặt 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.

- 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:

x )(



x

 yyM ,'(

)

,'( yyM

(1.6)

x ),



exp



,'( yy

x ),



x ),( y

t kk

 k



  

  

(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)}

)( yi

(1.8) Chuỗi y* được xác định bằng thuật toán Viterbi cải tiến [Spr07] như mô tả là xác suất của “chuỗi trạng thái độ dài i kết thúc trong hình 2. Định nghĩa

)

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.

i y ( k

)

Giả sử biết tất cả với mọi yk thuộc tập trạng thái S của mô hình, cần

y (1 i



(

)



max

(

xác định . Từ hình 2, ta suy ra công thức truy hồi

x ),

 

1 

yMy k

1 

  y k

)

y (1

)

( 1yi

(1.9)

) ( 2yi

?

)

i y ( N



arg

max

,'(

Hình 2. Một bước trong thuật toán Viterbi cải tiến

),

ye )( i

 

xyyMy *)'( i

Đặt . 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

y

n )(*



arg

max

)( y

 n

o i  n

- 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ề

- 16 -

1.2.1.1. Học không có giám sát và Học có giám sát

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.

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

- 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.

biểu diễn vector cột của các nhãn. Như đã nêu, Nếu nhãn là các số, 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

- 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

- 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

- 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

- 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ự đ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 đượ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

- 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 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.

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 -

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 toá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 -

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ự đoá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ự đoá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.

(2.1)

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à

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 -

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

là giá trị đích và cho ∆(·, ·) là hàm khoảng

đến giá trị đích cho Eθ[f(X)]. Cho 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 -

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

. Trong [MC10], Gideon S. Mann và Andrew McCallum tiêu GEC là đặ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)

(2.6)

Với tiềm năng không chính thức

Trong đó là phân bố mục tiêu và

(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 toán Gradient (Độ chênh lệch)

- 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 toá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 toá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 -

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 toán tiến/lùi, xây dựng một giàn kết quả trung gian:

(2.12)

được lưu ở mỗi giai Để hiệu quả,

đ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 toá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 toán trích chọn thông tin từ văn bản pháp luật tiếng Việt.

- 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 -

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 -

đứ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 Ngoà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 toá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 toá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 toá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à http://www.cand.com.vn.

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 toá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 -

(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ụ:

B-LOC

Thủy_thủ Nguyễn_Ngọc_Hới B-PER xã Quảng_Phúc I-LOC , O Quảng_Trạch B-LOC O từng là O bộ_đội O đi O chiến_trường O B B-MISC O năm 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 -

Tập các văn bản đầu vào

chứa các đoạn văn

Module tách từ Tiếng Việt

lý

Gán nhãn POS Giai đoạn 1. Các bước tiền xử dữ liệu

Gán nhãn NER

Tập dữ liệu ra với định dạng

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)

Mô hình CRFs với GEC (được hiệu chỉnh sau mỗi bước)

Kết thúc học ?

Dữ liệu kiểm tra

Giai đoạn 2. Hoc bán giám sát CRFs voi GEC

Mô hình CRFs

Kết quả đánh giá mô hình

- 34 -

Hình 3/4. Mô hình đề xuất giải quyết bài toá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).

tác giả Lê Hồng Phương tool vnTagger của tại

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 http://jvnsegmenter.sourceforge.net . Đâ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 toán xử lý văn bản, đặc biệt là các bài toá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 trang web http://www.loria.fr/~lehong/tools/vnTagger.php . Đâ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 http://mallet.cs.umass.edu/. 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 toá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 -

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 hoà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 -

3.2.3. Lựa chọn thuộc tính

Ý nghĩa

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ổ

Âm tiết quan sát tại vị trí -2 so với vị trí hiện tại Âm tiết quan sát tại vị trí liền trước so với vị trí hiện tại Âm tiết quan sát tại vị trí liền sau so với vị trí hiện tại Âm tiết quan sát tại vị trí +2 so với vị trị hiện tại Âm tiết quan sát tại vị trí hiện tại và vị trí liền sau Âm tiết quan sát tại vị trí liền trước và vị trí hiện tại Âm tiết quan sát tại vị trí -2 và vị trí liền trước Âm tiết quan sát tại vị trí 2 và vị trí liền sau Âm tiết quan sát tại vị trí liền trước, hiện tại và liền sau Âm tiết quan sát tại vị trí -2, vị trí liền trước và hiện tại Âm tiết quan sát tại vị trí 2, vị trí liền sau và hiện tại

trượt bằng 5): Mẫu ngữ cảnh S-2 S-1 S1 S2 S0S1 S-1S0 S-2S-1 S1S2 S-1S0S1 S-2S-1S0 S0S1S2

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 InitialCap AllCaps CapsMix SingleDigit HasDigit DoubleDigits Ý nghĩa Viết hoa chữ cái đầu Viết hoa tất cả các chữ cái Chữ cái thường và hoa lẫn lộn Số 1 chữ số Có chứa số 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 -

ecision 

a b

(3.1)

a c

(3.2) call 

measure



ecision Re*  Re

Pr*2 (Pr

call call

ecision

(3.3) 

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:

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 toá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 toá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.

- 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 http://www.cand.com.vn. 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. Ngoà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 -

- 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 toà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.

CRF

CRF.ER

CRF.GE

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

NaN

0.0000

OVERALL

0.7489

0.9859

0.7863

0.9290

0.8825

0.9051

0.9044

0.9756

0.9386

Bảng 3. Kết quả nhóm thực nghiệm 1

- 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

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 -

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.9918

1.0000

0.9959

MISC

0.8310

0.9833

0.9008

0.9815

0.7910

0.8760

0.9350

0.9890

0.9601

OVERALL

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

PER

0.9232

0.9453

0.9341

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

0.9350

0.9773

0.9545

OVERALL

0.9927

0.9895

0.9911

- 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ữ

CRF

CRF.ER

Precision Recall F-measure Precision Recall F-measure

ORG

0.9989

1.0000

0.9995

0.9777

PER

0.9931

0.9993

0.9962

0.9956

0.9927

0.9941

LOC

1.0000

0.9973

1.0000

0.9986

MISC

0.9155

0.9559

0.9353

1.0000

0.9254

0.9612

liệu huấn luyện 100% và tập dữ liệu kiểm tra.

0.9769

0.9888

0.9827

OVERALL

0.9939

0.9911

0.9925

Bảng 7. Kết quả nhóm thực nghiệm 5

- 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 hoà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 -

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 -

KẾT LUẬN

Sau một thời gian tìm hiểu và nghiên cứu về bài toá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 toá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 -

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 hoà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à hoà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 -

TÀI LIỆU THAM KHẢO

[AG05]

[BC01]

[BC09]

[BLR04]

[BM98]

[BN04]

[BNJ03]

M. R. Amini and P. Gallinari. Semi-supervised learning with an imperfect supervisor. Knowledge and Information Systems, 8(4):385–413, 2005. 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. 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. 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. 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. M. Belkin and P. Niyogi. Semi-supervised learning on Riemannian manifolds. Machine Learning, 56(1-3):209–239, 2004. David M. Blei, Andrew Y.Ng và Michael I.Jordan. Latent Dirichlet Allocation. University of California, Berkeley, Berkeley, CA 94720. 2003

[BNS06]

[BNS05] M. Belkin, P. Niyogi, and V. Sindhwani. On manifold regularization. In Proceedings of the 10th International Workshop on Artiﬁcial Intelligence and Statistics, pages 17–24, Savannah, Barbados, 2005. 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. Scheﬀer. Semi-supervised learning for structured output

[Car10]

variables. In Proceedings of the 23rd International Conference on Machine Learning, pages 145–152, Pittsburgh, PA, 2006. Andrew Carlson (2010). Coupled Semi-Supervised Learning, PhD Thesis (CMU-ML-10-104), Carnegie Mellon University, 2010.

- 48 -

[CZ05]

[DLR77]

[CMD07] Andrew McCallum, Gideon Mann, Gregory Druck (2007). Generalized Expectation Criteria, Technical Report UM-CS-2007-60, University of Massachusetts Amherst, August, 2007 O. Chapelle and A. Zien. Semi-supervised learning by low density separation. In proceedings of the 10th International Workshop on Artiﬁcial Intelligence and Statistics, pages 57–64. Savannah Hotel, Barbados, 2005. 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.

[Erk10]

[FUS05]

[GB04]

[GY05]

[GZ00]

[HC71]

[HM07]

[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. Ayse Naz Erkan (2010). Semi-supervised Learning via Generalized Maximum Entropy, PhD Thesis, New York University, 2010. A. Fujino, N. Ueda, and K. Saito. A hybrid generative/discriminative approach to semi-supervised classiﬁer design. In Proceedings of the 20th National Conference on Artiﬁcial Intelligence, pages 764–769, Pittsburgh, PA, 2005. Y.Grandvaletand, Y.Bengio. Semi-supervised learning by entropy minimization. In Advances in Neural Information Processing Systems, 2004. 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. 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. J.Hammersley and P. Clifford (1971). Markov fields on finite graphs and lattices. Unpublished manuscript. M. Hein and M. Maier. Manifold denoising. In B. Sch¨olkopf, J. C. Platt, and T. Ho(cid:0)man, editors, Advances in Neural Information Processing Systems 19, pages 561–568. MIT Press, Cambridge, MA, 2007.

- 49 -

[Joa99]

[JWL06]

[KL51]

[KQ10]

[Kul59]

[LCP01]

[LJ05]

[Mal02]

[MC08]

[MC10]

[MGZ04]

T. Joachims. Transductive inference for text classiﬁcation using support vector machines. In Proceedings of the 16th International Conference on Machine Learning, pages 200–209, Bled, Slovenia, 1999 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. S. Kullback and R. A. Leibler. On Information and Sufficiency. Annuals of Mathematical Statistics 22 (1): pages 79–86, 1951. Pavel P. Kuksa, Yanjun Qi (2010). Semi-Supervised Bio-Named Entity Recognition with Word-Codebook Learning, SDM 2010: 25-36, 2010. S. Kullback. Information theory and statistics. John Wiley and Sons, NY, 1959. 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. 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. 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. Gideon S. Mann, Andrew McCallum (2008). Generalized Expectation Criteria for Semi-Supervised Learning of Conditional Random Fields, ACL- 08 (HLT): 870–878, 2008. 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 Scott Miller, Jethran Guinness, Alex Zamanian (2004). Name Tagging with Word Clusters and Discriminative Training, ACL 04, 2004.

[MU97]

[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. D. J. Miller and H. S. Uyar. A mixture of experts classiﬁer with learning based on both labelled and unlabelled data. In M. Mozer, M. I. Jordan, and

- 50 -

[NCT00]

T. Petsche, editors, Advances in Neural Information Processing Systems 9, pages 571–577. MIT Press, Cambridge, MA, 1997. K.Nigam, A. K. McCallum, S. Thrun, and T. Mitchell. Text classiﬁcation from labeled and unlabeled documents using EM. Machine Learning, 39(2- 3):103–134, 2000.

[NG00]

K. Nigam and R. Ghani. Analyzing the eﬀectiveness 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 eﬀect of unlabeled samples in

[Spr07]

[Wal02]

[Wal04]

reducing the small sample size problem and mitigating the hughes phenomenon. IEEE Transactions on Geo-science and Remote Sensing, 32(5):1087–1095, 1994. 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. Hanna M. Wallach. Efficient Training of Conditional Random Fields. Technical Report, University of Edinburgh, 2002 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.

[ZBL04]

[WHW09] Yang Wang, Gholamreza Haffari, Shaojun Wang, Greg Mori (2009). A Rate Distortion Approach for Semi-Supervised Conditional Random Fields, NIPS2009, 2009. 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 -

[ZC06]

editors, Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2004. 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. Laﬀerty. Semi-supervised learning using

[Zho08]

[ZL05]

[ZL07]

[ZL07b]

[ZL10]

[ZZY07]

Gaussian ﬁelds and harmonic functions. In Proceedings of the 20th International Conference on Machine Learning, pages 912–919, Washington, DC, 2003. Z. H. Zhou. Semi-supervised learning by disagreement. In Proceedings of the 4th IEEE International Conference on Granular Computing, Hangzhou, China, 2008. Z. H. Zhou and M. Li. Tri-training: Exploiting unlabeled data using three classiﬁers. IEEE Transactions on Knowledge and Data Engineering, 17(11):1529–1541, 2005. 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. 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. Zhi-Hua Zhou and Ming Li. Semi-supervised Learning by Disagreement. National Key Laboratory for Novel Software Technology Nanjing University, Nanjing 210093, China. 2010. 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 Artiﬁcial Intelligence, pages 675–680, Vancouver, Canada, 2007.