Bài giảng Máy học và mạng neural: Bài 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

Bài 01 – Tổng quan về học máy

 Vai trò của học máy trong trí tuệ nhân tạo.  Học máy là gì?  Ứng dụng của học máy.  Các lĩnh vực liên quan đến học máy.  Các bước của học máy.  Các vấn đề cơ bản trong học máy. Ví dụ về thuật toán học máy.  Cách tiếp cận của khoá học

Những vấn đề cốt lõi của TTNT

Biểu diễn (representation). Lập luận (reasoning).

• • • Học (learning). • Tương tác (interaction).

 Là một nhánh của trí tuệ nhân tạo  Liên quan đến việc phát triển các kĩ thuật cho phép các máy

tính có thể “học”

 Ở VN nằm trong môn học TTNT nâng cao  Trên thế giới là một môn học hoặc nhiều môn học riêng và

được chú trọng giảng dạy ở bậc ĐH&SĐH

Tổng quan về học máy

 Con người học như thế nào? – Nhớ và làm lại (học vẹt). – Học nhờ quan sát và khái quát hoá (học hiểu).  Các định nghĩa về Học máy (Machine learning)

– Học là sự thay đổi thích ứng trong hệ thống giúp cho hệ thống có thể xử lý vấn đề ngày càng hiệu quả hơn khi gặp lại những tình huống tương tự [Simon, 1983]

– Một quá trình mà một chương trình máy tính cải thiện hiệu suất của nó

trong một công việc thông qua kinh nghiệm [Mitchell, 1997]

(Học máy = Cải thiện hiệu quả một công việc thông qua kinh nghiệm) – Việc lập trình các máy tính để tối ưu hóa một tiêu chí hiệu suất dựa trên các dữ liệu ví dụ hoặc kinh nghiệm trong quá khứ [Alpaydin, 2004]

Học máy là gì?

 Học là cần thiết trong những môi trường chưa quen thuộc,  Học là một phương pháp hữu hiệu để xây dựng hệ thống  Học là cách để các chương trình thông minh có thể hiệu chỉnh

hành vi để tăng hiệu quả giải quyết vấn đề.

 Học khi nào:

– Tri thức con người chưa đủ (VD Trên sao hỏa), – Con người không đủ khả năng giải thích(nhận dạng giọng nói) – Lời giải thay đổi theo thời gian (routing on a computer network) – Lời giải cần thích nghi trong từng trường hợp cụ thể (sinh vật học)

Học làm gì?khi nào học?

Ứng dụng của học máy

xây dựng ngày càng đầy đủ.

 Dữ liệu ngày càng nhiều và dư thừa nhưng tri thức cần thì

thiếu.

 Sức mạnh tính toán của máy tính được nâng cao.  Nhiều ngành khoa học mới nảy nở (VD Bioinformatics)

Hiện học máy được ứng dụng trên nhiều lĩnh vực do:  Một loạt các thuật toán học máy ra đời. Cơ sở lý thuyết được

 Khai phá dữ liệu (Data Mining)  Máy truy tìm dữ liệu (search engines)  Chẩn đoán y khoa (medical diagnosis)  Phát hiện thẻ tín dụng giả (Banking bảo mật thông tin),  Phân tích thị trường chứng khoán, thị trường tài chính (stock

market analysis)

 Phân loại các chuỗi DNA (bioinformatics )  Nhận dạng tiếng nói và chữ viết, dịch tự động, (speech and handwriting recognition, natural language processing)

 Chơi trò chơi (game playing)  Chơi và cử động rô-bốt (robot locomotion).

Ứng dụng của học máy

 Inductive Concept Learning.  Decision Trees.  Artificial Neural Networks.  Bayesian Networks.  Support Vector Machines.  Learning Markov Processes.  Instance-Based (Lazy) Learning.  Learning by Explanation.  Learning by Reinforcement.  Heuristic Learning (GAs, GP, ...).  Rule Induction.

........

Các phương pháp học máy

Các Lĩnh Vực Liên Quan

 Artificial intelligence Computational complexity theory Bayesian methods Control theory Information theory Philosophy Psycholopy and neurobiology Statistics ….

Quy trình học máy

Các loại thuật toán Học máy

 Học nửa giám sát : kết hợp các ví dụ có gắn nhãn và không gắn nhãn để sinh một hàm hoặc một bộ phân loại thích hợp.

 Học tăng cường : trong đó, thuật toán học một chính sách hành động tùy theo các quan sát về thế giới. Mỗi hành động đều có tác động tới môi trường, và môi trường cung cấp thông tin phản hồi để hướng dẫn cho thuật toán của quá trình học.

Các loại thuật toán Học máy (tiếp)

 Chuyển đổi: tương tự học có giám sát nhưng không xây dựng hàm một cách rõ ràng. Thay vì thế, cố gắng đoán kết quả mới dựa vào các dữ liệu huấn luyện, kết quả huấn luyện, và dữ liệu thử nghiệm có sẵn trong quá trình huấn luyện.

 Học cách học: trong đó thuật toán học thiên kiến quy nạp của

chính mình, dựa theo các kinh nghiệm đã gặp.

Các loại thuật toán Học máy (tiếp)

Các bước trong học máy

Ví dụ: Xây dựng chương trình chơi cờ tướng thông minh.

T: chơi cờ tướng (người-máy, máy-máy). P: số phần trăm ván thắng khi chơi với các kiện tướng quốc gia. E: Kinh nghiệm từ những ván tự chơi (máy-máy) và chơi với người.

1. Phát biểu bài toán: [Tom Mitchell, 1997] Học = Cải thiện khả năng thực hiện nhiệm vụ T của hệ thống dựa trên kinh nghiệm E với độ đo chất lượng thực hiện nhiệm vụ P.

Các bước trong học máy

quốc gia.

T: chơi cờ tướng (người-máy, máy-máy). P: số phần trăm ván thắng khi chơi với các kiện tướng

Thu thập kinh nghiệm (dữ liệu) E ở đâu? Như thế nào? Đâu là thành phần cần học trong chương trình? Biểu diễn thành phần đó như thế nào? Dùng thuật toán gì để học?

Vấn đề: – – – – –

Các bước trong học máy

được chứa ngay trong các ví dụ học (Phản hồi trực tiếp) hay được cung cấp gián tiếp (có trễ, ví dụ từ môi trường hoạt động hay trong quá trình hoạt động, ví dụ trong spam, nhận dạng giọng nói, nhận dạng chữ viết, nhận dạng ảnh vân tay,…)?  Các dữ liệu học theo kiểu có giám sát hay không có giám sát?

(có đầu ra lý tưởng không?).

 Dữ liệu có mang tính đại diện cho hay tương thích với các ví

dụ của hệ thống trong tương lai (future test examples) hay đích của quá trình học không?

2. Xác định kiểu dữ liệu dùng cho huấn luyện:  Các thông tin hướng dẫn quá trình học (training feedback)

f: Board → Move.

Các bước trong học máy

tốt nhất có thể đến được từ b thông qua chuỗi nước đi tối ưu.

3. Xác định hàm mục tiêu: Xác định trực tiếp: V: Board → R Ví dụ định nghĩa hàm giá trị như sau: b là trạng thái cuối bàn cờ thắng cuộc: V(b)=100. b là trạng thái cuối bàn cờ thua cuộc: V(b)= -100. b là trạng thái bàn cờ hoà: V(b)=0. Nếu b không phải là trạng thái kết thì V(b)=V(b’). Trong đó b’ là trạng thái kết

Các bước trong học máy

4. Xác định (lựa chọn) cách biểu diễn cho hàm mục

tiêu cần học:

 Dạng hàm đa thức (a polynomial function) trên các đặc trưng của bàn cờ? (ví dụ số lượng xe, pháo, mã, tốt, tượng, sỹ).

 Mạng Neural nhân tạo (an artificial neural network)?  Tập luật (a set of rules)?  Cây quyết định (a decision tree)?  Biểu thức giải tích tiến hoá (analysis of evolution) từ lập trình

GEN?

Các bước trong học máy

Xác định biểu diễn cho hàm mục tiêu: Ví dụ:  Dạng hàm đa thức trên các đặc trưng của bàn cờ? (ví

dụ số lượng xe, pháo, mã, tốt, tượng, sỹ). V’(b) = w0+w1xe+w2ph+w3ma+w4to+w5tu+w6sy

Các bước trong học máy

5. Lựa chọn một giải thuật học máy có thể học (xấp xỉ)

Hàm mục tiêu V(b). Hàm học được V’(b). Vtrain(b): Giá trị đầu ra lý tưởng trong tập mẫu. Ước lượng giá trị đầu ra lý tưởng: Vtrain(b)=V’(Successor(b)).

được hàm mục tiêu:

V(b)=0 + 1rp(b) + 2bp(b) Initial weights: 0=-10, 1 =75, 2 =-60

V(b0)=0 + 1*2 + 2*2 = 20

Example: 4x4 checkers

m1 : bb1 V(b1)=20 m2 : bb2 V(b2)=20 m3 : bb3 V(b3)=20

Example 4x4 checkers

1. Compute error(b0) = Vtrain(b) – V(b0) = V(b1) – V(b0) = 0 2. For each board feature fi, update weight i  i +  fi error(b)

V(b1)=20 V(b0)=20

0  0 + 0.1 * 1 * 0 1  1 + 0.1 * 2 * 0 2  2 + 0.1 * 2 * 0

Example: 4x4 checkers

V(b2)=20

V(b0)=20 V(b1)=20

V(b3)=20

Example: 4x4 checkers

V(b3)=20

V(b4a)=20 V(b4b)=-55

Example 4x4 checkers

1. Compute error(b3) = Vtrain(b) – V(b3) = V(b4) – V(b3) = -75 2. For each board feature fi, update weight

V(b4)=-55 V(b3)=20

i  i +  fi error(b) : 0=-10, 1 =75, 2 =-60 0  0 - 0.1 * 1 * 75, 0 = -17.5 1  1 - 0.1 * 2 * 75, 1 = 60 2  2 - 0.1 * 2 * 75, 2 = -75

