Download miễn phí Khóa luận Nhận biết các loại thực thể trong văn bản tiếng Việt nhằm hỗ trợ web ngữ nghĩa và tìm kiếm hướng thực thể
Mục lục
Lời Thank .i
Tóm tắt . ii
Mục lục . iii
Bảng từviết tắt . v
Mở đầu .1
Chương 1. Bài toán nhận diện loại thực thể. 3
1.1. Trích chọn thông tin . 3
1.2. Bài toán nhận biết các loại thực thể. 4
1.3. Mô hình hóa bài toán nhận biết các loại thực thể. 5
1.4. Ý nghĩa của bài toán nhận biết các loại thực thể. 6
Chương 2. Các hướng tiếp cận giải quyết bài toán nhận biết các loại thực thể. 8
2.1. Hướng tiếp cận thủcông . 8
2.2. Các mô hình Markov ẩn (HMM) . 9
2.2.1. Tổng quan vềcác mô hình HMM . 9
2.2.2. Giới hạn của các mô hình Markov ẩn . 10
2.3. Mô hình Markov cực đại hóa Entropy (MEMM) . 11
2.3.1. Tổng quan vềmô hình Markov cực đại hóa Entropy (MEMM) . 11
2.3.2. Vấn đề“label bias” . 13
2.4. Tổng kết chương . 14
Chương 3. Conditional Random Field (CRF) . 15
3.1. Định nghĩa CRF . 15
3.2. Nguyên lý cực đại hóa Entropy . 16
3.2.1. Độ đo Entropy điều kiện . 17
3.2.2. Các ràng buộc đối với phân phối mô hình . 17
3.2.3. Nguyên lý cực đại hóa Entropy . 18
3.3. Hàm tiềm năng của các mô hình CRF . 19
3.4. Thuật toán gán nhãn cho dữliệu dạng chuỗi . 20
3.5. CRF có thểgiải quyết được vấn đề‘label bias’ . 22
3.6. Tổng kết chương . 22
Chương 4. Ước lượng tham sốcho các mô hình CRF . 23
4.1. Các phương pháp lặp . 24
4.1.1. Thuật toán GIS . 26
4.1.2. Thuật toán IIS . 27
4.2. Các phương pháp tối ưu số(numerical optimisationmethods) . 28
4.2.1. Kĩthuật tối ưu sốbậc một . 28
4.2.2. Kĩthuật tối ưu sốbậc hai. 29
4.3. Tổng kết chương . 30
Chương 5. Hệthống nhận biết các loại thực thểtrong tiếng Việt . 31
5.1. Môi trường thực nghiệm . 31
5.1.1. Phần cứng . 31
5.1.2. Phần mềm . 31
5.1.3. Dữliệu thực nghiệm . 31
5.2. Hệthống nhận biết loại thực thểcho tiếng Việt . 31
5.3. Các tham sốhuấn luyện và đánh giá thực nghiệm . 32
5.3.1. Các tham sốhuấn luyện . 32
5.3.2. Đánh giá các hệthống nhận biết loại thực thể. 33
5.3.3. Phương pháp “10-fold cross validation” . 34
5.4. Lựa chọn các thuộc tính . 34
5.4.1. Mẫu ngữcảnh vềtừvựng . 35
5.4.2. Mẫu ngữcảnh thểhiện đặc điểm của từ. 35
5.4.3. Mẫu ngữcảnh dạng regular expression . 36
5.4.4. Mẫu ngữcảnh dạng từ điển . 36
5.5. Kết quảthực nghiệm . 37
5.5.1. Kết quảcủa 10 lần thửnghiệm . 37
5.5.2. Lần thực nghiệm cho kết quảtốt nhất . 37
5.5.3. Trung bình 10 lần thực nghiệm . 42
5.5.4. Nhận xét . 42
Kết luận . 43
Phụlục: Output của hệthống nhận diện loại thực thểtiếng Việt . 45
Tài liệu tham khảo . 48
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
về tính độc lập như trong HMM và giữvai trò quan trọng trong việc xác định trạng thái kế tiếp.
Kí hiệu PSi-1(Si|Oi)=P(Si|Si-1,Oi). Áp dụng phương pháp cực đại hóa Entropy
(sẽ được đề cập trong chương 3), McCallum xác định phân phối cho xác suất chuyển
trạng thái có dạng hàm mũ như sau:
⎟⎠
⎞⎜⎝
⎛= ∑
−
−
a
iiaa
ii
iiS SOfSOZ
OSP
i
),(exp
),(
1)|(
1
1
λ (2.4)
Ở đây, aλ là các tham số cần được huấn luyện (ước lượng); Z (Oi, Si) là thừa
số chẩn hóa để tổng xác suất chuyển từ trạng thái Si-1 sang tất cả các trạng thái Si kề
đều bằng 1; fa (Oi, Si) là hàm thuộc tính tại vị trí thứ i trong chuỗi dữ liệu quan sát và
trong chuỗi trạng thái. Mỗi hàm thuộc tính fa (Oi,Si) nhận hai tham số, một là dữ liệu
quan sát hiện tại Oi và một là trạng thái hiện tại Si. McCallum định nghĩa a=, ở
đây b là thuộc tính nhị phân chỉ phụ thuộc vào dữ liệu quan sát hiện tại và Si là trạng
thái hiện tại. Sau đây là một ví dụ về một thuộc tính b:
Hàm thuộc tính fa (Oi, Si) xác định nếu b (Oi) xác định và trạng thái hiện tại
nhận một giá trị cụ thể nào đó:
b(Oi) =
1 nếu dữ liệu quan sát hiện tại là “the”
0 nếu ngược lại
fa (Oi,Si)=
1 nếu b (Oi) =1 và Si=Si-1
0 nếu ngược lại
13
Để gán nhãn cho dữ liệu, MEMM xác định chuỗi trạng thái S làm cực đại
P(S|O) trong công thức (2.3).Việc xác định chuỗi S cũng được thực hiện bằng cách áp
dụng thuật toán Viterbi như trong HMM.
2.3.2. Vấn đề “label bias”
Trong một số trường hợp đặc biệt, các mô hình MEMM và các mô hình định
nghĩa một phân phối xác suất cho mỗi trạng thái có thể gặp phải vấn đề “label bias”
[15][17]. Ta hãy xem xét một kịch bản chuyển trạng thái đơn giản sau:
Hình 4: Vấn đề “label bias”
Giả sử ta cần xác định chuỗi trạng thái khi xuất hiện chuỗi quan sát là “rob”. Ở
đây, chuỗi trạng thái đúng S là ‘0345’ và ta mong đợi xác suất P (0345|rob) sẽ lớn hơn
xác suất P(0125|rob).
Áp dụng công thức (2.3), ta có:
P (0125|rob) =P (0)*P (1|0, r)*P (2|1, o)*P (5|2, b)
Vì tổng các xác suất chuyển từ một trạng thái sang các trạng thái kề với nó
bằng 1 nên mặc dù trạng thái 1 chưa bao giờ thấy quan sát ‘o’ nhưng nó không có cách
nào khác là chuyển sang trang thái 2, điều đó có nghĩa là P (2|1, x) =1 với x có thể là
một quan sát bất kì. Một cách tổng quát, các trạng thái có phân phối chuyển với
entropy thấp (ít đường đi ra) có xu hướng ít chú ý hơn đến quan sát hiện tại.
Lại có P (5|2, b) =1, từ đó suy ra: P (0125|rob) = P(0)*P(1|0,r). Tương tự ta
cũng có P (0345|rob)=P (0)*P (3|0,r). Nếu trong tập huấn luyện, từ ‘rib’ xuất hiện
thường xuyên hơn từ ‘rob’ thì xác suất P(3|0,r) sẽ nhỏ hơn xác suất P(1|0,r), điều đó
dẫn đến xác suất P(0345|rob) nhỏ hơn xác suất P(0125|rob), tức là chuỗi trạng thái
S=0125 sẽ luôn được chọn dù chuỗi quan sát là ‘rib’ hay ‘rob’.
Năm 1991, Léon Bottou đưa ra hai giải pháp cho vấn đề này.Giải pháp thứ
nhất là gộp hai trạng thái 1, 3 và trì hoãn việc rẽ nhánh cho đến khi gặp một quan sát
o_
0
1 2
3 4
5
r_
r_
b: rib
b: rob
i_
14
xác định (cụ thể ở đây là ‘i’ và ‘o’). Đây chính là trường hợp đặc biệt của việc chuyển
một automata đa định sang một automata đơn định. Nhưng vấn đề ở chỗ ngay cả khi
có thể thực hiện việc chuyển đổi này thì cũng gặp phải sự bùng nổ tổ hợp các trạng
thái của automata. Giải pháp thứ hai mà Bottou đưa ra là chúng ta sẽ bắt đầu mô hình
với một đồ thị đầy đủ của các trạng thái và để cho thủ tục huấn luyện tự quyết định
một cấu trúc thích hợp cho mô hình.Tiếc rằng giải pháp này sẽ làm mất tính đi tính có
thứ tự của mô hình, một tính chất rất có ích cho các bài tóan trích chọn thông tin [5].
Một giái pháp đúng đắn hơn cho vấn đề này là xem xét toàn bộ chuỗi trạng
thái như một tổng thể và cho phép một số các bước chuyển trong chuỗi trạng thái này
đóng vai trò quyết định với việc chọn chuỗi trạng thái. Điều này có nghĩa là xác suất
của toàn bộ chuỗi trạng thái sẽ không phải được bảo tồn trong quá trình chuyển trạng
thái mà có thể bị thay đổi tại một bước chuyển tùy thuộc vào quan sát tại đó.Trong ví
dụ trên, xác suất chuyển tại 1 và 3 có thể có nhiều ảnh hưởng đối với việc ta sẽ chọn
chuỗi trạng thái nào hơn xác suất chuyển trạng thái tại 0.
2.4. Tổng kết chương
Chương này giới thiêu các hướng tiếp cận nhằm giải quyết bài toán nhận diện
loại thực thể: hướng tiếp cận thủ công, các hướng tiếp cận học máy (HMM và
MEMM). Trong khi hướng tiếp cận thủ công có giới hạn là tốn kém về công sức, thời
gian và không khả chuyển thì HMM không thể tích hợp các thuộc tính phong phú của
chuỗi dữ liệu quan sát vào quá trình phân lớp, và MEMM gặp phải vấn đề “label bias”.
Những phân tích, đánh giá với từng phương pháp cho thấy nhu cầu về một mô hình
thật sự thích hợp cho việc gán nhãn dữ liệu dạng chuỗi nói chung và bài toán nhận
diện các loại thực thể nói riêng.
15
Chương 3. Conditional Random Field (CRF)
CRF [6][11][12][15][16][17] được giới thiệu lần đầu vào năm 2001 bởi
Lafferty và các đồng nghiệp. Giống như MEMM, CRF 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. Tuy vậy, khác với MEMM, CRF là mô hình đồ thị
vô hướng. Điều này cho phép CRF 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 MEMM. Chính vì cách mô hình hóa như vậy, CRF có thể giải quyết được vấn đề
‘label bias’. Chương này sẽ đưa ra định nghĩa CRF, một số phương pháp ước lượng
tham số cho các mô hình CRF và thuật tóan Viterbi cải tiến để tìm chuỗi trạng thái tốt
nhất mô tả một chuỗi dữ liệu quan sát cho trước.
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 CRF.
3.1. Định nghĩa CRF
Kí hiệu X là biến ngẫu nhiên nhận giá trị là chuỗi dữ liệu cần 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 gía trị trong tập hữu hạn các trạng thái S. Trong bài toán
nhận biết các loại thực thể, X có thể nhận giá trị là các câu trong ngôn ngữ tự nhiên, Y
là một chuỗi ngẫu nhiên các tên thực thể tương ứng với các 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ên thực thể (tên người, tên địa
danh,...).
Cho m...