Thuật toán máy hỗ trợ vector (support vector machine-SVM) Người hướng dẫn:CN.Vũ Tiến Thành Sinhviên :Đinh thị Hương Lớp : k52CA Nội dung I.Phát biểu tốn 1.Trình bày tóm tắt phân lớp liệu 2.Tại lại sử dụng thuật toán SVM để phân lớp liệu? II Thuật toán máy hỗ trợ vector(SVM) Định nghĩa Mục đích Mơ hình giải thuật 4.Các câu hỏi 5.Giải 6.Transductive support vector machine(TSVM) III.Ứng dụng SVM I.Phát biểu tốn: 1.Trình bày tóm tắt phân lớp liệu - Phân lớp liệu kỹ thuật khai phá liệu sử dụng rộng rãi nghiên cứu mở rộng - Mục đích: Để dự đốn nhãn phân lớp cho liệu mẫu - Đầu vào: Một tập mẫu liệu huấn luyện,với nhãn phân lớp cho mẫu liệu - Đầu ra:Bộ phân lớp dựa tập huấn luyện,hoặc nhãn phân lớp - Kỹ thuật phân lớp liệu tiến hành bao gồm bước: Bước 1: Xây dựng mơ hình từ tập huấn luyện Bước 2: Sử dụng mơ hình – kiểm tra tính đắn mơ hình dùng để phân lớp liệu Bước Xây dựng mơ hình - Mỗi bộ/mẫu liệu phân vào lóp xác định trước - Lớp bộ/mẫu liệu xác định thuộc tính gán nhãn lớp - Tập bộ/mẫu liệu huấn luyện-tập huấn luyện – dùng để xây dựng mơ hình - Mơ hình biểu diễn luật phân lớp,các định cơng thức tốn học Bước 2: Sử dụng mơ hình - Phân lớp cho đối tượng chưa phân lớp - Đánh giá độ xác mơ hình + Lớp biết trước mẫu/bộ liệu đem kiểm tra so sánh với kết thu từ mơ hình + Tỉ lệ xác phần trăm mẫu/bộ liệu phân lớp mơ hình số lần kiểm tra - Các thuật toán phân lớp liệu phổ biến: + Thuật toán định + Thuật toán SVM + Thuật toán phân lớp Bayes + Thuật toán phân lớp K người láng giềng gần 2.Tại lại sử dụng thuật toán SVM phân lớp liệu? - SVM hiệu để giải tốn liệu có số chiều lớn(ảnh liệu biểu diễn gene,protein, tế bào) - SVM giải vấn đề overfitting tốt (dữ liệu có nhiễu tách dời nhóm liệu huấn luyện ít) - Là phương pháp phân lớp nhanh - Có hiệu suất tổng hợp tốt hiệu suất tính tốn cao 5.Trả lời: a.Có thể mở rộng mơ hình SVM để xử lý trường hợp cho phép lỗi tồn tại,khi siêu phẳng tốt cho phép tồn số lỗi đào tạo liệu? - giả sử có số liệu âm vượt giới hạn,những điểm thể số lượng lỗi tồn mặt phẳng phân cách có lề cực đại - phương pháp lề mềm sử dụng để mở rộng tốn SVM siêu phẳng cho phép số liệu nhiễu tồn - Phương pháp lề mềm (softmargin) sử dụng cách đưa thêm biến nới lỏng đo độ phân lớp sai cho liệu x: thỏamãn ràng buộc ξi tính khoảng cách từ lớp liệu bị lỗi đến hàm f(xn).do tổng giá trị biến tạm so sánh với giá trị hàm cực tiểu ban đầu Vd minh họa liệu bị nhiễu b.Có thể mở rộng mơ hình SVM tình trường hợp liệu khơng phân chia tuyến tính? - SVM ban đầu thuật tốn phân lớp tuyến tính,nhờ áp dụng hàm kernel, thuật tốn tìm siêu phẳng không gian phi tuyến đặc trưng biến đổi uu ruu r - Mở rộng uu r xi yithông qua hàm ánh xạ uu r tích vơ hướng khơng gian H lớn φcho ( xi )biến xi chí vơ hạn chiều,theo đẳng thức giữ Trong đẳng thức,khi có tích vơ hướng uu ruu r ta tính tích vơ hướng chúng xi phép yi thơng qua biến đổi vectors uu r uu r φ ( xi).φ ( yi ) gọi hàm kernel - Hàm kernel sử dụng để xác định nhiều quan hệ đầu vào khơng tuyến tính - Đối với hàm kernel tuyến tính ta xác định nhiều hàm bậc hai hàm mũ - Trong năm gần ,nhiều nghiên cứu sâu vào nghiên cứu kernel khác cho phân lớp SVM cho nhiều thống kê thử nghiệm khác c.Có thể thiết kế thuật giải cho việc tìm siêu phẳng phân cách có lề cực đại cho hàng ngàn hay hàng triệu thực thể không? - Một trở ngại ban đầu SVM hiệu việc tính tốn - Tuy nhiên vấn đề giải thành công + Cách tiếp cận :chia vấn đề tối ưu hóa lớn thành vấn đề nhỏ cho cuối gồm vài biến lựa chọn cẩn thận để tối ưu hóa đạt hiệu cao.Quá trình lặp lặp lại tất vấn đề tối ưu hóa triển khai thành công +Một cách tiếp cận gần xem xét vấn đề nghiên cứu SVM tìm bao đóng nhỏ tập mẫu liệu Với mẫu liệu này,khi ánh xạ vào không gian n chiều,đại diện tập gốc sử dụng để xây dựng bao đóng xấp xỉ nhỏ tập mẫu liệu.Phương pháp đạt hiệu cao.ta sử dụng máy core-vector để phân lớp hàng triệu liệu vài giây 5.Transductive support vector machine (TSVM) - Là mở rộng support vector machine chuẩn với liệu chưa gán nhãn - Mục tiêu tìm gán nhãn liệu chưa gán nhãn, cho tồn biên tuyến tính có lề cực đại liệu gán nhãn ban đầu liệu chưa gán nhãn -Giả sử có L mẫu gán nhãn U mẫu chưa gán nhãn gọi tập U - Cực tiểu hóa theo biến ( mục tiêu: ) hàm đáp ứng đk : C C* tham số người dùng thiết lập,có ý nghĩa cân độ lớn lề với ví dụ bị phân lớp sai ví dụ chưa gán nhãn -Ban đầu dùng phân lớp học quy nạp gán nhãn cho ví dụ tập U sau nâng cấp nghiệm cách đổi lại nhãn cho ví dụ tập U L bị gán sai huấn luyện lại,nó lặp * * C khơng cịn nhỏ thua tham số ngườiC +dùng −C* Ví dụ minh họa TSVM - liệu gán nhãn,siêu phẳng có phân cách lề cực đại đường chấm chấm, - với liệu chưa gán nhãn(các điểm đen)thì siêu phẳng có phân cách lề cực đại đường thẳng màu đen III.Ứng dụng SVM: Sử dụng phân loại nhận dạng - Trong việc nhận dạng chữ viết tay tiếng Việt +Dựa sở thành phần liên thông ảnh,phân tập ký tự tiếng Việt thành nhóm (box,dạng chữ rời,dạng chữ liên tục) tách ký tự có dấu thành phần rời +Sau xây dựng máy phân lớp SVM để nhận dạng cho phần chữ phần dấu + Kết thực nghiệm cho thấy mơ hình nhận dạng có độ xác tương đối cao - Trong nhận dạng mặt người : +Giai đoạn huấn luyện: ảnh mẫu vector hóa x= { X ,K , X 900 } dùng phương pháp PCA để rút trích đặc trưng thành vector y ={Y1 ,K , Y100 } đưa vào huấn luyện SVM +Giai đoạn nhận dạng:Mẫu cần nhận dạng vector hóa rút trích sau đưa vào nhận dạng SVM để xác định lớp cho mẫu - Phân tích vi ảnh protein subcelluar location + Ảnh đầu vào tiền xử lý thông qua thuật giải khử nhiễu, điều chỉnh tự động cường độ sáng + Thuật giải MRF [9] áp lên ảnhnhằm thực segmentation để phân biệt rõ phần nhân phần khác ảnh +Biến đổi mô tả phần áp ảnh đầu vào với tối đa tỉ lệ phân rã khác + Bước phân lớp thực với thuật giải SVM đa tỉ lệ cho phù hợp với tính chất đa phân giải hệ số sau biến đổi Tài liệu tham khảo: - tài liệu tham khảo chính: [3] Xindong Wu, Vipin Kumar, J.Ross Quinlan, Joydeep Ghosh, Qiang Yang, Hiroshi Motoda, Geoffrey J McLachlan, Angus Ng, Bing Liu, Philip S Yu , Zhi-Hua Zhou, Michael Steinbach, David J Hand, Dan Steinberg, Top 10 algorithms in data mining, Knowl Inf Syst (2008) - [CV95] Corinna Cortes, Vladimir Vapnik (1995) SupportVector Networks, Machine Learning, 20(3): 273-297 - http://en.wikipedia.org/wiki/Support_vector_machine - Nguyễn Thị Hương Thảo, Nguyễn Thị Thùy Linh, Nguyễn Thu Trang, Hà Quang Thụy (2007) Một giải pháp học bán giám sát SVM phân lớp trang web tiếng Việt, Baos cao FAIR 07, Nha Trang - http://en.wikipedia.org/wiki/Regression_analysis - http://en.wikipedia.org/wiki/Supervised_learning - http://www.slideshare.net/khuongquynh/bai-4phan-lop-presentation - http://en.wikipedia.org/wiki/Statistical_classification Xin chân thành cảm ơn! ... tra - Các thuật toán phân lớp liệu phổ biến: + Thuật toán định + Thuật toán SVM + Thuật toán phân lớp Bayes + Thuật toán phân lớp K người láng giềng gần 2.Tại lại sử dụng thuật toán SVM phân... liệu 2.Tại lại sử dụng thuật toán SVM để phân lớp liệu? II Thuật toán máy hỗ trợ vector( SVM) Định nghĩa Mục đích Mơ hình giải thuật 4.Các câu hỏi 5.Giải 6.Transductive support vector machine(TSVM)... f(x): - Để tìm siêu phẳng phân cách có lề cực đại,xây dựng vector hỗ trợ siêu phẳng song song với siêu phẳng phân cách gần vector hỗ trợ nhất,đó hàm : w.x – b = w.x – b = -1 w - Khoảng cách siêu