Bài giảng Phương pháp nghiên cứu khoa học trong tin học - Hoàng Kiếm

0. Nguyên lý thực hiện sơ bộ 11. Nguyên lý dự phòng 12. Nguyên lý đẳng thế 66 II. Phương pháp giải quyết vấn đề theo khoa học về phát minh, sáng chế (tt) 13.Nguyên lý đảo ngược 14.Nguyên lý cầu (tròn) hóa 15.Nguyên lý năng động 16.Nguyên lý tác động bộ phận và dư thừa 17.Nguyên lý bộ xung chiều khác 18.Sự dao động cơ học 19.Nguyên lý tác đông theo chu kỳ 20.Nguyên lý tác đông liên tục hữu hiệu 21.Nguyên lý vượt nhanh 22.Nguyên lý chuyển hại thành thắng 67 II. Phương pháp giải quyết vấn đề theo khoa học về phát minh, sáng chế (tt) 23. Nguyên lý quan hệ phản hồi 24. Nguyên lý sử dụng trung gian 25. Nguyên lý tự phục vụ 26. Nguyên lý sao chép (copy) 27. Nguyên lý rẻ thay cho đắt 28. Nguyên lý thay thế sơ đồ cơ học 29. Nguyên lý sử dụng các kết cấu thủy và khí 30. Sử dụng bao mềm dẻo và mềm mỏng 31. Sử dụng vật liệu nhiều lỗ 68 32. Nguyên lý đổi màu 33. Nguyên lý đồng nhất 34. Nguyên lý loại bỏ và tái sinh từng phần 35. Đổi các thông số hóa lý của đối tượng 36. Sử dụng chuyển pha 37. Sử dụng nở nhiệt 38. Sử dụng các chất oxy hóa 39. Sử dụng môi trường trơ 40. Sử dụng vật liệu tổng hợp (composit) II. Phương pháp giải quyết vấn đề theo khoa học về phát minh, sáng chế (tt) 69 Đưa một bài toán vào máy tính Ngẫu nhiên, xác định bất định cục bộ Rõ ràng Đệ quy Cách giải Hữu hạn Đúng Gần đúng Không cân lúc nào cũng đúng Heuritic P MT Algorithm Program 70 Nguyên tắc 1 - Nguyên tắc phân nhỏ Nội dung: • Chia các đối tượng thành các thành phần độc lập • Làm đối tượng thành các thành phần tháo ráp • Tăng mức độ phân nhỏ đối tượng Nhận xét : • Nguyên tắc phân nhỏ thường dùng các nguyên tắc 2_Tách khỏi, 3_Phẩm chất cục bộ, 5_Kết hợp, 6_vạn năng CÁC VÍ DỤ MINH HỌA MỘT SỐ THỦ THUẬT TRONG CÁC BÀI TOÁN KỸ THUẬT 71 Minh họa a) Đoàn tàu hỏa là sự kết hợp nhiều toa xe sự phân nhỏ đòan tàu trành được ma sát lớn khi đi qua các cua quẹo. b) Bom bi là kết quả phân nhỏ: một quả bom mẹ chứa nhiều quả bom con, mỗi quả bom con chứa nhiều viên bi sát thương. Trong kỹ thuật lập trình, ai cũng biết một nguyên tắc cơ bản là modul hóa, nghĩa là phân nhỏ chương trình thành nhiều modul độc lập gọi là các chương trình con, thể nhiên chùng là các hàm hoặc các procedure Nguyên tắc 1 - Nguyên tắc phân nhỏ (tt) 72 Nguyên tắc 2_Nguyên tắc tách khỏi Nội dung • Tách thành phần gây phiền phất ra khỏi đôi tượng hoặc ngược lại. Trách lấy phần cần thiết. Minh họa a) Khi xử lý tín hiệu số có thể ta sẽ: Tách bỏ các nhiễu, phục hồi tín hiệu ban đầu Sóng mang tín hiệu: tách sóng để lấy tín hiệu cần thiết MỘT SỐ THỦ THUẬT TRONG CÁC BÀI TÓAN KỸ THUẬT 73 b) Thử vàng bằng nhiệt hoặc kim loại để: Thử bằng nhiệt (phun lửa): chất không phải vàng sẽ nóng chảy và lộ ra trước tiên Dùng hóa chất để trích vàng trong hổn hợp vàng-bạc. Dùng phép điện giải để mạ các đối tượng. Nguyên tắc 2_Nguyên tắc tách khỏi (tt) 74 Nguyên tắc 3_Nguyên tắc cục bộ Nội dung • Chuyển đối tượng (hay môi trường bên ngoài, tác động bên ngoài) có cấu trúc đồng nhất thành không đồng nhất. • Các phần khác nhau của đối tượng phải có các chất năng khác nhau • Mỗi phần của đối tượng phải có các chất năng khác nhau MỘT SỐ THỦ THUẬT TRONG CÁC BÀI TÓAN KỸ THUẬT 75 Minh họa a) Truyền động qua các bánh răng: các bộ phận cố định, khó tháo rời thì dùng chất liệu tốt, các bộ tiếp xúc khác để thay thế thì bằng nhựa hoặc bằng bạc thau. b) Các thợ rèn có các kỹ thuật rèn dao, rựa rất đặc sắc: nguyên than dao là loại thép thường, còn khu vực lưỡi dao, được rèn vào một thanh thép lò so chất lượng tốt tạo ra dao rất sắc, mềm dẽo (không gãy mẻ khi va chạm mạnh) nhưng lại rất dễ mài. Ta có thể nhớ lại thời chống Mỹ, bộ đội ta thường dùng các díp xe(thép cực tốt) để rèn thành dao, rựa để dùng, nhưng tới khi bị cùn thì bị vất đi vì rất khó mài sắt lại nếu không có công cụ đặc biệt. Nguyên tắc 3_Nguyên tắc cục bộ (tt) 76 Nguyên tắc 3_Nguyên tắc cục bộ (tt) c) Trong lập trình, trong một đọan chương trình, cần phân biệt các phẩm chất cục bộ: ở đâu là lõi của phần phần chương trình, phần khác là những thao tác phụ. Ví dụ : in tất cả các số nguyên trong phạm vi [2.10000]., với ìng thức in ra : mỗi hàng có 8 số nguyên tố, mỗi trang có 20 hàng, tạm dừng, như vậy, lỗi của chương trình (phẩm chất cục bộ) là phần kiểm tra n có phải số nguyên tố không, nếu phải thì in ra. d) Trong học tập, trong lớp học thường có 1 thủ lỉnh là lớp trưởng để điều hành lớp, tuy nhiên nế lớp chỉ có 1 thủ lỉnh thì để dẫn đến 1 lớp đồng nhất, một chiều, thiếu sống động sáng tạo, do đó cần tạo thêm nhiều thủ lỉnh ở một số lỉnh vực khác, tử đó phong trào học tập , sinh họat sẽ sôi nổi, sống động hơn. 77 MỘT SỐ THỦ THUẬT TRONG CÁC BÀI TÓAN KỸ THUẬT Nguyên tắc 4_Nguyên tắc phản đối xứng Nội dung: • Chuyển đối tượng có hìng dạng, tính chất đối xứng thành phản đối xứng Minh họa: • Truyền lực qua chất lỏng Chất lỏng A B 78 Nguyên tắc 4_Nguyên tắc phản đối xứng (tt) • Hệ thống phao nổi trong hồ chứa nước Trong hồ chứa nước, người ta gắn một phao nổi có 2 công dụng: khi mực nước xuống thấp, phao sẽ đóng công tắc hoặc mở van để bom nuớc vào, khi nước đầy, phao sẽ đóng van hoặc làm hở công tắc. 79 • Kềm mở các vòng roan: Trong các bộ phận cơ học vận hành có tốc độ cao, thường người ta khóa các con ốc lại bằng chốt bi hoặc bằng miếng roan dạng vành khăn. Để mở các vòng roan này người ta dùng một loại kềm phản đối xứng: càng bóp vào thì gọng kềm càng mở ra. Kềm Lực bóp vào Nguyên tắc 4_Nguyên tắc phản đối xứng (tt) 80 Nguyên tắc 5_Nguyên tắc kết hợp Nội dung: • Kết hợp các đối tượng đồng nhất hoặc các đối tượng dùng cho các hoạt động kế cận. • Kết hợp về mặt thời gian các hoạt động đồng nhất hoặc kế cận gian rỗi của CPU, tận dụng tài nguyên để cho ra hệ điều hành đa nhiệm, nhiều người dùng. MỘT SỐ THỦ THUẬT TRONG CÁC BÀI TÓAN KỸ THUẬT 81 Minh họa: • Dao xếp nhiều lưỡi với nhiều công dụng : dao dùng cắt, xẻ, có răng cưa để cưa rọc, mở nút chai bia, mở nút chai rượu, khui đồ hộp • Chương trình máy tính : Các ngôn ngữ cấp cao thường cho phép kết hợp mã nguồn của Assembly • Hệ điều hành : kết hợp thời Nguyên tắc 5_Nguyên tắc kết hợp(tt) 82 1. Mô hình thông tin ban đầu III. CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ TỔNG QUÁT Phân tích Phân chia Phân cấp Phân tích Phân loại 83 2. Các phương pháp phân tích vấn đề: a) Phân chia vấn đề: Ví dụ: tìm cặp điểm gần nhau nhất trong tập n điểm III. CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ TỔNG QUÁT (tt) є = min(1, 2) min(1, 2,3)1 3 2 є є 84 Ví dụ: Xác định phần đường thẳng qua 2 điểm x,y nằm trong phạm vi màn hình 6 7 8 1 2 3 45 9 III. CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ TỔNG QUÁT (tt) 85 b) Phân loại vấn đề Ci(P) = U Ci(P) Ci(P) : p P ,T(P) (class có thể phủ nhau) (class, classure) Ví dụ: nhận dạng chữ in Loại 2 chân : I Loại 3 chân : A, L, V, III. CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ TỔNG QUÁT (tt) 86 c) Phân công vấn đề Là một biến thể của nguyên lý phân nhỏ vấn đề Vấn đề A  { A1, A2,, An} P  { P1, P2,, Pn} 1 2 4 3 5 6 III. CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ TỔNG QUÁT (tt) 87 Ví dụ : vật liệu mới trong xây dựng là các tấm lợp vừa có công dụng che chắn, chống nóng, cách âm đồng thời chịu lực, do đó cấu tạo của nó có nhiều lớp : lớp trên cùng là lớp thép mạ kẽm, lớp dưới là vật cách nhiệt, cách âm, lớp chịu lực III. CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ TỔNG QUÁT (tt) 88 Ví dụ : Tân dược điều trị bệnh theo từng giai đoạn khác nhau, với chức năng khác nhau, do đó các loại dược chất bọc trong các lớp khác nhau, các vỏ bọc có thời gain phân hủy khác nhau nên khi uống vào, từng loại thuốc sẽ tác dụng vào cơ thể ở những thời điểm khác nhau. • • Hạt thuốc • • • •• • • • •• • • Các lớp vỏ III. CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ TỔNG QUÁT (tt) 89 d / Phân cấp bài toán Bài toán P  cấu trúc lại bài toán P’ Mô tả thô Mô tả tinh Ví dụ về xử lý hình ảnh Tìm xem một ảnh A nằm ở đâu trong ảnh B P Không gian Thời gian Khác III. CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ TỔNG QUÁT (tt) 90 Ảnh A Ảnh B Ảnh C X X X X X X Ảnh A: biến đổi thành một điểm bằng cách lấy độ xám trung bình của ma trận 5x5 Ảnh B: dựa vào các ảnh mẫu, biến đổi thành ảnh C là các điểm, ảng C nhỏ hơn ảnh B gấp 25 lần III. CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ TỔNG QUÁT (tt) 91 e) Phân tích: Yếu tố chính P  f1, f2,, fn Thành phần chính  c1, c2, ck Tương quan hồi qui : P  CiRCj Đệ qui : P  Pn  Pn+1 Fractals:tìm phân tố nhỏ nhất (atom) biểu diễn vấn đề Phân tích dấu hiệu, yếu tố, thành phần chính P P’ Nhận dạng X thực Đối sách các yếu tố Mô hình thực tế Mô hình thông tin đặc trưng III. CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ TỔNG QUÁT (tt) 92 Ví dụ : bài tóan nén ảnh_Kỹ thuật quadtree s (Có thể xem thêm trong Principles of Pictorial Information System Design_Tác giả Shi Kuo Chang_Trang 133-136) Trên bức ảnh nhị phân 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 2 3 I R F G F I204 314 C M N 224 324 334 104 III. CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ TỔNG QUÁT (tt) 93 A: nút đen toàn giá trị 0 : nút trắng toàn giá trị 1 : nút xám toàn giá trị 1 và 0 III. CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ TỔNG QUÁT (tt) 94 Ô lớn chia thành 4 ô nhỏ, nếu còn lẫn trị 0 hoặc 1 thì tiếp tục chia 4 cho đến khi các ô toàn giá trị 1 hoặc 0. Phân tích yếu tố: (factor analyse) X : (x1, x2,, xn)  f(f1, f2,, fn) Phân tích Fractal :  Atoms Ảnh Ảnh F Fourier F: phép biến Đổi Fourier Ảnh F cho biết qui luật, yếu tố chính của ảnh III. CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ TỔNG QUÁT (tt) 95 ABC, ABX, AAX, ABC, BB,BBC,BBX A (atom 1) AB (atom 2) ABC (atom 3) Atom1 Atom1 Chọn Atoms Bức ảnh sau khi atom hóa Các atom được chọn lọc Mọi ảnh đều có thể xuất phát từ những atom III. CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ TỔNG QUÁT (tt) Nén một cơ sở dữ liệu ( không phải là nén dữ liệu ) Xem nội dung một file văn bản 96 Tổng hợp P ~P P Q III. Các phương pháp tổng hợp vấn đề Tổ hợp (Combination) P=P1UP2U..Upn Đối hợp (Convolution) Kết hợp (Associate) X Y A: ma trận kết hợp Xk Yk Thêm một thông tin kết hợp với P để giải P Tổng hợp theo không gian và thời gian Tích hợp (Integration) Tích hợp tri thức khi Xây dựng hệ chuyên gia Phải có những phân tích về những sử lý để rút kink nghiệm 97 Tổng hợp theo không gian và thời gian a.) Không gian của P P: DDi=D DiDj= PD1 PD2 PD3 ------------- PDK Ví dụ: Buffering và Dithering phân chia không gian và điều kiện biến. P D1 Domain III. Các phương pháp tổng hợp vấn đề (tt) 98 b.) Thời gian giải quyết P T0 Pre Pro Pos T • Paralell • Conection c.) Không gian và thời gian Kết hợp không gian và thời gian III. Các phương pháp tổng hợp vấn đề (tt) 99 IV. CÁC PHƯƠNG PHÁP NGHIÊN CỨU , GIẢI QUYẾT VẤN ĐỀ - BÀI TOÁN TRONG TIN HỌC - Phương pháp trực tiếp - Phương pháp gián tiếp - Phương pháp Heuristic - Phương pháp trí tuệ nhân tạo - Mạng Neural - Thuật giải di truyền - . 100 IV. CÁC PHƯƠNG PHÁP NGHIÊN CỨU , GIẢI QUYẾT VẤN ĐỀ - BÀI TOÁN TRONG TIN HỌC 1. Phương pháp trực tiếp Đặc điểm của cách giải quyết vấn đề này là : - Xác định trực tiếp được lời giải qua một thủ tục tính toán (công thức, hệ thức, định luật,) hoặc qua các bước căn bản để có được lời giải. - Việc giải quyết vấn đề trên máy tính chỉ là thao tác lập trình hay là sự chuyển đổi lời giải từ ngôn ngữ bên ngoài sang các ngôn ngữ được sử dụng trong máy tính. 101 1. Phương pháp trực tiếp (tt) Các nguyên lý áp dụng trong phương pháp trực tiếp : - Nguyên lý 1 : Chuyển đổi dữ liệu bài toán thành dữ liệu của chương trình, có nghĩa là “Dữ liệu của bài tóan sẽ được biểu diễn lại dưới dạng các biến của chương trình thông qua các quy tắc xác định của ngôn ngữ lập trình cụ thể” 102 1. Phương pháp trực tiếp (tt) - Nguyên lý 2 : Chuyển đổi quá trình tính toán của bài toán thành các cấu trúc của chương trình, có nghĩa là “Mọi quá trình tính toán đều có thể mô tả và thực hiện dựa trên ba cấu trúc cơ bản : Cấu trúc tuần tự, cấu trúc rẽ nhánh và cấu trúc lặp”. 103 1. Phương pháp trực tiếp (tt) - Nguyên lý 3 : Biểu diễn các tính toán chính xác, có nghĩa là “Chương trình tính toán theo các biểu thức chính xác không đồng nhất với quá trình tính toán chính xác về mặt hình thức”. - Nguyên lý 4 : Biểu diễn các tính toán gần đúng bằng cấu trúc lặp, có nghĩa là “Mọi quá trình tính toán gần đúng đều dựa trên các cấu trúc lặp với tham số xác định”. 104 - Nguyên lý 5 : Phân chi bài toán ban đầu thành những bài toán nhỏ hơn, có nghĩa là “Mọi vấn đề-bài toán đều có thể giải quyết bằng cách phân chia thành những vấn đề-bài toán nhỏ hơn”. - Nguyên lý 6 : Biểu diễn các tính toán không tường minh bằng đệ quy, có nghĩa là “Quá trình đệ quy trong máy tính không đơn giản như các biểu thức quy nạp trong toán học”. 1. Phương pháp trực tiếp (tt) 105 IV. CÁC PHƯƠNG PHÁP NGHIÊN CỨU , GIẢI QUYẾT VẤN ĐỀ - BÀI TOÁN TRONG TIN HỌC (tt) 2. Phương pháp gián tiếp : - Phương pháp này được sử dụng khi chưa tìm ra lời giải chính xác của vần đề. - Đây cũng chính là cách tiếp cận chủ yếu của loài người từ xưa đến nay. - Đưa ra những giải pháp mang đặc trưng của máy tính, dựa vào sức mạnh tính toán của máy tính. nhiên. - Một lời giải trực tiếp bao giờ cũng tốt hơn, nhưng không phải lúc nào cũng có. 106 CÁC PHƯƠNG PHÁP TÌM KIẾM LỜI GIẢI VÉT CẠN TOÀN BỘ VÉT CẠN THEO KIỂU M ẮT LƯỚI VÉT CẠN TUYẾN TÍNH VÉT CẠN CÓ CẤU TRÚC TÌM KIẾM CHIỀU SÂU(MÊ CUNG) TÌM KIẾM CHIỀU RỘNG THỬ - SAI PHÂN LỚP ĐƠN GIẢN ĐIỀU KIỆN RÚT GỌN KHÔNG GIAN TÌM KIẾM TRƯỚC KHI TÌM KIẾM TRONG KHI TÌM KIẾM NHÁNH CẬN HEURISTIC LEO NÚI ĐƠN GIẢN DỐC ĐỨNG BFS A* 107 2. Phương pháp gián tiếp (tt) Các phương pháp gián tiếp Phương pháp thử – sai Khi xây dựng lời giải bài toán theo phương pháp thử – sai, người ta thường dựa vào 3 nguyên lý sau : - Nguyên lý vét cạn : Đây là nguyên lý đơn giản nhất, liệt kê tất cả các trường hợp có thể xảy ra. 108 2. Phương pháp gián tiếp (tt) - Nguyên lý ngẫu nhiên : Dựa vào việc thử một số khả năng được chọn một cách ngẫu nhiên. Khả năng tìm ra lời giải đúng phụ thuộc rất nhiều vào chiến lược chọn ngẫu nhiên. - Nguyên lý mê cung : Nguyên lý này được áp dụng khi chúng ta không thể biết được chính xác “hình dạng” lời giải mà phải xây dựng dần lời giải qua từng bước một giống như tìm đường đi trong mê cung. 109 2. Phương pháp gián tiếp (tt) Để thực hiện tốt phương pháp thử - sai, chúng ta nên áp dụng các nguyên lý sau : - Nguyên lý vét cạn toàn bộ: Muốn tìm được cây kim trong đống rơm, hãy lần lượt rút ra từng cọng rơm cho đến khi rút được cây kim - Nguyên lý mắt lưới : Lưới bắt cá chỉ bắt được những con cá có kích thước lớn hơn kích thước mắt lưới. 110 - Nguyên lý giảm độ phức tạp của thử và sai : Thu hẹp trường hợp trước và trong khi duyệt, đồng thời đơn giản hóa tối đa điều kiện chấp nhận một trường hợp. - Nguyên lý thu gọn không gian tìm kiếm : Loại bỏ những trường hợp hoặc nhóm trường hợp chắc chắn không dẫn đến lời giải. - Nguyên lý đánh giá nhánh cận: Nhánh có chứa quả phải nặng hơn trọng lượng của quả. 2. Phương pháp gián tiếp (tt) 111 2. Phương pháp gián tiếp (tt) Phương pháp Heuristic - Phương pháp Heuristic có đặc điểm là đơn giản và gần gủi với cách suy nghĩ của con người, cho ra được những lời giải đúng trong đa số các trường hợp áp dụng. - Các thuật giải Heuristic được xây dựng dựa trên một số nguyên lý rất đơn giản như : -- Vét cạn thông minh -- Tối ưu cục bộ (Greedy) -- Hướng đích” -- Sắp thứ tự 112 Để thực hiện tốt phương pháp Heuristic, chúng ta nên áp dụng các nguyên lý sau : - Nguyên lý leo núi : Muốn leo lên đến đỉnh thì bước sau phải “cao hơn” bước trước. - Nguyên lý chung : Chọn hướng đi triển vọng nhất trong số những hướng đi đã biết. 2. Phương pháp gián tiếp (tt) 113 2. Phương pháp gián tiếp (tt) Phương pháp trí tuệ nhân tạo - Phương pháp trí tuệ nhân tạo dựa trên trí thông minh của máy tính. - Phương pháp này, người ta sẽ đưa vào máy trí thông minh nhân tạo giúp máy tính bắt chước một phần khả năng suy luận như con người, máy tính dựa trên những điều đã được “học“ để tự đưa ra phương án giải quyết vấn đề. 114 2. Phương pháp gián tiếp (tt) 115 Phương pháp trí tuệ nhân tạo (tt) Trong lĩnh vực “máy học” , các hình thức học có thể phân chia như sau : - Học vẹt - Học bằng cách chỉ dẫn - Học bằng qui nạp - Học bằng tương tự - Học dựa trên giải thích - Học dựa trên tình huống - Khám phá hay học không giám sát 116 Các kỹ thuật thường được áp dụng trong “máy học” là : - Khai khoáng dữ liệu - Mạng nơ ron - Thuật giải di truyền - Phương pháp trí tuệ nhân tạo (tt) 117 Thế nào là máy học (Learning Machine) ? Máy tính hay chương trình máy tính có khả năng tự hoàn thiện từ “kinh nghiệm”. Máy học còn có nghĩa là việc mô hình hóa môi trường xung quanh hay khả năng một chương trình máy tính sinh ra một cấu trúc dữ liệu mới khác với cấu trúc hiện có. Chẳng hạn việc tìm ra những luật Ifthen từ tập dữ liệu đầu vào. (Krzysztof J. Cios, Witold Pedrycz, Roman W. Swiniarski. Data Mining Methods for Knowledge Discovery. Kluwer Academic Publishers, 1998) 118 Phân loại máy học Phân loại thô:  Học giám sát (supervised learning)  Học không giám sát (unsupervised learning) Phân loại theo 2 tiêu chuẩn : “cấp độ học” và “cách tiếp cận” Cấp độ học: - Học vẹt (Rote learning) - Học theo giải thích (by explanation) - Học theo ví dụ, trường hợp (by examples, cases) - Học khám phá (by discovering) 119 Cách tiếp cận: Tiếp cận thống kê Tiếp cận toán tử logic Tiếp cận hình học (phân hoạch không gian, xây dựng cây định danh, ) Tiếp cận mạng Neural Tiếp cận khai mỏ dữ liệu  Phân loại máy học (tt) 120 1.Tiếp cận thống kê Ví dụ: Chương trình đoán ý nghĩ con người. Máy sẽ đoán người chơi nghĩ số 0 hay 1 trong đầu, người chơi sẽ phải trả lời cho máy biết là máy đã đoán đúng hay sai. Để từ đó máy tính sẽ học qui luật suy nghĩa của người chơi. 1 Máy đoán là 0 Máy đoán sai 121 Ý tưởng cài đặt: hết sức đơn giản - Lưu trữ toàn bộ dãy số 0, 1 mà người chơi đã nghĩ ra. - Lấy 7 con số trước đó (người chơi đưa ra), tính xác suất xuất hiện của số 1 và số 0 sau dãy 7 con số này. Máy sẽ đoán số có xác suất xuất hiện cao hơn. Giả sử ở lần đoán thứ i, dãy số mà người dùng đã đoán như sau: 1 1 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 ? Từ dữ liệu lưu trữ ở những lần đoán trước, giả sử số lần xuất hiện của 1 sau dãy 0 0 0 0 1 0 0 là 28 và số lần xuất hiện của số 0 là 90 Xác suất xuất hiện của số 1 sau dãy này là: 28/(28+90) = 23.7% Xác suất xuất hiện của số 0 sau dãy này là: 90/(28+90) = 76.3% Máy sẽ đoán số 0 122 1.Tiếp cận thống kê (tt) Nhận xét ví dụ:  Ví dụ đã đưa ra là thuộc cấp độ học vẹt sử dụng cách tiếp cận thống kê. Máy không thể đoán đúng ngay được, nhưng càng về sau (vài trăm lần đoán) máy càng trở nên chính xác một cách kinh ngạc (trung bình có thể lên đến 90%).  Trên thực tế khi cài đặt chương trình này tác giả không chỉ đoán qui luật từ dãy số của người chơi, máy còn sử dụng cả dãy số mà máy đã đoán 123 2.Tiếp cận hình học Xét bài toán: cho tập các hình chữ nhật với kích thước (ngang & rộng) và màu sắc khác nhau (hình vẽ). Cho biết hình bên phải có màu gì? Vaøng Tía Ñoû amC Xanh laù caây Xanh döông Tím ? Ñoû 124 2.Tiếp cận hình học (tt) Giải quyết bài toán:  Phản ứng tự nhiên của con người: tìm khối có sẵn gần giống để đoán màu cho khối chưa biết. Như thế nào là gần giống ?  Biểu diễn 2 thuộc tính chiều rộng & chiều cao dưới dạng 1 điểm trên mặt phẳng 2 chiều.  Tính khoảng cách từ khối cần tìm đến tất cả các khối còn lại. (bài toán người láng giềng gần nhất với độ phức tạp O(n)). Ñoû amC U Ñoû Tím Xanh döông Xanh laù caây Tía Vaøng 0 2 4 6 2 4 6 125 3.Tiếp cận logic Ví dụ 1: Baïn haõy thöû tìm ñaëc tính ñeå phaân bieät hai nhoùm hình aûnh A vaø B döôùi ñaây. 126 Nhận xét ví dụ 1:  Nếu tinh ý bạn sẽ nhận thấy các điểm trắng trong nhóm A luôn thẳng hàng.  Thật khó để phát hiện ra đặc tính vừa nêu trên (ngay cả đối với con người) nhất là đối với các đối tượng hình học.  Nhà bác học Bongard đã đề ra một phương án xác định mối liên hệ bằng cách xây dựng các mệnh đề logic. (xem ví dụ 2) 3.Tiếp cận logic (tt) 127 3.Tiếp cận logic (tt) Ví dụ 2: Xác định đặc điểm của các nhóm hình A, B Nhoùm A Nhoùm B 128 3.Tiếp cận logic (tt) Nhận xét ví dụ 2:  Nhoùm A : Toång soá ñænh tröø toång soá ñoái töôïng = 7. (Chaúng haïn nhö hình 2 trong nhoùm A coù 3 hình goàm 2 tam giaùc vaø moät hình chöõ nhaät, toång coäng coù 10 ñænh).  Nhoùm B : Toång soá ñænh tröø toång soá ñoái töôïng = 6.  Hình ellipse vaø hình troøn ñöôïc xem laø khoâng coù ñænh naøo  Khoâng ñöôïc gôïi yù thì quan hệ treân laø moät loaïi quan heä raát khoù ñöôïc phaùt hieän.  Vôùi phöông aùn cuûa Bongard, ta vaãn coù theå tìm ra ñöôïc moái lieân heä ñuû ñeå phaân bieät hai nhoùm hình naøy. 129 4.Học dựa trên cây định danh  Döïa treân yù töôûng cuûa tieáp caän hình hoïc laø phaân chia khoâng gian baøi toaùn taïo thaønh moät caây quyeát ñònh, ngöôøi ta ñaõ xaây döïng caùc phöông phaùp hoïc döïa treân vieäc xaây döïng caây ñònh danh.  Xây dựng cây định danh bằng cách tìm các qui luật của dữ liệu. 130 4.Học dựa trên cây định danh (tt) Teân Toùc h.aoC C Caân Naëng Duøng kem? Keát quaû arahS Vaøng T.Bình Nheï Khoâng Chaùy anaD Vaøng aoC T.Bình Coù Khoâng lexA Naâu Thaáp T.Bình Coù Khoâng nnieA Vaøng Thaáp T.Bình Khoâng Chaùy milieE Ñoû T.Bình Naëng Khoâng Chaùy eterP Naâu aoC Naëng Khoâng Khoâng ohnJ Naâu T.Bình Naëng Khoâng Khoâng artieK Vaøng Thaáp Nheï Coù Khoâng 131 4.Học dựa trên cây định danh (tt)  Đề xuất phương pháp giải quyết  Đâm chồi Maøu toùc lexA eterP ohnJ arahS anaD nnieA artieK mmileE Pvaøng = { arahS , ana, D nnieA , artie }K Pnaâu = { lex, eter, ohn } A P J Pñoû = { mmileE }  Caùc ngöôøi bò chaùy naéng ñöôïc gaïch döôùi vaø in ñaäm.  Pvaøng laø coøn laãn loän ngöôøi chaùy naêng vaø khoâng chaùy naéng. 132 4.Học dựa trên cây định danh (tt)  Quan saùt thuoäc tính chieàu cao. Thuoäc tính naøy giuùp phaân hoaïch taäp Pvaøng thaønh 3 taäp con : P Vaøng, Thaáp = {nnieA , art ie}K PVaøng, T. Bình= {arahS } P Vaøng,aoC = { anaD } Chieàu cao Thaáp T.Bình aoC arahSnnieA artieK anaD Maøu toùc lexA eterP ohnJ arahS anaD nnieA artieK mmileE 133 4.Học dựa trên cây định danh (tt)  Caây ñònh danh cuoái cuøng: Duøng kem Coù Khoâng anaD artieK arahS nnieA Maøu toùc lexA eterP ohnJ arahS anaD nnieA artieK mmileE 134 5.Tiếp cận mạng Neural  Maïng neural laø thuaät ngöõ noùi ñeán moät phöông phaùp giaûi quyeát vaán ñeà – baøi toaùn treân maùy tính moâ phoûng theo hoaït ñoäng cuûa caùc teá baøo thaàn kinh trong naõo boä.  Maïng neural nhaân taïo laø söï moâ phoûng caáu truùc cuûa maïng neural sinh hoïc. Maïng neural nhaân taïo ñöôïc taïo thaønh bôûi söï noái keát giöõa raát nhieàu ñôn vò thaàn kinh goïi laø perceptron. Nhaùnh Truïc Khôùp Thaân Caáu truùc cuûa moät teá baøo thaàn kinh sinh hoïc 135 fxiwi y x1 x2 xn-1 xn w1 w2 wn-1 wn  Cấu tạo moät ñôn vò thaàn kinh nhaân taïo (nhö hình vẽ) Giaù trò ñaàu ra y cuûa moät perceptron ñöôïc tính baèng coâng thöùc sau: y = f((x nwn+ x n- 1wn- 1 + + w 2n 2 + w 1n 1 + w 0) - ) (  ñöôïc goïi laø ngöôõng kích hoaït cuûa neural ) Haøm f ñöôïc goïi laø haøm truyeàn. Moät haøm truyeàn caàn phaûi coù tính chaát sau : - bò chaën - ñôn ñieäu taêng - haøm lieân tuïc 5.Tiếp cận mạng Neural 136 5.Tiếp cận mạng Neural (tt) Mô hình minh họa mạng neural 1 lớp Units Input Unit output Cung liên kết (trọng số Wj) 137 5.Tiếp cận mạng Neural (tt) Mô hình minh họa mạng neural tổng quát Các unit input Các unit ẩn Các unit output Ik Wk,j aj Wj, i Oi 138 5.Tiếp cận mạng Neural (tt) Mạng lan truyền (Feed Forward) I1 I2 H3 H4 O5 W24 W23 W14 W13 W35 W45 Nguyên tắc xác định giá trị Output của node 5: a5 = f (W3,5a3 + W4,5a4) = f (W3,5 f(W1,3a1 + W2,3a2) + W4,5 f(W1,4a1 + W2,4a2)) 139 5.Tiếp cận mạng Neural (tt) Mạng Hopfield Mạng Hopfield hoạt động tương tự hoạt động một bộ nhớ kết hợp có: Wi,j = Wj,i +3-2 -1+1 +2 +1 -1 +1 -1 +3-1 +3-2 -1+1 +2 +1 -1 +1 -1 +3-1 140 5.Tiếp cận mạng Neural (tt) Mạng Perceptron Các unit input Các unit output Ij Wj,i Oi Các unit input Các unit output Ij Wj,i Oi Perceptron đơn lẻ 141 5.Tiếp cận mạng Neural (tt) Các unit input Các unit ẩn Các unit output xk Wk,j aj Wj, i Oi Mạng lan truyền ngược (back propagation) 142 Các ví dụ minh họa Áp dụng một số thủ thuật trong các bài toán tin học V.1 Nguyên Tắc Phân Nhỏ - Chia đối tượng thành các phần độc lập - Làm đối tượng thành các phần tháo lắp được - Tăng mức độ phân nhỏ của các đối tượng Chúng ta lấy ví dụ bài toán tìm kiếm nhị phân, ta chia đôi dãy phần tử, mỗi lần tìm kiếm chỉ tìm kiếm một nửa dãy.