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

В области статистической теории обучения матричная регуляризация обобщает понятия векторной регуляризации на случаи, когда объектом обучения является матрица. Цель регуляризации — обеспечить соблюдение условий, например, разреженности или гладкости, которые могут давать стабильные предсказательные функции. Например, в более общей векторной структуре регуляризация Тихонова оптимизирует по для нахождения вектора , который является стабильным решением задачи регрессии. Когда система описывается матрицей, а не вектором, эту задачу можно записать как где векторная норма, обеспечивающая штраф регуляризации на , была расширена до матричной нормы на .$${\displaystyle \min _{x}\left\|Ax-y\right\|^{2}+\lambda \left\|x\right\|^{2}}$$${\displaystyle x}$$${\displaystyle \min _{X}\left\|AX-Y\right\|^{2}+\lambda \left\|X\right\|^{2},}$$${\displaystyle x}$${\displaystyle X}$

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

Рассмотрим матрицу, которую нужно выучить из набора примеров, , где переходит из в , и переходит из в . Пусть каждая входная матрица будет , и пусть будет размером . Общую модель для вывода можно представить как , где скалярное произведение является скалярным произведением Фробениуса . Для различных приложений матрицы будут иметь разные формы, ^[1] но для каждого из них задача оптимизации для вывода может быть записана как , где определяет эмпирическую ошибку для заданного , а является штрафом за регуляризацию матрицы. Функция обычно выбирается выпуклой и часто выбирается для обеспечения разреженности (с использованием -норм) и/или гладкости (с использованием -норм). Наконец, находится в пространстве матриц с скалярным произведением Фробениуса .${\displaystyle W}$${\displaystyle S=(X_{i}^{t},y_{i}^{t})}$${\displaystyle я}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle т}$${\displaystyle 1}$${\displaystyle Т}$${\displaystyle X_{i}}$${\displaystyle \in \mathbb {R} ^{DT}}$${\displaystyle W}$${\displaystyle D\times T}$${\displaystyle у}$$${\displaystyle y_{i}^{t}=\left\langle W,X_{i}^{t}\right\rangle _{F},}$$${\displaystyle X_{i}}$${\displaystyle W}$$${\ displaystyle \ min _ {W \ in {\ mathcal {H}}} E (W) + R (W),}$$${\displaystyle E}$${\displaystyle W}$${\displaystyle R(W)}$${\displaystyle R(W)}$${\displaystyle \ell ^{1}}$${\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 (e_{t})_{t}}$${\displaystyle (e_{i}')_{i}}$${\displaystyle \mathbb {R} ^{T}}$${\displaystyle \mathbb {R} ^{D}}$${\displaystyle w_{i}^{t}}$${\displaystyle W}$${\displaystyle y}$${\displaystyle W}$

Проблема реконструкции из небольшого набора выборочных записей возможна только при определенных ограничениях на матрицу, и эти ограничения могут быть усилены функцией регуляризации. Например, можно предположить, что имеет низкий ранг, в этом случае штраф за регуляризацию может принять форму ядерной нормы. ^[2] где , с от до , являются сингулярными значениями .${\displaystyle W}$${\displaystyle W}$$${\displaystyle R(W)=\lambda \left\|W\right\|_{*}=\lambda \sum _{i}\left|\sigma _{i}\right|,}$$${\displaystyle \sigma _{i}}$${\displaystyle i}$${\displaystyle 1}$${\displaystyle \min D,T}$${\displaystyle W}$

Модели, используемые в многомерной регрессии, параметризуются матрицей коэффициентов. В приведенном выше внутреннем произведении Фробениуса каждая матрица такова , что выход внутреннего произведения является скалярным произведением одной строки входных данных с одним столбцом матрицы коэффициентов. Знакомая форма таких моделей —${\displaystyle X}$$${\displaystyle X_{i}^{t}=e_{t}\otimes x_{i}}$$$${\displaystyle Y=XW+b}$$

Многие из векторных норм, используемых в регрессии с одной переменной, могут быть расширены на многомерный случай. Одним из примеров является квадрат нормы Фробениуса, которую можно рассматривать как -норму , действующую либо по входу, либо на сингулярные значения матрицы:${\displaystyle \ell ^{2}}$$${\displaystyle R(W)=\lambda \left\|W\right\|_{F}^{2}=\lambda \sum _{i}\sum _{j}\left|w_{ij}\right|^{2}=\lambda \operatorname {Tr} \left(W^{*}W\right)=\lambda \sum _{i}\sigma _{i}^{2}.}$$

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

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

Роль матричной регуляризации в этой настройке может быть такой же, как и в многомерной регрессии, но матричные нормы также могут использоваться для связывания задач обучения между задачами. В частности, обратите внимание, что для задачи оптимизации решения, соответствующие каждому столбцу, разъединены. То есть одно и то же решение может быть найдено путем решения совместной задачи или путем решения изолированной задачи регрессии для каждого столбца. Задачи могут быть связаны путем добавления дополнительного штрафа за регуляризацию к ковариации решений , где моделирует взаимосвязь между задачами. Эту схему можно использовать как для обеспечения сходства решений между задачами, так и для изучения конкретной структуры сходства задач путем чередования оптимизаций и . ^[3] Когда известно, что взаимосвязь между задачами лежит на графике, матрица Лапласа графа может использоваться для связывания задач обучения.$${\displaystyle \min _{W}\left\|XW-Y\right\|_{2}^{2}+\lambda \left\|W\right\|_{2}^{2}}$$${\displaystyle Y}$$${\displaystyle \min _{W,\Omega }\left\|XW-Y\right\|_{2}^{2}+\lambda _{1}\left\|W\right\|_{2}^{2}+\lambda _{2}\operatorname {Tr} \left(W^{T}\Omega ^{-1}W\right)}$$${\displaystyle \Omega }$${\displaystyle W}$${\displaystyle \Omega }$

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

Существует ряд матричных норм, которые действуют на сингулярные значения матрицы. Часто используемые примеры включают p-нормы Шаттена , где p  = 1 или 2. Например, регуляризация матрицы с 1-нормой Шаттена, также называемой ядерной нормой, может использоваться для обеспечения разреженности в спектре матрицы. Это использовалось в контексте завершения матрицы, когда предполагается, что рассматриваемая матрица имеет ограниченный ранг. ^[2] В этом случае задача оптимизации становится:$${\displaystyle \min \left\|W\right\|_{*}~~{\text{ subject to }}~~W_{i,j}=Y_{ij}.}$$

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

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

Самый простой пример структурированной разреженности использует норму с и :${\displaystyle \ell _{p,q}}$${\displaystyle p=2}$${\displaystyle q=1}$$${\displaystyle \left\|W\right\|_{2,1}=\sum _{i}\left\|w_{i}\right\|_{2}.}$$

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

В более общем смысле норму можно применять к произвольным группам переменных: где индекс относится к группам переменных и указывает мощность группы .${\displaystyle \ell _{2,1}}$$${\displaystyle R(W)=\lambda \sum _{g}^{G}{\sqrt {\sum _{j}^{|G_{g}|}\left|w_{g}^{j}\right|^{2}}}=\lambda \sum _{g}^{G}\left\|w_{g}\right\|_{g}}$$${\displaystyle g}$${\displaystyle |G_{g}|}$${\displaystyle g}$

Алгоритмы для решения этих проблем разреженности групп расширяют более известные методы Лассо и группового Лассо, допуская перекрывающиеся группы, например, и были реализованы с помощью методов поиска совпадений : ^[7] и методов проксимального градиента . ^[8] Записывая проксимальный градиент относительно заданного коэффициента, , можно увидеть, что эта норма обеспечивает мягкий порог по группе ^[1], где — индикаторная функция для групповых норм .${\displaystyle w_{g}^{i}}$$${\displaystyle \operatorname {prox} _{\lambda ,R_{g}}\left(w_{g}\right)^{i}=\left(w_{g}^{i}-\lambda {\frac {w_{g}^{i}}{\left\|w_{g}\right\|_{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 \left\|f\right\|_{{\mathcal {H_{D}}},1}=\left\|h\right\|_{\mathcal {H_{A}}}+\left\|h'\right\|_{\mathcal {H_{B}}}}$$

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

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