Bài giảng Nhập môn trí tuệ nhân tạo

tham s ố cho b ộ phân lo ại. Mô hình phân lo ại sau đó được 
sử d ụng để d ự đoán nhãn cho ví d ụ m ới. Quá trình h ọc th ực ch ất là quá trình xác định d ạng và 
tham s ố c ủa hàm đích, là hàm x ấp x ỉ giá tr ị nhãn phân lo ại. 
 97
Học máy 
 Ph ần này s ẽ trình bày k ỹ thu ật h ọc máy d ựa trên m ột nguyên t ắc khác g ọi là học d ựa trên ví 
dụ (instance-based learning). Khác v ới các ph ươ ng pháp h ọc ở trên, h ọc d ựa trên ví d ụ không t ạo 
ra mô hình hay hàm đích cho d ữ li ệu, thay vào đó, trong quá trình h ọc thu ật toán ch ỉ l ưu l ại t ất c ả 
các m ẫu hu ấn luy ện được cung c ấp. Khi c ần phân lo ại hay ra quy ết đị nh cho ví d ụ m ới, thu ật toán 
tìm nh ững m ẫu hu ấn luy ện t ươ ng t ự và xác định nhãn phân lo ại hay giá tr ị c ủa ví d ụ d ựa trên 
nh ững m ẫu này. 
 Do thu ật toán không làm gì trong quá trình h ọc mà ch ỉ l ưu l ại các m ẫu hu ấn luy ện, ph ươ ng 
pháp h ọc dựa trên ví d ụ còn được g ọi là h ọc l ười (lazy learning) hay h ọc b ằng cách nh ớ 
(memory-based learning). H ọc d ựa trên ví d ụ bao g ồm m ột s ố k ỹ thu ật h ọc khác nhau nh ư thu ật 
toán k-hàng xóm g ần nh ất (k-nearest neighbor), suy di ễn theo tr ường h ợp (case-based reasoning). 
Điểm khác nhau c ơ b ản gi ữa nh ứng k ỹ thu ật này là cách bi ểu di ễn và tính độ t ươ ng t ự gi ữa các ví 
dụ. Thu ật toán k-hàng xóm g ần nh ất s ử d ụng cách bi ểu di ễn ví d ụ đơn gi ản d ưới d ạng vec t ơ 
trong không gian Ơclit và s ử d ụng kho ảng cách Ơclit để tính độ t ươ ng t ự, trong khi suy di ễn theo 
tr ường h ợp d ựa trên vi ệc bi ểu di ễn các m ẫu (g ọi là tr ường h ợp) ph ức t ạp h ơn và dùng nh ững k ỹ 
thu ật ph ức t ạp được xây d ựng riêng để tính độ t ươ ng t ự cho các tr ường h ợp. 
 Ưu điểm. So v ới ph ươ ng pháp h ọc d ựa trên mô hình, h ọc d ựa trên ví d ụ có m ột s ố ưu điểm. 
Th ứ nh ất, do không quy đị nh tr ước mô hình hay d ạng c ủa hàm đích, h ọc d ựa trên ví d ụ có th ể xây 
dựng nh ững hàm đích r ất ph ức t ạp. Th ứ hai, thay vì xây d ựng hàm đích chung cho toàn b ộ d ữ 
li ệu, h ọc d ựa trên ví d ụ xây d ựng hàm đích d ựa trên m ột s ố m ẫu g ần v ới ví d ụ đang c ần d ự đoán, 
do v ậy có th ể t ận d ụng được đặ c điểm mang tính c ục b ộ c ủa d ữ li ệu để mô t ả t ốt h ơn giá tr ị ví d ụ 
mới. 
 Nh ược điểm. Nh ược điểm th ứ nh ất c ủa h ọc d ựa trên ví d ụ là t ốc độ ch ậm trong giai đoạn 
phân lo ại. Do thu ật toán ph ải so sánh ví d ụ m ới v ới toàn b ộ t ập m ẫu để tìm ra nh ững m ẫu t ươ ng 
tự nên th ời gian phân lo ại t ỷ l ệ thu ận v ới kích th ước t ập m ẫu. Để kh ắc ph ục v ấn đề t ốc độ , cách 
thông d ụng nh ất là s ử d ụng k ỹ thu ật đánh ch ỉ s ố để tìm ki ếm nhanh m ẫu t ươ ng t ự. Nh ược điểm 
th ứ hai c ủa h ọc d ựa trên ví d ụ là vi ệc tính độ t ươ ng t ự được th ực hi ện v ới toàn b ộ thu ộc tính. N ếu 
thu ộc tính không liên quan t ới phân lo ại c ủa ví d ụ thì khi s ử d ụng s ẽ gây nhi ễu, khi ến nh ững ví 
dụ cùng nhãn không t ươ ng t ự v ới nhau. V ấn đề ch ọn và s ử d ụng nh ững thu ộc tính t ốt, do v ậy, có 
ảnh h ưởng quy ết đị nh t ới độ chính xác c ủa ph ươ ng pháp này. 
5.4.2. Ph ươ ng pháp k-hàng xóm g ần nh ất 
 K-hàng xóm g ần nh ất (k-nearest neighbors, vi ết t ắt là k-NN) là ph ươ ng pháp tiêu bi ểu nh ất 
của h ọc d ựa trên ví d ụ. Nguyên t ắc c ủa ph ươ ng pháp này là đặc điểm c ủa m ẫu được quy ết đị nh 
dựa trên đặc điểm c ủa k mẫu gi ống m ẫu đang xét nh ất. Ví d ụ, mu ốn xác đị nh nhãn phân lo ại, ta 
tìm k mẫu g ần nh ất và xem nh ững m ẫu này mang nhãn gì. 
 Ph ươ ng pháp k-NN th ường làm vi ệc v ới d ữ liệu trong đó các thu ộc tính được cho d ưới 
dạng vec t ơ các s ố th ực. Nh ư v ậy, m ỗi m ẫu t ươ ng ứng v ới m ột điểm trong không gian Ơ clit. Gi ả 
sử m ẫu x có giá tr ị thu ộc tính là . Để xác đị nh các m ẫu gi ống x, c ần có độ 
 98
Học máy 
đo kho ảng cách gi ữa các m ẫu. Do m ẫu t ươ ng ứng v ới điểm trong không gian, kho ảng cách Ơ clit 
th ường được dùng cho m ục đích này. Kho ảng cách Ơ clit gi ữa hai m ẫu xi và xj được tính nh ư sau: 
 n 2
 d (xi, xj) = ∑l=1(al (xi ) − al (x j )) 
 Với kho ảng cách d (xi, xj) v ừa được đị nh ngh ĩa, ph ươ ng pháp k-NN cho hai tr ường h ợp: 
phân lo ại và h ồi quy (regression) được th ực hi ện nh ư sau. 
 Phân lo ại 
 Mỗi m ẫu x có th ể nhãn phân lo ại f(x) v ới f(x) nh ận m ột giá tr ị trong t ập h ữu h ạn các phân 
lo ại C. Thu ật toán k-NN cho phân lo ại được cho trên hình 5.5. 
 Giai đoạn h ọc (hu ấn luy ện) 
 Lưu các m ẫu hu ấn luy ện có d ạng vào c ơ s ở d ữ li ệu 
 Giai đoạn phân lo ại 
 Đầu vào: tham s ố k 
 Với m ẫu x c ần phân lo ại: 
 1. Tính kho ảng cách d (x, xi) t ừ x tới t ất c ả m ẫu xi trong c ơ s ở d ữ li ệu 
 2. Tìm k mẫu có d (x, xi) nh ỏ nh ất, gi ả s ử k mẫu đó là x1, x2, , xk. 
 3. Xác định nhãn phân lo ại f’(x) là nhãn chi ếm đa s ố trong t ập { x1, 
 x2, , xk.} 
 Hình 5.5. Thu ật toán k-NN cho bài toán phân lo ại 
 Hồi quy (regression) 
 Mỗi m ẫu x có th ể nhãn phân lo ại f(x) v ới f(x) là m ột s ố th ực. Thu ật toán k-NN ở trên có th ể 
