Байесовский классификатор
Материал из MachineLearning.
м |
м |
||
| Строка 32: | Строка 32: | ||
В байесовской теории классификации эта задача разделяется на две. | В байесовской теории классификации эта задача разделяется на две. | ||
| + | * Построение оптимального классификатора при известных плотностях классов. Эта подзадача имеет простое и окончательное решение. | ||
| + | * Восстановление плотностей классов по обучающей выборке. {{S|В этой}} подзадаче сосредоточена основная сложность байесовского подхода к классификации. | ||
=== Построение классификатора при известных плотностях классов === | === Построение классификатора при известных плотностях классов === | ||
| - | |||
Пусть для каждого класса <tex>y \in Y</tex> известна | Пусть для каждого класса <tex>y \in Y</tex> известна | ||
''априорная вероятность'' <tex>P_y</tex> того, что появится объект класса <tex>y</tex>, | ''априорная вероятность'' <tex>P_y</tex> того, что появится объект класса <tex>y</tex>, | ||
| Строка 44: | Строка 45: | ||
''Средний риск'' опредеяется как математическое ожидание ошибки: | ''Средний риск'' опредеяется как математическое ожидание ошибки: | ||
<center> | <center> | ||
| - | <tex>R(a) = \sum_{y\in Y} \sum_{s\in Y} \lambda_{y} P_y \mathsf{P}_{(x,y)}\bigl\{a(x)=s|y\bigr\}, | + | <tex>R(a) = \sum_{y\in Y} \sum_{s\in Y} \lambda_{y} P_y \mathsf{P}_{(x,y)}\bigl\{a(x)=s|y\bigr\},</tex> |
| - | </tex> | + | |
</center> | </center> | ||
где <tex>\lambda_{y}</tex> — ''цена ошибки'' или | где <tex>\lambda_{y}</tex> — ''цена ошибки'' или | ||
| Строка 52: | Строка 52: | ||
'''Теорема.''' Решением этой задачи является алгоритм | '''Теорема.''' Решением этой задачи является алгоритм | ||
<center> | <center> | ||
| - | <tex>a(x) = \mathrm{arg}\max_{y\in Y} \lambda_{y} P_y p_y(x). | + | <tex>a(x) = \mathrm{arg}\max_{y\in Y} \lambda_{y} P_y p_y(x).</tex> |
| - | </tex> | + | |
</center> | </center> | ||
| Строка 63: | Строка 62: | ||
=== Восстановление плотностей классов по обучающей выборке === | === Восстановление плотностей классов по обучающей выборке === | ||
| - | |||
По заданной подвыборке объектов класса <tex>y</tex> | По заданной подвыборке объектов класса <tex>y</tex> | ||
построить эмпирические оценки априорных вероятностей <tex>P_y</tex> | построить эмпирические оценки априорных вероятностей <tex>P_y</tex> | ||
| Строка 73: | Строка 71: | ||
[[Восстановление распределения вероятностей|Восстановление плотностей]] (функций правдоподобия каждого из классов) является наиболее трудной задачей. | [[Восстановление распределения вероятностей|Восстановление плотностей]] (функций правдоподобия каждого из классов) является наиболее трудной задачей. | ||
Наиболее распространены три подхода: параметрический, непараметрический | Наиболее распространены три подхода: параметрический, непараметрический | ||
| - | и | + | и разделение смеси вероятностных распределений. |
Третий подход занимает промежуточное положение между первыми двумя, | Третий подход занимает промежуточное положение между первыми двумя, | ||
и в определённом смысле является наиболее общим. | и в определённом смысле является наиболее общим. | ||
| Строка 79: | Строка 77: | ||
* ''Параметрическое'' восстановление плотности при дополнительном предположении, что [[многомерное нормальное распределение|плотности нормальные (гауссовские)]], приводит к [[нормальный дискриминантный анализ|нормальному дискриминантному анализу]] и [[Линейный дискриминант Фишера|линейному дискриминанту Фишера]]. | * ''Параметрическое'' восстановление плотности при дополнительном предположении, что [[многомерное нормальное распределение|плотности нормальные (гауссовские)]], приводит к [[нормальный дискриминантный анализ|нормальному дискриминантному анализу]] и [[Линейный дискриминант Фишера|линейному дискриминанту Фишера]]. | ||
* ''Непараметрическое'' восстановление плотности приводит, в частности, к [[метод парзеновского окна|методу парзеновского окна]]. | * ''Непараметрическое'' восстановление плотности приводит, в частности, к [[метод парзеновского окна|методу парзеновского окна]]. | ||
| - | * '' | + | * ''[[Разделение смеси распределений]]'' может быть сделано с помощью [[EM-алгоритм]]а. Дополнительное предположение, что плотности компонент смеси являются радиальными функциями, приводит к [[Метод радиальных базисных функций|методу радиальных базисных функций]]. Обычно в качестве компонент смеси берут, опять-таки, гауссовские плотности. |
Таким образом, формула байесовского классификатора приводит к большому разнообразию байесовских алгоритмов, отличающихся только способом восстановления плотностей. | Таким образом, формула байесовского классификатора приводит к большому разнообразию байесовских алгоритмов, отличающихся только способом восстановления плотностей. | ||
| Строка 97: | Строка 95: | ||
так как оценить <tex>n</tex> одномерных плотностей гораздо легче, чем | так как оценить <tex>n</tex> одномерных плотностей гораздо легче, чем | ||
одну <tex>n</tex>-мерную плотность. | одну <tex>n</tex>-мерную плотность. | ||
| - | К сожалению, оно крайне редко выполняется на практике, отсюда и название метода. | + | {{S|К сожалению}}, оно крайне редко выполняется на практике, отсюда и название метода. |
Наивный байесовский классификатор может быть как параметрическим, так и непараметрическим, | Наивный байесовский классификатор может быть как параметрическим, так и непараметрическим, | ||
| Строка 126: | Строка 124: | ||
* [[:Участник:Vokov|Воронцов К.В.]] [http://www.ccas.ru/voron/teaching.html#ML Математические методы обучения по прецедентам]. МФТИ (2004), ВМиК МГУ (2007). | * [[:Участник:Vokov|Воронцов К.В.]] [http://www.ccas.ru/voron/teaching.html#ML Математические методы обучения по прецедентам]. МФТИ (2004), ВМиК МГУ (2007). | ||
| + | [[Категория:Байесовская теория классификации]] | ||
[[Категория:Машинное обучение]] | [[Категория:Машинное обучение]] | ||
[[Категория:Классификация]] | [[Категория:Классификация]] | ||
[[Категория:Энциклопедия анализа данных]] | [[Категория:Энциклопедия анализа данных]] | ||
Версия 13:30, 30 апреля 2008
Байесовский классификатор — широкий класс алгоритмов классификации, основанный на принципе максимума апостериорной вероятности. Для классифицируемого объекта вычисляются функции правдоподобия каждого из классов, по ним вычисляются апостериорные вероятности классов. Объект относится к тому классу, для которого апостериорная вероятность максимальна.
Содержание |
Введение
Байесовский подход к классификации основан на теореме, утверждающей, что если плотности распределения каждого из классов известны, то искомый алгоритм можно выписать в явном аналитическом виде. Более того, этот алгоритм оптимален, то есть обладает минимальной вероятностью ошибок.
На практике плотности распределения классов, как правило, не известны. Их приходится оценивать (восстанавливать) по обучающей выборке. В результате байесовский алгоритм перестаёт быть оптимальным, так как восстановить плотность по выборке можно только с некоторой погрешностью. Чем короче выборка, тем выше шансы подогнать распределение под конкретные данные и столкнуться с эффектом переобучения.
Байесовский подход к классификации является одним из старейших, но до сих пор сохраняет прочные позиции в теории распознавания. Он лежит в основе многих достаточно удачных алгоритмов классификации.
К числу байесовских методов классификации относятся:
- Наивный байесовский классификатор
- Линейный дискриминант Фишера
- Квадратичный дискриминант
- Метод парзеновского окна
- Метод радиальных базисных функций (RBF)
- Логистическая регрессия
Основная формула
Пусть — множество описаний объектов,
— множество номеров (или наименований) классов.
На множестве пар «объект, класс»
определена
вероятностная мера
.
Имеется конечная обучающая выборка независимых наблюдений
,
полученных согласно вероятностной мере
.
Задача классификации заключается в том, чтобы построить алгоритм
,
способный классифицировать произвольный объект
.
В байесовской теории классификации эта задача разделяется на две.
- Построение оптимального классификатора при известных плотностях классов. Эта подзадача имеет простое и окончательное решение.
- Восстановление плотностей классов по обучающей выборке. В этой подзадаче сосредоточена основная сложность байесовского подхода к классификации.
Построение классификатора при известных плотностях классов
Пусть для каждого класса известна
априорная вероятность
того, что появится объект класса
,
и плотности распределения
каждого из классов,
называемые также функциями правдоподобия классов.
Требуется построить алгоритм классификации
,
доставляющий минимальное значение функционалу среднего риска.
Средний риск опредеяется как математическое ожидание ошибки:
где — цена ошибки или
штраф за отнесение объекта класса
к какому-либо другому классу.
Теорема. Решением этой задачи является алгоритм
Значение интерпретируется как апостериорная вероятность того, что объект
принадлежит классу
.
Если классы равнозначимы, ,
то объект
просто относится к классу
с наибольшим значением плотности распределения в точке
.
Восстановление плотностей классов по обучающей выборке
По заданной подвыборке объектов класса
построить эмпирические оценки априорных вероятностей
и функций правдоподобия
.
В качестве оценки априорных вероятностей берут, как правило, долю объектов данного класса в обучающей выборке.
Восстановление плотностей (функций правдоподобия каждого из классов) является наиболее трудной задачей. Наиболее распространены три подхода: параметрический, непараметрический и разделение смеси вероятностных распределений. Третий подход занимает промежуточное положение между первыми двумя, и в определённом смысле является наиболее общим.
- Параметрическое восстановление плотности при дополнительном предположении, что плотности нормальные (гауссовские), приводит к нормальному дискриминантному анализу и линейному дискриминанту Фишера.
- Непараметрическое восстановление плотности приводит, в частности, к методу парзеновского окна.
- Разделение смеси распределений может быть сделано с помощью EM-алгоритма. Дополнительное предположение, что плотности компонент смеси являются радиальными функциями, приводит к методу радиальных базисных функций. Обычно в качестве компонент смеси берут, опять-таки, гауссовские плотности.
Таким образом, формула байесовского классификатора приводит к большому разнообразию байесовских алгоритмов, отличающихся только способом восстановления плотностей.
Наивный байесовский классификатор
Наивный байесовский классификатор (naїve Bayes)
основан на той же формуле и дополнительном предположении, что
объекты описываются независимыми признаками:
.
Следовательно, функции правдоподобия классов представимы в виде
,
где
— плотность распределения значений
-го признака для класса
.
Предположение о независимости существенно упрощает задачу,
так как оценить одномерных плотностей гораздо легче, чем
одну
-мерную плотность.
К сожалению, оно крайне редко выполняется на практике, отсюда и название метода.
Наивный байесовский классификатор может быть как параметрическим, так и непараметрическим, в зависимости от того, каким методом восстанавливаются одномерные плотности.
Основные его преимущества — простота реализации и низкие вычислительные затраты при обучении и классификации. В тех редких случаях, когда признаки действительно независимы (или почти независимы), наивный байесовский классификатор (почти) оптимален.
Основной его недостаток — относительно низкое качество классификации в большинстве реальных задач.
Чаще всего он используется либо как примитивный эталон для сравнения различных моделей алгоритмов, либо как элементарный строительный блок в алгоритмических композициях.
Литература
- Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
- Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974.
- Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.
- Дуда Р., Харт П. Распознавание образов и анализ сцен. — М.: Мир, 1976.
- Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. — Springer, 2001. ISBN 0-387-95284-5.
Ссылки
- Воронцов К.В. Математические методы обучения по прецедентам. МФТИ (2004), ВМиК МГУ (2007).
