Bài giảng Trí tuệ nhân tạo - Chương 10: Học máy - Nguyễn Nhật Quang
Trí Tuệ Nhân Tạo
Nguyễn Nhật Quang
Viện Công nghệ Thông tin và Truyền thông
Trường Đại học Bách Khoa Hà Nội
Năm học 2009-2010
Nội dung môn học:
Giới thiệu về Trí tuệ nhân tạo
Tác tử
Giải quyết vấn đề: Tìm kiếm, Thỏa mãn ràng buộc
Logic và suy diễn
Biểu diễn tri thức
Suy diễn với tri thức không chắc chắn
Học máy
Giới thiệu về học máy
Phân lớp Naïve Bayes
Học dựa trên các láng giềng gần nhất
Lập kế hoặch
Trí Tuệ Nhân Tạo
2
Giới thiệu về Học máy
Các định nghĩa về Học máy (Machine learning)
động) của nó [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]
→ 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]
Biểu diễn một bài toán học máy [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
•
• Đối với các tiêu chí đánh giá hiệu suất P
• Thông qua (sử dụng) kinh nghiệm E
Trí Tuệ Nhân Tạo
3
Các ví dụ của bài toán học máy (1)
Bài toán lọc các trang Web theo sở
T: Dự đoán (để lọc) xem những trang
Web nào mà một người dùng cụ thể
thích đọc
Interested?
P: Tỷ lệ (%) các trang Web được dự
đoán đúng
E: Một tập các trang Web mà người
dùng đã chỉ định là thích đọc và một tập
không thích đọc
Trí Tuệ Nhân Tạo
4
Các ví dụ của bài toán học máy (2)
Bài toán phân loại các trang Web theo các chủ đề
T: Phân loại các trang Web theo các chủ đề đã định trước
P: Tỷ lệ (%) các trang Web được phân loại chính xác
E: Một tập các trang Web, trong đó mỗi trang Web gắn với một
chủ đề
Which
cat.?
Trí Tuệ Nhân Tạo
5
Các ví dụ của bài toán học máy (3)
Bài toán nhận dạng chữ
T: Nhận dạng và phân loại các
từ trong các ảnh chữ viết tay
P: Tỷ lệ (%) các từ được nhận
Which word?
dạng và phân loại đúng
E: Một tập các ảnh chữ viết
we do
in the right way
tay, trong đó mỗi ảnh được gắn
với một định danh của một từ
Trí Tuệ Nhân Tạo
6
Các ví dụ của bài toán học máy (4)
Bài toán robot lái xe tự động
T: Robot (được trang bị các
camera quan sát) lái xe tự động
trên đường cao tốc
Which steering
P: Khoảng cách trung bình mà
command?
robot có thể lái xe tự động
trước khi xảy ra lỗi (tai nạn)
Go
Move Move Slow Speed
right down up
E: Một tập các ví dụ được ghi
lại khi quan sát một người lái xe
mỗi ví dụ gồm một chuỗi các
ảnh và các lệnh điều khiển xe
straight left
Trí Tuệ Nhân Tạo
7
Quá trình học máy
Tập học
Huấn luyện
hệ thống
Tập dữ liệu
(Dataset)
Tập tối ưu
(Validation set)
các tham số
của hệ thống
Tập thử nghiệm
(Test set)
Thử nghiệm
hệ thống
Trí Tuệ Nhân Tạo
8
Học có vs. không có giám sát
Học có giám sát (supervised learning)
nhãn lớp (hoặc giá trị đầu ra mong muốn) của ví dụ học đó
Bài toán học phân lớp (classification problem)
D_train = {(<Biểu_diễn_của_x>, <Nhãn_lớp_của_x>)}
Bài toán học dự đoán/hồi quy (prediction/regression problem)
D_train = {(<Biểu_diễn_của_x>, <Giá_trị_đầu_ra_của_x>)}
Học không có giám sát (unsupervised learning)
Mỗi ví dụ học chỉ chứa mô tả (biểu diễn) của ví dụ học đó - mà
không có bất kỳ thông tin nào về nhãn lớp hay giá trị đầu ra mong
muốn của ví dụ học đó
Bài toán học phân cụm (Clustering problem)
Tập học D_train = {(<Biểu_diễn_của_x>)}
Trí Tuệ Nhân Tạo
9
Bài toán học máy – Các thành phần chính (1)
Lựa chọn các ví dụ học (training/learning examples)
•
ngay trong các ví dụ học, hay là được cung cấp gián tiếp (vd: từ môi
trường hoạt động)
• Các ví dụ học theo kiểu có giám sát (supervised) hay không có giám sát
(unsupervised)
• Các ví dụ học phải tương thích với (đại diện cho) các ví dụ sẽ được sử
dụng bởi hệ thống trong tương lai (future test examples)
Xác định hàm mục tiêu (giả thiết, khái niệm) cần học
• F: X → {0,1}
• F: X → {Một tập các nhãn lớp}
• F: X → R+ (miền các giá tri số thực dương)
• …
Trí Tuệ Nhân Tạo
10
Bài toán học máy – Các thành phần chính (2)
Lựa chọn cách biểu diễn cho hàm mục tiêu cần học
•
• Một tập các luật (a set of rules)
• Một cây quyết định (a decision tree)
•
• …
Lựa chọn một giải thuật học máy có thể học (xấp xỉ)
được hàm mục tiêu
• Phương pháp học hồi quy (Regression-based)
• Phương pháp học quy nạp luật (Rule induction)
• Phương pháp học cây quyết định (ID3 hoặc C4.5)
• Phương pháp học lan truyền ngược (Back-propagation)
• …
Trí Tuệ Nhân Tạo
11
Các vấn đề trong Học máy (1)
Giải thuật học máy (Learning algorithm)
• Những giải thuật học máy nào có thể học (xấp xỉ) một hàm
mục tiêu cần học?
• Với những điều kiện nào, một giải thuật học máy đã chọn
sẽ hội tụ (tiệm cận) hàm mục tiêu cần học?
• Đối với một lĩnh vực bài toán cụ thể và đối với một cách
biểu diễn các ví dụ (đối tượng) cụ thể, giải thuật học máy
nào thực hiện tốt nhất?
Trí Tuệ Nhân Tạo
12
Các vấn đề trong Học máy (2)
Các ví dụ học (Training examples)
• Bao nhiêu ví dụ học là đủ?
• Kích thước của tập học (tập huấn luyện) ảnh hưởng thế
nào đối với độ chính xác của hàm mục tiêu học được?
• Các ví dụ lỗi (nhiễu) và/hoặc các ví dụ thiếu giá trị thuộc
tính (missing-value) ảnh hưởng thế nào đối với độ chính
xác?
Trí Tuệ Nhân Tạo
13
Các vấn đề trong Học máy (3)
Quá trình học (Learning process)
• Chiến lược tối ưu cho việc lựa chọn thứ tự sử dụng (khai
thác) các ví dụ học?
• Các chiến lược lựa chọn này làm thay đổi mức độ phức
tạp của bài toán học máy như thế nào?
• Các tri thức cụ thể của bài toán (ngoài các ví dụ học) có
thể đóng góp thế nào đối với quá trình học?
Trí Tuệ Nhân Tạo
14
Các vấn đề trong Học máy (4)
Khả năng/giới hạn học (Learning capability)
• Hàm mục tiêu nào mà hệ thống cần học?
Biểu diễn hàm mục tiêu: Khả năng biểu diễn (vd: hàm tuyến
tính / hàm phi tuyến) vs. Độ phưc tạp của giải thuật và quá
trình học
• Các giới hạn (trên lý thuyết) đối với khả năng học của các giải thuật
học máy?
• Khả năng khái quát hóa (generalize) của hệ thống từ các ví dụ học?
Để tránh vấn đề “over-fitting” (đạt độ chính xác cao trên tập học,
nhưng đạt độ chính xác thấp trên tập thử nghiệm)
• Khả năng hệ thống tự động thay đổi (thích nghi) biểu diễn (cấu trúc)
bên trong của nó?
Để cải thiện khả năng (của hệ thống đối với việc) biểu diễn và học
hàm mục tiêu
Trí Tuệ Nhân Tạo
15
Vấn đề over-fitting (1)
Một hàm mục tiêu (một giả thiết) học được h sẽ được gọi
tồn tại một hàm mục tiêu khác h’ sao cho:
• h’ kém phù hợp hơn (đạt độ chính xác kém hơn) h đối với tập
học, nhưng
• h’ đạt độ chính xác cao hơn h đối với toàn bộ tập dữ liệu (bao
gồm cả những ví dụ được sử dụng sau quá trình huấn luyện)
Vấn đề over-fitting thường do các nguyên nhân:
• Lỗi (nhiễu) trong tp huấn (do quá trình thu thp/xây d
tập dữ liệu)
• Số lượng các ví dụ học quá nhỏ, không đại diện cho toàn bộ tập
Trí Tuệ Nhân Tạo
16
Vấn đề over-fitting (2)
Giả sử gọi Dlà tập toàn bộ các ví dụ, và D_trainlà tập
Giả sử gọi ErrD(h)là mức lỗi mà giả thiết hsinh ra đối
D_train
ra đối với tập D_train
hD_train
nếu tồn tại một giả thiết khác h’:
•ErrD_train(h) < ErrD_train(h’), và
•ErrD(h) > ErrD(h’)
Trí Tuệ Nhân Tạo
17
Vấn đề over-fitting (3)
Trong số các giả thiết (hàm mục tiêu)
Hàm mục tiêu f(x) nào
đạt độ chính xác cao nhất
đối với các ví dụ sau này?
học được, giả thiết (hàm mục tiêu) nào
khái quát hóa tốt nhất từ các ví dụ học?
Lưu ý: Mục tiêu của học máy là để
t c
dự đoán đối với các ví dụ sau này,
không phải đối với các ví dụ học
f(x)
Occam’s razor: Ưu tiên chọn hàm
mục tiêu đơn giản nhất phù hợp (không
nhất thiết hoàn hảo) với các ví dụ học
→Khái quát hóa tốt hơn
→Dễ giải thích/diễn giải hơn
→Độ phức tạp tính toán ít hơn
x
Trí Tuệ Nhân Tạo
18
Vấn đề over-fitting – Ví dụ
Tiếp tục quá trình học cây quyết định sẽ làm giảm độ chính xác đối
với tập thử nghiệm mặc dù tăng độ chính xác đối với tập học
[Mitchell, 1997]
Trí Tuệ Nhân Tạo
19
Phân lớp Naïve Bayes
Là các phương pháp học phân lớp có giám sát và dựa
Dựa trên một mô hình (hàm) xác suất
Việc phân loại dựa trên các giá trị xác suất của các khả
năng xảy ra của các giả thiết
Là một trong các phương pháp học máy thường được
sử dụng trong các bài toán thực tế
Trí Tuệ Nhân Tạo
20
Tải về để xem bản đầy đủ
52 trang
17600
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Trí tuệ nhân tạo - Chương 10: Học máy - Nguyễn Nhật Quang", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_tri_tue_nhan_tao_chuong_10_hoc_may_nguyen_nhat_qua.pdf
