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

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

(Различия между версиями)
Перейти к: навигация, поиск
 
(15 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
{{Задание|Kolesnikov||8 января 2009}}
+
'''Формула Надарая-Ватсона''' используется для решения задачи непараметрического [http://www.machinelearning.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7 восстановления регрессии].
-
 
+
-
'''Формула Надарая-Ватсона''' используется для решения задачи непараметрического [[восстановления регрессии]].
+
== Постановка задачи ==
== Постановка задачи ==
Пусть задано пространство объектов <tex>X</tex> и множество возможных ответов <tex>Y = \mathbb{R}</tex>. Существует неизвестная зависимость <tex>$y^*:X \rightarrow Y$</tex>, значения которой известны только на объектах обучающией выборки <tex>$ X^l = (x_i\ ,\ y_i)^l_{i=1},\ y_i = y^*(x_i) $</tex>. Требуется построить [[алгоритм]] <tex>a:\ X\rightarrow Y</tex>, аппроксимирующий неизвестную зависимость <tex>$y^*$</tex>. Предполагается, что на множестве <tex>X</tex> задана [[метрика]] <tex>\rho(x,x^')</tex>.
Пусть задано пространство объектов <tex>X</tex> и множество возможных ответов <tex>Y = \mathbb{R}</tex>. Существует неизвестная зависимость <tex>$y^*:X \rightarrow Y$</tex>, значения которой известны только на объектах обучающией выборки <tex>$ X^l = (x_i\ ,\ y_i)^l_{i=1},\ y_i = y^*(x_i) $</tex>. Требуется построить [[алгоритм]] <tex>a:\ X\rightarrow Y</tex>, аппроксимирующий неизвестную зависимость <tex>$y^*$</tex>. Предполагается, что на множестве <tex>X</tex> задана [[метрика]] <tex>\rho(x,x^')</tex>.
==Формула Надарая-Ватсона==
==Формула Надарая-Ватсона==
-
Для вычисления <tex>$a(x) = \alpha$</tex> при <tex>$ \forall x \in X$</tex>, воспользуемся [[методом наименьших квадратов]]: <br />
+
Для вычисления <tex>$a(x) = \alpha$</tex> при <tex>$ \forall x \in X$</tex>, воспользуемся [http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0%D0%B8%D0%BC%D0%B5%D0%BD%D1%8C%D1%88%D0%B8%D1%85_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%BE%D0%B2 методом наименьших квадратов]: <br />
<tex>Q(\alpha;X^l) = \sum_{i=1}^l \omega_i(x)(\alpha-y_i)^2 \rightarrow \underset{\alpha \in \mathbb{R}}{min}</tex>, где <tex>\omega_i</tex> - это вес i-ого объекта. <br />
<tex>Q(\alpha;X^l) = \sum_{i=1}^l \omega_i(x)(\alpha-y_i)^2 \rightarrow \underset{\alpha \in \mathbb{R}}{min}</tex>, где <tex>\omega_i</tex> - это вес i-ого объекта. <br />
Веса <tex>\omega_i</tex> разумно задать так, чтобы они убывали по мере увеличения расстояния <tex>\rho(x,x_i)</tex>. Для этого можно ввести невозрастающую, гладкую, ограниченную функцию <tex>K:[0, \infty) \rightarrow [0, \infty)</tex>, называемую [[ядром]], и представить <tex>\omega_i</tex> в следующем виде : <br />
Веса <tex>\omega_i</tex> разумно задать так, чтобы они убывали по мере увеличения расстояния <tex>\rho(x,x_i)</tex>. Для этого можно ввести невозрастающую, гладкую, ограниченную функцию <tex>K:[0, \infty) \rightarrow [0, \infty)</tex>, называемую [[ядром]], и представить <tex>\omega_i</tex> в следующем виде : <br />
-
<tex>\omega_i(x) = K\left(\frac{\rho(x,x_i)}{h} \right )</tex> <br />
+
<tex>\omega_i(x) = K\left(\frac{\rho(x,x_i)}{h} \right )</tex>, где <tex>h</tex> — ширина окна. <br />
-
Приравняв нулю производную <tex>\frac{\partial Q}{\partial \alpha} = 0</tex>,получаем формулу '''Надалая-Ватсона''' :
+
Приравняв нулю производную <tex>\frac{\partial Q}{\partial \alpha} = 0</tex>, и, выразив <tex>\alpha</tex>,получаем '''формулу Надарая-Ватсона''' :
-
<tex>$a(x;X^l) = \frac{\sum_{i=1}^{l} y_i\omega_i(x)}{\sum_{i=1}^{l} \omega_i(x)}$</tex>
+
<tex>$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 )}$</tex>
 +
 
==Обоснование формулы==
==Обоснование формулы==
 +
Строгим обоснованием формулы в одномерном случае с метрикой <tex>\rho(x,x_i) = |x - x_i|</tex> служит следующая теорема : <br />
 +
'''Теорема''' Пусть выполнены условия : <br />
 +
1) выборка <tex>$X^l = (x_i,y_i)^l_{i=1}$</tex> получена случайно и независимо из распределения <tex>p(x,y)</tex> <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) восстанавливаемая зависимость, определяемая плотностью <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) последовательность <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>.
 +
==Литература==
==Литература==
 +
1) К. В. Воронцов, [[Машинное обучение (курс лекций, К.В.Воронцов)|Лекции по алгоритмам восстановления регрессии]], 2009<br />
 +
2) Хардле В. Прикладная непараметрическая регрессия. - М.: Мир, 1993. <br />
 +
 +
[[Категория:Непараметрическая регрессия]]

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

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

Содержание

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

Пусть задано пространство объектов 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://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»
Личные инструменты