Ускоренный градиент Нестерова

Материал из MachineLearning.

(Различия между версиями)

Версия 10:23, 25 июня 2026

Статья написана с использованием LLM GPT-4o и проверена участником Arina Pakalova 14:23, 25 июня 2026 (MSD)

Генерация признаков (англ. feature generation, feature construction) — это процесс создания новых переменных на основе исходного признакового описания объектов с целью повышения информативности данных для последующего применения алгоритмов машинного обучения.

Генерация признаков является ключевым этапом конструирования признаков (feature engineering) и принципиально отличается от отбора признаков (feature selection). Если отбор подразумевает выбор оптимального подмножества из уже существующих переменных, то генерация заключается в расширении пространства признаков за счет явного или неявного вычисления новых характеристик^[1].

Формальное определение

Пусть задано исходное признаковое описание объекта $x \in \mathbb{R}^d$ . Генерация признаков представляет собой отображение: $\phi: \mathbb{R}^d \rightarrow \mathbb{R}^D$ , где $D > d$ . Новое описание объекта формируется как $\tilde{x} = \phi(x)$ . Целью данного преобразования является переход в такое пространство $\mathbb{R}^D$ , в котором обучающая выборка становится линейно разделимой или обладает более выраженной структурой, позволяющей построить модель с меньшей ошибкой обобщения^[1].

Основные методы генерации признаков

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

Базовые математические преобразования

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

Логарифмирование и степенные преобразования: применяются для изменения распределения признака (например, для приближения к нормальному распределению) и снижения влияния выбросов.
Дискретизация (биннинг): преобразование непрерывной переменной в категориальную путем разбиения области значений на интервалы.
Нормализация и стандартизация: хотя технически это преобразования масштаба, они создают новые представления признаков, необходимые для корректной работы метрических алгоритмов (например, метода k-ближайших соседей).

Признаки взаимодействия (Interaction features)

Создаются путем комбинирования двух или более исходных переменных для фиксации совместного влияния факторов на целевую переменную:

Мультипликативное взаимодействие: произведение признаков $x_i \cdot x_j$ . Классическим примером являются полиномиальные признаки, где формируются все возможные произведения исходных переменных до заданной степени. Это позволяет линейным моделям (таким как линейная регрессия или логистическая регрессия) аппроксимировать нелинейные зависимости^[1].
Аддитивное взаимодействие и отношения: суммы или частные от деления признаков (например, отношение площади комнаты к ее объему).

Специфические генераторы для структурированных данных

Временные ряды: генерация лаг-признаков (значений за предыдущие периоды), скользящих статистик (среднее значение, дисперсия, минимум/максимум в окне), признаков сезонности (день недели, месяц) и автокорреляционных функций.
Текстовые данные: применение подходов мешка слов (Bag-of-Words), вычисление TF-IDF характеристик, генерация n-грамм. Данные методы преобразуют неструктурированный текст в числовую матрицу «объект-признак».
Графовые данные: вычисление характеристик вершин и рёбер, таких как степень вершины, коэффициент кластеризации, меры центральности (например, PageRank), расстояния в графе.

Автоматическая генерация признаков

Вместо ручного конструирования применяются алгоритмические подходы:

Глубокое обучение (Deep Learning): скрытые слои искусственных нейронных сетей (например, сверточных сетей для изображений) выполняют иерархическую автоматическую генерацию признаков. Выходы предпоследнего слоя выступают в роли сгенерированных признаков для финального классификатора^[1].
Генетическое программирование (Genetic Programming): эволюционный поиск оптимальных математических формул для комбинации исходных признаков.
Синтез глубоких признаков (Deep Feature Synthesis): алгоритм, реализованный в библиотеке Featuretools, который автоматически применяет наборы примитивных трансформаций (aggregation, transform) к реляционным базам данных для генерации новых признаков.

Проблемы и ограничения

Применение генерации признаков сопряжено с рядом проблем:

Проклятие размерности: избыточная генерация признаков приводит к экспоненциальному росту размерности пространства. Это требует пропорционального роста объема обучающей выборки для сохранения плотности данных, иначе модель подвержена переобучению.
Мультиколлинеарность: создание производных признаков (например, суммы двух сильно скоррелированных признаков) часто приводит к высокой корреляции между предикторами. Это может вызвать числовую нестабильность при обучении линейных моделей без регуляризации.
Вычислительная сложность: хранение и обработка разреженных матриц огромной размерности (характерных для n-грамм или полиномиальных признаков высокой степени) требует значительных ресурсов оперативной памяти и процессорного времени.

Литература

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A3%D1%81%D0%BA%D0%BE%D1%80%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82_%D0%9D%D0%B5%D1%81%D1%82%D0%B5%D1%80%D0%BE%D0%B2%D0%B0»

@@ Строка 1: / Строка 1: @@
-{{well|Статья написана с использованием LLM и проверена участником [[Участник:Arina Pakalova|Arina Pakalova]] 13:11, 25 июня 2026 (MSD)}}
+{{well|Статья написана с использованием LLM '''GPT-4o''' и проверена участником [[Участник:Arina Pakalova|Arina Pakalova]] 14:23, 25 июня 2026 (MSD)}}
-'''Ускоренный градиент Нестерова''' (англ. ''Nesterov accelerated gradient'', NAG) — семейство оптимальных по порядку итеративных методов первого порядка для решения задач [[Выпуклая оптимизация|выпуклой оптимизации]]. Метод обеспечивает достижение нижней оценки сложности для класса гладких выпуклых задач, равной <tex>O(1/k^2)</tex>, где <tex>k</tex> — номер итерации.
-== Определение и актуальность в теории оптимизации ==
+'''Генерация признаков''' (англ. ''feature generation'', ''feature construction'') — это процесс создания новых переменных на основе исходного [[Признаковое описание|признакового описания]] объектов с целью повышения информативности данных для последующего применения алгоритмов [[Машинное обучение|машинного обучения]].
-В середине 1980-х годов Ю. Е. Нестеровым была доказана нижняя оценка скорости сходимости для класса гладких выпуклых задач минимизации, показывающая, что ни один метод первого порядка не может гарантировать скорость сходимости быстрее, чем <tex>O(1/k^2)</tex>. До этой работы стандартный [[Метод градиентного спуска|градиентный спуск]] обеспечивал лишь скорость <tex>O(1/k)</tex>.
-Ускоренный градиент Нестерова является первым алгоритмом, достигающим этой теоретической нижней границы, что делает его '''оптимальным''' в смысле теории вычислительной сложности черного ящика (first-order black-box optimization). В дальнейшем концепция «ускорения» была обобщена на широкий класс невыпуклых, вариационных и стохастических задач, став фундаментальным строительным блоком современных алгоритмов машинного обучения (например, алгоритма FISTA).
+Генерация признаков является ключевым этапом [[Конструирование признаков|конструирования признаков]] (feature engineering) и принципиально отличается от [[Отбор признаков|отбора признаков]] (feature selection). Если отбор подразумевает выбор оптимального подмножества из уже существующих переменных, то генерация заключается в расширении пространства признаков за счет явного или неявного вычисления новых характеристик<ref name="kuhn">Kuhn, M., & Johnson, K. (2019). ''Feature Engineering and Selection: A Practical Approach for Predictive Models''. CRC Press.</ref>.
-== Постановка задачи ==
+== Формальное определение ==
-Рассмотрим задачу безусловной минимизации:
-<tex>
-\min_{x \in \mathbb{R}^n} f(x),
-</tex>
-где целевая функция <tex>f: \mathbb{R}^n \to \mathbb{R}</tex> удовлетворяет следующим условиям:
-# '''[[Выпуклая функция|Выпуклость]]''': для любых <tex>x, y \in \mathbb{R}^n</tex> выполняется <tex>f(y) \ge f(x) + \langle \nabla f(x), y - x \rangle</tex>.
+Пусть задано исходное признаковое описание объекта <tex>x \in \mathbb{R}^d</tex>. Генерация признаков представляет собой отображение:
-# '''[[Условие Липшица|Гладкость]]''': градиент функции является [[Липшицева непрерывность|липшицевым]] с константой <tex>L > 0</tex>, то есть для любых <tex>x, y \in \mathbb{R}^n</tex>:
+<tex>\phi: \mathbb{R}^d \rightarrow \mathbb{R}^D</tex>,
-<tex>
+где <tex>D > d</tex>. Новое описание объекта формируется как <tex>\tilde{x} = \phi(x)</tex>. Целью данного преобразования является переход в такое пространство <tex>\mathbb{R}^D</tex>, в котором [[Обучающая выборка|обучающая выборка]] становится линейно разделимой или обладает более выраженной структурой, позволяющей построить модель с меньшей [[Ошибка обобщения|ошибкой обобщения]]<ref name="bishop">Bishop, C. M. (2006). ''Pattern Recognition and Machine Learning''. Springer.</ref>.
-\|\nabla f(x) - \nabla f(y)\| \le L \|x - y\|.
-</tex>
-Эквивалентное условие гладкости:
-<tex>
-f(y) \le f(x) + \langle \nabla f(x), y - x \rangle + \frac{L}{2} \|x - y\|^2.
-</tex>
-Пусть <tex>x^*</tex> — точка минимума функции <tex>f(x)</tex>, а <tex>f^* = f(x^*)</tex> — глобальное минимальное значение.
+== Основные методы генерации признаков ==
-== Описание метода ==
+Методы генерации классифицируются в зависимости от типа исходных данных и применяемых математических преобразований.
-Классический вариант метода (1983 г.) генерирует две последовательности: основную точку <tex>x_k</tex> и вспомогательную (экстраполированную) точку <tex>y_k</tex>.
-'''Алгоритм:'''
+=== Базовые математические преобразования ===
-* '''Инициализация:''' <tex>y_0 = x_0 \in \mathbb{R}^n</tex>.
+К данной группе относятся арифметические операции над скалярными признаками:
-* '''Итерация''' <tex>k = 0, 1, 2, \dots</tex>:
+* '''Логарифмирование и степенные преобразования:''' применяются для изменения распределения признака (например, для приближения к нормальному распределению) и снижения влияния выбросов.
-<tex>
+* '''Дискретизация (биннинг):''' преобразование непрерывной переменной в категориальную путем разбиения области значений на интервалы.
-\begin{cases}
+* '''Нормализация и стандартизация:''' хотя технически это преобразования масштаба, они создают новые представления признаков, необходимые для корректной работы метрических алгоритмов (например, [[Метод k-ближайших соседей|метода k-ближайших соседей]]).
-x_{k+1} = y_k - \frac{1}{L} \nabla f(y_k), \\
-y_{k+1} = x_{k+1} + \frac{k}{k+3} (x_{k+1} - x_k).
-\end{cases}
-</tex>
-В данном выражении коэффициент <tex>\frac{k}{k+3}</tex> является частным случаем последовательности <tex>\alpha_k = \frac{2}{k+3}</tex>. Существуют эквивалентные формы записи через трехточечный рекуррентный процесс, однако приведенная форма наиболее наглядно демонстрирует механизм «заглядывания вперед» (look-ahead), когда градиент вычисляется не в текущей аппроксимации <tex>x_k</tex>, а в экстраполированной точке <tex>y_k</tex>.
-== Теоретические свойства и скорость сходимости ==
+=== Признаки взаимодействия (Interaction features) ===
+Создаются путем комбинирования двух или более исходных переменных для фиксации совместного влияния факторов на [[Целевая переменная|целевую переменную]]:
+* '''Мультипликативное взаимодействие:''' произведение признаков <tex>x_i \cdot x_j</tex>. Классическим примером являются [[Полиномиальные признаки|полиномиальные признаки]], где формируются все возможные произведения исходных переменных до заданной степени. Это позволяет линейным моделям (таким как [[Линейная регрессия|линейная регрессия]] или [[Логистическая регрессия|логистическая регрессия]]) аппроксимировать нелинейные зависимости<ref name="hastie">Hastie, T., Tibshirani, R., & Friedman, J. (2009). ''The Elements of Statistical Learning'' (2nd ed.). Springer.</ref>.
+* '''Аддитивное взаимодействие и отношения:''' суммы или частные от деления признаков (например, отношение площади комнаты к ее объему).
-Основной теоретический результат для метода формулируется с помощью техники '''оценивающих последовательностей''' (estimate sequences).
+=== Специфические генераторы для структурированных данных ===
+* '''Временные ряды:''' генерация лаг-признаков (значений за предыдущие периоды), скользящих статистик (среднее значение, дисперсия, минимум/максимум в окне), признаков сезонности (день недели, месяц) и автокорреляционных функций.
+* '''Текстовые данные:''' применение подходов [[Мешок слов|мешка слов]] (Bag-of-Words), вычисление [[TF-IDF|TF-IDF]] характеристик, генерация n-грамм. Данные методы преобразуют неструктурированный текст в числовую матрицу «объект-признак».
+* '''Графовые данные:''' вычисление характеристик вершин и рёбер, таких как степень вершины, [[Коэффициент кластеризации|коэффициент кластеризации]], меры центральности (например, PageRank), расстояния в графе.
-'''Определение.''' Последовательность функций <tex>\phi_k: \mathbb{R}^n \to \mathbb{R}</tex> называется оценивающей последовательностью для функции <tex>f</tex>, если выполняются два условия:
+=== Автоматическая генерация признаков ===
-# <tex>\phi_k(x) \le f(x)</tex> для всех <tex>x \in \mathbb{R}^n</tex> и всех <tex>k \ge 0</tex>.
+Вместо ручного конструирования применяются алгоритмические подходы:
-# Существует такая последовательность <tex>\{y_k\}</tex>, что <tex>f(y_k) \le \phi_k(x^*)</tex> для всех <tex>k \ge 0</tex>.
+* '''Глубокое обучение (Deep Learning):''' скрытые слои [[Искусственная нейронная сеть|искусственных нейронных сетей]] (например, [[Сверточная нейронная сеть|сверточных сетей]] для изображений) выполняют иерархическую автоматическую генерацию признаков. Выходы предпоследнего слоя выступают в роли сгенерированных признаков для финального классификатора<ref name="bishop"/>.
+* '''Генетическое программирование (Genetic Programming):''' эволюционный поиск оптимальных математических формул для комбинации исходных признаков.
+* '''Синтез глубоких признаков (Deep Feature Synthesis):''' алгоритм, реализованный в библиотеке Featuretools, который автоматически применяет наборы примитивных трансформаций (aggregation, transform) к реляционным базам данных для генерации новых признаков.
-=== Теорема (О скорости сходимости для гладких выпуклых функций) ===
+== Проблемы и ограничения ==
-Пусть функция <tex>f</tex> выпукла и имеет липшицев градиент с константой <tex>L</tex>. Тогда для последовательности <tex>\{y_k\}</tex>, генерируемой ускоренным градиентом Нестерова, выполняется:
-<tex>
-f(y_k) - f^* \le \frac{2L \|x_0 - x^*\|^2}{(k+1)^2}.
-</tex>
-'''Доказательство.'''
+Применение генерации признаков сопряжено с рядом проблем:
-Рассмотрим оценивающую последовательность вида:
+* '''[[Проклятие размерности|Проклятие размерности]]:''' избыточная генерация признаков приводит к экспоненциальному росту размерности пространства. Это требует пропорционального роста объема обучающей выборки для сохранения плотности данных, иначе модель подвержена [[Переобучение|переобучению]].
-<tex>
+* '''Мультиколлинеарность:''' создание производных признаков (например, суммы двух сильно скоррелированных признаков) часто приводит к высокой корреляции между предикторами. Это может вызвать числовую нестабильность при обучении линейных моделей без регуляризации.
-\phi_{k+1}(x) = (1 - \alpha_{k+1})\phi_k(x) + \alpha_{k+1} \left[ f(x_{k+1}) + \langle \nabla f(x_{k+1}), x - x_{k+1} \rangle + \frac{L}{2}\|x - x_{k+1}\|^2 \right],
+* '''Вычислительная сложность:''' хранение и обработка разреженных матриц огромной размерности (характерных для n-грамм или полиномиальных признаков высокой степени) требует значительных ресурсов оперативной памяти и процессорного времени.
-</tex>
-где <tex>\alpha_0 = 1</tex> и <tex>\alpha_{k+1} = \frac{2}{k+3}</tex>.
-В качестве начальной функции выберем <tex>\phi_0(x) = f(x_0) + \langle \nabla f(x_0), x - x_0 \rangle + \frac{L}{2}\|x - x_0\|^2</tex>.
-Утверждение 1: <tex>\phi_k(x) \le f(x)</tex> для всех <tex>x</tex>. Докажем по индукции.
-* База: <tex>\phi_0(x)</tex> является глобальной верхней оценкой для <tex>f(x)</tex> в силу условия гладкости.
-* Шаг индукции: Пусть <tex>\phi_k(x) \le f(x)</tex>. По условию гладкости, выражение в квадратных скобках также является верхней оценкой <tex>f(x)</tex>. Так как <tex>(1-\alpha_{k+1}) \ge 0</tex> и <tex>\alpha_{k+1} \ge 0</tex>, их выпуклая комбинация <tex>\phi_{k+1}(x)</tex> также не превышает <tex>f(x)</tex>.
-Утверждение 2: Выполнение условия <tex>f(y_k) \le \phi_k(x^*)</tex>.
-Найдем минимум правой части выражения для <tex>\phi_{k+1}(x)</tex>. Точка минимума квадратичной функции в скобках есть <tex>x_{k+1}</tex>. Значение в этой точке равно <tex>f(x_{k+1})</tex>. Следовательно, минимальное значение <tex>\phi_{k+1}(x)</tex> достигается в точке:
-<tex>
-y_{k+1} = \arg\min_{x} \phi_{k+1}(x) = (1-\alpha_{k+1})y_k + \alpha_{k+1} x_{k+1}.
-</tex>
-Подставляя <tex>x_{k+1} = y_k - \frac{1}{L}\nabla f(y_k)</tex> и выражение для <tex>\alpha_{k+1}</tex>, после алгебраических преобразований получаем рекуррентное соотношение <tex>y_{k+1} = x_{k+1} + \frac{k}{k+3}(x_{k+1} - x_k)</tex>, что в точности совпадает с алгоритмом.
-Оценим значение:
-<tex>
-\phi_{k+1}(y_{k+1}) = (1-\alpha_{k+1})\phi_k(y_{k+1}) + \alpha_{k+1} f(x_{k+1}) \le (1-\alpha_{k+1})\phi_k(x^*) + \alpha_{k+1} \left[ f(y_k) - \frac{1}{2L}\|\nabla f(y_k)\|^2 \right].
-</tex>
-Используя предположение индукции <tex>f(y_k) \le \phi_k(x^*)</tex> и неравенство Коши-Буняковского-Шварца для градиента, можно показать, что <tex>\phi_{k+1}(y_{k+1}) \le \phi_k(x^*) - \frac{\alpha_{k+1}}{2L}\|\nabla f(y_k)\|^2 \le \phi_k(x^*)</tex>. Отсюда <tex>f(y_{k+1}) \le \phi_{k+1}(x^*)</tex>.
-Утверждение 3: Оценка скорости.
-Введем вспомогательную последовательность <tex>A_k = \alpha_k \prod_{i=1}^{k-1} (1-\alpha_i)</tex>. Можно показать, что <tex>A_k = \frac{2}{(k+1)(k+2)}</tex>.
-Из разложения оценивающей последовательности в точке <tex>x^*</tex> следует:
-<tex>
-A_{k+1} (f(y_{k+1}) - f^*) \le \phi_0(x^*) - f^* \le \frac{L}{2}\|x_0 - x^*\|^2.
-</tex>
-Подставляя явный вид <tex>A_{k+1}</tex>, получаем искомую оценку <tex>f(y_k) - f^* \le \frac{2L \|x_0 - x^*\|^2}{(k+1)^2}</tex>. <tex>\blacksquare</tex>
-=== Теорема (О скорости сходимости для сильно выпуклых функций) ===
-Если функция <tex>f</tex> является [[Сильно выпуклая функция|сильно выпуклой]] с параметром <tex>\mu > 0</tex>, то метод модифицируется путем замены коэффициента экстраполяции на константу:
-<tex>
-\beta = \frac{\sqrt{L} - \sqrt{\mu}}{\sqrt{L} + \sqrt{\mu}}.
-</tex>
-Тогда скорость сходимости становится линейной:
-<tex>
-f(y_k) - f^* \le \left( \frac{\sqrt{L} - \sqrt{\mu}}{\sqrt{L} + \sqrt{\mu}} \right)^{2k} (f(y_0) - f^*).
-</tex>
-=== Свойства метода ===
-# '''Оптимальность''': Метод достигает теоретической нижней границы <tex>O(1/k^2)</tex> для класса гладких выпуклых задач. Изменение константы шага или коэффициента экстраполяции не может улучшить асимптотику по порядку.
-# '''Немонотонность''': В отличие от классического градиентного спуска, последовательность значений целевой функции <tex>\{f(y_k)\}</tex> не является монотонно убывающей. Допускаются локальные возрастания функции на отдельных итерациях.
-# '''Чувствительность к шуму''': Метод критически зависит от точности вычисления градиента. При добавлении стохастического шума (в SGD) ускорение может быть утрачено без применения специальных техник стабилизации (например, variance reduction).
-# '''Зависимость от константы Липшица''': Практическое применение метода требует знания или оценки константы <tex>L</tex>. Слишком завышенная оценка приводит к замедлению сходимости, заниженная — к расходимости алгоритма.
 == Литература ==
