Наивный классификатор Байеса
Часть серии о |
Байесовская статистика |
---|
Апостериорный = Вероятность × Априорный ÷ Доказательства |
Фон |
Модельное здание |
Апостериорное приближение |
Оценщики |
Приближение доказательств |
Оценка модели |
В статистике наивные классификаторы Байеса представляют собой семейство линейных « вероятностных классификаторов », которые предполагают, что признаки условно независимы, учитывая целевой класс. Сила (наивность) этого предположения и дала классификатору такое название. Эти классификаторы относятся к числу простейших моделей байесовских сетей . [ 1 ]
Наивные байесовские классификаторы хорошо масштабируются и требуют ряда параметров, линейных по количеству переменных (признаков/предикторов) в задаче обучения. Обучение максимальному правдоподобию можно выполнить путем оценки выражения в закрытой форме , [ 2 ] : 718 для этого требуется линейное время , а не дорогостоящая итеративная аппроксимация , используемая для многих других типов классификаторов.
В статистической литературе наивные модели Байеса известны под разными названиями, включая простой Байес и независимость Байеса . [ 3 ] Все эти названия относятся к использованию теоремы Байеса в решающем правиле классификатора, но наивный Байес не обязательно является байесовским методом. [ 2 ] [ 3 ]
Введение
[ редактировать ]Наивный Байес — это простой метод построения классификаторов: моделей, которые присваивают метки классов экземплярам задач, представленным в виде векторов значений признаков , где метки классов извлекаются из некоторого конечного набора. Не существует единого алгоритма обучения таких классификаторов, а есть семейство алгоритмов, основанных на общем принципе: все наивные байесовские классификаторы предполагают, что значение определенного признака не зависит от значения любого другого признака с учетом переменной класса. Например, яблоком можно считать фрукт, если он красный, круглый и диаметром около 10 см. Наивный байесовский классификатор считает, что каждая из этих характеристик независимо вносит вклад в вероятность того, что этот фрукт является яблоком, независимо от любых возможных корреляций между признаками цвета, округлости и диаметра.
Во многих практических приложениях для оценки параметров наивных моделей Байеса используется метод максимального правдоподобия ; другими словами, можно работать с наивной байесовской моделью, не принимая байесовскую вероятность и не используя какие-либо байесовские методы.
Несмотря на свою наивную конструкцию и явно упрощенные предположения, наивные байесовские классификаторы неплохо себя зарекомендовали во многих сложных реальных ситуациях. В 2004 году анализ проблемы байесовской классификации показал, что существуют веские теоретические причины для явно неправдоподобной эффективности наивных байесовских классификаторов. [ 4 ] Тем не менее, всестороннее сравнение с другими алгоритмами классификации в 2006 году показало, что байесовская классификация уступает другим подходам, таким как усиленные деревья или случайные леса . [ 5 ]
Преимущество наивного байесовского метода состоит в том, что для оценки параметров, необходимых для классификации, требуется лишь небольшой объем обучающих данных. [ 6 ]
Вероятностная модель
[ редактировать ]Абстрактно, наивный Байес — это модель условной вероятности : она присваивает вероятности для каждого из K возможных исходов или классов задан экземпляр проблемы, который нужно классифицировать, представленный вектором кодирование некоторых n признаков (независимых переменных). [ 7 ]
Проблема с приведенной выше формулировкой заключается в том, что если количество признаков n велико или признак может принимать большое количество значений, то основывать такую модель на таблицах вероятностей невозможно. Поэтому модель необходимо переформулировать, чтобы сделать ее более управляемой. Используя теорему Байеса , условную вероятность можно разложить как:
На простом английском языке, используя терминологию байесовской вероятности , приведенное выше уравнение можно записать как
На практике интерес представляет только числитель этой дроби, поскольку знаменатель не зависит от и значения признаков даны так, что знаменатель фактически постоянен. Числитель эквивалентен совместной вероятностной модели. которое можно переписать следующим образом, используя цепное правило для повторного применения определения условной вероятности :
«наивные» предположения условной независимости : предположим, что все функции в Теперь в игру вступают , взаимно независимы обусловлены категорией . Согласно этому предположению,
Таким образом, совместную модель можно выразить как где обозначает пропорциональность, поскольку знаменатель опущено.
Это означает, что при сделанных выше предположениях независимости условное распределение по переменной класса является: где доказательства является масштабным коэффициентом, зависящим только от , то есть константа, если известны значения переменных объекта.
Построение классификатора из вероятностной модели
[ редактировать ]В результате обсуждения до сих пор была выведена модель независимых признаков, то есть наивная вероятностная модель Байеса . Наивный байесовский классификатор сочетает эту модель с решающим правилом . Одно общее правило — выбирать наиболее вероятную гипотезу, чтобы свести к минимуму вероятность ошибочной классификации; это известно как максимальное апостериорное правило принятия решения или MAP . Соответствующий классификатор, классификатор Байеса , — это функция, которая присваивает метку класса. для некоторого k следующим образом:
Оценка параметров и модели событий
[ редактировать ]Приоритет класса может быть рассчитан, предполагая равновероятные классы, т. е. или путем расчета оценки вероятности класса из обучающего набора: Чтобы оценить параметры распределения признака, необходимо предположить распределение или создать непараметрические модели для признаков из обучающего набора. [ 8 ]
Предположения о распределении признаков называются «моделью событий» наивного байесовского классификатора. Для дискретных функций, подобных тем, которые встречаются при классификации документов (включая фильтрацию спама), полиномиальные распределения и распределения Бернулли популярны . Эти предположения приводят к двум различным моделям, которые часто путают. [ 9 ] [ 10 ]
Гауссов наивный Байес
[ редактировать ]При работе с непрерывными данными типичным предположением является то, что непрерывные значения, связанные с каждым классом, распределяются в соответствии с нормальным (или гауссовым) распределением. Например, предположим, что обучающие данные содержат непрерывный атрибут, . Данные сначала сегментируются по классу, а затем по среднему значению и дисперсии . рассчитывается в каждом классе. Позволять быть средним значением в связанный с классом , и пусть быть скорректированной по Бесселю дисперсией значений в связанный с классом . Предположим, кто-то собрал некоторое значение наблюдения . Тогда плотность вероятности дали класс , то есть, , можно вычислить, подставив в уравнение нормального распределения, параметризованное и . Формально,
Другой распространенный метод обработки непрерывных значений — использование группирования для дискретизации значений признаков и получения нового набора признаков, распределенных по Бернулли. В некоторой литературе предполагается, что это необходимо для использования наивного Байеса, но это неправда, поскольку дискретизация может отбросить дискриминационную информацию . [ 3 ]
Иногда распределение условно-классовых предельных плотностей далеко от нормального. В этих случаях оценка плотности ядра может использоваться для более реалистичной оценки предельных плотностей каждого класса. Этот метод, предложенный Джоном и Лэнгли, [ 8 ] может значительно повысить точность классификатора. [ 11 ] [ 12 ]
Полиномиальный наивный Байес
[ редактировать ]В полиномиальной модели событий выборки (векторы признаков) представляют собой частоты, с которыми определенные события были созданы полиномиальной моделью. где — это вероятность того, что событие i произойдет (или K таких многочленов в случае мультикласса). Вектор признаков тогда это гистограмма с подсчет количества раз, когда событие i наблюдалось в конкретном случае. Это модель событий, обычно используемая для классификации документов, где события представляют появление слова в одном документе (см. предположение о наборе слов ). Вероятность наблюдения гистограммы x определяется выражением: где .
Полиномиальный наивный байесовский классификатор становится линейным классификатором, если его выразить в логарифмическом пространстве: [ 13 ] где и . Оценка параметров в пространстве журнала предпочтительна, поскольку умножение большого количества малых значений может привести к значительной ошибке округления. Применение логарифмического преобразования уменьшает влияние этой ошибки округления.
Если данный класс и значение признака никогда не встречаются вместе в обучающих данных, то оценка вероятности на основе частоты будет равна нулю, поскольку оценка вероятности прямо пропорциональна количеству появлений значения признака. Это проблематично, поскольку при их умножении будет уничтожена вся информация о других вероятностях. Поэтому часто желательно включать поправку малой выборки, называемую псевдосчетом , во все оценки вероятности, чтобы ни одна вероятность никогда не становилась точно равной нулю. Этот способ регуляризации наивного Байеса называется сглаживанием Лапласа , когда псевдосчет равен единице, и сглаживанием Лидстоуна в общем случае.
Ренни и др. обсудить проблемы с полиномиальным предположением в контексте классификации документов и возможные способы решения этих проблем, включая использование весов tf–idf вместо необработанных частот терминов и нормализации длины документа, чтобы создать наивный байесовский классификатор, конкурентоспособный с опорным вектором машины . [ 13 ]
Бернулли, наивный Байес
[ редактировать ]В многомерной модели событий Бернулли функции представляют собой независимые логические переменные ( двоичные переменные ), описывающие входные данные. Как и полиномиальная модель, эта модель популярна для задач классификации документов. [ 9 ] где используются признаки появления двоичных терминов, а не частоты терминов. Если — логическое значение, выражающее появление или отсутствие i -го термина в словаре, а затем вероятность документа, заданного классом дается: [ 9 ] где вероятность класса создание термина . Эта модель событий особенно популярна для классификации коротких текстов. Его преимущество заключается в явном моделировании отсутствия терминов. Обратите внимание, что наивный байесовский классификатор с моделью событий Бернулли — это не то же самое, что полиномиальный классификатор NB с числом частот, усеченным до единицы.
Полуконтролируемая оценка параметров
[ редактировать ]Имея способ обучения наивного байесовского классификатора на основе помеченных данных, можно построить полуконтролируемый алгоритм обучения, который может обучаться на комбинации помеченных и неразмеченных данных, запуская алгоритм обучения с учителем в цикле: [ 14 ]
- Учитывая коллекцию меченых образцов L и немеченых образцов U начните с обучения наивного байесовского классификатора на L .
- До схождения делаем:
- Прогнозирование вероятностей классов для всех примеров x в .
- Переобучите модель на основе вероятностей ( а не меток), предсказанных на предыдущем шаге.
Сходимость определяется на основе улучшения правдоподобия модели. , где обозначает параметры наивной байесовской модели.
Этот алгоритм обучения является примером более общего алгоритма максимизации ожидания (EM): шагом прогнозирования внутри цикла является E -шаг EM, а повторное обучение наивного байесовского алгоритма представляет собой M -шаг. Алгоритм формально обоснован предположением, что данные генерируются моделью смеси , а компоненты этой модели смеси являются в точности классами задачи классификации. [ 14 ]
Обсуждение
[ редактировать ]Несмотря на то, что далеко идущие предположения о независимости часто бывают неточными, наивный классификатор Байеса обладает несколькими свойствами, которые делают его удивительно полезным на практике. В частности, разделение распределений условных признаков классов означает, что каждое распределение можно независимо оценить как одномерное распределение. Это помогает смягчить проблемы, возникающие из-за «проклятия размерности» , например, необходимость в наборах данных, которые экспоненциально масштабируются в зависимости от количества объектов. Хотя наивный Байес часто не может дать точную оценку правильных вероятностей классов, [ 15 ] для многих приложений это может не быть требованием. Например, простой байесовский классификатор выполнит правильную классификацию по правилу принятия решений MAP, если правильный класс прогнозируется как более вероятный, чем любой другой класс. Это верно независимо от того, является ли оценка вероятности незначительной или даже крайне неточной. Таким образом, общий классификатор может быть достаточно надежным, чтобы игнорировать серьезные недостатки лежащей в его основе наивной вероятностной модели. [ 16 ] Другие причины наблюдаемого успеха наивного байесовского классификатора обсуждаются в цитируемой ниже литературе.
Связь с логистической регрессией
[ редактировать ]В случае дискретных входных данных (индикатор или частотные характеристики для дискретных событий) наивные байесовские классификаторы образуют генеративно-дискриминативную пару с классификаторами полиномиальной логистической регрессии : каждый наивный байесовский классификатор можно рассматривать как способ подбора вероятностной модели, которая оптимизирует совместное правдоподобие. , в то время как логистическая регрессия соответствует той же вероятностной модели для оптимизации условного . [ 17 ]
Более формально мы имеем следующее:
Теорема . Наивные байесовские классификаторы бинарных признаков включаются в состав классификаторов логистической регрессии.
Рассмотрим общую задачу многоклассовой классификации с возможными классами , то (ненаивный) классификатор Байеса дает по теореме Байеса:
Наивный классификатор Байеса дает где
Это и есть классификатор логистической регрессии.
Связь между ними можно увидеть, заметив, что функцию решения для наивного Байеса (в двоичном случае) можно переписать как «класс прогнозирования если шансы превосходят показатели ". Выражение этого в пространстве журнала дает:
Левая часть этого уравнения — это логарифм шансов, или logit , величина, предсказанная линейной моделью, которая лежит в основе логистической регрессии. Поскольку наивный Байес также является линейной моделью для двух «дискретных» моделей событий, ее можно перепараметризовать как линейную функцию. . В таком случае получение вероятностей представляет собой вопрос применения логистической функции к или в случае мультикласса функция softmax .
Дискриминационные классификаторы имеют меньшую асимптотическую ошибку, чем генеративные; однако исследования Нг и Джордана показали, что в некоторых практических случаях наивный байесовский метод может превзойти логистическую регрессию, поскольку он быстрее достигает своей асимптотической ошибки. [ 17 ]
Примеры
[ редактировать ]Классификация лиц
[ редактировать ]Задача: определить, является ли данный человек мужчиной или женщиной на основе измеренных характеристик. К характеристикам относятся рост, вес и размер стопы. Хотя в классификаторе NB мы рассматриваем их как независимые, на самом деле это не так.
Обучение
[ редактировать ]Пример обучающего набора ниже.
Человек | рост (футы) | вес (фунты) | размер стопы (дюймы) |
---|---|---|---|
мужской | 6 | 180 | 12 |
мужской | 5,92 (5 футов 11 дюймов) | 190 | 11 |
мужской | 5,58 (5 футов 7 дюймов) | 170 | 12 |
мужской | 5,92 (5 футов 11 дюймов) | 165 | 10 |
женский | 5 | 100 | 6 |
женский | 5,5 (5 футов 6 дюймов) | 150 | 8 |
женский | 5,42 (5 футов 5 дюймов) | 130 | 7 |
женский | 5,75 (5 футов 9 дюймов) | 150 | 9 |
Классификатор, созданный на основе обучающего набора с использованием предположения о распределении Гаусса, будет иметь вид (учитывая, что дисперсии являются несмещенными выборочными дисперсиями ):
Человек | среднее (высота) | дисперсия (высота) | среднее (вес) | дисперсия (вес) | среднее значение (размер стопы) | отклонение (размер стопы) |
---|---|---|---|---|---|---|
мужской | 5.855 | 3.5033 × 10 −2 | 176.25 | 1.2292 × 10 2 | 11.25 | 9.1667 × 10 −1 |
женский | 5.4175 | 9.7225 × 10 −2 | 132.5 | 5.5833 × 10 2 | 7.5 | 1.6667 |
В следующем примере предполагается, что классы равновероятны, так что P(мужской) = P(женский) = 0,5. Это априорное распределение вероятностей может быть основано на предварительном знании частот в большей популяции или в обучающем наборе.
Тестирование
[ редактировать ]Ниже приведен образец, который можно отнести к мужскому или женскому полу.
Человек | рост (футы) | вес (фунты) | размер стопы (дюймы) |
---|---|---|---|
образец | 6 | 130 | 8 |
Чтобы классифицировать образец, необходимо определить, какая задняя часть больше: самец или самка. Для классификации мужского пола задняя часть определяется выражением
Для классификации как женщины задняя часть определяется как
Доказательство (также называемое нормализующей константой) может быть рассчитано:
Однако, учитывая выборку, доказательства являются постоянными и, таким образом, одинаково масштабируют обе апостериорные области. Поэтому он не влияет на классификацию и его можно игнорировать. Теперь можно определить распределение вероятностей для пола выборки: где и — параметры нормального распределения, которые были предварительно определены из обучающей выборки. Обратите внимание, что здесь допустимо значение больше 1 — это плотность вероятности, а не вероятность, поскольку высота — непрерывная переменная.
Поскольку задний числитель больше в случае женщины, прогнозируется, что выборка будет женщиной.
Классификация документов
[ редактировать ]Вот проработанный пример наивной байесовской классификации проблемы классификации документов . Рассмотрим задачу классификации документов по их содержанию, например на спамовые и неспамовые электронные письма . Представьте, что документы взяты из нескольких классов документов, которые можно смоделировать как наборы слов, где (независимая) вероятность того, что i-е слово данного документа встречается в документе из класса C, можно записать как
(При таком подходе все еще больше упрощается, если предположить, что слова распределены в документе случайным образом, то есть слова не зависят от длины документа, положения внутри документа по отношению к другим словам или другого контекста документа. )
Тогда вероятность того, что данный документ D содержит все слова , учитывая класс C , является
Вопрос, на который необходимо ответить: «Какова вероятность того, что данный документ D принадлежит данному классу C ?» Другими словами, что такое ?
Теперь по определению и
Теорема Байеса превращает их в формулировку вероятности с точки зрения правдоподобия .
Предположим на мгновение, что существует только два взаимоисключающих класса, S и ¬ S (например, спам и не спам), так что каждый элемент (электронное письмо) принадлежит либо к одному, либо к другому; и
Используя приведенный выше байесовский результат, можно написать:
Деление одного на другое дает:
Что можно перефакторизовать как:
Таким образом, отношение вероятностей p( S | D )/p(¬ S | D ) может быть выражено через ряд отношений правдоподобия . Фактическая вероятность p( S | D ) может быть легко вычислена из log (p( S | D ) / p(¬ S | D )) на основе наблюдения, что p( S | D ) + p(¬ S | D ) = 1.
Логарифмируя все эти отношения , получаем:
(Этот метод « логарифмических отношений правдоподобия » является распространенным методом в статистике. В случае двух взаимоисключающих альтернатив (таких как этот пример) преобразование логарифмического отношения правдоподобия в вероятность принимает форму сигмовидной кривой : см. в logit подробности .)
Наконец, документ можно классифицировать следующим образом. Это спам, если (т.е. ), иначе это не спам.
См. также
[ редактировать ]- ДВЕРЬ
- классификатор Байеса
- Байесовская фильтрация спама
- Байесовская сеть
- Случайный наивный Байес
- Линейный классификатор
- Логистическая регрессия
- Персептрон
- Эвристика «Возьми лучшее»
Ссылки
[ редактировать ]Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( Май 2009 г. ) |
- ^ МакКаллум, Эндрю. «Графические модели, Лекция 2: Представление байесовской сети» (PDF) . Архивировано (PDF) из оригинала 9 октября 2022 г. Проверено 22 октября 2019 г.
- ^ Jump up to: а б Рассел, Стюарт ; Норвиг, Питер (2003) [1995]. Искусственный интеллект: современный подход (2-е изд.). Прентис Холл. ISBN 978-0137903955 .
- ^ Jump up to: а б с Хенд, диджей; Ю, К. (2001). «Идиотский Байес — не такой уж и глупый?». Международный статистический обзор . 69 (3): 385–399. дои : 10.2307/1403452 . ISSN 0306-7734 . JSTOR 1403452 .
- ^ Чжан, Гарри. Оптимальность наивного Байеса (PDF) . Конференция FLAIRS2004.
- ^ Каруана, Р.; Никулеску-Мизил, А. (2006). Эмпирическое сравнение алгоритмов обучения с учителем . Учеб. 23-я Международная конференция по машинному обучению. CiteSeerX 10.1.1.122.5901 .
- ^ «Почему наивный байесовский метод работает лучше, когда количество функций >> размер выборки по сравнению с более сложными алгоритмами машинного обучения?» . Обмен стеками с перекрестной проверкой . Проверено 24 января 2023 г.
- ^ Нарасимха Мурти, М.; Сушила Деви, В. (2011). Распознавание образов: алгоритмический подход . ISBN 978-0857294944 .
- ^ Jump up to: а б Джон, Джордж Х.; Лэнгли, Пэт (1995). Оценка непрерывных распределений в байесовских классификаторах . Учеб. Одиннадцатая конф. О неопределенности в искусственном интеллекте. Морган Кауфманн. стр. 338–345. arXiv : 1302.4964 .
- ^ Jump up to: а б с МакКаллум, Эндрю; Нигам, Камаль (1998). Сравнение моделей событий для текстовой классификации Наивного Байеса (PDF) . Семинар AAAI-98 по обучению категоризации текста. Том. 752. Архивировано (PDF) из оригинала 9 октября 2022 г.
- ^ Мецис, Вангелис; Андрутсопулос, Ион; Палиурас, Георгиос (2006). Фильтрация спама с помощью наивного байесовского метода — какой именно наивный байесовский метод? . Третья конференция по электронной почте и борьбе со спамом (CEAS). Том. 17.
- ^ Пирионеси, С. Маде; Эль-Дираби, Тамер Э. (01.06.2020). «Роль анализа данных в управлении инфраструктурными активами: преодоление проблем с размером и качеством данных». Журнал транспортной техники, Часть B: Тротуары . 146 (2): 04020022. doi : 10.1061/JPEODX.0000175 . S2CID 216485629 .
- ^ Хасти, Тревор. (2001). Элементы статистического обучения: интеллектуальный анализ данных, логические выводы и прогнозирование: с 200 полноцветными иллюстрациями . Тибширани, Роберт, Фридман, Дж. Х. (Джером Х.). Нью-Йорк: Спрингер. ISBN 0-387-95284-5 . OCLC 46809224 .
- ^ Jump up to: а б Ренни, Дж.; Ши, Л.; Тиван, Дж.; Каргер, Д. (2003). Устранение плохих предположений наивных классификаторов Байеса (PDF) . ИКМЛ. Архивировано (PDF) из оригинала 9 октября 2022 г.
- ^ Jump up to: а б Нигам, Камаль; МакКаллум, Эндрю; Трун, Себастьян; Митчелл, Том (2000). «Учимся классифицировать текст из маркированных и немаркированных документов с помощью EM» (PDF) . Машинное обучение . 39 (2/3): 103–134. дои : 10.1023/А:1007692713085 . S2CID 686980 . Архивировано (PDF) из оригинала 9 октября 2022 г.
- ^ Никулеску-Мизил, Александру; Каруана, Рич (2005). Прогнозирование хороших вероятностей с помощью обучения с учителем (PDF) . ИКМЛ. дои : 10.1145/1102351.1102430 . Архивировано из оригинала (PDF) 11 марта 2014 г. Проверено 24 апреля 2016 г.
- ^ Риш, Ирина (2001). Эмпирическое исследование наивного классификатора Байеса (PDF) . Семинар IJCAI по эмпирическим методам в искусственном интеллекте. Архивировано (PDF) из оригинала 9 октября 2022 г.
- ^ Jump up to: а б Нг, Эндрю Ю .; Джордан, Майкл И. (2002). О дискриминативных и генеративных классификаторах: сравнение логистической регрессии и наивного Байеса . НИПС . Том. 14.
Дальнейшее чтение
[ редактировать ]- Домингос, Педро; Паццани, Майкл (1997). «Об оптимальности простого байесовского классификатора при потерях ноль-единица» . Машинное обучение . 29 (2/3): 103–137. дои : 10.1023/А:1007413511361 .
- Уэбб, Дж.И.; Боутон, Дж.; Ван, З. (2005). «Не такой уж наивный Байес: агрегирование оценщиков с одной зависимостью» . Машинное обучение . 58 (1): 5–24. дои : 10.1007/s10994-005-4258-6 .
- Мозина, М.; Демсар, Дж.; Каттан, М.; Зупан, Б. (2004). Номограммы для визуализации наивного байесовского классификатора (PDF) . Учеб. ПКДД-2004. стр. 337–348.
- Марон, Мэн (1961). «Автоматическое индексирование: экспериментальное исследование». Журнал АКМ . 8 (3): 404–417. дои : 10.1145/321075.321084 . hdl : 2027/uva.x030748531 . S2CID 6692916 .
- Минский, М. (1961). Шаги к искусственному интеллекту . Учеб. ИРЭ. Том. 49. стр. 8–30.