300 років потому: вчені виявили новий потенціал у ньютонівському методі

Понад три століття дослідники покладалися на потужний алгоритм, розроблений Ісааком Ньютоном, для вирішення складних проблем у сфері логістики, фінансів, технологій та навіть чистої математики.

• Вчені спростували власне спростування щодо виробництва електроенергії з обертання Землі

Деталі

Цей простий, але ефективний метод забезпечує чудовий спосіб наближених рішень, коли прямі обчислення надто складні. Але навіть метод, розроблений одним із найвидатніших умів історії, має свої обмеження — він не працює належним чином для всіх функцій. Однак це може скоро змінитися, адже команда дослідників розширила метод Ньютона, зробивши його потужнішим, ніж будь-коли.

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

Їхня робота розширює метод Ньютона, щоб ефективно працювати з найширшим класом функцій, підносячи багатовікову техніку на нові висоти.

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

У 1680-х роках Ісаак Ньютон розробив метод вирішення цієї проблеми, використовуючи дві ключові частини інформації: нахил функції (перша похідна) і те, як цей нахил змінюється (друга похідна).

Його підхід передбачає апроксимацію складної функції за допомогою простішого квадратного рівняння, розв’язання її мінімуму та повторення процесу до досягнення справжнього мінімуму.

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

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

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

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

Однак для цього дослідникам потрібно було спочатку розібратися зі складним математичним завданням.

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

Однак деякі функції мають особливі характеристики, які полегшують їх мінімізацію. У своїй новій роботі Ахмаді, Чаудрі та Чжан доводять, що завжди можливо створити наближені рівняння з цими сприятливими характеристиками.

Тріо показало, як налаштувати ці рівняння, щоб ефективно використовувати метод Ньютона. Згідно з їх дослідженням, рівняння легше мінімізувати, якщо воно має дві ключові властивості.

По-перше, воно має бути чашоподібним, або “опуклим”. Це означає, що графік рівняння має мати лише одну долину замість багатьох, усуваючи можливість помилково прийняти довільну долину за найнижчу.

По-друге, рівняння можна записати у вигляді суми квадратів.

Останніми роками математики розробили методи мінімізації рівнянь із великими показниками степеня, якщо вони відповідають цим двом умовам — опуклості та сумі квадратів.

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

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

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

Використовуючи цю модифіковану версію наближення Тейлора, Ахмаді та його колеги показали, що їхній алгоритм все одно буде сходитися до справжнього мінімуму вихідної функції, навіть якщо він включає будь-яку кількість похідних.

Вони також виявили, що швидкість конвергенції зростає з кількістю використовуваних похідних. Подібно до методу Ньютона, використання двох похідних сходиться з квадратичною швидкістю.

За допомогою цього методу Ахмаді, Чоудрі та Чжан створили більш потужну версію методики Ньютона, яка дозволяє досягати справжнього мінімуму функції за меншу кількість ітерацій, ніж попередні методи.

У майбутньому цей покращений метод Ньютона можна буде використовувати у машинному навчанні.

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