Luận văn Thạc sĩ Công nghệ thông tin: Xử lý nhập nhằng nghĩa của từ sử dụng học máy không giám sát

Chia sẻ: Tomjerry001 | Ngày: | Loại File: PDF | Số trang:89

Thêm vào BST

Báo xấu

41
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu nghiên cứu của đề tài là hiểu và phân biệt WSI và WSD, các phương pháp tiếp cận cho WSI và WSD. Tìm hiểu về mô hình chủ đề và các tiếp cận điển hình như HDP (mô hình Bayes phi tham số), LDA, CTM (mô hình Bayes có tham số). Tìm hiểu cách áp dụng các phương pháp HDP, LDA, CTM cho WSI . Sau đó ta xây dựng một hệ thống WSI dựa vào phương pháp HDP với dữ liệu ở quyết bài toán số 14 tại cuộc thi SemEval-2010 và so sánh các phương pháp khác cho WSI như LDA và CTM, ta thấy được ưu điểm của mô hình HDP, đó là xác định tự động số lượng nghĩa biến đổi trên một từ trong khi đó LDA, CTM lại cần một số nghĩa cố định trước được xây dựng bằng tay, đồng thời so sánh hiệu suất của các hệ thống này với các hệ thống tại SemEval 2010 và nhận thấy rằng HDP có kết quả vượt trội so với các hệ thống khác, hơn cả CTM và LDA. Trong phần công việc tương lai, một cách mới sử dụng HDP cho bài toán liên quan đã được đề xuất.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Công nghệ thông tin: Xử lý nhập nhằng nghĩa của từ sử dụng học máy không giám sát

