Khóa luận Độ tương đồng ngữ nghĩa giữa hai câu và ứng dụng trong tóm tắt văn bản

1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Hoàng Minh Hiền ĐỘ TƯƠNG ĐỒNG NGỮ NGHĨA GIỮA HAI CÂU VÀ ỨNG DỤNG TRONG TÓM TẮT VĂN BẢN KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2008 2 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Hoàng Minh Hiền ĐỘ TƯƠNG ĐỒNG NGỮ NGHĨA GIỮA HAI CÂU VÀ ỨNG DỤNG TRONG TÓM TẮT VĂN BẢN KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: PGS TS Hà Quang Thụy Cán bộ đồng hướng dẫn: Thạc Sỹ Đặng Thanh Hải HÀ NỘI - 2008 3 Lời cảm ơn Tôi xin gửi lời cảm ơn và biết ơn sâu sắc nhất tới Phó Giáo sư Tiến sĩ Hà Quang Thụy và Thạc sỹ Đặng Thanh Hải đã chỉ bảo và hướng dẫn tận tình cho tôi trong suốt quá trình nghiên cứu Khoa học và quá trình thực hiện khoá luận này. Tôi chân thành cảm ơn các thầy, cô đã tạo cho tôi những điều kiện thuận lợi để học tập và nghiên cứu tại trường Đại học Công Nghệ. Tôi cũng xin gửi lời cảm ơn tới các anh chị, các bạn sinh viên trong nhóm nghiên cứu “Khai phá dữ liệu và khám phá tri thức” đã giúp đỡ, ủng hộ và động viên tôi trong quá trình nghiên cứu và làm khoá luận. Đặc biệt, tôi xin cảm ơn Cử nhân Trần Mai Vũ, Nghiên cứu sinh Nguyễn Cẩm Tú và Sinh viên Lê Diệu Thu, những người đã hỗ trợ tôi rất nhiều về kiến thức chuyên môn, giúp tôi có thể hoàn thành khóa luận. Cuối cùng, tôi muốn gửi lời cảm ơn và biết ơn vô hạn tới bố, mẹ, anh trai, tất cả bạn bè và những người thân yêu của tôi. Xin chân thành cảm ơn! Sinh viên Hoàng Minh Hiền 4 Tóm tắt nội dung Hiện nay, tóm tắt văn bản là một bài toán có tính ứng dụng thực tiễn cao. Tóm tắt văn bản nhận được sự nhiều sự quan tâm nghiên cứu của nhiều nhà khoa học, của các hội nghị quốc tế như hội nghị DUC (Document Understanding Conference), hội nghị Coling/ACL (Computational Linguistics/Association for Computational Linguistics), của các trung tâm nghiên cứu như IBM, Microsoft… Khóa luận với đề tài “Độ tương đồng ngữ nghĩa giữa hai câu và ứng dụng trong bài toán tóm tắt văn bản” tập trung nghiên cứu vào các phương pháp tóm tắt văn bản; độ tương đồng câu và các phương pháp để tính toán độ tương đồng câu. Từ đó, trên cơ sở về một số kết quả nghiên cứu đã có về độ đo tương đồng câu và về Hidden Topic, khóa luận đề xuất một mô hình tóm tắt văn bản đơn có sử dụng Hidden Topic để tính toán độ tương đồng ngữ nghĩa giữa hai câu. 5 Mục lục Tóm tắt nội dung ............................................................................................................... 4 Mục lục ............................................................................................................................... 5 Danh sách bảng.................................................................................................................. 7 Danh sách hình vẽ.............................................................................................................. 8 Bảng ký hiệu và từ viết tắt ................................................................................................ 9 Mở đầu.............................................................................................................................. 10 Chương 1. Tổng quan về tóm tắt văn bản và độ tương đồng câu............................... 12 1.1. Đặt vấn đề......................................................................................................12 1.2. Nền tảng kiến thức ........................................................................................13 1.2.1. Data Mining .......................................................................................13 1.2.2. Text Mining .......................................................................................13 1.2.3. Web Mining .......................................................................................14 1.3. Tóm tắt văn bản.............................................................................................15 1.4. Độ tương đồng giữa hai câu ..........................................................................16 Chương 2. Bài toán tóm tắt văn bản và một số phương pháp tóm tắt văn bản ........ 18 2.1. Bài toán tóm tắt văn bản................................................................................18 2.1.1. Định nghĩa tóm tắt .............................................................................18 2.1.2. Phân loại tóm tắt văn bản...................................................................19 2.1.3. Tóm tắt văn bản đơn ..........................................................................21 2.2. Các phương pháp tóm tắt văn bản đơn..........................................................21 2.2.1. Phương pháp Word frequencies.........................................................22 2.2.2. Phương pháp của Edmundson ...........................................................23 2.2.3. Tóm tắt văn bản tự động sử dụng trích chọn câu hai bước................26 6 Chương 3. Độ tương đồng câu và phương pháp tính độ tương đồng câu.................. 32 3.1. Độ tương đồng...............................................................................................32 3.2. Độ tương đồng câu ........................................................................................32 3.3. Phương pháp để đo độ tương đồng câu.........................................................33 3.3.1. Phương pháp tính độ tương đồng câu sử dụng WordNet corpus.......33 3.3.2. Phương pháp tính độ tương đồng câu sử dụng Hidden Topic ...........39 Chương 4. Đề xuất mô hình tóm tắt và kết quả thực nghiệm ..................................... 46 4.1. Đề xuất mô hình tóm tắt................................................................................46 4.2. Thiết kế mô hình thử nghiệm ........................................................................47 4.3. Kết quả thực nghiệm .....................................................................................47 Kết luận và hướng phát triển của khóa luận ................................................................ 50 Tài liệu tham khảo........................................................................................................... 51 7 Danh sách bảng Bảng 1. Các kết quả so sánh các độ đo...............................................................................37 Bảng 2. Trọng số của từng câu trong văn bản [không dùng Hidden Topic] ......................48 Bảng 3. Trọng số của từng câu trong văn bản [dùng Hidden Topic] .................................49 8 Danh sách hình vẽ Hình 1. Mô hình chung của một hệ thống tóm tắt văn bản ............................................... 15 Hình 2. Giá trị trung bình của các phương pháp ............................................................... 26 Hình 3. Hệ thống tóm tắt sử dụng phương pháp trích chọn câu hai bước......................... 27 Hình 4. So sánh giữa phương pháp Two-step và các phương pháp khác (Title) .............. 31 Hình 5. So sánh giữa phương pháp Two-step và các phương pháp khác ( không sử dụng Title) .................................................................................................................................. 31 Hình 6. Lược đồ tính toán độ tương đồng câu .................................................................. 34 Hình 7. Hệ thống cây phân cấp ngữ nghĩa ........................................................................ 36 Hình 8. Mô hình biểu diễn của LDA (Các khối vuông biểu diễn quá trình lặp)............... 40 Hình 9. Mô hình sinh cho LDA......................................................................................... 41 Hình 10. Quá trình khởi tạo lấy mẫu lần đầu .................................................................... 42 Hình 11. Quá trình khởi tạo lấy mẫu lại ............................................................................ 43 Hình 12. Quá trình đọc các tham số đầu ra ....................................................................... 44 Hình 13. Nội dung một văn bản đơn tiếng Việt ................................................................ 47 9 Danh sách các từ viết tắt WAP : Wireless Application Protocol PDA : Personal digital assistant SMS : Short Message Service LDA : Latent Dirichlet Allocation IR : Information Retrieval TF : Term Frequency IDF : Inverted document frequency 10 Mở đầu Dữ liệu trên Internet được sinh ra liên tục mỗi ngày, lượng thông tin khổng lồ đó khiến người dùng trở nên bối rối do không đủ thời gian đọc tất cả văn bản. Tóm tắt văn bản tự động hiện đang là một bài toán được sự quan tâm nghiên cứu của nhiều nhà khoa học. Tóm tắt văn bản có thể được ứng dụng để tóm tắt các bản tin với định dạng WAP hoặc SMS cho các thiết bị PDA, điện thoại di động. Trong máy tìm kiếm, ứng dụng tóm tắt văn bản sẽ đưa ra một đoạn mô tả của kết quả tìm kiếm. Người dùng dựa vào đó để chọn nhưng kết quả phù hợp với mong muốn của mình... Những ứng dụng đa dạng và phong phú của tóm tắt văn bản khẳng định sự cần thiết của việc xây dựng một hệ thống tóm tắt văn bản tự động hiệu quả. Mục tiêu chính của khóa luận là tập trung vào việc khảo sát, nghiên cứu các phương pháp giải quyết bài toán tóm tắt văn bản một cách hiệu quả. Để tiếp cận mục tiêu này, khóa luận giới thiệu kết quả nghiên cứu của báo cáo [4]: phương pháp tính độ tương đồng câu sử dụng WordNet corpus; Đồng thời, khóa luận nghiên cứu, đề xuất phương pháp tính toán độ tương đồng câu sử dụng mô hình topic ẩn. Ưu điểm của phương pháp này là làm tăng tính ngữ nghĩa trong tính toán độ tương đồng câu mà không cần dùng tới một mạng ngữ nghĩa hay một corpus nào khác. Nội dung của khóa luận được chia thành các chương như sau: Chương 1. Tổng quan về bài toán tóm tắt văn bản và độ tương đồng câu: Đề cập tới nhu cầu của ứng dụng tóm tắt văn bản, các nền tảng kiến thức của bài toán tóm tắt. Phần này cũng giới thiệu những nội dung cơ bản nhất của bài toán tóm tắt văn bản và độ tương đồng ngữ nghĩa giữa hai câu. Chương 2. Bài toán tóm tắt văn bản và một số phương pháp tóm tắt văn bản: Trình bày cụ thể về bài toán tóm tắt văn bản bao gồm định nghĩa tóm tắt, phân loại tóm tắt, cách đánh giá một văn bản tóm tắt và một số phương pháp tóm tắt văn bản. Chương 3. Độ đo tương đồng câu và phương pháp tính độ tương đồng câu. Chương này giới thiệu về độ tương đồng, độ tương đồng câu và hai phương pháp khác nhau để tính độ tương đồng câu: Phương pháp tính độ tương đồng câu sử dụng WordNet corpus 11 đã được trình bày trong báo cáo nghiên cứu khoa học [4] và phương pháp tính độ tương đồng câu sử dụng Hidden Topic. Chương 4. Đề xuất và thực nghiệm: Trình bày những đề xuất của mô hình tóm tắt văn bản sử dụng Hidden Topic và những kết quả đánh giá thử nghiệm của mô hình mà luận áp dụng cho bài toán tóm tắt văn bản. Chương 5. Kết luận và hướng phát triển khóa luận: tóm lược lại những điểm chính của khóa luận, chỉ ra những điểm cần khắc phục, đồng thời đưa ra hướng nghiên cứu trong thời gian tới. 12 Chương 1. Tổng quan về tóm tắt văn bản và độ tương đồng câu 1.1. Đặt vấn đề Tóm tắt văn bản thuộc lĩnh vực xử lý văn bản (text processing) và cũng là một bài toán tiêu biểu của xử lý ngôn ngữ tự nhiên. Xử lý văn bản cũng như text mining, Web mining đều dựa trên các kỹ thuật của xử lý ngôn ngữ tự nhiên, mà quan trọng là việc hiểu và dùng tri thức về ngôn ngữ ở các mức độ khác nhau [14]. Đối tượng xử lý của bài toán tóm tắt văn bản có thể là một văn bản hay nhiều văn bản. Do sự phát triển của Internet, thông tin được sinh ra liên tục mỗi ngày, khối lượng dữ liệu trên Web rất lớn, do đó vấn đề trùng lặp thông tin thường xuyên xảy ra. Giải pháp cho vấn đề này đó là tóm tắt văn bản tự động. Việc tóm tắt sẽ giúp người dùng tiết kiệm thời gian đọc, cải thiện tìm kiếm cũng như tăng hiệu quả indexing cho search engine. Tóm tắt văn bản được ứng dụng ngày một rộng rãi. Tóm tắt văn bản có thể ứng dụng trong tóm tắt các bản tin với định dạng WAP hoặc SMS cho các thiết bị PDA, điện thoại di động. Trong máy tìm kiếm, ứng dụng tóm tắt văn bản sẽ đưa ra một đoạn mô tả của kết quả tìm kiếm. Người dùng dựa vào đó để chọn nhưng kết quả phù hợp với mong muốn của mình. Hiện nay, tóm tắt văn bản được sự quan tâm đặc biệt trong các hội nghị quốc tế như hội nghị DUC (Document Understanding Conference),... hoặc các trung tâm nghiên cứu của Microsoft, IBM ... Chính những ứng dụng rộng rãi và nhu cầu thực tiễn trên là động lực để khóa luận tập trung nghiên cứu về bài toán tóm tắt văn bản, các phương pháp tóm tắt văn bản. Khóa luận cũng đã đề đề xuất phương pháp tính độ tương đồng ngữ nghĩa giữa hai câu để giải quyết bài toán này. 13 1.2. Nền tảng kiến thức 1.2.1. Data Mining Khai phá dữ liệu là một khái niệm ra đời vào những năm cuối của thập kỷ 1980. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có giá trị tiềm ẩn trong các tập dữ liệu lớn (các kho dữ liệu). Nó là một bước trong quá trình tìm kiếm tri thức. Những công cụ data mining có thể phát hiện những xu hướng trong tương lai, các tri thức mà data mining mang lại cho các doanh nghiệp có thể ra các quyết định kịp thời và trả lời những câu hỏi trong lĩnh vực kinh doanh mà trước đây tốn nhiều thời gian để xử lý. Với ưu điểm trên, Data mining đã chứng tỏ được tính hữu dụng của nó trong môi trường kinh doanh đầy tính cạnh tranh ngày nay và được ứng dụng rộng rãi trong các lĩnh vực thương mại, tài chính, điều trị y học, giáo dục, viễn thông..v.v. Mục đích của khai phá dữ liệu là các tri thức chiết xuất sẽ được sử dụng cho lợi ích cạnh tranh trên thương trường và các lợi ích trong nghiên cứu khoa học. Do đó, có thể coi mục đích chính của khai phá dữ liệu sẽ là mô tả (description) và dự đoán (prediction). Dự đoán liên quan đến việc sử dụng các biến hoặc các trường trong cơ sở dữ liệu để chiết xuất ra các mẫu là các dự đoán những giá trị chưa biết hoặc những giá trị trong tương lai của các biến đáng quan tâm. Mô tả tập trung vào việc tìm kiếm các mẫu mô tả dữ liệu mà con người có thể hiểu được. Để đạt được hai mục đích này, nhiệm vụ chính của khai phá dữ liệu bao gồm: phân lớp, phân cụm, tóm tắt, … Từ đó, có thể thấy rõ ràng rằng tóm tắt cũng là một phần quan trọng của data mining. 1.2.2. Text Mining Trong [5], tóm tắt văn bản cũng là một trong những bài toán chủ yếu của lĩnh vực Text Mining. Thực tế hiện nay, một phần quan trọng của các thông tin sẵn có được lưu trữ trong cơ sở dữ liệu văn bản (hoặc cơ sở dữ liệu tài liệu) gồm tập hợp rất lớn các tài liệu từ nhiều nguồn khác nhau, như các bài báo mới, các bài báo nghiên cứu, sách, thư viện điện tử, các thông điệp thư điện tử hay các trang Web. Các cơ sở dữ liệu văn bản phát triển nhanh do sự tăng lên của lượng thông tin điện tử có sẵn, như các xuất bản điện tử, các loại khác của tài liệu điện tử, thư điện tử, và World Wide Web (có thể xem như một lượng cơ sở dữ liệu văn bản lớn, liên kết và động). 14 Hầu hết các thông tin trong chính phủ, công nghiệp, thương mại và các viện nghiên cứu đều được lưu trữ ở dạng điện tử, theo kiểu cơ sở dữ liệu văn bản. Số lượng tài liệu điện tử này phát triển với tốc độ chóng mặt gây cho con người những khó khăn trong việc tiếp nhận nội dung chính của chúng. Các kỹ thuật tìm kiếm thông tin truyền thống trở nên không tương xứng với lượng dữ liệu văn bản ngày càng lớn. Người dùng không biết bên trong tài liệu chứa gì, thật khó để đưa ra câu truy vấn hiệu quả cho việc phân tích và trích rút các thông tin có ích từ dữ liệu. Người sử dụng cần các công cụ so sánh các tài liệu khác nhau, xếp hạng độ quan trọng và độ liên quan của các tài liệu, hoặc tìm các mẫu và các xu hướng qua nhiều tài liệu. Do đó, việc tính độ tương đồng trong văn bản, độ tương đồng giữa các văn bản, tóm tắt văn bản ... trở nên ngày càng phổ biến và là nội dung cần thiết trong khai phá text. 1.2.3. Web Mining Web cũng chứa một lượng thông tin hyperlink, thông tin truy cập Web và các thông tin có ích, cung cấp nguồn tài nguyên dồi dào cho data mining. Kích thước của Web lên đến hàng trăm Terabytes và vẫn đang phát triển rất nhanh. Web được xem như một thư viện điện tử khổng lồ. Tuy nhiên, số lượng tài liệu khổng lồ trong thư viện này lại không được sắp xếp theo bất cứ thứ tự cụ thể nào, không có chỉ mục, tiêu đề, tác giả, bìa trang, bảng nội dung, ... Đây chính là khó khăn để tìm kiếm thông tin mong muốn trong thư viện. Không chỉ có Web phát triển nhanh, mà thông tin của nó cũng luôn được cập nhật. Các tin tức, thông tin thị trường chứng khoán, thời tiết, thể thao, shopping, quảng cáo, và một số các trang Web khác cũng được cập nhật thường xuyên trên Web. Thông tin liên kết và các bản ghi truy cập cũng được cập nhật liên tục. Trong [12], 99% các thông tin trên mạng là không có ích đối với 99% người dùng Web. Thực tế, mỗi người dùng thường chỉ quan tâm một phần rất nhỏ của Web, phần còn lại, họ không mấy quan tâm. Làm thế nào để những phần của Web mà người dùng quan tâm được tìm thấy? Làm thế nào có thể tìm ra những trang Web chất lượng cao trong một topic cụ thể? Những thách thức này là động lực thúc đẩy các nghiên cứu về Web mining cũng như hệ thống tóm tắt văn bản tự động. 15 1.3. Tóm tắt văn bản Trong nhiều năm qua, có rất nhiều dự án, công trình nghiên cứu về bài toán tóm tắt văn bản. Và cách tiếp cận chủ yếu của bài toán này được chia thành hai hướng chính: một là cách tiếp cận theo hướng trích lược (shallower approaches), hai là cách tiếp cận theo hướng hiểu sâu (abstract). [18] Chiến lược tóm tắt văn bản phổ biến nhất vẫn là trích chọn câu. Các phương pháp tóm tắt văn bản truyền thống thường sử dụng phương pháp NLP (linguistic) và các phương pháp thống kê để trích rút ra các câu quan trọng. Nhưng một vài vấn đề xuất hiện trong cả hai phương pháp đối với tóm tắt văn bản. Mặc dù hiệu suất cao, phương pháp NLP có có một vài khó khăn trong việc yêu cầu sử dụng các công cụ phân tích ngôn ngữ chất lượng cao như phân tích bài luận và các nguồn ngôn ngữ như WordNet, Lexcial Chain, không gian vector ngữ cảnh (Context Vector Space); chúng là các nguồn tài nguyên có ích cho hệ thống tóm tắt văn bản nhưng một điểm yếu của chúng là mất quá nhiều thời gian và chi phí để xây dựng. Mặt khác, các phương pháp thống kê dễ hiểu và thực hiện, tuy nhiên nó bỏ qua nội dung ngữ nghĩa của các từ và các thành phần tiềm năng của chúng trong các cụm từ multi-word (multi-word phrases). Do đó, nhìn chung thì các phương pháp thống kê chỉ ra kết quả chính xác thấp. [13] Mô hình chung của một hệ tóm tắt văn bản dựa trên cách tiếp cận của Mani&Maybury gồm có ba bước: Analysis, Transformation, Synthesis. [18] Hình 1. Mô hình chung của một hệ thống tóm tắt văn bản 16 Analysis Bước này sẽ phân tích văn bản đầu vào để đưa ra những mô tả bao gồm các thông tin dùng để tìm kiếm, đánh giá các đơn vị ngữ liệu quan trọng cũng như các tham số đầu vào cho việc tóm tắt. Thông qua bước này, các câu quan trọng, đặc trưng, chứa các ý chính của văn bản sẽ được trích chọn. Transformation Bước biến đổi sẽ biến đổi từng câu quan trọng thu được từ bước phân tích trước để giản lược các câu này. Dựa trên các dấu hiệu có thể rút gọn, về cấu trúc ngữ pháp hoặc ngữ nghĩa, mỗi câu sẽ được giảm kích thước mà vẫn giữ được phần lớn ý mà nó hàm chứa trước khi rút gọn. Synthesis Từ các câu quan trọng được được chọn ra ở bước phân tích, được rút ngắn ở bước biến đổi, bước synthesis sẽ liên kết chúng lại thành đoạn theo một thứ tự nào đó hoặc theo cấu kết ngữ pháp rồi hiển thị phù hợp với yêu cầu người dùng. [1] 1.4. Độ tương đồng giữa hai câu Độ tương đồng ngữ nghĩa giữa các câu đóng một vai trò ngày càng quan trọng trong nghiên cứu Text mining, Web mining và xử lý ngôn ngữ tự nhiên. Nó cũng