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.
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
53 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 3355 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Đề tài Độ tương đồng ngữ nghĩa giữa hai câu và ứng dụng trong tóm tắt văn bản, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trê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 đồng ngữ nghĩa giữa câu truy vấn với các đoạn
text ngắn bao quanh ảnh thì hệ thống tìm kiếm sẽ đưa ra kết quả đáp ứng tốt hơn yêu cầu
người dùng. Vấn đề tính toán độ tương đồng giữa các câu trong văn bản với nhau hoặc
với câu chủ đề của văn bản/nhóm văn bản nhận được sự quan tâm đặc biệt trong các hội
nghị khoa học quốc tế, đặc biệt trong các hội nghị thường niên về hiểu văn bản
(Document Understanding Workshop - DUC)1. Việc xây dựng một độ đo chuẩn xác để
thể hiện được mối quan hệ tương đồng về ngữ nghĩa giữa các câu sẽ làm cho các ứng
dụng trở nên “thông minh” hơn, đặc biệt trên Web [22][23]. Tồn tại một số phương pháp
1 Các hội thảo khoa học DUC diễn ra hàng năm từ năm 2001 đến nay, mà hai năm gần đây có DUC 2006,
June 8-9, 2006, New York Marriott, New York USA và DUC 2007, April 26-27, 2007, Rochester, New
York USA.
17
tính toán độ tương đồng giữa các câu, mà điển hình là phương pháp dựa trên tính toán
thống kê và phương pháp dựa trên quan hệ ngữ nghĩa giữa tập các từ trong hai câu đó
[9][16].
18
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
2.1. Bài toán tóm tắt văn bản
2.1.1. Định nghĩa tóm tắt
Tóm tắt văn bản là quá trình làm giảm đi độ dài hoặc độ phức tạp của một văn bản
mà không mất đi nội dung chính của văn bản [18].Bài toán tóm tắt văn bản có đầu vào là
văn bản nguồn và một tham số được gọi là tỷ lệ trích xuất. Tỷ lệ trích xuất của văn bản
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ể... Dựa vào mục đích thì tóm tắt được chia thành tóm tắt generic, query-based;
tóm tắt indicative và information; hay tóm tắt background. Dựa vào output thì chia ra
thành hai kiểu là extract và abstract.
• Tóm tắt trên cơ sở input sẽ trả lời cho câu hỏi “Cái gì sẽ được tóm tắt”. Các chia
này sẽ cho ta nhiều cách phân loại con khác nhau. Cụ thể như:
- Kiểu văn bản (bài báo, bản tin, thư, báo cáo …). Với cách phân loại này, tóm tắt
văn bản là bài báo sẽ khác với tóm tắt thư, tóm tắt báo cáo khoa học do những đặc trưng
văn bản quy định.
- Định dạng văn bản: tóm tắt văn bản free-form, tóm tắt văn bản có cấu trúc. Với
văn bản có cấu trúc, tóm tắt văn bản thường sử dụng một mô hình học đã xây dựng từ
trước.
- Kích thước nguồn: tóm tắt đa văn bản, tóm tắt văn bản đơn. Một vài hệ thống sẽ
tạo ra một bản tóm tắt dựa trên một tài liệu đơn, trong khi một vài hệ thống khác có thể sử
dụng nhiều nguồn tài liệu. Những hệ thống này được biết như các hệ thống multi-
document summarization. Tóm tắt nhiều nguồn văn bản dựa trên việc nối nhiều văn bản
với nhau.
- Miền cụ thể (y tế) hay tổng quát.
• Tóm tắt trên cơ sở mục đích thực chất là làm rõ cách tóm tắt, mục đích tóm tắt là
gì, tóm tắt phục vụ đối tượng nào ...
- Nếu phụ thuộc vào đối tượng đọc tóm tắt thì tóm tắt cho chuyên gia khác cách tóm
tắt cho các đối tượng đọc thông thường.
- Tóm tắt sử dụng trong IR sẽ khác với tóm tắt phục vụ cho việc sắp xếp.
20
- Dựa trên mục đích tóm tắt, còn có thể chia ra thành tóm tắt Indicative và tóm tắt
Informative. Tóm tắt Indicative chỉ ra loại của thông tin, ví dụ như là “alert”. Còn tóm tắt
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
giống như các bài toán tóm tắt khác, là một quá trình tóm tắt tự động với đầu vào là một
văn bản, đầu ra là một đoạn mô tả ngắn gọn nội dung chính của văn bản đầu vào đó. Tóm
tắt văn bản đơn là bước đệm cho việc xử lý, tóm tắt đa văn bản và các bài toán tóm tắt
phức tạp hơn.
Văn bản đơn có thể là một trang Web, một bài báo, hoặc một tài liệu với định dạng
xác định (ví dụ : .doc, .txt)… Những phương pháp tóm tắt văn bản ra đời đầu tiên đều là
các phương pháp tóm tắt cho văn bản đơn. Chẳng hạn như với input là một trang Web, có
thể tóm tắt sử dụng thêm câu truy vấn để đưa ra nội dung của bản tóm tắt. Cách làm này
có ưu điểm là văn bản kết quả sẽ cho nội dung gần với mong muốn của người sử dụng
hơn. Quá trình tóm tắt cụ thể sẽ xét mối liên hệ, sự tương đồng giữa các thành phần trong
văn bản với câu truy vấn để tìm ra các phần quan trọng trong văn bản. Tuy nhiên, với tóm
tắt một văn bản đơn không sử dụng truy vấn, quá trình tóm tắt sẽ xét sự tương đồng giữa
các thành phần của văn bản với nhau. Điều này dẫn đến một vấn đề là chưa thể kết luận
ngay các thành phần quan trọng của văn bản để có thể trích rút, đưa vào tóm tắt.
2.2. Các phương pháp tóm tắt văn bản đơn
Những năm 50-70, tóm tắt văn bản chủ yếu dựa vào các kỹ thuật thống kê để tóm tắt
các văn bản khoa học.
Những năm 80, người ta sử dụng trí tuệ nhân tạo để tóm tắt các văn bản ngắn, các
bản tin, các bài tường thuật. Đến những năm 90, các hệ thống lai (hybrid system) được sử
dụng trong tóm tắt bản tin và một vài văn bản khoa học. Trong thực tế, một hệ thống tóm
tắt có thể tổ hợp và sử dụng nhiều phương pháp. Các phương pháp này được gọi là
phương pháp lai, ví dụ một phương pháp một phương pháp có thể là tổ hợp của các kỹ
thuật thống kê. [9]
Từ năm 2000 đến nay, tóm tắt tập trung vào các lĩnh vực như tóm tắt đa văn bản
(các tin tức, trang Web, email, văn bản luật, y tế, …), sinh Headline; tóm tắt hỗ trợ các
thiết bị 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ằng cách
thiết lập một ngưỡng tần số nhỏ nhất. Với những từ phổ biến (có tần số cao), loại bỏ bằng
cách thiết lập một ngưỡng tần số lớn nhất, so sánh các từ tần số cao với một danh sách từ
phổ biến. Đây cũng chính là việc loại bỏ các từ dừng ( như “the”, “a”, “for”, “is” … ).
Để tính tần số của từ quan trọng, Luhn tính phấn phối của mỗi từ trong tài liệu (tf)
và phân phối của từ ở trong corpus (idf – inverted document frequency).
NUMDOC: số tài liệu trong corpus
23
NUMDOC(term): số tài liệu mà có term xuất hiện.
Nếu tf(term)*idf(term) vượt một ngưỡng xác định, các cụm từ khóa được tìm thấy
và được gán trọng số. Các câu với tổng trọng số cụm cao nhất được chọn.
2.2.2. Phương pháp của Edmundson
Phương pháp tóm tắt của Edmundson [11] dựa vào kỹ thuật trích rút các phần quan
trọng văn bản sử dụng tổng hợp bốn thông tin gồm: các cụm từ gợi ý, từ khóa, title và vị
trí của câu. Đây chính là cơ sở của phương pháp.
Cụm từ gợi ý (cue) trong văn bản
Có các cụm từ gợi ý có thể hoàn toàn liên quan hoặc không liên quan tới các câu
quan trọng. Ví dụ với các cụm từ ‘In this paper, ‘In conclusion’, ‘our work’,… thường
theo sau chúng chính là phần quan trọng trong văn bản. Hoặc như cụm từ ‘for example’
thường chỉ ra phần không quan trọng của văn bản.
Tiêu đề (title) của văn bản
Giả thuyết của cách trích rút này là “tiêu đề của văn bản thường chỉ ra nội dung của
văn bản đó”. Vì thế các từ trong tiêu đề giúp tìm ra nội dung có liên quan [11].
Edmundson là người đầu tiên chỉ ra các từ trong title và heading thường xuất hiện nhiều
trong các câu quan trọng hơn các câu không quan trọng.
Các câu tiêu đề và đề 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
từ xuất hiện thường xuyên trong văn bản có xu hướng chỉ ra chủ đề của văn bản. Mức độ
quan trọng của từ được tính toán trên cơ sở tần số của chúng (tf-term frequency). Một
mục từ xuất hiện trong văn bản nhiều hơn một ngưỡng nào đó thì được cọi là từ quan
trọng. Mức độ quan trọng của các câu được tính toán dựa trên cơ sở tầm quan trọng của
các từ mà câu đó chứa. [15]
Từ những cơ sở trên, Edmundson tính trọng số của một câu là một tổ hợp tuyến tính
của các trọng số nhận được từ bốn phương pháp trích rút các phần quan trọng:
Các câu có trọng số cao nhất sẽ được đưa vào tóm tắt. Trong phương trình trên:
• Các tham số được điều chỉnh phù hợp bằng cách sử dụng tập huấn luyện.
• Trọng số Cue của câu: Σ (Trọng số Cue của mỗi từ trong câu)
- So sánh mỗi từ trong câu với từ điển Cue.
- Gán tất cả các từ có lợi với trọng số b>0, các từ nhiễu với trọng số s<0, các từ Null
với n=0
)(.)(.)(.)(.)( SPositionSKeywordSCueSTitleSWeight δγβα +++=
25
• Trọng số Key của câu: Σ (Trọng số Key của mỗi từ trong câu)
Trọng số Key của mỗi từ xác định dựa theo phương pháp của Luhn[15], tính tần số
của các từ.
• Trọng số Title của câu: Σ (Trọng số Title của mỗi từ trong câu)
Để xác định trọng số Title của mỗi từ trong câu:
- Tạo một bảng Title bao gồm tất cả các từ non-Null trong title, subtitle và heading
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ố O1
- Các câu của đoạn cuối cùng đựoc đánh dấu trọng số O2
- Câu đầu tiên trong một đoạn được đánh dấu trọng số O3
- Câu cuối cùng của đoạn được dánh dấu trọng số O4
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%.
26
Hình 2. Giá trị trung bình của các phương pháp [11]
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
Hệ thống tóm tắt trong [13] dựa trên cơ sở các phương pháp thống kê và thực hiện
trích chọn câu theo hai bước. Vì nó tổ hợp các phương pháp thống kê và làm giảm dữ liệu
nhiễu thông qua hai bước để có thể thu được hiệu suất cao.
Mục tiêu của tóm tắt văn bản là lấy thông tin, trích rút nội dung và biểu diễn những
nội dung quan trọng nhất cho người sử dụng theo một form nào đó. Phương pháp có chi
phí thấp và kiến trúc hệ thống vững chắc (robust) bởi vì nó không yêu cầu bất cứ nguồn
ngôn ngữ nào cả. Hai bước tóm tắt cụ thể như sau:
- Bước đầu tiên, tạo ra các câu giả bi-gram bằng cách tổ hợp hai câu kề nhau
(adjacent) để giải quyết vấn đề rời rạc đặc trưng (feature sparseness); vấn đề này xuất hiện
nếu tóm tắt văn bản trích chọn đặc trưng chỉ từ một câu. Sau đó, ước lượng trọng số quan
trọng của các câu giả bi-gram bằng phương pháp tổ hợp Title và Location. Có thể nhận
được nhiều câu giả có ích hơn thông qua việc xóa đi các câu giả bi-gram không có giá trị
(xóa dữ liệu nhiễu).
- Ở bước thứ hai, chia các câu giả bi-gram thành mỗi câu đơn gốc và biểu diễn trích
chọn các câu quan trọng bằng phương pháp Aggregation Similarity. Bởi vì phương pháp
Aggregation Similarity (độ tương đồng kết hợp) ước lượng các phần quan trọng nhất của
câu bằng việc tính toán độ tương đồng của tất cả các câu khác trong một tài liệu, phương
pháp Aggregation Similarity hiệu quả hơn sau khi xóa bỏ đi các câu nhiễu. Vì thế hệ
27
thống tóm tắt không yêu cầu nguồn ngôn ngữ như WordNet và bộ phân tích luật, nó cho
chi phí thấp và vững chắc. [13]
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 [13]
2.2.3.1. Các phương pháp thống kê tổng quát
Title Method
Trọng số của các câu được tính bằng số từ phổ biến được sử dụng giữa câu và title.
Tính toán này yêu cầu một truy vấn từ title trong mô hình không gian vector trọng số
Boolean.
Trong đó: Si là một câu thứ i và Q là một truy vấn từ title, wik là trọng số của từ thứ k
trong câu và wqk là trọng số của từ thứ k trong truy vấn.
Location Method
Trọng số của câu được tính theo công thức:
28
Trong đó: Si là câu thứ i và N là tổng số câu trong văn bản.
Aggregation Similarity Method
Trọng số của một câu được tính bằng tổng độ tương đồng của câu đó với tất cả các
vectors câu khác trong mô hình không gian vector tài liệu. Mỗi trọng số được tính như
sau:
Phương trình sim(Si, Sj) tính độ tương đồng giữa hai câu i và j, wik là trọng số của từ
thứ k trong câu thứ i.
Frequency Method
Tần số của từ xuất hiện trong một tài liệu thường được sử dụng để tính toán độ quan
trọng của các câu [15]. Trong phương pháp này, trọng số của một câu có thể được tính
bằng tổng trọng số của các từ trong câu. Có thể dùng phương pháp TF.IDF truyền thống
để tính trọng số wi của từ i như sau:
Trong đó: tfi là tần số từ của từ i trong tài liệu, N là tổng số từ trong văn bản và dfi là
tần số tài liệu của từ i trong toàn bộ tập dữ liệu.
2.2.3.2. Phương pháp TF-Based Query
Như mô tả ở trên, title thường sử dụng cho một truy vấn và phương pháp Title chỉ ra
hiệu suất cao hơn các phương pháp tổng quan khác. Tuy nhiên, trong trường hợp đặc biệt,
nó có thể khó trích rút một title từ các tài liệu hoặc bất cứ kiểu tài liệu nào không có title.
Đối với trường hợp này, chúng tôi đề xuất một phương pháp để trích rút các từ chủ để cho
một truy vấn. Phương pháp truy vấn trên cơ sở TF sử dụng một truy vấn – truy vấn bao
29
gồm các từ với tần số từ cao nhất trong một tài liệu. Phương pháp coi các từ với tần số
cao như các khái niệm quan trọng [15].
Giống như phương pháp Title, ma trận tích được sử dụng như độ đo tương đồng
giữa một câu và một truy vấn trên cơ sở TF. Để biểu diễn các câu, chỉ các từ thích hợp và
danh từ phổ biến được sử dụng sau khi loại bỏ từ dừng.
Trong đó, tfik là các tần số từ của từ thứ k trong câu thứ i (trọng số Boolean) và Si là
vector câu. Phương trình tính toán độ tương đồng giữa các câu và truy vấn trên cơ sở TF:
n là số lượng từ trong một tài liệu. wik là trọng số của từ thứ k trong câu thứ i và
wTFQk là trọng số của từ thứ k trong truy vấn trên cơ sở TF.
2.2.3.3. Tổ hợp các phương pháp thống kê trong hai bước
Xóa đi các câu nhiễu trong bước đầu tiên (First Step)
Phương trình đánh trọng số cho các câu giả bi-gram:
Sau khi tất cả các câu giả bi-gram được đánh trọng số, khoảng 50% trong số chúng
bị xóa bởi vì chúng bị xem là những câu nhiễu.
Tóm tắt trích chọn trong bước thứ hai (Second Step)
Phương trình cuối cùng như sau:
Trong đó wa là giá trị trọng số phản ánh tầm quan trọng của phương pháp
Aggregation Similarity.
30
Với trường hợp các tài liệu không có title, phương pháp truy vấn TF-based được sử
dụng thay cho phương pháp Title. Phương trình cụ thể như sau:
2.2.3.4. Kết quả thực nghiệm
Trong thực nghiệm, phương pháp sử dụng dữ liệu test gồm nhiều bài báo tin tức của
Korea Research and Development Information Center(KORDIC). Mỗi tài liệu test có
title, content, tóm tắt theo tỉ lệ 30% và 10%. Các tóm tắt theo tỉ lệ 30% và 10% của các tài
liệu test được làm bằng cách trích rút câu từ nội dung bằng tay. Để đo hiệu suất của
phương pháp, độ đo F1 được sử dụng như phương trình (13) sau:
Trong đó P là độ chính xác, R là độ hồi tưởng
Dưới đây là các kết quả thực nghiệm cụ thể của phương pháp
Để xác định hiệu quả của phương pháp tổ hợp hai bước, bài báo [13] so sánh hiệu
suất của phương pháp tổ hợp hai bước với các phương pháp khác như Title, Location, và
DOCUSUM.
31
Hình 4. So sánh giữa phương pháp Two-step và các phương pháp khác (trường
hợp sử dụng Title) [13]
Như trên hình 4, hệ thống trích chọn câu hai bước đã chỉ ra hiệu suất tốt hơn phương
pháp Title, Location và thậm chí là DOCUSUM. Thực nghiệm trong trường hợp no-title.
cũng chỉ ra kết quả như vậy.
Hình 5. So sánh giữa phương pháp Two-step và các phương pháp khác (trường
hợp không sử dụng Title) [13]
Tóm lại, phương pháp sử dụng các câu giả bi-gram để giải quyết vấn đề rời rạc đặc
trưng và tổ hợp thống kê hai bước để cải thiện hiệu quả. Như kết quả, phương pháp thu
được hiệu suất cao hơn các phương pháp thống kê khác và DOCUSUM. Phương pháp
này không chỉ có hiệu suất cao mà còn có điểm mạnh là dễ thực hiện bởi vì nó chỉ sử
dụng các phương pháp thống kê đơn giản.
32
Chương 3. Độ tương đồng câu và phương
pháp tính độ tương đồng câu
3.1. Độ tương đồng
Trong toán học, một độ đo là một hàm số cho tương ứng với một "chiều dài", một
"thể tích" hoặc một "xác suất" với một phần nào đó của một tập hợp cho sẵn. Nó là một
khái niệm quan trọng trong giải tích và trong lý thuyết xác suất.
Ví dụ, độ đo đếm được định nghĩa bởi µ(S) = số phần tử của S
Rất khó để đo sự giống nhau, sự tương đồng. Sự tương đồng là một đại lượng (con
số) phản ánh cường độ của mối quan hệ giữa hai đối tượng hoặc hai đặc trưng. Đại lượng
này thường ở trong phạm vi từ -1 đến 1 hoặc 0 đến 1. Như vậy, một độ đo tương đồng có
thể coi là một loại scoring function (hàm tính điểm).
Ví dụ, trong mô hình không gian vector, ta sử dụng độ đo cosine để tính độ tương
đồng giữa hai văn bản, mỗi văn bản được biểu diễn bởi một vector.
Phân loại độ đo tương đồng, ở đây có thể liệt kê ra một số độ đo như độ đo tương
đồng giữa các từ, độ đo tương đồng giữa các văn bản, độ đo tương đồng giữa nhiều ảnh,
độ đo tương đồng giữa các ontology, …
3.2. Độ tương đồng câu
Xét ví dụ gồm hai câu “Tôi là nam” và “Tôi là nữ”. Ta có thể nhận thấy hai câu trên
có sự tương đồng cao, tuy nhiên chúng ta cần phải có một độ đo để có thể tính được độ
tương đồng của chúng.
Bài toán tính độ tương đồng câu được phát biểu như sau: Xét một tài liệu d gồm có n
câu: d = s1,s2,… sn. Mục tiêu của bài toán là tìm ra được một giá trị của hàm S(si,sj) với
S∈(0,1). Hàm S(si,sj) được gọi là độ tương đồng giữa hai câu si và sj. Giá trị này càng cao
thì sự giống nhau về ngữ nghĩa của hai câu càng lớn.
Độ tương đồng ngữ nghĩa là một giá trị tin cậy phản ánh mối quan hệ ngữ nghĩa
giữa hai câu. Trên thực tế, khó có thể lấy một giá trị có chính xác cao bởi vì ngữ nghĩa chỉ
được hiểu đầy đủ trong một ngữ cảnh cụ thể.
33
3.3. Phương pháp để đo độ tương đồng câu
Như đã giới thiệu, hiện nay có hai phương pháp điển hình để đo độ tương đồng câu
là phương pháp thống kê và phương pháp xử lý ngôn ngữ tự nhiên..
Với phương pháp thống kê, có một số phương pháp sử dụng các độ đo dựa vào tần
suất xuất hiện của từ trong câu, nổi bật là phương pháp sử dụng độ đo cosin. Phương pháp
này xử lý nhanh, tốn ít chi phí tuy nhiên vẫn chưa đảm bảo độ chính xác cao về mặt ngữ
nghĩa.
Còn các phương pháp sử dụng xử lý ngôn ngữ tự nhiên, một số cách tiếp cận đặc
trưng được đưa ra là sử dụng phân tích cấu trúc ngữ pháp, sử dụng mạng ngữ nghĩa đối
với từ, như sử dụng Wordnet corpus hoặc Brown corpus. Phương pháp xử lý ngôn ngữ tự
nhiên xử lý chậm hơn, tốn nhiều chi phí hơn tuy nhiên khi xét về mặt ngữ nghĩa thì cao
hơn phương pháp thống kê.
Xét cho cùng, cả phương pháp xử lý ngôn ngữ tự nhiên cũng như phương pháp
thống kê đều chỉ là những phương pháp “tạm thời” bởi vì chúng chưa đạt đến mức độ
“thông minh” như con người mong muốn.
3.3.1. Phương pháp tính độ tương đồng câu sử dụng WordNet corpus
3.3.1.1. Mô hình của phương pháp
Mô hình của phương pháp dựa trên mô hình được đề xuất trong báo cáo [16] để tính
toán độ tương đồng câu tiếng Anh.
34
Hình 6. Lược đồ tính toán độ tương đồng câu [16]
Về mặt cấu trúc, một đoạn văn bản gồm nhiều câu, mỗi câu được tạo thành bởi một
chuỗi các từ mang các thông tin cần thiết. Phương pháp này được thực hiện dựa vào thông
tin về ngữ nghĩa và cú pháp của các từ trong câu
Dựa vào mô hình, giải quyết bài toán có 5 bước:
Bước 1: Tiền xử lý
- Tách mỗi câu thành một danh sách các từ tố (token): Mỗi câu được tách ra thành
một danh sách các từ và xóa đi các từ dừng. Từ dừng là các từ xuất hiện thường
xuyên, các từ không có ý nghĩa.
- Xác định từ loại (part of speech: từ loại): Sau khi câu được tách thành danh sách
các từ. Bước này sẽ xác định đúng từ loại (POS - như noun, verb, pronoun, adverb
...) của mỗi từ trong câu.
Bước 2: Tính độ tương tự từ
- Sau khi đã có danh sách các từ được gán nhãn, ta xác định được một tập từ chung
cho hai câu. Tập từ chung này bao gồm tất cả những từ phân biệt có trong hai câu
đó.
- Dựa vào tập từ chung đồng thời sử dụng wordnet ta sẽ ước tính được độ tương
đồng về ngữ nghĩa cho các từ trong mỗi câu với tập từ chung .Từ đó đưa ra được
vector ngữ nghĩa cho hai câu.
Bước 3: Tính độ tương đồng ngữ nghĩa cho hai câu
Khi tính được độ tương tự từ, ta đưa ra được vector ngữ nghĩa si cho mỗi câu. Sử
dụng vector ngữ nghĩa của hai câu để tính độ tương đồng về ngữ nghĩa cho hai câu
đó.
Bước 4: Tính độ tương đồng thứ tự từ
Dựa tập từ chung ta xác định vector thứ tự từ cho mỗi câu.
Bước 5: Tính độ tương đồng cho toàn bộ câu
Kết hợp giữa vector ngữ nghĩa và vector thứ tự của hai câu ta tính ra được độ tương
đồng cho hai câu.
35
3.3.1.2. Tính độ tương tự từ dựa trên WordNet
Vì một đoạn văn bản gồm nhiều câu và mỗi câu có thể xem như một chuỗi các từ
mang thông tin cần thiết nên từ được xem như là đơn vị thấp nhất về mặt ngữ nghĩa khi
xét cho một văn bản. Vậy, muốn tính độ tương tự câu yêu cầu bắt buộc phải dựa vào độ
tương tự của từ có trong câu.
Độ tương tự giữa các từ có ý nghĩa trong các bài toán trích chọn thông tin từ corpus
và trong NLP được dùng để hỗ trợ cho việc biên soạn các từ điển từ đồng nghĩa. Bên cạnh
đó, nó cũng được ứng dụng để mở rộng và sửa các truy vấn ngôn ngữ tự nhiên [20].
Phương pháp tiến hành đo độ tương tự từ dựa vào wordnet
Như trên đã giới thiệu, WordNet là một mạng ngữ nghĩa trong đó có chứa rất nhiều
node. Mỗi node sẽ biểu diễn một khái niệm về thế giới thực. Wordnet được xây dựng
dưới dạng cây phân cấp nên thể hiện được mối quan hệ giữa các từ. Vì thế, việc sử dụng
wordnet cho việc tính độ tương tự từ sẽ thuận tiện rất nhiều.
Ví dụ đối với hai từ boy và teacher, khi xét mối quan hệ giữa 2 từ này trên tập
corpus wordnet ta có thể xây dựng được một cấu trúc cây thể hiện mối quan hệ ngữ nghĩa
giữa hai từ thông qua các nút khác như trong hình vẽ. Teacher – educator – professional
– adult – person – male – male child – boy [16].
36
Hình 7. Hệ thống cây phân cấp ngữ nghĩa[16]
Cho hai từ c1, c2, chúng ta cần tính độ tương tự từ cho hai từ đó dựa vào WordNet.
Ta sẽ tìm một lớp nào đó trong cây phân cấp để xác định các từ trong nhóm lớp đó, rồi
tiến hành so sánh. Phương pháp này có thể được thực hiện dựa vào nhiều độ đo như: độ
đo Jiang Conrath (JCN), độ đo Lin, Extended Gloss Overlaps, Hirst-St Onge, Resnik,
Leacock-Chodorow. Từ [20], có bảng sau:
Measure Nouns Only All POS
Jiang-Conrath 0.46 n/a
Ex.Gloss Overlaps 0.43 0.34
Lin 0.39 n/a
Vector 0.33 0.29
37
Hirst-St.Onge 0.33 0.23
Resnik 0.29 n/a
Leacock Chodorow 0.28 n/a
Bảng 1. Các kết quả so sánh các độ đo
Độ đo JCN luôn có giới hạn dưới là 0 nhưng không có giới hạn trên. JCN sử dụng
nội dung thông tin (Information Content) của các khái niệm (concept).
IC = IC(concept) = –log(P(concept))
Xác suất xuất hiện của khái niệm trong một corpus được tính bằng tần số của từ đó
trong corpus:
P(concept) = freq(concept)/N
Trong đó: N là tổng số khái niệm có trong corpus.
Công thức tính khoảng cách ngữ nghĩa:
distance = IC(c1) + IC(c2) – 2. IC(lcs(c1, c2))
Trong đ ó: lcs(c1, c2): Khái niệm thấp nhất trong hệ thống cấp bậc quan hệ is-a hay
nó là cha của hai từ c1và c2; distance: Khoảng cách của hai từ.
Từ đó, đưa ra được mối quan hệ giữa hai từ c1 và c2 như sau:
Relatedness(c1, c2) = 1 / distance
Ví dụ: Xét hai từ boy và teacher. Dựa vào hình 4 ta có lcs(boy, teacher) là person
3.3.1.3. Độ tương đồng về ngữ nghĩa giữa 2 câu
Sau khi tính được độ tương tự từ, ta đưa ra được vector ngữ nghĩa si cho mỗi câu.
Giá trị của từng thành phần có trong vector là giá trị về độ tương tự từ của từng từ trong
câu với tập từ chung [16].
Sự giống nhau về ngữ nghĩa giữa 2 câu là hệ số cosin giữa 2 vector :
||||.||||
.
21
21
ss
ssSs =
38
3.3.1.4. Độ tương đồng về thứ tự của các từ trong câu
Mục tiêu của phần này là từ hai câu input, đưa ra được vector thứ tự từ cho mỗi câu.
Ví dụ: Ta có hai câu T1 và T2 với
T1: A quick brown dog jumps over the lazy fox
T2: A quick brown fox jumps over the lazy dog
Tập từ chung T = {A quick brown dog jumps over the lazy fox }
Nếu chỉ xét đến độ tương đồng về ngữ nghĩa giữa các từ trong câu thì 2 câu này
giống nhau hoàn toàn. Tuy nhiên thực tế lại khác, hai câu mang ý nghĩa hoàn toàn trái
ngược nhau. Vì vậy, nãy sinh vấn đề cần phải tính đến thứ tự của các từ có trong câu [16].
Cách ước tính độ tương đồng về thứ tự của các từ trong mỗi câu như sau:
- Nếu như từ trong tập từ chung mà có trong câu thì từ đó sẽ có cùng thứ tự với từ
trong câu đó.
- Ngược lại, nếu như từ trong tập từ chung không giống với từ nào trong câu thì thứ
tự của nó sẽ là 0.
Gọi r là vector thứ tự từ trong câu. Với hai câu T1 và T2 thì ta có hai vector r1 và r2
tương ứng như sau:
r1 = { 1 2 3 4 5 6 7 8 9 }
r2 = {1 2 3 9 5 6 7 8 4 }
Công thức để tính độ tương đồng về thứ tự của từ trong câu như sau:
3.3.1.5. Tính độ tương đồng cho toàn bộ câu
Sự giống nhau về toàn bộ câu được định nghĩa là sự kết hơp giữa độ tương tự về mặt
ngữ nghĩa và thứ tự của từ trong câu
||||
||||)1(
||||.||||
.
)1(),(
21
21
21
21
21
rr
rr
ss
ss
SSTTS rs
+
−−+=
−+=
δδ
δδ
||||
||||1
21
21
rr
rrS r +
−−=
39
Với , quyết định việc đóng góp về ngữ nghĩa và thứ tự từ tới toàn bộ
câu.
3.3.2. Phương pháp tính độ tương đồng câu sử dụng Hidden Topic
Mục tiêu chính là làm thế nào để thu được lợi từ các nguồn tài nguyên lớn của dữ
liệu trực tuyến nhằm tăng tính ngữ nghĩa trong việc tính độ tương đồng câu.
Phương pháp tiếp cận vấn đề dựa trên cơ sở các nghiên cứu thành công gần đây của
mô hình phân tích topic ẩn LDA (Latent Dirichlet Allocation) … Ý tưởng cơ bản của mô
hình là với mỗi lần học, ta tập hợp một tập dữ liệu lớn được gọi là “Universal dataset” và
xây dựng một mô hình học trên cả dữ liệu học và một tập giàu các topic ẩn được tìm ra từ
tập dữ liệu đó. [6]
3.3.2.1. Latent Dirichlet Allocation (LDA)
Latent Dirichlet Allocation (LDA) là một mô hình sinh xác suất cho tập dữ liệu rời
rạc như text corpora. David Blei, Andrew Ng và Michael Jordan đã phát triển LDA vào
năm 2003. LDA dựa trên ý tưởng: mỗi tài liệu là sự trộn lẫn của nhiều topic, mỗi topic là
một phân bố xác suất trên các từ. Về bản chất, LDA là một mô hình Bayesian 3 cấp
(three-level hierarchical Bayes model: corpus level, document level, word level) trong đó
mỗi phần của một tập hợp được mô hình như một mô hình trộn hữu hạn trên cơ sở tập các
xác suất topic. Trong ngữ cảnh của mô hình văn bản, xác suất topic cung cấp một biểu
diễn tường minh của một tài liệu. Trong phần tiếp theo sẽ thảo luận nhiều hơn về mô hình
sinh, ước lượng tham số cũng như inference trong LDA.
Mô hình sinh trong LDA
Cho một corpus của M tài liệu biểu diễn bởi D={d1,d2, …, dM}, trong đó, mỗi tài
liệu m trong corpus bao gồm Nm từ wi rút từ một tập Vocabulary của các term {t1, …, tv},
V là số từ. LDA cung cấp một mô hình sinh đầy đủ chỉ ra kết quả tốt hơn các phương
pháp trước. Quá trình sinh ra document như sau:
10 ≤≤ δ δ
40
Hình 8. Mô hình biểu diễn của LDA [6]
Các khối vuông trong Hình 8 biểu diễn các quá trình lặp.
Tham số đầu vào: α và β (corpus-level parameter)
α: Dirichlet prior on mϑ
r
(theta)
β: Dirichlet prior on kϕr
mϑ
r
(theta): phân phối của topic trong document thứ m (document-level parameter)
zm,n : topic index (word n của văn bản m)
wm,n: word n của văn bản m chỉ bởi zm,n (word-level variable, observed word)
kϕr : phân phối của các từ được sinh từ topic zm,n
M: số lượng các tài liệu.
Nm: số lượng các từ trong tài liệu thứ m.
K: số lượng các topic ẩn.
LDA sinh một tập các từ wm,n cho các văn bản md
r
bằng cách:
• Với mỗi văn bản m, sinh ra phân phối topic mϑ
r
cho văn bản.
• Với mỗi từ, zm,n được lấy mẫu dựa vào phân phối topic trên.
• Với mỗi topic index zm,n, dựa vào phân phối từ kϕr , nmw , được sinh ra.
41
• kϕr được lấy mẫu một lần cho tòan bộ corpus.
Mô hình sinh đầy đủ (đã chú giải) được biểu diễn trong Hình 9.
Hình 9. Mô hình sinh cho LDA
Ở đây, Dir, Poiss and Mult lần lượt là các phân phối Dirichlet, Poisson, Multinomial.
(Lấy mẫu theo phân phối Dirichlet, Poisson, Multinomial).
Ước lượng tham số và Inference thông qua Gibbs Sampling
Cho trước một tập các văn bản, tìm xem topic model nào đã sinh ra tập các văn bản
trên. Bao gồm:
- Tìm phân phối xác suất trên tập từ đối với mỗi topic - kϕr
- Tìm phân phối topic của mỗi tài liệu mϑ
r
Gibbs Sampling
- Thuật toán nhằm lấy mẫu từ phân phối xác suất có điều kiện của 2 hoặc nhiều
biến ngẫu nhiên.
- Quá trình ước lượng tham số cho LDA gồm các bước:
42
Khởi tạo: lấy mẫu lần đầu
zero all count variables, ( )zmn , mn , ( )tzn , zn
for all documents [ ]Mm ,1∈ do
for all words [ ]mNn ,1∈ in document m do
sample topic index nmz , ~Mult(1/K)
increment document-topic count: ( ) 1+smn
increment document-topic sum: 1+mn
increment topic-term count: ( ) 1+tsn
increment topic-term sum: 1+zn
end for
end for
Hình 10. Quá trình khởi tạo lấy mẫu lần đầu
Trong đó: ( )zmn : số topic z trong văn bản m
mn : tổng số topic trong văn bản m
( )tzn : số term t trong topic z
zn : tổng số term trong topic z
Mỗi lần lấy mẫu cho một từ, các tham số đối với từng term và topic trên lần lượt
được tăng lên.
43
Burn-in period: quá trình lấy mẫu lại cho đến khi đạt được một độ chính xác nhất
định
while not finished do
for all documents [ ]Mm ,1∈ do
for all words [ ]mNn ,1∈ in document m do
- for the current assignment of z to a term t for word nmw , :
decrement counts and sums: ( ) 1−zmn ; 1−mn ; ( ) 1−tzn ; 1−zn
- multinomial sampling acc. To Eq. Error! Reference source
not found. (decrements from previous step):
sample topic index ( )wzzpz ii rr ,|~~ −
- use the new assignment of z to the term t for word nmw , to:
increment counts and sums: ( ) 1+zmn
r
; 1+tzn r ; 1+zn r
end for
end for
Hình 11. Quá trình khởi tạo lấy mẫu lại
Trong mỗi lần lấy mẫu lại: các tham số tương ứng với các topic và term cũ giảm đi
1, các tham số tương ứng với các topic và term mới tăng lên 1.
44
Check convergence and read out parameters: Quá trình kết thúc, đọc các tham số
đầu ra Φ và Θ
if converged and L sampling iterations since last read out then
- the different parameters read outs are averaged
read out parameter set Φ acc. to Eq. kϕr
read out parameter set Θ acc. to Eq. mϑ
r
end if
end while
Hình 12. Quá trình đọc các tham số đầu ra
2 phân phối ẩn kϕr và mϑ
r
được tính như sau:
Ước lượng tham số
Để phát triển một bộ lấy mẫu Gibbs cho LDA, Heirich et al áp dụng phương pháp
biến ẩn. Biến ẩn ở đây là nmz , , ví dụ, các topic xuất hiện với các từ nmw , của corpus. Ở đây,
không cần gộp các tập tham số Θ và Φ bởi vì chúng chỉ là thống kê sự kết hợp giữa wm,n
và zm,n tương ứng, các biến trạng thái của chuỗi Markov.
3.3.2.2. Sử dụng mô hình chủ đề ẩn để tính độ tương đồng câu
Với mỗi câu, sau khi inference topic sẽ nhận được các phân phối xác suất của topic
trên câu và phân phối xác suất của từ trên topic. Tức là với mỗi câu i, LDA sinh ra phân
phối topic iϑ
r
cho câu. Với mỗi từ trong câu, zi,j – topic index (từ j của câu i) - đuợc lấy
mẫu dựa theo phân phối topic trên. Sau đó, dựa vào topic index zi,j ta làm giàu các câu
bằng cách thêm từ. Vector tương ứng với câu thứ i có dạng như sau:
( )
( )
v
V
v
v
k
t
t
k
tk
n
n
β
βϕ
+
+=
∑
=1
,
( )
( )
z
K
z
z
m
k
k
m
km
n
n
α
αϑ
+
+=
∑
=1
,
{ }||121 ,...,,,...,, VKi wwttts =
45
Ở đây, 1
1
=∑
=
K
i
it và ∑
=
=
||
1
1
V
i
iw . ti là trọng số của topic thứ i trong K topic đã được phân
tích (K là một tham số hằng của LDA); wi là trọng số của từ thứ i trong tập từ vựng V của
tất cả các câu. Ở đây, không cần phải tìm phân phối xác suất từ đối với topic vì ở mức
P(topic|câu), kết quả tóm tắt mang tính ngữ nghĩa bao quát hơn.
Mỗi câu có thể có nhiều phân phối xác suất topic. Với hai câu thứ i và j, chúng ta sử
dụng độ đô cosine để tính độ tương đồng giữa hai câu đã được làm giàu với Hidden
Topic.
46
Chương 4. Đề xuất mô hình tóm tắt và kết
quả thực nghiệm
4.1. Đề xuất mô hình tóm tắt
Khóa luận đề xuất mô hình để giải quyết bài toán tóm tắt là tính toán độ tương tự
câu sử dụng Hidden Topic. Ưu điểm của việc sử dụng Hidden Topic 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 bất cứ một corpus nào khác.
Cụ thể quy trình tóm tắt văn bản gồm các bước sau:
Bước 1: Quá trình tiền xử lý:
- Xử lý văn bản: Tách câu, đưa mỗi câu nằm trên từng dòng, bỏ các câu ngắn
theo một ngưỡng đã xác định trước.
- Sử dụng công cụ JvnSegmente [25] để tách các từ trong tiếng Việt cho kết quả
trả về từ bước trên; Loại bỏ các từ stop-word không có ý nghĩa.
- Lưu các câu vào một cấu trúc dữ liệu có dạng Sentence đã được định nghĩa
trước (trong class Sentence). Class Corpus sẽ quản lý tập dữ liệu các câu.
Bước 2: Quá trình tính toán độ tượng tự ngữ nghĩa giữa các cặp câu:
- Sử dụng JgibbsLD [24] xác định topic model nào sinh ra tập các câu trên, tức là
tìm phân phối xác suất của topic trên câu.
- Tính độ tương đồng giữa các cặp câu sử dụng Hidden Topic bằng độ đo
Cosine.
Bước 3: Quá trình tóm tắt văn bản:
- Tính trọng số lần lượt cho từng câu bằng phương pháp Aggregation Similarity
[13].
- Sắp xếp theo thứ tự tăng dần trọng số của câu.
47
- Dựa vào một ngưỡng tỷ lệ tóm tắt cho trước, chọn ra được một số lượng các
câu có trọng số cao nhất.
4.2. Thiết kế mô hình thử nghiệm
Mô tả dữ liệu
- Input: Một văn bản tiếng Việt
Dữ liệu dùng để tóm tắt là các trang tin bài được lấy từ các trang báo điện tử
của Việt nam như
- Output: Văn bản đã được tóm tắt với tỷ lệ cho trước.
Mục tiêu:
- Tính được độ tương đồng câu bằng độ đo Cosine.
- Tính được độ tương đồng câu bằng độ đo Cosine áp dụng thêm Hidden topic.
- Áp dụng độ đo trên vào bài toán tóm tắt văn bản đơn.
4.3. Kết quả thực nghiệm
Nội dung trang web tóm tắt
1 người VN mất tiền vì 'nước thần'
Một người Việt Nam ở Nauy đã mất 180.000 kroner (35.000 USD) vì tin rằng, nếu trộn
lượng tiền mặt này với một thứ nước lỏng đặc biệt, số tiền sẽ tự sinh ra gấp đôi.
Trong tuần này, một người đàn ông 32 tuổi có quốc tịch Pháp sẽ phải ra hầu tòa ở Oslo vì
bị cáo buộc tội lừa đảo bằng "nước thần".
Đầu năm nay, anh chàng này đã dạy một người Việt Nam cách làm giàu chỉ qua một đêm.
Theo cách làm này, một số tiền mặt được xếp chung với một lượng giấy trắng, nhúng vào
một chất lỏng đặc biệt để qua đêm. Sáng hôm sau, số tiền sẽ tự sinh ra gấp đôi.
Sau khi nghe theo lời khuyên, nạn nhân đã mất sạch cả tiền mặt và mất luôn dấu vết của
"thầy phù thủy" khi thức dậy vào sáng hôm sau. Vào ngày 3/3, "thầy phù thủy" trên đã bị
bắt khi tìm mọi cách rời khỏi Nauy với 200.000 kroner trong hành lý.
Hình 13. Nội dung một văn bản đơn tiếng Việt
48
Áp dụng quy trình tóm tắt ở mục 4.1, tính được độ tương đồng lần lượt giữa các câu
trong văn bản và trọng số của từng câu.
Trường hợp không sử dụng Hidden Topic, trọng số của từng câu như bảng sau:
Câu Trọng số
1 2.547
2 1.902
3 2.342
4 2.247
5 1.479
6 1.802
7 1.913
8 1.937
9 1.668
10 1.766
Bảng 2. Trọng số của từng câu trong văn bản [không dùng Hidden Topic]
Với tỷ lệ trích xuất 30% có kết quả tóm tắt như sau:
“Một người Việt Nam ở Nauy đã mất 180.000 kroner (35.000 USD) vì tin rằng, nếu
trộn lượng tiền mặt này với một thứ nước lỏng đặc biệt, số tiền sẽ tự sinh ra gấp đôi. Đầu
năm nay, anh chàng này đã dạy một người Việt Nam cách làm giàu chỉ qua một đêm.
Theo cách làm này, một số tiền mặt được xếp chung với một lượng giấy trắng, nhúng vào
một chất lỏng đặc biệt để qua đêm.”
49
Trường hợp không sử dụng Hidden Topic, trọng số của từng câu:
Câu Trọng số
1 1.765
2 1.000
3 1.209
4 1.194
5 1.354
6 1.414
7 1.386
8 1.294
9 1.000
10 1.105
Bảng 3. Trọng số của từng câu trong văn bản [dùng Hidden Topic]
Tương tự, với tỷ lệ trích xuất 30%, có kết quả tóm tắt:
“Một người Việt Nam ở Nauy đã mất 180.000 kroner (35.000 USD) vì tin rằng, nếu
trộn lượng tiền mặt này với một thứ nước lỏng đặc biệt, số tiền sẽ tự sinh ra gấp đôi. Sau
khi nghe theo lời khuyên, nạn nhân đã mất sạch cả tiền mặt và mất luôn dấu vết của "thầy
phù thủy" khi thức dậy vào sáng hôm sau. Vào ngày 3/3, "thầy phù thủy" trên đã bị bắt
khi tìm mọi cách rời khỏi Nauy với 200.000 kroner trong hành lý.”
Nhận xét, đánh giá
Từ thực nghiệm, có thể thấy rằng, mô hình tóm tắt sử dụng Hidden Topic cho kết
quả khả quan mặc dù các câu trả về vẫn chưa thể hiện ngữ nghĩa một cách súc tích ngắn
gọn. Những câu có trọng số cao nhất sẽ được trích rút cho tóm tắt. Tỷ lệ trích rút sẽ chỉ ra
số lượng câu được chọn cho văn bản tóm tắt.
50
Kết luận và hướng phát triển của khóa luận
Với nhu cầu thực tiễn về các ứng dụng tóm tắt văn bản hiện nay, khóa luận đã tập
trung nghiên cứu về bài toán tóm tắt văn bản nói chung và tóm tắt văn bản đơn nói riêng.
Các kết quả cụ thể mà khóa luận đạt được là:
- Khảo sát, nghiên cứu các phương pháp tóm tắt văn bản; áp dụng độ đo tương
đồng câu vào trong tóm tắt.
- Khóa luận cũng đã đề xuất được một mô hình tóm tắt văn bản đơn dựa trên tính
toán độ tương đồng câu có sử dụng Hidden Topic.
- Thử nghiệm mô hình đã đề xuất và cho được kết quả ban đầu khả quan.
Do hạn chế về thời gian và kiến thức sẵn có, khóa luận mới chỉ dừng lại ở mức thử
nghiệm mô hình. Với những kết quả thực nghiệm ban đầu, sẽ cần tiếp tục hoàn thiện
phương pháp tóm tắt để nâng cao hiệu suất tóm tắt.
Bên cạnh đó, tìm hiểu s ự khác nhau giữa văn bản đơn và đa văn bản. Từ đó áp dụng
phương pháp tính độ tương đồng câu vào trong tóm tắt đa văn bản. Mục tiêu cụ thể là tiếp
tục tăng tính ngữ nghĩa cho phương pháp tính độ tương đồng câu áp dụng vào bài toán
tóm tắt đa văn bản.
51
Tài liệu tham khảo
Tiếng Việt
[1] Hà Thành Lê, Lương Chi Mai, Huỳnh Quyết Thắng, Định Thị Phương Thu (2006).
Kết hợp các phương pháp chọn câu quan trọng xây dựng ứng dụng tóm tắt văn bản tiếng
Việt, Một số vấn đề chọn lọc của công nghệ thông tin, 2006, 413-421.
[2] Lương Chi Mai, Hồ Tú Bảo (2006). Về xử lý tiếng Việt trong công nghệ thông tin, Tài
liệu Đề tài KC.01.01.06-10 "Nghiên cứu phát triển một số sản phẩm thiết yếu về xử lý
tiếng nói và văn bản tiếng Việt", Viện Công nghệ Thông tin, Viện Khoa học và Công
nghệ Việt Nam, 2006.
[3] Đỗ Phúc, Hồ Anh Thư (2005). Rút trích và tóm tắt nội dung trang web tiếng Việt,
Phát triển khoa học - công nghệ, 2005, 8/(10):13-22
[4] Phạm Thị Thu Uyên, Hoàng Minh Hiền, Trần Mai Vũ, Hà Quang Thụy. Độ tương
đồng ngữ nghĩa giữa hai câu và ứng dụng trong tóm tắt văn bản tiếng Việt (gui Hoi nghi
Hue).
Tiếng Anh
[5] Dang Thanh Hai, Nguyen Thu Trang, Ha Quang Thuy. The Graph of Concepts based
Text Summarization, College of Technology, Vietnam National University, Hanoi.
[6] Phan Xuan Hieu, Susumu Horiguchi, Nguyen Le Minh. Learning to Classify Short
and Sparse Text & Web with Hidden Topics from Large-scale Data Collections, 17th
International World Wide Web Conference, 2008.
[7] Le Nguyen Minh (2004). Statistical Machine Learning Approaches to Cross Language
Text Summarization, PhD thesis in School of Information Science Japan Advanced
Institute of Science and Technology, September 2004.
52
[8] Cam-Tu Nguyen, Trung-Kien Nguyen, Xuan-Hieu Phan, Le-Minh Nguyen and
Quang-Thuy Ha (2006). Vietnamese Word Segmentation with CRFs and SVMs: An
Investigation. The 20th Pacific Asia Conference on Language, Information and
Computation (PACLIC20), November 1-3, 2006, Wuhan, China, 215-222.
[9] Blake,C., Kampov,J., Orphanides,A., West,D., & Lown,C. (2007). UNC-CH at DUC
2007: Query Expansion, Lexical Simplification, and Sentence Selection Strategies for
Multi-Document Summarization, Document Understanding Conference 2007 (DUC
2007), Rochester, NY, April 26-27, 2007.
[10] Dan Cohen. Automatic Text Summarization. Seminar in Natural Language
Programming and Computational Linguistics.
[11] H. Edmundson. New methods in automatic abstracting. Journal of ACM, 16(2):264--
285, 1969.
[12] Jiawei Han and Micheline Kamber. Data Mining: Concepts and Techniques, 2nd ed.
The Morgan Kaufmann Series in Data Management Systems, Jim Gray, Series Editor
Morgan Kaufmann Publishers, March 2006. ISBN 1-55860-901-6.
[13] Wooncheol Jung, Youngjoong Ko, and Jungyun Seo (2004). Automatic Text
Summarization Using Two-step Sentence Extraction, Proceedings of Asian Information
Retrieval Symposium (AIRS 2004), in Beijing, China, pp.43-48, Oct, 2004.
[14] Daniel Jurafsky, and James H. Martin, 2000. Speech and Language Processing: An
Introduction to Natural Language Processing, Speech Recognition, and Computational
Linguistics. Prentice-Hall.
[15] H.P.Luhn. The automatic creation of literature abstracts. IBM Journal of Research
Development, 2(2):159–165,1958.
[16] Yuhua Li, David McLean, Zuhair Bandar, James O'Shea, Keeley A. Crockett
(2006). Sentence Similarity Based on Semantic Nets and Corpus Statistics. IEEE Trans.
Knowl. Data Eng. 18(8): 1138-1150
53
[17] A. A. Mohamed, S. Rajasekaran, (2006). Query-Based Summarization Based on
Document Graphs, Document Understanding Workshop, June 8-9, 2006 (DUC2006),New
York Marriott, Brooklyn, New York USA.
[18] Inderjeet Mani and Mark T. Maybury (eds). Advances in Automatic Text
Summarization. MIT Press, 1999. ISBN 0-262-13359-8. 442 pp.
[19] Manabu Okumura. Text Summarization. Asian Applied Natural Language
Processing for Linguistics Diversity and Language Resource Development (ADD2),
Thailand Science Park, 2007.
[20] Siddharth Patwardhan (2003). Incorporating Dictionary and Corpus Information into
a Context Vector Measure of Semantic Relatedness. MSc. Thesis, University of
Minnesota, Duluth, MN.
[21] P. Senellart and V. D. Blondel (2008). Automatic discovery of similar words, Survey
of Text Mining II: Clustering, Classification and Retrieval (M. W. Berry and M.
Castellanos, editors): 25–44. Springer-Verlag, January 2008.
[22] Pierre Senellart (2007). Understanding the Hidden Web, PhD thesis in Computer
science, Université Paris-Sud, Orsay, France, December 2007.
[23] Krishna Sapkota, Laxman Thapa, Shailesh Bdr. Pandey (2006). Efficient Information
Retrieval Using Measures of Semantic Similarity, Conference on Software, Knowledge,
Information Management and Applications, Chiang Mai, Thailand, December 2006, 94-
98.
Các công cụ sử dụng
[24] Phan Xuân Hiếu. JGibbsLDA. School of
Information Sciences Tohoku University.
[25] Nguyễn Cẩm Tú, Phan Xuân Hiếu. JvnSegmenter.
Đại học Công nghệ - Đại học Quốc gia Hà Nội.
Các file đính kèm theo tài liệu này:
- Độ tương đồng ngữ nghĩa giữa hai câu và ứng dụng trong tóm tắt văn bản.pdf