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

Эта статья описывает только один узкоспециализированный аспект связанной с ней темы . Пожалуйста, помогите улучшить эту статью , добавив больше общей информации. Страница обсуждения может содержать предложения. ( Ноябрь 2020 г. )

И зеленая, и синяя функции несут нулевые потери в заданных точках данных. Выученная модель может быть склонена к предпочтению функции зеленого, которая может лучше обобщаться на большее количество точек, извлеченных из основного неизвестного распределения, путем корректировки веса члена регуляризации.${\ displaystyle \ lambda}$

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

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

В машинном обучении регуляризация - это любая модификация алгоритма обучения, предназначенная для уменьшения его ошибки обобщения, но не ошибки обучения ^[3]

Классификация [ править ]

Эмпирическое изучение классификаторов (из конечного набора данных) всегда является недооцененной проблемой, потому что оно пытается вывести функцию любых заданных только примеров .${\ displaystyle x}$${\ displaystyle x_ {1}, x_ {2}, ... x_ {n}}$

Член регуляризации (или регуляризатор) добавляется к функции потерь :${\ Displaystyle R (f)}$

${\ displaystyle \ min _ {f} \ sum _ {i = 1} ^ {n} V (f (x_ {i}), y_ {i}) + \ lambda R (f)}$

где - базовая функция потерь, которая описывает стоимость прогнозирования того, когда метка , например, потери площади или потери на шарнире ; и является параметром, который контролирует важность члена регуляризации. обычно выбирается для наложения штрафа на сложность . Используемые конкретные понятия сложности включают ограничения на гладкость и границы нормы векторного пространства . ^{[4] [ необходима страница ]}${\ displaystyle V}$${\ displaystyle f (x)}$${\ displaystyle y}$${\ displaystyle \ lambda}$${\ Displaystyle R (f)}$${\ displaystyle f}$

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

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

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

Обобщение [ править ]

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

Цель этой задачи обучения - найти функцию, которая соответствует или предсказывает результат (метку), которая минимизирует ожидаемую ошибку по всем возможным входам и меткам. Ожидаемая ошибка функции :${\ displaystyle f_ {n}}$

${\ Displaystyle I [f_ {n}] = \ int _ {X \ times Y} V (f_ {n} (x), y) \ rho (x, y) \, dx \, dy}$

где и - области входных данных и их метки соответственно.${\ displaystyle X}$${\displaystyle Y}$${\displaystyle x}$${\displaystyle y}$

Обычно в задачах обучения доступна только часть входных данных и меток, измеренных с некоторым шумом. Следовательно, ожидаемая ошибка неизмерима, и лучший доступный суррогат - это эмпирическая ошибка по доступным выборкам:${\displaystyle N}$

${\displaystyle I_{S}[f_{n}]={\frac {1}{n}}\sum _{i=1}^{N}V(f_{n}({\hat {x}}_{i}),{\hat {y}}_{i})}$

Без ограничений на сложность доступного функционального пространства (формально, гильбертова пространства воспроизводящего ядра ) будет изучена модель, которая несет нулевые потери на суррогатную эмпирическую ошибку. Если измерения (например, ) были выполнены с шумом, эта модель может страдать от переобучения и отображать плохую ожидаемую ошибку. Регуляризация вводит штраф за исследование определенных областей функционального пространства, используемого для построения модели, что может улучшить обобщение.${\displaystyle x_{i}}$

Тихоновская регуляризация [ править ]

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

При изучении линейной функции , характеризующейся неизвестном вектором таким образом, что можно добавить -норм вектора к выражению потери для того , предпочитать решения с меньшими нормами. Тихоновская регуляризация - одна из самых распространенных форм. Это также известно как регресс гребня. Это выражается как:${\displaystyle f}$ ${\displaystyle w}$${\displaystyle f(x)=w\cdot x}$${\displaystyle L_{2}}$${\displaystyle w}$

${\displaystyle \min _{w}\sum _{i=1}^{n}V({\hat {x}}_{i}\cdot w,{\hat {y}}_{i})+\lambda \|w\|_{2}^{2}}$

