Байесовский классификатор

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

(Различия между версиями)

Текущая версия

Байесовский классификатор — широкий класс алгоритмов классификации, основанный на принципе максимума апостериорной вероятности. Для классифицируемого объекта вычисляются функции правдоподобия каждого из классов, по ним вычисляются апостериорные вероятности классов. Объект относится к тому классу, для которого апостериорная вероятность максимальна.

Содержание

1 Введение
2 Основная формула
- 2.1 Построение классификатора при известных плотностях классов
- 2.2 Восстановление плотностей классов по обучающей выборке
3 Наивный байесовский классификатор
4 Литература
5 Ссылки

Введение

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

На практике плотности распределения классов, как правило, не известны. Их приходится оценивать (восстанавливать) по обучающей выборке. В результате байесовский алгоритм перестаёт быть оптимальным, так как восстановить плотность по выборке можно только с некоторой погрешностью. Чем короче выборка, тем выше шансы подогнать распределение под конкретные данные и столкнуться с эффектом переобучения.

Байесовский подход к классификации является одним из старейших, но до сих пор сохраняет прочные позиции в теории распознавания. Он лежит в основе многих достаточно удачных алгоритмов классификации.

К числу байесовских методов классификации относятся:

Основная формула

Пусть $X$ — множество описаний объектов, $Y$ — множество номеров (или наименований) классов. На множестве пар «объект, класс» $X \times Y$ определена вероятностная мера $\mathsf P$ . Имеется конечная обучающая выборка независимых наблюдений $X^m = \{(x_1,y_1),\ldots,(x_m,y_m)\}$ , полученных согласно вероятностной мере $\mathsf P$ .

Задача классификации заключается в том, чтобы построить алгоритм $a:\; X\to Y$ , способный классифицировать произвольный объект $x \in X$ .

В байесовской теории классификации эта задача разделяется на две.

Построение оптимального классификатора при известных плотностях классов. Эта подзадача имеет простое и окончательное решение.
Восстановление плотностей классов по обучающей выборке. В этой подзадаче сосредоточена основная сложность байесовского подхода к классификации.

Построение классификатора при известных плотностях классов

Пусть для каждого класса $y \in Y$ известна априорная вероятность $P_y$ того, что появится объект класса $y$ , и плотности распределения $p_y(x)$ каждого из классов, называемые также функциями правдоподобия классов. Требуется построить алгоритм классификации $a(x)$ , доставляющий минимальное значение функционалу среднего риска.

Средний риск опредеяется как математическое ожидание ошибки:

$R(a) = \sum_{y\in Y} \sum_{s\in Y} \lambda_{y} P_y \mathsf{P}_{(x,y)}\bigl\{a(x)=s|y\bigr\},$

где $\lambda_{y}$ — цена ошибки или штраф за отнесение объекта класса $y$ к какому-либо другому классу.

Теорема. Решением этой задачи является алгоритм

$a(x) = \mathrm{arg}\max_{y\in Y} \lambda_{y} P_y p_y(x).$

Значение $P\{y|x\} = P_y p_y(x)$ интерпретируется как апостериорная вероятность того, что объект $x$ принадлежит классу $y$ .

Если классы равнозначимы, $\lambda_{y} P_y = \mathrm{const}(y)$ , то объект $x$ просто относится к классу с наибольшим значением плотности распределения в точке $x$ .

Восстановление плотностей классов по обучающей выборке

По заданной подвыборке объектов класса $y$ построить эмпирические оценки априорных вероятностей $P_y$ и функций правдоподобия $p_y(x)$ .

В качестве оценки априорных вероятностей берут, как правило, долю объектов данного класса в обучающей выборке.

Восстановление плотностей (функций правдоподобия каждого из классов) является наиболее трудной задачей. Наиболее распространены три подхода: параметрический, непараметрический и разделение смеси вероятностных распределений. Третий подход занимает промежуточное положение между первыми двумя, и в определённом смысле является наиболее общим.

