300 лет спустя: учёные обнаружили новый потенциал в методе Ньютона

Более трёх столетий исследователи полагались на мощный алгоритм, разработанный Исааком Ньютоном, для решения сложных проблем в сфере логистики, финансов, технологий и даже чистой математики.

• Ученые опровергли собственное опровержение относительно производства электроэнергии от вращения Земли

Детали

Этот простой, но эффективный метод обеспечивает отличный способ приближённых решений, когда прямые вычисления слишком сложны. Но даже метод, разработанный одним из самых выдающихся умов истории, имеет свои ограничения — он не работает должным образом для всех функций. Однако это может скоро измениться, ведь команда исследователей расширила метод Ньютона, сделав его более мощным, чем когда-либо.

Прошлым летом Амир Али Ахмади из Принстонского университета вместе со своими бывшими студентами Абрааром Чаудри (теперь в Технологическом институте Джорджии) и Джеффри Чжаном (теперь в Йельском университете) представили последний прорыв.

Их работа расширяет метод Ньютона, чтобы эффективно работать с самым широким классом функций, поднимая многовековую технику на новые высоты.

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

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

Его подход предполагает аппроксимацию сложной функции более простым квадратным уравнением, решение её минимума и повторение процесса до достижения истинного минимума.

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

Математики давно пытались усовершенствовать метод Ньютона. В 19 веке математик Пафнутий Чебышев представил версию, которая использовала кубические уравнения для приближения функций, но она не работала для функций с несколькими переменными.

Совсем недавно Юрий Нестеров из Будапештского университета Корвина разработал метод в 2021 году, который мог обрабатывать несколько переменных с помощью кубических уравнений. Однако распространение его на более сложные уравнения, такие как квартическое или квинтическое, сделало его неэффективным. Несмотря на это ограничение, его работа стала большим прорывом в оптимизации.

Ахмади, Чаудри и Чжан основывались на работе Нестерова, чтобы разработать алгоритм, который обрабатывает любое количество переменных и производных, оставаясь эффективным — то, что ранее считалось невозможным.

Однако для этого исследователям нужно было сначала разобраться со сложной математической задачей.

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

Однако некоторые функции имеют особые характеристики, которые облегчают их минимизацию. В своей новой работе Ахмади, Чаудри и Чжан доказывают, что всегда возможно создать приближённые уравнения с этими благоприятными характеристиками.

Трио показало, как настроить эти уравнения, чтобы эффективно использовать метод Ньютона. Согласно их исследованию, уравнения легче минимизировать, если они имеют два ключевые свойства.

Во-первых, оно должно быть чашеобразным, или "выпуклым". Это означает, что график уравнения должен иметь только одну долину вместо множества, устраняя возможность ошибочно принять произвольную долину за самую низкую.

Во-вторых, уравнение можно записать в виде суммы квадратов.

В последние годы математики разработали методы минимизации уравнений с высокими показателями степени, если они соответствуют этим двум условиям — выпуклости и сумме квадратов.

Однако эти методы не применяются к методу Ньютона, поскольку в большинстве случаев приближение Тейлора, используемое в процессе, естественно не обладает этими свойствами.

Используя технику, называемую полуопределённым программированием, исследователи нашли способ перестроить приближение Тейлора так, чтобы сделать его суммой квадратов и выпуклым.

Трио просто добавило к приближению Тейлора фактор ошибки, изменив его на уравнение с двумя желаемыми свойствами.

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

Они также обнаружили, что скорость сходимости возрастает с количеством используемых производных. Подобно методу Ньютона, использование двух производных сходится с квадратичной скоростью.

С помощью этого метода Ахмади, Чаудри и Чжан создали более мощную версию методики Ньютона, которая позволяет достигать истинного минимума функции за меньшее количество итераций, чем предыдущие методы.

В будущем этот улучшенный метод Ньютона можно будет использовать в машинном обучении.

Ранее исследование компании OpenAI показало, что наказание искусственного интеллекта за обманчивые или вредные действия не останавливает его от неподобающего поведения, а просто заставляет его лучше скрывать ложь.