Bài giảng Trí Tuệ Nhân Tạo - Chương 8: Máy lọc - Nguyễn Văn Hòa

Nội dung text: Bài giảng Trí Tuệ Nhân Tạo - Chương 8: Máy lọc - Nguyễn Văn Hòa

1. Ch ươ ng 8: Máy h c 1
2. Ni d ng
   Các khái ni ệm v ề máy h ọc
   Các k ỹ thu ật h ọc c ủa máy  Cây quy ết đị nh  Mạng neuron  Gi ải thu ật di truy ền (Genetic) 2
3. Hc Máy (Machine Learning)
   Học (learning) là b ất c ứ s ự thay đổ i nào trong m ột h ệ th ống cho phép nó ti ến hành t ốt h ơn trong l ần th ứ hai khi l ặp l ại cùng m ột nhi ệm v ụ ho ặc v ới nhi ệm v ụ khác t ừ cùng m ột qu ần th ể đó. (Herbert Simon)
   Học liên quan đế n v ấn đề khái quát hóa t ừ kinh nghi ệm (d ữ li ệu rèn luy ện) => bài toán quy n ạp (induction)
   Vì d ữ li ệu rèn luy ện th ườ ng h ạn ch ế, nên th ườ ng khái quát hóa theo m ột s ố khía c ạnh nào đó (heuristic) => tính thiên lệch quy n ạp (inductive bias)
   Có ba ti ếp c ận h ọc:  Các ph ươ ng pháp h ọc d ựa trên ký hi ệu (symbol -based): ID3  Ti ếp c ận k ết n ối: Các m ạng neuron sinh h ọc  Ti ếp c ận di truy ền hay ti ến hóa: gi ải thu ật genetic 3
4. Cây quy t đ nh (ID3)
   Là m ột gi ải thu ật h ọc đơ n gi ản nh ưng thành công
   Cây quy ết đị nh (Q Đ) là m ột cách bi ểu di ễn cho phép chúng ta xác đị nh phân lo ại c ủa m ột đố i t ượ ng b ằng cách ki ểm tra giá tr ị c ủa m ột s ố thu ộc tính.
   Gi ải thu ật có:  Đầ u vào: Một đố i t ượ ng hay m ột t ập h ợp các thu ộc tính mô t ả m ột tình hu ống  Đầ u ra: th ườ ng là quy ết đị nh yes/no, ho ặc các phân lo ại.
   Trong cây quy ết đị nh:  Mỗi nút trong bi ểu di ễn m ột s ự ki ểm tra trên m ột thu ộc tính nào đó, mỗi giá tr ị có th ể c ủa nó t ươ ng đươ ng v ới m ột nhánh c ủa cây  Các nút lá th ể hi ện s ự phân lo ại.
   Kích c ỡ c ủa cây Q Đ tùy thu ộc vào th ứ t ự c ủa các ki ểm tra trên các thu ộc tính. 4
5. Ví d Cây Q Đ: Ch ơi Tennis
   Mục đích: h ọc để xem có ch ơi Tennis không?
   Cây quy ết đị nh: Quang c ảnh nắng Âm u mưa Độ ẩm Yes Gió cao Trung bình mạnh nh ẹ No Yes No Yes 5
6. Quy n p cây Q Đ t các ví d
   Ví d ụ (hay d ữ li ệu rèn luy ện cho h ệ th ống) g ồm: Giá tr ị c ủa các thu ộc tính + Phân lo ại c ủa ví d ụ Ngày Quang c ảnh Nhi ệt độ Độ ẩm Gió Ch ơi Tennis D1 Nắng Nóng Cao nh ẹ Không D2 Nắng Nóng Cao Mạnh Không D3 Âm u Nóng Cao Nh ẹ Có D4 Mưa ấm áp Cao nh ẹ Có D5 Mưa Mát TB nh ẹ Có D6 Mưa Mát TB Mạnh Không D7 Âm u Mát TB Mạnh Có D8 Nắng ấm áp Cao nh ẹ Không D9 Nắng Mát TB nh ẹ Có D10 Mưa ấm áp TB nh ẹ Có D11 Nắng ấm áp TB Mạnh Có D12 Âm u ấm áp Cao Mạnh Có D13 Âm u Nóng TB nh ẹ Có D14 Mưa ấm áp Cao Mạnh không 6
7. Làm sao đ h c đư c cây Q Đ
   Ti ếp c ận đơ n gi ản  Học m ột cây mà có m ột lá cho m ỗi ví d ụ.  Học thu ộc lòng m ột cách hoàn toàn các ví d ụ.  Có th ể s ẽ không th ực hi ện t ốt trong các tr ườ ng h ợp khác.
   Ti ếp c ận t ốt h ơn:  Học m ột cây nh ỏ nh ưng chính xác phù h ợp v ới các ví dụ  Occam’s razor – cái đơ n gi ản th ườ ng là cái t ốt nh ất! Gi ả thuy ết có kh ả n ăng nh ất là gi ả thuy ết đơ n gi ản nh ất th ống nh ất v ới t ất c ả các quan sát. 7
8. Xây d ng cây Q Đ: Trên - xu ng Vòng l ặp chính: 1. A < - thu ộc tính quy ết đị nh t ốt nh ất cho nút k ế 2. Gán A là thu ộc tính quy ết đị nh cho nút 3. Với m ỗi giá tr ị c ủa A, t ạo m ột nút con m ới cho nút 4. Sắp x ếp các ví d ụ vào các nút lá 5. If các ví d ụ đã đượ c phân lo ại đúng, d ừng ctr; Else l ặp lại trên m ỗi nút lá m ới Để phân lo ại m ột tr ườ ng h ợp, có khi cây Q Đ không cần s ử d ụng t ất c ả các thu ộc tính đã cho, m ặc dù nó vẩn phân lo ại đúng t ất c ả các ví d ụ. 8
9. Các kh n ăng có th c a nút con
   Các ví d ụ có c ả âm và d ươ ng:  Tách m ột l ần n ữa
   Tất c ả các ví d ụ còn l ại đề u âm ho ặc đề u d ươ ng  tr ả v ề cây quy ết đị nh
   Không còn ví d ụ nào  tr ả v ề m ặc nhiên
   Không còn thu ộc tính nào (nhi ễu)  Quy ết đị nh d ựa trên m ột lu ật nào đó (lu ật đa s ố) 9
10. +: D3, D4, D5, D7, D9, D10, D11, D12, D13 -: D1, D2, D6, D8, D14 Quang c ảnh? Nắng Âm u Mưa +: D9, D11 +: D3, D7, D12, D13 +: D4, D5, D10 -: D1, D2, D8 -: -: D6, D14 +: D3, D4, D5, D7, D9, D10, D11, D12, D13 -: D1, D2, D6, D8, D14 Độ ẩm? Cao Trung b ình +: D3, D4, D12 +: D5, D9, D10, D11, D13 -: D1, D2, D8, D14 -: D6 10
11. +: D3, D4, D5, D7, D9, D10, D11, D12, D13 -: D1, D2, D6, D8, D14 Quang c ảnh? Nắng Âm u Mưa +: D9, D11 +: D3, D7, D12, D13 +: D4, D5, D10 -: D1, D2, D8 -: -: D6, D14 Độ ẩm? Yes Gi ó? Mạnh Cao TB Nh ẹ +: +: D9, D11 +: +: D4, D5, D10 -: D1, D2, D8 -: -: D6, D14 -: No Yes No Yes 11
12. ID3 xây d ng cây Q Đ theo gi i thu t sau: 12
13. Đánh giá hi u su t
    Chúng ta mu ốn có m ột cây Q Đ có th ể phân lo ại đúng m ột ví d ụ mà nó ch ưa t ừng th ấy qua.
    Vi ệc h ọc s ử d ụng m ột “t ập rèn luy ện” (traning set), và
    Vi ệc đánh giá hi ệu su ất s ử d ụng m ột “t ập ki ểm tra” (test set): 1. Thu th ập m ột t ập h ợp l ớn các ví d ụ 2. Chia thành t ập rèn luy ện và t ập ki ểm tra 3. Sử d ụng gi ải thu ật và t ập rèn luy ện để xây d ựng gi ả thuy ết h (cây QĐ) 4. Đo ph ần tr ăm t ập ki ểm tra đượ c phân lo ại đúng b ởi h 5. Lặp l ại b ướ c 1 đế n 4 cho các kích c ỡ t ập ki ểm tra khác nhau đượ c ch ọn m ột cách nh ẫu nhiên. 13