Параметрическое восстановление плотности при дополнительном предположении, что плотности нормальные (гауссовские), приводит к нормальному дискриминантному анализу и линейному дискриминанту Фишера.
Непараметрическое восстановление плотности приводит, в частности, к методу парзеновского окна.
Разделение смеси распределений может быть сделано с помощью EM-алгоритма. Дополнительное предположение, что плотности компонент смеси являются радиальными функциями, приводит к методу радиальных базисных функций. Обычно в качестве компонент смеси берут, опять-таки, гауссовские плотности.

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

Наивный байесовский классификатор

Наивный байесовский классификатор (naїve Bayes) основан на той же формуле и дополнительном предположении, что объекты описываются независимыми признаками. Предположение о независимости существенно упрощает задачу, так как оценить $n$ одномерных плотностей гораздо легче, чем одну $n$ -мерную плотность. К сожалению, оно крайне редко выполняется на практике, отсюда и название метода. Наивный байесовский классификатор может быть как параметрическим, так и непараметрическим, в зависимости от того, каким методом восстанавливаются одномерные плотности.

Литература

Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974.
Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.
Дуда Р., Харт П. Распознавание образов и анализ сцен. — М.: Мир, 1976.
Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. — Springer, 2001. ISBN 0-387-95284-5.

Ссылки

Машинное обучение (курс лекций, К.В.Воронцов)

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%91%D0%B0%D0%B9%D0%B5%D1%81%D0%BE%D0%B2%D1%81%D0%BA%D0%B8%D0%B9_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%B8%D1%84%D0%B8%D0%BA%D0%B0%D1%82%D0%BE%D1%80»

Категории: Байесовская теория классификации | Машинное обучение | Классификация | Энциклопедия анализа данных

@@ Строка 1: / Строка 1: @@
+'''Байесовский классификатор''' — широкий класс [[алгоритм]]ов [[классификация|классификации]], основанный на принципе максимума апостериорной вероятности. Для классифицируемого объекта вычисляются функции правдоподобия каждого из классов, по ним вычисляются апостериорные вероятности классов. Объект относится к тому классу, для которого апостериорная вероятность максимальна.
 == Введение ==
+Байесовский подход к классификации основан на теореме, утверждающей, что если плотности распределения каждого из классов известны, то искомый алгоритм можно выписать в явном аналитическом виде. Более того, этот алгоритм оптимален, то есть обладает минимальной вероятностью ошибок.
-Байесовский подход основан на теореме, утверждающей, что
+На практике плотности распределения классов, как правило, не известны. Их приходится [[Восстановление распределения вероятностей|оценивать (восстанавливать)]] по обучающей выборке. В результате байесовский алгоритм перестаёт быть оптимальным, так как восстановить плотность по выборке можно только с некоторой погрешностью. Чем короче выборка,
-если плотности распределения каждого из классов известны,
+тем выше шансы подогнать распределение под конкретные данные и столкнуться с [[переобучение|эффектом переобучения]].
-то искомый алгоритм можно выписать в явном аналитическом виде.
-Более того, этот алгоритм оптимален,
-то есть обладает минимальной вероятностью ошибок.
-На практике плотности распределения классов, как правило, не известны.
+Байесовский подход к классификации является одним из старейших, но до сих пор сохраняет прочные позиции в теории распознавания. Он лежит в основе многих достаточно удачных алгоритмов классификации.
-Их приходится оценивать (восстанавливать) по обучающей выборке.
-В результате байесовский алгоритм перестаёт быть оптимальным,
-так как восстановить плотность по выборке можно только с некоторой погрешностью.
-Чем короче выборка,
-тем выше шансы подогнать распределение под конкретные данные
-и столкнуться с [[переобучение|эффектом переобучения]].
-Байесовский подход к классификации является одним из старейших,
+К числу байесовских методов классификации относятся:
-но до сих пор сохраняет прочные позиции в теории распознавания.
+* [[Наивный байесовский классификатор]]
-Он лежит в основе многих достаточно удачных алгоритмов классификации.
+* [[Линейный дискриминант Фишера]]
+* [[Квадратичный дискриминант]]
+* [[Метод парзеновского окна]]
+* [[Метод радиальных базисных функций]] (RBF)
+* [[Логистическая регрессия]]
 == Основная формула ==
 Пусть <tex>X</tex> — множество описаний объектов,
 <tex>Y</tex> — множество номеров (или наименований) классов.
