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

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

  • pdf06_nguyennhatan_5692_2149176.pdf