Tài liệu Các kỹ thuật lai ghép trong giải thuật di truyền

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ----------  ---------- NGUYỄN XUÂN TOÀN CÁC KỸ THUẬT LAI GHÉP TRONG GIẢI THUẬT DI TRUYỀN NGÀNH CÔNG NGHỆ THÔNG TIN MÃ SỐ 1.01.10 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TSKH. NGUYỄN XUÂN HUY HÀ NỘI - 2007 1 MỤC LỤC MỞ ĐẦU ............................................................................................................................ 3 Chƣơng 1. MỘT SỐ PHƢƠNG PHÁP TÁCH TỪ VÀ PHÂN LOẠI VĂN BẢN TIẾNG VIỆT ..................................................................................................................... 6 1.1. Tổng quan về tách từ và phân loại văn bản tiếng Việt ............................ 6 1.2. Hƣớng tiếp cận tách từ và phân loại văn bản tiếng Việt ......................... 8 1.2.1. Hƣớng tiếp cận dựa trên từ ..................................................................... 9 1.2.2. Hƣớng tiếp cận dựa trên ký tự .............................................................. 10 1.2.3. Một số nhận xét về các phƣơng pháp tách từ tiếng Việt ........................ 11 1.3. Phƣơng pháp tách từ và phân loại văn bản tiếng Việt dựa trên thống kê từ Internet và Giải thuật di truyền ............................................................... 11  Kết luận chƣơng 1 ................................................................................. 15 Chƣơng 2. GIẢI THUẬT DI TRUYỀN ...................................................................... 16 2.1. Tổng quan về giải thuật di truyền ........................................................ 16 2.2. Một số cách biểu diễn lời giải của giải thuật di truyền ......................... 19 2.2.1. Biểu diễn nhị phân ............................................................................... 19 2.2.2. Biểu diễn hoán vị ................................................................................. 20 2.2.3. Biểu diễn giá trị .................................................................................... 21 2.2.4. Biểu diễn dạng cây ............................................................................... 21 2.3. Các toán tử di truyền ........................................................................... 21 2.3.1. Đánh giá độ thích nghi của cá thể và toán tử chọn lọc .......................... 22 2.3.2. Toán tử lai ghép ................................................................................... 24 2.3.3. Toán tử đột biến ................................................................................... 25 2.4. Cơ sở toán học của giải thuật di truyền ................................................ 27 2.4.1. Một số khái niệm.................................................................................. 28 2.4.2. Định lý sơ đồ........................................................................................ 30 2.5. Những cải tiến của giải thuật di truyền ................................................ 32 2 2.5.1. Các toán tử cao cấp .............................................................................. 32 2.5.2. Các sơ đồ lựa chọn ............................................................................... 38  Kết luận chƣơng 2 ................................................................................. 39 Chƣơng 3. SỬ DỤNG GIẢI THUẬT DI TRUYỀN TÁCH TỪ TIẾNG VIỆT ....... 40 3.1. Cấu trúc âm tiết và mối tƣơng quan với “từ” tiếng Việt ....................... 40 3.1.1. Cấu trúc âm tiết năm thành phần .......................................................... 40 3.1.2. Cấu trúc âm tiết ba thành phần ............................................................. 42 3.1.3. So sánh cấu trúc hai loại âm tiết ........................................................... 49 3.2. Nguyên lý thống kê dựa trên Internet ................................................... 50 3.3. Sử dụng giải thuật di truyền để tách từ tiếng Việt ................................ 53 3.3.1. Khảo sát độ dài của “từ” trên từ điển .................................................... 54 3.3.2. Xử lý dữ liệu ........................................................................................ 55 3.3.3. Biểu diễn cá thể.................................................................................... 57 3.3.4. Khởi tạo các tham số ............................................................................ 58 3.3.5. Toán tử chọn lọc .................................................................................. 59 3.3.6. Toán tử lai ghép ................................................................................... 60 3.3.7. Toán tử đột biến ................................................................................... 61 3.3.8. Quá trình sinh sản ................................................................................ 62 3.4. Phân loại văn bản tiếng Việt ................................................................ 63  Kết luận chƣơng 3 ................................................................................. 63 KẾT LUẬN ...................................................................................................................... 65 TÀI LIỆU THAM KHẢO .............................................................................................. 66 PHỤ LỤC ......................................................................................................................... 70 3 MỞ ĐẦU Hơn hai thập kỷ trở lại đây, lƣợng thông tin đƣợc lƣu trữ trên các thiết bị điện tử không ngừng tăng lên. Do các ƣu điểm khi lƣu trữ tài liệu số nhƣ cách lƣu trữ gọn nhẹ, thời gian lƣu trữ lâu dài, tiện dụng trong trao đổi, dễ dàng sửa đổi… nên các phƣơng thức sử dụng giấy tờ trong công việc và trong giao dịch đã dần đƣợc số hoá chuyển sang các dạng văn bản lƣu trữ trên máy tính hoặc truyền tải trên mạng. Điều đó đã làm số lƣợng văn bản số tăng lên nhanh chóng. Cùng với sự gia tăng về số lƣợng văn bản, nhu cầu tìm kiếm văn bản cũng tăng theo. Với lƣợng văn bản đồ sộ thì việc phân loại văn bản tự động phục vụ quá trình tìm kiếm thông tin dễ dàng, nhanh chóng là cần thiết. Đồng thời, việc phân loại văn bản tự động sẽ giúp con ngƣời tiết kiệm đƣợc rất nhiều thời gian và công sức. Theo [29], “Việc phân loại văn bản tự động là việc gán các nhãn phân loại lên một văn bản mới dựa trên mức độ tương tự của văn bản đó so với các văn bản đã được gán nhãn trong tập huấn luyện”. Trong tiếng Anh đã có nhiều công trình nghiên cứu và đạt đƣợc kết quả nhƣ: Graph - Based Approach [6], Neural Network [12], Support Vector Machine [18], Linear Least Squares Fit [28]… Các phƣơng pháp trên đều dựa vào xác suất thống kê hoặc thông tin về trọng số của từ trong văn bản. Đối với tiếng Việt, đã có một số công trình nghiên cứu về phân loại văn bản: Conditional Random Fields and Support Vector Machine [7], Weighted Finit State Transducer and Neural Network [10], Dynamic Programming [20]… Các nghiên cứu trên đã đề cập đến khó khăn trong vấn đề xử lý văn bản để rút ra tần số xuất hiện của từ. Trong khi đó, để phân loại văn bản thì bƣớc tách từ đầu tiên là quan trọng. Đồng thời phần lớn các phƣơng pháp tách từ tiếng Việt đều dựa trên tập dữ liệu huấn luyện và từ điển trong khi hiện nay 4 chƣa có từ điển hay tập dữ liệu huấn luyện tiếng Việt đƣợc gán nhãn đủ lớn phục vụ việc này. Trong thời gian gần đây, một phƣơng pháp tiếp cận cho việc tách từ và phân loại văn bản là: Internet and Genetics Algorithm - Based Text Categorization (IGATEC) của H. Nguyen [17]. Điểm khác biệt của thuật toán là kết hợp giải thuật di truyền với việc trích xuất thông tin thống kê từ Internet thông qua một công cụ tìm kiếm thay vì lấy từ tập dữ liệu nhƣ các phƣơng pháp khác. Giải thuật di truyền cho phép xây dựng phƣơng pháp tìm kiếm song song (tìm kiếm tiến hóa) trên quần thể mà trong đó mỗi cá thể tƣơng ứng với một cách tách từ cho câu đang xét. Hàm thích nghi sẽ đánh giá độ thích nghi của các tài liệu thống kê, rút trích từ Internet sử dụng các công cụ tìm kiếm thông minh (Search Engine). Thông tin rút trích bao gồm tần số các tài liệu và thông tin tƣơng quan giữa các nhóm từ trong tài liệu. Trên cơ sở các phân tích trên, luận văn thực hiện tìm hiểu giải thuật di truyền, cơ sở toán học, các cải tiến của giải thuật di truyền và ứng dụng vào vấn đề tách từ tiếng Việt. Việc tách từ tiếng Việt trong luận văn này dựa trên ý tƣởng của thuật toán IGATEC nhƣng có bổ sung một vài cải tiến trong quá trình lai ghép và đột biến nhằm tăng độ chính xác. Ngoài phần mở đầu, kết luận và phụ lục, luận văn đƣợc chia thành các chƣơng chính nhƣ sau:  Chƣơng 1. Một số phƣơng pháp tách từ và phân loại văn bản tiếng Việt: tìm hiểu các hƣớng tiếp cận tách từ và phân loại văn bản tiếng Việt và phƣơng pháp tách từ tiếng Việt sử dụng giải thuật di truyền kết hợp với trích xuất thông tin thống kê từ Internet.  Chƣơng 2. Giải thuật di truyền: tìm hiểu về giải thuật di truyền, cơ sở toán học, các toán tử và các cải tiến của giải thuật di truyền. 5  Chƣơng 3. Sử dụng giải thuật di truyền để tách từ tiếng Việt: đề xuất một số cải tiến trong quá trình lai ghép và đột biến với mục tiêu tăng hiệu quả của thuật toán IGATEC. Mặc dù đã cố gắng hoàn thành luận văn trong phạm vi và khả năng cho phép nhƣng sẽ không tránh khỏi những thiếu sót. Hiện thời trong luận văn này mới chỉ dừng ở mức tìm hiểu, sử dụng giải thuật di truyền cho quá trình tách từ tiếng Việt phục vụ cho các chƣơng trình dịch chéo đa ngữ, phân loại tự động các văn bản tiếng Việt… Mong quý thầy cô và các bạn đọc thông cảm, có những ý kiến đóng góp để hoàn thiện đề tài. 6 Chƣơng 1 MỘT SỐ PHƢƠNG PHÁP TÁCH TỪ VÀ PHÂN LOẠI VĂN BẢN TIẾNG VIỆT 1.1. Tổng quan về tách từ và phân loại văn bản tiếng Việt Theo các kết quả nghiên cứu [7, 10, 20, 29], các phƣơng pháp phân loại văn bản tiếng Việt hiệu quả nhƣ: Support Vector Machine, Conditional Random Fields, Dynamic Programing… đều cần thông tin xác suất hay thống kê trọng số của từ. Thông qua tìm hiểu các phƣơng pháp này trong việc phân loại văn bản tiếng Việt, có thể nhận ra rằng việc tách từ là bƣớc đầu tiên hết sức quan trọng cần phải đƣợc giải quyết. Đối với các ngôn ngữ châu Á nhƣ tiếng Hoa, tiếng Nhật, tiếng Hàn và cả tiếng Việt, tách từ là một khó khăn chính trong việc phân loại văn bản. Mặc dù đƣợc viết bằng các ký tự La tinh mở rộng, tiếng Việt cũng có những đặc tính chung với các ngôn ngữ Đông Nam Á khác nhƣ khó xác định ranh giới giữa các từ và có nhiều điểm khác biệt về ngữ âm, văn phạm và ngữ nghĩa… so với tiếng Anh. Do đó, khó có thể áp dụng hƣớng tiếp cận đã đƣợc nghiên cứu và thử nghiệm thành công trên tiếng Anh [6, 12, 18, 29, 30]… cho phân loại văn bản tiếng Việt nếu không xây dựng thành công giải pháp cho việc tách từ trong văn bản tiếng Việt. Vì sao việc xác định ranh giới từ trong tiếng Việt lại là bài toán khó? Đơn vị cơ bản trong tiếng Việt là tiếng (hay “âm tiết”), không phải là từ. Trong [1] đã nêu ra một số đặc tính chính của từ trong tiếng Việt nhƣ sau: - Từ ở dạng nguyên thể, hình thức và ý nghĩa độc lập với cú pháp. - Từ đƣợc cấu trúc từ “tiếng” (hay “âm tiết”). 7 - Từ bao gồm từ đơn (từ một tiếng) và từ ghép (n tiếng với n < 5), bao gồm từ láy và từ ghép. Ví dụ: “Khoa học” là từ ghép gồm 2 “tiếng” trong tiếng Việt. Trong khi đó, định nghĩa về từ trong tiếng Anh nhƣ sau: “Từ là một nhóm ký tự có nghĩa, được phân cách bởi ký tự khoảng trắng trong câu” (Theo từ điển Webster). Dƣới đây là một số điểm khác biệt chính giữa tiếng Việt và tiếng Anh [2, 17, 25]. Đặc điểm Tiếng Việt Tiếng Anh Đơn vị cơ bản Tiếng (Âm tiết) Từ Tiền tố/Hậu tố Không có Có Không đồng nhất Đƣợc định nghĩa rõ Từ loại Ranh giới từ Tổ hợp có nghĩa dựa vào Khoảng trắng hoặc dấu câu ngữ cảnh của các tiếng Bảng 1.1. Các điểm khác biệt chính giữa tiếng Việt và tiếng Anh. Chính những đặc điểm khác biệt trên làm cho việc tách từ tiếng Việt trở nên khó khăn hơn. Theo Đinh Điền [10], trong một số phƣơng pháp tách từ tiếng Hoa và một số ngôn ngữ Đông Nam Á khác đƣợc thử nghiệm trên tiếng Việt thì điều kiện quan trọng cần có là một hệ thống từ điển và tập dữ liệu huấn luyện đầy đủ chính xác. Một từ điển hay một tập dữ liệu huấn luyện không hoàn chỉnh sẽ làm giảm hiệu suất của thuật toán. Hiện tại, chƣa có từ điển chuẩn hay dữ liệu huấn luyện tiếng Việt đƣợc gán nhãn đủ lớn phục vụ việc này. Do đặc điểm của tiếng Việt nên việc xây dựng bộ từ điển chuẩn hay dữ liệu này cần rất nhiều thời gian, công sức và chi 8 phí. Đây chính là vấn đề đáng lo nhất trong bài toán phân loại văn bản tiếng, xử lý ngôn ngữ tự nhiên và tìm kiếm thông tin tiếng Việt. 1.2. Hƣớng tiếp cận tách từ và phân loại văn bản tiếng Việt Theo các kết quả khảo sát của Foo và Li [14] về tách từ trong văn bản tiếng Hoa và qua tìm hiểu có thể thấy rằng có hai cách tiếp cận trong vấn đề tách từ và phân loại văn bản: Hƣớng tiếp cận dựa trên từ và hƣớng tiếp cận dựa trên ký tự. Vietnamese Segmentation Chinese Segmentation Character - Based Uni - Gram Lê Hà An Word - Based N - Gram H. Nguyen Statistic Dictionary Nguyễn Cẩm Tú Hybrid Đinh Điền Luận văn này Full Word / Phrase Shortest Match Longest Match Component Overlap Match Hình 1.1. Các hướng tiếp cận cơ bản trong việc tách từ tiếng Hoa và hướng tiếp cận trong tách từ tiếng Việt. 9 1.2.1. Hướng tiếp cận dựa trên từ Các hƣớng tiếp cận dựa trên từ đƣợc chia thành ba nhóm: dựa vào thống kê (Statistic Based), dựa vào từ điển (Dictionary Based) và nhóm lai (Hybrid). Giải pháp theo hƣớng tiếp cận dựa vào thống kê cần phải dựa vào thống tin thống kê nhƣ: từ, tần số ký tự, xác suất cùng xuất hiện trong một tập dữ liệu cơ sở… Tính hiệu quả của các giải pháp loại này chủ yếu dựa vào dữ liệu huấn luyện cụ thể đƣợc sử dụng. Đây là vấn đề khó khăn đối với bài toán tách từ tiếng Việt. Trong hƣớng tiếp cận dựa vào từ điển, các phân đoạn văn bản đƣợc đối sánh dựa vào từ điển. Hạn chế trong việc tách từ theo hƣớng tiếp cận dựa trên từ điển đó là cần phải thực hiện hoàn toàn dựa trên từ điển hoàn chỉnh, trong khi việc xây dựng từ điển hoàn chỉnh là không khả thi. Hƣớng tiếp cận lai áp dụng nhiều cách khác nhau để tận dụng ƣu điểm của các giải pháp. Mặc dù có đƣợc những ƣu điểm của các giải pháp nhƣng hƣớng tiếp cận này lại gặp phải các khóa khăn, phức tạp khác nhƣ: thời gian xử lý, không gian đĩa… Đinh Điền [10] đã xây dựng dữ liệu huấn luyện riêng (khoảng 10MB) dựa vào các tài nguyên, tin tức và sách điện tử trên Internet… Trên cơ sở tập dữ liệu tác giả sử dụng hệ thống tách từ tiếng Việt gồm hai tầng: tầng WFST ngoài việc tách từ còn xử lý thêm các vấn đề liên quan đến đặc thù của tiếng Việt nhƣ từ láy, tên riêng… và tầng mạng nơron dùng để khử nhập nhằng đối với các trƣờng hợp tầng WFST cho kết quả ngang nhau. Phƣơng pháp này cho kết quả với độ chính xác cao vì mục đích của tác giả là để phục vụ cho việc dịch máy. Tuy nhiên tập dữ liệu huấn luyện còn tƣơng đối nhỏ, khó có thể đảm bảo dung lƣợng và độ phong phú cho việc tách từ. 10 Tóm lại, các hƣớng tiếp cận phục vụ cho việc phân loại văn bản tiếng Việt dựa vào từ chỉ thực hiện tốt khi chúng ta có bộ từ điển tốt hay dữ liệu huấn luyện đủ lớn. 1.2.2. Hướng tiếp cận dựa trên ký tự Các hƣớng tiếp cận dựa trên ký tự (dựa trên “tiếng” - “âm tiết” trong tiếng Việt) có thể chia làm hai nhóm nhỏ: tiếp cận dựa trên một ký tự (unigram) và tiếp cận dựa trên nhiều ký tự (n-gram): Hƣớng tiếp cận dựa trên một ký tự chia văn bản thành các ký tự đơn lẻ để thực hiện tách từ. Hƣớng tiếp cận dựa trên nhiều ký tự (n-gram) chia văn bản ra thành nhiều chuỗi, mỗi chuỗi gồm hai, ba ký tự trở lên. So với hƣớng tiếp cận trên một ký tự, hƣớng tiếp cận này cho nhiều kết quả ổn định hơn. Ƣu điểm nổi bật của hƣớng tiếp cận dựa trên nhiều ký tự là tính đơn giản và dễ ứng dụng, ngoài ra còn có thuận lợi là ít tốn chi phí cho việc tạo chỉ mục (index) và xử lý nhiều câu truy vấn (query processing). Các phƣơng pháp dựa trên ký tự tuy đơn giản nhƣng đã đem lại một số kết quả trong việc xử lý Việt. Gần đây cũng có một số bài báo tiếp cận hƣớng tách từ và phân đoạn văn bản tiếng Việt theo hƣớng tiếp cận này: Lê Hà An [10] đã xây dựng tập dữ liệu thô và sử dụng quy hoạch động để tối ƣu hóa tổng xác suất của các phân đoạn trong văn bản (các ngữ đƣợc phân cách bởi các ký tự phân cách). Tập dữ liệu đầu vào đƣợc tác giả sử dụng nhỏ và thí nghiệm chỉ dừng lại ở việc tách từ có ba “tiếng”. Nguyễn Cẩm Tú [7] đang nghiên cứu, sử dụng hai phƣơng pháp Conditional Random Fields và Support Vector Machine cho việc phân loại văn bản tiếng Việt. 11 Trong bài báo của H. Nguyen [17], thay vì sử dụng tập dữ liệu thô cho quá trình phân loại, tác giả đã sử dụng thông tin thống kê trực tiếp từ Internet và sử dụng giải thuật di truyền để tìm ra những cách phân loại văn bản tối ƣu nhất của cùng một văn bản. Mặc dù bài báo chỉ mới trình bày những kết quả thử nghiệm bƣớc đầu, nhƣng cũng đã mở ra khả năng tìm hiểu, nghiên cứu, phát triển cho hƣớng tiếp cận này. 1.2.3. Một số nhận xét về các phương pháp tách từ tiếng Việt Một cách tổng quan, phƣơng pháp dựa trên từ cho độ chính xác khá cao (trên 95%) nhờ vào tập dữ liệu huấn luyện lớn, đƣợc đánh dấu chính xác, tuy nhiên hiệu suất của thuật toán phụ thuộc hoàn toàn vào dữ liệu huấn luyện. Với các phƣơng pháp cần phải sử dụng từ điển hoặc tập huấn luyện, ngoài việc tách từ thật chính xác, ta còn có thể nhờ vào các thông tin đánh dấu trong tập dữ liệu để thực hiện các mục đích khác nhƣ dịch máy, kiểm lỗi chính tả, từ điển đồng nghĩa... Hƣớng tiếp cận dựa trên ký tự có ƣu điểm là dễ thực hiện, thời gian thực thi tƣơng đối nhanh, tuy nhiên lại có độ chính xác không cao bằng phƣơng pháp dựa trên từ. Hƣớng tiếp cận này thích hợp cho các mục đích nghiên cứu không cần đến độ chính xác tuyệt đối cũng nhƣ các thông tin về từ loại nhƣ phân loại văn bản, lọc spam, firewall... Nhìn chung, hƣớng tiếp cận dựa trên ký tự có những ƣu điểm nhất định, mở ra các hƣớng nghiên cứu tiếp theo để nâng cao độ chính xác của phƣơng pháp tách từ này. 1.3. Phƣơng pháp tách từ và phân loại văn bản tiếng Việt dựa trên thống kê từ Internet và Giải thuật di truyền Phƣơng pháp tách từ và phân loại văn bản tiếng Việt dựa trên thống kê từ Internet và giải thuật di truyền (Internet and Genetics Algorithm-based Text Categorization for Documents in Vietnamese (IGATEC) do H. Nguyen giới 12 thiệu là hƣớng tiếp cận cho việc tách từ cho mục đích phân loại văn bản mà không cần dùng đến một từ điển hay tập huấn luyện nào. Trong hƣớng tiếp cận này, tác giả kết hợp giữa giải thuật di truyền với dữ liệu thống kê đƣợc trích xuất từ Internet tiến hoá một quần thể gồm các cá thể là các khả năng tách từ trong câu. Hàm thích nghi sẽ đánh giá độ thích nghi của các tài liệu thống kê, rút trích từ Internet sử dụng các công cụ tìm kiếm thông minh. Theo khảo sát, Hệ thống gồm ba phần: - Online Extractor. - Engine for Text Segmentation. - Text Categorization. Online Extractor Segmentation Online Extractor Segmentation Online Extractor …… Segmentation Online Extractor Hình 1.2. Mô hình hệ thống IGATEC. Online Extractor: thực hiện lấy thông tin về tần số xuất hiện của các từ trong văn bản bằng cách sử dụng một Search Engine nổi tiếng nhƣ Google. Sau đó, tác giả sử dụng các công thức sau đây để tính toán mức độ phụ thuộc lẫn nhau (Mutual Information) để là cơ sở tính hàm phù hợp fitness cho Engine 13 của giải thuật di truyền. - Công thức tính xác suất các từ xuất hiện trên Internet: count ( x) o p(x) = MAX (1.1) count ( x1 & x2 ) o p(x1 & x2) = MAX (1.2) với MAX là số lƣợng các tài liệu tiếng Việt đã đƣợc lập chỉ mục. count(x) số lƣợng văn bản trên Internet đƣợc tìm thấy có chứa từ x hoặc cùng chứa x1 và x2 đối với count(x1 & x2). - Tính xác suất độ phụ thuộc của một từ lên một từ khác: p( x1 & x2 ) p(x1 | x2) = p( x1 ) (1.3) Thông tin phụ thuộc lẫn nhau (Mutual Information) của các từ ghép đƣợc cấu tạo bởi n tiếng (cx = x1x2…xn) tính bởi công thức sau: p( x1 & x2 & ... & xn ) MI (cx) = n  p( x )  p( x j 1 j 1 & x2 & ... & xn ) (1.4) Engine for Text Segmentation: mỗi cá thể trong quần thể đƣợc biểu diễn bởi chuỗi các bit 0 và 1, trong đó, mỗi bit đại diện cho một tiếng trong văn bản, mỗi nhóm bit cùng loại đại diện cho một phân đoạn (Segment). Các cá thể đƣợc khởi tạo ngẫu nhiên, trong đó, mỗi Segment đƣợc giới hạn trong khoảng 5 tiếng. Engine sau đó thực hiện các toán tử lai ghép và đột biến làm tăng giá trị fitness của các cá thể nhằm đạt đƣợc cách tách từ tốt nhất có thể. Text Categorization: tác giả dùng độ hỗ trợ (Support Degree) của văn bản cần phân loại cho các từ khoá để phân loại văn bản. Công thức phân loại văn bản trong IGATEC do chính tác giả đề nghị dựa vào xác suất đồng xuất 14 hiện của các từ trong văn bản với một từ khóa nhất định, cụ thể: - Cho trƣớc một từ khóa k, độ phụ thuộc của từ x vào k đƣợc tính theo p (k & x) công thức (1.3) tức là: p(k | x) = p ( x) - Tiếp theo, độ liên quan (Relative) của một cách tách ngữ t với từ khóa k bằng tổng xác suất của tất cả các từ x xuất hiện đồng thời với k: p rel (t, k) =  p(k | x ) i 1 (1.5) i - Độ hỗ trợ của cách tách ngữ t vào chủ đề c = {k1,k2,…,ks} là: 1 n SP (t, c) =  rel (t | ki ) n i1 (1.6) với ki là tập các từ khóa đại diện cho chủ đề c. Theo công thức trên, tác giả cho rằng phân đoạn g = {t1, t2,…, tn} có độ hỗ trợ vào một chủ đề càng cao thì khả năng phân đoạn đó thuộc về chủ đề này càng lớn. Dựa vào các công thức, độ phụ thuộc của văn bản d đƣợc xác định theo công thức: m m 1 n SP (d, c) =  SP( g i | c) =   SP(tij | c) i 1 n j 1 i 1 (1.7) Kết quả ở công thức (1.7) cho thấy văn bản d sẽ thuộc về chủ đề có SP(d, c) lớn nhất.  Nhận xét về phƣơng pháp IGATEC: Phƣơng pháp IGATEC có ƣu điểm là: - Không cần sử dụng bất cứ tập dữ liệu huấn luyện hoặc từ điển nào. - Tƣơng đối đơn giản và không tốn thời gian huấn luyện. 15 Một số Hạn chế: - IGATEC có độ chính xác thấp nhƣng vẫn chấp nhận đƣợc đối với mục đích tách từ dành cho phân loại văn bản. - Thời gian chạy ban đầu khá chậm do phải lấy thông tin từ Internet mà đƣờng truyền ở Việt Nam còn hạn chế. - Chƣa có các thử nghiệm trên tập dữ liệu đủ lớn.  Kết luận chƣơng 1 Chƣơng 1, đã tìm hiểu về một số phƣơng pháp tách từ và phân loại văn bản tiếng Việt. Đồng thời trong chƣơng này cũng tìm hiểu và trình bày phƣơng pháp tách từ dựa trên giải thuật di truyền và thống kê Internet (IGATEC) do H. Nguyen giới thiệu cũng nhƣ các ƣu điểm và hạn chế của phƣơng pháp IGATEC. Các chƣơng tiếp theo sẽ đi sâu tìm hiểu giải thuật di truyền, cơ sở toán học và các cải tiến của giải thuật... Trên cơ sở đó đề xuất một số cải tiến nhằm tăng hiệu quả cho thuật toán IGATEC. 16 Chƣơng 2 GIẢI THUẬT DI TRUYỀN 2.1. Tổng quan về giải thuật di truyền Giải thuật di truyền (Genetic Algorithm - GA) lần đầu đƣợc tác giả Holland giới thiệu vào năm 1962 [15, 16]. Giải thuật di truyền mô phỏng theo cơ chế của quá trình chọn lọc và di truyền trong tự nhiên [3, 4, 5, 9, 11, 13, 15, 16, 22, 25]. Từ tập các lời giải có thể ban đầu, thông qua nhiều bƣớc tiến hoá để hình thành các tập mới với những lời giải tốt hơn, cuối cùng sẽ tìm đƣợc lời giải gần tối ƣu nhất. Giải thuật di truyền sử dụng các thuật ngữ lấy từ di truyền học: - Một tập hợp các lời giải đƣợc gọi là một lớp hay quần thể (Population). - Mỗi lời giải biểu diễn bởi một nhiễm sắc thể hay cá thể (Chromosome). - Nhiễm sắc thể đƣợc tạo thành từ các gen. Một quá trình tiến hoá đƣợc thực hiện trên một quần thể tƣơng đƣơng với sự tìm kiếm trên không gian các lời giải có thể của bài toán. Quá trình tìm kiếm này luôn đòi hỏi sự cân bằng giữa hai mục tiêu: Khai thác lời giải tốt nhất và xem xét toàn bộ không gian tìm kiếm. Giải thuật di truyền thực hiện tìm kiếm theo nhiều hƣớng bằng cách duy trì tập hợp các lời giải có thể và khuyến khích sự hình thành và trao đổi thông tin giữa các hƣớng. Tập lời giải phải trải qua nhiều bƣớc tiến hoá, tại mỗi thế hệ, một tập mới các cá thể đƣợc tạo ra có chứa các phần của những cá thể thích nghi nhất trong thế hệ cũ. Đồng thời giải thuật di truyền khai thác một cách có hiệu quả thông tin trƣớc đó để suy xét trên điểm tìm kiếm mới với mong muốn có đƣợc sự cải thiện qua từng thế hệ. Nhƣ vậy, các đặc trƣng đƣợc đánh giá tốt sẽ có cơ 17 hội phát triển và các tính chất tồi (không thích nghi với môi trƣờng) sẽ có xu hƣớng biến mất. Giải thuật di truyền tổng quát đƣợc mô tả nhƣ sau: PROCEDURE GeneticAlgorithm; BEGIN T:=0; Khởi tạo lớp P(t); Đánh giá lớp P(t); While not (Điều_kiện_kết_thúc) do Begin t:=t+1; Chọn lọc P(t) từ P(t-1); Kết hợp các cá thể của P(t); Đánh giá lớp P(t); end; END; Trong đó: - Tập hợp các lời giải ban đầu đƣợc khởi tạo ngẫu nhiên. - Trong vòng lặp thứ t, GeneticAlgorithm xác định tập các nhiễm sắc thể trong quần thể P(t)={x1t, x2t, …, xnt} bằng cách chọn lựa các nhiễm sắc thể thích nghi hơn từ quần thể P(t-1). Mỗi nhiễm sắc thể xit đƣợc đánh giá để xác định độ thích nghi của nó và một số thành viên của P(t) lại đƣợc tái sản xuất nhờ các toán tử chọn lọc, lai ghép và đột biến. Khi áp dụng giải thuật di truyền để giải quyết một bài toán cụ thể, cần phải xác định rõ các vấn đề sau: 18 1. Chọn các cách biểu diễn di truyền nào đối với những lời giải có thể của bài toán? 2. Tạo tập lời giải ban đầu nhƣ thế nào? 3. Xác định hàm đánh giá để đánh giá mức độ thích nghi của các cá thể trong quần thể. 4. Xác định các toán tử di truyền để sản sinh con cháu. 5. Xác định giá trị các tham số mà giải thuật di truyền sử dụng nhƣ kích thƣớc tập lời giải, xác suất áp dụng các toán tử di truyền… Nhƣ vậy giải thuật di truyền là một giải thuật lặp nhằm giải quyết các bài toán tìm kiếm, nó khác với các giải thuật tối ƣu thông thƣờng ở những điểm cơ bản sau: - Giải thuật di truyền làm việc với bộ mã của tập thông số chứ không làm việc trực tiếp với giá trị của các thông số. - Giải thuật di truyền tìm kiếm song song trên một quần thể chứ không tìm kiếm từ một điểm, mặt khác nhờ áp dụng các toán tử di truyền, nó sẽ trao đổi thông tin giữa các điểm, nhƣ vậy sẽ giảm bớt khả năng kết thúc tại một cực tiểu cục bộ mà không tìm thấy cực tiểu toàn cục. - Giải thuật di truyền chỉ sử dụng thông tin của hàm mục tiêu để đánh giá quá trình tìm kiếm chứ không đòi hỏi các thông tin bổ trợ khác. - Các luật chuyển đổi của giải thuật di truyền mang tính xác suất chứ không mang tính tiền định. Các thông số của bài toán đƣợc mã hoá thành các chuỗi. Cách đơn giản nhất là chúng ta dùng chuỗi bit để mã hoá các thông số của bài toán. Mỗi thông số đƣợc mã hoá bằng một chuỗi bit có độ dài nào đó, sau đó nối chúng lại với nhau, ta sẽ có một chuỗi mã hoá cho tập các thông số. Để tính toán giá trị hàm mục tiêu tƣơng ứng với mỗi chuỗi thông số, ta phải giải mã bộ thông số này theo một quy tắc nào đó. Giải thuật di truyền tìm kiếm song song trên một tập 19 các chuỗi, do đó giảm thiểu đƣợc khả năng bỏ qua các cực trị toàn cục và dừng lại ở cực trị địa phƣơng. Điều này giải thích vì sao giải thuật di truyền mang tính toàn cục. Hiện nay giải thuật di truyền đƣợc áp dụng ngày càng nhiều trong kinh doanh, khoa học và kỹ thuật vì tính chất không quá phức tạp mà hiệu quả của nó. Hơn nữa, giải thuật di truyền không đòi hỏi khắt khe đối với không gian tìm kiếm nhƣ giả định về sự liên tục, sự có đạo hàm... Bằng lý thuyết và thực nghiệm, giải thuật di truyền đã đƣợc chứng minh là giải thuật tìm kiếm toàn cục mạnh trong các không gian lời giải phức tạp. 2.2. Một số cách biểu diễn lời giải của giải thuật di truyền Biểu diễn lời giải là vấn đề đầu tiên đƣợc quan tâm tới khi bắt tay vào giải quyết một bài toán bằng giải thuật di truyền. Việc lựa chọn cách biểu diễn lời giải nhƣ thế nào phụ thuộc vào từng lớp bài toán thậm chí vào từng bài toán cụ thể. Giải thuật di truyền kinh điển dùng chuỗi nhị phân có chiều dài xác định để biểu diễn lời giải [16]. Tuy nhiên, thực tế cho thấy cách biểu diễn này khó áp dụng trực tiếp cho các bài toán tối ƣu cỡ lớn có nhiều ràng buộc. Vì lý do đó, giải thuật di truyền cải tiến hay còn gọi là Chương trình tiến hoá đã tìm kiếm các cách biểu diễn thích nghi và tự nhiên hơn với các bài toán thực tế nhƣ: Biểu diễn theo trật tự, theo giá trị thực, bằng cấu trúc cây, ma trận [5]… Phần tiếp theo sẽ trình bầy tổng quan về các cách biểu diễn đó. 2.2.1. Biểu diễn nhị phân Trong biểu diễn nhị phân (Binary Encoding), mỗi nhiễm sắc thể là một chuỗi các bit 0 hoặc 1. Chẳng hạn: NST A: 101100101100101011100101