Example: 4x4 checkers

0 = -17.5 , 1 = 60, 2 = -75

V(b5)=-107.5 V(b4)=-107.5

Example 4x4 checkers

V(b6)=-167.5 V(b5)=-107.5

error(b5) = Vtrain(b) – V(b5) = V(b6) – V(b5) = -60 0=-17.5, 1 =60, 2 =-75 i  i +  fi error(b) 0  0 - 0.1 * 1 * 60, 0 = -23.5 1  1 - 0.1 * 1 * 60, 1 = 54 2  2 - 0.1 * 2 * 60, 2 = -87

Final board state: black won Vf(b)=-100

Example 4x4 checkers

error(b6) = Vtrain(b) – V(b6) = Vf(b6) – V(b6) = 97.5 0=-23.5, 1 =54, 2 =-87 i  i +  fi error(b) 0  0 + 0.1 * 1 * 97.5, 0 = –13.75 1  1 + 0.1 * 0 * 97.5, 1 = 54 2  2 + 0.1 * 2 * 97.5, 2 = -67.5

V(b6)=-197.5

Các bước trong học máy

Thuật toán học: Luật cập nhật trọng số LMS: Lặp: Chọn mẫu huấn luyện b ngẫu nhiên. 1. Tính lỗi: Error(b)=Vtrain(b) - V’(b). 2. Đối với mỗi đặc trưng fi của bàn cờ: wi = wi + c . fi . Error(b) Trong đó c là tốc độ học (ví dụ 0.1).

Determine Type of Training Experience

Table of correct moves

Games against experts

Games against self

Determine Target Function

BoardMove

BoardValue

Determine Representation of Learned Function

polynomial

Artificial neural network

Linear function of six features

Determine Learning Algorithm

Gradient descent

Linear programming

Thiết kế các bước lựa chọn

Completed design

Một số vấn đề trong học máy

 Khi nào một thuật toán học hoạt động tốt?  Số lượng mẫu ảnh hưởng đến chất lượng học như thế

nào?

xử lý nhiễu dữ liệu?

 Ảnh hưởng của độ phức tạp của biểu diễn Khả năng

 Khả năng tự sửa đổi cấu trúc biểu diễn?  Khả năng học được?  Sử dụng tri thức sẵn có?  Học theo mô phỏng sinh học và tự nhiên?

Các vấn đề trong học máy

Vấn đề over-fitting

Vấn đề over-fitting – ví dụ

 Bài toán lọc SPAM: cho một tập các emails (training

examples) đã được đánh dấu spam/ham, một thuật toán ML sẽ đưa ra một “bộ luật” (prediction rule) mà dùng nó có thể tự động lọc các emails trong tương lai vào spam folder hay inbox.

 T, P, E?  Các mục tiêu?

– độ chính xác cao (đừng filter email của sếp vào spam folder), – dùng ít tài nguyên tính toán (spam filter chứ có phải VS.NET đâu mà

cần 4GB bộ nhớ và 2 phút để khởi động)

– dùng ít training data (đừng bắt click spam/ham 3 năm liên tục rồi mới

chịu làm việc)

– có tính khái quát cao, tiếng Anh gọi là general-purpose (một thuật toán

có thể dùng cho cả spam filter, web filter trong browser)

– có prediction rule đơn giản

Ví dụ học máy

Người dùng thích cái gì?

Ví dụ học máy

Credit scoring

Regression

Training examples of a person

Test images

Face Recognition

Ví dụ học máy

Lựa chọn của khoá học

Tiếp cận thuật toán đối với học máy: Tìm hiểu các thuật toán và mô hình học máy cơ bản

như:

 Học khái niệm  Cây quyết định,  Mạng Neural,  Mạng Bayesian,  Support Vector Machines,  Mô hình Markov ẩn,  Giải thuật di truyền  ...

 UCI Repository: http://www.ics.uci.edu/~mlearn/MLRepository.html  UCI KDD Archive:

http://kdd.ics.uci.edu/summary.data.application.html

 Statlib: http://lib.stat.cmu.edu/  Delve: http://www.cs.utoronto.ca/~delve/  BSDS500:

http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbe nch/

 fMRI: http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-81/www/

Resources: Datasets

 Journal of Machine Learning Research www.jmlr.org  Machine Learning  Neural Computation  Neural Networks  IEEE Transactions on Neural Networks  IEEE Transactions on Pattern Analysis and Machine

Intelligence

 Annals of Statistics  Journal of the American Statistical Association  ...

Resources: Journals

 International Conference on Machine Learning (ICML)

– ICML05: http://icml.ais.fraunhofer.de/

 European Conference on Machine Learning (ECML)

– ECML05: http://ecmlpkdd05.liacc.up.pt/

 Neural Information Processing Systems (NIPS)

– NIPS05: http://nips.cc/

 Uncertainty in Artificial Intelligence (UAI)

– UAI05: http://www.cs.toronto.edu/uai2005/

 Computational Learning Theory (COLT)