Tài liệu Một số kỹ thuật vector tựa (SVM) trong khai phá dữ liệu và ứng dụng vào nhận dạng

x: ờ ơ ỉ d ạ i h ọ c ọ u ó c g ia h à n ộ i TRƯỜNG ĐAI « HOC CÔNG NGHÊ * • NGUYỀN HOÀI NAM MỘT SỐ KỸ THUẬT VECTOR TỤA (SVM) TRONG KHAI PHÁ D ữ LIÊU VÀ ỨNG DƯNG VÀO NHẢN DANG • • 0 ề Ngành : Công nghệ thông tin Chuyên ngành : Hệ thống Thông tin Mằ sổ : 60 48 05 LUẬN VĂN THẠC s ĩ NGƯỜI HƯỚNG DẢN KHOA HỌC : PGS.TSKH. Bùi Công Cường ■JAi HỌC QUỐC GIA HÀ NÔI ; rung tâm thO ng tin thư viện 1 Vr LOẬ . . A S A L Hà Nội - 2008 _ 3 MỤC LỤC LỜI CAM Đ O A N ........................................................................................................1 LỜI CẢM Ơ N ............................................................................................................. 2 C Á C TỪ V I Ế T T Ắ T , T H U Ậ T N G Ữ .............................................................................. 6 C Á C HÌN H V Ẽ ........................................................................................................................6 CHƯƠNG 1 : MỘT 1.1 SỐ KIẾN THÚC CHUẨN B Ị ......................................... 10 Bài toán tối ưu.............................................................................10 1.1.1 Bài toán qui hoạch tuyến tín h .................................................................10 /. ỉ. ỉ. ỉ Dạng chính tắc......................................................................... 1Ị Ị. ỉ. ỉ.2 Dạng chaân tắc........................................................................ / / 1.1.2 Qui hoạch tuyến tính đổi ngẫu................................................................ 12 1.2 Biểu diễn dữ liệu............................................................................ 14 1.2.1 Dữ liệu huấn luyện.......................................................................................... 14 1.2.2 Không gian hữu hạn chiều...................................................................... 14 1.2.3 Một thuật toán nhận dạng mẫu đơn g iả n .............................................. 15 1.2.4 Một số khái niệm trong lý thuyết học thổng k ê ................................... 18 1.2.4. ỉ Không gian v c ...........................................................................19 1.2.4.2 Mối liên hệ giữa lý thuvểt học thống kê và SVM .................. 20 1.3 Phưoìig pháp phân tích thành phần chính (PCA).....................................20 1.3.1 Đ ộ lệch c h u ẩ n ........................................................................................................ 20 1.3.2 Phương sai..................................................................................................21 1.3.3 Vector riêng, giá trị riêng........................................................................22 1.3.4 Phương pháp phân tích thành phần chính............................................ 23 4 CHƯƠNG 2 : KHAI PHÁ DỮ LIỆU VÀ HỌC MÁY..................................... 28 2.1 Khái niêm hoc.................................................................................28 • • 2.1.1 Qúa trình học............................................................................................. 28 2.2 Máy h ọ c ................................................................................................................29 2.2.1 Quy trình của máy học.............................................................................30 2.2.1.1 Học có thày.................................................................................30 2.2.1.2 Học không có th à y..................................................................... 31 2.2. ỉ .3 Học có thày một phần ................................................................S ỉ 2.3 Khai phá dữ liệu.................................................................................................32 2.3.1 Cấu trúc của một hệ thống khai phádừ liệu........................................32 2.3. ỉ. ì X ử lý dữ liệu................................................................................. 32 2.3.2 Các bài toán chính trong khai phá dữ liệu............................................33 2.3.2.1 Phân lớp và phán cụm ...............................................................33 23 .2 .2 Tim ra các luật............................................................................34 2.3.3 Một số phương pháp tính dùng trong khaiphá dừ liệu..........................35 2.4 Sự giống và khác nhau giữa khai phádữ liệu và máy học..........................35 C H U ONG 3 ............................................................................................................................36 HÀM HẠT N H Â N ............................................................................................................ 36 3.1 Tích vô hướng các đặc trưng........................................................................... 36 3.1.1 Đặc trưng đơn............................................................................................36 3.1.2 H àm h ạ t n h â n .........................................................................................................37 3.1.3 Hàm hạt nhân đa th ứ c..............................................................................37 3.2 Biểu diễn sự đồng dạng trong không gian tuyếntính............................39 3.2.1 Các hạt nhân xác định dương..................................................................39 3.2.2 Tái lập ánh xạ hạt nhân........................................................................... 40 3.2.3 Tái lập không gian hạt nhân H ilbert..................................................... 42 3.2.4 Ánh xạ hạt nhân Mercer.......................................................................... 43 3.3 Các hạt nhân thưòng đưọc sử dụng..................................................45 5 C H Ư Ơ N G 4 .................................................................................................................. 46 P H Ư Ơ N G PHÁP V E C T O R TỰA (SVM).............................................................46 4.1 Phân chia bằng siêu phắng.............. .................................................................. 46 4.2 Vai trò cùa lề trong siêu phẳng......................................................................... 47 4.3 Siêu phẳng tối ưu - Phân lóp tuyến tín h ............ .... .......................................49 4.3.1 Đánh giá lỗi.............................................................................................. 50 4.3.2 Bài toán qui hoặch toàn phươne của tìm lề phân lớp tối ưu.............. 51 4.4 Phân lóp phi tuyến bằng vector t ự a ................................................................ 51 4.5 Siêu phẳng vói lề m ề m ........................................................................................54 4.6 Phấn lóp trong truòìig họp có nhiều l ớ p ....................................................... 60 4.6.1 Chiến lược Một-đỐi-Phần còn lại (One Versus the Rest)................... 60 4.6.2 Chiến lược so sánh theo cặp (hay còn gọi làmột đối m ộ t)................ 61 CHƯONG 5 : MỘT SÓ ỦNG DỤNG CỦA KỲ THUẬT VECTOR TựA .62 5.1 Phấn loai văn b ả n .................................................................................................62 ■ 5.2 Nhận dạng ả n h ...................................................................................................... 64 5.2.1 Phân lớp độc lập.......................................................................................64 5.2.2 Phân lớp với ảnh màu.............................................................................. 65 5.3 Nhận dạng chữ số viết tay................................................................................66 5.4 Tin-sinh học (Bio-lnformatỉcs)..........................................................................67 5.4.1 Phát hiện protein tương đồng...,.............................................................67 CHƯƠNG 6 : CÀI Đ ẬT THỬ NGHIỆ # * M .......................................................... ....69 6.1 Nhận dạng ảnh khuôn m ặt ngư ờ i.................................................................... 69 6.1.1 Xây dựng không gian đặc trưng.............................................................70 6.1.2 Huấn luyện và nhận dạng........................................................................72 6.2 Xây dựng hệ thống nhận dạng....................................................................... 74 KÉT LUẬN............................................................................................................... 76 TÀI LIỆU TH AM K H Ả O ........................................................................................77 6 CÁ C TỪ VIẾT TẮT, THUẬT NGŨ (ORL Cambridge Olivetti Research Lab PCA Principal Components Analysis 1RBF Radial Basic Function SVM Support Vector Machines vc Vapnik Chervonenkis CÁC HÌNH VẼ Hình 1.1 Phân lớp trong đơn giản............................................................................. 17 Hình 1.2 : Hai hàm huấn luyện cho kết quả khác nhau trên dữ liệu kiểm tra...... 18 Hình : 1.3 v c của các đường thẳng có hướng......................................................... 20 trong không gian 2 chiều (R2) là 3.............................................................................. 20 Hình 1.4 Ý nghĩa hình học của PC A .......................................................................... 27 Hình 2.1 : Sơ đồ của Bloom........................................................................................ 29 Hình 2.2 : Thuật toán học có thày : Cây quyết định, Mạng nơron, Vector tựa ..31 Hình 2.3 : Thuật toán học không có thày : Phân cụm ..............................................31 Hình 3.1 Ví dụ về phân lớp nhị phân khi ánh xạ sang không gian đặc trưng.....38 Hình 3.2 Minh hoạ mối liên hệ giữa ánh xạ đặc trưng với hạt nhân.....................40 Hình 4.1 Một siêu phẳng phân lớp các đối tượng thành hai lớp............................46 Hình 4.2 Siêu phẳng dạng chính tắc........................................................................... 47 Hình 4.3 Vỉ dụ phân lớp trong không gian 2 chiều..................................................48 Hình 4.4 : Ví dụ : Bằng cách ánh xạ không gian dữ liệu phi tuyến đầu v à o .......52 Hình 4.5 : Ví dụ về SVMs trong không gian phi tu y ế n ..........................................53 Hình 4.6 : P-SVC với V = 0.1 (trên-trái)đến V = 0.8 (dưới-phải)....................57 Hình 6.1 : Ảnh của một người trong dữ liệu ảnh O R L ........................................... 71 Hình 6.2 Phân lớp sử dụng cây phân lớp nhị p h â n ..................................................73 Hình 6.3 Phân nhiều lớp với sổ lớp là 4 ....................................................................73 Hình 6.4 Các dữ liệu huấn luyện................................................................................ 74 Hình 6.5 : Dừ liệu kiếm tra và các kết nhận dạng....................................................75 7 MỞ ĐẦU Trong thời gian gần đây, công nghệ thông tin đã góp phần quan trọng vào sự phát triển kinh tế, giáo dục và làm thav đổi xã hội, tạo ra những khái niệm, quan niệm mới trong nhiều lĩnh vực, tác động đến tất cả các cá nhân, tổ chức trong xã hội. Công nghệ thông tin đà làm xoá mờ khoảng cách về địa lý, giúp con người ờ khắp nơi trên thế giới, ở tất cả các nền văn hoá có thế dễ dàng trao đổi, chia sẻ thông tin. Chính vì nhừng tiện ích vô cùng thân thiện cùa nó nên cộng đồng tham gia vào việc sử dụng, phát triển công nghệ thông tin là rất rộng lớn, không kể tuổi tác, nahề nghiệp, tôn giáo, vùng miền,...Chúng ta đã được chứng kiến sự phát triên nhir vũ bão của công nghệ thông tin trong nhừng năm vừa qua, từ bộ vi xử lý tới các hệ thổna lưu trữ cũng đã phải phát triển nhanh chóng đế đáp ứng được khối lượng thông tin khổng lồ; các thông tin này không nằm một chỗ mà nó luôn được luân chuyển, bổ sung, cập nhật bởi người sử dụng. Với khối lượng thông tin lớn đến như vậy, liệu con người chúng ta có cảm thấy quá tái, ngập chìm trong biên thông tin, không thế chọn lựa được những thông tin quan trọng, gần với nhu cầu sử dụng của minh nhất. Điều đó có nghĩa là chúng ta có quá nhiều thông tin, nhưng điều chúng ta thực sự cần đó là tri thức,là kiến thức có được qua sự tổng hợp, phân tích, thống kê từ các kho thông tin đó. Đe tìm ra được tri thức trong một kho thông tin khổng lồ thì chúng ta cần phải có các phương pháp khái phá các lượng thông tin đó. Cùng chính vì lý do đó mà trong thời gian gần đây, nghành khai phá dừ liệu được rất nhiều người quan tâm và nghiên cứu. Trong luận vãn tốt nghiệp cao học tại trường Đại học công nghệ - Đại học quốc gia Hà Nội, tôi thực hiện đề tài “Một sổ kỹ th u ậ t vector tựa (SVM) trong khai phá dữ liệu và ứng dụng vào nhận dạng” • Lý do chọn đề tài Trong khai phá dừ liệu và học máy, yếu tố quyết định đến độ chính xác trong các dự đoán là khả năng phân lớp tốt. Kỹ thuật vector tựa được đánh giá là có khả năng phân lớp rất tốt, đặc biệt là các bài toán phân lớp phi tuyến. Hiện nay đã có nhiều ứng dụng được xây dựng dựa trên kỹ thuật vector tựa và cho kết quả rất khả quan. • Mục đích, đổi tư ợ n g , phạm vi nghiên cứu 8 Nghiên cứu phần cơ sở, lý thuvết chung của kv thuật vector tựa, nghiên cứu một sổ kỹ thuật vector tựa cụ thể. Nghiên cửu các phương pháp sử dụng kv thuật vector tựa trong nhận dạng mẫu, đặc biệt là nhận dạng khuôn mặt. Đưa ra các giải pháp nhàm tăng cường tốc độ tính toán, độ chính xác cho phương pháp vector tựa. • Ý nghĩa khoa học và thực tiễn Đây là một trong các phương pháp phân lớp hiện đại, có thể áp dụng cho nhiều bài toán phàn lớp hiện nay. Với giới hạn những đổi tượng, vấn đề tìm hiểu và nghiên cứu như trên, i uận văn bao gồm 6 c h ư ơ n g : C hư ơ ng 1 : Một số kiến thức chuẩn bị Giới thiệu các khái niệm về quy hoạch tuyến tính, lý thuyết học thống kê, và các khái niệm ban đầu về kỹ thuật vector tựa, cũng như mối liên hệ giữa lý thuyết thống kê và kỹ thuật vector tựa. C hu’O'ng 2 : Khai phá d ữ liệu và học máy Trình bày các khái niệm về khai phá dữ liệu và học máy Chương 3 : Hàm hạt nhân Trình bày khái niệm về hàm hạt nhân, trình bày về không gian đặc trưng, trình bày về sử dụng hạt nhân trong kỹ thuật vector tựa. Chương 4 : Phương pháp vector tựa (SVM) Trình bày các nội dung cơ bản của phương pháp vector tựa. Tập trong đi sâu vào các kỹ thuật vector tựa hay được sử dụng hiện nay. C hương 5 : M ột số ứng dụng của SVM Phân tích, xây dựng bài toán nhận dạng khuôn mặt bàng kỹ thuật vector tựa. Lựa chọn phương pháp phân tích thành phần chính (PCA) để trích rút đặc trưng của khuôn mặt, xây dựng cờ sở dữ liệu ảnh mặt để kiểm tra khả năng hoạt động của các kỹ thuật vector tựa. Chương 6 : Cài đ ặ t th ử nghiệm 9 Cài đặt thử nghiệm hệ thống nhận dạng khuôn mặt người để kiểm tra khả năng phân lớp của kỹ thuật vector tựa. Kết luân Đánh giá hiệu quả của phương pháp vector tựa cũng như đưa ra các hướng cài tiến, các ứng dụng có thể áp dụng kỹ thuật vector tựa. 10 CHƯƠNG 1 : MỘT SÓ KIẾN TH ÚC CHUẨN BỊ 1.1 Bài toán tối ưu. Bài toán tối ưu là bài toán tìm nghiệm tối ưu (cho một hàm mục tiêu nào đó) trono, số các phương án (nghiệm) chấp nhận thuộc miền V cho trước. 1.1.1 Bài toán qui hoạch tuyến tính Qui hoạch tuyến tính là một trong những lớp bài toán tối ưu quan trọng nhất vả được ứng dụng rồng rãi trong thực tiền. Qui hoạch tuyến tính là bài toán tìm cực tiểu (hay cực đại) của một hàm tuyến tính f(x) trên một khúc lồi D c Rn được xác định bơi một hệ phương trình hay bất phương trình tuyến tính cho trước. Bài toán này có dạng : Tìm các vector x= (x/, x 2, Z n CịXị —>m in sao cho 7=1 thoá mân các ràng buộc Z / . *—‘j7 = = 11 X'7=1 uClij i j X) x > < bị , i = 1, . . . , 171, > b ị , i = m l + 1 ,..., 771! + m 2, (1.1) ( 1 .2) X—1« y d ụ Xj — bị , i = i — m í + m 2 4 - 1 , £—Jj = 1 Xị > 0 ,7 = l,...,n,Xj < 0,j - 71! + 1, ...,ní + n2 < n (1 .3 ) (1 .4 ) trong đó a;j,bj,Cj là các h ằ n g số cho trước. Trong bài toán trên, f được gọi là hàm mục tiêu, mỗi hệ thức (1.1) - (1.4) được gọi là các ràng buộc. Mồi ràng buộc (1.1) - (1.3) gọi là một ràng buộc chính (dạng đẳng thức hay bất đẳng thức), mồi ràng buộc X j> 0 hay Xj < 0 gọi là một ràng buộc về dấu. Điểm X=(X],X2....xn) c Rn thoá mân mọi ràng buộc của bài toán gọi là một điểm chấp nhận được hay một phương án. Tập hợp tất cả các phương án, ký hiệu là D, gọi là miền ràng buộc hay miền chấp nhận được. Một phương án đạt cực tiểu của hàm mục tiêu gọi là một phương án tối ưu hay một lời giải của bài toán đã cho. Bài toán có ít nhất một phương án tối ưu gọi là bài toán có lời giải. Bài toán không có phươna, án (miền ràng buộc rồng D =0) hoặc có phương án nhưng không có phương án tối ưu, do hàm mục tiêu giám vô hạn (bài toán tìm min) hoặc tăng vô hạn (bài toán tìm max) gọi là bài toán không có lời giải. 11 Các ràng buộc chính của bài toán được sắp xếp theo thứ tự; trước hết là các ràn g bu ộc < rồi đ ến các ràn g buộc > v à sau c ù n g ỉà các ràng buộc = m J là số ràng buộc <, m2 là sổ ràng buộc >, m là tổng số các ràng b u ộ c chính, n là biến số củ a bài toán, nỊ là số ràn g bu ộc Xj > 0, n 2 là số ràng buộc X j< 0 (có thể ri|=0, n2=0). Nếu không có các ràng buộc < thì mj=0, không có các ràng buộc > thì m2, không có ràng buộc = thì m=mi+m2. Với bài toán bất kỳ, bao giờ ta cũng có thế viết các ràng buộc chính ở dạng sao cho mọi bị > 0, i= l,...,m (nếu có bj < 0 ta nhân cả hai vế của ràng buộc i với - 1 , rồi đổi chiều bất đẳng thức và sắp xếp lại thứ tự các ràng buộc chính nếu cần) Người ta thường xét bài toán qui hoạch tuyến tính ở hai dạng sau đây : 1.1.1.1 Dạng chính tắc Z n C ịX ị -» m i n , /=1 l^ r a ijxị = bi> i = 1 , 2 , m, V Xj > 0 , j = 1,2, Ràng buộc chính dạng đẳng thức và mọi biến đều không âm 1.1.1.2 Dạng chuẩn tắc Z n C jX j -> m i n , i =1 I^ l i = 1,2,..., m , CLijXj > bị, Xj > 0 , j = 1,2, Ràng buộc chính dạng bất đẳng thức > (đổi với bài toán min hoặc < đối với bài toán max), và mọi biến đều không âm. Đe viết bài toán gọn hơn, ta dùng các ký hiệu vector và ma trận sau: A = an a 21 a12 ... 0-22• ••• a ĩn a 2n .aml ^m2 Q-mn. • ' ai j ' , A j= Ũ 2j .a m j . 12 ■V ' 0) hay min { f(x)= : Ax = b, X > 0 } max { f(x)= : Ax = b, X > 0 } ( là tích vô hướng của hai vector c và x) Bài toán quy hoạch tuyến tính chuẩn tẳc có dạng (không đòi hỏi b > 0) hay m in { f(x )= < c ,x > : A x > b, X > 0 } m ax { f(x )= < c,x > : A x < b, X > 0 } 1.1.2 Qui hoạch tuyến tính đối ngẫu. Đổi ngẫu là một phương pháp mà ứng với mỗi bài toán qui hoạch tuyến tính đã cho (gọi là bài toán gốc), ta có thể thiết lập một bài toán quy hoạch tuyến tính khác (gọi là bài toán đối ngẫu) sao cho từ lời giải của bài toán này ta có thể thu được thông tin về lời giải của bài toán kia. Vì thế, đôi khi đế có được lời giải của một bài toán tỏ ra khó khăn, thì việc chuvến sang bài toán đối ngẫu giúp ta có được lời giải thuận tiện hơn nhiều. Hơn thế, khi phân tích đồng thời cả hai bài toán gổc và bài toán đổi ngẫu ta có thể rút ra được các kết luận sâu sắc cả về mặt toán học lẫn ý nghĩa thực tiễn. Cho một qui hoạch tuyến tính, kỷ hiệu (P), dưới dạng chuẩn : (P) f(x)=C iX |+c2X2+ . . . + c nx n —» m in với các ràng buộc I aMxi + ai2x2 + ...+ ainxn > bj , i= l,2,...,m I Xj > 0 , j= l,2 ,...,n , 13 trong đó ay, bị, Cj là các hệ số cho trước; x=(xl,x2,...,xn) G Rn là vector biến cần tìm. Ta gọi đổi ngầu của (P) là qui hoạch tuyển tính, bài toán đối ngầu Q có dạng : g(y)=b,yi+b2y2+ ...+ bnyn max với các ràng buộc a ,yj + aj2y 2 + ...+ ainy n 0 ,j= l,2 ,...,m , ■S ở đây y= (yi.y 2v » y n ) e Rn là vector biến cần tìm. Ta có nhận xét : • Các ràng buộc chính trong qui hoạch ban đầu (ta gọi là qui hoạch gốc hay bài toán gốc) tương ứng một - một với các biến trong bài toán đối ngẫu (mà ta sè gọi là các biến đối ngẫu), trong khi các biến trong qui hoạch gốc (biến gốc) sẽ tương ứng một - một với các ràng buộc chính trong bài toán đối ngẫu • Các hệ số ờ vế phải với ràng buộc chính trong bài toán gốc trờ thành các hệ sổ mục tiêu trong bài toán đối ngẫu, còn các hệ số mục tiêu trong bài toán gổc trở thành các hệ số ở vế phải ràng buộc chính trong bài toán đối ngẫu • Bài toán gốc tính min thì bài toán đổi ngẫu tính max (và ngược lại) • Cả hai bài toán (P) và (Q) đều có dạng chuẩn; mọi ràng buộc đều là các bất đẳng thức (> đối với bài toán tìm min, < đối với bài toán tìm max) và mọi biến đều không âm. Dùng ký hiệu vector và ma trận, ta có thể viết : Bài toán gốc f(x)= —> min Ax >b, X > 0. Bài toán đối ngẫu g(y)= —> max ATy < c, y > 0. (A 1 là ma trận chuyển vị của ma trận A, là tích vô hướng của hai vector a và b) 14 1.2 Biểu diễn dữ liêu 1.2.1 Dữ liệu huấn luyện Giả sử ta có các đối tượng được chia thành hai lớp, cho một đổi tượno; mới và ta phải xem đối tượng đó thuộc về lớp nào. Bài toán trên có thể tổng q u át h o á th àn h : ( x 1(y , ) , . . . , ( x m,y m) e X Trong đó X { -1 ,1 } X là tập khác rỗng các mẫu Xj (còn gọi là các đầu vào, mẫu, quan sát), còn y, được gọi là các nhãn, đầu ra. Không mất tính tổng quát ta chỉ xem xét hai giá trị của nhãn là +1 và - 1 , đó là trường hợp nhận dạng mẫu hay phân lớp nhị phân. Khi đó, sau khi huấn luyện qua các dữ liệu huấn luyện ta cỏ thế tồng quát quá cho các dừ liệu chưa gắn nhãn, tức là ta dự đoán X E X thuộc về lớp nào {+1,-1} Với sự chuyển đổi dừ huấn luyện vào đê dự đoán đầu ra trong {+ 1,-1} đã làm cho bài toán trở nên đơn giản hơn nhiều. Do vậy chúng ta cần có các phép biến đồi dừ liệu của tập dừ liệu huấn luyện Xét phép biến đổi k : X X X -» E (.x , x ') *-> /c(x,x') với hai mẫu X v à x ’ qua phép biển đổi ta có sổ thực thể hiện sự liên quan của X và x \ với k là đổi xứng (k(x,x’)= k(x’,x) với mọi x ,x ’G M) thì k được gọi là một hạt nhân. 1.2.2 Không gian hữu hạn chiều Xét li, V 0. Tích trực tiếp của I L v ằ V : X L x V = {(u,v)\u 6 ĩl,v £ V] Trong trường hợp V. — V — IRn, ta xét tích vô hướng của hai vector X = (xv x 2..... xn) Vày = (yv y2, - , y n) < x , y > == là : f > [X [ *ị.y , i i=1 15 v ề mặt hình học, tích vô hướng của hai vector chính là cosine của góc tạo thành của hai vector đó. Dựa vào đó ta có thể tính được chuẩn của vector* theo công thức sau : ||x || = v < x . x > 1.2.3 Không gian đặc trưng Việc chuyển được không gian đặc trưng lên một không gian ơclit giúp ta có được hình dung về mặt hình học cũng như có thể tính được góc, độ dài, khoảng cách. Tuy nhiên, nó cũng đặt ra một số vấn đề sau : • Đe có thể tính toán trong không gian thì ta phải biểu diễn các mẫu dưới dạng vector trong một không gian ĨC qua ánh xạ :

