Продолжаем разговор. Прошлая статья была переходной от предыдущего цикла о графических моделях вообще (часть 1, часть 2, часть 3, часть 4) к новому мини-циклу о тематическом моделировании: мы поговорили о сэмплировании как методе вывода в графических моделях. А теперь мы начинаем путь к модели латентного размещения Дирихле (latent Dirichlet allocation) и к тому, как все эти чудесные алгоритмы сэмплирования применяются на практике. Сегодня – часть первая, в которой мы поймём, куда есть смысл обобщать наивный байесовский классификатор, и заодно немного поговорим о кластеризации.
Тематическое моделирование решает классическую задачу анализа текстов – как создать вероятностную модель большой коллекции текстов, которую затем можно будет использовать, например, для информационного поиска (information retrieval), классификации или, как в нашем случае, для рекомендаций контента. Мы уже говорили об одной из простейших моделей, пытающихся решить эту задачу – о широко известном наивном байесовском классификаторе. Можно, конечно, классифицировать тексты и по-другому – при помощи метода опорных векторов, например, или логистической регрессии, или любого другого классификатора – однако наивный Байес будет нам сейчас наиболее полезен как пример для дальнейшего обобщения.
В модели наивного байесовского классификатора каждому документу присваивается скрытая переменная, соответствующая его теме (взятой из заранее определённого дискретного набора, например «финансы», «культура», «спорт»), и слова условно независимы друг с другом при данной теме. Каждой теме соответствует дискретное распределение на словах, из которого они порождаются; мы просто предполагаем, что слова условно независимы при условии темы:
В результате каждая тема представляет собой дискретное распределение на словах. Можно представить себе огромный нечестный кубик, который вы кидаете, чтобы получить следующее слово, или мешок слов, в который вы не глядя запускаете руку, чтобы вытащить следующее. Нечестный мешок, правда, труднее представить – ну, скажем, каждое слово на камушках в мешке встречается по несколько раз, причём разные слова по-разному (вся эта интуиция нам ещё пригодится, bear with me for a moment). У вас есть один мешок, на котором написано «финансы», другой – «культура», третий – «спорт»:
И когда вы «генерируете» из этих мешков новый документ в наивном байесе, вы сначала выбираете мешок (кидая кубик), а потом из этого мешка начинаете выбирать слова одно за другим:
Графическая модель этого процесса выглядит очень просто (о том, как читать эти картинки, мы говорили в первой части предыдущего цикла, а во второй части даже был пример именно наивного байесовского классификатора). Слева – графическая модель полностью, в центре – модель одного документа с плашкой, которая скрывает повторяющиеся одинаковые переменные, а справа – та же модель, но для всего датасета, с явно выделенными переменными α и β, которые содержат параметры всех этих дискретных распределений:
Она тоже показывает, что наивный Байес состоит из одного дискретного распределения (кубика), которым определяется сравнительный «вес» тем, и нескольких дискретных распределений (мешков), по числу тем, которые показывают вероятности выпадения того или иного слова в теме.
А чтобы обучить наивный Байес (да и любой другой классификатор, тут уж никуда не денешься), нужно иметь размеченный набор текстов, на которых можно будет обучать эти распределения:
При обучении наивного Байеса мы для каждого документа знаем его тему, и остаётся обучить только распределение слов в каждой теме по отдельности и вероятности выпадения тем:
Для этого достаточно просто подсчитать, сколько раз то или иное слово встретилось в той или иной теме (и сколько раз темы встречаются в датасете), а результат сгладить по Лапласу.
У наивного байесовского классификатора видны сразу два направления, по которым его можно было бы расширить и улучшить:
Начать будет логично с первого направления, о том, как перейти к обработке датасетов без меток, ведь даже если мы сделаем модель, в которой у каждого документа несколько тем, разметить большой датасет руками, да ещё и на несколько тем для одного документа, будет крайне затруднительно. Итак, давайте представим, что у нас есть датасет, состоящий из текстов, и мы предполагаем, как и в наивном Байесе, что каждый документ был порождён из одной-единственной темы. Разница только в том, что теперь мы не знаем, из какой именно, и задача для нас выглядит так:
Давайте предполагать (мы и в LDA будем так делать; чтобы от этого избавиться, нужны непараметрические методы, до которых нам ещё далеко), что число потенциальных категорий (разных мешков со словами) нам известно, неизвестно только их содержание. Таким образом, вероятностная модель выглядит точно так же:
,
и распределения в ней всё те же. Разница только в том, что раньше мы при обучении знали для каждого документа его тему, а теперь не знаем. Иначе говоря, совместное распределение, из которого порождаются документы, всё то же: если обозначить через w вектор слов и через c категорию документа D, его общее правдоподобие будет
где βc – это распределение в мешке слов, соответствующем категории c; а общее правдоподобие, которое нужно максимизировать при обучении – это, соответственно,
и максимизировать его надо по-прежнему по α и βc. Но если раньше мы делали это при известных c, и задача максимизации разбивалась по отдельным темам и была в сущности тривиальной, то теперь надо максимизировать при неизвестных c, т.е. фактически взяв ожидание по ним:
Как это сделать?
То, что у нас получилось, на самом деле является совершенно стандартной задачей кластеризации: есть много объектов (текстов) в многомерном пространстве (слов), и нужно разбить их на отдельные классы так, чтобы тексты в одном классе были бы как можно более похожи друг на друга и при этом как можно менее похожи на тексты в других классах. Так что здесь может помочь стандартный инструмент обучения моделей кластеризации – EM-алгоритм (от слов Expectation-Maximization, сейчас поймёте почему). EM-алгоритм предназначен для ситуаций, когда в модели есть скрытые переменные (как у нас c), и нужно максимизировать правдоподобие модели по её параметрам (у нас это α и β), но в ожидании по скрытым переменным. EM-алгоритм сначала инициализирует модель какими-то начальными значениями, а затем итеративно повторяет два шага:
В нашем случае на Е-шаге мы просто находим вероятности того, что каждый документ принадлежит разным категориям, при фиксированных α и β:
А затем на М-шаге считаем эти вероятности принадлежности фиксированными и оптимизируем α и β (лучше со сглаживанием α0 и β0, соответствующим неким априорным распределениям на параметры α и β):
Затем это всё нужно повторить до тех пор, пока α и β не сойдутся; это и есть ЕМ-алгоритм для кластеризации, применённый к случаю дискретных атрибутов (слов в документах).
Общая идея того, почему EM-алгоритм, собственно, работает, такова: на каждом Е-шаге EM-алгоритм фактически строит вспомогательную функцию от параметров модели, которая в текущем приближении касается функции правдоподобия и при этом везде остаётся меньше неё (миноризует функцию правдоподобия). Вот картинка из одного из источников на эту тему (честно признаюсь, забыл, из какого именно):
А затем на М-шаге ЕМ-алгоритм находит параметры, максимизирующие эту вспомогательную функцию. Очевидно, что при этом мы переходим в точку, в которой общее правдоподобие увеличивается. Я не буду сейчас подробно углубляться в доказательство того, что EM-алгоритм действительно это всё делает и действительно корректно работает, нам важна только общая идея.
Сегодня мы сделали первый из двух шагов на пути от наивного байесовского классификатора к LDA: перешли от задачи классификации, в которой у каждого документа в обучающем датасете должна быть фиксированная категория, к задаче кластеризации, в которой документы не обязательно должны быть размечены по категориям. Отметим, кстати, что если у вас всё-таки размечена часть документов (это называется semi-supervised learning), это очень легко добавить в получившуюся модель. Нужно просто зафиксировать соответствующие переменные ci(D), сделать их равными единице в размеченной теме и нулю во всех остальных, и в рамках EM-алгоритма не обучать эти переменные, оставляя их значения фиксированными. Такой «посевной датасет» будет, кстати, очень полезен для дальнейшего обучения модели.
В следующий раз мы сделаем второй шаг на пути к латентному размещению Дирихле: от категорий, присваиваемых всему тексту целиком, перейдём к темам, которых в каждом документе может быть несколько.
Классификация: наивный Байес
Тематическое моделирование решает классическую задачу анализа текстов – как создать вероятностную модель большой коллекции текстов, которую затем можно будет использовать, например, для информационного поиска (information retrieval), классификации или, как в нашем случае, для рекомендаций контента. Мы уже говорили об одной из простейших моделей, пытающихся решить эту задачу – о широко известном наивном байесовском классификаторе. Можно, конечно, классифицировать тексты и по-другому – при помощи метода опорных векторов, например, или логистической регрессии, или любого другого классификатора – однако наивный Байес будет нам сейчас наиболее полезен как пример для дальнейшего обобщения.
В модели наивного байесовского классификатора каждому документу присваивается скрытая переменная, соответствующая его теме (взятой из заранее определённого дискретного набора, например «финансы», «культура», «спорт»), и слова условно независимы друг с другом при данной теме. Каждой теме соответствует дискретное распределение на словах, из которого они порождаются; мы просто предполагаем, что слова условно независимы при условии темы:
В результате каждая тема представляет собой дискретное распределение на словах. Можно представить себе огромный нечестный кубик, который вы кидаете, чтобы получить следующее слово, или мешок слов, в который вы не глядя запускаете руку, чтобы вытащить следующее. Нечестный мешок, правда, труднее представить – ну, скажем, каждое слово на камушках в мешке встречается по несколько раз, причём разные слова по-разному (вся эта интуиция нам ещё пригодится, bear with me for a moment). У вас есть один мешок, на котором написано «финансы», другой – «культура», третий – «спорт»:
И когда вы «генерируете» из этих мешков новый документ в наивном байесе, вы сначала выбираете мешок (кидая кубик), а потом из этого мешка начинаете выбирать слова одно за другим:
Графическая модель этого процесса выглядит очень просто (о том, как читать эти картинки, мы говорили в первой части предыдущего цикла, а во второй части даже был пример именно наивного байесовского классификатора). Слева – графическая модель полностью, в центре – модель одного документа с плашкой, которая скрывает повторяющиеся одинаковые переменные, а справа – та же модель, но для всего датасета, с явно выделенными переменными α и β, которые содержат параметры всех этих дискретных распределений:
Она тоже показывает, что наивный Байес состоит из одного дискретного распределения (кубика), которым определяется сравнительный «вес» тем, и нескольких дискретных распределений (мешков), по числу тем, которые показывают вероятности выпадения того или иного слова в теме.
А чтобы обучить наивный Байес (да и любой другой классификатор, тут уж никуда не денешься), нужно иметь размеченный набор текстов, на которых можно будет обучать эти распределения:
При обучении наивного Байеса мы для каждого документа знаем его тему, и остаётся обучить только распределение слов в каждой теме по отдельности и вероятности выпадения тем:
Для этого достаточно просто подсчитать, сколько раз то или иное слово встретилось в той или иной теме (и сколько раз темы встречаются в датасете), а результат сгладить по Лапласу.
У наивного байесовского классификатора видны сразу два направления, по которым его можно было бы расширить и улучшить:
- насколько необходимо иметь размеченный датасет? размечать датасет руками очень дорого, а датасет нужен достаточно большой, потому что мы обучаем распределение всех слов в данной теме; может быть, можно как-нибудь так, без меток, если умеючи?
- в реальных датасетах разве что твиты будут иметь одну хорошо определённую тему; например, новость «защитник «Челси» и сборной Бразилии Давид Луис был продан в «ПСЖ» более чем за 40 миллионов фунтов стерлингов» изрядно подпортит нашу модель, ведь здесь сочетаются слова о спорте и о финансах, и в результате либо спортивная тема получит «контаминацию» из финансовых слов, либо наоборот; можно ли сделать так, чтобы у одного документа было несколько тем?
От классификации к кластеризации
Начать будет логично с первого направления, о том, как перейти к обработке датасетов без меток, ведь даже если мы сделаем модель, в которой у каждого документа несколько тем, разметить большой датасет руками, да ещё и на несколько тем для одного документа, будет крайне затруднительно. Итак, давайте представим, что у нас есть датасет, состоящий из текстов, и мы предполагаем, как и в наивном Байесе, что каждый документ был порождён из одной-единственной темы. Разница только в том, что теперь мы не знаем, из какой именно, и задача для нас выглядит так:
Давайте предполагать (мы и в LDA будем так делать; чтобы от этого избавиться, нужны непараметрические методы, до которых нам ещё далеко), что число потенциальных категорий (разных мешков со словами) нам известно, неизвестно только их содержание. Таким образом, вероятностная модель выглядит точно так же:
,и распределения в ней всё те же. Разница только в том, что раньше мы при обучении знали для каждого документа его тему, а теперь не знаем. Иначе говоря, совместное распределение, из которого порождаются документы, всё то же: если обозначить через w вектор слов и через c категорию документа D, его общее правдоподобие будет
где βc – это распределение в мешке слов, соответствующем категории c; а общее правдоподобие, которое нужно максимизировать при обучении – это, соответственно,
и максимизировать его надо по-прежнему по α и βc. Но если раньше мы делали это при известных c, и задача максимизации разбивалась по отдельным темам и была в сущности тривиальной, то теперь надо максимизировать при неизвестных c, т.е. фактически взяв ожидание по ним:
Как это сделать?
То, что у нас получилось, на самом деле является совершенно стандартной задачей кластеризации: есть много объектов (текстов) в многомерном пространстве (слов), и нужно разбить их на отдельные классы так, чтобы тексты в одном классе были бы как можно более похожи друг на друга и при этом как можно менее похожи на тексты в других классах. Так что здесь может помочь стандартный инструмент обучения моделей кластеризации – EM-алгоритм (от слов Expectation-Maximization, сейчас поймёте почему). EM-алгоритм предназначен для ситуаций, когда в модели есть скрытые переменные (как у нас c), и нужно максимизировать правдоподобие модели по её параметрам (у нас это α и β), но в ожидании по скрытым переменным. EM-алгоритм сначала инициализирует модель какими-то начальными значениями, а затем итеративно повторяет два шага:
- E-шаг – найти ожидания (expectation) скрытых переменных при данной модели;
- M-шаг – максимизировать правдоподобие (maximization), считая переменные равными своим ожиданиям, найденным на E-шаге.
В нашем случае на Е-шаге мы просто находим вероятности того, что каждый документ принадлежит разным категориям, при фиксированных α и β:
А затем на М-шаге считаем эти вероятности принадлежности фиксированными и оптимизируем α и β (лучше со сглаживанием α0 и β0, соответствующим неким априорным распределениям на параметры α и β):
Затем это всё нужно повторить до тех пор, пока α и β не сойдутся; это и есть ЕМ-алгоритм для кластеризации, применённый к случаю дискретных атрибутов (слов в документах).
Общая идея того, почему EM-алгоритм, собственно, работает, такова: на каждом Е-шаге EM-алгоритм фактически строит вспомогательную функцию от параметров модели, которая в текущем приближении касается функции правдоподобия и при этом везде остаётся меньше неё (миноризует функцию правдоподобия). Вот картинка из одного из источников на эту тему (честно признаюсь, забыл, из какого именно):
А затем на М-шаге ЕМ-алгоритм находит параметры, максимизирующие эту вспомогательную функцию. Очевидно, что при этом мы переходим в точку, в которой общее правдоподобие увеличивается. Я не буду сейчас подробно углубляться в доказательство того, что EM-алгоритм действительно это всё делает и действительно корректно работает, нам важна только общая идея.
Что дальше
Сегодня мы сделали первый из двух шагов на пути от наивного байесовского классификатора к LDA: перешли от задачи классификации, в которой у каждого документа в обучающем датасете должна быть фиксированная категория, к задаче кластеризации, в которой документы не обязательно должны быть размечены по категориям. Отметим, кстати, что если у вас всё-таки размечена часть документов (это называется semi-supervised learning), это очень легко добавить в получившуюся модель. Нужно просто зафиксировать соответствующие переменные ci(D), сделать их равными единице в размеченной теме и нулю во всех остальных, и в рамках EM-алгоритма не обучать эти переменные, оставляя их значения фиксированными. Такой «посевной датасет» будет, кстати, очень полезен для дальнейшего обучения модели.
В следующий раз мы сделаем второй шаг на пути к латентному размещению Дирихле: от категорий, присваиваемых всему тексту целиком, перейдём к темам, которых в каждом документе может быть несколько.
