Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mơ thuật tốn Find-s BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG -o0o - TÌM HIỂU VỀ HỌC MÁY VÀ PHƢƠNG PHÁP HỌC KHÁI NIỆM XÂY DỰNG MODULE MƠ PHỎNG THUẬT TỐN FIND-S ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công Nghệ Thông Tin Sinh viên thực hiện: Vũ Ngọc Nam Giáo viên hƣớng dẫn: Ths Vũ Mạnh Khánh Mã số sinh viên: 111351 Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mơ thuật tốn Find-s Chƣơng 1:Tổng Quan Về Học máy 1.1 Giới thiệu học máy Học máy, nhiều tài liệu gọi máy học lĩnh vực trí tuệ nhân tạo cho phép máy tính "học" Cụ thể hơn, học máy phương pháp để tạo chương trình máy tính dựa tập liệu.Trong chương đưa câu trả lời chung cho câu hỏi: Tại phải học máy ? Thế toán học máy xác định ? Cho ví dụ minh hoạ ? Các vấn đề học máy ? Từ phát minh máy tính người ta muốn làm chương trình làm cho máy học người (học máy) đến mong muốn chưa thực Tuy người ta có nhiều thành tựu lĩnh vực học máy như: Nhận dạng tiếng nói Xử lý ngơn ngữ tự nhiên Dự đốn, chuẩn trị y học Nhận dạng ADN Phân loại cấu trúc thiên văn Chơi cờ số trò chơi khác Lái xe tự động Các ứng dụng để khám phá tri thức (Data mining) CSDL lớn nhằm trợ giúp định Học máy kế thừa thành tựu nhiều lĩnh vực khoa học Sau số lĩnh vực ý tưởng ảnh hưởng tới học máy: Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mơ thuật tốn Find-s Trí tuệ nhân tạo: Học biểu diễn tượng trưng khái niệm; học máy tốn tìm kiếm; học cách tiếp cận cải tiến giải toán; sử dụng tri thức sãn có liệu đào tạo để hướng dẫn học Các phương pháp Bayes: định lý Bayes làm sở để tính xác suất giả thuyết, Cách phân lớp Bayes, thuật toán ước lượng giá trị không quan sát Lý thuyết độ phức tạp tính tốn: tính độ phức tạp nhiệm vụ học đo qua ví dụ đào tạo, số lỗi tính tốn Lý thuyết điều khiển: Các thủ tục học để điều khiển trình nhằm tối ưu hố mục đích định trước hay học cách đốn trạng thái q trình điều khiển Lý thuyết thông tin: độ đo nội dung thông tin entropy;Mã tối ưu quan hệ chúng tới dãy đào tạo tối ưuđể mã hoá giả thuyết Triết học: nguyên lý Occam's razor ( cho giả thuyết đơn giản tơt ; phân tích luận chứng để tổng quát hoá liệu quan sát Tâm lý học thần kinh học: đáp ứng thực tế người, mơ hình neural Thống kê: đặc trưng lỗi, lý thuyết lấy mẫu, khoảng tin cậy 1.2 Các toán học thiết lập đắn Trước hết ta cần phát biểu định nghĩa chung cho chương trình học số nhiệm vụ cần học Định nghĩa Một chương trình máy tính gọi học từ thí nghiệm E lớp nhiệm vụ học T độ đo mức thực P thực nhiệm vụ Tcủa đo T cải tiến qua kinh nghiệm E Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Công Nghệ Thông Tin Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mơ thuật tốn Find-s Các ví dụ: 1)Chương trình học chơi cờ với T: Chơi cờ P: Tỷ lệ thắng đối thủ E: chơi với với người khác hay có thầy Với toán ta cần biễu diễn đặc trưng ván cờ nào? học gì? thuật tốn học sao? 2)Nhận dạng chữ viết tay T: phân lớp (nhận dạng ) chữ viết tay nhờ phân tích ảnh P : tỷ lệ chữ nhận dạng E : chữ viết phân loại đưa 3) Robot học lái T: lái xe đường cao tốc 4-làn xe nhờ sử dụng sensor nhìn P: quảng cách trung bình trước có lỗi E : loạt ảnh lệnh lái ghi qua quan sát người dạy 4) Phân nhóm đối tượng Tập đối tượng cần chia làm k nhóm cho đối tượng nhóm tương tự cịn đối tượng khác nhóm khác T: phân nhóm P: tương tự tương quan chung E: Q trình phân nhóm 5) Chẩn trị bệnh Dựa cở liệu bệnh án: lưu trữ triệu chứng; phác đồ điều trị kết bệnh nhân, chẩn đoán bệnh đưa phác đồ điều trị cho bệnh nhân Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mơ thuật tốn Find-s T: Đoán đưa phác đồ điều trị P: Tỷ lệ chẩn đoán điều trị khỏi bệnh E: Các bệnh án biết 1.3 Thiết kế hệ học Trong mục ta xét toán học chơi cờ với đối thủ để minh hoạ Chọn kinh nghiệm đào tạo Trước hết cần chọn kiểu kinh nghiệm đào tạo: trực tiếp hay gián tiếp (có liên hệ ngược) Việc lựa chọn có ảnh hưởng lớn tới thành cơng thất bại hệ học Ví dụ Trực tiếp: kinh nghiệm chơi cờ cho cờ nước cho Gián tiếp: thông tin bao gồm dãy nước kết cục nhiều ván chơi Thứ hai chọn cách điều khiển dãy kinh nghiệm đào tạo: Có thể cờ nước cờ thầy cho sẵn hệ học hồn tồn dựa vào hệ chơi tự tạo ván cờ trạng thái có thầy hay khơng có thầy (tuỳ theo toán cụ thể ) Thứ ba làm để đánh giá độ đo đích thực P qua độ đo thí dụ đào tạo (Các nước qua thí nghiệm khơng tốt chưa gặp đối thủ thực sự) Khi ta cần số giả thiết bổ sung Nếu chọn cách chơi với nó, ta mơ tả cụ thể nhiệm vụ học chơi cờ: T: Chơi cờ P: Tỷ lệ thắng đối thủ E: chơi với Tiếp theo ta cần chọn Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mơ thuật tốn Find-s Kiểu xác định tri thức để học Một cách biểu diễn tri thức đích Một cấu học 1.4 Các vấn đề học máy Việc học máy thực chất tìm kiếm khơng gian giả thuyết lớn giả thuyết phù hợp với liệu quan sát tri thức có Trong ví dụ , khơng gian giả thuyết xác định giá trị trọng số liệu ván chơi tri thức làcách để nước hợp lệ Các vấn đề thường gặp học máy là: Từ ví dụ đào tạo có tồn thuật tốn để học hàm đích hay khơng? thuật tốn có hội tụ tới hàm đích mong muốn khơng? liệu có đủ cho thuật tốn khơng?thuật tốn tốt cho toán cách thể xét Bao nhiêu liệu đào tạo đủ? Trong không gian giả thuyết liệu có thi ưứơc lượng mức tin cậy nào? Các tri thức biết có tác dụng cho trình học Chiến lược thí nghiệm đào tạo tốt nhất, cách chọn chiến lươc nào? Cách tốt để đưa toán học toán xấp xỉ hàm? Q trình tự động hố khơng? Làm hệ học lựa chon cách biểu diễn để cải tiến khả biểu diễn học hàm đích? Chƣơng 2: 2.1 Các công thức xác suất thông kê Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mơ thuật tốn Find-s Không gian mẫu không gian biến cố Không gian mẫu Tiến hành thực phép thử (thí nghiệm) Giả sử ta trước kết phép thử ta biết tập tất kết phép thử Ta có phép thử ngẫu nhiên Tập tất kết phép thử gọi khơng gian mẫu phép thử, ký hiệu Với phép thử, ta xác định khơng gian mẫu theo nhiều cách Không gian biến cố Mỗi phần tử gọi biến cố sơ cấp Mỗi tập gọi biến cố (ngẫu nhiên), ký hiệu A, B,…Khi phép thử thực hiện, ta nói biến cố A xảy kết xuất phần tử A Các phép toán với biến cố Cho A, B, C, A1, , An biến cố không gian mẫu Khi đó, - A gọi kéo theo B, ký hiệu A Ì B xảy A kéo theo xảy B - Tổng A B, ký hiệu A B biến cố xảy A B xảy - Tích A B, ký hiệu A B hay AB biến cố xảy A B xảy - Hiệu A B, ký hiệu A \ B biến cố xảy A xảy B không xảy - Biến cố = \ A gọi biến cố đối lập biến cố A - Nếu A B= A B gọi xung khắc với - Dãy n biến cố A1,A2,…,An lập thành hệ đầy đủ biến cố i1/ A1 A2 i2/ Ai Aj = … An = với (xung khắc đơi) Cần lưu ý số tính chất sau: Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mô thuật toán Find-s *A B=B *A (B C) = (A B) C=A B C; A (B C) = (A B) C=A B C *A (B C) = (A B) (A *A A; =W;A A B=B = A C); A (B C) = (A B) (A C) * Công thức xác suất cổ điển P(A) = = Xác suất điều kiện Trong nhiều trường hợp, vấn đề đặt là: ta nói xác suất biến cố A có thơng tin biến cố B (liên quan tới A) xảy ra? Trong trường hợp đơn giản nhất, câu trả lời dễ dàng Chẳng hạn, A B xung khắc A khơng thể xảy ra, xác suất để A xảy Trường hợp khác, A chắn xảy nên xác suất Vấn đề cịn lại, B xảy cho ta phần thông tin phép thử (tức cho A) P(A) xác định Khái niệm xác suất điều kiện sử dụng cho trường hợp Định nghĩa 1.1.1 Cho không gian xác suất (W, , P) B với P(B) > Khi với biến cố A bất kỳ, xác suất điều kiện biến cố A với điều kiện biến cố B xảy ra, ký hiệu xác định Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mơ thuật tốn Find-s Tính chất 1.1.2 * * * * Công thức xác suất biến cố tích Từ định nghĩa xác suất điều kiện ta suy Mở rộng cho trường hợp tổng quát ta nhận Sự độc lập biến cố Định nghĩa 1.1.6 Hai biến cố A B gọi độc lập với P(AB) = P(A) P(B) Từ định nghĩa dễ suy kết sau Hai biến cố A B độc lập với Hai biến cố A B độc lập với độc lập độc lập độc lập Định nghĩa 1.1.7 Dãy n biến cố B1, B2, , Bn gọi Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mô thuật tốn Find-s * Độc lập đơi P(BiBj) = P(Bi) P(Bj) với i j; i, j = * Độc lập toàn thể với i1 với i = 1, 2, , n Khi A biến cố với P(A) > ta có Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin 10 Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mơ thuật tốn Find-s Với thuộc tính h Nếu ràng buộc thoả mãn giữ nguyên Ngược lại thay h ràng buộc tổng quát thoả mãn x Bảng 2.3: Thuật toán Find-S Chẳng hạn đưa ví dụ bảng 2.1: x1= < nắng, ấm, trung bình, mạnh, ấm, khơng đổi> < nắng, ấm, trung bình, mạnh, ấm, khơng đổi> h Nếu đưa thêm ví dụ x2 = < nắng, ấm, cao, mạnh, ấm, không đổi> < nắng, ấm, ?, mạnh, ấm, không đổi> h Thuật tốn bỏ qua thí dụ sai (thứ 3) tới ví dụ thứ tư x4 = < nắng, ấm, cao, mạnh, lạnh, đổi> h < nắng, ấm, ?, mạnh, ?, ?> Ví dụ minh hoạ hình 2.2 Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin 21 Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mơ thuật tốn Find-s Hình 2.2 thuật tốn Find-S cho ví dụ bảng 2.1 Thuật tốn địi hỏi khơng gian giả thuyết cho liên kết ràng buộc thuộc tính Khi ta tìm giả thuyết chi tiết phù hợp với mẫu dương với mẫu âm giả thuyết tập mẫu cho Tuy số câu hỏi chưa trả lời thuật toán là: Thuật tốn có hội tụ tới giả thuyết khơng? (nó có học khái niệm khơng?) Mặc dù thuật tốn cho ta giả thuyết phù hợp với tập mẫu đào tạo ta khơng biết có giả thuyết phù hợp liệu ta tìm giả thuyết hay khơng? Nếu khơng ta cần ước lượng tính khơng chắn Tại ta ưa giả thuyết chi tiết nhất? giả thuyết khác sao? (tổng qt trung gian Nếu có ví dụ sai sao? Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin 22 Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mơ thuật tốn Find-s Trong ví dụ có khơng gian giả thuyết H Trong thực tế có nhiều khơng gian giả thuyết có nhiều giả thuyết chi tiết 3.5 Khơng gian tƣờng thuật thuật toán loại trừ ứng cử Trong mục đưa thuật toán cho ta giả thuyết phù hợp với tập mẫu đào tạo 3.5.1 Biễu diễn giả thuyết Thuật toán mục tìm giả thuyết mơ tả thù hợp với mẫu quan sát Trước hết ta cần định nghĩa Định nghĩa Một giả thuyết h gọi phù hợp với tập liệu đào tạo D h(x)=c(x) với D consistent(h,D) ( x, c( x) D)h( x) c( x) Chú ý khái niệm phù hợp khác khái niệm thoả mãn định nghĩa Thuật toán loại trừ ứng cử tìm tất giả thuyết phù hợp với tập ví dụ quan sát Tập gọi không gian tường thuật không gian giả thuyết H tập mẫu đào tạo D Định nghĩa Không gian tường thuật (được ký hiệu VSH,D không gian giả thuyết H tập liệu đào tạo D tập H phù hợp với tập mẫu D VS H , D h H consistent(h, D) 3.5.2 Thuật toán liệt kê loại trừ ứng cử:( List-then-eliminate algorithm) Một cách đơn giản để biểu diễn không gian tường thuật liệt kê phần tử Ý tưởng dẫn tới thuật tốn liệt kê-loại trừ ứng cử mô tả bảng 2.4 Thuật tốn khởi tạo tồn khơng gian giả thuyết sau loại trừ dần giả thuyết khơng phù hợp với ví dụ quan sát Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin 23 Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mô thuật toán Find-s Bảng 2.4 Thuật toán liệt kê loại trừ ứng cử VH,D danh sách giả thuyết H Với D loại trừ giả thuyết h VH,D mà h(x) c(x) Đầu VH,D Về ngun tắc thuật tốn áp dụng không gian giả thuyết H hữu hạn thựng hành thường khơng thể liệt kê tìm kiếm vét cạn H 3.5.3 Một cách biểu diễn compact khôn gian tường thuật Người ta biểu diễn khơng gian tường thuật nhờ thứ tự tổng quát đến chi tiết cách cận chi tiết cận tổng quát VH,D mà liệt kê chúng Để minh hoạ cho cách biểu diễn ta trở lại với tốn học khái niệm thích chơi thể thao với ví dụ bảng 2.1 Thuật tốn Find-S cho ta giả thuyết chi tiết là: < nắng, ấm, ?, mạnh, ?, ?> thực có sáu giả thuyết H phù hợp với tập mẫu bảng 2.1, giả thuyết mô tả hình 2.3 Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin 24 Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mơ thuật tốn Find-s Hình 2.3 Khơng gian tường thuật với tập biên tổng quát chi tiết cho toán học khái niệm bảng 2.1 Ý tưởng dẫn đến thuật toán loại trừ ứng cử Để trình bày thuật tốn ta cần đến định nghĩa tập biên tổng quát G chi tiết S Định nghĩa Biên tổng quát G không gian giả thuyết H tập liệu đào tạo D tập giả thuyết tổng quát H phù hợp với D G g H consistent( g , D) ( g ' H ) ( g ' g g ) consistent( g ' , D) Định nghĩa Biên chi tiết S không gian giả thuyết H tập liệu đào tạo D tập giả thuyết chi tiết H phù hợp với D S s H consistent( s, D) ( s' H ) ( s s' ) consistent( s' , D) g Tập G S hồn tồn đặc tả VH,D nhờ định lý sau Định lý 2.1 Định lý biễu diễn không gian tƣờng thuật Giả sử X tập mẫu tuỳ ývà H tập giả thuyết giá trị Bun xác định X Cho C:X {0,1} khái niệm đích xác định X D tập mẫu đào tạo tuỳ ý :{x,c(x)}Vowis X, H,c D cho G S xác định VH,D = h H ( s S )( g G)( g g h g s) Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin 25 Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mô thuật toán Find-s 3.5.4 Thuật toán loại trừ ứng cử Trong thuật toán ta khởi tạo G S giả thuyết G0 S0 giả thuyết tổng quát chi tiết nhất: G S G0 = S0 = < , , , , , > Khi mẫu đào tạo xem xét, G S chi tiết hoá tổng quát hoá để loại trừ khỏi VH,D giả thuyết không phù hợp với liệu tương ứng Sau tập mẫu D xét VH,D chứa giả thuyết phù hợp với D H Thuật tốn tóm tắt bảng 2.5 Bảng 2.5 Thuật toán loại trừ ứng cử Khởi tạo G tập giả thuyết tổng quát H Khởi tạo S tập giả thuyết chi tiết H 2.( Lặp)Với ví dụ đào tạo d={x,c(x)}, thực hiện: +Nếu d ví dụ dương (c(x)=1) -lấy khỏi G giả thuyết không phù hợp với d -Với s S không phù hợp với d: lấy s khỏi S thêm vào S s tổng quát hoá chi tiết h smà h phù hợp với D có phần tử G tổng quát h Lấy khỏi S giả thuyết tổng quát giả thuyết S +Nếu d ví dụ âm (c(x)=0) -lấy khỏi S giả thuyết không phù hợp với d Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin 26 Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mô thuật tốn Find-s -Với g G khơng phù hợp với d: lấy g khỏi G thêm vào G chi tiết hoá nhỏ h g mà h phù hợp với D có phần tử S chi tiết h Lấy khỏi G giả thuyết tổng uát giả thuyết G Một ví dụ minh hoạ Hình 2.4 biểu diễn thuật tốn áp dụng ví dụ đầu bảng 2.1 Tập biên khởi tạo G0 S0 1:< nắng, ấm, trung bình, mạnh, ấm, khơng đổi> c=1 2:< nắng, ấm, cao, mạnh, ấm, không đổi> S0: c=1 < , , , , , > < nắng, ấm, trung bình, mạnh, ấm, khơng đổi> S1: S2: < nắng, ấm, ?, mạnh, ấm, không đổi> G0 , G1 , G : Hình 2.4 xử lý ví dụ Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin 27 Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mơ thuật tốn Find-s Ví dụ dương tăng tổng quát biên chi tiết cịn ví dụ âm tăng chi tiết biên tổng quát Bây ta xét ví dụ 3: :< mưa, lạnh, cao, mạnh, ấm, đổi> ;c=0 minh hoạ hình 2.5 < nắng, ấm, ?, mạnh, ấm, không đổi> S2, S3: Hình 2.5 xử lý ví dụ Ví dụ 4: c=1 xử lý hình 2.6 S3: S4 G4 G3 : < nắng, ấm, ?, mạnh, ấm, không đổi> < nắng, ấm, ?, mạnh, ?, ?> mạnh,?,?> G4 Hình 2.7: VH, D 3.6 Các ý thuật tốn loại trừ ứng cử 1) khơng gian tường thuật có hội tụ tới giả thuyết khơng? Hội tụ mẫu đào tạo khơng có lỗi H có giả thuyết 2) Nên lấy ví dụ tiếp theo? Trường hợp đựoc xét ví dụ có thầy Nếu ta phải tạo thí dụ nên chon thí dụ thoả mãn nửa khơng gian tường thuật có vâyh ta giảm nửavà ta tìm giả thuyết với log2 VS thí nghiệm 3) Nhận biết mẫu Giả sử VH,D không có ví dụ mà giả thuyết thống ta xác định giá trị chung Khi khơng thống tuỳ theo tỷ lệ phân bố xác suất để định 3.7 Khuynh hƣớng quy nạp - Thuật tốn ta xét có giả thuyết H chứa giả thuyết Xét ví dụ : Các ví dụ ngày chơi khơng A Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin 29 Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mô thuật tốn Find-s Ví dụ Bầu trời nhiệt độ độ ẩm gió nước dự báo thích chơi nắng ấm trung bình mạnh mát đổi có mây ấm trung bình mạnh mát đổi có mưa ấm trung bình mạnh mát đổi không Giả thuyết chi tiết phù hợp với hai ví dụ đầu S2= < ?, ấm, trung bình, mạnh, mát, đổi> khơng với ví dụ Sở dĩ khuynh hướng học liên kết ràng buộc - Học khuynh hướng xét giả thuyết Định nghĩa 7: Xét L thuật toán học tập mẫu X Giả sử C khái niệm X, Dc = {x,c(x)}laf tập liệu đào tạo Giả sử L(xi, Dc) phân lớp gán cho xi L sau đào tạo Dc Khuynh hường đào tạo L tập khẳng định B cho với khái niệm đích c ví dụ đào tạo tương ứng Dc ta có: ( xi X ) (B Dc xi ) ├ L(xi,Dc) - Khuynh hướng quy nạp thuật toán loại trừ ứng cử khái niệm đích c thuộc vào khơng gian giả thuyết H Sơ đồ xử lý thuật tốn hình Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin 30 Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mơ thuật tốn Find-s Chƣơng :Thực nghiệm 4.1 Giới thiệu module mơ thuật tốn Find - S: Chương trình mơ em xây dựng Netbean 7.0 dùng ngơn ngữ lập trình Java 4.1.1 Mơ tả chung: * Đầu vào: - Xây dựng tập liệu đầu vào (tập mẫu) - Tạo tập liệu đầu vào - Mở tập liệu đầu vào có sẵn * Chạy chương trình để tìm giả thuyết chi tiết hay tập quy tắc dựa tập liệu đầu vào * Đầu ra: Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin 31 Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mơ thuật tốn Find-s - Tập quy tắc cho liệu đầu vào * Nhập vào liệu đầu vào tính kết (Yes ,No) dựa vào tập quy tắc 4.1.2 Chương trình : - Load Data: Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin 32 Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mơ thuật tốn Find-s Chạy thuật toán: Nhập phẩn tử kiểm tra: Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin 33 Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mô thuật toán Find-s Nhập tập liệu đầu vào: Load File Data: Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Cơng Nghệ Thơng Tin 34 Đồ án tốt nghiệp:Tìm hiểu học máy phương pháp học khái niệm.Xây dựng module mơ thuật tốn Find-s Sinh viên:Vũ Ngọc Nam, Khóa 11, Nghành Công Nghệ Thông Tin 35 ... án tốt nghiệp :Tìm hiểu học máy phương pháp học khái niệm. Xây dựng module mơ thuật tốn Find- s Chƣơng 1:Tổng Quan Về Học máy 1.1 Giới thiệu học máy Học máy, nhiều tài liệu gọi máy học lĩnh vực trí... nghiệp :Tìm hiểu học máy phương pháp học khái niệm. Xây dựng module mô thuật tốn Find- s Kiểu xác định tri thức để học Một cách biểu diễn tri thức đích Một cấu học 1.4 Các vấn đề học máy Việc học máy. .. Đồ án tốt nghiệp :Tìm hiểu học máy phương pháp học khái niệm. Xây dựng module mơ thuật tốn Find- s 3.5.4 Thuật toán loại trừ ứng cử Trong thuật toán ta khởi tạo G S giả thuyết G0 S0 giả thuyết tổng