Аппроксимация Лапласа (пример)

Материал из MachineLearning.

(Различия между версиями)

Текущая версия

Аппроксимация Лапласа - способ оценки параметров нормального распределения при аппроксимации заданной плотности вероятности.

Содержание

1 Постановка задачи
2 Описание алгоритма
3 Вычислительный эксперимент
4 Смотри также
5 Литература
6 Примечания

Постановка задачи

Задана выборка — множество $X^N=\{{x}_1,\ldots,{x}_N|x\in\R^M\}$ значений свободных переменных и множество $\{y_1,\ldots, y_N| y\in\R\}$ соответствующих им значений зависимой переменной. Необходимо для выбранной регрессионной модели $f(w,x)$ :

3-1 показать зависимость среднеквадратичной ошибки от значений параметров модели: $SSE=SSE(w)$ ;

3-2 построить график и сделать аппроксимацию Лапласа для зависимости $SSE=SSE(w)$ ;

3-3 найти расстояния между полученными зависимостями, используя расстояние Кульбака - Лейблера.

Описание алгоритма

При восстановлении регрессии рассматривалась следующая гипотеза порождения данных:

$y=f(x,w)+\epsilon$ , где $\epsilon\propto N(0,\sigma^2)$

В таком случае, при фиксированной модели f плотность вероятности появления данных равняется^[1]:

$p(y|x,w)=\frac{1}{Z_D}exp(-E_D)$ , где

$E_D$ - это функция регрессионных невязок, т.е. $SSE$ ;

$Z_D$ - нормировачный коэффициент.

3-1. В заданной модели f, используя метод наименьших квадратов, находим оптимальное значение вектора параметров $\mathcal w_{opt}$ . Далее, фиксируем все параметры выбранной регрессионной модели (для определенности зададим им оптимальные значения) кроме одного (пусть этот незафиксированный параметр будет $w_1$ ). После чего, варьируя значение $w_1$ , строим искомую зависимость $SSE=SSE(w_1)$ и график $p(y|x,w_1)$ . Таким образом построена зависимость от одного параметра $w_1$ . Аналогично действуя, строится зависимость от большего количества параметров.

3-2. При аппроксимации Лапласа, полученную в пункте 3-1 функцию $p(y|x,w_1)$ приближаем функцией многомерного нормального распределения $N(w_{otp},A)$ . Воспользуемся нелинейной регрессионной моделью:

$p \propto exp((w - w_{otp})^T A^{-1} (w-w_{otp}))$

Другими словами, зная из пункта 3-1 значение $p(D|w)$ (т.е. множество пар $(p_i, w_i)$ , где $w_i$ - вектор параметров i-го сэмпла), надо получить корреляционную матрицу $A$ .

Вначале, представляем элементы матрицы $A$ в виде вектора параметров. Далее, используя метод Ньютона-Гаусса,находим оптимальный вектора параметров (минимум суммы остаточных квадратов). Затем, делаем обратный переход от вектора параметров к матрице и получаем искомую корреляционную матрицу $A$ .

3-3. Расстояние Кульбака - Лейблера между двумя распределениями p(z) и q(z) равняется:

$D_{kl}(p,q)=\sum\limits_{z\in \mathcal{Z}} p(z) \ln \frac{p(z)}{q(z)}$

Вычислительный эксперимент

Обозначим плотность распределения SSE как $p_{SSE}$ , а его аппроксимация лапласа $p_{lap}$ .

Во время вычислительного эксперимента SSE принимало достаточно большие значения (порядка $10^3 - 10^4$ ). Как следствие, p(y) принимало значения порядка 1, и аппроксимация Лапласа была некорректной.

Поэтому, аппроксимация Лапласа применялась не к самому распределению p(y), а к ln(p(y)) (т.е. к -SSE c точностью до коэффициента).

Пример 1

Задуманная функция $y=x + sin3x$ . Рассматривается линейная регрессионная модель с двумя параметрами: $y(x)=w_1+w_2x$ . $w_1_{opt}$ и $w_2_{opt}$ - оптимальное значение параметров (при которых SSE минимально).

Фиксируем один параметр $w_1=w_1_{opt}$ и задаем различные значение $w_2$ (500 случайных значений на отрезке [-1;2]). Строим зависимость:

$D_{kl}(p_{SSE},p_{lap})=0.0085$ .

Повторим эксперимент, только теперь варьируем сразу оба параметра $w_1$ и $w_2$ :

Рис. 1. Зависимость $- SSE$ от $w_1$ и $w_2$

Рис. 2. Зависимость от и . Ось log(p) направлена вверх

Рис. 2. Зависимость $- SSE$ от $w_1$ и $w_2$ . Ось log(p) направлена вверх

аппроксимация Лапласа:

Laplace approximation

$D_{kl}(p_{SSE},p_{lap})=4.9491*10^{-5}$

ковариационная матрица FIXIT: матрица не является положительно определенной! По критерию Сильвестра элементы не диагонали должны быть положительны $A=10^3*\begin{Vmatrix} -0.1021 & -0.3141\\ -0.3141 & -1.3242\\ \end{Vmatrix}$

На рис.2 наблюдается зависимость между коэффициентами $w_1$ и $w_2$ . Следовательно, ковариационная матрица $cov(w_1,w_2)$ не будет диагональной.

Пример 2

Задуманная функция $y=7.5x + 12tanx+\epsilon$ , где $\epsilon$ - белый гауссовский шум. Рассматривается следующая регрессионная модель: линейная комбинация функций $x$ и $tanx$ .

$y(x)=w_1*x+w_2tanx$ .

$w_1_{opt}$ и $w_2_{opt}$ - оптимальное значение параметров (при которых SSE минимально).

Фиксируем один параметр $w_1=w_1_{opt}$ и задаем различные значение $w_2$ (10000 случайных значений на отрезке [5;15]). Строим зависимость:

$D_{kl}(p_{SSE},p_{lap})=4.3097*10^{-16}$

Повторим эксперимент, только теперь варьируем сразу оба параметра $w_1$ и $w_2$ (10000 случайных значений на отрезке [-100;100]):

Рис. 1. Зависимость $- SSE$ от $w_1$ и $w_2$

Рис. 2. Зависимость $- SSE$ от $w_1$ и $w_2$ . Ось log(p) направлена вверх

аппроксимация Лапласа:

Laplace Approximation

Laplace Approximation. Ось log(p) направлена вверх

$D_{kl}(p_{SSE},p_{lap})=0.1753$

ковариационная матрица $A=10^4*\begin{Vmatrix} -2.9234 & 0.0413\\ 0.0413 & -3.9066\\ \end{Vmatrix}$

Пример 3

Задуманная функция $y=exp(7+log(5x))+\epsilon$ , где $\epsilon$ - белый гауссовский шум. Рассматривается существенно нелинейная регрессионная модель с двумя параметрами: $y(x)=exp(w_1+log(w_2x))$ .

Фиксируем один параметр $w_2=5$ и задаем различные значение $w_1$ (10000 случайных значений на отрезке [6.5;7.5]). Строим зависимость:

$D_{kl}(p_{SSE},p_{lap})=0.0794$ .

Повторим эксперимент, только теперь варьируем сразу оба параметра $w_1$ и $w_2$ (10000 случайных значений на отрезках [4.5;5.5] и [6.5;7.5] соответственно):

Зависимость $- SSE$ от $w_1$ и $w_2$

аппроксимация Лапласа:

Laplace Approximation

$D_{kl}(p_{SSE},p_{lap})=0.0718$

ковариационная матрица $A=10^{11}*\begin{Vmatrix} -2.7859 & 0.0056\\ 0.0056 & 0.0146\\ \end{Vmatrix}$

Смотри также

Литература