14. S d ng lý thuy t thông tin
    Chúng ta mu ốn ch ọn các thu ộc tính có th ể gi ảm thi ểu chi ều sâu c ủa cây Q Đ.
    Thu ộc tính t ốt nh ất: chia các ví d ụ vào các t ập h ợp ch ứa toàn ví d ụ âm ho ặc ví d ụ d ươ ng.
    Chúng ta c ần m ột phép đo để xác đị nh thu ộc tính nào cho kh ả n ăng chia t ốt h ơn. Thu ộc tính nào t ốt h ơn? [29+, 36 -] A1 = ? [29+, 36 -] A2 = ? [21+, 6-] [8+, 30-] [18+, 34-] [11+,2-] 14
15. Entropy
    Entropy(S) = số l ượ ng mong đợ i các bit c ần thi ết để mã hóa m ột lớp (+ hay – ) c ủa m ột thành viên rút ra m ột cách ng ẫu nhiên t ừ S (trong tr ườ ng h ợp t ối ưu, mã có độ dài ng ắn nh ất).
    Theo lý thuy ết thông tin: mã có độ dài t ối ưu là mã gán –log 2p bits cho thông điệp có xác su ất là p. • S là m ột t ập rèn luy ện •p⊕ là ph ần các ví d ụ d ươ ng trong t ập S •pΘ là ph ần các ví d ụ âm trong t ập S • Entropy đo độ pha tr ộn c ủa t ập S: = − − Entropy (S) p⊕ log 2 p⊕ pΘ log 2 pΘ c = − Entropy (S) ∑ pi log 2 pi i=1 15
16. Lư ng thông tin thu đư c Information Gain
    Gain(S, A) = L ượ ng gi ảm entropy mong đợ i qua vi ệc chia các ví d ụ theo thu ộc tính A = − | Sv | Gain (S, A) Entropy (S) ∑ Entropy (Sv ) v∈Values ( A) | S | [29+, 36-] A1 = ? [29+, 36-] A2 = ? [21+, 6-] [8+, 30-] [18+, 34-] [11+,2-] 16
17. Ch n thu c tính k ti p S: [9+,5 – ] S: [9+,5 – ] E = 0.940 E = 0.940 Độ ẩm Gi ó Cao TB Nh ẹ Mạnh [3+,4 – ] [6+,1 – ] [6+,2 – ] [3+,3 – ] E = 0.985 E = 0.592 E = 0.811 E = 1.0 Gain(S, Độ ẩm) Gain(S, Gió) = .940 – (7/14).985 – (7/14).592 = .940 – (8/14).811 – (6/14)1.0 = .151 = .048 17
18. Tìm ki m KG gi thuy t trong ID3 (1)
    KG gi ả thuy ết đầ y đủ =>gi ả thuy ết ch ắc ch ắn thu ộc KG này
    Đầ u ra là m ột gi ả thuy ết (cây Q Đ) =>Cây nào? Không th ể ch ọn cây v ới 20 câu h ỏi
    Không quay lui => c ực ti ểu đị a ph ươ ng
    Lựa ch ọn tìm ki ếm d ựa trên th ống kê => ch ịu đượ c d ữ li ệu nhi ễu
    Thiên l ệch quy n ạp: thích cây ng ắn h ơn. 18
