Khóa luận 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ể hoạt động tốt nhất. 1.2.2. Hướng tiếp cận xây dựng các mô hình học máy Với hệ thống IE được xây dựng theo hướng tiếp cận dựa trên tri thức thì chu trình kiểm tra và sửa lỗi gặp rất nhiều khó khăn và phụ thuộc vào nhiều yếu tố như: Loại ngôn ngữ, thời gian và khả năng viết luật. Chỉ một vài thay đổi trong đặc tả cũng gây khó khăn trong sự điều chỉnh. Câu trả lời cho các giới hạn này là phải xây dựng một mô hình bằng cách nào đó có thể “tự học”. Điều này sẽ giúp làm giảm bớt sự tham gia của các chuyên gia ngôn ngữ và làm tăng tính linh hoạt cho hệ thống. Có rất nhiều phương pháp học máy như mô hình markov ẩn (Hidden Markov Models-HMM), các mô hình Markov cực đại hóa Entropy (Maximum Markov Models – MEMM) và mô hình các trường ngẫu nhiên có Kho tài liệu Luật cũ Kiểm duyệt Sửa chữa Luật mới Cập nhật knowlegde engineer 6 điều kiện ( Conditional Random Fields – CRF)… Các mô hình này sẽ được đề cập chi tiết trong chương sau. Các đặc điểm phải kể đến của việc xây dựng hệ thống IE theo hướng hệ thống có thể tự đào tạo (automatic training approach) là không cần một người nào đó hiểu biết về cách hoạt động của hệ thống IE và viết luật cho nó như thế nào [10]. Điều cần thiết ở đây là một người nào đó biết được miền ứng dụng của nó và hiểu được những thông tin cần rút trích. Một khi dữ liệu huấn luyện được chú thích, thuật toán huấn luyện chạy và sinh ra những thông tin học được hay còn gọi là model để phục vụ cho quá trình trích chọn tự động sau này. Mô hình với hướng tiếp cận này được mô tả qua hình 3 như sau: Các thuật học sẽ dựa trên dữ liệu để tự học và thu được một model, dựa trên model này nó sẽ trích chọn các thông tin trên dữ liệu mới. Hình 3. Mô hình xây dựng IE theo mô hình học máy Khi xây dựng hệ thống IE theo hướng này phải tập trung vào việc tạo ra dữ liệu huấn luyện. Hệ thống có thể tự học mà không cần sự can thiệp của bất kỳ các chuyên viên nào. Tuy vậy việc xây dựng và lưu trữ tập dữ liệu huấn luyện rất khó và đắt vì để hệ thống có thể thực hiện tốt thì yêu cầu dữ liệu phải nhiều đó cũng là hệ quả dẫn đến việc khó sửa đổi. Vì chỉ cần thêm hoặc xóa các thuộc tính thì cần phải thay đổi trên toàn tập huấn luyện của nó. Tùy vào công việc và những điều kiện đã có mà ta có thể xây dựng hệ thống IE theo hướng các mô hình học máy hoặc theo hướng tiếp cận dựa tri thức. Ví dụ như khi nguồn văn bản và người viết luật đáp ứng được yêu cầu thì nên xây dựng hệ thống IE theo hướng tiếp cận dựa tri thức, hoặc khi các mô tả về thông tin trích chọn luôn có sự thay đổi thì cũng lên làm theo hướng thứ nhất. Còn với dữ liệu lớn thì nên xây dựng hệ thống IE theo mô hình học máy. Dữ liệu Huấn luyện Thuật toán học Model file 7 1.3. KIẾN TRÚC HỆ THỐNG IE Mặc dù hệ thống IE được xây dựng theo các ứng dụng và công việc khác nhau, theo những cách khác nhau. Nhưng về cơ bản thì một hệ thống IE nói chung có những phần tử chính được mô tả trong hình sau: Hình 4. Modules chính của hệ thống IE Với mô hình trên thì tùy thuộc vào từng ngôn ngữ mà có các bài toán cụ thể và có những phương pháp xử lý cho phù hợp. Với rất nhiều ngôn ngữ đa dạng do vậy hệ thống từ tố của mỗi quốc gia sẽ khác nhau: Ví dụ như ngôn ngữ Trung Quốc và Nhật Bản khác hẳn so với chuẩn ngôn ngữ European. Nhưng chúng ta quan tâm là đối với tiếng Việt thì có những khó khăn gì trong quá trình xử lý. Về mặt ngữ pháp và ngữ nghĩa gặp rất nhiều khó khăn. Vì các công cụ để xử lý trong các bước trên là hầu như chưa có sẵn, hơn nữa đối với tiếng Việt là một ngôn ngữ đơn âm và đa âm phức tạp do vậy việc xử lý cũng gặp khó khăn. Phân đoạn từ Gán nhãn từ loại Phân tích cú pháp hoàn chỉnh Đồng tham chiếu Trộn các kết quả Phân tích từ tố Xử lý hình thái, và từ vựng Phân tích cú pháp Phân tích miền 8 1.4. BÀI TOÁN TRÍCH CHỌN THÔNG TIN NHÀ ĐẤT Các bài toán điển hình trong xử lý tiếng Việt đó là: nhận biết các loại thực thể, phân nhóm các cụm từ tiếng Việt, phân loại văn bản tiếng Việt. Đây là những bài toán cơ bản nhưng đóng vai trò quan trọng để giúp xử lý các bài toàn phức tạp trong lĩnh vực này. Trong luận văn này trình bày bài toán trích chọn thông tin nhà đất. Ở đây chúng ta phải phân biệt rõ giữa tìm kiếm thông tin (Information Retrival - IR) và trích chọn thông tin (Information Extraction -IE). IR có thể hiểu đơn giản là từ một nguồn rất nhiều tệp văn bản hay tiếng nói tìm ra những tệp có nội dung liên quan đến một câu hỏi hay một điều cần biết. Điển hình của công nghệ này là Google, một hệ tìm kiếm trên web. Cần nói thêm rằng mặc dù rất hữu hiệu, nhưng google chỉ cho chúng ta tìm theo những từ khóa và đôi khi tìm những kết quả không hề liên quan, hoặc tìm ra những văn bản vốn đã tồn tại trên Web. Với Information Extraction từ một nguồn rất nhiều tệp văn bản hay lời nói tìm ra những đoạn bên trong một số tệp liên quan đến một vấn đề cần quan tâm. Ví dụ xét một bản tin nhà đất sau: “Cần bán chung cư TT9 Văn Phú mặt đường Lê Trọng Tốn, diện tích 90m2, mặt tiền 4,5m. Giá bán: 1 tỷ Liên hệ: 0988830999” Với bản tin nhà đất trên ta chỉ cần quan tâm đến địa chỉ, diện tích, giá bán, loại nhà và điện thoại liên hệ. Do vậy không nhất thiết phải hiểu toàn văn bản, mục đích của bài toán trích chọn thông tin nhà đất là làm sao đưa ra được các thông tin liên quan đến địa chỉ, diện tích, giá bán, loại nhà… từ một khối dữ liệu rất lớn. Với mục đích đó văn bản trên có thể được mô phỏng bằng cách gán nhãn như sau: Cần bán chung cư TT9 Văn Phú mặt đường Lê Trọng Tốn , diện tích 90m2, mặt tiền 4,5m. Giá bán: 1 tỷ . Liên hệ: 0988830999 . Với các quy ước các nhãn cho các từ tố trong đoạn tin trên như sau: 9 DC: Địa chỉ trong đó B-DC là từ bắt đầu của địa chỉ và I-DC là các từ tiếp theo của địa chỉ 9 GB: Giá bán trong đó B-GB là từ bắt đầu của giá bán và I-GB là các từ tiếp theo của giá bán 9 DT: Diện tích trong đó B-DT là từ bắt đầu của diện tích và I-DT từ tiếp theo của diện tích 9 9 DD:Di động trong đó B-DD là từ bắt đầu của số di động và I-DD là các từ tiếp theo của số di động 9 LN: loại nhà có thể là chung cư hoặc căn hộ, trong đó B-LN là từ bắt đầu loại nhà, I-LN là từ tiếp theo của loại nhà. Cũng như các bài toán trích chọn khác như: trích chọn thực thể, nhận dạng tên, trích chọn thông tin nhà đất cũng có các hướng tiếp cận khác nhau, trong luận văn này tập trung vào bài toán trích chọn thông tin nhà đất theo phương pháp học máy bằng cách sử dụng mô hình CRF. Một mô hình được đánh giá là có chất lượng cao đối với bài toán trích chọn thông tin. 1.5. Ý NGHĨA CỦA BÀI TOÁN TRÍCH CHỌN THÔNG TIN NHÀ ĐẤT Trong bất cứ một ngôn ngữ nào thì việc thì việc tìm ra những thông tin liên quan là điều rất quan trọng mà không cần phải đọc hiểu toàn bộ văn bản. Chính vì vậy việc trích chọn thông tin có một nghĩa rất lớn trong việc xử lý ngôn ngữ tự nhiên. ¾ Tiết kiệm thời gian. Như chúng ta đã biết thì mỗi một bản tin đăng trên những website khác nhau thì có những định dạng rất khác nhau: Có thể là định dạng văn bản thông thường, cũng có thể là dạng bảng biểu, hoặc các đường liên kết… Với những cách thể hiện văn bản như vậy thì việc tìm ra những thông tin như diện tích của ngôi nhà, địa chỉ… Là một việc tương đối khó khăn. Với bài toán trích chọn thông tin nhà đất thì sẽ tiết kiệm thời gian rất nhiều cho người bán và người mua. ¾ Có thể tìm kiếm thông tin chính xác hơn rất nhiều. Vấn đề ở đây là trong một bản tin có sự nhập nhằng giữa thông tin địa chỉ của mảnh đất và địa chỉ của người chủ. Việc trích chọn có thể giảm bớt sự nhập nhằng trong thông tin này. Nói rộng hơn nữa bài toán trích chọn thông tin nhà đất chỉ là bài toán nhỏ. Từ bài toán này ta cũng thấy được ý nghĩa của việc trích chọn thông tin trong tiếng Việt. ¾ Giúp cho việc tóm tắt văn bản chính xác nếu như chủ đề của văn bản được chỉ rõ ¾ Tự tạo ra các trường liên quan một cách tự động trong cơ sở dữ liệu được lấy từ văn bản. ¾ Một số ứng dụng điển hình của trích chọn thông tin: sử dụng trích chọn thông tin trong thư viện số- DL (Digital Libraries) - thư viện số có thể hiểu là các văn 10 bản hoặc hình ảnh…. Rút trích thông tin từ thư điện tử. Trích chọn tiểu sử người (có thể là chân dung, vị trí, email, địa chỉ, số điện thoại, số fax…) 1.6. TỔNG KẾT CHƯƠNG Chương này giới thiệu tổng quan về trích chọn thông tin. Với hai hướng tiếp cận của xây dựng hệ thống trích chọn thông tin theo hướng máy tri thức và theo hướng hệ thống tự đào tạo giúp mọi người có thể hình dung ra được các cách tiếp cận với trích chọn thông tin. Đồng thời cũng nêu ra được nhiệm vụ của khóa luận. 11 Chương 2. CONDITIONAL RANDOM FIELDS Như giới thiệu trong chương trước, chương này giới thiệu vào một số mô hình học máy, trong đó tập trung vào mô hình Conditional Random Fields (CRF) [11] [13] [8] [17], phần đầu nêu lên hai mô hình học máy HMM, và MEMM và những vấn đề gặp phải từ đó nêu lên mô hình học máy CRF có thể giải quyết được các vấn đề đó như thế nào. Đồng thời cũng giới thiệu được chi tiết về mô hình CRF như: Đưa ra được định nghĩa CRF, xác định các hàm tiềm năng của CRF thông qua nguyên lý cực đại hóa Entropy, xác định được các ràng buộc của mô hình. Một số qui ước ký hiệu: ¾ Chữ viết hoa X, Y, Z.. kí hiệu cho các biến ngẫu nhiên. ¾ Chữ đậm xr ví dụ: x = (x1,...,xn), y, t .. ký hiệu các vector vector biểu diễn chuỗi dữ liệu quan sát , vector biểu diễn chuỗi các nhãn. ¾ xi , yi biểu diễn các thành phần trong một vector. ¾ chữ viết thường x, y, z…. là ký hiệu cho một giá trị đơn như một dữ liệu quan sát hay một trạng thái. ¾ S là tập các hữu hạn trạng thái. ¾ O là tập dữ liệu quan sát được. 2.1. MÔ HÌNH MARKOV ẨN- HMM Mô hình Markov được giới thiệu vào cuối những năm 1960 [12]. Cho đến hiện nay nó có một ứng dụng khá rộng như trong nhận dạng giọng nói, tính toán sinh học (Computational Biology ), và xử lý ngôn ngữ tự nhiên. HMM là mô hình máy hữu hạn trạng thái với các tham số biểu diễn xác suất chuyển trạng thái và xác suất sinh dữ liệu quan sát tại mỗi trạng thái. Mô hình Markov ẩn là mô hình thống kê trong đó hệ thống được mô hình hóa được cho là một quá trình Markov với các tham số không biết trước, nhiệm vụ là xác định các tham số ẩn từ các tham số quan sát được. Các tham số của mô hình được rút ra sau đó có thể sử dụng để thực hiện các phân tích kế tiếp. Trong bài toán trích chọn thông tin nhà đất thì các tham số quan sát được đó chính là các từ trong câu, còn các trạng thái chính là các nhãn B-DC, I-DC, B-DT, I-DT.. 12 Trong một mô hình Markov điển hình, trạng thái được quan sát trực tiếp bởi người quan sát [21], và vì vậy các xác suất chuyển tiếp trạng thái là các tham số duy nhất (hình 5 có thể mô tả rõ cho điều này). Hình 5. HMM - xi — Các trạng thái trong mô hình Markov - aij — Các xác suất chuyển tiếp - bij — Các xác suất đầu ra - yi — Các dữ liệu quan sát Mô hình Markov ẩn thêm vào các đầu ra: mỗi trạng thái có xác suất phân bố trên các biểu hiện đầu ra có thể. Vì vậy, nhìn vào dãy của các biểu hiện được sinh ra bởi HMM không trực tiếp chỉ ra dãy các trạng thái. Ta có tìm ra được chuỗi các trạng thái mô tả tốt nhất cho chuỗi dữ liệu quan sát được bằng cách tính. )(/)|()|( XPXYPXYP = (2.1) Hình 6. Đồ thị vô hướng HMM Ở đó Yn là trạng thái tại thời điểm thứ t=n trong chuỗi trạng thái Y, Xn là dữ liệu quan sát được tại thời điểm thứ t=n trong chuỗi X. Do trạng thái hiện tại chỉ phụ thuộc vào trạng thái ngay trước đó với giả thiết rằng dữ liệu quan sát được tại thời điểm t chỉ phụ thuộc và trạng thái t. Ta có thể tính P(Y, X). ∏ − −= n t tttt YXPYYPYXPYPXYP 2 1111 )|(*)|()|()(),( (2.2) Y1 Y2 … … … Yn X1 X2 … … … Xn 13 Một số hạn chế của mô hình Markov để tính được xác suất P(Y,X) thông thường ta phải liệt kê hết các trường hợp có thể của chuỗi Y và chuỗi X. Thực tế thì chuỗi Y là hữu hạn có thể liệt kê được, còn X (các dữ liệu quan sát) là rất phong phú. Để giải quyết các vấn đề này HMM đưa ra giả thiết về sự độc lập giữa các dữ liệu quan sát: Dữ liệu quan sát được tại thời điểm t chỉ phụ thuộc vào trạng thái tại thời điểm đó. Hạn chế thứ hai gặp phải là việc sử dụng xác suất đồng thời P(Y, X) đôi khi không chính xác vì với một số bài toán thì việc sử dụng xác suất điều kiện P(Y | X) cho kết quả tốt hơn rất nhiều. 2.2. MÔ HÌNH CỰC ĐẠI HÓA ENTROPY-MEMM Mô hình MEMM [4] thay thế các xác suất chuyển trạng thái và các xác suất sinh quan sát trong HMM bởi một hàm xác suất duy nhất P(Si | Si-1, Oi) (xác suất dịch chuyển từ trạng thái hiện tại là Si-1 tới trạng thái trước đó là Si với dữ liệu quan sát hiện tại là Oi) thay vì sử dụng P(Si | Si-1) và P(Oi | Si). Mô hình MEMM quan niệm rằng các quan sát đã được cho trước và chúng ta không cần quan tâm đến xác suất sinh ra chúng mà chỉ quan tâm vào xác suất chuyển trạng thái. Dưới đây là đồ thị có hướng mô tả cho mô hình MEMM. Hình 7. Đồ thị có hướng mô tả cho mô hinh MEMM Qua đồ thị ta nhận thấy rằng quan sát hiện tại không chỉ phụ thuộc vào trạng thái hiện tại mà còn có thể phụ thuộc vào trạng thái trước đó. Xác suất P(S | O) có thể tính như sau: ∏ = −= n t ttt OSSPOSPOSP 1 1 ),|(*),()|( (2.3) MEMM coi dữ liệu quan sát là các điều kiện cho trước thay vì coi chúng là các thành phần được sinh bởi mô hình như trong HMM vì thế xác suất chuyển trạng thái có thể phụ thuộc vào các thuộc tính đa dạng của chuỗi dữ liệu quan sát. S1 S2 … … … Sn S1:n 14 Với mô hình này ta chia ),|( 1 ttt OSSP − thành các hàm dịch chuyển được huấn luyện một cách riêng biệt trong |S| - tập hợp trạng thái. Như sau: ),|()|( 11t tttttS OSSPOSP −=− McCallum xác định phân phối cho xác suất chuyển trạng thái có dạng hàm mũ sau: ⎟⎠ ⎞⎜⎝ ⎛= ∑ − − ),(exp),( 1)|( 1 1 tta a a tt ttS SOfSOZ OSP t λ (2.4) Ở đây aλ là các tham số cần được huấn luyện; Z(Ot, St) là thừa số chuẩn hóa để tổng xác suất chuyển từ trạng St-1 sang St kề với nó đều bằng 1; fa(Ot, St) là hàm thuộc tính tại vị trí thứ i trong chuỗi dữ liệu quan sát và trong chuỗi trạng thái. Ở đây ta định nghĩa mỗi một thuộc tính fa có hai đối số: Dữ liệu quan sát hiện tại và trạng thái hiện tại. McCallum cũng đinh nghĩa a= trong đó b chỉ phụ thuộc vào dữ liệu quan sát hiện tại. 1 nếu dữ liệu quan sát hiện tại là “1tỷ” b(Ot)= 0 nếu ngược lại Hàm thuộc tính fa xác định nếu b(Ot) nhận một giá trị xác định: 1 nếu b(Ot)=1 và St=St-1 f(Ot,St)= 0 nếu ngược lại Vấn đề “label alias” gặp phải trong mô hình MEMM Vấn đề gặp phải ở mô hình MEMM [14] “lable alias”. Xét một ví dụ đơn giản sau: Hình 8. label alias 15 Giả sử ta cần xác định chuỗi trạng thái khi xuất hiện chuỗi quan sát là “rob” do vậy chuỗi trạng thái đúng là 0345 vì vậy ta mong đợi xác suất. P( 0345|rob ) > P( 0125|rob) Lại có P(0125|rob) = P(0)*P(1|0, r)*P(2|1,o )*P(5|2, b). Do xác suất chuyển trạng thái của 2 trạng thái kề nhau là l. Do vậy: P(0125 | rob)=P(0)*P(1 | 0, r). Tương tự ta cũng có P(0345 | rob)=P(0)*P(3 | 0, r). Nếu trong tập huấn luyện “rib”xuất hiện nhiều hơn “rob” thì chuỗi trạng thái S=0125 luôn được chọn dù chuỗi quan sát là rib hay rob. Đây là hạn chế gặp phải trong mô hình MEMM, hạn chế này ảnh hưởng rất lớn đến quá trình gán nhãn của MEMM. Để giải quyết vấn đề alias Léon Bottou (1991) [4] đưa ra một số cách sau: Thứ nhất như mô hình ở trên ta có thể gộp trạng thái 1 và 4 và trì hoãn việc phân nhánh cho đến khi gặp một quan sát xác định ( Discriminating Observation ). Nhưng đối với máy hữu hạn trạng thái thì điều này không thể vì xảy ra sự bùng nổ tổ hợp. giải pháp thứ hai là ta có thể luôn thay đổi cấu trúc trạng thái của mô hình điều này có nghĩa xác suất của toàn bộ chuỗi trạng thái sẽ không được bảo tồn mà có thể bị thay đổi trong một vài bước chuyển tùy thuộc vào quan sát đó. Trên đây là những vấn đề hạn chế của HMM và MEMM từ đó cho thấy nhu cầu cần thiết của mô hình CRF có thể giải quyết những hạn chế trên. 2.3. MÔ HÌNH CONDITIONAL RANDOM FIELDS CRF được giới thiệu vào những năm 2001 bởi Lafferty và các đồng nghiệp [14] [11]. CRF là mô hình dựa trên xác xuất điều kiện, thường được sử dụng trong gán nhãn và phân tích dữ liệu tuần tự ví dụ ký tự, ngôn ngữ tự nhiên. Khác với mô hình MEMM, CRF là mô hình đồ thị vô hướng. Điều này cho phép CRF có thể định nghĩa phân phối xác suất của toàn bộ chuỗi trạng thái với điều kiện biết chuỗi quan sát cho trước thay vì phân phối trên mỗi trạng thái với điều kiện biết trạng thái trước đó và quan sát hiện tại như trong mô hình MEMM. Chính những tính chất này của CRF mà mô hình này giải quyết được vấn đề “label bias”. 2.3.1. Việc gán nhãn cho dữ liệu tuần tự Nhiệm vụ của gán nhãn tuần tự [13] để thiết lập chuỗi quan sát được xuất hiện trong nhiều trường. Một trong những phương thức phổ biến để thực hiện gán nhãn và 16 phân đoạn là sử dụng quy tắc HMM hoặc mô hình máy hữu hạn trạng thái để định nghĩa chuỗi các nhãn có thể xảy ra nhất cho những từ của bất cứ câu nào. Theo những nghiên cứu về mô hình Markov ẩn và mô hình cực đại hóa Entropy ở trên. Thì CRF đã giải quyết được toàn bộ những vấn đề mà hai mô hình trên mắc phải như “ label alias ”[11]. Conditional random fields là một probabilistic framework (theo xác suất) cho việc gán nhãn và phân đoạn dữ liệu tuần tự. Thay vì sử dụng xác suất độc lập trên chuỗi nhãn và chuỗi quan sát, ta sử dụng xác suất có điều kiện P(Y | X) trên toàn bộ chuỗi nhãn được đưa bởi chuỗi mỗi chuỗi quan sát X. CRF là một mô hình đồ thị vô hướng định nghĩa một phân bố tuyến tính đơn trên các chuỗi nhãn (trình tự nhãn) được đưa ra bởi các chuỗi quan sát được. CRFs thuận lợi hơn các mô hình Markov và MEMM. Nó làm tốt hơn cả của MEMM và HMM trên số lượng chuỗi gán nhãn lớn.Ví dụ: xét ngôn ngữ tự nhiên, việc gán nhãn cho các từ trong câu sẽ tương ứng với loại từ vựng. Ở đây các câu sẽ là dữ liệu tuần tự còn nhãn cần gán chính là các từ loại [NP He ] [VP reckons ] [NP the current account deficit ] [VP will narrow ] [PP to ] [NP only # 1.8 billion ] [PP in ] [NP September ] Trong đó ý nghĩa của các nhãn là: NP: nounse phrase, VP: verb phrase… Trong bài toán trích chọn thông tin nhà đất của mình thì dữ liệu tuần tự ở đây chính là các bản tin nhà đất, còn các nhãn cần gán đó là các thông tin về địa chỉ (B- DC, I-DC) hoặc diện tích (B-DT,I-DT)… 2.3.2. Định nghĩa CRF Trước khi xem định nghĩa trường ngẫu nhiên điều kiện ta xem định nghĩa thế nào là một trường ngẫu nhiên [9] Cho một đồ thị vô hướng không có chu trình G(V,E), ở đây V là tập các đỉnh của đồ thị và E là tập các cạnh vô hướng nối các đỉnh của đồ thị nếu thỏa mãn: Υ Υ ),|(),|( ikkijiji vvvvPvvvvP ≈=≠ thì V gọi là trường ngẫu nhiên (2.5) 17 Hình 9. Một trường ngẫu nhiên P(Y5| ΥYi)=P(Y5|Y4,Y6) . Vậy Y={Y5, Y4,Y6} là trường ngẫu nhiên. Tiếp đến chúng ta định nghĩa trường ngẫu nhiên có điều kiện như sau: X là biến ngẫu nhiên nhận giá trị là chuỗi dữ liệu cần phải gán nhãn.Y là biến ngẫu nhiên nhận giá trị là chuỗi nhãn tương ứng. Mỗi thành phần Yi của Y là một biến ngẫu nhiên nhận giá trị trong tập hữu hạn các trạng thái S. Các đỉnh V biểu diễn các thành phần của biến ngẫu nhiên Y sao cho tồn tại ánh xạ một – một giữa các đỉnh và một thành phần Yv của Y. Ta nói: CRF được định nghĩa: (Y | X) là một trường ngẫu nhiên điều kiện (Conditional Random Field) với điều kiện X khi ta chỉ tính được xác xuất có điệu kiện P(Yi | Xi) với Yi⊂Y và Xi⊂ X và với mỗi Xi ta chọn được argmaxYiP(Yi | Xi). Trong bài toán dữ liệu dạng chuỗi, G có thể được biểu diễn như sau: G = ( V={1,2,3,…m}, E={i,i+1}i=1…m-1). Kí hiệu X=(X1, X2…Xn), Y=(Y1, Y2,…Yn). Ta có mô hình đồ thị vô hướng của CRF có dạng sau: Hình 10. Đồ thị vô hướng mô tả cho CRF Y5 Y1 Y4 Y3 Y2 Y6 18 Gọi C là tập hợp tất cả các đồ thị con đầy đủ của đồ thị G (đồ thị biểu diễn cấu trúc của một CRF). Theo kết quả của Hammerly-Clifford cho các trường Markov, ta thừa số hóa được p(y | x) – xác suất của chuỗi nhãn với điều kiện biết chuỗi dữ liệu quan sát – thành tích các hàm tiềm năng: P(y|x)=∏ ∈ CA A xA )|(ψ (2.6) Có thể mô phỏng như hình sau: Hình 11. Mô tả các hàm tiềm năng Tính chất của trường ngẫu nhiên có điệu kiện là: ¾ Mô hình phân biệt (discriminative models) ¾ Mô hình chuỗi (sequential models) ¾ Mô hình đồ thị vô hướng (Undirected graphical models) 2.3.3. Nguyên lý cực đại hóa Entropy Laferty xác định các hàm tiềm năng cho các mô hình CRF dựa trên nguyên lý cực đại hóa Entropy [7]. Nguyên lý này cho phép đánh giá các phân phối xác suất từ một tập các dữ liệu huấn luyện. 2.3.3.1. Độ đo Entropy điều kiện Entropy là độ đo tính đồng đều hay tính không chắc chắn của một phân phối xác suất [7]. Độ đo Entropy điều kiện của một phân phối mô hình trên “một chuỗi trạng thái với điều kiện biết chuỗi dữ liệu quan sát ” p(y | x) có dạng sau: H(y | x) = - ∑ yx, p(x, y)*log p(y | x) (2.7) = - ∑ yx, p^(x)*p(y | x)*log p(y | x) X1:n Yt+1 Yt+2 Y t Yt+3 Ψ1 Ψ2 Ψ3 19 2.3.3.2. Các ràng buộc đối với phân phối mô hình Vấn đề chính là phải tìm ra chuỗi p*(y|x) sao cho thỏa mãn hàm mục tiêu sau: p* (y|x) = argmaxH(y|x) (2.8) Các ràng buộc đối với mô hình được thiết lập bằng cách thống kê các thuộc tính được rút ra từ tập dữ liệu huấn luyện. Ví dụ về một thuộc tính 1 nếu y=name, x=Mister fi(x,y)= 0 nếu ngược lại Tập các thuộc tính là tập hợp các thông tin quan trọng trong dữ liệu huấn luyện. Ký hiệu kì vọng của thuộc tính f theo phân phối xác suất thực nghiệm : fE ][ˆ =∑ x,y i(x,y)(x,y) fpˆ (2.9) Ở đây p^(x,y) là phân phối thực nghiệm trong dữ liệu huấn luyện. Dữ liệu huấn luyện gồm N cặp, mỗi cặp gồm một chuỗi dữ liệu quan sát và một chuỗi nhãn D={(xi,yi)}, khi đó phân phối thực nghiệm trong dữ liệu huấn luyện được tính như sau: ),(ˆ yxp = 1/N * số lần xuất hiện đồng thời của x,y trong tập huấn luyện Kỳ vọng của thuộc tính f theo phân phối xác suất trong mô hình Ep[f] =∑ x,y i(x,y)x)*fp(x) *p(y| (2.10) Phân phối mô hình thống nhất với phân phối thực nghiệm chỉ khi kỳ vọng của mọi thuộc tính theo phân phối xác suất phải xấp xỉ bằng kì vọng của thuộc tính đó theo phân phối mô hình : fEfE pyxp ][][),(ˆ = (2.11) Từ công thức (2.11) có thể thấy rõ các ràng buộc của mô hình. 20 2.3.3.3. Nguyên lý cực đại hóa Entropy Gọi P là không gian của tất cả các phân phối xác suất điều kiện, và n là số các thuộc tính rút ra từ dữ liệu huấn luyện. P’ là tập con của P, P’ được xác định như sau: P’={ p |P∈ fEfE pp ][][ˆ = }...3,2,1{ ni∈∀ } (2.12) Tư tưởng chính của nguyên lý cực đại hóa Entropy là ta phải xác định một phân phối mô hình sao cho: phân phối mô hình phải thỏa mãn mọi ràng buộc được rút ra từ thực nghiệm, và phải gần nhất với phân phối đều. Có nghĩa là ta phải tìm phân phối mô hình p( y | x ) thỏa mãn hai điều kiện thứ nhất phải thuộc tập P’ thứ hai là nó phải làm cực đại hóa Entropy điều kiện (2.7) Hay nói cách khác khi fEfE pp ][][ˆ = và p(y | x)≥0 yx,∀ và∑ ∈ ∀= Yy xxyp 1)|( ta sẽ có (2.7) Với mỗi một thuộc tính fi ta đưa vào một thừa số langrange λi, ta định nghĩa hàm Lagrange L(p, λ) như sau: L(p, λ) = H(p)+ ( )∑ i ip ipi ][fE ][fE ˆ -*λ (2.13) Phân phối p(y | x) làm cực đại hóa độ đo Entropy H(p) và thỏa mãn n ràng buộc (2.11) cũng sẽ làm cực đại hàm L(p, λ). Từ (2.13) suy ra P(y | x) = )exp( )( 1 i i i fxZ ∑λλ (2.14) Ở đây Zλ(x) là thừa số chuẩn hóa để đảm bảo ∑ y xyp )|( =1 với mọi x: Zλ(x)=∑ ∑ ⎟⎠ ⎞⎜⎝ ⎛ y i ii fλexp (2.15) 2.3.4. Hàm tiềm năng của các mô hình CRF Bằng cách áp dụng nguyên lý cực đại hóa Entropy, Lafferty xác định hàm tiềm năng của một CRF có dạng hàm số mũ. ΨA(A|x)=exp∑ k xAfy )|(κκ (2.16) Trong đó: fk là một thuộc tính của chuỗi dữ liệu quan sát 21 yk là trọng số chỉ mức độ biểu đạt thông tin của thuộc tính fk A là đồ thị con của đồ thị vô hướng G 2.3.5. Conditional Random Fields Mô hình CRFs cho phép các quan sát trên toàn bộ X, nhờ đó chúng ta có thể sử dụng nhiều thuộc tính hơn phương pháp Hidden Markov Model. Một cách hình thức chúng ta có thể xác định được quan hệ giữa một dãy các nhãn y và một câu đầu vào x qua công thức sau. ⎟⎠ ⎞⎜⎝ ⎛ += ∑∑ ∑∑− t k t k ikkiikk xysxyytxZ xyP ),(),,(exp )( 1)|( 1 μλ (2.17) Ở đây x,y là chuỗi dữ liệu quan sát và chuỗi trạng thái tương ứng; tk(yi-1,yi,x,i): là thuộc tính của toàn bộ chuỗi quan sát và các trạng thái tại vị trí i-1, i trong chuỗi trạng thái; sk(yi,x,i): là thuộc tính của toàn bộ chuỗi quan sát và trạng thái tại vị trí i trong chuỗi trạng thái; λj, μk: là các tham số được thiết lập từ dữ liệu huấn luyện. Khi định nghĩa các thuộc tính , chúng ta xây dựng 1 chuỗi các thuộc tính b(x,i) của chuỗi dữ liệu quan sát để diễn tả vài đặc trưng nào đó của phân phối thực nghiệm của dữ liệu huấn luyện. Ví dụ : 1 nếu quan sát ở vị trí i và từ là = “Đình” b(x,i) = 0 nếu khác Mỗi một hàm mô tả sẽ nhận một giá trị của một trong số các giá trị thực b(x,i) là trạng thái hiện tại( nếu trong trường hợp hàm trạng thái ) hoặc là trạng thái trước và trạng thái hiện tại (trong trường hợp là hàm dịch chuyển) nhận giá trị riêng. Do đó toàn bộ hàm mô tả có giá trị thực. Hàm trạng thái sk(yi,x,i) dùng để xác định định danh của trạng thái Trong bài toán trích chọn thông tin nhà đất thì ví dụ một hàm trạng thái như sau: 1 nếu xi= “chuỗi các số” và yi =B-DD si = 0 nếu ngược lại Hàm dịch chuyển giúp thêm vào mối quan hệ giữa một nhãn và các nhãn liền kệ với nó. 22 1 nếu xi-1= “Mỹ”, xi= “ Đình” và yi-1=B_DC, yi=I_DC ti= 0 nếu ngược lại. Ở đó Z(x) là thừa số chuẩn hóa. Và được tính theo công thức sau: Z(x)=∑ ∑∑∑∑ ⎟⎠ ⎞⎜⎝ ⎛ +− y i k ikkik t k k xysxyiyt ),(),,exp 1( μλ (2.18) θ(λ1 ,λ2…..,μ1, μ2) là các véctơ tham số của mô hình . θ sẽ được ước lượng giá trị trong phần tiếp theo. Chú ý rằng đối với các công thức (2.17) và (2.18) ta có thể viết một cách đơn giản như sau: sk(yi,x,i)= sk(yi-1, yi,x,i) và Fj(y,x)= ∑ = − n i ii ixyyfi 1 1 ),,,( . Ở đó fj(yi-1,yi,x,i) là hàm trạng thái sk(yi-1, yi,x,i) hoặc hàm dich chuyển tk(yi-1, yi,x,i). Điều này cho ta tính được xác suất của nhãn y khi biết chuỗi quan sát x: P(y|x,λ) = )( 1 xZ exp(∑ j jj xyF ),(λ ) (2.19) 2.3.6. So sánh với các mô hình khác Bản chất của phân phối toàn cục của CRF giúp cho các mô hình này tránh được vấn đề label alias . Qua quá trình thực nghiệm cho thấy tỉ lệ lỗi của CRF là thấp hơn cả so với MEMM và HMM Với 2000 mẫu dữ liệu huấn luyện và 500 mẫu test kết quả là tỷ lệ lỗi của CRF là 4.6%, của MEMM tỷ lệ lỗi là 42% [14]. 23 Hình 12. Tỷ lệ lỗi của CRF so với các mô hình học máy khác 2.4. TỔNG KẾT CHƯƠNG Chương này giới thiệu những vấn đề cơ bản về CRF : định nghĩa CRF, việc gán nhãn cho dữ liệu dạng chuỗi, hàm tiềm năng cho các mô hình CRF, chứng tỏ được rằng CRF giải quyết được vấn đề label alias. Qua đó thấy được rằng CRF có khả năng xử lý dữ liệu tốt hơn rất nhiều so với các mô hình khác như HMM hay MEMM. Dữ liệu tăng theo chiều tăng của mũi tên 24 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 ++ Hai vấn đề quan trọng cần phải được đề cập đến khi nghiên cứu về mô hình CRF [8] đó là: thứ nhất khi đưa chuỗi nhãn y và một chuỗi quan sát x làm thế nào tìm ra một tham số λ của CRF để làm cực đại hóa xác suất p(y|x, λ) vấn đề này tạm gọi là huấn luyện (training). Thứ hai khi đưa ra một chuỗi quan xát x và một tham số λ làm thế nào để tìm được chuỗi các nhãn y phù hợp nhất tạm gọi vấn đề này quy nạp (inference). Ở chương này sẽ đi giải quyết từng vấn đề nêu ở trên. Đồng thời cũng giới thiệu được công cụ CRF++, một công cụ xây dựng dựa trên mô hình CRF. 3.1. THUẬT TOÁN GÁN NHÃN CHO DỮ LIỆU DẠNG CHUỖI Mục đích của việc gán nhãn là làm sao tìm được chuỗi y* sao cho cực đại hóa xác suất p(y|x, λ). Hay nói cách khác mục đích của thuật toán là làm sao tìm ra chuỗi nhãn phù hợp nhất với chuỗi dữ liệu quan sát. Với bài toán trích chọn thông tin nhà đất thì việc sử dụng thuật toán Virterbi đóng vai trò quan trọng. Thuật toán làm làm cho quá trình trích chọn chính xác hơn. Thay việc tính xác suất tổng các xác suất ta chỉ cần tính giá trị lớn nhất của xác suất dịch chuyển. Khi đó chuỗi trạng thái y* mô tả tốt nhất cho chuỗi dữ liệu quan sát x là nghiệm của phương trình. y*=argmax{p(y|x)} (3.1) =argmaxyexp )⎟⎠ ⎞⎜⎝ ⎛ + ∑ ∑∑ ∑ − i k ikkiik i k k xysxyyt ),(),,1( μλ =argmaxy )⎟⎠ ⎞⎜⎝ ⎛ + ∑∑∑∑ − i k ikkiik i k k xysxyyt ),(),,1( μλ Vì Z(x) không phụ thuộc vào nhãn riêng biệt x và số mũ là một hàm đơn điệu. Nên ta bỏ qua Z(x) trong công thức (3.1). Để tìm được y*, thỏa mãn (3.1) thì gặp phải một khó khăn trong thời gian tính toán, vì thời gian tính toán là hàm mũ. 25 Chuỗi y* được xác đinh bằng thuật toán Virterbi [17]. Định nghĩa ∂i(y) là xác suất của chuỗi trạng thái độ dài i kết thúc bởi trạng thái y và có xác suất lớn nhất biết chuỗi quan sát là x. Trong đó ∂1(yk) là xác suất đầu tiên của mỗi trạng thái yk. Ta định nghĩa )(yΨ i để ghi lại nhãn thứ i-1 có xác suất lớn nhất. Thuật toán dừng khi )(yΨ i có giá trị là 1. Thuật toán Viterbi có thể được mô tả qua các bước sau: ¾ Bước 1: Khởi tạo ∂1(yk) =∑ k kk xys ),(μ Yy∈∀ ¾ Bước 2: Đệ quy ∂i+1(yk) = Yyy,x)xyyt kk kk ∈∀⎟⎠ ⎞⎜⎝ ⎛ ++∂ ∑∑ (s),,'()(y' max kki μλ Yyy,x)xyyty kk kki ∈∀⎟⎠ ⎞⎜⎝ ⎛ ++∂= ∑∑+ (s),,'()(y' maxarg)( kki1 μλψ ¾ Bước 3: Dừng Đệ quy dừng khi i=n= chiều dài của chuỗi Để có thể tìm được y* bằng cách sử dụng kỹ thuật backtracking. Khi đó y* sẽ là một dàng buộc, Những ràng buộc trong công thức (3.4) sẽ được chuyển qua ràng buộc bởi các chuỗi nhãn con C được định nghĩa như sau C=. Ràng buộc sẽ được viết đệ quy lại như sau: 1tkjkik yy if x)),y,(yM*)(y(max +=∂ i ∂t+1(yk)= 0 nếu ngược lại Trong ngữ cảnh của chúng ta thì ràng buộc C tương ứng với các chuỗi dữ liệu quan sát được chính xác bởi người sử dụng 3.2. XÁC SUẤT CRF ĐƯỢC TÍNH NHƯ MỘT MA TRẬN Để việc tính p(y|x, λ) – xác suất của chuỗi nhãn y khi biết chuỗi quan sát x một cách hiệu quả ta có thể tính được thông qua một ma trận [14] cách tính như sau: Ở chuỗi các nhãn ta thêm vào hai trạng thái start state và end state tương đương với nó là y0 và yn+1. Ta định nghĩa n+1 ma trận {Mi(x) có cỡ | γγ × | với i=1,2..n ; γ là 26 cạnh nỗi các nhãn y’ tới y}. Khi đó các phần tử trong ma trận được tính theo công thức sau: Mi(y’,y|x)=exp ⎟⎠ ⎞⎜⎝ ⎛ +∑∑∑∑ − t t ikkiik t k k xysxyyt ),(),,1( μλ Khi đó xác suất của chuỗi nhãn y khi biết chuỗi quan sát x có thể được viết như kết quả xấp xỉ của các phần tử của n+1 ma trận cho từng cặp chuỗi p(y|x, λ)= ∏+ = − 1 1 1 ),|( )( 1 n i ii xyyMi xZ Trong đó Z(x) được tính như sau Z(x)= endstart n i i xM , 1 1 )( ⎥⎦ ⎤⎢⎣ ⎡∏+ = 3.3. ƯỚC LƯỢNG THAM SỐ CHO MÔ HÌNH CRF Kỹ thuật được sử dụng để đánh giá tham số cho một mô hình CRF [11] là làm cực đại hóa độ đo likelihood giữa phân phối mô hình và phân phối thực nghiệm. Giả sử dữ liệu huấn luyện gồm cặp một chuỗi quan sát và một chuỗi trạng thái {x(k),y(k)} Nk ...1=∀ . Độ đo lilelihood giữa tập huấn luyện và mô hình điều kiện tương ứng p(y|x,θ) là: L(θ)= ),(ˆ , ),|( yxp yx xyp∏ θ (2.20) Ở đây θ(λ1,λ2,...μ1,μ2) là các tham số mô hình và ),(ˆ yxp là phân phối thực nghiệm đồng thời của x, y trong tập huấn luyện. Nguyên lý cực đại likelihood: các tham số tốt nhất của mô hình là các tham số làm cực đại hàm likehood. θML=argmax θL(θ) (2.21) θML đảm bảo những dữ liệu quan sát được trong tập huấn luyện sẽ nhận xác suất cao trong mô hình. Để tính θ trong công thức (2.20 ) rất khó khăn ta lấy logarit 2 vế ( gọi tắt là log-likelihood ): l(θ) = ∑ yx , ))x,|y)log(p(y(x,pˆ θ (2.22) 27 Vì hàm logarit là hàm đơn điệu nên việc làm này không thay đổi giá trị của θ được chọn . Thay p(y|x, θ) của mô hình CRF vào công thức (2.14): l(θ)= ∑∑ ∑∑ −⎥⎦ ⎤⎢⎣ ⎡ + = + = xyx n i Z(x)*pst logˆ** y)(x,pˆ , 1 1n 1i μλ (2.23) Ở đây λ(λ1, λ2…λn) và μ(μ1, μ2.. μn) là các vector tham số của mô hình, t là vector các thuộc tính chuyển ; t là các vector thuộc tính chuyển (t1(yi-1,yi,x) ,t2(yi-1,yi,x)..); s là vector các thuộc tính trạng thái (s1(yi,x) , s2(yi,x) Hàm log-likelihood cho mô hình CRF là một hàm lõm và trơn trong toàn bộ không gian của tham số. Đạo hàm (2.23) theo λj ta được j l λ θ ∂ ∂ )( = ∑∑ ∑ ∑ = − = n i iij yx i,i-j xyyt(x)p(y|x,θp,x)y(y(x,yp 1 1 , n 1i x 1 ),,()ˆ-t)ˆ = [ ] [ ]kxypkyxp tEtE ),|(),(ˆ θ= (2.24) Ở đó ),(ˆ yxp là phân phối thực nghiệm đồng thời của x,y trong tập huấn luyện Việc thiết lập phương trình trên bằng 0 tương đương với việc đưa ra một ràng buộc cho mô hình: giá trị trung bình của tk theo phân phối ),|()(ˆ θxypxp bằng giá trị trung bình của tk theo phân phối thực nghiệm. Thực chất bài toán ước lượng tham số cho một mô hình CRF là bài toán tìm cực đại của hàm log-kikelihood. Ở đây chúng ta sử dụng phương pháp lặp để tìm ra vector θ làm cực đại log-likelihood. Mục đích của phương pháp lặp là luôn cập nhất các tham số theo công thức sau: λk λk+ δλk μk μk + δμk Ở đây các giá trị δμk,, δλk được chọn sao cho giá trị của hàm log-likelihood gần với cực đại hơn. Trong phương pháp lặp ta tìm ra một cách thức cập nhật tham số mô hình sao cho log-likelihood nhận giá trị càng gần với cực đại càng tốt. Việc cập nhật tham số sẽ dừng khi hàm log-likelihood hội tụ. ISS cập nhật tham số δλk theo cách sau [ ]kfEˆ = ),,(),(ˆ 11 1, xyytyxp ii n i k yx − + = ∑∑ 28 = ),(1 1 1, ),,()|()(ˆ yxTii n i k yx kexyytxypxp λ∂− + = ∑∑ Ở đó T(x,y)= ∑∑∑∑ +− i k ikiik i k xysxyyt ),(),,1( Việc cập nhật δμk làm tương tự. Tuy nhiên việc tính toán về phải của công thức trên là cả một vấn đề lớn bởi vì T(x,y) là biến toàn cục của x,y. Dưới đây trình bày hai thuật toán được dựa trên sự cải tiến của thuật toán Improved Iterative Scaling- IIS. 3.3.1. Thuật toán S Để giải quyết vấn đề trên ta sử dụng hàm yếu (slack feature) [14] được định nghĩa như sau: s(x,y)= S - ( ) ∑ ∑∑∑ +− i k iki i k k xysxyiyt ),(,,1 Trong đó S là một hằng số để s(x(i),y) ≥0 cho tất cả các nhãn y và tất cả các vector của chuỗi quan sát x(i) trong tập huấn luyện. Đặc tính s là toàn cục tức là nó không tương ứng với một đỉnh hoặc một cạnh bất kỳ nào của đồ thị vô hướng. Với mỗi giá trị i= 0,…, n+1. Ta định nghĩa một forward vector )(xiα như sau: =)|(0 xyα 1 nếu y=start 0 nếu ngược lại Quy lạp )(xiα = )(1 xi −α Mi(x) Tương tự ta cũng xác định backward vector )(xiβ được định nghĩa như sau: 1 nếu stop )|(1 xyn +β = 0 nếu ngược lại Và )(xiβ T =Mi+1(x) )(1 xn +β . Các tham số được cập nhật theo công thức sau: 29 δλk= S 1 log )( )(ˆ k k fE fE δμk= )( )(ˆ log1 k k sE sE S Ở đó : Efk=∑ ∑∑+ =x n i yy k xyytxp 1 1 ,' ),,'()(ˆ * )( )|()|,'()|'( 0 1 xZ xyxyyMxy iii βα − Esk=∑ ∑∑ =x n i y k xysxp 1 ),()(ˆ )( )|()|'( 0 1 xZ xyxy ii βα − Tốc độ hội tụ của thuật toán S phụ thuộc vào độ lớn của S, độ lớn của S tỷ lệ nghịch với số lượng các bước cập nhật. 3.3.2. Thuật toán T Thuật toán đưa ra xấp xỉ T(x,y) ≈ T(x) = maxyT(x,y) Ta định nghĩa ak, t là kỳ vọng của tk bk,t là kỳ vọng của sk đưa ra T(x) = m. Khi đó ta cập nhật tham số là kμδ = log kγ , δλk =log kβ . Ở đó kγ và kβ được định nghĩa trong đa thức sau: β mk T i tk∑ = max 0 ,α = kfEˆ , γ mk T i tkb∑ = max 0 , = skE Để đơn giản ta chỉ xét trường hợp cập nhật tham số λk. Đưa ra hai tham số θ =(λ1, λ2,..) và θ’=( λ1+δλ1, λ2+δλ2.....) . Ta định nghĩa một hàm phụ ),'( θθΑ như sau: )(θl - )'(θl = )|( )|( log),(ˆ ' , xyp xyp yxp yx θ θ∑ = ( .' θθ − ) tEˆ - )(ˆ xp x ∑ log )( )(' xZ xZ θθ ≥ ( .' θθ − ) tEˆ - )(ˆ xp x ∑ )( )(' xZ xZ θθ 30 = δλ . tEˆ -∑ y exyp )|(θ δλ.t(x,y) ≥ δλ . tEˆ - ))(exp()( ),()|()( ,, ^ xT xT yxfkxypxp k kyx δλθ∑ = ),'( θθΑ Nhận xét rằng l(θ’) - l(θ) ≥ ),'( θθΑ nên δλi làm cực đại ),'( θθΑ cũng sẽ làm cực đại gia số của hàm log-likelihood. 3.4. CÔNG CỤ CRF++ TOOLKIT 3.4.1. Giới thiệu CRF ++ là một công cụ cài đặt mô hình CRF và được phân phối dưới dạng mã nguồn mở có thể dùng để phân đoạn và gán nhãn dữ liệu tuần tự [19]. CRF++ được thiết kế cho cùng một mục đích phổ dụng có thể ứng dụng trong những bài toán xử lý ngôn ngữ tự nhiên như nhận dạng thực thể tên, trích chọn thông tin và đóng khung văn bản. Hệ thống được hoạt động theo phương pháp học nửa giám sát được thực hiện gồm các bước sau: Bước 1: Tạo bộ dữ liệu huấn luyện bé. Bước này được thực hiện bằng tay Bước 2: Sử dụng mô hình CRFs để huấn luyện trên tập dữ liệu này. Bước 3: Tạo tập test và sử dụng CRFs để gán nhãn Bước 4: Bộ dữ liệu mới được sinh ra bằng cách bổ sung các nhãn cho tập dữ liệu test 31 CRF++ được chia làm 2 modulo chính có thể mô tả như hình (13) như sau: Hình 13. Mô hình hoạt động của CRF++ 3.4.2. Tính năng - Có thể định nghĩa lại các tính năng đã có, ta có thể tùy biến để thêm các đặc trưng mới phù hợp với bài toán cụ thể. - Viết bằng C++, là phần mềm mã nguồn mở - Bộ nhớ nhỏ sử dụng trong cả kiểm tra và phân tích - Có thể đưa ra xác suất lề cho tất cả những đầu vào. 3.4.3. Cài đặt và cách sử dụng 3.4.3.1 Cài đặt ¾ Chuyển vào thư mục chứa công cụ CRF++ ¾ Dùng lênh chmod 777 ./configure ¾ make clean && make 3.4.3.2. File định dạng huấn luyện và test Để sử dụng được CRF++ ta cần phải có 2 file dữ liệu, 1 file dùng cho quá trình huấn luyện, file còn lại dùng cho quá trình kiểm tra. Cả file huấn luyện và kiểm tra cần Dữ liệu CRFs Model file Decoding Câu tiếng Việt Output Giai đoạn huấn luyện Giai đoạn thực hiện 32 có 1 định dạng riêng của CRF++ để nó có thể làm việc được. Thông thường file huấn luyện và file kiểm tra chứa đựng rất nhiều từ tố. Mỗi từ tố phải viết trên một dòng, Ngoài từ tố ra còn có các cột chứa các thông tin khác dùng để mô tả từ tố chẳng hạn như là từ loại của từ tố và cột cuối cùng chứa nhãn của từ tố. Để định nghĩa từ tố phụ thuộc vào từng công việc, trong hầu hết các trường hợp điển hình thì chúng là các từ. Mỗi một từ tố ở một dòng, các cột được phân chia bởi các khoảng trắng. Trình tự các từ tố tạo thành một câu. Một dòng trắng để phân biệt giữa các câu. Dưới đây là một ví dụ về file huấn luyện. Với cột thứ nhất là bản thân từ đó, cột thứ hai là từ loại và cột cuối cùng là nhãn cần gán. Input: Data He PRP B-NP reckons VBZ B-VP the DT B-NP current JJ I-NP account NN I-NP deficit NN I-NP will MD B-VP narrow VB I-VP to TO B-PP only RB B-NP # # I-NP 1.8 CD I-NP billion CD I-NP in IN B-PP September NNP B-NP . . O He PRP B-NP reckons VBZ B-VP .. 3.4.3.3. Template type File này mô tả những đặc trưng sẽ sử dụng khi huấn luyện và kiểm tra. Mỗi một dòng trong trong file template chỉ ra một template, mỗi một template có dạng như sau %x[row,col] dùng để định nghĩa một từ trong dữ liệu đầu vào. File template được xây dựng tùy vào từng bài toán cụ thể và tùy vào file huấn luyện và file kiểm tra. Ví dụ với dữ liệu đầu vào như sau thì file template sẽ được xây dựng như sau: 33 Dữ liệu đầu vào He PRP B-NP reckons VBZ B-VP the DT B-NP << CURRENT TOKEN current JJ I-NP account NN I-NP Template Từ tố tương ứng %x[0,0] The %x[0,1] DT %x[-1,0] Reckons %x[-2,1] PRP %x[0,0]%x[0,1] The/DT Có hai loại template là Unigram template và Bigramtemplate • Unigram template Với loại này khi đưa 1 template CRF ++ sẽ tự động tạo ra các hàm đặc trưng func1 = if (output = B-DT and feature="U01:DT") return 1 else return 0 func2 = if (output = I-DT and feature="U01:DT") return 1 else return 0 func3 = if (output = O and feature="U01:DT") return 1 else return 0 ... Số lượng hàm tạo ra bởi một template là ( L * N) L : số lượng output N: số lượng chuỗi duy nhất được mở rộng từ template dược chỉ ra. • Bigram template Với template này ,sự liên kết giữa từ tố hiện tại (current token) và từ tố trước đó (previous output token) được tự động tạo ra Với loại này tạo ra (L *L *N) (N là số lượng các đặc trưng riêng biệt được tạo ra) đặc trưng khác nhau do vậy có thể không hiệu quả trong huấn luyện và kiểm tra. 34 3.4.4. Huấn luyện và kiểm tra Sau khi chuẩn bị toàn bộ các file train, file test, file template ta tiến hành huấn luyện và test như sau ¾ Huấn luyện (training) Để huấn luyện các file ta sử dụng lệnh crf_learn với cú pháp sau: % crf_learn template_file train_file model_file Ở đó : Lệnh crf_learn tạo ra mô hình huấn luyện trong file model_file Kết quả của lệnh crf_learn: iter: Số lượng lặp được xử lý terr: Tỷ lệ lỗi đối với các thẻ ( được tính bằng số lượng thẻ lỗi/ tổng số thẻ ) serr: Tỷ lệ lỗi đối với câu ( được tính bằng số câu lỗi /tổng số câu ) obj: Giá trị của đối tượng hiện tại. Khi giá trị này hội tụ tại một điểm cố định. CRF ++ dừng lặp 35 Bảng 2. Bảng các tham số huấn luyện Tham số Giá trị mặc định Ý nghĩa -a CRF-L2 hoặc CRF-L1 CRF-L2 Tham số này dùng để thay đổi thuật toán mặc định của CRF ++ . Thông thường thì L2 thực hiện tốt hơn không đáng kể so với L1, trong khi số lường các đặc tính L1 là nhỏ hơn một cách đáng kể so với L2 -c float: Cùng với tùy chọn này, có thể thay đổi nhiều tham số cho CRFs -f NUM 1 Chỉ có các thuộc tính có tần suất xuất hiện lớn hơn giá trị này thì mới được tích hợp vào mô hình CRF . -p NUM Nếu máy tính của bạn có nhiều CPU, giúp cho việc huấn luyện nhanh hơn bằng cách sử dụng đa luồng. NUM là số lượng các luồng ¾ Kiểm tra (testing) Để kiểm tra dữ liệu sau khi huấn luyện sử dụng lệnh crf_test với cú pháp như sau: % crf_test -m model_file test_files ... Model_file là file do crf_learn tao ra. Trong khi test không cần tạo ra template_file bởi vì model file có thông tin giống như file template . Test_file là kiểm tra dữ liệu bạn muốn gán thẻ theo trình tự. File này có định dạng giống như file traning được xây dựng ở trên. 36 Bảng 3. Bảng các tham số của lệnh crf_test Tham số Giá trị mặc định Ý nghĩa -v level 0 Tùy chọn này đưa ra một số thông tin chi tiết từ CRF++bằng cách tăng cấp độ của level N best ouput Đưa ra N kết quả được sắp xếp theo xắc suất điều kiện của CRF++ 3.5. TỔNG KẾT CHƯƠNG Trong chương này đã nêu ra hai vấn đề cơ bản trong mô hình CRF. Có rất nhiều phương pháp sử dụng để giải quyết hai vấn đề đó. Trong phần này đã nêu ra hai hướng giải quyết cơ bản và hiệu quả nhất. Đó thuật toán Virterbi và hai thuật toán T và thuật toán S. Cả hai thuật toán đều được cải tiến từ thuật toán IIS. Chương này cũng giới thiệu được công cụ CRF++ toolkit, một công cụ có nhiều ứng dụng trong xử lý ngôn ngữ tự nhiên. 37 Chương 4. ỨNG DỤNG CRF VÀO BÀI TOÁN TRÍCH CHỌN THÔNG TIN NHÀ ĐẤT Một hệ thống hữu ích dùng để xử lý tiếng Việt là rất quan trọng. Ví dụ như bài toán nhận biết các loại thực thể là một bài toán cơ bản trong trích chọn thông tin và xử lý ngôn ngữ tự nhiên. Từ việc nhận biết các loại thực thể ta có thể rút trích ra những thông tin cần thiết tùy thuộc vào mục đích riêng. Trong chương này sẽ ứng dụng mô hình CRF đã nói ở trên vào bài toán trích chọn thông tin nhà đất. 4.1. MÔ HÌNH HÓA BÀI TOÁN TRÍCH CHỌN THÔNG TIN NHÀ ĐẤT Đối với bất kỳ một văn bản nào thì việc hiểu nhanh văn bản và tóm tắt được nội dung chính là rất cần thiết. Cũng như vậy trong bất kỳ một bản tin nhà đất nào kể cả người bán và người mua đều quan tâm đến những vấn đề cơ bản nhất liên quan đến nhà, hoặc đất cần bán hoặc cần mua. Với tư tưởng vậy với một thông tin nhà đất những yếu tố chúng ta cần quan tâm là: Vị trí của nhà hoặc đất như thế nào, diện tích?, giá bán?, loại nhà nào?, địa chỉ liên hệ với chủ sở hữu?. Với tất cả các thông tin trên có thể hiểu đầy đủ được về thông tin về ngôi nhà cần bán hoặc cần mua. Nhiệm vụ của bài toán trích chọn thông tin nhà đất là làm sao có thể rút trích những thông tin được liệt kê trong bảng 4 như sau: Bảng 4. Bảng các thông tin cần trích chọn Tên Chú thích DC Địa chỉ DT Diện tích DD Di động GB Giá bán LN Loại nhà Vấn đề đặt ra là với một lượng thông tin nhỏ thì ta có thể dễ dàng tìm ra được các thông tin đó. Nhưng với một dữ liệu lớn thì vấn đề rất khó khăn. Chính vì vậy và việc 38 ứng dụng một mô hình có thể “tự học” để có thể tìm ra những thông tin đó là rất cần thiết. 4.1.1. Xử lý dữ liệu đầu vào Dữ liệu ban đầu đầu được tiền xử lý trong win (được gán nhãn bằng tay trong win). Sau đó, chuyển từ dạng mã hóa UTF-8 sang tiếng Việt không dấu. Có thể mô hình hóa như hình 14 sau: Hình 14. Mô hình xử lý dữ liệu của bài toán trích chọn nhà đất Từ bản tin nhà về nhà đất sau khi tải về sẽ được gán nhãn, vì hiện tại CRF++ không hỗ trợ UNICODE nên khóa luận tạm thời chọn giải pháp là chuyển sang tiếng Việt không dấu. Điều này có thể làm giảm chất lượng của hệ thống nhận dạng do thông tin ngữ nghĩa của đoạn văn bị mất đi, tuy nhiên hướng phát triển tương lai tác giả sẽ đề xuất một cách tốt hơn để tránh mất thông tin trong quá trình chuyển đổi Do không có sẵn các công cụ xử lý cho tiếng Việt, như công cụ gán nhãn từ loại nên trong bài toán trích chọn thông tin nhà đất file huấn luyện và file kiểm tra chỉ sử dụng duy nhất chính từ tố đó, do vậy trong file huấn luyện và file kiểm tra chỉ có hai thông là từ và nhãn do vậy 2 file này chỉ có hai cột, cột thứ nhất chứa từ là chính từ đó và cột thứ hai là nhãn của loại từ. Với các từ tố không liên quan đến các thông tin trích chọn thì được gán nhãn bằng nhãn OTH (other): Dữ liệu tiếng Việt Dữ liệu được gán nhãn Dữ liệu được chuyển thành tiếng Việt không dấu 39 Ví dụ một đoạn dữ liệu trong file huấn luyện Cần OTH bán OTH hai OTH lô OTH đất OTH TT9 B-DC Văn I-DC Phú I-DC mặt OTH đuờng B-DC Lê I-DC Trọng I-DC Tốn I-DC , OTH diện OTH tích OTH 90m2 B-DT , OTH mặt OTH tiền OTH 4.2. MÔI TRƯỜNG THỰC NGHIỆM 4.2.1. Phần cứng Máy Core 2 Duo, chip 512 MHz, Ram 1GB, trong máy có bộ biên dịch gcc phiên bản >3.00. Dùng máy ảo vimware chạy hệ điều hành Linux Redhat Enterprise 5.0 4.2.2. Phần Mềm CRF ++ toolkit là một CRF Framework cho các bài toán phân đoạn và gán nhãn giá trị tuần tự. Trong phần này, sử dụng một ứng dụng của CRF vào việc trích chọn thông tin nhà đất. Sử dụng phiên bản CRF++toolkit version 0.51 [21]. 4.2.3. Dữ liệu thực nghiệm Dữ liệu thực nghiệm gồm khoảng 300 bản tin lĩnh vực nhà đất. Nội dung về bản tin nhà đất được lấy từ các website sau: các website này có các định dạng và cách trình bày khác nhau, do vậy cần phải qua bước xử lý như đã trình bày ở trên. 40 Trong đó file huấn luyện khoảng 300 câu, và file kiểm tra khoảng 200 câu. 4.2.3.1. Lần thử nghiệm thứ nhất Trong bài toán của mình, tôi đã xây dựng file mẫu với kiểu định dạng Unigram trọn như file template sau U00:%x[-2,0]: (xét từ trước hai vị trí và nhãn hiện tại) U01:%x[-1,0]: (xét từ trước một vị trí hiện tại ) U02:%x[0,0]: (từ hiện tại) U03:%x[1,0]: (từ sau vị trí hiện tại) U04:%x[2,0]: (từ sau 2 vị trí) U05:%x[-1,0] / %x[0,0]: (Từ trước và từ hiện tại) U06:%x[0,0]/%x[1,0]: (Từ sau và từ hiện tại) Với các khuôn mẫu này sẽ tạo ra các hàm đặc trưng để cho mô hình có thể “tự học” Ví dụ như func1= if(output= B-DC ) return 1 else return 0; func2=if(output=I-DC ) return 1 else return 0; 4.2.3.2. Lần thử nghiệm thứ hai Trong lần thử nghiệm đầu tiên, toàn bộ hệ thống làm việc đều do mô hình tự học. Như chúng ta đã biết những thông tin cần rút trích trong bài toán trích chọn thông tin nhà đất là địa chỉ, diện tích, loại nhà, di động, giá bán. Với các thông tin trích chọn này ta có thể mô tả như sau: Đối với thông tin về số di động sẽ bao gồm một chuỗi toàn những số từ 0 đến 9 ví dụ 01678558976, đối với địa chỉ, vị trí của nhà hoặc đất cần bán hoặc cần mua thì là một danh từ chỉ địa điểm và thường viết hoa ký tự đầu tiên ví dụ như Mỹ Đình- Hà Nội. Đối với thông tin giá bán thường thì giá bán sẽ là một chuỗi có cả số và có dấu chấm hoặc dấu phảy ví dụ như 1.2 tỷ hoặc 1,2 tỷ. Từ những mô tả trên trong lần thử nghiệm thứ hai này, tôi sẽ thêm những tính năng mới mô tả cho những thông tin cần rút trích trên, giúp cho quá trình tự học của mô hình rút trích được tốt nhất. 41 Xét từ trước hai vị trí và nhãn hiện tại Xét từ trước một vị trí hiện tại Từ sau vị trí hiện tại Từ sau 2 vị trí Từ trước và từ hiện tại Từ sau và từ hiện tại Từ hiện tại có toàn số hay không? Từ hiện tại có chữ đầu tiên là chữ hoa hay không? Từ hiện tại có toàn chữ thường hay không? Từ hiện tại có gồm các ký tự như “.” hoặc “,”. Với những đặc trưng của dữ liệu bài toán như vậy mình có thể xây dựng thêm các feature fk trong công thức (2.16) mô tả cho dữ liệu của bài toán trích chọn thông tin nhà đất như sau: Hàm thứ nhất function InitCap() mô tả cho thông tin địa chỉ: Như đã biết địa chỉ thường viết hoa chữ cái đầu tiên, hàm này có chức năng nếu chữ cái đầu tiên của một từ tố là chữ hoa thì sẽ trả về một giá trị nào đó còn nếu không trả về một giá trị khác. Có thể mô tả như sau: 1 Nếu chữ cái đầu tiên của từ quan sát được là chữ hoa fk= InitCap() = 0 nếu ngược lại Tương tự như vậy ta xây dựng các hàm ContainAllDigit(): Nếu chuỗi quan sát được là một chuỗi số thì có khả năng đây là số điện thoại. 1 Nếu dữ liệu quan sát là toàn số fk= ContainAllDigit() = 0 nếu ngược lại 42 Hàm thứ ba DigitandComma() hàm này xây dựng để mô tả đặc trưng của thông tin liên quan đến giá bán, ở đây giá bán thường được biểu diễn bằng một số trong đó có thể chứa các dấu phân cách ví dụ: 2,3 hoặc 1.55. Nếu dữ liệu quan sát là con số có dấu phân cách là dấu phảy hoặc dấu chấm thì rất có thể đó là giá bán của ngôi nhà hoặc mảnh đất. 1 nếu dữ liệu quan sát là số hoặc số dấu chấm hoặc phảy fk= DigitandComma() = 0 nếu ngược lại Ngoài ra xây dựng dựng hàm AllLow() để kiểm tra xem dữ liệu quan sát được có hoàn toàn là chữ viết thường hay không. Hàm này được xây dựng như ba hàm trên nó sẽ mô tả cho những dữ liệu khác ví dụ như ngoài những thông tin liên quan đến bài toán rút trích như địa chỉ, diện tích, số điện thoại, giá bán thì các dữ liệu khác sẽ được mô tả trong hàm này. 1 nếu từ hiện tại là hoàn toàn chữ thường fk= AllLow() = 0 nếu ngược lại 4.2.3.3. Kết quả và đánh giá Để kiểm nghiệm công cụ đã sử dụng khoảng 500 câu trong file huấn luyện và 200 câu test. Để đánh giá kết quả ta đánh giá thông qua độ chính xác (precision), độ hồi tưởng (recall), và F1 được xác định như sau: # số lượng nhãn chính xác Độ chính xác = # tổng số nhãn cần gán # số lượng nhãn chính xác Độ hồi tưởng = # tổng số nhãn được gán trong tập test 43 Bảng kết quả thu được với sử dụng các mẫu đặc trưng thứ nhất: Bảng 4. Bảng kết quả lần test thứ nhất Nhãn Độ chính xác Độ hồi tưởng F1 DD 72.36% 83,18% 77.39% GB 51.72% 72.82% 60.48% DT 60.21% 69.70% 64.61% DC 27.87% 57.63% 37.57% LN 41.54% 69.23% 51.92% Bảng kết quả thu được với mẫu đặt trưng thứ hai: Bảng 5. Bảng kết quả lần test thứ hai Nhãn Độ chính xác Độ hồi tưởng F1 DD 72.36% 91.75% 80.91% GB 54.48% 71.17% 61.72% DT 73.30% 76.50% 74.87% DC 31.15% 66.09% 42.34% LN 32.31% 67.74% 43.75% 2*độ chính xác* độ hồi tưởng F1 = Độ chính xác +độ hồi tưởng 44 Đồ thị sau sẽ diễn ta đầy đủ cho mức chính xác của công cụ. Chứng tỏ đây là một công cụ hữu ích cho việc trích chọn thông tin 0.00% 10.00% 20.00% 30.00% 40.00% 50.00% 60.00% 70.00% 80.00% DC GB DD DT LN Thông tin trích chọn Đ ộ ch ín h xá c lần thử nghiệm thứ hai lần thử nghiệm thứ nhất Hình 15. Biểu đồ thể hiện sự tương quan giữa hai lần kiểm tra 4.3. HẠN CHẾ VÀ HƯỚNG ĐI CHO TƯƠNG LAI Do là bài toán trích chọn thông tin trong tiếng Việt, nhưng với môi trường Linux, CRF++ toolkit thì không hỗ trợ UNICODE. Do vậy việc chuyển tiếng Việt về tiếng Việt không dấu đã phần nào làm mất đi phần ngữ nghĩa của văn bản. Do vậy sẽ ảnh hưởng đến độ chính xác của bài toán. Ngoài ra do dữ liệu thực nghiệm vẫn còn ít, nên cũng ảnh hưởng đến kết quả thử nghiệm. Đối với các bài toán trích chọn như trên thì việc viết các đặc tính (feature) giúp hệ thống có thể tự học tốt nhất thì sẽ mang lại hiệu quả cao. Với cách đó có thể thêm các thông tin mô tả các từ tố trong file huấn luyện. Ví dụ nếu có thêm công cụ gán nhãn từ loại thì ta có thêm vào một cột trong file huấn luyện mô ta cho từ loại cần trích chọn, ví dụ như các thông tin về địa chỉ thì là từ loại danh từ (DT) như ví dụ ở dưới: Từ DT B-DC Liêm DT I-DC - DAU OTH Ha DT B-DC Nội DT I-DC 45 Việc bổ sung thêm các thông tin này cộng với việc thay đổi các hàm đặc trưng sẽ cung cấp nhiều thông tin cho CRF++, do đó chất lượng trích chọn sẽ cải tiến hơn rất là nhiều. Một hướng phát triển khác trong tương lai là trích chọn thêm các thông tin khác liên quan đến thông tin nhà đất chẳng hạn như: hướng nhà, số phòng.... 4.4. TỔNG KẾT CHƯƠNG Chương này giới thiệu bài toán trích chọn thông tin nhà đất sử dụng mô hình CRF và sử dụng công cụ CRF++ để thực hiện. Với những cải tiến công cụ ta thấy một kết quả đáng ghi nhận trong việc ứng dụng công cụ CRF++ vào bài toán của mình. Từ bảng kết quả thu được cũng cho thấy công cụ khá hữu ích trong việc xử lý tiếng Việt. Và đưa ra một tương lai trong việc xử lý ngôn ngữ tiếng Việt. 46 KẾT LUẬN Tin học là một công cụ đắc lực có ứng dụng nhiều trong các lĩnh vực khác nhau. Vấn đề đặt ra là làm sao cho máy có thể tự động “học” mà không cần có sự can thiệp nhiều của con người đây là vấn đề rất quan trọng của CNTT. Một mô hình có thể phần nào đáp ứng được công việc này đó là Conditional Random Field. Với mô hình này có rất nhiều ứng dụng như gán nhãn, phân cụm, nhận biết các loại thực thể và trích chọn thông tin. Đây là vấn đề nhỏ nhưng lại góp phần to lớn trong việc xây dựng những bài toán lớn hơn.Ở đây tập chung vào ứng dụng trích chọn thông tin với các ứng dụng phổ biến trong tương lai gần như: trích chọn thông tin web, trích chọn các sự kiện, và ứng dụng cho việc hỏi và trả lời (Question-answering)- hệ hỏi đáp. Trong tương lai chúng ta có thể sử dụng máy tính để trộn các thông tin được coi là quan trọng với nhau. Hầu hết các ứng dụng đều liên quan đến việc xử lý ngôn ngữ. Trong giai đoạn đầu, CNTT tập trung vào dữ liệu dạng số, biểu diễn dưới dạng cấu trúc như các vector hay bảng biểu. Sau đó các xử lý phức tạp hơn ra đời như hình ảnh, âm thanh, văn bản, ký hiệu hình thức, đồ thị, … Có thể kể đến một số bài toán tiêu biểu trong xử lý ngôn ngữ như: Nhận dạng tiếng nói, tổng hợp tiếng nói, nhận dạng chữ viết, dich tự động, tóm tắt văn bản, tìm kiếm thông tin và trích chọn thông tin. Trong mười năm qua với các cách tiếp cận dựa vào thống kê và tiếp cận dựa vào dữ liệu. Công nghệ xử lý tiếng nói không chỉ dựa trên các kỹ thuật xử lý tín hiệu, mà còn dựa vào việc hiểu ngôn ngữ. Do các tham số của các mô hình thống kê có thể tự “học” được từ các kho ngữ liệu lớn. Với hướng phát triển như vậy việc ứng dụng mô hình Conditional Random Field vào các bài toán ứng dụng trong xử lý ngôn ngữ là rất cần thiết. 47 TÀI LIỆU THAM KHẢO Tài liệu tiếng Việt: [1] Hồ Tú Bảo, Lương Chi Mai. Việc xử lý tiếng Việt trong công nghệ thông tin. Viện công nghệ thông tin, Viện khoa học và Công nghệ tiên tiến Nhật Bản [2] Cao Hoàng Trụ, Nguyễn Lê Minh. Phân cụm từ tiếng Việt bằng phương pháp học máy cấu trúc. Pages 11. 2006 [3] Phan Thị Tươi, Nguyễn Quang Châu, Cao Hoàng Trụ. Gán nhãn từ loại cho tiếng Việt dựa trên văn phong và tính toán xác suất. Tạp chí phát triển KH&CN, tập 9, số 2 -2006 Tài liệu tiếng Anh: [4] Andrew McCallum DayneFreitag. Maximum Entropy Markov Models for Information Extractionand Segmentation. in AT&T Labs-Research. Pages 1-9 [5] Ben Wellner. Conditional Random Fields and Maximum Entropy Markov Models. In CS114 Spring 2006 (slide) [6] Canasai Kruengkrai,Virach Sornlertlamvanich, HitoshiIsahara. A Conditional Random Field Framework for Thai Morphological Analysis. In Proceedings of the Fifth International Conference on Language Resources and Evaluation(LREC-2006), may 24-26, 2006. Genoa, Italy. Pages 1-16 [7] Carl Bergstrom. Joint entropy, conditional entropy, relative entropy, and mutual information. January 13, 2008. In Cover and Thomas (1991). Pages 1-8 [8] Conglei Yao. Conditional Random field an overview. Computer Networks and Distributed Systems Laboratory Peking University 2008-12-31. in technique report 42 slides [9] Dan Cong. Conditional Random Fields and Its Applications .Feb. 1, 2006 [10] Douglas E. Appelt and David J. Israel. Introduction to Information Extraction Technology .A Tutorial Prepared for IJCAI-99. in Artificial Intelligence Center SRI International [11] Fredric Brown. Information Extraction: 10-707 and 11-748 (slide) [12] Phil Blunsom. Hidden Markov Models- August 19, 2004. Pages 1-7 48 [13] Hanna M. Wallach. Conditional Random Fields: An Introduction. pages 1-9. February 24, 2004. In University of Pennsylvania CIS Technical Report MS- CIS-04-21 [14] John Lafferty and Andrew McCallum. Conditional Random Fields Probabilistic Models for Segmenting and Labeling Sequence Data. Pages 1-8 [15] Nikis Karampatziakis. Maxinum Entropy Markov Models [16] Rakesh Dugad . A Tutorial on hidden Markov Models. Technical Rep ort No SPANN May 1996. Pages 1-16. [17] Trausti Kristjansson & Aron Culotta & PaulViola & Andrew McCallum. InteractiveInformationExtraction with Constrained Conditional Random Fields. in Microsoft Research. Pages 7 [18] William W. Cohen CALD. Conditonal Random Field in CALD [19] Vikas Kedia. Graphical Models for Information Extraction and Reconciliation. Department of Computer Science and Engineering Indian Institute of Technology, Bombay Mumbai. In M. Tech. Project First Stage Report Submitted in partial fulfillment of the requirements for the degree of Master of Technology. Pages 20 [20] [21]