Модифицированный алгоритм градиентного спуска по узловым прямым в задаче регрессионного анализа

Рассмотрены вопросы создания вычислительно эффективных алгоритмов реализации метода наименьших модулей для оценивания регрессионных зависимостей. Цель работы — повышение быстродействия градиентного спуска по узловым прямым за счет учета геометрии целевой функции вблизи минимума, а также его сравнительный анализ с алгоритмом проектирования градиента. Предложен модифицированный алгоритм градиентного спуска для регрессионного оценивания методом наименьших модулей. Эффективность достигнута за счет исключения вычислений значений целевой функции в минимумах узловых прямых и определения улучшенного начального приближения на части выборки. В результате удалось уменьшить зависимость времени вычислений от объема выборки и расширить область использования метода наименьших модулей. Алгоритм проектирования градиента для построения линейных регрессионных зависимостей не гарантирует нахождение точного решения и значительно проигрывает в быстродействии алгоритмам спуска по узловым прямым.

1. Вероятность и математическая статистика: Энциклопедия / Гл. ред. Ю. В. Прохоров. — М.: Большая Российская энциклопедия, 1999. — 910 с.

2. Акимов П. А., Матасов А. И. Итерационный алгоритм для l1-аппроксимации в динамических задачах оценивания / Автоматика и телемеханика. 2015. № 5. С. 7 – 26.

3. Darlington R. B., Hayes A. F. Regression Analysis and Linear Models. Concepts, Applications, and Implementation. — New York – London: The Guilford Press, 2017. — 661 p.

4. Christensen R. Analysis of Variance, Design, and Regression Linear Modeling for Unbalanced Data. 2nd ed. — CRC Press, 2016. — 603 p.

5. Мудров В. И., Кушко В. Л. Методы обработки измерений. Квазиправдоподобные оценки. — М.: Радио и связь, 1983. — 304 с.

6. Орлов А. И. Многообразие моделей регрессионного анализа (обобщающая статья) / Заводская лаборатория. Диагностика материалов. 2018. Т. 84. № 5. С. 63 – 73. DOI: 10.26896/1028-6861-2018-84-5-63-73

7. Нелюбин А. П., Подиновский В. В. Аппроксимация таблично заданных функций: многокритериальный подход / Журнал вычислительной математики и математической физики. 2023. Т. 63. № 5. С. 717 – 730. DOI: 10.31857/S0044466923050174

8. Sheynin O. B. R. J. Boscovich’s work on probability / Archive for History of Exact Sciences. 1973. Vol. 9. Nos. 4 – 5. P. 306 – 324. DOI: 10.1007/BF00348366

9. Laplace P. S. Sur Quelques du Systeme du Monde. Memories de l’Academie Royale des Science de Paris, 1789. — Paris: Gauthier-Villars, 1895.

10. Stigler S. M. Studies in the History of Probability and Statistics. XXXII: Laplace, Fisher and the Discovery of the Concept of Sufficiency / Biometrika. 1973. Vol. 60. No. 3. P. 439 – 445. DOI: 10.1093/biomet/60.3.439

11. Basset G., Koenker R. Asymptotic Theory of Least Absolute Error Regression / J. Am. Statist. Assoc. 1978. Vol. 73. No. 363. P. 618 – 622. DOI: 10.1080/01621459.1978.10480065

12. Болдин М. В., Симонова Г. И., Тюрин Ю. Н. Знаковый статистический анализ линейных моделей. — М.: Наука; Физматлит, 1997. — 288 с.

13. Тырсин А. Н., Азарян А. А. Точное оценивание линейных регрессионных моделей методом наименьших модулей на основе спуска по узловым прямым / Вестник ЮУрГУ. Серия «Математика. Механика. Физика». 2018. Т. 10. № 2. С. 47 – 56. DOI: 10.14529/mmph180205

14. Тырсин А. Н. Алгоритмы спуска по узловым прямым в задаче оценивания регрессионных уравнений методом наименьших модулей / Заводская лаборатория. Диагностика материалов. 2021. Т. 87. № 5. С. 68 – 75. DOI: 10.26896/1028-6861-2021-87-5-68-75

15. Narula S. C., Wellington J. F. Algorithm AS108: Multiple linear regression with minimum sum of absolute errors / Appl. Statistics. 1977. Vol. 26. P. 106 – 111.

16. Armstrong R. D., Kung D. S. Algorithm AS132: Least absolute value estimates for a simple linear regression problem / Appl. Statistics. 1978. Vol. 27. P. 363 – 366.

17. Панюков А. В., Мезал Я. А. Параметрическая идентификация квазилинейного разностного уравнения / Вестник Южно-Уральского государственного университета. Серия: Математика. Механика. Физика. 2019. Т. 11. № 4. С. 32 – 38. DOI: 10.14529/mmph190404

18. Мезал Я. А. Квазилинейный анализ дискретных моделей нелинейной динамики (временных рядов): дис. ... канд. физ.-мат. наук. — Челябинск, 2020. — 134 с.

19. Тырсин А. Н., Голованов О. А. Спуск по узловым прямым и симплекс-алгоритм — два варианта регрессионного анализа на основе метода наименьших модулей / Заводская лаборатория. Диагностика материалов. 2024. Т. 90. № 5. С. 79 – 87. DOI: 10.26896/1028-6861-2024-90-5-79-87

20. Rosen J. B. The gradient projection method for nonlinear programming. Part 1: Linear constraints / J. Soc. Industr. Appl. Math. 1960. Vol. 8. No. 1. P. 181 – 217. DOI: 10.1137/0108011

21. The travelling salesman problem: a guided tour of combinatorial optimization / E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys, Eds. — J. Wiley & Sons, 1985. — 465 p.

22. Мину М. Математическое программирование. Теория и алгоритмы / Пер. с франц. — М.: Наука, 1990. — 488 с.

23. Barbu A., Zhu S.-C. Monte Carlo Methods. — Springer Nature Singapore Pte Ltd., 2020. — 422 p. DOI: 10.1007/978-981-13-2971-5_1

24. Тырсин А. Н. Метод подбора наилучшего закона распределения непрерывной случайной величины на основе обратного отображения / Вестник ЮУрГУ. Серия «Математика. Механика. Физика». 2017. Т. 9. № 1. С. 31 – 38. DOI: 10.14529/mmph170104