Непараметрическая регрессия: ядерное сглаживание

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

(Различия между версиями)

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

Текущая версия

Ядерное сглаживание - один из простейших видов непараметрической регрессии.

Содержание

1 Постановка задачи
2 Принцип
3 Описание метода
4 Литература
5 См. также

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

Решается задача восстановления регрессии. Задано пространство объектов $X$ и множество возможных

ответов $Y=R$ . Существует неизвестная целевая зависимость $y^*: X \rightarrow Y$ , значения которой известны только на объектах обучающей выборки $X^m={(x_i, y_i)}_{i=1}^m$ . Требуется построить алгоритм $a: X \rightarrow Y$ , аппроксимирующий целевую зависимость $y^*$ .

Принцип

Принцип, используйщий идейно простой подход к представлению последовательности весов $\{ W_{mi}(x) \}_{i=1}^m$ состоит в описании формы весовой функции $W_{mi}(x)$ посредством функции плотности со скалярным параметром, который регулирует размер и форму весов около х. Эту функцию формы принято называть ядром $K$ .

Полученные таким образом веса далее используются для представления величины $a(x)$ в виде взвешенной суммы значений $y_i$ обучающей выборки.

Описание метода

Определение ядра

Ядро — это непрерывная ограниченная симметричная вещественная функция $K$ с единичным интегралом

$\int K(u)du=1$

Последовательность весов

Последовательность весов для ядерных оценок (для одномерного $x$ ) определяется как :: $W_{mi}(x)=\frac{K_{h_m}(x-X_i)}{\hat{f}_{h_m}(x)}$ , где

$\hat{f}_{h_m}(x)=\frac1m \sum_{i=1}^m K_{h_m}(x-X_i)$ ,

$K_{h_m}(u)=\frac{1}{h_m} K$\frac{u}{h_m}$$

представляет собой ядро с параметром $h_m$ . Этот параметр принято называть шириной окна. Подчеркнув зависимость $h\ =\ h_m$ от объема выборки $m$ , условимся сокращенно обозначать последовательность весов $W_{mi}(x)$ .

Функция ядра

Функция $\hat{f}_{h_m}(x)$ является ядерной оценкой плотности Розенблата — Парзена (Rosenblatt, 1956; Parzen, 1962) для (маргинальной) плотности переменной $x$ . Данный вид ядерных весов $W_{mi}(x)$ был предложен в работах (Nadaraya, 1964) и (Watson, 1964). Как следствие, оценка ожидаемой величины восстанавливаемой зависимости $E(y\|x)$ :

$\hat{m}_h(x)=\frac{\frac1m\textstyle\sum\limits_{i=1}^m K_{h_m}(x-X_i)Y_i}{\frac1m\textstyle\sum\limits_{i=1}^m K_{h_m}(x-X_i)}$

часто называют оценкой Надарая—Ватсона. Ширина окна определяет, насколько быстро убывают веса $W_{mi}(x)$ по мере удаления объектов $x_i$ от $x$ . Характер убывания определяется видом ядра $K$ . Нормализация весов $\hat{f}_{h_m}(x)$ гарантирует, что сумма весов равна единице.

Замечание. При ряде условий имеет место сходимость по вероятности данной оценки к $E(y|x)$ .

Пример функции ядра

Примеры различных функций ядра.

На практике используется несколько видов ядерных функций. Чаще всего используется квартическая ядерная функция

$K(u)=(15/16)(1-u^2)^2I(\| u \| \le 1)$ .

Также используется ядро Епанечникова, обладающее некоторыми свойствами оптимальности [Хардле В п4.5]; это функция параболического типа (Epanechnikov, 1969; Bartlett, 1963):

$K(u)=0.75(1-u^2)I(\| u \| \le 1)$ .

Другими примерами являются ядро Гаусса,

$K(u)=(2\pi)^{-1/2} \exp(-u^2/2)$ ,

треугольное ядро

$K(u)=(1-\|u\|)I(\| u \| \le 1)$ ,

и прямоугольное ядро

$K(u)=(1/2)I(\| u \| \le 1)$ .

Замечание. Точность восстанавливаемой зависимости мало зависит от выбора ядра. Ядро определяет степень гладкости функции $a(x)$ .

Зависимость от ширины окна

Выбор окна решающим образом влияет на точность восстанавливаемой зависимости. При чересчур малых значениях $h$ кривая $a(x)$ стремится пройти через каждую точку выборки, остро реагируя на шумы и претерпевая резкие скачки, поскольку в этом случае оценка опирается только на небольшое число наблюдений из узкой окрестности точки $x$ . Наоборот, если ширина окна велика, функция чрезмерно сглаживается и в пределе при $h \rightarrow \infty$ вырождается в константу -- усреднённое значение величин $y_i$ . В этом случае сглаженная функция не даёт возможности определить характерные особенности искомой зависимости $y^*(x)$ .

Литература

Хардле В. Прикладная непараметрическая регрессия. — 1989.
Воронцов К.В. Лекции по алгоритмам восстановления регрессии. — 2007.
Лагутин М.Б. Наглядная математическая статистика. — 2009.

См. также

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

Студент: Участник:Tolstikhin

Преподаватель: Участник:Vokov

Срок: 31 декабря 2009

В настоящее время задание завершено и проверено. Данная страница может свободно правиться другими участниками проекта MachineLearning.ru.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9D%D0%B5%D0%BF%D0%B0%D1%80%D0%B0%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F:_%D1%8F%D0%B4%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D1%81%D0%B3%D0%BB%D0%B0%D0%B6%D0%B8%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5»

Категория: Непараметрическая регрессия

@@ Строка 1: / Строка 1: @@
-{{UnderConstruction|[[Участник:SL|SL]] 01:27, 12 января 2009 (MSK)}}
 '''Ядерное сглаживание''' - один из простейших видов [[Непараметрическая регрессия|непараметрической регрессии]].
+== Постановка задачи ==
+:Решается задача восстановления регрессии. Задано пространство объектов <tex>X</tex> и множество возможных
+ответов <tex>Y=R</tex>. Существует неизвестная целевая зависимость <tex> y^*: X \rightarrow Y</tex>,
+значения которой известны только на объектах обучающей выборки <tex> X^m={(x_i, y_i)}_{i=1}^m</tex>.
+Требуется построить алгоритм <tex>a: X \rightarrow Y </tex>, аппроксимирующий целевую зависимость <tex>y^*</tex>.
 == Принцип ==
-Используйщий идейно простой подход к представлению последовательности весов <tex>\{ W_{ni}(x) \}_{i=1}^n</tex> состоит в описании формы весовой функции <tex>W_{ni}(x)</tex> посредством функции плотности со скалярным параметром, который регулирует размер и форму весов около х. Эту функцию формы  принято называть ''ядром'' <tex>K</tex>.
+Принцип, используйщий идейно простой подход к представлению последовательности весов <tex>\{ W_{mi}(x) \}_{i=1}^m</tex> состоит в описании формы весовой
+функции <tex>W_{mi}(x)</tex> посредством функции плотности со скалярным параметром, который регулирует размер и форму весов около х.
+Эту функцию формы  принято называть ''ядром'' <tex>K</tex>.
+Полученные таким образом веса далее используются для представления величины <tex>a(x)</tex> в виде взвешенной суммы значений <tex> y_i</tex> обучающей выборки.
-== Последовательность весов ==
+== Описание метода ==
 === Определение ядра ===
 '''Ядро''' — это непрерывная ограниченная симметричная вещественная функция <tex>K</tex> с единичным интегралом
 ::<tex>\int K(u)du=1</tex>
-Последовательность весов для ядерных оценок (для одномерного
+=== Последовательность весов ===
-<tex>x</tex>) определяется как
+Последовательность весов для ядерных оценок (для одномерного <tex>x</tex>) определяется как ::<tex>W_{mi}(x)=\frac{K_{h_m}(x-X_i)}{\hat{f}_{h_m}(x)}</tex>,
-::<tex>W_{ni}(x)=\frac{K_{h_n}(x\;-\;X_i)}{\hat{f}_{h_n}(x)}</tex>,
 где
-::<tex>\hat{f}_{h_n}(x)=\frac{\sum_{i=1}^n K_{h_n}(x\;-\;X_i)}{n}</tex>,
+::<tex>\hat{f}_{h_m}(x)=\frac1m \sum_{i=1}^m K_{h_m}(x-X_i)</tex>,
 a
-::<tex>K_{h_n}(u)=\frac{K\(\frac{u}{h_n}\)}{h_n}</tex>
+::<tex>K_{h_m}(u)=\frac{1}{h_m} K\(\frac{u}{h_m}\)</tex>
-представляет собой ядро с параметром масштаба <tex>h_n</tex>. Подчеркнув
+представляет собой ядро с параметром <tex>h_m</tex>. Этот параметр принято называть шириной окна. Подчеркнув зависимость <tex>h\ =\ h_m</tex> от объема выборки <tex>m</tex>, условимся сокращенно обозначать последовательность весов <tex>W_{mi}(x)</tex>.
-зависимость <tex>h\ =\ h_n</tex> от объема выборки <tex>n</tex>, условимся сокращен-
-но обозначать последовательность весов <tex>W_{ni}(x)</tex>.
 === Функция ядра ===
-Функция <tex>\hat{f}_{h_n}(x)</tex> является ''ядерной оценкой плотности Розенблата — Парзена'' (Rosenblatt, 1956; Parzen, 1962) для (маргинальной) плотности переменной <tex>x</tex>. Данный вид ядерных весов <tex>W_{ni}(x)</tex> был предложен в работах (Nadaraya, 1964) и (Watson, 1964), и, как следствие,
+Функция <tex>\hat{f}_{h_m}(x)</tex> является ''ядерной оценкой плотности Розенблата — Парзена'' (Rosenblatt, 1956; Parzen, 1962) для (маргинальной) плотности
-::<tex>\hat{m}_h(x)=\frac{n^{-1}\sum_{i=1}^n K_{h_n}(x\;-\;X_i)Y_i}{n^{-1}\sum_{i=1}^n K_{h_n}(x\;-\;X_i)}</tex>
+переменной <tex>x</tex>. Данный вид ядерных весов <tex>W_{mi}(x)</tex> был предложен в работах (Nadaraya, 1964) и (Watson, 1964). Как следствие, оценка
-часто называют оценкой ''Надарая — Ватсона''. ''форма'' ядерных весов определяется ядром <tex>K</tex> в то время как ''размер'' весов параметризируется посредством переменной <tex>h</tex>, называемой ''шириной окна''. Нормализация весов <tex>\hat{f}_{h_n}(x)</tex> позволяет адаптироваться к локальной интенсивности переменной <tex>x</tex> и, кроме того, гарантирует, что сумма весов равна еденице. Вообще говоря, можно брать различные ядерные функции, нр как практика, так и теория ограничивают выбор. Так, например, ядерные функции, принимающие очень малые значения, могут приводить к машинному нулю компьютера, поэтому разумно рассматривать такие ядерные функции, которые равны нулю вне некоторого фиксированного интервала.
+ожидаемой величины восстанавливаемой зависимости <tex>E(y\|x)</tex>:
+::<tex>\hat{m}_h(x)=\frac{\frac1m\textstyle\sum\limits_{i=1}^m K_{h_m}(x-X_i)Y_i}{\frac1m\textstyle\sum\limits_{i=1}^m K_{h_m}(x-X_i)}</tex>
+часто называют оценкой ''Надарая—Ватсона''.
+Ширина окна определяет, насколько быстро убывают веса <tex>W_{mi}(x)</tex> по мере удаления объектов <tex>x_i</tex> от <tex>x</tex>.
+Характер убывания определяется видом ядра <tex>K</tex>.
+Нормализация весов <tex>\hat{f}_{h_m}(x)</tex> гарантирует, что сумма весов равна единице.
+'''Замечание'''. При ряде условий имеет место сходимость по вероятности данной оценки к <tex>E(y|x)</tex>.
 === Пример функции ядра ===
-[[Изображение:YepanchikovsKernel.png|thumb|right|260px|Ядро Бпанечникова. Это ядро <tex>K(u)=0.75(1-u^2)I(\| u \| \le 1)</tex> имеет параболическую форму и носитель <tex>[-1,1]</tex>.]]
+[[Изображение:CoreFunc.png|thumb|right|400px|Примеры различных функций ядра.]]
-Обычно используется ядерная функция, обладающая некоторыми свойствами оптимальности [Хардле В п4.5]; это функция
+На практике используется несколько видов ядерных функций.
+Чаще всего используется квартическая ядерная функция
+::<tex>K(u)=(15/16)(1-u^2)^2I(\| u \| \le 1)</tex>.
+Также используется ядро Епанечникова, обладающее некоторыми свойствами оптимальности [Хардле В п4.5]; это функция
 параболического типа (Epanechnikov, 1969; Bartlett, 1963):
 ::<tex>K(u)=0.75(1-u^2)I(\| u \| \le 1)</tex>.
-'''Замечание.''' Ядро не дифференцируемо при <tex>u = \pm 1</tex>. Ядерная оценка не определена для значения ширины окна с <tex>\hat{f}_{h_n}(x)=0</tex>. Если такой случай <tex>0/0</tex> возникает, то <tex>\hat{m}_h(x)</tex> определяется как <tex>0</tex>.
-=== Зависимость от ширины окна ===
-Допустим, что ядерная оценка вычисляется только в точках наблюдений <tex>\{ X_i\}_{i=1}^n</tex>. Тогда при <tex>h\rightarrow0</tex>,
-::<tex>\hat{m}_h(x)\rightarrow\frac{K(0)Y_i}{K(0)}=Y_i</tex>;
-следовательно, малая ширина окна воспроизводит данные. Исследуем теперь, что происходит при <tex>h\rightarrow\infty</tex>. Допустим, что <tex>K</tex> имеет носитель <tex>[-1,1]</tex>, как на рис. Тогда <tex>K(x\;-\;X_i/h)\rightarrow K(0)</tex> и, следовательно,
-::<tex>\hat{m}_h(x)=\frac{n^{-1}\sum_{i=1}^n K(0)Y_i}{n^{-1}\sum_{i=1}^n K(0)}\;=\;n^{-1}\sum_{i=1}^n Y_i</tex>
-Слишком большое значение ширины окна приводит таким образом к чрезмерному сглаживанию кривой — среднему арифметическому значений переменной отклика.
+Другими примерами являются ядро Гаусса,
+::<tex>K(u)=(2\pi)^{-1/2} \exp(-u^2/2)</tex>,
+треугольное ядро
+::<tex>K(u)=(1-\|u\|)I(\| u \| \le 1)</tex>,
+и прямоугольное ядро
+::<tex>K(u)=(1/2)I(\| u \| \le 1)</tex>.
+'''Замечание'''. Точность восстанавливаемой зависимости мало зависит от выбора ядра.
+Ядро определяет степень гладкости функции <tex>a(x)</tex>.
+=== Зависимость от ширины окна ===
+Выбор окна решающим образом влияет на точность восстанавливаемой зависимости.
+При чересчур малых значениях <tex>h</tex> кривая <tex>a(x)</tex> стремится пройти через каждую точку выборки, остро реагируя на шумы и претерпевая резкие
+скачки, поскольку в этом случае оценка опирается только на небольшое число наблюдений из узкой окрестности точки <tex>x</tex>.
+Наоборот, если ширина окна велика, функция чрезмерно сглаживается и в пределе при <tex> h \rightarrow \infty</tex> вырождается в константу -- усреднённое
+значение величин <tex> y_i</tex>. В этом случае сглаженная функция не даёт возможности определить характерные особенности искомой зависимости <tex> y^*(x)</tex>.
 ==Литература==
@@ Строка 45: / Строка 73: @@
 |ссылка       = http://optimization.nlprog.ru/read/ru/8776859F6322A5AF21D45220A9B5B57E110C2E84/index.htm
 }}
+# {{книга
+|автор        = Воронцов К.В.
+|заглавие  = Лекции по алгоритмам восстановления регрессии
+|год          = 2007
+|ссылка       = http://www.ccas.ru/voron/download/Regression.pdf
+}}
+# {{книга
+|автор        = Лагутин М.Б.
+|заглавие  = Наглядная математическая статистика
+|год          = 2009
+|ссылка       =
+}}
 ==См. также==
-* [[Ядерное сглаживание]]
+* [[Алгоритм LOWESS]]
+* [[Вариация и смещение]]
 * [[Регрессионный анализ]]
-[[Категория:Регрессионный анализ]]
+[[Категория:Непараметрическая регрессия]]
+{{ЗаданиеВыполнено|Tolstikhin|Vokov|31 декабря 2009}}