Luận văn Phân tích câu hỏi trong hệ thống hỏi đáp tiếng Việt

hông gian dữ liệu đầu vào m, vì với một số lượng n các dữ liệu mẫu cố định, tập hợp các siêu phẳng sẽ tăng theo hàm mũ với lũy thừa m. Với bài toán phân lớp trang văn bản, m thường rất lớn, khoảng vài ngàn hay thậm chí là hàng triệu từ. 1 Overfitting: 30 Hình 4. Mối quan hệ giữa các siêu phẳng phân cách Theo lý thuyết học thống kê được phát triển bởi Vapnik năm 1998 chỉ ra rằng có thể xác định một siêu phẳng tối ưu thỏa mãn hai tính chất quan trọng (1) nó là duy nhất với mỗi tập dữ liệu học tách rời tuyến tính; (2) khả năng overfitting là nhỏ hơn so với các siêu phẳng khác. Định nghĩa biên M của bộ phân lớp là khoảng cách giữa các siêu phẳng và các dữ liệu học gần nhất. Siêu phẳng tối ưu nhất là siêu phẳng có biên lớn nhất, điều đó có nghĩa là chúng ta cần tìm siêu phẳng sao cho khoảng cách từ siêu phẳng đến những điểm gần nhất là lớn nhất (Hình 5). Vapnik cũng chứng minh rằng khả năng overfitting với siêu phẳng tối ưu nhỏ hơn so với các siêu phẳng khác. 31 Hình 5. Siêu phẳng tối ưu và biên. Khoảng cách từ một điểm x đến siêu phẳng là: Vì vậy siêu phẳng tối ưu có thể thu được bằng ràng buộc tối ưu sau: 0w,w max M sao cho Ti i 0 1 y (w x w ) M,i 1,...n || w || + ≥ = Trong đó ràng buộc yêu cầu mọi tài liệu học (tương đương với các điểm) phải nằm trên nửa mặt phẳng của nó và khoảng cách tới siêu phẳng lớn hơn hoặc bằng M. Đặt 1w M= biểu thức trên được viết lại như sau 0w,w min W sao cho Ti i 0y (w x w ) M,i 1,...,n+ ≥ = Đưa về phương trình Lagrangian: ( )n2 Ti i 0 i 1 1L(D) || w || y w w 1 2 = ⎡ ⎤= − + α + −⎣ ⎦∑ 0|||| 1 wxw w T + 32 Sau đó tính đạo hàm của phương trình trên theo w,w0 ta được n T i i 1 1max 2α = − α Λα + α∑ thỏa mãn i 0,i 1,...,nα ≥ = Với Λ là ma trận n×n trong đó iα = yiyj jTi xx . Đây là bài toán bậc hai, theo lý thuyết có thể giải được bằng phương pháp chuẩn tối ưu. Với mỗi dữ liệu học i, cách giải phải thỏa mãn điều kiện: iα ( )[ ]1wwy 0Ti −+ =0 Và do đó hoặc iα = 0 hoặc )wxw(y 0iTi + =1. Nói cách khác, nếu iα >0 thì khoảng cách từ điểm xi đến mặt phẳng phân cách là M . Các điểm thỏa mãn iα >0 được gọi là các vector hỗ trợ. Hàm quyết định h(x) có thể được tính qua công thức dấu của f(x) hoặc tương đương với dạng sau: i T i n 1i i xxxy(x) ∑ = =f Những kết quả trong phần trên chỉ áp dụng cho trường hợp các tập có thể phân chia tuyến tính. Với các tập không thể phân chia tuyến tính, người ta đưa ra giải pháp “lề mềm” (soft margin) [5] . Hàm tối ưu trong trường hợp này là: ∑ = + n 1i C||w||min iww, ξ0 thỏa mãn ( )+ ≥ − = ≥ = ⎧⎪⎨⎪⎩ T i i 0 i i y w x w 1 ξ ,i 1,...,n ξ 0, i 1,...,n Ở đây, iξ gọi là biến nới lỏng (slack variables), hay các biến dương thể hiện mức độ chịu lỗi của bộ phân lớp (tolerances of misclassification). Thông qua đó, các vector huấn luyện được phép rơi vào trong khoảng chịu lỗi dọc theo biên ngăn cách hai lớp như được mô tả trong hình 6. 33 Hình 6. Biến nới lỏng cho soft margin Vấn đề này có thể đưa về dạng: 1 1max 2 n T i iα α α α = − Λ +∑ thỏa mãn Cα0 i ≤≤ i=1,…,n Bộ phân lớp theo cách này được gọi là bộ phân lớp máy vector hỗ trợ – Support Vector Machine. Nếu dữ liệu học là không tách rời tuyến tính, độ chính xác của bộ phân lớp SVM sẽ rất thấp, ngay cả với siêu phẳng tuyến tính tốt nhất. Phương pháp trình bày ở trên có thể mở rộng để phù hợp với dữ liệu không tách rời tuyến tính bằng cách sử dụng hàm nhân để ánh xạ mỗi điểm x ∈ Rm vào một không gian có số chiều lớn hơn (có thể là vô hạn chiều) gọi là không gian đặc trưng mà ở trong không gian này dữ liệu là tách rời tuyến tính Phân lớp đa lớp với SVM Bài toán phân lớp câu hỏi yêu cầu một bộ phân lớp đa lớp do đó cần cải tiến SVM cơ bản (phân lớp nhị phân) thành bộ phân lớp đa lớp. Một trong những phương pháp cải tiến đó là sử dụng thuật toán 1-against-all [40]. Ý tưởng cơ bản là chuyển bài toán phân lớp nhiều lớp thành nhiều bài toán phân lớp nhị phân như sau: 34 - Giả sử tập dữ liệu mẫu (x1,y1), … ,(xm,ym) với xi là một vector n chiều và yi ∈Y là nhãn lớp được gán cho vector xi (có m nhãn lớp khác nhau). - Biến đổi tập Y ban đầu thành m tập có hai lớp con có cấu trúc như sau. Zi ={yi , \ iY y } . - Áp dụng SVM phân lớp nhị phân cơ bản với m tập Zi để xây dựng siêu phẳng cho phân lớp này. - Bộ phân lớp với sự kết hợp của m bộ phân lớp trên được gọi là bộ phân lớp đa lớp mở rộng với SVM. 3.1.2.2. MEM Theo [4], đối với bài toán phân lớp dữ liệu, Entropy cực đại là một kỹ thuật dùng để ước lượng xác suất các phân phối từ dữ liệu. Tư tưởng chủ đạo của nguyên lý Entropy cực đại là “mô hình phân phối đối với mỗi tập dữ liệu và tập các ràng buộc đi cùng phải đạt được độ cân bằng đều nhất có thể ” – (có Entropy cực đại). Tập dữ liệu được học (đã được gán nhãn) được sử dụng để tìm ra các ràng buộc cho mô hình - là cơ sở để ước lượng phân phối cho từng lớp cụ thể. Những ràng buộc này được thể hiện bởi các giá trị ước lượng được của các đặc trưng. Từ các ràng buộc sinh ra bởi tập dữ liệu này, mô hình sẽ tiến hành tính toán để có được một phân phối với Entropy cực đại. Ví dụ về mô hình Entropy cực đại: “Giả sử với bộ phân lớp bài báo của báo điện từ Vnexpress. Bốn lớp chính chỉ ra đó là pháp_luật, thể_thao, quốc_tế, văn_hóa. Các thống kê trên tập dữ liệu mẫu chỉ ra rằng trung bình 70% các tài liệu trong lớp thể_thao có chứa từ bóng_đá. Như vậy một cách trực quan có thể thấy rằng nếu một tài liệu D có chứa từ bóng_đá thì xác suất được phân vào lớp thể_thao là 70% và xác suất phân vào ba lớp còn lại 10% ( bằng nhau giữa các lớp) và nếu D không chứa từ thể_thao thì xác suất phân phối của D là đều cho bốn lớp (mỗi lớp 25%).” Trong ví dụ trên “tài liệu chứa cụm bóng_đá thì có xác suất phân vào lớp thể_thao là 70%” là một ràng buộc của mô hình. 35 a. Các ràng buộc và đặc trưng Đối với nguyên lý Entropy cực đại, các ràng buộc cho phân phối điều kiện sẽ được thiết lập dựa trên tập dữ liệu mẫu. Mỗi một ràng buộc biểu thị một đặc điểm của tập dữ liệu học. Một đặc trưng trong mô hình Entropy cực đại được biểu hiện bởi một hàm fi(D;C). Nguyên lý cực đại Entropy cho phép chúng ta thu hẹp mô hình phân phối để thu được giá trị kỳ vọng cân bằng cho từng đặc trưng của dữ liệu. Xác suất phân phối của dữ liệu D cho lớp C thỏa mãn phương trình sau: ( )( ) ( ) ( ) ( ) (*) cd,fd|cPdPdcd,f |D| 1 i cdDd i ∑∑∑ = ∈ Trong phương trình (*) D là tập dữ liệu và C là một lớp câu hỏi. Ở một khía cạnh khác, fi(D;C) có thể được hiểu như: Nếu C là tập các lớp có thể mà chúng ta muốn phân lớp và D là tập các ngữ cảnh ( ràng buộc) có thể mà chúng ta quan sát được, thì mệnh đề biểu diễn thông tin ngữ cảnh là một hàm có dạng như sau: {0,1}DC :f →× Và được mô tả như sau: 1 khi c=c′ và cp(d) = true 0 trong trường hợp còn lại Trong đó cp(d) là một hàm có dạng: cp: d→ {true, false} Hàm này trả về giá trị true hoặc false, phụ thuộc vào sự xuất hiện hoặc không xuất hiện của các thông tin hữu ích trong một số ngữ cảnh d trong D. Ví dụ: - c' là lớp “thể_thao”, d là văn bản hiện tại. - cp = [ câu hiện tại chứa cụm từ “bóng_đá” ]. thì hàm đặc điểm này sẽ trả về giá trị 1 nếu như lớp dự đoán a là “thể_thao” và mang giá trị 0 trong các trường hợp còn lại. Bước đầu tiên khi sử dụng cự đại Entropy là phải xác định được tập hàm đặc trưng cho bộ phân lớp, sau đó đánh giá giá trị kỳ vọng của đặc trưng ấy trên tập dữ liệu học để biến hàm đặc trưng này thành một ràng buộc của phân lớp. fcp,c′ (c,d) = 36 b. Mô hình Entropy cực đại Mô hình xác suất Entropy cực đại cung cấp một cách đơn giản để kết hợp các đặc trưng của dữ liệu trong những ngữ cảnh khác nhau để ước lượng xác suất của một số lớp xuất hiện cùng với một số ngữ cảnh này. Trước tiên chúng ta sẽ mô tả cách biểu diễn đặc trưng này và kết hợp nó vào một dạng riêng của mô hình xác suất dưới các hình mẫu. Tư tưởng chủ đạo của phương pháp Entropy cực đại là tìm được một mô hình có phân phối xác suất thỏa mãn mọi ràng buộc quan sát được từ dữ liệu mà không đưa thêm bất kì một giả thiết nào khác. Theo nguyên lý Entropy cực đại, phân phối cần đáp ứng dữ liệu quan sát và làm cực đại độ đo Entropy có điều kiện: ( ) ( ) ( ) ( ) , | log |≡ −∑ % c d H p p c p c d p d c ( )* argmax ∈ = p C p H p (p * là phân phối xác suất tối ưu) Mô hình Entropy cực đại xây dựng các đặc trưng từ tập dữ liệu huấn luyện. Mỗi đặc trưng nhận hàm hai của câu hỏi và lớp, hàm này nhận một trong hai giá trị đúng hoặc sai. Tập các ràng buộc sẽ được thiết lập từ các đặc trưng này. Một ràng buộc là một điều kiện từ dữ liệu buộc mô hình phải thỏa mãn. Mỗi đặc trưng fi được gán một trọng số iλ . Khi đó, bài toán phân lớp đưa về bài toán ước lượng xác suất có điều kiện: ( ) ( )i i i 1P c | d exp f d,c Z(d) ⎛ ⎞= λ⎜ ⎟⎝ ⎠∑ trong đó Z(d) là biểu thức chuẩn hóa để bảm bảo điều kiện ( ) 1d|cp =∑ , có công thức như sau: Khi các đặc trưng được ước lượng từ tập dữ liệu mẫu, thì giải pháp cho mô hình Entropy cực đại giống với giải pháp với bài toán cực đại hóa likelihood trên mô hình mũ sau: ( ) ( )∑ ∑ ⎟⎠⎞⎜⎝⎛ λ= c ii i c,dfexpdZ 37 ( ) ( )∏ = = k 1i dc,f i iλ Z(d) 1d|cP ( )∑∏ = = c k 1i dc,f i iλZ(d) ( ) ( ) ( )~ c,d L P p c,d logp c|d=∑ Tức là p* arg max L(p) arg max H(p)= = . c. Thuật toán uớc lượng tham số Ước lượng tập tham số { }1 n, ...,λ = λ λ để huấn luyện mô hình Entropy đạt được cực đại. Trên thế giới hiện nay có nhiều phương pháp để ước lượng tập tham số này như: thuật toán GIS – Generalized Iterative Scaling, thuật toán IIS – Improved Iterative Scaling là thuật toán ước lượng tham số của mô hình mũ do các thành viên trong nhóm nghiên cứu tại IBM’s T. J. Watson Research Center đưa ra vào những năm đầu của thập kỉ 1990, thuật toán L-BFGS – Limited memory BFGS – là phương pháp giới hạn bộ nhớ cho phương pháp quasi-Newton cho phép tối ưu hàng triệu tham số với tốc độ rất nhanh. 3.1.3. Xây dựng bộ phân lớp câu hỏi theo học máy thống kê Bài toán phân lớp câu hỏi cũng có thể coi là bài toán phân lớp văn bản, trong đó mỗi câu hỏi được xem là một văn bản. Tuy nhiên phân lớp câu hỏi có một số đặc trưng riêng so với phân lớp văn bản: - Số lượng từ trong một câu hỏi ít hơn nhiều trong một văn bản, do đó dữ liệu câu hỏi là rất rời rạc. Việc biểu diễn câu hỏi theo tần suất từ (TF, IDF) hầu như không tăng hiệu quả phân lớp vì các từ thường chỉ xuất hiện một lần trong câu hỏi. - Các từ dừng trong phân lớp văn bản là quan trọng với phân lớp câu hỏi. - Số lượng nhãn lớp thường rất lớn. Đối với các thuật toán phân lớp, khi số lượng lớp tăng thì hiệu quả sẽ giảm [36]. Nhiều hệ thống Q&A đã áp dụng phân lớp đa cấp nhằm giảm số lượng lớp tại mỗi bộ phân lớp ở từng cấp. 38 3.1.3.1. Mô hình phân lớp câu hỏi Phân lớp câu hỏi sử dụng học máy thống kê hiện đang nhận được sự chú ý của nhiều nhà nghiên cứu [20,25,36,41]. Li và Roth [25] xây dựng một bộ phân lớp câu hỏi phân cấp dựa trên một taxonomy câu hỏi 2 cấp thể hiện sự phân lớp ngữ nghĩa tự nhiên của câu trả lời. Cấu trúc phân cấp bao gồm 6 lớp câu hỏi thô (coarse class) là ABBREVIATION (viết tắt), ENTITY (thực thể), DESCRIPTION (mô tả), HUMAN (con người), LOCATION (địa điểm) và NUMERIC VALUE (giá trị số). Mỗi lớp câu hỏi thô lại được phân chia thành các lớp con (fine class). Taxonomy câu hỏi của Li và Roth được trình bày chi tiết trong bảng 1 (Mục 2.4). Theo Li và Roth thì phân lớp câu hỏi có tính nhập nhằng, tức là một câu hỏi có thể được phân vào nhiều lớp do không có một ranh giới rõ ràng nào giữa các lớp. Ví dụ câu hỏi “Sử tử ăn gì ?” có thể được phân vào lớp food (thức ăn), animal (động vật) hay câu hỏi “Đại học Công Nghệ ở đâu ?” có thể được phân vào lớp country (đất nước), state (tỉnh)… Vì vậy bộ phân lớp thô sẽ cho đầu ra là một số nhãn lớp thô (phân lớp đa nhãn). Câu hỏi lần lượt được cho qua hai bộ phân lớp Coarse_Classifier và Fine_Classifier. Theo hình 7, câu hỏi ban đầu được phân lớp bởi bộ phân lớp thô Coarse_Classifier cho ra một tập các lớp thô. C1 = Coarse_Classifier(C) = { c1,c2,…cn} với |C1| <= 5, |C| = 6, C = {abbreviation, entity, description, human, location, numeric value} Sau đó các nhãn của lớp thô c1,..cn được mở rộng bởi các nhãn lớp con tương ứng. Cụ thể hơn, mỗi nhãn thô ci được ánh xạ vào một tập nhãn lớp con theo taxonomy phân cấp, Fci = { fi1,fi2,….fim} và được tổng hợp lại thành C2 = U Fci. Bộ phân lớp tinh Fine_Classifier sẽ xác định tập các nhãn lớp con C3 = Fine_Classifier(C2) với |C3| <=5. Kết quả đầu ra là hợp của C1 và C3 được sử dụng cho quá trình tìm câu trả lời. 39 Hình 7. Mô hình bộ phân lớp đa cấp của Li và Roth Kết quả mà Li và Roth đạt được khá tốt, độ chính xác là 84.2% cho 50 lớp con và 91% cho 6 lớp cha với thuật toán SnoW. Sử dụng taxonomy câu hỏi của Li và Roth, tiến sĩ Nguyễn Trí Thành [36] đã áp dụng học bán giám sát để tận dụng dữ liệu câu hỏi chưa gán nhãn nhằm tăng độ chính xác cho phân lớp câu hỏi và đề xuất hai cách thay đổi thuật toán Tri-training để phù hợp với dữ liệu câu hỏi. 3.1.3.2. Trích chọn đặc trưng cho phân lớp câu hỏi Trích chọn đặc trưng có ý nghĩa quan trọng, ảnh hưởng trực tiếp đến kết quả phân lớp. Các loại đặc trưng chính thường được sử dụng là tập từ (bag-of-word) và tập các cặp từ/nhãn từ loại (bag-of-word/POS tag). Việc phân loại câu hỏi có điểm khác với phân loại văn bản đó là câu hỏi chỉ chứa một số ít từ trong khi văn bản có số lượng từ rất lớn. Trọng số từ (TF – term frequency) góp phần quan trọng trong nâng cao độ chính xác của phân lớp văn bản, trong khi với câu hỏi các từ hầu như chỉ xuất hiện một lần duy nhất, do đó việc biểu diễn câu hỏi theo trọng số từ không có ý nghĩa mấy trong phân lớp câu hỏi. Trong phân lớp văn bản các từ như “nào”, “gì”, “sao” thường được coi là từ dừng (stop word) và bị loại bỏ ở bước trích chọn đặc trưng. Việc này là rất quan trọng trong nâng cao hiệu quả của bộ phân lớp và đã được chứng minh trong [21]. Tuy nhiên những từ này lại có ý nghĩa rất quan trọng trong phân lớp câu hỏi. Để có thể giữ lại các từ này 40 mà vẫn giảm được số chiều của không gian biểu diễn dữ liệu, trong tiếng Anh kĩ thuật stemming thường được áp dụng. Ví dụ trong tiếng Anh, các động từ được chuyển về dạng nguyên thể (“was”, “were”, “is”, “are”, “am” được chuyển hết thành “be”), các danh từ số nhiều chuyển về dạng danh từ số ít (“children” thành “child”, “girls” thành “girl” …), các số từ đều được chuyển về cùng một giá trị (“2004”, “1.5”, “5” đều chuyển thành “100”) [36]. Ví dụ: “Thủ tướng Việt Nam năm 2007 là ai” Được chuyển thành: “Thủ tướng Việt Nam năm 100 là ai” Sau bước tiền xử lý này, một tập V các từ khác nhau xuất hiện trong tập câu hỏi ví dụ sẽ được trích ra (gọi là từ điển – dictionary). Gọi N là kích thước của từ điển, N chính là số chiều của không gian biểu diễn câu hỏi. Các câu hỏi sẽ được biểu diễn dưới dạng vector gồm N thành phần: qi= (w1,w2,…..,wN) trong đó wi = 1 nếu từ thứ i trong từ điển xuất hiện trong câu hỏi qi. 0 nếu từ thứ i trong từ điển không xuất hiện trong câu hỏi qi Các vector này là đầu vào cho bộ phân lớp. Với loại đặc trưng là tập các cặp từ/nhãn từ loại thì tập từ điển V sẽ khác một chút. Các cặp từ/nhãn từ loại là thành phần của từ điển. Một từ có thể có nhiều chức năng ngữ pháp, có lúc đóng vai trò là danh từ, có lúc lại là động từ (ví dụ từ “đá”, “bò” …). Những từ này sẽ được chuyển thành “đá”- danh từ và “đá”-động từ và được tính là hai thành phần khác nhau của từ điển. Việc biểu diễn đặc trưng dưới dạng từ/nhãn từ loại sẽ giúp phân biệt được các từ này theo các nghĩa khác nhau. Trong tiếng Anh việc biểu diễn câu hỏi dưới dạng bag-of-word là khá đơn giản bởi đặc trưng của tiếng Anh là các từ phân cách nhau bởi khoảng trắng. Do đó việc sử dụng unigram cũng chính là bag-of-word. Trong khi với tiếng Việt, một từ có thể được ghép lại từ nhiều âm tiết, do đó không thể dùng khoảng trắng làm ranh giới phân cách các từ. Cần thiết phải có một công cụ tách từ hiệu quả cho tiếng Việt [37] . 41 Việc biểu diễn câu hỏi theo bag-of-word và bag-of-word/POS tag không giữ được các thông tin về trật tự từ trong câu, do đó người ta sử dụng n-gram làm đặc trưng. Bag- of-ngrams là một kỹ thuật biểu diễn văn bản độc lập với ngôn ngữ. Nó chuyển đổi các văn bản/câu hỏi thành các vectơ đặc trưng đa chiều với mỗi đặc trưng tương đương với một chuỗi con liền kề nhau. Để nâng cao độ chính xác của bộ phân lớp, các đặc trưng ngữ nghĩa khác được xem xét. Li và Roth đã xây dựng bộ phân lớp câu hỏi sử dụng thuật toán Sparse Network of Winnows – SnoW với các đặc trưng được sử dụng là: từ vựng (bag-of-word), nhãn từ loại (POS tag), cụm từ (các cụm không giao nhau - non-overlapping), cụm danh từ đầu tiên trong câu hỏi (head chunks) và tên thực thể (named entity). Bộ dữ liệu học bao gồm 5500 câu hỏi được thu thập từ các nguồn: 4.500 câu hỏi tiếng Anh công bố bởi USC1, 500 câu hỏi tự tạo cho một số lớp có ít câu hỏi, 894 câu hỏi thu thập từ tập câu hỏi của TREC 8 và TREC 9 và 500 câu hỏi của TREC 10 cho dữ liệu kiểm tra. Độ chính xác mô hình đạt được là 78,8% với 50 lớp con (phân lớp đa cấp với 6 lớp cha và 50 lớp con). Khi sử dụng danh sách các từ (được xây dựng bằng tay) liên quan đến một lớp câu hỏi thì độ chính xác đạt 84.2 %. Mỗi lớp câu hỏi có một danh sách các từ liên quan, là các từ thường xuyên xuất hiện trong lớp câu hỏi đó. Ví dụ lớp câu hỏi về nguyên nhân có danh sách các từ {“nguyên nhân” , “lí do”, “tại sao”, “vì sao”…}. Bộ dữ liệu do Li và Roth sử dụng đã được công bố và được nhiều nhóm nghiên cứu sử dụng để so sánh kết quả khi thực nghiệm với các thuật toán hoặc các đặc trưng mới để nâng cao kết quả đạt được của phân lớp câu hỏi. Hacioglu và Ward [14] sử dụng máy hỗ trợ vector (support vector machines - SVM) với đặc trưng là bigram và mã sửa lỗi đầu ra (error-correcting output code-ECOC ) đã đạt kết quả 80.2% và 82.0%. Zhang và Lee [41] sử dụng SVMs tuyến tính với đặc trưng là bag-of-word và bag-of-ngram đạt độ chính xác 79.2%. Năm 2006, Li và Roth đã sử dụng thêm các đặc trưng ngữ nghĩa gồm: tên thực thể, nghĩa của từ trong WordNet, danh sách từ liên quan đến lớp câu hỏi (xây dựng bằng tay), các từ có độ tương đồng về mặt ngữ nghĩa (sinh tự động). Việc kết hợp các đặc trưng về ngữ nghĩa này với các đặc trưng về ngữ pháp (POS tag, cụm từ ..) họ đã đạt được độ chính xác 89.3% cho 50 lớp con khi huấn luyện mô hình với 21.500 câu hỏi và kiểm thử với 1000 câu hỏi. Krishnan [24] sử dụng các chuỗi ngắn của câu hỏi (một đến 3 từ) làm 1 42 đặc trưng và đạt được độ chính xác 86.2% cho 50 lớp con khi tiến hành huấn luyện trên bộ dữ liệu 5500 câu hỏi do UIUC công bố và được ghi nhận là kết quả tốt nhất trên tập dữ liệu này. Theo Krishnan thì chỉ cần dựa vào một chuỗi ngắn các từ liên tục trong câu hỏi (gọi là informer span) đã có thể nhận diện được câu hỏi thuộc lớp nào. Vì vậy họ đã sử dụng Conditional Random Field (CRF) để xác định informer span với độ chính xác 85%, sau đó xây dựng bộ phân lớp meta-classifier sử dụng SVM tuyến tính trên kết quả đầu ra của CRF. Hình thức của từ cũng được coi là một loại đặc trưng hữu ích. Đặc trưng hình thức từ bao gồm 5 đặc trưng: Viết hoa tất cả các kí tự trong từ, viết thường tất cả, dạng hỗn hợp (có cả chữ thường lẫn chữ viết hoa), tất cả các kí tự là chữ số (0-9) và các hình thức khác. Các đặc trưng này rất có ích, ví dụ nếu tất cả các kí tự của từ viết hoa thì thường thường đó là tên thực thể, hoặc một dạng viết tắt .., nếu tất cả các kí tự của từ là chữ số thì rất có thể đó là con số, ngày tháng, mã số, điện thoại ….Các đặc trưng hình thức từ này góp phần làm tăng độ chính xác của phân lớp [20]. 3.2. Phương pháp xác định loại câu hỏi sử dụng kĩ thuật xử lý ngôn ngữ tự nhiên Bài báo [15] đã đưa ra một phương pháp tích hợp nhiều kĩ thuật trong xử lý ngôn ngữ tự nhiên dựa trên tri thức vào hệ thống hỏi đáp tự động và thu được kết quả rất tốt. Phương pháp xác định loại câu hỏi được tiến hành như sau (xem minh họa trong Hình 8): - Câu hỏi được phân tích ngữ pháp và biểu diễn dưới dạng cây cú pháp. - Các nút lá của cây được gán nhãn là các từ tương ứng và được chia làm hai loại: non-skip và skip. Các lá non-skip là lá mà nhãn là danh từ, động từ, tính từ, trạng từ. Các lá còn lại thuộc loại skip. 43 Hình 8. Xác định loại câu hỏi sử dụng kĩ thuật xử lý ngôn ngữ tự nhiên - Duyệt cây theo thứ tự bottom-up, gán nhãn cho các nút cha theo nhãn của các nút con nonskip dựa theo các luật xác định. Một luật căn cứ vào nhãn ngữ pháp của nút cha để chọn ra một nút con thích hợp và lan truyền nhãn của nút con này lên mức kế tiếp của cây. Nút con được chọn được coi là nút có mối liên hệ với các nút anh em nonskip khác. Quá trình lan truyền được thực hiện cho đến khi gốc của cây cú pháp được gán nhãn. Một đồ thị ngữ nghĩa cũng được tạo ra trong khi quá trình lan truyền nhãn và từ có số lượng mối liên hệ nhiều nhất với các từ khác được xem là từ trọng tâm (focus word). - Để xác định loại câu hỏi, người ta sử dụng một cây phân cấp các loại câu hỏi dựa trên Wordnet. Loại câu hỏi là các nút cha (hypermym) của từ trọng tâm trong WordNet. 44 Hình 9. Ánh xạ từ trọng tâm vào Wordnet Trong ví dụ ở hình 9, từ researcher là từ trọng tâm, được ánh xạ vào tập subset về scientist, có hypermym là PERSON. Vì vậy câu hỏi này được xác định là câu hỏi về người. Ưu điểm: - Rất mạnh mẽ, có thể xử lý được nhiều loại câu hỏi khác nhau. Dễ dàng mở rộng các lớp do chỉ cần thêm các nhãn lớp vào trong tập synset của WordNet. Nhược điểm: -Việc ánh xạ từ loại câu hỏi vào các tập từ của WordNet phải làm hoàn toàn bằng tay. - Không có cơ chế khử nhập nhằng ngữ nghĩa của từ, nếu từ trọng tâm có nhiều nghĩa trong WordNet thì sẽ chọn tập synset nào đại diện cho loại câu hỏi ? - Chưa xử lý với trường hợp từ trọng tâm không có trong WordNet. - Phải cần tới các công cụ xử lý và các nguồn tài nguyên ngôn ngữ. researcher oceanographe chemist Scientist, man of science America islander, island- westerner inhabitant, dweller, denizen actor actress dancer performer, performing artist ballet dancer tragedian ERSONP What researcher discovered Hepatitis-B vaccine What researcher discovered the vaccine against Hepatitis-B? What is the name of the French oceanographer who owned Calypso? PERSO What oceanographer ownedCalypso name French PERSO 45 3.3. Phương pháp xác định loại câu hỏi sử dụng mẫu quan hệ Một phương pháp khác hay được sử dụng để xác định loại câu hỏi là dựa trên tập mẫu. Yếu tố quyết định hiệu quả của phương pháp này là cần có một tập mẫu tốt, có khả năng bao quát được các trường hợp đa dạng của câu hỏi. Ý tưởng chính của hướng tiếp cận này là “ Trong nhiều trường hợp, câu trả lời và câu hỏi thường có sự tương đồng khá lớn, nhiều khi câu trả lời là sự sắp xếp lại các từ khóa trong câu hỏi”. Ví dụ như câu hỏi “ X là gì” thì câu trả lời thường có dạng “X là Y”. Một thông tin trong ngôn ngữ tự nhiên có thể được diễn đạt theo nhiều cách khác nhau. Vì vậy nếu chúng ta có thể sử dụng nguồn dữ liệu phong phú, đa dạng, dư thừa và nhiều trùng lặp trên Web để học ra các mẫu trả lời của một loại câu hỏi thì khả năng tập mẫu này bao phủ được các trường hợp của câu hỏi là cao. Khó khăn của phương pháp này là cần có một cơ chế đánh giá độ tin cậy của các mẫu sinh ra một cách hợp lý, tuy nhiên việc cài đặt là khá dễ dàng và chỉ tốn ít công sức làm dữ liệu mồi cho quá trình học boostraping. Phương pháp Snowball [7] là một phương pháp học boostraping dựa trên ý tưởng của phương pháp DIPRE [11] dùng để trích ra các mẫu quan hệ và tập dữ liệu cho một quan hệ từ một tập hạt giống nhỏ ban đầu. Bài toán mà Snowball giải quết được phát biểu ngắn gọn như sau: Cho một mối quan hệ (ví dụ - “tổ chức A có trụ sở tại địa điểm B” ) và một số thể hiện của quan hệ đó, gọi là tập hạt giống – seed. Ví dụ: Nhiệm vụ đặt ra là: Tìm các mẫu quan hệ biểu diễn mỗi quan hệ này, sau đó sử dụng các mẫu này để tự động tìm ra các thể hiện khác của quan hệ. Kết quả là một cơ sở dữ liệu lớn các thể hiện của quan hệ được sinh ra từ tập hạt giống nhỏ ban đầu. MICROSOFT REDMOND IBM ARMONK BOEING SEATTLE INTEL SANTA CLARA 46 Hình 10. Mô hình Snowball Hình 10 mô tả vòng lặp hoạt động của Snowball, trong đó hai bước sinh mẫu và sinh seed mới là quan trọng nhất. Vòng lặp này kết thúc khi lượng seed sinh ra đủ lớn hoặc không tìm thêm được seed mới. Snowball biểu diễn các mẫu quan hệ dưới dạng các vector từ có trọng số. Vì vậy mẫu sẽ có khả năng khái quát cao, dễ dàng nhận bắt được các biến thể đa dạng của mẫu. Đồng thời Snowball cũng đưa ra phương pháp tìm kiếm, trích chọn và đánh giá độ tin cậy của seed mới và mẫu mới được sinh ra. Từ đó có thể trích rút ra được một bảng dữ liệu lớn với độ tin cậy từ tập seed mồi ban đầu rất nhỏ. Trong chương 4, chúng tôi có tiến hành thực nghiệm việc phân tích câu hỏi dựa trên tập mẫu (được học bằng phương pháp Snowball) và tích hợp vào hệ thống hỏi đáp tiếng Việt, bước đầu cho kết quả khá tốt. Tag Entities Seed Tuples Find Occurrences of Seed Tuples Generate New Seed Tuples Generate Extraction Patterns Augment Tables 47 Chương 4. Thực nghiệm phân tích câu hỏi tiếng Việt Chương này tiến hành thực nghiệm phân tích câu hỏi trên hai loại hệ thống hỏi đáp khác nhau. Với hệ thống hỏi đáp miền mở, chúng tôi xây dựng bộ phân lớp câu hỏi sử dụng học máy thống kê. Chúng tôi thử nghiệm với hai thuật toán SVM và MEM, đồng thời thử nghiệm với các đặc trưng khác nhau của câu hỏi để tìm ra phương án lựa chọn phù hợp nhất cho phân lớp câu hỏi tiếng Việt. Với hệ thống hỏi đáp miền đóng (miền du lịch), chúng tôi thực nghiệm việc phân tích câu hỏi dựa trên việc trích rút các mẫu quan hệ ngữ nghĩa. 4.1. Thực nghiệm với phân lớp câu hỏi sử dụng học máy thống kê 4.1.1. Dữ liệu và công cụ cho thực nghiệm Dựa theo các kết quả nghiên cứu về phân lớp câu hỏi được trình bày trong III, chúng tôi xây dựng bộ phân lớp sử dụng học máy thống kê cho hệ thống hỏi đáp trên miền mở theo các nội dụng sau: ™ Taxonomy câu hỏi: Sử dụng taxonomy của Li và Roth (đã trình bày trong phần 2.4.2) bao gồm 6 lớp cha: ABBREVIATION (viết tắt), ENTITY (thực thể), DESCRIPTION (mô tả), HUMAN (con người), LOCATION (địa điểm) và NUMERIC VALUE (giá trị số) và 50 lớp con. Tập taxonomy câu hỏi theo loại ngữ nghĩa của câu trả lời này được xem là có khả năng bao phủ hầu hết các trường hợp về ngữ nghĩa của câu trả lời. ™ Dữ liệu: Sử dụng tập 5500 câu hỏi tiếng Anh đã được công bố bởi UIUC1 (bộ dữ liệu đã được gán nhãn chuẩn), chúng tôi tiến hành dịch sang tiếng Việt. Quá trình dịch được tiến hành theo tiêu chí: hiểu nghĩa và phân lớp của câu tiếng Anh, từ đó đặt câu hỏi với nội dung tương tự trong tiếng Việt theo văn phong tự nhiên của người Việt, đảm bảo rằng không có sự gượng ép hay ảnh hưởng của tiếng Anh, số lượng người làm dữ liệu câu hỏi là 5, đảm bảo tính đa dạng trong văn phong tiếng Việt. Số lượng câu hỏi đã dịch được là 1684 với phân phối trên từng lớp được trình bày chi tiết trong bảng 3: 1 48 Bảng 3. Số lượng câu hỏi theo từng lớp cha Lớp cha Số câu hỏi HUMAN 344 NUMERIC VALUE 313 LOCATION 278 ENTITY 317 DESCRIPTION 393 ABBREVIATION 39 ™ Thuật toán áp dụng: Sử dụng Support Vector Machine và Maximun Entropy Model (hai thuật toán được áp dụng nhiều trong phân lớp câu hỏi tiếng Anh) ™ Công cụ: o Trong thực nghiêm với SVM, khóa luận sử dụng SVMmulticlass - Multi-Class Support Vector Machine của tác giả Thorsten Joachims [22, 23]. o Với thuật toán Entropy cực đại, khóa luận sử dụng thư viện của tác giả Phan Xuân Hiếu [16]. o Module xử lý dữ liệu: Khử nhiễu câu hỏi, trích chọn các đặc trưng từ câu hỏi (phần này do tác giả tự viết). ™ Trích chọn đặc trưng: Chúng tôi tiến hành thử nghiệm và đánh giá ảnh hưởng của các đặc trưng khác nhau của câu hỏi tới việc phân lớp. o Đặc trưng đầu tiên được sử dụng là bag-of-unigram và bag-of-word. Để sử dụng bag-of-word, chúng tôi sử dụng công cụ tách từ tiếng Việt JVnTextPro [37]. o Chúng tôi đề xuất đưa thêm đặc trưng từ để hỏi. Trong tiếng Việt, nhiều khi chỉ cần dựa trên các từ để hỏi như ở đâu, khi nào, ai,.. là có thể xác định được câu hỏi thuộc loại nào. Vì vậy chúng tôi sử dụng một danh sách các từ để hỏi trong tiếng Việt (xem bảng 7) làm đặc trưng cho phân lớp câu hỏi. 49 4.1.2. Kết quả bộ phân lớp sử dụng SVM và MEM Do số lượng câu hỏi gán nhãn còn hạn chế nên ban đầu chúng tôi mới chỉ tiến hành thực nghiệm xây dựng bộ phân lớp cho 6 lớp cha. 4.1.2.1. Với MEM Kết quả thu được khá khả quan, đạt độ chính xác cao nhất là 81.14 % khi sử dụng đặc trưng là bag-of-word có sử dụng tách từ. Kết quả chi tiết cho từng lớp được liệt kê trong Bảng 4 và Bảng 5. Bảng 4. Kết quả bộ phân lớp MEM khi sử dụng unigram Class human model match Pre Rec F1 ENTY 112 104 71 68.27 63.39 65.74 DESC 127 133 107 80.45 84.25 82.31 ABBR 10 11 8 72.73 80.00 76.19 HUM 131 132 112 84.85 85.50 85.17 NUM 97 101 90 89.11 92.78 90.91 LOC 85 81 66 81.48 77.65 79.52 Avg.1 79.48 80.60 80.03 Avg.2 562 562 454 80.78 80.78 80.78 Bảng 5. Kết quả bộ phân lớp MEM khi sử dụng tách từ class human model match Pre Rec F1 ENTY 112 109 72 66.06 64.29 65.16 DESC 127 137 107 78.10 84.25 81.06 ABBR 10 8 7 87.50 70.00 77.78 HUM 131 116 104 89.66 79.39 84.21 NUM 97 104 92 88.46 94.85 91.54 LOC 85 88 74 84.09 87.06 85.55 Avg.1 82.31 79.97 81.12 Avg.2 562 562 456 81.14 81.14 81.14 50 4.1.2.2. Với SVM Thiết lập tham số: Sau khi thử nghiệm với nhiều giá trị khác nhau, chúng tôi đặt giá trị c = 10000 (c là tham số trade off giữa tỉ lệ sai của dữ liệu học và kích thước biên của bộ phân lớp SVM).Kết quả tốt nhất với SVM khi sử dụng đặc trưng unigram kết hợp từ để hỏi với độ chính xác là 81.49%. Kết quả chi tiết được liệt kê trong Bảng 6. Bảng 6. Kết quả bộ phân lớp SVM sử dụng các đặc trưng khác nhau Đặc trưng Độ chính xác Tỉ lệ lỗi Unigram 80.78% 108/562 = 19.22% Tách từ 79.72% 121/562 = 20.28% Unigram + từ hỏi 81.49% 104/562 = 18.51% Tách từ + từ hỏi 80.60% 109/562 = 19.40% Bảng 7. Danh sách các từ hỏi tại sao thế nào định nghĩa ra sao có cách nào cái gì vì sao bằng cách nào là gì làm sao chỗ nào gì nghĩ sao nơi nào ở đâu thì sao lúc nào đi đâu thấy sao lý do nào nơi đâu sao nguyên nhân nào từ đâu bao nhiêu khi nào đâu bao giờ thời gian nào có phải bao người nào là ai có mấy nào ai mấy nguyên nhân thật không như thế nào lý do phải không 51 Nhận xét: - Hai thuật toán SVM và MEM có kết quả xấp xỉ nhau trong phân lớp câu hỏi tiếng Việt. Kết quả tốt nhất với SVM là 81.49% và với MEM là 81.14%. - Đặc trưng từ để hỏi có tác dụng nâng cao độ chính xác của phân lớp câu hỏi. Khi áp dụng với SVM, đặc trưng từ để hỏi giúp tăng độ chính xác 0.71% và 0.88% tương ứng khi kết hợp với đặc trưng unigram và tách từ. Độ tăng này không lớn có thể được giải thích như sau: Trong các đặc trưng bag-of-unigram và bag-of-word cũng đã xét đến các từ hỏi này với vai trò giống với các từ khác trong câu hỏi. Việc xuất hiện các từ hỏi này với tần suất lớn theo từng loại câu hỏi khác nhau cũng đã giúp SVM ngầm nhận diện được các từ này là từ quan trọng trong phân lớp. - Ảnh hưởng của tách từ trong phân lớp câu hỏi: Với MEM, tách từ giúp tăng độ chính xác của phân lớp, trong khi với SVM đặc trưng tách từ lại không tốt bằng việc dùng unigram. Có thể giải thích như sau: theo nguyên lý cực đại Entropy, mô hình tự tìm ra trong dữ liệu (tập câu hỏi mẫu) những ràng buộc và đặc trưng riêng cho từng phân lớp. Với SVM, dữ liệu được biểu diễn dưới dạng các điểm trong không gian đặc trưng, SVM cố gắng tìm ra các siêu phẳng ngăn cách dữ liệu của từng lớp câu hỏi. Việc tách từ có thể đã ảnh hưởng tích cực với việc tìm các ràng buộc của mô hình MEM, trong khi lại ảnh hưởng tiêu cực đến sự phân bố dữ liệu trong không gian, dẫn đến siêu phẳng phân cách các lớp không tốt như siêu phẳng tìm được khi dùng unigram. 4.2. Thực nghiệm với xác định loại câu hỏi sử dụng mẫu quan hệ 4.2.1. Mô hình thực nghiệm phân tích câu hỏi sử dụng mẫu quan hệ Trong [6], chúng tôi xây dựng một hệ thống hỏi đáp dựa trên việc trích rút các mẫu quan hệ ngữ nghĩa, áp dụng cho lĩnh vực du lịch. Mục tiêu của hệ thống là trả lời các câu hỏi dạng đơn giản, liên quan đến quan hệ ngữ nghĩa hai ngôi, ví dụ như “Hội lim tổ chức ở đâu?” (quan hệ LỄ HỘI – tổ chức ở - ĐỊA ĐIỂM), “Hà tây có chùa gì ?” (quan hệ CHÙA- ở - ĐỊA ĐIỂM),…. Dựa vào việc khảo sát dữ liệu thực tế, chúng tôi liệt kê 85 mối quan hệ được quan tâm nhiều nhất trong ngành du lịch, ví dụ: lễ hội – địa điểm, bãi biển – địa điểm, đặc sản – địa điểm, núi – chiều cao,… Bước đầu chúng tôi tiến hành thực nghiệm trên 10 mối quan hệ. Mô hình của hệ thống được mô tả trong hình 11. 52 Hình 11. Mô hình hệ thống hỏi đáp tiếng Việt sử dụng trích xuất mẫu quan hệ Hệ thống gồm hai pha chính: Trích rút mẫu tổng quát và sinh seed mới: Pha này được tiến hành offline, mục đích là tạo ra cơ sở dữ liệu về mẫu và seed phục vụ cho pha phân tích câu hỏi và trích xuất câu trả lời sau này. Phương pháp được sử dụng là Snowball kết hợp với việc sử dụng máy tìm kiếm Google để khai thác thông tin sẵn có trên Internet (xem chi tiết trong [6]) Pha phân tích câu hỏi và trích xuất câu trả lời (Hình 12): Pha này sử dụng cơ sở dữ liệu mẫu và seed được sinh ra trong pha trước để phân tích câu hỏi và trích xuất câu trả lời. Bước phân tích câu hỏi có nhiệm vụ xác định tên thực thể và quan hệ mà câu hỏi đang hướng tới. Bước trích xuất câu trả lời chỉ đơn giản là truy vấn cơ sở dữ liệu (dựa trên đầu ra của bước phân tích câu hỏi). Câu hỏi Câu trả lời Phân tích câu hỏi và trích xuất câu trả lời Trích xuất mẫu tổng quát và seed Data 53 Hình 12. Mô hình xử lý cho pha phân tích câu hỏi và trích xuất câu trả lời Pha phân tích câu hỏi bao gồm các bước chính sau đây: Ví dụ với câu hỏi: Nam Định có những bãi biển gì? Bước 1: Nhận dạng thực thể trong câu hỏi dựa trên cơ sở dữ liệu. Sử dụng phương pháp so khớp tất cả các chuỗi con của câu hỏi với các thành phần trong tập seed (tập dữ liệu quan hệ) để tìm ra tập S các seed có chứa thực thể của câu hỏi. Dựa vào các seed này, xác định tập R các quan hệ tương ứng và tập P các mẫu trả lời tiềm năng. Ví dụ với câu hỏi trên, thực thể nhận dạng được là Nam Định với nhãn TỈNH- THANH PHỐ. Từ đó hệ thống xác định được một tập seed S có chứa một thành phần là Nam Định (Bảng 8). Bảng 8. Tập seed tìm được cùng với mối quan hệ tương ứng Mối quan hệ Thành phần thứ nhất của seed Thành phần thứ hai của seed Bãi biển – Địa điểm Quất Lâm Nam Định Bãi biển – Địa điểm Hải Thịnh Nam Định Lễ hội – Địa điểm Hội phủ giầy Nam Định Câu trả lời Câu hỏi Phân tích câu hỏi Trích rút câu trả lời Cơ sở dữ liệu mẫu và seed Tên thực thể và quan hệ 54 Tập các mối quan hệ có thể là {Bãi biển-Địa điểm, Lễ hội-Địa điểm} (Bảng 9). Bảng 9. Tập quan hệ cùng các mẫu tương ứng Mối quan hệ Mẫu tổng quát Bãi biển – Địa điểm bãi_biển thuộc Bãi biển – Địa điểm có bãi_biển Bãi biển – Địa điểm … Lễ hội – Địa điểm khai_mạc tại Lễ hội – Địa điểm Hằng năm tổ_chức lễ_hội Lễ hội – Địa điểm … … …. Bước 2: Biểu diễn câu hỏi (đã loại bỏ từ dừng và tách từ bằng công cụ JVnTextPro) dưới dạng vector từ có trọng số. Vector câu hỏi có dạng: Bước 3: Tính độ tương đồng giữa vector câu hỏi với các mẫu tiềm năng trong P sử dụng độ đo Cosin. Chọn mẫu p có độ tương đồng Simp cao nhất với câu hỏi. Hệ thống sử dụng một ngưỡng µ- độ tương đồng thấp nhất giữa câu hỏi và mẫu. Nếu Simp < µ thì hệ thống không đưa ra câu trả lời (do độ tin cậy quá thấp). Nếu Simp > µ thì quan hệ r mà mẫu p thuộc vào là quan hệ mà câu hỏi đang hướng tới. Độ đo cosin giữa hai vector s1và s2 là: Trong ví dụ trên mẫu có độ tương đồng cao nhất với vector câu hỏi là: có bãi_biển Như vậy, qua ba bước trên, pha phân tích câu hỏi tìm ra được tên thực thể TỈNH-THÀNH PHỐ là Nam Định trong mối quan hệ Lễ hội-Địa điểm. Từ hai thông tin này cũng biết được rằng câu hỏi đang hỏi về Lễ hội. Việc còn lại của pha trích xuất câu trả lời là truy vấn cơ sở dữ liệu để đưa ra các Lễ hội của Nam Định. ||||.|||| . 21 21 ss ssSs = 55 4.2.2. Kết quả phân tích câu hỏi sử dụng mẫu quan hệ Tập dữ liệu test: Chúng tôi xây dựng một bộ câu hỏi gồm 1000 câu hỏi đơn giản liên quan đến 10 mối quan hệ được chọn (Bảng 10). Bảng 10. Các quan hệ được thực nghiệm trong hệ thống Lễ hội-địa điểm Nhà hàng – địa điểm Bãi biển – địa điểm Khách sạn – địa điểm Chùa chiền – địa điểm Siêu thị - địa điểm Sông – địa điểm Công viên – địa điểm Quán cafe – địa điểm Chợ - địa điểm Công cụ phần mềm (Bảng 11): Bảng 11. Các công cụ sử dụng Java SE JDK 6 eclipse-SDK-3.4.1-win32 MySql 5.0 JvnTextPro [37] 56 Các thành phần chính trong hệ thống (Bảng 12): Bảng 12. Các thành phần chính của hệ thống Q&A trên miền du lịch Tên package, class Chức năng package vqa.Datalayer.dao Kết nối với cơ sở dữ liệu MySql package vqa.Datalayer.data Cài đặt các lớp RefinedPattern, RoughPattern, Seed,… là thành phần chính trong việc trích rút mẫu và seed package vqa.util Các hàm tiện ích package vqa. SearchEngineIE Thu thập dữ liệu cho việc tạo mẫu và seed thông qua Google package vqa. CharsetDetector Phát hiện và sửa lỗi font chữ các tài liệu được lấy về từ Google class PatternGenerator và SeedGenerator Thực hiện quá trình sinh mẫu và seed mới class QuestionProcessor Phân tích câu hỏi và đưa ra câu trả lời Lựa chọn ngưỡng µ-độ tương đồng thấp nhất: Hệ thống sử dụng một ngưỡng µ về độ tương đồng thấp nhất giữa câu hỏi và mẫu. Hệ thống chỉ đưa ra câu trả lời khi độ tương đồng giữa câu hỏi và mẫu vượt qua ngưỡng µ. Khi lựa chọn giá trị của µ cần cân nhắc đến sự cân bằng giữa khả năng trả lời câu hỏi chính xác nhất và khả năng trả lời được nhiều câu hỏi nhất. Nếu µ càng lớn, thì độ tương đồng giữa câu hỏi và mẫu càng cao do đó độ chính xác sẽ tăng, trong khi đó số lượng câu trả hỏi trả lời được sẽ giảm. Bảng 13 thể hiện độ tương quan giữa độ chính xác và khả năng trả lời phụ thuộc vào ngưỡng µ. Bảng 13. Kết quả phân tích câu hỏi trong hệ thống hỏi đáp trên miền du lịch µ Độ chính xác Khả năng đưa ra câu trả lời 0.4 85.5% 95,3% 0.5 89,7 % 91,4% 0.6 92,6% 80,3% 57 Kết quả đạt được khá tốt khi chọn µ = 0.5, độ chính xác là 89.7% và khả năng trả lời là 91,4%. Nhận xét: Một hệ thống hỏi đáp tốt là hệ thống có khả năng đưa ra câu trả lời chính xác nhất và có thể trả lời được nhiều câu hỏi nhất. Theo thực nghiệm chúng tôi nhận thấy, độ chính xác (số lượng câu trả lời đúng trên số câu trả lời hệ thống đưa ra) và khả năng đưa ra câu trả lời (số lượng câu trả lời trên tổng số câu hỏi đưa vào) của hệ thống có quan hệ tỉ lệ nghịch với nhau. Chúng tôi chọn giá trị của µ = 0.5 để đảm bảo độ cân bằng giữa 2 tính chất này của hệ thống. Hệ thống hoạt động khá tốt với các câu hỏi đơn giản hỏi về quan hệ ngữ nghĩa hai ngôi xung quanh các quan hệ được quan tâm, đưa ra câu trả lời có độ tin cậy cao. Việc học ra các mẫu tốt, chính xác, thể hiện được đặc trưng của từng quan hệ là rất quan trọng, ảnh hưởng lớn đến độ chính xác của hệ thống. Chúng tôi đánh giá hệ thống có khả năng mở rộng dễ dàng. Chỉ cần làm tay một số seed ban đầu cho các quan hệ quan tâm là hệ thống có thể tự học ra các mẫu để trả lời cho câu hỏi liên quan. Tuy nhiên hạn chế của hệ thống là chỉ trả lời được các câu hỏi liên quan đến các quan hệ có trong hệ thống. Để đáp ứng nhu cầu thực sự của người dùng, hệ thống cần phải mở rộng thêm nhiều quan hệ khác. 58 Kết luận Hệ thống hỏi đáp tự động đang nhận được sự quan tâm đặc biệt của các nhà nghiên cứu và doanh nghiệp trong ngành công nghệ thông tin. Nhu cầu về một hệ thống hỏi đáp tiếng Việt là rất lớn. Phân tích câu hỏi có vai trò đặc biệt quan trọng trong hệ thống hỏi đáp tự động. Khóa luận khảo sát các phương pháp phân tích câu hỏi đang được quan tâm, phân tích và tìm ra phương pháp phù hợp cho phân tích câu hỏi tiếng Việt. Khóa luận này đã đạt được những kết quả sau: • Trình bày một cách khái quát nhất về hệ thống hỏi đáp tự động và nêu lên ý nghĩa, vai trò của pha phân tích câu hỏi trong hệ thống hỏi đáp. • Khảo sát, nghiên cứu các vấn đề xung quanh việc phân tích câu hỏi và trình bày các phương pháp hiện đang được quan tâm trong phân tích câu hỏi. Khóa luận chỉ ra việc phân lớp câu hỏi theo loại ngữ nghĩa của câu trả lời là đặc biệt quan trọng với hệ thống hỏi đáp tự động. • Xây dựng bộ phân lớp câu hỏi cho hệ thống hỏi đáp tiếng Việt trên miền mở sử dụng hai thuật toán SVM và MEM đạt độ chính xác khá cao. • Xây dựng module phân tích câu hỏi cho hệ thống hỏi đáp tiếng Việt trên miền du lịch dựa vào trích rút mẫu quan hệ Bên cạnh đó, khóa luận còn một số hạn chế: • Khóa luận mong muốn xây dựng được bộ phân lớp hai cấp với 6 lớp cha và 50 lớp con, tuy nhiên do số lượng câu hỏi gán nhãn được còn ít nên mới chỉ phân lớp được cho 6 lớp cha. Độ chính xác của bộ phân lớp chưa thực sự cao. • Hệ thống hỏi đáp tiếng Việt cho miền du lịch còn hạn chế về số lượng các quan hệ. Các hướng nghiên cứu và phát triển tiếp theo là: Với phần phân tích câu hỏi cho hệ thống hỏi đáp miền mở. • Thu thập và gán nhãn thêm dữ liệu câu hỏi. Mỗi lớp câu hỏi cần trung bình 100 câu hỏi mẫu, do đó để có thể tiến hành phân lớp cho 50 lớp con khóa luận cần tiếp tục thu thập dữ liệu (cần khoảng 5000 câu hỏi). 59 • Đưa thêm các đặc trưng ngữ nghĩa nhằm nâng cao độ chính xác cho bộ phân lớp câu hỏi. • Tiến hành thực nghiệm với nhiều thuật toán học khác để tìm ra thuật toán phù hợp nhất với phân lớp câu hỏi tiếng Việt. Có thể áp dụng phương pháp học bán giám sát để tận dụng nguồn câu hỏi chưa gán nhãn. • Thực nghiệm phần tạo truy vấn mở rộng cho hệ thống trích chọn thông tin. Với phần phân tích câu hỏi cho hệ thống hỏi đáp tiếng Việt cho miền du lịch • Tiến hành sinh mẫu và seed cho nhiều quan hệ khác và tích hợp vào hệ thống để đánh giá độ chính xác của phân tích câu hỏi khi số quan hệ tăng lên. Đồng thời hoàn thiện hệ thống để có thể đáp ứng nhu cầu thực tế của người dùng. 60 Tài liệu tham khảo Tài liệu tiếng Việt [1] Hồ Tú Bảo, Lương Chi Mai. Về xử lý tiếng Việt trong công nghệ thông tin. Viện Công nghệ Thông tin, Viện Khoa học và Công nghệ Tiên tiến Nhật bản. [2] Nguyễn Thị Hương Thảo. Phân lớp phân cấp Taxonomy văn bản Web và ứng dụng. Khóa luận tốt nghiệp đại học, Đại học Công nghệ, 2006. [3] Hà Quang Thụy & nhóm khai phá dữ liệu và ứng dụng. Bài giảng về khai phá dữ liệu. 2007. [4] Nguyễn Minh Tuấn. Phân lớp câu hỏi hướng tới tìm kiếm ngữ nghĩa tiếng việt trong lĩnh vực y tế. Khóa luận tốt nghiệp đại học, Đại học Công nghệ, 2008. [5] Nguyễn Cẩm Tú. Máy Vector Hỗ trợ (SVMs) và các Phương pháp Nhân.2007 [6] Phạm Thu Uyên, Nguyễn Đức Vinh, Nguyễn Đạo Thái. Hệ thống hỏi đáp tự động sử dụng trích rút quan hệ ngữ nghĩa trong kho văn bản tiếng Việt. Nghiên cứu khoa học sinh viên cấp trường Đại học Công Nghệ, 2009 Tài liệu tiếng Anh [7] Eugene Agichtein, Luis Gravano. Snowball: Extracting Relations from Large Plain-Text Collections. In Proceedings of the Fifth ACM International Conference on Digital Libraries, 2000. [8] Michele Banko, Eric Brill, Susan Dumais, Jimmy Lin. AskMSR: Question Answering Using the Worldwide Web. Microsoft Research. In Preceedings of 2002 AAAI Spring Symposium on Mining Answers from Texts and Knowledge bases, Palo Alto, California, March 2002. [9] Matthew W. Bilotti, Boris Katz, and Jimmy Lin. What Works Better for Question Answering: Stemming or Morphological Query Expansion? ACM SIGIR'04 Workshop Information Retrieval for QA, (Jul. 2004). [10] John Burger, Claire Cardie, Vinay Chaudhri, Robert Gaizauskas, Sanda Harabagiu, David Israel, Christian Jacquemin, Chin-Yew Lin, Steve Maiorano, 61 George Miller, Dan Moldovan , Bill Ogden, John Prager, Ellen Riloff, Amit Singhal, Rohini Shrihari, Tomek Strzalkowski, Ellen Voorhees, Ralph Weishedel. Issues, Tasks and Program Structures to Roadmap Research in Question & Answering (Q&A) 2002. [11] Sergey Brin (Computer Science Department, Stanford University). Extracting Patterns and Relations from the World Wide Web. In WebDB Workshop at 6th International Conference on Extending Database Technology, EDBT’98, 1998. [12] Eric Brill, Jimmy Lin, Michele Banko, Susan Dumais and Andrew Ng (Microsoft Research One Microsoft Way Redmond). Data-Intensive Question Answering . In Proceedings of the Tenth Text REtrieval Conference (TREC 2001), 2001. [13] Jaime Carbonell, Donna Harman , Eduard Hovy, and Steve Maiorano, John Prange and Karen Sparck-Jones. Vision Statement to Guide Research in Question & Answering (Q&A) and Text Summarization. Final version 1. 2000. [14] Kadri Hacioglu, Wayne Ward. 2003. Question Classification with Support Vector Machines and Error Correcting Codes. The Association for Computational Linguistics on Human Language Technology, vol. 2, tr.28–30. [15] Sanda M. Harabagiu, Marius A. Paşca, Steven J. Maiorano. Experiments with open-domain textual Question Answering. International Conference On Computational Linguistics Proceedings of the 18th conference on Computational linguistics - Volume 1, 2000, tr. 292 - 298 [16] Phan Xuan Hieu. JTextPro: A Java-based Text Processing Toolkit. jtextpro.sourceforge.net/ [17] Wesley Hildebr, Boris Katz, Jimmy Lin. Answering Definition Questions Using Web Knowledge Bases. Book: Natural Language Processing – IJCNLP, 2005. [18] Eduard Hovy, Ulf Hermjakob and Lin, C.-Y. The Use of External Knowledge in Factoid QA. Paper presented at the Tenth Text REtrieval Conference (TREC 10), Gaithersburg, MD, 2001, November 13-16. [19] Eduard Hovy, Ulf Hermjakob, and DeepakRavichandran. A Question/Answer Typology with Surface Text Patterns. In Proceedings of the second international conference on Human Language Technology Research. 2002 62 [20] Zhiheng Huang, Marcus Thint, Zengchang Qin. Question Classification using Head Words and their Hypernyms. ACL 2008. [21] Thorsten Joachims. Text Categorization with Support Vector Machines: Learning with Many Relevant Features. Proceedings of ECML-98, the 10th European Conference on Machine Learning, 1998, tr 137-142. [22] Thorsten Joachims. Learning to Classify Text using Support Vector Machines. Kluwer. 2002 [23] Thorsten Joachims. SVM multiclass Multi-Class Support Vector Machine. Cornell University Department of Computer Science. [24] Vijay Krishnan and Sujatha Das and Soumen Chakrabarti. Enhanced Answer Type Inference from Questions using Sequential Models. The conference on Human Language Technology and Empirical Methods in Natural Language Processing, 2005. [25] Xin Li, Dan Roth. Learning Question Classifiers. COLING'02, Aug, 2002. [26] Xin Li, Dan Roth. Learning question classifiers: the role of semantic information. Natural Language Engineering, Volume 12 , Issue 3 , September 2006, tr. 229 – 249. [27] Bernardo Magnini. Open Domain Question Answering: Techniques, Resources and Systems. RANLP 2005. [28] George A. Miller, Richard Beckwith, Christiane Fellbaum,Derek Gross, and Katherine Miller. Introduction to WordNet: An On-line Lexical Database. 1998. [29] Dan Moldovan, Sanda Harabagiu, Marius Pasca, Rada Mihalcea, Richard Goodrum, Roxana Girju and Vasile Rus. The Structure and Performance of an Open- Domain Question Answering System. In Proceedings of the 38th Annual Meeting of the Association for Comoutational Linguistics (ACL-2000), 2000. [30] N.F. Noy and McGuinness, D.L. Ontology Development 101: A Guide to Creating Your First Ontology SMI. Technical report SMI-2001-0880 , Stanford University, 2001. [31] Robinson, W. P., Rackstraw, S. J. A Question of Answers (Vol. I). Boston: Routledge & Kegan Paul. 1972. 63 [32] Robinson, W. P., Rackstraw, S. J. A Question of Answers (Vol. II). Boston: Routledge & Kegan Paul, 1972. [33] E. Saquete, P. Martınez-Barco, R. Mu˜noz, J.L. Vicedo. Splitting Complex Temporal Questions for Question Answering Systems. ACL 2004 [34] Luís Sarmento, Jorge Filipe Teixeira, Eugénio Oliveira. Experiments with Query Expansion in the RAPOSA (FOX) Question Answering System. In The Cross- Language Evaluation Forum (CLEF), 2008. [35] Mihai Surdeanu. Question Answering Techniques and Systems. TALP Research Center Dep. Llenguatges i Sistemes Informàtics Universitat Politècnica de Catalunya. [36] Nguyen Tri Thanh. Study on Acquiring and Using Linguistic Semantic Information for Search System. Doctor thesis, Japan Advanced Institute of Science anf Technology, 2008. [37] Nguyen Cam Tu. JVnTextpro: A Java-based Vietnamese Text Processing Toolkit. SISLab Software Utility. College of Technology, Vietnam National University, Hanoi. [38] Ellen M. Voorhees. The TREC-8 Question Answering Track Report. Paper presented at the Eighth Text REtrieval Conference (TREC 8) Gaithersburg, MD, 1999 November 16-19. [39] Hui Yang and Tat-Seng Chua.The Integration of Lexical Knowledge and External Resources for Question Answering. School of Computing, National University of Singapore. [40] Liu Yi, Zheng Y F. One-against-all multi-Class SVM classification using reliability measures. Proceedings of the 2005 International Joint Conference on Neural Networks Montreal,Canada, 2005. [41] Dell Zhang, Wee Sun Lee. Question Classification using Support Vector Machines. The ACM SIGIR conference in informaion retrieval, 2003, tr 26–32.