Алгоритм LOWESS

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

(Различия между версиями)
Перейти к: навигация, поиск
(Постановка задачи)
(Постановка задачи)
Строка 8: Строка 8:
=== Постановка задачи ===
=== Постановка задачи ===
Решается задача восстановления регрессии. Задано пространство объектов <tex>X</tex> и множество возможных
Решается задача восстановления регрессии. Задано пространство объектов <tex>X</tex> и множество возможных
-
ответов <tex>Y</tex>. Существует неизвестная целевая зависимость <tex> y^*: X \rightarrow Y</tex>,
+
ответов <tex>Y=R</tex>. Существует неизвестная целевая зависимость <tex> y^*: X \rightarrow Y</tex>,
значения которой известны только на объектах обучающей выборки <tex> X^m={(x_i, y_i)}_1^m</tex>
значения которой известны только на объектах обучающей выборки <tex> X^m={(x_i, y_i)}_1^m</tex>
Требуется построить алгоритм <tex>a: X \rightarrow Y </tex>, аппроксимирующий целевую зависимость <tex>y^*</tex>.
Требуется построить алгоритм <tex>a: X \rightarrow Y </tex>, аппроксимирующий целевую зависимость <tex>y^*</tex>.
Строка 14: Строка 14:
Непараметрическое восстановление регрессии основано на идее, что значение <tex>a(x)</tex> вычисляется
Непараметрическое восстановление регрессии основано на идее, что значение <tex>a(x)</tex> вычисляется
для каждого объекта <tex>x</tex> по нескольким ближайшим к нему объектам обучающей выборки.
для каждого объекта <tex>x</tex> по нескольким ближайшим к нему объектам обучающей выборки.
 +
 +
В формуле Надарая–Ватсона для учета близости объектов <tex>x_i</tex> обучающей выборки к объекту <tex>a(x)</tex>
 +
предлагалось использовать невозрастающую, гладкую, ограниченную функцию
 +
<tex>K: [0,∞) \rightarrow [0,∞)</tex>, называемую ядром:
 +
 +
::<tex>w_i(x) = K\left( \frac{\ro(x, xi)}{h}\right)</tex>
=== Вход ===
=== Вход ===

Версия 20:34, 28 декабря 2009

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

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


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

Содержание

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

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

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

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

w_i(x) = K\left(  \frac{\ro(x, xi)}{h}\right)

Вход

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. Как правило, этот процесс сходится довольно быстро.

Литература

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

См. также


Данная статья является непроверенным учебным заданием.
Студент: Участник:Валентин Голодов
Преподаватель: Участник:Vokov
Срок: 31 декабря 2009

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

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


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