В случае общей функции норма функции в ее воспроизводящем ядре гильбертовом пространстве равна:

${\displaystyle \min _{f}\sum _{i=1}^{n}V(f({\hat {x}}_{i}),{\hat {y}}_{i})+\lambda \|f\|_{\mathcal {H}}^{2}}$

Поскольку норма дифференцируема , обучение можно продвигать путем градиентного спуска .${\displaystyle L_{2}}$

Регуляризованный по Тихонову метод наименьших квадратов [ править ]

Задачу обучения с функцией потерь по методу наименьших квадратов и регуляризацией Тихонова можно решить аналитически. Записанный в матричной форме, оптимальным считается тот, для которого градиент функции потерь по отношению к равен 0.${\displaystyle w}$${\displaystyle w}$

${\displaystyle \min _{w}{\frac {1}{n}}({\hat {X}}w-Y)^{T}({\hat {X}}w-Y)+\lambda \|w\|_{2}^{2}}$

${\displaystyle \nabla _{w}={\frac {2}{n}}{\hat {X}}^{T}({\hat {X}}w-Y)+2\lambda w}$

${\displaystyle 0={\hat {X}}^{T}({\hat {X}}w-Y)+n\lambda w}$    ( условие первого порядка )

${\displaystyle w=({\hat {X}}^{T}{\hat {X}}+\lambda nI)^{-1}({\hat {X}}^{T}Y)}$

При построении задачи оптимизации другие значения дают большие значения для функции потерь. В этом можно убедиться, исследуя вторую производную .${\displaystyle w}$ ${\displaystyle \nabla _{ww}}$

Во время обучения этот алгоритм требует времени . Члены соответствуют обращению матрицы и вычислению соответственно. Тестирование требует времени.${\displaystyle O(d^{3}+nd^{2})}$ ${\displaystyle X^{T}X}$${\displaystyle O(nd)}$

Ранняя остановка [ править ]

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

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

Теоретическая мотивация методом наименьших квадратов [ править ]

Рассмотрим конечную аппроксимацию ряда Неймана для обратимой матрицы A, где :${\displaystyle \|I-A\|<1}$

${\displaystyle \sum _{i=0}^{T-1}(I-A)^{i}\approx A^{-1}}$

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

${\displaystyle w_{T}={\frac {\gamma }{n}}\sum _{i=0}^{T-1}(I-{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {X}})^{i}{\hat {X}}^{T}{\hat {Y}}}$

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

Вышеупомянутый алгоритм эквивалентен ограничению количества итераций градиентного спуска для эмпирического риска

${\displaystyle I_{s}[w]={\frac {1}{2n}}\|{\hat {X}}w-{\hat {Y}}\|_{\mathbb {R} ^{n}}^{2}}$

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

${\displaystyle {\begin{aligned}w_{0}&=0\\w_{t+1}&=(I-{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {X}})w_{t}+{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {Y}}\end{aligned}}}$

Базовый случай тривиален. Индуктивный случай доказывается следующим образом:

${\displaystyle {\begin{aligned}w_{T}&=(I-{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {X}}){\frac {\gamma }{n}}\sum _{i=0}^{T-2}(I-{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {X}})^{i}{\hat {X}}^{T}{\hat {Y}}+{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {Y}}\\&={\frac {\gamma }{n}}\sum _{i=1}^{T-1}(I-{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {X}})^{i}{\hat {X}}^{T}{\hat {Y}}+{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {Y}}\\&={\frac {\gamma }{n}}\sum _{i=0}^{T-1}(I-{\frac {\gamma }{n}}{\hat {X}}^{T}{\hat {X}})^{i}{\hat {X}}^{T}{\hat {Y}}\end{aligned}}}$

Регуляризаторы для разреженности [ править ]

Предположим, что дан словарь с размерностью так , что функция в функциональном пространстве может быть выражена как:${\displaystyle \phi _{j}}$${\displaystyle p}$

${\displaystyle f(x)=\sum _{j=1}^{p}\phi _{j}(x)w_{j}}$

