Что называется статистикой. Наивный байесовский классификатор документов в Excel

Самое распространенное применение наивного Байеса - классификация документов. Является ли это электронное письмо спамом или наоборот, долгожданной новостью? Эта запись в Twitter - благодушная или сердитая? Нужно ли передавать этот перехваченный звонок по сотовому для дальнейшего исследования федеральным агентам? Вы предоставляете «данные для обучения», например, классифицированные примеры документов, обучающему алгоритму, который в дальнейшем сможет «разбить» новые документы на те же категории, используя имеющиеся знания.

Самый распространенный подход к классификации документов - это использование модели набор слов в сочетании с наивным байесовским классификатором. Модель набор слов воспринимает документ как беспорядочное множество слов. «Джонни съел сыр» для него то же самое, что «сыр съел Джонни» - и то и другое состоит из одного и того же множества слов: {«Джонни», «съел», «сыр»}.

Скачать заметку в формате или , примеры в формате

Небольшое введение в теорию вероятностей. Выражение р() используется для обозначения вероятности. Например, р(А) = 0, 2 означает, что событие А произойдет с вероятностью 20%. Выражения, типа р(А|B) используются для обозначения условных вероятностей. Например, р(А|B) = 0,3 означает, что вероятность события А, при условии, что случилось событие В, составляет 30%. Совместная вероятность р(А, B) используется для обозначения вероятности того, что события А и В произойдут одновременно. Если события А и В независимы, то р(А, B) = р(А) * р(B). Если события А и В зависимы, то р(А, B) = р(А) * р(B|A).

В качестве примера мы изучаем твиты о сервисе для отправки электронных писем – Mandrill.com . При поиске по ключевому слову – mandrill – помимо полезных, появляются также ссылки, не имеющие отношения к делу. Наша задача – отфильтровать релевантные твиты. Допустим, ранее мы накопили базу, включающую 300 твитов: 150 – о приложении Mandrill.com, и 150 – других.

Каждый твит мы разбиваем на отдельные слова (называемые жетонами - token ). Нам важны две вероятности:

р (приложение | слово1, слово2 …)
р (другое | слово1, слово2, …)

Это вероятность того, что твит либо о приложении, либо о чем-то другом, при том, что мы обнаруживаем слова: «слово1», «слово2» и т.д.

(1) р (приложение | слово1, слово2, …) > р (другое | слово1, слово2, …)

то данный твит - о Mandrill.com. Но как же вычислить эти вероятности? Первый шаг - использование теоремы Байеса, которая позволяет переписать условную вероятность приложения как:

Точно так же

Подставив (2) и (3) в (1) и умножив обе части на р(слово1, слово2, …) , получим условие (1) в виде:

(4) р(прилож.) * р(слово1,слово2,…| прилож.) > р(другое) * р(слово1,слово2,…| другое)

Применяемое для анализа правило апостериорного максимума (МАР) позволяет, во-первых, не обращать внимание на различие значений р (прилож.) и р (другое), а во-вторых, считать вероятности вхождения слов в твит независимыми (хотя это и не так!), и заменить:

р(слово1,слово2,…| прилож.) –> р(слово1| прилож.) * р(слово2| прилож.) * …
р(слово1,слово2,…|другое) –>

В окончательном виде мы будем сравнивать две величины:

(5) р(слово1| прилож.) * р(слово2| прилож.) * … > р(слово1|другое) * р(слово2|другое) * …

Предположение о независимости позволяет разбить совместную условную вероятность набора слов при известном классе на вероятности нахождения каждого слова в данном классе. Считая слова независимыми, мы вносим в алгоритм МАР множество ошибок, но, в конце концов, они не влияют на правильность выбора между набором, относящимся к приложению и другими твитам.

Осталось решить две проблемы: что делать с редкими словами, и как победить исчезающе малые величины, появляющиеся при перемножении большого числа вероятностей, близких к нулю? Принято добавлять единицу к каждому значению (даже нулевому). Это называется дополнительным сглаживанием и часто используется для приспособления неведомых ранее слов к модели наборов слов. А вместо умножения используется сложение логарифмов. Например, у вас есть произведение: 0,2 * 0,8. Прологарифмируйте его: ln(0,2 * 0,8) = ln(0,2) + ln(0,8).

Итак, все объяснения даны, и можно перейти к Excel. На первых двух листах книги с примерами содержатся по 150 твитов, относящихся к приложению Mandrill.com (рис. 1) и к другим темам. Последовательно в оригинальном тексте твитов все буквы заменяются на строчные, а затем знаки препинания – на пробелы. Например, формула в ячейке Е2 =ПОДСТАВИТЬ(D2;»?»;» «) – заменяет в тексте, содержащемся в ячейке D2, все знаки вопроса на пробелы.

Рис. 1. Удаление лишних знаков в базе твитов о приложении (чтобы увеличить изображение, кликните на нем правой кнопкой мыши, и выберите Открыть картинку в новой вкладке )

Теперь нам необходимо сосчитать, сколько раз каждое слово используется в записях данной категории. Для этого нужно собрать все слова из твитов каждой базы в одном столбце. Предполагая, что каждый твит содержит не более 30 слов, и собираясь присвоить каждому жетону отдельную строку, вам понадобится 150 * 30 = 4500 строк. Создайте новый лист, назовите его Жетоны_прил. Назовите ячейку А1 Твиты . Скопируйте в буфер значения Н2:Н151 с листа Приложение. Выделите на листе Жетоны_прил. область А2:А4501 и кликните Вставить –> Специальная вставка –> значения (рис. 2). Нажмите Ok. Обратите внимание: так как вы вставляете 150 твитов в 4500 строк, Excel повторяет все за вас. Это означает, что если вы выделите первое слово из первого твита в строке 2, этот самый твит повторится для выделения второго слова в строке 152, третьего - в 302 и т.д.

Изучите формулы в столбцах В:D листа Жетоны_прил. , чтобы понять механику последовательного извлечения жетонов из твита (рис. 3). Аналогично создайте лист Жетоны_др. для базы твитов, не относящихся к приложению Mandrill.com.

Рис. 3. Фрагмент листа Жетоны_прил., на котором извлекаются жетоны из базы данных твитов, относящихся к приложению Mandrill.com

Теперь на базе листа Жетоны_прил. следует создать сводную таблицу, которая подсчитает число вхождений каждого жетона. С помощью фильтра сводной таблицы исключите слова длиною до 4 символов, а также добавьте столбцы для подсчета логарифма частоты вхождения жетона (рис. 4). Повторите операцию для листа Жетоны_др.

Теперь, когда модель классификатора «обучена», настало время ее использовать. На листе Тест размещены 20 твитов, которые нужно классифицировать. Они также обработаны (как и на рис. 1). Поместим подготовленные твиты на лист Классификация . Выделите D2:D21 и выберите ДАННЫЕ –> Текст по столбцам . В появившемся окне выберите С разделителями и нажмите Далее . На втором шаге выберите знаки табуляции и пробела в качестве разделителей, а также Считать последовательные разделители одним (рис. 5). Ограничитель строк установите (нет) . Нажмите Далее . На последнем шаге Формат данных столбца установите общий . Нажмите Готово .

Процедура разбросает твиты по столбцам всего листа до столбца AI (рис. 6).

Теперь с помощью функции ВПР извлечем данные о логарифмах вероятностей вхождения тестовых жетонов в два набора данных (приложение / другие). Сравним суммы, и сделаем вывод о принадлежности тестов к тому или иному классу (рис. 7). Выделены цветом твиты, разность логарифмов по которым менее 1. Подробнее с формулами можно ознакомиться на листе Классификация.

Вот и все. Модель построена, предположения сделаны.

Написано по материалам книги Джона Формана . – М.: Альпина Паблишер, 2016. – С. 101–128

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

