Простой и широко используемый математический метод наконец-то может быть применён к решению бесконечно сложных задач. Комментарий Сохранить статью Прочитать позже
Введение
Каждый день исследователи ищут оптимальные решения. Возможно, им нужно определить, где построить крупный авиатранспортный узел. Или найти способ максимизировать доходность при минимизации риска инвестиционного портфеля. Или разработать беспилотные автомобили, способные различать сигналы светофора и знаки «стоп».
Математически эти задачи сводятся к поиску минимальных значений функций. Однако во всех этих случаях функции слишком сложны для прямого вычисления. Исследователям приходится вместо этого аппроксимировать минимальные значения.
Оказывается, один из лучших способов сделать это — использовать алгоритм, разработанный Исааком Ньютоном более 300 лет назад. Этот алгоритм довольно прост. Это немного похоже на поиск самой низкой точки в незнакомом ландшафте вслепую. Когда вы ставите одну ногу перед другой, вам нужна только информация о том, поднимаетесь ли вы или спускаетесь, и увеличивается или уменьшается уклон. Используя эту информацию, вы можете довольно быстро получить хорошее приближение к минимуму.
Несмотря на свою огромную мощь (спустя столетия метод Ньютона по-прежнему играет ключевую роль в решении современных задач в логистике, финансах, компьютерном зрении и даже чистой математике), у него есть существенный недостаток. Он работает не со всеми функциями. Поэтому математики продолжают изучать этот метод, находя различные способы расширить его область применения без ущерба для эффективности.
Прошлым летом три исследователя объявили о последнем усовершенствовании метода Ньютона. Амир Али Ахмади из Принстонского университета вместе со своими бывшими студентами Абрааром Чаудхари (ныне работающим в Технологическом институте Джорджии) и Джеффри Чжаном (ныне работающим в Йельском университете) расширили метод Ньютона, сделав его эффективным для самого широкого класса функций на сегодняшний день.
«Метод Ньютона имеет тысячу различных применений в оптимизации, — сказал Ахмади. — Потенциально наш алгоритм может его заменить».
В 1680-х годах Исаак Ньютон разработал алгоритм поиска оптимальных решений. Три столетия спустя математики всё ещё используют и совершенствуют его метод.
Многовековая техника
Математические функции преобразуют входные данные в выходные. Часто важнейшей характеристикой функции является её минимальное значение — комбинация входных данных, дающая минимально возможный выходной сигнал.
Но найти минимум сложно. Функции могут содержать десятки переменных, возведённых в высокие степени, что не поддаётся формульному анализу; графики их решений образуют многомерные ландшафты, которые невозможно исследовать с высоты птичьего полёта. В этих многомерных ландшафтах, как сказала Коралия Картис из Оксфордского университета, «мы хотим найти долину. Некоторые из них — локальные долины, другие — низшая точка. Вы пытаетесь найти всё это, и вопрос в том: какая информация вам доступна, чтобы это сделать?»
В 1680-х годах Ньютон осознал, что даже при работе с очень сложной функцией всегда будут доступны как минимум два источника информации, помогающие найти её самую глубокую впадину. Во-первых, можно вычислить так называемую первую производную функции, или наклон: крутизну функции в данной точке. Во-вторых, можно вычислить скорость изменения самого наклона (вторую производную функции).
Амир Али Ахмади видит проблемы оптимизации повсюду, куда ни глянь.
Допустим, вы пытаетесь найти минимум какой-то сложной функции. Сначала выберите точку на кривой функции, которая, по вашему мнению, может быть близка к истинному минимуму. Вычислите первую и вторую производные функции в этой точке. Эти производные можно использовать для построения специального квадратного уравнения — параболы, если функция находится в двумерной плоскости, и параболоида, если функция многомерна. Это квадратное уравнение, называемое приближением Тейлора, приблизительно соответствует вашей функции в выбранной точке.
Теперь вычислите минимум квадратного уравнения вместо исходного — это можно легко сделать, используя известную формулу. (Это потому, что квадратные уравнения просты; когда уравнения становятся сложнее, вычисление минимума становится невыполнимой задачей.) Вы получите точку. Затем подставьте координаты этой точки обратно в исходную функцию, и вы получите новую точку функции, которая, как мы надеемся, ближе к её истинному минимуму. Начните весь процесс заново.
Ньютон доказал, что если повторять этот процесс, то в конечном итоге найдёшь минимальное значение исходной, более сложной функции. Этот метод не всегда работает, особенно если начать с точки, слишком далекой от истинного минимума. Но в большинстве случаев он работает. И у него есть несколько привлекательных свойств.
Другие итерационные методы, такие как градиентный спуск — алгоритм, используемый в современных моделях машинного обучения, — сходятся к истинному минимуму с линейной скоростью. Метод Ньютона сходится к нему гораздо быстрее: с «квадратичной» скоростью. Другими словами, он позволяет определить минимальное значение за меньшее количество итераций, чем градиентный спуск. (Каждая итерация метода Ньютона требует больших вычислительных затрат, чем итерация градиентного спуска, поэтому исследователи предпочитают градиентный спуск для некоторых приложений, например, для обучения нейронных сетей. Тем не менее, метод Ньютона по-прежнему чрезвычайно эффективен, что делает его полезным в самых разных контекстах.)
Ньютон мог бы написать свой метод, сходящийся к истинному минимальному значению ещё быстрее, если бы вместо того, чтобы брать только первую и вторую производные в каждой точке, он также брал, скажем, третью и четвёртую производные. Это дало бы ему более сложные аппроксимации Тейлора, с показателями степеней больше 2. Но вся суть его стратегии заключалась в преобразовании сложной функции в более простую. Эти более сложные уравнения Тейлора были выше математических возможностей Ньютона.
«Ньютон сделал это для степени 2. Он сделал это, потому что никто не знал, как минимизировать многочлены более высокого порядка», — сказал Ахмади.
В последующие столетия математики работали над расширением его метода, чтобы выяснить, сколько информации они могут извлечь из более сложных приближений Тейлора своих функций.
Например, в XIX веке русский математик Пафнутий Чебышёв предложил вариант метода Ньютона, который аппроксимировал функции кубическими уравнениями (со степенью 3). Однако его алгоритм не работал, когда исходная функция содержала несколько переменных. Совсем недавно, в 2021 году, Юрий Нестеров (ныне работающий в Будапештском университете Корвина) продемонстрировал, как эффективно аппроксимировать функции любого числа переменных кубическими уравнениями. Однако его метод нельзя было распространить на аппроксимацию функций, использующих уравнения четвёртой, пятой и так далее степени, не потеряв при этом эффективности. Тем не менее, это доказательство стало крупным прорывом в этой области.
Теперь Ахмади, Чаудхари и Чжан развили результат Нестерова ещё дальше. Их алгоритм работает для любого числа переменных и произвольного числа производных. Более того, он остаётся эффективным во всех этих случаях, что до сих пор было невозможно.
Но сначала им нужно было найти способ значительно упростить сложную математическую задачу.
Нахождение пространства для маневра
Не существует быстрого и универсального метода поиска минимумов функций, возведённых в высокие степени. Это всегда было главным ограничением метода Ньютона. Однако существуют определённые типы функций, обладающие свойствами, позволяющими легко их минимизировать. В новой работе Ахмади, Чаудхари и Чжан доказывают, что всегда можно найти аппроксимирующие уравнения, обладающие этими свойствами. Затем они показывают, как адаптировать эти уравнения для эффективного применения метода Ньютона.
Какие свойства позволяют легко минимизировать уравнение? Два фактора: во-первых, уравнение должно иметь чашеобразную, или «выпуклую», форму. Вместо множества впадин у него всего одна — это значит, что при попытке минимизировать его можно не беспокоиться о том, что случайная впадина будет принята за самую низкую.
Абраар Чаудхри и двое его коллег недавно нашли способ улучшить многовековой метод нахождения минимумов функций.
Второе свойство заключается в том, что уравнение можно записать в виде суммы квадратов. Например, 5x² + 16x + 13 можно записать в виде суммы (x + 2)² + (2x + 3)². В последние годы математики разработали методы минимизации уравнений с произвольно большими показателями степеней, при условии, что они одновременно выпуклы и представляют собой сумму квадратов. Однако эти методы оказались малоэффективны в случае метода Ньютона. В большинстве случаев используемое вами приближение Тейлора не будет обладать этими полезными свойствами.
Однако Ахмади, Чаудхари и Чжан придумали, как использовать метод, называемый полуопределенным программированием, чтобы изменить приближение Тейлора ровно настолько, чтобы оно стало и суммой квадратов, и выпуклой функцией, но не настолько, чтобы оно оторвалось от исходной функции, на которую должно было напоминать.
По сути, они добавили множитель подстановки к разложению Тейлора, превратив его в уравнение, обладающее двумя желаемыми свойствами. «Мы можем немного изменить разложение Тейлора, чтобы упростить его минимизацию. Представьте себе разложение Тейлора, но немного модифицированное», — сказал Ахмади. Затем он и его коллеги показали, что, используя эту модифицированную версию разложения Тейлора, которая включала произвольное количество производных, их алгоритм всё равно сходится к истинному минимуму исходной функции. Более того, скорость сходимости масштабировалась с числом используемых производных: подобно тому, как использование двух производных позволило Ньютону приблизиться к истинному минимуму с квадратичной скоростью, использование трёх производных позволило исследователям приблизиться к нему с кубической скоростью, и так далее.
Ахмади, Чаудхари и Чжан создали более мощную версию метода Ньютона, которая позволяет достичь истинного минимального значения функции за меньшее количество итераций, чем предыдущие методы.
Как и в случае с оригинальной версией метода Ньютона, каждая итерация этого нового алгоритма по-прежнему требует больших вычислительных затрат, чем такие методы, как градиентный спуск. В результате, на данный момент, новая разработка не изменит работу беспилотных автомобилей, алгоритмов машинного обучения или систем управления воздушным движением. Лучшим вариантом в этих случаях по-прежнему остаётся градиентный спуск.
«Многие идеи оптимизации требуют годы, прежде чем их можно будет полностью реализовать на практике», — сказал Джейсон Альтшулер из Пенсильванского университета. «Но это кажется новым взглядом».
Если со временем базовая вычислительная технология, необходимая для работы метода Ньютона, станет более эффективной, что сделает каждую итерацию менее затратной в вычислительном плане, то алгоритм, разработанный Ахмади, Чаудхари и Чжаном, в конечном итоге сможет превзойти градиентный спуск для самых разных приложений, включая машинное обучение.
«Теоретически наш алгоритм, несомненно, быстрее», — сказал Ахмади. Он добавил, что надеется, что через 10–20 лет так же будет и на практике.
Исправление: 25 марта 2025 г.
Графика в этой статье была обновлена.
Источник: www.quantamagazine.org
