Ограничения, Лагранж и разреженность

Штраф наказывает плохой выбор после того, как он сделан. Ограничение работает раньше: оно очерчивает область, из которой вообще разрешено выбирать. И почти всегда лучшая допустимая точка лежит там, где линия уровня цели впервые касается границы этой области.

Разрешено не всё

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

Запишем это так: ищем минимум $f(x,y)$ при условии

$$g(x,y)=0.$$

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

Равенство задаёт кривую

Условие $g(x,y)=0$ вырезает на плоскости кривую — линию допустимых точек. Двигаться по ней можно только вдоль касательного направления $v$. Малый шаг вдоль границы не меняет $g$ в первом порядке, а это значит, что касательная перпендикулярна градиенту ограничения:

$$\nabla g^\top v=0.$$

Теперь встанем в условный минимум. Если бы вдоль границы оставалось направление, в котором $f$ убывает, мы бы туда сдвинулись и получили точку получше. Значит, в оптимуме любое допустимое движение не меняет $f$ в первом порядке:

$$\nabla f^\top v=0.$$

Оба градиента перпендикулярны одной и той же касательной. На плоскости это оставляет им единственную возможность — лежать на одной прямой. Так рождается условие Лагранжа:

$$\nabla f(x^\star,y^\star)+\lambda\,\nabla g(x^\star,y^\star)=0.$$

Геометрия касания

Условие Лагранжа удобнее всего читать глазами. Линии уровня цели — это вложенные кривые, вдоль каждой из которых $f$ постоянна. Спускаясь к минимуму цели, мы перебираем всё меньшие уровни. Пока линия уровня пересекает границу под углом, вдоль границы есть куда сползти на уровень пониже. Спуск вдоль забора прекращается ровно тогда, когда очередная линия уровня коснулась границы, не пересекая её. В точке касания их касательные совпадают, а значит, совпадают и перпендикуляры к ним — два градиента ложатся на одну прямую.

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

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

Множитель как цена ресурса

У числа $\lambda$ есть смысл, ради которого его и стоит вычислять. Ослабим ограничение: пусть теперь допускается $g(x,y)=c$ для маленького $c$. Оптимальное значение цели сдвинется, и скорость этого сдвига — как раз множитель. Для записи $f+\lambda(g-c)$ выполняется

$$\frac{dV}{dc}=-\lambda,\qquad V(c)=\min_{g=c} f.$$

Множитель показывает, насколько улучшится лучшая достижимая ошибка, если дать задаче ещё чуть-чуть свободы. Поэтому его называют теневой ценой ресурса: он говорит, сколько «стоит» в единицах цели один лишний метр границы.

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

Неравенство и активная граница

Ограничения-равенства редки; чаще встречается неравенство $g(x)\le0$ — «не дороже бюджета», «не больше веса». Здесь возможны два случая. Свободный минимум может уже лежать внутри разрешённой области; тогда граница ни при чём, и множитель равен нулю. Либо свободный минимум за границей, и оптимум прижимается к ней; тогда множитель положителен, а работает всё то же условие касания.

Эти два случая связывает одно равенство:

$$\lambda\,g(x)=0.$$

Оно требует: либо запас есть и $g(x)<0$, тогда $\lambda=0$; либо граница активна и $g(x)=0$, тогда $\lambda$ может быть ненулевым. Вместе с допустимостью и стационарностью это часть условий Каруша—Куна—Таккера — рабочего языка оптимизации с неравенствами.

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

Круг Тихонова и ромб

До сих пор форма ограничения была любой. Но в машинном обучении почти всегда штрафуют размер вектора весов, и тут форма решает всё. Ограничение $\lVert w\rVert_2\le R$ задаёт круг, а $\lVert w\rVert_1\le R$ — ромб с углами на осях. Одна и та же линия уровня квадратичной ошибки коснётся этих областей в разных местах.

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

Круговое ограничение $\lVert w\rVert_2\le R$ — это и есть регуляризация Тихонова, гребневая регрессия. Советский математик Андрей Тихонов пришёл к ней, разбираясь с некорректно поставленными задачами, где крошечное изменение данных швыряло решение куда попало. Добавка, наказывающая большие веса, стабилизирует ответ, делая его устойчивым к шуму.

Ромб $L_1$ ведёт себя иначе. Его грани сходятся в острые углы, и решение цепляется за них охотнее, чем за гладкую сторону круга. В угле часть координат — ровно ноль. Поэтому $L_1$ не просто уменьшает веса, а занулит лишние, отбирая небольшой набор признаков. Механику этого видно на операции мягкого порога: если вклад признака по модулю меньше порога, $L_1$ обнуляет его начисто.

Разреженность на реальных данных

Проверим это на живом примере. Возьмём классический набор о диабете (Эфрон и соавторы, 2004): для 442 пациентов записаны десять показателей — возраст, пол, индекс массы тела, давление и шесть анализов крови, — а целевая величина показывает, насколько болезнь продвинулась за год. Задача врача-статистика: если позволено оставить лишь несколько измерений, какие сохранить?

Прогоним $L_1$-регрессию при разных штрафах $\alpha$. Штраф большой — модель обязана держать почти все веса нулевыми и оставляет только самые полезные признаки; штраф ослабевает — по одному подключаются остальные. Так рисуется путь коэффициентов.

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

Вывод содержательный, а не только технический. Модель, поставленная в условия жёсткой экономии, сама выделила показатели, которые медицина считает ключевыми для диабета. Для сравнения: гребневое ограничение Тихонова на тех же данных сжало бы все десять весов, но не обнулило ни одного — короткого списка признаков от него не дождёшься. Разреженность — исключительное свойство острых углов $L_1$.

Но у короткого списка есть ловушка. Если два признака сильно связаны, $L_1$ может выбрать один из пары почти наугад и занулить второй. Нулевой коэффициент говорит о сделанном выборе, а не о том, что признак не важен. Поэтому отобранный набор проверяют на устойчивость: перетасовывают обучающие строки и смотрят, держится ли состав. Если он скачет от пересчёта к пересчёту, объяснять его как причину болезни опасно.

Геометрия против алгоритма

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

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

Лаборатория касания

Порядок опытов. Перед вами линии уровня квадратичной потери и синяя допустимая область. Красная точка — решение с ограничением, там, где линия уровня впервые коснулась границы. Кликните по полю — свободный минимум цели переедет в это место, и решение пересчитается. Переключайте форму ограничения и меняйте бюджет $R$. Понаблюдайте за главным: у ромба $L_1$ при многих положениях цели решение садится точно на ось, и один вес обнуляется, а у круга $L_2$ оба веса остаются живыми при том же бюджете. Увеличьте $R$ настолько, чтобы свободный минимум попал внутрь области, — ограничение погаснет, и решение вернётся в свободный минимум. Вы своими руками нащупаете, откуда берётся разреженность.

Сборка: форма забора решает судьбу решения

Оптимизация с ограничениями держится на одной картинке: лучшая допустимая точка лежит там, где линия уровня цели касается границы, и в этой точке градиент цели уравновешен нормалью ограничения, $\nabla f+\lambda\nabla g=0$. Множитель $\lambda$ — не служебная буква, а теневая цена: скорость, с которой лучшая ошибка падает при ослаблении границы. Для неравенств добавляется условие дополнения: граница либо активна, либо спит. А форма ограничения задаёт характер решения: круглое ограничение Тихонова мягко сжимает все веса и стабилизирует модель, ромб $L_1$ цепляется углами за оси и отбирает короткий набор признаков — что и подтвердил путь Lasso на данных о диабете, оставив от десяти показателей всего два. Осталось соединить это с обучением: штраф входит в потерю, его производная течёт по сети в обратном распространении, а недифференцируемые ограничения — на память или число ненулевых весов — обходят проекцией или отдельным шагом сжатия. С этого перехода от геометрии к работающему алгоритму продолжается механика обучения.

Задачи