[ЗАСТАВКА] В этом
видео мы с вами разберемся, как строятся вероятностные
тематические модели и как устроен основной алгоритм для их построения — EM-алгоритм.
Напомню, что в конце предыдущего видео мы пришли к постановке задачи,
которая по наблюдающимся словам в документах строит тематическую модель.
Постановка заключалась в максимизации логарифма правдоподобия,
к которому добавлен некоторый регуляризатор R — произвольная функция.
Но для того чтобы эту задачу было удобно решать,
от этой функции требуется только то, чтобы она была гладкой,
тогда можно к этой задаче применять условие Каруша — Куна — Таккера.
Естественно, выкладки я сейчас опускаю и просто показываю результат.
Это не решение, выраженное в аналитическом виде, к сожалению,
это всего лишь система уравнений, которую придется решать, но решать ее достаточно
удобно очень простым численным методом, который называется метод простых итераций.
И он же по совместительству здесь у нас оказывается EM-алгоритмом.
Это система уравнений, которая состоит из двух типов уравнений.
Первое, это так называемый E-шаг EM-алгоритма — это вычисление
условных распределений тем для каждого слова в каждом документе.
И то, что записано в первой строке этой системы уравнений, по сути дела,
не что иное, как просто формула Байеса, по которой мы можем выразить вот эти наши
вспомогательные переменные P, t, d, w в этой системе через параметры модели Φ и θ.
А вот формулы M-шага, они, наоборот, они выражают основные
параметры модели Φ и θ через вспомогательные переменные P, t, d, w.
И если откинуть регуляризатор, считать, что R = 0, то окажется,
что вот те формулы, которые здесь записаны — это просто частотные оценки
условных вероятностей слов в темах и тем в документах.
То есть если бы мы знали тему каждого слова, мы могли бы просто написать,
очень легко посчитать частотные оценки вероятностей условных слов в
темах и тем в документах.
Но поскольку мы не можем знать, на самом деле,
тему каждого слова в каждом документе, мы ее оцениваем вот так
вот по фактически формуле Байеса и получаем итерационный процесс,
где основные вспомогательные переменные оцениваются друг по другу поочередно.
Но и обращаю внимание на то, что оператор нормировки здесь переводит
произвольный вектор xt в вектор, координаты
которого неотрицательны и нормированы, то есть сумма их в точности равна 1.
То есть любой произвольный вещественный вектор переводится в вектор той
же размерности, который может играть роль дискретного распределения.
И вот через эту операцию нормирования векторов очень удобно оказалось
записать вот все уравнения этой системы уравнений.
Есть два очень известных частных случая этой системы —
ведь мы можем задавать регуляризатор в широких пределах.
Так вот, если он совсем не задан — R = 0, то мы получаем очень известный метод,
который в 1999 году был придуман и опубликован Томасом Хофманом.
Метод называется «вероятностный латентный семантический анализ», или PLSA.
Четыре года спустя появился следующий метод,
который был предложен Дэвидом Блеем,
Эндрю Энджи и Майклом Джорданом — три очень известных ученых.
Их статья по латентному размещению Дирихле — это, наверное,
самая цитируемая работа в тематическом моделировании.
Здесь я не буду очень подробно рассказывать все те соображения,
и почему именно распределение Дирихле здесь появляется,
и все те соображения, которые были использованы авторами этого метода.
Но с точки зрения регуляризации взгляд на этот метод довольно прост
— это вот такой вот регуляризатор, в котором появляются параметры β и α.
Авторы этого метода рассматривали его с точки зрения байесовского обучения,
и там делалось два вероятностных предположения.
Первое — что столбцы матриц Φ и θ могут быть не какими угодно,
они порождаются из распределения Дирихле.
Распределение Дирихле — это такое распределение, которое умеет порождать
векторы заданной размерности, которые являются нормированными неотрицательными,
то есть могут быть вероятностными распределениями.
Вот такая вот двухступенчатая порождающая модель: сначала из Дирихле порождаются
столбы матриц Φ и θ, а потом из них уже,
как мы в предыдущих видео обсуждали, порождается текст.
И второе предположение делается,
что если мы воспользуемся принципом максимума апостериорной вероятности,
то есть учтем эти априорные распределения в принципе максимума
совместного правдоподобия данных и модели Φ и θ,
которые тоже генерируются вероятностным образом,
то вот тогда мы сможем получить новую постановку задачи, которую
можно трактовать как регуляризованное логарифмированное правдоподобие.
Вот интересны свойства распределения Дирихле — почему-то все-таки они именно
оказались удобными в качестве априорных распределений.
Дело в том, что распределение Дирихле позволяет генерировать как разреженные,
так и такие вот сильно сглаженные дискретные распределения.
Причем случаи разреженности, вот как показано на левом графике,
нас как раз интересуют больше всего, потому что у нас есть гипотеза о том,
что каждая тема состоит, в общем-то, из небольшого числа тем, слов, и каждая...
каждый документ состоит из небольшого числа тем.
То есть кажется, что вот как раз, когда параметры распределения Дирихле меньше 1,
это самый интересный для нас случай,
потому что распределения получаются разреженными.
Ну и если параметры распределения Дирихле в точности 1, то это получается просто
равномерное распределение, и в таком случае LDA просто переходит в PLSA.
Интересен другой
взгляд на латентное размещение Дирихле,
даже более простой, но чтобы его рассказать, я должен ввести понятие
дивергенции Кульбака — Лейблера — это вообще очень полезное понятие,
и в машинном обучении, и в теории вероятности довольно часто встречается.
Это способ померять расстояние между двумя распределениями.
Поскольку нас интересует дискретное распределение,
мы сейчас только вот такой случай рассматриваем, а вообще,
в общем случае вместо суммы здесь должен стоять интеграл.
Итак, дивергенция Кульбака — Лейблера определяется
вот по такой несложной формуле.
Основные ее свойства — это то, что это неотрицательное значение,
и она равна 0 тогда и только тогда, когда распределение P и Q совпадают.
Мера — несимметричная, она, строго говоря, поэтому не является
функцией расстояния между распределениями P и Q в обычном смысле.
Она меряет в некотором смысле степень вложенности
распределения P в распределение Q.
Другой способ посмотреть на это — это связать
минимизацию дивергенции Кульбака — Лейблера с максимизацией правдоподобия.
Оказывается, что это две эквивалентные вещи.
Если P у нас — эмпирическое распределение,
а Q — это какая-то параметрическая модель распределения с параметром α,
то если мы используем принцип максимума правдоподобия,
для того чтобы определить этот параметр так, чтобы наше эмпирическое распределение
P как можно лучше соответствовало модели, то это все равно что минимизировать
дивергенцию Кульбака — Лейблера между этими двумя распределениями.
Вот такая вот интерпретация дает нам неплохую интуицию о смысле дивергенции и
о том, как ее можно использовать, а мы ее будем использовать в роли регуляризаторов.
Итак, другой взгляд на латентное размещение Дирихле,
как я говорил, более простой, заключается в том,
что если мы зададимся вот этими вот векторами — ну, рассмотрим матрицу Φ,
тогда мы задаемся векторами β, это вектор над словарем слов.
Так вот, те слова, которые соответствуют значениям
β > 1 — для них условные вероятности слов в
темах будут сглаживаться, они будут приближаться к значениям βw.
А если βw было < 1, то, наоборот, будет происходить разреживание,
и максимизация дивергенции Кульбака — Лейблера между двумя распределениями будет
означать, что распределение Φt, то есть столбцы матрицы Φ,
соответствующие теме t, они будут разреживаться,
то есть в них будут появляться больше нулевых или почти нулевых элементов.
Так вот, в отличие от байесовской точки зрения здесь нам не
нужно ни вводить распределения Дирихле, ни говорить об априорных
вероятностях — здесь достаточно сказать, что мы просто либо просто приближаем
столбцы матриц Φ и θ каким-то заданным распределением, либо удаляем от них.
И это вот приближение-удаление можно даже делать для разных
координат — в столбце некоторые сглаживать, некоторые разреживать.
Более того, появляется свобода задавать параметры β и α какими угодно,
без ограничений, что они должны быть строго положительны —
это ограничение шло из самого определения, что такое распределение Дирихле.
Но вот в нашей такой интерпретации, более свободной,
никаких ограничений на β и α не возникает, и можно, например,
сильнее разреживать эти распределения, добиваясь того,
чтобы модель была разреженной, то есть было как можно больше 0 в матрице Φ и θ,
но при этом, конечно, эти матрицы Φ и θ чтобы хорошо описывали нашу коллекцию.
Итак, от частных случаев перевернемся снова к общему случаю.
Мы ведь получили некую систему уравнений и договорились, что мы будем решать ее
методом простых итераций, то есть по вспомогательным переменным P, t, d,
w — это условные вероятности тем для слов в документах — мы будем считать основные
параметры модели Φ и θ, ну и, наоборот, по Φ и θ мы рассчитываем P, t, d, w.
Так вот, можно, ничего не меняя в формулах вот этой системы уравнений,
организовать вычислительный процесс метода простых итераций таким образом,
чтобы он шел максимально быстро,
причем именно на больших коллекциях текстовых документов.
Дело в том, что матрицы Φ и θ находятся в неравноправном положении.
Матрица Φ относится ко всей коллекции целиком,
и каждый ее столбец относится ко всей коллекции целиком,
а вот в матрице θ каждый столбец относится только к одному документу.
Поэтому если мы будем итерировать таким образом, что только после просмотра всей
коллекции мы будем обновлять матрицы Φ и θ, процесс будет работать крайне медленно.
Потому что матрица Φ будет обновляться слишком редко.
Мы можем делать по-другому: мы можем просматривать каждый документ,
строить для него тематическую модель и обновлять матрицу Φ.
Можем обрабатывать по несколько документов,
образуя такие вот порции или пакеты, батчи — по-разному их называют.
И после вычисления модели для нескольких документов обновлять матрицу Φ.
Вот оказалось, что такой процесс самый быстрый, и появились онлайновые алгоритмы.
Они появились не сразу, а примерно лет 5 назад,
и они сразу сделали тематическое моделирование очень эффективным
инструментом анализа больших коллекций текстов.
Оказалось, что матрица Φ может сходиться даже до того,
как мы просмотрели всю коллекцию.
Ну, например, коллекция — огромна, избыточна, содержит миллионы документов,
а оказывается, что после просмотра нескольких первых десятков тысяч,
мы уже получаем более или менее хорошую, устоявшуюся матрицу Φ — она уже сошлась.
И нам остается только тематизировать остальные документы.
Вот в таком режиме работы мы можем прогнать EM-алгоритм через всю коллекцию,
сделав фактически только одну итерацию.
Приходится, правда, делать несколько итераций для каждого документа.
Вот такой вот алгоритм — он называется онлайновым алгоритмом — используется
практически во всех основных пакетах по тематическому моделированию,
которые сегодня существуют даже в открытом коде и рекомендуются для
обработки больших коллекций.
Итак, краткое резюме.
EM-алгоритм — это основной инструмент в тематическом моделировании.
Онлайновый алгоритм, как мы сейчас видели, позволяет вообще делать обработку
большой коллекции за один проход.
И вот тот подход, который основан на использовании регуляризаторов,
хорош тем, что можно единообразно, с помощью одного и того же EM-алгоритма,
вот этого онлайнового, строить огромное разнообразие тематических моделей,
не только LDA и PLSA, а менять регуляризаторы,
добавлять новые регуляризаторы, учитывать все новые и новые требования к модели.
Вот такой вот подход оказался очень продуктивным, простым,
универсальным, гибким.
И в следующем видео я расскажу еще немножко больше о том,
какие конкретно регуляризаторы, кроме стандартных, как в LD, можно использовать.
Evgeniy Riabenko
Evgeny Sokolov
Victor Kantor
Emeli Dral
Константин Воронцовдоктор физико-математических наук, профессор
