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

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

(Перенаправлено с Оценка Надарая-Ватсона)

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

Содержание

1 Постановка задачи
2 Формула Надарая-Ватсона
3 Обоснование формулы
4 Литература

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

Пусть задано пространство объектов $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$ ,получаем формулу Надарая-Ватсона :

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

Строгим обоснованием формулы в одномерном случае с метрикой $\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$ .