Đề tài Tìm hiểu mô hình crf và ứng dụng trong trích chọn thông tin trong tiếng việt

i TRƯỜNG ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Loan TÌM HIỂU MÔ HÌNH CRF VÀ ỨNG DỤNG TRONG TRÍCH CHỌN THÔNG TIN TRONG TIẾNG VIỆT KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI -2009 ii TRƯỜNG ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Loan TÌM HIỂU MÔ HÌNH CRF VÀ ỨNG DỤNG TRONG TRÍCH CHỌN THÔNG TIN TRONG TIẾNG VIỆT KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn : Tiến Sĩ Nguyễn Trí Thành HÀ NỘI – 2009 iii LỜI CẢM ƠN Trước tiên, em muốn gửi lời cảm ơn sâu sắc đến Tiến Sĩ Nguyễn Trí Thành, người đã tận tình hướng dẫn em trong suốt quá trình thực hiện khóa luận. Em xin gửi lời cảm ơn chân thành và sâu sắc tới các thầy, cô tại trường Đại học Công Nghệ đã dạy dỗ và tận tình chỉ bảo cho tôi trong suốt quá trình học tập tại trường. Những kiến thức mà thầy cô truyền đạt sẽ là vốn quý báu cho chúng em bước vào tương lai. Mình xin cảm ơn tập thể sinh viên K50C Trường Đại học Công Nghệ đã ủng hộ và khuyến khích tôi trong quá trình nghiên cứu và thực hiện khóa luận này. Cuối cùng, con xin cảm ơn chân thành và biết ơn vô hạn tới gia đình, những người có công sinh thành, nuôi dưỡng, những người luôn kịp thời động viên và giúp đỡ vượt qua những khó khăn trong cuộc sống. 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 chắc chắn sẽ không tránh khỏi những thiếu sót. Chúng em kính mong nhận được sự thông cảm của quý Thầy Cô và các bạn Hà Nội, ngày 12 tháng 5 năm 2009 Sinh viên Nguyễn Thị Loan iv TÓM TẮT Nội dung của khóa luận là tìm hiểu mô hình CRF, và ứng dụng của mô hình này trong trích chọn thông tin trong tiếng Việt. Trước hết khóa luận trình bày những khái niệm chung về trích chọn thông thông tin. Đồng thời nêu đến hai hướng tiếp cận để xây dựng một hệ thống trích chọn thông tin cũng như ưu nhược điểm của từng hướng tiếp cận, Đồng thời cũng nêu ra được ứng dụng của trích chọn thông tin trong tiếng Việt như thế nào. Cụ thể ở đây là bài toán trích chọn thông tin nhà đất. Để ứng dụng trích chọn trong tiếng Việt luận văn đã nêu ra được ba mô hình học máy trong đó tập trung chủ yếu vào mô hình Conditional Random Field –CRF. Bất kỳ mô hình nào cũng có ưu nhược điểm trong luận văn này trình bày hai vấn đề lớn của mô hình CRF đó là vấn đề gán nhãn và ước lượng tham số. Đồng thời cũng trình bày về công cụ hữu ích CRF++. Luận văn cũng trình bày được việc ứng dụng mô hình CRF làm nền tảng lý thuyết và cơ sở thực hành là công cụ CRF vào bài toán trích chọn thông tin nhà đất. Một bài toán nhỏ trong bài toán xử lý ngôn ngữ tự nhiên. v MỤC LỤC LỜI CẢM ƠN ................................................................................................................... iii TÓM TẮT ..........................................................................................................................iv MỤC LỤC ...........................................................................................................................v DANH MỤC CÁC HÌNH VẼ ..........................................................................................vii BẢNG CÁC KÍ HIỆU VIẾT TẮT ................................................................................ viii LỜI MỞ ĐẦU .....................................................................................................................1 Chương 1.TỔNG QUAN....................................................................................................3 1.1. TRÍCH CHỌN THÔNG TIN ................................................................................................ 3 1.2. CÁC CÁCH TIẾP CẬN TRÍCH CHỌN THÔNG TIN........................................................ 5 1.2.1. Hướng tiếp cận dựa trên tri thức.......................................................................5 1.2.2. Hướng tiếp cận xây dựng các mô hình học máy ...............................................5 1.3. KIẾN TRÚC HỆ THỐNG IE................................................................................................ 7 1.4. BÀI TOÁN TRÍCH CHỌN THÔNG TIN NHÀ ĐẤT ..............................................8 1.5. Ý NGHĨA CỦA BÀI TOÁN TRÍCH CHỌN THÔNG TIN NHÀ ĐẤT .............................. 9 1.6. TỔNG KẾT CHƯƠNG....................................................................................................... 10 Chương 2. CONDITIONAL RANDOM FIELDS .........................................................11 2.1. MÔ HÌNH MARKOV ẨN- HMM...................................................................................... 11 2.2. MÔ HÌNH CỰC ĐẠI HÓA ENTROPY-MEMM............................................................... 13 2.3. MÔ HÌNH CONDITIONAL RANDOM FIELDS.............................................................. 15 2.3.1.Việc gán nhãn cho dữ liệu tuần tự ....................................................................15 2.3.2. Định nghĩa CRF...............................................................................................16 2.3.3. Nguyên lý cực đại hóa Entropy .......................................................................18 2.3.3.1. Độ đo Entropy điều kiện .................................................................................. 18 2.3.3.2. Các ràng buộc đối với phân phối mô hình..................................................... 19 2.3.3.3. Nguyên lý cực đại hóa Entropy....................................................................... 20 2.3.4. Hàm tiềm năng của các mô hình CRF.............................................................20 2.3.5. Conditional Random Fields.............................................................................21 2.3.6. So sánh với các mô hình khác .........................................................................22 2.4. TỔNG KẾT CHƯƠNG....................................................................................................... 23 Chương 3. THUẬT TOÁN GÁN NHÃN VÀ ƯỚC LƯỢNG THAM SỐ CỦA MÔ HÌNH CRF VÀ CÔNG CỤ CRF ++..............................................................................24 3.1. THUẬT TOÁN GÁN NHÃN CHO DỮ LIỆU DẠNG CHUỖI......................................... 24 vi 3.2. XÁC SUẤT CRF ĐƯỢC TÍNH NHƯ MỘT MA TRẬN.................................................. 25 3.3. ƯỚC LƯỢNG THAM SỐ CHO MÔ HÌNH CRF............................................................ 26 3.3.1. Thuật toán S..................................................................................................28 3.3.2. Thuật toán T .................................................................................................29 3.4. CÔNG CỤ CRF++ TOOLKIT............................................................................................ 30 3.4.1. Giới thiệu.......................................................................................................30 3.4.2. Tính năng.......................................................................................................31 3.4.3. Cài đặt và cách sử dụng.................................................................................31 3.4.3.1 Cài đặt.......................................................................................................31 3.4.3.2. File định dạng huấn luyện và test ................................................................ 31 3.4.3.3. Template type................................................................................................. 32 3.4.4. Huấn luyện và kiểm tra...................................................................................34 3.5. TỔNG KẾT CHƯƠNG....................................................................................................... 36 Chương 4. ỨNG DỤNG CRF VÀO BÀI TOÁN TRÍCH CHỌN THÔNG TIN NHÀ ĐẤT....................................................................................................................................37 4.1. MÔ HÌNH HÓA BÀI TOÁN TRÍCH CHỌN THÔNG TIN NHÀ ĐẤT ........................... 37 4.1.1. Xử lý dữ liệu đầu vào .....................................................................................38 4.2. MÔI TRƯỜNG THỰC NGHIỆM ...................................................................................... 39 4.2.1. Phần cứng ......................................................................................................39 4.2.2. Phần Mềm......................................................................................................39 4.2.3. Dữ liệu thực nghiệm......................................................................................39 4.2.3.1. Lần thử nghiệm thứ nhất ................................................................................... 40 4.2.3.2. Lần thử nghiệm thứ hai ..................................................................................... 40 4.2.3.3. Kết quả và đánh giá ........................................................................................... 42 4.3. HẠN CHẾ VÀ HƯỚNG ĐI CHO TƯƠNG LAI................................................................ 44 4.4. TỔNG KẾT CHƯƠNG....................................................................................................... 45 KẾT LUẬN .......................................................................................................................46 TÀI LIỆU THAM KHẢO................................................................................................47 vii DANH MỤC CÁC HÌNH VẼ Hình 1. Một hệ thống trích chọn thông tin ..........................................................................4 Hình 2. Mô hình xây dựng IE theo hướng tiếp cận dựa trên tri thức ...................................5 Hình 3. Mô hình xây dựng IE theo mô hình học máy..........................................................6 Hình 4. Modules chính của hệ thống IE..............................................................................7 Hình 5. HMM .....................................................................................................................12 Hình 6. Đồ thị vô hướng HMM..........................................................................................12 Hình 7. Đồ thị có hướng mô tả cho mô hinh MEMM........................................................13 Hình 8. Label alias..............................................................................................................14 Hình 9. Một trường ngẫu nhiên ..........................................................................................17 Hình 10. Đồ thị vô hướng mô tả cho CRF .........................................................................17 Hình 11. Mô tả các hàm tiềm năng....................................................................................18 Hình 12. Tỷ lệ lỗi của CRF so với các mô hình học máy khác..........................................23 Hình 13. Mô hình hoạt động của CRF++...........................................................................31 Hình 14. Mô hình xử lý dữ liệu của bài toán trích chọn nhà đất........................................38 Hình 15. Biểu đồ thể hiện sự tương quan giữa hai lần kiểm tra.........................................44 viii BẢNG CÁC KÍ HIỆU VIẾT TẮT STT Kí hiệu Chú giải cho kí hiệu sử dụng 1 IE Trích chọn thông tin 2 HMM Mô hình Markov ẩn 3 MEMM Mô hình cực đại hóa Entropy 4 CRF Trường ngẫu nhiên có điều kiện 5 IR Tìm kiếm thông tin 1 LỜI MỞ ĐẦU Trong thời đại bùng nổ công nghệ thông tin như hiện nay thì việc ứng dụng công nghệ thông tin trong các lĩnh vực của đời sống ngày càng đa dạng và phong phú. Toàn bộ các ứng dụng đều thực hiện trên các thông tin đầu vào từ dạng đơn giản đến phức tạp. Từ dạng văn bản dạng ký tự thông thường cho đến những thông tin đầu vào phức tạp như hình ảnh, âm thanh. Việc ứng dụng công nghệ xử lý ngôn ngữ cũng hết sức phong phú. Có thể kể tới trong những năm gần đây có một số công nghệ rất nổi tiếng như [1]: Hãng SAMSUNG đưa ra thị trường điện thoại di động P207 có thể nhận biết được các câu nói đơn giản ví dụ “tôi sẽ gọi lại” rồi chuyển chúng về dạng tin nhắn. Bên cạnh đó có rất nhiều những công nghệ dịch tự động trên web như Language Tool dịch nhiều thứ tiếng trong google. Có thể phân loại các bài toán như xử lý tiếng nói hay xử lý hình ảnh (speech and image processing), xử lý văn bản (text processing), khai phá văn bản hoặc web (text and web mining). Tất cả các bài toán đều được thực hiện bằng máy, tuy nhiên vấn đề đặt ra là làm thế là để máy có thể xử lý một cách tự động lại là một bài toán khó. Cái khó ở chỗ làm sao cho máy hiểu được ngôn ngữ đa dạng của con người. Đối với tiếng Việt đã có một số các sản phẩm liên quan đến tiếng Việt như: Bộ gõ chữ tiếng Việt, chương trình nhận dạng chữ tiếng Việt như VnDOCR của viện Công Nghệ Thông Tin, các phần mềm như EVTRAN, gần đây tiêu biểu là kết quả của việc Việt hóa Windows và Office. Là người đi sau trong lĩnh vực xử lí ngôn ngữ tự nhiên, việc hiểu các công nghệ ngôn ngữ là rất cần thiết. Trong luận văn này đề cập tới ứng dụng của CNTT trong việc trích chọn thông tin trong tiếng Việt. Có rất nhiều phương pháp, trong luận văn này giới thiệu mô hình Conditional Random Field là cơ sở lý thuyết để thực hiện công việc và công cụ CRF++ để thực hành trích chọn thông tin trong tiếng Việt và cụ thể là bài toán trích chọn thông tin nhà đất. Trong khuôn khổ của khóa luận tốt nghiệp với đề tài “Tìm hiểu mô hình CRF và ứng dụng trong trích chọn thông tin trong tiếng Việt” em xin trình bày một công nghệ ứng dụng trong việc xử lý ngôn ngữ tiếng Việt. Nội dung khóa luận gồm 4 chương: ¾ Chương 1: Tổng quan: Giới thiệu tổng quan về trích chọn thông tin, và các cách tiếp cận để xây dựng hệ thống trích chọn thông tin những ứng dụng của trích chọn thông tin, và ứng dụng trong xử lý tiếng Việt, đồng 2 thời cũng mô hình hóa và nêu được ý nghĩa của bài toán trích chọn thông tin nhà đất. ¾ Chương 2: Conditional Random Fields: Chương này giới thiệu một số mô hình học máy như HMM, MEMM và tập trung vào mô hình Conditional Random Field – CRF. Đưa ra được khái niệm trường ngẫu nhiên, trường ngẫu nhiên có điều kiện. Đồng thời cũng chỉ ra được rằng mô hình CRF hiệu quả hơn so với các mô hình học máy khác. ¾ Chương 3: Thuật toán gán nhãn và ước lượng tham số cho mô hình CRF và công cụ CRF++: Chương này đưa ra hai vấn đề cơ bản của mô hình CRF và hướng giải quyết hiệu quả nhất. Ở đây thuật toán gán nhãn sử dụng thuật toán Viterbi một thuật toán trong quy hoạch động. Và hai thuật toán T và thuật toán S giải quyết vấn đề ước lượng tham số cho mô hình CRF. Đồng thời cũng giới thiệu được công cụ CRF++ toolkit, một công cụ cài đặt mô hình CRF được sử dụng trong bài toán trích chọn thông tin nhà đất. ¾ Chương 4: Ứng dụng CRF vào bài toán trích chọn thông tin nhà đất: Chương này nói về việc ứng dụng của mô hình CRF đã nói ở các chương trước vào bài toán trích chọn thông tin nhà đất. Một hướng đi mới trong bài toán xử lý ngôn ngữ tự nhiên. 3 Chương 1. TỔNG QUAN Chủ đề chính của khóa luận là tìm hiểu mô hình Conditional Random Field và ứng dụng trong trích chọn thông tin trong tiếng Việt. Chương này sẽ giới thiệu tổng quan về trích chọn thông tin và các hướng tiếp cận trích chọn thông tin. Đồng thời cũng nêu được ý nghĩa của việc trích chọn thông tin trong tiếng Việt. 1.1. TRÍCH CHỌN THÔNG TIN Khi tìm kiếm một thư mục có chứa rất nhiều thư mục con hoặc rất nhiều file với nhiều định dạng khác nhau. Thực chất là chúng ta đang làm việc với các ký tự [10] [11]. Do vậy có rất nhiều hướng để xử lý như: ¾ Lọc, đếm từ: Tập tin như một chuỗi các ký tự ASCII. Ví dụ trong Linux có thể tìm kiếm file hoặc các ký tự bằng lệnh grep với điều kiện là đưa ra một chuỗi mô ta cho nó. ¾ Tìm kiếm thông tin hoặc tài liệu: Tệp tin là những từ có thể là một chuỗi các đơn vị từ mang một ý nghĩa nào đó. ¾ Trích chọn thông tin: Cũng như “tìm thông tin tài liệu” nhưng nó có thể là một từ hoặc một cụm từ có nghĩa và liên quan đến một chủ đề cụ thể nào đó. ¾ Hiểu toàn văn bản (text understanding). Tệp tin như câu truyện, tiểu thuyết. Với dữ liệu đầu vào rất lớn. Và nhiệm vụ của mình phải “hiểu toàn văn bản” mới đưa ra được nội dung cần quan tâm. Không giống như việc hiểu toàn văn bản (tất cả các câu chữ đều liên quan đến nhau), các hệ thống trích chọn thông tin chỉ cố gắng nhận biết một số nội dung thông tin đáng quan tâm. Có thể kể tới các mức độ trích chọn thông tin từ văn bản sau: Trích chọn các thực thể (Entity Extraction), trích chọn quan hệ giữa các thực thể (Relation Extraction), xác định đồng tham chiếu (Co-reference Resolution). Cũng phải lưu ý rằng trích chọn không đơn thuần là trích chọn trong một văn bản với các ký tự ASCII hoặc Unicode. Trích chọn ở đây có thể là trích chọn âm thanh, trích chọn hình ảnh. Tuy nhiên trong luận văn này chỉ tập chung giới thiệu trích chọn thông tin liên quan tới văn bản. 4 Các kỹ thuật sử dụng trong trích chọn thông tin gồm: Phân đoạn, phân lớp, kết hợp và phân cụm. Hình 1. Một hệ thống trích chọn thông tin Trích chọn thông tin như một nhiệm vụ lấp đầy các trường (slots) trong cơ sở dữ liệu bằng những đoạn text nhỏ hơn (hay nói cách khác kết quả của một hệ thống trích chọn thông tin thường là các mẫu chứa một số lượng xác định các trường đã được điền thông tin). Ví dụ như ở hình 1 ta có một hệ thống trích chọn những tên riêng xuất hiện trong văn bản, trích chọn các tổ chức liên quan, tìm các sự liên kết giữa các tổ chức và tên người, vị trí của người đó trong tổ chức và cuối cùng là đưa vào trong cơ sở dữ liệu. October 14, 2002, 4:00 a.m. PT For years, Microsoft Corporation CEO Bill Gates railed against the economic philosophy of open-source software with Orwellian fervor, denouncing its communal licensing as a "cancer" that stifled technological innovation. Today, Microsoft claims to "love" the open- source concept, by which software code is made public to encourage improvement and development by outside programmers. Gates himself says Microsoft will gladly disclose its crown jewels--the coveted code behind the Windows operating system--to select customers. "We can be open source. We love the concept of shared source," said Bill Veghte, a Microsoft VP. "That's a super-important shift for us in terms of code access.“ Richard Stallman, founder of the Free Software Foundation, countered saying… Microsoft Corporation CEO Bill Gates Microsoft Gates Microsoft Bill Veghte Microsoft VP Richard Stallman founder Free Software Foundation N A M E T I T L E O R GA N I ZA T I O N B i l l G at e s CE O M i cr o s o f t B i l l V e g ht e VP M i cr o s o f t R i ch a r d S t a l lm a n fo u n d e r Fr e e S of t . . * * * * 5 1.2. CÁC CÁCH TIẾP CẬN TRÍCH CHỌN THÔNG TIN 1.2.1. Hướng tiếp cận dựa trên tri thức Đặc điểm của việc xây dựng hệ thống trích chọn thông tin theo hướng này là hệ thống luật được xây dựng bằng tay hoàn toàn phụ thuộc vào kinh nghiệm riêng của từng người trong từng lĩnh vực của IE, các mẫu hay các luật được tạo ra và được kiểm duyệt một cách kỹ lưỡng có quy mô bởi các “knowlegde engineer” [10]. Những quy tắc luôn được kiểm định nhiều lần. Có thể mô hình hóa việc xây dựng này theo hình 2 như sau: Hình 2. Mô hình xây dựng IE theo hướng tiếp cận dựa trên tri thức Với cách tiếp cận này thì hệ thống hoạt động theo một chu trình. Để xây dựng một hệ thống hoạt động tốt phải luôn luôn có sự tương tác giữa người viết luật và hệ thống cùng với kho ngữ liệu huấn luyện (hình 2) và tập luật luôn luôn được cập nhật để cho hệ thống có thể