Chương 1 Giới thiệu 1.1 Mục tiêu Trong luận văn này, tôi nghiên cứu việc xây dựng kernel cho thuật toán phân lớp trong lĩnh vực máy học, cụ thể là thuật toán phân lớp Support Vector Machine (SVM). SVM thực hiện việc phân lớp bằng cách tìm siêu phẳng (hyperplane) mà cho phép cực đại hóa khoảng cách biên (maximize margins). Trong khi đó, kernel của SVM dùng để đo độ tương đồng giữa các mẫu học, việc này đóng góp lớn vào hiệu quả phân lớp của thuật toán SVM. Thêm nữa, SVM là thuật toán phân lớp hiệu quả và được sử dụng rất rộng rãi trong nhiều lĩnh vực, đặc biệt trong lĩnh vực thị giác máy tính.
Từ kernel tuyến tính (linear kernel) mà sử dụng hàm tương quan (correlation), hay tích nội (inner product) để tính độ tương đồng trong việc phân chia lớp ở thời gian đầu khi thuật toán SVM được đề xuất. Các nhà nghiên cứu nhận thấy rằng, dữ liệu ngày càng phong phú và đa dạng, việc này đòi hỏi cần phải sử dụng các kernel phi tuyến (non-linear kernel) để có thể tìm được siêu phẳng hiệu quả hơn. Do vậy, nghiên cứu xây dựng kernel là một trong những chủ đề được nhiều nhà nghiên cứu trên thế giới quan tâm. Để đánh giá sự hiệu quả của kernel đề xuất, tôi áp dụng kernel đề xuất vào bài toán phân loại ảnh trong lĩnh vực thị giác máy tính.
Trong đó, bài toán phân loại đối tượng và phân loại cảnh là hai thể hiện cụ thể của bài toán phân loại ảnh được thực nghiệm dựa trên việc áp dụng kernel đề xuất để phân lớp.2 Đóng góp của luận văn 1.1 Xây dựng kernel cho thuật toán SVM Luận văn đề xuất Hierarchical Spatial Matching Kernel (HSMK), tạm dịch kernel so khớp có tính không gian và phân cấp. HSMK là sự cải tiến của Sptial Pyramid Matching Kernel – SPMK (tạm dịch kernel so khớp dạng tháp) dựa trên mô hình thô mịn (coarse to fine – C2F). SPMK được đề xuất bởi Lazebnik và các 10 đồng sự [19] thực hiện việc chia ảnh trên một chuỗi các lưới có kích thước khác nhau thành các vùng con (subregions), sau đó áp dụng mô hình túi đặc trưng (Bag of features – BoF) [6] để mô hình cho các vùng con này. Kernel đề xuất - HSMK cũng thực hiện việc chia ảnh dựa trên một chuỗi các lưới có kích thước khác nhau như trong SPMK, nhưng thay vì sử dụng mô hình BoF mà được biết hạn chế trong việc mô hình vùng để có thể đo được độ tương đồng tối ưu, HSMK sử dụng mô hình C2F để có thể xem xét vùng trên nhiều kích cỡ khác nhau, việc này có thể cho phép HSMK đạt được sự xấp xỉ độ tương đồng tối ưu tốt hơn khi sử dụng BoF như trong SPMK.
HSMK được tôi và các đồng sự công bố trong bài báo “Hiearchical Spatial Matching Kernel for Image Categorization” ở hội nghị quốc tế về phân tích và nhận dạng ảnh (International Conference on Image Analysis and Recognition – ICIAR) ở Burnaby, British Columbia, Canada vào năm 2011.2 Áp dụng kernel xây dựng cho bài toán phân loại ảnh Để cho thấy sự hiệu quả của kernel đề xuất - HSMK, tôi áp dụng vào bài toán phân loại ảnh thông qua hai thể hiện là bài toán phân loại đối tượng và phân loại cảnh. Từ thực nghiệm trên nhiều cơ sở dữ liệu ảnh chuẩn (benchmark dataset) cho bài toán phân loại đối tượng như Oxford Flower, CALTECH-101, CALTECH-256, cũng như cho bài toán phân loại cảnh như MIT Scene, UIUC Scene. HSMK cho kết quả vượt trội so với SPMK, với lưu ý rằng, SPMK được biết như kernel tốt nhất được dùng mô hình đối tượng cho việc tính toán độ tương đồng trong nhiều bài toán của lĩnh vực thị giác máy tính, đặc biệt là bài toán phân loại ảnh. Thêm nữa, việc sử dụng kernel đề xuất - HSMK cũng cho kết quả cao nhất (state of the art) hoặc ngang với các cách tiếp cận khác trên các cơ sở dữ liệu chuẩn này.
Mặt khác, hướng tiếp cận sử dụng HSMK chỉ sử dụng một kernel phi tuyến với SVM trên một loại đặc trưng, trong khi các phương pháp đạt kết quả cao nhất khác trên các cơ sở dữ liệu chuẩn trên thường sử dụng trên nhiều loại đặc trưng, cũng như sử dụng các phương pháp học phức tạp như học với nhiều kernel (multiple 11 kernel learning – MKL), tối ưu tuyến tính kết hợp boosting (linear programming boosting – LP-B).3 Các đóng góp khác liên quan Luận văn không trình bày tất cả các đóng góp được công bố của tôi trong thời gian là một học viên cao học. Trong phần này, tôi trình bày tóm tắt đóng góp khác liên quan đến hướng của luận văn – về máy học và thị giác máy tính. Tôi đề xuất thuật toán phân đoạn (segmentation) màu cho ảnh biển báo giao thông dựa trên thuật toán phân lớp SVM. Thay vì xử lý trên từng điểm ảnh (pixel) như cách tiếp cận truyền thống, thuật toán đề xuất xử lý trên một vùng các điểm ảnh để có thể sử dụng các thông tin lân cận, nâng cao hiệu quả phân đoạn màu trong ảnh giao thông.
Thuật toán này được áp dụng vào việc phát hiện biển báo giao thông cho hệ thống lái xe tự động trong đề án “Hệ thống lái xe tự động” (Autonomous driving system) của Học Viện Công Nghệ Toyota, Nagoya, Nhật Bản (Toyota Technological Institute, Nagoya, Japan). Công trình này được công bố trong bài báo “Realtime Traffic Sign Detection Using Color and Shape-Based Features” ở hội nghị lần hai về hệ thống cơ sở dữ liệu và hệ thống thông tin thông minh (Asian Conference on Intelligent Information and Database Systems – ACIIDS) ở Huế, Việt Nam, 2010.4 Cấu trúc của luận văn Trong chương 2, tôi trình bày khái quát nền tảng lý thuyết của thuật toán phân lớp dựa trên Support Vector Machine (SVM), từ SVM truyền thống với việc học dựa trên một kernel tới dạng học nhiều kernel của SVM, hay được biết với tên gọi bài toán Multiple Kernel Learning (MKL) cũng như lý thuyết về kernel được sử dụng trong SVM cũng như trong MKL. Tiếp đó, trong chương 3, tôi trình bày phương pháp học dựa trên kernel mà được xem là một trong những hướng tiếp cận chính và hiệu quả cho bài toán phân loại ảnh và trong chương 4, tôi trình bày kernel mà luận văn đề xuất - Hiearchical Spatial Matching Kernel (HSMK). Cuối cùng, 12 chương 5 trình bày việc áp dụng HSMK vào bài toán phân loại ảnh mà cụ thể là bài toán phân loại đối tượng và bài toán phân loại cảnh trên những cơ sở dữ liệu chuẩn như: Oxford Flower, CALTECH-101, CALTECH-256, MIT Scene và UIUC Scene.
13 Chương 2 Thuật toán phân lớp dựa trên SVM Trong chương này, tôi trình bày khái quát lý thuyết phân lớp của thuật toán Support Vector Machine (SVM). Tôi cũng nhắc lại lý thuyết kernel áp dụng cho thuật toán SVM trong chương này. Cuối cùng là một hướng nghiên cứu đang được cộng đồng nghiên cứu máy học rất quan tâm là việc học với nhiều kernel cho SVM, hay được biết với tên gọi bài toán Multiple Kernel Learning (MKL).1 Học với một kernel – Support Vector Machine (SVM) 2.1 Thuật toán phân lớp SVM Thuật toán phân lớp SVM được đề xuất bởi Cortes và Vapnik vào năm 1995 [3]. Nhưng những ý tưởng chính của thuật toán phân lớp SVM bắt nguồn từ hai công trình của Vapnik và Lerner vào năm 1963 [31] và Vapnik và Chervonenkis vào năm 1964 [32].
Thuật toán SVM là một bộ phân lớp nhị phân được xây dựng cho một tập dữ liệu huấn luyện như sau: Gọi X = {x1 , x2 ,., xN } với xi ∈ là tập dữ liệu nhập và Y = { y1 , y2 ,., y N } n tương ứng là tập dữ liệu xuất, hay còn gọi là nhãn của các mẫu dữ liệu nhập với yi ∈{−1, +1}. Dtrain = ( X , Y ) được gọi là tập dữ liệu huấn luyện cho thuật toán phân lớp SVM. Bộ phân lớp tuyến tính được mô hình như sau: y ( x) = sign( wT x + b) (2.1) Với w∈ n là vector trọng số và b ∈. Khi đó, ta có ràng buộc dữ liệu cho thuật toán học SVM như sau: ⎪⎧ w xk + b ≥ +1 yk = +1 T ⎨ T (2.2) ⎪⎩ w xk + b ≤ −1 yk = −1 Ta có thể kết hợp tập điều kiện (2.3) 14 Với điều kiện ràng buộc như trong (2.3), với các tập dữ liệu không thể phân tách được trên tất cả các mẫu học thì lời giải cho thuật toán phân lớp SVM là rỗng, điều này rất dễ xảy ra trong thực tế, do dữ liệu huấn luyện luôn có nhiễu.
Để giải quyết cho trường hợp này, Cortes và Vapnik [3] đã thay đổi công thức (2.4) Với biến slack ξ k > 0 để giải quyết cho trường hợp một số mẫu trong tập dữ liệu huấn luyện vi phạm điều kiện phân lớp. Ta có thể thấy những mẫu có ξ k > 1 là những mẫu vi phạm điều kiện phân lớp so với ràng buộc trong (2. Công thức tối ưu dạng nguyên thủy (primal problem) theo không gian trọng số của SVM có dạng như sau: N 1 T min J P ( w, ξ ) = w w + C ∑ ξk w,b ,ξ 2 k =1 s., N Với C là một số nguyên dương, được sử dụng để điều khiển giữa việc tối ưu hàm mục tiêu và những mẫu vi phạm ràng buộc phân lớp của SVM trong (2.5), ta có biểu thức Lagrangian tương ứng là: N N L( w, b, ξ ; α , v) = J p ( w, ξ ) − ∑ α k ( yk ( w xk + b) − 1 + ξ k ) − ∑ vkξ k (2.6) T k =1 k =1 Với các hệ số Lagrangian α k ≥ 0, vk ≥ 0 với k = 1,. Từ biểu thức (2.6), ta có lời giải của vấn đề tương ứng với việc giải bài toán: max min L( w, b, ξ ;α , v) (2.7) α ,v w,b ,ξ Lấy đạo hàm từng phần cho mỗi biến của hàm Lagrangian L trong (2.6), ta có: 15 ⎧ ∂L N ⎪ =0 → w = ∑ α k yk xk ⎪ ∂w k =1 ⎪ ∂L N ⎨ ∂b =0 → ∑α y = 0 k k (2.6) ta có bài toán đối ngẫu dạng tối ưu bậc hai (Dual Quadratic Programming) cho bài toán SVM như sau: 1 N N max J D (α ) = − ∑ yk yl xk xlα kα l + ∑ α k T α 2 k ,l =1 k =1 N s., N Do biểu thức (2.9) là dạng bài toán tối ưu bậc hai (Quadratic Programming), do vậy có thể sử dụng các bộ giải tối ưu (optimization solvers) để tìm lời giải.2 Kernel trong thuật toán phân lớp SVM 2.
