CHƯƠNG 1 MỘT SỐ KIẾN THỨC CƠ SỞ
4.3. Giải thuật di truyền trích rút tập câu tóm tắt tối ưu
Một nhiệm vụ nghiên cứu của luận án là hướng đến tìm kiếm một tập câu tóm tắt tối ưu chứa các câu tóm tắt tốt và thể hiện tri thức đa dạng được trích rút từ cơ sở dữ liệu. Do đó, luận án sử dụng hàm đánh giá độ thích nghi, các phép tốn di truyền cơ bản như trong nghiên cứu của Donis-Diaz và cộng sự trong [38] như được trình bày trong mục 4.2.1 và 4.2.2 sau đây. Ngồi các phép tốn di truyền cơ bản, Donis-Diaz và cộng sự [38] có sử dụng thêm hai phép tốn bổ sung để tạo thành mơ hình di truyền lai Hybird-GA trích rút tập câu tóm tắt tối ưu từ cơ sở dữ liệu creep. Tuy nhiên, qua kết quả thực nghiệm của Donis-Diaz và cộng sự cho thấy vẫn còn hạn chế trong hai phép toán cleaning và improver. Đây là cơ sở để tác giả luận án đưa ra các đề xuất cải tiến cho mơ hình giải thuật di truyền mới.
4.3.1.Hàm đánh giá độ thích nghi
Donis-Diaz và cộng sự [38] đánh giá một tập câu tóm tắt tối ưu dựa trên độ tốt (goodness) và độ đa dạng (deversity). Độ tốt của một câu tóm tắt được đánh giá theo công thức (4.3). Độ tốt của một tập câu tóm tắt Gd được tính bằng trung bình cộng độ tốt của các câu tóm tắt trong tập câu như trong công thức (4.4) (l là số lượng câu tóm tắt trong tập câu).
𝐺𝑛 = 𝑇 ∙ 𝑆𝑡(𝑄) (4.3)
𝐺𝑑 = ∑𝑙𝑖=1𝐺𝑛𝑖
𝑙 (4.4)
Trong đó: T là độ đo đúng đắn, St(Q) là trọng số của từ lượng hóa Q được gán sẵn dựa trên đánh giá mức độ ưa thích của các từ lượng hóa. Trong nghiên cứu [38], năm từ lượng hóa được gán trọng số lần lượt là St(‘most’) = 1, St(‘much’) =
0.75, St(‘half’) = 0.20, St(‘some’) = 0.15, St(‘few’) = 0.05. Như vậy, từ lượng hóa diễn đạt cho tỷ lệ càng lớn thì trọng số càng lớn.
Độ đa dạng của một tập câu tóm tắt được tính bằng cơng thức (4.5). Trong đó, C là số lớp khi thực hiện phân cụm tập câu tóm tắt, l là số lượng câu trong tập câu tóm tắt.
𝐷𝑒 =𝐶
𝑙 (4.5)
Giá trị C là số cụm khi thực hiện phân cụm tập câu tóm tắt dựa trên hàm tính độ tương tự L như sau:
𝐿(𝑝1, 𝑝2) = {𝑌𝑒𝑠 𝑖𝑓 ∑𝑚𝑘=0𝐻(𝑝1𝑘, 𝑝2𝑘) < 2
𝑁𝑜 𝑖𝑛 𝑜𝑡ℎ𝑒𝑟 𝑐𝑎𝑠𝑒 (4.6) Hai câu tóm tắt p1 và p2 trích rút từ cơ sở dữ liệu gồm có m thuộc tính được biểu diễn bởi vectơ số gồm (m + 1) thành phần. Thành phần p10 và p20 là chỉ số của hạng từ lượng hóa Q trong Dom(Q), các thành phần p1i, p2i lần lượt là chỉ số của hạng từ trong Dom(Ai) của vectơ biểu diễn câu tóm tắt p1, p2 (Dom(Ai) – miền hạng từ của thuộc tính Ai). Nếu thuộc tính Ai khơng có trong câu tóm tắt thì thành phần thứ i trong vectơ biểu diễn câu tóm tắt nhận giá trị 0. Khi kết quả của hàm L(p1, p2) là ‘yes’ tức là hai câu tóm tắt p1và p2 là tương tự nhau. Trong đó, hàm H(p1k, p2k) được tính theo cơng thức (4.7) để so sánh thành phần thứ k trong hai vectơ có khác biệt nhau không. Thành phần thứ k khác biệt nhau (giá trị hàm H(p1k, p2k) = 1) khi: (1) p1k = 0 và p2k 0; p1k 0 và p2k = 0 (thuộc tính Akchỉ có trong một câu tóm tắt, khơng có trong câu tóm tắt cịn lại); (2) thuộc tính Ak cùng có trong cả hai câu tóm tắt, nhưng hai chỉ số hạng từ có sự khác biệt. Hai chỉ số của hạng từ trong cùng
Dom(Ak) được coi là khác biệt khi chúng ở hai vị trí trong thứ tự sắp xếp ngữ nghĩa tăng dần cách nhau lớn hơn 20% số lượng từ trong Dom(Ak). Ví dụ: Nếu Dom(Ak)= {’very low’, ‘low’, ‘little low’, ‘medium’, ‘little high’, ‘high’, ‘very high’}, hạng từ ‘low’ ở vị trí 2 và hạng từ ‘medium’ ở vị trí 4 có khoảng cách là |2 − 4| > 20%*7 = 1.4. Do đó, hai từ ‘low’ và ‘medium’ được coi là khác biệt. Trong khi, hạng từ ‘little low’ và ‘medium’ lần lượt ở vị trí 3 và 4, ta có |3 - 4| < 20%*7 = 1.4, nên hai hạng từ ‘little low’ và ‘medium’ được coi là không khác biệt.
𝐻(𝑝1𝑘, 𝑝2𝑘) = { 1 𝑖𝑓 |𝑝1𝑘− 𝑝2𝑘| > 𝑟𝑜𝑢𝑛𝑑 (20% ∗ 𝑠𝑖𝑧𝑒 (𝐷𝑜𝑚(𝐴𝑘)) 𝑜𝑟 𝑖𝑓 𝑝1𝑘 = 0 𝑎𝑛𝑑 𝑝2𝑘 ≠ 0 𝑜𝑟 𝑖𝑓 𝑝1𝑘 ≠ 0 𝑎𝑛𝑑 𝑝2𝑘= 0 0 𝑖𝑛 𝑜𝑡ℎ𝑒𝑟 𝑐𝑎𝑠𝑒 (4.7)
Hàm thích nghi Fit cho một cá thể, tương ứng với một tập câu tóm tắt, là tổng hợp của 2 độ đo: độ tốt của một tập câu tóm tắt Gd và độ đa dạng De theo cơng thức gộp nhập như sau:
𝐹𝑖𝑡 = 𝑚𝑔𝐺𝑑 + 𝑚𝑑𝐷𝑒 (4.8)
Trong đó mg, md lần lượt là trọng số của 2 độ đo Gd và De thỏa điều kiện mg
+ md = 1. Các tác giả trong [38] đã chọn mg = 0.7, md = 0.3, tức là độ tốt của tập các câu tóm tắt được gán trọng số gấp hơn 2 lần độ phong phú của tồn tập câu tóm tắt.
4.3.2.Các phép tốn trong mơ hình giải thuật di truyền lai Hybrid-GA
Trong [38], Doniz-Diaz và cộng sự mã hóa mỗi câu tóm tắt thành một gen, mỗi cá thể là một tập câu tóm tắt. Ban đầu, khởi tạo một quần thể gồm nhiều cá thể, tức là gồm nhiều tập câu tóm tắt ứng viên. Q trình tiến hóa thực hiện qua nhiều vòng lặp bởi các phép toán di truyền cơ bản (chọn lọc, lai ghép, đột biến) để làm tăng độ thích nghi của quần thể ban đầu. Cuối cùng, cá thể tốt nhất tương ứng tập câu tóm tắt tốt nhất được chọn làm kết quả của bài tốn tìm kiếm tập câu tóm tắt tối ưu theo hàm đánh giá Fit.
4.3.2.1.Các phép toán di truyền cơ bản
o Toán tử chọn lọc: qua mỗi lần tiến hóa có một tỷ lệ các cá thể tốt nhất (giá trị hàm đánh giá Fit lớn nhất) trong thế hệ hiện tại được chuyển sang thế hệ tiếp theo.
o Toán tử lai ghép: thực hiện lai ghép tại một điểm giữa hai cá thể được chọn ngẫu nhiên để sinh ra hai con. Toán tử lai ghép sẽ trao đổi các gen giữa hai cá thể, tức là trao đổi các câu tóm tắt giữa hai tập câu tóm tắt. Phép tốn lai ghép làm tăng độ đo tính đa dạng của các tập câu tóm tắt, khơng làm thay đổi độ tốt của từng câu tóm tắt nhưng có thay đổi độ tốt của cả tập câu tóm tắt.
o Tốn tử đột biến: một tỷ lệ nhỏ (thường khoảng 0.05) làm thay đổi một vài gen trong cá thể được chọn ngẫu nhiên bằng một gen mới được sinh ngẫu
nhiên, tức là thay thế một số câu tóm tắt trong tập câu. Tốn tử đột biến làm thay đổi cả độ tốt Gd và độ phong phú De của tập câu tóm tắt.
4.3.2.2.Hai phép tốn bổ sung
Phép tốn cleaning sẽ thay thế tất cả các gen tương ứng với các câu tóm tắt có giá trị đúng đắn T = 0 bởi một câu tóm tắt được sinh ngẫu nhiên khác. Tuy nhiên, nó chỉ được áp dụng với tần suất 10% số thế hệ hay số lần lặp tiến hóa.
Phép tốn improver sử dụng kỹ thuật tìm kiếm lân cận để thực hiện thay thế một câu tóm tắt hiện tại bởi một câu tóm tắt có giá trị đúng đắn T tăng lên hoặc qua ngưỡng 0.8. Trong quá trình tìm kiếm sẽ thay thế ngẫu nhiên một thành phần trong điều kiện lọc F hoặc kết luận S, cả từ lượng hóa Q. Phép thay thế có thể thực hiện thay thế thuộc tính này bởi thuộc tính khác hoặc thay thế hạng từ này bởi một hạng từ có ngữ nghĩa lân cận. Tốn tử được sử dụng với tỷ lệ, tần suất như thế nào tùy thuộc vào từng thực nghiệm cụ thể.
Thực nghiệm trong [38] trích rút tập câu tóm tắt tối ưu trên cơ sở dữ liệu
creep sử dụng các mơ hình giải thuật di truyền khác nhau đã chứng tỏ hiệu quả của các phép toán bổ sung cleaning và improver. Mơ hình di truyền có sử dụng phép toán cleaning cho kết quả tốt hơn mơ hình di truyền cơ bản. Mơ hình di truyền sử dụng cả hai phép tốn cleaning và improver lại cho kết quả tốt hơn mơ hình chỉ sử dụng phép toán cleaning.
4.3.3.Một số hạn chế trong mơ hình giải thuật di truyền lai Hybrid-GA và định
hướng khắc phục
Phép toán improver nhằm thay thế một câu tóm tắt hiện tại bởi một câu tóm tắt theo chiến lược thay thế lân cận hướng đến độ đo đúng đắn tốt hơn. Kết quả thực nghiệm trong [38] vẫn còn 3 trong số 30 câu tóm tắt có giá trị T < 0.8 làm giảm đánh giá độ tốt của tập câu tóm tắt. Kết quả này có thể do tập hạng từ lượng hóa chỉ có 5 hạng từ ‘none’, ‘few’, ‘half’, ‘much’, ‘most’, các tập mờ biểu diễn ngữ nghĩa cho 5 hạng từ tạo thành phân hoạch mạnh trên miền tham chiếu nên có thể sinh ra câu tóm tắt giá trị đúng đắn trong lân cận của 0.5.
Kết quả thực nghiệm trong [38] cho thấy vẫn cịn 1 trong 30 câu tóm tắt có giá trị T = 0. Tức là phép tốn cleaning chưa loại bỏ hết được các câu tóm tắt mà T
= 0. Các câu tóm tắt với T = 0 là do khơng có bản ghi nào trong cơ sở dữ liệu thỏa điều kiện lọc F.
Để khắc phục hạn chế nêu trên, tác giả luận án đề xuất khắc phục như sau: o Mở rộng tập các hạng từ lượng hóa bằng cách bổ sung thêm hạng từ có
tính riêng lớn hơn theo phương pháp xây dựng khung nhận thức ngôn ngữ (Linguistis Frame of Cognition - LFoC) dựa trên phương pháp luận của ĐSGT như trong chương 2. Vì cấu trúc tập mờ biểu diễn ngữ nghĩa cho từ lượng hóa được thiết kết theo thủ tục HA-TFS-MG tại mục 2.5.1 trong chương 2 ở dạng đa thể nên càng tăng mức tính riêng của tập hạng từ lượng hóa càng có cơ hội thu được các câu tóm tắt có giá trị đúng đắn gần với giá trị tối đa 1. Điều này đã được chứng tỏ thơng qua các thí nghiệm trong chương 3 về ưu điểm của tập từ lượng hóa khi được mở rộng để thêm nhiều từ có mức tính riêng lớn hơn.
o Chỉ sinh ngẫu nhiên thành phần lọc o(Fq), cấu trúc của thành phần kết luận
o(Es). Sau đó dùng chiến lược tham lam để xác định hạng từ ngôn ngữ trong o(Es) và Q sao cho giá trị đúng đắn T và thứ tự ngữ nghĩa của Q lớn nhất có thể. Chiến lược này được áp dụng hướng đến sinh các câu tóm tắt được ưu thích, tức là làm tăng độ tốt của câu tóm tắt.
o Câu tóm tắt có giá trị T = 0 tương ứng với các câu tóm tắt mà khơng có bản ghi nào trong cơ sở dữ liệu thỏa điều kiện lọc o(Fq). Do đó, để khơng xuất hiện các câu tóm tắt như này cần sử dụng độ đo hỗ trợ supp(o(Fq)) để đánh giá lực lượng các bản ghi thỏa điều kiện lọc o(Fq). Chỉ khi supp(o(Fq)) lớn hơn ngưỡng cho trước thì mới sinh câu tóm tắt mới.
Các ý tưởng cải tiến này được triển khai thành thủ tục sinh câu tóm tắt tốt dựa trên chiến lược tham lam. Sau đó, thủ tục này được sử dụng trong mơ hình giải thuật di truyền được đề xuất.