рус eng
«ИЗВЕСТИЯ ИРКУТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА». СЕРИЯ «МАТЕМАТИКА»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

Список выпусков > Серия «Математика». 2023. Том 43

О свойствах разложения функции потерь на смещение и разброс для метода kNN

Автор(ы)
В. М. Неделько1

1Институт математики им. С. Л. Соболева СО РАН, Новосибирск, Российская Федерация

Аннотация
Для метода ближайших соседей (kNN) существует общеизвестное аналитическое выражение для разложения ошибки регрессионной модели на смещение и разброс. Однако данное выражение справедливо только для классической постановки задачи регрессионного анализа, в которой случайной является только целевая переменная, а «объясняющие» переменные неслучайны. Получены аналитические выражения для разложения для некоторых постановок, когда все переменные являются случайными. В отличие от классической постановки в полученных выражениях компонента разброса демонстрирует различное поведение при разной размерности пространства, в частности, при размерности 1 разброс практически линейно увеличивается с ростом k, т.е. уменьшается с ростом сложности. Подобное поведение разложения на смещение и разброс является нежелательным его свойством при использовании для объяснения структуры ошибок обучения. В связи с этим представляется целесообразным использовать разложение ошибки на погрешность аппроксимации и статистическую погрешность. Компоненты последнего разложения всегда монотонны.
Об авторах
Неделько Виктор Михайлович, канд. физ.-мат. наук, доц., старший научный сотрудник, Институт математики им. С. Л. Соболева СО РАН, Российская Федерация, 630090, г. Новосибирск, nedelko@math.nsc.ru
Ссылка для цитирования
Nedel’ko V. M. On the Properties of Bias-Variance Decomposition for kNN Regression // Известия Иркутского государственного университета. Серия Математика. 2023. Т. 43. C. 110–121. https://doi.org/10.26516/1997-7670.2023.43.110
Ключевые слова
разложение на смещение и разброс, машинное обучение, метод k-ближайших соседей, проблема переобучения
УДК
519.246
MSC
68T10, 62H30
DOI
https://doi.org/10.26516/1997-7670.2023.43.110
Литература
  1. Double trouble in double descent: bias and variance(s) in the lazy regime / S. d’Ascoli, M. Refinetti, G. Biroli, F. Krzakala // Proceedings of the 37th International Conference on Machine Learning (ICML’20). 2020. JMLR.org. Article 213. P. 2280–2290.
  2. Reconciling modern machine learning practice and the classical bias-variance trade-off / M. Belkin, D. Hsu, S. Ma, S. Mandal // Proceedings of the National Academy of Sciences. 2019. Т. 116, № 32. С. 15849–15854. https://doi.org/10.1073/pnas.1903070116
  3. Berikov V. Semi-supervised classification using multiple clustering and low-rank matrix operations // Lecture Notes in Computer Science. 2019. Т. 11548. С. 529–540. https://doi.org/10.1007/978-3-030-22629-9_37
  4. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. 2009.
  5. Heskes T. Bias/variance decompositions for likelihood-based estimators // Neural Computation. 1998. Vol. 10, N 6. P. 1425–1433. http://doi.org/10.1162/089976698300017232
  6. Kanevskiy D., Vorontsov K. Cooperative coevolutionary ensemble learning // Multiple Classifier Systems, 7th International Workshop, MCS 2007, Prague, Czech Republic, May 23–25. 2007. С. 469–478. http://dx.doi.org/10.1007/978-3-540-72523-7_47
  7. Kotsiantis S. Bagging and boosting variants for handling classifications problems: A survey // The Knowledge Engineering Review. 2014. Vol. 29, N 1. P. 78–100. http://dx.doi.org/10.1017/S0269888913000313
  8. Лбов Г. С., Старцева Н. Г. Об одном понятии сложности стратегии природы в распознавании образов // Анализ данных в экспертных системах. Новосибирск, 1986. Вып. 117 : Вычислительные системы. С. 91–102.
  9. Лбов Г. С., Старцева Н. Г. Сложность распределений в задачах классификации // Доклады РАН. 1994. Т. 338, № 5. C. 592–594.
  10. Лбов Г. С., Старцева Н. Г. Логические решающие функции и вопросы статистической устойчивости решений. Новосибирск : Изд-во Ин-та математики, 1999. 211 с.
  11. Deep double descent: where bigger models and more data hurt / P. Nakkiran, G. Kaplun, Y. Bansal, T. Yang, B. Barak, I. Sutskever // Journal of Statistical Mechanics: Theory and Experiment. 2021.
  12. A Modern Take on the Bias-Variance Tradeoff in Neural Networks / B. Neal, S. Mittal, A. Baratin, V. Tantia, M. Scicluna, S. Lacoste-Julien, I. Mitliagkas // 2018. https://doi.org/10.48550/arXiv.1810.08591
  13. Неделько В. М. Некоторые вопросы оценивания качества методов построения решающих функций // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2013. Т. 24, № 3. С. 123–132.
  14. Nedel’ko V. Statistical fitting criterion on the basis of cross-validation estimation // Pattern Recognition and Image Analysis. 2018. Vol. 28. P. 510–515. http://dx.doi.org/10.1134/S1054661818030148
  15. Nedel’ko V. On decompositions of decision function quality measure // Известия Иркутского государственного университета. Серия Математика. 2020. Т. 33. С. 64–79. http://dx.doi.org/10.26516/1997-7670.2020.33.64
  16. Nedel’ko V. Tight risk bounds for histogram classifier // Proceedings of IFOST2016 11th International Forum on Strategic Technology. 2016. С. 267–271.
  17. Rachakonda A. R., Bhatnagar A. Aratio: Extending area under the roc curve for probabilistic labels // Pattern Recognition Letters. 2021. Vol. 150. P. 265–271. http://dx.doi.org/https://doi.org/10.1016/j.patrec.2021.06.023
  18. Rudakov K. Mathematical Foundations for Processing High Data Volume // Machine Learning and Artificial Intelligence, Pattern Recognit. Image Anal. 2019. Vol. 29. P. 339–343. http://dx.doi.org/10.1134/S1054661819030192
  19. Stuart G., Bienenstock E., Doursat R. Neural networks and the bias/variance dilemma // Neural Computation. 1992. Vol. 4, N 1. P. 1–58. http://dx.doi.org/10.1162/neco.1992.4.1.1
  20. Rethinking bias-variance trade-off for generalization of neural networks / Z. Yang, Y. Yu, C. You, J. Steinhardt, Y. Ma // International Conference on Machine Learning. 2020. С. 10767–10777.

Полная версия (english)