Выпуклость, минимумы и принцип Ферма

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

Условие Ферма: в минимуме склон нулевой

Начнём с простого наблюдения, которому почти четыре века. Если гладкая функция достигает минимума или максимума во внутренней точке, то её производная там равна нулю. В минимуме дно долины горизонтально: слева функция убывала, справа возрастает, а в самой нижней точке склон обнуляется. То же в вершине холма. Это условие сформулировал Пьер Ферма около 1637 года, и оно лежит в основе всей оптимизации:

$$x^{*} \text{ — точка экстремума} \;\Rightarrow\; f'(x^{*}) = 0 .$$

Отсюда рецепт поиска экстремумов, знакомый со школы: продифференцировать функцию, приравнять производную к нулю, решить уравнение. Точки, где $f'=0$, называют стационарными — в них функция «замирает», её мгновенное изменение равно нулю. Именно к таким точкам стремится обучение сети: там, где производная потери по весам обнулилась, дальнейший спуск невозможен, и модель останавливается.

Четыре лица нулевого склона

Итак, $f'=0$ ловит не только минимумы. Горизонтальная касательная бывает у четырёх разных рельефов, и различить их важно. Минимум: слева спуск, справа подъём, дно долины. Максимум: слева подъём, справа спуск, вершина холма. Седло (в одном измерении — точка перегиба со стационарностью): функция на миг замирает, но продолжает в ту же сторону, как ступенька на склоне. И, наконец, плато, где производная ноль на целом участке.

Отличить минимум от максимума помогает вторая производная — скорость изменения самого склона. Если в стационарной точке $f''>0$, склон поворачивает вверх (дно чаши) — это минимум; если $f''<0$, вниз (купол) — максимум; а если $f''=0$, тест молчит, и надо смотреть внимательнее. Так, приравняв к нулю первую производную и проверив знак второй, находят и классифицируют все стационарные точки.

$$f'(x^{*})=0,\; \begin{cases} f''(x^{*})>0 & \Rightarrow\ \text{минимум},\\ f''(x^{*})<0 & \Rightarrow\ \text{максимум},\\ f''(x^{*})=0 & \Rightarrow\ \text{нужен разбор}. \end{cases}$$

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Выпуклость: когда локальное становится глобальным

Пример с кубической функцией пугает: нашли минимум, а он не самый низкий. Для настоящей оптимизации нужна гарантия, что найденный минимум — действительно лучший. Такую гарантию даёт одно свойство функции — выпуклость.

Функция выпукла, если она всюду загибается вверх: её вторая производная неотрицательна, $f''\ge 0$, и график нигде не выгибается куполом. Наглядное определение ещё проще: соедините любые две точки графика отрезком-хордой — у выпуклой функции хорда всюду лежит не ниже графика, кривая провисает под ней, как канат. Парабола, экспонента, модуль — выпуклы; синус или кубическая — нет.

Драгоценное свойство выпуклых функций вот в чём: у них любой локальный минимум является глобальным. Нет ловушек, нет обманных ямок на склоне — всё, что выглядит как дно, и есть настоящее дно. А значит, условие Ферма $f'=0$ находит сразу глобальный минимум, единственный и лучший. Выпуклая оптимизация — решённая задача: приравнял производную к нулю, и готово. Соединив это с условием Ферма, получаем чёткое правило: для выпуклой функции стационарная точка — это глобальный минимум, точка, и никаких проверок второй производной или перебора не требуется. Всё искусство оптимизации в трудных случаях — это, по сути, попытки вернуть себе гарантии, которые выпуклость даёт даром.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Почему нейросети трудно учить

Теперь понятно, отчего одни модели обучаются легко, а другие мучительно. Потеря линейной регрессии — среднеквадратичная ошибка как функция весов — выпукла: это парабола (в многомерном варианте — чаша), у неё единственный минимум, и его находят точной формулой, без всякого спуска. Оттого линейные модели так надёжны: их оптимизация решена раз и навсегда.

