Англоязычная версия данной заметки доступна здесь https://alex-ber.medium.com/708d04754e9e.
См. также:
Часть 1: Метод Ньютона в R. От эвристики к формальной верификации (Kernel-Level)
Часть 1 Приложение А. Пространства $L_p$ (Under the Hood): От топологических хаков к квадратичной гладкости
Часть 1 Приложение B. Другой пример Loss function на примере кросс-энтропии
Часть 1 Приложение C. Анатомия квадратичной сходимости: Доказательство теоремы Канторовича в $R$
Часть 2: Метод Ньютона в $R^n$. От Гессиана к Аппаратным Лимитам
Часть 3: Метод Ньютона для Векторных полей. Матрица Якоби, Гато и Архитектура Backpropogation
Бонусная Часть 4: Метод Ньютона в бесконечномерных пространствах (Level 99)
Dual-Core подход и Эвристика (Запускаем Систему-1)
Всякий раз, когда перед нами стоит задача найти корень функции , мозг требует наглядности. Студенты, инженеры и дата-сайентисты обожают, когда сложные абстракции можно «потрогать». Это абсолютно нормально: чтобы погрузиться в алгоритм, нам сначала нужно запустить «Систему-1» — наше быстрое, ассоциативное и визуальное мышление.
Прежде чем закапываться в строгую математику (наш Kernel-level), давайте выведем метод Ньютона двумя максимально интуитивными — но, спойлер, математически нестрогими — путями.
Ниже есть продолжение.Путь первый: физический (Ньютон и кинематика)
Давайте представим простейшую физическую симуляцию. Пусть наша функция $f(x)$ описывает текущую координату летящего объекта, а переменная $x$ играет роль времени. У нас есть зафиксированное положение объекта в момент времени $x_{old}$, равное $f(x_{old})$.
Из школьного курса физики мы знаем, что производная координаты по времени — это мгновенная скорость. Значит, скорость нашего объекта в данный момент равна $v = f'(x_{old})$.
Как найти координату объекта спустя мгновение $\Delta x$? Берем классическую формулу пути для равномерного движения и делаем эвристическое допущение: на коротком отрезке времени наша скорость не успеет сильно измениться. Тогда:
$f(x_{new}) \approx f(x_{old}) + v \cdot \Delta x$
В чем заключается наша главная задача? Мы ищем корень — то есть хотим узнать, на сколько нужно "перемотать" время, чтобы объект оказался точно в нулевой координате. Значит, мы требуем, чтобы $f(x_{new}) = 0$. Подставляем этот ноль в наше уравнение и выражаем шаг $\Delta x$:
$0 \approx f(x_{old}) + v \cdot \Delta x$
$\Delta x = - \frac{f(x_{old})}{v}$
Вуаля! Мы вычислили, на сколько нужно сдвинуть время, чтобы с текущей скоростью $v$ приземлиться ровно в ноль. Теперь нам остается только сделать этот шаг от старой точки, чтобы получить новую:
$x_{new} = x_{old} + \Delta x = x_{old} - \frac{f(x_{old})}{f'(x_{old})}$
На языке алгоритмов мы привыкли обозначать текущий шаг как $x_k$, а следующий как $x_{k+1}$. Переписав формулу, мы получаем классический шаг метода Ньютона-Рафсона, который мы только что «изобрели», просто вспомнив формулу $S = v \cdot t$. Конечно, поскольку в реальности скорость функции меняется (у нее есть ускорение — вторая производная), за один шаг мы в идеальный ноль не попадем. Именно поэтому метод итеративный!
Путь второй: геометрический (касательная и метод Рафсона/Симпсона)
Если физика вас не убеждает, давайте включим пространственное мышление. Рисуем график функции $f(x)$. У нас есть текущая точка $(x_k, f(x_k))$. Кривая может быть сложной, изгибаться и вести себя непредсказуемо. Что делают инженеры, когда видят нелинейность? Они ее линеаризуют!
Заменим сложную кривую в нашей текущей точке на самую лучшую локальную прямую — её касательную. Давайте выведем её уравнение.
Любая прямая на плоскости полностью задается точкой, через которую она проходит, и её наклоном. Наша прямая гарантированно проходит через точку $(x_k, f(x_k))$. Ее наклон — это отношение изменения по вертикали к изменению по горизонтали ($\frac{\Delta y}{\Delta x}$). По геометрическому смыслу производной, этот наклон в точности равен $f'(x_k)$.
Теперь возьмем абсолютно любую точку $(x, y)$ на нашей будущей прямой. Наклон отрезка между нашей зафиксированной точкой и этой произвольной точкой должен равняться производной. Запишем это:
$\frac{y - f(x_k)}{x - x_k} = f'(x_k)$
Умножаем обе части на знаменатель, и перед нами возникает уравнение касательной:
$y - f(x_k) = f'(x_k)(x - x_k)$
Нас интересует, где эта упрощенная модель пересекает ось абсцисс. Приравниваем $y = 0$ и решаем уравнение относительно $x$ (нашего нового шага $x_{k+1}$):
$- f(x_k) = f'(x_k)(x_{k+1} - x_k)$
$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$
И снова мы приходим к той же самой формуле. Мы заменили сложную задачу (поиск корня кривой) на простую (поиск корня прямой), сместились, и готовы повторить этот процесс снова.
Философский мост: Вавилонский метод vs Греческий подход
Здесь стоит сделать важную остановку. На самом деле, то, что мы сейчас обсуждаем, отражает глобальный раскол в подходах к вычислениям, который дожил до эпохи Machine Learning.
Историки математики выделяют два фундаментальных паттерна: «вавилонский» и «греческий».
«Вавилонский метод» — это чистая эмпирика, data-driven подход. Древние вавилоняне не доказывали теорем. Они собирали таблицы данных, замечали закономерности и выводили эвристические правила (алгоритмы). В современном мире вавилонский подход — это парадигма Deep Learning. Мы берем «черный ящик», заливаем в него терабайты данных, масштабируем параметры, и система индуктивно подгоняет кривые, находя решение. Почему это работает? Вавилонянам (и часто ML-инженерам) это не так важно, главное — Loss падает.
«Греческий метод» — это царство дедукции и формальных моделей. Греки (Пифагор, Евклид, Архимед) сначала строили строгую абстрактную теорию. Пусть даже их модель мира была странной (вроде хрустальных сфер в космосе), но она была математически строгой, и из неё логически выводились все следствия. Именно так Эратосфен смог вычислить радиус Земли с помощью палки и тени.
Катарсис: чёрт из табакерки
А теперь давайте столкнем эти два мира лбами. Как древние вавилоняне (за 1500 лет до н.э.) вычисляли квадратные корни, например, $\sqrt{9801}$?
У них было простое эмпирическое правило-эвристика: возьми любую начальную догадку (допустим, $x_0 = 100$, так как мы понимаем, что $100^2 = 10000$, что очень близко к цели). Подели искомое число на эту догадку.
Тут возникает важный логический момент: если начальная догадка была больше настоящего корня, то результат деления будет меньше корня. А если догадка оказалась меньше корня, то результат деления будет больше. В любом случае настоящий корень всегда оказывается зажат где-то посередине между вашей догадкой и результатом деления!
Поэтому просто возьми среднее арифметическое между ними — это и будет новая, улучшенная догадка, которая гарантированно ближе к истине. Алгоритм вавилонян выглядел так:
$x_{k+1} = \frac{1}{2} \left( x_k + \frac{9801}{x_k} \right)$
Давайте сделаем первый шаг:
$x_1 = \frac{1}{2} \left( 100 + \frac{9801}{100} \right) = \frac{1}{2} \left( \frac{10000 + 9801}{100} \right) = \frac{19801}{200}$
Истинный корень из 9801 равен ровно 99. Всего за одну итерацию алгоритм, придуманный примерно в XVII в. до н.э., промахнулся мимо правильного ответа лишь на 5 тысячных (так как $\frac{19801}{200} = 99.005$)! Но давайте сделаем второй шаг, чтобы избежать округлений, подставим наше новое точное значение $x_1$ в виде обыкновенной дроби:
$x_2 = \frac{1}{2} \left( \frac{19801}{200} + \frac{9801}{\frac{19801}{200}} \right) = \frac{1}{2} \left( \frac{19801}{200} + \frac{9801 \cdot 200}{19801} \right) = \frac{1}{2} \left( \frac{19801}{200} + \frac{1960200}{19801} \right)$
Приводим дроби в скобках к общему знаменателю ($200 \cdot 19801 = 3960200$):
$x_2 = \frac{1}{2} \left( \frac{19801^2 + 1960200 \cdot 200}{3960200} \right) = \frac{1}{2} \left( \frac{392079601 + 392040000}{3960200} \right) = \frac{784119601}{7920400}$
А теперь самая магия. Если выделить из этой монструозной дроби целую часть, мы получим ровно $99 + \frac{1}{7920400}$. Алгоритм выдал феноменальную точность без единого округления!
Спустя всего две итерации мы получили точность до седьмого знака после запятой.
А теперь включим «греческую» строгость и применим метод Ньютона к задаче поиска корня. $\sqrt{9801}$ — это положительный корень функции $f(x) = x^2 - 9801 = 0$.
Её производная в нашей текущей точке: $f'(x_k) = 2x_k$. Подставляем в общую формулу шага Ньютона $\left( x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} \right)$:
$x_{k+1} = x_k - \frac{x_k^2 - 9801}{2x_k}$
Проведем вычисления. Сначала приводим $x_k$ к общему знаменателю $2x_k$:
$x_{k+1} = \frac{2x_k^2}{2x_k} - \frac{x_k^2 - 9801}{2x_k}$
Записываем всё под одну общую черту (минус перед второй дробью меняет знаки в числителе):
$x_{k+1} = \frac{2x_k^2 - (x_k^2 - 9801)}{2x_k} = \frac{2x_k^2 - x_k^2 + 9801}{2x_k} = \frac{x_k^2 + 9801}{2x_k}$
Теперь разобьем полученную дробь на две отдельные части и сократим первую из них:
$x_{k+1} = \frac{x_k^2}{2x_k} + \frac{9801}{2x_k} = \frac{x_k}{2} + \frac{9801}{2x_k}$
Наконец, выносим множитель $\frac{1}{2}$ за скобки из обоих слагаемых:
$x_{k+1} = \frac{1}{2} \left( x_k + \frac{9801}{x_k} \right)$
Бам! Формула метода Ньютона в точности схлопнулась в эмпирическое правило вавилонян! Строгая математическая модель, которую мы вывели через кинематику и касательные, веками молча пряталась под капотом древней эвристики.
Переключение в Систему-2
Наглядно? Абсолютно. Можно ли это закодить? Да, и оно будет работать. Но строго ли это? Нет. И кинематика, и визуализация касательных — это классическое «махание руками» (hand-waving).
Наша способность визуализировать геометрию сломается, как только мы перейдем в многомерные пространства нейросетей, где касательные превращаются в абстрактные гиперплоскости, а привычный угол наклона нарисовать невозможно. Физика работает только при условии, что «скорость не меняется», что локально и не дает гарантий безопасности алгоритма.
Нам нужен строгий математический фундамент. Эвристика закончилась — мы переходим в Систему-2 и начинаем писать Kernel-level код, опираясь на формальное разложение функции в ряд Тейлора.
Переосмысление производной: Линейный Патч (Linear Patch)
Смерть касательной
Итак, мы в Системе-2. Первое, что нам нужно сделать для написания надежного математического ядра (Kernel-level) — это отказаться от школьных картинок. Визуализация через касательные и углы наклона — это отличный стартовый костыль, но в мире Machine Learning он превращается в ловушку.
Современные нейросети оптимизируют функции потерь (Loss), которые зависят от миллионов или даже миллиардов параметров. Мы находимся в огромном пространстве $\mathbb{R}^{10^9}$. В таком пространстве касательная прямая мутирует в касательную гиперплоскость. Наше пространственное воображение больше не может строго обосновать и гарантировать правильность шага — хотя мы и продолжим использовать геометрические метафоры вроде «оврагов» или «седловых точек» для интуиции. Чтобы идти дальше, мы должны перевести геометрию на язык строгой алгебры.
Производная как Линейный Оператор
В школе мы говорили, что производная $f'(x_0)$ в точке — это число (тангенс угла наклона или мгновенная скорость). В высшей математике и архитектуре ML производная — это не число. Это Линейный Оператор.
Представьте, что у вас есть сложная, непредсказуемая, нелинейная функция на каком-то отрезке [a, b]. Мы находимся в точке $x_0$ и хотим сделать небольшой шаг $\Delta x$. Нам нужно узнать, как при этом изменится значение функции (то есть найти приращение $\Delta f$).
Производная $f'(x_0)$ — это лучший локальный «Линейный Патч» (Linear Patch) для нашей функции. В классической академической математике эту функцию-трансформер называют Дифференциалом. Она принимает на вход ваш вектор смещения $\Delta x$ и линейно трансформирует его в изменение функции $\Delta f$:
$\Delta f \approx f'(x_0) \cdot \Delta x$
Кстати, та самая школьная формула касательной — это и есть просто графическое отображение работы этого патча: $y = f(x_0) + f'(x_0)(x - x_0)$.
Суть линейного патча в его поразительной предсказуемости: если вы увеличите шаг $\Delta x$ в 2 раза, то прогнозируемое изменение функции $\Delta f$ тоже увеличится ровно в 2 раза. Это идеальный, надежный интерфейс внутри хаотичного нелинейного мира.
Единый интерфейс (API) для любого измерения
Вы можете спросить: зачем называть обычное умножение на число таким тяжеловесным термином как «Линейный Оператор»?
Ответ кроется в масштабируемости. Обычное число $f'(x_0)$ из одномерного пространства $\mathbb{R}^1$ можно рассматривать как самую маленькую в мире матрицу — матрицу размера $1 \times 1$.
Когда в следующих частях нашей серии мы начнем масштабировать алгоритм, наши смещения $\Delta x$ и изменения функции $\Delta f$ перестанут быть просто числами и станут многомерными векторами или тензорами. Но алгебраическая запись линейного патча $\Delta f \approx Operator \cdot \Delta x$ не изменится вообще. Закрытый интервал [а, b] превратится в любое компактное множество, а этот крошечный скалярный оператор бесшовно и автоматически эволюционирует:
- В вектор-строку Градиента, когда мы будем минимизировать многомерный Loss.
- В прямоугольную Матрицу Якоби, когда слои нашей нейросети начнут принимать векторы и возвращать другие векторы.
- И, наконец, в Производную Фреше (Level 99), когда мы выйдем в бесконечномерные пространства непрерывной памяти (Банаховы пространства). Этот же самый интерфейс позволит нам обучать непрерывные во времени нейросети (Neural ODE) и аппаратно «взламывать» уравнения нелинейной физики.
А когда линейности перестанет хватать и нам понадобится учесть кривизну пространства для точного снайперского шага, к нашему API органично добавится следующий этаж — «Квадратичный патч», где и появится знаменитая Матрица Гессе (Гессиан).
Интерфейс патча остается неизменным на любом уровне абстракции. Смерть школьной касательной открывает нам доступ к универсальному математическому API Вселенной.
Но у этого линейного патча прямо сейчас есть одна фундаментальная уязвимость — знак «приближенно равно» ($\approx$). Настало время с ней разобраться и перейти к инкапсуляции ошибки.
Инкапсуляция ошибки: о-малое и Формула Тейлора (API)
Линейный патч прекрасен, но в реальном нелинейном мире он всегда ошибается. Знак $\approx$ в формуле $\Delta f \approx f'(x_0) \Delta x$ — это бомба замедленного действия. Чтобы построить надежный алгоритм и гарантировать System Security, нам нужно строго описать и инкапсулировать эту ошибку. Нам нужны инструменты для работы с погрешностью.
Уровень абстракции 1 (High-Level API): Черный ящик $o(\Delta x)$
Первый способ работы с ошибкой — это спрятать её в «черный ящик». В математике этот паттерн проектирования называется «о-малое» от $\Delta x$, или $o(\Delta x)$. Мы переписываем наше приближение в виде точного равенства:
$\Delta f = f'(x_0) \Delta x + o(\Delta x)$
Что такое $o(\Delta x)$?
Примечание: Здесь было отступление для ML-инженеров, но оно у меня получилось длинное, поэтому я его вынес в две отдельные заметки "Часть 1 Приложение А. Пространства $L_p$ (Under the Hood): От топологических хаков к квадратичной гладкости" и "Часть 1 Приложение B. Другой пример Loss function на примере кросс-энтропия". Вы можете как прочитать их сейчас, так и прочитать после прочтения первой части.
И «о-малое» выступает как универсальный черный ящик, валидный для функции локальной ошибки абсолютно любой природы. У этого абстрактного интерфейса есть лишь один строгий контракт: по мере уменьшения шага $\Delta x$, ошибка убывает быстрее, чем сам шаг. На языке пределов это записывается так:
$\lim_{\Delta x \to 0} \frac{o(\Delta x)}{\Delta x} = 0$
Это отличный High-Level API. Он идеален для теоретических выкладок и асимптотики (когда шаг стремится к нулю). Но для реальной разработки и доказательства стабильности метода Ньютона он недостаточен. Нам нужно точно знать, насколько большой может быть ошибка при конкретном конечном шаге, а не в абстрактном пределе. Нам нужен доступ к исходному коду ошибки.
Уровень абстракции 2 (Low-Level API): Формула Тейлора
Чтобы заглянуть под капот ошибки, мы опускаемся на уровень ниже. Здесь нам на помощь приходит Формула Тейлора (в данном случае с остаточным членом в форме Лагранжа). По сути, Формула Тейлора — это конкретная, низкоуровневая «реализация» (implementation) нашего High-Level API применительно к итеративным методам.
Теоремы Лагранжа о конечных приращениях, которая оперирует только первой производной, нам уже не хватит. Первая производная описывает только наклон, а ошибка линейного патча возникает из-за того, что функция изгибается. Значит, нам нужна кривизна, за которую архитектурно отвечает вторая производная.
Классический матанализ любит раскладывать функции в бесконечный ряд Тейлора, но это требует идеальной гладкости (строгой аналитичности — способности функции идеально совпадать со своим бесконечным рядом, а не просто быть бесконечно дифференцируемой). В реальных алгоритмах нам не нужна бесконечность, да и архитектурные требования можно сильно смягчить. Нам достаточно, чтобы функция была всего лишь дважды дифференцируемой (с непрерывной второй производной). Этого минимума уже хватает, чтобы Формула Тейлора предоставила нам конечный, точный «исходный код» для вычисления значения функции в новой точке $x = x_k + \Delta x$ (то есть $\Delta x = x - x_k$):
$f(x) = f(x_k) + f'(x_k)\Delta x + \frac{1}{2}f''(\xi)\Delta x^2$
Давайте разберем этот код по частям:
- $f(x_k)$ — наша текущая позиция (база).
- $f'(x_k)\Delta x$ — работа нашего Линейного Патча (Дифференциала).
- $\frac{1}{2}f''(\xi)\Delta x^2$ — это и есть распакованная ошибка, наш квадратичный хвост.
Здесь $\xi$ — это какая-то промежуточная точка. В матанализе стандартное требование для таких теорем — функция должна быть непрерывна на замкнутом отрезке и дифференцируема на открытом. Поэтому наша точка $\xi$ всегда прячется где-то строго внутри открытого интервала $(x_k, x)$. И хотя мы не знаем её точного местоположения, это уже не важно.
Для строгой гарантии System Security мы рассматриваем весь наш рабочий замкнутый отрезок и просто берем максимально возможное значение модуля второй производной на нём (назовем эту константу максимальной кривизны $M$). Но имеем ли мы право утверждать, что этот максимум вообще существует?
Да! Здесь нас страхует знаменитая теорема Вейерштрасса для непрерывных функций: так как наша вторая производная непрерывна на замкнутом отрезке, она математически гарантированно достигает на нем своего максимального значения.
Замечание: теорема Вейерштрасса для непрерывных функций — это лишь проекция мощного закона из общей топологии. В оригинале он звучит так: непрерывная функция на компактном множестве всегда достигает своих экстремумов. Пока мы находимся в классических размерностях — в первых трех блоках нашей серии — действует теорема Гейне–Бореля: множество компактно тогда и только тогда, когда оно замкнуто и ограничено. Но будьте осторожны! В 4-й части, когда мы шагнем в бесконечномерные Банаховы пространства, ситуация изменится. Останется верно, что если множество компактно то оно замкнуто и ограничено, однако обратное утверждение, не верно в общем случае. Там замкнутости и ограниченности больше не хватит для компактности, топология покажет свои зубы, и нам потребуются куда более хитрые инструменты.
Взяв этот гарантированный максимум $M$, мы получаем железный «худший сценарий» (worst-case bound) — точную верхнюю границу ошибки, хуже которой ситуация точно не станет.
System Security: Теорема Канторовича как Статический Анализатор
Проблема: Уязвимость в коде
Итак, мы вывели алгоритм: $x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$. Посмотрите внимательно на эту формулу глазами программиста. Что вы видите? Правильно — потенциальный DivisionByZeroException.
Что произойдет, если производная $f'(x_k)$ окажется равна нулю (или очень близка к нему)? Знаменатель схлопнется, дробь станет гигантской, и наш следующий шаг выкинет нас далеко за пределы рабочей области. Алгоритм улетит в бесконечность. Даже если мы не делим на чистый ноль, слишком широкий шаг может вышвырнуть нас из так называемой «зоны притяжения» (basin of attraction) нашего корня. Эвристика без гарантий — это бомба в продакшене.
Теорема Канторовича: Строгая математическая формулировка
Теорема Канторовича: Пусть функция $f(x)$ непрерывна на замкнутом отрезке $D = [a, b]$ и дважды дифференцируема на интервале $(a, b)$. Пусть задана начальная точка $x_0 \in D$, для которой выполняются следующие условия:
- Начальный шаг ограничен: $|\Delta x_0| = \left| \frac{f(x_0)}{f'(x_0)} \right| \le \eta$
- Модуль обратной величины первой производной в начальной точке ограничен: $\left| \frac{1}{f'(x_0)} \right| \le \beta$. (Именно такая формулировка позволит нам в будущем бесшовно заменить число в знаменателе на норму обратной матрицы Якоби или Гессе в многомерном мире).
- Модуль второй производной (кривизна) ограничен сверху: $|f''(x)| \le M$ для всех $x \in D$
Если выполняется условие $h = M \cdot \eta \cdot \beta \le \frac{1}{2}$ и отрезок $\Omega = [x_0 - t^*, x_0 + t^*]$, где $t^* = \frac{1 - \sqrt{1 - 2h}}{h} \eta \le 2\eta$, целиком принадлежит $D$, то внутри окрестности $\Omega$ гарантированно существует корень $x^*$ уравнения $f(x) = 0$, и последовательность итераций метода Ньютона $x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$ безопасно сойдется к нему, не покидая $\Omega$. При этом сходимость обладает квадратичной скоростью при $h < 1/2$ (ошибка убывает пропорционально квадрату предыдущей) и может снижаться до линейной в граничном случае $h = 1/2$. Корень $x^*$ является единственным в пределах большей окрестности радиуса $t^{**} = \frac{1 + \sqrt{1 - 2h}}{h} \eta$ (при условии, что эта окрестность также лежит в $D$).
Интуиция: Теорема как статический анализатор (API Contracts)
В современной разработке для предотвращения катастроф во время выполнения используют статические анализаторы кода (вроде TypeScript, Rust compiler или линтеров). Они проверяют типы и контракты до запуска программы. В математике роль такого статического анализатора для метода Ньютона играет приведенная выше теорема (за работы в том числе в этой области Леонид Канторович позже получил Нобелевскую премию по экономике).
Чтобы «компиляция» прошла успешно, анализатор должен просто проверить три условия контракта. При этом анализатор работает «вслепую» относительно самого корня: он сопоставляет локальные данные только в одной стартовой точке $x_0$ (размер шага и наклон) с глобальным ограничением на кривизну ($M$) во всей зоне $D$.
Важнейший философский поинт теоремы Канторовича заключается в том, что это теорема существования. Анализатору не нужно знать, где находится корень и есть ли он вообще. Если начальные условия (шаг, наклон и кривизна) удовлетворяют контракту $h \le 1/2$, теорема математически гарантирует, что корень существует, и метод его обязательно найдет. Триггер $h \le 1/2$ просто говорит: «ваш стартовый шаг достаточно мал по сравнению с максимально возможной кривизной графика».
Правило $2\eta$ и SLA алгоритма. Теорема дает программистам блестящее инженерное «правило большого пальца»: истинный корень всегда лежит на расстоянии, не превышающем удвоенного первого шага ($t^* \le 2\eta$). Кроме того, анализатор прописывает жесткий SLA (Service Level Agreement): если запас прочности есть ($h < 1/2$), количество верных знаков ответа будет удваиваться на каждой итерации. И лишь в экстремальном краевом случае ($h = 1/2$) алгоритм деградирует до обычной линейной скорости.
Замечание про современный Deep Learning. В многомерном мире алгоритмы работают с системами уравнений: там вместо деления на производную используется обратная матрица Якоби, но общая логика сохраняется. Однако в мире современных нейросетей с миллиардами параметров, где функции потерь представляют собой дикие многомерные ландшафты, аналогов теореме Канторовича не найдено. У нас нет строгого математического «анализатора» для ChatGPT. Вместо формальной верификации ML-инженеры вынуждены опираться на эмпирические эвристики (градиентный клиппинг, адаптивный learning rate, оптимизаторы вроде Adam), инженерную интуицию и своего рода высокотехнологичное шаманство. Обучение современной нейросети — это прыжок в темноту с надеждой собрать парашют в полете.
Примечание: Доказательство теоремы Канторовича у меня получилось длинным, поэтому я его вынес в Часть 1 Приложение C. Анатомия квадратичной сходимости: Доказательство теоремы Канторовича в $R$
Пример: Зигзаг смерти и нарушение контрактов
Что бывает, если проигнорировать статический анализатор? Попробуем найти корень функции $f(x) = \arctan(x) = 0$. Очевидно, что истинный корень $x^* = 0$.
Производная арктангенса: $f'(x) = \frac{1}{1+x^2}$. Формула шага принимает вид: $x_{k+1} = x_k - (1+x_k^2)\arctan(x_k)$.
Если мы возьмем начальную точку $x_0 = 1.39$, метод стремительно сойдется к корню $x^* = 0$. Мы внутри безопасной зоны притяжения, условие Канторовича выполнено, маховик сходимости запущен, всё работает идеально.
Но стоит нам взять $x_0 = 1.40$, как происходит катастрофа. В этой точке график арктангенса уже начинает выполаживаться. Касательная становится слишком горизонтальной, производная падает (обратная величина $\beta$ становится слишком большой, а $h$ пробивает потолок в $1/2$). Триггер ломается на первом же шаге. Шаг становится больше, чем расстояние до корня: алгоритм перепрыгивает ноль и приземляется в точке с противоположным знаком, но еще дальше от нуля. На следующей итерации шаг будет еще шире.
Начинается расходимость, известная как «зигзаг смерти». Алгоритм будет бесконечно метаться влево-вправо, улетая в бесконечность. Это визуально и болезненно доказывает: любая красивая эвристика без проверки формальных контрактов — небезопасна.
Как современная ML-индустрия «чинит» эту проблему? Простейший способ предотвратить улет в бесконечность — искусственно ограничить длину шага, добавив множитель (Learning Rate, $\alpha \le 1$). Это гасит размах маятника и открывает дверь к целой вселенной квазиньютоновских методов и адаптивных оптимизаторов.
Undefined Behavior и Комплексная плоскость (Отключаем линтер)
В Приложении C (куда мы вынесли всю тяжелую математику) мы доказали работоспособность нашего статического анализатора для классической прямой действительных чисел $\mathbb{R}$. Там всё прозрачно: числа выстроены в ряд, работают операции «больше/меньше», а значит — работают графики, интегралы и дискриминанты.
Но что будет, если мы покинем эту уютную, математически доказанную песочницу? В комплексной плоскости $\mathbb{C}$ мы выходим в открытое 2D-поле, где направления спутались, и старая логика компараторов больше не применима. Давайте сделаем банальный каст типов от вещественных чисел (Float) к комплексным (Complex) и просто запустим нашу базовую формулу Ньютона z -= f(z)/f'(z) «на авось», полностью отключив линтер Канторовича. Мы вступаем в зону детерминированного хаоса, который для нашего статического анализатора выглядит как чистое Undefined Behavior.
Возьмем простейшее уравнение: $z^3 - 1 = 0$. В комплексной плоскости $\mathbb{C}$ у него ровно три корня (один вещественный $z=1$ и два комплексных). Представьте, что это три «сервера», к одному из которых должен подключиться наш алгоритм.
Интуиция Системы-1 подсказывает нам, что плоскость должна поделиться на три ровные, аккуратные зоны — бассейны притяжения (basins of attraction). Если мы стартуем близко к одному из корней, так оно и происходит — эвристика срабатывает, и метод мгновенно паркуется к ближайшему серверу. Но давайте раскрасим каждый стартовый пиксель $z_0$ на экране в цвет того корня, к которому в итоге пришел алгоритм, и посмотрим на границы этих зон.
Они не прямые. Они образуют Фрактал Ньютона — бесконечно сложную, психоделическую структуру, где цвета перемешаны в неразрешимую пыль. Если вы возьмете любую, даже микроскопическую область на границе этих цветов и увеличите её в миллиард раз, вы снова увидите все три цвета, переплетенные между собой.
В этой фрактальной зоне возникает математический аналог лавинного нарастания ошибки. Смещение вашей начальной догадки $z_0$ буквально на одну миллионную долю пикселя может радикально изменить итоговый корень. Детерминированный алгоритм становится вычислительно непредсказуемым. Вы никогда не знаете заранее, на каком «сервере» закончится вычисление.
Этот фрактал — это не просто красивая картинка. Это наглядный визуальный краш-дамп при жесточайшем стресс-тесте архитектуры итеративных методов. Он доказывает инженерам: «Вот как выглядит ваш продакшен, если вы просто берете красивую эвристическую формулу, выходите за пределы доказанной математической базы и надеетесь, что оно как-нибудь само сойдется». Чувствительность к начальным условиям превращает вычисления в хаос.
В будущих частях нашей серии мы увидим, как этот хаос масштабируется. Нам придется заново конструировать статические анализаторы для многомерных пространств $\mathbb{R}^n$ и абстрактных Банаховых миров. Ведь фракталы Ньютона в комплексной плоскости — это лишь 2D-превью того кошмара, который происходит в диких многомерных ландшафтах нейросетей ($\mathbb{R}^{10^9}$), где миллионы весов пытаются нащупать минимум Loss-функции.
Заключение Части 1 и мост в Machine Learning
Резюме: Kernel-level math
Давайте посмотрим, какой путь мы проделали. Мы начали с интуитивного «махания руками» — физики и геометрии, которые работают на уровне Системы-1, но ломаются в краевых случаях. Заменив касательную на Линейный Патч, инкапсулировав ошибку в форме Лагранжа в ряде Тейлора и прикрутив статический анализатор Канторовича, мы создали строгое, безопасное математическое ядро (Kernel-level). Этот алгоритм не просто «как-то работает», он аппаратно гарантирует результат.
Каст типов: Корни vs Оптимизация
Но подождите. На протяжении всей этой статьи мы решали задачу поиска корня: $f(x) = 0$. Однако в современном Machine Learning и Deep Learning мы почти никогда не ищем корни Loss-функции (идеальный нулевой Loss часто означает жесткий оверфиттинг или невозможен в принципе). В ML мы ищем минимум: $L(w) \to \min$, где $w$ — это веса нашей модели.
Как применить наш мощный метод Ньютона к задаче оптимизации? Нам нужен банальный «каст типов» (Type Casting). Вспомним теорему из базового матанализа: если в какой-то точке функция достигает локального экстремума (например, дна оврага) и дифференцируема в ней, то её первая производная в этой точке обязана быть равна нулю.
Строго говоря, обнуление производной дает нам лишь стационарную точку. Это только кандидат: точка может оказаться и локальным максимумом (вершиной холма), и коварной седловой точкой. В классическом матанализе, чтобы убедиться, что перед нами именно минимум, достаточно проверить поведение первой производной вокруг этой точки (если её знак меняется с минуса на плюс — мы на дне). Однако для численного алгоритма, «ослепшего» в конкретной координате, исследовать окрестности неудобно. Ему нужен мгновенный локальный инструмент — оценка кривизны прямо в точке (вторая производная). Но как бы мы ни проверяли статус точки в конце, базовая алгоритмическая задача минимизации $L(w) \to \min$ всегда сводится к одному: поиску корней первой производной, то есть решению уравнения $L'(w) = 0$.
Давайте возьмем нашу классическую формулу Ньютона $x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$ и просто подставим в нее вместо функции $f$ производную лосса $L'$. Что произойдет?
- Текущая позиция $x_k$ превратится в текущие веса $w_k$.
- Числитель $f(x_k)$ превратится в первую производную лосса $L'(w_k)$.
- А знаменатель $f'(x_k)$ (производная от производной) превратится во вторую производную лосса $L''(w_k)$ (в многомерном мире эта матрица кривизны называется Матрицей Гессе или Гессианом)!
Формула метода Ньютона для оптимизации (ML-версия) принимает вид:
$w_{k+1} = w_k - \frac{L'(w_k)}{L''(w_k)}$
Вот оно! Вторая производная (кривизна), которая раньше скромно сидела в остаточном члене Тейлора и служила лишь для оценки ошибки, теперь официально стала полноправной частью самого алгоритма. Она попала в знаменатель. И это изящно решает проблему слепоты алгоритма: именно вторая производная в знаменателе помогает ему «ощупать» пространство вокруг себя, понять, куда оно выгнуто (вверх или вниз), и скорректировать направление и размер шага.
В следующей части нашей серии мы масштабируем этот алгоритм на многомерные пространства $\mathbb{R}^n$, где миллионы весов нейросети заставят первую производную стать Градиентом, а вторую производную в знаменателе — исполинской Матрицей Гессе (Гессианом). Мы узнаем, почему метод Ньютона в ML — это снайперский выстрел, и почему железо (Hardware) до сих пор не позволяет нам использовать его в чистом виде для обучения GPT.
Вместо послесловия
«В классической математике метод Ньютона — это строго типизированный Rust, где компилятор Канторовича бьет по рукам за любую неточность. А современная оптимизация в Deep Learning (градиентный спуск) — это JavaScript: вместо идеального weights -= inverse(Hessian) * grad мы просто пишем weights -= lr * grad, игнорируем кривизну пространства, ловим NaN в седловых точках и молимся, чтобы костыли оптимизатора Adam (который, по сути, пытается дешево угадать диагональ этого Гессиана через дисперсию градиентов) как-нибудь сами всё разрулили».
No comments:
Post a Comment