В статистике наивные классификаторы Байеса представляют собой семейство линейных « вероятностных классификаторов », которые предполагают , что признаки условно независимы, учитывая целевой класс. Сила (наивность) этого предположения и дала классификатору такое название. Эти классификаторы относятся к числу простейших моделей байесовских сетей . [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]
Сходимость определяется на основе улучшения правдоподобия модели , где обозначает параметры наивной байесовской модели.
Этот алгоритм обучения является примером более общего алгоритма максимизации ожидания (EM): шагом прогнозирования внутри цикла является E -шаг EM, а повторное обучение наивного байесовского алгоритма представляет собой M -шаг. Алгоритм формально обоснован предположением, что данные генерируются моделью смеси , а компоненты этой модели смеси являются в точности классами задачи классификации. [14]
Несмотря на то, что далеко идущие предположения о независимости часто бывают неточными, наивный классификатор Байеса обладает несколькими свойствами, которые делают его удивительно полезным на практике. В частности, разделение распределений условных признаков классов означает, что каждое распределение можно независимо оценить как одномерное распределение. Это помогает смягчить проблемы, возникающие из-за проклятия размерности , такие как необходимость в наборах данных, которые экспоненциально масштабируются в зависимости от количества объектов. Хотя наивный Байес часто не может дать хорошую оценку правильных вероятностей классов, [15] это может не быть требованием для многих приложений. Например, простой байесовский классификатор выполнит правильную классификацию по правилу принятия решений MAP, если правильный класс прогнозируется как более вероятный, чем любой другой класс. Это верно независимо от того, является ли оценка вероятности незначительной или даже крайне неточной. Таким образом, общий классификатор может быть достаточно надежным, чтобы игнорировать серьезные недостатки лежащей в его основе наивной вероятностной модели. [16] Другие причины наблюдаемого успеха наивного байесовского классификатора обсуждаются в цитируемой ниже литературе.
В случае дискретных входных данных (индикатор или частотные характеристики для дискретных событий) наивные байесовские классификаторы образуют генеративно-дискриминативную пару с классификаторами полиномиальной логистической регрессии : каждый наивный байесовский классификатор можно рассматривать как способ подбора вероятностной модели, которая оптимизирует совместное правдоподобие. , тогда как логистическая регрессия соответствует той же вероятностной модели для оптимизации условной . [17]
Более формально мы имеем следующее:
Теорема . Наивные байесовские классификаторы бинарных признаков включаются в состав классификаторов логистической регрессии.
Рассмотрим общую задачу мультиклассовой классификации с возможными классами , тогда (ненаивный) байесовский классификатор дает по теореме Байеса:
Наивный классификатор Байеса дает
Это и есть классификатор логистической регрессии.
Связь между ними можно увидеть, заметив, что функцию решения для наивного Байеса (в двоичном случае) можно переписать как «предсказать класс, если шансы превышают шансы «. Выражение этого в пространстве журнала дает:
Левая часть этого уравнения представляет собой логарифм шансов, или logit , величину, предсказанную линейной моделью, которая лежит в основе логистической регрессии. Поскольку наивный байесовский метод также является линейной моделью для двух «дискретных» моделей событий, его можно перепараметризовать как линейную функцию . Получение вероятностей тогда является вопросом применения логистической функции к или, в случае с несколькими классами, функции softmax .
Дискриминационные классификаторы имеют меньшую асимптотическую ошибку, чем генеративные; однако исследования Нг и Джордана показали, что в некоторых практических случаях наивный байесовский метод может превзойти логистическую регрессию, поскольку он быстрее достигает своей асимптотической ошибки. [17]
Задача: определить, является ли данный человек мужчиной или женщиной на основе измеренных характеристик. К характеристикам относятся рост, вес и размер стопы. Хотя в классификаторе NB мы рассматриваем их как независимые, на самом деле это не так.
Пример обучающего набора ниже.
Классификатор, созданный на основе обучающего набора с использованием предположения о распределении Гаусса, будет иметь вид (учитывая, что дисперсии являются несмещенными выборочными дисперсиями ):
В следующем примере предполагается, что классы равновероятны, так что P(мужской) = P(женский) = 0,5. Это априорное распределение вероятностей может быть основано на предварительном знании частот в большей популяции или в обучающем наборе.
Ниже приведен образец, который можно отнести к мужскому или женскому полу.
Чтобы классифицировать образец, необходимо определить, какая задняя часть больше: самец или самка. Для классификации мужского пола задняя часть определяется выражением
Для классификации как женщины задняя часть определяется как
Доказательство (также называемое нормализующей константой) может быть рассчитано:
Однако, учитывая выборку, доказательства являются постоянными и, таким образом, одинаково масштабируют обе апостериорные области. Поэтому он не влияет на классификацию и его можно игнорировать. Теперь можно определить распределение вероятностей для пола выборки:
где и – параметры нормального распределения, определенные ранее по обучающей выборке. Обратите внимание, что здесь допустимо значение больше 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.
Логарифмируя все эти отношения, получаем :
(Этот метод « логарифмических отношений правдоподобия » является распространенным методом в статистике. В случае двух взаимоисключающих альтернатив (таких как этот пример) преобразование логарифмического отношения правдоподобия в вероятность принимает форму сигмовидной кривой . : подробности см. в журнале .)
Наконец, документ можно классифицировать следующим образом. Это спам, если (т.е. ), в противном случае это не спам.