Регуляризация структурированной разреженности

Регуляризация структурированной разреженности это класс методов и область исследований в теория статистического обучения, которые расширяют и обобщают методы обучения регуляризации разреженности.^[1] И методы регуляризации разреженности, и структурированной разреженности стремятся использовать предположение, что выходная переменная ${ displaystyle Y}$ (т.е. ответ, или зависимая переменная ), который нужно изучить, можно описать уменьшенным числом переменных во входном пространстве ${ displaystyle X}$ (т.е. домен, пространство Особенности или же объясняющие переменные ). Методы регуляризации разреженности сосредоточьтесь на выборе входных переменных, которые лучше всего описывают выход. Методы регуляризации структурированной разреженности обобщать и расширять методы регуляризации разреженности, обеспечивая оптимальный выбор структур, таких как группы или сети входных переменных в ${ displaystyle X}$ .^[2]^[3]

Общей мотивацией для использования методов структурированной разреженности являются интерпретируемость модели, многомерное обучение (где размерность ${ displaystyle X}$ может быть больше, чем количество наблюдений ${ displaystyle n}$ ) и уменьшение вычислительная сложность.^[4] Более того, методы структурированной разреженности позволяют включать предварительные предположения о структуре входных переменных, таких как перекрывающиеся группы,^[2] неперекрывающиеся группы и ациклические графы.^[3] Примеры использования методов структурированной разреженности включают распознавание лиц,^[5] магнитно-резонансное изображение (МРТ) обработка,^[6] социолингвистический анализ обработки естественного языка,^[7] и анализ генетической экспрессии при раке груди.^[8]

Определение и связанные понятия

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

Рассмотрим линейное ядро упорядоченный минимизация эмпирического риска проблема с функцией потерь ${ Displaystyle V (у_ {я}, е (х))}$ и ${ displaystyle ell _ {0}}$ «норма» как штраф за регуляризацию:

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

куда ${ Displaystyle х, ш в mathbb {R ^ {d}}}$ , и ${ Displaystyle | ш | _ {0}}$ обозначает ${ displaystyle ell _ {0}}$ "норма", определяемая как количество ненулевых элементов вектора ${ displaystyle w}$ . ${ displaystyle f (x) = langle w, x_ {i} rangle}$ как говорят редкий, если ${ Displaystyle | ш | _ {0} = s$ . Это означает, что на выходе ${ displaystyle Y}$ можно описать небольшим набором входных переменных.

В общем, допустим, что словарь ${ displaystyle phi _ {j}: X rightarrow mathbb {R}}$ с ${ displaystyle j = 1, ..., p}$ задана так, что целевая функция ${ displaystyle f (x)}$ задачи обучения можно записать как:

{ Displaystyle е (х) = сумма _ {j = 1} ^ {p} phi _ {j} (x) w_ {j}}

,

{ displaystyle forall x in X}

В ${ displaystyle ell _ {0}}$ норма ${ Displaystyle | е | _ {0} = | ш | _ {0}}$ как количество ненулевых компонент ${ displaystyle w}$ определяется как

{ Displaystyle | ш | _ {0} = | {j | w_ {j} neq 0, j in {1, ..., p } } |}

, куда

{ displaystyle | A |}

мощность множества

{ displaystyle A}

.

${ displaystyle f}$ считается редким, если ${ Displaystyle | е | _ {0} = | ш | _ {0} = s$ .

Однако при использовании ${ displaystyle ell _ {0}}$ Норма регуляризации благоприятствует разреженным решениям, ее сложно использовать с вычислительной точки зрения и, кроме того, она не является выпуклой. Вычислительно более выполнимая норма, которая способствует более разреженным решениям, - это ${ displaystyle ell _ {1}}$ норма; Было показано, что это все еще способствует более разреженным решениям и дополнительно является выпуклым.^[4]

Структурированная регуляризация разреженности расширяет и обобщает проблему выбора переменных, которая характеризует регуляризацию разреженности.^[2]^[3] Рассмотрим вышеизложенное упорядоченный минимизация эмпирического риска проблема с общим ядром и связанной картой функций ${ displaystyle phi _ {j}: X rightarrow mathbb {R}}$ с ${ displaystyle j = 1, ..., p}$ .

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

Срок регуляризации ${ Displaystyle лямбда | ш | _ {0}}$ наказывает каждого ${ displaystyle w_ {j}}$ компонент независимо, что означает, что алгоритм будет подавлять входные переменные независимо друг от друга.

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

Структуры и нормы

Неперекрывающиеся группы: групповое лассо

Случай неперекрывающихся групп - самый простой пример структурированной разреженности. В нем априори разбиение вектора коэффициентов ${ displaystyle w}$ в ${ displaystyle G}$ предполагается, что группы не перекрываются. Позволять ${ displaystyle w_ {g}}$ вектор коэффициентов в группе ${ displaystyle g}$ , мы можем определить член регуляризации и его групповую норму как

{ displaystyle lambda R (w) = lambda sum _ {g = 1} ^ {G} | w_ {g} | _ {g}}

,

куда ${ displaystyle | w_ {g} | _ {g}}$ это группа ${ displaystyle ell _ {2}}$ норма ${ displaystyle | w_ {g} | _ {g} = { sqrt { sum _ {j = 1} ^ {| G_ {g} |} (w_ {g} ^ {j}) ^ {2 }}}}$ , ${ displaystyle G_ {g}}$ это группа ${ displaystyle g}$ , и ${ displaystyle w_ {g} ^ {j}}$ это j-й компонент группы ${ displaystyle G_ {g}}$ .

Указанная норма также именуется группа лассо.^[2] Этот регуляризатор приведет к нулю целые группы коэффициентов, а не отдельные коэффициенты. Поскольку группы не перекрываются, набор ненулевых коэффициентов может быть получен как объединение групп, которые не были установлены на ноль, и наоборот для набора нулевых коэффициентов.

Перекрывающиеся группы

Перекрывающиеся группы - это случай разреженности структуры, когда переменная может принадлежать более чем одной группе ${ displaystyle g}$ . Этот случай часто представляет интерес, поскольку он может представлять более общий класс отношений между переменными, чем неперекрывающиеся группы, такие как древовидные структуры или другие типы графиков.^[3]^[8]

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

Пересечение дополнений: групповое лассо

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

{ displaystyle lambda R (w) = lambda sum _ {g = 1} ^ {G} | w_ {g} | _ {g}}

,

куда ${ displaystyle | w_ {g} | _ {g}}$ это группа ${ displaystyle ell _ {2}}$ норма, ${ displaystyle G_ {g}}$ это группа ${ displaystyle g}$ , и ${ displaystyle w_ {g} ^ {j}}$ это j-й компонент группы ${ displaystyle G_ {g}}$ .

Как и в случае неперекрывающихся групп, группа лассо регуляризатор потенциально обнулит целые группы коэффициентов. Выбранные переменные - это переменные с коэффициентами ${ displaystyle w_ {j}> 0}$ . Однако, поскольку в этом случае группы могут перекрываться, мы берем пересечение дополнений тех групп, которые не установлены в ноль.

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

Объединение групп: латентное групповое лассо

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

Формулировка подхода объединения групп также упоминается как латентная группа лассо, и требует изменить группу ${ displaystyle ell _ {2}}$ рассмотренной выше нормы и введем следующий регуляризатор ^[3]

{ Displaystyle R (w) = inf left { sum _ {g} | w_ {g} | _ {g}: w = sum _ {g = 1} ^ {G} { bar { w}} _ {g} right }}

куда ${ Displaystyle ш ин { mathbb {R ^ {d}}}}$ , ${ displaystyle w_ {g} in G_ {g}}$ - вектор коэффициентов группы g, а ${ displaystyle { bar {w}} _ {g} in { mathbb {R ^ {d}}}}$ вектор с коэффициентами ${ displaystyle w_ {g} ^ {j}}$ для всех переменных ${ displaystyle j}$ в группе ${ displaystyle g}$ , и ${ displaystyle 0}$ во всех остальных, т.е. ${ displaystyle { bar {w}} _ {g} ^ {j} = w_ {g} ^ {j}}$ если ${ displaystyle j}$ в группе ${ displaystyle g}$ и ${ displaystyle { bar {w}} _ {g} ^ {j} = 0}$ иначе.

Этот регуляризатор можно интерпретировать как эффективно реплицирующие переменные, принадлежащие более чем одной группе, тем самым сохраняя структуру группы. По замыслу подхода объединения групп, требующего ${ displaystyle w = sum _ {g = 1} ^ {G} { bar {w}} _ {g}}$ создает вектор весов w, который эффективно суммирует веса всех переменных по всем группам, к которым они принадлежат.

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

Целевая функция с использованием группового лассо состоит из функции ошибок, которая обычно должна быть выпуклой, но не обязательно сильно выпуклой, и группы ${ displaystyle ell _ {1}}$ срок регуляризации. Проблема с этой целевой функцией заключается в том, что она выпуклая, но не обязательно сильно выпуклая, и, следовательно, обычно не приводит к однозначным решениям.^[9]

Пример способа исправить это - ввести квадрат ${ displaystyle ell _ {2}}$ норма весового вектора как дополнительный член регуляризации при сохранении ${ displaystyle ell _ {1}}$ член регуляризации из подхода группового лассо.^[9] Если коэффициент при квадрате ${ displaystyle ell _ {2}}$ срок нормы больше чем ${ displaystyle 0}$ , то потому что квадрат ${ displaystyle ell _ {2}}$ член нормы является сильно выпуклым, результирующая целевая функция также будет сильно выпуклой.^[9] При условии, что ${ displaystyle ell _ {2}}$ коэффициент достаточно мал, но все же положителен, весовой вектор, минимизирующий результирующую целевую функцию, обычно очень близок к весовому вектору, который минимизирует целевую функцию, которая будет результатом удаления группы ${ displaystyle ell _ {2}}$ член регуляризации полностью от исходной целевой функции; последний сценарий соответствует подходу группового лассо.^[9] Таким образом, этот подход позволяет упростить оптимизацию при сохранении разреженности.^[9]

Нормы, основанные на структуре входных переменных

Видеть: Функция субмодульного набора

Помимо норм, рассмотренных выше, другие нормы, используемые в методах структурированной разреженности, включают иерархические нормы и нормы, определенные в сетках. Эти нормы возникают из субмодульных функций и позволяют включать предварительные предположения о структуре входных переменных. В контексте иерархических норм эту структуру можно представить как ориентированный ациклический граф над переменными, тогда как в контексте норм, основанных на сетке, структура может быть представлена в виде сетки.^[10]^[11]^[12]^[13]^[14]^[15]

Иерархические нормы

Видеть: Обучение без учителя

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

Иерархии скрытых переменных стали естественной структурой в нескольких приложениях, особенно для моделирования текстовых документов.^[11] Иерархические модели, использующие байесовские непараметрические методы, использовались для изучения тематические модели,^[10] которые представляют собой статистические модели для обнаружения абстрактных «тем», встречающихся в коллекции документов. Иерархии также рассматривались в контексте методов ядра.^[13] Иерархические нормы были применены к биоинформатике,^[12] компьютерное зрение и тематические модели.^[14]

Нормы, определенные на сетках

Если структура, предполагаемая над переменными, имеет форму одномерной, двухмерной или трехмерной сетки, то субмодульные функции, основанные на перекрывающихся группах, могут рассматриваться как нормы, приводящие к стабильным наборам, равным прямоугольной или выпуклой форме.^[13] Такие методы нашли применение в компьютерном зрении.^[15]

Алгоритмы вычислений

Проблема выбора лучшего подмножества

Проблема выбора наилучшего подмножества входных переменных может быть естественно сформулирована в рамках системы штрафов как:^[4]

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

Где ${ Displaystyle | ш | _ {0}}$ обозначает ${ displaystyle ell _ {0}}$ "норма", определяемая как количество ненулевых элементов вектора ${ displaystyle w}$ .

Хотя такая формулировка имеет смысл с точки зрения моделирования, она невыполнима с вычислительной точки зрения, поскольку эквивалентна исчерпывающему поиску, оценивающему все возможные подмножества переменных.^[4]

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

Выпуклое расслабление

Естественным приближением к проблеме выбора наилучшего подмножества является ${ displaystyle ell _ {1}}$ регуляризация нормы:^[4]

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

Такая схема называется базовое преследование или Лассо, который заменяет ${ displaystyle ell _ {0}}$ «норма» для выпуклых недифференцируемых ${ displaystyle ell _ {1}}$ норма.

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

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

Таким образом, методы проксимального градиента полезны для решения задач регуляризации разреженности и структурированной разреженности.^[9] следующего вида:

{ displaystyle min _ {w in mathbb {R} ^ {d}} { frac {1} {n}} sum _ {i = 1} ^ {n} V (y_ {i}, w , x_ {i}) + R (w)}

Где ${ displaystyle V (y_ {i}, w, x_ {i})}$ выпуклый и дифференцируемый функция потерь словно квадратичная потеря, и ${ Displaystyle R (ш)}$ является выпуклым потенциально недифференцируемым регуляризатором, таким как ${ displaystyle ell _ {1}}$ норма.

Связь с другими областями машинного обучения

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

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

В упомянутых выше алгоритмах учитывалось сразу все пространство и разбивалось на группы, т.е. подпространства. Дополнительная точка зрения состоит в том, чтобы рассмотреть случай, когда отдельные пространства объединяются для получения нового. Полезно обсудить эту идею, рассматривая конечные словари. Конечные словари с линейно независимыми элементами - эти элементы также известны как атомы - относятся к конечным наборам линейно независимых базисных функций, линейные комбинации которых определяют пространства гипотез. Конечные словари могут использоваться для определения конкретных ядер, как будет показано ниже.^[16] Предположим для этого примера, что вместо одного словаря рассматривается несколько конечных словарей.

Для простоты случай, когда есть только два словаря ${ displaystyle A = {a_ {j}: X rightarrow mathbb {R}, j = 1, ..., p }}$ и ${ displaystyle B = {b_ {t}: X rightarrow mathbb {R}, t = 1, ..., q }}$ куда ${ displaystyle q}$ и ${ displaystyle p}$ являются целыми числами, будут считаться. Атомы в ${ displaystyle A}$ а также атомы в ${ displaystyle B}$ считаются линейно независимыми. Позволять ${ displaystyle D = {d_ {k}: X rightarrow mathbb {R}, k = 1, ..., p + q } = A cup B}$ быть объединением двух словарей. Рассмотрим линейное пространство функций ${ displaystyle H}$ заданные линейными комбинациями вида

${ Displaystyle е (х) = сумма _ {я = 1} ^ {p + q} {w ^ {j} d_ {j} (x)} = sum _ {j = 1} ^ {p} { w_ {A} ^ {j} a_ {j} (x)} + sum _ {t = 1} ^ {q} {w_ {B} ^ {t} b_ {t} (x)}, x in ИКС}$

для некоторых векторов коэффициентов ${ displaystyle w_ {A} in mathbb {R} ^ {p}, w_ {B} in mathbb {R} ^ {q}}$ , куда ${ displaystyle w = (w_ {A}, w_ {B})}$ . Предположим, что атомы в ${ displaystyle D}$ чтобы по-прежнему быть линейно независимым, или, что то же самое, что отображение ${ displaystyle w = (w_ {A}, w_ {B}) mapsto f}$ один к одному. Функции в пространстве ${ displaystyle H}$ можно рассматривать как сумму двух компонентов, одна в пространстве ${ displaystyle H_ {A}}$ линейные комбинации атомов в ${ displaystyle A}$ и один в ${ displaystyle H_ {B}}$ линейные комбинации атомов в ${ displaystyle B}$ .

Один из вариантов нормы на этом пространстве ${ displaystyle || f || = || w_ {A} || + || w_ {B} ||}$ . Обратите внимание, что теперь мы можем просматривать ${ displaystyle H}$ как функциональное пространство, в котором ${ displaystyle H_ {A}}$ , ${ displaystyle H_ {B}}$ являются подпространствами. Ввиду предположения о линейной независимости ${ displaystyle H}$ можно отождествить с ${ Displaystyle mathbb {R} ^ {p + q}}$ и ${ displaystyle H_ {A}, H_ {B}}$ с ${ Displaystyle mathbb {R} ^ {p}, mathbb {R} ^ {q}}$ соответственно. Указанная выше норма может рассматриваться как групповая норма в ${ displaystyle H}$ связанные с подпространствами ${ displaystyle H_ {A}}$ , ${ displaystyle H_ {B}}$ , обеспечивая связь с регуляризацией структурированной разреженности.

Здесь, ${ displaystyle H_ {A}}$ , ${ displaystyle H_ {B}}$ и ${ displaystyle H}$ можно рассматривать как воспроизводящие гильбертовы пространства ядра с соответствующими отображениями характеристик ${ displaystyle Phi _ {A}: X rightarrow mathbb {R} ^ {p}}$ , данный ${ Displaystyle Phi _ {A} (x) = (a_ {1} (x), ..., a_ {p} (x))}$ , ${ displaystyle Phi _ {B}: X rightarrow mathbb {R} ^ {q}}$ , данный ${ Displaystyle Phi _ {B} (x) = (b_ {1} (x), ..., b_ {q} (x))}$ , и ${ displaystyle Phi: X rightarrow mathbb {R} ^ {p + q}}$ , заданный конкатенацией ${ displaystyle Phi _ {A}, Phi _ {B}}$ , соответственно.

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

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

пробелы.^[16]

Когда полезно изучение разреженного множественного ядра

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

Объединение данных: когда каждое ядро соответствует разному типу модальности / функции.
Нелинейный выбор переменных: рассмотрим ядра ${ displaystyle K_ {g}}$ зависит только от одного измерения ввода.

Обычно разреженное изучение нескольких ядер особенно полезно, когда ядер много, а выбор модели и интерпретируемость важны.^[16]

Дополнительное использование и приложения

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

Компрессионное зондирование в магнитно-резонансная томография (МРТ), реконструкция МР-изображений из небольшого количества измерений, потенциально обеспечивающая значительное сокращение времени МР-сканирования^[6]
Крепкий распознавание лица при наличии перекоса, окклюзии и изменения освещенности^[5]
Раскрытие социолингвистический ассоциации между лексическими частотами, используемыми авторами Twitter, и социально-демографическими переменными их географических сообществ^[7]
Анализ выбора генов данных рака груди с использованием априорных значений перекрывающихся групп, например, биологически значимых наборов генов^[8]

Регуляризация структурированной разреженности - Structured sparsity regularization

Содержание

Определение и связанные понятия

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