Tài liệu ứng dụng mạng bayes xây dựng hệ thống trắc nghiệm thích nghi

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA TRẦN THỊ TỐ LOAN ỨNG DỤNG MẠNG BAYES XÂY DỰNG HỆ THỐNG TRẮC NGHIỆM THÍCH NGHI LUẬN VĂN THẠC SĨ KỸ THUẬT Đà Nẵng - Năm 2017 1 ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA TRẦN THỊ TỐ LOAN ỨNG DỤNG MẠNG BAYES XÂY DỰNG HỆ THỐNG TRẮC NGHIỆM THÍCH NGHI Chuyên ngành: Khoa học máy tính Mã số: 60.48.01.01 LUẬN VĂN THẠC SĨ KỸ THUẬT Người hướng dẫn khoa học: TS. ĐẶNG HOÀI PHƯƠNG Đà Nẵng - Năm 2017 i LỜI CAM ĐOAN Tôi xin cam đoan đề tài “Ứng dụng mạng Bayes xây dựng hệ thống trắc nghiệm thích nghi” này là công trình nghiên cứu của riêng tôi dưới sự hướng dẫn của TS. Đặng Hoài Phương. Các nội dung nghiên cứu, kết quả trong đề tài này là trung thực. Tác giả Trần Thị Tố Loan ii TÓM TẮT LUẬN VĂN ỨNG DỤNG MẠNG BAYES XÂY DỰNG HỆ THỐNG TRẮC NGHIỆM THÍCH NGHI Trần Thị Tố Loan, học viên cao học khóa 31, chuyên ngành Khoa học máy tính, mã số: 60.48.01, trường Đại học Bách Khoa - Đại học Đà Nẵng Tóm tắt - Hệ thống trắc nghiệm thích nghi (TNTN) đã được nghiên cứu, hiện thực hóa và ứng dụng rộng rải nhờ tính chính xác và khách quan trong quá trình đánh giá năng lực, kiến thức của thí sinh. Tuy nhiên, những mô hình và hệ thống TNTN đã tồn tại vẫn còn một số nhược điểm nhất định. Nghiên cứu này được đề xuất nhằm khắc phục, mở rộng tính toán cho hệ thống TNTN có câu hỏi chứa nhiều tham số, chọn lựa câu hỏi phù hợp với mức độ kiến thức hiện tại của thí sinh. Luận văn đã khái quát về TNTN, giới thiệu các hệ thống TNTN đã tồn tại. Từ lý thuyết mạng Bayes, lý thuyết đáp ứng câu hỏi tác giả đã thiết kế và xây dựng hệ thống TNTN. Các phân tích đánh giá hệ thống cũng được giới thiệu trong luận văn. Tác giả đã tóm tắt các kết quả đạt được và đưa ra hướng phát triển tiếp theo. Từ khóa – Trắc nghiệm thích nghi; mạng Bayes; lý thuyết đáp ứng câu hỏi; thuật toán ước lượng năng lực. BAYESIAN NETWORK APPLICATIONS FOR BUILDING COMPUTERIZED ADAPTIVE TESTING SYSTEMS Abstract - Computerized Adaptive Testing (CAT) has been research, actualize and wide apply because of their accuracy and objective in process of testing ability and knowledge of the candidate. However existing CAT system model still have some limitation. This research was proposed inorder to resolve; expand the calculation ability of CAT sytem which have many parameters; select the suitable question depend on candidate’s current knowledge level. The thesis is generaly describle about CAT; introduce about existing CAT model. From Bayesian Network theory; Item Response Theory adapt to question which designes and created the CAT system. Among these, the fuzzy controller to optimized the calculation for the ability estimatation agrorithm of student. The review and analysis for te system also mention in the Thesis. The author was summarize the successful result and given the improvement direction next step. Key words - Computerized Adaptive Testing; Bayesian Network; Item Response Theory; the ability estimatation agrorithm of student. iii MỤC LỤC LỜI CAM ĐOAN ......................................................................................................i TÓM TẮT LUẬN VĂN .......................................................................................... ii MỤC LỤC .............................................................................................................. iii DANH MỤC CÁC CHỮ VIẾT TẮT ....................................................................... v DANH MỤC CÁC KÝ HIỆU .................................................................................vi DANH MỤC CÁC BẢNG .................................................................................... vii DANH MỤC CÁC HÌNH..................................................................................... viii DANH MỤC CÁC BIỂU ĐỒ .................................................................................ix MỞ ĐẦU .................................................................................................................. 1 1. Lý do chọn đề tài .............................................................................................. 1 2. Mục đích và ý nghĩa đề tài ................................................................................ 1 3. Mục tiêu và nhiệm vụ ....................................................................................... 2 4. Đối tượng và phạm vi nghiên cứu .................................................................... 2 5. Phương pháp nghiên cứu .................................................................................. 2 6. Kết quả dự kiến ................................................................................................. 3 CHƯƠNG 1. CƠ SỞ LÝ LUẬN VÀ THỰC TIỄN ................................................. 4 1.1. Tổng quan về trắc nghiệm thích nghi ............................................................ 4 1.1.1. Khái niệm trắc nghiệm thích nghi .......................................................... 4 1.1.2. Lịch sử TNTN .......................................................................................... 4 1.2. Các thành phần của mô hình TNTN .............................................................. 5 1.2.1. Ngân hàng câu hỏi .................................................................................. 5 1.2.2. Thuật toán lựa chọn câu hỏi ................................................................... 5 1.2.3. Đánh giá năng lực của thí sinh ............................................................... 5 1.2.4. Điều kiện dừng ........................................................................................ 6 1.3. Hoạt động của mô hình TNTN ...................................................................... 6 1.4. Phân tích các mô hình TNTN ........................................................................ 7 CHƯƠNG 2. XÂY DỰNG MÔ HÌNH TRẮC NGHIỆM THÍCH NGHI ............... 9 2.1. Lý thuyết mạng Bayes ................................................................................... 9 2.1.1. Giới thiệu ................................................................................................ 9 2.1.2. Định nghĩa mạng Bayes .......................................................................... 9 2.1.3. Mạng Bayes nhân quả........................................................................... 10 2.1.4. Học cấu trúc.......................................................................................... 10 2.1.5. Học tham số .......................................................................................... 10 2.1.6. Suy luận trong mạng Bayes .................................................................. 11 2.1.7. Ứng dụng .............................................................................................. 11 iv 2.2. Lý thuyết đáp ứng câu hỏi ........................................................................... 12 2.2.1. Giới thiệu .............................................................................................. 12 2.2.2. Mô hình IRT 2 tham số ......................................................................... 12 2.3. Xây dựng mô hình TNTN dựa trên mạng Bayes kết hợp IRT 2 tham số ........... 14 2.3.1. Mô hình TNTN ...................................................................................... 14 2.3.2. Ngân hàng câu hỏi ................................................................................ 15 2.3.3. Thuật toán TNTN .................................................................................. 16 2.3.4. Thuật toán lựa chọn câu hỏi ................................................................. 17 2.3.5. Ước lượng năng lực thí sinh ................................................................. 17 2.3.6. Thuật toán dừng .................................................................................... 25 CHƯƠNG 3. XÂY DỰNG VÀ TRIỂN KHAI HỆ THỐNG ................................. 26 3.1. Phân tích chức năng của hệ thống TNTN .................................................... 26 3.1.1. Biểu đồ đặc tả chức năng của thí sinh .................................................. 26 3.1.2. Biểu đồ đặc tả chức năng của giáo viên ............................................... 27 3.1.3. Biểu đồ đặc tả chức năng của hệ thống ................................................ 28 3.2. Biểu đồ use case của hệ thống TNTN.......................................................... 28 3.2.1. Các tác nhân của hệ thống ................................................................... 28 3.2.2. Use case thí sinh ................................................................................... 28 3.2.3. Use case giáo viên ................................................................................ 29 3.3. Biểu đồ trạng thái của hệ thống TNTN........................................................ 29 3.3.1. Biểu đồ trạng thái của giáo viên ........................................................... 29 3.3.2. Biểu đồ trạng thái của thí sinh ............................................................. 30 3.3.3. Biểu đồ trạng thái của hệ thống ........................................................... 31 3.4. Biểu đồ tuần tự của hệ thống TNTN............................................................ 32 3.5. Biểu đồ hoạt động của hệ thống TNTN ....................................................... 33 3.5.1. Biểu đồ hoạt động của thí sinh ............................................................. 33 3.5.2. Biểu đồ hoạt động của giáo viên .......................................................... 34 3.5.3. Biểu đồ hoạt động của hệ thống ........................................................... 35 3.6. Thiết kế cơ sở dữ liệu................................................................................... 36 3.7. Triển khai hệ thống TNTN .......................................................................... 36 3.8. Đánh giá hệ thống TNTN ............................................................................ 37 TÀI LIỆU THAM KHẢO ...................................................................................... 42 PHỤ LỤC QUYẾT ĐỊNH GIAO ĐỀ TÀI. BẢN SAO KẾT LUẬN CỦA HỘI ĐỒNG, BẢN SAO NHẬN XÉT CỦA CÁC PHẢN BIỆN. v DANH MỤC CÁC CHỮ VIẾT TẮT TNTN TNKQ CSDL NHCH Trắc nghiệm thích nghi Trắc nghiệm khách quan Cơ sở dữ liệu Ngân hàng câu hỏi vi DANH MỤC CÁC KÝ HIỆU a b P(i) θ Độ phân biệt câu hỏi Độ khó câu hỏi Xác suất trả lời đúng câu hỏi thứ i Năng lực thí sinh vii DANH MỤC CÁC BẢNG Số bảng Tên bảng Trang 1.1 Bảng đánh giá các thuật toán lựa chọn MI, KL và MEI (+: có, -: không) 7 2.1 Thiêt kế giả định môn Mathematics 19 2.2 Phân cấp chi tiết môn Mathematics 19 2.3 Xác suất trả lời đúng câu hỏi 25 3.1 Bộ câu hỏi ước lượng tham số theo IRT 2 tham số 37 3.2. Kết quả đánh giá năng lực của thí sinh 40 viii DANH MỤC CÁC HÌNH Số hiệu 1.1. 2.1. 2.2. 2.3. 2.4. 2.5. 2.6. 2.7. 3.1. 3.2. 3.3. 3.4. 3.5. 3.6. 3.7. 3.8. 3.9. 3.10. 3.11. 3.12. Tên hình Mô hình hoạt động của hệ thống TNTN Mô hình TNTN Thuật toán TNTN Các phương án của mô hình quan hệ nhân quả BN mô phỏng mối quan hệ giữa chủ đề và các khái niệm của nó Mạng Bayes cho TNTN Chuyển đổi ICC Sử dụng G(x) để tính các xác suất Biểu đồ đặc tả chức năng của thí sinh Biểu đồ đặc tả chức năng của giáo viên Biểu đồ đặc tả chức năng của hệ thống Biểu đồ Use case thí sinh Biểu đồ Use case giáo viên Biểu đồ trạng thái của giáo viên Biểu đồ trạng thái của thí sinh Biểu đồ trạng thái của hệ thống Biểu đồ tuần tự của hệ thống Biểu đồ hoạt động của thí sinh Biểu đồ hoạt động của giáo viên Biểu đồ hoạt động của hệ thống Trang 6 14 16 21 22 23 23 24 26 27 28 28 29 29 30 31 32 33 34 35 ix DANH MỤC CÁC BIỂU ĐỒ Số hiệu biểu đồ Biểu đồ 3.1 Biểu đồ 3.2 Tên bảng Biểu đồ biểu diễn lựa chọn câu hỏi cho thí sinh có θ= 0.5 Biểu đồ biểu diễn lựa chọn câu hỏi cho thí sinh có θ= 1.5 và θ= 1.5 Trang 38 39 1 MỞ ĐẦU 1. Lý do chọn đề tài Đánh giá kết quả học tập là một khâu quan trọng trong quá trình đào tạo, là một trong những yếu tố quyết định chất lượng giáo dục. Các phương pháp đánh giá truyền thống như: vấn đáp, tự luận, … thường mất nhiều thời gian, khó chính xác và không khách quan. Để khắc phục những hạn chế trên thì kiểm tra bằng hình thức trắc nghiệm đã được đề xuất. Nhờ vào đặc điểm luôn có sự rõ ràng của đáp án, tính khách quan trong đánh giá kết quả học tập của người học mà hình thức đánh giá này đã được áp dụng ở hầu khắp hệ thống giáo dục trên thế giới. Một trong những hệ thống trắc nghiệm đang được sử dụng phổ biến là trắc nghiệm khách quan (Objective test) [4]. Tuy nhiên mô hình trắc nghiệm này vẫn chưa thực sự đưa ra kết quả đúng đắn hoặc công bằng do một số nguyên nhân: bộ câu hỏi trong một bài kiểm tra được lựa chọn một cách ngẫu nhiên nên sẽ có bài kiểm tra quá khó hoặc quá dễ, điều này dẫn đến gây nhàm chán cho thí sinh khi làm toàn câu hỏi dễ hoặc gây ức chế nếu gặp phải câu hỏi quá khó. Để quá trình đánh giá mức năng lực của thí sinh được chính xác và khách quan hơn, một mô hình trắc nghiệm đã và đang được nghiên cứu hiện nay là trắc nghiệm thích nghi (TNTN) đặc biệt là mô hình thích nghi trên máy tính (Computerized Adaptive Testing - CAT) [14]. Mô hình này cho phép lựa chọn câu hỏi tiếp theo phù hợp với mức kiến thức và năng lực hiện tại của thí sinh. Hệ thống TNTN trên máy tính cho phép tự động đánh giá mỗi thí sinh với tập hợp câu hỏi trắc nghiệm là khác nhau về số lượng và nội dung câu hỏi. Năng lực thí sinh được cập nhật thường xuyên trong quá trình đánh giá, và quá trình đánh giá sẽ kết thúc khi đưa ra được chính xác mức kiến thức và năng lực thực sự của thí sinh. Ngày nay, với sự phát triển vượt bậc của khoa học máy tính nên vấn đề triển khai các hệ thống TNTN dựa trên cơ sở các mô hình toán học là hoàn toàn khả thi. Một số mô hình TNTN đã được nghiên cứu và hiện thực hóa như: mô hình TNTN trên cơ sở lý thuyết đáp ứng câu hỏi [19], mô hình TNTN trên cơ sở [15], … Tuy nhiên các mô hình TNTN kể trên vẫn còn tồn tại một số nhược điểm 2. Mục đích và ý nghĩa đề tài a. Mục đích Xây dựng mô hình TNTN trên cơ sở mạng Bayes. Xây dựng hệ thống TNTN dựa trên mô hình đề xuất và triển khai ứng dụng cho việc đánh giá kiến thức và kỹ năng của sinh viên ở Trường ĐH Sư phạm Kỹ thuật Vĩnh Long đối với học phần Lập trình Web. b. Ý nghĩa khoa học Xây dựng mô hình TNTN ứng dụng mạng Bayes. 2 c. Ý nghĩa thực tiễn Hiện thực hóa hệ thống TNTN trên cơ sở mô hình đề xuất nhằm nâng cao hiệu quả đánh giá năng lực người học một cách tự động hóa. 3. Mục tiêu và nhiệm vụ a. Mục tiêu Nghiên cứu mô hình TNTN; Tìm hiểu mạng Bayes; Xây dựng mô hình TNTN trên cơ sở mạng Bayes; Hiện thực hóa hệ thống Website đánh giá dựa trên mô hình đề xuất. b. Nhiệm vụ Đưa ra vấn đề và phân tích vấn đề; Phát biểu, phân tích và xây dựng mô hình TNTN để giải quyết bài toán đặt ra; Triển khai thực tế và đánh giá kết quả đạt được của hệ thống. 4. Đối tượng và phạm vi nghiên cứu a. Đối tượng nghiên cứu Các mô hình và thuật toán TNTN; Các hệ thống TNTN hiện có; Lý thuyết mạng Bayes. b. Phạm vi nghiên cứu Ứng dụng mạng Bayes xây dựng hệ thống TNTN cho học phần Lập trình Web tại Trường Đại học Sư phạm Kỹ thuật Vĩnh Long. 5. Phương pháp nghiên cứu a. Phương pháp lý thuyết Phân tích và đánh giá các mô hình, thuật toán và hệ thống TNTN hiện có và khả năng ứng dụng đối với giáo dục ở Việt Nam;ây Đưa ra kết luận và cơ sở cho việc lựa chọn mạng Bayes làm nền tảng để xây dựng mô hình TNTN; Nghiên cứu và áp dụng mạng Bayes xây dựng hệ thống TNTN. b. Phương pháp thực nghiệm Xây dựng ngân hàng câu hỏi làm dữ liệu đầu vào cho chương trình (bao gồm việc thiết lập các tham số đặc trưng cho từng câu hỏi); Xây dựng Website TNTN trên cơ sở mô hình đề xuất; Triển khai và đánh giá hệ thống. 3 6. Kết quả dự kiến a. Kết quả của đề tài Xây dựng mô hình TNTN trên cơ sở mạng Bayes và Lý thuyết đáp ứng câu hỏi; Hiện thực hóa hệ thống TNTN trên cơ sở mô hình đề xuất và triển khai thực tế đối với học phần Lập trình Web tại Trường Đại học Sư phạm Kỹ thuật Vĩnh Long. b. Hướng phát triển của đề tài Tối ưu hóa mô hình TNTN đề xuất; Hoàn thiện hệ thống TNTN. 4 CHƯƠNG 1. CƠ SỞ LÝ LUẬN VÀ THỰC TIỄN Chương này giới thiệu tổng quan về TNTN, các thành phần cơ bản, hoạt động chung của một mô hình TNTN; Phân tích các mô hình TNTN đã tồn tại, từ đó đưa ra lý do để xây dựng TNTN trên cơ sở mạng Bayes. 1.1. Tổng quan về trắc nghiệm thích nghi 1.1.1. Khái niệm trắc nghiệm thích nghi Trắc nghiệm thích nghi (TNTN), tiếng Anh gọi là “Adaptive Test” là thuật ngữ để chỉ một phương pháp đánh giá thí sinh bằng hình thức kiểm tra trắc nghiệm nhưng đánh giá theo hướng năng lực của thí sinh bằng bộ câu hỏi tương ứng với mức năng lực đó. Hệ thống trắc nghiệm thích nghi trên máy tính (CAT-Computerized Adaptive Testing) là phần mềm quản lý tự động với những câu hỏi có độ khó phù hợp với thí sinh dựa trên năng lực hiện thời của thí sinh. Trái ngược với trắc nghiệm khách quan trên máy tính - hệ thống đưa ra bộ các câu hỏi theo trình tự đã được xác định trước hoặc ngẫu nhiên, hệ thống CAT đưa ra câu hỏi thích ứng với thí sinh. Nếu thí sinh trả lời chính xác một câu hỏi thì câu hỏi trắc nghiệm tiếp theo khó hơn câu hỏi hiện thời. Do đó, nếu thí sinh trả lời sai câu hỏi hiện thời thì câu hỏi tiếp theo sẽ dễ hơn. Vì vậy, những sinh viên khác nhau sẽ nhận được các tập các câu hỏi trắc nghiệm khác nhau dựa trên câu trả lời của họ về các câu hỏi. Quy trình đánh giá với khả năng thích nghi có các ưu điểm sau: - Quy trình đánh giá trở nên động và riêng rẽ, vì nó được thích ứng với mỗi sự thực hiện của thí sinh. - Tránh được việc thí sinh phải làm bài thi trên những câu hỏi không phù hợp với năng lực của mình. - Số lượng các câu hỏi đã yêu cầu để ước lượng mức hiểu biết của thí sinh là giảm đi đáng kể, kết quả dẫn tới quy trình đánh giá bớt nhàm chán. 1.1.2. Lịch sử TNTN TNTN đã xuất hiện từ rất lâu và được ứng dụng nhiều trong thực tế cuộc sống như trắc nghiệm thông minh, trắc nghiệm tâm lý, Elearing, … Ý tưởng ban đầu của TNTN là của nhà Tâm lý học người Pháp Alfred Binet (1859- 1911). Năm 1905, ông đã phát triển một thử nghiệm tư duy trên trẻ em. Các thử nghiệm đối với nhiều độ tuổi khác nhau với những bộ câu hỏi phù hợp cho từng lứa tuổi. Từ những thông tin của mỗi đợt kiểm tra, ông đưa đưa ra kết luận năng lực cho từng ứng viên. Phương pháp của Binet là đơn giản và có thể thực hiện bằng máy vi tính. Năm 1980, Lord đưa ra phương pháp đánh giá có tên là Flexilevel. Sau đó có một số biến thể của phương pháp này như phương pháp Step của Henning (1987), phương 5 pháp Testle của Lewis và Sheehan (1990). Những phương pháp này là sự sàng lọc từ phương pháp của Binet. Các câu hỏi được phân loại theo cấp độ độ khó khác nhau, mỗi cấp độ gồm nhiều câu hỏi. Việc đánh giá sau đó sẽ được tiến hành với một bộ các câu hỏi thuộc một cấp nào đó tùy thuộc vào tỷ lệ thành công của mỗi cấp độ mà quyết định di chuyển lên hay xuống một cấp. Sau khi thực hiện một số tập con, có thể ước lượng được khả năng thực sự của một số thí sinh. Với tốc độ phát triển chóng mặt của máy tính điện tử thì ngày nay các hệ thống TNTN đã trở nên phổ biến và giúp cho việc đánh giá năng lực (kiến thức) thí sinh ngày càng trở nên chính xác và hiệu quả hơn. Một số thử nghiệm đã được công nhận như: Graduate Record Test, Graduate Management Admission Test, Scholastic Aptitude Test, …. 1.2. Các thành phần của mô hình TNTN Về cơ bản, mô hình TNTN có các thành phần: ngân hàng câu hỏi (Calibrated item bank), thuật toán lựa chọn câu hỏi (Item selection algorithm), thuật toán đánh giá (Scoring algorithm) và điều kiện dừng (Termination criterion) [7], [13], [14]. Tuy nhiên, các thành phần này có những điểm khác so với trắc nghiệm khách quan. 1.2.1. Ngân hàng câu hỏi Là tập hợp câu hỏi đã được ước lượng các tham số đặc trưng như độ khó, độ phân biệt. Ngân hàng câu hỏi được sử dụng để làm cơ sở đánh giá năng lực thí sinh. Do đó, ngân hàng câu hỏi tốt đòi hỏi phải có số lượng tương đối lớn và phong phú. 1.2.2. Thuật toán lựa chọn câu hỏi Việc đánh giá năng lực của thí sinh trong TNTN phụ thuộc rất lớn vào thuật toán lựa chọn câu hỏi. Nếu câu hỏi được chọn quá dễ so với năng lực hiện tại của thí sinh thì thí sinh có thể dễ dàng trả lời và ngược lại. Điều này dễ dẫn tới việc đánh giá năng lực thí sinh không chính xác. Thuật toán này được sử dụng để lựa chọn câu hỏi tốt nhất từ ngân hàng câu hỏi để đưa vào bài kiểm tra. Câu hỏi được cho là tốt nhất là câu phù hợp nhất với năng lực hiện tại của thí sinh, nghĩa là câu hỏi hỏi này có các tham số câu hỏi tương ứng với tham số năng lực hiện tại của thí sinh. Thuật toán lựa chọn câu hỏi gồm các bước sau: - Dựa trên tham số năng lực hiện tại, tính toán giá trị của hàm thông tin cho các câu hỏi chưa đưa ra cho thí sinh trả lời; - Tìm và chọn câu hỏi phù hợp nhất với năng lực hiện tại của thí sinh (câu hỏi có hàm thông tin lớn nhất). 1.2.3. Đánh giá năng lực của thí sinh Sau khi nhận kết quả trả lời câu hỏi của thí sinh, hệ thống sẽ tính toán lại mức năng lực của thí sinh. Việc tính toán này sẽ đưa ra giá trị mới cho tham số năng lực. Thông thường giá trị này không thay đổi nhiều so với lần đánh giá trước đó và sẽ tiến dần đến mức năng lực thực sự của thí sinh. 6 1.2.4. Điều kiện dừng Vì mô hình TNTN hoạt động theo thuật toán lặp các thao tác lựa chọn câu hỏi, thí sinh trả lời, đánh giá năng lực nên cần có điều kiện dừng để làm căn cứ kết thúc quá trình trắc nghiệm. Điều kiện dừng có thể là một hoặc một số tiêu chí như: độ sai lệch năng lực thấp, thời gian làm bài vượt quá thời gian quy định, số lượng câu hỏi vượt quá mức quy định, … 1.3. Hoạt động của mô hình TNTN Bắt đầu Khởi tạo mức năng lực Đúng Điều kiện dừng Sai Lựa chọn câu hỏi phù hợp Đánh giá lại mức năng lực Báo cáo kết quả mức năng lực Kết thúc Hình 1.1. Mô hình hoạt động của hệ thống TNTN Hoạt động chung của mô hình TNTN là một thuật toán lặp gồm các bước sau: Bước 1: Khởi tạo giá trị mức năng lực ban đầu của thí sinh. Bước 2: Dựa vào mức năng lực hiện tại của thí sinh, lựa chọn câu hỏi phù hợp nhất từ các câu hỏi chưa được chọn. Bước 3: Tính toán lại mức năng lực mới dựa vào kết quả trả lời câu hỏi của thí sinh. Bước 4: Quay lại bước 2 nếu điều kiện dừng chưa thỏa mãn. 7 Trong mô hình TNTN, thuật toán lựa chọn câu hỏi tiếp theo phù hợp với năng lực hiện tại của thí sinh là khó khăn vì phải được tính toán một cách phức tạp. Ngày nay với sự phát triển của khoa học máy tính thì vấn đề trên đã được giải quyết một cách tốt hơn, giúp hệ thống đánh giá năng lực của thí sinh một cách chính xác, nhanh chóng và giảm bớt thời gian cũng như chi phí của quá trình đánh giá. 1.4. Phân tích các mô hình TNTN Như đã đề cập ở trên, thuật toán lựa chọn câu hỏi tiếp theo là phần quan trọng nhất trong mô hình TNTN. Cho đến hiện nay, tồn tại các mô hình TNTN sử dụng một số thuật toán lựa chọn câu hỏi tiếp theo phù hợp với năng lực của thí sinh như: thuật toán lựa chọn câu hỏi theo tiêu chuẩn thông tin tối đa (Maximum Information - MI), thuật toán lựa chọn câu hỏi theo thông tin toàn cục (Kullback-Leibler – KL), thuật toán lựa chọn câu hỏi dựa trên sự phân tích tiên đoán theo tiêu chí tối đa thông tin (Maximum Expected Information - MEI). Thuật toán lựa chọn câu hỏi theo tiêu chuẩn thông tin tối đa (MI) [12] là thuật toán phổ biến được sử dụng trong các mô hình TNTN. Câu hỏi thứ n+1 được lựa chọn cho thí sinh là câu hỏi cung cấp thông tin tối đa cho phép ước lượng khả năng của thí sinh ( n) dựa trên n câu hỏi trước đó mà thí sinh đã trả lời. Thuật toán lựa chọn câu hỏi theo thông tin toàn cục (KL) là thuật toán lựa chọn câu hỏi dựa trên phương pháp thông tin tổng thể được đề xuất bởi Chang and Ying (1996) [11]. Thuật toán này sử dụng độ đo Kullback-Leibler để tính toán ước lượng trong việc lựa chọn câu hỏi. Thuật toán lựa chọn câu hỏi dựa trên sự phân tích tiên đoán theo tiêu chí tối đa thông tin (MEI) là thuật toán lựa chọn câu hỏi dựa trên việc phân tích tiên đoán các tiêu chí tối đa thông tin dự kiến được đề xuất bởi van der Linden (1998) [19]. Thuật toán MI, KL và MEI sẽ dừng khi tiêu chuẩn lỗi (SE) đủ nhỏ. Khi đó có thể nói đã xác định được mức năng lực của thí sinh. Bảng 1.1. Bảng đánh giá các thuật toán lựa chọn MI, KL và MEI (+: có, -: không) Thuật toán lựa chọn câu hỏi Thuật toán MI Đánh giá Khả năng thích Số câu hỏi để Thời gian tính thông số câu ứng liên tục với xác định tiêu toán hàm thông hỏi tham số năng lực chuẩn tin lỗi+/(SE) +/- Thuật toán KL - - +/- +/- Thuật toán MEI - - +/- +/- Phân tích các mô hình TNTN sử dụng các thuật toán lựa chọn câu hỏi kể trên không tính toán đến thông số của câu hỏi sẽ ảnh hưởng như thế nào đến việc lựa chọn 8 (ví dụ như độ khó của câu hỏi), không có khả năng thích ứng liên tục với tham số năng lực của thí sinh. Ngoài ra, khi tiêu chuẩn lỗi được đặt cố định ở mức thấp đòi hỏi phải cần nhiều câu hỏi cho bài kiểm tra và thời gian tính toán hàm thông tin phụ thuộc nhiều vào ngân hàng câu hỏi. Từ phân tích trên thì các mô hình và hệ thống TNTN hiện có còn tồn tại nhiều hạn chế, vì vậy nên định hướng và nghiên cứu đề tài: “Ứng dụng mạng Bayes xây dựng mô hình trắc nghiệm thích nghi” là cần thiết để khắc phục các tồn tại nêu trên. 9 CHƯƠNG 2. XÂY DỰNG MÔ HÌNH TRẮC NGHIỆM THÍCH NGHI Chương này trình bày nội dung nghiên cứu chính của đề tài đó là xây dựng mô hình TNTN dựa trên mạng Bayes. 2.1. Lý thuyết mạng Bayes 2.1.1. Giới thiệu Mạng Bayes (tiếng Anh: Bayesian network hoặc Bayesian belief network hoặc belief network) là một mô hình xác suất dạng đồ thị. Một mạng Bayes được biểu diễn bởi một đồ thị, trong đó các nút đại diện cho các biến còn các cung đại diện cho các phụ thuộc có điều kiện. Phân phối xác suất có điều kiện phụ thuộc (joint probability distribution) của các biến được xác định bởi cấu trúc đồ thị của mạng. Cấu trúc đồ thị của một mạng Bayes dẫn tới các mô hình dễ giải thích và tới các thuật toán học và suy luận hiệu quả. Các nút có thể đại diện cho đủ loại biến, một tham số đo được, một biến ẩn (latent variable) hay một giả thuyết chứ không nhất thiết phải đại diện cho các biến ngẫu nhiên. 2.1.2. Định nghĩa mạng Bayes Một mạng Bayes là một đồ thị có hướng phi chu trình mà trong đó: Các nút biểu diễn các biến; Các cung biểu diễn các quan hệ phụ thuộc thống kê giữa các biến và phân phối xác suất địa phương cho mỗi giá trị nếu cho trước giá trị của các cha của nó. Nếu có một cung từ nút A tới nút B, thì biến B phụ thuộc trực tiếp vào biến A, và A được gọi là cha của B. Nếu với mỗi biến trong mạng là Xi, i ∈{1,..,N} và Pa(Xi) là tập hợp các biến cha của nút Xi thì phân phối xác suất có điều kiện phụ thuộc của các biến là tích của các phân phối xác suất địa phương. 𝑛 𝑃(𝑋1 , … , 𝑋𝑛 ) = ∏ 𝑃(𝑋𝑖 | Pa(𝑋𝑖 )) 𝑖=1 Như vậy, để xác định một mạng Bayesian chúng ta cần cung cấp: Tập các biến: X1, X2, ..., Xn. Tập hợp các mối quan hệ (ảnh hưởng nhân quả) giữa các biến đó. Các mối quan hệ được đại diện bởi các liên kết trực tiếp trong mạng, và dĩ nhiên là mạng không có chứa bất kỳ chu trình nào. Với mỗi biến, sự phân phối có điều kiện {P(Xi| Pa(Xi)), i=1, …, n}. Nếu Xi không có cha, ta nói rằng phân phối xác suất địa phương của nó là không có