Bishop, C. Pattern Recognition And Machine Learning. Springer. 2006.

Примечания

Данная статья была создана в рамках учебного задания.

Студент: Евгений Зайцев

Преподаватель: В.В.Стрижов

Срок: 24 декабря 2010

В настоящее время задание завершено и проверено. Данная страница может свободно правиться другими участниками проекта MachineLearning.ru.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%90%D0%BF%D0%BF%D1%80%D0%BE%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D1%86%D0%B8%D1%8F_%D0%9B%D0%B0%D0%BF%D0%BB%D0%B0%D1%81%D0%B0_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29»

Категория: Практика и вычислительные эксперименты

@@ Строка 1: / Строка 1: @@
-[[Аппроксимация Лапласа]] - способ оценки параметров нахождения нормального распределения при апроксимации заданой плотности вероятности.
+[[Аппроксимация Лапласа]] - способ оценки параметров нормального распределения при аппроксимации заданной плотности вероятности.
-==Сэмплирование==
-'''Сэмплирование''' – метод выбора подмножества наблюдаемых величин из данного множества, с целью выделения неких свойст исходного множества.
-Одно из основных приминений методов сэмплирования заключается в оценке математического ожидания сложных вероятностных распределений:
- <center><tex>E[f]=\int f(z)p(z) dz</tex> </center>
-для которых тяжело делать выборку непосредственно из распределения ''p(z)''. Однако, можно подсчитать значение ''p(z)'' в любой точке ''z''. Основная идея заключается в создании незавсимой выборки <tex>z^{(l)}</tex> (где <tex>l=1,...,L</tex>) из распределения <tex>p(z)</tex>. Это позволит оцениваемое математическое ожидание приблизить конечной суммой:
-<center> <tex>\hat f=\frac{1}{L}\sum_{l=1}^{L} f(z^{(l)})</tex></center>
-Существует [http://en.wikipedia.org/wiki/Sampling_(statistics)#cite_ref-ken_black_india_0-0 несколько методов сэмплирования] для создания выборки <tex>z^{(l)}</tex> <ref>Bishop, C. Pattern Recognition And Machine Learning. Springer. 2006., Chapter 11 Sampling Methods, p. 523-558.</ref>:
-*Simple random sampling;
-*Systematic sampling;
-*Rejection sampling;
-*Adaptive rejection sampling.
 ==Постановка задачи==
 Задана выборка — множество <tex>X^N=\{{x}_1,\ldots,{x}_N|x\in\R^M\}</tex> значений свободных переменных и множество <tex>\{y_1,\ldots, y_N| y\in\R\}</tex> соответствующих им значений зависимой переменной.
-Необходимо для выбранной регрессионной модели <tex>f(\mathbf{w},\mathbf{x})</tex>
+Необходимо для выбранной регрессионной модели <tex>f(w,x)</tex>:
-# показать зависимость среднеквадратичной ошибки от значений параметров модели: <tex>SSE=SSE(w)</tex>;
-# построить график и сделать апроксимацию Лапласа для нее;
+'''3-1''' показать зависимость среднеквадратичной ошибки от значений параметров модели: <tex>SSE=SSE(w)</tex>;
-# найти расстояния между получеными зависимостями, используя [http://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence расстояние Кульбака - Лейблера].
+'''3-2''' построить график и сделать аппроксимацию Лапласа для зависимости <tex>SSE=SSE(w)</tex>;
+'''3-3''' найти расстояния между полученными зависимостями, используя [http://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence расстояние Кульбака - Лейблера].
 ==Описание алгоритма==
+При восстановлении регрессии рассматривалась следующая гипотеза порождения данных:
+<center><tex>y=f(x,w)+\epsilon</tex>, где</center>
+<center><tex>\epsilon\propto N(0,\sigma^2)</tex></center>
+В таком случае, при фиксированной модели ''f'' плотность вероятности появления данных равняется<ref>Стрижов В.В., Крымова Е.А. Методы выбора регрессионных моделей. М.: ВЦ РАН, 2010. 60 с., стр. 41 </ref>:
+<center><tex>p(y|x,w)=\frac{1}{Z_D}exp(-E_D)</tex>, где</center>
+<tex>E_D</tex> - это функция регрессионных невязок, т.е. <tex>SSE</tex>;
-Расстояние Кульбака - Лейблера:
+<tex>Z_D</tex> - нормировачный коэффициент.
-<center> <tex>D_{kl}(p,q)=\sum\limits_{x\in \mathcal{X}} p(x) \ln \frac{p(x)}{q(x)}</tex></center>
+'''3-1'''. В заданной модели ''f'', используя [[метод наименьших квадратов]], находим оптимальное значение вектора параметров <tex>\mathcal w_{opt}</tex>. Далее, фиксируем  все параметры выбранной регрессионной модели (для определенности зададим им оптимальные значения) кроме одного (пусть этот незафиксированный параметр будет <tex>w_1</tex>). После чего, варьируя значение <tex>w_1</tex>, строим искомую зависимость <tex>SSE=SSE(w_1)</tex> и график <tex>p(y|x,w_1)</tex>. Таким образом построена зависимость от одного параметра <tex>w_1</tex>.
+Аналогично действуя, строится зависимость от большего количества параметров.
+'''3-2'''. При аппроксимации Лапласа, полученную в пункте 3-1 функцию <tex>p(y|x,w_1)</tex> приближаем функцией многомерного нормального распределения <tex> N(w_{otp},A)</tex>. Воспользуемся нелинейной регрессионной моделью:
+<center><tex> p \propto exp((w - w_{otp})^T A^{-1} (w-w_{otp})) </tex></center>
+Другими словами, зная из пункта 3-1 значение <tex>p(D|w)</tex> (т.е. множество пар <tex>(p_i, w_i)</tex>, где <tex>w_i</tex> - вектор параметров ''i''-го сэмпла), надо получить корреляционную матрицу <tex>A</tex>.
+Вначале, представляем элементы матрицы <tex>A</tex> в виде вектора параметров. Далее, используя [[метод Ньютона-Гаусса]],находим оптимальный вектора параметров (минимум суммы остаточных квадратов). Затем, делаем обратный переход от вектора параметров к матрице и получаем искомую корреляционную матрицу <tex>A</tex>.
+'''3-3'''. Расстояние Кульбака - Лейблера между двумя распределениями ''p(z)'' и ''q(z)'' равняется:
+<center> <tex>D_{kl}(p,q)=\sum\limits_{z\in \mathcal{Z}} p(z) \ln \frac{p(z)}{q(z)}</tex></center>
 ==Вычислительный эксперимент==
-Обозначим плоность распределения SSE как <tex> p_{SSE}</tex>, а его апроксимация лапласса <tex> p_{lap}</tex>
+Обозначим плотность распределения SSE как <tex> p_{SSE}</tex>, а его аппроксимация лапласа <tex> p_{lap}</tex>.
+{{tip | Во время вычислительного эксперимента ''SSE'' принимало достаточно большие значения (порядка <tex>10^3 - 10^4</tex>). Как следствие, ''p(y)'' принимало значения порядка 1, и аппроксимация Лапласа была некорректной.
+Поэтому, аппроксимация Лапласа применялась не к самому распределению ''p(y)'', а к ''ln(p(y))'' (т.е. к ''-SSE'' c точностью до коэффициента).}}
 ===Пример 1===
-Задуманная функция <tex>y=x + sin3x</tex>. Берем линейную регрессионную модель с двумя параметрами: <tex>y(x)=w_1+w_2x</tex>.
+Задуманная функция <tex>y=x + sin3x</tex>. Рассматривается линейная регрессионная модель с двумя параметрами: <tex>y(x)=w_1+w_2x</tex>.
-Используя [[метод наименьших квадратов]] находим оптимальное значение <tex>w_1_{opt}</tex> и <tex>w_2_{opt}</tex> (при которых ''SSE'' минимально).
+<tex>w_1_{opt}</tex> и <tex>w_2_{opt}</tex> - оптимальное значение параметров (при которых ''SSE'' минимально).
-'''При фиксированном''' <tex>w_1=w_1_{opt}</tex> задаем различные значение <tex>w_2</tex> (500 случайных значений на отрезке [-1;2]) и строим зависимость:
+'''Фиксируем один параметр''' <tex>w_1=w_1_{opt}</tex> и задаем различные значение <tex>w_2</tex> (500 случайных значений на отрезке [-1;2]). Строим зависимость:
 [[Изображение:Sse(w2)b.png‎|center|frame]]
@@ Строка 41: / Строка 56: @@
 <tex>D_{kl}(p_{SSE},p_{lap})=0.0085</tex>.
-'''Повторим эксперимент''', только теперь варируем сразу оба параметра <tex>w_1</tex> и <tex>w_2</tex>:
+'''Повторим эксперимент''', только теперь варьируем сразу оба параметра <tex>w_1</tex> и <tex>w_2</tex>:
-[[Изображение:Sse(w1,w2).png|center|frame|Рис. 1. Зависимость <tex>- SSE</tex> от <tex>w_1</tex> и <tex>w_2</tex>]]
+[[Изображение:Sse(w1,w2)a.png|center|frame|Рис. 1. Зависимость <tex>- SSE</tex> от <tex>w_1</tex> и <tex>w_2</tex>]]
-[[Изображение:Sse(w1,w2)_axle_up.png|center|frame|Рис. 2. Зависимость <tex>- SSE</tex> от <tex>w_1</tex> и <tex>w_2</tex>. Ось log(p) направлена вверх]]
+[[Изображение:Sse(w1,w2)verh.png|center|frame|Рис. 2. Зависимость <tex>- SSE</tex> от <tex>w_1</tex> и <tex>w_2</tex>. Ось log(p) направлена вверх]]
-апроксимация Лапласса:
+аппроксимация Лапласа:
-[[Изображение:Laplas_2_parametr.png‎|center|frame|Laplace approximation]]
+[[Изображение:Laplas.png‎|center|frame|Laplace approximation]]
+<tex>D_{kl}(p_{SSE},p_{lap})=4.9491*10^{-5}</tex>
+ковариационная матрица
+FIXIT: матрица не является положительно определенной! По критерию Сильвестра элементы не диагонали должны быть положительны
+<tex>A=10^3*\begin{Vmatrix}
+-0.1021 & -0.3141\\
+-0.3141 & -1.3242\\
+\end{Vmatrix}
+</tex>
-<tex>D_{kl}(p_{SSE},p_{lap})=1.2481</tex>
 На рис.2 наблюдается зависимость между коэффициентами <tex>w_1</tex> и <tex>w_2</tex>. Следовательно, ковариационная матрица <tex>cov(w_1,w_2)</tex> не будет диагональной.
+===Пример 2===
+Задуманная функция <tex>y=7.5x + 12tanx+\epsilon</tex>, где <tex>\epsilon</tex> - белый гауссовский шум. Рассматривается следующая регрессионная модель: линейная комбинация функций <tex>x</tex> и <tex>tanx</tex>.
+<center> <tex>y(x)=w_1*x+w_2tanx</tex>.</center>
+<tex>w_1_{opt}</tex> и <tex>w_2_{opt}</tex> - оптимальное значение параметров (при которых ''SSE'' минимально).
+'''Фиксируем один параметр''' <tex>w_1=w_1_{opt}</tex> и задаем различные значение <tex>w_2</tex> (10000 случайных значений на отрезке [5;15]). Строим зависимость:
+[[Изображение:Odin_parametr.png‎|center|frame]]
+<tex>D_{kl}(p_{SSE},p_{lap})=4.3097*10^{-16}</tex>
+'''Повторим эксперимент''', только теперь варьируем сразу оба параметра <tex>w_1</tex> и <tex>w_2</tex>(10000 случайных значений на отрезке [-100;100]):
+[[Изображение:Dva_parametr_bok.png‎|center|frame|Рис. 1. Зависимость <tex>- SSE</tex> от <tex>w_1</tex> и <tex>w_2</tex>]]
+[[Изображение:Dva_parametr_verh.png|center|frame|Рис. 2. Зависимость <tex>- SSE</tex> от <tex>w_1</tex> и <tex>w_2</tex>. Ось log(p) направлена вверх]]
+аппроксимация Лапласа:
+[[Изображение:Laplas_bok.png‎|center|frame|Laplace Approximation]]
+[[Изображение:Laplas_verh.png‎|center|frame|Laplace Approximation.   Ось log(p) направлена вверх]]
+<tex>D_{kl}(p_{SSE},p_{lap})=0.1753</tex>
+ковариационная матрица
+<tex>A=10^4*\begin{Vmatrix}
+-2.9234 & 0.0413\\
+.0413 & -3.9066\\
+\end{Vmatrix}
+</tex>
+===Пример 3===
+Задуманная функция <tex>y=exp(7+log(5x))+\epsilon</tex>, где <tex>\epsilon</tex> - белый гауссовский шум. Рассматривается существенно нелинейная регрессионная модель с двумя параметрами: <tex>y(x)=exp(w_1+log(w_2x))</tex>.
+'''Фиксируем один параметр''' <tex>w_2=5</tex> и задаем различные значение <tex>w_1</tex> (10000 случайных значений на отрезке [6.5;7.5]). Строим зависимость:
+[[Изображение:Non_lin_1_par.png‎|center|frame]]
+<tex>D_{kl}(p_{SSE},p_{lap})=0.0794</tex>.
+'''Повторим эксперимент''', только теперь варьируем сразу оба параметра <tex>w_1</tex> и <tex>w_2</tex>(10000 случайных значений на отрезках [4.5;5.5] и [6.5;7.5] соответственно):
+[[Изображение:Non_lin_2_par.png‎|center|frame| Зависимость <tex>- SSE</tex> от <tex>w_1</tex> и <tex>w_2</tex>]]
+аппроксимация Лапласа:
+[[Изображение:Non_lin_2_par_laplas.png‎|center|frame| Laplace Approximation]]
+<tex>D_{kl}(p_{SSE},p_{lap})=0.0718</tex>
+ковариационная матрица
+<tex>A=10^{11}*\begin{Vmatrix}
+-2.7859 & 0.0056\\
+.0056 & 0.0146\\
+\end{Vmatrix}
+</tex>
 == Смотри также ==
@@ Строка 58: / Строка 143: @@
 * [[Сэмплирование]]
 * [http://en.wikipedia.org/wiki/Sampling_(statistics)#Notes Сэмплирование на вики]
-* [http://example.com/ Ссылка на текст статьи]
+* [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group774/Zaitsev2010Laplace/zaytsev_yevgen_laplace_aproximation/ Скачать код MATLAB можно здесь]
-* [http://example.com/ Ссылка на код]
 == Литература ==
@@ Строка 69: / Строка 153: @@
-{{Задание|Евгений Зайцев|В.В.Стрижов|24 декабря 2010|Yevgen.zaytsev|Strijov}}
+{{ЗаданиеВыполнено|Евгений Зайцев|В.В.Стрижов|24 декабря 2010|Yevgen.zaytsev|Strijov}}
 [[Категория:Практика и вычислительные эксперименты]]

Аппроксимация Лапласа (пример)

Материал из MachineLearning.

Текущая версия

Содержание

Постановка задачи

Описание алгоритма

Вычислительный эксперимент

Пример 1

Пример 2

Пример 3

Смотри также

Литература

Примечания

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты