Bài giảng Trí tuệ nhân tạo - Bài 4: Một số ví dụ về máy học - Văn Thế Thành

2/19/2014 1 1 CHƯƠNG 4: MỘT SỐ VÍ DỤ VỀ MÁY HỌC NHẬP MÔN TRÍ TUỆ NHÂN TẠO 2 1. GIỚI THIỆU Một số phương pháp máy học để tiếp thu tri thức hay tạo ra tri thức
Học vẹt
Học cách đề xuất
Học bằng cách thu thập các trường hợp
Học bằng cách xây dựng cây định danh
Học không giám giám sát và bài tóm gom nhóm dữ liệu
Học giám sát và bài toán phân lớp dữ liệu 2/19/2014 2 3 1. GIỚI THIỆU (tt) Học vẹt
Hệ tiếp nhận các khẳng định của các quyết định đúng. Khi hệ tạo ra một quyết định không đúng, hệ sẽ đưa ra các luật hay quan hệ đúng mà hệ đã sử dụng. Hình thức học vẹt nhằm cho phép chuyên gia cung cấp tri thức theo kiểu tương tác. Học bằng cách chỉ dẫn
Thay vì đưa ra một luật cụ thể cần áp dụng vào tình huống cho trước, hệ thống sẽ được cung cấp bằng các chỉ dẫn tổng quát.
Ví dụ: "gas hầu như bị thoát ra từ van thay vì thoát ra từ ống dẫn". Hệ thống phải tự mình đề ra cách biến đổi từ trừu tượng đến các luật khả dụng. 4 1. GIỚI THIỆU (tt) Học bằng qui nạp
Hệ thống được cung cấp một tập các ví dụ và kết luận được rút ra từ từng ví dụ. Hệ liên tục lọc các luật và quan hệ nhằm xử lý từng ví dụ mới. Học bằng tương tự
Hệ thống được cung cấp đáp ứng đúng cho các tác vụ tương tự nhưng không giống nhau. Hệ thống cần làm thích ứng đáp ứng trước đó nhằm tạo ra một luật mới có khả năng áp dụng cho tình huống mới. 2/19/2014 3 5 1. GIỚI THIỆU (tt) Học dựa trên giải thích
Hệ thống phân tích tập các lời giải ví dụ ( và kết quả) nhằm ấn định khả năng đúng hoặc sai và tạo ra các giải thích dùng để hướng dẫn cách giải bài toán trong tương lai. Học dựa trên tình huống
Bấy kỳ tính huống nào được hệ thống lập luận đều được lưu trữ cùng với kết quả cho dù đúng hay sai. Khi gằp tình hướng mới, hệ thống sẽ làm thích nghi hành vi đã lưu trữ với tình huống mới. Khám phá hay học không giám sát
Thay vì có mục tiêu tường minh, hệ khám phá liên tục tìm kiếm các mẫu và quan hệ trong dữ liệu nhập. Các ví dụ về học không giám sát bao gồm gom cụm dữ liệu, học để nhận dạng các đặc tính cơ bản như cạnh từ các điểm ảnh. 6 2. Một số ví dụ: Học qua logic: Bongard (1970) là người đầu tiên ứng dụng các toán tử logic để học và nhận dạng các đối tượng hình ảnh. Ý tưởng: Tìm quan hệ đơn giản nhất trong số các quan hệ có thể sử dụng để học và nhận dạng các hình ảnh. 2/19/2014 4 7 2. Một số ví dụ (tt) Lôùp A Lôùp B Chúng ta có thể quan sát thấy các hình vẽ thuộc lớp A có 3 vòng trắng luôn luôn nằm trên một đường thẳng. 8 2. Một số ví dụ (tt) Vấn đề đặt ra: -Tìm quan hệ đơn giản nhất có thể phân biệt được các hình ảnh. Bongard đã dùng bảng logic “mô tả – quan hệ” để dẫn xuất ra các mệnh đề logic: φ có thể dùng để phân biệt 2 lớp E và E’ nếu φ(E) và φ(E’) đối ngẫu nhau. )...21(φ nϕϕϕ ∧∧∧∨= 2/19/2014 5 9 2. Một số ví dụ (tt) P1 P2 P3 P4 P5 1 2 3 4 5 6 7 8 9 10 10 2. Một số ví dụ (tt) Các đối tượng trong mẫu: 54321 54321 54321 54321 54321 54321 54321 54321 54321 54321 54321 0001110 010009 010018 000117 010116 010105 100104 100103 010012 011111 PPPPP PPPPP PPPPP PPPPP PPPPP PPPPP PPPPP PPPPP PPPPP PPPPP PPPPP ⇒ 2/19/2014 6 11 2. Một số ví dụ (tt) Sau khi tính tổng và rút gọn lại được: )P.PP.P.(PP.P 3232121 ++      ϕ∈ 321 321 21 P.P.P P.P.P P.P )A(x Khoâng coù thì phaûi coù hình (3,4,5) Coù thì phaûi coù hình vaø hình (1) Coù thì khoâng coù hình vaø hình (1) 12 3. HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH Cây định danh: Là một dạng của cây quyết định, trong đó mỗi tập các kết luận có thể xảy ra được thiết lập một cách ngầm định bởi một danh sách các mẫu mà chúng được phân vào một lớp đã biết. Baûng döõ lieäu Caây ñònh danh Luaät Thöû Xaây döïng 2/19/2014 7 13 3. HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH (tt) Ví dụ có bảng dữ liệu quan sát Tên Tóc Ch.Cao Cân Nặng Dùng kem? Kết quả Sarah Vàng T.Bình Nhẹ Không Cháy Dana Vàng Cao T.Bình Có Không Alex Nâu Thấp T.Bình Có Không Annie Vàng Thấp T.Bình Không Cháy Emilie Đỏ T.Bình Nặng Không Cháy Peter Nâu Cao Nặng Không Không John Nâu T.Bình Nặng Không Không Kartie Vàng Thấp Nhẹ Có Không 14 3. HỌC BẰNG CÁCH XÂY DỰNG CÂY ĐỊNH DANH (tt) •Thuộc tính mục tiêu: là thuộc tính quan tâm (tính chất cháy nắng hay không cháy nắng) . R = {"cháy nắng", "bình thường"}. •Thuộc tính dẫn xuất: Chúng ta quan sát hiện tượng cháy nắng dựa trên 4 thuộc tính sau : chiều cao (cao, trung bình, thấp), màu tóc (vàng, nâu, đỏ), cân nặng (nhẹ, TB, nặng), dùng kem (có, không) là thuộc tính dẫn xuất P là tất cả những người được liệt kê trong bảng dưới (8 người) 2/19/2014 8 15 3.1.Đâm chồi Vàng Nâu Đỏ 16 3.1. Đâm chồi (tt) 2/19/2014 9 17 3.2. Phương án chọn thuộc tính phân hoạch Vấn đề mà chúng ta gặp phải cũng tương tự như bài toán tìm kiếm : "Đứng trước một ngã rẽ, ta cần phải đi vào hướng nào?".  Hai phương pháp đánh giá dưới đây giúp ta chọn được thuộc tính phân hoạch tại mỗi bước xây dựng cây định danh. 18 3.2.1. Thuật toán Quinlan (1) •Quinlan quyết định thuộc tính phân hoạch bằng cách xây dựng các vector đặc trưng cho mỗi giá trị của từng thuộc tính dẫn xuất và thuộc tính mục tiêu. •Cách tính vectơ đặc trưng: Với mỗi thuộc tính dẫn xuất A còn có thể sử dụng để phân hoạch, tính : VA(j) = ( T(j , r1), T(j , r2) , , T(j , rn) ) *T(j, ri) = (tổng số phần tử trong phân hoạch có giá trị thuộc tính dẫn xuất A là j và có giá trị thuộc tính mục tiêu là ri ) / ( tổng số phần tử trong phân hoạch có giá trị thuộc tính dẫn xuất A là j ) * r1, r2, , rn là các giá trị của thuộc tính mục tiêu 2/19/2014 10 19 3.2.1. Thuật toán Quinlan (2)
Vector đơn vị là vector có duy nhất một thành phần có giá trị 1 và những thành phần khác có giá trị 0.
Thuộc tính được chọn để phân hoạch là thuộc tính có nhiều vector đơn vị nhất. 20 3.2.1. Thuật toán Quinlan vaøng toùc coùsaùt quan soá Toång vaøng toùc coù naéng chaùysaùt quan soá Toång vaøng toùc coùsaùt quan soá Toång vaøng toùc coù naéng chaùy gsaùt khoân quan soá Toång Không cháy nắng = Cháy nắng = 2/19/2014 11 21 VTóc (vàng) = (T(vàng,cháy nắng),T(vàng, không cháy nắng)) Số người tóc vàng là : 4 Số người tóc vàng và cháy nắng là : 2 Số người tóc vàng và không cháy nắng là : 2 Do đó VTóc(vàng) = (2/4 , 2/4) = (0.5, 0.5) Tương tự VTóc(nâu) = (0/3, 3/3) = (0,1) (vector đơn vị) VTóc(đỏ) = (1/1, 0/1) = (1,0) (vector đơn vị) Tổng số vector đơn vị của thuộc tính tóc là 2 3.2.1. Thuật toán Quinlan(tt) 22 3.2.1. Thuật toán Quinlan (tt) Các thuộc tính khác được tính tương tự, kết quả như sau : VC.Cao(Cao) = (0/2,2/2) = (0,1) VC.Cao(T.B) = (2/3,1/3) VC.Cao(Thấp) = (1/3,2/3) VC.Nặng (Nhẹ) = (1/2,1/2) VC.Nặng (T.B) = (1/3,2/3) VC.Nặng (Nặng) = (1/3,2/3) VKem (Có) = (3/3,0/3) = (1,0) VKem (Không) = (3/5,2/5) Như vậy thuộc tính màu tóc có số vector đơn vị nhiều nhất nên sẽ được chọn để phân hoạch. 2/19/2014 12 23 3.2.1. Thuật toán Quinlan (tt) Sau khi phân hoạch theo màu tóc xong, chỉ có phân hoạch theo tóc vàng (Pvàng) là còn chứa những người cháy nắng và không cháy nắng nên ta sẽ tiếp tục phân hoạch tập này. Ta sẽ thực hiện thao tác tính vector đặc trưng tương tự đối với các thuộc tính còn lại (chiều cao, cân nặng, dùng kem). Trong phân hoạch Pvàng, tập dữ liệu của chúng ta còn lại là : Tên Ch.Cao Cân Nặng Dùng kem? Kết quả Sarah T.Bình Nhẹ Không Cháy Dana Cao T.Bình Có Không Annie Thấp T.Bình Không Cháy Kartie Thấp Nhẹ Có Không 24 3.2.1. Thuật toán Quinlan (tt) VC.Cao(Cao) = (0/1,1/1) = (0,1) VC.Cao(T.B) = (1/1,0/1) = (1,0) VC.Cao(Thấp) = (1/2,1/2) VC.Nặng (Nhẹ) = (1/2,1/2) VC.Nặng (T.B) = (1/2,1/2) VC.Nặng (Nặng) = (0,0) VKem (Có) = (0/2,2/2) = (0,1) VKem (Không) = (2/2,0/2) = (1,0) 2 thuộc tính dùng kem và chiều cao đều có 2 vector đơn vị. Ta chọn phân hoạch theo thuộc tính dùng kem. 2/19/2014 13 25 3.2.1. Thuật toán Quinlan (tt) Kết quả Cây định danh cuối cùng : Vàng Nâu Đỏ 26 3.2.2. Phương pháp độ đo hỗn loạn Với mỗi thuộc tính dẫn xuất ta chỉ cần tính ra độ đo hỗn loạn và lựa chọn thuộc tính nào có độ đo hỗn loạn là thấp nhất. Công thức tính như sau : trong đó : • bt là tổng số phần tử có trong phân hoạch • bj là tổng số phần tử có thuộc tính dẫn xuất A có giá trị j. • bri : tổng số phần tử có thuộc tính dẫn xuất A có giá trị j và thuộc tính mục tiêu có giá trị i. 2/19/2014 14 27 Ví dụ: STT Kích cỡ Màu sắc Hình dáng Quyết định 1 Trung bình Đỏ Cầu Mua 2 Lớn Vàng Hộp Mua 3 Trung bình Xanh Trụ Không mua 4 Nhỏ Xanh Cầu Mua 5 Trung bình Xanh Nón Không mua 6 Nhỏ Xanh Nón Không mua 7 Trung bình Đỏ Trụ Mua 28 Ví dụ (tt) Nhỏ Trung bình Lớn √ 4 6 √ 1 3 5 √ 7 √ 2 Kích cỡ Màu sắc Vàng XanhĐỏ √ 2 √ 1 √ 7 3 √ 4 5 6 Hình dáng Cầu √ 1 √ 4 Hộp √ 2 3 √ 7 Trụ 5 6 Nón 2/19/2014 15 29 Ví dụ (tt) 46.0 4 3log 4 3 4 1log 4 1 7 400 22 ≈      ×−×−++= 7 6 7 4 7 20 1 1log 1 1 7 1 4 2log 4 2 4 2log 4 2 7 4 2 1log 2 1 2 1log 2 1 7 2 22222 =+=      −×−+      ×−×−+      ×−×−= Độ hỗn loạn TB kích cỡ: 7 20 2 1log 2 1 2 1log 2 1 7 200 22 =+      ×−×−++= Độ hỗn loạn TB màu sắc: Độ hỗn loạn TB hình dáng: 30 Ví dụ (tt) Chọn thuộc tính hình dáng vì có độ hỗn loạn trung bình nhỏ nhất: Hình dáng Cầu Nón Hộp Trụ MuaMua ? Không mua 2/19/2014 16 31 Ví dụ (tt) STT Kích cỡ Màu sắc Quyết định 3 Trung bình Xanh Không mua 7 Trung bình Đỏ Mua Sau khi test lần 1 xong, ta đã loại ra 5 mẫu ổn định => có 1 bảng nhỏ hơn: Kích cỡ 3 √ 7 Trung bình Màu sắcXanh Đỏ 3 √ 7 Độ hỗn loạn trung bình kích cỡ:=1 Độ hỗn loạn trung bình màu sắc:=0 32 Ví dụ (tt) Chọn thuộc tính màu sắc vì có độ hỗn loạn TB nhỏ nhất: Màu sắc Đỏ Xanh Mua Không mua Cầu Nón Hộp Trụ Hình dáng MuaMua Không mua Màu sắc Đỏ Xanh Mua Không mua Cây quyết định: