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

Содержание 1 Программа курса 1.1 Задачи анализа текстов. Вероятностные модели коллекций текстов 1.2 Вероятностный латентный семантический анализ 1.3 Модификации алгоритма обучения модели PLSA 1.4 Аддитивная регуляризация тематических моделей 1.5 Разреживание и сглаживание 1.6 Внутренние методы оценивания качества 1.7 Внешние методы оценивания качества 1.8 Робастные тематические модели 1.9 Синтаксические тематические модели 1.10 Регуляризация для задач классификации 1.11 Динамические тематические модели 1.12 Иерархические тематические модели 1.13 Многоязычные тематические модели 1.14 Многомодальные тематические модели 1.15 Распараллеливание алгоритмов обучения тематических моделей 1.16 Литература 1.17 Ссылки 1.18 См. также

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Модификации алгоритма обучения модели PLSA

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

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

• Сглаженные байесовские оценки условных вероятностей.

Робастный ЕМ-алгоритм (REM).

• Робастная модель с шумом и фоном.
• Упрощённая робастная модель.

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

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

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

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

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

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

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

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

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

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

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

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

• Некорректность постановки задачи тематического моделирования.
• Аддитивная регуляризация.
• Общая формула M-шага для регуляризованного ЕМ-алгоритма.

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

• Гипотеза разреженности распределений терминов тем и тем документов.
• Энтропийный регуляризатор и максимизация KL-дивергенции.
• Связь разреживания с L0-регуляризацией и методом разреживания нейронных сетей Optimal Brain Damage.
• Связь разреженности и единственности неотрицательного матричного разложения.

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

• Модель латентного размещения Дирихле LDA.
• Обоснование LDA через минимизацию KL–дивергенции. Виды сглаживающих распределений.
• Свойства распределения Дирихле, сопряжённость с мультиномиальным распределением.
• Байесовский вывод. Сглаженные частотные оценки условных вероятностей.
• Оценки максимума апостериорной вероятности.
• Численные методы оптимизации гиперпараметров.

Комбинирование разреживания и сглаживания.

• Разреживание предметных тем и сглаживание фоновых тем. Автоматическое выделение стоп-слов.
• Частичное обучение как выборочное сглаживание.

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

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

Разреживание и сглаживание

Сглаживание

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

Частичное обучение (Semi-supervised EM).

• Виды частично размеченных данных: привязка документа к темам, привязка термина к темам, нерелевантность, переранжирование списков терминов тем и тем документов, виртуальные документы.
• Использование частично размеченных данных для инициализации.
• Использование частично размеченных данных в качестве поправок на М-шаге ЕМ-алгоритма.

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

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

Литература: [Blei, 2003].

Внутренние методы оценивания качества

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

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

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

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

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

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

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

• Контрастность темы (число типичных документов темы, число типичных терминов темы).
• Пиковость темы.
• Однородность (радиус) темы.
• Конфликтность темы (близость темы к другим темам).

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

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

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

Внешние методы оценивания качества

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

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

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

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

Задание 1.4.

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

Литература: [Blei, 2003].

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

Робастность — устойчивость модели к нарушениям исходных предпосылок, заложенных в основу модели.

Робастная тематическая модель с фоном и шумом

• Аналитическое решение задачи о стационарной точке функции Лагранжа, формулы M-шага.
• Аддитивный и мультипликативный М-шаг.
• Оценки тематичности слов.
• Эксперименты: робастная модель не нуждается в регуляризации и более устойчива к разреживанию.

Разреженная робастная тематическая модель с шумом

• Максимизация правдоподобия для упрощённой робастной модели.
• Вычисление перплексии для упрощённой робастной модели.

Робастная тематическая модель с усечёнными распределениями

• Явления синонимии, взаимной заменяемости терминов, эффект burstiness.
• Гипотеза об усечённых распределениях терминов тем в документах как ослабление гипотезы условной независимости.
• Аналитическое решение задачи о стационарной точке функции Лагранжа. Модификация ЕМ-алгоритма.

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

