Luận văn Tìm hiểu phương pháp học tích cực và ứng dụng cho bài toán lọc thư rác

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CƠNG NGHỆ NGUYỄN THỊ HỒNG HẬU TÌM HIỂU PHƯƠNG PHÁP HỌC TÍCH CỰC VÀ ỨNG DỤNG CHO BÀI TỐN LỌC THƯ RÁC LUẬN VĂN THẠC SĨ Hà Nội - 2011 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CƠNG NGHỆ NGUYỄN THỊ HỒNG HẬU TÌM HIỂU PHƯƠNG PHÁP HỌC TÍCH CỰC VÀ ỨNG DỤNG CHO BÀI TỐN LỌC THƯ RÁC Ngành: Cơng nghệ thơng tin Chuyên ngành: Hệ thống thơng tin Mã số: 60 48 05 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN TRÍ THÀNH Hà Nội - 2011 1 MỤC LỤC DANH SÁCH HÌNH VẼ ................................................................................. 3 DANH SÁCH CÁC BẢNG BIỂU .................................................................. 4 CHƯƠNG I: GIỚI THIỆU ............................................................................. 5 1.1 Giới thiệu đề tài ...................................................................................... 5 1.1.1 Lý do chọn đề tài ................................................................................... 5 1.1.2 Mục tiêu của đề tài ................................................................................ 6 1.1.3 Các giai đoạn thực hiện đề tài ............................................................... 7 1.2 Cấu trúc của luận văn ............................................................................ 8 CHƯƠNG II - TỔNG QUAN VỀ HỌC TÍCH CỰC ................................. 10 2.1 Giới thiệu học tích cực ......................................................................... 10 2.2 Phương pháp học tích cực ................................................................... 13 2.3 Kịch bản học tích cực ........................................................................... 15 2.3.1 Stream_based Sampling ..................................................................... 15 2.3.2 Pool-based Sampling .......................................................................... 15 2.4 Các chiến lược truy vấn trong học tích cực ....................................... 15 2.4.1 Lấy mẫu khơng chắc chắn................................................................... 16 2.4.2 Truy vấn dựa vào hội đồng ................................................................. 17 2.5 So sánh học tích cực học thụ động ...................................................... 17 2.6 Miền ứng dụng của học tích cực ......................................................... 18 2.7 Kết luận ................................................................................................. 19 CHƯƠNG III - MỘT SỐ THUẬT TỐN HỌC TÍCH CỰC .................. 20 3.1 Học tích cực dựa trên perceptron ....................................................... 20 3.1.1 Giới thiệu ............................................................................................ 20 3.1.2 Thuật tốn perceptron ......................................................................... 20 3.1.3 Cải tiến bước cập nhật perceptron ...................................................... 23 3.1.4 Perceptron chỉnh sửa tích cực ............................................................. 25 3.2 Học tích cực với SVM ......................................................................... 27 2 3.2.1 Giới thiệu ............................................................................................ 27 3.2.2 Máy hỗ trợ vector ................................................................................ 27 3.2.3 Version space ...................................................................................... 30 3.2.4 Học tích cực với SVM ........................................................................ 33 3.3 Kết luận ................................................................................................. 39 CHƯƠNG 4. ỨNG DỤNG HỌC TÍCH CỰC CHO BÀI TỐN LỌC THƯ RÁC ....................................................................................................... 40 4.1 Giới thiệu ............................................................................................... 40 4.2 Học tích cực trong bài tốn lọc thư rác .............................................. 41 4.3 Thử nghiệm và kết quả ........................................................................ 43 4.3.1. Cài đặt chương trình thử nghiệm ..................................................... 43 4.3.2. Thu thập và biểu diễn dữ liệu .......................................................... 45 4.3.3. Xây dựng chương trình biểu diễn và tiền xừ lý dữ liệu ................... 48 4.3.4. Kết quả thử nghiệm .......................................................................... 51 4.4 Kết luận ................................................................................................. 57 KẾT LUẬN .................................................................................................... 58 TÀI LIỆU THAM KHẢO ............................................................................ 60 3 DANH SÁCH HÌNH VẼ Hình 2.1 Lược đồ chung cho bộ học thụ động Hình 2.2 Lược đồ chung cho bộ học tích cực Hình 2.3 Lược đồ tổng thể của học tích cực Hình 3.1 Thuật tốn perceptron chuẩn Hình 3.2 Thuật tốn cải tiến percepron chuẩn Hình 3.3 Quy tắc học tích cực là truy vấn các nhãn cho các điểm x trong L Hình 3.4. Phiên bản tích cực của Perceptron đã chỉnh sửa. Hình 3.5 (a) Máy hỗ trợ vector tuyến tính đơn giản. (b) Máy hỗ trợ vector và máy hỗ trợ vector transaction Hình 3.6 Máy hỗ trợ vector sử dụng hàm nhân đa thức bậc 5 Hình 3.7 (a) Tính đối ngẫu trong version space (b) Một bộ phân lớp SVM trên một version space Hình 3.8 (a) Lề đơn giản truy vấn b (b) Lề đơn giản truy vấn a Hình 3.9 (a) Lề MaxMin truy vấn b (b) Lề MaxRatio truy vấn e. Hình 4.1 Bộ lọc thư rác áp dụng phương pháp học tích cực Hình 4.2 Bộ lọc thư rác tích cực dựa trên Perceptron/SVM active Hình 4.3 Giao diện chính của chương trình Hình 4.4 Giao diện lựa chọn thư mục chứ dữ liệu Hình 4.5 Thơng báo quá trình làm sạch dữ liệu thành cơng Hình 4.6 Giao diện thơng báo kết quả xử lý Hình 4.7 Kết quả thuật tốn perceptron Hình 4.8 Cấu trúc file cấu hình của chương trình ActiveExperiment Hình 4.9 Kết quả chạy thuật tốn SIMPLE Hình 4.10 Kết quả chạy thuật tốn SELF_CONF Hình 4.11 Kết quả chạy thuật tốn KFF Hình 4.12. Kết quả chạy thuật tốn BALANCE_EE 4 DANH SÁCH CÁC BẢNG BIỂU Bảng 4.1 Ví dụ nội dung của bốn thư Bảng 4.2 Từ điển và chỉ số cho dữ liệu trong bảng 4.1 Bảng 4.3 Biểu diễn vector cho dữ liệu trong bảng 4.1 Bảng 4.4 Kết quả chạy qua 20 lần truy vấn của các thuật tốn 5 CHƯƠNG I: GIỚI THIỆU 1.1 Giới thiệu đề tài 1.1.1 Lý do chọn đề tài Ngày nay thư điện tử (email) đã trở thành một cơng cụ đắc lực phục vụ cho nhu cầu trao đổi thơng tin của các cơ quan tổ chức, doanh nghiệp cũng như mỗi cá nhân. Email giúp con người cĩ thể kết nối mọi nơi, mọi lúc với cơng việc và cuộc sống cá nhân. Tuy nhiện thư điển tử cũng đang bị lợi dụng để phát tán thư rác (spam) lây lan virus máy tính và lừa đảo trực tuyến, gây thiệt hại lớn cho người sử dụng. Thư rác là thư điện tử được gửi hàng loạt với nội dung mà người nhận khơng mong đợi, khơng muốn xem, hay chứa những nội dung khơng liên quan đến người nhận và thường được sử dụng để gửi thơng tin quảng cáo. Do cĩ giá thành tương đối thấp so với các phương pháp quảng cáo khác, thư rác hiện chiếm một tỷ lệ lớn và ngày càng tăng trong tổng số thư điện tử được gửi qua Internet. Sự xuất hiện và gia tăng thư rác khơng những gây khĩ chịu và làm mất thời gian của người nhận mà cịn ảnh hưởng tới đường truyền Internet và làm chậm tốc độ xử lý của máy chủ thư điện tử, gây thiệt hại lớn về kinh tế. Thư rác là một trong những thách thức lớn nhất hiện nay mà khách hàng và các nhà cung cấp dịch vụ phải đối phĩ. Spam đã trở thành một hình thức quảng cáo chuyên nghiệp, phát tán virus, ăn cắp thơng tin... với nhiều thủ đoạn và mánh khĩe cực kỳ tinh vi. Người dùng sẽ phải mất khá nhiều thời gian để xĩa những thư điện tử “khơng mời mà đến”, nếu vơ ý cịn cĩ thể bị nhiễm virus, trojan, spyware ... và nặng nề hơn là mất thơng tin như thẻ tín dụng, tài khoản ngân hàng qua các email dạng thư lừa người dùng tưởng đĩ là thư hợp lệ (phishing). Để loại bỏ hoặc giảm thiểu ảnh hưởng của thư rác, nhiều cách tiếp cận khác nhau đã được nghiên cứu và sử dụng. Giải pháp đấu tranh với thư rác rất đa dạng, bao gồm từ các cố gắng về pháp lý trong việc xây dựng luật ngăn chặn phát tán thư rác cho tới những giải pháp kỹ thuật nhằm phát hiện và 6 ngăn chặn thư rác trong những giai đoạn khác nhau của quá trình tạo và phát tán thư. Tất nhiên, những kẻ gửi thư rác sẽ liên tục cải thiện chiến thuật/cách thức của chúng, do đĩ, điều quan trọng là biện pháp ngăn chặn thư rác phải “học” cách thức thay đổi của thư rác theo thời gian để giúp việc ngăn chặn cĩ hiệu quả. Và việc ngăn chặn thư rác phải được thực hiện nhanh nhất cĩ thể để khơng làm ảnh hưởng đến hệ thống, cơng việc khác. Từ những đặc điểm của hệ thống thư điện tử như cĩ sự tương tác với người sử dụng và sự biến đổi của thư rác, luận văn nghiên cứu về học tích cực và xác định được sự phù hợp cho bài tốn lọc thư rác. Đề tài “Tìm hiểu phương pháp học tích cực và ứng dụng cho bài tốn lọc thư rác” được tiến hành nhằm đưa ra được phương pháp xây dựng bộ lọc thư rác cĩ thể “học” được cách thức thay đổi của thư rác và tận dụng được sự tương tác với người dùng để đưa ra các truy vấn phân loại cho thư điện tử giúp cho việc phân loại thư rác đạt hiệu quả và chính xác cao. Trong phạm vi đề tài, luận văn tiến hành nghiên cứu một số giải pháp học thư rác dựa vào các phương pháp học tích cực (bộ lọc tích cực). Nội dung nghiên cứu bao gồm cả thử nghiệm trên dữ liệu thực làm rõ khả năng lọc thư của các bộ lọc tích cực, so sánh hiệu quả của các phương pháp được áp dụng trong bộ lọc. 1.1.2 Mục tiêu của đề tài Để loại bỏ thư rác, các nhà cung cấp dịch vụ thư điện tử đã tích hợp nhiều chương trình lọc thư rác vào dịch vụ thư điện tử. Các chương trình lọc thư rác chủ yếu dựa vào các phương pháp học máy thơng qua một bộ học. Tuy nhiên dựa vào thực tế: thư điện tử là một dịch vụ online, các thư điện tử được cập nhật thay đổi theo thời gian và cĩ sự tương tác của người sử dụng hịm thư với hệ thống vì vậy đề tài đã tập trung vào nghiên cứu bộ học tích cực và áp dụng cho bài tốn lọc thư rác. 7 Trên cơ sở xác định loại hình nghiên cứu của đề tài là nghiên cứu lý thuyết và ứng dụng thực nghiệm, mục tiêu của đề tài là tìm hiểu về phương pháp học tích cực và tìm giải giải pháp cho bài tốn lọc thư rác, chọn mơ hình thích hợp để áp dụng vào bài tốn lọc thư rác với các tiêu chí: - Lọc thư rác nhanh, phát hiện chính xác thư rác (spam mail). - Tận dụng được khả năng tương tác với người sử dụng dịch vụ mail, sự phân loại mail của người dùng để tăng thêm lượng mail đã gán nhãn cũng như chất lượng của dữ liệu gán nhãn. - Cĩ khả năng thích nghi với các biến thể của thư rác, chủ động lọc loại ra các thư rác ngày một hoạt động tinh vi hơn. Giống như trong lĩnh vực phịng chống virus máy tính, hacker luơn tìm cách để chống lại các chương trình diệt virus, thì trong chương trình lọc thư rác, những người gửi thư rác luơn tìm cách để tránh được bộ lọc thư rác một cách hữu hiệu. Vì vậy mà thư rác luơn luơn được biến đổi, cải tiến hơn do những người gửi thư rác. Sử dụng phương pháp học tích cực cho bài tốn lọc thư rác làm phong phú thêm tập lời giải cho bài tốn nhận dạng các đối tượng biến đổi. Bộ lọc thư rác tích cực giảm chi phí và thời gian thu thập dữ liệu, bởi vì nĩ được xây dựng dựa trên sự tương tác giữa bộ học và người dùng là nhận dạng thư rác hay thư thường. Với mục tiêu đã nêu ở trên luận văn chủ yếu tập trung nghiên cứu vào phương pháp học tích cực, áp dụng được các bộ học để tìm ra lời giải cho bài tốn lọc thư rác. Để kiểm tra và đánh giá kết quả, luận văn sử dụng các chương trình thực nghiệm đã cài đặt sẵn các bộ học mà luận văn nghiên cứu, thu thập dữ liệu thực tế, xây dựng chương trình xử lý dữ liệu thành các tri thức để huấn luyện các bộ học thực nghiệm nhằm phát hiện ra các thư rác một cách chính xác và đạt hiệu quả cao. 1.1.3 Các giai đoạn thực hiện đề tài Quá trình nghiên cứu của luận văn được thực hiện qua các giai đoạn sau: 8 Giai đoạn 1 – Nghiên cứu lý thuyết: Thu thập tài liệu, các bài viết liên quan đến học tích cực và phương pháp lọc mail. Nghiên cứu tài liệu, tìm hiểu phương pháp học học máy nĩi chung và phương pháp học tích cực nĩi riêng. Tìm hiểu cụ thể vào pương pháp học tích cực dựa vào perceptron và học tích cực với SVM. Tìm hiểu một số phương pháp lọc mail, tham khảo một số mơ hình lọc mail đã được xây dựng. Trên cơ sở khoa học và lý thuyết đã tìm hiểu lựa chọn phương pháp và áp dụng trong thực tế. Giai đoạn 2 – Xây dựng chương trình tiền xử lý dữ liệu để làm dữ liệu cho bài tốn lọc mail. Tìm hiểu và cài đặt các cơng cụ cĩ ứng dụng cho bài tốn lọc mail. Thu thập dữ liệu từ thực tế, sử dụng chương trình cĩ sẵn, xử lý dữ liệu và chạy thực nghiệm dữ liệu trên các cơng cụ đã cài đặt được. Phân tích đánh giá và nhận xét kết quả thực nghiệm Giai đoạn 3 – Tổng kết: Khái quát hĩa và rút ra kết luận chung cho đề tài. Viết báo cáo, cơng bố kết quả nghiên cứu trong đề tài. 1.2 Cấu trúc của luận văn Luận văn gồm bốn chương: Chương 1 dẫn nhập và giới thiệu chung về luận văn, lý do chọn đề tài, mục tiêu của đề tài và ý nghĩa của đề tài. Chương này cũng trình bày các giai đoạn thực hiện luận văn và cấu trúc của luận văn. Chương 2: trình bày các cơ sở lý thuyết phục vụ cho bài tốn lọc mai. Cụ thể chương 2 sẽ giới thiệu về phương pháp học tích cực. Đưa ra mơ hình học tích cực, so sánh giữa hai mơ hình học thụ động và học tích cực. Từ đĩ nêu ra được ưu điểm của học tích cực và các miền ứng dụng. Chương 3: sẽ trình bày về các mơ hình học tích cực. Đầu tiên, Chương 3 trình bày cơ sở lý thuyết của phương pháp học tích cực dựa vào perceptron sử dụng cải tiến bước cập nhật. Cuối Chương 3 trình bày về học tích cực với SVM, giới thiệu ba phương pháp truy vấn trong bộ học SVM: Simple Margin, MaxMin Margin và Ratio Margin. Chương 4: Giới thiệu bài tốn lọc thư rác, phương pháp học tích cực trong bài tốn lọc thư rác. Chương 4 sử dụng phương pháp học tích cực dựa vào Perceptron và SVM active vào xây dựng mơ hình cho bài tốn lọc thư rác. 9 Phần cuối chương 4: Cài đặt các tool thực nghiệm và xây dựng chương trình xử lý dữ liệu thu thập được về dạng dữ liệu đầu vào cho các tool thực nghiệm. Phân tích, đánh giá và nhận xét kết quả thực nghiệm. Phần Kết luận: tổng kết lại những kết quả đã thực hiện được trong luận văn và đưa ra phương hướng phát triển luận văn trong tương lai. 10 CHƯƠNG II - TỔNG QUAN VỀ HỌC TÍCH CỰC 2.1 Giới thiệu học tích cực Mục đích chính của học máy là thu được những mẫu chung từ một lượng dữ liệu hữu hạn [36]. Học máy được chia thành 2 loại: học cĩ giám sát và học khơng giám sát. Nhiệm vụ của học giám sát là dự đốn thêm những các đặc trưng của một đối tượng đầu vào [36]. Ví dụ: đơn giản là bài tốn dự dốn cân nặng của một người khi biết chiều cao của họ, cịn những bài tốn phức tạp hơn cĩ thể là dự đốn chủ đề của hình ảnh khi biết các giá trị của điểm ảnh. Một lĩnh vực trọng tâm của học giám sát là bài tốn phân lớp. Phân lớp là bài tốn học cĩ giám sát mà ở đĩ đặc trưng nữa của một đối tượng mà chúng ta mong muốn dự đốn là các giá trị rời rạc. Ta gọi đặc trưng này là nhãn. Mục đích của phân lớp là tạo ra một ánh xạ các đối tượng đầu vào tới các nhãn.Ví dụ, phân loại các tài liệu trong đĩ chúng ta mong muốn gán nhãn tự động cho một tài liệu mới với một vài chủ để đã xác định trước (ví dụ thể thao, chính trị, kinh doanh…). Hướng tiếp cận của học máy để giải quyết được vấn đề này là chúng ta phải thu thập được tập huấn luyện (trainning set) bằng cách gán nhãn tự động một số các tài liệu. Tiếp theo chúng sử dụng một bộ học (learner) thực hiện trên tập huấn luyện đã được gán nhãn để sinh ra một ánh xạ từ các tài liệu đến chủ đề. Chúng ta gọi ánh xạ này là bộ phân lớp (classifier). Chúng ta cĩ thể dùng bộ phân lớp (classifier) để gán nhãn cho các tài liệu mới. Một lĩnh vực lớn nữa của học máy là học khơng giám sát. Khoảng cách giữa học giám sát và học khơng giám sát cũng khơng hồn tồn rõ ràng. Tuy nhiên bản chất của học khơng giám sát là chúng ta sẽ khơng nhận được thơng tin cụ thể về cách thức thực hiện như thế nào. Nĩi cách khác, trong bài tốn phân lớp chúng ta nhận được tập dữ liệu huấn luyện đã được gán nhãn tự động. Học khơng giám sát bao gồm bài tốn phân cụm (Ở đây chúng ta sẽ cố tìm nhĩm dữ liệu tương tự nhau) và xây dựng mơ hình (chúng ta cố gắng xây dựng một mơ hình miền từ một tập dữ liệu). Tất cả các bài tốn học giám sát và khơng giám sát, đầu tiên là thu thập 11 đầy đủ lượng dữ liệu sao cho được đánh mẫu tự động từ sự phân bố mật độ cơ bản và sau đĩ chúng ta quy vào một lớp hay một mơ hình. Phương pháp này được gọi là học thụ động. Bộ học thụ động nhận dữ liệu một cách ngẫu nhiên từ thế giới (hình 2.1) và sau đĩ đưa ra mơ hình để phân lớp. Thơng thường những bài tốn mất nhiều thời gian và chi phí trong các ứng dụng là thu thập dữ liệu. Trong một số trường hợp, chúng ta cĩ giới hạn các tài nguyên cho việc thu thập dữ liệu. Do đĩ, rất là quan trọng khi xác định cách để chúng ta cĩ thể sử dụng những tài nguyên này càng nhiều càng tốt. Hầu như trong tất cả các trường hợp chúng ta đều cho rằng thu thập các thể hiện dữ liệu một cách ngẫu nhiên là độc lập và phân bố tương tự nhau. Tuy nhiên, trong một số trường hợp chúng ta cĩ thể cĩ cách hướng dẫn quá trình lấy mẫu. Ví dụ, trong bài tốn phân lớp tài liệu, thường rất dễ thu thập một lượng lớn các tài liệu chưa gán nhãn. Thay vì lựa chọn tài liệu một cách ngẫu nhiên để gán nhãn cho tập huấn luyện, chúng ta cĩ quyền lựa chọn (yêu cầu) cẩn thận một số tài liệu để gán nhãn. Trong bài tốn ước lượng tham số và phát hiện cấu trúc, giả sử chúng ta nghiên cứu bệnh ung thư phổi trong ngành y: v Chúng ta cĩ một danh sách sơ bộ ban đầu về tuổi và sở thích hút thuốc của những người cĩ khả năng mắc bệnh để chúng ta cĩ quyền lựa chọn hướng kiểm tra thêm. v Chúng ta cĩ khả năng đưa ra chỉ với một số người bản kiểm tra chi tiết. Thay vì chọn ngẫu nhiên một số người để kiểm tra thì ta đặt ra yêu cầu với những người phù hợp với các đặc điểm nào đĩ. Ví dụ Chúng ta muốn kiểm tra những người hút thuốc và trên 50 tuổi. v Hơn nữa, chúng ta khơng cần phải đưa ra các danh sách câu hỏi trước. Chúng ta cĩ thể chọn câu hỏi tiếp theo dựa trên các câu trả lời của các câu hỏi trước. Quá trình hướng dẫn các bước lấy mẫu bằng câu hỏi cho một số trường hợp nào đĩ căn cứ vào dữ liệu mà chúng ta đã được cung cấp gọi là học tích cực. 12 Hình 2.1 Lược đồ chung cho bộ học thụ động Hình 2.2: Lược đồ chung cho bộ học tích cực. Học tích cực (đơi khi cịn được gọi là học truy vấn hay thiết kế thực nghiệm tối ưu trong các bài tốn thống kê) là một lĩnh vực nhỏ của học máy nĩi riêng và trong trí tuệ nhân tạo nĩi chung. Giả thiết chính là nếu thuật tốn học được phép chọn dữ liệu từ những gì nĩ học thì nĩ sẽ thực hiện tốt hơn ngay cả khi được huấn luyện ít hơn. Hệ thống học tích cực cố gắng vượt qua những hạn chế trong việc gán nhãn bằng cách đưa ra các truy vấn để các dữ liệu chưa gán nhãn sẽ được người sử dụng hay chuyên gia gán nhãn. Bằng cách này, bộ học tích cực hướng đến việc đạt được độ chính xác cao trong việc sử dụng dữ liệu gán nhãn càng ít càng tốt, do đĩ sẽ giảm thiểu được chí phí trong việc thu thập dữ liệu cĩ nhãn. Học tích cực được coi là một hướng tiếp cận cĩ mục đích tốt trong các bài tốn học máy hiện đại mà dữ liệu cĩ thể bị dư thừa nhưng các nhãn thì khan hiếm hoặc là tốn chi phí mới cĩ được. Học tích cực là một trong những phương pháp học giám sát [7] tạo ra những dữ liệu được gán nhãn với sự giúp đỡ của con người trong những vịng lặp cĩ phản hồi [5]. Bộ học tập trung vào việc huấn luyện sử dụng một lượng nhỏ dữ liệu đã gán nhãn và làm giảm số các nhãn mà người sử dụng cĩ để Thế giới Bộ học thụ động Mơ hình hoặc bộ phân lớp Dữ liệu Dữ liệu ra Thế giới Bộ học tích cực Mơ hình /Bộ phân lớp Dữ liệu đã gán nhãn/chưa gán nhãn Truy vấn Phản hồi Dữ liệu ra 13 phân lớp bằng cách chọn các dữ liệu cĩ nhiều thơng tin nhất. Điều này chỉ ra rằng ta chỉ cần một phần nhỏ dữ liệu trong tập dữ liệu lớn phải gán nhãn để huấn luyện một bộ học sao cho đạt được bộ phân lớp tốt. Vì trong học giám sát dữ liệu cần thiết phải sử dụng dữ liệu đã gán nhãn, nên bài tốn gán nhãn thường rất tốn thời gian và chi phí. Động lực đằng sau học tích cực là tối đa hĩa hiệu suất bằng cách giảm thiểu cơng sức của con người trong việc gán nhãn dữ liệu càng nhiều càng tốt [9]. Một đặc điểm nữa của học tích cực là nĩ là một quá trình lặp đi lặp lại [5]. Trong mỗi lần lặp, đầu tiên bộ học được huấn luyện với dữ liệu huấn luyện, sau đĩ một tập nhỏ dữ liệu chưa cĩ nhãn được lựa chọn và đưa cho người sử dụng (hoặc chuyên gia) gán nhãn cho chúng, và cuối cùng dữ liệu vừa được gán nhãn sẽ được thêm vào tập huấn luyện ban đầu và bộ học sẽ lại được huấn luyện lại. Quá trình này được lặp đi lặp lại cho đến khi chấm dứt. 2.2 Phương pháp học tích cực Bước chính trong phương pháp học tích cực là định nghĩa khái niệm mơ hình M và chất lượng mơ hình (mơ hình tổn thất, Loss(M)). Định nghĩa mơ hình và chất lượng mơ hình tương ứng sẽ được thay đổi phù hợp đối với từng bài tốn riêng. Với khái niệm tổn thất của mơ hình đã đưa ra, chúng ta lựa chọn câu truy vấn tiếp theo sao cho nĩ sẽ đưa đến một mơ hình mới với độ tổn thất của mơ hình là thấp nhất. Khi đang xem xét việc đưa ra câu truy vấn tiềm năng q, ta cần ước định độ tổn thất của mơ hình tiếp theo M’. Mơ hình M’ là mơ hình M được cập nhật với câu truy vấn q và câu trả lời x. Vì khơng biết câu trả lời x cĩ đúng với câu truy vấn tiếp theo khơng, nên ta phải thực hiện một số phép tổng hợp và phép tính trung bình. Một phương pháp tự nhiên là duy trì bộ phân phối các câu trả lời hợp với mỗi câu truy vấn. Ta cĩ thể tính được độ tổn thất kỳ vọng của mơ hình sau khi đưa ra câu truy vấn mà chúng ta đạt được độ kỳ vọng ở câu trả lời cho câu truy vấn đĩ: 14
  
  (2.1) Nếu sử dụng định nghĩa này trong thuật tốn học tích cực thì cĩ thể chọn các câu truy vấn sao cho độ tổn thất kỳ vọng của mơ hình là thấp nhất. Dựa vào nhưng phân tích ở trên Tong [36] đã đưa ra lược đồ tổng thể của học tích cực như trong hình 2.3 For i:=1 to totalQueries ForEach q in potentialQueries Evaluate Loss(q) EndForEach Ask truy vấn q sao cho Loss(q) là thất nhất Update cập nhật mơ hình M với truy vấn q và phản hồi x EndFor Return mơ hình Hình 2.3 Lược đồ tổng thể của học tích cực [36] Trong thống kê, sự lựa chọn chuẩn để tối thiểu độ tổn thất kỳ vọng chínhlà tối thiểu được độ tổn thất cực đại [3]. Nĩi các khác, nếu giả sử các trường hợp đều là xấu nhất: điều này cĩ nghĩa là câu trả lời x sẽ luơn là câu trả lời cho độ tổn thất của mơ hình là cao nhất.
   
  (2.2) Nếu chúng ta sử dụng định nghĩa độ tổn thất này cho câu truy vấn trong thuật tốn học tích cực thì chúng ta nên lựa chọn câu truy vấn cho kết quả đạt độ tổn thất mơ hình lớn nhất. 15 2.3 Kịch bản học tích cực Cĩ một vài kịch bản học trong một số bài tốn khác nhau, trong đĩ bộ học cĩ thể đưa ra câu truy vấn. Tuy nhiên cĩ hai kịch bản chính, khá phổ biến trong các nghiên cứu và thường xuyên được sử dụng trong các bài tốn áp dụng phương pháp học tích cực. Hai kịch bản học đĩ là stream-based sampling và pool-based sampling. 2.3.1 Stream-based sampling Trong kịch bản ‘stream-based sampling’, bộ học lấy một mẫu tại một thời điểm nào đĩ từ các dữ liệu phân tán và cố gắng đưa ra một quyết định trên mẫu này là cĩ lựa chọn và đem nĩ ra để hỏi người dùng ghi nhãn cho nĩ hoặc sẽ bỏ qua nĩ. 2.3.2 Pool-based sampling Trong kịch bản ‘pool-based sampling’, đầu tiên bộ học lấy tất cả các mẫu và xếp hạng chúng tăng dần dựa trên dự đốn của bộ phân lớp. Sau đĩ, bộ học sẽ chọn k mẫu đầu tiên của danh sách xếp hạng trong mỗi lần lặp và đưa chúng cho từng người sử dụng một để ghi nhãn. Trong kịch bản ‘pool-based sampling’, dữ liệu chưa gán nhãn là cố định và khơng thay đổi; trong khi kịch bản ‘stream-based scenario’ là một phiên bản trực tuyến của kịch bản ‘pool-based sampling’ vì ngay lập tức nĩ yêu cầu người sử dụng gán nhãn sau khi nĩ được phân lớp [44]. Chúng ta cĩ thể kết luận rằng kịch bản ‘stream-based scenario’ khác biệt với kịch bản ‘pool-based sampling’ về việc liệu trong mơ hình các mẫu được chọn cĩ được hỏi người sử dụng nhãn ngay lập tức khơng hoặc lúc đầu tất cả các mẫu được xếp hạng và từ dữ liệu đã xếp hạng này cĩ được lựa chọn để được gán nhãn. 2.4 Các chiến lược truy vấn trong học tích cực Các mẫu được chọn phải cĩ rất nhiều thơng tin cĩ hiệu quả cho bài 16 tốn. Để làm được việc lựa chọn mẫu, cĩ một số phương pháp truy vấn độc lập với kịch bản học tích cực đã giới thiệu giới thiệu ở trên. Trong số các phương pháp truy vấn được sử dụng trong các ứng dụng khác nhau của phương pháp học tích cực, Settles [6][7] đã trình bày việc phân loại hồn chỉnh nhất và tồn diện nhất cho các phương pháp truy vấn này. Trong đĩ cĩ hai phương pháp được sử dụng rộng rãi nhất đĩ là lấy mẫu khơng chắc chắn và truy vấn dựa trên hội đồng (Query by committee). 2.4.1 Lấy mẫu khơng chắc chắn Phương pháp lựa chọn mẫu nổi tiếng nhất và đơn giản là "lấy mẫu khơng chắc chắn" (Uncertainty Sampling) được giới thiệu bởi Lewis và Gale [14]. Trong phương pháp này, bộ học tích cực đưa ra các mẫu tới người sử dụng là khơng chắc chắn. Xét các dự đốn của bộ phân lớp cho dữ liệu khơng cĩ nhãn, ta sẽ cĩ một đường biên giữa các mẫu khơng cĩ thơng tin và các mẫu cĩ chứa thơng tin. Các mẫu khơng cĩ thơng tin là những mẫu cần cĩ sự dự đốn chắc chắn cao nhất cho việc gán nhãn; vì thế các mẫu kiểu này khơng phải là hữu ích cho học tích cực và cũng khơng cần thiết để hỏi nhãn cho chúng. Các mẫu cĩ thơng tin là các mẫu mà bộ phân lớp khơng cần phải cĩ một dự đốn tốt cho việc gán nhãn với sự tự tin cao. Do vậy những dữ liệu cĩ độ chắc chắn thấp hơn sẽ hữu ích cho bộ học tích cực. Đường biên giữa các mẫu chứa thơng tin và mẫu khơng chứa thơng tin cĩ thể được định nghĩa với một số điểm như độ tin cậy của bộ phân lớp cho các nhãn mà nĩ đã gán. Trong thực tế ‘độ tin cậy’ là sự dự đốn của bộ phân lớp với xác suất cao nhất cho các nhãn của mẫu [5]. Vì nĩ cĩ thể được nhận ra, nên trong việc lấy mẫu khơng chắc chắn chỉ cĩ một bộ phân lớp là cần thiết cho mơ hình [21]. Cĩ một số cách tính độ tin cậy mà bộ phân lớp sử dụng. Trong số đĩ, cĩ ‘entropy’ được Shannon [11] đề xuất là một trong những cách phổ biến nhất. Sử dụng entropy là độ tin cậy, các mẫu cĩ entropy cao sẽ là các mẫu chứa thơng tin nhiều nhất vì dự đốn của bộ phân lớp cho các mẫu đĩ là thấp 17 và các mẫu này sẽ là các ứng cử viên tốt nhất được lựa chọn và đưa ra cho người sử dụng gán nhãn. 2.4.2 Truy vấn dựa vào hội đồng Seung cùng cộng sự [20] và Freund cùng cộng sự [45] đề xuất một phương pháp truy vấn được sử dụng rộng rãi được gọi là truy vấn dựa vào hội đồng (query by committee). Trong phương pháp này nhiều hơn một bộ phân lớp được sử dụng và mỗi bộ phân lớp cố gắng để lấy các mẫu chứa nhiều thơng tin nhất. Trong số các mẫu chứa thơng tin được lựa chọn cho mỗi bộ phân lớp, các mẫu mà cĩ độ bất đồng lớn nhất giữa các bộ phân lớp sẽ được lựa chọn và đưa ra cho người sử dụng gán nhãn. 2.5 So sánh học tích cực học thụ động • Bộ học Một bộ học tích cực thu thập thơng tin bằng cách đưa ra các câu truy vấn và nhận lại các câu trả lời. Sau đĩ nĩ đưa ra bộ phân lớp hoặc mơ hình cĩ thể sử dụng được cho bài tốn của mình. Bộ học tích cực khác với bộ học thụ động ở chỗ bộ học thụ động nhận thơng tin một cách ngẫu nhiên và sau đĩ đưa ra bộ phân lớp và mơ hình. Một điểm khác nữa là bộ học thụ động chuẩn giống như một sinh viên thu thập thơng tin bằng cách chỉ ngồi và lắng nghe giáo viên trong khi bộ học tích cực là người đặt ra câu hỏi cho giáo viên, nghe câu trả lời và hỏi thêm dựa trên câu trả lời của giáo viên. Rất hợp lý khi đưa ra câu hỏi dựa trên câu trả lời trước đĩ sẽ cho phép bộ học tích cực thực hiện tốt hơn bộ học thụ động. • Thành phần truy vấn Điểm khác chủ yếu giữa bộ học tích cực và bộ học thụ động là khả năng đặt câu hỏi vào câu hỏi và câu trả lời trước. Khái niệm về câu hỏi và câu trả lời chính xác là gì sẽ phụ thuộc vào các bài tốn cụ thể tiếp theo. Khả năng sử dụng phương pháp học tích cực sẽ được lựa chọn tùy vào từng trường hợp, từng bài tốn cụ thể. 18 2.6 Miền ứng dụng của học tích cực Học tích cực được áp dụng trong rất nhiều ứng dụng khác nhau, nhưng đặc biệt gần đây người ta lại chú ý đến phương pháp học tích cực trong lĩnh vực xử lý ngơn ngữ tự nhiên. Ngồi ra học tích cực cũng được sử dụng trong nhiều ứng dụng như: • Nhận dạng giọng nĩi (Hakkani-Tür et al., 2002), hiểu ngơn ngữ nĩi (Tur et al., 2003; 2005). • Phân tích cú pháp (Thompson và cộng sự, 1999; Hwa, 2000; Tang và cộng sự, 2002;. Hwa và cộng sự, 2003;. Steedman và cộng sự, 2003;. Baldbridge và Osborne, 2003; 2004; 2006; Osborne và Baldridge, 2004, Becker và Osborne, 2005) • Khai thác thơng tin (Thompson et al., 1999; Settles and Craven, 2008), tìm kiếm thơng tin (Zhang and Chen, 2002; Yu, 2005), • Phân lớp tài liệu (Schohn and Cohn, 2000; Roy and McCallum, 2001), • Lọc thư rác (Sculley, 2008) • Tìm kiếm hình ảnh (Tong, Simon Tong 2001) • Phân lớp văn bản (Lewis and Gale, 1994; McCallum and Nigam, 1998; Tong and Koller, 2001; Zhu et al., 2003; Baldbridge and Osborne, 2006; Zhu et al., 2008ab, Lewis and Catlett, 1994; Liere and Tadepalli, 1997; Hoi et al., 2006), • Phân đoạn tài liệu (Settles and Craven, 2008), • Phân đoạn từ vựng (Sassano, 2002), word sense disambiguation (Fujii et al., 1998; Dang, 2004; Chen et al., 2006; Chan and Ng, 2007; Zhu and Hovy, 2007; Zhu et al., 2008ab), • Nhận dạng chữ số viết tay (Zhu et al., 2003), • Dịch máy (machine translation) (Haffari and Sarkar, 2009; Haffari et al., 2009), • Nhận dạng thực thể ghi tên (Shen et al., 2004; Laws and Schütze, 2008), 19 2.7 Kết luận Trong chương này đã trình bày cơ sở lý thuyết của học tích cực. Giới thiệu học tích cực là gì, phương pháp học tích cực, các kịch bản và các phương pháp truy vấn. Tĩm lại, phương pháp học tích cực được tĩm tắt lại như sau: Đầu tiên chúng ta chọn một mơ hình và độ tổn thất mơ hình thích hợp với bài tốn học. Sau đĩ chúng ta cũng chọn một phương pháp cho việc tính độ tổn thất mơ hình tiềm năng đưa ra câu truy vấn tiềm năng. Với mỗi câu truy vấn chúng ta đánh giá độ tổn thất tiềm năng và chúng ta lựa chọn để đưa ra câu truy vấn, câu truy vấn này sẽ đưa ra được độ tổn thất mơ hình tiềm năng thấp nhất. 20 CHƯƠNG III - MỘT SỐ THUẬT TỐN HỌC TÍCH CỰC Chương này sẽ giới thiệu một số thuật tốn học tích cực. Cụ thể sẽ đi vào giới thiệu hai thuật tốn phổ biến là perceptron và Active SVM. 3.1 Học tích cực dựa trên perceptron 3.1.1 Giới thiệu Một trong những phương pháp tiếp cận ra đời sớm nhất cho vấn đề phân lớp tuyến tính trong học máy là thuật tốn Perceptron. Perceptron được Rosenblatt đề xuất năm 1958 [17], chiếm một vị trí quan trọng trong lịch sử của các thuật tốn nhận dạng mẫu.Perceptron là một bộ phân lớp tuyến tính và là một phần của học máy kể từ những năm 1958 và đã cĩ nhiều phân tích lý thuyết về nĩ. Phần này sẽ trình bày thuật tốn học tích perceptron chuẩn và thuật tốn perceptron tích cực cĩ cải tiến bước cập nhật do Dasgupta đề xuất năm 2005 [32]. 3.1.2 Thuật tốn perceptron Cho tập dữ liệu học           với    và    là một số nguyên xác định  là dữ liệu dương (+1) hay âm (-1). Một tài liệu  được gọi là dữ liệu dương nếu nĩ thuộc lớp !;  được gọi là dữ liệu âm nếu nĩ khơng thuộc lớp !. Bộ phân lớp tuyến tính được xác định bằng siêu phẳng chia dữ liệu thành vào các lớp thuộc tính. Tập các giả thiết như vậy ta cĩ: " #  $% $&  ' (3.1) Trong đĩ $  và $&   là các hệ số cĩ thể điều chỉnh đĩng vai trị là tham số của mơ hình. Hàm phân lớp nhị phân h: Rm → {0,1}, cĩ thể thu được bằng cách xác định dấu của (: 21 )  *+ế,+# - ''+ế,+# . '/+ 3.2+ Như vậy việc học mơ hình phân lớp chính là việc xác định siêu phẳng từ dữ liệu. Với thuật tốn này, mỗi dữ liệu được xem là một điểm trong mặt phẳng. Dữ liệu học là tách rời tuyến tính (linearly separable) nếu tồn tại một siêu phẳng sao cho hàm phân lớp phù hợp với tất cả các nhãn, tức là # - ' với mọi i = 1,...,n. Với giả thuyết này, Rosenblatt đã đưa ra một thuật tốn lặp đơn giản để xác định siêu phẳng: Mục đích của thuật tốn Perceptron là tìm ra được một siêu phẳng bằng cách làm giảm thiểu đi khoảng cách của các điểm dữ liệu phân lớp nhầm (misclassified) tới đường biên quyết định. Nĩ bắt đầu với việc dự đốn các tham số ban đầu cho mặt phẳng phân cách, và sau đĩ khi cĩ những sai lầm xảy ra thì nĩ cập nhật lại việc dự đốn trước đĩ. Perceptron Khởi tạo các giả thiết ban đầuv0 For t=0 to n do Dự đốn: if #3 . 3 4 '+then 53  678#3 . 3 else 53  678#3 . 3 Bước lọc: quyết định hỏi nhãn yt của điểm xt Cập nhật: If 3#3. 3 9 ' then #3:;  #3 3 . 3 Bước lọc phù hợp else #3:;  #3 Hình 3.1 Thuật tốn perceptron chuẩn [32] 22 Thuật tốn chọn tập các giả thiết như là mơ hình của thuật tốn và lỗi tổng quát của mỗi giả thiết làm độ tổn thất của mơ hình. Với giả thiết # bất kỳ thuộc Rd sẽ cĩ miền lỗi ξ3    6<678#3.  = 678,. , u là vector đơn vị. Do đĩ thuật tốn sẽ lựa chọn các dữ liệu sao cho giảm miền lỗi của giả thiết càng nhiều càng tốt. Bước cập nhật Rosenblatt [17] là người đầu tiên phân tích hoạt động hội tụ của bước cập nhật perceptron, nĩ bao gồm qui tắc đơn giản sau đây: if (xt, yt) bị phân lớp nhầm (misclassified), then #3:;  #3 33. Vì vậy, thay vì sử dụng một biến của nguyên tắc cập nhật, theo Motzkin và Schoenberg [40] đã cải tiến bước cập nhật theo quy tắc sau: if (xt, yt) bị phân lớp nhầm, then vt+1 = vt −2(vt . xt)xt Giả sử xt đã chuẩn hĩa theo đơn vị chiều dài. Lưu ý rằng bản cập nhật cũng cĩ thể viết như vt+1 = vt+2yt|vt . xt| xt, chỉ khi bản cập nhật được thực hiện trên những sai lầm, trong trường hợp này theo định nghĩa yt≠ SGN (vt . xt). Vì vậy Motzkin và Schoenberg [40] đang chia mức độ các bản cập nhật sau của perceptron chuẩn theo một thừa số 2|vt .xt| để tránh những dao động gây ra bởi các điểm gần một nửa khơng gian đại diện bởi các giả thuyết hiện thời. Motzkin và Schoenberg đã giới thiệu quy tắc này, trong bối cảnh giải quyết các bất đẳng thức tuyến tính, và gọi nĩ là phương pháp "phản xạ" (Reflexion). Sau đĩ, Hampson và Kibler [34] áp dụng nĩ để học tập bộ phân tách tuyến tính, trong một khuơn khổ phân tích khác với chúng ta. Cùng một quy tắc, nhưng khơng cĩ tham số 2, đã được sử dụng trong nhiều nghiên cứu trước đây [4] nghiên cứu về việc học các bộ phân lớp tuyến tính từ dữ liệu nhiễu, trong một thiết lập khối. Hai ơng cĩ thể chỉ ra rằng cơng thức của họ cĩ sự thực hiện tổng quát trong một thiết lập giám sát (khơng tích cực). Bước lọc 23 Với giới hạn mà thuật tốn đã đưa ra, thì luật lọc tự nhiên là truy vấn các điểm xt khi |vt . xt| nhỏ hơn ngưỡng st. Sự lựa chọn st là rất quan trọng. Nếu nĩ là quá lớn, sau đĩ chỉ một phần nhỏ rất ít các điểm đã truy vấn sẽ thực sự bị phân lớp sai - hầu như tất cả các nhãn sẽ bị lãng phí. Nĩi cách khác, nếu st quá bé, thì thời gian chờ đợi cho một truy vấn cĩ thể khá cao, và khi một bản cập nhật thực sự được thực hiện, thì độ lớn của nĩ cĩ thể lại rất nhỏ. Vì vậy, tác giả thiết lập ngưỡng cho phù hợp: tác giả bắt đầu với st cĩ giá trị cao, và chia nĩ cho 2 cho đến khi đạt được mức mà cĩ đủ bộ phân lớp sai các điểm đã truy vấn. Áp dùng chiến lược này vào bản cập nhật Perceptron đã chỉnh sửa, chúng ta nhận được một thuật tốn học tích cực (hình 3.5) với độ phức tạp nhãn >?@ AB ;C), tạo ra >?@ AB ;C) lỗi và cĩ lỗi ≤ε. 3.1.3 Cải tiến bước cập nhật perceptron Phần này mơ tả một thuật tốn Perceptron đã đượcc cải tiến. Khơng giống như Perceptron chuẩn, thuật tốn Perceptron cải tiến đảm bảo rằng vt.u tăng nghĩa là lỗi của vt giảm đơn điệu. Một sự khác biệt nữa của bản cải tiến chuẩn (so với các bản khác) là độ lớn của các giả thuyết hiện thời luơn luơn là 1. Điều này rất thuận lợi cho việc phân tích. Perceptron cải tiến chiều d và số lần cập nhật M #;  ;. ; --với dữ liệu đầu tiên ; ; For t=1 to M: 3  3 là dữ liệu tiếp theo với  #3 . ' #3:;  #3  2#3 . 33 Hình 3.2 Thuật tốn cải tiến percepron chuẩn 24 Trong thuật tốn perceptron chuẩn hình 3.1, bước cập nhật perceptron chuẩn vt+1 = vt + xt.yt là cùng hướng nhưng khác độ lớn (được chia theo hệ số 2|vt.xt|) Các thuật tốn Perceptron cải tiến chuẩn được đưa ra trong hình 3.2. Ta cĩ ||vt||=1 (3.3) Và D#3:;DE  D#3DE F#3 . 3ED3DE  F#3 . 3E  . (3.4) Ngược lại, đối với bản cải tiến Perceptron chuẩn, mức độ của vt tăng đều đặn. Với bản cải tiến đã sửa, lỗi cĩ thể chỉ giảm bởi vì vt.u cũng chỉ giảm. #3:; ,  #3 . ,  2#3. 3. 3 . ,  #3 . , 2<#3 . 3<<3 . ,<. (3.5) Biểu thức thứ 3.4 xảy ra theo thực tế là vt phân lớp nhầm xt. Do vậy vt.u tăng, và sự tăng cĩ thể bị chặn từ dưới bằng cách chỉ ra <#3 . 3<<3 . ,< là lớn. Trước đây Hamson và Kibler đã từng sử dụng bản cập nhật này cho việc học bộ phân tách tuyến tính [34], gọi là “Reflection” (Sự phản ánh), dựa trên phương pháp “Reflexion” của Motzkin and Schoenberg [40]. 3 . #3:;  3 . #3  23 . #33 . 3  3 . #3 (3.6) Nĩi chung, biểu thức (3.6) cĩ thể coi là bản cập nhật sửa của dạng #3:; #3  G#3 . 33, dạng này tương đương với phương pháp “Reflexion” trong việc giải bất đẳng thức tuyến tính [30][40]. Khi α≠2, vector vt khơng cịn giữ độ dài cố định nữa, tuy nhiên cũng cĩ thể xác minh được rằng các vector đơn vị tương ứng #53thỏa mãn: #53:;. ,  #53 . , G<#53 . 3<<3 . ,<HI  G2  G#53 . 3E, (3.7) Và do vậy bất kỳ sự lựa chọn nào α∈[0,2] cũng đảm bảo rằng lỗi khơng tăng. Blum và cộng sự[4] đã sử dụng α=1 bảo đảm rằng sự phát triển trong mẫu số (phân tích của họ đã khơng dựa vào tiến bộ trong tử số) miễn là #53 . , và 25 #53. 3E bị chặn ở 0. Phương pháp tiếp cận của họ được sửa dụng một loạt như là một phần của thuật tốn phức tạp hơn cho học noise_tolerant. Trong khung làm việc tuần tự, cĩ thể chặn <#53 . 3<<3 . ,< bởi 0, dưới sự phân tán thống nhất, và do đĩ sự lựa chọn α=2 là thuận lợi nhất, nhưng α=1 sẽ cĩ thể tốt hơn. Hình 3.3 Quy tắc học tích cực là truy vấn các nhãn cho các điểm x trong L, L được xác định bởi ngưỡng st trên |vt.xt| [32] 3.1.4 Perceptron chỉnh sửa tích cực Mục đích trong việc thiết kế luật học tích cực là giảm thiểu phức tạp nhãn được đưa vào câu truy vấn chỉ cho các nhãn trên các điểm trong miền lỗi ξt. Tuy nhiên khơng cĩ tri thức của u, thuật tốn sẽ khơng biết vị trí của ξt. Theo trực giác thì luật học tích cực là xấp xỉ với miền lỗi, với thơng tin đã cho thuật tốn cĩ vt. Trong hình 3.3, vùng đã gán nhãn L đơn giản là miền được hình thành bởi việc tạo ngưỡng cho các lề của một ví dụ ứng viên đối với vt. Phiên bản tích cực của thuật tốn Perceptron cải tiến được chỉ ra trong hình 3.4. Thuật tốn này tương tự thuật tốn của phần trước trong các bước cập nhật. Đối với quy tắc lọc, sẽ duy trì một ngưỡng st và chỉ yêu cầu cho các nhãn của các ví dụ cĩ <#3. < 9 3. Miền xấp xỉ lỗi đạt được bằng cách chọn ngưỡng st thích hợp, để quản lý sự cân bằng giữa vùng L đang quá lớn, gây ra nhiều nhãn bị lãng phí mà khơng tìm được ξt, và L chỉ chứa các điểm cĩ lề rất 26 nhỏ đối với vt, vì bước cập nhật sẽ tạo ra sự cải tiến rất nhỏ trên các điểm như thế. Thuật tốn giảm ngưỡng thích ứng với thời gian, bắt đầu với s1=1/J@ và giảm ngưỡng đi 2 lần cho đến khi nào cĩ thể thực hiện các ví dụ đã gán nhãn trên ngưỡng là đúng. Chúng ta giới hạn cận dưởi của st đối với lỗi chỉ ra rằng với xác suất cao thì ngưỡng st khơng bao giờ là nhỏ. Perceptron cải tiến chiều d, số lượng nhãn L và R #;  ;. ; cho dữ liệu đầu tiên ; ; ;  HJ@ For t=1 to L: Chờ dữ liệu tiếp theo x: <. #3< 9 3 và truy vấn nhãn của x. Gọi dữ liệu đã gán nhãn 3  3 If3 . #33 . ', then: #3:;  #3  2#3 . 33 3:;  3 else #3:;  #3 If các dự đốn là đúng trên R dữ liệu đã gán nhãn liên tiếp (vd:  . # 4 '+K  L    L    L), then 3:;  3H2 else 3:;  3 Hình 3.4. Một phiên bản tích cực của Perceptron đã chỉnh sửa. [32] 27 Thuật tốn trong hình 3.4 đã được Dasgupta đã trình bày bằng cách cải tiến bước cập nhật của thuật tốn perceptron [32], thu được một thuật tốn đơn giản hơn, đạt được lỗi mục tiêu ε bằng cách sử dụng số lượng nhãn xác định >?@ AB ;C. Trong lý thuyết phát triển của học tập tích cực, các kịch bản khơng tầm thường và cụ thể nhất mà trong đĩ học tập tích cực đã được thể hiện để cung cấp cho một sự cải tiến hàm số mũ trong độ phức tạp mẫu là học một một bộ phân tách tuyến tính cho các dữ liệu phân bố đều trên mặt cầu đơn vị. 3.2 Học tích cực với SVM 3.2.1 Giới thiệu Bộ phân loại SVM đã được sử dụng rộng rãi trong rất nhiều bài tốn phân lớp. Tuy nhiên chúng chỉ được sử dụng với tập dữ liệu huấn luyện đã được lựa chọn ngẫu nhiên. Trong mục này sẽ trình bày thuật tốn Active Support Vector Machines (Acitve SVM) cĩ thể làm giảm đi dung lượng cũng như sự cần thiết của tập dữ liệu huấn luyện. 3.2.2 Máy hỗ trợ vector 3.2.2.1 Máy vector hỗ trợ sử dụng phương pháp qui nạp Máy vector hỗ trợ [41] cĩ các cơ sở lý thuyết vững chắc và đạt được những thành cơng thực nghiệm xuất sắc. Chúng cũng được áp dụng cho những bài tốn như: nhận dạng số viết bằng tay [24], nhận dạng đối tượng [13], và phân lớp văn bản [37][33]. Hãy xét thuật tốn SVM cho bài tốn phân lớp nhị phân. Cho tập huấn luyện ; E   M là các vector trong khơng gian X⊆Rd và tập các nhãn ; E   M với yi∈ {-1,1}. Theo cách hiểu thơng thường nhất, thì SVMs là các siêu phẳng chia tập dữ liệu huấn luyện bằng một lề cực đại. Tất cả các vector nằm trên một mặt của siêu phẳng đều được gán nhãn là -1, và tất cả các 28 vector nằm trên mặt kia đều được gán nhãn là 1. Các vector huấn luyện gần siêu phẳng nhất gọi là vector hỗ trợ (support vector). Hình 3.5 (a) Máy hỗ trợ vector tuyến tính đơn giản. (b) Máy hỗ trợ vector (đường nét đứt) và máy hỗ trợ vector hồi quy (đường nét liền). Những vịng trịn biểu diễn dữ liệu chưa được gán nhãn. Nĩi chung, SVMs cho phép chiếu dữ liệu huấn luyện gốc trong khơng gian X sang một khơng gian đặc trưng F nhiều chiều hơn thơng qua một phép phân Mercer K. Nĩi cách khác chúng ta cĩ tập các bộ phân lớp như sau: (  +NOGP   M Q& R++++++++++++++++++++++++++++++++++++++3.S Khi K thỏa mãn điều kiện Mercer [12] thì PT U  +ΦT.ΦU trong đĩ Φ: X→Y và “⋅” là phép tích trong (inner product). Ta cĩ thể viết lại như sau: +(  V.Φ W BX+YZ++V OGΦ M Q& +++++++++++++++++++++++++3.[ Do vậy, bằng cách sử dụng K chúng ta cĩ thể ánh xạ dữ liệu huấn luyện sang một khơng gian đặc trưng (thường là nhiều chiều hơn). Siêu phẳng lề cực đại được chỉ ra trong biểu thức 3.8. Sau đĩ SVM tính các αi tương ứng với siêu phẳng cĩ lề cực đại trong khơng gian F. Khi chọn các hàm nhân khác nhau thì cĩ thể ánh xạ dữ liệu huấn luyện từ khơng gian X sang F sao cho các 29 siêu phẳng trong F sao cho các siêu phẳng trong F tương ứng với các đường biên quyết định phức tạp hơn trong khơng gian gốc X. Hai hàm nhân thường sử dụng là hàm nhân đa thức P\ #  \. # ] tạo ra đường biên đa thức bậc p trong khơng gian đầu vào X và hàm nhân radial basis fuction ^_ `  abcdbe.dbe tạo đường biên bằng cách định vị trọng số Gauss dựa trên các dữ liệu huấn luyện chính. Trong hình 3.6 minh họa đường biên quyết định trong khơng gian đầu vào X của một SVM sử dụng hàm nhân đa thức bậc 5. Đường biên quyết định được làm cong trong khơng gian X tương ứng với siêu phẳng lề cực đại trong tập thuộc tính F. Các tham số αi xác định SVM cĩ thể được tìm trong hàm đa thức thời gian bằng cách giải quyết bài tốn tối ưu lồi[42]:  f g G  ;Eg GGhhPi h (3.10) với : αi > 0 i=1…n 3.2.2.2 Máy vector hỗ trợ sử dụng phương pháp transduction Giả sử tập dữ liệu huấn luyện đã được gán nhãn và bài tốn đặt ra là tạo ra một bộ phân lớp thực hiện tốt trên tập dữ liệu kiểm tra chưa biết. Thêm vào trong phương pháp qui nạp thơng thường, SVMs cĩ thể sử dụng cho bài tốn transduction. Đầu tiên là cho tập dữ liệu đã gán nhãn và chưa gán nhãn. Bài tốn học là phải khai báo các nhãn tới các dữ liệu chưa gán nhãn càng chính xác càng tốt. SVMs cĩ thể thực hiện phương pháp transduction bằng cách tìm các siêu phẳng làm cực đại hĩa lề liên quan đến dữ liệu đã gán nhãn và chưa gán nhãn. Ví dụ được thể hiện ở hình 3.5b. Gần đây, các transduction SVM(TSVM) cịn được sử dụng để giải quyết bài tốn phâp lớp văn bản [37][38] đã đạt được một số tiến bộ trong việc thực hiện cân bằng tỉ số độ chính xác/độ hồi phục (precision/recall) trên các SVM qui nạp. 30 Hình 3.6 Máy hỗ trợ vector sử dụng hàm nhân đa thức bậc 5. Khơng giống SVM, TSVM cĩ độ phức tạp thời gian đa thức, chi phí để tìm được hướng giải quyết cho TSVM tăng lên theo hàm mũ cùng với sự tăng của dữ liệu chưa được gán nhãn. Bằng trực quan, ta phải gán tất cả các nhãn cĩ thể cho dữ liệu chưa gán nhãn, và mỗi một nhãn phải tìm một siêu phẳng cĩ lề cực đại. Do vậy sẽ sử dụng thuật tốn xấp xỉ thay thế. Ví dụ, Joachims sử dụng dạng tìm kiếm quỹ tích để gán nhãn và tái gán nhãn cho dữ liệu chưa được gán nhãn để cải tiến kích thước của lề. 3.2.3 Version space Cho tập dữ liệu huấn luyện đã gán nhãn và hàm nhân Mercer K, khi đĩ sẽ cĩ một tập các siêu phẳng chia dữ liệu thành vào khơng gian thuộc tính F. Tập các giả thuyết phù hợp như vậy gọi là version space [39]. Nĩi cách khác, giải thuyết f là trong version space nếu với mọi dữ liệu huấn luyện xi cĩ nhãn yi thì f(xi)>0 nếu yi=1 và f(xi)<0 nếu yi=-1. Tổng quát hơn: Định nghĩa 3.5.1: Cho tập các giả thuyết: j  k(<(  l.Φ DlD Lmn+YZ+l∈+op (3.11) Trong đĩ khơng gian tham số W sẽ tương ứng với khơng gian F. Version space q được định nghĩa như sau: q  (∈+j<∀∈( - ' (3.12) 31 Chú ý rằng khi j là tập các siêu phẳng, sẽ cĩ một song ánh giữa vector w vào giả thuyết f trong j. Do vậy q sẽ được định nghĩa lại như sau: q  rl∈o<+DlD   sl.Φt - '   u (3.13) Định nghĩa 3.5.2: Kích thước hay diện tích của version space Area(q) là diện tích bề mặt của siêu khối cầu khi D$D  . Lưu ý rằng version space chỉ tồn tại khi dữ liệu huấn luyện là tách rời tuyến tính trong khơng gian thuộc tính. Như đã đề cập trong phần 3.2.2.1, hạn chế này khơng giới hạn như lúc đầu ta tưởng. Tồn tại sự đỗi ngẫu giữa khơng gian thuộc tính F và khơng gian tham số v[43][28] mà chúng ta sẽ áp dụng cho phần sau: các điểm trong F tương ứng với các siêu phẳng trong W và ngược lại. Vì định nghĩa các điểm trong W tương ứng với các siêu phẳng trong F, ta sẽ quan sát một trường hợp dữ liệu huấn luyện xi trong version space giới hạn các siêu phẳng tách rời nhau vào những bộ mà phân lớp xi một cách chính xác. Thực tế, chúng ta cĩ thể chỉ ra rằng, tập các điểm cĩ thể cho phép w trong W bị giới hạn nằm trong một phía của một siêu phẳng trong W. Hơn nữa, để chỉ ra các điểm trong F tương ứng với siêu phẳng trong W, giả sử cho dữ liệu huấn luyện mới xi cĩ nhãn yi, sau đĩ bất kỳ siêu phẳng phân chia nào cũng phải thỏa mãn s$.Φt - '. Bây giờ thay vì chỉ coi w như là một vector trong siêu phẳng F thì ta nghĩ rằng Φ(xi) cũng là vector trong khơng gian W. Do đĩ s$.Φt - ' là nửa khơng gian trong W. Lại cĩ $.Φ  ' là một siêu phẳng trong W mà nĩ đĩng vai trị như một trong những đường biên của version space q. Lưu ý rằng version space là một miền đã được kết nối trên bề mặt của một siêu khối trong khơng gian tham số. Hình 3.7 là một ví dụ. 32 (a) (b) Hình 3.7 (a) Tính đối ngẫu trong version space. Bề mặt của siêu khối biểu diễn các vector trọng số đơn vị. Mỗi một trong hai siêu phẳng tương ứng với dữ liệu huấn luyện đã gán nhãn. Mỗi siêu phẳng giới hạn diện tích trên siêu khối mà trong đĩ chứa các giả thiết. Ở đây, version space là các đoạn bề mặt của siêu khối gần với camera nhất. (b) Một bộ phân lớp SVM trên một version space. Khối bị chìm tối là khối cĩ bán kính lớn nhất mà tâm của nĩ nằm trên version space và bề mặt của nĩ khơng cắt siêu phẳng. Tâm của khối bị chìm tương ứng với SVM, mà bán kính của nĩ tương đương với lề của SVM trong F và điểm huấn luyện tương ứng với các siêu phẳng mà nĩ tiếp xúc là các vector hỗ trợ. Các SVM tìm siêu phẳng mà siêu phẳng đĩ cực đại hĩa lề trong khơng gian đặc tính F. Một cách để đưa ra bài tốn tối ưu này như sau: wmnxwyz {XV.Φ (3.14) với D$D  +`|+s$.Φt - '+   Vì cĩ điều kiện DVD   và s$.Φt - '+chúng ta đưa ra giải pháp trong version space. Bây giờ chúng ta coi bài tốn trên như tìm một điểm trên version space sao cho khoảng cách: {XV.Φ là cực đại. Từ tính đối ngẫu giữa khơng gian thuộc tính với khơng gian tham số và DV.ΦD  λ 33 thì mỗi Φ } λ là một vector đơn vị của một siêu phẳng trong khơng gian đặc tính. Bởi vì s$.Φt - '   + nên mỗi siêu phẳng sẽ giới hạn version space. Biểu thức s$.Φt cĩ thể xem như sau: λ× khoảng cách giữa điểm w và siêu phẳng cĩ vector Φ Do đĩ, muốn tìm điểm w* trong version space mà làm cực đại khoảng cách cực tiểu tới bất kỳ siêu phẳng đã mơ tả nào. Nghĩa là, các SVM tìm tâm của các siêu khối cĩ bán kính lớn nhất, siêu khối mà tâm của nĩ được đặt trong version space và bề mặt của nĩ khơng cắt siêu phẳng sẽ tương ứng với dữ liệu đã gán nhãn, như trong hình 3.7(b). Các pháp tuyến của khối là khoảng cách từ tâm của khối tới một trong những siêu phẳng sV~.Φt với Φ là vector hỗ trợ. Bây giờ hãy coi w* là một vector đơn vị của SVM và Φ là các điểm trong khơng gian thuộc tính, chúng ta cĩ khoảng cách $~⋅Φ }λ  là: ; λ × khoảng cách giữa vector hỗ trợ Φ và siêu phẳng cĩ vector đơn vị w, Đĩ là lề của siêu phẳng bị chia bởi λ. Do đĩ, bán kính của siêu khối tương ứng với lề của SVM. 3.2.4 Học tích cực với SVM Trong học tích cực dựa trên tập dữ liệu ban đầu đã cĩ một lượng lớn dữ liệu chưa gán nhãn. Giả sử dữ liệu x được phân phối tương tự và độc lập, các nhãn của nĩ cũng được phân phối theo bộ phân phối điều kiện P(Y|x). Cho dữ liệu chưa gán nhãn U, bộ học tích cực SVM ℓ gồm ba thành phần: (f,q,X). Thành phần đầu tiên là một bộ phân lớp SVM f: X→[-1,+1] đã huấn luyện trên tập dữ liệu hiện thời X đã được gán nhãn (cũng cĩ thể là tập dữ liệu chưa gán nhãn U). Thành phần thứ hai q(X) là hàm truy vấn, đưa ra tập dữ liệu hiện tại X đã gãn nhãn sẽ quyết định dữ liệu nào trong U là câu truy vấn tiếp theo. Bộ học tích cực cĩ thể đưa ra bộ phân lớp f sau mỗi câu truy vấn (học trực tuyến – online learning) hoặc sau một số câu truy vấn nhất định. 34 Điểm khác biệt chính giữa bộ học tích cực và bộ học thụ động là thành phần truy vấn q. Thành phần này cho ta biết dữ liệu chưa gán nhãn nào để hỏi tiếp theo dữ liệu nào sẽ đưa tới cách thiết kế một hàm như vậy. Chúng ta sẽ sử dụng phương pháp chung của học tích cực trong phần 2.2. Đầu tiên chúng ta sẽ định nghĩa mơ hình và chất lượng mơ hình. Sau đĩ chúng ta sẽ lựa chọn dữ liệu để cải thiện chất lượng của mơ hình. 3.2.6.1 Mơ hình và hàm tổn thất (Loss) Chúng ta sử dụng version space làm mơ hình của bài tốn, và kích thước của mơ hình như là độ tổn thất của mơ hình. Do vậy, chúng ta sẽ chọn để hỏi dữ liệu, các dữ liệu mà cố gắng làm giảm kích thước của version space càng nhiều càng tốt. Tại sao nên lựa chọn tốt mơ hình và loss mơ hình? Giả sử rằng w*∈v là một vector tham số tương ứng với SVM sao cho cĩ thể biết được các nhãn thực của tất cả dữ liệu. Biết rằng w* phải thuộc version space qi, qi là version space cĩ được sau i câu truy vấn, q1 ⊃q2⊃q3… Do đĩ, bằng việc rút gọn kích thước của version space càng nhiều càng tốt với mỗi câu truy vấn, ta cĩ thể càng làm giảm nhanh kích thước của khơng gian chứa w*. SVM mà chúng ta học được từ một số lượng giới hạn các câu truy vấn sẽ gần tới w*. Định nghĩa 3.6.1: Cho một bộ học tích cực ℓ, qi là version space của ℓ sau i câu truy vấn được đưa ra. Bây giờ khi cho câu truy vấn thứ i+1 của dữ liệu xi+1 ta cĩ: qb  q ∩r$∈v< sV.Φ:;t - 'u (3.15) q:  q ∩r$∈v< sV.Φ:;t - 'u (3.16) Vì qb và q: là version space khi câu truy vấn tiếp theo xi+1 được gán nhãn là -1 hoặc +1. 35 Chúng ta mong muốn giảm kích thước của version space càng nhanh càng tốt. Cách tốt nhất để cĩ được điều này là lựa chọn một câu truy vấn làm giảm nửa kích thước của version space. Hình 3.8 (a) Lề đơn giản truy vấn b (b)Lề đơn giản truy vấn a Hình 3.9 (a) Lề MaxMin truy vấn b. Hai SVM cĩ lề m- và m+ cho b được chỉ ra. (b) Lề MaxRatio truy vấn e. Hai SVM cĩ lề m- và m+ cho e cũng được chỉ ra. Seung và cộng sự [20] cũng sử dụng một phương pháp để truy vấn các điểm sao cho đạt được giảm kích thước của version space càng nhiều càng tốt. Nếu người ta muốn chấp nhận rằng cĩ một giả thuyết ở trong j mà tạo ra dữ liệu thì giả thiết đĩ đĩ là xác định và dữ liệu là những điểm tự do, sau đĩ sự thực hiện tổng quát các thuộc tính của thuật tốn mà chia nửa version space được đưa ra [45]. Ví dụ, cĩ thể chỉ ra rằng lỗi tổng quát giảm số các câu truy vấn theo cấp số nhân. 3.2.6.2 Các thuật tốn truy vấn Ở phần trước chúng ta đã cung cấp một phương pháp truy vấn dữ liệu để chia version space hiện tại thành hai phần tương đương nhau càng nhanh càng tốt. Khi cho dữ liệu x chưa gán nhãn, thực tế là chưa tính tốn rõ ràng 36 được kích thước của version space mới q− và q+ (các version space thu được khi x được gán nhãn tương ứng là -1 và +1). Dưới đây là ba phương pháp cũng gần giống phương phương trên: • Simple Margin (Lề đơn giản): Cho tập dữ liệu {x1,…,xi} và các nhãn tương ứng {y1,…,yi} vector đơn vị SVM wi cĩ được từ tập dữ liệu này là tâm của siêu khối lớn nhất nằm vừa khít trong version space qi. Vị trí của wi trong version space qi phụ thuộc vào hình dạng của qi; tuy nhiên nĩ thường nằm ngay trong tâm của version space. Bây giờ chúng ta cĩ thể kiểm tra mỗi dữ liệu chưa gán nhãn x để biết xem từ sự tương ứng với các siêu phẳng trong W đến việc wi được đặt đúng tâm như thế nào. Siêu phẳng W càng gần điểm wi, thì nĩ càng được đặt gần đúng tâm của version space hơn và nĩ càng cắt đơi version space. Do vậy, với dữ liệu chưa gán nhãn thì siêu phẳng của chúng trong W gần vector wi nhất. Mỗi một dữ liệu chưa gán nhãn x, khoảng cách ngắn nhất giữa siêu phẳng của nĩ trong khơng gian W và vector wi chính là khoảng cách giữa vector đặc tính Φ và siêu phẳng wi trong F. Khoảng cách này được tính là: <$i.Φ<. Kết quả này theo một quy luật rất tự nhiên: học một SVM trên tập dữ liệu gán nhãn đã cĩ trước và chọn dữ liệu tiếp theo để truy vấn sao cho nĩ gần siêu phẳng trong F nhất. Hình 3.8(a) là một ví dụ minh họa. Trong bức ảnh cách điệu, chúng ta đã trải phẳng bề mặt của siêu khối vector đơn vị cĩ trọng số xuất hiện trong hình 3.7(a). Vùng trắng là version space wi được bao quanh bởi các đường nét liền tương ứng với trường hợp dữ liệu cĩ nhãn. Năm đường nét đứt biểu diễn cho các trường hợp dữ liệu chưa gán nhãn. Hình trịn biểu diễn hình cầu cĩ bán kính lớn nhất mà cĩ thể vừa khít trong version space. Lưu ý rằng đường viền của hình trịn khơng chạm vào đường nét liền - giống như những hình cầu tối trong hình 3.7 (b) khơng tiếp xúc được các siêu phẳng trên bề mặt của hình cầu lớn hơn (chúng sẽ tiếp xúc một điểm nào đĩ trên bề mặt). Trường hợp dữ liệu b là gần với SVM wi nhất và vì vậy sẽ chọn b để truy vấn. 37 • MaxMin Margin (Lề MaxMin): Phương pháp lề Simple cĩ thể là một xấp xỉ gần đúng. Nĩ dựa trên giả định rằng version space là đối xứng và wi được đặt ở tâm. Trong lý thuyết và thực tế đã chứng minh rằng các giả định này cĩ thể khơng chính xác [28]. Thật vậy, nếu khơng cẩn thận sẽ rất cĩ thể truy vấn một trường hợp dữ liệu mà siêu phẳng của nĩ thậm chí khơng giao nhau với version space. Xấp xỉ MaxMin được thiết kế để khắc phục phần nào những vấn đề này. Cho dữ liệu {x1,…,xi} và nhãn {y1,…,yi}, các vector đơn vị SVM wi là tâm của hình cầu cĩ bán kính lớn nhất mà vừa khít trong version space qi và bán kính mi của hình cầu tương ứng với kích thước lề của wi. Cĩ thể sử dụng bán kính mi là biểu thị cho kích thước của version space [43]. Giả sử chúng cĩ một trường hợp dữ liệu tiềm năng chưa gán nhãn x. Chúng ta cĩ thể ước lượng tương đối kích thước của các version space q− bằng cách ghi nhãn cho dữ liệu x là -1, sau khi thêm x vào dữ liệu huấn luyện đã gán nhãn thì tìm SVM và kích thước lề m− của nĩ. Chúng ta cĩ thể thực hiện một phép tính tương tự cho q+ bằng cách gán lại nhãn cho x là +1 và tìm được SVM kết quả để cĩ được lề m+. Khi tách version space, ta thường muốn Area(q−) và Area(q+) là tương đương nhau. Bây giờ, hãy tính min(Area(q−),Area(q+)), nĩ sẽ là nhỏ nếu Area(q −) và Area(q+) là khác nhau. Vì vậy chúng ta sẽ xem xét min(m−,m+) là một xấp xỉ và chúng ta sẽ chọn để truy vấn x sao cho min(m−,m+) là lớn nhất. Do đĩ, các thuật tốn truy vấn MaxMin là như sau: đối với mỗi trường hợp dữ liệu chưa gán nhãn x, tính các lề m− và m+ của các SVM thu được khi x được gán nhãn tương ứng là -1 và 1, sau đĩ chọn để truy vấn trường hợp dữ liệu chưa gán nhãn sao cho min(m−,m+) là lớn nhất. Hình 3.8(b) và 3.9(a) chỉ ra một ví dụ so sánh giữa hai phương pháp lề Simple và lề MaxMin. • Ratio Margin: Phương pháp này tương tự phương pháp lề MaxMin. Ta cũng sử dụng m− và m+ biểu thị cho kích thước của q− và q+. Tuy nhiên, thực tế ta sẽ cố gắng tính tốn version space qi lâu hơn và đối với vài 38 trường hợp dữ liệu x thì cả hai m− và m+ cĩ thể là nhỏ vì hình khối của version space. Do vậy thay vì tìm kích thước tương ứng của m− và m+, ta sẽ chọn để truy vấn x sao cho {X k−+ +−p là lớn nhất (xem hình 3.9(b)). Ba phương thức trên xấp xỉ với thành phần truy vấn mà luơn chia nửa version space. Sau khi thực hiện một số truy vấn để trả về một bộ phân lớp bằng cách học một SVM với các trường hợp dữ liệu cĩ nhãn. Phương pháp Simple cĩ độ tính tốn chuyên sâu ít đầy đủ hơn hai phương pháp cịn lại bởi vì nĩ cần học chỉ một SVM cho mỗi vịng truy vấn, trong khi hai phương pháp MaxMin và MaxRatio cần phải học hai SVMs cho mỗi trường hợp dữ liệu trong suốt mỗi vịng truy vấn. Chú ý rằng khơng nhất thiết dùng một trong những phương pháp này cho tất cả các vịng truy vấn. Vì lý do tính tốn, sẽ cĩ thể rất cĩ lợi khi thay đổi giữa các phương pháp khác nhau sau khi một số truy vấn đã được hỏi: phương pháp truy vấn này được gọi là phương pháp Hybird. Chúng ta đưa ra giả định đã cĩ các vector đặc tính huấn luyện với các modun cố định. Các khái niệm về version space và kích thước của nĩ vẫn đúng. Hơn nữa, lề của SVM cĩ thể được sử dụng như là một dấu hiệu kích thước của version space mà khơng cần quan tâm đến vector đặc tính cĩ các modun cố định hay khơng. Do đĩ, sự giải thích cho các phương pháp MaxMin và MaxRatio vẫn đúng thậm chí khơng cĩ các hạn chế trên các module của vector đặc tính huấn luyện. Sự giả thiết về các Modun cố định là cần thiết cho việc xem version space trên phương diện hình học là đúng. Các phương pháp Simple vẫn cĩ thể được sử dụng khi các vector huấn luyện đặc trưng khơng cĩ module cố định, nhưng sự giải thích khơng cịn đúng kể từ khi SVM khơng cịn thể được xem như là tâm của hình cầu lớn nhất cho phép. Tuy nhiên, đối với phương pháp Simple, các hướng thay thế khác đã được Campbell, Cristianini và Smola đề xuất [10] mà khơng yêu cầu sự cố định trên các module. 39 Đối với học quy nạp, sau khi thực hiện một số câu truy vấn, sau đĩ sẽ trả về một bộ phân lớp bằng cách học một SVM với các trường hợp dữ liệu cĩ nhãn. Đối với học hồi quy, sau khi truy vấn một số trường hợp dữ liệu sau đĩ sẽ trả về một bộ phân lớp bằng cách học một SVM hồi quy với các trường hợp dữ liệu cĩ nhãn và khơng cĩ nhãn. 3.3 Kết luận Trong chương này đã nghiên cứu và trình bày tập trung vào hai thuật tốn học tích cực. Phần đầu của chương giới thiệu thuật tốn perceptron do Rosenblatt đề xuất. Tiếp theo là phương pháp cải tiến thuật tốn perceptron của Dasgupta. Dasgupta cải tiến bước cập nhật của perceptron để thu được một thuật tốn đơn giản hơn, sử dụng dữ liệu đã gán nhãn ít hơn và đạt được lỗi mục tiêu ε. Phần tiếp theo của chương trình bày học tích cực dựa vào SVM, đưa ra khái niệm khơng gian version space, và coi đĩ là mơ hình của học tích cực dựa vào SVM, trong đĩ bề mặt của version space đươc coi như là độ tổn thất của mơ hình. Phần cuối của chương giới thiệu một số thuật tốn truy vấn dữ liệu để cĩ thể làm giảm khơng gian version space càng nhanh càng tốt. Khi đĩ độ tổn thất của mơ hình sẽ giảm càng nhanh hơn. Các thuật tốn truy vấn bao gồm: Simple, MaxMin, Ratio Margin. 40 CHƯƠNG 4. ỨNG DỤNG HỌC TÍCH CỰC CHO BÀI TỐN LỌC THƯ RÁC 4.1 Giới thiệu Trong số các phương pháp lọc và ngăn chặn thư rác thơng dụng, phương pháp lọc theo nội dung cĩ một số ưu điểm quan trọng và hiện đang được sử dụng trong nhiều hệ thống lọc thư thương phẩm. Lọc theo nội dung hoạt động theo nguyên tắc phân loại thư điện tử thành hai nhĩm “thư rác” và “thư thường” bằng cách phân tích phần nội dung của thư. Trong nghiên cứu này, chúng tơi giới hạn việc phân loại thư cho trường hợp thư cĩ chứa văn bản. Như vậy, nội dung thư ở đây là phần văn bản trong thư. Chúng tơi cũng khơng xem xét tới cách định dạng trong thư khi phân loại, chẳng hạn thư cĩ được trình bày dưới dạng HTML hay khơng, mặc dù thơng tin về định dạng cĩ thể đĩng vai trị quan trọng trong việc phát hiện thư rác. Lọc thư rác theo nội dung là trường hợp riêng của bài tốn phân loại văn bản. Tuỳ theo nội dung, thư được phân thành hai loại: thư rác và thư bình thường. Việc phân loại tiến hành như sau. Trước tiên, nội dung thư được biểu diễn dưới dạng vector các đặc trưng hay các thuộc tính, mỗi đặc trưng thường là một từ hoặc cụm từ xuất hiện trong thư. Tiếp theo, trong giai đoạn huấn luyện, tập thư đã được gán nhãn {rác, bình thường} - gọi là dữ liệu huấn luyện hay dữ liệu mẫu - được sử dụng để huấn luyện một bộ phân lớp. Sau khi huấn luyện xong, bộ phân loại được sử dụng để xác định thư mới (thư chưa biết nhãn) thuộc vào loại nào trong hai loại nĩi trên. Trong cả giai đoạn huấn luyện và phân loại, thuật tốn phân loại chỉ làm việc với nội dung thư đã được biểu diễn dưới dạng vector. Cĩ nhiều phương pháp phân loại cĩ thể sử dụng để phân loại thư điện tử, luận văn này nghiên cứu phân loại dựa vào phương pháp học tích cực với hai thuật tốn xây dựng bộ học tích cực là thuật tốn Perceptron [17] và Acitve Support Vector Machines (Acitve SVM) [35]. 41 4.2 Học tích cực trong bài tốn lọc thư rác Nhiệm vụ của lọc thư rác là tự động tìm ra các thư điện tử khơng mong muốn, độc hại trước khi chúng được chuyển đến người sử dụng. Nhiệm vụ của lọc thư rác là một phạm vi ứng dụng quan trọng và cĩ qui mơ lớn trong lĩnh vực học máy. Phương pháp học tích cực đã được phát triển mạnh mẽ trong học máy để làm giảm đi chi phí gán nhãn bằng cách xác định các dữ liệu chứa thơng tin mà cĩ yêu cầu nhãn. Điều này được thể hiện trong thực tế rằng chỉ cĩ một phần nhỏ của tập dữ liệu chưa cĩ nhãn là cần phải được gán nhãn để huấn luyện bộ học tích cực sao cho đạt đến một hiệu suất đủ để ứng dụng trong việc phân loại. Với tốc độ học cao và yêu cầu ít các email đã gán nhãn để huấn luyện, chúng ta sẽ áp dụng phương pháp học tích cực ở trên vào bài tốn lọc thư rác. Phương pháp học tích cực cho phép chọn các mẫu huấn luyện một cách tự động. Sử dụng tri thức hiện tại, bộ học tích cực khơng thụ động nhận các mẫu huấn luyện mà lại tích cực lựa chọn các mẫu sao cho cĩ thể huấn luyện được một mơ hình tối ưu hơn. Kịch bản ý tưởng của học tích cực trong bài tốn lọc thư rác được thể hiện qua hình 4.1. Các thư điện tử được giả sử là đến theo luồng, nghĩa là tại một thời điểm chỉ cĩ một thư điện tử đến. Với mỗi một thư đến, bộ học sẽ đưa ra truy vấn để nhận được nhãn của thư bằng cách dự đốn đĩ là thư thường hay thư rác. Người dùng sẽ quan sát thư và nhãn của thư được bộ học dự đốn trước đĩ và thực hiện phản hồi đến bộ học tích cực, cung cấp nhãn thực sự của thư, thư đĩ thực sự là thư rác hay thư thường. Bộ lọc thư tích cực nhận phản hồi của người dùng sẽ xác định được sự dự đốn của mình về nhãn của thư là đúng hay sai. Nĩ học sẽ sử dụng nhãn thực sự của thư do người dùng phản hồi để cập nhật thêm vào tập huấn luyện, huấn luyện (cập nhật) lại mơ hình để cải thiện hiệu suất lọc thư hay cải thiện dự đốn nhãn cho các thư sau. Hình 4.1 Bộ l Cĩ nhiều thuật to hình như thuật tốn truy v mẫu khơng chắc chắn, truy v này đều đạt hiệu quả trong b chỉ áp dụng 2 thuật tốn dựng bộ học tích cực cho b Trong mơ hình b vào thuật tốn perceptron ho bày ở chương 3. Với bộ sẽ cho ta bộ lọc thư rác dựng dựa trên active SVM s thư rác tích cực này được vector hĩa và được trích đĩ được đưa vào bộ học học của bộ lọc thư điện bộ lọc đạt hiệu quả cao. 42 ọc thư rác áp dụng phương pháp học tích án được sử dụng để xây dựng bộ học ấn dựa vào hội động (Query by Committee), l ấn dựa vào tập dữ liệu ban đầu… C ài tốn lọc thư rác. Tuy nhiên trong lu học tích cực là Perceptron và active ài tốn lọc thư rác. ài tốn lọc thư rác bộ học tích cực được ặc thuật tốn học tích cực dựa vào họctích cực được xây dựng trên thuật tích cực perceptron. Bộ học tích tích ẽ thu được bộ lọc thư SVM tích thể hiện trong hình 4.2. Thư điện tử chọn các thuộc tính đặc trưng đại di tích cực (perceptron hoặc SVM active). Qu tử sẽ được lặp đi lặp lại nhằm mục đích cực tích cực, điển ấy ác thuật tốn ận văn này, SVM để xây xây dựng dưa SVM đã trình tốn perceptron cực được xây cực. Các bộ lọc khi đến sẽ được ện cho thư, sau á trình thu được một Hình 4.2 Bộ lọc th 4.3 Thử nghiệm và k Luận văn định hư thử nghiệm phân loại thư đi cả thư thườngvà thưc rác. Ph nghiệm mã nguồn mở chương ba là chương tr ActiveExperimenter do thu thập dữ liệu và xây d liệu về dạng dữ liệu đầ phân tích, đánh giá và nh 4.3.1. Cài đặt chươ 4.3.1.1. Chương tr 1. Giới thiệu chương tr Chương tr năm 1999, và các tiếp theo. Snow trên các thuật tốn 2. Down load Chương trình đượ 43 ư rác tích cực dựa trên Perceptron/SVM active ết quả ớng khai thác phần mềm mã nguồn m ện tử trên tập dữ liệu là các thư đi ần đầu của mục 4.3 sẽ giới thi cài đặt hai thuật tốn học tích cực đã tr ình Snow do Dan Roth xây dựng [46] Ran EL-Yaniv xây dựng [47]. Các ph ựng chương trình tiền xử lý dữ liệu và bi u vào cho các cơng cụ thực nghiệm. V ận xét thực nghiệm. ng trình thử nghiệm ình snow ình ình Snow được Ran Roth cài đặt phi phiên bản sau cũng được phát triển là chương trình học kiến trúc, là bộ h winnow, percepptron, nạve Bayer… c download trên trang web mã nguồn m ở để tiến hành ện tử bao gồm ệu hai tool thực ình bày trong và chương trình ần tiếp theo sẽ ểu diễn dữ à cuối cùng là ên bản đầu tiên trong nững năm ọc được cài đặt ở: 44 3. Cài đặt Chương trình được cài đặt trên máy tính cĩ cài hệ điều hành Linux, Trước tiên, cần giải nén file cài đặt bằng các lệnh sau: >tar –xvzf SNoW_v3.1.8.tar Sau đĩ nĩ sẽ tạo ra một thư mục cĩ tên là Snow_v3.1 chứa Makefile và các file nguồn. Chuyển đường dẫn vào thư mục vừađược tạo ra (Snow_v3.1) bằng lệnh > cd Snow_v3.1 Gõ lệnh: >makefile Chương trình sẽ tạo ra file thực thi Snow Quá trình thực thi này được sử dụng để huấn luyện, kiểm tra và đánh giá quá trình thực hiện. 4.3.1.2. Chương trình ActiveExperimenter 1. Giới thiệu chương trình ActiveExperiment là chương trình được cài đặt dựa trên bốn thuật tốn học tích cực dựa vào SVM, đĩ là thuật tốn Simple, Self-Conf, KFF và balanced. Chương trình được Ran EL-Yaniv xây dựng bằng ngơn ngữ java, cài đặt một số thuật tốn học tích cực. 2. Down load Người dùng cĩ thể download cơng cụ trên trang web: 3. Cài đặt Chương trình cĩ thể cài đặt trên máy tình cáo cài hệ điều hành Window hoặc Linux. Để chạy chương trình trước tiên phải cài java 1.4.2 hoặc phiên bản cao hơn. Cĩ thể download java trên trang web. Sau khi đã cài đặt mơi trường, giải nén file cài đặt AcitveExperimenter.zip, ta được thư mục AcitveExperimenter. Trong 45 thư mục cĩ chưa file experimenter.bat chính là file chạy của chương trình. 4.3.2. Thu thập và biểu diễn dữ liệu 1. Dữ liệu thử nghiệm Một khĩ khăn khi thử nghiệm lọc thư là hiện nay chưa cĩ những bộ dữ liệu mẫu chuẩn. Do vậy tác giả sẽ tự tiến hành xây dựng bộ dữ liệu thư để dùng trong thử nghiệm của mình. Thư rác được thu thập từ hai nguồn: nguồn thứ nhất là những thư rác mà các tác giả nhận được qua địa chỉ thư của mình tại Việt nam. Nguồn thứ hai là những thư rác do quản trị phát hiện tại mail server của cơng ty FPT (mail.fpt.com.vn). Thư bình thường là những thư mà các tác giả nhận được thơng qua hịm thư mail.gdt.gov.vn. Đối với các thư bình thường nhận được, trong trường hợp thư nhận từ cùng một nguồn qua nhiều phiên gửi và reply thì đối với những thư gửi sau sẽ được xố phần đã gửi từ trước, chỉ giữ lại nội dung thư nhận được cuối cùng. Đối với những thư bao gồm cả văn bản và hình ảnh, chỉ cĩ phần văn bản được sử dụng, phần hình ảnh bị bỏ qua khơng xem xét. Các thơng số chính về bộ dữ liệu được thống kê: Tổng thư: 700 Thư rác: 236 Thư thường: 464 2. Biểu diễn nội dung thư dưới dạng mơ hình boolean Để cĩ thể sử dụng kỹ thuật học máy và xác suất thống kê, nội dung thư cần được biểu diễn dưới dạng thuận tiện cho việc áp dụng thuật tốn học máy. Các phương pháp lọc thư bằng cách tự động phân loại theo nội dung đều sử dụng cách biểu diễn thư dưới dạng véctơ. Mặc dù cĩ nhiều cách xây dựng véctơ nhưng cách đơn giản nhất là mơ hình boolean. Nguyên tắc cơ bản của phương pháp này là khơng quan tâm tới vị trí xuất hiện các từ hay cụm từ 46 trong thư mà coi thư như một tập hợp khơng cĩ thứ tự các từ. Mỗi thư khi đĩ được biểu diễn bởi một véctơ. Số phần tử của véctơ bằng số lượng từ khác nhau trên tồn bộ tập dữ liệu huấn luyện. Cĩ nhiều cách tính giá trị các phần tử của vectơ. Cách đơn giản nhất là sử dụng giá trị nhị phân: mỗi phần tử của véctơ bằng 1 hay 0 tuỳ thuộc vào từ tương ứng cĩ xuất hiện trong thư tương ứng với véctơ hay khơng. Giả sử cĩ một tập gồm m văn bản   @; @E   @M. Mỗi văn bản gịm n từ khĩa €  L; LE   LM. Gọi   $h là ma trận trọng số, trong đĩ wij là trọng số của từ khĩa ti trong văn bản dj. Mơ hình Boolean là mơ hình đơn giản nhất, trong đĩ trọng số các từ trong văn bản là 0 hoặc 1. Khi đĩ, mỗi văn bản sẽ được biểu diễn dưới dạng tập hợp như sau: di={tij}, trong đĩ tij là từ ti cĩ trọng số wij trong văn bản dj là 1.[1] Các phương pháp phức tạp hơn thường dựa vào tần suất xuất hiện của từ trong thư. Từ xuất hiện càng nhiều thì phần tử tương ứng của vectơ cĩ giá trị càng lớn và ngược lại. Trên các tập dữ liệu mẫu thực, số lượng từ khác nhau cĩ thể lên tới hàng chục nghìn tương ứng với số lượng phần tử trong mỗi véctơ. Trong các phần sau sẽ đề cập tới kỹ thuật giảm bớt số lượng từ dùng để biểu diễn thư. Phương pháp biểu diễn thư sử dụng boolean trình bày ở trên bỏ qua thơng tin về vị trí xuất hiện và thứ tự các từ trong thư. Những thơng tin này cĩ thể cĩ giá trị quan trọng trong việc phát hiện thư rác. Tuy nhiên, do đơn giản, phương pháp boolean vẫn là phương pháp biểu diễn nội dung thư thơng dụng nhất, mặc dù cĩ nhược điểm vừa nêu. Trong nghiên cứu này, luận văn cũng sử dụng phương pháp boolean và các mở rộng của phương pháp này để biểu diễn nội dung thư điện tử: 47 Tập các từ trong tất cả tài liệu sẽ được sắp xếp thành từ điển và được đánh chỉ số theo thứ tự tăng dần. Thư sẽ được biểu diễn dưới dạng vector, biểu diễn thứ tự tăng dần các chỉ số của các từ cĩ trong thư đĩ. Dưới đây là một ví dụ đơn giản minh hoạ cho cách biểu diễn nội dung nĩi trên. Dữ liệu huấn luyện bao gồm bốn thư, trong đĩ hai thư là thư rác và hai là thư bình thường. Nội dung các thư được cho trong bảng 4.1. Trên bảng 4.3. là biểu diễn véctơ cho các thư trong bảng 4.1. Số TT Nội dung Nhãn 1 mua và trúng thưởng Rác 2 mua một tặng một Rác 3 anh mua rồi Bình thường 4 vừa gửi xong Bình thường Bảng 4.1. Ví dụ nội dung của 4 thư. Từ các thư trên ta sắp xếp các từ trong thư dưới sạng từ điển và đánh chỉ số như sau: Bảng 4.2 Từ điển từ và chỉ số cho dữ liệu trong bảng 4.1 Từ Chỉ số anh 1 gửi 2 một 3 mua 4 rồi 5 tặng 6 thưởng 7 trúng 8 và 9 vừa 10 xong 11 48 Số TT anh gửi một Mua rồi tặng thưởng Trùng và vừa xong 1 4 7 8 9 2 3 4 6 3 1 4 5 4 2 10 11 Bảng 4.3. Biểu diễn véctơ cho dữ liệu trong bảng 4.1 Như vậy các thư sẽ được biểu diễn như sau: Thư1 ={4, 7, 8, 9} Thư2={3, 4, 6} Thư3={1, 4, 5} Thư4={2, 10, 11} 4.3.3. Xây dựng chương trình biểu diễn và tiền xừ lý dữ liệu a. Mơi trường cài đặt: Chương trình được cài đặt trên các mơi trường ứng dụng sau: - Mơi trường cài đặt ứng dụng: Visual Studio .NET - Ngơn ngữ sử dụng: Visual C# b. Chức năng của chương trình: + Tiền xử lý dữ liệu: tách từ trong các thư thành các từ đơn, loại bỏ đi các ký tự đặc biệt, loại bỏ các từ dừng (stop-word). Đưa các từ vào trong từ điển, đánh chỉ số cho các từ. + Xử lý dữ liệu tạo file dữ liệu đầu vào cho các chương trình thực nghiệm. c. Kết quả cài đặt chương trình: 49 - Giao diện chính của chương trình: Hình 4.3. Giao diện chính của chương trình Lựa chọn thư mục chứa dữ liệu để lấy dữ liệu đưa vào chương trình xử lý: Hình 4.4 Giao diện lựa chọn thư mục chứa dữ liệu Nhấn nút “Làm sạch dữ liệu” để loại bỏ các ký tự đặc biệt trong thư: ký tự xuống dịng, loại bỏ các từ dừng (stop word). Quá trình làm sạch dữ liệu sau khi hồn thành sẽ thơng báo như trong hình 4.5 50 Hình 4.5 Thơng báo quá trình làm sạch dữ liệu đã thành cơng Bấm nút “Xứ lý” để biểu diễn dữ liệu về dạng vector thể hiện trong các file cĩ đuơi chấm là snow và libsvm. Trên màn hình chương trình cũng thể hiện dữ liệu huấn luyện và kiểm tra (hình 4.6). Trong file huấn luyện gồm cĩ 323 thư thường và 167 thư rác. Trong file kiểm tra cĩ 141 thư thường và 69 thư rác. Kết quả của chương trình là tạo ra các file cĩ đuơi .snow và .libsvm chính là dữ liệu thử nghiệm tương ứng cho các chương trình Snow và AcitveExperimenter. Dữ liệu ra được lưu trong thư mục đã chọn ở đầu chương trình. 51 Hình 4.6 Giao diện thơng báo kết quả xử lý dữ liệu 4.3.4. Kết quả thử nghiệm Hai phương pháp phân loại được thử nghiệm bao gồm chương trình Snow cài đặt perceptron và active SVM. Chương trình Snow Qua trìnhhử nghiệm được thực hiện qua hai bước: bước huấn luyện và bước kiểm tra. Bước huấn luyện gõ lệnh: ../snow –train –I traindata.snow –F NetworkFile.net –A archfile Bước kiểm tra gõ lệnh: ../snow –test –I testdata.snow – F NetworkFile.net Kết quả màn hình: kết quả của chương trình được thể hiện trong hình 4.7 52 Hình 4.7. Kết quả chạy thuật tốn Perceptron Chương trình ActiveExperimenter Thử nghiệm cũng được chia thành 2 giai đoạn: giai đoạn huấn luyện và kiểm tra. Thực nghiệm sử dụng phương pháp đánh giá 10 fold-cross validation: tồn bộ dữ liệu được chia ngẫu nhiên thành 10 nhĩm kích thước tương đương nhau. Bộ phân loại được huấn luyện trên chín nhĩm sau đĩ được kiểm tra trên một nhĩm cịn lại. Lặp lại 10 lần với 10 nhĩm dùng để kiểm tra, sau đĩ lấy trung bình cộng kết quả. Để chạy chương trình ta gõ lệnh: experimenter.bat thay đổi file dữ liệu hay các thơng số đầu vào chương trình ta cĩ thể sửađổi trong file config.xml trong thư mục ActiveExperimenter\Config. Trong file config.xml ta cĩ thể lựa chọn thuật tốn truy vấn là SIMPLE, SELF_CONF, KFF… Nếu để mặc định sẽ được hiểu là thuật tốn SIMPLE đã trình bày trong chương 3. File config.xml cĩ cấu trúc như trong hình 4.8: 53 Hinh 4.8 Cấu trúc file cấu hình của chương trình ActiveExperimenter Màn hình sau khi chạy chương trình với thuật tốn SIMPLE ta cĩ kết quả thể hiện trong hình 4.9 Hình 4.9. Kết quả chạy thuật tốn SIMPLE 54 Khi lựa chọn thuật tốn là thuật tốn SELF_CONF để thử nghiệm cũng trên tập dữ liệu đĩ, thu được kết quả ở hình 4.10: Hình 4.10. Kết quả chạy thuật tốn SELF_CONF 55 Khi sử dụng thuật tốn KFF ta thu được kết quả như hình 4.11. Hình 4.11. Kết quả chạy thuật tốn KFF Cuối cùng là chạy thử nghiệm trên thuật tốn BALANCE_EE ta thu được kết quả như hình 4.12: Hình 4.12. Kết quả chạy thuật tốn BALANCE_EE 56 Trong bốn thuật tốn đã sử dụng thực nghiệm trong chương trình ActiveExperiment thì cĩ ba thuật tốn đều cho kết quả cao và tương tự ngang nhau. Riêng thuật tốn KFF thì cho độ chính xác rất thấp chưa đạt 50%. Kết quả được thể hiện trong bảng 4.4 Ta cĩ bảng kết quả của các thuật tốn SVM active như trong bảng 4.4: Lần truy vấn SIMPLE SELF_CONF KFF BALANCE_EE 1 63.72 61.79 61.03 61.03 2 80.64 81.25 67.82 73.72 3 62.82 77.31 67.05 63.97 4 84.10 87.82 63.33 74.74 5 69.49 84.87 63.33 79.74 6 81.54 88.21 66.67 82.05 7 76.28 90.13 60.77 74.10 8 86.92 87.31 57.56 83.21 9 87.44 91.54 57.05 83.33 10 87.82 92.18 50.38 80.64 11 90.13 92.65 53.21 86.15 12 90.13 92.82 52.05 85.64 13 91.67 92.56 52.56 92.95 14 92.95 92.18 52.44 90.64 15 93.33 92.95 50.90 92.95 16 89.23 93.82 47.95 86.67 17 92.95 92.56 45.26 92.82 18 93.21 92.56 46.54 94.10 19 93.82 93.08 47.69 93.46 20 93.08 92.31 46.28 93.72 Bảng 4.4 Kết quả chạy qua 20 lần truy vấn của các thuật tốn Cả trong hai chương trình thực nghiệm bước truy vấn và phản hồi người dùng được chương trình hĩa trong quá trình thực nghiệm. Khi chương trình chọn một dữ liệu thư điện tử để truy vấn nhãn, thì nhận được sự phản hồi đã được thể hiện thơng qua là dữ liệu thư đĩ đã được gán nhãn sẵn trong tập dữ liệu huấn luyện. 57 4.5.2. Nhận xét về kết quả thử nghiệm Với dữ liệu huấn luyện trên đây, Snow đạt độ chính xác là 99%, cịn chương trình experimenter chỉ cho độ chính xác là 87,82% ở lần truy vấn thứ 10. Khi số lần truy vấn càng nhiều thì độ chính xác càng cao, thể hiện ở các lần truy vấn thứ 15-20 đạt độ chính xác là 93,08 %.Tuy nhiên điều này cũng đã khẳng định được tính hiệu quả cao của thuật tốn perceptron và acitve SVM. Trong số hai phương pháp phân loại được sử dụng, phương pháp perceptron cho kết quả tốt nhất, tuy nhiên phương pháp active SVM cĩ ưu thế hơn do cĩ độ phức tạp tính tốn thấp hơn nhiều. Thời gian chạy của chương trình snow qua một vịng huấn luyện, kiểm tra mất 1.37s, tuy nhiên với chương trình ActiveExperimenter chạy qua 10 vịng huấn luyện, mỗi vịng sẽ truy vấn 20 lần, thời gian chạy chỉ cĩ 0.91s, trung bình mỗi vịng mất khoảng 0.09s , điều này khẳng định độ phức tạp tính tốn thuật tốn của phương pháp active SVM thấp dù độ chính xác thì chưa cao nhất cĩ thể. Trong khi thuật tốn Perceptron cho độ chính xác cao, nhưng thời gian chạy cịn khá lâu. Đối với thuật tốn acitve SVM cĩ sự hạn chế là sử dụng hàm hàm nhân Radial basis function mà chưa sử dụng các hàm nhân khác, chẳng hạn như hàm nhân đa thức. Điều này cĩ thể là một trong những nguyên nhân dẫn đến độ chính xác của thuật tốn chưa được cao. 4.4 Kết luận Chương này đã giới thiệu bài tốn lọc thư rác và áp dụng phươg pháp học tích cực và trong bài tốn. Trong chương này cũng giới thiệu chương trình xử lý dữ liệu và chuẩn hĩa dữ liệu về dạng vector và đầu vào cho các tool thực nghiệm. Thực nghiệm các tool cĩ cài đặt các thuật tốn học tích cực trên tập dữ liệu tạo được. Phân tích đánh giá và nhận xét kết quả thực ngiệm. 58 KẾT LUẬN Những vấn đề đã được giải quyết trong luận văn Sau một thời gian thu thập tài liệu, khảo sát và phân tích nội dung một số bài báo được đề xuất trong lĩnh vực nghiên cứu về học máy, bản luận văn này là sự tổng hợp những nét chính trong học tích cực và là một hướng giải quyết cho bài tốn lọc thư rác. Sau đây là những điểm chính mà luận văn đã tập trung giải quyết. ü Tìm hiểu phương pháp học tích cực, so sánh với học thụ động, tìm ra ưu điểm của từng phương pháp và các trường hợp ứng dụng phù hợp. ü Tìm hiểu phương pháp học tích cực dựa vào perceptron, thuật tốn học perceptron đã được cải tiến của Dagupsta đề xuất năm 2005. Thuật tốn được xây dựng lên từ việc đưa sự cải tiến bước cập nhật perceptron của Morkin vào thuật tốn perceptron chuẩn cĩ 2 bước lọc và bước cập nhật. ü Tìm hiểu phương pháp học tích cực dựa vào SVM được Simon Tong đề xuất năm 2001, các thuật tốn truy vấn: Simple Margin, MaxMin Margin và Ratio Margin. ü Ứng dụng các phương pháp học tích cực đã tìm hiểu áp dụng vào bài tốn lọc thư rác, xây dựng mơ hình cho bài tốn lọc thư rác. Với các mơ hình khơng sử dụng phương pháp học tích cực (mơ hình thụ động), để huấn luyện được bộ học, cần một lượng lớn dữ liệu huấn luyện, vì vậy mà tốn kém trong chi phí và thời gian. Trong mơ hình lọc thư rác tích cực sẽ làm giảm được lượng dữ liệu huấn luyện này. Hơn nữa, mơ hình lọc thư thụ động sẽ phải mất chi phí nhiều hơn và phải được huấn luyện lại để cĩ thể phát hiện được các thư rác ngày một phát triển tinh vi hơn, thì bộ lọc thư tích cực lại cĩ khả năng tự cập nhật lại lại mơ hình khi nhận được thơng tin cần thiết từ việc đưa ra truy vấn cho dữ liệu đã được lựa chọn phù hợp từ truy vấn và câu phản hồi trước đĩ. Vì vậy mà bộ lọc thư tích cực sẽ khơng cần mất nhiều chi phí cho việc huấn luyện lại, và giảm tập dữ liệu huấn luyện cho mơ hình. Bộ lọc 59 thư rác đã trình bày trong luận văn đạt độ chính xác và hiệu quả cao. Thực nghiệm đạt 99% đối với thuật tốn perceptron và 93.7% đối với các thuật tốn active SVM. ü Thu thập dữ liệu thư, spam và xây dựng chương trình xử lý dữ liệu thực tế thành dữ liệu đầu vào cho các thử nghiệm. Luận văn xây dựng thử nghiệm trên các tool sẵn cĩ cài đặt các thuật tốn perceptron và active SVM mà luận văn đã giới thiệu. Cơng việc nghiên cứu trong tương lai Cải tiến thuật tốn active SVM để sử dụng các hàm nhân khác nhằm nâng cao chất lượng phân lớp. Tiếp tục tìm hiểu các phương pháp xử lý nhằm làm tăng chất lượng phân lớp, đồng thời xử lý các thư cĩ nội dung khơng phải là văn bản chằng hạn như hình ảnh, … Ứng dụng vào một hệ thống mail server trong một tổ chức để lọc thư cho cán bộ/nhân viên. 60 TÀI LIỆU THAM KHẢO Tiếng Việt [1] Hà Quang Thụy, Phan Xuân Hiếu, Đồn Sơn, Nguyễn Trí Thành, Nguyễn Thu Trang, Nguyễn Cẩm Tú (2009), Giáo trình khai phá dữ liệu Web, Nhà xuất bản giáo dục Việt Nam. [2] Nguyễn Thanh Thủy (2001), Khai phá dữ liệu, Nhà xuất bản Kỹ thuật và ứng dụng. Tiếng Anh [3] A. Wald (1950). Statistical decision functions. Wiley, New York [4] A. Blum, A. Frieze, R. Kannan, and S. Vempala (1996). A polynomial-time algorithm for learning noisy linear threshold functions. In Proc. 37th Annual IEEE Symposium on the Foundations of Computer Science. [5] B. Busser, R. Morante (2005) ‘Designing an active learning based system for corpus annotation’, In Procesamiento del Lenguaje Natural, núm. 35, pp. 375-381. [6] Burr Settles (2008) Curious Machines: Active Learning with Structured Instances. Ph.D. dissertation, University of Wisconsin–Madison, USA. [7] Burr Settles (2009) ‘Active learning literature survey’ Computer Sciences Technical Report 1648, University of Wisconsin–Madison. [8] Burr Settles, M. Craven (2008) ‘An analysis of active learning strategies for sequence labeling tasks’ In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1069–1078. [9] DC.A. Thompson, M.E. Califf and R.J. Mooney (1999) ‘Active learning for natural language parsing and information extraction’, In Proceedings of the 16th International Conference on Machine Learning, pp. 406-414. [10] C. Campbell, N. Cristianini, & A. Smola (2000). Query learning with large margin classifiers. Proceedings of the Seventeenth International Conference on Machine Learning. [11] C. E. Shannon, (1948) ‘A mathematical theory of communication’ Bell System Technical Journal, 27:379-423,623-656. [12] C.J. Burges. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 1999. [13] C. Nakajima, I. Norihiko, M. Pontil & Poggio (2000). Object recognition and detection by a combination of support vector machine and rotation 61 invariant phase only correlation. Proceedings of International Conference on Pattern Recognition. [14] D.D. Lewis, W. Gale (1994) ‘A sequential algorithm for training text classifiers’, In Proceedings of the ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 3-12. [15] D.D. Lewis, J. Catlett (1994) ‘Heterogeneous Uncertainty Sampling for Supervised Learning’ In Proceedings of the 11th International Conference on Machine Learning, pp.148-156. [16] D. Hakkani-Tür, G. Riccardi and A. Gorin (2002) ‘Active learning for automatic speech recognition’ In Proceedings of ‘International Conference on Acoustics, Speech and Signal Processing (ICASSP), Orlando, FL. [17] F. Rosenblatt (1958). The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65:386–407. [18] G. Tur, D. Hakkani-Tür and R.E. Schapire (2005) ‘Combining active and semisupervised learning for spoken language understanding’ Speech Communication, 45(2):171–186. [19] G. Tur, R.E. Schapire and D. Hakkani-Tür (2003) ‘Active learning for spoken language understanding’ In Proceedings of International Conference on Acoustics, Speech and Signal Processing (ICASSP), Hong Kong. [20] H. Seung, M. Opper & H. Sompolinsky (1992). Query by committee. Proceedings of Computational Learning Theory. [21] J. Baldridge, M. Osborne (2004) ‘Active learning and the total cost of annotation’, In Proceedings of the Conference on Empirical Methods in Natural Language Processing, Forum Convention Center, Barcelona, Spain, pp. 9-16 [22] J. Zhu, H. Wang, E. Hovy (2008a) ‘Learning a stopping criterion for active learning for word sense disambiguation and text classification’ In Proceedings of the 3rd International Joint Conference on NLP (IJNLP), Heydarabad, India. pp. 366-372. [23] J. Zhu, H. Wang, T. Yao and B. Tsou (2008b) ‘Active learning with sampling by uncertainty and density for word sense disambiguation and text classification’ In Proceedings of the 22nd International Conference on Computational Linguistics (CoLing) pp. 1137-1144. [24] LeCun, Jackel, Bottou, Brunot, A., Cortes, C., Denker, J. S., Drucker, H., Guyon, I., Muller, U. A., Sackinger, E., Simard, P., & Vapnik (1995). Comparison of learning algorithms for handwritten digit recognition. International Conference on Artificial Neural Networks, Paris. [25] M. Steedman, R. Hwax, S. Clark, M. Osborne, A. Sarkar, J. Hockenmaier, P. Ruhleny, S. Bakerz, J. Crimy (2003) ‘Example selection for bootstrapping statistical parsers’ In Proceedings of the Human Language Technology 62 Conference / North American Chapter of the Association for Computational Linguistics (HLT/NAACL), Edmonton, Canada. [26] R. Hwa, (2000) ‘Sample selection for statistical grammar induction’ In Proceedings of the 2000 Joint SIGDAT Conference on EMNLP and VLC, Hong Kong, China, pp. 45.52. [27] R. Hwa, M. Osborne and A. Sarkar and M. Steedman (2003) ‘Corrected cotraining for statistical parsers’ In Proceedings of the ICML Workshop: The Continuum from Labeled to Unlabeled Data. pp. 95-102. [28] R. Herbrich, T. Graepel, & C. Campbell (1999). Bayes point machines: Estimating the Bayes point in kernel space. International Joint Conference on Artificial Intelligence Workshop on Support Vector Machines. [29] R. Liere, P. Tadepalli (1997) ‘Active learning with committees for text categorization’ In Proceedings 14th Conference of the American Association for Artificial Intelligence (AAAI), pp. 591-596. [30] S. Agmon (1954). The relaxation method for linear inequalities. Canadian Journal of Math., 6(3):382–392. [31] S.C.H Hoi, R. Jin, M.R. Lyu (2006) ‘Large-scale text categorization by batch mode active learning’ In Proceedings of the International Conference on the World Wide Web, pp. 633–642. [32] S. Dasgupta (2005). Coarse sample complexity bounds for active learning. In Advances in Neural Information Processing Systems 18. [33] S. Dumais, J. Platt, D. Heckerman & M. Sahami (1999). Inductive learning algorithms and representations for text categorization. Proceedings of the Seventh International Conference on Information and Knowledge Management. ACM Press. [34] S. Hampson and D. Kibler (1999). Minimum generalization via reflection: A fast linear threshold learner. Machine Learning, 37(1):51–73. [35] S. Tong and D. Koller. Support vector machine active learning with applications to text classification. Journal of Machine Learning Research, 2:45–66, 2001. [36] S. Tong, (2001) Active Learning: Theory and Applications. Ph.D. dissertation, Stanford University. [37] T. Joachims. Text categorization with support vector machines. Proceedings of the European Conference on Machine Learning. Springer-Verlag, 1999. [38] T. Joachims. Transductive inference for text classification using support vector machines. Proceedings of the Sixteenth International Conference on Machine Learning. Morgan Kaufmann, 1999. 63 [39] T. Mitchell (1982). Generalization as search. Artificial Intelligence. [40] T.S. Motzkin and I.J. Schoenberg (194). The relaxation method for linear inequalities. Canadian Journal of Math., 6(3):393–404. [41] V. Vapnik. Estimation of dependences based on empirical data. Springer Verlag, 1982. [42] V. Vapnik. The nature of statistical learning theory. Springer, New York, 1995. [43] V. Vapnik, (1998). Statistical learning theory. Wiley. [44] Y. Baram, R. El-Yaniv and K. Luz (2004) ‘Online choice of active learning algorithm’ In Journal of Machine Learning Research 5, pp. 255-259 [45] Y. Freund, H. Seung, E. Shamir & N. Tishby (1992). Selective sampling using the Query by Committee algorithm. Machine Learning. Website: [46] [47]