LỜI CẢM ƠN
Người đầu tiên tôi muốn gửi lời cảm ơn là thầy giáo hướng dẫn của
tôi, Thầy giáo. Thầy đã gợi mở cho tôi những ý tưởng mới, hướng
nghiên cứu thích hợp, luôn sẵn sàng giúp khi tôi cần sự giúp đỡ và đặc
biệt là luôn luôn động viên để tôi tin rằng mình sẽ thành công. Làm
việc với thầy tôi đã học hỏi được phương pháp nghiên cứu khoa học,
cách tiếp cận và giải quyết với những vấn đề mới và hơn hết là một
cách làm việc nghiêm túc và khoa học.
Tôi muốn gửi lời cảm ơn tới các thầy cô trong khoa Công nghệ
Thông đã giúp đỡ, chỉ bảo tôi trong suốt quá trình học tập tại trường
cũng như làm đồ án tốt nghiệp.
Tôi muốn gửi lời cảm ơn tới các anh, chị tại công ty tôi thực tập –
công ty Cổ phần Dịch vụ Công nghệ Thông tin NaiSCorp. Mọi người ở
công ty đã tạo điều kiện, giúp đỡ tôi trong suốt quá trình thực tập cũng
như làm đồ án tốt nghiệp, phòng Ngôn Ngữ đã giúp tôi trong việc đánh
giá chất lượng bản tóm tắt.
Cuối cùng, tôi muốn gửi lời cảm ơn tới những người thân và bạn bè
của tôi – những người đã luôn động viên tôi trong suốt quá trình học tập
cũng như làm đồ án tốt nghiệp.
1
TÓM TẮT NỘI DUNG
Tự động tóm tắt văn bản là tự động xác định những nội dung quan
trọng nhất trong một (một số) tài liệu (cùng loại). Đây là một bài toán rất
khó, liên quan đến nhiều lĩnh vực khoa học như: trí tuệ nhân tạo, thống
kê, ngôn ngữ học, Bài toán này đã được các nhà nghiên cứu trên thế
giới tìm hiểu từ những năm 1950, kết quả của những nghiên cứu đó là
một số hệ thống tự động tóm tắt văn bản đã được công bố và cho chất
lượng khá tốt như SUMMARIST, SweSUM, MEAD, Tuy nhiên, các
nghiên cứu và các hệ thống đó chỉ áp dụng cho một số ngôn ngữ như:
Tiếng Anh, Tiếng Pháp, Tiếng Nhật,… Mặc dù đã được nghiên cứu
nhiều, thu được nhiều thành công nhưng bài toán này vẫn là một thách

2.2.1.Quá trình Markov rời rạc 21
2.2.2.Mô hình Markov ẩn 23
2.2.3.Ba bài toán cơ bản được giải quyết bởi HMM 24
2.3.Mô hình Maximum Entropy 25
2.3.1.Lý thuyết Entropy 26
2.3.2.Mô hình học Maximum Entropy 27
3.1.Mô hình bài toán 31
3.1.1.Tiền xử lý 32
3.1.1.1.Loại bỏ từ dừng (stop-word) 33
3.1.1.2.Stemming 34
3.1.1.3.Case folding 35
3.1.2.Biểu diễn văn bản trên máy tính 35
3.1.2.1.Mô hình Boolean 35
3.1.2.2.Mô hình không gian Vector 36
3.1.3.Trích rút các câu từ văn bản gốc 37
3.1.4.Tạo bản tóm tắt 38
3
3.2.Tổng quan các phương pháp tự động tóm tắt văn bản 38
3.2.1.Các phương pháp heuristic 39
3.2.1.1.Phương pháp Keyword (Luhn 1958) 39
3.2.1.2.Phương pháp Title (Edmunson 1969) 40
3.2.1.3.Phương pháp Location (Edmunson 1969) 40
3.2.1.4.Phương pháp Aggregation Similarity 41
3.2.1.5.Phương pháp Cue 41
3.2.2.Phương pháp thống kê (Statistical based approach) 41
3.2.3.Phương pháp học máy 42
3.2.4.Phương pháp kết hợp (Hybrid approach) 43
4.1.Trích rút từ đơn, từ ghép sử dụng mô hình thống kê N-gram 44
4.2.Sinh dữ liệu huấn luyện 46
4.2.1.Sinh dữ liệu huấn luyện sử dụng phương pháp thống kê 46