19. Chuy n cây v thành các lu t Quang c ảnh nắng Âm u mưa Độ ẩm Yes Gió cao Trung bình mạnh nh ẹ No Yes No Yes If (Quang -cảnh =n ắng) ∧ (Độ ẩm = Cao) Then Ch ơi-Tennis = No If (Quang-cảnh =n ắng) ∧ (Độ ẩm = TB) Then Ch ơi-Tennis = Yes If (Quang-cảnh =Âm u) Then Ch ơi-Tennis = Yes 19
20. Khi nào nên s d ng cây Q Đ
    Các ví d ụ đượ c mô t ả b ằng các c ặp “thu ộc tính – giá tr ị”, vd: Gió - mạnh, Gió - nh ẹ
    Kết qu ả phân lo ại là các giá tr ị r ời r ạc, vd: Yes, No
    Dữ li ệu rèn luy ện có th ể ch ứa l ỗi (b ị nhi ễu)
    Dữ li ệu rèn luy ện có th ể thi ếu giá tr ị thu ộc tính Ví d ụ:
    Phân lo ại b ệnh nhân theo các b ệnh c ủa h ọ
    Phân lo ại h ỏng hóc thi ết b ị theo nguyên nhân
    Phân lo ại ng ườ i vay ti ền theo kh ả n ăng chi tr ả 20
21. Ví d ụ: ướ c l ượ ng độ an toàn c ủa m ột tài kho ản tín d ụng Table 13.1:Table Data credit from history loan of applications. 21
22. Figure 13.13: Mt cây Q Đ cho bài toán đánh giá đ an toàn c a tín d ng. 22
23. Figure 13.14: Mt cây Q Đ đơ n gi n h ơn. 23
24. Figure 13.15: Mt cây Q Đ đang xây d ng. Figure 13.16: Mt cây Q Đ khác đang xây d ng. 24
25. Neural Networks
    Ng ượ c l ại v ới các mô hình d ựa trên ký hi ệu: Không chú tr ọng vi ệc s ử d ụng các ký hi ệu m ột cách t ườ ng minh để gi ải quy ết v ấn đề .
    Ý t ưở ng d ựa trên các h ệ não: Xem trí tu ệ là s ự phát sinh t ừ các h ệ th ống g ồm nh ững thành ph ần đơ n gi ản (neuron), t ươ ng tác v ới nhau thông qua m ột quá trình h ọc ho ặc thích nghi mà ở đó các k ết n ối gi ữa các thành ph ần đượ c điều ch ỉnh.
    Gặt hái r ất nhi ều thành công trong nh ững n ăm g ần đây.
    Từ đồ ng ngh ĩa:  Tính toán neural (neural computing)  Các m ạng neural (neural networks)  Các h ệ k ết n ối (connectionist system)  Các h ệ x ử lý phân tán song song (parallel distributed processing) 25
26. Neuron nhân t o
    Thành ph ần c ơ b ản c ủa m ạng neuron là m ột neuron nhân tạo.
    Các thành ph ần c ủa m ột neuron nhân t ạo:  Các tín hi ệu vào xi {0,1} {1,-1} real  Các tr ọng s ố wi real  Một m ức kích ho ạt ∑i wixi →  Một hàm ng ưỡ ng f : ∑i wixi tín hi ệu ra 26
27. Neural Networks
    Các thu ộc tính t ổng quát c ủa m ột m ạng là:  Hình thái m ạng: mẫu k ết n ối gi ữa (các t ầng c ủa) các neuron.  Gi ải thu ật h ọc: cách điều ch ỉnh các tr ọng s ố trong quá trình x ử lý t ập d ữ li ệu rèn luy ện  Cơ ch ế mã hóa: sự thông d ịch c ủa các tín hi ệu vào và w11 tín hi ệu ra I 1 H1 w12 w11 I 1 H O1 1 O1 I2 w12 H2 I2 I3 wi j 27
