Формула Надарая-Ватсона
Материал из MachineLearning.
Формула Надарая-Ватсона используется для решения задачи непараметрического восстановления регрессии.
Содержание |
Постановка задачи
Пусть задано пространство объектов и множество возможных ответов
. Существует неизвестная зависимость
, значения которой известны только на объектах обучающией выборки
. Требуется построить алгоритм
, аппроксимирующий неизвестную зависимость
. Предполагается, что на множестве
задана метрика
.
Формула Надарая-Ватсона
Для вычисления при
, воспользуемся методом наименьших квадратов:
, где
- это вес i-ого объекта.
Веса разумно задать так, чтобы они убывали по мере увеличения расстояния
. Для этого можно ввести невозрастающую, гладкую, ограниченную функцию
, называемую ядром, и представить
в следующем виде :
, где
— ширина окна.
Приравняв нулю производную , и, выразив
,получаем формулу Надарая-Ватсона :
Обоснование формулы
Строгим обоснованием формулы в одномерном случае с метрикой служит следующая теорема :
Теорема Пусть выполнены условия :
1) выборка получена случайно и независимо из распределения
2) ядро удовлетворяет ограничениям
и
3) восстанавливаемая зависимость, определяемая плотностью , удавлетворяет при любом
ограничению
4) последовательность такова, что
и
Тогда имеет место сходимость по вероятности : в любой точке
, в которой
и
непрерывны и
.
Литература
1) К. В. Воронцов, Лекции по алгоритмам восстановления регрессии, 2009
2) Хардле В. Прикладная непараметрическая регрессия. - М.: Мир, 1993.