7
Chương I: Giới thiệu
Trong những năm gần đây, chúng ta đang được chứng kiến sự phát
triển như vũ bão của World-Wide-Web. Theo thống kê của Lyman &
Varian năm 2003 có khoảng 4 tỷ trang web đã được indexed bởi
Google, khoảng 200TB dữ liệu trên Web [28] Và theo số liệu năm 2007
thì số website được indexed bởi Google đã lên tới 10 tỷ. Trước sự phát
triển đó thì một vấn đề đặt ra là làm thế nào con người có thể sử dụng
một cách hiệu quả lượng thông tin khổng lồ đó trên Internet? Đã có rất
nhiều nghiên cứu trên thế giới nhằm giải quyết bài toán này và đã thu
được những kết quả hết sức khả quan. Các nghiên cứu có thể kể đến là:
Hệ thống tổ chức, tìm kiếm thông tin (Information Retrieval – IR), gom
cụm dữ liệu, trích rút thông tin, trả lời câu hỏi, tóm tắt văn bản…[28]
Trong đó tự động tóm tắt văn bản là công cụ rất quan trọng, nó giúp
người sử dụng giảm được thời gian xử lý và nhanh chóng có được thông
tin cần thiết.
Ngày nay, các công cụ tìm kiếm trên Internet đã rất phát triển, hỗ
trợ đắc lực người sử dụng tìm kiếm những thông tin cần thiết. Một số
công cụ tìm kiếm có thể kể đến như: Google.com, Yahoo.com… và ở
Việt Nam có socbay.com.vn, timnhanh.com… Tất cả các công cụ tìm
kiếm này đều thực hiện tìm kiếm dựa trên từ khóa và kết quả trả về có
thể hàng nghìn, hàng vài trăm nghìn kết quả. Chính lượng kết quả trả
nhiều như vậy có thể làm người sử dụng bị choáng ngợp, không biết
nên chọn kết quả nào. Do đó, một công việc hết sức cần thiết là giúp
người sử dụng sàng lọc được lượng thông tin khổng lồ đó và nhanh
chóng chọn được tài liệu thích hợp nhất. Chúng ta thử tưởng tượng, với
mỗi kết quả tìm kiếm được có một bản tóm tắt ngắn gọn những nội
dung chính hoặc các kết quả trả về được chia thành các nhóm tài liệu
khác nhau, với mỗi nhóm có một bản tóm tắt nội dung của nó. Như vậy,
8

Có rất nhiều khái niệm về tự động tóm tắt văn bản, tuy nhiên chúng
ta có thể hiểu như sau: Tự động tóm tắt văn bản là tự động tạo ra một
văn bản mới ngắn gọn nhưng chứa nội dung chính của một (hay một
vài) tài liệu (cùng loại) [30] Kích thước của bản tóm tắt được giới hạn
là không dài quá ½ kích thước của tài liệu gốc [8].[27]
Bài toán tự động tóm tắt văn bản là một bài toán phức tạp vì nó
liên quan đến rất nhiều lĩnh vực như: thống kê, ngôn ngữ học, trí tuệ
nhân tạo (làm thế nào để máy tính có thể hiểu được ngôn ngữ tự nhiên
như con người). Ngoài ra nó còn phụ thuộc vào đặc thù của từng ngôn
ngữ. Song đây là một bài toán có ý nghĩa thực tế rất cao đặc biệt trong
bối cảnh hiện nay, trước một lượng thông tin khổng lồ trên Internet, mà
chủ yếu ở dạng text. Một trong những ứng dụng có ý nghĩa hết sức quan
trọng của bài toán này là ứng dụng trong lĩnh vực quốc phòng an ninh.
Như chúng ta đã biết, Internet phát triển đem đến cho loài người rất
nhiều sự tiện lợi, tuy nhiên sẽ có những mặt trái của nó, sẽ có những cá
nhân hoặc tổ chức lợi dụng Internet để phát tán các thông tin không
chính xác, phản động. Việc xác định những thông tin nào là có lợi,
thông tin nào là không chính xác đòi hỏi phải có một đội ngũ nhân viên
xử lý các văn bản. Với sự phát triển của Internet, lượng văn bản được
cập nhật lên mạng là vô cùng lớn và nhanh chóng, điều đó dẫn tới vấn
đề là liệu các nhân viên chuyên xử lý văn bản đó có xử lý kịp thời
không? Chắc chắn là khó có thể xử lý kịp. Do đó, cần phải có các phần
mềm trích rút thông tin, gom cụm dữ liệu, tóm tắt văn bản để giúp các
nhân viên xử lý văn bản giảm thời gian tìm kiếm, xử lý, phân loại văn
bản.
10
Chính vì những ý nghĩa hết sức to lớn của bài toán tự động tóm tắt
văn bản nên hiện nay nó vẫn được giới học thuật trong và ngoài nước
tiếp tục nghiên cứu. Đặc biệt khi mà vẫn chưa có một phần mềm nào
thực hiện tự động tóm tắt văn bản tiếng Việt thì đề tài này sẽ hứa hẹn