28. Ví d : Neuron McCulloch-Pitts Các neurron dùng để tính các hàm logic and và or 28
29. Hc Perceptron
    Mạng neuron đơ n t ầng f(net)
    Các giá tr ị vào 1 ho ặc -1
    Các tr ọng s ố ki ểu th ực net = ∑ w x t i i i
    Mức kích ho ạt ∑i wixi
    Hàm ng ưỡ ng gi ới h ạn c ứng f : 1 if ∑i wixi >= t -1 if ∑i wixi < t
    Điều ch ỉnh tr ọng s ố: ∆wi = c(d-f( ∑i wixi)) x i c: h ằng s ố ch ỉ t ốc độ h ọc d: đầ u ra mong mu ốn Nếu k ết qu ả th ực và k ết qu ả mong mu ốn gi ống nhau, không làm gì Nếu k ết qu ả th ực là -1 và k ết qu ả mong mu ốn là 1, t ăng tr ọng s ố c ủa đườ ng th ứ i lên 2cx i Nếu k ết qu ả th ực là 1 và k ết qu ả mong mu ốn là -1, gi ảm tr ọng s ố c ủa đườ ng th ứ i xu ống 2cx i 29
30. Phân lo i c a các h th ng H c
    Học có s ự h ướ ng d ẫn (Supervised learning)  Cho h ệ th ống m ột t ập các ví d ụ và m ột câu tr ả l ời cho mỗi ví d ụ.  Rèn luy ện h ệ th ống cho đế n khi nó có th ể đư a ra câu tr ả l ời đúng cho các ví d ụ này.
    Học không có s ự h ướ ng d ẫn (Unsupervised learning)  Cho h ệ th ống m ột t ập h ợp các ví d ụ và cho nó t ự khám phá các m ẫu thích h ợp trong các ví d ụ. Mạng neuron s ử d ụng m ột hình th ức h ọc có sự h ướ ng d ẫn 30
31. S d ng perceptron trong bài toán phân lo i Fig 14-4: M ột h ệ th ống phân lo ại đầ y đủ 31
32. Ví d Perceptron
    Cho tr ướ c: một t ập các d ữ li ệu vào
    Yêu c ầu: rèn luy ện perceptron sao cho nó phân lo ại các đầ u vào m ột cách đúng đắ n 32
33. Ví d Perceptron: gi i pháp
    2 tín hi ệu vào x1 x2
    Một tín hi ệu vào th ứ ba đượ c s ử d ụng nh ư m ột thiên v ị và có giá tr ị c ố đị nh b ằng 1, cho phép d ịch chuy ển đườ ng phân cách
    Mức kích ho ạt: w1x1 + w 2x2 + w 3
    Hàm ng ưỡ ng: hàm d ấu, >0 = +1, <0 = -1 đây là ng ưỡ ng gi ới h ạn c ứng tuy ến tính hai c ực
    Các tr ọng s ố: đượ c kh ởi t ạo ng ẫu nhiên, cập nh ật 10 l ần, v ới t ốc độ h ọc là 0.2
    Kết qu ả: -1.3x 1 + -1.1x 2 + 10.9 = 0 33
34. Tính tách r i tuy n tính (linearly seperatable)
    Trong m ột không gian n chi ều, m ột s ự phân lo ại mang tính tuy ến tính n ếu các l ớp c ủa nó có th ể đượ c tách r ời b ởi m ột m ặt n-1 chi ều.
    Perceptron không th ể gi ải quy ết các bài toán phân lo ại không tách r ời tuy ến tính.  Ví d ụ: bài toán X-OR 34
