Матричная регуляризация - Matrix regularization

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

${ displaystyle min _ {x} | Ax-y | ^ {2} + lambda | x | ^ {2}}$

найти вектор ${ displaystyle x}$ это стабильное решение проблемы регрессии. Когда система описывается матрицей, а не вектором, эту задачу можно записать как

${ displaystyle min _ {X} | AX-Y | ^ {2} + lambda | X | ^ {2},}$

где векторная норма, обеспечивающая штраф за регуляризацию на ${ displaystyle x}$ был расширен до матричной нормы на ${ displaystyle X}$.

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

Основное определение

Рассмотрим матрицу ${ displaystyle W}$ учиться на примерах, ${ displaystyle S = (X_ {i} ^ {t}, y_ {i} ^ {t})}$, куда ${ displaystyle i}$ идет от ${ displaystyle 1}$ к ${ displaystyle n}$, и ${ displaystyle t}$ идет от ${ displaystyle 1}$ к ${ displaystyle T}$. Пусть каждая входная матрица ${ displaystyle X_ {i}}$ быть ${ Displaystyle в mathbb {R} ^ {DT}}$, и разреши ${ displaystyle W}$ иметь размер ${ displaystyle D times T}$. Общая модель вывода ${ displaystyle y}$ можно представить как

${ displaystyle y_ {i} ^ {t} = langle W, X_ {i} ^ {t} rangle _ {F},}$

где внутренний продукт - это Внутренний продукт Фробениуса. Для различных приложений матрицы ${ displaystyle X_ {i}}$ будут иметь разные формы,^[1] но для каждого из них задача оптимизации вывести ${ displaystyle W}$ можно записать как

${ Displaystyle мин _ {W in { mathcal {H}}} E (W) + R (W),}$

куда ${ displaystyle E}$ определяет эмпирическую ошибку для данного ${ displaystyle W}$, и ${ Displaystyle R (W)}$ штраф за регуляризацию матрицы. Функция ${ Displaystyle R (W)}$ обычно выбирается выпуклым и часто выбирается для обеспечения разреженности (используя ${ displaystyle ell ^ {1}}$-norms) и / или гладкость (используя ${ displaystyle ell ^ {2}}$-нормы). Ну наконец то, ${ displaystyle W}$ находится в пространстве матриц ${ displaystyle { mathcal {H}}}$ с внутренним произведением Фробениуса ${ displaystyle langle dots rangle _ {F}}$.

Общие приложения

Завершение матрицы

В проблеме заполнение матрицы, матрица ${ displaystyle X_ {i} ^ {t}}$ принимает форму

