›

Bài giảng Nhập môn trí tuệ nhân tạo - Chương 7: Nhập môn học máy - Ngô Hữu Phúc

pdf 91 trang cucquyet12 4530
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Nhập môn trí tuệ nhân tạo - Chương 7: Nhập môn học máy - Ngô Hữu Phúc", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_nhap_mon_tri_tue_nhan_tao_chuong_7_nhap_mon_hoc_ma.pdf

Nội dung text: Bài giảng Nhập môn trí tuệ nhân tạo - Chương 7: Nhập môn học máy - Ngô Hữu Phúc

  1. NHẬP MÔN TRÍ TUỆ NHÂN TẠO CHƯƠNG 7 Nhập môn học máy Bộ môn Khoa học máy tính Biên soạn: TS Ngô Hữu Phúc 1 Chương 7: Nhập môn máy học
  2. Thông tin chung  Thông tin về nhóm môn học: TT Họ tên giáo viên Học hàm Học vị Đơn vị công tác (Bộ môn) 1 Ngô Hữu Phúc GVC TS BM Khoa học máy tính 2 Trần Nguyên Ngọc GVC TS BM Khoa học máy tính 3 Hà Chí Trung GVC TS BM Khoa học máy tính 4 Trần Cao Trưởng GV ThS BM Khoa học máy tính  Thời gian, địa điểm làm việc: Bộ môn Khoa học máy tính Tầng 2, nhà A1.  Địa chỉ liên hệ: Bộ môn Khoa học máy tính, khoa Công nghệ thông tin.  Điện thoại, email: 069-515-329, ngohuuphuc76.mta@gmail.com. 2 Chương 7: Nhập môn máy học
  3. Cấu trúc môn học  Chương 1: Giới thiệu chung.  Chương 2: Logic hình thức.  Chương 3: Các phương pháp tìm kiếm mù.  Chương 4: Các phương pháp tìm kiếm có sử dụng thông tin.  Chương 5: Các chiến lược tìm kiếm có đối thủ.  Chương 6: Các bài toán thỏa rằng buộc.  Chương 7: Nhập môn học máy. 3 Chương 7: Nhập môn máy học
  4. Bài 7: Nhập môn máy học Chương 7, mục: 7.1 – 7.5 Tiết: 1-3; 4-6; Tuần thứ: 11,12 (xây dựng ứng dụng chương 6),13,14,15 (xây dựng ứng dụng chương 7) . Mục đích, yêu cầu: 1. Nắm được khái niệm về máy học. 2. Nắm được phương pháp học quy nạp. 3. Nắm được phương pháp xây dựng cây quyết định. 4. Nắm được phương pháp học trong Mạng Neural. Hình thức tổ chức dạy học: Lý thuyết. Thời gian: 6 tiết. Địa điểm: Giảng đường do Phòng Đào tạo phân công Nội dung chính: (Slides) 4 Chương 7: Nhập môn máy học
  5. Nội dung 7.1. Khái niệm về máy học? (4) 7.2. Học quy nạp. 7.3. Học với cây quyết định. 7.4. Học trong Mạng Neural. • Mạng Perceptron. • Mạng Perceptron đa lớp với thuật giải BP. 5 Chương 7: Nhập môn máy học
  6. 7.1. Khái niệm về máy học (1/4)  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).  Định nghĩa của H. Simon. “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ự” 6 Chương 7: Nhập môn máy học
  7. 7.1. Khái niệm về máy học (2/4) Học làm gì?  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 đề. 7 Chương 7: Nhập môn máy học
  8. 7.1. Khái niệm về máy học (3/4) Học của tác tử: . Environment: Môi trường. . Sensors: cảm biến. . Critic: phân tích, đánh giá. . Effectors: 8 Chương 7: Nhập môn máy học
  9. 7.1. Khái niệm về máy học (4/4) Xây dựng module học cho hệ thống:  Việc xây dựng module học cho hệ thống phải tính đến yếu tố:  Phần nào cần học để tăng hiệu năng giải quyết vấn đề.  Thông tin phản hồi đối với phần học của hệ thống.  Cách biểu diễn tri thức cần học.  Dạng thông tin phản hồi:  Học có giám sát: trả lời chính xác cho các câu hỏi.  Học không giám sát: không có câu trả lời chính xác.  Học tăng cường: giành lấy phần thưởng nếu làm đúng. 9 Chương 7: Nhập môn máy học
  10. 7.2. Học quy nạp  Ví dụ: học một hàm từ mẫu ví dụ. f là hàm mục tiêu Một mẫu ví dụ là một cặp (x, f(x)) Bài toán: Tìm giả thuyết h sao cho h ≈ f dựa trên tập mẫu cho trước Mô hình đơn giản hoá việc học:  Không tính đến tri thức có sẵn  Giả sử tập mẫu là có đủ. 10 Chương 7: Nhập môn máy học
  11. Phương pháp học quy nạp  Xây dựng h gần với f trên tập huấn luyện  (h được gọi là nhất quán với f trên tập mẫu)  E.g., khớp đường cong: 11 Chương 7: Nhập môn máy học
  12. Phương pháp học quy nạp  Xây dựng h gần với f trên tập huấn luyện  (h được gọi là nhất quán với f trên tập mẫu)  E.g., khớp đường cong: 12 Chương 7: Nhập môn máy học
  13. Phương pháp học quy nạp  Xây dựng h gần với f trên tập huấn luyện  (h được gọi là nhất quán với f trên tập mẫu)  E.g., khớp đường cong: 13 Chương 7: Nhập môn máy học
  14. Phương pháp học quy nạp  Xây dựng h gần với f trên tập huấn luyện  (h được gọi là nhất quán với f trên tập mẫu)  E.g., khớp đường cong: 14 Chương 7: Nhập môn máy học
  15. Phương pháp học quy nạp  Xây dựng h gần với f trên tập huấn luyện  (h được gọi là nhất quán với f trên tập mẫu)  E.g., khớp đường cong: 15 Chương 7: Nhập môn máy học
  16. Phương pháp học quy nạp  Xây dựng h gần với f trên tập huấn luyện  (h được gọi là nhất quán với f trên tập mẫu)  E.g., khớp đường cong:  Ockham’s razor: ưu tiên những giả thiết nào xấp xỉ tốt hàm mục tiêu và càng đơn giản càng tốt 16 Chương 7: Nhập môn máy học
  17. 7.3. Học các cây quyết định Bài toán: Học xem khi nào thì nên ngồi bàn đợi tại một restaurant: 1. Alternate: Có restaurant nào cạnh đây không? 2. Bar: Liệu có khu vực quầy bar có thể ngồi không? 3. Fri/Sat: hôm nay là thứ 6 hay thứ 7? 4. Hungry: có đang đói không? 5. Patrons: Số người trong restaurant (None, Some, Full) 6. Price: khoảng giá ($, $$, $$$) 7. Raining: ngoài trời có mưa không? 8. Reservation: đã đặt trước chưa? 9. Type: loại restaurant (French, Italian, Thai, Burger) 10. WaitEstimate: thời gian chờ đợi (0-10, 10-30, 30-60, >60) 17 Chương 7: Nhập môn máy học
  18. Biểu diễn thuộc tính giá trị  Các mẫu được biểu diễn bằng các thuộc tính và giá trị (Boolean, discrete, continuous)  Nhiệm vụ đặt ra là phân loại xem trường hợp nào trong tương lai là positive (T) hay negative (F) 18 Chương 7: Nhập môn máy học
  19. Cây quyết định  Biểu diễn giả thiết cần học.  Ví dụ: 19 Chương 7: Nhập môn máy học
  20. Khả năng biểu diễn  Cây quyết định có khả năng dùng để biểu diễn bất cứ hàm nào.  E.g. hàm Boolean:  Với một cây quyết định nhất quán với tập mẫu huấn luyện thì mỗi input, output của hàm tương ứng với một đường đi trong cây. Nhưng cũng có thể khả năng khái quát hoá không cao đối với các ví dụ mới chưa biết.  Ưu tiên tìm cây có độ phức tạp nhỏ. 20 Chương 7: Nhập môn máy học
  21. Không gian giả thuyết Số lượng cây quyết định cho hàm Boolean = = Số lượng hàm boolean n = số lượng bảng luận ý với 2n hàng = 22  E.g., nếu có 6 thuộc tính Boolean, có 18,446,744,073,709,551,616 cây 21 Chương 7: Nhập môn máy học
  22. Thuật toán học cây quyết định  Mục đích: Tìm cây nhỏ nhất quán với tập mẫu huấn luyện.  Ý tưởng: Tìm kiếm heuristic chọn thuộc tính quan trọng nhất để phân tách (đệ quy) 22 Chương 7: Nhập môn máy học
  23. Chọn thuộc tính  Ý tưởng: chọn thuộc tính (giá trị) sao cho sao cho nó giúp phân tách tập mẫu thanh hai tập thuần khiết (chỉ có positive hay chỉ có negative).  Patrons? là lựa chọn tốt hơn 23 Chương 7: Nhập môn máy học
  24. Sử dụng lý thuyết thông tin  để cài đặt Choose-Attribute trong thuật toán DTL:  Lượng thông tin (Entropy): I(P(v1), , P(vn)) = Σi=1 -P(vi) log2 P(vi)  Đối với tập có p mẫu positive và n negative: p n p p n n I( , ) log log p n p n p n 2 p n p n 2 p n 24 Chương 7: Nhập môn máy học
  25. Lợi thông tin (Information gain)  chọn thuộc tính A chia tập huấn luyện E thành các tập con E1, , Ev tính theo giá trị của A, và giả sự A có v giá trị khác nhau. v p n p n remainder(A)  i i I( i , i ) i 1 p n pi ni pi ni  Lợi thông tin (IG) là độ giảm trong entropy trong việc test thuộc tính: p n IG(A) I( , ) remainder(A) p n p n  Chọn thuộc tính có IG lớn nhất 25 Chương 7: Nhập môn máy học
  26. Lợi thông tin (Information gain) Trong tập mẫu của ví dụ, p = n = 6, I(6/12, 6/12) = 1 bit Xét thuộc tính Patrons và Type (và các thuộc tính khác): 2 4 6 2 4 IG(Patrons) 1 [ I(0,1) I(1,0) I( , )] .541 bits 12 12 12 6 6 2 1 1 2 1 1 4 2 2 4 2 2 IG(Type) 1 [ I( , ) I( , ) I( , ) I( , )] 0 bits 12 2 2 12 2 2 12 4 4 12 4 4 Patrons có giá trị IG cao nhất nên được DTL chọn làm gốc của cây quyết định. 26 Chương 7: Nhập môn máy học
  27. Lợi thông tin (Information gain)  Cây quyết định học bởi DTL từ 12 ví dụ:  Nhỏ hơn cây quyết định đưa ra lúc đầu 27 Chương 7: Nhập môn máy học
  28. Khi nào học tốt?  Làm sao chắc rằng h ≈ f ? 1. sử dụng các kết quả trong thống kê và học thống kê. 2. Thử h trên tập ví dụ mới (test set) Learning curve = % Số lượng đoán đúng trên tập test khi kích thước tập huấn luyện tăng lên. 28 Chương 7: Nhập môn máy học
  29. Đọc thêm  Giáo trình: chương 18 (phần 1-3).  MIT Open courseware: ch5, ch6, ch7.  T. Mitchell, Machine Learning, McGraw-Hill.  J.R. Quinlan, C4.5: Programs for Machine Learning, Morgan Kaufmann. 29 Chương 7: Nhập môn máy học
  30. Câu hỏi ôn tập 1. Định nghĩa việc học? 2. Cho biết các loại học khác nhau? 3. Cho biết các dạng học trong học máy? 4. Cấu trúc cây quyết định? 5. Cài đặt thuật toán DTL. 6. Dùng C4.5, hoặc thuật toán DTL để giải các bài toán về Data Mining. 30 Chương 7: Nhập môn máy học
  31. PERCEPTRON ĐƠN LỚP 31 Chương 7: Nhập môn máy học
  32. Cấu trúc Perceptron w1, 1 w1, 2  w1, R w w  w W = 2, 1 2, 2 2, R wS, 1 wS, 2  wS, R T wi, 1 1w T wi, 2 w iw = W = 2 wi, R T Sw T ai = har dlim ni = hardlim iw p + bi 32 Chương 7: Nhập môn máy học
  33. Perceptron đơn lớp một đầu ra w 1, 1 = 1 w 1, 2 = 1 b = –1 T a = hardlim 1w p+ b = hardlim w1, 1 p1 + w1, 2 p2 + b 33 Chương 7: Nhập môn máy học
  34. Biên quyết định T T 1w p + b = 0 1w p = –b • Tất cả các điểm trên biên quyết định có cùng tích vô hướng với vector trọng số. • Tất cả khi chiếu lên vector trọng số đều quy về một điểm. Nói khác đi chúng nằm trên đường thẳng vuông góc với vector trọng số. 34 Chương 7: Nhập môn máy học
  35. Ví dụ hàm - OR 0  0  1  1  p1 = , t1 = 0  p2 = , t2 = 1  p3 = , t3 = 1 p4 = , t4 = 1 0  1  0  1  35 Chương 7: Nhập môn máy học
  36. Lời giải cho bài toán phân lớp OR Siêu phẳng biên phải vuông góc với vector trọng số. 0.5 1w = 0.5 Lấy một điểm bất kỳ trên siêu phẳng biên để tính giá trị của bias. T 0 1w p + b = 0.5 0.5 + b = 0.25+ b = 0 b = –0.25 0.5 36 Chương 7: Nhập môn máy học
  37. Perceptron đơn lớp nhiều đầu ra Mỗi một neuron có một siêu phẳng biên riêng. T iw p + bi = 0 Mỗi neuron có thể dùng để phân tách hai lớp. Do đó nếu n-neuron đầu ra thì có thẻ dùng để phân tách 2n lớp. 37 Chương 7: Nhập môn máy học
  38. Luật học qua ví dụ {p1, t1} , {p2, t2} , , {pQ, tQ } 1  –1  0  p1 = , t1 = 1  p2 = , t2 = 0 p3 = , t3 = 0  2  2  –1  38 Chương 7: Nhập môn máy học
  39. Khởi tạo ban đầu Khởi tạo ngẫu nhiên: 1.0 1w = –0.8 nạp p1 vào mạng neural: T 1 a = hardlim 1w p1 = hardlim 1.0 –0.8 2 a = hardlim –0.6 = 0 39 Chương 7: Nhập môn máy học Phân sai lớp.
  40. LUẬT HỌC • đặt 1w to p1 – Không ổn định • cộng p1 vào 1w new old Ta có luật: If t = 1 and a = 0, then 1w = 1w + p new ol d 1.0 1 2.0 1w = 1w + p1 = + = –0.8 2 1.2 40 Chương 7: Nhập môn máy học
  41. Vector mẫu thứ hai T –1 a = hardlim 1w p2 = hardlim 2.0 1.2 2 a = hardlim 0.4 = 1 (Phân lớp sai) new old Ta có luật học: If t = 0 and a = 1, then1 w = 1w – p new old 2.0 –1 3.0 1w = 1w – p2 = – = 1.2 2 –0.8 41 Chương 7: Nhập môn máy học
  42. Vector mẫu thứ ba T 0 a = hardlim 1w p3 = hardlim 3.0 –0.8 –1 a = hardlim 0.8 = 1 (Phân lớp sai) wne w = wol d – p = 3.0 – 0 = 3.0 1 1 3 –0.8 –1 0.2 Siêu phẳng đã phân lớp chính xác. new o ld If t = a, then 1w = 1w . 42 Chương 7: Nhập môn máy học
  43. Luật học thống nhất new old If t = 1 and a = 0, th en 1w = 1w + p n ew old If t = 0 and a = 1, th en 1w = 1w – p new ol d If t = a, th en 1w = 1w e = t – a new old If e = 1, th en1 w = 1w + p new old If e = –1, th en1 w = 1w – p If e = 0, th en wnew = wold 1 1 chú ý: bias tương đương new old old 1w = 1w + ep = 1w + t– a p với đầu vào có kết nối new ol d b = b + e trọng số =1. 43 Chương 7: Nhập môn máy học
  44. Perceptron đơn lớp nhiều đầu ra Update dòng thứ i của ma trận trọng số: new old iw = iw + e ip ne w ol d bi = bi + ei Dạng ma trận: Wnew = Wold + epT new ol d b = b + e 44 Chương 7: Nhập môn máy học
  45. Ví dụ tự động phân loại Táo/Chuối Tập huấn luyện (ba thuộc tính: Shape, Texture, Weight)   –1 1 p1 = 1 , t1 = 1  p2 = 1 , t2 = 0  –1  –1  Trọng số khởi tạo W = 0.5 –1 –0.5 b = 0.5 Lần lặp đầu tiên –1 a = hardlim Wp1 + b = hardlim 0.5 –1 –0.5 1 + 0.5 –1 a = hardlim –0.5 = 0 e = t1 – a = 1 – 0 = 1 new old T W = W + ep = 0.5 –1 –0.5 + 1 –1 1 –1 = –0.5 0 –1.5 new ol d 45 Chương 7: Nhập môn máyb học= b + e = 0.5 + 1 = 1.5
  46. Lần lặp thứ hai 1 a = hardlim (Wp2 + b) = hardlim ( –0.5 0 –1.5 1 + 1.5 ) –1 a = hardlim (2.5) = 1 e = t2 – a = 0 – 1 = –1 new old T W = W + ep = –0.5 0 –1.5 + –1 1 1 –1 = –1.5 –1 –0.5 bnew = bold + e = 1.5+ –1 = 0.5 46 Chương 7: Nhập môn máy học
  47. Kiểm tra –1 a = hardl im (Wp1 + b) = hardlim ( –1.5 –1 –0.5 1 + 0.5) –1 a = hardlim (1.5) = 1 = t1 1 a = hardl im (Wp2 + b) = hardlim ( –1.5 –1 –0.5 1 + 0.5) –1 a = hardlim (–1.5) = 0 = t2 47 Chương 7: Nhập môn máy học
  48. Định Lý hội tụ cho Perceptron 1. Khả tách tuyến tính: Hai tập điểm A và B trong không gian vector X n-chiều được coi là khả tách tuyến tính nếu tồn tại n+1 số thực w1, , wn sao cho với mọi x=(x1,x2, ,xn) A thoả mãn wx wn+1 và với mọi y=(y1, y2, ,yn) B thoả mãn wy wn+1 và với mọi y=(y1, y2, ,yn) B thoả mãn wy<0. Bổ đề: Khả tách tuyến tính khả tách tuyến tính tuyệt đối. 48 Chương 7: Nhập môn máy học
  49. Định Lý hội tụ cho Perceptron Định lý (cho perceptron đơn lớp một đầu ra): Nếu hai tập P và N là hữu hạn và khả tách tuyến tính thì luật toán học Perceptron sẽ hội tụ (có nghĩa là tw sẽ chỉ được update một số hữu hạn lần). Chứng minh: i) Đặt P'=PN' trong đó N' gồm những phần tử không thuộc N. ii) Các vector thuộc P' có thể chuẩn hoá (chuẩn bằng 1) vì nếu tồn tại w sao cho wx > 0 (với mọi x P') thì x > 0 với mọi  iii) Vector có thể chuẩn hoá. Do giả thiết là siêu phẳng biên tồn tại, nên phải có vector lời giải được chuẩn hoá w*. 49 Chương 7: Nhập môn máy học
  50. Định Lý hội tụ cho Perceptron Chứng minh (tiếp): Giả sử thuật toán đã chạy được t+1 bước, w(t+1) đã được update. Có nghĩa là tại bước t tồn tại vector pi bị phân lớp sai (có thể lập luận tương tự trong trường hợp vector bị phân lớp sai là ni). w(t+1)=w(t)+pi (1) Cosine của góc giữa w và w* là: cos =(w*. w(t+1))/(||w*||.||w(t+1)||) =(w*. w(t+1))/(||w(t+1)||) (2) Thế (1) vào tử số của (2) ta có: w*.w(t+1)=w*(w(t)+pi)=w*. w(t)+w*.pi w*. wt + trong đó = min{w*.p /  p P'}. Do đó bằng quy nạp ta có: w*. w(t+1) w*. w(0) + (t+1)  (3) Mặt khác xét mẫu số của (2): 2 2 2 ||w(t+1)|| =(w(t)+pi)(w(t)+pi)=||w(t)|| +2w(t).pi+||pi|| Do w(t).pi là số âm hoặc bằng 0 (do đó mới phải update w(t)) 2 2 2 2 w(t+1) ||w(t)|| +||pi|| ||w(t)|| +1 ||w(0)|| +(t+1) (4) Kết hợp (3) và (4) ta có: cos (w*. w(0)+(t+1))/sqrt( ||w(0)||2+(t+1)) Vế phải tăng tỷ lệ với sqrt(t) (do  > 0) do đó t bắt buộc phải hữu hạn (vì cos 1). Kết thúc chứng minh. 50 Chương 7: Nhập môn máy học
  51. Cải tiến thuật toán học Perceptron • Mặc dù định lý hội tụ đảm bảo tính dừng của thuật toán học Perceptron, tuy nhiên trong thực tế số lần lặp có thể rất lớn (thậm chí là hàm số mũ với đầu vào). 1. Corrective Learning (perceptron một đầu ra):  = e.w(t).pi (e=yi-ti) w(t+1)= w (t)+ ((+).pi)/||pi|| Mỗi sample bị phân lớp sai có thể hiệu chỉnh lại trong một bước để phân lớp đúng. Ví dụ nếu pi P bị phân lớp sai (w(t).pi 0. 51 Chương 7: Nhập môn máy học
  52. Cải tiến thuật toán học Perceptron 2. Thuật giải học Pocket (Gallant, 1990): Trong thực tế tập dữ liệu không phải lúc nào cũng khả tách tuyến tính một cách hoàn hảo. Do đó cần lưu giữ vector trọng số (hay ma trận trọng số) đạt mức phân lớp tốt nhất. Giải thuật:(perceptron một đầu ra) Bước khởi tạo: Khởi trị vector w ngẫu nhiên. Đặt ws=w (ws là vector lưu trữ), hs=0 (hs là số vector phân lớp thành công liên tiếp). Bước lặp: Udate w sử dụng luật học Perceptron. Dùng biến h ghi lại số lần phân lớp thành công liên tiếp. Nếu h>hs thì thay ws bằng w và hs thay bằng h. Tiếp tục lặp. (Gallant, 1990) chứng minh rằng nếu tập training là hữu hạn và các vector đầu vào cũng như trọng số là hữu tỷ thì thuật toán sẽ hội tụ tới lời giải tối ưu với xác suất bằng 1. 52 Chương 7: Nhập môn máy học
  53. Hạn chế của Perceptron đơn lớp Biên quyết định là tuyến tính T 1w p + b = 0 Không dùng đuợc đối với các bài toán không khả tách tuyến tính 53 HàmChương XOR 7: Nhập môn máy học
  54. Đọc thêm 1. M.T. Hagan, H.B. Demuth, and M. Beale, Neural Network Design, PWS Publishing. 2. N.J. Nilson, Mathematical Foundations of Learning Machines, Morgan Kaufmann. 54 Chương 7: Nhập môn máy học
  55. Câu Hỏi Ôn Tập 1. Nêu cấu trúc và luật học của mạng Perceptron? 2. Chứng minh định lý hội tụ của mạng Perceptron? 3. Lấy các ví dụ và mô phỏng Perceptron trong MatLab? 55 Chương 7: Nhập môn máy học
  56. PERCEPTRON ĐA LỚP  Nội dung: • Cấu trúc mạng Perceptron đa lớp. • Thuật giải lan truyền ngược (BP). • Định Lý Kolmogorov và độ phức tạp học. • Một số Heuristics cho việc cải tiến BP.  56 Chương 7: Nhập môn máy học
  57. Perceptron Đa Lớp 1 2 3 57 Chương 7: Nhập môn máyR học – S – S – S Network
  58. Ví dụ 58 Chương 7: Nhập môn máy học
  59. Các biên quyết đinh Biên thứ nhất: 1 a1 = hardlim –1 0 p + 0.5 Biên thứ hai: 1 a2 = hardlim 0 –1 p + 0.75 Mạng con thứ nhất 59 Chương 7: Nhập môn máy học
  60. Các Biên Quyết Định Biên thứ ba: 1 a3 = hardlim 1 0 p – 1.5 Biên thứ tư: 1 a4 = hardlim 0 1 p –0.25 Mạng con thứ hai 60 Chương 7: Nhập môn máy học
  61. Mạng tổng hợp –1 0 0.5 1 1 0.75 W = 0 –1 b = 1 0 –1.5 0 1 –0.25 2 W = 1 1 0 0 b2 = –1.5 0 0 1 1 –1.5 3 3 W = 1 1 b = –0.5 61 Chương 7: Nhập môn máy học
  62. Xấp Xỉ Hàm 1 1 f n = 1 + e –n f 2 n = n Giá trị các tham số 1 1 1 1 w1, 1 = 10 w2, 1 = 10 b1 = –10 b2 = 10 2 2 2 w1, 1 = 1 w1, 2 = 1 b = 0 62 Chương 7: Nhập môn máy học
  63. Đồ thị "hàm" của mạng 3 2 1 0 -1 -2 -1 0 1 2 63 Chương 7: Nhập môn máy học
  64. Thay đổi giá trị các tham số 3 3 1 2 2 2 –1 w 1 0 b2 20 1, 1 1 1 0 0 -1 -1 -2 -1 0 1 2 -2 -1 0 1 2 3 3 2 2 –1 b 1 2 –1 w1, 2 1 2 1 1 0 0 -1 -1 -2 -1 0 1 2 -2 -1 0 1 2 64 Chương 7: Nhập môn máy học
  65. Mạng Đa Lớp m + 1 m+ 1 m + 1 m m+ 1 a = f W a + b m = 0, 2,  , M – 1 0 a = p a = aM 65 Chương 7: Nhập môn máy học
  66. Hàm Lỗi Tập huấn luyện {p1,t1} , {p2, t2} ,  , {pQ,tQ} MSE F x = Ee2  = E t – a 2  Dạng Vector T T F x = Ee e  = E t – a t – a  Xấp xỉ MSE Fˆ x = t k –a k T t k – a k = eT k e k Approximate Steepest Descent m m Fˆ m m Fˆ w k + 1 = w k – b k + 1 = b k – i, j i, j i i m w m b 66 Chương 7: Nhập môn máy học i, j i
  67. Đạo Hàm Hàm Hợp df n w df n dn w = dw dn dw Ví dụ f n = cos n n = e 2w f n w = cos e2w df n w df n dn w 2w 2w 2w = = –sin n 2e = –sin e 2e dw dn dw Tính Gradient m m Fˆ Fˆ ni Fˆ Fˆ n = = i m nm wm m m m w i, j i i, j bi ni bi 67 Chương 7: Nhập môn máy học
  68. TÍNH GRADIENT Sm –1 m m m– 1 m ni =  wi, j aj + bi j = 1 nm nm i = am – 1 i = 1 m j m wi, j bi Độ nhạy Fˆ sm  i m ni Gradient Fˆ m m – 1 Fˆ m = s a = s m i j m i w i, j bi 68 Chương 7: Nhập môn máy học
  69. Steepest Descent m m m m – 1 m m m wi, j k +1 = wi, j k – si aj bi k + 1 = bi k – si m m m m – 1 T m m m W k + 1 = W k – s a b k + 1 = b k – s Fˆ m n1 Fˆ m Fˆ m s  m = n2 n  Fˆ m n m S 69 ChươngBước 7: Nhập tiếpmôn máy theo: học Tính độ nhạy (Backpropagation)
  70. Ma trận Jacobian Sm m + 1 m + 1 m + 1 m + 1 m m +1 n1 n1 n1  m + 1   wi, l al + bi m m m m n a i l = 1 m + 1 j n1 n2 n m = = w S m m i, j m m + 1 m + 1 m + 1 n j n j n j m + 1 n2 n2 n2 n   m m m m n1 n2 n m m + 1 m m  S ni m + 1 f n j m + 1 m m n = = ' m wi, j m wi, j f n j    n j nj m + 1 m + 1 m + 1 n n n Sm + 1 Sm + 1 Sm + 1 m m  m  f n m m m fÝ nm = j n n n m j m 1 2 S nj Ým m f n1 0  0 m + 1 m m n m + 1 m m ' m m 0 fÝ n  0 = W F' n F n = 2 nm     m m 70 0 0  fÝ n m Chương 7: Nhập môn máy học S
  71. Backpropagation (Sensitivities) m + 1 T m Fˆ n Fˆ m m m +1 T Fˆ = = = Ý s m m +1 F n W m + 1 nm n n n m m m m +1 T m +1 s = FÝ(n ) W s Độ nhạy được tính từ tầng cuối cùng và lan truyền ngược lại cho đến tầng đầu. M M – 1 2 1 s s  s s 71 Chương 7: Nhập môn máy học
  72. Khởi đầu (Last Layer) SM 2  t – a T  j j M Fˆ  t – a t – a a s = = = j = 1 = –2 t – a i- i M M M i i M ni ni ni ni M M M a a  f n M M i- = i = i = fÝ n M M M i ni ni ni M ÝM M si = –2 ti – ai f n i M M M s = –2FÝ (n ) t – a 72 Chương 7: Nhập môn máy học
  73. Tổng kết thuật toán Lan truyền Xuôi 0 a = p m + 1 m+ 1 m + 1 m m+ 1 a = f W a + b m = 0, 2,  , M – 1 a = aM Lan truyền ngược M M M s = –2FÝ (n ) t – a m m m m+ 1 T m+ 1 s = FÝ (n ) W s m = M – 1,  , 2, 1 Cập nhật trọng số m m m m – 1 T m m m W k + 1 = W k – s a b k + 1 = b k – s 73 Chương 7: Nhập môn máy học
  74. Ví dụ: Regression t g p = 1 + sin p 4 p - e + 1-2-1 a Network 74 Chương 7: Nhập môn máy học
  75. Network p 1-2-1 a Network 75 Chương 7: Nhập môn máy học
  76. Khởi tạo ban đầu 1 –0.27 1 –0.48 2 2 W 0 = b 0 = W 0 = 0.09 –0.17 b 0 = 0.48 –0.41 –0.13 3 Network Response Sine Wave 2 1 0 76 Chương-1 7: Nhập môn máy học -2 -1 0 1 2
  77. Lan Truyền Xuôi a0 = p = 1 1 1 1 0 1 –0.27 –0.48 –0.75 a = f W a + b = logsig 1 + = logsig –0.41 –0.13 –0.54 1 0.75 a1 = 1 + e = 0.32 1 1 0.36 8 1 + e0.54 2 2 2 1 2 0.32 1 a = f W a + b = purelin ( 0.09 –0.17 + 0.48 ) = 0.44 6 0.36 8  2  e = t – a = 1 + sin p – a = 1 + sin 1 – 0.44 6 = 1.26 1 4  4  77 Chương 7: Nhập môn máy học  
  78. Đạo hàm hàm chuyển –n 1 d 1 e 1 1 1 1 fÝ n = = = 1 – = 1 – a a dn –n 2 –n –n 1 + e 1 + e–n 1 + e 1 + e 2 d fÝ n = n = 1 dn 78 Chương 7: Nhập môn máy học
  79. Lan Truyền Ngược 2 2 2 2 s = –2FÝ(n ) t – a = –2 fÝ n2 1.261 = –2 1 1.261 = –2.522 1 1 1 1 1 2 T 2 1 – a1 a1 0 0.09 s = FÝ(n ) W s = –2.52 2 1 1 –0.17 0 1 – a2 a2 1 1 – 0.32 1 0.32 1 0 0.09 s = –2.52 2 0 1 – 0.36 8 0.36 8 –0.17 s 1 = 0.21 8 0 –0.22 7 = –0.04 95 0 0.23 3 0.42 9 0.09 97 79 Chương 7: Nhập môn máy học
  80. Cập nhật trọng số = 0.1 2 2 2 1 T W 1 = W 0 – s a = 0.09–0.17 – 0.1 –2.522 0.3210.368 2 W 1 = 0.17 1–0.07 72 2 2 2 b 1 = b 0 – s = 0.48 – 0.1 –2.522 = 0.732 1 1 1 0 T –0.27 –0.04 95 –0.26 5 W 1 = W 0 – s a = – 0.1 1 = –0.41 0.09 97 –0.42 0 b1 1 = b1 0 – s1 = –0.48 – 0.1 –0.04 95 = –0.47 5 80 Chương 7: Nhập môn máy học –0.13 0.09 97 –0.14 0
  81. Lựa chọn Cấu trúc mạng i g p = 1 + sin p 4 1-3-1 Network 3 3 2 i = 1 2 i = 2 1 1 0 0 -1 -1 -2 -1 0 1 2 -2 -1 0 1 2 3 3 i = 4 i = 8 2 2 1 1 0 0 -1 -1 -2 -1 0 1 2 -2 -1 0 1 2 81 Chương 7: Nhập môn máy học
  82. Lựa chọn cấu trúc mạng 6 g p = 1 + sin p 4 3 3 2 1-2-1 2 1-3-1 1 1 0 0 -1 -1 -2 -1 0 1 2 -2 -1 0 1 2 3 3 1-4-1 1-5-1 2 2 1 1 0 0 -1 -1 -2 -1 0 1 2 -2 -1 0 1 2 82 Chương 7: Nhập môn máy học
  83. Hội tụ g p = 1+ sin p 3 3 2 5 2 1 5 1 3 1 3 2 4 4 2 0 0 0 0 1 -1 -1 -2 -1 0 1 2 -2 -1 0 1 2 Hội tụ đến cực trị toàn cục Hội tụ đến cực trị địa phương 83 Chương 7: Nhập môn máy học
  84. Khái quát hoá {p1,t1}, {p2, t2} ,  , {pQ, tQ} g p = 1 + sin p p = –2, –1.6, –1.2,  , 1.6, 2 4 3 3 1-2-1 1-9-1 2 2 1 1 0 0 -1 -1 -2 -1 0 1 2 -2 -1 0 1 2 84 Chương 7: Nhập môn máy học
  85. Định Lý Kolmogov và Độ Phức Tạp Học  Bài toán số 13 của David Hilbert "Nghiệm của đa thứ bậc 7 không thể biểu diễn bằng chồng hàm của các hàm 2 biến cụ thể là đa thức sau đây: f7+xf3+yf2+zf+1=0 không thể giải được bằng các hàm hai biến".  Ví dụ về chồng hàm hai biến để giải phương trình bậc 2. 85 Chương 7: Nhập môn máy học
  86. Định Lý Kolmogov và Độ Phức Tạp Học  Năm 1957, Kolmogorov (Arnold, Lorenz) chứng minh giả thiết đưa ra trong bài toán của Hilbert là sai. Thậm chí chứng minh kết quả mạnh hơn: mọi hàm liên tục đều biểu diễn được bằng chồng các hàm một biến chỉ dùng phép toán nhân và cộng.  Định Lý Kolmogorov: f:[0,1]n [0,1] là hàm liên tục thì tồn tại các hàm một biến g, hi i=1,2, ,2n+1 và các hằng số i sao cho:  f(x1,x2, ,xn)= j=1,2n+1g(i=1,n ihj(xi))  Định lý cho mạng Neural (Baron, 1993):  Mạng Perceptron hướng tiến một lớp ẩn dùng hàm chuyển sigmoid có thể xấp xỉ bất cứ hàm khả tích Lơbe nào trên khoảng [0,1]. 86 Chương 7: Nhập môn máy học
  87. Định Lý Kolmogov và Độ Phức Tạp Học  Mặc dù vậy các định lý chỉ đưa ra sự tồn tại mà không đưa ra được thuật toán cho việc xác định cấu trúc mạng (số neuron trong tầng ẩn) hay các trọng số.  Định lý NP về học cho mạng Neural (Judd, 1990):  Bài toán tìm các trọng số tối ưu cho mạng Neural đa lớp có hàm chuyển hardlims là NP đầy đủ.  Lưu ý:  - do đó thuật toán BP không đảm bảo tìm được nghiệm tối ưu, thậm chí không đảm bảo sự hội tụ.  -Việc xác định cấu trúc mạng và một số yếu tố của thuật toán học còn mang tính kinh nghiệm, Heuristic. 87 Chương 7: Nhập môn máy học
  88. Một số Heuristics cho BP • Cập nhật theo chế độ tuần tự (online) hay batch (epoch):  Thường việc học theo chế độ tuần tự giúp BP hội tụ nhanh hơn, đặc biệt khi dữ liệu lớn và dư thừa. • Chuẩn hoá giá trị đầu ra:  Đảm bảo giá trị đầu ra nằm trong miền giá trị của hàm chuyển trên các neuron đầu ra tương ứng (thường là nằm trong khoảng [a+, b- ]. • Chuẩn hoá giá trị đầu vào:  Đảm bảo giá trị trung bình gần 0 hoặc nhỏ so với độ lệch tiêu chuẩn (stdev). Các giá trị tốt nhất phải độc lập với nhau. • Khởi tạo giá trị trọng số:  Uniform random in [- , ]; [- , -][ , ] • Kết thúc sớm:  Khi liên tiếp n epoch training mà không có sự cải thiên đáng kể lỗi hay không có sự thay đổi đáng kể của các trọng số. 88 Chương 7: Nhập môn máy học
  89. Một số Heuristics cho BP • Tốc độ học:  Tốc độ học của các Neuron nên đều nhau vì vậy, neuron tầng sau (thường có gradient lớn hơn tầng trước) nên có tốc độ học nhỏ hơn tầng trước, Neuron có ít input nên có tốc độ học lớn hớn Neuron có nhiều input. • Kiểm tra chéo (crossvalidation):  Tách tập dữ liệu ra làm hai tập độc lập (training and testing). Tỷ lệ thường là 2/3:1/3. Thực hiện việc học trên tập training và kiểm tra khả năng khái quát hoá của mạng trên tập testing. • Luật phân lớp tối ưu:  Dùng M neuron đầu ra cho bài toán phân M lớp sử dụng luật cạnh tranh winner-take-all. • Xác định số neuron lớp ẩn:  Các ước lượng cận thô (số lượng dữ liệu, chiều VC). Phương pháp: Incremental, Decremental. 89 Chương 7: Nhập môn máy học
  90. Đọc thêm 1. M.T. Hagan, H.B. Demuth, and M. Beale, Neural Network Design, PWS Publishing. 2. Giáo trình, chương 19. 3. MIT Courseware: ch8, ch9. 90 Chương 7: Nhập môn máy học
  91. Câu Hỏi ôn tập 1. Trình bày cấu trúc mạng Neuron Perceptron đa lớp? 2. Trình bày giải thuật học lan truyền ngược cho MLP. 3. Trình bày định lý Kolmogorov và ứng dụng cho MLP. 4. Cài đặt thuật giải BP cho MLP. 5. Ứng dụng MLP để giải các bài toán như: Classification và Regression. 91 Chương 7: Nhập môn máy học