Tài liệu Phương pháp học máy đa nhãn đa thể hiện và ứng dụng trong gán nhẵn vùng ảnh

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN DUY LINH PHƯƠNG PHÁP HỌC MÁY ĐA NHÃN – ĐA THỂ HIỆN VÀ ỨNG DỤNG TRONG GÁN NHÃN VÙNG ẢNH LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà nội – 2015 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN DUY LINH PHƯƠNG PHÁP HỌC MÁY ĐA NHÃN – ĐA THỂ HIỆN VÀ ỨNG DỤNG TRONG GÁN NHÃN VÙNG ẢNH Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Cẩm Tú TS. Đặng Thanh Hải Hà nội – 2015 i Lời cảm ơn Lời đầu tiên, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc nhất đến TS. Nguyễn Cẩm Tú, TS. Đặng Thanh Hải đã tận tình chỉ bảo và hướng dẫn tôi trong suốt quá trình nghiên cứu khoa học và thực hiện luận văn này. Tôi xin chân thành cảm ơn các thầy, cô đã tạo mọi điều kiện thuận lợi cho tôi trong suốt quá trình học tập và nghiên cứu tại trường. Tôi cũng xin gửi lời cảm ơn đến các anh, chị và các bạn trong phòng thí nghiệm KT-Lab đã hỗ trợ tôi rất nhiều trong quá trình thực hiện luận văn. Cuối cùng, tôi xin gửi lời cảm ơn vô hạn đến gia đình và bạn bè, những người luôn bên cạnh giúp đỡ và động viên tôi trong suốt quá trình học tập, cũng như thực hiện luận văn. Tôi xin chân thành cảm ơn! Hà nội, ngày 18 tháng 12 năm 2015 Học viên Nguyễn Duy Linh ii Lời cam đoan Tôi xin cam đoan nội dung được trình bày trong luận văn này là do tôi thực hiện dưới sự hướng dẫn của TS. Nguyễn Cẩm Tú, TS. Đặng Thanh Hải. Tất cả những tài liệu tham khảo từ các nghiên cứu liên quan đều được trích dẫn rõ ràng từ danh mục tài liệu tham khảo trong luận văn. Nội dung luận văn không có việc sao chép tài liệu, công trình nghiên cứu của người khác mà không chỉ rõ về tài liệu tham khảo. Hà nội, ngày 18 tháng 12 năm 2015 Học viên Nguyễn Duy Linh iii MỤC LỤC Lời cam đoan ......................................................................................................... ii Danh mục các từ viết tắt ........................................................................................ v Danh mục các bảng .............................................................................................. vi Danh mục các hình vẽ, đồ thị .............................................................................. vii MỞ ĐẦU ............................................................................................................... 1 CHƯƠNG 1. TỔNG QUAN PHƯƠNG PHÁP HỌC MÁY ĐA NHÃN – ĐA THỂ HIỆN VÀ BÀI TOÁN GÁN NHÃN VÙNG ẢNH ..................................... 4 1.1. Phương pháp học máy đa nhãn - đa thể hiện ............................................. 4 1.2. Bài toán gán nhãn vùng ảnh ....................................................................... 9 1.3. Kết luận .................................................................................................... 11 CHƯƠNG 2. CÁC PHƯƠNG PHÁP GIẢI QUYẾT BÀI TOÁN HỌC MÁY ĐA NHÃN – ĐA THỂ HIỆN .................................................................................... 12 2.1. Hướng giải pháp phân rã bài toán ............................................................ 12 2.1.1. Lấy học máy đa nhãn làm cầu nối..................................................... 13 2.1.2. Lấy học máy đa thể hiện làm cầu nối................................................ 14 2.2. Hướng giải pháp giải quyết trực tiếp ....................................................... 14 2.3. Một số phương pháp học máy đa thể hiện ............................................... 16 2.3.1. Phương pháp DD ............................................................................... 16 2.3.2. Phương pháp EM-DD ....................................................................... 19 2.3.3. Phương pháp MISVM ....................................................................... 22 2.4. Một số độ đo đánh giá của học máy đa nhãn – đa thể hiện ..................... 25 2.5. Kết luận .................................................................................................... 28 CHƯƠNG 3. ỨNG DỤNG PHƯƠNG PHÁP HỌC MÁY ĐA NHÃN - ĐA THỂ HIỆN CHO BÀI TOÁN GÁN NHÃN VÙNG ẢNH ......................................... 29 3.1. Phương pháp đề xuất ................................................................................ 29 3.1.1. Giới thiệu........................................................................................... 29 3.1.2. Nội dung phương pháp đề xuất ......................................................... 29 3.2. Thực nghiệm và đánh giá ......................................................................... 32 iv 3.2.1. Mô tả thực nghiệm ............................................................................ 32 3.2.2. Môi trường và các công cụ................................................................ 32 3.2.3. Dữ liệu thực nghiệm.......................................................................... 33 3.2.4. Thực nghiệm ..................................................................................... 33 3.2.5. Đánh giá kết quả................................................................................ 37 3.3. Kết luận .................................................................................................... 38 KẾT LUẬN ......................................................................................................... 39 TÀI LIỆU THAM KHẢO ................................................................................... 40 v Danh mục các từ viết tắt STT 1 2 3 Từ viết tắt Bp-Mll EM-DD DD 4 D-MIMLSVM 5 6 MI MIL 7 MISVM 8 9 MISL MIML 10 MIMLRBF 11 MIMLSVM 12 MIML-DD 13 MIML-EMDD 14 MIML-MISVM 15 16 17 18 19 20 21 22 ML-kNN MLL MLSVM MSRCv2 SISL SIML SVM NLDD Cụm từ tiếng anh Back-propagation Multi-label learning Expectation-Maximization Diversity Density Diversity Density Directly Multi-Instance Lulti-Label Learning Support Vector Machine Multi-Instance Multi-Instance Learning Multi-Instance Support Vector Machine (Maximum Pattern Margin Formulation) Multi-Instance Single-Label Learning Multi-Instance Multi-Label Learning Multi-Instance Multi-Label Learning Radial Basis Function Multi-Instance Multi-Label Learning Support Vector Machine Multi-Instance Multi-Label Learning Diversity Density Multi-Instance Multi-Label Learning Expectation-Maximization Diversity Density Multi-Instance Multi-Label Learning MultiInstance Support Vector Machine Multi-Label k-Nearest Neighbor Multi-Label Learning Multi-Label Learning Support Vector Machine Microsoft Research Cambridge version 2 Single-Instance Single-Label Learning Single-Instance Multi-Label Learning Support Vector Machines Negative Logarithm of Diversity Density vi Danh mục các bảng Bảng 3.1: Cấu hình phần cứng ............................................................................ 32 Bảng 3.2: Công cụ và các thư viện phần mềm.................................................... 33 Bảng 3.3: Kết quả của MIML-DD ở cấp độ vùng ảnh........................................ 33 Bảng 3.4: Kết quả của MIML-EMDD ở cấp độ vùng ảnh ................................. 34 Bảng 3.5: Kết quả của MIML-DD ở cấp độ hình ảnh ........................................ 35 Bảng 3.6: Kết quả của MIML-EMDD ở cấp độ hình ảnh .................................. 36 vii Danh mục các hình vẽ, đồ thị Hình 1.1: Bốn khung học máy phân lớp hiện nay ................................................ 4 Hình 1.2: Một bài viết có nhiều nhãn.................................................................... 5 Hình 1.3: Một hình ảnh chứa nhiều vùng ảnh....................................................... 7 Hình 1.4: Ví dụ về học máy đa nhãn - đa thể hiện ............................................... 8 Hình 1.5: Hình ảnh được gán nhãn yếu trên Instagram ........................................ 9 Hình 2.1: Hai giải pháp phân rã bài toán học máy MIML ................................. 12 Hình 2.2: Thuật toán MIML Bayes dựa trên quá trình Gaussian tiền nghiệm .. 15 Hỉnh 2.3: Cấu trúc của mạng nơ ron MIMLRBF ............................................... 16 Hình 2.4: Ví dụ một điểm có Diverse Density ................................................... 17 Hình 2.5: Mã giả của phương pháp EM-DD ...................................................... 21 Hình 2.6: Ví dụ phân lớp với MISVM ............................................................... 23 Hình 2.7: Mã giả giải thuật tối ưu heuristic của phương pháp MISVM ............ 24 Hình 3.1: Mô hình phương pháp đề xuất ............................................................ 30 Hình 3.2: Biểu đồ thể hiện kết quả trung bình của các phương pháp ở cấp độ vùng ảnh với tỉ lệ giả túi 0% ........................................................................................ 34 Hình 3.3: Biểu đồ thể hiện kết quả trung bình của các phương pháp ở cấp độ vùng ảnh với tỉ lệ giả túi 60% ...................................................................................... 35 Hình 3.4: Biểu đồ thể hiện kết quả trung bình của các phương pháp ở cấp độ hình ảnh với tỉ lệ giả túi 0% ........................................................................................ 36 Hình 3.5: Biểu đồ thể hiện kết quả trung bình của các phương pháp ở cấp độ hình ảnh với tỉ lệ giả túi 60% ...................................................................................... 37 1 MỞ ĐẦU Hiện nay, với sự phát triển mạnh mẽ của các ứng dụng chia sẻ hình ảnh, mạng xã hội đã sản sinh ra lượng dữ liệu hình ảnh vô cùng lớn. Cùng với đó là sự gia tăng của nhu cầu tổ chức, tìm kiếm, trích xuất thông tin từ nguồn dữ liệu hình ảnh này. Mỗi hình ảnh thường chứa một số vùng ảnh nhất định, ứng với mỗi vùng ảnh có nội dung và mang ý nghĩa khác nhau. Gán nhãn vùng ảnh nhằm hỗ trợ cho việc phân loại, tìm kiếm, trích xuất thông tin từ ảnh dựa trên các từ khóa. Do khối lượng dữ liệu hình ảnh rất lớn nên việc gán nhãn vùng ảnh thủ công tốn nhiều thời gian và công sức. Vì vậy, nhu cầu gán nhãn vùng ảnh tự động càng trở nên cấp thiết. Học máy đa nhãn – đa thể hiện là một trong bốn khung học máy phân lớp phổ biến hiện nay [17, 18], bao gồm học máy đơn nhãn - đơn thể hiện (hay còn được gọi là học máy giám sát truyền thống), học máy đơn nhãn - đa thể hiện (hay học máy đa thể hiện), học máy đa nhãn – đơn thể hiện (hay học máy đa nhãn) và học máy đa nhãn - đa thể hiện. Với học máy phân lớp đơn nhãn – đơn thể hiện (single-instance, single-label learning: SISL) hay còn được gọi là học máy phân lớp truyền thống, mỗi đối tượng được phân lớp chỉ thuộc vào một lớp (nhãn lớp) và chỉ có một thể hiện duy nhất trong miền ứng dụng. Trong học máy phân lớp đơn nhãn - đa thể hiện (multi-instance, single-label learning: MISL) [5], mỗi đối tượng chỉ thuộc vào một lớp nhưng có thể có nhiều thể hiện khác nhau. Với học máy đa nhãn – đơn thể hiện (single-instance, multi-label learning: SIML) [7], mỗi đối tượng được phân vào nhiều lớp và chỉ có một thể hiện trong miền ứng dụng. Học máy đa nhãn – đa thể hiện (multi-instance, multi-label learning: MIML) [17, 18] là khung học máy phân lớp mới nhất hiện nay, được nhóm tác giả Zhi-Hua Zhou và Min-Ling Zhang công bố lần đầu tiên vào năm 2006. Trong khung học máy MIML, mỗi đối tượng không chỉ thuộc vào nhiều lớp, mà còn có nhiều thể hiện. So với học máy phân lớp truyền thống, khung học máy đa nhãn – đa thể hiện biểu diễn tự nhiên và thuận tiện hơn [17, 18] các đối tượng có nhiều thể hiện, đồng thời thuộc về nhiều lớp. Trong thực tế, có không ít đối tượng có nhiều thể hiện và thuộc về nhiều lớp khác nhau. Ví dụ, một hình ảnh còn được xem là một túi thường bao gồm một số vùng ảnh (mỗi vùng ảnh được coi như một thể hiện), đồng thời hình ảnh còn thuộc về nhiều lớp khác nhau. Việc áp dụng các phương pháp học máy có giám sát cho bài toán gán nhãn vùng ảnh yêu cầu bộ dữ liệu học đã được gán nhãn cho từng vùng ảnh phải đủ 2 lớn. Để xây dựng bộ dữ liệu được gán nhãn chuẩn, đòi hỏi mất nhiều thời gian và chi phí để thuê các chuyên gia gán nhãn cho khối lượng lớn tập dữ liệu huấn luyện. Việc xây dựng bộ dữ liệu hình ảnh được gán nhãn yếu thường dễ hơn so với việc xây dựng bộ dữ liệu hình ảnh được gán nhãn chi tiết cho từng vùng ảnh. Ta có thể tận dụng lượng dữ liệu hình ảnh được gán nhãn yếu khá phổ biến hiện nay từ các ứng dụng chia sẻ hình ảnh, mạng xã hội. Hình ảnh được gán nhãn yếu [13] là các hình ảnh được gán nhãn ở cấp độ hình ảnh thay vì gán nhãn chi tiết cho từng vùng (đối tượng) của ảnh, nhãn của mỗi hình ảnh là tập các nhãn ứng với các vùng bên trong của hình ảnh đó. Nhờ đó, ta có thể xây dựng được bộ dữ liệu huấn luyện được gán nhãn yếu với số lượng lớn cho việc huấn luyện phân lớp học máy đa nhãn - đa thể hiện. Trong đó, mỗi ảnh được gán nhãn yếu được coi như một túi, mỗi vùng của ảnh được xem như một thể hiện, với tập các nhãn là nhãn của ảnh. Trên cơ sở như vậy, luận văn tập trung nghiên cứu phương pháp học máy đa nhãn – đa thể hiện và các hướng giải pháp để giải quyết vấn đề đa nhãn – đa thể hiện. Có hai hướng giải pháp chính giải quyết vấn đề học máy đa nhãn – đa thể hiện. Hướng giải pháp đầu tiên là phân rã bài toán học máy đa nhãn – đa thể hiện thành bài toán có độ phức tạp ít hơn (lấy học máy đa thể hiện hoặc học máy đa nhãn làm cầu nối), nổi bật là nghiên cứu của Zin-Hua Zhou và cộng sự [17, 18]. Từ đó xây dựng thuật toán học máy MIML dựa trên việc tích hợp các thuật toán học máy tương ứng với học máy đa thể hiện hay học máy đa nhãn. Hướng giải pháp thứ hai là giải quyết trực tiếp bài toán học máy MIML một cách toàn vẹn, tiêu biểu là nghiên cứu của Jianjun He và cộng sự [8]. Để giải quyết bài toán gán nhãn vùng ảnh, luận văn tiến hành nghiên cứu sâu hơn hướng giải pháp phân rã vấn đề học máy đa nhãn – đa thể hiện lấy học máy đa thể hiện làm cầu nối. Ngoài ra, luận văn cũng nghiên cứu các thuật toán học máy đa thể hiện như: DD [9], EM-DD [11], MISVM [3]. Qua đó, luận văn đưa ra đề xuất xây dựng thuật toán học máy MIML mới dựa trên việc tích hợp các thuật toán học máy đa thể hiện DD [9], EM-DD [11], MISVM [3] đã nghiên cứu để giải quyết bài toán gán nhãn vùng ảnh. Đồng thời, luận văn đưa ra đề xuất bổ sung thông tin vùng ảnh nhằm nâng cao chất lượng gán nhãn. Luận văn được chia thành ba chương với nội dung như sau: Chương 1: Tổng quan phương pháp học máy đa nhãn – đa thể hiện và bài toán gán nhãn vùng ảnh. Giới thiệu chung về phương pháp học máy đa nhãn – đa thể hiện và bài toán gán nhãn vùng ảnh. 3 Chương 2: Các phương pháp giải quyết bài toán học máy đa nhãn – đa thể hiện. Luận văn trình bày về các hướng giải pháp để giải quyết vấn đề đa nhãn – đa thể hiện, như tiếp cận giải quyết trực tiếp, hướng giải pháp phân rã bài toán học máy đa nhãn – đa thể hiện thành các bài toán có độ phức tạp ít hơn. Tiếp theo, luận văn sẽ trình bày các phương pháp học máy đa thể hiện như DD, EM-DD, MISVM được sử dụng để giải quyết bài toán học máy đa nhãn – đa thể hiện. Ngoài ra, luận văn còn trình bày một số độ đo đánh giá cho phương pháp học máy đa nhãn – đa thể hiện. Chương 3: Ứng dụng phương pháp học máy đa nhãn - đa thể hiện cho bài toán gán nhãn vùng ảnh. Luận văn đưa ra đề xuất xây dựng thuật toán học máy MIML mới dựa trên việc tích hợp các thuật toán học máy đa thể hiện DD, EMDD, MISVM đã nghiên cứu ở Chương 2 cho bài toán gán nhãn vùng ảnh. Đồng thời, luận văn còn đề xuất bổ sung thông tin vùng ảnh nhằm nâng cao chất lượng gán nhãn. Luận văn trình bày quá trình thực nghiệm dựa trên phương pháp được đề xuất với tập dữ liệu thực nghiệm MSRCv2. Cuối cùng, luận văn đưa ra đánh giá kết quả thực nghiệm thu được. Phần kết luận: Tóm lược những kết quả đã đạt được của luận văn và đưa ra định hướng nghiên cứu tiếp theo trong tương lai. 4 CHƯƠNG 1. TỔNG QUAN PHƯƠNG PHÁP HỌC MÁY ĐA NHÃN – ĐA THỂ HIỆN VÀ BÀI TOÁN GÁN NHÃN VÙNG ẢNH 1.1. Phương pháp học máy đa nhãn - đa thể hiện Học máy đa nhãn – đa thể hiện là một trong bốn khung học máy giám sát phổ biến hiện nay [17, 18], bao gồm học máy đơn nhãn - đơn thể hiện (hay còn được gọi là học máy giám sát truyền thống), học máy đơn nhãn - đa thể hiện, học máy đa nhãn - đơn thể hiện và học máy đa nhãn - đa thể hiện. Hình 1.1 cho ta thấy sự khác nhau của bốn khung học máy phân lớp hiện nay. Hình 1.1: Bốn khung học máy phân lớp hiện nay [18] Với học máy giám sát truyền thống hay còn gọi là học máy đơn nhãn - đơn thể hiện, một đối tượng được biểu diễn dưới dạng một thể hiện (hay véc tơ đặc trưng) và được gán một nhãn tương ứng. Khung học máy đơn nhãn – đơn thể hiện được mô tả trong Hình 1.1(a). Theo định nghĩa hình thức của học máy giám sát truyền thống [17, 18]: Ta ký hiệu 𝑋 là không gian thể hiện (hay không gian đặc trưng), 𝑌 là tập các nhãn. Để học hàm 𝑓: 𝑋 → 𝑌 từ tập dữ liệu cho trước {(x1, y1), (x2, y2),…,(xm, ym)} trong đó 𝑥𝑖 ∈ 𝑋 là một thể hiện và 𝑦𝑖 ∈ 𝑌 là nhãn xác định của thể hiện xi. Tức là từ một tập dữ liệu ví dụ đã được xây dựng từ trước {(x1, y1), (x2, y2),…,(xm, ym)}, yêu cầu của bài toán học máy giám sát truyền thống là học một ánh xạ f sao cho có thể gán nhãn cho từng thể hiện trong tập thể hiện 𝑋 với một nhãn trong tập 5 𝑌. Tuy học máy giám sát truyền thống đã được ứng dụng khá phổ biến và thu được nhiều kết quả tích cực, nhưng có nhiều đối tượng trong thế giới thực lại không hoàn toàn phù hợp với khung học máy này. Trong học máy đơn nhãn – đơn thể hiện, mỗi đối tượng chỉ thuộc về duy nhất một khái niệm, cùng với đó là thể hiện chỉ ứng với một nhãn đơn xác định. Tuy nhiên, có rất nhiều đối tượng phức tạp trong thực tế, các đối tượng này có thể thuộc về đồng thời nhiều nhãn lớp. Ví dụ, một hình ảnh có thể có đồng thời nhiều nhãn như bầu trời, tòa nhà, cây cối v.v. Một trang web có thể thuộc về nhiều thể loại như trang tin tức, tin thể thao hay tin bóng đá. Các khung học máy đa nhãn, học máy đa thể hiện, học máy đa nhãn – đa thể hiện là giải pháp cho vấn đề này. Trong học máy đa nhãn (còn được gọi là học máy đa nhãn – đơn thể hiện) [17, 18], một đối tượng được biểu diễn dưới dạng một thể hiện và được gán với nhiều nhãn lớp. Theo Zhi-Hua Zhou [17, 18] học máy đa nhãn được định nghĩa như sau: Giả sử 𝑋 là không gian thể hiện (hay không gian đặc trưng), 𝑌 là tập các nhãn. Mục tiêu là học hàm ánh xạ 𝑓: 𝑋 → 2𝑌 từ tập dữ liệu cho trước {(x1, Y1), (x2, Y2),…,(xm, Ym)} trong đó 𝑥𝑖 ∈ 𝑋 là một thể hiện và 𝑌𝑖 ⊆ 𝑌 là tập các nhãn {𝑦𝑖1 , 𝑦𝑖2 , … , 𝑦𝑖𝑙𝑖 }, 𝑦𝑖𝑘 ∈ 𝑌 (𝑘 = 1,2, … , 𝑙𝑖 ). Ký hiệu li là số nhãn có trong tập 𝑌𝑖 . Hình 1.2: Một bài viết có nhiều nhãn 6 Trong thực tế, học máy đa nhãn được ứng dụng trong nhiều lĩnh vực như phân lớp văn bản, ảnh, các dữ liệu đa phương tiện khác, trong tin sinh học v.v. Các văn bản có thể thuộc về nhiều thể loại khác nhau như: một bài báo có thể được phân lớp thành tin thể thao, tin xã hội hay tin giải trí. Một bức ảnh có thể thuộc nhiều lớp như bãi biển, mặt trời lặn. Tương tự như vậy, một bài hát có thể thuộc về nhiều thể loại như nhạc rock, nhạc ballad. Hình 1.2 là ví dụ cho dữ liệu của học máy đa nhãn, trong đó bài viết có nhiều nhãn như: Phú Yên, Du lịch, Khám phá, Trải nghiệm, Tôi thấy hoa vàng trên cỏ xanh v.v. Đã có rất nhiều thuật toán học máy đa nhãn được đề xuất trong thời gian qua như các tác giả Zhang, Min-Ling và Zhi-Hua Zhou [14] đã đề xuất thuật toán mạng nơ ron đa nhãn Bp-Mll trên cơ sở thuật toán Backpropagation cho việc phân loại văn bản và phân loại chức năng gen. Thuật toán k láng giềng gần nhất cho bài toán đa nhãn ML-kNN [15] cũng của Zhang, Min-Ling và Zhi-Hua Zhou. Các thuật toán đa nhãn MLSVM trên cơ sở thuật toán SVM của nhóm tác giả Boutell [4], của tác giả Godbole và Sarawagi [6] v.v. Với học máy đa thể hiện, các đối tượng được biểu diễn bởi nhiều thể hiện khác nhau và được gắn với một nhãn đơn duy nhất [17, 18]. Các đối tượng trong học máy đa thể hiện có thể được coi là các túi, ứng với mỗi túi là tập các thể hiện (hay tập các véc tơ đặc trưng). Một túi được gán nhãn “dương” nếu túi đó chứa ít nhất một thể hiện “dương”, túi được gán nhãn “âm” nếu tất cả thể hiện trong túi là “âm”. Trong học máy đa thể hiện, một đối tượng được biểu diễn bằng một tập các thể hiện khác nhau. Ví dụ, nhiều vùng ảnh có thể được trích xuất từ một hình ảnh (mỗi vùng ảnh tương ứng với một thể hiện), một tài liệu văn bản có thể chứa nhiều phần khác nhau (mỗi phần ứng với một thể hiện). Do vậy, các hình ảnh hay tài liệu văn bản có thể được biểu diễn bởi một tập các thể hiện. Có một chú ý trong học máy đa thể hiện đó là trong dữ liệu huấn luyện, mặc dù các túi được gán nhãn nhưng ta lại không biết được nhãn của các thể hiện trong túi đó [18]. Định nghĩa hình thức của học máy đa thể hiện [17, 18] như sau: Ký hiệu 𝑋 là không gian thể hiện (hay không gian đặc trưng), 𝑌 là tập các nhãn. Học hàm ánh xạ 𝑓: 2𝑋 → 𝑌 từ tập dữ liệu cho trước {(X1, y1), (X2, y2), … (Xm, ym)} trong đó 𝑋𝑖 ⊆ 𝑋 là tập các thể hiện {𝑥𝑖1 , 𝑥𝑖2 , … , 𝑥𝑖𝑛𝑖 }, 𝑥𝑖𝑗 ∈ 𝑋 (𝑗 = 1,2, … , 𝑛𝑖 ) và 𝑦𝑖 ∈ 𝑌 là nhãn của Xi. Ký hiệu ni là số thể hiện của tập 𝑋𝑖 . Học máy đa thể hiện được đề xuất lần đầu tiên bởi các tác giả Dietterich, Thomas G., Richard H. Lathrop, Tomás Lozano-Pérez [4] trong nghiên cứu dự 7 báo hoạt tính thuốc. Thời gian qua đã có nhiều thuật toán học máy đa thể hiện được đề xuất, một vài trong số đó là thuật toán DD [9] được đề xuất bởi Oded Maron và Tomás Lozano-Pérez, thuật toán EM-DD [11] của Qi Zhang và Goldma, thuật toán MISVM [3] do Stuart Andrews và cộng sự đề xuất v.v. Luận văn sẽ trình bày chi tiết các thuật toán DD [9], EM-DD [11] và MISVM [3] ở Chương 2. Các phương pháp học máy đa thể hiện được ứng dụng khá rộng rãi trong nhiều lĩnh vực [18] như phân loại và trích xuất ảnh, phân loại văn bản, khai phá web, phát hiện thư rác, nhận dạng khuôn mặt v.v. Hình 1.3 là một ví dụ cho dữ liệu của học máy đa thể hiện, từ một hình ảnh có thể trích xuất ra nhiều vùng ảnh (mỗi vùng ảnh tương ứng với một thể hiện) như: vùng ảnh rừng cây, vùng ảnh bầu trời và vùng ảnh vườn hoa. Hình 1.3: Một hình ảnh chứa nhiều vùng ảnh Học máy đa nhãn – đa thể hiện được đề xuất bởi Zhi-Hua Zhou và cộng sự [17, 18] là khung học máy mới nhất trong số bốn khung học máy hiện nay. Trong khung học máy MIML, mỗi đối tượng không chỉ thuộc vào nhiều lớp, mà còn có nhiều thể hiện khác nhau, hay mỗi đối tượng được biểu diễn bởi tập các véc tơ đặc trưng (tập các thể hiện) và được gán với nhiều nhãn lớp. Ví dụ, một hình ảnh có thể bao gồm nhiều vùng khác nhau ứng với các thể hiện, và được gán nhiều nhãn khác nhau. Hình 1.4 là một ví dụ về học máy đa nhãn - đa thể hiện. Trong 8 đó, hình ảnh bao gồm nhiều vùng ảnh ứng với các thể hiện khác nhau như thể hiện instance1 ứng với vùng ảnh cây cối (tree), thể hiện instance2 ứng với vùng ảnh chứa con voi (elephant), v.v. hình ảnh còn được gán các nhãn lớp tree, elephant và lion. Khung học máy MIML được định nghĩa một cách hình thức [17, 18] như sau: Ký hiệu 𝑋 là không gian thể hiện, 𝑌 là tập các nhãn. Học hàm ánh xạ 𝑓: 2𝑋 → 2𝑌 từ tập dữ liệu cho trước {(X1, Y1), (X2, Y2), … (Xm, Ym)} trong đó 𝑋𝑖 ⊆ 𝑋 là tập các thể hiện {𝑥𝑖1 , 𝑥𝑖2 , … , 𝑥𝑖𝑛𝑖 }, 𝑥𝑖𝑗 ∈ 𝑋 (𝑗 = 1,2, … , 𝑛𝑖 ) và 𝑌𝑖 ⊆ 𝑌 là tập các nhãn {𝑦𝑖1 , 𝑦𝑖2 , … , 𝑦𝑖𝑙𝑖 }, 𝑦𝑖𝑘 ∈ 𝑌 (𝑘 = 1,2, … , 𝑙𝑖 ). Ký hiệu ni là số thể hiện của tập 𝑋𝑖 , li là số nhãn trong tập 𝑌𝑖 . Hình 1.4: Ví dụ về học máy đa nhãn - đa thể hiện [7] Có thể thấy rằng, các khung học máy đa nhãn, học máy đa thể hiện và học máy đa nhãn – đa thể hiện là kết quả từ sự nhập nhằng trong việc biểu diễn các đối tượng của thế giới thực [17, 18]. Học máy đa thể hiện nghiên cứu sự nhập nhằng của không gian dữ liệu đầu vào (hay không gian thể hiện), một đối tượng có nhiều cách biểu diễn đầu vào (các thể hiện) khác nhau. Học máy đa nhãn xem xét sự nhập nhằng của không gian đầu ra (hay không gian nhãn lớp), mỗi đối tượng có nhiều biểu diễn đầu ra (các nhãn lớp). Trong khi đó, học máy đa nhãn – đa thể hiện xem xét sự nhập nhằng đồng thời của cả không gian đầu vào và đầu ra. Khi giải quyết các vấn đề của thế giới thực, việc biểu diễn tốt các vấn đề thường quan trọng hơn có thuật toán học máy tốt. Do việc biểu diễn tốt vấn đề có thể thu được nhiều thông tin có ý nghĩa và làm cho việc học để giải quyết vấn đề được dễ dàng hơn. Học máy đa nhãn – đa thể hiện biểu diễn các đối tượng có sự nhập nhằng cả về đầu vào và đầu ra, thuận tiện và tự nhiên hơn các khung học máy khác. 9 1.2. Bài toán gán nhãn vùng ảnh Hiện nay, sự phát triển mạnh mẽ của các ứng dụng chia sẻ hình ảnh, mạng xã hội như Instagram, Flickr, Facebook v.v. đã sản sinh ra một lượng dữ liệu hình ảnh khổng lồ. Theo một báo cáo của Instagram [19], trung bình mỗi ngày có hơn 80 triệu bức ảnh được chia sẻ qua ứng dụng Instagram. Nội dung và chủ đề của các hình ảnh được chia sẻ rất phong phú như thể thao, giải trí, phong cảnh, con người, khoa học - công nghệ, thiên văn v.v. Đây là nguồn dữ liệu rất tốt, có thể sử dụng cho nhiều mục đích khác nhau. Cùng với sự gia tăng của lượng dữ liệu ảnh là gia tăng của nhu cầu tổ chức, tìm kiếm, trích xuất thông tin từ nguồn dữ liệu hình ảnh này. Mỗi hình ảnh thường chứa một số vùng ảnh nhất định, ứng với mỗi vùng ảnh có nội dung và mang ý nghĩa khác nhau. Gán nhãn vùng ảnh nhằm hỗ trợ cho việc phân loại, tìm kiếm, nhận dạng, trích xuất thông tin từ ảnh dựa trên các từ khóa. Do khối lượng dữ liệu hình ảnh rất lớn nên việc gán nhãn vùng ảnh thủ công tốn nhiều thời gian và công sức. Vì vậy, nhu cầu gán nhãn vùng ảnh tự động càng trở nên cấp thiết. Việc áp dụng các phương pháp học máy có giám sát cho bài toán gán nhãn hình ảnh nói chung và bài toán gán nhãn vùng ảnh nói riêng, yêu cầu bộ dữ liệu học đã được gán nhãn cho từng ảnh, vùng ảnh phải đủ lớn. Để xây dựng bộ dữ liệu được gán nhãn chuẩn, đòi hỏi mất nhiều thời gian và chi phí để thuê các chuyên gia gán nhãn cho khối lượng lớn tập dữ liệu huấn luyện. Việc xây dựng bộ dữ liệu hình ảnh được gán nhãn yếu thường dễ hơn so với việc xây dựng bộ dữ liệu hình ảnh được gán nhãn chi tiết cho từng vùng ảnh. Hình 1.5: Hình ảnh được gán nhãn yếu trên Instagram 10 Hình ảnh được gán nhãn yếu [1, 13] (weak-labeling image hoặc looselylabeled image) là các hình ảnh được gán nhãn ở cấp độ hình ảnh (túi thể hiện) thay vì gán nhãn chi tiết cho từng vùng (thể hiện) của ảnh, nhãn của mỗi hình ảnh là tập các nhãn ứng với các vùng có trong hình ảnh đó. Ta có thể tận dụng lượng dữ liệu hình ảnh được gán nhãn yếu khá phổ biến hiện nay từ các ứng dụng chia sẻ hình ảnh, mạng xã hội. Hình 1.5 là một ví dụ về hình ảnh được gán nhãn yếu trên ứng dụng chia sẻ hình ảnh Instagram. Nhãn của ảnh gồm một số nhãn như saturn, rings, space v.v. đây là các nhãn tương ứng của các đối tượng có trong ảnh. Dữ liệu hình ảnh được gán nhãn yếu có một số ưu điểm [13]: (1) chúng có thể biểu diễn các đặc trưng trực quan khác nhau của các lớp đối tượng hiệu quả hơn; (2) có thể được thu thập dễ dàng hơn bằng cách cung cấp các nhãn của đối tượng được gán yếu ở cấp độ hình ảnh so với việc thu thập ở cấp độ đối tượng (hay vùng ảnh); và (3) đây là nguồn dữ liệu khởi đầu của việc nhận dạng cảnh và đối tượng trong thế giới thực do sự đa dạng của các nhãn và các đặc trưng của mình. Với những ưu điểm như vậy, ta có thể xây dựng được bộ dữ liệu huấn luyện được gán nhãn yếu với số lượng lớn cho việc huấn luyện phân lớp học máy đa nhãn - đa thể hiện. Trong đó, mỗi ảnh được gán nhãn yếu được coi như một túi, mỗi vùng của ảnh được xem như một thể hiện, nhãn của ảnh là tập các nhãn của các thể hiện. Bài toán gán nhãn vùng ảnh trở thành bài toán gán nhãn cho từng thể hiện trong túi. 11 1.3. Kết luận Trong chương này, luận văn đã giới thiệu khái quát một số khái niệm, nội dung của các phương pháp học máy như học máy giám sát truyền thống, học máy đa nhãn, học máy đa thể hiện và học máy đa nhãn – đa thể hiện. Ngoài ra, luận văn cũng giới thiệu về bài toán gán nhãn vùng ảnh và việc áp dụng phương pháp học máy đa nhãn – đa thể hiện cho bài toán gán nhãn vùng ảnh. Chương tiếp theo, luận văn sẽ giới thiệu các phương pháp giải quyết bài toán học máy đa nhãn – đa thể hiện và một số phương pháp học máy đa thể hiện.