Преобразование Лежандра со всех сторон

Учась в институте, я встречал преобразование Лежандра в совершенно неожиданных местах: от методов оптимизации до физики. Было очевидно, что существует некоторая фундаментальная структура, сшивающая все воедино. В этой статье пробую нащупать эту нить: показываю, как преобразование Лежандра проявляется в различных областях, стараюсь идти от конкретных примеров и делать акцент на связях - чтобы выстроить цельную картину. Приветствую любые комментарии и указания на ошибки/неточности

Геометрия

Для начала рассмотрим функцию $f(x) = x^{2}$ . В точке $x_{0}$ касательная: $h(x) = f\left( x_{0} \right) + f^{'}\left( x_{0} \right)\left( x - x_{0} \right)$

$x^{2}$ – типичный пример гладкой выпуклой функции. Формализуем интуицию вокруг выпуклости:

Во-первых, выпуклая функция – это та, чей надграфик выпуклый, т.е. содержит любую хорду. Двигаясь между точками $\left( x,f(x) \right)$ и $\left( y,f(y) \right)$ , мы всегда оказываемся над графиком. Это называют неравенством Йенсена:

$f \left( tx + (1 - t)y \right) \leq t \cdot f(x) + (1 - t) \cdot f(y)\ \forall x,y\ \forall t \in \lbrack 0,1\rbrack$

Во-вторых, для гладких функций выпуклость можно определить так: график функции лежит над касательными:

$f(y) \geq f(x) + f^{'}(x)(y - x)\ \ \forall x,y$

В-третьих, геометрически это означает, что наклон f растет быстрее, чем наклон касательной: $f^{''}(x) \geq 0\ \ \forall x$

Остановимся на (2). Заметим, что функцию можно описать двумя способами:

набором всех точек , таких что
набором всех касательных, оборачивающих график функции. Каждая касательная задается тоже двумя числами: - наклоном и сдвигом по вертикали

Оказывается, для выпуклых функций оба описания эквивалентны. Пока фиксируем, а чем это полезно - ниже

Алгебра

Рассмотрим некоторую хитрую конструкцию. Возьмем функцию и сопоставим ей функцию $f^{*}(p)$ по такому правилу (пока примем это как черный ящик, постепенно поймем глубинные смыслы):

$f^{*}(p) = \sup_{x}\left( px - f(x) \right)$

Посмотрим на примерах:

$f(x) \equiv 0\ \ \Rightarrow \ \ f^{*}(p) = \sup_{x}(px) = \left\{ \begin{matrix} 0,\ \ p = 0 \\ \infty,\ \ p \neq 0 \end{matrix} \right.$

Получилась некоторая «вывернутая дельта-функция»: во всех точках $\infty$ , в нуле 0. Попробуем сдвинуть исходную функцию f по вертикали:

$f(x) \equiv b\ \ \Rightarrow \ \ f^{*}(p) = \sup_{x}(px - b) = \left\{ \begin{matrix} - b,\ \ p = 0 \\ \infty,\ \ p \neq 0 \end{matrix} \right.$

Наша конструкция $f^{*}(p)$ просела на некоторый сдвиг, но все еще центрирована в . Усложним пример:

$f(x) = x\ \ \Rightarrow \ \ f^{*}(p) = \sup_{x}\left( (p - 1)x \right) = \left\{ \begin{matrix} 0,\ \ p = 1 \\ \infty,\ \ p \neq 1 \end{matrix} \right.$

Получилась та же «вывернутая дельта-функция», но теперь с центром в 1. Видно, что этот пример отличается от самого первого в единственном месте: множитель перед x в первом супремуме – просто p, а в текущем – (p-1). Эта единица возникла именно как коэффициент перед x, то есть наклон функции f. Обобщим и проверим интуицию:

$f(x) = kx + b\ \ \Rightarrow \ \ f^{*}(p) = \sup_{x}\left( (p - k)x - b \right) = \left\{ \begin{matrix} - b,\ \ p = k \\ \infty,\ \ p \neq k \end{matrix} \right.$

Видно, что наша конструкция $f^{*}(p)$ детектирует наклон исходной функции f(x). Когда аргумент p функции $f^{*}(p)$ совпадает с наклоном исходной функции f(x), индикатор срабатывает, и мы получаем конечное число на выходе. Более того, это число совпало с величиной, на которую нужно сдвинуть функцию вниз, чтобы «обернуть» исходную f снизу (и тогда $\infty$ при $p \neq k$ логична, ведь прямые и гарантированно пересекутся). Эта идея собрана в неравенстве Фенхеля — Юнга:

$f^{}(p) = \sup_{x}\left( px - f(x) \right)\ \ \Rightarrow \ \ f(x) \geq px - f^{*}(p)\ \ \forall x,p$

Прямые $px - f^{*}(p)$ целиком лежат под графиком – это как раз набор касательных, оборачивающих заданную функцию f снизу. Продолжим эксперименты: что если наклон меняется со временем?

$f(x) = x^{2}\ \ \Rightarrow \ \ f^{*}(p) = \sup_{x}\left( - x^{2} + px \right)$

Внутри супремума – парабола ветвями вниз. Теперь связалось, почему мы вообще рассматриваем выпуклые функции: супремум искать проще. В данном случае супремум достигается в вершине параболы $\frac{p}{2}$ . Подставим $x = \frac{p}{2}$ , тогда

$\ f^{*}(p) = px - f\left( \frac{p}{2} \right) = p*\frac{p}{2} - \left( \frac{p}{2} \right)^{2} = \frac{p^{2}}{4}$

Нашей исходной параболе $f(x) = x^{2}$ сопоставляется парабола $f^{*}(p) = \frac{p^{2}}{4}$ , лежащая ниже исходной. А что если провернуть наше преобразование в обратную сторону?

$f(x) = \frac{x^{2}}{4}\ \ \Rightarrow \ \ f^{*}(p) = \sup_{x}\left( - \frac{x^{2}}{4} + px \right)$

Аналогичные рассуждения про вершину параболы приведут нас к тому, что $f^{*}(p) = p^{2}$ . Получается, конкретно в этом примере мы провели преобразование дважды и вернулись к исходной функции $f^{**} = f$ .

Всегда ли это так? Оказывается, нет: только для выпуклых и замкнутых – это теорема Фенхеля-Моро:

$f^{**} \leq f$ всегда. Фенхель-Юнг: $f(x) \geq px - f^{*}(p)\ \ \forall x,p\ \ \Rightarrow \ \ f(x) \geq \sup_{p}{px - f^{*}(p)} = f^{**}(x)$
$f^{**}$ всегда выпукла и замкнута, по построению
довольно техническое доказательство, по которому $f^{**} = conv\ f$ (выпуклая оболочка f, т.е. множество всех хорд с концами в надграфике). По определению через выпуклый надграфик, выпуклая функция совпадает со своей выпуклой оболочкой, поэтому для выпуклых $f^{**} = f$

Заметим отдельно, что, опираясь на выпуклость, мы подбирали супремум по нулям производной: $f^{*}(p) = \left( px - f(x) \right)\left. \ \right|_{p = f^{'}(x)} = \left( px - f(x) \right)\left. \ \right|_{x = \left( f^{'} \right)^{- 1}(p)}$ . Такая замена требует обратимости $f^{'}$ , т.е. строгой выпуклости – это нам позже пригодится.

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

$f(x) = \frac{x^{2}}{2},\ \ f^{*}(p) = \sup_{x}\left( - \frac{x^{2}}{2} + px \right) = \left( - \frac{x^{2}}{2} + px \right)\left. \ \right|_{p = f^{'}(x)} = \frac{p^{2}}{2}$

Предположим, что существует другая неподвижная точка $g = g^{*},\ \ g \neq f$ . Фенхель-Юнг: $px \leq g(x) + g^{*}(p) = g(x) + g(p)$ для $\forall x,p$ . В частности, для получим $\frac{x^{2}}{2} < g(x)$ . Но тогда:

$g^{*}(p) = \sup_{x}\left( px - g(x) \right) < \sup_{x}\left( px - \frac{x^{2}}{2} \right) = \frac{p^{2}}{2}$

т.е. $g \neq g^{*}$ , противоречие. Значит, $\frac{x^{2}}{2}$ – единственная неподвижная точка. По сути, проводя наше преобразование, мы «отражали» функции относительно «зеркала» $\frac{x^{2}}{2}$ .

Конструкция, которую мы все это время рассматривали, называется преобразованием Лежандра. Ключевая идея: выпуклая функция = верхняя огибающая своих нижних оценок.

Физика / механика

Существует три классических подхода для описания физических систем: по Ньютону, Лагранжу и Гамильтону. Ньютон работает с силами – нам это сейчас не интересно. Сфокусируемся на лагранжевом и гамильтоновом формализме, покажем связь между ними и место, где возникает преобразование Лежандра.

Рассмотрим задачу кинематики: по какой траектории полетит камень в поле гравитации (для простоты – бросим вертикально)?

Можно ввести координату , потенциальную энергию , кинетическую энергию $T = \frac{mv^{2}}{2} = \frac{m{\dot{q}}^{2}}{2}$ . В контексте выпуклых функций сразу бросается в глаза выпуклость кинетической энергии по скоростям (спойлер: это пригодится).

Полная энергия сохраняется, т.е. $0 = \frac{d}{dt}\left( mgq + \frac{m{\dot{q}}^{2}}{2} \right) = mg\dot{q} + m\dot{q}\ddot{q} = m\dot{q}(g + \ddot{q})$ , причем масса положительна, а скорость зануляется только в одной точке (вершине траектории). Остается $\ddot{q} = - g$ . Решив этот дифур, получим знакомое $q = q_{0} + v_{0}t - \frac{gt^{2}}{2}$ .

Вместо скорости $\dot{q}$ , можно описать систему через изменение импульса: $\frac{dp}{dt} = - mg,\ \ p = m\dot{q} = mv_{0} - mgt$ . Сократив, получим $\dot{q} = v_{0} - gt$ . Решив этот дифур, получим такой же ответ: $q = q_{0} + v_{0}t - \frac{gt^{2}}{2}$ .

Вывод: два описания системы (координаты и скорости vs координаты и импульсы) эквивалентны в рассмотренной нами выпуклой задаче.

Оказывается, оба подхода опираются на более глубокую теорию и тесно связаны

Лагранж описывает систему с помощью обобщенных координат и скоростей $\dot{q}$

Вводится кинетическая энергия $T\left( q,\dot{q} \right)$ и потенциальная энергия $U\left( q,\dot{q} \right)$ , их разность называется лагранжианом . Интеграл лагранжиана по времени (вдоль траектории) называется действием:

$S\lbrack q\rbrack = \int_{t_{1}}^{t_{2}}{L\left( q,\dot{q},t \right)dt}$

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

Возмутим траекторию (требования к возмущению – гладкая функция, обнуляющаяся на концах):

$q_{\varepsilon}(t) = q(t) + \varepsilon \cdot \eta(t),\ \ {\dot{q}}_{\varepsilon}(t) = \dot{q}(t) + \varepsilon \cdot \dot{\eta}(t),\ \ \eta\left( t_{1} \right) = \eta\left( t_{2} \right) = 0$

Действие вдоль возмущенной траектории:

$S\left\lbrack q_{\varepsilon} \right\rbrack = S(\varepsilon) = \int_{t_{1}}^{t_{2}}{L\left( q + \varepsilon\eta,\dot{q} + \varepsilon\dot{\eta},t \right)dt}$

Проварьируем: продифференцируем по $\varepsilon$ , найдем экстремум:

$0 = \frac{\delta S}{\delta q} = \frac{dS}{d\varepsilon} = \int_{t_{1}}^{t_{2}}{\frac{dL\left( q + \varepsilon\eta,\dot{q} + \varepsilon\dot{\eta},t \right)}{d\varepsilon}dt} = \int_{t_{1}}^{t_{2}}{\left\lbrack \frac{\partial L}{\partial q}\frac{\partial q_{\varepsilon}}{\partial\varepsilon} + \frac{\partial L}{\partial\dot{q}}\frac{\partial{\dot{q}}_{\varepsilon}}{\partial\varepsilon} \right\rbrack dt} = \int_{t_{1}}^{t_{2}}{\left\lbrack \frac{\partial L}{\partial q}\eta \right\rbrack dt} + \int_{t_{1}}^{t_{2}}{\left\lbrack \frac{\partial L}{\partial\dot{q}}\dot{\eta} \right\rbrack dt}$

Второе слагаемое – проинтегрируем по частям, вспомнив, что $\eta\left( t_{1} \right) = \eta\left( t_{2} \right) = 0$ :

$0 = \frac{dS}{d\varepsilon} = \int_{t_{1}}^{t_{2}}{\left\lbrack \frac{\partial L}{\partial q}\eta \right\rbrack dt} + \left\lbrack \frac{\partial L}{\partial\dot{q}}\eta \right\rbrack_{t_{1}}^{t_{2}} - \int_{t_{1}}^{t_{2}}{\frac{d}{dt}\left( \frac{\partial L}{\partial\dot{q}} \right)\eta dt} = \int_{t_{1}}^{t_{2}}{\left\lbrack \frac{\partial L}{\partial q} - \frac{d}{dt}\left( \frac{\partial L}{\partial\dot{q}} \right) \right\rbrack\eta dt}$

Мы рассматривали выражения для произвольного $\eta$ , а по основной лемме вариационного исчисления это значит, что квадратная скобка тождественно равна нулю. Получим уравнение Эйлера-Лагранжа:

$\frac{\partial L}{\partial q} - \frac{d}{dt}\left( \frac{\partial L}{\partial\dot{q}} \right) = 0$

В лагранжевом формализме вводится также обобщенный импульс $p = \frac{\partial L}{\partial\dot{q}}$ . Можно подставить систему из школьной механики и проверить соответствие с привычным определением: $p = \frac{\partial}{\partial v}\left( \frac{1}{2}mv^{2} - U(x) \right) = mv$

Гамильтон описывает систему с помощью обобщенных координат и импульсов

Вводится гамильтониан $H = p\dot{q} - L$ . Сразу интересное наблюдение: это выражение уже похоже на содержимое супремума в преобразовании Лежандра, но подойдем к этой связи осторожнее. Пока отметим: в классической механике типично, что кинетическая энергия $T = \frac{mv^{2}}{2} = \frac{p\dot{q}}{2}$ , поэтому $H = p\dot{q} - L = 2T - (T - U) = T + U$ , т.е. полная энергия.

Распишем и проварьируем действие в терминах гамильтониана (дважды и независимо по q,p):

$S\lbrack q,p\rbrack = \int_{t_{1}}^{t_{2}}{\left\lbrack p\dot{q} - H(q,p) \right\rbrack dt},\ \ 0 = \frac{dS}{d\varepsilon} = \int_{t_{1}}^{t_{2}}{\left\lbrack \dot{q} - \frac{\partial H}{\partial p} \right\rbrack\xi dt} - \int_{t_{1}}^{t_{2}}{\left\lbrack \dot{p} + \frac{\partial H}{\partial q} \right\rbrack\eta dt}$

Получим уравнения Гамильтона:

$\dot{q} = \frac{\partial H}{\partial p},\ \ \dot{p} = - \frac{\partial H}{\partial q}$

Оказывается, Гамильтон – это лежандров образ Лагранжа. Рассмотрим $H = \sup_{\dot{q}}\left( p\dot{q} - L \right)$ . На самом деле, мы так и вводили выше, но не заметили, как неявно учли, что находимся в супремуме выражения. Действительно,

$0 = \frac{d}{d\dot{q}}\left( p\dot{q} - L \right) = p - \frac{\partial L}{\partial\dot{q}}$ , т.е. $p = \frac{\partial L}{\partial\dot{q}}$

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

Теперь продифференцируем и подставим определение импульса:

$dH = \dot{q}dp + pd\dot{q} - \frac{\partial L}{\partial q}dq - \frac{\partial L}{\partial\dot{q}}d\dot{q} - \frac{\partial L}{\partial t}dt = \dot{q}dp - \frac{\partial L}{\partial q}dq - \frac{\partial L}{\partial t}dt + \left( p - \frac{\partial L}{\partial\dot{q}} \right)d\dot{q} = \dot{q}dp - \frac{\partial L}{\partial q}dq - \frac{\partial L}{\partial t}dt$

При этом сам . Сопоставим частные производные:

$dH = \frac{\partial H}{\partial p}dp + \frac{\partial H}{\partial q}dq + \frac{\partial H}{\partial t}dt\ \ \ \Rightarrow \ \ \dot{q} = \frac{\partial H}{\partial p},\ \ \frac{\partial H}{\partial q} = - \frac{\partial L}{\partial q}$

Вспомним ур-е Эйлера-Лагранжа – на решении:

$\frac{\partial L}{\partial q} = \frac{d}{dt}\left( \frac{\partial L}{\partial\dot{q}} \right) = \dot{p},\ \ т.е.\dot{p} = - \frac{\partial H}{\partial q}$

Видна первая большая польза от преобразования Лежандра: мы свели ОДУ 2го порядка к паре ОДУ 1го порядка. Плюс существуют методы, которые проще использовать в гамильтоновом формализме (а в квантовой механике в принципе вводится именно оператор Гамильтона), поэтому преобразование Лежандра возникает часто.

Почему это вообще работает? И пара комментариев

Преобразование Лежандра корректно определено, если отображение $\dot{q} \rightarrow p$ локально обратимо (мы ведь выражаем $\dot{q}$ через из определения импульса $p = \frac{\partial L}{\partial\dot{q}}$ ). Достаточное условие – невырожденность гессиана $\frac{\partial^{2}L}{\partial{\dot{q}}^{2}}$ , но более физично условие положительной определенности – т.е. выпуклости лагранжиана по $\dot{q}$ . Почему более физично, на простом примере: $L = \frac{mv^{2}}{2} - U(x),\ \ \ \frac{\partial^{2}L}{\partial{\dot{q}}^{2}} = m > 0$ . Оказывается, гессиан лагранжиана описывает массы и их аналоги, что часто оказывается положительным. Сразу отметим: $p = \frac{\partial L}{\partial\dot{q}}$ и $\dot{q} = \frac{\partial H}{\partial p}$ взаимно обратные отображения, поэтому гессианы и – обратные матрицы (из теоремы об обратной функции). В частности, гессиан описывает величины с размерностью обратных масс (подвижностей)

Есть более глубокий взгляд: постулируется ряд симметрий, из которых выводятся суждения о виде

однородность пространства $\rightarrow T$ зависит только от $\dot{q}$
изотропность пространства $\rightarrow T$ квадратичная форма от $\dot{q}$
из принципа относительности Галилея следует, что законы механики одинаковы в любой ИСО, а значит может зависеть только от координат

Получается, что выпуклость часто гарантируется на фундаментальном уровне. Но не всегда: иногда физика допускает невыпуклые лагранжианы, и тогда эквивалентность Лагранжа vs Гамильтона теряется.

Дополнительно рассмотрим случай, когда какой-то $\dot{q}$ нельзя выразить через свой из $p = \frac{\partial L}{\partial\dot{q}}$ (как мы делали). Это означает $\frac{dp}{d\dot{q}} = \frac{\partial^{2}L}{\partial{\dot{q}}^{2}} = 0$ . Дважды проинтегрируем: $L = C_{1}(q) \cdot \dot{q} + C_{2}(q)$ . Подставим:

$H = \sup_{\dot{q}}\left( p\dot{q} - L \right) = \sup_{\dot{q}}\left( \left( p - C_{1}(q) \right) \cdot \dot{q} - C_{2}(q) \right) = \left\{ \begin{matrix} - C_{2}(q),\ \ p = C_{1}(q) \\ \infty,\ \ p \neq C_{1}(q) \end{matrix} \right.$

Это буквально наш старый пример

$f(x) = kx + b\ \ \Rightarrow \ \ f^{}(p) = \sup_{x}\left( (p - k) \cdot x - b \right) = \left\{ \begin{matrix} - b,\ \ p = k \\ \infty,\ \ p \neq k \end{matrix} \right.$

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

Задачу можно свести к еще более удобному виду, если перейти в координаты, в которых гамильтониан $\equiv 0$ . Решение нам сейчас не интересно, в итоге получится уравнение Гамильтона-Якоби (пригодится, но не скоро, S - вдоль экстремали):

$\frac{\partial S}{\partial t} + H\left( q,\frac{\partial S}{\partial q},t \right) = 0,$

Итог: преобразование Лежандра позволяет переписать задачу в виде, в котором ее иногда проще решать.

Оптимизация

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

Чаще преобразование Лежандра записывают в векторном виде: $f^{*}(p) = \sup_{x}\left( \left\langle x,p \right\rangle - f(x) \right)$ . Для гладких функций: $f^{*}(p) = \left\langle x,p \right\rangle - f(x)$ при $x = (\nabla f)^{- 1}(p)$ . Отсюда же следует: $\nabla f^{*} = (\nabla f)^{- 1}$ . Кроме того, $\nabla^{2}f^{*} = \left( \nabla^{2}f \right)^{- 1}$ (если гессиан обратим - по теореме об обратной функции, что мы пронаблюдали на примере лагранжиана и гамильтониана)

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

Условная оптимизация

Рассмотрим задачу $\min_{x}{f(x)}$ при . Составляем лагранжиан (сразу отметим: это не тот же лагранжиан, который был в физике, к сожалению, тут коллизия имен – лишь совпадение):

$L(x,\lambda) = f(x) + \lambda^{T}(b - Ax)$

Что произошло: для допустимых x (т.е. таких, что второе слагаемое зануляется) можно взять любой множитель $\lambda$ – все равно в скобке ноль. Но теперь давайте рассмотрим не только допустимые x, а вообще все x: свободы больше, значит минимум только опустится:

$\inf_{допустимые\ x}{f(x)} = \inf_{допустимые\ x}\left( f(x) + \lambda^{T}(b - Ax) \right) \geq \inf_{x}\left( f(x) + \lambda^{T}(b - Ax) \right)$

Обозначим $g(\lambda) = \inf_{x}\left( f(x) + \lambda^{T}(b - Ax) \right)$ – это семейство оценок снизу на нашу функцию f. Из этого семейства логично взять лучшую: $\sup_{\lambda}{g(\lambda)}$ – это все еще оценка снизу, но максимальная (наиболее «тугая»).

Перейдя к двойственной задаче, мы буквально провели преобразование Лежандра. Оказывается, преобразование Лежандра всегда было задачей условной оптимизации с линейными ограничениями:

$g(\lambda) = \inf_{x}{L(x,\lambda)} = \lambda^{T}b + \inf_{x}\left\lbrack f(x) - \left( A^{T}\lambda \right)^{T}x \right\rbrack = \lambda^{T}b - \sup_{x}\left\lbrack \left( A^{T}\lambda \right)^{T}x - f(x) \right\rbrack = \lambda^{T}b - f^{*}\left( A^{T}\lambda \right)$

Поскольку все время $g(\lambda)$ по построению были оценками снизу, $\sup_{\lambda}g \leq \inf f$ . Причем в невыпуклом случае зазор ожидается, потому что двойственная задача восстанавливает лишь $f^{**} = conv\ f$ .

Градиентный спуск

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

$x_{k + 1} = x_{k} - \eta \cdot \nabla f\left( x_{k} \right)$

Эту инженерную интуицию можно обосновать аналитически. Аппроксимируем функцию f ее касательной в текущей точке. Попробуем перейти в ее минимум, но минимум касательной, ясно, на бесконечности, поэтому добавим штраф за отход от исходной строчки – норму шага с регулируемым коэффициентом $\eta$ :

$f(x) \approx f\left( x_{k} \right) + \left\langle \nabla f\left( x_{k} \right),\ x - x_{k} \right\rangle$ $x_{k + 1} = \arg{\min\left\lbrack f\left( x_{k} \right) + \left\langle \nabla f\left( x_{k} \right),\ x - x_{k} \right\rangle + \frac{1}{2\eta}\left\| x - x_{k} \right\|^{2} \right\rbrack} = \arg{\min_{x}\left\lbrack \eta\left\langle \nabla f\left( x_{k} \right),x \right\rangle + \frac{1}{2}\left\| x - x_{k} \right\|^{2} \right\rbrack}$

Видно, что градиентный спуск эквивалентен задаче оптимизации с евклидовым штрафом $\left\| x - x_{k} \right\|^{2}$

Продифференцируем выражение под аргминимумом по x:

$\nabla f\left( x_{k} \right) + \frac{1}{\eta}\left( x - x_{k} \right) = 0\ \ \Rightarrow \ \ x_{k + 1} = x_{k} - \eta \cdot \nabla f\left( x_{k} \right)$

Но здесь заложено довольно тонкое допущение, для понимания которого нужно погрузиться в природу сопряженных пространств.

Сопряженное пространство — это множество всех непрерывных линейных функционалов, заданных на исходном пространстве. Преобразование Лежандра переводило нас именно туда. В обоих пространствах существует метрика - симметричная положительно определенная матрица , на основе которой вводится скалярное произведение: $\left\langle u,v \right\rangle_{M} = u^{T}Mv$ . В сопряженном пространстве живет $\partial f$ – “сырой” ковектор-градиент, а в исходном - $\nabla f$ , причем $\left\langle \nabla f,v \right\rangle_{M} = \partial f(v)$ , или $\nabla f = M^{- 1}\partial f$ . В Евклидовой метрике , поэтому $\nabla f = \partial f$ , как мы и писали в формуле градиентного спуска.

Мы ранее уже сталкивались с ситуацией, когда сопряжение не изменяет функцию: $\psi = \frac{1}{2}x^{2}$ . Вернемся к ней, а точнее, рассмотрим $\psi(x) = \frac{1}{2}x^{T}Mx$ . Тогда $\nabla\psi(x) = Mx,\ \ \ \nabla\psi^{*}(p) = M^{- 1}p$ – это буквально наше правило $\nabla\psi^{*} = (\nabla\psi)^{- 1}$ из начала раздела. Как видно, сама матрица $M = \nabla^{2}\psi$ . В физике у нас уже возникал обратимый гессиан $\frac{\partial^{2}L}{\partial{\dot{q}}^{2}} = m > 0$ , масса/матрица инерции. Это та самая матрица , просто в другом контексте.

Возвращаемся к градиентному спуску. В более общем случае $M \neq I$ будет:

$x_{k + 1} = x_{k} - \eta \cdot \nabla f\left( x_{k} \right) = x_{k} - \eta \cdot \nabla\psi^{*}(\partial f)$

Просто мы не заметили, как неявно выбрали самосопряженную $\psi$ – ту самую из начала статьи.

Зеркальный спуск

Суммируем, в чем была проблема. Мы складываем объект из исходного пространства (x) с объектом из сопряженного (градиент). Мы незаметно отождествили пространства и $X^{*}$ , хотя в общем случае они различны. На практике это означает, что мы не учли геометрию задачи. Классический пример – минимизация на вероятностном симплексе: $x_{i} \geq 0,\ \ \sum_{}^{}x_{i} = 1$ . Евклидов штраф на нем всё время утыкается в границы, так что хотелось бы заложить в метод учет геометрии пространств

Эту проблему решает алгоритм зеркального спуска:

берем строго выпуклую гладкую функцию $\psi$ (distance-generating function, «зеркало»)
переводим точку в сопряженное пространство
делаем градиентный спуск в сопряженном пространстве – там, где на самом деле живут градиенты
возвращаемся в исходное пространство

Именно за счет переходов между исходным пространством и сопряженным алгоритм получил название «зеркальный» спуск:

$x_{k + 1} = \nabla\psi^{*}\left( \nabla\psi\left( x_{k} \right) - \eta \cdot \nabla f\left( x_{k} \right) \right)$

Градиентный спуск – частный случай зеркального при $\psi(x) = \frac{1}{2}x^{T}x$ .

У зеркального спуска есть эквивалентная запись (можно убедиться, взяв градиент выражения под argmax):

$x_{k + 1} = \arg{\min_{x}\left\lbrack \eta\left\langle \nabla f\left( x_{k} \right),x \right\rangle + D_{\psi}\left( x,x_{k} \right) \right\rbrack},\ \ где\ D_{\psi}(x,y) = \psi(x) - \psi(y) - \left\langle \nabla\psi(y),x - y \right\rangle$

Функция $D_{\psi}$ называется дивергенцией Брэгмана – по сути, это аналог расстояния. Для $\psi = \frac{1}{2}\left\| \ \cdot \ \right\|^{2}$ будет $D_{\psi}(x,y) = \frac{1}{2}\left\| x - y \right\|^{2}$ , и вся конструкция схлопывается в обычный градиентный спуск.

Вернемся к примеру с минимизацией на вероятностном симплексе $x_{i} \geq 0,\ \ \sum_{}^{}x_{i} = 1$ . Мы упоминали, что евклидов штраф не учитывает геометрию пространства, но какой подошел бы лучше? Оказывается, в качестве зеркала лучше всего подходит отрицательная энтропия $\psi = \sum_{}^{}{x_{i}\log x_{i}}$ .

$D_{\psi}(x,y) = \psi(x) - \psi(y) - \left\langle \nabla\psi(y),x - y \right\rangle = \sum_{}^{}{x_{i}\log x_{i}} - \sum_{}^{}{y_{i}\log y_{i}} - \sum_{}^{}{\left( \log y_{i} + 1 \right)\left( x_{i} - y_{i} \right)} = \sum_{}^{}{x_{i}\log x_{i}} - \sum_{}^{}{x_{i}\log y_{i}} - \sum_{}^{}x_{i} + \sum_{}^{}y_{i} = \sum_{}^{}{x_{i}\log\frac{x_{i}}{y_{i}}} = KL\left( x||y \right)$

Оказывается, дивергенция Брэгмана для отрицательной энтропии становится KL-дивергенцией – естественным аналогом расстояния для распределений.

Метод Ньютона

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

$f(x) \approx f\left( x_{k} \right) + \left\langle \nabla f\left( x_{k} \right),\ x - x_{k} \right\rangle + \frac{1}{2}\left( \ x - x_{k} \right)^{T}\nabla^{2}f\left( x_{k} \right)\left( \ x - x_{k} \right)$ $x_{k + 1} = \arg{\min{\left\lbrack f\left( x_{k} \right) + \left\langle \nabla f\left( x_{k} \right),\ x - x_{k} \right\rangle + \frac{1}{2}\left( \ x - x_{k} \right)^{T}\nabla^{2}f\left( x_{k} \right)\left( \ x - x_{k} \right) \right\rbrack = x_{k} - \left\lbrack \nabla^{2}f\left( x_{k} \right) \right\rbrack^{- 1}\partial f}}$

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

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

Видно, что метод Ньютона использует в качестве метрики гессиан $M = \nabla^{2}f$ и эквивалентен зеркальному спуску с зеркалом $\psi(x) = \frac{1}{2}x^{T}\nabla^{2}f\left( x_{k} \right)x$ . При этом при переходе из сопряженного пространства обратно к иксам, градиент домножается как раз на обратный гессиан (как мы ранее получали связь между гессианом прямой и сопряженной функций, если гессиан невырожден)

Метрику/гессиан $M = \nabla^{2}f$ можно аппроксимировать. Такие методы называют квазиньютоновскими. Например, если М приближается матрицей ранга 2, метод называется BFGS.

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

Статфиз / термодинамика

Вернемся немного к физике. Обсудим одно ложное утверждение, которое я слышал в контексте термодинамики: “преобразование Лежандра меняет интенсивные и экстенсивные величины”.

Что такое «интенсивные» и «экстенсивные»? Пусть система увеличилась в $\lambda$ раз. Тогда $g(\lambda X) = \lambda g(X)$ – экстенсивная (объем V, энтропия S), а $g(\lambda X) = g(X)$ – интенсивная (температура T, давление P). Вообще, функции со свойством $g(\lambda X) = \lambda^{k}g(X)$ называются однородными порядка . Такие функции удобны тем, что масштабируются предсказуемо.

Возьмем внутреннюю энергию . Ее переменные - экстенсивные, а производные $\frac{\partial U}{\partial S} = T,\ \ \frac{\partial U}{\partial V} = - P,\ \ \frac{\partial U}{\partial N} = \mu$ – интенсивные (их вычисление – чисто технический момент). Преобразование Лежандра дает свободную энергию Гельмгольца: $F(T,V,N) = \inf_{S}(U - TS)$ , и экстенсивная S действительно меняется на интенсивную T. Но возьмем теперь все возможные величины в расчете на 1 частицу: $U = Nu(s,v),\ \ F = Nf(T,v)$ . Важно, что s стала интенсивной. Тогда $f(T,v) = \inf_{s}\left( u(s,v) - Ts \right)$ , и Лежандр произвел обмен двух интенсивных величин. Тот факт, что часто лежандрова пара состоит из экстенсивной + интенсивной величины, это просто следствие однородности взятых функций.

Мы затронули интересный момент о сопряженности термодинамических потенциалов. Оказывается, эта ветка открывает ряд ценных связей

Энтропия

Статистический смысл энтропии появляется так. Пусть в ящике с вымышленной перегородкой находится несколько частиц. Суммарное кол-во частиц – макросостояние ящика, а распределение частиц по ячейкам – микросостояния. Всего микросостояний, реализующих данное макросостояние, - $\Omega$ штук, все они независимы и равновероятны (с вероятностью $p = \frac{1}{\Omega}$ ). Энтропия должна быть функцией от $\Omega$ – потому что просто больше не от чего оттолкнуться. При этом мы знаем, что энтропия аддитивна ( $S = S_{1} + S_{2}$ ), а количеств микросостояний мультипликативно, по аналогии с вероятностями независимых событий ( $\Omega = \Omega_{1}\Omega_{2}$ ). Единственная функция, которая переводит произведение в сумму ( $S\left( \Omega_{1}\Omega_{2} \right) = S\left( \Omega_{1} \right) + S\left( \Omega_{2} \right)$ ) – это логарифм, т.е. $S = k\ln\Omega$ . Подставив выражение в закон идеального газа, мы получим, что – константа Больцмана. Сам же ящик не обязан описывать геометрические положения частиц: он может, например, иллюстрировать распределение частиц по энергиям. В итоге $S = k\ln{\Omega(E)}$

Выразим общую энтропию через равные вероятности $p(E) = \frac{1}{\Omega(E)}$ :

$S = k\ln{\Omega(E)} = k \cdot \left( - \frac{\Omega}{\Omega} \right) \cdot \left( - \ln\Omega \right) = - k\sum_{i = 1}^{\Omega}{\frac{1}{\Omega}\ln\frac{1}{\Omega}} = - k\sum_{i = 1}^{\Omega}{p\ln p}$

Это похоже на энтропию Шеннона (об этом – позже)

Второе начало термодинамики гласит, что в изолированной системе энтропия растет, пока не достигнет максимума в термодинамическом равновесии. По виду последней функции ясно, что энтропия максимальна на равномерном распределении. Часто 2е начало искаженно пересказывают как «вселенная стремится к беспорядку», хотя точнее было бы «вселенную вероятнее застать в наиболее вероятном ее состоянии, и таким состоянием является то, что часто соответствует равномерному разбросу». На самом деле, рост энтропии – это просто следствие того факта, что равномерное распределение соответствует наибольшему числу микросостояний среди всех распределений. Эта идея лежит в основе принципа максимума энтропии

Свободная энергия

Посмотрим на вероятность $p_{i}$ микросостояния с энергией $E_{i}$ в системе из ящика и резервуара. Все состояния равновероятны, поэтому вероятность пропорциональна числу способов его реализовать: $p_{i}\ \sim\ \Omega\left( E - E_{i} \right)$ , причем энергия ящика много меньше энергии резервуара ( $E \gg E_{i}$ ). Разложив определение энтропии по Тейлору, получим $\frac{S}{k} = \ln{\Omega\left( E - E_{i} \right)} \approx \ln{\Omega(E)} - \frac{\partial\ln\Omega}{\partial E}E_{i}$ . По определению температуры, $\frac{\partial S}{\partial E} = \frac{1}{T}$ , поэтому $\frac{S}{k} \approx \ln{\Omega(E)} - \frac{E_{i}}{kT}$ . Тогда $\ln p_{i}\sim\ln{\Omega(E)} - \frac{E_{i}}{kT}$ . Взяв экспоненту и учтя константу, получим распределение Гиббса:

$p_{i} = \frac{1}{Z}e^{- E_{i}/kT} = \frac{e^{- E_{i}/kT}}{\sum_{i}^{}e^{- E_{i}/kT}}$

Это похоже на софтмакс с температурой (об этом – позже)

Подставим вероятности в формулу энтропии (вспомнив определение внутренней энергии):

$S = - k\sum_{}^{}{p_{i}\ln p_{i}} = - k\sum_{}^{}{p_{i}\left( - \ln Z - \frac{E_{i}}{kT} \right)} = k\ln Z + \frac{U}{T}\ \ \Rightarrow \ \ U - TS = - kT\ln Z$

А оказалось, что – это определение свободной энергии, поэтому:

$F = - \frac{\ln Z}{\beta},\ \ где\ Z = \sum_{i}^{}e^{- \beta E_{i}}\ и\ \ \beta = \frac{1}{kT}\ \ \ \Rightarrow \ \ \ F = - kT\ln\left\lbrack \sum_{i}^{}e^{- E_{i}/kT} \right\rbrack$

Это похоже на log-sum-exp (об этом – позже)

Связь энтропии и свободной энергии

Проинтегрируем по уровням энергии через плотность состояний:

$Z(\beta) = \int_{}^{}{\Omega(E)e^{- \beta E}dE} = \int_{}^{}e^{S(E)/k\ - \beta E}dE,\ \ где\ S,E\ \sim\ N$

При огромном числе частиц ( $N \rightarrow \infty$ ) работает ЦПТ. Поэтому подынтегральная функция концентрируется вблизи максимума, вырождается в дельта-функцию, и вклад в интеграл дает лишь одно значение подынтегральной функции – в ее максимуме (это на пальцах метод перевала):

$Z(\beta) = \exp\left\lbrack \sup_{E}\left( \frac{S(E)}{k}\ - \beta E \right) \right\rbrack$

Продифференцировав $\frac{\partial}{\partial E}\left( \frac{S(E)}{k}\ - \beta E \right) = 0$ , получим термодинамическое определение температуры: $\frac{\partial S}{\partial E} = \frac{1}{T}$ . Как уже было в разделе про Лагрàнжа и Гамильтона с определением импульса, тут определение температуры тоже возникло из поиска экстремума. Мы нашли максимум, потому что – вогнутая функция ( выпуклая), реализовав принцип максимума энтропии. Это логично: наличие установившейся температуры – понятный признак термодинамического равновесия, где энтропия максимальна.

Вернемся к определению свободной энергии:

$- \beta F(\beta) = \ln Z = \sup_{E}\left( \frac{S(E)}{k}\ - \beta E \right) = \sup_{E}\left( - \beta \cdot E\ - \left( - \frac{S(E)}{k} \right) \right) = \sup_{E}\left( p \cdot E - f(E) \right)$

Теперь, когда функция $f(E) = - \frac{S(E)}{k}$ стала выпуклая, проявилось преобразование Лежандра (через sup). Сама лежандрова пара – это функция $\ln Z$ по переменной $- \beta$ и функция $- \frac{S}{k}$ по переменной .

Такая пара может показаться громоздкой, но на самом деле она скрывает красивую связь: мы показывали, что $\ln Z$ – это log-sum-exp, а $- \frac{S(E)}{k}$ – это $- \sum_{}^{}{p\ln p}$ . Итог: log-sum-exp и негэнтропия лежандрово сопряжены

Итог: преобразование Лежандра в статфизе порождает много полезных для статистики и ML идей

Статистика

Если задача тервера понять по параметрам модели, какие данные она генерирует, то задача статистики – по данным получить оценку параметров. Заметная часть статистики основана на преобразовании Лежандра

Энтропия, softmax, logsumexp

Вспомним раздел про статфиз (энтропия, Гиббс, свободная энергия). Тем, кто сталкивался со статистикой/ML, формулы в разделе про статфиз уже заспойлерили 3 вещи:

энтропия имеет вид $- \sum_{}^{}{p\ln p}$ , как энтропия Шеннона
распределение гиббса похоже на softmax с температурой
свободная энергия имеет вид log-sum-exp

Возьмем негэнтропию Шеннона на вероятностном симплексе. Рассмотрим дискретные вероятности (в непрерывном случае действия аналогичны, но с интегралами вместо сумм). Плюс договоримся использовать натуральный логарифм вместо двоичного:

$- H(p) = \sum_{i}^{}{p_{i}\ln p_{i}},\ \ p \in \Delta = \left\{ p:\ \ \ p_{i} \geq 0\ \ ,\ \sum_{i}^{}p_{i} = 1 \right\}$

Посчитаем ее градиент:

$\nabla\left( - H(p) \right) = \begin{bmatrix} \ln p_{1} + 1 & \ldots & \ln p_{n} + 1 \end{bmatrix} = \theta$

Градиент негэнтропии не имеет какого-то устоявшегося названия, но с точностью до константы – это логиты / логарифмические шансы: $\theta_{i} = \ln\frac{p_{i}}{p_{base}} = \ln p_{i} - \ln p_{base}$ , причем точное равенство при $p_{base} = \frac{1}{e}$ .

Посчитаем гессиан и проверим, что функция выпуклая:

$\nabla^{2}\left( - H(p) \right) = \begin{pmatrix} \frac{1}{p_{1}} & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \frac{1}{p_{n}} \end{pmatrix} \succ 0$

Гессиан негэнтропии работает с величинами, обратными вероятностям. По аналогии с лежандровой парой лагранжиан-гамильтониан в физике, и как мы выводили по теореме об обратной функции, можно предположить, что гессиан сопряженной функции как-то работает с прямыми вероятностями. Будет ли он формально обратным – не факт, надо проверять по теореме об обратной функции

Посчитаем преобразование Лежандра от негэнтропии:

$\psi^{*}(\theta) = \sup_{p \in \Delta}\left( \left\langle \theta,p \right\rangle - \sum_{i}^{}{p_{i}\ln p_{i}} \right)$

Это задача условной оптимизации на симплексе. Решать умеем с помощью функции Лагранжа из раздела про методы оптимизации:

$L = \sum_{i}^{}{p_{i}\theta_{i}} - \sum_{i}^{}{p_{i}\ln p_{i}} + \lambda\left( 1 - \sum_{i}^{}p_{i} \right),\ \ \frac{\partial L}{\partial p_{i}} = \theta_{i} - \ln p_{i} - 1 - \lambda = 0\ \ \Rightarrow \ \ p_{i} = e^{\theta_{i} - 1 - \lambda}$

Отдельно отметим, что это полностью соответствует определению преобразования Лежандра, т.к. множитель при $\lambda$ зануляется на всех из рассматриваемого пространства. Саму $\lambda$ подбираем из нормировки $\sum_{i}^{}p_{i} = 1$ :

$p_{i} = \frac{e^{\theta_{i}}}{\sum_{i}^{}e^{\theta_{i}}}\ \ \ \Rightarrow \ \ \ p = softmax\ \theta$

Подставим в $\psi^{*}$ :

$\psi^{*}(\theta) = \sum_{i}^{}{\theta_{i}p_{i}} - \sum_{i}^{}{p_{i}\ln p_{i}} = \sum_{i}^{}{p_{i}\theta_{i}} - \sum_{i}^{}{p_{i}\left( \theta_{i} - \ln{\sum_{i}^{}e^{\theta_{i}}} \right) = \sum_{i}^{}{p_{i}\ln{\sum_{i}^{}e^{\theta_{i}}}}} = \ln{\sum_{i}^{}e^{\theta_{i}}}$ $\left( - H(p) \right)^{*} = logsumexp(\theta)$ ВКонтакте Telegram Twitter

📊 Источник: Habr | Оригинал