12.2. Выпуклость¶
Выпуклость играет ключевую роль в разработке алгоритмов оптимизации. Это связано прежде всего с тем, что анализ и тестирование алгоритмов в таком контексте значительно проще. Иными словами, если алгоритм работает плохо даже в выпуклом случае, обычно не стоит ожидать хороших результатов в более общих ситуациях. Кроме того, хотя задачи оптимизации в глубоком обучении, как правило, невыпуклы, в окрестности локальных минимумов они часто обладают свойствами, характерными для выпуклых задач. Это может приводить к появлению новых интересных вариантов оптимизации, таких как (Izmailov et al., 2018).
%matplotlib inline
import numpy as np
import torch
from mpl_toolkits import mplot3d
from d2l import torch as d2l
12.2.1. Определения¶
Прежде чем переходить к выпуклому анализу, нам необходимо определить выпуклые множества и выпуклые функции. Они позволяют получить математические инструменты, которые широко применяются в машинном обучении.
12.2.1.1. Выпуклые множества¶
Множества лежат в основе выпуклости. Проще говоря, множество \(\mathcal{X}\) в векторном пространстве является выпуклым, если для любых \(a, b \in \mathcal{X}\) отрезок, соединяющий \(a\) и \(b\), также принадлежит \(\mathcal{X}\). В математических терминах это означает, что для всех \(\lambda \in [0, 1]\) выполняется
Это звучит несколько абстрактно. Рассмотрим Fig. 12.2.1. Первое множество не является выпуклым, поскольку существуют отрезки, не содержащиеся в нём. Два других множества таких проблем не имеют.
Fig. 12.2.1 Первое множество невыпукло, а два других — выпуклы.¶
Одни лишь определения не особенно полезны, если с ними нельзя ничего сделать. В данном случае мы можем рассмотреть пересечения, как показано на рисунке Fig. 12.2.2. Предположим, что \(\mathcal{X}\) и \(\mathcal{Y}\) — выпуклые множества. Тогда \(\mathcal{X} \cap \mathcal{Y}\) также является выпуклым. Чтобы убедиться в этом, рассмотрим любые \(a, b \in \mathcal{X} \cap \mathcal{Y}\). Поскольку \(\mathcal{X}\) и \(\mathcal{Y}\) выпуклы, отрезки, соединяющие \(a\) и \(b\), содержатся как в \(\mathcal{X}\), так и в \(\mathcal{Y}\). Следовательно, они должны содержаться и в \(\mathcal{X} \cap \mathcal{Y}\), что и доказывает нашу теорему.
Fig. 12.2.2 Пересечение двух выпуклых множеств выпукло.¶
Мы можем усилить этот результат с минимальными усилиями: пересечение выпуклых множеств \(\mathcal{X}_i\) является выпуклым \(\cap_{i} \mathcal{X}_i\). Чтобы показать, что обратное утверждение неверно, рассмотрим два непересекающихся множества \(\mathcal{X} \cap \mathcal{Y} = \emptyset\). Теперь выберем \(a \in \mathcal{X}\) и \(b \in \mathcal{Y}\). Отрезок, соединяющий \(a\) и \(b\), лежащий в Fig. 12.2.3, должен содержать часть, которая не принадлежит ни \(\mathcal{X}\), ни \(\mathcal{Y}\), поскольку мы предположили, что \(\mathcal{X} \cap \mathcal{Y} = \emptyset\). Следовательно, этот отрезок не принадлежит и \(\mathcal{X} \cup \mathcal{Y}\), что доказывает: в общем случае объединение выпуклых множеств не обязательно является выпуклым.
Fig. 12.2.3 Объединение двух выпуклых множеств не обязательно является выпуклым.¶
Как правило, задачи глубокого обучения формулируются на выпуклых множествах. Например, \(\mathbb{R}^d\), множество \(d\)-мерных векторов действительных чисел, является выпуклым множеством (ведь отрезок, соединяющий любые две точки в \(\mathbb{R}^d\), целиком лежит в \(\mathbb{R}^d\)). В некоторых случаях мы работаем с переменными ограниченной длины, такими как шары радиуса \(r\), определяемые формулой \(\{\mathbf{x} | \mathbf{x} \in \mathbb{R}^d \textrm{ and } \|\mathbf{x}\| \leq r\}\).
12.2.1.2. Выпуклые функции¶
Теперь, когда у нас есть выпуклые множества, мы можем ввести выпуклые функции \(f\). Для заданного выпуклого множества \(\mathcal{X}\) функция \(f: \mathcal{X} \to \mathbb{R}\) является выпуклой, если для любых \(x, x' \in \mathcal{X}\) и любых \(\lambda \in [0, 1]\) выполняется
Чтобы проиллюстрировать это, построим графики нескольких функций и проверим, какие из них удовлетворяют условию. Ниже мы определим несколько функций, как выпуклых, так и невыпуклых.
f = lambda x: 0.5 * x**2 # Convex
g = lambda x: torch.cos(np.pi * x) # Nonconvex
h = lambda x: torch.exp(0.5 * x) # Convex
x, segment = torch.arange(-2, 2, 0.01), torch.tensor([-1.5, 1])
d2l.use_svg_display()
_, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
for ax, func in zip(axes, [f, g, h]):
d2l.plot([x, segment], [func(x), func(segment)], axes=ax)
Как и ожидалось, функция косинуса является невыпуклой, тогда как парабола и экспоненциальная функция — выпуклыми. Обратите внимание, что требование выпуклости множества \(\mathcal{X}\) необходимо для осмысленности условия. В противном случае результат вычисления \(f(\lambda x + (1-\lambda) x')\) может быть не определён.
12.2.1.3. Неравенство Йенсена¶
Для выпуклой функции \(f\) одним из наиболее полезных математических инструментов является неравенство Йенсена. По сути, оно представляет собой обобщение определения выпуклости:
где \(\alpha_i\) — неотрицательные действительные числа, такие что \(\sum_i \alpha_i = 1\), а \(X\) — случайная величина. Иными словами, математическое ожидание выпуклой функции не меньше, чем значение выпуклой функции от математического ожидания, причём последнее выражение обычно проще. Чтобы доказать первое неравенство, мы многократно применяем определение выпуклости к одному слагаемому в сумме за раз.
Одним из распространённых применений неравенства Йенсена является оценка более сложного выражения более простым. Например, его применение может касаться логарифма правдоподобия частично наблюдаемых случайных величин. То есть мы используем
поскольку \(\int P(Y) P(X \mid Y) dY = P(X)\). Это можно использовать в вариационных методах. Здесь \(Y\) — это, как правило, ненаблюдаемая случайная величина, \(P(Y)\) — наилучшее предположение о её распределении, а \(P(X)\) — распределение, из которого \(Y\) проинтегрировано. Например, в кластеризации \(Y\) может быть меткой кластера, а \(P(X \mid Y)\) — порождающей моделью при использовании меток кластеров.
12.2.2. Свойства¶
Выпуклые функции обладают многими полезными свойствами. Ниже мы опишем несколько из них, которые часто используются на практике.
12.2.2.1. Локальные минимумы являются глобальными минимумами¶
Прежде всего, локальные минимумы выпуклых функций являются также и глобальными минимумами. Мы можем доказать это от противного следующим образом.
Рассмотрим выпуклую функцию \(f\), заданную на выпуклом множестве \(\mathcal{X}\). Предположим, что \(x^{\ast} \in \mathcal{X}\) является локальным минимумом: существует малое положительное значение \(p\) такое, что для всех \(x \in \mathcal{X}\), удовлетворяющих условию \(0 < |x - x^{\ast}| \leq p\), выполняется неравенство \(f(x^{\ast}) < f(x)\).
Предположим, что локальный минимум \(x^{\ast}\) не является глобальным минимумом \(f\): существует \(x' \in \mathcal{X}\), для которого \(f(x') < f(x^{\ast})\). Также существует \(\lambda \in [0, 1)\) такой, что \(\lambda = 1 - \frac{p}{|x^{\ast} - x'|}\), и при этом \(0 < |\lambda x^{\ast} + (1-\lambda) x' - x^{\ast}| \leq p\).
Однако, согласно определению выпуклых функций, получаем
что противоречит нашему утверждению о том, что \(x^{\ast}\) является локальным минимумом. Следовательно, не существует \(x' \in \mathcal{X}\), для которого выполняется \(f(x') < f(x^{\ast})\). Локальный минимум \(x^{\ast}\) является также глобальным минимумом.
Например, выпуклая функция \(f(x) = (x-1)^2\) имеет локальный минимум в точке \(x=1\), который также является глобальным минимумом.
f = lambda x: (x - 1) ** 2
d2l.set_figsize()
d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')
Тот факт, что локальные минимумы выпуклых функций являются также и глобальными минимумами, очень удобен. Это означает, что при минимизации функций мы не можем «застрять». Однако следует отметить, что это не означает, что не может существовать более одного глобального минимума или что он может вовсе отсутствовать. Например, функция \(f(x) = \mathrm{max}(|x|-1, 0)\) достигает своего минимального значения на интервале \([-1, 1]\). Напротив, функция \(f(x) = \exp(x)\) не достигает минимального значения на \(\mathbb{R}\): при \(x \to -\infty\) она асимптотически стремится к \(0\), но не существует такого \(x\), для которого \(f(x) = 0\).
12.2.2.2. Множества ниже выпуклых функций выпуклы¶
Выпуклые множества удобно определять через нижние множества выпуклых функций. Конкретно, пусть задана выпуклая функция \(f\), определённая на выпуклом множестве \(\mathcal{X}\), тогда любое нижнее множество
выпуклый.
Докажем это кратко. Напомним, что для любых \(x, x' \in \mathcal{S}_b\) необходимо показать, что \(\lambda x + (1-\lambda) x' \in \mathcal{S}_b\) при условии \(\lambda \in [0, 1]\). Поскольку \(f(x) \leq b\) и \(f(x') \leq b\), из определения выпуклости получаем
12.2.2.3. Выпуклость и вторые производные¶
Если вторая производная функции \(f: \mathbb{R}^n \rightarrow \mathbb{R}\) существует, проверить, является ли \(f\) выпуклой, очень просто. Нам нужно лишь убедиться, что матрица Гессе функции \(f\) является положительно полуопределённой: \(\nabla^2f \succeq 0\), то есть, обозначая матрицу Гессе \(\nabla^2f\) через \(\mathbf{H}\), выполняется условие \(\mathbf{x}^\top \mathbf{H} \mathbf{x} \geq 0\) для всех \(\mathbf{x} \in \mathbb{R}^n\). Например, функция \(f(\mathbf{x}) = \frac{1}{2} \|\mathbf{x}\|^2\) выпукла, поскольку \(\nabla^2 f = \mathbf{1}\), то есть её матрица Гессе — единичная матрица.
Формально дважды дифференцируемая одномерная функция \(f: \mathbb{R} \rightarrow \mathbb{R}\) выпукла тогда и только тогда, когда её вторая производная \(f'' \geq 0\). Для любой дважды дифференцируемой многомерной функции \(f: \mathbb{R}^{n} \rightarrow \mathbb{R}\) она выпукла тогда и только тогда, когда её гессиан \(\nabla^2f \succeq 0\).
Сначала докажем одномерный случай. Чтобы показать, что выпуклость \(f\) влечёт \(f'' \geq 0\), воспользуемся тем, что
Поскольку вторая производная определяется через предел конечных разностей, следует, что
Чтобы показать, что \(f'' \geq 0\) влечёт выпуклость \(f\), мы воспользуемся тем фактом, что \(f'' \geq 0\) означает монотонное неубывание функции \(f'\). Пусть \(a < x < b\) — три точки в \(\mathbb{R}\), такие что \(x = (1-\lambda)a + \lambda b\) и \(\lambda \in (0, 1)\). Согласно теореме о среднем, существуют \(\alpha \in [a, x]\) и \(\beta \in [x, b]\), такие что
В силу монотонности \(f'(\beta) \geq f'(\alpha)\), следовательно
Поскольку \(x = (1-\lambda)a + \lambda b\), получаем
тем самым доказывая выпуклость.
Во-вторых, перед доказательством многомерного случая нам понадобится лемма: \(f: \mathbb{R}^n \rightarrow \mathbb{R}\) выпукла тогда и только тогда, когда для всех \(\mathbf{x}, \mathbf{y} \in \mathbb{R}^n\)
выпуклый.
Чтобы доказать, что выпуклость \(f\) влечёт выпуклость \(g\), мы можем показать, что для всех \(a, b, \lambda \in [0, 1]\) (следовательно, \(0 \leq \lambda a + (1-\lambda) b \leq 1\))
Чтобы доказать обратное, мы можем показать, что для всех \(\lambda \in [0, 1]\)
Наконец, используя лемму выше и результат одномерного случая, многомерный случай можно доказать следующим образом. Многомерная функция \(f: \mathbb{R}^n \rightarrow \mathbb{R}\) выпукла тогда и только тогда, когда для всех \(\mathbf{x}, \mathbf{y} \in \mathbb{R}^n\) \(g(z) \stackrel{\textrm{def}}{=} f(z \mathbf{x} + (1-z) \mathbf{y})\), где \(z \in [0,1]\), она выпукла. Согласно одномерному случаю, это выполняется тогда и только тогда, когда \(g'' = (\mathbf{x} - \mathbf{y})^\top \mathbf{H}(\mathbf{x} - \mathbf{y}) \geq 0\) (\(\mathbf{H} \stackrel{\textrm{def}}{=} \nabla^2f\)) для всех \(\mathbf{x}, \mathbf{y} \in \mathbb{R}^n\), что эквивалентно условию \(\mathbf{H} \succeq 0\) согласно определению положительно полуопределенных матриц.
12.2.3. Ограничения¶
Одним из замечательных свойств выпуклой оптимизации является то, что она позволяет эффективно обрабатывать ограничения. То есть она позволяет решать задачи оптимизации с ограничениями вида:
где \(f\) — это целевая функция, а функции \(c_i\) — функции ограничений. Чтобы понять, что это означает, рассмотрим случай, когда \(c_1(\mathbf{x}) = \|\mathbf{x}\|_2 - 1\). В этом случае параметры \(\mathbf{x}\) ограничены единичным шаром. Если второе ограничение имеет вид \(c_2(\mathbf{x}) = \mathbf{v}^\top \mathbf{x} + b\), то это соответствует тому, что все \(\mathbf{x}\) лежат в полупространстве. Одновременное выполнение обоих ограничений эквивалентно выбору сечения шара.
12.2.3.1. Лагранжиан¶
В общем случае решение задачи оптимизации с ограничениями является сложной задачей. Один из способов её решения основан на довольно простой физической интуиции. Представьте себе шар внутри коробки. Шар скатится в самую нижнюю точку, где силы тяжести будут уравновешены силами, которые стенки коробки могут оказывать на шар. Иными словами, градиент целевой функции (т.е. сила тяжести) будет компенсирован градиентом функции ограничений (шар должен оставаться внутри коробки благодаря тому, что стенки «отталкивают» его). Обратите внимание, что некоторые ограничения могут быть неактивными: стенки, которых не касается шар, не смогут оказывать никакую силу на шар.
Пропуская вывод лагранжиана \(L\), вышеизложенные рассуждения можно выразить в виде следующей задачи оптимизации седловой точки:
Здесь переменные \(\alpha_i\) (\(i=1,\ldots,n\)) — это так называемые множители Лагранжа, которые обеспечивают соблюдение ограничений. Они выбираются достаточно большими, чтобы гарантировать выполнение условия \(c_i(\mathbf{x}) \leq 0\) для всех \(i\). Например, для любого \(\mathbf{x}\), где \(c_i(\mathbf{x}) < 0\) выполняется естественным образом, мы бы выбрали \(\alpha_i = 0\). Кроме того, это задача оптимизации седловой точки, в которой необходимо максимизировать \(L\) по всем \(\alpha_i\) и одновременно минимизировать её по \(\mathbf{x}\). Существует обширная литература, объясняющая, как получить функцию \(L(\mathbf{x}, \alpha_1, \ldots, \alpha_n)\). Для наших целей достаточно знать, что седловая точка функции \(L\) соответствует оптимальному решению исходной задачи оптимизации с ограничениями.
12.2.3.2. Штрафы¶
Один из способов приближённого решения задач условной оптимизации — адаптация лагранжиана \(L\). Вместо того чтобы удовлетворять \(c_i(\mathbf{x}) \leq 0\), мы просто добавляем \(\alpha_i c_i(\mathbf{x})\) к целевой функции \(f(x)\). Это гарантирует, что ограничения не будут нарушены слишком сильно.
На самом деле, мы использовали этот приём всё время. Рассмотрим затухание весов в Section 3.7. В нём мы добавляем \(\frac{\lambda}{2} \|\mathbf{w}\|^2\) к целевой функции, чтобы гарантировать, что \(\mathbf{w}\) не станет слишком большим. С точки зрения задачи условной оптимизации можно увидеть, что это обеспечит выполнение условия \(\|\mathbf{w}\|^2 - r^2 \leq 0\) для некоторого радиуса \(r\). Регулируя значение \(\lambda\), мы можем изменять размер \(\mathbf{w}\).
В целом, добавление штрафов — это хороший способ обеспечения приближенного выполнения ограничений. На практике это оказывается гораздо более устойчивым, чем точное выполнение. Кроме того, для невыпуклых задач многие свойства, делающие точный подход столь привлекательным в выпуклом случае (например, оптимальность), больше не выполняются.
12.2.3.3. Проекции¶
Альтернативной стратегией удовлетворения ограничений служат проекции. Ранее мы уже встречались с ними, например, при рассмотрении обрезки градиента в Section 9.5. Там мы обеспечивали, чтобы длина градиента не превышала \(\theta\), с помощью
Оказывается, это проекция \(\mathbf{g}\) на шар радиуса \(\theta\). Более общо, проекция на выпуклое множество \(\mathcal{X}\) определяется как
который является ближайшей точкой в \(\mathcal{X}\) к \(\mathbf{x}\).
Fig. 12.2.4 Выпуклые проекции¶
Математическое определение проекций может показаться несколько абстрактным. Fig. 12.2.4 объясняет это несколько более наглядно. На рисунке изображены два выпуклых множества: круг и ромб. Точки, находящиеся внутри обоих множеств (желтые), остаются неизменными при проецировании. Точки, лежащие вне обоих множеств (черные), проецируются на точки внутри множеств (красные), которые являются ближайшими к исходным точкам (черным). Хотя для \(\ell_2\) шаров направление сохраняется, в общем случае это не обязательно, что можно увидеть на примере ромба.
Одним из применений выпуклых проекций является вычисление разреженных векторов весов. В этом случае мы проецируем векторы весов на \(\ell_1\) шар, который является обобщением случая с ромбом из Fig. 12.2.4.
12.2.4. Итоги¶
В контексте глубокого обучения основная цель выпуклых функций заключается в том, чтобы мотивировать алгоритмы оптимизации и помочь нам понять их устройство в деталях. В дальнейшем мы увидим, как соответствующим образом выводятся градиентный спуск и стохастический градиентный спуск.
Пересечение выпуклых множеств является выпуклым. Объединение — нет.
Математическое ожидание выпуклой функции не меньше, чем значение выпуклой функции от математического ожидания (неравенство Йенсена).
Функция, дважды дифференцируемая, является выпуклой тогда и только тогда, когда её гессиан (матрица вторых производных) является положительно полуопределённой.
Выпуклые ограничения можно добавить с помощью лагранжиана. На практике их можно просто добавить в виде штрафа к целевой функции.
Проекции отображаются в точки выпуклого множества, ближайшие к исходным точкам.
12.2.5. Упражнения¶
Предположим, что мы хотим проверить выпуклость множества, проведя все отрезки между точками внутри этого множества и убедившись, что они полностью лежат в нём.
Докажите, что достаточно проверять только точки на границе.
Докажите, что достаточно проверить только вершины множества.
Обозначим через \(\mathcal{B}_p[r] \stackrel{\textrm{def}}{=} \{\mathbf{x} | \mathbf{x} \in \mathbb{R}^d \textrm{ and } \|\mathbf{x}\|_p \leq r\}\) шар радиуса \(r\) в норме \(p\). Докажите, что \(\mathcal{B}_p[r]\) выпукло для всех \(p \geq 1\).
Для выпуклых функций \(f\) и \(g\) покажите, что \(\mathrm{max}(f, g)\) также выпукла. Докажите, что \(\mathrm{min}(f, g)\) не является выпуклой.
Докажите, что нормализация функции софтмакс выпукла. Более конкретно, докажите выпуклость \(f(x) = \log \sum_i \exp(x_i)\).
Докажите, что линейные подпространства, т. е. \(\mathcal{X} = \{\mathbf{x} | \mathbf{W} \mathbf{x} = \mathbf{b}\}\), являются выпуклыми множествами.
Докажите, что в случае линейных подпространств с \(\mathbf{b} = \mathbf{0}\) проекция \(\textrm{Proj}_\mathcal{X}\) может быть записана в виде \(\mathbf{M} \mathbf{x}\) для некоторой матрицы \(\mathbf{M}\).
Покажите, что для дважды дифференцируемых выпуклых функций \(f\) можно записать \(f(x + \epsilon) = f(x) + \epsilon f'(x) + \frac{1}{2} \epsilon^2 f''(x + \xi)\) для некоторого \(\xi \in [0, \epsilon]\).
Рассмотрим выпуклое множество \(\mathcal{X}\) и два вектора \(\mathbf{x}\) и \(\mathbf{y}\). Докажите, что проекции не увеличивают расстояния, то есть \(\|\mathbf{x} - \mathbf{y}\| \geq \|\textrm{Proj}_\mathcal{X}(\mathbf{x}) - \textrm{Proj}_\mathcal{X}(\mathbf{y})\|\).