Bài giảng Học máy - Bài 5: Học mạng nơron nhân tạo- Nguyễn Nhật Quang

Học Máy (IT 4862) ễ hậNguy n N t Quang quangnn-fit@mail.hut.edu.vn Trường Đại học Bách Khoa Hà Nội Viện Công nghệ thông tin và truyền thông Năm học 2011-2012 Nội d ô hung m n ọc: „ Giới thiệu chung „ Đánh giá hiệu năng hệ thống học máy „ Các phương pháp học dựa trên xác suất „ 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) „ Các phương pháp học không giám sát L ộ tᄠọc c ng c „ Học tăng cường 2 Học Máy – IT 4862 Mạng nơ-ron nhân tạo – Giới thiệu (1) „ Mạng nơ-ron nhân tạo (Artificial neural network – ANN) ‰ Mô phỏng các hệ thống nơ-ron sinh học (các bộ não con người) ‰ ANN là một cấu trúc (structure/network) được tạo nên bởi một số lượng các nơ-ron (artificial neurons) liên kết với nhau „ Mỗi nơ-ron ‰ Có một đặc tính vào/ra Th hiệ ột tí h t á bộ ( ột hà bộ)‰ ực n m n o n cục m m cục „ Giá trị đầu ra của một nơ-ron được xác định bởi Đặc tính vào/ra của nó‰ ‰ Các liên kết của nó với các nơ-ron khác ‰ (Có thể) các đầu vào bổ sung 3Học Máy – IT 4862 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 phâ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ứ ă (hà tiê ) ủ ột ANN đ á đị h bởi„ c n ng m mục u c a m ược x c n ‰ Kiến trúc (topology) của mạng nơ-ron ‰ Đặc tính vào/ra của mỗi nơ ron - ‰ Chiến lược học (huấn luyện) ‰ Dữ liệu học 4Học Máy – IT 4862 ANN – Các ứng dụng điển hình (1) „ Xử lý ảnh và Computer vision ‰ Ví dụ: So khớp tiền xử lý phân đoạn và phân tích ảnh computer vision , , , , nén ảnh, xử lý và hiểu các ảnh thay đổi theo thời gian „ Xử lý tín hiệu Ví d Phâ tí h tí hiệ à hì h thái đị hấ độ đất‰ ụ: n c n u v n a c n, ng „ Nhận dạng mẫu ‰ Ví dụ: Trích chọn thuộc tính, phân loại và phân tích tín hiệu ra-đa, nhận dạng và hiểu giọng nói, nhận dạng dấu vân tay, nhận dạng ký tự (chữ hoặc số), nhận dạng mặt người, và phân tích chữ viết tay „ Y tế ‰ Ví dụ: Phân tích và hiểu tín hiệu điện tim, chẩn đoán các loại bệnh, và xử lý các ảnh trong lĩnh vực y tế 5Học Máy – IT 4862 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ập kế hoạch, điều khiể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ời giải h bài t á ời đ hà điề khiể à kh h hiê ứ ềc o o n ngư ưa ng, u n v oa ọc ng n c u v 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ện và khắc phục sự cố, dự đoán tải (khối lượng) công việc, và đánh giá mức độ an toàn „ ...(và nhiều lĩnh vực bài toán khác!) 6Học Máy – IT 4862 Cấu trúc và hoạt động của một nơ-ron „ Các tín hiệu đầu vào (input signals) của nơ-ron (xi, i=1 m) x0=1.. ‰ Mỗi tín hiệu đầu vào xi gắn với một trọng số wi „ Trọng số điều chỉnh (bias) x1 Σx2 w0 w1 w2 Giá trị đầw0 (với x0=1) „ Đầu vào tổng thể (Net input) là một hàm tích hợp ủ á tí hiệ đầ à xm wm u ra của nơ-ron (Out)c a c c n u u v o – Net(w,x) „ Hàm tác động/truyền (Activation/transfer Các tín Đầu vào Hàm tác function) tính giá trị đầu ra của nơ-ron – f(Net(w,x)) „ Giá trị đầu ra (Output) của hiệu đầu vào của nơ-ron ( ) tổng thể (Net) động (truyền) (f) 7Học Máy – IT 4862 nơ-ron: Out=f(Net(w,x)) x Đầu vào tổng thể và dịch chuyển ∑∑ mm „ Đầ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 == =+=++++= i ii i iimm xwxwwxwxwxwwNet 01 022110 1.... „ Ý nghĩa của tín hiệu dịch chuyển (bias) w0 Họ các hàm phân tách N t không thể phân tách đ ợc các→ e =w1x1 ư ví dụ thành 2 lớp (two classes) →Nhưng: họ các hàm Net=w1x1+w0 có thể! Net = w1x1 Net Net Net = w1x1 + w0 x1 x1 8Học Máy – IT 4862 Hàm tác động: Giới hạn cứng (Hard-limiter) „ Còn được gọi là hàm ngưỡng (threshold function) ầ ấ ⎩ ⎨⎧ ≥== lainguocnêu0 nêu ,1 ),(1)( θθ NetNethlNetOut „ Giá trị đ u ra l y một trong 2 giá trị „ θ là giá trị ngưỡng „ Nhược điểm: không liên tục, đạo , ),(),(2)( θθ NetsignNethlNetOut == OutBinary Out hàm không liên tục hard-limiter 1 1 Bipolar hard-limiter θ 0 Net Net0θ -1 9Học Máy – IT 4862 Hàm tác động: Logic ngưỡng (Threshold logic) ⎪⎪ ⎪ ⎨ ⎧ −≤≤−+ −< == θθθα θ θα 1if)( if ,0 )()( NetNet Net NettlNetOut O t ⎪⎪ ⎪ ⎩ −> θα α 1 if ,1 ,,, Net (α >0)u 1 )))(,1min(,0max( θα += Net „ Còn được gọi là hàm tuyến tính bã hò ( t ti li f ti ) 0 Net-θ (1/α)-θ o a sa ura ng near unc on „ Kết hợp của 2 hàm tác động: tuyến tính và giới hạn chặt ố 1/α „ α xác định độ d c của khoảng tuyến tính „ Nhược điểm: Liên tục – nhưng đ hà khô liê t 10Học Máy – IT 4862 ạo m ng n ục Hàm tác động: Xích-ma (Sigmoidal) )(1 1),,()( θαθα +−+== NetNetsfNetOut Out e „Được dùng phổ biến nhất 1 „Tham số α xác định độ dốc „Giá trị đầu ra trong khoảng (0,1) 0-θ Net 0.5 „Ưu điểm ‰ Liên tục, và đạo hàm liên tục Đ hà ủ ột hà í h‰ ạo m c a m m x c -ma được biểu diễn bằng một hàm của chính nó 11Học Máy – IT 4862 Hàm tác động: Hyperbolic tangent 1 1 2 1 1),,tanh()( )()( )( −=−== ++ +− θαθα θα θα NetNet NeteNetNetOut ++ −− ee Out„ Cũng hay được sử dụng 1 „ Tham số α xác định độ dốc „ Giá trị đầu ra trong khoảng (-1,1) 0-θ Net „ Ưu điểm ‰ Liên tục, và đạo hàm liên tục ‰Đạo hàm của một hàm tanh có thể -1 được biểu diễn bằng một hàm của chính nó 12Học Máy – IT 4862 ANN – Kiến trúc mạng (1) input bias„Kiến trúc của một ANN được x/đ bởi: ‰ Số lượng các tín hiệu đầu vào và đầu ra hidden layer ‰ Số lượng các tầng ‰ Số lượng các nơ-ron trong mỗi tầng ‰ Số lượng các trọng số (các liên kết) đối ỗ output layer output với m i nơ-ron ‰Cách thức các nơ-ron (trong một tầng, hoặc giữa các tầng) liên kết với nhau Nhữ à hậ á tí hiệ‰ ng nơ-ron n o n n c c n u điều chỉnh lỗi „Một ANN phải có ầ ầ Ví dụ: Một ANN với một tầng ẩn • Đầu vào: 3 tín hiệu ‰Một t ng đ u vào (input layer) ‰Một tầng đầu ra (output layer) ‰ Không, một, hoặc nhiều tầng ẩn (hidden l ( )) • Đầu ra: 2 giá trị • Tổng cộng, có 6 neurons - 4 ở tầng ẩn 13Học Máy – IT 4862 ayer s - 2 ở tầng đầu ra ANN – Kiến trúc mạng (2) „ Một tầng (layer) chứa một nhóm các nơ-ron „ Tầng ẩn (hidden layer) là một tầng nằm ở giữa tầng đầu vào (input layer) và tầng đầu ra (output layer) Cá út ở tầ ẩ (hidd d ) khô t tá t„ c n ng n en no es ng ương c rực tiếp với môi trường bên ngoài (của mạng nơ-ron) „ Một ANN được gọi là liên kết đầy đủ (fully connected) nếu mọi đầu ra từ một tầng liên kết với mọi nơ-ron của tầng kế tiếp 14Học Máy – IT 4862 ANN – Kiến trúc mạng (3) „ Một ANN được gọi là mạng lan truyền tiến (feed- forward network) nếu không có bất kỳ đầu ra của một nút là đầu vào của một nút khác thuộc cùng tầng (hoặc thuộc một tầng phía trước) „ Khi các đầu ra của một nút liên kết ngược lại làm các đầu vào của một nút thuộc cùng tầng (hoặc thuộc một tầng phía trước) thì đó là một mạng phản hồi (feedback, network) ‰ Nếu phản hồi là liên kết đầu vào đối với các nút thuộc cùng tầng, thì đó là phản hồi bên (lateral feedback) „ Các mạng phản hồi có các vòng lặp kín (closed loops) được gọi là các mạng hồi quy (recurrent networks) 15Học Máy – IT 4862 Kiến trúc mạng – Ví dụ Mạng lan truyền tiến ầ Một nơ-ron với 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ều tầng Mạng hồi quy nhiều tầng 16Học Máy – IT 4862 ANN – Các quy tắc học „ 2 kiểu học trong các mạng nơ-ron nhân tạo ‰ Học tham số (Parameter learning) → Mục tiêu là thay đổi thích nghi các trọng số (weights) của các liên kết trong mạng nơ-ron ‰ Học cấu trúc (Structure learning) → Mục tiêu là thay đổi thích nghi cấu trúc mạng, bao gồm số lượng các nơ-ron và các kiểu liên kết giữa chúng „ 2 kiểu học này có thể được thực hiện đồng thời hoặc riêng rẽ ầ ắ ể„ Ph n lớn các quy t c học trong ANN thuộc ki u học tham số ố„ Trong bài học này, chúng ta sẽ chỉ xét việc học tham s 17Học Máy – IT 4862 Quy tắc học trọng số tổng quát x0= 1 „ Tại bước học (t), mức độ điều chỉnh vec-tơ trọng số w tỷ lệ Δw a neuron x ... w0 wj w1 xj x1 Out thuận với tích của tín hiệu học r(t) và đầu vào x(t) Δw(t) ~ r(t).x(t) η xwmxm ... Learning signal generator d Δw(t) = η.r(t).x(t) trong đó η (>0) là tốc độ học (learning rate) „ Tín hiệu học r là một hàm của w, x, và giá trị đầu ra mong muốn d Lưu ý: xj có thể là: • một tín hiệu đầu vào, hoặc r = g(w,x,d) „Quy tắc học trọng số tổng quát Δw(t) = η.g(w(t),x(t),d(t)).x(t) • một giá trị đầu ra của một nơ- ron khác 18Học Máy – IT 4862 Perceptron x0=1 „ Một perceptron là một kiểu đơn giản nhất của ANNs x1 x2 w0 w1 Out (chỉ gồm duy nhất một nơ- ron) Σ xm w2 wm ⎞⎛ m „ Sử dụng hàm tác động giới hạn chặt ( ) ⎟⎟⎠⎜⎜⎝== ∑=j jj xwsignxwNetsignOut 0),( „ Đối với một ví dụ x, giá trị đầu ra của perceptron là ‰1, nếu Net(w,x)>0 1 ế l i 19Học Máy – IT 4862 ‰ - , n u ngược ạ Perceptron – Minh họa Mặt phẳng phân tách w0+w1x1+w2x2=0x1 Đầu ra = 1 Đầu ra = -1 x2 20Học Máy – IT 4862 Perceptron – Giải thuật học „ Với một tập các ví dụ học D= {(x,d)} ‰ x là vectơ đầu vào ‰ d là giá trị đầu ra mong muốn (-1 hoặc 1) „ Quá trình học của perceptron nhằm xác định một vectơ trọng số cho phép perceptron sinh ra giá trị đầu ra chính xác ( 1 - hoặc 1) cho mỗi ví dụ học „ Với một ví dụ học x được perceptron phân lớp chính xác, thì vectơ trọng số w không thay đổi „ Nếu d=1 nhưng perceptron lại sinh ra -1 (Out=-1), thì w cần được thay đổi sao cho giá trị Net(w x) tăng lên , „ Nếu d=-1 nhưng perceptron lại sinh ra 1 (Out=1), thì w cần được thay đổi sao cho giá trị Net(w,x) giảm đi 21Học Máy – IT 4862 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 22 Học Máy – IT 4862 Perceptron batch(D, η)_ Initialize w (wi← an initial (small) random value) do ∆w ← 0 for each training instance (x,d)∈D Compute the real output value Out if (Out≠d) ∆w ← ∆w + η(d Out)x - end for w ← w + ∆w until all the training instances in D are correctly classified return w 23 Học Máy – IT 4862 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 perceptron không ‰ Các ví dụ học là có thể phân tách tuyến tính (linearly separable) ‰ Sử dụng một tốc độ học η đủ nhỏ thể phân lớp chính xác đối với tập học này! „ 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ất của hàm mục 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ơ ố ấ 24Học Máy – IT 4862 trọng s phù hợp nh t với các ví dụ học Hàm đánh giá lỗi (Error function) „ Xét một ANN có n nơ-ron đầu ra Đối ới ột í d h ( d) iá t ị lỗi h (t i i ) 2 „ v m v ụ ọc x, , g r ọc ra n ng error gây ra bởi vectơ trọng số (hiện tại) w: ( ) 12 1)( ∑ = −= n i ii OutdE wx Lỗi h â bởi t t ố (hiệ t i) đối ới ∑1 „ ọc g y ra vec ơ rọng s n ạ w v toàn bộ tập học D: ∈ = D D ED E x x ww )()( 25Học Máy – IT 4862 Gradient descent „ Gradient của E (ký hiệu là ∇E) là một vectơ ‰ Có hướng chỉ đi lên (dốc) ⎞⎛ ‰ Có độ dài tỷ lệ thuận vớ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 ⎟⎟⎠⎜ ⎜ ⎝ ∂ ∂ ∂ ∂ ∂ ∂=∇ Nw E w E w EE ,...,,)( 21 w trong đó N là tổng số các trọng số (các liên kết) trong mạng E∂ „ 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 Ni w w i i ..1 , =∀∂−=Δ ηΔw = -η.∇E(w); „ Yêu cầu: Các hàm tác động được sử dụng trong mạng phải là 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 26Học Máy – IT 4862 , Gradient descent – Minh họa Không gian một chiều Không gian 2 chiều E(w) E(w1,w2) 27Học Máy – IT 4862 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 w i 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 28 , , ... Học Máy – IT 4862 ANN nhiều tầng và giải thuật lan truyền ngược „ Một perceptron chỉ có thể biểu diễn một hàm phân tách tuyến tính (linear separation function) „ Một mạng nơ-ron nhiều tầng (multi-layer NN) được học bởi giải thuật lan truyền ngược (back-propagation -BP- algorithm) có thể biểu diễn một hàm phân tách phi tuyến phức tạp (highly non-linear separation function) „ Giải thuật học BP được sử dụng để học các trọng số của một mạng nơ-ron nhiều tầng ‰ Cấu trúc mạng cố định (các nơ-ron và các liên kết giữa chúng là cố định) ‰ Đối với mỗi nơ-ron, hàm tác động phải có đạo hàm liên tục Giải th ật BP á d hiế l di t d t t tắ ậ„ u p ụng c n ược gra en escen rong quy c c p nhật các trọng số ‰ Để cực tiểu hóa lỗi (khác biệt) giữa các giá trị đầu ra thực tế và các giá trị đầu ra mong muốn đối với các ví dụ học 29Học Máy – IT 4862 , Giải thuật học lan truyền ngược (1) „ Giải thuật học lan truyền ngược tìm kiếm một vectơ các trọng số (weights vector) giúp cực tiểu hóa lỗi tổng thể của hệ thố đối ới tậ hng v p ọc „ Giải thuậ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ền tiến từ tầng đầu vào đến tầng đầu ra (đi qua các tầng ẩn) ‰ Giai đoạn lan truyền ngược lỗi (Error backward) „ Căn cứ vào giá trị đầu ra mong muốn của vectơ đầu vào, hệ thống tính toán giá trị lỗi „ Bắt đầu từ tầng đầu ra, giá trị lỗi được lan truyền ngược qua mạng, từ tầng này qua tầng khác (phía trước), cho đến tầng đầu vào „ Việc lan truyền ngược lỗi (error back-propagation) được thực hiện thông qua việc tính toán (một cách truy hồi) giá trị gradient cục bộ của mỗi nơ ron 30Học Máy – IT 4862 - Giải thuật học lan truyền ngược (2) Giai đoạn lan truyền tiến tín hiệu: • Kích hoạt (truyền tín hiệu qua) mạng Giai đoạn lan truyền ngược lỗi: • Tính toán lỗi ở đầu ra • Lan truyền (ngược) lỗi 31Học Máy – IT 4862 Giải thuật BP – Cấu trúc mạng x1 xj xm... ...Input xj „ Xét mạng nơ-ron 3 tầng (trong hình vẽ) để minh họa giải thuật học BP Hidden wqj (j=1..m) „ m tín hiệu đầu vào xj (j=1..m) „ l nơ-ron tầng ẩn zq (q=1..l) „ n nơ ron đầu ra y (i=1 n) neuron zq (q=1..l) wiq Outq ... ... - i .. „ wqj là trọng số của liên kết từ tín hiệu đầu vào xj tới nơ-ron tầng ẩn zq Out ... ...Output neuron yi (i=1 n) „ wiq là trọng số của liên kết từ nơ-ron tầng ẩn zq tới nơ-ron đầu ra yi i..„ 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ới nơ ron đầu ra y 32Học Máy – IT 4862 - i Giải thuật BP – Lan truyền tiến (1) „ Đối với mỗi ví dụ học x ‰ Vectơ đầu vào x được lan truyền từ tầng đầu vào đến tầng đầu ra ‰ Mạng sẽ sinh ra một giá trị đầu ra thực tế (actual output) Out (là một vectơ của các giá trị Outi, i=1..n) ố ầ ầ ẩ m „ Đ i với một vectơ đ u vào x, một nơ-ron zq ở t ng n sẽ nhận được giá trị đầu vào tổng thể (net input) bằng: ∑ = = j jqjq xwNet 1 và sinh ra một giá trị đầu ra (cục bộ) bằng: ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛== ∑ = m j jqjqq xwfNetfOut 1 )( trong đó f( ) là hàm tác động (activation function) của nơ ron z 33Học Máy – IT 4862 . - q 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 đầu ra ∑ ∑∑ = == ⎟ ⎟ ⎠ ⎞ ⎜⎜⎝ ⎛== l q m j jqjiq l q qiqi xwfwOutwNet 1 11 ⎞⎛ ⎞⎛⎞⎛ ll „ Nơ-ron yi sinh ra giá trị đầu ra (là một giá trị đầu ra của mạng) ⎟⎟⎠⎜ ⎜ ⎝ ⎟ ⎟ ⎠⎜ ⎜ ⎝ =⎟⎟⎠⎜ ⎜ ⎝ == ∑ ∑∑ = == q m j jqjiq q qiqii xwfwfOutwfNetfOut 1 11 )( „ 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 34Học Máy – IT 4862 Giải thuật BP – Lan truyền ngược (1) „ Đối với mỗi ví dụ học x ‰ Các tín hiệu lỗi (error signals) do sự khác biết giữa giá trị đầu ra mong muốn d và giá trị đầu ra thực tế Out được tính toán ‰ Các tín hiệu lỗi này được lan truyền ngược (back-propagated) từ tầng đầu ra tới các tầng phía trước, để cập nhật các trọng số (weights) „ Để xét các tín hiệu lỗi và việc lan truyền ngược của ( ) ( ) ( )[ ]∑∑ −=−= n iin ii NetfdOutdwE 22 2121 chúng, cần định nghĩa một hàm đánh giá lỗi == ii 11 ∑ ∑ ⎥⎥⎦ ⎤ ⎢⎢⎣ ⎡ ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛−= n i l q qiqi Outwfd 1 2 12 1 = = 35Học Máy – IT 4862 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 ẩn tới tầng đầu ra được cập nhật bởi iq iq w Ew ∂ ∂−=Δ η Sử d tắ h ỗi đ hà đối ới ∂E/∂ t ó [ ] ( )[ ][ ] qiqiii iq i i i i iq OutOutNetfOutdw Net Net Out Out Ew ηδηη =−=⎥⎥⎦ ⎤ ⎢⎢⎣ ⎡ ∂ ∂⎥⎦ ⎤⎢⎣ ⎡ ∂ ∂⎥⎦ ⎤⎢⎣ ⎡ ∂ ∂−=Δ ' „ ụng quy c c u ạo m v wiq, a c (Lưu ý: dấu “–” đã được kết hợp với giá trị ∂E/∂Outi) „ δi là tín hiệu lỗi (error signal) của nơ-ron yi ở tầng đầu ra [ ] ( )[ ]iii i i ii i NetfOutdNet Out Out E Net E '−=⎥⎦ ⎤⎢⎣ ⎡ ∂ ∂⎥⎦ ⎤⎢⎣ ⎡ ∂ ∂−=∂ ∂−=δ trong đó Neti là đầu vào tổng thể (net input) của nơ-ron yi ở tầng 36Học Máy – IT 4862 đầu ra, và f'(Neti)=∂f(Neti)/∂Neti Giải thuật BP – Lan truyền ngược (3) „ Để cập nhật các trọng số của các liên kết từ tầng đầu vào tới tầng ẩn chúng ta cũng áp dụng phương pháp ⎤⎡∂⎤⎡∂⎤⎡ ∂∂ N tO tEE , gradient-descent và quy tắc chuỗi đạo hàm ⎥⎥⎦⎢ ⎢ ⎣ ∂⎥ ⎥ ⎦⎢ ⎢ ⎣ ∂⎥ ⎥ ⎦⎢ ⎢ ⎣∂ −=∂−=Δ qj q q q qqj qj w e Net u Outw w ηη ỗ ấ ằ ỗ 2 „ Từ công thức tính hàm l i E(w), ta th y r ng m i thành phần lỗi (di-yi) (i=1..n) là một hàm của Outq ∑ ∑ = = ⎥⎥⎦ ⎤ ⎢⎢⎣ ⎡ ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛−= n i l q qiqi OutwfdE 1 12 1)(w 37Học Máy – IT 4862 Giải thuật BP – Lan truyền ngược (4) n „ Áp dụng quy tắc chuỗi đạo hàm, ta có ( ) ( )[ ] ( ) jq i iqiiiqj xNetfwNetfOutdw '' 1 ∑ = −=Δ η [ ] ( )n xxNetfw ηδδη∑ ' jqjq i iqi == =1 „ δq là tín hiệu lỗi (error signal) của nơ-ron zq ở tầng ẩn ( ) iqn i iq q q qq q wNetfNet Out Out E Net E ∑ = =⎥⎥⎦ ⎤ ⎢⎢⎣ ⎡ ∂ ∂ ⎥⎥⎦ ⎤ ⎢⎢⎣ ⎡ ∂ ∂−=∂ ∂−= 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 38Học Máy – IT 4862 Giải thuật BP – Lan truyền ngược (5) „ Theo các công thức tính các tín hiệu lỗi δi và δq đã nêu, thì tín hiệu lỗi của một nơ-ron ở tầng ẩn khác với tín hiệu lỗi của một nơ-ron ở tầng đầu ra „ Do sự khác biệt này, thủ tục cập nhật trọng số trong giải thuật BP được gọi là quy tắc học delta tổng quát „ Tín hiệu lỗi δq của nơ-ron zq ở tầng ẩn được xác định bởi ‰ Các tín hiệu lỗi δi của các nơ-ron yi ở tầng đầu ra (mà nơ-ron zq liên kết tới) và , ‰ Các hệ số chính là các trọng số wiq „ Đặc điểm quan trọng của giải thuật BP: Quy tắc cập nhật trọng số có tính cục bộ ‰ Để tính toán thay đổi (cập nhật) trọng số của một liên kết, hệ thống chỉ cần sử dụng các giá trị ở 2 đầu của liên kết đó! 39Học Máy – IT 4862 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ộng (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ổng quát của quy tắc cập nhật trọng số trong 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ị đầu ra của nơ-ron ở tầng ẩn (hoặc tín hiệu đầu vào) b , ‰ δa là tín hiệu lỗi của nơ-ron a 40Học Máy – IT 4862 Back_propagation_incremental(D, η) Mạng nơ-ron gồm Q tầng, q = 1,2,...,Q qNeti và qOuti là đầu vào tổng thể (net input) và giá trị đầu ra của nơ-ron i ở tầng q Mạng có m tín hiệu đầu vào và n nơ-ron đầu ra qwij là trọng số của liên kết từ nơ-ron j ở tầng (q-1) đến nơ-ron i ở tầng q Bước 0 (Khởi tạo) Chọn ngưỡng lỗi Ethreshold (giá trị lỗi có thể chấp nhận được) Khởi tạo giá trị ban đầu của các trọng số với các giá trị nhỏ ngẫu nhiên Gán E=0 Bước 1 (Bắt đầu một chu kỳ học) Á d t đầ à ủ í d h k đối ới tầ đầ à ( 1)p ụng vec ơ u v o c a v ụ ọc v ng u v o q= qOuti = 1Outi = xi(k), ∀i Bước 2 (Lan truyền tiến) ( ) ⎟⎟⎞⎜⎜⎛== ∑ − jqijqiqiq OutwfNetfOut 1 Lan truyền tiến các tín hiệu đầu vào qua mạng, cho đến khi nhận được các giá trị đầu ra của mạng (ở tầng đầu ra) QOuti ⎠⎝ j 41 Học Máy – IT 4862 Bước 3 (Tính toán lỗi đầu ra) Tính toán lỗi đầu ra của mạng và tín hiệu lỗi Qδi của mỗi nơ-ron ở tầng đầu ra ∑ = −+= n i i Qk i OutdEE 1 2)( )( 2 1 )Net'()fOut(dδ QQ(k)Q −= iiii Bước 4 (Lan truyền ngược lỗi) Lan truyền ngược lỗi để cập nhật các trọng số và tính toán các tín hiệu lỗi q-1δi cho các tầng phía trước 2,...,1, allfor ;11 −== ∑−− QQqδw)Net'(fδ jqjiqiqiq Δqwij = η.(qδi).(q-1Outj); qwij = qwij + Δqwij jBước 5 (Kiểm tra kết thúc một chu kỳ học – epoch) Kiểm tra xem toàn bộ tập học đã được sử dụng (đã xong một chu kỳ học – epoch) Nếu toàn bộ tập học đã được dùng, chuyển đến Bước 6; ngược lại, chuyển đến Bước 1 Bước 6 (Kiểm tra lỗi tổng thể) Nếu lỗi tổng thể E nhỏ hơn ngưỡng lỗi chấp nhận được (<Ethreshold), thì quá trình học kết thúc và trả về các trọng số học được; 42 Học Máy – IT 4862 Ngược lại, gán lại E=0, và bắt đầu một chu kỳ học mới (quay về Bước 1) Giải thuật BP – Lan truyền tiến (1) f(Net1) 1x f(Net4) f(Net2) Out6f(Net6) 2x f(Net5) f(Net3) 43Học Máy – IT 4862 Giải thuật BP – Lan truyền tiến (2) 11 xw f(Net1) 1x 1x 21 2 xw x f(Net4) Out6 f(Net2) f(Net6) 2x f(Net5) )( 21111 21 xwxwfOut xx +=f(Net3) 44Học Máy – IT 4862 Giải thuật BP – Lan truyền tiến (3) f(Net1) 1x f(Net4) 12 1 xw x Out6 f(Net2) f(Net6) 2x 22 2 xw x f(Net5) )( 22122 21 xwxwfOut xx +=f(Net3) 45Học Máy – IT 4862 Giải thuật BP – Lan truyền tiến (4) f(Net1) 1x f(Net4) Out6 f(Net2) f(Net6) 2x 13 1xw x f(Net5) 23 2 xw x )( 23133 21 xwxwfOut xx +=f(Net3) 46Học Máy – IT 4862 Giải thuật BP – Lan truyền tiến (5) Outwf(Net1) 1x 242Outw 141 f(Net4) 343Outw Out6 f(Net2) f(Net6) 2x f(Net5) )( 3432421414 OutwOutwOutwfOut ++= f(Net3) 47Học Máy – IT 4862 Giải thuật BP – Lan truyền tiến (6) f(Net1) 1x 151Outw f(Net4) O t Out6 f(Net2) f(Net6) 2x 252 uw f(Net5) 353Outw )( 3532521515 OutwOutwOutwfOut ++= f(Net3) 48Học Máy – IT 4862 Giải thuật BP – Lan truyền tiến (7) f(Net1) 1x 464Outw f(Net4) Out6 f(Net2) f(Net6) 2x 565Outwf(Net5) )( 5654646 OutwOutwfOut +=f(Net3) 49Học Máy – IT 4862 Giải thuật BP – Tính toán lỗi f(Net1) 1x f(Net4) δ6 Out6 f(Net2) f(Net6) 2x f(Net5) d is the desired [ ] ( )[ ]6666 ' NetfOutdN t Out O t E N t E −=⎥⎦ ⎤⎢⎣ ⎡ ∂ ∂⎥⎦ ⎤⎢⎣ ⎡ ∂ ∂−=∂ ∂−=δ f(Net3) output value 666 eue 50Học Máy – IT 4862 Giải thuật BP – Lan truyền ngược (1) δf(Net1) 1x 64w δ 4 f(Net4) 6 Out6 f(Net2) f(Net6) 2x f(Net5) )δ)(w(Netfδ 66444 '= f(Net3) 51Học Máy – IT 4862 Giải thuật BP – Lan truyền ngược (2) f(Net1) 1x δ6f(Net4) δ5 Out6 f(Net2) f(Net6) 2x 65w f(Net5) )δ)(w'(Netfδ 66555 =f(Net3) 52Học Máy – IT 4862 Giải thuật BP – Lan truyền ngược (3) δ1 f(Net ) 1x 41w 51w δ41 f(Net4) Out6 f(Net ) f(Net6) x δ52 f(Net5) 2 )δwδ)(w'(Netfδ 55144111 +=f(Net3) 53Học Máy – IT 4862 Giải thuật BP – Lan truyền ngược (4) δ4f(Net1) 1x 42wδ f(Net4) 52w δ 2 Out6 f(Net2) f(Net6) 2x 5 f(Net5) )δwδ)(w'(Netfδ 55244222 +=f(Net3) 54Học Máy – IT 4862 Giải thuật BP – Lan truyền ngược (5) δ4f(Net1) 1x f(Net4) 43w δ Out6 f(Net2) f(Net6) 2x 53w 5 δ f(Net5) )δwδ)(w'(Netfδ 55344333 += 3 f(Net3) 55Học Máy – IT 4862 Giải thuật BP – Cập nhật trọng số (1) 1w δ1 f(Net1) 1x 1x 1xw f(Net4)2 Out6 f(Net2) f(Net6) 2x f(Net5) 1111 11 xww xww xx ηδ ηδ += += f(Net3) 2111 22 xx 56Học Máy – IT 4862 Giải thuật BP – Cập nhật trọng số (2) f(Net1) 1x δ f(Net4) 12x w 2 Out6 f(Net2) f(Net6) 2x 22x w f(Net5) 2222 1222 11 xww xww xx ηδ ηδ += += f(Net3) 22 xx 57Học Máy – IT 4862 Giải thuật BP – Cập nhật trọng số (3) f(Net1) 1x f(Net4) Out6 f(Net2) f(Net6) 2x 13xw δ3 f(Net5) 23x w 2333 1333 11 xww xww xx xx ηδ ηδ += += f(Net3) 22 58Học Máy – IT 4862 Giải thuật BP – Cập nhật trọng số (4) w δ4 f(Net1) 1x 42w 41 f(Net4) 43w Out6 f(Net2) f(Net6) 2x Outww ηδ+ f(Net5) 244242 144141 Outww Outww ηδ ηδ += += = f(Net3) 344343 59Học Máy – IT 4862 Giải thuật BP – Cập nhật trọng số (5) f(Net1) 1x f(Net4) 51w δ5 Out6 f(Net2) f(Net6) 2x 52 w Outww ηδ+ f(Net5) 53w 255252 155151 Outww Outww ηδ ηδ += += = f(Net3) 355353 60Học Máy – IT 4862 Giải thuật BP – Cập nhật trọng số (6) f(Net1) 1x 64w δ6 f(Net4) Out6 f(Net2) f(Net6) 2x 65w f(Net5) 466464 Outηδww Outηδww += +=f(Net3) 566565 61Học Máy – IT 4862 BP: Khởi tạo giá trị của các trọng số „ Thông thường, các trọng số được khởi tạo với các giá trị nhỏ ngẫu nhiên „ Nếu các trọng số có các giá trị ban đầu lớn ‰ Các hàm xích-ma (sigmoid functions) sẽ đạt trạng thái bão hòa sớm ‰ Hệ thống sẽ tắc ở một điểm cực tiểu cục bộ (local minimum) hoặc ở một trạng thái không đổi (very flat plateau) gần điểm bắt đầu „ Các gợi ý cho w0 b (liên kết từ nơ-ron b tới nơ-ron a) a ‰ Ký hiệu na là số lượng các nơ-ron ở cùng tầng với nơ-ron a w0ab ∈ [−1/na, 1/na] ]k/k/[w ab 330 −∈ ‰ Ký hiệu ka là số lượng các nơ-ron có liên kết (tiến) đến nơ-ron a (=số lượng các liên kết đầu vào của nơ-ron a) , aa 62Học Máy – IT 4862 BP: Tốc độ học (Learning rate) „ Ảnh hưởng quan trọng đến hiệu quả và khả năng hội tụ của giải thuật học BP Một iá t ị lớ ó thể đẩ h h hội t ủ á t ì h h h ó‰ g r η n c y n an sự ụ c a qu r n ọc, n ưng c thể làm cho hệ thống bỏ qua điểm tối ưu toàn cục hoặc rơi vào điểm tối ưu cục bộ ‰ Một giá trị η nhỏ có thể làm cho quá trình học kéo dài rất lâu „ Thường được chọn theo thực nghiệm (experimentally) đối với mỗi bài toán „ Các giá trị tốt của tốc độ học ở lúc bắt đầu (quá trình học) có thể không tốt ở một thời điểm sau đấy ‰ Nên sử dụng một tốc độ học thích nghi (động) „ Sau khi cập nhật các trọng số, kiểm tra xem việc cập nhật các trọng số có giúp làm giảm giá trị lỗi Δη = a , if ΔE < 0 consistently -bη , if ΔE > 0 (a, b > 0) 0 , otherwise. 63Học Máy – IT 4862 BP: Momentum -η∇E(t’+1) + αΔw(t’) αΔw(t’) -η∇E(t’+1) Δw(t’) B „ Phương pháp Gradient descent có thể rất chậm nếu η nhỏ, và có thể d độ h ế á lớ A’ A Δw(t) ao ng mạn n u η qu n „ Để giảm mức độ dao động, cần đưa vào một thành phần B’ ∇E(t+1) + Δ (t) αΔw(t) -η∇E(t+1) momentum Δw(t) = -η∇E(t) + αΔw(t-1) trong đó α (∈[0,1]) là một tham số -η α w Gradient descent đối với một hàm lỗi bậc 2 đơn giản. momentum (thường lấy =0.9) „ Một quy tắc, dựa trên các thí nghiệm để chọn các giá trị hợp lý Quỹ đạo bên trái không sử dụng momentum. Quỹ đạo bên phải có sử dụng , cho tốc độ học và momentum là: (η+α) >≈ 1; trong đó α>η để tránh dao động momentum. 64Học Máy – IT 4862 BP: Số lượng các nơ-ron ở tầng ẩn „ Kích thước (số nơ-ron) của tầng ẩn là một câu hỏi quan trọng đối với việc áp dụng các mạng nơ-ron lan truyền tiến nhiều tầng ể ế ếđ giải quy t các bài toán thực t „ Trong thực tế, rất khó để xác định chính xác số lượng các nơ- ron cần thiết để đạt được một độ chính xác mong muốn của hệ thống „ Kích thước của tầng ẩn thường được xác định qua thí nghiệm (experimentally/trial and test) „ Gợi ý ‰ Bắt đầu với số lượng nhỏ các nơ-ron ở tầng ẩn (=tỷ lệ nhỏ so với số lượng các tín hiệu đầu vào) ‰ Nếu mạng không thể hội tụ, bổ sung thêm các nơ-ron vào tầng ẩn ‰ Nếu mạng hội tụ có thể xem xét sử dụng ít hơn các nơ-ron tầng ẩn 65Học Máy – IT 4862 , 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á hà liê t (C ti f ti )„ c m n ục on nuous unc 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ột ANN sử dụng 2 tầng ẩn [Cybenko 1988] , 66Học Máy – IT 4862 ANNs – Ưu điểm, Nhược điểm „ Các ưu điểm ‰ Bản chất (về cấu trúc) hỗ trợ tính toán song song ở mức (rất) cao ‰ Khả năng chịu nhiễu/lỗi, nhờ kiến trúc tính toán song song ‰ Có thể được thiết kế để tự thích nghi (các trọng số, cấu trúc mạng) „ Các nhược điểm ‰ Không có quy tắc tổng quát để xác định cấu trúc mạng và các th ố h tối h ột (lớ ) bài t á hất đị ham s ọc ưu c o m p o n n n ‰ Không có phương pháp tổng quát để đánh giá hoạt động bên trong của ANN (vì vậy, hệ thống ANN bị xem như một “hộp đen”) ‰ Rất khó (không thể) đưa ra giải thích cho người dùng ‰ Rất khó để dự đoán hiệu năng của hệ thống trong tương lai (khả năng khái quát hóa của hệ thống học) 67Học Máy – IT 4862 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ểu rời rạc hoặc kiểu số „ Miền giá trị đầu ra của hàm mục tiêu có kiểu số thực, hoặc kiểu rời rạc, hoặc kiểu 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ầu thời gian (khá) nhanh cho việc phân loại/dự đoán 68Học Máy – IT 4862