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

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

(Различия между версиями)
Перейти к: навигация, поиск
(новый курс Воронцова на ВМК)
Строка 179: Строка 179:
{{well|
{{well|
-
Конспект лекций: [[Media:Voron-2013-ptm.pdf|Voron-2013-ptm.pdf, 3 МБ]] {{важно|(обновление 22 марта 2013)}}.
+
Конспект лекций: [[Media:Voron-2013-ptm.pdf|Voron-2013-ptm.pdf, 500 КБ]] {{важно|(обновление 22 марта 2013)}}.
}}
}}

Версия 13:08, 22 марта 2013

Содержание

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

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

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

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

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

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

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

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

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

Литература: [1].

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

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

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

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

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

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

Алгоритм вероятностного латентного семантического анализа (PLSA).

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

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

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

Гипотеза разреженности.

  • Проблема генерации реалистичных модельных данных.
  • Эмпирические законы Ципфа, Ципфа-Мандельброта, Хипса.
  • Гипотеза разреженности распределений терминов тем и тем документов.
  • Гипотеза об усечённых распределениях терминов тем в документах как ослабление гипотезы условной независимости.
  • Связь разреженности и единственности матричного разложения.

Задание.

  1. Реализовать генератор модельных данных. Реализовать вычисление эмпирических распределений терминов тем и тем документов.
  2. Реализовать оценки точности заданных распределений терминов тем и тем документов путём их сравнения с эмпирическими распределениями (с учётом перестановок тем). Вычислить оценки точности для исходных модельных распределений.
  3. Реализовать оценки точности модели p(w|d).
  4. Реализовать рациональный ЕМ-алгоритм.
  5. Исследовать зависимости точности модели и точности восстановления от числа итераций и от числа тем в модели (отличающегося от числа тем в исходных данных).
  6. Исследовать зависимость точности модели и точности восстановления от случайной инициализации. Построить распределения или доверительные интервалы точностей.
  7. Исследовать, при которых условиях проблема неустойчивости не возникает.

Литература: [5].

Модификации PLSA и оценивание качества тематических моделей

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

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

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

  • Эвристика замены апостериорного распределения несмещённым эмпирическим.
  • Эксперименты по подбору оптимального числа сэмплирований.

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

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

Разреженный ЕМ-алгоритм.

  • Гипотеза разреженности.
  • Эвристика принудительного разреживания в ЕМ-алгоритме. Варианты реализации.

Способы учёта дополнительной информации (частичное обучение).

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

Задание.

  1. В экспериментах на модельных данных сравнить оценки точности модели и точности восстановления для алгоритмов GEM, SEM, OEM.
  2. Исследовать зависимость точности модели и точности восстановления от степени разреженности исходных модельных данных.
  3. Исследовать влияние разреживания и частичного обучения на точность модели и точность восстановления.

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

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

  • Текстовые коллекции, библиотеки алгоритмов, источники информации.

Перплексия.

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

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

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

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

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

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

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

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

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

Визуализация тематических моделей.

Задание.

  1. В экспериментах на реальных данных построить зависимости перплексии обучающей и контрольной коллекции от числа итераций и числа тем.

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

  • Байесовская регуляризация. Свойства распределения Дирихле, сопряжённость с мультиномиальным распределением. Байесовский вывод. Сглаженные частотные оценки условных вероятностей.
  • Сэмплирование Гиббса как вариант стохастического ЕМ-алгоритма.
  • Численные методы оптимизации гиперпараметров.
  • Сравнение LDA и PLSA, подвержен ли PLSA переобучению.

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

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

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

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

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

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

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

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

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

  • Возможность для темы иметь несколько родительских тем.
  • Нисходящие и восходящие иерархические модели.

Тематические модели с выделением ключевых фраз

  • Задачи предварительной обработки текстов. Очистка (номера страниц, переносы, опечатки, числовая информация, оглавление, таблицы и рисунки), лемматизация, удаление стоп-слов, удаление редких слов.
  • Задача выделения терминов. Основные идеи: словари терминов, морфологический анализ предложений, поиск коллокаций, машинное обучение.
  • Статистические оценки неслучайности. Вывод критерия C-Value.
  • Морфологический анализатор.
  • Тематические модели с учётом синонимии (эффект burstiness).

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

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

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

  1. Маннинг К., Рагхаван П., Шютце Х. Введение в информационный поиск. — Вильямс, 2011.
  2. Воронцов К. В., Потапенко А. А. Регуляризация, робастность и разреженность вероятностных тематических моделей // Компьютерные исследования и моделирование 2012 Т. 4, №12. С 693–706.
  3. 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.

Дополнительная литература

  1. Blei D. M., Ng A. Y., Jordan M. I. Latent Dirichlet allocation // Journal of Machine Learning Research. — 2003. — Vol. 3. — Pp. 993–1022.
  2. 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.
  3. Hoffman M. D., Blei D. M., Bach F. R. Online Learning for Latent Dirichlet Allocation // NIPS, 2010. Pp. 856–864.
  4. 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, 500 КБ (обновление 22 марта 2013).