Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Lớp biên lớn với sự tương đồng không xác định
Tóm tắt
Lớp phân loại với sự tương đồng không xác định đã thu hút sự chú ý trong cộng đồng học máy. Điều này một phần do thực tế rằng nhiều hàm tương đồng phát sinh trong thực tiễn không đối xứng và không xác định dương, tức là điều kiện Mercer không được thỏa mãn, hoặc điều kiện Mercer rất khó để xác minh. Các ví dụ về những sự tương đồng không xác định trong các ứng dụng học máy rất phong phú, chẳng hạn như điểm tương đồng BLAST giữa các chuỗi protein, sự tương đồng được đánh giá bởi con người giữa các khái niệm và từ ngữ, cũng như khoảng cách tiếp tuyến hay khoảng cách hình dạng trong thị giác máy tính. Tuy nhiên, những công trình trước đây về phân loại với sự tương đồng không xác định không hoàn toàn thỏa đáng. Chúng đã hoặc giới thiệu các nguồn không nhất quán trong việc xử lý các ví dụ trong quá khứ và tương lai bằng cách khoảng cách hạt nhân, hoặc đã chọn giải pháp tối thiểu cục bộ bằng cách tối ưu hóa không lồi, hoặc đã sản xuất những giải pháp không thưa bằng cách học trong các không gian Krein. Mặc dù có khối lượng nghiên cứu lớn dành cho chủ đề này gần đây, chúng tôi chứng minh trong bài báo này rằng một ý tưởng cũ, cụ thể là máy vector hỗ trợ chuẩn 1 (SVM) được đề xuất cách đây hơn 15 năm, có nhiều lợi thế hơn so với các công trình gần đây hơn. Đặc biệt, phương pháp SVM chuẩn 1 có khái niệm đơn giản hơn, điều này giúp việc triển khai và bảo trì dễ dàng hơn. Nó cạnh tranh, nếu không muốn nói là vượt trội hơn, tất cả các phương pháp khác về độ chính xác dự đoán. Hơn nữa, nó sản xuất ra những giải pháp thường thưa hơn nhiều so với các phương pháp gần đây tới nhiều bậc. Ngoài ra, chúng tôi cung cấp nhiều lý do lý thuyết bằng cách liên kết SVM chuẩn 1 với các thuật toán học đã được thiết lập tốt như mạng nơ-ron, SVM và bộ phân loại k-láng giềng. Cuối cùng, chúng tôi tiến hành đánh giá thực nghiệm sâu rộng, cho thấy rằng bằng chứng ủng hộ SVM chuẩn 1 là có ý nghĩa thống kê.
Từ khóa
#học máy #phân loại #hỗ trợ vector #độ chính xác dự đoán #khoảng cách #không gian KreinTài liệu tham khảo
Abu-Mostafa, Y. S., Magdon-Ismail, M., & Lin, H. T. (2012). Learning from data. AMLBook.
Balcan, M. F., Blum, A., & Srebro, N. (2008). A theory of learning with similarity functions. Machine Learning, 72(1–2), 89–112.
Bartlett, P. L. (1997). For valid generalization, the size of the weights is more important than the size. Advances in Neural Information Processing Systems (NIPS), 9, 134.
Lichman, M. (2013). UCI machine learning repository. Irvine, CA: University of California, School of Information and Computer Sciences. http://archive.ics.uci.edu/ml
Boser, B. E., Guyon, I., & Vapnik, V. (1992) A training algorithm for optimal margin classifiers. In Fifth annual workshop on computational learning theory (pp. 144–152).
Boyd, S., & Vandenberghe, L. (2004). Convex optimization. Cambridge: Cambridge university press.
Bradley, P. S., & Mangasarian, O. L. (1998). Feature selection via concave minimization and support vector machines. In ICML.
Burges, C. (1999). Geometry and invariance in kernel based methods. In B. Schölkopf, C. J. C. Burges, & A. J. Smola (Eds.), Advances in kernel methods–support vector learning (pp. 89–116). Cambridge, MA: MIT Press.
Burges, C. J. (1998). A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 2, 121–167.
Chang, C., & Lin, C. J. (2001). LIBSVM: A library for support vector machines (online). http://www.csie.ntu.edu.tw/cjlin/libsvm.
Chen, J., & Ye, J. (2008). Training SVM with indefinite kernels. In Proceedings of ICML (pp. 136–143).
Chen, Y., Garcia, E. K., Gupta, M. R., Rahimi, A., & Cazzanti, L. (2009a). Similarity-based classification: Concepts and algorithms. JMLR, 10, 747–776.
Chen, Y., Gupta, M. R., & Recht, B. (2009b). Learning kernels from indefinite similarities. In Proceedings of ICML (pp. 145–152).
Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine learning, 20(3), 273–297.
Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1), 21–27.
Demšar, J. (2006). Statistical comparisons of classifiers over multiple data sets. JMLR, 7, 1–30.
Fei-Fei, L., Fergus, R., & Perona, P. (2004). Learning generative visual models from few training examples: An incremental Bayesian approach tested on 101 object categories. In IEEE CVPR: Workshop on generative-model based vision.
Finkelstein, L., Gabrilovich, E., Matias, Y., Rivlin, E., Solan, Z., Wolfman, G., et al. (2002). Placing search in context: The concept revisited. ACM Transactions on Information Systems, 20(1), 116–131.
Fung, G. M., & Mangasarian, O. L. (2004). A feature selection Newton method for support vector machine classification. Computational Optimization and Applications, 28, 185–202.
Graepel, T., Herbrich, R., Bollmann-Sdorra, P., & Obermayer, K. (1999). Classification on pairwise proximity data. In M. J. Kearns, S. A. Solla, & D. A. Cohn (Eds.), Advances in NIPS (pp. 438–444). MIT Press.
Gurobi Optimization I. (2012). Gurobi optimizer reference manual. http://www.gurobi.com.
Haasdonk, B. (2005). Feature space interpretation of svms with indefinite kernels. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(4), 482–492.
Hastie, T., Tibshirani, R., & Friedman, J. (2001). The elements of statistical learning: Data mining, inference, and prediction. Springer series in statistics (2nd ed.). Springer.
Hilario, M., & Kalousis, A. (2008). Approaches to dimensionality reduction in proteomic biomarker studies. Briefings in Bioinformatics, 9(2), 102–118.
Holm, S. (1979). A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 6(2), 65–70.
IBM I. (2015). Cplex optimizer. http://www.ibm.com/software/commerce/optimization/cplex-optimizer/.
Lin, H. T., & Lin, C. J. (2003). A study on sigmoid kernels for SVM and the training of non-PSD kernels by SMO-type methods. Tech. rep., Department of Computer Science, National Taiwan University. http://www.csie.ntu.edu.tw/cjlin/papers/tanh.pdf.
Liu, H., Motoda, H., Setiono, R., & Zhao, Z. (2010). Feature selection: An ever evolving frontier in data mining. In 4th workshop on feature selection in data mining (FSDM 10), PAKDD. pp. 4–13.
Loosli, G., Ong, C. S., & Canu, S. (2013). SVM in Krein spaces. Tech. rep. http://hal.archives-ouvertes.fr/hal-00869658/.
Luntz, A., & Brailovsky, V. (1969). On estimation of characters obtained in statistical procedure of recognition. Technicheskaya Kibernetica, 3(6) (in Russian).
Luss, R., & d’Aspremont, A. (2009). Support vector machine classification with indefinite kernels. Mathematical Programming Computation, 1(2–3), 97–118.
Macskassy, S. A., & Provost, F. (2007). Classification in networked data: A toolkit and a univariate case study. JMLR, 8, 935–983.
Mangasarian, O. L. (1998). Generalized support vector machines. Tech. Rep. Mathematical Programming Technical Report 98-14, University of Wisconsin.
Mohri, M., Rostamizadeh, A., & Talwalkar, A. (2012). Foundations of machine learning. Cambridge: MIT Press.
Noordewier, M. O., Towell, G. G., & Shavlik, J. W. (1991). Training knowledge-based neural networks to recognize genes in dna sequences. In R. P. Lippmann, J. E. Moody, & D. S. Touretzky (Eds.), Advances in NIPS (pp. 530–536). Morgan-Kaufmann.
Ong, C. S., Mary, X., Canu, S., & Smola, A. J. (2004). Learning with non-positive kernels. In ICML.
Park, J., & Sandberg, I. W. (1991). Universal approximation using radial-basis-function networks. Neural Computation, 3(2), 246–257.
Pekalska, E., Paclik, P., & Duin, R. P. (2001). A generalized kernel approach to dissimilarity-based classification. JMLR, 2, 175–211.
Schapire, R. E., Freund, Y., Bartlett, P., & Lee, W. S. (1998). Boosting the margin: A new explanation for the effectiveness of voting methods. Annals of Statistics, 26(5), 1651–1686.
Schölkopf, B., & Smola, A. J. (2002). Learning with kernels: Support vector machines, regularization, optimization, and beyond. Cambridge: MIT Press.
Soman, K. P., Loganathan, R., & Ajay, V. (2009). Machine Learning with SVM and other Kernel methods. PHI Learning.
Tipping, M. E. (2001). Sparse bayesian learning and the relevance vector machine. JMLR, 1, 211–244.
Vapnik, V., & Chapelle, O. (2000). Bounds on error expectation for support vector machines. Neural Computation, 12(9), 2013–2036.
Vapnik, V. N. (1999). An overview of statistical learning theory. IEEE Transactions on Neural Networks, 10(5), 988–999.
Wu, G., Zhang, Z., & Chang, E. Y. (2005). An analysis of transformation on non-positive semidefinite similarity matrix for kernel machines. Tech. rep., UCSB.
Wu, X., Kumar, V., Ross Quinlan, J., Ghosh, J., Yang, Q., Motoda, H., et al. (2008). Top 10 algorithms in data mining. Knowledge and Information Systems, 14(1), 1–37.
Ying, Y., Campbell, C., & Girolami, M. (2009). Analysis of SVM with indefinite kernels. Advances in NIPS, 22, 2205–2213.
Zhu, J., Rosset, S., Hastie, T., & Tibshirani, R. (2004). 1-norm support vector machines. Advances in Neural Information Processing Systems (NIPS), 16, 49–56.
Zou, H. (2007). An improved 1-norm SVM for simultaneous classification and variable selection. In Proceedings of the 11th international conference on artificial intelligence and statistics (pp. 675–681).