Наивный Байес

Прежде чем перевести страницу, проверить орфографию или показать результаты поиска, программа должна понять, на каком языке текст. Самый простой способ, который при этом работает, — посчитать. Возьмём по 1500 предложений на каждом из четырнадцати языков и запомним, сколько раз в каждом языке встретилось каждое сочетание из трёх букв подряд — триграмма. Чтобы определить язык нового текста, перемножим частоты его триграмм в каждом языке и выберем язык, где произведение больше. Это наивный Байес. Напишите что-нибудь сами или возьмите пример.

В примере белорусская фраза, и ближайший соперник — русский. Подсветка показывает, кто за кого. «Лі» в конце слова, «пад» и «і·п» — за белорусский: в русских предложениях такие сочетания почти не встречаются. Окончание «-ему» тянет к русскому, но таких улик меньше, и они слабее. Русский отстаёт на 38,6 — это разность логарифмов, а в разах шансы русского меньше в e^38,6 ≈ 6·10¹⁶. На 2800 предложениях проверки, которых модель не видела, она угадывает 2780, то есть 99,29 %. Кнопка «где ошибается» показывает оставшиеся двадцать: почти все — короткие фразы, чаще всего украинские, принятые за русские.

Идея

Нам нужна вероятность того, что текст x написан на языке L. Формула Байеса переворачивает её в то, что можно оценить по данным:

Знаменатель одинаков для всех языков, и при сравнении его можно не считать. P(L) — априорная вероятность языка: у нас по 1500 предложений на язык, и она у всех одна и та же. Остаётся P(x | L) — вероятность увидеть именно этот текст, если он на языке L. Её по данным не оценить: этой фразы в обучении, скорее всего, нет. Поэтому делают наивное допущение: текст — это последовательность триграмм, и при известном языке каждая выбирается независимо от соседних. Тогда

а каждую P(g | L) оценивает подсчёт: сколько раз триграмма g встретилась в текстах языка L, делённое на число всех их триграмм. Повторяющаяся триграмма входит в произведение столько раз, сколько встречается в тексте, — такую модель называют мультиномиальной.

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

Допущение заведомо неверно: соседние триграммы делят две буквы из трёх, и за «вже» в тексте может идти только триграмма, которая начинается с «же», а вовсе не любая. Почему модель с таким допущением угадывает 99 % языков, разобрано ниже. Сначала — два места, где формула ломается, если запрограммировать её буквально.

Ноль и сглаживание

Триграмма, которой не было в обучении языка, получает вероятность 0 и обнуляет всё произведение. Достаточно одного редкого слова, имени или опечатки, чтобы язык исключили, сколько бы улик за него ни было. А если такая триграмма найдётся у каждого языка, ответа нет вовсе.

Лечится это сглаживанием Лапласа: к каждому счётчику прибавляют α, будто каждую триграмму словаря видели ещё α раз,

где c_L(g) — сколько раз язык видел триграмму, N_L — сколько всего триграмм в его текстах, а V — сколько разных триграмм во всём обучении, 25 155. Знаменатель растёт ровно настолько, чтобы вероятности по-прежнему давали в сумме единицу. Незнакомая триграмма теперь стоит дорого, но конечно.

Без сглаживания 928 предложений из 2800 — треть — получают ноль у всех четырнадцати языков, и угадано только 1856. С любым α > 0 угадано от 2755 до 2780: при α = 0,001 — 2773, при α = 1 — 2780, при α = 10 — 2755. Важно, чтобы прибавка была, а насколько она велика, почти не важно, пока она не начинает заглушать сами счётчики.

Правило прибавлять единицу придумал Лаплас для задачи, которую сам считал скорее упражнением: какова вероятность, что солнце взойдёт завтра, если оно всходило каждый из n дней? Его ответ — (n + 1)/(n + 2): будто к наблюдениям добавили один восход и один невосход. В «Опыте философии теории вероятностей» 1814 года он взял пять тысяч лет, 1 826 213 дней, и получил шансы 1 826 214 к одному.

