Bài giảng Học máy (IT 4862) - Bài 4: Các phương pháp học có giám sát - Phần 1: Hồi quy tuyến tính - Nguyễn Nhật Quang

Học Máy
(IT 4862)
ễ hậNguy n N t Quang
quangnn-fit@mail.hut.edu.vn
Trường Đại học Bách Khoa Hà Nội
Viện Công nghệ thông tin và truyền thông
Năm học 2011-2012
Nội d ô hung m n ọc:
„ Giới thiệu chung
„ Đánh giá hiệu năng hệ thống học máy
Cá h há h d t ê á ất„ c p ương p p ọc ựa r n x c su
„ Các phương pháp học có giám sát
„ Hồi quy tuyến tính (Linear regression)
„ Các phương pháp học không giám sát
„ Lọc cộng tác
H tă ờ
2
Học Máy – IT 4862
„ ọc ng cư ng
Hồi quy tuyến tính – Giới thiệu
„ Với một ví dụ đầu vào, dự đoán một giá trị đầu ra kiểu số thực
„ Một phương pháp học máy đơn-giản-nhưng-hiệu-quả phù hợp 
khi hàm mục tiêu (cần học) là một hàm tuyến tínhh
∑+=++++= n ii xwwxwxwxwwxf 022110 ...)( (wi,xi ∈R)
„ Cần học (xấp xỉ) một hàm mục tiêu f
f: X → Y
=i
nn
1
• X: Miền không gian đầu vào (không gian vectơ n chiều – Rn)
• Y: Miền không gian đầu ra (miền các giá trị số thực – R)
• f: Hàm mục tiêu cần học (một hàm ánh xạ tuyến tính)
ƒ Thực chất, là học một vectơ các trọng số: w = (w0, w1, w2, ,wn)
3Học Máy – IT 4862
Hồi quy tuyến tính – Ví dụ
Hàm tuyến tính f(x) nào phù hợp?
f(x)x f(x)
0.13 -0.91
1.02 -0.17
3.17 1.61
-2.76 -3.31
1.44 0.18
x
5.28 3.36
-1.74 -2.46
7 93 5 56. .
... ...
Ví dụ: f(x) = -1.02 + 0.83x
4Học Máy – IT 4862
Các ví dụ học/kiểm thử
„ Đối với mỗi ví dụ học x=(x1,x2,...,xn), trong đó xi∈R
• Giá trị đầu ra mong muốn cx (∈R)
• Giá trị đầu ra thực tế (tính bởi hệ thống) ∑+= n
i
iix xwwy
1
0
→ wi là đánh giá hiện thời của hệ thống đối với giá trị trọng số của 
thuộc tính thứ i
=
→ Giá trị đầu ra thực tế yx được mong muốn là (xấp xỉ) cx
Đối với mỗi ví dụ kiểm thử =( )„ z z1,z2,...,zn
• Cần dự đoán (tính) giá trị đầu ra
• Bằng cách áp dụng hàm mục tiêu đã học được f 
5Học Máy – IT 4862
Hàm đánh giá lỗi
„ Giải thuật học hồi quy tuyến tính cần phải xác định hàm 
đá h iá lỗin g 
→ Đánh giá mức độ lỗi của hệ thống trong giai đoạn huấn luyện
„ Định nghĩa hàm lỗi E
• Lỗi của hệ thống đối với mỗi ví dụ học x:
2
1
0
2
2
1)(
2
1)( ⎟⎟⎠
⎞
⎜⎜⎝
⎛ −−=−= ∑
=
n
i
iixxx xwwcycxE
• Lỗi của hệ thống đối với toàn bộ tập huấn luyện D:
2
0
2
2
1)(
2
1)( ∑ ∑∑∑ ⎟⎟⎠
⎞
⎜⎜⎝
⎛ −−=−== n iixxx xwwcycxEE
1∈ =∈∈ Dx iDxDx
6Học Máy – IT 4862
Hồi quy tuyến tính – Giải thuật
„ Việc học hàm mục tiêu f là tương đương với việc học vectơ 
trọng số w sao cho cực tiểu hóa giá trị lỗi huấn luyện E
→ Phương pháp này có tên gọi là “Least-Square Linear Regression”
„ Giai đoạn huấn luyện
• Khởi tạo vectơ trọng số w
• Tính toán giá trị lỗi huấn luyện E
• Cập nhật vectơ trọng số w theo quy tắc delta (delta rule) 
• Lặp lại, cho đến khi hội tụ về một giá trị lỗi nhỏ nhất (cục bộ) E
„ Giai đoạn dự đoán
Đối với một ví dụ mới z, giá trị đầu ra được dự đoán bằng:
∑+= n ii zwwzf 0 **)( Trong đó w*=(w*0,w*1,..., w*n)là vectơ trọng số đã học được=i 1 
7Học Máy – IT 4862
Quy tắc delta
„ Để cập nhật vectơ trọng số w theo hướng giúp giảm bớt 
giá trị lỗi huấn luyện E 
• η là tốc độ học (là một hằng số dương)
→ Xác định mức độ thay đổi đối với các giá trị trọng số tại mỗi bước học
• Cập nhật theo từng ví dụ (Instance-to-instance/incremental update): 
wi ← wi + η(cx-yx)xi
( )∑• Cập nhật theo đợt (Batch update):
„ Các tên gọi khác của quy tắc delta
i
Dx
xxii xycww
∈
−+← η
• LMS (least mean square) rule
• Adaline rule
• Widrow Hoff rule- 
8Học Máy – IT 4862
LSLR_batch(D, η)
for each thuộc tính fi
wi← giá trị (nhỏ) được khởi tạo ngẫu nhiên
while not CONVERGENCE 
for each thuộc tính fi
delta_wi← 0
for each ví dụ học x∈D
Tính toán giá trị đầu ra thực tế yx
for each thuộc tính fi 
delta_wi← delta_wi + η(cx-yx)xi
for each thuộc tính fi
wi ← wi + delta_wi
end while
return w
9
Học Máy – IT 4862
Cập nhật theo đợt/theo từng ví dụ
„ Giải thuật trên tuân theo chiến lược cập nhật theo đợt
„ Cập nhật theo đợt (Batch update)
• Tại mỗi bước học, các giá trị trọng số được cập nhật sau khi tất 
cả các ví dụ học được đưa vào (được học bởi) hệ thống 
- Giá trị lỗi được tính tích lũy đối với tất cả các ví dụ học
- Các giá trị trọng số được cập nhật theo giá trị lỗi tích lũy tổng thể
„ Cập nhật theo từng ví dụ (Instance-to-instance/ 
incremental update)
T i ỗi b ớ h á iá t ị t ố đ ậ hật lậ tứ• ạ m ư c ọc, c c g r rọng s ược c p n ngay p c 
sau khi mỗi ví dụ học được đưa vào (được học bởi) hệ thống
- Giá trị lỗi (riêng biệt) được tính cho ví dụ học đưa vào
- Các giá trị trọng số được cập nhật ngay lập tức theo giá trị lỗi này
10Học Máy – IT 4862
LSLR_incremental(D, η)
for each thuộc tính fi
wi← giá trị (nhỏ) được khởi tạo ngẫu nhiên
while not CONVERGENCE
for each ví dụ học x∈D
Tính toán giá trị đầu ra thực tế yx 
for each thuộc tính fi
wi← wi + η(cx-yx)xi
end while
return w
11
Học Máy – IT 4862
Các điều kiện kết thúc học
„ Trong các giải thuật LSLR_batch và 
S i l á t ì h h kết thú khi á điềL LR_ ncrementa , qu r n ọc c c c u 
kiện được chỉ định bởi CONVERGENCE được thỏa mãn
Cá điề kiệ kết thú h th ờ đ đị h hĩ d„ c u n c ọc ư ng ược n ng a ựa 
trên một số tiêu chí đánh giá hiệu năng hệ thống
• Kết thúc, nếu giá trị lỗi nhỏ hơn giá trị ngưỡng
• Kết thúc, nếu giá trị lỗi ở một bước học lớn hơn giá trị lỗi ở bước 
học trước
Kết thú ế khá biệt iữ á iá t ị lỗi ở 2 b ớ h liê• c, n u sự c g a c c g r ư c ọc n 
tiếp nhỏ hơn giá trị ngưỡng
• ...
12Học Máy – IT 4862