Bài giảng Máy học và mạng Neural - Bài 1: Tổng quan về học máy - Vũ Đức Lung

Máy học và mạng neural (Machine Learning and Neural Network) Giảng viên: TS. Vũ Đức Lung Email: lungvd@uit.edu.vn 1 Bài 01 – Tổng quan về học máy  Vai trò của học máy trong trí tuệ nhân tạo.  Học máy là gì?  Ứng dụng của học máy.  Các lĩnh vực liên quan đến học máy.  Các bước của học máy.  Các vấn đề cơ bản trong học máy. Ví dụ về thuật toán học máy.  Cách tiếp cận của khoá học Những vấn đề cốt lõi của TTNT • Biểu diễn (representation). • Lập luận (reasoning). • Học (learning). • Tương tác (interaction). Tổng quan về học máy  Là một nhánh của trí tuệ nhân tạo  Liên quan đến việc phát triển các kĩ thuật cho phép các máy tính có thể “học”  Ở VN nằm trong môn học TTNT nâng cao  Trên thế giới là một môn học hoặc nhiều môn học riêng và được chú trọng giảng dạy ở bậc ĐH&SĐH 4 Học máy là gì?  Con người học như thế nào? – Nhớ và làm lại (học vẹt). – Học nhờ quan sát và khái quát hoá (học hiểu).  Các định nghĩa về Học máy (Machine learning) – Học là sự thay đổi thích ứng trong hệ thống giúp cho hệ thống có thể xử lý vấn đề ngày càng hiệu quả hơn khi gặp lại những tình huống tương tự [Simon, 1983] – Một quá trình mà một chương trình máy tính cải thiện hiệu suất của nó trong một công việc thông qua kinh nghiệm [Mitchell, 1997] (Học máy = Cải thiện hiệu quả một công việc thông qua kinh nghiệm) – Việc lập trình các máy tính để tối ưu hóa một tiêu chí hiệu suất dựa trên các dữ liệu ví dụ hoặc kinh nghiệm trong quá khứ [Alpaydin, 2004] 5 Học làm gì?khi nào học?  Học là cần thiết trong những môi trường chưa quen thuộc,  Học là một phương pháp hữu hiệu để xây dựng hệ thống  Học là cách để các chương trình thông minh có thể hiệu chỉnh hành vi để tăng hiệu quả giải quyết vấn đề.  Học khi nào: – Tri thức con người chưa đủ (VD Trên sao hỏa), – Con người không đủ khả năng giải thích(nhận dạng giọng nói) – Lời giải thay đổi theo thời gian (routing on a computer network) – Lời giải cần thích nghi trong từng trường hợp cụ thể (sinh vật học) Ứng dụng của học máy Hiện học máy được ứng dụng trên nhiều lĩnh vực do: Một loạt các thuật toán học máy ra đời. Cơ sở lý thuyết được xây dựng ngày càng đầy đủ.  Dữ liệu ngày càng nhiều và dư thừa nhưng tri thức cần thì thiếu.  Sức mạnh tính toán của máy tính được nâng cao.  Nhiều ngành khoa học mới nảy nở (VD Bioinformatics) Ứng dụng của học máy  Khai phá dữ liệu (Data Mining) Máy truy tìm dữ liệu (search engines)  Chẩn đoán y khoa (medical diagnosis)  Phát hiện thẻ tín dụng giả (Banking bảo mật thông tin),  Phân tích thị trường chứng khoán, thị trường tài chính (stock market analysis)  Phân loại các chuỗi DNA (bioinformatics )  Nhận dạng tiếng nói và chữ viết, dịch tự động, (speech and handwriting recognition, natural language processing)  Chơi trò chơi (game playing)  Chơi và cử động rô-bốt (robot locomotion). 8 Các phương pháp học máy  Inductive Concept Learning.  Decision Trees.  Artificial Neural Networks.  Bayesian Networks.  Support Vector Machines.  Learning Markov Processes.  Instance-Based (Lazy) Learning.  Learning by Explanation.  Learning by Reinforcement.  Heuristic Learning (GAs, GP, ...).  Rule Induction. ........ Các Lĩnh Vực Liên Quan  Artificial intelligence Computational complexity theory Bayesian methods Control theory Information theory Philosophy Psycholopy and neurobiology Statistics . Quy trình học máy 11 Các loại thuật toán Học máy 12 Các loại thuật toán Học máy (tiếp)  Học nửa giám sát : kết hợp các ví dụ có gắn nhãn và không gắn nhãn để sinh một hàm hoặc một bộ phân loại thích hợp.  Học tăng cường : trong đó, thuật toán học một chính sách hành động tùy theo các quan sát về thế giới. Mỗi hành động đều có tác động tới môi trường, và môi trường cung cấp thông tin phản hồi để hướng dẫn cho thuật toán của quá trình học. 13 14 Các loại thuật toán Học máy (tiếp)  Chuyển đổi: tương tự học có giám sát nhưng không xây dựng hàm một cách rõ ràng. Thay vì thế, cố gắng đoán kết quả mới dựa vào các dữ liệu huấn luyện, kết quả huấn luyện, và dữ liệu thử nghiệm có sẵn trong quá trình huấn luyện.  Học cách học: trong đó thuật toán học thiên kiến quy nạp của chính mình, dựa theo các kinh nghiệm đã gặp. Các bước trong học máy 1. Phát biểu bài toán: [Tom Mitchell, 1997] Học = Cải thiện khả năng thực hiện nhiệm vụ T của hệ thống dựa trên kinh nghiệm E với độ đo chất lượng thực hiện nhiệm vụ P. Ví dụ: Xây dựng chương trình chơi cờ tướng thông minh. T: chơi cờ tướng (người-máy, máy-máy). P: số phần trăm ván thắng khi chơi với các kiện tướng quốc gia. E: Kinh nghiệm từ những ván tự chơi (máy-máy) và chơi với người. Các bước trong học máy T: chơi cờ tướng (người-máy, máy-máy). P: số phần trăm ván thắng khi chơi với các kiện tướng quốc gia. Vấn đề: – Thu thập kinh nghiệm (dữ liệu) E ở đâu? – Như thế nào? – Đâu là thành phần cần học trong chương trình? – Biểu diễn thành phần đó như thế nào? – Dùng thuật toán gì để học? Các bước trong học máy 2. Xác định kiểu dữ liệu dùng cho huấn luyện:  Các thông tin hướng dẫn quá trình học (training feedback) được chứa ngay trong các ví dụ học (Phản hồi trực tiếp) hay được cung cấp gián tiếp (có trễ, ví dụ từ môi trường hoạt động hay trong quá trình hoạt động, ví dụ trong spam, nhận dạng giọng nói, nhận dạng chữ viết, nhận dạng ảnh vân tay,)?  Các dữ liệu học theo kiểu có giám sát hay không có giám sát? (có đầu ra lý tưởng không?).  Dữ liệu có mang tính đại diện cho hay tương thích với các ví dụ của hệ thống trong tương lai (future test examples) hay đích của quá trình học không? Các bước trong học máy 3. Xác định hàm mục tiêu: f: Board → Move. Xác định trực tiếp: V: Board → R Ví dụ định nghĩa hàm giá trị như sau: b là trạng thái cuối bàn cờ thắng cuộc: V(b)=100. b là trạng thái cuối bàn cờ thua cuộc: V(b)= -100. b là trạng thái bàn cờ hoà: V(b)=0. Nếu b không phải là trạng thái kết thì V(b)=V(b’). Trong đó b’ là trạng thái kết tốt nhất có thể đến được từ b thông qua chuỗi nước đi tối ưu. Các bước trong học máy 4. Xác định (lựa chọn) cách biểu diễn cho hàm mục tiêu cần học:  Dạng hàm đa thức (a polynomial function) trên các đặc trưng của bàn cờ? (ví dụ số lượng xe, pháo, mã, tốt, tượng, sỹ).  Mạng Neural nhân tạo (an artificial neural network)?  Tập luật (a set of rules)?  Cây quyết định (a decision tree)?  Biểu thức giải tích tiến hoá (analysis of evolution) từ lập trình GEN? Các bước trong học máy Xác định biểu diễn cho hàm mục tiêu: Ví dụ:  Dạng hàm đa thức trên các đặc trưng của bàn cờ? (ví dụ số lượng xe, pháo, mã, tốt, tượng, sỹ). V’(b) = w0+w1xe+w2ph+w3ma+w4to+w5tu+w6sy Các bước trong học máy 5. Lựa chọn một giải thuật học máy có thể học (xấp xỉ) được hàm mục tiêu: Hàm mục tiêu V(b). Hàm học được V’(b). Vtrain(b): Giá trị đầu ra lý tưởng trong tập mẫu. Ước lượng giá trị đầu ra lý tưởng: Vtrain(b)=V’(Successor(b)). Example: 4x4 checkers V(b)=0 + 1rp(b) + 2bp(b) Initial weights: 0=-10, 1 =75, 2 =-60 V(b0)=0 + 1*2 + 2*2 = 20 m1 : bb1 V(b1)=20 m2 : bb2 V(b2)=20 m3 : bb3 V(b3)=20 Example 4x4 checkers V(b1)=20 V(b0)=20 1. Compute error(b0) = Vtrain(b) – V(b0) = V(b1) – V(b0) = 0 2. For each board feature fi, update weight i  i +  fi error(b) 0  0 + 0.1 * 1 * 0 1  1 + 0.1 * 2 * 0 2  2 + 0.1 * 2 * 0 Example: 4x4 checkers V(b2)=20 V(b0)=20 V(b1)=20 V(b3)=20 Example: 4x4 checkers V(b4b)=-55 V(b4a)=20 V(b3)=20 Example 4x4 checkers V(b4)=-55 V(b3)=20 1. Compute error(b3) = Vtrain(b) – V(b3) = V(b4) – V(b3) = -75 2. For each board feature fi, update weight i  i +  fi error(b) : 0=-10, 1 =75, 2 =-60 0  0 - 0.1 * 1 * 75, 0 = -17.5 1  1 - 0.1 * 2 * 75, 1 = 60 2  2 - 0.1 * 2 * 75, 2 = -75 Example: 4x4 checkers V(b5)=-107.5 V(b4)=-107.5 0 = -17.5 , 1 = 60, 2 = -75 Example 4x4 checkers V(b6)=-167.5 V(b5)=-107.5 error(b5) = Vtrain(b) – V(b5) = V(b6) – V(b5) = -60 0=-17.5, 1 =60, 2 =-75 i  i +  fi error(b) 0  0 - 0.1 * 1 * 60, 0 = -23.5 1  1 - 0.1 * 1 * 60, 1 = 54 2  2 - 0.1 * 2 * 60, 2 = -87 Example 4x4 checkers V(b6)=-197.5 error(b6) = Vtrain(b) – V(b6) = Vf(b6) – V(b6) = 97.5 0=-23.5, 1 =54, 2 =-87 i  i +  fi error(b) 0  0 + 0.1 * 1 * 97.5, 0 = –13.75 1  1 + 0.1 * 0 * 97.5, 1 = 54 2  2 + 0.1 * 2 * 97.5, 2 = -67.5 Final board state: black won Vf(b)=-100 Các bước trong học máy Thuật toán học: Luật cập nhật trọng số LMS: Lặp: Chọn mẫu huấn luyện b ngẫu nhiên. 1. Tính lỗi: Error(b)=Vtrain(b) - V’(b). 2. Đối với mỗi đặc trưng fi của bàn cờ: wi = wi + c . fi . Error(b) Trong đó c là tốc độ học (ví dụ 0.1). Thiết kế các bước lựa chọn Determine Type of Training Experience Games against experts Games against self Table of correct moves BoardMove Determine Target Function BoardValue Determine Representation of Learned Function polynomial Linear function of six features Artificial neural network Determine Learning Algorithm Gradient descent Linear programming Completed design Một số vấn đề trong học máy  Khi nào một thuật toán học hoạt động tốt?  Số lượng mẫu ảnh hưởng đến chất lượng học như thế nào?  Ảnh hưởng của độ phức tạp của biểu diễn Khả năng xử lý nhiễu dữ liệu?  Khả năng tự sửa đổi cấu trúc biểu diễn?  Khả năng học được?  Sử dụng tri thức sẵn có?  Học theo mô phỏng sinh học và tự nhiên? Các vấn đề trong học máy 33 Các vấn đề trong học máy 34 Các vấn đề trong học máy 35 Các vấn đề trong học máy 36 Vấn đề over-fitting 37 Vấn đề over-fitting 38 Vấn đề over-fitting 39 Vấn đề over-fitting – ví dụ 40 Ví dụ học máy  Bài toán lọc SPAM: cho một tập các emails (training examples) đã được đánh dấu spam/ham, một thuật toán ML sẽ đưa ra một “bộ luật” (prediction rule) mà dùng nó có thể tự động lọc các emails trong tương lai vào spam folder hay inbox.  T, P, E?  Các mục tiêu? – độ chính xác cao (đừng filter email của sếp vào spam folder), – dùng ít tài nguyên tính toán (spam filter chứ có phải VS.NET đâu mà cần 4GB bộ nhớ và 2 phút để khởi động) – dùng ít training data (đừng bắt click spam/ham 3 năm liên tục rồi mới chịu làm việc) – có tính khái quát cao, tiếng Anh gọi là general-purpose (một thuật toán có thể dùng cho cả spam filter, web filter trong browser) – có prediction rule đơn giản 41 Ví dụ học máy 42 Người dùng thích cái gì? 43 Ví dụ học máy 44 Credit scoring 45 Credit scoring 46 Regression 47 Regression 48 49 Face Recognition Training examples of a person Test images Ví dụ học máy 50 Ví dụ học máy 51 Lựa chọn của khoá học Tiếp cận thuật toán đối với học máy: Tìm hiểu các thuật toán và mô hình học máy cơ bản như:  Học khái niệm  Cây quyết định,  Mạng Neural,  Mạng Bayesian,  Support Vector Machines,  Mô hình Markov ẩn,  Giải thuật di truyền  ... Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1) Resources: Datasets  UCI Repository:  UCI KDD Archive:  Statlib:  Delve:  BSDS500: nch/  fMRI: Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1) Resources: Journals  Journal of Machine Learning Research www.jmlr.org Machine Learning  Neural Computation  Neural Networks  IEEE Transactions on Neural Networks  IEEE Transactions on Pattern Analysis and Machine Intelligence  Annals of Statistics  Journal of the American Statistical Association  ... Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1) Resources: Conferences  International Conference on Machine Learning (ICML) – ICML05:  European Conference on Machine Learning (ECML) – ECML05:  Neural Information Processing Systems (NIPS) – NIPS05:  Uncertainty in Artificial Intelligence (UAI) – UAI05:  Computational Learning Theory (COLT) – COLT05:  International Joint Conference on Artificial Intelligence (IJCAI) – IJCAI05:  International Conference on Neural Networks (Europe) – ICANN05:  ...