_пособие_ Ветров Д.П._ Кропотов Д.А. Байесовские методы машинного обучения_ учебное пособие (2007) (1185333), страница 16
Текст из файла (страница 16)
9.3. Поведение функции fiL (hi , uM L,i , αi ) при разных значениях αi410Глава 10Общее решение для недиагональнойрегуляризацииВ главе представлена схема получения наиболее обоснованного регуляризатора для обобщенных линейныхмоделей классификации и произвольной неотрицательной матрицей регуляризации. Подробное вниманиеуделено математическим преобразованиям, позволяющим свести сложную задачу условной матричнойоптимизации к простому виду. Также в главе приводятся правила дифференцирования по матрице и повектору.104Глава 10.
Общее решение для недиагональной регуляризации10.1105Ликбез: Дифференцирование по вектору и по матрицеДифференцирование по вектору• Пусть f (x) — некоторая скалярная функция, зависящая от вектора x ∈ Rn . Тогда ее производнаяпо вектору по определению естьµ¶∂f (x)∂f (x)∂f (x)=,...,= ∇f (x)∂x∂x1∂xn• Пусть f (x) = (f1 (x), . . . , fm (x))T — некоторая векторная функция от скалярной переменной x ∈ R.Тогда ее производная по аргументу по определению есть∂f (x)=∂xµ∂f1 (x)∂fm (x),...,∂x∂x¶T• Пусть f (x) = (f1 (x), . . .
, fm (x))T — некоторая векторная функция, зависящая от вектора x ∈ Rn .Тогда ее производная по вектору будет матрице鵶∂f (x)∂fi (x)=∈ Rn×m∂x∂xjДифференцирование матриц• Пусть A(x) = (aij (x)) ∈ Rn×n — квадратная матрица, зависящая от параметра x. Тогда ее производная по параметру по определению равн൶∂A(x)∂aij (x)=∂x∂xX Упр.• В частности, выписывая выражения покоординатно можно показать , что∂AB∂A∂B=B+A∂x∂x∂x∂A−1∂A −1= −A−1A∂x∂xµ¶∂ log det(A)∂A= tr A−1∂x∂xДифференцирование по матрице• Рассмотрим некоторую скалярную функцию, зависящую от матрицы f (A), A = (aij ) ∈ Rn×n• При поиске оптимальной матрицыA∗ = arg max f (A)Aвозникает задача дифференцирования функции по матрице• Производной функции по матрице назовем матрицу производных по соответствующим элементам Aµ¶∂f (A)∂f (A)=∈ Rn×n∂A∂aijГлава 10.
Общее решение для недиагональной регуляризации106Полезные формулы• Производная следа матрицы∂ tr(AB)= BT ,∂A• Выведем производную определителя матрицы∂ tr(AT B)=B∂A∂ det(A).∂Adet(A) =nXДля этого распишем определитель по строкеaij Mij ,i=1где Mij = (−1)i+j−1 det(Aij ) — алгебраическое дополнение, а Aij — матрица, полученная из A путемвычеркивания i-ой строки и j-го столбца. Тогда, учитывая, что Mik не зависит от aij для любыхk 6= j, получаемPn∂ i=1 aij Mij∂ det(A)== Mij .∂aij∂aijКаждый элемент матрицы A−1 выражается через алгебраические дополнения матрицы A как a−1ij =1M,отсюдаjidet(A)∂ det(A)= det(A)A−1∂A10.210.2.1Общее решение для недиагональной регуляризацииПолучение выражения для обоснованности с произвольной матрицейрегуляризацииГауссовское априорное распределение на веса классификатора• Рассмотрим стандартныйалгоритм логистической регрессии с произвольным гауссовским регуля√¡¢det(A)ризатором p(w|A) = (2π)m/2 exp − 12 wT AwwM P = arg max p(t|X, w)N (w|0, A−1 ) =warg maxwnYi=11 + exp(−tipµ¶det(A)1 Texp − w Awm/22j=1 wj φj (xi )) (2π)1Pm• Матрица регуляризации находится в результате поиска наиболее обоснованной моделиZA = arg max p(t|X, A) = arg max p(t|X, w)p(w|A)dwA∈AA∈A• Классическая байесовская логистическая регрессия соответствует множеству A = {A|A = αI, α ≥0}, а метод релевантных векторов — множеству A = {A|A = diag(α1 , .
. . , αm ), αj ≥ 0}Глава 10. Общее решение для недиагональной регуляризации107Общая постановка задачи• Очевидно, что ни байесовская логистическая регрессия, ни метод релевантных векторов не покрывают все возможные гауссовские априорные распределения на множество весов w• Рассмотрим задачу поиска наиболее обоснованного распределения во всем классе нормальных распределенийZA = arg max p(t|X, A) = arg max p(t|X, w)p(w|A)dw,A∈AA∈ATгде A = {A|A = A, A ≥ 0}Приближение Лапласа для правдоподобия• Используем метод Лапласа для того, чтобы приблизить правдоподобие гауссианой• Пусть H = ∇∇ − log p(t|X, w)|wM L — отрицательный гессиан логарифма правдоподобия, взятый вточке максимума, тогд൶1p(t|X, w) ≈ p̂(t|X, w) = p(t|X, wM L ) exp − (w − wM L )T H(w − wM L )2• ОбозначимQ(w) = p̂(t|X, w)p(w|A) = p̂(t|X, w)X Упр.pµ¶det(A)1 Texp−wAw,2(2π)m/2тогда легко показать, что выражение для обоснованности принимает видQ(wM P )(2π)m/2E(A) ≈ pdet(−∇∇ log Q(w)|wM P )Окончательный вид оптимизируемого функционала• Для упрощения выкладок, перейдем к рассмотрению логарифма обоснованности, очевидно, чтоA = arg max E(A) = arg max log E(A)A∈AA∈A• Выражение для логарифма обоснованности имеет вид¡¢log E(A) ≈ log p̂(t|X, wM P ) − 0.5wTM P AwM P + 0.5 log det (H + A)−1 A + C → maxA∈AЗадача поиска оптимальной матрицы в классе неотрицательно определенных (semi-definite programming) являетсянетривиальной и проблема разработки эффективного численного метода решения на настоящий момент являетсяоткрытойКомпонента log det(A) возникает из плотности p(w|A), являющейся множителем Q(w), а det(H+A) — это определительгессиана det(−∇∇ log Q(w)|wM L )10.2.2Получение оптимальной матрицы регуляризации в явном видеСхема последующих выкладок• Выражение обоснованности через точку максимума правдоподобия• Выражение обоснованности через промежуточную матрицу M = H(H + A)−1 A• Получение явной формулы для M и произвольной симметричной матрицы A• Получение оптимальной матрицы A с учетом ее неотрицательной определенностиГлава 10.
Общее решение для недиагональной регуляризации108Выражение wM P через wM L• Обоснованность зависит от точки максимума регуляризованного правдоподобия wM P , которая намомент поиска наилучшего регуляризатора неизвестна• Учитывая, что wM P зависит от выбранной матрицы регуляризации A, получим явный вид этойзависимостиµµ¶p¶det(A)11 TTQ(w) = p̂(t|X, wM L ) exp − (w − wM L ) H(w − wM L )exp − w Aw22(2π)m/2£¤mlog(2π)log Q(w) = −0.5 (w − wM L )T H(w − wM L ) + wT Aw − log det(A)) + log p̂(t|X, wM L ) −2∂ log Q(w)= −H(w − wM L ) − Aw = −(H + A)w + HwM L∂w• В точке w = wM P производная регуляризованного правдоподобия равна нулю, отсюдаwM P = (H + A)−1 HwM L .Выражение обоснованности через точку максимума правдоподобия• Подставим формулу для wM P в выражение для обоснованностиlog E(A) = 0.5 log det((H + A)−1 A) −£−0.5 (wM P − wM L )T H(wM Pmlog(2π) + log p̂(t|X, wM L )−2¤− wM L ) + wTM P AwM P• Учитывая, что матрицы H и (H + A) симметричные, wTM P = wTM L H(H + A)−1• Разность wM P − wM L может быть записана в матричном виде¡¢wM P − wM L = (H + A)−1 H − I wM L• Результат подстановки в последнее слагаемое обоснованности£©ª ©ª¤−0.5wTM L H(H + A)−1 − I H (H + A)−1 H − I + H(H + A)−1 A(H + A)−1 H wM L =£¤−0.5wTM L H(H + A)−1 H(H + A)−1 H − 2H(H + A)−1 H + H + H(H + A)−1 A(H + A)−1 H wM L =£¤−0.5wTM L H(H + A)−1 (H + A)(H + A)−1 H − −2H(H + A)−1 H + H wM L =£¤£¤−0.5wTM L H(H + A)−1 H − 2H(H + A)−1 H + H wM L = −0.5wTM L −H(H + A)−1 H + H wM L .Матричная хитрость• Воспользуемся следующим матричным тождествомH − H(H + A)−1 H = H(H + A)−1 ((H + A) − H) = H(H + A)−1 A• Тогда выражение для логарифма обоснованности (не забыв добавить 0.5 log det((H + A)−1 A)) можнопереписатьmlog E(A) = log p̂(t|X, wM L ) −log(2π)+2¡¢0.5[−wTM L H(H + A)−1 AwM L + log det (H + A)−1 A ]• Но и в таком виде оптимизация по A крайне затруднительнаГлава 10.
Общее решение для недиагональной регуляризации109Еще одна матричная хитрость• Сделаем замену переменной M = H(H + A)−1 A, тогда¡¢log E(A) = 0.5[−wTM L M wM L + log det (H + A)−1 A ] + C• Используя свойство определителя произведения, перепишем второе слагаемое¡¢log det (H + A)−1 A = log det(M ) − log det(H)• Учитывая, что H не зависит от A, получаемlog E(A) = 0.5[−wTM L M wM L + log det(M )] + C1 ,но такое выражение легко оптимизировать по матрице M !Выражение для оптимальной матрицы MX Упр.• Продифференцируем логарифм обоснованности поэлементно по матрице M и приравняем производную к нулю£¤∂log E(A)= 0.5 M −1 − wM L wTM L = 0,∂M• Отсюда получаем выражение для оптимальной матрицы M −1M −1 = wM L wTM L• Матрица M −1 имеет ранг 1, т.к.
равна произведению двух ненулевых векторов (матриц ранга 1).Выражение для оптимальной матрицы A• Получим выражение для матрицы AM = H(H + A)−1 AA−1 (H + A) = M −1 HA−1 H + I = M −1 HA−1 = (M −1 H − I)H −1 = M −1 − H −1 = wM L wTM L − H −1X Упр.• Матрица A−1 симметричная• Матрица H > 0, а значит A не является неотрицательнойНеотрицательная матрица регуляризации• Для того, чтобы получить неотрицательную матрицу, приведем A−1 к диагональному виду с помощью ортогонального преобразованияD = U T A−1 U = diag(d1 , d2 ≤ 0, . . . , dm ≤ 0),U T = U −1• Все собственные значения A−1 кроме, быть может, одного, заведомо неположительные.
Заменим ихнулямиD = diag(d1 , +0, . . . , +0)• Тогда D−1 = diag(d−11 , +∞, . . . , +∞)• Такое преобразование соответствует оптимальной неотрицательной матрице регуляризации с сохранением направлений регуляризации, задаваемых оптимальной матрицей wM L wTM L − H −1Глава 10. Общее решение для недиагональной регуляризации110Смысл оптимальной матрицы регуляризации• У оптимальной матрицы регуляризации A = U D−1 U T все собственные значения, кроме одного,равны бесконечности• Это означает, что веса w не могут меняться вдоль соответствующих собственных векторов• Обозначим за u собственный вектор, имеющий конечное собственное значение d−11 , тогда максимумрегуляризованного правдоподобия wM P = θM P u, гдеθM P = arg max p(t|X, θu)p(θ|d−11 ),θ∈Rздесь p(θ|d−11 )=√ 12πd1³2θexp − 2d1´∼ N (θ|0, d1 )• Полученный классификатор имеет единственную степень свободы!Алгоритм 5: «Идеальная» гауссовская регуляризацияВход: Обучающая выборка {xi , ti }ni=1 , xi ∈ Rd , ti ∈ {+1, −1}; Матрица обобщенных признаков Φ ={φj (xi )}n,mi,j=1 ;´³PmВыход: Набор весов wM P для решающего правила t∗ (x) = signj=1 wM P,j φj (x) ;1:2:3:4:5:6:7:8:9:10:Найти wM L = arg max p(t|X, w);Вычислить H = −∇∇ log p(t|X, w)|w=wM L ;Вычислить собственные вектора и собственные значения A = wM L wTM L − H −1 = QT D−1 Q, D =diag(d1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
