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

Версия 18:28, 5 января 2010

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

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

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

Методы решения

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

Непараметрическое восстановление плотности

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

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

Построить функцию p~(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. К сожалению, нет универсального способа выбора областей 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) метод парзеновского окна.DN предполагаются регулярными областями, размеры которых удовлетворяют условиям теоремы, исходя из этого определяется число kN.

2) метод k ближайших соседей. Фиксируется не области DN, а число kN, затем для точки x0 определяется регулярная область, содержащая kN ближайших к x0 точек.

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

Идея: функция p(x) аппроксимируется с помощью системы базисных функций {φj}j=1 ∞. оценка p(x) ищется в виде ...

Коэффициенты cj выбираются таким образом, чтобы погрешность аппроксимации была минимальной, т.е. ...

Реально вместо бесконечного ряда (1) рассматривается конечная сумма первых l членов.

Как правило, рассматривают ортогональную систему базисных функций, при этом используют многочлены Лежандра, Чебышева, Эрмита, Лагранжа, Лагерра и т.п.

Параметрическое восстановление плотности

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

Постановка задачи Известен общий вид функции плотности распределения 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 в учебном процессе.