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

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

(Различия между версиями)
Перейти к: навигация, поиск
(вернул voron-2014-task-PTM.pdf)
м (Программа курса 2015)
Строка 59: Строка 59:
== Программа курса 2015 ==
== Программа курса 2015 ==
-
* Файл с описанием заданий: [[Media:voron-2015-task-PTM.pdf|voron-2014-task-PTM.pdf]]
+
* Файл с описанием заданий: [[Media:voron-2014-task-PTM.pdf|voron-2014-task-PTM.pdf]]
=== Задачи анализа текстов и вероятностные модели ===
=== Задачи анализа текстов и вероятностные модели ===
Строка 406: Строка 406:
* Коллекция Википедии.
* Коллекция Википедии.
* Коллекция arXiv.org.
* Коллекция arXiv.org.
-
* Коллекция социальной сети VK.
+
* Коллекция социальной сети VK.
==Литература==
==Литература==

Версия 23:24, 26 февраля 2016

Содержание

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

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

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

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

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

Введение

Презентация: (PDF, 0,6 МБ) — обновление 27.02.2016.

  • Понятие «темы», цели и задачи тематического моделирования. Основные предположения. Гипотеза «мешка слов». Методы предварительной обработки текстов.
  • Вероятностное пространство. Тема как латентная (ненаблюдаемая) переменная. Гипотеза условной независимости. Порождающая модель документа как вероятностной смеси тем.
  • Постановка обратной задачи восстановления параметров модели по данным.
  • Вероятностный латентный семантический анализ (PLSA).
  • Принцип максимума правдоподобия, Условия Каруша–Куна–Таккера. Униграммные модели коллекции и документа.
  • Теорема о необходимых условиях максимума правдоподобия для модели PLSA.
  • ЕМ-алгоритм и его элементарная интерпретация. Формула Байеса и частотные оценки условных вероятностей.
  • Рациональный ЕМ-алгоритм (встраивание Е-шага внутрь М-шага).

Обзор задач и моделей

Презентация: (PDF, 8,3 МБ) — обновление 27.02.2016.

  • Разновидности тематических моделей.
  • Средства визуализации тематических моделей.
  • Разведочный информационный поиск и требования к тематическим моделям.
  • Задача поиска релевантных тем в социальных сетях.
  • Применение тематического моделирования для информационного анализа электрокардиосигналов.
  • Динамическая модель коллекции пресс-релизов.
  • Проект BigARTM.
  • Открытые проблемы и направления исследований.

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

Презентация: (PDF, Х,Х МБ) — обновление ХХ.ХХ.2016.

  • Задача тематического моделирования как некорректно поставленная задача стохастического матричного разложения.
  • Эксперименты на синтетических данных. Демонстрация неустойчивости.
  • Эксперименты по устойчивости на реальных текстовых коллекциях.
  • Аддитивная регуляризация тематических моделей.
  • Теорема о необходимых условиях максимума правдоподобия для ARTM.
  • Дивергенция Кульбака-Лейблера.
  • Регуляризаторы сглаживания и разреживания.
  • Латентное размещение Дирихле (LDA). Свойства распределения Дирихле.
  • Принцип максимума апостериорной вероятности. LDA как частный случай ARTM.
  • Сравнение LDA и PLSA. Экспериментальные факты: LDA скорее улучшает оценки редких слов, чем снижает переобучение.

Регуляризаторы для улучшения интерпретируемости тем

Презентация: (PDF, Х,Х МБ) — обновление ХХ.ХХ.2016.

  • Разреживание предметных тем и сглаживание фоновых тем. Автоматическое выделение стоп-слов.
  • Частичное обучение как разновидность сглаживания.
  • Сфокусированные тематические модели. Использование словаря для выделения предметных тем. Примеры: выделение тематики эпидемий, межэтнических отношений.
  • Регуляризатор декоррелирования тем.
  • Регуляризатор когерентности тем.
  • Регуляризатор отбора тем.


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Робастная модель с фоном и шумом.
  • Упрощённая робастная модель.
  • Почему робастный PLSA лучше, чем LDA. Эффект повышения правдоподобия (перплексии) в робастных моделях с шумом.

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

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

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

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

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

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

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

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

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

  • Максимизация и минимизация KL-дивергенции.
  • Альтернативный вариант разреживания через L0-регуляризацию.
  • Связь разреженности и единственности неотрицательного матричного разложения.
  • Разреживание предметных тем и сглаживание фоновых тем. Автоматическое выделение стоп-слов.

Регуляризаторы частичного обучения.

  • Частичное обучение как выборочное сглаживание.
  • Сфокусированные тематические модели. Использование словаря для выделения предметных тем.
  • Пример: выделение тематики эпидемий, этнических конфликтов.

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

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

Регуляризаторы для классификации и регрессии.

  • Задачи регрессии на текстах. Примеры. Регуляризатор. Формула М-шага.
  • Задачи классификации текстов. Примеры. Регуляризатор. Формула М-шага.

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

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

Литература: [Воронцов, 2013, 2015], [Chemudugunta, 2006].

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

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

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

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

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

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

  • Лексическое ядро темы: множество типичных терминов темы.
  • Чистота и контрастность темы
  • Документное ядро темы: множество типичных документов темы.
  • Однородность темы: распределение расстояний между p(w|t) и p(w|t,d).
  • Конфликтность темы: близость темы к другим темам.

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

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

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

Внешние оценки качества тематических моделей

Оценивание интерпретируемости тем.

  • Экспертное оценивание интерпретируемости.
  • Асессорская разметка терминов и документов, релевантных теме.
  • Метод интрузий.
  • Радикальное улучшение интерпретируемости в n-граммных тематических моделях.

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

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

