Аппроксимация функции ошибки

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

(Различия между версиями)
Перейти к: навигация, поиск
 
(57 промежуточных версий не показаны.)
Строка 1: Строка 1:
{{TOCright}}
{{TOCright}}
-
В работе рассматривается метод аппроксимации функции ошибки функцией многомерного нормального распределения. Рассматриваются случаи матрицы ковариации общего вида, диагональной матрицы ковариации, а также диагональной матрицы ковариации с равными значениями дисперсии. Для нормировки получившихся функций распределения используется [[аппроксимация Лапласа | Аппроксимация Лапласа]].
+
В работе рассматривается метод аппроксимации функции ошибки функцией многомерного нормального распределения. Рассматриваются случаи матрицы ковариации общего вида, диагональной матрицы ковариации, а также диагональной матрицы ковариации с равными значениями дисперсии. Для нормировки получившихся функций распределения используется [[ Аппроксимация Лапласа | аппроксимация Лапласа]].
== Постановка задачи ==
== Постановка задачи ==
-
Задана выборка <tex>\{(\mathbf{x}_i,y_i)\}_{i=1}^m</tex>, в которой ...
+
Дана выборка <tex>D = \{(x_i, y_i)\}_{i = 1}^N</tex>, где <tex>x_i \in \mathbb{R}^n, i = 1, \dots, N</tex> - вектора независимой переменной, а <tex>y_i \in \mathbb{R}, i = 1, \dots, N</tex> - значения зависимой переменной.
 +
Предполагается, что
 +
<center><tex>y = f(x, w)</tex>, где <tex>f(x, w)</tex> - некоторая параметрическая функция, <tex>w \in W</tex> - вектор ее параметров.</center>
 +
Также предполагается, что задано апостериорное распределение параметров модели <tex>p(w | D, f)</tex>, которому соответствует функция ошибки <tex>S(w)</tex>:
 +
<center><tex>p(w | D, f) = \frac{exp(-S(w))}{Z_S}</tex>.</center>
 +
Пусть <tex>w_{MP} = \arg\max_w p(w | D, f)</tex> - наиболее вероятные параметры модели. Требуется найти [[Аппроксимация Лапласа | аппроксимацию Лапласа]] для функции <tex>p(w | D, f)</tex> в точке <tex>w_{MP}</tex>. Заметим, что в данной работе в качестве функции ошибки берется сумма квадратов ошибок аппроксимации
 +
<center><tex>S(w) = \sum_{i = 1}^N (y_i - f(x_i, w))^2</tex>.</center>
== Описание решения ==
== Описание решения ==
-
* '''настолько подробно, что по математическому описанию можно было бы восстановить код'''
+
Сначала находим оптимальные значения параметров модели <tex>w</tex>:
 +
<center><tex>w_{MP} = \arg\max_w p(w | D, f).</tex></center>
 +
Далее необходимо найти аппроксимацию Лапласа в точке <tex>w_{MP}</tex>:
 +
<center><tex>p^*(w| k, A) = k * \exp(-(w - w_{MP})^T A (w - w_{MP}))</tex>,</center>
 +
где <tex>A</tex> - матрица, обратная к ковариационной матрице нормального распределения, а <tex>k</tex> - нормирующий коэффициент. Заметим, что в силу положительной определенности матрицы <tex>A</tex> ее можно представить в соответствии с разложением Холецкого: <tex>A = L L^T</tex>, где <tex>L</tex> - верхнетреугольная матрица. Параметризуем матрицу <tex>L</tex> следующим образом:
 +
<center><tex>L(i, j) = \begin{cases}e^{h_{ij}} & i = j, \\ sinh(h_{ij}) & j > i, \\ 0 & j < i, \\ \end{cases}</tex> где <tex>h_{ij} \in \mathbb{R}, i, j = 1, \dots, N, j \ge i</tex>.</center>
 +
