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
ĐẠ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
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.
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........................................................................................................... 517
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
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ờ
độ 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
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
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 được sử dụng
như là một tiêu chuẩn của trích chọn thông tin để tìm ra những tri thức ẩn trong cơ sở dữ
liệu hay trên các kho dữ liệu trực tuyến. Một ứng dụng thực tế là khi tìm kiếm ảnh từ một
trang Web, nếu xác định hợp lý sự tương đồ
thường bằng độ dài của bản tóm tắt chia cho độ dài của v
ăn bản nguồn. Output của bài
toán là văn bản tóm tắt.
Trước đây, các dạng tóm tắt văn bản đều do con người xử lý, nghĩa là do người đọc
rồi rút ra ý chính, sắp xếp các ý theo một thứ tự hợp lý sau đó dùng lời văn của người tóm
tắt để trình bày lại một cách ngắn gọn nội dung chính của văn bản. Do con người tóm tắt
nên văn bản luôn đảm bảo được tính m
ạch lạc của của nó. Tuy nhiên, cũng vì thế mà văn
bản tóm tắt không tránh khỏi mang dấu ấn chủ quan của người xử lý.
Nhìn chung, các bài toán tóm tắt văn bản cần đảm bảo các yêu cầu như cần phản ánh
trung thành nội dung của văn bản được tóm tắt; có tính bao quát toàn độ nội dung chính
của văn bản; đảm bảo tỷ lệ trích xuất văn bản; tính mạch lạc, tính chặt chẽ củ
a văn bản, ...
Tóm tắt văn bản liên quan tới việc “xử lý” ngôn ngữ. Có thể nói xử lý ngôn ngữ tự
động trên máy tính là một trong những vấn đề khó nhất của Công Nghệ Thông Tin. Khó
là nằm ở chỗ làm sao cho máy hiểu được ngôn ngữ con người, từ việc hiểu nghĩa từng từ
trong mỗi hoàn cảnh cụ thể, đến việc hiểu nghĩa một câu, rồi hiểu cả văn bản. Mấ
u chốt ở
đây là bản chất phức tạp của ngôn ngữ con người, đặc biệt là sự đa nghĩa và nhập nhằng
nghĩa của ngôn ngữ. Thêm nữa, có một khác biệt sâu sắc nữa là con người ngầm hiểu và
dùng quá nhiều common sense (lẽ thường) trong khi rất khó làm cho máy hiểu những điều
này. [2]
19
2.1.2. Phân loại tóm tắt văn bản
Có nhiều cách phân loại tóm tắt văn bản khác nhau tuy nhiên sự phân loại chỉ mang
tính tương đối, phụ thuộc vào việc tóm tắt trên cơ sở nào. Ở đây, khóa luận phân loại tóm
tắt như dựa vào input, output, mục đích tóm tắt [9]. Nếu dựa vào input ta có tóm tắt đa
văn bản, đơn văn bản; tóm tắt miền cụ thể và tóm tắt miền tổng quát; tóm tắt một kiểu văn
bản cụ th
Informative chỉ ra nội dung của thông tin.
- Tóm tắt Query-based hay tóm tắt General. Tóm tắt general mục đích chính là tìm
ra một đoạn tóm tắt cho toàn bộ văn bản mà nội dung của đoạn văn bản sẽ bao quát toàn
bộ nội dung của văn bản đó. Tóm tắt query-based sẽ tóm tắt dựa trên một truy vấ
n người
dùng, tìm ra một đoạn trong văn bản phù hợp với truy vấn đó.
• Tóm tắt trên cơ sở output cũng có nhiều cách phân loại.
- Phân loại phụ thuộc vào ngôn ngữ lựa chọn cho tóm tắt (như tóm tắt tiếng Anh,
tóm tắt tiếng Việt ...).
- Phân loại phụ thuộc vào định dạng của kết quả tóm tắt như table, paragraph, key
words.
- Hay cách phân loại phổ biến là tóm tắt Extract và tóm tắt Abstract.
Extract lập danh sách các
đoạn của văn bản. Extract là một tóm tắt bao gồm toàn bộ
các phần quan trọng được trích ra từ văn bản nguồn.
Abstract là nhóm lại nội dung một cách mạch lạc, súc tích. Abstract là một tóm tắt
ngắn gọn được viết lại từ văn bản nguồn dựa trên các ý chính đã trích rút.
Extraction dễ hơn Abstraction, abstraction cần hiểu và viết lại. Ví dụ minh họa cho
sự khác nhau giữa Extract và Abstract như sau: [18] 21
2.1.3. Tóm tắt văn bản đơn
Đối tượng thực nghiệm của khóa luận là các văn bản đơn. Tóm tắt văn bản đơn cũng
cầm tay; tóm tắt đa phương tiện.
Chiến lược tóm tắt văn bản phổ biến nhất vẫn là trích rút các phần quan trọng (các
câu) trong văn bản rồi sắp xếp chúng theo thứ tự trong văn bản. Bên cạnh đó, tóm tắt văn
22
bản cũng bao gồm cả việc đơn giản hóa câu bằng cách thu ngắn câu lại, xóa đi các phần
không quan trọng trong câu để làm cho văn bản ngắn gọn hơn. Người ta thường sử dụng
các thông tin có trong văn bản để trích rút các phần quan trọng (các câu) trong văn bản.
Cách tiếp cận truyền thống này chủ yếu dựa trên các phương pháp heuristic. Những thông
tin trong văn bản có thể là tần số từ trong văn bản, đầu
đề của văn bản, vị trí câu, cụm từ
gợi ý, … Trích rút các phần quan trọng trong văn bản là kỹ thuật phổ biến được sử dụng
trong tóm tắt văn bản. Trên thế giới cũng đã có nhiều công trình nghiên cứu về tóm tắt
văn bản sử dụng các kỹ thuật này.
2.2.1. Phương pháp Word frequencies
Hans Peter Luhn (1958) được coi là “cha đẻ của lĩnh vực Information Retrieval” và
là tác giả của bài báo “The Automatic Creation of Literature Abstracts – 1958” [15].
Phương pháp của Luhn xuất phát từ một ý tưởng tóm tắt các tài liệu văn học chuyên
ngành. Phương pháp dựa trên cơ sở giả thiết rằng: tần số của từ xuất hiện trong bài báo là
một độ đo hữu ích về nghĩa của từ; vị trí tương đối của các từ có nghĩa trong phạm vi một
câu cũng là
độ đo hữu ích về nghĩa của từ. Tuy nhiên, cơ sở của phương pháp còn bị hạn
chế do khả năng của máy tính không thể biểu diễn được được các thông tin ngữ nghĩa.
Luhn sử dụng tần số từ cho tóm tắt bởi các từ quan trọng thường được lặp đi lặp lại
nhiều lần trong văn bản. Thêm vào đó, thuật toán lại đơn giản, tốn ít th
ời gian xử lý nên
chí phí rẻ. Một chú ý của phương pháp là các dạng khác nhau của cùng một từ được tính
như cùng một từ. Thêm vào đó, việc tính toán tần số của từ sẽ dẫn đến việc, các từ có tần
số quá thấp hoặc quá cao (như “the”, “and”,..). Những từ này đều là các từ không quan
trọng. Giải pháp đặt ra ở đây là với các từ có tần số thấp, có thể dễ dàng loại bỏ bằ
đề mục (title và heading) được xem như là các tóm tắt ngắn gọn
của văn bản. Các câu có chứa nội dung các từ trong đầu đề và tiêu đề là những câu quan
trọng trong văn bản. Một câu chỉ có thể có một title và có thể không có title. Việc xác
định title hiện tại dựa vào nhận xét: Title là câu duy nhất của đoạn đầu tiên. Nghĩa là ta
xét đoạn đầu tiên của văn bản, nếu đây chỉ có một câu thì câu này là title, ngược lại, ta coi
văn bản không có title. Cách xác định này phụ thuộc định dạng của văn bản đầu vào. Các
từ trong title còn được dùng để đánh giá các câu khác trong văn bản, câu nào sát nghĩa với
title, câu đó sẽ đựoc gán trọng số cao hơn so với các câu khác. [1]
Vị trí (location) của câu
Phương pháp đơn giản là dựa trên giả thiết rằng các câu xuất hiện ở đầu văn bản
thường quan trọng hơn các câu xuất hiện ở giữ
a hoặc cuối văn bản. Cách đơn giản nhất để
xây dựng một tóm tắt là luôn chọn câu đầu tiên trong văn bản hoặc chọn k câu đầu tiên
24
trong văn bản, khi mà có thêm yêu cầu tham số tỷ lệ tóm tắt. Mặc dù hiệu suất của
phương pháp này phụ thuộc vào kiểu văn bản và tỉ lệ tóm tắt, phương pháp vẫn có khả
năng nhận dạng khoảng 33% các câu quan trọng trong văn bản [9]
Ngoài ra, các văn bản có xu hướng có cấu trúc phụ thuộc vào kiểu của chúng. Ví dụ
như theo quy tắc báo chí, văn bản thường chia làm ba phần: Phần giới thiệu, ph
ần chính,
phần tóm lược lại. Trong văn bản kiểu này:
- Các câu thuộc đề tài thường có xu hướng xuất hiện ở vị trí bắt đầu của các đoạn.
- Các câu quan trọng có xu hướng xuất hiện ở cuối của văn bản.
Từ ví dụ trên, phương pháp trích rút phần quan trọng trong văn bản sử dụng thông
tin vị trí câu đòi hòi: Các câu quan trọng được đặt ở các vị trí “phụ thuộc vào ki
ểu văn
bản”; những vị trí này có thể đuợc tìm thấy tự động thông qua việc huấn luyện [19].
Tần số từ trong văn bản
Các câu quan trọng chứa nội dung các từ xuất hiện thường xuyên trong văn bản. Các
a tài liệu.
- Các từ được cho một trọng số title dương nếu chúng xuất hiện trong bảng Title này.
- Các từ Title được cho trọng số lớn hơn các từ Heading.
• Trọng số Location của câu:
- Các câu của đoạn đầu tiên được đánh dấu trọng số O
1
- Các câu của đoạn cuối cùng đựoc đánh dấu trọng số O
2
- Câu đầu tiên trong một đoạn được đánh dấu trọng số O
3
- Câu cuối cùng của đoạn được dánh dấu trọng số O
4
Thứ tự trọng số của câu: O1 + O2 + O3 + O4
Đánh giá phương pháp này, kết quả chỉ ra rằng việc tổ hợp cả bốn cách trích rút của
Edmundson không cho hiệu suất tốt nhất.
Từ hình 2, có thể dễ dàng thấy phương pháp cho kết quả tốt nhất là khi tổ hợp ba
thông tin: Cue, Title và Location. Phương pháp tổ hợp này có giá trị trung bình cao nhất,
xấp xỉ 55%.
Copyright: Tài liệu đại học ©