Bài giảng Máy học - Chương 1: Giới thiệu máy học

Click to edit Master title style Click to edit Master text styles Second level Third level Fourth level Fifth level 12/24/2012 ‹#› Máy Học Kiểm tra Seminar (nhóm): 25% - Mỗi nhóm 5 bạn sẽ trình bày một chủ đề của môn học (nội dung + demo). Trắc nghiệm (cá nhân): 60% - Cuối mỗi buổi học sẽ có kiểm tra trắc nghiệm về nội dung của buổi học. Báo cáo (nhóm): 25% - Mỗi nhóm 5 bạn sẽ viết tóm tắt phần mình trình bày (không quá 30 trang), bao gồm cài đặt một ứng dụng để minh họa. Nội dung Chương 1: GIỚI THIỆU MÁY HỌC Chương 2: MÔ HÌNH CÂY QUYẾT ĐỊNH (Decision Tree) Chương 3: PHƯƠNG PHÁP RÚT GỌN SỐ CHIỀU DỮ LIỆU (PCA/LDA) Chương 4: MÔ HÌNH MẠNG NƠ RON (Neural Network) Chương 5: MÔ HÌNH MÁY HỌC VÉC TƠ HỖ TRỢ (SVM) Chương 6: MÔ HÌNH HỌC THEO NHÓM KẾT HỢP (Boosting / Adaboost) Chương 7: MÔ HÌNH THUẬT GIẢI DI TRUYỀN ĐỐI VỚI BÀI TOÁN PHÂN LỚP (Genetic Algorithm) Chương 8 : MÔ HÌNH HỌC TĂNG CƯỜNG (Reinforcement Learning) Chương 9: MÔ HÌNH HỌC MARKOV và MARKOV Ẩn Chương 10: CÁC THUẬT TOÁN CLUSTERING Chương 11: LÝ THUYẾT MÁY HỌC (PAC, Bayes, Bias/Variance) Giới thiệu Máy Học MÁY HỌC Máy học dùng để chỉ đến việc xác định, xây dựng và đánh giá mô hình tính toán dùng để tái tạo, dự đoán hay ra quyết định từ tập dữ liệu cho trước Tom M. Mitchell MÁY HỌC Trước đây có khuynh hướng cho rằng việc nghiên cứu xây dựng và đánh giá các mô hình học hay thuật toán trong ML đóng vai trò quan trọng, nhưng gần đây có khuynh hướng cho rằng việc xác định làm thế nào sử dụng ML đóng vai trò quan trọng hơn trong nghiên cứu ML (“Machine Learning that matters” and “Trends in ML according to Google Scholars ”) MÁY HỌC Classification or Categorization Clustering Regression Dimensionality Reduction Supervised learning Unsupervised learning Semi-Supervised learning MÔ HÌNH CÂY QUYẾT ĐỊNH Cây quyết định là 1 phương pháp phân lớp thuộc nhóm học có giám sát, mục tiêu từ bảng dữ liệu cho trước xây dựng một cây quyết định từ tổ hợp giá trị các thuộc tính X1 X2 …. Xn có thể suy ra giá trị của thuộc tính Y MÔ HÌNH CÂY QUYẾT ĐỊNH Các vấn đề trong việc xây dựng và áp dụng cây quyết định 	- Lựa chọn độ đo và xác định các node trong cây 	- Xử lý các data bị mất hay thiếu trong bảng dữ liệu 	- Xử lý trường hợp quá khớp (Overfitting) 	- Xử lý rút gọn cây qua quá trình sắp xếp lại và loại bỏ nhánh để tránh cây trùng lắp PHƯƠNG PHÁP RÚT GỌN SỐ CHIỀU DỮ LIỆU Xây dựng phương pháp rút gọn số chiều của một tập dữ liệu vector từ N xuống M với N << M PHƯƠNG PHÁP RÚT GỌN SỐ CHIỀU DỮ LIỆU Các vấn đề trong bài toán rút gọn số chiều 	- Cách xây dựng ma trận tương quan (hay ma trận hiệp phương sai) và cách giải bài toán eigenvalue và eigenvector của ma trận trên 	- Phương pháp PCA 	- Phương pháp LDA 	- phân tích nhân tử SVD MÔ HÌNH MẠNG NƠ RON Mạng neural và ý nghĩa sinh học MÔ HÌNH MẠNG NƠ RON Mô hình perceptron Mô hình mạng đa lớp Mô hình mạng hai lớp Nghiên cứu các thuật toán học và đánh giá các mô hình trên MÔ HÌNH MÁY HỌC VÉC TƠ HỖ TRỢ Là phương pháp phân lớp dựa trên lý thuyết thống kê Dữ liệu có thể phân chia qua hàm tuyến tính Dữ liệu không thể phân chia qua hàm tuyến tính Trong trường hợp không thể phân chia tuyến tính Kernel MÔ HÌNH MÁY HỌC VÉC TƠ HỖ TRỢ Các vấn đề trong mô hình máy học vec tơ hỗ trợ 	- Xây dựng mô hình phân lớp tuyến tính 	- Xây dựng mô hình hồi quy tuyến tính 	- Xây dựng và sử dụng kernel MÔ HÌNH HỌC THEO NHÓM KẾT HỢP Mô hình học kết hợp nghiên cứu việc kết hợp các hàm fi để tạo thành bộ phân lớp tốt hơn f1 f2 f3 f4 MÔ HÌNH HỌC THEO NHÓM KẾT HỢP Mô hình học mạnh : trong việc phân lớp đó là những phân lớp có độ chính xác cao mô hình yếu (không phải là 100%). Mô hình học yếu hơn: trong việc phân lớp đó là những phân lớp có độ chính xác không cao (nhưng không có nghĩa weak là quá thấp) phải hơn việc phân lớp ngẫu nhiên một chút. Vấn đề trong mô hình học theo nhóm kết hợp là xác định các trọng số kết hợp của các mô hình học yếu để tạo thành mô hình học mạnh hơn. Vấn đề phân chia bộ dữ liệu học để đạt được mô hình học mạnh hơn. MÔ HÌNH THUẬT GIẢI DI TRUYỀN Thuật giải di truyền (GA-Genetic Algorithms) là giải thuật tìm kiếm, chọn lựa các giải pháp tối ưu để giải quyết các bài toán thực tế khác nhau, dựa trên cơ chế chọn lọc của tự nhiên: từ tập lời giải ban đầu, thông qua nhiều bước tiến hoá, hình thành tập lời giải mới phù hợp hơn, và cuối cùng dẫn đến lời giải tối ưu toàn cục. MÔ HÌNH THUẬT GIẢI DI TRUYỀN Xây dựng cấu trúc gen cho mỗi lời giải của bài toán, từ đó mã hoá thành một nhiễm sắc thể. Giải mã các nhiễm sắc thể thành lời giải của bài toán và đo lường mức độ lỗi của lời giải. Xây dựng thuật toán theo cơ chế di truyền để tìm kiếm các nhiễm sắc thể tốt trên không gian lời giải. MÔ HÌNH HỌC TĂNG CƯỜNG Mô hình học tăng cường là mô hình xây dựng dựa trên mô hình sau Học tăng cường nghiên cứu cách thức một agent trong một môi trường nên chọn thực hiện các hành động nào để cực đại hóa điểm thưởng reward MÔ HÌNH HỌC TĂNG CƯỜNG Nghiên cứu các xác định môi trường, điểm thưởng và agent cho mô hình bài toán mà mình cần giải Thuật toán Q-learning và Sarsa MÔ HÌNH MARKOV - MARKOV ẨN Mô hình Markov Mô hình Markov ẩn …. O1 O2 OT-2 OT-1 OT X1 X2 XT-2 XT-1 XT MÔ HÌNH MARKOV - MARKOV ẨN Xác định mô hình xác suất sử dụng trong mô hình Markov và Markov ẩn. Xác định các thuật toán học cho mô hình Markov ẩn và các thuật toán tính xác suất lân cận cực đại trong mô hình Makov và Markov ẩn. CÁC THUẬT TOÁN CLUSTERING Các thuật toán phân nhóm dựa trên đồ thị We0 = 17 We1 = 2 We2 = 1 We4 = 2 We5 = 3 We3 = 3 We7 = 2 We6 = 2 We9 = 1 We8 = 3 We10 = 4 We11 = 3 Các thuật toán phân nhóm dựa trên vùng ảnh hưởng Các thuật toán branch and bound ….. LÝ THUYẾT MÁY HỌC Giới thiệu máy học và lý thuyết máy học Các vấn đề về lỗi Độ phức tạp mẫu cho không gian giả thuyết hữu hạn Độ phức tạp mẫu cho không gian giả thuyết vô hạn Giới hạn lỗi