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

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

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

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

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

Классификация

Эмпирическое изучение классификаторов (из конечного набора данных) всегда является недооцененной проблемой, поскольку оно пытается вывести функцию любого ${ 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)}$

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

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

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

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

Обобщение

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

Цель этой задачи обучения - найти функцию, которая соответствует или предсказывает результат (метку), которая минимизирует ожидаемую ошибку по всем возможным входам и меткам. Ожидаемая ошибка функции ${ 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 е (х) = вес CDOT х}$, можно добавить ${ displaystyle L_ {2}}$-норма вектора ${ displaystyle w}$ выражению потерь, чтобы предпочесть решения с меньшими нормами. Это называется тихоновской регуляризацией, одной из наиболее распространенных форм регуляризации. Это также известно как регресс гребня. Это выражается как:

${ displaystyle min _ {w} sum _ {i = 1} ^ {n} V ({ hat {x}} _ {i} cdot w, { hat {y}} _ {i}) + лямбда | ш | _ {2} ^ {2}}$

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

${ Displaystyle мин _ {е} сумма _ {я = 1} ^ {п} V (е ({ шляпа {х}} _ {я}), { шляпа {у}} _ {я}) + lambda | f | _ { mathcal {H}} ^ {2}}$

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

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

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

${ displaystyle min _ {w} { frac {1} {n}} ({ hat {X}} wY) ^ {T} ({ hat {X}} wY) + 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 leftarrow}$Это условие первого порядка для этой задачи оптимизации

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

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

Во время обучения этот алгоритм занимает ${ Displaystyle О (д ^ {3} + nd ^ {2})}$ время. Слагаемые соответствуют обращению матрицы и вычислению ${ displaystyle X ^ {T} X}$, соответственно. Тестирование занимает ${ Displaystyle О (nd)}$ время.

Ранняя остановка

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

На практике ранняя остановка реализуется путем обучения на обучающем наборе и измерения точности на статистически независимом проверочном наборе. Модель обучается до тех пор, пока производительность на проверочном наборе не перестанет улучшаться. Затем модель тестируется на тестовом наборе.

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

Рассмотрим конечное приближение Серия Неймана для обратимой матрицы А куда ${ Displaystyle | I-A | <1}$:

${ displaystyle sum _ {я = 0} ^ {T-1} (I-A) ^ {i} приблизительно 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}}}$

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

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

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

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

${ displaystyle { begin {align} 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 {align}}}$

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

${ displaystyle { begin {align} 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} { шляпа {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} { шляпа {Y}} end {выровнена}}}$

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

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

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

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

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

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

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

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

Упругая сетевая регуляризация

${ displaystyle L_ {1}}$ регуляризация может иногда приводить к неуникальным решениям. На рисунке представлен простой пример, когда пространство возможных решений лежит на линии под углом 45 градусов. Это может быть проблематичным для определенных приложений и решается путем объединения ${ displaystyle L_ {1}}$ с ${ 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] }$

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

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

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

В то время как ${ displaystyle L_ {1}}$ норма не приводит к NP-сложной проблеме, ${ displaystyle L_ {1}}$ норма выпуклая, но не является строго дифференцируемой из-за перегиба в точке x = 0. Субградиентные методы которые полагаются на субпроизводный можно использовать для решения ${ displaystyle L_ {1}}$ упорядоченные проблемы обучения. Однако более быстрая сходимость может быть достигнута проксимальными методами.

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

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

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

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

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

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

${ displaystyle S _ { lambda} (v) f (n) = { begin {case} 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 { случаи}}}$

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

Групповая разреженность без перекрытий

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

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

${ Displaystyle R (ш) = сумма _ {г = 1} ^ {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 {case}}}$

Групповая разреженность с перекрытиями

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

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

${ 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 (е) = сумма _ {я, j} w_ {ij} (f (x_ {i}) - f (x_ {j})) ^ {2}}$

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

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

Проблема оптимизации ${ Displaystyle мин _ {е in mathbb {R} ^ {m}} R (е), м = и + л}$ можно решить аналитически, если ограничение ${ 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 (ш) = сумма _ {я = 1} ^ {D} | W | _ {2,1}}$

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

Регуляризация ядерной нормы

${ Displaystyle R (ш) = | сигма (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} - { гидроразрыв {1} {I (r)}} sum _ {s in I (r)} f_ {s} | _ {H_ {k}} ^ {2}}$ куда ${ Displaystyle I (г)}$ это кластер задач.

Этот регуляризатор похож на регуляризатор со средним ограничением, но вместо этого обеспечивает сходство между задачами в одном кластере. Это может собрать более сложную априорную информацию. Этот метод использовался для прогнозирования 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), а Байесовский информационный критерий (БИК). Альтернативные методы контроля переобучения, не связанные с регуляризацией, включают: перекрестная проверка.

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

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

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

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

Примечания

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

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