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

Kỹ thuật điện tử & Khoa học máy tính<br /> <br /> <br /> X¸c ®Þnh c¸c hÖ sè ®Æc tr­ng<br /> b»ng gi¶I thuËt di truyÒn cho bµi to¸n<br /> tãm t¾t v¨n b¶n tiÕng viÖt<br /> NGUYỄN NHẬT AN*, NGUYỄN QUANG BẮC*,  <br /> NGUYỄN ĐỨC HIẾU**, TRẦN NGỌC ANH** <br /> <br /> 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<br /> 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<br /> văn bản tiếng Việt theo hướng trích rút (Extraction Summarization) dựa trên các<br /> đặ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<br /> 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<br /> 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<br /> truyền để xác định hệ số các đặc trưng từ kho ngữ liệu huấn luyện. Thử nghiệm<br /> 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<br /> tóm tắt có độ chính xác cao, có thể áp dụng tốt trong thực tế.<br /> <br /> 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. <br />  <br /> 1. ĐẶT VẤN ĐỀ<br /> 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ừ <br /> 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. <br /> 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 <br /> 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à: <br /> 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 <br /> 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 <br /> 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í <br /> 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 <br /> [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 <br /> 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 <br /> pháp tính toán các hệ số thông qua quá trình học.  <br /> Đố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 <br /> 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, <br /> 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 <br /> 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 <br /> 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 <br /> 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, <br /> 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 <br /> 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ả. <br /> 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 <br /> 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 <br /> giải thuật di truyền dựa trên các đặc trưng văn bản quan trọng. <br /> 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 <br /> 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 <br /> 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ử <br /> nghiệm tóm tắt văn bản và đánh giá chúng.  <br /> <br /> <br />  <br /> <br /> 36     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.”  <br /> Nghiên cứu khoa học công nghệ<br /> <br /> 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 <br /> 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 <br /> trong Phần 4. <br /> 2. NỘI DUNG CẦN GIẢI QUYẾT<br /> 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<br /> 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: <br /> 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ừ.  <br /> Bước 2. Tính trọng số các câu theo các đặc trưng văn bản như. <br /> 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ệ. <br /> 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.  <br /> <br /> TIỀN TÍNH SẮP XUẤT<br /> Văn XỬ LÝ: TRỌNG XẾP CÂU Văn bản<br /> Tách câu,  SỐ CÂU theo   Theo tứ  Tóm<br /> bản<br /> tách từ,  theo   trọng số,   tự xuất <br /> tắt<br /> gán nhãn,  các đặc  rút trích   hiện <br />  loại hư  trưng  theo tỉ lệ  trong văn <br /> <br /> Hình 1. Quy trình tóm tắt đơn văn bản tổng quát.<br /> 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ô <br /> tả như sau: <br /> z<br /> Score  s   ki  Scoreti  s    (1) <br />               i 1<br /> <br /> trong  đó,  z  số  đặc  trưng,  Scoreti  s  là  trọng  số  của  các  đặc  trưng  trong  câu  s,  ti là  đặc <br /> trưng thứ i của văn bản. <br /> 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 <br /> 2 yếu tố quan trọng là: <br /> - Xác định tập đặc trưng quan trọng của văn bản tiếng Việt <br /> - Xác định bộ hệ số đặc trưng như thế nào?  <br /> 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 <br /> và cách xác định bộ hệ số đặc trưng. <br /> 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<br /> Để 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 <br /> 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 <br /> 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 <br /> 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 <br /> 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ỏ. <br /> 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 <br /> đề, 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 <br /> của tác giả Nguyễn Văn Tu[2]. <br /> 2.2.1. Ví trí câu<br /> Đị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<br /> định là giá trị vị trí của câu trong một đoạn văn bản.<br /> Đố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 <br /> 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 <br /> trọng của câu trong một đoạn văn bản được tính theo công sau: <br />              Score f 1  s   1   (2) <br /> k<br /> <br />  <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 32, 08 - 2014                               37<br />  Kỹ thuật điện tử & Khoa học máy tính<br /> <br /> 2.2.2. Trọng số TF.ISF(term frequency- inverse sentence frequency)<br /> Đị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ố<br /> 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<br /> câu.<br /> Phương pháp này bắt nguồn từ công thức nổi tiếng TFxIDF( term frequency – inverse <br /> document frequency), được sử dụng để xác định mức độ quan trọng của từ trong một văn <br /> 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 <br /> 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 <br /> 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 <br /> câu (TFxISF: term frequency- inverse sentence frequency): <br /> 1 Nw<br />   Score f 2  s   TF  wk , s   ISF  wk  (3) <br /> N w k 1<br /> 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, TF  wk , s   <br /> <br /> là số lần xuất hiện của thực từ wk trong câu s, ISF  w   log  N s    là nghịch đảo của <br /> <br /> k <br />  SF  wk  <br /> 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 <br /> có chứa thực từ wk. <br /> 2.2.3. Độ dài câu<br /> Đị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<br /> đượ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.<br /> 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 <br /> 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á <br /> 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 độ <br /> 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 <br /> sát kho ngữ liệu tiếng Việt.  <br /> <br /> <br /> <br /> <br />  <br /> 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<br /> được chuẩn hoá về đoạn [0,1].<br /> Công thức độ dài câu được xây dựng như sau: <br />  ax 2  bx  c, 0  x  12  <br />  <br />             Score  s        x   2   (4) <br /> f3<br />  exp   2<br />  , x  12 <br />  2  2 <br />    <br /> trong đó, a = - 0.00529, b =  0.12174, c = 0.3;  = 26.3 ,  = 11.5,   = 10.5 <br /> 2.2.4. Xác suất thực từ<br /> Đị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<br /> 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.<br /> <br /> <br />  <br /> <br /> 38     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.”  <br /> Nghiên cứu khoa học công nghệ<br /> <br /> Đặ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 <br /> 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ì <br /> câu đó càng quan trọng. <br /> 1 Nw<br />             Score f 4  s   P  wk    (5) <br /> N w k 1<br /> C  wk <br /> trong đó, P  wk     xác suất unigram của từ wk, C(wk) là số lần xuất hiện của thực từ <br /> Nuni<br /> wk trong văn bản, Nuni là tổng số các thực từ (các unigram) trong văn bản. <br /> 2.2.5. Thực thể tên<br /> Đị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<br /> đượ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.<br /> Đặ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 <br /> 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 <br /> công cụ gán nhãn vnTagger[11].  <br /> N<br />              Score f 5  s   name<br /> s  <br /> (6) <br /> Nw  s<br /> 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. <br /> 2.2.6. Dữ liệu số<br /> Đị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ố<br /> đượ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ó<br /> trong câu.<br /> Đặ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 <br /> 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 <br /> 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 <br /> biết thông qua nhãn M của công cụ gán nhãn vnTagger[11]:  <br /> N s<br />                 Score f 6  s   num   (7) <br /> Nw  s <br /> trong đó,  N num  s  là số thuật ngữ dữ liệu số xuất hiện trong câu. <br /> 2.2.7. Tương tự với tiêu đề<br /> Đị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<br /> 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 đề.<br /> Đặ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. <br /> Được tính dựa theo phép đo đồng xuất hiện Dice[10]:  <br /> <br />               Score f 7  s   SimDice  S , T   2    <br /> S T<br /> (8) <br /> S T<br /> trong đó,  S  s1 , s2 , , sN  là vetor thực từ khác nhau của câu, T  t1 , t2 , , t M  là vetor <br /> 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 . <br /> 2.2.8. Câu trung tâm<br /> Đị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<br /> 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<br /> trong văn bản.<br /> Đặ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 <br /> 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 <br /> Similarity [13], được mô tả bằng công thức sau: <br />  <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 32, 08 - 2014                               39<br />  Kỹ thuật điện tử & Khoa học máy tính<br /> <br /> m<br />              Score f 8  s    Sim  S , S   <br /> j 1, j  i<br /> Dice i j (9) <br /> <br />  <br /> Trong đó:  SimDice Si , S j  là phép đo đồng xuất hiện Dice giữa câu thứ i với câu thứ j<br /> được tính tương tự như công thức (8). <br /> 2.3. Học hệ số các đặc trưng bằng giải thuật di truyền<br /> 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 <br /> 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 <br /> 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 <br /> như sau: <br /> 8<br />                 Score  s   ki  Score fi  s    (10) <br /> i 1<br /> <br /> Trong đó:  Score fi  s  là điểm số của đặc trưng i và  ki là hệ số của nó.  <br /> 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 <br /> 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 <br /> 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 <br /> 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ệ <br /> 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 <br /> học hệ số được mô tả trong hình 3. <br /> Tập văn bản mẫu <br /> Tập văn bản mẫu <br /> <br /> Các đặc trưng  Tóm tắt bằng tay <br /> <br /> Nhiễm sắc thể <br /> <br /> <br /> Khởi tạo quần  Đánh giá độ thích nghi  Chọn lọc <br /> thể ban đầu <br /> <br /> Xây dựng quần  Lai ghép <br /> thể mới <br /> sai <br /> Bộ hệ số đặc  đúng  Đột biến <br /> trưng k1,...,k8 Điều kiện dừng <br />  <br /> Hình 3. Mô hình học hệ số đặc trưng bằng thuật toán di truyền.<br /> 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ữ <br /> của giải thuật di truyền. <br /> 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ữ<br /> liệu sau:   m, a, D   d1 , d2 ,, d m  , sh   sh1 , sh2 ,, shm  , t   t1 , t2 ,, tn  <br /> 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 <br /> để tóm tắt văn bản, đối với mỗi văn bản học thứ j:  d j là văn bản toàn văn chứa tiêu đề và <br /> các câu nội dung,  sh j là bản tóm tắt con người của văn bản đó. <br /> 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 <br /> đặ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. <br /> <br /> <br />  <br /> <br /> 40     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.”  <br /> Nghiên cứu khoa học công nghệ<br /> <br /> 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 <br /> đượ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 <br /> được định nghĩa như sau:<br /> Định nghĩa 9:  Độ đo đánh giá văn bản tóm tắt được định nghĩa bằng độ tương tự<br /> 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):<br /> Sum  a, d , t , k i SH i<br />  <br />                Sim Sum  a, d , t , k i , SH i   <br /> SH i<br />   (11) <br /> <br /> trong đó,  Sum  a, d , t , k i  smi1 ,, smir    là vector thực từ khác nhau của văn bản tóm <br /> 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<br /> SH i  shi1 , , shil   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 <br /> văn bản di<br /> Giả sử  s   k1 , k2 , kn   là  bộ hệ số  đặc trưng chấp nhận được. Khi đó mô hình  bài <br /> toán tìm hệ số đặc trưng tóm tắt văn bản được phát biểu như sau: <br /> <br />   DFC  m, a, d , sh, t   max <br /> m<br /> <br /> Sim Sum  a, d , t , k i , SH i   (12) <br /> i 1 m<br /> n<br /> với miền ràng buộc:  ki  1; ki  0  <br /> i 1<br /> 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 <br /> 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. <br /> 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 <br /> chiều   k1 , k2 , kn  ,  k i     để biểu diễn các cá thể (các điểm) trong không gian tìm kiếm. <br /> Mỗi quần thể là một tập bao gồm một số cố định các cá thể. <br /> Độ đo thích nghi . Với mỗi cá thể  s   k1 , k2 , kn   ta xác định mức độ thích nghi của <br /> cá thể, f(s), bằng công thức sau: <br /> <br />                 f  s   <br /> <br /> m Sim Sum  a , d , t , k  , SH<br /> i i<br />  <br />  (13) <br /> i 1 m<br /> Toán tử lai ghép. Giả sử  s1   k11 , k12 , k1n   và  s2   k21 , k22 , k2 n   là 2 cá thể bất <br /> kỳ trong quần thể. Chúng ta đưa ra một số dạng toán tử lai ghép sau đây: <br /> 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à  s1 và <br /> s2 mô  tả  trên, có thể tạo  ra  hai  cá  thể  con  s1'   và  s2'     với  các  véc  tơ  cột  tương  ứng của <br /> chúng được xác định như sau:  <br />                  k1i '  k1i  , i  1,, z;  k1i '  k2i , i  z  1, , n   (14) <br /> ' '<br />                  k2i  k2i  , i  1, , z;  k2i  k1i , i  z  1,, n (15) <br /> 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ừ <br /> cá  thể  s   k1 , k2 , kn  ,  thành  phần  ki   được  thay  thế  bởi  một  số  ngẫu  nhiên    trong <br /> khoảng xác định  [li , ui ]  của  ki . Cá thể  s  sau khi đột biến với các véc tơ cột tương ứng <br /> của chúng được xác định như sau:  <br />   k j '  k j , j  i;  k j '   , j  i; j  1 n   (16) <br /> <br /> <br />  <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 32, 08 - 2014                               41<br />  Kỹ thuật điện tử & Khoa học máy tính<br /> <br /> 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 độ <br /> thích nghi: <br /> f s<br />   ps    (17) <br />  sG f  s <br /> Trong đó s là cá thể và G là quần thể đang xem xét có chứa s. <br /> <br /> THUẬT TOÁN GA HỌC HỆ SỐ ĐẶC TRƯNG<br /> Input: m, a, D, sh, t  <br /> 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 <br /> s   k1 , k2 , kn    <br /> Bước 0.  Khởi  tạo  quần  thể  gồm  X  cá  thể  G0   s10 , , sk0  ,  trong  đó: <br /> <br />  <br /> si0  ki01 , ki02 ,  kin0 ; i  1 k    <br />  <br /> Bước 1. Giải  các  bài  toán  Sum a, d ii , t , k tj ,  i  1,, m,   j  1,, k ,  t là số thế hệ <br /> thứ t của quần thể. Tính độ thích nghi  f  s  ,  i  1,, k  cho từng cá thể của  Gt  theo (13). <br /> t<br /> i<br /> <br /> Á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.  <br /> 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à <br /> cho nghiệm tối ưu là bộ hệ số đặc trưng tối ưu. <br /> Bước 3. Lựa chọn các cha-mẹ trong  Gt  theo mức độ thích nghi để ghép cặp theo toán <br /> tử lai ghép (14)-(15) để tạo nên tập các hậu thế  Gtlg  với K1 phần tử.  <br /> Bước 4. Tác động toán tử đột biến (16) vào  Gt Gtlg  để nhận được  Gt 1 , đặt t=t+1 và <br /> <br /> quay lại bước 1.  <br /> 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<br /> 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à <br /> 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. <br /> 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 <br /> vực như hình 4: <br />   Tập văn bản mẫu  Văn bản <br /> <br /> <br /> <br /> Các đặc trưng  Tóm tắt bằng tay <br /> Các đặc trưng <br /> <br /> GIẢI THUẬT DI TRUYỀN<br /> Nhiễm sắc thể:   s   k1 , k2 , k8   <br /> Bộ hệ số đặc <br /> Hàm thích nghi <br /> trưng k1 , k2 , k8  <br /> f s  <br /> m<br /> <br /> Sim Sum  a, d , t , k i , SH i <br /> i 1 m Văn bản tóm tắt <br />  <br />  <br /> 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.<br /> <br /> <br />  <br /> <br /> 42     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.”  <br /> Nghiên cứu khoa học công nghệ<br /> <br /> 3. THỬ NGHIỆM, ĐÁNH GIÁ<br />  <br /> 3.1. Biểu diễn nhiễm sắc thể<br /> 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, <br /> 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 <br /> 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 <br /> sẽ có giá trị từ 0-31. <br /> k1  k2  k3 k4 k5 k6 k7 k8<br /> <br /> 3.2. Quá trình đào tạo để học hệ số đặc trưng<br /> 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 <br /> 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 <br /> đ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ố <br /> 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 độ <br /> 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. <br /> 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 <br /> qua quá trình đào tạo (đã được chuẩn hoá để tổng các hệ số bằng 1). <br /> 3.3. Kho ngữ liệu<br /> 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 <br /> 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 <br /> 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 <br /> 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 <br /> 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ử <br /> nghiệm. <br /> Ở bước tiền xử lý chúng tôi sử dụng các bộ công cụ sau: <br /> - VnSentDetector (một gói của vnTokenizer) [11] để thực hiện tách câu tiếng Việt. <br /> - 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ừ <br /> tiếng Việt.  <br /> - Sử dụng bộ công cụ vnTagger[11] để gán nhãn từ loại với bộ 18 nhãn. <br /> <br /> Bảng 1: Bảng ngữ liệu thử nghiệm báo Hà Tĩnh điện tử (http://baohatinh.vn).<br /> Lĩnh vực Chính trị Xã hội Kinh tế Thể thao<br /> Số văn bản  1000  1000  1000  1000 <br /> <br /> 3.4. Kết quả<br /> 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 <br /> đà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á <br /> 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: <br />  Có 100 cá thể trong một quần thể.  <br />  Xác suất lai ghép 0.8 <br />  Xác suất đột biến 0.1  <br />  Thuật toán dừng khi đạt được 1000 thế hệ.  <br />  Tỷ lệ tóm tắt là 30%. <br /> 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 để <br /> đà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á <br /> kết quả trung bình. <br /> <br /> <br />  <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 32, 08 - 2014                               43<br />  Kỹ thuật điện tử & Khoa học máy tính<br /> <br /> 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ô <br /> hình đào tạo bằng giải thuật di truyền thông qua 5 lần thực hiện. <br /> Bảng 2. Bảng kết quả hệ số đặc trưng.<br /> Hệ số trung bình<br /> Đặc trưng Thể<br /> Chính trị Xã hội Kinh tế<br /> thao<br /> F1 – Vị trí câu  0.20  0.16  0.11  0.16 <br /> F2-  Trọng số TF.ISF (term frequency- <br /> inverse sentence frequency)  0.05  0.09  0.06  0.03 <br /> F3 – Độ dài câu  0.03  0.03  0.03  0.06 <br /> F4 – Xác suất thực từ  0.16  0.11  0.09  0.21 <br /> F5- Danh từ riêng  0.04  0.20  0.22  0.10 <br /> F6- Dữ liệu số  0.17  0.03  0.06  0.03 <br /> F7 – Độ tương đồng giữa câu với tiêu <br /> đề  0.16  0.19  0.19  0.22 <br /> F8- Câu trung tâm  0.20  0.20  0.23  0.18 <br /> Độ chính xác trung bình ROUGE-N<br /> 46% 45% 48% 42%<br /> theo tỉ lệ tóm tắt 30%<br /> 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 <br /> 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 <br /> 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à <br /> 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ố <br /> 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 <br /> 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 <br /> 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 <br /> trong lĩnh vực xã hội, kinh tế và thể thao thì lại ngược lại. <br /> 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 <br /> 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 <br /> đượ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 <br /> tóm tắt và hệ thống (công thức 11).  <br /> <br /> 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<br /> toán di truyền.<br /> Lĩnh vực Độ chính xác trung bình(%)<br /> (20 văn bản mẫu, tỉ lệ tóm tắt 30%) ROUGE-N (N=1)<br /> Chính trị  46 % <br /> Xã hội  43% <br /> Kinh tế  48% <br /> Thể thao  43% <br /> <br /> 4. KẾT LUẬN<br />  <br /> 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 <br /> 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 đề <br /> trọng tâm: <br /> - Xác định 8 đặc trưng quan trọng của văn bản tiếng Việt. <br /> - 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 <br /> học kho văn bản tóm tắt mẫu. <br />  <br /> <br /> 44     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.”  <br /> Nghiên cứu khoa học công nghệ<br /> <br /> 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ể <br /> 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 <br /> 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, <br /> 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ò <br /> 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 <br /> 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 <br /> vụ hữu ích cho bài toán tóm tắt văn bản tiếng Việt. <br /> <br /> TÀI LIỆU THAM KHẢO<br />  <br /> [1]. Diệp Quang Ban, “Ngữ Pháp Tiếng Việt”, Nhà xuất bản giáo dục, 2004 <br /> [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 <br /> [3]. Thanh  Le  Ha,  Quyet  Thang  Huynh,  Chi  Mai  Luong,  “A Primary Study on<br /> Summarization of Documents in Vietnamese”,  Proceeding  of  the  First  International <br /> Congress of the International Federation for Systems Research, Kobe, Japan, Nov 15-<br /> 17, 2005. pp.234-239. <br /> [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<br /> 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ự, <br /> 2012, 175 trang. <br /> [5]. M.L.  Nguyen,  Shimazu,  Akira,  Xuan,  Hieu  Phan, Tu,  Bao  Ho,  Horiguchi,  Susumu, <br /> "Sentence Extraction with Support Vector Machine Ensemble",  Proceedings  of  the <br /> First World Congress of the International Federation for Systems Research : The New <br /> Roles of Systems Sciences For a Knowledge-based Society 2005. <br /> [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<br /> bản và ứng dụng”, Trường Đại học Khoa Học Tự Nhiên, ĐHQG-HCM, 2011. <br /> [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<br /> 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ệ <br /> thông tin và truyền thông- Hà Nội, 03-04/12/2012. <br /> [8]. Nguyen  Quang  Uy,  Pham  Tuan  Anh,  Truong  Cong  Doan,  Nguyen  Xuan  Hoai,  “A<br /> Study on the Use of Genetic Programming for Automatic Text Summarization”, KSE, <br /> 2012 4th Int. Conference on Knowledge and Systems Engineering, 2012, pp.93-98. <br /> [9]. R.K. Gupta, “Genetic Algorithms-an Overview”, impulse E, ITM Uni., Vol. 1, 2006. <br /> [10].Dice,  L.R.  (1945):  “Measures of the amount of ecologic association between<br /> species”. Ecology 26, pp.297–302.  <br /> [11].VLSP  project,  Vietnamese  Language  Processing, http://vlsp.vietlp.org <br /> [12].Suanmali,  L., Salim, N., Salem Binwahlan, M.:  “Genetic Algorithm based Sentence<br /> Extraction for Text Summarization”. Inter. J. of Innovative Computing 1(1), 2011. <br /> [13].Mohamed Abdel Fattah and Fuji Ren, "Automatic Text Summarization", Proceedings <br /> of  World  Academy  of  Science,  Engineering  and  Technology,  Vol  27,ISSN  1307-<br /> 6884, 192-195, Feb 2008. <br /> [14].Ngoc  Anh  Tran,  Thanh  Tinh  Dao,  Phuong  Thai  Nguyen  (2002),  "An  Effective <br /> Context-based Method for Vietnamese Word Segmentation", Proceedings of the First <br /> International  Workshop  on  Vietnamese  Language  and  Speech  Processing  (VLSP <br /> 2012), pp.34-40, In Conjunction with 9th IEEE-RIVF Conference on Computing and <br /> Communication Technologies (RIVF 2012). <br /> [15].Ngoc  Anh  Tran,  Thanh  Tinh  Dao,  Phuong  Thai  Nguyen  (2013),  "Identifying<br /> Coordinated Compound Words for Vietnamese Word Segmentation", Proceedings of <br /> the 5th Inter. Conference of Soft Computing and Pattern Recognition (SoCPaR 2013). <br /> <br /> <br />  <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 32, 08 - 2014                               45<br />  Kỹ thuật điện tử & Khoa học máy tính<br /> <br /> [1] Nguyễn Nhật An, Trần Ngọc Anh, Phan Thị Nguyệt Hoa, “Kỹ thuật Voting trong bài<br /> 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 <br /> san CNTT 04/2014, tr.54-61. <br /> [2] Karel Jezek and Josef Steinberger, “Automatic Text summarization”, Vaclav Snasel <br /> (Ed.):  Znalosti  2008,  pp.1-12,  ISBN  978-80-227-2827-0,  FIIT  STU  Brarislava, <br /> UstavInformatiky a softveroveho inzinierstva, 2008. <br />  <br /> ABSTRACT<br /> DETERMINING THE TEXT FEATURE COEFFICIENTS BY GENETIC ALGORITHM <br /> FOR VIETNAMESE TEXT SUMMARIZATION <br /> Text summarization is the text concise process that retains the important<br /> information. This paper proposes a new approach in Vietnamese text<br /> summarization (by Extraction Summarization) based on key characteristics such<br /> as location of sentences, sentence length, weight TFxISF, probability of<br /> substantive word, similarity between the sentence and the title, center sentence,...<br /> The first, we identified a set of the features in Vietnamese text. The next step, we<br /> use the genetic algorithms to determine the feature coefficients of training text<br /> corpus. Experiments of text summarization with coefficients determined by<br /> genetic algorithm show the summary texts are highly accurate, can be applied in<br /> practice.<br /> Keywords: Vietnamese text summarization, Text feature coefficients, Gennetic algorithm. <br /> <br />  <br /> Nhận bài ngày 02 tháng 07 năm 2014<br /> Hoàn thiện ngày 25 tháng 07 năm 2014<br /> Chấp nhận đăng ngày 03 tháng 08 năm 2014<br /> <br /> <br /> <br /> <br /> Địa chỉ:   * Viện Công nghệ thông tin, Viện KH-CN Quân sự - nguyennhatan@gmail.com <br />   ** Khoa CNTT, Học viện Kỹ thuật Quân sự - anhtn69@gmail.com <br />  <br /> <br /> <br /> <br /> <br />  <br /> <br /> 46     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.”  <br />