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

pdf9 trang | Chia sẻ: quangot475 | Lượt xem: 812 | Lượt tải: 0download
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:

  • pdf11_nguyennhatan_2576_2149226.pdf