LUẬN VĂN: TRÍCH CHỌN THỰC THỂ TÊN NGƯỜI TRONG TIẾNG VIỆT

Chia sẻ: Lan Lan | Ngày: | Loại File: PDF | Số trang:43

Thêm vào BST

Báo xấu

211
lượt xem 50
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: LUẬN VĂ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
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 i
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. ii
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 iii
Kết luận ................................................................ ................................ ..................... 32 Tài liệu tham khảo ..................................................................................................... 34 iv
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 v
Danh sách hình vẽ vi
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 1
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. 2
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 3
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. 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 NAME TITLE ORGANIZATION open- source concept, by which software code is made public to IE Bill Gates CEO Microsoft Corporation encourage improvement and development by outside programmers. Gates himself says Microsoft will gladly Bill Veghte VP Microsoft disclose its crown jewels-the coveted code behind the W indows opertating Richard Stallman founder Free Software Foundation 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 F oundation, countered saying… Hình 1: Mô hình trích chọn thực thể 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), 4
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ó 5
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 h ay 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 n gữ 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. 6
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 7
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”. 8
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ư 9
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: S  {S1 ,S2 ,...,Sn } - 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: O  {O1 ,O 2 ,...,On } - 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: P (S ,O ) P (S | O )  P (O ) Ta có thể mô hình hóa HMM dưới dạng một đồ thị có hướng như sau: S1 S2 S3 Sn-1 Sn O1 O2 O3 On-1 On Hình 2 : Ví dụ về mô hình Markov Ở đâ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 P(S , O)  P(S1 )  P(O1 | S1 ) P(St |S t 1) * P(Ot | St ) t 2 10
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 P(Si | Si 1 , Oi ) để 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. S1 S2 S3 Sn-1 Sn O1 O2 O3 On-1 On Hình 3 : Đồ thị có hướng mô tả một mô hình MEMM Xác su ất P(S|O) được tính theo công thức:   1 expk fk (ot , st ) P(st | st1, ot ) Pt1 (st | ot )   s Z(ot , st1)  k  11
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 đó: 1 nếu b (Ot) =1 và St=St-1 Fk (Ot,St)= 0 n ếu ngược lại 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” i_ r_ b:rib 1 2 rib 3 0 4 5 o:_ r_ b: rob Hình 4: Vấn đề Label Bias 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 12