Теорему Байеса или помнит, или тривиально может вывести любой, кто проходил хоть самый-самый базовый курс теории вероятностей. Помните, что такое условная вероятность события x при условии события y ? Прямо по определению: , где - это совместная вероятность x и y , а p (x ) и p (y ) - вероятности каждого события по отдельности. Значит, совместную вероятность можно выразить двумя способами:
.

Ну, вот вам и теорема Байеса:

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

А теперь давайте соотнесём это с типичной задачей машинного обучения. Здесь D - это данные, то, что мы знаем, а θ - это параметры модели, которые мы хотим обучить. Например, в модели SVD данные - это те рейтинги, которые ставили пользователи продуктам, а параметры модели - факторы, которые мы обучаем для пользователей и продуктов.

Каждая из вероятностей тоже имеет свой смысл. - это то, что мы хотим найти, распределение вероятностей параметров модели после того, как мы приняли во внимание данные; это называется апостериорной вероятностью (posterior probability). Эту вероятность, как правило, напрямую не найти, и здесь как раз и нужна теорема Байеса. - это так называемое правдоподобие (likelihood), вероятность данных при условии зафиксированных параметров модели; это как раз найти обычно легко, собственно, конструкция модели обычно в том и состоит, чтобы задать функцию правдоподобия. А - априорная вероятность (prior probability), она является математической формализацией нашей интуиции о предмете, формализацией того, что мы знали раньше, ещё до всяких экспериментов.

Здесь, наверное, не время и не место в это углубляться, но заслуга преподобного Томаса Байеса была, конечно, не в том, чтобы переписать в две строчки определение условной вероятности (не было тогда таких определений), а как раз в том, чтобы выдвинуть и развить такой взгляд на само понятие вероятности. Сегодня «байесовским подходом» называют рассмотрение вероятностей с позиций скорее «степеней доверия», чем фриквентистской (от слова frequency, а не freak!) «доли успешных экспериментов при стремлении к бесконечности общего числа экспериментов». В частности, это позволяет рассуждать о вероятностях одноразовых событий - ведь на самом деле нет никакого «стремящегося к бесконечности числа экспериментов» для событий вроде «Россия станет чемпионом мира по футболу в 2018 году» или, ближе к нашей теме, «Васе понравится фильм «Трактористы»»; тут скорее как с динозавром: или понравится, или нет. Ну а математика, конечно, при этом везде одна и та же, колмогоровским аксиомам вероятности всё равно, что о них думают.

Для закрепления пройденного - простой пример. Рассмотрим задачу категоризации текстов: например, предположим, что мы пытаемся рассортировать по темам поток новостей на основе уже имеющейся базы данных с темами: спорт, экономика, культура… Мы будем использовать так называемую bag-of-words model: представлять документ (мульти)множеством слов, которые в нём содержатся. В результате каждый тестовый пример x принимает значения из множества категорий V и описывается атрибутами . Нам нужно найти наиболее вероятное значение данного атрибута, т.е.

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

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

Чтобы с этим справиться, наивный байесовский классификатор (naive Bayes classifier - его иногда даже называют idiot’s Bayes) предполагает условную независимость атрибутов при условии данного значения целевой функции:

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

Заметим, что наивный байесовский классификатор делает чертовски сильное предположение: в классификации текстов мы предполагаем, что разные слова в тексте на одну и ту же тему появляются независимо друг от друга. Это, конечно, полный бред - но, тем не менее, результаты получаются вполне приличные. На самом деле наивный байесовский классификатор гораздо лучше, чем кажется. Его оценки вероятностей оптимальны, конечно, только в случае настоящей независимости; но сам классификатор оптимален в куда более широком классе задач, и вот почему. Во-первых, атрибуты, конечно, зависимы, но их зависимость одинакова для разных классов и «взаимно сокращается» при оценке вероятностей. Грамматические и семантические зависимости между словами одни и те же и в тексте про футбол, и в тексте о байесовском обучении. Во-вторых, для оценки вероятностей наивный байес очень плох, но как классификатор гораздо лучше (обычно, если даже на самом деле и , наивный байес выдаст и , но классификация при этом будет чаще правильная).

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

