International Journal of Nonlinear Analysis and Applications
A new variant of online binary passive-aggressive algorithm for interval data
Document Type : Research Paper
Authors
1 Department of Mathematics, Faculty of Engineering Science, Quchan University of Technology, Quchan, Iran
2 Department of Computer Engineering, Faculty of Electrical and Computer Engineering, Quchan University of Technology, Quchan, Iran
Abstract
Online algorithms process data sequentially, updating their parameters as new data points arrive to minimize prediction errors. However, traditional online algorithms are not inherently designed to handle interval data, which poses a significant challenge in many real-world applications. In this paper, we propose a novel online binary classification algorithm specifically tailored for interval data. We introduce a new loss function that extends the online passive-aggressive (PA) framework, enabling it to effectively handle both ordinal and interval data. The proposed loss function is computationally efficient and provides a robust solution for online learning in the presence of interval data. We provide theoretical guarantees for the algorithm, including cumulative squared loss bounds and relative loss bounds, which demonstrate its effectiveness. Empirical evaluations on multiple datasets show that our method achieves competitive performance compared to existing online algorithms while uniquely addressing the challenges posed by interval data.
Keywords
[1] C. Angulo, D. Anguita, L. Gonzalez-Abril, and J. A. Ortega, Support vector machines for interval discriminant analysis, Neurocomputing 71 (2008), no. 7, 1220-1229.
[2] M. Baymani, N. Salehi-M., and A. Mansoori, Applying norm concepts for solving interval support vector machine, Neurocomputing 311 (2018), 41-50.
[3] J. Bergstra, R. Bardenet, Y. Bengio, and B. Kégl, Algorithms for hyper-parameter optimization, Advances in neural information processing systems, vol. 24, 2011.
[4] A. Blanco-Fernandez, A. Colubi, and M. García-Bárzana, A set arithmetic-based linear regression model for modelling interval-valued responses through real-valued variables, Inf. Sci. 247 (2013), 109-122.
[5] G. Cavallanti, N. Cesa-Bianchi, and C. Gentile, Tracking the best hyper-plane with a simple budget perceptron, Machine Learn. 69 (2007), no. 2, 143-167.
[6] Y. Chen and J. Z. Wang, Support vector learning for fuzzy rule-based classification systems, IEEE Trans. Fuzzy Syst. 11 (2003), no. 6, 716-728.
[7] Z. Chen, Robust sparse online learning through adversarial sparsity constraints, 2024 9th IEEE Int. Conf. Smart Cloud (SmartCloud), IEEE, 2024, pp. 42-47.
[8] L. Cheng, D. Schuurmans, S. Wang, T. Caelli, and S. Vishwanathan, Implicit online learning with kernels, Advances in neural information processing systems, MIT Press, 2007, pp. 249-256.
[9] W.-Y. Cheng and C.-F. Juang, An incremental support vector machine-trained TS-type fuzzy system for online classification problems, Fuzzy Sets and Systems 163 (2011), no. 1, 24-44.
[10] C. Cortes and V. Vapnik, Support-vector networks, Machine Learn. 20 (1995), no. 3, 273-297.
[11] K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer, Online passive-aggressive algorithms, J. Machine Learn. Res. 7 (2006), 551-585.
[12] K. Crammer, J. Kandola, and Y. Singer, Online classification on a budget, Advances in Neural Information Processing Systems, vol. 16, MIT Press, Cambridge, MA, 2004, pp. 225-232.
[13] F.D.A. de Carvalho, P. Brito, and H.-H. Bock, Dynamic clustering for interval data based on l2 distance, Comput. Statist. 21 (2006), no. 2, 231-250.
[14] R.M. de Souza and F.D. A. De Carvalho, Clustering of interval data based on city-block distances, Pattern Recog. Lett. 25 (2004), no. 3, 353-365.
[15] O. Dekel, S. Shalev-Shwartz, and Y. Singer, The forgerton: A kernel-based perceptron on a fixed budget, Advances in Neural Information Processing Systems, vol. 18, 2005, pp. 259-266.
[16] H. Edelstein, Introduction to data mining and knowledge discovery, 3rd ed., Two Crows Corporation, Potomac, MD, USA, 1999.
[17] Y. Forghani and H. S. Yazdi, Robust support vector machine-trained fuzzy system, Neural Networks 50 (2014), 154-165.
[18] Y. Freund and R. E. Schapire, Large margin classification using the perceptron algorithm, Machine Learn. 37 (1999), no. 3, 277-296.
[19] S.C. Hoi, D. Sahoo, J. Lu, and P. Zhao, Online learning: A comprehensive survey, arXiv preprint arXiv:1802.02871 (2018).
[20] S. C. H. Hoi, J. Wang, P. Zhao, J. Zhuang, and Z. Liu, Large scale online kernel classification, Int. Joint Conf. Artific. Intell., IJCAI/AAAI, 2013, pp. 1750-1756.
[21] E. Hullermeier, Learning from imprecise and fuzzy observations: Data disambiguation through generalized loss minimization, Int. J. Approx. Reason. 55 (2014), no. 7, 1519-1534.
[22] J. Kivinen, A.J. Smola, and R.C. Williamson, Online learning with kernels, Advances in neural information processing systems, 2002, pp. 785-792.
[23] J. Kivinen, A.J. Smola, and R.C. Williamson, Online learning with kernels, IEEE Trans. Signal Process. 52 (2004), no. 8, 2165-2176.
[24] J. Langford, L. Li, and T. Zhang, Sparse online learning via truncated gradient, J. Machine Learn. Res. 10 (2009), 777-801.
[25] S. Lee, Y. Liao, M.H. Seo, and Youngki Shin, Fast and robust online inference with stochastic gradient descent via random scaling, Proc. AAAI Conf. Artific. Intell., vol. 36, 2022, pp. 7381-7389.
[26] Y. Liu, X. Fan, W. Li, and Y. Gao, Online passive-aggressive active learning for trapezoidal data streams, IEEE Trans. Neural Networks Learn. Syst. 34 (2022), no. 10, 6725-6739.
[27] J. Lu, S.C. Hoi, J. Wang, P. Zhao, and Z.-Y. Li, Large scale online kernel learning, J. Machine Learn. Res. 17 (2016), 1-43.
[28] F. Orabona, J. Keshet, and B. Caputo, The projectron: A bounded kernel-based perceptron, Proc. 25th Int. Conf. Machine learn., ACM, 2008, pp. 720-727.
[29] F. Orabona, J. Keshet, and B. Caputo, Bounded kernel-based online learning, J. Machine Learn. Res. 10 (2009), 2643-2666.
[30] W. Qin and X. Luo, Asynchronous parallel fuzzy stochastic gradient descent for high-dimensional incomplete data representation, IEEE Trans. Fuzzy Syst. 32 (2023), no. 2, 445-459.
[31] A.B. Ramos-Guajardo and P. Grzegorzewski, Distance-based linear discriminant analysis for interval-valued data, Inf. Sci. 372 (2016), 591-607.
[32] F. Rosenblatt, The perceptron: A probabilistic model for information storage and organization in the brain, Psychol. Rev. 65 (1958), no. 6, 386-408.
[33] B. Scholkopf and A.J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, MIT Press, Cambridge, MA, USA, 2001.
[34] J. Shawe-Taylor and N. Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, New York, NY, USA, 2004.
[35] V. Sindhwani, P. Niyogi, and M. Belkin, Beyond the point cloud: from transductive to semi-supervised learning, Proc. 22nd Int. Conf. Machine Learn., ACM, 2005, pp. 824-831.
[36] L. V. Utkin, A. I. Chekh, and Y. A. Zhuk, Binary classification SVM-based algorithms with interval-valued training data using triangular and Epanechnikov kernels, Neural Networks 80 (2016), 53-66.
[37] L. Wang, H.-B. Ji, and Y. Jin, Fuzzy passive-aggressive classification: A robust and efficient algorithm for online classification problems, Inf. Sci. 220 (2013), 46-63.
[38] Z. Wang, K. Crammer, and S. Vucetic, Breaking the curse of kernelization: Budgeted stochastic gradient descent for large-scale SVM training, J. Machine Learn. Res. 13 (2012), no. 1, 3103-3131.
[39] Z. Wang and S. Vucetic, Online passive-aggressive algorithms on a budget, Proc. Thirteenth Int. Conf. Artific. Intell. Statist., vol. 9, 2010, pp. 908-915.
[40] C.-H. Wu, H. Horng-Shing Lu, and H.-M. Hang, Budgeted passive-aggressive learning for online multiclass classification, IEEE Access 8 (2020), 227420-227437.
[41] T. Zhai and H. Wang, Online passive-aggressive multilabel classification algorithms, IEEE Trans. Neural Networks Learn. Syst. 34 (2022), no. 12, 10116-10129.
[42] Y. Zhang, Learning label correlations for multi-label online passive aggressive classification algorithm, Wuhan Univ. J. Natur. Sci. 29 (2024), no. 1, 51-58.
[43] P. Zhao, J. Wang, P. Wu, R. Jin, and S.C. Hoi, Fast bounded online gradient descent algorithms for scalable kernel-based online learning, Proc. 29th Int. Conf. Machine Learn., Omnipress, New York, NY, USA, 2012, pp. 169-176.
[44] Z. Zhou, W.-S. Zheng, J.-F. Hu, Y. Xu, and J. You, One-pass online learning: A local approach, Pattern Recogn. 51 (2016), 346-357.
[2] M. Baymani, N. Salehi-M., and A. Mansoori, Applying norm concepts for solving interval support vector machine, Neurocomputing 311 (2018), 41-50.
[3] J. Bergstra, R. Bardenet, Y. Bengio, and B. Kégl, Algorithms for hyper-parameter optimization, Advances in neural information processing systems, vol. 24, 2011.
[4] A. Blanco-Fernandez, A. Colubi, and M. García-Bárzana, A set arithmetic-based linear regression model for modelling interval-valued responses through real-valued variables, Inf. Sci. 247 (2013), 109-122.
[5] G. Cavallanti, N. Cesa-Bianchi, and C. Gentile, Tracking the best hyper-plane with a simple budget perceptron, Machine Learn. 69 (2007), no. 2, 143-167.
[6] Y. Chen and J. Z. Wang, Support vector learning for fuzzy rule-based classification systems, IEEE Trans. Fuzzy Syst. 11 (2003), no. 6, 716-728.
[7] Z. Chen, Robust sparse online learning through adversarial sparsity constraints, 2024 9th IEEE Int. Conf. Smart Cloud (SmartCloud), IEEE, 2024, pp. 42-47.
[8] L. Cheng, D. Schuurmans, S. Wang, T. Caelli, and S. Vishwanathan, Implicit online learning with kernels, Advances in neural information processing systems, MIT Press, 2007, pp. 249-256.
[9] W.-Y. Cheng and C.-F. Juang, An incremental support vector machine-trained TS-type fuzzy system for online classification problems, Fuzzy Sets and Systems 163 (2011), no. 1, 24-44.
[10] C. Cortes and V. Vapnik, Support-vector networks, Machine Learn. 20 (1995), no. 3, 273-297.
[11] K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer, Online passive-aggressive algorithms, J. Machine Learn. Res. 7 (2006), 551-585.
[12] K. Crammer, J. Kandola, and Y. Singer, Online classification on a budget, Advances in Neural Information Processing Systems, vol. 16, MIT Press, Cambridge, MA, 2004, pp. 225-232.
[13] F.D.A. de Carvalho, P. Brito, and H.-H. Bock, Dynamic clustering for interval data based on l2 distance, Comput. Statist. 21 (2006), no. 2, 231-250.
[14] R.M. de Souza and F.D. A. De Carvalho, Clustering of interval data based on city-block distances, Pattern Recog. Lett. 25 (2004), no. 3, 353-365.
[15] O. Dekel, S. Shalev-Shwartz, and Y. Singer, The forgerton: A kernel-based perceptron on a fixed budget, Advances in Neural Information Processing Systems, vol. 18, 2005, pp. 259-266.
[16] H. Edelstein, Introduction to data mining and knowledge discovery, 3rd ed., Two Crows Corporation, Potomac, MD, USA, 1999.
[17] Y. Forghani and H. S. Yazdi, Robust support vector machine-trained fuzzy system, Neural Networks 50 (2014), 154-165.
[18] Y. Freund and R. E. Schapire, Large margin classification using the perceptron algorithm, Machine Learn. 37 (1999), no. 3, 277-296.
[19] S.C. Hoi, D. Sahoo, J. Lu, and P. Zhao, Online learning: A comprehensive survey, arXiv preprint arXiv:1802.02871 (2018).
[20] S. C. H. Hoi, J. Wang, P. Zhao, J. Zhuang, and Z. Liu, Large scale online kernel classification, Int. Joint Conf. Artific. Intell., IJCAI/AAAI, 2013, pp. 1750-1756.
[21] E. Hullermeier, Learning from imprecise and fuzzy observations: Data disambiguation through generalized loss minimization, Int. J. Approx. Reason. 55 (2014), no. 7, 1519-1534.
[22] J. Kivinen, A.J. Smola, and R.C. Williamson, Online learning with kernels, Advances in neural information processing systems, 2002, pp. 785-792.
[23] J. Kivinen, A.J. Smola, and R.C. Williamson, Online learning with kernels, IEEE Trans. Signal Process. 52 (2004), no. 8, 2165-2176.
[24] J. Langford, L. Li, and T. Zhang, Sparse online learning via truncated gradient, J. Machine Learn. Res. 10 (2009), 777-801.
[25] S. Lee, Y. Liao, M.H. Seo, and Youngki Shin, Fast and robust online inference with stochastic gradient descent via random scaling, Proc. AAAI Conf. Artific. Intell., vol. 36, 2022, pp. 7381-7389.
[26] Y. Liu, X. Fan, W. Li, and Y. Gao, Online passive-aggressive active learning for trapezoidal data streams, IEEE Trans. Neural Networks Learn. Syst. 34 (2022), no. 10, 6725-6739.
[27] J. Lu, S.C. Hoi, J. Wang, P. Zhao, and Z.-Y. Li, Large scale online kernel learning, J. Machine Learn. Res. 17 (2016), 1-43.
[28] F. Orabona, J. Keshet, and B. Caputo, The projectron: A bounded kernel-based perceptron, Proc. 25th Int. Conf. Machine learn., ACM, 2008, pp. 720-727.
[29] F. Orabona, J. Keshet, and B. Caputo, Bounded kernel-based online learning, J. Machine Learn. Res. 10 (2009), 2643-2666.
[30] W. Qin and X. Luo, Asynchronous parallel fuzzy stochastic gradient descent for high-dimensional incomplete data representation, IEEE Trans. Fuzzy Syst. 32 (2023), no. 2, 445-459.
[31] A.B. Ramos-Guajardo and P. Grzegorzewski, Distance-based linear discriminant analysis for interval-valued data, Inf. Sci. 372 (2016), 591-607.
[32] F. Rosenblatt, The perceptron: A probabilistic model for information storage and organization in the brain, Psychol. Rev. 65 (1958), no. 6, 386-408.
[33] B. Scholkopf and A.J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, MIT Press, Cambridge, MA, USA, 2001.
[34] J. Shawe-Taylor and N. Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, New York, NY, USA, 2004.
[35] V. Sindhwani, P. Niyogi, and M. Belkin, Beyond the point cloud: from transductive to semi-supervised learning, Proc. 22nd Int. Conf. Machine Learn., ACM, 2005, pp. 824-831.
[36] L. V. Utkin, A. I. Chekh, and Y. A. Zhuk, Binary classification SVM-based algorithms with interval-valued training data using triangular and Epanechnikov kernels, Neural Networks 80 (2016), 53-66.
[37] L. Wang, H.-B. Ji, and Y. Jin, Fuzzy passive-aggressive classification: A robust and efficient algorithm for online classification problems, Inf. Sci. 220 (2013), 46-63.
[38] Z. Wang, K. Crammer, and S. Vucetic, Breaking the curse of kernelization: Budgeted stochastic gradient descent for large-scale SVM training, J. Machine Learn. Res. 13 (2012), no. 1, 3103-3131.
[39] Z. Wang and S. Vucetic, Online passive-aggressive algorithms on a budget, Proc. Thirteenth Int. Conf. Artific. Intell. Statist., vol. 9, 2010, pp. 908-915.
[40] C.-H. Wu, H. Horng-Shing Lu, and H.-M. Hang, Budgeted passive-aggressive learning for online multiclass classification, IEEE Access 8 (2020), 227420-227437.
[41] T. Zhai and H. Wang, Online passive-aggressive multilabel classification algorithms, IEEE Trans. Neural Networks Learn. Syst. 34 (2022), no. 12, 10116-10129.
[42] Y. Zhang, Learning label correlations for multi-label online passive aggressive classification algorithm, Wuhan Univ. J. Natur. Sci. 29 (2024), no. 1, 51-58.
[43] P. Zhao, J. Wang, P. Wu, R. Jin, and S.C. Hoi, Fast bounded online gradient descent algorithms for scalable kernel-based online learning, Proc. 29th Int. Conf. Machine Learn., Omnipress, New York, NY, USA, 2012, pp. 169-176.
[44] Z. Zhou, W.-S. Zheng, J.-F. Hu, Y. Xu, and J. You, One-pass online learning: A local approach, Pattern Recogn. 51 (2016), 346-357.
)
Articles in Press, Corrected Proof
Available Online from 27 February 2026
- Receive Date: 20 October 2024
- Revise Date: 12 January 2025
- Accept Date: 19 January 2025