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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 9: Строка 9:
<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>\alpha</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>
 +
 
==Обоснование формулы==
==Обоснование формулы==
 +
Строгим обоснованием формулы служит следующая теорема : <br />
 +
'''Теорема''' Пусть выполнены условия : <br />
 +
1) <br />
 +
2) <br />
 +
3) <br />
 +
4) <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>.
 +
==Литература==
==Литература==

Версия 14:17, 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)
2)
3)
4)
Тогда имеет место сходимость по вероятности : 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»
Личные инструменты