«Есть три вида лжи: ложь,
наглая ложь и статистика».
Марк Твен

Статистика - это не заумные формулы и абстрактные выводы, это то, что имеет непосредственное отношение к реальной жизни и помогает принимать важные решения. Статистика вездесуща, начиная с вероятности выиграть в лотерею заканчивая прогнозной полицией. Хол Вариан, главный экономист компании Google, в интервью Нью-Йорк Таймс сказал, что в следующем десятилетии работа со статистическими данными станет the sexy job.

Если измерять ваши продвижения в футах, то соответствующую последовательность можно описать как 1 + ½ + ¼ + ⅛ … Сколько бы вы ни продвигались таким способом к стене (а вы будете делать это до бесконечности), совокупное расстояние, пройденное вами, не может превышать 2 метров, то есть вашего исходного расстояния от стены. С математической точки зрения, совокупное расстояние, пройденное вами, можно приравнять к 2 метрам, что весьма удобно в плане вычислений. Математик сказал бы, что сумма бесконечного ряда 1 метр+ ½ метра+ ¼ метра + ⅛ метра… сходится к 2 метрам, то есть именно то, что пытался объяснить преподаватель.

Теперь, исходя из собственного опыта вы можете утверждать, что благодаря интуиции математика и другие технические детали становятся гораздо понятнее.

В фильме 2002 года Minority Report Том Круз играет детектива, предотвращающего преступления. Его герой является сотрудником некоего бюро, которое использует определенную технологию для прогнозирования преступлений еще до того, как они будут совершены. И это уже не фантастика. В 2011 году в газете The New York Times вышла статья под заголовком: «Полиция прибывает на место до совершения преступления». В ней рассказывалось, что специальная компьютерная программа предсказала высокую вероятность совершения краж из автомобилей в этот день на подземной парковке, расположенной в деловом районе города Санта-Круз. Когда туда приехали детективы, они обнаружили двух женщин, слишком уж пристально всматривающихся в окна автомобилей. Одна из них уже неоднократно задерживалась за воровство, а у другой нашли запрещенные наркотики.

Система, использовавшаяся в Санта-Круз, была разработана двумя математиками, антропологом и криминалистом. Отдел полиции в Чикаго создал у себя целое подразделение аналитиков-прогнозистов. Частично его формирование объяснялось тем, что банды, терроризировавшие город, действовали по определенным шаблонам.

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

Важным моментом в этом обсуждении является то, что корреляция не предполагает причинно-следственной связи: положительная или отрицательная корреляция между двумя переменными вовсе не обязательно означает, что изменения одной переменной вызывают изменения другой. Статистическая зависимость между A и B не доказывает, что A является причиной B. Вообще говоря, не исключено, что B - это причина A.

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

Другой вариант: дополнительные траты на школьное образование могут стимулировать экономический рост, что позволяет вкладывать больше средств в образование, то есть причинно-следственные связи могут носить двусторонний характер. Следовательно, мы не должны использовать объясняющие переменные, зависящие от исхода, который мы пытаемся объяснить, - в противном случае результаты могут оказаться безнадежно запутанными.

Концепция вероятности понятным языком

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

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

Кроме того, Caveon Test Security выявляет экзамены, в ходе которых экзаменуемые отвечают на сложные вопросы значительно лучше, чем на простые (в таком случае предполагается, что ответы им были известны заранее), или количество исправлений неправильного ответа на правильный существенно превышает количество исправлений правильного ответа на неправильный (в таком случае предполагается, что после экзамена преподаватель или экзаменатор подменил листы с ответами).

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

В книге «Голая статистика» автор постарался по возможности избегать употребления математических формул, уравнений и графиков. Статистика может быть действительно интересной и по большей части не так сложна, как кажется поначалу.

Фото обложки поста - .

P.S. Понравилось? Подписывайтесь на нашу рассылку. Раз в две недели мы будем присылать вам 10 лучших материалов из блога.