Bài giảng Học máy - L8: Các phương pháp học có giám sát Học mạng nơron nhân tạo (Artificial neural network)

Nội dung text: Bài giảng Học máy - L8: Các phương pháp học có giám sát Học mạng nơron nhân tạo (Artificial neural network)

1. Nội dung môn học: „ Giới thiệu chung „ Đánh giá hiệunăng hệ thống họcmáy „ Các phương pháp họccd dựatrênxácsua trên xác suất „ Các phương pháp họccógiámsát „ Học mạng nơron nhân tạo (Artificial neural network) „ Các phương pháp học không giám sát „ Lọccộng tác „ Họctăng cường Học Máy – IT 4862 2
2. Mạng nơ-ron nhân tạo – Giới thiệu (2) „ ANN có thể được xem như một cấu trúc xử lý thông tin một cách ppgghân tán và song song ở mức cao „ ANN có khả năng học (learn), nhớ lại (recall), và khái quát hóa (generalize) từ các dữ liệu học –bằng cách gán và điều chỉnh (thích nghi) các giá trị trọng số (mức độ quan trọng) của các liên kết giữa các nơ-ron „ Chức năng (hàm mục tiêu ) của mộtANNt ANN được xác địnhbh bởi ‰ Kiến trúc (topology) của mạng nơ-ron ‰ Đặc tính vào/ra củaam mỗiin nơ-ron ‰ Chiến lược học (huấn luyện) ‰ Dữ liệu học ọ H c Máy – IT 4862 4
3. ANN – Các ứng dụng điển hình (2) „ Các hệ thống quân sự ‰ Ví dụ: Phát hiện thủy lôi, phân loại nhiễu ra-đa „ Các hệ thống tài chính ‰ Ví dụ: Phân tích thị trường chứng khoán, đánh giá giá trị bất động sản, kiểm tra truy cập thẻ tín dụng, kinh doanh cổ phiếu „ Lậpkế hoạch, điềukhiển, và tìm kiếm ‰ Ví dụ: Cài đặt song song các bài toán thỏa mãn ràng buộc, tìm lờigiải cho bài tátoánngười đưa hàng, điều khiểnvà khoa họcnghiêncứuvề người máy (robotics) „ Các hệ thống năng lượng ‰ Ví dụ: Đánh giá trạng thái hệ thống, phát hiệnvàkhắcphụcsự cố, dự đoán tải(khốilượng) công việc, và đánh giá mức độ an toàn „ (và nhiều lĩnh vực bài toánkhác!) ọ H c Máy – IT 4862 6
4. Đầu vào tổng thể và dịch chuyển „ Đầu vào tổng thể (net input) thường được tính toán bởi một hàm tuyến tính m m Net = w0 + w1x1 + w2 x2 + + wm xm = w0.1+ ∑ wi xi = ∑ wi xi i=1 i=0 „ Ý nghĩa của tín hiệu dịch chuyển (bias) w0 →Họ các hàm phân tách NtNet=w1x1 không th ể phân tách đợđược các ví dụ thành 2 lớp (two classes) →Nhưng: họ các hàm Net=w1x1+w0 có thể! Net Net Net = w1x1 Net = w1x1 + w0 x1 x1 ọ H c Máy – IT 4862 8
5. Hàm tác động: Logic ngưỡng (Threshold logic) ⎧ ⎪ 0, if Net −θ ⎩⎪ α (α >0) = max(0,min(1,α(Net +θ ))) OtOut „ Còn được gọi là hàm tuyến tính bão hòa (sa tura ting li near func tion ) 1 „ Kết hợp của 2 hàm tác động: tuyến tính và giới hạn chặt -θ 0 (1/α)-θ Net „ α xác định độ dốc của khoảng tuyến tính 1/α „ Nhược điểm: Liên tục – nhưng đạo hàm không liê n tục ọ H c Máy – IT 4862 10
6. Hàm tác động: Hyperbolic tangent 1− e−α (Net+θ ) 2 Out(Net) = tanh(Net,α,θ ) = = −1 1+ e−α (Net+θ ) 1+ e−α (Net+θ ) „ Cũng hay đượcsử dụng Out „ Tham số α xác định độ dốc „ Giá trịđầu ra trong khoảng (-1,1) 1 „ Ưu điểm ‰ Liên tục, và đạo hàm liên tục -θ 0 Net ‰ Đạo hàm của một hàm tanh có thể -1 đượcbiểudiễnbằng một hàm của chính nó ọ H c Máy – IT 4862 12
7. ANN – Kiến trúc mạngg( (2) „ Một tầng (layer) chứamột nhóm các nơ-ron „ Tầng ẩn (hidden layer) là mộttầng nằm ở giữatầng đầu vào (input layer) và tầng đầu ra (output layer) „ Cácnút ở tầng ẩn (hidden no des ) không tương tác trực tiếpvớimôitrường bên ngoài (củamạng nơ-ron) „ MộtANNt ANN được gọi là liên kết đầy đủ (fully connected) nếumọi đầuratừ mộttầng liên kếtvớimọinơ-ron của tầng kế tiếp ọ H c Máy – IT 4862 14
8. Kiến trúc mạng – Ví dụ Mạng lan Một nơ-ron với truyền tiến phản hồi đến một tầng chính nó Mạng hồi quy một tầng Mạng lan truyền tiến nhiềutu tầng Mạng hồi quy nhiều tầng ọ H c Máy – IT 4862 16
9. QQyuy tắc học trọng số tổnggq quát „ Tạibướchọc (t), mức độ điều chỉnh vec-tơ trọng số w tỷ lệ x0= 1 w thuậnvới tích của tín hiệuhọc r(t) 0 x1 w a neuron và đầuvàox(t) 1 Out x w (t) (t) (t) j Δw Δw ~ r .x xj (t) (t) (t) Δw = η.r .x w x Learning x m d m signal trong đó η (>0) là tốc độ học η generator (learning rate) „ Tín hiệuhọc r là một hàm của w, Lưu ý: x có thể là: x, và giá trịđầu ra mong muốn d j • một tín hiệu đầu vào, hoặc r = g(w,x,d) •một giá trị đầu ra của một nơ- „ Quy tắchọc trọng số tổng quát ron khác Δw(t) = η.g(w(t),x(t),d(t)).x(t) ọ H c Máy – IT 4862 18
10. Perceptron – Minh họa Mặtpht phẳng phân tách w +w x +w x =0 x1 0 1 1 2 2 Đầu ra = 1 Đầurau ra =- 1 x2 ọ H c Máy – IT 4862 20
11. Perceptron_ incremental(D, η) Initialize w (wi ← an initial (small) random value) do for each training instance (x,d)∈D Compute the real output value Out if (Out≠d) w ← w + η(d-Out)x end for until all the training instances in D are correctly classified return w Học Máy – IT 4862 22
12. Perceptron – Giới hạn „ Giải thuật học cho perceptron được chứng minh là hội tụ (converge) nếu: Một ppperceptron khôn g ‰ Các ví dụ học là có thể phân tách tuyến thể phân lớp chính xác tính (linearly separable) đối với tập học này! ‰ Sử dụng một tốc độ học η đủ nhỏ „ Giải thuật học perceptron có thể không hội tụ nếu như các ví dụ học không thể phân tách tuyến tính (not linearly separable) „ Khi đó, áp dụng quy tắc delta (delta rule) ‰ Đảm bảo hội tụ về một xấp xỉ phù hợp nhấtct của hàm mụcctiêu tiêu ‰ Quy tắc delta sử dụng chiến lược gradient descent để tìm trong không gian giả thiết (các vectơ trọng số) một vectơ trọng số phù hợp nhất với các ví dụ học ọ H c Máy – IT 4862 24
13. Gradient descent „ Gradient của E (ký hiệulà∇E) là mộtvectơ ‰ Có hướng chỉđilên(dốc) ‰ Có độ dài tỷ lệ thuậnvới độ dốc „ Gradient ∇E xác định hướng gây ra việc tăng nhanh nhất (steepest increase) đối với giá trị lỗi E ⎛ ∂E ∂E ∂E ⎞ ∇E(w) = ⎜ , , , ⎟ ⎝ ∂w1 ∂w2 ∂wN ⎠ trong đó N là tổng số các trọng số (các liên kết) trong mạng „ Vì vậy, hướng gây ra việc giảm nhanh nhất (steepest decrease) là giá trị phủđịnh của gradient của E ∂E Δw =-η.∇E(w); Δwi = −η , ∀i =1 N ∂wi „ Yêu cầu: Các hàm tác động đượcsử dụng trong mạng phảilàcác hàm liên tục đối với các trọng số, và có đạo hàm liên tục ọ H c Máy – IT 4862 26
14. Gradient_descent_incremental (D, η) Initialize w (wi ← an initial (small) random value) do for each training instance (x,d)∈D Compute the network output for each weight component wi wi ← wi – η(∂Ex/∂wi) end for end for until (stopping criterion satisfied) return w Stopping criterion: Số chu kỳ học (epochs) , Ngưỡng lỗi, Học Máy – IT 4862 28
15. Giải thuật học lan truyền ngược (()1) „ Giảithuậthọc lan truyềnngược tìm kiếmmộtvectơ các trọng số (weights vector) giúp cựctiểu hóa lỗitổng thể củahệ thống đối với tập học „ Giảithuật BP bao gồm 2 giai đoạn(bước) ‰ Giai đoạn lan truyền tiến tín hiệu (Signal forward) . Các tín hiệu đầu vào (vectơ các giá trịđầu vào) được lan truyềntiến từ tầng đầuvàođếntầng đầura(đi qua các tầng ẩn) ‰ Giai đoạn lan truyềnngượclỗi (Error backward) „ Căncứ vào giá trịđầu ra mong muốncủavectơđầu vào, hệ thống tính toán giá trị lỗi „ Bắt đầutừ tầng đầura, giá trị lỗi được lan truyềnngược qua mạng, từ tầng này qua tầng khác (phía trước), cho đếntầng đầuvào „ Việc lan truyềnngượclỗi (error back-propagation) đượcthựchiện thông qua việc tính toán (mộtcáchtruyhồi) giá trị gradient cụcbộ của mỗi nơ-ron ọ H c Máy – IT 4862 30
16. Giải thuật BP – Cấu trúc mạng „ Xét mạng nơ-ron 3 tầng (trong hình vẽ) để minh họa giải thuật x x x họcBPc BP Input xj 1 j m (j=1 m) „ m tín hiệu đầu vào xj (j=1 m) wqj „ l nơ-ron tầng ẩn zq (q=1 l) „ n nơ-ron đầuura ra y (i=1 n) Hidden i neuron z Out „ wqj là trọng số của liên kết từ q q (q=1 l) tín hiệu đầu vào xj tới nơ-ron wiq tầng ẩn zq „ wiq là trọng số của liên kết từ Output nơ-ron tầng ẩn zq tới nơ-ron neuron yi đầu ra yi (i=1 n) Outi „ Outq là giá trị đầu ra (cục bộ) của nơ-ron tầng ẩn zq „ Outi là giá trị đầu ra của mạng tương ứng vớiin nơ-ron đầurau ra yi ọ H c Máy – IT 4862 32
17. Giải thuật BP – Lan truyền tiến (()2) „ Giá trị đầu vào tổng thể (net input) của nơ-ron yi ở tầng đầurau ra l l ⎛ m ⎞ Net = w Out = w f ⎜ w x ⎟ i ∑ iq q ∑∑iq ⎜ qj j ⎟ q=1 q==11⎝ j ⎠ „ Nơ-ron yi sinh ra giá trị đầu ra (là một giá trị đầu ra của mạng) ⎛ l ⎞ ⎛ l ⎛ m ⎞⎞ Out = f (Net ) = f ⎜ w Out ⎟ = f ⎜ w f ⎜ w x ⎟⎟ i i ⎜∑ iq q ⎟ ⎜∑∑iq ⎜ qj j ⎟⎟ ⎝ q=1 ⎠ ⎝ q==11⎝ j ⎠⎠ „ Vectơ các giá trị đầu ra Outi (i=1 n) chính là giá trị đầu ra thực tế của mạng, đối với vectơ đầu vào x ọ H c Máy – IT 4862 34
18. Giải thuật BP – Lan truyền ngược (2) „ Theo phương pháp gradient-descent, các trọng số của các liên kết từ tầng ẩntớitầng đầurađượccập nhậtbởi ∂E Δwiq = −η ∂wiq „ Sử dụng quy tắcchuỗi đạo hàm đối với ∂E/∂wiq, tacó ⎡ ⎤ ⎡ ∂E ⎤⎡∂Outi ⎤ ∂Neti Δwiq = −η ⎢ ⎥⎢ ⎥⎢ ⎥ = η[]di − Outi []f '()Neti []Out q =ηδ iOut q ⎣∂Outi ⎦⎣ ∂Neti ⎦⎣⎢ ∂wiq ⎦⎥ (Lưu ý: dấu“–” đã đượckếthợpvớigiátrị ∂E/∂Outi) „ δi là tín hiệulỗi (error signal) củanơ-ron yi ở tầng đầura ∂E ⎡ ∂E ⎤⎡∂Outi ⎤ δ i = − = −⎢ ⎥⎢ ⎥ = []di − Outi []f '()Neti ∂Neti ⎣∂Outi ⎦⎣ ∂Neti ⎦ trong đó Neti là đầuvàotổng thể ((p)net input) củanơ-ron yi ở tầng đầura, vàf'(Neti)=∂f(Neti)/∂Neti ọ H c Máy – IT 4862 36
19. Giải thuật BP – Lan truyền ngược (4) „ Áp dụng quy tắc chuỗi đạo hàm, ta có n Δwqj =η ∑ [(di − Outi ) f '(Neti )wiq ] f '(Net q )x j i=1 n = η ∑ [δ i wiq ] f '(Net q )x j = ηδ q x j i=1 „ δq là tín hiệu lỗi (error signal) của nơ-ron zq ở tầng ẩn n ∂E ⎡ ∂E ⎤⎡∂Out q ⎤ δ q = − = −⎢ ⎥⎢ ⎥ = f '()Net q ∑δ i wiq ∂Net q ⎣⎢∂Out q ⎦⎥⎣⎢ ∂Net q ⎦⎥ i=1 trong đó Netq là đầu vào tổng thể (net input) của nơ-ron zq ở tầng ẩn, và f'(Netq)=∂f(Netq)/∂Netq ọ H c Máy – IT 4862 38
20. Giải thuật BP – Lan truyền ngược (6) „ Quá trình tính toán tín hiệu lỗi (error signals) như trên có thể được mở rộngg( (khái quát ) dễ dàng đối với mạng nơ- ron có nhiều hơn 1 tầng ẩn „ Dạng tổngqg quát của qqyuy tắc cập nhật trọng số tronggg giải thuật BP là: Δwab = ηδaxb ‰ b và a là 2 chỉ số tương ứng với 2 đầu của liên kết (b→a) (từ một nơ-ron (hoặc tín hiệu đầu vào) b đến nơ-ron a) ‰ xb là giá trị đầuurac ra củaan nơ-ron ở tầng ẩnn(ho (hoặc tín hiệu đầu vào) b, ‰ δa là tín hiệu lỗi của nơ-ron a ọ H c Máy – IT 4862 40
21. Bước3(Tính toán lỗi đầura) Q Tính toán lỗi đầuracủamạng và tín hiệulỗi δi củamỗinơ-ron ở tầng đầura n 1 (k ) Q 2 E = E + ∑ (di − Outi ) 2 i=1 Q (k) Q Q δi = (d i − Out i )f '( Net i ) Bước4(Lan truyềnngượclỗi) q-1 Lan truyềnngượclỗi để cậpnhậtcáctrọng số và tính toán các tín hiệulỗi δi cho các tầng phía trước q q q-1 q q q Δ wij = η.( δi).( Outj); wij = wij + Δ wij q−1 q−1 q q δi = f '( Net i )∑ w ji δ j ; for all q = Q,Q −1, ,2 j Bước5(Kiểmtrakết thúc mộtchukỳ học – epoch) Kiểm tra xem toàn bộ tậphọc đã đượcsử dụng (đã xong mộtchukỳ học – epoch) Nếu toàn bộ tậphọc đã được dùng, chuyển đếnBước6; ngượclại, chuyển đếnBước1 Bước6(Kiểmtralỗitổng thể) Nếulỗitổng thể E nhỏ hơnngưỡng lỗichấpnhận được (<Ethreshold), thì quá trình học kết thúc và trả về các trọng số học được; Ngượclại, gán lạiE=0, vàbắt đầumộtchukỳ học mới (quay về Bước1) Học Máy – IT 4862 42
22. Giảithuật BP – Lan truyềntiến(2) f(Net ) w x 1 1x1 1 x 1 w x f(Net4) 1x2 2 Out6 f(Net6) f(Net2) f(Net5) x2 f(Net ) 3 Out = f (w x + w x ) 1 1x1 1 1x2 2 ọ H c Máy – IT 4862 44
23. GiảithuậtBP –Lan truyềntiến(4) f(Net1) x 1 f(Net4) Out6 f(Net6) f(Net2) f(Net ) x w x 5 2 3x1 1 w x f(Net ) 3x2 2 3 Out = f (w x + w x ) 3 3x1 1 3x2 2 ọ H c Máy – IT 4862 46
24. GiảithuậtBP –Lan truyềntiến(6) f(Net1) x 1 w51Out1 f(Net4) Out6 f(Net6) f(Net2) w52OtOut2 f(Net5) x2 w53Out3 f(Net3) Out5 = f (w51Out1 + w52Out2 + w53Out3 ) ọ H c Máy – IT 4862 48
25. GiảithuậtBP –Tínhtoánlỗi f(Net1) x 1 f(Net4) δ6 Out6 f(Net6) f(Net2) f(Net ) x 5 2 d is the desired output value f(Net3) ∂E ⎡ ∂E ⎤⎡∂Out6 ⎤ δ 6 = − = −⎢ ⎥⎢ ⎥ = [d − Out6 ][ f '(Net6 )] ∂NtNet6 ⎣∂OtOut 6 ⎦⎣ ∂NtNet 6 ⎦ ọ H c Máy – IT 4862 50
26. Giải thuật BP – Lan truyền ngược(2) f(Net1) x 1 f(Net4) δ6 Out6 f(Net6) f(Net2) δ5 w65 f(Net5) x2 f(Net3) δ5 = f '(Net5 )(w65δ6 ) ọ H c Máy – IT 4862 52
27. Giải thuật BP – Lan truyền ngược(4) f(Net1) δ4 x1 f(Net ) w42 4 δ2 Out6 f(Net6) f(Net2) w 52 δ5 f(Net5) x2 f(Net3) δ2 = f '(Net2 )(w42δ4 + w52δ5 ) ọ H c Máy – IT 4862 54
28. GiảithuậtBP –Cậpnhậttrọng số (1) δ1 f(Net ) w 1 1x1 x f(Net ) 1 w 4 1x2 Out6 f(Net6) f(Net2) f(Net5) x2 w = w + ηδ x 1x1 1x1 1 1 f(Net3) w = w + ηδ x 1x2 1x2 1 2 ọ H c Máy – IT 4862 56
29. GiảithuậtBP –Cậpnhậttrọng số (3) f(Net1) x 1 f(Net4) Out6 f(Net6) f(Net2) w f(Net5) x2 3x1 δ3 w3x w = w +ηδ x 2 3 x1 3 x1 3 1 f(Net3) w = w +ηδ x 3 x2 3 x2 3 2 ọ H c Máy – IT 4862 58
30. GiảithuậtBP –Cậpnhậttrọng số (5) f(Net1) x 1 f(Net4) Out6 f(Net6) f(Net2) w51 δ5 w 52 f(Net5) x2 w = w +ηδ Out w53 51 51 5 1 f(Net ) 3 w52 = w52 +ηδ5Out2 w53 = w53 +ηδ5Out3 ọ H c Máy – IT 4862 60
31. BP: Khởi tạo giá trị của các trọng số „ Thông thường, các trọng sốđượckhởitạovới các giá trị nhỏ ngẫu nhiên „ Nếucáctrọng số có các giá trị ban đầulớn ‰ Các hàm xích-ma (sigmoid functions) sẽđạttrạng thái bão hòa sớm ‰ Hệ thống sẽ tắc ở một điểmcựctiểucụcbộ (local minimum) hoặc ở mộttrạng thái không đổi (very flat plateau) gần điểmbắt đầu 0 „ Các gợi ý cho w ab (liên kết từ nơ-ron b tới nơ-ron a) ‰ Ký hiệu na là số lượng các nơ-ron ở cùng tầng vớinơ-ron a 0 w ab ∈ [−1/na, 1/na] ‰ Ký hiệu ka là số lượng các nơ-ron có liên kết(tiến) đếnnơ-ron a (=số lượng các liên kết đầuvàocủanơ-ron a) 0 w ab ∈ [ − 3/ ka ,3/ ka ] ọ H c Máy – IT 4862 62
32. BP: Momentum „ Phương pháp Gradient descent có -η∇E(t’+1) thể rấtchậmnếu η nhỏ, và có thể αΔw(t’) -η∇E(t’+1) + αΔw(t’) Δw(t’) dao động mạnh nếu η quá lớn B A’ Δw(t) A „ Để giảmmức độ dao động, cần đưavàomột thành phần momentum (t) (t) (t-1) -η∇E(t+1) Δw = -η∇E + αΔw B’ αΔw(t) trong đó α (∈[0,1]) là một tham số -η∇∇E(t+1) + αΔΔw(t) momentum (thường lấy =0.9) Gradient descent đốivớimộthàm „ Một quy tắc, dựatrêncácthí lỗibậc2 đơngiản. nghiệm, để chọn các giá trị hợp lý cho tốc độ học và momentum là: Quỹđạo bên trái không sử dụng momentum. (η+α)>≈ 1; trong đó α>η để tránh dao động Quỹđạo bên phảicósử dụng momentum. ọ H c Máy – IT 4862 64
33. ANNs – Giới hạn học „ Các hàm nhị phân (Boolean functions) ‰ Bất kỳ hàm nhị phân nào cũng có thể học được bởi một ANN sử dụng 1 tầng ẩn „ Các hàm liên tục (Con tinuous functi ons) ‰ Bất kỳ một hàm liên tục bị giới hạn (bounded continuous function) nào cũng có thể học được (xấp xỉ) bởi một ANN sử dụng 1 tầng ẩn [Cybenko, 1989; Hornik et al., 1989] ‰ Bất kỳ một hàm mục tiêu nào cũng có thể học được (xấp xỉ) bởi mộtANNst ANN sử dụng 2 tầng ẩn [Cybenko, 1988] ọ H c Máy – IT 4862 66
34. ANNs – Khi nào? „ Mỗi ví dụ được biểu diễn bởi một tập gồm (rất) nhiều thuộc tính kiểuru rờiri rạchoc hoặccki kiểuus số „ Miền giá trị đầu ra của hàm mục tiêu có kiểu số thực, hoặc kiểuru rờiri rạc, hoặckic kiểuuvect vectơ „ Tập dữ liệu có thể chứa nhiễu/lỗi „ Dạng của hàm mục tiêu không xác định (biết) tr ước „ Không cần thiết (hoặc không quan trọng) phải đưa ra giải thích cho người dùng đối với các kết quả „ Chấp nhận thời gian (khá) lâu cho quá trình huấn luyện „ Yêu cầuthu thời gian (khá) nhanh cho việc phân lo ại/dự đoán ọ H c Máy – IT 4862 68