áp dụng là: Kupiec, Pedersen, and Chen (1995) đã sử dụng mạng
Bayesian để thực hiện tóm tắt các báo cáo khoa học; Aone et al (1999)
và Lin (1999) đã thử nghiệm các phương pháp học máy khác nhau và so
sánh kết quả của chúng với nhau;… Ngoài ra có một số các nghiên cứu
khác lại dựa vào ngôn ngữ học [27]
Các kỹ thuật tóm tắt đơn văn bản không phải trích rút thì được xếp
vào loại tóm lược. Witbrock và Mittal (1999) thực hiện chọn ra một tập
các từ (word) từ tài liệu gốc, sau đó tổ chức các từ này thành các câu sử
dụng mô hình ngôn ngữ n-gram. Jing và McKeown (1999) thực hiện kỹ
thuật “cut and paste” các đoạn trong tài liệu gốc, sau đó sẽ kết hợp các
đoạn đã trích rút được để tạo bản tóm tắt. Ngoài ra một phương pháp
khác là từ các câu đã trích rút, sẽ thực hiện cắt bỏ phần dư thừa của mỗi
câu, sau đó bản tóm tắt được sinh ra bằng cách hoặc là sử dụng các câu
đã được tối giản hoặc kết hợp một số câu tối giản thành câu mới. Một
nghiên cứu theo hướng này đó là của Knight và Macru (2000) [27]
Bài toán tóm tắt đa văn bản là bài toán mới được nghiên cứu
khoảng từ năm 2000 trở lại đây. Bài toán có thể được phát biểu như
sau: Tự động tóm tắt đa văn bản là tự động tạo ra bản tóm tắt nội dung
chính từ một số văn bản cùng loại (cùng chủ đề). Đây là bài toán rất
hay, rất có ý nghĩa trong thực tế. Chẳng hạn như, sau khi thực hiện các
kỹ thuật tự động phân loại, gom cụm kết quả tìm kiếm từ search engine,
12
một chương trình tự động tóm tắt nội dung các tài liệu trong mỗi cụm,
hoặc một hệ thống tổng hợp tin tức từ các trang web tin tức khác nhau.
Bài toán tự động tóm tắt đa văn bản có ba vấn đề chính cần được
giải quyết đó là [14].: một là, nhận ra các thông tin dưa thừa; hai là số
lượng văn bản đầu vào và kích thước bản tóm tắt; ba là bản tóm tắt phải
bảo đảm tính mạch lạc. Đây thật sự là ba thách thức lớn bởi vì:
- Với vấn đề thứ nhất: Vì các văn bản đầu vào là cùng loại (cùng
chủ đề) nên nó sẽ chứa những câu quan trọng ở các văn bản khác

quả tóm tắt tốt hơn, lời văn sẽ muợt mà hơn. Tuy nhiên, nếu làm không
tốt thì câu văn sẽ rất lủng củng. Cách thực hiện dễ hơn là trích rút, với
cách thực hiện này có thể tạo ra bản tóm tắt bằng các kết nối các đơn vị
trích rút được. Điều này có thể dẫn tới lời văn không được mượt mà.
Chúng ta cần phải có các kỹ thuật để làm trơn (smoothing) để tạo bản
tóm tắt được mạch lạc, dễ hiểu.
 Tóm tắt chỉ định và tóm tắt thông tin
Tóm tắt chỉ định là tạo ra bản tóm tắt với mục đích giúp người sử
dụng quyết định có nên đọc tài liệu đó không [30].? Dạng tóm tắt này
được ứng dụng trong các hệ thống tìm kiếm thông tin (google,
yahoo…).
Còn tóm tắt thông tin là tạo ra bản tóm tắt chứa đầy đủ những
những nội dung chính của tài liệu, nó có thể được dùng để thay thế tài
liệu gốc. Dạng tóm tắt này thường được ứng dụng để trợ giúp các
chuyên viên xử lý văn bản, giúp họ giảm thời gian xử lý một khối lượng
văn bản lớn.
14
1.1.3. Các tiêu chí đánh giá
Đi kèm với việc tóm tắt văn bản thì việc đánh giá chất lượng của
bản tóm tắt cũng là một vấn đề cần phải được nghiên cứu. Để đánh giá
chất lượng một bản tóm tắt người ta thường dựa vào các tiêu chí sau:
 Độ rút gọn: Là tỷ lệ giữa kích thước bản tóm tắt trên kích thước
