Phân lớp phi tuyến dữ liệu lớn với giải thuật song song cho mô hình máy học véctơ hỗ trợ cục bộ

Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 9-10/7/2015<br /> DOI: 10.15625/vap.2015.000193<br /> <br /> PHÂN LỚP PHI TUYẾN DỮ LIỆU LỚN VỚI GIẢI THUẬT SONG SONG<br /> CHO MÔ HÌNH MÁY HỌC VÉCTƠ HỖ TRỢ CỤC BỘ<br /> Đỗ Thanh Nghị1, Phạm Nguyên Khang1<br /> 1<br /> Khoa Công nghệ Thông tin và Truyền thông, Trường Đại học Cần Thơ<br /> dtnghi@cit.ctu.edu.vn, pnkhang@cit.ctu.edu.vn<br /> TÓM TẮT - Trong bài báo này, chúng tôi đề xuất một mô hình máy học véc-tơ hỗ trợ cục bộ mới dựa trên máy học véc-tơ<br /> hỗ trợ (SVM) và giải thuật gom cụm dữ liệu (clustering), gọi là kSVM, dùng để phân lớp phi tuyến dữ liệu lớn. kSVM sử dụng giải<br /> thuật k-means để phân hoạch dữ liệu thành k cụm (cluster). Sau đó, với mỗi cụm kSVM huấn luyện một mô hình SVM phi tuyến dùng<br /> để phân lớp dữ liệu của cụm. Việc huấn luyện các mô hình SVM trên từng cụm hoàn toàn độc lập với nhau, vì thế có thể được thực<br /> hiện song song trên các máy tính multi-core. Giải thuật song song để huấn luyện kSVM nhanh hơn rất nhiều so với các giải thuật<br /> SVM chuẩn như LibSVM, SVMLight trong bài toán phân lớp phi tuyến dữ liệu lớn. Kết quả thực nghiệm trên các tập dữ liệu của<br /> UCI và 3 tập dữ liệu nhận dạng ký tự viết tay cho thấy đề xuất của chúng tôi hiệu quả hơn mô hình SVM chuẩn.<br /> Từ khóa - Máy học véctơ hỗ trợ, máy học véc-tơ hỗ trợ cục bộ, phân lớp phi tuyến dữ liệu lớn.<br /> <br /> I. GIỚI THIỆU<br /> Trong những năm gần đây, mô hình máy học véctơ hỗ trợ (SVM) [1] và các phương pháp dựa trêm hàm nhân<br /> (kernel-based methods) đã cho thấy được tính hợp lý của nó trong các bài toán phân toán, hồi quy và phát hiện phần tử<br /> mới. Các ứng dụng thành công của SVM đã được công bố trong nhiều lĩnh vực khác nhau như nhận dạng mặt người,<br /> phân lớp văn bản và tin-sinh học [2]. Các phương pháp này đã trở thành các công phân tích dữ liệu phổ biến. Mặc dù<br /> sở hữu nhiều ưu điểm, SVM vẫn thích hợp khi xử lý dữ liệu lớn. Lời giải của bài toán SVM là kết quả bài toán quy<br /> hoạch toàn phương (QP), vì thế độ phức tạp tính toán của các giải thuật SVM ít nhất là O(m2) với m là số phần tử trong<br /> tập huấn luyện. Hơn nữa, do yêu cầu bộ nhớ lớn nên việc sử dụng SVM trở nên khó khăn hơn khi đối mặt với dữ liệu<br /> lớn. Điều này dẫn đến yêu cầu mở rộng khả năng xử lý (scale up) của các giải thuật học để có thể xử lý các tập dữ liệu<br /> lớn trên các máy tính cá nhân (PCs).<br /> Chúng tôi đầu tư đề xuất một giải thuật song song cho bài toán SVM cục bộ, gọi là kSVM, nhằm giải quyết bài<br /> toán phân lớp phi tuyến các tập dữ liệu lớn. Thay vì xây dựng một mô hình SVM toàn cục như các giải thuật cổ điển<br /> (rất khoa khi xử lý dữ liệu lớn), giải thuật kSVM xây dựng một tập các mô hình SVM cục bộ. Điều này có thể được<br /> thực hiện rất dễ dàng bằng cách áp dụng giải thuật SVM chuẩn trên các tập dữ liệu nhỏ. Giải thuật kSVM thực hiện<br /> việc huấn luyện qua hai giai đoạn. Trong giai đoạn đầu, sử dụng giải thuật k-means [3] phân hoạch tập dữ liệu huấn<br /> luyện thành k cụm (cluster). Trong giai đoạn thứ hai, với mỗi cụm dữ liệu xây dựng một mô hình SVM phi tuyến để<br /> phân lớp dữ liệu cho cụm.<br /> II. MÁY HỌC VÉCTƠ HỖ TRỢ<br /> Xét bài toán phân lớp nhị phân như Hình 1, với m phần tử xi (i = 1, 2, …, m) trong không gian n chiều, Rn. Mỗi<br /> phần tử có nhãn tương ứng yi ∈ {-1, +1}. Với bài toán này, giải thuật SVM [1] cố gắng tìm một siêu phẳng tối ưu (biểu<br /> diễn bằng pháp véctơ w ∈ Rn và độ lệch b ∈ R) tách các phần tử thành hai phần tương ứng với nhãn của chúng. Siêu<br /> phẳng tối ưu là siêu phẳng cách xa 2 lớp nhất. Bài toán này tương đương với việc cực đại hoá khoảng cách hay còn gọi<br /> là lề (margin) giữa hai siêu phẳng hỗ trợ của mỗi lớp (x.w – b = 1 đối với lớp +1 và w.x – b = -1 đối với lớp -1).<br /> Khoảng cách giữa hai siêu phẳng hỗ trợ bằng 2/||w|| trong đó ||w|| là độ lớn (2-norm) của pháp véctơ w. Trường hợp dữ<br /> liệu không khả tách tuyến tính (linearly separable), ta xem mỗi phần tử nằm sai phía so với mặt phẳng hỗ trợ tương ứng<br /> với lớp của chúng là lỗi, khoảng cách từ phần tử lỗi đến siêu phẳng hỗ trợ được ký hiệu zi (zi ≥ 0). Vì thế, bộ phân lớp<br /> SVM phải đồng thời cực đại hoá lề và cực tiểu hoá lỗi. Mô hình SVM chuẩn mô hình hoá bài toán tối ưu này về bài<br /> toán quy hoạch toàn phương (1).<br /> m<br /> 1 m m<br /> min ∑∑ yi y jαiα j K xi , x j − ∑α<br /> α 2<br /> i=1 j=1<br /> i=1 i<br /> <br /> với ràng buộc:<br /> <br /> ⎧ m<br /> ⎪ ∑ yiα i = 0<br /> ⎪<br /> ⎨ i=1<br /> ⎪<br /> ⎪ 0 ≤ αi ≤ C ∀i = 1, 2,..., m<br /> ⎩<br /> <br /> (1)<br /> <br /> 548<br /> 5<br /> <br /> PHÂ LỚP PHI TUY<br /> ÂN<br /> YẾN DỮ LIỆU LỚN VỚI GIẢI THUẬT SONG S ONG CHO MÔ H<br /> L<br /> T<br /> HÌNH MÁY HỌC VÉCTƠ…<br /> <br /> tr<br /> rong đó C là h<br /> hằng số dương dùng để điều chỉnh độ lớn của lề và tổn khoảng các lỗi;<br /> g<br /> n<br /> ng<br /> ch<br /> tính<br /> <br /> n<br /> K xi , x j là hàm nhân tuyến<br /> <br /> K xi , x j = xi • x j .<br /> <br /> Hìn 1. Tách tuyến tính các phần tử thành hai lớp<br /> nh<br /> n<br /> ớp.<br /> <br /> Giải bà toán quy ho<br /> ài<br /> oạch toàn phươ (1), ta thu được αi (i = 1, 2, …, m). Các phần tử xi tương ứng với αi > 0<br /> ơng<br /> u<br /> .<br /> được gọi là cá véctơ hỗ tr Chỉ cần cá véctơ này ta có thể dựng lại được các siêu phẳng hỗ trợ và tìm được siêu<br /> đ<br /> ác<br /> rợ.<br /> ác<br /> t<br /> g<br /> c<br /> phẳng phân lớ tối ưu (nằm chính giữa h siêu phẳng hỗ trợ). Việc phân lớp ph tử mới x v mô hình SVM được<br /> p<br /> ớp<br /> m<br /> hai<br /> g<br /> hần<br /> với<br /> S<br /> cho bởi:<br /> c<br /> <br /> ⎛m<br /> ⎞<br /> p<br /> predictSVM (x = sign ⎜∑ y iαi K x, xi − b ⎟<br /> x)<br /> ⎝ i=1<br /> ⎠<br /> <br /> (2)<br /> <br /> ến<br /> i<br /> sử<br /> h<br /> ].<br /> ó<br /> ớp<br /> Các biế thể của giải thuật SVM s dụng các hàm phân lớp khác nhau [8] Để có thể có hàm phân lớ khác, ta<br /> không cần thay đổi giải thuậ mà chỉ cần thay đổi hàm nhân tuyến tí bằng các h<br /> k<br /> y<br /> ật<br /> m<br /> ính<br /> hàm nhân khá Bằng cách này ta thu<br /> ác.<br /> được các mô h<br /> đ<br /> hình phân lớp dựa trên các v<br /> véctơ hỗ trợ kh nhau. Hai hàm nhân ph tuyến phổ bi là:<br /> hác<br /> hi<br /> iến<br /> <br /> (<br /> <br /> )<br /> <br /> K xi , x j = xi ⋅ x j +1<br /> +<br /> <br /> d<br /> <br /> •<br /> <br /> Hàm đa thức bậc d<br /> d:<br /> <br /> •<br /> <br /> Hàm cơ sở bán kín (Radial Bas Function – RBF):<br /> nh<br /> sic<br /> <br /> K xi , x j = e<br /> <br /> −γ xi − j<br /> −x<br /> <br /> 2<br /> <br /> nh<br /> VM<br /> quả<br /> ịnh, chịu đựng nhiễu tốt và phù hợp với các bài toán như: phân<br /> g<br /> à<br /> i<br /> Mô hìn máy học SV cho kết q cao, ổn đị<br /> lớp, hồi quy và phát hiện ph tử ngoại la Nhiều ứng dụng thành cô của SVM đã được công bố bao gồm nhiều lĩnh<br /> à<br /> hần<br /> ai.<br /> ông<br /> M<br /> g<br /> vực: nhận dạng ảnh, phân lo văn bản và sinh-tin học [2].<br /> v<br /> g<br /> oại<br /> à<br /> III.GIẢI T<br /> THUẬT SON SONG CH MÁY HỌ VÉC-TƠ HỖ TRỢ CỤ BỘ<br /> NG<br /> HO<br /> ỌC<br /> ỤC<br /> Nghiên cứu trong [9] đã chỉ ra rằn độ phức tạp tính toán của SVM ít nhất là<br /> n<br /> ]<br /> ng<br /> p<br /> a<br /> t<br /> <br /> O (m 2 )<br /> <br /> t<br /> trong đó m là số phần tử<br /> <br /> tr<br /> rong tập huấn luyện. Điều n làm SVM trở nên khó sử dụng trong các tập dữ liệ lớn. Huấn lu<br /> n<br /> này<br /> M<br /> s<br /> ệu<br /> luyện một mô hình SVM<br /> toàn cục trên m tập dữ liệu lớn là một th<br /> một<br /> u<br /> hách thức do độ phức tạp tín toán cao và cần nhiều bộ nhớ.<br /> đ<br /> nh<br /> à<br /> ộ<br /> A. Huấn luyệ các mô hình SVM<br /> A<br /> ện<br /> liệu huấn luyện thành k<br /> Giải thu kSVM củ chúng tôi s dụng giải th<br /> uật<br /> ủa<br /> sử<br /> huật k-means[3] để phân h<br /> hoạch tập dữ l<br /> cụm, và sau đó huấn luyện một mô hình SVM phi tuy trên mỗi cụm. Hình 2 minh hoạ kết quả của mô hình SVM<br /> c<br /> h<br /> yến<br /> t<br /> toàn cục (hình trái) và 3 mô hình SVM cụ bộ (hình ph<br /> h<br /> ô<br /> ục<br /> hải), sử dụng hàm nhân RBF với γ = 10 v hằng số dun hoà C =<br /> h<br /> F<br /> và<br /> ng<br /> 106.<br /> 1<br /> <br /> Đỗ Thanh Nghị, P<br /> Đ<br /> Phạm Nguyên Kh<br /> hang<br /> <br /> 549<br /> <br /> H<br /> Hình 2. Mô hìn SVM toàn cụ (trái) và các mô hình SVM c bộ (phải).<br /> nh<br /> ục<br /> m<br /> cục<br /> <br /> Bây giờ ta sẽ xem xé độ phức tạp của việc xây dựng k mô hì SVM cục bộ với giải th<br /> ờ<br /> ét<br /> p<br /> ình<br /> huật kSVM. Toàn bộ tập<br /> T<br /> dữ liệu huấn lu<br /> d<br /> uyện gồm m p<br /> phần tử được phân hoạch thành k cụm (giả sử cân bằ<br /> t<br /> (<br /> ằng). Vì thế, m cụm có khoảng m/k<br /> mỗi<br /> phần tử. Độ ph tạp tính to của k mô hình SVM cụ bộ là<br /> p<br /> hức<br /> oán<br /> ục<br /> <br /> (<br /> <br /> )<br /> <br /> O k ( m ) = O ( mk<br /> k<br /> 2<br /> <br /> 2<br /> <br /> n<br /> o<br /> ). Việc phân tích này cho thấy rằng<br /> <br /> huấn luyện k m hình SVM cục bộ trong giải thuật kSV nhanh hơ huấn luyện một mô hình SVM toàn cục (độ phức<br /> h<br /> mô<br /> M<br /> VM<br /> ơn<br /> tạp<br /> <br /> O (m 2 ) .<br /> <br /> hải<br /> g<br /> ược<br /> t<br /> h<br /> iều<br /> dung hoà giữa khả năng<br /> a<br /> Cần ph chú ý rằng tham số k đư sử dụng trong mô hình kSVM để đi chỉnh sự d<br /> nh<br /> ải<br /> g<br /> đề<br /> a<br /> tổng quát hoá và chi phí tín toán của giả thuật. Trong [10, 11, 12], Vapnik đã đ cập đến sự dung hoà giữa khả năng<br /> ử<br /> (k<br /> bộ),<br /> c<br /> tổng quát hoá và số phần tử trong tập học. Trong ngữ cảnh của mô hình kSVM ( SVM cục b điều này có thể hiểu<br /> như sau:<br /> n<br /> •<br /> <br /> Nếu k lớn, thời gia huấn luyện của giải thuậ kSVM giảm đáng kể (độ phức tạp củ kSVM là<br /> an<br /> n<br /> ật<br /> m<br /> ộ<br /> ủa<br /> <br /> O( m<br /> k<br /> <br /> 2<br /> <br /> )) và<br /> <br /> kích t<br /> thước của các cụm (cluster) nhỏ. Tính cục bộ sẽ tăng và khả năng tổ quát hoá th<br /> )<br /> v<br /> ổng<br /> hấp.<br /> Nếu k nhỏ, thời gia huấn luyện của giải thuậ kSVM giảm không đáng kể. Tuy nhiên do kích thư của các<br /> an<br /> n<br /> ật<br /> m<br /> n,<br /> ước<br /> cụm l nên khả nă tổng quát hoá cao.<br /> lớn<br /> ăng<br /> Điều nà cho thấy rằ ta cần phả điều chỉnh k sao cho kíc thước của c cụm đủ lớ (vd: 200 nh đề nghị<br /> ày<br /> ằng<br /> ải<br /> ch<br /> các<br /> ớn<br /> hư<br /> tr<br /> rong [11]). Hơ nữa, do kS<br /> ơn<br /> SVM huấn luy k mô hình độc lập từ k cụm dữ liệu n ta có thể song song hoá quá trình<br /> yện<br /> h<br /> nên<br /> huấn luyện kh dễ dàng. Đâ là một tính chất rất tuyệt vời của kSV Giải thuậ kSVM song song tận dụn ưu điểm<br /> h<br /> há<br /> ây<br /> h<br /> VM.<br /> ật<br /> g<br /> ng<br /> của các hệ thố tính toán hiệu năng ca như máy tín đa nhân ha hệ thống t<br /> c<br /> ống<br /> ao<br /> nh<br /> ay<br /> tính toán lưới. Việc cài đặt giải thuật<br /> t<br /> kSVM song so đơn giản nhất là sử dụn mô hình lậ trình đa xử lý sử dụng b nhớ chia sẻ openMPI [13] trên các<br /> k<br /> ong<br /> ụng<br /> ập<br /> ử<br /> bộ<br /> ẻ<br /> máy tính đa nh Các bước cơ bản của q trình huấn luyện kSVM song song đư mô tả trong giải thuật 1.<br /> m<br /> hân.<br /> c<br /> quá<br /> ược<br /> g<br /> •<br /> <br /> Giải thuật 1: Giải thuật máy học véct hỗ trợ cục bộ kSVM<br /> t<br /> t<br /> tơ<br /> b<br /> Đầu vào:<br /> • Tậ dữ liệu huấ luyện D<br /> ập<br /> ấn<br /> • Số mô hình cục bộ k<br /> ố<br /> c<br /> • Si tham số γ<br /> iêu<br /> • H<br /> Hằng số C<br /> Đầu ra:<br /> • K mô hình SVM cục bộ<br /> M<br /> Bắt đầu<br /> Áp dụn giải thuật g<br /> ng<br /> gom cụm k-me<br /> eans lên tập D<br /> thu đượ k cụm D1, D2, …, Dk và các tâm tương ứng c1, c2, … ck<br /> ợc<br /> g<br /> …,<br /> #pragm omp parallel for<br /> ma<br /> for i = 1 to k do<br /> /* H<br /> Huấn luyện m hình SVM cục bộ trên cụm Di */<br /> mô<br /> c<br /> lsvmi = svm(Di, γ, C)<br /> m<br /> end<br /> return kSVM = { c1 , lsvm1 ), (c1 , lsvm1 ),..., (ck , lsvmk )}<br /> (<br /> <br /> Kết thúc<br /> <br /> 550<br /> <br /> PHÂN LỚP PHI TUYẾN DỮ LIỆU LỚN VỚI GIẢI THUẬT SONG SONG CHO MÔ HÌNH MÁY HỌC VÉCTƠ…<br /> <br /> B. Phân lớp phần tử mới bằng các mô hình SVM cục bộ<br /> Mô hình kSVM = { c1 , lsvm1 ), (c1 , lsvm1 ),…, (ck , lsvmk )} được dùng để phân lớp dữ liệu mới, x, như sau.<br /> (<br /> Trước hết, ta tìm cụm gần với x nhất (tìm cụm có tâm gần với x nhất).<br /> <br /> cNN = argmin d(x, c)<br /> <br /> (3)<br /> <br /> c<br /> <br /> trong đó d(x, c) là khoảng cách từ phần tử x đến tâm của cụm c.<br /> Sau đó, sử dụng mô hình SVM cục bộ<br /> <br /> lsvmNN<br /> <br /> (tương ứng với<br /> <br /> cNN<br /> <br /> ) để dự báo lớp của x.<br /> <br /> predict(x, kSVM ) = predict(x, lsvmNN )<br /> <br /> (4)<br /> <br /> IV. ĐÁNH GIÁ<br /> Chúng tôi quan tâm đến hiệu quả của giải thuật SVM cục bộ song song được đề xuất (gọi là kSVM) cho bài<br /> toán phân lớp. Chúng tôi đã cài đặt giải thuật kSVM bằng ngôn ngữ C++ sử dụng thư viện OpenMP [13]. Để so sánh,<br /> chúng tôi sử dụng thư viện SVM chuẩn libVM [14]. Đánh giá hiệu quả phân lớp được thực hiện trên hai tiêu chí: độ<br /> chính xác phân lớp và thời gian huấn luyện. Chúng tôi quan tâm đến việc so sánh hiệu quả giải thuật kSVM và<br /> libSVM.<br /> Tất cả các thí nghiệm được chạy trên máy tính cá nhân, cài hệ điều hành Linux Fedora 20, bộ vi xử lý Intel®<br /> Core i7-4790, 3.6 GHz, 4 nhân và bộ nhớ RAM 32 GB.<br /> Thí nghiệm được thực hiện trên 4 tập dữ liệu UCI [4] và 3 bộ dữ liệu ký tự viết tay chuẩn hai bộ cũ: USPS [5],<br /> MNIST [6] và một bộ dữ liệu ký tự viết tay mới [7]. Bảng 1 trình bày mô tả của các tập dữ liệu thực nghiệm. Nghi thức<br /> kiểm tra đánh giá được chỉ ra trong cột cuối của bảng. Dữ liệu đã được chia thành hai tập: huấn luyện (Trn) và kiểm tra<br /> (Tst). Chúng tôi sử dụng tập huấn luyện để huấn luyện các mô hình SVM. Sau đó, sử dụng các mô hình SVM thu được<br /> để phân lớp dữ liệu trong tập kiểm tra.<br /> Chúng tôi đề xuất sử dụng hàm nhân RBF trong cả kSVM và SVM chuẩn vì tính tổng quát và tính hiệu quả của<br /> nó [15]. Chúng tôi cũng điều chỉnh siêu tham số gamma của hàm nhân RBF (hàm nhân RBF của hai phần tử xi, xj) và<br /> tham số C (tham số dung hoà lỗi và độ lớn của lề SVM) để có được kết quả cao nhất. Hơn nữa giải thuật kSVM của<br /> chúng tôi có sử dụng thêm một tham số k. Chúng tôi đề xuất chọn k sao cho mỗi cụm dữ liệu có khoảng 1000 phần tử.<br /> Ý tưởng chính là tạo ra một sự dung hoà giữa khả năng tổng quát hoá [12] và chi phí tính toán. Bảng 2 trình bày các<br /> siêu tham số được sử dụng cho kSVM và SVM.<br /> Bảng 1. Bảng mô tả tập dữ liệu thực nghiệm<br /> <br /> ID<br /> 1<br /> 2<br /> 3<br /> 4<br /> 5<br /> 6<br /> 7<br /> <br /> Dataset<br /> Opt. Rec. of Handwritten Digits<br /> Letter<br /> Isolet<br /> USPS Handwritten Digit<br /> A New Benchmark for Hand.<br /> Char. Rec.<br /> MNIST<br /> Forest Cover Types<br /> <br /> Số phần tử<br /> 5620<br /> 20000<br /> 7797<br /> 9298<br /> 40133<br /> 70000<br /> 581012<br /> <br /> Số thuộc tính<br /> 64<br /> 16<br /> 617<br /> 256<br /> 3136<br /> 784<br /> 54<br /> <br /> Số lớp<br /> 10<br /> 26<br /> 26<br /> 10<br /> 36<br /> <br /> Nghi thức kiểm tra<br /> 3832 Trn - 1797 Tst<br /> 13334 Trn - 6666 Tst<br /> 6238 Trn - 1559 Tst<br /> 7291 Trn - 2007 Tst<br /> 36000 Trn - 4133 Tst<br /> <br /> 10<br /> 7<br /> <br /> 60000 Trn - 10000 Tst<br /> 400000 Trn - 181012 Tst<br /> <br /> Bảng 2. Các siêu tham số của kSVM và SVM<br /> <br /> ID<br /> 1<br /> 2<br /> 3<br /> 4<br /> 5<br /> 6<br /> 7<br /> <br /> Dataset<br /> Opt. Rec. of Handwritten Digits<br /> Letter<br /> Isolet<br /> USPS Handwritten Digit<br /> A New Benchmark for Hand. Char. Rec.<br /> MNIST<br /> Forest Cover Types<br /> <br /> γ<br /> 0.0001<br /> 0.0001<br /> 0.0001<br /> 0.0001<br /> 0.001<br /> 0.05<br /> 0.0001<br /> <br /> C<br /> <br /> k<br /> <br /> 100000<br /> 100000<br /> 100000<br /> 100000<br /> 100000<br /> 100000<br /> 100000<br /> <br /> 10<br /> 30<br /> 10<br /> 10<br /> 50<br /> 100<br /> 500<br /> <br /> Kết quả phân lớp của libSVM và kSVM trên 7 tập dữ liệu được cho trong bảng 3 và các hình 3 và hình 4. Như<br /> mong đợi, giải thuật kSVM của chúng tôi có thời gian huấn luyện ngắn hơn nhiều so với giải thuật libSVM. Về tiêu chí<br /> độ chính xác phân lớp, giải thuật của chúng tôi cho kết quả có thể so sánh được với giải thuật libSVM.<br /> <br /> Đỗ Thanh Nghị, P<br /> Đ<br /> Phạm Nguyên Kh<br /> hang<br /> <br /> 551<br /> <br /> Với 5 tập dữ liệu nhỏ đầu tiên, cải tiến về mặt thời gian của kSVM là khôn đáng kể. T nhiên với các tập dữ<br /> ỏ<br /> i<br /> t<br /> k<br /> ng<br /> Tuy<br /> liệu lớn, kSVM tăng tốc đán kể quá trìn huấn luyện Với tập dữ liệu MNIST, kSVM nhanh hơn libSVM đến 33.64<br /> M<br /> áng<br /> nh<br /> n.<br /> l<br /> h<br /> lần. Đặc biệt, với tập dữ liệ Forest cov type (được xem như là tập dữ liệu kh đối với SV phi tuyến [16, 17]),<br /> ệu<br /> ver<br /> c<br /> hó<br /> VM<br /> n<br /> libSVM chạy đ 23 ngày v chưa cho r lời giải. Tro khi đó, kS<br /> đến<br /> vẫn<br /> ra<br /> ong<br /> SVM thực hiệ huấn luyện trong 223.7 giây và cho<br /> ện<br /> g<br /> độ chính xác p<br /> đ<br /> phân lớp 97.06<br /> 6%!<br /> Bảng 3. So sán hiệu quả của các phương ph theo độ chín xác (%) và t<br /> B<br /> nh<br /> a<br /> háp<br /> nh<br /> thời gian huấn l<br /> luyện (giây)<br /> <br /> ID<br /> 1<br /> 2<br /> 3<br /> 4<br /> 5<br /> 6<br /> 7<br /> <br /> Dataset<br /> Opt. R of Handw<br /> Rec.<br /> written Digits<br /> Letter<br /> Isolet<br /> t<br /> USPS Handwritten Digit<br /> S<br /> n<br /> A Ne Benchmark for Hand. Ch Rec.<br /> ew<br /> k<br /> har.<br /> MNIS<br /> ST<br /> Fores Cover Type<br /> st<br /> es<br /> <br /> Độ chính xác (%)<br /> h<br /> li<br /> ibSVM<br /> kSVM<br /> 98.33<br /> 97.05<br /> 97.40<br /> 96.14<br /> 96.47<br /> 95.44<br /> 96.86<br /> 96.86<br /> 95.14<br /> 92.98<br /> 98.37<br /> 98.11<br /> NA<br /> 97.06<br /> <br /> Thời gi huấn luyệ (giây)<br /> ian<br /> ện<br /> libSV<br /> VM<br /> kSVM<br /> 0.5 8<br /> 0.21<br /> 2.87<br /> 7<br /> 0.5<br /> 8.37<br /> 7<br /> 2.94<br /> 2<br /> 5.8 8<br /> 3.82<br /> 107.0<br /> 07<br /> 35.7<br /> 1531 .06<br /> 45.50<br /> 4<br /> NA<br /> A<br /> 223.7<br /> 2<br /> <br /> Hình 3. So sánh thời gian huấn luyện.<br /> s<br /> h<br /> <br /> Hình 4. So sá độ chính xá phân lớp.<br /> ánh<br /> ác<br /> <br /> V THẢO LU<br /> V.<br /> UẬN VỀ CÁC CÔNG TR<br /> RÌNH CÓ LIÊ QUAN<br /> ÊN<br /> Đề xuất của chúng tô liên quan đế các giải thu huấn luyện SVM trên m số khía cạn Các phươn pháp cải<br /> t<br /> ôi<br /> ến<br /> uật<br /> n<br /> một<br /> nh.<br /> ng<br /> n<br /> ệu<br /> ồm<br /> ng<br /> ụng<br /> để<br /> ài<br /> tiến việc huấn luyện SVM đối với dữ liệ lớn bao gồ các phươn pháp sử dụ heuristic đ phân rã bà toán quy<br /> hoạch toàn phư<br /> h<br /> ương gốc thàn nhiều bài to nhỏ [9, 14 18, 19].<br /> nh<br /> oán<br /> 4,<br /> Mangas<br /> sarian và các cộng sự đã đ xuất cải biên bài toán SVM để có đ<br /> đề<br /> S<br /> được các mô hình máy học mới như<br /> Lagragian SVM [20], proxi<br /> L<br /> M<br /> imal SVM [21], Newton SVM [22]. Mô hình SVM b<br /> S<br /> ô<br /> bình phương tối thiểu (Lea squares<br /> ast<br /> SVM), do Suy<br /> S<br /> ykens và Vand<br /> dewalle [23] đ xuất, thay đổi bài toán tối ưu SVM c<br /> đề<br /> t<br /> chuẩn thành b toán SVM khác hiệu<br /> bài<br /> quả hơn (về m thời gian). Các giải thu này chỉ cần giải hệ phươ trình tuyế tính thay v phải giải bà toán quy<br /> q<br /> mặt<br /> .<br /> uật<br /> n<br /> ơng<br /> ến<br /> vì<br /> ài<br /> hoạch toàn phư<br /> h<br /> ương. Điều nà làm giảm đ<br /> ày<br /> đáng kể thời gian huấn luyệ Gần đây h<br /> g<br /> ện.<br /> hơn, phương p<br /> pháp giảm gra<br /> adient ngẫu<br /> <br />