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


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

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

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


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

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ữ

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.

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ự

ự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.

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

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

- 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ố O
1

- Các câu của đoạn cuối cùng đựoc đánh dấu trọng số O
2