Также параметризуем нормирующий множитель <tex>k = exp(h_0)</tex>.
 +
Получаем, что <tex>p^*(w | A, k) = p^*(w | h_{ij}, i, j = 1, \dots, N, j \ge i, h_0)</tex>.
 +
Построим обучающую выборку <tex>D_S = (w_k, S(w_k)), k = 1, \dots, N_S</tex>, где точки <tex>w_k</tex> берутся равномерно из окрестности наиболее вероятных параметров <tex>w_{MP}</tex>, в которой мы хотим построить аппроксимацию.
 +
Для нахождения неизвестных параметров <tex>h_{ij}, i, j = 1, \dots, N, j \ge i, h_0</tex> минимизируем квадратичный критерий для точек обучающей выборки <tex>D_S</tex>:
 +
<center><tex>\sum_{k = 1}^{N_S} (S(w_k) - p^*(w_k | h_{ij}, h_0))^2 \to \min_{h_{ij}, h_0}.</tex></center>
-
== Вычислительный эксперимент ==
+
Заметим, что получаемые в результате решения данной оптимизационной задачи значения параметров могут существенно отличаться в зависимости от используемого для ее решения оптимизационного алгоритма. В данной работе рассматриваются два алгоритма оптимизации: [[Алгоритм Левенберга-Марквардта | Левенберг-Марквардт]] и [[Trust region | Trust region]].
-
Цель вычислительного эксперимента&nbsp;- ...
+
-
* '''описание эксперимента'''
+
После нахождения оптимальных значений параметров полученные распределения остается отнормировать в соответствии с аппроксимацией Лапласа:
-
* '''иллюстрации с комментариями'''
+
<center><tex>Z_S = exp(-S(w_{MP})) * \sqrt{\frac{(2 \pi)^n}{\det A}}</tex>.</center>
-
<source lang="matlab">
+
== Вычислительный эксперимент: качество аппроксимации ==
-
y = 1; % There is no need to post all your code here. Only extracts and only if it is necessary.
+
В эксперименте в качестве обучающей выборки использовался временной ряд цен на хлеб из 195 точек. Для приближения использовалась модель линейной регрессии <tex>f(x, w) = w_1 + w_2 * x^2</tex>. На картинках ниже графически представлены результаты.
-
</source>
+
 +
[[Изображение:results.png|1150px|thumb|Результаты эксперимента]]
-
[[Изображение:ModelBreadSw.png|200px|thumb|Функция ошибки, пример графика]]
+
Функция ошибки в рассмотренном случае хорошо аппроксимируется предложенным методом, причем качество аппроксимации возрастает с увеличением качества модели. Хорошее качество аппроксимации обусловлено тем, что функция ошибки в рассматриваемом примере принадлежит тому же классу, что и функция аппроксиматор.
-
Требования к оформлению графиков:
+
== Вычислительный эксперимент: устойчивость алгоритма ==
-
* шрифт должен быть больше,
+
Для сравнения устойчивости алгоритмов Левенберга-Марквардта и Trust region в качестве обучающей выборки использовался временной ряд цен на хлеб из 195 точек. Для приближения использовалась регрессионная модель <tex>f(x, w) = \frac{1 - \exp(w_1 + w_2 * x)}{1 + \exp(w_1 + w_2 * x)}</tex>. При таком виде целевой функции вид функции ошибки в окрестности оптимума несколько отличается от гауссовского. Рассматривалась зависимость оптимизированного значения параметров <tex>h_0</tex> и <tex>h_{22}</tex> от начального значения.
-
* толщина линий равна двум,
+
-
* заголовки осей с большой буквы,
+
-
* заголовок графика отсутствует (чтобы не дублировать подпись в статье);
+
-
* рекомендуется сразу сохранять EPS и PNG (для TeX и для Wiki).
+
-
<source lang="matlab">
+
<gallery widths="500px" heights="300px">
-
h = figure; hold('on');
+
Изображение:approximationSigmoid.png | Аппроксимация данных
-
plot(xi,y,'r-', 'Linewidth', 2);
+
Изображение:errorSigmoid.png | Функция ошибки
-
plot(xi,y,'b.', 'MarkerSize', 12);
+
</gallery>
-
axis('tight');
+
 
