WikiDer > Методы проксимального градиента для обучения

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

${ displaystyle 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 {где}} x_ {i} in mathbb {R} ^ {d} { text {and}} y_ {i} in mathbb {R}.}$

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

Соответствующий фон

Проксимальные градиентные методы применимы в самых разных сценариях решения выпуклая оптимизация проблемы формы

${ Displaystyle мин _ {х in { mathcal {H}}} F (x) + R (x),}$

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

${ Displaystyle 0 в partial (F + R) (х),}$

куда ${ displaystyle partial varphi}$ обозначает субдифференциальный действительной выпуклой функции ${ displaystyle varphi}$.

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

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

которая определена корректно из-за строгой выпуклости ${ displaystyle ell _ {2}}$ норма. Оператор близости можно рассматривать как обобщение проекция.^[1][3][4]Мы видим, что оператор близости важен, потому что ${ displaystyle x ^ {*}}$ сводит к минимуму проблему ${ Displaystyle мин _ {х in { mathcal {H}}} F (x) + R (x)}$ если и только если

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

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

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

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

Общий вид разложения Моро утверждает, что для любого ${ displaystyle x in { mathcal {X}}}$ и любой ${ displaystyle gamma> 0}$ который

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

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

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

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

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

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

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

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

куда ${ Displaystyle | ш | _ {0}}$ обозначает ${ displaystyle ell _ {0}}$ "норма", то есть количество ненулевых элементов вектора ${ displaystyle w}$. Редкие решения представляют особый интерес в теории обучения для интерпретируемости результатов: разреженное решение может идентифицировать небольшое количество важных факторов.^[5]

Решение для ${ displaystyle ell _ {1}}$ оператор близости

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

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

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

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

${ displaystyle { begin {align} u = operatorname {prox} _ {R} (x) iff & 0 in partial left (R (u) + { frac {1} {2}} | ux | _ {2} ^ {2} right) iff & 0 in partial R (u) + ux iff & x-u in partial R (u). end {выравнивается} }}$

За ${ Displaystyle R (ш) = | ш | _ {1}}$ легко вычислить ${ displaystyle partial R (w)}$: the ${ displaystyle i}$-я запись ${ displaystyle partial R (w)}$ точно

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

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

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

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

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

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

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

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

${ displaystyle w ^ {k + 1} = S _ { gamma} left (w ^ {k} - gamma nabla F left (w ^ {k} right) right).}$

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

Сходимость этой схемы с неподвижной точкой хорошо изучена в литературе.^[1][6] и гарантируется при соответствующем выборе размера шага ${ displaystyle gamma}$ и функция потерь (например, квадрат потерь, взятый здесь). Ускоренные методы были введены Нестеровым в 1983 году, которые улучшают скорость сходимости при определенных предположениях регулярности на ${ displaystyle F}$.^[7] Такие методы широко изучались в предыдущие годы.^[8]Для более общих задач обучения, где оператор близости не может быть вычислен явно для некоторого члена регуляризации ${ displaystyle R}$такие схемы с фиксированной точкой по-прежнему могут быть реализованы с использованием аппроксимации как градиента, так и оператора близости.^[4][9]

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

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

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

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

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

можно разрешить переменный размер шага ${ displaystyle gamma _ {k}}$ вместо постоянного ${ displaystyle gamma}$. В литературе предлагалось множество схем адаптивного размера шага.^{[1][4][11][12]} Применение этих схем^[2][13] предполагают, что они могут предложить значительное улучшение количества итераций, необходимых для сходимости с фиксированной точкой.

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

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

${ displaystyle 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} верно),}$

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

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

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

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

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

${ Displaystyle R (ш) = сумма _ {г = 1} ^ {G} | ш_ {г} | _ {2},}$

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

${ displaystyle { 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 {case}}}$

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

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

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

В отличие от проблемы группового лассо, где объекты сгруппированы в непересекающиеся блоки, может быть случай, когда сгруппированные объекты перекрываются или имеют вложенную структуру. Такие обобщения группового лассо рассматривались в различных контекстах.^{[16][17][18][19]} Для перекрывающихся групп один общий подход известен как латентная группа лассо который вводит скрытые переменные для учета перекрытия.^[20][21] Структура вложенных групп изучается в предсказание иерархической структуры и с ориентированные ациклические графы.^[18]

Смотрите также

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

Рекомендации