Машинное обучение вики
Регистрация
NikEYN (обсуждение | вклад)
Метки: Визуальный редактор apiedit
SSerov (обсуждение | вклад)
Метки: Визуальный редактор 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>.
   
Так и родился на свет один из непараметрических способов оценки плотности распределения &mdash; ядерное сглаживание (KDE или Kernel Density Estimation). В отличие от метода гистограмм блоки (окна), по которым оценивается распределение, не фиксированы, а центрируются по точке-представителю.
+
Так и родился на свет один из непараметрических способов оценки плотности распределения &mdash; ядерное сглаживание (KDE или Kernel Density Estimation). В отличие от метода гистограмм, блоки (окна), по которым оценивается распределение, не фиксированы, а центрируются по точке-представителю.
   
 
Общая формула KDE (для одномерного и многомерного случая) представлена ниже.
 
Общая формула KDE (для одномерного и многомерного случая) представлена ниже.
   
Два важных параметра метода: ядро и ширина окна. Выбор ядра в основном влияет на гладкость итогового распределения, но на точность аппроксимации намного большее влияние оказывает второй параметр, поэтому подбор ширины окна является важной и не всегда тривиальной задачей (прибегают к кросс-валидации, различным эвристикам или динамическому выбору ширины окна: см далее), но основное правило приблизительно таково: чем плотнее выборочное распределение, тем уже должно быть окно.
+
Два важных параметра метода: [[Ядра (Kernels)|ядро]] и ширина окна. Выбор ядра в основном влияет на гладкость итогового распределения, но на точность аппроксимации намного большее влияние оказывает второй параметр, поэтому подбор ширины окна является важной и не всегда тривиальной задачей (прибегают к [[Кросс-валидация (Cross-validation)|кросс-валидации]], различным эвристикам или динамическому выбору ширины окна: см далее), но основное правило приблизительно таково: чем плотнее выборочное распределение, тем уже должно быть окно.
   
 
Итак...
 
Итак...
Строка 21: Строка 19:
 
<math>C</math> &mdash; количество классов.
 
<math>C</math> &mdash; количество классов.
   
<math>\mathbb{X}=\{(x_i, y_i)\}_{i=1}^{N}</math> &mdash; выборка, <math>x_i \in \mathbb{R}^D</math>, все <math>y_i \in \{1, \dots, C\}</math> или все <math>y_i \in \mathbb{R}</math>. <math>x \in \mathbb{R}^D</math>.
+
<math>\mathbb{X}=\{(x_i, y_i)\}_{i=1}^{N}</math> &mdash; выборка, <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> &mdash; ширина окна (bandwidth), <math>h \geq 0</math>.
 
<math>h</math> &mdash; ширина окна (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\max\{(1 - u^2)^2, 0\}</math>
+
* Квартическое ядро: <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) \propto \max\{1 - u^T\cdot u, 0\}</math>
+
* Ядро Епанечникова: <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}) \propto \max\{1 - \tfrac{\rho^2(x, x_i)}{h^2}, 0\}</math>
+
* Ядро Епанечникова: <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>Выбор ширины окна (brandwidth)</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> &mdash; расстояние от <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> &mdash; расстояние от <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> &mdash; расстояние от <math>x</math> до <math>K</math>-го ближайшего соседа (<math>K</math> можно найти по скользящему контролю).
 
* <b>Переменное значение <math>h(x)</math></b>, например: <math>h(x)</math> &mdash; расстояние от <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> &mdash; индекс <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> &mdash; индекс <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> &mdash; веса для 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> &mdash; монотонно невозрастающая функция, <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.

— оценка зависимости .

Гистограммы[]

Недостаток: необходимо фиксировать отрезки, на которые разбивается интервал. Проблема: выбор количества корзинок и ширины корзинок.

Histogram

Две гистограммы для одной выборки


Ядерное сглаживание[]

Идея: каждый выборки будет центром блока.

Блок может иметь следующий вид: .

Одномерный случай []

Kernel Density Estimation (KDE, локальная непараметрическая оценка Парзена-Розенблатта) — , — ядро, чётная и нормированная функция: . Следствие: обладает той же степенью гладкости, что и ядро .

Виды ядер[]

  • Прямоугольное ядро (tophat kernel): соответствует эмпирической оценке плотности (доля точек выборки, лежащих внутри отрезка ). Одно из простейших ядер, но не учитывает расстояние между объектами, а также итоговое распределение не будет являться непрерывным.
  • Гауссово ядро:
  • Ядро Епанечникова:
  • Треугольное ядро:
  • Косинусное ядро:
  • Экспоненциальное ядро:
  • Квартическое ядро:

Состоятельность оценки []

Оценка состоятельна, если .

Достаточные условия состоятельности оценки :

,

, , ,

Многомерный случай []

Виды ядер[]

  • Гауссово ядро:
  • Ядро Епанечникова:
  • Произведение одномерных ядер:
Зависящие от метрики ядра[]

Примечание: в случае метрики, отличной от евклидовой, коэффициенты перед ядрами могут быть другими.

  • Гауссово ядро:
  • Ядро Епанечникова:

Выбор ширины окна (bandwidth)[]

При плотность концентрируется вблизи точек выборки, претерпевает резкие скачки. При более гладкая плотность, происходит вырождение в константу. При построении KDE ширина окна важнее, чем функция ядра , так как тип ядра влияет на гладкость, а не на точность аппроксимации.

Стратегия выбора: чем более плотное распределение объектов выборки, тем меньше должно быть

  • Постоянное значение h, примеры стратегий:
    • — расстояние от до -го ближайшего соседа ( можно вычислять по скользящему контролю).
    • вычисляется по скользящему контролю (Leave-one-out, например), можно найти по максимальному правдоподобию на отложенной выборке (поиск максимального значения правдоподобия производится по заданному списку значений ).
  • Переменное значение , например: — расстояние от до -го ближайшего соседа ( можно найти по скользящему контролю).

Метод Парзеновского окна[]

Метод Парзеновского окна — метод байесовской классификации, основанный на непараметрическом восстановлении плотности по имеющейся выборке.

Оценка условной плотности через KDE ():

— число объектов класса — метрика.

Байесовское решающее правило даёт следующий классификатор:

Оценим с помощью KDE, как :

Преобразование метода Парзеновского окна в метод ближайших соседей[]

Обозначим — индекс -го ближайшего соседа для , . Тогда:

Ссылки[]