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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Вероятностный латентный семантический анализ)
Строка 2: Строка 2:
Спецкурс читается студентам 2—5 курсов на кафедре «[[Математические методы прогнозирования (кафедра ВМиК МГУ)|Математические методы прогнозирования]]» [[ВМиК]] [[МГУ]] с 2013 года.
Спецкурс читается студентам 2—5 курсов на кафедре «[[Математические методы прогнозирования (кафедра ВМиК МГУ)|Математические методы прогнозирования]]» [[ВМиК]] [[МГУ]] с 2013 года.
 +
 +
В спецкурсе изучаются методы построения вероятностных тематических моделей (topic modeling) коллекций текстовых документов. Развивается многокритериальный подход к решению некорректно поставленной задачи стохастического матричного разложения — аддитивная регуляризации тематических моделей. Особое внимание будет уделяется комбинированию статистических и лингвистических методов анализа текстов. Рассматриваются прикладные задачи классификации и категоризации текстов, информационного поиска, персонализации и рекомендательных систем, а также задачи анализа и классификации дискретизированных биомедицинских сигналов. Предполагается проведение студентами численных экспериментов на модельных и реальных данных.
От студентов требуются знания курсов линейной алгебры, математического анализа, теории вероятностей. Знание математической статистики, методов оптимизации и какого-либо языка программирования желательно, но не обязательно.
От студентов требуются знания курсов линейной алгебры, математического анализа, теории вероятностей. Знание математической статистики, методов оптимизации и какого-либо языка программирования желательно, но не обязательно.
Строка 8: Строка 10:
= Программа курса =
= Программа курса =
-
 
-
== Часть 1 ==
 
=== Задачи анализа текстов. Вероятностные модели коллекций текстов ===
=== Задачи анализа текстов. Вероятностные модели коллекций текстов ===
Строка 15: Строка 15:
'''Задачи классификации текстов.'''
'''Задачи классификации текстов.'''
* Коллекция текстовых документов. Векторное представление документа.
* Коллекция текстовых документов. Векторное представление документа.
-
* Постановка задачи классификации текстов. Объекты, признаки, классы, обучающая выборка. Распознавание текстов заданной тематики. Анализ тональности. Частоты слов (терминов) как признаки. Линейный классификатор.
+
* Эмпирические законы Ципфа, Ципфа-Мандельброта, Хипса.
 +
* Постановка задачи классификации текстов. Объекты, признаки, классы, обучающая выборка.
 +
* Частоты слов (терминов) как признаки. Распознавание текстов заданной тематики. Анализ тональности.
 +
* Линейный классификатор. Наивный байесовский классификатор.
* Задача распознавание жанра текстов. Распознавание научных текстов. Примеры признаков.
* Задача распознавание жанра текстов. Распознавание научных текстов. Примеры признаков.
* Задача категоризации текстов, сведение к последовательности задач классификации.
* Задача категоризации текстов, сведение к последовательности задач классификации.
'''Задачи предварительной обработки текстов.'''
'''Задачи предварительной обработки текстов.'''
-
* Очистка: удаление номеров страниц, переносов, опечаток, нетекстовой информация, оглавлений, таблиц, рисунков.
+
* Очистка, удаление номеров страниц (колонтитулов), переносов, опечаток, оглавлений, таблиц, рисунков, нетекстовой информации.
-
* Лемматизация и стемминг.
+
* Лемматизация и стемминг. Сравнение готовых инструментальных средств.
-
* Удаление стоп-слов. Удаление редких слов.
+
* Выделение и удаление стоп-слов и редких слов.
'''Задачи информационного поиска.'''
'''Задачи информационного поиска.'''
-
* Задача поиска документов по запросу. Инвертированный индекс. Косинусная мера сходства.
+
* Задача поиска документов по запросу. Инвертированный индекс.
 +
* Меры сходства векторов частот. Косинусная мера сходства. Расстояние Хеллингера.
* Критерий текстовой релевантности TF-IDF. Вероятностная модель и вывод формулы TF-IDF.
* Критерий текстовой релевантности TF-IDF. Вероятностная модель и вывод формулы TF-IDF.
* Задача ранжирования. Примеры признаков. Формирование асессорских обучающих выборок.
* Задача ранжирования. Примеры признаков. Формирование асессорских обучающих выборок.
Строка 32: Строка 36:
* Вероятностное пространство. Гипотезы «мешка слов» и «мешка документов». Текст как простая выборка, порождаемая вероятностным распределением. Векторное представление документа как эмпирическое распределение.
* Вероятностное пространство. Гипотезы «мешка слов» и «мешка документов». Текст как простая выборка, порождаемая вероятностным распределением. Векторное представление документа как эмпирическое распределение.
* Понятие параметрической порождающей модели. Принцип максимума правдоподобия.
* Понятие параметрической порождающей модели. Принцип максимума правдоподобия.
-
* Униграммная модель документов и коллекции. Аналитическое решение задачи о стационарной точке функции Лагранжа. Частотные оценки условных вероятностей.
+
* Униграммная модель документов и коллекции.
 +
* ''Ликбез.'' Теорема Куна-Таккера.
 +
* Аналитическое решение задачи о стационарной точке функции Лагранжа. Частотные оценки условных вероятностей.
-
'''Литература:''' [Маннинг, 2011].
+
'''Литература:''' [Маннинг 2011].
=== Вероятностный латентный семантический анализ ===
=== Вероятностный латентный семантический анализ ===
Строка 44: Строка 50:
'''Задача тематического моделирования.'''
'''Задача тематического моделирования.'''
-
* Вероятностное пространство. Тема как латентная (скрытая) переменная. Представление темы дискретным распределением на множестве слов.
+
* Вероятностное пространство. Тема как латентная (ненаблюдаемая) переменная. Гипотеза условной независимости. Порождающая модель документа как вероятностной смеси тем.
-
* Модель смеси униграмм. Недостаток: каждый документ принадлежит только одной теме.
+
-
* Представление документа дискретным распределением на множестве тем. Гипотеза условной независимости. Порождающая модель документа как вероятностной смеси тем.
+
* Постановка обратной задачи восстановления параметров модели по данным.
* Постановка обратной задачи восстановления параметров модели по данным.
Строка 56: Строка 60:
'''Проведение экспериментов на модельных данных.'''
'''Проведение экспериментов на модельных данных.'''
* Процесс порождения терминов в документе. Генератор модельных (синтетических) данных. Генерация случайной величины из заданного дискретного распределения.
* Процесс порождения терминов в документе. Генератор модельных (синтетических) данных. Генерация случайной величины из заданного дискретного распределения.
 +
* Распределение Дирихле. Генерация разреженных и сглаженных векторов дискретных распределений из распределения Дирихле.
* Оценивание точности восстановления модельных данных. Расстояние между дискретными распределениями. Проблема перестановки тем, венгерский алгоритм.
* Оценивание точности восстановления модельных данных. Расстояние между дискретными распределениями. Проблема перестановки тем, венгерский алгоритм.
* Проблема неединственности и неустойчивости матричного разложения. Экспериментальное оценивание устойчивости решения.
* Проблема неединственности и неустойчивости матричного разложения. Экспериментальное оценивание устойчивости решения.
Строка 65: Строка 70:
# Реализовать рациональный ЕМ-алгоритм.
# Реализовать рациональный ЕМ-алгоритм.
# Исследовать зависимости точности модели и точности восстановления от числа итераций и от числа тем в модели (при фиксированном числе тем в исходных данных). Что происходит, когда тем больше, чем нужно? Меньше, чем нужно?
# Исследовать зависимости точности модели и точности восстановления от числа итераций и от числа тем в модели (при фиксированном числе тем в исходных данных). Что происходит, когда тем больше, чем нужно? Меньше, чем нужно?
-
# Исследовать влияние случайного начального приближения на точность модели и точность восстановления. Построить для них эмпирические распределения и доверительные интервалы. Можно ли утверждать, что EM-алгоритм всегда сходится к одному и тому же решению?
+
# Исследовать влияние случайного начального приближения на устойчивость решения. Построить эмпирические распределения и доверительные интервалы для расстояний Хеллингера между истинными матрицами и восстановленными.
-
# Исследовать, когда проблема неустойчивости возникает, когда не возникает.
+
# Исследовать влияние разреженности матриц Фи и Тета на устойчивость решения.
'''Задание для 4 курса ФУПМ:''' [[Media:voron-2014-task-PTM.pdf|voron-2014-task-PTM.pdf]]
'''Задание для 4 курса ФУПМ:''' [[Media:voron-2014-task-PTM.pdf|voron-2014-task-PTM.pdf]]
-
'''Литература:''' [Hofmann, 1999].
+
'''Литература:''' [Hofmann 1999].
===Модификации алгоритма обучения модели PLSA===
===Модификации алгоритма обучения модели PLSA===
Строка 76: Строка 81:
* ''Напоминания.'' Задача тематического моделирования коллекции текстовых документов. Модель PLSA, формулы Е-шага и М-шага.
* ''Напоминания.'' Задача тематического моделирования коллекции текстовых документов. Модель PLSA, формулы Е-шага и М-шага.
-
'''Обобщённый ЕМ-алгоритм (GEM).'''
+
'''Латентное размещение Дирихле (LDA)'''
-
* Проблема медленной сходимости EM-алгоритма на больших коллекциях. Проблема хранения трёхмерных матриц.
+
* Сглаженные байесовские оценки условных вероятностей.
-
* Эвристика частых обновлений параметров.
+
 
-
* Эвристика замены средних экспоненциальным сглаживанием.
+
'''Робастный ЕМ-алгоритм (REM).'''
 +
* Робастная модель с шумом и фоном.
 +
* Упрощённая робастная модель.
'''Стохастический ЕМ-алгоритм (SEM).'''
'''Стохастический ЕМ-алгоритм (SEM).'''
* Гипотеза разреженности апоcтериорного распределения тем p(t|d,w).
* Гипотеза разреженности апоcтериорного распределения тем p(t|d,w).
-
* Эвристика замены апостериорного распределения его несмещённой оценкой.
 
* Алгоритм сэмплирования Гиббса.
* Алгоритм сэмплирования Гиббса.
-
* Эксперименты по подбору оптимального числа сэмплирований.
 
'''Онлайновый ЕМ-алгоритм (OEM).'''
'''Онлайновый ЕМ-алгоритм (OEM).'''
Строка 96: Строка 101:
* Случайная инициализация.
* Случайная инициализация.
* Инициализация по документам.
* Инициализация по документам.
-
 
+
* Поиск якорных слов. Алгоритм Ароры.
-
'''Частичное обучение (Semi-supervised EM).'''
+
-
* Виды частично размеченных данных: привязка документа к темам, привязка термина к темам, нерелевантность, переранжирование списков терминов тем и тем документов, виртуальные документы.
+
-
* Использование частично размеченных данных для инициализации.
+
-
* Использование частично размеченных данных в качестве поправок на М-шаге ЕМ-алгоритма.
+
'''Задание 1.2'''
'''Задание 1.2'''
Строка 110: Строка 111:
# Исследовать влияние частичной разметки на точность модели и точность восстановления. Проверить гипотезу, что небольшой доли правильно размеченных документов уже достаточно для существенного улучшения точности и устойчивости модели.
# Исследовать влияние частичной разметки на точность модели и точность восстановления. Проверить гипотезу, что небольшой доли правильно размеченных документов уже достаточно для существенного улучшения точности и устойчивости модели.
-
'''Литература:''' [Hoffman, 2010].
+
'''Литература:''' [Hoffman 2010, Asuncion 2009].
-
===Разреживание и сглаживание===
+
===Аддитивная регуляризация тематических моделей===
 +
* ''Напоминания''. Вероятностная тематическая модель. Принцип максимума правдоподобия. PLSA. EM-алгоритм.
 +
* ''Ликбез''. KL-дивергенция.
-
'''Разреживание'''
+
'''Многокритериальная регуляризация.'''
-
* Эмпирические законы Ципфа, Ципфа-Мандельброта, Хипса.
+
* Некорректность постановки задачи тематического моделирования.
 +
* Аддитивная регуляризация.
 +
* Общая формула M-шага для регуляризованного ЕМ-алгоритма.
 +
 
 +
'''Регуляризатор разреживания.'''
* Гипотеза разреженности распределений терминов тем и тем документов.
* Гипотеза разреженности распределений терминов тем и тем документов.
-
* Принудительное разреживание в ЕМ-алгоритме. Оценка значимости (salience) параметров, метод [[OBD|Optimal Brain Damage]].
+
* Энтропийный регуляризатор и максимизация KL-дивергенции.
-
* Выделение нетематических терминов.
+
* Связь разреживания с L0-регуляризацией и методом разреживания нейронных сетей [[OBD|Optimal Brain Damage]].
-
* Генерация реалистичных модельных данных.
+
* Связь разреженности и единственности неотрицательного матричного разложения.
* Связь разреженности и единственности неотрицательного матричного разложения.
-
'''Сглаживание'''
+
'''Регуляризатор сглаживания.'''
* Модель латентного размещения Дирихле LDA.
* Модель латентного размещения Дирихле LDA.
 +
