Bài giảng Trí tuệ nhân tạo - Chương 6: Học máy - Lê Thanh Hương

1Chương 6. Học máy Lê Thanh Hương Bộ ô HTTT Kh CNTT 1 m n , oa Đại học Bách khoa Hà Nội 6.1. Học “Học đề cập đến các thay đổi của hệ thống theo hướng thích nghi: chúng cho phép hệ thống thực hiện các công việc trong cùng một môi trường hiệu quả hơn từ lần thực hiện thứ 2” 2 Các phương pháp học • Học có giám sát: biết trước câu trả lời đúng • Học không giám sát: không biết trước câu trả lời đúng • Học tăng cường: đôi khi có thưởng/phạt cho các hành động 3 Những gì cần học? • Mẹo trong tìm kiếm • Hàm đánh giá trò chơi • Tri thức khai báo (các mệnh đề logic) • Các bộ phân loại Cấu trúc phân loại 4 – – Ngữ pháp 2Học có giám sát: qui nạp • Trường hợp tổng quát: – Cho tập các cặp (x, f(x)), tìm hàm f. • Phân loại: – Cho tập các cặp (x, y) với y là 1 nhãn, tìm hàm cho phép gán x với giá trị đúng của nó. • Phân loại đơn giản: 5 – Cho tập các cặp (x, y) với x là 1 đối tượng và y = + nếu x thuộc đúng lớp và - nếu ngược lại. Tìm hàm cho phép gán nhãn chính xác. Coi học như việc tìm kiếm • Đoán hàm phù hợp với các đầu vào = xác định 1 giả thiết. • Không gian giả thiết = tập tất cả các giả thiết có thể. • Học là việc tìm kiếm 1 giả thiết phù hợp trong không gian giả thiết 6 Các phương pháp phân loại • Học qui nạp • Láng giềng gần • Xác suất • Cây quyết định • Mạng nơron 7 • Giải thuật di truyền • 6.2. Học cây quyết định Bài toán: quyết định có đợi 1 bàn ở quán ăn không, dựa trên các thông tin sau: 1 Lựa chọn khác: có quán ăn nào khác gần đó không?. 2. Quán rượu: có khu vực phục vụ đồ uống gần đó không? 3. Fri/Sat: hôm nay là thứ sáu hay thứ bảy? 4. Đói: chúng ta đã đói chưa? 5. Khách hàng: số khách trong quán (không có, vài người, đầy) 6. Giá cả: khoảng giá ($,$$,$$$) 8 7. Mưa: ngoài trời có mưa không? 8. Đặt chỗ: chúng ta đã đặt trước chưa? 9. Loại: loại quán ăn (Pháp, Ý, Thái, quán ăn nhanh) 10. Thời gian đợi: 0-10, 10-30, 30-60, >60 3Phép biểu diễn dựa trên thuộc tính • Các mẫu được miêu tả dưới dạng các giá trị thuộc tính (logic, rời rạc, liên tục) • Ví dụ, tình huống khi đợi 1 bàn ăn 9 • Các loại (lớp) của mẫu là khẳng định (T) hoặc phủ định (F) 10 Patrons, WaitEstimates, Alternative, Hungry, Rain Cây quyết định là cách biểu diễn các giả thiết. 11 Không gian giả thiết Khi ó th ộ tí h B l ố l á â ết đị h là? c n u c n oo ean, s ượng c c c y quy n = số các hàm Boolean = số các giá trị khác nhau trong bảng ví dụ mẫu với 2n hàng = 22n Ví dụ, với 6 thuộc tính Boolean, có 18,446,744,073,709,551,616 cây 12 4Thuật toán ID3 Mục đích: tìm cây thoả mãn tập mẫu Ý tưởng: (lặp) chọn thuộc tính quan trọng nhất làm gốc của cây/cây con ID3(Examples, Target_attribute, Attributes) /* Examples: các mẫu luyện Target_attribute: thuộc tính cần đoán giá trị Attributes: các thuộc tính có thể được kiểm tra qua phép học cây quyết định. */ • Tạo 1 nút gốc Root cho cây 13 • If ∀ Examples +, trả về cây chỉ có 1 nút Root, với nhãn + • If ∀ Examples -, trả về cây chỉ có 1 nút Root, với nhãn – • If Attributes rỗng, trả về cây chỉ có 1 nút Root, với nhãn = giá trị thường xuất hiện nhất của Target_attribute trong Examples Thuật toán ID3 • Otherwise Begin: – A ← thuộc tính trong Attributes cho phép phân loại tốt nhất Examples – Thuộc tính quyết định của nút gốc← A – Với các giá trị vi có thể có của A, • Thêm 1 nhánh mới dưới gốc, ứng với phép kiểm tra A = vi • Đặt Examplesvi = tập con của Examples với giá trị thuộc tính A = vi • If Examplesvi rỗng – Then, dưới nhánh mới này, thêm 1 lá với nhãn = giá trị ấ ấ ủ 14 thường xu t hiện nh t c a Target_attribute trong Examples – Else, dưới nhánh mới này thêm cây con ID3(Examplesvi, Target_attribute, Attributes - {A})) • End • Return Root Thuộc tính nào tốt nhất? 15 Sử dụng lượng thông tin đạt được Information Gain Ö xác định thông qua độ đo Entropy Entropy của một tập mẫu •S là một tập mẫu của tập luyện •p+ là tỷ lệ các mẫu dương trong S •p- là tỷ lệ các mẫu âm trong S 16 •Entropy đo độ nhiễu của S = số các bit cần thiết để mã hoá lớp + hoặc - của các thành viên ngẫu nhiên của S •Entropy(S) = - p+*log2p+ - p-*log2p- 5Entropy Entropy H(X) của biến ngẫu nhiên X: Ví dụ, với S gồm 9 mẫu dương và 5 mẫu âm, kí hiệu S([9+,5-]). Entropy([9+ 5-]) 17 , = - (9/14)log2(9/14) – (5/14)log2(5/14) = 0.940 Information Gain Gain(S, A) = độ giảmentropy do việc phân loại trong A Sv Gain(S,A) = Entropy(S) – )( )( SvEntropy SAValuesv ∑ ∈ 18 Ví dụ: tập luyện Day Outlook Temperature Humidity Wind PlayTennis D1 Sunny Hot High Weak No D2 Sunny Hot High Strong No S = [9+,5-] D3 Overcast Hot High Weak Yes D4 Rain Mild High Weak Yes D5 Rain Cool Normal Weak Yes D6 Rain Cool Normal Strong No D7 Overcast Cool Normal Strong Yes D8 Sunny Mild High Weak No D9 S C l N l W k Y Humidity ={High,Normal}: Shigh=[3+,4-]; Snormal=[6+,1-] Wind ={Weak,Strong}: Sweak = [6+,2-]; 19 unny oo orma ea es D10 Rain Mild Normal Weak Yes D11 Sunny Mild Normal Strong Yes D12 Overcast Mild High Strong Yes D13 Overcast Hot Normal Weak Yes D14 Rain Mild High Strong No Sstrong = [3+,3-] Thuộc tính nào phân loại tốt nhất? Humidity High Normal Wind Weak Strong S:[9+,5-] E=0.940 S:[9+,5-] E=0.940 [3+,4-] E=0.985 [6+,1-] E=0.592 [6+,2-] E=0.811 [3+,3-] E=1.000 Gain(S,Wind) = Entropy(S) – = Entropy(S) – (8/14)Entropy(SWeak) – (6/14)Entropy(SStrong) )( )( SvEntropy S Sv AValuesv ∑ ∈ 20 = 0.940 – (8/14)*0.811 – (6/14)*1.00 = 0.048 Gain(S,Humidity) = 0.940 – (7/14)*0.985 – (7/14)*0.592 = 0.151 Gain(S,Outlook)=0.246; Gain(S,Humidity)=0.151 Gain(S,Wind)=0.048; Gain(S,Temperature)=0.029 6SSunny = {D1,D2,D8,D9,D11} Gain(SSunny, Humidity ) = .970 – (3/5)*0.0 – (2/5)*0.0 = .970 Thuộc tính nào tiếp? G i (S T t ) 21 a n Sunny, empera ure = .970 –(2/5)*0.0– (2/5)*1.0– (1/5)*0.0=.570 Gain(SSunny, Wind ) = 0.970 – (2/5)*1.0 – (3/5)*0.918 = 0.019 Cây quyết định sử dụng khi nào? Các bài toán với các đặc tính sau thích hợp với học cây quyết định: ẫ ả ở• Các m u mô t được b i các cặp thuộc tính-giá trị • Hàm đích có giá trị rời rạc • Cần có các giả thiết rời rạc • Các dữ liệu luyện có thể có nhiễu • Dữ liệu luyện có thể thiếu giá trị thuộc tính 22 Ví dụ: • Chẩn đoán y tế • Phân tích các nguy cơ về tín dụng • Mô hình hoá việc lập lịch Đo độ chính xác • Làm sao để biết h ≈ f ? • Sử dụng lý thuyết tính toán 1. Thử giả thiết h trên 1 tập các ví dụ mới (tập thử) (sử dụng ốcùng 1 mức độ phân b các mẫu như tập luyện) Learning curve = % chính xác trên tập thử, sử dụng hàm xây dựng trên tập luyện 23 6.3. Học dựa trên mẫu Ý tưởng: lưu tất cả các mẫu luyện Láng giềng gần nhất: • Cho mẫu hỏi x trước tiên định vị mẫu luyện gần q, nhất xn, sau đó đánh giá K láng giềng gần nhất: • Cho xq, quyết định dựa trên k láng giềng gần nhất (nếu hàm đích có giá trị rời rạc) • Lấy trung bình giá trị f của k láng giềng gần nhất )f(x)(xfˆ nq ← 24 (nếu là giá trị thực) k ∑ =← k 1i i q )f(x )(xfˆ 7Phương pháp láng giềng gần • Tổ chức dữ liệu dưới dạng bảng . • Xây dựng ma trận cho phép tính khoảng cách giữa các cặp đối tượng. • Khi có 1 đối tượng mới chưa có kết luận, lấy kết luận của láng giềng gần 25 nhất gán cho nó. Ví d kNN a2 ụ: K = 4 mẫu mới S1 S2 S3 S6 S7 Sx 26 S4 S5 S8 a1(0,0) a1 a2 T S1 -2 0 B S2 -1 5 2 B. S3 0.4 1.8 R S4 1.5 -1 R S5 3 -0.2 B S6 3.2 1.5 R 27 S7 4.5 2 B S8 4.7 -0.2 B Sx 2 0.5 X kNN • Để định nghĩa độ tương tự giữa 2 TH, ta dùng ma trận. • Giả sử các mẫu là các điểm trong không gian n chiều Rn và dùng khoảng cách Euclidean • Cho Xi và Xj là 2 ví dụ. Khoảng cách của chúng là [ ]∑ −= jkikji xxXXd 22 ),( 28 trong đó xik là giá trị của thuộc tính k trên ví dụ Xi. k 8Thuật toán kNN cho các giá trị rời rạc Thuật toán (tham số k) 1. Với mỗi mẫu luyện (X, f(X)), bổ sung mẫu vào tập luyện 2. Khi có mẫu mới Xq, gán lớp: f(Xq) = lớp của đa số các thành viên trong k láng giềng gần nhất của Xq 29 với δ(a,b) = 1 nếu a = b và 0 nếu ngược lại ∑ =∈ = k 1iVv f(Xi)) (v, argmax (Xq)fˆ δ kNN cho các hàm giá trị thực Thuật toán (tham số k) 1. Với mỗi mẫu luyện (X, f(X)), bổ sung mẫu vào tập luyện 2. Khi có mẫu mới Xq, gán lớp: f(Xq) = giá trị trung bình của k láng giềng gần ấ 30 nh t của Xq ∑= kXfXf iq )()(ˆ Đánh trọng số khoảng cách kNN Có thể muốn các láng giềng gần nhất có trọng số cao ∑k xf )(ˆ ωk trong đó à d( ) là kh ả á h iữ à ∑= =← k i i i ii qxf 1 1)( ω 2),( 1 iq i xxd =ϖ ∑ =∈ = 1i i Vv q ))f(X (v, argmax )(Xfˆ δϖ i 31 v xq, xi o ng c c g a xq v xi Chú ý: từ đây có thể thấy lý do dùng tất cả các mẫu luyện thay vì chỉ có k → phương pháp Shepard Khi nào nên dùng láng giềng gần • Các mẫu tương ứng với các điểm trong Rn • Mỗi mẫu có dưới 20 thuộc tính Nhiề ẫ l ệ• u m u uy n Ưu điểm: • Luyện rất nhanh • Học các hàm đích phức tạp • Không mất thông tin 32 Nhược điểm: • Chậm khi truy vấn • Dễ bị ảnh hưởng bởi các thuộc tính không liên quan 9Ảnh hưởng của số chiều Giả thiết các mẫu được mô tả bởi 20 thuộc tính, nhưng chỉ có 2 thuộc tính liên quan đến hàm đích Ảnh hưởng của số chiều: phương pháp kNN thường bị mất phương hướng khi X nhiều chiều Một số giải pháp: • Giãn chiều thứ j bởi trọng số zj, trong đó z1,,zn 33 được chọn để tối thiểu hoá lỗi dự tính • Sử dụng cross-validation để tự động chọn các trọng số z1,,zn 6.4. Mạng nơron nhân tạo nghiên cứu và mô phỏng các tiến trình xử lý song song và phân tán khổng lồ diễn ra trong bộ não con người 34 Các vấn đề: • Tốc độ bộ não nhận dạng hình ảnh • Rất nhiều nơron trong một bộ não • Tốc độ một nơron truyền dữ liệu Ví dụ Lái xe Luyện bộ phận điền khiển xe lái xe chính xác trên nhiều địa hình khác nhau máy tính (thuật toán học) 35 lớp 1 sang trái lớp 2 đi thẳng lớp 3 sang phải Biểu diễn mạng nơron Trái Giữa Phải Tầng ra Tầng ẩn Tầng vào 36 10 Định nghĩa • Là một hệ thống gồm rất nhiều phần tử xử lý đ iả h t độ ơn g n oạ ng song song. • Tính năng: phụ thuộc vào – cấu trúc hệ thống – mức độ liên kết giữa các phần tử á t ì h ử lý bê t á hầ tử 37 – qu r n x n rong c c p n • Có thể học từ số liệu và tổng quát hoá từ các số liệu đó. Khi nào sử dụng mạng nơron? Mạng nơron thích hợp với những bài toán có đặc điểm sau: • Các mẫu luyện được thể hiện bởi nhiều cặp giá trị-thuộc tính (ví dụ, điểm ảnh) • Các mẫu luyện có thể có lỗi • Chấp nhận thời gian huấn luyện dài • Cần đánh giá nhanh hàm mục tiêu được học 38 • Không cần hiểu giả thiết cuối cùng vì NN được coi là hộp đen Perceptron o(x1,...,xn) = 1 nếu w0 + w1x1 + w2x2 ++wnxn >0 -1 trong trường hợp ngược lại hay: o( ) = sgn( )x r xw rr . 39 trong đó sgn(y) = 1 nếu y >0 -1 nếu ngược lại Nhiệm vụ học: tìm các giá trị của w Không gian giả thiết: không gian các vectơ trọng số Khả năng của Perceptron Mỗi perceptron tạo ra 1 mặt phân cách siêu phẳng trên không gian đầu vào n chiều + + + - - - Mặt phân cách (WX = 0) 40 11 Khả năng của Perceptron – có thể học các hàm ¬, ∧, ∨, NAND, NOR – không biểu diễn được các hàm không phân tách được ằ ếb ng đường tuy n tính, vd XOR 1 0 (x1 ∨ x2) ∧ (¬x1 ∨ ¬x2) 0 1 41 ¾ Mọi hàm logic đều có thể biểu diễn bằng 1 mạng perceptron có ít nhất 2 tầng Mạng nơron biểu diễn hàm XOR v1 = x1 ∨ x2 x1 x2 v1 v2 y v = ¬x ∨ ¬ x y = v1 ∧ v2 (x1 ∨ x2) ∧ (¬x1 ∨ ¬x2) 42 2 1 2 tầng vào tầng ẩn tầng ra Học các trọng số mạng • Luật perceptron: dùng khi tập luyện – phân tách được bằng 1 đường tuyến tính – đủ nhỏ • Luật delta: 43 dùng khi tập luyện không phân thể tách tuyến tính Luật huấn luyện Perceptron • Khởi tạo một vector có các trọng số ngẫu nhiên Lặ l i hà t h ỗi ẫ l ệ đế khi hà• p ạ m percep ron c o m m u uy n n m perceptron phân loại đúng tất cả các mẫu luyện: • Các trọng số được sửa đổi tại mỗi bước dựa vào luật huấn luyện perceptron: trong đó iii www Δ+⎯⎯← xotww )( −+Δ⎯⎯←Δ η 44 với – t = c( ) là hàm đích – o là đầu ra perceptron – η = tốc độ học, là hằng số nhỏ xr iii 12 Ví dụ... Biểu diễn g(x1,x2) = AND(x1,x2) x1 W1 x1 x2 g 0 0 0 {0; 1} x2 x0=1 W0 W2 Σ 0 1 0 1 0 0 1 1 1 w0 + 1.w1 + 1.w2 >0 45 o(x) = 1 nếu > 0 0 nếu ngược lại xw rr. w0 + 1.w1 + 0.w2 < 0 w0 + 0.w1 + 1.w2 < 0 w0 + 0.w1 + 0.w2 < 0 Öw0 = -0.8; w1= 0.5; w2 = 0.5 Ví dụ... ầ iii xotww )( −+Δ⎯⎯←Δ ηiii www Δ+⎯⎯← ∑ = = 2 0 *. i ii xwxw rr Khởi tạo các giá trị đ u: Δw0 = 0, Δw1 = 0, Δw2 = 0 w0 = -1.5, w1 = -0.5, w2 = 0.5, η = 0.1 x0 x1 x2 t ∑ o Δw0 Δw1 Δw2 1 0 0 0 -1.5 0 0 0 0 Δw0 = Δw0 + η*(t-o)*x0 = 0 + 0.1*(0-0)*1 = 0∑ = x0.w0+x1.w1+x2.w2 = 1.w0+0.w1+0.w2 = w0 = -1.5 w0 = w0 + Δw0 = -1.5 + 0 = -1.5, w1 = -0.5, w2 = 0.5 46 1 0 1 0 -1 0 0 0 0 1 1 0 0 -2 0 0 0 0 1 1 1 1 -1.5 0 0.1 0.1 0.1 Δw0 = Δw0 + η*(t-o)*x0 = 0 + 0.1*(1-0)*1 = 0.1 w0 = w0 + Δw0 = -1.5 + 0.1 = -1.4, w1 = -0.4, w2 = 0.6 Ví dụ... iii xotww )( −+Δ⎯⎯←Δ ηiii www Δ+⎯⎯← ∑ = = 2 0 *. i ii xwxw rr Δw0 = 0.1, Δw1 = 0.1, Δw2 = 0.1 w0 = -1.4, w1 = -0.4, w2 = 0.6, η = 0.1 w0 = w0 + Δw0 = -1.4 + 0.1 = -1.3, w1 = -0.3, w2 = 0.7 ∑ = x0.w0+x1.w1+x2.w2 = 1.w0+0.w1+0.w2 = w0 = -1.4 Δw0 = Δw0 + η*(t-o)*x0 = 0.1 + 0.1*(0-0)*1 = 0.1 47 x0 x1 x2 t ∑ o Δw0 Δw1 Δw2 1 0 0 0 -1.4 0 0.1 0.1 0.1 1 0 1 0 -0.6 0 0.1 0.1 0.1 1 1 0 0 1 1 1 1 Ứng dụng của mạng nơron - Nhận dạng mặt 48 13 Ứng dụng của mạng nơron - Nhận dạng mặt • Có nhiều hàm đích có thể học trong việc nhận dạng ảnh: – xác định người – hướng quay (trái, phải, thẳng, ...) – giới tính 49 – có đeo kính hay không Ứng dụng của mạng nơron - Nhận dạng mặt • Nhiệm vụ học: phân loại các hình ảnh camera về mặt người với nhiều góc độ khác nhau • CSDL hình ảnh • Các hình ảnh với 624 grayscale: 20 người, mỗi người khoảng 32 ảnh • Nhiều cách biểu cảm (vui, buồn, giận, bình thường) • Các hướng khác nhau (trái, phải, thẳng, hướng lên) • Độ phân giải 120x128 50 • Học hướng quay của mặt người: – không cần các lựa chọn tối ưu, phương pháp này cho kết quả tốt – sau khi luyện trên 260 hình ảnh, việc phân loại đạt độ chính xác trên tập thử là 90% Các lựa chọn 1 Mã hoá đầu vào: hình ảnh hay các đặc tính. 2. Mã hoá đầu ra: số lượng đầu ra, các hàm đích cho đầu ra 3. Cấu trúc mạng: số lượng nút mạng và liên kết giữa chúng 4. Các tham số thuật toán học ố 51 – T c độ học – giá trị momentum Mã hoá đầu vào • Thiết kế các lựa chọn • Tiền xử lý hình ảnh để rút ra các hướng, các vùng có ậ độ iố h h ặ á đặ í h hì h ả h bộm t g ng n au, o c c c c t n n n cục khác • Khó khăn: số cạnh có thể thay đổi, trong khi NN có số lượng cố định các đầu vào • Các hình đã mã hoá là 1 tập cố định các giá trị mật độ 30x32 điểm ảnh (tóm tắt về độ phân giải của ảnh ban đầu) từ 0 đến 255 52 , 14 Mã hoá đầu ra • Mỗi đầu ra: 4 giá trị xác định hướng mà người nhìn (trái, phải, thẳng, hướng lên) • Mỗi đơn vị: phân loại sử dụng 1 đầu ra, gán 0.2, 0.4, 0.6 và 0.8 cho 4 giá trị • Chọn 1 trong n đầu ra mã hoá: ấ hiề ứ độ t d để biể diễ hà 53 – cung c p n u m c ự o u n m đích (n lần số trọng số ở tầng ra) – độ khác nhau giữa giá trị cao nhất và nhì dùng để đo độ tin cậy Cấu trúc mạng 54 mạng 960 x 3 x 4