-
Thông tin
-
Hỏi đáp
Tổng hợp bài giảng môn Xử lý ngôn ngữ tự nhiên| Bài giảng môn Xử lý ngôn ngữ tự nhiên|Trường Đại học Bách Khoa Hà Nội
Tổng hợp bài giảng môn Xử lý ngôn ngữ tự nhiên| Bài giảng môn Xử lý ngôn ngữ tự nhiên|Trường Đại học Bách Khoa Hà Nội. Tài liệu gồm 80 trang giúp bạn tham khảo, ôn tập và đạt kết quả cao trong kỳ thi sắp tới. Mời bạn đọc đón xem.
Đại học Bách Khoa Hà Nội (2.8 K)
Tổng hợp bài giảng môn Xử lý ngôn ngữ tự nhiên| Bài giảng môn Xử lý ngôn ngữ tự nhiên|Trường Đại học Bách Khoa Hà Nội
Tổng hợp bài giảng môn Xử lý ngôn ngữ tự nhiên| Bài giảng môn Xử lý ngôn ngữ tự nhiên|Trường Đại học Bách Khoa Hà Nội. Tài liệu gồm 80 trang giúp bạn tham khảo, ôn tập và đạt kết quả cao trong kỳ thi sắp tới. Mời bạn đọc đón xem.
Preview text:
Tách từ
Tách từ tiếng Việt
z Mục đích: xác định ranh giới của các từ trong câu.
z Là bước xử lý quan trọng đối với các hệ thống XLNNTN,
đặc biệt là đối với các ngôn ngữ đơn lập, ví dụ: âm tiết Lê Thanh Hương
Trung Quốc, âm tiết Nhật, âm tiết Thái, và tiếng Việt.
Bộ môn Hệ thống Thông tin
z Với các ngôn ngữ đơn lập, một từ có ể th có một hoặc
Viện CNTT &TT – Trường ĐHBKHN nhiều âm tiết.
Email: huonglt-fit@mail.hut.edu.vn
¾ Vấn đề của bài toán tách từ là khử được sự nhập nhằng trong ranh giới từ. 1 2 Từ vựng Từ vựng
z tiếng Việt là ngôn ngữ không biến hình Độ dài # %
z Từ điển từ tiếng Việt (Vietlex): >40.000 từ, 1 6,303 15.69 trong đó: 2 28,416 70.72 z 81 55% . â t m itiết l à là t ừ t : từ t đ ơn 3 2 259 , 5 6 . 2 62 4 2,784 6.93
z 15.69% các từ trong từ điển là từ đơn 5 419 1.04
z 70.72% từ ghép có 2 âm tiết Tổng 40,181 100
z 13.59% từ ghép ≥ 3 âm tiết
z 1.04% từ ghép ≥ 4 âm tiết
Bảng 1. Độ dài của từ tính theo âm tiết 3 4
Qui tắc cấu tạo từ tiếng Việt
Qui tắc cấu tạo từ tiếng Việt
z Từ đơn: dùng một âm tiết làm một từ.
z Từ láy: các yếu tố cấu tạo có thành phần ngữ âm được lặp
lại; nhưng vừa lặp vừa biến đổi. Một từ được lặp lại cũng cho z
Ví dụ: tôi, bác, người, cây, hoa, đi, chạy, vì, đã, à, nhỉ, nhé... ta từ láy.
z Từ ghép: tổ hợp (ghép) các âm tiết lại, giữa các âm tiết
đó có quan hệ về nghĩa với nhau.
z Biến thể của từ: được coi là dạng lâm thời biến động hoặc dạng " lời ờ nói" nói của t ừ t . z Từ ghép ẳ đ ng lập. cá à
c th nh tố cấu tạo có quan ệ h ì b nh ẳ đ ớ ng v i nhau về nghĩa. z
Rút gọn một từ dài thành từ ngắn hơn
z ki-lô-gam → ki lô/ kí lô
z Ví dụ: chợ búa, bếp núc z
Lâm thời phá vỡ cấu trúc của từ, phân bố lại yếu tố tạo từ với z
Từ ghép chính phụ. các thành tố cấu tạo này phụ thuộc vào thành
tố cấu tạo kia. Thành tố phụ có vai trò phân loại, chuyên biệt hoá
những yếu tố khác ngoài từ chen vào. Ví dụ:
và sắc thái hoá cho thành tố chính.
z khổ sở → lo khổ lo sở
z Ví dụ: tàu hoả, đường sắt, xấu bụng, tốt mã, ngay đơ, thằng
z ngặt nghẽo → cười ngặt cười nghẽo tắp, sưng vù...
z danh lợi + ham chuộng → ham danh chuộng lợi 5 6
Qui tắc cấu tạo từ tiếng Việt
Các hướng tiếp cận
z Các diễn tả gồm nhiều từ (vd, “bởi vì”) cũng được coi là
z Tiếp cận dựa trên từ điển 1 từ
z Tiếp cận theo phương pháp thống kê
z Tên riêng: tên người và vị trí được coi là 1 đơn vị từ vựng
z Kết hợp hai phương pháp trên. z ẫ
Các m u thường xuyên: số, thời gian 7 8 Các phương pháp
Tiếp cận dựa trên từ điển
z So khớp từ dài nhất (Longest Matching)
z Học dựa trên sự cải biến (Transformation-based cao học, 1999> Learning – TBL) z Xây dựng từ điển
z Chuyển đổi trạng thái trọng số hữu hạn (Weighted Finite
z Mỗi mục từ lưu thông tin về từ, từ loại, nghĩa loại State Transducer – WFST)
z Tổ chức sao cho tốn ít bộ nhớ và thuận tiện trong việc
z Độ hỗn loạn cực đại (Maximum Entropy – ME) tìm kiếm
z Học máy sử dụng mô hình Markov ẩn (Hidden Markov
z Mã hóa từ điển: Từ loại và nghĩa loại kiểu byte được lưu Models- HMM)
dưới dạng một ký tự.
z Học máy sử dụng vectơ hỗ trợ (Support Vector
z VD: danh từ -112 – p, - 115 – s Machines)
z Kết hợp một số phương pháp trên 9 10
Tiếp cận dựa trên từ điển
Tìm từ trong từ điển z
Phân trang theo hai chữ cái đầu của từ, sắp tăng. Với mỗi trang,
các từ lại được sắp theo vần ABC.
z Độ dài tối đa của từ? 3? 4? 5? Paragraph 1 2 n
z Vấn đề: không xử lý được các tổ hợp từ cố ba bà . . . . . . xe
định, vd "ông chẳng bà chuộc“ Content ¾ Đưa ra tất ả c á c c từ ghé ó p c t t rong ừ đ iển bao 1
trùng với phần đầu của xâu vào 2 bà ngoại bài tập n xe cộ xe đạp 11 12
Tìm từ trong từ điển
Phân giải nhập nhằng
Nếu nhà máy nghỉ thì ta về
z Lấy tất cả các cách phân tích, nếu phân tích Vị trí từ: 0 1 2 3 4 5 6 7
cú pháp cho ra cây đúng thì đó là cách phân z Ta có bảng sau: tích đúng. z z z Ký hiệu: z - LT - DT z <động từ> - ĐgT <đại từ> - ĐaT 13 14 Cách tiếp cận lai
Biểu thức chính qui z
là một khuôn mẫu được so sánh với một chuỗi
segmentation of Vietnamese texts, Proceedings of the z Các ký tự đặc biệt:
2nd International Conference on Language and Automat z
* - bất cứ chuỗi ký tự nào, kể cả không có gì z x – ít nhất 1 ký tự
Theory and Applications, LATA 2008, Tarragona, Spain, z
+ - chuỗi trong ngoặc xuất hiện ít nhất 1 lần 2008 > . z Ví d ụ:
z Kết hợp phân tích automat hữu hạn + biểu thức chính z Email: x@x(.x)+
quy + so khớp từ dài nhất + thống kê (để giải quyết nhập z dir *.txt nhằng) z
‘*John’ -> ‘John’, ‘Ajohn’, “Decker John” z
Biểu thức chính quy được sử dụng đặc biệt nhiều trong: * Phân tích cú pháp
* Xác nhận tính hợp lệ của dữ liệu * Xử lý chuỗi
* Tách dữ liệu và tạo báo cáo 15 16
Giới thiệu phi hình thức về Automat hữu hạn automat hữu hạn
z Lớp ngôn ngữ chính qui, được đoán nhận bởi máy ảo,
z Một bài toán trong automat là nhận diện
gọi tên là automat hữu hạn.
chuỗi w có thuộc về ngôn ngữ L hay không. z
Automat hữu hạn đơn định (Deterministic Finite Automat a– DFA z
Automat hữu hạn không đơn định (Nondeterministic Finite
z Chuỗi nhập được xử lý tuần tự từng ký hiệu Auto Au m to at a a – a NFA) mộ m t từ trái sang ph ải. z
Automat hữu hạn không đơn định, chấp nhận phép truyền rỗng (ε-NFA)
z Trong quá trình thực thi, automat cần phải
nhớ thông tin đã qua xử lý. 17 18
Automat hữu hạn cho các từ
Ví dụ về automat hữu hạn tiếng Anh
L = {w ∈ {0, 1}* | w kết thúc bằng chuỗi con 10}. 19 20
Cách tách từ đơn giản
Lựa chọn cách tách từ z
Biểu diễn đoạn bằng chuỗi các âm tiết s
z Phát hiện các mẫu thông thường như tên riêng, chữ viết 1 s2 … sn
tắt, số, ngày tháng, địa chỉ email, URL,… sử dụng biểu z
Trường hợp nhập nhằng thường xuyên nhất là 3 từ liền nhau s1s2s3 trong đó s thức chính qui 1s2 và s2s3 đều là từ. z Hệ th ệ ống ch g ọn c ọ
huỗi âm tiết dài nhất từ vị trí hiện t ệ ại và ạ
có trong từ điển, chọn cách tách có ít từ nhất
¾ Hạn chế: có thể đưa ra cách phân tích không đúng. z
BIểu diễn 1 đoạn bằng đồ thị có hướng tuyến tính G = (V,E), V = {v
¾ Giải quyết: liệt kê tất, có 1 chiến lược để chọn cách tách 0, v tốt nhất.
1, . . . , vn, vn+1} z
Nếu các âm tiết si+1, si+2, . . . , sj tạo thành 1 từ -> trong G có cạnh (vi,vj) z
Các cách tách từ = các đường đi ngắn nhất từ v0 đến vn+1 21 22 Thuật toán
Phân giải nhập nhằng
Thuật toán 1. Xây dựng đồ thị cho chuỗi s1s2 . . . sn 1: V ← ; z Xác suất xâu s:
2: for i = 0 to n + 1 do
3: V ← V {vi}; 4: end for 5: for i = 0 to n do
6: for j = i to n do
7: if (accept(AW, si · · · sj)) then z P(w i-1): xác suất w
8: E ← E {(v i|w1
i khi có i-1 âm tiết trước i, vj+1)}; 9: end if đó 10: end for
z n = 2: bigram; n = 3: trigram 11: end for
12: return G = (V,E); 23
accept(A, s): automat A nhận xâu vào s 24
Phân giải nhập nhằng Kỹ thuật làm trơn
z Khi n = 2, tính giá trị P(wi|wi-1) lớn nhất maximum likelihood (ML)
với λ1 + λ2 = 1 và λ1, λ2 ≥ 0 PML(wi) = c(wi)/N
z Với tập thử nghiệm T = {s1,s2,…,sn}, xác suất P(T) của tập thử th :
z c(s): số lần xâu s xuất hiện; N: tổng số từ trong tập luyện z Entropy của văn bản:
z Khi dữ liệu luyện nhỏ hơn kích cỡ toàn bộ tập dữ liệu Æ P ~ 0 với NT: số từ trong T
z Sử dụng kỹ thuật làm trơn
z Entropy tỉ lệ nghịch với xác suất trung bình của 1 cách tách
từ cho các câu trong văn bản thử nghiệm. 25 26
Xác định giá trị λ1, λ2 Thuật toán
z Từ tập dữ liệu mẫu, định nghĩa C(wi-1,wi) là số lần (wi-1, w λ
i) xuất hiện trong tập mẫu. Ta cần chọn λ1 2 để làm cực đại giá trị
với λ1 + λ2 = 1 và λ1, λ2 ≥ 0 28 Kết quả z
Sử dụng tập dữ liệu gồm 1264 bài trong báo Tuổi trẻ, có 507,358 từ z
Lấy ε = 0.03, các giá trị λ hội tụ sau 4 vòng lặp z
Độ chính xác = số từ hệ thống xác định đúng/tổng số từ hệ thống xác định = 95% 29 Định nghĩa Gán nhãn từ loại
z Gán nhãn từ loại (Part of Speech tagging - POS
tagging): mỗi từ trong câu được gán nhãn thẻ từ loại tương ứng của nó
z Vào : 1 đoạn văn bản đã tách từ + tập nhãn Lê T hanh H ương z Ra: c ác cá h ch gán nhãn chính chính xác xác nhấ nh t ấ
Bộ môn Hệ thống Thông tin
Viện CNTT &TT – Trường ĐHBKHN Ví dụ 1 Ví dụ 2
Email: huonglt-fit@mail.hut.edu.vn Ví dụ 3 Ví dụ 4 Ví dụ 5
¾ Gán nhãn làm cho việc phân tích văn bản dễ dàng hơn 1 2
Tại sao cần gán nhãn?
Tập từ loại tiếng Anh
z Dễ thực hiện: có thể thực hiện bằng nhiều phương pháp khác nhau z
Lớp đóng (các từ chức năng): số lượng cố định z
Giới từ (Prepositions): on, under, over,…
z Các phương pháp sử dụng ngữ cảnh có thể đem lại kết quả tốt z
Tiểu từ (Particles): abroad, about, around, before, in, instead, since, without,… z Mặ M d c ù dù ê n n th thực hiệ hi n bằ b hâ ng p n tích ă v n bả b n z
Mạo từ (Articles): a, an, the z Các ứng dụng: z
Liên từ (Conjunctions): and, or, but, that,…
z Text-to-speech: record - N: [‘reko:d], V: [ri’ko:d]; lead – z
Đại từ (Pronouns): you, me, I, your, what, who,… N [led], V: [li:d] z
Trợ động từ (Auxiliary verbs): can, will, may, should,…
z Tiền xử lý cho PTCP. PTCP thực hiện việc gán nhãn tốt hơn nhưng đắt hơn z
Lớp mở: có thể có thêm từ mới
z Nhận dạng tiếng nói, PTCP, tìm kiếm, v.v… 3
z Dễ đánh giá (có bao nhiêu thẻ được gán nhãn đúng?) 4
Lớp từ mở trong tiếng Anh
Tập nhãn cho tiếng Anh Proper nouns: IBM, Colorado nouns count nouns: book, ticket common nouns mass nouns: snow, salt auxiliaries z
tập ngữ liệu Brown: 87 nhãn verbs . . . z
3 tập thường được sử dụng: open class Color: red, white p ¾ Nhỏ: 4 5 45 n hãn nhãn - Penn P t r t eebank ( slide (slide s au) sau) adjectives Age: old, young ¾
Trung bình: 61 nhãn, British national corpus Value: good, bad ¾ Lớn: 146 nhãn, C7
Locatives adverbs: home, here, downhill
Degree adverbs: extremely, very, somewhat adverbs
Manner adverbs: slowly, delicately
Temporal adverbs: yesterday, Monday 5 6
Penn Treebank – ví dụ
z The grand jury commented on a number of other topics.
Ö The/DT grand/JJ jury/NN commented/VBD
on/IN a/DT number/NN of/IN other/JJ topics/NNS ./. I know that blocks the sun.
He always books the violin concert tickets early.
He says that book is interesting. 7 8
Khó khăn trong gán nhãn từ
Các phương pháp gán nhãn từ loại? loại
z Dựa trên xác suất: dựa trên xác suất lớn
nhất, dựa trên mô hình Markov ẩn (hidden
… là xử lý nhập nhằng markov model – HMM) Pr (Det N) - > Pr Pr (Det (Det Det) - z Dựa trên luật If Then … 9 10 Các cách tiếp cận
Gán nhãn dựa trên xác suất
z Sử dụng HMM : “Sử dụng tất cả thông tin đã
Cho câu hoặc 1 xâu các từ, gán nhãn từ loại có và đoán”
thường xảy ra nhất cho các từ trong xâu đó. Cách thực hiện: z Dựa trên ràng bu g ộc ngữ g phá p p: p “không
đoán, chỉ loại trừ những khả năng sai” z Hidden Markov model (HMM):
Chọn thẻ từ loại làm tối đa xác suất:
z Dựa trên chuyển đổi: “Đoán trước, sau đó
P(từ|từ loại)•P(từ loại| n từ loại phía trước) có thể thay đổi”
The/DT grand/JJ jury/NN commented/VBD on/IN a/DT
number/NN of/IN other/JJ topics/NNS ./. ⇒ 11 P(jury|NN) = 1/2 12 Ví dụ -HMMs Gán nhãn HMM
z Công thức Bigram HMM: chọn ti cho wi có nhiều
khả năng nhất khi biết ti-1 và wi :
ti = argmaxj P(tj | ti-1 , wi) (1) z Giả Gi thi ế thi t đơ n đơ g iả gi n hóa HMM: v ấ v n đề gán nhãn
có thể giải quyết bằng cách dựa trên các từ và
thẻ từ loại bên cạnh nó
ti = argmaxj P(tj | tj-1 )P(wi | tj ) (2)
Thực hiện học có giám sát, sau đó suy diễn để xác định thẻ từ loại xs chuỗi thẻ
xs từ thường xuất hiện với thẻ tj
(các thẻ đồng xuất hiện) 13 14 Ví dụ
Giả sử chúng ta có tất cả các từ loại trừ từ race
I/PP know/VBP that/WDT block/NN blocks/NNS?VBZ? the/DT 1.
Secretariat/NNP is/VBZ expected/VBN to/TO race/VB sun/NN.
z Chỉ nhìn vào từ đứng trước(bigram): tomorrow/NN to/TO race/??? NN or VB? 2.
People/NNS continue/VBP to/TO inquire/VB the/DT
reason/NN for/IN the/DT race/NN for/IN outer/JJ the/DT race/??? space/NN z Áp dụng (2): t
z Không thể đánh giá bằng cách chỉ đếm từ trong tập ngữ
i = argmaxj P(tj | tj-1 )P(wi | tj ) liệu (và chuẩn hóa)
z Chọn thẻ có xác suất lớn hơn giữa 2 xác suất:
z Muốn 1 động từ theo sau TO nhiều hơn 1 danh từ (to
race, to walk). Nhưng 1 danh từ cũng có thể theo sau
P(VB|TO)P(race|VB) hoặc P(NN|TO)P(race|NN) TO (run to school)
xác suất của 1 từ là race khi biết từ loại là VB. 15 16 Tính xác suất Bài tập
Xét P(VB|TO) và P(NN|TO) z I know that blocks the sun.
z Từ tập ngữ liệu Brown
z He always books the violin concert tickets early. P(NN|TO)= .021
z He says that book is interesting. P(VB|TO)= .340
z I/PP know/VBP that/WDT blocks/VBZ the/DT sun/NN. P(race|NN)= 0.00041
z He/PP always/RB books/VBZ the/DT violin/NN P(race|VB)= 0.00003
concert/NN tickets/NNS early/RB. z
P(VB|TO)P(race|VB) = 0.00001
z He/PP says/VBZ that/WDT book/NN is/VBZ interesting/JJ. z
P(NN|TO)P (race|NN) = 0.000007
z I know that block blocks the sun.
¾ race cần phải là động từ nếu đi sau “TO”
z I/PP know/VBP that/DT block/NN blocks/NNS?VBZ? the/DT sun/NN. 17 18 Mô hình đầy đủ
Mở rộng sử dụng luật chuỗi
z Chúng ta cần tìm chuỗi thẻ tốt nhất cho toàn xâu
z Cho xâu từ W, cần tính chuỗi từ loại có xác suất lớn
P(A,B) = P(A|B)P(B) = P(B|A)P(A) nhất T=t
P(A,B,C) = P(B,C|A)P(A) = P(C|A,B)P(B|A)P(A)
1, t2 ,…, tn hoặc, = P(A)P(B|A)P(C|A,B)
P(A,B,C,D…) = P(A)P(B|A)P(C|A,B)P(D|A,B,C..) ˆ
T = arg max P(T | W ) T τ ∈ (nguyên lý Bayes) n
P(T )P(W | T ) = ∏ P(w | w t ...w t t )P(t |w t ...w t ) i 1 1 i 1 − i 1 − i i 1 1 i 1 − i 1 − i 1 = pr từ lịch sử nhãn 19 20 Giả thiết trigram Thay vào công thức
z Xác suất 1 từ chỉ phụ thuộc vào nhãn của nó P(T)P(W|T) =
P(w | w t ...t ...
t ) = P(w | t ) n n i 1 1 i 1 − i i i
P(t )P(t | t )∏ P(t | t t )[∏ P(w | t )] 1 2 1 i i−2 i 1 − i i
z Ta lấy lịch sử nhãn thông qua 2 nhãn gần i=3 i 1 =
nhất (trigram: 2 nhãn gần nhất + nhãn hiện tại)
P(t | w t ...t ) = P(t | t t ) i 1 1 i 1 − i i−2 i 1 − 21 22 Đánh giá xác suất Bài toán
z Sử dụng quan hệ xác suất từ tập ngữ liệu để đánh giá xác suất: Cần giải quyết c(t ( t t ) ˆ i− ) 2 i 1 T = P(t ( | t t ) i i−1 i ) = T arg max m P(T ( )P(W ( | T ) i i 1 − i−2 c(t t ) T τ ∈ i−2 i 1 − c(w ,t ) P(w | t ) i i =
Bây giờ ta có thể tính được tất cả các tích i i c(t ) P(T)P(W|T) i 23 24 Ví dụ Tìm đường n đi có điểm cao n
P(t )P(t | t )∏ P(t | t t )[∏ P(w | t )] NNS NNS − − nh1ất 2 1 i i 2 i 1 i i i=3 i 1 = NNS DT NNS NNS 30 75 1 NNS VB VBP DT 30 60 the dog saw ice-cream 1 1 52 VB
Tìm đường đi tốt nhất? VBP the dog saw ice-cream 25 26
Cách tìm đường đi có điểm cao nhất Độ chính xác z
Sử dụng tìm kiếm kiểu best-first (A*) z > 96% 1.
Tại mỗi bước, chọn k giá trị tốt nhất ( ) . Mỗi giá
trị trong k giá trị này ứng với 1 khả năng kết hợp
z Cách đơn giản nhất? 90%
nhãn của tất cả các từ
z Gán mỗi từ với từ loại thường xuyên nhất của nó 2. Khi gán từ ế ti p theo, tính lại xá ấ c su t. Quay lại bước 1
z Gán từ chưa biết = danh từ z
Ưu: nhanh (không cần kiểm tra tất cả các khả năng
z Người: 97%+/- 3%; nếu có thảo luận: 100%
kết hợp, chỉ k cái tiềm năng nhất) z
Nhược: có thể không trả về kết quả tốt nhất mà chỉ chấp nhận được 27 28
Cách tiếp cận thứ 2: gán nhãn
Transformation-based painting
dựa trên chuyển đổi
Transformation-based Learning (TBL): z
Kết hợp cách tiếp cận dựa trên luật và cách tiếp ậ c á n x c suất ử : s d ụ h
ng ọc máy để chỉnh l ại t h thẻ thông qua vài lần duyệt z
Gán nhãn sử dụng tập luật tổng quát nhất, sau đó
đến tập luật hẹp hơn, thay đổi một số nhãn, và tiếp tục 29 30
Transformation-based painting
Transformation-based painting 31 32
Transformation-based painting
Transformation-based painting 33 34
Transformation-based painting
Transformation-based painting 35 36 Ví dụ với TBL Ví dụ với TBL 1.
Gán mọi từ với nhãn thường xuất hiện nhất
(thường độ chính xác khoảng 90% ). Từ tập ngữ liệu Brown: P(NN|race | )= 0.98 P(VB|race)= 0.02 2. …expected/VBZ to/ TO race/NN race/VB tomorrow/NN
…the/DT race/NN for/IN outer/JJ space/NN 3.
Sử dụng luật chuyển đổi:
Thay NN bằng VB khi thẻ trước đó là TO
pos: ‘NN’>’VB’ ← pos: ‘TO’ @[-1] o 37 38
Luật gán nhãn từ loại
Luật gán nhãn từ loại 39 40
Học luật TB trong hệ thống TBL Các tập ngữ liệu z Tập huấn luyện
w0 w1 w2 w3 w4 w5 w6 w7 w8 w9 w10 z Tậ T p n g ngữ liệ li u h iệ hi n t ại (CC (CC 1) 1)
dt vb nn dt vb kn dt vb ab dt vb
z Tập ngữ liệu tham khảo
dt nn vb dt nn kn dt jj kn dt nn 41 42
Khuôn dạng cho luật gán nhãn
Học luật TB trong hệ thống từ loại TBL
z Trong TBL, chỉ các luật thỏa khuôn dạng mới được học. z Ví dụ: các luật tag: t ' ag: VB V '>' B NN' ← tag: t 'DT'@[- @[ 1].
tag:’NN’>’VB' ← tag:'DT'@[-1]. thỏa khuôn dạng tag:A>B ← tag:C@[-1].
z Có thể tạo khuôn dạng sử dụng các biến vô danh tag:_>_ ← tag:_@[-1]. 43 44
Sinh và tính điểm cho luật ứng
Điểm, độ chính xác, ngưỡng viên 1 z Điểm của 1 luật:
z Template = tag:_>_ ← tag:_@[-1] score(R) = |pos(R)| - |neg(R)|
z R1 = tag:vb>nn ← tag:dt@[-1] z Độ chính xác:
z Threshold: ngưỡng mà độ chính xác của 1 luật cần z pos(R1) = 3
vượt qua để có thể được lựa chọn. z neg(R1) = 1
z Trong TBL, ngưỡng của độ chính xác thường < 0.5.
z score(R1) = pos(R1) - neg(R1) = 3-1 = 2 45 46
Sinh và tính điểm cho luật ứng viên 2
Học luật TB trong hệ thống TBL
z Template = tag:_>_ ← tag:_@[-1]
z R2 = tag:nn>vb ← tag:vb@[-1] z pos(R2) = 1 z neg(R2) = 0
z score(R2) = pos(R2) - neg(R2) = 1-0 = 1 47 48
Tối ưu hóa việc chọn luật tốt
Chọn luật tốt nhất nhất
z Thứ hạng hiện tại của luật ứng viên
z Giảm dư thừa luật:chỉ sinh các luật ứng viên
R1 = tag:vb>nn ← tag:dt@[-1] Score = 2
phù hợp ít nhất với 1 dữ liệu trong tập luyện.
R2 = tag:nn>vb ← tag:vb@[-1] Score = 1 … z Đánh Đ g iá giá tă t ng cường ườ : ng
z Nếu score threshold =< 2 thì chọn R1
z Lưu vết của các luật ứng viên tốt nhất
z ngược lại nếu score threshold > 2, dừng
z Bỏ qua các luật phù hợp với số lượng mẫu <
score của luật tốt nhất 49 50
Tìm kiếm tham lam kiểu Best- First Ưu điểm của TBL Hàm giá
z Luật có thể được tạo thủ công
h(n) = giá ước lượng của đường đi rẻ nhất từ trạng z Luật dễ hiểu và logic thái t c ủa nút n đế n t r trạng t hái t đ ích z Dễ cài đặt
z Có thể chạy rất nhanh (nhưng cài đặt thì phức tạp) 51 52
Phân tích lỗi: khó khăn đối với
Cách tốt nhất phát hiện các từ
bộ gán nhãn từ loại chưa biết
Các lỗi thông thường (> 4%)
z Dựa trên 3 dạng đuôi biến tố (-ed, -s, -ing);
32 đuôi phái sinh (-ion, etc.); chữ hoa; gạch
z NN (common noun) vs .NNP (proper noun) vs. JJ (adjective): khó phân bi p ệt, sự phân bi p ệt này là y quan q nối
trọng đặc biệt trong trích rút thông tin
z RP(particle) vs. RB(adverb) vs. IN(preposition):tất cả z Tổng quát hơn:
các loại này có thể xuất hiện tuần tự sau động từ z Phân tích hình thái từ
z VBD vs. VBN vs. JJ: phân biệt thời quá khứ, phân từ
z Các cách tiếp cận học máy
2, tính từ (raced vs. was raced vs. the out raced horse) 53 54
Gán nhãn từ loại tiếng Việt
Các bước thực hiện Câu tiếng
Qua những lần từ Sài_Gòn về Quảng_Ngãi kiểm_tra
Việt đã tách công_việc , Sophie và Jane thường trò_chuyện với z Tách từ từ
Mai , cảm_nhận ngọn_lửa_sống và niềm_tin z
Gán nhãn tiên nghiệm (gán mỗi từ với tất cả các nhãn từ loại mà
mãnh_liệt từ người phụ_nữ VN này . nó có thể có). Câu tiếng
Qua những lần từ Sài_Gòn về Quảng_Ngãi kiểm_tra z
Với một từ mới, dùng một nhãn ngầm định hoặc gắn cho nó tập Việt ệ đ ã đ công vi _ ệc ệ S , ophie và Jane th ườ th ng t rò tr c _ huyệ huy n ệ vớ v i
tất cả các nhãn. Với ngôn n g gữ
g biến đổi hình thái Æ dựa vào hình thái từ được gán
Mai , cảm_nhận ngọn_lửa_sống và niềm_tin
nhãn từ loại mãnh_liệt từ người phụ_nữ VN này .
z Quyết định kết quả gán nhãn (loại bỏ nhập nhằng) z
dựa vào quy tắc ngữ pháp Chú thích z dựa vào xác suất từ loại z sử dụng mạng nơ-ron z
các hệ thống lai sử dụng kết hợp tính toán xác suất và ràng buộc ngữ pháp z gán nhãn nhiều tầng 55 56
Khó khăn trong gán nhãn từ
Dữ liệu phục vụ gán nhãn loại tiếng Việt z Ngữ liệu:
z đặc trưng riêng về ngôn ngữ z Từ điển từ vựng
z thiếu các kho dữ liệu chuẩn như Brown hay
z Kho văn bản đã gán nhãn, có thể kèm theo các quy Penn Treebank tắ t c ắ ngữ g ữ ph p áp á x p ây â y dự d n ự g g bằ b n ằ g g tay tay ¾ khó k h khă t n đ rong ánh giá iá kết quả
z Kho văn bản chưa gán nhãn, có kèm theo các thông
tin ngôn ngữ như là tập từ loại
z Kho văn bản chưa gán nhãn, với tập từ loại được xây
dựng tự động nhờ các tính toán thống kê 57 58 Cách tiếp cận 1 [Đinh Điền]
[Đinh Điền] Dien Dinh and Kiem Hoang, POS-tagger for English-
z Xây dựng một tập ngữ liệu song ngữ Anh – Việt ~ 5 triệu
Vietnamese bilingual corpus. HLTNAACL Workshop on Building and từ (cả Anh lẫn Việt).
using parallel texts: data driven machine translation and beyond, 2003.
z gán nhãn từ loại cho tiếng Anh dựa trên Transformation-
based Learning – TBL [Brill 1995]
z chuyển đổi và ánh xạ từ thông tin từ loại từ tiếng
z gióng hàng giữa hai ngôn ngữ (độ chính xác khoảng Anh do
87%) để chuyển nhãn từ loại sang tiếng Việt.
z gán nhãn từ loại trong tiếng Anh đã đạt độ chính xác
z kết quả được hiệu chỉnh bằng tay để làm dữ liệu huấn cao ( >97%)
luyện cho bộ gán nhãn từ loại tiếng Việt.
z những thành công gần đây của các phương pháp
gióng hàng từ (word alignment methods) giữa các cặp ngôn ngữ. 59 60 [Đinh Điền] Cách tiếp cận 2 z Ưu điểm: z
[Nguyen Huyen, Vu Luong] Thi Minh Huyen Nguyen, Laurent
Romary, and Xuan Luong Vu, A Case Study in POS Tagging of
z tránh được việc gán nhãn từ loại bằng tay nhờ tận
Vietnamese Texts. The 10th annual conference TALN 2003.
dụng thông tin từ loại ở một ngôn ngữ khác.
z dựa trên nền tảng và tính chất ngôn ngữ của tiếng Việt. z Nhược: z xây xâ dự d ng ự tậ t p ậ từ t loạ lo i ạ (tags (tagset) cho cho tiế ti ng ế Việ Vi t ệ dự d a ự trên trên
z Tiếng Anh và tiếng Việt khác nhau: về cấu tạo từ, trật
chuẩn mô tả khá tổng quát của các ngôn ngữ Tây Âu,
tự và chức năng ngữ pháp của từ trong câu Æ khó
nhằm mô đun hóa tập nhãn ở hai mức: khăn trong gióng hàng z
mức cơ bản/cốt lõi (kernel layer): đặc tả chung nhất cho các
z Lỗi tích lũy qua hai giai đoạn: (a) gán nhãn từ loại cho ngôn ngữ
tiếng Anh và (b) gióng hàng giữa hai ngôn ngữ z
mức tính chất riêng (private layer): mở rộng và chi tiết hóa cho
một ngôn ngữ cụ thể dựa trên tính chất của ngôn ngữ đó
z Tập nhãn được chuyển đổi trực tiếp từ tiếng Anh
sang tiếng Việt không điển hình cho từ loại tiếng Việt 61 62
[Nguyen Huyen, Vu Luong] Cách tiếp cận 3
z mức cơ bản: danh từ (noun – N), động từ (verb – V),
z [Phuong] Nguyễn Thị Minh Huyền, Vũ Xuân Lương, Lê
tính từ (adjective – A), đại từ (pronoun – P), mạo từ
Hồng Phương . Sử dụng bộ gán nhãn từ loại xác suất
(determine – D), trạng từ (adverb – R), tiền-hậu giới
QTAG cho văn bản tiếng Việt. Kỷ yếu Hội thảo
từ (adposition – S), liên từ (conjunction – C), số từ ICT.rda’03 (numeral – M), tình thái thái từ t (interjec e tio t n – I), và từ t z làm việc trên mộ ử t c ổ a s chứa 3 từ, sau
ngoại Việt (residual – X, như foreign words, ...).
khi đã bổ sung thêm 2 từ giả ở đầu và
z mức tính chất riêng: được triển khai tùy theo các dạng
từ loại trên như danh từ đếm được/không đếm được cuối văn bản.
đối với danh từ, giống đực/cái đối với đại từ, .v.v.
z Nhãn được gán cho mỗi từ đã lọt ra ngoài
cửa sổ là nhãn kết quả cuối cùng. 63 64
Thủ tục gán nhãn từ loại [Phương] [Phương]
1. Đọc từ (token) tiếp theo
z Chia kho văn bản đã gán nhãn làm 2 tập: tập huấn luyện
2. Tìm từ đó trong từ điển và tập thử nghiệm
3. Nếu không tìm thấy, gán cho từ đó tất cả các nhãn có thể
z Tự động gán nhãn cho các phần văn bản
4. Với mỗi nhãn có thể
z So sánh kết quả thu được với dữ liệu mẫu. a. tính Pw = P(tag|token)
z Thời gian huấn luyện với 32000 từ: ~ 30s
b. tính Pc = P(tag|t1,t2), t1, t2, là nhãn tương ứng của hai từ đứng trước từ token.
c. tính Pw,c = Pw * Pc, kết hợp hai xác suất trên.
5. Lặp lại phép tính cho hai nhãn khác trong cửa sổ
Sau mỗi lần tính lại (3 lần cho mỗi từ), các xác suất kết quả
được kết hợp để cho ra xác suất toàn thể của nhãn được gán cho từ. 65 66 [Phương] [Phương] z Câu đã gán nhãn: z
Câu từ tập ngữ liệu mẫu
hồi lên < w pos="Nn"> sáu
hồi lên < w pos="Nn"> sáu
, có lần
, có lần tôi đã tôi đã
nhìn thấy một nhìn thấy một pos "N = t" "N b > ức / < w> = N "Nc" t > ranh / < w> = Jd" "Jd t > ệ uy t ệ pos "N = t" "N b > ức / < w> = N "Nc" t > ranh / < w> = Jd" "Jd t > ệ uy t ệ đẹp đẹp
Câu do chương trình gán nhãn
Nc - danh từ đơn thể, Vto - ngoại động từ chỉ hướng, Nn - danh từ số
hồi lên < w pos="Nn">
lượng, Vs - động từ tồn tại, Nu - danh từ đơn vị, Pp - đại từ nhân
sáu , có
xưng, Jt - phụ từ thời gian, Vt - ngoại động từ, Nt - danh từ loại thể,
lần tôi đã Jd - phụ từ chỉ mức độ, Aa - tính từ hàm chất.
pos="Vt"> nhìn thấy một
bức tranh pos="Jd"> tuyệt đẹp 67 68 [Phương] Cách tiếp cận 4 z Kết quả: z Phan Xuân Hiếu:
z dựa trên phương pháp Maximum Entropy (MaxEnt) và
z ~94% (9 nhãn từ vựng và 10 nhãn cho các loại kí
Conditional Random Fields (CRFs) - ứng dụng rất nhiều hiệu)
cho các bài toán gán nhãn cho các thành phần trong dữ z ~85% (48 nhãn t ừ t v ựng và 10 nhãn cho c ác các lo ại liệ li u ệ chu ch ỗ u i ỗ . kí hiệu)
z Nếu không dùng đến từ điển từ vựng (chỉ sử
z Dữ liệu huấn luyện: là tập ngữ liệu Viet Treebank bao
dụng kho văn bản đã gán nhãn mẫu) thì các
gồm hơn 10.000 câu tiếng Việt được gán nhãn từ loại
bởi các chuyên gia ngôn ngữ.
kết quả chỉ đạt được tương ứng là ~80% và ~60%. 69 70 [Hiếu]
Trích chọn đặc trưng
z ... thường trò_chuyện với Mai ...
z Cần xác định từ loại cho từ “trò_chuyện”, các đặc trưng: z
Chính bản thân từ “trò_chuyện” thường xuất hiện với từ loại nào
trong tập dữ liệu Viet Treebank? z Từ “ trò tr c _ huyệ huy n ệ ” n thườ th ng c ó có nhãn từ lo ạ lo i ạ là là g ì gì t ro tr n o g n t ừ đ i đ ển? ể Là động từ chăng? z
Từ thường đi ngay trước từ “trò_chuyện” thường có gợi ý gì? z
Từ với đi sau từ “trò_chuyện” có gợi ý gì? Có phải nó gợi ý là
ngay trước nó là một động từ hay không? z
Kết hợp của hai từ “với Mai” gợi ý điều gì, chắc từ trước đó
(“trò_chuyện”) nên là một động từ?
Học mô hình gán nhãn từ loại 71 72
Ngữ cảnh cho trích xuất đặc
Ngữ cảnh cho trích xuất đặc trưng trưng 73 74
Kết quả gán nhãn sử dụng MaxEnt và CRFs
Tập từ loại tiếng Việt idPOS symbolPOS vnPOS enPOS 1 N danh từ noun 2 V động từ verb 3 A tính từ adjective 4 M số từ numeral 5 P đại từ pronoun 6 R phụ ph từ adver adv b 7 O giới từ preposition 8 C liên từ conjunction 9 I trợ từ auxiliary word 10 E cảm từ emotivity word 11 Xy* từ tắt abbreviation 12 S
yếu tố từ (bất, vô…) component stem 13 U không xác định undetermined
•Từ tắt mang nhãn kép: X = từ loại của từ tắt ; 75 76
•y = kí hiệu từ tắt. Ví dụ: GDP-Ny ; HIV – Ny.
Tập tiểu từ loại tiếng Việt
Tập tiểu từ loại tiếng Việt idPOS idSub symbol vnPOS enPOS POS POS idPOS idSub symbol vnPOS enPOS 1 1 Np danh từ riêng proper noun POS POS 1 2 Nc danh từ đơn thể countable noun 4 17 Mc số từ số lượng cardinal numeral 1 3 Ng danh từ tổng thể collective Noun 4 18 Mo số từ thứ tự ordinal numeral 1 4 Na
danh từ trừu tượng abstract noun 5 19 Pp đại từ xưng hô personal pronoun 1 5 Ns danh từ chỉ loại classifier noun 5 20 Pd đại từ chỉ định demonstrative pronoun 1 6 Nu danh t ừ đơ n v ị v unit noun 5 21 Pq đại đạ t ừ s ố l ượng quality qualit pronoun pronoun 1 7 Nq danh từ chỉ lượng quantity noun 5 22 Pi đại từ nghi vấn interrogative pronoun 2 8 Vi động từ nội động intransitive verb 6 23 R phụ từ adverb 2 9 Vt
động từ ngoại động transitive verb 7 24 O giới từ preposition 2 10 Vs động từ trạng thái state verb 8 25 C liên từ conjunction 2 11 Vm động từ tình thái modal verb 9 26 I trợ từ auxiliary word 2 12 Vr động từ quan hệ relative verb 10 27 E cảm từ emotivity word 3 13 Ap tính từ tính chất property adjective 11 28 Xy từ tắt abbreviation 3 14 Ar tính từ quan hệ relative adjective 12 29 S
yếu tố từ (bất, vô…) component stem 3 15 Ao
tính từ tượng thanh onomatopoetic adjective 13 30 U không xác định undetermined 77 3 16 Ai tính từ tượng hình pictographic adjective 78 Bài toán PTCP Phân tích cú pháp cây PTCP mẫu P T tính độ chính xác Lê Thanh Hương C điể i m câu
Bộ môn Hệ thống Thông tin P Các bộ PTCP
Viện CNTT &TT – Trường ĐHBKHN cây cú pháp hiện nay có độ
Email: huonglt-fit@mail.hut.edu.vn Văn phạm chính xác cao (Eisner, Collins, Charniak, etc.) 1 2
Khái niệm về văn phạm Văn phạm
z Phân tích câu “Bò vàng gặm cỏ non”
z Một văn phạm sản sinh là một hệ thống z Cây cú pháp:
z G = ( T, N, S, R ), trong đó z Tập luật
z T (terminal) – tập ký hiệu kết thúc z C Æ CN VN
z N (non terminal) – tập ký hiệu không kết thúc z CN Æ DN
z S (start) – ký hiệu khởi đầu z VN Æ ĐgN z R (rule) – tập luật z ĐgN Æ ĐgT DN
z R = { α Æ β | α, β ∈ (T∪N) } z DN Æ DT TT
z α Æ β gọi là luật sản xuất 3 4 Dạng chuẩn Chomsky
Nhắc lại về văn phạm
z Văn phạm: 1 tập luật viết lại
z Mọi NNPNC không chứa ε đều có thể sinh từ
z Ký hiệu kết thúc: các ký hiệu không thể phân rã được
một văn phạm tnđó mọi sản xuất đều có nữa.
dạng A Æ BC hoặc A Æ a, với A,B,C∈N và a
z Ký hiệu không kết thúc: các ký hiệu có thể phân rã được. ∈T z Xét Xé ă v h n p ạm G:
z Ví dụ: Tìm dạng chuẩn Chomsky cho văn S → NP VP
phạm G với T = {a,b}, N ={S,A,B}, R như sau: NP → John, garbage VP → laughed, walks z S Æ bA|aB
G có thể sinh ra các câu sau: z A ÆbAA|aS|a
John laughed. John walks. z B Æ aBB|bS|b
Garbage laughed. Garbage walks. 5 6 Cấu trúc ngữ pháp
Các ứng dụng của PTCP
Cây cú pháp biểu diễn cấu trúc ngữ pháp của một câu. Bò vàng gặm cỏ non.
Dịch máy (Alshawi 1996, Wu 1997, ...) C các thao tác CN với cây VN tiếng Anh tiếng Việt DN ĐgN DT TT ĐgT DN Bò vàng gặm
Nhận dạng tiếng nói sử dụng PTCP (Chelba et al 1998) DT TT Put the file in the folder. cỏ non Put the file and the folder. 7 8
Văn phạm phi ngữ cảnh
Các ứng dụng của PTCP (Context-Free Grammar)
… còn gọi là văn phạm cấu trúc đoạn z G =
Kiểm tra ngữ pháp (Microsoft)
z T – tập các ký hiệu kết thúc (terminals)
z N - tập các ký hiệu không kết thúc (non-terminals)
Trích rút thông tin (Hobbs 1996)
z P – ký hiệu tiền kết thúc (preterminals), khi viết lại trở thành ký ký hi ệ hi u ệ kết ế thúc thúc, P ⊂ N
So với văn phạm cảm ngữ cảnh
z S – ký hiệu bắt đầu R: αAγ ⇒ αβγ
z R: X → γ , X là ký hiệu không kết thúc; γ là chuỗi các Kho văn bản CSDL
ký hiệu kết thúc và không kết thúc (có thể rỗng) NY Times
z Văn phạm G sinh ra ngôn ngữ L câu truy vấn
z Bộ nhận dạng: trả về yes hoặc no
z Bộ PTCP: trả về tập các cây cú pháp 9 10 z Văn phạm ngữ cấu:
z α→β, với α ∈ V+ , β ∈ V*
Văn phạm phi ngữ cảnh
z Văn phạm cảm ngữ cảnh:
z r = α→β, với α ∈ V+ , β ∈ V* , ⏐α⏐≤⏐β⏐
z và α1Aα2→α1β’α2 với β’≠ε
z Văn phạm phi ngữ cảnh: z A → θ, A ∈ N, z ớ v i ớ θ ∈ V*= ( T ∪ N ) * )* z Văn phạm chính qui: z A → aB, VPCQ z A → Ba, VPPNC z A → a, với A, B ∈ N, a ∈ T. VPCNC VPNC 11 12