_пособие_ Ветров Д.П._ Кропотов Д.А. Байесовские методы машинного обучения_ учебное пособие (2007) (_пособие_ Ветров Д.П._ Кропотов Д.А. Байесовские методы машинного обучения_ учебное пособие (2007).pdf), страница 13
Описание файла
PDF-файл из архива "_пособие_ Ветров Д.П._ Кропотов Д.А. Байесовские методы машинного обучения_ учебное пособие (2007).pdf", который расположен в категории "". Всё это находится в предмете "(ммо) методы машинного обучения" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 13 страницы из PDF
Решение задачи выбора модели по Байесу. Обоснованность модели82Оценка максимального правдоподобия• Пусть вероятности выпадения чисел 1, 2, . . . , N равны, соответственно q1 , q2 , . . . , qN• Тогда правдоподобие выборки x = (x1 , . . . , xn ) равноp(x|q) =nYqxii=1• Подставляя в формулу наши наблюдения получаемp(x1 , x2 |q) = q8 q6 → maxq• Учитывая, что все qi неотрицательны иPNi=1 qiq6M L = q8M L =• Отсюда мат. ожидание µM L =PNi=1= 1, получаем1,2qiM L = 0, ∀i 6= 6, 8iqiM L = 12 (x1 + x2 ) = 7Байесовская оценка вероятностей• В отсутствие априорной информации о датчике случайных чисел, наиболее естественным является предположение о равномерности распределения вероятностей выпадения каждого числа p(q) =Const• Это частный случай распределения ДирихлеNX1α01 −1α0 −1. . . qNN ,qi = 1, qi ≥ 00 q1B(α )i=1D(q|α) =0=1при α10 = · · · = αN• Тогда применяя формулу Байеса, учитывая, что правдоподобие равно p(x1 , x2 |q) = q8 q6 , получаем1 00q .
. . q50 q61 q70 q81 q90 . . . qN= D(q|α1 ),Z 1где α61 = α81 = 2, а все остальные αi1 = 1p(q|x1 , x2 ) =Байесовская оценка мат. ожидания• Чтобы получить точечные оценки вероятностей q1 , . . . , qN , возьмем мат. ожидание апостериорногораспределения• По свойству распределения ДирихлеαiEqi = PNj=1αj• Тогда, при N = 10 получаем12= ≈ 0.16,126qi =1≈ 0.08 ∀i 6= 6, 81212=≈ 0.02,10251qi =1≈ 0.01 ∀i 6= 6, 8102q6 = q8 =при N = 100 получаемq6 = q8 =• Отсюда находим оценку мат. ожидания датчика, равную µM P (N = 10) = 5.75 и µM P (N = 100) ≈49.65Глава 7.
Решение задачи выбора модели по Байесу. Обоснованность модели83Выбор наиболее обоснованной модели• Итак, для двух различных моделей датчика мы получили два существенно разных ответа. Выберемнаиболее обоснованную модель• Обозначим обоснованность через Ev. Тогда справедливо следующее равенствоp(q|x) =0q8 q6 × q10 . . . qNq8 q6=,0B(α )EvB(α1 )где B(α) — нормировочная константа в распределении Дирихле (многомерная бета-функция), равнаяQNi=1 Γ(αi )B(α) =Γ(α1 + · · · + αN )• Отсюда получаем формулу для обоснованности моделиEv =B(α1 )B(α0 )• Как и следовало ожидать, Ev(N = 10) > Ev(N = 100)Обоснованность• Зависимость обоснованности от N показана на рисунке 7.7NРис. 7.7. При N < 8 обоснованность равна нулю, т.к.
получить выборку x1 = 8, x2 = 6, применяя такой датчик, невозможно(функция правдоподобия всюду будет равна нулю). При больших N обоснованность падает, т.к. такие модели способныобъяснить не только наши наблюдения, но и «много чего еще»Глава 8Метод релевантных векторовГлава посвящена описанию метода релевантных векторов, являющегося примером успешного применения методов байесовского обучения и отправным пунктом для различных модификаций и обобщений,описанных в последующих главах. Рассматриваются задачи восстановления регрессии и классификации,показаны различия в применении метода наибольшей обоснованности для этих двух задач.
Отдельноевнимание уделено технике матричных вычислений, приведены основные матричные тождества.84Глава 8. Метод релевантных векторов8.185Ликбез: Матричные тождества обращенияМатричные тождества обращения• Эти тождества показывают, как изменяется матрица, если к ее обращению что-то добавляется.• Тождество Шермана-Моррисона-Вудбери(A−1 + U V T )−1 = A − AU (I + V T AU )−1 V T A• Лемма об определителе матрицыdet(A−1 + U V T ) = det(I + V T AU ) det(A−1 )Тождество Шермана-Моррисона-Вудбери• Тождество(A−1 + U V T )−1 = A − AU (I + V T AU )−1 V T A• Доказательство(A−1 + U V T )(A − AU (I + V T AU )−1 V T A) = I + U V T A − (U + U V T AU )(I + V T AU )−1 V T A =I + U V T A − U (I + V T AU )(I + V T AU )−1 V T A = I + U V T A − U V T A = IТождества для определителей матрицы• При доказательстве многих матричных тождеств полезным оказывается следующее равенство:µ¶A Bdet= det(A) det(D − CA−1 B) = det(D) det(A − BD−1 C)C DЗдесь A ∈ Rm×m , B ∈ Rm×n , C ∈ Rn×m , D ∈ Rn×n• Это равенство следует из следующего тождества:µ¶ µ¶µ¶ µA BA 0IA−1 BI==C DC I0 D − CA−1 B0BD¶µA − BD−1 CD−1 C0I¶• Лемма об определителе матрицыdet(A−1 + U V T ) = det(I + V T AU ) det(A−1 )• Доказательство:detµ −1AVT−UI¶= det(A−1 ) det(I + V T AU ) = det(I) det(A−1 + U I −1 V T ) = det(A−1 + U V T )Глава 8.
Метод релевантных векторов8.286Метод релевантных векторов для задачи регрессииОбобщенные линейные модели• Рассмотрим следующую задачу восстановления регрессии: имеется выборка (X, t) = {xi , ti }ni=1 , гдевектор признаков xi ∈ Rd , а целевая переменная ti ∈ R, требуется для нового объекта x∗ предсказатьзначение целевой переменной t∗ .• Предположим, что t = f (x) + ε, где ε ∼ N (ε|0, σ 2 ), аf (x) =mXwj φj (x) = wT φ(x)j=1Здесь w — набор числовых параметров, а φ(x) — вектор обобщенных признаков.• Часто в качестве обобщенных признаков выбираются следующие:– Обычные признаки — φj (x) = xj , j = 1, .
. . , d– Ядровые функции — φj (x) = K(x, xj ), j = 1, . . . , n, φn+1 (x) ≡ 1Метод максимума правдоподобия (линейная регрессия)• Так как шумовая компонента ε имеет независимое нормальное распределение, то можно выписатьфункцию правдоподобия обучающей выборки:p(t|X, w) =nYp(ti |xi , w) =i=1nYN (ti |f (xi , w), σ 2 ) =i=1nYi=1√µ¶1(ti − wT φ(xi ))2exp −=2σ 22πσµ Pn¶(ti − wT φ(xi ))21√exp − i=12σ 2( 2πσ)n• Переходя к логарифму, получаем−n1 X1(ti − wT φ(xi ))2 = − 2 (t − Φw)T (t − Φw) → max2w2σ i=12σЗдесь Φ = [φ(x1 )T , . . .
, φ(xn )T ]T• Точка максимума правдоподобия выписывается в явном виде:wM L = (ΦT Φ)−1 ΦT tВведение регуляризации (априорного распределения)• Следуя байесовскому подходу воспользуемся методом максимума апостериорной плотности:wM P = arg max p(w|X, t) = arg max p(t|X, w)p(w)ww• Выберем в качестве априорного распределения на параметры w следующее:p(w|α) = N (w|0, α−1 I)Такой выбор соответствует штрафу за большие значения коэффициентов w с параметром регуляризации αГлава 8. Метод релевантных векторов87• Максимизация апостериорной плотности эквивалентна следующей задаче оптимизации:−n1 Xα(ti − φ(xi ))2 − kwk2 → max2w2σ i=12• РешениеwM P = (σ −2 ΦT Φ + αI)−1 σ −2 ΦT tЛинейная регрессия: обсуждение• Высокая скорость обучения (достаточно сделать инверсию матрицы σ −2 ΦT Φ + αI размера m × m)• Отсутствие способов автоматического выбора параметра регуляризации α и дисперсии шума σ 2(параметров модели)• Неразреженное решение (вообще говоря, все базисные функции входят в решающее правило с ненулевым весом)Метод релевантных векторов• Для получения разреженного решения введем в качестве априорного распределения на параметрыw нормальное распределение с диагональной матрицей ковариации с различными элементамина диагонали:p(w|α) = N (0, A−1 )Здесь A = diag(α1 , .
. . , αm ). Такое априорное распределение соответствует независимой регуляризации вдоль каждого веса wi со своим параметром регуляризации αi ≥ 0• Для подбора параметров модели α, σ воспользуемся идеей максимизации обоснованности:Z2p(t|α, σ ) = p(t|X, w, σ 2 )p(w|α)dw → max2α,σВычисление обоснованности• Обоснованность является сверткой двух нормальных распределений и может быть вычислена аналитическиZZ22p(t|α, σ ) = p(t|X, w, σ )p(w|α)dw = Q(w)dw• Рассмотрим функцию L(w) = log Q(w).
Она является квадратичной функцией и может быть представлена как:1L(w) = L(wM P ) + (∇w L(wM P ))T (w − wM P ) + (w − wM P )T H(w − wM P )2wM P = arg max L(w) ⇒ ∇w L(wM P ) = 0wH = ∇∇L(wM P )• Тогда обоснованность может быть вычислена ка굶ZZ1TQ(w)dw = exp L(wM P ) + (w − wM P ) H(w − wM P ) dw =2pppQ(wM P )= Q(wM P ) (2π)m det((−H)−1 ) = (2π)m pdet(−H)Глава 8. Метод релевантных векторовX Упр.88Вычисление обоснованности• Обозначив β = σ −2 , приводим подобные слагаемые в выражении для L(wM P )11nL(w) = − β(t − Φw)T (t − Φw) − wT Aw − log(2π)−22211mlog(2π) + log det(A) = − β[tT t − 2wT ΦT t + wT ΦT Φw] + C−222• Приравнивая производную по w к нулю получаем значение wM P1∇L(w) = − β(−2ΦT t + 2ΦT Φw) − Aw = 0 ⇒ wM P = (βΦT Φ + A)−1 βΦT t2• Выделяем полный квадрат относительно t в выражении для L(wM P )L(wM P ) = −1£ Tβt t − 2βtT Φ(βΦT Φ + A)−1 βΦT t + tT Φβ(βΦT Φ + A)−1 ×2¤×(βΦT Φ + A)(βΦT Φ + A)−1 βΦT t + C =1− βtT [I − 2βΦ(βΦT Φ + A)−1 ΦT + +Φ(βΦT Φ + A)−1 βΦT ]t + C =2½1− βtT [I − βΦ(βΦT Φ + A)−1 ΦT ]t + C =2(I − βΦ(βΦT Φ + A)−1 ΦT )−1 = {Тож-во Вудбери} =¾I + βΦ(βΦT ΦΦT βΦ)−1 ΦT = I + βΦA−1 ΦT =− 0.5βtT (I + βΦA−1 ΦT )−1 t + C = −0.5tT (β −1 I + ΦA−1 ΦT )−1 t + C• Таким образом выражение для обоснованности представляет собой гауссовское распределение относительно вектора t, а значит нормализующая константа выписывается в явном видеZpQ(wM P )p(t|X, α, σ 2 ) = p(t|X, σ 2 )p(w|α)dw = (2π)m p=det(−H)√µ¶pdet A11mp(2π) √exp − tT (β −1 I + ΦA−1 ΦT )−1 t p=2( 2πσ)n (2π)mdet(−H)½H = −(βΦT Φ + A), det(−H) = det(βΦT Φ + A) = det(A(I + βA−1 ΦT Φ)) =¾−1 T−1 Tdet(A) det(I + βA Φ Φ) = {Лемма об опр-ле матр.} = det(A) det(I + βΦA Φ ) =µ¶11 T −1−1 T −1pexp − t (β I + ΦA Φ ) t2(2π)n det(β −1 I + ΦA−1 ΦT )1/2Оптимизация обоснованностиX Упр.• Приравнивая к нулю производные обоснованности по α, σ 2 , можно получить итерационные формулы для пересчета параметров:γiαinew = 2γi = 1 − αiold ΣiiwM P,i(σ 2 )new =Здесь Σ = (βΦT Φ + A)−1 , wM P = βΣΦT t.kt − Φwk2Pmn − i=1 γiГлава 8.