Оценивание плотности распределения
Материал из MachineLearning.
(→Методы локального оценивания) |
|||
(5 промежуточных версий не показаны.) | |||
Строка 8: | Строка 8: | ||
==Непараметрическое восстановление плотности== | ==Непараметрическое восстановление плотности== | ||
- | Будем считать, что общий вид функции распределения неизвестен, известны только некоторые свойства | + | Будем считать, что общий вид функции распределения неизвестен, известны только некоторые свойства — например, функция гладкая, непрерывная. Тогда для оценки плотности применяют непараметрические методы оценивания. |
'''Постановка задачи''' | '''Постановка задачи''' | ||
Строка 16: | Строка 16: | ||
===Гистограммный метод оценивания=== | ===Гистограммный метод оценивания=== | ||
'''Идея''': если <tex>p(x)</tex> - плотность случайного вектора <tex>\xi</tex>, то <tex>P(\Omega) = \int_{\Omega}{p(x)dx} = p(x_0)V(\Omega)</tex>, | '''Идея''': если <tex>p(x)</tex> - плотность случайного вектора <tex>\xi</tex>, то <tex>P(\Omega) = \int_{\Omega}{p(x)dx} = p(x_0)V(\Omega)</tex>, | ||
- | где <tex>x_0\in\Omega</tex>, <tex>V(\Omega)</tex> - мера области <tex>\Omega</tex>. Если <tex>X_N = \{x_1, \cdots , x_N\}</tex> - выборка, <tex>k</tex> | + | где <tex>x_0\in\Omega</tex>, <tex>V(\Omega)</tex> - мера области <tex>\Omega</tex>. Если <tex>X_N = \{x_1, \cdots , x_N\}</tex> - выборка, <tex>k</tex> — число значений выборки в <tex>\Omega</tex>, то |
<tex>P(\Omega)\approx \frac {k}{N}</tex>. | <tex>P(\Omega)\approx \frac {k}{N}</tex>. | ||
Строка 22: | Строка 22: | ||
Поэтому <tex>p(x_0)V(\Omega)\approx \frac {k}{N} \Rightarrow p(x_0)\approx \frac {k}{N\cdot V(\Omega))</tex>. | Поэтому <tex>p(x_0)V(\Omega)\approx \frac {k}{N} \Rightarrow p(x_0)\approx \frac {k}{N\cdot V(\Omega))</tex>. | ||
- | Значит, <tex>p(x) = \frac {k}{N\cdot V(\Omega))</tex> | + | Значит, <tex>p(x) = \frac {k}{N\cdot V(\Omega))</tex> — оценка плотности. |
Построение гистограммы: | Построение гистограммы: | ||
- | + | # найдем ограниченную область <tex>A</tex> пространства <tex>X</tex>(пространства объектов), содержащее все векторы из обучающей выборки <tex>X_l</tex>; | |
- | + | # разобьем <tex>A</tex> на непересекающиеся области <tex>A_1, \cdots, A_p</tex>; | |
- | + | # если <tex>k_i</tex> - количество элементов обучающей выборки <tex>X^l</tex>, принадлежащих области <tex>A_i</tex>, то | |
- | + | ||
- | + | ||
<tex>\tilde p(x)=\frac{k}{N\cdot V(A_i)}</tex>, <tex>x\in A_i</tex>, | <tex>\tilde p(x)=\frac{k}{N\cdot V(A_i)}</tex>, <tex>x\in A_i</tex>, | ||
Строка 37: | Строка 35: | ||
Оценка <tex>\tilde p(x)</tex> будет состоятельной при некотором выборе <tex>A_i</tex>. К сожалению, нет универсального способа выбора областей <tex>Ai</tex> таких, чтобы оценка была состоятельной. | Оценка <tex>\tilde p(x)</tex> будет состоятельной при некотором выборе <tex>A_i</tex>. К сожалению, нет универсального способа выбора областей <tex>Ai</tex> таких, чтобы оценка была состоятельной. | ||
- | |||
===Методы локального оценивания=== | ===Методы локального оценивания=== | ||
'''Идея''': оценить плотность <tex>p(x)</tex> в точке <tex>x_0</tex> с помощью элементов обучающей выборки, попавших в некоторую окрестность <tex>x_0</tex>. | '''Идея''': оценить плотность <tex>p(x)</tex> в точке <tex>x_0</tex> с помощью элементов обучающей выборки, попавших в некоторую окрестность <tex>x_0</tex>. | ||
- | Пусть <tex>X_N = \{x_1, ... , x_N\}</tex> - | + | Пусть <tex>X_N = \{x_1, ... , x_N\}</tex> - последовательность выборок независимых случайных векторов, <tex>\Omega _N</tex> - последовательность областей, содержащих точку <tex>x</tex>, <tex>k_N</tex> - число выборочных значений выборки <tex>X_N</tex>, попавших в область <tex>\Omega _N</tex>. |
'''Теорема.''' Если функция <tex>p(x)</tex> непрерывна в точке <tex>x_0</tex>, все области <tex>\Omega _N</tex> содержат точку <tex>x_0</tex> и удовлетворяют условиям | '''Теорема.''' Если функция <tex>p(x)</tex> непрерывна в точке <tex>x_0</tex>, все области <tex>\Omega _N</tex> содержат точку <tex>x_0</tex> и удовлетворяют условиям | ||
- | + | #<tex>\lim _{N \rightarrow \infty} V(\Omega _N) = 0</tex>; | |
- | + | #<tex>\lim _{N \rightarrow \infty} N\cdot V(\Omega _N) = \infty</tex>, | |
- | + | ||
то функция <tex>\tilde p(x) = \frac {k_N}{N\cdot V(\Omega _N)}</tex>, <tex>x\in \Omega _N</tex> будет несмещенной, асимптотически эффективной и состоятельной оценкой плотности <tex>p(x)</tex> в точке <tex>x_0</tex>. | то функция <tex>\tilde p(x) = \frac {k_N}{N\cdot V(\Omega _N)}</tex>, <tex>x\in \Omega _N</tex> будет несмещенной, асимптотически эффективной и состоятельной оценкой плотности <tex>p(x)</tex> в точке <tex>x_0</tex>. | ||
Строка 54: | Строка 50: | ||
Существуют два основных подхода к выбору областей, содержащих точку <tex>x_0</tex>: | Существуют два основных подхода к выбору областей, содержащих точку <tex>x_0</tex>: | ||
- | + | #[[метод парзеновского окна]]. <tex>\Omega _N</tex> предполагаются регулярными областями, размеры которых удовлетворяют условиям теоремы, исходя из этого определяется число <tex>k_N</tex>. | |
- | + | #[[метод k ближайших соседей]]. Фиксируются не области <tex>\Omega _N</tex>, а число <tex>k_N</tex>, затем для точки <tex>x_0</tex> определяется регулярная область, содержащая <tex>k_N</tex> ближайших к <tex>x_0</tex> точек. | |
- | + | ||
- | + | ||
===Метод оценивания с помощью аппроксимации функции плотности=== | ===Метод оценивания с помощью аппроксимации функции плотности=== | ||
- | '''Идея''': функция <tex>p(x)</tex> аппроксимируется с помощью системы базисных функций <tex>\{\phi _j\}_{j=1}^{\infty}</tex> | + | '''Идея''': функция <tex>p(x)</tex> аппроксимируется с помощью системы базисных функций <tex>\{\phi _j\}_{j=1}^{\infty}</tex> — оценка <tex>\tilde p(x)</tex> ищется в виде |
<tex>\tilde p(x) = \sum _{j = 1}^{\infty} c_j\phi _j(x)</tex>. (1) | <tex>\tilde p(x) = \sum _{j = 1}^{\infty} c_j\phi _j(x)</tex>. (1) | ||
Строка 97: | Строка 91: | ||
<tex>\tilde \Sigma = \frac {1}{l}\sum _{i = 1}^{l}(x_i - \tilde \mu)(x_i - \tilde \mu)^T</tex>. | <tex>\tilde \Sigma = \frac {1}{l}\sum _{i = 1}^{l}(x_i - \tilde \mu)(x_i - \tilde \mu)^T</tex>. | ||
- | |||
===[[Метод моментов]]=== | ===[[Метод моментов]]=== | ||
Строка 121: | Строка 114: | ||
<tex>p(x) = \sum _{j = 1}^{k}\omega _j p_j(x)</tex>, <tex>\sum _{j = 1}^{k}\omega _j = 1</tex>, <tex>\omega _j \ge 0</tex>. | <tex>p(x) = \sum _{j = 1}^{k}\omega _j p_j(x)</tex>, <tex>\sum _{j = 1}^{k}\omega _j = 1</tex>, <tex>\omega _j \ge 0</tex>. | ||
- | где <tex>p_j(x)</tex> | + | где <tex>p_j(x)</tex> — плотность распределения <tex>j</tex>-й компоненты смеси, <tex>\omega _j</tex> - её априорная вероятность. Функции правдоподобия принадлежат параметрическому семейству распределений <tex>\phi (x; \theta)</tex> и отличаются только значениями параметра, <tex>p_j(x) = \phi (x; \theta )</tex>. |
'''Постановка задачи''' | '''Постановка задачи''' | ||
- | Известна выборка <tex>X_m</tex> | + | Известна выборка <tex>X_m</tex> — независимых случайных наблюдений из смеси <tex>p(x)</tex>, известны число <tex>k</tex> и функция <tex>\phi</tex>. Требуется найти оценку параметров <tex>\Theta = (\omega _1, \cdots ,\omega _k, \theta _1, \cdots , \theta _k)</tex>. |
===[[ЕМ-алгоритм, его модификации и обобщения |EM-алгоритм]]=== | ===[[ЕМ-алгоритм, его модификации и обобщения |EM-алгоритм]]=== | ||
'''Идея''': искусственно вводится вектор скрытых переменных <tex>G</tex>, обладающий следующими свойствами: | '''Идея''': искусственно вводится вектор скрытых переменных <tex>G</tex>, обладающий следующими свойствами: | ||
- | + | #он может быть вычислен, если известны значения вектора параметров <tex>\Theta</tex>; | |
- | + | #поиск максимума правдоподобия сильно упрощается, если известны значения скрытых переменных. | |
- | + | ||
EM-алгоритм состоит из итерационного повторения двух шагов. На E-шаге вычисляется ожидаемое значение (expectation) вектора скрытых переменных <tex>G</tex> по текущему приближению вектора параметров <tex>\Theta</tex>. На М-шаге решается задача максимизации правдоподобия (maximization) и находится следующее приближение вектора <tex>\Theta</tex> по текущим значениям векторов <tex>G</tex> и <tex>\Theta</tex>. | EM-алгоритм состоит из итерационного повторения двух шагов. На E-шаге вычисляется ожидаемое значение (expectation) вектора скрытых переменных <tex>G</tex> по текущему приближению вектора параметров <tex>\Theta</tex>. На М-шаге решается задача максимизации правдоподобия (maximization) и находится следующее приближение вектора <tex>\Theta</tex> по текущим значениям векторов <tex>G</tex> и <tex>\Theta</tex>. | ||
Строка 149: | Строка 141: | ||
[[EM-алгоритм с последовательным добавлением компонент]] позволяет решить обе эти проблемы. Идея данного метода заключается в следующем. Имея некоторый набор компонент, можно выделить объекты <tex>x_i</tex>, которые хуже всего описываются смесью - это объекты с наименьшими значениями правдоподобия <tex>p(x_i)</tex>. По этим объектам строится ещё одна компонента. Затем она добавляется в смесь и запускаются EM-итерации, чтобы новая компонента и старые "притёрлись друг к другу". Так продолжается до тех пор, пока все объекты не окажутся покрыты компонентами. | [[EM-алгоритм с последовательным добавлением компонент]] позволяет решить обе эти проблемы. Идея данного метода заключается в следующем. Имея некоторый набор компонент, можно выделить объекты <tex>x_i</tex>, которые хуже всего описываются смесью - это объекты с наименьшими значениями правдоподобия <tex>p(x_i)</tex>. По этим объектам строится ещё одна компонента. Затем она добавляется в смесь и запускаются EM-итерации, чтобы новая компонента и старые "притёрлись друг к другу". Так продолжается до тех пор, пока все объекты не окажутся покрыты компонентами. | ||
- | |||
=Сравнение различных подходов= | =Сравнение различных подходов= | ||
Строка 157: | Строка 148: | ||
=Литература= | =Литература= | ||
+ | http://www.lepskiy.ucoz.com/lect_Lepskiy_Bronevich_pass.pdf | ||
+ | |||
http://lepskiy.ucoz.ru/_2_pass.pdf | http://lepskiy.ucoz.ru/_2_pass.pdf | ||
Строка 162: | Строка 155: | ||
- | + | {{Задание|ihoho|Константин Воронцов|31 декабря 2009}} | |
- | + | [[Категория:Оценивание вероятностных распределений]] | |
- | + | ||
- | + |
Текущая версия
Байесовские алгоритмы классификации основываются на знании априорных вероятностей классов и законов распределения вероятностей признаков в каждом классе. На практике нам известна только обучающая выборка объектов. Будем считать элементы выборки независимыми случайными величинами, имеющими одинаковое распределение. Требуется по выборке оценить плотность этого распределения.
Содержание |
Постановка задачи
Требуется оценить плотность распределения по выборке независимых случайных векторов, распределенных по этому закону .
Методы решения
Существуют три основных подхода к оцениванию плотности распределения: непараметрический, параметрический и восстановление смесей распределений.
Непараметрическое восстановление плотности
Будем считать, что общий вид функции распределения неизвестен, известны только некоторые свойства — например, функция гладкая, непрерывная. Тогда для оценки плотности применяют непараметрические методы оценивания.
Постановка задачи
Построить функцию , которая аппроксимировала бы неизвестную функцию в некотором смысле.
Гистограммный метод оценивания
Идея: если - плотность случайного вектора , то , где , - мера области . Если - выборка, — число значений выборки в , то
.
Поэтому .
Значит, — оценка плотности.
Построение гистограммы:
- найдем ограниченную область пространства (пространства объектов), содержащее все векторы из обучающей выборки ;
- разобьем на непересекающиеся области ;
- если - количество элементов обучающей выборки , принадлежащих области , то
, ,
где - мера области .
Оценка будет состоятельной при некотором выборе . К сожалению, нет универсального способа выбора областей таких, чтобы оценка была состоятельной.
Методы локального оценивания
Идея: оценить плотность в точке с помощью элементов обучающей выборки, попавших в некоторую окрестность .
Пусть - последовательность выборок независимых случайных векторов, - последовательность областей, содержащих точку , - число выборочных значений выборки , попавших в область .
Теорема. Если функция непрерывна в точке , все области содержат точку и удовлетворяют условиям
- ;
- ,
то функция , будет несмещенной, асимптотически эффективной и состоятельной оценкой плотности в точке .
Существуют два основных подхода к выбору областей, содержащих точку :
- метод парзеновского окна. предполагаются регулярными областями, размеры которых удовлетворяют условиям теоремы, исходя из этого определяется число .
- метод k ближайших соседей. Фиксируются не области , а число , затем для точки определяется регулярная область, содержащая ближайших к точек.
Метод оценивания с помощью аппроксимации функции плотности
Идея: функция аппроксимируется с помощью системы базисных функций — оценка ищется в виде
. (1)
Коэффициенты выбираются таким образом, чтобы погрешность аппроксимации была минимальной, т.е.
.
Реально вместо бесконечного ряда (1) рассматривается конечная сумма первых членов.
Как правило, рассматривают ортогональную систему базисных функций, при этом используют многочлены Лежандра, Чебышева, Эрмита, Лагранжа, Лагерра и т.п.
Параметрическое восстановление плотности
Если общий вид функции плотности распределения случайного вектора ξ известен в том смысле, что точный вид функции полностью определяется набором параметров, которые можно оценить по обучающей выборке, то применяют параметрические методы оценивания плотности.
Постановка задачи
Известен общий вид функции плотности распределения случайного вектора , зависящий от вектора параметров . Требуется по обучающей выборке значений вектора получить оценку вектора .
Метод максимального правдоподобия
Метод максимального правдоподобия предложен Р.Фишером в 1912г.
Идея: найти такой вектор параметров , что
.
Пример:
Пусть , а плотность имеет вид многомерного нормального распределения:
Тогда оценки параметров и по методу максимального правдоподобия по выборке имеют следующий вид
;
.
Метод моментов
Идея: если - плотность распределения случайного вектора , то моменты -го порядка равны (считаем, что ):
.
Оценку можно найти по выборке :
Оценку можно найти из системы уравнений:
.
Если зависимоть - непрерывна, то - состоятельная оценка.
Восстановление смесей распределений
Если "форма" классов имеет достаточно сложный вид, не "поддающийся" описанию одним распределением, то применяют методы восстановления смесей распрелений - описывают класс несколькими распределениями.
Предположим, что плотность распределения имеет вид смеси распределений:
, , .
где — плотность распределения -й компоненты смеси, - её априорная вероятность. Функции правдоподобия принадлежат параметрическому семейству распределений и отличаются только значениями параметра, .
Постановка задачи
Известна выборка — независимых случайных наблюдений из смеси , известны число и функция . Требуется найти оценку параметров .
EM-алгоритм
Идея: искусственно вводится вектор скрытых переменных , обладающий следующими свойствами:
- он может быть вычислен, если известны значения вектора параметров ;
- поиск максимума правдоподобия сильно упрощается, если известны значения скрытых переменных.
EM-алгоритм состоит из итерационного повторения двух шагов. На E-шаге вычисляется ожидаемое значение (expectation) вектора скрытых переменных по текущему приближению вектора параметров . На М-шаге решается задача максимизации правдоподобия (maximization) и находится следующее приближение вектора по текущим значениям векторов и .
Итерации останавливаются, когда значения функционала , где
,
или скрытых переменных перестают существенно изменяться. Удобнее контролировать скрытые переменные, так как они имеют смысл вероятностей и принимают значения из отрезка [0, 1].
"Проблемы", возникающие при реализации EM-алгоритма
- Проблема выбора начального приближения. Хотя алгоритм EM сходится при достаточно общих предположениях, скорость сходимости может существенно зависеть от "хорошего" выбора начального приближения. Сходимость ухудшается в тех случаях, когда делается попытка поместить несколько компонент в один фактический сгусток распределения, либо разместить компоненту посередине между сгустками.
- Проблема выбора числа компонент . До сих пор предполагалось, что число компонент известно заранее. На практике это, как правило, не так.
EM-алгоритм с последовательным добавлением компонент позволяет решить обе эти проблемы. Идея данного метода заключается в следующем. Имея некоторый набор компонент, можно выделить объекты , которые хуже всего описываются смесью - это объекты с наименьшими значениями правдоподобия . По этим объектам строится ещё одна компонента. Затем она добавляется в смесь и запускаются EM-итерации, чтобы новая компонента и старые "притёрлись друг к другу". Так продолжается до тех пор, пока все объекты не окажутся покрыты компонентами.
Сравнение различных подходов
Были рассмотрены три подхода к задаче оценивания плотности распределения: непараметрический, параметрический и разделение смесей. Каждый из них применяется при определенных априорных знаниях о плотности распределения. Параметрические методы восстановления используются, если вид функции распределения известен с точностью до набора параметров, которые оцениваются по обучающей выборке. Непараметрические методы уже не требуют знания функции распределения с точностью до параметров, а только некоторых свойств функции, например, непрерывность или гладкость. Если же форма классов имеет достаточно "сложный" вид, не поддающийся описанию одним распределением, то применяют методы разделения смесей, когда предполагается, что внутри класса плотность распределения представляет собой смесь нескольких распределений.
Несмотря на то, что, казалось бы, все подходы имеют разные области применимости и используют разные методы обучения можно выделить и черты сходства между ними. Непараметрические оценки плотности можно рассматривать как предельный частный случай смеси распределений, в которой каждому обучающему объекту соответствует ровно одна компонента с априорной вероятностью и сферической плотностью с центром в точке . С другой стороны, параметрический подход также является крайним случаем смеси - когда берётся только одна компонента. Таким образом, все три подхода отличаются, в первую очередь, количеством аддитивных компонент в модели распределения: . Это приводит к качественным различиям в методах обучения. Требования к форме компонент ослабляются по мере увеличения их числа. Восстановление смеси из произвольного числа компонент k является, по всей видимости, наиболее общим подходом в байесовской классификации.
Литература
http://www.lepskiy.ucoz.com/lect_Lepskiy_Bronevich_pass.pdf
http://lepskiy.ucoz.ru/_2_pass.pdf
Машинное обучение (курс лекций, К.В.Воронцов)
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |