WikiSort.ru - Не сортированное

Машинное обучение и data mining

Задачи Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение

Обучение с учителем Метод k-ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамбли моделей (Бэггинг, Бустинг, Random forest) Метод релевантных векторов

Кластерный анализ Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift

Снижение размерности Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE

Структурное прогнозирование Графовая вероятностная модель (Байесовская сеть, Скрытая марковская модель, CRF)

Выявление аномалий Метод k-ближайших соседей Локальный уровень выброса

Графовые вероятностные модели Байесовская сеть Марковская сеть Скрытая марковская модель

Искусственные нейронные сети Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации (Сигмоида, Softmax, Радиально-базисная функция) Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть (Долгая краткосрочная память, Управляемый рекуррентный блок) Свёрточная нейронная сеть (U-Net) Автокодировщик

Обучение с подкреплением Марковский процесс Уравнение Беллмана Жадный алгоритм Q-learning SARSA Temporal difference (TD)

Теория Теория Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения

Журналы и конференции NIPS ICML ML JMLR ArXiv:cs.LG

Глоссарий Глоссарий по машинному обучению

Статьи по теме List of datasets for machine-learning research Outline of machine learning

Наи́вный ба́йесовский классифика́тор — простой вероятностный классификатор, основанный на применении теоремы Байеса со строгими (наивными) предположениями о независимости.

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

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

Достоинством наивного байесовского классификатора является малое количество данных необходимых для обучения, оценки параметров и классификации.

Модель наивного байесовского классификатора

Вероятностная модель для классификатора — это условная модель

${\displaystyle p(C\mid F_{1},\dots ,F_{n})}$

над зависимой переменной класса ${\displaystyle C}$ с малым количеством результатов или классов, зависимая от нескольких переменных ${\displaystyle F_{1},\ldots ,F_{n}}$ . Проблема заключается в том, что когда количество свойств ${\displaystyle n}$ очень велико или когда свойство может принимать большое количество значений, тогда строить такую модель на вероятностных таблицах становится невозможно. Поэтому мы переформулируем модель, чтобы сделать её легко поддающейся обработке.

Используя теорему Байеса, запишем

${\displaystyle p(C\mid F_{1},\dots ,F_{n})={\frac {p(C)\ p(F_{1},\dots ,F_{n}\mid C)}{p(F_{1},\dots ,F_{n})}}.}$

На практике интересен лишь числитель этой дроби, так как знаменатель не зависит от ${\displaystyle C}$ и значения свойств ${\displaystyle F_{i}}$ даны, так что знаменатель — константа.

Числитель эквивалентен совместной вероятности модели

${\displaystyle p(C,F_{1},\dots ,F_{n})}$

которая может быть переписана следующим образом, используя повторные приложения определений условной вероятности:

${\displaystyle p(C,F_{1},\dots ,F_{n})=}$

${\displaystyle =p(C)\ p(F_{1},\dots ,F_{n}\mid C)=}$

${\displaystyle =p(C)\ p(F_{1}\mid C)\ p(F_{2},\dots ,F_{n}\mid C,F_{1})=}$

${\displaystyle =p(C)\ p(F_{1}\mid C)\ p(F_{2}\mid C,F_{1})\ p(F_{3},\dots ,F_{n}\mid C,F_{1},F_{2})=}$

${\displaystyle =p(C)\ p(F_{1}\mid C)\ p(F_{2}\mid C,F_{1})\cdot \ldots \cdot p(F_{n}\mid C,F_{1},F_{2},F_{3},\dots ,F_{n-1})}$

и т. д. Теперь можно использовать «наивные» предположения условной независимости: предположим, что каждое свойство ${\displaystyle F_{i}}$ условно независимо от любого другого свойства ${\displaystyle F_{j}}$ при ${\displaystyle j\neq i}$ . Это означает:

${\displaystyle p(F_{i}\mid C,F_{j})=p(F_{i}\mid C)}$

таким образом, совместная модель может быть выражена как:

${\displaystyle p(C,F_{1},\dots ,F_{n})=p(C)\ p(F_{1}\mid C)\ p(F_{2}\mid C)\ p(F_{3}\mid C)\cdot \ldots \cdot p(F_{n}\mid C)=}$

${\displaystyle =p(C)\prod _{i=1}^{n}p(F_{i}\mid C).}$

Это означает, что из предположения о независимости, условное распределение по классовой переменной ${\displaystyle C}$ может быть выражено так:

${\displaystyle p(C\mid F_{1},\dots ,F_{n})={\frac {1}{Z}}p(C)\prod _{i=1}^{n}p(F_{i}\mid C)}$

где ${\displaystyle Z=p(F_{1},\dots ,F_{n})}$  — это масштабный множитель, зависящий только от ${\displaystyle F_{1},\dots ,F_{n}}$ , то есть константа, если значения переменных известны.

Оценка параметров

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

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

Построение классификатора по вероятностной модели

Наивный байесовский классификатор объединяет модель с правилом решения. Одно общее правило должно выбрать наиболее вероятную гипотезу; оно известно как апостериорное правило принятия решения (MAP). Соответствующий классификатор — это функция ${\displaystyle \mathrm {classify} }$ , определённая следующим образом:

${\displaystyle \operatorname {classify} (f_{1},\dots ,f_{n})=\arg \max _{c}p(C=c)\prod _{i=1}^{n}p(F_{i}=f_{i}\mid C=c)}$

Пример: фильтрация спама

Рассмотрим простой пример применения наивного байесовского классификатора к задаче классификации документов по их содержимому, а именно к классификации электронных писем на два класса — спам (${\displaystyle S}$ ) и не-спам (${\displaystyle \neg S}$ ).

Будем считать, что документы выбраны из нескольких классов документов, которые могут быть представлены множеством слов с (независимой) вероятностью, что i-е слово данного документа встречается в документе класса C:

${\displaystyle p(w_{i}\mid C)}$

(Для этой задачи предположим, что вероятность встречи слова в документе независима от длины документа и все документы имеют одинаковую длину.)

Тогда вероятность для данного документа D и класса C

${\displaystyle p(D\mid C)=\prod _{i}p(w_{i}\mid C)}$

Вопрос, на который мы хотим ответить: «какова вероятность того, что данный документ D принадлежит классу C?». Другими словами, чему равна ${\displaystyle p(C\mid D)}$ ?

По теореме Байеса

${\displaystyle p(C\mid D)={p(C) \over p(D)}\,p(D\mid C)}$

Предположим, что мы имеем только два класса: S и ¬S (напр. спам и не-спам). Тогда

${\displaystyle p(S\mid D)={p(S) \over p(D)}\,\prod _{i}p(w_{i}\mid S)}$

${\displaystyle p(\neg S\mid D)={p(\neg S) \over p(D)}\,\prod _{i}p(w_{i}\mid \neg S)}$

Поделив одно на другое получим отношение правдоподобия

${\displaystyle {p(S\mid D) \over p(\neg S\mid D)}={p(S) \over p(\neg S)}\,\prod _{i}{p(w_{i}\mid S) \over p(w_{i}\mid \neg S)}}$

или (для логарифма правдоподобия)

${\displaystyle \ln {p(S\mid D) \over p(\neg S\mid D)}=\ln {p(S) \over p(\neg S)}+\sum _{i}\ln {p(w_{i}\mid S) \over p(w_{i}\mid \neg S)}}$

Действительная вероятность ${\displaystyle p(S\mid D)}$ может быть посчитана из ${\displaystyle \ln {p(S\mid D) \over p(\neg S\mid D)}}$ основываясь на наблюдении, что ${\displaystyle p(S\mid D)+p(\neg S\mid D)=1}$ . Для этого необходимо из функции правдоподобия сформировать вероятностное пространство

${\displaystyle p(S\mid D)={\frac {e^{q}}{1+e^{q}}}}$ , где ${\displaystyle q=\ln {p(S\mid D) \over p(\neg S\mid D)}}$

Наконец, документ может быть классифицирован сравнением логарифма правдоподобия с некоторым порогом h (например h=0). Перед нами спам, если

${\displaystyle \ln {p(S\mid D) \over p(\neg S\mid D)}>h}$ .

См. также

• Байесовская сеть доверия
• Линейный классификатор

Ссылки

• Domingos, Pedro & Michael Pazzani (1997) «On the optimality of the simple Bayesian classifier under zero-one loss». Machine Learning, 29:103-137. (also online at CiteSeer: )
• Rish, Irina. (2001). «An empirical study of the naive Bayes classifier». IJCAI 2001 Workshop on Empirical Methods in Artificial Intelligence. (available online: PDF, PostScript)
• Hand, DJ, & Yu, K. (2001). «Idiot’s Bayes — not so stupid after all?» International Statistical Review. Vol 69 part 3, pages 385—399. ISSN 0306-7734.
• Mozina M, Demsar J, Kattan M, & Zupan B. (2004). «Nomograms for Visualization of Naive Bayesian Classifier». In Proc. of PKDD-2004, pages 337—348. (available online: PDF  (недоступная ссылка с 13-05-2013 [2116 дней] — история))
• Maron, M. E. (1961). «Automatic Indexing: An Experimental Inquiry.» Journal of the ACM (JACM) 8(3):404-417. (available online: PDF)
• Minsky, M. (1961). «Steps toward Artificial Intelligence.» Proceedings of the IRE 49(1):8-30.
• McCallum, A. and Nigam K. «A Comparison of Event Models for Naive Bayes Text Classification». In AAAI/ICML-98 Workshop on Learning for Text Categorization, pp. 41–48. Technical Report WS-98-05. AAAI Press. 1998. (available online: PDF)
• Субботин С. В., Большаков Д. Ю. Применение байесовского классификатора для распознавания классов целей. // «Журнал Радиоэлектроники», 2006, № 4 (available online)

Программные продукты

• jBNC — Bayesian Network Classifier Toolbox

Для улучшения этой статьи желательно: Проверить достоверность указанной в статье информации. Проставив сноски, внести более точные указания на источники.