Логарифмы вместо произведения

Вторая беда — само произведение. Средняя триграмма русского текста имеет вероятность порядка 10^−3,4, и произведение теряет больше трёх десятичных порядков на каждой букве. Наименьшее положительное число double — около 4,9·10⁻³²⁴. Нижний график сцены показывает, что происходит: на 97-й триграмме произведение становится ровно нулём, и дальше все языки равны. Сто букв — это одно-два предложения.

Логарифм превращает произведение в сумму, а сумма логарифмов теряет на каждой букве всего семь-восемь единиц. Вероятность 6276 символов русских предложений проверки — 10^−21 386, и это число спокойно хранится как −49 243,8. Сравнивать языки можно прямо по суммам: логарифм возрастает, и больше сумма — больше вероятность.

6276 characters of Russian: the product of probabilities is 0 from trigram 97 on; the sum of logarithms is -49243.8, that is 10^-21386.3

Код

Обучение — это словарь счётчиков на каждый язык. Ответ — для каждого языка сумма log(c + α) − log(N_L + αV) по триграммам текста плюс логарифм априорной вероятности. Тексты в файле уже очищены: строчные буквы и пробелы вместо всего остального, — поэтому Python и Go режут на триграммы одни и те же символы. В Go текст режется по рунам, а не по байтам: кириллическая буква занимает в UTF-8 два байта.

«ти вже попоїла»: ukr -109.06, bul -125.70, rus -126.55
«ты уже поела»: rus -90.57, bel -106.20, ukr -110.49
«мы не забылі»: bel -86.50, rus -93.95, kaz -107.58

Украинская и русская фразы об одном и том же различаются буквами «и» и «ы», «ї», словами «вже» и «уже», и у каждой отрыв от ближайшего соперника больше пятнадцати единиц логарифма. Белорусская «мы не забылі» почти целиком состоит из триграмм, обычных и для русского, и выдают её последние буквы «лі»: отрыв 7,45, и это всё ещё шансы примерно в 1700 раз.

Почему наивное допущение работает

Возьмём два языка, A и B, и посмотрим на разность их логарифмов. Каждая триграмма g текста прибавляет log P(g | A) − log P(g | B), и столько раз, сколько встречается.

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

Для выбора класса это редко важно: решает знак суммы, а двойной счёт улик раздувает сумму, но знак меняет нечасто. Педро Домингос и Майкл Паццани в 1997 году разобрали это строго: наивный Байес выбирает лучший класс в гораздо более широком круге задач, чем те, где признаки действительно независимы. А вот вероятности он называет неправильные — слишком уверенные.

Когда модель уверена на 99,99 % и больше — а так у 2618 предложений из 2800, — она права всегда. Но среди тех, где она говорит «от 90 до 99 %», в среднем 96,6 %, верных ответов только 79,5 %. Причину мы знаем: соседние триграммы делят две буквы, и каждая буква голосует почти трижды. Поделим логарифмы на два, как будто независимых улик вдвое меньше, — сдвиньте T. Уверенность в той же корзине станет 96,3 %, а точность — 99,1 %: поправка грубая, теперь модель даже скромнее, чем следовало бы. Но ни один ответ при этом не изменился: все суммы поделены на одно и то же число, и порядок языков прежний.

T = 1: confidence   texts  said     right
  0.0000-0.9000     36   73.931%   69.44%
  0.9000-0.9900     39   96.557%   79.49%
  0.9900-0.9990     47   99.649%   97.87%
  0.9990-0.9999     60   99.960%  100.00%
  0.9999-1.0000   2618  100.000%  100.00%

Отсюда практическое правило. Если нужен только ответ — какой язык, спам или нет, — наивный Байес хорош и дёшев. Если нужна сама вероятность — например, чтобы решать, что делать с письмом, которое спам с вероятностью 95 %, — его вероятностям верить нельзя: в 2005 году Никулеску-Мизил и Каруана на восьми задачах показали, что он сдвигает вероятности к 0 и 1. Тогда его выход калибруют отдельно или берут логистическую регрессию. Эндрю Ын и Майкл Джордан в 2001 году сравнили эту пару и теоретически, и на данных: наивный Байес быстрее выходит на свой предел точности и выигрывает, когда примеров мало, а логистическая регрессия на больших данных обычно приходит к меньшей ошибке.