tài liệu gốc. Kích thước của tài liệu có thể đo bằng số câu, số từ,
số ký tự,…
 Độ chính xác: Thể hiện xem bản tóm tắt có thể hiện chính xác
nội dung chính của tài liệu gốc hay không
 Độ liên kết: Là thể hiện xem bản tóm tắt có “trơn” hay không?
Nghĩa là bản tóm tắt phải bảo đảm về mặt văn học, nó phải liền
mạch, không rời rạc, lủng củng.
1.1.4. Giới hạn đề tài

lớn.
 Xây dựng Module thực hiện sinh dữ liệu tự động phục vụ cho quá
trình huấn luyện, kiểm thử và đánh giá kết quả.
 Cài đặt 3 phương pháp khác nhau tự động tóm tắt văn bản: TF-
IDF, kết hợp các phương pháp thống kê và cuối cùng là phương
pháp học máy thống kê Entropy cực đại.
 Xây dựng bộ dữ liệu kiểm thử bằng cách nhờ các chuyên gia ngôn
ngữ và một số bạn sinh viên tạo bản tóm tắt bằng trích rút các câu
quan trọng.
 Sử dụng độ đo PR để đánh giá kết quả thực hiện của các phương
pháp đã cài đặt.
1.3. Bố cục đồ án
Bài báo cáo này được tổ chức như sau:
16
Chương I: Giới thiệu về bài toán tự động tóm tắt văn bản, ý nghĩa
thực tế của bài toán, phân loại và các tiêu chí đánh giá chất lượng bản
tóm tắt. Trong phần này chúng tôi cũng đưa ra giới hạn nghiên cứu của
đề tài, tóm tắt những kết quả đã đạt được và bố cục của báo cáo
Chương II: Chương này trình bày một số mô hình cơ bản mà sẽ
được sử dụng trong đồ án này. Mô hình chúng tôi giới thiệu đầu tiên là
mô hình thống kê N-gram, mô hình này sẽ được áp dụng giải bài toán
text segmentation. Tiếp theo chúng tôi sẽ trình bày những lý thuyết cơ
bản về hai mô hình học máy thống kê: Mô hình Markov ẩn và mô hình
Entropy cực đại. Mô hình Markov ẩn sẽ được sử dụng trong việc sinh
dữ liệu huấn luyện, còn mô hình Entropy cực đại được sử dụng thực
hiện tóm tắt văn bản.
Chương III: Trong chương này, chúng tôi sẽ trình bày mô hình
chung giải quyết bài toán tự động tóm tắt văn bản. Chi tiết các bước
thực hiện cũng như các kỹ thuật thường được sử dụng trong mỗi bước.
Tiếp theo, chúng tôi trình bày tổng quan các kỹ thuật tự động tóm tắt