Применение ограничения разреженности может привести к более простым и интерпретируемым моделям. Это полезно во многих реальных приложениях, таких как вычислительная биология . Примером может служить разработка простого прогностического теста на заболевание, чтобы минимизировать затраты на выполнение медицинских тестов при максимальной прогностической способности.${\displaystyle w}$

Разумное ограничение разреженности - это норма , определяемая как количество ненулевых элементов в . Однако решение регуляризованной проблемы обучения оказалось NP-трудным . ^[6] L 0 {\displaystyle L_{0}} ${\displaystyle \|w\|_{0}}$${\displaystyle w}$${\displaystyle L_{0}}$

Норма (смотрите также Нормы ) может быть использована для аппроксимации оптимальной нормы с помощью выпуклой релаксации. Можно показать, что норма порождает разреженность. В случае метода наименьших квадратов эта проблема известна как LASSO в статистике и поиск базиса в обработке сигналов. L 1 {\displaystyle L_{1}} L 0 {\displaystyle L_{0}} L 1 {\displaystyle L_{1}}

${\displaystyle \min _{w\in \mathbb {R} ^{p}}{\frac {1}{n}}\|{\hat {X}}w-{\hat {Y}}\|^{2}+\lambda \|w\|_{1}}$

L 1 {\displaystyle L_{1}} регуляризация может иногда приводить к неуникальным решениям. На рисунке представлен простой пример, когда пространство возможных решений лежит на линии под углом 45 градусов. Это может быть проблематичным для определенных приложений и преодолеваться путем комбинирования с регуляризацией в эластичной сетевой регуляризации , которая принимает следующую форму: L 1 {\displaystyle L_{1}} L 2 {\displaystyle L_{2}}

${\displaystyle \min _{w\in \mathbb {R} ^{p}}{\frac {1}{n}}\|{\hat {X}}w-{\hat {Y}}\|^{2}+\lambda (\alpha \|w\|_{1}+(1-\alpha )\|w\|_{2}^{2}),\alpha \in [0,1]}$

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

Упругая сетевая регуляризация широко используется на практике и реализована во многих библиотеках машинного обучения.

Проксимальные методы [ править ]

Хотя норма не приводит к NP-трудной проблеме, норма выпуклая, но не строго дифференцируема [ sic ? ] из-за перегиба при x = 0. Методы субградиента, которые полагаются на субпроизводную, можно использовать для решения регуляризованных задач обучения. Однако более быстрая сходимость может быть достигнута проксимальными методами. L 1 {\displaystyle L_{1}} L 1 {\displaystyle L_{1}} L 1 {\displaystyle L_{1}}

Для такой задачи , которая является выпуклой, непрерывной, дифференцируемой, с непрерывным липшицевым градиентом (например, функцией потерь по методу наименьших квадратов) и является выпуклой, непрерывной и правильной, тогда ближайший метод решения проблемы выглядит следующим образом. Сначала определим проксимальный оператор${\displaystyle \min _{w\in H}F(w)+R(w)}$${\displaystyle F}$${\displaystyle R}$

${\displaystyle \operatorname {prox} _{R}(v)=\operatorname {argmin} \limits _{w\in \mathbb {R} ^{D}}\{R(w)+{\frac {1}{2}}\|w-v\|^{2}\},}$

а затем повторить

${\displaystyle w_{k+1}=\operatorname {prox} \limits _{\gamma ,R}(w_{k}-\gamma \nabla F(w_{k}))}$

Проксимальный метод итеративно выполняет градиентный спуск, а затем проецирует результат обратно в пространство, разрешенное .${\displaystyle R}$

Когда - регуляризатор, проксимальный оператор эквивалентен оператору мягкой пороговой обработки,${\displaystyle R}$ L 1 {\displaystyle L_{1}}

${\displaystyle S_{\lambda }(v)f(n)={\begin{cases}v_{i}-\lambda ,&{\text{if }}v_{i}>\lambda \\0,&{\text{if }}v_{i}\in [-\lambda ,\lambda ]\\v_{i}+\lambda ,&{\text{if }}v_{i}<-\lambda \end{cases}}}$

Это позволяет проводить эффективные вычисления.

Редкость группы без перекрытий [ править ]

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

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

