Xây dựng ứng dụng tóm lược tự động văn bản tiếng việt

liệu 8. POS Part of Speech Từ loại 9. RST Rhetorical Structure Theory Lý thuyết cấu trúc tu từ 10 HMM Hidden Markov Model Mô hình Markov ẩn DANH MỤC HÌNH VẼ Hình 2.1: Phân tích cú pháp 25 Hình 2.2: Học luật chuyển đổi cú pháp Anh - Việt 29 Hình 3.1: Tóm tắt trang tin 33 Hình 3.2: Tóm tắt hoạt động để hiển thị trên thiết bị cầm tay 33 Hình 3.3: Tóm tắt danh sách tìm kiếm từ Google và gợi ý đọc tiếp 34 Hình 3.4: Tóm tắt tài liệu khoa học 34 Hình 3.5: Mô hình hệ Tóm tắt văn bản tổng quát 39 Hình 3.6: Mô hình một hệ Trích rút văn bản 40 Hình 3.7: Quan hệ lẫn nhau giữa các đoạn trong văn bản 42 Hình 3.8: Giao diện SweSUM - Hệ thống Tóm tắt đa ngôn ngữ 56 Hình 3.9: Giao diện và kết quả trích rút văn bản của Microsoft Word 57 Hình 4.1: Mô hình ứng dụng Tóm lược văn bản tiếng Việt 61 Hình 4.2: Mô hình hóa văn bản 61 Hình 4.3: Giải thuật tách term từ trái qua 63 Hình 4.4: Giải thuật tách term từ phải qua 65 Hình 4.5: Phương pháp tiêu đề 67 Hình 4.6: Phương pháp tần suất xuất hiện 70 Hình 5.1: Giao diện chính 77 Hình 5.2: Giao diện kiểm thử 78 Hình 5.3: Giao diện phân tách đoạn và câu 79 Hình 5.4: Giao diện phân tách thuật ngữ của đoạn 80 Hình 5.5: Kết quả thực thi phương pháp TFxIDF 81  MỤC LỤC DANH MỤC TỪ VIẾT TẮT 1 DANH MỤC HÌNH VẼ 2 MỤC LỤC 3 LỜI NÓI ĐẦU 7 Chương 1. KHAI PHÁ VĂN BẢN 10 1.1. Khai phá dữ liệu 10 1.2. Khai phá văn bản 11 1.3. Biểu diễn văn bản 12 1.3.1. Mô hình boolean 13 1.3.2. Mô hình không gian vector 13 a. Mô hình không gian vector chuẩn 13 b. Kỹ thuật TFxIDF 14 c. Mô hình vector thưa và các mô hình không gian vector khác 15 1.3.3. Các mô hình biểu diễn văn bản khác 16 a. Mô hình Xác suất 16 b. Mô hình Mạng Bayes 16 c. Mô hình tập thô dung sai 17 1.4. Các bài toán Khai phá văn bản điển hình 17 1.4.1. Bài toán Phân lớp văn bản 17 1.4.2. Bài toán Phân nhóm văn bản 18 1.4.3. Bài toán Đánh chỉ mục - Tìm kiếm 19 1.4.4. Bài toán Tóm tắt văn bản 19 1.5. Kết chương 20 Chương 2. XỬ LÝ NGÔN NGỮ TỰ NHIÊN 21 2.1. Tổng quan về Xử lý ngôn ngữ tự nhiên. 21 2.2. Các vấn đề cơ bản của Xử lý ngôn ngữ tự nhiên 23 2.2.1. Phân tách thuật ngữ - Phân tách đoạn và câu 23 2.2.2. Gán nhãn từ loại 24 2.2.3. Phân tích cú pháp 25 2.2.4. Phân tích ngữ nghĩa 26 2.3. Các đặc trưng ngôn ngữ của tiếng Việt 26 2.3.1 Đặc trưng về ngữ âm và âm vị 26 2.3.2 Đặc trưng về từ pháp và hình thái 27 2.3.3. Đặc trưng về ngữ pháp 28 2.4. Kết chương 30 Chương 3. BÀI TOÁN TÓM TẮT VĂN BẢN 31 3.1. Giới thiệu chung 31 3.1.1. Tóm tắt văn bản là gì ? 32 3.1.2. Các tiêu chí đánh giá 34 3.1.3. Phân loại bài toán Tóm tắt văn bản 35 3.2. Mô hình Tóm tắt văn bản 38 3.2.1. Mô hình chung 38 3.2.2. Các phương pháp áp dụng trong pha Phân tích 40 3.2.2.1. Phương pháp thống kê (Statistical Methods) 41 3.2.2.2 . Phương pháp cấu trúc 42 3.2.2.3. Kết luận về các phương pháp trong pha Phân tích 44 3.2.3. Các phương pháp áp dụng trong pha Biến đổi 45 3.2.3.1. Giản lược về cấu trúc câu ( Syntactic Condensation ) 45 3.2.3.2. Giản lược về mặt ngữ nghĩa ( Semantic Condensation) 46 3.2.3.3. Kết luận về các phương pháp trong pha Biến đổi 48 3.2.4. Các phương pháp áp dụng trong pha Generation 48 3.2.4.1. Phương pháp hiển thị phân đoạn ( Segmental Display ) 48 3.2.4.2. Phương pháp Hiển thị 50 3.2.4.3. Kết luận về các phương pháp trong pha Hiển thị 50 3.3. Đánh giá kết quả tóm tắt 51 3.3.1. Đánh giá bên trong (Intrinsic Evaluation) 52 3.3.1.1. Độ chặt chẽ mạch lạc ( Coherence ) 52 3.3.1.2. Độ hàm chứa thông tin ( Informationess ) 52 3.3.2. Đánh giá bên ngoài ( Extrinsic Evaluation ) 52 3.3.2.1. Độ phù hợp ( Relevance ) 52 3.3.2.2. Độ dễ đọc dễ hiểu ( Reading Comprehence ) 52 3.3.3. So sánh đánh giá bên trong - bên ngoài 52 3.3.4. Các phương pháp đánh giá 53 3.3.4.1. Độ chính xác (Precision ) và độ hồi tưởng (Recall) 53 3.3.4.2. Đánh giá độ tương tự về nội dung (Content-based Similarity) 54 3.3.4.2. Độ tương quan phù hợp (Relevance Correlation) 54 3.3.6. Các hệ đánh giá ứng dụng tóm tắt văn bản 55 3.4. Một số hệ thống tóm tắt văn bản trên thế giới 55 3.5. Kết chương 58 Chương 4. XÂY DỰNG ỨNG DỤNG TÓM LƯỢC VĂN BẢN TIẾNG VIỆT 59 4.1. Mô hình xây dựng ứng dụng 59 4.2. Cài đặt tiền xử lý văn bản tiếng Việt 61 4.2.1. Chuẩn hóa văn bản 61 4.2.2. Mô hình hóa văn bản. 61 4.2.3. Tách thuật ngữ. 62 4.3. Lựa chọn, cài đặt các kĩ thuật sử dụng trong bài toán Tóm tắt 65 4.3.1. Các phương pháp trong pha Phân tích 65 a. Phương pháp Title 66 b. Phương pháp Heading 67 c. Phương pháp NamedEntity - NE 68 d. Phương pháp Quan hệ liên đoạn (Paragraph Cooccurence) 69 e. Phương pháp Tần suất xuất hiện của thuật ngữ 69 f. Phương pháp TFxIPF (Term Frequency times Inverted Paragraph Frequency) 70 4.3.2. Các phương pháp trong pha Biến đổi 71 4.3.2.1. Biến đổi nhờ vào rút gọn câu 71 4.3.2.2. Giản lược câu về mặt ngữ nghĩa 74 4.3.3. Các phương pháp trong pha Hiển thị 74 4.4. Kết chương 75 Chương 5. KIỂM THỬ VÀ ĐÁNH GIÁ ỨNG DỤNG 76 5.1. Giao diện kết quả thực nghiệm 76 5.2. Tập kiểm thử 81 5.3. Kết quả kiểm thử và đánh giá 82 5.3.1. Kiểm thử thuật toán tách term tiếng Việt 82 5.3.2. Kiểm thử thuật toán tách named Entity 83 5.3.3. Kiểm thử, đánh giá module chọn câu quan trọng 83 5.3.3.1. Phương pháp truyền thống 84 5.3.3.2. Phương pháp đánh giá theo độ tương tự nội dung 85 5.3.4. Kiểm thử đánh giá rút gọn câu 86 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 89 TÀI LIỆU THAM KHẢO 90 LỜI NÓI ĐẦU Hai thập kỷ gần đây, khắp nơi trên thế giới tràn ngập thông tin. Chính sự phát triển nhanh chóng của Công nghệ thông tin và Truyền thông đã đem lại cho thế giới của chúng ta bộ mặt mới. Các ứng dụng của Công nghệ thông tin - Truyền thông đã hiện diện trong hầu hết các ngành, các lĩnh vực của cuộc sống, kéo theo chúng là những thay đổi đáng kể. Nền kinh tế tri thức, hợp tác toàn cầu, những công việc quản lý, vận hành những hoạt động từ vi mô tới vĩ mô của doanh nghiệp, tin học hóa quy trình hành chính, điều khiển tác nghiệp, giải trí, liên lạc, trợ giúp... là những ứng dụng tiêu biểu của Công nghệ Thông tin và Truyền thông. Đặc biệt, sự ra đời của Internet - Mạng thông tin toàn cầu - được coi là nguyên nhân chính, thúc đẩy sự bùng nổ thông tin trên toàn thế giới. Những lợi ích mà Internet mang lại quá lớn khiến chúng ta phụ thuộc nhiều vào nó. Những người biết sử dụng linh hoạt và đúng đắn những lợi thế này sẽ phần nào vượt lên trên những thách thức của nền kinh tế tri thức toàn cầu để thu được những thành công trong công việc cũng như cuộc sống. Thông qua Internet, những thông tin quý giá về mọi lĩnh vực đều sẵn sàng đợi chúng ta khám phá và lĩnh hội. Trong thế giới thông tin đa dạng phong phú như vậy, nhu cầu thu thập được những thông tin cần thiết, có giá trị đồng thời xử lý chúng thành dạng dữ liệu mong muốn là nhu cầu chính đáng và cấp thiết của nhân loại. Lĩnh vực của Công nghệ thông tin có thể đáp ứng những nhu cầu to lớn này là Khai phá dữ liệu. Khai phá dữ liệu, vốn chỉ là một giai đoạn trong bảy giai đoạn của quá trình Phát hiện tri thức trong cơ sở dữ liệu, tuy nhiên, do là giai đoạn chính yếu, nên chúng ta thường đồng nhất, hay nói chính xác hơn là lấy Khai phá dữ liệu làm đại diện cho cả quá trình Phát hiện tri thức trong cơ sở dữ liệu. Và vì vậy, Khai phá dữ liệu được hiểu như một quá trình lấy ra các thông tin quan trọng từ các dạng CSDL, biến đổi, xử lý chúng nhằm phục vụ những mục đích cụ thể của con người. Các phương pháp thường dùng trong Khai phá dữ liệu là các phương pháp Trích chọn, Thống kê hay Phân loại... Do phần lớn dữ liệu ở dạng văn bản nên một lĩnh vực nhỏ hơn là Khai phá văn bản được quan tâm chú ý hơn cả. Và trong đồ án này, em xin đề cập tới Khai phá văn bản như là tiền đề cho việc giải quyết bài toán Tóm tắt văn bản. Khai phá dữ liệu - Khai phá văn bản tuy ra đời muộn nhưng đã đạt được nhiều thành tựu đáng kể và tất nhiên cũng đóng góp rất nhiều cho ngành Khoa học máy tính. Trên thế giới cũng như ở Việt Nam, các vấn đề của Khai phá văn bản đã và đang được tìm hiểu nghiên cứu cũng như xây dựng các ứng dụng mang tính thực tiễn cao. Tuy nhiên, vẫn còn rất nhiều vấn đề cần phải giải quyết, đặc biệt là ở Việt Nam, khi Khai phá văn bản mới được chúng ta quan tâm tới trong khoảng chục năm trở lại đây. Các bài toán điển hình của Khai phá văn bản như Phân lớp văn bản, Phân nhóm văn bản hiện mới trong quá trình nghiên cứu, chưa có một sản phẩm nào mang tính thương mại trên thị trường. Một bài toán khác của Khai phá văn bản là Thu thập thông tin đã được cài đặt thành các ứng dụng tìm kiếm trên mạng như các bộ máy tìm kiếm của Netnam (PanVietNam) hay Tinh Vân (Vinaseek). Nhưng những ứng dụng như vậy còn quá ít và chưa đáp ứng đầy đủ cho các nhu cầu to lớn của nền Công nghệ thông tin Việt Nam. Trong khi lĩnh vực Khai phá dữ liệu mới trở thành đề tài nóng bỏng, cấp thiết gần đây do sự bùng nổ thông tin toàn cầu thì trong ngành Khoa học máy tính, có một lĩnh vực khác đã ra đời cách đây khá lâu, và cũng đã có nhiều thành tựu trong suốt quá trình phát triển của mình. Đó là lĩnh vực Xử lý ngôn ngữ tự nhiên. Mục đích của Xử lý ngôn ngữ tự nhiên là giúp cho máy tính và con người hiểu nhau hơn, thuận tiện hơn trong quá trình làm việc và đem lại lợi ích tối đa cho con người. Thông qua các giao tiếp thân thiện, dễ hiểu giữa người và máy, việc đưa Công nghệ thông tin thật sự đi vào đời sống nhân loại là mục tiêu lớn nhất mà Xử lý ngôn ngữ tự nhiên hướng tới. Xử lý ngôn ngữ tự nhiên là quá trình xử lý sao cho máy tính có thể hiểu được một thông tin giống như cách mà con người hiểu thông tin đó thông qua các khía cạnh ngôn ngữ bao hàm trong nó. Theo định nghĩa này thì Xử lý ngôn ngữ tự nhiên là một phần của Trí tuệ nhân tạo - làm cho máy tính nắm bắt, thao tác, mô phỏng cách mà con người thực hiện. Vì vậy các phương pháp của Trí tuệ nhân tạo thường được dùng trong lĩnh vực Xử lý ngôn ngữ tự nhiên, kết hợp với các đặc trưng của ngành ngôn ngữ học như hình thái, ngữ pháp, ngữ nghĩa… Các bài toán điển hình của Xử lý ngôn ngữ tự nhiên là Trả lời tự động, Dịch máy, Sinh văn bản tự động, Kiểm tra chính tả… Như vậy, hai lĩnh vực Khai phá dữ liệu và Xử lý ngôn ngữ tự nhiên có nhiều điểm khác biệt mặc dù cùng sử dụng một số các phương pháp của Trí tuệ nhân tạo. Nói đến Khai phá dữ liệu là nói đến việc tìm ra thông tin quan trọng, thông tin mong muốn từ một lượng lớn dữ liệu, còn nói đến Xử lý ngôn ngữ tự nhiên là nói đến việc máy tự phân tích và hiểu những khía cạnh ngôn ngữ trong thông tin cụ thể. Tuy nhiên, có một bài toán điển hình của Khai phá dữ liệu có sử dụng rất nhiều những khái niệm, mô hình, phương pháp của Xử lý ngôn ngữ tự nhiên, đó là bài toán Tóm tắt văn bản. Bài toán tóm tắt văn bản thật ra đã được coi là một vấn đề của Xử lý ngôn ngữ tự nhiên khi nó lần đầu tiên được đề cập và nghiên cứu một cách nghiêm túc trong bài báo khoa học của Luhn vào năm 1958 [17] và tiếp đó là của Edminson vào năm 1969 [21]. Như vậy, Tóm tắt văn bản đã ra đời trước khi có sự ra đời của Khai phá văn bản ! Và khi Khai phá văn bản ra đời, dựa trên những đặc điểm của nó, người ta mới xếp Tóm tắt văn bản vào lĩnh vực mới mẻ này. Tóm tắt văn bản là quá trình chắt lọc những thông tin quan trọng nhất từ một nguồn để tạo ra một bản ngắn gọn hơn đáp ứng các nhiệm vụ cụ thể và người dùng cụ thể. Tóm tắt văn bản làm nhiệm vụ chọn ra các câu hàm chứa ý chính, các câu quan trọng nên về bản chất nó thuộc lĩnh vực của Khai phá văn bản. Tuy nhiên trong quá trình chắt lọc, rút gọn thì cần có sự áp dụng của các phương pháp Xử lý ngôn ngữ tự nhiên nếu muốn kết quả ra là một văn bản dễ đọc, dễ hiểu và mang ý nghĩa ngôn ngữ tự nhiên như đầu vào của nó. Tóm tắt văn bản có rất nhiều ứng dụng trong ngành Công nghệ thông tin cũng như Ngôn ngữ học và một số ngành khác. Trên thế giới đã có rất nhiều các ứng dụng Tóm tắt văn bản, với những mục đích nghiên cứu cũng như thương mại. Mặc dù vậy, do những khó khăn và thách thức riêng, Tóm tắt văn bản hiện nay chưa được nghiên cứu nhiều ở Việt Nam so với các bài toán điển hình khác trong lĩnh vực Khai phá văn bản. Chính vì lý do này em đã chọn Tóm tắt văn bản tiếng Việt là đề tài đồ án tốt nghiệp, mong muốn góp một phần công sức cho sự phát triển của Khai phá văn bản tiếng Việt nói riêng và Công nghệ thông tin Việt Nam nói chung. Trong đồ án này em muốn trình bày những kết quả tìm hiểu về bài toán Tóm tắt văn bản và bước đầu xây dựng một Ứng dụng tóm tắt văn bản tiếng Việt, sử dụng kết hợp các phương pháp của Khai phá văn bản và Xử lý ngôn ngữ tự nhiên có xét tới những đặc trưng về ngôn ngữ của tiếng Việt. Đồ án gồm các phần sau : Chương 1. Trình bày về lĩnh vực Khai phá dữ liệu nói chung và Khai phá văn bản nói riêng, các vấn đề mô hình hóa văn bản cũng như đề cập sơ qua một số bài toán Khai phá văn bản điển hình. Chương 2. Trình bày về lĩnh vực Xử lý ngôn ngữ tự nhiên, các vấn đề chung của Xử lý ngôn ngữ tự nhiên, các đặc trưng ngôn ngữ tiếng Việt cũng như các vấn đề riêng khi xử lý tự động văn bản tiếng Việt. Chương 3. Trình bày những vấn đề cơ bản về bài toán Tóm tắt văn bản, bao gồm mô tả khái niệm chung và phân loại một bài toán Tóm tắt văn bản, lịch sử phát triển và những ứng dụng của Tóm tắt văn bản, mô hình chung và các phương pháp xây dựng một ứng dụng Tóm tắt văn bản… Chương 4. Trình bày việc thiết kế và xây dựng ứng dụng tóm lược văn bản tiếng Việt VTAS dựa trên một số phương pháp trong các phương pháp đã nêu ở chương 3. Ngoài ra trong chương này, những cài đặt tiền xử lý văn bản cũng được em đề cập đến với những nét mới so với các công việc tương tự trước đây của một số nhà nghiên cứu lĩnh vực Khai phá văn bản tiếng Việt. Chương 5. Trình bày việc kiểm thử và đánh giá ứng dụng VTAS, các kết quả thực nghiệm của chương trình. Sau đó là phần kết luận và các hướng phát triển sắp tới của đề tài này. Cuối cùng là phần tài liệu tham khảo và các phụ lục của đồ án.  Chương 1. KHAI PHÁ VĂN BẢN Trong chương này em xin trình bày những vấn đề cơ bản của lĩnh vực Khai phá dữ liệu và Khai phá văn bản : Khái niệm chung về Khai phá dữ liệu và Khai phá văn bản Các mô hình biểu diễn văn bản Một số bài toán điển hình của lĩnh vực Khai phá văn bản 1.1. Khai phá dữ liệu Khai phá dữ liệu, thuật ngữ mới ra đời từ đầu những năm 90 của thế kỷ trước, ban đầu được dùng để nói đến quá trình phát hiện, trích rút ra những thông tin hữu dụng từ một lượng lớn dữ liệu lưu trữ trong các loại cơ sở dữ liệu khác nhau [22]. Vào những năm trở lại đây, một khái niệm mới ra đời, đó là khái niệm Phát hiện tri thức trong cơ sở dữ liệu ( Knowledge Discovery in Databases). Quá trình Phát hiện tri thức trong cơ sở dữ liệu gồm bảy giai đoạn [22]: Làm sạch dữ liệu trước khi thu thập (Data cleaning) Tích hợp dữ liệu từ các nguồn khác nhau (Data Integration) Chọn lựa dữ liệu ứng viên (Data Selection) Biến đổi dữ liệu thành dạng chuẩn để xử lý (Data Transformation) Khai phá dữ liệu (Data Mining) Đánh giá kết quả (Evaluation) Biểu diễn tri thức (Knowledge Presentation) Như vậy Khai phá dữ liệu chỉ là một trong bảy giai đoạn của quá trình Phát hiện tri thức trong cơ sở dữ liệu. Tuy nhiên đây là giai đoạn chính nên sau này người ta thường đồng nhất hai khái niệm Khai phá dữ liệu và Phát hiện tri thức trong cơ sở dữ liệu. Cả hai thuật ngữ này hiện nay dùng để chỉ quá trình phân tích một lượng lớn dữ liệu để tìm ra tri thức tiềm ẩn trong đó. Định nghĩa này hàm chứa nhiều điều. Tri thức, khái niệm ở mức cao nhất trong mục phân cấp Dữ liệu - Thông tin - Tri thức, dùng để chỉ những dữ liệu có quan hệ với nhau, mang tính định hướng tập trung (thông tin), đồng thời qua đó chúng ta có thể thấy được tính chủ động và những vận động quá khứ cũng như xu hướng tương lai của thông tin đó. Quá trình Khai phá dữ liệu không chỉ dừng ở mức độ phát hiện mà nó thực hiện việc phân tích dữ liệu, để tìm ra những tri thức chưa từng được biết đến trước đó. Người ta không xếp những câu truy vấn cơ sở dữ liệu vào các kỹ thuật Khai phá dữ liệu bởi vì chúng chỉ giúp ta lấy ra những dữ liệu đã được xác định, tiền xử lý sắp xếp từ trước trong một không gian lưu trữ rộng lớn như các cơ sở dữ liệu mà thôi. Điều này cũng có nghĩa là, một bộ máy tìm kiếm (Search Engine) nếu chỉ thực hiện chức năng tìm kiếm đơn thuần trên các cơ sở dữ liệu phẳng thì không thực sự là một ứng dụng Khai phá dữ liệu như chúng ta vẫn từng nghĩ từ trước đến nay. Các ứng dụng Khai phá dữ liệu hiện tại đã tiến xa trong các môi trường thương mại cũng là vì khả năng dự đoán được các xu hướng tương lai của một thông tin cần quan tâm - khía cạnh nổi bật của tri thức. Oracle, IBM, Yahoo, Microsoft đã tích hợp những nghiên cứu Khai phá dữ liệu hết sức nghiêm túc và thành công của mình vào các họ sản phẩm, các nền tảng (Platform) dành cho các doanh nghiệp cỡ lớn cũng như các ứng dụng phổ biến cho cá nhân người dùng. Các kỹ thuật của Khai phá dữ liệu cũng được áp dụng rộng rãi trong Data warehousing - quá trình lưu trữ và quản lý tập trung các cơ sở dữ liệu khác nhau bằng các công cụ quản lý tiên tiến trong việc lưu trữ, truyền tải, phân tích và khai thác dữ liệu với dung lượng lưu trữ cực lớn và tốc độ xử lý cực mạnh. 1.2. Khai phá văn bản Trong cơ sở dữ liệu, phần lớn dữ liệu ở dạng văn bản. Lĩnh vực con của Khai phá dữ liệu áp dụng với dữ liệu văn bản phi cấu trúc được gọi là Khai phá văn bản (Text Mining). Các kỹ thuật chính của Khai phá văn bản là Nhận dạng mẫu, Trích rút đặc trưng, Thống kê tần suất từ khóa, Phân loại…, các phương pháp Trí tuệ Nhân tạo như Học máy, Mạng Nơ-ron, Giải thuật Di truyền…, các phương pháp Xử lý ngôn ngữ tự nhiên… Khai phá văn bản do làm việc với các dữ liệu phi cấu trúc nên cần phải có phương tiện để mô hình hóa chúng, tiền xử lý cho các bước tiếp theo. Nói chung Khai phá văn bản gồm các bước: Thu thập dữ liệu ở dạng văn bản, làm sạch chúng, phân tích biến đổi, lấy thông tin và hiển thị thông tin. Mô hình chung của Khai phá văn bản : Hình 1.1: Mô hình khai phá văn bản chung Công việc thu thập và công việc làm sạch dữ liệu văn bản có thể diễn ra theo thứ tự thu thập trước, làm sạch sau và cũng có thể ngược lại tùy yêu cầu. Thậm chí, việc thu thập và làm sạch còn được lặp đi lặp lại nhiều lần để có được một kết quả tối ưu cho các bước tiếp. Do vậy quá trình thu thập – làm sạch là quá trình chung và hết sức quan trọng của các bài toán thuộc lĩnh vực Khai phá văn bản. Ngoài việc thu thập và làm sạch dữ liệu văn bản thì việc tìm kiếm đối sánh văn bản cũng là một công việc cốt lõi, không thể thiếu trong tất cả các bài toán Khai phá văn bản. Trong đó các văn bản được thu thập thường có sự liên quan hay tương tự với nhau. Độ liên quan hay tương tự thường được định lượng thông qua sự giống nhau về từ ngữ, về nghĩa hoặc theo một tiêu chí nào đó. Các bài toán điển hình của lĩnh vực Khai phá văn bản bao gồm : Phân lớp văn bản, Phân loại văn bản, Đánh chỉ mục - Tìm kiếm và Tóm tắt văn bản. Các bài toán này chúng ta sẽ đi sâu hơn ở phần sau. 1.3. Biểu diễn văn bản Như chúng ta đã nói ở phần trước, văn bản thông thường là dạng dữ liệu phi cấu trúc, do vậy muốn xử lý chúng, trước hết phải biểu diễn chúng thành những dạng có cấu trúc. Bên cạnh đó, việc xác định mối liên quan và thực hiện các phép biến đổi, ánh xạ văn bản cũng đòi hỏi những dạng này phải có khả năng thao tác bằng những phép toán cơ bản như các phép cộng, nhân, đại số quan hệ…và các phép toán phức tạp khác. Trên thực tế, có ba mô hình thường được sử dụng để biểu diễn văn bản, tất nhiên các mô hình này đều thỏa mãn những yêu cầu kể trên. Đó là Mô hình boolean, Mô hình không gian vector và Mô hình tập thô dung sai. 1.3.1. Mô hình boolean Trong mô hình boolean, văn bản, vốn là tập hợp của các term ( thuật ngữ ), được biểu diễn bởi chỉ số từng term và trọng số của chúng. Trọng số của từng term - dùng để đánh giá độ quan trọng của chúng - trong mô hình này chỉ mang hai giá trị 0 và 1, tùy theo sự xuất hiện của term đó trong văn bản. Trong khi đó, câu truy vấn bao gồm các văn bản tìm kiếm liên hệ với nhau thông qua các phép đại số quan hệ cơ bản như NOT (phủ định), AND (và) hay OR (hoặc). Thông qua mô hình Dạng chuẩn phân biệt (Disjunctive Normal Form), câu truy vấn có thể biểu diễn thành dạng vector với các thành phần liên kết và các phép toán quan hệ cơ bản như trên [1,6]. Từ đây, độ liên quan giữa một văn bản và truy vấn được xác định thông qua các thành phần liên kết. Độ liên quan này chỉ có thể mang hai giá trị : 0 – văn bản không phù hợp với truy vấn và 1 – văn bản phù hợp. Do vậy có thể thấy rằng hạn chế lớn nhất của mô hình này đó là việc đánh giá độ liên quan chỉ trả về hai kết quả, hoặc phù hợp hoặc không, như vậy yêu cầu của hệ thống khi cần sắp xếp và chọn lựa các văn bản theo mức độ liên quan đến truy vấn sẽ không đạt. Độ liên quan của mô hình này không thể phân chia thành các mức khác nhau, do vậy không phản ánh được thực tế là việc liên quan giữa văn bản và truy vấn có thể là mờ, không chắn chắn. Hạn chế này được gỡ bỏ khi ta sử dụng một mô hình tổng quát hơn – Mô hình không gian vector (Vector Space Model). 1.3.2. Mô hình không gian vector a. Mô hình không gian vector chuẩn Như trên đã đề cập, mô hình không gian vector là mô hình tổng quát hơn mô hình Boolean. Các văn bản được biểu diễn thành các vector nhiều chiều, với trọng số không chỉ mang hai giá trị là 0 hay 1 mà có thể mang các giá trị khác tùy theo cách đánh giá, tính toán. Một khác biệt nữa so với mô hình boolean là các phép toán cơ bản của mô hình không gian vector. Các phép toán đại số quan hệ dĩ nhiên không phù hợp nữa, thay vào đó là các phép toán vector như cộng hai vector, nhân hai vector, tích vô hướng… Khi biểu diễn văn bản thành các vector, vấn đề về truy vấn và xác định độ liên quan hoàn toàn được giải quyết. Truy vấn là kết quả của các phép toán vector giữa các vector biểu diễn cho những văn bản cấu thành nên truy vấn, như vậy, truy vấn trong trường hợp này cũng là một văn bản đặc biệt. Việc xác định độ liên quan giữa truy vấn và văn bản được quy thành độ liên quan giữa văn bản và văn bản. Hai văn bản là hai vector, vậy khoảng cách hay góc giữa chúng đều có thể đại diện cho sự liên quan giữa hai văn bản này. Tất nhiên, để áp dụng được các phép toán vector cơ bản, hai vector cần chuẩn hóa về số chiều (độ dài). Biểu diễn hai văn bản lần lượt là hai vector : x(w1,x,w2,x,….,wn,x) và y (w1,y,w 2,y,…,wn,y). Góc giữa hai vector này có thể xác địng thông qua công thức Cosine như sau : cosine(x,y) = Theo cách biểu diễn như trên người ta không quan tâm đến chỉ số của một term, vì vốn nó đã được sắp thứ tự ngay trong vector biểu diễn văn bản. Nghĩa là với vector x(w1,x,w2,x,….,wn,x) kể trên, w1,x chính là trọng số của term có chỉ số là 1, w2.x là trọng số của term có chỉ số là 2,…Việc đánh chỉ số cho term thường dựa vào một danh sách thuật ngữ. Do vậy ta sẽ quan tâm đến việc trọng số của term được xác định ra sao. Trọng số của term, ngoài cách gán giá trị là 0 hay 1 tùy vào sự xuất hiện của term như mô hình boolean, người ta còn có thể gán các giá trị tần suất cho chúng. Việc gán các giá trị tần suất cho trọng số của term cũng là một điều hợp lý vì người ta có thể đánh giá độ quan trọng của một term thông qua tấn suất xuất hiện của term đó trong văn bản. Giá trị này có thể đơn giản chỉ là số lần xuất hiện cuả term đó, tần suất của term đó ( số lần xuất hiện chia cho tổng số lần xuất hiện của tất cả các term ) hay một giá trị nào khác tối ưu hơn. Thông thường, số lần xuất hiện của một term thường được dùng như trọng số của term trong vector văn bản chứa nó. Số lần xuất hiện này thường được biểu diễn thông qua các hàm logarithm cơ số tự nhiên hoặc cơ số mười. Đây chính là kỹ thuật đánh trọng số TF (Term Frequency). b. Kỹ thuật TFxIDF Khi nói đến sự liên quan, người ta thường dùng một kỹ thuật, được coi là tin cậy và phản ánh chính xác độ liên quan. Đó là kỹ thuật TFxIDF. TFxIDF, viết tắt của Term Frequency times Inverse Document Frequency, dựa trên một nhận xét thực tế là : trong một tập các văn bản, khi xét riêng một văn bản thì một term càng quan trọng nếu nó xuất hiện nhiều trong văn bản đó và xuất hiện ít trong các văn bản còn lại. Rõ ràng nếu có được những điều kiện kể trên, thì term đó sẽ là một trong những đặc trưng của văn bản, và độ quan trọng của nó càng lớn. Gọi ft,d là số lần xuất hiện của term t trong văn bản d. Tần suất của term t trong văn bản d có thể được đánh giá qua các công thức sau Gọi N là tổng số các văn bản đang xét, ni là số văn bản mà trong đó term t xuất hiện. ta có ni/N là tấn suất xuất hiện của t trong tất cả các văn bản. Nghịch đảo của giá trị này, sau khi được chuẩn hóa, nhân với TF ta có : Như vậy giá trị TFxIDF có thể đại diện cho sự quan trọng, mối liên quan của term t với một tập hợp các văn bản cho trước. Quay lại với mô hình không gian vector, chúng ta hoàn toàn có thể dùng giá trị TFxIDF gán cho trọng số của term. Tất nhiên khi làm như vậy thì vector biểu diễn của một văn bản không những phụ thuộc vào từ điển và bản thân văn bản đó mà nó còn phụ thuộc vào những văn bản còn lại trong hệ thống đang xét. Việc tính độ liên quan hoàn toàn có thể thực hiện theo các công thức tính khoảng cách Euclidean hay Cosine như đã nêu ở trên, tuy nhiên với một tập các văn bản ổn định, không đổi của hệ thống thì chúng ta có thể tối ưu việc xác định độ liên quan của một văn bản và các văn bản khác. Một trong những kỹ thuật tối ưu như sau : giả sử ta muốn xác định độ liên quan của một văn bản d và một văn bản Di trong tập các văn bản của hệ thống, ta sẽ tính trước độ liên quan TFxIDF của tất cả các term có trong từ điển với Di, lưu trữ ở đâu đó. Sau này, ta xem các term nào có mặt trong d, tính độ liên quan của term đó với Di bằng cách nhân số lần xuất hiện của nó trong d với các giá trị TFxIDF đã tính sẵn, sau đó cộng tất cả kết quả này lại ta sẽ có được độ liên quan của văn bản d và Di. Tất nhiên, cách này sẽ làm giảm thời gian tính toán khi xử lý nhưng đổi lại, chúng ta sẽ phải mất chi phí về tài nguyên và thời gian khi lưu trữ các giá trị TFxIDF của tất cả các term trong từ điển với tất cả các văn bản trong tập văn bản D. Kỹ thuật này được gọi là kỹ thuật ngoại tuyến - offline. Khi thời gian xử lý cần phải nhanh, kỹ thuật ngoại tuyến được sử dụng. Chúng ta sử dụng nhiều tài nguyên để lưu trữ trước một lượng lớn dữ liệu đã tính toán trước, sau đó khi xử lý chỉ cần thực hiện một khối lượng nhỏ hơn rất nhiều, để đảm bảo mặt hiệu suất thực thi của ứng dụng. Kỹ thuật ngoại tuyến còn được sử dụng rất rộng rãi trong các bài toán khác của lĩnh vực Khai phá văn bản nói chung và Khai phá dữ liệu nói riêng. Kỹ thuật TFxIDF không những dùng để biểu diễn văn bản theo mô hình vector mà còn ứng dụng vào rất nhiều các giai đoạn khác trong những bài toán Khai phá văn bản. Kỹ thuật này ra đời đã lâu nhưng hiện vẫn đang được dùng phổ biến bởi sự phản ánh chính xác và tin cậy của độ đặc trưng, độ riêng biệt, độ quan trọng của các thành phần dữ liệu. Người ta cũng đã đưa ra một số các công thức khác thuộc dạng TFxIDF và đều mang lại những kết quả tốt. c. Mô hình vector thưa và các mô hình không gian vector khác Khi đề cập đến chỉ số của một term trong vector biểu diễn văn bản, chúng ta đã nói rằng chúng đã được xác định đối với một từ điển cho trước. Tuy nhiên, theo mô hình không gian vector chuẩn thì việc lưu trữ một vector như vậy sẽ rất lãng phí tài nguyên. Một vector chuẩn sẽ có số chiều là số term có trong từ điển. Với một từ điển trung bình thì số term là khoảng bảy mươi ngàn. Trong khi đó một văn bản với độ dài trung bình có số term ít hơn rất nhiều. Các term không xuất hiện trong văn bản sẽ có trọng số là 0 và như vậy vector biểu diễn văn bản sẽ gồm rất nhiều giá trị 0, gấp nhiều lần các giá trị khác 0. Điều này có thể khắc phục bằng mô hình vector thưa. Một vector biểu diễn văn bản gồm các cặp chỉ số - trọng số của các term xuất hiện trong văn bản đó (tất nhiên trọng số trong trường hợp này luôn khác 0). Như vậy tuy ta tốn thêm tài nguyên lưu trữ chỉ số của term nhưng chỉ phải lưu trữ số lượng term ít hơn rất nhiều. Biểu diễn là vậy, nhưng ta hoàn toàn có thể chuyển đổi giữa mô hình vector thưa và mô hình không gian vector chuẩn một cách nhanh chóng. Việc tính toán độ tương tự vẫn không đổi. Bản chất của mô hình này thật đơn giản : Mỗi cặp i - di đại diện cho một vector chuẩn có trọng số của term thứ i là di và tất cả các trọng số thành phần còn lại là 0. Vector biểu diễn văn bản là tổng của các vector trên. Như vậy, thay vì biểu diễn vector văn bản dạng chuẩn, chúng ta còn có thể biểu diễn chúng thành tuyến tính các vector thành phần. Các vector này có thể là các vector đơn vị, các vectơ trực giao, trực chuẩn. Mỗi cách chọn các vector thành phần đưa lại cho chúng ta các mô hình không gian vector tiên tiến hơn nhằm phục vụ tốt hơn những mục đích hay những kết quả cho các bước xử lý văn bản tiếp sau. Một trong những cách biểu diễn tuyến tính vector thành phần đó là kỹ thuật Đánh chỉ mục khái niệm (Concept Indexing). Thay vì đơn vị văn bản là các term, đơn vị theo kỹ thuật này là khái niệm. Mỗi khái niệm cũng là một vector. Vector biểu diễn văn bản là tuyến tính của các vector này. Kỹ thuật Đánh chỉ mục khái niệm không dừng lại ở việc mô tả văn bản mà thật sự nó là một kỹ thuật mới được nghiên cứu và đưa vào áp dụng gần đây nhằm xây dựng các giải thuật tiên tiến cho các bài toán như Phân lớp văn bản, Phân loại văn bản v.v... 1.3.3. Các mô hình biểu diễn văn bản khác a. Mô hình Xác suất Mô hình xác suất biểu diễn và sắp xếp văn bản thu được theo thứ tự giảm dần của xác suất độ liên quan giữa truy vấn và các văn bản đối tượng [3]. Mô hình xác suất thường được dùng trong bài toán Tìm kiếm văn bản truyền thống cũng như bài toán Thu thập thông tin ( Information Retrieval - IR ). b. Mô hình Mạng Bayes Mô hình mạng Bayes là sự kết hợp phần nào của mô hình xác suất và lý thuyết đồ thị. Mạng Bayes được mô tả bởi một đồ thị có hướng, trong đó các nút là các biến ngẫu nhiên, các cung là quan hệ nhân quả giữa các biến này. Trên cung có ghi các xác suất có điều kiện [3,6]. Mô hình mạng Bayes thường được dùng cho các phương pháp học Bayes dựa theo lý thuyết phân loại Bayes ( Naive Bayes Classify ). c. Mô hình tập thô dung sai Mô hình tập thô du._.ng sai (Tolerance Rough Set Model) là một mô hình mới, tiên tiến dựa trên lý thuyết về logic mờ và tập mờ (Fuzzy Set). Điều cốt lõi của lý thuyết này là việc xác định chính xác một giả thiết nào đó (ví dụ như hai văn bản này có phù hợp, có giống nhau không...) là một điều rất khó. Tuy nhiên chúng ta có thể chỉ ra một cặp xấp xỉ trên và xấp xỉ dưới để khẳng định được giả thiết đó là đúng. Sử dụng các suy diễn hợp lý để xác định và "làm đẹp" các ngưỡng này. Lý thuyết Logic mờ đã và đang được ứng dụng rất mạnh mẽ trong lĩnh vực Trí tuệ nhân tạo [3]. Mô hình tập thô gần đây được sử dụng nhiều cho các bài toán tìm kiếm cũng như phân nhóm văn bản.. Lý thuyết tập thô được các nhà nghiên cứu Trí tuệ nhân tạo phát triển và ngày càng thể hiện được tính ưu việt không chỉ trong việc biểu diễn và thao tác văn bản mà còn trong các vấn đề khác của lĩnh vực này. 1.4. Các bài toán Khai phá văn bản điển hình 1.4.1. Bài toán Phân lớp văn bản Bài toán phân lớp văn bản (Text Categorization) là một bài toán hay, có nhiều ứng dụng trong thực tế. Đầu vào của bài toán là tập các văn bản đã được phân lớp sẵn, cho một văn bản mới, ứng dụng phải chỉ ra văn bản đó thuộc lớp nào trong các lớp có sẵn ban đầu. Thuật toán thường được dùng là Cây quyết định (Decision Tree), K - Láng giềng gần nhất (K - Nearest Neighbor), các thuật toán hồi quy (Regression-based Algorithms)... Văn bản đầu vào sau khi được biểu diễn theo một mô hình nào đó, được theo dõi đối sánh với các văn bản đã phân lớp : có liên quan tới văn bản hoặc các văn bản nào nhất thì sẽ thuộc lớp tương ứng. Người ta gọi đây là phương pháp học có giám sát. (Supervised Learning Approach) [5,14]. Hình 1.2: Mô tả các bài toán phân lớp văn bản 1.4.2. Bài toán Phân nhóm văn bản Bài toán Phân nhóm văn bản (Text Clustering) có điểm khác so với bài toán Phân lớp văn bản ở chỗ cho một tập văn bản chưa được phân loại gì cả, yêu cầu bài toán này là phân tập văn bản này thành các nhóm dựa trên độ tương đồng giữa chúng. Đây là phương pháp học không có giám sát (Unsupervised Learning Approach). Các thuật toán hay được dùng để giải quyết bài toán này là : Các thuật toán Phân chia, thuật toán Phân cấp, Mô hình SVM (Support Vector Machine) và các thuật toán xây dựng tập thuật ngữ thường xuyên (Frequent Term Set). Hình 1.3: Mô tả bài toán Phân nhóm văn bản 1.4.3. Bài toán Đánh chỉ mục - Tìm kiếm Một tên gọi khác phổ biến hơn của bài toán này là Thu thập thông tin (Information Retrieval). Nói chính xác hơn bài toán Thu thập thông tin là bài toán cơ bản của Khai phá dữ liệu, và là bài toán tổng quát hơn của bài toán Đánh chỉ mục - Tìm kiếm (Indexing - Searching). Yêu cầu bài toán là tìm kiếm trong kho dữ liệu những văn bản phù hợp với câu truy vấn đưa vào. Bước đánh chỉ mục thường giúp tìm kiếm nhanh hơn. Bài toán này là cơ sở cho các Search Engine - những bộ máy tìm kiếm và trả về thông tin - một trong những công cụ hũu ích nhất trên Internet giúp chúng ta có thể tìm được thông tin cần thiết chỉ thông qua một câu truy vấn đơn giản. Hiện nay các ứng dụng tìm kiếm kiểu này thường áp dụng các phương pháp truy hồi để tăng khả năng chính xác cho dữ liệu tìm được. Bài toán này còn là đầu vào cho một số các bài toán khác [2,3,6]. 1.4.4. Bài toán Tóm tắt văn bản Quá trình tóm tắt là quá trình rút ra những thông tin quan trọng nhất từ một hay nhiều nguồn văn bản để tạo ra một văn bản gọn hơn phục vụ cho một số nhiệm vụ hay người dùng cụ thể. Bài toán tóm tắt văn bản (Text Summarization) là một trong những bài toán khó cài đặt nhất nhưng cũng hữu ích nhất của lĩnh vực Khai phá văn bản. Một số biến thể của bài toán này như sinh phụ đề tự động (Subtitling), sinh ý chính tài liệu (Document Gisting), sinh tiêu đề văn bản (Header Generating)... Những thuật toán của bài toán này cũng được dùng trong các bài toán tương tự như tóm tắt hình ảnh, âm thanh - những dữ liệu đa phương tiện. 1.5. Kết chương Trong chương này em đã đề cập đến những khái niệm cơ bản về Khai phá dữ liệu, Khai phá văn bản, các mô hình biểu diễn văn bản và các bài toán điển hình của Khai phá văn bản. Các chương sau em sẽ đi sâu vào việc trình bày những hiểu biết bài toán Tóm tắt văn bản, đặc biệt là xem xét khả năng phát triển trong môi trường tiếng Việt và qua đó cài đặt một ứng dụng tóm tắt văn bản tiếng Việt dựa trên những tìm hiểu và nghiên cứu về Xử lý tiếng Việt. Chương 2. XỬ LÝ NGÔN NGỮ TỰ NHIÊN Trong chương này em xin trình bày về lĩnh vực Xử lý ngôn ngữ tự nhiên Tổng quan về Xử lý ngôn ngữ tự nhiên Các vấn đề cơ bản của Xử lý ngôn ngữ tự nhiên Đặc trưng ngôn ngữ tiếng Việt và ảnh hưởng của nó tới quá trình xử lý văn bản tiếng Việt tự động 2.1. Tổng quan về Xử lý ngôn ngữ tự nhiên. Xử lý ngôn ngữ tự nhiên như chúng ta đã đề cập, là lĩnh vực thuộc ngành Khoa học máy tính, và đã xuất hiện từ rất lâu. Với việc sử dụng các phương pháp Trí tuệ nhân tạo, Xử lý ngôn ngữ tự nhiên cũng thường được coi là ngành nghiên cứu hẹp hơn của lĩnh vực này. Ngôn ngữ tự nhiên (Natural Language) là thuật ngữ dùng để chỉ các ngôn ngữ giao tiếp giữa con người với nhau như tiếng Việt, tiếng Anh, tiếng Nhật…, để phân biệt với ngôn ngữ nhân tạo (Artificial Language) hay còn gọi là ngôn ngữ lập trình (Programming Language) để cjỏ các ngôn ngữ con nguời giao tiếp với máy tính như Pascal, C/C++, Java… Lĩnh vực Xử lý ngôn ngữ tự nhiên ra đời đã lâu, trải qua nhiều nghiên cứu và ứng dụng, ngày nay được hiểu như là lĩnh vực giúp máy tính xử lý các vấn đề về ngôn ngữ tự nhiên, không ngoài mục đích là để giúp cho giao tiếp giữa người và máy thuận tiện và thân thiện hơn. Xử lý ngôn ngữ tự nhiên có rất nhiều hướng ứng dụng và mỗi hướng ứng dụng đó lại là một ngành nghiên cứu hết sức thú vị. Khi nói đến Xử lý ngôn ngữ tự nhiên thì chúng ta phải nói đến cơ sở ngôn ngữ tự nhiên. Đó là những vấn đề cơ bản của ngôn ngữ mà lĩnh vực Xử lý ngôn ngữ tự nhiên bám sát và nghiên cứu làm sao cho máy tính phân tích và hiểu ngôn ngữ tự nhiên giống như con người hiểu hoặc chí ít cũng là gần như cách con người hiểu. Các vấn đề cơ bản của ngôn ngữ tự nhiên bao gồm : Phonology & Phonetics (Âm vị và Ngữ âm) Morphology (Hình thái học) Grammar (Ngữ pháp) Stôiantic (Ngữ nghĩa) Pragmatics (Ngữ dụng) Âm vị và ngữ âm học là các ngành nghiên cứu của Ngôn ngữ học, chuyên nghiên cứu về đơn vị phát âm, cách phát âm và các biến thái của chúng. Hướng ứng dụng tương ứng của chúng thuộc Xử lý ngôn ngữ tự nhiên là ngành Xử lý - Nhận dạng tiếng nói. Hình thái học là ngành nghiên cứu về hình thái của từ, nghĩa là tùy thuộc vào thời, thể, cách mà các từ có sự biến đổi hay kết hợp khác nhau. Các thành tựu của hình thái học được các nhà khoa học về Máy tính sử dụng trong các nghiên cứu mà họ lấy từ hay chữ là đơn vị để xử lý như Nhận dạng chữ viết, Kiểm tra và sửa chính tả… Grammar là ngành nghiên cứu về ngữ pháp, bao gồm từ pháp và cú pháp. Từ pháp đề cập đến các đặc tính từ loại (Part Of Speech), giống, số của từ. Một số nhà ngôn ngữ cũng xếp Hình thái học vào vấn đề Từ pháp học. Cú pháp (Syntactic) đề cập đến sự liên kết giữa các từ, các ngữ trong câu. Ngữ pháp và ngữ nghĩa là hai vấn đề mà Xử lý ngôn ngữ tự nhiên quan tâm nhất và cũng đạt được nhiều kết quả nghiên cứu nhất cho đến hiện tại. Syntactic đề cập đến vấn đề ngữ nghĩa : một từ, ngữ hay câu được “hiểu” như thế nào, hàm chứa ý gì, quan hệ về nghĩa giữa các từ với nhau thế nào... Đối với tiếng Anh đã có nhiều nghiên cứu về ngữ nghĩa và thậm chí nhiều mạng ngữ nghĩa - mô tả quan hệ về nghĩa giữa các từ theo nhiều khía cạnh - đã được xây dựng. Nổi tiếng nhất có lẽ là WordNet [9,18,24]. Mạng ngữ nghĩa này là một kho tri thức khổng lồ được cung cấp miễn phí cho việc nghiên cứu. Hiện tại nhiều mạng Wordnet cho các thứ tiếng khác ngoài tiếng Anh cũng đã được xây dựng, tuy nhiên mạng Wordnet Việt nam hiện tại vẫn chưa được chính thức nghiên cứu và xây dựng. Pragmatic - Ngữ dụng học - là ngành nghiên cứu việc dùng các từ, các ngữ trong các lĩnh vực khác nhau. Các thống kê về việc tần suất sử dụng của các từ trong các lĩnh vực khác nhau là những thông số quan trọng cần thiết cho những phương pháp thống kê của Xử lý ngôn ngữ tự nhiên. Trên các mức này, máy tính cần phải hiểu được ngôn ngữ ở mức cao hơn. Đó là mức ngữ đoạn (Discourse) và mức tri thức (World Knowledge). Mức ngữ đoạn là các quan hệ về mặt ngữ pháp và ngữ nghĩa, thậm chí ngữ dụng của các đoạn văn bản. Đã có nhiều nghiên cứu về vấn đề này, nổi tiếng nhất là Lý thuyết cấu trúc tu từ (Rhetorical Structure Theory - RST). RST biểu thị các quan hệ ngữ pháp và ngữ nghĩa giữa các câu với nhau, giữa các đoạn với nhau thông qua các quan hệ được định nghĩa sẵn. Lý thuyết này thường được áp dụng trong việc phân tích ngữ đoạn cũng như sinh văn bản tự động. Mức tri thức là mức rộng nhất, máy phải hiểu được tất cả các vấn đề của một tiếng, một từ, một ngữ, một câu, một khái niệm, một thông tin, một tri thức... Tất nhiên chưa có một nghiên cứu nào đạt được mức này tuy nhiên cũng đã có một số nghiên cứu đặt ra tham vọng sẽ mô hình hóa về tất cả mọi đặc tính của ngôn ngữ cho một đơn vị nào đó, có thể là từ, câu, đoạn... Ngôn ngữ tự nhiên là một vấn đề phức tạp ngay cả với con người, vì vậy, đối với máy tính việc xử lý ngôn ngữ tự nhiên là một công việc hết sức khó khăn. Chúng ta phải đối mặt với các bài toán kinh điển của Khoa học máy tính và Trí tuệ nhân tạo - các bài toán đòi hỏi chi phí tính toán cực lớn. Chính vì điều này, Xử lý ngôn ngữ tự nhiên trước đây phát triển chậm và có xu hướng áp dụng các thuật toán dựa luật và suy diễn. Tuy nhiên vào những thập kỷ gần đây, sự phát triển nhanh chóng của phần cứng máy tính kéo theo sự ra đời của các máy tính nhỏ gọn, giá thành rẻ mà lại có hiệu suất tính toán cao đã mở ra những triển vọng sáng sủa cho lĩnh vực Trí tuệ nhân tạo nói chung và Xử lý ngôn ngữ tự nhiên nói riêng. Các thuật toán thống kê cũng đang từng ngày được áp dụng nhiều hơn và cho những kết quả khả quan. Các thành tựu của Xử lý ngôn ngữ tự nhiên không chỉ áp dụng trong nghiên cứu mà đã được dùng để xây dựng các ứng dụng mang tính thương mại và đạt được nhiều thành công trên thị trường. 2.2. Các vấn đề cơ bản của Xử lý ngôn ngữ tự nhiên Như chúng ta đã đề cập, ngữ pháp và ngữ nghĩa là các vấn đề được quan tâm nhất và có ứng dụng nhiều nhất trong các bài toán điển hình của lĩnh vực Xử lý ngôn ngữ tự nhiên như Tóm tắt, Dịch máy, Trả lời tự động… Sau đây là các bài toán cơ bản thuộc về ngữ pháp và ngữ nghĩa mà các nhà Xử lý ngôn ngữ tự nhiên thường phải giải quyết. 2.2.1. Phân tách thuật ngữ - Phân tách đoạn và câu Phân tách thuật ngữ (Word Segmentation) là công việc tách một chuỗi văn bản ra thành các term (tạm dịch : thuật ngữ) xem các term nào có trong từ điển, term nào không có trong từ điển (các tên riêng, ký hiệu, chữ viết tắt…). Công việc này làm tiền đề cho việc mô hình hóa văn bản. Chúng ta phải thực hiện việc này trước thì mới có thể vector hóa một văn bản, đối sánh hay xác định độ liên quan… Đối với các ngôn ngữ Latin giống như tiếng Anh và tiếng Pháp thì vấn đề này không phức tạp bằng các ngôn ngữ khác như tiếng Việt, tiếng Trung Quốc hay tiếng Nhật… do các từ của tiếng Anh hay tiếng Pháp được tách nhau bởi một hay nhiều dấu cách còn trong tiếng Việt, Trung Quốc, Nhật… thì giữa các dấu cách không phải là từ mà là tiếng (chữ) - một đơn vị nhỏ hơn từ. Ví dụ: Xét câu tiếng Anh sau : We announced that we have captured him. Dựa vào dấu cách chúng ta có thể phân tách được các từ dễ dàng : We | announced | that | we | have | captured | him. Tuy nhiên ta xem câu tiếng Việt tương ứng : Chúng em xin thông báo rằng chúng em đã bắt được hắn ta. Rõ ràng chúng ta không thể dùng dấu cách để phân tách từ cho câu này. Kết quả phân tách thuật ngữ đúng phải là như sau : Chúng em | xin | thông báo | rằng | chúng em | đã | bắt được | hắn ta. Để giải quyết vấn đề này các nhà Xử lý ngôn ngữ tự nhiên của Việt Nam, Trung Quốc, Nhật Bản… thường sử dụng một số phương pháp như : Đối sánh thuật ngữ dài nhất (Maximum Length Matching), Đồ thị chuyển trạng thái (Transducing Graph), dựa cú pháp (Syntax-based Approach)… Mỗi phương pháp có ưu và nhược điểm riêng nhưng phương pháp nào cũng sử dụng một từ điển hoặc danh sách từ vựng. Do vậy sự chính xác của từ điển hay danh sách từ vựng là yếu tố quan trọng ảnh hưởng đến sự chính xác của bộ phân tách thuật ngữ. Ngoài ra vì có những nhập nhằng trong ngôn ngữ nên bài toán này cũng như các bài toán khác của Xử lý ngôn ngữ tự nhiên chưa được giải quyết một cách trọn vẹn. Hiện tại các bộ phân tách thuật ngữ thường đạt được kết quả từ 85% đến 98% các từ phân tách chính xác [15]. Bộ đoán nhận danh từ riêng, chữ viết tắt cũng có thể coi là một phần của bộ phân tách thuật ngữ và được áp dụng rộng rãi. Nhiều bài toán coi đây là một công việc cơ bản vì danh từ riêng, chữ viết tắt… có tần suất xuất hiện khá cao trong văn bản và chúng cũng hàm chứa mức độ quan trọng lớn. Ngoài ra việc đoán nhận danh từ riêng, chữ viết tắt còn là một phần của việc hợp giải tham chiếu (Coreference Resolution) - được dùng nhiều trong các ứng dụng tóm tắt và sinh ngôn ngữ tự nhiên (Natural Language Generating). Xét về phạm vi lớn hơn thì chúng ta phải đối mặt với một vấn đề khác, đó là Phân tách đoạn-câu (Sentence Segmentation) là công việc phân tách một văn bản thành những đoạn và câu nhằm tạo tiền đề cho việc phân tích cú pháp sau này của văn bản đó. Bài toán này không phân biệt ngôn ngữ vì hầu hết các ngôn ngữ thường phân tách câu dựa trên những dấu hiệu là các dấu ngắt câu như dấu chấm, chấm hỏi, chấm than... Tuy vậy, nếu văn bản đưa vào không chuẩn thì kết quả cũng không thể đạt 100%. Ví dụ như lỗi sau các dấu chấm câu không viết hoa sẽ dẫn đến việc hiểu nhầm thành dấu ba chấm. Ngoài ra, một số phần trăm sai sót khác còn do hiện tượng những dấu chấm câu được dùng như là ký hiệu thực hiện chức năng khác khác gây ra. Ví dụ như dấu chấm được dùng để phân tách phần nguyên và phần thập phân của một con số. Nói chung phân tách đoạn-câu có khả năng đạt được độ chính xác cao hơn và cũng dễ dàng cài đặt hơn phân tách từ nhưng phạm vi áp dụng của chúng thì không rộng bằng. 2.2.2. Gán nhãn từ loại Gán nhãn từ loại là công việc gán cho mỗi từ trong câu, hay đoạn thông tin về từ loại (Part of speech) của chúng. Ví dụ : xét câu tiếng Việt sau : Học sinh học sinh học Câu này nếu gán nhãn từ loại đúng sẽ là : [Học sinh]N[học]V [sinh học]N Tuy nhiên làm sao để máy có thể hiểu và gán đúng nhãn từ loại là một vấn đề. Sự nhập nhằng trong ngôn ngữ cản trở việc máy đoán nhận đúng. Ngoài ra việc phân tách thuật ngữ cũng ảnh hưởng tới việc gán nhãn vì các danh sách thuật ngữ của một câu là đầu vào cho một bộ gán nhãn từ loại. Với ví dụ trên có khá nhiều bộ gán nhãn từ loại gán sai dẫn tới kết luận sai về cú pháp. Các phương pháp thường dùng để cài đặt bộ gán nhãn từ loại bao gồm : Mô hình Markov ẩn - Giải thuật Viterbi, Dựa luật cú pháp (rule-based), Dựa bộ nhớ (Memory-based), Độ hỗn loạn lớn nhất (Maximum Entropy)… Trong đó các phương pháp áp dụng mô hình Markov ẩn (Hidden Markov Model - HMM) được sử dụng nhiều nhất. Các phương pháp như Bigram, Trigram hay CFG (Context Free Grammar) đều thuộc loại này. Hiện nay một bộ gán nhãn từ loại (POS Tagger) chính xác nhất đạt được 98% từ gán nhãn đúng [15]. 2.2.3. Phân tích cú pháp Phân tích cú pháp là bài toán tổng quát của gán nhãn từ loại. Ngoài việc gán từ loại cho từng từ, bộ phân tích cú pháp (Syntax Analyzer, Parser) phải nhận biết được các ngữ và gán kiểu cho các ngữ làm sao để có được một câu hoàn chỉnh về mặt ngữ pháp. Nếu không câu đó là câu không hoàn chỉnh. Xét về ngôn ngữ học, đó sẽ không phải là câu. Kết quả việc gán từ, ngữ này thường được biểu diễn thành cây, gọi là cây cú pháp (Syntax Tree). Với ví dụ trên ta có : Hình 2.1: Phân tích cú pháp Các bộ phân tích cú pháp thường được cài đặt bởi các thuật toán dựa trên luật hay ngữ liệu (corpus-based). Việc kiểm tra xem một câu có phải là câu hoàn chỉnh hay không thường dựa vào việc duyệt cây và cấu trúc chính của một ngôn ngữ. Ở tiếng Anh, cấu trúc chính tạo nên câu hoàn chỉnh về mặt ngữ pháp là cấu chúc S + V + (O) : Chủ ngữ + Động từ + (Tân ngữ). Tuy nhiên trong tiếng Việt cấu trúc “nòng cốt” tạo bởi quan hệ “đề - thuyết” (hay quan hệ “chủ - vị”) là cấu trúc của một câu hoàn chỉnh về mặt ngữ pháp [7]. Việc phân tích cú pháp là một công việc cơ bản của các bài toán Xử lý ngôn ngữ tự nhiên, tuy vậy do tính chất phức tạp của ngôn ngữ và các đặc thù riêng của quá trình máy học, các bộ phân tích cú pháp chưa đạt được độ chính xác cao như mong đợi. 2.2.4. Phân tích ngữ nghĩa Như chúng ta đã đề cập ở trên, phân tích ngữ nghĩa tức là giúp cho máy có thể “hiểu” được một từ, một câu, một đoạn... hàm chứa ý nghĩa gì hay mối quan hệ về nghĩa giữa chúng... Các phương pháp dùng để phân tích ngữ nghĩa hay được dùng đó là các phương pháp dựa trên tri thức hay dựa trên ngữ liệu. Dựa trên tri thức (Knowledge-based) là phương pháp dựa trên các kho tri thức ngữ nghĩa có sẵn (như WordNet) để phân tích ngữ nghĩa. Dựa trên ngữ liệu (Corpus-based) là phương pháp dựa trên những thống kê các kho ngữ liệu để đưa ra được ngữ nghĩa của đối tượng đang xét. Các phương pháp này nói chung đòi hỏi phải có kho tri thức hoặc kho ngữ liệu lớn, càng lớn càng chính xác nhưng đối với tiếng Việt thì đây là hạn chế lớn do chúng ta không có được các nguồn tài nguyên này. Một cách khắc phục là xây dựng các kho ngữ liệu song ngữ (Parallel Corpora) và từ các nghiên cứu tương ứng của một ngôn ngữ mà dẫn ra một số kết quả thích hợp cho ngôn ngữ còn lại. 2.3. Các đặc trưng ngôn ngữ của tiếng Việt Do trong đồ án này, việc tìm hiểu các đặc trưng ngôn ngữ tiếng Việt có mục đích là để áp dụng các phương pháp Xử lý ngôn ngữ tự nhiên vào quá trình Tóm tắt văn bản tiếng Việt nên chỉ có các đặc trưng về từ pháp - hình thái từ và đặc trưng về ngữ pháp được đề cập đến. Đặc trưng về ngữ âm và âm vị được đề cập đến một phần với vấn đề chuẩn hóa thanh điệu và i-y. Các đặc điểm về ngữ nghĩa tiếng Việt không có nhiều khác biệt so với các ngôn ngữ khác cũng sẽ không được đề cập. 2.3.1 Đặc trưng về ngữ âm và âm vị Mỗi âm tiết tiếng Việt gồm ba phần : phần đầu, phần sau và thanh điệu. Phần đầu của âm tiết được xác định là Âm đầu, vì ở vị trí này chỉ có một âm vị tham gia cấu tạo. Phần sau của âm tiết  được gọi là phần Vần. Phần Vần gồm các loại âm vị được gọi là Âm đệm, Âm chính và Âm cuối. Thanh điệu có sáu loại ngang, hỏi, huyền, sắc, ngã, nặng. Thanh điệu được đặt ở trên nguyên âm trong âm tiết. Tuy nhiên phần Vần có thể có nhiều nguyên âm do vậy việc bỏ dấu ở nguyên âm nào là vấn đề đã được đặt ra từ lâu trong các hội thảo về chuẩn hóa ngôn ngữ và công nghệ thông tin-truyền thông. Ngoài ra, do sự có mặt của dấu phụ - các dấu không phải là thanh điệu, đi kèm với một số nguyên âm để tạo ra các nguyên âm mới ( Ví dụ: “^” với â, ê, ô hay “’” với ơ, ư…) - nên vị trí đặt thanh điệu cũng phải hòa hợp với các dấu phụ này. Như vậy tại sao cần phải chuẩn hóa ? Rõ ràng khi viết chữ, chỉ cần viết đúng các dấu thanh điệu, vị trí đâu cần quan tâm, ai cũng hiểu được kia mà ! Thật ra không phải vậy, khi nền Công nghệ thông tin phát triển, việc bỏ dấu chính xác chính là một phần trong quá trình lưu trữ các âm tiết, chữ viết trong các tài liệu điện tử và tất nhiên đòi hỏi một sự chính xác tuyệt đối. Nói riêng trong các vấn đề của đồ án này, khi phân tách thuật ngữ, máy tính phải dựa vào từ điển. Nếu các thuật ngữ trong từ điển và thuật ngữ trong văn bản đầu vào không được lưu trữ theo cùng quy tắc thì việc đối sánh sẽ trả về kết quả không mong muốn. Ví dụ như khi máy tính tìm kiếm từ “hóa trị” trong từ điển tiếng Việt sẽ báo không có vì trong từ điển chỉ lưu trữ từ “hoá trị”. Vấn đề tương tự cũng xảy ra nếu không có sự chuẩn hóa i-y. Ví dụ như vật lý một từ dễ thấy trong các báo điện tử sẽ không có mặt trong từ điển tiếng Việt vì trong từ điển chỉ có từ “vật lí”. Các quy tắc chuẩn hóa về vị trí thanh điệu cũng như vấn đề i-y đã được một số nhà ngôn ngữ học đưa ra và nói chung đã được ngành ngôn ngữ học thống nhất. Nhưng trong các văn bản điện tử thì hiện tại chưa có được các chuẩn hóa này. Bản thân các bộ gõ tiếng Việt thường được dùng hiện nay như Vietkey hay Unikey cũng có các tùy chọn bỏ dấu. 2.3.2 Đặc trưng về từ pháp và hình thái Khi tìm hiểu các đặc trưng tiếng Việt ta cần chú ý tiếng Việt là một ngôn ngữ đơn lập - đơn âm tiết (monosyllable). Xét về mặt từ pháp, trong tiếng Việt, hình vị là từ. Bởi vì từ là đơn vị nhỏ nhất để đặt câu, từ có nghĩa hoàn chỉnh và cấu tạo ổn định [7]. Từ được cấu thành bởi một đơn vị nhỏ hơn, chúng ta thường quen gọi là “tiếng” ( hay “chữ” - xét về mặt chữ viết, “âm tiết” - xét về mặt ngữ âm). Dựa trên “tiếng” - đơn vị rất dễ nhận biết thông qua các dấu cách - chúng ta phân biệt được đâu là từ ghép, đâu là từ đơn. Từ đơn là từ chỉ có một tiếng, từ ghép là từ có hai tiếng trở lên. Đây chính là vấn đề của các ngôn ngữ như tiếng Việt : rất khó khăn khi thực hiện việc phân tách thuật ngữ. Cách tốt nhất là dựa trên từ điển để đối sánh và rút ra kết luận (Bên ngành ngôn ngữ học có một số phương pháp để xác định xem đó là một từ hay nhiều từ như khảo sát về hiện tượng tách, lặp, iếc hóa hay đối chiếu…[7], tuy nhiên các phương pháp này không thể áp dụng được đối với máy tính !). Xét về mặt hình thái, khác với phần lớn các ngôn ngữ hệ Latin, tiếng Việt thường không có hiện tượng biến cách hay dẫn xuất khi câu thay đổi về thời, thể, cách. Thay vào đó là việc sử dụng kết hợp với hư từ (từ công cụ) để phản ánh sự thay đổi này. Hư từ là các từ cấu tạo bởi các tiếng được dùng độc lập, chỉ có ý nghĩa về mặt ngữ pháp. Ví dụ như : đã, sẽ, bị, chưa… Các hư từ này kết hợp với các thực từ - là các từ mang ý nghĩa thật sự về nghĩa - sẽ thực hiện nhiệm vụ phản ánh việc thay đổi về thời, thể, cách [7,8]. Ví dụ: Em ăn cơm - Em đã ăn cơm - Em sẽ ăn cơm (hiện tại - quá khứ - tương lai). Ông ấy đánh - Ông ấy bị đánh (chủ động - bị động). Lại xét về mặt từ pháp, trong các ngôn ngữ khác, việc thay đổi giống và số cũng được thực hiện thông qua việc biến cách, tuy nhiên trong tiếng Việt chúng ta sử dụng các danh từ chỉ số luợng để làm việc này. Ví Dụ: Một con vịt cái - các con vịt đực - loài vịt (Giống). Một con vịt - Những con vịt - Mười con vịt - lũ vịt (Số). Điều này ảnh hưởng trực tiếp đến quá trình tiền xử lý văn bản cũng như đoán nhận ngữ nghĩa. Việc chuẩn hóa hình thái từ của các hệ tiếng Latin là cả một vấn đề trong khi đó tiếng Việt chúng ta không cần quan tâm đến. Ngược lại, khi xét đến ngữ nghĩa chúng ta phải thông qua các hư từ hay danh từ số lượng đi kèm để hiểu được nghĩa đầy đủ của một từ hay cụm từ. 2.3.3. Đặc trưng về ngữ pháp Xét về mặt ngữ pháp, tiếng Việt có khá nhiều khác biệt so với các ngôn ngữ khác, trong đó cần nói đến việc tạo câu dựa trên cấu trúc nòng cốt và trật tự từ [7,8]. Cấu trúc nòng cốt, dựa trên quan hệ “đề thuyết” của tiếng Việt đề cập đến một quy tắc chung nhất của tiếng Việt khi tạo câu, đó là một câu hoàn chỉnh về mặt ngữ pháp phải có phần đề và phần thuyết. Phần đề cấu thành bởi danh ngữ. Phần thuyết cấu thành bởi hoặc là động ngữ hoặc tính ngữ hoặc một đoản ngữ khác. Đây chính là sự khác biệt chính về ngữ pháp với một số ngôn ngữ khác, tiếng Anh chẳng hạn. Trong tiếng Anh, cấu trúc chính là S-V-(O). Một câu hoàn chỉnh của tiếng Anh cần phải có một động ngữ trong đó động từ đóng vai trò chính. Tiếng Việt thì không chắc vậy. Một câu hoàn chỉnh có thể không có động từ. Ví dụ, Xét câu tiếng Anh sau : This flower is beautiful. Câu tiếng Việt tương ứng : Bông hoa này đẹp. Hai câu này đều là các câu hoàn chỉnh về mặt ngữ pháp. Trong câu tiếng Anh chúng ta nhận ra động từ to be được chia với ngôi thứ ba số ít. Còn trong tiếng Việt phần thuyết chỉ là tính từ “đẹp” mà thôi. Một điều cần nói ở đây là chúng ta không nên so sánh và ép buộc các quy tắc ngữ pháp của một ngôn ngữ cho một ngôn ngữ khác do sự ra đời, lịch sử phát triển, hoàn cảnh xã hội và đặc trưng văn hóa của mỗi ngôn ngữ là khác nhau, đặc biệt khi chúng thuộc các hệ ngôn ngữ khác nhau. Đã có nhiều cá nhân cho rằng ngữ pháp tiếng Anh chặt chẽ hơn ngữ pháp tiếng Việt, cụ thể trong ví dụ trên thực ra câu tiếng Việt phải là Bông hoa này thì đẹp, và thì là một động từ tương ứng với to be. Như vậy tiếng Việt cũng có cấu trúc chính như tiếng Anh ! Kết luận này là gượng ép và vô căn cứ. Trên đây chúng ta đã đề cập đến vấn đề nòng cốt câu ảnh hưởng thế nào đến việc tạo câu, sau đây phần trật tự từ. Trật tự là một trong ba phương tiện được sử dụng trong tiếng Việt để cấu thành câu [7,8]. Do tiếng Việt có tính tịnh tiến, tính cảm đề và tính đề diễn nên khác biệt giữa tiếng Việt và các ngôn ngữ khác hệ về mặt trật tự là rất lớn. Điều này ảnh hưởng đến việc ánh xạ một-một các quy tắc ngữ pháp đã có của ngôn ngữ khác (phổ biến hơn, có nhiều thành tựu nghiên cứu hơn) với các quy tắc của tiếng Việt. Chỉ trong một phạm vi nào đó thì phép ánh xạ này mới tương ứng cả về trật tự cũng như chức năng của từ, ngữ. Trong trường hợp tiếng Anh - tiếng Việt, phạm vi này không lớn. Nói chung các ánh xạ này thường là nhiều nhiều và chúng ta cần có những phương tiện hay thông tin khác để xác định sự tương ứng duy nhất. Đây là tư tưởng chính của các phương pháp Xử lý ngôn ngữ tự nhiên dựa vào ngữ liệu song ngữ hoặc đa ngữ (parallel corpora) vốn đang được nghiên cứu và áp dụng cho các ngôn ngữ ít phổ biến hơn bằng cách sử dụng các thành quả nghiên cứu đối với tiếng Anh - ngôn ngữ phổ biến nhất. Việc xác định ánh xạ giữa các đơn vị ngôn ngữ (từ, ngữ, câu…) được gọi là việc căn ke đơn vị ngôn ngữ (Alignment). Ví dụ, thông qua việc dịch và gán nhãn bằng tay hai câu thuộc hai ngôn ngữ có ý nghĩa và cấu trúc tổng quan tương đương người ta có thể rút ra các luật chuyển đổi từ ngôn ngữ này sang ngôn ngữ kia và ngược lại. Minh họa cụ thể : Sau khi gán nhãn từ loại và phân tích cú pháp (do người thực hiện) tương ứng ngôn ngữ cho hai câu sau : Tiếng Việt : Chiếc xe máy màu đỏ là xe của em. Tiếng Anh : The red bike is my bike. Hình 2.2: Học luật chuyển đổi cú pháp Anh - Việt Từ đây ta rút ra các luật cú pháp chuyến đổi tương ứng của tiếng Việt và tiếng Anh để cho máy học. Sau này giả sử cần máy tính phân tích cú pháp một câu tiếng Việt tương tự câu trên (Chẳng hạn : Cái xe đạp màu xanh là cái xe của anh ấy), với câu tiếng anh tương ứng (The blue bicycle is his bicycle) kèm theo phân tích cú pháp của câu tiếng Anh này, máy sẽ dựa trên các vào chuyển đổi này để có thể đưa ra kết quả phân tích cú pháp của câu tiếng Việt. 2.4. Kết chương Xử lý ngôn ngữ tự nhiên là một lĩnh vực lý thú và có khả năng ứng dụng rộng rãi trong các ngành khoa học khác. Các vấn đề của Xử lý ngôn ngữ tự nhiên phụ thuộc vào các đặc trưng của từng ngôn ngữ. Vì vậy mong muốn phát triển các nghiên cứu và ứng dụng riêng về Xử lý tiếng Việt đã trở thành mong muốn chung của các nhà nghiên cứu trong Công nghệ thông tin, Ngôn ngữ, Văn hóa Việt Nam… Trong chương này em đã trình bày các tìm hiểu của mình về Lĩnh vực Xử lý ngôn ngữ tự nhiên cũng như các đặc trưng ngôn ngữ tiếng Việt cần thiết cho bài toán Tóm tắt văn bản tiếng Việt. Các vấn đề cơ bản của Xử lý ngôn ngữ tự nhiên trong tiếng Việt đã được nêu ra và sẽ được giải quyết phần nào trong các chương sắp tới. Sau đây là phần tìm hiểu sâu hơn về bài toán Tóm tắt văn bản : các khái niệm, tiêu chí phân loại, mô hình chung, các phương pháp xây dựng cũng như đánh giá kết quả một ứng dụng Tóm tắt văn bản. Chương 3. BÀI TOÁN TÓM TẮT VĂN BẢN Trong chương ba em xin trình bày vấn đề trọng tâm của đồ án, đó là bài toán Tóm tắt văn bản tự động. Chương này bao gồm các mục sau : Giới thiệu tổng quan về bài toán Tóm tắt văn bản bao gồm các khái niệm, phân loại bài toán… Mô hình bài toán Tóm tắt văn bản, các phương pháp thường sử dụng trong bài toàn này. Đánh giá một ứng dụng tóm tắt văn bản 3.1. Giới thiệu chung Ở Việt Nam hiện nay, hầu như tất cả các bài toán tiếng Việt điển hình của Khai phá văn bản đều đã được nghiên cứu và cài đặt thành ứng dụng như Tìm kiếm văn bản, Phân lớp & Phân loại văn bản..., đóng góp rất nhiều vào sự phát triển của lĩnh vực Xử lý văn bản tự động tiếng Việt. Tuy nhiên, bài toán Tóm tắt văn bản thì chưa có nhiều nghiên cứu tiến hành đề xuất và xây dựng thành công ứng dụng. Có lẽ bởi vì bài toán này không chỉ cần những công cụ và phương pháp của Khai phá văn bản mà còn phải lưu ý đến những vấn đề về Xử lý ngôn ngữ tự nhiên (Natural Language Processing). Điều này thật không tương xứng với nền thông tin tri thức hiện tại của Việt Nam, khi mà đang có hàng ngàn nhu cầu khác nhau cần đến những ứng dụng trợ giúp tóm lược văn bản hay sinh tiêu đề và hiển thị chúng theo những dạng mong muốn. Chính sự dễ dàng khi truy cập vào kho dữ liệu Internet khổng lồ và phong phú lại là nhược điểm cho việc tìm kiếm những thông tin mà chúng ta cần đến bởi chúng quá nhiều và không thống nhất về định dạng lưu trữ và hiển thị. Kể cả khi đã lấy được những thông tin đó thông qua các hệ thống phân loại, tìm kiếm thì cũng không thể nắm bắt toàn bộ vì thời gian thì có hạn mà số lượng thông tin trả về quá lớn. Đấy là chúng ta còn chưa kể đến việc những thông tin này liệu đã chính xác như mong muốn hay chưa, liệu chúng ta có nên bỏ thời gian để đọc chúng ? Một hệ thống Tóm tắt văn bản sẽ giúp chúng ta giải quyết phần lớn các nhu cầu vừa nêu. Hệ thống sẽ giúp chúng ta đọc nhanh hơn, nắm bắt những tri thức cần thiết trong một tài liệu khoa học hàng trăm bằng cách tóm lược tài liệu đó lại thành một đoạn văn bản dài vài ba chục trang. Một xếp các văn bản khác đưa vào chờ ta đọc và ta sẽ nắm bắt được những ý chính, cốt yếu của chúng. Những văn bản tìm thấy từ Internet, ta nhờ hệ thống quyết định liệu ta nên đọc văn bản nào để có thể tìm đúng thông tin ta cần. Những tóm lược ngắn gọn các công việc mà cô thư ký đưa, những bản giới thiệu nội dung phim truyện tuần tới, những bức email thương mại chỉ vài dòng... Đó là những khả năng mà một hệ thống Tóm tắt văn bản có thể mang lại. 3.1.1. Tóm tắt văn bản là gì ? Hệ thống Tóm tắt văn bản, như chúng ta đề cập tới trong đồ án này, có tên đầy đủ là Hệ thống Tóm tắt văn bản tự động [10,12]. Một hệ thống Tóm tắt văn bản tự động là một ứng dụng sinh tự động một mô t._.ánh giá TF (Term Frequency) : Một term xuất hiện trong văn bản nhiều hơn một ngưỡng nào đó thì được coi là term đạt tiêu chuẩn TF và danh sách các term TF trong văn bản được dùng để đánh giá các câu thông qua việc gán điểm TF tùy vào độ xuất hiện của term đó. Hiện tại VTAS để ngưỡng là.... Thông qua kết quả kiểm thử, phương pháp này cho kết quả khá cao, tuy nhiên thời gian xử lý lớn. Hình 4.6: Phương pháp tần suất xuất hiện f. Phương pháp TFxIPF (Term Frequency times Inverted Paragraph Frequency) Phương pháp này dựa trên cách đánh giá TFxIDF đã nêu trong chương 1, phần mô hình biểu diễn văn bản bằng mô hình không gian vector. Theo cách đánh giá này một thuật ngữ là quan trọng và đặc trưng khi nó xuất hiện nhiều trong văn bản này và ít xuất hiện trong các văn bản khác. Ở đây, một thuật ngữ được xét ở trong một đoạn và nó được tính điểm TFIPF theo công thức : Trong đó tf là số lần xuất hiện term i trong đoạn, N là tổng số đoạn trong văn bản, ni là số đoạn chứa term i Sau đó tất cả các thuật ngữ đều được tính điểm TFIPF, sắp xếp giảm dần theo điểm này. Một phần trăm nào đó của các thuật ngữ có số điểm TFIPF cao nhất sẽ được dùng để đánh giá các câu trong văn bản giống như cách của các phương pháp Title, Heading hay Tần suất xuất hiện : gán điểm TFIPF cho mỗi câu dựa trên sự có mặt của các thuật ngữ TFIPD trong câu. Trước khi áp dụng các phương pháp nêu trên của pha Phân tích, văn bản cần được loại bỏ từ dừng (Stopword) bởi vì các từ dừng này ảnh hưởng rất lớn đến độ chính xác của các tiêu chí gán điểm. Các từ dừng là các từ xuất hiện nhiều trong văn bản nhưng không mang nhiều ý nghĩa về mặt nội dung, thường là các hư từ, mạo từ như và, nên, vì thế, tuy nhiên… VTAS loại bỏ từ dừng thông qua một module rất đơn giản, kiểm tra trong các term của văn bản, đoạn văn, câu văn xem có các term trong danh sách từ dừng tiếng Việt không, nếu có thì loại bỏ. Danh sách từ dừng tiếng Việt được xây dựng bán tự động dựa trên việc thu thập các từ xuất hiện nhiều trong một lượng lớn các văn bản thuộc các lĩnh vực khác nhau. Rõ ràng với việc phân tán nội dung như vậy, các từ xuất hiện nhiều là các từ dừng. Sau đó danh sách từ dừng này còn được chuẩn hóa bằng tay. Việc loại từ dừng không thực hiện ở pha tiền xử lý vì rất nhiều từ dừng là những chứng cớ ngôn ngữ rất quan trọng cho các pha sau, đặc biệt là pha Hiển thị. Trong pha hiển thị, dựa vào một số các từ dừng, thường là từ nối, để sinh trở lại văn bản. Trong pha phân tích, em có cài đặt một số các phương pháp khác như Ngữ cố định, Vị trí tối ưu, Chuỗi từ vựng, tuy nhiên chưa tích hợp vào VTAS do chưa chứng minh được tính đúng đắn, do chi phí tính toán cho các thuật toán theo phương pháp đó lớn hoặc do chưa áp dụng được với kiểu tài liệu đầu vào và ngữ liệu tiếng Việt hiện tại. 4.3.2. Các phương pháp trong pha Biến đổi 4.3.2.1. Biến đổi nhờ vào rút gọn câu Như chúng ta đã đề cập, các phương pháp biến đổi nhờ vào rút gọn câu không tăng thêm độ chính xác của ứng dụng tóm tắt, chỉ làm tăng độ nén cũng như làm cho người đọc dễ hiểu và nắm bắt được vấn đề chính. Trong đồ án này em chọn phương pháp rút gọn câu dựa theo luật cú pháp. Các luật cú pháp rút gọn thông thường được thu về thông qua việc học, áp dụng vào một câu đã phân tích cú pháp để rút gọn cấu trúc câu đó. Nhưng hiện tại em chưa có một bộ phân tích cú pháp chính xác mà chỉ là một bộ phân tích nông (shallow parser) nên chỉ có một số luật cơ bản được áp dụng để rút gọn như xóa ngữ đồng vị, xóa bỏ chú thích, xóa trạng ngữ, giữ lại danh từ chính trong ngữ danh từ. Các thuật toán loại bỏ ngữ đồng vị, xóa chú thích, xóa trạng ngữ hay giữ lại danh từ được cài đặt trong đồ án này là các thuật toán khác nhau chứ không phải dựa trên các tập luật rút gọn thống nhất. Thông qua kiểm thử em nhận thấy bốn thuật toán này làm việc rất hiệu quả, áp dụng trên nhiều câu và có độ chính xác cao so với việc học từ các tập mẫu và đưa ra tập luật rút gọn thống nhất. i. Thuật toán loại bỏ ngữ đồng vị Ngữ đồng vị là các ngữ đóng cùng một vai trò với một thành phần nào đó của câu, thường là ngữ danh từ. Các ngữ đồng vị này không mang nhiều chức năng cú pháp, chỉ làm rõ nghĩa cho câu : Ví dụ: Bill Gate, chủ tịch tập đoàn Microsoft, là người giàu nhất thế giới. Ở đây, “chủ tịch tập đoàn Microsoft” là ngữ đồng vị, có thể bỏ đi, kết quả chấp nhận trong một chừng mực nào đó khi ta phải ưu tiên thực hiện yêu cầu về độ nén. Ngữ đồng vị là trường hợp xuất hiện khá nhiều trong các mẩu tin, thường được phân cách bởi một cặp dấu phảy, đây chính là dấu hiệu để phân tách ngữ đồng vị và thành phần cùng chức năng với chúng. Chúng ta có thể dễ dàng phân biệt ngữ đồng vị với tập liệt kê các cụm danh từ - vốn không thể loại bỏ - bằng việc xét chức năng từ loại của thành phần đi ngay sau dấu phảy cuối cùng Ví dụ: Một chiếc Toyota, hai chiếc Hyundai, hai chiếc Mercedez đã bị tạm giữ ngay trong ngày đầu tiên. Ví dụ trên đây là tập liệt kê cụm danh từ vì ngữ đầu tiên sau dấu phảy cuối “hai chiếc Mercedez” vốn là một ngữ danh từ, khác với ngữ đi sau dấu phảy trong trường hợp ngữ đồng vị sẽ là ngữ động từ. Như vậy ta kiểm tra xem ngữ đi ngay sau dấu phảy cuối cùng là ngữ động từ hay ngữ danh từ. Trong trường hợp là ngữ động từ thì ngữ nằm giữa hai dấu phảy cuối cùng là ngữ đồng vị và ta có thể loại bỏ. Tất nhiên trước khi thực hiện việc này chúng ta phải phân tách tập ngữ danh từ và ngữ động từ - nòng cốt của câu - bằng bộ phân tích cú pháp nông để giảm thiểu sai sót gây ra do các dấu phảy nằm ở ngữ động từ. ii. Loại bỏ chú thích Chú thích thực ra phần lớn là một loại ngữ đồng vị, nhưng được phát hiện dễ dàng hơn và thuật toán loại bỏ chúng cũng đơn giản hơn nhiều. Điều này kéo theo độ chính xác của phương pháp là rất cao so với các phương pháp rút gọn khác. Hiện tại, hệ thống chỉ coi những phần nào nằm trong dấu ngoặc đơn, nằm giữa hai dấu ngạch ngang (- như thế này -) là chú thích. Sau khi nhận biết, chúng ta lập tức xóa các chú thích đi. Thuật toán chỉ đơn giản kiểm tra một câu có cặp “()” hay “- -” thì xóa phần nằm giữa. iii. Loại bỏ trạng ngữ Trạng ngữ là các ngữ bổ nghĩa cho câu (chính xác hơn là bổ nghĩa cho động từ chính trong câu ) về mặt thời gian, nơi chốn, nguyên nhân, mục đích, cách thức Ví dụ: Nằm ở xã Kim Thuỷ, huyện Lệ Thuỷ, Quảng Bình, suối Bang còn nguyên nét hoang sơ kỳ bí với đường vào hẹp, quanh co và dốc. Từ ngày hôm nay, nhiều trường đại học trên địa bàn thành phố tiếp tục nhận hồ sơ thí sinh trúng tuyển nguyện vọng một và hai. Để tránh lộn xộn và quá tải, ĐH Kinh tế tiếp nhận hồ sơ sinh viên theo khu vực. Các trạng ngữ này được phát hiện bằng cách tương tự như ngữ đồng vị : Ngữ trước dấu phảy duy nhất của câu được lấy ra và kiểm tra xem có là một ngữ danh từ hay không, nếu không phải, và đồng thời ngữ sau dấu phảy là một ngữ danh từ thì chương trình coi đây là một trạng ngữ và chương trình sẽ loại bỏ trạng ngữ đó. Đây là trường hợp xuất hiện nhiều nhất trong các mẩu tin và cũng là một phương pháp có độ chính xác cũng như độ nén cao. iv. Giữ lại cụm danh từ chính trong ngữ danh từ : Đây là phương pháp rút gọn đơn giản nhưng chỉ mang lại kết quả có độ nén thấp và làm giảm độ chính xác của ứng dụng tóm tắt. Một ngữ danh từ thường gồm các thành phần như danh từ chỉ đơn vị, danh từ loại thể, danh từ chính , tính từ bổ nghĩa cho danh từ chính, trạng từ bổ nghĩa cho tính từ. Ví dụ: “Nokia 9960i là một chiếc điện thoại di động vô cùng sang trọng” Trong câu trên “[một] [chiếc] [điện thoại di động] [vô cùng] [sang trọng]” là một ngữ danh từ. Chúng ta có thể rút gọn ngữ danh từ này chỉ còn “[một] [chiếc] [điện thoại di động], bỏ hết tính từ bổ nghĩa cho danh từ chính, trạng từ bổ nghĩa cho tính từ. Câu sẽ trở thành : Nokia 9960i là một chiếc điện thoại di động. Như chúng ta thấy chỉ nên áp dụng phương pháp này trong trường hợp yêu cầu độ nén cao vì tính chính xác của hệ thống giảm đi khá nhiều. Tùy vào yêu cầu độ nén mà các thành phần trong ngữ danh từ có thể bỏ đi theo thứ tự là trạng từ bổ nghĩa tính từ, tính từ bổ nghĩa danh từ chính, danh từ đơn vị và danh từ loại thể. Như ví dụ trên, nếu yêu cầu độ nén không lớn ứng dụng chỉ cần loại bỏ trạng từ để có được câu sau : Nokia 9960i là một chiếc điện thoại di động sang trọng. Các thành phần từ loại trong ngữ danh từ được gán trọng số “loại bỏ”. Trọng số càng lớn thì mức độ ưu tiên loại bỏ càng lớn. Một số trường hợp tương tự như trạng từ bổ nghĩa động từ, mệnh đề quan hệ cũng sử dụng chung mô hình này nếu có được trọng số “loại bỏ” chính xác. Đặc biệt thông qua quá trình học máy chúng ta có thể rút ra các luật rút gọn và gán các trọng số tương ứng. Ứng dụng hiện tại chưa cài đặt mô hình học tự động từ tập ngữ liệu. Trong các phương pháp rút gọn theo cú pháp ở trên, VTAS sử dụng ba phương pháp đầu do độ chính xác của toàn ứng dụng không bị ảnh hưởng, kết quả rút gọn cũng đạt yêu cầu. Phương pháp cuối cùng khi chưa có bộ phân tích cú pháp cũng như một mô hình học máy thích hợp thì chưa được đưa vào áp dụng để rút gọn câu. 4.3.2.2. Giản lược câu về mặt ngữ nghĩa Thông qua việc kiểm thử, em thấy rằng các phương pháp giản lược câu về mặt ngữ nghĩa không nên áp dụng cho việc rút gọn các mẩu tin bởi vì hiện tượng các khái niệm cùng cấp ý niệm như lê, táo, đào... cùng có chung một kiểu từ loại xuất hiện trong các mẩu tin là rất ít. Và quan trọng hơn, nếu không có mạng ngữ nghĩa chi tiết thì độ chính xác tóm tắt sẽ giảm đi rất nhiều. Sau đây là một câu tin chuyên mục sức khỏe nói về tác dụng của cây chua me đất: Để chữa viêm họng chúng ta dùng chua me đất, bồ công anh, cam thảo sắc uống ngày một thang mỗi thứ 20g, chia làm hai đến ba lần. Sau khi dựa vào mạng ngữ nghĩa về y học, chúng ta tìm được khái niệm “dược thảo” là khái niệm ở cấp ngay trên các khái niệm về “chua me đất”, “bồ công anh”, “cam thảo” và thay thế chúng, ta sẽ được câu mới quả thật có ngắn gọn hơn : Để chữa viêm họng chúng ta dùng dược thảo sắc uống ngày một thang mỗi thứ 20g, chia làm hai đến ba lần. Tuy nhiên chúng ta có thể dễ dàng nhận thấy câu này chả còn ý nghĩa ban đầu của nó ! Người đọc không biết dược thảo ở đây là loại nào, nó quá chung chung. Như vậy chúng ta thấy rằng không nên áp dụng các phương pháp rút gọn câu dựa vào ngữ nghĩa đối với các mẩu tin vì phạm vi ứng dụng rất nhỏ, độ chính xác giảm nhiều đồng thời công sức xây dựng mạng ngữ nghĩa là rất lớn. 4.3.3. Các phương pháp trong pha Hiển thị Pha hiển thị của VTAS được cài đặt đơn giản : Sắp xếp lại các câu đã được chọn và được rút gọn theo thứ tự ban đầu trong văn bản đưa vào. Sau đó các câu này được đưa qua một module hợp giải tham chiếu đơn giản và hiển thị kết quả cuối cùng Việc sắp xếp câu theo thứ tự ban đầu là việc đơn giản bởi các câu của văn bản đầu vào sau khi được VTAS mô hình hóa đã trở thành các đối tượng clsSentence tương ứng, trong đó có các thuộc tính như thứ tự câu trong đoạn (tương đối) và thứ tự câu trên toàn văn bản (tuyệt đối). Chính nhờ thuộc tính thứ tự câu tuyệt đối này, chúng ta có thể sắp xếp và nối chúng lại với nhau theo thứ tự ban đầu. Minh rất thông minh. Cậu ấy thường đạt kết quả cao trong học tập. Ngoài ra cậu ấy còn có khả năng văn nghệ nữa Module hợp giải tham chiếu của VTAS thực hiện hai công việc : loại bỏ tham chiếu tự do và loại bỏ tham chiếu thường. Loại bỏ tham chiếu tự do được thực hiện đơn giản như sau : Các ngữ đầu tiên của câu được tách ra (dựa vào dấu phảy), nếu các ngữ này không là ngữ danh từ, ngữ động từ, ngữ tính từ hoặc không là một mệnh đề, đồng thời chứa các term có trong một danh sách các tham chiếu tự do như “đó”, “như vậy”, “như trên” …thì sẽ bị loại bỏ. Loại bỏ tham chiếu thường là một phần quan trọng, cải thiện tính dễ đọc, dễ hiểu và tính tự nhiên của kết quả trả về. Thuật toán loại bỏ tham chiếu thường dựa trên việc phát hiện các NamedEntity và các tham chiếu ngay từ pha Phân tích. Ở pha phân tích, các chuỗi đồng tham chiếu sẽ được xây dựng với đầu mỗi chuỗi là một named entity, các phần tử đi sau là các đại từ trong câu, cuối cùng là đại từ trước một named entity khác. Các câu chứa các đồng tham chiếu này được thay các đại từ bởi named entity đầu chuỗi đồng tham chiếu. Các named entity ứng viên chọn làm đầu chuỗi đồng tham chiếu là các named entity ở đầu câu trong trường hợp có nhiều named entity trong cùng một câu. 4.4. Kết chương Trong chương này em đã đề cập đến những giải thuật cài đặt phần lý thuyết được nói đến trong các chương đầu tiên. Trong số đó có một số giải thuật đơn giản nhưng cũng có nhiều giải thuật khó, đòi hỏi phải cải tiến thì mới đáp ứng được yêu cầu về tính chính xác, về thời gian thực thi và về hiệu quả ứng dụng. Chương kế tiếp em xin giới thiệu giao diện của chương trình và phần kết quả kiểm thử - phần không thể thiếu đối với bất kỳ ứng dụng nào cài đặt các phương pháp Khai phá văn bản và Xử lý ngôn ngữ tự nhiên. Chương 5. KIỂM THỬ VÀ ĐÁNH GIÁ ỨNG DỤNG Trong chương này em xin trình bày những phần sau : Kết quả thử nghiệm của VTAS Giao diện chính và giao diện kiểm thử của chương trình. Đánh giá truyền thống dựa trên độ chính xác và độ hồi tưởng Đánh giá dựa theo độ phù hợp về nội dung 5.1. Giao diện kết quả thực nghiệm VTAS được em xây dựng trên môi trường .NET bằng ngôn ngữ C#. Đây là ngôn ngữ có khả năng xử lý các cơ sở dữ liệu phẳng một cách nhanh chóng, ngoài ra các đối tượng cấu trúc dữ liệu có sẵn của C# như DictionaryBase, HashTable, ArrayList… có cơ chể quản lý tìm kiếm và truy xuất phần tử tối ưu, linh hoạt, rất thích hợp cho các bài toán Khai phá văn bản. Cơ sở dữ liệu của chương trình là cơ sở dữ liệu phẳng, chỉ gồm các file *.txt. Điều này cho phép dễ dàng truy nhập và sửa đổi thêm bớt dữ liệu. Sau đây là giao diện chính của VTAS. Hình 5.1: Giao diện chính Với mục đích phục vụ nghiên cứu, khi cài đặt ứng dụng em đã cài đặt các chức năng kiểm thử đơn vị, tập hợp thành một form riêng. Sau đây là hình ảnh của form này: Hình 5.2: Giao diện kiểm thử Các kết quả trung gian như mô hình hoá văn bản, tách đoạn, phân tách thuật ngữ của một văn bản được theo dõi trực quan và dễ dàng thống kê, kiểm thử. Kết quả của pha Phân tích và Biến đổi cũng được hiển thị thông qua form này. Hình 5.3: Giao diện phân tách đoạn và câu Hình 5.4: Giao diện phân tách thuật ngữ của đoạn Hình 5.5: Kết quả thực thi phương pháp TFxIDF 5.2. Tập kiểm thử Việc kiểm thử hệ thống được tách thành việc kiểm thử các module thành phần, bao gồm các module sau : tách term tiếng việt, tách named entity, chọn câu quan trọng và sát với ý chính văn bản, rút gọn câu. Trong đó module chọn câu quan trọng (Kết quả của pha Phân tích) là quan trọng nhất vì nó quyết định độ chính xác của toàn ứng dụng. Ứng dụng được kiểm thử dựa trên tập dữ liệu là các tin thuộc nhiều thể loại của báo điện tử VnExpress ( Thông số của tập kiểm thử : 500 văn bản thuộc 8 thể loại : Du lịch : 86 văn bản, kích thước trung bình 4 KB. Giáo dục : 65 văn bản, kích thước trung bình 4 KB. Kinh doanh : 65 văn bản, kích thước trung bình 4 KB. Ô tô - Xe máy : 48 văn bản, kích thước trung bình 4,7 KB. Pháp luật : 70 văn bản, kích thước trung bình 3,5 KB. Sức khoẻ : 76 văn bản, kích thước trung bình 5 KB. Thể thao : 40 văn bản, kích thước trung bình 7.5 KB. Vi tính : 50 văn bản, kích thước trung bình 4.3 KB. Thông số danh sách thuật ngữ Số thuật ngữ có trong danh sách : 70350 từ Độ dài của thuật ngữ dài nhất : 39 ký tự Thông số danh sách từ dừng Số từ dừng có trong danh sách : 1053 từ. Độ dài của từ dừng dài nhất : 24 kí tự. Với tập kiểm thử như trên, em đã lấy ngẫu nhiên một số lượng văn bản nào đó phục vụ cho các lần kiểm thử khác nhau. Kết quả kiểm thử được trình bày trong phần sau. Các lý thuyết đánh giá kiểm thử một ứng dụng Tóm tắt đã được em nêu ở chương 3, phần Đánh giá tóm tắt. 5.3. Kết quả kiểm thử và đánh giá 5.3.1. Kiểm thử thuật toán tách term tiếng Việt - Lấy 6 văn bản bất kỳ thuộc 6 thể loại khác nhau từ tập kiểm thử, lần lượt cho đi qua bộ phân tách thuật ngữ với cùng danh sách thuật ngữ được nêu ở trên, kết quả phân tách như sau : STT Tên văn bản Lớp Số lỗi sai khi tách chuỗi từ trái qua Số lỗi sai khi tách chuỗi từ phải qua 1 Ấn tượng Hoàng Sơn Du lịch 1 1 2 Chính phủ lập Ban chỉ đạo đánh giá chất lượng giáo dục Giáo dục 2 1 3 Cổ phiếu Bảo Minh đắt giá Kinh doanh 0 1 4 Khen thưởng 2 cảnh sát giao thông không nhận hối lộ Pháp luật 1 0 5 Lysine - vi chất quan trọng nhưng dễ bị thiếu hụt Sức khoẻ 3 1 6 Khai mạc diễn đàn CNTT Việt Nam 2004 Vi tính 0 0 Đánh giá : Qua đây ta thấy khi áp dụng thuật toán tách thuật ngữ theo độ dài từ dài nhất từ trái qua không hiệu quả bằng từ phải qua, trong khi độ phức tạp tính toán của hai thuật toán là như nhau. 5.3.2. Kiểm thử thuật toán tách named Entity - Lấy 6 văn bản bất kỳ thuộc 6 thể loại khác nhau từ tập kiểm thử, lần lượt cho đi qua bộ phát hiện Named Entity, kết quả phân tách như sau : STT Tên văn bản Lớp Số NE tách đúng/tổng số NE Kết quả phần trăm 1 Thăm biển Cù Mông Du lịch 16/16 100% 2 Các môn thi và ngày thi tốt nghiệp THCS, THPT chính thức Giáo dục 8/8 100% 3 Vụ kiện tôm đe doạ tới xuất khẩu của Mỹ Kinh doanh 25/27 92.6% 4 TP HCM: Án các loại tăn Pháp luật 11/12 91.7% 5 Viêm não cấp xuất hiện ở nhiều địa phương Sức khoẻ 14/14 100% 6 Bill Gates bênh vực nỗ lực vá lỗi của Microsoft Vi tính 29/33 87.9% Đánh giá : Bộ phát hiện named entity thường cho kết quả cao khi phân tách các văn bản có nội dung thuần tiếng Việt. Độ chính xác của nó giảm đi khi phải đoán nhận các văn bản có các tên riêng nhiều tiếng của nước ngoài. Tuy vậy, kết quả vẫn đạt cao 5.3.3. Kiểm thử, đánh giá module chọn câu quan trọng Đây là phần kiểm thử quan trọng nhất. Từ tập kiểm thử em chọn ra 10 văn bản bất kỳ. Các phương pháp đánh giá được áp dụng với các mức độ nén lần lượt là 10%, 20%, 30%, 40%,50%. Mức độ nén này được tính xấp xỉ theo tỉ lệ số câu. Các phương pháp tóm tắt hoặc ứng dụng trích rút được dùng : Baseline : Mỗi văn bản tóm tắt được tạo bởi việc nối theo đúng thứ tự tự nhiên các câu đầu mỗi đoạn trong văn bản. Tất cả các câu đầu mỗi đoạn đều được chọn nên phương pháp Baseline chỉ áp dụng ở một độ nén cố định. Human : Đây là tập tóm tắt dựng nên bởi các bạn sinh viên và chuyên gia ngôn ngữ. Đầu tiên họ chọn ra một số lượng các câu quan trọng, sát với ý chính của cả văn bản. Sau khi chọn, họ sắp xếp xem câu nào là câu quan trọng nhất, câu nào là câu quan trọng thứ hai, cứ thế cho đến hết số câu vừa chọn. Tiêu chí lựa chọn là do họ tự xây dựng. MSSum : Đây là tập tóm tắt dựng nên bởi công cụ Auto Summarize của Microsoft Word 2002. Auto Summarize là một ứng dụng trích rút và sinh tiêu đề dựa trên các phương pháp thống kê, không bị ảnh hưởng quá nhiều vào ngôn ngữ và thể loại của văn bản. VTAS : Kết quả trả về từ module trích rút của VTAS với các độ nén khác nhau và tổ hợp tuyến tính các “chiến lược” tóm tắt khác nhau. Với các tập kết quả trên, em đánh giá ứng dụng dựa trên các phương pháp đánh giá như sau 5.3.3.1. Phương pháp truyền thống Sử dụng các tiêu chí độ chính xác và độ hồi tưởng, chúng ta đánh giá từng phương pháp Baseline, MSSum va VTAS với kết quả Human do người thực hiện. Vì chúng ta chọn độ nén về câu như nhau cho mỗi lần đánh giá nên dễ dàng thấy F = P = R, do đó chúng ta chỉ ghi lại điểm F mà thôi. Điểm F của mỗi phương pháp là trung bình cộng điểm F trên một văn bản. Kết quả kiểm thử trên phương pháp truyền thống thu được như sau : Độ rút gọn 10% 20% 30% 40% 50% Baseline 0.783 0.302 0.219 - - MSSum 0.921 0.605 0.595 0.650 0.627 VTAS 0.863 0.543 0.754 0.698 0.601 Đánh giá : Qua kết quả như trên, ta thấy đối với tiếng Việt, VTAS tóm tắt rất tốt, hơn trả MS Summary của Microsoft Word 2002 một chút. Điều này có lẽ là do VTAS sử dụng các tài nguyên tiếng Việt, cách tiếp cận cũng là tiếng Việt. Phương pháp lấy câu đầu đoạn có độ chính xác kém nhất. Khi ta tăng từ 10% à 50% độ rút gọn thì độ chính xác bị ảnh hưởng lớn nhất ở phương pháp Baseline, hai phương pháp kia không bị ảnh hưởng lắm (không thấy rõ xu hướng tăng hay giảm). Việc này cũng có thể giải thích được. Khi độ rút gọn tăng, xu hướng liên kết giữa các câu đầu đoạn sẽ yếu hơn. 5.3.3.2. Phương pháp đánh giá theo độ tương tự nội dung Ở đây, chúng ta sử dụng công thức Cosine cho M vì VTAS đã mô hình hoá các văn bản ở dạng vector. S là văn bản do VTAS sinh ra. Tập đánh giá là J=Human. Như vậy công thức xác định độ tương tự nội dung sẽ là : , Trong đó m là số văn bản của tập đánh giá J Kết quả thực nghiệm đối với 10 văn bản như sau : Độ rút gọn 10% 20% 30% 40% 50% 1 1 0.12 0.16 0.12 0.11 2 1 0.12 0.10 0.08 0.07 3 0.30 0.13 0.10 0.08 0.07 4 1 0.11 0.12 0.08 0.09 5 0.13 0.10 0.13 0.06 0.09 6 1 0.12 0.14 0.07 0.07 7 1 0.12 0.14 0.07 0.06 8 1 0.10 0.12 0.10 0.08 9 0.15 0.11 0.14 0.07 0.06 10 1 0.11 0.12 0.07 0.08 Đánh giá : Với độ rút gọn rất nhỏ, VTAS cho kết quả cao bởi vì VTAS ưu tiên các câu Title - chỉ cần có Title thì Title sẽ được đưa vào bản tóm tắt, cũng giống như cách con người tóm tắt. Với độ rút gọn cao hơn, mức độ gần gũi về mặt nội dung của bản kết quả VTAS và bản kết quả do người thực hiện giảm đi. Qua đây, em thấy cần phải có thêm những cách đánh giá khác nữa về mặt nội dung Em không dùng các phương pháp đánh giá bên ngoài cho VTAS vì đây là ứng dụng tóm tắt đơn văn bản chung chung, không tìm kiếm theo truy vấn. 5.3.4. Kiểm thử đánh giá rút gọn câu Đối với VTAS, các phương pháp rút gọn câu không làm ảnh hưởng tới độ chính xác của toàn bộ ứng dụng, do vậy mười câu bất kỳ lấy ra từ tập kiểm thử được rút gọn và tính toán độ nén theo độ dài câu. Kết quả như sau STT Câu Số kí tự 1 Giám đốc của WHO tại khu vực Tây Thái Binh Dương, ông Shigeru Omi, đang kêu gọi các nước xem xét lại tiêu chuẩn an toàn sinh học sau đợt phát dịch SARS mới đây tại Trung Quốc 174 Giám đốc của WHO tại khu vực Tây Thái Binh Dương kêu gọi các nước xem xét lại tiêu chuẩn an toàn sinh học sau đợt phát dịch SARS mới đây tại Trung Quốc 151 2 Hấp dẫn bởi ánh sáng, mực tập trung dưới ánh đèn măng-sông 58 Mực tập trung dưới ánh đèn măng-sông 36 3 Hai phần mềm dự thi (Quản lý học sinh học nghề của Thận và Quản lý thư viện của Dương) đã đưa về hai giải khuyến khích cá nhân 126 Hai phần mềm dự thi đã đưa về hai giải khuyến khích cá nhân 59 4 Với mục đích nâng cao tinh thần trách nhiệm của giáo viên đối với học sinh, Bộ khuyến khích các thày cô giáo tự ra đề cho học sinh lớp mình dạy để có sự đánh giá chính xác nhất 176 Bộ khuyến khích các thày cô giáo tự ra đề cho học sinh lớp mình để có sự đánh giá chính xác nhất 96 5 Tại quyết định ra ngày 5/7, Đoàn Luật sư kết luận đơn tố cáo của bị can Nguyễn Minh Phong về hành vi chạy án của ông Chiến (được thuê bảo vệ quyền lợi cho Phong trong vụ án đánh bạc) không có căn cứ vững chắc 208 Đoàn Luật sư kết luận đơn tố cáo của bị can Nguyễn Minh Phong về hành vi chạy án của ông Chiến không có căn cứ vững chắc 120 6 Cảnh sát hình sự Công an thành phố Đà Lạt vừa bắt quả tang Ngô Việt Trung (nguyên thủ môn đội bóng đá Lâm Đồng) đang ghi độ bóng đá cho hai người chơi tại nhà 158 Cảnh sát hình sự Công an thành phố Đà Lạt vừa bắt quả tang Ngô Việt Trung đang ghi độ bóng đá cho hai người chơi tại nhà 120 7 Trưởng khoa Khám bệnh, bác sĩ Nguyễn Thanh Giảng, cho biết ca mổ này rất phức tạp vì bệnh nhân mới mười hai tuổi, nặng 19 kg do chậm phát triển 143 Trưởng khoa Khám bệnh cho biết ca mổ này rất phức tạp vì bệnh nhân mới mười hai tuổi, nặng 19 kg do chậm phát triển 115 8 Ngoài ra, nguồn cho thận cũng rất khó khăn (thường người nhà bệnh nhân sẽ có độ tương thích lớn hơn) 100 Ngoài ra, nguồn cho thận cũng rất khó khăn 42 9 Eric Benhamou, Chủ tịch kiêm Giám đốc điều hành Palm, nhận định sự hợp nhất này góp phần thúc đẩy thị trường máy tính cầm tay tăng trưởng 137 Eric Benhamou nhận định sự hợp nhất này góp phần thúc đẩy thị trường máy tính cầm tay tăng trưởng 97 10 Nằm giữa một bên là Thái Bình Dương và một bên là hồ Kitaura rộng lớn, Kashima có khí hậu ôn hòa và phong cảnh thiên nhiên tuyệt đẹp 132 Kashima có khí hậu ôn hòa và phong cảnh thiên nhiên tuyệt đẹp 61 Như vậy độ rút gọn câu trung bình là: Trong đó : len(Ti ) là chiều dài câu rút gọn thứ i len(Si ) là chiều dài câu được rút gọn thứ i, Đánh giá : Các phương pháp rút gọn câu ở trên có độ rút gọn khá nhỏ, độ chính xác hầu như không ảnh hưởng. Văn bản sau pha này giảm kích thước khoảng 40%, góp phần vào việc sinh một văn bản ngắn gọn nhưng vẫn hàm chứa những ý chính của câu quan trọng đã được chọn qua pha Phân tích. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Các bài toán xử lý văn bản tiếng Việt luôn là các bài toán khó nhưng hay và hữu ích, đang được quan tâm và nghiên cứu nhiều ở nước ta hiện nay. Trong đồ án này, em đã trình bày về những vấn đề cơ bản, những khó khăn thách thức, triển vọng phát triển cũng như phạm vi ứng dụng rộng rãi của bài toán Tóm tắt văn bản tiếng Việt. Đây là một trong số ít những bài toán có sự kết hợp của hai lĩnh vực Khai phá văn bản và Xử lý ngôn ngữ tự nhiên. Các kết quả đạt được của đồ án : - Hiểu được những vấn đề tổng quan của Khai phá Văn bản và Xử lý ngôn ngữ tự nhiên, từ đó làm tiền đề cho những nghiên cứu định hướng về bài toán Tóm tắt văn bản. - Nắm bắt và phân biệt được rõ những khái niệm, yêu cầu và mục đích chung của một bài toán tóm tắt văn bản. Tìm hiểu các phương pháp cũng như các hướng giải quyết của các nhà nghiên cứu đi trước về vấn đề này - Tìm hiểu những đặc trưng ngôn ngữ cơ bản của tiếng Việt, từ đó đề xuất những phương pháp riêng, phù hợp hơn đối với một ứng dụng Tóm lược văn bản tiếng Việt, xây dựng mô hình và cài đặt thành công ứng dụng. Hướng phát triển sắp tới của đề tài : - Cải tiến và phát triển các phương pháp tóm tắt theo hướng Xử lý ngôn ngữ tự nhiên nhằm tăng tính chính xác cũng như sự thân thiện của kết quả trả về. - Tích hợp ứng dụng với các ứng dụng khác để tạo ra các hệ thống thật sự hữu ích cho người dùng Việt Nam. - Tham gia vào quá trình xây dựng các tài nguyên ngôn ngữ phục vụ cho ngành công nghệ thông tin và truyền thông cũng như các ngành khác liên quan. Trong suốt quá trình làm đồ án, em đã được sự giúp đỡ, hỗ trợ và đông viên rất lớn từ các thầy cô và bạn bè. Tuy nhiên do những hạn chế về mặt kinh nghiệm và thời gian, đồ án chắc chắn còn tồn tại khiếm khuyết. Qua đây em cũng mong muốn nhận được những góp ý nhằm phát triển tốt hơn đề tài này trong tương lai. Một lần nữa em xin gửi lời cám ơn chân thành và sâu sắc tới TS. Huỳnh Quyết Thắng. Thầy là người định hướng cho em, cũng là người tận tình hướng dẫn, chỉ bảo, động viên em giúp em hoàn thành tốt đồ án. Em cũng xin gửi lời cảm ơn tới các thầy cô trong Bộ môn và trong Khoa, tới gia đình và bạn bè, những người đã tạo điều kiện và giúp đỡ em rất nhiều trong quá trình học tập tại trường cũng như việc hoàn thành tốt nghiệp. TÀI LIỆU THAM KHẢO [1]. Chu Hồng Trang, Bài toán phân nhóm văn bản áp dụng cho Tiếng Việt, Đồ án tốt nghiệp ĐHBKHN, 5/2004. [2]. Hoàng Minh Sơn, Xây dựng hệ thống tìm kiếm thông tin hỗ trợ tiếng Việt, Đồ án tốt nghiệp ĐHBKHN, 2004. [3]. Lê Thị Tú Kiên, Nghiên cứu về xử lý tự động văn bản tiếng Việt, Luận văn thạc sỹ ĐHBKHN, 2003. [4]. Huỳnh Quyết Thắng, Hoàng Minh Sơn, Thử nghiệm các giải thuật tách từ tiếng Việt và xây dựng cấu trúc dữ liệu trong bài toán tìm kiếm văn bản tiếng Việt, Tài liệu khoa học - ĐHBKHN. [5]. Nguyễn Hoàng Anh, Hà Thành Lê, Hoàng Vĩnh Sơn, Phân lớp văn bản, Báo cáo đồ án thực tập chuyên ngành ĐHBKHN, 2004. [6]. Phạm Thị Anh Lê, Tìm kiếm thông tin dựa vào mô hình thống kê các giải thuật và kiến trúc phần mềm, Luận văn thạc sỹ ĐHBKHN, 2002. [7]. Nguyễn Tài Cẩn, Ngữ pháp tiếng Việt (Tiếng - Từ ghép - Đoản Ngữ), NXB Đại học Quốc gia Hà Nội, 1998. [8]. Trung tâm Khoa học xã hội và Nhân văn Quốc gia, Ngữ pháp tiếng Việt, NXB Khoa học xã hội, 2000. [9]. Eduard Hovy & Daniel Marcu, Automated Text Summarization Tutorial, COLING/ACL ’98. [10]. Mani & Maybury, Automatic Summarization, ACL 2001. [11]. Partha Lal, Text Summarization, Doctor thesis, 07/2002. [12]. Udo Hahn, Automated Text Summarization- Methods, Systems, Evaluatio.. [13]. Inderjeet MANI, Summarization Evaluation: An Overview. [14]. Đinh Thị Phương Thu, Bài toán phân lớp văn bản tiếng Việt, Luận văn Thạc sĩ khoa CNTT, 11/2004 [15]. Nguyễn Thị Minh Huyền, Vũ Xuân Lương, Lê Hồng Phương, Sử dụng bộ gán nhãn từ loại xác suất QTAG cho văn bản tiếng Việt - Kỉ yếu hội thảo khoa học quốc gia lần thứ nhất về nghiên cứu, phát triển và ứng dụng công nghệ thông tin và truyền thông (ICT.rda 2003), Nhà xuất bản Khoa học và kĩ thuật, Hà nội, 2003. [16]. Lê Thanh Hương: Phân tích cú pháp tiếng Việt, Luận văn tốt nghiệp cao học ,1999. [17]. Luhn, H. P, The automatic creation of literature abstracts, IBM journal of Research and Development, 1958. [18]. R. Radev Et All, Evaluation challenges in large-scale document summarization, ACL ’03. [19]. Regina Barzilay, Lexical Chains for Summarization, M.Sc Thesis, 11/97. [20]. Jing, H., Sentence reduction for automatic text summarization, Proc. of the 6th Conference on Applied Natural Language Processing, 2000. [21]. Knight, K. and Marcu, D., Statistics-Based Summarization. Step One: Sentence Compression, Proc. of AAAI2000, 2000. [22]. Hồ Tú Bảo, Knowledge Discovery and Data Mining, Viện CNTT - Viện khoa học và công nghệ tiên tiến Nhật Bản JAIST, Bài giảng tại đại học Bách Khoa Hà Nội, 12/2003. [23]. Đinh Điền, Ứng dụng Ngữ liệu song ngữ Anh - Việt điện tử trong ngành ngôn ngữ học so sánh, tạp chí Ngôn ngữ, Viện ngôn ngữ học, 2002. [24]. Đinh Điền, Xây dựng và khai thác Kho ngữ liệu song ngữ Anh - Việt điện tử, Luận án tiến sĩ ngữ văn, 2004 ._.