* Обоснование LDA через минимизацию KL–дивергенции. Виды сглаживающих распределений.
* Свойства распределения Дирихле, сопряжённость с мультиномиальным распределением.
* Свойства распределения Дирихле, сопряжённость с мультиномиальным распределением.
* Байесовский вывод. Сглаженные частотные оценки условных вероятностей.
* Байесовский вывод. Сглаженные частотные оценки условных вероятностей.
-
* Максимизация обоснованности модели. Численные методы оптимизации гиперпараметров.
+
* Оценки максимума апостериорной вероятности.
 +
* Численные методы оптимизации гиперпараметров.
 +
 
 +
'''Комбинирование разреживания и сглаживания.'''
 +
* Разреживание предметных тем и сглаживание фоновых тем. Автоматическое выделение стоп-слов.
 +
* Частичное обучение как выборочное сглаживание.
 +
 
 +
'''Ковариационные регуляризаторы.'''
 +
* Антиковариация тем.
 +
* Выявление корреляций между темами, модель CTM. Оценивание параметров модели (матрицы ковариаций).
 +
* Корреляция документов.
 +
* Тематические модели цитирования.
 +
 
 +
===Разреживание и сглаживание===
 +
 
 +
'''Сглаживание'''
* Сравнение LDA и PLSA. Экспериментальные факты: LDA скорее улучшает оценки редких слов, чем снижает переобучение.
* Сравнение LDA и PLSA. Экспериментальные факты: LDA скорее улучшает оценки редких слов, чем снижает переобучение.
* Дилемма разреживания и сглаживания.
* Дилемма разреживания и сглаживания.
 +
 +
'''Частичное обучение (Semi-supervised EM).'''
 +
* Виды частично размеченных данных: привязка документа к темам, привязка термина к темам, нерелевантность, переранжирование списков терминов тем и тем документов, виртуальные документы.
 +
* Использование частично размеченных данных для инициализации.
 +
* Использование частично размеченных данных в качестве поправок на М-шаге ЕМ-алгоритма.
'''Задание 1.3'''
'''Задание 1.3'''
Строка 218: Строка 245:
'''Литература:''' [Chemudugunta, 2006].
'''Литература:''' [Chemudugunta, 2006].
-
== Часть 2 ==
 
-
 
-
===Аддитивная регуляризация тематических моделей===
 
-
* ''Напоминания''. Вероятностная тематическая модель. Принцип максимума правдоподобия. KL-дивергенция. PLSA. EM-алгоритм.
 
-
 
-
'''Тихоновская регуляризация.'''
 
-
* Некорректность постановки задачи тематического моделирования.
 
-
* Аддитивная регуляризация.
 
-
* Общая формула M-шага для регуляризованного ЕМ-алгоритма.
 
-
* Концепция композитных многофункциональных тематических моделей.
 
-
 
-
'''Сглаживание и разреживание.'''
 
-
* Сглаживание. Альтернативное обоснование LDA через регуляризатор–дивергенцию.
 
-
* Разреживание. Энтропийный регуляризатор.
 
-
* Частичное обучение как выборочное сглаживание.
 
-
 
-
'''Ковариационные регуляризаторы.'''
 
-
* Антиковариация тем.
 
-
* Корреляция документов.
 
-
* Тематические модели цитирования.
 
===Синтаксические тематические модели===
===Синтаксические тематические модели===
Строка 323: Строка 330:
'''Дополнительная литература'''
'''Дополнительная литература'''
# Воронцов К. В., Потапенко А. А. Регуляризация, робастность и разреженность вероятностных тематических моделей // Компьютерные исследования и моделирование 2012 Т. 4, №12. С 693–706.
# Воронцов К. В., Потапенко А. А. Регуляризация, робастность и разреженность вероятностных тематических моделей // Компьютерные исследования и моделирование 2012 Т. 4, №12. С 693–706.
 +
# 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.
 +
# Vorontsov K. V., Potapenko A. A. Additive Regularization of Topic Models // Machine Learning Journal, Special Issue «Data Analysis and Intelligent Optimization», Springer, 2014.
# Blei D. M., Ng A. Y., Jordan M. I. Latent Dirichlet allocation // Journal of Machine Learning Research. — 2003. — Vol. 3. — Pp. 993–1022.
# 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.
# 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.

Версия 19:58, 6 октября 2014

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература: [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.

Ссылки

См. также

Личные инструменты