Three-way learnability: A learning theoretic perspective on Three-way Decision

• Autorzy: Campagner Andrea , Ciucci Davide

Identyfikatory

DOI

10.15439/2022F18

• Konferencja: Federated Conference on Computer Science and Information Systems (17 ; 04-07.09.2022 ; Sofia, Bulgaria)
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

computer science; evidence theory; statistical learning; probability distribution; complexity theory; standard

PL

informatyka; teoria dowodu; statystyka; uczenie się; rozkład prawdopodobieństwa; teoria złożoności; standard

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2022
• Tom: Vol. 30
• Strony: 243--246
• Opis fizyczny: Bibliogr. 26 poz., wz.

Twórcy

autor

Campagner Andrea

• Dipartimento di Informatica, Sistemistica e Comunicazione, University of Milano–Bicocca, Viale Sarca 336/14, 20126 Milano, Italy

autor

Ciucci Davide

• Dipartimento di Informatica, Sistemistica e Comunicazione, University of Milano–Bicocca, Viale Sarca 336/14, 20126 Milano, Italy

Bibliografia

• 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.

Uwagi

1. Short article

2. Track 5: 4th International Symposium on Rough Sets: Theory and Applications

3. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).