-# Нестеров Ю. Е. Метод решения задачи выпуклого программирования со скоростью сходимости <tex>O(1/k^2)</tex> // Доклады Академии Наук. — 1983. — Т. 269, № 3. — С. 543–547.
+<references />
-# Nesterov Y. Introductory Lectures on Convex Optimization: A Basic Course. — Springer Science & Business Media, 2004. — (См. Главу 2).
-# Beck A., Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems // SIAM Journal on Imaging Sciences. — 2009. — Vol. 2, no. 1. — P. 183–202. (Описание алгоритма FISTA как частного случая).
-# Bubeck S. Convex Optimization: Algorithms and Complexity. // Foundations and Trends in Machine Learning. — 2015. — Vol. 8, no. 11-12. — P. 231–357.
-== См. также ==
-* [[Метод инерции Поляка]]
-* [[Диагональный метод Левенберга-Марквардта]]
-* [[Метод наискорейшего спуска]]
-* [http://www.machinelearning.ru/wiki/images/3/34/Rodomanov-fast-gradient-methods.pdf Быстрый градиентный метод]
-* [http://www.machinelearning.ru/wiki/images/0/03/Rodomanov_FGM.pdf Анализ быстрого градиентного метода нестерова для задач машинного обучения с L1-регуляризацией]
-* [[Метод сопряжённых градиентов]]