_пособие_ Ветров Д.П._ Кропотов Д.А. Байесовские методы машинного обучения_ учебное пособие (2007) (_пособие_ Ветров Д.П._ Кропотов Д.А. Байесовские методы машинного обучения_ учебное пособие (2007).pdf), страница 15

L1регуляризацию функционала качестваmΦ(θ) = log p(x|θ) −αX|θj | → maxθ2 j=1Свойство лапласовского регуляризатораПри использовании лапласовского априорного распределения на веса, многие веса могут оказатьсяравными нулю. Это связано с тем, что использование регуляризации эквивалентно ограничению областипоиска экстремума исходной (нерегуляризованной) функции (серая область на рис. 9.1) При лапласовскомраспределении соответствющая область имеет характерные изломы, в которых может находиться условный экстремум исходной функции.

В то же время, вероятность того, что хотя бы один из весов окажетсяравным нулю при использовании гауссовского априорного распределения равна нулюГлава 9. Недиагональная регуляризация обобщенных линейных моделей98Рис. 9.1. Влияние вида регуляризатора на положение экстремума регуляризованной функции9.2Метод релевантных собственных векторов9.2.1RVM и его ограниченияРегуляризованная логистическая регрессия (напоминание)• Рассматривается стандартная задача классификации на 2 класса с обучающей выборкой (X, t) ={xi , ti }ni=1 , где x ∈ Rd и t ∈ {−1, 1}• Классификатор имеет формуt̂(x) = sign(y(xi )) = signmXwj φj (x) = sign(wT φ(x)),j=1где {φj (x)}mj=1 — множество заранее фиксированных базисных функций, а w — вектор весов, настраиваемых в ходе обучения путем максимизации регуляризованного логарифма правдоподобия¡¢wM P = arg max log p(t|X, w) − αwT w ,гдеp(t|X, w) =nY1.1 + exp(−ti y(xi ))i=1• С вероятностной точки зрения это соответствует введению гауссовского априорного распределенияна веса w с центром в нуле и ковариационной матрицей Σ = α−1 I• Назовем матрицу A = Σ−1 матрицей регуляризации.

В данном случае матрица регуляризации равнаαIГлава 9. Недиагональная регуляризация обобщенных линейных моделей99Метод релевантных векторов (напоминание)• В 1999г. М. Типпинг предложил установить индивидуальные коэффициенты регуляризации αj длякаждого веса wj .• Это соответствует использованию гауссовского априорного распределения с произвольной неотрицательно определенной диагональной матрицей регуляризацииsµ¶det(A)1 Tp(w|α) =exp − w Aw ,(2π)m2где A = diag(α1 , . .

. , αm ), αj ≥ 0.• Для определения значений коэффициентов регуляризации использовался принцип наибольшей обоснованностиZαM E = arg max p(t|X, α) = arg max p(t|X, w)p(w|α)dw.• Метод релевантных векторов обладает интересным свойством разреженности получаемого классификатора• Большинство αj уходят в +∞, эффективно исключая нерелевантные базисные функции и делаяклассификатор разреженнымНедостатки RVM• При обучении классификатора RVM требуется порядка 20–50 итераций для настройки α, на каждойиз которых приходится обучать метод регуляризованной логистической регрессии• RVM не может быть напрямую применен для лапласовского априорного распределения на весаw.

В то же время известно, что лапласовское априорное распределение обычно приводит к болееразреженным решающим правилам• И регуляризованная логистическая регрессия, и метод релевантных векторов не инвариантны относительно линейных преобразований базисных функцийЛинейная неинвариантность• Рассмотрим невырожденную матрицу L ∈ Rm×m• Пусть ψ(x) = Lφ(x) — новое множество базисных функций• Поскольку наш классификатор линеен по базисным функциям, вполне естественно требовать, чтобы классификатор, обученный по базисным функциям ψ(x), был эквивалентен классификатору,полученному при использовании базисных функций φ(x)• К сожалению, это не так в случае RVM и регуляризованной логистической регрессии9.2.2Регуляризация степеней свободыСтепени свободы• Идея: Что будет, если регуляризовывать не веса wj , а т.н.

степени свободы (направления, ассоциированные с собственными векторами гессиана логарифма правдоподобия)?• Известно, что в большинстве случаев в окрестностях точки максимума функция правдоподобиядостаточно хорошо может быть приближена гауссианой. Главные оси соответствующей матрицыковариации определяют степени свободы классификатораГлава 9. Недиагональная регуляризация обобщенных линейных моделей100w2логарифмправдоподобияu1u2wMLwMPстепени свободыw1Рис. 9.2. Регуляризация степеней свободы, ассоциированных с собственными векторами гессиана правдоподобия• Мотивация: Один и тот же вес может входить и в значимые, и в нерелевантные степени свободы• Следствие: Такая регуляризация немедленно становится инвариантной относительно линейных преобразований множества базисных функций• С точки зрения исходных весов w этот подход соответствует использованию недиагональной симметричной матрицы регуляризацииПриближение функции правдоподобия• Пусть u — новые переменные, ассоциированные с каждой степенью свободы• Приблизим правдоподобие гауссианой в точке максимума, используя приближение Лаплас൶1TTp(t|X, u) ≈ p̂(t|X, u) = p(t|X, uM L ) exp − (u − uM L ) QHQ (u − uM L ) ,2где QT = Q−1 — матрица перехода от u к w, т.е.

w = QT u• Приближенное правдоподобие p̂(t|X, u) = p̂(t|X, w) является сепарабельной функцией от u, т.е.может быть представлено в виде произведения функций, зависящих от одной компоненты вектораumYp̂(t|X, u) = p(t|X, uM L )g(uj , uM L,j , hj )j=19.2.3Оптимизация обоснованности для различных семейств априорных распределенийВычисление обоснованности• Поскольку мы ввели независимую регуляризацию каждой степени свободы uj , регуляризатор такжеявляется сепарабельной функцией от uГлава 9.

Недиагональная регуляризация обобщенных линейных моделей101• Следовательно, обоснованность представима в виде произведения одномерных интегралов, каждыйиз которых зависит только от одного коэффициента регуляризации αj , и можно оптимизировать всеαj одновременно и независимо.• Обозначив собственные вектора матрицы −H за {hj }, получаемZp(t|X, α) ≈p̂(t|X, u)p(u|α)du = p(t|X, uM L )p(t|X, uM L )m ZYZ Ymg(uj , uM L,j , hj )p(uj |αj )du =j=1g(uj , uM L,j , hj )p(uj |αj )duj = p(t|X, uM L )j=1mYfj (hj , uM L,j , αj )j=1Гауссовское априорное распределениеВ случае, когда степени свободы имеют гауссовское априорное распределение uj ∼ N (uj |0, αj−1 ), одномерный интеграл и оптимальное значение для αj могут быть получены аналитическиrfjG (hj , uM L,j , αj ) =αj2πZÃ!µ¶r2hαuhjααjjjjML,jexp − (uj − uM L,j )2 −u2 duj =exp −,22 jhj + αj2(hj + αj )(αj∗ =hj,hj u2M L,j −1+∞,если hj u2M L,j > 1иначеВ частности, условие на релевантность степени свободы удается получить в явном виде.Алгоритм 3: Метод релевантных собственных векторовВход: Обучающая выборка {xi , ti }ni=1 , xi ∈ Rd , ti ∈ {+1, −1}; Матрица обобщенных признаков Φ ={φj (xi )}n,mi,j=1 ;´³Pmwφ(x);Выход: Набор весов wM P для решающего правила t∗ (x) = signMP,jjj=11: Найти w M L = arg max p(t|X, w);2: Вычислить гессиан H = ∇∇ log p(t|X, w)|w=wM L ;3: Вычислить собственные вектора и собственные значения гессиана −H = QT ΛQ, Λ = diag(h1 , .

. . , hm );4:5:6:Вычислить uM L = QwM L ;для j = 1, . . . , mесли hj u2M L,j > 1 тоhαj∗ := hj u2 j −1 ;M L,j8:иначе9:αj∗ := +∞10: Найти w M P = arg max p(t|X, w)p(Qw|α∗ )7:Лапласовское априорное распределение• В случае, когда степени свободы имеют априорное распределение Лапласа p(uj |αj ) = L(uj |αj−1 ),интеграл также может быть вычислен аналитическиГлава 9.

Недиагональная регуляризация обобщенных линейных моделей102• Для этого разобьем интеграл на дваZfjL (hj , uM L,j , αj ) =Z+∞g(uj , uM L,j , hj )p(uj |αj )duj =−∞0Z+∞g(uj , uM L,j , hj )p(uj |αj )duj +αj4Z−∞g(uj , uM L,j , hj )p(uj |αj )duj =0¶¶µµZαjαj +∞αjhj (uj − uM L,j )2hj (uj − uM L,j )2−|uj | duj +−|uj | dujexp −exp −224 022−∞0Вычисление интегралаX Упр.• Обе «половинки» представляют собой интегралы от квадратных трехчленов под экспонентой, которые легко вычисляются с помощью «интеграла ошибок»Z +∞¡¢2erfc(x) = √exp −ξ 2 dξπ xq ³q ³´´αihiαi• Обозначим x1 = h2i 2h−u,x=+uM L,i2M L,i . Тогда можно показать , что22hiiÃ!r£¡ ¢¡ ¢¤hi u2M L,iαjπL× exp x21 erfc(x1 ) + exp x22 erfc(x2 )fj (hj , uM L,j , αj ) =exp −42hj2• Заметим, что при x1,2 существенно отличных от нуля, возникают численные трудности с вычислением этих выраженийВозникающие неопределенности• Действительно, при x > 27, выражениеexp(x2 ) > 10300и большинство программ считают его равным +∞• Аналогичная ситуация с функцией erfc(x).

При x > 26 выражениеerfc(x) < 10−300 ,что является тождественным нулем, например, для MATLAB• С другой стороны, выражение для интеграла можно преобразовать, представив его в виде произведения бесконечно больших величин на бесконечно малыеЧисленные хитрости• Пусть xj À 0, j ∈ {1, 2}, тогда можно показать, что√erfcx(xj ) = exp(x2j ) erfc(xj ) ≈ 1/( πxj )• При xj ¿ 0 объединяем exp(−hi u2M L,i /2) и exp(x2j )exp(−hi u2M L,i /2) exp(x2j ) = exp(yj ),гдеy1,2 =αi2αi uM L,i∓.8hi2Глава 9. Недиагональная регуляризация обобщенных линейных моделей103Алгоритм 4: Метод релевантных собственных векторов с лапласовским регуляризаторомВход: Обучающая выборка {xi , ti }ni=1 , xi ∈ Rd , ti ∈ {+1, −1}; Матрица обобщенных признаков Φ ={φj (xi )}n,mi,j=1 ;³P´mВыход: Набор весов wM P для решающего правила t∗ (x) = signwφ(x);MP,jjj=11: Найти w M L = arg max p(t|X, w);2: Вычислить гессиан H = ∇∇ log p(t|X, w)|w=wM L ;3: Вычислить собственные вектора и собственные значения гессиана −H = QT ΛQ, Λ = diag(h1 , .

. . , hm );Вычислить uM L = QwM L ;для j = 1, . . . , mαj∗ := arg max fjL (hj , uM L,j , αj );Найти uM P = arg max p(t|X, w)p(u|α∗ ) при условии uM L,i ui ≥ 0;8: Найти w M P = QT uM P4:5:6:7:Оптимизация функции fiL (hi , uM L,i , αi )Точка максимума функции fiL (hi , uM L,i , αi ) не может быть выписана в явном виде, поэтому необходимачисленная оптимизация (впрочем, не слишком обременительная, т.к. функция является унимодальной(см. рис. 9.3), либо наибольшее значение достигается при αi = +∞)54.543.532.521.510.50-210-110010110210310Рис.