Спуск по узловым прямым и симплекс-алгоритм — два варианта регрессионного анализа на основе метода наименьших модулей

Проведен сравнительный анализ вычислительной сложности точных алгоритмов оценивания линейных регрессионных уравнений методом наименьших модулей. Цель работы — сравнение вычислительной эффективности точных алгоритмов спуска по узловым прямым и алгоритмов, основанных на решении задачи линейного программирования. Для этого рассмотрены алгоритм градиентного спуска по узловым прямым и алгоритмы решения эквивалентной прямой и двойственной задач линейного программирования с использованием симплекс-метода. Выполнена оценка вычислительной сложности алгоритмов реализации метода наименьших модулей с помощью решения прямой и двойственной задач линейного программирования. Также с помощью метода статистических испытаний Монте-Карло проведено сравнение среднего времени определения коэффициентов регрессии с помощью решения прямой и двойственной задач линейного программирования со средним временем градиентного спуска по узловым прямым. Установлено, что оба варианта значительно уступают градиентному спуску по узловым прямым как в плане вычислительной сложности алгоритмов, так и по времени вычисления. При этом выигрыш алгоритма спуска по узловым прямым растет с увеличением объема выборки, достигая сотни и более раз.

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

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

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

4. Basset G., Koenker R. Asymptotic theory of least absolute error regression / Journal of the American Statistical Association. 1978. Vol. 73. N 363. P. 618 – 622.

5. Birkes D., Dodge Y. Alternative Methods of Regression. — John Wiley & Sons, 1993. — 239 p.

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

7. Wei Xue, Wensheng Zhang, Gaohang Yu. Least absolute deviations learning of multiple tasks / Journal of Industrial & Management Optimization. 2018. N 14(2). P. 719 – 729. DOI: 10.3934/jimo.2017071

8. Вучков И., Бояджиева Л., Солаков Е. Прикладной линейный регрессионный анализ / Пер. с болг. — М.: Финансы и статистика, 1987. — 239 с.

9. Авдюшев В. А., Мезенцева А. Д. Метод наименьших модулей и его эффективность при обработке измерений с ошибками различного распределения / Известия вузов. Физика. 2012. Т. 55. № 10-2. С. 68 – 76.

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

11. Bloomfield P., Steiger W. L. Least Absolute Deviations: Theory, Applications, and Algorithms. — Boston – Basel – Stuttgart: Birkhauser, 1983. — 349 p.

12. Азарян А. А. Быстрые алгоритмы моделирования многомерных линейных регрессионных зависимостей на основе метода наименьших модулей: дис. ... канд. физ.-мат. наук. — Екатеринбург, 2018.

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

14. Barrodale I., Roberts F. D. K. An improved algorithm for discrete L1 linear approximation / SIAM Journal on Numerical Analysis. 1973. Vol. 10. P. 839 – 848.

15. Narula S. C., Wellington J. F. Algorithm AS108: Multiple linear regression with minimum sum of absolute errors / Applied 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 / Applied Statistics. 1978. Vol. 27. P. 363 – 366.

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

18. Голованов О. А., Тырсин А. Н. Регрессионный анализ данных на основе метода наименьших модулей в динамических задачах оценивания / Заводская лаборатория. Диагностика материалов. 2023. Т. 89. № 5. С. 71 – 80. DOI: 10.26896/1028-6861-2023-89-5-71-80

19. Wesolowsky G. O. A new descent algorithm for the least absolute value regression problem / Communications in Statistics, Simulation and Computation. 1981. Vol. 10. N 5. P. 479 – 491. DOI: 10.1080/03610918108812224

20. Hawley R. W., Gallagher Jr. N. C. On Edgeworth’s method for minimum absolute error linear regression / IEEE Transactions on Signal Processing. 1994. Vol. 42. N 8. P. 2045 – 2054. DOI: 10.1109/78.301827

21. Тырсин А. Н., Максимов К. Е. Оценивание линейных регрессионных уравнений с помощью метода наименьших модулей / Заводская лаборатория. Диагностика материалов. 2012. Т. 78. № 7. С. 65 – 71.

22. Богданова Е. Л., Соловейчик К. А., Аркина К. Г. Оптимизация в проектном менеджменте. Линейное программирование. — СПб.: Университет ИТМО, 2017. — 165 с. https://books.ifmo.ru/file/pdf/2252.pdf

23. Tukey J. W. A Survey of Sampling from Contaminated Distribution / Contributions to Probability and Statistics. — Stanford: Stanford Univ. Press, 1960. P. 443 – 485.

24. Хьюбер П. Робастность в статистике / Пер. с англ. — М.: Мир, 1984. — 304 с.

25. Chow G. C. Tests of equality between sets of coefficients in two linear regressions / Econometrica. 1960. Vol. 28. N 3. P. 591 – 605. DOI: 10.2307/1910133