Tài liệu Xác định các hệ số phương pháp cho bài toán tóm tắt văn bản Tiếng Việt dựa vfao kỹ thuật Voting - 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ố kỹ thuật Voting” 82
Xác định các hệ số phương pháp cho bài
toán tóm tắt văn bản tiếng việt dựa vào
kỹ thuật voting
NGUYỄN NHẬT AN*, NGUYỄN QUANG BẮC*,
NGUYỄN ĐỨC HIẾU**, TRẦN NGỌC ANH**
Túm tắt: Phương phỏp túm tắt văn bản tiếng Việt dựa vào kỹ thuật Voting là một
phương phỏp mới được đề xuất với ý tưởng xem kết quả của mỗi phương phỏp túm
tắt văn bản khỏc nhau là một lỏ phiếu đó được sắp xếp thứ tự ưu tiờn cỏc cõu trớch
rỳt, sử dụng kỹ thuật Voting để lựa chọn cỏc cõu ưu tỳ dựa trờn cỏc lỏ phiếu đó nờu.
Bài bỏo này phõn tớch hạn chế của phương phỏp trờn và đề xuất hướng cải tiến bằng
cỏch đưa vào cỏc hệ số phương phỏp. Đề xuất cỏch xỏc định cỏc hệ số phương phỏp
bằng giải thuật di truyền thụng qua quỏ trỡnh học kho ngữ liệu túm tắt mẫu. Thử
nghiệm túm tắt văn bản dựa theo kỹ thuật Voting với cỏc hệ số phương phỏp cho
thấy, văn bản túm tắt cú độ chớnh...
9 trang |
Chia sẻ: quangot475 | Lượt xem: 812 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Xác định các hệ số phương pháp cho bài toán tóm tắt văn bản Tiếng Việt dựa vfao kỹ thuật Voting - 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ố kỹ thuật Voting” 82
X¸c ®Þnh c¸c hÖ sè ph¬ng ph¸p cho bµi
to¸n tãm t¾t v¨n b¶n tiÕng viÖt dùa vµo
kü thuËt voting
NGUYỄN NHẬT AN*, NGUYỄN QUANG BẮC*,
NGUYỄN ĐỨC HIẾU**, TRẦN NGỌC ANH**
Tóm tắt: Phương pháp tóm tắt văn bản tiếng Việt dựa vào kỹ thuật Voting là một
phương pháp mới được đề xuất với ý tưởng xem kết quả của mỗi phương pháp tóm
tắt văn bản khác nhau là một lá phiếu đã được sắp xếp thứ tự ưu tiên các câu trích
rút, sử dụng kỹ thuật Voting để lựa chọn các câu ưu tú dựa trên các lá phiếu đã nêu.
Bài báo này phân tích hạn chế của phương pháp trên và đề xuất hướng cải tiến bằng
cách đưa vào các hệ số phương pháp. Đề xuất cách xác định các hệ số phương pháp
bằng giải thuật di truyền thông qua quá trình học kho ngữ liệu tóm tắt mẫu. Thử
nghiệm tóm tắt văn bản dựa theo kỹ thuật Voting với các hệ số phương pháp cho
thấy, văn bản tóm tắt có độ chính xác cao hơn phương pháp tóm tắt dựa theo kỹ
thuật Voting truyền thống đã được đề xuất.
Từ khóa: Tóm tắt văn bản tiếng Việt, Kỹ thuật Voting, Hệ số phương pháp, 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). Đố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
[1][2][3][4][5][6][7].
Trong các nghiên cứu đó, chúng tôi quan tâm đến hướng tiếp cận mới được đưa ra là
tóm tắt đơn văn bản tiếng Việt dựa vào kỹ thuật Voting [1]. Ý tưởng của phương pháp này
là xem kết quả của mỗi phương pháp tóm tắt văn bản khác nhau là một lá phiếu đã được
sắp xếp thứ tự ưu tiên các câu trích rút, sử dụng kỹ thuật Voting để lựa chọn các câu ưu tú
dựa trên các lá phiếu đã nêu. 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ẽ phân tích hạn chế, sau đó nghiên cứu, đề xuất
cải tiến bằng cách đưa hệ số phương pháp vào để nâng cao độ chính xác.
Nghiên cứu giải quyết hai vấn đề chính: Một là, trình bày phương pháp tóm tắt đơn
văn bản tiếng Việt dựa vào kỹ thuật Voting và hạn chế của nó; hai là, cách đưa hệ số
phương pháp vào và xác định bộ hệ số phương pháp 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. Sau đó, 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 đượ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 dựa vào kỹ thuật Voting
Trong phần này, chúng tôi trình bày tóm tắt lại hướng tiếp cận tóm tắt đơn văn bản
tiếng Việt dựa vào kỹ thuật Voting của nhóm tác giả đã nêu trong bài báo [1]
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 83
2.1.1. Phương pháp Voting
Voting là một quá trình đưa ra quyết định của cử tri để chọn ra một danh sách ứng cử
viên tốt nhất thoả mãn các tiêu chí bầu chọn cho một mục đích cụ thể nào đó[12]. Trong
nghiên cứu, nhóm tác giả chỉ trình bày kỹ thuật voting dựa trên các lá phiếu có sự ưu tiên
(sắp xếp). Chúng ta xem ví dụ trong bảng 1:
Bảng 1. Minh hoạ phương pháp Voting.
Số phiếu bầu chọn
2 3 1
Ưu tiên 1 A B C
Ưu tiên 2 B C B
Ưu tiên 3 C A A
Ưu tiên 4 D D D
Phương pháp tính điểm Borda[12]
Trong phương pháp này, các vị trí được tính điểm như sau: vị trí cuối cùng được 1
điểm, tiếp theo trên vị trí cuối cùng được 2 điểm, Sau đó, các điểm được nhân với số
phiếu để và cộng lại với nhau để có được tổng số điểm cho mỗi ứng viên.
Xét ví dụ ở bảng 1: Ưu tiên 1 được 4 điểm, ưu tiên 2 được 3 điểm, ưu tiên 3 được 2
điểm và ưu tiên 4 được 1 điểm: Điểm cho mỗi ứng cử viên là:
A = 4×2 + 2×3 + 2×1 = 16
B = 3×2 + 4×3 + 3×1 = 21
C = 2×2 + 3×3 + 4×1 = 17
D = 1×2 + 1×3 + 1×1 = 6
Kết quả bầu chọn từ cao xuống thấp, ta được danh sách theo thứ tự: B, C, A, D.
2.1.2. Bài toán tóm tắt đơn văn bản tiếng Việt dựa vào kỹ thuật Voting
Ý tưởng của phương pháp này là xem kết quả của mỗi phương pháp tóm tắt văn bản
khác nhau là một lá phiếu đã được sắp xếp thứ tự ưu tiên các câu trích rút, sử dụng kỹ
thuật Voting để lựa chọn các câu ưu tú dựa trên các lá phiếu đã nêu[1].
Hình 1. Mô hình tóm tắt đơn văn bản tiếng Việt dựa vào kỹ thuật Voting.
Văn bản tiếng Việt đầu vào
(tách câu, tách từ, loại bỏ hư từ)
KỸ THUẬT
VOTING
Lấy theo tỉ lệ tóm tắt và
xuất nguyên câu gốc
Tóm tắt theo
phương pháp (1)
Tóm tắt theo
phương pháp (2)
Tóm tắt theo
phương pháp (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ố kỹ thuật Voting” 84
Mô hình tiếp cận sử dụng kỹ thuật Voting cho bài toán tóm tắt đơn văn bản được mô
tả như sau:
Bước 1. Tiền xử lý văn bản tiếng Việt cho đầu vào: tách câu, tách từ, gán nhãn, loại bỏ
hư từ...
Bước 2. Thực hiện tính trọng số câu theo n phương pháp (1), (2),,(n). Kết quả của
mỗi phương pháp là tập các câu được sắp xếp từ cao xuống thấp theo trọng số (Max-Min
như trong hình 1).
Bước 3. Thực hiện kỹ thuật Voting trên tập các kết quả, kết quả Voting là tập các câu
được sắp xếp lại theo trọng số Voting từ cao xuống thấp làm kết quả đầu ra.
Bước 4. Thực hiện lấy các câu có trọng số Voting từ cao xuống thấp theo tỉ lệ tóm tắt,
xuất nguyên các câu đã rút trích theo thứ tự xuất hiện trong văn bản gốc.
Minh hoạ: Tóm tắt văn bản có 6 câu với 3 phương pháp tóm tắt làm đầu vào, kết quả
của mỗi phương pháp sau khi tính trọng số và sắp xếp từ cao xuống thấp được mô tả dưới
bảng 2:
Bảng 2. Minh hoạ tóm tắt bằng kỹ thuật Voting.
(1) (2) (3) Vongting (Borda)
Câu 2 Câu 1 Câu 1 Câu 1
Câu 1 Câu 2 Câu 2 Câu 2
Câu 6 Câu 6 Câu 3 Câu 6
Câu 3 Câu 3 Câu 6 Câu 3
Câu 5 Câu 5 Câu 4 Câu 5
Câu 4 Câu 4 Câu 5 Câu 4
Kết quả chọn theo tỉ lệ 50% sau khi Voting là: Câu 1, Câu 2, Câu 6
Nhận xét:
Phương pháp trên tác giả đã chỉ ra rằng, nó chỉ hiệu quả khi các phương pháp đầu vào
là các phương pháp cạnh tranh (có kết quả xấp xỉ nhau) bởi vì với kỹ thuật Voting, kết quả
Voting sẽ thiên về xu hướng của đa số, nghĩa là nếu số phương pháp “xấu” nhiều hơn thì
kết quả Voting sẽ “xấu” và ngược lại.
Như vậy, để khắc phục vấn đề này phần tiếp theo chúng tôi sẽ trình bày cách đưa hệ số
phương pháp vào và cách xác định bộ hệ số đó. Ở đây hệ số phương pháp chính là số lá
phiếu giống nhau về thứ tự sắp xếp ứng viên.
2.2. Hệ số phương pháp và cách xác định bằng giải thuật di truyền
Như ví dụ minh họa phương pháp Voting ở bảng 1, chúng ta nhận thấy rằng cách tính
điểm của phương pháp Voting phụ thuộc vào 2 yếu tố: thứ hạng ưu tiên và số lá phiếu bầu
chọn. Với phương pháp tóm tắt văn bản bằng kỹ thuật Voting[1] tác giả chỉ mới quan tâm
đến thứ hạng ưu tiên (danh sách câu được sắp xếp văn bản theo trọng số câu) và xem mỗi
phương pháp chỉ là một lá phiếu.
Do vậy, ở nghiên cứu này chúng tôi định nghĩa hệ số phương pháp chính là số lá phiếu
của hướng tiếp cận tóm tắt đơn văn bản dựa trên kỹ thuật Voting. Hệ số này sẽ quyết định
độ tốt của phương pháp đầu vào, những phương pháp tốt sẽ có hệ số cao, những phương
pháp yếu sẽ có hệ số thấp. Với cách tiếp cận này, chúng ta có thể thấy rằng, đầu vào là các
phương pháp bất kỳ mà không cần xác định phương pháp cạnh tranh.
Điểm số của câu theo kỹ thuật Voting được tính như sau:
1
n
i i
i
Score s k f s
(1)
Trong đó: if s là điểm số câu được tính theo kỹ thuật Voting của phương pháp tóm
tắt i và ik là hệ số phương pháp, n là số phương pháp tóm tắt đầu vào.
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 85
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 phương pháp 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 2. Mô hình học hệ số phương pháp 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ố phương pháp trên ngôn
ngữ của giải thuật di truyền.
Bài toán tìm hệ số phương pháp 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 n a D d d d sh sh sh s pph p p
trong đó, m là số văn bản đầu vào để học, n là số phương pháp tóm tắt làm đầu vào, a là tỷ
lệ tóm tắt, Đố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 và jsh là bản tóm tắt con người của văn bản đó, pi là các danh sách câu được sắp
xếp theo trọng số của phương pháp tóm tắt văn bản i.
Bài toán đặt ra là tìm các hệ số phương pháp k sao cho bản tóm tắt dựa vào kỹ thuật
Voting , , ,votingSum a d p k 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.
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 1: Độ đ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):
, , ,
, , , ,
voting ii
voting ii
i
Sum a d p k SH
Sim Sum a d p k SH
SH
(2)
Các phương pháp
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ố phương
pháp k1,...,kn
đúng
sai
Tập văn bản mẫu
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ố kỹ thuật Voting” 86
trong đó, 1, , , , , voting i iriSum a d p k sm sm là vector thực từ khác nhau của văn
bản tóm tắt theo kỹ thuật voting với 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ố phương pháp chấp nhận được. Khi đó mô hình
bài toán tìm hệ số phương pháp cho tóm tắt văn bản dựa theo kỹ thuật Voting được phát
biểu như sau:
1
, , , ,
, , , ,
m
voting ii
i
Sim Sum a d p k SH
DFC m a d sh p max
m
(3)
với miền ràng buộc:
0ik
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ố phương pháp 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 voting ii
i
Sim Sum a d p k SH
f s
m
(4)
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 (5)
' '
2 2 2 1 , 1, , ; , 1, ,i i i ik k i z k k i z n (6)
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 (7)
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
(8)
Trong đó, s là cá thể và G là quần thể đang xem xét có chứa s.
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 87
ik
i
THUẬT TOÁN GA HỌC HỆ SỐ PHƯƠNG PHÁP
Input: , , , , m a D sh p
Output: Nghiệm tối ưu của bài toán , , , ,DFC m a D sh p là tập hệ số phương pháp
1 2, , ns k k k
Bước 0. Khởi tạo quần thể gồm K 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,..,tvoting i jSum a d p k i m j k t là số thế hệ
thứ t của quần thể. Tính mức độ thích nghi , 1, ,tif s i k cho từng cá thể của tG theo
(4). Áp dụng toán tử chọn lọc (8) 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ố phương pháp 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 (5)-(6) để 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 (7) vào lgt tG G để nhận được 1tG , đặt t=t+1 và
quay lại bước 1.
2.3. Mô hình tóm tắt đơn văn bản tiếng Việt dựa trên kỹ thuật Voting cải tiến
Như đã trình bày ở trên, chúng ta thêm vào bộ hệ số phương pháp để xác định độ tốt
của từng phương pháp và xác định nó bằng giải thuật di truyền thông qua học kho ngữ liệu
tóm tắt mẫu. Mô hình tóm tắt văn bản tiếng Việt dựa trên kỹ thuật Voting cải tiến được mô
tả như hình 3:
Hình 3. Mô hình tóm tắt văn bản dựa theo kỹ thuật Voting cải tiến.
3. THỬ NGHIỆM, ĐÁNH GIÁ
3.1. 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 1000
văn bản thuộc lĩnh vực chính trị của báo Hà Tĩnh điện tử ( với phần
tóm tắt khoảng 100 từ để làm dữ liệu thử nghiệm.
Tóm tắt bằng tay Các phương
Tập văn bản mẫu
GIẢI THUẬT DI TRUYỀN
Nhiễm sắc thể: 1 2, , ns k k k
Hàm thích nghi
1
, , , , m voting ii
i
Sim Sum a d p k SH
f s
m
Bộ hệ số phương
pháp
1 2, , nk k k
Văn bản
Các phương
pháp
Văn bản tóm tắt
Phương pháp
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ố kỹ thuật Voting” 88
Ở bước tiền xử lý chúng tôi sử dụng các bộ công cụ sau:
- Bộ công cụ tách câu vnSentDetector (một gói của vnTokenizer) [8] để 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ả [9][10][11] được dùng để tách từ
tiếng Việt.
- Sử dụng bộ công cụ vnTagger[8] để gán nhãn từ loại với bộ 18 nhãn.
Hình 4. Minh hoạ cấu trúc tệp dữ liệu theo chuẩn XML.
3.2. Thử nghiệm, đánh giá
Chúng tôi thử nghiệm với 3 phương pháp tính trọng số câu được đề xuất trong [1].
Phương pháp 1: dựa vào vị trí câu, tần suất từ và độ dài câu.
Score(S) = (1+1/k) x ScoreAVR(S) x Flength(S)
Phương pháp 2: dựa vào vị trí câu, chất lượng thông tin và độ dài câu.
Score(S) = (1+1/k) x ScoreH(S) x Flength(S)
Phương pháp 3: dựa vào vị trí câu, độ tương tự giữa câu và câu tiêu đề và độ dài câu.
Score(S) = (1+1/k) x SimDICE(S) x Flength(S)
Chúng tôi thực hiện xác định bộ hệ số phương pháp 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. Trong quá trình đào tạo, giải thuật di truyền sẽ
được thực hiện với các thông số sau:
Quần thể gồm 100 cá thể.
Xác suất lai ghép 0.8
Xác suất đột biến 0.1
Kỷ_niệm/V 50/M năm/M ngày/N mở/V đường/N Trường_Sơn/Np ./CH
duong-truong-son/7/24/2009 4:09:00 PM - Nguồn ảnh : Xuân_Hải - (
Chủ_tịch Hội CCB xã Trường_Sơn , Đức_Thọ ).
Đường/N Trường_Sơn/Np -/CH đường_mòn/N Hồ_Chí_Minh/Np
,/CH con/Nc đường/N huyền_thoại/N đã/R không/R ít/A sách_báo/N
phim_ảnh/N giới_thiệu/V con/Nc đường/N huyền_thoại/N này/P ./CH
Tuy_nhiên/C ,/CH tuyến_đường/N giao_liên/N chuyển/V quân/N từ/E
Bắc/Np vào/V Nam/Np phải/V vượt/V qua/V nhiều/A con/Nc sông/N lớn/A
./CH Để/E bộ_đội/N vượt/V sông/N an_toàn/A ,/CH tránh/V tổn_thất/N
do/E không_quân/N Mỹ/Np đánh_phá/V là/V yêu_cầu/N cao/A nhất/R của/E
nhiệm_vụ/N ./CH Bến/N đò/N Chợ/N Thượng/Np ,/CH một/M trong/E
những/L trọng_điểm/N của/E bộ_đội/N qua/E sông/N đã/R nói/V lên/R
điều/N đó/P ./CH
Bến_đò/N Chợ_Thượng/Np qua/V sông/N La/Np
đã/R có/V từ/E xa_xưa/A ,/CH thuộc/V xã/N Trường_Sơn/Np (/CH
Đức_Thọ/Np )/CH thường_ngày/A chở/V khách/N qua/V sông/N
nối/V đôi/M bờ/N giao_lưu/V buôn_bán/V làm_ăn/V ./CH
Chiến_tranh_phá_hoại/N nổ/V ra/R ,/CH đò/N
Chợ_Thượng/Np được/V gánh/N thêm/V nhiệm_vụ/N chở/V bộ_đội/N
qua/V sông/N vào/V Nam/Np chiến_đấu/V ./CH
Trách_nhiệm/N này/P được/V giao/V cho/E
Đảng_bộ/N và/Cc nhân_dân/N xã/N Trường_Sơn/Np suốt/A từ/E
năm/N 1965/M đến/E khi/N Tổ_quốc/N thống_nhất/V ./CH
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 89
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.
Bảng 3. Bảng kết quả hệ số phương pháp.
STT Phương pháp Hệ số
1 Phương pháp 1 2
2 Phương pháp 2 3
3 Phương pháp 3 5
Qua kết quả, chúng ta có thể thấy rằng, hệ số phương pháp có kết quả cao phản ảnh độ
tốt của phương pháp đó. Như vậy, phương pháp 1 dựa vào tần suất nghịch đảo từ là yếu
hơn cả, còn phương pháp 3 dựa vào độ tương tự với tiêu đề là tốt nhất.
Với bộ hệ số phương pháp này, chúng tôi tiến hành tóm tắt 20% văn bản còn lại theo
phương pháp tóm tắt dựa trên kỹ thuật Voting cải tiến và so sánh kết quả với phương pháp
tóm tắt dựa trên kỹ thuật Voting gốc với tỉ lệ tóm tắt 30% . 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 theo công thức (2).
Bảng 4. Bảng kết quả tóm tắt văn bản
Phương pháp 1 Phương pháp 2 Phương pháp 3 Phương pháp
Voting gốc[1]
Phương pháp
Voting cải tiến
35% 36% 38% 38.5% 39%
Kết quả này cho thấy việc đưa hệ số phương pháp vào bài toán tóm tắt văn bản dựa
vào kỹ thuật Voting cho thấy hiệu quả hơn. Nó tránh tình trạng nhiều phương pháp yếu sẽ
kéo kết Voting quả xuống thấp hơn phương pháp tốt.
4. KẾT LUẬN
Bài báo này đã trình bày cải tiến phương pháp tóm tắt đơn văn bản tiếng Việt dựa theo
kỹ thuật Voting bằng cách đưa hệ số phương pháp và cách xác định hệ số. Nghiên cứu tập
trung giải quyết hai vấn đề trọng tâm:
- Trình bày cách đưa hệ số phương pháp.
- Xác định các hệ số phương pháp 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.
Qua quá trình thử nghiệm 1000 văn bản thuộc lĩnh vực chính trị với tóm tắt con người
bao gồm 100 từ. Chúng tôi nhận thấy rằng việc đưa hệ số phương pháp vào phát huy hiệu
quả. Nó khắc phục được điểm yếu của phương pháp tóm tắt văn bản dựa vào kỹ thuật
Voting gốc.
TÀI LIỆU THAM KHẢO
[1]. Nguyễn Nhật An, Trần Ngọc Anh, "Tóm tắt văn bản tiếng Việt dựa vào kỹ thuật
Voting", Chuyên san Công nghệ thông tin và Truyền thông (JICT) thuộc Tạp chí
Khoa học và Kỹ thuật, Học viện Kỹ thuật quân sự, tháng 4/2014, pp.57-67
[2]. 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.
[3]. 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”. HV KTQS, 2012, 175 trang.
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ố kỹ thuật Voting” 90
[4]. 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.
[5]. 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.
[6]. 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.
[7]. 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 Inter. Conference on Knowledge and Systems Engineering, 2012, pp.93-98.
[8]. VLSP project, Vietnamese Language Processing,
[9]. Ngoc Anh Tran, Thanh Tinh Dao, Phuong Thai Nguyen, "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 Confer. on Comp. and Com. Tech.(RIVF 2012).
[10]. Ngoc Anh Tran, Thanh Tinh Dao, Phuong Thai Nguyen, "Identifying Coordinated
Compound Words for Vietnamese Word Segmentation", Proceedings of the Fifth
International Conference of Soft Computing and Pattern Recognition (SoCPaR 2013).
[11]. 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í NCKH&CNQS, Đặc san CNTT 04/2014, tr.54-61
[12]. Pacuit, Eric (2012), "Voting Methods", The Stanford Encyclopedia of Philosophy
(Winter 2012 Edition),
ABSTRACT
DETERMINING THE METHOD COEFFICIENTS FOR VIETNAMESE TEXT
SUMMARIZATION BASED ON VOTING TECHNIQUE
Vietnamese text summarization based on Voting technique is a new
approach, is proposed with the idea of considering the results of each method of
different text summarization is a voting leaf has been arranged in priority order
of sentence extraction, using Voting techniques to choose elite sentences based
on scores on the votes. This paper analyses the limitations of the methods above
and proposes ways to improve the system by using method coefficients. The
paper also proposes the way to determine the method coefficients by genetic
algorithms through the process of learning from the corpus of sample text
summarization. Experimental results with method coefficients showed that the
accuracy of summarized text is higher the traditional voting technique before.
Keywords: Vietnamese text summarization, Method voting, Method coefficients, Gennetic algorithm.
Nhận bài ngày 01 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 05 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:
- 11_nguyennhatan_2576_2149226.pdf