Bài giảng Máy học và mạng Neural - Bài 6: Học với luật Bayes và giải thuật di truyền - Vũ Đức Lung

07/08/2013 1 Máy học và mạng neural (Machine Learning and Neural Network) Giảng viên: TS. Vũ Đức Lung Email: lungvd@uit.edu.vn 1 Bài 06: Học với luật Bayes (Bayesian Learning) và Giải thuật di truyền (Genetic algorithm – GA) 2 07/08/2013 2 Nội dung  Học Bayes  Định lý (xác suất) Bayes  Phương pháp lựa chọn giả thuyết  Thuật toán học MAP vét cạn  Thuật toán Phân lớp Bayes đơn giản Giải thuật di truyền  Các khái niệm  Giải thuật tổng quát  Các toán tử di truyền  Bài toán người đi bán hàng TSP  Dự báo TTCK kết hợp ANNs và GA  Các phương pháp học máy khác 3 Học với luật Bayes (Bayesian Learning)  Định lý (xác suất) Bayes  Phương pháp lựa chọn giả thuyết  Thuật toán học MAP vét cạn  Thuật toán Phân lớp Bayes đơn giản 4 07/08/2013 3 Tại sao dùng phương pháp Bayes? Giúp tạo ra những thuật toán học hiệu quả (như Naive Bayesian, Bayesian Belief Networks). • Có khả năng kết hợp tri thức tiên nghiệm và dữ liệu quan sát được. • Giúp biểu diễn tri thức không chắc chắn (thể hiện qua độ tin cậy (belief)) và biểu diễn mối quan hệ nhân quả không chắc chắn giữa các sự kiện. • Tận dụng độ tin cậy tiên nghiệm của người dùng. 5 Định lý (xác suất) Bayes? 6 07/08/2013 4 Phương pháp lựa chọn giả thuyết Ý tượng chọn giả thuyết nào có khả năng cao nhất sau khi quan sát dữ liệu. Phương pháp MAP (maximum a posteriori) Nếu P(hi)=P(hj) thì ta có phương pháp ML (Maximum Likelihood): 7 Một bác sỹ biết Bệnh nhân viêm màng não có triệu chứng cứng cổ S|M: 50% Xác suất một bệnh nhân bị viêm màng não M là 1/50.000 Xác suất một bệnh nhân bị cứng cổ S là 1/20 Một bệnh nhân bị cứng cổ hỏi xác suất anh/cô ta bị viêm màng não ? Ví dụ 0002.0 20/1 50000/15.0 )( )()|( )|(    SP MPMSP SMP 07/08/2013 5 Ví dụ Một bệnh nhân nhận được xét nghiệm ung thư là dương tính, hỏi khả năng bị ung thư của anh ta như thế nào? Biết rằng xét nghiệm đưa kết quả dương tính với độ chính xác 98% (true positive), và đưa ra kết quả xét nghiệm âm với độ chính xác 97% (true negative). Xác suất bệnh ung thư trong toàn bộ dân số là 0.08. P(cancer)=0.08 ; P(!cancer)=0.92; P(+|cancer)=0.98; P(-|cancer)=0.02; P(+|!cancer)=0.03; P(-|!cancer)=0.97. P(cancer|+)=P(+|cancer)*P(cancer)=0.98*0.08=0.0784 P(!cancer|+)=P(+|!cancer)*P(!cancer)=0.03*0.92=0.0276 Chuẩn hoá:P(cancer|+)=0.74 ; P(!cancer|+)=0.26 9 Thuật toán học MAP vét cạn Brute-Force MAP learning algorithm 1. Đối với mỗi giả thuyết h  H (không gian giả thuyết H), tính xác suất hậu nghiệm (posterior): 2. Đưa ra giả thuyết hMAP với xác suất hậu nghiệm lớn nhất: Nhận xét chỉ áp dụng được nếu |H| nhỏ. 10 07/08/2013 6 Phân lớp mẫu mới hMAP cho ta giả thuyết khả dĩ nhất trên tập dữ liệu D cho trước. Câu hỏi: nếu có một mẫu mới x, thì x có khả năng cao nhất được phân vào lớp nào? - không phải lúc nào hMAP(x) cũng là câu trả lời! Ví dụ: có 3 giả thuyết Với x ta có: 11 Phân lớp Bayes tối ưu Ví dụ: 12 (1) 07/08/2013 7 Thuật toán Phân lớp Bayes đơn giản • Một trong những thuật toán hữu dụng và thông dụng của Machine Learning (như cây quyết định, mạng Neural, ...). Thường được dùng trong các trường hợp: • Có tập huấn luyện lớn (dư thừa dữ liệu huấn luyện). • Các thuộc tính của bộ dữ liệu độc lập nhau (trong việc phân lớp). Đã được ứng dụng thành công trong: • Chuẩn đoán. • Phân loại văn bản. 13 Thuật toán Phân lớp Bayes đơn giản Giả sử f: XV bộ dữ liệu x được xác định bởi bộ thuộc tính-giá trị (a1, a2, ... , an) giá trị phân lớp khả dĩ nhất: giả định của NB: 14 07/08/2013 8 Thuật toán Phân lớp Bayes đơn giản 15 Thuật toán Phân lớp Bayes đơn giản Ví dụ: quyết định chơi Tenis: 16 07/08/2013 9 Ví dụ bài toán chơi Tennis 17 Day Outlook Temp. Humidity Wind Play tennis 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 3 Overcast Hot High Weak Yes 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 7 Overcast Cool Normal Strong Yes 8 Sunny Mild High Weak No 9 Sunny Cold Normal Weak Yes 10 Rain Mild Normal Weak Yes 11 Sunny Mild Normal Strong Yes 12 Overcast Mild High Strong Yes 13 Overcast Hot Normal Weak Yes 14 Rain Mild High Strong No Thuật toán Phân lớp Bayes đơn giản Theo trên thì xác suất thành phần P(ai|vj) = nc/n, trong đó: • n - số lượng mẫu có giá trị phân lớp vj • nc số lượng mẫu có v=vj và a=ai Tình huống giá trị phân lớp vj không có ai nào, dẫn tới: = 0 và = 0 Giải pháp: sử dụng công thức làm trơn Trong đó: • n - số lượng mẫu có giá trị phân lớp vj • nc số lượng mẫu có v=vj và a=ai • p là ước lượng tiên nghiệm cho • m là trọng số (kích thước mẫu tương đương) 18 07/08/2013 10 Thuật toán Phân lớp Bayes đơn giản Ứng dụng phân loại văn bản: (là một trong những thuật toán hiệu quả nhất, bên cạnh SVM). 1. Biểu diễn mỗi tài liệu dưới dạng vector các từ, mỗi thuộc tính là một từ tại một vị trí của tài liệu. 2. Học: Dùng các mẫu huấn luyện để xác định: P(+),P(-), P(doc|+), P(doc|-) Giả thiết của NB: Trong đó P(ai=wk|vj) là xác suất để từ ở vị trí i là wk đối với lớp vj và giả thiết thêm: 19 Thuật toán Phân lớp Bayes đơn giản 20 07/08/2013 11 Thuật toán Phân lớp Bayes đơn giản 21  Sử dụng thuật toán Naïve Bayes (công thức tính P(ai=wk|vj)) P(spam|token)= P(spam) * P(token|spam) / P(token) Trong đó, các thông số được tính bằng  P( spam|token) : xác suất spam của từ khóa token  P(spam): tỉ lệ thư spam trên tổng số thư  P(token): Số lần xuất hiện của token trên tổng số thư  P(token|spam):Số lần xuất hiện của token trên tổng thư spam http:// lhu.edu.vn 22 VD ứng dụng lọc thư rác 07/08/2013 12  Ví dụ  P(spam|bán) = P(600/1000) * P(300/600) / P(400/1000) = 0.6*0.5/0.4=0.75=75%  P(ham|bán) =P(400/1000) * P(100/400)/P(400/1000) = 0.4*0.25/0.4=0.25=25%  P(spam|mua) =P(600/1000) * P(90/600) / P(100/1000) = 0.6*0.15/0.1=0.9=90%  P(ham|mua ) =P(400/1000) *P(10/400) /P(100/1000) = 0.4*0.025/0.1=0.1=10% http:// lhu.edu.vn 23 Từ đơn Tần số xuất hiện HAM(thư tốt) SPAM(thư rác) Tổng cộng Tổng số thư 400 600 1000 Token “bán” 100 300 400 Token “mua” 10 90 100 VD ứng dụng lọc thư rác Một vài nhận xét về Bayesian  Các sự kiện giả thiết là độc lập nhau không gần với thực tế  đơn giản hơn, dễ tính toán hơn  Thực tế rất khó để tính được xác suất kết hợp của các thuộc tính phụ thuộc lẫn nhau Mạng Bayesian đưa ra giả thiết phức tạp hơn, các sự kiện phụ thuộc một phần (độc lập có điều kiện), gần thực tế hơn nhưng vẫn có thể tình toán được  Nghiên cứu thêm về Bayesian Networks [Mitchell, chapter 6] 24 07/08/2013 13 Giải thuật di truyền Genetic algorithm - GA  Là thuật toán tìm kiếm bắt chước sự chọn lọc tự nhiên và di truyền: – Các cá thể khỏe có khả năng thích nghi tốt với môi trường sẽ được tái sinh và nhân bản ở các thế hệ sau. – Mỗi cá thể có cấu trúc gien đặc trưng cho phẩm chất của cá thể đó – Trong quá trình sinh sản, các cá thể con có thể thừa hưởng các phẩm chất của cả cha và mẹ, cấu trúc gien của nó mang một phần cấu trúc gien của cha và mẹ – Trong quá trình tiến hóa, có thể xảy ra hiện tượng đột biến cấu trúc gien của cá thể con có thể chứa các gien mà cả cha và mẹ đều không có 25 Các khái niệm  Mỗi cá thể được mã hóa bởi một cấu trúc dữ liệu mô tả cấu trúc gen của cá thể đó gọi là nhiễm sắc thể (chromosome)  Mỗi nhiễm sắc thể được tạo thành từ các đơn vị được gọi là gen  Ví dụ mỗi nhiễm sắc thể có thể là một chuỗi nhị phân trong đó mỗi gen có thể được đại diện bởi một hay nhiều chữ số nhị phân  Thuật toán di truyền làm việc trên các quần thể gồm nhiều cá thể  Mỗi quần thể ứng với một gian đoạn phát triển sẽ được gọi là một thế hệ  Từ thế hệ ban đầu được tạo ra, thuật toán di truyền bắt chước sự chọn lọc tự nhiên và di truyền để biến đổi các thế hệ  Phần tử tốt nhất trong các thế hệ chính là kết quả của sự tìm kiếm bằng thuật toán di truyền 26 07/08/2013 14 Giải thuật tổng quát 27 Các điểm lưu ý  Phương pháp biểu diễn một cá thể trong quần thể các lời giải ứng viên của bài toán, hay nói khác hơn là hình thức biểu diễn một lời giải tiềm năng của bài toán.  Độ lớn của quần thể là số lượng ứng viên có trong quần thể.  Điều kiện dừng của vòng lặp?  Hàm đánh giá (fitness function)?  Chọn lựa bao nhiêu phần trăm lời giải tốt để giữ lại? 28 07/08/2013 15 Các toán tử di truyền 29 Toán tử di truyền 30 07/08/2013 16 VD1: Bài toán người đi bán hàng TSP  Ở bài toán này, dùng mẫu bit để biểu diễn cho lời giải của bài toán không phải là một cách hay. Chẳng hạn, ta có chín thành phố cần ghé thăm 1, 2, 9, ta xem mỗi thành phố như một mẫu 4 bit 0001, 0010, 1001. Khi đó một lời giải khả dĩ sẽ có hình thức như sau: Một cách khác: 31 VD1: Bài toán người đi bán hàng TSP  Sinh mẫu con: 32 07/08/2013 17 33 VD 2: Dự báo TTCK kết hợp ANNs và GA  Căn cứ vào các phân tích ở trên ta chọn sử dụng hàm tansigmoid trong các lớp ẩn và hàm purelinear trong lớp xuất. Cấu trúc mạng của ta sẽ có gồm có lớp nhập, từ 1 tới 2 lớp ẩn và lớp xuất. Theo Thuyết Cybenko về xấp xỉ hàm phi tuyến tính, bất kỳ một hàm nào đều có thể được xấp xỉ với một độ chính xác tùy ý bởi một mạng với 3 lớp Nơron có các hàm truyền tuyến tính trong lớp xuất và các hàm truyền nén trong hai lớp ẩn còn lại. -Lý do chọn hàm tansigmoid mà không chọn hàm sigmoid vì chuỗi thời gian tỷ suất lợi nhuận của ta chứa các giá trị trong đoạn [-1,1], do vậy hàm tansigmoid sẽ phù hợp hơn. - Lý do không chọn hàm harlimit là vì hàm này thích hợp cho các mạng thực hiện chức năng phân loại hơn là hồi qui như trong ý đồ thiết kế mô hình dự báo của ta. 34 Mạng Nơron có 2 lớp ẩn VD 2: Dự báo TTCK kết hợp ANNs và GA - Như vậy Mạng Nơron ta sử dụng sẽ có cấu trúc như sau: x-y-z-1 Trong đó: • x: số đầu vào của lớp nhập • y: số nơron trong lớp ẩn thứ nhất (y nguyên >1) • z: số nơron trong lớp ẩn thứ hai (z nguyên >=0) • 1: số đầu ra của mạng. • Như vậy với cấu trúc mạng như trên, ta đã định nghĩa xong lớp xuất cũng như các đặc tính của các nút trong lớp ẩn. Vấn đề còn lại là xác định số Nơron trong lớp ẩn cũng như số đầu vào. Vấn đề là không có một phương pháp chung nào cho việc lựa chọn cấu trúc mạng. Do vậy ta sẽ sử dụng giải thuật Giải thuật Di truyền tìm kiếm không gian cấu trúc mạnng x-y-z-1 để chọn ra số nút tối ưu trong các lớp. • Vì lý sự giới hạn của tài nguyên tính toán, ta sẽ chỉ cho Giải thuật Di truyền tìm kiếm một phần trong không gian x-y-z-1 là xMax-yMax-zMax-1, trong đó xMax, yMax và zMax lần lượt là các giới hạn trên mà ta đặt cho x, y và z tương ứng. Xác định cấu trúc mạng neural trong dự báo chứng khoán 07/08/2013 18 35 3 thành phần của Giải thuật Di truyền Thành phần thứ nhất: Tạo ra một quần thể khởi tạo gồm m các cá thể được lựa chọn ngẫu nhiên, hình thành nên thế hệ đầu tiên. Thành phần thứ hai: Nhập m cá thể này và cho ra ở đầu ra một giá trị đánh giá cho mỗi cá thể dựa trên một hàm mục tiêu (hàm thích nghi). Các đánh giá này mô tả mức độ thích nghi so với yêu cầu cho mỗi cá thể đang xét. Thành phần thứ ba: Chịu trách nhiệm cho việc tạo ra thế hệ tiếp theo (chọn giống). Một thế hệ mới được hình thành dựa trên những cá thể phù hợp (thích nghi) nhất của thế hệ trước. Thủ tục đánh giá thế hệ N và hình thành nên thế hệ N+1 dựa trên N này được lặp đi lặp lại cho đến khi thỏa một tiêu chuẩn nào đó về hiệu năng cho trước. VD 2: Dự báo TTCK kết hợp ANNs và GA Giải thuật di truyền: Các thành phần chính 36 VD 2: Dự báo TTCK kết hợp ANNs và GA Giải thuật di truyền: Thế hệ khởi tạo Thành phần này định nghĩa các gien tạo nên bộ nhiễm sắc thể của mỗi cá thể (cấu trúc mạng). Có 3 gien mô tả số đầu vào (x) và số Nơron trong mỗi lớp ẩn (y, z, có hai lớp ẩn). Các giá trị mà các gien có thể có là : x: số đầu vào, x nguyên từ 1 đến xMax y: số nơron trong lớp ẩn thứ nhất, y nguyên từ 1 đến yMax z: số nơron trong lớp ẩn thứ hai, z nguyên từ 0 đến zMax z=0 khi không có lớp ẩn thứ 2. Ta không quan tâm tới các mạng Nơron có số nút trên cả hai lớp ẩn bằng 0 (y=0 và z=0) vì chúng cho ra các mô hình tuyến tính. Như vậy một nhiễm sắc thể được định nghĩa như là một bộ ba ‘x y z’. Quần thể khởi tạo gồm m bộ nhiễm sắc thể được chọn ngẫu nhiên sao cho tất cả các bộ nhiễm sắc thể này đều có cấu trúc khác nhau trong thế hệ đầu tiên (mục đích để tạo ra một không gian đa dạng nhất có thể). 07/08/2013 19 37 VD 2: Dự báo TTCK kết hợp ANNs và GA Giải thuật di truyền: Hàm thích nghi Sau khi thế hệ đầu tiên đã được định nghĩa, ta sử dụng các hàm thích nghi cho trong bảng sau để đánh giá từng bộ nhiễm sắc thể trong số m bộ nhiễm sắc thể đang có trong thế hệ này. 38 VD 2: Dự báo TTCK kết hợp ANNs và GA Giải thuật di truyền: Chọn giống Mỗi nhiễm sắc thể của một thế hệ mới được tạo ra từ một trong các các hoạt động tái sinh, lai ghép, hoặc đột biến. Các hoạt động này được lựa chọn theo một phương pháp lấy xác suất. Điều kiện dừng: Giải thuật sẽ kết thúc khi đạt đến một số lượng thế hệ cụ thể nào đó (gọi là MaxGen) và trả về một cấu trúc với tất cả các nhiễm sắc thể của các cá thể trong các thế hệ. 07/08/2013 20 39 Dự báo thị trường chứng khoán Lưu đồ Giải thuật Di truyền - Từ sơ đồ giải thuật di truyền ta có mỗi thành viên của thế hệ mới được tạo thành từ một trong các hoạt động tái sinh, lai ghép hay đột biến. Các hoạt động này sẽ được lựa chọn dựa theo một sơ đồ xác suất gọi là vòng quay Rulet (roulette wheel). - Mỗi hoạt động tương ứng với một xác suất là Ptái sinh, Plai ghép, và Pđột biến, sao cho: Ptái sinh + Plai ghép + Pđột biến =1  số lượng các cá thể con được tạo thành từ mỗi quá trình tái sinh, lai ghép hay đột biến cũng lần lượt tương ứng với các xác suất Ptái sinh, Plai ghép, và Pđột biến Tóm lại: việc lựa chọn một cá thể nào đó (hoặc hai trong trường hợp lai ghép) là dựa vào độ thích nghi của chúng và được thực hiện theo cơ chế vòng quay Rulet. Các phương pháp học máy khác  Học dựa trên các láng giềng gần nhất (Nearest neighbors learning)  SVM – Support Vector Machine  Học quy nạp luật (Rule induction)  ..... 40 07/08/2013 21 Giới Thiệu Phần mềm Thuật toán NB cho phân loại tài liệu: bayes.html. Mạng Bayesian (cài đặt trong JAVA): WEKA: Một số phần mềm đi kèm sách 41 Câu hỏi và bài tập 42 07/08/2013 22 Bài tập mẫu 43 Bài tập mẫu Cho tập dữ liệu huấn luyện như trong bảng. Hãy dùng Bayes tính P(yes|E) và P(no|E) để dự đoán một người với các thông số theo giả thuyết E sau có mua máy tính hay không? E={age<=30, income=medium, student=yes, credit-rating=fair} 44