Формула Надарая-Ватсона
Материал из MachineLearning.
(11 промежуточных версий не показаны.) | |||
Строка 1: | Строка 1: | ||
- | |||
- | |||
'''Формула Надарая-Ватсона''' используется для решения задачи непараметрического [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 восстановления регрессии]. | '''Формула Надарая-Ватсона''' используется для решения задачи непараметрического [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 восстановления регрессии]. | ||
== Постановка задачи == | == Постановка задачи == | ||
Строка 9: | Строка 7: | ||
<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>, где <tex>h</tex> | + | <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_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>$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 /> | + | Строгим обоснованием формулы в одномерном случае с метрикой <tex>\rho(x,x_i) = |x - x_i|</tex> служит следующая теорема : <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>. | ||
==Литература== | ==Литература== | ||
+ | 1) К. В. Воронцов, [[Машинное обучение (курс лекций, К.В.Воронцов)|Лекции по алгоритмам восстановления регрессии]], 2009<br /> | ||
+ | 2) Хардле В. Прикладная непараметрическая регрессия. - М.: Мир, 1993. <br /> | ||
+ | |||
+ | [[Категория:Непараметрическая регрессия]] |
Текущая версия
Формула Надарая-Ватсона используется для решения задачи непараметрического восстановления регрессии.
Содержание |
Постановка задачи
Пусть задано пространство объектов и множество возможных ответов . Существует неизвестная зависимость , значения которой известны только на объектах обучающией выборки . Требуется построить алгоритм , аппроксимирующий неизвестную зависимость . Предполагается, что на множестве задана метрика .
Формула Надарая-Ватсона
Для вычисления при , воспользуемся методом наименьших квадратов:
, где - это вес i-ого объекта.
Веса разумно задать так, чтобы они убывали по мере увеличения расстояния . Для этого можно ввести невозрастающую, гладкую, ограниченную функцию , называемую ядром, и представить в следующем виде :
, где — ширина окна.
Приравняв нулю производную , и, выразив ,получаем формулу Надарая-Ватсона :
Обоснование формулы
Строгим обоснованием формулы в одномерном случае с метрикой служит следующая теорема :
Теорема Пусть выполнены условия :
1) выборка получена случайно и независимо из распределения
2) ядро удовлетворяет ограничениям и
3) восстанавливаемая зависимость, определяемая плотностью , удавлетворяет при любом ограничению
4) последовательность такова, что и
Тогда имеет место сходимость по вероятности : в любой точке , в которой и непрерывны и .
Литература
1) К. В. Воронцов, Лекции по алгоритмам восстановления регрессии, 2009
2) Хардле В. Прикладная непараметрическая регрессия. - М.: Мир, 1993.