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

- 1 -

TRƯỜNG ………………….

KHOA……………………….

----------

Báo cáo tốt nghiệp

Đề tài:

TRÍCH CHỌN THÔNG TIN TRÊN TẬP VĂN BẢN PHÁP LUẬT DÙNG KỸ

THUẬT HỌC MÁY BÁN GIÁM SÁT DỰA TRÊN MÔ HÌNH CRFs THEO TIÊU

CHUẨN KỲ VỌNG TỔNG QUÁT

1

- 2 -

LỜI CAM ĐOAN

Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá

nhân tôi, không sao chép lại của người khác. Trong toàn bộ nội dung của luận

văn, những điều được trình bày hoặc là của cá nhân hoặc là được tổng hợp từ

nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và

được trích dẫn hợp pháp. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình

thức kỷ luận theo quy định cho lời cam đoan của mình.

Hà Nội, 05/2011

Phạm Thị Ngân

2

- 3 -

MỤC LỤC

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

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

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

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

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

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

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

CHƯƠNG 1: HỌC BÁN GIÁM SÁT THEO MÔ HÌNH TRƯỜNG NGẪU

NHIÊN CÓ ĐIỀU KIỆN.................................................................................. 11

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

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

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

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

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

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

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

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

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

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

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

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

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

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

VỌNG TỔNG QUÁT ...................................................................................... 23

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

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

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

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

3

- 4 -

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

CHƯƠNG 3: MỘT MÔ HÌNH HỌC MÁY BÁN GIÁM SÁT CRFs TRÍCH

CHỌN THÔNG TIN PHÁP LUẬT TIẾNG VIỆT ......................................... 29

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

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

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

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

tiếng Việt ...................................................................................................... 31

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4

- 5 -

DANH MỤC HÌNH VẼ

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

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

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

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

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

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

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

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

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

5

- 6 -

DANH MỤC BẢNG BIỂU

Bảng 1. Mẫu ngữ cảnh từ vựng ........................................................................ 36

Bảng 2. Mẫu ngữ cảnh phát hiện tên thực thể .................................................. 36

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

Bảng 4. Kết quả nhóm thực nghiệm 2............................................................... 40

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

Bảng 6. Kết quả nhóm thực nghiệm 4............................................................... 42

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

6

- 7 -

KÝ TỰ VIẾT TẮT

CRFs

EM

Conditional Random Fields

Entropy Maximum

GE

Generalized Expectation

Generalized Expectation Criteria

Generalized Iterative Scaling

independently and identically

Improved Iterative Scaling

Kullback Leibler

GEC

GIS

i.i.d

IIS

KL

L-BFGS

LOC

MISC

NER

ORG

PER

Limited memory Broyden–Fletcher–Goldfarb–Shanno

LOCation

MIScellaneous

Named Entity Recognition

ORGanization

PERson

7

- 8 -

LỜI CẢM ƠN

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

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

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

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

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

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

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

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

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

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

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

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

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

Hà Nội, tháng 05 năm 2011

Học viên

Phạm Thị Ngân

8

- 9 -

LỜI MỞ ĐẦU

Trích chọn thông tin là một khâu cơ bản trong bài toán khai phá dữ liệu.

Ngày nay, cùng với sự phát triển của công nghệ thông tin, Tin học đã dần được

ứng dụng rộng rãi trong nhiều lĩnh vực như kinh tế, thương mại, y tế, ngân hàng

và mang lại nhiều lợi ích to lớn. Bản thân tôi hiện đang công tác tại Học viện

Cảnh sát nhân dân, tôi có những hiểu biết nhất định về công tác giữ gìn trật tự an

toàn xã hội của lực lượng cảnh sát nhân dân. Tôi nhận thấy, các hoạt động của

lực lượng cảnh sát có liên quan nhiều đến việc lưu trữ hồ sơ dữ liệu, tra cứu,

phân tích tổng hợp dữ liệu... Tuy nhiên, công tác quản lý hồ sơ dữ liệu này vẫn

còn kém hiệu quả do những hạn chế nhất định. Do đó tôi đã mạnh dạn chọn đề

tài tập trung nghiên cứu vào việc trích lọc thông tin trên tập văn bản pháp luật

này.

Trong nhiều thập kỷ qua, các nhà khoa học quan tâm đến lĩnh vực xử lý

ngôn ngữ tự nhiên đã nghiên cứu và đề xuất được nhiều phương pháp, mô hình

xử lý ngôn ngữ với hiệu quả cao. Nổi bật trong số đó là phương pháp học máy

bán giám sát dựa trên mô hình trường ngẫu nhiên có điều kiện theo tiêu chuẩn

kỳ vọng tổng quát, phương pháp này đạt được kết quả rất khả quan trên tập dữ

liệu ngôn ngữ tiếng Anh và hiện chưa được áp dụng cho tiếng Việt. Được sự

giúp đỡ và đồng ý của Thầy giáo hướng dẫn TS. Nguyễn Lê Minh, tác giả quyết

định sử dụng mô hình này ứng dụng cho tập văn bản pháp luật.

Bố cục của luận văn chia thành 4 chương như sau:

Chương 1: Trình bày những kiến thức cơ bản về mô hình trường ngẫu

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

Chương 2: Trình bày về tiêu chuẩn kỳ vọng tổng quát và áp dụng tiêu

chuẩn kỳ vọng tổng quát vào mô hình trường ngẫu nhiên có điều kiện.

Chương 3: Trình bày về bài toán trích chọn thưc thể trên tập văn bản pháp

luật và đề xuất mô hình giải quyết bài toán dựa trên mô hình CRFs theo

tiêu chuẩn kỳ vọng tổng quát.

Chương 4: Trình bày các thực nghiệm trên tập dữ liệu sử dụng một số mô

hình học máy có giám sát CRFs, và mô hình học máy bán giám sát

CRFs theo chuẩn hóa entropy và theo tiêu chuẩn kỳ vọng tổng quát; Từ

đó đánh giá kết quả thu được.

Trong phần kết luận, luận văn tóm tắt lại những công việc đã thực hiện và

các kết quả đạt được. Đồng thời cũng đề cập đến những điểm còn hạn chế của

9

- 10 -

luận

văn

và

hướng

nghiên

cứu

trong

tương

lai.

10

- 11 -

CHƯƠNG 1

HỌC BÁN GIÁM SÁT THEO MÔ HÌNH

TRƯỜNG NGẪU NHIÊN CÓ ĐIỀU KIỆN

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

Mô hình trường ngẫu nhiên có điều kiện (Conditional Random Fields, viết

tắt là CRFs) được Lafferty và cộng sự, 2001 [LCP01] giới thiệu lần đầu tiên vào

năm 2001. CRFs là mô hình dựa trên xác suất có điều kiện, nó cho phép tích hợp

được các thuộc tính đa dạng của chuỗi dữ liệu quan sát nhằm hỗ trợ cho quá

trình phân lớp. Tuy nhiên, khác với các mô hình xác suất khác, CRFs là mô hình

đồ thị vô hướng. Điều này cho phép CRFs có thể định nghĩa phân phối xác suất

của toàn bộ chuỗi trạng thái với điều kiện biết chuỗi quan sát cho trước thay vì

phân phối trên mỗi trạng thái với điều kiện biết trạng thái trước đó và quan sát

hiện tại như trong các mô hình đồ thị có hướng khác. Theo Lafferty và cộng sự

[LCP01], Hanna M. Wallach, 2002 và 2004 [Wal02, Wal04], bản chất “phân phối

điều kiện” và “phân phối toàn cục” của CRFs cho phép mô hình này khắc phục

được những nhược điểm của các mô hình trước đó trong việc gán nhãn và phân

đoạn các dữ liệu dạng chuỗi mà tiêu biểu là vấn đề ‘label bias’.

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

qui ước kí hiệu:

 Chữ viết hoa X, Y, Z…kí hiệu các biến ngẫu nhiên.

 Chữ thường đậm x, y, t, s,…kí hiệu các vector như vector biểu diễn

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

 Chữ viết thường in đậm và có chỉ số là kí hiệu của một thành phần

trong một vector, ví dụ x_ichỉ 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 Y_i

của Y là một biến ngẫu nhiên nhận giá trị trong tập hữu hạn các trạng thái S.

Trong bài toán gán nhãn từ loại, X có thể nhận giá trị là các câu trong ngôn ngữ

11

- 12 -

tự nhiên (gồm các từ), Y là một chuỗi ngẫu nhiên các nhãn tương ứng với các từ

tạo thành câu này và mỗi một thành phần Y_icủa Y có miền giá trị là tập tất cả các

nhãn từ loại có thể (danh từ, động từ, tính từ,...).

Cho một đồ thị vô hướng phi chu trình G = (V, E), ở đây V là tập các đỉnh

của đồ thị và E là tập các cạnh vô hướng nối các đỉnh đồ thị. Các đỉnh V biểu

diễn các thành phần của biến ngẫu nhiên Y sao cho tồn tại ánh xạ một- một giữa

một đỉnh và một thành phần Y_vcủ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

Y_vtuân theo tính chất Markov đối với đồ thị G [LCP01]:

P(Y | X,Y_,  v)  P(Y | X,Y_,N(v))

(1.1)

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=(X₁, X₂,…, X_n), Y=(Y₁,Y₂,...,Y_n). Mô hình đồ thị cho CRFs có

dạng:

Y_n-1

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

Gọi C là tập hợp tất cả các đồ thị con đầy đủ của đồ thị G - đồ thị biểu diễn

cấu trúc của một CRFs. Áp dụng kết quả của J.Hammersley và P. Clifford, 1971

[HC71] cho các trường ngẫu nhiên Markov, sẽ thừa số hóa được p(y|x) - xác

suất của chuỗi nhãn với điều kiện biết chuỗi dữ liệu quan sát - thành tích của

các hàm tiềm năng như sau (theo [Wal04]):

P(y | x) 

 ( A | x)

(1.2)



A

AC

Vì trong các bài toán xử lý dữ liệu dạng chuỗi, đồ thị biểu diễn cấu trúc của

một CRF có dạng đường thẳng như trong hình 1 cho nên tập C phải là hợp của E và

V, trong đó E là tập các cạnh của đồ thị G và V là tập các đỉnh của G, hay nói cách

khác đồ thị con A hoặc chỉ gồm một đỉnh hoặc chỉ gồm một cạnh của G.

12

- 13 -

1.1.2. Học máy CRFs

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

Lafferty và cộng sự [LCP01] giới thiệu phương pháp xác định các hàm

tiềm năng cho các mô hình CRFs dựa trên nguyên lý cực đại hóa Entropy. Cực

đại hóa Entropy là một nguyên lý cho phép đánh giá các phân phối xác suất từ

một tập các dữ liệu huấn luyện. Bằng cách áp dụng nguyên lý cực đại hóa

Entropy, Lafferty xác định hàm tiềm năng của một CRF có dạng một hàm mũ.









 A | x  exp  f A | x

(1.3)



A

k

Ở đây f_klà một thuộc tính của chuỗi dữ liệu quan sát và  _klà trọng số chỉ

mức độ biểu đạt thông tin của thuộc tính f_k.

Có hai loại thuộc tính là thuộc tính chuyển (kí hiệu là t) và thuộc tính trạng

thái (kí hiệu là s) tùy thuộc vào A là đồ thị con gồm một đỉnh hay một cạnh của

G. Thay các hàm tiềm năng vào công thức (1.2) và thêm vào đó một thừa số

chuẩn hóa Z(x) để đảm bảo tổng xác suất của tất cả các chuỗi nhãn tương ứng

với một chuỗi dữ liệu quan sát bằng 1, ta được:

1





P(y | x) 

exp

 t (y ,y ,x) 

 s (y ,x)





(1.4)

_



k

i1

i

k

i

Z(x)

i

k

i

k



Ở đây, x, y là chuỗi dữ liệu quan sát và chuỗi trạng thái tương ứng; t_klà

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; s_klà thuộc tính của toàn bộ chuỗi quan sát và trạng thái tại ví trí i

trong chuỗi trạng thái.

1 nếu x_i=Bill và y_i= B_PER

s_i=

0 nếu ngược lại

1 nếu x_i-1= “Bill”, x_i=”Clinton” và y_i-1=B_PER,y_i=I_PER

t_i=

0 nếu ngược lại

=

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







Z(x)  exp

 t (y ,y ,x) 

 s (y ,x)



(1.5)

 



k

i1

i

k

i

y

i

k

i

k





Đặt(₁,₂,...,_1,₂..) là các vector các tham số của mô hình,  được ước

lượng giá trị nhờ các phương pháp ước lượng tham số cho mô hình sẽ được đề

cập trong phần sau.

13

- 14 -

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

Tại mỗi vị trí i trong chuỗi dữ liệu quan sát, ta định nghĩa một ma trận

chuyển |S|×|S| như sau:

M _i(x) 



M _i(y', y, x)



(1.6)







M (y', y,x)  exp

 t (y', y,x)   s (y,x)



(1.7)

_



i

k



Ở đây M_i(y’, y, x) là xác suất chuyển từ trạng thái y’ sang trạng thái y với

chuỗi dữ liệu quan sát là x. Chuỗi trạng thái y* mô tả tốt nhất cho chuỗi dữ liệu

quan sát x là nghiệm của phương trình:

y* = argmax{p(y|x)}

(1.8)

Chuỗi y* được xác định bằng thuật toán Viterbi cải tiến [Spr07] như mô tả

trong hình 2. Định nghĩa _i(y) là xác suất của “chuỗi trạng thái độ dài i kết thúc

bởi trạng thái y và có xác suất lớn nhất” biết chuỗi quan sát là x.

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

 (y )

xác định

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

i1

j





_i1(y _j)  max _i1(y_k)*M_i(y_k, y _j,x) y_k S

(1.9)

_i1(y_j)

Pr_i(y₁)

_i(y₂)

?

Pr

_i(y_N)

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

Pr e_i(y)  arg max



_i1(y')* M _i(y', y, x)



Đặ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)  argmax



_n(y)



o

o i  n

14

- 15 -

 Bước lặp: chừng nào i>0

o i  i-1

o y  Pre_i(y)

o y*(i) = y

Chuỗi y* tìm được chính là chuỗi có xác suất p(y*|x) lớn nhất, đó cũng

chính là chuỗi nhãn phù hợp nhất với chuỗi dữ liệu quan sát cho trước.

Như vậy, do bản chất phân phối toàn cục của mình, CRFs có thể giải quyết

được vấn đề ‘label bias’, một nhược điểm tiêu biểu của mô hình MEM [MMI02,

Wal04]. Ở phương diện lý thuyết mô hình, ta có thể coi mô hình CRFs như là

một máy trạng thái xác suất với các trọng số không chuẩn hóa, mỗi trọng số gắn

liền với một bước chuyển trạng thái. Bản chất không chuẩn hóa của các trọng số

cho phép các bước chuyển trạng thái có thể nhận các giá trị quan trọng khác

nhau. Vì thế bất cứ một trạng thái nào cũng có thể làm tăng hoặc giảm xác suất

được truyền cho các trạng thái sau nó mà vẫn đảm bảo xác suất cuối cùng được

gán cho toàn bộ chuỗi trạng thái thỏa mãn định nghĩa về xác suất nhờ thừa số

chuẩn hóa toàn cục.

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

Kĩ thuật được sử dụng để đánh giá tham số cho một mô hình CRFs là làm

cực đại hóa độ đo likelihood giữa phân phối mô hình và phân phối thực nghiệm.

Nguyên lý cực đại likelihood được phát biểu như sau: Các tham số tốt nhất

của mô hình là các tham số làm cực đại hàm likelihood. Như vậy, về phương

diện toán học, bài toán ước lượng tham số cho một mô hình CRFs chính là bài

toán tìm cực đại của hàm log-likelihood. Có nhiều phương pháp tìm cực đại của

hàm log-likelihood như các phương pháp lặp (IIS, GIS), các phương pháp tối ưu

số (phương pháp dựa trên vector gradient như phương pháp gradient liên hợp,

quasi-Newton …) và L-BFGs có thể phục vụ cho ước lượng tham số mô hình.

Trong các phương pháp tìm cực trị hàm log-likelihood này, phương pháp L-

BFGs được đánh giá là vượt trội và có tốc độ hội tụ nhanh nhất [Mal02].

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

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

Trong lý thuyết xác suất, một dãy các biến ngẫu nhiên được gọi là có độc

lập cùng phân phối nếu chúng có cùng một phân phối và độc lập với nhau. Các

quan sát trong một mẫu thường được giả thiết là độc lập cùng phân phối nhằm

làm đơn giản hoá tính toán toán học bên dưới của nhiều phương pháp thống kê.

Trong nhiều ứng dụng, điều này thường không thực tế. Trước khi nghiên cứu về

15

- 16 -

học máy bán giám sát, tôi giới thiệu sơ bộ về hai phương pháp học máy cơ bản

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

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

Học không có giám sát (unsupervised learning): Là phương pháp học máy

nhằm tìm ra một mô hình phù hợp với các quan sát. Cho trước một mẫu chỉ gồm

các đối tượng (objects), cần tìm kiếm cấu trúc quan tâm (interesting structures)

của dữ liệu, và nhóm các đối tượng giống nhau.

Học không giám sát thường coi các đối tượng đầu vào là một tập các biến

ngẫu nhiên. Sau đó, một mô hình mật độ kết hợp sẽ được xây dựng cho tập dữ

liệu đó. Biểu diễn toán học của phương pháp này như sau:

Cho X=(x₁, x₂, …, x_n) là tập hợp gồm n mẫu (examples or points), x_i∈

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 (x_i,y_i), cần tìm ra mối quan hệ dự đoán giữa các đối tượng và các nhãn.

Mục đích là học một phép ánh xạ từ x tới y, khi cho trước một tập huấn luyện

16

- 17 -

gồm các cặp (x_i,y_i), trong đó y_i∈ Y gọi là các nhãn hoặc đích của các mẫu X_i.

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 (x_i,y_i) 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á x_iđược tạo ra

như thế nào mà tập trung đánh giá p(y|x) . Một vài phương pháp discriminative

hạn chế chúng để mô hình xem p(y|x) lớn hơn hoặc nhỏ hơn 0.5, ví dụ như

SVM. Trong thực hành, phương pháp này thường được đánh giá là hiệu quả hơn

phương pháp sinh (generative).

Để có thể giải quyết một bài toán nào đó của học có giám sát người ta phải

xem xét nhiều bước khác nhau:

1. Xác định loại của các ví dụ huấn luyện. Trước khi làm bất cứ điều gì,

người kĩ sư nên quyết định loại dữ liệu nào sẽ được sử dụng làm ví

dụ. Chẳng hạn, đó có thể là một kí tự viết tay đơn lẻ, toàn bộ một từ

viết tay, hay toàn bộ một dòng chữ viết tay.

2. Thu thập tập huấn luyện. Tập huấn luyện cần đặc trưng cho thực tế sử

dụng của hàm chức năng. Vì thế, một tập các đối tượng đầu vào được

thu thập và đầu ra tương ứng được thu thập, hoặc từ các chuyên gia

hoặc từ việc đo đạc tính toán.

3. Xác định việc biễu diễn các đặc trưng đầu vào cho hàm chức năng cần

tìm. Sự chính xác của hàm chức năng phụ thuộc lớn vào cách các đối

17

- 18 -

tượng đầu vào được biểu diễn. Thông thường, đối tượng đầu vào được

chuyển đổi thành một vec-tơ đặc trưng, chứa một số các đặc trưng

nhằm mô tả cho đối tượng đó. Số lượng các đặc trưng không nên quá

lớn, do sự bùng nổ tổ hợp; nhưng phải đủ lớn để dự đoán chính xác

đầu ra.

4. Xác định cấu trúc của hàm chức năng cần tìm và giải thuật học tương

ứng. Ví dụ, người kĩ sư có thể lựa chọn việc sử dụng mạng nơ-ron

nhân tạo hay cây quyết định.

5. Hoàn thiện thiết kế. Người kĩ sư sẽ chạy giải thuật học từ tập huấn

luyện thu thập được. Các tham số của giải thuật học có thể được điều

chỉnh bằng cách tối ưu hóa hiệu năng trên một tập con (gọi là tập

kiểm chứng -validation set) của tập huấn luyện, hay thông qua kiểm

chứng chéo (cross-validation). Sau khi học và điều chỉnh tham số,

hiệu năng của giải thuật có thể được đo đạc trên một tập kiểm tra độc

lập với tập huấn luyện.

Trong “học có giám sát”, các dữ liệu được gán nhãn nên việc giải quyết

vấn đề thường thuận lợi hơn rất nhiều. Tuy nhiên, với một số lượng dữ liệu lớn

thì công việc gán nhãn cho dữ liệu đòi hỏi nỗ lực của con người và tốn nhiều

thời gian. Còn “học không có giám sát” là mô hình hóa một tập dữ liệu, trong đó

dữ liệu đầu vào chưa được gán nhãn mà nó dựa trên môt mô hình phù hợp với

các quan sát, vì vậy với một số lượng lớn dữ liệu thì sự chính xác của kết quả

thu được không cao. Thực tế cho thấy rằng, dữ liệu chưa được gán nhãn có thể

thu thập được rất nhiều và một cách dễ dàng. Tuy nhiên để xử lý số lượng dữ

liệu đó có kết quả tốt cũng gặp nhiều khó khăn.

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

“Học máy bán giám sát” là sự kết hợp giữa “học có giám sát” và “học

không có giám sát”. Với một số lượng lớn dữ liệu, kể cả dữ liệu chưa gán nhãn

và những dữ liệu đã được gán nhãn, sẽ được “máy học” giải quyết bằng một

cách tốt nhất bằng các giải thuật “học bán giám sát.

Từ đó, học bán giám sát có thể được xem là:

- Học giám sát cộng thêm dữ liệu chưa gán nhãn (Supervised learning

+additional unlabeled data).

- Học không giám sát cộng thêm dữ liệu gán nhãn (Unsupervised

learning + additional labeled data).

Học bán giám sát chính là cách học sử dụng thông tin có ở cả dữ liệu gán

nhãn (trong tập dữ liệu huấn luyện) lẫn dữ liệu chưa gán nhãn. Các thuật toán

18

- 19 -

học bán giám sát có nhiệm vụ chính là mở rộng tập các dữ liệu gán nhãn ban

đầu. Hiệu quả của thuật toán phụ thuộc vào chất lượng của các mẫu gán nhãn

được thêm vào ở mỗi vòng lặp và được đánh giá dựa trên hai tiêu chí:

- Các mẫu được thêm vào phải được gán nhãn một cách chính xác.

- Các mẫu được thêm vào phải mang lại thông tin hữu ích cho bộ phân

lớp (hoặc dữ liệu huấn luyện).

Các phương pháp học bán giám sát sẽ rất hữu ích khi dữ liệu chưa gán nhãn

nhiều hơn dữ liệu gán nhãn. Việc thu được dữ liệu gán nhãn là rẻ, nhưng để gán

nhãn chúng thì tốn rất nhiều thời gian, công sức và tiền bạc. Đó là tình trạng của

rất nhiều các lĩnh vực ứng dụng trong học máy như:

- Trong nhận dạng lời nói, ta sẽ dễ dàng ghi lại một lượng lớn các bài diễn

thuyết, nhưng để gán nhãn chúng yêu cầu con người phải lắng nghe rồi đánh

máy sao chép lại.

- Sự phong phú của hàng tỉ các trang web sẵn sàng cho xử lý tự động, nhưng

để phân lớp chúng một cách tin cậy đòi hỏi con người phải đọc chúng.

- ...

Học bán giám sát là việc học trên cả dữ liệu đã và chưa được gán nhãn. Từ

một số lượng lớn các dữ liệu chưa được gán nhãn, và một tập với số luợng nhỏ

dữ liệu đã được gán nhãn ban đầu (thường gọi là seed set) để xây dựng một bộ

phân lớp thậm chí là tốt hơn. Trong quá trình học như thế, phương pháp học sẽ

tận dụng được những thông tin phong phú của dữ liệu chưa gán nhãn, mà chỉ

yêu cầu một số lượng rất nhỏ các dữ liệu đã gán nhãn.

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

Theo Zhi-Hua Zhou và Ming Li, 2010 [ZL10], có rất nhiều các thuật toán

học máy bán giám sát và có thể chia thành bốn nhóm phương pháp như sau:

phương pháp sinh [MU97, NCT00, SL94], S3VMs (Semi-Supervised Support

Vector Machines – phương pháp máy vectơ hỗ trợ bán giám sát) [CZ05, GY05,

Joa99, LJ05], phương pháp dựa trên đồ thị [BN04, BNS05, BNS06, ZBL04,

ZGL03] và phương pháp dựa trên mâu thuẫn [ZL07, ZL05, ZZY07, ZC06,

NG00, GZ00, BS06, BM98].

- Trong phương pháp sinh, cả tập mẫu gán nhãn và chưa gán nhãn được giả

thiết được sinh ra từ mô hình cùng tham số. Do đó, những tham số mô

hình có liên kết trực tiếp những mẫu chưa gán nhãn với mục tiêu học.

Những mô hình trong phương pháp này thường coi những nhãn của dữ

liệu chưa gán nhãn là những giá trị thiếu của tham số mô hình và sử dụng

thuật toán cực đại hóa kỳ vọng EM [DLR77] để tính toán ước lượng cực

19

- 20 -

đại likelihood của tham số mô hình. Những thuật toán trong phương pháp

này khác nhau ở mô hình sinh được sử dụng để phù hợp với dữ liệu, ví dụ

phương pháp pha trộn Gaussian [SL94], phương pháp Naïve Bayes

[NCT00]. Những mô hình sinh thực thi đơn giản, dễ dàng và có thể hiệu

quả hơn mô hình discriminative khi học với mẫu gán nhãn nhỏ. Tuy

nhiên, nhóm thuật toán này có nhược điểm lớn đó là khi giả thiết mô hình

sai hoặc mô hình sử dụng tập dữ liệu chưa gán nhãn lớn thì việc thực thi

bị kém hiệu quả. Do đó, để mô hình này thực thi có hiệu quả trong những

ứng dụng thực, cần phải tạo được mô hình sinh chính xác dựa trên miền

tri thức, hoặc người ta có thể kết hợp những mặt tích cực của mô hình

sinh và mô hình discriminative [AG05, FUS05]. Một số thuật toán điển

hình của phương pháp này được Xiaojin Zhu đề cập trong [Zhu08] như:

Thuật toán học bán giám sát cực đại kỳ vọng EM địa phương, Thuật toán

Self-training...

- Phương pháp S3VMs cố gắng sử dụng dữ liệu chưa gán nhãn để điều

chỉnh đường biên quyết định được học từ tập nhỏ những mẫu dữ liệu gán

nhãn, nhờ đó có thể đi qua được những vùng dày đặc trong khi vẫn giữ

được phân lớp chính xác cho dữ liệu gán nhãn. T. Joachims, 1999 [Joa99]

đề xuất mô hình TSVM (Transductive Support Vector Machine). Đầu

tiên, thuật toán này khởi tạo một SVM sử dụng những mẫu gán nhãn và

gán những nhãn tiềm năng cho dữ liệu chưa gán nhãn. Sau đó, nó lặp lại

việc cực đại hóa biên của cả dữ liệu gán nhãn và chưa gán nhãn với những

nhãn tiềm năng bằng cách đặt nhãn của dữ liệu chưa gán nhãn trên các

mặt của biên quyết định. Cách này có thể đạt được giải pháp tối ưu đó là

biên quyết định không chỉ phân lớp chính xác dữ liệu gán nhãn mà còn

tránh được việc đi qua vùng mật độ cao. Tuy nhiên, độ không lồi của hàm

thiệt hại (loss function) trong TSVM sẽ dẫn đến thực tế là có nhiều điểm

tối ưu cục bộ. Do đó nhiều nghiên cứu được đề xuất để giảm tác động tiêu

cực này.

- Phương pháp học bán giám sát dựa trên đồ thị đầu tiên có thể thực thi

được đề xuất bởi Blum và Chawla, 2001 [BC01], họ xây dựng một đồ thị

với các nút là những mẫu huấn luyện (cả gán nhãn và chưa gán nhãn) và

cạnh giữa các nút thể hiện mối quan hệ giữa những mẫu tương ứng ví dụ

như quan hệ đồng dạng. Dựa trên đồ thị này, vấn đề học bán giám sát có

thể được giải quyết bằng việc tìm đường cắt nhỏ nhất của đồ thị mà theo

đó những nút trong mỗi phần có cùng nhãn. Sau đó, A. Blum và cộng sự,

2004 [BLR04] làm nhiễu đồ thị bằng một số điểm ngẫu nhiên và tạo ra

20

- 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

21

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

22

- 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

23

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

Cho X là tập các biến kí hiệu là x X. Cho θ là những tham số của một số

mô hình, cho phép xác định phân bố xác suất trên tập X, p_θ(X). Kỳ vọng của các

hàm f(X) theo mô hình là

(2.1)

Trong đó, f(x) là một hàm bất kỳ của biến x cho giá trị vô hướng hoặc

vecto. Hàm này có thể chỉ phụ thuộc vào tập con của tập biến x.

24

- 25 -

Và những kỳ vọng cũng có thể được xác định trên những phép gán giá trị

biến, ví dụ, khi thực hiện huấn luyện xác suất điều kiện của một số mô hình.

Trong trường hợp này, những biến được chia thành biến đầu vào X và biến đầu

ra Y. Một tập các phép gán cho biến đầu vào (những trường hợp dữ liệu huấn

luyện)

= {x1, x2,...} có thể cho trước và kỳ vọng điều kiện là

(2.2)

Một GEC được định nghĩa là một hàm G, sử dụng tham số là kỳ vọng của

mô hình f(X) và trả về một giá trị vô hướng, giá trị này được bổ sung vào như là

một điều kiện trong hàm mục tiêu ước lượng tham số:

(2.3)

Trong một số trường hợp, G có thể được định nghĩa dựa trên khoảng cách

đến giá trị đích cho E_θ[f(X)]. Cho là giá trị đích và cho ∆(·, ·) là hàm khoảng

cách. Trong trường hợp này, G có thể định nghĩa là:

(2.4)

Như đã mô tả ở trên, GEC là một dạng tổng quát, nó coi các phương pháp

ước lượng tham số truyền thống khác là trường hợp đặc biệt. Có thể phân chia

GEC theo mức độ linh hoạt như sau:

1. Một GEC được xác định một cách độc lập theo tham số hóa. Trong các

phương pháp ước lượng tham số truyền thống - phương pháp đồ thị, có

sự tương ứng một-một giữa các tập con của các biến sử dụng trong mỗi

phần tham số hóa của mô hình và tập con của các biến trong đó các kỳ

vọng được xac định cho hàm mục tiêu. Trong GEC, mỗi tập con này có

thể được lựa chọn độc lập.

2. Những GEC điều kiện khác nhau không cần tất cả các điều kiện cho

những trường hợp giống nhau, chúng có thể tác động đến những tập dữ

liệu khác nhau hoặc những sự kết hợp khác nhau của những tập dữ liệu.

3. “Dấu hiệu huấn luyện” có giám sát bất kể ở kỳ vọng đích hay tổng

quát, trạng thái của hàm tỷ số, G, có thể xác định từ dữ liệu huấn luyện

gán nhãn hoặc bất kỳ nguồn nào, bao gồm cả những tác vụ khác hoặc

tri thức tiền nghiệm.

Do đó, một GEC có thể được xác định một cách độc lập với tham số hóa và

độc lập với những lựa chọn của bất kỳ tập dữ liệu điều kiện nào. Và một GEC có

25

- 26 -

thể hoạt động trên một số tập con bất kỳ của các biến trong x. Thêm vào đó, hàm

f có thể được định nghĩa theo kỳ vọng sinh ra mô-men của phân bố p_θ(X) hoặc

bất kỳ kỳ vọng nào khác. Hàm tỷ số G và hàm khoảng cách ∆ có thể dựa trên

nguyên lý thông tin hoặc những hàm bất kỳ.

Những giá trị GEC có thể được sử dụng như là những thành phần duy nhất

của hàm mục tiêu ước lượng tham số hoặc chúng có thể được sử dụng kết hợp

với những giá trị khác. Ví dụ, GEC có thể được áp dụng trong nhiều sơ đồ học

khác nhau trong đó sử dụng những hàm mục tiêu, bao gồm học kết hợp/sinh,

học không giám sát, học điều kiện/phân biệt, học có giám sát, học với những

biến ẩn, học có cấu trúc…

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

quát

Nhìn chung, GEC biểu diễn một tham chiếu trên giá trị của kỳ vọng mô

hình [CMD07]. Một kiểu tham chiếu có thể được biểu diễn bằng hàm khoảng

cách , kỳ vọng mục tiêu , dữ liệu D, hàm f và phân bố mô hình , hàm mục

tiêu GEC là

. Trong [MC10], Gideon S. Mann và Andrew McCallum

, phân kỳ

đặt những hàm là phân bố xác suất điều kiện và đặt

KL là độ đo không đối xứng giữa 2 phân bố xác suất p và q. Đối với huấn luyện

bán giám sát của CRFs, các tác giả bổ sung hàm mục tiêu với điều kiện chuẩn

hóa.

(2.5)

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

(2.6)

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

(2.7)

Trong đó f_m(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:f_m(x,j)=1} và Um là tập các chuỗi mà f_m(x,j) có mặt cho

một số j.

Tính toán Gradient (Độ chênh lệch)

26

- 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= <y_{1..(j-1) (j+1..n)}>. Bước cuối cùng như sau từ định nghĩa của

y

xác suất biên P(y_i|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

27

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

Để hiệu quả,

được lưu ở mỗi giai

đoạn trong giàn.

có thể được tính theo cách

tương tự. Để tính giàn cần thời gian O(ns²) và một giàn phải được tính cho mỗi

nhãn, do đó thời gian là O(ns³).

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.

28

- 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

29

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

30