GIỚI THIỆU SVM - Tài Liệu Text - 123doc

GIỚI THIỆU SVM

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (2.06 MB, 100 trang )

CHƯƠNG 2: PHƯƠNG PHÁP MÁY VÉC TƠ TỰA

SVM - SUPPORT VECTOR MACHINESChương này nghiên cứu một số vấn đề cơ bản của SVM: phân lớp tuyến tính với siêu phẳng tối ưu, sử dụng hàm nhân để phân lớp gián tiếp thông qua khônggian đặc trưng với số chiều cao hơn trong phân lớp phi tuyến, lý thuyết chiều VC Vapnik – Chervonenkis, một số thuật toán huấn luyện SVM như thuật toán chặtkhúc, thuật toán phân rã, thuật toán SMO Sequential Minimal Optimization và một số chiến lược SVM cho bài toán phân đa lớp. Cuối cùng là phần nghiên cứuứng dụng SVM vào bài toán nhận dạng chữ viết tay rời rạc trên các tập dữ liệu chữ số viết tay USPS United States Postal service và bộ mẫu chữ số viết tay MNISTcủa Viện Công nghệ và Tiêu chuẩn Quốc gia Hoa Kỳ National Institute of Standard and Technology of the United States.

2.1. GIỚI THIỆU SVM

được nghiên cứu từ những năm của thập niên 1960 với những cơng trình của Vapnik và Lerner 1963, Vapnik và Chervonenkis 1964. Cơ sở của SVMdựa trên nền tảng của lý thuyết học thống kê và lý thuyết chiều Vapnik Chervonenkis VC đã được phát triển qua 3 thập kỷ bởi Vapnik và Chervonenkis[9,10]. Lý thuyết này bắt đầu có những bước phát triển mạnh mẽ về mặt ứng dụng kể từ những năm cuối của thập niên 1990 Burges, 1996 [84]; Osuma, 1997 [85];Platt, 1998 [13] và từ đó đến nay nó đã trở thành một công cụ khá mạnh trong nhiều lĩnh vực như: nhận dạng chữ viết [16,22,23], nhận dạng mặt người [85]...Trong những năm gần đây, SVM được biết đến như một hướng tiếp cận phân lớp hiệu quả và đang được áp dụng rộng rãi trong nhiều ứng dụng thực tế. Ưu điểm củaSVM là khả năng phân lớp với độ chính xác cao, điều này được đảm bảo bởi các tính chất của siêu phẳng tối ưu và cách sử dụng hàm nhân. Tuy nhiên, tốc độ phân34lớp của SVM bị đánh giá là chậm hơn so với các phương pháp phân lớp khác. Trong quá trình phân lớp, SVM phải duyệt qua tất cả các véc tơ tựa để so sánh vớimẫu cần nhận dạng, khi số véc tơ tựa tăng thì tốc độ phân lớp cũng giảm xuống tương ứng.Các thuật toán huấn luyện SVM [9,10] được thực hiện theo ý tưởng sau: tìmsiêu phẳng tối ưu trong không gian đặc trưng để cực đại khoảng cách giữa hai lớp mẫu huấn luyện trong bài toán phân lớp nhị phân. Như vậy, việc huấn luyện SVMtương đương với việc giải bài toán tối ưu với số lượng các biến là l và số các tham số là l2, trong đó l là số lượng mẫu huấn luyện. Điều này dẫn đến bài toán trở nên phức tạp hơn trong cả hai mặt: không gian nhớ để lưu trữ và độ phức tạp tính tốn.Hơn nữa, siêu phẳng tối ưu lại nằm trong không gian đặc trưng với số chiều cao hơn dựa trên cơ sở lựa chọn hàm nhân. Mà việc lựa chọn hàm nhân phù hợp chotừng ứng dụng cụ thể buộc người sử dụng SVM phải thử nghiệm nhiều lần huấn luyện với các loại hàm nhân khác nhau tương ứng với các giá trị tham số khác nhaucủa chúng. Mặt khác, mục đích của việc huấn luyện SVM là lọc ra các mẫu huấn luyện có tham gia vào việc tạo siêu phẳng đồng thời loại bỏ các mẫu khơng liênquan, các mẫu có tham gia tạo ra siêu phẳng được gọi là các véc tơ tựa SV - Support Vector. Có nhiều thuật toán huấn luyện SVM, các thuật toán chặt khúc vàthuật tốn phân rã [2] đã phân tích bài tốn quy hoạch toàn phương QP - Quadratic Programing ban đầu thành một dãy các bài toán QP nhỏ hơn. Các thuật tốn nàyđã chứng tỏ rằng có thể giải các bài tốn với kích thước vượt q khả năng lưu trữ của bộ nhớ máy tính. Thuật tốn SMO [4] có thể xem là trường hợp cá biệt củathuật tốn phân rã, trong mỗi lần lặp SMO giải một bài tốn QP với kích thước là hai bằng giải pháp phân tích, vì vậy khơng cần phải giải bài tốn tối ưu. Các thuậttoán này đã được cài đặt trong hầu hết các phần mềm SVM mã nguồn mở hiện nay như SVMlight[16], LIBSVM [19], SVMTorch [17] và HeroSvm [18]. Cácphần sau đây sẽ nghiên cứu chi tiết những vấn đề cơ bản của SVM.

2.2. SVM TUYẾN TÍNH

Xem Thêm

Tài liệu liên quan

• 240637
  • 100
  • 278
  • 1

Tải bản đầy đủ (.pdf) (100 trang)

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(2.06 MB) - 240637-100 (trang) Tải bản đầy đủ ngay ×