Вероятностные тематические модели (курс лекций, К.В.Воронцов)

Материал из MachineLearning.

Содержание 1 Программа курса 1.1 Задачи анализа текстов и вероятностные модели 1.2 Вероятностный латентный семантический анализ 1.3 Латентное размещение Дирихле 1.4 Аддитивная регуляризация тематических моделей 1.5 Оценивание качества тематических моделей 1.6 Внешние оценки качества тематических моделей 1.7 Мультимодальные регуляризованные тематические модели 1.8 Определение числа тем и иерархические модели 1.9 Тематические модели, учитывающие порядок слов 1.10 Динамические и пространственные тематические модели 1.11 Визуализация тематических моделей 1.12 Параллельные и распределённые алгоритмы 2 Литература 3 Ссылки

Спецкурс читается студентам 2—5 курсов на кафедре «Математические методы прогнозирования» ВМиК МГУ с 2013 года.

В спецкурсе изучается вероятностное тематическое моделирование (topic modeling) коллекций текстовых документов. Развивается многокритериальный подход к решению некорректно поставленной задачи стохастического матричного разложения — аддитивная регуляризация тематических моделей. Рассматриваются свойства интерпретируемости, устойчивости и полноты тематических моделей, а также способы их измерения. Рассматриваются прикладные задачи классификации и категоризации текстов, информационного поиска, персонализации и рекомендательных систем. Рассматриваются задачи анализа и классификации символьных последовательностей неязыковой природы, в частности, аминокислотных и нуклеотидных последовательностей, дискретизированных биомедицинских сигналов. Предполагается проведение студентами численных экспериментов на модельных и реальных данных.

От студентов требуются знания курсов линейной алгебры, математического анализа, теории вероятностей. Знание математической статистики, методов оптимизации, машинного обучения, языков программирования Python и С++ желательно, но не обязательно.

Условием сдачи спецкурса является выполнение индивидуальных практических заданий.

• Файл с описанием заданий: voron-2016-task-PTM.pdf

Программа курса

Задачи анализа текстов и вероятностные модели

Задачи классификации текстов.

• Коллекция текстовых документов. Векторное представление документа.
• Эмпирические законы Ципфа, Ципфа-Мандельброта, Хипса.
• Постановка задачи классификации текстов. Объекты, признаки, классы, обучающая выборка.
• Линейный классификатор. Наивный байесовский классификатор.
• Задача распознавания языка текста.
• Задача распознавание жанра текста. Распознавание научных текстов. Примеры признаков.
• Задача категоризации текстов, сведение к последовательности задач классификации.
• Задача анализа тональности.

Задачи предварительной обработки текстов.

• Очистка: удаление номеров страниц (колонтитулов), переносов, опечаток, оглавлений, таблиц, рисунков, нетекстовой информации.
• Лемматизация и стемминг. Сравнение готовых инструментальных средств.
• Выделение и удаление стоп-слов и редких слов.

Задачи информационного поиска.

• Задача поиска документов по запросу. Инвертированный индекс.
• Меры сходства векторов частот. Косинусная мера сходства. Расстояние Хеллингера.
• Дивергенция Кульбака-Леблера и её свойства. Дивергенция Кресси-Рида.
• Критерий текстовой релевантности TF-IDF. Вероятностная модель и вывод формулы TF-IDF.
• Задача ранжирования. Примеры признаков. Формирование асессорских обучающих выборок.

Униграммная модель документов и коллекции.

• Вероятностное пространство. Гипотезы «мешка слов» и «мешка документов». Текст как простая выборка, порождаемая вероятностным распределением. Векторное представление документа как эмпирическое распределение.
• Понятие параметрической порождающей модели. Принцип максимума правдоподобия.
• Униграммная модель документов и коллекции.
• Ликбез. Теорема Куна-Таккера.
• Аналитическое решение задачи о стационарной точке функции Лагранжа. Частотные оценки условных вероятностей.

Литература: [Маннинг 2011].

Вероятностный латентный семантический анализ

• Напоминания. Коллекция текстовых документов. Векторное представление документа. Задачи информационного поиска и классификации текстов.

Мотивации вероятностного тематического моделирования

