- PHÂN LỚP ẢNH VỚI GIẢI THUẬT GIẢM GRADIENT NGẪU NHIÊN ĐA LỚP Đỗ Thanh Nghị 1 và Phạm Nguyên Khang 1. - Biểu diễn đặc trưng không đổi SIFT, Mô hình túi từ BoVW, Máy học véc tơ hỗ trợ SVM, Phương pháp giảm gradient ngẫu nhiên SGD Keywords:. - In this paper, we present a new algorithm, MC-SGD (Multiclass Stochastic Gradient Descent), to effectively classify multiclass images. - We propose a new algorithm called MC-SGD that is suited for classifying very-high-dimensional datasets. - The numerical test results on a real dataset showed that our algorithm MC-SGD outperforms Support Vector Machines (SVM) using non-linear kernel functions (Radial Basis Function - RBF).. - Trong bài này, chúng tôi trình bày giải thuật mới, giảm gradient ngẫu nhiên (Multiclass Stochastic Gradient Descent - MC-SGD), cho phân lớp hiệu quả dữ liệu ảnh đa lớp. - Tập dữ liệu ảnh biểu diễn ảnh bằng mô hình túi từ (Bag-of-Words - BoW) sử dụng các nét đặc trưng không đổi với những biến đổi tỉ lệ (Scale-Invariant Feature Transform - SIFT), dựa trên đặc trưng cục bộ, không bị thay đổi trước những biến đổi tỉ lệ ảnh, tịnh tiến, phép quay, không bị thay đổi một phần đối với phép biến đổi hình học affine (thay đổi góc nhìn) và mạnh với những thay đổi về độ sáng, sự nhiễu và che khuất. - Chúng tôi đề nghị một giải thuật phân lớp đa lớp mới, giảm gradient ngẫu nhiên MC-SGD, cho phép phân lớp hiệu quả dữ liệu có số chiều lớn thu được từ bước biểu diễn ảnh. - Kết quả thực nghiệm trên tập dữ liệu thực cho thấy giải thuật MC-SGD phân lớp nhanh, chính xác hơn khi so sánh với giải thuật máy học véc tơ hỗ trợ (Support Vector Machines - SVM) sử dụng hàm nhân phi tuyến (Radial Basis Function - RBF).. - Phân lớp ảnh là gán nhãn tự động cho từng ảnh theo chủ đề đã được định nghĩa trước dựa vào nội dung của ảnh. - Phân lớp ảnh có nhiều ứng dụng trong thực tế như nhận dạng chữ số trên chi phiếu ngân hàng, mã số trên bì thư của dịch vụ bưu chính, hay các chữ số trên các biểu mẫu nói chung, đặc biệt là tổ chức nội dung trang web một cách tự động bằng cách đánh nhãn tự động ảnh.. - Hệ thống phân lớp ảnh thường bao gồm hai bước: rút trích đặc trưng từ nội dung ảnh và huấn luyện mô hình máy học để gán nhãn tự động từ các đặc trưng này. - Hiệu quả của hệ thống phân lớp phụ thuộc vào các phương pháp sử dụng ở hai giai đoạn trên.. - Daoudi, 04) sử dụng tiếp cận rút trích đặc trưng dựa trên phát hiện của các điểm, màu sắc, kết cấu (texture), tổ chức. - Một ảnh được biểu diễn bởi tập hợp túi từ được xây dựng bằng cách áp dụng một giải thuật gom nhóm lên các véc tơ mô tả cục bộ SIFT. - Giai đoạn tiền xử lý cho ra một tập dữ liệu với số chiều rất lớn. - Tác giả đề xuất giảm chiều dữ liệu và sử dụng k láng giềng để phân lớp hiệu quả ảnh.. - Chúng tôi đề xuất sử dụng ý tưởng của phương pháp biểu diễn ảnh bằng đặc trưng không đổi SIFT và mô hình túi từ. - Tuy nhiên thay vì giảm chiều thì chúng tôi đề xuất một giải thuật học mới, giảm gradient ngẫu nhiên MC-SGD, cho phép phân lớp hiệu quả dữ liệu có số chiều lớn thu được từ bước biểu diễn ảnh. - Kết quả thực nghiệm trên tập dữ liệu ảnh thực từ ImageNet (Deng et al., 12) chỉ rằng giải thuật mới MC-SGD phân lớp nhanh, chính xác khi so sánh với giải thuật máy học véc tơ hỗ trợ SVM (Vapnik, 95) sử dụng hàm nhân phi tuyến (Radial Basis Function - RBF).. - Phần tiếp theo của bài viết được trình bày như sau: phần 2 trình bày ngắn gọn về biểu diễn ảnh bằng mô hình túi từ của đặc trưng cục bộ không đổi, phần 3 trình bày giải thuật phân lớp đa lớp MC-SGD. - 2 BIỂU DIỄN ĐẶC TRƯNG KHÔNG ĐỔI VÀ MÔ HÌNH TÚI TỪ. - Biểu diễn ảnh là một bước quan trọng trong phân loại ảnh. - Trong lãnh vực phân lớp và tìm kiếm ảnh, đặc trưng cục bộ SIFT (Lowe, 04) là những điểm đặc trưng, vùng đặc trưng để biểu diễn ảnh rất hiệu quả, ngày càng trở nên phổ biến. - Nghiên cứu tiên phong của (Bosch et al., 06) đề xuất hệ thống phân lớp ảnh dựa trên đặc trưng SIFT và mô hình túi từ (xuất phát từ ý tưởng phân lớp văn bản). - Giai đoạn biểu diễn ảnh theo mô hình túi từ và đặc trưng không đổi SIFT bao gồm 3 bước chính: (i) phát hiện và biểu diễn các nét đặc trưng. - Hình 1: Các điểm đặc trưng được phát hiện bởi thuật toán Hessian-Affine. - Các điểm đặc trưng (Hình 1) được tính trên những ảnh này bằng cách sử dụng các giải thuật phát hiện điểm đặc trưng cục bộ (local feature detector) như là Harris-Affine, Hessian-Affine (Mikolajczyk &. - Những điểm đặc trưng này có thể là cực trị cục bộ của phép toán DoG (Difference of Gaussian) hoặc là cực đại của phép toán LoG (Laplace of Gaussian). - Sau đó, vùng xung quanh các điểm đặc trưng được xác định và mô tả bằng các véc tơ mô tả cục bộ. - Véc tơ mô tả SIFT được đánh giá rất cao bởi giới chuyên môn trong việc biểu diễn các vùng xung quanh điểm đặc trưng bởi vì nó không đổi đối với những biến đổi tỉ lệ, tịnh tiến, phép quay, và không đổi một phần với đối với những thay đổi về góc nhìn, đồng thời nó cũng rất mạnh với những thay đổi về độ sáng, sự che khuất, nhiễu.. - Hình 2 minh hoạ một ví dụ của véc tơ mô tả SIFT được xây dựng từ vùng cục bộ xung quanh một điểm đặc trưng. - Lúc này, mỗi ảnh được biểu diễn bởi một tập các véc tơ mô tả SIFT.. - Tiếp theo, một ảnh sẽ được biểu diễn bằng tần số của các từ trực quan trong ảnh. - Hình 3 mô tả các bước tạo mô hình BoW biểu diễn các ảnh.. - Hình 2: Đặc trưng cục bộ SIFT được tính toán từ vùng xung quanh điểm đặc biệt (vòng tròn):. - Hình 3: Tạo mô hình BoVW để biểu diễn ảnh 3 THUẬT GIẢI GIẢM GRADIENT NGẪU. - Giai đoạn tiền xử lý cho một tập dữ liệu với số chiều rất lớn (ví dụ, 50000 từ trực quan với nhiều đặc trưng đầu vào với mỗi đặc trưng chỉ chứa ít thông tin cho phân lớp). - Giải thuật máy học véc tơ. - hỗ trợ SVM (Vapnik, 95) là mô hình hiệu quả và phổ biến cho vấn đề phân lớp những tập dữ liệu có số chiều lớn. - Xuất phát từ cài đặt hiệu quả giải thuật SVM bằng phương pháp giảm gradient ngẫu nhiên SGD (Bottou &. - Boussquet, 08), chúng tôi phát triển giải thuật MC-SGD cho phân lớp đa lớp tập dữ liệu có số chiều lớn này.. - Khoảng cách lỗi được biểu diễn bởi z i 0 (với x i nằm đúng phía của siêu phẳng hỗ trợ của nó thì khoảng cách lỗi tương ứng z i = 0, còn ngược lại thì z i >. - Phân lớp phần tử x dựa vào dấu của (w.x - b).. - Hình 4: Phân lớp tuyến tính với máy học véctơ hỗ trợ. - Một cài đặt cho giải thuật SVM của (Bottou &. - Boussquet, 08) dựa trên phương pháp giảm gradient ngẫu nhiên, có độ phức tạp tuyến tính với số phần tử dữ liệu. - Giải thuật SGD có độ phức tạp tuyến tính với số phần tử của tập dữ liệu học, phân lớp dữ liệu có số phần tử và số chiều lớn rất hiệu quả (Bottou &. - 3.3 Giải thuật giảm gradient ngẫu nhiên cho phân lớp đa lớp (MC-SGD). - SGD cũng như hầu hết các giải thuật SVM đều xuất phát từ vấn đề phân lớp nhị phân (2 lớp:. - Chúng tôi mở rộng giải thuật SGD để có thể giải quyết vấn đề phân lớp tập dữ liệu có c lớp (c ≥ 3) hay còn gọi là đa lớp.. - Hình 5: Phân lớp đa lớp, 1-vs-all (trái), 1-vs-1 (phải) Để giải quyết phân lớp tập dữ liệu đa lớp,. - giải thuật SVM thường dựa trên 2 phương pháp đơn giản là 1-vs-all (Vapnik, 95) và 1-vs-1 (Krebel, 99).. - Phương pháp 1-vs-all xây dựng c mô hình SVM nhị phân, mô hình thứ t tách lớp t (lớp dương) ra khỏi các lớp khác (âm).. - Phương pháp 1-vs-1 xây dựng c(c-1)/2 mô hình SVM nhị phân, mỗi mô hình tách một cặp 2 lớp.. - Việc phân lớp dựa vào bình chọn khoảng cách đến các siêu phẳng thu được từ SVM nhị phân.. - Như đã chỉ ra trong thực tế của phân lớp kho dữ liệu ảnh rất lớn, hàng chục ngàn lớp (Sanchez &. - Perronnin, 11), (Deng et al., 12), 1-vs-all thì đơn giản cho kết quả tốt cho vấn đề phân lớp ảnh.. - Tuy nhiên, khi áp dụng 1-vs-all vào trong SGD để giải quyết vấn đề đa lớp, chúng ta lại gặp một khó khăn lớn, huấn luyện các SGD nhị phân trên tập dữ liệu mất cân bằng. - Giả sử tập dữ liệu chúng ta có 100 lớp, thì khi sử dụng 1-vs-all, mô hình SGD thứ t tách lớp t (lớp dương chỉ chiếm khoảng 1%) ra khỏi các lớp khác (lớp âm chiếm khoảng 99. - Để giải quyết vấn đề này, chúng tôi đề xuất chiến lược xây dựng balanced bagging cho từng mô hình SGD nhị phân dựa trên lấy mẫu giảm và cập nhật trọng số bất đối xứng. - Huấn luyện mô hình SGD nhị phân tách lớp t (dương, thiểu số). - khỏi các lớp khác (âm, đa số), cần xây dựng k mô hình cơ sở SGD như sau:. - Sử dụng tập mẫu giảm lớp âm và dữ liệu của lớp dương làm tập huấn luyện mô hình cơ sở SGD.. - Huấn luyện SGD nhị phân, chú ý sử dụng công thức (4) với cập nhật trọng số lớn hơn khi phân lớp sai dữ liệu thuộc lớp dương (thiểu số), và trọng số nhỏ hơn khi phân lớp sai dữ liệu thuộc lớp âm (đa số).. - Kết thúc, chúng ta tổng hợp k mô hình cơ sở SGD thu được mô hình SGD nhị phân tách lớp t từ các lớp khác.. - Cần chú ý rằng, balanced bagging sử dụng tập mẫu giảm của lớp âm, giúp cân bằng phân bố dữ liệu giữa 2 lớp, khả năng lấy mẫu một phần tử của lớp dương và lớp âm là gần như nhau khi tiến hành cập nhật w trong (4). - Chính vì lý do đó mà giải thuật MC-SGD sử dụng các balanced bagging có thể phân lớp hiệu quả tập dữ liệu đa lớp.. - 4 KẾT QUẢ THỰC NGHIỆM. - Để tiến hành đánh giá hiệu quả của giải thuật MC-SGD cho phân lớp ảnh đa lớp, chúng tôi đã cài đặt giải thuật MC-SGD bằng ngôn ngữ lập trình C/C. - Ngoài ra, chúng tôi cũng cần so sánh MC- SGD với một giải thuật SVM chuẩn, được sử dụng phổ biến trong cộng đồng máy học là LibSVM (Chang &. - Tất cả các giải thuật đều được thực hiện trên một máy tính cá nhân (Intel 3GHz, 2GB RAM) chạy hệ điều hành Linux.. - Hình 6: Ảnh mẫu trong tập ImageNet 10 lớp Tập dữ liệu thực nghiệm được lấy về từ. - Chúng tôi chọn tập gồm 6675 ảnh của 10 lớp (xem Hình 6). - Chúng tôi tách tập dữ liệu ra thành tập huấn luyện có 4450 ảnh và tập kiểm thử có chứa 2225 ảnh. - Để biểu diễn ảnh bằng mô hình túi từ trực quan, chúng tôi sử dụng giải thuật phát hiện đặc trưng cục bộ Hessian Affine của (Mikolajczyk &. - Sau đó, thực thi giải thuật k-means (MacQueen, 67) để gom nhóm các véc tơ mô tả SIFT vào 50000 clusters tương ứng với 50000 từ trực quan. - Giai đoạn tiền xử lý tạo ra hai tập (bảng) dữ liệu huấn luyện, kiểm thử, tương ứng với 4450 và 2225 phần tử, 50000 chiều và 10 lớp. - Chúng tôi cố gắng thay đổi số clusters (từ trực quan từ 1000 đến 100000) để tìm các kết quả thực nghiệm tốt nhất. - Cuối cùng, chúng tôi thu được độ chính xác ổn định với 50000 từ trực quan.. - Bước tiền xử lý này là duy nhất cho hai giải thuật máy học mà chúng tôi kiểm thử trong bài viết.. - Chúng tôi sử dụng tập huấn luyện để xây dựng mô hình MC-SGD và SVM sử dụng hàm nhân phi tuyến RBF (SVM-RBF). - MC-SGD sử dụng tham số lambda = 0.1 (hằng số quy tắc, dùng điều chỉnh độ rộng lề phân hoạch), lặp 7 chu kỳ (epoch) là hội tụ đến kết quả tốt nhất. - Chúng tôi cố gắng sử dụng hàm nhân RBF của SVM (hàm nhân RBF của hai điểm dữ liệu x i , x j là K[i, j. - Giải thuật SVM sử dụng hàm nhân RBF (với 00001. - Bảng 1: Kết quả phân lớp ảnh. - Lớp MC-SGD. - Hình 7: Kết quả phân lớp ảnh. - So sánh kết quả cho thấy được MC-SGD phân lớp chính xác hơn SVM-RBF. - MC-SGD cho kết quả tốt nhất 8 trong 10 lớp dữ liệu ảnh và cho độ chính xác tổng thể cao hơn gần 5% so với SVM- RBF. - Với các kết quả phân lớp này, chúng tôi tin rằng giải thuật MC-SGD cho phép phân lớp hiệu quả dữ liệu có số chiều lớn thu được từ bước biểu diễn ảnh bằng mô hình túi từ và đặc trưng không đổi SIFT.. - Ý tưởng của việc tăng chiều trong biểu diễn ảnh bằng mô hình túi từ để có thể phân lớp đơn giản bằng mô hình tuyến tính mà không cần đến mô hình phi tuyến là tiếp cận rất hiệu quả. - Khi số chiều dữ liệu là nhỏ, chúng ta cần đến mô hình phi tuyến để giải quyết tốt vấn đề phân lớp. - Tuy nhiên, huấn luyện mô hình phi tuyến có độ phức tạp rất cao so với mô hình tuyến tính. - Nhưng ngược lại, mô hình tuyến tính thì chỉ làm việc tốt trên tập dữ liệu có số chiều lớn. - Chính vì lý do đó, tăng số chiều biểu diễn ảnh bằng mô hình túi từ để có thể sử dụng mô hình phân lớp tuyến tính là ý tưởng tuyệt vời cho cả độ chính xác và thời gian huấn luyện mô hình.. - Chúng tôi đã đề xuất giải thuật phân lớp tuyến tính đa lớp, giảm gradient ngẫu nhiên MC-SGD, cho phép phân lớp hiệu quả dữ liệu có số chiều lớn thu được từ bước biểu diễn ảnh. - Chúng tôi cũng vừa phát triển giải thuật MC- SGD song song cho phép tăng tốc quá trình thực thi trên máy tính có nhiều bộ xử lý, nhóm hay lưới máy tính. - Trong tương lai gần, chúng tôi sử dụng giải thuật MC-SGD song song để thực hiện phân lớp tập dữ liệu thử thách ImageNet-2012 có hơn 1 triệu ảnh, 1000 lớp khác nhau. - Bên cạnh đó, chúng tôi cũng muốn chúng tôi dự định ứng dụng phương pháp đề xuất vào vấn đề phân lớp ảnh, văn bản, video.