Oi H+ X : = 4>(X) Nếu như mẫu đã nằm trong không gian , thì chúng ta vẫn muốn tìm kiếm cách đối sánh tổng quát hơn bằng phép ánh xạ o Trong cả hai trường hợp trên, ta đều gọi K là không gian đặc trưng, X là vector trong không gian đặc trưng, biểu diễn cho X. Qua cách đưa dữ liệu vào không gian đặc trưng qua chúng ta được : • Có cách thức so sánh trong không gian tích của J-C k(x,x')-< • 4>(x), 4>(x') > (1.5) Ta có thế có các biểu diễn hình học, sử dụng đại số tuyến tính và giải tích hình học để giải quyết bài toán máy học. • Có nhiều cách để chọn ánh xạ 4> nên có nhiều cách so sánh. 1.2.3 Một thuật toán nhận dạng mẫu đơn giản Giả sử, dữ liệu của chúng nằm trong không gian tích K , do đó chúng ta có thể tính được các khoảng cách trong không gian đó, ý tưởng chính của thuật toán là gán một mẫu thuộc vào một lớp mà gần với trung bình của lớp đó hơn. 16 Trước tiên, ta tính trung binh mẫu của hai lớp c+ = ~ ĩi{i\yi=+1} x i c - + ~ ^ 1 7 S { i | y i=_j} x i (1-6) ( 1-7 ) Trong đó m+ và m. là số lượng các mẫu có nhãn là âm và dương, và hai lớp này đều không rỗng. Điểm RÌữa hai lớp C+ và c. là điểm c:=(c+ + c.)/2. Đe biết xem X thuộc về lớp nào thì ta kiếm tra xem góc tạo thành giữa vector x-c và vector w xem có nhỏ hơn n/2 hay không. Ta có : y = sgn < (x - c), w > = sgn < (x - (c+ + c _ ) / 2 ) ,(c+ + c_) > = s g n ( < x , c + > - < x , c _ > + b) (1.8) Gọi b là lề, ta có 6 = i( |c _ |2 Do |Ịx|| = v< |c+ | 2), (1.9) x . x > ncn khi b triệt ticu tức là khoảng cách trung bình của hai lớp đến gốc toạ độ là bàng nhau. Từ (1.8) ta có một siêu phẳng, gồm các điểm thoả mãn các điều kiện của một đẳng thức tuyển tính. Trừ (1.6) và (1.7) cho ( 1 .8) ta có hàm quyết định : Và lề b thành : 17 Hình ỉ. I Phân lớp trong đơn gián Khi b=0 ta có trường hợp đặc biệt, bài toán trở thành bài toán phân lớp theo phương pháp thống kê. Khi đó, k sê trở thành hàm xác suất khi một biến không thav đổi / k ( x ,x ') d x = 1 v ớ i m ọ i x ' e X (1.12) X Khi đó (1.11) là dạng phân lớp Bayes với hai lớp và phân bố xác suất được tính theo công thức sau : p +( x ) := — ĨĨĨ+ y í—i k(x,xi) và P - 0 0 := — ĨĨI- {Ì|yi=+1} Khi đó, với một sổ mẫu X, V L-Ấ k(x,xi) ( 1 .1 3 ) {i|y«=-i} thì nhãn được xác định bằng giá trị lớn hơn trong hai giá trị p , (x) và p.(x) ĐẠI H Ọ C Q U O C G I A H A N Ộ I t r u n g Tâm JHÔNG TIN THU VIỆN V lc / -'M A. 6____ 18 í . 2.4 Một số khái niệm trong lý thuyết học thống kê Xác định mức độ rủi ro trong phân lóp Hình 1.2 : Hai hàm huấn luyện cho kết quả khác nhau trên dữ liệu kiềm tra Trong ví dụ phân lớp như trong hình trên, với tập dừ liệu huấn luyện là ba điếm (được khoanh tròn) và ba tập dữ liệu kiểm tra (trên trục x). Ta thấy cả hai hàm f(x) và g(x) đều cho kết quả tốt trên tập dữ liệu huấn luyện, nhung với các dự đoán trong tập dữ liệu kiểm tra thi hai hàm cho các kết quả khác nhau. Do đó, nếu chỉ dựa trên các dữ liệu huấn luyện thì chúng ta không thể nào xác định được hàm phân lớp nào là tốt. Một hàm f nếu có thể phân lớp tốt trên các dữ liệu kiểm tra tức là f có tính tổng quát hoá tốt. Một quan sát (Y X) , bị chi phối bởi một xác suất p (xác suất tiên nghiệm chưa biết). Ở đây, c h ú n g ta chấp n hận giả thiết rằn g tập h u ấn luyện bao gồm N biến ngẫu nhiên được sinh ra theo p : (X],Yi),...,(Xn,Yn) . Từ đó người ta đưa ra định nghĩa “mức độ tổng quát hóa” của một luật f là xác suất mà lu ậ t/sin h ra một lồi trên một ví dụ mới (ví dụ mới được sinh ra theo phân phổi p ), ta viết lại điều này dưới dạng: R(/)=p(/rx>* Y) R(/)=0 là độ rủi ro của bộ phân lớp / Nếu R(/)=0 có nghĩa / sẽ không sinh ra một lồi phân lớp nào trên một quan sát mới, hay nó có một khả năng tống quát hóa tốt. Với một tập huấn luyện s, bộ phân lớp / ta có thể quan sát được Remp(/), nhưng không thể quan sát được R(/). Trực giác cho thấy trong nhiều trường họp Rcmp(/) nhỏ thì R(/) cũng nhỏ. Vì vậy nhiều giải thuật học cố gắng tìm kiếm một luật với Rcmp(/) nhỏ với hi vọng rằng R(/) cũng sẽ nhỏ. Theo luật số lớn, với một luật xác định/ độ rủi ro thực nghiệm Remp(/) dần hội tụ đến R(/) khi dữ liệu huấn luyện lớn, do đó Rcmp(/) là một chỉ số tốt cho R(/) 19 Một giai thuật học chọn luật với độ rủi ro thực nghiệm trên tập huấn luyện là thấp nhất, nói cách khác, chọn luật / được định nghĩa như sau : Remp( / ) = inf Rcmp( / ) Phương pháp này thườníĩ là phương pháp cực tiểu rủi ro thực nghiệm ( E:RM). Nói cách khác, mục tiêu cua giải thuật học là tìm ra luật có khả năng tổng quát hóa tốt nhất, hay tìm luật thỏa mân R ( D = inf R.(/*) Mối liên hệ giữa R(f) và R(/*) là kết quả chính của ]ý thuyết học thống kê E R (/) < fi(/-)+ c * J ï p c là hàng sổ toàn cục, V(F) là đặc trưng số lượng của tập luật F , còn được gọilà chiều Vapnik-Chervonenkis (hay chiều VC), và N là số các ví dụ trong tập huấn luyện Nếu • Số lượng quan sát N trong tập huấn luyện phải đủ lớn • Số chiều v c của tập luật tiềm năng phải đủ nhò Thì độ rủi ro của một luật được chọn f không khác nhiều so với độ rủi ro tốt nhất có thể /?(/*) Ta thấy chiều v c càng nhỏ, khả năng tổng quát hóa của luật được lựa chọn theo phương thức ERM càng nhỏ. Nói cách khác, một giải thuật học sẽ tìm một luật tổng quát hóa tốt nếu nó có thể chọn các luật từ một tập F với sổ chiều vc nhỏ. 1.2.4.1 Không gian v c Xét các hàm f (x): R - » { + t,- l}, có 21 cách để gán nhãn cho / điểm. Nếu với mồi một cách gán nhãn ta đều có thể tìm thấy một thành phần của tập hợp ự(x)} mà nhận dạng chính xác cách gán nhãn này. Khi đó tập hợp của / điểm được nói là bị phá vỡ bởi tập hợp các hàm ịf(x)}. Chiều v c của [f(x)} là số lớn 20 nhât của các điêm dừ liệu mà có thê bị phá vờ bời nó. Chiêu vc của các siêu phẳng tronạ không gian Rn là thường là n+1. Hình : 1.3 v c của các đường thẳng cỏ hưởng trong không gian 2 chiều (R2) là 3. Tóm lại, đóng góp chính của lý thuyết học thống kê cho việc thiết kế một giải thuật là xác định tầm quan trọng của tập các luật F mà thuật toán có thể lựa chọn 1.2.4.2 Mối liên hệ giữa lý thuyết học thống kê và SVM Từ nhừng kết quả chính của lý thuyết học thống kê, tư tưởng chủ đạo của SVM là tăng khả năng tổng quát hóa tốt bằng cách kiểm soát chiều v c . ở đây, tồn tại hai mục tiêu đổi nghịch nhau trong việc thiết kế một giải thuật học: • Chọn F càng phong phú càng tốt để đảm bảo rằng tồn tại ít nhật một phần tử trong F có rủi ro nhỏ nhất. • Chọn F càng nhỏ, đơn giản càng tốt để rủi ro của luật được chọn gần với rủi ro của luật tốt nhất 1.3 Phương pháp phân tích thành phần chính (PCA) 1.3.1 Đô • •lêch chuẩn Trong thống kê, khái niểm lấy mẫu là rất quan trọng. Bằng việc lấy mẫu, ta có thề có được các độ đo gần như giống với độ đo trên toàn tập dừ liệu mà ta 21 e X là tập dừ liệu mẫu, khi đó giá trị trung bình đã lấy mầu. Giả sử, x lt mầu được tính theo công thức sau : - X = I L i Xi n (1.14) Giá trị trung bình mẫu không chứa đựng nhiều thông tin về tập mẫu, có thế có hai tập mẫu có sự phân bố dữ liệu khác nhau nhưng vẫn có giá trị trung bình mầu giống nhau. Do đó chúng ta cần có giá trị độ lệch chuấn (Standard Deviation) để đo sự phân bổ dữ liệu, độ lệch chuẩn thể hiện khoảng cách trung bình từ trung bình mẫu đến một điểm dừ liệu s = (n -l) 1.3.2 Ph trong sai Phương sai (variance) cũng ià một công cụ đế đo độ phân tán của dữ liệu trong tập mẫu : 2 _ E?=i(*i - X ) : * ( n 1- -n...1) •» (L16) t Hay ta có thê viêt dưới dạng : ...... Z ?=1 ( X i - X ) ( X i - X ) v a r ( x ) = — ----_ ---------( n - 1) (1.17) Tuy nhiên, cả độ lệch chuẩn và phương sai chỉ làm việc trên không gian một chiều thế nên trong không gian nhiều chiều ta chỉ tìm được sự phân bố dữ liệu trên từng chiều riêng biệt. Điều chúng ta đang mong muốn là tìm mối quan hệ giữa các chiều dừ liệu với giá trị trung bình mẫu. Do đó chúng ta sử dụng hàm hiệp phương sai (covariance) để so sánh giữa hai chiều dữ liệu trong không gian nhiều chiều. Ví dụ, trong không gian ba chiều (x,y,x), bằng cách sử dụng hàm hiệp phương sai chúng ta có thể xem xét sự phân bố dữ liệu trong các chiều (x,y),(x,z) và (y,z), giá trị của hàm hiệp phương sai giữa (x,x), (y,y) và (z,z) cũng chính là giá trị hiệp phương sai tương úm trên x,y và z. Hàm hiệp phương sai được tính theo công thức sau :