Просмотр

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

У вас нет прав на выполнение этой операции по следующим причинам:

• Запрошенное действие могут выполнять только участники из групп emailconfirmed, Администраторы.
• Вы должны подтвердить ваш адрес электронной почты перед правкой страниц. Пожалуйста, введите и подтвердите ваш адрес эл. почты на странице настроек.

Вы можете просмотреть и скопировать исходный текст этой страницы:

'''Формула Надарая-Ватсона''' используется для решения задачи непараметрического [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 восстановления регрессии]. == Постановка задачи == Пусть задано пространство объектов <tex>X</tex> и множество возможных ответов <tex>Y = \mathbb{R}</tex>. Существует неизвестная зависимость <tex>$y^*:X \rightarrow Y$</tex>, значения которой известны только на объектах обучающией выборки <tex>$ X^l = (x_i\ ,\ y_i)^l_{i=1},\ y_i = y^*(x_i) $</tex>. Требуется построить [[алгоритм]] <tex>a:\ X\rightarrow Y</tex>, аппроксимирующий неизвестную зависимость <tex>$y^*$</tex>. Предполагается, что на множестве <tex>X</tex> задана [[метрика]] <tex>\rho(x,x^')</tex>. ==Формула Надарая-Ватсона== Для вычисления <tex>$a(x) = \alpha$</tex> при <tex>$ \forall x \in X$</tex>, воспользуемся [http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0%D0%B8%D0%BC%D0%B5%D0%BD%D1%8C%D1%88%D0%B8%D1%85_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%BE%D0%B2 методом наименьших квадратов]: <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(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>$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>\rho(x,x_i) = |x - x_i|</tex> служит следующая теорема : <br /> '''Теорема''' Пусть выполнены условия : <br /> 1) выборка <tex>$X^l = (x_i,y_i)^l_{i=1}$</tex> получена случайно и независимо из распределения <tex>p(x,y)</tex> <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) восстанавливаемая зависимость, определяемая плотностью <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) последовательность <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>. ==Литература== 1) К. В. Воронцов, [[Машинное обучение (курс лекций, К.В.Воронцов)|Лекции по алгоритмам восстановления регрессии]], 2009<br /> 2) Хардле В. Прикладная непараметрическая регрессия. - М.: Мир, 1993. <br /> [[Категория:Непараметрическая регрессия]]

Возврат к странице Формула Надарая-Ватсона.