thay đổi d ễ dàng cho bài toán h ồi quy này b ằng cách thay b ước đánh s ố 3 trong thu ật toán hình 
4.3 nh ư sau: 
 k
 ∑ f (xi )
 f ('x) = i=1 
 k
 Thu ật toán k-NN có m ột tham s ố đầ u vào là k: s ố hàng xóm được dùng để quy ết đị nh nhãn 
cho m ẫu đang xét. N ếu k = 1, giá tr ị hàm f ’( x) được ch ọn b ằng giá tr ị hàm f của m ẫu g ần nh ất. 
Thông th ường k = 1 không cho k ết qu ả t ốt do hàng xóm g ần nh ất có ảnh h ưởng quy ết đị nh t ới giá 
tr ị f ’( x). Trong tr ường h ợp hàng xóm g ần nh ất là nhi ễu s ẽ khi ến k ết qu ả b ị sai. Nhi ều nghiên c ứu 
cho th ấy giá tr ị k trong kho ảng t ừ 5 đế n 10 là phù h ợp. Để xác đị nh giá tr ị c ụ th ể c ủa k có th ể s ử 
dụng ph ươ ng pháp ki ểm tra chéo nh ư đã trình bày ở ph ần t ỉa cây. Giá tr ị k cho độ chính xác khi 
ki ểm tra chéo t ốt nh ất s ẽ được l ựa ch ọn cho thu ật toán. 
5.4.3. Một s ố l ưu ý v ới thu ật toán k-NN 
 a) Các độ đo kho ảng cách và độ t ươ ng t ự 
 99
Học máy 
 Kho ảng cách Ơ clit là độ đo thông d ụng để tính kho ảng cách gi ữa các ví d ụ. Bên c ạnh đó 
có th ể s ử d ụng nh ững độ đo khác. 
 - Kho ảng cách Mahalanobis . Kho ảng cách Mahalanobis cho phép tính độ t ươ ng 
 quan gi ữa các thu ộc tính và được s ử d ụng trong tr ường h ợp các thu ộc tính được 
 bi ểu di ễn theo nh ững thang khác nhau, ch ẳng h ạn khi hai thu ộc tính là chi ều cao 
 và cân n ặng. Trong tr ường h ợp đó, kho ảng cách Mahalanobis cho phép chu ẩn hóa 
 kho ảng cách, cân b ằng đóng góp c ủa hai thu ộc tính. 
 - Kho ảng cách Hamming . Kho ảng cách Ơ clit không th ể s ử d ụng được n ếu thu ộc 
 tính nh ận giá tr ị r ời r ạc. Trong tr ường h ợp này có th ế s ử d ụng kho ảng cách 
 Hamming, được tính b ằng s ố thu ộc tính có giá tr ị khác nhau. 
 b) S ử d ụng tr ọng s ố cho các hàng xóm 
 Theo thu ật toán k-NN trình bày ở trên cho bài toán h ồi quy, m ỗi hàng xóm có đóng góp 
