Оценивание плотности распределения

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

Байесовские алгоритмы классификации основываются на знании априорных вероятностей классов и законов распределения вероятностей признаков в каждом классе. На практике нам известна только обучающая выборка объектов. Будем считать элементы выборки независимыми случайными величинами, имеющими одинаковое распределение. Требуется по выборке оценить плотность этого распределения.

Постановка задачи Требуется по выборке Xl = (xi, yi)i=1 l независимых случайных векторов, распределенных по неизвестному закону p(x), оценить плотность p(x).

Методы решения Существуют три основных подхода к оцениванию плотности распределения: непараметрический, параметрический и восстановление смесей распределений.

Непараметрическое восстановление плотности Будем считать, что общий вид функции распределения неизвестен, известны только некоторые свойства - например, функция гладкая, непрерывная. Тогда для оценки плотности применяют непараметрические методы оценивания. Постановка задачи Построить функцию p~(x), которая апроксимировала бы неизвестную функцию p(x) в некотором смысле. Критерии апроксимации могут быть такими: 1) сходимость по вероятности в точке x - оценка p~(x) должна быть состоятельной; 2) среднеквадратичная сходимость в точке x - оценка p~(x) должна быть асимптотически несмещенной и асимптотически эффективной.

 Гистограммный метод оценивания.

Идея: если p(x) - плотность случайного вектора ξ, то ... где ..., V(D) - мера области D. Если X = {x1, ... , xN} - выборка, k - число значений выборки в D, то P(D)≈k/N. Поэтому p(x0)V(D)≈k/N ⇒ p(x0)≈k/(N*V(D)). Значит, p(x) = k/(N*V(D)) - оценка плотности.

    Построение гистограммы

1) найдем ограниченную область A пространства X(пространства объектов), содержащее все векторы из обучающей выборки Xl; 2) разобьем A на непересекающиеся области A1, ... , Ar; 3) если ki - количество элементов обучающей выборки Xl, принадлежащих области Ai, то ... где V(Ai) - мера области Ai. Оценка p(x|Xl) будет состоятельной при условии "правильного" выбора Ai.

    Гистограмма с шестью регулярными ячейками

//картинка//

    Недостатки гистограммного метода

1) невысокая точность; 2) требуется задание всей выборки; 3) нет универсального способа выбора областей Ai, чтобы оценка была состоятельной.

 Методы локального оценивания

Идея: оценить плотность p(x) в точке x0 с помощью элементов обучающей выборки, попавших в некоторую окрестность x0. Пусть XN = {x1, ... , xN} - последотельность выборок независимых случайных векторов, DN - последовательность областей, содержащих точку x, kN - число выборочных значений выборки XN, попавших в область DN. Теорема. Если функция p(x) непрерывна в точке x0, все области DN содержат точку x0 и удовлетворяют условиям 1) ... 2) ... то функция p~(x) = ... будет несмещенной, асимптотически эффективной и состоятельной оценкой плотности p(x) в точке x0. Существуют два основных подхода к выбору областей, содержащих точку x0: 1) метод парзеновского окна.Рассматриваются регулярные области, размеры которых удовлетворяют условиям теоремы, определяется число точек обучающей выборки, попавших внутрь этой области и вычисляется оценка плотности. 2) метод kN ближайших соседей. Фиксируется некоторая точка x0, задается число kN, вычисляются размеры наименьшей регулярной области, содержащей kN ближайших к x0 точек.

 Метод оценивания с помощью аппроксимации функции плотности

Идея: для аппроксимации функции p(x) выбирается некоторая система базисных функций {φj}j=1 ∞ и аппроксимирующая функция ищется в виде ... Коэффициенты cj выбираются таким образом, чтобы погрешность аппроксимации была минимальной, т.е. ... Реально вместо бесконечного ряда (1) рассматривается конечная сумма первых l членов. Как правило, рассматривают ортогональную систему базисных функций, при этом используют многочлены Лежандра, Чебышева, Эрмита, Лагранжа, Лагерра и т.п. Выбор того или иного типа многочленов определяется либо из имеющейся априорной информации о виде плотности распределения p(x), либо характером распределения выборочных значений, либо из соображений простоты. Использование аппроксимирующих функций позволяет организовать обработку данных "на лету", корректировать значения cj при поступлении новых членов в обучающей выборке.

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

Постановка задачи Известен общий вид функции плотности распределения p(x|a) случайного вектора ξ, зависящий от вектора параметров a. Требуется по обучающей выборке X = {x1, ... , xl} значений вектора ξ получить оценку a~ вектора a.

 Метод максимального правдоподобия

Предложен Р.Фишером в 1912г. Идея: найти такой вектор параметров a~, что ...

   Пример

Пусть плотность p(x) имеет вид многомерного нормального распределения: ... Тогда оценки параметров μ и Σ по методу максимального правдоподобия по выборке Xm имеют следующий вид ...

 Метод моментов