ghép đôi hoặc ghép ba, ghép bốn hoặc nhiều hơn. Ví dụ, “tôi”, “học”,
“nhà” là các từ đơn; “tôi tớ”, “học hành”, “nhà cửa” là các từ ghép đôi;
“trường đại học”, “bộ quốc phòng” là các từ ghép ba. Xét về góc độ
ngữ nghĩa thì các cụm từ bộ ba trở lên gồm các từ bộ đôi và từ đơn kết
hợp lại [1] Do vậy, trong nghiên cứu này chúng tôi sẽ nghiên cứu hai
loại N-Gram là: unigram (đơn) và bigram (đôi) là đủ để thống kê và xét
ngữ nghĩa của từ.
Trong các văn bản tiếng Việt thì từ ghép chiếm tỷ lệ cao hơn từ
đơn. Đưa ra một câu tiếng Việt, chúng ta có thể dễ dàng xác định được
đâu là từ đơn, đâu là từ ghép. Tuy nhiên, để máy tính có thể làm được
điều này thì lại là một bài toán không đơn giản. Trong lĩnh vực khai phá
dữ liệu văn bản, bài toán này được gọi là text segmentation. Với cách
tiếp cận thống kê ngôn ngữ theo mô hình N-Gram, chúng ta có thể xác
định được từ đơn, từ ghép trong mỗi câu trong văn bản. Có nghĩa là nó
19
có thể giải quyết cho bài toán text segmentation. Sau đây chúng tôi sẽ
trình bày những kiến thức cơ bản về mô hình thống kê ngôn ngữ N-Gram.
Những kiến thức này sẽ được sử dụng trong thuật toán trích rút từ đơn,
từ ghép tiếng Việt.
• Ước lượng xác suất n-gram
Xác suất mô hình n-gram được ước lượng bằng việc thống kê
(đếm) dãy các từ với số lượng lớn các văn bản trên nhiều lĩnh vực khác
nhau. Nói chung, càng nhiều, càng phong phú càng tốt.
Gọi C(w) là số lần xuất hiện của từ w trong tổng số N từ. Xác suất
ước lượng là:
N
wC
wP
)(
)(

• Tính xác suất của cụm từ
Cho một cụm từ , xác suất của cụm từ này được tính
theo công thức xác suất có điều kiện Bayes như sau:
20
2.2. Mô hình Markov ẩn
Mô hình Markov ẩn được mở rộng từ khái niệm mô hình Markov.
Để hiểu được mô hình Markov ẩn, trước hết chúng ta cần phải hiểu
được quá trình Markov. Trong phần này chúng tôi sẽ trình bày những
kiến thức cơ bản về quá trình Markov rời rạc, sau đó sẽ trình bày về mô
hình Markov ẩn.
2.2.1. Quá trình Markov rời rạc
Xét một hệ thống mà tại mỗi thời điểm hệ ở một trạng thái trong
một tập N trạng thái khác nhau S
1
, S
2
, …, S
N
[26]
Ví dụ: Một hệ thống gồm N = 5 trạng thái được mô phỏng như hình sau:
Hình 2. 1. Xích Markov có 5 trạng thái (S
1
, S
2
, S
3
, S
4
, S
5

điểm t chỉ phụ thuộc vào trạng thái của hệ thống tại thời điểm t-1. Nếu
hệ thống tại thời điểm t-1 đang ở trạng thái đèn đỏ thì trạng thái của hệ
thống tại thời điểm t sẽ phải là đèn xanh. Chúng ta nhận thấy rằng việc
chuyển trạng thái là đã được xác định, nghĩa là nếu hiện tại đèn đỏ thì
thời điểm tiếp theo hệ sẽ chuyển sang đèn xanh với xác suất là 1.
Ví dụ 2: Về việc dự báo thời tiết cho mỗi ngày. Giả sử thời tiết cho
mỗi ngày có 3 dạng {Nắng, Mưa, Mây), không như trong ví dụ 1, việc
chuyển trạng thái thời tiết với xác suất có giá trị trong khoảng [0, 1]. Giả
sử ta có ma trận xác suất chuyển như sau:
Thời
tiết
ngày
hôm
qua
Thời tiết ngày hôm nay
Nắng Mây Mưa
Nắng 0.5 0.25 0.25
Mây 0.375 0.125 0.375
Mưa 0.125 0.625 0.375
Bảng 2. 1. Bảng xác suất chuyển trong dự báo thời tiết
22
Nghĩa là, nếu ngày hôm qua trời Nắng thì hôm nay trời Nắng với
xác suất 0.5, Mây và Mưa với cùng xác suất 0.25. Chúng ta cũng thấy
rằng tổng xác suất trên một cột là bằng 1.
Để hệ thống hoạt động được thì chúng ta cần phải có bước khởi
tạo, cụ thể là khởi tạo trạng thái thời tiết. Chúng ta sử dụng một vector
khởi tạo gọi là vector
π
. Chẳng hạn như chúng ta khởi tạo
)0,0,1(

Định nghĩa HMM: Một mô hình Markov ẩn là một bộ ba (
),, BA
π
trong đó
-
π
: Vector của xác suất trạng thái khởi tạo
- A = (a
ij
) là ma trận xác suất chuyển, a
ij
= P(q
t
= S
j
|q
t-1
= S
i
);
- B = (b
ij
) với b
ij
= P(y
i
|x
j
) là xác suất quan sát y
i

, và một chuỗi các
quan sát O = {o
1
, o
2
, … o
T
}. Hãy tính chuỗi các trạng thái ẩn tốt nhất
của mô hình để có chuỗi quan sát O.
Bài toán này được giải quyết bằng cách sử dụng thuật toán Viterbi
• Learning
Phát biểu bài toán: Cho mô hình Markov ẩn
λ
, và một chuỗi các
quan sát O = {o
1
, o
2
, … o
T
}. Chúng ta cần thay đổi các biến của mô hình
),,(
π
BA
như thế nào để
)|(
λ
OP
đạt giá trị lớn nhất.
2.3. Mô hình Maximum Entropy