Bài giảng Xử lý ngôn ngữ tự nhiên (Natural Language Processing): Bài 7.2 - Lê Thanh Hương

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