Bài giảng Trí tuệ nhân tạo - Chương 9: Học máy - Trần Ngân Bình

Chương 9	Học MáyGiáo viên: Trần Ngân BìnhChương 9. p.2Học 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): ID3Tiếp cận kết nối: Các mạng neuron sinh họcTiếp cận di truyền hay tiến hóa: giải thuật genetic Chương 9. p.3Cây quyết định (ID3)Là một giải thuật học đơn giản nhưng thành côngCâ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âyCá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.Chương 9. p.4Ví dụ Cây QĐ: Chơi TennisMục đích: học để xem có chơi Tennis không?Cây quyết định:YesQuang cảnhnắngÂm umưaĐộ ẩmYesGiócaoTrung bìnhmạnhnhẹNo YesNoChương 9. p.5Quy 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àyQuang cảnhNhiệt độĐộ ẩmGióChơi TennisD1Nắng NóngCaonhẹKhôngD2NắngNóng CaoMạnhKhôngD3Âm uNóngCaoNhẹCóD4Mưaấm ápCaonhẹCóD5Mưa MátTBnhẹCóD6 MưaMátTBMạnhKhôngD7Âm uMátTBMạnhCóD8Nắngấm ápCaonhẹKhôngD9Nắng MátTBnhẹCóD10Mưaấm ápTBnhẹCóD11Nắngấm ápTBMạnhCóD12Âm uấm ápCaoMạnhCóD13Âm uNóngTBnhẹCóD14Mưaấm ápCaoMạnhkhôngChương 9. p.6Làm sao để học được cây QĐTiếp cận đơn giảnHọ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.Chương 9. p.7Xây dựng cây QĐ: Trên - xuốngVòng lặp chính:A 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ỏiKhông quay lui => cực tiểu địa phươngLựa chọn tìm kiếm dựa trên thống kê => chịu được dữ liệu nhiễuThiên lệch quy nạp: thích cây ngắn hơn.Chương 9. p.18Chuyển cây về thành các luậtIf (Quang-cảnh =nắng)  (Độ ẩm = Cao) Then Chơi-Tennis = NoIf (Quang-cảnh =nắng)  (Độ ẩm = TB) Then Chơi-Tennis = YesIf (Quang-cảnh =Âm u) Then Chơi-Tennis = YesYesQuang cảnhnắngÂm umưaĐộ ẩmYesGiócaoTrung bìnhmạnhnhẹNo YesNoChương 9. p.19Khi 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, NoDữ 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ínhVí 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ânPhân loại người vay tiền theo khả năng chi trảChương 9. p.20Table 13.1:	Data from credit history of loan applications.Ví dụ: ước lượng độ an toàn của một tài khoản tín dụngChương 9. p.21Figure 13.13:	Một cây QĐ cho bài toán đánh giá độ an toàn của tín dụng.Chương 9. p.22Figure 13.14:	Một cây QĐ đơn giản hơn.Chương 9. p.23Figure 13.15:	Một cây QĐ đang xây dựng.Figure 13.16:	 Một cây QĐ khác đang xây dựng.Chương 9. p.24Neural 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)Chương 9. p.25Neuron nhân tạoThà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} realCác trọng số 	wi 	realMột mức kích hoạt	∑i wixiMột hàm ngưỡng	f : ∑i wixi  tín hiệu raChương 9. p.26Neural NetworksCá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ệnCơ chế mã hóa:	sự thông dịch của các tín hiệu vào và 	tín hiệu raI1I2I3H1H2O1wijw11w12I1I2H1O1w11w12Chương 9. p.27Ví dụ: Neuron McCulloch-PittsCác neurron dùng để tính các hàm logic and và or Chương 9. p.28Học PerceptronMạng neuron đơn tầngCác giá trị vào 1 hoặc -1Các trọng số kiểu thựcMứ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 0 = +1, kết quả càng tốtChương 9. p.38Figure 10.12:	A backpropagation net to solve the exclusive-or problem.The Wij 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) ->0Sau 1400 lượt:	WH1 = -7.0	WHB = 2.6	 WO1 = -5.0	WH2 = -7.0	WOB = 7.0	 WO2 = -4.0	WHO = -11.0Chương 9. p.39Các vấn đề liên quan khi sử dụng Neural NetworksCá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 ẩnKhi nào sử dụng các nút thiên lệchCá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?Chương 9. p.40Giải thuật GeneticNắm bắt ý tưởng từ thuyết tiến hóaHọ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ánThành phần:Quần thể các giải pháp khả dĩHàm đánh giáCác phép toán tạo con mới: giao nhau (crossover)Đột biến (mutation)Giải thuật:Điều kiện kết thúc: #vònglặp, Trung bình ‘độ tốt’ của quần thể Khởi tạo quần thểĐK thỏaGọi hàm đánh giá Chọn các thành viên tốtTạo con mớiThay thế thành viên kém bằng các con mớiChọn giải pháp từ quần thểNY