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 Việt

ô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 vậy, với các bài toán gán nhãn cho dữ liệu dạng chuỗi, ta nên đưa ra các phương thức biểu diễn các dữ liệu quan sát mềm dẻo hơn như là biểu diễn dữ liệu quan sát dưới dạng các thuộc tính (features) không phụ thuộc lẫn nhau. Ví dụ với bài toán phân loại các câu hỏi và câu trả lời trong một danh sách FAQ, các thuộc tính có thể là bản thân các từ hay độ dài của dòng, số lượng các kí tự trắng, dòng hiện tại có viết lùi đầu dòng hay không, số các kí tự không nằm trong bảng chữ cái, các thuộc tính về các chức năng ngữ pháp của chúng… Rõ ràng những thuộc tính này không nhất thiết phải độc lập với nhau. • 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, mà tiêu biểu là phương pháp SVM. Ở các chương sau sẽ trình bày rõ hơn về 3 20 phương pháp học máy tiêu biểu đã đạt được kết quả khả quan khi áp dụng cho bài toán gán nhãn từ loại ở các ngôn ngữ khác, đó là mô hình Markov cực đại hóa Entropy MEMM, 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 Phương pháp lai là phương pháp dựa trên học chuyển đổi (transformation-based learning), đâ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ả hai đặc tính của 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 9. Mô hình tổng quát của phương pháp lai 21 Thuật toán bao gồm 5 bước • 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ụ: 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” • 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” 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 3. 22 Bảng 3. Ví dụ về một số luật chuyển Đạ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). Nhóm các tác giả Ðinh Ðiền, Nguyễn Văn Toàn và Diệp Chí Cường trong nghiên cứu “gán nhãn từ loại tự động cho tiếng Việt” [abc] đã áp dụng thử nghiệm mô hình này với tập nhãn đối chiếu từ tập nhãn Brown corpus của tiếng Anh và cho kết quả bước đầu vào khoảng hơn 80%. 23 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 Qua 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), em nhận 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. Trong khóa luận này, em 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à MEMM, CRF và SVM. Trong đó MEMM và CRF là các mô hình cải tiến dựa trên mô hình xác suất HMM truyền thống, còn SVM là đại diện đặc trưng cho các phương pháp học máy dựa trên độ đo, 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. Ở đây, 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. 2.1. Mô hình Markov cực đại hóa Entropy (MEMM) Như đã nói ở phần trên, mô hình HMM tuy là một mô hình học máy khá tốt, nhưng nó vẫn còn những mặt hạn chế khó có thể khắc phục. Mô hình Markov cực đại hóa Entropy MEMM (Maximum Entropy Markov Model) do McCallum đề xuất [abc] chính là đáp án cho những vấn đề còn hạn chế của mô hình Markov truyền thống. 2.1.1.Khái niệm mô hình MEMM MEMM là một mô hình cải tiến dựa trên mô hình Markov truyền thống. So với mô hình HMM, MEMM thay thế các xác suất chuyển trạng thái và xác suất sinh quan sát trong HMM bởi một hàm xác suất duy nhất P (Ti|Ti-1, Oi) - xác suất để trạng thái hiện tại là Ti với điều kiện trạng thái trước đó là Ti-1 và dữ liệu quan sát hiện tại là Wi. Mô hình MEMM quan niệm rằng các quan sát đã được cho trước và chúng ta không cần quan tâm đến xác suất sinh ra chúng, điều duy nhất cần quan tâm là các xác suất chuyển trạng thái. So sánh với HMM, ở đây quan sát hiện tại không chỉ phụ thuộc vào trạng thái hiện tại mà còn có thể phụ thuộc vào trạng thái trước đó, điều đó có nghĩa là quan sát hiện tại được gắn liền với quá trình chuyển trạng thái thay vì gắn liền với các trạng thái riêng lẻ như trong mô hình HMM truyền thống. 24 Hình 9: Đồ thị có hướng mô tả một mô hình MEMM Áp dụng tính chất Markov thứ nhất, xác suất P(T|W) có thể tính theo công thức : ∏ = −∗= n t tt WTTPWTPWTP 1 1111 ),|()|()|( (3.1) MEMM coi các dữ liệu quan sát là các điều kiện cho trước thay vì coi chúng như các thành phần được sinh ra bởi mô hình như trong HMM vì thế xác suất chuyển trạng thái có thể phụ thuộc vào các thuộc tính đa dạng của chuỗi dữ liệu quan sát. Các thuộc tính này không bị giới hạn bởi giả thiết về tính độc lập như trong HMM và giữ vai trò quan trọng trong việc xác định trạng thái kế tiếp. Kí hiệu PTi-1(Ti|Wi)=P(Ti|Ti-1,Wi). Áp dụng phương pháp cực đại hóa Entropy (sẽ được đề cập ở phần dưới), McCallum xác định phân phối cho xác suất chuyển trạng thái có dạng hàm mũ như sau: ⎟⎠ ⎞⎜⎝ ⎛= ∑ − − a iiaa ii iiT TWfTWZ WTP i ),(exp ),( 1)|( 1 1 λ (3.2) Ở đây, aλ là các tham số cần được huấn luyện (ước lượng); Z (Wi, Ti) là thừa số chẩn hóa để tổng xác suất chuyển từ trạng thái Ti-1 sang tất cả các trạng thái Ti kề đều bằng 1; fa (Wi, Ti) 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 fa (Wi,Ti) nhận hai tham số, một là dữ liệu quan sát hiện tại Wi và một là trạng thái hiện tại Ti. McCallum định nghĩa a=, ở đây b là thuộc tính nhị phân chỉ phụ thuộc vào dữ liệu quan sát hiện tại và Si là trạng thái hiện tại. Sau đây là một ví dụ về một thuộc tính b: Hàm thuộc tính fa (Wi, Ti) xác định nếu b (Wi) xác định và trạng thái hiện tại nhận một giá trị cụ thể nào đó: b(Wi) = 1 nếu dữ liệu quan sát hiện tại là “the” 0 nếu ngược lại T T2 Tn-1 Tn T3 W1 W2 W 3 W n-1 W n 25 Để gán nhãn cho dữ liệu, MEMM xác định chuỗi trạng thái T làm cực đại P(T|W) trong công thức (2.3).Việc xác định chuỗi nhãn T cũng được thực hiện bằng cách áp dụng thuật toán Viterbi như trong HMM. 2.1.2. Nguyên lý cực đại hóa Entropy và mô hình xác suất 2.1.2.1. 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.3) 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’ (CRF.7) và hai là nó phải làm cực đại Entropy điều kiện (CRF.3). 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)()(|' ~ ∈∀=∈= 2.1.2.1.2. Mô hình xác suất fa (Wi,Ti)= 1 nếu b (Wi) =1 và Ti=Ti- 0 nếu ngược lại 26 Theo [6] 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 thẻ có thể có. Xác suất mô hình của lịch sử h cùng với thẻ t được định nghĩa theo công thức 3.4: ∏ = ∏= k j thf j jthp 1 ),(),( αµ (3.4) 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. Cho trước một tập các từ {w1, …, wn} và một chuỗi thẻ {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 thẻ 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.5 ∏ ∏∏ = == Π== n i k j thf j n i ii iijthppL 1 1 ),( 1 ),()( αµ (3.5) 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.6 ∑ ∈∈ −= τtHh thpthppH , ),(log),()( (3.6) Và các ràng buộc được cho bởi công thức 3.7 kjfEEf ji ≤≤= 1,~ (3.7) Trong đó kỳ vọng đặc trưng của mô hình là 3.8 ),(),( , thfthpEf tHh ji ∑ ∈∈ = τ (3.8) và kỳ vọng đặc trưng quan sát là 3.9 ∑ = = n i iijiii thfthpfE 1 ),(),(~~ (3.9) 27 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. 2.1.3. Hạn chế của mô hình MEMM 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” [abc]. 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 MEMM 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. 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 automata đa đị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 tính đ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 tóan trích chọn thông tin [abc]. 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 đó. 28 2.2. Mô hình trường ngẫu nhiên điều kiện (CRF) Mô hình trường ngẫu nhiên điều kiện CRF (Conditional Random Fields) [abc] được giới thiệu lần đầu vào năm 2001 bởi Lafferty và các đồng nghiệp. Giống như MEMM, 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 MEMM, CRF là mô hình đồ thị vô hướng. Điều này cho phép CRF có thể định nghĩa phân phối xác suất của toàn bộ chuỗi trạng thái với điều kiện biết chuỗi quan sát cho trước thay vì phân phối trên mỗi trạng thái với điều kiện biết trạng thái trước đó và quan sát hiện tại như trong các mô hình MEMM. 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 các nhược điểm của những mô hình học máy khác như HMM và MEMM 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, nguyên lý cực đại hóa Entropy – một phương pháp đánh giá phân phối xác suất từ dữ liệu và là cơ sở để 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, một số phương pháp để ước lượng các tham số cho mô hình CRF. 2.2.1. Khái niệmCRF 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à 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 của 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 - CRF) 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: ))(,,|(),,|( vNYXYPvYXYP vv ∈=≠ ωω ωω (3.10) 29 Ở đâ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 10: Đồ 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 [14- Markov fields on finite graphs and lattices. Unpublished manuscript, 1971] cho các trường ngẫu nhiên Markov, ta thừa số hóa được p(y|x) - xác suất của chuỗi nhãn với điều kiện biết chuỗi dữ liệu quan sát- thành tích của các hàm tiềm năng như sau: ∏ ∈ = CA A AP )|()|( xxy ψ (3.11) 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 5 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. 2.2.2. Hàm tiềm năng của các mô hình CRF Lafferty [abc] 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 [abc]. 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.12) Yn-1 Y1 X Y3 Y2 Yn 30 Ở đâ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 tính chuyển (kí hiệu là t) và thuộc tính trạng thái(kí hiệu là s) tùy thuộc vào A là đồ thị con gồm một đỉnh hay một cạnh của G. Thay các hàm tiềm năng vào công thức (CRF.2) và thêm vào đó một thừa sổ chuẩn hóa Z(x) để đảm bảo tổng xác suất của tất cả các chuỗi nhãn tương ứng với một chuỗi dữ liệu quan sát bằng 1, ta được: ⎟⎠ ⎞⎜⎝ ⎛ += ∑ ∑∑∑ − i i k ikk k iikk stZ P ),(),,(exp )( 1)|( 1 xyxyyx xy µλ (3.13) Ở đây, x,y là chuỗi dữ liệu quan sát và chuỗi trạng thái tương ứng; tk là thuộc tính của tòan bộ chuỗi quan sát và các trạng thái tại ví trí i-1, i trong chuỗi trạng thái; sk là thuộc tính của toàn bộ chuỗi quan sát và trạng thái tại ví trí i trong chuỗi trạng thái. Thừa số chuẩn hóa Z(x) được tính như sau: ∑ ∑ ∑∑∑ ⎟⎠ ⎞⎜⎝ ⎛ += − y i i k ikk k iikk stZ ),(),,(exp)( 1 xyxyyx µλ (3.14) ..),...,,( 2,121 µµλλθ là các vector các tham số của mô hình, teta sẽ được ước lượng giá trị nhờ các phương pháp ước lượng tham số cho mô hình sẽ được đề cập trong phần sau. 2.2.3. Thuật toán gán nhãn cho dữ liệu dạng chuỗi Tại mỗi vị trí i trong chuỗi dữ liệu quan sát, ta định nghĩa một ma trận chuyển |S|*|S| như sau: [ ]),,'()( xx yyMM ii = (3.15) ti = 1 nếu xi-1= “Bill”, xi=”Clinton” và yi-1=B_PER,yi=I_PER 0 nếu ngược lại si = 1 nếu xi=Bill và yi= B_PER 0 nếu ngược lại 31 ⎟⎠ ⎞⎜⎝ ⎛ += ∑ ∑ k k kkkki ysyytyyM ),(),,'(exp),,'( xxx µλ (3.16) Ở đây Mi(y’,y,x) là xác suất chuyển từ trạng thái y’ sang trạng thái y với chuỗi dữ liệu quan sát là x. Chuỗi trạng thái y* mô tả tốt nhất cho chuỗi dữ liệu quan sát x là nghiệm của phương trình: y* = argmax{p(y|x)} (3.17) Chuỗi y* được xác định bằng thuật toán Viterbi cải tiến. Định nghĩa )( yi∂ là xác suất của “chuỗi trạng thái độ dài i kết thúc bởi trạng thái y và có xác suất lớn nhất” biết chuỗi quan sát là x. Hình 11: Một bước trong thuật toán Viterbi cải tiến Giả sử biết tất cả )( ki y∂ với mọi yk thuộc tập trạng thái S của mô hình, cần xác định )(1 ji y+∂ . Từ hình 7, ta suy ra công thức đệ quy ( ) SyyyMyy kjkikiji ∈∀∂=∂ −+ ),,(*)(max)( 11 x (3.18) Đặt ( )),,'(*)'(maxarg)(Pr 1 xyyMyye iii −∂= . Giả sử chuỗi dữ liệu quan sát x có độ dài n, sử dụng kĩ thuật backtracking để tìm chuỗi trạng thái y* tương ứng như sau: • Bước 1: Với mọi y thuộc tập trạng thái tìm o ( ))(maxarg)(* yn n∂=y o i Å n ? )( Ni y∂Prob= yj )( 1yi∂ y1 y2 yN Prob= )( 2yi∂ )(1 ji y+∂ 32 • Bước lặp: chừng nào i>0 o i Å i-1 o y Å Prei(y) o y*(i) = y Chuỗi y* tìm được chính là chuỗi có xác suất p(y*|x) lớn nhất, đó cũng chính là chuỗi nhãn phù hợp nhất với chuỗi dữ liệu quan sát cho trước. Như vậy ,do bản chất phân phối toàn cục của mình, CRF có thể giải quyết được vấn đề ‘label bias’, một nhược điểm tiêu biểu của mô hình MEMM. Ở phương diện lý thuyết mô hình, ta có thể coi mô hình CRF như là một máy trạng thái xác suất với các trọng số không chuẩn hóa, mỗi trọng số gắn liền với một bước chuyển trạng thái. Bản chất không chuẩn hóa của các trọng số cho phép các bước chuyển trạng thái có thể nhận các giá trị quan trọng khác nhau. Vì thế bất cứ một trạng thái nào cũng có thể làm tăng hoặc giảm xác suất được truyền cho các trạng thái sau nó mà vẫn đảm bảo xác suất cuối cùng được gán cho toàn bộ chuỗi trạng thái thỏa mãn định nghĩa về xác suất nhờ thừa số chuẩn hóa toàn cục. 3.2.5.Ước lượng tham số cho các mô hình CRF Kĩ thuật được sử dụng để đánh giá tham số cho một mô hình CRF là làm cực đại hóa độ đo likelihood giữa phân phối mô hình và phân phối thực nghiệm. Giả sử dữ liệu huấn luyện gồm một tập N cặp, mỗi cặp gồm một chuỗi quan sát và một chuỗi trạng thái tương ứng, D={(x(i),y(i))} Ni K1=∀ . Độ đo likelihood giữa tập huấn luyện và mô hình điều kiện tương ứng p(y|x,θ ) là: ∏= yx yxxy , ),(~),|()( ppL θθ (3.19) Ở đây ..),...,,( 2,121 µµλλθ là các tham số của mô hình và ),(~ yxp là phân phối thực nghiệm đồng thời của x,y trong tập huấn luyện. Nguyên lý cực đại likelihood: các tham số tốt nhất của mô hình là các tham số làm cực đại hàm likelihood. )(maxarg θθ θ LML = (3.20) MLθ đảm bảo những dữ liệu mà chúng ta quan sát được trong tập huấn luyện sẽ nhận được xác suất cao trong mô hình. Nói cách khác, các tham số làm cực đại hàm 33 likelihood sẽ làm phân phối trong mô hình gần nhất với phân phối thực nghiệm trong tập huấn luyện. Vì việc tính teta dựa theo công thức (4.1) rất khó khăn nên thay vì tính toán trực tiếp, ta đi xác định teta làm cực đại logarit của hàm likelihood (thường được gọi tắt là log-likelihood): ( )∑= yx xyyx , ),|(log),(~)( θθ ppl (3.21) Vì hàm logarit là hàm đơn điệu nên việc làm này không làm thay đổi giá trị của θ được chọn.Thay p(y|x,θ ) của mô hình CRF vào công thức (4.3), ta có: ∑ ∑∑ ∑ −⎥⎦ ⎤⎢⎣ ⎡ += + = =yx x xstyx , 1 1 1 log*)(~**),(~)( Zppl n i n i µλθ (3.22) Ở đây, ),..,( 21 nλλλλ và ),...,,( 21 mµµµµ là các vector tham số của mô hình, t là vector các thuộc tính chuyển (t1(yi-1,yi,x),t2(yi-1,yi,x),…), s là vector các thuộc tính trạng thái (s1(yi,x),s2(yi,x),…). Hàm log-likelihood cho mô hình CRF là một hàm lõm và trơn trong toàn bộ không gian của tham số. Bản chất hàm lõm của log-likelihood cho phép ta có thể tìm được giá trị cực đại toàn cục θ bằng cách thiết lập các thành phần của vector gradient của hàm log-likelihood bằng không. Mỗi thành phần trong vector gradient của hàm log-likelihood là đạo hàm của hàm log-likelihood theo một tham số của mô hình. Đạo hàm hàm log – likelihood theo tham số kλ ta được: ∑ ∑ = −=∂ ∂ yx xyyyx , 1 1 ),,(),(~ )( n i iik k tplλ θ -∑ ∑ = − x xyyxyx n i iiktpp 1 1 ),,(),|()(~ θ = [ ] [ ]kpkp tEtE ),|(),(~ θxyyx − (3.23) Việc thiết lập phương trình trên bằng 0 tương đương với việc đưa ra một ràng buộc cho mô hình: giá trị trung bình của tk theo phân phối ),|()(~ θxyx pp bằng giá trị trung bình của tk theo phân phối thực nghiệm ),(~ yxp . Như vậy, về phương diện toán học, bài toán ước lượng tham số cho một mô hình CRF chính là bài toán tìm cực đại của hàm log-likelihood. Có nhiều phương pháp tìm cực đại của hàm log-likelihood như các phương pháp lặp (IIS, GIS), các phương pháp 34 tối ưu số (phương pháp dựa trên vector gradient như phương pháp gradient liên hợp, quasi-Newton …) và L-BFGs có thể phục vụ cho ước lượng tham số mô hình. Trong các phương pháp tìm cực trị hàm log-likelihood này, phương pháp L-BFGs được đánh giá là vượt trội và có tốc độ hội tụ nhanh nhất. 2.3. Mô hình máy véc tơ hỗ trợ (SVM) 2.3.1. Khái niệm và cơ sở của phương pháp SVM Phương pháp máy véc tơ hỗ trợ SVM (Support Vector Machine) ra đời từ lý thuyết học thống kê do Vapnik và Chervonekis xây dựng năm 1995 [abc] 11,12 và có nhiều tiềm năng phát triển về mặt lý thuyết cũng như ứng dụng trong thực tế. SVM là một họ các phương pháp dựa trên cơ sở các hàm nhân (kernel) để tối thiểu hóa rủi ro ước lượng.Các thử nghiệm thực tế cho thấy, phương pháp SVM có khả năng phân loại khá tốt đối với bài toán phân lớp cũng như trong nhiều ứng dụng khác (ước lượng hồi quy, nhân dạng chữ viết tay …). Ý tưởng của phương pháp là cho trước một tập huấn luyện được biểu diễn trong k