1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ ------------------------------------------- TRẦN THỊ HIỀN XỬ LÝ NHẬP NHẰNG NGHĨA CỦA TỪ SỬ DỤNG HỌC MÁY KHÔNG GIÁM SÁT LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN Hà Nội – 2014
2 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ ------------------------------------------- TRẦN THỊ HIỀN XỬ LÝ NHẬP NHẰNG NGHĨA CỦA TỪ SỬ DỤNG HỌC MÁY KHÔNG GIÁM SÁT Ngành: Công nghệ thông tin Chuyên ngành: Kỹ thuật phần mềm Mã số: 60480103 LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: TIẾN SĨ NGUYỄN PHƢƠNG THÁI Hà Nội – 2014
1 LỜI CẢM ƠN Để hoàn thành đƣợc luận văn thạc sỹ này, trƣớc hết tôi xin gửi lời cảm ơn sâu sắc nhất đến TS.Nguyễn Phƣơng Thái. Thầy đã cung cấp cho tôi những kiến thức, tài liệu, phƣơng pháp khi nghiên cứu một vấn đề mang tính khoa học. Thầy thƣờng xuyên đƣa ra và giúp tôi có những ý tƣởng khi làm luận văn. Tôi xin chân thành cảm ơn thầy về sự hỗ trợ chân thành và nhiệt tình trong suốt thời gian qua. Tôi xin bày tỏ lòng biết ơn tới các thầy, cô giáo trong Bộ môn Công nghệ phần mềm, Khoa Công nghệ thông tin - Phòng Đào tạo sau đại học - Nghiên cứu Khoa học, Trƣờng Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tạo mọi điều kiện tốt nhất để tôi hoàn thành khóa học này. Đồng thời, tôi cũng xin cảm ơn gia đình, bạn bè, những ngƣời luôn khuyến khích và giúp đỡ tôi trong mọi hoàn cảnh khó khăn. Tôi xin cảm ơn cơ quan và các đồng nghiệp đã hết sức tạo điều kiện cho tôi trong suốt thời gian tôi học tập và rèn luyện tại trƣờng Đại học Công nghệ - Đại học Quốc gia Hà Nội. Tôi xin chân thành cảm ơn bạn Hoàng Thanh Tùng – K53 Trƣờng Đại học Công nghệ - Đại học Quốc gia Hà Nội đã có những góp ý quý báu về đề tài nghiên cứu của tôi. Hà Nội, ngày 28 tháng 10 năm 2014 Học viên Trần Thị Hiền
2 LỜI CAM ĐOAN Tôi xin cam đoan những kiến thức trình bày trong luận văn này là do tôi tìm hiểu, nghiên cứu và trình bày theo cách hiểu của bản thân dƣới sự hƣớng dẫn trực tiếp của TS.Nguyễn Phƣơng Thái. Trong quá trình làm luận văn tôi có tham khảo các tài liệu có liên quan và đã ghi rõ nguồn gốc tham khảo tài liệu đó. Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo tôi xin chịu hoàn toàn trách nhiệm. Hà nội, ngày 28 tháng 10 năm 2014 Học viên Trần Thị Hiền
3 MỤC LỤC LỜI CẢM ƠN ................................................................................................................................ 1 LỜI CAM ĐOAN ......................................................................................................................... 2 MỤC LỤC...................................................................................................................................... 3 DANH MỤC CÁC KÍ HIỆU, TỪ VIẾT TẮT .......................................................................... 5 DANH MỤC CÁC HÌNH VẼ ..................................................................................................... 6 DANH MỤC CÁC BẢNG BIỂU ............................................................................................... 7 MỞ ĐẦU ........................................................................................................................................ 8 CHƢƠNG I: GIỚI THIỆU ........................................................................................................ 10 1.1. WSI và WSD ................................................................................................................... 10 1.2. Phƣơng pháp tiếp cận cho WSD ................................................................................... 11 1.3. Phƣơng pháp tiếp cận cho WSI ..................................................................................... 12 1.3.1. Phƣơng pháp phân cụm ....................................................................................... 12 1.3.2. Đồ thị xuất hiện đồng thời (Co-occurrence graphs ) ........................................ 14 1.3.3. Mục tiêu đề tài ...................................................................................................... 15 1.3.4. Ứng dụng của đề tài ....................................................................................... 16 CHƢƠNG II: BÀI TOÁN MÔ HÌNH CHỦ ĐỀ VÀ CÁC TIẾP CẬN ĐIỂN HÌNH ....... 17 2.1. Tổng quan về mô hình chủ đề ....................................................................................... 17 2.2. LDA .................................................................................................................................. 18 2.3. CTM ................................................................................................................................. 20 2.4. HDP .................................................................................................................................. 22 2.5. Ứng dụng của mô hình chủ đề ...................................................................................... 24 2.6. Sử dụng mô hình chủ đề trong WSI ............................................................................ 26 2.6.1. Ngữ cảnh địa phƣơng và ngữ cảnh toàn cục ..................................................... 26 2.6.2. Xem bài toán WSI nhƣ một bài toán mô hình chủ đề ...................................... 26 CHƢƠNG III: SỬ DỤNG PHƢƠNG PHÁP HDP CHO WSI ............................................. 28
4 3.1. Tổng quan về HDP ......................................................................................................... 28 3.1.1. Thiết lập ................................................................................................................. 30 3.1.2. Dirichlet Process ................................................................................................... 31 3.1.3. HDP ........................................................................................................................ 32 3.2. Sử dụng phƣơng pháp HDP cho WSI .......................................................................... 38 3.2.1. Giới thiệu ............................................................................................................... 38 3.2.2. WSI dựa vào phƣơng pháp Bayes ...................................................................... 39 3.3. So sánh phƣơng pháp HDP với LDA và CTM ........................................................... 41 CHƢƠNG IV: ĐÁNH GIÁ VÀ KẾT QUẢ THỰC NGHIỆM ............................................ 46 4.1. Mô tả dữ liệu ................................................................................................................... 46 4.1.1. Tập dữ liệu huấn luyện ........................................................................................ 47 4.1.2. Tập dữ liệu thử nghiệm ........................................................................................ 48 4.2. Phƣơng pháp đánh giá .................................................................................................... 48 4.2.1. Đánh giá không giám sát ..................................................................................... 49 4.2.2. Đánh giá giám sát ................................................................................................. 52 4.3. Thực nghiệm .................................................................................................................... 53 4.3.1. Tiền xử lý dữ liệu ................................................................................................. 54 4.3.2. Phƣơng pháp huấn luyện và thử nghiệm ........................................................... 55 4.3.3. Xử lý dữ liệu đầu ra .............................................................................................. 56 4.4. Kết quả và so sánh .......................................................................................................... 58 4.4.1. Hiệu suất của hệ thống ......................................................................................... 59 4.4.2. Kết quả đánh giá không giám sát .................................................................. 59 4.4.3. Kết quả đánh giá giám sát ................................................................................... 62 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ............................................................................... 65 TÀI LIỆU THAM KHẢO.......................................................................................................... 66 PHỤ LỤC ..................................................................................................................................... 68
5 DANH MỤC CÁC KÍ HIỆU, TỪ VIẾT TẮT Từ viêt tắt Từ tiếng Anh CBC Clustering By Committee CTM Correlated Topic Model DP Dirichlet Proceses GS Gold Sense HDP Hierarchical Dirichlet Proceses LDA Latent Dirichlet Allocation MFS Most Frequent Sense Plsi Probabilistic latent semantic indexing POS Part Of Speech WSD Word Sense Disambiguation WSI Word Sense Induction WSID Word Sense Induction and Discrimination
6 DANH MỤC CÁC HÌNH VẼ Hình 1.1: Ví dụ về mô hình siêu đồ thị ............................................................................. 14 Hình 2.1: Biểu diễn đồ họa của LDA. ................................................................................ 19 Hình 2.2: Quá trình sinh trong CTM. ................................................................................. 22 Hình 2.3: Mô hình hỗn hợp HDP. ..................................................................................... 23 Hình 2.4: Các từ trực quan trên hình ảnh ........................................................................... 25 Hình 3.1: Mô hình hỗn hợp HDP. ...................................................................................... 33 Hình 3.2: Mô tả quyền kinh doanh nhà hàng Trung Hoa. ................................................ 35 Hình 3.3: Lantent Dirichlet Allocation cho WSI ............................................................... 39 Hình 3.4: Mô hình HDP cho WSI ..................................................................................... 41 Hình 3.5: Hiệu suất của mô hình Brody và Lapata với số lƣợng ngữ nghĩa khác nhau..... 42 Hình 3.6: Kết quả F1 – Measure khi sử dụng phƣơng pháp LDA và HDP cho WSI với tập dữ liệu tại cuộc thi SemEval 2007 ..................................................................................... 43 Hình 4.1: Các giai đoạn huấn luyện, thử nghiệm và đánh giá của SemEval-2010 task14. 46 Hình 4.2: Các bƣớc của quá trình làm thực nghiệm ........................................................... 53 Hình 4.3: Ví dụ về kết quả tiền xử lý dữ liệu ..................................................................... 54
7 DANH MỤC CÁC BẢNG BIỂU Bảng 1.1: Precision, recall and F-measure của thuật toán phân cụm ................................. 13 Bảng 1.2: Kết quả của siêu đồ thị dựa trên các hệ thống MFS .......................................... 15 Bảng 2.1: Xác định nghĩa của từ “accounting”. ................................................................. 25 Bảng 3.1: Ví dụ phân cụm từ mục tiêu “deploy” sử dụng LDA ...................................... 44 Bảng 3.2: Ví dụ phân cụm từ mục tiêu “deploy” sử dụng CTM ...................................... 44 Bảng 3.3: Ví dụ phân cụm từ mục tiêu “deploy” sử dụng HDP ...................................... 44 Bảng 4.1: Chi tiết về tập huấn luyện và tập thử nghiệm .................................................... 47 Bảng 4.2: Tạo tập huấn luyện: Các truy vấn cho từ mục tiêu failure ................................. 48 Bảng 4.3: Ma trận nghĩa phân cụm và GS.......................................................................... 52 Bảng 4.4: So sánh sự giống và khác nhau của hai hệ thống............................................... 57 Bảng 4.5: Thời gian thực hiện chƣơng trình ..................................................................... .58 Bảng 4.6: Đánh giá không giám sát theo V-Measure........................................................ 60 Bảng 4.7: Đánh giá không giám sát theo Paired F-Score ................................................... 61 Bảng 4.8: Supervised recall (SR) (tập thử nghệm đƣợc chia :80% ánh xạ, 20% đánh giá) ............................................................................................................................................ 62 Bảng 4.9: Supervised recall (SR) (tập thử nghệm đƣợc chia :60% ánh xạ, 40% đánh giá) ............................................................................................................................................ 63
8 MỞ ĐẦU Xử lý nhập nhằng ngữ nghĩa của từ là một trong những vấn đề đƣợc rất nhiều nhà nghiên cứu trong lĩnh vực xử lý ngôn ngữ tự nhiên quan tâm đến. Vì vậy có nhiều cách tiếp cận khác nhau để giải quyết vấn đề xử lý nhập nhằng ngữ nghĩa chẳng hạn nhƣ các phƣơng pháp dựa vào tri thức (knowledge-based methods) [1] và các phƣơng pháp dựa vào kho ngữ liệu (corpus-based methods). Đối với phƣơng pháp thứ hai, phƣơng pháp có thể sử dụng là học có giám sát, học không có giám sát và kết hợp của hai phƣơng pháp này. Nói chung, các phƣơng pháp học có giám sát cho ra kết quả với độ chính xác cao hơn nhƣng nhƣợc điểm của phƣơng pháp này đòi hỏi tiêu tốn công sức trong việc xây dựng tập dữ liệu gán nhãn, nó lại không nhận biết đƣợc nghĩa của từ trong trƣờng hợp mới. Trong khi đó phƣơng pháp không giám sát khắc phục đƣợc hai nhƣợc điểm này. Do đó, phƣơng pháp học không giám sát là một hƣớng đi rất đƣợc chú ý để giải quyết vấn đề này. Nó sẽ phân cụm các trƣờng hợp xuất hiện của từ trong văn bản, mỗi cụm thể hiện một nghĩa. WSI (Word Sense Induction) là một hƣớng tiếp cận không giám sát cho vấn đề này, WSI đã cho thấy lợi thế của nó cho việc xử lý nhập nhằng nghĩa của từ trong một số lĩnh vực mà dữ liệu huấn luyện đƣợc chú thích không có sẵn hoặc số lƣợng nghĩa của các từ khác nhau phụ thuộc vào mục đích khác nhau. Trong khi có nhiều phƣơng pháp cho WSI, thì phân cụm theo ngữ cảnh là một trong những giải pháp hiệu quả nhất và đƣợc sử dụng rộng rãi. Luận văn tập trung vào việc áp dụng một mô hình Bayes phi tham số (Nonparametric Bayesian model) - Hierarchical Dirichlet Process ( HDP) cho bài toán WSI. Kết quả đƣợc thể hiện thông qua việc so sánh với phƣơng pháp Latent Dirichlet Allocation (LDA) - một mô hình Bayes có tham số của Blei và Jordan [3] cho vấn đề này, và còn đƣợc so sánh với phƣơng pháp của Blei và Lafferty [2] đó là Correlated Topic Model (CTM) với cùng một tập dữ liệu ở bài toán số 14 trong cuộc thi SemEval - 2010. Ta thấy rằng mô hình HDP vƣợt trội về chất lƣợng xác định nghĩa và có ƣu điểm là xác định một cách tự động số lƣợng nghĩa biến đổi trên một từ thì LDA, CTM lại cần một số nghĩa cố định trƣớc đƣợc xây dựng bằng tay. Đó là sự vƣợt trội hơn của cách tiếp cận WSI dựa trên HDP so với các cách tiếp cận khác. Ngoài phần kết luận, luận văn đƣợc trình bày thành 4 chƣơng với nội dung đƣợc trình bày nhƣ sau:
9 Chƣơng 1: Giới thiệu về WSI, WSD và các phƣơng pháp tiếp cận cho WSI, WSD, đồng thời giới thiệu về mục tiêu và kết quả sẽ trình bày trong luận văn. Chƣơng 2: Bài toán mô hình chủ đề và các tiếp cận điển hình Ở chƣơng này trình bày tổng quan về mô hình chủ đề, các tiếp cận điển hình nhƣ: LDA, CTM (mô hình Bayes có tham số ), HDP (mô hình Bayes phi tham số) và cách sử dụng chúng trong WSI. Chƣơng 3: Sử dụng phƣơng pháp HDP cho WSI Với tính linh hoạt trong việc xác định nghĩa của từ một cách tự động. Trong khuôn khổ luận văn quan tâm đến việc xác định nghĩa của từ dựa vào phƣơng pháp HDP. Ở chƣơng này trình bày sâu hơn về phƣơng pháp HDP và so sánh với phƣơng pháp LDA và CTM. Chúng ta sẽ thấy rõ hơn về ƣu, nhƣợc điểm của phƣơng pháp này thông qua kết quả thực nghiệm ở chƣơng 4. Chƣơng 4: Đánh giá và kết quả thực nghiệm Trong phần này đƣa ra chi tiết về phƣơng pháp đƣợc sử dụng để đánh giá hệ thống WSI, mô tả dữ liệu ở bài toán số 14 của cuộc thi SemEval - 2010 đƣợc sử dụng để huấn luyện, thử nghiệm trong hệ thống này và mô tả chi tiết thực nghiệm xây dựng hệ thống WSI của ta. Tiếp theo là kết quả công việc bao gồm hiệu suất của hệ thống trên tập dữ liệu ở bài toán số 14 của cuộc thi SemEval – 2010 và so sánh kết quả với hai phƣơng pháp CTM, LDA. Cuối cùng là kết luận, hƣớng phát triển, tài liệu tham khảo và phụ lục. Phần kết luận trình bày tóm tắt kết quả thu đƣợc và đề xuất hƣớng nghiên cứu tiếp theo.
10 CHƢƠNG I: GIỚI THIỆU Nội dung của chƣơng này giới thiệu về WSI và WSD, qua đó phân biệt đƣợc sự khác nhau giữa chúng. Đồng thời giới thiệu một số phƣơng pháp tiếp cận cho WSI, WSD và mục tiêu của đề tài. 1.1. WSI và WSD Hiểu đƣợc nghĩa của từ một cách chính xác là điều cần thiết để giao tiếp, đặc biệt là thông tin liên lạc tự động. Tuy nhiên một từ có thể có nhiều nghĩa, việc xác định ý nghĩa đang đƣợc sử dụng không phải lúc nào cũng dễ dàng cho cả con ngƣời và máy tính. Ví dụ: Xét nghĩa của từ “access” trong hai câu sau đây: The police gained access through a broken window. (Cảnh sát vào được thông qua cửa sổ vỡ). You need a password to get access to the computer system. (Bạn cần một mật khẩu để truy cập vào hệ thống máy tính). Nhƣ vậy ở câu thứ nhất từ “access” có nghĩa là sự tiếp cận, cách vào , quyền vào một nơi nào đó. Còn ở câu thứ hai có nghĩa là quyền sử dụng, truy cập. Trong ví dụ trên, chúng ta khá dễ dàng phân biệt các từ “access” , tuy nhiên trong một số trƣờng hợp, nhiệm vụ phân biệt là một thách thức cho các nhà nghiên cứu từ ngữ học thậm chí là ngƣời có kinh nghiệm. WSI và WSD là hai cách tiếp cận khác nhau cho bài toán nhận dạng tự động nghĩa của từ. Hệ thống WSD thƣờng theo cách tiếp cận giám sát – yêu cầu ngữ liệu đƣợc gắn nhãn thủ công cho giai đoạn huấn luyện. Ngƣợc lại, các hệ thống WSI là không giám sát; chúng chỉ cần văn bản thô, điều này có sẵn “miễn phí” trên internet và nhiều nguồn khác. Kết quả là, việc chuyển hệ thống WSD tới miền dữ liệu hoặc ngôn ngữ mới là một công việc tốn kém bởi vì chúng ta phải cung cấp một dữ liệu đƣợc chú giải mới và kiến thức về ngôn ngữ /miền cụ thể. Việc chuyển một hệ thống WSI thì dễ hơn vì trong hầu hết các trƣờng hợp, chúng ta chỉ cần huấn luyện lại hệ thống trên dữ liệu “miễn phí ” mới. Các hệ thống WSD thƣờng dựa trên các danh sách cố định chứa các nghĩa đƣợc xác định trƣớc. Từ các danh sách này, nghĩa thích hợp nhất đƣợc chọn và gắn cho từ. Do đó số lƣợng nghĩa không thể thay đổi đƣợc trong hệ thống WSD. Điều này dẫn đến
11 một số khó khăn khi triển khai hệ thống với các lĩnh vực khác nhau và với các mục đích khác nhau. Trong một số ứng dụng, các ngữ nghĩa đƣợc xử lý thô có thể là hữu ích hơn các ngữ nghĩa đã làm mịn, và trong một số ứng dụng khác, lại đòi hỏi ngữ nghĩa đã đƣợc làm mịn. Các hệ thống WSI cho phép số lƣợng nghĩa của một từ thay đổi. Hơn nữa hệ thống WSD không thể phát hiện các nghĩa mà không xuất hiện trong “từ điển” của chúng. Bài toán này có thể đƣợc giải quyết dễ dàng trong hệ thống WSI; chúng ta chỉ cần cung cấp dữ liệu có chứa các nghĩa mới và điều chỉnh số lƣợng nghĩa nếu cần thiết. Mặc dù WSI có nhiều lợi thế hơn WSD, nhƣng các hệ thống WSD thƣờng có hiệu suất tốt hơn. Vì vậy, WSI không thể thay thế WSD trong tất cả các trƣờng hợp nhƣng nó lại đang rất đƣợc quan tâm. Xây dựng một hệ thống WSI là mục tiêu chính của luận văn này, nó dựa trên phƣơng pháp phân cụm ngữ cảnh, trong đó các ngữ cảnh của từ đƣợc nhóm lại thành các cụm đại diện cho các nghĩa. Tổng quan về cách tiếp cận cho bài toán WSD và WSI đƣợc đƣa ra trong phần tiếp theo của chƣơng. 1.2. Phƣơng pháp tiếp cận cho WSD Phƣơng pháp để xử lý nhập nhằng ngữ nghĩa thƣờng đƣợc phân loại theo nguồn tri thức chính để phân biệt các nghĩa (thƣờng đƣợc dùng bởi các chuyên gia ngôn ngữ học). Các phƣơng pháp này chủ yếu dựa vào từ điển chuyên ngành, tri thức về từ vựng, và không sử dụng bất cứ một thông tin ngữ liệu nào, đƣợc gọi dƣới thuật ngữ chuyên ngành là các phƣơng pháp dựa vào từ điển hay dựa vào tri thức. Điểm yếu của phƣơng pháp này là bộ cơ sở tri thức thƣờng sẽ rất lớn, hơn nữa với sự phức tạp của ngôn ngữ tự nhiên thì việc dùng các luật để xử lý nhập nhằng cũng chỉ đạt đƣợc độ chính xác có giới hạn. Ngƣời ta còn sử dụng phƣơng pháp học máy để giải quyết nhập nhằng ngữ nghĩa. Wilks và Stevenson báo cáo vài thử nghiệm về giải quyết nhập nhằng nghĩa của từ bằng cách sử dụng những thông tin thu đƣợc từ quá trình học tập trên ngữ liệu mẫu [15]. Phƣơng pháp này có thể phân loại nhƣ sau: Học không giám sát (unsupervised training): thông tin đƣợc tập hợp từ tập ngữ liệu thô chƣa đƣợc gán nhãn. Học có giám sát (supervised training): thông tin đƣợc tập hợp từ tập ngữ liệu đã đƣợc gán nhãn để huấn luyện hoặc lấy làm dữ liệu cho quá trình trích chọn. Và kết hợp cả hai phƣơng pháp trên là bán giám sát (semi-supervised). Đặc điểm của phƣơng pháp học máy không giám sát là phân cụm các trƣờng hợp xuất hiện của từ trong văn bản. WSI là một hƣớng tiếp cận cho vấn đề này.
12 1.3. Phƣơng pháp tiếp cận cho WSI Một phƣơng pháp thay thế để tiếp cận WSD chính là WSI [10]. WSI nhằm mục đích xác định tự động nghĩa của từ một cách trực tiếp từ ngữ liệu, WSI thƣờng đƣợc xem nhƣ một bài toán phân cụm không giám sát. Đầu vào cho thuật toán phân cụm là các ví dụ của từ mục tiêu với những bối cảnh đi kèm nó và đầu ra là một phép phân cụm các ví dụ này thành các lớp tƣơng ứng với các nghĩa suy diễn. Nói cách khác, các ngữ cảnh đƣợc nhóm cùng nhau trong cùng một lớp biểu diễn một nghĩa đặc trƣng [12]. Từ đây rất nhiều phƣơng pháp phân cụm đƣợc sử dụng, ta đi xét ba phƣơng pháp điển hình:  Phân cụm theo ngữ cảnh.  Phân cụm theo từ.  Đồ thị xuất hiện đồng thời (Co-occurrence graphs ). Hai phƣơng pháp tiếp cận đầu tiên có mối liên quan chặt chẽ và đƣợc bắt nguồn từ ý tƣởng tƣơng tự nhau. Phƣơng pháp đồ thị xuất hiện đồng thời cho thấy vấn đề từ các góc độ khác nhau, nó tạo ra kết quả của hình thức khác nhau. Chúng ta sẽ lần lƣợt xem xét từng cách tiếp cận một. 1.3.1. Phƣơng pháp phân cụm Ý tƣởng đằng sau phƣơng pháp tiếp cận phân cụm theo từ và phân cụm theo ngữ cảnh là các từ có ý nghĩa tƣơng tự sẽ xuất hiện trong bối cảnh tƣơng tự.Ý tƣởng này lần đầu tiên đƣợc đề xuất bởi Harris trong năm 1954 [18] và đƣợc biết đến với cụm từ: “một từ đƣợc đặc trƣng bởi những từ xung quanh nó” . Nhiều cuộc thử nghiệm đã đƣợc làm để thực hiện ý tƣởng này và chúng có thể đƣợc chia thành hai nhóm chính: phân cụm theo ngữ cảnh và phân cụm theo từ. Mặc dù hai cách tiếp cận dựa trên ý tƣởng giống nhau, nhƣng tính năng và các kỹ thuật đã đƣợc sử dụng thì khác nhau. Phân cụm theo từ Từ ý tƣởng này, các nhà nghiên cứu đã thu đƣợc nhiều phƣơng pháp để phân cụm các từ tƣơng tự theo ngữ cảnh của chúng. Một cụm bao gồm các từ có ý nghĩa tƣơng tự; vì vậy các từ phân cụm chỉ có một nghĩa rất đơn giản. Tuy nhiên, khi một từ có nhiều nghĩa, nó thuộc về tất cả các cụm đại diện cho nghĩa của mình. Mục đích của nhiệm vụ này là các nghĩa khác nhau của các từ đa nghĩa phải thuộc về các cụm khác nhau.
13 Trong phƣơng pháp này, mỗi từ đƣợc đại diện bởi một véc tơ đặc trƣng và một chức năng đƣợc chọn để đo sự giống nhau giữa các véc tơ đặc trƣng. Số lƣợng và các loại đặc trƣng khác nhau từ hệ thống này tới hệ thống khác. Một thuật toán phân cụm sau đó thì đƣợc áp dụng cho tập các véc tơ đặc trƣng. Trong năm 2002, Pantel anh Lin [11] đã áp dụng sáu thuật toán phân nhóm khác nhau trên một tập dữ liệu chung sử dụng các tính năng tƣơng tự nhau. Các nghĩa tạo ra đƣợc so sánh với các nghĩa thuộc tiêu chuẩn vàng lấy từ WordNet. Hiệu suất của hệ thống đƣợc đo bằng cách sử dụng F- measure, F-measure là trung bình điều hòa của độ chính xác (precision – P) và recall (R): 2 PR F (1.1) PR Kết quả hiển thị trong bảng 1.1. Bảng 1.1: Precision, recall and F-measure của thuật toán phân cụm (Dữ liệu đƣợc lấy từ [11]). Thuật toán Precision Recall F – measure CBC 60.8 50.8 55.4 UNICON 53.3 45.5 49.2 Buckshot 52.6 45.2 48.6 K-means 48.0 44.2 46.0 Bisecting K-means 33.8 31.8 32.8 Average-link 50.0 41.0 45.0 Nhƣ đƣợc thể hiện trong bảng. thuật toán CBC [11] có F-measure cao nhất và dƣờng nhƣ là thuật toán phân cụm tốt nhất. Tuy nhiên việc thực hiện các thuật toán ở trên là hạn chế. Một lý do của hiệu suất này bị hạn chế là chúng ta không có đủ thông tin. Phƣơng pháp tiếp theo – phân cụm theo ngữ cảnh, cho phép các nhà nghiên cứu sử dụng nhiều thông tin đặc biệt là các đồng xuất hiện địa phƣơng đƣợc đánh giá cao có liên quan đến từ mục tiêu cho nhiệm vụ phân cụm.
14 Phân cụm theo ngữ cảnh Khác với phân cụm theo từ, đối tƣợng cho phân cụm trong phƣơng pháp này không phải là từ mục tiêu mà là ngữ cảnh của từ đó. Trong khi phân cụm theo từ thƣờng sử dụng các đồng xuất hiện chung dựa trên các từ của chính bản thân chúng. (các đặc trƣng thƣờng là một phần của lời nói, sắp xếp có thứ tự, …), phân cụm theo ngữ cảnh cho phép sử dụng các đồng xuất hiện địa phƣơng. Trong năm 2009, Samuel Brody và Mirella Lapata [12] trình bày một hệ thống mà chỉ cần ngữ cảnh địa phƣơng là đầu vào cho nhiệm vụ xác định ngữ nghĩa. Brody và Lapata đã sử dụng LDA – một mô hình “túi từ” cho không gian mô hình ngữ cảnh và phân cụm. Một nghĩa trong hệ thống thực ra là một phân phối trên tập từ vựng, các nghĩa khác nhau đƣợc là đƣợc đại diện bởi các phân phối khác nhau. Hệ thống vƣợt trội so với hầu hết các hệ thống trong cuộc thi SemEval – 2007. Công việc sau đó đƣợc làm bởi Xuchen và Benjamin Van Durme trong năm 2011 [16] cho thấy hiệu suất có thể cải thiện bằng cách thay thế LDA bằng HDP. Do đó, phƣơng pháp phân nhóm theo ngữ cảnh có nhiều triển vọng hơn phƣơng pháp phân cụm theo từ. 1.3.2. Đồ thị xuất hiện đồng thời (Co-occurrence graphs ) Trong khi hai phƣơng pháp trƣớc cố gắng phân định một từ vào một cụm thích hợp nhất, phƣơng pháp đồ thị suất hiện đồng thời cố gắng để mô hình không gian nhƣ một đồ thị ở các nút là từ (hoặc tập các từ) và các đồng xuất hiện của từ đại diện cho các cạnh. Hình 1.1: Ví dụ về mô hình siêu đồ thị (hình từ [9])
15 Trong năm 2007, Klapaftis và Manandhar [9] đã giới thiệu hệ thống U o Y dựa trên mô hình siêu đồ thị. Trong U o Y, không gian bài toán là đƣợc thể hiện nhƣ một siêu đồ thị H= (V,F), trong đó V,F là tập các đỉnh và siêu cạnh tƣơng ứng. Trong cuộc thi SemEval – 2007 [7], U o Y đã cho thấy sự cải thiện so với Most Frequent Sense (MFS) ban đầu về độ tinh khiết và dữ liệu ngẫu nhiên: Bảng 1.2: Kết quả của siêu đồ thị dựa trên các hệ thống MFS (Dữ liệu lấy từ SemEval – 2007 [7]) Measure (nouns) UoY MFS Entropy 25.5 46.3 Purity 89.8 82.4 F-Measure 65.8 80.7 Measure (verbs) UoY MFS Entropy 28.9 44.4 Purity 82.0 77 F-Measure 45.1 76.8 1.3.3. Mục tiêu đề tài Mục đích của đề tài là xây dựng hệ thống WSI dựa trên phƣơng pháp phân cụm theo ngữ cảnh và so sánh với hệ thống WSI khác đó là phƣơng pháp HDP – mô hình Bayes phi tham số. Để làm đƣợc điều đó trƣớc hết ta cần làm rõ các vấn đề sau đây: - Hiểu và phân biệt WSI và WSD, các phƣơng pháp tiếp cận cho WSI và WSD. - Tìm hiểu về mô hình chủ đề và các tiếp cận điển hình nhƣ HDP (mô hình Bayes phi tham số), LDA, CTM (mô hình Bayes có tham số). - Tìm hiểu cách áp dụng các phƣơng pháp HDP, LDA, CTM cho WSI . Sau đó ta xây dựng một hệ thống WSI dựa vào phƣơng pháp HDP với dữ liệu ở quyết bài toán số 14 tại cuộc thi SemEval- 2010 và so sánh các phƣơng pháp khác cho WSI nhƣ LDA và CTM, ta thấy đƣợc ƣu điểm của mô hình HDP, đó là xác định tự động số lƣợng nghĩa biến đổi trên một từ trong khi đó LDA, CTM lại cần một số nghĩa
16 cố định trƣớc đƣợc xây dựng bằng tay, đồng thời so sánh hiệu suất của các hệ thống này với các hệ thống tại SemEval 2010 và nhận thấy rằng HDP có kết quả vƣợt trội so với các hệ thống khác, hơn cả CTM và LDA. Trong phần công việc tƣơng lai, một cách mới sử dụng HDP cho bài toán liên quan đã đƣợc đề xuất. 1.3.4. Ứng dụng của đề tài Nhƣ ở phần 1.3.3 thì mục đích của chúng ta là xây dựng một hệ thống WSI dựa vào phƣơng pháp HDP – mô hình Bayes phi tham số để ứng dụng vào công việc xử lý nhập nhằng ngữ nghĩa trong đó không gian ngữ cảnh của từ đƣợc phân cụm vào các chủ đề đại diện cho ý nghĩa của từ. Cụ thể chúng ta sẽ thấy đƣợc trong phần 2.5. Nhƣ vậy ở chƣơng này chúng ta đã tìm hiểu về WSD, WSI và nêu ra mục tiêu của luận văn là xây dựng một hệ thống WSI dựa vào mô hình HDP, sau đó so sánh với các mô hình LDA, CTM. Ba mô hình LDA, CTM và HDP chúng đều là mô hình chủ đề (topic models), vì vậy ở chƣơng tiếp theo chúng ta đi tìm hiểu chung về mô hình chủ đề và các tiếp cận điển hình.
17 CHƢƠNG II: BÀI TOÁN MÔ HÌNH CHỦ ĐỀ VÀ CÁC TIẾP CẬN ĐIỂN HÌNH Ở chƣơng trƣớc chúng ta đã đề cập đến một số phƣơng pháp tiếp cận cho WSI, trong đó phƣơng phƣơng pháp phân cụm theo ngữ cảnh có nhiều triển vọng hơn, trong khuôn khổ luận văn này trình bày mô hình phân cụm theo ngữ cảnh đó là mô hình Bayes có tham số (LDA, CTM) và mô hình Bayes phi tham số (HDP), nhƣng trƣớc hết chúng ta đi tìm hiểu tổng quan về mô hình chủ đề, cuối cùng là cách sử dụng chúng trong WSI. 2.1. Tổng quan về mô hình chủ đề Hiện nay các tài liệu của chúng ta tiếp tục đƣợc số hóa và lƣu trữ - theo hình thức tin tức, blog, các trang web, bài báo khoa học, sách, hình ảnh, âm thanh, video và mạng xã hội – nó trở nên khó khăn hơn để tìm kiếm và khám phá. Chúng ta cần công cụ tính toán mới để giúp việc tổ chức, tìm kiếm và hiểu một lƣợng lớn thông tin này. Hiện nay chúng ta sử dụng công cụ tìm kiếm nhƣ Google và Bing để khám phá internet. Cách phổ biến nhất là chúng cung cấp một số từ khóa để các công cụ tìm kiếm và sau đó nhận đƣợc một danh sách các tài liệu liên quan đến các từ khóa đó. Tuy nhiên, phƣơng pháp này không mô tả sự thay đổi trong các chủ đề và mô hình hóa các mối quan hệ giữa các văn bản. Đôi khi chúng ta có thể muốn tìm một chủ đề đầu tiên và sau đó thể chuyển hƣớng đến các tài liệu khác liên quan với chủ đề đó. Đây là một giải pháp tốt cho sự tƣơng tác với lƣu trữ trực tuyến của chúng ta. Tìm kiếm hình ảnh và khám phá các văn bản dựa trên chủ đề thông qua chúng. Chúng ta có thể phóng to và thu nhỏ để tìm kiếm cụ thể hoặc các chủ đề rộng lớn; chúng ta có thể nhìn thấy các chủ đề đó đã thay đổi nhƣ thế nào qua thời gian hoặc làm thế nào để chúng liên kết đƣợc với nhau. Chứ không phải là việc tìm kiếm văn bản qua mỗi tìm kiếm từ khóa, trƣớc hết chúng ta tìm chủ đề mà chúng ta quan tâm, sau đó xem xét các văn bản liên quan đến chủ đế đó. Ví dụ, xem xét sử dụng các chủ đề để khám phá đầy đủ lịch sử của New York Times. Ở một mức độ rộng, một số trong những chủ đề có thể tƣơng ứng với các phần của tờ báo – chính sách đối ngoại, các vấn đề quốc gia, thể thao. Chúng ta có thể phóng to một chủ đề quan tâm nhất, nhƣ chính sách đối ngoại, để bộc lộ các khía cạnh khác nhau của nó – chính sách đối ngoại ở Trung Quốc, cuộc xung đột ở Trung Đông, mối quan hệ của Mỹ với Nga. Sau đó chúng ta có thể chuyển hƣớng qua thời gian để bộc lộ các chủ đề
18 cụ thể này đã đƣợc thay đổi nhƣ thế nào để theo dõi, ví dụ mức độ thay đổi ở Trung Đông trong vòng 50 năm qua. Và trong tất cả các thăm dò này chúng ta có thể chỉ ra các bài viết ban đầu liên quan tới chủ đề. Nhƣng theo cách này chúng ta không tƣơng tác với lƣu trữ điện tử. Trong khi ngày càng nhiều văn bản có sẵn trực tuyến, đơn giản sức mạnh của con ngƣời không có đủ để đọc và nghiên cứu vấn đề mô tả ở trên. Để kết thúc vấn đề này, các nhà nghiên cứu học máy đã trình bày (phát triển) mô hình chủ đề xác suất [6], để tìm kiếm các thông tin theo chủ đề của các tập tài liệu và mô hình hóa mối quan hệ giữa các chủ đề, những thay đổi trong mỗi chủ đề. Các nhà nghiên cứu sử dụng phƣơng pháp thống kê để phân tích văn bản và sử dụng thông tin thăm dò để ghi nhãn các văn bản. Hầu hết các hệ thống mô hình chủ đề là không giám sát có nghĩa là chúng không yêu cầu bất kỳ dữ liệu nào đã đƣợc gán nhãn. Kết quả là, các hệ thống mô hình chủ đề có giá rẻ và dễ dàng tới cổng thông tin của miền dữ liệu mới. Tuy nhiên một số công việc đã chỉ ra rằng hiệu suất của các hệ thống mô hình chủ đề có thể đƣợc cải thiện bằng cách cung cấp cho chúng với các dữ liệu đƣợc gán nhãn. Trong phần tiếp theo của luận văn nghiên cứu một số loại mô hình chủ đề tiêu biểu mà cho thấy chúng mạnh hơn các phƣơng pháp khác và đƣợc các nhà khoa học sử dụng rộng rãi. 2.2. LDA Latent Dirichlet Allocation ( LDA) đƣợc đề xuất lần đầu tiên bởi Blei và cộng sự năm 2003 [3] và là một trong những mô hình chủ đề phổ biến nhất. Từ LDA, nhiều mô hình chủ đề khác đƣợc xây dựng bằng cách thay đổi một số thành phần của nó. LDA là một mô hình xác suất, trong đó chúng tôi giả sử rằng văn bản đƣợc tạo ra từ một quá trình sinh. LDA là một mô hình "túi từ" điều đó có nghĩa là các từ trong một văn bản đƣợc giả sử là hoán chuyển đƣợc (không tính thứ tự). Chúng ta chỉ xét số lƣợng từ xuất hiện trong một văn bản. Do đó, văn bản trong LDA là các véc tơ của số từ trong một không gian V-chiều trong đó V là kích thƣớc của từ vựng. Mặc dù thứ tự của từ là quan trọng, nhƣng tính toán khó khăn. Bằng cách giả sử rằng các từ đƣợc hoán chuyển trong một văn bản, LDA đơn giản hóa kết quả mô hình nhanh chóng nhƣng là cách mô hình hóa các văn bản. Trong một số mô hình chủ đề giống pLSI, một văn bản chỉ có thể thuộc về một chủ đề.