Идея: если p(x|a) - плотность распределения случайного вектора ξ, то начальные моменты m-го порядка равны ... Оценку E~[ξm] можно найти по выборке XN = {x1, ... , xN}: ... Оценку a~ можно из системы уравнений: ... Если зависимоть E[ξm](a) - непрерывна, то a~ - состоятельная оценка.

Восстановление смесей распределений Если "форма" классов имеет достаточно сложный вид, не "поддающийся" описанию одним распределением, то применяют методы восстановления смесей распрелений - описывают класс несколькими распределениями. Предположим, что плотность распределения p(x) имеет вид смеси k распределений: ... где pj(x) - функция правдоподобия j-й компоненты смеси, wj - её априорная вероятность. Функции правдоподобия принадлежат параметрическому семейству распределений φ(x; θ) и отличаются только значениями параметра, p (x) = φ(x; θ ). Постановка задачи Известна выборка Xm - независимых случайных наблюдений из смеси p(x), известны число k и функция φ. Требуется найти оценку параметров Θ = (w1, . . . ,wk, θ1, . . . , θk).

 EM-алгоритм

Идея: искусственно вводится вектор скрытых переменных G, обладающий следующими свойствами: 1) он может быть вычислен, если известны значения вектора параметров Θ; 2) поиск максимума правдоподобия сильно упрощается, если известны значения скрытых переменных. EM-алгоритм состоит из итерационного повторения двух шагов. На E-шаге вычисляется ожидаемое значение (expectation) вектора скрытых переменных G по текущему приближению вектора параметров Θ. На М-шаге решается задача максимизации правдоподобия (maximization) и находится следующее приближение вектора Θ по текущим значениям векторов G и Θ. Итерации останавливаются, когда значения функционала Q(Θ), где Q(Θ) = ... или скрытых переменных G перестают существенно изменяться. Удобнее контролировать скрытые переменные, так как они имеют смысл вероятностей и принимают значения из отрезка [0, 1].

   "Проблемы", возникающие при реализации EM-алгоритма.
       Проблема выбора начального приближения. Хотя алгоритм EM сходится при достаточно общих предположениях, скорость сходимости может существенно зависеть от "хорошего" выбора начального приближения. Сходимость ухудшается в тех случаях, когда делается попытка поместить несколько компонент в один фактический сгусток распределения, либо разместить компоненту посередине между сгустками.
       Проблема выбора числа компонент k. До сих пор предполагалось, что число компонент k известно заранее. На практике это, как правило, не так.

   EM-алгоритм с последовательным добавлением компонент позволяет решить обе эти проблемы. Идея данного метода заключается в следующем. Имея некоторый набор компонент, можно выделить объекты xi, которые хуже всего описываются смесью - это объекты с наименьшими значениями правдоподобия p(xi). По этим объектам строится ещё одна компонента. Затем она добавляется в смесь и запускаются EM-итерации, чтобы новая компонента и старые "притёрлись друг к другу". Так продолжается до тех пор, пока все объекты не окажутся покрыты компонентами.

Сравнение различных подходов Были рассмотрены три подхода к задаче оценивания плотности распределения: непараметрический, параметрический и разделение смесей. Каждый из них применяется при определенных априорных знаниях о плотности распределения. Параметрические методы восстановления используются, если вид функции распределения известен с точностью до набора параметров, которые оцениваются по обучающей выборке. Непараметрические методы уже не требуют знания функции распределения с точностью до параметров, а только некоторых свойств функции, например, непрерывность или гладкость. Если же форма классов имеет достаточно "сложный" вид, не поддающийся описанию одним распределением, то применяют методы разделения смесей, когда предполагается, что внутри класса плотность распределения представляет собой смесь нескольких распределений. Несмотря на то, что, казалось бы, все подходы имеют разные области применимости и используют разные методы обучения можно выделить и черты сходства между ними. Непараметрические оценки плотности можно рассматривать как предельный частный случай смеси распределений, в которой каждому обучающему объекту xi соответствует ровно одна компонента с априорной вероятностью wj = 1/m и сферической плотностью с центром в точке xi. С другой стороны, параметрический подход также является крайним случаем смеси - когда берётся только одна компонента. Таким образом, все три подхода отличаются, в первую очередь, количеством аддитивных компонент в модели распределения: 1 << k << m. Это приводит к качественным различиям в методах обучения. Требования к форме компонент ослабляются по мере увеличения их числа. Восстановление смеси из произвольного числа компонент k является, по всей видимости, наиболее общим подходом в байесовской классификации.

http://lepskiy.ucoz.ru/_2_pass.pdf

Данная статья является непроверенным учебным заданием. Студент: Участник:ihoho Преподаватель: Участник:Константин Воронцов Срок: 31 декабря 2009 До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.