Лекция составлена по мотивам результатов исследований К. В. Воронцова, доктора физико-математических наук, преподавателя ШАД и МГУ
¶ Постановка задачи
В NLP мы работаем с коллекциями текстовых документов. Каждый документ представляет собой множество токенов. Говоря о каких-либо документах в реальной жизни мы часто сталкиваемся с таким понятием, как тема. В обработке естественного языка тема, также как и документ, ассоциируется с множеством токенов.
Замечание: здесь и далее понятия “токен”, “терм" и “слово” считаем синонимами.
Тема - это:
- специальная терминология предметной области;
- набор часто совместно встречающихся токенов;
- кластер текстовых документов.
Тема - это вероятностное распределение на терминах: - вероятность встретить термин w в теме t. Это распределение является латентным, то есть скрытым.
Тематический профиль - это вероятностное распределение на документах: - вероятность темы t для документа d. Это распределение также является латентным.
Замечание: подобные вероятностные распределения проще всего представлять в виде матриц. Если у нас 500 терминов и 5 тем, то имеет матрицу 500 на 5, сумма чисел в столбце равна единице.
Тематическое моделирование - это задача выделения тем и определения тематического профиля каждого документа по наблюдаемому распределению (это частота слова в документе). Можно заметить, что тематическое моделирование сильно напоминает задачу кластеризации текстовых документов.
Основное отличие в том, что здесь мы имеем дело с так называемой мягкой кластеризацией (документ может принадлежать к нескольким кластерам, результат кластеризации задается распределением вероятностей).
Некоторые приложения тематического моделирования:
- поиск научной информации;
- агрегирование новостей;
- семантический поиск.
Пусть:
- T - множество тем;
- W - множество слов;
- D - множество текстовых документов;
- порядок документов в коллекции не важен;
- порядок слов в документе не важен (структура Bag of Words);
- - дискретное вероятностное пространство;
- коллекция документов представляется в виде троек (di, wi, ti); таких троек очевидно ;
- каждое слово w в документе d связано с каждой темой (но с некоторыми - более сильная связь);
- p(w | d, t) = p(w | t) - гипотеза условной независимости (порождение слов в документе не зависит от документа, а зависит от тем, которые затрагиваются в документе).
Появление слова зависит только от темы, но не от того, в каком документе мы эту тему обсуждаем
Тема определяется тем, какие слова в ней встречаются чаще
В теме "Космос" высока вероятность слов "ракета", "орбита", "спутник". В теме "Биология" "клетка", "ДНК" и др.
Идея состоит в том, чтобы поставить задачу генерации текста (моделирования языка):
Автор задумал написать статью и решил, в каких пропорциях смешать темы (определил тематический профиль). Автор берет ручку, ставит ее на первое место в предложении и:
- выбирает случайным образом тему из своего профиля
- смотрит в мешок слов этой темы и случайно достает оттуда слово
- записывает слово
Конечно же, это чисто формальная задача. Никто на самом деле так тексты не генерирует
Куда интереснее решать обратную задачу.
Мы знаем - частота термина w в документе d; - количество терминов в документе d; тогда .
Поскольку мы не знаем вероятности и , мы можем рассматривать их как параметры распределения . Введем обозначения: , .
Тогда и имеем задачу стохастического матричного разложения:
Стохастическое означает, что столбцы всех матриц - векторы, соответствующие дискретным распределениям (нормированы и неотрицательны)
Запишем правдоподобие (совместное распределение всей выборки) и поставим задачу его максимизации:
Правдоподобие - вероятность того, что реальная коллекция текстов могла быть сгенерирована моделью
Произведем классический прием - логарифмирование:
Получаем задачу математического программирования:
При ограничениях в собственном смысле (нормировки):
И ограничениях неотрицательности:
¶ EM-алгоритм
Имеем задачу нелинейной условной оптимизации. Чтобы ее решить вспомним, а что вообще называется оптимальным решением по теореме Каруша-Куна-Таккера:
Запишем условия Каруша-Куна-Таккера для нашей задачи (поскольку наша целевая функция является функцией двух переменных, условия мы будем расписывать для одной из переменных (считая другую константой) - для ; для другой переменной все аналогично):
Замечание: знак минус, потому что у нас задача на максимум.
Умножим обе части уравнения на :
Здесь имеем:
Но:
Суммируем обе части равенства по словам:
Делаем подстановку:
Отсюда получаем уравнение:
Продолжая рассуждения, мы приходим к уравнениям, по которым можем итеративно вычислять и :
На практике вычисления организуются в виде EM-алгоритма:
E-шаг:
M-шаг:
Нормировка:
Знаменатель в нашей задаче всегда больше нуля (если коллекция непустая, то и ). Мы только что получили алгоритм pLSA (Probabilistic Latent Semantic Analysis), представленный в 1999 году. Именно с этой идеи началось развитие тематического моделирования.
Интересный факт: EM (Expectation–maximization) - алгоритм является своего рода абстракцией над двухшаговыми алгоритмами оптимизации. Вы знаете (и реализовывали в прошлом семестре) как минимум один алгоритм, основанный на этой идее. Какой?
Казалось бы, задача решена, ведь у нас есть конкретные формулы, которые даже можно осознать и использовать? Но все не так просто! Задача математического программирования, которую мы сформулировали, является некорректно поставленной по Адамару (решение на самом деле не единственное, их бесконечное множество):
если - решение, то стохастические матрицы - также решения;
Очередная (любая?) квадратная матрица S размера |T| порождает очередное решение. Веселая получается задачка оптимизации конечно 🙂
Это верно не для любой матрицы , а только для такой, которая сохраняет стохастичность (неотрицательность и нормировку) матриц и
¶ ARTM и LDA
Для решения этой проблемы в модель вводят регуляризаторы, которые позволяют доопределить задачу.
Рассматриваемый прием называется аддитивной регуляризацией тематических моделей (ARTM) и является постановкой задачи оптимизации в общем виде.
EM-алгоритм в общем виде выглядит следующим образом (если интересно, попробуйте самостоятельно аналогично вывести его из теоремы Каруша-Куна-Таккера, почти все то же самое):
E-шаг:
M-шаг:
И вот теперь уже есть причина задаться вопросом: как быть, если знаменатель при нормировке будет равен 0 (такое возможно, поскольку частная производная может быть отрицательной, на регуляризаторы не накладывается никаких ограничений).
Действительно, знаменатель может быть равен нулю. Для нас это будет значить, что мы не можем вычислить соответствующие столбцы матриц и .
Считаем, что тема t вырождена, если для всех терминов :
Если тема вырождена, то , заполняем столбец нулями. Таким образом регуляризатор может производить отбор тем.
Считаем, что документ d вырожден, если для всех тем :
Если документ вырожден, то , заполняем столбец нулями. Интерпретируем это так, что модель не в состоянии описать данный документ.
Все алгоритмы для решения задачи тематического моделирования могут быть описаны в виде задачи с аддитивной регуляризацией, например LDA, который вы использовали в ЛР 8 по дисциплине “Машинное обучение”.
LDA (Latent Dirichlet allocation) на языке регуляризаторов описывается следующим образом:
Очевидным образом получаем формулы для M-шага:
LDA за счет своих гиперпараметров позволяет управлять разреженностью столбцов матриц .
Гипотеза: столбцы и порождаются распределением Дирихле.
Учитывая, что совместное правдоподобие наблюдаемой выборки и выборки распределения Дирихле определяется следующим образом:
Легко получаем регуляризатор LDA, который был выше (с помощью логарифмирования).
И самое главное, теперь мы понимаем, как с помощью этого регуляризатора создавать вырожденные темы и документы:
Специально не убирал опечатку
¶ Выводы
Задача тематического моделирование - это построение тематических профилей документов и выделение наиболее характерных терминов для каждой темы.
На самом деле мы решаем не задачу моделирования, а обратную задачу, которая в исходной постановке имеет бесконечное множество решений.
Используя идею аддитивной регуляризации мы можем выработать общий подход к решению задачи используя идею EM-алгоритма и придумывать собственные регуляризаторы, а значит и свои алгоритмы тематического моделирования.
Регуляризаторы позволяют производить отбор тем и находить аномалии среди документов.
Наиболее популярный алгоритм LDA основан на идее генерации столбцов искомых матриц с помощью распределения Дирихле, которое задается двумя параметрами. Корректируя значения этих параметров, мы можем получать различные тематические профили и наборы тем.
На следующем занятии мы практически решим задачу тематического моделирования.