Bài giảng Xử lý ngôn ngữ tự nhiên - Chương 7: Phân lớp văn bản Tiếng Việt theo hướng tiếp cận lexical chain - Lê Thanh Hương

4/21/2011 1 PHÂN LỚP VĂN BẢN TIẾNG VIỆT THEO HƯỚNG TIẾP CẬN LEXICAL CHAIN PHẦN I: TỔNG QUAN VỀ BÀI TOÁN PHÂN LỚP VĂN BẢN Các phương pháp biểu diễn văn bản ƒ Mô hình vector ƒ Văn bản = 1 vector n chiều + trọng số cho mỗi giá trị của nó ƒ Mô hình vector thưa ố từ ới t ố khá 0 hỏ h ất hiề ới ố từ óƒ s v rọng s c n ơn r n u so v s c trong Cơ sở dữ liệu Các phương pháp biểu diễn văn bản ƒ Mô hình tần số kết hợp TF x IDF ƒ Xét: ƒ Tập dữ liệu gồm m văn bản: D = {d1, d2, dm}. ƒ Mỗi văn bản biểu diễn dưới dạng một vector gồm n thuật ngữ T = {t1, t2,tn}. ƒ fij là số lần xuất hiện của thuật ngữ ti trong văn bản dj ƒ m là số lượng văn bản ƒ hi là số văn bản mà thuật ngữ ti xuất hiện ƒ Gọi W = {wij } là ma trận trọng số, trong đó wij là giá trị trọng số của thuật ngữ ti trong văn bản dj Các phương pháp biểu diễn văn bản ƒ Ma trận trọng số TFxIDF được tính như sau: ⎧ ⎞⎛ ⎪⎩ ⎪⎨ ≥⎟⎟⎠⎜ ⎜ ⎝ += l¹i ng−îc nÕu nÕu1 0 h h mf w iji ij ij 1log)]log([ Các phương pháp biểu diễn văn bản (tt) ƒ Mô hình Lexical Chain: ƒ “Lexical Chain” là một khái niệm nhằm duy trì tính cố kết giữa các từ trong văn bản có mối liên quan với nhau về mặt ngữ nghĩa ƒ Một số loại quan hệ về ngữ nghĩa giữa các từ: ƒ Lặp lại (Repeatation) ƒ Đồng nghĩa (synonyms ) ƒ Trái nghĩa () ƒ Bộ phận-Toàn thể (hypernyms, hyponyms ) ƒ ƒ Ví dụ : C1= {kinh tế, thương mại, lĩnh vực, vốn, thị trường} 4/21/2011 2 Các thuật toán giải quyết bài toán Phân lớp văn bản ƒ Thuật toán cây quyết định. ƒ Thuật toán k-NN. ƒ Thuật toán Lexical Chain. Thuật toán Cây quyết định ƒ Cây quyết định gồm các nút quyết định, các nhánh và lá : ƒ Mỗi lá gắn với một nhãn lớp, ƒ Mỗi nút quyết định mô tả một phép thử X nào đó, ƒ Mỗi nhánh của nút này tương ứng với một khả năng của X. ƒ Ý tưởng: Phân lớp một tài liệu dj bằng phép thử đệ quy các trọng số mà các khái niệm được gán nhãn cho các nút trong của cây với vector cho đến khi đạt tới một nút lá => nhãn của nút lá này được gán cho tài liệu dj. ƒ Ưu điểm: chuyển dễ dàng sang dạng cơ sở tri thức là các luật Nếu - Thì . ƒ Nhược điểm: ƒ Cây thu được thưòng rất phức tạp, chỉ phù hợp với tập mẫu ban đầu. ƒ Khi áp dụng cây với các dữ liệu mới sẽ gây ra sai số lớn. Thuật toán kNN (K-Nearest Neighbor) ƒ Tư tưởng : tính toán độ phù hợp của văn bản đang xét với từng lớp (nhóm) dựa trên k văn bản mẫu có độ tương tự gần nhất. ƒ Có 3 cách gán nhãn: ƒ Gán nhãn văn bản gần nhất: ƒ Gán nhãn theo số đông ƒ Gán nhãn theo độ phù hợp chủ đề ƒ Cách biểu diễn văn bản (hướng tiếp cận truyền thống): TF x IDF Thuật toán Lexical Chain ƒ Bước 1: Đọc từ w trong văn bản. ƒ Bước 2: Tiến hành dừng nếu w là stop-word. ƒ Bước 3: Thông qua WordNet, lấy về tập S gồm tất cả các nghĩa mà w có thể có. ƒ Bước 4: Tiến hành tìm kiếm mối liên hệ gần nhất giữa w với các từ trong tập hợp chain đã được khởi tạo ƒ Nếu tìm thấy mối liên hệ đủ gần, tiến hành kết nạp w vào chain đó, đồng thời khử nhập nhằng nghĩa cho w bằng cách tỉa đi tất cả các sense đã không được sử dụng để tìm mối liên hệ này ƒ Nếu không tìm được chain nào thoả mãn, tiến hành lập chain mới và kết nạp w là từ đầu tiên. Lý do lựa chọn hướng Lexical Chain ƒ Can thiệp vào bản chất ngôn ngữ của văn bản, thay vì mô hình toán học thuần tuý ƒ Khử nhập nhằng ngữ nghĩa của từ rất tốt. Hiệ ả khi hệ thố ầ “h l i”ƒ u qu ng c n ọc ạ ƒ Giúp thu gọn không gian bài toán ƒ Là hướng tiếp cận mới PHẦN II: TIẾP CẬN BÀI TOÁN PHÂN LỚP VĂN BẢN TIẾNG VIỆT THEO HƯỚNG LEXICAL CHAIN 4/21/2011 3 Các tác động của đặc trưng ngôn ngữ Tiếng Việt đến bài toán ƒ Cần phải thiết kế thêm giải thuật để tách từ ƒ Không cần phải giải quyết bài toán Stemming ƒ Hiện tượng từ đồng âm: nhập nhằng ngữ nghĩa ế ể ểƒ Ti ng Việt chưa có một WordNet hoàn chỉnh đ bi u đạt các mối quan hệ ngữ nghĩa một cách phong phú và đầy đủ như Tiếng Anh Mô hình giải quyết bài toán Từ điển Tiếng Việt 1.Tiền xử lý Input Text Từ điển Stop- word Kho văn bản đã huấn luyện Cây phân cấp ngữ nghĩa 2. Xây dựng Lexical Chains (LC) 3.Tính độ tương đương với các văn bản mẫu bằng LC 4.Quyết định lớp cho văn bản Categorized Text Các yếu tố ngôn ngữ được sử dụng ƒ Từ điển Tiếng Việt : 70.000 từ (có gắn nghĩa) ƒ Từ điển từ dừng ƒ Cây phân cấp ngữ nghĩa ROOT Cây phân cấp ngữ nghĩa Tiếng Việt Bird Chim sẻ Vàng anhTừ Mammal Bò Gấu Fish Cá trắm Cá thu animal ConcreteThing K N Mức trừu tượng chung thấp nhất N KSEMDIST = Tiền xử lý văn bản ƒ Tách từ ƒ Gán nhãn từ loại, lọc ra các danh từ L i bỏ từ dừ begin Chia văn bản thành các truy vấn nhỏ hơn Bỏ qua 1 Là từ khoá ? F các dấu “.”, “, “ , “;” , “:” Xét từng truy vấn (các tiếng) ƒ oạ ng. end tiếng ở bên phải Cắt từ khỏi truy vấn Truy vấn rỗng ? T F T Giải thuật xây dựng Lexical Chain ƒ Bước 1: Với mỗi danh từ trong văn bản, liệt kê tất cả các nghĩa mà nó có thể có. ƒ Bước 2: Sử dụng WSDG để xác định nghĩa phù hợp nhất của mỗi từ trong số tập hợp nghĩa xác định ở bước 1. ƒ Bước 3: Xây dựng các Lexical Chain dựa vào nghĩa duy nhất vừa tìm được cho mỗi từ. ƒ Xuất phát từ tập chain rỗng. ƒ Với mỗi từ w: ƒ kết nạp nó vào chain c nếu độ tương đồng của nó với tất cả các từ trong c đều đủ gần (vượt ngưỡng lập trước) ƒ Ngược lại, lập chain mới và kết nạp nó là từ đầu tiên α Đồ thị khử nhập nhằng nghĩa ƒ Gọi: ƒ T = {T1 , T2, Tn} là tập các danh từ trong văn bản. ƒ Si (i=1,...mi) là tập hợp các nghĩa mà danh từ Ti có thể có được (mi là số lượng nghĩa của Ti) ƒ G=(V,E) ƒ Vi biểu diễn Ti, nhưng chia làm mi phần ƒ Mỗi phần Vij biểu diễn nghĩa Sij của Ti ƒ Mỗi cạnh trong E nối Vij và Vi’j’ ƒ Mỗi cạnh được gán trọng số: ƒ Trọng số của mỗi nghĩa Vij: ' ' , ' '( , ) ( )ij i j ij i jw V V sim S S= ' '( ) ( , ) ( ' , , ' 1, )ij ij i jw V w V V i i i i n= ≠ =∑ 4/21/2011 4 Ví dụ minh hoạ giải thuật Vận Đơn vị « Sáng nay, mẹ tôi đi chợ mua hai cân đường để vắt nước chanh » tải Gia vị quy uớc đo lường Vật dụng Hoa quả ĐƯỜNG CÂN CHANH + Đường: W(‘Gia vị’) =2.0, W(‘vận tải’) =0.8 => Đường = Gia vị + Cân: W(‘đơn vị đo lường’) =1.8, W(‘Vật dụng’) =1.4 ⇒Cân = đơn vị đo lường Đánh giá các Lexical Chain ƒ Điểm cho mỗi chain: ƒ score(C) = Length * Homogeneity ƒ Trong đó: L th Số l á “l t từ” t Cƒ eng : ượng c c ượ rong . ƒ Homogeneity: Tính đồng nhất giữa các từ trong C ƒ Alpha = 0.75 _ _ _ _ _Homogeneity 1 Number of distinct words in C Length α= − Dùng LC tính độ tương tự giữa các văn bản ƒ Ký hiệu các chuỗi từ vựng c và d lần lượt là : ƒ c = {c1,c2,, cm} và d = {d1,d2,, dn} ƒ Trong đó, mỗi thành phần ci, dj (i=1..m, j=1..n) đều chỉ có 1 nghĩa duy nhất lần lượt là và .cs ds ƒ Độ tương đồng giữa c và d : ƒ Độ tương tự giữa chain c và văn bản D i j 1 1 ( , ) ( , ) i j m n c d i j sim c d sim s s = = = ∑∑ ( , ) ( , ) d D sim c D sim c d ∈ = ∑ Gán nhãn lớp cho văn bản ƒ Gán nhãn theo tổng độ phù hợp chủ đề ƒ Lần lượt tính tổng độ phù hợp của văn bản Q với tất cả các phân lớp có trong k văn bản đã lấy ra ƒ Gán nhãn chủ đề phù hợp nhất cho Q ƒ Q sẽ thuộc vào phân lớp có tổng độ liên quan cao nhất. PHẦN III: TIẾP CẬN BÀI TOÁN PHÂN LỚP VĂN BẢN TIẾNG VIỆT THEO HƯỚNG LEXICAL CHAIN Chức năng Huấn luyện tập mẫu Tiền xử lý Xây dựng tập Lexical Chains Lọc các Chains mạnh và lưu trữ Tập văn bản thô (đã phân lớp đúng) CHỨC NĂNG HUẤN LUYỆN TẬP MẪU Tập văn bản được huấn luyệnTập văn bản chỉ chứa danh từ Tập văn bản dưới dạng các chain 4/21/2011 5 Xây dựng các Lexical Chain Từ điển Tiếng Việt (có gắn nghĩa) Cây phân cấp ngữ nghĩa Tập văn bản (biểu diễn dưới dạng các danh từ ) XÂY DỰNG TẬP LEXICAL CHAINS Thu thập tập nghĩa Xây dựng WSD Graph Chọn nghĩa phù hợp nhất Tập danh từ+ tập nghĩa Tập các chain cho văn bản Cấu trúc nên các chain Chức năng Phân lớp văn bản Từ điển tiếng Việt+ ngữ nghĩa Tập V.bản đã huấn luyện Văn bản đầu vào (cần phân lớp) Chủ đề phù hợp nhất cho văn bản Tiền xử lý Xác định độ liên quan Gán chủ đề Tập các chains mạnh Các văn bản phù hợp nhất (có kèm chủ đề) PHÂN LỚP VĂN BẢN Thiết kế dữ liệu cá quả composite word ¾Từ điển Tiếng Việt (nguồn: trung tâm từ điển học Vietlex): Animal _ _ cá dữ ở nước ngọt, thân tròn, dài, có nhiều đốm đen, đầu nhọn, khoẻ, bơi nhanh Thiết kế dữ liệu ¾Cây phân cấp nghĩa (nguồn: trung tâm từ điển học Vietlex): Organization Root/ConcreteThing/LivingThing/People/Organization Thiết kế dữ liệu ƒ Lưu các Lexical Chain: ƒ Tập lexical chain của mỗi văn bản lưu trong một file .txt ƒ Các lexical chain cách nhau 1 dòng trống ƒ Trong 1 lexical chain: Mỗi từ được lưu trên 1 dòngƒ ƒ Câu trúc mỗi từ như sau: ƒ Ví dụ: luật sư|People|4 bị cáo|People|1 thẩm phán|People|3 cán bộ|People|2 người làm|People|1 Từ Nghĩa Số lần xuất hiện Giao diện chính 4/21/2011 6 Chức năng quản lý từ điển, từ dừng và văn bản mẫu Tập ngữ liệu thử nghiệm o Các bài báo được sưu tầm trên trang tin vietnamnet ( o 8 chủ đề: Khoa học, Vi tính, Giáo dục, Pháp luật, Đời sống, Thể thao, Kinh doanh, Ô tô xe máy Số bài báo 100 Số chủ đề (lớp) 8 Kích thước bài báo lớn nhất 6.13 KB Kích thước bài báo nhỏ nhất 1.11 KB Kích thước trung bình của một bài báo 3.30 (KB) Số danh từ nhiều nhất trong một bài báo 89 Số danh từ ít nhất trong một bài báo 18 Số danh từ trung bình trong một bài báo 35.47 Một số kết quả thử nghiệm Số bài báo được thử nghiệm 100 Thời gian phân lớp nhanh nhất 0.2 s Thời gian phân lớp chậm nhất 1.9 s Thời gian phân lớp trung bình 0.713 Số văn bản được phân lớp đúng 92 Hiệu suất phân lớp 92 % Kích thước trung bình của mỗi bài báo 3.30 (KB) Số danh từ trung bình trên mỗi bài báo 35.47 Số văn bản phân lớp được 100 Độ chính xác (precision) 92 % Nhận xét ƒ Các văn bản bị phân lớp sai do một số nguyên nhân: ƒ Bản thân nội dung văn bản cũng có sự nhập nhằng. ƒ Sai từ khâu tách từ và lọc danh từ. ấ ế ề ốƒ Cây phân c p ngữ nghĩa còn hạn ch v s lượng nghĩa, dẫn đến một số danh từ có nghĩa xa nhau nhưng lại cùng thuộc về một lớp nghĩa trừu tượng (ví dụ: Concept, ConcreteThing.) ƒ Độ sâu của cây chưa lớn nên dẫn tới độ tương đồng của các từ thuộc dạng trên lại cao.