• Идея понижения размерности: переход от вектора (терминов) к вектору тем.
• Цели тематического моделирования: разведочный поиск научной информации, навигация и систематизация, агрегирование новостных потоков, классификация и категоризация текстов, обход проблем синонимии и омонимии.

Задача тематического моделирования.

• Вероятностное пространство. Тема как латентная (ненаблюдаемая) переменная. Гипотеза условной независимости. Порождающая модель документа как вероятностной смеси тем.
• Постановка обратной задачи восстановления параметров модели по данным.

Вероятностный латентный семантический анализ (PLSA).

• Принцип максимума правдоподобия, аналитическое решение задачи о стационарной точке функции Лагранжа, формулы M-шага.
• Элементарная интерпретация ЕМ-алгоритма: Е-шаг как формула Байеса для апостериорной вероятности темы, М-шаг как частотные оценки условных вероятностей.
• Рациональный ЕМ-алгоритм (встраивание Е-шага внутрь М-шага).

Онлайновый ЕМ-алгоритм (OEM).

• Проблема больших данных.
• Эвристика разделения М-шага.
• Эвристика разделения коллекции на пачки документов.
• Добавление новых документов (folding-in).

Проведение экспериментов на модельных данных.

• Процесс порождения терминов в документе. Генератор модельных (синтетических) данных. Генерация случайной величины из заданного дискретного распределения.
• Распределение Дирихле. Генерация разреженных и сглаженных векторов дискретных распределений из распределения Дирихле.
• Оценивание точности восстановления модельных данных. Расстояние между дискретными распределениями. Проблема перестановки тем, венгерский алгоритм.
• Проблема неединственности и неустойчивости матричного разложения. Экспериментальное оценивание устойчивости решения.

Задание 1.1 Обязательные пункты: 1–3 и любой из последующих.

1. Реализовать генератор модельных данных. Реализовать вычисление эмпирических распределений терминов тем и тем документов.
2. Реализовать оценку точности восстановления с учётом перестановки тем. Вычислить оценку точности для исходных модельных распределений.
3. Реализовать рациональный ЕМ-алгоритм.
4. Исследовать зависимости точности модели и точности восстановления от числа итераций и от числа тем в модели (при фиксированном числе тем в исходных данных). Что происходит, когда тем больше, чем нужно? Меньше, чем нужно?
5. Исследовать влияние случайного начального приближения на устойчивость решения. Построить эмпирические распределения и доверительные интервалы для расстояний Хеллингера между истинными матрицами и восстановленными.
6. Исследовать влияние разреженности матриц Фи и Тета на устойчивость решения.
7. Исследовать полноту решения. Сколько запусков со случайным начальным приближением необходимо сделать, чтобы найти все исходные темы? Как различность и разреженность исходных тем влияет на полноту?

Литература: [Hofmann 1999].

Латентное размещение Дирихле

• Напоминания. Задача тематического моделирования коллекции текстовых документов. Модель PLSA, формулы Е-шага и М-шага.

Латентное размещение Дирихле (LDA)

• Свойства распределения Дирихле.
• Принцип максимума апостериорной вероятности. Модифицированные формулы М-шага.
• Байесовский вывод. Свойство сопряжённости мультиномиального распределения и распределения Дирихле. Другие модифицированные формулы М-шага.
• Обзор модификаций формул М-шага.
• Методы оптимизации гиперпараметров.
• Небайесовская интерпретация модели LDA.
• Сравнение LDA и PLSA. Экспериментальные факты: LDA скорее улучшает оценки редких слов, чем снижает переобучение.

Стохастический ЕМ-алгоритм (SEM).

• Гипотеза разреженности апоcтериорного распределения тем p(t|d,w).
• Эвристика сэмплирования. Алгоритм сэмплирования Гиббса.

Способы формирования начальных приближений.

• Случайная инициализация.
• Инициализация по документам.
• Контекстная документная кластеризация.
• Поиск якорных слов. Алгоритм Ароры.

Задание 1.2 Обязательные пункты: 1 и любой из последующих.

