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

Содержание 1 Программа курса 1.1 Часть 1 1.1.1 Задачи анализа текстов. Вероятностные модели коллекций текстов 1.1.2 Вероятностный латентный семантический анализ 1.1.3 Модификации алгоритма обучения модели PLSA 1.1.4 Разреживание и сглаживание 1.1.5 Внутренние методы оценивания качества 1.1.6 Внешние методы оценивания качества 1.1.7 Робастные тематические модели 1.2 Часть 2 1.2.1 Аддитивная регуляризация тематических моделей 1.2.2 Синтаксические тематические модели 1.2.3 Регуляризация для задач классификации 1.2.4 Динамические тематические модели 1.2.5 Иерархические тематические модели 1.2.6 Многоязычные тематические модели 1.2.7 Многомодальные тематические модели 1.2.8 Распараллеливание алгоритмов обучения тематических моделей 1.3 Литература 1.4 Ссылки 1.5 См. также

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

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

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

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

Часть 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задание для 4 курса ФУПМ: voron-2014-task-PTM.pdf

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

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

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

Обобщённый ЕМ-алгоритм (GEM).

• Проблема медленной сходимости EM-алгоритма на больших коллекциях. Проблема хранения трёхмерных матриц.
• Эвристика частых обновлений параметров.
• Эвристика замены средних экспоненциальным сглаживанием.

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

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

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

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

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

• Случайная инициализация.
• Инициализация по документам.

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

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

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

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

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

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

Разреживание

• Эмпирические законы Ципфа, Ципфа-Мандельброта, Хипса.
• Гипотеза разреженности распределений терминов тем и тем документов.
• Принудительное разреживание в ЕМ-алгоритме. Оценка значимости (salience) параметров, метод Optimal Brain Damage.
• Выделение нетематических терминов.
• Генерация реалистичных модельных данных.
• Связь разреженности и единственности неотрицательного матричного разложения.

Сглаживание

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

Задание 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].

Часть 2

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

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

Тихоновская регуляризация.

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

Сглаживание и разреживание.

• Сглаживание. Альтернативное обоснование LDA через регуляризатор–дивергенцию.
• Разреживание. Энтропийный регуляризатор.
• Частичное обучение как выборочное сглаживание.

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

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

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

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

• Задача выделения терминов как ключевых фраз (словосочетаний). Словари терминов.
• Морфологический анализ текста.
• Синтаксический анализ текста. Выявление подчинительных связей.
• Статистические методы поиска коллокаций. Критерий 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. Blei D. M., Ng A. Y., Jordan M. I. Latent Dirichlet allocation // Journal of Machine Learning Research. — 2003. — Vol. 3. — Pp. 993–1022.
3. 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.
4. 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.
5. 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.
6. Hoffman M. D., Blei D. M., Bach F. R. Online Learning for Latent Dirichlet Allocation // NIPS, 2010. Pp. 856–864.
7. 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.
8. 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.
9. 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 МБ).

См. также

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