Александр Николаевич Тырсин
620002, г. Екатеринбург, ул. Мира, 19;
454080, г. Челябинск, пр. Ленина, 76
Alexander N. Tyrsin
19, ul. Mira, Yekaterinburg, 620002;
76, prosp. Lenina, Chelyabinsk, 454080
Рассмотрена задача оценивания линейных регрессионных уравнений методом наименьших модулей. Точные методы его реализации значительно проигрывают по быстродействию методу наименьших квадратов. Наиболее быстрый алгоритм, основанный на покоординатном спуске по узловым прямым, имеет вычислительную сложность, пропорциональную квадрату числа наблюдений, что ограничивает практическое применение в задачах мониторинга и диагностики. Цель работы — описание более быстрого варианта реализации спуска по узловым прямым, а также оценка его быстродействия. Снижение вычислительных затрат достигнуто за счет того, что вместо вычисления значений целевой функции в узловых точках находят ее производную в окрестности этих точек по направлению узловой прямой. Приведена оценка вычислительной эффективности градиентного спуска по узловым прямым. Для типового компьютера проведен сравнительный анализ среднего времени вычислений для различных алгоритмов. Приведен простой пример, иллюстрирующий реализацию градиентного спуска. Наряду со снижением вычислительных затрат устранена возможность накопления вычислительных погрешностей при определении значений целевой функции для больших выборок. Кроме этого, градиентный спуск достаточно просто реализуется. Это позволяет использовать метод наименьших модулей как альтернативу методу наименьших квадратов в различных практических приложениях.
A problem of estimating linear regression equations by the least absolute deviations method is considered. The exact methods of implementation of the method are significantly inferior in performance to the least square method. The fastest algorithm based on coordinate descent along nodal straight lines has a computational complexity proportional to the square of the number of observations, which limits the practical application of the method to monitoring and diagnostic tasks. The goal of the study is to describe a faster version of the descent along the nodal straight lines, as well as to evaluate the performance. Reduction of the computational costs is achieved due to the fact that instead of calculating the values of the objective function at nodal points, we find the derivative of the objective function in the vicinity of these points along the nodal line. The computational efficiency of gradient descent along nodal straight lines is estimated. For a typical computer, a comparative analysis of the average calculation time for various algorithms of descent along nodal straight lines is performed. A simple example is given to illustrate the implementation of a gradient descent procedure. Along with reduction of the computational costs, we also eliminated the possibility of accumulating computational errors when determining the values of the objective function for large samples. Moreover, gradient descent is quite simple for implementation. This makes it possible to use the method of least absolute deviations as an alternative to the least square method in various practical applications.
The authors declare that there are no conflicts of interest present.