_пособие_ Ветров Д.П._ Кропотов Д.А. Байесовские методы машинного обучения_ учебное пособие (2007) (1185333), страница 14
Текст из файла (страница 14)
Метод релевантных векторов89• Параметр γi может интерпретироваться как степень, в которой соответствующий вес wi определяется данными или регуляризацией. Если αi велико, то вес wi существенно предопределен априорнымраспределением, Σii ' αi−1 и γi ' 0. С другой стороны для малых значений αi значение веса wiполностью определяется данными, γi ' 1.Принятие решения2• Зная значения αM P , σMP можно вычислить распределение прогноза :Z222p(t∗ |x∗ , t, X) = p(t∗ |x∗ , w, σMP )p(w|t, X, αM P , σM P )dw = N (t∗ |y∗ , σ∗ )X Упр.Здесьy∗ = wTM P φ(x∗ )2Tσ∗2 = σMP + φ(x∗ ) Σφ(x∗ )Алгоритм 1: Метод релевантных векторов для задачи регрессииВход: Обучающая выборка {xi , ti }ni=1 xi ∈ Rd , ti ∈ R; Матрица обобщенных признаков Φ = {φj (xi )}n,mi,j=1 ;−1Выход:w, матрица Σ и оценка дисперсии шума βдля решающего правила t∗ (x) =Pm Набор весов2−1Twφ(x),σ(x)=β+φ(x)Σφ(x);jj∗∗∗j=11: инициализация: αi := 1, i = 1, .
. . , m, β := 1, AlphaBound := 1012 , WeightBound :=10−6 , NumberOfIterations := 100;2: для k = 1, . . . , NumberOfIterations3:A := diag(α1 , . . . , αm );4:Σ := (βΦT Φ + A)−1 ;5:wM P := ΣβΦT t;6:для j = 1, . . . , m7:если wM P,j < WeightBound или αj > AlphaBound то8:wM P,j := 0, αj := +∞, γj := 0;9:иначеγ10:γj := 1 − αj Σjj , αj := w2 j ;11:β :=Pn− mj=1 γjkt−ΦwM P k2M P,jМетод релевантных векторов для регрессии: обсуждение• На практике процесс обучения обычно требует 20—50 итераций. На каждой итерации вычисляетсяwM P (это требует обращения матрицы размера m × m), а также пересчитываются значения α, σ 2(практически не требует времени). Как следствие, скорость обучения метода падает в 20-50 раз посравнению с линейной регрессией.• При использовании ядровых функций в качестве обобщенных признаков необходимо проводитьскользящий контроль для различных значений параметров ядровых функций.
В этом случае времяобучения возрастает еще в несколько раз.• Параметры регуляризации α и дисперсии шума в данных σ 2 подбираются автоматически.• На выходе получается разреженное решение, т.е. только небольшое количество исходных объектоввходят в решающее правило с ненулевым весом.• Кроме значения прогноза y∗ алгоритм выдает также дисперсию прогноза σ∗2 .Глава 8. Метод релевантных векторов901.210.80.60.40.20−0.2−0.4−10−8−6−4−20246810Рис.
8.1. Пример применения регрессии релевантных векторов для зашумленной функции y(x) = sinc(x). В качестве базисных функций использовались φj (x) = exp(−βkx − xj k2 ). Объекты, соответствующие релевантным базисным функциям,обведены в кружочки. В процессе обучения большинство αj стремятся к +∞. Таким образом, априорное распределение насоответствующий вес wj становится вырожденным, что соответствует ситуации wj = 0, т.е.
исключению данной базиснойфункции из модели8.3Метод релевантных векторов для задачи классификацииЗадача классификации• Рассмотрим следующую задачу классификации на два класса: имеется выборка (X, t) = {xi , ti }ni=1 ,где вектор признаков xi ∈ Rd , а целевая переменная ti ∈ {+1, −1}, требуется для нового объекта x∗предсказать значение целевой переменной t∗ .• Воспользуемся обобщенными линейными моделями для классификации:mX¡¢t̂(x) = sign(f (x)) = sign wj φj (x) = sign wT φ(x)j=1Здесь w — набор числовых параметров, а φ(x) — вектор обобщенных признаков.Метод максимума правдоподобия (логистическая регрессия)• В качестве функции правдоподобия выберем произведение логистических функций (см.
рис. 8.2a):p(t|X, w) =nYi=1p(ti |xi , w) =nY11+exp(−ti f (xi ))i=1• Переходя к логарифму правдоподобия, получаем (см. рис. 8.2b):−nXi=1log(1 + exp(−ti f (xi ))) → maxwГлава 8. Метод релевантных векторов91413.50.832.50.620.41.50.210.50−5−4−3−2−10123450−2.5−2−1.5−1(a)−0.500.511.522.5(b)Рис. 8.2. На рисунке (а) показаны логистические функции правдоподобия правильной классификации объектов из первого ивторого классов. На рисунке (b) изображены различные виды функционалов, штрафующих ошибку на обучении: количествоошибок (черная кривая), функция потерь в методе опорных векторов (hinge loss, серая кривая), логарифм логистическойфункции (пунктирная линия)Оптимизация функции правдоподобия (IRLS)• Функция − log(1 + exp(−x)) является вогнутой, поэтому логарифм правдоподобия как сумма вогнутых функций также является вогнутой функцией и имеет единственный максимум.• Для поиска максимума логарифма правдоподобия L воспользуемся методом Ньютона:wnew = wold − H −1 ∇L(w)Здесь H = ∇∇L(w) — гессиан логарифма правдоподобия.• Вычисляя градиент и гессиан, получаем формулы пересчета:wnew = (ΦT RΦ)−1 ΦT Rzz = Φwold − R−1 diag(t)sЗдесь si =11+exp(−ti f (xi )) ,R = diag(s1 (1 − s1 ), .
. . , sn (1 − sn )).Введение регуляризации• По аналогии с линейной регрессией можно рассмотреть максимум апостериорной плотности с нормальным априорным распределением с единичной матрицей ковариации, умноженной на коэффициент α−1 :nXα−log(1 + exp(−ti f (xi ))) − kwk2 → maxw2i=1• Метод оптимизации меняется следующим образом:wnew = (ΦT RΦ + αI)−1 ΦT Rzz = Φwold − R−1 diag(t)sГлава 8. Метод релевантных векторов92Логистическая регрессия: обсуждение• По-прежнему довольно высокая скорость работы. На практике обучение часто требует всего 3—7итераций.• Отсутствие способа автоматического выбора параметра регуляризации α• Неразреженное решениеМетод релевантных векторов• Для получения разреженного решения введем в качестве априорного распределения на параметрыw нормальное распределение с диагональной матрицей ковариации с различными элементамина диагонали:p(w|α) = N (w|0, A−1 )Здесь A = diag(α1 , . .
. , αm ).• Для подбора параметров модели α воспользуемся идеей максимизации обоснованности:Zp(t|α) = p(t|X, w)p(w|α)dw → maxαПриближение Лапласа³ 2´1• Рассмотрим функцию p(z) = exp − z2 1+exp(−20z−4)(см. рис. 8.3).• Разложим логарифм функции в ряд Тейлора в точке максимума:z0 = arg max f (z),zHlog f (z) ' log f (z0 ) + (z − z0 )2 ,2¯d2 f ¯¯H=dz 2 ¯z=z0• Тогда функцию f (z) можно приблизить следующим образом (см. рис. 8.3):µ¶Hf (z) ' f (z0 ) exp(z − z0 )22Вычисление обоснованности• Подынтегральное выражение в обоснованности является произведением логистических функций инормального распределения. Такой интеграл не берется аналитически.• Решение: приблизить подынтегральную функцию гауссианой, интеграл от которой легко берется.Для приближения воспользуемся методом Лапласа:ZZpQ(wM P ),p(t|α) = p(t|X, w)p(w|α)dw = Q(w)dw ' (2π)m qdet(− ∇∇ log Q(w)|w=wM P )гдеwM P = arg max Q(w)wГлава 8.
Метод релевантных векторов93510−50.8−10−150.6−200.4−25−300.2−350−2−10123−40−24−1(a)01234(b)Рис. 8.3. Функция правдоподобия (рисунок (а)) и ее логарифм (рисунок (b)) вместе с соответствующим приближениемЛапласаОптимизация обоснованностиПриравнивая к нулю производную логарифма обоснованности по α, получаем:log p(t|X, α) = log Q(wM P ) −−nX1log det(−H) + C =2mlog(1 + exp(−ti f (xi , wM P ))) −i=1X Упр.m1X11X2αi wMlog det(−H) +log αi + CP,i −2 i=122 i=1Здесь H = −ΦT RΦ − A, R = diag(s1 (1 − s1 ), . .
. , sn (1 − sn )), si =11+exp(−ti f (xi ,wM P )) .∂1 211log p(t|X, α) = − wMdet(ΦT RΦ + A)−1 det(ΦT RΦ + A) × ((ΦT RΦ + A)−1 )jj += 0P,j −∂αj222αjОтсюда получаем итерационные формулы пересчета α, аналогичные регрессии:αinew =1 − αiold Σii2wMP,iМетод релевантных векторов: обсуждение• На практике процесс обучения обычно требует 20—50 итераций. На каждой итерации вычисляетсяwM P (это требует 3—7 итераций с обращениями матрицы размера m×m), а также пересчитываютсязначения α (практически не требует времени). Как следствие, скорость обучения метода падает в20—50 раз по сравнению с логистической регрессией.• При использовании ядровых функций в качестве обобщенных признаков необходимо проводитьскользящий контроль для различных значений параметров ядровых функций. В этом случае времяобучения возрастает еще в несколько раз.• Параметры регуляризации α подбираются автоматически.• На выходе получается разреженное решение.Глава 8.
Метод релевантных векторов94Рис. 8.4. Пример применения метода релевантных векторов для задачи классификации. В качестве базисных функций использовались φj (x) = exp(−β(x−xj )2 ). Объекты, соответствующие релевантным базисным функциям, обведены в кружочки.В процессе обучения большинство αj стремятся к +∞. Таким образом, априорное распределение на соответствующий весwj становится вырожденным, что соответствует ситуации wj = 0, т.е.
исключению данной базисной функции из модели• Для вычисления дисперсии прогноза необходимо проводить дополнительно аппроксимацию интегралаZp(t∗ |x∗ , t, X) = p(t∗ |x∗ , w)p(w|t, X, αM P )dwГлава 8. Метод релевантных векторов95Алгоритм 2: Метод релевантных векторов для задачи классификацииВход: Обучающая выборка {xi , ti }ni=1 xi ∈ Rd , ti ∈ {+1, −1}; Матрица обобщенных признаков Φ ={φj (xi )}n,mi,j=1 ;PmВыход: Набор весов w для решающего правила t∗ (x) = j=1 wj φj (x);1: инициализация: αi := 1, i = 1, . . . , m, w M P = t, AlphaBound := 1012 , WeightBound :=10−6 , NumberOfIterations := 100;2: для k = 1, .
. . , NumberOfIterations3:A := diag(α1 , . . . , αm );4:повторять5:для i = 1, . . . , n6:si := (1+exp(−ti Pm1 wM P,j φj (xi ))) ;j=17:8:9:10:11:12:13:14:15:16:R := diag(s1 (1 − s1 ), . . . , sn (1 − sn ));z := ΦwM P − R−1 (s − t);Σ := (ΦT RΦ + A)−1 ;wM P := ΣΦT Rz;oldпока kwnewM P − w M P k меняется больше, чем на заданную величинудля j = 1, . . . , mесли wM P,j < WeightBound или αj > AlphaBound тоwM P,j := 0, αj := +∞, γj := 0;иначе1−α Σαj := w2 j jj ;M P,jГлава 9Недиагональная регуляризацияобобщенных линейных моделейВ главе рассматриваются ограничения и недостатки метода релевантных векторов и способы их преодоления. Описана идея регуляризации степеней свободы алгоритма классификации, соответствующаяиспользованию недиагональной матрицы регуляризации весов классификатора.
Рассматривается регуляризация с помощью введения лапласовского априорного распределения и ее отличительные особенности.96Глава 9. Недиагональная регуляризация обобщенных линейных моделей9.197Ликбез: Неотрицательно определенные матрицы и Лапласовское распределениеНеотрицательно определенные матрицы• Матрица A ∈ Rn×n называется неотрицательно определенной, если соответствующая ей квадратичная форма всегда неотрицательна, т.е. ∀x ∈ RnhAx, xi ≥ 0.• Матрица A называется симметричной, если AT = A• В частности, множество всех n-мерных нормальных распределений с центром в нуле изоморфномножеству всех неотрицательно определенных симметричных матрицpµ¶det(A)1 T−1N (x|0, A ) =exp − x Ax , AT = A, A ≥ 0.2(2π)n/2Свойство неотрицательно определенных симметричных матриц• Из линейной алгебры известно, что любая симметричная (самосопряженная) матрица можетбыть приведена к диагональному виду линейным преобразованием координат, т.е.
∃P : P T =P −1 , det(P ) 6= 0 такая, чтоΛ = P T AP = diag(λ1 , . . . , λn )• Если дополнительно известно, что матрица A неотрицательно определена, то все λi ≥ 0• Количество ненулевых λi называется рангом матрицы AЛапласовское распределение• Распределением Лапласа называется двустороннее показательное распределени嵶λλL(x|λ) = exp − |x|42• Распределение Лапласа имеет сингулярность в нуле и более тяжелые хвосты, чем нормальное распределение• В логарифмической шкале введение априорного распределения Лапласа на веса означает т.н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