@@ Строка 26: / Строка 23: @@
 [[вероятностная мера]]&nbsp;<tex>\mathsf P</tex>.
 Имеется конечная [[выборка|обучающая выборка]] независимых наблюдений
-<tex>X^m = \{(x_1,y_1),\dots,(x_m,y_m)\}</tex>,
+<tex>X^m = \{(x_1,y_1),\ldots,(x_m,y_m)\}</tex>,
 полученных согласно вероятностной мере&nbsp;<tex>\mathsf P</tex>.
-'''Задача классификации''' заключается в том, чтобы построить алгоритм
+'''Задача классификации''' заключается в том, чтобы построить [[алгоритм]]
 <tex>a:\; X\to Y</tex>,
 способный классифицировать произвольный объект
@@ Строка 35: / Строка 32: @@
 В байесовской теории классификации эта задача разделяется на две.
+* Построение оптимального классификатора при известных плотностях классов. Эта подзадача имеет простое и окончательное решение.
+* Восстановление плотностей классов по обучающей выборке. {{S|В этой}} подзадаче сосредоточена основная сложность байесовского подхода к классификации.
 === Построение классификатора при известных плотностях классов ===
-'''Задача 1.'''
 Пусть для каждого класса <tex>y \in Y</tex> известна
 ''априорная вероятность'' <tex>P_y</tex> того, что появится объект класса <tex>y</tex>,
@@ Строка 48: / Строка 45: @@
 ''Средний риск'' опредеяется как математическое ожидание ошибки:
 <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>
 где <tex>\lambda_{y}</tex> — ''цена ошибки'' или
@@ Строка 56: / Строка 52: @@
 '''Теорема.''' Решением этой задачи является алгоритм
 <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>
-Если классы равнозначны, <tex>\lambda_{y} P_y = \mathrm{const}(y)</tex>,
+Значение <tex>P\{y|x\} = P_y p_y(x)</tex> интерпретируется как [[апостериорная вероятность]] того, что объект <tex>x</tex> принадлежит классу <tex>y</tex>.
+Если классы равнозначимы, <tex>\lambda_{y} P_y = \mathrm{const}(y)</tex>,
 то объект <tex>x</tex> просто относится к классу
 с наибольшим значением плотности распределения в точке <tex>x</tex>.
 === Восстановление плотностей классов по обучающей выборке ===
-'''Задача 2.'''
 По заданной подвыборке объектов класса <tex>y</tex>
 построить эмпирические оценки априорных вероятностей <tex>P_y</tex>
 и функций правдоподобия <tex>p_y(x)</tex>.
-В качестве оценки априорных вероятностей берут, как правило,
+В качестве оценки априорных вероятностей берут, как правило, долю объектов данного класса в обучающей выборке.
-долю объектов данного класса в обучающей выборке.
-Восстановление плотностей (функций правдоподобия каждого из классов) является самой трудной задачей.
+[[Восстановление распределения вероятностей|Восстановление плотностей]] (функций правдоподобия каждого из классов) является наиболее трудной задачей.
-Наиболее распространены три подхода: параметрический, непараметрический
+Наиболее распространены три подхода: параметрический, непараметрический и разделение смеси вероятностных распределений.
-и расщепление смеси вероятностных распределений.
+Третий подход занимает промежуточное положение между первыми двумя, и в определённом смысле является наиболее общим.
-Третий подход занимает промежуточное положение между первыми двумя,
-и в определённом смысле является наиболее общим.
 * ''Параметрическое'' восстановление плотности при дополнительном предположении, что [[многомерное нормальное распределение|плотности нормальные (гауссовские)]], приводит к [[нормальный дискриминантный анализ|нормальному дискриминантному анализу]] и [[Линейный дискриминант Фишера|линейному дискриминанту Фишера]].
 * ''Непараметрическое'' восстановление плотности приводит, в частности, к [[метод парзеновского окна|методу парзеновского окна]].
-* ''Восстановление смеси плотностей'' может быть сделано с помощью [[EM-алгоритм]]а. Дополнительное предположение, что плотности компонент смеси являются радиальными функциями, приводит к [[Метод радиальных базисных функций|методу радиальных базисных функций]]. Обычно в качестве компонент смеси берут, опять-таки, гауссовские плотности.
+* ''[[Разделение смеси распределений]]'' может быть сделано с помощью [[EM-алгоритм]]а. Дополнительное предположение, что плотности компонент смеси являются радиальными функциями, приводит к [[Метод радиальных базисных функций|методу радиальных базисных функций]]. Обычно в качестве компонент смеси берут, опять-таки, гауссовские плотности.
 Таким образом, формула байесовского классификатора приводит к большому разнообразию байесовских алгоритмов, отличающихся только способом восстановления плотностей.
 == Наивный байесовский классификатор ==
+''[[Наивный байесовский классификатор]]'' (naїve Bayes)
-''Наивный байесовский классификатор'' (naїve Bayes)
 основан на той же формуле и дополнительном предположении, что
-объекты описываются <tex>n</tex> независимыми признаками:
+объекты описываются независимыми признаками.
-<tex>x \equiv \bigl( \xi_1=f_1(x),\ldots, \xi_n=f_n(x) \bigr)</tex>.
-Следовательно, функции правдоподобия классов представимы в виде
-<tex>p_y(x) = p_{y1}(\xi_1) \cdot \ldots \cdot p_{yn}(\xi_n)</tex>,
-где
-<tex>p_{yj}(\xi_j)</tex> — плотность распределения значений
-<tex>j</tex>-го признака для класса <tex>y</tex>.
 Предположение о независимости существенно упрощает задачу,
 так как оценить <tex>n</tex> одномерных плотностей гораздо легче, чем
 одну <tex>n</tex>-мерную плотность.
-К сожалению, оно крайне редко выполняется на практике, отсюда и название метода.
+{{S|К сожалению}}, оно крайне редко выполняется на практике, отсюда и название метода.
 Наивный байесовский классификатор может быть как параметрическим, так и непараметрическим,
 в зависимости от того, каким методом восстанавливаются одномерные плотности.
-Основные его преимущества — простота реализации
-и низкие вычислительные затраты при обучении и классификации.
-В тех редких случаях, когда
-признаки действительно независимы (или почти независимы),
-наивный байесовский классификатор (почти) оптимален.
-Основной его недостаток —
-относительно низкое качество классификации в большинстве реальных задач.
-Чаще всего он используется либо как примитивный эталон
-для сравнения различных моделей алгоритмов,
-либо как элементарный строительный блок
-в [[алгоритмическая композиция|алгоритмических композициях]].
 == Литература ==
 # ''Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д.'' Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
+# ''Вапник В. Н., Червоненкис А. Я.'' Теория распознавания образов. — М.: Наука, 1974.
 # ''Вапник В. Н.'' Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.
 # ''Дуда Р., Харт П.'' Распознавание образов и анализ сцен. — М.: Мир, 1976.
@@ Строка 131: / Строка 97: @@
 == Ссылки ==
+* [[Машинное обучение (курс лекций, К.В.Воронцов)]]
-* [[:Участник:Vokov|Воронцов К.В.]] [http://www.ccas.ru/voron/teaching.html#ML Математические методы обучения по прецедентам]. МФТИ (2004), ВМиК МГУ (2007).
+[[Категория:Байесовская теория классификации]]
 [[Категория:Машинное обучение]]
+[[Категория:Классификация]]
 [[Категория:Энциклопедия анализа данных]]

Байесовский классификатор

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

Текущая версия

Содержание

Введение

Основная формула

Построение классификатора при известных плотностях классов

Восстановление плотностей классов по обучающей выборке

Наивный байесовский классификатор

Литература

Ссылки

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты