Luận vă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

( , ) ( , ) 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 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 (3.9) 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.11) Ở đâ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. 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 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.12) ..),...,,( 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. 3.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.13)       k k kkkki ysyytyyM ),(),,'(exp),,'( xxx  (3.14) Ở đâ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.15) Chuỗi y* được xác định bằng thuật toán Viterbi cải tiến [16] như mô tả trong hình 8. Đị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. 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 8, ta suy ra công thức truy hồi   SyyyMyy kjkikiji   ),,(*)(max)( 11 x (3.16) 32 Hình 8. Một bước trong thuật toán Viterbi cải tiến Đặ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  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 MEM [12, 19]. Ở 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. ? )( Ni yProb= yj )( 1yi y1 y2 yN Prob= )( 2yi )(1 ji y 33 3.2.4. Ướ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. Nguyên lý cực đại likelihood được phát biểu như sau: 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. 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 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. 3.3. Mô hình máy véc tơ hỗ trợ 3.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) [11, 23] ra đời từ lý thuyết học thống kê do Vapnik và Chervonekis xây dựng năm 1995, 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 …). Hình 9. Hai cách chia không gian véc tơ thành hai nửa riêng biệt Lề lớn Lề nhỏ Véc tơ hỗ trợ 34 Ý 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 không gian vector, trong đó mỗi một văn bản được xem như một điểm trong không gian này. Như vậy, rõ ràng có nhiều cách có thể chia không gian này thành hai nửa riêng biệt, hình 9 cho ta một trường hợp ví dụ. Phương pháp SVM tìm ra một siêu mặt phẳng h (siêu phẳng) quyết định tốt nhất có thể chia các điểm trên không gian này thành hai lớp riêng biệt tương ứng, tạm gọi là lớp âm (-) và lớp dương (+). Chất lượng của siêu phẳng này được quyết định bởi một khoảng cách (được gọi là lề) của điểm dữ liệu gần nhất của mỗi lớp đến mặt phẳng này. Khoảng cách lề càng lớn thì xác suất của việc phân lớp sai sẽ càng nhỏ, tức là càng có sự phân chia tốt các điểm ra thành hai lớp, như vậy, ta sẽ đạt được kết quả phân lớp tốt. Theo [23], bộ phân lớp SVM là mặt siêu phẳng phân tách các mẫu dương khỏi các mẫu âm với độ chênh lệch cực đại, trong đó độ chênh lệch – còn gọi là lề- xác định bằng khoảng cách giữa các mẫu dương và các mẫu âm gần mặt siêu phẳng nhất. Mặt siêu phẳng này được gọi là siêu phẳng lề tối ưu . Tóm lại, mục tiêu của thuật toán SVM là tìm được khoảng cách lề lớn nhất để tạo kết quả phân lớp tốt. Hình 10 dưới đây cho ta mô tả trực quan về phương pháp SVM. Hình 10. Mặt siêu phẳng tách các mẫu dương khỏi các mẫu âm. Mặc dù bản chất của phương pháp này đã được định nghĩa ở trên, nhưng có rất nhiều phiên bản khác nhau của nó, thường thì miền trong của lề trong tập dữ liệu huấn Các mẫu âm Các mẫu dương Lề Véc tơ hỗ trợ Véc tơ hỗ trợ Siêu phẳng lề tối ưu 35 luyện có thể chứa một lượng nhỏ các điểm, dẫn đến việc không thể phân chia các mẫu âm và các mẫu dương bằng một mặt siêu phẳng tuyến tính, hình 11 là một ví dụ minh họa. Trong trường hợp này, sự không “thẳng” (không tuyến tính) của siêu phẳng được biến đổi trở thành “thẳng” (tuyến tính) bằng cách sử dụng các hàm nhân. Một ví dụ của biến đổi sử dụng hàm nhân được minh họa trong hình 12 [23]. Hình 11. Trường hợp không thể phân chia các mẫu âm và các mẫu dương bằng một siêu phẳng tuyến tính Hình 12. Biến đổi siêu phẳng không tuyến tính thành siêu phẳng tuyến tính sử dụng hàm nhân Việc phân lớp trong trường hợp mở rộng này cũng tương tự trường hợp cơ sở, dựa trên giá trị âm hoặc dương của đầu ra. 36 3.3.2. Áp dụng phương pháp SVM cho bài toán gán nhãn từ loại Có thể nói SVM thực chất là một bài toán tối ưu, mục tiêu của thuật toán là tìm được một không gian H và siêu mặt phẳng quyết định h trên H sao cho sai số khi phân lớp là thấp nhất, nghĩa là kết quả phân lớp sẽ cho kết quả tốt nhất. Đối với bài toán gán nhãn từ loại, ta gọi x là ngữ cảnh (một tập các đặc trưng) của mẫu đầu vào đang cần gán nhãn, xi và yi (với i= 1, …, l; yi ∈ {1, -1}) lần lượt chỉ ra ngữ cảnh của dữ liệu huấn luyện và lớp tương ứng của nó [12]. 1 ( ) sgn( ( , ) ) l i i i i f x a y K x x b    (3.17) , -1 , 1max min- 2 i ii y i i y i b b b    (3.18) 1 ( , ) l i j j j i j b a y K x x    (3.19) Trong đó, hàm sgn được định nghĩa như sau: sgn(x) = 1 (x ≥ 0) -1 (trong trường hợp ngược lại) Mỗi αi được cố định khi giá trị L(α) trong biểu thức dưới đây được cực đại hóa dưới điều kiện của biểu thức (3.18) và (3.19) 1 , 1 1( ) ( , ) 2 l l i i j i j i j i i j L a y y K x x        (3.20) 0 ( 1,..., )i C i l   (3.21) 1 0 l i i i y   (3.22) Hàm K trong biểu thức (3.20) được gọi là hàm nhân và rất nhiều dạng của hàm nhân có thể được sử dụng [8], hình 13 dưới đây mô tả hàm nhân Basis Radial exp (- gamma*|u-v|2) [23]. 37 Hình 13. Hàm nhân Basis Radial Trong một số nghiên cứu về bài toán gán nhãn từ loại, hàm đa thức dưới đây được sử dụng [12]: ( , ) ( 1)dK x y x y   (3.23) Với C (trong biểu thức(3.21)) và d (trong biểu thức (3.23)) luôn nhận giá trị không đổi và được xác định trong thực nghiệm. Thông thường thì C và d lần lượt được cố định là 1 và 2 cho tất cả các thực nghiệm. Một tập các giá trị xi thỏa mãn α >0 được gọi là véc tơ hỗ trợ, phần biểu thức được tính tổng trong biểu thức (3.21) có thể được tính chỉ sử dụng các vector hỗ trợ. Chúng ta thấy rằng SVM là mặt phẳng quyết định chỉ phụ thuộc vào các vector hỗ trợ, khi các điểm khác bị xóa đi thì thuật toán vẫn cho kết quả giống như ban đầu. Chính đặc điểm này làm cho SVM khác với các thuật toán khác như KNN, LLSF, Nnet, NB vì tất cả dữ liệu trong tập huấn luyện đều được dùng để tối ưu hóa kết quả. Một vấn đề được đặt ra là, phương pháp SVM có thể chia dữ liệu làm hai lớp, tuy nhiên đối với bài toán gán nhãn từ loại cho dữ liệu văn bản, số lớp tương ứng với số từ loại mà ta cần xác định luôn lớn hơn hai, vậy liệu phương pháp SVM có phù hợp để giải quyết bài toán gán nhãn từ loại hay không?. Để giải quyết vấn đề này. thường thì dữ liệu với hơn hai lớp sẽ được xử lý bằng phương pháp pair-wise, tức là với dữ liệu chứa N lớp, ta sẽ xây dựng tất cả các cặp của hai lớp khác nhau, tổng số sẽ là N(N-1)/2 cặp. Từng lớp tốt hơn trong một cặp hai lớp sẽ được xác định bằng cách sử dụng bộ phân lớp 2 lớp, cuối cùng, lớp chính xác sẽ được xác định dựa trên cơ sở đánh giá kết quả của N(N-1)/2 lần phân lớp. 3.3.3. Huấn luyện SVM Huấn luyện SVM thực chất là việc giải bài toán quy hoạch toàn phương SVM [11]. Các phương pháp số giải bài toán quy hoạch này yêu cầu phải lưu trữ một ma (a) Radial Basic Function (b) RBF mapping 38 trận có kích thước bằng bình phương của số lượng mẫu huấn luyện. Trong những bài toán thực tế, điều này là không khả thi vì thông thường kích thước của tập dữ liệu huấn luyện thường rất lớn (có thể lên tới hàng chục nghìn mẫu). Nhiều thuật toán khác nhau được phát triển để giải quyết vấn đề nêu trên. Những thuật toán này dựa trên việc phân rã tập dữ liệu huấn luyện thành những nhóm dữ liệu. Điều đó có nghĩa là bài toán quy hoạch toàn phương lớn được phân rã thành các bài toán quy hoạch toàn phương với kích thước nhỏ hơn. Sau đó, những thuật toán này kiểm tra các điều kiện KKT (Karush Kuhn Tucker) để xác định phương án tối ưu . Một trong những phương pháp tiêu biểu là thuật toán huấn luyện SVM tối ưu hóa tuần tự cực tiểu (Sequential Minimal Optimization - SMO), dựa vào lý thuyết Lagrange để giải bài toán quy hoạch toàn phương. Thuật toán này sử dụng tập dữ liệu huấn luyện (còn gọi là tập làm việc) có kích thước nhỏ nhất bao gồm hai hệ số Lagrange. Bài toán quy hoạch toàn phương nhỏ nhất phải gồm hai hệ số Lagrange vì các hệ số Lagrange phải thỏa mãn ràng buộc đẳng thức (3.22). Phương pháp SMO cũng có một số heuristic cho việc chọn hai hệ số Lagrange để tối ưu hóa ở mỗi bước. Mặc dù có nhiều bài toán quy hoạch toàn phương con hơn so với các phương pháp khác, mỗi bài toán con này được giải rất nhanh dẫn đến bài toán quy hoạch toàn phương tổng thể cũng được giải một cách nhanh chóng. 39 Chương 4. THỰC NGHIỆM ÁP DỤNG BA MÔ HÌNH HỌC MÁY CHO BÀI TOÁN GÁN NHÃN TỪ LOẠI TIẾNG VIỆT VÀ ĐÁNH GIÁ KẾT QUẢ Mặc dù trên thế giới đã có nhiều phương pháp được đề xuất cho việc giải quyết bài toán gán nhãn từ loại, nhưng vì tiếng Việt có những đặc trưng riêng phức tạp và tiềm ẩn nhiều nhập nhằng nên một phương pháp cho kết quả cao ở ngôn ngữ khác chưa chắc đã đạt được kết quả tương tự với tiếng Việt. Dựa trên cơ sở lý thuyết đã có ở chương 3, khóa luận tiến hành thực nghiệm áp dụng ba mô hình học máy MEM, CRF và SVM cho bài toán gán nhãn từ loại tiếng Việt trên cùng môi trường thực nghiệm và tập đặc trưng. Từ kết quả thu được, khóa luận đưa ra một số so sánh về kết quả đạt được cũng như một số nhận xét sơ bộ về ưu nhược điểm của các phương pháp này. 4.1. Mô tả thực nghiệm 4.1.1. Phần cứng Máy tính cá nhân Celeron R, Chip 3.06 GHz, Ram 1 GB 4.1.2. Phần mềm Sử dụng các công cụ dưới đây để tiến hành thực nghiệm gán nhãn từ loại tiếng Việt:  Thực nghiệm gán nhãn từ loại tiếng việt sử dụng mô hình MEM bằng hệ thống tích hợp mô hình tách từ và gán nhãn từ loại tiếng Việt được xây dựng bởi tác giả Trần Thị Oanh, phòng thí nghiệm các hệ tích hợp thông minh, trường đại học Công nghệ, đại học Quốc gia Hà nội, năm 2008 [4].  Thực nghiệm gán nhãn từ loại tiếng việt sử dụng mô hình CRF bằng công cụ CRF++ xây dựng bởi tác giả người Nhật Taku Kudo [24]. Công cụ được viết bằng C++, bản cập nhật mới nhất ngày 06 tháng 05 năm 2009.  Thực nghiệm gán nhãn từ loại tiếng việt sử dụng mô hình SVM dựa trên công cụ SVMmulticlass. Đây là một công cụ phát triển từ công cụ SVMlight, được xây dựng bởi tác giả Thorsten Joachims [22] (Department of Computer Science, Cornell University). Bản cập nhật mới nhất là version 2.20 ngày 14 tháng 8 năm 2008. 40  Khóa luận đã xây dựng các công cụ trợ giúp bằng ngôn ngữ C++ và Delphi để hỗ trợ thực nghiệm, bao gồm: o Chuẩn hóa dữ liệu theo định dạng phù hợp o Mã hóa dữ liệu theo yêu cầu của hệ thống gán nhãn o Áp dụng đặc trưng chuẩn hóa biểu thức chính quy o Xây dựng từ điển để hỗ trợ trích chọn đặc trưng o Trích chọn đặc trưng về thông tin từ vựng và thông tin nhãn từ loại o Đánh giá độ chính xác của kết quả 4.1.3. Dữ liệu thực nghiệm và tập nhãn từ loại Để áp dụng thực nghiệm ba phương pháp học máy MEM, CRF và SVM, khóa luận sử dụng hai bộ dữ liệu riêng biệt được gán nhãn với hai tập nhãn khác nhau cho huấn luyện và kiểm thử nhằm tăng tính khách quan cho kết quả đạt được. Hai bộ dữ liệu đều được thu thập từ các báo điện tử có uy tín ở Việt Nam và bao gồm nhiều văn bản thuộc các chủ đề khác nhau như: Công nghệ thông tin, Kinh tế, Chính trị, Xã hội, Pháp luật, Đời sống … Trong nội dung của khóa luận, dữ liệu đã được qua bước tiền xử lý, tức là đã được tách từ, quy chuẩn theo đúng định dạng cần thiết và đã được gán nhãn sẵn để phục vụ cho quá trình học có giám sát cũng như kiểm thử. Các nhãn sẽ được xác định bằng cách viết hoa và đi liền (cách một dấu cách) hoặc phân cách với từ mà nó xác định bằng dấu “/” hay “//”, quy tắc ký hiệu này có thể thay đổi một cách dễ dàng tuy thuộc vào yêu cầu sử dụng dữ liệu.  Bộ dữ liệu thứ nhất (bộ dữ liệu Viet TreeBank): Đây là sản phẩm của dự án quốc gia VLSP, gồm 142 văn bản, tương ứng với khoảng hơn 10.000 câu và khoảng 230.000 từ. Bộ dữ liệu này được gán nhãn từ loại bằng tập nhãn từ loại VTB (Viet Tree Bank) gồm 16 nhãn từ loại, 1 nhãn cho từ không gán nhãn được và 1 nhãn cho ký hiệu đặc biệt. 41 Bảng 5. Tập nhãn từ loại Viet Tree Bank cho tiếng Việt STT Tên nhãn Ý nghĩa của nhãn 1 N Danh từ 2 Np Danh từ riêng 3 Nc Danh từ chỉ loại 4 Nu Danh từ đơn vị 5 V Động từ 6 A Tính từ 7 P Đại từ 8 L Định từ 2 9 M Số từ 10 R Phó từ 11 E Giới từ 3 (kết từ chính phụ) 12 C Liên kết từ (kết từ đẳng lập) 13 I Thán từ 14 T Trợ từ, tình thái từ (tiểu từ) 4 15 B Từ tiếng nước ngoài (hay từ vay mượn) 16 Y Từ viết tắt 17 X Các từ không phân loại được 18++ Ký hiệu Các ký hiệu đặc biệt khác (?, /, #, $ …) Một câu ví dụ ở bộ dữ liệu thứ nhất: Một/M buổi/N trưa/N đang/R ngồi/V chờ/V khách/N ở/E bến/N Đinh_Bộ_Lĩnh/Np,/, tôi/P thấy/V một/M đồng_nghiệp/N già/A móc/V trong/E bao/N nilông/N ra/V một/M quyển/Nc giáo_trình/N đại_học/N môn/N Triết_học/N Mác/Np - /- Lênin/Np./.  Bộ dữ liệu thứ hai được xây dựng bởi nhóm tác giả Trần Thị Oanh, gồm 780 văn bản, tương ứng với khoảng 8000 câu và khoảng 150.000 từ. Bộ dữ liệu này được 42 gán nhãn từ loại bằng tập nhãn VnPOS gồm 13 nhãn từ loại, 1 nhãn cho các từ không thể gán nhãn và các nhãn ký hiệu đặc biệt. Bảng 6. Tập nhãn từ loại VnPOS cho tiếng Việt STT Tên nhãn Ý nghĩa của nhãn 1 NN Danh từ thường 2 NC Danh từ chỉ loại 3 NP Danh từ riêng 4 VB Động từ 5 JJ Tính từ 6 PP Đại từ 7 D Định từ và số từ 8 AD Phụ từ 9 IN Giới từ 10 CC Liên từ 11 UH Thán từ 12 RB Trợ từ 13 TN Thành ngữ 14 X Các từ không thể gán nhãn được 15++ Ký hiệu Các ký hiệu đặc biệt khác (#, ^, &, …) Một câu ví dụ ở bộ dữ liệu thứ hai: Tờ//NC Wall_Street_Journal//NP ghi//VB lời//NC phát_biểu//VB của//IN Tổng_Giám_đốc//NN kiêm//VB Giám_đốc_điều_hành//NN Mazda//NP,//, Hisakazu_Imaki//NP ://: Chúng_tôi//PP sẽ//AD đảm_nhiệm//VB vai_trò//NN phát_triển//VB nền_tảng//NN kiến_trúc//NN cho//IN các//D thế_hệ//NN xe//NN Ford//NP hạng//NC nhỏ//JJ trong//IN tương_lai//NN.//. Nhìn chung cả hai tập nhãn đều mới được xây dựng ở mức thô, nhưng tạm thời trong các yêu cầu trước mắt thì số lượng nhãn là đủ đáp ứng yêu cầu thực nghiệm để 43 đối chiếu, so sánh kết quả đạt được khi sử dụng các mô hình học máy khác nhau cho bài toán gán nhãn từ loại. 4.2. Mô tả tập đặc trưng dựa trên mức từ và mức hình vị Lựa chọn các thuộc tính từ tập dữ liệu huấn luyện là nhiệm vụ quan trọng nhất, giữ vai trò quyết định chất lượng của một hệ thống gán nhãn từ loại. Các thuộc tính được lựa chọn càng tinh tế thì độ chính xác của hệ thống càng tăng. Tập các đặc trưng sử dụng trong thực nghiệm của khoá luận này được xây dựng như sau:  Tiếp thu một số đặc trưng tiêu biểu và thông dụng thường được sử dụng trong nhiều ngôn ngữ trên thế giới (như tiếng Anh [15], tiếng Thái [12], tiếng Trung Quốc [20], …)  Bố sung thêm một số đặc trưng có khả năng là hữu ích, phù hợp với đặc điểm riêng của tiếng Việt đã được đề xuất trong một vài nghiên cứu trước đây ([4]). Với cách xây dựng như trên, tập đặc trưng được sử dụng trong thực nghiệm của khoá luân bao gồm các đặc trưng sau: 4.2.1. Các đặc trưng dựa vào thông tin từ vựng và thông tin từ loại Các thuộc tính tại vị trí i trong chuỗi dữ liệu quan sát gồm hai phần, một là thông tin ngữ cảnh tai vị trí i của chuỗi dữ liệu quan sát, một là phần thông tin về nhãn tương ứng. Công việc lựa chọn các thuộc tính thực chất là chọn ra các mẫu vị từ ngữ cảnh (context predicate template), các mẫu này thể hiện những các thông tin đáng quan tâm tại một vị trí bất kì trong chuỗi dữ liệu quan sát. Áp dụng các mẫu ngữ cảnh này tại môt vị trí trong chuỗi dữ liệu quan sát cho ta các thông tin ngữ cảnh (context predicate) tại vị trí đó. Mỗi thông tin ngữ cảnh tại i khi kết hợp với thông tin nhãn tương ứng tại vị trí đó sẽ cho ta một thuộc tính của chuỗi dữ liệu quan sát tại i. Như vậy một khi đã có các mẫu ngữ cảnh, ta có thể rút ra được hàng nghìn thuộc tính một cách tự động từ tập dữ liệu huấn luyện. Xét một cửa sổ trượt với kích cỡ bằng 5 trượt dọc theo dữ liệu đang xét như ví dụ trong hình 14. Thông tin từ vựng và thông tin từ loại sử dụng cho việc lựa chọn đặc trưng cho MEM, CRF và SVM được cho trong bảng 7. 44 Hình 14. Cửa sổ trượt với kích cỡ size=5 chuyển động dọc theo dữ liệu Bảng 7. Thông tin từ vựng và thông tin từ loại sử dụng cho việc lựa chọn đặc trưng Loại Ký hiệu Giải thích Thông tin từ vựng w-2, w-1, w0, w1, w2 wi cho biết dữ liệu quan sát được tại vị trí thứ i trong chuỗi đầu vào (chuỗi đầu vào được coi là chuỗi nằm trong cửa số trượt với kích cỡ 5). Trong đó wi là dữ liệu quan sát được ngay tại vị trí hiện tại. Thông tin nhãn từ loại t-2, t-1 ti cho biết nhãn của từ tại vị trí thứ i trong chuỗi đầu vào. Ký hiệu thông tin ngữ cảnh (còn được gọi là lịch sử) là h, thông tin về nhãn là t, xác suất đồng thời của lịch sử h và thông tin về nhãn t được xác định bằng các tham số mà các đặc trưng tương ứng của nó là ữu ích, ví dụ αi thỏa mãn fi (h,t) = 1. Khi cho trước (h, t), một đặc trưng phải tồn tại trên bất cứ từ nào hoặc nhãn nào trong lịch sử h, và phải chứa thông tin giúp dự đoán nhãn t, ví dụ như thông tin chính tả của từ hiện tại, hoặc thông tin về hai nhãn trước từ hiện tại. Ngữ cảnh từ và nhãn xác định đối với một đặc trưng được cho bằng định nghĩa của lịch sử h, như công thức (4.1). , , , , , , ,{ }i i i 1 i 2 i 1 i 2 i 1 i 2h w w w w w t t      (4.1) Ví dụ: Áp dụng mẫu ngữ cảnh trên tại vị trí 1 trong chuỗi “3000 đồng” ta được ngữ cảnh w0: đồng. Giả sử trong dữ liệu huấn luyện, từ đồng trong chuỗi dữ liệu trên được gán nhãn Nu (Với Nu là nhãn danh từ đơn vị trong tập nhãn Viet Tree Bank), kết hợp với ngữ cảnh ta có thể rút ra được một thuộc tính của chuỗi dữ liệu quan sát là fi(h,t) = 1 nếu từ hiện tại là “đồng” và nhãn là Nu 0 nếu ngược lại N N , N C tiếng máy_bay , bầu_trời như w-2 w-1 w0 w1 w2 R V V A được vút lên cao t1 t2 V Dứt 45 4.2.2. Mẫu ngữ cảnh dạng biểu thức chính quy Một đặc trưng quan trọng khác cần được xem xét đến là các đặc trưng có thể được xây dựng bằng chuẩn hóa biểu thức chính quy. Các mẫu ngữ cảnh biểu thức chính quy có tác dụng hỗ trợ xác định nhãn từ loại một các nhanh chóng và chính xác hơn. Trong nhiều trường hợp nếu chỉ dựa vào thông tin về từ và từ loại của các từ trước và sau từ đang xét thì có thể gặp phải nhập nhằng làm ảnh hưởng đến kết quả của hệ thống. Trong khi đó, nếu dựa vào các mẫu ngữ cảnh biểu thức chính quy thì sẽ xác định được ngay các nhãn từ loại. Bảng dưới đây là một ví dụ cho các mẫu ngữ cảnh biểu thức chính quy xác định dữ liệu có dạng số: Bảng 8. Một số mẫu ngữ cảnh BTCQ xác định dữ liệu dạng số Mẫu ngữ cảnh Ví dụ Ý nghĩa ^[0-9]* 123456 Số ^[0-9]+/[0-9]+/[0-9]+$ 12/04/2005 Ngày tháng ^[0-9]+/[0-9]+$ 22/5 Ngày tháng hoặc phân số ^[0-9][0-9][0-9][0-9]$ 2005 Năm ^[0-9]đồng$ ^[0-9]USD$ 10000 đồng 30 USD Tiền tệ ^[0-9]%$ 7% Phần trăm Z1 = {một, hai …, mười,} Z2 = {mươi, trăm…} ^[z1]* [z2]*[z1]*$ Tám mươi Mười một Số … … … 4.3. Hệ thống gán nhãn từ loại cho tiếng Việt Sử dụng các phương pháp học máy MEM, CRF và SVM, 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. Trong phần này, ta quan tâm tới kiến trúc đường ống (pipeline), tức là việc gán nhãn từ loại được thực hiện sau khi đã có thông tin về từ vựng. Kiến trúc tổng thể của mô hình gán nhãn từ loại sẽ được sử dụng trong thực nghiệm được thể hiện trong 46 hình 15 [4]. Trong đó, có hai pha chính là pha huấn luyện mô hình và pha kiểm thử sử dụng mô hình.  Pha huấn luyện mô hình: Đầu vào là văn bản đã được tách từ, đưa qua bộ trích chọn đặc trưng (cách thiết kế tập đặc trưng hữu ích cho tiếng Việt sẽ được trình bày ở phần sau) rồi đưa vào mô hình học máy để huấn luyện. Ta sẽ sử dụng MEM, CRF hoặc SVM để huấn luyện mô hình ở bước này.  Pha kiểm thử: Còn được gọi là pha gán nhãn hay pha giải mã. Văn bản đầu vào sẽ được qua pha kiểm thử theo thuật toán phù hợp, ví dụ như thuật toán beam search [4], kết quả sẽ cho ra chuỗi nhãn tốt nhất tương ứng với dữ liệu đầu vào (chuỗi nhãn gồm các nhãn thuộc tập nhãn được chọn) Hình 15. Một mô hình gán nhãn từ loại tiếng Việt Thực nghiệm trong nội dung khóa luận sẽ tiến hành gán nhãn từ loại theo 2 hướng tiếp cận khác nhau, cùng với đó là tập đặc trưng có thay đổi phù hợp với từng cách tiếp cận:  Gán nhãn từ loại dựa vào thông tin về từ (Tiếp cận dựa trên mức từ).  Gán nhãn từ loại dựa vào thông tin hình vị (Tiếp cận dựa trên mức hình vị). Trích chọn đặc trưng Huấn luyện mô hình Pha kiểm thử Tài liệu chưa gán nhãn Tài liệu gán nhãn từ loại Tài liệu đã gán nhãn 47 4.3.1. Gán nhãn từ loại dựa vào thông tin về từ Gán nhãn từ loại dựa vào thông tin về từ là việc gán nhãn sử dụng các đặc trưng ngữ cảnh xung quanh từ đang xét. Các mẫu đặc trưng được mô tả như ở dưới đây, trong đó W đề cập tới từ còn POS đề cập tới nhãn từ loại của từ.  Từ Wi (i = -2, -1, 0, 1, 2)  Nhãn của từ đằng trước từ hiện tại POS(W-1)  Hai nhãn hai từ đằng trước từ hiện tại POS(W-2) POS(W-1)  Từ đang xét có phải dấu câu?  Từ đang xét có phải từ đầu tiên của câu?  Từ đang xét có ký tự đầu của mỗi hình vị viết hoa hay không? 4.3.2. Gán nhãn từ loại dựa vào thông tin hình vị Hướng tiếp cận gán nhãn từ loại ở mức hình vị dựa trên đặc điểm của tiếng Việt là các từ được cấu thành từ các hình vị. Trong tiếng việt, hình vị nhỏ nhất là “tiếng” được hình thành bởi nhiều ký tự trong bảng chữ cái. Dưới đây là mô tả đặc trưng dựa trên hình vị:  Hình vị S-i (i = -2, -1, 0, 1, 2)  Nhãn của hình vị đằng trước từ hiện tại POS(S-1wo)  Nhãn của 2 hình vị đằng trước từ hiện tại POS(S-2Wo) POS(S-1Wo)  Hình vị đang xét có phải dấu câu?  HÌnh vị đang xét có phải hình vị đầu tiên của một câu?  Hình vị đang xét có ký tự đầu tiên viết hoa hay không? Trong đó, với chú ý thêm là đặc trưng POS(S-1wo) chính là nhãn từ loại của hình vị đầu tiên thuộc từ đứng ngay trước từ hiện tại. Và POS(S-2Wo) POS(S-1Wo) chính là nhãn từ loại của hình vị đầu tiên thuộc từ đứng trước và cách từ hiện tại một từ. 48 4.4. Phương pháp thực nghiệm và các tham số đánh giá thực nghiệm 4.4.1. Phương pháp thực nghiệm Thực nghiệm theo phương pháp kiểm thử chéo 5 lần (5-fold cross validation). Theo phương pháp này, dữ liệu thực nghiệm được chia thành 5 phần bằng nhau, lần lượt lấy 4 phần để huấn luyện và 1 phần còn lại để kiểm thử, kết quả sau 5 lần thực nghiệm được ghi lại và đánh giá tổng thể. 4.4.2. Các tham số đánh giá thực nghiệm Khóa luận đánh giá độ “tốt” của các thực nghiệm dựa trên hai yếu tố chính:  Độ chính xác của kết quả (tức là dữ liệu đầu ra của mô hình). Đây là một trong những yếu tố quan trọng nhất cần phải xem xét để đánh giá độ tốt của một mô hình. Đối với các thực nghiệm đã được tiến hành, độ chính xác của dữ liệu đầu ra được tính bằng công thức: correctP correct incorrect    Thời gian xử lý của bộ gán nhãn. Thời gian này bao gồm: thời gian huấn luyện và thời gian gán nhãn (ở đây ta tính bằng thời gian kiểm thử trong các thực nghiệm). Ở đây ta ký hiệu thời gian huấn luyện là T (tính bằng đơn vị giây) và thời gian kiểm thử là t (tính bằng đơn vị giây); thời gian kiểm thử được tính bằng thời gian từ lúc mô hình bắt đầu gán nhãn cho dữ liệu kiểm thử đến lúc đầu ra được in ra file một cách hoàn chỉnh. 4.5. Kết quả thực nghiệm Các mô hình học máy MEM, CRF và SVM đã được huấn luyện trên cùng một môi trường phần cứng và sử dụng cùng tập đặc trưng đã được thiết kế ở phần trước. 4.5.1. Kết quả của năm lần thực nghiệm a. Kết quả thực nghiệm áp dụng mô hình MEM Dữ liệu huấn luyện và kiểm thử được xử lý theo từng câu một, thủ tục kiểm thử tuân theo thuật toán beam search, thuật toán này sẽ tìm kiếm để liệt kê các chuỗi nhãn ứng cử viên cho câu và chuỗi nhãn cao nhất được chọn là đáp án. 49  Ở mức từ Bảng 9. Độ chính xác khi áp dụng mô hình MEM ở mức từ Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình Bộ dữ liệu thứ nhất 86.47 86.73 86.56 86.24 86.11 86.42 Bộ dữ liệu thứ hai 85.17 85.64 85.51 85.71 85.81 85.57 Thực nghiệm áp dụng mô hình MEM để gán nhãn cho văn bản tiếng Việt ở mức từ cho độ chính xác trung bình với bộ dữ liệu thứ nhất là 86.42% trong đó kết quả cao nhất là 86.73%. Với bộ dữ liệu thứ hai, độ chính xác trung bình là 85.57% và độ chính xác cao nhất là 85.81%. Thời gian huấn luyện MEM vào khoảng gần 3 tiếng với bộ dữ liệu thứ nhất và khoảng 2 tiếng với bộ dữ liệu thứ hai. MEM cần khá nhiều thời gian để tiến hành kiểm thử, khoảng hơn 10 phút trong cả 2 bộ dữ liệu.  Ở mức hình vị Bảng 10. Độ chính xác khi áp dụng mô hình MEM ở mức hình vị Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình Bộ dữ liệu thứ nhất 89.72 89.93 89.76 90.07 89.86 89.87 Bộ dữ liệu thứ hai 88.63 89.64 89.26 89.36 89.63 89.30 Trong thực nghiệm ở mức hình vị, độ chính xác ở cả hai bộ dữ liệu nhìn chung đều tăng lên đáng kể: Với bộ dữ liệu thứ nhất là 89.87% ở giá trị trung bình, trong đó kết quả cao nhất là 90.07%; Với bộ dữ liệu thứ hai, độ chính xác trung bình là 89.30% và cao nhất là 89.64%. Thời gian huấn luyện tăng lên khoảng hơn 1.5 lần so với ở mức từ (khoảng 4,5 tiếng để huấn luyện mô hình sử dụng bộ dữ liệu thứ nhất và khoảng 3 tiếng nếu sử dụng bộ dữ liệu thứ hai). Thời gian kiểm thử vào khoảng 20 phút với bộ dữ liệu thứ nhất và 15 phút với bộ dữ liệu thứ hai. Tương tự MEM, đối với CRF dữ liệu huấn luyện và kiểm thử cũng được xử lý theo từng câu một. Trong thực nghiệm này, việc ước lượng các tham số cho mô mình CRF được tiến hành bằng phương pháp LBFGS. 50 b. Kết quả thực nghiệm áp dụng mô hình CRF  Ở mức từ Bảng 11. Độ chính xác khi áp dụng mô hình CRF ở mức từ Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình Bộ dữ liệu thứ nhất 90.91 91.02 90.87 90.86 90.93 90.92 Bộ dữ liệu thứ hai 89.36 89.61 89.48 89.76 89.72 89.59 Áp dụng CRF ở mức từ, độ chính xác trung bình đạt được với bộ dữ liệu thứ nhất là 90.92% (cao nhất là 91.02%). Với bộ dữ liệu thứ hai, độ chính xác trung bình là 89.59% (cao nhất đạt được là 89.72%). Thời gian huấn luyện nhìn chung là khá lớn (khoảng 5 tiếng với bộ dữ liệu thứ nhất và 4 tiếng với bộ dữ liệu thứ hai). Nhưng ngược lại, thời gian kiểm thử nhỏ, chỉ xấp xỉ 1-2 giây với cả 2 bộ dữ liệu  Ở mức hình vị Bảng 12. Độ chính xác khi áp dụng mô hình CRF ở mức hình vị Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình Bộ dữ liệu thứ nhất 91.32 91.88 91.49 91.68 91.83 91.64 Bộ dữ liệu thứ hai 89.82 90.35 90.76 89.95 89.98 90.17 Ở mức hình vị, độ chính xác trung bình đạt được với bộ dữ liệu thứ nhất là 91.64%, trong đó cao nhất là là 91.88%, với bộ dữ liệu thứ hai, độ chính xác trung bình là 90.17% và độ chính xác cao nhất là 90.76%. Như vậy, độ chính xác có tăng so với thực nghiệm ở mức từ, nhưng độ tăng không nhiều (khoảng 0,6 – 0,7%). Thực nghiệm ở mức hình vị với CRF mất nhiều thời gian để huấn luyện và kiểm thử hơn so với thực nghiệm ở mức từ, mức tăng vào khoảng hơn 3 tiếng, thời gian kiểm thử tăng không đáng kể và vẫn ở mức thấp. c. Kết quả thực nghiệm áp dụng mô hình SVM Để phục vụ cho việc trích chọn các đặc trưng về từ hoặc hình vị, một từ điển các từ và hình vị đã được xây dựng, việc số hóa các đặc trưng theo yêu cầu đầu vào của mô hình dựa trên số thứ tự của từ hoặc hình vị trong từ điển này. Kết quả thực nghiệm áp dụng mô hình SVM được cho ở bảng 14 và bảng 15 dưới đây. 51  Ở mức từ Bảng 13. Độ chính xác khi áp dụng mô hình SVM ở mức từ Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình Bộ dữ liệu thứ nhất 89.44 88.59 88.62 88.21 88.96 88.76 Bộ dữ liệu thứ hai 87.27 86.89 87.16 86.93 87.05 87.06 Thực nghiệm áp dụng mô hình SVM ở mức từ cho độ chính xác trung bình với bộ dữ liệu thứ nhất là 88.76%, kết quả cao nhất là 89.44%, hai con số này với bộ dữ liệu thứ hai lần lượt là 87.06% và 87.27%. SVM không cần quá nhiều thời gian để huấn luyện, (khoảng nửa giờ đến một giờ trong cả 2 bộ dữ liệu). Tốc độ kiểm thử cũng khá tốt, chỉ nằm trong khoảng 4-5 giây.  Ở mức hình vị Bảng 14. Độ chính xác khi áp dụng mô hình SVM ở mức hình vị Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Trung bình Bộ dữ liệu thứ nhất 90.41 91.24 90.81 90.88 90.56 90.78 Bộ dữ liệu thứ hai 89.96 89.16 89.79 89.16 88.96 89.41 Ở mức hình vị, nhìn chung độ chính xác tăng hơn khá nhiều so mới mức từ (khoảng 2%), độ chính xác trung bình với bộ dữ liệu thứ nhất là 90.78%, cao nhất là 91.24%, với bộ dữ liệu thứ hai là 89.41% ở mức trung bình và 89.96% là độ chính xác cao nhất. Thời gian huấn luyện ở mức hình vị chỉ tăng lên khoảng 20 phút so với huấn luyện ở mức từ, thời gian kiểm thử tăng không đáng kể và vẫn ở mức thấp, nằm trong khoảng 5-6 giây. 4.5.2. Tổng hợp kết quả Để phục vụ cho việc đánh giá và so sánh kết quả áp dụng các mô hình học máy khác nhau cho bài toán gán nhãn từ loại tiếng Việt, hình 16 và 17 dưới đây tổng hợp các kết quả trung bình về độ chính xác khi áp dụng ba mô hình học máy cho bộ dữ liệu thứ nhất và bộ dữ liệu thứ hai. 52 a. Thực nghiệm với bộ dữ liệu thứ nhất Các lần thực nghiệm tiến hành với trung bình khoảng 8000 câu cho huấn luyện và 2000 câu cho kiểm thử. Kết quả được tổng hợp trong hình 16. Hình 16. Độ chính xác trung bình trong thực nghiệm với bộ dữ liệu thứ nhất b. Thực nghiệm với bộ dữ liệu thứ hai Các lần thực nghiệm tiến hành với trung bình khoảng 6000 câu cho huấn luyện và 1500 câu cho kiểm thử. Kết quả được tổng hợp trong hình 17. Hình 17. Độ chính xác trung bình trong thực nghiệm với bộ dữ liệu thứ hai 85.57 89.3 89.59 90.17 87.06 89.41 80 85 90 95 100 MEM CRF SVM Mức từ Mức hình vị 86.42 89.87 90.92 91.64 88.76 90.78 80 85 90 95 100 MEM CRF SVM Mức từ Mức hình vị 53 4.5.3. Đánh giá và thảo luận Qua tiến hành thực nghiệm áp dụng ba mô hình học máy MEM, CRF và SVM cho bài toán gán nhãn từ loại tiếng Việt, sử dụng 2 bộ dữ liệu và 2 tập nhãn tương ứng khác nhau trên cùng một môi trường thực nghiệm và cùng cách lấy đặc trưng, có thể đưa ra một số nhận xét như sau:  Thực nghiệm cho thấy tính khả quan của các hướng tiếp cận dựa trên các mô hình MEM, CRF và SVM cho bài toán gán nhãn từ loại tiếng Việt. Dù trong nội dung của khóa luận mới chỉ tích hợp được một số đặc trưng đơn giản (chưa tích hợp từ điển từ vựng, các hệ luật bổ sung để chữa lỗi, …), nhưng bước đầu cả ba phương pháp đều cho kết quả về độ chính xác rất đáng chú ý. Trong đó, phương pháp áp dụng mô hình CRF hầu như luôn cho độ chính xác cao nhất trong tất cả các thực nghiệm. Nhìn chung, có thể sắp xếp về độ chính xác của ba phương pháp theo thứ tự tăng dần như sau: MEM < SVM < CRF  Cũng về độ chính xác, nhìn chung cách tiếp cận ở mức hình vị cho kết quả chính xác hơn ở mức từ, các phương pháp có sự chênh lệch về kết quả khác nhau. Điều này chứng tỏ đối với các phương pháp này, cách trích chọn đặc trưng dựa trên thông tin về hình vị là phù hợp hơn so với cách trích chọn đặc trưng dựa trên thông tin về từ. o Đối với MEM, cách tiếp cận thực nghiệm dựa trên mức hình vị cho kết quả khả quan hơn hẳn so với cách tiếp cân dựa trên mức từ (tăng lên trung bình 3-4%). o Khi áp dụng SVM, thực nghiệm ở mức hình vị cho độ chính xác tăng lên trung bình hơn 2%, tuy không phải là con số vượt trội như MEM, nhưng đây vẫn là cải thiện kết quả đáng chú ý. o CRF luôn cho độ chính xác cao nhất, và độ chính xác cũng có tăng khi thự nghiệm ở mức từ, tuy nhiên độ chênh lệch không nhiều, chỉ khoảng 0.6%.  Thời gian huấn luyện của các phương pháp khá chênh lệch. Lấy ví dụ với bộ dữ liệu thứ nhất, trong khi SVM chỉ mất khoảng một giờ để huấn luyện ở mức từ thì CRF mất đến 5 tiếng để huấn luyện, và con số này đối với MEM là 3 tiếng. 54 Tuy nhiên khi áp dụng vào thực tế, thường thì ta sẽ chỉ phải huấn luyện một lần cho tất cả các lần sử dụng về sau, vì vậy yếu tố thời gian huấn luyện không hẳn là một trở ngại quá lớn. Từ kết quả thực nghiệm, có thể sắp xếp theo thứ tự giảm dần của thời gian huấn luyện như sau: CRF > MEM > SVM  Thời gian kiểm thử, cũng tức là thời gian mà hệ thống tiến hành gán nhãn cho một văn bản lạ, là yếu tố quan trọng cần phải xét đến vì nó góp phần quyết định đến khả năng sử dụng trong các ứng dụng thực tế. Ngược lại với thời gian huấn luyện, CRF tiến hành kiểm thử rất nhanh (chỉ khoảng 1-3 giây), SVM kiểm thử chậm hơn CRF, nhưng cũng chỉ dừng lại trong mức 5-6 giây. Trong khi đó MEM cần đến khoảng 10-20 phút cho việc kiểm thử. Ta có thể đưa ra so sánh tương đối về thời gian kiểm thử của ba mô hình theo thứ tự giảm dần là: MEM < SVM <CRF 55 KẾT LUẬN Những vấn đề đã được giải quyết trong khoá luận Trong khuôn khổ một khóa luận tốt nghiệp đại học, nội dung nghiên cứu tập trung tìm hiểu về một bài toán cơ bản trong xử lý ngôn ngữ tự nhiên là bài toán gán nhãn từ loại và việc giải quyết bài toán này cho tiếng Việt. Tuy chưa đạt được một kết quả đặc biệt vượt trội, nhưng hy vọng khóa luận sẽ góp phần đem lại lợi ích cho cộng đồng nghiên cứu vấn đề xử lý ngôn ngữ tiếng Việt. Các đóng góp của khóa luận gồm các điểm chính như sau:  Về lý thuyết Khóa luận đã hệ thống hóa một số vấn đề lý thuyết về gán nhãn từ loại cũng như nắm bắt được các cách tiếp cận khác nhau cũng như tình hình nghiên cứu trong nước và thế giới. Đồng thời, khóa luận cũng đã trình bày, phân tích việc áp dụng ba mô hình học máy tiên tiến hiện nay là MEM, CRF và SVM cho bài toán gán nhãn từ loại tiếng Việt.  Về thực nghiệm Dựa trên cơ sở lý thuyết đã tìm hiểu được, khóa luận tiến hành thực nghiệm áp dụng ba mô hình học máy MEM, CRF và SVM trên cùng một môi trường thực nghiệm và cách lấy đặc trưng để đưa ra so sánh khách quan. Việc thực nghiệm được tiến hành theo hướng tiếp cận ở mức từ và mức hình vị với hai bộ dữ liệu khác nhau. Kết quả thực nghiệm cho thấy cả ba phương pháp học máy đã được áp dụng đều cho độ chính xác khá cao, đặc biệt là CRF (ở mức hình vị là 91.64% với bộ dữ liệu thứ nhất và 90.17 với bộ dữ liệu thứ hai). Trong đó, thực nghiệm dựa trên mức hình vị cho độ chính xác cao hơn so với dựa trên mức từ, chứng tỏ đối với tiếng Việt, cách trích chọn đặc trưng dựa trên thông tin về hình vị là phù hợp hơn. Bên cạnh đó, các yếu tố về thời gian có sự chênh lệch khá nhiều (CRF cần nhiều thời gian để huấn luyện nhất, bù lại tốc độ gán nhãn rất nhanh, SVM có ưu thế về mặt thời gian huấn luyện, tốc độ gán nhãn cũng khá tốt, trong khi đó MEM tuy không cần quá nhiều thời gian để huấn luyện nhưng tốc độ gán nhãn lại chậm hơn nhiều so với hai phương pháp còn lại). Như vậy việc lựa chọn sử dụng mô hình áp dụng cần phù hợp điều kiện thực tế. Kết quả thu được là khá tương đồng với các nghiên cứu tương tự trên thế giới, điều này chứng tỏ tập đặc trưng sử dụng là chấp nhận được và ba mô hình học máy đều rất khả thi để áp dụng cho bài toán gán nhãn từ loại tiếng Việt. Tuy những kết quả ban đầu có độ chính 56 xác chưa thật xuất sắc, nhưng chúng cũng đáp ứng được tốt yêu cầu đặt ra ban đầu của đề tài và đặt nền tảng cho các nghiên cứu tiếp theo. Công việc nghiên cứu tiếp theo Do còn nhiều hạn chế về thời gian và kiến thức, khoá luận còn một số vấn đề cần tiếp tục hoàn thiện và phát triển trong thời gian tới:  Tiếp tục nghiên cứu kỹ hơn về lý thuyết các mô hình học máy, thay đổi các tham số, thuật toán hay hàm nhân được sử dụng khi áp dụng mô hình với hy vọng cải thiện kết quả tốt hơn.  Thử thay đổi tập đặc trưng để đánh giá kết quả cũng như giá trị và độ phù hợp của từng đặc trưng đối với những đặc trưng riêng của tiếng Việt.  Tìm hiểu thêm các đặc điểm của tiếng Việt để xây dựng các đặc trưng mới, hữu ích để có thể sử dụng cho bài toán gán nhãn từ loại, cùng với đó là tích hợp từ điển từ vựng hỗ trợ nhằm tăng độ chính xác của kết quả.  Tiến hành thực nghiệm gán nhãn từ loại với tập nhãn ở mức mịn hơn. 57 TÀI LIỆU THAM KHẢO Tài liệu tham khảo Tiếng Việt [1] Diệp Quang Ban. Ngữ pháp Việt Nam. NXB Đại học Sư phạm, 2004. [2] Nguyễn Quang Châu, Phan Thị Tươi, Cao Hoàng Trụ. Gán nhãn từ loại cho Tiếng Việt dựa trên văn phong và tính toán xác suất. Đăng trên tạp chí phát triển KH&CN, tập 9, số 2-2006. [3] Nguyễn Thị Minh Huyền, Vũ Xuân Lương, Lê Hồng Phương. Sử dụng bộ gán nhãn từ loại xác suất QTAG cho văn bản Tiếng Việt. Báo cáo hội thảo ICT.rda, 2003. [4] Trần Thị Oanh. Mô hình tách từ, gán nhãn từ loại và hướng tiếp cận tích hợp cho tiếng Việt. Luận văn cao học, trường Đại học Công nghệ, Đại học Quốc gia Hà Nội, 2008. Tài liệu tham khảo tiếng Anh [5] Robert Dale, H. L. Somers, Hermann Moisl. Handbook of Natural Language Processing. Published by Marcel Dekker, Inc, New York, NY, USA, 2000. Chapter 17. [6] Dinh Dien, Hoang Kiem. POS-Tagger for English-Vietnamese Bilingual Corpus. In HLT-NAACL 2003 Workshop: Building and Using Parallel Texts Data Driven Machine Translation and Beyond, pp.88-95, Edmonton. May-June 2003. [7] Yair Halevi. Part of Speech Tagging Slide. Seminar in Natural Language Processing and Computational Linguistics, The Blavatnik School of Computer Science – Tel Aviv University. 25 April 2006. [8] Introduction to SVM (Support Vector Machine) and CRF (Conditional Random Field) Slide. Artifical Intelligence Lab, the University of Arizona. Courses Syllabus of MIS510, Spring 2009. [9] Daniel Jurafsky, Jame H. Martin. Speech and language processing. Draft of September 28, 1999. Published by Prentice-Hall, Inc, 2000. Pp. 285-317. 58 [10] John Laferty, Andrew McCallum, Fernando Pereira. Conditional Random Fields: Probabilistic Models for segmenting and labeling Sequence Data. In Proc. of the Eighteenth International Conference on Machine Learning (ICML-2001), 2001. [11] Andrew W. Moore. Support Vector Machines Slide. The Auton Lab, Carnegie Mellon University's School of Computer Science. Nov 23rd, 2001. [12] Masaki Murata, Qing Ma, Hitoshi Isahara. Comparison of Three Machine- Learning Methods for Thai Part-of-Speech Tagging. In Proc. ACM Transactions on Asian Language Information Processing, Vol. 1, No. 2, June 2002, Pages 145-158. [13] Hwee Tou Ng, in Kiat Low. Chinese Part-of-Speech Tagging: One-at-a- Time or All-at-Once? Word-Based or Character-Based? Department of Computer ScienceNational University of Singapore. In Proc. of the Fifth SIGHAN Workshop on Chinese Language Processing, pages 205–208, Sydney, July 2006. [14] Owen Rambow. Introduction to Syntax, with Part-of-Speech Tagging Slide. Computer Science at Columbia University. September 17 & 19, 2008. [15] A.Ratnaparkhi. A maximum entropy model for part-of-speech tagging. In Proc. Emparical Methods for Natural Language Processing, 1996. [16] Richard Sproat. Introduction to Speech Technology (Language Models, HMMs, Forward Algorithm, Viterbi Algorithm…) Slide. Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign. ECE 398RS Courses, Fall 2007. [17] Cam-Tu Nguyen, Trung-Kien Nguyen, Xuan-Hieu Phan, Le-Minh Nguyen, Quang-Thuy Ha. Vietnamese word segmentation with crfs and svms: An investigation. In Proc. of the 20th Pacific Asia Conference on Language, Information and Computation (PACLIC20), pages 215_222. Wuhan, China, 2005. [18] Universita’ di Venezia. Part-of-speech Tagging Courses Slide. September, 2003. 59 [19] Hanna M.Wallach. Conditional Random Fields: An introduction. Technical Report MS-CIS-04-21, Department of Computer and Information Science, University of Pennsylvania. February 24, 2004. [20] GouDong Zhou, Jian Su. A Chinese Efficient Analyser Integrating Word Segmentation, Part-Of-Speech Tagging, Partial Parsing and Full Parsing. In the Proc.of the second SIGHAN workshop on Chinese language processing, 2003. [21] Yig Yeong Taek. Word Classes and Part-of-Speech Tagging Slide. In Seminar at Korean Language Processing Lab, 26/5/07. [22] Website: SVMmulticlass based on SVMlight by Joachims. [23] Website: Website is devoted to learning methods building on kernels, such as the support vector machine. [24] Website: Yet Another CRF toolkit by Taku Kudo. [25] Website: Maximum Entropy Modeling.