Đề tài 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ế

hiện quan hệ cú pháp của các yếu tố trong câu, nhờ đó nhằm đưa ra nội dung muốn thông báo. Trên văn bản, ngữ điệu thường được biểu hiện bằng dấu câu. Sự khác nhau trong nội dung thông báo được nhận biệt khi so sánh hai câu sau: - Đêm hôm qua, cầu gãy. - Đêm hôm, qua cầu gãy. Qua một số đặc điểm nổi bật vừa nêu trên đây, chúng ta có thể hình dung được phần nào bản sắc và tiềm năng của tiếng Việt 2.3. Tìm kiếm ngữ nghĩa trong lĩnh vực y tế Trong phần này, khóa luận sẽ trình bày những bước đầu của việc xây dựng một máy tìm kiếm ngữ nghĩa trên lĩnh vực Y tế cho tiếng Việt. 2.3.1. Ontology Y tế trong tiếng Việt Với các dữ liệu về y tế thu thập được từ các trang Web và Ontology BioCaster [1], tiến hành liệt kê các thuật ngữ (term) quan trọng nhằm có thể nêu định nghĩa cho người dùng với hướng nghiên cứu tiếp theo là tự động liên kết đến các định nghĩa có sẵn trên 17 trang wikipedia. Từ các thuật ngữ trên, sẽ định nghĩa các thuộc tính của chúng. Việc xây dựng Ontology là một quá trình lặp lại được bắt đầu bằng việc định nghĩa các khái niệm trong hệ thống lớp và mô tả thuộc tính của các khái niệm đó. Qua khảo sát Ontology BioCaster với các thuật ngữ trong tiếng Việt, cùng với một số luợng lớn các trang Web về y tế hiện nay ở Việt Nam, chúng tôi đã xây dựng nên một tập các thuật ngữ, các mối quan hệ cơ bản nhất để từ đó để xuất ra Ontology thử nghiệm ban đầu, với những khái niệm cơ bản sau: - Thuốc: bao gồm hai loại Đông y và Tây y. Ví dụ, thuốc 5-Fluorouracil Ebewe chống ung thư (ung thư đại trực tràng, vú, thực quản, dạ dày), hay là thuốc Ciloxan sát trùng, chống nhiễm khuẩn ở mắt. Thuốc đông y ngũ gia bì chữa bệnh phong thấp, tráng gân cốt … - Bệnh, hội chứng: Các loại bệnh như cúm gà, viêm loét dạ dày, các hội chứng mất ngủ, suy tim … - Triệu chứng : Ví dụ như triệu chứng của cúm H5N1 là sốt cao, nhức đầu, đau mỏi toàn thân,... - Nguyên nhân: Tác nhân (virut, vi khuẩn..muỗi, gà, chim..), và các nguyên khác như là thiếu ngủ, lười tập thể dục, hút thuốc lá thụ động … - Thực phẩm: Bao gồm các món ăn có lợi hoặc gây hại cho sức khỏe con nguời cũng như phù hợp với một số loại bệnh nào đó. - Người: Bao gồm bác sỹ, giáo sư mà người bệnh có thể tìm kiếm để khám bênh, xin giúp đỡ khi mắc bệnh. - Tổ chức: Bệnh viện, phòng khám, hiệu thuốc … là các địa điểm để bệnh nhân có thể tìm đến khi mắc bệnh. - Địa điểm: Địa chỉ của một tổ chức nào đó mà bệnh nhân có thể tìm đến, các nơi dịch đang phát sinh và lan rộng. - Cơ thể người: Là tất cả các bộ phận cơ thể người có thể thể bị nhiễm bệnh: mắt, mũi, gan, tim … - Hoạt động: Chẩn trị, xét nghiệm, hồi cứu, hô hấp nhân tạo, phòng tránh, tiêm phòng ... - Hóa chất: Vitamin, khoáng chất …gây tác động xấu, tốt đến cơ thể con người, ví dụ vitamin A có lợi cho mắt, Vitamin C, E làm giảm các nguy cơ bệnh tim… Giữa các khái niệm cơ bản trên có các mỗi quan hệ như sau: - Sự tương tác thuốc – thuốc : Thuốc này có thể gây tác dụng phụ cho thuốc kia, hay có thể kết hợp các loại thuốc với nhau để chữa bệnh. Ví dụ thuốc chống ung 18 thư Alexan không nên dùng chung với methotrexate hay 5-fluorouracil - Thực phẩm tác động xấu, tốt đến bệnh, cơ thể người: Ví dụ như uống xôđa nhiêu có rủi ro mắc các bệnh rối loạn trao đổi chất, tăng vòng bụng, tăng huyết áp… - Quan hệ bệnh – thuốc: () - Quan hệ nguyên nhân gây ra bệnh, hay bệnh có nguyên nhân: () - Quan hệ bệnh – triệu chứng: () - Quan hệ bệnh biến chứng thành bệnh khác: - Các hoạt động tác động lên bệnh: - Bệnh được phát hiện, chữa trị ở tổ chức: - Người làm việc trong một tổ chức tại địa điểm nào đó: Ví dụ minh họa thể hiện Mô hình của Ontology Y tế này ở hình 2. 2.3.2. Bộ phân lớp câu hỏi Y tế trong tiếng Việt Với Ontology Y tế giới thiệu ở phần trên, để giải quyết được hai bài toán mang đặc trưng của tiếng Việt cần xây dựng một bộ phân lớp câu hỏi Y tế trong tiếng Việt. Bộ phân lớp câu hỏi này là bộ phân lớp nội miền (trong miền Ontology Y tế), tức là với các câu hỏi/truy vấn của người dùng đưa vào, bộ phân lớp phải xác định chúng thuộc về các khái niệm nào. Chương 3 sẽ cụ thể hóa các phương pháp phân lớp câu hỏi. 19 Chương 3. Các phương pháp phân lớp câu hỏi 3.1. Giới thiệu về phân lớp câu hỏi. Trong hầu hết các hệ thống tìm kiếm ngữ nghĩa, bước đầu tiên là xử lý câu hỏi nhằm xác định câu hỏi đó hỏi về cái gì? Phân chia truy vấn của người dùng ra thành một số lớp định nghĩa trước như hỏi địa điểm (ở đâu ?), thời gian (khi nào ?)… Thông thường ở phần lớn các trường hợp để xác định được điều này, hệ thống thường sử dụng một số thông tin hay đặc trưng của câu hỏi để xác định kiểu của câu trả lời. Ví dụ với câu hỏi “ai là người phát hiện ra vacxin phòng bệnh dại?” thì mục đích của câu hỏi là muốn tìm hiểu thông tin về một người. Hệ thống cần xác định được kiểu của câu trả lời (trong ví dụ này là thông tin về một người) để có thể trả về thong tin mong muốn cho người dùng. Trong các hệ thống tìm kiếm ngữ nghĩa, đối tượng được tìm kiếm là các thông tin mang ngữ nghĩa, do vậy việc phân lớp câu hỏi còn được gọi là phân lớp ngữ nghĩa cho câu hỏi (semantic question classification) có hai vai trò quan trọng sau đây: (1) Giảm không gian tìm kiếm, chẳng hạn với câu hỏi “thuốc nào chữa bệnh viêm họng?” hệ thống chỉ cần tìm kiếm trên các lớp thuốc của miền Y tế để có câu trả lời, thay vì tìm kiếm trên toàn bộ cơ sở dữ liệu. (2) Nâng cao độ chính xác của câu trả lời. Đối với các hệ thống tìm kiếm ngữ nghĩa lớn tìm kiếm trên nhiều miền Ontology, thường có bộ phân lớp câu hỏi kép gồm : (1) phân lớp để xác định miền Ontology của câu hỏi (phân lớp nội miền) (2) phân lớp để xác định câu hỏi thuộc lĩnh vực nào (lớp nào) trong miền Ontology đã xác định ở phân lớp nội miền. Ngược lại đối với các máy tìm kiếm ngữ nghĩa trên một miền Ontology, chỉ cần xây dựng bộ phân lớp đơn (2). 3.2. Các phương pháp phân lớp câu hỏi Hiện nay, có một số nghiên cứu tập trung vào hướng tiếp cận biểu thức chính qui dựa vào những luật ngữ pháp viết tay (hand-written grammar rulers) để xác định lớp của câu hỏi đầu vào như các tác giả B., Huang, Y., Kupsc, A. và Nyberg, E năm 2003 [35] giới thiệu. Mặc dù hướng tiếp cận này cũng đạt được những thành công đáng kể, nhưng vẫn có những hạn chế mà đã được Li, Roth 2002[19] và Hacioglu, Ward 2003[16] chỉ ra. 20 Cụ thể, các tác giả [14] đã chỉ ra bốn hạn chế của hướng tiếp cận này: (1) Xây dựng mô hình cho phương pháp này rất tốn thời gian và công sức, cần có sự cộng tác của những chuyên gia trong lĩnh vực ngôn ngữ học khi xây dựng các mẫu câu hỏi và văn phạm cho từng loại câu hỏi đó. (2) Các luật ngữ pháp viết tay và văn phạm của từng loại câu hỏi rất cứng nhắc, không linh động. Khi một dạng câu hỏi mới xuất hiện, mô hình theo hướng này không thể xử lý. Muốn xử lý được mô hình cần phải được cung cấp những luật mới. (3) Vấn đề nhập nhằng của các văn phạm ngữ pháp rất khó xử lý, kiểm soát và phụ thuộc vào đặc điểm của từng ngôn ngữ. (4) Khi tập câu trả lời được mở rộng hoặc thay đổi kéo theo việc phải viết lại hoàn toàn các luật trước đó nên hệ thống rất khó mở rộng. Với các hạn chế như trên dẫn đến số lớp của bộ phân lớp theo hướng này là nhỏ (khoảng 8-10 lớp) không thích hợp khi tích hợp vào một hệ thống tìm kiếm ngữ nghĩa có qui mô lớn. Một hướng tiếp cận khác để giải quyết bài toán phân lớp câu hỏi là theo hướng tiếp cận xác suất được Jonathan Brown năm 2004 tổng hợp lại [15], bao gồm hai cách tiếp cận chính đó là: (1) Tiếp cận theo hướng học máy (machine learning) (2) Tiếp cận theo mô hình ngôn ngữ (language modeling) Không giống như hướng tiếp cận biểu thức chính quy (thực hiện việc so sánh mẫu), các phương pháp theo hướng tiếp cận dựa trên xác suất sẽ xây dựng một mô hình phân lớp tự động từ tập dữ liệu học cho trước. Các thuật toán của hướng tiếp cận này sẽ tính toán xác suất phân lớp cho câu hỏi vào dựa trên những đặc trưng hay những mối quan hệ của các từ trong câu hỏi/truy vấn đưa vào. Nhờ đó phương pháp này khắc phục những nhược điểm của hướng tiếp cận biểu thức chính quy [15]. Do vậy, hướng tiếp cận này không những phù hợp với các hệ thống tìm kiếm ngữ nghĩa lớn mà còn phù hợp với các hệ thống nhỏ hơn (do khả năng linh hoạt cao dễ dàng mở rộng tập dữ liệu và số phân lớp). Khóa luận sẽ tập trung trình bày các phương pháp phân lớp câu hỏi dựa trên hướng tiếp cận xác suất để xây dựng bộ phân lớp câu hỏi trong Tiếng Việt. 3.3. Hướng tiếp cận dựa trên xác suất Bên cạnh hướng tiếp cận dựa trên biểu thức chính quy thì hướng tiếp cận dựa trên xác suất cũng là một hướng tiếp cận được nhiều nhà khoa học lựa chọn khi nghiên cứu về phân lớp câu hỏi. Như đã được giới thiệu, hướng tiếp cận dựa trên xác suất bao gồm hai hướng con là hướng học máy và hướng dựa trên mô hình ngôn ngữ [15]. Hướng tiếp cận học máy sử dụng những thuật toán và kỹ thuật cho phép máy tính có thể “học” 1 được. Cụ thể, trong bài toán phân lớp câu hỏi hướng tiếp cận học máy sử dụng các thuật toán như : Support Vector Machines (SVM), láng giềng gần nhất (Nearest 21 Neighbors – kNN), Naïve Bayes (NB)…v.v để học trên tập câu hỏi mẫu đã được gán nhãn từ đó xây dựng mô hình phân lớp câu hỏi. Trong khi đó, tiếp cận dựa trên mô hình ngôn ngữ xây dựng một mô hình ngôn ngữ thống kê có thể ước lượng được phân phối của ngôn ngữ tự nhiên chính xác nhất có thể. Ví dụ, với một xâu S = “Bệnh đau dạ dày chữa ở đâu?” thì mô hình ngôn ngữ cho xâu S chính là xác suất P(S), sao cho xác suất này ánh xạ với tần suất mà xâu S trở được xuất hiện như một câu nói trong ngôn ngữ tự nhiên (ví dụ tiếng Việt). Khi áp dụng phương pháp này cho bài toán phân lớp câu hỏi, tức là xây dựng một mô hình ngôn ngữ cho từng câu hỏi. Mô hình này sẽ cho biết xác suất câu hỏi được phân vào lớp nào là hợp lý nhất (lớn nhất). Cả hai phương pháp trên đều có độ chính xác khác nhau phụ thuộc vào ngôn ngữ áp dụng. Để lựa chọn hướng tiếp cận tốt nhất khi xây dựng bộ phân lớp câu hỏi cho tiếng Việt, phần tiếp theo của khóa luận sẽ trình bày những khảo sát về cả hai hướng tiếp cận trên 3.3.2 Các hướng tiếp cận theo phương pháp học máy Trong hướng tiếp học máy thuật toán được sử dụng chủ yếu để giải quyết bài toán phân lớp câu hỏi là Support Vector Machines (được sử dụng trong các tài liệu [19, 20, 22], ngoài ra các thuật toán khác cũng được sử dụng như Nearest Neighbors (NN), Naïve Bayes (NB), Decision Tree (DT) và Sparse Network of Winnows (SNoW) [42]. Đưới đây trình bày sơ lược về nội dung một số thuật toán học máy. 3.3.1.1 Support Vector Machines (SVM) a. Thuật toán [2] Thuật toán Support Vector Machines (máy vector hỗ trợ) được Corters và Vapnik giới thiệu vào năm 1995. SVM rất hiệu quả để giải quyết các bài toán với dữ liệu có số chiều lớn như các vector biểu diễn văn bản. Thuật toán SVM ban đầu chỉ được thiết kế để giải quyết bài toán phân lớp nhị phân tức là số lớp hạn chế là hai lớp. Hiện nay, SVM được đánh giá là bộ phân lớp chính xác nhất cho bài toán phân lớp văn bản [31] bởi vì đó là bộ phân lớp tốc độ rất nhanh và hiệu quả đối với bài toán phân lớp văn bản. Cho tập dữ liệu học D ={(xi, yi), i = 1,…, n} với xi ∈ Rm và yi∈{0,1} là một số là một số nguyên xác định xi là dữ liệu dương hay âm. Một tài liệu xi được gọi là dữ liệu dương nếu nó thuộc lớp ci ; xi được gọi là dữ liệu âm nếu nó không thuộc lớp ci . Bộ phân lớp tuyến tính được xác định bằng siêu phẳng: {x : f(x) = WT + w0 =0} Trong đó W∈ Rm và w0∈R đóng vai trò là tham số của mô hình. Hàm phân lớp nhị phân h: Rm → {0,1}, có thể thu được bằng cách xác định dấu của f(x): { 0 (x) 1 0 (x) 0 >≤= f f h 22 Học bộ phân lớp của mô hình bao gồm việc xác định w và w0 từ dữ liệu. Với thuật toán này, mỗi dữ liệu được xem là một điểm trong mặt phẳng. Dữ liệu học là tách rời tuyến tính (linearly separable) nếu tồn tại một siêu phẳng sao cho hàm phân lớp phù hợp với tất cả các nhãn; tức là yif(xi)>0 với mọi i = 1,...,n. Với giả thuyết này, Rosenblatt đã đưa ra một thuật toán đơn giản để xác định siêu phẳng : 1. w ←0 2. w0←0 3. repeat 4. e←0 5. for i←1,…,n 6. do s←sign(yi(wTxi +w0) 7. if s<0 8. then w ←w + yixi 9. w0←w0 + yixi 10. e←e+1 11. util e=0 12. return (w,w0) Điều kiện cần để D tách rời tuyến tính là số dữ liệu học n = |D| nhỏ hơn hoặc bằng m+1. Điều này là thường đúng với bài toán phân lớp văn bản, bởi vì số lượng từ mục có thể lên tới hàng nghìn và lớn hơn nhiều lần so với số lượng dữ liệu học. 23 Hình 4. Mối quan hệ giữa các siêu phẳng phân cách Trong Hình 4, giả sử rằng các dữ liệu mẫu thuộc lớp âm và lớp dương đều tuân theo luật phân bố chuẩn Gaussian, và được tạo ra với cùng một xác suất. Khi đó một siêu phẳng phân cách được gọi là lý tưởng nếu nó làm cực tiểu xác suất phân lớp sai cho một điểm dữ liệu mới. Với giả thuyết ở trên thì siêu phẳng phân cách lý tưởng sẽ trực giao với đoạn thẳng nối tâm của hai vùng có mật độ xác suất lớn nhất. Rõ ràng các siêu phẳng được xây dựng nhằm phân cách các điểm dữ liệu mẫu có thể lệch đi rất nhiều so với siêu phẳng lý tưởng, do đó sẽ dẫn tới việc phân lớp không tốt trên dữ liệu mới sau này. Độ phức tạp của quá trình xác định siêu phẳng lý tưởng sẽ tăng theo số chiều của không gian đầu vào m, vì với một số lượng các dữ liệu mẫu cố định, tập hợp các siêu phẳng thực tế 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ừ. 24 Hình 5. Siêu phẳng tối ưu và biên. Theo lý thuyết 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 thoả mãn hai tính chất quan trong (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 [26]. Đị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. 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 || + ≥ = 0 T ww ||w|| 1 + 25 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ểm 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 = ⎡ ⎤= − + α + −⎣ ⎦∑ 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α = − α Λα + α∑ thoả 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 thoả 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 thoả 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 Nếu dữ liệu học không tách rời tuyến tính, thêm biến ξi và thay phương trình trên bằng phương trình: ∑ = + 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 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. 26 b. 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[20]. Ý tưởng cơ bản như sau: - 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 . - Chia tập Y thành m tập 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. c. Áp dụng SVM vào phân lớp câu hỏi Tuy mục tiêu ban đầu của SVM là dùng cho phân lớp nhị phân, nhưng hiện nay đã được cải tiến cho phân lớp đa lớp, phiên bản phân lớp đa lớp này sẽ được sử dụng cho bài toán phân lớp câu hỏi. Hai quá trình chuẩn bị dữ liệu khi xây dựng được mô hình phân lớp câu hỏi dựa trên SVM như sau: (1) Thiết kế mô hình cây phân cấp (taxonomy) cho tập lớp câu hỏi. Miền ứng dụng của câu hỏi sẽ quyết định độ phức tạp (phân cấp) của taxonomy (2) Xây dựng tập dữ liệu mẫu (corpus) đã được gán nhãn cho từng lớp câu hỏi. Trong bước này, cách lựa chọn đặc trưng để biểu diễn câu hỏi có vai trò quan trọng. Phụ thuộc vào đặc điểm của từng ngôn ngữ mà tập các đặc trưng được lựa chọn khác nhau. Ví dụ với tiếng Anh thì tập đặc trưng của nó là các từ. Sau khi xây dựng được tập các lớp câu hỏi cùng với tập dữ liệu sẽ tiến hành “học”: Mô hình học như sau: Hình 6. Sơ đồ phân lớp câu hỏi với SVM Trong Hình 6, bước tiền xử lý thực hiện chức năng làm tinh dữ liệu: loại bỏ từ dừng (stopword) …sau đó câu hỏi được trích trọn các đặc trưng (các đặc trưng được lựa chọn từ trước), dữ liệu đầu vào của bộ phân lớp SVM sẽ là tập các vector đặc trưng. 27 3.3.1.2 Một số phương pháp khác Ngoài SVM và K láng giềng gần nhất, trong bài toán phân lớp câu hỏi một số phương pháp khác được giới thiệu ở [42] như: • Thuật toán Naïve Bayes (NB) [32]là một thuật toán phổ biến trong học máy. Được McCallum [22] và Yang [41] đánh giá là một trong những phương pháp có hiệu năng cao nhất khi thực hiện phân lớp văn bản. Tư tưởng chủ đạo của thuật toán Naïve Bayes là ước lượng các thông số của đa thức sinh cho của thể hiện (văn bản, câu …). Sau đó lựa chọn lớp thích hợp nhất cho từng thể hiện dựa vào các luật Bayes và giả thiết Bayes (giả thiết độc lập - sự xuất hiện của đặc trưng này là tự nhiên, không phụ thuộc vào sự xuất hiện các đặc trưng khác) • Thuật toán cây quyết định (Decision Tree –DT) [32] là phương pháp xấp xỉ giá trị các hàm mục tiêu rời rạc. Trong đó, hàm học của phương pháp này là một cây có bậc tùy ý. Cây quyết định bao gồm các lá và nhánh, mỗi là là đại diện cho một lớp và các nhánh là các điều kiện, đặc trưng dẫn đến lớp ở đỉnh lá. • Thuật toán Mạng lọc thưa (Sparse Network of Winnows -SNoW) [6] được thiết kế để học trên những tập dữ liệu có số lượng đặc trưng lớn. Được sử dụng rộng rãi trong các bài toán phân lớp đa lớp. SNoW là một mạng thưa dùng các hàm tuyến tính là các bộ lọc để cập nhật tập luật. Phương pháp này thích hợp cho học trong miền khi các đặc trưng tiềm năng tạo các quyết định sai khác nhau mà không biết mức độ ưu tiên. • Bộ phân lớp dựa trên thuật toán K người láng giềng gần nhất là một bộ phân lớp dựa trên bộ nhớ, đơn giản vì nó được xây dựng bằng cách lưu trữ tất cả các đối tượng trong tập huấn luyện. Để phân lớp cho một điểm dữ liệu mới x, trước hết bộ phân lớp sẽ tính khoảng cách từ điểm x đến tất cả các điểm dữ liệu trong tập huấn luyện. Qua đó tìm được tập N(x, D, k) gồm k điểm dữ liệu mẫu có khoảng cách đến x là gần nhất. Ví dụ nếu các dữ liệu mẫu được biểu diễn bởi không gian vector thì chúng ta có thể sử dụng khoảng cách Euclian để tính khoảng cách giữa các điểm dữ liệu với nhau. Sau khi xác định được tập N(x, D, k), bộ phân lớp sẽ gán nhãn cho điểm dữ liệu x bằng lớp chiếm đại đa số trong tập N(x, D, k). Mặc dù rất đơn giản, nhưng thuật toán K người láng giềng gần nhất đã cho kết quả tốt trong nhiều ứng dụng thực tế. Để áp dụng thuật toán k-NN vào tài liệu văn bản, chúng ta sử dụng hàm tính trọng số cho mỗi lớp theo biểu thức (1.1) (Trong công thức, ( )kD,x,Nc là tập con chỉ chứa các đối tượng thuộc lớp c của tập): ( ) ( )∑∈= kD,x,Ncx' )x'cos(x,x|cScore (1.1) Khi đó tài liệu x sẽ được phân vào lớp c0 nếu: ( ) ( ){ }Cc,x|cscoreMaxx|cScore 0 ∈= 28 3.3.1.3 Thực nghiệm khi tiến hành phân lớp câu hỏi Với sự phong phú của các thuật toán trong học máy dẫn đến việc phải cân nhắc khi lựa chọn thuật giải nào đại diện cho hướng học máy áp dụng vào bài toán phân lớp câu hỏi trong tiếng Việt. Zhang [42] đã tiến hành thử nghiệm năm thuật toán khác nhau trong hướng học máy khi xây dựng bộ phân lớp câu hỏi. Dựa trên kết thực nghiệm này, sẽ quyết định thuật toán sử dụng trong hướng học máy. Thực nghiệm của Zhang như sau: a. Taxonomy của lớp câu hỏi Lớp cha Các lớp con ABBR Tóm tắt, sự khai triển DESC Định nghĩa, mô tả, lý do ENTY Động vật, cơ thể, màu sắc, sang tác, tiền tệ, ngôn ngữ, chữ viết, loại khác, thực vật, bệnh /thuốc, sự kiện, thực phẩm, ngôn ngữ, công cụ - phương tiện, sản phẩm, tôn giáo, thể thao, vật chất, ký hiệu, kỹ thuật, thuật ngữ, xe cộ, từ. HUM Nhóm, cá thể, tên, tư cách LOC Thành phố, đất nước, núi, bang, loại khác NUM Mã, đếm, ngày, khoảng cách, tiền, thứ tự, khác, phần trăm-tỉ lệ, thời kỳ, tốc độ, nhiệt độ, kích cỡ, cân nặng Bảng 1. Taxonomy của tập lớp câu hỏi thử nghiệm của Zhang Bảng trên mô tả tầng cao nhất của taxonomy câu hỏi, mỗi một lớp thuộc cột “chi tiết” mô tả một loại câu hỏi riêng biệt. b. Tập câu hỏi cho taxonomy trên bao gồm các câu hỏi đã được gán nhãn được cung cấp bởi USC [11], UIUC [42] và TREC [14][13] [12]. Tập dữ liệu này được gán nhãn thủ công. Mỗi một câu hỏi chỉ thuộc một lớp nhất định. Tập đặc trưng lựa chọn bao gồm hai loại đặc trưng: (1) bag-of-words: biểu diễn văn bản/câu hỏi độc lập với ngôn ngữ và ngữ pháp. Mỗi một văn bản/câu hỏi được biểu diễn bẳng một tập các từ, tập từ này không xếp thứ tự. 29 (2) 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-grams là các ký tự liền kề nhau (chuỗi con) bắt đầu từ mẫu tự A. Vì vậy, khoảng cách n-grams trong văn bản ít hơn hoặc bằng |A|n. Đều này cho thấy số chiều của vectơ đặc trưng n- grams có thể rất lớn thậm chí khi n có giá trị vừa phải. Vector đặc trưng trích trọn được với mỗi câu hỏi thường là vector có giạ trị nhị phân (các chiều thường mang giá trị 0 hoặc 1 – xuất hiện hoặc không xuất hiện) khi sử dụng hai kiểu đặc trưng trên. c. Kết quả của thí nghiệm Sau năm lần thí nghiệm với 5 tập dữ liệu có số lượng câu hỏi khác nhau : 1.000, 2.000, 3.000, 4.000 và 5.500 câu. Kết quả thực nghiệm như sau (về độ chính xác): • Thí nghiệm trên tập lớp cha (năm lớp cha như ở bảng 1.0) o Khi chọn vector đặc trưng là bag-of-words Bảng 2. Độ chính xác trên năm phân lớp cha với các giải thuật khác nhau trong học máy, sử dụng vector đặc trưng bag-of-words. Thuật toán 1000 2000 3000 4000 5000 Láng giềng gần nhất 70.0% 73.6% 74.8% 74.8% 75.6% Naïve Bayes 53.8% 60.4% 74.2% 76.0% 77.4% Cây quyết định 78.8% 79.8% 82.0% 83.4% 84.2% SNoW 71.8% 73.4% 74.2% 78.2% 66.8% SVM 76.8% 83.4% 87.2% 87.4% 85.8% 30 o Khi sử dụng vertor đặc trưng là bag-of-Ngrams Bảng 3. Độ chính xác trên năm phân lớp Cha với các giải thuật khác nhau trong học máy, sử dụng vector đặc trưng bag-of-Ngrams • Thí nghiệm trên tập lớp chi tiết (trong bảng 1.0) o Khi chọn vector đặc trưng là bag-of-words Bảng 4. Độ chính xác trên các phân lớp con với các giải thuật khác nhau trong học máy, sử dụng vector đặc trưng bag-of-words. Thuật toán 1000 2000 3000 4000 5000 Láng giềng gần nhất 72.0% 81.0% 79.8% 80.8% 79.8% Naïve Bayes 73.0% 79.2% 80.0% 81.8% 83.2% Cây quyết định 73.8% 82.6% 83.0% 84.6% 84.2% SNoW 59.8% 85.2% 80.6% 87.0% 86.6% SVM 77.6% 82.6% 84.8% 84.8% 87.4% Thuật toán 1000 2000 3000 4000 5000 Láng giềng gần nhất 57.4% 62.8% 65.2% 67.2% 68.4% Naïve Bayes 48.8% 52.8% 56.6% 56.2% 58.4% Cây quyết định 67.0% 70.0% 73.6% 75.4% 77.0% SNoW 42.2% 66.2% 69.0% 66.6% 74.0% SVM 68.0% 75.0% 77.2% 77.4% 80.2% 31 o Khi sử dụng vertor đặc trưng là bag-of-Ngrams Bảng 5. Độ chính xác trên các phân lớp con với các giải thuật khác nhau trong học máy, sử dụng vector đặc trưng bag-of-Ngrams Từ kết quả thực nghiệm trên, nhận thấy rằng: • Độ chính xác của phân lớp tỉ lệ với tập dữ liệu học • SVM mang lại độ chính xác cao hơn so với các phương pháp còn lại. Đối với SVM độ chênh lệnh khi sử dụng tập đặc trưng là bag-of-words và tập đặc trưng bag-of-ngrams là không lớn. Như vậy, dựa trên kết quả thực nghiêm trên và một số thực nghiệm khác của Hacioglu [16] và Li [19]có thể kết luận rằng đối với phân lớp câu hỏi theo phương pháp SVM là lựa chọn khá tốt so với các thuật toán khác trong học máy. Phần thực nghiệm sử dụng SVM cho tập dữ liệu tiếng Việt sẽ được tình bày cụ thể ở Chương 4. 3.3.3 Hướng tiếp cận dựa trên mô hình hình ngôn ngữ Chúng ta có thể xem xét rất nhiều bài toán trong lĩnh vực xử lý ngôn ngữ tự nhiên (Natural Language Processing - NLP) dưới dạng các bài toán phân lớp với nhiệm vụ là ước lượng xác suất có điều kiện p(a|b) của “lớp” a xuất hiện trong “ngữ cảnh” (context) b, hay nói cách khác là, ước lượng xác suất xuất hiện của a với điều kiện b. Ngữ cảnh trong các bài toán xử lý ngôn ngữ tự nhiên thường bao gồm các từ và việc chọn ra ngữ cảnh phụ thuộc theo bài toán đặt ra. Đối với một số bài toán thì ngữ cảnh b có thể là một từ đơn lẻ nhưng đối với một số bài toán khác thì ngữ cảnh b có thể chứa một số từ xung Thuật toán 1000 2000 3000 4000 5000 Láng giềng gần nhất 59.4% 64.6% 67.2% 67.4% 68.6% Naïve Bayes 54.4% 58.4% 63.0% 65.0% 67.8% Cây quyết định 62.8% 72.2% 72.6% 73.0% 77.0% SNoW 44.0% 67.0% 75.0% 55.8% 75.8% SVM 65.0% 74.0% 74.8% 77.4% 79.2% 32 quanh hoặc các từ cùng với các nhãn cú pháp tương ứng. Bài toán đặt ra là chúng ta phải tìm một phương pháp ước lượng (có thể tin tưởng được) mô hình xác suất có điều kiện p(a|b) . Hướng tiếp cận này là tiếp cận theo mô hình ngôn ngữ LM. Ý tưởng cơ bản nhất của LM là : • Các phần của văn bản đều được sinh ra từ một mô hình ngôn ngữ • Giữa hai phần văn bản bất kỳ, có một độ đo thể hiện xác suất chúng cùng được sinh ra bởi một mô hình ngôn ngữ. Trong phân lớp câu hỏi LM được sử dụng để tính xác suất của phân lớp câu hỏi C xuất hiện trong ngữ cảnh câu hỏi Q. Giả sử truy vấn Q là tập hợp của n từ w1,w2, …,wn. Xác suất Q và lớp C được sinh ra bởi cùng một mô hình ngôn ngữ được tính theo công thức: ( ) 1 2| ( | ) ( | ) *...* ( | )nP Q C P w C P w C P w C= ∗ (*) Một mô hình ngôn ngữ sẽ được tạo ra cho mỗi một lớp câu hỏi Ci (i=1,…,n). Mô hình này xây dựng từ tập hợp các câu hỏi thuộc lớp C. Khi một câu hỏi Q tới, xác suất P(Q|Ci) sẽ được tính với tất cả các lớp câu hỏi Ci , Q sẽ được phân vào lớp Ci có xác suất P(Q|Ci) lớn nhất. Thông thường, để khi sử dụng mô hình ngôn ngữ để tiến hành phân lớp các mẫu n-gram (chủ yếu là unigram và bigram) được sử dụng . Công thức (*) là dạng biểu diễn unigram. Bigram có dạng biểu diễn như sau: ( ) 1 2 1 1| ( | ) ( | , w ) *...* ( | , )n nP Q C P w C P w C P w C w −= ∗ (**) Để xác định được xác suất ở (*) hoặc (**) phải tính được giá trị của từng xác suất thành phần ở vế phải: P(wi|C) (với i=1,…,n), một cách trực quan thì xác suất này phải tỉ lệ với số lần từ wi xuất hiện trong C. Ngoài ra, khi áp dụng LM phải có biện pháp loại bỏ trường hợp xác suất P(Q|C) bằng không. Để loại bỏ tình trạng này cần áp dụng những kỹ thuật làm mịn các xác suất thành phần P(wi|C) sao cho minP(wi|C)>0. Các phương pháp làm mịn được tác giả Wei Li giới thiệu cụ thể trong tài liệu [36]. Sử dụng kỹ thuật LM cho phân lớp câu hỏi Wei Li[36] đạt được kết quả khá khả quan (độ chính xác khoảng 80%) khi sử dụng kết hợp hai mẫu unigram và bigram. Một kỹ thuật để nâng cao hiệu suất của LM đó là các mô hình khi xây dựng được tích hợp với bộ phận nhận dạng thực thể tên (Named entity recognition-NE), bộ phận này sẽ nhận diện các thực thể thuộc: tên người, địa danh, số … một từ wi nếu được NE nhận diện, nó sẽ bị thay thể bằng tên dại diện cho lớp thực thể đó. Ví dụ với câu hỏi “Ai là 33 Ronaldo?” nếu “Ronaldo” được nhận dạng thuộc lớp bởi NE, thì câu hỏi sẽ chuyển thành dạnh “ai là ” theo đó, độ chính xác của LM sẽ được nâng cao . 3.3.3.1 Hướng tiếp cận Entropy cực đại Đố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) (được giới thiệu ở tài liệu [17] và [24]) 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 thì “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. 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. 34 Ở 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: ( ) { khi c c' và cp(d) true1cp,c ' 0 otherwisef c,d = == 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 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. 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 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 thoả 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) 35 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 thoả 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 chứng minh ở [28]): ( ) ( )∏ = = 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 – được đưa ra trong [7]; Thuật toán IIS – Improved Iterative Scaling – được đưa ra trong [8] 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 ( ) ( )∑ ∑ ⎟⎠⎞⎜⎝⎛ λ= c ii i c,dfexpdZ 36 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. L-BFGS là thuật toán sử dụng trong phần thử nghiệm với nguyên lý Entropy cực đại ở Chương 4. 37 Chương 4. Thực nghiệm và đánh giá 4.1 Dữ liệu của thực nghiệm Dữ liệu dùng để thử nghiệm cho bộ phân lớp câu hỏi Y tế tiếng Việt là các câu hỏi được lấy từ các trang sau Web: . Tập dữ liệu kiểm tra lấy từ báo và Toàn bộ dữ liệu của thử nghiệm đều được gán nhãn bằng tay. Các phân lớp của dữ liệu được thiết kế dựa trên Ontology Y tế đã được giới thiệu ở chương 2, mục 2.3 bao gồm 8 lớp như sau: STT Phân lớp Ký hiệu Số lượng câu hỏi 1 Benh B 413 2 dia_diem DD 43 3 Nguyen_nhan NN 114 4 trieu_chung TC 42 5 hoat_dong HD 314 6 thuc_pham TP 105 7 Thuoc TH 96 8 thoi_gian T 23 Tổng số 1150 Bảng 6.Tập dữ liệu huấn luyện Dữ liệu dùng cho huấn luyện cùng số lượng câu hỏi được mô tả trong Bảng 6 bao gồm 1144 câu hỏi được lấy cân bằng theo các lớp, tuy nhiên có một số lớp có sự chênh lệch lớn là do chúng tôi nhận thấy rằng số lượng từ chuyên môn của lớp đó và nhu cầu hỏi 38 trong lớp đấy không nhiều như các lớp khác nên không cần phải sử dụng một lượng câu hỏi quá lớn. Tập dữ liệu dùng để kiểm tra được mô tả trong bảng 7, số lượng câu hỏi của mỗi lớp tỉ lệ với số lượng câu hỏi trong tập dữ liệu dùng để huấn luyện. STT Phân lớp Ký hiệu Số lượng câu hỏi 1 benh B 48 2 dia_diem DD 9 3 nguyen_nhan NN 20 4 trieu_chung TC 13 5 hoat_dong HD 38 6 thuc_pham TP 29 7 thuoc TH 31 8 thoi_gian T 6 Tổng số 194 Bảng 7. Tập dữ liệu kiểm tra 4.2 Thiết kế thử nghiệm Khóa luận thử nghiệm theo hai thuật toán Support Vector Machines và nguyên lý Entropy cực đại. a. Thiết lập thông số cho SVM 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 [44], đòi hỏi thiết lập một số thông số cho chương trình, các thông số này được lựa chọn qua nhiều lần thử nghiệm. Chi tiết các thông số được trình bày trong bảng 8. 39 Tham số Giá trị Mô tả -c 1.0 Giá trị chuyển đổi giữa lỗi của tập huấn luyện và độ lệch chuẩn -t 0 Loại hàm nhân của , 0 là lựa chọn hàm tuyến tính -w 3 Cấu trúc của thuật toán học, 3 là lựa chọn thuật toán nối ràng buộc đôi. Bảng 8. Tham số huấn luyện mô hình SVM b. Thiết lập thông số cho Entropy cực đại 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, X.H [43], việc sử dụng cũng đòi hỏi thiết lập một số thông số cho mô hình. Các thông số này cũng được lựa chọn qua nhiều lần thử nghiệm, chi tiết được mô tả ở bảng 9. Tham số Giá trị Mô tả numIterations 10 Số bước lặp trong quá trình huấn luyện cpRareThreshold 0 Các đặc trưng xuất hiện nhiều hơn số này thì sẽ không bị loại bỏ khỏi tập dữ liệu huấn luyện. fRareThreshold 0 Các mệnh đề mô tả thông tin ngữ cảnh phải xuất hiện nhiều hơn số này thì sẽ được dùng để xây dựng các đặc trưng. Bảng 9. Tham số huấn luyện mô hình Entropy cực đại 4.3 Kết quả thực nghiệm a. Kết quả thực nghiệm với SVM Với SVM khi tiến hành thử nghiệm với tập dữ liệu tiếng Việt, sử dụng độ đo TF-IDF trên mẫu unigram, trong thời gian 1.56 giây cho kết quả khá thấp. Chi tiết kêt quả mô tả ở bảng 10. Thuật toán Thời gian Độ chính xác Tỉ lệ lỗi SVM 1.56 26% 58/148 Bảng 10. kết quả huấn luyện với SVM 40 b. Kết quả thực nghiệm với Entropy cực đại Tiến hành thử nghiệm trên tập dữ liệu huấn luyện với số lượng bước lặp là 10. Các kết quả thu được khá khả quan với thời gian khoảng 0.15giây/lần và được mô tả trong một số bảng biểu và đồ thị được biểu diễn sau đây. Độ chính xác Độ hồi tưởng F1 Bước lặp Thời gian Avg1 Avg2 Avg1 Avg2 Avg1 Avg2 1 0.26 46.54 55.15 38.81 55.15 42.32 55.15 2 0.22 49.24 60.82 45.37 60.82 47.22 60.82 3 0.127 63.99 63.92 51.83 63.92 57.27 63.92 4 0.11 71.40 65.98 59.80 65.98 65.09 65.98 5 0.132 73.56 67.53 63.15 67.53 67.95 67.53 6 0.133 73.54 69.07 64.64 69.07 68.80 69.07 7 0.117 72.93 67.01 62.83 67.01 67.51 67.01 8 0.135 69.13 64.95 60.55 64.95 64.56 64.95 9 0.153 70.24 63.92 59.93 63.92 64.67 63.92 10 0.106 79.25 65.46 61.85 65.46 69.47 65.46 Trung bình 0.1493 66.982 64.381 56.876 64.381 61.486 64.381 Bảng 11. Kết quả 10 lần huấn luyện với Entropy cực đại Qua bảng trên, chúng tôi thấy kết quả khả quan nhất là ở bước lặp thứ 6 với độ đo F1 đạt 69.07% chi tiết về bước lặp này như sau: 41 Nhãn Độ chính xác Độ hồi tưởng F1 benh 65.57 83.33 73.39 hoat_dong 62.22 73.68 67.47 dia_diem 50.00 23.08 31.58 nguyen_nhan 80.00 88.89 84.21 thoi_gian 88.24 75.00 81.08 trieu_chung 100.00 50.00 66.67 thuoc 76.92 64.52 70.18 thuc_pham 65.38 58.62 61.82 Avg1 73.54 64.64 68.80 Avg2 69.07 69.07 69.07 Bảng 12. Kết quả của bước lặp thứ 6 Trong bảng kết quả trên thì kết quả của phân lớp địa_điểm rất kém với độ đo chính xác là 31.58% và tốt nhất là phân lớp nguyên_nhân với độ chính xác là 84.21%. 42 0 10 20 30 40 50 60 70 80 1 2 3 4 5 6 7 8 9 10 Bước lặp Đ ộ đo F 1 F1-Avg2 F1-Avg1 Hình 7. Đồ thị biểu diễn sự phụ thuộc của F1 vào số lần lặp 0 10 20 30 40 50 60 70 80 90 1 2 3 4 5 6 7 8 9 10 Bước lặp Đ ộ ch ín h xá c củ a ph ân lo ại Độ chính xác Độ hồi tưởng F1 Hình 8. Tổng hợp độ đo 10 lần huấn luyện 43 4.4 Đánh giá kết quả thực nghiệm Kết quả thực nghiệm thu được cho thấy có sự chênh lệch rất lớn giữa hai phương pháp SVM và Entropy cực đại (SVM có độ chính xác là 25% và Entropy cực đại là 70%) khi sử dụng cho bộ phân lớp câu hỏi tiếng Việt. Đâu là nguyên nhân dẫn đến sự chênh lệch này? a. Đối với thuật toán SVM SVM khi áp dụng vào bộ phân lớp câu hỏi tiếng Anh có độ chính xác rất cao (khoảng 80% – như trong các bài báo [16] và [42] công bố) nhưng khi sử dụng thuật toán này cho bộ dữ liệu tiếng Việt độ chính xác bị giảm đáng kể. Nguyên nhân của sự sụt giảm này có thể được lý giải theo cảm tính như sau: (1) Khóa luận sử dụng tập dữ liệu khác so với tập dữ liệu của các tác giả Hacioglu [16] và Zhang [42] (2) Số lượng dữ liệu học chưa đủ lớn (1150 câu hỏi) chưa thể hiện hết được các đặc trưng của từng lớp câu hỏi. Khi tập dữ liệu dùng để huấn luyện tăng lên độ chính xác của thuật toán cũng được nâng lên. (3) Có sự khác biệt về vector đặc trưng sử dụng khi biểu diễn câu hỏi; nguyên nhân này có thể là thứ yếu vì trong bài báo [42], tác giả Zhang cũng sử dụng TF IDF và mô hình unigram để làm vector đặc trưng cho từng câu hỏi. b. Đối với nguyên lý Entropy cực đại Đối với tập dữ liệu học là 1150 câu hỏi cho 8 phân lớp cho kết quả khá khả quan về độ đo F1 là 69.07%. Mặt khác, do số lượng câu hỏi huấn luyện cho từng phân lớp có sự chênh lệch dẫn đến khả năng đoán nhẫn của từng phân lớp cũng khác nhau. Ví dụ như lớp Bệnh có số lượng câu hỏi là 413 trong khi lớp thời_gian có số lượng câu hỏi là 23. Lý do của việc này là khi xảy ra sự mất cân bằng trong số lượng dữ liệu dùng để huấn luyện, trọng số của các đặc trưng có ích chuyên biệt cho từng lớp sẽ không cao do đó mô hình rất dễ đoán nhận nhầm. Để đảm bảo khả năng đoán nhận của các phân lớp cần bằng với nhau và khả năng đoán nhận tốt thì số lượng câu hỏi mẫu cho từng lớp cần phải tương đương nhau về mặt số lượng. Song song với đó là tập câu hỏi huấn luyện cần gia tăng thêm về số lượng, đảm bảo cung cấp đầu đủ các ràng buộc từ dữ liệu cho mô hình. Như trong mục 3.3.3 đã trình bày, tư tưởng chủ đạo của nguyên lý cực đại Entropy là thay vì thêm vào các ràng buộc mới, 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. Điều này là khác với 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. Cho nên khi tập liệu không có số lượng quá lớn và mỗi một tài liệu chỉ chứa ít đặc trưng (như câu hỏi) làm cho sự phân lớp của SVM bị giảm sút trong khi mô hình của phân lớp của nguyên lý cực đại Entropy vấn được bảo đảm. 44 Từ những kết quả thực nghiệm trên cho thấy khi xây dựng bộ phân lớp câu hỏi tiếng Việt thuật toán nguyên lý Entropy cực đại tỏ ra thích hợp hơn so với các thuật toán khác. 45 Kết luận Nhu cầu xây dựng một hệ thống tìm kiếm ngữ nghĩa cho từng lĩnh vực trong đời sống ngày càng trở cấp thiết, trong đó vấn đề xây dựng hai module phân lớp câu hỏi và mạng ngữ nghĩa chịu ảnh hưởng bởi đặc trưng riêng của từng ngôn ngữ là phần quan trong trong quá trình xây dựng một hệ thống tìm kiếm ngữ nghĩa . Sự đa dạng của các thuật toán phân loại dữ liệu nói chung và phân lớp câu hỏi nói riêng khiến cho việc lựa chọn thuật toán để xây dựng module phân lớp câu hỏi cho từng ngôn ngữ tở nên khó khăn hơn. Khóa luận này tiếp cận các vấn đề nói trên và nghiên cứu các thuật toán phổ biến hiện nay cho phân lớp câu hỏi, từ đó đưa ra phương pháp và thuật toán áp dụng vào tiếng Việt . Khóa luận đã đạt được những kết quả: • Phân tích các vấn đề xung quanh bài toán xây dựng một hệ thống tìm kiếm ngữ nghĩa • Chỉ ra các module chịu ảnh hưởng bởi đặc trưng ngôn ngữ và phân tích phương pháp xây dựng các module này. • Khảo sát các thuật toán phân lớp câu hỏi và lựa chọn thuật toán tốt nhất khi áp dụng cho tiếng Việt • Xây dựng module phân lớp câu hỏi Y tế trong tiếng Việt. Do giới hạn về thời gian cũng như kiến thức của tác giả cho nên hiệu quả module phân lớp câu hỏi cho tiếng Việt chưa thực sự cao. Hạn chế này cần được tiếp tục nghiên cứu và cải tiến qua đó để khẳng định tính hiệu quả của phương pháp chỉ ra. 46 Tài liệu tham khảo Tiếng Việt [1] Lê Diệu Thu, Trần Thị Ngân, “Xây dựng Ontology nhằm hỗ trợ tìm kiếm ngữ nghĩa trong lĩnh vực Y tế”, Công trình sinh viên nghiên cứu khoa học, Đại học Công nghệ, ĐHQGHN, 2008. [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ệ, ĐHQGHN, 2006. [3] Trung tâm ngôn ngữ học Việt Nam. “Đặc điểm tiếng Việt”, [4] VN-KIM , Đại học Bách khoa, ĐHQG Thành Phố Hồ chí Minh Tiếng Anh [5] Clocksin W. F. and Mellish C. S., “Programming in Prolog”, Springer-Verlag, 1981. [6] D. Roth. “Learning to Resolve Natural Language Ambiguities: A Unified Approach.” Proceedings of AAAI'98: 806-813, Madison, WI, USA, Jul 1998. [7] Darroch, J. and Ratcliff, D. “Generalized iterative scaling for log-linear models”. Annals Mathematical Statistics, 43(5):1470–1480, 1972. [8] Della Pietra, S., Della Pietra, V. and Lafferty, J. “Inducing features of random fields”. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(4):380–393, 1997. [9] Description logic, [10] Dieter E. Jenz “Ontology-Based Business Process Management: The Vision Statement”, White Paper, Jenz and Partner GmbH, 2003 [11] E. Hovy, L. Gerber, U. Hermjakob, C. Lin, and D. Ravichandran. “Towards Semantics-based Answer Pinpointing”. Proceedings of the DARPA Human Language Technology conference (HLT), San Diego, CA,1999 [12] E. Voorhees. “Overview of the TREC 2001 Question Answering Track”. Proceedings of the 10th Text Retrieval Conference (TREC10): 157-165, NIST, Gaithersburg, MD, 2001. [13] E. Voorhees. Overview of the TREC-9 Question Answering Track. Proceedings of the 9th Text Retrieval Conference (TREC9): 71-80, NIST, Gaithersburg, MD, 2000. [14] E. Voorhees. The TREC-8 Question Answering Track Report. Proceedings of the 8th Text Retrieval Conference (TREC8): 77-82, NIST, Gaithersburg, MD, 1999. 47 [15] Jonathan Brown, “Entity-Tagged Language Models for Question Classification in a QA System”, IR Lab project, 2004. 743s04/jonbrown/Brown-IRLab.pdf [16] Kadri Hacioglu and Wayne Ward. "Question Classification with Support Vector Machines and Error Correcting Codes". Proceedings of HLT-NAACL 2003:28-30, Edmonton, Alberta, Canada, May 2003. [17] K. Nigam, J. Lafferty, and A. McCallum, "Using maximunm Entropy for text classification", Proceeding of the 16th International Joint Conference Workshop on Machine Learning for Information Filtering: 61-67 Stockholm, Sweden, 1999. [18] Kincho H. Law, “Ontology: Basic Definitions and a Brief Introduction”, TN-2007- 03. NEESit – Workshops 2007. [19] Li, X. & Roth, D. “Learning Question Classifiers”, Proceedings of the 19th International Conference on Computational Linguistics (COLING):556–562, 2002. [20] 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. [21] Maria Vargas-Vera, Enrico Motta, John Domingue: “AQUA: An Ontology-Driven Question Answering System”, New Directions in Question Answering:53-57, 2003. [22] McCallum and K. Nigam. “A Comparison of Event Models for Naïve Bayes Text Classification”, AAAI-98Workshop on Learning for Text Categorization, 1998. [23] N. Guarino (ed.), “Formal Ontology in Information Systems”. Proceedings of FOIS’98:3-15, Trento, Italy, 6-8 June 1998. Amsterdam, IOS Press. [24] Nguyen Viet Cuong, Nguyen Thi Thuy Linh Ha, Quang Thuy and Phan Xuan Hieu (2006). A Maximum Entropy Model for Text Classification. The International Conference on Internet Information Retrieval 2006:134-139, Hankuk Aviation University, December 6, 2006, Goyang-si, Korea. [25] Noy, N.F., and McGuinness, D.L. “Ontology Development 101: A Guide to Creating Your First Ontology SMI”, Technical report SMI-2001-0880 (2001), Stanford University. [26] Pierre Baldi, Paolo Frasconi, Padhraic Smyth. “Modeling the Internet and the Web: Probabilistic Methods and Algorithms”, John Wiley and Sons, 2003. [27] R.Guha, Rob McCool, Eric Miller. “Semantic Search”, 48 [28] Ratnaparkhi, A. “A simple introduction to maximum Entropy models for natural language processing”. Technical Report 97-08, Institute for Research in Cognitive Science, University of Pennsylvania, 1997. [29] S.Cohen , Mamou, J., Kanza, Y., Sagiv, Y.: “ Xsearch: A semantic search engine for xml”. In: Proceedings of of the 29th VLDB Conference, Berlin, Germany. (2003) [30] S Decker, F van Harmelen, J Broekstra, M Erdmann, Dieter Fensel, Ian Horrocks, Michel Klein, Sergey Melnik. “The Semantic Web - on the respective Roles of XML and RDF”, IEEE Internet Computing, 4(5):63-74, 2000. [31] Soumen Chakrabarti. “Mining the Web: discovering knowledge from hypertext data”, Morgan Kaufmann Publishers, 2003. [32] T. Mitchell. “Machine Learning”, McGraw Hill, New York,1997. [33] “Taxonomy”, [34] Tim Berners-Lee, “Semantic Web Road map”, [35] Van Durme, B., Huang, Y., Kupsc, A. and Nyberg, E. "Towards Light Semantic Processing for Question Answering", HLT/NAACL Workshop on Text Meaning, 2003, [36] W Li “Question Classification Using Language Modeling” – Technical report Center for Intelligent Information Retrieval Department of Computer Science University of Massachusetts, Amherst, MA 01003, 2002 [37] W3C, Extensible Markup Language [38] W3C, OWL Web Ontology Language Overview, features/ [39] W3C, Abstract Syntax (Normative) RDF concepts/#section-Graph-syntax [40] W3C, Semantic Web Activity [41] Y. Yang and X. Liu. A Re-examination of Text Categorization Methods. In Proceedings of ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’99), trang 42-49, 1999. [42] Zhang, D. and Lee, W.S. “Question Classification using Support Vector Machines” , In Proceedings of SIGIR 2003. [43] Phan, X.H, “JTextPro: A Java-based Text Processing Toolkit”, [44] Thorsten Joachims, SVM multiclass Multi-Class Support Vector Machine, Cornell University Department of Computer Science.