Вероятностные тематические модели (курс лекций, К.В.Воронцов)/2015
Материал из MachineLearning.
Программа спецкурса, прочитанного весной 2015 года студентам 2—5 курсов на кафедре «Математические методы прогнозирования» ВМиК МГУ.
- Файл с описанием заданий: voron-2015-task-PTM.pdf
Задачи анализа текстов и вероятностные модели
Задачи классификации текстов.
- Коллекция текстовых документов. Векторное представление документа.
- Эмпирические законы Ципфа, Ципфа-Мандельброта, Хипса.
- Постановка задачи классификации текстов. Объекты, признаки, классы, обучающая выборка.
- Линейный классификатор. Наивный байесовский классификатор.
- Задача распознавания языка текста.
- Задача распознавание жанра текста. Распознавание научных текстов. Примеры признаков.
- Задача категоризации текстов, сведение к последовательности задач классификации.
- Задача анализа тональности.
Задачи предварительной обработки текстов.
- Очистка: удаление номеров страниц (колонтитулов), переносов, опечаток, оглавлений, таблиц, рисунков, нетекстовой информации.
- Лемматизация и стемминг. Сравнение готовых инструментальных средств.
- Выделение и удаление стоп-слов и редких слов.
Задачи информационного поиска.
- Задача поиска документов по запросу. Инвертированный индекс.
- Меры сходства векторов частот. Косинусная мера сходства. Расстояние Хеллингера.
- Дивергенция Кульбака-Леблера и её свойства. Дивергенция Кресси-Рида.
- Критерий текстовой релевантности TF-IDF. Вероятностная модель и вывод формулы TF-IDF.
- Задача ранжирования. Примеры признаков. Формирование асессорских обучающих выборок.
Униграммная модель документов и коллекции.
- Вероятностное пространство. Гипотезы «мешка слов» и «мешка документов». Текст как простая выборка, порождаемая вероятностным распределением. Векторное представление документа как эмпирическое распределение.
- Понятие параметрической порождающей модели. Принцип максимума правдоподобия.
- Униграммная модель документов и коллекции.
- Ликбез. Теорема Куна-Таккера.
- Аналитическое решение задачи о стационарной точке функции Лагранжа. Частотные оценки условных вероятностей.
Литература: [Маннинг 2011].
Вероятностный латентный семантический анализ
- Напоминания. Коллекция текстовых документов. Векторное представление документа. Задачи информационного поиска и классификации текстов.
Мотивации вероятностного тематического моделирования
- Идея понижения размерности: переход от вектора (терминов) к вектору тем.
- Цели тематического моделирования: разведочный поиск научной информации, навигация и систематизация, агрегирование новостных потоков, классификация и категоризация текстов, обход проблем синонимии и омонимии.
Задача тематического моделирования.
- Вероятностное пространство. Тема как латентная (ненаблюдаемая) переменная. Гипотеза условной независимости. Порождающая модель документа как вероятностной смеси тем.
- Постановка обратной задачи восстановления параметров модели по данным.
Вероятностный латентный семантический анализ (PLSA).
- Принцип максимума правдоподобия, аналитическое решение задачи о стационарной точке функции Лагранжа, формулы M-шага.
- Элементарная интерпретация ЕМ-алгоритма: Е-шаг как формула Байеса для апостериорной вероятности темы, М-шаг как частотные оценки условных вероятностей.
- Рациональный ЕМ-алгоритм (встраивание Е-шага внутрь М-шага).
Онлайновый ЕМ-алгоритм (OEM).
- Проблема больших данных.
- Эвристика разделения М-шага.
- Эвристика разделения коллекции на пачки документов.
- Добавление новых документов (folding-in).
Проведение экспериментов на модельных данных.
- Процесс порождения терминов в документе. Генератор модельных (синтетических) данных. Генерация случайной величины из заданного дискретного распределения.
- Распределение Дирихле. Генерация разреженных и сглаженных векторов дискретных распределений из распределения Дирихле.
- Оценивание точности восстановления модельных данных. Расстояние между дискретными распределениями. Проблема перестановки тем, венгерский алгоритм.
- Проблема неединственности и неустойчивости матричного разложения. Экспериментальное оценивание устойчивости решения.
Задание 1.1 Обязательные пункты: 1–3 и любой из последующих.
- Реализовать генератор модельных данных. Реализовать вычисление эмпирических распределений терминов тем и тем документов.
- Реализовать оценку точности восстановления с учётом перестановки тем. Вычислить оценку точности для исходных модельных распределений.
- Реализовать рациональный ЕМ-алгоритм.
- Исследовать зависимости точности модели и точности восстановления от числа итераций и от числа тем в модели (при фиксированном числе тем в исходных данных). Что происходит, когда тем больше, чем нужно? Меньше, чем нужно?
- Исследовать влияние случайного начального приближения на устойчивость решения. Построить эмпирические распределения и доверительные интервалы для расстояний Хеллингера между истинными матрицами и восстановленными.
- Исследовать влияние разреженности матриц Фи и Тета на устойчивость решения.
- Исследовать полноту решения. Сколько запусков со случайным начальным приближением необходимо сделать, чтобы найти все исходные темы? Как различность и разреженность исходных тем влияет на полноту?
Литература: [Hofmann 1999].
Латентное размещение Дирихле
- Напоминания. Задача тематического моделирования коллекции текстовых документов. Модель PLSA, формулы Е-шага и М-шага.
Латентное размещение Дирихле (LDA)
- Свойства распределения Дирихле.
- Принцип максимума апостериорной вероятности. Модифицированные формулы М-шага.
- Байесовский вывод. Свойство сопряжённости мультиномиального распределения и распределения Дирихле. Другие модифицированные формулы М-шага.
- Обзор модификаций формул М-шага.
- Методы оптимизации гиперпараметров.
- Небайесовская интерпретация модели LDA.
- Сравнение LDA и PLSA. Экспериментальные факты: LDA скорее улучшает оценки редких слов, чем снижает переобучение.
Стохастический ЕМ-алгоритм (SEM).
- Гипотеза разреженности апоcтериорного распределения тем p(t|d,w).
- Эвристика сэмплирования. Алгоритм сэмплирования Гиббса.
Робастные тематические модели.
- Робастная модель с фоном и шумом.
- Упрощённая робастная модель.
- Почему робастный PLSA лучше, чем LDA. Эффект повышения правдоподобия (перплексии) в робастных моделях с шумом.
Способы формирования начальных приближений.
- Случайная инициализация.
- Инициализация по документам.
- Контекстная документная кластеризация.
- Поиск якорных слов. Алгоритм Ароры.
Задание 1.2 Обязательные пункты: 1 и любой из последующих.
- Реализовать онлайновый алгоритм OEM.
- Исследовать влияние размера первой пачки и последующих пачек на качество модели.
- Исследовать влияние выбора числа итераций на внутреннем и внешнем циклах алгоритма OEM на качество и скорость построения модели.
- Исследовать возможность улучшения качества модели с помощью второго прохода по коллекции (без инициализации p(w|t)).
- Исследовать влияние гиперпараметров на правдоподобие модели и точность восстановления.
Литература: [Hoffman 2010], [Asuncion 2009].
Аддитивная регуляризация тематических моделей
- Напоминания. Вероятностная тематическая модель. Принцип максимума правдоподобия. PLSA. EM-алгоритм.
Многокритериальная регуляризация.
- Некорректность постановки задачи тематического моделирования.
- Аддитивная регуляризация тематических моделей.
- Вывод формулы M-шага для регуляризованного ЕМ-алгоритма.
- Проект BigARTM.
Регуляризаторы сглаживания и разреживания.
- Максимизация и минимизация KL-дивергенции.
- Альтернативный вариант разреживания через L0-регуляризацию.
- Связь разреженности и единственности неотрицательного матричного разложения.
- Разреживание предметных тем и сглаживание фоновых тем. Автоматическое выделение стоп-слов.
Регуляризаторы частичного обучения.
- Частичное обучение как выборочное сглаживание.
- Сфокусированные тематические модели. Использование словаря для выделения предметных тем.
- Пример: выделение тематики эпидемий, этнических конфликтов.
Ковариационные регуляризаторы.
- Дековариация тем.
- Тематические модели цитирования.
- Задача выявления корреляций между темами, модель CTM.
- Оценивание параметров (матрицы ковариаций) в модели CTM.
Регуляризаторы для классификации и регрессии.
- Задачи регрессии на текстах. Примеры. Регуляризатор. Формула М-шага.
- Задачи классификации текстов. Примеры. Регуляризатор. Формула М-шага.
Задание 1.3 Обязательные пункты: 1 и любой из остальных.
- Реализовать разреживание в онлайновом алгоритме OEM.
- Исследовать зависимость правдоподобия модели и точности восстановления от степени разреженности исходных модельных данных.
- Исследовать влияние разреживания на правдоподобие модели и точность восстановления. Проверить гипотезу, что если исходные данные разрежены, то разреживание существенно улучшает точность восстановления и слабо влияет на правдоподобие модели.
- Исследовать влияние частичной разметки на правдоподобие модели и точность восстановления. Проверить гипотезу, что небольшой доли правильно размеченных документов уже достаточно для существенного улучшения правдоподобия и устойчивости модели.
- Исследовать влияние сглаживания на правдоподобие модели и точность восстановления.
Литература: [Воронцов, 2013, 2015], [Chemudugunta, 2006].
Оценивание качества тематических моделей
Реальные данные.
- Текстовые коллекции, библиотеки алгоритмов, источники информации.
- Внутренние и внешние критерии качества.
- Дополнительные данные для построения внешних критериев качества.
Перплексия и правдоподобие.
- Определение и интерпретация перплекcии.
- Перплексия контрольной коллекции. Проблема новых слов в контрольной коллекции.
- Проблема сравнения моделей с разными словарями.
- Относительная перплексия.
Оценивание качества темы.
- Лексическое ядро темы: множество типичных терминов темы.
- Чистота и контрастность темы
- Документное ядро темы: множество типичных документов темы.
- Однородность темы: распределение расстояний между p(w|t) и p(w|t,d).
- Конфликтность темы: близость темы к другим темам.
Статистические тесты условной независимости.
- Методология проверки статистических гипотез. Критерий согласия хи-квадрат Пирсона.
- Проблема разреженности распределения. Эксперименты, показывающие неадекватность асимптотического распределения статистики хи-квадрат.
- Статистики модифицированного хи-квадрат, Кульбака-Лейблера, Хеллингера.
- Обобщённое семейство статистик Кресси-Рида.
- Эмпирическое оценивание квантилей распределения статистики Кресси-Рида.
- Применения теста условной независимости для поиска плохо смоделированных тем, документов, терминов. Поиск тем для расщепления.
Литература: [Newman, 2009–2011].
Внешние оценки качества тематических моделей
Оценивание интерпретируемости тем.
- Экспертное оценивание интерпретируемости.
- Асессорская разметка терминов и документов, релевантных теме.
- Метод интрузий.
- Радикальное улучшение интерпретируемости в n-граммных тематических моделях.
Когерентность.
- Определение когерентности.
- Эксперименты, показывающие связь когерентности и интерпретируемости.
- Способы оценивания совместной встречаемости слов.
Суммаризация темы.
- Проблема визуализации тем.
- Выделение тематичных слов и предложений.
- Кластеризация тематичных предложений.
- Ранжирование тематичных предложений.
- Асессорская разметка предложений, релевантных теме.
- Задача автоматического именования темы.
Критерии качества классификации и ранжирования.
- Полнота, точность и F-мера в задачах классификации и ранжирования.
- Критерии качества ранжирования: MAP, DCG, NDCG.
- Оценка качества тематического поиска документов по их длинным фрагментам.
Задание 1.4.
- Применить OEM к реальным коллекциям.
- Исследовать на реальных данных зависимость внутренних и внешних критериев качества от эвристических параметров алгоритма обучения OEM.
- В экспериментах на реальных данных построить зависимости перплексии обучающей и контрольной коллекции от числа итераций и числа тем.
Литература:
Мультимодальные регуляризованные тематические модели
- Напоминания. Аддитивная регуляризация тематических моделей.
Мультимодальная АРТМ.
- Виды модальностей и примеры прикладных задач.
- Вывод формул М-шага.
- Тематическая модель классификации. Пример: Технология информационного анализа электрокардиосигналов.
- Тематическая модель текста и изображений.
- Задача аннотирования изображений.
Мультиязычные тематические модели.
- Параллельные и сравнимые коллекции.
- Регуляризаторы для учёта двуязычных словарей.
Модели многоматричных разложений.
- Понятие порождающей модальности.
- Вывод формул М-шага.
- Автор-тематическая модель (author-topic model).
- Модель для выделения поведений объектов в видеопотоке.
Гиперграфовая модель.
- Примеры транзакционных данных в социальных и рекламных сетях.
- Вывод формул М-шага.
Литература:
Определение числа тем и иерархические модели
Регуляризатор энтропийного разреживания.
- Регуляризатор и формула М-шага. Эффект строкового разреживания.
- Определение истинного числа тем в экспериментах с полумодельными данными.
- Гипотеза о несуществовании истинного числа тем.
- Эффект отбрасывания малых, дублирующих и линейно зависимых тем.
- Сравнение с моделью иерархических процессов Дирихле.
Тематическая модель с фиксированной иерархией.
- Задачи категоризации текстов. Стандартный метод решения — сведение к последовательности задач классификации.
- Необходимость частичного обучения для задачи категоризации.
- Вероятностная формализация отношения «тема–подтема». Тождества, связывающие распределения тем и подтем
- Задача построения разреженного иерархического тематического профиля документа.
Послойное нисходящее построение тематической иерархии.
- Регуляризатор матрицы Фи.
- Регуляризатор матрицы Тета.
- Измерение и оптимизация качества иерархических моделей.
- Разреживание вероятностного отношения тема—подтема.
Одновременное построение всех слоёв тематической иерархии.
Литература: .
Тематические модели, учитывающие порядок слов
Мультиграммные модели.
- Задача выделения терминов как ключевых фраз (словосочетаний). Словари терминов.
- Морфологический и синтаксический анализ текста.
- Отбор фраз с подчинительными связями.
- Отбор фраз по статистическому критерию коллокации C-Value. Совмещение критериев TF-IDF и CValue.
- Отбор фраз по оценке тематичности.
- Задача сокращения словаря (vocabulary reduction) и проблема сравнения моделей с разными словарями.
Регуляризаторы для выделения энграмм.
- Биграммная тематическая модель.
Сегментирующие тематические модели.
- Позиционный регуляризатор, вывод формул М-шага.
- Пост-обработка Е-шага.
- Интерпретация текста как пучка временных рядов и задача разладки.
- Алгоритм тематической сегментации.
- Тематические модели предложений (sentence topic model).
Векторная модель word2vec.
- Векторная модель word2vec и её интерпретация как латентной модели с матричным разложением.
- Гибрид тематической модели и векторной модели word2vec.
- Связь word2vec с регуляризатором когерентности.
- Эксперименты с гибридной моделью W2V-TM.
Литература: .
Динамические и пространственные тематические модели
Тематические модели с модальностью времени.
- Регуляризатор разреживания тем в каждый момент времени.
- Регуляризаторы сглаживания темы как временного ряда.
- Вывод M-шага для негладкого регуляризатора.
Тематические модели с модальностью геолокации.
- Тематические модели социальных сетей.
Траектории регуляризации
Обучение с подкреплением
- Контекстный многорукий бандит.
- Инкрементная регрессия.
- Регрессия с верхними доверительными границами (UCB).
Задача оптимизации трактории в пространстве коэффициентов регуляризации
- Относительные коэффициенты регуляризации.
- Признаковое описание контекста. Метрики качества тематической модели.
- Функция премии и скаляризация критериев.
- Особенности реализации обучения с подкреплением в онлайновом ЕМ-алгоритме.
Визуализация тематических моделей
Навигация по тематической модели.
- Визуализатор TMVE.
- Визуализатор Termite.
- Визуализатор для BigARTM.
Методы визуализации.
- Задача и методы многомерного шкалирования.
- Визуализация «дорожной карты» темы или набора тем.
- Визуализация тематических иерархий.
- Визуализация динамических моделей, метафора «реки тем».
- Визуализация тематической структуры документа.
- Визуализация модели трёх источников.
Средства разведочного поиска.
- Концепция пользовательского интерфейса для разведочного поиска.
- Оценивание качества разведочного информационного поиска.
- Концепция иерархической суммаризации.
Большие данные
Параллельные и распределённые алгоритмы.
- Обзор подходов к распараллеливанию онлайнового EМ-алгоритма.
- Распараллеливание онлайнового EМ-алгоритма в BigARTM.
- Распределённое хранение коллекции.
Обработка больших коллекций в BigARTM.
- Особенности предварительной обработки.
- Коллекция Википедии.
- Коллекция arXiv.org.
- Коллекция социальной сети VK.
Литература
Основная литература
- Воронцов К.В. Тематическое моделирование в BigARTM: теория, алгоритмы, приложения. Voron-2015-BigARTM.pdf.
- Воронцов К.В. Лекции по тематическому моделированию. Voron-2013-ptm.pdf.
- 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. Русский перевод
Дополнительная литература
- Воронцов К. В., Потапенко А. А. Модификации EM-алгоритма для вероятностного тематического моделирования // Машинное обучение и анализ данных. — 2013. — T. 1, № 6. — С. 657–686.
- Воронцов К. В., Фрей А. И., Ромов П. А., Янина А. О., Суворова М. А., Апишев М. А. BigARTM: библиотека с открытым кодом для тематического моделирования больших текстовых коллекций // Аналитика и управление данными в областях с интенсивным использованием данных. XVII Международная конференция DAMDID/RCDL’2015, Обнинск, 13-16 октября 2015.
- Маннинг К., Рагхаван П., Шютце Х. Введение в информационный поиск. — Вильямс, 2011.
- 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.
- Blei D. M., Ng A. Y., Jordan M. I. Latent Dirichlet allocation // Journal of Machine Learning Research. — 2003. — Vol. 3. — Pp. 993–1022.
- 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.
- 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.
- 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.
- 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.
- Hoffman M. D., Blei D. M., Bach F. R. Online Learning for Latent Dirichlet Allocation // NIPS, 2010. Pp. 856–864.
- 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.
- 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.
- 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
- Видеозапись лекции на ТМШ, 19 июня 2015
Ретроспектива
Вероятностные тематические модели (курс лекций, К.В.Воронцов)/2015 | Вероятностные тематические модели (курс лекций, К.В.Воронцов)/2016 | Вероятностные тематические модели (курс лекций, К.В.Воронцов)/2017 |
Вероятностные тематические модели (курс лекций, К.В.Воронцов)/2018 | Вероятностные тематические модели (курс лекций, К.В.Воронцов)/2019, ВМК | Вероятностные тематические модели (курс лекций, К.В.Воронцов)/2020 |
Вероятностные тематические модели (курс лекций, К.В.Воронцов)/2021 |