А вот потеря нейросети как функция её весов — глубоко невыпуклая: поверхность в миллионномерном пространстве, изрытая несчётным числом локальных минимумов, седловин и плато. Условие Ферма здесь бесполезно: стационарных точек мириады, и приравнять производную к нулю аналитически невозможно. Приходится спускаться шаг за шагом, скатываясь в какое-то дно — и нет гарантии, что оно глобальное. Вся сложность обучения сетей растёт из этой невыпуклости; удивительно не то, что глубокие сети трудно учить, а то, что найденные локальные минимумы обычно оказываются достаточно хорошими. Почему — вопрос, над которым наука бьётся до сих пор.

На реальных данных: оптимальный размер пула

Оптимизация с настоящим минимумом бывает и вдалеке от нейросетей. Классический пример — групповое тестирование, придуманное Робертом Дорфманом в 1943 году, когда призывников массово проверяли на болезнь. Идея: вместо того чтобы делать анализ каждому, смешивают кровь группы из $n$ человек и тестируют смесь. Если она чиста — все $n$ здоровы за один тест; если положительна — тестируют каждого отдельно. Когда больных мало, огромное большинство групп чисты, и экономия колоссальна.

Сколько человек брать в группу? Слишком маленькая группа почти не экономит тестов, слишком большая почти всегда даёт положительную смесь и требует поголовной перепроверки. Между этими крайностями есть наилучший размер. Ожидаемое число тестов на человека при доле больных $p$ равно

$$C(n) = \frac1n + \Bigl(1 - (1-p)^n\Bigr),$$

где $1/n$ — доля первого группового теста на человека, а второе слагаемое — вероятность, что группа окажется положительной и потребует поголовной перепроверки. Эта функция размера группы $n$ — чашеобразная, с единственным минимумом. При доле больных $1\%$ она минимальна при группе из $11$ человек и даёт всего $0{,}20$ теста на человека — в пять раз меньше поголовного, экономия $80\%$. Реальная оптимизация, реальный минимум, найденный тем же условием: производную по $n$ в ноль.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Русская линия: как считать оптимальное

Превратить «найти наилучшее» из искусства в науку — заслуга во многом советской математики. В 1939 году ленинградский математик Леонид Канторович, разбирая задачу фанерного треста о том, как распределить станки, чтобы выпуск был максимальным, создал линейное программирование — метод поиска оптимума при линейных ограничениях. Это была новая математика оптимального планирования: как распределить ресурсы, перевезти грузы, загрузить производство наилучшим образом. За теорию оптимального использования ресурсов Канторович в 1975 году получил Нобелевскую премию по экономике — единственный советский экономический нобелиат. Оптимизация, которой мы обучаем нейросети, и оптимизация, которой Канторович планировал экономику, — одна математика минимума и максимума, просто на разных ландшафтах.

Лаборатория: рельефы и ловушки

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

Сборка: лёгкие задачи и трудные

Прежде чем спускаться к минимуму, мы разобрались, что это такое. Условие Ферма превращает поиск экстремума в решение уравнения $f'=0$, но ловит все стационарные точки скопом — минимумы, максимумы, седла, плато; отделить минимум помогает вторая производная. Главный же водораздел проводит выпуклость: у выпуклой функции любой локальный минимум глобален, ловушек нет, и оптимизация решена — оттого линейные модели надёжны. Невыпуклый рельеф нейросетевой потери полон локальных минимумов и седловин, и там нет ни формулы, ни гарантии лучшего ответа — только спуск шаг за шагом в какое-то дно. Мы увидели настоящий минимум настоящей задачи на групповом тестировании и вспомнили Канторовича, сделавшего оптимизацию наукой. Осталось главное: как, собственно, спускаться к дну, не видя всей поверхности, а щупая её под ногами. Инструмент для этого — производная, указывающая направление наискорейшего спуска, градиент; с него начинается механика обучения.

Задачи