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

Версия 07:39, 26 февраля 2014

Спецкурс читается студентам 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 МБ).

См. также

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