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

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

Версия от 14:39, 5 января 2010; Kolesnikov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Перейти к: навигация, поиск

Данная статья является непроверенным учебным заданием.

Студент: Участник: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$ , воспользуемся методом наименьших квадратов:

, где  - это вес 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$ ,получаем формулу Надарая-Ватсона :

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

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