Алгоритм LOWESS

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

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

Перейти к: навигация, поиск

Версия 21:39, 28 декабря 2009

Статья плохо доработана.

Имеются указания по её улучшению:

Алгоритм LOWESS (locally weighted scatter plot smoothing) - локально взвешенное сглаживание.

Содержание

1 Постановка задачи
2 Непараметрическая регрессия
- 2.1 Оптимизация ширины окна
3 Вход
4 Выход
5 Алгоритм
6 Литература
7 См. также

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

Решается задача восстановления регрессии. Задано пространство объектов $X$ и множество возможных ответов $Y=R$ . Существует неизвестная целевая зависимость $y^*: X \rightarrow Y$ , значения которой известны только на объектах обучающей выборки $X^m={(x_i, y_i)}_{i=1}^m$ Требуется построить алгоритм $a: X \rightarrow Y$ , аппроксимирующий целевую зависимость $y^*$ .

Непараметрическая регрессия

Непараметрическое восстановление регрессии основано на идее, что значение $a(x)$ вычисляется для каждого объекта $x$ по нескольким ближайшим к нему объектам обучающей выборки.

В формуле Надарая–Ватсона для учета близости объектов $x_i$ обучающей выборки к объекту $a(x)$ предлагалось использовать невозрастающую, гладкую, ограниченную функцию $K: [0,\infty) \rightarrow [0,\infty)$ , называемую ядром:

$w_i(x) = K\left( \frac{\rho(x, x_i)}{h}\right)$

Параметр $h$ называется шириной ядра или шириной окна сглаживания. Чем меньше $h$ , тем быстрее будут убывать веса $w_i(x)$ по мере удаления $x_i(x)$ от $x$ .

Оптимизация ширины окна

Чтобы оценить при данном $h$ или $K$ точность локальной аппроксимации в точке $x_i$ , саму эту точку необходимо исключить из обучающей выборки. Если этого не делать, минимум ошибки будет достигаться при $h\rightarrow 0$ . Такой способ оценивания называется скользящим контролем с исключением объектов по одному (leave-one-out, LOO):

$LOO(h,X^m) = \sum_{i=1}^m{(a_h(x_i;X^m\setminus\{x_i\}) - y_i)^2} \rightarrow min\limits_h$

Оценка Надарайя–Ватсона $\textstyle a_h(x,X^m) = \frac{\sum_{i=1}^m{y_iw_i}}{\sum_{i=1}^m{w_i}}$ крайне чувствительна к большим одиночным выбросам. На практике легко идентифицируются только грубые ошибки, возникающие, например, в результате сбоя оборудования или невнимательности персонала при подготовке данных. В общем случае можно лишь утверждать, что чем больше величина ошибки

$\varepsilon_i = \left | a_h \left (x_i;X^m\setminus\{x_i\} \right) -y_i \right |$

тем в большей степени прецедент $(x_i,y_i)$ является выбросом , и тем меньше должен быть его вес. Эти соображения приводят к идее домножить веса $w_i(x)$ на коэффициенты $\gamma_i = \bar{K}(\varepsilon_i)$ , где $\bar{K}$ — ещё одно ядро, вообще говоря, отличное от $K$ .

Вход

$X^l$ - обучающая выборка

Выход

Коэффициенты $\gamma_i, i=1,\ldots,l$

Алгоритм

1: инициализация

$\gamma_i:=1, i=1,\ldots,l$

2: повторять 3: вычислить оценки скользящего контроля на каждом объекте:

$a_i:=a_h$ x_i;X^l\setminus\{x_i\} $=\frac{\sum_{j=1,j\ne i}^ly_j\gamma_jK$\frac{\rho(x_i,x_j)}{h(x_i)}$}{\sum_{j=1,j\ne i}^l\gamma_jK$\frac{\rho(x_i,x_j)}{h(x_i)}$},\;i=1,\ldots,l$

4: вычислить коэффициенты $\gamma_i$ :

$\gamma_i:=\tilde{K}( \| a_i\;-\;y_i\| ) ,\;i=1,\ldots,l$ ;

5: пока коэффициенты $\gamma_i$ не стабилизируются

Коэффициенты $\gamma_i$ , как и ошибки $\epsilon_i$ , зависят от функции $a_h$ , которая, в свою очередь, зависит от $\gamma_i$ . Разумеется, это не "порочный круг", а хороший повод для организации итерационного процесса. На каждой итерации строится функция $a_h$ , затем уточняются весовые множители $\gamma_i$ . Как правило, этот процесс сходится довольно быстро.

Литература

Воронцов К.В. Лекции по алгоритмам восстановления регрессии. — 2007.

См. также

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

Студент: Участник:Валентин Голодов

Преподаватель: Участник:Vokov

Срок: 31 декабря 2009

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

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

→

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_LOWESS»

Категории: Регрессионный анализ | Непроверенные учебные задания

@@ Строка 12: / Строка 12: @@
 Требуется построить алгоритм <tex>a: X \rightarrow Y </tex>, аппроксимирующий целевую зависимость <tex>y^*</tex>.
+=== Непараметрическая регрессия ===
 Непараметрическое восстановление регрессии основано на идее, что значение <tex>a(x)</tex> вычисляется
 для каждого объекта <tex>x</tex> по нескольким ближайшим к нему объектам обучающей выборки.
@@ Строка 24: / Строка 25: @@
 тем быстрее будут убывать веса <tex>w_i(x)</tex> по мере удаления <tex>x_i(x)</tex> от <tex>x</tex>.
-===Оптимизация ширины окна===
+====Оптимизация ширины окна====
 Чтобы оценить при данном <tex>h</tex> или <tex>K</tex> точность локальной аппроксимации в точке <tex>x_i</tex>,
 саму эту точку необходимо исключить из обучающей выборки. Если этого не делать, минимум ошибки будет