Khóa luận Trích chọn thực thể tên người trong Tiếng Việt

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Lê Thu Thùy TRÍCH CHỌN THỰC THỂ TÊN NGƯỜI TRONG TIẾNG VIỆT KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI – 2009 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Lê Thu Thùy TRÍCH CHỌN THỰC THỂ TÊN NGƯỜI TRONG TIẾNG VIỆT KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: TS. Nguyễn Trí Thành HÀ NỘI – 2009 i Lời cảm ơn Trước tiên, em muốn gửi lời cảm ơn sâu sắc nhất đến thầy giáo, TS. Nguyễn Trí Thành, những 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 này. Em xin bày tỏ lời cảm ơn sâu sắc đến những thầy cô giáo đã giảng dạy em trong bốn năm học qua, đã cho em những kiến thức quý báu để em có thể vững bước trên con đường đi của mình. Tôi xin gửi lời cảm ơn sâu sắc tới các bạn trong lớp K50 CA đã ủng hộ và khuyến khích tôi trong suốt quá trình học tập tại trường. Và lời cuối cùng, tôi xin bày tỏ lòng chân thành và biết ơn vô hạn tới cha mẹ và em trai tôi, những người luôn ở bên cạnh tôi những lúc tôi khó khăn nhất, giúp tôi vượt qua những khó khăn trong học tập cũng như trong cuộc sống. Xin chân thành cảm ơn! Sinh Viên Lê Thu Thùy ii Tóm tắt Trích chọn các loại thực thể nói chung, cũng như trích chọn tên người nói riêng là một bước cơ bản trong trích chọn thông tin từ văn bản và xử lý ngôn ngữ tự nhiên. Nó được ứng dụng nhiều trong dịch tự động, tóm tắt văn bản, hiểu ngôn ngữ tự nhiên, nhận biết tên thực thể trong sinh/y học và đặc biệt ứng dụng trong việc tích hợp tự động các đối tượng, thực thể từ môi trường Web vào các ontology ngữ nghĩa và các cơ sở tri thức. Trong khóa luận này, em trình bày một giải pháp trích chọn thực thể tên người cho các văn bản tiếng Việt trên môi trường Web. Sau khi xem xét các hướng tiếp cận khác nhau, em đã lựa chọn phương pháp dựa trên giải thuật mở rộng quan hệ mẫu đối ngẫu lặp lại (Dual Interative Pattern Relation Expansion - DIPRE) [17] mà Brin đã đề xuất. Đây là phương pháp sử dụng học bán giám sát (semi-supervised), dựa trên các ngữ cảnh (occurrences) xung quanh các thực thể để trích chọn quan hệ mẫu, từ đó đưa ra được danh sách các thực thể cần nhận biết. iii Mục lục Lời cảm ơn ...................................................................................................................i Tóm tắt ........................................................................................................................ii Mục lục ..................................................................................................................... iii Bảng từ viết tắt ............................................................................................................v Danh sách hình vẽ.......................................................................................................vi Mở đầu ........................................................................................................................1 Chương 1. Bài toán trích chọn .....................................................................................3 thực thể tên người ........................................................................................................3 1.1. Trích chọn thông tin ..........................................................................................3 1.2. Tổng quan về bài toán trích chọn thực thể tên ...................................................4 1.3. Bài toán trích chọn thực thể tên người trong văn bản tiếng Việt trên môi trường web..........................................................................................................................5 1.4. Ý nghĩa của bài toán trích chọn thực thể tên người............................................7 Chương 2. Các hướng tiếp cận trong trích chọn thông tin ............................................9 2.1. Phương pháp dựa trên học máy .........................................................................9 2.1.1. Mô hình Markov ẩn (HMM).......................................................................9 2.1.1.1. Tổng quan về HMM ............................................................................9 2.1.1.2. Hạn chế của mô hình HMM...............................................................11 2.1.2. Mô hình Markov cực đại hóa Entropy (MEMM) ......................................11 2.1.2.1. Tổng quan về mô hình MEMM .........................................................11 2.1.2.2. Vấn đề Label Bias .............................................................................12 2.1.3. Mô hình trường điều kiện ngẫu nhiên (CRF) ............................................13 2.1.3.1. Tổng quan về mô hình CRF...............................................................13 2.1.3.2. Hàm tiềm năng của mô hình CRF......................................................14 2.2. Phương pháp tiếp cận dựa trên hệ luật .............................................................16 2.2.1 Tổng quan về tiếp cận dựa trên hệ luật ......................................................16 2.2.2 Giải thuật DIPRE ......................................................................................16 2.2.1.1. Tổng quan về học bán giám sát..........................................................16 2.2.1.2. Giải thuật DIPRE...............................................................................18 2.3 Tổng kết chương ..............................................................................................21 Chương 3. Hệ thống trích chọn tên người trong văn bản tiếng Việt trên môi trường Web...........................................................................................................................22 3.1 Hướng giải quyết bài toán ................................................................................22 3.2 Thực nghiệm ....................................................................................................27 3.2.1. Môi trường thực hiện................................................................................27 3.2.2 Thu thập dữ liệu ........................................................................................27 3.3. Khảo sát và xây dựng thủ công các tập dữ liệu từ điển ban đầu .......................27 3.3.1. Tập dữ liệu từ điển ban đầu và tập mẫu ....................................................27 3.3.2. Giới hạn vòng lặp .....................................................................................29 3.4 Đánh giá hệ thống nhận dạng thực thể.............................................................29 3.4.1. Kết quả.....................................................................................................30 3.4.2. Đánh giá...................................................................................................31 iv Kết luận .....................................................................................................................32 Tài liệu tham khảo .....................................................................................................34 v Bảng từ viết tắt Từ hoặc cụm từ Viết tắt Condition Random Field CRF Dual Interative Pattern Relation Expansion DIPRE Hidden Markov Model HMM Maximum Entropy Markov Model MEMM Name Entity Recognition NER vi Danh sách hình vẽ 1 Mở đầu Trích chọn thực thể tên (Name Entity Extraction), đặc biệt là trích chọn tên người ngày càng trở nên quan trọng hơn đối với sự phát triển ngày càng cao các ứng dụng của xử lý ngôn ngữ tự nhiên. Tuy nhiên, việc trích chọn tên người cũng như sử dụng chúng một cách triệt để vẫn là một vấn đề không hề đơn giản. Thừa nhận rằng, một trong những cách tốt nhất để xác định tên người là sử dụng thông tin ngữ cảnh xuất hiện xung quanh tên người. Do đó, vấn đề chính sẽ là làm thế nào để tìm ra các ngữ cảnh mà tại đó, tên người xuất hiện. Các phương pháp có thể là thủ công, sử dụng hệ luật (rule-based) hay tự động… Hiện nay, hầu hết các hệ thống nhận dạng tên thực thể đều dựa vào một tập nhỏ các loại thực thể tên thông thường. Mặc dù đã có một vài đề xuất được đưa ra nhằm mở rộng các cấp của các loại thực thể tên nhưng nó vẫn cố định một số lượng nhất định các loại thực thể tên. Vấn đề áp dụng bài toán trích chọn các loại thực thể cho các miền dữ liệu có tính chất đặc trưng riêng khác với những dữ liệu bình thường, điều này rất đáng được quan tâm. Trong khi đó, với những ứng dụng quan trọng trong web ngữ nghĩa, hay trong hệ thống hỏi đáp tự động, …thì các miền dữ liệu tên người cũng là một trong những miền dữ liệu được nhắc tới nhiều nhất. Ý thức được những lợi ích mà các bài toán trích chọn thực thể nói chung và trích chọn tên người nói riêng, em đã chọn hướng nghiên cứu nhằm giải quyết bài toán trích chọn thực thể tên người trong văn bản tiếng Việt trên môi trường Web làm đề tài luận văn của mình. Luận văn được tổ chức thành các chương như sau: Chương 1 giới thiệu tổng quan về bài toán trích chọn thông tin, bài toán trích chọn thực thể tên người cho văn bản tiếng Việt trên môi trường Web cùng những ứng dụng thực tế của nó. Chương 2 trình bày một số hướng tiếp cận nhằm giải quyết bài toán trích chọn thực thể như phương pháp dựa trên hệ luật, phương pháp học máy như HMM, MEMM, CRF. Đối với phương pháo dựa trên hệ luật, khóa luận sẽ giới thiệu về một số hệ thống liên quan tới trích chọn thực thể. Cụ thể đó chính là giải thuật DIPRE [17], một giải thuật được đề xuất bởi Brin, sử dụng tập dữ liệu ban đầu (seed) để tìm ra các 2 mẫu (patterns). Phương pháp này đều đã có những kết quả thực nghiệm hết sức khả quan. Chương 3 trình bày hệ thống trích chọn thực thể tên người trong văn bản tiếng Việt trên môi trường Web dựa trên giải thuật DIPRE (Dual Interative Pattern Relation Expansion)[17] mà Brin (1998) đã đề xuất kết hợp với một số luật mang những đặc điểm cơ bản của tên người trong tiếng Việt và đưa ra một số kết quả thực nghiệm. 3 Chương 1. Bài toán trích chọn thực thể tên người Chủ đề chính của khóa luận là áp dụng phương pháp dựa trên hệ luật (rule-based) kết hợp với giải thuật DIPRE (Dual Interative Pattern Relation Expansion)[17] do Brin đề xuất. Chương này sẽ giới thiệu tổng quan về trích chọn thông tin, về bài toán trích chọn thực thể nói chung, chi tiết về bài toán trích chọn thực thể tên người nói riêng cũng như ứng dụng, ý nghĩa của bài toán trích chọn thực thể tên người. 1.1. Trích chọn thông tin Trích chọn thông tin là một lĩnh vực quan trọng trong khai phá dữ liệu văn bản, thực hiện việc trích rút các thông tin có cấu trúc từ các văn bản không có cấu trúc. Cụ thể hơn, một hệ thống trích chọn thông tin sẽ trích ra những thông tin đã được định nghĩa trước về các thực thể và mối quan hệ giữa chúng từ một văn bản dưới dạng ngôn ngữ tự nhiên và điền những thông tin này vào một văn bản ghi dữ liệu có cấu trúc hoặc một dạng mẫu (template) được định nghĩa trước đó. Ví dụ như việc trích chọn vị trí của một cuộc hẹn từ một bức thư điện tử hay trích chọn tên của một công ty từ một bài báo… Các kĩ thuật được sử dụng trong trích chọn thông tin gồm có: hướng tiếp cận dựa trên luật và dựa trên các phương pháp học máy. Có thể sử dụng trích chọn thông tin từ văn bản với nhiều mức độ khác nhau như nhận dạng các loại thực thể tên (Name Entity Recognition – NER), điền thông tin các mẫu kịch bản (Scenario Template), hay xác định quan hệ giữa các thực thể (Relation Extraction hay còn gọi là trích chọn quan hệ), ví dụ như liên kết các bản ghi (record association) trong cơ sở dữ liệu, hay để chuẩn hóa (nomalization) và tránh trùng lặp (deduplication) dữ liệu … Khóa luận này tập trung chủ yếu vào việc nhận dạng thực thể tên và trích chọn quan hệ giữa chúng để giải quyết bài toán trích chọn tên người trong văn bản tiếng Việt trên môi trường Web. Có rất nhiều mức độ cũng như nội dung công việc trích chọn thông tin khác nhau. Công việc nghiên cứu trích chọn ở đây là trích lại những thông tin từ văn bản. Ví dụ, tại hội thảo MUC-7 (Seventh Message Understanding Conmference), thông tin trích chọn mà người ta quan tâm đến là nhận diện những sự kiện liên quan đến việc 4 phóng tên lửa trong 100 bài báo của NewYork Times. Công việc này được thực hiện bằng cách làm sao trả lời được những câu hỏi như: Tên lửa được phóng ra từ đâu? Ai là chủ nhân điều khiển tên lửa đó? Khối lượng chất nổ trong tên lửa? Chất nổ sử dụng là gì? Hình 1 dưới đây mô tả một hệ thống trích chọn thông tin. Hình 1 biểu diễn việc trích chọn các thực thể “NAME”, “TITLE” và thực thể “ORGANIZATION” từ một đoạn văn bản. Kết quả đưa ra là danh sách tên người (NAME) tương ứng với chức vụ (TITLE) và tổ chức (ORGANIZATION) của họ xuất hiện trong văn bản nêu trên. Như vậy, có thể hiểu đơn giản rằng công việc trích chọn thông tin ở đây đơn giản là đi tìm những quan hệ giữa các đối tượng có tên được chỉ định trước. 1.2. Tổng quan về bài toán trích chọn thực thể tên Việc trích chọn các thực thể tên (còn được gọi là phân lớp tên riêng) là một công việc của xử lý ngôn ngữ tự nhiên trên máy tính. Nhiệm vụ chính của nó là tìm kiếm và phân lớp các từ vào các nhóm đối tượng như: tên người (person), địa danh (location), IE NAME TITLE ORGANIZATION Bill Gates CEO Microsoft Corporation Bill Veghte VP Microsoft Richard Stallman founder Free Software Foundation October 14,2002, 4:00 a.m. PT For year, Microsoft Corporation CEO Bill Gates railed against the economic philosophy of open-source software with Orwellian fevor, denouncing its communal licensing as a “cancer” that stifled technological innovation. Today, Microsoft clains 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 opertating 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… Hình 1: Mô hình trích chọn thực thể 5 tổ chức (organization), ngày tháng (date), thời gian (time), tỷ lệ (percentage), tiền tệ (moneytary) và cả những loại thực thể không thuộc những dạng kể trên. Bài toán trích chọn thực thể là bài toán đơn giản nhất trong số các bài toán trích chọn thông tin. Các nhà nghiên cứu đã chỉ ra rằng, để thực hiện được việc trích chọn các thông tin phức tạp, hệ thống phải có khả năng thực hiện một số công việc đơn giản hơn. Và trích chọn thực thể chính là một trong những yêu cầu đầu tiên của hầu hết các hệ thống đó, vì rõ ràng trước khi có thể xác định được các mối quan hệ giữa các thực thể, ta phải xác định được đâu là các thực thể tham gia vào mối quan hệ đó. Do đó, bài toán trích chọn thực thể là một trong những bước cơ bản nhất trước khi tính đến việc giải quyết các bài toán phức tạp hơn trong lĩnh vực này. Có rất nhiều phương pháp đã được sử dụng để giải quyết các bài toán trích chọn thực thể, từ các phương pháp dựa trên hệ luật (rule-based) đến các phương pháp học máy (machine learning). Một số phương pháp học máy như: Mô hình Markov ẩn (Hidden Markov Model - HMM), mô hình cực đại hóa Entropy (Maximum Entropy Markov Model - MEMM), mô hình trường ngẫu nhiên điều kiện (Conditional Ramdom Field - CRF), phương pháp máy vector hỗ trợ (Support Vector Machine - SVM)….Các phương pháp ngày sẽ được giới thiệu chi tiết ở chương 2. 1.3. Bài toán trích chọn thực thể tên người trong văn bản tiếng Việt trên môi trường web Các thực thể đóng vai trò quan trọng rất nhiều trong ứng dụng xử lý ngôn ngữ tự nhiên. Hiện nay, hầu hết các hệ thống nhận dạng thực thể tên đều dựa vào một tập nhỏ các loại thực thể tên thông thường. Mặc dù đã có một vài đề xuất được đưa ra nhằm mở rộng các cấp của các loại thực thể tên nhưng nó vẫn cố định ở một số lượng nhất định các loại thực thể tên. Trong các ứng dụng thực tế: hệ thống hỏi đáp hay hệ thống tìm kiếm ngữ nghĩa, người dùng có thể sẽ hứng thú hơn với riêng từng loại thực thể. Khi đó, vấn đề đặt ra sẽ là áp dụng bài toán trích chọn các loại thực thể cho các miền dữ liệu có tính chất đặc trưng riêng biệt, khác với những dữ liệu thông thường. Đây là điều rất đáng được quan tâm. Và miền dữ liệu tên người cũng là một trong những miền dữ liệu được nhắc tới nhiều nhất. Chính vì vậy, nội dung chính của khóa luận nhằm đưa ra một phương pháp trích chọn thực thể tên người từ văn bản tiếng Việt trên môi trường Web. Thực thể tên người luôn song hành, gắn bó với cuộc sống của mỗi con người từng giờ, từng phút, đóng một vai trò quan trọng đối với mỗi cá nhân. Nó không chỉ có 6 chức năng phân biệt người này với người khác mà còn có chức năng thẩm mỹ nên đối với người Việt Nam, tên người cũng thường được chọn lựa khá kỹ về mặt ngữ âm và ngữ nghĩa. Do đó, việc khai thác tối ưu vấn đề này để áp dụng cho nhiều bài toán cụ thể khác cũng là một đề tài quan trọng. Tuy nhiên, đối với hệ thống tên người trên thế giới nói chung hay của Việt Nam nói riêng đều không có một nguyên tắc chung nào trong việc đặt tên. Cũng như sự phong phú về ngôn ngữ dẫn tới thực thể tên người sẽ có cấu trúc phức tạp hơn, do đó, không tránh khỏi sự nhập nhằng. điều này khiến cho việc trích chọn tên người cũng như trích chọn quan hệ giữa chúng trở nên khó khăn hơn so với các văn bản tiếng Anh. Cụ thể như sau:  Các văn bản tiếng Việt không có dữ liệu huấn luyện có sẵn, và các nguồn tài nguyên có thể tra cứu trên WordNet trong tiếng Anh.  Thiếu các thông tin ngữ pháp (POS) và các thông tin về cụm từ như: cụm danh từ, cụm động từ,…cho tiếng Việt trong khi các thông tin này giữ vai trò quan trọng trong việc trích chọn thực thể.  Một số trường hợp dễ dàng xuất hiện đối với tên người trong tiếng Việt như sau: “Hồ Chí Minh là một vị lãnh tụ vĩ đại của dân tộc Việt Nam.” (1) “Hồ Chí Minh là một trong những thành phố lớn nhất ở Việt Nam.” (2) “Tổng thống Mỹ có chuyến viếng thăm Trung Quốc.” (3) “Tổng thống Mỹ Obama có chuyến viếng thăm Trung Quốc.” (4) “Tổng thống Obama có chuyến viếng thăm đất nước Trung Quốc.” (5) Xét trường hợp (1) và (2), dễ dàng nhận thấy sự nhập nhằng, điều này sẽ phát sinh những vấn đề như: “Hồ Chí Minh” nào là tên người? Chữ “Hồ” đầu câu viết hoa, do đó, thông tin viết hoa đầu câu thường không mang nhiều ý nghĩa. Xét tới trường hợp (3), (4), và (5), có thể thấy cùng một nội dung nhưng có nhiều cách để diễn đạt, nhưng không phải cách diễn đạt nào cũng khiến người lập trình có thể dễ dàng lấy ra được tên người. 7 Trường hợp (3) hoàn toàn không có tên người, nhưng đây cũng là trường hợp dễ nhầm lẫn khi thực hiện trích chọn. Trường hợp (5) tồn tại hai loại thực thể, “Mỹ” chỉ địa danh. “Obama” chỉ tên người Rất có thể kết quả trích chọn sẽ đưa ra kết quả là “Mỹ Obama” → đó là một kết quả hoàn toàn không chính xác. Như vậy, bài toán đưa ra nhằm đánh giá các chiến lược khai phá dữ liệu tên người, đặc biệt tập trung vào hai bài toán con: trích chọn thực thể và trích chọn quan hệ. Bởi vì, trước khi xác định được quan hệ giữa các thực thể để thực hiện trích rút thì ta phải nhận biết được thực thể cần trích chọn. Việc trích chọn thực thể tên người đòi hỏi phải nhận biết được các thành phần cơ bản và đặc trưng của dữ liệu tên người, ví dụ như các chức danh luôn đi kèm với tên người trong văn bản: ông, bà, học sinh, anh, chị, thầy giáo, cô giáo, giám đốc, tổng giám đốc, …dựa vào sự xuất hiện của các thực thể, thuật toán đưa ra sẽ giữ lại các ngữ cảnh xung quanh thực thể tên để từ đó trích chọn ra quan hệ các mẫu, cuối cùng, dựa vào các mẫu đã trích chọn được để tiếp tục đưa ra các thực thể tên người cần trích chọn. Đây chính là phương pháp mà khóa luận đề cập tới để áp dụng cho bài toán này dựa trên cơ sở giải thuật DIPRE (Dual Interative Pattern Relation Expansion)[17] của Brin. Với phương pháp này ta sẽ khắc phục được những vấn đề đặt ra đối với thực thể tên người trong tiếng Việt cũng như việc tìm kiếm để sinh ra các mẫu khác nhau. Cụ thể về cách giải quyết bài toán sẽ được trình bày chi tiết ở chương 3. 1.4. Ý nghĩa của bài toán trích chọn thực thể tên người Trích chọn thông tin luôn là bước đi đầu tiên của nhiều ứng dụng thực tế và việc trích chọn, nhận biết tên người cũng tương tự như vậy. Tên người là một thành phần chủ chốt để xử lý câu đầu vào. Do đó, trích chọn tên người được sử dụng một cách rộng rãi trong nhiều lĩnh vực khác nhau như xử lý ngôn ngữ tự nhiên, thu thập thông tin, dịch tự động…Cụ thể như sau:  Hỗ trợ Web ngữ nghĩa. Web ngữ nghĩa là các trang Web có thể biểu diễn dữ liệu “thông minh”, ở đây “thông minh” chỉ khả năng kết hợp, phân lớp và khả năng suy diễn trên dữ liệu đó. Sự thành công của các Web ngữ nghĩa phụ thuộc vào các ontology, cũng như sự phát triển của các trang 8 Web được chú giải bởi các siêu dữ liệu tuân theo các ontology này. Mặc dù các lợi ích mà các ontology đem lại là rất lớn nhưng việc xây dựng chúng một cách tự động lại hết sức khó khăn. Vì lý do này, các công cụ trích chọn thông tin tự động từ các trang Web để “làm đầy “ các ontology như hệ thống nhận biết thực thể là hết sức cần thiết.  Xây dựng các máy tìm kiếm hướng thực thể theo các đặc trưng riêng biệt. Người dùng có thể lấy ra được danh sách chỉ có riêng thực thể tên người mà họ cần tìm thay vì một loạt danh sách bao gồm cả các thực thể khác.  Như đã được đề cập trên đây, một hệ thống nhận biết thực thể tên người có thể đóng vai trò là một thành phần cơ bản cho các bài toán trích chọn thông tin phức tạp hơn, phụ thuộc vào mục đích sử dụng của con người.  Trước khi đọc một tài liệu, người dùng có thể đọc lướt qua các tên người mà họ quan tâm. Hệ thống trích chọn thực thể tên người cho tiếng Việt cũng sẽ làm tiền đề cho việc giải quyết các bài toán về trích chọn thông tin từ các tài liệu tiếng Việt cũng như hỗ trợ cho việc xử lý ngôn ngữ tiếng Việt. Áp dụng hệ thống để xây dựng một ontology về các thực thể trong tiếng Việt sẽ đặt nền móng cho một thế hệ Web mới - “ Web ngữ nghĩa tiếng Việt”. 9 Chương 2. Các hướng tiếp cận trong trích chọn thông tin Có rất nhiều phương pháp đã được dùng để giải quyết bài toán trích chọn thực thể, từ phương pháp dựa trên hệ luật tới phương pháp học máy. Một số phương pháp học máy như: Mô hình Markov ẩn (Hidden Markov Model - HMM), mô hình Markov cực đại hóa Entropy (Maximum Entropy Markov Model - MEMM), mô hình trường ngẫu nhiên điều kiện (Conditional Random Field - CRF), phương pháp máy vector hỗ trợ (Support Vector Machine - SVM)…. Chương này sẽ giới thiệu một số hướng tiếp cận cùng với ưu và nhược điểm của chúng, từ đó lý giải tại sao phương pháp mà khóa luận sử dụng lại dựa trên giải thuật DIPRE để xây dựng hệ thống trích chọn tên riêng cho tiếng Việt. 2.1. Phương pháp dựa trên học máy 2.1.1. Mô hình Markov ẩn (HMM) 2.1.1.1. Tổng quan về HMM HMM là mô hình máy hữu hạn trạng thái (finite state machine) 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 và nhiệm vụ là xác định các tham số ẩn từ các tham số quan sát được, dựa trên sự thừa nhận này. 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 ví dụ cho các ứng dụng nhận dạng mẫu. 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 một người quan sát, 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. 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 các dãy trạng thái. Các trạng thái trong mô hình HMM được xem là bị ẩn đi bên dưới dữ liệu quan sát sinh ra do mô hình. Quá trình sinh ra chuỗi dữ liệu quan sát trong HMM thông qua một loạt các bước chuyển trạng thái xuất phát từ một trong các trạng thái bắt đầu, chuyển tiếp tới một trạng thái mới, quan sát một dữ liệu được lựa chọn bởi trạng thái đó, quá trình chuyển tiếp lại làm tương tự, quan sát một dữ liệu khác và cứ tiếp tục như 10 vậy cho tới một trạng thái đích cuối cùng được đưa ra. Kết hợp các dữ liệu thu được thành một tập dữ liệu của các trạng thái: 1 2 n{S ,S ,...,S }S  - chuỗi các trạng thái ẩn và xác suất phân bố trên các biểu hiện đầu ra có thể trong các từ vựng quan sát: 1 2 n{O ,O ,...,O }O  - chuỗi các dữ liệu quan sát Từ đây ta có thể tìm ra chuỗi các trạng thái mô tả tốt nhất cho chuỗi dữ liệu quan sát bằng cách tính: )( ),()|( OP OSPOSP  Ta có thể mô hình hóa HMM dưới dạng một đồ thị có hướng như sau: Ở đây, Si là trạng thái tại thời điểm t=i trong chuỗi trạng thái S, Oi là dữ liệu quan sát được tại thời điểm t=i trong chuỗi O. Sử dụng tính chất Markov thứ nhất (trạng thái hiện tại chỉ phụ thuộc vào trạng thái ngay trước đó) và giả thiết dữ liệu quan sát được tại thời điểm t chỉ phụ thuộc trạng thái tại t, ta có thể tính xác suất P(S,O) như sau:    n t tttt SOPSSPSOPSPOSP 2 1111 )|(*)|()|()(),( S1 S2 S3 Sn-1 Sn O1 O2 O3 On-1 On Hình 2: Ví dụ về mô hình Markov 11 Quá trình tìm ra chuỗi trạng thái tối ưu mô tả tốt nhất chuỗi dữ liệu quan sát cho trước có thể được thực hiện bởi một kĩ thuật lập trình quy hoạch động sử dụng thuật toán Viterbi [6]. 2.1.1.2. Hạn chế của mô hình HMM Chúng ta phải cần nhiều chuỗi dữ liệu quan sát hơn để tính P(S,O). Tuy nhiên, S là chuỗi các trạng thái ẩn, số lượng có hạn thì có thể liệt kê được nhưng chuỗi dữ liệu quan sát được O thì rất đa dạng, ta không thể nào có thể liệt kê ra hết được. Khi áp dụng vào các bài toán phân lớp dữ liệu dạng chuỗi, các mô hình thường sử dụng xác suất đồng thời để mô hình hóa các bài toán có tính điều kiện.Với các bài toán này sẽ thích hợp hơn nếu ta dùng một mô hình điều kiện có thể tính toán P (S|O) trực tiếp thay vì P (S, O) ban đầu. 2.1.2. Mô hình Markov cực đại hóa Entropy (MEMM) 2.1.2.1. Tổng quan về mô hình MEMM Một mô hình khác được đưa ra nhằm khắc phục những hạn chế mà mô hình HMM đã gặp phải, đó là mô hình MEMM. Mô hình MEMM sử dụng một hàm xác suất duy nhất 1( | , )i i iP S S O để thay thế cho xác suất chuyển trạng thái và xác suất quan sát trong HMM. Đối với MEMM, các dữ liệu quan sát được cho trước nên ta chỉ cần quan tâm tới xác suất chuyển trạng thái. Xác suất P(S|O) được tính theo công thức:            k ttkk tt ttsttt sofsoZ osPossP t ),(exp ),( 1)|(),|( 1 1 1  S1 S2 Sn-1 Sn S3 O1 O2 O3 On-1 On Hình 3: Đồ thị có hướng mô tả một mô hình MEMM 12 Với: k là các tham số cần được huấn luyện (ước lượng) Z (Ot, St-1) là thừa số chẩn hóa để tổng xác suất chuyển từ trạng thái St-1 sang tất cả các trạng thái St kề đều bằng 1 fk (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. Mỗi hàm thuộc tính fk (Ot,St) nhận hai tham số, một là dữ liệu quan sát hiện tại Oi và một là trạng thái hiện tại St. k = với: k’ là thuộc tính nhị phân chỉ phụ thuộc vào dữ liệu quan sát hiện tại. St là trạng thái hiện tại. Khi đó: 2.1.2.2. Vấn đề Label Bias Trong một số trường hợp đặc biệt, các mô hình MEMM và các mô hình định nghĩa một phân phối xác suất cho mỗi trạng thái có thể gặp phải vấn đề “label bias”. Ta lấy một ví dụ với 2 chuỗi “rib” và “rob” tương ứng với chuỗi trạng thái “0123” và “0453” Có thể thấy cả 2 xâu đầu ra đều có xác suất giống nhau: P(0123|rib) = Pr(1|0,r)/Z1 * Pr(2|1,o)/Z2 * Pr(3|2,b)/Z3 = 0.5 * 1 * 1 = 1 Fk (Ot,St)= 1 nếu b (Ot) =1 và St=St-1 0 nếu ngược lại o:_ 0 1 2 4 5 3 r_ r_ b:rib rib b: rob i_ Hình 4: Vấn đề Label Bias 13 P(0453|rob) = Pr(4|0,r)/Z1’ * Pr(5|4,i)/Z2’ * Pr(3|5,b)/Z3’ = 0.5 * 1 *1 = 1 Khi đó, giả sử như trong tập huấn luyên, từ “rob” xuất hiện nhiều hơn từ “rib” thì khi đó, xác suất P(4|0,r) sẽ lớn hơn xác suất P(1|0,r), hay xác suất của P(0123|rib) sẽ nhỏ hơn xác suất của P(0453|rob), hay chuỗi trạng thái “0453” sẽ được chọn cho dù chuỗi quan sát là “rib” hay “rob”. 2.1.3. Mô hình trường điều kiện ngẫu nhiên (CRF) 2.1.3.1. Tổng quan về mô hình CRF CRF là mô hình dựa trên xác suất có điều kiện dựa trên việc gán nhãn và phân đoạn dữ liệu liên tục. CRF là mô hình đồ thị vô hướng để từ đó có thể định nghĩa một 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. Ưu điểm cơ bản của CRF so với mô hình Markov ẩn đó chính là tính có điều kiện của chúng, làm giảm nhẹ các giả định không phụ thuộc được yêu cầu bởi HMM để bảo đảm kết quả dễ xử lý. Thêm vào nữa, CRF cũng tránh được vấn đề label bias gặp phải trong mô hình Markov cực đại hóa Entropy cũng như đồ thị có hướng trong mô hình Markov điển hình. CRF được thể hiện bằng mô hình đồ thị vô hướng, hoặc bằng trường Markov ngẫu nhiên, bao toàn bộ điều kiện lên X, biến ngẫu nhiên biểu hiện qua các chuỗi quan sát. Cho một đồ thị vô hướng không có chu trình G=(E,V) với: + V là tập các đỉnh của đồ thị. + E là tập các cạnh vô hướng nối các đỉnh đồ thị. + 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 một đỉnh và một thành phần của Yv của Y. + Một node v V tương ứng với mỗi biến ngẫu nhiên biểu diễn một thành phần vY của Y. Nếu mỗi biến ngẫu nhiên của vY tuân theo đặc tính của Markov đối với G thì (Y,X) là một CRF. 14 Hình 5: Đồ thị vô hướng mô tả CRF Trong đó: X=(X1, X2,…, Xn), Y=(Y1,Y2, ...,Yn). 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 trạng thái S. 2.1.3.2. Hàm tiềm năng của mô hình CRF Cấu trúc đồ thị của CRF có thể được sử dụng để tìm thừa số của việc phân phối các mối ghép nối ở các thành phần Yv của Y vào trong các tích chuẩn hóa của giá trị dương, của hàm tiềm năng mang giá trị thực xuất phát từ khái niệm độc lập điều kiện. Mỗi hàm tiềm năng đều hoạt động dựa trên một tập con của các biến ngẫu nhiên được biểu diễn bởi các đỉnh của đồ thị G. Theo định nghĩa của độc lập điều kiện đối với mô hình đồ thị vô hướng, việc thiếu một cạnh bất kỳ giữa hai đỉnh của G sẽ khiến cho các biến ngẫu nhiên được biểu diễn bởi các đỉnh này trở thành độc lập điều kiện đồng thời nó cũng kéo theo các biến ngẫu nhiên khác vào trong mô hình. Tức là các hàm tiềm năng cũng phải chắc chắn việc các biến ngẫu nhiên cũng sẽ không xuất hiện cùng trong một hàm tiềm năng. Đối với trường cấp cấu trúc dây chuyền của CRF, mỗi hàm chức năng sẽ hoạt động theo các cặp có các biến được gán nhãn liền kề nhau Yi và Yi+1 Yn-1 Y1 X Y3 Y2 Yn 15 Theo định nghĩa về xác suất của một nhãn đặc trưng của chuỗi y được quan sát bởi chuỗi x trở thành một tích chuẩn hóa của các hàm tiềm năng, hàm tiềm năng biểu diễn dưới dạng hàm số mũ: j 1 j exp( ( , , , ) ( , , ))j i i k k i k t y y x i s y x i    Khi 1( , , , )j i it y y x i là một hàm tiềm năng chuyển tiếp của toàn bộ chuỗi quan sát và các nhãn ở vị trí i và i-1 trong chuỗi gán nhãn. ( , , )k is y x i : là một hàm tiềm năng trạng thái của nhãn ở vị trí i và chuỗi quan sát. j và k : là các tham số để ước lượng từ tập dữ liệu huấn luyện. Tập các giá trị thực tiềm năng b(x,i) của chuỗi quan sát nhằm biểu diễn một vài ký tự của việc phân bố có kinh nghiệm các tập huấn luyện cần được giữ lại trong việc phân phối mô hình. Một ví dụ: Mỗi hàm tiềm năng đều đưa ra giá trị tiềm năng quan sát b(x,i) nếu trạng thái hiện tại (trong trường hợp là hàm trạng thái ) hoặc trạng thái trước và trạng thái hiện hiện tại (trong trường hợp là hàm chuyển tiếp) đưa ra giá trị riêng. Bởi vậy mà tất các các hàm tiềm năng đều có giá trị thực. Viết đơn giản các biểu thức: 1( , , ) ( , , , )i i is y x i s y y x i và 1 j ( , ) ( , , , ) n j j i iF y x t y y x i  b(x,i) = 1 nếu ví trí quan sát ở i là từ “September” 0 nếu ngược lại 16 Tại mỗi 1( , , , )j i if y y x i cũng là một hàm trạng thái như 1( , , , )i is y y x i hay hàm chuyển tiếp 1( , , , )i it y y x i . Điều này cho phép xác suất của một chuỗi nhãn y được đưa ra mọt chuỗi quan sát x theo công thức dưới đây: j 1( | , ) ex p ( ( , ) ) ( ) j j p y x F y x Z x    Với Z(x) là một thừa số chuẩn hóa, Z(x) được tính theo công thức: ( ) ( , )j y Z x F y x 2.2. Phương pháp tiếp cận dựa trên hệ luật 2.2.1 Tổng quan về tiếp cận dựa trên hệ luật Một hệ thống dựa trên hệ luật bao gồm các tập luật cơ bản (Nếu - Thì), tập các sự vật, bộ thông dịch (interpreter) sử dụng tập luật để sinh ra các sự vật. Hệ thống áp dụng phương pháp dựa trên luật sẽ khảo sát dữ liệu và tạo ra một tập luật ban đầu dựa theo phương pháp thủ công, sau đó áp dụng vào mô hình và mở rộng tập luật này. Các luật chủ yếu được xây dựng dựa trên ngữ cảnh chứa thực thể đang xét. Chương 3 sẽ đề cập chi tiết về cách áp dụng phương pháp này và mô hình giải quyết bài toán. Một trong những phương pháp dựa trên hệ luật dùng để trích chọn thực thể tên đem lại kết quả khả quan là phương pháp sử dụng giải thuật DIPRE (Dual Interative Pattern Relation Expansion)[17] do Brin đề xuất. Phương pháp này sử dụng học bán giám sát (semi-supervised) để xử lý dữ liệu ban đầu. 2.2.2 Giải thuật DIPRE 2.2.1.1. Tổng quan về học bán giám sát Có thể thấy hiện nay, nhu cầu về một lượng lớn các dữ liệu học và những khó khăn để thu được các dữ liệu đó đặt ra một câu hỏi quan trọng: Liệu có thể sử dụng được nguồn thông tin nào khác trong phân lớp văn bản mà có thể làm giảm sự cần thiết của dữ liệu gán nhãn? Đây chính là nguồn động lực thúc đẩy sự phát triển của các phương pháp học bán giám sát. 17 Nhìn vào sự tồn tại của dữ liệu ta thấy, trong thực tế dữ liệu thường tồn tại ở dạng trung gian: Không phải tất cả dữ liệu đều được gán nhãn cũng như không phải tất cả chúng đều chưa được gán nhãn. Bán giám sát là một phương pháp học sử dụng thông tin từ cả hai nguồn dữ liệu này. Trong khoa học máy tính, phương pháp học bán giám sát là một phần của học máy mà trong đó, nó có thể sử dụng cả dữ liệu đã được gán nhãn và dữ liệu không gán nhãn làm tập huấn luyện – một lượng nhỏ các dữ liệu gán nhãn với một lượng lớn dữ liệu chưa được gán nhãn. Học có giám sát là phương pháp sử dụng tập dữ liệu đã được gán nhãn, việc gán nhãn thủ công này rõ ràng là tốn thời gian, công sức và khó khăn, không đảm bảo được độ chính xác. Ngược lại, học không giám sát là phương pháp sử dụng tập dữ liệu chưa gán nhãn. Trong khi lượng dữ liệu chưa gán nhãn là rất nhiều, dễ thu thập nhưng cũng khiến cho học không giám sát đôi khi không đảm bảo được kết quả khả quan. Từ đó, học bán giám sát đã ra đời dưới sự kết hợp ưu điểm và hạn chế của học có giám sát và không giám sát. Mục đích chính của học bán giám sát là mở rộng tập dữ liệu không gán nhãn ban đầu. Từ đó, mô hình học bán giám sát được thể hiện như sau: Học giám sát Dữ liệu chưa gán nhãn Học không giám sát Dữ liệu gán nhãn Học bán giám sát Hình 5: Mô hình học bán giám sát 18 Phạm vi sử dụng của học bán giám sát Các phương pháp học bán giám sát sẽ rất hữu ích khi dữ liệu chưa gán nhãn nhiều hơn dữ liệu gán nhãn. Việc thu được dữ liệu gán nhãn là rẻ, nhưng để gán nhãn chúng thì tốn rất nhiều thời gian, công sức và tiền bạc. Đó là tình trạng của rất nhiều các lĩnh vực ứng dụng trong học máy như:  Trong nhận dạng lời nói, ta sẽ dễ dàng ghi lại một lượng lớn các bài diễn thuyết, nhưng để gán nhãn chúng yêu cầu con người phải lắng nghe rồi đánh máy sao chép lại.  Sự phong phú của hàng tỉ các trang web sẵn sàng cho xử lý tự động, nhưng để phân lớp chúng một cách tin cậy đòi hỏi con người phải đọc chúng.... Học bán giám sát là việc học trên cả dữ liệu đã và chưa được gán nhãn. Từ một số lượng lớn các dữ liệu chưa được gán nhãn, và một luợng nhỏ dữ liệu đã được gán nhãn ban đầu (thường gọi là seed set) để xây dựng một bộ phân lớp thậm chí là tốt hơn. Trong quá trình học như thế phương pháp sẽ tận dụng được những thông tin phong phú của dữ liệu chưa gán nhãn (unlabeled data), mà chỉ yêu cầu một số lượng rất nhỏ các dữ liệu đã gán nhãn (labeled data). Ý tưởng chung là vẫn thu được performance tốt như đối với việc học trên tập một tập dữ liệu lớn đã được gán nhãn. Có một câu hỏi là: Liệu các phương pháp học bán giám sát có ích hay không? Chính xác hơn là, so sánh với học giám sát chỉ sử dụng dữ liệu gán nhãn, ta có thể hy vọng vào sự chính xác của dự đoán khi xét thêm các điểm không gán nhãn. Câu trả lời là “có” dưới những giả thiết phù hợp (certain assumptions) của từng mô hình. Trong khóa luận này, đối với học bán giám sát, ta chỉ quan tâm xem nó dùng để làm gì chứ không đi sâu vào các bước xử lý đối với văn bản như thế nào. Học bán giám sát đã được Brin áp dụng đối với phương pháp DIPRE trong trích chọn quan hệ mẫu trong văn bản. 2.2.1.2. Giải thuật DIPRE Web là một nguồn tài nguyên tồn tại một số lượng lớn khổng lồ các dữ liệu văn bản như thư điện tử, cơ sở dữ liệu tổng hợp, thư viện só, các bản ghi tình trạng bệnh nhân, …Các dữ liệu đều bị phân tán, và tồn tại ở nhiều định dạng khác nhau. Do đó, vấn đề trích chọn thông tin từng đoạn dữ liệu riêng biệt trong văn bản trên WWW một 19 cách tự động, ít có sự can thiệp của con người là một vấn đề mà từ trước tới giờ luôn thu hút nhiều sự quan tâm của nhiều nhà khoa học. Brin đã đưa ra phương pháp DIPRE cho việc mở rộng mối quan hệ mẫu trong văn bản trên môi trường Web để trích chọn thực thể. Phương pháp này dựa vào các mẫu (pattern) và các tập nhỏ ban đầu (seed) để trích ra các quan hệ mẫu phù hợp với ngữ cảnh của các văn bản. Ban đầu ta có một tập mồi chứa các bộ, các bộ này là những xâu sẽ xuất hiện trong tập các văn bản trên Web. Cơ bản của phương pháp DIPRE mà Brin muốn hướng tới đó là từ các bộ sẽ trích chọn ra được các mẫu và ngược lại, từ các mẫu sẽ sinh ra các bộ mới. Mẫu ở đây sẽ chứa các thành phần trong bộ mà ta cần trích chọn và thêm các ngữ cảnh liên quan. Phương pháp này chính là việc trích chọn quan hệ giữa mẫu để đưa ra kết quả thu được là danh sách các thực thể tên mà ta cần trích ra. Thuật toán mà DIPRE như sau: Ban đầu có một tập nhỏ D các cặp (tác giả, tên sách) 1. Sử dụng tập nhỏ chứa các ví dụ liên quan tới thực thể cần trích chọn để gán nhãn các dữ liệu. 2. Tạo ra các mẫu từ các dữ liệu đã được gán nhãn. 3. Đưa các mẫu từ dữ liệu chưa được gán nhãn tới tập các cặp (tác giả, tên sách) mới và thêm chúng vào trong tập nhỏ các cặp D ban đầu. 4. Quay trở lại bước 1 và lặp lại cho tới khi mẫu mới, quan hệ mới không được sinh ra thì giải thuật sẽ dừng. Hệ thống sẽ thực hiện trích chọn thực thể như mô tả một ví dụ dưới đây.Cụ thể với tập nhỏ ban đầu (seed) của cặp (tác giả, tên sách).  Giả sử ban đầu trong tập seed có cặp: (Arthur Conan Doyle, The Advanture of Sherlock Holmes). Hệ thống sẽ thực hiện tìm kiếm tất cả các tài liệu văn bản trên môi trường Web chứa cặp đó. Trong quá trình tìm kiếm, giả sử tìm thấy một câu có chứa cặp thực thể trên như sau: “Read The Adventures of Sherlock Holmes by Arthur Conan Doyle online or in you email”. 20  Sau đó, thực hiện trích chọn bộ. Để xác định ngữ cảnh xung quanh cặp thực thể , thiết lập một bộ gồm 6 thành phần: [order, tác giả, tên sách, prefix, suffix, middle] Trong đó: order có kiểu boolean. order = 1 nếu xâu tên tác giả xuất hiện trước xâu tên sách và order= 1 thì ngược lại, xâu tên sách xuất hiện trước xâu tên tác giả. prefix và suffix là các xâu có khoảng 10 kí tự xuất hiện tương ứng bên trái và bên phải của đoạn thực thể được phát hiện. middle là xâu xuất hiện giữa tác giả và tên sách. Tương ứng với câu tìm được ở trên, ta có bộ: [0,Arthur Conan Doyle, The Adventures of Sherlock Holmes, Read, online or, by] Tương tự như vậy, giả sử hệ thống lại tìm thấy một đoạn phù hợp với cặp trong tập seed bao đầu như sau: “When Sir Arthur Conan Doyle wrote the advantures of Sherlock Holmes in 1892 he was high” Tương tự như trên, bộ trích rút ra sẽ là: [1, Arthur Conan Doyle, The Adventures of Sherlock Holmes, When Sir, in 1982, wrote] Khi đó, hệ thống sẽ có danh sách các bộ: [0,Arthur Conan Doyle, The Adventures of Sherlock Holmes, Read, online or, by] [1, Arthur Conan Doyle, The Adventures of Sherlock Holmes, When Sir, in 1982, wrote]  Nhóm các bộ dựa vào order và middle, sau đó, tạo ra các mẫu (patterns) Mẫu tương ứng với 2 bộ tìm được ở trên là: [Sir, Arthur Conan Doyle, wrote, The Advantages of Sherlock Holmes, in 1982]  Mẫu sinh ra sẽ được viết dưới dạng biểu thức chính quy: [*prefix, author, middle, title, suffix*] Tương ứng với mẫu tìm được của cặp (tác giả, tên sách): [Sir, .*?, wrote, .*?, in 1982] 21  Với mẫu tìm được ở dạng biểu thức chính quy như trên, hệ thống sẽ tìm trên nhiều tài liệu khác. Giả sử như: “Sir Arthur Conan Doyle wrote Speckled Band in 1982, that is around 672 years apart which would make the stories”  Trích chọn quan hệ mới: (Arthur Conan Doyle, Speckled Band)  Quan hệ mới này được lưu vào trong tập seed ban đầu và tiếp tục lặp lại thuật toán này với quan hệ mới vừa tìm được. Đó là một ví dụ cụ thể mà Brin đã sử dụng giải thuật DIPRE để thực hiện trích chọn thực thể (tác giả, tên sách). Vấn đề khó khăn của DIPRE Vấn đề về hiệu suất chính là vấn đề mà DIPRE gặp phải. Việc sử dụng tập mồi nhỏ để từ đó trích chọn ra các mẫu rồi lại trích ra qua hệ mới, tốc độ của DIPRE sẽ rất chậm, và đặc biệt trong trường hợp tập seed chứa dữ liệu có sự xuất hiện ít, trong khi tập dữ liệu sẽ phải thực hiên tìm kiếm là lớn. Khi đó, yêu cầu đặt ra sẽ phải quét hết một số lượng lớn các mẫu và các bộ trong một kho dữ liệu vô cùng lớn. Và liệu rằng DIPRE có lưu giữ được dữ liệu khi đã bị phân tách từ kết quả khi chung mở rộng quan hệ giữa các mẫu. Điều này không chỉ kéo theo tốc độ giảm mà kết quả cũng thấp. 2.3 Tổng kết chương Chương này giới thiệu các hướng tiếp cận nhằm giải quyết bào toán trích chọn thông tin nói chung cũng như trích chọn thực thể nói riêng: hướng tiếp cận dựa trên hệ luật (giải thuật DIPRE), các hướng tiếp cận học máy (HMM, MEMM, CRF). Có thể thấy, mỗi hướng tiếp cận đều có những ưu và nhược điểm khác nhau như giải thuật DIPRE có hiệu suất không cao, tốc độ xử lý chậm, HMM không thể tích hợp các thuộc tính phong phú của chuỗi dữ liệu quan sát vào quá trình phân lớp, và MEMM gặp phải vấn đề “label bias”. Sau đó lại tiếp tục nâng lên mô hình cao hơn khi sử dụng CRF để khắc phục những nhược điểm mà HMM và MEMM gặp phải. CRF có khả năng xử lý dữ liệu dạng này mạnh hơn so với các mô hình học máy khác như HMM hay MEMM. Tuy nhiên, nhược điểm của mô hình CRF là thời gian tính toán của nó tương đối chậm trong trường hợp dữ liệu huấn luyện tương đối lớn. Thêm nữa là dữ liệu đầu vào của các mô hình này đều phải sử dụng các công cụ để xử lý dữ liệu như phân tách, gán nhãn trong khi nếu dựa theo giải thuật DIPRE của Brin thì những công việc tiền xử lý dữ liệu như vậy hoàn toàn không phải thực hiện. Chi tiết về phương pháp sử dụng cho hệ thống trích chọn tên người dựa trên giải thuật DIPRE sẽ được đề cập ở chương 3. 22 Chương 3. Hệ thống trích chọn tên người trong văn bản tiếng Việt trên môi trường Web Từ chương 2, ta có thể thấy rằng, việc sử dụng các mô hình HMM, MEMM, CRF cũng đều có những ưu nhược điểm nhất định. Một trong những nhược điểm đó là vấn đề tiền xử lý dữ liệu. Cả 3 mô hình đều phải sử dụng các công cụ để thực hiện phân lớp dữ liệu trước khi đưa chúng vào xử lý, việc đó khiến cho hệ thống cũng một phần trở nên cồng kềnh, tốn nhiều công sức, thời gian hơn. Do đó, khóa luận này hướng tới phương pháp trích chọn thực thể tên người mà không sử dụng bất cứ công cụ nào đối với việc tiền xử lý dữ liệu. Đặc biệt, toàn bộ hệ thống sẽ xử lý trên dữ liệu thô. Để có thể làm được việc đó, hướng tiếp cận mà khóa luận này muốn hướng tới là dựa theo giải thuật DIPRE [17] mà Brin đã đề ra để thực hiện mở rộng quan hệ mẫu, từ đó trích chọn ra thực thể tên người trong tiếng Việt. Các phần tiếp theo của chương này sẽ đề cập tới hướng giải quyết này. 3.1 Hướng giải quyết bài toán Như đã nói ở chương 1, việc trích chọn thực thể tên người đòi hỏi phải nhận biết được các thành phần cơ bản và đặc trưng của dữ liệu tên người. Đối với người Việt Nam, tên người có một số đặc trưng cơ bản nhất như là các chức danh luôn đi kèm với tên người trong văn bản: ông, bà, học sinh, anh, chị, thầy giáo, cô giáo, giám đốc, tổng giám đốc, …Dựa theo giải thuật DIPRE, để trích chọn được tên người, ta phải dựa vào sự xuất hiện của các thực thể tên trong tập nhỏ ban đầu (tập seed), thuật toán đưa ra sẽ giữ lại các ngữ cảnh xung quanh thực thể tên đó để từ đó trích chọn ra quan hệ các mẫu, cuối cùng, dựa vào các mẫu đã trích chọn được để tiếp tục đưa ra các thực thể tên người cần trích chọn. Bài toán được xây dựng dựa trên cơ sở giải thuật DIPRE. Tuy nhiên, như đã đề cập tới giải thuật này ở chương 2, Brin ban đầu chỉ sử dụng từ tập nhỏ các dữ liệu (tập seed) ban đầu để từ đó trích ra các mẫu, và đưa ra quan hệ mới giữa các thực thể. Chính điều này đã khiến cho giải thuật này gặp vấn đề về hiệu suất, tốc độ chậm. Do đó, khóa luận chỉ dựa trên tư tưởng của Brin đó là từ tập mẫu trích ra tên thực thể và ngược lại từ thực thể trích ra mẫu. Do đó, hướng giải quyết cho bài toán trích chọn tên người trong tiếng Việt sẽ được minh họa trên hình 7 và được trình bày chi tiết dưới đây. 23 Giải thích mô hình: 1. Bắt đầu từ một tập luật mẫu ban đầu, dựa vào 2. từ điển chức danh (ví dụ: ông, giáo sư,…) hệ thống sẽ trích chọn ra tập các ứng cử cho tên người. 3. Từ tập ứng cử tên người, thủ tục lọc sẽ loại bỏ các ứng cử tên không chính xác để thu được một tập hợp tên người. Nếu tập tên người thu được là tập rỗng thì giải thuật dừng. 4. Dựa vào tập tên người đã thu được, thủ tục sinh mẫu sẽ sinh ra các ứng cử mẫu mới bằng cách khai thác kho văn bản đang có. Sau đó các ứng cử mẫu sẽ được lọc để loại các ứng cử bị trùng hoặc có độ chính xác thấp. Kết quả đầu ra của thủ tục này ta thu được một tập mẫu mới. Nếu tập mẫu mới thu được là tập rỗng thì giải thuật dừng. Trích chọn tên người Từ điển chức danh Mẫu ban đầu Kho văn bản Ứng cử Tên người Lọc Tên người Sinh ứng cử mẫu và lọc ra các mẫu tốt Tập mẫu mới Trích chọn tên người với mẫu mới Từ điển Họ Hình 6: Mô hình trích chọn tên người 24 5. Từ tập mẫu mới và từ điển họ, thủ tục trích chọn thứ 2 sẽ tìm ra các ứng cử tên mới. Giải thuật quay lại bước 2. Phần dưới đây sẽ mô tả chi tiết các khái niệm, cũng như các thủ tục được trình bày trên hình 7.  Xây dựng thủ công các tập ban đầu Trong tiếng Việt, tên người thường đi sau các chức danh như: ông, bà, anh, chị, giám đốc, tổng giám đốc, giáo viên, học sinh,…do đó, đầu tiên sẽ xây dựng các tập từ điển ban đầu, đây là cách xây dựng thủ công. Tương tự như giải thuật DIPRE đã làm, đó là xây dựng một tập nhỏ dữ liệu (tập seed) ban đầu và trong quá trình tìm các xuất hiện sẽ trích chọn ra các bộ, lưu giữ các ngữ cảnh (ngữ cảnh ở đây chính là các từ đằng trước, đằng sau thực thể), từ đó sinh ra các mẫu, từ các mẫu sẽ lại trích ra được quan hệ mới, đó chính là thực thể mới, thực thể này sẽ lại được lưu vào trong tập seed và vòng lặp lại tiếp tục cho tới khi không còn quan hệ mới nào được tạo ra nữa. Như vậy, hệ thống sẽ có thêm một tập dữ liệu ban đầu chứa tên thực thể người. Tập dữ liệu này được xây dựng một cách thủ công. Do định dạng chuẩn của tên người Việt Nam là nên tập này có thể có dạng , hoặc ở dạng , hoặc ở dạng chuẩn như trên. Ví dụ như: Nam, hoặc Trần Quang Khải hoặc Quang Minh,… tập này sẽ được sử dụng tương tự như trong giải thuật DIPRE đã nói ở trên. Vì tên người rất phổ biến và dễ dàng đưa ra được nên có thể đưa ra một tập từ điển khác chỉ có của người như: Nguyễn, Lê, Trần, Dương, Phùng, Đinh…. Bởi rõ ràng nhận ra rằng khi trong văn bản xuất hiện một từ thuộc là của người thì chắc chắn sau từ đó hoặc không có gì hoặc sẽ có tên người. Ví dụ: “Bạn Nguyễn Minh Châu đã đạt học sinh giỏi trong năm học này.” (8) “Dòng họ Nguyễn là dòng họ nổi tiếng khắp vùng này vì truyền thống hiếu học” (9) Ở câu (8), “Nguyễn Minh Châu” là tên người nhưng ở câu (9), “Nguyễn” ở đây là chỉ về một dòng họ. Chi tiết, cụ thể hơn, có thể xây dựng tập từ điển tên người chứa đầy đủ <tên đệm> thì khi đó, hệ thống chỉ việc đối chiếu, so sánh giữa tập từ điển này với dữ liệu trong văn bản, mẫu (pattern) sẽ được trích ra rất nhanh và cũng rất nhiều. Tuy nhiên, làm việc này sẽ mất thời gian, tốn công sức rất nhiều vì phương pháp thực 25 hiện chỉ là thủ công, lại thêm nữa là thừa bởi, thực chất chỉ cần tập chứa các của tên người cũng đủ để giải quyết bài toán một cách nhanh chóng. Vấn đề mà từ ngữ trong tiếng Việt vẫn hay xảy ra đó là sự nhập nhằng. Tên người có thể trùng với tên địa danh, tên tổ chức. Do đó, để giảm bớt tỉ lệ lỗi của hệ thống, cũng cần xây dựng một tập từ điển các từ có mang nghĩa bắt đầu địa danh, tổ chức như là: công ty, công ty TNHH, tỉnh, thành phố, huyện, làng, xã, nước, quốc gia, ….những từ ngữ này hoàn toàn không phải là quá nhiều, việc xây dựng bằng thủ công là tương đối nhẹ nhàng và đơn giản.  Các tập mẫu của thực thể tên người trong tiếng việt Với tên người thường có giới hạn bởi xâu mang nghĩa như: ông, bà, anh, chị, …và các xâu thuộc như: chạy, nói, học, lái xe, đàn, hát, nhảy,… Do đó, một mẫu phù hợp trích được trong quá trình trích chọn mẫu sẽ gồm có: prefix, personal name, suffix Trong đó: prefix: thường chỉ chức danh của người, những từ thường đứng trước tên người trong văn bản. suffix: thường chỉ động từ, những từ thường đứng sau tên người trong văn bản. personal name: là tên thực thể người xuất hiện trong văn bản. Tên người trong tiếng Việt sẽ được giới hạn bởi các chữ cái trong bảng chữ cái tiếng Việt bao gồm: [A-Ya-y] Viết dưới dạng biểu thức chính quy sẽ là: *prefix, personal name, suffix*  Xây dựng tập mẫu dựa trên các xuất hiện của tập nhỏ thực thể ban đầu hoặc từ các tập từ điển được dựng sẵn, biểu diễn các mẫu dưới dạng biểu thức chính quy Đây là một xử lý quan trọng trong hệ thống bởi mẫu có chính xác bao nhiêu thì thì tỉ lệ lỗi trong quá trình trích chọn sẽ giảm bấy nhiêu. Việc sinh ra mẫu mới có thể được làm như sau: 1. Xác minh lại xem các thành phần prefix và suffix trong tất cả các xuất hiện của các thực thể tên người có giống nhau không. Nếu không thì nó không thể tạo ra 26 mẫu phù hợp với tên người được. Ngược lại, lưu tập prefix và suffix mới vào trong tập các prefix và suffix ban đầu. 2. Thiết lập tập prefix mới (là các prefix đã được trích ra từ các xuất hiện của thực thể ban đầu) với các suffix ban đầu để tìm ra mẫu mới và ngược lại. Thiết lập tập prefix mới (là các prefix đã được trích ra từ các xuất hiện của thực thể ban đầu) với các suffix ban đầu để tìm ra mẫu mới. Ví dụ: Một mẫu mới được tạo thành có prefix mới là: giáo sư suffix mới là giảng dạy Trong khi đó: tập prefix ban đầu có: tiến sĩ tập suffix ban đầu có: nghiên cứu Như vậy, sẽ có một vài mẫu mới được sinh ra, sẽ có: Prefix là: giáo sư – suffix là: nghiên cứu Prefix là: tiến sĩ – suffix là: giảng dạy  Một số đặc trưng riêng của tên người cần chú ý Tên người dạng chuẩn trong các văn bản thường được trình bày dưới dạng các viết hoa các chữ cái đầu câu như: Nguyễn Minh Ngọc, Uyên, Tiến Dũng,… Tên người Việt Nam thường tối đa là một xâu gồm khoảng 5 từ. Mỗi cái tên đều thể hiện cả về mặt thẩm mỹ, do đó, có thể loại bỏ những từ không vô nghĩa, hoặc những nghĩa không hay khi xử lý văn bản, như: đất, ận, bẩn, mèo, chuột, … Thuật toán trích chọn ra mẫu từ tập các mẫu Trước tiên phải xác nhận xem prefix và suffix của tất cả các lần xuất hiện có giống nhau hay không? Nếu không thì không thể tạo ra mẫu mới. 1. Nhóm các lần xuất hiện của thực thể trong tập seed ban đầu theo prefix và suffix. Kết quả đưa ra là một nhóm các mẫu. 27 2. Với mỗi mẫu trong nhóm trên, tạo ra một mẫu mới dựa trên prefix của mẫu mới với suffix của mẫu ban đầu và ngược lại, suffix của mẫu ban đầu với prefix của mẫu mới. Nếu mẫu mới tạo ra trùng với một trong các mẫu ban đầu thì loại bỏ mẫu đó và ngược lại, sẽ lấy mẫu đó thực hiện trích chọn thực thể từ dữ liệu, rồi lại lặp lại như bước 1 cho đến khi không sinh ra được mẫu mới thì dừng. 3.2 Thực nghiệm 3.2.1. Môi trường thực hiện Phần cứng: Máy Celeron III, chip 768 MHz, Ram 512 MB Công cụ lập trình: Eclipse Ngôn ngữ lập trình: Java 3.2.2 Thu thập dữ liệu Sử dụng công cụ teleport download dữ liệu tự động bao gồm 150 bài báo lấy từ nguồn 3.3. Khảo sát và xây dựng thủ công các tập dữ liệu từ điển ban đầu 3.3.1. Tập dữ liệu từ điển ban đầu và tập mẫu Dựa theo ngôn ngữ tiếng Việt, em đã tìm ra các đặc trưng của dữ liệu và tiến hành xây dựng cấu trúc các file input phù hợp. Cụ thể như sau: Tên tập dữ liệu Nội dung prefix.txt Ông|bà|tổng giám đốc… suffix.txt Chạy|nhảy|nói|… ho_diction.txt Nguyễn, Trần, Lê,.. discard.txt Thành phố, đất nước, công ty, công ty TNHH,… seed.txt Lan, Nguyễn Công Minh,… chucdanh.txt Anh, chị, ông, bà, sinh viên, học sinh, giáo sư,…. Bảng 1: Bảng các tập dữ liệu từ điển ban đầu 28 Luật trong prefix.txt Trong prefix.txt chứa các từ, các cụm từ được viết theo từng dòng trong file, thường hay đứng trước tên người. Khi mẫu được sinh ra, chúng sẽ gồm có prefix và suffix. Khi đó, prefix sẽ được lưu vào trong prefix.txt. Chúng được sử dụng để kết hợp các từ hoặc cụm từ trong đó với các từ hoặc cụm từ trong prefix để sinh ra mẫu mới phù hợp. Để từ đó sẽ trích chọn ra tên thực thể phù hợp. Luật trong suffix.txt Tương tự như trong prefix.txt, các xâu trong suffix.txt, được viết theo từng dòng trong file, thường là những động từ miêu tả hành động của con người, thường hay đứng sau tên người. Các xâu này kết hợp với các xâu trong prefix.txt để đưa ra mẫu để trích chọn thực thể tên người. Ví dụ: trong prefix.txt có: ông, bà,… Trong suffix.txt có: tập thể dục, chạy bộ Từ đây, ta có thể có mẫu sinh ra là: [ông, personal name, tập thể dục] [ông, personal name, chạy bộ] [bà, personal name, tập thể dục] [bà, personal name, chạy bộ] Luật trong họ_diction.txt Đây là tập từ điển các họ của tên người. Tập này có tác dụng giúp cho quá trinh trích chọn tên được nhanh chóng hơn, không mất thời gian tìm kiếm quá lâu khi chỉ phụ thuộc vào một ít tập nhỏ trong seed.txt. Ví dụ, khi xử lý dữ liệu trong văn bản, hệ thống sẽ tìm thấy họ “Nguyễn” trong tên “Nguyễn Văn Ba” thì lập tức sẽ trích ra tên đó luôn chứ không cần thiết phải thực hiện tìm kiếm chỉ theo các tên có trong tập nhỏ dữ liệu ban đầu. Luật trong discard.txt Tập này nhằm giải quyết quá trình lọc tên thực thể tránh nhập nhằng bởi trong ngôn ngữ, sẽ xuất hiện nhiều người có tên trùng với tên địa danh, hoặc tên tổ chức. 29 Ví dụ: “Tổng thống Mỹ Obama có chuyến viếng thăm đất nước ta vào ngày 29/10/2009.” Khi đó, nếu ra duyệt thấy từ tổng thống, chắc chắn hệ thống sẽ trích ra tên người là “Mỹ Obama”. Nên để tránh tình trạng trên, ta sẽ buộc phải duyệt qua discard.txt để có thể lọc, bỏ qua tên riêng “Mỹ” và chọn tên “Obama”. Lúc này thì lại áp dụng lặp lại như trong luật prefix.txt. Luật trong chucdanh.txt Với các từ hay cụm từ được dựng sẵn từ prefix.txt, luật này được sử dụng để thực hiện duyệt dữ liệu trong văn bản, kiểm tra xem sau mỗi từ hoặc cụm từ đó, có từ nào viết hoa đầu chữ cái đầu tiên không. Nếu có thì sẽ duyệt tiếp cho tới khi bắt gặp từ có chữ cái đầu tiên viết thường. Sau đó trích ra những từ có chữ cái viết hoa đầu tiên đó, đem so sánh với tập seed.txt. Nếu chưa có thì ta thêm dữ liệu tên đó vào trong tập đó. Nếu có rồi thì ra giữ lấy ngữ cảnh của nó và tiếp tục duyệt tiếp. Việc giữ lại ngữ cảnh để tiếp tục so sánh với các tên khác, xét mối quan hệ giữa chúng và sau đó sẽ lọc mẫu, lưu vào file đó. Luật trong seed.txt Nội dung trong seed.txt là danh sách một số tên người, đó chính là tập dữ liệu nhỏ ban đầu để hệ thống xử lý ban đầu khi đọc dữ liệu từ văn bản. Từ các thông tin trong tập nhỏ ban đầu này, dựa theo phương pháp đã nói đến ở phần trên, hệ thống sẽ tìm ra các xuất hiện của chúng trong văn bản. Từ đó sẽ sinh ra mẫu mới. 3.3.2. Giới hạn vòng lặp Vòng lặp sẽ dừng khi đã duyệt hết đoạn văn bản và các thực thể mới cũng như các mẫu mới không được sinh thêm nữa. 3.4 Đánh giá hệ thống nhận dạng thực thể Các hệ thống nhận biết loại thực thể được đánh giá chất lượng thông qua ba độ đo: độ chính xác (precision), độ hồi tưởng (recall) và độ đo F (F-messure). Ba độ đo này được tính toán theo các công thức sau: 30 missingincorrectcorrect correct Rec ++ = incorrectcorrect correct Pre + = RecPre RecPre F + **2 = Ý nghĩa của các giá trị correct, incorrect, missing và được định nghĩa ở bảng 2. Giá trị Ý nghĩa Correct Số trường hợp gán đúng Incorrect Số trường hợp gán sai Missing Số trường hợp gán thiếu Bảng 2: Các giá trị đánh giá một hệ thống nhận dạng thực thể 3.4.1. Kết quả Kết quả kiểm tra, thực hiện trên 150 trang web, kết quả trích chọn thực thể tên người đưa ra khá khả quan Kết quả thu được cụ thể như sau: Độ đo (%) Số văn bản 50 100 150 P 67.74 78.59 83.56 R 65.68 76.23 80.35 F 66.69 77.39 81.9 31 3.4.2. Đánh giá Qua kết quả, em nhận thấy khi tăng dần các văn bản để xử lý trích chọn thì các độ đo (P,R,F) tăng lên. Tuy nhiên mức độ tăng lên của các độ đo thì chưa được caonhư mong muốn. Khi tăng số văn bản lên 150 thì các độ đo đạt giá trị cao nhất (Độ chính xác P: 83.56%, Độ đo F-measure: 81.9%). Độ chính xác hệ thống nhận dạng thực thể tên người của em chưa đạt được kết quả cao như mong muốn, một phần vì chương trình vẫn còn nhiều thiếu sót, một phần khác do cấu trúc văn bản phức tạp và thay đổi liên tục nên việc áp dụng luật cũng như quá trình sinh mẫu còn gây ra nhiều trường hợp nhập nhằng. 32 Kết luận Những vấn đề đã được giải quyết trong luận văn Khóa luận đã hệ thống hóa một số vấn đề lý thuyết về trích chọn thông tin, bài toán trích chọn thực thể nói chung và trích chọn tên người trong tiếng Việt nói riêng. Đồng thời khóa luận cũng đã trình bày, phân tích, đánh giá một số hướng tiếp cận bài toán nhận biết loại thực thể. Khóa luận đã nêu ra một số vấn đề và giải pháp đối với bài toán nhận biết thực thể tên người trong văn bản tiếng Việt trên môi trường Web dựa trên giải thuật DIPRE của Brin , tuy rằng thực nghiệm và thu được một số kết quả chưa được như mong muốn. Sau đây là một số nét chính mà luận văn đã tập trung giải quyết. Chương 1 đưa ra một cái nhìn khái quát về trích chọn thông tin, bài toán nhận biết loại thực thể nói chung và bài toán trích chọn thực thể tên người nói riêng cho văn bản tiếng Việt trên môi trường Web cùng những ứng dụng thực tế của nó. Chương 2 xem xét các hướng tiếp cận khác nhau để nhằm giải quyết bài toán nhận diện loại thực thể, đó là các phương pháp thủ công, phương pháp HMM, phương pháp MEMM. Chương này đi sâu vào phân tích đánh giá từng phương pháp, cho thấy sự thiếu linh hoạt của các phương pháp thủ công, sự nghèo nàn của các thuộc tính được chọn trong mô hình HMM và vấn đề “label bias” mà các mô hình MEMM gặp phải. Đồng thời đi sâu vào tìm hiểu giải thuật DIPRE, ưu và nhược điểm của nó để áp dụng vào giải quyết các vấn đề liên quan tới khóa luận. Chương 3 trình bày hệ thống trích chọn tên người trong văn bản tiếng Việt. Chương này cũng đưa ra các kết quả của hệ thống nhận diện loại thực thể tiếng Việt qua một số lần thực nghiệm. Công việc nghiên cứu trong tương lai Mặc dù kết quả phân loại thực thể của hệ thống có thể tốt hơn nữa nhưng do thời gian có hạn nên em mới chỉ dừng lại ở con số của F1 là 81%, trong thời gian tới, em sẽ tiếp tục nghiên cứu nhằm cải thiện hệ thống, em tin rằng kết quả này có thể tăng lên mức cao hơn. Trên cơ sở hệ thống nhận diện loại thực thể tiếng Việt hiện nay, em dự định sẽ mở rộng và nghiên cứu thêm nhiều hướng nghiên cứu khác trong văn bản tiếng Việt, chẳng hạn ngoài việc trích chọn tên người, ta có thể trích chọn thêm chức danh của 33 người đó trong văn bản. Ví dụ: từ câu “Giáo sư Ngô Thúc Lanh vừa mới …” thì cặp thông tin hữu ích có thể trích chọn ra là . Hoặc hướng tới trích chọn tên người nước ngoài trong văn bản Việt Nam vì định dạng tên người nước ngoài khác với tên người Việt Nam. Ví dụ: Richard C. Wang, Xiao-Long Wang, … Vì tên người Việt không có kèm theo dấu ngắt câu như trong cách mà người nước ngoài viết tên, do đó, vấn đề này cũng là một vấn đề đáng để quan tâm. 34 Tài liệu tham khảo Tài liệu tham khảo tiếng Việt [1] Mai Ngọc Chừ; Vũ Đức Nghiệu & Hoàng Trọng Phiến. Cơ sở ngôn ngữ học và tiếng Việt. Nxb Giáo dục, H., 1997, trang 142–152. [2] Nguyễn Việt Cường. Bài toán lọc và phân lớp nội dung Web tiếng Việt với hướng tiếp cận Entropy cực đại. Luận văn tốt nghiệp ĐHCN 2005 [3] Trần Thị Oanh. Thuật toán Self-Training và Co-Training ứng dụng trong phân lớp văn bản. Luận văn tốt nghiệp ĐHCN năm 2006 [4] Nguyễn Cẩm Tú. Nhận biết các loại thực thể trong văn bản tiếng Việt nhằm hỗ trợ Web ngữ nghĩa và tìm kiếm hướng thực thể. Luận văn tốt nghiệp ĐHCN 2005 [5] Website tiếng Việt nói về xử lý ngôn ngữ tự nhiên: Tài liệu tham khảo tiếng Anh [6] A. McCallum, D. Freitag, and F. Pereia. Maximum entropy markov models for information extraction and segmentation. In Proc. Interational Conference on Machine Learning, 2000 [7] Adam Berger. The Improved Iterative Scaling Algorithm: A gentle Introduction. School of Computer Science, Carnegie Mellon University [8] Andrew McCallum. Efficiently Inducing Features of Conditional Random Fields. Computer Science Department. University of Massachusetts [9] Andrew McCallum, Khashayar Rohanimanesh, and Charles Sutton. Dynamic Conditional Random Fields for Jointly Labeling Multiple Sequences. Department of Computer Science, University of Massachusetts [10] H. M. Wallach. Efficient training of conditional random fields. Master’s thesis, University of Edinburgh, 2002 [11] Hana Wallach. Efficient Training of Conditional Random Fields. M.Sc. thesis, Division of Informatics, University of Edinburgh, 2002. [12] J. Lafferty, A. McCallum, and F. Pereia. Conditional ramdom fields: probabilistic models for segmenting and labeling sequence data. In International Conference on Machine Learning, 2001 [13] Ralph Grishman. Information extraction: Techniques and challenges. In Information Extraction (International Summer School SCIE-97). Springer- verlag, 1997. 35 [14] Ronald Schoenberg. Optimization with the Quasi-Newton Method, September 5, 2001. [15] Cvetana Krstev, Du_sko Vitas and Sandra Gucul. Recognition of Personal Names in Serbian Texts. Faculty of Philology, University of Belgrade, Studentski trg 3, Faculty of Mathematics, University of Belgrade, Studentski trg 16, Belgrade, Serbia & Montenegro. [16] Feng Zhang, Liu Wenyin, Zheng Chen. A New Statistical Approach to Personal Name Extraction. [17] Serey Brin Extracting Patterns and Relation from World – Wide –Web. In Proceedings of the 1998 International Work-shop in the Web and Databased, March. [18] Sunita Sarawagi, William W. Cohen. Semi-Markov Conditional Random Fields for Information Extraction. [19] Trausti Kristjansson, Aron Cullota, Paul viola, Adrew McCallum. Interactive Information Extraction with Constrained Conditionial Random Fields. [20] William Cohen. Integration of heterogeneous databases without common domains using queries based on textual similarity. In Proceedings of the 1998 ACM International Conference on Management of Data (SIGMOD’98), 1998. [21] Yi-Feng Lin, Tzong-Han Tsai, Wen-Chi Chou, Kuen-Pin Wu, Ting-Yi Sung and Wen-Lian Hs. A Maximum Entropy Approach to Biomedical Named Entity Recognition. Institute of Information Science, Academia Sinica, 2004. [22] Ying Yu, Xiao-Long Wang, Yi Guan. Information Extraction for Chinese Free Based Pattern Match Combine with Heuristic Information. School of Computer Science and Technology, Harbin Institude of Technology, Harbin150006, China.