В машинном обучении встречаются задачи, где нужно изучить структуру данных, найти в них скрытые взаимосвязи и закономерности. Например, нам может понадобиться описать каждого клиента банка с помощью меньшего количества переменных — для этого можно использовать методы понижения размерности, основанные на матричных разложениях. Такие методы пытаются сформировать новые признаки на основе старых, сохранив как можно больше информации в данных. Другим примером может служить задача тематического моделирования, в которой для набора текстов нужно построить модель, объясняющую процесс формирования этих текстов из небольшого количества тем. Такие задачи назвают обучением без учителя. В отличие от обучения с учителем, в них не предполагают восстановление зависимости между объектами и целевой переменной. Из этого курса вы узнаете об алгоритмах кластеризации данных, с помощью которых, например, можно искать группы схожих клиентов мобильного оператора. Вы научитесь строить матричные разложения и решать задачу тематического моделирования, понижать размерность данных, искать аномалии и визуализировать многомерные данные.
Базовые тематические модели и EM-алгоритм
Loading...
From the course by Moscow Institute of Physics and Technology
Поиск структуры в данных
759 оценки
Moscow Institute of Physics and Technology
759 оценки
Course 3 of 6 in the Specialization Машинное обучение и анализ данных
From the lesson
Тематическое моделирование
Люди уже много веков сохраняют свои знания в виде книг, а крупнейшая на сегодняшний день коллекция информации — Интернет — состоит из огромного количества текстов. Тексты, по сути, являются наиболее популярным видом данных, и поэтому очень важно уметь искать в них закономерности. Тематическое моделирование — это способ семантического анализа коллекции текстовых документов. Тематическая модель позволяет для каждого документа найти темы, которые его описывают, и кроме того показывает, какие слова характеризуют ту или иную тему. Другими словами, мы находим более компактное представление большого набора текстов в виде нескольких тем. С математической точки зрения тематическая модель — это еще один вид матричного разложения, где в качестве исходной матрицы выступает матрица частот слов в документах. На четвертой неделе мы поговорим о том, где применяют тематические модели, какие они бывают, как их строить и как оценивать.
Meet the Instructors
Evgeniy Riabenko
Evgeny Sokolov
Victor Kantor
Emeli Dral
Константин Воронцовдоктор физико-математических наук, профессор
Кафедра интеллектуальных систем
[ЗАСТАВКА] В этом
видео мы с вами разберемся, как строятся вероятностные
тематические модели и как устроен основной алгоритм для их построения — EM-алгоритм.
Напомню, что в конце предыдущего видео мы пришли к постановке задачи,
которая по наблюдающимся словам в документах строит тематическую модель.
Постановка заключалась в максимизации логарифма правдоподобия,
к которому добавлен некоторый регуляризатор R — произвольная функция.
Но для того чтобы эту задачу было удобно решать,
от этой функции требуется только то, чтобы она была гладкой,
тогда можно к этой задаче применять условие Каруша — Куна — Таккера.
Естественно, выкладки я сейчас опускаю и просто показываю результат.
Это не решение, выраженное в аналитическом виде, к сожалению,
это всего лишь система уравнений, которую придется решать, но решать ее достаточно
удобно очень простым численным методом, который называется метод простых итераций.
И он же по совместительству здесь у нас оказывается EM-алгоритмом.
Это система уравнений, которая состоит из двух типов уравнений.
Первое, это так называемый E-шаг EM-алгоритма — это вычисление
условных распределений тем для каждого слова в каждом документе.
И то, что записано в первой строке этой системы уравнений, по сути дела,
не что иное, как просто формула Байеса, по которой мы можем выразить вот эти наши
вспомогательные переменные P, t, d, w в этой системе через параметры модели Φ и θ.
А вот формулы M-шага, они, наоборот, они выражают основные
параметры модели Φ и θ через вспомогательные переменные P, t, d, w.
И если откинуть регуляризатор, считать, что R = 0, то окажется,
что вот те формулы, которые здесь записаны — это просто частотные оценки
условных вероятностей слов в темах и тем в документах.
То есть если бы мы знали тему каждого слова, мы могли бы просто написать,
очень легко посчитать частотные оценки вероятностей условных слов в
темах и тем в документах.
Но поскольку мы не можем знать, на самом деле,
тему каждого слова в каждом документе, мы ее оцениваем вот так
вот по фактически формуле Байеса и получаем итерационный процесс,
где основные вспомогательные переменные оцениваются друг по другу поочередно.
Но и обращаю внимание на то, что оператор нормировки здесь переводит
произвольный вектор xt в вектор, координаты
которого неотрицательны и нормированы, то есть сумма их в точности равна 1.
То есть любой произвольный вещественный вектор переводится в вектор той
же размерности, который может играть роль дискретного распределения.
И вот через эту операцию нормирования векторов очень удобно оказалось
записать вот все уравнения этой системы уравнений.
Есть два очень известных частных случая этой системы —
ведь мы можем задавать регуляризатор в широких пределах.
Так вот, если он совсем не задан — R = 0, то мы получаем очень известный метод,
который в 1999 году был придуман и опубликован Томасом Хофманом.
Метод называется «вероятностный латентный семантический анализ», или PLSA.
Четыре года спустя появился следующий метод,
который был предложен Дэвидом Блеем,
Эндрю Энджи и Майклом Джорданом — три очень известных ученых.
Их статья по латентному размещению Дирихле — это, наверное,
самая цитируемая работа в тематическом моделировании.
Здесь я не буду очень подробно рассказывать все те соображения,
и почему именно распределение Дирихле здесь появляется,
и все те соображения, которые были использованы авторами этого метода.
Но с точки зрения регуляризации взгляд на этот метод довольно прост
— это вот такой вот регуляризатор, в котором появляются параметры β и α.
Авторы этого метода рассматривали его с точки зрения байесовского обучения,
и там делалось два вероятностных предположения.
Первое — что столбцы матриц Φ и θ могут быть не какими угодно,
они порождаются из распределения Дирихле.
Распределение Дирихле — это такое распределение, которое умеет порождать
векторы заданной размерности, которые являются нормированными неотрицательными,
то есть могут быть вероятностными распределениями.
Вот такая вот двухступенчатая порождающая модель: сначала из Дирихле порождаются
столбы матриц Φ и θ, а потом из них уже,
как мы в предыдущих видео обсуждали, порождается текст.
И второе предположение делается,
что если мы воспользуемся принципом максимума апостериорной вероятности,
то есть учтем эти априорные распределения в принципе максимума
совместного правдоподобия данных и модели Φ и θ,
которые тоже генерируются вероятностным образом,
то вот тогда мы сможем получить новую постановку задачи, которую
можно трактовать как регуляризованное логарифмированное правдоподобие.
Вот интересны свойства распределения Дирихле — почему-то все-таки они именно
оказались удобными в качестве априорных распределений.
Дело в том, что распределение Дирихле позволяет генерировать как разреженные,
так и такие вот сильно сглаженные дискретные распределения.
Причем случаи разреженности, вот как показано на левом графике,
нас как раз интересуют больше всего, потому что у нас есть гипотеза о том,
что каждая тема состоит, в общем-то, из небольшого числа тем, слов, и каждая...
каждый документ состоит из небольшого числа тем.
То есть кажется, что вот как раз, когда параметры распределения Дирихле меньше 1,
это самый интересный для нас случай,
потому что распределения получаются разреженными.
Ну и если параметры распределения Дирихле в точности 1, то это получается просто
равномерное распределение, и в таком случае LDA просто переходит в PLSA.
Интересен другой
взгляд на латентное размещение Дирихле,
даже более простой, но чтобы его рассказать, я должен ввести понятие
дивергенции Кульбака — Лейблера — это вообще очень полезное понятие,
и в машинном обучении, и в теории вероятности довольно часто встречается.
Это способ померять расстояние между двумя распределениями.
Поскольку нас интересует дискретное распределение,
мы сейчас только вот такой случай рассматриваем, а вообще,
в общем случае вместо суммы здесь должен стоять интеграл.
Итак, дивергенция Кульбака — Лейблера определяется
вот по такой несложной формуле.
Основные ее свойства — это то, что это неотрицательное значение,
и она равна 0 тогда и только тогда, когда распределение P и Q совпадают.
Мера — несимметричная, она, строго говоря, поэтому не является
функцией расстояния между распределениями P и Q в обычном смысле.
Она меряет в некотором смысле степень вложенности
распределения P в распределение Q.
Другой способ посмотреть на это — это связать
минимизацию дивергенции Кульбака — Лейблера с максимизацией правдоподобия.
Оказывается, что это две эквивалентные вещи.
Если P у нас — эмпирическое распределение,
а Q — это какая-то параметрическая модель распределения с параметром α,
то если мы используем принцип максимума правдоподобия,
для того чтобы определить этот параметр так, чтобы наше эмпирическое распределение
P как можно лучше соответствовало модели, то это все равно что минимизировать
дивергенцию Кульбака — Лейблера между этими двумя распределениями.
Вот такая вот интерпретация дает нам неплохую интуицию о смысле дивергенции и
о том, как ее можно использовать, а мы ее будем использовать в роли регуляризаторов.
Итак, другой взгляд на латентное размещение Дирихле,
как я говорил, более простой, заключается в том,
что если мы зададимся вот этими вот векторами — ну, рассмотрим матрицу Φ,
тогда мы задаемся векторами β, это вектор над словарем слов.
Так вот, те слова, которые соответствуют значениям
β > 1 — для них условные вероятности слов в
темах будут сглаживаться, они будут приближаться к значениям βw.
А если βw было < 1, то, наоборот, будет происходить разреживание,
и максимизация дивергенции Кульбака — Лейблера между двумя распределениями будет
означать, что распределение Φt, то есть столбцы матрицы Φ,
соответствующие теме t, они будут разреживаться,
то есть в них будут появляться больше нулевых или почти нулевых элементов.
Так вот, в отличие от байесовской точки зрения здесь нам не
нужно ни вводить распределения Дирихле, ни говорить об априорных
вероятностях — здесь достаточно сказать, что мы просто либо просто приближаем
столбцы матриц Φ и θ каким-то заданным распределением, либо удаляем от них.
И это вот приближение-удаление можно даже делать для разных
координат — в столбце некоторые сглаживать, некоторые разреживать.
Более того, появляется свобода задавать параметры β и α какими угодно,
без ограничений, что они должны быть строго положительны —
это ограничение шло из самого определения, что такое распределение Дирихле.
Но вот в нашей такой интерпретации, более свободной,
никаких ограничений на β и α не возникает, и можно, например,
сильнее разреживать эти распределения, добиваясь того,
чтобы модель была разреженной, то есть было как можно больше 0 в матрице Φ и θ,
но при этом, конечно, эти матрицы Φ и θ чтобы хорошо описывали нашу коллекцию.
Итак, от частных случаев перевернемся снова к общему случаю.
Мы ведь получили некую систему уравнений и договорились, что мы будем решать ее
методом простых итераций, то есть по вспомогательным переменным P, t, d,
w — это условные вероятности тем для слов в документах — мы будем считать основные
параметры модели Φ и θ, ну и, наоборот, по Φ и θ мы рассчитываем P, t, d, w.
Так вот, можно, ничего не меняя в формулах вот этой системы уравнений,
организовать вычислительный процесс метода простых итераций таким образом,
чтобы он шел максимально быстро,
причем именно на больших коллекциях текстовых документов.
Дело в том, что матрицы Φ и θ находятся в неравноправном положении.
Матрица Φ относится ко всей коллекции целиком,
и каждый ее столбец относится ко всей коллекции целиком,
а вот в матрице θ каждый столбец относится только к одному документу.
Поэтому если мы будем итерировать таким образом, что только после просмотра всей
коллекции мы будем обновлять матрицы Φ и θ, процесс будет работать крайне медленно.
Потому что матрица Φ будет обновляться слишком редко.
Мы можем делать по-другому: мы можем просматривать каждый документ,
строить для него тематическую модель и обновлять матрицу Φ.
Можем обрабатывать по несколько документов,
образуя такие вот порции или пакеты, батчи — по-разному их называют.
И после вычисления модели для нескольких документов обновлять матрицу Φ.
Вот оказалось, что такой процесс самый быстрый, и появились онлайновые алгоритмы.
Они появились не сразу, а примерно лет 5 назад,
и они сразу сделали тематическое моделирование очень эффективным
инструментом анализа больших коллекций текстов.
Оказалось, что матрица Φ может сходиться даже до того,
как мы просмотрели всю коллекцию.
Ну, например, коллекция — огромна, избыточна, содержит миллионы документов,
а оказывается, что после просмотра нескольких первых десятков тысяч,
мы уже получаем более или менее хорошую, устоявшуюся матрицу Φ — она уже сошлась.
И нам остается только тематизировать остальные документы.
Вот в таком режиме работы мы можем прогнать EM-алгоритм через всю коллекцию,
сделав фактически только одну итерацию.
Приходится, правда, делать несколько итераций для каждого документа.
Вот такой вот алгоритм — он называется онлайновым алгоритмом — используется
практически во всех основных пакетах по тематическому моделированию,
которые сегодня существуют даже в открытом коде и рекомендуются для
обработки больших коллекций.
Итак, краткое резюме.
EM-алгоритм — это основной инструмент в тематическом моделировании.
Онлайновый алгоритм, как мы сейчас видели, позволяет вообще делать обработку
большой коллекции за один проход.
И вот тот подход, который основан на использовании регуляризаторов,
хорош тем, что можно единообразно, с помощью одного и того же EM-алгоритма,
вот этого онлайнового, строить огромное разнообразие тематических моделей,
не только LDA и PLSA, а менять регуляризаторы,
добавлять новые регуляризаторы, учитывать все новые и новые требования к модели.
Вот такой вот подход оказался очень продуктивным, простым,
универсальным, гибким.
И в следующем видео я расскажу еще немножко больше о том,
какие конкретно регуляризаторы, кроме стандартных, как в LD, можно использовать.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
