Метки: Визуальный редактор apiedit |
Метки: Визуальный редактор apiedit |
||
(не показано 11 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
− | {{викифицировать}} |
||
− | |||
== Идея aka Краткое содержание == |
== Идея aka Краткое содержание == |
||
Проблема: нужен непараметрический метод для оценки плотности. |
Проблема: нужен непараметрический метод для оценки плотности. |
||
Строка 6: | Строка 4: | ||
Решение: метод будет основан на локальной оценке плотности в окрестности интересующей точки по известной выборке. Локальная оценка опирается на само определение плотности распределения: <math> p(x) = \lim_{h \to 0} \frac{1}{2h}P[x - h, x + h]</math>, где <math>P[a, b]</math> — вероятностная мера отрезка <math>[a, b]</math>. |
Решение: метод будет основан на локальной оценке плотности в окрестности интересующей точки по известной выборке. Локальная оценка опирается на само определение плотности распределения: <math> p(x) = \lim_{h \to 0} \frac{1}{2h}P[x - h, x + h]</math>, где <math>P[a, b]</math> — вероятностная мера отрезка <math>[a, b]</math>. |
||
− | Так и родился на свет один из непараметрических способов оценки плотности распределения — ядерное сглаживание (KDE или Kernel Density Estimation). В отличие от метода гистограмм блоки (окна), по которым оценивается распределение, не фиксированы, а центрируются по точке-представителю. |
+ | Так и родился на свет один из непараметрических способов оценки плотности распределения — ядерное сглаживание (KDE или Kernel Density Estimation). В отличие от метода гистограмм, блоки (окна), по которым оценивается распределение, не фиксированы, а центрируются по точке-представителю. |
Общая формула KDE (для одномерного и многомерного случая) представлена ниже. |
Общая формула KDE (для одномерного и многомерного случая) представлена ниже. |
||
− | Два важных параметра метода: ядро и ширина окна. Выбор ядра в основном влияет на гладкость итогового распределения, но на точность аппроксимации намного большее влияние оказывает второй параметр, поэтому подбор ширины окна является важной и не всегда тривиальной задачей (прибегают к кросс-валидации, различным эвристикам или динамическому выбору ширины окна: см далее), но основное правило приблизительно таково: чем плотнее выборочное распределение, тем уже должно быть окно. |
+ | Два важных параметра метода: [[Ядра (Kernels)|ядро]] и ширина окна. Выбор ядра в основном влияет на гладкость итогового распределения, но на точность аппроксимации намного большее влияние оказывает второй параметр, поэтому подбор ширины окна является важной и не всегда тривиальной задачей (прибегают к [[Кросс-валидация (Cross-validation)|кросс-валидации]], различным эвристикам или динамическому выбору ширины окна: см далее), но основное правило приблизительно таково: чем плотнее выборочное распределение, тем уже должно быть окно. |
Итак... |
Итак... |
||
Строка 21: | Строка 19: | ||
<math>C</math> — количество классов. |
<math>C</math> — количество классов. |
||
− | <math>\mathbb{X}=\{(x_i, y_i)\}_{i=1}^{N}</math> — выборка, <math>x_i \in \mathbb{R}^D</math>, |
+ | <math>\mathbb{X}=\{(x_i, y_i)\}_{i=1}^{N}</math> — выборка, <math>x_i \in \mathbb{R}^D</math>, <math>y_i \in \{1, \dots, C\}</math>. <math>x \in \mathbb{R}^D</math>. |
<math>h</math> — ширина окна (bandwidth), <math>h \geq 0</math>. |
<math>h</math> — ширина окна (bandwidth), <math>h \geq 0</math>. |
||
Строка 52: | Строка 50: | ||
* Косинусное ядро: <math>K(u)=\tfrac{\pi}{4}\cos(\tfrac{\pi\cdot u}{2})\cdot\mathbb{I}[|u| \leq 1]</math> |
* Косинусное ядро: <math>K(u)=\tfrac{\pi}{4}\cos(\tfrac{\pi\cdot u}{2})\cdot\mathbb{I}[|u| \leq 1]</math> |
||
* Экспоненциальное ядро: <math>K(u)=\tfrac{1}{2}\cdot\exp(-|u|)</math> |
* Экспоненциальное ядро: <math>K(u)=\tfrac{1}{2}\cdot\exp(-|u|)</math> |
||
− | * Квартическое ядро: <math>K(u)=\tfrac{15}{16}\cdot |
+ | * Квартическое ядро: <math>K(u)=\tfrac{15}{16}\cdot(1 - u^2)^2\cdot\mathbb{I}[|u| \leq 1]</math> |
==== <b>Состоятельность оценки <math>\hat{p}(x)</math></b> ==== |
==== <b>Состоятельность оценки <math>\hat{p}(x)</math></b> ==== |
||
Строка 68: | Строка 66: | ||
==== <b>Виды ядер</b> ==== |
==== <b>Виды ядер</b> ==== |
||
* Гауссово ядро: <math>K(u)=\tfrac{1}{(2\cdot\pi)^{\tfrac{D}{2}}}\cdot\exp(\tfrac{-u^T\cdot u}{2})</math> |
* Гауссово ядро: <math>K(u)=\tfrac{1}{(2\cdot\pi)^{\tfrac{D}{2}}}\cdot\exp(\tfrac{-u^T\cdot u}{2})</math> |
||
− | * Ядро Епанечникова: <math>K(u) \ |
+ | * Ядро Епанечникова: <math>K(u)=\tfrac{(D+2)!!}{2^{\left \lceil \tfrac{D+2}{2} \right \rceil}\cdot\pi^{\left \lfloor \tfrac{D}{2} \right \rfloor}}\cdot\max\{1 - u^T\cdot u, 0\}</math> |
* Произведение одномерных ядер: <math>K(\tfrac{x - x_i}{h})=\prod_{d=1}^{D} K_d(\tfrac{x^d - x_i^d}{h}), x=(x^1, \dots, x^D), x_i=(x_i^1, \dots, x_i^D)</math> |
* Произведение одномерных ядер: <math>K(\tfrac{x - x_i}{h})=\prod_{d=1}^{D} K_d(\tfrac{x^d - x_i^d}{h}), x=(x^1, \dots, x^D), x_i=(x_i^1, \dots, x_i^D)</math> |
||
− | ===== <b>Зависящие от метрики <math>\rho(\cdot, \cdot)</math> ядра</b> ===== |
+ | ===== <b>Зависящие от [[метрики]] <math>\rho(\cdot, \cdot)</math> ядра</b> ===== |
+ | <b>Примечание:</b> в случае метрики, отличной от евклидовой, коэффициенты перед ядрами могут быть другими. |
||
+ | |||
<math>\hat{p}(x)=\tfrac{1}{N\cdot h^D}\cdot\sum_{i=1}^{N}K(\tfrac{\rho(x, x_i)}{h})</math> |
<math>\hat{p}(x)=\tfrac{1}{N\cdot h^D}\cdot\sum_{i=1}^{N}K(\tfrac{\rho(x, x_i)}{h})</math> |
||
* Гауссово ядро: <math>K(\tfrac{\rho(x, x_i)}{h})=\tfrac{1}{(2\cdot\pi)^{\tfrac{D}{2}}}\cdot\exp(\tfrac{-\rho^2(x, x_i)}{2\cdot h^2})</math> |
* Гауссово ядро: <math>K(\tfrac{\rho(x, x_i)}{h})=\tfrac{1}{(2\cdot\pi)^{\tfrac{D}{2}}}\cdot\exp(\tfrac{-\rho^2(x, x_i)}{2\cdot h^2})</math> |
||
− | * Ядро Епанечникова: <math>K(\tfrac{\rho(x, x_i)}{h}) \ |
+ | * Ядро Епанечникова: <math>K(\tfrac{\rho(x, x_i)}{h})=\tfrac{(D+2)!!}{2^{\left \lceil \tfrac{D+2}{2} \right \rceil}\cdot\pi^{\left \lfloor \tfrac{D}{2} \right \rfloor}}\cdot\max\{1 - \tfrac{\rho^2(x, x_i)}{h^2}, 0\}</math> |
− | === <b>Выбор ширины окна ( |
+ | === <b>Выбор ширины окна (bandwidth)</b> === |
При <math>h \to 0</math> плотность концентрируется вблизи точек выборки, <math>\hat{p}(x)</math> претерпевает резкие скачки. При <math>h \to \infty</math> более гладкая плотность, происходит вырождение в константу. При построении KDE ширина окна <math>h</math> важнее, чем функция ядра <math>K(\cdot)</math>, так как тип ядра влияет на гладкость, а не на точность аппроксимации. |
При <math>h \to 0</math> плотность концентрируется вблизи точек выборки, <math>\hat{p}(x)</math> претерпевает резкие скачки. При <math>h \to \infty</math> более гладкая плотность, происходит вырождение в константу. При построении KDE ширина окна <math>h</math> важнее, чем функция ядра <math>K(\cdot)</math>, так как тип ядра влияет на гладкость, а не на точность аппроксимации. |
||
<b>Стратегия выбора</b>: чем более плотное распределение объектов выборки, тем меньше должно быть <math>h</math> |
<b>Стратегия выбора</b>: чем более плотное распределение объектов выборки, тем меньше должно быть <math>h</math> |
||
* <b>Постоянное значение h</b>, примеры стратегий: |
* <b>Постоянное значение h</b>, примеры стратегий: |
||
− | ** <math>h=\tfrac{1}{N}\cdot\sum_{i=1}^{N}d_{iK}, d_{iK}</math> — расстояние от <math>x_i</math> до <math>K</math>-го ближайшего соседа (<math>K</math> можно вычислять по скользящему контролю). |
+ | ** <math>h=\tfrac{1}{N}\cdot\sum_{i=1}^{N}d_{iK}, d_{iK}</math> — расстояние от <math>x_i</math> до <math>K</math>-го ближайшего соседа (<math>K</math> можно вычислять по [[Кросс-валидация (Cross-validation)|скользящему контролю]]). |
− | ** <math>h</math> вычисляется по скользящему контролю (Leave-one-out, например). |
+ | ** <math>h</math> вычисляется по скользящему контролю (Leave-one-out, например), можно найти по максимальному правдоподобию на отложенной выборке (поиск максимального значения правдоподобия производится по заданному списку значений <math>h</math>). |
* <b>Переменное значение <math>h(x)</math></b>, например: <math>h(x)</math> — расстояние от <math>x</math> до <math>K</math>-го ближайшего соседа (<math>K</math> можно найти по скользящему контролю). |
* <b>Переменное значение <math>h(x)</math></b>, например: <math>h(x)</math> — расстояние от <math>x</math> до <math>K</math>-го ближайшего соседа (<math>K</math> можно найти по скользящему контролю). |
||
=== <b>Метод Парзеновского окна</b> === |
=== <b>Метод Парзеновского окна</b> === |
||
+ | <b>Метод Парзеновского окна</b> — метод байесовской [[Задача классификации|классификации]], основанный на непараметрическом восстановлении плотности по имеющейся выборке. |
||
Оценка условной плотности <math>p(x|y)</math> через KDE (<math>y \in \{1, \dots, C\}, D \geq 1</math>): |
Оценка условной плотности <math>p(x|y)</math> через KDE (<math>y \in \{1, \dots, C\}, D \geq 1</math>): |
||
Строка 96: | Строка 97: | ||
<math>\hat{y}(x)=\arg\max_{y}\tfrac{1}{N_y\cdot h^D}\cdot\sum_{i:y_i=y}K(\tfrac{\rho(x, x_i)}{h})\cdot\tfrac{N_y}{N}=\arg\max_{y}\sum_{i:y_i=y}K(\tfrac{\rho(x, x_i)}{h})</math> |
<math>\hat{y}(x)=\arg\max_{y}\tfrac{1}{N_y\cdot h^D}\cdot\sum_{i:y_i=y}K(\tfrac{\rho(x, x_i)}{h})\cdot\tfrac{N_y}{N}=\arg\max_{y}\sum_{i:y_i=y}K(\tfrac{\rho(x, x_i)}{h})</math> |
||
+ | ==== <b>Преобразование метода Парзеновского окна в [[Метод ближайших соседей (kNN)|метод ближайших соседей]]</b> ==== |
||
Обозначим <math>h(x)=\rho(x, x_{i(K)}), i(K)</math> — индекс <math>K</math>-го ближайшего соседа для <math>x</math>, <math>K(u)=\mathbb{I}[|u| \leq 1]</math>. Тогда: |
Обозначим <math>h(x)=\rho(x, x_{i(K)}), i(K)</math> — индекс <math>K</math>-го ближайшего соседа для <math>x</math>, <math>K(u)=\mathbb{I}[|u| \leq 1]</math>. Тогда: |
||
<math>\hat{y}(x)=\arg\max_{y}\sum_{j:y_j=y}\mathbb{I}[\rho(x, x_j) \leq \rho(x, x_{i(K)})]=\arg\max_{y}\sum_{j:\rho(x, x_j) \leq \rho(x, x_{i(K)})}\mathbb{I}[y_j=y]=</math><math>=\arg\max_{y}\sum_{j=1}^{K}\mathbb{I}[y_{i(j)}=y]</math> |
<math>\hat{y}(x)=\arg\max_{y}\sum_{j:y_j=y}\mathbb{I}[\rho(x, x_j) \leq \rho(x, x_{i(K)})]=\arg\max_{y}\sum_{j:\rho(x, x_j) \leq \rho(x, x_{i(K)})}\mathbb{I}[y_j=y]=</math><math>=\arg\max_{y}\sum_{j=1}^{K}\mathbb{I}[y_{i(j)}=y]</math> |
||
− | |||
− | ==== <b>Касательно регрессии</b> ==== |
||
− | {{Сомнения|Что непонятно? = (Этого не было в лекции, прошу особо внимательно проверить)}}<math>y \in \mathbb{R}, D \geq 1</math>. |
||
− | |||
− | * <b>KNN регрессия</b>: <math>\hat{y}(x)=\tfrac{\sum_{j=1}^{K}w_{i(j)}\cdot y_{i(j)}}{\sum_{j=1}^{K}w_{i(j)}}, w_{i(j)}</math> — веса для KNN регрессии |
||
− | * <b>Формула ядерного сглаживания Надарая-Ватсона</b>: <math>\hat{y}(x)=\tfrac{\sum_{i=1}^{N}y_i\cdot K(\tfrac{\rho(x, x_i)}{h})}{\sum_{i=1}^{N}K(\tfrac{\rho(x, x_i)}{h})}</math> |
||
− | |||
− | Следующими заменами регрессия Надарая-Ватсона будет преобразована в KNN регрессию: |
||
− | |||
− | <math>K(u)=\mathbb{I}[|u| \leq 1]\cdot K_1(u), K_1(|u|)</math> — монотонно невозрастающая функция, <math>h(x)=\rho(x, x_{i(K)})</math>, в случае <math>K_1(|u|)\equiv1</math> ответом для <math>x</math> будет среднее арифметическое по <math>y_{i(j)}, j=1,\dots, K</math>. |
||
== Ссылки == |
== Ссылки == |
Текущая версия от 23:52, 13 января 2017
Идея aka Краткое содержание[]
Проблема: нужен непараметрический метод для оценки плотности.
Решение: метод будет основан на локальной оценке плотности в окрестности интересующей точки по известной выборке. Локальная оценка опирается на само определение плотности распределения: , где — вероятностная мера отрезка .
Так и родился на свет один из непараметрических способов оценки плотности распределения — ядерное сглаживание (KDE или Kernel Density Estimation). В отличие от метода гистограмм, блоки (окна), по которым оценивается распределение, не фиксированы, а центрируются по точке-представителю.
Общая формула KDE (для одномерного и многомерного случая) представлена ниже.
Два важных параметра метода: ядро и ширина окна. Выбор ядра в основном влияет на гладкость итогового распределения, но на точность аппроксимации намного большее влияние оказывает второй параметр, поэтому подбор ширины окна является важной и не всегда тривиальной задачей (прибегают к кросс-валидации, различным эвристикам или динамическому выбору ширины окна: см далее), но основное правило приблизительно таково: чем плотнее выборочное распределение, тем уже должно быть окно.
Итак...
Условные обозначения[]
— количество объектов в выборке.
— размер признакового пространства, .
— количество классов.
— выборка, , . .
— ширина окна (bandwidth), .
— оценка плотности распределения .
условие — равняется 1, если условие выполнено, иначе равняется 0.
— оценка зависимости .
Гистограммы[]
Недостаток: необходимо фиксировать отрезки, на которые разбивается интервал. Проблема: выбор количества корзинок и ширины корзинок.
Ядерное сглаживание[]
Идея: каждый выборки будет центром блока.
Блок может иметь следующий вид: .
Одномерный случай []
Kernel Density Estimation (KDE, локальная непараметрическая оценка Парзена-Розенблатта) — , — ядро, чётная и нормированная функция: . Следствие: обладает той же степенью гладкости, что и ядро .
Виды ядер[]
- Прямоугольное ядро (tophat kernel): соответствует эмпирической оценке плотности (доля точек выборки, лежащих внутри отрезка ). Одно из простейших ядер, но не учитывает расстояние между объектами, а также итоговое распределение не будет являться непрерывным.
- Гауссово ядро:
- Ядро Епанечникова:
- Треугольное ядро:
- Косинусное ядро:
- Экспоненциальное ядро:
- Квартическое ядро:
Состоятельность оценки []
Оценка состоятельна, если .
Достаточные условия состоятельности оценки :
,
, , ,
Многомерный случай []
Виды ядер[]
- Гауссово ядро:
- Ядро Епанечникова:
- Произведение одномерных ядер:
Зависящие от метрики ядра[]
Примечание: в случае метрики, отличной от евклидовой, коэффициенты перед ядрами могут быть другими.
- Гауссово ядро:
- Ядро Епанечникова:
Выбор ширины окна (bandwidth)[]
При плотность концентрируется вблизи точек выборки, претерпевает резкие скачки. При более гладкая плотность, происходит вырождение в константу. При построении KDE ширина окна важнее, чем функция ядра , так как тип ядра влияет на гладкость, а не на точность аппроксимации.
Стратегия выбора: чем более плотное распределение объектов выборки, тем меньше должно быть
- Постоянное значение h, примеры стратегий:
- — расстояние от до -го ближайшего соседа ( можно вычислять по скользящему контролю).
- вычисляется по скользящему контролю (Leave-one-out, например), можно найти по максимальному правдоподобию на отложенной выборке (поиск максимального значения правдоподобия производится по заданному списку значений ).
- Переменное значение , например: — расстояние от до -го ближайшего соседа ( можно найти по скользящему контролю).
Метод Парзеновского окна[]
Метод Парзеновского окна — метод байесовской классификации, основанный на непараметрическом восстановлении плотности по имеющейся выборке.
Оценка условной плотности через KDE ():
— число объектов класса — метрика.
Байесовское решающее правило даёт следующий классификатор:
Оценим с помощью KDE, как :
Преобразование метода Парзеновского окна в метод ближайших соседей[]
Обозначим — индекс -го ближайшего соседа для , . Тогда: