Тихоновская регуляризация - Tikhonov regularization

Часть серии о
Регрессионный анализ
Модели
Линейная регрессия Простая регрессия Полиномиальная регрессия Общая линейная модель
Обобщенная линейная модель Дискретный выбор Биномиальная регрессия Бинарная регрессия Логистическая регрессия Полиномиальная логистическая регрессия Смешанный логит Пробит Полиномиальный пробит Заказал логит Заказал пробит Пуассон
Многоуровневая модель Фиксированные эффекты Случайные эффекты Линейная модель смешанных эффектов Нелинейная модель смешанных эффектов
Нелинейная регрессия Непараметрический Полупараметрический Крепкий Квантиль Изотонический Основные компоненты Наименьший угол Местный Сегментированный
Ошибки в переменных
Предварительный расчет
Наименьших квадратов Линейный Нелинейный
Обычный Взвешенный Обобщенный
Частичное Общий Неотрицательный Регрессия хребта Регулярный
Наименьшие абсолютные отклонения Итеративно переназначенный Байесовский Байесовская многомерная
Фон
Проверка регрессии Средний и прогнозируемый ответ Ошибки и остатки Доброта подгонки Студентизированный остаток Теорема Гаусса – Маркова
Математический портал
v т е

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

В простейшем случае проблема матрицы моментов, близких к сингулярным , облегчается добавлением положительных элементов к диагоналям , тем самым уменьшая ее число обусловленности . По аналогии с обычной оценкой методом наименьших квадратов , простая оценка гребня в этом случае имеет вид ${\ Displaystyle (\ mathbf {X} ^ {\ mathsf {T}} \ mathbf {X})}$

${\ displaystyle {\ hat {\ beta}} _ {R} = (\ mathbf {X} ^ {\ mathsf {T}} \ mathbf {X} + \ lambda \ mathbf {I}) ^ {- 1} \ mathbf {X} ^ {\ mathsf {T}} \ mathbf {y}}$

где - регрессион , - матрица плана , - единичная матрица , а параметр гребня служит константой, смещающей диагонали матрицы моментов. Можно показать, что эта оценка является решением задачи наименьших квадратов с учетом ограничения , которое может быть выражено в виде лагранжиана: ${\ displaystyle \ mathbf {y}}$${\ displaystyle \ mathbf {X}}$${\ displaystyle \ mathbf {I}}$${\ displaystyle \ lambda \ geq 0}$ ${\ displaystyle \ beta ^ {\ mathsf {T}} \ beta = c}$

${\ Displaystyle \ мин _ {\ бета} \, (\ mathbf {y} - \ mathbf {X} \ beta) ^ {\ mathsf {T}} (\ mathbf {y} - \ mathbf {X} \ beta) + \ lambda (\ beta ^ {\ mathsf {T}} \ beta -c)}$

что показывает, что это не что иное, как множитель Лагранжа ограничения. В случае , когда ограничение не является обязательным , оценка гребня сводится к обычным методам наименьших квадратов . Более общий подход к регуляризации Тихонова обсуждается ниже. ${\ displaystyle \ lambda}$${\ displaystyle \ lambda = 0}$

История

Тихоновская регуляризация была изобретена независимо во многих различных контекстах. Он стал широко известен благодаря его применению к интегральным уравнениям из работ Андрея Тихонова и Дэвида Л. Филлипса. Некоторые авторы используют термин регуляризация Тихонова – Филлипса . Конечномерный случай был изложен Артуром Э. Хорлом , который использовал статистический подход, и Манусом Фостером, который интерпретировал этот метод как фильтр Винера – Колмогорова (Кригинга) . Вслед за Хёрлом в статистической литературе она известна как гребневая регрессия.

Тихоновская регуляризация

Предположим, что для известной матрицы и вектора мы хотим найти такой вектор , что ${\ displaystyle A}$${\ displaystyle \ mathbf {b}}$${\ displaystyle \ mathbf {x}}$

${\ displaystyle A \ mathbf {x} = \ mathbf {b}.}$