nh ư nhau vào giá tr ị c ủa ví d ụ m ới. Tuy nhiên, s ẽ h ợp lý h ơn n ếu cho phép nh ững hàng xóm ở 
gần có ảnh h ưởng nhi ều h ơn t ới giá tr ị d ự đoán. Có th ể th ực hi ện điều này b ằng cách nhân giá tr ị 
hàng xóm v ới tr ọng s ố, tr ọng s ố càng l ớn n ếu hàng xóm ở càng g ần ví d ụ c ần d ự đoán. Ví d ụ, 
tr ọng s ố có th ể tính b ằng ngh ịch đả o c ủa bình ph ươ ng kho ảng cách t ới ví d ụ c ần d ự đoán, t ức là: 
 1
 wi = 2 
 d(x, xi )
 Thêm tr ọng s ố vào công th ức h ồi quy, giá tr ị hàm f ‘( x) c ủa ví d ụ x được tính nh ư sau: 
 k
 ∑ wi f (xi )
 i=1
 f ('x) = k 
 ∑ wi
 i=1
 Trong tr ường h ợp này, m ẫu s ố là t ổng tr ọng s ố và cho phép chu ẩn hóa độ đóng góp c ủa 
từng hàng xóm. 
 Với vi ệc s ử d ụng tr ọng s ố, có th ể không c ần gi ới h ạn s ố l ượng hàng xóm do nh ững ví d ụ ở 
càng xa s ẽ có ảnh h ưởng càng nh ỏ t ới giá tr ị hàm đích c ủa ví d ụ m ới. Tuy nhiên, vi ệc không gi ới 
hạn s ố l ượng hàng xóm đòi h ỏi tính toán nhi ều và do v ậy t ốc độ c ủa thu ật toán s ẽ b ị ảnh h ưởng. 
 c) Ảnh h ưởng c ủa thu ộc tính t ới thu ật toán 
 Để tính kho ảng cách, k-NN s ử d ụng toàn b ộ thu ộc tính c ủa ví d ụ, b ất k ể thu ộc tính có liên 
quan t ới nhãn phân lo ại c ủa ví d ụ hay không. Đây là điểm khác v ới ph ươ ng pháp h ọc cây quy ết 
định, trong đó ch ỉ nh ững thu ộc tính liên quan được ch ọn trên các nút, hay ph ươ ng pháp Bayes 
đơ n gi ản, trong đó ch ỉ nh ững thu ộc tính liên quan m ới có xác su ất điều ki ện cao. N ếu d ữ li ệu bao 
gồm c ả nh ững thu ộc tính không liên quan t ới nhãn phân lo ại, nh ững thu ộc tính này s ẽ ảnh h ưởng 
tới kho ảng cách. Ví d ụ, gi ả s ử d ữ li ệu có 100 thu ộc tính, trong đó ch ỉ có 2 thu ộc tính có ảnh 
hưởng t ới nhãn phân lo ại. Khi đó nh ững ví d ụ có hai thu ộc tính này gi ống nhau v ẫn có th ể n ằm 
rất xa nhau trong không gian 100 chi ều. 
 Ảnh h ưởng c ủa s ố l ượng thu ộc tính l ớn và không liên quan làm gi ảm đáng k ể độ chính xác 
của k-NN. Để gi ải quy ết v ấn đề này có th ể s ử d ụng hai ph ươ ng pháp: 
 100
Học máy 
 - Đánh tr ọng s ố cho thu ộc tính sao cho thu ộc tính ít liên quan có tr ọng s ố nh ỏ và 
 ng ược l ại. 
 - Lựa ch ọn thu ộc tính (hay còn g ọi là trích ch ọn đặ c tr ưng): ch ỉ nh ững thu ộc tính 
 liên quan được gi ữ l ại, trong khi nh ững thu ộc tính không liên quan b ị b ỏ đi. Đây là 
 tr ường h ợp riêng ph ươ ng pháp đánh tr ọng s ố cho thu ộc tính, trong đó nh ững thu ộc 
 tính b ị lo ại có tr ọng s ố b ằng không. 
 Có r ất nhi ều nghiên c ứu đề c ập t ới vi ệc l ựa ch ọn và đánh tr ọng s ố cho thu ộc tính. Do gi ới 
hạn c ủa môn h ọc, các n ội dung này s ẽ không được đề c ập t ới ở đây. 
5.5. SƠ L ƯỢC V Ề MỘT S Ố PH ƯƠ NG PHÁP H ỌC MÁY KHÁC 
 Ngoài ba ph ươ ng pháp h ọc máy dùng cho phân lo ại được trình bày ở trên, r ất nhi ều ph ươ ng 
pháp học máy khác đã được phát tri ển và s ử d ụng trong nhi ều ứng d ụng khác nhau. Sau đây là 
gi ới thi ệu s ơ l ược v ề m ột s ố ph ươ ng pháp được ứng d ụng nhi ều ho ặc và độ chính xác t ốt. 
 Mạng n ơ ron nhân t ạo 
 Mạng n ơ ron nhân t ạo d ựa trên nguyên lý h ệ th ống th ần kinh (n ơ ron) c ủa ng ười và động 
vật b ậc cao, trong đó sử d ụng nhi ều nút được n ối v ới nhau thành m ột m ạng l ưới. Tín hi ệu được 
truy ền t ừ nút n ọ sang nút kia tùy thu ộc m ức tín hi ệu và c ơ ch ế x ử lý t ại m ỗi nút. 
 Trên hình sau là m ột ví d ụ t ổ ch ức m ạng n ơ ron trong đó m ột s ố nút nh ận tín hi ệu t ừ ngoài 
vào, m ột s ố nút tr ả tín hi ệu ra ngoài, các nút có th ể truy ền tín hi ệu t ới nh ững nút khác. 
 Tại m ỗi nút có m ột hàm cho phép tr ả ra k ết qu ả theo tín hi ệu đầ u vào. Nh ờ vi ệc s ử d ụng 
nhi ều nút v ới nh ững hàm x ử lý riêng t ại t ừng nút, m ạng n ơ ron cho phép xây d ựng nh ững hàm 
đích r ất ph ức t ạp để ánh x ạ t ừ tín hi ệu đầ u vào thành k ết qu ả đầ u ra. 
 Quá trình h ọc m ạng n ơ ron là quá trình hi ệu ch ỉnh tham s ố c ủa hàm x ử lý t ại các nút sao 
cho ánh x ạ đầ u vào sang đầu ra phù h ợp nh ất v ới d ữ li ệu hu ấn luy ện. 
 Mạng n ơ ron nhân t ạo là ph ươ ng pháp h ọc máy được phát tri ển t ừ s ớm, có th ể dùng cho 
phân lo ại ho ặc h ồi quy v ới độ chính xác cao, đã và đang được s ử d ụng trong r ất nhi ều ứng d ụng 
khác nhau. 
 Support vector machines (SVM) 
 101
Học máy 
 Support vector machines (SVM) (m ột s ố tài li ệu d ịch là máy vec t ơ t ựa) là k ỹ thu ật h ọc 
máy được phát tri ển và nghiên c ứu g ần đây (t ừ n ăm 1995). SVM được xây d ựng cho bài toán 
phân lo ại nh ị phân, t ức là m ỗi ví d ụ có th ể nh ận m ột trong hai nhãn. Các ví d ụ ph ải được bi ểu 
di ễn b ằng thu ộc tính liên t ục, và do v ậy m ỗi ví d ụ t ươ ng ứng v ới m ột vec t ơ trong không gian 
(t ươ ng t ự tr ường h ợp k-NN). 
 SVM d ựa trên hai nguyên t ắc chính 
 - SVM tìm cách phân chia ví d ụ có nhãn khác nhau b ằng m ột siêu ph ẳng sao cho 
 kho ảng cách t ừ siêu ph ẳng t ới nh ững ví d ụ có nhãn khác nhau là l ớn nh ất. Nguyên 
 tắc này được g ọi là nguyên t ắc lề c ực đạ i (max margin). Trong quá trình hu ấn 
 luy ện, thu ật toán SVM xác đị nh siêu ph ẳng có l ề c ực đạ i b ằng cách gi ải bài toán 
 tối ưu cho m ột hàm m ục tiêu b ậc 2. 
 - Để gi ải quy ết tr ường h ợp các ví d ụ không th ể phân chia b ằng m ột siêu ph ẳng, 
 ph ươ ng pháp SVM s ẽ ánh x ạ không gian ban đầ u c ủa các ví d ụ sang m ột không 
 gian khác th ường là có s ố chi ều cao h ơn, sau đó tìm siêu ph ẳng v ới l ề c ực đạ i 
 trong không gian này. Để tăng tính hi ệu qu ả khi ánh x ạ, m ột k ỹ thu ật được s ử 
 dụng là k ỹ thu ật dùng hàm nhân (kernel function) thay cho tích có h ướng c ủa các 
 vec t ơ. 
 Trong tr ường h ợp phân lo ại v ới nhi ều nhãn, cách th ường dùng là k ết h ợp nhi ều SVM nh ị 
phân v ới nhau. 
 SVM có nhi ều ưu điểm: 
 - Đây là ph ươ ng pháp có c ơ s ở lý thuy ết t ốt d ựa trên lý thuy ết v ề kh ả n ăng khái quát 
 hóa c ủa b ộ phân lo ại. 
 - Có th ể làm vi ệc t ốt v ới d ữ li ệu nhi ều chi ều (nhi ều thu ộc tính). 
 - Cho k ết qu ả r ất chính xác so v ới các ph ươ ng pháp khác trong h ầu h ết ứng d ụng. 
 Boosting 
 Khác v ới nh ững ph ươ ng pháp trình bày ở trên, boosting là m ột d ạng meta learning, t ức là 
làm vi ệc d ựa trên nh ững ph ươ ng pháp h ọc khác. Để gi ải quy ết bài toán phân lo ại, boosting k ết 
hợp nhi ều b ộ phân lo ại đơn gi ản v ới nhau để t ạo ra m ột b ộ phân lo ại có độ chính xác cao hơn. 
 Ví d ụ, ta có th ể xây d ựng b ộ phân lo ại đơn gi ản b ằng cách s ử d ụng cây quy ết đị nh ch ỉ có 
một nút – nút g ốc, còn được g ọi là g ốc cây quy ết đị nh. Cây quy ết đị nh nh ư v ậy s ẽ có độ chính 
xác không cao. Thu ật toán boosting khi đó k ết h ợp các g ốc cây nh ư sau: 
 - Mỗi ví d ụ hu ấn luy ện được gán m ột tr ọng s ố, đầ u tiên tr ọng s ố b ằng nhau. 
 - Thu ật toán l ặp l ại nhi ều vòng 
  Tại m ỗi vòng, l ựa ch ọn m ột g ốc cây có độ chính xác t ốt nh ất. G ốc cây chính xác 
 nh ất là g ốc cây có l ỗi nh ỏ nh ất v ới lỗi tính b ằng t ổng tr ọng s ố nh ững ví dụ b ị phân 
 lo ại sai. 
 102
Học máy 
  Nh ững ví d ụ b ị phân lo ại sai được t ăng tr ọng s ố trong khi nh ững ví d ụ đúng b ị 
 gi ảm tr ọng s ố. Nh ờ vi ệc thay đổ i tr ọng s ố nh ư v ậy, thu ật toán s ẽ chú ý nhi ều h ơn 
 tới ví d ụ b ị phân lo ại sai trong nh ững vòng sau. 
 - Bộ phân lo ại cu ối được t ạo ra b ằng t ổng các cây quy ết đị nh xây d ựng t ại m ỗi vòng l ặp. 
 Thu ật toán boosting có m ột s ố ưu điểm nh ư: 
 - Độ chính xác cao. 
 - Ít b ị ảnh h ưởng b ởi hi ện t ượng quá v ừa d ữ li ệu. 
 - Có th ể s ử d ụng v ới nhi ều ph ươ ng pháp phân lo ại đơn gi ản khác nhau. 
 103
Học máy 
 TÀI LI ỆU THAM KH ẢO 
1. S. Russell, P. Norvig. Artificial intelligence: a modern approach. 2nd edition. Prentice Hall. 
 2003. 
2. Tim M. Jones. Artificial intelligence a system approach. Infinity science press. 2008. 
3. Đinh M ạnh T ường. Trí tu ệ nhân t ạo. Nhà xu ất b ản Khoa h ọc k ỹ thu ật. 2002. 
4. Nguy ễn Thanh Th ủy. Trí tu ệ nhân t ạo. Nhà xu ất b ản khoa h ọc k ỹ thu ật 1999. 
5. T. Mitchell. Machine learning. McGrawhill. 1997. 
6. Đỗ Trung Tu ấn. Trí tu ệ nhân t ạo. Nhà xu ất b ản Giáo d ục 1998. 
 104