Формула Надарая-Ватсона

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 14: Строка 14:
==Обоснование формулы==
==Обоснование формулы==
-
Строгим обоснованием формулы в одномерном случае служит следующая теорема : <br />
+
Строгим обоснованием формулы в одномерном случае с метрикой <tex>\rho(x,x_i) = |x - x_i|</tex> служит следующая теорема : <br />
'''Теорема''' Пусть выполнены условия : <br />
'''Теорема''' Пусть выполнены условия : <br />
1) выборка <tex>$X^l = (x_i,y_i)^l_{i=1}$</tex> получена случайно и независимо из распределения <tex>p(x,y)</tex> <br />
1) выборка <tex>$X^l = (x_i,y_i)^l_{i=1}$</tex> получена случайно и независимо из распределения <tex>p(x,y)</tex> <br />

Версия 21:25, 6 января 2010

Данная статья является непроверенным учебным заданием.
Студент: Участник:Kolesnikov
Преподаватель: Участник:Константин Воронцов
Срок: 8 января 2010

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

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


Формула Надарая-Ватсона используется для решения задачи непараметрического восстановления регрессии.

Содержание

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

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

Формула Надарая-Ватсона

Для вычисления $a(x) = \alpha$ при $ \forall x \in X$, воспользуемся методом наименьших квадратов: 

Q(\alpha;X^l) = \sum_{i=1}^l \omega_i(x)(\alpha-y_i)^2 \rightarrow \underset{\alpha \in \mathbb{R}}{min}, где \omega_i - это вес i-ого объекта.

Веса \omega_i разумно задать так, чтобы они убывали по мере увеличения расстояния \rho(x,x_i). Для этого можно ввести невозрастающую, гладкую, ограниченную функцию K:[0, \infty) \rightarrow [0, \infty), называемую ядром, и представить \omega_i в следующем виде :
\omega_i(x) = K\left(\frac{\rho(x,x_i)}{h} \right ), где h — ширина окна.
Приравняв нулю производную \frac{\partial Q}{\partial \alpha} = 0, и, выразив \alpha,получаем формулу Надарая-Ватсона : 

$a_h(x;X^l) = \frac{\sum_{i=1}^{l} y_i\omega_i(x)}{\sum_{i=1}^{l} \omega_i(x)} = \frac{\sum_{i=1}^{l} y_iK\left(\frac{\rho(x,x_i)}{h} \right )}{\sum_{i=1}^{l} K\left(\frac{\rho(x,x_i)}{h} \right )}$

Обоснование формулы

Строгим обоснованием формулы в одномерном случае с метрикой \rho(x,x_i) = |x - x_i| служит следующая теорема :
Теорема Пусть выполнены условия :
1) выборка $X^l = (x_i,y_i)^l_{i=1}$ получена случайно и независимо из распределения p(x,y)
2) ядро K(r) удовлетворяет ограничениям \int^\infty_0 K(r)dr < \infty и \underset{r \rightarrow \infty}{lim} rK(r) = 0
3) восстанавливаемая зависимость, определяемая плотностью p(y|x), удавлетворяет при любом x \in X ограничению E(y^2|x) = \int_Y y^2p(y|x)dy < \infty
4) последовательность h_l такова, что \underset{l \rightarrow \infty}{lim} h_l = 0 и \underset{l \rightarrow \infty}{lim}\ lh_l = \infty

Тогда имеет место сходимость по вероятности : a_{h_l}(x; X^l) \overset{P}{\rightarrow} E(y|x) в любой точке x \in X, в которой E(y|x), p(x) и D(y|x) непрерывны и p(x) > 0.

Литература

1) К. В. Воронцов, Лекции по алгоритмам восстановления регрессии, 2009
2) Хардле В. Прикладная непараметрическая регрессия. - М.: Мир, 1993.

Источник — «http://www.recognition.su/wiki/index.php?title=%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%9D%D0%B0%D0%B4%D0%B0%D1%80%D0%B0%D1%8F-%D0%92%D0%B0%D1%82%D1%81%D0%BE%D0%BD%D0%B0»
Личные инструменты