${\displaystyle R(w)=\sum _{g=1}^{G}\|w_{g}\|_{2},}$ куда ${\displaystyle \|w_{g}\|_{2}={\sqrt {\sum _{j=1}^{|G_{g}|}(w_{g}^{j})^{2}}}}$

Это можно рассматривать как введение регуляризатора по норме по членам каждой группы, за которой следует норма по группам.${\displaystyle L_{2}}$${\displaystyle L_{1}}$

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

${\displaystyle \operatorname {prox} \limits _{\lambda ,R,g}(w_{g})={\begin{cases}(1-{\frac {\lambda }{\|w_{g}\|_{2}}})w_{g},&{\text{if }}\|w_{g}\|_{2}>\lambda \\0,&{\text{if }}\|w_{g}\|_{2}\leq \lambda \end{cases}}}$

Редкость группы с перекрытиями [ править ]

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

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

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

Для каждого , определяются как вектор , такие , что ограничение на группы равные и все остальные записи равен нуль. Регуляризатор находит оптимальное разделение на части. Его можно рассматривать как дублирование всех элементов, которые существуют в нескольких группах. Проблемы обучения с помощью этого регуляризатора также могут быть решены проксимальным методом с некоторыми осложнениями. Ближайший оператор не может быть вычислен в замкнутой форме, но может эффективно решаться итеративно, вызывая внутреннюю итерацию в ближайшей итерации метода.${\displaystyle w_{g}}$${\displaystyle {\bar {w}}_{g}}$${\displaystyle {\bar {w}}_{g}}$${\displaystyle g}$${\displaystyle w_{g}}$${\displaystyle {\bar {w}}_{g}}$${\displaystyle w}$

Регуляризаторы для обучения без учителя [ править ]

Когда сбор меток обходится дороже, чем входные примеры, может быть полезно полу-контролируемое обучение. Регуляризаторы были разработаны, чтобы направлять алгоритмы обучения для изучения моделей, которые учитывают структуру обучающих выборок без учителя. Если дана симметричная весовая матрица , можно определить регуляризатор:${\displaystyle W}$

${\displaystyle R(f)=\sum _{i,j}w_{ij}(f(x_{i})-f(x_{j}))^{2}}$

Если кодирует результат некоторой метрики расстояния для точек и , желательно, чтобы . Этот регуляризатор улавливает эту интуицию и эквивалентен:${\displaystyle W_{ij}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle f(x_{i})\approx f(x_{j})}$

${\displaystyle R(f)={\bar {f}}^{T}L{\bar {f}}}$где - матрица Лапласа графа, индуцированного .${\displaystyle L=D-W}$${\displaystyle W}$

Задача оптимизации может быть решена аналитически, если ограничение применяется ко всем контролируемым выборкам. Поэтому отмеченная часть вектора очевидна. Непомеченная часть решается за:${\displaystyle \min _{f\in \mathbb {R} ^{m}}R(f),m=u+l}$${\displaystyle f(x_{i})=y_{i}}$${\displaystyle f}$${\displaystyle f}$

${\displaystyle \min _{f_{u}\in \mathbb {R} ^{u}}f^{T}Lf=\min _{f_{u}\in \mathbb {R} ^{u}}\{f_{u}^{T}L_{uu}f_{u}+f_{l}^{T}L_{lu}f_{u}+f_{u}^{T}L_{ul}f_{l}\}}$

${\displaystyle \nabla _{f_{u}}=2L_{uu}f_{u}+2L_{ul}Y}$

${\displaystyle f_{u}=L_{uu}^{\dagger }(L_{ul}Y)}$

Обратите внимание, что псевдообратное значение может быть взято, потому что оно имеет тот же диапазон, что и .${\displaystyle L_{ul}}$${\displaystyle L_{uu}}$

Регуляризаторы для многозадачного обучения [ править ]

В случае многозадачного обучения проблемы рассматриваются одновременно, каждая из которых каким-то образом связана. Цель состоит в том, чтобы изучить функции, в идеале заимствуя силу из взаимосвязи задач, которые обладают предсказательной силой. Это эквивалентно изучению матрицы .${\displaystyle T}$${\displaystyle T}$${\displaystyle W:T\times D}$

Разреженный регуляризатор столбцов [ править ]

${\displaystyle R(w)=\sum _{i=1}^{D}\|W\|_{2,1}}$

Этот регуляризатор определяет норму L2 для каждого столбца и норму L1 для всех столбцов. Ее можно решить проксимальными методами.

Регуляризация ядерных норм [ править ]

${\displaystyle R(w)=\|\sigma (W)\|_{1}}$где это собственные значения в сингулярном разложении в .${\displaystyle \sigma (W)}$${\displaystyle W}$

Регуляризация с ограничениями по среднему значению [ править ]

${\displaystyle R(f_{1}\cdots f_{T})=\sum _{t=1}^{T}\|f_{t}-{\frac {1}{T}}\sum _{s=1}^{T}f_{s}\|_{H_{k}}^{2}}$

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

Кластерная регуляризация с ограничениями по среднему [ править ]

${\displaystyle R(f_{1}\cdots f_{T})=\sum _{r=1}^{C}\sum _{t\in I(r)}\|f_{t}-{\frac {1}{I(r)}}\sum _{s\in I(r)}f_{s}\|_{H_{k}}^{2}}$где кластер задач.${\displaystyle I(r)}$

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

Сходство на основе графиков [ править ]

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

${\displaystyle R(f_{1}\cdots f_{T})=\sum _{t,s=1,t\neq s}^{T}\|f_{t}-f_{s}\|^{2}M_{ts}}$для данной симметричной матрицы подобия .${\displaystyle M}$

Другие способы использования регуляризации в статистике и машинном обучении [ править ]

Байесовские методы обучения используют априорную вероятность, которая (обычно) дает более низкую вероятность более сложным моделям. Хорошо известные методы выбора модели включают информационный критерий Акаике (AIC), минимальную длину описания (MDL) и байесовский информационный критерий (BIC). Альтернативные методы контроля переобучения, не связанные с регуляризацией, включают перекрестную проверку .

Примеры применения различных методов регуляризации к линейной модели :

Модель	Подходящая мера	Мера энтропии [4] [7]
AIC / BIC	${\displaystyle \|Y-X\beta \|_{2}}$	${\displaystyle \|\beta \|_{0}}$
Регрессия хребта [8]	${\displaystyle \|Y-X\beta \|_{2}}$	${\displaystyle \|\beta \|_{2}}$
Лассо [9]	${\displaystyle \|Y-X\beta \|_{2}}$	${\displaystyle \|\beta \|_{1}}$
Основное стремление к шумоподавлению	${\displaystyle \|Y-X\beta \|_{2}}$	${\displaystyle \lambda \|\beta \|_{1}}$
Модель Рудина – Ошера – Фатеми (ТВ)	${\displaystyle \|Y-X\beta \|_{2}}$	${\displaystyle \lambda \|\nabla \beta \|_{1}}$
Модель Поттса	${\displaystyle \|Y-X\beta \|_{2}}$	${\displaystyle \lambda \|\nabla \beta \|_{0}}$
RLAD [10]	${\displaystyle \|Y-X\beta \|_{1}}$	${\displaystyle \|\beta \|_{1}}$
Селектор Данцига [11]	${\displaystyle \|X^{\top }(Y-X\beta )\|_{\infty }}$	${\displaystyle \|\beta \|_{1}}$
НАКЛОН [12]	${\displaystyle \|Y-X\beta \|_{2}}$	${\displaystyle \sum _{i=1}^{p}\lambda _{i}|\beta |_{(i)}}$

См. Также [ править ]

• Байесовская интерпретация регуляризации
• Компромисс смещения и дисперсии
• Матричная регуляризация
• Регуляризация с помощью спектральной фильтрации
• Регуляризованный метод наименьших квадратов
• Множитель Лагранжа

Заметки [ править ]

Ссылки [ править ]

• Ноймайер, А. (1998). «Решение плохо обусловленных и сингулярных линейных систем: Учебное пособие по регуляризации» (PDF) . SIAM Обзор . 40 (3): 636–666. DOI : 10.1137 / S0036144597321909 .