-
xlabel('Time, $\xi$', 'FontSize', 24, 'FontName', 'Times', 'Interpreter','latex');
+
<gallery widths="500px" heights="300px">
-
ylabel('Value, $y$', 'FontSize', 24, 'FontName', 'Times', 'Interpreter','latex');
+
Изображение:fullSigmoid.png | Аппроксимация функции ошибки в случае ковариационной матрицы общего вида
-
set(gca, 'FontSize', 24, 'FontName', 'Times')
+
</gallery>
-
saveas(h,'ModelOne.eps', 'psc2');
+
 
-
saveas(h,'ModelOne.png', 'png');
+
<gallery widths="500px" heights="300px">
-
</source>
+
Изображение:stability1.png | Зависимость значения параметра <tex>h_0</tex>, полученного в результате оптимизации от его начального значения.
 +
Изображение:stability2.png | Зависимость значения параметра <tex>h_{22}</tex>, полученного в результате оптимизации от его начального значения.
 +
</gallery>
== Исходный код и полный текст работы ==
== Исходный код и полный текст работы ==
Строка 43: Строка 57:
== Смотри также ==
== Смотри также ==
-
* [[Метод ближайших соседей]]
+
* [[Аппроксимация Лапласа]]
-
* [[Многомерная случайная величина]]
+
* [[Алгоритм Левенберга-Марквардта]]
== Литература ==
== Литература ==
* [http://ya.ru Bishop, C. Pattern Recognition And Machine Learning. Springer. 2006.]
* [http://ya.ru Bishop, C. Pattern Recognition And Machine Learning. Springer. 2006.]
-
{{Задание|Максим Панов|В.В. Стрижов|28 сентября 2011|Maxx|Strijov}}
+
{{ЗаданиеВыполнено|Максим Панов|В.В. Стрижов|2 декабря 2011|Maxx|Strijov}}
[[Категория:Практика и вычислительные эксперименты]]
[[Категория:Практика и вычислительные эксперименты]]

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

Содержание

В работе рассматривается метод аппроксимации функции ошибки функцией многомерного нормального распределения. Рассматриваются случаи матрицы ковариации общего вида, диагональной матрицы ковариации, а также диагональной матрицы ковариации с равными значениями дисперсии. Для нормировки получившихся функций распределения используется аппроксимация Лапласа.

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

Дана выборка D = \{(x_i, y_i)\}_{i = 1}^N, где x_i \in \mathbb{R}^n, i = 1, \dots, N - вектора независимой переменной, а y_i \in \mathbb{R}, i = 1, \dots, N - значения зависимой переменной. Предполагается, что

y = f(x, w), где f(x, w) - некоторая параметрическая функция, w \in W - вектор ее параметров.

Также предполагается, что задано апостериорное распределение параметров модели p(w | D, f), которому соответствует функция ошибки S(w):

p(w | D, f) = \frac{exp(-S(w))}{Z_S}.

Пусть w_{MP} = \arg\max_w p(w | D, f) - наиболее вероятные параметры модели. Требуется найти аппроксимацию Лапласа для функции p(w | D, f) в точке w_{MP}. Заметим, что в данной работе в качестве функции ошибки берется сумма квадратов ошибок аппроксимации

S(w) = \sum_{i = 1}^N (y_i - f(x_i, w))^2.

Описание решения

Сначала находим оптимальные значения параметров модели w:

w_{MP} = \arg\max_w p(w | D, f).

Далее необходимо найти аппроксимацию Лапласа в точке w_{MP}:

p^*(w| k, A) = k * \exp(-(w - w_{MP})^T A (w - w_{MP})),

где A - матрица, обратная к ковариационной матрице нормального распределения, а k - нормирующий коэффициент. Заметим, что в силу положительной определенности матрицы A ее можно представить в соответствии с разложением Холецкого: A = L L^T, где L - верхнетреугольная матрица. Параметризуем матрицу L следующим образом:

L(i, j) = \begin{cases}e^{h_{ij}} & i = j, \\ sinh(h_{ij}) & j > i, \\ 0 & j < i, \\ \end{cases} где h_{ij} \in \mathbb{R}, i, j = 1, \dots, N, j \ge i.

Также параметризуем нормирующий множитель k = exp(h_0). Получаем, что p^*(w | A, k) = p^*(w | h_{ij}, i, j = 1, \dots, N, j \ge i, h_0). Построим обучающую выборку D_S = (w_k, S(w_k)), k = 1, \dots, N_S, где точки w_k берутся равномерно из окрестности наиболее вероятных параметров w_{MP}, в которой мы хотим построить аппроксимацию. Для нахождения неизвестных параметров h_{ij}, i, j = 1, \dots, N, j \ge i, h_0 минимизируем квадратичный критерий для точек обучающей выборки D_S:

\sum_{k = 1}^{N_S} (S(w_k) - p^*(w_k | h_{ij}, h_0))^2 \to \min_{h_{ij}, h_0}.

Заметим, что получаемые в результате решения данной оптимизационной задачи значения параметров могут существенно отличаться в зависимости от используемого для ее решения оптимизационного алгоритма. В данной работе рассматриваются два алгоритма оптимизации: Левенберг-Марквардт и Trust region.

После нахождения оптимальных значений параметров полученные распределения остается отнормировать в соответствии с аппроксимацией Лапласа:

Z_S = exp(-S(w_{MP})) * \sqrt{\frac{(2 \pi)^n}{\det A}}.

Вычислительный эксперимент: качество аппроксимации

В эксперименте в качестве обучающей выборки использовался временной ряд цен на хлеб из 195 точек. Для приближения использовалась модель линейной регрессии f(x, w) = w_1 + w_2 * x^2. На картинках ниже графически представлены результаты.

Результаты эксперимента
Результаты эксперимента

Функция ошибки в рассмотренном случае хорошо аппроксимируется предложенным методом, причем качество аппроксимации возрастает с увеличением качества модели. Хорошее качество аппроксимации обусловлено тем, что функция ошибки в рассматриваемом примере принадлежит тому же классу, что и функция аппроксиматор.

Вычислительный эксперимент: устойчивость алгоритма

Для сравнения устойчивости алгоритмов Левенберга-Марквардта и Trust region в качестве обучающей выборки использовался временной ряд цен на хлеб из 195 точек. Для приближения использовалась регрессионная модель f(x, w) = \frac{1 - \exp(w_1 + w_2 * x)}{1 + \exp(w_1 + w_2 * x)}. При таком виде целевой функции вид функции ошибки в окрестности оптимума несколько отличается от гауссовского. Рассматривалась зависимость оптимизированного значения параметров h_0 и h_{22} от начального значения.

Аппроксимация данных

Функция ошибки

Аппроксимация функции ошибки в случае ковариационной матрицы общего вида

Зависимость значения параметра h_0, полученного в результате оптимизации от его начального значения.

Зависимость значения параметра h_{22}, полученного в результате оптимизации от его начального значения.

Исходный код и полный текст работы

Смотри также

Литература

Данная статья была создана в рамках учебного задания.
Студент: Максим Панов
Преподаватель: В.В. Стрижов
Срок: 2 декабря 2011


В настоящее время задание завершено и проверено. Данная страница может свободно правиться другими участниками проекта 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_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8_%D0%BE%D1%88%D0%B8%D0%B1%D0%BA%D0%B8»
Личные инструменты