Khóa luận So sánh một số phương pháp học máy cho bài toán gán nhãn từ loại tiếng Vệt

x[ (t )× P(w | t )× P(t | t )]         (2.9) Một trong những bộ gán nhãn tiêu biểu sử dụng phương pháp này là bộ gán nhãn TnT của tác giả Thorsten Brants sử dụng phương pháp tri-gram, cho kết quả 96.7% với tập nhãn Penn TreeBank và bộ dữ liệu WallStreet trong tiếng Anh [16]. QTAG là một bộ gán nhãn dựa trên mô hình HMM do nhóm nghiên cứu Corpus Research thuộc trường đại học tổng hợp Birmingham phát triển, cung cấp miễn phí cho mục đích T1 T2 T3 Tn-1 Tn W1 W 2 W 3 W n-1 W n ( | ... ) ( | )i 1 1 i 1 i 1 i i iP w w t w t t P w t   ( | ... ) ( | )i 1 1 i 1 i 1 i i-2 i-1P t w t w t P t t t   ( ) ( | ) ( | )[ ( | )] n n 1 2 1 i i-2 i-1 i i i 3 i 1 P t P t t P t t t P w t     18 nghiên cứu. Một điểm nổi trội của QTAG là dù được xây dựng cho tiếng Anh nhưng nó có thể được huấn luyện để sử dụng cho các ngôn ngữ khác [3]. Phương pháp xác suất còn được sử dụng để gán nhãn từ loại trong rất nhiều ngôn ngữ khác nhau, ví dụ việc áp dụng mô hình HMM cho bài toán gán nhãn từ loại tiếng Trung Quốc đạt đến 93.5 % trong nghiên cứu của các tác giả GouDong Zhou và Jian Su [20]; Hai tác giả Fábio N.Kepler và Marcelo Finger cũng công bố kết quả sử dụng mô hình HMM để gán nhãn từ loại cho tiếng Bồ Đào Nha với kết quả 93.48 % [18]. Tuy nhiên, mặc dù tính đến thời điểm hiện tại, đây là một trong những phương pháp gán nhãn theo phương pháp xác suất thông dụng nhất được biết đến nhưng nó vẫn còn tiềm tàng những giới hạn khó giải quyết. Adrew McCallum trong các nghiên cứu của mình [10] đã đưa ra hai vấn đề mà các mô hình HMM truyền thống nói riêng và các mô hình sinh (generative models) nói chung gặp phải khi gán nhãn cho dữ liệu dạng chuỗi.  Thứ nhất, để có thể tính được xác suất P(T, W) (2.1), thông thường ta phải liệt kê hết các trường hợp có thể của chuỗi T và chuỗi W. Nếu như các chuỗi T có thể liệt kê được vì số lượng các trạng thái là có hạn thì trong nhiều ứng dụng ta không thể nào liệt kê hết được các chuỗi W vì dữ liệu quan sát là hết sức phong phú và đa dạng. Để giải quyết vấn đề này, HMM phải đưa ra giả thiết về sự độc lập giữa các dữ liệu quan sát, đó là dữ liệu quan sát được tại thời điểm i chỉ phụ thuộc trạng thái tại thời điểm đó. Tuy nhiên giả thiết này không có trong thế giới thực vì vậy khi áp dụng nó trong các hệ thống thực tế sẽ khó tránh khỏi một yếu tố bất lợi như thiếu tính mềm dẻo, bỏ sót thuộc tính ...  Vấn đề thứ hai mà các mô hình sinh gặp phải khi áp dụng vào các bài toán phân lớp dữ liệu dạng chuỗi đó là chú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(T|W) trực tiếp thay vì P (T,W) như trong công thức (2.1). Ngoài HMM, còn rất nhiều phương pháp xác suất khác có thể sử dụng để giải quyết bài toán gán nhãn từ loại nói chung và bài toán gán nhãn từ loại tiếng Việt nói riêng, nhiều trong số chúng có những ưu điểm giải quyết được các hạn chế của mô hình HMM mà ta đã nói ở trên. Cùng với đó, bên cạnh các phương pháp học máy xác suất, còn có các phương pháp học máy khác, ví dụ phương pháp học máy dựa trên độ đo, phương pháp sử dụng mạng nơ ron nhân tạo, …. Các chương sau sẽ trình bày rõ hơn về ba phương pháp học máy tiêu biểu đã đạt được kết quả khả quan khi áp dụng 19 cho bài toán gán nhãn từ loại trong các ngôn ngữ khác, đó là mô hình cực đại hóa Entropy MEM, mô hình miền ngẫu nhiên điều kiện CRF và mô hình máy véc tơ hỗ trợ SVM. 2.3. Phương pháp lai Đại diện tiêu biểu của phương pháp lai là phương pháp dựa trên học chuyển đổi (Transformation-Based learning TBL) [6], đây là một phương pháp học có giám sát, đòi hỏi một tập ngữ liệu đã được gán nhãn. Phương pháp này sử dụng đặc tính của cả hai kiến trúc gán nhãn nói trên. Giống như bộ gán nhãn dựa trên luật, nó dựa vào luật để xác định khi một từ nhập nhằng thì nó có khả năng là một nhãn nào nhất. Giống như bộ gán nhãn xác suất, nó có một thành phần học máy để tạo ra các luật một cách tự động từ một bộ dữ liệu huấn luyện đã được gán nhãn trước. Ý tưởng chính của thuật toán này là bắt đầu với một vài giải pháp đơn giản (hoặc tinh vi) cho vấn đề (gọi là “baseline tagging”) và từng bước áp dụng những luật biến đổi (luật chuyển) tối ưu (tìm ra từ tập ngữ liệu huấn luyện đã được đánh dấu chính xác) để dần dần giải quyết vấn đề (tức là chuyển từ nhãn không chính xác sang nhãn chính xác). Quá trình này sẽ dừng lại khi không còn luật chuyển tối ưu nào được lựa chọn hoặc đã hết dữ liệu. Hình 5 cho ta mô hình tổng quát của phương pháp lai. Hình 5. Mô hình tổng quát của phương pháp lai Dữ liệu chưa gán nhãn Trạng thái bắt đầu Dữ liệu đã gán nhãn “Sự thật” Các luật Bộ học 20 Thuật toán bao gồm 5 bước [6]  Bước 1: Gán nhãn cho từng từ bằng nhãn thông dụng nhất.  Bước 2: Chọn một phép chuyển có tính quyết định thay thế nhãn đã gán bằng nhãn mới mà kết quả đem lại có hệ số đánh giá lỗi thấp hơn (Đánh giá một phép chuyển bằng hệ số đánh giá lỗi thực chất là so sánh nó với “sự thật”).  Bước 3: Áp dụng phép chuyển này cho cả tập huấn luyện.  Bước 4: Thực hiện lại các bước trên  Bước 5: Đưa ra kết quả là một bộ gán nhãn mà nhãn đầu tiên sử dụng unigrams, sau đó áp dụng phép chuyển đã được “học” ở trên theo thứ tự. Ví dụ về một số luật chuyển thường được áp dụng cho phương pháp lai được cho bởi bảng 4 [6]. Bảng 4. Ví dụ về một số luật chuyển của TBL cho tiếng Anh Chuyển nhãnS TT Cũ Mới Điều kiện Ví dụ 1 2 3 4 5 NN VBP NN VB VBD VB VB VB NN VBN Nhãn trước đó là TO 1 trong 3 nhãn trước đó là MD 1 trong 2 nhãn trước đó là DT 1 trong 3 nhãn trước đó là VBZ To/TO race/NNVB Might/MD vanish/VBPVB Might/MD not reply/NNVB Ví dụ: Xét từ “race” trong hai câu dưới đây - It is expected to race tomorrow. - The race for outer space. Thuật toán sẽ thực hiện như sau:  Đầu tiên, gán nhãn tất cả các từ “race” là NN (nhãn thường gặp nhất trong tập ngữ liệu Brown corpus). Tức là: “It is expected to race/NN tomorrow” “The race/NN for outer space” 21  Sau đó, sử dụng luật biến đổi để thay thế các nhãn NN bằng VB cho tất cả các từ “race” mà đứng trước nó là từ được gán nhãn TO. Tức là: “It is expected to race/VB tomorrow” Và “The race/NN for outer space” Đại diện tiêu biểu cho phương pháp này là bộ gán nhãn từ loại Brill’s (được xây dựng bởi Eric Brill) sử dụng cho tiếng Anh, đây là một bộ gán nhãn rất thông dụng vì các ưu điểm của nó như miễn phí, đem lại kết quả khá khả quan (Độ chính xác là 96.6% cho tập ngữ liệu Wall Street Journal). 2.4. Các nghiên cứu liên quan tại Việt Nam Bài toán gán nhãn từ loại cho tiếng Việt bắt đầu được quan tâm khá muộn so với tiếng Anh, tuy gặp phải không ít khó khăn vì những đặc trưng phức tạp riêng của tiếng Việt, nhưng việc nghiên cứu lại có một lợi thế rất lớn là tiếp thu được những thành quả nghiên cứu đã được áp dụng cho tiếng Anh nói riêng và trên thế giới nói chung. Phần này sẽ điểm qua một vài nghiên cứu tiêu biểu liên quan đến bài toán gán nhãn từ loại tiếng Việt. 2.4.1. Các nghiên cứu dựa trên phương pháp hệ luật Nhằm phát huy tác dụng hữu ích của phương pháp dựa trên hệ luật khi được sử dụng bằng cách kết hợp bổ sung với các phương pháp khác, nhóm nghiên cứu gồm các tác giả Nguyễn Quang Châu, Phan Thị Tươi, Cao Hoàng Trụ đã đề xuất một phương pháp 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 [2]. Nhóm tác giả xây dựng một hệ thống kết hợp bộ gán nhãn tri-gram và bộ gán nhãn dựa trên văn phong. Phương pháp gán nhãn từ loại dựa trên văn phong thực chất là căn cứ vào cách thể hiện của văn bản trong một ngữ cảnh cụ thể để xác định từ loại cho các từ, điều này bao hàm việc xác định phải đảm bảo các luật văn phạm của các từ trong câu. Để xây dựng hệ thống luật này, nhóm tác giả dựa vào JAPE (Java Annotation Patterns Engine), hệ thống luật gồm trên 270 luật để xác định cho 48 từ loại (danh từ riêng, đại từ xưng hô, danh từ loại thể, ...) và các luật để xác định các kiểu ngày tháng năm (date). Phương pháp dựa trên văn phong áp dụng các luật xác định danh từ riêng, trên cơ sở các danh từ riêng được xác định, tiếp tục áp dụng các luật để xác định 48 nhãn từ loại còn lại. 22 Nhóm các tác giả tiến hành thử nghiệm trên một bộ dữ liệu khoảng hơn 70.000 từ thuộc các văn bản về lĩnh vực văn học, báo chí... Nghiên cứu thực nghiệm sử dụng tập nhãn gồm 48 nhãn từ loại với 10 miền giới hạn. Kết quả thử nghiệm tốt nhất với các tập mẫu đã xây dựng đạt tới độ chính xác ~80% nếu chỉ dùng phương pháp gán nhãn bằng xác suất (P1) và đạt ~90% nếu dùng phương pháp gán nhãn dựa trên văn phong kết hợp với phương pháp xác suất (P2). Bảng 5 cho ta kết quả gán nhãn cho các văn bản, văn phong khác nhau. 2.4.2. Các nghiên cứu dựa trên phương pháp học máy Nghiên cứu theo hướng giải quyết bài toán gán nhãn từ loại tiếng Việt bằng phương pháp xác suất, nhóm nghiên cứu của tác giả Nguyễn Thị Minh Huyền [3] đã sửa đổi phần mềm QTAG được xây dựng cho tiếng Anh (do nhóm nghiên cứu Corpus Research thuộc trường đại học tổng hợp Birmingham phát triển) để thích nghi với việc thao tác trên văn bản tiếng Việt, cũng như cho phép sử dụng từ điển từ vựng có thông tin từ loại bên cạnh việc sử dụng kho văn bản đa gán nhãn. Bộ gán nhãn QTAG là một bộ gán nhãn tri-gram, sử dụng phương pháp gán nhãn xác suất, QTAG sử dụng từ điển từ vựng gồm 37454 mục từ, mỗi mục từ có kèm theo dãy tất cả các từ loại mà nó có thể có. VNQTAG được huấn luyện và kiểm thử bằng các văn bản thuộc một số thể loại khác nhau (văn học Việt Nam/nước ngoài, khoa học, báo chí), bao gồm 63732 lượt từ, sử dụng hai bộ nhãn từ loại với độ mịn khác nhau: bộ thứ nhất gồm 9 nhãn từ vựng và 10 nhãn cho các loại kí hiệu, bộ nhãn thứ hai gồm 48 nhãn từ vựng và 10 nhãn cho các loại kí hiệu. Kết quả thử nghiệm tốt nhất với các tập mẫu đa xây dựng đạt tới độ chính xác ~94% đối với bộ nhãn thứ nhất, trong khi với bộ nhãn thứ hai chỉ đạt tới ~85%. 2.4.3. Các nghiên cứu dựa trên phương pháp lai Một nghiên cứu khác cũng dựa trên nền tảng của phương pháp học máy là công trình xây dựng công cụ gán nhãn từ loại tiếng Việt JvnTagger, đây là nghiên cứu nằm trong khuôn khổ đề tài cấp nhà nước VLSP được thực hiện bởi nhóm các tác giả Phan Xuân Hiếu, Nguyễn Cẩm Tú. JvnTagger dựa trên mô hình CRF và MEM và được cài đặt bằng ngôn nhữ Java. Công cụ này được huấn luyện bằng dữ liệu khoảng 10.000 câu của Viet Treebank và sử dụng tập nhãn Viet Treebank. Tuy công cụ chưa được đưa vào ứng dụng thực tế, nhưng theo các báo cáo kỹ thuật mà nhóm tác giả cung cấp thì thử nghiệm với phương pháp 5-fold cross validation cho thấy kết quả gán nhãn với CRFs có thể đạt giá trị F1 lớn nhất lài 90.40% và MaxEnt đạt giá trị F1 lớn nhất là 91.03%. 23 Ngoài ra còn có nhiều nghiên cứu khác theo hướng dựa trên phương pháp học máy để giải quyết bài toán gán nhãn từ loại. Có thể kể đến hệ thống tích hợp tách từ và gán nhãn từ loại của tác giả Trần Thị Oanh xây dựng năm 2008. Tác giả đã thiết kế bộ nhãn VnPOS tag cho tiếng Việt gồm 14 nhãn từ và hơn 10 nhãn ký hiệu, thực nghiệm được tiến hành trên bộ dữ liệu khoảng 8000 câu thu thập từ các báo điện tử với nhiều chủ đề khác nhau. Việc gán nhãn từ loại được tiến hành bằng phương pháp MEM với hai cách tiếp cận ở mức từ và mức hình vị. Kết quả đạt được ở mức từ là 85.57% và 89.22% ở mức hình vị. Áp dụng phương pháp lai TBL, Ðinh Ðiền và các cộng sự đã đề xuất một phương pháp gán nhãn từ loại tự động cho Tiếng Việt [6] bằng việc xây dựng kho ngữ liệu song ngữ Anh-Việt (EVC) với hơn 500.000 câu mà trong đó hơn 25.000 câu tiếng Việt đã được gán nhãn từ loại chính xác nhờ kết quả liên kết từ Anh-Việt và phép chiếu từ loại từ Anh sang Việt (Tập nhãn tiếng Anh sử dụng để đối chiếu là Brown corpus, kho ngữ liệu này đã được công bố ở Hội nghị Quốc tế về Xử lý ngôn ngữ APIS02 tại Bangkok, Thái Lan vào 2/2002). Đây chính là điểm nổi bật của phương pháp gán nhãn từ loại này. Thuật toán TBL sử dụng trong nghiên cứu được các tác giả thể hiện dưới dạng sơ đồ khối như trên hình 6. Nhóm tác giả đã áp dụng thử nghiệm mô hình này và bước đầu nhận được kết quả trên 80%. Như vậy, có thể thấy rằng bài toán gán nhãn từ loại cho tiếng Việt đang ngày càng được quan tâm nghiên cứu, bước đầu đã đạt được một số kết quả khá khả quan. Tuy nhiên đây vẫn là hướng nghiên cứu đầy tiềm năng và cũng đầy thử thách, cùng với đó là việc các nghiên cứu đã có hầu hết vẫn còn mang tính cá thể, chưa có được sự đối chiếu so sánh khách quan. Khóa luận này sẽ tập trung vào việc áp dụng và so sánh kết quả của một số phương pháp tiên tiến được sử dụng thành công cho các ngôn ngữ khác trên cùng một môi trường thực nghiệm và cách lấy đặc trưng để đưa ra nhận xét về ưu, nhược điểm cũng như độ phù hợp của chúng với tiếng Việt. 24 Hình 6. Mô hình TBL cho tiếng Việt Như vậy, có khá nhiều phương pháp học máy đã được áp dụng để giải quyết bài toán gán nhãn từ loại tiếng Việt. Tuy bước đầu đạt được một số kết quả khả quan, nhưng hầu hết các nghiên cứu đều mang tính cá thể, sử dụng bộ dữ liệu học cũng như tập đặc trưng khác nhau. Trong khóa luận này, chúng tôi thực hiện so sánh một vài phương pháp học máy điển hình trên cùng một bộ dữ liệu và sử dụng cùng tập đặc trưng. Từ kết quả thu được, chúng tôi tiến hành đánh giá các phương pháp trên một vài yêu tố, cũng như xem xét độ phù hợp của tập đặc trưng đã sử dụng đối với tiếng Viêt. Word aligned bilingual SUSANNE corpus Remove POS-tags Unannotated Vietnamese corresponding POS-tags Brown POS- tagger Current annotated corpus Templates Candidate Transformation Rule Optimal Rule mark > β End Sequence of Optimal rule Corpus annotated Compare & Evaluate Y N 25 Chương 3. BA MÔ HÌNH HỌC MÁY ÁP DỤNG CHO BÀI TOÁN GÁN NHÃN TỪ LOẠI TIẾNG VIỆT Việc khảo sát các phương pháp học máy được áp dụng thành công cho nhiều ngôn ngữ (chủ yếu là khảo sát các phương pháp đã được sử dụng cho 3 ngôn ngữ tiêu biểu là tiếng Anh, tiếng Trung Quốc và tiếng Thái) cho thấy có khá nhiều phương pháp học máy có thể áp dụng cho bài toán gán nhãn từ loại Tiếng Việt. Khóa luận lựa chọn ba phương pháp học máy điển hình đã cho kết quả khả quan ở nhiều ngôn ngữ và có khả năng đạt kết quả tốt đối với tiếng Việt, đó là MEM, CRF và SVM. Cơ sở lý thuyết ở chương này sẽ là nền tảng cho phần thực nghiệm để đưa ra đánh giá về độ chính xác cũng như phù hợp của các phương pháp này với Tiếng Việt. Trong các thực nghiệm thuộc phạm vi khóa luận, bài toán gán nhãn từ loại được xem là bài toán phân lớp, với các lớp chính là các nhãn từ loại đã được xác định trước. 3.1. Mô hình cực đại hóa Entropy Mô hình cực đại hóa Entropy (Maximum Entropy Model - MEM) [4, 15, 25] là một mô hình dựa trên lý thuyết xác suất, được đề xuất lần đầu bởi Jaynes E.T. từ năm 1957. Theo [25], MEM giải quyết tốt ba yêu cầu chủ yếu của xử lý ngôn ngữ tự nhiên, đó là: Độ chính xác, đặc trưng thiếu tri thức và khả năng tái sử dụng. Phần này sẽ giới thiệu về bản chất lý thuyết, mô hình xác suất và một số mặt còn hạn chế của MEM. 3.1.1. Khái niệm MEM Tư tưởng chính của phương pháp cực đại hóa Entropy là “ngoài vệc thỏa mãn một số ràng buộc nào đó thì mô hình càng đồng đều càng tốt” [25]. Để rõ hơn về vấn đề này, thử xem xét trong trường hợp một bài toán gán nhãn từ loại gồm có 8 nhãn từ loại. Giả sử chúng ta có một ràng buộc duy nhất: 80% các từ có ký tự đầu của các hình vị viết hoa là danh từ riêng (Np). Trực quan cho thấy, nếu có một từ mà tất cả ký tự đầu của các hình vị tạo nên nó là viết hoa thì chúng ta có thể nói có 80% khả năng từ này thuộc lớp danh từ riêng, và 20% khả năng được chia đều cho 7 lớp còn lại. Mặc dù MEM có thể được dùng để ước lượng bất kì một phân phối xác suất nào, khóa luận sẽ tập trung xem xét khả năng làm cực đại hóa entropy cho việc gán nhãn dữ liệu dạng chuỗi. Nói cách khác, ta tập trung vào việc học ra phân phối điều kiện của chuỗi nhãn tương ứng với chuỗi (xâu) đầu vào cho trước 26 Như vây, bản chất lý thuyết của MEM là chọn một phân bố xác suất p theo một đặc trưng ràng buộc nào đó. Phân bố được chọn là phân bố làm cực đại hóa độ hỗn loạn thông tin trong một tập các thực thể được gán nhãn. 3.1.2. Nguyên lý cực đại hóa Entropy Cực đại hóa Entropy là một nguyên lý 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. Entropy là độ đo về 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. Độ đ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 một chuỗi dữ liệu quan sát” p(y|x) có dạng sau  yx xyxyx , )|(log*)|(*)(~)( ppppH (3.1) Tư tưởng chủ đạo 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 đó tuân theo mọi giả thiết đã biết từ thực nghiệm và ngoài ra không đưa thêm bất kì một giả thiết nào khác”. Điều này có nghĩa là 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. Nói theo ngôn ngữ toán học, ta phải tìm phân phối mô hình p(y|x) thỏa mãn hai điều kiện, một là nó phải thuộc tập P’ và hai là nó phải làm cực đại Entropy điều kiện (3.1). Vớ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à P’ là tập con của P, P’ được xác định như sau:   nifEfEPpP ipip ...,3,2,1)()(|' ~  3.1.3. Mô hình xác suất Theo [4, 15] mô hình xác suất được định nghĩa theo không gian H x T, trong đó H là tập từ có thể và ngữ cảnh từ loại, hoặc còn gọi là “lịch sử”, và T là tập các nhãn có thể có. Xác suất mô hình của lịch sử h cùng với nhãn t được định nghĩa theo công thức 3.2:    k j thf j jthp 1 ),(),(  (3.2) Trong đó, ∏ là hằng số chuẩn hóa, {µ, α1, … αk} là các tham số mang giá trị dương của mô hình và {f1, …, fk} chính là các đặc trưng, thỏa mãn fj (h,t){0, 1}. Chú ý rằng mỗi tham số aj tương ứng với một đặc trưng fj. 27 Cho trước một tập các từ {w1, …, wn} và một chuỗi nhãn {t1, …, tn} được xem là dữ liệu huấn luyện, ta định nghĩa hi là lịch sử khi dự đoán nhãn ti. Các tham số {µ, α1, … αk} được chọn sao cho làm cực đại likelihood dữ liệu huấn luyện sử dụng p theo công thức (3.3)      n i k j thf j n i ii iijthppL 1 1 ),( 1 ),()(  (3.3) Mô hình này được xem xét dưới dạng Maximum Entropy, trong đó mục tiêu là cực đại entropy của một phân phối dưới những ràng buộc nhất định. Ở đây, entropy của phân phối p được định nghĩa theo công thức (3.4) , ( ) ( , ) ( , ) h H t H p p h t logp h t      (3.4) Và các ràng buộc được cho bởi công thức (3.5) ,i jEf Ef 1 j k   (3.5) Trong đó kỳ vọng đặc trưng của mô hình là (3.6) ),(),( , thfthpEf tHh ji     (3.6) và kỳ vọng đặc trưng quan sát là (3.7)    n i iijiii thfthpfE 1 ),(),(~~ (3.7) Trong đó ),(~ ii thp là xác suất của (hi, ti) trong dữ liệu huấn luyện. Vì thế, các ràng buộc này sẽ ép buộc mô hình phải đáp ứng được yêu cầu phù hợp tương ứng giữa các kỳ vọng đặc trưng đó với kỳ vọng đặc trưng quan sát trong dữ liệu huấn luyện. 3.1.4. Hạn chế của mô hình MEM Mặc dùng mô hình MEM có những ưu điểm về độ chính xác, đặc trưng thiếu tri thức và khả năng tái sử dụng, nhưng trong một số trường hợp đặc biệt, MEM cũng như 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” [10]. Vấn đề “label bias” là vấn đề do các trạng thái có phân phối chuyển với entropy thấp (ít đường đi ra) có xu hướng ít chú ý hơn đến quan sát hiện tại, mô hình MEM gặp phải vấn đề này tức là không xác định được nhánh rẽ đúng, điều này sẽ có ảnh hưởng đến kết quả mà nó đạt được. 28 Năm 1991, Léon Bottou đưa ra hai giải pháp cho vấn đề “label bias”.Giải pháp thứ nhất là gộp các trạng thái và trì hoãn việc rẽ nhánh cho đến khi gặp một quan sát xác định. Đây chính là trường hợp đặc biệt của việc chuyển một ô-tô-mát không đơn định sang một automata đơn định. Nhưng vấn đề ở chỗ ngay cả khi có thể thực hiện việc chuyển đổi này thì cũng gặp phải sự bùng nổ tổ hợp các trạng thái của automata. Giải pháp thứ hai mà Bottou đưa ra là chúng ta sẽ bắt đầu mô hình với một đồ thị đầy đủ của các trạng thái và để cho thủ tục huấn luyện tự quyết định một cấu trúc thích hợp cho mô hình.Tiếc rằng giải pháp này sẽ làm mất đi tính có thứ tự của mô hình, một tính chất rất có ích cho các bài toán trích chọn thông tin . Một giái pháp đúng đắn hơn cho vấn đề này là xem xét toàn bộ chuỗi trạng thái như một tổng thể và cho phép một số các bước chuyển trong chuỗi trạng thái này đóng vai trò quyết định với việc chọn chuỗi trạng thái. Điều này có nghĩa là xác suất của toàn bộ chuỗi trạng thái sẽ không phải được bảo tồn trong quá trình chuyển trạng thái mà có thể bị thay đổi tại một bước chuyển tùy thuộc vào quan sát tại đó . 3.2. Mô hình trường ngẫu nhiên điều kiện Mô hình trường ngẫu nhiên điều kiện CRF (Conditional Random Fields) [4, 10, 19] được giới thiệu lần đầu vào năm 2001 bởi Lafferty và các đồng nghiệp. CRF là mô hình dựa trên xác suất điều kiện, nó có thể tích hợp được các thuộc tính đa dạng của chuỗi dữ liệu quan sát nhằm hỗ trợ cho quá trình phân lớp. Tuy vậy, khác với các mô hình xác suất khác, 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 các mô hình đồ thị có hướng khác. Bản chất “phân phối điều kiện” và “phân phối toàn cục” của CRF cho phép mô hình này khắc phục được những nhược điểm của các mô hình trước đó trong việc gán nhãn và phân đoạn các dữ liệu dạng chuỗi mà tiêu biểu là vấn đề ‘label bias’. Phần này sẽ đưa ra định nghĩa CRF, lựa chọn các “hàm tiềm năng” cho các mô hình CRF, thuật toán Viterbi cải tiến để tìm chuỗi trạng thái tốt nhất mô tả một chuỗi dữ liệu quan sát cho trước và một số phương pháp để ước lượng các tham số cho mô hình CRF. 3.2.1. Khái niệm CRF Kí hiệu 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 và 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à 29 một biến ngẫu nhiên nhận gía trị trong tập hữu hạn các trạng thái S. Trong bài toán gán nhãn từ loại, X có thể nhận giá trị là các câu trong ngôn ngữ tự nhiên (gồm các từ), Y là một chuỗi ngẫu nhiên các nhãn tương ứng với các từ tạo thành câu này và mỗi một thành phần Yi của Y có miền giá trị là tập tất cả các nhãn từ loại có thể (danh từ, động từ, tính từ,...). 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 đồ 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 Yv của Y. Ta nói (Y|X) là một trường ngẫu nhiên điều kiện (Conditional Random Field) khi với điều kiện X, các biến ngẫu nhiên Yv tuân theo tính chất Markov đối với đồ thị G [10]: ))(,,|(),,|( vNYXYPvYXYP vv    (3.8) Ở đây, N(v) là tập tất cả các đỉnh kề với v. Như vậy, một CRF là một trường ngẫu nhiên phụ thuộc toàn cục vào X. Trong các bài toán xử lý dữ liệu dạng chuỗi, G đơn giản chỉ là dạng chuỗi G = (V={1,2,…m}, E={(i,i+1)}). Kí hiệu X=(X1, X2,…, Xn), Y=(Y1,Y2,...,Yn). Mô hình đồ thị cho CRF có dạng: Hình 7. Đồ thị vô hướng mô tả CRF 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. Áp dụng kết quả của Hammerley-Clifford cho các trường ngẫu nhiên Markov, sẽ 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ủa các hàm tiềm năng như sau (theo [19]):    CA A AP )|()|( xxy  (3.9) Yn-1 Y1 X Y3 Y2 Yn 30 Vì trong các bài toán xử lý dữ liệu dạng chuỗi đồ thị biểu diễn cấu trúc của một CRF có dạng đường thẳng như trong hình 7 nên tập C phải là hợp của E và V, trong đó E là tập các cạnh của đồ thị G và V là tập các đỉnh của G, hay nói cách khác đồ thị con A hoặc chỉ gồm một đỉnh hoặc chỉ gồm một cạnh của G. 3.2.2. Hàm tiềm năng của các mô hình CRF Lafferty [10] 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. Cực đại hóa Entropy là một nguyên lý 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. 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 một hàm mũ.     k kkA AfA xx |exp|  (3.10) Ở đây fk là một thuộc tính của chuỗi dữ liệu quan sát và k là trọng số chỉ mức độ biểu đạt thông tin của thuộc tính fk. Có hai loại thuộc tính là thuộc