Алгоритмы спуска по узловым прямым в задаче оценивания регрессионных уравнений методом наименьших модулей

Аннотация

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