Суммаризация темы.

  • Проблема визуализации тем.
  • Выделение тематичных слов и предложений.
  • Кластеризация тематичных предложений.
  • Ранжирование тематичных предложений.
  • Асессорская разметка предложений, релевантных теме.
  • Задача автоматического именования темы.

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

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

Задание 1.4.

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

Литература:

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

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

Мультимодальная АРТМ.

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

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

Модели многоматричных разложений.

  • Понятие порождающей модальности.
  • Вывод формул М-шага.
  • Автор-тематическая модель (author-topic model).
  • Модель для выделения поведений объектов в видеопотоке.

Гиперграфовая модель.

  • Примеры транзакционных данных в социальных и рекламных сетях.
  • Вывод формул М-шага.

Литература:

Определение числа тем и иерархические модели

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

  • Регуляризатор и формула М-шага. Эффект строкового разреживания.
  • Определение истинного числа тем в экспериментах с полумодельными данными.
  • Гипотеза о несуществовании истинного числа тем.
  • Эффект отбрасывания малых, дублирующих и линейно зависимых тем.
  • Сравнение с моделью иерархических процессов Дирихле.

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

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

Послойное нисходящее построение тематической иерархии.

  • Регуляризатор матрицы Фи.
  • Регуляризатор матрицы Тета.
  • Измерение и оптимизация качества иерархических моделей.
  • Разреживание вероятностного отношения тема—подтема.

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

Литература: .

Тематические модели, учитывающие порядок слов

Мультиграммные модели.

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

Регуляризаторы для выделения энграмм.

  • Биграммная тематическая модель.

Сегментирующие тематические модели.

  • Позиционный регуляризатор, вывод формул М-шага.
  • Пост-обработка Е-шага.
  • Интерпретация текста как пучка временных рядов и задача разладки.
  • Алгоритм тематической сегментации.
  • Тематические модели предложений (sentence topic model).

Векторная модель word2vec.

  • Векторная модель word2vec и её интерпретация как латентной модели с матричным разложением.
  • Гибрид тематической модели и векторной модели word2vec.
  • Связь word2vec с регуляризатором когерентности.
  • Эксперименты с гибридной моделью W2V-TM.

Литература: .

Динамические и пространственные тематические модели

Тематические модели с модальностью времени.

  • Регуляризатор разреживания тем в каждый момент времени.
  • Регуляризаторы сглаживания темы как временного ряда.
  • Вывод M-шага для негладкого регуляризатора.

Тематические модели с модальностью геолокации.

  • Тематические модели социальных сетей.

Траектории регуляризации

Обучение с подкреплением

  • Контекстный многорукий бандит.
  • Инкрементная регрессия.
  • Регрессия с верхними доверительными границами (UCB).

Задача оптимизации трактории в пространстве коэффициентов регуляризации

  • Относительные коэффициенты регуляризации.
  • Признаковое описание контекста. Метрики качества тематической модели.
  • Функция премии и скаляризация критериев.
  • Особенности реализации обучения с подкреплением в онлайновом ЕМ-алгоритме.

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

Навигация по тематической модели.

  • Визуализатор TMVE.
  • Визуализатор Termite.
  • Визуализатор для BigARTM.

Методы визуализации.

  • Задача и методы многомерного шкалирования.
  • Визуализация «дорожной карты» темы или набора тем.
  • Визуализация тематических иерархий.
  • Визуализация динамических моделей, метафора «реки тем».
  • Визуализация тематической структуры документа.
  • Визуализация модели трёх источников.

Средства разведочного поиска.

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

Большие данные

Параллельные и распределённые алгоритмы.

  • Обзор подходов к распараллеливанию онлайнового EМ-алгоритма.
  • Распараллеливание онлайнового EМ-алгоритма в BigARTM.
  • Распределённое хранение коллекции.

Обработка больших коллекций в BigARTM.

  • Особенности предварительной обработки.
  • Коллекция Википедии.
  • Коллекция arXiv.org.
  • Коллекция социальной сети VK.

Литература

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

  1. Vorontsov K. V., Potapenko A. A. Additive Regularization of Topic Models // Machine Learning. Special Issue “Data Analysis and Intelligent Optimization with Applications”: Volume 101, Issue 1 (2015), Pp. 303-323. Русский перевод
  2. Vorontsov K. V., Frei O. I., Apishev M. A., Romov P. A., Suvorova M. A., Yanina A. O. Non-Bayesian Additive Regularization for Multimodal Topic Modeling of Large Collections // Proceedings of the 2015 Workshop on Topic Models: Post-Processing and Applications, October 19, 2015, Melbourne, Australia. ACM, New York, NY, USA. pp. 29–37.
  3. Маннинг К., Рагхаван П., Шютце Х. Введение в информационный поиск. — Вильямс, 2011.
  4. 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.
  5. 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. Воронцов К. В., Потапенко А. А. Модификации EM-алгоритма для вероятностного тематического моделирования // Машинное обучение и анализ данных. — 2013. — T. 1, № 6. — С. 657–686.
  2. Воронцов К. В., Фрей А. И., Ромов П. А., Янина А. О., Суворова М. А., Апишев М. А. BigARTM: библиотека с открытым кодом для тематического моделирования больших текстовых коллекций // Аналитика и управление данными в областях с интенсивным использованием данных. XVII Международная конференция DAMDID/RCDL’2015, Обнинск, 13-16 октября 2015.
  3. Blei D. M., Ng A. Y., Jordan M. I. Latent Dirichlet allocation // Journal of Machine Learning Research. — 2003. — Vol. 3. — Pp. 993–1022.
  4. 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.
  5. 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.
  6. 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.
  7. Hoffman M. D., Blei D. M., Bach F. R. Online Learning for Latent Dirichlet Allocation // NIPS, 2010. Pp. 856–864.
  8. 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.
  9. 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.

Ссылки