35. Lu t Delta Tổng quát hóa perceptron b ằng cách: 1. Thay th ế hàm ng ưỡ ng gi ới h ạn c ứng b ằng các hàm kích ho ạt khác có kh ả n ăng l ấy vi phân Ví d ụ: m ột hàm kích ho ạt sigmoidal -λ*net f(net) = 1/(1 + e ) với net = ∑i wixi f ’(net) = f(net) * (1- f(net)) 2. Sử d ụng lu ật delta để điều ch ỉnh tr ọng s ố trên đầ u vào th ứ k c ủa nút th ứ i f’: đạ o hàm b ậc nh ất c: t ốc độ h ọc ∆w = c(d i –Oi) f’(net i)x k di: đầ u ra mong mu ốn = c(d i –Oi) O i (1 – Oi) x k Oi: đầ u ra th ật s ự 35
36. Lan truy n ng ư c (backpropagation)
    Tại các nút c ủa các m ạng đa t ầng, l ỗi mà m ột nút ph ải ch ịu trách nhi ệm c ũng ph ải đượ c chia ph ần cho các nút ở t ầng ẩn và các tr ọng s ố ph ải đượ c điều ch ỉnh m ột cách phù h ợp.
    Gi ải thu ật lan truy ền ng ượ c bắt đầ u t ại t ầng ra và truy ền các lỗi ng ượ c v ề xuyên qua các t ầng ẩn. Lu ật delta t ổng quát để điều ch ỉnh tr ọng s ố c ủa đầ u vào th ứ k của nút th ứ i: ∆wk = c(d i –Oi) O i (1 – Oi) x k cho nút ở t ầng ra ∆wk = c ∑j (delta j wij ) O i (1 – Oi) x k cho nút ở t ầng ẩn với delta j = (d j – Oj) O j (1 – Oj) j ch ạy trên các nút c ủa t ầng k ế ti ếp mà t ại đó nút i truy ền các đầ u ra c ủa nó. 36
37. Ví d m ng Neuron: NETtalk
    Vấn đề : phát âm v ăn b ản ti ếng Anh đúng
    Đầ u vào: một chu ỗi
    Đầ u ra: âm v ị và tr ọng âm kèm theo cho m ỗi ký t ự
    Gi ải pháp:
    Kết qu ả th ực nghi ệm: đúng 60% sau khi rèn luy ện v ới 500 ví d ụ (100 l ượ t) càng nhi ều ví d ụ rèn luy ện => k ết qu ả càng t ốt 38
38. Figure 10.12: A backpropagation net to solve the exclusive-or problem. The W ij are the weights and H is the hidden node. Sử d ụng 4 m ẫu ví d ụ để luy ện t ập: (0,0) -> 0; (1,0) ->1; (0,1) -> 1; (1,1) ->0 Sau 1400 l ượ t: WH1 = -7.0 WHB = 2.6 WO1 = -5.0 WH2 = -7.0 WOB = 7.0 WO2 = -4.0 WHO = -11.0 39
39. Các v n đ liên quan khi s d ng Neural Networks
    Các m ạng đa t ầng là đầ y đủ v ề m ặt tính toán, tuy nhiên:  Làm sao để ch ọn s ố nút ẩn và s ố t ầng ẩn  Khi nào s ử d ụng các nút thiên l ệch  Cách ch ọn m ột t ập rèn luy ện  Điều ch ỉnh các tr ọng s ố hay t ốc độ h ọc nên n.t.n?  40
40. Gi i thu t Genetic
    Nắm b ắt ý t ưở ng t ừ thuy ết ti ến hóa
    Học đượ c xem nh ư là s ự c ạnh tranh gi ữa các qu ần th ể các gi ải pháp kh ả d ĩ đang ti ến hóa c ủa bài toán
    Thành ph ần:  Qu ần th ể các gi ải pháp kh ả d ĩ Kh ởi t ạo qu ần th ể  Hàm đánh giá Y ĐK th ỏa  Các phép toán t ạo con m ới:
    giao nhau (crossover) N
    Độ t bi ến (mutation) •Gọi hàm đánh giá
    Gi ải thu ật: •Ch ọn các thành viên t ốt  Điều ki ện k ết thúc: #vòngl ặp, •Tạo con m ới Trung bình ‘ độ t ốt’ c ủa qu ần th ể •Thay th ế thành viên kém bằng các con m ới Ch ọn gi ải pháp t ừ qu ần th ể 41