TAILIEUCHUNG - Báo cáo khoa học: "A Class of Submodular Functions for Document Summarization"

We design a class of submodular functions meant for document summarization tasks. These functions each combine two terms, one which encourages the summary to be representative of the corpus, and the other which positively rewards diversity. Critically, our functions are monotone nondecreasing and submodular, which means that an efficient scalable greedy optimization scheme has a constant factor guarantee of optimality. | A Class of Submodular Functions for Document Summarization Hui Lin Dept. of Electrical Engineering University of Washington Seattle WA 98195 USA hlin@ Jeff Bilmes Dept. of Electrical Engineering University of Washington Seattle Wa 98195 UsA bilmes@ Abstract We design a class of submodular functions meant for document summarization tasks. These functions each combine two terms one which encourages the summary to be representative of the corpus and the other which positively rewards diversity. Critically our functions are monotone nondecreasing and submodular which means that an efficient scalable greedy optimization scheme has a constant factor guarantee of optimality. When evaluated on DuC 2004-2007 corpora we obtain better than existing state-of-art results in both generic and query-focused document summarization. Lastly we show that several well-established methods for document summarization correspond in fact to submodular function optimization adding further evidence that submodular functions are a natural fit for document summarization. 1 Introduction In this paper we address the problem of generic and query-based extractive summarization from collections of related documents a task commonly known as multi-document summarization. We treat this task as monotone submodular function maximization to be defined in Section 2 . This has a number of critical benefits. On the one hand there exists a simple greedy algorithm for monotone submodular function maximization where the summary solution obtained say S is guaranteed to be almost as good as the best possible solution say Sopt according to an objective F. More precisely the greedy algorithm is a constant factor approximation to the cardinality constrained version of the problem so that 510 F S 1 - 1 e F Sopt - Sopt . This is particularly attractive since the quality of the solution does not depend on the size of the problem so even very large size problems do well. It is .

• Báo cáo khoa học
• A Class of Submodular Functions
• Document Summarization
• Hui Lin
• báo cáo khoa học
• báo cáo ngôn ngữ
• ngôn ngữ tự nhiên
• Bài giảng Xử lý ngôn ngữ tự nhiên
• Xử lý ngôn ngữ tự nhiên
• Kỹ thuật lập trình
• Mô hình ngôn ngữ
• Mô hình n gram
• Dịch máy
• Phương pháp dịch máy
• Hiểu ngôn ngữ
• Phân loại tin tự động
• Tạo chí tin học
• Điều khiển học
• Truy vấn ngôn ngữ tự nhiên
• Phép dịch truy vấn ngôn ngữ tự nhiên
• Truy vấn SQL
• Văn phạm ngữ nghĩa
• Xử lý nhập nhằng ngữ nghĩa
• Xử lý ngữ nghĩa
• Phân tích ngữ nghĩa
• Biểu diễn vị từ
• Thuộc tính về sự kiện
• Thuộc tính về sự kiện
• Xử lý ngôn ngữ
• Natural Language Processing
• Ngôn ngữ lập trình
• Nhập nhằng cấu trúc
• Tri thức về ngôn ngữ
• Mô hình ngôn ngữ Google Book N grams
• Mô hình ngôn ngữ KenLM
• Phương pháp làm mịn
• Bài toán PTCP
• Phân tích cú pháp
• Cấu trúc ngữ pháp
• Phân tích cú pháp xác suất
• CKY kết hợp xác suất
• Văn phạm phi ngữ cảnh xác suất
• Hình thái học
• Gán nhãn từ loại
• Ngôn ngữ tự nhiên trong dịch máy
• Hệ thống dịch máy
• Phương pháp xây dựng bảng từ
• Tác từ
• Conditional random fields
• Nhận dạng thực thể có tên
• Đối tượng vật lý trừu tượng
• Phân lớp văn bản
• Biểu diễn nhị phân
• Ma trận từ văn bản
• Wolfram Alpha
• Trích rút thông tin
• Phương pháp Snowball