Đồ án Các đặc trưng ngôn ngữ cho bài toán phân loại câu hỏi tiếng Việt

ì, v.v.) 9 WHAP Cụm tính từ nghi vấn (lạnh thế nào, đẹp ra sao, v.v.) 10 WHRP Cụm từ nghi vấn dùng khi hỏi về thời gian, nơi chốn, v.v. 11 WHPP Cụm giới từ nghi vấn (với ai, bằng cách nào, v.v.) 12 S Câu trần thuật (khẳng định hoặc phủ định) 13 SQ Câu hỏi 14 SBAR Mệnh đề phụ (bổ nghĩa cho danh từ, động từ, và tính từ) Bảng 2-3: Nhãn chức năng cú pháp [13] STT Tên Chú thích 1 SUB Nhãn chức năng chủ ngữ 2 DOB Nhãn chức năng tân ngữ trực tiếp 3 IOB Nhãn chức năng tân ngữ gián tiếp 4 TPC Nhãn chức năng chủ đề 5 PRD Nhãn chức năng vị ngữ không phải cụm động từ 6 LGS Nhãn chức năng chủ ngữ logic của câu ở thể bị động 7 EXT Nhãn chức năng bổ ngữ chỉ phạm vi hay tần suất của hành động 8 H Nhãn phần tử trung tâm (của cụm từ hoặc mệnh đề) 9 – 12 TC, CMD, EXC, SPL Nhãn phân loại câu: đề thuyết, mệnh lệnh, cảm thán, đặc biệt 13 TTL Tít báo hay tiêu đề 14 VOC Thành phần hô cách 15 TMP Nhãn chức năng trạng ngữ chỉ thời gian 16 LOC Nhãn chức năng trạng ngữ chỉ nơi chốn 17 DIR Nhãn chức năng trạng ngữ chỉ hướng 18 MNR Nhãn chức năng trạng ngữ chỉ cách thức 19 PRP Nhãn chức năng trạng ngữ chỉ mục đích hay lí do 20 ADV Nhãn chức năng trạng ngữ nói chung ĐỒ ÁN TỐT NGHIỆP Chương 2: Hệ thống phân loại câu hỏi tiếng Việt GVHD: TS. Ngô Xuân Bách 16 SVTH: Nguyễn Đình Nghị – D11CNPM3 Ví dụ phân tích phụ thuộc một câu tiếng Việt: Hình 2-2: Phân tích phụ thuộc của một câu tiếng Việt [2]. Trong đồ án, chúng tôi sử dụng công cụ VnDP [23] (A Vietnamese dependency parsing toolkit) để chuyển định dạng các câu hỏi về dạng cây cú pháp phụ thuộc. Ví dụ chúng ta có 2 câu: Câu 1: Trong hai thành phố Hà Nội và Bắc Ninh, thành phố nào có diện tích lớn hơn? Câu 2: Hà Nội là thành phố có diện tích lớn nhất Việt Nam phải không? Biểu diễn cây cú pháp: 1 Trong Trong E E - 10 loc - - 2 hai hai M M - 3 det - - 3 thành_phố thành_phố N N - 1 pob - - 4 Hà_Nội Hà_Nội N N - 3 nmod - - 5 và và C C - 4 coord - - 6 Bắc_Ninh Bắc_Ninh N N - 5 conj - - 7 , , , , - 6 punct - - 8 thành_phố thành_phố N N - 10 sub - - 9 nào nào P P - 8 nmod - - 10 có có V V - 0 root - - 11 diện_tích diện_tích N N - 10 dob - - 12 lớn lớn A A - 11 nmod - - 13 hơn hơn A A - 12 amod - - 1 Hà_Nội Hà_Nội N N - 2 sub - - 2 là là V V - 0 root - - 3 thành_phố thành_phố N N - 2 dob - - 4 có có V V - 2 vmod - - 5 diện_tích diện_tích N N - 4 dob - - 6 lớn lớn A A - 5 nmod - - 7 nhất nhất R R - 6 amod - - 8 Việt_Nam Việt_Nam N N - 9 sub - - 9 phải phải A A - 2 dep - - 10 không không R R - 9 amod - - ĐỒ ÁN TỐT NGHIỆP Chương 2: Hệ thống phân loại câu hỏi tiếng Việt GVHD: TS. Ngô Xuân Bách 17 SVTH: Nguyễn Đình Nghị – D11CNPM3 Sau khi có biểu diễn cây cú pháp, chúng ta trích rút đặc trưng root và child, mỗi một câu chỉ có một root duy nhất, và mỗi root có thể có nhiều child: Câu 1: root = “có” child = “trong” child = “thành phố” child = “diện tích” Câu 2: root = “là” child = “Hà_Nội” child = “thành_phố” child = “có” child = “đẹp” Từ tập đặc trưng của cây cú pháp, chúng ta cũng xây dựng tập từ điển chứa các đặc trưng đó và biểu diễn các đặc trưng dưới dạng vector đặc trưng tương tự như các loại đặc trưng khác. 2.3 Các thuật toán học máy Có nhiều thuật toán khác nhau cho phân lớp như Naïve Bayes, K-láng giềng gần nhất, cây quyết định (Decision Tree), Máy véc tơ hỗ trợ (Support Vector Machine), Mạng lọc thưa (Sparse Network of Winnows - SNoW), Mô hình Entropy cực đại, v.v. Tuy nhiên phần tiếp theo của đồ án, chúng tôi chỉ trình bày 3 thuật toán là Máy véc tơ hỗ trợ, Naïve Bayes và K-láng giềng gần nhất, đây là các thuật toán được sử dụng nhiều trong phân loại câu hỏi và cũng sẽ được sử dụng trong phần thực nghiệm ở chương 3. 2.3.1 Máy véc tơ hỗ trợ (Support Vector Machine) Support Vector Machine [17] viết tắt là SVM, là một phương pháp trong thống kê và khoa học máy tính cho một tập hợp các phương pháp học có giám sát liên quan đến nhau để phân loại và phân tích hồi quy. SVM dạng chuẩn nhận dữ liệu vào và phân loại chúng vào 2 lớp khác nhau. a) Ý tƣởng Cho trước một tập huấn luyện, được biểu diễn trong không gian vector, trong đó mỗi tài liệu là một điểm, phương pháp này tìm ra một siêu phẳng quyết định tốt nhất có thể chia các điểm trên không gian này thành hai lớp riêng biệt tương ứng là lớp + và lớp -. Chất lượng của siêu phẳng này được quyết định bởi khoảng cách (gọi là biên) của điểm dữ liệu gần nhất của mỗi lớp đến mặt phẳng này. Khi đó, khoảng cách biên càng lớn thì mặt phẳng quyết định càng tốt, đồng thời việc phân loại càng chính xác. Mục đích của phương pháp SVM là tìm được khoảng cách biên lớn nhất, điều này được minh họa như sau: Hình 2-3: Siêu phẳng phân chia dữ liệu học thành 2 lớp + và – với khoảng cách biên lớn nhất [17]. ĐỒ ÁN TỐT NGHIỆP Chương 2: Hệ thống phân loại câu hỏi tiếng Việt GVHD: TS. Ngô Xuân Bách 18 SVTH: Nguyễn Đình Nghị – D11CNPM3 b) Cơ sở lý thuyết SVM thực chất là một bài toán tối ưu, mục tiêu của thuật toán này là tìm được một không gian F và siêu phẳng quyết định f trên F sao cho sai số phân loại là thấp nhất. Cho tập mẫu (x1, y1), (x2, y2), (xf, yf)} với xi ∈ Rn, thuộc vào hai lớp nhãn: yi ∈ {-1,1} là nhãn lớp tương ứng của các xi (-1 biểu thị lớp I, 1 biểu thị lớp II). Ta có, phương trình siêu phẳng chứa vectơ ⃑⃑⃑ trong không gian: ⃑⃑⃑ ⃑⃑ ( ⃑⃑ ⃑) ( ⃑⃑⃑ ⃑⃑ ) { ⃑⃑⃑ ⃑⃑ ⃑⃑⃑ ⃑⃑ Như vậy, f(Xi) biểu diễn sự phân lớp của Xi vào hai lớp như đã nêu. Ta nói yi = +1 nếu Xi thuộc lớp I và yi = -1 nếu Xi thuộc lớp II. Khi đó, để có siêu phẳng f ta sẽ phải giải bài toán sau: Tìm min w với W thỏa mãn điều kiện sau: ( ( ⃑⃑⃑ ⃑⃑ )) ∈ ⃑⃑ ⃑⃑ ⃑⃑ Bài toán SVM có thể giải bằng kỹ thuật sử dụng toán tử Lagrange để biến đổi về thành dạng đẳng thức. Một đặc điểm thú vị của SVM là mặt phẳng quyết định chỉ phụ thuộc các Support Vector và nó có khoảng cách đến mặt phẳng quyết định là . Cho dù các điểm khác bị xóa đi thì thuật toán vẫn cho kết quả giống như ban đầu. Đây chính là điểm nổi bật của phương pháp SVM so với các phương pháp khác vì tất cả các dữ liệu trong tập huấn luyện đều được dùng để tối ưu hóa kết quả. Bài toán phân 2 lớp với SVM Bài toán đặt ra là: Xác định hàm phân lớp để phân lớp các mẫu trong tương lai, nghĩa là với một mẫu dữ liệu mới xi thì cần phải xác định xi được phân vào lớp +1 hay lớp -1 Hình 2-4: Minh họa bài toán phân 2 lớp bằng phương pháp SVM [17]. Để xác định hàm phân lớp dựa trên phương pháp SVM, ta sẽ tiến hành tìm hai siêu phẳng song song sao cho khoảng cách y giữa chúng là lớn nhất có thể để phân ĐỒ ÁN TỐT NGHIỆP Chương 2: Hệ thống phân loại câu hỏi tiếng Việt GVHD: TS. Ngô Xuân Bách 19 SVTH: Nguyễn Đình Nghị – D11CNPM3 tách hai lớp này ra làm hai phía. Hàm phân tách tương ứng với phương trình siêu phẳng nằm giữa hai siêu phẳng tìm được. Các điểm mà nằm trên hai siêu phẳng phân tách được gọi là các Support Vector. Các điểm này sẽ quyết định đến hàm phân tách dữ liệu. Bài toán nhiều phân lớp với SVM Để phân nhiều lớp thì kỹ thuật SVM nguyên thủy sẽ chia không gian dữ liệu thành 2 phần và quá trình này lặp lại nhiều lần. Khi đó hàm quyết định phân dữ liệu vào lớp thứ i của tập n, 2-lớp sẽ là: ( ) Những phần tử x là support vector sẽ thỏa điều kiện: ( ) { Như vậy, bài toán phân nhiều lớp sử dụng phương pháp SVM hoàn toàn có thể thực hiện giống như bài toán 2 lớp. Bằng cách sử dụng cách thức “một - đối - một”. Giả sử bài toán cần phân loại có k lớp (k > 2), chiến lược "một-đối-một”sẽ tiến hành ( ) lần phân lớp nhị phân sử dụng phương pháp SVM. Mỗi lớp sẽ tiến hành phân tách với k-1 lớp còn lại để xác định k-1 hàm phân tách dựa vào bài toán phân hai lớp bằng phương pháp SVM. c) Các bƣớc chính của phƣơng pháp SVM  Phương pháp SVM yêu cầu dữ liệu được biểu diễn như các vector của các số thực. Như vậy nếu đầu vào chưa phải là số thì ta cần phải tìm cách chuyển chúng về dạng số của SVM.  Tiền xử lý dữ liệu: Thực hiện biến đổi dữ liệu phù hợp cho quá trình tính toán, tránh các số quá lớn mô tả các thuộc tính. Thường nên co giãn (scaling) dữ liệu để chuyển về đoạn [-1, 1] hoặc [0, 1].  Chọn hàm hạt nhân: Lựa chọn hàm hạt nhân phù hợp tương ứng cho từng bài toán cụ thể để đạt được độ chính xác cao trong quá trình phân lớp.  Thực hiện việc kiểm tra chéo để xác định các tham số cho ứng đụng. Điều này cũng quyết định đến tính chính xác của quá trình phân lớp.  Sử dụng các tham số cho việc huấn luyện với tập mẫu. Trong quá trình huấn luyện sẽ sử dụng thuật toán tối ưu hóa khoảng cách giữa các siêu phẳng trong quá trình phân lớp, xác định hàm phân lớp trong không gian đặc trưng nhờ việc ánh xạ dữ liệu vào không gian đặc trưng bằng cách mô tả hạt nhân, giải quyết cho cả hai trường hợp dữ liệu là phân tách và không phân tách tuyến tính trong không gian đặc trưng.  Kiểm thử tập dữ liệu Test. ĐỒ ÁN TỐT NGHIỆP Chương 2: Hệ thống phân loại câu hỏi tiếng Việt GVHD: TS. Ngô Xuân Bách 20 SVTH: Nguyễn Đình Nghị – D11CNPM3 2.3.2 Naïve Bayes a) Giới thiệu Naïve Bayes (NB) [17] là phương pháp phân loại có giám sát dựa vào xác suất được sử dụng rộng rãi trong lĩnh vực máy học [Mitchell, 1996] [Joachims, 1997] [Jason, 2001], được sử dụng lần đầu tiên trong lĩnh vực phân loại bởi Maron vào năm 1961 [Maron, 1961] sau đó trở nên phổ biến dùng trong nhiều lĩnh vực như trong các công cụ tìm kiếm [Rijsbergen et al, 1970], các bộ lọc email [Sahami et al, 1998] v.v. b) Cơ sở lý thuyết Thuật toán Naïve Bayes dựa trên định lý Bayes được phát biểu như sau: ( ) ( ) ( ) ( ) ( ) ( ) Áp dụng trong bài toán phân loại, các dữ kiện gồm có: - D: tập dữ liệu huấn luyện đã được vector hóa dưới dạng ( ). - Ci: phân lớp i, với i = {1,2,,m}. - Các thuộc tính độc lập điều kiện đôi một với nhau. Theo định lý Bayes: ( ) ( ) ( ) ( ) Theo tính chất độc lập điều kiện: ( ) ∏ ( ) Trong đó: - ( ) là xác suất thuộc phân lớp i khi biết trước mẫu X. - ( ) xác suất là phân lớp i. - ( ) xác suất thuộc tính thứ k mang giá trị xk khi đã biết X thuộc phân lớp i. Các bước thực hiện thuật toán Naïve Bayes: Bước 1: Huấn luyện Naïve Bayes (dựa vào tập dữ liệu), tính ( ) và ( ). Bước 2: Phân lớp ( ), ta cần tính xác suất thuộc từng phân lớp khi đã biết trước Xnew. Xnew được gán vào lớp có xác suất lớn nhất theo công thức: ∈ ( ( )∏ ( ) ) ĐỒ ÁN TỐT NGHIỆP Chương 2: Hệ thống phân loại câu hỏi tiếng Việt GVHD: TS. Ngô Xuân Bách 21 SVTH: Nguyễn Đình Nghị – D11CNPM3 c) Áp dụng cho bài toán phân loại câu hỏi Ý tưởng: Ý tưởng cơ bản của cách tiếp cận Naïve Bayes là sử dụng xác suất có điều kiện giữa từ và chủ đề để dự đoán xác suất chủ đề của một câu hỏi cần phân loại. Điểm quan trọng của phương pháp này chính là ở chỗ giả định rằng sự xuất hiện của tất cả các từ trong câu hỏi đều độc lập với nhau. Giả định đó làm cho việc tính toán NB hiệu quả và nhanh chóng hơn các phương pháp khác vì không sử dụng việc kết hợp các từ để đưa ra phán đoán chủ đề. Kết quả dự đoán bị ảnh hưởng bởi kích thước tập dữ liệu, chất lượng của không gian đặc trưng. Hướng dẫn cài đặt: Mô tả vector đặc trưng của văn bản: là vector có số chiều là số đặc trưng trong toàn tập dữ liệu, các đặc trưng này đôi một khác nhau. Nếu văn bản có chứa đặc trưng đó sẽ có giá trị 1, ngược lại là 0. Thuật toán gồm 2 giai đoạn huấn luyện và phân lớp:  Huấn luyện: tính ( ) và ( ) Đầu vào: - Các vector đặc trưng của văn bản trong tập huấn luyện (Ma trận MxN, với M là số vector đặc trưng trong tập huấn luyện, N là số đặc trưng của vector). - Tập nhãn/lớp cho từng vector đặc trưng của tập huấn luyện. Đầu ra: - Các giá trị xác suất ( ) và ( ). Công thức tính ( ) đã làm trơn Laplace: ( ) Trong đó: - |docsi|: số văn bản của tập huấn luyện thuộc phân lớp i. - |total docs|: số văn bản trong tập huấn luyện. - M: số phân lớp Cài đặt: - Khởi tạo mảng A, B có kích thước m. - Duyệt qua các văn bản trong tập dữ liệu, đếm số văn bản trong mỗi phân lớp lưu vào A. - Tính xác suất cho từng phân lớp theo công thức trên và lưu vào mảng B. Công thức tính ( ) đã làm trơn Laplace: ĐỒ ÁN TỐT NGHIỆP Chương 2: Hệ thống phân loại câu hỏi tiếng Việt GVHD: TS. Ngô Xuân Bách 22 SVTH: Nguyễn Đình Nghị – D11CNPM3 ( ) | | Trong đó: - | |: Số văn bản trong trong phân lớp i có đặc trưng thứ k mang giá trị xk. (hay số văn bản trong lớp i, có xuất hiện/không xuất hiện đặc trưng k) - : Số văn bản của tập huấn luyện thuộc phân lớp i. - Số giá trị có thể có của đặc trưng thứ k Cài đặt: - Với vector đặc trưng như mô tả bên trên, dk ở đây mang giá trị là 2, tương ứng với xuất hiện và không xuất hiện. Do chỉ có 2 giá trị, ta có thể tính nhanh xác suất không xuất hiện theo công thức ( ̅) ( ). - Khởi tạo mảng 3 chiều C, chiều 1 có kích thước là m (số phân lớp), chiều 2 có kích thước là N (số đặc trưng), chiều 3 có kích là 2 (dk) để lưu các giá trị ( ). - Duyệt qua các văn bản trong tập dữ liệu, tiến hành thống kê các chỉ số cần thiết để tính xác suất ( ) theo công thức trên và lưu vào mảng C.  Phân lớp Đầu vào: - Vector đặc trưng của văn bản cần phân lớp - Các giá trị xác suất tính ( ) và ( ). Đầu ra: - Giá trị xác suất thuộc phân lớp I khi biết trước mẫu X Dựa vào vector đặc trưng của văn bản cần phân lớp, áp dụng công thức trên tính xác suất thuộc từng phân lớp cho văn bản, và chọn ra lớp có xác suất cao nhất. 2.3.3 K láng giềng gần nhất (K-nearest neighbors) a) Giới thiệu K-Nearest Neighbors (KNN) [17] được sử dụng rất phổ biến trong lĩnh vực Data Mining. KNN là phương pháp để phân lớp các đối tượng dựa vào khoảng cách gần nhất giữa đối tượng cần xếp lớp với tất cả các đối tượng trong Training Data. Một đối tượng được phân lớp dựa vào k láng giềng của nó. K là số nguyên dương được xác định trước khi thực hiện thuật toán. Người ta thường dùng khoảng cách Euclide để tính khoảng cách giữa các đối tượng. b) Cơ sở lý thuyết 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 ĐỒ ÁN TỐT NGHIỆP Chương 2: Hệ thống phân loại câu hỏi tiếng Việt GVHD: TS. Ngô Xuân Bách 23 SVTH: Nguyễn Đình Nghị – D11CNPM3 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 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 Euclide để 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 người láng giềng 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: ( ) ∑ ( ) ∈ ( ) Trong đó Nc(x, D, k) là tập con chỉ chứa các đối tượng thuộc lớp c của tập N(x, D, k). Khi đó tài liệu x sẽ được phân vào lớp c0 nếu: ( ) * ( ) ∈ + Phương pháp K người láng giềng gần nhất là một phương pháp đơn giản. Tuy nhiên, thuật toán này ổn định và sai sót thấp khi số văn bản trong tập văn bản láng giềng phải lớn. c) Mô tả thuật toán - Xác định giá trị tham số K (số láng giềng gần nhất). - Tính khoảng cách giữa đối tượng cần phân lớp với tất cả các đối tượng trong training data (thường sử dụng khoảng cách Euclide, Cosine). - Sắp xếp khoảng cách theo thứ tự tăng dần và xác định k láng giềng gần nhất với đối tượng cần phần lớp. - Lấy tất cả các lớp của k láng giềng gần nhất đã xác định. Dựa vào phần lớn lớp của láng giềng gần nhất để xác định lớp cho đối tượng d) Áp dụng cho bài toán phân loại câu hỏi Ý tưởng: Khi cần phân loại một câu hỏi mới, thuật toán sẽ tính khoảng cách (khoảng cách Euclide, Cosine) của tất cả các câu hỏi trong tập huấn luyện đến câu hỏi này để tìm ra k câu hỏi gần nhất (gọi là k “láng giềng”), sau đó dùng các khoảng cách này đánh trọng số cho tất cả chủ đề. Trọng số của một chủ đề chính là tổng tất cả các câu hỏi trong k láng giềng có cùng chủ đề, chủ đề nào không xuất hiện trong k láng giềng sẽ có trọng số bằng 0. Sau đó các chủ đề sẽ được sắp xếp theo mức độ giảm dần và các chủ đề có trọng số cao sẽ được chọn là chủ đề của câu hỏi cần phân loại. ĐỒ ÁN TỐT NGHIỆP Chương 2: Hệ thống phân loại câu hỏi tiếng Việt GVHD: TS. Ngô Xuân Bách 24 SVTH: Nguyễn Đình Nghị – D11CNPM3 Khoảng cách giữa 2 văn bản chính là độ tương tự giữa 2 văn bản đó, 2 văn bản có giá trị độ tương tự càng lớn thì khoảng cách càng gần nhau. Ví dụ: Dùng công thức Cosine để tính độ tương tự giữa 2 văn bản: ( ) ( ) ‖ ‖ ‖ ‖ Văn bản A: Tôi là học sinh. Văn Bản B: Tôi là sinh viên. Văn bản C: Tôi là giáo viên. Biểu diễn văn bản theo vector: Tôi là học sinh viên giáo Văn bản A 1 1 1 1 0 0 Văn bản B 1 1 0 1 1 0 Văn bản C 1 1 0 0 1 1 Vector A = (1,1,1,1,0,0) Vector B = (1,1,0,1,1,0) Vector C = (1,1,0,0,1,1) ( ⃑ ) ( ⃑ ) √ ( ) ( ) √ Điều đó cho thấy văn bản A tương tự văn bản B hơn so với C. Hướng dẫn cài đặt: Thông thường các thuật toán sẽ gồm 2 giai đoạn huấn luyện và phân lớp, riêng đối với thuật toán KNN do thuật toán này không cần tạo ra mô hình khi làm trên tập huấn luyện các văn bản đã có nhãn/lớp sẵn, nên không cần giai đoạn huấn luyện (giai đoạn huấn luyện của KNN là gán nhãn cho các văn bản trong tập huấn luyện bằng cách gom nhóm các văn bản có vector đặc trưng giống nhau thành cùng 1 nhóm). Mô tả vector đặc trưng của văn bản: là vector có số chiều là số đặc trưng trong toàn tập dữ liệu, các đặc trưng này đôi một khác nhau. Nếu văn bản có chứa đặc trưng đó sẽ có giá trị 1, ngược lại là 0. Đầu vào: - Vector đặc trưng của văn bản cần phân lớp. - Các vector đặc trưng của văn bản trong tập huấn luyện (Ma trận MxN, với M là số vector đặc trưng trong tập huấn luyện, N là số đặc trưng của vector). - Tập nhãn/lớp cho từng vector đặc trưng của tập huấn luyện. Đầu ra: ĐỒ ÁN TỐT NGHIỆP Chương 2: Hệ thống phân loại câu hỏi tiếng Việt GVHD: TS. Ngô Xuân Bách 25 SVTH: Nguyễn Đình Nghị – D11CNPM3 - Nhãn/lớp của văn bản cần phân loại. Quá trình phân lớp gồm các bước sau: - Xác định giá trị tham số K (số láng giềng gần nhất). Tùy vào mỗi tập huấn luyện (số lượng mẫu trong tập huấn luyện, không gian tập mẫu có phủ hết các trường hợp) mà việc chọn số K sẽ ảnh hưởng đến kết quả phân lớp. - Lần lượt duyệt qua các văn bản (được đại diện bằng vector đặc trưng của văn bản) trong tập huấn luyện và tính độ tương tự của văn bản đó với văn bản cần phân lớp. - Sau khi đã có mảng các giá trị lưu độ tương tự của văn bản cần phân lớp với các văn bản trong tập huấn luyện, ta sắp xếp độ tương tự các văn bản theo thứ tự giảm dần (lưu ý đây là độ tương tự, độ tương tự càng lớn tức là khoảng cách càng gần) và lấy ra k văn bản đầu tiên trong mảng (tức là k văn bản gần với văn bản cần phân lớp nhất). - Khởi tạo mảng A có độ dài bằng số phân lớp để lưu số văn bản của mỗi lớp. Duyệt qua k văn bản, đếm số văn bản trong từng phân lớp và lưu vào mảng. - Duyệt qua mảng A, tìm lớp có số văn bản nhiều nhất và chọn là lớp cho văn bản mới. ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 26 SVTH: Nguyễn Đình Nghị – D11CNPM3 CHƢƠNG 3: THỰC NGHIỆM VÀ ĐÁNH GIÁ Sau khi tìm hiểu các phương pháp giải quyết bài toán, trong chương 3, đồ án trình bày chi tiết thực nghiệm gồm có quá trình thu thập và xử lý dữ liệu, các phương pháp làm thực nghiệm, kết quả và đánh giá. 3.1 Dữ liệu thực nghiệm 3.1.1 Chuẩn bị dữ liệu Dữ liệu chuẩn bị cho thực nghiệm gồm 3000 câu hỏi tiếng Việt thuộc 22 loại khác nhau được thu thập từ địa chỉ web: Mỗi câu hỏi có dạng: . 3000 câu hỏi được lưu vào file có tên “questions.txt”. Hình 3-1: File questions.txt. Bảng 3-1: Số lượng câu hỏi của mỗi nhãn. STT Nhãn tiếng Anh Nhãn tiếng Việt Số câu hỏi 1 Location Địa điểm 420 2 Count Số lượng 265 3 Manner Cách thức 266 4 Description Mô tả 266 5 Reason Lý do 190 6 Food Món ăn 103 7 Sport Thể thao 62 8 Definition Định nghĩa 266 9 Animal Động vật 112 ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 27 SVTH: Nguyễn Đình Nghị – D11CNPM3 10 Human Người 268 11 Money Tiền bạc 71 12 Event Sự kiện 56 13 Date Ngày tháng 218 14 Period Giai đoạn 75 15 Vehicle Xe cộ 27 16 Product Sản phẩm 42 17 Termeq Thuật ngữ 93 18 Substance Vật chất 41 19 ABBR Viết tắt 72 20 Color Màu sắc 40 21 Distance Khoảng cách 34 22 Plant Cây cối 13 *** Total 3000 3.1.2 Tiền xử lý dữ liệu Trước khi xử lý dữ liệu ta thực hiện tách riêng nhãn phân loại của 3000 câu hỏi và lưu vào tệp labels.txt, và tệp questions.txt lúc này chỉ còn chứa 3000 câu hỏi mà không chứa nhãn phân loại. Hình 3-2: File labels.txt. ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 28 SVTH: Nguyễn Đình Nghị – D11CNPM3 a) Tách từ Trong đồ án, chúng tôi sử dụng công cụ tách từ tiếng Việt là vnTokenizer [19]. Chương trình chạy dưới dạng dòng lệnh: - vnTokenizer.sh nếu chạy trên các hệ điều hành Linux/Unix/Mac OS - vnTokenizer.bat nếu chạy trên các hệ điều hành MS Windows Yêu cầu máy cần cài JRE (Java Runtime Enviroment) phiên bản 1.6 Câu lệnh tách từ cho một tệp trên hệ điều hành MS Windows như sau: vnTokenizer.bat -i -o [] Hai tùy chọn -i và -o là bắt buộc. Ngoài ra, người dùng có thể cung cấp các tùy chọn không bắt buộc sau đây: +) -xo: dùng định dạng XML để biểu diễn kết quả thay vì định dạng mặc định là văn bản thô. +) -nu: không sử dụng dấu gạch dưới khi ghi kết quả. Nếu tùy chọn này được sử dụng thì trong kết quả, các âm tiết không được nối với nhau bằng ký tự gạch dưới, mà bằng ký tự trắng. +) -sd: sử dụng mô-đun tách câu trước khi thực hiện tách từ. Nếu tùy chọn này được sử dụng thì trước tiên vnTokenizer thực hiện tách văn bản input thành một tập các câu, sau đó thực hiện tách từ từng câu một. Các tùy chọn này có thể được phối hợp đồng thời với nhau để cho ra kết quả mong muốn. Khi thực nghiệm, chúng tôi chỉ sử dụng hai tùy chọn -i và –o và kết quả tách từ được lưu vào tệp “questions.tok” như sau: Hình 3-3: File questions.tok. ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 29 SVTH: Nguyễn Đình Nghị – D11CNPM3 b) Gán nhãn từ Để thực hiện việc gán nhãn từ loại, chúng tôi sử dụng công cụ gán nhãn từ tiếng Việt là vnTagger [20]. Chương trình chạy dưới dạng dòng lệnh: -vnTagger.sh nếu chạy trên các hệ điều hành Linux/Unix/Mac OS -vnTagger.bat nếu chạy trên các hệ điều hành MS Windows Yêu cầu máy cần cài JRE (Java Runtime Enviroment) phiên bản 1.6 Câu lệnh gán nhãn từ cho một tệp trên hệ điều hành MS Windows như sau: vnTagger.bat -i -o [] Hai tùy chọn -i và -o là bắt buộc. Ngoài ra, người dùng có thể cung cấp các tùy chọn không bắt buộc sau đây: +) –u: thêm gạch dưới giữa các âm tiết của một từ +) –p: không dùng định dạng XML để biểu diễn kết quả Các tùy chọn này có thể được phối hợp đồng thời với nhau để cho ra kết quả mong muốn. Khi thực nghiệm, ngoài sử dụng hai tùy chọn -i và –o, chúng tôi còn sử dụng cả hai tùy chọn –u và –p và kết quả gán nhãn từ được lưu vào tệp “questions.tagger” như sau: Hình 3-4: File questions.tagger. Sau khi gán nhãn từ loại, chúng tôi thực hiện trích rút nhãn từ loại và lưu vào tệp “questions.pos”. ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 30 SVTH: Nguyễn Đình Nghị – D11CNPM3 Hình 3-5: File questions.pos. c) Biểu diễn cây cú pháp Để xây dựng cây cú pháp cho câu hỏi, chúng tôi sử dụng công cụ VnDP toolkit [23]. VnDP toolkit là bộ công cụ phân tích cú pháp phụ thuộc tiếng Việt, tích hợp bộ phân tích cú pháp MSTParser và bộ gán nhãn từ RDRPOSTagger. Công cụ được viết bằng ngôn ngữ java: Đầu vào: tệp dữ liệu đã được tách từ Đầu ra: - Tệp .TAGGED biểu diễn kết quả gán nhãn từ - Tệp .DEP.CONLL biểu diễn các câu dưới dạng cây cú pháp ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 31 SVTH: Nguyễn Đình Nghị – D11CNPM3 Hình 3-6: File questions.DEP.CONLL. Sau khi đã biểu diễn các câu dưới dạng cây cú pháp, chúng tôi thực hiện trích rút cây cú pháp, lấy các từ gốc là các từ có nhãn là root, lưu vào tệp “questions.root” với định dạng: root=”” và các từ con của từ gốc, lưu vào tệp “questions.child” với định dạng: child=”” Hình 3-7: File questions.root. ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 32 SVTH: Nguyễn Đình Nghị – D11CNPM3 Hình 3-8: File questions.child. 3.2 Thiết lập thực nghiệm 3.2.1 Thực nghiệm với 3000 câu hỏi a. SVM Trong thực nghiệm với thuật toán SVM, chúng tôi sử dụng công cụ libsvm để phân loại câu hỏi cho thuật toán với các đặc trưng từ vựng, âm tiết, n-gram, nhãn từ loại và cây cú pháp.  Bước 1: Xây dựng từ điển Sử dụng tệp “questions.txt” xây dựng ba bộ từ điển chứa các đặc trưng âm tiết được biểu diễn theo 1 gram, 1+2 grams và 1+2+3 grams. Sử dụng tệp “questions.tok” xây dựng ba bộ từ điển chứa các đặc trưng từ vựng được biểu diễn theo 1 gram, 1+2 grams và 1+2+3 grams. Các từ điển có định dạng: : Hình 3-9: File từ điển.  Bước 2: Chuyển đồi định dạng libsvm Dựa vào sáu bộ từ điển đã xây dựng, chuyển đổi định dạng hai tệp “questions.txt” và “questions.tok” về đúng định dạng của libsvm: : : ... Trong đó: ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 33 SVTH: Nguyễn Đình Nghị – D11CNPM3 - là nhãn phân loại, giá trị đích của tập huấn luyện. Đối với việc phân lớp, nó là một số nguyên xác định một lớp. Đối với hồi qui, nó là một số thực bất kỳ. - là một số nguyên bắt đầu từ 1, trong trường hợp này nó là vị trí của âm tiết hoặc từ vựng trong từ điển. - là số lần xuất hiện của âm tiết hoặc từ vựng trong câu. Mỗi tệp được chuyển về định dạng của libsvm theo 3 kiểu: 1 gram, 1+2 grams, và 1+2+3 grams. Hình 3-10: Định dạng dữ liệu cho libsvm. Như vậy, sau khi chuyển đổi định dạng sẽ có 6 tệp: Bảng 3-2: Các tệp sau khi chuyển đổi Dữ liệu gốc Tệp chuyển đổi questions.txt (âm tiết) Âm tiết 1 gram Âm tiết 1+2 grams Âm tiết 1+2+3 grams questions.tok (từ vựng) Từ vựng 1 gram Từ vựng 1+2 grams Từ vựng 1+2+3 grams  Bước 3: Tạo các bộ dữ liệu thực nghiệm Chia ngẫu nhiên mỗi tệp làm 5 phần, mỗi phần gồm 600 câu, gọi 5 phần đó lần lượt là set1, set2, set3, set4, set5. Sử dụng 4 phần (2400 câu) để tiến hành huấn luyện, và 1 phần còn lại (600 câu) để kiểm tra và việc này sẽ được thực hiện 5 lần. Sau tiến hành 5 lần như trên kết quả cuối cùng sẽ được tính bằng trung bình cộng của 5 kết quả của 5 lần tương ứng. - Lần 1: tập train gồm phần 2+3+4+5 còn tập test sẽ là phần 1. - Lần 2: tập train gồm phần 1+3+4+5 còn tập test sẽ là phần 2. ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 34 SVTH: Nguyễn Đình Nghị – D11CNPM3 - Lần 3: tập train gồm phần 1+2+4+5 còn tập test sẽ là phần 3. - Lần 4: tập train gồm phần 1+2+3+5 còn tập test sẽ là phần 4. - Lần 5: tập train gồm phần 1+2+3+4 còn tập test sẽ là phần 5. Như vậy, mỗi tệp sẽ có 5 thực nghiệm khác nhau, do có 6 tệp nên tổng cộng số thực nghiệm cần phải thực hiện là 30 thực nghiệm.  Bước 4: Chạy thực nghiệm với công cụ libsvm Một tập thực nghiệm sẽ có hai tệp, một tệp train và một tệp test, tên của chúng là trainN.txt và testN.txt (N=1,2,3,4,5). Mở command window để gõ lệnh, chuyển đường dẫn lệnh về thư mục chứa svm-scale.exe: - Scale tệp train: svm-scale –l 0 –u 1 –s rangeN trainN.txt > trainN.scale. - Scale tệp test: svm-scale –r rangeN testN.txt > testN.scale. - Chọn tham số C và gamma: thay đổi đường dẫn lệnh về thư mục chứa grid.py, gõ lệnh python grid.py trainN.scale. - Thay đổi đường dẫn lệnh về thư mục chứa svm-train.exe và svm-predict.exe. - Huấn luyện dữ liệu: svm-train –c –g -b 1 trainN.scale. - Dự đoán: svm-predict –b 1 testN.scale trainN.scale.model testN.predict .  Bước 5: Bổ sung đặc trưng nhãn từ loại và cây cú pháp Sau khi có được kết quả của tất cả các trường hợp, tính giá trị trung bình của 5 thực nghiệm cho mỗi tệp. Lựa chọn bộ dữ liệu thực nghiệm mà cho kết quả dự đoán tốt nhất để bổ sung thêm các đặc trưng nhãn từ loại và cây cú pháp. Sau đó tiến hành chạy lại thực nghiệm với công cụ libsvm. b. Các thuật toán khác Sau khi sử dụng libsvm tiến hành thực nghiệm với các đặc trưng khác nhau, chúng tôi sử dụng bộ dữ liệu đạt được kết quả tốt nhất để áp dụng các thuật toán Naïve Bayes, K-láng giềng gần nhất bằng cách sử dụng công cụ Weka [22]. ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 35 SVTH: Nguyễn Đình Nghị – D11CNPM3 Hình 3-11: Giao diện màn hình chính của Weka. Để có thể sử dụng công cụ Weka, chúng ta cần chuyển đổi định dạng dữ liệu về đúng dạng ARFF, CSV, C4.5, hoặc binary. Trong đồ án, chúng tôi chuyển định dạng dữ liệu về dạng file ARFF. Định dạng dữ liệu (ARFF): - Phần khai báo @ralation @attribute @attribute - Các kiểu dữ liệu: Numeric: dữ liệu dạng số Ví dụ: @ATTRIBUTE name numeric Nominal: dữ liệu rời rạc Ví dụ: @ATTRIBUTE class {sport, count} String: dữ liệu chuỗi Ví dụ: @ATTRIBUTE name string Date Date: dữ liệu kiểu ngày Ví dụ: @ATTRIBUTE discovered date - Phần dữ liệu: Mỗi mẫu dữ liệu được đặt trên một dòng, giá trị của các thuộc tính được liệt kê theo thứ tự từ trái qua phải và ngăn cách bởi dấu phẩy. ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 36 SVTH: Nguyễn Đình Nghị – D11CNPM3 Hình 3-12: Định dạng dữ liệu file arrff. Sau khi chuyển đổi định dạng dữ liệu, chúng tôi tiến hành làm thực nghiệm sử dụng Weka với các thuật toán Naïve Bayes và K-láng giềng gần nhất. c. Cách thức đánh giá Sau khi đã thực nghiệm xong, việc tiếp theo là cần phải đánh giá xem kết quả thực nghiệm có tốt không. Để đánh giá kết quả phân loại câu hỏi, ta sử dụng một số chỉ số đánh giá:  Recall: độ chính xác của dự đoán cho từng nhãn Recall =  Precision: độ chính xác của mỗi lần dự đoán Precision = Từ thực nghiệm chúng ta có 3 giá trị: Human, Model, Match Trong đó: - Human: Số câu hỏi thực tế - Model: Số câu hỏi mà máy dự đoán - Match: Số câu hỏi được máy dự đoán đúng Chúng ta có công thức: ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 37 SVTH: Nguyễn Đình Nghị – D11CNPM3 Rec = = Prec = =  F1 Tiêu chí đánh giá F1 là sự kết hợp của 2 tiêu chí đánh giá Precision và Recall F1 = F1 là một giá trị trung bình điều hòa của các tiêu chí Precision và Recall - F1 có xu hướng lấy giá trị gần với giá trị nào nhỏ hơn giữa 2 giá trị Precision và Recall - F1 có giá trị lớn nếu cả 2 giá trị Precision và Recall đều lớn d. Kết quả  Kết quả chạy SVM cho đặc trưng từ vựng, âm tiết và n-grams: Bảng 3-3: Kết quả thực nghiệm SVM sử dụng n-grams, âm tiết và từ vựng Đặc trƣng n-grams Lần 1 (%) Lần 2 (%) Lần 3 (%) Lần 4 (%) Lần 5 (%) TB (%) Từ vựng 1gram 84.50 85.00 82.83 84.00 83.83 84.03 1+2grams 82.83 85.50 81.83 83.00 83.17 83.27 1+2+3grams 83.17 83.83 82.00 81.67 82.67 82.67 Âm tiết 1gram 83.00 83.83 83.33 81.83 81.50 82.70 1+2grams 84.83 87.67 84.67 84.00 85.33 85.30 1+2+3grams 84.17 87.00 83.83 82.50 84.83 84.47 Bảng 3-4: Kết quả phân lớp cho mỗi nhãn (âm tiết 1+2grams) STT Nhãn Human Model Match Precision (%) Recall (%) F1(%) 1 Location 420 434 370 85.25 88.10 86.65 2 Count 265 281 251 89.32 94.72 91.94 3 Manner 266 285 259 90.88 97.37 94.01 4 Description 266 297 219 73.74 82.33 77.80 5 Reason 190 183 176 96.17 92.63 94.37 6 Food 103 90 74 82.22 71.84 76.68 7 Sport 62 58 48 82.76 77.42 80.00 8 Definition 266 289 241 83.39 90.60 86.85 ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 38 SVTH: Nguyễn Đình Nghị – D11CNPM3 9 Animal 112 99 95 95.96 84.82 90.05 10 Human 268 278 218 78.42 81.34 79.85 11 Money 71 64 58 90.63 81.69 85.93 12 Event 56 51 29 56.86 51.79 54.21 13 Date 218 211 195 92.42 89.45 90.91 14 Period 75 67 64 95.52 85.33 90.14 15 Vehicle 27 21 13 61.90 48.15 54.17 16 Product 42 42 29 69.05 69.05 69.05 17 Termeq 93 83 71 85.54 76.34 80.68 18 Substance 41 31 30 96.77 73.17 83.33 19 ABBR 72 62 52 83.87 72.22 77.61 20 Color 40 36 34 94.44 85.00 89.47 21 Distance 34 28 25 89.29 73.53 80.65 22 Plant 13 10 8 80.00 61.54 69.57 *** Total 3000 3000 2559 84.29 78.56 81.09 Recall là tiêu chí đánh giá dựa trên số lần mỗi nhãn được đoán đúng. Tuy nhiên, mỗi một nhãn sẽ được dự đoán một số lần nào đó, và số lượng này có thể lớn hơn hoặc nhỏ hơn số lượng thực tế. Nếu như một nhãn được dự đoán nhiều lần hơn số lượng thực tế thì số lần dự đoán đúng cũng sẽ tăng lên. Vì vậy nếu số câu hỏi được dự đoán đúng tăng lên mà số lần dự đoán cũng tăng lên thì hiệu suất của thuật toán không thực sự tốt. Cho nên chúng tôi sử dụng thêm tiêu chí Precision. Tiêu chí này ngoài việc quan tâm tới số lần dự đoán đúng, nó còn quan tâm tới số lần mà mỗi nhãn được dự đoán. Tuy nhiên cả hai tiêu chí này vẫn chưa thể hiện được hiệu suất dự đoán. Để giải quyết vấn đề đó, chúng tôi sử dụng tiêu chí F1 là một sự kết hợp hài hòa của hai tiêu chí Recall và Precision: F1 = . ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 39 SVTH: Nguyễn Đình Nghị – D11CNPM3 Hình 3-13: So sánh độ chính xác giữa đặc trưng âm tiết và đặc trưng từ vựng. Kết quả thực nghiệm cho thấy việc sử dụng đặc trưng âm tiết đạt hiệu quả cao hơn đặc trưng từ vựng. Nguyên nhân có thể là do trong một câu thì số lượng âm tiết sẽ nhiều hơn số lượng từ vựng, do đó số đặc trưng âm tiết nhiều hơn sẽ giúp việc dự đoán được tốt hơn. Kết quả cao nhất đạt được là 85.30% khi sử dụng đặc trưng âm tiết 1+2 grams. Vì vậy, bộ dữ liệu đặc trưng âm tiết 1+2grams sẽ được sử dụng để bổ sung thêm các đặc trưng khác. Hình 3-14: Độ chính xác cho mỗi nhãn (âm tiết 1+2 grams). Dựa vào bảng 3-4 và hình 3-14 ta thấy có 11 nhãn đạt được độ chính xác khá tốt, cao hơn độ chính xác trung bình đó là các nhãn Location, Count, Manner, Reason, Definition, Animal, Money, Date, Period, Substance và Color. Các nhãn này có giá trị 84.03 83.27 82.67 82.7 85.3 84.47 81 81.5 82 82.5 83 83.5 84 84.5 85 85.5 1 gram 1+2 grams 1+2+3 grams Từ vựng Âm tiết 0 10 20 30 40 50 60 70 80 90 100 Lo ca ti o n C o u n t M an n er D es cr ip ti o n R ea so n Fo o d Sp o rt D ef in it io n A n im al H u m an M o n ey Ev en t D at e P er io d V eh ic le P ro d u ct Te rm eq Su b st an ce A B B R C o lo r D is ta n ce P la n t To ta l F1 ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 40 SVTH: Nguyễn Đình Nghị – D11CNPM3 F1, precision và recall đều cao hơn giá trị trung bình của tất cả các nhãn và sự chênh lệch giữa precision và recall là không lớn. Trong khi ở các nhãn có giá trị F1 nhỏ hơn giá trị trung bình thì các giá trị precision và recall thường có chênh lệch khá lớn.  Kết quả thực nghiệm SVM khi bổ sung các đặc trưng: Bảng 3-5: Kết quả thực nghiệm khi bổ sung thêm các đặc trưng Bảng 3-6: Kết quả phân lớp cho mỗi nhãn (âm tiết 1+2grams + nhãn từ loại + root) STT Nhãn Human Model Match Precision (%) Recall (%) F1(%) 1 Location 420 423 365 86.29 86.90 86.59 2 Count 265 279 253 90.68 95.47 93.01 3 Manner 266 281 258 91.81 96.99 94.33 4 Description 266 303 220 72.61 82.71 77.33 5 Reason 190 184 175 95.11 92.11 93.59 6 Food 103 91 71 78.02 68.93 73.19 7 Sport 62 58 48 82.76 77.42 80.00 8 Definition 266 288 245 85.07 92.11 88.45 9 Animal 112 101 94 93.07 83.93 88.26 10 Human 268 279 222 79.57 82.84 81.17 11 Money 71 66 61 92.42 85.92 89.05 12 Event 56 50 30 60.00 53.57 56.60 13 Date 218 210 194 92.38 88.99 90.65 14 Period 75 67 65 97.01 86.67 91.55 15 Vehicle 27 19 12 63.16 44.44 52.17 16 Product 42 46 30 65.22 71.43 68.18 17 Termeq 93 83 71 85.54 76.34 80.68 Các đặc trƣng Độ chính xác Âm tiết 1+2 grams 85.30% Âm tiết 1+2 grams + nhãn từ loại 85.37% (+0.07%) Âm tiết 1+2 grams + nhãn từ loại + root 85.53% (+0.23%) Âm tiết 1+2 grams + nhãn từ loại + root + child 85.40% (+0.10%) ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 41 SVTH: Nguyễn Đình Nghị – D11CNPM3 18 Substance 41 31 29 93.55 70.73 80.56 19 ABBR 72 65 55 84.62 76.39 80.29 20 Color 40 37 35 94.59 87.50 90.91 21 Distance 34 29 25 86.21 73.53 79.37 22 Plant 13 10 8 80.00 61.54 69.57 *** Total 3000 3000 2566 84.08 78.93 81.16 Hình 3-15: So sánh độ chính xác giữa các đặc trưng. Kết quả tốt nhất của tất cả các thực nghiệm là 85.53% khi sử dụng thuật toán SVM kết hợp các đặc trưng âm tiết 1+2grams, nhãn từ loại và đặc trưng root của cây cú pháp. Độ chính xác giữa các thực nghiệm là không quá lớn, sự chênh lệch lớn nhất là 85.53% – 85.3% = 0.23%. Do đó, độ chênh lệch chỉ số F1 cũng không quá lớn: 81.16% – 81.09% = 0.07%.  Kết quả thực nghiệm với các thuật toán khác Bảng 3-7: Kết quả thực nghiệm của các thuật toán khác nhau Thuật toán Độ chính xác SVM 85.53% Naïve Bayes 77.56% K láng giềng gần nhất (k=1) 70.83% K láng giềng gần nhất (k=5) 66.60% 85.15 85.2 85.25 85.3 85.35 85.4 85.45 85.5 85.55 âm tiết 1+2grams âm tiết 1+2grams + nhãn từ loại âm tiết 1+2grams + nhãn từ loại + root âm tiết 1+2grams + nhãn từ loại + root + child Độ chính xác giữa các đặc trƣng ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 42 SVTH: Nguyễn Đình Nghị – D11CNPM3 Kết quả thực nghiệm cho thấy thuật toán SVM là lựa chọn tốt nhất cho bài toán phân loại câu hỏi. Độ chính xác có sự chênh lệch khá lớn giữa thuật toán SVM và các thuật toán khác. Chênh lệch lớn nhất là giữa thuật toán SVM và thuật toán K-láng giềng gần nhất ( ), độ chênh lệch là 85.53% - 66.60% = 18.93%. 3.2.2 Thực nghiệm bổ sung câu truy vấn a. Phƣơng pháp thực nghiệm Hình 3-16: Phương pháp thực nghiệm bổ sung câu truy vấn Trong thực nghiệm bổ sung câu truy vấn, các câu hỏi trong bộ dữ liệu ban đầu sẽ được đưa vào các hệ thống máy tìm kiếm và lấy ra các kết quả truy vấn. Sau đó các câu truy vấn sẽ được bổ sung vào tập các câu hỏi ban đầu với mục đích tăng kích thước dữ liệu huấn luyện. Khi kích thước dữ liệu huấn luyện tăng lên, chúng tôi hi vọng sẽ có thêm nhiều thông tin cho quá trình huấn luyện, từ đó sẽ xây dựng được một mô hình huấn luyện tốt hơn, góp phần cải thiện kết quả phân loại. Sau khi bổ sung các kết quả truy vấn, chúng tôi tiến hành trích xuất các đặc trưng và áp dụng các thuật toán học máy thống kê để tiến hành làm thực nghiệm. b. Dữ liệu thực nghiệm Với bộ dữ liệu 3000 câu hỏi ban đầu, chúng tôi đưa từng câu hỏi vào máy tìm kiếm Google, tiến hành thu thập 5 kết quả đầu tiên được máy tìm kiếm trả về, lưu kết quả vào tệp “question_and_query.txt”, mỗi dòng trong tệp có dạng: tab tab Question Máy tìm kiếm Kết quả truy vấn Huấn luyện ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 43 SVTH: Nguyễn Đình Nghị – D11CNPM3 Hình 3-17: File question_and_query.txt. c. Thiết lập thực nghiệm Trong thực nghiệm bổ cung các câu truy vấn, chúng tôi chỉ tiến hành thực nghiệm sử dụng thuật toán SVM với bộ dữ liệu có kết quả tốt nhất của thực nghiệm 3000 câu hỏi trên các đặc trưng từ vựng, âm tiết và n-grasm. Do thực nghiệm với âm tiết 1+2grams đạt kết quả tốt nhất nên các câu truy vấn sẽ được bổ sung vào bộ dữ liệu âm tiết 1+2grams. - Các âm tiết trong các câu truy vấn sẽ được bổ sung vào từ điển 1+2grams, mỗi âm tiết được viết thêm kí tự “q_” vào phía trước để phân biệt với các âm tiết trong câu hỏi. - Chuyển đổi định dạng các câu truy vấn về định dạng libsvm. - Bổ sung các câu truy vấn đã được chuyển đổi định dạng vào các tệp train và test của bộ dữ liệu âm tiết 1+2grams sao cho đúng thứ tự câu. - Chạy thực nghiệm với công cụ libsvm cho bộ dữ liệu. d. Kết quả thực nghiệm Bảng 3-8: Kết quả thực nghiệm bổ sung câu truy vấn Đặc trƣng Lần 1 (%) Lần 2 (%) Lần 3 (%) Lần 4 (%) Lần 5 (%) TB (%) Âm tiết 1+2grams 84.83 87.67 84.67 84.00 85.33 85.30 Âm tiết 1+2grams + câu truy vấn 80.67 82.50 81.83 79.50 81.33 81.17 (-4.13) Như vậy thực nghiệm với việc bổ sung các câu truy vấn không cho kết quả tốt hơn với việc chỉ sử dụng câu hỏi. Điều này cho thấy việc sử dụng thêm các câu truy vấn từ máy tìm kiếm google không phù hợp với bài toán phân loại câu hỏi. Các câu truy vấn đã tạo ra nhiễu, làm cho mô hình huấn luyện không đạt được kết quả tốt nhất. Ví dụ câu hỏi: Con vật nào được đặt chân đầu tiên vào không gian? ĐỒ ÁN TỐT NGHIỆP Chương 3: Thực nghiệm và đánh giá GVHD: TS. Ngô Xuân Bách 44 SVTH: Nguyễn Đình Nghị – D11CNPM3 5 kết quả tìm kiếm từ google:  Chạy đua vào không gian – Wikipedia tiếng Việt  Người đầu tiên đặt chân lên mặt trăng - Các bài viết - KhoaHoc.TV  Động vật đầu tiên bay vào không gian - Các bài viết  Ký ức của người đầu tiên đi bộ ngoài không gian - VnExpress  Chân Không Vật Chất - Nơi Vật Chất Tạo Nên Không Gian (Michel ... Câu hỏi có nhãn là Động vật, nhưng trong 5 kết quả tìm kiếm được trả về từ máy tìm kiếm google lại cho ra 4 kết quả không liên quan tới động vật, mà chỉ có một kết quả liên quan tới động vật là câu: Động vật đầu tiên bay vào không gian. Điều này đã tạo ra nhiễu cho mô hình huấn luyện, làm cho việc huấn luyện không chính xác, và do đó kết quả phân loại sẽ không được tốt. Yêu cầu đặt ra cần phải có thêm các nghiên cứu với các phương pháp khác để có thể cải thiện tốt hơn độ chính xác trong việc phân loại câu hỏi. ĐỒ ÁN TỐT NGHIỆP GVHD: TS. Ngô Xuân Bách 45 SVTH: Nguyễn Đình Nghị – D11CNPM3 KẾT LUẬN Phân loại câu hỏi tiếng Việt vẫn là một vấn đề còn khá mới, nhưng nó có ý nghĩa vô cùng quan trọng. Từ việc giải quyết bài toán phân loại câu hỏi tiếng Việt, giúp cho chúng ta tiến gần hơn việc có thể xây dựng được một hệ thống hỏi đáp dành riêng cho tiếng Việt, góp phần đem lại sự thuận tiện hơn cho người dùng trong việc thu thập và tìm kiếm thông tin tiếng Việt. Ngoài ra, chúng ta có thể dựa vào nghiên cứu này để phát triển trí tuệ nhân tạo cho robot, giúp chúng có thể hiểu và trả lời các câu hỏi tiếng Việt, từ đó có thể giải quyết được các công việc của con người, có thể làm việc dựa trên mệnh lệnh mà con người đưa ra. Nhìn chung, đồ án đã đạt được một số thành tựu như: - 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 bài toán phân loại câu hỏi tiếng Việt. - Khảo sát, nghiên cứu 5 loại đặc trưng tiếng Việt khác nhau cho bài toán phân loại câu hỏi tiếng Việt. - Nghiên cứu và làm thực nghiệm với 3 thuật toán học máy khác nhau. - So sánh và phân tích các kết quả thực nghiệm và chúng tôi đã tìm ra được trường hợp cho kết quả tốt nhất. - Từ kết quả thực nghiệm, chúng tôi xây dựng thành công một ứng dụng demo giúp phân loại câu hỏi dựa trên các đặc trưng khác nhau. Đồ án vẫn còn một số hạn chế như: - Nghiên cứu vẫn còn đơn giản. - Kết quả thực nghiệm đạt được vẫn chưa thực sự tốt so với những nghiên cứu trước đây. Đặc biệt với việc bổ sung các câu truy vấn đã làm cho kết quả thực nghiệm không những không tăng lên mà còn giảm đi. - Phần mềm demo vẫn còn hạn chế, tốc độ xử lý vẫn còn chậm, đặc biệt là khi dự đoán với đặc trưng nhãn từ loại và cây cú pháp. Về hướng phát triển tương lai, chúng tôi sẽ tiến hành phát triển một tập dữ liệu tiếng Việt lớn hơn và nghiên cứu sử dụng thêm nhiều đặc trưng tiếng Việt khác, góp phần cải thiện tốt hơn khả năng phân loại. Ngoài ra chúng tôi cũng sẽ nghiên cứu và thử nghiệm với một số thuật toán khác để tìm ra thuật toán phù hợp nhất với bài toán phân loại câu hỏi tiếng Việt. ĐỒ ÁN TỐT NGHIỆP GVHD: TS. Ngô Xuân Bách 46 SVTH: Nguyễn Đình Nghị – D11CNPM3 PHỤ LỤC A. Công cụ sử dụng Bảng A-1: Các công cụ sử dụng Công cụ Trang chủ Java SE JDK 7u21 Netbean 8.0.1 https://netbeans.org/ Notepad++ vnTokenizer vnTagger VnDP: A Vietnamese dependency parsing toolkit libSVM https://www.csie.ntu.edu.tw/~cjlin/libsvm/ Weka B. Chƣơng trình demo Phần này trình bày hệ thống phân loại câu hỏi của chúng tôi. Hệ thống nhận đầu vào là câu hỏi của người dùng dưới dạng ngôn ngữ tự nhiên và trả về nhãn phân loại cho từng câu hỏi của người dùng. Người dùng có thể nhập câu hỏi theo 2 cách: - Cách 1: Nhập bằng tay, người dùng tự gõ câu hỏi vào ô question - Cách 2: Nhập bằng file, người dùng tự gõ đường dẫn file hoặc duyệt đến file chứa câu hỏi và click nút import để nhập tất cả câu hỏi trong file vào ô question. ĐỒ ÁN TỐT NGHIỆP GVHD: TS. Ngô Xuân Bách 47 SVTH: Nguyễn Đình Nghị – D11CNPM3 Hình B-1: Giao diện nhập câu hỏi bằng tay. Hình B-2: Giao diện nhập câu hỏi bằng file. Sau khi nhập câu hỏi, người dùng có thể lựa chọn một trong ba tùy chọn trích xuất đặc trưng: - Syllables: chỉ sử dụng âm tiết của câu hỏi - Syllables and pos: sử dụng âm tiết của câu hỏi và nhãn từ loại - Syllables and pos and dependency: sử dụng âm tiết của câu hỏi, nhãn từ loại và đặc trưng cú pháp của câu. Bước tiếp theo người dùng click vào nút predict và chờ đợi, hệ thống sẽ xử lý câu hỏi, trích xuất đặc trưng và đưa ra nhãn dự đoán cho câu hỏi đó trong ô Label. ĐỒ ÁN TỐT NGHIỆP GVHD: TS. Ngô Xuân Bách 48 SVTH: Nguyễn Đình Nghị – D11CNPM3 Sau khi chương trình thực hiện xong, người dùng có thể click vào nút Clear để xóa dữ liệu trong hai ô Question và ô Label và tiếp tục chương trình với các câu hỏi mới. Hình B-3: Giao diện chạy chương trình. ĐỒ ÁN TỐT NGHIỆP GVHD: TS. Ngô Xuân Bách 49 SVTH: Nguyễn Đình Nghị – D11CNPM3 TÀI LIỆU THAM KHẢO Tài liệu tiếng Anh [1] I. Fahmi (2009). Automatic term and relation extraction for medical question answering system. PhD Thesis, the University of Groningen, The Netherlands. [2] Phuong Le-Hong, Xuan-Hieu Pham and Tien-Dung Nguyen, Using dependency analysis to improve question classification, Knowledge and Systems Enginneering, Springer International Publishing, 2015, pages 653-655. [3] Zhiheng Huang, Marcus Thint and Zengchang Qin, Question Classification using Head Words and their Hypernyms, Proceedings of the 2008 Conference on Empirical Methods in Natural Languae Processing, pages 927-936, Honolulu, October 2008. [4] Boris Katz. Annotating the World Wide Web Using Natural Language. Proceedings of the 5th RIAO Conference on Computer Assisted Information Searching on the Internet (RIAO '97), 1997, pages 136-139. [5] Deepak Ravichandran, Abraham Ittycheriah, and Salim Roukos. 2003. Automatic derivation of surface text patterns for a maximum entropy based question answering system. In Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology: companion volume of the Proceedings of HLT-NAACL 2003--short papers - Volume 2 (NAACL-Short '03), Vol. 2. Association for Computational Linguistics, Stroudsburg, PA, USA, 85-87. [6] Hakan Sundblad, Question Classification in Question Answering Systems, Linkuping Studies in Science and Technology, June 2007, ISBN 978-91-85831- 55-5. [7] Dang Hai Tran, Cuong Xuan Chu, Son Bao Pham and Minh Le Nguyen, Learning Based Approaches for Vietnamese Question Classification Using Keywords Extraction from the Web, International Joint Conference on Natural Language Processing, pages 740-746, Nagoya, Japan, 14-18 October 2013. [8] Vu Mai Tran, Vinh Duc Nguyen, Oanh Thi Tran, Uyen Thu Thi Pham and Thuy-Quang Ha. An Experimental Study of Vietnamese Question Answering System. International Conference on Asian Language Processing, {IALP} 2009, Singapore, December 7-9, 2009, pages 152-155. [9] Dell Zhang and Wee Sun Lee. 2003. Question classification using support vector machines. In Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval (SIGIR '03). ACM, New York, NY, USA, pages 26-32. ĐỒ ÁN TỐT NGHIỆP GVHD: TS. Ngô Xuân Bách 50 SVTH: Nguyễn Đình Nghị – D11CNPM3 Tài liệu tiếng Việt [10] Trần Cao Đệ, Phạm Nguyên Khang, Phân loại văn bản với máy học vector hỗ trợ và cây quyết định, Tạp chí Khoa học 2012:21a 52-63, Trường Đại học Cần Thơ. [11] Đỗ Bá Lâm, Lê Thanh Hương, Xây dựng hệ thống phân tích cú pháp tiếng Việt sử dụng văn phạm HPSG, Đại học Bách Khoa Hà Nội, 2008. ICT08- VLSP-SP85-2. [12] Hà Thị Minh Lộc, Xây dựng mô hình hệ thống hỏi đáp tự động hỗ trợ đào tạo trực tuyến, Luận văn thạc sĩ, Học viện Công nghệ Bưu chính Viễn thông, 2013. [13] Nguyễn Phương Thái, Vũ Xuân Lương, Nguyễn Thị Minh Huyền, Xây dựng treebank tiếng Việt, Viện Khoa học và Công nghệ Tiên tiến Nhật Bản, 07/2008. [14] Nguyễn Minh Thành, Phân loại văn bản, Đồ án môn học Xử lý ngôn ngữ tự nhiên, Đại học quốc gia Thành phố Hồ Chí Minh, 01/2011. [15] Nguyễn Đức Vinh, Phân tích câu hỏi trong hệ thống hỏi đáp tiếng Việt, Khóa luận tốt nghiệp đại học, Đại học quốc gia Hà Nội, 2009. Danh mục các Website tham khảo: [16] Google : https://www.google.com [17] Wikipedia: [18] Natural Language Processing: [19] Lê Hồng Phương, vnTokenizer - Vietnamese words segmentation , 2010. [20] Lê Hồng Phương, vnTagger - Vietnamese words segmentation , 2010. [21] [22] [23] [24] [25] [26] https://answers.yahoo.com/ [27] https://www.question.com/topic/google/