Bài giảng Lý thuyết nhận dạng – Chương 4: Phân lớp dựa trên tối ưu hóa hàm lượng giá

"Bài giảng Lý thuyết nhận dạng – Chương 4: Phân lớp dựa trên tối ưu hóa hàm lượng giá" với các nội dung giới thiệu chung (cont); thuật toán perceptron; phương pháp tổng bình phương nhỏ nhất; support vector machnes trường hợp tuyến tính; các lớp không phân biệt...
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết nhận dạng – Chương 4: Phân lớp dựa trên tối ưu hóa hàm lượng giá Tối ưu hóa hàm lượng giá LÝ THUYẾT NHẬN DẠNG CHƯƠNG 4: PHÂN LỚP DỰA TRÊN TỐI ƯU HÓA HÀM LƯỢNG GIÁ1 Biên soạn: TS Ngô Hữu Phúc Bộ môn: Khoa học máy tính Học viện kỹ thuật quân sự Email: ngohuuphuc76@gmail.com4.1. GIỚI THIỆU CHUNG  Trong chương này tập trung vào việc thiết kế hàm phân biệt/mặt quyết định có khả năng phân lớp theo một tiêu chí nào đó.  Với các kỹ thuật sử dụng bộ phân lớp Bayesian dựa trên ước lượng hàm phân bố dữ liệu của mỗi lớp. Tuy nhiên, đây là nhóm công việc phức tạp đối với dữ liệu có số chiều lớp.  Chương này đưa ra giải pháp xây dựng mặt quyết định mà không cần sử dụng hàm phân bố của dữ liệu.  Giải pháp thuộc nhóm này đơn giản hơn so với phương pháp phân lớp Bayesian, ngay cả đối với dữ liệu không nhiều.Tối ưu hóa hàm lượng giá 24.1. GIỚI THIỆU CHUNG (CONT)  Để minh họa, thiết kế bộ phân lớp tuyến tính được mô tả: ? ? ? + ?0 = 0 hay có thể viết lại: ? ?′? ?′ ≡ ? ? , ?0 1  Như vậy, nếu ?′ được ước lượng, một bộ dữ liệu x sẽ thuộc lớp ?1 ?2 nếu: ?′? ? ′ = ? ? ? + ?0 > < 0  Lưu ý: để đơn giản cách viết, có thể lược bỏ ký hiệu chuyển vị.Tối ưu hóa hàm lượng giá 34.1. GIỚI THIỆU CHUNG (CONT) Với dữ liệu trên, có thể dùng bộ phân lớp tuyến tínhTối ưu hóa hàm lượng giá 44.1. GIỚI THIỆU CHUNG (CONT) Với dữ liệu trên, có thể dùng bộ phân lớp tuyến tính???Tối ưu hóa hàm lượng giá 54.2. THUẬT TOÁN PERCEPTRON  Thuật toán Perceptron thích hợp với phân 2 lớp dạng tuyến tính.  Giải thuật tính giá trị của trọng số w trong bộ phân lớp tuyến tính để có thể phân biệt 2 lớp.  Giải thuật bắt đầu từ một ước lượng ban đầu và hội tụ đến lời giải của bài toán sau một số bước lặp.  Việc cập nhật giá trị trọng số tại bước i có dạng: ? ? + 1 = ? ? − ?? ?? ? ?∈? Trong đó:  w đã bao gồm cả ?0 ;  Y: tập bị phân lớp sai ở bước t;  ?? = −1 nếu ? ∈ ?1 ; ?? = 1 nếu ? ∈ ?2 ;  ?? : hệ số học tại bước t. Hệ số này do người thiết kế lựa chọn.  Thuật toán dừng khi Y rỗng.Tối ưu hóa hàm lượng giá 64.2. THUẬT TOÁN PERCEPTRON (CONT) Nguyên tắc chung của giải thuật là giảm gradient! Ý tưởng chung:  ???? = ???? + ∆? ?? ?  ∆? = −? |?=???? ?? ?? ? ? ??  = ?∈? ?? ? = ?∈? ?? ? ? ? ??  Từ đó, ta có: ? ? + 1 = ? ? − ?? ?? ? ?∈? với ?? đóng vai trò hệ số họcTối ưu hóa hàm lượng giá 74.2. THUẬT TOÁN PERCEPTRON (CONT) Ví dụ về sự biến đổi trong ý tưởng: w(t  1)  w(t )   t x  w(t )   t x x ( x  1)Tối ưu hóa hàm lượng giá 84.2. THUẬT TOÁN PERCEPTRON (CONT)1. Chọn ?0 ngẫu nhiên2. Chọn ?03. ?=04. Repeat5. ?=∅6. For ? = 1 to N7. ?? ??? ? ? ? ?? ≥ 0 ?ℎ?? ? = ? ∪ ??8. End {For}9. ? ? + 1 = ? ? − ?? ?∈? ?? ?10. Hiệu chỉnh ??11. ? =?+112. Until ? = ∅Tối ưu hóa hàm lượng giá 94.2. THUẬT TOÁN PERCEPTRON (CONT)  Sau khi hình thành bộ phân lớp, một dữ liệu x thuộc lớp nào tùy vào kết quả của hàm: ? ? ? ? = ? ?1 ?1 + ?2 ?2 + ⋯ + ?? ?? + ?0  Hàm ? . được gọi là hàm truyền hay hàm kích hoạt. Ví dụ:  ? ? = 1 nếu ? > 0; ? ? = −1 nếu ? < 0;  Mô hình mạng cơ bản (perceptron hay neuron):Tối ưu hóa hàm lượng giá 104.2. THUẬT TOÁN PERCEPTRON (CONT)  Xây dựng Perceptron trong MatLAB có dạng: [w, iter, mis_clas] = perce(X, y, w_ini, rho)  Trong đó:  X: ma trận có dạng (l +1)×N chứa dữ liệu huấn luyện. ...