Series and Convergence — Ряды и сходимость

Когда бесконечная сумма имеет конечное значение и с какой скоростью алгоритм приближается к ответу.

k = 0 \sum \infty γ^{k} = \frac{1}{1 - γ}, ∣ γ ∣ < 1

Обозначения

$γ$ коэффициент, управляющий вкладом дальних членов
$k$ индекс слагаемого в сумме или ряде
$\sum$ суммирование по всем перечисленным элементам

Ключевые тезисы

Геометрический ряд объясняет, почему дисконтированная награда в RL конечна при $γ < 1$ .
Скорость сходимости бывает линейной, сверхлинейной и квадратичной — от неё зависит число итераций.
Экспоненциальное скользящее среднее (Adam, momentum) — это тот же геометрический ряд с весами.

Подробный разбор

2 подтем — раскройте любую, чтобы увидеть объяснение, формулы, примеры и интерактивные графики.

Геометрический ряд в ML

Одна формула, три применения.

k = 0 \sum \infty γ^{k} = \frac{1}{1 - γ}

Обозначения

$γ$ коэффициент, управляющий вкладом дальних членов
$k$ индекс слагаемого в сумме или ряде
$\sum$ суммирование по всем перечисленным элементам

RL: дисконтированная награда конечна, а «эффективный горизонт» примерно $1/ (1 - γ)$ .
Momentum: экспоненциальное среднее с $β = 0.9$ эквивалентно усреднению примерно по 10 последним градиентам.
EMA-метрики в мониторинге: тот же ряд задаёт длину окна.

Скорости сходимости

Сколько итераций нужно до нужной точности.

Скорость	Поведение ошибки	Пример
сублинейная	$O (1/ k)$	SGD на выпуклой задаче
линейная	$O (ρ^{k})$ , $ρ < 1$	GD на сильно выпуклой
квадратичная	ошибка возводится в квадрат	метод Ньютона вблизи решения

На практике

Практический смысл: линейная сходимость означает фиксированное число итераций на каждый знак точности, сублинейная — рост числа итераций на порядок за знак.

Связанные темы

Аппарат анализа · Предельные теоремы

Limits and Continuity97%

Пределы и непрерывность · Математический анализ

Предел описывает, к чему стремится функция вблизи точки. На этом понятии держатся производная, интеграл и вся теория сходимости алгоритмов.

Derivative85%

Производная · Математический анализ

Скорость изменения функции: предел отношения приращения функции к приращению аргумента. Геометрически — наклон касательной.

Differentiation Rules85%

Правила дифференцирования · Математический анализ

Сумма, произведение, частное и композиция — четыре правила, которых достаточно, чтобы продифференцировать почти любую функцию потерь вручную.

Taylor Series85%

Ряд Тейлора · Математический анализ

Приближение функции многочленом по производным в точке. Инструмент, которым обосновывают почти все методы оптимизации.

Multivariable Calculus85%

Многомерный анализ · Математический анализ

Функции многих переменных: частные производные, градиент, производная по направлению и линии уровня.

Jacobian85%

Якобиан · Математический анализ

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

Lagrange Multipliers85%

Множители Лагранжа · Математический анализ

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

Convexity85%

Выпуклость · Математический анализ

Свойство функции, гарантирующее единственность минимума и сходимость градиентных методов.

Numerical Differentiation85%

Численное дифференцирование · Математический анализ

Приближение производной конечными разностями: медленно и неточно, но незаменимо для проверки аналитических градиентов.

Integral85%

Интеграл · Математический анализ

Определённый интеграл — площадь под кривой, неопределённый — обратная операция к дифференцированию. В ML интеграл почти всегда означает математическое ожидание.

Differential Equations85%

Дифференциальные уравнения · Математический анализ

Уравнения, связывающие функцию с её производными. Описывают динамику — от роста популяций до обратного процесса в диффузионных моделях.

Calculus85%

Математический анализ · Основы

Производные показывают, как изменится ошибка при малом изменении параметра. Именно это делает возможным градиентное обучение.

Gradient85%

Градиент · Математический справочник

Вектор частных производных, указывающий направление наибыстрейшего роста функции.

Hessian85%

Гессиан · Математический справочник

Матрица вторых производных, описывающая локальную кривизну функции.

Backpropagation85%

Обратное распространение ошибки · Глубокое обучение

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

Law of Large Numbers80%

Закон больших чисел · Теория вероятностей и распределения

Среднее по выборке сходится к математическому ожиданию при росте числа наблюдений.

Central Limit Theorem80%

Центральная предельная теорема · Теория вероятностей и распределения

Сумма большого числа независимых слагаемых со сравнимым вкладом распределена приближённо нормально.

Heavy Tails80%

Тяжёлые хвосты · Теория вероятностей и распределения

Распределения, у которых экстремальные значения не являются пренебрежимо редкими. Именно они ломают привычные оценки и метрики.

Confidence intervals80%

Доверительные интервалы · Оценка моделей

Показывают точность оценки метрики; одно число без интервала мало о чём говорит.

Bootstrap80%

Бутстрэп · Оценка моделей

Многократная выборка с возвращением: даёт распределение метрики и доверительные интервалы без предположений о нормальности.

Statistics80%

Статистика · Основы

Как от выборки перейти к выводам о генеральной совокупности: оценки, доверительные интервалы и проверка гипотез.