Проксимальные градиентные методы обучения

Методы проксимального градиента (прямое обратное расщепление) для обучения — это область исследований в области теории оптимизации и статистического обучения , которая изучает алгоритмы для общего класса задач выпуклой регуляризации , где штраф за регуляризацию может быть не дифференцируемым . Одним из таких примеров является $\ell _{1}$ регуляризация (также известная как Лассо) формы

$\min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\lambda \|w\|_{1},\quad {\text{ where }}x_{i}\in \mathbb {R} ^{d}{\text{ and }}y_{i}\in \mathbb {R} .$

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

Соответствующая информация

Методы проксимального градиента применимы в самых разных сценариях решения задач выпуклой оптимизации вида

$\min _{x\in {\mathcal {H}}}F(x)+R(x),$

где $F$ является выпуклым и дифференцируемым с липшицевым непрерывным градиентом , $R$ — выпуклая , полунепрерывная снизу функция, которая, возможно, недифференцируема, и ${\mathcal {H}}$ — некоторое множество, обычно гильбертово пространство . Обычный критерий $x$ сводит к минимуму $F(x)+R(x)$ тогда и только тогда, когда $\nabla (F+R)(x)=0$ в выпуклой дифференцируемой ситуации теперь заменяется на

$0\in \partial (F+R)(x),$

где $\partial \varphi$ обозначает субдифференциал вещественной выпуклой функции $\varphi$.

Дана выпуклая функция $\varphi :{\mathcal {H}}\to \mathbb {R}$ важным оператором, который следует учитывать, является его проксимальный оператор $\operatorname {prox} _{\varphi }:{\mathcal {H}}\to {\mathcal {H}}$ определяется

$\operatorname {prox} _{\varphi }(u)=\operatorname {arg} \min _{x\in {\mathcal {H}}}\varphi (x)+{\frac {1}{2}}\|u-x\|_{2}^{2},$

которое корректно определено из-за строгой выпуклости $\ell _{2}$ норма. Проксимальный оператор можно рассматривать как обобщение проекции . Мы видим, что оператор близости важен, потому что $x^{*}$ это минимизация проблемы $\min _{x\in {\mathcal {H}}}F(x)+R(x)$ тогда и только тогда, когда

$x^{*}=\operatorname {prox} _{\gamma R}\left(x^{*}-\gamma \nabla F(x^{*})\right),$ где $\gamma >0$ любое положительное действительное число.

Разложение Моро

Одним из важных методов, связанных с методами проксимального градиента, является разложение Моро, которое разлагает тождественный оператор как сумму двух операторов близости. А именно, пусть $\varphi :{\mathcal {X}}\to \mathbb {R}$ быть полунепрерывной снизу выпуклой функцией в векторном пространстве. ${\mathcal {X}}$. Определим его сопряженное по Фенхелю $\varphi ^{*}:{\mathcal {X}}\to \mathbb {R}$ быть функцией

$\varphi ^{*}(u):=\sup _{x\in {\mathcal {X}}}\langle x,u\rangle -\varphi (x).$

Общая форма разложения Моро гласит, что для любого $x\in {\mathcal {X}}$ и любой $\gamma >0$ что

$x=\operatorname {prox} _{\gamma \varphi }(x)+\gamma \operatorname {prox} _{\varphi ^{*}/\gamma }(x/\gamma ),$

для чего $\gamma =1$ подразумевает, что $x=\operatorname {prox} _{\varphi }(x)+\operatorname {prox} _{\varphi ^{*}}(x)$. Разложение Моро можно рассматривать как обобщение обычного ортогонального разложения векторного пространства, аналогично тому факту, что операторы близости являются обобщениями проекций.

В некоторых ситуациях может оказаться проще вычислить оператор близости для сопряженного числа. $\varphi ^{*}$ вместо функции $\varphi$, поэтому можно применить разложение Моро. Это относится к групповому лассо .

Регуляризация Лассо

Рассмотрим регуляризованную задачу минимизации эмпирического риска с квадратичными потерями и с $\ell _{1}$ норма как штраф за регуляризацию:

$\min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\lambda \|w\|_{1},$

где $x_{i}\in \mathbb {R} ^{d}{\text{ and }}y_{i}\in \mathbb {R} .$ $\ell _{1}$ Проблему регуляризации иногда называют лассо ( оператор наименьшего абсолютного сжатия и выбора ). Такой $\ell _{1}$ Проблемы регуляризации интересны тем, что они влекут за собой разреженные решения, т. е. решения $w$ задача минимизации имеет относительно мало ненулевых компонентов. Лассо можно рассматривать как выпуклую релаксацию невыпуклой задачи.

$\min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\lambda \|w\|_{0},$

где $\|w\|_{0}$ обозначает $\ell _{0}$ «норма», то есть количество ненулевых элементов вектора. $w$. Разреженные решения представляют особый интерес в теории обучения с точки зрения интерпретируемости результатов: разреженное решение может выявить небольшое количество важных факторов.

Решение _{L 1} оператора близости

Для простоты ограничимся проблемой, где $\lambda =1$. Чтобы решить проблему

$\min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\|w\|_{1},$

мы рассматриваем нашу целевую функцию в двух частях: выпуклый дифференцируемый член $F(w)={\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}$ и выпуклая функция $R(w)=\|w\|_{1}$. Обратите внимание, что $R$ не является строго выпуклым.

Вычислим оператор близости для $R(w)$. Сначала найдем альтернативную характеристику оператора близости $\operatorname {prox} _{R}(x)$ следующее:

${\begin{aligned}u=\operatorname {prox} _{R}(x)\iff &0\in \partial \left(R(u)+{\frac {1}{2}}\|u-x\|_{2}^{2}\right)\\\iff &0\in \partial R(u)+u-x\\\iff &x-u\in \partial R(u).\end{aligned}}$

Для $R(w)=\|w\|_{1}$ это легко вычислить $\partial R(w)$: $i$ая запись $\partial R(w)$ это именно

$\partial |w_{i}|={\begin{cases}1,&w_{i}>0\\-1,&w_{i}<0\\\left[-1,1\right],&w_{i}=0.\end{cases}}$

Используя приведенную выше перехарактеризацию оператора близости, для выбора $R(w)=\|w\|_{1}$ и $\gamma >0$ у нас есть это $\operatorname {prox} _{\gamma R}(x)$ определяется по записи

$\left(\operatorname {prox} _{\gamma R}(x)\right)_{i}={\begin{cases}x_{i}-\gamma ,&x_{i}>\gamma \\0,&|x_{i}|\leq \gamma \\x_{i}+\gamma ,&x_{i}<-\gamma ,\end{cases}}$

который известен как мягкого порога оператор $S_{\gamma }(x)=\operatorname {prox} _{\gamma \|\cdot \|_{1}}(x)$.

Итерационные схемы с фиксированной запятой

Чтобы окончательно решить проблему лассо, мы рассмотрим уравнение неподвижной точки, показанное ранее:

$x^{*}=\operatorname {prox} _{\gamma R}\left(x^{*}-\gamma \nabla F(x^{*})\right).$

Учитывая, что мы явно вычислили форму оператора близости, мы можем определить стандартную процедуру итерации с фиксированной точкой. А именно, исправить некоторые первоначальные $w^{0}\in \mathbb {R} ^{d}$и для $k=1,2,\ldots$ определять

$w^{k+1}=S_{\gamma }\left(w^{k}-\gamma \nabla F\left(w^{k}\right)\right).$

Обратите внимание здесь на эффективный компромисс между эмпирической ошибкой $F(w)$ и штраф за регуляризацию $R(w)$. Этот метод с фиксированной точкой разделил эффект двух разных выпуклых функций, которые составляют целевую функцию, на шаг градиентного спуска ( $w^{k}-\gamma \nabla F\left(w^{k}\right)$) и шаг мягкой установки порога (через $S_{\gamma }$).

Сходимость этой схемы с неподвижной точкой хорошо изучена в литературе. и гарантируется при соответствующем выборе размера шага $\gamma$ и функция потерь (например, взятая здесь квадратичная потеря). Ускоренные методы были предложены Нестеровым в 1983 году, которые улучшают скорость сходимости при определенных предположениях о регулярности $F$. Подобные методы широко изучались в предыдущие годы. Для более общих задач обучения, когда оператор близости не может быть вычислен явно для некоторого члена регуляризации. $R$, такие схемы с фиксированной точкой все еще могут быть реализованы с использованием аппроксимаций как градиента, так и оператора близости.

Практические соображения

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

Адаптивный размер шага

В итерационной схеме с фиксированной точкой

$w^{k+1}=\operatorname {prox} _{\gamma R}\left(w^{k}-\gamma \nabla F\left(w^{k}\right)\right),$

можно разрешить переменный размер шага $\gamma _{k}$ вместо константы $\gamma$. В литературе было предложено множество схем адаптивного размера шага. Применение этих схем предполагают, что они могут обеспечить существенное увеличение количества итераций, необходимых для сходимости с фиксированной точкой.

Эластичная сеть (регуляризация смешанной нормы)

Эластичная чистая регуляризация предлагает альтернативу чистой $\ell _{1}$ регуляризация. Проблема лассо ( $\ell _{1}$) регуляризация предполагает штрафной срок $R(w)=\|w\|_{1}$, который не является строго выпуклым. Следовательно, решения $\min _{w}F(w)+R(w),$ где $F$ — некоторая эмпирическая функция потерь, не обязательно должна быть уникальной. Этого часто можно избежать путем включения дополнительного строго выпуклого члена, такого как $\ell _{2}$ Штраф за регуляризацию нормы. Например, можно рассмотреть задачу

$\min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\lambda \left((1-\mu )\|w\|_{1}+\mu \|w\|_{2}^{2}\right),$

где $x_{i}\in \mathbb {R} ^{d}{\text{ and }}y_{i}\in \mathbb {R} .$Для $0<\mu \leq 1$ срок наказания $\lambda \left((1-\mu )\|w\|_{1}+\mu \|w\|_{2}^{2}\right)$ теперь строго выпукла, и, следовательно, задача минимизации теперь допускает единственное решение. Замечено, что при достаточно малых $\mu >0$, дополнительный срок наказания $\mu \|w\|_{2}^{2}$ действует как предобуславливатель и может существенно улучшить сходимость, не оказывая при этом отрицательного влияния на разреженность решений.

Использование структуры группы

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

Групповое лассо

Групповое лассо — это обобщение метода лассо , когда объекты группируются в непересекающиеся блоки. Предположим, что объекты сгруппированы в блоки $\{w_{1},\ldots ,w_{G}\}$. Здесь в качестве штрафа за регуляризацию мы принимаем

$R(w)=\sum _{g=1}^{G}\|w_{g}\|_{2},$

что представляет собой сумму $\ell _{2}$ норма соответствующих векторов признаков для разных групп. Аналогичный анализ оператора близости, описанный выше, можно использовать для вычисления оператора близости для этого штрафа. Там, где штраф за лассо имеет оператор близости, который устанавливает мягкое пороговое значение для каждого отдельного компонента, оператор близости для группового лассо является мягким пороговым значением для каждой группы. Для группы $w_{g}$ у нас есть оператор близости $\lambda \gamma \left(\sum _{g=1}^{G}\|w_{g}\|_{2}\right)$ дается

${\widetilde {S}}_{\lambda \gamma }(w_{g})={\begin{cases}w_{g}-\lambda \gamma {\frac {w_{g}}{\|w_{g}\|_{2}}},&\|w_{g}\|_{2}>\lambda \gamma \\0,&\|w_{g}\|_{2}\leq \lambda \gamma \end{cases}}$

где $w_{g}$ это $g$ая группа.

В отличие от лассо, вывод оператора близости для группового лассо основан на разложении Моро . Здесь оператор близости сопряженного группового аркана становится проекцией на шар двойственной нормы .

Другие структуры группы

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

См. также

• Выпуклый анализ
• Метод проксимального градиента
• Регуляризация
• Статистическая теория обучения