Рекомендательные системы: теорема Байеса и наивный байесовский классификатор

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

    image

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

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

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

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

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

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

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

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

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

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

    В следующей серии мы усложним этот пример и рассмотрим модель LDA, которая способна выделять темы в корпусе документов безо всякого набора отмеченных документов, причём так, что один документ сможет содержать несколько тем, а также применим её к задаче рекомендаций.
    • +19
    • 43,4k
    • 9
    Surfingbird 60,64
    Компания
    Поделиться публикацией
    Похожие публикации
    Комментарии 9
    • 0
      Изложено доступно. Но это как конспект открыл свой, ощущение, что именно это изложение я где-то уже читал, хотя это может только ощущение. Наверное в математике всегда так — если поймешь модель и ее синопсис, то многие вещи становятся «похожими».
      • 0
        Некоторые предложения про наивный байес прямо из моих лекций взяты; про саму теорему я тоже не в первый раз пишу, не исключено, что начинаю повторяться. :)
      • 0
        Подписался. Спасибо.
        • +1
          Вот еще лекция на этот счет от школы анализа данных (яндекс): shad.yandex.ru/lectures/machine_learning.xml (вторая лекция).
          • 0
            Было бы еще интересно услышать про NLP-методы, позволяющие понимать структуру предложения в т.ч. сарказм. Т.е. например, есть ли методы, позволяющие корректно классифицировать предложение «это был бы потрясающий ресторан, если бы там было недорого, вкусно и атмосферно» как негативное. bag of words модель здесь, скорее всего, выдаст позитивную классификацию.
            • 0
              Я бы обязательно написал отличный текст про распознавание сарказма, если бы что-нибудь в этом понимал и если бы это было по теме блога. ;)
              • 0
                Я, если честно, не обратил внимания, что это блог компании и подумал, что это просто цикл статей по машинному обучению.
                • 0
                  Это задумывалось как цикл статей по рекомендательным системам. Эта конкретная запись пообщее вышла, но я надеюсь уже в следующей части вернуться к теме.
                  • 0
                    Нет-нет, вышло замечательно. Пишите, доступно для восприятия, даже если это и отклоняется от общей линии темы.

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

            Самое читаемое