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

Trong bốn thuật toán đã sử dụng thực nghiệm trong chương trình ActiveExperiment thì có ba thuật toán đều cho kết quả cao và tương tự ngang nhau. Riêng thuật toá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 toá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

Có thể bạn quan tâm!

Xem toàn bộ 65 trang tài liệu này.

Bảng 4.4 Kết quả chạy qua 20 lần truy vấn của các thuật toá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.

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 toá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 toá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 toán thuật toá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 toá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 toá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 toán chưa được cao.

4.4 Kết luận‌

Chương này đã giới thiệu bài toán lọc thư rác và áp dụng phươg pháp học tích cực và trong bài toá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 toá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.

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 toá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 toán học perceptron đã được cải tiến của Dagupsta đề xuất năm 2005. Thuật toá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 toá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 toá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 toán lọc thư rác, xây dựng mô hình cho bài toá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

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 toán perceptron và 93.7% đối với các thuật toá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 toá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 toá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.

Tiếng Việt

TÀI LIỆU THAM KHẢO

[1] Hà Quang Thụy, Phan Xuân Hiếu, Đoà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 classiﬁers. 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

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 Artiﬁcial 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

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 Artiﬁcial 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 reﬂection: 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 classiﬁcation. 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 classiﬁcation using support vector machines. Proceedings of the Sixteenth International Conference on Machine Learning. Morgan Kaufmann, 1999.

[39] T. Mitchell (1982). Generalization as search. Artiﬁcial 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] http://l2r.cs.uiuc.edu/~cogcomp/asoftware.php?skey=SNOW

[47] http://www.cs.technion.ac.il/~rani/code/active/code_index.html