Стандартный подход - это обычная линейная регрессия методом наименьших квадратов . Однако, если ни один из них не удовлетворяет уравнению или удовлетворяет более одного - то есть решение не единственное, - проблема считается некорректной . В таких случаях обычная оценка методом наименьших квадратов приводит к переопределенной или, чаще, недоопределенной системе уравнений. Большинство реальных явлений имеют эффект фильтров нижних частот в прямом направлении , в котором сопоставляется с . Следовательно, при решении обратной задачи обратное отображение работает как фильтр верхних частот, который имеет нежелательную тенденцию к усилению шума ( собственные значения / сингулярные значения являются наибольшими при обратном отображении, где они были наименьшими при прямом отображении). Кроме того, обычный метод наименьших квадратов неявно обнуляет каждый элемент реконструированной версии, который находится в нулевом пространстве , вместо того, чтобы позволить использовать модель в качестве априорной для . Обычный метод наименьших квадратов стремится минимизировать сумму квадратов остатков , которую можно компактно записать как ${\ displaystyle \ mathbf {x}}$${\ displaystyle \ mathbf {x}}$${\ displaystyle A}$${\ displaystyle \ mathbf {x}}$${\ displaystyle \ mathbf {b}}$${\ displaystyle \ mathbf {x}}$${\ displaystyle A}$${\ displaystyle \ mathbf {x}}$

${\ displaystyle \ | A \ mathbf {x} - \ mathbf {b} \ | _ {2} ^ {2},}$

где - евклидова норма . ${\ Displaystyle \ | \ cdot \ | _ {2}}$

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

${\ displaystyle \ | A \ mathbf {x} - \ mathbf {b} \ | _ {2} ^ {2} + \ | \ Gamma \ mathbf {x} \ | _ {2} ^ {2}}$

для некоторой правильно подобранной матрицы Тихонова . Во многих случаях эта матрица выбирается как кратная единичной матрице ( ), отдавая предпочтение решениям с меньшими нормами ; это известно как регуляризация L ₂ . В других случаях могут использоваться высокочастотные операторы (например, оператор разности или взвешенный оператор Фурье ) для обеспечения гладкости, если основной вектор считается в основном непрерывным. Эта регуляризация улучшает условия задачи, что позволяет получить прямое численное решение. Явное решение, обозначенное как , дается формулой ${\ displaystyle \ Gamma}$${\ displaystyle \ Gamma = \ alpha I}$${\ displaystyle {\ hat {x}}}$

${\ displaystyle {\ hat {x}} = (A ^ {\ top} A + \ Gamma ^ {\ top} \ Gamma) ^ {- 1} A ^ {\ top} \ mathbf {b}.}$

Эффект регуляризации может варьироваться в зависимости от масштаба матрицы . Для этого сводится к решению нерегуляризованное наименьших квадратов, при условии , что (А ^Т А) ^-1 существует. ${\ displaystyle \ Gamma}$${\ displaystyle \ Gamma = 0}$

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

Обобщенная тихоновская регуляризация

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

${\ displaystyle \ | Ax-b \ | _ {P} ^ {2} + \ | x-x_ {0} \ | _ {Q} ^ {2},}$

где мы привыкли обозначать квадрат взвешенной нормы (сравните с расстоянием Махаланобиса ). В байесовской интерпретации является обратной матрицей ковариаций из , представляет собой ожидаемое значение из , и является обратной ковариационной матрицей . Затем матрица Тихонова задается как факторизация матрицы (например, факторизация Холецкого ) и считается отбеливающим фильтром . ${\ Displaystyle \ | х \ | _ {Q} ^ {2}}$${\ displaystyle x ^ {\ top} Qx}$${\ displaystyle P}$${\ displaystyle b}$${\ displaystyle x_ {0}}$${\ displaystyle x}$${\ displaystyle Q}$${\ displaystyle x}$${\ Displaystyle Q = \ Gamma ^ {\ top} \ Gamma}$

Эта обобщенная задача имеет оптимальное решение, которое можно явно записать по формуле ${\ displaystyle x ^ {*}}$

${\ displaystyle x ^ {*} = (A ^ {\ top} PA + Q) ^ {- 1} (A ^ {\ top} Pb + Qx_ {0}),}$

или эквивалентно

${\ displaystyle x ^ {*} = x_ {0} + (A ^ {\ top} PA + Q) ^ {- 1} (A ^ {\ top} P (b-Ax_ {0})).}$

Лаврентьевская регуляризация

В некоторых ситуациях можно избежать использования транспонирования , предложенного Михаилом Лаврентьевым . Например, if является симметричным положительно определенным, т. Е. То же самое и обратным ему , которое, таким образом, может использоваться для установки квадрата взвешенной нормы в обобщенной регуляризации Тихонова, что приводит к минимизации ${\ displaystyle A ^ {\ top}}$${\ displaystyle A}$${\ displaystyle A = A ^ {\ top}> 0}$${\ displaystyle A ^ {- 1}}$${\ Displaystyle \ | х \ | _ {P} ^ {2} = x ^ {\ top} A ^ {- 1} x}$

${\ displaystyle \ | Ax-b \ | _ {A ^ {- 1}} ^ {2} + \ | x-x_ {0} \ | _ {Q} ^ {2}}$

или, что то же самое, с точностью до постоянного члена,

${\ displaystyle x ^ {\ top} (A + Q) x-2x ^ {\ top} (b + Qx)}$.

Эта задача минимизации имеет оптимальное решение, которое можно явно записать по формуле ${\ displaystyle x ^ {*}}$

${\ displaystyle x ^ {*} = (A + Q) ^ {- 1} (b + Qx_ {0})}$,

что есть не что иное, как решение обобщенной проблемы Тихонова, где ${\ displaystyle A = A ^ {\ top} = P ^ {- 1}.}$

Регуляризация Лаврентьева, если применима, выгодна исходной регуляризации Тихонова, поскольку матрица Лаврентьева может быть лучше обусловлена, т. Е. Иметь меньшее число обусловленности , по сравнению с матрицей Тихонова${\ displaystyle A + Q}$${\ displaystyle A ^ {\ top} A + \ Gamma ^ {\ top} \ Gamma.}$

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

Обычно дискретные линейные плохо обусловленные задачи возникают в результате дискретизации интегральных уравнений , и можно сформулировать регуляризацию Тихонова в исходном бесконечномерном контексте. Вышесказанное мы можем интерпретировать как компактный оператор в гильбертовых пространствах , и как элементы в области определения и области значений . Тогда оператор является самосопряженным ограниченным обратимым оператором. ${\ displaystyle A}$${\ displaystyle x}$${\ displaystyle b}$${\ displaystyle A}$${\ Displaystyle A ^ {*} A + \ Gamma ^ {\ top} \ Gamma}$

Связь с сингулярным разложением и фильтром Винера

При этом решение методом наименьших квадратов может быть проанализировано особым образом с использованием разложения по сингулярным числам . Учитывая разложение по сингулярным числам ${\ displaystyle \ Gamma = \ alpha I}$

${\ Displaystyle A = U \ Sigma V ^ {\ top}}$

с сингулярными значениями регуляризованное решение Тихонова может быть выражено как ${\ displaystyle \ sigma _ {я}}$

${\ displaystyle {\ hat {x}} = VDU ^ {\ top} b,}$

где имеет диагональные значения ${\ displaystyle D}$

${\ displaystyle D_ {ii} = {\ frac {\ sigma _ {i}} {\ sigma _ {i} ^ {2} + \ alpha ^ {2}}}}$

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

Наконец, это связано с фильтром Винера :

${\ displaystyle {\ hat {x}} = \ sum _ {i = 1} ^ {q} f_ {i} {\ frac {u_ {i} ^ {\ top} b} {\ sigma _ {i}} } v_ {i},}$

где веса Винера и является ранг из . ${\ displaystyle f_ {i} = {\ frac {\ sigma _ {i} ^ {2}} {\ sigma _ {i} ^ {2} + \ alpha ^ {2}}}}$${\ displaystyle q}$${\ displaystyle A}$

Определение фактора Тихонова

Оптимальный параметр регуляризации обычно неизвестен и часто в практических задачах определяется специальным методом. Возможный подход основан на байесовской интерпретации, описанной ниже. Другие подходы включают принцип несоответствия , перекрестную проверку , метод L-кривой , ограничение максимального правдоподобия и непредвзятую прогнозную оценку риска . Грейс Вахба доказала, что оптимальный параметр в смысле перекрестной проверки без исключения минимизирует ${\ displaystyle \ alpha}$

${\ displaystyle G = {\ frac {\ operatorname {RSS}} {\ tau ^ {2}}} = {\ frac {\ | X {\ hat {\ beta}} - y \ | ^ {2}} { [\ operatorname {Tr} (IX (X ^ {T} X + \ alpha ^ {2} I) ^ {- 1} X ^ {T})] ^ {2}}},}$

где - остаточная сумма квадратов , - эффективное число степеней свободы . ${\ displaystyle \ operatorname {RSS}}$${\ Displaystyle \ тау}$

Используя предыдущую декомпозицию SVD, мы можем упростить приведенное выше выражение:

${\ displaystyle \ operatorname {RSS} = \ left \ | y- \ sum _ {i = 1} ^ {q} (u_ {i} 'b) u_ {i} \ right \ | ^ {2} + \ left \ | \ sum _ {i = 1} ^ {q} {\ frac {\ alpha ^ {2}} {\ sigma _ {i} ^ {2} + \ alpha ^ {2}}} (u_ {i} 'б) u_ {i} \ right \ | ^ {2},}$

${\ displaystyle \ operatorname {RSS} = \ operatorname {RSS} _ {0} + \ left \ | \ sum _ {i = 1} ^ {q} {\ frac {\ alpha ^ {2}} {\ sigma _ {i} ^ {2} + \ alpha ^ {2}}} (u_ {i} 'b) u_ {i} \ right \ | ^ {2},}$

а также

${\ displaystyle \ tau = m- \ sum _ {i = 1} ^ {q} {\ frac {\ sigma _ {i} ^ {2}} {\ sigma _ {i} ^ {2} + \ alpha ^ {2}}} = m-q + \ sum _ {i = 1} ^ {q} {\ frac {\ alpha ^ {2}} {\ sigma _ {i} ^ {2} + \ alpha ^ {2} }}.}$

Отношение к вероятностной формулировке

Вероятностная формулировка обратной задачи вводит (когда все неопределенности являются гауссовыми) ковариационная матрица, представляющая априорные неопределенности для параметров модели, и ковариационную матрицу, представляющую неопределенности для наблюдаемых параметров. В частном случае, когда эти две матрицы являются диагональными и изотропными, и , и, в этом случае, уравнения обратной теории сводятся к уравнениям выше, с . ${\ displaystyle C_ {M}}$${\ displaystyle C_ {D}}$${\ Displaystyle C_ {M} = \ sigma _ {M} ^ {2} I}$${\ Displaystyle C_ {D} = \ sigma _ {D} ^ {2} I}$${\ displaystyle \ alpha = {\ sigma _ {D}} / {\ sigma _ {M}}}$

Байесовская интерпретация

Хотя поначалу выбор решения этой регуляризованной проблемы может показаться искусственным, да и сама матрица кажется довольно произвольной, этот процесс может быть оправдан с байесовской точки зрения . Обратите внимание, что для некорректно поставленной задачи необходимо обязательно ввести некоторые дополнительные предположения, чтобы получить единственное решение. Статистически априорное распределение вероятностей иногда считается многомерным нормальным распределением . Для простоты здесь сделаны следующие предположения: средние значения равны нулю; их компоненты независимы; компоненты имеют одинаковое стандартное отклонение . Данные также подвержены ошибкам, и ошибки также считаются независимыми с нулевым средним и стандартным отклонением . При этих предположениях регуляризованное по Тихонову решение является наиболее вероятным решением с учетом данных и априорного распределения согласно теореме Байеса . ${\ displaystyle \ Gamma}$${\ displaystyle x}$ ${\ displaystyle \ sigma _ {x}}$${\ displaystyle b}$${\ displaystyle \ sigma _ {b}}$${\ displaystyle x}$

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

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

• Оценщик LASSO - еще один метод регуляризации в статистике.
• Упругая сетевая регуляризация
• Матричная регуляризация

Примечания

использованная литература

дальнейшее чтение

• Грубер, Марвин (1998). Повышение эффективности за счет сжатия: оценки регрессии Джеймса – Стейна и Риджа . Бока-Ратон: CRC Press. ISBN 0-8247-0156-9.
• Кресс, Райнер (1998). «Тихоновская регуляризация» . Численный анализ . Нью-Йорк: Спрингер. С. 86–90. ISBN 0-387-98408-9.
• Нажмите, WH; Теукольский, С.А.; Феттерлинг, штат Вашингтон; Фланнери, ВР (2007). «Раздел 19.5. Методы линейной регуляризации» . Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8.
• Салех, AK Md. Ehsanes; Араши, Мохаммад; Кибрия, Б.М. Голам (2019). Теория оценки хребтовой регрессии с приложениями . Нью-Йорк: Джон Вили и сыновья. ISBN 978-1-118-64461-4.
• Тэдди, Мэтт (2019). «Регуляризация» . Наука о бизнес-данных: сочетание машинного обучения и экономики для оптимизации, автоматизации и ускорения принятия бизнес-решений . Нью-Йорк: Макгроу-Хилл. С. 69–104. ISBN 978-1-260-45277-8.