Tài liệu Xác định các hệ số đặc trưng bằng giải thuật di truyền cho bài toán tóm tắt văn bản Tiếng Việt - Nguyễn Nhật An: Kỹ thuật điện tử & Khoa học mỏy tớnh
N. N. An, N. Q. Bắc, N. Đ. Hiếu, T. N. Anh,“Xỏc định cỏc hệ số văn bản tiếng Việt.” 36
Xác định các hệ số đặc trưng
bằng giảI thuật di truyền cho bài toán
tóm tắt văn bản tiếng việt
NGUYỄN NHẬT AN*, NGUYỄN QUANG BẮC*,
NGUYỄN ĐỨC HIẾU**, TRẦN NGỌC ANH**
Túm tắt: Túm tắt văn bản là quỏ trỡnh rỳt gọn văn bản mà vẫn giữ được
những thụng tin quan trọng. Bài bỏo này đề xuất một tiếp cận mới trong túm tắt
văn bản tiếng Việt theo hướng trớch rỳt (Extraction Summarization) dựa trờn cỏc
đặc trưng quan trọng như vị trớ cõu, độ dài cõu, trọng số TFxISF, xỏc suất thực
từ, độ tương tự với chủ đề, cõu trung tõm... Đầu tiờn, chỳng tụi xỏc định tập đặc
trưng quan trọng trong văn bản tiếng Việt. Bước tiếp theo sử dụng giải thuật di
truyền để xỏc định hệ số cỏc đặc trưng từ kho ngữ liệu huấn luyện. Thử nghiệm
túm tắt văn bản với cỏc hệ số thu được từ giải thuật di truyền cho thấy, văn bản
túm tắt cú độ chớnh xỏc cao, cú thể ỏp dụng t...
11 trang |
Chia sẻ: quangot475 | Lượt xem: 506 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Xác định các hệ số đặc trưng bằng giải thuật di truyền cho bài toán tóm tắt văn bản Tiếng Việt - Nguyễn Nhật An, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Kỹ thuật điện tử & Khoa học máy tính
N. N. An, N. Q. Bắc, N. Đ. Hiếu, T. N. Anh,“Xác định các hệ số văn bản tiếng Việt.” 36
X¸c ®Þnh c¸c hÖ sè ®Æc trng
b»ng gi¶I thuËt di truyÒn cho bµi to¸n
tãm t¾t v¨n b¶n tiÕng viÖt
NGUYỄN NHẬT AN*, NGUYỄN QUANG BẮC*,
NGUYỄN ĐỨC HIẾU**, TRẦN NGỌC ANH**
Tóm tắt: Tóm tắt văn bản là quá trình rút gọn văn bản mà vẫn giữ được
những thông tin quan trọng. Bài báo này đề xuất một tiếp cận mới trong tóm tắt
văn bản tiếng Việt theo hướng trích rút (Extraction Summarization) dựa trên các
đặc trưng quan trọng như vị trí câu, độ dài câu, trọng số TFxISF, xác suất thực
từ, độ tương tự với chủ đề, câu trung tâm... Đầu tiên, chúng tôi xác định tập đặc
trưng quan trọng trong văn bản tiếng Việt. Bước tiếp theo sử dụng giải thuật di
truyền để xác định hệ số các đặc trưng từ kho ngữ liệu huấn luyện. Thử nghiệm
tóm tắt văn bản với các hệ số thu được từ giải thuật di truyền cho thấy, văn bản
tóm tắt có độ chính xác cao, có thể áp dụng tốt trong thực tế.
Từ khóa: Tóm tắt văn bản tiếng Việt, Đặc trưng văn bản, Hệ số đặc trưng văn bản, Giải thuật di truyền.
1. ĐẶT VẤN ĐỀ
Trong thời đại bùng nổ thông tin điện tử, nhu cầu tự động tổng hợp thông tin nổi bật từ
kho văn bản điện tử khổng lồ đó trở nên đặc biệt quan trọng và được sự quan tâm rộng rãi.
Tóm tắt văn bản là quá trình rút gọn văn bản mà vẫn giữ được những thông tin quan trọng
của văn bản. Kỹ thuật tóm tắt văn bản được các nhà nghiên cứu phân ra thành hai loại là:
tóm tắt văn bản là tóm tắt rút trích ES(Extraction Summarization) và tóm tắt tóm lược
AS(Abstraction Summarization)[17]. Đối với tóm tắt văn bản tiếng Việt, các nghiên cứu
chủ yếu dựa theo hướng tiếp cận ES là thông qua tính toán các đặc trưng tần suất từ, vị trí
câu, từ tiêu đề, độ tương tự... để chọn ra các câu quan trọng nhất theo tỉ lệ trích rút
[3,4,5,6,7,8]. Tuy nhiên, các nghiên cứu đều chưa chỉ ra được việc sử dụng hệ số các đặc
trưng như thế nào là hợp lý để cho bản tóm tắt tốt và chưa xây dựng được một phương
pháp tính toán các hệ số thông qua quá trình học.
Đối với ngôn ngữ tiếng Anh, vấn đề nêu trên đã được một số nhà nghiên cứu giải quyết
theo hướng học máy bằng giải thuật di truyền [12,13] và cho kết quả khả quan. Tuy nhiên,
khó có thể áp dụng trực tiếp cho tiếng Việt vì các đặc trưng ngôn ngữ tiếng Việt và tiếng
Anh khác nhau (do loại hình ngôn ngữ, do nền văn hóa) chẳng hạn: khác biệt về ngữ âm
học, hình vị, ranh giới từ, từ loại; trật tự từ (tính từ và danh từ), kết cấu câu (chủ đề và cụm
chủ vị), Do vậy, các đặc trưng văn bản tiếng Anh và tiếng Việt là khác nhau. Mặt khác,
do tiếng Việt chưa xây dựng được từ điển, kho ngữ liệu đầy đủ và chưa có Vietworknet
nên sử dụng các phương pháp tiếng Anh áp dụng cho tiếng Việt không mấy hiệu quả.
Nhận thấy đây là một hướng nghiên cứu mới trong tiếng Việt, do đó trong bài báo này
chúng tôi sẽ nghiên cứu, đề xuất hướng tiếp cận mới trong tóm tắt văn bản tiếng Việt bằng
giải thuật di truyền dựa trên các đặc trưng văn bản quan trọng.
Nghiên cứu giải quyết hai vấn đề chính: Một là, xác định tập đặc trưng quan trọng của
văn bản tiếng Việt; hai là, xác định bộ hệ số đặc trưng bằng giải thuật di truyền thông qua
quá trình học tập văn bản tóm tắt mẫu. Từ bộ hệ số đặc trưng đó, chúng tôi tiến hành thử
nghiệm tóm tắt văn bản và đánh giá chúng.
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số 32, 08 - 2014 37
Nghiên cứu được trình bày theo thứ tự sau: Phần 2 trình bày nội dung nghiên cứu; Phần
3 trình bày các kết quả thử nghiệm, và so sánh đánh giá; cuối cùng kết luận được trình bày
trong Phần 4.
2. NỘI DUNG CẦN GIẢI QUYẾT
2.1. Bài toán tóm tắt đơn văn bản tiếng Việt theo hướng trích rút
Quy trình thực hiện tóm tắt đơn văn bản tổng quát theo hướng trích rút:
Bước 1. Tiền xử lý văn bản đầu vào: tách câu, tách từ, gán nhãn, lọc bỏ các hư từ.
Bước 2. Tính trọng số các câu theo các đặc trưng văn bản như.
Bước 3. Sắp xếp các câu theo trọng số, rút trích các câu có trọng số cao theo tỉ lệ.
Bước 4. Xuất các câu đã rút trích theo thứ tự xuất hiện trong văn bản gốc.
Hình 1. Quy trình tóm tắt đơn văn bản tổng quát.
Công thức tổng quát để tính trọng số câu thông qua tập đặc trưng quan trọng được mô
tả như sau:
z
1
i ti
i
Score s k Score s
(1)
trong đó, z số đặc trưng, tiScore s là trọng số của các đặc trưng trong câu s, ti là đặc
trưng thứ i của văn bản.
Qua đây, ta có thể nhận xét rằng, bài toán tóm tắt đơn văn bản tiếng cần xác định được
2 yếu tố quan trọng là:
- Xác định tập đặc trưng quan trọng của văn bản tiếng Việt
- Xác định bộ hệ số đặc trưng như thế nào?
Phần tiếp theo chúng tôi sẽ trình bày rõ tập đặc trưng quan trọng của văn bản tiếng Việt
và cách xác định bộ hệ số đặc trưng.
2.2. Xây dựng tập đặc trưng văn bản quan trọng cho văn bản tiếng Việt
Để xây dựng tập đặc trưng văn bản tiếng Việt, chúng tôi sử dụng quan điểm phân loại
từ vựng tiếng Việt của Diệp Quang Ban[1]. Theo tác giả, từ loại tiếng Việt được chia làm
hai loại chính là thực từ và hư từ. Thực từ là những từ có ý nghĩa từ vựng (nghĩa là mang
thông tin) còn hư từ là những từ chỉ có chức năng ngữ pháp (không mang thông tin). Do
vậy, chúng tôi chỉ tiến hành tính toán các đặc trưng dựa trên thực từ, còn hư từ bị loại bỏ.
Ngoài ra, ở bước tiền xử lý, để nâng cao độ chính xác, các thực từ đồng nghĩa trong tiêu
đề, nội dung được thay thế bằng một từ duy nhất bằng cách sử dụng từ điển đồng nghĩa
của tác giả Nguyễn Văn Tu[2].
2.2.1. Ví trí câu
Định nghĩa 1: Độ quan trọng của câu của văn bản dựa theo đặc trưng vị trí được xác
định là giá trị vị trí của câu trong một đoạn văn bản.
Đối với văn bản tiếng Việt thường câu đầu tiên trong đoạn là quan trọng nhất. Giả sử s
là một câu trong văn bản gốc, k là vị trí của câu s trong đoạn văn bản chứa câu s. Độ quan
trọng của câu trong một đoạn văn bản được tính theo công sau:
1
1
fScore s
k
(2)
Văn
bản
TIỀN
XỬ LÝ:
Tách câu,
tách từ,
gán nhãn,
loại hư
TÍNH
TRỌNG
SỐ CÂU
theo
các đặc
trưng
SẮP
XẾP
theo
trọng số,
rút trích
theo tỉ lệ
XUẤT
CÂU
Theo tứ
tự xuất
hiện
trong văn
Văn bản
Tóm
tắt
Kỹ thuật điện tử & Khoa học máy tính
N. N. An, N. Q. Bắc, N. Đ. Hiếu, T. N. Anh,“Xác định các hệ số văn bản tiếng Việt.” 38
2.2.2. Trọng số TF.ISF(term frequency- inverse sentence frequency)
Định nghĩa 2: Độ quan trọng của câu trong văn bản dựa theo đặc trưng trọng số
TF.ISF được tính bằng giá trị trung bình cộng các trọng số TF.ISF của các thực từ trong
câu.
Phương pháp này bắt nguồn từ công thức nổi tiếng TFxIDF( term frequency – inverse
document frequency), được sử dụng để xác định mức độ quan trọng của từ trong một văn
bản, mà văn bản đó nằm trong một tập hợp các văn bản. Công thức này phù hợp với bài
toán tóm tắt đa văn bản. Ở đây, chúng tôi tiếp cận bài toán đơn văn bản nên tính độ quan
trọng của câu trong một câu thông qua trung bình cộng độ quan trọng của thực từ trong
câu (TFxISF: term frequency- inverse sentence frequency):
2
1
1
,
wN
f k k
kw
Score s TF w s ISF w
N
(3)
trong đó, wk là thực từ thứ k trong câu s, Nw là số các thực từ có trong câu s, ,kTF w s
là số lần xuất hiện của thực từ wk trong câu s,
s
k
k
N
ISF w log
SF w
là nghịch đảo của
tần suất từ wk , NS là là tổng số câu có trong văn bản, SF(wk) là tổng số câu trong văn bản
có chứa thực từ wk.
2.2.3. Độ dài câu
Định nghĩa 3: Độ quan trọng của câu trong văn bản dựa theo đặc trưng độ dài câu
được tính bằng giá trị phân bố độ dài câu tính theo thực từ trong kho ngữ liệu lớn.
Theo quan điểm của chúng tôi, công thức độ dài câu được xây dựng dựa theo số thực
từ mà câu đó chứa. Do vậy, khác với quan điểm của các nghiên cứu trước đây là câu quá
ngắn hoặc quá dài đều không chứa trong văn bản tóm tắt. Chúng tôi sử dụng đặc trưng độ
dài câu cho tất cả các câu trong văn bản thông qua độ đo được tính toán qua quá trình khảo
sát kho ngữ liệu tiếng Việt.
Hình 2. Sơ đồ phân bố độ dài câu tính theo thực từ của ~ 20.000 văn bản tiếng Việt
được chuẩn hoá về đoạn [0,1].
Công thức độ dài câu được xây dựng như sau:
2
2
3
2
, 0 12
, 12
22
f
ax bx c x
Score s x
exp x
(4)
trong đó, a = - 0.00529, b = 0.12174, c = 0.3; = 26.3 , = 11.5, = 10.5
2.2.4. Xác suất thực từ
Định nghĩa 4: Độ quan trọng của câu trong văn bản dựa theo đặc trưng xác xuất thực
từ được tính bằng giá trị trung bình cộng xác suất unigram của các thực từ trong câu.
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số 32, 08 - 2014 39
Đặc trưng này sử dụng xác suất unigram của các thực từ để làm nền tảng tính toán
trọng số câu. Câu có chứa nhiều thực từ có tần suất xuất hiện cao trong toàn văn bản thì
câu đó càng quan trọng.
4
1
1 wN
f k
w k
Score s P w
N
(5)
trong đó,
k
k
uni
C w
P w
N
xác suất unigram của từ wk, C(wk) là số lần xuất hiện của thực từ
wk trong văn bản, Nuni là tổng số các thực từ (các unigram) trong văn bản.
2.2.5. Thực thể tên
Định nghĩa 5: Độ quan trọng của câu trong văn bản dựa theo đặc trưng thực thể tên
được tính bằng thương của số thực thể tên xuất hiện trong câu và số thực từ có trong câu.
Đặc trưng này đếm số của các thực thể tên (như danh từ riêng, từ viết tắt) trong một
câu. Trong nghiên cứu này, các thực thể có tên được nhận biết thông qua nhãn Np, Ny của
công cụ gán nhãn vnTagger[11].
5
name
f
w
N s
Score s
N s
(6)
trong đó, Nname(s) là số thực thể tên xuất hiện trong câu, Nw (s) số các thực từ có trong câu s.
2.2.6. Dữ liệu số
Định nghĩa 6: Độ quan trọng của câu trong văn bản dựa theo đặc trưng dữ liệu số
được tính bằng thương của số thực từ là dữ liệu số xuất hiện trong câu và số thực từ có
trong câu.
Đặc trưng này được đưa ra dựa theo quan điểm của một số nhà nghiên cứu tóm tắt văn
bản xem rằng các thuật ngữ được viết dưới hình thức số đôi khi truyền đạt thông tin quan
trọng. Đặc trưng này đếm số thực từ dạng dữ liệu số xuất hiện trong một câu được nhận
biết thông qua nhãn M của công cụ gán nhãn vnTagger[11]:
6
num
f
w
N s
Score s
N s
(7)
trong đó, numN s là số thuật ngữ dữ liệu số xuất hiện trong câu.
2.2.7. Tương tự với tiêu đề
Định nghĩa 7: Độ quan trọng của câu trong văn bản dựa theo đặc trưng tương tự với
tiêu đề được tính bằng phép đo đồng xuất hiện thực từ giữa câu và câu tiêu đề.
Đặc trưng này xem xét độ đồng xuất hiện thực từ giữa câu và câu tiêu đề của văn bản.
Được tính dựa theo phép đo đồng xuất hiện Dice[10]:
7 , 2f Dice
S T
Score s Sim S T
S T
(8)
trong đó, 1 2 , , , NS s s s là vetor thực từ khác nhau của câu, 1 2, , , MT t t t là vetor
thực từ khác nhau của câu tiêu đề, S T là số thực từ đồng xuất hiện trong S vàT .
2.2.8. Câu trung tâm
Định nghĩa 8: Độ quan trọng của câu trong văn bản dựa theo đặc trưng câu trung
tâm được tính bằng giá trị trung bình cộng xác độ tương tự giữa câu và các câu khác
trong văn bản.
Đặc trưng này xem xét độ đồng xuất hiện của các thực từ giữa một câu và các câu
khác trong văn bản. Đặc trưng này được tính toán dựa vào phương pháp Aggregation
Similarity [13], được mô tả bằng công thức sau:
Kỹ thuật điện tử & Khoa học máy tính
N. N. An, N. Q. Bắc, N. Đ. Hiếu, T. N. Anh,“Xác định các hệ số văn bản tiếng Việt.” 40
8
1,
,
m
f Dice i j
j j i
Score s Sim S S
(9)
Trong đó: ,Dice i jSim S S là phép đo đồng xuất hiện Dice giữa câu thứ i với câu thứ j
được tính tương tự như công thức (8).
2.3. Học hệ số các đặc trưng bằng giải thuật di truyền
Trong nghiên cứu này, chúng tôi đề xuất phương pháp kết hợp tuyến tính giữa 8 đặc
trưng được trình bày ở trên để tính điểm số cho câu. Những câu có điểm số cao được lựa
chọn tạo thành bản tóm tắt theo tỉ lệ người dùng mong muốn. Điểm số của câu được tính
như sau:
8
1
i fi
i
Score s k Score s
(10)
Trong đó: fiScore s là điểm số của đặc trưng i và ik là hệ số của nó.
Giải thuật di truyền là một trong những phát triển quan trọng của những nhà nghiên
cứu về tính toán ứng dụng cuối thế kỷ trước trong việc giải xấp xỉ các bài toán tối ưu toàn
cục. Mặt khác, giải thuật di truyền giản đơn khá đơn giản và thời gian tìm nghiệm toàn cục
nhanh. Do vậy, trong nghiên cứu này chúng tôi sử dụng giải thuật di truyền để tìm bộ hệ
số k của các đặc trưng thông qua quá trình học kho ngữ liệu do con người tóm tắt. Mô hình
học hệ số được mô tả trong hình 3.
Hình 3. Mô hình học hệ số đặc trưng bằng thuật toán di truyền.
Sau đây chúng ta sẽ lần lượt hình thức hóa bài toán tìm hệ số đặc trưng trên ngôn ngữ
của giải thuật di truyền.
Bài toán tìm hệ số đặc trưng cho bài toán tóm tắt văn bản được xác định bởi các dữ
liệu sau: 1 2 1 2 1 2, , , , , , , , , , , , ,m m nm a D d d d sh sh sh sh t t t t
trong đó, m là số văn bản đầu vào để học, a là tỷ lệ tóm tắt, t là các đặc trưng được sử dụng
để tóm tắt văn bản, đối với mỗi văn bản học thứ j:
jd là văn bản toàn văn chứa tiêu đề và
các câu nội dung,
jsh là bản tóm tắt con người của văn bản đó.
Bài toán đặt ra là tìm các hệ số đặc trưng k sao cho bản tóm tắt trích rút dựa vào các
đặc trưng theo tỉ lệ tóm tắt a "gần giống" với bản tóm tắt con người nhất.
Các đặc trưng
Tập văn bản mẫu
Tóm tắt bằng tay
Đánh giá độ thích nghi Khởi tạo quần
thể ban đầu
Xây dựng quần
thể mới
Điều kiện dừng
Nhiễm sắc thể
Chọn lọc
Lai ghép
Đột biến Bộ hệ số đặc
trưng k1,...,k8
đúng
sai
Tập văn bản mẫu
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số 32, 08 - 2014 41
Một bản "tóm tắt vàng" của hệ thống sinh ra theo quan điểm của chúng tôi cần đạt
được tiêu chí là chứa hầu hết các từ liên quan trong văn bản tóm tắt của con người. Độ đo
được định nghĩa như sau:
Định nghĩa 9: Độ đo đánh giá văn bản tóm tắt được định nghĩa bằng độ tương tự
giữa văn bản tóm tắt của hệ thống với văn bản tóm tắt con người (ROUGE-N):
, , ,
, , , ,
ii
ii
i
Sum a d t k SH
Sim Sum a d t k SH
SH
(11)
trong đó, 1, , , , , i iriSum a d t k sm sm là vector thực từ khác nhau của văn bản tóm
tắt của hệ thống theo bộ đặc trưng t và bộ hệ số k theo tỉ lệ tóm tắt a của văn bản di
1, ,i i ilSH sh sh là vector thực từ khác nhau của văn bản tóm tắt của con người của
văn bản di
Giả sử 1 2, , ns k k k là bộ hệ số đặc trưng chấp nhận được. Khi đó mô hình bài
toán tìm hệ số đặc trưng tóm tắt văn bản được phát biểu như sau:
1
, , , ,
, , , ,
m
ii
i
Sim Sum a d t k SH
DFC m a d sh t max
m
(12)
với miền ràng buộc:
1
1; 0
n
i i
i
k k
Sau đây chúng ta sẽ lần lượt hình thức hóa bài toán xác định hệ số đặc trưng bằng giải
thuật di truyền cho bài toán tóm tắt văn bản trên ngôn ngữ của giải thuật di truyền.
Biểu diễn bài toán. Chúng ta sử dụng nhiễm sắc thể có cấu trúc mã hoá là một vetor n
chiều 1 2 i, , , knk k k
để biểu diễn các cá thể (các điểm) trong không gian tìm kiếm.
Mỗi quần thể là một tập bao gồm một số cố định các cá thể.
Độ đo thích nghi . Với mỗi cá thể 1 2, , ns k k k ta xác định mức độ thích nghi của
cá thể, f(s), bằng công thức sau:
1
, , , , m ii
i
Sim Sum a d t k SH
f s
m
(13)
Toán tử lai ghép. Giả sử 1 11 12 1, , ns k k k và 2 21 22 2, , ns k k k là 2 cá thể bất
kỳ trong quần thể. Chúng ta đưa ra một số dạng toán tử lai ghép sau đây:
Giả sử z là một số được lựa chọn ngẫu nhiên, 1 z n . Từ hai cá thể cha mẹ là 1s và
2s mô tả trên, có thể tạo ra hai cá thể con
'
1s và
'
2s với các véc tơ cột tương ứng của
chúng được xác định như sau:
' '1 1 1 2 , 1, , ; , 1, ,i i i ik k i z k k i z n (14)
' '2 2 2 1 , 1, , ; , 1, ,i i i ik k i z k k i z n (15)
Toán tử đột biến phân phối đều: Với một gen i được chọn ngẫu nhiên để đột biến từ
cá thể 1 2, , ns k k k , thành phần ik được thay thế bởi một số ngẫu nhiên trong
khoảng xác định [ il , ]iu của ik . Cá thể s sau khi đột biến với các véc tơ cột tương ứng
của chúng được xác định như sau:
' ', ; , ; 1j j jk k j i k j i j n (16)
Kỹ thuật điện tử & Khoa học máy tính
N. N. An, N. Q. Bắc, N. Đ. Hiếu, T. N. Anh,“Xác định các hệ số văn bản tiếng Việt.” 42
i
Toán tử chọn lọc. Toán tử chọn lọc được xác định theo luật tỷ lệ thuận với mức độ
thích nghi:
s
s G
f s
p
f s
(17)
Trong đó s là cá thể và G là quần thể đang xem xét có chứa s.
THUẬT TOÁN GA HỌC HỆ SỐ ĐẶC TRƯNG
Input: , , , , m a D sh t
Output: Nghiệm tối ưu của bài toán , , , ,DFC m a D sh t là tập hệ số đặc trưng
1 2, , ns k k k
Bước 0. Khởi tạo quần thể gồm X cá thể 0 00 1 , , kG s s , trong đó:
0 0 0 01 2, , ; 1 i i i ins k k k i k
Bước 1. Giải các bài toán , , , , 1, , , 1, ,ti jSum a d t k i m j k , t là số thế hệ
thứ t của quần thể. Tính độ thích nghi , 1, ,tif s i k cho từng cá thể của tG theo (13).
Áp dụng toán tử chọn lọc (17) lên Gt để chọn ra K cá thể có mức độ thích nghi lớn nhất.
Bước 2. Nếu điều kiện dừng chưa thỏa mãn đến Bước 3. Ngược lại thuật toán dừng và
cho nghiệm tối ưu là bộ hệ số đặc trưng tối ưu.
Bước 3. Lựa chọn các cha-mẹ trong tG theo mức độ thích nghi để ghép cặp theo toán
tử lai ghép (14)-(15) để tạo nên tập các hậu thế lgtG với K1 phần tử.
Bước 4. Tác động toán tử đột biến (16) vào lgt tG G để nhận được 1tG , đặt t=t+1 và
quay lại bước 1.
2.4. Mô hình tóm tắt văn bản tiếng Việt dựa trên giải thuật di truyền
Như đã trình bày ở trên, chúng ta đã định nghĩa 8 đặc trưng của văn bản tiếng Việt và
cách xác định các hệ số đặc trưng ảnh hưởng đến bài toán tóm tắt văn bản như thế nào.
Sau khi xác định được hệ số các đặc trưng, ta có mô hình tóm tắt văn bản theo từng lĩnh
vực như hình 4:
Hình 4. Mô hình tóm tắt văn bản dựa trên giải thuật toán di truyền.
Tóm tắt bằng tay Các đặc trưng
Tập văn bản mẫu
GIẢI THUẬT DI TRUYỀN
Nhiễm sắc thể: 1 2 8, ,s k k k
Hàm thích nghi
1
, , , , m ii
i
Sim Sum a d t k SH
f s
m
Bộ hệ số đặc
trưng 1 2 8, ,k k k
Văn bản
Các đặc trưng
Văn bản tóm tắt
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số 32, 08 - 2014 43
3. THỬ NGHIỆM, ĐÁNH GIÁ
3.1. Biểu diễn nhiễm sắc thể
Mỗi nhiễm sắc thể của quần thể là một vector hệ số đặc trưng. Trong nghiên cứu này,
chúng tôi chỉ thử nghiệm với vector hệ số đặc trưng có chiều dài 40 bit biểu diễn 8 đặc
trưng, mỗi giá trị hệ số của từng đặc trưng được đại diện bởi 5 bit. Như vậy mỗi đặc trưng
sẽ có giá trị từ 0-31.
k1 k2 k3 k4 k5 k6 k7 k8
3.2. Quá trình đào tạo để học hệ số đặc trưng
Khởi tạo quần thể ban đầu gồm 100 cá thể với các nhiễm sắc thể được tạo ra ngẫu
nhiên (ki từ 0 đến 31). Tại mỗi vòng lặp của giải thuật di truyền, ở mỗi tài liệu đào tạo
điểm số các câu được tính theo công thức (10) và một bản tóm tắt được tạo ra theo tỉ lệ (số
câu tạo ra xấp xỉ số câu do con người tóm tắt). Quá trình nay lặp đi lặp lại đến khi độ
chính xác trung bình tính theo công thức (13) đạt xấp xỉ hoặc số thế hệ xấp xỉ 1000.
Nhiễm sắc thể được lựa chọn cuối cùng chính là bộ hệ số các đặc trưng được học thông
qua quá trình đào tạo (đã được chuẩn hoá để tổng các hệ số bằng 1).
3.3. Kho ngữ liệu
Ngữ liệu sử dụng trong bài báo này do chúng tôi tự xây dựng theo quan điểm thu thập
từ những trang báo mạng chính thống được biên tập cẩn thận. Trong cấu trúc của một bài
báo mạng thường được chia làm 3 phần: Tiêu đề, tóm tắt, nội dung. Chúng tôi xem phần
tóm tắt chính là phần tóm tắt của con người thực hiện. Do vậy, chúng tôi thu thập các văn
bản thuộc các lĩnh vực khác nhau với phần tóm tắt khoảng 100 từ để làm dữ liệu thử
nghiệm.
Ở bước tiền xử lý chúng tôi sử dụng các bộ công cụ sau:
- VnSentDetector (một gói của vnTokenizer) [11] để thực hiện tách câu tiếng Việt.
- Sử dụng các kỹ thuật tách từ của nhóm tác giả [14][15][16] được dùng để tách từ
tiếng Việt.
- Sử dụng bộ công cụ vnTagger[11] để gán nhãn từ loại với bộ 18 nhãn.
Bảng 1: Bảng ngữ liệu thử nghiệm báo Hà Tĩnh điện tử (
Lĩnh vực Chính trị Xã hội Kinh tế Thể thao
Số văn bản 1000 1000 1000 1000
3.4. Kết quả
Trong phần này, chúng tôi thực hiện xác định bộ hệ số 8 đặc trưng thông qua quá trình
đào tạo 80% văn bản mẫu bằng giải thuật di truyền với hàm thích nghi (13). Trong quá
trình đào tạo, giải thuật di truyền sẽ được thực hiện với các bước như sau:
Có 100 cá thể trong một quần thể.
Xác suất lai ghép 0.8
Xác suất đột biến 0.1
Thuật toán dừng khi đạt được 1000 thế hệ.
Tỷ lệ tóm tắt là 30%.
Trong mỗi lần thử nghiệm, mỗi lĩnh vực chúng tôi dùng 80% văn bản được sử dụng để
đào tạo và 20% văn bản dùng để thử nghiệm đánh giá. Thực hiện 5 lần chạy và đánh giá
kết quả trung bình.
Kỹ thuật điện tử & Khoa học máy tính
N. N. An, N. Q. Bắc, N. Đ. Hiếu, T. N. Anh,“Xác định các hệ số văn bản tiếng Việt.” 44
Bảng 2 cho thấy hệ số trung bình của mỗi đặc trưng văn bản được tính thông qua mô
hình đào tạo bằng giải thuật di truyền thông qua 5 lần thực hiện.
Bảng 2. Bảng kết quả hệ số đặc trưng.
Đặc trưng
Hệ số trung bình
Chính trị Xã hội Kinh tế
Thể
thao
F1 – Vị trí câu 0.20 0.16 0.11 0.16
F2- Trọng số TF.ISF (term frequency-
inverse sentence frequency) 0.05 0.09 0.06 0.03
F3 – Độ dài câu 0.03 0.03 0.03 0.06
F4 – Xác suất thực từ 0.16 0.11 0.09 0.21
F5- Danh từ riêng 0.04 0.20 0.22 0.10
F6- Dữ liệu số 0.17 0.03 0.06 0.03
F7 – Độ tương đồng giữa câu với tiêu
đề 0.16 0.19 0.19 0.22
F8- Câu trung tâm 0.20 0.20 0.23 0.18
Độ chính xác trung bình ROUGE-N
theo tỉ lệ tóm tắt 30%
46% 45% 48% 42%
Qua kết quả, chúng ta có thể thấy rằng, mỗi lĩnh vực sẽ có một bộ hệ số đặc trưng
khác nhau, trong đó các hệ số đặc trưng có kết quả cao phản ảnh sự quan trọng của đặc
trưng đó. Đặc trưng vị trí câu, xác suất thực từ, độ tương đồng với tiêu đề, câu trung tâm là
các đặc trưng có tính chất quan trọng trong cả 4 lĩnh vực, đặc trưng độ dài câu có hệ số
thấp phản ảnh đặc trưng này đóng vai trò không đáng kể trong tóm tắt văn bản. Các đặc
trưng còn lại phản ảnh mức độ quan trọng tuỳ vào từng lĩnh vực cụ thể. Ví dụ như, trong
lĩnh lực chính trị, đặc trưng dữ liệu số quan trọng, danh từ riêng không quan trọng nhưng
trong lĩnh vực xã hội, kinh tế và thể thao thì lại ngược lại.
Thực hiện thử nghiệm tóm tắt trên 20% văn bản mẫu còn lại bằng các bộ hệ số đặc
trưng trên trong từng lĩnh vực (trọng số câu được tính theo công thức 10). Kết quả tóm tắt
được đánh giá dựa trên độ ROUGE-N – độ đo đồng xuất hiện giữa văn bản do con người
tóm tắt và hệ thống (công thức 11).
Bảng 3. Bảng đánh giá độ chính xác trung bình của mô hình tóm tắt sử dụng thuật
toán di truyền.
Lĩnh vực
(20 văn bản mẫu, tỉ lệ tóm tắt 30%)
Độ chính xác trung bình(%)
ROUGE-N (N=1)
Chính trị 46 %
Xã hội 43%
Kinh tế 48%
Thể thao 43%
4. KẾT LUẬN
Bài báo này đã trình bày hướng tiếp cận mới trong tóm tắt đơn văn bản tiếng Việt theo
hướng trích rút dựa trên giải thuật di truyền. Nghiên cứu tập trung giải quyết hai vấn đề
trọng tâm:
- Xác định 8 đặc trưng quan trọng của văn bản tiếng Việt.
- Xác định các hệ số đặc trưng văn bản bằng giải thuật di truyền thông qua quá trình
học kho văn bản tóm tắt mẫu.
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số 32, 08 - 2014 45
Qua quá trình thử nghiệm tập văn bản thuộc 4 lĩnh vực chính trị, kinh tế, xã hội, thể
thao (mỗi lĩnh vực 1000 văn bản với tóm tắt con người bao gồm hơn 100 từ) chúng tôi
nhận thấy một số đặc trưng có ảnh hưởng lớn đến kết quả tóm tắt văn bản như vị trí câu,
xác suất thực từ, độ tương tự với tiêu đề, câu trung tâm. Đặc trưng độ dài câu đóng vai trò
không đáng kể, các đặc trưng còn lại phụ thuộc vào lĩnh vực văn bản. Với hướng tiếp cận
này, chúng ta có thể xây dựng bộ hệ số đặc trưng cho từng lĩnh vực văn bản cụ thể, phục
vụ hữu ích cho bài toán tóm tắt văn bản tiếng Việt.
TÀI LIỆU THAM KHẢO
[1]. Diệp Quang Ban, “Ngữ Pháp Tiếng Việt”, Nhà xuất bản giáo dục, 2004
[2]. Nguyễn Văn Tu, “Từ điển đồng nghĩa Tiếng Việt”, Nhà xuất bản giáo dục, 2001
[3]. Thanh Le Ha, Quyet Thang Huynh, Chi Mai Luong, “A Primary Study on
Summarization of Documents in Vietnamese”, Proceeding of the First International
Congress of the International Federation for Systems Research, Kobe, Japan, Nov 15-
17, 2005. pp.234-239.
[4]. Luận án Tiến sỹ, Nguyễn Thị Thu Hà. “Phát triển một số thuật toán tóm tắt văn bản
Tiếng Việt sử dụng phương pháp học bán giám sát”. Học viện Kỹ thuật quân sự,
2012, 175 trang.
[5]. M.L. Nguyen, Shimazu, Akira, Xuan, Hieu Phan, Tu, Bao Ho, Horiguchi, Susumu,
"Sentence Extraction with Support Vector Machine Ensemble", Proceedings of the
First World Congress of the International Federation for Systems Research : The New
Roles of Systems Sciences For a Knowledge-based Society 2005.
[6]. Luận án Tiến sỹ, Nguyễn Hoàng Tú Anh. “Tiếp cận đồ thị biểu diễn, khai thác văn
bản và ứng dụng”, Trường Đại học Khoa Học Tự Nhiên, ĐHQG-HCM, 2011.
[7]. Trương Quốc Định, Nguyễn Quang Dũng. “Một giải pháp tóm tắt văn bản tiếng Việt
tự động”, Hội thảo quốc gia lần thứ XV: Một số vấn đề chọn lọc của Công nghệ
thông tin và truyền thông- Hà Nội, 03-04/12/2012.
[8]. Nguyen Quang Uy, Pham Tuan Anh, Truong Cong Doan, Nguyen Xuan Hoai, “A
Study on the Use of Genetic Programming for Automatic Text Summarization”, KSE,
2012 4th Int. Conference on Knowledge and Systems Engineering, 2012, pp.93-98.
[9]. R.K. Gupta, “Genetic Algorithms-an Overview”, impulse E, ITM Uni., Vol. 1, 2006.
[10]. Dice, L.R. (1945): “Measures of the amount of ecologic association between
species”. Ecology 26, pp.297–302.
[11]. VLSP project, Vietnamese Language Processing,
[12]. Suanmali, L., Salim, N., Salem Binwahlan, M.: “Genetic Algorithm based Sentence
Extraction for Text Summarization”. Inter. J. of Innovative Computing 1(1), 2011.
[13]. Mohamed Abdel Fattah and Fuji Ren, "Automatic Text Summarization", Proceedings
of World Academy of Science, Engineering and Technology, Vol 27,ISSN 1307-
6884, 192-195, Feb 2008.
[14]. Ngoc Anh Tran, Thanh Tinh Dao, Phuong Thai Nguyen (2002), "An Effective
Context-based Method for Vietnamese Word Segmentation", Proceedings of the First
International Workshop on Vietnamese Language and Speech Processing (VLSP
2012), pp.34-40, In Conjunction with 9th IEEE-RIVF Conference on Computing and
Communication Technologies (RIVF 2012).
[15]. Ngoc Anh Tran, Thanh Tinh Dao, Phuong Thai Nguyen (2013), "Identifying
Coordinated Compound Words for Vietnamese Word Segmentation", Proceedings of
the 5th Inter. Conference of Soft Computing and Pattern Recognition (SoCPaR 2013).
Kỹ thuật điện tử & Khoa học máy tính
N. N. An, N. Q. Bắc, N. Đ. Hiếu, T. N. Anh,“Xác định các hệ số văn bản tiếng Việt.” 46
[1] Nguyễn Nhật An, Trần Ngọc Anh, Phan Thị Nguyệt Hoa, “Kỹ thuật Voting trong bài
toán tách từ tiếng Việt”, Tạp chí Nghiên cứu Khoa học & Công nghệ Quân sự, Đặc
san CNTT 04/2014, tr.54-61.
[2] Karel Jezek and Josef Steinberger, “Automatic Text summarization”, Vaclav Snasel
(Ed.): Znalosti 2008, pp.1-12, ISBN 978-80-227-2827-0, FIIT STU Brarislava,
UstavInformatiky a softveroveho inzinierstva, 2008.
ABSTRACT
DETERMINING THE TEXT FEATURE COEFFICIENTS BY GENETIC ALGORITHM
FOR VIETNAMESE TEXT SUMMARIZATION
Text summarization is the text concise process that retains the important
information. This paper proposes a new approach in Vietnamese text
summarization (by Extraction Summarization) based on key characteristics such
as location of sentences, sentence length, weight TFxISF, probability of
substantive word, similarity between the sentence and the title, center sentence,...
The first, we identified a set of the features in Vietnamese text. The next step, we
use the genetic algorithms to determine the feature coefficients of training text
corpus. Experiments of text summarization with coefficients determined by
genetic algorithm show the summary texts are highly accurate, can be applied in
practice.
Keywords: Vietnamese text summarization, Text feature coefficients, Gennetic algorithm.
Nhận bài ngày 02 tháng 07 năm 2014
Hoàn thiện ngày 25 tháng 07 năm 2014
Chấp nhận đăng ngày 03 tháng 08 năm 2014
Địa chỉ: * Viện Công nghệ thông tin, Viện KH-CN Quân sự - nguyennhatan@gmail.com
** Khoa CNTT, Học viện Kỹ thuật Quân sự - anhtn69@gmail.com
Các file đính kèm theo tài liệu này:
- 06_nguyennhatan_5692_2149176.pdf