1. Реализовать генерацию модельных данных с фоном и шумом.
2. Реализовать робастный алгоритм OEM.
3. Исследовать зависимость точности робастной модели и точности восстановления от параметров априорной вероятности фона и шума. Что происходит с точностью модели, когда эти параметры «плохо угаданы»?
4. Исследовать возможность оптимизации параметров априорной вероятности шума и фона.
5. Исследовать зависимость перплексии и качества поиска от априорной вероятности шума.
6. Исследовать влияние разреживания тематической компоненты робастной модели на перплексию и качество поиска.

Литература: [Chemudugunta, 2006].

Синтаксические тематические модели

Энграммные модели.

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

Марковские модели синтаксиса.

• Коллокации
• Оценивание матрицы переходных вероятностей.

Регуляризация для задач классификации

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

Простейшие модели.

• Примеры классов: годы, авторы, категории, и т.д.
• Моделирование классов темами.
• Моделирование классов распределениями тем.
• Автор-тематическая модель.
• Многоклассовые задачи. Частотный регуляризатор.

Тематическая модель классификации.

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

Динамические тематические модели

Модели с дискретным временем.

• Модель с фиксированной тематикой.
• Модель с медленно меняющейся тематикой.

Модели с непрерывным временем.

Иерархические тематические модели

• Задачи категоризации текстов. Стандартный метод решения — сведение к последовательности задач классификации.

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

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

Сетевые иерархические модели.

• Возможность для темы иметь несколько родительских тем.
• Дивергенция Кульбака–Лейблера. Свойства KL-дивергенции.
• Интерпретация KL-дивергенции как степени вложенности распределений. Оценивание силы связей «тема-подтема» KL-дивергенцией.
• Дополнение тематического дерева до тематической сети.

Иерархические процессы Дирихле.

• Оптимизация числа тем в плоской модели.
• Создание новых тем в иерархических моделях.
• Нисходящие и восходящие иерархические модели.

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

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

Многомодальные тематические модели

• Коллаборативная фильтрация.
• Модель научной социальной сети.
• Персонализация рекламы в Интернете.

Распараллеливание алгоритмов обучения тематических моделей

• Основы Map-Reduce
• Распределённое хранение коллекции.

Литература

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

1. Маннинг К., Рагхаван П., Шютце Х. Введение в информационный поиск. — Вильямс, 2011.
2. 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.
3. 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. Воронцов К. В., Потапенко А. А. Регуляризация, робастность и разреженность вероятностных тематических моделей // Компьютерные исследования и моделирование 2012 Т. 4, №12. С 693–706.
2. Vorontsov K. V., Potapenko A. A. Tutorial on Probabilistic Topic Modeling: Additive Regularization for Stochastic Matrix Factorization // AIST'2014, Analysis of Images, Social networks and Texts. — Lecture Notes in Computer Science (LNCS), Springer Verlag-Germany, 2014, Vol. CCIS 439. Pp. 28–45.
3. Vorontsov K. V., Potapenko A. A. Additive Regularization of Topic Models // Machine Learning Journal, Special Issue «Data Analysis and Intelligent Optimization», Springer, 2014.
4. Blei D. M., Ng A. Y., Jordan M. I. Latent Dirichlet allocation // Journal of Machine Learning Research. — 2003. — Vol. 3. — Pp. 993–1022.
5. 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.
6. 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.
7. 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.
8. Hoffman M. D., Blei D. M., Bach F. R. Online Learning for Latent Dirichlet Allocation // NIPS, 2010. Pp. 856–864.
9. 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.
10. 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.
11. Zavitsanos E., Paliouras G., Vouros G. A. Non-parametric estimation of topic hierarchies from texts with hierarchical Dirichlet processes // Journal of Machine Learning Research. — 2011. — Vol. 12. — Pp. 2749–2775.

Ссылки

• Тематическое моделирование
• Конспект лекций: Voron-2013-ptm.pdf, 2.6 МБ (обновление 16 октября 2013).
• Презентация доклада на семинаре в ВИНИТИ РАН, 23 апреля 2013. (PDF, 2.0 МБ).

См. также

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