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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 16: Строка 16:
Строгим обоснованием формулы служит следующая теорема : <br />
Строгим обоснованием формулы служит следующая теорема : <br />
'''Теорема''' Пусть выполнены условия : <br />
'''Теорема''' Пусть выполнены условия : <br />
-
1) <br />
+
1) выборка <tex>X^l = (x_i,y_i)^l_{i=1}</tex> получена случайно и независимо из распределения <tex>p(x,y)</tex> <br />
-
2) <br />
+
2) ядро <tex>K(r)</tex> удовлетворяет ограничениям <tex>\int^\infty_0 K(r)dr < \infty</tex> и <tex>\underset{r \rightarrow \infty}{lim} rK(r) = 0 </tex> <br />
-
3) <br />
+
3) восстанавливаемая зависимость, определяемая плотностью <tex>p(y|x)</tex>, удавлетворяет при любом <tex>x \in X</tex> ограничению <tex>E(y^2|x) = \int_Y y^2p(y|x)dy < \infty</tex><br />
-
4) <br />
+
4) последовательность <tex>h_l</tex> такова, что <tex>\underset{l \rightarrow \infty}{lim} h_l = 0</tex> и <tex>\underset{l \rightarrow \infty}{lim}\ lh_l = \infty</tex> <br />
 +
 
Тогда имеет место [[сходимость по вероятности]] : <tex>a_{h_l}(x; X^l) \overset{P}{\rightarrow} E(y|x)</tex> в любой точке <tex>x \in X</tex>, в которой <tex>E(y|x), p(x)</tex> и <tex>D(y|x)</tex> непрерывны и <tex>p(x) > 0</tex>.
Тогда имеет место [[сходимость по вероятности]] : <tex>a_{h_l}(x; X^l) \overset{P}{\rightarrow} E(y|x)</tex> в любой точке <tex>x \in X</tex>, в которой <tex>E(y|x), p(x)</tex> и <tex>D(y|x)</tex> непрерывны и <tex>p(x) > 0</tex>.
==Литература==
==Литература==

Версия 14:31, 5 января 2010

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

До указанного срока статья не должна редактироваться другими участниками проекта 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 )}$

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

Строгим обоснованием формулы служит следующая теорема :
Теорема Пусть выполнены условия :
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.

Литература

Источник — «http://machinelearning.ru/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»
Личные инструменты