Сколько это стоит

Обучение — один проход по текстам: O(N) для N символов, на каждую триграмму одна операция со словарём. Память — по счётчику на каждую пару «язык, триграмма», которая хоть раз встретилась; это заметно меньше, чем 25 155 × 14, потому что большинство триграмм бывает в немногих языках. Ответ на текст из m символов — L·m обращений к словарю и логарифмов для L языков; логарифмы можно посчитать заранее и хранить вместо счётчиков. Время растёт линейно с длиной текста:

Из того, что модель — это счётчики, следует свойство, которого нет у большинства других методов: её можно дообучать и разобучать по одному примеру. Пользователь отметил письмо как спам — прибавить его слова к счётчикам спама; ошибся и отменил — вычесть. Ни пересчёта, ни прохода по старым данным. Так работают почтовые фильтры, которые подстраиваются под письма конкретного человека; об этом вторая задача статьи. Единственная тонкость — V, число разных признаков в словаре: оно меняется, когда признак появляется впервые или пропадает совсем, и его тоже надо поддерживать.

Где работает

Самая известная история наивного Байеса — спам. В 1998 году Мехран Сахами, Сьюзан Дюмэ, Дэвид Хекерман и Эрик Хорвиц описали байесовский фильтр нежелательной почты по словам письма. Широко известным подход стал после эссе Пола Грэма «A Plan for Spam» в 2002 году: по его словам, на его собственной почте слегка доработанный байесовский фильтр пропускал меньше 5 спамовых писем из 1000 и не отправил в спам ни одного нужного. Строго говоря, Грэм комбинировал вероятности слов по-своему, и спорили, насколько его метод байесовский; но вслед за эссе появились фильтры, которые прямо следовали ему, например SpamBayes.

Спамеры ответили атакой на само сложение улик: стали дописывать в письма слова, обычные для нормальной почты. Дэниел Лоуд и Кристофер Мик в 2005 году измерили, сколько это стоит: без доступа к фильтру достаточно добавить не больше 150 таких слов, чтобы половина спама, который фильтр задерживал, прошла сквозь него, а если можно проверять письма на самом фильтре — хватает 30. Это верно и для наивного Байеса, и для логистической регрессии: обе модели складывают улики линейно. Помогает частое дообучение: фильтр, который учится на свежих письмах, узнаёт и новые «хорошие» слова спамеров.

Определение языка по n-граммам символов — вторая классическая задача. Библиотека language-detection Накатани Сюё 2010 года — наивный Байес по сочетаниям от одной до трёх букв; по слайдам автора, она различала 49 языков с точностью выше 99 %. А в scikit-learn есть MultinomialNB — ровно та модель, что в листинге, со сглаживанием α = 1 по умолчанию; его часто берут первым, чтобы понять, сколько вообще можно выжать из текстов, прежде чем браться за модели посложнее.

История

Работу Томаса Байеса, где появилась формула обратной вероятности, нашёл в его бумагах после его смерти Ричард Прайс и опубликовал в 1763 году; общий вид ей придал Лаплас в 1774 году. Классифицировать тексты по формуле Байеса первым, по-видимому, пробовал Мелвин Марон: в 1961 году его программа относила аннотации статей о вычислительной технике к 32 рубрикам по встретившимся в них словам-подсказкам. Через два года Фредерик Мостеллер и Дэвид Уоллес применили байесовский подход к спору об авторстве: двенадцать статей «Федералиста» 1787–1788 годов приписывали и Александру Гамильтону, и Джеймсу Мэдисону. Мостеллер и Уоллес смотрели не на темы, а на служебные слова, которые пишущий выбирает не задумываясь, — upon, whilst и другие, — и пришли к выводу, что все двенадцать статей написал Мэдисон.

Задачи

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