${ displaystyle X_ {i} ^ {t} = e_ {t} otimes e_ {i} ',}$

куда ${ Displaystyle (е_ {т}) _ {т}}$ и ${ Displaystyle (е_ {я} ') _ {я}}$ каноническая основа в ${ Displaystyle mathbb {R} ^ {T}}$ и ${ Displaystyle mathbb {R} ^ {D}}$. В этом случае роль внутреннего продукта Фробениуса заключается в выборе отдельных элементов. ${ Displaystyle ш_ {я} ^ {т}}$ из матрицы ${ displaystyle W}$. Таким образом, на выходе ${ displaystyle y}$ это выборка элементов из матрицы ${ displaystyle W}$.

Проблема реконструкции ${ displaystyle W}$ из небольшого набора выборочных записей возможно только при определенных ограничениях на матрицу, и эти ограничения могут быть реализованы с помощью функции регуляризации. Например, можно предположить, что ${ displaystyle W}$ имеет низкий ранг, и в этом случае штраф за регуляризацию может принимать форму ядерной нормы.^[2]

${ Displaystyle R (W) = lambda | W | _ {*} = lambda sum | sigma _ {i} |,}$

куда ${ displaystyle sigma _ {я}}$, с ${ displaystyle i}$ из ${ displaystyle 1}$ к ${ displaystyle min D, T}$, - сингулярные значения ${ displaystyle W}$.

Многомерная регрессия

Модели, используемые в многомерная регрессия параметризованы матрицей коэффициентов. В приведенном выше внутреннем произведении Фробениуса каждая матрица ${ displaystyle X}$ является

${ displaystyle X_ {i} ^ {t} = e_ {t} otimes x_ {i} ,}$

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

${ Displaystyle Y = XW + Ь ,}$

Многие из векторных норм, используемых в регрессии с одной переменной, можно распространить на многомерный случай. Одним из примеров является квадрат нормы Фробениуса, который можно рассматривать как ${ displaystyle ell ^ {2}}$-норма, действующая либо по элементам, либо по сингулярным числам матрицы:

${ displaystyle R (W) = lambda | W | _ {F} ^ {2} = lambda sum sum | w_ {ij} | ^ {2} = lambda operatorname {Tr} (W ^ {*} W) = lambda sum sigma _ {i} ^ {2}.}$

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

Многозадачное обучение

Настройка для многозадачного обучения почти такая же, как для многомерной регрессии. Основное отличие состоит в том, что входные переменные также индексируются по задачам (столбцы ${ displaystyle Y}$). Тогда представление с внутренним произведением Фробениуса будет

${ displaystyle X_ {i} ^ {t} = e_ {t} otimes x_ {i} ^ {t}.}$

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

${ Displaystyle мин _ {W} | XW-Y | _ {2} ^ {2} + lambda | W | _ {2} ^ {2}}$

решения, соответствующие каждому столбцу ${ displaystyle Y}$ развязаны. То есть одно и то же решение можно найти, решив совместную задачу или решив изолированную задачу регрессии для каждого столбца. Проблемы можно объединить, добавив дополнительный штраф за регулирование ковариантности решений.

${ displaystyle min _ {W, Omega} | XW-Y | _ {2} ^ {2} + lambda _ {1} | W | _ {2} ^ {2} + lambda _ {2} operatorname {Tr} (W ^ {T} Omega ^ {- 1} W)}$

куда ${ displaystyle Omega}$ моделирует взаимосвязь между задачами. Эта схема может использоваться как для обеспечения схожести решений для разных задач, так и для изучения конкретной структуры схожести задач путем чередования оптимизаций ${ displaystyle W}$ и ${ displaystyle Omega}$.^[3] Когда известно, что взаимосвязь между задачами лежит на графике, Матрица лапласа графа можно использовать для объединения задач обучения.

Спектральная регуляризация

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

Есть ряд матричных норм, которые действуют на сингулярные значения матрицы. Часто используемые примеры включают P-нормы Шаттена, с п = 1 или 2. Например, матричная регуляризация с 1-нормой Шаттена, также называемая ядерной нормой, может использоваться для обеспечения разреженности спектра матрицы. Это использовалось в контексте завершения матрицы, когда считается, что рассматриваемая матрица имеет ограниченный ранг.^[2] В этом случае проблема оптимизации становится:

${ Displaystyle мин | W | _ {*}}$ при условии ${ displaystyle W_ {i, j} = Y_ {ij}.}$

Спектральная регуляризация также используется для обеспечения матрицы коэффициентов пониженного ранга в многомерной регрессии.^[4] В этой настройке матрицу коэффициентов пониженного ранга можно найти, оставив только верхний ${ displaystyle n}$ сингулярные значения, но это можно расширить, чтобы сохранить любой сокращенный набор сингулярных значений и векторов.

Структурированная разреженность

Разреженная оптимизация стала предметом большого исследовательского интереса как способ поиска решений, которые зависят от небольшого числа переменных (см., Например, Метод лассо ). В принципе, разреженность на входе может быть обеспечена путем наложения штрафов на запись ${ displaystyle ell ^ {0}}$-норма матрицы, но ${ displaystyle ell ^ {0}}$-норма не выпуклая. На практике это может быть реализовано выпуклой релаксацией к ${ displaystyle ell ^ {1}}$-норма. Хотя начальная регуляризация с ${ displaystyle ell ^ {1}}$-norm найдет решения с небольшим количеством ненулевых элементов, применяя ${ displaystyle ell ^ {1}}$-норма к различным группам переменных может усилить структуру разреженности решений.^[5]

Самый простой пример структурированной разреженности использует ${ displaystyle ell _ {p, q}}$ норма с ${ displaystyle p = 2}$ и ${ displaystyle q = 1}$:

${ displaystyle | W | _ {2,1} = sum | w_ {i} | _ {2}.}$

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

В более общем плане ${ displaystyle ell _ {2,1}}$ норма может применяться к произвольным группам переменных:

${ displaystyle R (W) = lambda sum _ {g} ^ {G} { sqrt { sum _ {j} ^ {| G_ {g} |} | w_ {g} ^ {j} | ^ {2}}} = lambda sum _ {g} ^ {G} | w_ {g} | _ {g}}$

где индекс ${ displaystyle g}$ находится по группам переменных, и ${ displaystyle | G_ {g} |}$ указывает мощность группы ${ displaystyle g}$.

Алгоритмы для решения этих проблем разреженности групп расширяют более известные методы лассо и группового лассо, например, позволяя перекрывающиеся группы, и были реализованы через подходящее преследование:^[7] и проксимальные градиентные методы.^[8] Записав проксимальный градиент по отношению к данному коэффициенту, ${ displaystyle w_ {g} ^ {i}}$, видно, что эта норма обеспечивает групповой мягкий порог^[1]

${ displaystyle operatorname {prox} _ { lambda, R_ {g}} (w_ {g}) ^ {i} = left (w_ {g} ^ {i} - lambda { frac {w_ {g}) } ^ {i}} { | w_ {g} | _ {g}}} right) mathbf {1} _ { | w_ {g} | _ {g} geq lambda}.}$

куда ${ displaystyle mathbf {1} _ { | w_ {g} | _ {g} geq lambda}}$ индикаторная функция для групповых норм ${ displaystyle geq lambda}$.

Таким образом, используя ${ displaystyle ell _ {2,1}}$ Согласно нормам несложно обеспечить структуру разреженной матрицы по строкам, по столбцам или произвольными блоками. Например, применяя групповые нормы для блоков в многофакторной или многозадачной регрессии, можно найти группы входных и выходных переменных, в которых определены подмножества выходных переменных (столбцы в матрице ${ displaystyle Y}$) будет зависеть от того же разреженного набора входных переменных.

Выбор нескольких ядер

Идеи структурированной разреженности и выбор функции распространяется на непараметрический случай изучение нескольких ядер.^[9] Это может быть полезно, когда имеется несколько типов входных данных (например, цвет и текстура) с разными подходящими ядрами для каждого или когда соответствующее ядро ​​неизвестно. Если есть два ядра, например, с картами функций ${ displaystyle A}$ и ${ displaystyle B}$ лежат в соответствующих воспроизводящие ядерные гильбертовы пространства ${ displaystyle { mathcal {H_ {A}}}, { mathcal {H_ {B}}}}$, затем большее пространство, ${ displaystyle { mathcal {H_ {D}}}}$, можно создать как сумму двух пробелов:

${ displaystyle { mathcal {H_ {D}}}: f = h + h '; h in { mathcal {H_ {A}}}, h' in { mathcal {H_ {B}}}}$

предполагая линейную независимость в ${ displaystyle A}$ и ${ displaystyle B}$. В этом случае ${ displaystyle ell _ {2,1}}$-норма - это снова сумма норм:

${ Displaystyle | е | _ {{ mathcal {H_ {D}}}, 1} = | h | _ { mathcal {H_ {A}}} + | h ' | _ { математический {H_ {B}}}}$

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

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

• Регуляризация (математика)

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