1. Реализовать онлайновый алгоритм OEM.
2. Исследовать влияние размера первой пачки и последующих пачек на качество модели.
3. Исследовать влияние выбора числа итераций на внутреннем и внешнем циклах алгоритма OEM на качество и скорость построения модели.
4. Исследовать возможность улучшения качества модели с помощью второго прохода по коллекции (без инициализации p(w|t)).
5. Исследовать влияние гиперпараметров на правдоподобие модели и точность восстановления.

Литература: [Hoffman 2010], [Asuncion 2009].

Аддитивная регуляризация тематических моделей

• Напоминания. Вероятностная тематическая модель. Принцип максимума правдоподобия. PLSA. EM-алгоритм.

Многокритериальная регуляризация.

• Некорректность постановки задачи тематического моделирования.
• Аддитивная регуляризация тематических моделей.
• Вывод формулы M-шага для регуляризованного ЕМ-алгоритма.
• Проект BigARTM.

Регуляризаторы сглаживания и разреживания.

• Максимизация и минимизация KL-дивергенции.
• Альтернативный вариант разреживания через L0-регуляризацию.
• Связь разреженности и единственности неотрицательного матричного разложения.
• Разреживание предметных тем и сглаживание фоновых тем. Автоматическое выделение стоп-слов.

Робастные тематические модели.

• Робастная модель с фоном и шумом.
• Упрощённая робастная модель.
• Эффект повышения правдоподобия (перплексии) в робастных моделях с шумом.

Регуляризаторы частичного обучения.

• Частичное обучение как выборочное сглаживание.
• Сфокусированные тематические модели. Использование словаря для выделения предметных тем.
• Пример: выделение тематики эпидемий, этнических конфликтов.

Ковариационные регуляризаторы.

• Дековариация тем.
• Тематические модели цитирования.
• Задача выявления корреляций между темами, модель CTM.
• Оценивание параметров (матрицы ковариаций) в модели CTM.

Задание 1.3 Обязательные пункты: 1 и любой из остальных.

1. Реализовать разреживание в онлайновом алгоритме OEM.
2. Исследовать зависимость правдоподобия модели и точности восстановления от степени разреженности исходных модельных данных.
3. Исследовать влияние разреживания на правдоподобие модели и точность восстановления. Проверить гипотезу, что если исходные данные разрежены, то разреживание существенно улучшает точность восстановления и слабо влияет на правдоподобие модели.
4. Исследовать влияние частичной разметки на правдоподобие модели и точность восстановления. Проверить гипотезу, что небольшой доли правильно размеченных документов уже достаточно для существенного улучшения правдоподобия и устойчивости модели.
5. Исследовать влияние сглаживания на правдоподобие модели и точность восстановления.

Литература: [Воронцов, 2013, 2015], [Chemudugunta, 2006].

Оценивание качества тематических моделей

Реальные данные.

• Текстовые коллекции, библиотеки алгоритмов, источники информации.
• Внутренние и внешние критерии качества.
• Дополнительные данные для построения внешних критериев качества.

Перплексия и правдоподобие.

• Определение и интерпретация перплекcии.
• Перплексия контрольной коллекции. Проблема новых слов в контрольной коллекции.
• Проблема сравнения моделей с разными словарями.
• Относительная перплексия.

Оценивание качества темы.

• Лексическое ядро темы: множество типичных терминов темы.
• Чистота и контрастность темы
• Документное ядро темы: множество типичных документов темы.
• Однородность темы: распределение расстояний между p(w|t) и p(w|t,d).
• Конфликтность темы: близость темы к другим темам.

Статистические тесты условной независимости.

• Методология проверки статистических гипотез. Критерий согласия хи-квадрат Пирсона.
• Проблема разреженности распределения. Эксперименты, показывающие неадекватность асимптотического распределения статистики хи-квадрат.
• Статистики модифицированного хи-квадрат, Кульбака-Лейблера, Хеллингера.
• Обобщённое семейство статистик Кресси-Рида.
• Эмпирическое оценивание квантилей распределения статистики Кресси-Рида.
• Применения теста условной независимости для поиска плохо смоделированных тем, документов, терминов. Поиск тем для расщепления.

Литература: [Newman, 2009–2011].

Внешние оценки качества тематических моделей

Оценивание интерпретируемости тем.

• Экспертное оценивание интерпретируемости.
• Асессорская разметка терминов и документов, релевантных теме.
• Метод интрузий.
• Радикальное улучшение интерпретируемости в n-граммных тематических моделях.

Когерентность.

• Определение когерентности.
• Эксперименты, показывающие связь когерентности и интерпретируемости.
• Способы оценивания совместной встречаемости слов.

Суммаризация темы.

• Проблема визуализации тем.
• Выделение тематичных слов и предложений.
• Кластеризация тематичных предложений.
• Ранжирование тематичных предложений.
• Асессорская разметка предложений, релевантных теме.
• Задача автоматического именования темы.

Критерии качества классификации и ранжирования.

• Полнота, точность и F-мера в задачах классификации и ранжирования.
• Критерии качества ранжирования: MAP, DCG, NDCG.
• Оценка качества тематического поиска документов по их длинным фрагментам.

Задание 1.4.

1. Применить OEM к реальным коллекциям.
2. Исследовать на реальных данных зависимость внутренних и внешних критериев качества от эвристических параметров алгоритма обучения OEM.
3. В экспериментах на реальных данных построить зависимости перплексии обучающей и контрольной коллекции от числа итераций и числа тем.

Литература:

Мультимодальные регуляризованные тематические модели

• Напоминания. Аддитивная регуляризация тематических моделей.

Мультимодальная АРТМ.

• Виды модельностей и примеры прикладных задач.
• Вывод формул М-шага.
• Тематическая модель классификации документов.
• Тематическая модель текста и изображений.
• Задача аннотирования изображений.

Мультиязычные тематические модели.

• Параллельные и сравнимые коллекции.
• Регуляризаторы для учёта двуязычных словарей.

Модели многоматричных разложений.

• Понятие порождающей модальности.
• Вывод формул М-шага.
• Автор-тематическая модель.
• Модель для выделения поведений объектов в видеопотоке.

Гиперграфовая модель.

• Примеры транзакционных данных в социальных и рекламных сетях.
• Вывод формул М-шага.

Литература:

Определение числа тем и иерархические модели

Регуляризатор энтропийного разреживания.

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

Тематическая модель с фиксированной иерархией.

• Задачи категоризации текстов. Стандартный метод решения — сведение к последовательности задач классификации.
• Необходимость частичного обучения для задачи категоризации.
• Вероятностная формализация отношения «тема–подтема». Тождества, связывающие распределения тем и подтем
• Задача построения разреженного иерархического тематического профиля документа.

Послойное нисходящее построение тематической иерархии.

• Регуляризатор матрицы Фи.
• Регуляризатор матрицы Тета.
• Измерение и оптимизация качества иерархических моделей.
• Разреживание вероятностного отношения тема—подтема.

Одновременное построение всех слоёв тематической иерархии.

Литература: .

Тематические модели, учитывающие порядок слов

Мультиграммные модели.

• Задача выделения терминов как ключевых фраз (словосочетаний). Словари терминов.
• Морфологический и синтаксический анализ текста.
• Отбор фраз с подчинительными связями.
• Отбор фраз по статистическому критерию коллокации C-Value. Совмещение критериев TF-IDF и CValue.
• Отбор фраз по оценке тематичности.

Регуляризаторы для выделения энграмм.

• Биграммная тематическая модель.

Сегментирующие тематические модели.

• Позиционный регуляризатор, вывод формул М-шага.
• Пост-обработка Е-шага.
• Интерпретация текста как пучка временных рядов и задача разладки.
• Алгоритм тематической сегментации.

Литература: .

Динамические и пространственные тематические модели

Тематические модели с модальностью времени.

• Регуляризатор разреживания тем в каждый момент времени.
• Регуляризаторы сглаживания темы как временного ряда.
• Вывод M-шага для негладкого регуляризатора.

Тематические модели с модальностью геолокации.

• Тематические модели социальных сетей.

Визуализация тематических моделей

Навигация по тематической модели.

• Визуализатор TMVE.
• Визуализатор Termite.
• Визуализатор для BigARTM.

Методы визуализации.

• Задача и методы многомерного шкалирования.
• Визуализация «дорожной карты» темы или набора тем.
• Визуализация тематических иерархий.
• Визуализация динамических моделей, метафора «реки тем».
• Визуализация тематической структуры документа.
• Визуализация модели трёх источников.

Средства разведочного поиска.

• Концепция пользовательского интерфейса для разведочного поиска.
• Концепция иерархической суммаризации.

Параллельные и распределённые алгоритмы

• Обзор подходов к распараллеливанию онлайнового EМ-алгоритма.
• Распараллеливание онлайнового EМ-алгоритма в BigARTM.
• Распределённое хранение коллекции.

Литература

Основная литература

1. Vorontsov K. V., Potapenko A. A. Additive Regularization of Topic Models // Machine Learning. Special Issue “Data Analysis and Intelligent Optimization with Applications”: Volume 101, Issue 1 (2015), Pp. 303-323. Русский перевод
2. Vorontsov K. V., Frei O. I., Apishev M. A., Romov P. A., Suvorova M. A., Yanina A. O. Non-Bayesian Additive Regularization for Multimodal Topic Modeling of Large Collections // Proceedings of the 2015 Workshop on Topic Models: Post-Processing and Applications, October 19, 2015, Melbourne, Australia. ACM, New York, NY, USA. pp. 29–37.
3. Маннинг К., Рагхаван П., Шютце Х. Введение в информационный поиск. — Вильямс, 2011.
4. Daud A., Li J., Zhou L., Muhammad F. Knowledge discovery through directed probabilistic topic models: a survey // Frontiers of Computer Science in China.— 2010.— Vol. 4, no. 2. — Pp. 280–301.
5. Asuncion A., Welling M., Smyth P., Teh Y. W. On smoothing and inference for topic models // Proceedings of the International Conference on Uncertainty in Artificial Intelligence. — 2009.

Дополнительная литература

1. Воронцов К. В., Потапенко А. А. Модификации EM-алгоритма для вероятностного тематического моделирования // Машинное обучение и анализ данных. — 2013. — T. 1, № 6. — С. 657–686.
2. Воронцов К. В., Фрей А. И., Ромов П. А., Янина А. О., Суворова М. А., Апишев М. А. BigARTM: библиотека с открытым кодом для тематического моделирования больших текстовых коллекций // Аналитика и управление данными в областях с интенсивным использованием данных. XVII Международная конференция DAMDID/RCDL’2015, Обнинск, 13-16 октября 2015.
3. Blei D. M., Ng A. Y., Jordan M. I. Latent Dirichlet allocation // Journal of Machine Learning Research. — 2003. — Vol. 3. — Pp. 993–1022.
4. Chemudugunta C., Smyth P., Steyvers M. Modeling general and specific aspects of documents with a probabilistic topic model // Advances in Neural Information Processing Systems. — MIT Press, 2006. — Vol. 19. — Pp. 241–248.
5. Dempster A. P., Laird N. M., Rubin D. B. Maximum likelihood from incomplete data via the EM algorithm // J. of the Royal Statistical Society, Series B. — 1977. — no. 34. — Pp. 1–38.
6. Hofmann T. Probabilistic latent semantic indexing // Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval. — New York, NY, USA: ACM, 1999. — Pp. 50–57.
7. Hoffman M. D., Blei D. M., Bach F. R. Online Learning for Latent Dirichlet Allocation // NIPS, 2010. Pp. 856–864.
8. Lu Y., Mei Q., Zhai C. Investigating task performance of probabilistic topic models: an empirical study of PLSA and LDA // Information Retrieval. — 2011. — Vol.14, no.2. — Pp. 178–203.
9. Wallach H., Mimno D., McCallum A. Rethinking LDA: Why priors matter // Advances in Neural Information Processing Systems 22 / Ed. by Y. Bengio, D. Schuurmans, J. Lafferty, C. K. I. Williams, A. Culotta. — 2009. — Pp. 1973–1981.

Ссылки

• Тематическое моделирование
• Аддитивная регуляризация тематических моделей
• Коллекции документов для тематического моделирования
• BigARTM
• Конспект лекций: Voron-2013-ptm.pdf, 2.6 МБ (обновление 16 октября 2013).
• BigARTM: тематическое моделирование больших текстовых коллекций. Data Fest #1, 12 сентября 2015. (PDF, 6.5 МБ).