Многообразная регуляризация

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

В машинном обучении регуляризация многообразия — это метод использования формы набора данных для ограничения функций, которые должны быть изучены в этом наборе данных. Во многих задачах машинного обучения данные, подлежащие изучению, не охватывают все входное пространство. Например, системе распознавания лиц может не потребоваться классифицировать какое-либо возможное изображение, а только подмножество изображений, содержащих лица. Методика многообразного обучения предполагает, что соответствующее подмножество данных поступает из многообразия — математической структуры с полезными свойствами. Этот метод также предполагает, что изучаемая функция является гладкой : данные с разными метками вряд ли будут находиться близко друг к другу, поэтому функция маркировки не должна быстро меняться в областях, где может быть много точек данных. Из-за этого предположения алгоритм регуляризации многообразия может использовать немаркированные данные, чтобы сообщить, где изученной функции разрешено быстро изменяться, а где нет, используя расширение метода регуляризации Тихонова. . Алгоритмы многообразной регуляризации могут расширить алгоритмы контролируемого обучения в условиях полуконтролируемого обучения и трансдуктивного обучения , где доступны немаркированные данные. Этот метод использовался для таких приложений, как медицинская визуализация, географическая визуализация и распознавание объектов.

Регуляризатор многообразия

Мотивация

Многообразная регуляризация — это тип регуляризации , семейство методов, которые уменьшают переобучение задачи и гарантируют корректность постановки путем наказания сложных решений. В частности, регуляризация многообразий расширяет технику тихоновской регуляризации применительно к воспроизведению ядерных гильбертовых пространств (RKHS). При стандартной тихоновской регуляризации на RKHS алгоритм обучения пытается изучить функцию $f$ из пространства гипотез функций ${\mathcal {H}}$. Пространство гипотез представляет собой RKHS, что означает, что оно связано с ядром $K$, и поэтому каждая функция-кандидат $f$ имеет норму $\left\|f\right\|_{K}$, который представляет сложность функции-кандидата в пространстве гипотез. Когда алгоритм рассматривает функцию-кандидат, он учитывает ее норму, чтобы наказать сложные функции.

Формально, учитывая набор размеченных обучающих данных $(x_{1},y_{1}),\ldots ,(x_{\ell },y_{\ell })$ с $x_{i}\in X,y_{i}\in Y$ и функция потерь $V$, алгоритм обучения, использующий регуляризацию Тихонова, попытается решить выражение

${\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }V(f(x_{i}),y_{i})+\gamma \left\|f\right\|_{K}^{2}$

где $\gamma$ — это гиперпараметр , который контролирует, насколько алгоритм будет отдавать предпочтение более простым функциям, а не функциям, которые лучше соответствуют данным.

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

Регуляризация многообразия добавляет второй термин регуляризации, внутренний регуляризатор , к объемлющему регуляризатору, используемому в стандартной регуляризации Тихонова. Согласно предположению о многообразии в машинном обучении, рассматриваемые данные не поступают из всего входного пространства. $X$, но вместо этого из нелинейного многообразия $M\subset X$. Геометрия этого многообразия, внутреннего пространства, используется для определения нормы регуляризации.

Лапласова норма

Существует множество возможных вариантов встроенного регуляризатора. $\left\|f\right\|_{I}$. Многие естественные варианты выбора связаны с градиентом на многообразии. $\nabla _{M}$, который может дать представление о том, насколько гладкой является целевая функция. Гладкая функция должна изменяться медленно, если входные данные плотные; то есть градиент $\nabla _{M}f(x)$ должно быть небольшим там, где предельная плотность вероятности ${\mathcal {P}}_{X}(x)$, плотность вероятности случайно нарисованной точки данных, появляющейся в точке $x$, большой. Это дает один подходящий выбор для внутреннего регуляризатора:

$\left\|f\right\|_{I}^{2}=\int _{x\in M}\left\|\nabla _{M}f(x)\right\|^{2}\,d{\mathcal {P}}_{X}(x)$

На практике эту норму невозможно вычислить напрямую, поскольку предельное распределение ${\mathcal {P}}_{X}$ неизвестно, но его можно оценить по предоставленным данным.

Графовый

Когда расстояния между входными точками интерпретируются как график, матрица Лапласа графика может помочь оценить предельное распределение. Предположим, что входные данные включают в себя $\ell$ помеченные примеры (пары входных $x$ и этикетка $y$) и $u$немаркированные примеры (входные данные без связанных меток). Определять $W$ быть матрицей весов ребер графа, где $W_{ij}$ это мера расстояния между точками данных $x_{i}$ и $x_{j}$. Определять $D$ быть диагональной матрицей с $D_{ii}=\sum _{j=1}^{\ell +u}W_{ij}$ и $L$ быть матрицей Лапласа $D-W$. Тогда, поскольку количество точек данных $\ell +u$ увеличивается, $L$ сходится к оператору Лапласа–Бельтрами $\Delta _{M}$, что является дивергенцией градиента $\nabla _{M}$. Тогда, если $\mathbf {f}$ представляет собой вектор значений $f$ по данным, $\mathbf {f} =[f(x_{1}),\ldots ,f(x_{l+u})]^{\mathrm {T} }$, внутреннюю норму можно оценить:

$\left\|f\right\|_{I}^{2}={\frac {1}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f}$

Поскольку количество точек данных $\ell +u$ увеличивается, это эмпирическое определение $\left\|f\right\|_{I}^{2}$ сходится к определению, когда ${\mathcal {P}}_{X}$ известен.

Решение проблемы регуляризации с помощью графового подхода

Использование весов $\gamma _{A}$ и $\gamma _{I}$ для окружающих и внутренних регуляризаторов окончательное выражение, которое необходимо решить, будет выглядеть следующим образом:

${\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }V(f(x_{i}),y_{i})+\gamma _{A}\left\|f\right\|_{K}^{2}+{\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f}$

Как и в случае с другими методами ядра , ${\mathcal {H}}$может быть бесконечномерным пространством, поэтому, если выражение регуляризации не может быть решено явно, невозможно искать решение во всем пространстве. Вместо этого теорема о представителе показывает, что при определенных условиях выбора нормы $\left\|f\right\|_{I}$, оптимальное решение $f^{*}$ должна быть линейной комбинацией ядра с центром в каждой из входных точек: для некоторых весов $\alpha _{i}$,

$f^{*}(x)=\sum _{i=1}^{\ell +u}\alpha _{i}K(x_{i},x)$

Используя этот результат, можно найти оптимальное решение. $f^{*}$ путем поиска в конечномерном пространстве, определенном возможным выбором $\alpha _{i}$.

лапласовой

Идея, выходящая за рамки граф-лапласа, состоит в том, чтобы использовать соседей для оценки лапласиана. Этот метод аналогичен методам локального усреднения , которые, как известно, плохо масштабируются в многомерных задачах. Действительно, граф Лапласа, как известно, страдает от проклятия размерности . К счастью, можно использовать ожидаемую гладкость функции для оценки благодаря более сложному функциональному анализу. Этот метод заключается в оценке оператора Лапласа благодаря производным от чтения ядра $\partial _{1,j}K(x_{i},x)$ где $\partial _{1,j}$ обозначает частные производные по j -й координате первой переменной. Этот второй подход к норме Лапласа заключается в сопоставлении с бессеточными методами , которые контрастируют с методом конечных разностей в PDE.

Приложения

Регуляризация многообразия может расширить множество алгоритмов, которые можно выразить с помощью регуляризации Тихонова, выбрав подходящую функцию потерь. $V$ и пространство гипотез ${\mathcal {H}}$. Двумя часто используемыми примерами являются семейства машин опорных векторов и наименьших квадратов регуляризованные алгоритмы . (Регуляризованный метод наименьших квадратов включает в себя алгоритм гребневой регрессии; связанные алгоритмы LASSO и регуляризации эластичной сети могут быть выражены как машины опорных векторов. ) Расширенные версии этих алгоритмов называются лапласовскими регуляризованными наименьшими квадратами (сокращенно LapRLS) и лапласовскими машинами опорных векторов (LapSVM) соответственно.

наименьших квадратов (

Регуляризованный метод наименьших квадратов (RLS) — это семейство алгоритмов регрессии : алгоритмов, которые прогнозируют значение. $y=f(x)$ за его вклад $x$, с целью, чтобы прогнозируемые значения были близки к истинным меткам данных. В частности, RLS предназначен для минимизации среднеквадратической ошибки между прогнозируемыми значениями и истинными метками при условии регуляризации. Ридж-регрессия — это одна из форм СБН; в общем, RLS — это то же самое, что гребневая регрессия в сочетании с методом ядра . Постановка задачи для РЛС вытекает из выбора функции потерь $V$ в регуляризации Тихонова это среднеквадратическая ошибка:

$f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }(f(x_{i})-y_{i})^{2}+\gamma \left\|f\right\|_{K}^{2}$

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

$f^{*}(x)=\sum _{i=1}^{\ell }\alpha _{i}^{*}K(x_{i},x)$

и решение для $\alpha ^{*}$ дает:

$\alpha ^{*}=(K+\gamma \ell I)^{-1}Y$

где $K$ определяется как матрица ядра, причем $K_{ij}=K(x_{i},x_{j})$, и $Y$ — вектор меток данных.

Добавление лапласова члена для регуляризации многообразия дает лапласовское утверждение RLS:

$f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }(f(x_{i})-y_{i})^{2}+\gamma _{A}\left\|f\right\|_{K}^{2}+{\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f}$

Теорема о представителе для регуляризации многообразия снова дает

$f^{*}(x)=\sum _{i=1}^{\ell +u}\alpha _{i}^{*}K(x_{i},x)$

и это дает выражение для вектора $\alpha ^{*}$. Сдача в аренду $K$ быть матрицей ядра, как указано выше, $Y$ быть вектором меток данных, и $J$ быть $(\ell +u)\times (\ell +u)$ блочная матрица ${\begin{bmatrix}I_{\ell }&0\\0&0_{u}\end{bmatrix}}$:

$\alpha ^{*}={\underset {\alpha \in \mathbf {R} ^{\ell +u}}{\arg \!\min }}{\frac {1}{\ell }}(Y-JK\alpha )^{\mathrm {T} }(Y-JK\alpha )+\gamma _{A}\alpha ^{\mathrm {T} }K\alpha +{\frac {\gamma _{I}}{(\ell +u)^{2}}}\alpha ^{\mathrm {T} }KLK\alpha$

с решением

$\alpha ^{*}=\left(JK+\gamma _{A}\ell I+{\frac {\gamma _{I}\ell }{(\ell +u)^{2}}}LK\right)^{-1}Y$

LapRLS применялся для решения проблем, включая сенсорные сети, медицинская визуализация , обнаружение объектов, спектроскопия , классификация документов , лекарственно-белковые взаимодействия, и сжатие изображений и видео.

опорных векторов Лапласа (

Машины опорных векторов (SVM) — это семейство алгоритмов, часто используемых для классификации данных на две или более группы или классы . Интуитивно SVM рисует границу между классами так, чтобы самые близкие к границе помеченные примеры находились как можно дальше. Это можно непосредственно выразить в виде линейной программы , но это также эквивалентно регуляризации Тихонова с потерь шарнира : функцией $V(f(x),y)=\max(0,1-yf(x))$:

$f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }\max(0,1-y_{i}f(x_{i}))+\gamma \left\|f\right\|_{K}^{2}$

Добавление к этому выражению члена внутренней регуляризации дает постановку задачи LapSVM:

$f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }\max(0,1-y_{i}f(x_{i}))+\gamma _{A}\left\|f\right\|_{K}^{2}+{\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f}$

Опять же, теорема о представителе позволяет выразить решение через ядро, оцененное в точках данных:

$f^{*}(x)=\sum _{i=1}^{\ell +u}\alpha _{i}^{*}K(x_{i},x)$

$\alpha$можно найти, написав задачу в виде линейной программы и решив двойственную задачу . Снова позволяя $K$ быть матрицей ядра и $J$ быть блочной матрицей ${\begin{bmatrix}I_{\ell }&0\\0&0_{u}\end{bmatrix}}$, можно показать, что решение

$\alpha =\left(2\gamma _{A}I+2{\frac {\gamma _{I}}{(\ell +u)^{2}}}LK\right)^{-1}J^{\mathrm {T} }Y\beta ^{*}$

где $\beta ^{*}$ это решение двойной проблемы

${\begin{aligned}&&\beta ^{*}=\max _{\beta \in \mathbf {R} ^{\ell }}&\sum _{i=1}^{\ell }\beta _{i}-{\frac {1}{2}}\beta ^{\mathrm {T} }Q\beta \\&{\text{subject to}}&&\sum _{i=1}^{\ell }\beta _{i}y_{i}=0\\&&&0\leq \beta _{i}\leq {\frac {1}{\ell }}\;i=1,\ldots ,\ell \end{aligned}}$

и $Q$ определяется

$Q=YJK\left(2\gamma _{A}I+2{\frac {\gamma _{I}}{(\ell +u)^{2}}}LK\right)^{-1}J^{\mathrm {T} }Y$

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

Ограничения

• Регуляризация многообразия предполагает, что данные с разными метками вряд ли будут находиться близко друг к другу. Именно это предположение позволяет методу извлекать информацию из немаркированных данных, но оно применимо только к некоторым проблемным областям. В зависимости от структуры данных может потребоваться использование другого алгоритма полуконтролируемого или трансдуктивного обучения.
• В некоторых наборах данных внутренняя норма функции $\left\|f\right\|_{I}$ может быть очень близко к норме окружающей среды $\left\|f\right\|_{K}$: например, если данные состоят из двух классов, лежащих на перпендикулярных прямых, внутренняя норма будет равна внешней норме. В этом случае немаркированные данные не влияют на решение, полученное в результате регуляризации многообразия, даже если данные соответствуют предположению алгоритма о том, что сепаратор должен быть гладким. подходы, связанные с совместным обучением . Для устранения этого ограничения были предложены
• Если имеется очень большое количество непомеченных примеров, матрица ядра $K$становится очень большим, и алгоритм регуляризации многообразия может стать непомерно медленным в вычислениях. В этом случае могут помочь онлайн-алгоритмы и разреженные аппроксимации многообразия.

См. также

• Многообразное обучение
• Гипотеза многообразия
• Полуконтролируемое обучение
• Трансдукция (машинное обучение)
• Спектральная теория графов
• Воспроизведение ядра гильбертова пространства
• Tikhonov regularization
• Дифференциальная геометрия

Внешние ссылки

Программное обеспечение

• Библиотека ManifoldLearn и библиотека Primal LapSVM реализуют LapRLS и LapSVM в MATLAB .
• Библиотека Dlib для C++ включает функцию регуляризации линейного многообразия.