Logo PTI Logo FedCSIS

Proceedings of the 17th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 30

Three-way Learnability: A Learning Theoretic Perspective on Three-way Decision

,

DOI: http://dx.doi.org/10.15439/2022F18

Citation: Proceedings of the 17th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 30, pages 243–246 ()

Full text

Abstract. In this article we study the theoretical properties of Three-way Decision (TWD) based Machine Learning, from the perspective of Computational Learning Theory, as a first attempt to bridge the gap between Machine Learning theory and Uncertainty Representation theory. Drawing on the mathematical theory of orthopairs, we provide a generalization of the PAC learning framework to the TWD setting, and we use this framework to prove a generalization of the Fundamental Theorem of Statistical Learning. We then show, by means of our main result, a connection between TWD and selective prediction.

References

  1. E. Hüllermeier, “Learning from imprecise and fuzzy observations: Data disambiguation through generalized loss minimization,” International Journal of Approximate Reasoning, vol. 55, no. 7, pp. 1519–1534, 2014.
  2. G. Ma, F. Liu, G. Zhang, and J. Lu, “Learning from imprecise observations: An estimation error bound based on fuzzy random variables,” in 2021 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE). IEEE, 2021, pp. 1–8.
  3. S. Abbaszadeh and E. Hullermeier, “Machine learning with the sugeno integral: The case of binary classification,” IEEE Transactions on Fuzzy Systems, 2020.
  4. E. Hüllermeier and A. F. Tehrani, “On the vc-dimension of the choquet integral,” in International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems. Springer, 2012, pp. 42–50.
  5. Y. Yao, “Three-way decision: an interpretation of rules in rough set theory,” in International Conference on Rough Sets and Knowledge Technology. Springer, 2009, pp. 642–649.
  6. M. Ma, “Advances in three-way decisions and granular computing,” Knowl.-Based Syst, vol. 91, pp. 1–3, 2016.
  7. M. Hu, “Three-way bayesian confirmation in classifications,” Cognitive Computation, pp. 1–20, 2021.
  8. F. Min, S.-M. Zhang, D. Ciucci, and M. Wang, “Three-way active learning through clustering selection,” International Journal of Machine Learning and Cybernetics, pp. 1–14, 2020.
  9. H. Yu, X. Wang, G. Wang, and X. Zeng, “An active three-way clustering method via low-rank matrices for multi-view data,” Information Sciences, vol. 507, pp. 823–839, 2020.
  10. H. Li, L. Zhang, X. Zhou, and B. Huang, “Cost-sensitive sequential three-way decision modeling using a deep neural network,” International Journal of Approximate Reasoning, vol. 85, pp. 68–78, 2017.
  11. M. K. Afridi, N. Azam, and J. Yao, “Variance based three-way clustering approaches for handling overlapping clustering,” International Journal of Approximate Reasoning, vol. 118, pp. 47–63, 2020.
  12. P. Wang and Y. Yao, “Ce3: A three-way clustering method based on mathematical morphology,” Knowledge-based systems, vol. 155, pp. 54–65, 2018.
  13. A. Campagner, F. Cabitza, P. Berjano, and D. Ciucci, “Three-way decision and conformal prediction: Isomorphisms, differences and theoretical properties of cautious learning approaches,” Information Sciences, vol. 579, pp. 347–367, 2021.
  14. A. Campagner and D. Ciucci, “A formal learning theory for three-way clustering,” in International Conference on Scalable Uncertainty Management. Springer, 2020, pp. 128–140.
  15. R. Gelbhart and R. El-Yaniv, “The relationship between agnostic selective classification, active learning and the disagreement coefficient.” J. Mach. Learn. Res., vol. 20, no. 33, pp. 1–38, 2019.
  16. L. Li, M. L. Littman, T. J. Walsh, and A. L. Strehl, “Knows what it knows: a framework for self-aware learning,” Machine learning, vol. 82, no. 3, pp. 399–443, 2011.
  17. D. Ciucci, “Orthopairs and granular computing,” Granular Computing, vol. 1, no. 3, pp. 159–170, 2016.
  18. S. Shalev-Shwartz and S. Ben-David, Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
  19. L. G. Valiant, “A theory of the learnable,” Communications of the ACM, vol. 27, no. 11, pp. 1134–1142, 1984.
  20. V. Vapnik, “On the uniform convergence of relative frequencies of events to their probabilities,” in Doklady Akademii Nauk USSR, vol. 181, no. 4, 1968, pp. 781–787.
  21. R. El-Yaniv et al., “On the foundations of noise-free selective classification.” Journal of Machine Learning Research, vol. 11, no. 5, 2010.
  22. S. Goldwasser, A. T. Kalai, Y. Kalai, and O. Montasser, “Beyond perturbations: Learning guarantees with arbitrary adversarial test examples,” Advances in Neural Information Processing Systems, vol. 33, pp. 15 859–15 870, 2020.
  23. N. Alon, S. Hanneke, R. Holzman, and S. Moran, “A theory of pac learnability of partial concept classes,” arXiv preprint https://arxiv.org/abs/2107.08444, 2021.
  24. O. Rivasplata, I. Kuzborskij, C. Szepesvári, and J. Shawe-Taylor, “Pac-bayes analysis beyond the usual bounds,” arXiv preprint https://arxiv.org/abs/2006.13057, 2020.
  25. F. Cuzzolin, The geometry of uncertainty. Springer, 2017.
  26. Y. Yao and P. Lingras, “Interpretations of belief functions in the theory of rough sets,” Information sciences, vol. 104, no. 1-2, pp. 81–106, 1998.